1	import Base
2	import ./Reading.bend as Reading
3	import ./LogicalKey.bend as LogicalKey
4	import ./Comparison.bend as Comparison
5	import ./StateTree.bend as StateTree
6	import ./History.bend as History
7	import ./Store.bend as Store
8	
9	# Three-way merge, strategy "union-disjoint". The pure core decides per key
10	# from (base, first, second) with an explicit truth table: equal inputs take
11	# the value, single-side changes win, delete-vs-unchanged drops, every other
12	# divergence conflicts (both delete-vs-modify directions — asymmetry would
13	# break commutativity). Results are sorted before hashing, so compatible
14	# merges commute as trees by construction.
15	
16	
17	
18	# Pure merge result: merged entries or conflicting keys.
19	type MergeOutcome is Data:
20	  MergedEntries{merged_entries: List<&2, Reading.ChainEntry>}
21	  ConflictingKeys{conflicting_keys: List<&2, LogicalKey.LogicalKey>}
22	
23	# One named law verdict.
24	type LawCheck is Data:
25	  Check{check_name: String, check_passed: Bool}
26	
27	# Parents, base, result hash, strategy and checked laws.
28	type MergeCertificate is Data:
29	  Make{first_parent_commit: String, second_parent_commit: String, base_commit: String, result_tree_hash: String, strategy_name: String, checked_laws: List<&2, LawCheck>}
30	
31	# Success with commit and certificate, conflict, or unprovable.
32	type MergeResult is Data:
33	  MergeSuccess{resulting_commit: History.Commit, certificate: MergeCertificate}
34	  MergeConflict{conflicting_keys: List<&2, LogicalKey.LogicalKey>}
35	  MergeUnprovable{reason: String}
36	
37	# True only for successful merges.
38	def merge_succeeded(merge_result: MergeResult) -> Bool:
39	  match merge_result:
40	    case MergeSuccess{resulting_commit, certificate}:
41	      True{}
42	    case MergeConflict{conflicting_keys}:
43	      False{}
44	    case MergeUnprovable{reason}:
45	      False{}
46	
47	# Counts conflicting keys; zero otherwise.
48	def conflict_key_count(merge_result: MergeResult) -> Nat:
49	  match merge_result:
50	    case MergeSuccess{resulting_commit, certificate}:
51	      0n
52	    case MergeConflict{conflicting_keys}:
53	      List.length(&2, LogicalKey.LogicalKey, conflicting_keys)
54	    case MergeUnprovable{reason}:
55	      0n
56	
57	# Unwraps the resulting commit of a success.
58	def success_commit_of(merge_result: MergeResult) -> Maybe<&2, History.Commit>:
59	  match merge_result:
60	    case MergeSuccess{resulting_commit, certificate}:
61	      Some{resulting_commit}
62	    case MergeConflict{conflicting_keys}:
63	      None{}
64	    case MergeUnprovable{reason}:
65	      None{}
66	
67	# Unwraps the certificate of a success.
68	def success_certificate_of(merge_result: MergeResult) -> Maybe<&2, MergeCertificate>:
69	  match merge_result:
70	    case MergeSuccess{resulting_commit, certificate}:
71	      Some{certificate}
72	    case MergeConflict{conflicting_keys}:
73	      None{}
74	    case MergeUnprovable{reason}:
75	      None{}
76	
77	# Projects the first parent out of a certificate.
78	def cert_first_parent(certificate: MergeCertificate) -> String:
79	  match certificate:
80	    case Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, checked_laws}:
81	      first_parent_commit
82	
83	# Projects the second parent out of a certificate.
84	def cert_second_parent(certificate: MergeCertificate) -> String:
85	  match certificate:
86	    case Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, checked_laws}:
87	      second_parent_commit
88	
89	# Projects the base commit out of a certificate.
90	def cert_base_commit(certificate: MergeCertificate) -> String:
91	  match certificate:
92	    case Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, checked_laws}:
93	      base_commit
94	
95	# Projects the result tree out of a certificate.
96	def cert_result_tree(certificate: MergeCertificate) -> String:
97	  match certificate:
98	    case Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, checked_laws}:
99	      result_tree_hash
100	
101	# Projects the strategy name out of a certificate.
102	def cert_strategy_name(certificate: MergeCertificate) -> String:
103	  match certificate:
104	    case Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, checked_laws}:
105	      strategy_name
106	
107	# Projects the checked laws out of a certificate.
108	def cert_checked_laws(certificate: MergeCertificate) -> List<&2, LawCheck>:
109	  match certificate:
110	    case Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, checked_laws}:
111	      checked_laws
112	
113	# Projects the verdict out of a law check.
114	def law_check_passed(law_check: LawCheck) -> Bool:
115	  match law_check:
116	    case Check{check_name, check_passed}:
117	      check_passed
118	
119	# Projects merged entries; conflicts project as empty.
120	def merged_entries_of(merge_outcome: MergeOutcome) -> List<&2, Reading.ChainEntry>:
121	  match merge_outcome:
122	    case MergedEntries{merged_entries}:
123	      merged_entries
124	    case ConflictingKeys{conflicting_keys}:
125	      Nil{}
126	
127	# Projects conflicting keys; merges project as empty.
128	def conflicting_keys_of(merge_outcome: MergeOutcome) -> List<&2, LogicalKey.LogicalKey>:
129	  match merge_outcome:
130	    case MergedEntries{merged_entries}:
131	      Nil{}
132	    case ConflictingKeys{conflicting_keys}:
133	      conflicting_keys
134	
135	# True short-circuits the membership scan.
136	def decide_contains_member(head_matches: Bool, recursive_result: Bool) -> Bool:
137	  match head_matches:
138	    case True{}:
139	      True{}
140	    case False{}:
141	      recursive_result
142	
143	# Scans the visit list for the identifier.
144	def list_contains_member(+target_identifier: String, visit_list: List<&2, String>) -> Bool:
145	  match visit_list:
146	    case Nil{}:
147	      False{}
148	    case Con{head_identifier, remaining_identifiers}:
149	      decide_contains_member(String.eq(head_identifier, target_identifier), list_contains_member(target_identifier, remaining_identifiers))
150	
151	# Unknown commits contribute no parents.
152	def parent_list_or_empty(commit_maybe: Maybe<&2, History.Commit>) -> List<&2, String>:
153	  match commit_maybe:
154	    case None{}:
155	      Nil{}
156	    case Some{found_commit}:
157	      History.commit_parents_of(found_commit)
158	
159	# Skips visited parents in the queue.
160	def decide_queue_member(is_member: Bool, head_identifier: String, tail_queue: List<&2, String>) -> List<&2, String>:
161	  match is_member:
162	    case True{}:
163	      tail_queue
164	    case False{}:
165	      Con{head_identifier, tail_queue}
166	
167	# Keeps only unvisited parents.
168	def filter_unvisited(parent_identifiers: List<&2, String>, +visited_accum: List<&2, String>) -> List<&2, String>:
169	  match parent_identifiers:
170	    case Nil{}:
171	      Nil{}
172	    case Con{+head_identifier, remaining_parents}:
173	      decide_queue_member(list_contains_member(head_identifier, visited_accum), head_identifier, filter_unvisited(remaining_parents, visited_accum))
174	
175	# Deduplicates the visited accumulator.
176	def decide_visited_member(already_visited: Bool, +head_identifier: String, tail_result: List<&2, String>) -> List<&2, String>:
177	  match already_visited:
178	    case True{}:
179	      tail_result
180	    case False{}:
181	      Con{head_identifier, tail_result}
182	
183	# Breadth-first ancestor collection with fuel.
184	def collect_ancestors(remaining_fuel: Nat, visit_queue: List<&2, String>, +visited_accum: List<&2, String>) -> Store.Op<&2, List<&2, String>>:
185	  match remaining_fuel:
186	    case 0n:
187	      do Store.Op<&2, List<&2, String>>:
188	        return visited_accum
189	    case 1n+fuel_left:
190	      match visit_queue:
191	        case Nil{}:
192	          do Store.Op<&2, List<&2, String>>:
193	            return visited_accum
194	        case Con{+head_identifier, remaining_queue}:
195	          do Store.Op<&2, List<&2, String>>:
196	            commit_maybe : Maybe<&2, History.Commit> <- History.load_commit(head_identifier)
197	            +extended_queue : List<&2, String> = List.append(&2, String, remaining_queue, filter_unvisited(parent_list_or_empty(commit_maybe), visited_accum))
198	            tail_result : List<&2, String> <- collect_ancestors(fuel_left, extended_queue, Con{head_identifier, visited_accum})
199	            return decide_visited_member(list_contains_member(head_identifier, visited_accum), head_identifier, tail_result)
200	
201	# Some on the first common commit, otherwise the tail.
202	def decide_lca_found(is_common: Bool, +commit_identifier: String, tail_result: Maybe<&2, String>) -> Maybe<&2, String>:
203	  match is_common:
204	    case True{}:
205	      Some{commit_identifier}
206	    case False{}:
207	      tail_result
208	
209	# A hit ends the ascent: deeper links cannot beat the first common commit.
210	def lca_fuel_left(is_common: Bool, fuel_left: Nat) -> Nat:
211	  match is_common:
212	    case True{}:
213	      0n
214	    case False{}:
215	      fuel_left
216	
217	# Walks the second branch for the first ancestor-set hit. checker_fuel
218	# decreases every level for the termination checker; gated_fuel carries the
219	# early stop. Callers pass the same fuel twice.
220	def find_first_common(+ancestor_set: List<&2, String>, checker_fuel: Nat, gated_fuel: Nat, +commit_identifier: String) -> Store.Op<&2, Maybe<&2, String>>:
221	  match checker_fuel gated_fuel:
222	    case 0n _:
223	      History.empty_text_maybe()
224	    case 1n+checker_left 0n:
225	      History.empty_text_maybe()
226	    case 1n+checker_left 1n+gated_left:
227	      do Store.Op<&2, Maybe<&2, String>>:
228	        commit_maybe : Maybe<&2, History.Commit> <- History.load_commit(commit_identifier)
229	        +parent_text : String = History.first_parent_text(commit_maybe)
230	        tail_result : Maybe<&2, String> <- find_first_common(ancestor_set, checker_left, lca_fuel_left(list_contains_member(commit_identifier, ancestor_set), gated_left), parent_text)
231	        return decide_lca_found(list_contains_member(commit_identifier, ancestor_set), commit_identifier, tail_result)
232	
233	# Emits the first side entry.
234	def keep_first_entry(+combined_key: String, +entry_value: String, tail_outcome: MergeOutcome) -> MergeOutcome:
235	  match tail_outcome:
236	    case ConflictingKeys{conflicting_keys}:
237	      ConflictingKeys{conflicting_keys}
238	    case MergedEntries{merged_entries}:
239	      MergedEntries{Con{Reading.make_entry(combined_key, entry_value), merged_entries}}
240	
241	# Emits the second side entry.
242	def keep_second_entry(+combined_key: String, +entry_value: String, tail_outcome: MergeOutcome) -> MergeOutcome:
243	  match tail_outcome:
244	    case ConflictingKeys{conflicting_keys}:
245	      ConflictingKeys{conflicting_keys}
246	    case MergedEntries{merged_entries}:
247	      MergedEntries{Con{Reading.make_entry(combined_key, entry_value), merged_entries}}
248	
249	# Records the key as conflicting.
250	def raise_merge_conflict(+combined_key: String, tail_outcome: MergeOutcome) -> MergeOutcome:
251	  match tail_outcome:
252	    case ConflictingKeys{conflicting_keys}:
253	      ConflictingKeys{Con{LogicalKey.split_combined_key(combined_key), conflicting_keys}}
254	    case MergedEntries{merged_entries}:
255	      ConflictingKeys{Con{LogicalKey.split_combined_key(combined_key), Nil{}}}
256	
257	# Unchanged second keeps first; changed conflicts.
258	def decide_second_changed(second_unchanged: Bool, +combined_key: String, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
259	  match second_unchanged:
260	    case True{}:
261	      keep_first_entry(combined_key, first_text, tail_outcome)
262	    case False{}:
263	      raise_merge_conflict(combined_key, tail_outcome)
264	
265	# Unchanged first keeps second; otherwise checks second.
266	def decide_divergent_base(first_unchanged: Bool, second_unchanged: Bool, +combined_key: String, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
267	  match first_unchanged:
268	    case True{}:
269	      keep_second_entry(combined_key, second_text, tail_outcome)
270	    case False{}:
271	      decide_second_changed(second_unchanged, combined_key, first_text, second_text, tail_outcome)
272	
273	# Resolves two present values against the base.
274	def resolve_divergent(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
275	  match base_value:
276	    case None{}:
277	      raise_merge_conflict(combined_key, tail_outcome)
278	    case Some{+base_text}:
279	      decide_divergent_base(String.eq(first_text, base_text), String.eq(second_text, base_text), combined_key, first_text, second_text, tail_outcome)
280	
281	# Equal sides keep the value; unequal consults the base.
282	def decide_both_equal(both_equal: Bool, +combined_key: String, base_value: Maybe<&2, String>, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
283	  match both_equal:
284	    case True{}:
285	      keep_first_entry(combined_key, first_text, tail_outcome)
286	    case False{}:
287	      resolve_divergent(combined_key, base_value, first_text, second_text, tail_outcome)
288	
289	# Resolves two present values.
290	def resolve_both_present(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
291	  decide_both_equal(String.eq(first_text, second_text), combined_key, base_value, first_text, second_text, tail_outcome)
292	
293	# Unchanged present drops; modified conflicts.
294	def decide_present_delete(first_unchanged: Bool, +combined_key: String, +first_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
295	  match first_unchanged:
296	    case True{}:
297	      tail_outcome
298	    case False{}:
299	      raise_merge_conflict(combined_key, tail_outcome)
300	
301	# Keeps added values; checks modified-against-base.
302	def resolve_present_vs_deleted(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
303	  match base_value:
304	    case None{}:
305	      keep_first_entry(combined_key, first_text, tail_outcome)
306	    case Some{base_text}:
307	      decide_present_delete(String.eq(first_text, base_text), combined_key, first_text, tail_outcome)
308	
309	# Dispatches on the second side presence.
310	def resolve_first_present(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, second_value: Maybe<&2, String>, tail_outcome: MergeOutcome) -> MergeOutcome:
311	  match second_value:
312	    case None{}:
313	      resolve_present_vs_deleted(combined_key, base_value, first_text, tail_outcome)
314	    case Some{second_text}:
315	      resolve_both_present(combined_key, base_value, first_text, second_text, tail_outcome)
316	
317	# Unchanged second drops; modified conflicts.
318	def decide_delete_modify(second_unchanged: Bool, +combined_key: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
319	  match second_unchanged:
320	    case True{}:
321	      tail_outcome
322	    case False{}:
323	      raise_merge_conflict(combined_key, tail_outcome)
324	
325	# Keeps added values; checks modified-against-base.
326	def resolve_deleted_vs_present(+combined_key: String, base_value: Maybe<&2, String>, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
327	  match base_value:
328	    case None{}:
329	      keep_second_entry(combined_key, second_text, tail_outcome)
330	    case Some{base_text}:
331	      decide_delete_modify(String.eq(second_text, base_text), combined_key, second_text, tail_outcome)
332	
333	# Dispatches on the second side presence.
334	def resolve_first_absent(+combined_key: String, base_value: Maybe<&2, String>, second_value: Maybe<&2, String>, tail_outcome: MergeOutcome) -> MergeOutcome:
335	  match second_value:
336	    case None{}:
337	      tail_outcome
338	    case Some{second_text}:
339	      resolve_deleted_vs_present(combined_key, base_value, second_text, tail_outcome)
340	
341	# Decides one key from its (base, first, second) values.
342	def resolve_key_triple(+combined_key: String, base_value: Maybe<&2, String>, first_value: Maybe<&2, String>, second_value: Maybe<&2, String>, tail_outcome: MergeOutcome) -> MergeOutcome:
343	  match first_value:
344	    case None{}:
345	      resolve_first_absent(combined_key, base_value, second_value, tail_outcome)
346	    case Some{first_text}:
347	      resolve_first_present(combined_key, base_value, first_text, second_value, tail_outcome)
348	
349	# Emits unseen keys once.
350	def decide_unique_emit(is_seen: Bool, +head_key: String, tail_keys: List<&2, String>) -> List<&2, String>:
351	  match is_seen:
352	    case True{}:
353	      tail_keys
354	    case False{}:
355	      Con{head_key, tail_keys}
356	
357	# Collects candidate keys in first-seen order.
358	def unique_seen_keys(entries: List<&2, Reading.ChainEntry>, +seen_keys: List<&2, String>) -> List<&2, String>:
359	  match entries:
360	    case Nil{}:
361	      Nil{}
362	    case Con{+head_entry, remaining_entries}:
363	      decide_unique_emit(list_contains_member(Reading.entry_key_of(head_entry), seen_keys), Reading.entry_key_of(head_entry), unique_seen_keys(remaining_entries, Con{Reading.entry_key_of(head_entry), seen_keys}))
364	
365	# Concatenates base, first and second entries.
366	def all_candidate_entries(+base_entries: List<&2, Reading.ChainEntry>, +first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:
367	  List.append(&2, Reading.ChainEntry, base_entries, List.append(&2, Reading.ChainEntry, first_entries, second_entries))
368	
369	# Merges every unique key against the three entry lists.
370	def merge_unique_keys(unique_keys: List<&2, String>, +base_entries: List<&2, Reading.ChainEntry>, +first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> MergeOutcome:
371	  match unique_keys:
372	    case Nil{}:
373	      MergedEntries{Nil{}}
374	    case Con{+head_key, remaining_keys}:
375	      resolve_key_triple(head_key, Comparison.value_of_key(head_key, base_entries), Comparison.value_of_key(head_key, first_entries), Comparison.value_of_key(head_key, second_entries), merge_unique_keys(remaining_keys, base_entries, first_entries, second_entries))
376	
377	# Sorts merged entries by key for canonical hashing.
378	def sort_entries(unsorted_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:
379	  match unsorted_entries:
380	    case Nil{}:
381	      Nil{}
382	    case Con{head_entry, remaining_entries}:
383	      StateTree.insert_single_entry(sort_entries(remaining_entries), head_entry)
384	
385	# Sorts merged entries; conflicts pass through.
386	def finalize_merge(merge_outcome: MergeOutcome) -> MergeOutcome:
387	  match merge_outcome:
388	    case MergedEntries{merged_entries}:
389	      MergedEntries{sort_entries(merged_entries)}
390	    case ConflictingKeys{conflicting_keys}:
391	      ConflictingKeys{conflicting_keys}
392	
393	# Pure three-way merge core over entry lists.
394	def merge_entry_lists(+base_entries: List<&2, Reading.ChainEntry>, +first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> MergeOutcome:
395	  finalize_merge(merge_unique_keys(unique_seen_keys(all_candidate_entries(base_entries, first_entries, second_entries), Nil{}), base_entries, first_entries, second_entries))
396	
397	# Wraps conflicting keys as a Sess result.
398	def conflict_merge_result(conflicting_keys: List<&2, LogicalKey.LogicalKey>) -> Store.Op<&2, MergeResult>:
399	  do Store.Op<&2, MergeResult>:
400	    return MergeConflict{conflicting_keys}
401	
402	# Wraps an unprovable reason as a Sess result.
403	def unprovable_merge_result(+reason: String) -> Store.Op<&2, MergeResult>:
404	  do Store.Op<&2, MergeResult>:
405	    return MergeUnprovable{reason}
406	
407	# Issues the certificate with pairwise-compatibility evidence.
408	def build_merge_certificate(+first_parent_commit: String, +second_parent_commit: String, +base_commit: String, +result_tree_hash: String, +strategy_name: String) -> MergeCertificate:
409	  Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, Con{Check{"pairwise-compatibility", True{}}, Nil{}}}
410	
411	# Persists tree, commit and index for merged entries.
412	def persist_merged_result(+first_identifier: String, +second_identifier: String, +base_identifier: String, +merged_entries: List<&2, Reading.ChainEntry>) -> Store.Op<&2, MergeResult>:
413	  do Store.Op<&2, MergeResult>:
414	    +tree_hash_value : String <- History.persist_tree(merged_entries)
415	    +resulting_commit : History.Commit <- History.persist_commit(Con{first_identifier, Con{second_identifier, Nil{}}}, Con{History.Field{"strategy", "union-disjoint"}, Nil{}}, tree_hash_value)
416	    indexed_unit : Unit <- History.write_each_index(merged_entries, resulting_commit)
417	    return MergeSuccess{resulting_commit, build_merge_certificate(first_identifier, second_identifier, base_identifier, tree_hash_value, "union-disjoint")}
418	
419	# Persists merges; conflicts become results directly.
420	def persist_merge_outcome(merge_outcome: MergeOutcome, +first_identifier: String, +second_identifier: String, +base_identifier: String) -> Store.Op<&2, MergeResult>:
421	  match merge_outcome:
422	    case ConflictingKeys{conflicting_keys}:
423	      conflict_merge_result(conflicting_keys)
424	    case MergedEntries{merged_entries}:
425	      persist_merged_result(first_identifier, second_identifier, base_identifier, merged_entries)
426	
427	# Loads the three trees and merges them.
428	def merge_three_way(+first_identifier: String, +second_identifier: String, +base_identifier: String) -> Store.Op<&2, MergeResult>:
429	  do Store.Op<&2, MergeResult>:
430	    base_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(base_identifier)
431	    first_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(first_identifier)
432	    second_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(second_identifier)
433	    +base_entries : List<&2, Reading.ChainEntry> = Comparison.entries_or_empty(base_tree_maybe)
434	    +first_entries : List<&2, Reading.ChainEntry> = Comparison.entries_or_empty(first_tree_maybe)
435	    +second_entries : List<&2, Reading.ChainEntry> = Comparison.entries_or_empty(second_tree_maybe)
436	    merged_outcome : MergeOutcome = finalize_merge(merge_entry_lists(base_entries, first_entries, second_entries))
437	    persisted_result : MergeResult <- persist_merge_outcome(merged_outcome, first_identifier, second_identifier, base_identifier)
438	    return persisted_result
439	
440	# Merges on the ancestor; missing ancestors are unprovable.
441	def branch_lca_search(lca_maybe: Maybe<&2, String>, +first_identifier: String, +second_identifier: String) -> Store.Op<&2, MergeResult>:
442	  match lca_maybe:
443	    case None{}:
444	      unprovable_merge_result("no-common-ancestor")
445	    case Some{base_identifier}:
446	      merge_three_way(first_identifier, second_identifier, base_identifier)
447	
448	# Finds the lowest common ancestor, then merges.
449	def merge_with_ancestor_search(+first_identifier: String, +second_identifier: String) -> Store.Op<&2, MergeResult>:
450	  do Store.Op<&2, MergeResult>:
451	    ancestor_set : List<&2, String> <- collect_ancestors(10000n, Con{first_identifier, Nil{}}, Nil{})
452	    lca_maybe : Maybe<&2, String> <- find_first_common(ancestor_set, 10000n, 10000n, second_identifier)
453	    merged_result : MergeResult <- branch_lca_search(lca_maybe, first_identifier, second_identifier)
454	    return merged_result
455	
456	# Only union-disjoint merges; anything else is unprovable.
457	def decide_strategy_name(strategy_matches: Bool, +first_identifier: String, +second_identifier: String) -> Store.Op<&2, MergeResult>:
458	  match strategy_matches:
459	    case True{}:
460	      merge_with_ancestor_search(first_identifier, second_identifier)
461	    case False{}:
462	      unprovable_merge_result("unknown-strategy")
463	
464	# Merges two commits by strategy name.
465	def merge_commits(+first_identifier: String, +second_identifier: String, +strategy_name: String) -> Store.Op<&2, MergeResult>:
466	  decide_strategy_name(String.eq(strategy_name, "union-disjoint"), first_identifier, second_identifier)