1	import Base
2	
3	# Pure chain-reading cores; LAWS.bend quantifies over these, never over IO.
4	# Entries are a named Data constructor because a & pair defaults to kind
5	# Type, which List<&2, _> rejects.
6	type ChainEntry is Data:
7	  Entry{entry_key: String, entry_value: String}
8	
9	# Builds the "namespace/record" lookup key.
10	def encode_lookup_key(+namespace_name: String, +record_identifier: String) -> String:
11	  namespace_name ++ "/" ++ record_identifier
12	
13	# Some on match, otherwise the recursive fallback.
14	def pick_match(key_matches: Bool, stored_value: String, fallback: Maybe<&2, String>) -> Maybe<&2, String>:
15	  match key_matches:
16	    case True{}:
17	      Some{stored_value}
18	    case False{}:
19	      fallback
20	
21	# Most-recent-wins: the head of the chain is the newest commit.
22	def lookup_in_chain(+namespace_name: String, +record_identifier: String, ancestor_chain: List<&2, ChainEntry>) -> Maybe<&2, String>:
23	  match ancestor_chain:
24	    case Nil{}:
25	      None{}
26	    case Con{head_entry, remaining_chain}:
27	      match head_entry:
28	        case Entry{entry_key, entry_value}:
29	          pick_match(String.eq(entry_key, encode_lookup_key(namespace_name, record_identifier)), entry_value, lookup_in_chain(namespace_name, record_identifier, remaining_chain))
30	
31	# A tombstone reads as absent; any other value survives.
32	def drop_tombstone(is_tombstone: Bool, stored_value: String) -> Maybe<&2, String>:
33	  match is_tombstone:
34	    case True{}:
35	      None{}
36	    case False{}:
37	      Some{stored_value}
38	
39	# Maps the TOMBSTONE sentinel to None.
40	def resolve_tombstone(maybe_value: Maybe<&2, String>) -> Maybe<&2, String>:
41	  match maybe_value:
42	    case None{}:
43	      None{}
44	    case Some{+stored_value}:
45	      drop_tombstone(String.eq(stored_value, "TOMBSTONE"), stored_value)
46	
47	# Drops the entry on match, keeps it otherwise.
48	def drop_or_keep(is_match: Bool, stored_key: String, stored_value: String, filtered_tail: List<&2, ChainEntry>) -> List<&2, ChainEntry>:
49	  match is_match:
50	    case True{}:
51	      filtered_tail
52	    case False{}:
53	      Con{Entry{stored_key, stored_value}, filtered_tail}
54	
55	# Removes the head entry when its key equals the target.
56	def filter_entry(head_entry: ChainEntry, filtered_tail: List<&2, ChainEntry>, target_key: String) -> List<&2, ChainEntry>:
57	  match head_entry:
58	    case Entry{+entry_key, +entry_value}:
59	      drop_or_keep(String.eq(entry_key, target_key), entry_key, entry_value, filtered_tail)
60	
61	# Removes every entry whose key equals the target.
62	def remove_key_matches(+target_key: String, ancestor_chain: List<&2, ChainEntry>) -> List<&2, ChainEntry>:
63	  match ancestor_chain:
64	    case Nil{}:
65	      Nil{}
66	    case Con{head_entry, remaining_chain}:
67	      filter_entry(head_entry, remove_key_matches(target_key, remaining_chain), target_key)
68	
69	# Keeps the head and drops its older duplicates from the normalized tail.
70	def attach_head(head_entry: ChainEntry, normalized_tail: List<&2, ChainEntry>) -> List<&2, ChainEntry>:
71	  match head_entry:
72	    case Entry{+entry_key, +entry_value}:
73	      Con{Entry{entry_key, entry_value}, remove_key_matches(entry_key, normalized_tail)}
74	
75	# Drops older duplicates, keeping the first (newest) occurrence of each key.
76	def normalize_chain(ancestor_chain: List<&2, ChainEntry>) -> List<&2, ChainEntry>:
77	  match ancestor_chain:
78	    case Nil{}:
79	      Nil{}
80	    case Con{head_entry, remaining_chain}:
81	      attach_head(head_entry, normalize_chain(remaining_chain))
82	
83	# Shared vocabulary: other modules build ChainEntry through this constructor.
84	def make_entry(entry_key: String, entry_value: String) -> ChainEntry:
85	  Entry{entry_key, entry_value}
86	
87	# Projects the key out of an entry.
88	def entry_key_of(chain_entry: ChainEntry) -> String:
89	  match chain_entry:
90	    case Entry{entry_key, entry_value}:
91	      entry_key
92	
93	# Projects the value out of an entry.
94	def entry_value_of(chain_entry: ChainEntry) -> String:
95	  match chain_entry:
96	    case Entry{entry_key, entry_value}:
97	      entry_value