didbot_schema/

lib.rs

//! Lexicon schemas, as a typed tree a record can be checked against, and the
//! identifiers and string formats the check reads.
//!
//! `didbot-lexicon` embeds the documents and checks that they are well
//! formed. Validating a *record* also needs the identifier validators — DIDs,
//! handles, TIDs, record keys, `at://` URIs — so the schema model lives here,
//! beside them. It builds for `wasm32-unknown-unknown`, so a browser checks a
//! record with the same code the store runs; [`validate_with`] is the whole
//! of what a write's shape must satisfy.
//!
//! # What this covers
//!
//! The Lexicon specification's type system: object, array, string, integer,
//! boolean, bytes, cid-link, blob, unknown, ref, union, and every constraint
//! those carry. [`Method`] and [`MethodOutput`] carry a query's or
//! procedure's own parameters, input and output on top of that, so
//! [`Catalog::validate_input`] and [`Catalog::validate_output`] check an
//! XRPC body the same way [`validate_with`] checks a record.
//!
//! # Unrecognised things are carried, not refused
//!
//! Two rules, both from the specification, both about forward compatibility,
//! and both easy to get backwards. An object property no schema declares is
//! **preserved** rather than rejected — a client written against a newer
//! version of a lexicon must be able to write through an older server without
//! silently losing fields. And a `type` this build has never heard of parses
//! to [`Schema::Unrecognised`] and accepts anything, for the same reason
//! [`crate::format::StringFormat::parse`] shrugs at an unknown format: the
//! Lexicon language grows, and a server that treated growth as corruption
//! would break on a schema change it did not author.
//!
//! `knownValues` is likewise advisory and never enforced. It is the
//! specification's way of writing down an *open* set — the exact opposite of
//! `enum`, which is closed and is enforced.

#![forbid(unsafe_code)]

pub mod aturi;
pub mod format;
pub mod record_key;
pub mod tid;

mod check;
mod shape;

pub use aturi::{AtUri, AtUriError};
pub use check::{InvalidRecord, MAX_SCHEMA_DEPTH};
pub use record_key::{validate_record_key, RecordKeyError, MAX_RECORD_KEY_LENGTH};
pub use shape::{
    schema_is_held, validate_collection, validate_shape, validate_with, ShapeError, Stance,
};

use std::collections::{BTreeMap, BTreeSet};

use serde_json::Value;

use crate::format::StringFormat;

/// Why a lexicon document could not be turned into a schema tree.
///
/// Every one of these is a defect in a lexicon document rather than in a
/// record. For the documents this project embeds it is a build-time bug, and
/// the unit tests in this module are what catch it.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum SchemaError {
    /// A definition or property was not a JSON object.
    #[error("{path}: schema is not an object")]
    NotAnObject {
        /// Where in the document it sits.
        path: String,
    },
    /// A schema had no `type`.
    #[error("{path}: schema has no `type`")]
    NoType {
        /// Where in the document it sits.
        path: String,
    },
    /// A keyword held the wrong kind of JSON value.
    #[error("{path}: `{keyword}` is not {expected}")]
    BadKeyword {
        /// Where in the document it sits.
        path: String,
        /// The keyword that was wrong.
        keyword: &'static str,
        /// What it should have been.
        expected: &'static str,
    },
    /// A record definition had no `record` object.
    #[error("{path}: record definition has no `record` schema")]
    RecordWithoutSchema {
        /// Where in the document it sits.
        path: String,
    },
    /// A `type` that is only a field type appeared in definition position.
    ///
    /// `unknown` and `ref` describe a *slot inside* a schema: "whatever the
    /// writer put here" and "look over there". Neither says anything a
    /// document could define, so upstream refuses both under `defs`.
    #[error("{path}: `{kind}` is a field type and cannot be a definition")]
    NotADefinition {
        /// Where in the document it sits.
        path: String,
        /// The `type` as written.
        kind: &'static str,
    },
    /// A primary definition was named something other than `main`.
    ///
    /// Records and methods are addressed by the NSID of the document holding
    /// them, so a second one in the same document has no name to be reached
    /// by; the specification puts the primary under `main` and only `main`.
    #[error("{path}: a `{kind}` is a primary definition and must be named `main`")]
    PrimaryNotMain {
        /// Where in the document it sits.
        path: String,
        /// The `type` as written.
        kind: &'static str,
    },
}

