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)
}