1	import Base
2	import ../Keys.bend as Keys
3	import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
4	
5	# Reifies two independently owned copies of a byte buffer.
6	def clone.pair(+len: U32, copied: Array<U32> & Array<U32>) -> Bytes.Bytes & Bytes.Bytes:
7	  match copied:
8	    case (left, right):
9	      (Bytes.Bytes{len, left}, Bytes.Bytes{len, right})
10	
11	# Clones a byte buffer when range checks need both bounds.
12	def clone.split(bytes: Bytes.Bytes) -> Bytes.Bytes & Bytes.Bytes:
13	  match bytes:
14	    case Bytes.Bytes{+len, buf}:
15	      clone.pair(len, Bytes.copy.bytes(len, buf, Bytes.alloc(len), 0, 0))
16	
17	# Returns whether a key satisfies an optional inclusive lower bound.
18	def lower.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
19	  match comparison:
20	    case (_, _, LT{}):
21	      False{}
22	    case _:
23	      True{}
24	
25	# Checks an optional lower bound using the canonical byte comparator.
26	def lower(key: Bytes.Bytes, bound: Maybe<&1, Bytes.Bytes>) -> Bool:
27	  match bound:
28	    case None{}:
29	      True{}
30	    case Some{value}:
31	      lower.result(Keys.Bytes.cmp.with_inputs(key, value))
32	
33	# Returns whether a key sorts strictly below an optional upper bound.
34	def upper.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
35	  match comparison:
36	    case (_, _, LT{}):
37	      True{}
38	    case _:
39	      False{}
40	
41	# Checks an optional exclusive upper bound using byte order.
42	def upper(key: Bytes.Bytes, bound: Maybe<&1, Bytes.Bytes>) -> Bool:
43	  match bound:
44	    case None{}:
45	      True{}
46	    case Some{value}:
47	      upper.result(Keys.Bytes.cmp.with_inputs(key, value))
48	
49	def at_or_after_upper.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
50	  match comparison:
51	    case (_, _, LT{}): False{}
52	    case _: True{}
53	
54	# Detects the first ordered key that cannot belong to a half-open range.
55	def at_or_after_upper(key: Bytes.Bytes, bound: Maybe<&1, Bytes.Bytes>) -> Bool:
56	  match bound:
57	    case None{}: False{}
58	    case Some{value}:
59	      at_or_after_upper.result(Keys.Bytes.cmp.with_inputs(key, value))
60	
61	# Combines the lower and upper checks for a half-open range.
62	def in_range.checked(lower_ok: Bool, upper_ok: Bool) -> Bool:
63	  match lower_ok:
64	    case True{}:
65	      upper_ok
66	    case False{}:
67	      False{}
68	
69	# Checks a byte key against optional [lower, upper) bounds.
70	def in_range.copies(
71	  copies: Bytes.Bytes & Bytes.Bytes,
72	  lower_bound: Maybe<&1, Bytes.Bytes>,
73	  upper_bound: Maybe<&1, Bytes.Bytes>
74	) -> Bool:
75	  match copies:
76	    case (lower_key, upper_key):
77	      in_range.checked(lower(lower_key, lower_bound), upper(upper_key, upper_bound))
78	
79	# Checks a byte key against optional [lower, upper) bounds.
80	def in_range(
81	  key: Bytes.Bytes,
82	  lower_bound: Maybe<&1, Bytes.Bytes>,
83	  upper_bound: Maybe<&1, Bytes.Bytes>
84	) -> Bool:
85	  in_range.copies(clone.split(key), lower_bound, upper_bound)
86	
87	# Returns the equality component while consuming both preserved buffers.
88	def prefix.equal(result: Bytes.Bytes & Bytes.Bytes & Bool) -> Bool:
89	  match result:
90	    case (_, _, equal):
91	      equal
92	
93	# Compares a bounded key prefix with the requested bytes.
94	def prefix.slice.result(
95	  prefix: Bytes.Bytes,
96	  pair: Bytes.Bytes & Bytes.Bytes
97	) -> Bool:
98	  match pair:
99	    case (_, sliced):
100	      prefix.equal(Bytes.eq(sliced, prefix))
101	
102	# Slices exactly the requested prefix length and compares the resulting bytes.
103	def prefix.slice(key: Bytes.Bytes, prefix: Bytes.Bytes, +prefix_len: U32) -> Bool:
104	  prefix.slice.result(prefix, Bytes.slice(key, 0, prefix_len))
105	
106	# Rejects prefixes longer than the key before slicing.
107	def prefix.length.checked(
108	  key: Bytes.Bytes,
109	  prefix: Bytes.Bytes,
110	  +prefix_len: U32,
111	  +key_len: U32
112	) -> Bool:
113	  Bool.pick(Bool, U32.is_le(prefix_len, key_len),
114	    prefix.slice(key, prefix, prefix_len), False{})
115	
116	# Unpacks measured key and prefix lengths before comparison.
117	def prefix.lengths(
118	  key_pair: Bytes.Bytes & U32,
119	  prefix_pair: Bytes.Bytes & U32
120	) -> Bool:
121	  match key_pair:
122	    case (key, key_len):
123	      match prefix_pair:
124	        case (prefix, prefix_len):
125	          prefix.length.checked(key, prefix, prefix_len, key_len)
126	
127	# Checks whether a byte key begins with the exact byte prefix.
128	def has_prefix(key: Bytes.Bytes, prefix: Bytes.Bytes) -> Bool:
129	  prefix.lengths(Bytes.length(key), Bytes.length(prefix))