/// A string schema and everything that constrains it.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct StringSchema {
    /// The only value permitted, if the schema names one.
    pub constant: Option<String>,
    /// The closed set of permitted values, if the schema names one.
    ///
    /// Distinct from `knownValues`, which is open and is not enforced.
    pub choices: Option<Vec<String>>,
    /// The declared format, if this build recognises it.
    pub format: Option<StringFormat>,
    /// The format name as written, kept even when unrecognised so that an
    /// error can name it.
    pub format_name: Option<String>,
    /// Minimum length in UTF-8 bytes.
    pub min_length: Option<usize>,
    /// Maximum length in UTF-8 bytes.
    pub max_length: Option<usize>,
    /// Minimum length in grapheme clusters.
    pub min_graphemes: Option<usize>,
    /// Maximum length in grapheme clusters.
    pub max_graphemes: Option<usize>,
}

/// An integer schema and everything that constrains it.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct IntegerSchema {
    /// The only value permitted, if the schema names one.
    pub constant: Option<i64>,
    /// The closed set of permitted values, if the schema names one.
    pub choices: Option<Vec<i64>>,
    /// Smallest permitted value, inclusive.
    pub minimum: Option<i64>,
    /// Largest permitted value, inclusive.
    pub maximum: Option<i64>,
}

/// An object schema: its properties and which of them are required or
/// nullable.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct ObjectSchema {
    /// Properties that must be present.
    pub required: BTreeSet<String>,
    /// Properties that may be present and null.
    pub nullable: BTreeSet<String>,
    /// The declared properties. Anything not named here is preserved.
    pub properties: BTreeMap<String, Schema>,
}

/// One schema node.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Schema {
    /// `boolean`, optionally pinned to one value.
    Boolean {
        /// The only value permitted, if the schema names one.
        constant: Option<bool>,
    },
    /// `integer`.
    Integer(IntegerSchema),
    /// `string`.
    String(StringSchema),
    /// `bytes`, whose length bounds are on the decoded byte count.
    Bytes {
        /// Smallest permitted decoded length, in bytes.
        min_length: Option<usize>,
        /// Largest permitted decoded length, in bytes.
        max_length: Option<usize>,
    },
    /// `cid-link`: `{"$link": "<cid>"}`.
    CidLink,
    /// `blob`.
    Blob {
        /// MIME patterns the blob's type must match, if the schema names any.
        accept: Vec<String>,
        /// Largest permitted `size`, in bytes.
        max_size: Option<u64>,
    },
    /// `array`.
    Array {
        /// The element schema, if the document gave one.
        items: Option<Box<Schema>>,
        /// Fewest permitted elements.
        min_length: Option<usize>,
        /// Most permitted elements.
        max_length: Option<usize>,
    },
    /// `object`.
    Object(ObjectSchema),
    /// `ref`: a pointer at another definition, resolved at check time.
    Ref(String),
    /// `union`: one of several referenced definitions, chosen by `$type`.
    Union {
        /// The definitions this union admits.
        refs: Vec<String>,
        /// Whether a `$type` outside `refs` is refused. Open unions accept
        /// one, which is how a consumer survives a variant added later.
        closed: bool,
    },
    /// `unknown`: any object, but an object.
    Unknown,
    /// `null`.
    Null,
    /// `token`: as a field type, a placeholder that carries no data.
    Token,
    /// A `type` this build does not know, which accepts anything.
    Unrecognised(String),
}

/// One definition in a document.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Def {
    /// A `record`: a key strategy and the object schema of its body.
    Record {
        /// The record key strategy, as written.
        key: String,
        /// The record body's schema.
        record: Schema,
    },
    /// A `token`: a bare identifier with no data.
    Token,
    /// Any other definition usable as data — an object, a string, an array.
    Data(Schema),
    /// A `query`, `procedure`, `subscription` or `permission-set`.
    ///
    /// Kept rather than dropped for two reasons. A ref pointing at one is
    /// reported as pointing at something that is not data, instead of as a
    /// dangling ref. And the schemas a method declares are what the
    /// conformance harness checks this server's own HTTP against: an XRPC
    /// response is a JSON value with a schema, and the schema is in the
    /// document rather than in anything written here.
    Method(Box<Method>),
}

