Skip to main content

vibe/
ast_merge.rs

1//! 3-Way AST Structural Merge for VibeScript.
2//!
3//! Reconciles concurrent edits from the visual Studio canvas (`ours`) and the textual
4//! code editor (`theirs`) against a shared ancestor AST (`base`). Non-conflicting additions,
5//! modifications, and property edits are merged deterministically.
6
7use crate::ast::*;
8
9/// Result of a 3-way AST merge operation.
10#[derive(Debug, Clone)]
11pub struct MergeResult {
12    /// Merged program AST.
13    pub program: Program,
14    /// Any structural conflicts detected during merge.
15    pub conflicts: Vec<MergeConflict>,
16}
17
18/// A conflict where two branches modified the same AST node incompatibly.
19#[derive(Debug, Clone, PartialEq)]
20pub struct MergeConflict {
21    pub path: String,
22    pub description: String,
23    pub our_change: String,
24    pub their_change: String,
25}
26
27/// Perform a 3-way structural merge on VibeScript programs.
28pub fn merge_programs(base: &Program, ours: &Program, theirs: &Program) -> MergeResult {
29    let mut conflicts = Vec::new();
30    let mut merged_items = Vec::new();
31
32    // Index base, ours, and theirs items by key (Item kind + identifier)
33    let base_map = index_items(&base.items);
34    let mut our_map = index_items(&ours.items);
35    let mut their_map = index_items(&theirs.items);
36
37    // Deterministic key order: preserve appearance order across base -> ours -> theirs.
38    let mut all_keys: Vec<String> = Vec::new();
39    for item in base
40        .items
41        .iter()
42        .chain(ours.items.iter())
43        .chain(theirs.items.iter())
44    {
45        let key = item_key(item);
46        if !all_keys.contains(&key) {
47            all_keys.push(key);
48        }
49    }
50
51    for key in &all_keys {
52        let base_item = find_indexed_item(&base_map, key);
53        let our_item = take_indexed_item(&mut our_map, key);
54        let their_item = take_indexed_item(&mut their_map, key);
55
56        match (base_item, our_item, their_item) {
57            // Unchanged in both
58            (Some(b), Some(o), Some(t)) if items_equal(b, o) && items_equal(b, t) => {
59                merged_items.push((*b).clone());
60            }
61            // Modified only in ours
62            (Some(b), Some(o), Some(t)) if items_equal(b, t) && !items_equal(b, o) => {
63                merged_items.push(o.clone());
64            }
65            // Modified only in theirs
66            (Some(b), Some(o), Some(t)) if items_equal(b, o) && !items_equal(b, t) => {
67                merged_items.push(t.clone());
68            }
69            // Modified identically in both
70            (Some(_), Some(o), Some(t)) if items_equal(o, t) => {
71                merged_items.push(o.clone());
72            }
73            // Modified incompatibly in both -> Conflict (choose ours, record conflict)
74            (Some(_), Some(o), Some(t)) => {
75                conflicts.push(MergeConflict {
76                    path: key.clone(),
77                    description: "Conflicting modifications to item".to_string(),
78                    our_change: format!("{o:?}"),
79                    their_change: format!("{t:?}"),
80                });
81                merged_items.push(o.clone());
82            }
83            // Added only in ours
84            (None, Some(o), None) => {
85                merged_items.push(o.clone());
86            }
87            // Added only in theirs
88            (None, None, Some(t)) => {
89                merged_items.push(t.clone());
90            }
91            // Added identically in both
92            (None, Some(o), Some(t)) if items_equal(o, t) => {
93                merged_items.push(o.clone());
94            }
95            // Added differently in both -> Conflict
96            (None, Some(o), Some(t)) => {
97                conflicts.push(MergeConflict {
98                    path: key.clone(),
99                    description: "Conflicting additions with same identifier".to_string(),
100                    our_change: format!("{o:?}"),
101                    their_change: format!("{t:?}"),
102                });
103                merged_items.push(o.clone());
104            }
105            // Deleted in ours, unchanged in theirs -> Delete
106            (Some(b), None, Some(t)) if items_equal(b, t) => {}
107            // Deleted in theirs, unchanged in ours -> Delete
108            (Some(b), Some(o), None) if items_equal(b, o) => {}
109            // Deleted in both -> Delete
110            (Some(_), None, None) => {}
111            // Deleted in one, modified in the other -> Conflict
112            (Some(_), Some(o), None) => {
113                conflicts.push(MergeConflict {
114                    path: key.clone(),
115                    description: "Item deleted in theirs but modified in ours".to_string(),
116                    our_change: format!("{o:?}"),
117                    their_change: "deleted".to_string(),
118                });
119                merged_items.push(o.clone());
120            }
121            (Some(_), None, Some(t)) => {
122                conflicts.push(MergeConflict {
123                    path: key.clone(),
124                    description: "Item deleted in ours but modified in theirs".to_string(),
125                    our_change: "deleted".to_string(),
126                    their_change: format!("{t:?}"),
127                });
128                merged_items.push(t.clone());
129            }
130            (None, None, None) => {}
131        }
132    }
133
134    // Merge imports without duplication
135    let mut merged_imports = ours.imports.clone();
136    for imp in &theirs.imports {
137        if !merged_imports.iter().any(|i| i.path == imp.path) {
138            merged_imports.push(imp.clone());
139        }
140    }
141
142    // Merge requires without duplication
143    let mut merged_requires = ours.requires.clone();
144    for req in &theirs.requires {
145        if !merged_requires.iter().any(|r| r.id == req.id) {
146            merged_requires.push(req.clone());
147        }
148    }
149
150    let program = Program {
151        span: ours.span,
152        module: ours.module.clone().or_else(|| theirs.module.clone()),
153        prefixes: ours.prefixes.clone(),
154        locales: ours.locales.clone(),
155        imports: merged_imports,
156        requires: merged_requires,
157        items: merged_items,
158    };
159
160    MergeResult { program, conflicts }
161}
162
163fn item_key(item: &Item) -> String {
164    match item {
165        Item::Const(cd) => format!("const:{}", cd.name),
166        Item::Function(fd) => format!("fn:{}", fd.name),
167        Item::Hook(hd) => format!("on:{}", hd.path.join(".")),
168        Item::Enum(ed) => format!("enum:{}", ed.name),
169        Item::Law(ld) => format!("law:{}", ld.name),
170        Item::Material(md) => format!("material:{}", md.name),
171        Item::Field(fld) => format!("field:{}", fld.name),
172        Item::Cell(cd) => format!("cell:{}", cd.name),
173        Item::Present(pd) => format!("present:{}", pd.name),
174        Item::Bind(b) => format!(
175            "bind:{}",
176            strip_debug_spans(&format!("{:?}<->{:?}", b.left, b.right))
177        ),
178        Item::Statement(stmt) => format!("stmt:{}", strip_debug_spans(&format!("{stmt:?}"))),
179    }
180}
181
182fn index_items(items: &[Item]) -> Vec<(String, &Item)> {
183    let mut indexed = Vec::with_capacity(items.len());
184    for item in items {
185        let key = item_key(item);
186        if let Some(slot) = indexed.iter_mut().find(|(k, _)| *k == key) {
187            slot.1 = item;
188        } else {
189            indexed.push((key, item));
190        }
191    }
192    indexed
193}
194
195fn find_indexed_item<'a>(indexed: &[(String, &'a Item)], key: &str) -> Option<&'a Item> {
196    indexed.iter().find(|(k, _)| k == key).map(|(_, item)| *item)
197}
198
199fn take_indexed_item<'a>(indexed: &mut Vec<(String, &'a Item)>, key: &str) -> Option<&'a Item> {
200    indexed
201        .iter()
202        .position(|(k, _)| k == key)
203        .map(|pos| indexed.swap_remove(pos).1)
204}
205
206fn strip_debug_spans(debug: &str) -> String {
207    let bytes = debug.as_bytes();
208    let mut out = String::with_capacity(debug.len());
209    let mut i = 0;
210    let mut in_str = false;
211    let mut escape = false;
212    while i < bytes.len() {
213        let b = bytes[i];
214        if in_str {
215            out.push(b as char);
216            if escape {
217                escape = false;
218            } else if b == b'\\' {
219                escape = false;
220                if i + 1 < bytes.len() {
221                    out.push(bytes[i + 1] as char);
222                    i += 2;
223                    continue;
224                }
225            } else if b == b'"' {
226                in_str = false;
227            }
228            i += 1;
229            continue;
230        }
231        if b == b'"' {
232            in_str = true;
233            out.push('"');
234            i += 1;
235            continue;
236        }
237        const PREFIX: &[u8] = b"Span { start:";
238        if bytes[i..].starts_with(PREFIX) {
239            if let Some(rel_end) = debug[i..].find('}') {
240                out.push_str("Span");
241                i += rel_end + 1;
242                continue;
243            }
244        }
245        out.push(b as char);
246        i += 1;
247    }
248    out
249}
250
251fn items_equal(a: &Item, b: &Item) -> bool {
252    // Structural span-independent equality check.
253    strip_debug_spans(&format!("{a:?}")) == strip_debug_spans(&format!("{b:?}"))
254}
255
256#[cfg(test)]
257mod tests {
258    use super::*;
259    use crate::parse::parse_program;
260
261    #[test]
262    fn merge_disjoint_additions() {
263        let base = parse_program("const A: i64 = 1;\n").expect("base");
264        let ours = parse_program("const A: i64 = 1;\nconst B: i64 = 2;\n").expect("ours");
265        let theirs = parse_program("const A: i64 = 1;\nconst C: i64 = 3;\n").expect("theirs");
266
267        let res = merge_programs(&base, &ours, &theirs);
268        assert!(res.conflicts.is_empty());
269        assert_eq!(res.program.items.len(), 3);
270    }
271
272    #[test]
273    fn merge_bind_decl_items() {
274        let base = parse_program("const A: i64 = 1;\n").expect("base");
275        let mut ours = base.clone();
276        let bind_item = Item::Bind(BindDecl {
277            span: crate::span::Span::point(0),
278            left: Expr {
279                span: crate::span::Span::point(0),
280                kind: ExprKind::Ident("left_slot".into()),
281            },
282            right: Expr {
283                span: crate::span::Span::point(0),
284                kind: ExprKind::Ident("right_slot".into()),
285            },
286            clamp: None,
287            resolve: BindResolve::Latest,
288        });
289        ours.items.push(bind_item);
290        let mut theirs = base.clone();
291        theirs.items.push(
292            parse_program("const C: i64 = 3;\n")
293                .expect("theirs")
294                .items
295                .remove(0),
296        );
297
298        let res = merge_programs(&base, &ours, &theirs);
299        assert!(res.conflicts.is_empty());
300        assert_eq!(res.program.items.len(), 3);
301        assert!(res.program.items.iter().any(|item| matches!(item, Item::Bind(_))));
302    }
303}