Skip to main content

instruction_md/
resolve.rs

1//! The resolution transaction (§13, §14.1): a document, its bases and its includes become one resolved artifact
2//! (`instruction-resolved/1`) and its agent text (`instruction-text/1`).
3//!
4//!  1. read every source and keep its diagnostics;
5//!  2. compose depth-first: each base of `extends`, in declared order, is resolved on its own (its bases, patches and
6//!     includes first) as the instance `<parent>/<alias>`; the child's replace, extend and remove patches then apply
7//!     to that inherited tree, in source order, by qualified explicit id (`#alias/id`); its own body follows, with
8//!     each `::include` replaced by the content it selects, again a separate instance;
9//!  3. substitute each source's parameters into its parsed prose and its rules' conditions and reasons, as data;
10//!  4. emit the body with every node's instance, the dependencies and provenance, the diagnostics and a status, and
11//!     digest the whole in RFC 8785 form.
12//!
13//! Loading is the host's: [`resolve`] asks its loader for each source by its resolved URI and never fetches anything
14//! itself. Typed references resolve to the document's own objects; no resolver adapter is bound here, so nothing is
15//! enriched and a declared extension's manifest is never retrieved (an optional one leaves the result partial, a
16//! required one is an error).
17
18use std::collections::{BTreeMap, HashMap};
19use std::rc::Rc;
20use std::sync::LazyLock;
21
22use serde_json::{Map, Value};
23
24use crate::check::inline_diagnostics;
25use crate::digest::{digest, sha256_hex};
26use crate::inline::{TokenType, inline_tokens};
27use crate::jcs::{canonical_json, json_digest};
28use crate::js::{JS_DOT, JS_SPACES, blank, is_str, js_number, js_trim, js_value};
29use crate::pattern::Pattern;
30use crate::read::{ProseRef, ReadOptions, Reading, read, sort_diagnostics, value_fits};
31use crate::registry::is_rule;
32use crate::text::{ReferenceRecord, TextOptions, interpolate_values, literal, text_of, value_text};
33use crate::types::{Diagnostic, Document, Identity, KeyOrder, Metadata, Node, Object, Range, Severity};
34
35/// The resolved artifact's format.
36pub const RESOLVED_FORMAT: &str = "instruction-resolved/1";
37
38const DEFAULT_URI: &str = "document.md";
39
40/// A source a host hands the resolver: its resolved URI, its text and, when the provider knows one, its version.
41#[derive(Clone, Debug, Default, PartialEq)]
42pub struct Source {
43    pub uri: String,
44    pub text: String,
45    pub version: String,
46}
47
48/// Loads a source by its resolved URI (without a fragment); `None` when it is absent or the reader may not read it.
49pub type Loader<'a> = &'a dyn Fn(&str) -> Option<Source>;
50
51/// What configures a resolution.
52#[derive(Clone, Default)]
53pub struct ResolveOptions<'a> {
54    /// The document's own URI, which relative references resolve against (default `document.md`).
55    pub uri: String,
56    pub version: String,
57    /// The document's parameter values (§12); a base gets its record's `with`.
58    pub params: Object,
59    /// Loads what the document composes ([`resolve`] only).
60    pub load: Option<Loader<'a>>,
61    /// Bound the composition (defaults 8 and 64): past either, an error, never a silently truncated result (§18).
62    pub max_depth: usize,
63    pub max_sources: usize,
64}
65
66/// A selector (§11.2): an explicit id, a heading (its first occurrence unless one is given), or a span of lines.
67#[derive(Clone, Debug, PartialEq)]
68pub enum Selector {
69    Id(String),
70    Heading { heading: String, occurrence: Option<f64> },
71    Lines(f64, f64),
72}
73
74impl Selector {
75    pub fn to_json(&self) -> Value {
76        let mut m = Map::new();
77        match self {
78            Selector::Id(id) => {
79                m.insert("id".into(), id.clone().into());
80            }
81            Selector::Heading { heading, occurrence } => {
82                m.insert("heading".into(), heading.clone().into());
83                if let Some(o) = occurrence {
84                    m.insert("occurrence".into(), crate::js::num(*o));
85                }
86            }
87            Selector::Lines(a, b) => {
88                m.insert("lines".into(), Value::Array(vec![crate::js::num(*a), crate::js::num(*b)]));
89            }
90        }
91        Value::Object(m)
92    }
93
94    fn describe(&self) -> String {
95        match self {
96            Selector::Id(id) => format!("has the id {id}"),
97            Selector::Heading { heading, .. } => format!("is the heading \"{heading}\""),
98            Selector::Lines(..) => "matches the selector".into(),
99        }
100    }
101}
102
103/// A source the resolution composed.
104#[derive(Clone, Debug, PartialEq)]
105pub struct Dependency {
106    pub uri: String,
107    pub resolved_uri: String,
108    pub sha256: String,
109    /// live or pinned
110    pub mode: String,
111    pub version: String,
112    pub selector: Option<Selector>,
113    pub instance: String,
114}
115
116impl Dependency {
117    pub fn to_json(&self) -> Value {
118        let mut m = Map::new();
119        m.insert("uri".into(), self.uri.clone().into());
120        m.insert("resolved_uri".into(), self.resolved_uri.clone().into());
121        m.insert("sha256".into(), self.sha256.clone().into());
122        m.insert("mode".into(), self.mode.clone().into());
123        if !self.version.is_empty() {
124            m.insert("version".into(), self.version.clone().into());
125        }
126        if let Some(s) = &self.selector {
127            m.insert("selector".into(), s.to_json());
128        }
129        m.insert("instance".into(), self.instance.clone().into());
130        Value::Object(m)
131    }
132}
133
134/// Where an instance came from, or what changed it.
135#[derive(Clone, Debug, PartialEq, Default)]
136pub struct Provenance {
137    pub instance: String,
138    pub uri: String,
139    pub range: Option<Range>,
140    pub selector: Option<Selector>,
141    /// include, inherit, replace, extend or remove
142    pub operation: String,
143    pub target: String,
144    pub reason: String,
145    pub modified_by: String,
146    pub original: Option<Node>,
147}
148
149impl Provenance {
150    pub fn to_json(&self) -> Value {
151        let mut m = Map::new();
152        m.insert("instance".into(), self.instance.clone().into());
153        m.insert("uri".into(), self.uri.clone().into());
154        if let Some(r) = self.range {
155            m.insert("range".into(), r.to_json());
156        }
157        if let Some(s) = &self.selector {
158            m.insert("selector".into(), s.to_json());
159        }
160        for (k, v) in
161            [("operation", &self.operation), ("target", &self.target), ("reason", &self.reason), ("modified_by", &self.modified_by)]
162        {
163            if !v.is_empty() {
164                m.insert(k.into(), v.clone().into());
165            }
166        }
167        if let Some(n) = &self.original {
168            m.insert("original".into(), n.to_json());
169        }
170        Value::Object(m)
171    }
172}
173
174/// An extension bound to an instance.
175#[derive(Clone, Debug, PartialEq)]
176pub struct ExtensionBinding {
177    pub instance: String,
178    pub alias: String,
179    pub id: String,
180    pub version: String,
181    pub sha256: String,
182}
183
184impl ExtensionBinding {
185    pub fn to_json(&self) -> Value {
186        let mut m = Map::new();
187        for (k, v) in
188            [("instance", &self.instance), ("alias", &self.alias), ("id", &self.id), ("version", &self.version), ("sha256", &self.sha256)]
189        {
190            m.insert(k.into(), v.clone().into());
191        }
192        Value::Object(m)
193    }
194}
195
196/// The resolved document's identity.
197#[derive(Clone, Debug, PartialEq, Default)]
198pub struct ResolvedDocument {
199    pub uri: String,
200    pub sha256: String,
201    pub version: String,
202}
203
204/// `instruction-resolved/1` (schemas/resolved.schema.json): what a delivery's manifest names.
205#[derive(Clone, Debug, PartialEq)]
206pub struct Resolved {
207    pub format: String,
208    /// complete or partial
209    pub status: String,
210    pub document: ResolvedDocument,
211    pub body: Vec<Node>,
212    pub extensions: Vec<ExtensionBinding>,
213    pub objects: Vec<ReferenceRecord>,
214    pub resources: Vec<ReferenceRecord>,
215    pub dependencies: Vec<Dependency>,
216    pub provenance: Vec<Provenance>,
217    pub diagnostics: Vec<Diagnostic>,
218    pub resolved_digest: String,
219}
220
221impl Resolved {
222    /// What a delivery of this resolution signs ([`Manifest`]).
223    ///
224    /// ```
225    /// use instruction_md::{resolve, ResolveOptions};
226    ///
227    /// let r = resolve("MUST: be brief.\n", &ResolveOptions { uri: "instruction://ins_1".into(), version: "ver_1".into(), ..ResolveOptions::default() });
228    /// let m = r.resolved.manifest().to_json();
229    /// assert_eq!(m["format"], "instruction-resolved/1");
230    /// assert_eq!(m["document"]["version"], "ver_1");
231    /// assert_eq!(m["resolved_digest"], r.resolved.resolved_digest.as_str());
232    /// ```
233    pub fn manifest(&self) -> Manifest {
234        Manifest {
235            format: self.format.clone(),
236            status: self.status.clone(),
237            document: self.document.clone(),
238            dependencies: self.dependencies.clone(),
239            resolved_digest: self.resolved_digest.clone(),
240        }
241    }
242
243    /// The artifact as JSON.
244    pub fn to_json(&self) -> Value {
245        let mut m = self.artifact();
246        m.insert("resolved_digest".into(), self.resolved_digest.clone().into());
247        Value::Object(m)
248    }
249
250    /// The artifact without its digest.
251    fn artifact(&self) -> Map<String, Value> {
252        let mut m = Map::new();
253        m.insert("format".into(), self.format.clone().into());
254        m.insert("status".into(), self.status.clone().into());
255        m.insert("document".into(), self.document.to_json());
256        m.insert("body".into(), Value::Array(self.body.iter().map(Node::to_json).collect()));
257        m.insert("extensions".into(), Value::Array(self.extensions.iter().map(ExtensionBinding::to_json).collect()));
258        m.insert("objects".into(), Value::Array(self.objects.iter().map(ReferenceRecord::to_json).collect()));
259        m.insert("resources".into(), Value::Array(self.resources.iter().map(ReferenceRecord::to_json).collect()));
260        m.insert("dependencies".into(), Value::Array(self.dependencies.iter().map(Dependency::to_json).collect()));
261        m.insert("provenance".into(), Value::Array(self.provenance.iter().map(Provenance::to_json).collect()));
262        m.insert("diagnostics".into(), Value::Array(self.diagnostics.iter().map(Diagnostic::to_json).collect()));
263        m
264    }
265}
266
267/// What a delivery signature binds of its resolution (§7.6): the resolved artifact's format, status, document,
268/// dependencies and digest — never its body. A delivery attestation's `manifest` claim is [`Manifest::to_json`], and
269/// [`crate::verify_delivery`] checks that the author's digest is `document.sha256`.
270///
271/// The instruction/1 counterpart of the 1.1 resolution manifest: the authored digest and version are `document`
272/// (`sha256`, `version`); the includes are `dependencies`, each base and include with its URI, resolved URI, digest,
273/// mode (live or pinned), version, selector and instance; what was left unresolved is the `status` (`partial`). There
274/// are no facts or variants to record in this edition (every reader receives the same text), parameter values are
275/// part of `resolved_digest` (the artifact's body carries them), and the patches that changed an inherited tree are
276/// the artifact's provenance and the agent text's "Composition changes".
277#[derive(Clone, Debug, PartialEq)]
278pub struct Manifest {
279    /// instruction-resolved/1
280    pub format: String,
281    /// complete or partial
282    pub status: String,
283    pub document: ResolvedDocument,
284    pub dependencies: Vec<Dependency>,
285    /// The resolved artifact's RFC 8785 digest.
286    pub resolved_digest: String,
287}
288
289impl Manifest {
290    /// The manifest as a delivery claim carries it: `{format, status, document: {uri, sha256, version?},
291    /// dependencies, resolved_digest}`.
292    pub fn to_json(&self) -> Value {
293        let mut m = Map::new();
294        m.insert("format".into(), self.format.clone().into());
295        m.insert("status".into(), self.status.clone().into());
296        m.insert("document".into(), self.document.to_json());
297        m.insert("dependencies".into(), Value::Array(self.dependencies.iter().map(Dependency::to_json).collect()));
298        m.insert("resolved_digest".into(), self.resolved_digest.clone().into());
299        Value::Object(m)
300    }
301}
302
303impl ResolvedDocument {
304    /// `{uri, sha256, version?}`.
305    pub fn to_json(&self) -> Value {
306        let mut d = Map::new();
307        d.insert("uri".into(), self.uri.clone().into());
308        d.insert("sha256".into(), self.sha256.clone().into());
309        if !self.version.is_empty() {
310            d.insert("version".into(), self.version.clone().into());
311        }
312        Value::Object(d)
313    }
314}
315
316/// A resolution's outcome.
317#[derive(Clone, Debug)]
318pub struct Resolution {
319    /// No error: a successful resolution, which a registry may deliver.
320    pub ok: bool,
321    pub resolved: Resolved,
322    /// The agent text, `instruction-text/1`.
323    pub text: String,
324    pub diagnostics: Vec<Diagnostic>,
325    /// The document's own reading: its identities, parameters and lines.
326    pub root: Reading,
327}
328
329/// Resolves a document: reads it, loads what it composes through `opts.load` (in rounds, each source once),
330/// composes.
331pub fn resolve(text: &str, opts: &ResolveOptions) -> Resolution {
332    let uri = if opts.uri.is_empty() { DEFAULT_URI.to_string() } else { opts.uri.clone() };
333    let limit = if opts.max_sources == 0 { 64 } else { opts.max_sources };
334    let mut sources: BTreeMap<String, Option<Source>> = BTreeMap::new();
335    let mut pending = references_of(&read(text, &ReadOptions { uri: uri.clone(), ..ReadOptions::default() }), &uri);
336    if let Some(load) = opts.load {
337        while !pending.is_empty() && sources.len() < limit {
338            let round: Vec<String> = pending.drain(..).filter(|u| !sources.contains_key(u)).collect();
339            for u in round {
340                if sources.len() >= limit {
341                    break;
342                }
343                if sources.contains_key(&u) {
344                    continue;
345                }
346                let s = load(&u);
347                if let Some(s) = &s {
348                    for next in references_of(&read(&s.text, &ReadOptions { uri: s.uri.clone(), ..ReadOptions::default() }), &s.uri) {
349                        if !sources.contains_key(&next) && !pending.contains(&next) {
350                            pending.push(next);
351                        }
352                    }
353                }
354                sources.insert(u, s);
355            }
356        }
357    }
358    let loaded: HashMap<String, Source> = sources.into_iter().filter_map(|(k, v)| v.map(|v| (k, v))).collect();
359    resolve_with(text, &loaded, opts)
360}
361
362/// Resolves a document over sources already loaded, by resolved URI.
363pub fn resolve_with(text: &str, sources: &HashMap<String, Source>, opts: &ResolveOptions) -> Resolution {
364    let uri = if opts.uri.is_empty() { DEFAULT_URI.to_string() } else { opts.uri.clone() };
365    let root = Rc::new(Loaded {
366        uri: uri.clone(),
367        sha256: digest(text.as_bytes()),
368        version: opts.version.clone(),
369        read: read(text, &ReadOptions { uri, ..ReadOptions::default() }),
370    });
371    let lookup = |u: &str| -> Option<Rc<Loaded>> {
372        let s = sources.get(u)?;
373        Some(Rc::new(Loaded {
374            uri: s.uri.clone(),
375            sha256: digest(s.text.as_bytes()),
376            version: s.version.clone(),
377            read: read(&s.text, &ReadOptions { uri: s.uri.clone(), ..ReadOptions::default() }),
378        }))
379    };
380    run(root, &lookup, opts)
381}
382
383/// Resolves an authored tree over other trees, by URI (the specification's resolution cases are trees). A tree has
384/// no source bytes, so its digest is that of its canonical JSON.
385pub fn resolve_tree(document: &Document, sources: &HashMap<String, Document>, opts: &ResolveOptions) -> Resolution {
386    let as_loaded = |d: &Document, u: &str| -> Rc<Loaded> {
387        let u = if d.uri.is_empty() { u.to_string() } else { d.uri.clone() };
388        Rc::new(Loaded { uri: u.clone(), sha256: json_digest(&d.json_value()), version: String::new(), read: from_tree(d, &u) })
389    };
390    let uri = if !opts.uri.is_empty() {
391        opts.uri.clone()
392    } else if !document.uri.is_empty() {
393        document.uri.clone()
394    } else {
395        DEFAULT_URI.to_string()
396    };
397    let lookup = |u: &str| sources.get(u).map(|d| as_loaded(d, u));
398    run(as_loaded(document, &uri), &lookup, opts)
399}
400
401fn run(root: Rc<Loaded>, lookup: &dyn Fn(&str) -> Option<Rc<Loaded>>, opts: &ResolveOptions) -> Resolution {
402    let depth = if opts.max_depth == 0 { 8 } else { opts.max_depth };
403    let mut c = Composer {
404        lookup,
405        depth,
406        diagnostics: Vec::new(),
407        provenance: Vec::new(),
408        dependencies: Vec::new(),
409        partial: false,
410        identities: HashMap::new(),
411        loaded: HashMap::new(),
412    };
413    c.diagnostics.extend(root.read.diagnostics.iter().cloned());
414    c.diagnostics.extend(inline_diagnostics(&root.read));
415    let body = c.compose(&root, &[], "root", &opts.params).unwrap_or_default();
416    c.check_allowances(&body, &root.uri);
417    let mut diagnostics = c.diagnostics.clone();
418    sort_diagnostics(&mut diagnostics, true);
419    let mut partial = c.partial;
420    let mut ok = true;
421    for d in &diagnostics {
422        partial = partial || d.code == "reference-optional" || d.code == "parameter-optional";
423        ok = ok && d.severity != Severity::Error;
424    }
425    let mut resolved = Resolved {
426        format: RESOLVED_FORMAT.into(),
427        status: if partial { "partial".into() } else { "complete".into() },
428        document: ResolvedDocument { uri: root.uri.clone(), sha256: root.sha256.clone(), version: root.version.clone() },
429        body,
430        extensions: Vec::new(),
431        objects: Vec::new(),
432        resources: Vec::new(),
433        dependencies: std::mem::take(&mut c.dependencies),
434        provenance: std::mem::take(&mut c.provenance),
435        diagnostics: diagnostics.clone(),
436        resolved_digest: String::new(),
437    };
438    resolved.resolved_digest = format!("sha256:{}", sha256_hex(canonical_json(&Value::Object(resolved.artifact())).as_bytes()));
439    let identities = &c.identities;
440    let known = |instance: &str, id: &str| identities.get(instance).is_some_and(|l| l.read.identity(id).is_some());
441    let mut records = resolved.objects.clone();
442    records.extend(resolved.resources.iter().cloned());
443    let text = text_of(&resolved.body, &records, &resolved.provenance, &TextOptions { known: Some(&known), ..TextOptions::default() });
444    let root_read = root.read.clone();
445    Resolution { ok, resolved, text, diagnostics, root: root_read }
446}
447
448/// Reads a tree as the composer reads a source: its explicit identities, and every Markdown node outside a literal
449/// body as prose. A tree declares no parameters: no reader ran over it.
450fn from_tree(document: &Document, uri: &str) -> Reading {
451    let mut r = Reading::empty();
452    let mut body = document.body.clone();
453    fn walk(nodes: &mut [Node], quoted: bool, r: &mut Reading) {
454        for n in nodes {
455            if n.is_markdown() {
456                if !quoted {
457                    n.prose = true;
458                    r.prose_order.push(ProseRef { source: n.source.clone(), range: n.range });
459                }
460                continue;
461            }
462            if let Some(Value::String(id)) = n.attrs.get("id") {
463                r.add_identity(Identity { id: id.clone(), kind: n.kind.clone(), line: n.range.map_or(0, |rg| rg.start) }, true);
464            }
465            let q = quoted || literal(n);
466            if let Some(children) = n.children.as_mut() {
467                walk(children, q, r);
468            }
469        }
470    }
471    walk(&mut body, false, &mut r);
472    r.document = Document {
473        format: document.format.clone(),
474        uri: uri.to_string(),
475        metadata: Metadata {
476            front: document.metadata.front.clone(),
477            back: document.metadata.back.clone(),
478            front_order: document.metadata.front_order.clone(),
479        },
480        body,
481        raw: None,
482    };
483    r
484}
485
486/// The sources a document composes, as resolved URIs without fragments: its bases and its includes.
487pub fn references_of(r: &Reading, base: &str) -> Vec<String> {
488    let mut out: Vec<String> = Vec::new();
489    let mut add = |target: &str| {
490        let u = without_fragment(&resolve_uri(&named(r, target), base)).to_string();
491        if !out.contains(&u) {
492            out.push(u);
493        }
494    };
495    if let Some(Value::Array(list)) = r.document.metadata.front.get("extends") {
496        for e in list {
497            if let Some(Value::String(u)) = e.get("uri") {
498                add(u);
499            }
500        }
501    }
502    fn walk(nodes: &[Node], add: &mut dyn FnMut(&str)) {
503        for n in nodes {
504            if !n.is_directive() {
505                continue;
506            }
507            if n.kind == "include"
508                && let Some(Value::String(src)) = n.attrs.get("src")
509            {
510                add(src);
511            }
512            walk(n.children(), add);
513        }
514    }
515    walk(&r.document.body, &mut add);
516    out
517}
518
519// ---- composition ----
520
521struct Loaded {
522    uri: String,
523    sha256: String,
524    version: String,
525    read: Reading,
526}
527
528/// A base record or an include, as the composer imports either.
529struct ImportRef {
530    uri: String,
531    alias: String,
532    mode: Option<Value>,
533    sha256: Option<Value>,
534    version: Option<Value>,
535    select_value: Option<Value>,
536    required: bool,
537    with: Object,
538    /// a base (an include otherwise)
539    inherit: bool,
540    line: u32,
541}
542
543struct Composer<'l> {
544    lookup: &'l dyn Fn(&str) -> Option<Rc<Loaded>>,
545    depth: usize,
546    diagnostics: Vec<Diagnostic>,
547    provenance: Vec<Provenance>,
548    dependencies: Vec<Dependency>,
549    partial: bool,
550    /// each instance's reading: what a typed reference written in it can name
551    identities: HashMap<String, Rc<Loaded>>,
552    loaded: HashMap<String, Rc<Loaded>>,
553}
554
555/// Where diagnostics about a source go: under its URI, unless it is the document itself.
556fn where_(doc: &Loaded, instance: &str) -> String {
557    if instance == "root" { String::new() } else { doc.uri.clone() }
558}
559
560fn front_line(r: &Reading) -> u32 {
561    r.front_range.map_or(0, |fr| fr.start)
562}
563
564impl Composer<'_> {
565    /// S29 §5: a change of an inherited allowance that widens it.
566    fn widened(&mut self, before: &Object, after: &Object, id: &str, uri: String, line: u32) {
567        let w = crate::allowance::widenings(before, after);
568        if !w.is_empty() {
569            self.diag(
570                "allowance-widened",
571                Severity::Error,
572                format!("#{id}: an extending document may only narrow an inherited allowance; this widens {}", w.join(", ")),
573                uri,
574                line,
575            );
576            if let Some(d) = self.diagnostics.last_mut() {
577                d.target = format!("#{id}");
578            }
579        }
580    }
581
582    /// S29: each allowance once composed — its values as parameters resolved them, and what its references name.
583    fn check_allowances(&mut self, body: &[Node], root: &str) {
584        let mut seen: std::collections::HashSet<(u32, &'static str)> =
585            self.diagnostics.iter().map(|d| (d.range.map_or(0, |r| r.start), d.code)).collect();
586        let mut found: Vec<(&'static str, String, String, u32, String)> = Vec::new();
587        self.visit_allowances(body, root, &mut found);
588        for (code, message, uri, line, target) in found {
589            if seen.insert((line, code)) {
590                self.diag(code, Severity::Error, message, uri, line);
591                if let Some(d) = self.diagnostics.last_mut() {
592                    d.target = target;
593                }
594            }
595        }
596    }
597
598    fn kind_of(&self, instance: &str, reference: &str) -> Option<String> {
599        let r = reference.trim_start_matches(['#', '&']);
600        let parts: Vec<&str> = r.split('/').collect();
601        let (inst, id) = if parts.len() > 1 {
602            (format!("{instance}/{}", parts[..parts.len() - 1].join("/")), parts[parts.len() - 1])
603        } else {
604            (instance.to_string(), parts[0])
605        };
606        if let Some(found) = self.identities.get(&inst).and_then(|l| l.read.identity(id)) {
607            return Some(found.kind.clone());
608        }
609        // (an inherited object a child names unqualified: its bases' ids, when one of them alone has it)
610        let prefix = format!("{instance}/");
611        let kinds: Vec<String> = self
612            .identities
613            .iter()
614            .filter(|(k, _)| k.starts_with(&prefix))
615            .filter_map(|(_, l)| l.read.identity(id).map(|i| i.kind.clone()))
616            .collect();
617        if kinds.len() == 1 { kinds.into_iter().next() } else { None }
618    }
619
620    fn visit_allowances(&self, nodes: &[Node], root: &str, found: &mut Vec<(&'static str, String, String, u32, String)>) {
621        for n in nodes {
622            if !n.is_directive() {
623                continue;
624            }
625            if n.kind == "allowance" {
626                let instance = if n.instance.is_empty() { "root" } else { n.instance.as_str() };
627                let uri = if instance == "root" { String::new() } else { root.to_string() };
628                let line = n.range.map_or(0, |r| r.start);
629                let id = n.attrs.get("id").and_then(Value::as_str).unwrap_or("");
630                let target = if id.is_empty() { String::new() } else { format!("#{id}") };
631                let mut say = |code: &'static str, message: String| found.push((code, message, uri.clone(), line, target.clone()));
632                for p in crate::allowance::problems(&n.attrs).into_iter().chain(crate::allowance::unresolved(&n.attrs)) {
633                    say(p.code, format!("allowance #{id}: {}", p.message));
634                }
635                for w in crate::allowance::list(n.attrs.get("wallet")).into_iter().filter(|w| !w.is_empty()) {
636                    match self.kind_of(instance, &w) {
637                        None => say("reference-missing", format!("allowance #{id}: wallet {w} names nothing")),
638                        Some(k) if k != "wallet" => say("reference-kind", format!("allowance #{id}: {w} is a {k}, not a wallet")),
639                        _ => {}
640                    }
641                }
642                // (a bare name is a role's name, the host binds it; `#id` names a person or role in the document)
643                if let Some(a) = n.attrs.get("approver").and_then(Value::as_str).filter(|a| a.starts_with('#')) {
644                    match self.kind_of(instance, a) {
645                        None => say("reference-missing", format!("allowance #{id}: approver {a} names nothing")),
646                        Some(k) if k != "person" && k != "role" => say(
647                            "allowance-approver-not-person",
648                            format!("allowance #{id}: the approver {a} is a {k}; a person or a role approves, never an agent"),
649                        ),
650                        _ => {}
651                    }
652                }
653                if n.attrs.contains_key("payees") {
654                    for p in crate::allowance::list(n.attrs.get("payees")).into_iter().filter(|p| p.starts_with('&')) {
655                        if self.kind_of(instance, &p).is_none() {
656                            say("reference-missing", format!("allowance #{id}: payee {p} names nothing"));
657                        }
658                    }
659                }
660            }
661            self.visit_allowances(n.children(), root, found);
662        }
663    }
664
665    fn diag(&mut self, code: &'static str, severity: Severity, message: String, uri: String, line: u32) {
666        let mut d = Diagnostic::new(code, severity, message, line);
667        d.uri = uri;
668        self.diagnostics.push(d);
669    }
670
671    /// A document's effective body as the instance, or `None` when it cannot be composed (a cycle, the depth).
672    fn compose(&mut self, doc: &Rc<Loaded>, trail: &[String], instance: &str, values: &Object) -> Option<Vec<Node>> {
673        let r = &doc.read;
674        let uri = where_(doc, instance);
675        if trail.contains(&doc.uri) {
676            let mut path = trail.to_vec();
677            path.push(doc.uri.clone());
678            self.diag("composition-cycle", Severity::Error, format!("{} composes itself: {}", doc.uri, path.join(" → ")), uri, 0);
679            return None;
680        }
681        if trail.len() >= self.depth {
682            self.diag(
683                "limit-exceeded",
684                Severity::Error,
685                format!("composition is deeper than {} documents at {}", self.depth, doc.uri),
686                uri,
687                0,
688            );
689            return None;
690        }
691        self.loaded.entry(doc.uri.clone()).or_insert_with(|| doc.clone());
692        self.identities.insert(instance.to_string(), doc.clone());
693        let scope = self.parameters(doc, instance, values);
694        self.extensions(doc, instance);
695        let mut aliases: Vec<String> = Vec::new();
696        let mut inherited: Vec<Node> = Vec::new();
697        let bases = r.document.metadata.front.get("extends");
698        if bases.is_some() && !bases.is_some_and(Value::is_array) {
699            self.diag(
700                "invalid-metadata",
701                Severity::Error,
702                "extends is a list of base records: { uri, as, mode, sha256, version, select, with }".into(),
703                uri.clone(),
704                front_line(r),
705            );
706        }
707        if let Some(Value::Array(list)) = bases {
708            for b in list {
709                let u = b.get("uri").and_then(Value::as_str);
710                let alias = b.get("as").and_then(Value::as_str).filter(|a| !a.is_empty());
711                let (Some(u), Some(alias)) = (u, alias) else {
712                    self.diag(
713                        "invalid-metadata",
714                        Severity::Error,
715                        "each base in extends has a uri and an alias (as)".into(),
716                        uri.clone(),
717                        front_line(r),
718                    );
719                    continue;
720                };
721                if aliases.iter().any(|a| a == alias) {
722                    self.diag(
723                        "duplicate-id",
724                        Severity::Error,
725                        format!("the alias \"{alias}\" is used twice in {}", doc.uri),
726                        uri.clone(),
727                        front_line(r),
728                    );
729                    continue;
730                }
731                aliases.push(alias.to_string());
732                let rf = ImportRef {
733                    uri: u.to_string(),
734                    alias: alias.to_string(),
735                    mode: b.get("mode").cloned(),
736                    sha256: b.get("sha256").cloned(),
737                    version: b.get("version").cloned(),
738                    select_value: b.get("select").cloned(),
739                    required: true,
740                    with: b.get("with").and_then(Value::as_object).cloned().unwrap_or_default(),
741                    inherit: true,
742                    line: front_line(r),
743                };
744                if let Some(nodes) = self.import_source(doc, trail, instance, &rf) {
745                    inherited.extend(nodes);
746                }
747            }
748        }
749        let mut local = Vec::new();
750        for node in &r.document.body {
751            if node.is_directive() && matches!(node.kind.as_str(), "replace" | "extend" | "remove") {
752                self.patch(doc, instance, &mut inherited, node, &scope);
753                continue;
754            }
755            // (S29 §5: an allowance with an inherited allowance's id narrows it, and takes its place)
756            if node.is_directive()
757                && node.kind == "allowance"
758                && let Some(id) = node.attrs.get("id").and_then(Value::as_str)
759                && let Some(path) = find_kind(&inherited, "allowance", id)
760            {
761                let stamped = stamp(node, instance, &scope);
762                let (index, parent_path) = path.split_last().map(|(i, p)| (*i, p.to_vec())).unwrap_or((0, Vec::new()));
763                let before = siblings_at(&mut inherited, &parent_path).map(|sib| sib[index].attrs.clone());
764                if let Some(before) = before {
765                    self.widened(&before, &stamped.attrs, id, where_(doc, instance), node.range.map_or(0, |r| r.start));
766                    if let Some(sib) = siblings_at(&mut inherited, &parent_path) {
767                        sib[index] = stamped;
768                    }
769                    continue;
770                }
771            }
772            local.push(stamp(node, instance, &scope));
773        }
774        let included = self.includes(doc, trail, instance, local, &mut aliases);
775        inherited.extend(included);
776        Some(inherited)
777    }
778
779    /// Replaces each `::include` in nodes (at any depth) with what it selects; one that cannot be resolved stays.
780    fn includes(&mut self, doc: &Rc<Loaded>, trail: &[String], instance: &str, nodes: Vec<Node>, aliases: &mut Vec<String>) -> Vec<Node> {
781        let mut out = Vec::new();
782        for mut n in nodes {
783            if n.is_directive() && n.kind == "include" {
784                let src = n.attrs.get("src").and_then(Value::as_str).map(str::to_string);
785                let alias = n.attrs.get("as").and_then(Value::as_str).unwrap_or("").to_string();
786                let Some(src) = src.filter(|_| !alias.is_empty()) else {
787                    // (the reader reported it)
788                    out.push(n);
789                    continue;
790                };
791                let line = n.range.map_or(0, |r| r.start);
792                if aliases.contains(&alias) {
793                    self.diag(
794                        "duplicate-id",
795                        Severity::Error,
796                        format!("the alias \"{alias}\" is used twice in {}", doc.uri),
797                        where_(doc, instance),
798                        line,
799                    );
800                    out.push(n);
801                    continue;
802                }
803                aliases.push(alias.clone());
804                let rf = ImportRef {
805                    uri: src,
806                    alias,
807                    mode: n.attrs.get("mode").cloned(),
808                    sha256: n.attrs.get("sha256").cloned(),
809                    version: n.attrs.get("version").cloned(),
810                    select_value: None,
811                    required: n.attrs.get("required") == Some(&Value::Bool(true)),
812                    with: Object::new(),
813                    inherit: false,
814                    line,
815                };
816                match self.import_source(doc, trail, instance, &rf) {
817                    Some(nodes) => out.extend(nodes),
818                    None => out.push(n),
819                }
820                continue;
821            }
822            if n.is_directive()
823                && let Some(children) = n.children.take()
824            {
825                n.children = Some(self.includes(doc, trail, instance, children, aliases));
826            }
827            out.push(n);
828        }
829        out
830    }
831
832    /// Loads a base or an include, checks it against its pin, composes it as `<instance>/<alias>` and selects from it.
833    fn import_source(&mut self, doc: &Rc<Loaded>, trail: &[String], instance: &str, rf: &ImportRef) -> Option<Vec<Node>> {
834        let uri = where_(doc, instance);
835        let line = rf.line;
836        let (what, operation) = if rf.inherit {
837            (format!("the base \"{}\"", rf.alias), "inherit")
838        } else {
839            (format!("the include \"{}\"", rf.alias), "include")
840        };
841        let resolved = resolve_uri(&named(&doc.read, &rf.uri), &doc.uri);
842        let (path, fragment) = split_fragment(&resolved);
843        let path = path.to_string();
844        let missing = |c: &mut Self, message: String| {
845            if rf.required {
846                c.diag("reference-missing", Severity::Error, message, uri.clone(), line);
847            } else {
848                c.diag("reference-optional", Severity::Warning, message, uri.clone(), line);
849                c.partial = true;
850            }
851        };
852        let Some(target) = self.source(&path) else {
853            missing(self, format!("{what}: {} could not be read", rf.uri));
854            return None;
855        };
856        let mode = if is_str(rf.mode.as_ref(), "pinned") { "pinned" } else { "live" };
857        if mode == "pinned" && !is_str(rf.sha256.as_ref(), &target.sha256) {
858            let pin = rf.sha256.as_ref().and_then(Value::as_str).unwrap_or("no digest");
859            self.diag(
860                "pin-mismatch",
861                Severity::Error,
862                format!("{what} is pinned to {pin}, and {} is {}", rf.uri, target.sha256),
863                uri,
864                line,
865            );
866            return None;
867        }
868        if let Some(Value::String(v)) = &rf.version
869            && !target.version.is_empty()
870            && &target.version != v
871        {
872            self.diag(
873                "pin-mismatch",
874                Severity::Error,
875                format!("{what} asks for version {v}, and {} is {}", rf.uri, target.version),
876                uri,
877                line,
878            );
879            return None;
880        }
881        let child = format!("{instance}/{}", rf.alias);
882        let Some(selector) = selector_of(rf.select_value.as_ref(), fragment) else {
883            self.diag(
884                "invalid-attributes",
885                Severity::Error,
886                format!("{what}: a selector is one of id, heading or lines for an instruction document"),
887                uri,
888                line,
889            );
890            return None;
891        };
892        let mut next_trail = trail.to_vec();
893        next_trail.push(doc.uri.clone());
894        let body = if let Some(Selector::Lines(a, b)) = selector {
895            let lines = &target.read.lines;
896            if !(a >= 1.0 && b >= a && b <= lines.len() as f64) {
897                missing(self, format!("{what}: lines {}–{} are outside {}", js_number(a), js_number(b), rf.uri));
898                return None;
899            }
900            let text = lines[a as usize - 1..b as usize].join("\n") + "\n";
901            let fragment_read = read(&text, &ReadOptions { fragment: true, uri: target.uri.clone(), ..ReadOptions::default() });
902            let fragment = Rc::new(Loaded {
903                uri: target.uri.clone(),
904                sha256: target.sha256.clone(),
905                version: target.version.clone(),
906                read: fragment_read,
907            });
908            self.compose(&fragment, &next_trail, &child, &rf.with)?
909        } else {
910            let composed = self.compose(&target, &next_trail, &child, &rf.with);
911            match (&selector, composed) {
912                (Some(s), Some(body)) => match select_from(body, &child, s) {
913                    Some(body) => body,
914                    None => {
915                        missing(self, format!("{what}: {} has nothing that {}", rf.uri, s.describe()));
916                        return None;
917                    }
918                },
919                (_, Some(body)) => body,
920                (_, None) => return None,
921            }
922        };
923        self.dependencies.push(Dependency {
924            uri: rf.uri.clone(),
925            resolved_uri: path,
926            sha256: target.sha256.clone(),
927            mode: mode.into(),
928            version: target.version.clone(),
929            selector: selector.clone(),
930            instance: child.clone(),
931        });
932        self.provenance.push(Provenance {
933            instance: child,
934            uri: target.uri.clone(),
935            selector,
936            operation: operation.into(),
937            ..Provenance::default()
938        });
939        Some(body)
940    }
941
942    /// Applies a patch (§13.2) to the inherited tree: by qualified explicit id, against the tree as it is now.
943    fn patch(&mut self, doc: &Rc<Loaded>, instance: &str, inherited: &mut Vec<Node>, node: &Node, scope: &Object) {
944        let uri = where_(doc, instance);
945        let line = node.range.map_or(0, |r| r.start);
946        let raw = node.attrs.get("target").and_then(Value::as_str).unwrap_or("");
947        let target = raw.strip_prefix('#').unwrap_or(raw);
948        let parts: Vec<&str> = target.split('/').collect();
949        if !raw.starts_with('#') || parts.len() < 2 || parts.contains(&"") {
950            self.diag(
951                "patch-target",
952                Severity::Error,
953                format!(":::{}: its target is an inherited explicit id, #alias/id (it is \"{raw}\")", node.kind),
954                uri,
955                line,
956            );
957            return;
958        }
959        let wanted = format!("{instance}/{}", parts[..parts.len() - 1].join("/"));
960        let Some(path) = find_id(inherited, &wanted, parts[parts.len() - 1]) else {
961            self.diag("patch-target", Severity::Error, format!(":::{}: nothing inherited has the id #{target}", node.kind), uri, line);
962            return;
963        };
964        let (index, parent_path) = path.split_last().map(|(i, p)| (*i, p.to_vec())).unwrap_or((0, Vec::new()));
965        let Some(siblings) = siblings_at(inherited, &parent_path) else { return };
966        let original = siblings[index].clone();
967        match node.kind.as_str() {
968            "remove" => {
969                siblings.remove(index);
970            }
971            "replace" if original.value.is_some() => {
972                let format = original.value.as_ref().map(|v| v.format.clone()).unwrap_or_default();
973                if node.value.as_ref().is_none_or(|v| v.format != format) {
974                    self.diag(
975                        "patch-body",
976                        Severity::Error,
977                        format!(
978                            ":::replace{{target=\"#{target}\"}}: the target is a {} body, so its replacement is one too (format={format})",
979                            format.to_uppercase()
980                        ),
981                        uri,
982                        line,
983                    );
984                    return;
985                }
986                let dest = &mut siblings[index];
987                dest.value = node.value.clone();
988                dest.children = None;
989            }
990            "replace" => {
991                if node.value.is_some() {
992                    self.diag(
993                        "patch-body",
994                        Severity::Error,
995                        format!(":::replace{{target=\"#{target}\"}}: the target is Markdown, so its replacement is Markdown"),
996                        uri,
997                        line,
998                    );
999                    return;
1000                }
1001                let children = stamp_all(node.children(), instance, scope);
1002                let mut kept = Vec::new();
1003                let mut properties: Vec<Node> = Vec::new();
1004                for child in children {
1005                    if child.is_directive() && child.kind == "properties" && child.attrs.get("patch") == Some(&Value::Bool(true)) {
1006                        properties.push(child);
1007                        kept.push(None);
1008                        continue;
1009                    }
1010                    kept.push(Some(child));
1011                }
1012                let dest = &mut siblings[index];
1013                let mut problem = None;
1014                for p in &properties {
1015                    if let Err(message) = apply_properties(dest, p, target) {
1016                        problem = Some(message);
1017                        break;
1018                    }
1019                }
1020                if let Some(message) = problem {
1021                    self.diag("patch-body", Severity::Error, message, uri, line);
1022                    return;
1023                }
1024                dest.children = Some(kept.into_iter().flatten().collect());
1025            }
1026            _ => {
1027                if original.value.is_some() {
1028                    self.diag(
1029                        "patch-body",
1030                        Severity::Error,
1031                        format!(":::extend{{target=\"#{target}\"}}: a structured target is changed with :::replace"),
1032                        uri,
1033                        line,
1034                    );
1035                    return;
1036                }
1037                let children = stamp_all(node.children(), instance, scope);
1038                let dest = &mut siblings[index];
1039                let existing = dest.children.take().unwrap_or_default();
1040                dest.children = Some(if is_str(node.attrs.get("position"), "prepend") {
1041                    children.into_iter().chain(existing).collect()
1042                } else {
1043                    existing.into_iter().chain(children).collect()
1044                });
1045            }
1046        }
1047        if node.kind == "replace" && original.kind == "allowance" {
1048            let after = siblings_at(inherited, &parent_path).map(|sib| sib[index].attrs.clone());
1049            if let Some(after) = after {
1050                self.widened(&original.attrs, &after, target, where_(doc, instance), line);
1051            }
1052        }
1053        let reason = node.attrs.get("reason").and_then(Value::as_str).unwrap_or("").to_string();
1054        self.provenance.push(Provenance {
1055            instance: wanted,
1056            uri: doc.uri.clone(),
1057            range: node.range,
1058            selector: None,
1059            operation: node.kind.clone(),
1060            target: target.to_string(),
1061            reason,
1062            modified_by: doc.uri.clone(),
1063            original: Some(original),
1064        });
1065    }
1066
1067    /// The source at a resolved URI, read once; its own problems are reported once, under its URI.
1068    fn source(&mut self, uri: &str) -> Option<Rc<Loaded>> {
1069        if let Some(known) = self.loaded.get(uri) {
1070            return Some(known.clone());
1071        }
1072        let l = (self.lookup)(uri)?;
1073        let mut found = l.read.diagnostics.clone();
1074        found.extend(inline_diagnostics(&l.read));
1075        for mut d in found {
1076            d.uri = l.uri.clone();
1077            self.diagnostics.push(d);
1078        }
1079        self.loaded.insert(uri.to_string(), l.clone());
1080        Some(l)
1081    }
1082
1083    // ---- parameters (§12) ----
1084
1085    /// A source's parameter values: supplied ones checked against their declarations, defaults for the rest.
1086    fn parameters(&mut self, doc: &Loaded, instance: &str, values: &Object) -> Object {
1087        let mut out = Object::new();
1088        let uri = where_(doc, instance);
1089        for p in &doc.read.parameters {
1090            let line = if p.line == 0 { front_line(&doc.read) } else { p.line };
1091            if let Some(given) = values.get(&p.name) {
1092                if !value_fits(p, given) {
1093                    let allowed = p.values.as_ref().map_or(String::new(), |v| format!(" ({})", v.join(", ")));
1094                    self.diag(
1095                        "parameter-invalid",
1096                        Severity::Error,
1097                        format!("the value given for ${{{}}} is not a valid {}{allowed}", p.name, p.param_type),
1098                        uri.clone(),
1099                        line,
1100                    );
1101                    continue;
1102                }
1103                out.insert(p.name.clone(), given.clone());
1104            } else if let Some(d) = &p.default {
1105                out.insert(p.name.clone(), d.clone());
1106            } else if p.required {
1107                self.diag("parameter-missing", Severity::Error, format!("${{{}}} is required and has no value", p.name), uri.clone(), line);
1108            } else if uses_parameter(&doc.read, &p.name) {
1109                self.diag(
1110                    "parameter-optional",
1111                    Severity::Warning,
1112                    format!("${{{}}} has no value, so it stays as written", p.name),
1113                    uri.clone(),
1114                    line,
1115                );
1116            }
1117        }
1118        out
1119    }
1120
1121    /// Declared extensions — no manifest is retrieved here, so an optional binding leaves the result partial and a
1122    /// required one is an error (§15).
1123    fn extensions(&mut self, doc: &Loaded, instance: &str) {
1124        let meta = &doc.read.document.metadata;
1125        for (key, value) in entries(meta.front.get("extensions"), &meta.front_order, "extensions") {
1126            let required = value.get("required") == Some(&Value::Bool(true));
1127            let id = match value.get("id") {
1128                Some(v) if !v.is_null() => js_value(Some(v)),
1129                _ => key.clone(),
1130            };
1131            if required {
1132                self.diag(
1133                    "extension-unavailable",
1134                    Severity::Error,
1135                    format!("the extension {id} (\"{key}\") is required, and this resolver binds no extension manifests"),
1136                    where_(doc, instance),
1137                    front_line(&doc.read),
1138                );
1139            } else {
1140                self.partial = true;
1141            }
1142        }
1143    }
1144}
1145
1146/// Applies a `:::properties{patch=true}` inside a replacement: its mapping overrides the target's attributes, never
1147/// its id.
1148fn apply_properties(dest: &mut Node, p: &Node, target: &str) -> Result<(), String> {
1149    let Some(value) = &p.value else {
1150        return Err(format!("the properties patch for #{target} is a mapping of attributes"));
1151    };
1152    let Some(Value::Object(data)) = &value.data else {
1153        return Err(format!("the properties patch for #{target} is a mapping of attributes"));
1154    };
1155    for k in value.order.keys("", data) {
1156        if k == "id" {
1157            return Err(format!("a properties patch cannot change #{target}'s id"));
1158        }
1159        dest.attrs.insert(k.clone(), data[&k].clone());
1160    }
1161    Ok(())
1162}
1163
1164/// `Object.entries` of a mapping (its members in the order written) or a list (by index).
1165fn entries(v: Option<&Value>, order: &KeyOrder, path: &str) -> Vec<(String, Value)> {
1166    match v {
1167        Some(Value::Object(m)) => order.keys(path, m).into_iter().map(|k| (k.clone(), m[&k].clone())).collect(),
1168        Some(Value::Array(list)) => list.iter().enumerate().map(|(i, e)| (i.to_string(), e.clone())).collect(),
1169        _ => Vec::new(),
1170    }
1171}
1172
1173fn stamp_all(nodes: &[Node], instance: &str, scope: &Object) -> Vec<Node> {
1174    nodes.iter().map(|n| stamp(n, instance, scope)).collect()
1175}
1176
1177/// A copy of a node as the instance, its prose and its rules' conditions and reasons with values substituted.
1178fn stamp(node: &Node, instance: &str, scope: &Object) -> Node {
1179    let mut cp = Node { children: None, ..node.clone() };
1180    cp.instance = instance.to_string();
1181    if node.is_markdown() {
1182        if node.prose {
1183            cp.source = substitute(&node.source, scope);
1184        }
1185        return cp;
1186    }
1187    if is_rule(&node.kind) {
1188        for k in ["if", "because"] {
1189            if let Some(Value::String(s)) = cp.attrs.get(k).cloned() {
1190                cp.attrs.insert(k.into(), Value::String(interpolate_values(&s, scope)));
1191            }
1192        }
1193    }
1194    // (S29: an allowance's amounts and window may be parameters, checked once they resolve)
1195    if node.kind == "allowance" {
1196        for k in ["max", "budget", "approve-above", "times", "from", "until", "currency", "per"] {
1197            if let Some(Value::String(s)) = cp.attrs.get(k).cloned() {
1198                cp.attrs.insert(k.into(), Value::String(interpolate_values(&s, scope)));
1199            }
1200        }
1201    }
1202    if let Some(children) = &node.children {
1203        cp.children = Some(stamp_all(children, instance, scope));
1204    }
1205    cp
1206}
1207
1208/// Writes `${name}` in parsed prose (the inline tokenizer's, so never in code, math, URLs or attributes) as its
1209/// value, as data.
1210fn substitute(source: &str, values: &Object) -> String {
1211    let mut out = String::new();
1212    let mut at = 0;
1213    for t in inline_tokens(source) {
1214        if t.token_type != TokenType::Param || t.start < at {
1215            continue;
1216        }
1217        let Some(text) = values.get(&t.name).and_then(value_text) else { continue };
1218        out.push_str(&source[at..t.start]);
1219        out.push_str(&text);
1220        at = t.end;
1221    }
1222    out.push_str(&source[at..]);
1223    out
1224}
1225
1226fn uses_parameter(r: &Reading, name: &str) -> bool {
1227    for n in &r.prose_order {
1228        if inline_tokens(&n.source).iter().any(|t| t.token_type == TokenType::Param && t.name == name) {
1229            return true;
1230        }
1231    }
1232    let reference = format!("${{{name}}}");
1233    fn rule_uses(nodes: &[Node], reference: &str) -> bool {
1234        nodes.iter().filter(|n| n.is_directive()).any(|n| {
1235            is_rule(&n.kind)
1236                && ["if", "because"].iter().any(|k| n.attrs.get(*k).and_then(Value::as_str).is_some_and(|s| s.contains(reference)))
1237                || rule_uses(n.children(), reference)
1238        })
1239    }
1240    rule_uses(&r.document.body, &reference)
1241}
1242
1243// ---- selection (§11.2) ----
1244
1245/// The selector a base's select or a reference's fragment makes: `Some(None)` for none, `None` for one that is no
1246/// selector.
1247fn selector_of(select_value: Option<&Value>, fragment: Option<&str>) -> Option<Option<Selector>> {
1248    if let Some(Value::Object(s)) = select_value {
1249        if let Some(Value::String(id)) = s.get("id")
1250            && s.len() == 1
1251        {
1252            return Some(Some(Selector::Id(id.clone())));
1253        }
1254        if let Some(Value::String(heading)) = s.get("heading")
1255            && s.keys().all(|k| k == "heading" || k == "occurrence")
1256        {
1257            let occurrence = s.get("occurrence").and_then(Value::as_f64);
1258            return Some(Some(Selector::Heading { heading: heading.clone(), occurrence }));
1259        }
1260        if let Some(Value::Array(lines)) = s.get("lines")
1261            && lines.len() == 2
1262            && s.len() == 1
1263            && let (Some(a), Some(b)) = (lines[0].as_f64(), lines[1].as_f64())
1264            && a.fract() == 0.0
1265            && b.fract() == 0.0
1266        {
1267            return Some(Some(Selector::Lines(a, b)));
1268        }
1269        return None;
1270    }
1271    if select_value.is_some() {
1272        return None;
1273    }
1274    let Some(fragment) = fragment.filter(|f| !f.is_empty()) else {
1275        return Some(None);
1276    };
1277    let f = decode_uri_component(fragment);
1278    if let Some(id) = f.strip_prefix("id=") {
1279        return Some(Some(Selector::Id(id.to_string())));
1280    }
1281    if let Some(heading) = f.strip_prefix("heading=") {
1282        return Some(Some(Selector::Heading { heading: heading.to_string(), occurrence: None }));
1283    }
1284    // an ordinary fragment: an explicit id first, then a generated heading anchor
1285    Some(Some(Selector::Id(f)))
1286}
1287
1288struct Rx {
1289    escape_run: Pattern,
1290    atx: Pattern,
1291    code_toggle: Pattern,
1292    heading_brace: Pattern,
1293    heading_id: Pattern,
1294    code_span: Pattern,
1295    link_text: Pattern,
1296    emphasis: Pattern,
1297    space_run: Pattern,
1298    edge_dashes: Pattern,
1299    scheme: Pattern,
1300}
1301
1302static RX: LazyLock<Rx> = LazyLock::new(|| Rx {
1303    escape_run: Pattern::must(r"(?:%[0-9A-Fa-f]{2})+"),
1304    atx: Pattern::must(&format!(r"^ {{0,3}}(#{{1,6}})[ \t]+({JS_DOT}*?)(?:[ \t]+#+)?[ \t]*$")),
1305    code_toggle: Pattern::must(r"^ {0,3}(`{3,}|~{3,})"),
1306    heading_brace: Pattern::must(r"[ \t]\{([^{}]*)\}$"),
1307    heading_id: Pattern::must(&format!(r"(?:^|[{JS_SPACES}])#([A-Za-z0-9][A-Za-z0-9._-]*)")),
1308    code_span: Pattern::must(r"`([^`]*)`"),
1309    link_text: Pattern::must(r"!?\[([^\]]*)\]\([^)]*\)"),
1310    emphasis: Pattern::must(r"[*_~]+"),
1311    space_run: Pattern::must(&format!(r"[{JS_SPACES}]+")),
1312    edge_dashes: Pattern::must(r"^-+|-+$"),
1313    scheme: Pattern::must(r"^[A-Za-z][A-Za-z0-9+.-]*:"),
1314});
1315
1316/// Decodes each run of percent-escapes where it can: a run that is not UTF-8, and a stray %, stay as written.
1317fn decode_uri_component(s: &str) -> String {
1318    RX.escape_run.replace_all(s, |m| {
1319        let run = m.get(s, 0).unwrap_or("");
1320        let bytes: Vec<u8> = run
1321            .as_bytes()
1322            .chunks(3)
1323            .filter_map(|c| std::str::from_utf8(&c[1..]).ok().and_then(|h| u8::from_str_radix(h, 16).ok()))
1324            .collect();
1325        String::from_utf8(bytes).unwrap_or_else(|_| run.to_string())
1326    })
1327}
1328
1329/// The selected part of a composed body. An id selects that node and keeps the policies around it (the enclosing
1330/// policy context, §13.1); a heading selects its section of the top-level Markdown.
1331fn select_from(body: Vec<Node>, instance: &str, s: &Selector) -> Option<Vec<Node>> {
1332    match s {
1333        Selector::Id(id) => {
1334            if let Some(found) = select_id(&body, instance, id) {
1335                return Some(found);
1336            }
1337            select_heading(&body, &|h: &Heading| h.id == *id || h.anchor == *id, 1.0)
1338        }
1339        Selector::Heading { heading, occurrence } => select_heading(&body, &|h: &Heading| h.text == *heading, occurrence.unwrap_or(1.0)),
1340        Selector::Lines(..) => None,
1341    }
1342}
1343
1344fn select_id(nodes: &[Node], instance: &str, id: &str) -> Option<Vec<Node>> {
1345    for n in nodes {
1346        if !n.is_directive() {
1347            continue;
1348        }
1349        let within = if n.instance.is_empty() { instance } else { &n.instance };
1350        if is_str(n.attrs.get("id"), id) && within == instance {
1351            return Some(vec![n.clone()]);
1352        }
1353        if let Some(found) = select_id(n.children(), instance, id) {
1354            if n.kind == "policy" {
1355                let mut cp = n.clone();
1356                cp.children = Some(found);
1357                return Some(vec![cp]);
1358            }
1359            return Some(found);
1360        }
1361    }
1362    None
1363}
1364
1365struct Heading {
1366    level: usize,
1367    text: String,
1368    id: String,
1369    anchor: String,
1370    node: usize,
1371    line: usize,
1372}
1373
1374/// A section of the top-level Markdown: from its heading to the next heading of the same level or higher.
1375fn select_heading(body: &[Node], matches: &dyn Fn(&Heading) -> bool, occurrence: f64) -> Option<Vec<Node>> {
1376    let mut headings: Vec<Heading> = Vec::new();
1377    let mut anchors: HashMap<String, usize> = HashMap::new();
1378    for (i, n) in body.iter().enumerate() {
1379        if !n.is_markdown() {
1380            continue;
1381        }
1382        let mut code = false;
1383        for (li, l) in n.source.split('\n').enumerate() {
1384            if RX.code_toggle.is_match(l) {
1385                code = !code;
1386            }
1387            if code {
1388                continue;
1389            }
1390            let Some(m) = RX.atx.captures(l) else { continue };
1391            let content = m.get(l, 2).unwrap_or("");
1392            let mut visible = content.to_string();
1393            let mut id = String::new();
1394            if let Some(attrs) = RX.heading_brace.captures(content) {
1395                visible = js_trim(&content[..attrs.whole().0]).to_string();
1396                let inner = attrs.get(content, 1).unwrap_or("");
1397                if let Some(h) = RX.heading_id.captures(inner) {
1398                    id = h.get(inner, 1).unwrap_or("").to_string();
1399                }
1400            }
1401            let text = plain(&visible);
1402            let mut anchor = slug(&text);
1403            let seen = anchors.get(&anchor).copied().unwrap_or(0);
1404            anchors.insert(anchor.clone(), seen + 1);
1405            if seen > 0 {
1406                anchor = format!("{anchor}-{}", seen + 1);
1407            }
1408            headings.push(Heading { level: m.get(l, 1).map_or(0, str::len), text, id, anchor, node: i, line: li });
1409        }
1410    }
1411    let matched: Vec<&Heading> = headings.iter().filter(|h| matches(h)).collect();
1412    let index = occurrence - 1.0;
1413    if index.fract() != 0.0 || index < 0.0 || index >= matched.len() as f64 {
1414        return None;
1415    }
1416    let hit = matched[index as usize];
1417    let next = headings.iter().find(|h| (h.node > hit.node || h.node == hit.node && h.line > hit.line) && h.level <= hit.level);
1418    let mut out = Vec::new();
1419    for (i, n) in body.iter().enumerate().skip(hit.node) {
1420        if next.is_some_and(|next| i > next.node) {
1421            break;
1422        }
1423        if !n.is_markdown() {
1424            if next.is_none_or(|next| i < next.node) {
1425                out.push(n.clone());
1426            }
1427            continue;
1428        }
1429        let lines: Vec<&str> = n.source.split('\n').collect();
1430        let from = if i == hit.node { hit.line } else { 0 };
1431        let to = match next {
1432            Some(next) if i == next.node => next.line,
1433            _ => lines.len(),
1434        };
1435        let mut part = lines[from.min(to)..to].join("\n");
1436        if !blank(&part) {
1437            if !part.ends_with('\n') {
1438                part.push('\n');
1439            }
1440            let mut cp = n.clone();
1441            cp.source = part;
1442            out.push(cp);
1443        }
1444    }
1445    Some(out)
1446}
1447
1448/// A heading's visible text: inline code, emphasis and links reduced to their text.
1449fn plain(s: &str) -> String {
1450    let s = RX.code_span.replace_all(s, |m| m.get(s, 1).unwrap_or("").to_string());
1451    let s2 = RX.link_text.replace_all(&s, |m| m.get(&s, 1).unwrap_or("").to_string());
1452    js_trim(&RX.emphasis.replace_all(&s2, |_| String::new())).to_string()
1453}
1454
1455/// A heading's generated anchor (§11.2): casefolded, whitespace runs to -, only letters, numbers, _ and -, trimmed.
1456pub fn slug(text: &str) -> String {
1457    let lower = text.to_lowercase();
1458    let dashed = RX.space_run.replace_all(&lower, |_| "-".to_string());
1459    let kept: String = dashed.chars().filter(|c| c.is_alphabetic() || c.is_numeric() || *c == '_' || *c == '-').collect();
1460    let s = RX.edge_dashes.replace_all(&kept, |_| String::new());
1461    if s.is_empty() { "section".into() } else { s }
1462}
1463
1464/// The path (indices through children) to the node of the instance with the explicit id.
1465/// A node of `kind` with `id` in any instance (an inherited allowance, S29 §5), as a path of indices.
1466fn find_kind(nodes: &[Node], kind: &str, id: &str) -> Option<Vec<usize>> {
1467    for (i, n) in nodes.iter().enumerate() {
1468        if !n.is_directive() {
1469            continue;
1470        }
1471        if n.kind == kind && is_str(n.attrs.get("id"), id) {
1472            return Some(vec![i]);
1473        }
1474        if let Some(mut path) = find_kind(n.children(), kind, id) {
1475            path.insert(0, i);
1476            return Some(path);
1477        }
1478    }
1479    None
1480}
1481
1482fn find_id(nodes: &[Node], instance: &str, id: &str) -> Option<Vec<usize>> {
1483    for (i, n) in nodes.iter().enumerate() {
1484        if !n.is_directive() {
1485            continue;
1486        }
1487        if n.instance == instance && is_str(n.attrs.get("id"), id) {
1488            return Some(vec![i]);
1489        }
1490        if let Some(mut path) = find_id(n.children(), instance, id) {
1491            path.insert(0, i);
1492            return Some(path);
1493        }
1494    }
1495    None
1496}
1497
1498/// The sibling list a path's parent holds.
1499fn siblings_at<'n>(nodes: &'n mut Vec<Node>, parent: &[usize]) -> Option<&'n mut Vec<Node>> {
1500    let mut cur = nodes;
1501    for &i in parent {
1502        cur = cur.get_mut(i)?.children.as_mut()?;
1503    }
1504    Some(cur)
1505}
1506
1507// ---- URIs ----
1508
1509/// A named reference's URI (the front matter's references), else the target itself.
1510fn named(r: &Reading, target: &str) -> String {
1511    if RX.scheme.is_match(target) || target.starts_with('.') || target.starts_with('/') || target.contains(['/', '#']) {
1512        return target.to_string();
1513    }
1514    match r.document.metadata.front.get("references").and_then(|refs| refs.get(target)) {
1515        Some(Value::String(s)) => s.clone(),
1516        Some(Value::Object(rec)) => match rec.get("uri") {
1517            Some(Value::String(u)) => u.clone(),
1518            _ => target.to_string(),
1519        },
1520        _ => target.to_string(),
1521    }
1522}
1523
1524/// Resolves a reference against a base (RFC 3986): a URI with a scheme stays; a relative one is merged with the
1525/// base's path (a base without a scheme, `docs/child.md`, resolves as a path).
1526pub fn resolve_uri(reference: &str, base: &str) -> String {
1527    if RX.scheme.is_match(reference) {
1528        return reference.to_string();
1529    }
1530    if RX.scheme.is_match(base) {
1531        return rfc3986(reference, base).unwrap_or_else(|| reference.to_string());
1532    }
1533    let (path, fragment) = split_fragment(reference);
1534    let joined = if path.is_empty() {
1535        without_fragment(base).to_string()
1536    } else if path.starts_with('/') {
1537        path.to_string()
1538    } else {
1539        let b = without_fragment(base);
1540        format!("{}{path}", &b[..b.rfind('/').map_or(0, |i| i + 1)])
1541    };
1542    let mut segments: Vec<&str> = Vec::new();
1543    for s in joined.split('/') {
1544        if s == "." || s.is_empty() && !segments.is_empty() {
1545            continue;
1546        }
1547        if s == ".." {
1548            if segments.last().is_some_and(|l| !l.is_empty()) {
1549                segments.pop();
1550            }
1551            continue;
1552        }
1553        segments.push(s);
1554    }
1555    let mut out = segments.join("/");
1556    if let Some(f) = fragment {
1557        out.push('#');
1558        out.push_str(f);
1559    }
1560    out
1561}
1562
1563/// RFC 3986 §5.2 for a base with a scheme (an opaque base, or a malformed escape, resolves nothing).
1564fn rfc3986(reference: &str, base: &str) -> Option<String> {
1565    let bad_escape = |s: &str| {
1566        let b = s.as_bytes();
1567        (0..b.len()).any(|i| b[i] == b'%' && !(i + 2 < b.len() && b[i + 1].is_ascii_hexdigit() && b[i + 2].is_ascii_hexdigit()))
1568    };
1569    if bad_escape(reference) || bad_escape(base) {
1570        return None;
1571    }
1572    let colon = base.find(':')?;
1573    let scheme = &base[..colon];
1574    let rest = without_fragment(&base[colon + 1..]);
1575    let (rest, base_query) = match rest.split_once('?') {
1576        Some((r, q)) => (r, Some(q)),
1577        None => (rest, None),
1578    };
1579    let (authority, base_path) = match rest.strip_prefix("//") {
1580        Some(r) => match r.find('/') {
1581            Some(i) => (Some(&r[..i]), &r[i..]),
1582            None => (Some(r), ""),
1583        },
1584        None => (None, rest),
1585    };
1586    if authority.is_none() && !base_path.starts_with('/') {
1587        return None; // an opaque base
1588    }
1589    let (rpath, rfragment) = split_fragment(reference);
1590    let (rpath, rquery) = match rpath.split_once('?') {
1591        Some((p, q)) => (p, Some(q)),
1592        None => (rpath, None),
1593    };
1594    let (authority, path, query) = if let Some(r) = rpath.strip_prefix("//") {
1595        let (a, p) = match r.find('/') {
1596            Some(i) => (&r[..i], &r[i..]),
1597            None => (r, ""),
1598        };
1599        (Some(a.to_string()), remove_dot_segments(p), rquery)
1600    } else if rpath.is_empty() {
1601        (authority.map(str::to_string), base_path.to_string(), rquery.or(base_query))
1602    } else if rpath.starts_with('/') {
1603        (authority.map(str::to_string), remove_dot_segments(rpath), rquery)
1604    } else {
1605        let merged = if authority.is_some() && base_path.is_empty() {
1606            format!("/{rpath}")
1607        } else {
1608            format!("{}{rpath}", &base_path[..base_path.rfind('/').map_or(0, |i| i + 1)])
1609        };
1610        (authority.map(str::to_string), remove_dot_segments(&merged), rquery)
1611    };
1612    let mut out = format!("{scheme}:");
1613    if let Some(a) = authority {
1614        out.push_str("//");
1615        out.push_str(&a);
1616    }
1617    out.push_str(&path);
1618    if let Some(q) = query {
1619        out.push('?');
1620        out.push_str(q);
1621    }
1622    if let Some(f) = rfragment {
1623        out.push('#');
1624        out.push_str(f);
1625    }
1626    Some(out)
1627}
1628
1629fn remove_dot_segments(path: &str) -> String {
1630    let mut out: Vec<&str> = Vec::new();
1631    let segments: Vec<&str> = path.split('/').collect();
1632    let n = segments.len();
1633    for (i, s) in segments.iter().enumerate() {
1634        match *s {
1635            "." => {
1636                if i == n - 1 {
1637                    out.push("");
1638                }
1639            }
1640            ".." => {
1641                if out.len() > 1 {
1642                    out.pop();
1643                }
1644                if i == n - 1 {
1645                    out.push("");
1646                }
1647            }
1648            s => out.push(s),
1649        }
1650    }
1651    let joined = out.join("/");
1652    if path.starts_with('/') && !joined.starts_with('/') { format!("/{joined}") } else { joined }
1653}
1654
1655fn split_fragment(uri: &str) -> (&str, Option<&str>) {
1656    match uri.split_once('#') {
1657        Some((p, f)) => (p, Some(f)),
1658        None => (uri, None),
1659    }
1660}
1661
1662fn without_fragment(uri: &str) -> &str {
1663    split_fragment(uri).0
1664}
1665
1666/// One allowance as a host applies it: the document resolved over `sources`, that allowance's attributes with
1667/// parameters given their values, and the diagnostics that name it (target `#id`). `None` when it has none.
1668pub fn allowance_of(text: &str, id: &str, sources: &HashMap<String, Source>, opts: &ResolveOptions) -> Option<(Object, Vec<Diagnostic>)> {
1669    fn find<'n>(nodes: &'n [Node], id: &str) -> Option<&'n Node> {
1670        for n in nodes {
1671            if !n.is_directive() {
1672                continue;
1673            }
1674            if n.kind == "allowance" && is_str(n.attrs.get("id"), id) {
1675                return Some(n);
1676            }
1677            if let Some(f) = find(n.children(), id) {
1678                return Some(f);
1679            }
1680        }
1681        None
1682    }
1683    let r = resolve_with(text, sources, opts);
1684    let node = find(&r.resolved.body, id)?;
1685    let target = format!("#{id}");
1686    Some((node.attrs.clone(), r.diagnostics.into_iter().filter(|d| d.target == target).collect()))
1687}
1688
1689#[cfg(test)]
1690mod tests {
1691    use super::*;
1692
1693    #[test]
1694    fn uris() {
1695        for (r, b, want) in [
1696            ("./base.md", "docs/child.md", "docs/base.md"),
1697            ("../shared/x.md#id=a", "docs/child.md", "shared/x.md#id=a"),
1698            ("./base", "instruction://acme/morning", "instruction://acme/base"),
1699            ("https://example.org/a.md", "instruction://acme/morning", "https://example.org/a.md"),
1700            ("#id=a", "docs/child.md", "docs/child.md#id=a"),
1701            ("/abs/x.md", "docs/child.md", "/abs/x.md"),
1702            ("../b.md", "instruction://local/x/a.md", "instruction://local/b.md"),
1703        ] {
1704            assert_eq!(resolve_uri(r, b), want, "{r} against {b}");
1705        }
1706    }
1707
1708    #[test]
1709    fn slugs() {
1710        for (text, want) in
1711            [("Calendar privacy", "calendar-privacy"), ("Ünïcode & more!", "ünïcode--more"), ("***", "section"), (" -x- ", "x")]
1712        {
1713            assert_eq!(slug(text), want);
1714        }
1715    }
1716}