/// A `query`, `procedure`, `subscription` or `permission-set` definition.
///
/// Everything a method declares that is a *schema*, and nothing else. The
/// encoding strings are not kept: a method whose output is `application/cbor`
/// or `*/*` carries no schema and is [`Method::output`] `None`, which is the
/// only thing a caller can act on.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Method {
    /// The definition's `type`, as written.
    pub kind: String,
    /// The `parameters` object, when the method declares one.
    ///
    /// Query parameters arrive as strings and are coerced by whatever parsed
    /// the request, so this is here to be read rather than to check a request
    /// body against.
    pub parameters: Option<Schema>,
    /// The schema of a JSON request body, when the method takes one.
    pub input: Option<Schema>,
    /// The schema of a JSON response body, when the method returns one.
    pub output: Option<Schema>,
    /// The error names the method declares, in the order the document lists
    /// them.
    ///
    /// A client generates a typed class per name, so an error this server
    /// invents is one the client reports as an unknown failure rather than as
    /// the condition it is.
    pub errors: Vec<String>,
}

/// A set of lexicon documents that can resolve refs between themselves.
#[derive(Debug, Clone, Default)]
pub struct Catalog {
    documents: BTreeMap<String, BTreeMap<String, Def>>,
}

impl Catalog {
    /// An empty catalog.
    pub fn new() -> Self {
        Self::default()
    }

    /// Adds one parsed lexicon document.
    pub fn insert(&mut self, doc: &didbot_lexicon::lexicon::LexiconDoc) -> Result<(), SchemaError> {
        let mut defs = BTreeMap::new();
        for (name, body) in &doc.defs {
            defs.insert(
                name.clone(),
                parse_def(&format!("{}#{name}", doc.id), name, body)?,
            );
        }
        self.documents.insert(doc.id.clone(), defs);
        Ok(())
    }

