Skip to main content

dsl_kit_parse/
import.rs

1//! Load/link phase: expands `$import` placeholders into a single
2//! fully-linked [`ParseTree`] before conformance and [`DslBuild`].
3//!
4//! ## Model
5//!
6//! Imports are resolved in a **separate load phase, not as a runtime
7//! effect**: the engine never sees an import, and the existing
8//! suspend/resume `Call` surface keeps meaning "domain effect", never
9//! "go read a file". The loader walks the import graph to a fixpoint
10//! and hands downstream consumers one linked tree — the same
11//! resolution-before-evaluation split Bazel's `load()` and Dhall's
12//! import judgment standardise.
13//!
14//! Three properties carry the design:
15//!
16//! - **Literal-only specifiers.** An import site names its source with
17//!   a literal string (`{"$import": "lib"}` in the JSON front-end), so
18//!   the full document graph is derivable by a pure syntactic pass —
19//!   [`Loaded::dependencies`] reports it without executing anything.
20//! - **The host owns all IO.** The loader itself never touches the
21//!   filesystem; every byte enters through a caller-supplied
22//!   [`SourceResolver`]. The kit ships [`MapResolver`] (named
23//!   in-memory sources) as the canonical sandboxed implementation;
24//!   a filesystem resolver is just another impl a host may write.
25//! - **Bounded expansion.** Cycles are detected with a `Pending`
26//!   sentinel in the source cache and reported as the full chain
27//!   (`<root> → a → b → a`); [`ImportLimits`] caps depth, source
28//!   count, and total fetched bytes so reference-expansion blowups
29//!   fail loudly instead of exhausting memory.
30//!
31//! ## Placeholder shape
32//!
33//! Front-ends represent an import site as a [`ParseTree`] whose
34//! variant is [`IMPORT_VARIANT`] (`"$import"`) carrying a single
35//! [`IMPORT_SPEC_FIELD`] (`"spec"`) payload. The JSON bridge produces
36//! it from `{"$import": "name"}` at any node position; the canonical
37//! text front-end spells the same placeholder `@import "name"` once
38//! [`add_import_syntax`] has been applied to the grammar. The loader
39//! replaces each placeholder with the parsed-and-expanded tree of the
40//! resolved source; placeholders never survive into conformance — a
41//! leftover one is a [`import_codes::UNEXPANDED`] diagnostic there.
42//!
43//! Sharing is by value: two sites importing the same source each
44//! receive a clone of the expanded tree. Node identity is minted later
45//! (by [`DslBuild`] via `IdGen`), so clones cannot collide.
46//!
47//! ## Front-ends and mixing
48//!
49//! A fetched source declares its front-end via [`ImportSource`]:
50//! `Json` parses through [`serde_bridge::from_json_str`], `Text`
51//! through the [`Loader`]'s configured [`Grammar`]. The two mix
52//! freely — a text root may import JSON sources and vice versa —
53//! because both land in the same [`ParseTree`] trunk before splicing.
54//! A `Text` source arriving at a [`Loader`] with no grammar is a
55//! loud [`import_codes::TEXT_UNSUPPORTED`] failure, not a fallback.
56//!
57//! One known limitation: [`ParseTree::span`]s inside an expanded tree
58//! are byte offsets **relative to the source that parsed that
59//! subtree**, and the tree does not record which source that is.
60//! Loader diagnostics carry the resolution chain instead; per-subtree
61//! source attribution is a planned follow-up.
62//!
63//! ## Example
64//!
65//! ```ignore
66//! use dsl_kit_parse::import::{ImportLimits, MapResolver, load_json_str};
67//!
68//! let mut resolver = MapResolver::new();
69//! resolver.insert("lib", r#"{ "type": "Leaf", "value": "shared" }"#);
70//! let root = r#"{ "type": "Seq", "items": [ { "$import": "lib" } ] }"#;
71//! let loaded = load_json_str(root, &Cfg::schema(), &mut resolver, &ImportLimits::default())?;
72//! assert_eq!(loaded.dependencies.len(), 1);
73//! ```
74//!
75//! [`DslBuild`]: crate::DslBuild
76
77use crate::peg::{self, Grammar, Peg};
78use crate::{BuildError, Diagnostic, ParseTree, RawValue, serde_bridge};
79use dsl_kit_core::IdGen;
80use dsl_kit_schema::NodeSchema;
81use serde_json::Value;
82use std::collections::BTreeMap;
83use std::fmt;
84
85/// Reserved [`ParseTree::variant`] spelling for an unexpanded import
86/// placeholder.
87///
88/// The `$` sigil cannot appear in a Rust enum variant name, so the
89/// spelling can never collide with a DSL author's variant.
90pub const IMPORT_VARIANT: &str = "$import";
91
92/// Field name on an [`IMPORT_VARIANT`] placeholder that carries the
93/// literal source specifier.
94pub const IMPORT_SPEC_FIELD: &str = "spec";
95
96/// Diagnostic codes emitted by the import loader (and the shared
97/// placeholder machinery in the front-ends / conformance).
98pub mod import_codes {
99    /// The import graph contains a cycle. The message renders the full
100    /// resolution chain (`<root> → a → b → a`).
101    pub const CYCLE: &str = "dsl_kit::parse::import::cycle";
102    /// Expansion exceeded [`ImportLimits::max_depth`](super::ImportLimits).
103    pub const DEPTH_EXCEEDED: &str = "dsl_kit::parse::import::depth_exceeded";
104    /// Expansion exceeded [`ImportLimits::max_sources`](super::ImportLimits).
105    pub const SOURCE_LIMIT: &str = "dsl_kit::parse::import::source_limit";
106    /// Expansion exceeded [`ImportLimits::max_total_bytes`](super::ImportLimits).
107    pub const BYTE_LIMIT: &str = "dsl_kit::parse::import::byte_limit";
108    /// [`SourceResolver::resolve`](super::SourceResolver::resolve)
109    /// returned an error for a specifier.
110    pub const RESOLVE_FAILED: &str = "dsl_kit::parse::import::resolve_failed";
111    /// [`SourceResolver::fetch`](super::SourceResolver::fetch) returned
112    /// an error for a resolved source id.
113    pub const FETCH_FAILED: &str = "dsl_kit::parse::import::fetch_failed";
114    /// An import placeholder is malformed: the `$import` value is not
115    /// a string, or the object carries keys besides `$import`, or a
116    /// hand-built placeholder tree lacks a usable
117    /// [`IMPORT_SPEC_FIELD`](super::IMPORT_SPEC_FIELD) payload.
118    pub const SPEC_SHAPE: &str = "dsl_kit::parse::import::spec_shape";
119    /// Context marker prepended to diagnostics that originate inside
120    /// an imported source, naming the source and the resolution chain.
121    pub const IN_IMPORT: &str = "dsl_kit::parse::import::in_import";
122    /// An [`IMPORT_VARIANT`](super::IMPORT_VARIANT) placeholder
123    /// reached [`check_conformance`](crate::check_conformance) —
124    /// the document was not run through the loader.
125    pub const UNEXPANDED: &str = "dsl_kit::parse::import::unexpanded";
126    /// A [`ImportSource::Text`](super::ImportSource::Text) source was
127    /// fetched (or a text root was loaded) but the [`Loader`](super::Loader)
128    /// has no [`Grammar`](crate::peg::Grammar) configured — call
129    /// [`Loader::with_grammar`](super::Loader::with_grammar).
130    pub const TEXT_UNSUPPORTED: &str = "dsl_kit::parse::import::text_unsupported";
131    /// A sources bundle handed to
132    /// [`MapResolver::from_sources_json`](super::MapResolver::from_sources_json)
133    /// is malformed: not a JSON object, an entry that is not a
134    /// single-key `{"json": "…"}` / `{"text": "…"}` object, or an
135    /// unknown front-end tag.
136    pub const BAD_SOURCES: &str = "dsl_kit::parse::import::bad_sources";
137}
138
139// ---------------------------------------------------------------------------
140// SourceId / ImportSource / SourceResolver
141// ---------------------------------------------------------------------------
142
143/// Canonical identity of a source, as produced by
144/// [`SourceResolver::resolve`].
145///
146/// The loader caches, cycle-checks, and reports dependencies on this
147/// id — two specifiers that resolve to the same id are the same
148/// source, fetched once. Resolvers should canonicalise here (e.g.
149/// collapse `./` path segments) so aliased spellings don't defeat the
150/// cache the way Lua's `package.loaded` string-keying does.
151#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
152pub struct SourceId(String);
153
154impl SourceId {
155    /// Wraps a canonical id string.
156    pub fn new(id: impl Into<String>) -> Self {
157        Self(id.into())
158    }
159
160    /// The canonical id as a string slice.
161    pub fn as_str(&self) -> &str {
162        &self.0
163    }
164}
165
166impl fmt::Display for SourceId {
167    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
168        f.write_str(&self.0)
169    }
170}
171
172/// A fetched source document, tagged with the front-end that should
173/// parse it.
174///
175/// `#[non_exhaustive]`: further front-ends may be added; match with a
176/// catch-all.
177#[derive(Debug, Clone, PartialEq, Eq)]
178#[non_exhaustive]
179pub enum ImportSource {
180    /// A JSON document, parsed through
181    /// [`serde_bridge::from_json_str`].
182    Json(String),
183    /// A canonical-text document, parsed through the [`Loader`]'s
184    /// configured [`Grammar`]. Requires [`Loader::with_grammar`];
185    /// otherwise the fetch fails with
186    /// [`import_codes::TEXT_UNSUPPORTED`].
187    Text(String),
188}
189
190/// Host-supplied import IO: turns literal specifiers into canonical
191/// ids and canonical ids into source text.
192///
193/// This is the only place bytes enter the loader — the kit core stays
194/// io-free, mirroring Jsonnet's `import_callback` / Starlark's
195/// embedder-owned `load` resolution. `resolve` receives the importing
196/// source (or `None` for the root document) so relative-path schemes
197/// can canonicalise against the importer, and is split from `fetch`
198/// so the loader can dedupe on the canonical id *before* paying for
199/// IO.
200pub trait SourceResolver {
201    /// Canonicalises `spec` (as written at the import site inside
202    /// `importer`) into a [`SourceId`].
203    ///
204    /// Errors are reported as [`import_codes::RESOLVE_FAILED`].
205    fn resolve(&mut self, importer: Option<&SourceId>, spec: &str) -> Result<SourceId, String>;
206
207    /// Produces the source document for a resolved id.
208    ///
209    /// Called at most once per id per [`load_json_str`] call; errors
210    /// are reported as [`import_codes::FETCH_FAILED`] and cached, so
211    /// a broken source fails every site that imports it without being
212    /// re-fetched.
213    fn fetch(&mut self, id: &SourceId) -> Result<ImportSource, String>;
214}
215
216/// The canonical sandboxed [`SourceResolver`]: a map of named
217/// in-memory sources.
218///
219/// Specifiers are used verbatim as canonical ids. Nothing outside the
220/// map is reachable, which makes this the default-deny resolver shape
221/// suited to MCP-style hosts where the client supplies every source
222/// inline.
223#[derive(Debug, Clone, Default)]
224pub struct MapResolver {
225    sources: BTreeMap<String, ImportSource>,
226}
227
228impl MapResolver {
229    /// Constructs an empty resolver.
230    pub fn new() -> Self {
231        Self::default()
232    }
233
234    /// Registers (or replaces) a named JSON source.
235    pub fn insert(&mut self, name: impl Into<String>, json: impl Into<String>) {
236        self.sources
237            .insert(name.into(), ImportSource::Json(json.into()));
238    }
239
240    /// Registers (or replaces) a named canonical-text source.
241    pub fn insert_text(&mut self, name: impl Into<String>, text: impl Into<String>) {
242        self.sources
243            .insert(name.into(), ImportSource::Text(text.into()));
244    }
245
246    /// Builds a resolver from a JSON sources bundle — the wire shape
247    /// MCP-style hosts receive from a client:
248    ///
249    /// ```json
250    /// { "lib":  { "json": "{ \"type\": \"Leaf\", … }" },
251    ///   "frag": { "text": "Leaf(value: \"x\")" } }
252    /// ```
253    ///
254    /// Every entry must be a single-key object tagging the front-end
255    /// explicitly (`json` / `text`) with a string payload — the
256    /// flavour lives in the data, never inferred. Anything else is a
257    /// [`import_codes::BAD_SOURCES`] diagnostic; problems across
258    /// entries are collected before failing.
259    pub fn from_sources_json(sources_json: &str) -> Result<Self, BuildError> {
260        let value: Value = serde_json::from_str(sources_json).map_err(|e| {
261            BuildError::single(Diagnostic::error(
262                import_codes::BAD_SOURCES,
263                format!("sources bundle is not valid JSON: {e}"),
264            ))
265        })?;
266        let Value::Object(map) = value else {
267            return Err(BuildError::single(Diagnostic::error(
268                import_codes::BAD_SOURCES,
269                "sources bundle must be a JSON object mapping names to \
270                 single-key {\"json\": …} / {\"text\": …} objects",
271            )));
272        };
273
274        let mut resolver = Self::new();
275        let mut diags = Vec::new();
276        for (name, entry) in map {
277            let bad = |what: &str| {
278                Diagnostic::error(
279                    import_codes::BAD_SOURCES,
280                    format!(
281                        "source `{name}` {what} (expected a single-key \
282                         {{\"json\": \"…\"}} or {{\"text\": \"…\"}} object)"
283                    ),
284                )
285            };
286            let Value::Object(entry) = entry else {
287                diags.push(bad("is not an object"));
288                continue;
289            };
290            if entry.len() != 1 {
291                diags.push(bad("must carry exactly one front-end key"));
292                continue;
293            }
294            let (kind, payload) = entry.iter().next().expect("len checked");
295            let Value::String(payload) = payload else {
296                diags.push(bad("has a non-string payload"));
297                continue;
298            };
299            match kind.as_str() {
300                "json" => resolver.insert(name, payload.clone()),
301                "text" => resolver.insert_text(name, payload.clone()),
302                other => diags.push(bad(&format!("uses unknown front-end tag `{other}`"))),
303            }
304        }
305        if diags.is_empty() {
306            Ok(resolver)
307        } else {
308            Err(BuildError::new(diags))
309        }
310    }
311}
312
313impl SourceResolver for MapResolver {
314    fn resolve(&mut self, _importer: Option<&SourceId>, spec: &str) -> Result<SourceId, String> {
315        Ok(SourceId::new(spec))
316    }
317
318    fn fetch(&mut self, id: &SourceId) -> Result<ImportSource, String> {
319        match self.sources.get(id.as_str()) {
320            Some(source) => Ok(source.clone()),
321            None => Err(format!("no source registered under `{id}`")),
322        }
323    }
324}
325
326// ---------------------------------------------------------------------------
327// Limits / Loaded
328// ---------------------------------------------------------------------------
329
330/// Hard caps on import expansion.
331///
332/// Reference expansion is a real denial-of-service class (the
333/// billion-laughs family), so every bound fails loudly with a
334/// dedicated diagnostic instead of degrading. The defaults are
335/// generous for configuration-sized documents; hosts embedding
336/// untrusted input should tighten them.
337#[derive(Debug, Clone, PartialEq, Eq)]
338pub struct ImportLimits {
339    /// Maximum import nesting depth (root = depth 0). Exceeding it is
340    /// [`import_codes::DEPTH_EXCEEDED`].
341    pub max_depth: usize,
342    /// Maximum number of distinct sources fetched in one load.
343    /// Exceeding it is [`import_codes::SOURCE_LIMIT`].
344    pub max_sources: usize,
345    /// Maximum total bytes fetched across all sources in one load.
346    /// Exceeding it is [`import_codes::BYTE_LIMIT`].
347    pub max_total_bytes: usize,
348}
349
350impl Default for ImportLimits {
351    fn default() -> Self {
352        Self {
353            max_depth: 32,
354            max_sources: 256,
355            max_total_bytes: 8 * 1024 * 1024,
356        }
357    }
358}
359
360/// A fully-linked document plus its resolved import graph.
361#[derive(Debug, Clone, PartialEq)]
362pub struct Loaded {
363    /// The root tree with every placeholder replaced by its expanded
364    /// source. Ready for [`check_conformance`](crate::check_conformance)
365    /// and [`DslBuild`](crate::DslBuild).
366    pub tree: ParseTree,
367    /// Every source the load touched, as canonical ids, sorted
368    /// ascending and deduplicated. Empty when the root document has
369    /// no imports.
370    pub dependencies: Vec<SourceId>,
371}
372
373impl Loaded {
374    /// Stable digest of the resolved graph: the fully-linked tree's
375    /// content plus the sorted dependency ids, hashed with FNV-1a 64.
376    ///
377    /// Loads that link to the same tree content produce the same
378    /// digest — so "did anything change?" is a single string
379    /// comparison, in the spirit of Dhall's normalized-expression
380    /// hash. Spans are excluded (surface detail: reformatting a
381    /// source must not disturb the digest); field payloads are hashed
382    /// through their [`RawValue`], so the digest is sensitive to
383    /// which front-end parsed a payload (`Text` vs `Json`) — compare
384    /// digests produced by the same front-end mix. Non-cryptographic
385    /// — a change detector, not an integrity check.
386    pub fn digest(&self) -> String {
387        let mut h = Fnv1a::new();
388        feed_tree(&mut h, &self.tree);
389        for d in &self.dependencies {
390            h.write(b"\x1fdep\x1f");
391            h.write(d.as_str().as_bytes());
392        }
393        format!("{:016x}", h.finish())
394    }
395}
396
397/// FNV-1a 64-bit, hand-rolled so the digest is stable across Rust
398/// releases (`DefaultHasher` makes no such promise) without pulling a
399/// hashing dependency into the parse trunk.
400struct Fnv1a(u64);
401
402impl Fnv1a {
403    fn new() -> Self {
404        Self(0xcbf2_9ce4_8422_2325)
405    }
406
407    fn write(&mut self, bytes: &[u8]) {
408        for &b in bytes {
409            self.0 ^= u64::from(b);
410            self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
411        }
412    }
413
414    fn finish(&self) -> u64 {
415        self.0
416    }
417}
418
419/// Feeds a tree into the digest in a canonical order. `\x1f` (unit
420/// separator) delimits framing so `("ab", "c")` and `("a", "bc")`
421/// cannot collide by concatenation.
422fn feed_tree(h: &mut Fnv1a, tree: &ParseTree) {
423    h.write(b"\x1fnode\x1f");
424    h.write(tree.variant.as_bytes());
425    for (name, value) in &tree.fields {
426        h.write(b"\x1ffield\x1f");
427        h.write(name.as_bytes());
428        h.write(b"\x1f");
429        match value {
430            RawValue::Text(t) => {
431                h.write(b"t\x1f");
432                h.write(t.as_bytes());
433            }
434            // Default serde_json maps are BTree-backed, so `to_string`
435            // is deterministic for equal values.
436            RawValue::Json(v) => {
437                h.write(b"j\x1f");
438                h.write(v.to_string().as_bytes());
439            }
440        }
441    }
442    for (slot, children) in &tree.children {
443        h.write(b"\x1fslot\x1f");
444        h.write(slot.as_bytes());
445        for c in children {
446            feed_tree(h, c);
447        }
448    }
449    for (slot, entries) in &tree.keyed_children {
450        h.write(b"\x1fkeyed\x1f");
451        h.write(slot.as_bytes());
452        for (key, c) in entries {
453            h.write(b"\x1fkey\x1f");
454            h.write(key.as_bytes());
455            feed_tree(h, c);
456        }
457    }
458    h.write(b"\x1fend\x1f");
459}
460
461// ---------------------------------------------------------------------------
462// Loader
463// ---------------------------------------------------------------------------
464
465/// Import loader: a schema, an optional text [`Grammar`], and the
466/// expansion limits, bundled so every front-end entry point shares one
467/// configuration.
468///
469/// Every load walks the same pipeline: parse the root with its
470/// front-end, then resolve every [`IMPORT_VARIANT`] placeholder — at
471/// any depth, in positional and keyed child slots alike — through the
472/// caller's [`SourceResolver`], parse each fetched source with the
473/// front-end its [`ImportSource`] arm names, recursively expand, and
474/// splice in place. Diagnostics from distinct import sites are
475/// collected before failing; diagnostics from *inside* an imported
476/// source are prefixed with an [`import_codes::IN_IMPORT`] context
477/// marker naming the source and the resolution chain.
478#[derive(Debug, Clone)]
479pub struct Loader<'a> {
480    schema: &'a NodeSchema,
481    grammar: Option<&'a Grammar>,
482    limits: ImportLimits,
483}
484
485impl<'a> Loader<'a> {
486    /// Constructs a loader with default [`ImportLimits`] and no text
487    /// grammar (JSON sources only).
488    pub fn new(schema: &'a NodeSchema) -> Self {
489        Self {
490            schema,
491            grammar: None,
492            limits: ImportLimits::default(),
493        }
494    }
495
496    /// Enables the canonical text front-end: text roots and
497    /// [`ImportSource::Text`] sources parse through `grammar`.
498    ///
499    /// Pass a grammar that has been through [`add_import_syntax`],
500    /// otherwise text sources cannot spell `@import` themselves.
501    pub fn with_grammar(mut self, grammar: &'a Grammar) -> Self {
502        self.grammar = Some(grammar);
503        self
504    }
505
506    /// Replaces the default [`ImportLimits`].
507    pub fn with_limits(mut self, limits: ImportLimits) -> Self {
508        self.limits = limits;
509        self
510    }
511
512    /// Loads a JSON root document and expands its imports to a
513    /// fixpoint.
514    pub fn load_json_str(
515        &self,
516        root: &str,
517        resolver: &mut dyn SourceResolver,
518    ) -> Result<Loaded, BuildError> {
519        let tree = serde_bridge::from_json_str(root, self.schema)?;
520        self.expand_root(tree, resolver)
521    }
522
523    /// [`Loader::load_json_str`] over an already-deserialized
524    /// [`serde_json::Value`].
525    pub fn load_json_value(
526        &self,
527        root: &Value,
528        resolver: &mut dyn SourceResolver,
529    ) -> Result<Loaded, BuildError> {
530        let tree = serde_bridge::from_json_value(root, self.schema)?;
531        self.expand_root(tree, resolver)
532    }
533
534    /// Loads a canonical-text root document and expands its imports
535    /// to a fixpoint. Requires [`Loader::with_grammar`].
536    pub fn load_text(
537        &self,
538        root: &str,
539        resolver: &mut dyn SourceResolver,
540    ) -> Result<Loaded, BuildError> {
541        let Some(grammar) = self.grammar else {
542            return Err(BuildError::single(Diagnostic::error(
543                import_codes::TEXT_UNSUPPORTED,
544                "cannot load a text root: this Loader has no grammar — \
545                 configure one with `Loader::with_grammar`",
546            )));
547        };
548        let tree = grammar.parse(root)?;
549        self.expand_root(tree, resolver)
550    }
551
552    fn expand_root(
553        &self,
554        tree: ParseTree,
555        resolver: &mut dyn SourceResolver,
556    ) -> Result<Loaded, BuildError> {
557        let mut state = LoadState {
558            resolver,
559            limits: &self.limits,
560            schema: self.schema,
561            grammar: self.grammar,
562            cache: BTreeMap::new(),
563            stack: Vec::new(),
564            total_bytes: 0,
565        };
566        let tree = expand(tree, None, 0, &mut state).map_err(BuildError::new)?;
567        let dependencies = state.cache.into_keys().collect();
568        Ok(Loaded { tree, dependencies })
569    }
570}
571
572/// Loads a JSON root document with default limits and no text
573/// front-end. Convenience wrapper over [`Loader`].
574pub fn load_json_str(
575    root: &str,
576    schema: &NodeSchema,
577    resolver: &mut dyn SourceResolver,
578    limits: &ImportLimits,
579) -> Result<Loaded, BuildError> {
580    Loader::new(schema)
581        .with_limits(limits.clone())
582        .load_json_str(root, resolver)
583}
584
585/// [`load_json_str`] over an already-deserialized
586/// [`serde_json::Value`].
587pub fn load_json_value(
588    root: &Value,
589    schema: &NodeSchema,
590    resolver: &mut dyn SourceResolver,
591    limits: &ImportLimits,
592) -> Result<Loaded, BuildError> {
593    Loader::new(schema)
594        .with_limits(limits.clone())
595        .load_json_value(root, resolver)
596}
597
598// ---------------------------------------------------------------------------
599// Text syntax injection
600// ---------------------------------------------------------------------------
601
602/// Adds the reserved `@import "name"` spelling to a text grammar.
603///
604/// Appends a rule named [`IMPORT_VARIANT`] whose body is
605/// `Node("$import", %kw:@import Field("spec", %str))`, and makes it an
606/// alternative of the grammar's start rule — for grammars generated by
607/// [`crate::schema_gen`], the start rule is the `node` choice that
608/// every child slot references, so the spelling becomes available at
609/// every node position. A start rule whose body is not a [`Peg::Choice`]
610/// is wrapped in one.
611///
612/// Opt-in by design: a grammar that never passes through this function
613/// accepts no import syntax, and the reserved rule is invisible to
614/// [`crate::example_gen`] (examples never spell `@import`) and exempt
615/// from [`crate::grammar_check`]'s schema-consistency pass.
616///
617/// Idempotent — a grammar that already carries the reserved rule is
618/// returned unchanged. Fails with [`crate::peg::codes::UNKNOWN_RULE`]
619/// if the start rule is not defined.
620pub fn add_import_syntax(grammar: &mut Grammar, ids: &IdGen) -> Result<(), BuildError> {
621    let already = grammar
622        .rules
623        .iter()
624        .any(|r| matches!(r, Peg::Rule { name, .. } if name == IMPORT_VARIANT));
625    if already {
626        return Ok(());
627    }
628
629    let start = grammar.start.clone();
630    let start_rule = grammar
631        .rules
632        .iter_mut()
633        .find(|r| matches!(r, Peg::Rule { name, .. } if *name == start));
634    let Some(Peg::Rule { body, .. }) = start_rule else {
635        return Err(BuildError::single(Diagnostic::error(
636            peg::codes::UNKNOWN_RULE,
637            format!("cannot add import syntax: start rule `{start}` is not defined"),
638        )));
639    };
640
641    match body.as_mut() {
642        Peg::Choice { alts, .. } => alts.push(peg::rule_ref(ids, IMPORT_VARIANT)),
643        _ => {
644            let dummy = peg::token(ids, "");
645            let old = std::mem::replace(body.as_mut(), dummy);
646            **body = peg::choice(ids, vec![old, peg::rule_ref(ids, IMPORT_VARIANT)]);
647        }
648    }
649
650    grammar.rules.push(peg::rule(
651        ids,
652        IMPORT_VARIANT,
653        peg::node(
654            ids,
655            IMPORT_VARIANT,
656            peg::seq(
657                ids,
658                vec![
659                    peg::token(ids, "%kw:@import"),
660                    peg::field(ids, IMPORT_SPEC_FIELD, peg::token(ids, "%str")),
661                ],
662            ),
663        ),
664    ));
665    Ok(())
666}
667
668/// Per-load expansion state.
669struct LoadState<'a> {
670    resolver: &'a mut dyn SourceResolver,
671    limits: &'a ImportLimits,
672    schema: &'a NodeSchema,
673    grammar: Option<&'a Grammar>,
674    /// Source cache keyed on canonical id. Both outcomes are memoised
675    /// — a broken source stays broken for every later site instead of
676    /// being re-fetched and re-parsed per importer.
677    cache: BTreeMap<SourceId, CacheEntry>,
678    /// The in-flight resolution chain, for cycle detection and chain
679    /// rendering in diagnostics.
680    stack: Vec<SourceId>,
681    total_bytes: usize,
682}
683
684enum CacheEntry {
685    /// Expansion in progress — hitting this from below is a cycle.
686    Pending,
687    /// Fully expanded, ready to splice as a clone.
688    Ready(ParseTree),
689    /// Fetch / parse / expansion failed; the diagnostics replay at
690    /// every importing site.
691    Failed(Vec<Diagnostic>),
692}
693
694impl LoadState<'_> {
695    /// Renders the current resolution chain, optionally extended with
696    /// one more hop, as `<root> → a → b`.
697    fn chain(&self, tail: Option<&SourceId>) -> String {
698        let mut parts = vec!["<root>".to_string()];
699        parts.extend(self.stack.iter().map(SourceId::to_string));
700        if let Some(t) = tail {
701            parts.push(t.to_string());
702        }
703        parts.join(" → ")
704    }
705}
706
707/// Recursively replaces every placeholder in `tree`.
708///
709/// `importer` is the source the tree came from (`None` = the root
710/// document); `depth` counts import hops, not tree depth.
711fn expand(
712    mut tree: ParseTree,
713    importer: Option<&SourceId>,
714    depth: usize,
715    state: &mut LoadState<'_>,
716) -> Result<ParseTree, Vec<Diagnostic>> {
717    if tree.variant == IMPORT_VARIANT {
718        let spec = placeholder_spec(&tree)?;
719        return resolve_import(&spec, importer, depth, state);
720    }
721
722    let mut diags = Vec::new();
723    for (_, slot) in &mut tree.children {
724        for child in std::mem::take(slot) {
725            match expand(child, importer, depth, state) {
726                Ok(t) => slot.push(t),
727                Err(ds) => diags.extend(ds),
728            }
729        }
730    }
731    for (_, entries) in &mut tree.keyed_children {
732        for (key, child) in std::mem::take(entries) {
733            match expand(child, importer, depth, state) {
734                Ok(t) => entries.push((key, t)),
735                Err(ds) => diags.extend(ds),
736            }
737        }
738    }
739    if diags.is_empty() {
740        Ok(tree)
741    } else {
742        Err(diags)
743    }
744}
745
746/// Extracts the literal specifier from a placeholder tree.
747fn placeholder_spec(tree: &ParseTree) -> Result<String, Vec<Diagnostic>> {
748    match tree.field(IMPORT_SPEC_FIELD) {
749        Some(RawValue::Json(Value::String(s))) => Ok(s.clone()),
750        Some(RawValue::Text(s)) => Ok(s.clone()),
751        _ => Err(vec![
752            Diagnostic::error(
753                import_codes::SPEC_SHAPE,
754                format!(
755                    "`{IMPORT_VARIANT}` placeholder lacks a string `{IMPORT_SPEC_FIELD}` payload",
756                ),
757            )
758            .with_span(tree.span),
759        ]),
760    }
761}
762
763/// Resolves one import site: cache lookup, limit checks, fetch, parse,
764/// recursive expansion.
765fn resolve_import(
766    spec: &str,
767    importer: Option<&SourceId>,
768    depth: usize,
769    state: &mut LoadState<'_>,
770) -> Result<ParseTree, Vec<Diagnostic>> {
771    if depth + 1 > state.limits.max_depth {
772        return Err(vec![Diagnostic::error(
773            import_codes::DEPTH_EXCEEDED,
774            format!(
775                "import nesting exceeds max_depth {} at `{spec}` (chain: {})",
776                state.limits.max_depth,
777                state.chain(None),
778            ),
779        )]);
780    }
781
782    let id = state.resolver.resolve(importer, spec).map_err(|e| {
783        vec![Diagnostic::error(
784            import_codes::RESOLVE_FAILED,
785            format!(
786                "cannot resolve import `{spec}`: {e} (chain: {})",
787                state.chain(None)
788            ),
789        )]
790    })?;
791
792    match state.cache.get(&id) {
793        Some(CacheEntry::Pending) => {
794            return Err(vec![Diagnostic::error(
795                import_codes::CYCLE,
796                format!("import cycle detected: {}", state.chain(Some(&id))),
797            )]);
798        }
799        Some(CacheEntry::Ready(tree)) => return Ok(tree.clone()),
800        Some(CacheEntry::Failed(diags)) => return Err(diags.clone()),
801        None => {}
802    }
803
804    if state.cache.len() + 1 > state.limits.max_sources {
805        return Err(vec![Diagnostic::error(
806            import_codes::SOURCE_LIMIT,
807            format!(
808                "import expansion exceeds max_sources {} at `{id}` (chain: {})",
809                state.limits.max_sources,
810                state.chain(None),
811            ),
812        )]);
813    }
814
815    let fetched = match state.resolver.fetch(&id) {
816        Ok(s) => s,
817        Err(e) => {
818            let diags = vec![Diagnostic::error(
819                import_codes::FETCH_FAILED,
820                format!(
821                    "cannot fetch import `{id}`: {e} (chain: {})",
822                    state.chain(None)
823                ),
824            )];
825            state.cache.insert(id, CacheEntry::Failed(diags.clone()));
826            return Err(diags);
827        }
828    };
829
830    let source_len = match &fetched {
831        ImportSource::Json(text) | ImportSource::Text(text) => text.len(),
832    };
833    state.total_bytes += source_len;
834    if state.total_bytes > state.limits.max_total_bytes {
835        let diags = vec![Diagnostic::error(
836            import_codes::BYTE_LIMIT,
837            format!(
838                "import expansion exceeds max_total_bytes {} at `{id}` (chain: {})",
839                state.limits.max_total_bytes,
840                state.chain(None),
841            ),
842        )];
843        state.cache.insert(id, CacheEntry::Failed(diags.clone()));
844        return Err(diags);
845    }
846
847    let parsed = match fetched {
848        ImportSource::Json(text) => serde_bridge::from_json_str(&text, state.schema),
849        ImportSource::Text(text) => match state.grammar {
850            Some(grammar) => grammar.parse(&text),
851            None => {
852                let diags = vec![Diagnostic::error(
853                    import_codes::TEXT_UNSUPPORTED,
854                    format!(
855                        "import `{id}` is a text source but this Loader has no \
856                         grammar — configure one with `Loader::with_grammar` \
857                         (chain: {})",
858                        state.chain(None),
859                    ),
860                )];
861                state.cache.insert(id, CacheEntry::Failed(diags.clone()));
862                return Err(diags);
863            }
864        },
865    };
866
867    let parsed = match parsed {
868        Ok(tree) => tree,
869        Err(err) => {
870            let diags = in_import(&id, state, err.diagnostics);
871            state.cache.insert(id, CacheEntry::Failed(diags.clone()));
872            return Err(diags);
873        }
874    };
875
876    state.cache.insert(id.clone(), CacheEntry::Pending);
877    state.stack.push(id.clone());
878    let expanded = expand(parsed, Some(&id), depth + 1, state);
879    state.stack.pop();
880
881    match expanded {
882        Ok(tree) => {
883            state.cache.insert(id, CacheEntry::Ready(tree.clone()));
884            Ok(tree)
885        }
886        Err(diags) => {
887            let diags = in_import(&id, state, diags);
888            state.cache.insert(id, CacheEntry::Failed(diags.clone()));
889            Err(diags)
890        }
891    }
892}
893
894/// Prefixes diagnostics that originate inside an imported source with
895/// a context marker naming the source and the resolution chain.
896///
897/// Nested failures are wrapped once per hop, so a deep failure reads
898/// outermost-first. Diagnostics already carrying an
899/// [`import_codes::IN_IMPORT`] marker for this exact source are not
900/// re-wrapped (replayed cache entries arrive pre-wrapped).
901fn in_import(id: &SourceId, state: &LoadState<'_>, diags: Vec<Diagnostic>) -> Vec<Diagnostic> {
902    let marker = format!("in import `{id}`");
903    if diags
904        .first()
905        .is_some_and(|d| d.code == import_codes::IN_IMPORT && d.message.starts_with(&marker))
906    {
907        return diags;
908    }
909    let mut out = vec![Diagnostic::error(
910        import_codes::IN_IMPORT,
911        format!("{marker} (chain: {})", state.chain(Some(id))),
912    )];
913    out.extend(diags);
914    out
915}