src/StorageBytes.bend
mylsm-lsm-store@0.4.0.0 · 212 lines · 0 definitions
1import Base
2import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
3
4# State for the strict single-pass UTF-8 decoder.
5type Utf8State is Data:
6 Utf8State{need: U32, lo: U32, hi: U32, cp: U32, out: String, valid: Bool}
7
8def utf8.lead(+byte: U32, +out: String) -> Utf8State:
9 Utf8State{
10 Bool.pick(U32,
11 U32.is_lt(byte, 128), 0,
12 Bool.pick(U32, U32.is_le(194, byte) && U32.is_le(byte, 223), 1,
13 Bool.pick(U32, U32.is_eq(byte, 224) || U32.is_le(225, byte) && U32.is_le(byte, 236) || U32.is_le(238, byte) && U32.is_le(byte, 239) || U32.is_eq(byte, 237), 2,
14 Bool.pick(U32, U32.is_le(240, byte) && U32.is_le(byte, 244), 3, 0)))),
15 Bool.pick(U32, U32.is_eq(byte, 224), 160,
16 Bool.pick(U32, U32.is_eq(byte, 240), 144, 128)),
17 Bool.pick(U32, U32.is_eq(byte, 237), 159,
18 Bool.pick(U32, U32.is_eq(byte, 244), 143, 191)),
19 Bool.pick(U32,
20 U32.is_lt(byte, 128), byte,
21 Bool.pick(U32, U32.is_le(194, byte) && U32.is_le(byte, 223), U32.and(byte, 31),
22 Bool.pick(U32, U32.is_le(224, byte) && U32.is_le(byte, 239), U32.and(byte, 15),
23 Bool.pick(U32, U32.is_le(240, byte) && U32.is_le(byte, 244), U32.and(byte, 7), 0)))),
24 Bool.pick(String, U32.is_lt(byte, 128), SCon{Chr{byte}, out}, out),
25 U32.is_lt(byte, 128) || U32.is_le(194, byte) && U32.is_le(byte, 244)
26 }
27
28def utf8.cont(+need: U32, cp: U32, +out: String, ok: Bool, in_range: Bool, byte: U32) -> Utf8State:
29 match in_range:
30 case True{}:
31 +next_cp = (cp * 64 + U32.and(byte, 63) : U32)
32 Utf8State{(need - 1 : U32), 128, 191, next_cp,
33 Bool.pick(String, U32.is_eq(need, 1), SCon{Chr{next_cp}, out}, out), ok}
34 case False{}:
35 Utf8State{0, 128, 191, 0, out, False{}}
36
37def utf8.step(state: Utf8State, +byte: U32) -> Utf8State:
38 match state:
39 case Utf8State{0, _, _, _, out, True{}}:
40 utf8.lead(byte, out)
41 case Utf8State{0, _, _, _, out, False{}}:
42 Utf8State{0, 128, 191, 0, out, False{}}
43 case Utf8State{need, lo, hi, cp, out, ok}:
44 utf8.cont(need, cp, out, ok, U32.is_le(lo, byte) && U32.is_le(byte, hi), byte)
45
46def utf8.scan.fin.done(out: String, complete: Bool) -> Result<&1, &1, U32 & String, String>:
47 match complete:
48 case True{}:
49 Done{String.reverse(out)}
50 case False{}:
51 Fail{(1, "invalid UTF-8")}
52
53def utf8.scan.fin(state: Utf8State) -> Result<&1, &1, U32 & String, String>:
54 match state:
55 case Utf8State{need, _, _, _, out, True{}}:
56 utf8.scan.fin.done(out, U32.is_eq(need, 0))
57 case Utf8State{_, _, _, _, _, False{}}:
58 Fail{(1, "invalid UTF-8")}
59
60def utf8.scan(
61 remaining: Nat,
62 +offset: U32,
63 pair: Array<U32> & U32,
64 state: Utf8State
65) -> Result<&1, &1, U32 & String, String>:
66 match remaining:
67 case 0n:
68 match pair:
69 case (_, _):
70 utf8.scan.fin(state)
71 case 1n+p:
72 match pair:
73 case (buf, b):
74 utf8.scan(p, (offset + 1 : U32), Bytes.peek(buf, (offset + 1 : U32)), utf8.step(state, b))
75
76# Return None rather than wrapping when U32 addition overflows.
77def checked_add(+left: U32, +right: U32) -> Maybe<&2, U32>:
78 Bool.pick(Maybe<&2, U32>, U32.is_le(left, (4294967295 - right : U32)), Some{(left + right : U32)}, None{})
79
80# Normal target size for an encoded storage block or WAL frame.
81def MAX_BLOCK_BYTES() -> U32:
82 1048576
83
84# Hard cap for an individual encoded key or value.
85def MAX_RECORD_BYTES() -> U32:
86 1073741824
87
88# Hard cap for the complete serialized Manifest.
89def MAX_MANIFEST_BYTES() -> U32:
90 1048576
91
92def utf8.width(+scalar: U32) -> U32:
93 Bool.pick(U32, U32.is_le(scalar, 127), 1,
94 Bool.pick(U32, U32.is_le(scalar, 2047), 2,
95 Bool.pick(U32, U32.is_le(scalar, 65535), 3, 4)))
96
97def from_string.size(+text: String, +size: U32, fits: Bool) -> Maybe<&2, U32>:
98 match text fits:
99 case SNil{} _:
100 Some{size}
101 case SCon{Chr{_scalar}, SNil{}} False{}:
102 None{}
103 case SCon{Chr{scalar}, SNil{}} True{}:
104 Some{(size + utf8.width(scalar) : U32)}
105 case SCon{Chr{_scalar}, SCon{Chr{_next_scalar}, _rest}} False{}:
106 None{}
107 case SCon{Chr{scalar}, SCon{Chr{next_scalar}, rest}} True{}:
108 from_string.size(SCon{Chr{next_scalar}, rest}, (size + utf8.width(scalar) : U32),
109 U32.is_le((size + utf8.width(scalar) : U32),
110 (MAX_RECORD_BYTES() - utf8.width(next_scalar) : U32)))
111
112def from_string.size.begin(+text: String) -> Maybe<&2, U32>:
113 match text:
114 case SNil{}:
115 Some{0}
116 case SCon{Chr{scalar}, _}:
117 from_string.size(text, 0,
118 U32.is_le(0, (MAX_RECORD_BYTES() - utf8.width(scalar) : U32)))
119
120# Reject text fields outside the configured storage record cap.
121def from_string.checked(+len: U32, buf: Array<U32>) -> Result<&1, &1, U32 & String, Bytes.Bytes>:
122 Bool.pick(Result<&1, &1, U32 & String, Bytes.Bytes>,
123 U32.is_le(len, MAX_RECORD_BYTES()),
124 Done{Bytes.Bytes{len, buf}}, Fail{(2, "record too large")})
125
126def utf8.put.result(pair: Bytes.Cursor & Bool) -> Bytes.Cursor:
127 match pair:
128 case (cursor, _):
129 cursor
130
131def utf8.put.byte(cursor: Bytes.Cursor, +byte: U32) -> Bytes.Cursor:
132 utf8.put.result(Bytes.Cursor.put.u8(cursor, byte))
133
134def utf8.put.two(cursor: Bytes.Cursor, +scalar: U32) -> Bytes.Cursor:
135 utf8.put.byte(utf8.put.byte(cursor, (192 + U32.shrn(scalar, 6n) : U32)),
136 (128 + U32.and(scalar, 63) : U32))
137
138def utf8.put.three(cursor: Bytes.Cursor, +scalar: U32) -> Bytes.Cursor:
139 utf8.put.byte(utf8.put.byte(
140 utf8.put.byte(cursor, (224 + U32.shrn(scalar, 12n) : U32)),
141 (128 + U32.and(U32.shrn(scalar, 6n), 63) : U32)),
142 (128 + U32.and(scalar, 63) : U32))
143
144def utf8.put.four(cursor: Bytes.Cursor, +scalar: U32) -> Bytes.Cursor:
145 utf8.put.byte(utf8.put.byte(
146 utf8.put.byte(utf8.put.byte(cursor, (240 + U32.shrn(scalar, 18n) : U32)),
147 (128 + U32.and(U32.shrn(scalar, 12n), 63) : U32)),
148 (128 + U32.and(U32.shrn(scalar, 6n), 63) : U32)),
149 (128 + U32.and(scalar, 63) : U32))
150
151def utf8.put.scalar(
152 cursor: Bytes.Cursor,
153 +scalar: U32,
154 ascii: Bool,
155 two_byte: Bool,
156 three_byte: Bool
157) -> Bytes.Cursor:
158 match ascii two_byte three_byte:
159 case True{} _ _:
160 utf8.put.byte(cursor, scalar)
161 case False{} True{} _:
162 utf8.put.two(cursor, scalar)
163 case False{} False{} True{}:
164 utf8.put.three(cursor, scalar)
165 case False{} False{} False{}:
166 utf8.put.four(cursor, scalar)
167
168def utf8.encode.go(text: String, cursor: Bytes.Cursor) -> Bytes.Cursor:
169 match text:
170 case SNil{}:
171 cursor
172 case SCon{Chr{+scalar}, tail}:
173 utf8.encode.go(tail, utf8.put.scalar(cursor, scalar,
174 U32.is_le(scalar, 127), U32.is_le(scalar, 2047), U32.is_le(scalar, 65535)))
175
176def from_string.output.pair(result: Bytes.Bytes & U32) -> Bytes.Bytes:
177 match result:
178 case (bytes, _):
179 bytes
180
181def from_string.output(+text: String, +len: U32) -> Bytes.Bytes:
182 from_string.output.pair(Bytes.Cursor.finish(utf8.encode.go(text,
183 Bytes.Cursor.new(Bytes.Bytes{len, Bytes.alloc(len)}))))
184
185def from_string.preflight(+text: String, size: Maybe<&2, U32>) -> Result<&1, &1, U32 & String, Bytes.Bytes>:
186 match size:
187 case None{}:
188 Fail{(2, "record too large")}
189 case Some{len}:
190 Done{from_string.output(text, len)}
191
192# Encode public text at the packed storage boundary.
193def from_string(+text: String) -> Result<&1, &1, U32 & String, Bytes.Bytes>:
194 from_string.preflight(text, from_string.size.begin(text))
195
196# Decode bytes after strict RFC 3629 validation.
197def decode_checked(bytes: Bytes.Bytes) -> Result<&1, &1, U32 & String, String>:
198 match bytes:
199 case Bytes.Bytes{len, buf}:
200 utf8.scan(U32.to_nat(len), 0, Bytes.peek(buf, 0), Utf8State{0, 128, 191, 0, SNil{}, True{}})
201
202# Decode a packed buffer, rejecting malformed UTF-8.
203def to_string_strict(bytes: Bytes.Bytes) -> Result<&1, &1, U32 & String, String>:
204 decode_checked(bytes)
205
206# Read one bounded big-endian u32 through a package cursor.
207def read_u32be(cursor: Bytes.Cursor) -> Bytes.Cursor & Maybe<&2, U32>:
208 Bytes.Cursor.u32be(cursor)
209
210# Write one bounded big-endian u32 through a package cursor.
211def write_u32be(cursor: Bytes.Cursor, value: U32) -> Bytes.Cursor & Bool:
212 Bytes.Cursor.put.u32be(cursor, value)