src/Comparison.bend source

src/Comparison.bend on the hub · documented module

import Baseimport ./Reading.bend as Readingimport ./LogicalKey.bend as LogicalKeyimport ./StateTree.bend as StateTreeimport ./History.bend as Historyimport ./Store.bend as Store# Structural tree diff, membership-based (no ordering decisions): added =# second-only keys, removed = first-only keys, modified = shared keys with# different value hashes. Zero Cmp matching keeps every branch provable.# The v0.3 fan-out splits entries alternately and compares halves in# parallel; counts and sets agree with the sequential path, order does not# (downstream merge sorts before hashing, so order never leaks into hashes).# One changed key with its before/after hashes.type ModifiedEntry is Data:  Changed{changed_key: LogicalKey.LogicalKey, before_hash: String, after_hash: String}# Added, removed and modified sets plus prune/compare counts.type CompareResult is Data:  Make{added_keys: List<&2, LogicalKey.LogicalKey>, removed_keys: List<&2, LogicalKey.LogicalKey>, modified_entries: List<&2, ModifiedEntry>, pruned_subtree_count: Nat, compared_entry_count: Nat}# Projects the added keys out of a compare result.def added_keys_of(compare_result: CompareResult) -> List<&2, LogicalKey.LogicalKey>:  match compare_result:    case Make{added_keys, removed_keys, modified_entries, pruned_subtree_count, compared_entry_count}:      added_keys# Projects the removed keys out of a compare result.def removed_keys_of(compare_result: CompareResult) -> List<&2, LogicalKey.LogicalKey>:  match compare_result:    case Make{added_keys, removed_keys, modified_entries, pruned_subtree_count, compared_entry_count}:      removed_keys# Projects the modified entries out of a compare result.def modified_entries_of(compare_result: CompareResult) -> List<&2, ModifiedEntry>:  match compare_result:    case Make{added_keys, removed_keys, modified_entries, pruned_subtree_count, compared_entry_count}:      modified_entries# Projects the pruned-subtree count out of a compare result.def pruned_count_of(compare_result: CompareResult) -> Nat:  match compare_result:    case Make{added_keys, removed_keys, modified_entries, pruned_subtree_count, compared_entry_count}:      pruned_subtree_count# Projects the compared-entry count out of a compare result.def compared_entry_count_of(compare_result: CompareResult) -> Nat:  match compare_result:    case Make{added_keys, removed_keys, modified_entries, pruned_subtree_count, compared_entry_count}:      compared_entry_count# Splits an entry key into namespace and record.def entry_to_logical_key(head_entry: Reading.ChainEntry) -> LogicalKey.LogicalKey:  LogicalKey.split_combined_key(Reading.entry_key_of(head_entry))# True short-circuits the membership scan.def decide_member_found(head_matches: Bool, recursive_result: Bool) -> Bool:  match head_matches:    case True{}:      True{}    case False{}:      recursive_result# Scans entries for the target key.def key_in_entries(+target_key: String, entries: List<&2, Reading.ChainEntry>) -> Bool:  match entries:    case Nil{}:      False{}    case Con{head_entry, remaining_entries}:      decide_member_found(String.eq(Reading.entry_key_of(head_entry), target_key), key_in_entries(target_key, remaining_entries))# Keeps the entry only when absent from the other side.def decide_member_keep(is_member: Bool, +head_entry: Reading.ChainEntry, tail_keys: List<&2, LogicalKey.LogicalKey>) -> List<&2, LogicalKey.LogicalKey>:  match is_member:    case True{}:      tail_keys    case False{}:      Con{entry_to_logical_key(head_entry), tail_keys}# Keys of second absent from first: the added set.def second_only_entries(+first_entries: List<&2, Reading.ChainEntry>, second_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  match second_entries:    case Nil{}:      Nil{}    case Con{+head_entry, remaining_entries}:      decide_member_keep(key_in_entries(Reading.entry_key_of(head_entry), first_entries), head_entry, second_only_entries(first_entries, remaining_entries))# Keys of first absent from second: the removed set.def first_only_entries(+second_entries: List<&2, Reading.ChainEntry>, first_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  match first_entries:    case Nil{}:      Nil{}    case Con{+head_entry, remaining_entries}:      decide_member_keep(key_in_entries(Reading.entry_key_of(head_entry), second_entries), head_entry, first_only_entries(second_entries, remaining_entries))# Some on match, otherwise the tail result.def decide_value_found(head_matches: Bool, head_value: String, tail_result: Maybe<&2, String>) -> Maybe<&2, String>:  match head_matches:    case True{}:      Some{head_value}    case False{}:      tail_result# Finds the value stored under the key.def value_of_key(+target_key: String, entries: List<&2, Reading.ChainEntry>) -> Maybe<&2, String>:  match entries:    case Nil{}:      None{}    case Con{+head_entry, remaining_entries}:      decide_value_found(String.eq(Reading.entry_key_of(head_entry), target_key), Reading.entry_value_of(head_entry), value_of_key(target_key, remaining_entries))# Records a change only when values differ.def decide_modified_value(values_equal: Bool, +head_entry: Reading.ChainEntry, +second_value: String, tail_modified: List<&2, ModifiedEntry>) -> List<&2, ModifiedEntry>:  match values_equal:    case True{}:      tail_modified    case False{}:      Con{Changed{entry_to_logical_key(head_entry), Reading.entry_value_of(head_entry), second_value}, tail_modified}# Records a change when the key exists on both sides.def decide_modified_member(second_value_maybe: Maybe<&2, String>, +head_entry: Reading.ChainEntry, tail_modified: List<&2, ModifiedEntry>) -> List<&2, ModifiedEntry>:  match second_value_maybe:    case None{}:      tail_modified    case Some{+second_value}:      decide_modified_value(String.eq(Reading.entry_value_of(head_entry), second_value), head_entry, second_value, tail_modified)# Shared keys with different values: the modified set.def changed_pairs(+second_entries: List<&2, Reading.ChainEntry>, first_entries: List<&2, Reading.ChainEntry>) -> List<&2, ModifiedEntry>:  match first_entries:    case Nil{}:      Nil{}    case Con{+head_entry, remaining_entries}:      decide_modified_member(value_of_key(Reading.entry_key_of(head_entry), second_entries), head_entry, changed_pairs(second_entries, remaining_entries))# Membership diff core; counts cover both inputs.def compare_sorted_entries(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  Make{second_only_entries(first_entries, second_entries), first_only_entries(second_entries, first_entries), changed_pairs(second_entries, first_entries), 0n, Nat.add(List.length(&2, Reading.ChainEntry, first_entries), List.length(&2, Reading.ChainEntry, second_entries))}# Alternates entries into even/odd accumulators, then reverses.def split_step(entries: List<&2, Reading.ChainEntry>, take_head: Bool, evens_accum: List<&2, Reading.ChainEntry>, odds_accum: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry> & List<&2, Reading.ChainEntry>:  match entries:    case Nil{}:      (List.reverse(&2, Reading.ChainEntry, evens_accum), List.reverse(&2, Reading.ChainEntry, odds_accum))    case Con{head_entry, remaining_entries}:      match take_head:        case True{}:          split_step(remaining_entries, False{}, Con{head_entry, evens_accum}, odds_accum)        case False{}:          split_step(remaining_entries, True{}, evens_accum, Con{head_entry, odds_accum})# Splits into balanced halves for any key distribution.def split_entries(+source_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry> & List<&2, Reading.ChainEntry>:  split_step(source_entries, True{}, Nil{}, Nil{})# Copies the spine so each lane scans a private list without atomics.def decide_linear_value(values_equal: Bool, +first_head: Reading.ChainEntry, +second_head: Reading.ChainEntry, +tail_diff: CompareResult) -> CompareResult:  match values_equal:    case True{}:      Make{added_keys_of(tail_diff), removed_keys_of(tail_diff), modified_entries_of(tail_diff), pruned_count_of(tail_diff), Nat.add(2n, compared_entry_count_of(tail_diff))}    case False{}:      Make{added_keys_of(tail_diff), removed_keys_of(tail_diff), Con{Changed{entry_to_logical_key(first_head), Reading.entry_value_of(first_head), Reading.entry_value_of(second_head)}, modified_entries_of(tail_diff)}, pruned_count_of(tail_diff), Nat.add(2n, compared_entry_count_of(tail_diff))}# Merges one step by key order; both sides kept on ties (stable).# @unsafe: calls merge_by_key below (branch-dependent recursion needs the# forward reference); terminates in practice (one side always shrinks).@unsafedef merge_order(ordering: Cmp, first_head: Reading.ChainEntry, first_tail: List<&2, Reading.ChainEntry>, second_head: Reading.ChainEntry, second_tail: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:  match ordering:    case LT{}:      Con{first_head, merge_by_key(first_tail, Con{second_head, second_tail})}    case GT{}:      Con{second_head, merge_by_key(Con{first_head, first_tail}, second_tail)}    case EQ{}:      Con{first_head, Con{second_head, merge_by_key(first_tail, second_tail)}}# Unpacks the key comparison into the ordering step.def merge_dispatch(cmp_result: (String & String) & Cmp, first_head: Reading.ChainEntry, first_tail: List<&2, Reading.ChainEntry>, second_head: Reading.ChainEntry, second_tail: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:  match cmp_result:    case ((returned_first, returned_second), ordering):      merge_order(ordering, first_head, first_tail, second_head, second_tail)# Linear merge of two sorted lists by entry key.# @unsafe: the greater-side branch recurses on a reconstructed list, which# the termination checker cannot see through; one side always shrinks.@unsafedef merge_by_key(first_sorted: List<&2, Reading.ChainEntry>, second_sorted: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:  match first_sorted:    case Nil{}:      second_sorted    case Con{+first_head, first_tail}:      match second_sorted:        case Nil{}:          Con{first_head, first_tail}        case Con{+second_head, second_tail}:          merge_dispatch(String.cmp(Reading.entry_key_of(first_head), Reading.entry_key_of(second_head)), first_head, first_tail, second_head, second_tail)# Merges the sorted halves of one split pair.# @unsafe: calls sort_fuel below (split halves are computed, not structural).@unsafedef sort_split_halves(split_pair: List<&2, Reading.ChainEntry> & List<&2, Reading.ChainEntry>, +remaining_fuel: Nat) -> List<&2, Reading.ChainEntry>:  match split_pair:    case (even_entries, odd_entries):      merge_by_key(sort_fuel(remaining_fuel, even_entries), sort_fuel(remaining_fuel, odd_entries))# Merge sort with Nat fuel; fuel bounds recursion depth, not size.def sort_fuel(remaining_fuel: Nat, unsorted_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:  match remaining_fuel:    case 0n:      unsorted_entries    case 1n+fuel_left:      match unsorted_entries:        case Nil{}:          Nil{}        case Con{single_entry, Nil{}}:          Con{single_entry, Nil{}}        case Con{first_entry, Con{second_entry, remaining_entries}}:          sort_split_halves(split_entries(unsorted_entries), fuel_left)# Sorts entries by key; fuel starts at the entry count.def sort_entries_by_key(+unsorted_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:  sort_fuel(List.length(&2, Reading.ChainEntry, unsorted_entries), unsorted_entries)# Decides one linear-diff step by key order.# @unsafe: calls merge_sorted_diff below (branch-dependent recursion needs# the forward reference); one side always shrinks.@unsafedef decide_linear_order(ordering: Cmp, +first_head: Reading.ChainEntry, first_tail: List<&2, Reading.ChainEntry>, +second_head: Reading.ChainEntry, second_tail: List<&2, Reading.ChainEntry>) -> CompareResult:  match ordering:    case LT{}:      prepend_linear_removed(first_head, merge_sorted_diff(first_tail, Con{second_head, second_tail}))    case GT{}:      prepend_linear_added(second_head, merge_sorted_diff(Con{first_head, first_tail}, second_tail))    case EQ{}:      decide_linear_value(String.eq(Reading.entry_value_of(first_head), Reading.entry_value_of(second_head)), first_head, second_head, merge_sorted_diff(first_tail, second_tail))# Prepends a removed key to a computed tail diff; one entry consumed.def prepend_linear_removed(+head_entry: Reading.ChainEntry, +tail_diff: CompareResult) -> CompareResult:  Make{added_keys_of(tail_diff), Con{entry_to_logical_key(head_entry), removed_keys_of(tail_diff)}, modified_entries_of(tail_diff), pruned_count_of(tail_diff), Nat.add(1n, compared_entry_count_of(tail_diff))}# Prepends an added key to a computed tail diff; one entry consumed.def prepend_linear_added(+head_entry: Reading.ChainEntry, +tail_diff: CompareResult) -> CompareResult:  Make{Con{entry_to_logical_key(head_entry), added_keys_of(tail_diff)}, removed_keys_of(tail_diff), modified_entries_of(tail_diff), pruned_count_of(tail_diff), Nat.add(1n, compared_entry_count_of(tail_diff))}# Unpacks the key comparison into the linear-diff step.def dispatch_linear_diff(cmp_result: (String & String) & Cmp, +first_head: Reading.ChainEntry, first_tail: List<&2, Reading.ChainEntry>, +second_head: Reading.ChainEntry, second_tail: List<&2, Reading.ChainEntry>) -> CompareResult:  match cmp_result:    case ((returned_first, returned_second), ordering):      decide_linear_order(ordering, first_head, first_tail, second_head, second_tail)# Decides one linear-diff step over sorted heads.def linear_diff_heads(+first_head: Reading.ChainEntry, first_tail: List<&2, Reading.ChainEntry>, +second_head: Reading.ChainEntry, second_tail: List<&2, Reading.ChainEntry>) -> CompareResult:  dispatch_linear_diff(String.cmp(Reading.entry_key_of(first_head), Reading.entry_key_of(second_head)), first_head, first_tail, second_head, second_tail)# Linear diff over two sorted lists; counts cover both inputs.def merge_sorted_diff(+first_sorted: List<&2, Reading.ChainEntry>, +second_sorted: List<&2, Reading.ChainEntry>) -> CompareResult:  match first_sorted:    case Nil{}:      Make{second_only_entries(Nil{}, second_sorted), Nil{}, Nil{}, 0n, List.length(&2, Reading.ChainEntry, second_sorted)}    case Con{first_head, first_tail}:      match second_sorted:        case Nil{}:          Make{Nil{}, first_only_entries(Nil{}, Con{first_head, first_tail}), Nil{}, 0n, List.length(&2, Reading.ChainEntry, Con{first_head, first_tail})}        case Con{second_head, second_tail}:          linear_diff_heads(first_head, first_tail, second_head, second_tail)# Sorted-path diff: sorts both lists, then linear-diffs.def compare_entries_sorted(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  merge_sorted_diff(sort_entries_by_key(first_entries), sort_entries_by_key(second_entries))# Routes every compare through the sorted path; fastest at all sizes.def compare_entries_auto(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  compare_entries_sorted(first_entries, second_entries)# Missing trees read as empty entry lists.def entries_or_empty(tree_maybe: Maybe<&2, StateTree.StateTreeNode>) -> List<&2, Reading.ChainEntry>:  match tree_maybe:    case None{}:      Nil{}    case Some{found_tree}:      StateTree.tree_entries(found_tree)# Missing trees hash as the empty string.def hash_or_empty(tree_maybe: Maybe<&2, StateTree.StateTreeNode>) -> String:  match tree_maybe:    case None{}:      ""    case Some{found_tree}:      StateTree.tree_hash_of(found_tree)# Equal hashes yield an empty delta with one prune counted.def pruned_result(first_entries: List<&2, Reading.ChainEntry>, second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  Make{Nil{}, Nil{}, Nil{}, 1n, Nat.add(List.length(&2, Reading.ChainEntry, first_entries), List.length(&2, Reading.ChainEntry, second_entries))}# Missing second tree degrades to a one-sided diff.def pruned_or_present(second_maybe: Maybe<&2, StateTree.StateTreeNode>, first_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  match second_maybe:    case None{}:      compare_entries_auto(first_entries, Nil{})    case Some{second_tree}:      pruned_result(first_entries, StateTree.tree_entries(second_tree))# Missing first tree degrades to a one-sided diff.def pruned_or_empty(first_maybe: Maybe<&2, StateTree.StateTreeNode>, second_maybe: Maybe<&2, StateTree.StateTreeNode>) -> CompareResult:  match first_maybe:    case None{}:      compare_entries_auto(Nil{}, entries_or_empty(second_maybe))    case Some{first_tree}:      pruned_or_present(second_maybe, StateTree.tree_entries(first_tree))# Equal hashes prune; different hashes diff.def dispatch_tree_hashes(hashes_equal: Bool, +first_maybe: Maybe<&2, StateTree.StateTreeNode>, +second_maybe: Maybe<&2, StateTree.StateTreeNode>) -> CompareResult:  match hashes_equal:    case True{}:      pruned_or_empty(first_maybe, second_maybe)    case False{}:      compare_entries_auto(entries_or_empty(first_maybe), entries_or_empty(second_maybe))# Diffs two loaded trees with hash pruning.def compare_loaded_trees(+first_maybe: Maybe<&2, StateTree.StateTreeNode>, +second_maybe: Maybe<&2, StateTree.StateTreeNode>) -> CompareResult:  dispatch_tree_hashes(String.eq(hash_or_empty(first_maybe), hash_or_empty(second_maybe)), first_maybe, second_maybe)# Shell: loads both trees and diffs them.def compare_commits(+first_identifier: String, +second_identifier: String) -> Store.Op<&2, CompareResult>:  do Store.Op<&2, CompareResult>:    first_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(first_identifier)    second_tree_maybe : Maybe<&2, StateTree.StateTreeNode> <- History.read_tree_at(second_identifier)    return compare_loaded_trees(first_tree_maybe, second_tree_maybe)