shape/

lib.rs

mod accepts;
mod case_enum;
mod child_shape;
mod display;
mod from_json;
mod hashing;
mod helpers;
mod merge;
mod meta;
pub mod name;

pub mod graphql;
pub mod location;
#[cfg(test)]
mod tests;
mod visitor;

use std::hash::Hash;
use std::hash::Hasher;
use std::iter::empty;

pub use accepts::ShapeMismatch;
pub use case_enum::Error;
pub use case_enum::ShapeCase;
pub use helpers::OffsetRange;
use helpers::Ref;
use indexmap::IndexMap;
use indexmap::IndexSet;
use meta::ShapeMeta;
pub use visitor::ShapeVisitor;

use crate::case_enum::all::all;
use crate::case_enum::one::one;
use crate::location::Location;
use crate::merge::MergeSet;
use crate::name::Name;
use crate::name::WeakScope;

/// The `shape::Shape` struct provides a recursive, immutable, reference-counted
/// tree/DAG format for representing and enforcing common structures and usage
/// patterns of JSON-like data.
///
/// The `Shape` system is not bound to any particular programming language, so
/// it does not inherit a data model that it must represent and defend, yet it
/// must adopt/assume _some_ concrete data model, since a type system without a
/// data model to enforce is as useful as a straitjacket on a coat rack. JSON
/// was chosen for its relative simplicity, its ubiquity as a data interchange
/// format used across programming languages, and because JSON is often used in
/// scenarios without a static type system to help catch errors before runtime.
///
/// The `Shape` system has no source syntax for denoting shapes directly, but
/// you can use the `Shape::*` helper functions to create shapes
/// programmatically, in Rust. `Shape::pretty_print()` provides a human-readable
/// representation of a `Shape` for debugging and testing purposes.
///
/// All in all, this _Static `Shape` System_ (SSS) supports the following
/// type-theoretic features:
///
/// - [x] Primitive shapes: `Bool`, `String`, `Int`, `Float`, `Null`
/// - [x] Singleton primitive shapes: `true`, `false`, `"hello"`, `42`, `null`
/// - [x] `Array` shapes, supporting both static tuples and dynamic lists
/// - [x] `Object` shapes, supporting both static fields and dynamic string keys
/// - [x] `One<S1, S2, ...>` union shapes, representing a set of shape
///   alternatives
/// - [x] `All<S1, S2, ...>` intersection shapes, representing a set
///   simultaneous requirements
/// - [x] `shape.field(name)` and `shape.item(index)` methods for accessing the
///   shape of a subproperty of a shape
/// - [x] `Name` shape references, with support for symbolic subproperty shape
///   access
/// - [x] `Error` shapes, representing a failure of shape processing, with
///   support for chains of errors and partial shape data
/// - [x] `None` shapes, representing the absence of a value (helpful for
///   representing optionality of shapes)
/// - [x] `subshape.satisfies(supershape)` and `supershape.accepts(subshape)`
///   methods for testing shape relationships
/// - [x] `shape.accepts_json(json)` method for testing whether concrete JSON
///   data satisfies some expected shape
/// - [x] `shape.pretty_print()` method for debugging and testing

#[derive(Clone, Eq)]
// [`Shape`] enforces the simplification of [`ShapeCase`] variants, because
// there is no way to create a [`Shape`] without simplifying the input
// [`ShapeCase`]. This is a very useful invariant because it allows each
// [`ShapeCase`] to assume its immediate [`Shape`] children have already been
// simplified.
//
// In addition simplification, [`Shape`] supports testing shape-shape acceptance
// (or the equivalent inverse, satisfaction) with `super.accepts(sub)` and/or
// `sub.satisfies(super)`. See also `shape.accepts_json(json)` for testing
// whether concrete JSON data satisfies some expected `shape`.
//
// In the future, we may internalize/canonize shapes to reduce memory usage,
// especially for well-known shapes like `Bool` and `Int` and `String`. This
// would require either thread safety (is `type Ref<T> = std::sync::Arc<T>`
// enough?) or maintaining per-thread canonical shape tables.
pub struct Shape {
    // This field is private, but if you want to match against an immutable
    // reference to the `ShapeCase` variant, use `match shape.case() { ... }`.
    case: Ref<ShapeCase>,

    /// The combination of locations which, combined, produce this shape.
    ///
    /// Many cases will only have a single location, but when shapes are
    /// simplified, their locations are all retained in the result.
    ///
    /// Currently [`ShapeMeta::Loc(Location)`] is the only variant here, but we
    /// can add other kinds of metadata in the future.
    meta: Ref<ShapeMeta>,
}

impl PartialEq for Shape {
    fn eq(&self, other: &Self) -> bool {
        self.case == other.case
    }
}

impl Hash for Shape {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Since the PartialEq implementation ignores self.locations, so must
        // the Hash implementation.
        self.case.hash(state);
    }
}