    /// Builds a catalog from parsed documents.
    pub fn from_documents<'a>(
        docs: impl IntoIterator<Item = &'a didbot_lexicon::lexicon::LexiconDoc>,
    ) -> Result<Self, SchemaError> {
        let mut catalog = Self::new();
        for doc in docs {
            catalog.insert(doc)?;
        }
        Ok(catalog)
    }

    /// The catalog of the documents this deployment embeds.
    ///
    /// Built once and shared. Failure is a defect in a document this binary
    /// was compiled from, so it is reported as an empty catalog rather than
    /// panicking at an arbitrary first write; the unit tests in this module
    /// and in `didbot-lexicon` are what actually catch it.
    pub fn embedded() -> &'static Self {
        static EMBEDDED: std::sync::OnceLock<Catalog> = std::sync::OnceLock::new();
        EMBEDDED.get_or_init(|| {
            let docs = match didbot_lexicon::lexicon::load_all() {
                Ok(docs) => docs,
                Err(error) => {
                    tracing::error!(%error, "embedded lexicons did not parse");
                    return Catalog::new();
                }
            };
            Catalog::from_documents(&docs).unwrap_or_else(|error| {
                tracing::error!(%error, "embedded lexicons are not valid schemas");
                Catalog::new()
            })
        })
    }

    /// Whether this catalog holds a record definition for a collection.
    pub fn defines_record(&self, collection: &str) -> bool {
        matches!(self.lookup(collection, "main"), Some(Def::Record { .. }))
    }

    /// The record key strategy a collection's `main` definition declares.
    ///
    /// `None` when this catalog has no record definition for the collection.
    /// The string is returned exactly as the document wrote it, because
    /// deciding which strategies are supported belongs to the store that has
    /// to honour them; see `didbot-pds`'s `records::resolve_key`.
    pub fn record_key(&self, collection: &str) -> Option<&str> {
        match self.lookup(collection, "main") {
            Some(Def::Record { key, .. }) => Some(key.as_str()),
            _ => None,
        }
    }

    /// One definition, by document id and definition name.
    pub fn lookup(&self, document: &str, name: &str) -> Option<&Def> {
        self.documents.get(document)?.get(name)
    }

    /// Resolves a `ref` string written inside `from`.
    ///
    /// Three forms, all of them in the specification: `#name` is local to the
    /// document doing the referring, `nsid#name` names a definition in
    /// another, and a bare `nsid` names that document's `main`.
    pub fn resolve(&self, from: &str, reference: &str) -> Option<(String, &Def)> {
        let (document, name) = split_ref(from, reference);
        let def = self.lookup(&document, &name)?;
        Some((format!("{document}#{name}"), def))
    }

    /// Every collection this catalog defines a record for.
    pub fn record_collections(&self) -> Vec<&str> {
        self.documents
            .iter()
            .filter(|(_, defs)| matches!(defs.get("main"), Some(Def::Record { .. })))
            .map(|(id, _)| id.as_str())
            .collect()
    }

    /// One method definition, by NSID.
    ///
    /// `None` when this catalog holds no such document, or when the
    /// document's `main` is a record rather than a method.
    pub fn method(&self, nsid: &str) -> Option<&Method> {
        match self.lookup(nsid, "main") {
            Some(Def::Method(method)) => Some(method),
            _ => None,
        }
    }

    /// Checks a JSON response body against the output schema `nsid` declares.
    ///
    /// The whole reason this exists: a response is a value with a schema, the
    /// schema is written down in a document somebody else maintains, and a
    /// server that checks its own output against a struct it wrote from
    /// reading that document is checking its reading rather than the
    /// document.
    ///
    /// [`MethodOutput::Unchecked`] is not a pass. It says the document
    /// declares no JSON schema for this method's response — a CAR file, a
    /// blob — and a caller that wants coverage has to say what it checks
    /// instead.
    pub fn validate_output(&self, nsid: &str, body: &Value) -> MethodOutput {
        let Some(method) = self.method(nsid) else {
            return MethodOutput::NoSuchMethod;
        };
        let Some(schema) = &method.output else {
            return MethodOutput::Unchecked;
        };
        match check::check(self, nsid, schema, body) {
            Ok(()) => MethodOutput::Valid,
            Err(error) => MethodOutput::Invalid(error),
        }
    }

    /// Checks a JSON request body against the input schema `nsid` declares.
    ///
    /// The other direction, and it is worth checking too: a request this
    /// server's own tests compose is one a client would have to be able to
    /// compose, so a fixture that quietly stopped satisfying the document
    /// would make every response checked against it prove nothing.
    pub fn validate_input(&self, nsid: &str, body: &Value) -> MethodOutput {
        let Some(method) = self.method(nsid) else {
            return MethodOutput::NoSuchMethod;
        };
        let Some(schema) = &method.input else {
            return MethodOutput::Unchecked;
        };
        match check::check(self, nsid, schema, body) {
            Ok(()) => MethodOutput::Valid,
            Err(error) => MethodOutput::Invalid(error),
        }
    }

    /// Checks a record against the collection's `main` record definition.
    ///
    /// The collection must be one this catalog defines; see
    /// [`validate_with`], which is what decides that a record arriving over
    /// the wire has a schema at all.
    pub fn validate_record(&self, collection: &str, record: &Value) -> Result<(), InvalidRecord> {
        let Some(Def::Record { record: schema, .. }) = self.lookup(collection, "main") else {
            return Err(InvalidRecord::no_such_record(collection));
        };
        check::check(self, collection, schema, record)
    }
}

/// What checking a body against a method's declared schema found.
///
/// Four outcomes rather than a `Result`, because two of the failures are
/// about the *catalog* rather than about the body: a method nobody vendored
/// and a method that declares no schema are both silence, and silence that
/// reads as success is how a conformance suite stops conforming.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MethodOutput {
    /// The body satisfies the schema.
    Valid,
    /// The body does not.
    Invalid(InvalidRecord),
    /// The catalog holds no method by that name.
    NoSuchMethod,
    /// The method declares no JSON schema for this body.
    Unchecked,
}

impl MethodOutput {
    /// Panics unless the body was checked and satisfied its schema.
    ///
    /// For a test that means to assert conformance: it fails on a body that
    /// is wrong *and* on one that was never checked, which is the outcome a
    /// bare boolean would hide.
    #[track_caller]
    pub fn expect_valid(self, what: &str) {
        match self {
            Self::Valid => {}
            Self::Invalid(error) => panic!("{what} does not satisfy its lexicon: {error}"),
            Self::NoSuchMethod => {
                panic!("{what}: no such method in this catalog — is the document vendored?")
            }
            Self::Unchecked => {
                panic!(
                    "{what}: the document declares no schema for this body, so nothing was checked"
                )
            }
        }
    }
}

