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	# Walks the second branch for the first ancestor-set hit.
210	def find_first_common(+ancestor_set: List<&2, String>, remaining_fuel: Nat, +commit_identifier: String) -> Store.Op<&2, Maybe<&2, String>>:
211	  match remaining_fuel:
212	    case 0n:
213	      History.empty_text_maybe()
214	    case 1n+fuel_left:
215	      do Store.Op<&2, Maybe<&2, String>>:
216	        commit_maybe : Maybe<&2, History.Commit> <- History.load_commit(commit_identifier)
217	        tail_result : Maybe<&2, String> <- find_first_common(ancestor_set, fuel_left, History.first_parent_text(commit_maybe))
218	        return decide_lca_found(list_contains_member(commit_identifier, ancestor_set), commit_identifier, tail_result)
219	
220	# Emits the first side entry.
221	def keep_first_entry(+combined_key: String, +entry_value: String, tail_outcome: MergeOutcome) -> MergeOutcome:
222	  match tail_outcome:
223	    case ConflictingKeys{conflicting_keys}:
224	      ConflictingKeys{conflicting_keys}
225	    case MergedEntries{merged_entries}:
226	      MergedEntries{Con{Reading.make_entry(combined_key, entry_value), merged_entries}}
227	
228	# Emits the second side entry.
229	def keep_second_entry(+combined_key: String, +entry_value: String, tail_outcome: MergeOutcome) -> MergeOutcome:
230	  match tail_outcome:
231	    case ConflictingKeys{conflicting_keys}:
232	      ConflictingKeys{conflicting_keys}
233	    case MergedEntries{merged_entries}:
234	      MergedEntries{Con{Reading.make_entry(combined_key, entry_value), merged_entries}}
235	
236	# Records the key as conflicting.
237	def raise_merge_conflict(+combined_key: String, tail_outcome: MergeOutcome) -> MergeOutcome:
238	  match tail_outcome:
239	    case ConflictingKeys{conflicting_keys}:
240	      ConflictingKeys{Con{LogicalKey.split_combined_key(combined_key), conflicting_keys}}
241	    case MergedEntries{merged_entries}:
242	      ConflictingKeys{Con{LogicalKey.split_combined_key(combined_key), Nil{}}}
243	
244	# Unchanged second keeps first; changed conflicts.
245	def decide_second_changed(second_unchanged: Bool, +combined_key: String, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
246	  match second_unchanged:
247	    case True{}:
248	      keep_first_entry(combined_key, first_text, tail_outcome)
249	    case False{}:
250	      raise_merge_conflict(combined_key, tail_outcome)
251	
252	# Unchanged first keeps second; otherwise checks second.
253	def decide_divergent_base(first_unchanged: Bool, second_unchanged: Bool, +combined_key: String, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
254	  match first_unchanged:
255	    case True{}:
256	      keep_second_entry(combined_key, second_text, tail_outcome)
257	    case False{}:
258	      decide_second_changed(second_unchanged, combined_key, first_text, second_text, tail_outcome)
259	
260	# Resolves two present values against the base.
261	def resolve_divergent(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
262	  match base_value:
263	    case None{}:
264	      raise_merge_conflict(combined_key, tail_outcome)
265	    case Some{+base_text}:
266	      decide_divergent_base(String.eq(first_text, base_text), String.eq(second_text, base_text), combined_key, first_text, second_text, tail_outcome)
267	
268	# Equal sides keep the value; unequal consults the base.
269	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:
270	  match both_equal:
271	    case True{}:
272	      keep_first_entry(combined_key, first_text, tail_outcome)
273	    case False{}:
274	      resolve_divergent(combined_key, base_value, first_text, second_text, tail_outcome)
275	
276	# Resolves two present values.
277	def resolve_both_present(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
278	  decide_both_equal(String.eq(first_text, second_text), combined_key, base_value, first_text, second_text, tail_outcome)
279	
280	# Unchanged present drops; modified conflicts.
281	def decide_present_delete(first_unchanged: Bool, +combined_key: String, +first_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
282	  match first_unchanged:
283	    case True{}:
284	      tail_outcome
285	    case False{}:
286	      raise_merge_conflict(combined_key, tail_outcome)
287	
288	# Keeps added values; checks modified-against-base.
289	def resolve_present_vs_deleted(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
290	  match base_value:
291	    case None{}:
292	      keep_first_entry(combined_key, first_text, tail_outcome)
293	    case Some{base_text}:
294	      decide_present_delete(String.eq(first_text, base_text), combined_key, first_text, tail_outcome)
295	
296	# Dispatches on the second side presence.
297	def resolve_first_present(+combined_key: String, base_value: Maybe<&2, String>, +first_text: String, second_value: Maybe<&2, String>, tail_outcome: MergeOutcome) -> MergeOutcome:
298	  match second_value:
299	    case None{}:
300	      resolve_present_vs_deleted(combined_key, base_value, first_text, tail_outcome)
301	    case Some{second_text}:
302	      resolve_both_present(combined_key, base_value, first_text, second_text, tail_outcome)
303	
304	# Unchanged second drops; modified conflicts.
305	def decide_delete_modify(second_unchanged: Bool, +combined_key: String, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
306	  match second_unchanged:
307	    case True{}:
308	      tail_outcome
309	    case False{}:
310	      raise_merge_conflict(combined_key, tail_outcome)
311	
312	# Keeps added values; checks modified-against-base.
313	def resolve_deleted_vs_present(+combined_key: String, base_value: Maybe<&2, String>, +second_text: String, tail_outcome: MergeOutcome) -> MergeOutcome:
314	  match base_value:
315	    case None{}:
316	      keep_second_entry(combined_key, second_text, tail_outcome)
317	    case Some{base_text}:
318	      decide_delete_modify(String.eq(second_text, base_text), combined_key, second_text, tail_outcome)
319	
320	# Dispatches on the second side presence.
321	def resolve_first_absent(+combined_key: String, base_value: Maybe<&2, String>, second_value: Maybe<&2, String>, tail_outcome: MergeOutcome) -> MergeOutcome:
322	  match second_value:
323	    case None{}:
324	      tail_outcome
325	    case Some{second_text}:
326	      resolve_deleted_vs_present(combined_key, base_value, second_text, tail_outcome)
327	
328	# Decides one key from its (base, first, second) values.
329	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:
330	  match first_value:
331	    case None{}:
332	      resolve_first_absent(combined_key, base_value, second_value, tail_outcome)
333	    case Some{first_text}:
334	      resolve_first_present(combined_key, base_value, first_text, second_value, tail_outcome)
335	
336	# Emits unseen keys once.
337	def decide_unique_emit(is_seen: Bool, +head_key: String, tail_keys: List<&2, String>) -> List<&2, String>:
338	  match is_seen:
339	    case True{}:
340	      tail_keys
341	    case False{}:
342	      Con{head_key, tail_keys}
343	
344	# Collects candidate keys in first-seen order.
345	def unique_seen_keys(entries: List<&2, Reading.ChainEntry>, +seen_keys: List<&2, String>) -> List<&2, String>:
346	  match entries:
347	    case Nil{}:
348	      Nil{}
349	    case Con{+head_entry, remaining_entries}:
350	      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}))
351	
352	# Concatenates base, first and second entries.
353	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>:
354	  List.append(&2, Reading.ChainEntry, base_entries, List.append(&2, Reading.ChainEntry, first_entries, second_entries))
355	
356	# Merges every unique key against the three entry lists.
357	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:
358	  match unique_keys:
359	    case Nil{}:
360	      MergedEntries{Nil{}}
361	    case Con{+head_key, remaining_keys}:
362	      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))
363	
364	# Sorts merged entries by key for canonical hashing.
365	def sort_entries(unsorted_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:
366	  match unsorted_entries:
367	    case Nil{}:
368	      Nil{}
369	    case Con{head_entry, remaining_entries}:
370	      StateTree.insert_single_entry(sort_entries(remaining_entries), head_entry)
371	
372	# Sorts merged entries; conflicts pass through.
373	def finalize_merge(merge_outcome: MergeOutcome) -> MergeOutcome:
374	  match merge_outcome:
375	    case MergedEntries{merged_entries}:
376	      MergedEntries{sort_entries(merged_entries)}
377	    case ConflictingKeys{conflicting_keys}:
378	      ConflictingKeys{conflicting_keys}
379	
380	# Pure three-way merge core over entry lists.
381	def merge_entry_lists(+base_entries: List<&2, Reading.ChainEntry>, +first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> MergeOutcome:
382	  finalize_merge(merge_unique_keys(unique_seen_keys(all_candidate_entries(base_entries, first_entries, second_entries), Nil{}), base_entries, first_entries, second_entries))
383	
384	# Wraps conflicting keys as a Sess result.
385	def conflict_merge_result(conflicting_keys: List<&2, LogicalKey.LogicalKey>) -> Store.Op<&2, MergeResult>:
386	  do Store.Op<&2, MergeResult>:
387	    return MergeConflict{conflicting_keys}
388	
389	# Wraps an unprovable reason as a Sess result.
390	def unprovable_merge_result(+reason: String) -> Store.Op<&2, MergeResult>:
391	  do Store.Op<&2, MergeResult>:
392	    return MergeUnprovable{reason}
393	
394	# Issues the certificate with pairwise-compatibility evidence.
395	def build_merge_certificate(+first_parent_commit: String, +second_parent_commit: String, +base_commit: String, +result_tree_hash: String, +strategy_name: String) -> MergeCertificate:
396	  Make{first_parent_commit, second_parent_commit, base_commit, result_tree_hash, strategy_name, Con{Check{"pairwise-compatibility", True{}}, Nil{}}}
397	
398	# Persists tree, commit and index for merged entries.
399	def persist_merged_result(+first_identifier: String, +second_identifier: String, +base_identifier: String, +merged_entries: List<&2, Reading.ChainEntry>) -> Store.Op<&2, MergeResult>:
400	  do Store.Op<&2, MergeResult>:
401	    +tree_hash_value : String <- History.persist_tree(merged_entries)
402	    +resulting_commit : History.Commit <- History.persist_commit(Con{first_identifier, Con{second_identifier, Nil{}}}, Con{History.Field{"strategy", "union-disjoint"}, Nil{}}, tree_hash_value)
403	    indexed_unit : Unit <- History.write_each_index(merged_entries, resulting_commit)
404	    return MergeSuccess{resulting_commit, build_merge_certificate(first_identifier, second_identifier, base_identifier, tree_hash_value, "union-disjoint")}
405	
406	# Persists merges; conflicts become results directly.
407	def persist_merge_outcome(merge_outcome: MergeOutcome, +first_identifier: String, +second_identifier: String, +base_identifier: String) -> Store.Op<&2, MergeResult>:
408	  match merge_outcome:
409	    case ConflictingKeys{conflicting_keys}:
410	      conflict_merge_result(conflicting_keys)
411	    case MergedEntries{merged_entries}:
412	      persist_merged_result(first_identifier, second_identifier, base_identifier, merged_entries)
413	
414	# Loads the three trees and merges them.
415	def merge_three_way(+first_identifier: String, +second_identifier: String, +base_identifier: String) -> Store.Op<&2, MergeResult>:
416	  do Store.Op<&2, MergeResult>:
417	    base_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(base_identifier)
418	    first_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(first_identifier)
419	    second_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(second_identifier)
420	    +base_entries : List<&2, Reading.ChainEntry> = Comparison.entries_or_empty(base_tree_maybe)
421	    +first_entries : List<&2, Reading.ChainEntry> = Comparison.entries_or_empty(first_tree_maybe)
422	    +second_entries : List<&2, Reading.ChainEntry> = Comparison.entries_or_empty(second_tree_maybe)
423	    merged_outcome : MergeOutcome = finalize_merge(merge_entry_lists(base_entries, first_entries, second_entries))
424	    persisted_result : MergeResult <- persist_merge_outcome(merged_outcome, first_identifier, second_identifier, base_identifier)
425	    return persisted_result
426	
427	# Merges on the ancestor; missing ancestors are unprovable.
428	def branch_lca_search(lca_maybe: Maybe<&2, String>, +first_identifier: String, +second_identifier: String) -> Store.Op<&2, MergeResult>:
429	  match lca_maybe:
430	    case None{}:
431	      unprovable_merge_result("no-common-ancestor")
432	    case Some{base_identifier}:
433	      merge_three_way(first_identifier, second_identifier, base_identifier)
434	
435	# Finds the lowest common ancestor, then merges.
436	def merge_with_ancestor_search(+first_identifier: String, +second_identifier: String) -> Store.Op<&2, MergeResult>:
437	  do Store.Op<&2, MergeResult>:
438	    ancestor_set : List<&2, String> <- collect_ancestors(10000n, Con{first_identifier, Nil{}}, Nil{})
439	    lca_maybe : Maybe<&2, String> <- find_first_common(ancestor_set, 10000n, second_identifier)
440	    merged_result : MergeResult <- branch_lca_search(lca_maybe, first_identifier, second_identifier)
441	    return merged_result
442	
443	# Only union-disjoint merges; anything else is unprovable.
444	def decide_strategy_name(strategy_matches: Bool, +first_identifier: String, +second_identifier: String) -> Store.Op<&2, MergeResult>:
445	  match strategy_matches:
446	    case True{}:
447	      merge_with_ancestor_search(first_identifier, second_identifier)
448	    case False{}:
449	      unprovable_merge_result("unknown-strategy")
450	
451	# Merges two commits by strategy name.
452	def merge_commits(+first_identifier: String, +second_identifier: String, +strategy_name: String) -> Store.Op<&2, MergeResult>:
453	  decide_strategy_name(String.eq(strategy_name, "union-disjoint"), first_identifier, second_identifier)