shape/case_enum/

one.rs

use indexmap::IndexSet;

use crate::location::Location;
use crate::merge::MergeSet;
use crate::Shape;
use crate::ShapeCase;

/// 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, PartialEq, Eq, Hash)]
pub struct One {
    pub(crate) shapes: MergeSet<Shape>,
}

impl One {
    pub fn is_empty(&self) -> bool {
        self.shapes.is_empty()
    }

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

    pub fn contains(&self, shape: &Shape) -> bool {
        self.shapes.contains(shape)
    }
}

impl Shape {
    pub fn never(locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::new(
            ShapeCase::One(One {
                shapes: MergeSet::new([]),
            }),
            locations,
        )
    }

    #[must_use]
    pub fn is_never(&self) -> bool {
        matches!(self.case(), ShapeCase::One(One { shapes }) if shapes.is_empty())
    }
}

/// 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: IndexSet<Location>) -> Shape {
    let mut shapes = shapes.peekable();
    if shapes.peek().is_none() {
        // The empty One<> union represents an unsatisfiable shape
        // analogous to TypeScript's `never` type.
        return Shape::never(locations);
    }

    let mut new_shapes = MergeSet::new([]);

    // Flatten any nested `One` shapes
    for shape in shapes {
        if let ShapeCase::One(One {
            shapes: inner_shapes,
        }) = shape.case.as_ref()
        {
            locations.extend(shape.locations().cloned());
            new_shapes.extend(inner_shapes);
        } else {
            new_shapes.insert(shape);
        }
    }

    if new_shapes.is_empty() {
        return Shape::never(locations.iter().cloned());
    }

    // 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.insert(Shape::bool(
                true_shapes
                    .chain(false_shapes)
                    .flat_map(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)
}