src/StateTree.bend
ber-core-store@0.1.1.0 · 255 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/ContentHash.bend as ContentHash
4import ber-core-store@0.1.1.0/src/JsonAdapter.bend as JsonAdapter
5import bend-kit-json@0.3.0.0/json.bend as Json
6
7# Flat sorted state tree (v0.1: no children partitioning). Entries sorted by
8# combined key ("namespace/record"); staged entries win ties. The tree hash
9# covers the flattened entries only, never the JSON text. This module owns
10# both tree directions (serialize + parse); History only calls them.
11# Kit is named for the Val TYPE only; operations go through JsonAdapter.
12
13# Tree hash with sorted entries; children reserved for partitioning.
14type StateTreeNode is Data:
15 Make{tree_hash: String, entries: List<&2, Reading.ChainEntry>, children_hashes: List<&2, String>}
16
17# Projects the entries out of a tree node.
18def tree_entries(tree_node: StateTreeNode) -> List<&2, Reading.ChainEntry>:
19 match tree_node:
20 case Make{tree_hash, entries, children_hashes}:
21 entries
22
23# Projects the hash out of a tree node.
24def tree_hash_of(tree_node: StateTreeNode) -> String:
25 match tree_node:
26 case Make{tree_hash, entries, children_hashes}:
27 tree_hash
28
29# Appends one key=value pair to the flattened text.
30def flatten_head(+head_entry: Reading.ChainEntry, flattened_tail: String) -> String:
31 Reading.entry_key_of(head_entry) ++ "=" ++ Reading.entry_value_of(head_entry) ++ ";" ++ flattened_tail
32
33# Flattens sorted entries into the hashed text.
34def flatten_entries(sorted_entries: List<&2, Reading.ChainEntry>) -> String:
35 match sorted_entries:
36 case Nil{}:
37 ""
38 case Con{head_entry, remaining_entries}:
39 flatten_head(head_entry, flatten_entries(remaining_entries))
40
41# Hashes the flattened entries; the tree address.
42def compute_tree_hash(sorted_entries: List<&2, Reading.ChainEntry>) -> String:
43 ContentHash.compute_sha256_hex(flatten_entries(sorted_entries))
44
45# Merges one step by key order; staged wins ties.
46def decide_ordering(ordering: Cmp, base_head: Reading.ChainEntry, base_tail: List<&2, Reading.ChainEntry>, staged_head: Reading.ChainEntry, inserted_tail: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:
47 match ordering:
48 case LT{}:
49 Con{base_head, inserted_tail}
50 case GT{}:
51 Con{staged_head, Con{base_head, base_tail}}
52 case EQ{}:
53 Con{staged_head, base_tail}
54
55# Unpacks the comparison result into the ordering step.
56def decide_insert(cmp_result: (String & String) & Cmp, base_head: Reading.ChainEntry, base_tail: List<&2, Reading.ChainEntry>, staged_head: Reading.ChainEntry, inserted_tail: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:
57 match cmp_result:
58 case ((returned_first, returned_second), ordering):
59 decide_ordering(ordering, base_head, base_tail, staged_head, inserted_tail)
60
61# Inserts one staged entry into sorted position.
62def insert_single_entry(base_entries: List<&2, Reading.ChainEntry>, +staged_head: Reading.ChainEntry) -> List<&2, Reading.ChainEntry>:
63 match base_entries:
64 case Nil{}:
65 Con{staged_head, Nil{}}
66 case Con{+base_head, +base_tail}:
67 decide_insert(String.cmp(Reading.entry_key_of(base_head), Reading.entry_key_of(staged_head)), base_head, base_tail, staged_head, insert_single_entry(base_tail, staged_head))
68
69# Folds staged entries into the base list, sorted.
70def merge_sorted_entries(staged_entries: List<&2, Reading.ChainEntry>, base_entries: List<&2, Reading.ChainEntry>) -> List<&2, Reading.ChainEntry>:
71 match staged_entries:
72 case Nil{}:
73 base_entries
74 case Con{staged_head, staged_tail}:
75 merge_sorted_entries(staged_tail, insert_single_entry(base_entries, staged_head))
76
77# Encodes one entry as a two-item JSON array.
78def entry_pair_to_json(+head_entry: Reading.ChainEntry) -> Json.Val:
79 JsonAdapter.make_arr(Con{JsonAdapter.make_str(Reading.entry_key_of(head_entry)), Con{JsonAdapter.make_str(Reading.entry_value_of(head_entry)), Nil{}}})
80
81# Encodes the entry list as a JSON array.
82def entry_list_to_json(sorted_entries: List<&2, Reading.ChainEntry>) -> List<&2, Json.Val>:
83 match sorted_entries:
84 case Nil{}:
85 Nil{}
86 case Con{head_entry, remaining_entries}:
87 Con{entry_pair_to_json(head_entry), entry_list_to_json(remaining_entries)}
88
89# Encodes the hash/entries/children document canonically.
90def finalize_tree_document(hash_field: Sigma<&2, &2, String, _ => Json.Val>, entries_field: Sigma<&2, &2, String, _ => Json.Val>, children_field: Sigma<&2, &2, String, _ => Json.Val>) -> String:
91 JsonAdapter.encode_canonical(JsonAdapter.make_obj(Con{hash_field, Con{entries_field, Con{children_field, Nil{}}}}))
92
93# Serializes a merged entry list with its hash.
94def serialize_tree(+merged_entries: List<&2, Reading.ChainEntry>, +tree_hash_value: String) -> String:
95 finalize_tree_document(JsonAdapter.make_kv("hash", JsonAdapter.make_str(tree_hash_value)), JsonAdapter.make_kv("entries", JsonAdapter.make_arr(entry_list_to_json(merged_entries))), JsonAdapter.make_kv("children", JsonAdapter.make_arr(Nil{})))
96
97# Conses a decoded pair onto the tail.
98def prepend_entry_pair(key_text: String, value_text: String, parsed_tail: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
99 match parsed_tail:
100 case None{}:
101 None{}
102 case Some{tail_entries}:
103 Some{Con{Reading.make_entry(key_text, value_text), tail_entries}}
104
105# Unwraps the value text, then prepends.
106def prepend_value_text(key_text: String, value_maybe: Maybe<&2, String>, parsed_tail: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
107 match value_maybe:
108 case None{}:
109 None{}
110 case Some{value_text}:
111 prepend_entry_pair(key_text, value_text, parsed_tail)
112
113# Unwraps the key text, then continues.
114def prepend_pair_texts(key_maybe: Maybe<&2, String>, value_maybe: Maybe<&2, String>, parsed_tail: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
115 match key_maybe:
116 case None{}:
117 None{}
118 case Some{key_text}:
119 prepend_value_text(key_text, value_maybe, parsed_tail)
120
121# Decodes one [key, value] array; None on wrong shape.
122def prepend_pair_items(pair_items: List<&2, Json.Val>, parsed_tail: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
123 match pair_items:
124 case Con{key_json, Con{value_json, Nil{}}}:
125 prepend_pair_texts(JsonAdapter.as_str(key_json), JsonAdapter.as_str(value_json), parsed_tail)
126 case _:
127 None{}
128
129# Unwraps the pair array, then decodes.
130def prepend_parsed_pair(pair_maybe: Maybe<&2, List<&2, Json.Val>>, parsed_tail: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
131 match pair_maybe:
132 case None{}:
133 None{}
134 case Some{pair_items}:
135 prepend_pair_items(pair_items, parsed_tail)
136
137# Decodes one entry item.
138def prepend_parsed_entry(head_item: Json.Val, parsed_tail: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
139 prepend_parsed_pair(JsonAdapter.as_arr(head_item), parsed_tail)
140
141# Decodes the entry array; None on any bad item.
142def parse_entry_list(entry_items: List<&2, Json.Val>) -> Maybe<&2, List<&2, Reading.ChainEntry>>:
143 match entry_items:
144 case Nil{}:
145 Some{Nil{}}
146 case Con{head_item, remaining_items}:
147 prepend_parsed_entry(head_item, parse_entry_list(remaining_items))
148
149# Conses a decoded hash onto the tail.
150def prepend_child_tail(head_text: String, parsed_tail: Maybe<&2, List<&2, String>>) -> Maybe<&2, List<&2, String>>:
151 match parsed_tail:
152 case None{}:
153 None{}
154 case Some{tail_texts}:
155 Some{Con{head_text, tail_texts}}
156
157# Unwraps the child hash text, then prepends.
158def prepend_child_text(head_maybe: Maybe<&2, String>, parsed_tail: Maybe<&2, List<&2, String>>) -> Maybe<&2, List<&2, String>>:
159 match head_maybe:
160 case None{}:
161 None{}
162 case Some{head_text}:
163 prepend_child_tail(head_text, parsed_tail)
164
165# Decodes one child-hash item.
166def prepend_child_string(head_item: Json.Val, parsed_tail: Maybe<&2, List<&2, String>>) -> Maybe<&2, List<&2, String>>:
167 prepend_child_text(JsonAdapter.as_str(head_item), parsed_tail)
168
169# Decodes the children array; None on any non-string.
170def extract_child_strings(child_items: List<&2, Json.Val>) -> Maybe<&2, List<&2, String>>:
171 match child_items:
172 case Nil{}:
173 Some{Nil{}}
174 case Con{head_item, remaining_items}:
175 prepend_child_string(head_item, extract_child_strings(remaining_items))
176
177# Reassembles the node once children decode.
178def finish_tree_node(tree_hash_text: String, parsed_entries: List<&2, Reading.ChainEntry>, strings_maybe: Maybe<&2, List<&2, String>>) -> Maybe<&2, StateTreeNode>:
179 match strings_maybe:
180 case None{}:
181 None{}
182 case Some{child_hashes}:
183 Some{Make{tree_hash_text, parsed_entries, child_hashes}}
184
185# Unwraps the children array items, then finishes.
186def finish_children_strings(tree_hash_text: String, parsed_entries: List<&2, Reading.ChainEntry>, items_maybe: Maybe<&2, List<&2, Json.Val>>) -> Maybe<&2, StateTreeNode>:
187 match items_maybe:
188 case None{}:
189 None{}
190 case Some{child_items}:
191 finish_tree_node(tree_hash_text, parsed_entries, extract_child_strings(child_items))
192
193# Unwraps the children field, then continues.
194def extract_children_array(tree_hash_text: String, parsed_entries: List<&2, Reading.ChainEntry>, children_maybe: Maybe<&2, Json.Val>) -> Maybe<&2, StateTreeNode>:
195 match children_maybe:
196 case None{}:
197 None{}
198 case Some{children_json}:
199 finish_children_strings(tree_hash_text, parsed_entries, JsonAdapter.as_arr(children_json))
200
201# Unwraps parsed entries, then reads children.
202def extract_children(+document: Json.Val, tree_hash_text: String, entries_maybe: Maybe<&2, List<&2, Reading.ChainEntry>>) -> Maybe<&2, StateTreeNode>:
203 match entries_maybe:
204 case None{}:
205 None{}
206 case Some{parsed_entries}:
207 extract_children_array(tree_hash_text, parsed_entries, JsonAdapter.get_field(document, "children"))
208
209# Unwraps the entry items, then parses.
210def extract_entry_items(+document: Json.Val, tree_hash_text: String, items_maybe: Maybe<&2, List<&2, Json.Val>>) -> Maybe<&2, StateTreeNode>:
211 match items_maybe:
212 case None{}:
213 None{}
214 case Some{entry_items}:
215 extract_children(document, tree_hash_text, parse_entry_list(entry_items))
216
217# Unwraps the entries field, then continues.
218def extract_entry_array(+document: Json.Val, tree_hash_text: String, entries_maybe: Maybe<&2, Json.Val>) -> Maybe<&2, StateTreeNode>:
219 match entries_maybe:
220 case None{}:
221 None{}
222 case Some{entries_json}:
223 extract_entry_items(document, tree_hash_text, JsonAdapter.as_arr(entries_json))
224
225# Unwraps the hash text, then reads entries.
226def extract_with_tree_entries(+document: Json.Val, hash_text_maybe: Maybe<&2, String>, entries_maybe: Maybe<&2, Json.Val>) -> Maybe<&2, StateTreeNode>:
227 match hash_text_maybe:
228 case None{}:
229 None{}
230 case Some{tree_hash_text}:
231 extract_entry_array(document, tree_hash_text, entries_maybe)
232
233# Unwraps the hash field, then continues.
234def extract_with_tree_hash(+document: Json.Val, hash_maybe: Maybe<&2, Json.Val>) -> Maybe<&2, StateTreeNode>:
235 match hash_maybe:
236 case None{}:
237 None{}
238 case Some{hash_json}:
239 extract_with_tree_entries(document, JsonAdapter.as_str(hash_json), JsonAdapter.get_field(document, "entries"))
240
241# Reads the hash field of the document.
242def extract_tree_fields(+document: Json.Val) -> Maybe<&2, StateTreeNode>:
243 extract_with_tree_hash(document, JsonAdapter.get_field(document, "hash"))
244
245# Builds the node from parsed JSON; None on malformed input.
246def tree_from_parse(parse_result: Maybe<&2, Json.Val>) -> Maybe<&2, StateTreeNode>:
247 match parse_result:
248 case None{}:
249 None{}
250 case Some{+document}:
251 extract_tree_fields(document)
252
253# Parses stored tree text into a node.
254def parse_tree_document(stored_text: String) -> Maybe<&2, StateTreeNode>:
255 tree_from_parse(JsonAdapter.parse_text(stored_text))