vs_protocol/delta/
mod.rs

1//! Delta operations: encoding, parsing, application, and diffing.
2//!
3//! See `docs/PROTOCOL.md` § "Tree deltas". Five operations:
4//!
5//! | Op      | Wire                                          |
6//! | ------- | --------------------------------------------- |
7//! | Add     | `+<ref>@<parent>[:<pos>] <role> <label> ...`  |
8//! | Remove  | `-<ref>`                                      |
9//! | Update  | `~<ref> <k>=<v> ...`                          |
10//! | Move    | `><ref>@<parent>[:<pos>]`                     |
11//! | Replace | `*<ref>` then indented subtree                |
12//!
13//! The wire encoding is canonical (attributes sorted, ops in source
14//! order); the parser is tolerant.
15
16use std::collections::{BTreeMap, BTreeSet};
17use std::fmt::Write as _;
18
19use crate::codes::{Op, Role};
20use crate::error::{ParseError, Result};
21use crate::tokenize::{quote_label, quote_value, split_indent, strip_quotes, Tokenizer};
22use crate::tree::{Node, Ref, Tree};
23
24/// One delta operation.
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub enum DeltaOp {
27    /// Insert a new leaf node under `parent` at `pos` (or end if `None`).
28    /// `parent == Ref::ROOT` means root level.
29    Add {
30        r: Ref,
31        parent: Ref,
32        pos: Option<u32>,
33        role: Role,
34        label: String,
35        ops: BTreeSet<Op>,
36        attrs: BTreeMap<String, String>,
37    },
38    /// Remove the subtree rooted at `r`.
39    Remove { r: Ref },
40    /// Replace the attribute map at `r` (per `docs/codes.md`, Update is
41    /// attribute-only; for role/label/ops changes use [`DeltaOp::Replace`]).
42    Update {
43        r: Ref,
44        attrs: BTreeMap<String, String>,
45    },
46    /// Reparent or reorder `r` to `parent` at `pos`.
47    Move {
48        r: Ref,
49        parent: Ref,
50        pos: Option<u32>,
51    },
52    /// Blow away the subtree at `r` and install `subtree` in its place.
53    /// `subtree[0].r == r`; the wire-form indents these lines under
54    /// the `*<ref>` header.
55    Replace { r: Ref, subtree: Vec<Node> },
56}
57
58impl DeltaOp {
59    /// The ref this op operates on.
60    #[must_use]
61    pub fn target(&self) -> Ref {
62        match self {
63            Self::Add { r, .. }
64            | Self::Remove { r }
65            | Self::Update { r, .. }
66            | Self::Move { r, .. }
67            | Self::Replace { r, .. } => *r,
68        }
69    }
70}
71
72/// Encode a sequence of delta ops as the wire body.
73#[must_use]
74pub fn encode(ops: &[DeltaOp]) -> String {
75    let mut out = String::new();
76    for op in ops {
77        encode_one(op, &mut out);
78    }
79    out
80}
81
82fn encode_one(op: &DeltaOp, out: &mut String) {
83    match op {
84        DeltaOp::Add {
85            r,
86            parent,
87            pos,
88            role,
89            label,
90            ops,
91            attrs,
92        } => {
93            write!(out, "+{r}@{}", parent.0).expect("write");
94            if let Some(p) = pos {
95                write!(out, ":{p}").expect("write");
96            }
97            write!(out, " {role} {}", quote_label(label)).expect("write");
98            if !ops.is_empty() {
99                out.push(' ');
100                let mut first = true;
101                for op in ops {
102                    if !first {
103                        out.push(',');
104                    }
105                    out.push_str(op.as_str());
106                    first = false;
107                }
108            }
109            for (k, v) in attrs {
110                write!(out, " {k}={}", quote_value(v)).expect("write");
111            }
112            out.push('\n');
113        }
114        DeltaOp::Remove { r } => {
115            writeln!(out, "-{r}").expect("write");
116        }
117        DeltaOp::Update { r, attrs } => {
118            write!(out, "~{r}").expect("write");
119            for (k, v) in attrs {
120                write!(out, " {k}={}", quote_value(v)).expect("write");
121            }
122            out.push('\n');
123        }
124        DeltaOp::Move { r, parent, pos } => {
125            write!(out, ">{r}@{}", parent.0).expect("write");
126            if let Some(p) = pos {
127                write!(out, ":{p}").expect("write");
128            }
129            out.push('\n');
130        }
131        DeltaOp::Replace { r, subtree } => {
132            writeln!(out, "*{r}").expect("write");
133            for node in subtree {
134                encode_subtree_line(node, 1, out);
135            }
136        }
137    }
138}
139
140fn encode_subtree_line(node: &Node, depth: usize, out: &mut String) {
141    for _ in 0..depth {
142        out.push_str("  ");
143    }
144    write!(out, "{} {} {}", node.r, node.role, quote_label(&node.label)).expect("write");
145    if !node.ops.is_empty() {
146        out.push(' ');
147        let mut first = true;
148        for op in &node.ops {
149            if !first {
150                out.push(',');
151            }
152            out.push_str(op.as_str());
153            first = false;
154        }
155    }
156    for (k, v) in &node.attrs {
157        write!(out, " {k}={}", quote_value(v)).expect("write");
158    }
159    out.push('\n');
160    for child in &node.children {
161        encode_subtree_line(child, depth + 1, out);
162    }
163}
164
165/// Parse a delta-op stream into a vector of ops.
166pub fn parse(input: &str) -> Result<Vec<DeltaOp>> {
167    let lines: Vec<&str> = input.lines().collect();
168    let mut idx = 0usize;
169    let mut ops = Vec::new();
170    while idx < lines.len() {
171        let raw = lines[idx];
172        if raw.trim().is_empty() {
173            idx += 1;
174            continue;
175        }
176        let (depth, body) = split_indent(raw);
177        if depth != 0 {
178            return Err(ParseError::IndentJump {
179                from: 0,
180                to: depth,
181                line: idx + 1,
182            });
183        }
184        let sigil = body.chars().next().ok_or(ParseError::MalformedLine {
185            line: idx + 1,
186            message: "empty delta line",
187        })?;
188        match sigil {
189            '+' => {
190                ops.push(parse_add(&body[1..], idx + 1)?);
191                idx += 1;
192            }
193            '-' => {
194                ops.push(parse_remove(&body[1..], idx + 1)?);
195                idx += 1;
196            }
197            '~' => {
198                ops.push(parse_update(&body[1..], idx + 1)?);
199                idx += 1;
200            }
201            '>' => {
202                ops.push(parse_move(&body[1..], idx + 1)?);
203                idx += 1;
204            }
205            '*' => {
206                let (op, consumed) = parse_replace(&lines[idx..], idx + 1)?;
207                ops.push(op);
208                idx += consumed;
209            }
210            _ => {
211                return Err(ParseError::MalformedLine {
212                    line: idx + 1,
213                    message: "unknown delta sigil",
214                });
215            }
216        }
217    }
218    Ok(ops)
219}
220
221fn parse_add(rest: &str, line_no: usize) -> Result<DeltaOp> {
222    let mut tokens = Tokenizer::new(rest);
223    let head = tokens.next().ok_or(ParseError::MalformedLine {
224        line: line_no,
225        message: "missing ref@parent",
226    })?;
227    let (r, parent, pos) = parse_ref_at_parent(head, line_no)?;
228    let role_tok = tokens.next().ok_or(ParseError::MalformedLine {
229        line: line_no,
230        message: "missing role",
231    })?;
232    let label_tok = tokens.next().ok_or(ParseError::MalformedLine {
233        line: line_no,
234        message: "missing label",
235    })?;
236    let role: Role = role_tok.parse()?;
237    let label = strip_quotes(label_tok).to_string();
238
239    let mut ops = BTreeSet::new();
240    let mut attrs = BTreeMap::new();
241    consume_ops_and_attrs(tokens, line_no, &mut ops, &mut attrs)?;
242
243    Ok(DeltaOp::Add {
244        r,
245        parent,
246        pos,
247        role,
248        label,
249        ops,
250        attrs,
251    })
252}
253
254fn parse_remove(rest: &str, line_no: usize) -> Result<DeltaOp> {
255    let trimmed = rest.trim();
256    if trimmed.is_empty() {
257        return Err(ParseError::MalformedLine {
258            line: line_no,
259            message: "missing ref",
260        });
261    }
262    let r: Ref = trimmed.parse()?;
263    Ok(DeltaOp::Remove { r })
264}
265
266fn parse_update(rest: &str, line_no: usize) -> Result<DeltaOp> {
267    let mut tokens = Tokenizer::new(rest);
268    let r_tok = tokens.next().ok_or(ParseError::MalformedLine {
269        line: line_no,
270        message: "missing ref",
271    })?;
272    let r: Ref = r_tok.parse()?;
273    let mut attrs = BTreeMap::new();
274    for tok in tokens {
275        let (k, v) = tok.split_once('=').ok_or(ParseError::InvalidAttribute {
276            raw: tok.to_string(),
277        })?;
278        if k.is_empty() {
279            return Err(ParseError::InvalidAttribute { raw: tok.into() });
280        }
281        attrs.insert(k.to_string(), strip_quotes(v).to_string());
282    }
283    Ok(DeltaOp::Update { r, attrs })
284}
285
286fn parse_move(rest: &str, line_no: usize) -> Result<DeltaOp> {
287    let trimmed = rest.trim();
288    if trimmed.is_empty() {
289        return Err(ParseError::MalformedLine {
290            line: line_no,
291            message: "missing ref@parent",
292        });
293    }
294    let (r, parent, pos) = parse_ref_at_parent(trimmed, line_no)?;
295    Ok(DeltaOp::Move { r, parent, pos })
296}
297
298fn parse_replace(lines: &[&str], header_line_no: usize) -> Result<(DeltaOp, usize)> {
299    let header = &lines[0][1..]; // strip `*`
300    let r: Ref = header.trim().parse()?;
301    let mut consumed = 1;
302    let mut indented_lines: Vec<&str> = Vec::new();
303    while consumed < lines.len() {
304        let raw = lines[consumed];
305        if raw.trim().is_empty() {
306            consumed += 1;
307            continue;
308        }
309        let (depth, _) = split_indent(raw);
310        if depth == 0 {
311            break;
312        }
313        indented_lines.push(raw);
314        consumed += 1;
315    }
316    if indented_lines.is_empty() {
317        return Err(ParseError::MalformedLine {
318            line: header_line_no,
319            message: "Replace missing subtree",
320        });
321    }
322    // Dedent by one level and parse as a tree.
323    let mut dedented = String::new();
324    for l in &indented_lines {
325        let trimmed = l.strip_prefix("  ").unwrap_or(l);
326        dedented.push_str(trimmed);
327        dedented.push('\n');
328    }
329    let subtree = Tree::parse(&dedented)?;
330    if subtree.roots.is_empty() {
331        return Err(ParseError::MalformedLine {
332            line: header_line_no,
333            message: "Replace subtree empty",
334        });
335    }
336    Ok((
337        DeltaOp::Replace {
338            r,
339            subtree: subtree.roots,
340        },
341        consumed,
342    ))
343}
344
345fn parse_ref_at_parent(s: &str, line_no: usize) -> Result<(Ref, Ref, Option<u32>)> {
346    let (r_part, parent_part) = s.split_once('@').ok_or(ParseError::MalformedLine {
347        line: line_no,
348        message: "expected ref@parent",
349    })?;
350    let r: Ref = r_part.parse()?;
351    let (parent_part, pos_part) = match parent_part.split_once(':') {
352        Some((p, q)) => (p, Some(q)),
353        None => (parent_part, None),
354    };
355    let parent: Ref = parent_part.parse()?;
356    let pos = match pos_part {
357        Some(s) => Some(
358            s.parse::<u32>()
359                .map_err(|_| ParseError::InvalidPosition { raw: s.to_string() })?,
360        ),
361        None => None,
362    };
363    Ok((r, parent, pos))
364}
365
366fn consume_ops_and_attrs(
367    tokens: Tokenizer<'_>,
368    _line_no: usize,
369    ops: &mut BTreeSet<Op>,
370    attrs: &mut BTreeMap<String, String>,
371) -> Result<()> {
372    for tok in tokens {
373        if let Some((k, v)) = tok.split_once('=') {
374            if k.is_empty() {
375                return Err(ParseError::InvalidAttribute { raw: tok.into() });
376            }
377            attrs.insert(k.to_string(), strip_quotes(v).to_string());
378        } else {
379            for piece in tok.split(',') {
380                if piece.is_empty() {
381                    return Err(ParseError::InvalidAttribute { raw: tok.into() });
382                }
383                ops.insert(piece.parse::<Op>()?);
384            }
385        }
386    }
387    Ok(())
388}
389
390mod apply;
391mod diff;
392
393#[cfg(test)]
394mod tests;
395
396pub use apply::apply;
397pub use diff::diff;
vs_protocol/delta/mod.rs

vs_protocol/delta/
mod.rs
