omgbase_graph/
nodes.rs

1//! Node projection (§2): the Markdown adapter's nodes over each block's
2//! masked raw, 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;
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
143/// The line form of an inline field over one line (already split at the
144/// JavaScript line terminators): `^[ \t]*([a-z][a-z0-9_]*)::[ \t]*([^\n]*?)[ \t]*$`
145/// with `i`. Returns `(key, value, start, end)` with the offsets relative to
146/// the line: `start` after the leading blanks (where the key begins), `end`
147/// where the trimmed value ends (§2.1).
148pub(crate) fn line_field(line: &str) -> Option<(&str, &str, usize, usize)> {
149    let lead = line.len() - line.trim_start_matches([' ', '\t']).len();
150    let rest = &line[lead..];
151    let mut key_end = 0;
152    for (i, c) in rest.char_indices() {
153        let ok = if i == 0 {
154            c.is_ascii_alphabetic()
155        } else {
156            c.is_ascii_alphanumeric() || c == '_'
157        };
158        if !ok {
159            break;
160        }
161        key_end = i + c.len_utf8();
162    }
163    if key_end == 0 {
164        return None;
165    }
166    let key = &rest[..key_end];
167    let after = rest[key_end..].strip_prefix("::")?;
168    let value = after
169        .trim_start_matches([' ', '\t'])
170        .trim_end_matches([' ', '\t']);
171    let end = line.len() - line.trim_end_matches([' ', '\t']).len();
172    Some((key, value, lead, line.len() - end))
173}
174
175fn scan_block(b: &DocBlock<'_>, out: &mut Vec<ProjectedNode>) {
176    let id = b.block_id;
177    // Code is not prose: a code_fence projects nothing; inline code is masked.
178    let scan = if b.kind == BlockKind::CodeFence {
179        String::new()
180    } else {
181        mask_code_bytes(b.raw)
182    };
183    for m in LINK.captures_iter(&scan) {
184        let whole = m.get(0).expect("match");
185        let mut n = ProjectedNode::new(NodeKind::Link, 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    for m in WIKILINK.captures_iter(&scan) {
192        let whole = m.get(0).expect("match");
193        let mut n = ProjectedNode::new(NodeKind::Wikilink, id);
194        n.value = Some(m[1].to_owned());
195        n.span = Some((whole.start(), whole.end()));
196        out.push(n);
197    }
198    if b.kind == BlockKind::Task {
199        let checked = matches!(b.attrs.get("checked"), Some(AttrValue::Bool(true)));
200        let mut n = ProjectedNode::new(NodeKind::Task, id);
201        n.value = Some(b.text.to_owned());
202        n.span = Some((0, b.raw.len()));
203        n.attrs.insert("checked".to_owned(), Json::Bool(checked));
204        out.push(n);
205    }
206    for m in ANCHOR.captures_iter(&scan) {
207        let whole = m.get(0).expect("match");
208        let mut n = ProjectedNode::new(NodeKind::Anchor, id);
209        n.name = Some(m[1].to_owned());
210        n.span = Some((whole.start(), whole.end()));
211        out.push(n);
212    }
213    for m in BRACKETED.captures_iter(&scan) {
214        let whole = m.get(0).expect("match");
215        let mut n = ProjectedNode::new(NodeKind::InlineField, id);
216        n.name = Some(m[1].to_owned());
217        n.value = Some(m[2].to_owned());
218        n.span = Some((whole.start(), whole.end()));
219        out.push(n);
220    }
221    let mut line_start = 0;
222    for line in scan.split(JS_LINE_TERMINATORS) {
223        if let Some((key, value, start, end)) = line_field(line) {
224            let mut n = ProjectedNode::new(NodeKind::InlineField, id);
225            n.name = Some(key.to_owned());
226            n.value = Some(value.to_owned());
227            n.span = Some((line_start + start, line_start + end));
228            out.push(n);
229        }
230        // Every terminator is one byte except U+2028/U+2029 (three); recover
231        // the width from the source.
232        let next = line_start + line.len();
233        line_start = match scan[next..].chars().next() {
234            Some(t) => next + t.len_utf8(),
235            None => next,
236        };
237    }
238    for child in &b.children {
239        scan_block(child, out);
240    }
241}
242
243/// §2.1: the Markdown adapter's nodes over the body blocks in pre-order —
244/// per block, all links, all wikilinks, the task, all anchors, then the
245/// inline fields (bracketed, then line form). Containers are scanned too, so
246/// a feature inside a list item is projected once for the list and once for
247/// the item (§8). Spans are bytes into the block's `raw`.
248#[must_use]
249pub fn project_nodes(blocks: &[DocBlock<'_>]) -> Vec<ProjectedNode> {
250    let mut out = Vec::new();
251    for b in blocks {
252        scan_block(b, &mut out);
253    }
254    out
255}
256
257/// §2.3: `"n_"` + the first 12 hex of
258/// `sha256(doc_id + "|" + block_id + "|" + kind + "|" + ordinal)`.
259#[must_use]
260pub fn node_id(doc_id: &str, block_id: &str, kind: &str, ordinal: u32) -> String {
261    let digest = sha256(format!("{doc_id}|{block_id}|{kind}|{ordinal}").as_bytes());
262    format!("n_{}", &hex(&digest)[..12])
263}
264
265/// A node with its id and ordinal (§2.3).
266#[derive(Clone, Debug, PartialEq, Eq)]
267pub struct NodeRow<'a> {
268    pub node_id: String,
269    /// The count of earlier nodes of the same `(kind, block_id)`.
270    pub ordinal: u32,
271    pub node: &'a ProjectedNode,
272}
273
274/// §2.3: assign ordinals and ids to a document's nodes in list order (the
275/// adapter nodes followed by the section nodes).
276#[must_use]
277pub fn node_rows<'a>(doc_id: &str, nodes: &'a [ProjectedNode]) -> Vec<NodeRow<'a>> {
278    let mut counters: HashMap<(NodeKind, &str), u32> = HashMap::new();
279    nodes
280        .iter()
281        .map(|n| {
282            let ordinal = counters.entry((n.kind, n.block_id.as_str())).or_insert(0);
283            let this = *ordinal;
284            *ordinal += 1;
285            NodeRow {
286                node_id: node_id(doc_id, &n.block_id, n.kind.as_str(), this),
287                ordinal: this,
288                node: n,
289            }
290        })
291        .collect()
292}
293
294#[cfg(test)]
295mod tests {
296    use super::*;
297    use omgbase_format::parse_markdown;
298
299    fn nodes_of(source: &str) -> Vec<ProjectedNode> {
300        let tree = parse_markdown(source);
301        let ids: Vec<String> = (0..DocBlock::count(&tree.children))
302            .map(|i| format!("b_{i}"))
303            .collect();
304        let blocks = DocBlock::from_blocks(&tree.children, &ids);
305        project_nodes(&blocks)
306    }
307
308    /// `(kind, block_id, name, value, span)`.
309    type View<'a> = (
310        NodeKind,
311        &'a str,
312        Option<&'a str>,
313        Option<&'a str>,
314        Option<(usize, usize)>,
315    );
316
317    fn view(nodes: &[ProjectedNode]) -> Vec<View<'_>> {
318        nodes
319            .iter()
320            .map(|n| {
321                (
322                    n.kind,
323                    n.block_id.as_str(),
324                    n.name.as_deref(),
325                    n.value.as_deref(),
326                    n.span,
327                )
328            })
329            .collect()
330    }
331
332    #[test]
333    fn node_id_is_the_sha256_prefix() {
334        let id = node_id("d_0", "b_1", "md:link", 0);
335        assert_eq!(id.len(), 14);
336        assert_eq!(
337            id,
338            format!("n_{}", &hex(&sha256(b"d_0|b_1|md:link|0"))[..12])
339        );
340        assert_ne!(id, node_id("d_0", "b_1", "md:link", 1));
341    }
342
343    #[test]
344    fn links_with_titles_images_and_spans() {
345        let n = nodes_of("See [t](x.md \"title\") and ![alt](img.png)\n");
346        assert_eq!(
347            view(&n),
348            vec![
349                (
350                    NodeKind::Link,
351                    "b_0",
352                    Some("t"),
353                    Some("x.md"),
354                    Some((4, 21))
355                ),
356                (
357                    NodeKind::Link,
358                    "b_0",
359                    Some("alt"),
360                    Some("img.png"),
361                    Some((27, 41))
362                ),
363            ]
364        );
365        assert!(
366            nodes_of("[t](a b)\n").is_empty(),
367            "no space in a destination"
368        );
369        assert!(nodes_of("[t]()\n").is_empty());
370        let n = nodes_of("[](x)\n");
371        assert_eq!(n[0].name.as_deref(), Some(""));
372    }
373
374    #[test]
375    fn spans_are_bytes_into_raw() {
376        let n = nodes_of("héllo [t](x) `é` [[w]]\n");
377        let raw = "héllo [t](x) `é` [[w]]";
378        assert_eq!(
379            n[0].span,
380            Some((raw.find("[t]").unwrap(), raw.find("[t]").unwrap() + 6))
381        );
382        assert_eq!(n[1].kind, NodeKind::Wikilink);
383        assert_eq!(n[1].span, Some((raw.find("[[").unwrap(), raw.len())));
384        let n = nodes_of("- [x] dö it\n");
385        let task = n.iter().find(|n| n.kind == NodeKind::Task).unwrap();
386        assert_eq!(task.span, Some((0, "- [x] dö it".len())));
387    }
388
389    #[test]
390    fn wikilinks_keep_aliases_and_fragments() {
391        let n = nodes_of("[[note|Alias]] [[a#H]] [[b^r]]\n");
392        let values: Vec<&str> = n
393            .iter()
394            .filter(|n| n.kind == NodeKind::Wikilink)
395            .map(|n| n.value.as_deref().unwrap())
396            .collect();
397        assert_eq!(values, ["note|Alias", "a#H", "b^r"]);
398        // `^r` inside the wikilink is also an anchor match.
399        let anchors: Vec<&str> = n
400            .iter()
401            .filter(|n| n.kind == NodeKind::Anchor)
402            .map(|n| n.name.as_deref().unwrap())
403            .collect();
404        assert_eq!(anchors, ["r"]);
405    }
406
407    #[test]
408    fn tasks_project_once_per_nesting_level_of_the_task_only() {
409        let n = nodes_of("- [ ] open\n- [x] done\n");
410        let tasks: Vec<_> = n
411            .iter()
412            .filter(|n| n.kind == NodeKind::Task)
413            .map(|n| {
414                (
415                    n.block_id.as_str(),
416                    n.value.as_deref().unwrap(),
417                    n.attrs["checked"].as_bool().unwrap(),
418                )
419            })
420            .collect();
421        assert_eq!(tasks, [("b_1", "open", false), ("b_2", "done", true)]);
422        assert_eq!(n[0].kind, NodeKind::Task, "the list itself is not a task");
423    }
424
425    #[test]
426    fn anchors() {
427        let n = nodes_of("Para ^ref-1 and ^x_y and ^ (none)\n");
428        assert_eq!(
429            view(&n),
430            vec![
431                (NodeKind::Anchor, "b_0", Some("ref-1"), None, Some((5, 11))),
432                (NodeKind::Anchor, "b_0", Some("x_y"), None, Some((16, 20))),
433            ]
434        );
435    }
436
437    #[test]
438    fn inline_fields_bracketed_then_line_form_with_spans() {
439        let n = nodes_of("key:: two words  \nSee [k2:: v] (k3::\tw )\n");
440        let fields: Vec<_> = n
441            .iter()
442            .filter(|n| n.kind == NodeKind::InlineField)
443            .map(|n| {
444                (
445                    n.name.as_deref().unwrap(),
446                    n.value.as_deref().unwrap(),
447                    n.span.unwrap(),
448                )
449            })
450            .collect();
451        let raw = "key:: two words  \nSee [k2:: v] (k3::\tw )";
452        assert_eq!(
453            fields,
454            [
455                (
456                    "k2",
457                    "v",
458                    (raw.find("[k2").unwrap(), raw.find("[k2").unwrap() + 8)
459                ),
460                ("k3", "w", (raw.find("(k3").unwrap(), raw.len())),
461                ("key", "two words", (0, 15)),
462            ]
463        );
464        // Leading blanks on a continuation line: the span starts at the key.
465        assert_eq!(line_field("  \tkey::  v \t"), Some(("key", "v", 3, 11)));
466        assert_eq!(line_field("k::"), Some(("k", "", 0, 3)));
467        assert_eq!(line_field("- k:: v"), None);
468        assert_eq!(line_field("k: v"), None);
469        let n = nodes_of("first\n  key:: v\n");
470        assert_eq!(n[0].span, Some((8, 15)));
471        // Line form: key at line start only; not after a list marker.
472        assert!(
473            nodes_of("- k:: v\n")
474                .iter()
475                .all(|n| n.kind != NodeKind::InlineField)
476        );
477        // A bracketed field alone on a line is one node.
478        assert_eq!(
479            nodes_of("[k:: v]\n")
480                .iter()
481                .filter(|n| n.kind == NodeKind::InlineField)
482                .count(),
483            1
484        );
485        // Later lines, CRLF and U+2028 terminators.
486        let n = nodes_of("a:: 1\r\nb:: 2\u{2028}c:: 3\n");
487        let spans: Vec<_> = n
488            .iter()
489            .map(|n| (n.name.as_deref().unwrap(), n.span.unwrap()))
490            .collect();
491        assert_eq!(spans, [("a", (0, 5)), ("b", (7, 12)), ("c", (15, 20))]);
492        // Key case preserved; value trimmed.
493        let n = nodes_of("Key_1::   v  \n");
494        assert_eq!(
495            (n[0].name.as_deref(), n[0].value.as_deref(), n[0].span),
496            (Some("Key_1"), Some("v"), Some((0, 11)))
497        );
498        assert_eq!(nodes_of("k::\n")[0].value.as_deref(), Some(""));
499    }
500
501    #[test]
502    fn code_is_not_prose() {
503        assert!(nodes_of("```\n[t](x) [[w]] ^a k:: v\n```\n").is_empty());
504        assert!(nodes_of("see `[t](x)` and `[[w]]`\n").is_empty());
505        let n = nodes_of("`x` [t](y)\n");
506        assert_eq!(n[0].span, Some((4, 10)));
507    }
508
509    #[test]
510    fn containers_project_once_per_level() {
511        let n = nodes_of("- see [t](x)\n");
512        assert_eq!(
513            view(&n),
514            vec![
515                (NodeKind::Link, "b_0", Some("t"), Some("x"), Some((6, 12))),
516                (NodeKind::Link, "b_1", Some("t"), Some("x"), Some((6, 12))),
517            ]
518        );
519        let n = nodes_of("> [[w]]\n");
520        assert_eq!(n[0].block_id, "b_0");
521        assert_eq!(n[0].span, Some((2, 7)));
522        assert_eq!(n[1].block_id, "b_1");
523        assert_eq!(n[1].span, Some((0, 5)));
524    }
525
526    #[test]
527    fn ordinals_count_per_kind_and_block() {
528        let n = nodes_of("[a](x) [b](y) [[w]]\n\n[c](z)\n");
529        let rows = node_rows("d_0", &n);
530        let view: Vec<(NodeKind, &str, u32)> = rows
531            .iter()
532            .map(|r| (r.node.kind, r.node.block_id.as_str(), r.ordinal))
533            .collect();
534        assert_eq!(
535            view,
536            [
537                (NodeKind::Link, "b_0", 0),
538                (NodeKind::Link, "b_0", 1),
539                (NodeKind::Wikilink, "b_0", 0),
540                (NodeKind::Link, "b_1", 0),
541            ]
542        );
543        assert_eq!(rows[0].node_id, node_id("d_0", "b_0", "md:link", 0));
544        assert_eq!(rows[1].node_id, node_id("d_0", "b_0", "md:link", 1));
545        let mut ids: Vec<&str> = rows.iter().map(|r| r.node_id.as_str()).collect();
546        ids.sort_unstable();
547        ids.dedup();
548        assert_eq!(ids.len(), 4);
549    }
550
551    #[test]
552    fn section_shape() {
553        let s = ProjectedNode::section("b_0", "Title", 1, 0, 3);
554        assert_eq!(s.kind, NodeKind::Section);
555        assert_eq!(s.name.as_deref(), Some("Title"));
556        assert_eq!(s.value, None);
557        assert_eq!(s.span, None);
558        assert_eq!(
559            Json::Object(s.attrs.clone()),
560            serde_json::json!({"level": 1, "first_ordinal": 0, "last_ordinal": 3})
561        );
562        assert_eq!(NodeKind::parse("md:section"), Some(NodeKind::Section));
563        assert_eq!(NodeKind::parse("md:x"), None);
564        for k in [
565            NodeKind::Link,
566            NodeKind::Wikilink,
567            NodeKind::Task,
568            NodeKind::Anchor,
569            NodeKind::InlineField,
570            NodeKind::Section,
571        ] {
572            assert_eq!(NodeKind::parse(k.as_str()), Some(k));
573        }
574    }
575}
omgbase_graph/nodes.rs

omgbase_graph/
nodes.rs
