vs_protocol/delta/
apply.rs

1//! Apply a [`DeltaOp`] sequence to a [`Tree`].
2
3use crate::error::{ParseError, Result};
4use crate::tree::{Node, Ref, Tree};
5
6use super::DeltaOp;
7
8/// Apply `ops` to a clone of `prev` and return the resulting tree.
9pub fn apply(prev: &Tree, ops: &[DeltaOp]) -> Result<Tree> {
10    let mut tree = prev.clone();
11    for op in ops {
12        apply_one(&mut tree, op)?;
13    }
14    Ok(tree)
15}
16
17fn apply_one(tree: &mut Tree, op: &DeltaOp) -> Result<()> {
18    match op {
19        DeltaOp::Remove { r } => {
20            let _ = take_subtree(tree, *r);
21            Ok(())
22        }
23        DeltaOp::Add {
24            r,
25            parent,
26            pos,
27            role,
28            label,
29            ops,
30            attrs,
31        } => {
32            if find(tree, *r).is_some() {
33                return Err(ParseError::ApplyDuplicateRef(r.0));
34            }
35            let node = Node {
36                r: *r,
37                role: *role,
38                label: label.clone(),
39                ops: ops.clone(),
40                attrs: attrs.clone(),
41                children: Vec::new(),
42            };
43            insert_at(tree, *parent, *pos, node)?;
44            Ok(())
45        }
46        DeltaOp::Update { r, attrs } => {
47            let node = find_mut(tree, *r).ok_or(ParseError::ApplyMissingRef(r.0))?;
48            node.attrs = attrs.clone();
49            Ok(())
50        }
51        DeltaOp::Move { r, parent, pos } => {
52            let node = take_subtree(tree, *r).ok_or(ParseError::ApplyMissingRef(r.0))?;
53            insert_at(tree, *parent, *pos, node)
54        }
55        DeltaOp::Replace { r, subtree } => {
56            if subtree.is_empty() || subtree[0].r != *r {
57                return Err(ParseError::MalformedLine {
58                    line: 0,
59                    message: "Replace subtree root ref mismatch",
60                });
61            }
62            let location = locate(tree, *r);
63            take_subtree(tree, *r).ok_or(ParseError::ApplyMissingRef(r.0))?;
64            let new_node = subtree[0].clone();
65            match location {
66                Some((parent, pos)) => insert_at(tree, parent, Some(pos), new_node),
67                None => Ok(()),
68            }
69        }
70    }
71}
72
73pub(super) fn find(tree: &Tree, r: Ref) -> Option<&Node> {
74    fn walk(node: &Node, r: Ref) -> Option<&Node> {
75        if node.r == r {
76            return Some(node);
77        }
78        for child in &node.children {
79            if let Some(found) = walk(child, r) {
80                return Some(found);
81            }
82        }
83        None
84    }
85    for root in &tree.roots {
86        if let Some(found) = walk(root, r) {
87            return Some(found);
88        }
89    }
90    None
91}
92
93pub(super) fn find_mut(tree: &mut Tree, r: Ref) -> Option<&mut Node> {
94    fn walk(node: &mut Node, r: Ref) -> Option<&mut Node> {
95        if node.r == r {
96            return Some(node);
97        }
98        for child in &mut node.children {
99            if let Some(found) = walk(child, r) {
100                return Some(found);
101            }
102        }
103        None
104    }
105    for root in &mut tree.roots {
106        if let Some(found) = walk(root, r) {
107            return Some(found);
108        }
109    }
110    None
111}
112
113/// Remove the subtree rooted at `r` from `tree` and return it. Returns
114/// `None` if `r` is not present.
115pub(super) fn take_subtree(tree: &mut Tree, r: Ref) -> Option<Node> {
116    if let Some(idx) = tree.roots.iter().position(|n| n.r == r) {
117        return Some(tree.roots.remove(idx));
118    }
119    for root in &mut tree.roots {
120        if let Some(n) = take_from_subtree(root, r) {
121            return Some(n);
122        }
123    }
124    None
125}
126
127fn take_from_subtree(node: &mut Node, r: Ref) -> Option<Node> {
128    if let Some(idx) = node.children.iter().position(|c| c.r == r) {
129        return Some(node.children.remove(idx));
130    }
131    for child in &mut node.children {
132        if let Some(n) = take_from_subtree(child, r) {
133            return Some(n);
134        }
135    }
136    None
137}
138
139/// Locate `r`'s parent and position. `parent` is `Ref::ROOT` for
140/// top-level nodes.
141fn locate(tree: &Tree, r: Ref) -> Option<(Ref, u32)> {
142    if let Some(idx) = tree.roots.iter().position(|n| n.r == r) {
143        return Some((Ref::ROOT, u32::try_from(idx).unwrap_or(u32::MAX)));
144    }
145    for root in &tree.roots {
146        if let Some(loc) = locate_in_subtree(root, r) {
147            return Some(loc);
148        }
149    }
150    None
151}
152
153fn locate_in_subtree(node: &Node, r: Ref) -> Option<(Ref, u32)> {
154    for (i, child) in node.children.iter().enumerate() {
155        if child.r == r {
156            return Some((node.r, u32::try_from(i).unwrap_or(u32::MAX)));
157        }
158        if let Some(loc) = locate_in_subtree(child, r) {
159            return Some(loc);
160        }
161    }
162    None
163}
164
165fn insert_at(tree: &mut Tree, parent: Ref, pos: Option<u32>, node: Node) -> Result<()> {
166    if parent.is_root() {
167        let p = pos.unwrap_or(u32::MAX) as usize;
168        let p = p.min(tree.roots.len());
169        tree.roots.insert(p, node);
170        return Ok(());
171    }
172    let parent_node = find_mut(tree, parent).ok_or(ParseError::ApplyMissingParent(parent.0))?;
173    let p = pos.unwrap_or(u32::MAX) as usize;
174    let p = p.min(parent_node.children.len());
175    parent_node.children.insert(p, node);
176    Ok(())
177}
vs_protocol/delta/apply.rs

vs_protocol/delta/
apply.rs
