mos_core/document.rs
1//! The lowered semantic document graph (manifest §5, §6 stage 2).
2//!
3//! [`Document`] owns every [`Node`] and hands them out through their stable
4//! [`NodeId`]. Each node carries a [`NodeKind`], a [`SourceSpan`], a
5//! [`ContentHash`], a [`StyleId`], and an [`AttrMap`] of [`AttrValue`]s.
6
7use std::collections::{BTreeMap, BTreeSet};
8use std::path::PathBuf;
9use std::sync::Arc;
10
11use crate::{ContentHash, ContentHasher, SourceSpan};
12
13/// Stable identifier for a document node.
14///
15/// Per manifest §5.1, IDs should ideally be derived from
16/// `hash(file path + syntactic position + explicit label + local structure)`
17/// rather than parse order. The MVP 0 lowerer (`mos-eval`) hands out
18/// monotonic IDs through `Document::alloc`; the hash-based derivation is
19/// deferred to MVP 5 when stable IDs become observable through the cache.
20///
21/// # Examples
22///
23/// ```
24/// use mos_core::NodeId;
25///
26/// let root = NodeId(0);
27///
28/// assert_eq!(root.0, 0);
29/// ```
30#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug, Default)]
31pub struct NodeId(pub u64);
32
33/// Identifier for a resolved style bundle.
34///
35/// # Examples
36///
37/// ```
38/// use mos_core::StyleId;
39///
40/// let style = StyleId::default();
41///
42/// assert_eq!(style.0, 0);
43/// ```
44#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug, Default)]
45pub struct StyleId(pub u32);
46
47/// The kinds of nodes Mosaic recognises (manifest §5.1).
48///
49/// # Examples
50///
51/// ```
52/// use mos_core::NodeKind;
53///
54/// let kind = NodeKind::Paragraph;
55///
56/// assert_eq!(kind, NodeKind::Paragraph);
57/// ```
58#[derive(Copy, Clone, Eq, PartialEq, Debug)]
59pub enum NodeKind {
60 Document,
61 Section,
62 Paragraph,
63 Text,
64 Emphasis,
65 Strong,
66 BoldItalic,
67 Math,
68 Equation,
69 /// A captioned container: an image plus a caption paragraph, laid
70 /// out together with the caption beneath. Cross-references via
71 /// `@fig:foo` will target this kind once MVP 3 lands.
72 Figure,
73 /// A raster image (PNG / JPEG in MVP 1.5). The decoded pixel data
74 /// and natural dimensions live on the node's attributes; see the
75 /// `mos-eval` resolver for the exact attribute names.
76 Image,
77 Table,
78 Citation,
79 Reference,
80 /// A `@page(label)` reference to the printed page number of a labelled
81 /// target. Distinct from [`Reference`](Self::Reference) (which resolves to
82 /// a section/figure number): a page reference resolves to where the target
83 /// lands, which is only known after layout, via the resolve↔layout fixpoint
84 /// (issue #72). Carries a `label` attribute and placeholder `text`; layout
85 /// renders the `text` attribute like any inline run.
86 PageReference,
87 Theorem,
88 Footnote,
89 Bibliography,
90 Raw,
91 /// A bullet or numbered list. The `ordered` attribute distinguishes
92 /// the two kinds and child nodes are [`NodeKind::ListItem`]s.
93 List,
94 /// One entry inside a [`NodeKind::List`]. Paragraph children carry item
95 /// text; nested [`NodeKind::List`] children describe deeper levels.
96 ListItem,
97 /// `\\`: a forced line break inside a paragraph. Carries no
98 /// attributes; layout consumes it as a `WordItem::HardBreak`
99 /// sentinel in the inline word stream. A blank-line paragraph
100 /// break is **not** the same node: it ends the paragraph and
101 /// triggers paragraph-spacing leading, whereas `HardBreak` keeps
102 /// the same paragraph and applies normal inter-line leading.
103 HardBreak,
104}
105
106/// A semantic document node (manifest §5.1).
107///
108/// Nodes are allocated only by [`Document::alloc`] / [`Document::alloc_child`]
109/// from a [`NodeSpec`]: the arena assigns the [`NodeId`] and owns the
110/// `content_hash` and `style_id` fields. Those two fields are `pub(crate)`,
111/// which makes the struct literal unconstructible outside this crate, so no
112/// caller can fabricate a node with a fake id or a hand-set hash.
113///
114/// # Examples
115///
116/// ```
117/// use std::path::PathBuf;
118///
119/// use mos_core::{Document, NodeKind, NodeSpec, SourceSpan};
120///
121/// let file = PathBuf::from("main.mos");
122/// let mut doc = Document::new(file.clone());
123/// let id = doc.alloc(NodeSpec::new(NodeKind::Paragraph, SourceSpan::placeholder(file)));
124///
125/// assert_eq!(doc.get(id).map(|node| &node.kind), Some(&NodeKind::Paragraph));
126/// ```
127#[derive(Clone, Debug)]
128pub struct Node {
129 pub id: NodeId,
130 pub kind: NodeKind,
131 pub span: SourceSpan,
132 pub children: Vec<NodeId>,
133 pub attributes: AttrMap,
134 /// Authored subtree hash, computed by `Document::update_content_hashes`.
135 /// Default until that pass runs. `pub(crate)` to seal external construction.
136 pub(crate) content_hash: ContentHash,
137 /// Resolved style slot placeholder; set by the arena, always default
138 /// until styling lands. `pub(crate)` to seal external construction.
139 pub(crate) style_id: StyleId,
140}
141
142impl Node {
143 /// The authored subtree hash from the last
144 /// [`Document::update_content_hashes`] pass, or default if never computed.
145 ///
146 /// This is a snapshot, not a live hash of public attributes. `mos-eval`
147 /// computes it before resolution; later numbering and reference rewrites
148 /// leave it intact. It is not a complete layout or artifact cache key.
149 #[must_use]
150 pub const fn content_hash(&self) -> ContentHash {
151 self.content_hash
152 }
153
154 /// The node's resolved style slot: a placeholder, default until styling
155 /// lands. Read-only: the arena owns this field.
156 #[must_use]
157 pub const fn style_id(&self) -> StyleId {
158 self.style_id
159 }
160}
161
162/// Blueprint for allocating a node in the document arena.
163///
164/// Carries only caller-chosen fields: `kind`, `span`, and `attributes`.
165/// The arena supplies the `id`, empty `children`, and identity/style
166/// placeholders.
167#[derive(Clone, Debug)]
168pub struct NodeSpec {
169 pub kind: NodeKind,
170 pub span: SourceSpan,
171 pub attributes: AttrMap,
172}
173
174impl NodeSpec {
175 /// A spec for a node of `kind` spanning `span`, with no attributes.
176 #[must_use]
177 pub const fn new(kind: NodeKind, span: SourceSpan) -> Self {
178 Self {
179 kind,
180 span,
181 attributes: AttrMap::new(),
182 }
183 }
184
185 /// Attach `attributes` to this spec.
186 #[must_use]
187 pub fn with_attributes(mut self, attributes: AttrMap) -> Self {
188 self.attributes = attributes;
189 self
190 }
191}
192
193/// Attribute map carried on each node. Keys are interned strings in a
194/// later iteration; for now plain `String` keys are fine for the stub.
195pub type AttrMap = BTreeMap<String, AttrValue>;
196
197/// Attribute value carried on a semantic [`Node`].
198///
199/// # Examples
200///
201/// ```
202/// use mos_core::AttrValue;
203///
204/// let value = AttrValue::Str("intro".to_owned());
205///
206/// assert_eq!(value, AttrValue::Str("intro".to_owned()));
207/// ```
208#[derive(Clone, Debug, PartialEq)]
209pub enum AttrValue {
210 Bool(bool),
211 Int(i64),
212 Float(f64),
213 Str(String),
214 List(Vec<Self>),
215 /// A length already resolved to PDF points. The parser carries
216 /// unit-tagged literals (`mm`, `pt`, `em`); the lowerer converts
217 /// them to a single canonical scalar so layout never has to know
218 /// about units.
219 Length(f64),
220 /// Opaque binary payload; currently used to carry decoded raster
221 /// image pixels (RGB8) onto an [`NodeKind::Image`] node so the PDF
222 /// backend can emit them as an Image `XObject` without re-reading the
223 /// source file.
224 ///
225 /// Stored as `Arc<[u8]>` so a node carrying decoded pixels is cheap
226 /// to clone (e.g. across cache boundaries or when the same image
227 /// would otherwise be duplicated through the document graph). The
228 /// layout engine still dedups by resolved path, so most documents
229 /// hold one buffer per image regardless; the `Arc` is insurance
230 /// against accidental copies on the eval → layout boundary.
231 Bytes(Arc<[u8]>),
232}
233
234/// The lowered semantic document graph (manifest §5, §6 stage 2).
235///
236/// Owns every [`Node`] and exposes them through their stable [`NodeId`].
237/// MVP 0 stores nodes in insertion order; the manifest §5.1 hash-derived
238/// IDs land alongside the cache work in MVP 5.
239///
240/// # Examples
241///
242/// ```
243/// use std::path::PathBuf;
244///
245/// use mos_core::{Document, NodeId};
246///
247/// let doc = Document::new(PathBuf::from("main.mos"));
248///
249/// assert_eq!(doc.root, NodeId(0));
250/// ```
251#[derive(Debug)]
252pub struct Document {
253 pub root: NodeId,
254 pub file: PathBuf,
255 nodes: BTreeMap<NodeId, Node>,
256 next_id: u64,
257}
258
259impl Document {
260 /// Create an empty document rooted at `file`. Allocates the
261 /// `Document` root node (`NodeId(0)`) eagerly so callers can append
262 /// children to it immediately.
263 ///
264 /// # Examples
265 ///
266 /// ```
267 /// use std::path::PathBuf;
268 ///
269 /// use mos_core::Document;
270 ///
271 /// let doc = Document::new(PathBuf::from("main.mos"));
272 ///
273 /// assert_eq!(doc.len(), 1);
274 /// ```
275 #[must_use]
276 pub fn new(file: PathBuf) -> Self {
277 let root_id = NodeId(0);
278 let root_node = Node {
279 id: root_id,
280 kind: NodeKind::Document,
281 span: SourceSpan::placeholder(file.clone()),
282 content_hash: ContentHash::default(),
283 style_id: StyleId::default(),
284 children: Vec::new(),
285 attributes: AttrMap::new(),
286 };
287 let mut nodes = BTreeMap::new();
288 nodes.insert(root_id, root_node);
289 Self {
290 root: root_id,
291 file,
292 nodes,
293 next_id: 1,
294 }
295 }
296
297 /// Allocate a node from `spec` in the arena and return its assigned
298 /// [`NodeId`]. The arena fills in the id, an empty `children` list, and
299 /// the default `content_hash`/`style_id` placeholders.
300 ///
301 /// # Examples
302 ///
303 /// ```
304 /// use std::path::PathBuf;
305 ///
306 /// use mos_core::{Document, NodeId, NodeKind, NodeSpec, SourceSpan};
307 ///
308 /// let file = PathBuf::from("main.mos");
309 /// let mut doc = Document::new(file.clone());
310 /// let id = doc.alloc(NodeSpec::new(NodeKind::Paragraph, SourceSpan::placeholder(file)));
311 ///
312 /// assert_eq!(id, NodeId(1));
313 /// ```
314 pub fn alloc(&mut self, spec: NodeSpec) -> NodeId {
315 let id = NodeId(self.next_id);
316 self.next_id += 1;
317 self.nodes.insert(id, Self::node_from_spec(id, spec));
318 id
319 }
320
321 /// Build the arena-owned [`Node`] for `id` from a caller's [`NodeSpec`],
322 /// supplying the fields the caller does not control.
323 fn node_from_spec(id: NodeId, spec: NodeSpec) -> Node {
324 Node {
325 id,
326 kind: spec.kind,
327 span: spec.span,
328 children: Vec::new(),
329 attributes: spec.attributes,
330 content_hash: ContentHash::default(),
331 style_id: StyleId::default(),
332 }
333 }
334
335 /// Allocate a node from `spec` as a child of `parent` and return its
336 /// [`NodeId`].
337 ///
338 /// # Panics
339 ///
340 /// Panics if `parent` is not a node already allocated by this
341 /// `Document`. Silently producing detached nodes would hide lowerer
342 /// bugs in release builds, so this is intentionally a release-time
343 /// assertion rather than a `debug_assert!`.
344 ///
345 /// # Examples
346 ///
347 /// ```
348 /// use std::path::PathBuf;
349 ///
350 /// use mos_core::{Document, NodeKind, NodeSpec, SourceSpan};
351 ///
352 /// let file = PathBuf::from("main.mos");
353 /// let mut doc = Document::new(file.clone());
354 /// let child = doc.alloc_child(doc.root, NodeSpec::new(NodeKind::Paragraph, SourceSpan::placeholder(file)));
355 ///
356 /// assert_eq!(doc.get(doc.root).map(|node| node.children.as_slice()), Some(&[child][..]));
357 /// ```
358 pub fn alloc_child(&mut self, parent: NodeId, spec: NodeSpec) -> NodeId {
359 assert!(
360 self.nodes.contains_key(&parent),
361 "Document::alloc_child: unknown parent {parent:?}"
362 );
363 let child_id = self.alloc(spec);
364 // Safe to index: we just verified the key exists, and `alloc`
365 // doesn't remove existing entries.
366 if let Some(parent_node) = self.nodes.get_mut(&parent) {
367 parent_node.children.push(child_id);
368 }
369 child_id
370 }
371
372 /// Get a node by id.
373 ///
374 /// # Examples
375 ///
376 /// ```
377 /// use std::path::PathBuf;
378 ///
379 /// use mos_core::{Document, NodeKind};
380 ///
381 /// let doc = Document::new(PathBuf::from("main.mos"));
382 ///
383 /// assert_eq!(doc.get(doc.root).map(|node| node.kind), Some(NodeKind::Document));
384 /// ```
385 #[must_use]
386 pub fn get(&self, id: NodeId) -> Option<&Node> {
387 self.nodes.get(&id)
388 }
389
390 /// Mutable accessor for a single node. Used by the resolver
391 /// (manifest §6 stage 3) to back-patch attributes like `number`
392 /// onto sections and `text` onto `@label` references.
393 ///
394 /// # Examples
395 ///
396 /// ```
397 /// use std::path::PathBuf;
398 ///
399 /// use mos_core::{AttrValue, Document};
400 ///
401 /// let mut doc = Document::new(PathBuf::from("main.mos"));
402 /// if let Some(root) = doc.get_mut(doc.root) {
403 /// root.attributes.insert("title".to_owned(), AttrValue::Str("Demo".to_owned()));
404 /// }
405 ///
406 /// assert!(doc.get(doc.root).is_some_and(|node| node.attributes.contains_key("title")));
407 /// ```
408 #[must_use]
409 pub fn get_mut(&mut self, id: NodeId) -> Option<&mut Node> {
410 self.nodes.get_mut(&id)
411 }
412
413 /// Iterate over every node in the arena in insertion order.
414 ///
415 /// # Examples
416 ///
417 /// ```
418 /// use std::path::PathBuf;
419 ///
420 /// use mos_core::{Document, NodeKind};
421 ///
422 /// let doc = Document::new(PathBuf::from("main.mos"));
423 /// let kinds: Vec<NodeKind> = doc.nodes().map(|node| node.kind).collect();
424 ///
425 /// assert_eq!(kinds, vec![NodeKind::Document]);
426 /// ```
427 pub fn nodes(&self) -> impl Iterator<Item = &Node> {
428 self.nodes.values()
429 }
430
431 /// Compute each node's content hash from its own semantic inputs and its
432 /// ordered child hashes. The caller supplies the hash of the node's kind,
433 /// authored attributes, and external inputs; this crate owns graph traversal
434 /// and subtree framing. IDs, spans, and previous hashes are not folded here.
435 ///
436 /// Hashes are snapshots: after changing authored inputs, the caller must
437 /// run this pass again with the appropriate projection. Resolvers may keep
438 /// the original hashes while adding derived attributes.
439 ///
440 /// # Panics
441 ///
442 /// Panics if children contain a cycle or refer to an unallocated node.
443 /// These are document-construction bugs, not source-document errors.
444 pub fn update_content_hashes(&mut self, mut own_content: impl FnMut(&Node) -> ContentHash) {
445 let mut hashes = BTreeMap::<NodeId, ContentHash>::new();
446 let mut active = BTreeSet::new();
447 // Iterative postorder also handles shared children, detached nodes,
448 // and children allocated before their parent without recursion.
449 for &id in self.nodes.keys() {
450 if hashes.contains_key(&id) {
451 continue;
452 }
453 let mut pending = vec![(id, false)];
454 while let Some((id, exiting)) = pending.pop() {
455 if hashes.contains_key(&id) {
456 continue;
457 }
458 let node = &self.nodes[&id];
459 if exiting {
460 let mut hasher = ContentHasher::new();
461 hasher
462 .field(b"mos-core/semantic-subtree/v1")
463 .field(&own_content(node).0.to_le_bytes());
464 for child in &node.children {
465 hasher.field(&hashes[child].0.to_le_bytes());
466 }
467 hashes.insert(id, hasher.finish());
468 active.remove(&id);
469 } else {
470 assert!(
471 active.insert(id),
472 "Document::update_content_hashes: cycle at {id:?}"
473 );
474 pending.push((id, true));
475 pending.extend(node.children.iter().rev().map(|&child| (child, false)));
476 }
477 }
478 }
479 for (id, node) in &mut self.nodes {
480 node.content_hash = hashes[id];
481 }
482 }
483
484 /// Total number of nodes including the document root.
485 ///
486 /// # Examples
487 ///
488 /// ```
489 /// use std::path::PathBuf;
490 ///
491 /// use mos_core::Document;
492 ///
493 /// let doc = Document::new(PathBuf::from("main.mos"));
494 ///
495 /// assert_eq!(doc.len(), 1);
496 /// ```
497 #[must_use]
498 pub fn len(&self) -> usize {
499 self.nodes.len()
500 }
501
502 /// Return whether the document has no semantic content beyond the root.
503 ///
504 /// # Examples
505 ///
506 /// ```
507 /// use std::path::PathBuf;
508 ///
509 /// use mos_core::Document;
510 ///
511 /// let doc = Document::new(PathBuf::from("main.mos"));
512 ///
513 /// assert!(doc.is_empty());
514 /// ```
515 #[must_use]
516 pub fn is_empty(&self) -> bool {
517 // The root always exists, so `Document` is never truly empty;
518 // expose the conventional method anyway for clippy compliance.
519 self.len() <= 1
520 }
521}
522
523#[cfg(test)]
524mod tests {
525 use super::*;
526
527 #[test]
528 fn content_hashes_follow_child_order_and_ignore_allocation_order() {
529 fn graph(reverse_allocation: bool) -> (Document, NodeId, NodeId) {
530 let mut document = Document::new(PathBuf::from("test.mos"));
531 let spec = || {
532 NodeSpec::new(
533 NodeKind::Text,
534 SourceSpan::placeholder(document.file.clone()),
535 )
536 };
537 let a_spec = spec();
538 let b_spec = spec();
539 let (a, b) = if reverse_allocation {
540 let b = document.alloc(b_spec);
541 (document.alloc(a_spec), b)
542 } else {
543 (document.alloc(a_spec), document.alloc(b_spec))
544 };
545 document.get_mut(document.root).unwrap().children = vec![a, b, a];
546 (document, a, b)
547 }
548 fn hash(document: &mut Document, a: NodeId, b: NodeId) {
549 document.update_content_hashes(|node| {
550 ContentHasher::new()
551 .field(if node.id == a {
552 b"a"
553 } else if node.id == b {
554 b"b"
555 } else {
556 b"root"
557 })
558 .finish()
559 });
560 }
561 let (mut first, a, b) = graph(false);
562 let (mut second, other_a, other_b) = graph(true);
563 hash(&mut first, a, b);
564 hash(&mut second, other_a, other_b);
565 let original = first.get(first.root).unwrap().content_hash();
566 assert_ne!(original, ContentHash::default());
567 assert_eq!(original, second.get(second.root).unwrap().content_hash());
568 let child_hash = first.get(a).unwrap().content_hash();
569 first.get_mut(first.root).unwrap().children.swap(0, 1);
570 hash(&mut first, a, b);
571 assert_ne!(original, first.get(first.root).unwrap().content_hash());
572 assert_eq!(child_hash, first.get(a).unwrap().content_hash());
573 }
574
575 #[test]
576 fn content_hashes_support_older_children_and_deep_graphs() {
577 let mut document = Document::new(PathBuf::from("test.mos"));
578 let mut child = document.alloc(NodeSpec::new(
579 NodeKind::Text,
580 SourceSpan::placeholder(document.file.clone()),
581 ));
582 for _ in 0..4_000 {
583 let parent = document.alloc(NodeSpec::new(
584 NodeKind::Paragraph,
585 SourceSpan::placeholder(document.file.clone()),
586 ));
587 document.get_mut(parent).unwrap().children.push(child);
588 child = parent;
589 }
590 document
591 .get_mut(document.root)
592 .unwrap()
593 .children
594 .push(child);
595 let mut visits = BTreeSet::new();
596 document.update_content_hashes(|node| {
597 assert!(visits.insert(node.id), "each node hashed only once");
598 ContentHash(1)
599 });
600 assert_eq!(visits.len(), document.len());
601 assert!(
602 document
603 .nodes()
604 .all(|node| node.content_hash() != ContentHash::default())
605 );
606 }
607
608 #[test]
609 #[should_panic(expected = "cycle")]
610 fn content_hashes_reject_cycles() {
611 let mut document = Document::new(PathBuf::from("test.mos"));
612 let root = document.root;
613 document.get_mut(root).unwrap().children.push(root);
614 document.update_content_hashes(|_| ContentHash(1));
615 }
616
617 #[test]
618 #[should_panic]
619 fn content_hashes_reject_missing_children() {
620 let mut document = Document::new(PathBuf::from("test.mos"));
621 document
622 .get_mut(document.root)
623 .unwrap()
624 .children
625 .push(NodeId(99));
626 document.update_content_hashes(|_| ContentHash(1));
627 }
628
629 #[test]
630 #[should_panic(expected = "unknown parent")]
631 fn alloc_child_panics_on_unknown_parent() {
632 let mut doc = Document::new(PathBuf::from("test.mos"));
633 // `NodeId(9999)` was never allocated by `doc`; the call must
634 // abort instead of leaking a detached node.
635 doc.alloc_child(
636 NodeId(9999),
637 NodeSpec::new(
638 NodeKind::Text,
639 SourceSpan::placeholder(PathBuf::from("test.mos")),
640 ),
641 );
642 }
643
644 #[test]
645 fn document_alloc_and_traverse() {
646 let mut doc = Document::new(PathBuf::from("test.mos"));
647 let para = doc.alloc_child(
648 doc.root,
649 NodeSpec::new(
650 NodeKind::Paragraph,
651 SourceSpan::placeholder(PathBuf::from("test.mos")),
652 ),
653 );
654 doc.alloc_child(
655 para,
656 NodeSpec::new(
657 NodeKind::Text,
658 SourceSpan::placeholder(PathBuf::from("test.mos")),
659 ),
660 );
661 assert_eq!(doc.len(), 3);
662 assert_eq!(doc.get(doc.root).unwrap().children.len(), 1);
663 assert_eq!(doc.get(para).unwrap().children.len(), 1);
664 }
665}