impl Shape {
    /// Create a `Shape` from a [`ShapeCase`] variant.
    ///
    /// This method is crate-private to help enforce some invariants.
    pub(crate) fn new(case: ShapeCase, locations: impl IntoIterator<Item = Location>) -> Shape {
        let meta = ShapeMeta::new(&case, locations, []);
        Shape {
            case: Ref::new(case),
            meta: Ref::new(meta),
        }
    }

    /// When boolean helper methods like `.is_none()` and `.is_null()` are not
    /// enough, you can match against the underlying [`ShapeCase`] by obtaining an
    /// immutable `&ShapeCase` reference using the `shape.case()` method.
    #[must_use]
    pub fn case(&self) -> &ShapeCase {
        self.case.as_ref()
    }

    /// Returns an iterator over all [`Location`]s associated with this shape.
    pub fn locations(&self) -> impl Iterator<Item = &Location> {
        let self_locs = self.meta.locations();

        let unique_locs: IndexSet<&Location> = match self.case() {
            ShapeCase::One(shapes) => self_locs
                .chain(shapes.iter().flat_map(|s| s.meta.locations()))
                .collect(),
            ShapeCase::All(shapes) => self_locs
                .chain(shapes.iter().flat_map(|s| s.meta.locations()))
                .collect(),
            _ => self_locs.collect(),
        };

        unique_locs.into_iter()
    }

    /// Returns an iterator over all [`Name`]s associated with this shape.
    pub fn names(&self) -> impl Iterator<Item = &Name> {
        self.meta.names()
    }

    pub fn nested_base_names(&self) -> impl Iterator<Item = &str> {
        self.meta.nested_base_names()
    }

