~/bend-docscommunity

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{})# Compares both halves against the reference in parallel.def fan_added_halves(even_entries: List<&2, Reading.ChainEntry>, odd_entries: List<&2, Reading.ChainEntry>, +reference_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  even_added odd_added = second_only_entries(reference_entries, even_entries) second_only_entries(reference_entries, odd_entries)  List.append(&2, LogicalKey.LogicalKey, even_added, odd_added)# Unpacks the split pair into the fanned added step.def fan_out_pair(split_pair: List<&2, Reading.ChainEntry> & List<&2, Reading.ChainEntry>, +reference_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  match split_pair:    case (even_entries, odd_entries):      fan_added_halves(even_entries, odd_entries, reference_entries)# Fanned added-set computation.def fan_added_entries(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  fan_out_pair(split_entries(second_entries), first_entries)# Compares both halves against the reference in parallel.def fan_removed_halves(even_entries: List<&2, Reading.ChainEntry>, odd_entries: List<&2, Reading.ChainEntry>, +reference_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  even_removed odd_removed = first_only_entries(reference_entries, even_entries) first_only_entries(reference_entries, odd_entries)  List.append(&2, LogicalKey.LogicalKey, even_removed, odd_removed)# Unpacks the split pair into the fanned removed step.def fan_out_removed(split_pair: List<&2, Reading.ChainEntry> & List<&2, Reading.ChainEntry>, +reference_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  match split_pair:    case (even_entries, odd_entries):      fan_removed_halves(even_entries, odd_entries, reference_entries)# Fanned removed-set computation.def fan_removed_entries(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> List<&2, LogicalKey.LogicalKey>:  fan_out_removed(split_entries(first_entries), second_entries)# Compares both halves against the reference in parallel.def fan_modified_halves(even_entries: List<&2, Reading.ChainEntry>, odd_entries: List<&2, Reading.ChainEntry>, +reference_entries: List<&2, Reading.ChainEntry>) -> List<&2, ModifiedEntry>:  even_modified odd_modified = changed_pairs(reference_entries, even_entries) changed_pairs(reference_entries, odd_entries)  List.append(&2, ModifiedEntry, even_modified, odd_modified)# Unpacks the split pair into the fanned modified step.def fan_out_modified(split_pair: List<&2, Reading.ChainEntry> & List<&2, Reading.ChainEntry>, +reference_entries: List<&2, Reading.ChainEntry>) -> List<&2, ModifiedEntry>:  match split_pair:    case (even_entries, odd_entries):      fan_modified_halves(even_entries, odd_entries, reference_entries)# Fanned modified-set computation.def fan_modified_entries(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> List<&2, ModifiedEntry>:  fan_out_modified(split_entries(first_entries), second_entries)# Parallel diff; sets and counts agree with sequential.def compare_entries_fanned(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  Make{fan_added_entries(first_entries, second_entries), fan_removed_entries(first_entries, second_entries), fan_modified_entries(first_entries, second_entries), 0n, Nat.add(List.length(&2, Reading.ChainEntry, first_entries), List.length(&2, Reading.ChainEntry, second_entries))}# Entry count above which compare fans out.def comparison_parallel_threshold() -> Nat:  1024n# Fans out only past the threshold.def decide_fan_out(is_large: Bool, +first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  match is_large:    case True{}:      compare_entries_fanned(first_entries, second_entries)    case False{}:      compare_sorted_entries(first_entries, second_entries)# Chooses sequential or fanned compare by size.def compare_entries_auto(+first_entries: List<&2, Reading.ChainEntry>, +second_entries: List<&2, Reading.ChainEntry>) -> CompareResult:  decide_fan_out(Nat.is_ge(List.length(&2, Reading.ChainEntry, first_entries), comparison_parallel_threshold()), 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)