shape/

accepts.rs

use crate::case_enum::Error;
use crate::child_shape::NamedShapePathKey;

use super::Shape;
use super::ShapeCase;

/// The `Shape::validate*` methods return a vector of `ShapeMismatch` errors
/// that is non-empty when validation fails.
///
/// Each `ShapeMismatch` error contains the `expected` shape, the `received`
/// shape, and a `path` of `NamedShapePathKey` elements that leads from the root
/// shape to the nested object/array location where the mismatch happened.
///
/// Conveniently, the `expected`/`received` terminology works for both the
/// `expected.accepts(received)` and `received.satisfies(expected)` directions
/// of comparison, so it doesn't matter that `ShapeMismatch` errors happen to be
/// generated by the internal `satisfies_at_path` method rather than by the
/// `validate` method (which would also work).
///
/// Once issue #5 is implemented, you'll be able to obtain source location
/// information from the `expected` and `received` shapes (instead of adding
/// additional fields to the `ShapeMismatch` struct).
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub struct ShapeMismatch {
    pub expected: Shape,
    pub received: Shape,
    pub path: Vec<NamedShapePathKey>,
}

impl Shape {
    /// Returns true if the other shape meets all the expectations of the self
    /// shape. In set theory terms, the set of all values accepted by other is a
    /// subset of the set of all values accepted by self.
    #[must_use]
    pub fn accepts(&self, other: &Shape) -> bool {
        other.satisfies(self)
    }

    /// Returns true iff the given [`serde_json::Value`] satisfies self.
    #[must_use]
    pub fn accepts_json(&self, json: &serde_json::Value) -> bool {
        self.accepts(&Shape::from_json(json))
    }

    /// Returns true iff the given [`serde_json_bytes::Value`] satisfies self.
    pub fn accepts_json_bytes(&self, json: &serde_json_bytes::Value) -> bool {
        self.accepts(&Shape::from_json_bytes(json))
    }

    /// Validates that all expectations of the `self` shape are met by the
    /// `to_be_validated` shape, erroring with a non-empty vector of
    /// `ShapeMismatch` errors when validation fails.
    ///
    /// Note that `validate` is closer to `accepts` than `satisfies` in terms of
    /// the direction of the comparison, which is why the implementation uses
    /// `to_be_validated.satisfies_at_path(self, ...)` rather than
    /// `self.satisfies_at_path(to_be_validated, ...)`.
    #[must_use]
    pub fn validate(&self, to_be_validated: &Shape) -> Vec<ShapeMismatch> {
        to_be_validated.satisfies_at_path(self, &mut Vec::new())
    }

    /// `Shape::validate_json` is to `Shape::validate` as `Shape::accepts_json`
    /// is to `Shape::accepts`.
    #[must_use]
    pub fn validate_json(&self, json: &serde_json::Value) -> Vec<ShapeMismatch> {
        self.validate(&Shape::from_json(json))
    }

    /// `Shape::validate_json_bytes` is to `Shape::validate` as
    /// `Shape::accepts_json_bytes` is to `Shape::accepts`.
    pub fn validate_json_bytes(&self, json: &serde_json_bytes::Value) -> Vec<ShapeMismatch> {
        self.validate(&Shape::from_json_bytes(json))
    }

    /// Returns `true` if the `self` shape meets all the expectations of the
    /// `other` shape. In set theory terms, `self` satisfying `other` means the
    /// set of all values accepted by `self` is a subset of the set of all
    /// values accepted by `other`.
    ///
    /// The `satisfies` method is the inverse of the `accepts` method, in the
    /// sense that `a.accepts(b)` is equivalent to `b.satisfies(a)`. For
    /// historical reasons, the bulk of the `accepts`/`satisfies` logic happens
    /// in the internal `satisfies_at_path` method, though I have since realized
    /// the `accepts` direction generalizes a bit better to situations where
    /// `other` is not a `Shape`, such as `Shape::accepts_json(&self, json:
    /// &serde_json::Value)`.
    #[must_use]
    pub fn satisfies(&self, other: &Shape) -> bool {
        self.satisfies_at_path(other, &mut Vec::new()).is_empty()
    }

