1use crate::ast::*;
8
9#[derive(Debug, Clone)]
11pub struct MergeResult {
12 pub program: Program,
14 pub conflicts: Vec<MergeConflict>,
16}
17
18#[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
27pub 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 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 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 (Some(b), Some(o), Some(t)) if items_equal(b, o) && items_equal(b, t) => {
59 merged_items.push((*b).clone());
60 }
61 (Some(b), Some(o), Some(t)) if items_equal(b, t) && !items_equal(b, o) => {
63 merged_items.push(o.clone());
64 }
65 (Some(b), Some(o), Some(t)) if items_equal(b, o) && !items_equal(b, t) => {
67 merged_items.push(t.clone());
68 }
69 (Some(_), Some(o), Some(t)) if items_equal(o, t) => {
71 merged_items.push(o.clone());
72 }
73 (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 (None, Some(o), None) => {
85 merged_items.push(o.clone());
86 }
87 (None, None, Some(t)) => {
89 merged_items.push(t.clone());
90 }
91 (None, Some(o), Some(t)) if items_equal(o, t) => {
93 merged_items.push(o.clone());
94 }
95 (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 (Some(b), None, Some(t)) if items_equal(b, t) => {}
107 (Some(b), Some(o), None) if items_equal(b, o) => {}
109 (Some(_), None, None) => {}
111 (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 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 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 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}