src/scan/ByteRange.bend

mylsm-lsm-store@0.6.0.1 · 129 lines · 17 definitions

1import Base
2import mylsm-lsm-store@0.6.0.1/src/Keys.bend as Keys
3import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
4
5# Reifies two independently owned copies of a byte buffer.
6def 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.
12def 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.
18def 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.
26def 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.
34def 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.
42def 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
49def 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.
55def 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.
62def 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.
70def 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.
80def 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.
88def 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.
94def 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.
103def 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.
107def 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.
117def 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.
128def has_prefix(key: Bytes.Bytes, prefix: Bytes.Bytes) -> Bool:
129  prefix.lengths(Bytes.length(key), Bytes.length(prefix))