/// Splits a `ref` into the document it names and the definition inside it.
fn split_ref(from: &str, reference: &str) -> (String, String) {
    match reference.split_once('#') {
        Some(("", name)) => (from.to_owned(), name.to_owned()),
        Some((document, name)) => (document.to_owned(), name.to_owned()),
        None => (reference.to_owned(), "main".to_owned()),
    }
}

/// Types that may only appear under `defs` as `main`.
const PRIMARY_TYPES: &[&str] = &[
    "record",
    "query",
    "procedure",
    "subscription",
    "permission-set",
];

/// Types that are field types only, and are not definitions.
const FIELD_ONLY_TYPES: &[&str] = &["unknown", "ref"];

/// Parses one definition.
///
/// `name` is the key it sits under in `defs`, which is what decides whether a
/// primary definition is in a legal position; `path` is the same thing
/// rendered for error messages.
fn parse_def(path: &str, name: &str, body: &Value) -> Result<Def, SchemaError> {
    let object = body.as_object().ok_or_else(|| SchemaError::NotAnObject {
        path: path.to_owned(),
    })?;
    let kind = object
        .get("type")
        .and_then(Value::as_str)
        .ok_or_else(|| SchemaError::NoType {
            path: path.to_owned(),
        })?;
    if let Some(kind) = FIELD_ONLY_TYPES.iter().find(|field| **field == kind) {
        return Err(SchemaError::NotADefinition {
            path: path.to_owned(),
            kind,
        });
    }
    if name != "main" {
        if let Some(kind) = PRIMARY_TYPES.iter().find(|primary| **primary == kind) {
            return Err(SchemaError::PrimaryNotMain {
                path: path.to_owned(),
                kind,
            });
        }
    }
    match kind {
        "record" => {
            let record = object
                .get("record")
                .ok_or_else(|| SchemaError::RecordWithoutSchema {
                    path: path.to_owned(),
                })?;
            Ok(Def::Record {
                key: object
                    .get("key")
                    .and_then(Value::as_str)
                    .unwrap_or("tid")
                    .to_owned(),
                record: parse_schema(&format!("{path}.record"), record)?,
            })
        }
        "token" => Ok(Def::Token),
        "query" | "procedure" | "subscription" | "permission-set" => {
            Ok(Def::Method(Box::new(parse_method(path, kind, object)?)))
        }
        _ => Ok(Def::Data(parse_schema(path, body)?)),
    }
}

/// Parses a method definition's schemas.
///
/// `parameters` is a schema in its own right; `input` and `output` are
/// wrappers carrying an `encoding` and an optional `schema`. A body with an
/// encoding and no schema — `com.atproto.sync.getRepo` returns a CAR file —
/// is `None` rather than an error, because there is nothing to check and that
/// is the document saying so.
fn parse_method(
    path: &str,
    kind: &str,
    object: &serde_json::Map<String, Value>,
) -> Result<Method, SchemaError> {
    let body = |keyword: &'static str| -> Result<Option<Schema>, SchemaError> {
        let Some(wrapper) = object.get(keyword) else {
            return Ok(None);
        };
        let wrapper = wrapper.as_object().ok_or_else(|| SchemaError::BadKeyword {
            path: path.to_owned(),
            keyword,
            expected: "an object",
        })?;
        match wrapper.get("schema") {
            None | Some(Value::Null) => Ok(None),
            Some(schema) => Ok(Some(parse_schema(&format!("{path}.{keyword}"), schema)?)),
        }
    };
    let parameters = match object.get("parameters") {
        None | Some(Value::Null) => None,
        Some(parameters) => Some(parse_schema(&format!("{path}.parameters"), parameters)?),
    };
    let errors = object
        .get("errors")
        .and_then(Value::as_array)
        .map(|declared| {
            declared
                .iter()
                .filter_map(|error| error.get("name").and_then(Value::as_str))
                .map(str::to_owned)
                .collect()
        })
        .unwrap_or_default();
    Ok(Method {
        kind: kind.to_owned(),
        parameters,
        input: body("input")?,
        output: body("output")?,
        errors,
    })
}

