omgbase_mutate/
tree.rs

1//! The working tree (`spec/mutate/README.md` §1): a document loaded from the
2//! store into mutable blocks that carry their id, raw bytes, trailing trivia,
3//! attrs, children and a render flag. Blocks are addressed by **path** — the
4//! indices from the top level down — because Rust cannot hold a reference to
5//! a block while mutating its siblings; `locate` finds the path, the
6//! accessors resolve it.
7
8use omgbase_format::hash::{hex, sha256};
9use serde_json::{Map, Value};
10
11/// A block of the working tree (§1 `MutBlock`).
12#[derive(Clone, Debug, PartialEq)]
13pub struct MutBlock {
14    pub id: String,
15    /// The spec/format §3 kind name (`blocks.type`).
16    pub kind: String,
17    /// The raw blob's bytes.
18    pub raw: String,
19    /// The trivia blob's bytes, or `""` when `trivia_hash` was `NULL`.
20    pub trivia: String,
21    /// The block's attrs as stored (a JSON object).
22    pub attrs: Map<String, Value>,
23    pub children: Vec<MutBlock>,
24    /// The render flag (§3): `false` when loaded; set by the ops whose
25    /// children changed.
26    pub dirty: bool,
27}
28
29impl MutBlock {
30    /// A childless, clean block with empty attrs.
31    #[must_use]
32    pub fn new(id: &str, kind: &str, raw: &str, trivia: &str) -> Self {
33        Self {
34            id: id.to_owned(),
35            kind: kind.to_owned(),
36            raw: raw.to_owned(),
37            trivia: trivia.to_owned(),
38            attrs: Map::new(),
39            children: Vec::new(),
40            dirty: false,
41        }
42    }
43
44    /// This block and every descendant, pre-order.
45    pub fn iter(&self) -> impl Iterator<Item = &MutBlock> {
46        Walk { stack: vec![self] }
47    }
48
49    /// Whether this block or any descendant is dirty (§3).
50    #[must_use]
51    pub fn has_dirty_descendant(&self) -> bool {
52        self.dirty || self.children.iter().any(MutBlock::has_dirty_descendant)
53    }
54
55    /// Mark this block and its whole subtree clean.
56    pub fn mark_subtree_clean(&mut self) {
57        self.dirty = false;
58        for c in &mut self.children {
59            c.mark_subtree_clean();
60        }
61    }
62
63    /// The ids of this block and every descendant, pre-order.
64    #[must_use]
65    pub fn subtree_ids(&self) -> Vec<String> {
66        self.iter().map(|b| b.id.clone()).collect()
67    }
68}
69
70struct Walk<'a> {
71    stack: Vec<&'a MutBlock>,
72}
73
74impl<'a> Iterator for Walk<'a> {
75    type Item = &'a MutBlock;
76
77    fn next(&mut self) -> Option<Self::Item> {
78        let b = self.stack.pop()?;
79        self.stack.extend(b.children.iter().rev());
80        Some(b)
81    }
82}
83
84/// A document in the working tree (§1 `MutDoc`).
85#[derive(Clone, Debug, PartialEq)]
86pub struct MutDoc {
87    pub doc_id: String,
88    pub path: String,
89    /// `docs.format` (`markdown`).
90    pub format: String,
91    /// `docs.leading_trivia`.
92    pub leading_trivia: String,
93    /// The current revision's frontmatter blob + `docs.frontmatter_trivia`,
94    /// or `None` when the document has no frontmatter.
95    pub frontmatter_raw: Option<String>,
96    /// The top-level blocks.
97    pub children: Vec<MutBlock>,
98}
99
100/// Where a block sits: the indices from the top level down to it. The last
101/// element is its index among its siblings; the prefix is its parent's path
102/// (empty at the top level).
103pub type BlockPath = Vec<usize>;
104
105impl MutDoc {
106    /// A document with no frontmatter and the given top-level blocks.
107    #[must_use]
108    pub fn new(doc_id: &str, path: &str, children: Vec<MutBlock>) -> Self {
109        Self {
110            doc_id: doc_id.to_owned(),
111            path: path.to_owned(),
112            format: "markdown".to_owned(),
113            leading_trivia: String::new(),
114            frontmatter_raw: None,
115            children,
116        }
117    }
118
119    /// Every block at every depth, pre-order.
120    pub fn iter(&self) -> impl Iterator<Item = &MutBlock> {
121        Walk {
122            stack: self.children.iter().rev().collect(),
123        }
124    }
125
126    /// §1: find a block anywhere in the document; its path.
127    #[must_use]
128    pub fn locate(&self, block_id: &str) -> Option<BlockPath> {
129        fn search(list: &[MutBlock], id: &str, path: &mut BlockPath) -> bool {
130            for (i, b) in list.iter().enumerate() {
131                path.push(i);
132                if b.id == id || search(&b.children, id, path) {
133                    return true;
134                }
135                path.pop();
136            }
137            false
138        }
139        let mut path = Vec::new();
140        search(&self.children, block_id, &mut path).then_some(path)
141    }
142
143    /// Whether `block_id` is anywhere in the document.
144    #[must_use]
145    pub fn contains(&self, block_id: &str) -> bool {
146        self.locate(block_id).is_some()
147    }
148
149    /// The sibling list a parent path names (`[]` → the top level).
150    #[must_use]
151    pub fn siblings(&self, parent: &[usize]) -> &Vec<MutBlock> {
152        let mut list = &self.children;
153        for &i in parent {
154            list = &list[i].children;
155        }
156        list
157    }
158
159    /// Mutable [`MutDoc::siblings`].
160    pub fn siblings_mut(&mut self, parent: &[usize]) -> &mut Vec<MutBlock> {
161        let mut list = &mut self.children;
162        for &i in parent {
163            list = &mut list[i].children;
164        }
165        list
166    }
167
168    /// The block at `path`.
169    ///
170    /// # Panics
171    ///
172    /// If `path` is empty or does not name a block.
173    #[must_use]
174    pub fn block(&self, path: &[usize]) -> &MutBlock {
175        let (last, parent) = path.split_last().expect("a block path is non-empty");
176        &self.siblings(parent)[*last]
177    }
178
179    /// Mutable [`MutDoc::block`].
180    ///
181    /// # Panics
182    ///
183    /// If `path` is empty or does not name a block.
184    pub fn block_mut(&mut self, path: &[usize]) -> &mut MutBlock {
185        let (last, parent) = path.split_last().expect("a block path is non-empty");
186        &mut self.siblings_mut(parent)[*last]
187    }
188
189    /// §1 `owner_of`: the block owning the sibling list at `parent`, or
190    /// `None` at the top level.
191    #[must_use]
192    pub fn owner_of(&self, parent: &[usize]) -> Option<&MutBlock> {
193        if parent.is_empty() {
194            None
195        } else {
196            Some(self.block(parent))
197        }
198    }
199
200    /// §1 `mark_container_dirty`: a structural change to a sibling list
201    /// invalidates its owner's raw; the top level needs no marking.
202    pub fn mark_container_dirty(&mut self, parent: &[usize]) {
203        if !parent.is_empty() {
204            self.block_mut(parent).dirty = true;
205        }
206    }
207
208    /// The ids of every block, pre-order.
209    #[must_use]
210    pub fn all_ids(&self) -> Vec<String> {
211        self.iter().map(|b| b.id.clone()).collect()
212    }
213}
214
215/// `hex(sha256(raw))`: the content CAS token (§1.2).
216#[must_use]
217pub fn raw_hash_hex(raw: &str) -> String {
218    hex(&sha256(raw.as_bytes()))
219}
220
221/// The ordered ids of a sibling list.
222#[must_use]
223pub fn child_ids(list: &[MutBlock]) -> Vec<String> {
224    list.iter().map(|b| b.id.clone()).collect()
225}
226
227/// §1.2: `hex(sha256(child ids joined by ","))`.
228#[must_use]
229pub fn parent_children_hash(list: &[MutBlock]) -> String {
230    hex(&sha256(child_ids(list).join(",").as_bytes()))
231}
232
233#[cfg(test)]
234mod tests {
235    use super::*;
236
237    fn nested() -> MutDoc {
238        let mut list = MutBlock::new("l", "list", "- a\n- b", "\n");
239        let mut a = MutBlock::new("a", "list_item", "- a", "");
240        a.children.push(MutBlock::new("p", "paragraph", "a", ""));
241        list.children.push(a);
242        list.children
243            .push(MutBlock::new("b", "list_item", "- b", ""));
244        MutDoc::new(
245            "d_0",
246            "a.md",
247            vec![MutBlock::new("h", "heading", "# H", "\n\n"), list],
248        )
249    }
250
251    #[test]
252    fn locate_returns_paths_and_accessors_resolve_them() {
253        let doc = nested();
254        assert_eq!(doc.locate("h"), Some(vec![0]));
255        assert_eq!(doc.locate("l"), Some(vec![1]));
256        assert_eq!(doc.locate("b"), Some(vec![1, 1]));
257        assert_eq!(doc.locate("p"), Some(vec![1, 0, 0]));
258        assert_eq!(doc.locate("zz"), None);
259        assert_eq!(doc.block(&[1, 0, 0]).raw, "a");
260        assert_eq!(doc.siblings(&[1]).len(), 2);
261        assert_eq!(doc.owner_of(&[1]).map(|b| b.id.as_str()), Some("l"));
262        assert!(doc.owner_of(&[]).is_none());
263        assert_eq!(doc.all_ids(), ["h", "l", "a", "p", "b"]);
264    }
265
266    #[test]
267    fn dirty_marks_propagate_to_ancestors_only_by_query() {
268        let mut doc = nested();
269        assert!(!doc.block(&[1]).has_dirty_descendant());
270        doc.mark_container_dirty(&[1, 0]);
271        assert!(doc.block(&[1, 0]).dirty);
272        assert!(doc.block(&[1]).has_dirty_descendant());
273        assert!(!doc.block(&[1]).dirty);
274        doc.mark_container_dirty(&[]);
275        doc.block_mut(&[1]).mark_subtree_clean();
276        assert!(!doc.block(&[1]).has_dirty_descendant());
277    }
278
279    #[test]
280    fn hashes() {
281        assert_eq!(
282            raw_hash_hex("abc"),
283            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
284        );
285        let doc = nested();
286        assert_eq!(child_ids(&doc.children), ["h", "l"]);
287        assert_eq!(parent_children_hash(&doc.children), raw_hash_hex("h,l"));
288        assert_eq!(parent_children_hash(&[]), raw_hash_hex(""));
289    }
290}
omgbase_mutate/tree.rs

omgbase_mutate/
tree.rs
