omgbase_graph/
nodes.rs

1//! Node projection (§2): the Markdown adapter's nodes over each block's
2//! own, masked text, the `md:section` shape the store appends, ordinals and
3//! `node_id`.
4
5use std::collections::HashMap;
6use std::fmt;
7use std::sync::LazyLock;
8
9use omgbase_format::hash::{hex, sha256};
10use omgbase_format::{AttrValue, BlockKind};
11use omgbase_properties::{DocBlock, line_field, own_text};
12use regex::Regex;
13use serde_json::{Map as JsonMap, Value as Json};
14
15use crate::mask::mask_code_bytes;
16
17/// JavaScript's `\s` (WhiteSpace + LineTerminator), as a regex class body:
18/// the reference's patterns run without the `u` flag, so `\s` is this set,
19/// not Unicode `White_Space` (U+0085 is not in it; U+FEFF is).
20pub(crate) const JS_WS: &str = r"\t\n\x0B\x0C\r \x{A0}\x{1680}\x{2000}-\x{200A}\x{2028}\x{2029}\x{202F}\x{205F}\x{3000}\x{FEFF}";
21
22/// JavaScript's multiline `^`/`$` sit at these line terminators.
23pub(crate) const JS_LINE_TERMINATORS: [char; 4] = ['\n', '\r', '\u{2028}', '\u{2029}'];
24
25/// `\[([^\]]*)\]\(([^)\s]+)(?:\s+"[^"]*")?\)`.
26static LINK: LazyLock<Regex> = LazyLock::new(|| {
27    Regex::new(&format!(
28        r#"\[([^\]]*)\]\(([^){JS_WS}]+)(?:[{JS_WS}]+"[^"]*")?\)"#
29    ))
30    .expect("valid")
31});
32/// `\[\[([^\]]+)\]\]`.
33static WIKILINK: LazyLock<Regex> =
34    LazyLock::new(|| Regex::new(r"\[\[([^\]]+)\]\]").expect("valid"));
35/// `\^([a-zA-Z0-9_-]+)`.
36static ANCHOR: LazyLock<Regex> =
37    LazyLock::new(|| Regex::new(r"\^([a-zA-Z0-9_-]+)").expect("valid"));
38/// The bracketed inline field of `spec/properties` §3.2 (the reference's
39/// `i` flag only widens `[a-z]` to ASCII letters).
40static BRACKETED: LazyLock<Regex> = LazyLock::new(|| {
41    Regex::new(r"[\[(]([A-Za-z][A-Za-z0-9_]*)::[ \t]*([^\]\n)]*?)[ \t]*[\])]").expect("valid")
42});
43
44/// A node kind (§2.1, §2.2).
45#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
46pub enum NodeKind {
47    Link,
48    Wikilink,
49    Task,
50    Anchor,
51    InlineField,
52    Section,
53}
54
55impl NodeKind {
56    /// The `nodes.kind` string.
57    #[must_use]
58    pub const fn as_str(&self) -> &'static str {
59        match self {
60            NodeKind::Link => "md:link",
61            NodeKind::Wikilink => "md:wikilink",
62            NodeKind::Task => "md:task",
63            NodeKind::Anchor => "md:anchor",
64            NodeKind::InlineField => "md:inline_field",
65            NodeKind::Section => "md:section",
66        }
67    }
68
69    /// The inverse of [`NodeKind::as_str`].
70    #[must_use]
71    pub fn parse(s: &str) -> Option<Self> {
72        match s {
73            "md:link" => Some(NodeKind::Link),
74            "md:wikilink" => Some(NodeKind::Wikilink),
75            "md:task" => Some(NodeKind::Task),
76            "md:anchor" => Some(NodeKind::Anchor),
77            "md:inline_field" => Some(NodeKind::InlineField),
78            "md:section" => Some(NodeKind::Section),
79            _ => None,
80        }
81    }
82}
83
84impl fmt::Display for NodeKind {
85    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
86        f.write_str(self.as_str())
87    }
88}
89
90/// One projected node before it has an id (§2.1, §2.2).
91#[derive(Clone, Debug, PartialEq, Eq)]
92pub struct ProjectedNode {
93    pub kind: NodeKind,
94    /// The block the node is anchored to (a real id at ingest).
95    pub block_id: String,
96    pub name: Option<String>,
97    pub value: Option<String>,
98    /// `[start, end)` **byte** offsets into the block's UTF-8 `raw`, or
99    /// `None` (sections).
100    pub span: Option<(usize, usize)>,
101    /// JSON object.
102    pub attrs: JsonMap<String, Json>,
103}
104
105impl ProjectedNode {
106    fn new(kind: NodeKind, block_id: &str) -> Self {
107        Self {
108            kind,
109            block_id: block_id.to_owned(),
110            name: None,
111            value: None,
112            span: None,
113            attrs: JsonMap::new(),
114        }
115    }
116
117    /// §2.2: an `md:section` node for a `sections` row (`name` = the
118    /// heading's text; `attrs = { level, first_ordinal, last_ordinal }`; no
119    /// span).
120    #[must_use]
121    pub fn section(
122        heading_block: &str,
123        text: &str,
124        level: i64,
125        first_ordinal: i64,
126        last_ordinal: i64,
127    ) -> Self {
128        let mut attrs = JsonMap::new();
129        attrs.insert("level".to_owned(), Json::from(level));
130        attrs.insert("first_ordinal".to_owned(), Json::from(first_ordinal));
131        attrs.insert("last_ordinal".to_owned(), Json::from(last_ordinal));
132        Self {
133            kind: NodeKind::Section,
134            block_id: heading_block.to_owned(),
135            name: Some(text.to_owned()),
136            value: None,
137            span: None,
138            attrs,
139        }
140    }
141}
142
143fn scan_block(b: &DocBlock<'_>, out: &mut Vec<ProjectedNode>) {
144    let id = b.block_id;
145    // §1: the block's own text (children blanked — a feature belongs to the
146    // innermost block), then code masked; a code_fence projects nothing. Both
147    // masks keep byte length, so spans index the original `raw`.
148    let scan = if b.kind == BlockKind::CodeFence {
149        String::new()
150    } else {
151        mask_code_bytes(&own_text(b))
152    };
153    for m in LINK.captures_iter(&scan) {
154        let whole = m.get(0).expect("match");
155        let mut n = ProjectedNode::new(NodeKind::Link, id);
156        n.name = Some(m[1].to_owned());
157        n.value = Some(m[2].to_owned());
158        n.span = Some((whole.start(), whole.end()));
159        out.push(n);
160    }
161    for m in WIKILINK.captures_iter(&scan) {
162        let whole = m.get(0).expect("match");
163        let mut n = ProjectedNode::new(NodeKind::Wikilink, id);
164        n.value = Some(m[1].to_owned());
165        n.span = Some((whole.start(), whole.end()));
166        out.push(n);
167    }
168    if b.kind == BlockKind::Task {
169        let checked = matches!(b.attrs.get("checked"), Some(AttrValue::Bool(true)));
170        let mut n = ProjectedNode::new(NodeKind::Task, id);
171        n.value = Some(b.text.to_owned());
172        n.span = Some((0, b.raw.len()));
173        n.attrs.insert("checked".to_owned(), Json::Bool(checked));
174        out.push(n);
175    }
176    for m in ANCHOR.captures_iter(&scan) {
177        let whole = m.get(0).expect("match");
178        let mut n = ProjectedNode::new(NodeKind::Anchor, id);
179        n.name = Some(m[1].to_owned());
180        n.span = Some((whole.start(), whole.end()));
181        out.push(n);
182    }
183    for m in BRACKETED.captures_iter(&scan) {
184        let whole = m.get(0).expect("match");
185        let mut n = ProjectedNode::new(NodeKind::InlineField, id);
186        n.name = Some(m[1].to_owned());
187        n.value = Some(m[2].to_owned());
188        n.span = Some((whole.start(), whole.end()));
189        out.push(n);
190    }
191    // The line form (`spec/properties` §3.2, 1.1: a list marker and a task
192    // checkbox may precede the key); the span runs from the key to the end of
193    // the trimmed value.
194    let mut line_start = 0;
195    for line in scan.split(JS_LINE_TERMINATORS) {
196        if let Some((key, value, start, end)) = line_field(line) {
197            let mut n = ProjectedNode::new(NodeKind::InlineField, id);
198            n.name = Some(key.to_owned());
199            n.value = Some(value.to_owned());
200            n.span = Some((line_start + start, line_start + end));
201            out.push(n);
202        }
203        // Every terminator is one byte except U+2028/U+2029 (three); recover
204        // the width from the source.
205        let next = line_start + line.len();
206        line_start = match scan[next..].chars().next() {
207            Some(t) => next + t.len_utf8(),
208            None => next,
209        };
210    }
211    for child in &b.children {
212        scan_block(child, out);
213    }
214}
215
216/// §2.1: the Markdown adapter's nodes over the body blocks in pre-order —
217/// per block, over its own text, all links, all wikilinks, the task, all
218/// anchors, then the inline fields (bracketed, then line form). A container's
219/// own text excludes its children, so a feature inside a list item is
220/// projected once, for the item (1.1; §8). Spans are bytes into the block's
221/// `raw`.
222#[must_use]
223pub fn project_nodes(blocks: &[DocBlock<'_>]) -> Vec<ProjectedNode> {
224    let mut out = Vec::new();
225    for b in blocks {
226        scan_block(b, &mut out);
227    }
228    out
229}
230
231/// §2.3: `"n_"` + the first 12 hex of
232/// `sha256(doc_id + "|" + block_id + "|" + kind + "|" + ordinal)`.
233#[must_use]
234pub fn node_id(doc_id: &str, block_id: &str, kind: &str, ordinal: u32) -> String {
235    let digest = sha256(format!("{doc_id}|{block_id}|{kind}|{ordinal}").as_bytes());
236    format!("n_{}", &hex(&digest)[..12])
237}
238
239/// A node with its id and ordinal (§2.3).
240#[derive(Clone, Debug, PartialEq, Eq)]
241pub struct NodeRow<'a> {
242    pub node_id: String,
243    /// The count of earlier nodes of the same `(kind, block_id)`.
244    pub ordinal: u32,
245    pub node: &'a ProjectedNode,
246}
247
248/// §2.3: assign ordinals and ids to a document's nodes in list order (the
249/// adapter nodes followed by the section nodes).
250#[must_use]
251pub fn node_rows<'a>(doc_id: &str, nodes: &'a [ProjectedNode]) -> Vec<NodeRow<'a>> {
252    let mut counters: HashMap<(NodeKind, &str), u32> = HashMap::new();
253    nodes
254        .iter()
255        .map(|n| {
256            let ordinal = counters.entry((n.kind, n.block_id.as_str())).or_insert(0);
257            let this = *ordinal;
258            *ordinal += 1;
259            NodeRow {
260                node_id: node_id(doc_id, &n.block_id, n.kind.as_str(), this),
261                ordinal: this,
262                node: n,
263            }
264        })
265        .collect()
266}
267
268#[cfg(test)]
269mod tests {
270    use super::*;
271    use omgbase_format::parse_markdown;
272
273    fn nodes_of(source: &str) -> Vec<ProjectedNode> {
274        let tree = parse_markdown(source);
275        let ids: Vec<String> = (0..DocBlock::count(&tree.children))
276            .map(|i| format!("b_{i}"))
277            .collect();
278        let blocks = DocBlock::from_blocks(&tree.children, &ids);
279        project_nodes(&blocks)
280    }
281
282    /// `(kind, block_id, name, value, span)`.
283    type View<'a> = (
284        NodeKind,
285        &'a str,
286        Option<&'a str>,
287        Option<&'a str>,
288        Option<(usize, usize)>,
289    );
290
291    fn view(nodes: &[ProjectedNode]) -> Vec<View<'_>> {
292        nodes
293            .iter()
294            .map(|n| {
295                (
296                    n.kind,
297                    n.block_id.as_str(),
298                    n.name.as_deref(),
299                    n.value.as_deref(),
300                    n.span,
301                )
302            })
303            .collect()
304    }
305
306    #[test]
307    fn node_id_is_the_sha256_prefix() {
308        let id = node_id("d_0", "b_1", "md:link", 0);
309        assert_eq!(id.len(), 14);
310        assert_eq!(
311            id,
312            format!("n_{}", &hex(&sha256(b"d_0|b_1|md:link|0"))[..12])
313        );
314        assert_ne!(id, node_id("d_0", "b_1", "md:link", 1));
315    }
316
317    #[test]
318    fn links_with_titles_images_and_spans() {
319        let n = nodes_of("See [t](x.md \"title\") and ![alt](img.png)\n");
320        assert_eq!(
321            view(&n),
322            vec![
323                (
324                    NodeKind::Link,
325                    "b_0",
326                    Some("t"),
327                    Some("x.md"),
328                    Some((4, 21))
329                ),
330                (
331                    NodeKind::Link,
332                    "b_0",
333                    Some("alt"),
334                    Some("img.png"),
335                    Some((27, 41))
336                ),
337            ]
338        );
339        assert!(
340            nodes_of("[t](a b)\n").is_empty(),
341            "no space in a destination"
342        );
343        assert!(nodes_of("[t]()\n").is_empty());
344        let n = nodes_of("[](x)\n");
345        assert_eq!(n[0].name.as_deref(), Some(""));
346    }
347
348    #[test]
349    fn spans_are_bytes_into_raw() {
350        let n = nodes_of("héllo [t](x) `é` [[w]]\n");
351        let raw = "héllo [t](x) `é` [[w]]";
352        assert_eq!(
353            n[0].span,
354            Some((raw.find("[t]").unwrap(), raw.find("[t]").unwrap() + 6))
355        );
356        assert_eq!(n[1].kind, NodeKind::Wikilink);
357        assert_eq!(n[1].span, Some((raw.find("[[").unwrap(), raw.len())));
358        let n = nodes_of("- [x] dö it\n");
359        let task = n.iter().find(|n| n.kind == NodeKind::Task).unwrap();
360        assert_eq!(task.span, Some((0, "- [x] dö it".len())));
361    }
362
363    #[test]
364    fn wikilinks_keep_aliases_and_fragments() {
365        let n = nodes_of("[[note|Alias]] [[a#H]] [[b^r]]\n");
366        let values: Vec<&str> = n
367            .iter()
368            .filter(|n| n.kind == NodeKind::Wikilink)
369            .map(|n| n.value.as_deref().unwrap())
370            .collect();
371        assert_eq!(values, ["note|Alias", "a#H", "b^r"]);
372        // `^r` inside the wikilink is also an anchor match.
373        let anchors: Vec<&str> = n
374            .iter()
375            .filter(|n| n.kind == NodeKind::Anchor)
376            .map(|n| n.name.as_deref().unwrap())
377            .collect();
378        assert_eq!(anchors, ["r"]);
379    }
380
381    #[test]
382    fn tasks_project_once_per_nesting_level_of_the_task_only() {
383        let n = nodes_of("- [ ] open\n- [x] done\n");
384        let tasks: Vec<_> = n
385            .iter()
386            .filter(|n| n.kind == NodeKind::Task)
387            .map(|n| {
388                (
389                    n.block_id.as_str(),
390                    n.value.as_deref().unwrap(),
391                    n.attrs["checked"].as_bool().unwrap(),
392                )
393            })
394            .collect();
395        assert_eq!(tasks, [("b_1", "open", false), ("b_2", "done", true)]);
396        assert_eq!(n[0].kind, NodeKind::Task, "the list itself is not a task");
397    }
398
399    #[test]
400    fn anchors() {
401        let n = nodes_of("Para ^ref-1 and ^x_y and ^ (none)\n");
402        assert_eq!(
403            view(&n),
404            vec![
405                (NodeKind::Anchor, "b_0", Some("ref-1"), None, Some((5, 11))),
406                (NodeKind::Anchor, "b_0", Some("x_y"), None, Some((16, 20))),
407            ]
408        );
409    }
410
411    #[test]
412    fn inline_fields_bracketed_then_line_form_with_spans() {
413        let n = nodes_of("key:: two words  \nSee [k2:: v] (k3::\tw )\n");
414        let fields: Vec<_> = n
415            .iter()
416            .filter(|n| n.kind == NodeKind::InlineField)
417            .map(|n| {
418                (
419                    n.name.as_deref().unwrap(),
420                    n.value.as_deref().unwrap(),
421                    n.span.unwrap(),
422                )
423            })
424            .collect();
425        let raw = "key:: two words  \nSee [k2:: v] (k3::\tw )";
426        assert_eq!(
427            fields,
428            [
429                (
430                    "k2",
431                    "v",
432                    (raw.find("[k2").unwrap(), raw.find("[k2").unwrap() + 8)
433                ),
434                ("k3", "w", (raw.find("(k3").unwrap(), raw.len())),
435                ("key", "two words", (0, 15)),
436            ]
437        );
438        // Leading blanks on a continuation line: the span starts at the key.
439        assert_eq!(line_field("  \tkey::  v \t"), Some(("key", "v", 3, 11)));
440        assert_eq!(line_field("k::"), Some(("k", "", 0, 3)));
441        assert_eq!(line_field("k: v"), None);
442        let n = nodes_of("first\n  key:: v\n");
443        assert_eq!(n[0].span, Some((8, 15)));
444        // Line form after a list marker (1.1): the item's node, span from the
445        // key; the list projects nothing.
446        assert_eq!(
447            view(&nodes_of("- k:: v  \n")),
448            vec![(
449                NodeKind::InlineField,
450                "b_1",
451                Some("k"),
452                Some("v"),
453                Some((2, 7))
454            )]
455        );
456        let n = nodes_of("- [ ] due:: fri\n");
457        assert_eq!(
458            view(&n),
459            vec![
460                (
461                    NodeKind::Task,
462                    "b_1",
463                    None,
464                    Some("due:: fri"),
465                    Some((0, 15))
466                ),
467                (
468                    NodeKind::InlineField,
469                    "b_1",
470                    Some("due"),
471                    Some("fri"),
472                    Some((6, 15))
473                ),
474            ]
475        );
476        // A bracketed field alone on a line is one node.
477        assert_eq!(
478            nodes_of("[k:: v]\n")
479                .iter()
480                .filter(|n| n.kind == NodeKind::InlineField)
481                .count(),
482            1
483        );
484        // Later lines, CRLF and U+2028 terminators.
485        let n = nodes_of("a:: 1\r\nb:: 2\u{2028}c:: 3\n");
486        let spans: Vec<_> = n
487            .iter()
488            .map(|n| (n.name.as_deref().unwrap(), n.span.unwrap()))
489            .collect();
490        assert_eq!(spans, [("a", (0, 5)), ("b", (7, 12)), ("c", (15, 20))]);
491        // Key case preserved; value trimmed.
492        let n = nodes_of("Key_1::   v  \n");
493        assert_eq!(
494            (n[0].name.as_deref(), n[0].value.as_deref(), n[0].span),
495            (Some("Key_1"), Some("v"), Some((0, 11)))
496        );
497        assert_eq!(nodes_of("k::\n")[0].value.as_deref(), Some(""));
498    }
499
500    #[test]
501    fn code_is_not_prose() {
502        assert!(nodes_of("```\n[t](x) [[w]] ^a k:: v\n```\n").is_empty());
503        assert!(nodes_of("see `[t](x)` and `[[w]]`\n").is_empty());
504        let n = nodes_of("`x` [t](y)\n");
505        assert_eq!(n[0].span, Some((4, 10)));
506    }
507
508    #[test]
509    fn containers_project_their_own_text_only() {
510        let n = nodes_of("- see [t](x)\n");
511        assert_eq!(
512            view(&n),
513            vec![(NodeKind::Link, "b_1", Some("t"), Some("x"), Some((6, 12)))]
514        );
515        let n = nodes_of("> [[w]]\n");
516        assert_eq!(
517            view(&n),
518            vec![(NodeKind::Wikilink, "b_1", None, Some("w"), Some((0, 5)))]
519        );
520        // Nested: the inner item only, span into its raw.
521        let n = nodes_of("- outer\n  - inner [a](/x.md)\n");
522        assert_eq!(
523            view(&n),
524            vec![(
525                NodeKind::Link,
526                "b_4",
527                Some("a"),
528                Some("/x.md"),
529                Some((8, 18))
530            )]
531        );
532    }
533
534    #[test]
535    fn ordinals_count_per_kind_and_block() {
536        let n = nodes_of("[a](x) [b](y) [[w]]\n\n[c](z)\n");
537        let rows = node_rows("d_0", &n);
538        let view: Vec<(NodeKind, &str, u32)> = rows
539            .iter()
540            .map(|r| (r.node.kind, r.node.block_id.as_str(), r.ordinal))
541            .collect();
542        assert_eq!(
543            view,
544            [
545                (NodeKind::Link, "b_0", 0),
546                (NodeKind::Link, "b_0", 1),
547                (NodeKind::Wikilink, "b_0", 0),
548                (NodeKind::Link, "b_1", 0),
549            ]
550        );
551        assert_eq!(rows[0].node_id, node_id("d_0", "b_0", "md:link", 0));
552        assert_eq!(rows[1].node_id, node_id("d_0", "b_0", "md:link", 1));
553        let mut ids: Vec<&str> = rows.iter().map(|r| r.node_id.as_str()).collect();
554        ids.sort_unstable();
555        ids.dedup();
556        assert_eq!(ids.len(), 4);
557    }
558
559    #[test]
560    fn section_shape() {
561        let s = ProjectedNode::section("b_0", "Title", 1, 0, 3);
562        assert_eq!(s.kind, NodeKind::Section);
563        assert_eq!(s.name.as_deref(), Some("Title"));
564        assert_eq!(s.value, None);
565        assert_eq!(s.span, None);
566        assert_eq!(
567            Json::Object(s.attrs.clone()),
568            serde_json::json!({"level": 1, "first_ordinal": 0, "last_ordinal": 3})
569        );
570        assert_eq!(NodeKind::parse("md:section"), Some(NodeKind::Section));
571        assert_eq!(NodeKind::parse("md:x"), None);
572        for k in [
573            NodeKind::Link,
574            NodeKind::Wikilink,
575            NodeKind::Task,
576            NodeKind::Anchor,
577            NodeKind::InlineField,
578            NodeKind::Section,
579        ] {
580            assert_eq!(NodeKind::parse(k.as_str()), Some(k));
581        }
582    }
583}
omgbase_graph/nodes.rs

omgbase_graph/
nodes.rs
