shape/case_enum/
one.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
use super::deduplicate_shape::extend_or_insert_shape;
use crate::location::Location;
use crate::{Shape, ShapeCase};
use indexmap::IndexSet;

/// The contents of a [`ShapeCase::One`]. Constructing this requires simplifying the shapes it
/// contains so there aren't unnecessary duplicates left over and so hashes are consistent.
///
/// This intentionally can't be constructed directly because it prevents accidental unsimplified
/// [`ShapeCase::One`]s. Construct this via [`Shape::one`] instead.
#[derive(Clone, Debug, Eq)]
pub struct One {
    shapes: Vec<Shape>,
}

impl One {
    pub fn iter(&self) -> impl Iterator<Item = &Shape> {
        self.shapes.iter()
    }
}

impl<'a> IntoIterator for &'a One {
    type Item = &'a Shape;
    type IntoIter = std::slice::Iter<'a, Shape>;

    fn into_iter(self) -> Self::IntoIter {
        self.shapes.iter()
    }
}

impl PartialEq<One> for One {
    fn eq(&self, other: &One) -> bool {
        self.shapes.iter().collect::<IndexSet<_>>() == other.shapes.iter().collect::<IndexSet<_>>()
    }
}

/// Builds a [`Shape`] with [`ShapeCase::One`] _unless_ the shapes can simplify to a single
/// [`ShapeCase`].
pub(crate) fn one(shapes: impl Iterator<Item = Shape>, mut locations: Vec<Location>) -> Shape {
    let mut shapes = shapes.peekable();
    if shapes.peek().is_none() {
        return Shape::none();
    }

    let mut new_shapes = Vec::new();

    // Flatten any nested `One` shapes
    for shape in shapes {
        if let ShapeCase::One(One { shapes }) = shape.case.as_ref() {
            locations.extend(shape.locations);
            for inner_shape in shapes {
                extend_or_insert_shape(&mut new_shapes, inner_shape.clone());
            }
        } else {
            extend_or_insert_shape(&mut new_shapes, shape);
        }
    }

    // The presence of the general Unknown shape subsumes all
    // other union member shapes.
    if let Some(unknown) = new_shapes
        .iter()
        .find(|shape| shape.case() == ShapeCase::Unknown)
    {
        return unknown.clone();
    }

    // The presence of the general Bool shape subsumes all
    // specific literal boolean shapes.
    let boolean_shape = ShapeCase::Bool(None);
    if new_shapes.iter().any(|shape| shape.case() == boolean_shape) {
        new_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Bool(Some(_))));
    } else {
        // Also, if new_shapes contains both true and false, then we
        // can remove them and simplify the union by adding
        // boolean_shape.
        //
        // Theoretically this same logic could apply to Int or
        // String, but that would require somehow forming a union of
        // every possible integer or string value.
        let true_shape = ShapeCase::Bool(Some(true));
        let false_shape = ShapeCase::Bool(Some(false));

        let mut true_shapes = new_shapes
            .iter()
            .filter(|shape| shape.case() == true_shape)
            .peekable();
        let mut false_shapes = new_shapes
            .iter()
            .filter(|shape| shape.case() == false_shape)
            .peekable();

        if true_shapes.peek().is_some() && false_shapes.peek().is_some() {
            new_shapes.push(Shape::bool(
                true_shapes
                    .chain(false_shapes)
                    .flat_map(|shape| &shape.locations)
                    .cloned(),
            ));
            new_shapes.retain(|shape| !matches!(shape.case(), ShapeCase::Bool(Some(_))));
        }
    }

    // The presence of the general String shape subsumes all
    // specific literal string shapes.
    if new_shapes
        .iter()
        .any(|shape| shape.case() == ShapeCase::String(None))
    {
        new_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::String(Some(_))));
    }

    if new_shapes
        .iter()
        .any(|shape| shape.case() == ShapeCase::Float)
    {
        // The presence of the general Float shape subsumes all
        // general and literal Int shapes.
        new_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Int(_)));
    } else if new_shapes
        .iter()
        .any(|shape| shape.case() == ShapeCase::Int(None))
    {
        // The presence of the general Int shape subsumes all
        // specific literal int shapes.
        new_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Int(Some(_))));
    }

    // It's tempting to try to simplify new_shapes further by
    // removing any shape that satisfies another shape, since that's
    // one interpretation of the cases above: specific primitive
    // value shapes like 123 satisfy general primitive shapes like
    // Int, and therefore add nothing to the union if the general
    // shape is present.
    //
    // However, in the cases above, the specific value shapes happen
    // to be fully subsumed by the general shape, adding no further
    // information to the general union. When we're dealing with
    // arrays or objects, a shape can satisfy another shape and
    // still add information to the union, so information would be
    // lost if we removed such shapes here.
    //
    // For example, since { a: Int } is a more general shape than
    // (is satisfied by) { a: Int, b: String }, including { a: Int,
    // b: String } in a union with { a: Int } technically does not
    // change the set of values represented by the union, but you
    // might still like to know that the b field's shape across the
    // union is String | None, rather than just None, as it would be
    // if we removed the more specific shape from new_shapes.
    //
    // As a side note, detecting satisfaction among all pairs of
    // members of the union is a quadratic operation in the size of
    // the union, so it's nice we don't need to do all that work.

    // A union of one shape is equivalent to that shape by itself.
    if let (Some(only_shape), 1) = (new_shapes.first(), new_shapes.len()) {
        return only_shape.clone();
    }

    Shape::new(ShapeCase::One(One { shapes: new_shapes }), locations)
}