    #[allow(clippy::too_many_lines)]
    fn satisfies_at_path(
        &self,
        other: &Shape,
        path: &mut Vec<NamedShapePathKey>,
    ) -> Vec<ShapeMismatch> {
        let mut mismatches = Vec::new();

        // Helper closure that translates boolean results to vector results. The
        // `path` and `mismatches` parameters are always the local parameter and
        // variable of the same names from the outer scope, but passing them in
        // this way simplifies ownership logic and strips mutability.
        let report = |satisfies: bool,
                      path: &[NamedShapePathKey],
                      mismatches: Vec<ShapeMismatch>|
         -> Vec<ShapeMismatch> {
            if satisfies {
                // Use the report closure only in situations where the truth of
                // `satisfies` should hide any previous mismatches.
                vec![]
            } else {
                // Concatenate earlier mismatches with the current mismatch.
                [
                    mismatches,
                    vec![ShapeMismatch {
                        expected: other.clone(),
                        received: self.clone(),
                        path: path.to_vec(),
                    }],
                ]
                .concat()
            }
        };

        match other.case() {
            ShapeCase::One(other_shapes) => {
                // If the union is empty (i.e. other.is_never()), then the only
                // self shapes that can satisfy this empty union are other never
                // shapes and None.
                if other_shapes.is_empty() {
                    return if self.is_never() || self.is_none() {
                        Vec::new()
                    } else {
                        // Reporting this error is important, since there are no
                        // self shapes to produce mismatches below.
                        vec![ShapeMismatch {
                            expected: other.clone(),
                            received: self.clone(),
                            path: path.clone(),
                        }]
                    };
                }

                // If self satisfies any single shape in the union, then self
                // satisfies the union.
                for other_shape in other_shapes {
                    let other_mismatches = self.satisfies_at_path(other_shape, path);
                    if other_mismatches.is_empty() {
                        return Vec::new();
                    }
                    mismatches.extend(other_mismatches);
                }
                // Importantly, we do not return false here (in contrast with
                // the ::All case below), because the union might still be
                // satisfied by self, e.g. when self is Bool and the union
                // contains both true and false as members.
                //
                // We will need to handle ShapeCase::One logic in the ::Bool
                // case below, but otherwise the loop above saves most of the
                // cases below from explicitly worrying about other being a
                // ShapeCase::One.
            }

            ShapeCase::All(other_shapes) => {
                // If other is an intersection, then self must satisfy all of
                // the member shapes. Returning unconditionally from this case
                // means we don't have to worry about other being a
                // ShapeCase::All below.
                return other_shapes
                    .iter()
                    .flat_map(|other_shape| self.satisfies_at_path(other_shape, path))
                    .collect::<Vec<_>>();
            }

            // Sometimes we don't know anything (yet) about the structure of a
            // shape, but still want to refer to it by name and access the
            // shapes of subproperties (symbolically if not concretely). That's
            // what the ShapeCase::Name variant models.
            //
            // The ShapeCase::Name name parameter is either an identifier
            // referring to a named shape (like ID or JSON or Product) or a
            // string like "$this" when referring to the type of a variable.
            //
            // When it comes to ShapeCase::satisfies, we have a policy decision
            // to make here: are named shape references satisfied by any shape,
            // or satisfied by none? Do they satisfy any shape, or satisfy none?
            //
            // By policy (and because it works well in practice) we say named
            // shape references are satisfied by any shape, but satisfy no
            // shape. The _expectations_ narrative may help here: a named shape
            // imposes no expectations on shapes that seek to satisfy it, so all
            // succeed; however, a named shape also meets no expectations of any
            // other shape, except (trivially) itself. This interpretation would
            // make named shape references behave like the `unknown` type in
            // TypeScript, which is satisfied by all but satisfies none.
            //
            // Given this way of handling named shape references, we
            // conveniently do not need a separate enum variant to represent the
            // general JSON type, as it is just another named shape reference,
            // akin to `unknown` in TypeScript.
            ShapeCase::Name(_name, _subpath) => {
                // When other is a named shape reference, any self satisfies it.
                return Vec::new();
            }

            ShapeCase::Unknown => {
                // Unknown shapes are satisfied by any shape.
                return Vec::new();
            }

            ShapeCase::Error(Error { partial, .. }) => {
                // If other is an error shape, it accepts (is satisfied by)
                // itself trivially.
                if self.case == other.case {
                    return Vec::new();
                }

                // If the other error has Some(partial) shape, self satisfies
                // other if it satisfies that partial shape.
                if let Some(partial) = partial {
                    return self.satisfies_at_path(partial, path);
                }

                // Otherwise, the other error shape is not satisfied by self.
                return vec![ShapeMismatch {
                    expected: other.clone(),
                    received: self.clone(),
                    path: path.clone(),
                }];
            }

            // None shapes are satisfied only by themselves and the empty union
            // produced by Shape::never.
            ShapeCase::None => {
                return if self.is_none() || self.is_never() {
                    Vec::new()
                } else {
                    vec![ShapeMismatch {
                        expected: other.clone(),
                        received: self.clone(),
                        path: path.clone(),
                    }]
                };
            }

            _ => {
                // Fall through to matching against self...
            }
        }

        match self.case() {
            ShapeCase::Bool(Some(value)) => report(
                match other.case() {
                    ShapeCase::Bool(other_value) => {
                        Some(value) == other_value.as_ref() || other_value.is_none()
                    }
                    // We already handled the ::One and ::All cases above.
                    _ => false,
                },
                path,
                mismatches,
            ),

            ShapeCase::Bool(None) => report(
                (|| match other.case() {
                    ShapeCase::Bool(None) => true,

                    // This case goes beyond the basic ShapeCase::One handling
                    // provided at the top of the function, because we want to allow
                    // ::Bool(None) to match a union of true and false.
                    ShapeCase::One(other_shapes) => {
                        let true_shape = Shape::bool_value(true, []);
                        let false_shape = Shape::bool_value(false, []);
                        let mut true_satisfies = false;
                        let mut false_satisfies = false;

                        for other_shape in other_shapes {
                            // We already tested whether self.satisfies(other_shape)
                            // above, so we don't need to retest that here.
                            if true_shape.satisfies_at_path(other_shape, path).is_empty() {
                                true_satisfies = true;
                            }
                            if false_shape.satisfies_at_path(other_shape, path).is_empty() {
                                false_satisfies = true;
                            }
                            // If both true and false satisfy at least one
                            // other_shape, then the union is satisfied by Bool.
                            if true_satisfies && false_satisfies {
                                // Returns from the (|| match ...)() closure.
                                return true;
                            }
                        }

                        false
                    }

                    _ => false,
                })(),
                path,
                mismatches,
            ),

            ShapeCase::String(value) => report(
                match other.case() {
                    ShapeCase::String(other_value) => value == other_value || other_value.is_none(),
                    // We already handled the ::One case above.
                    _ => false,
                },
                path,
                mismatches,
            ),

            ShapeCase::Int(value) => report(
                match other.case() {
                    ShapeCase::Int(other_value) => value == other_value || other_value.is_none(),
                    // All Int values are also (trivially convertible to) Float
                    // values, so Int is a subshape of Float.
                    ShapeCase::Float => true,
                    // We already handled the ::One case above.
                    _ => false,
                },
                path,
                mismatches,
            ),

            ShapeCase::Float => report(matches!(other.case(), ShapeCase::Float), path, mismatches),

            // Both ::Null and ::None satisfy only themselves, but they have an
            // important difference in behavior when they appear in ::All
            // intersections. The null value "poisons" intersections, reducing
            // the whole intersection to null, which can be appropriate behavior
            // when reporting certain kinds of top-level errors. The None value
            // simply disappears from intersections, as it imposes no additional
            // constraints on the intersection shape.
            ShapeCase::Null => report(matches!(other.case(), ShapeCase::Null), path, mismatches),

            // None is satisfied by itself and the unsatisfiable empty ::One
            // union produced by Shape::never.
            ShapeCase::None => report(other.is_none() || other.is_never(), path, mismatches),

            // ShapeCase::Unknown satisfies no other shapes except itself. We
            // already handled the case when other is ::Unknown above, so we can
            // report false here.
            ShapeCase::Unknown => report(false, path, mismatches),

            ShapeCase::Array { prefix, tail } => match other.case() {
                ShapeCase::Array {
                    prefix: other_prefix,
                    tail: other_tail,
                } => {
                    let mismatch_count = mismatches.len();

                    for (i, other_shape) in other_prefix.iter().enumerate() {
                        path.push(NamedShapePathKey::from(i));
                        if let Some(shape) = prefix.get(i) {
                            mismatches.extend(shape.satisfies_at_path(other_shape, path));
                        } else {
                            mismatches.extend(tail.satisfies_at_path(other_shape, path));
                        }
                        path.pop();
                    }

                    if mismatches.len() > mismatch_count {
                        return mismatches;
                    }

                    #[allow(clippy::match_same_arms)]
                    match (tail.case(), other_tail.case()) {
                        // If neither self nor other have a rest shape (and
                        // prefix satisfies other_prefix), self satisfies other.
                        (ShapeCase::None, ShapeCase::None) => Vec::new(),
                        // If self has a rest shape but other does not, other
                        // has no expectations about self's rest shape (and we
                        // already checked prefixes), so self satisfies other.
                        (_, ShapeCase::None) => Vec::new(),
                        // If self has no rest shape while other does, self will
                        // always be a static tuple of elements that we know
                        // satisfies other. Other may permit additional rest
                        // elements, but their absence does not prevent
                        // satisfaction.
                        (ShapeCase::None, _) => Vec::new(),
                        // If ShapeCase::None is not involved on either side,
                        // then other expects a certain rest shape and self has
                        // its own rest shape, so rest must satisfy other_tail.
                        _ => {
                            path.push(NamedShapePathKey::AnyIndex);
                            mismatches.extend(tail.satisfies_at_path(other_tail, path));
                            path.pop();

                            if mismatches.len() > mismatch_count {
                                mismatches
                            } else {
                                Vec::new()
                            }
                        }
                    }
                }

                // We already handled the ::One and ::All cases above.
                _ => report(false, path, mismatches),
            },

            ShapeCase::Object { fields, rest } => match other.case() {
                ShapeCase::Object {
                    fields: other_fields,
                    rest: other_rest,
                } => {
                    let mismatch_count = mismatches.len();

                    // Check that all fields expected by other are present in
                    // self.
                    for (field_name, field_shape) in other_fields {
                        path.push(NamedShapePathKey::from(field_name.as_str()));
                        if let Some(self_field_shape) = fields.get(field_name) {
                            mismatches
                                .extend(self_field_shape.satisfies_at_path(field_shape, path));
                        } else {
                            // Optional properties of shape S can be represented
                            // by Shape::one(&[S, Shape::none()]) field shapes
                            // in other_fields, which Shape::none() (i.e. the
                            // shape of the undefined field in self) satisfies.
                            mismatches.extend(Shape::none().satisfies_at_path(field_shape, path));
                        }
                        path.pop();
                    }

                    if mismatches.len() > mismatch_count {
                        return mismatches;
                    }

                    #[allow(clippy::match_same_arms)]
                    match (rest.case(), other_rest.case()) {
                        // If neither self nor other have a rest shape (and fields
                        // satisfies other_fields), self satisfies other.
                        (ShapeCase::None, ShapeCase::None) => Vec::new(),
                        // If self has a rest shape but other does not, other has
                        // no expectations about self's rest shape (and we already
                        // checked static fields), so self satisfies other.
                        (_, ShapeCase::None) => Vec::new(),
                        // If self has no rest shape while other does, self will
                        // always be a static set of fields that we know
                        // satisfies other. Other may permit additional rest
                        // properties, but their absence does not prevent
                        // satisfaction.
                        (ShapeCase::None, _) => Vec::new(),
                        // If ShapeCase::None is not involved on either side,
                        // then other expects a certain rest shape and self has
                        // its own rest shape, so rest must satisfy other_rest.
                        _ => {
                            path.push(NamedShapePathKey::AnyField);
                            mismatches.extend(rest.satisfies_at_path(other_rest, path));
                            path.pop();

                            if mismatches.len() > mismatch_count {
                                mismatches
                            } else {
                                Vec::new()
                            }
                        }
                    }
                }

                // We already handled the ::One and ::All cases above.
                _ => report(false, path, mismatches),
            },

            // If *self* is a ShapeCase::One union, then every possibility must
            // satisfy other. For example, if self is true | false, and other is
            // Bool, then since true and false each individually satisfy Bool,
            // the union true | false satisfies Bool.
            ShapeCase::One(shapes) => {
                if shapes.is_empty() {
                    if other.is_never() || other.is_none() {
                        Vec::new()
                    } else {
                        vec![ShapeMismatch {
                            expected: other.clone(),
                            received: self.clone(),
                            path: path.clone(),
                        }]
                    }
                } else {
                    let mismatch_count = mismatches.len();
                    for shape in shapes {
                        mismatches.extend(shape.satisfies_at_path(other, path));
                    }
                    if mismatches.len() > mismatch_count {
                        mismatches
                    } else {
                        Vec::new()
                    }
                }
            }

            // If self is a ShapeCase::All intersection, then it satisfies other
            // if any of the member shapes satisfy other.
            //
            // Tricky example involving an unsimplified ShapeCase::All:
            // { a: Int } & { b: Int } should satisfy { a: Int, b: Int }
            ShapeCase::All(shapes) => {
                for shape in shapes {
                    let other_mismatches = self.satisfies_at_path(shape, path);
                    if other_mismatches.is_empty() {
                        return other_mismatches;
                    }
                    mismatches.extend(other_mismatches);
                }
                mismatches
            }

            ShapeCase::Error(Error { partial, .. }) => {
                // We already tested whether self == other when other is an
                // error shape above, so we only need to test the partial shape
                // in the other direction here.
                //
                // If self is an error shape, it satisfies itself trivially, and
                // if it has Some(partial) shape, the error satisfies other if
                // that partial shape does.
                //
                // In cases when the partial shape represents a best guess at
                // the intended shape, mismatches can provide guidance without
                // interfering with satisfaction logic.
                if self.case == other.case {
                    Vec::new()
                } else if let Some(partial) = partial {
                    partial.satisfies_at_path(other, path)
                } else {
                    report(false, path, mismatches)
                }
            }

            ShapeCase::Name(_name, _subpath) => {
                // When self is a named shape reference, it satisfies no other
                // except itself. This makes named shape references more like
                // TypeScript's `unknown` type than its `any` type (which
                // satisfies all and is satisfied by all).
                report(self.case == other.case, path, mismatches)
            }
        }
    }
}