src/Merging.bend
ber-core-store@0.1.1.0 · 453 lines · 0 definitions
1import Base
2import ber-core-store@0.1.1.0/src/Reading.bend as Reading
3import ber-core-store@0.1.1.0/src/LogicalKey.bend as LogicalKey
4import ber-core-store@0.1.1.0/src/Comparison.bend as Comparison
5import ber-core-store@0.1.1.0/src/StateTree.bend as StateTree
6import ber-core-store@0.1.1.0/src/History.bend as History
7import ber-core-store@0.1.1.0/src/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.
19type 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.
24type LawCheck is Data:
25 Check{check_name: String, check_passed: Bool}
26
27# Parents, base, result hash, strategy and checked laws.
28type 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.
32type 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.
38def 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.
48def 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.
58def 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.
68def 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.
78def 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.
84def 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.
90def 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.
96def 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.
102def 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.
108def 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.
114def 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.
120def 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.
128def 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.
136def 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.
144def 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.
152def 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.
160def 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.
168def 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.
176def 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.
184def 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.
202def 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.
210def 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.
221def 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.
229def 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.
237def 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.
245def 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.
253def 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.
261def 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.
269def 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.
277def 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.
281def 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.
289def 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.
297def 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.
305def 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.
313def 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.
321def 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.
329def 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.
337def 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.
345def 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.
353def 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.
357def 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.
365def 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.
373def 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.
381def 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.
385def 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.
390def 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.
395def 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.
399def 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.
407def 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.
415def 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.
428def 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.
436def 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.
444def 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.
452def 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)