/// Reads a keyword as a non-negative size.
fn size(
    path: &str,
    object: &serde_json::Map<String, Value>,
    keyword: &'static str,
) -> Result<Option<usize>, SchemaError> {
    match object.get(keyword) {
        None | Some(Value::Null) => Ok(None),
        Some(value) => value
            .as_u64()
            .and_then(|n| usize::try_from(n).ok())
            .map(Some)
            .ok_or(SchemaError::BadKeyword {
                path: path.to_owned(),
                keyword,
                expected: "a non-negative integer",
            }),
    }
}

/// Reads a keyword as a signed integer.
fn integer(
    path: &str,
    object: &serde_json::Map<String, Value>,
    keyword: &'static str,
) -> Result<Option<i64>, SchemaError> {
    match object.get(keyword) {
        None | Some(Value::Null) => Ok(None),
        Some(value) => value.as_i64().map(Some).ok_or(SchemaError::BadKeyword {
            path: path.to_owned(),
            keyword,
            expected: "an integer",
        }),
    }
}

/// Reads a keyword as a list of strings.
fn strings(
    path: &str,
    object: &serde_json::Map<String, Value>,
    keyword: &'static str,
) -> Result<Option<Vec<String>>, SchemaError> {
    let Some(value) = object.get(keyword) else {
        return Ok(None);
    };
    let items = value.as_array().ok_or(SchemaError::BadKeyword {
        path: path.to_owned(),
        keyword,
        expected: "an array",
    })?;
    items
        .iter()
        .map(|item| {
            item.as_str()
                .map(str::to_owned)
                .ok_or(SchemaError::BadKeyword {
                    path: path.to_owned(),
                    keyword,
                    expected: "an array of strings",
                })
        })
        .collect::<Result<Vec<_>, _>>()
        .map(Some)
}

/// Parses one schema node.
fn parse_schema(path: &str, body: &Value) -> Result<Schema, SchemaError> {
    let object = body.as_object().ok_or_else(|| SchemaError::NotAnObject {
        path: path.to_owned(),
    })?;
    let kind = object
        .get("type")
        .and_then(Value::as_str)
        .ok_or_else(|| SchemaError::NoType {
            path: path.to_owned(),
        })?;

    Ok(match kind {
        "boolean" => Schema::Boolean {
            constant: object.get("const").and_then(Value::as_bool),
        },
        "integer" => Schema::Integer(IntegerSchema {
            constant: integer(path, object, "const")?,
            choices: match object.get("enum") {
                None => None,
                Some(value) => Some(
                    value
                        .as_array()
                        .ok_or(SchemaError::BadKeyword {
                            path: path.to_owned(),
                            keyword: "enum",
                            expected: "an array",
                        })?
                        .iter()
                        .map(|item| {
                            item.as_i64().ok_or(SchemaError::BadKeyword {
                                path: path.to_owned(),
                                keyword: "enum",
                                expected: "an array of integers",
                            })
                        })
                        .collect::<Result<Vec<_>, _>>()?,
                ),
            },
            minimum: integer(path, object, "minimum")?,
            maximum: integer(path, object, "maximum")?,
        }),
        "string" => {
            let format_name = object
                .get("format")
                .and_then(Value::as_str)
                .map(str::to_owned);
            Schema::String(StringSchema {
                constant: object
                    .get("const")
                    .and_then(Value::as_str)
                    .map(str::to_owned),
                choices: strings(path, object, "enum")?,
                format: format_name.as_deref().and_then(StringFormat::parse),
                format_name,
                min_length: size(path, object, "minLength")?,
                max_length: size(path, object, "maxLength")?,
                min_graphemes: size(path, object, "minGraphemes")?,
                max_graphemes: size(path, object, "maxGraphemes")?,
            })
        }
        "bytes" => Schema::Bytes {
            min_length: size(path, object, "minLength")?,
            max_length: size(path, object, "maxLength")?,
        },
        "cid-link" => Schema::CidLink,
        "blob" => Schema::Blob {
            accept: strings(path, object, "accept")?.unwrap_or_default(),
            max_size: size(path, object, "maxSize")?.map(|n| n as u64),
        },
        "array" => Schema::Array {
            items: match object.get("items") {
                None => None,
                Some(items) => Some(Box::new(parse_schema(&format!("{path}.items"), items)?)),
            },
            min_length: size(path, object, "minLength")?,
            max_length: size(path, object, "maxLength")?,
        },
        "object" => Schema::Object(parse_object(path, object)?),
        "params" => Schema::Object(parse_object(path, object)?),
        "ref" => Schema::Ref(
            object
                .get("ref")
                .and_then(Value::as_str)
                .ok_or(SchemaError::BadKeyword {
                    path: path.to_owned(),
                    keyword: "ref",
                    expected: "a string",
                })?
                .to_owned(),
        ),
        "union" => Schema::Union {
            refs: strings(path, object, "refs")?.unwrap_or_default(),
            closed: object
                .get("closed")
                .and_then(Value::as_bool)
                .unwrap_or(false),
        },
        "unknown" => Schema::Unknown,
        "null" => Schema::Null,
        "token" => Schema::Token,
        other => Schema::Unrecognised(other.to_owned()),
    })
}

