1	import Base
2	import ./Reading.bend as Reading
3	import ./ContentHash.bend as ContentHash
4	import ./JsonAdapter.bend as JsonAdapter
5	import 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.
14	type 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.
18	def 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.
24	def 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.
30	def 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.
34	def 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.
42	def 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.
46	def 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.
56	def 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.
62	def 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.
70	def 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.
78	def 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.
82	def 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.
90	def 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.
94	def 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.
98	def 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.
106	def 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.
114	def 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.
122	def 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.
130	def 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.
138	def 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.
142	def 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.
150	def 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.
158	def 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.
166	def 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.
170	def 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.
178	def 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.
186	def 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.
194	def 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.
202	def 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.
210	def 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.
218	def 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.
226	def 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.
234	def 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.
242	def 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.
246	def 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.
254	def parse_tree_document(stored_text: String) -> Maybe<&2, StateTreeNode>:
255	  tree_from_parse(JsonAdapter.parse_text(stored_text))