shape/case_enum/

one.rs

use indexmap::IndexSet;

use crate::case_enum::Error;
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 {
    /// The unsatisfiable shape, analogous to TypeScript's `never` type: an
    /// empty `One<>` union, which no value inhabits.
    ///
    /// A `Never` is always the end of some line of reasoning. It may be an
    /// intersection of incompatible types, a `!` assertion on a shape that is
    /// always `None`, or a union with nothing left in it, and a caller handed
    /// a bare `Never` cannot tell which. So `reason` is required, and is
    /// attached as an [`Error`] in the shape's [`crate::meta::ShapeMeta`],
    /// exactly as [`Shape::error`] attaches its message. It is reachable via
    /// [`own_errors`](Shape::own_errors) and [`errors`](Shape::errors), and
    /// renders as the `(err "...")` suffix of
    /// [`pretty_print`](Shape::pretty_print).
    ///
    /// The reason is diagnostic, never semantic. [`PartialEq`] and
    /// [`Hash`](std::hash::Hash) for [`Shape`] compare only the
    /// [`ShapeCase`], so two `Never`s with different reasons remain equal and
    /// hash alike, and [`is_never`](Shape::is_never) does not consult the
    /// reason either.
    ///
    /// Write the reason as a statement of the conflict rather than of its
    /// consequence, for example `"no value is both a number and a string"`
    /// rather than `"this can never match"`, so that it still reads correctly
    /// when it surfaces nested inside a larger diagnostic.
    #[must_use]
    pub fn never(reason: impl Into<String>, locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::new_with_errors(
            ShapeCase::One(One {
                shapes: MergeSet::new([]),
            }),
            locations,
            [Error {
                message: reason.into(),
            }],
        )
    }

    #[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("a union of no shapes admits no value", 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()
        {
            locations.extend(shape.locations().cloned());
            new_shapes.extend(inner_shapes);
        } else {
            new_shapes.insert(shape);
        }
    }

    if new_shapes.is_empty() {
        // Flattening consumed every member, which means every member was
        // itself a Never. Those members' own reasons are dropped rather than
        // collected here, so this reason states only what is certain from
        // this vantage point.
        return Shape::never(
            "every member of this union admits no value",
            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(), 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(), 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(), 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(), 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)
}