/// Parses the body of an object schema.
fn parse_object(
    path: &str,
    object: &serde_json::Map<String, Value>,
) -> Result<ObjectSchema, SchemaError> {
    let mut properties = BTreeMap::new();
    if let Some(declared) = object.get("properties") {
        let declared = declared.as_object().ok_or(SchemaError::BadKeyword {
            path: path.to_owned(),
            keyword: "properties",
            expected: "an object",
        })?;
        for (name, body) in declared {
            properties.insert(name.clone(), parse_schema(&format!("{path}.{name}"), body)?);
        }
    }
    Ok(ObjectSchema {
        required: strings(path, object, "required")?
            .unwrap_or_default()
            .into_iter()
            .collect(),
        nullable: strings(path, object, "nullable")?
            .unwrap_or_default()
            .into_iter()
            .collect(),
        properties,
    })
}

#[cfg(test)]
mod tests {
    /// A collection this deployment holds no schema for, used here as an
    /// ordinary record that is not one of its own.
    const THING: &str = "com.example.thing";

    use super::*;

    #[test]
    fn every_embedded_lexicon_becomes_a_schema() {
        let docs = didbot_lexicon::lexicon::load_all().expect("embedded lexicons parse");
        let catalog = Catalog::from_documents(&docs).expect("embedded lexicons are valid schemas");
        let mut collections = catalog.record_collections();
        collections.sort_unstable();
        let mut known = didbot_lexicon::nsid::ALL.to_vec();
        known.sort_unstable();
        assert_eq!(collections, known);
    }

    #[test]
    fn the_shared_catalog_is_not_empty() {
        // `embedded` degrades to an empty catalog rather than panicking, so
        // the assertion that it built is worth making once.
        assert!(Catalog::embedded().defines_record(didbot_lexicon::nsid::REGISTRATION));
    }

    #[test]
    fn a_collections_key_strategy_comes_off_its_record_definition() {
        let catalog = Catalog::embedded();
        assert_eq!(
            catalog.record_key(didbot_lexicon::nsid::REGISTRATION),
            Some("literal:self")
        );
        // A collection this deployment holds no document for has no strategy
        // here, whoever else defines one: the record is the ordinary case.
        assert_eq!(catalog.record_key(THING), None);
        assert_eq!(catalog.record_key("com.example.nothing"), None);
    }

    #[test]
    fn refs_resolve_in_all_three_written_forms() {
        let doc: didbot_lexicon::lexicon::LexiconDoc = serde_json::from_value(serde_json::json!({
            "lexicon": 1,
            "id": "com.example.thing",
            "defs": {
                "main": {"type": "record", "key": "tid", "record": {"type": "object"}},
                "side": {"type": "object"}
            }
        }))
        .expect("a hand-written document parses");
        let catalog = Catalog::from_documents(std::iter::once(&doc)).expect("valid");

        assert!(catalog.resolve("com.example.thing", "#side").is_some());
        assert!(catalog
            .resolve("com.example.other", "com.example.thing#side")
            .is_some());
        assert!(catalog
            .resolve("com.example.other", "com.example.thing")
            .is_some());
        assert!(catalog.resolve("com.example.thing", "#missing").is_none());
    }

    #[test]
    fn an_unrecognised_type_parses_rather_than_failing() {
        let schema = parse_schema("x", &serde_json::json!({"type": "hologram"}))
            .expect("an unknown type is not a parse failure");
        assert_eq!(schema, Schema::Unrecognised("hologram".to_owned()));
    }
}