    /// Returns a [`Shape`] that accepts any boolean value, `true` or `false`.
    #[must_use]
    pub fn bool(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Bool(None), locations)
    }

    /// Returns a [`Shape`] that accepts only the specified boolean value.
    #[must_use]
    pub fn bool_value(value: bool, locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Bool(Some(value)), locations)
    }

    /// Returns a [`Shape`] that accepts any string value.
    #[must_use]
    pub fn string(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::String(None), locations)
    }

    /// Returns a [`Shape`] that accepts only the specified string value.
    #[must_use]
    pub fn string_value(value: &str, locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::String(Some(value.to_string())), locations)
    }

    /// Returns a [`Shape`] that accepts any integer value.
    #[must_use]
    pub fn int(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Int(None), locations)
    }

    /// Returns a [`Shape`] that accepts only the specified integer value.
    #[must_use]
    pub fn int_value(value: i64, locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Int(Some(value)), locations)
    }

    /// Returns a [`Shape`] that accepts any floating point value.
    #[must_use]
    pub fn float(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Float, locations)
    }

    /// Returns a [`Shape`] that accepts only the JSON `null` value.
    #[must_use]
    pub fn null(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Null, locations)
    }

    #[must_use]
    pub fn is_null(&self) -> bool {
        self.case.is_null()
    }

    /// Returns a symbolic reference to a named shape, potentially not yet
    /// defined.
    ///
    /// In order to add items to the subpath of this named shape, call the
    /// `.field(name)` and/or `.item(index)` methods.
    ///
    /// Note that variable shapes are represented by [`ShapeCase::Name`] where the
    /// name string includes the initial `$` character.
    #[must_use]
    pub fn name(name: &str, locations: impl IntoIterator<Item = Location>) -> Self {
        let locations = locations.into_iter().collect::<Vec<_>>();
        Self::new(
            ShapeCase::Name(
                name::Name::base(name.to_string(), locations.clone()),
                WeakScope::none(),
            ),
            locations.clone(),
        )
    }

    /// Useful for obtaining the kind of [`IndexMap`] this library uses for the
    /// [`ShapeCase::Object`] variant.
    #[must_use]
    pub fn empty_map() -> IndexMap<String, Self> {
        IndexMap::new()
    }

    /// Returns a [`Shape`] that accepts any object shape, regardless of the other
    /// shape's `fields` or `rest` shape, because an empty object shape `{}`
    /// imposes no expectations on other objects (except that they are objects).
    ///
    /// In the other direction, an empty object shape `{}` can satisfy itself or
    /// any `Dict<V>` shape (where the `Dict` may be dynamically empty), but
    /// cannot satisfy any object shape with non-empty `fields`.
    #[must_use]
    pub fn empty_object(locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::new(
            ShapeCase::Object {
                fields: Shape::empty_map(),
                rest: Shape::none(),
            },
            locations,
        )
    }

    /// To get a compatible empty mutable [`IndexMap`] without directly
    /// depending on the [`indexmap`] crate yourself, use [`Shape::empty_map()`].
    #[must_use]
    pub fn object(
        fields: IndexMap<String, Shape>,
        rest: Shape,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::new(ShapeCase::Object { fields, rest }, locations)
    }

    /// Returns a [`Shape`] that accepts any object shape with the given static
    /// fields, with no dynamic fields considered.
    #[must_use]
    pub fn record(
        fields: IndexMap<String, Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::object(fields, Shape::none(), locations)
    }

    /// Returns a [`Shape`] that accepts any dictionary-like object with dynamic
    /// string properties having a given value shape.
    #[must_use]
    pub fn dict(value_shape: Shape, locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::object(Shape::empty_map(), value_shape, locations)
    }

    /// Arrays, tuples, and lists are all manifestations of the same underlying
    /// [`ShapeCase::Array`] representation.
    pub fn array(
        prefix: impl IntoIterator<Item = Shape>,
        tail: Shape,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        let prefix = prefix.into_iter().collect();
        Self::new(ShapeCase::Array { prefix, tail }, locations)
    }

    /// A tuple is a [`ShapeCase::Array`] with statically known (though possibly
    /// empty) element shapes and no dynamic tail shape.
    pub fn tuple(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::array(shapes, Shape::none(), locations)
    }

    /// A `List<S>` is a [`ShapeCase::Array`] with an empty static `prefix` and a
    /// dynamic element shape `S`.
    #[must_use]
    pub fn list(of: Shape, locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::array(empty(), of, locations)
    }

    /// Returns a [`ShapeCase::One`] union of the given shapes, simplified.
    ///
    /// Note that `locations` in this case should _not_ refer to each individual inner shape, but
    /// to the thing that caused all of these shapes to be combined, like maybe a `->match`. If
    /// there is no obvious cause to point users to, then the location should be empty.
    pub fn one(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        one(shapes.into_iter(), locations.into_iter().collect())
    }

    /// Returns a [`ShapeCase::All`] intersection of the given shapes, simplified.
    ///
    /// Note that `locations` in this case should _not_ refer to each individual inner shape, but
    /// to the thing that caused all of these shapes to be combined, like maybe a `IntfA & IntfB`.
    /// If there is no obvious cause to point users to, then the location should be empty.
    pub fn all(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        all(shapes.into_iter(), locations.into_iter().collect())
    }

    /// Returns a shape that accepts any JSON value (including [`ShapeCase::None`]
    /// and [`ShapeCase::Unknown`]), and is not accepted by any shape other than itself.
    #[must_use]
    pub fn unknown(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Unknown, locations)
    }

    #[must_use]
    pub fn is_unknown(&self) -> bool {
        matches!(self.case(), ShapeCase::Unknown)
    }

    /// Returns a shape representing the absence of a JSON value, which is
    /// satisfied/accepted only by itself.
    ///
    /// Because this represents the absence of a value, it shouldn't have a location. Basically,
    /// nothing can produce none alone, and if it were a union, that union would have its own
    /// location.
    #[must_use]
    pub fn none() -> Self {
        Self::new(ShapeCase::None, [])
    }

    #[must_use]
    pub fn is_none(&self) -> bool {
        self.case.is_none()
    }

    /// Report a failure of shape processing.
    #[must_use]
    pub fn error(
        message: impl Into<String>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Self::new(ShapeCase::error(message.into()), locations)
    }

    #[must_use]
    pub fn is_error(&self) -> bool {
        matches!(self.case(), ShapeCase::Error { .. })
    }

    /// Iterate over all errors within this shape, recursively
    pub fn errors(&self) -> impl Iterator<Item = &Error> {
        self.case.errors()
    }

    /// Report a failure of shape processing associated with a
    /// partial/best-guess shape that may still be useful.
    #[must_use]
    pub fn error_with_partial(
        message: impl Into<String>,
        partial: Shape,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Self::new(
            ShapeCase::error_with_partial(message.into(), partial),
            locations,
        )
    }

    /// Clone the shape, adding the provided `locations` to the existing locations.
    #[must_use]
    pub fn with_locations<'a>(mut self, locations: impl IntoIterator<Item = &'a Location>) -> Self {
        for loc in locations {
            if !self.meta.has_location(loc) {
                Ref::make_mut(&mut self.meta).add_location(loc);
            }
        }
        self
    }
}

#[cfg(test)]
mod test_errors {
    use super::*;

    #[test]
    fn multiple_errors_in_array() {
        let shape = Shape::tuple(
            [
                Shape::int([]),
                Shape::error("Expected a string", []),
                Shape::bool([]),
                Shape::error("Expected a null", []),
            ],
            [],
        );
        let errors: Vec<_> = shape.errors().collect();
        assert_eq!(errors.len(), 2);
        assert_eq!(errors[0].message, "Expected a string");
        assert_eq!(errors[1].message, "Expected a null");
    }

    #[test]
    fn nested_errors() {
        let shape = Shape::record(
            [
                ("a".to_string(), Shape::int([])),
                ("b".to_string(), Shape::error("Expected a string", [])),
                ("c".to_string(), Shape::bool([])),
                (
                    "d".to_string(),
                    Shape::record(
                        [
                            ("e".to_string(), Shape::error("Expected a null", [])),
                            ("f".to_string(), Shape::float([])),
                        ]
                        .into_iter()
                        .collect(),
                        [],
                    ),
                ),
            ]
            .into_iter()
            .collect(),
            [],
        );

        let errors: Vec<_> = shape.errors().collect();
        assert_eq!(errors.len(), 2);
        assert_eq!(errors[0].message, "Expected a string");
        assert_eq!(errors[1].message, "Expected a null");
    }
}