Debian Codegraph @

bytes/tokenize.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use types;
5
6 export type tokenizer = struct {
7 in: []u8, // string being tokenized
8 delim: []u8, // delimiter
9 p: i64, // p < 0 for reverse tokenizers, 0 <= p for forward ones.
10 };
11
12 // Tokenizes a byte slice, returning an iterator that yields tokens from the
13 // slice delimited by one of any number of delimiter bytes. If the input slice
14 // begins with or ends with a delimiter, an empty slice is returned respectively
15 // as the first and last call to [[next_token]].
16 //
17 // The variadic argument slice is borrowed from the caller, who should take care
18 // to ensure that it is valid for the lifetime of the tokenizer.
19 //
20 // The caller must ensure that at least one delimiter is provided and that the
21 // length of the slice is less than [[types::I64_MAX]].
22 export fn tokenize(in: []u8, delim: u8...) tokenizer = {
23 assert(len(delim) > 0, "bytes::tokenize called with empty slice");
24 assert(len(in) < types::I64_MAX: size,
25 "bytes::tokenize: input length exceeds I64_MAX");
26 if (len(in) == 0) {
27 delim = [];
28 };
29
30 return tokenizer {
31 in = in,
32 delim = delim,
33 p = types::I64_MAX, // I64_MAX means we haven't peeked the next token yet.
34 };
35 };
36
37 // Like [[tokenize]], but tokenizes the slice in reverse, such that the first
38 // call to [[next_token]] returns the last token and the last call returns the
39 // first token.
40 export fn rtokenize(in: []u8, delim: u8...) tokenizer = {
41 assert(len(delim) > 0, "bytes::rtokenize called with empty slice");
42 assert(len(in) < types::I64_MAX: size,
43 "bytes::rtokenize: input length exceeds I64_MAX");
44 if (len(in) == 0) {
45 delim = [];
46 };
47
48 return tokenizer {
49 in = in,
50 delim = delim,
51 // I64_MIN means we haven't peeked the next token yet. Note that
52 // p == -1 corresponds to an index of len(s), and
53 // p == -(1 - len(s)) corresponds to an index of 0.
54 p = types::I64_MIN,
55 };
56 };
57
58 // Returns the next token from a [[tokenizer]] and advances the cursor.
59 export fn next_token(s: *tokenizer) ([]u8 | done) = {
60 const b = match (peek_token(s)) {
61 case let b: []u8 =>
62 yield b;
63 case done => return done;
64 };
65
66 const slen = len(s.in): i64;
67 const reverse = s.p < 0;
68 if (reverse) {
69 if (slen + s.p + 1 == 0) {
70 s.delim = s.delim[..0];
71 s.in = s.in[..0];
72 } else {
73 const end = (slen + s.p + 1): size - 1;
74 s.in = s.in[..end];
75 };
76 s.p = types::I64_MIN;
77 } else {
78 if (s.p == slen) {
79 s.delim = s.delim[..0];
80 s.in = s.in[..0];
81 } else {
82 s.in = s.in[s.p: size + 1..];
83 };
84 s.p = types::I64_MAX;
85 };
86
87 return b;
88 };
89
90 // Returns the next token from a [[tokenizer]] without advancing the cursor.
91 export fn peek_token(s: *tokenizer) ([]u8 | done) = {
92 if (len(s.delim) == 0) {
93 return done;
94 };
95
96 const reverse = s.p < 0;
97 const ifunc = if (reverse) &rindex else &index;
98
99 const known = ((reverse && s.p != types::I64_MIN) ||
100 (!reverse && s.p != types::I64_MAX));
101 if (!known) {
102 let i = if (reverse) types::I64_MIN else types::I64_MAX;
103 let dlen = 0i64;
104 const slen = len(s.in): i64;
105
106 for (let d .. s.delim) {
107 match (ifunc(s.in, d)) {
108 case let ix: size =>
109 if (!reverse && ix: i64 < i) {
110 i = ix: i64;
111 dlen = 1;
112 } else if (reverse && ix: i64 > i) {
113 i = ix: i64;
114 dlen = 1;
115 };
116 case void =>
117 if (!reverse && slen < i: i64) {
118 i = slen;
119 } else if (reverse && 0 > i: i64) {
120 i = 0;
121 };
122 };
123 };
124
125 if (reverse) {
126 if (i == slen) {
127 s.p = -(slen + 1);
128 } else {
129 s.p = i + dlen - slen - 1;
130 };
131 } else {
132 s.p = i;
133 };
134 };
135
136 if (reverse) {
137 return s.in[len(s.in) + s.p: size + 1..];
138 } else {
139 return s.in[..s.p: size];
140 };
141 };
142
143 // Returns the remainder of the input slice from a [[tokenizer]] ahead of the
144 // token cursor.
145 export fn remaining_tokens(s: *tokenizer) []u8 = {
146 return s.in;
147 };
148
149 // Splits a byte slice into tokens delimited by 'delim', starting at the
150 // beginning of the slice, and returning a slice of up to N tokens. The caller
151 // must free the returned slice. The slices within the result are borrowed from
152 // 'in'.
153 //
154 // The caller must ensure that 'delim' is not empty. The caller must free the
155 // result after use.
156 export fn splitn(in: []u8, delim: []u8, n: size) ([][]u8 | nomem) = {
157 assert(len(delim) > 0, "bytes::splitn must not be called with an empty delimiter");
158 let toks: [][]u8 = [];
159 let ok = false;
160 defer if (!ok) free(toks);
161 let tok = tokenize(in, delim...);
162 for (let i = 0z; i < n - 1z; i += 1) {
163 match (next_token(&tok)) {
164 case let s: []u8 =>
165 append(toks, s)?;
166 case done =>
167 ok = true;
168 return toks;
169 };
170 };
171 match (peek_token(&tok)) {
172 case done => void;
173 case []u8 =>
174 append(toks, remaining_tokens(&tok))?;
175 };
176 ok = true;
177 return toks;
178 };
179
180 // Splits a byte slice into tokens delimited by 'delim', starting at the end of
181 // the slice, and returning a slice of up to N tokens. The caller must free the
182 // returned slice. The slices within the result are borrowed from 'in'.
183 //
184 // The caller must ensure that 'delim' is not empty. The caller must free the
185 // result after use.
186 export fn rsplitn(in: []u8, delim: []u8, n: size) ([][]u8 | nomem) = {
187 assert(len(delim) > 0, "bytes::rsplitn called with empty delimiter");
188 let toks: [][]u8 = [];
189 let tok = rtokenize(in, delim...);
190 let ok = false;
191 defer if (!ok) free(toks);
192 for (let i = 0z; i < n - 1z; i += 1) {
193 match (next_token(&tok)) {
194 case let s: []u8 =>
195 append(toks, s)?;
196 case done =>
197 ok = true;
198 return toks;
199 };
200 };
201 match (peek_token(&tok)) {
202 case done => void;
203 case []u8 =>
204 append(toks, remaining_tokens(&tok))?;
205 };
206
207 for (let i = 0z; i < len(toks) / 2; i += 1) {
208 const j = len(toks) - i - 1;
209 const tmp = toks[i];
210 toks[i] = toks[j];
211 toks[j] = tmp;
212 };
213
214 ok = true;
215 return toks;
216 };
217
218 // Splits a byte slice into tokens delimited by byte present in 'delim' (see
219 // [[tokenize]] for details).
220 //
221 // The caller must free the returned slice. The byte slices within the slice are
222 // borrowed from 'in'.
223 //
224 // The caller must ensure that 'delim' is not empty.
225 export fn split(in: []u8, delim: []u8) ([][]u8 | nomem) =
226 splitn(in, delim, types::SIZE_MAX);
227
228 fn tokenize_test(
229 func: *fn(_: []u8, _: u8...) tokenizer,
230 in: []u8,
231 delim: []u8,
232 tokens: [][]u8,
233 iters: size = types::SIZE_MAX,
234 ) tokenizer = {
235 const tok = func(in, delim...);
236 let n = 0z;
237 for (const want .. tokens) {
238 if (n >= iters) {
239 return tok;
240 };
241 n += 1;
242
243 const p = peek_token(&tok) as []u8;
244 const n = next_token(&tok) as []u8;
245 assert(equal(p, n));
246 assert(equal(n, want));
247 };
248
249 if (n >= iters) {
250 return tok;
251 };
252
253 assert(peek_token(&tok) is done);
254 assert(next_token(&tok) is done);
255 return tok;
256 };
257
258 @test fn tokenize() void = {
259 // simple case
260 tokenize_test(&tokenize, [1, 2, 0, 3, 4], [0], [
261 [1, 2],
262 [3, 4],
263 ]);
264
265 // multiple delimiters
266 tokenize_test(&tokenize, [1, 2, 0, 3, 4, 42, 5, 6], [0, 42], [
267 [1, 2],
268 [3, 4],
269 [5, 6],
270 ]);
271
272 // empty tokens
273 tokenize_test(&tokenize, [1, 2, 0, 0, 0, 3, 4], [0], [
274 [1, 2],
275 [],
276 [],
277 [3, 4],
278 ]);
279
280 // leading empty tokens
281 tokenize_test(&tokenize, [0, 1, 2, 3, 0], [0], [
282 [],
283 [1, 2, 3],
284 [],
285 ]);
286
287 // remaining_tokens
288 const tok = tokenize_test(&tokenize, [1, 2, 0, 3, 4], [0], [
289 [1, 2],
290 ], 1);
291 assert(equal(remaining_tokens(&tok), [3, 4]));
292 };
293
294 @test fn rtokenize() void = {
295 // simple case
296 tokenize_test(&rtokenize, [1, 2, 0, 3, 4], [0], [
297 [3, 4],
298 [1, 2],
299 ]);
300
301 // multiple delimiters
302 tokenize_test(&rtokenize, [1, 2, 0, 3, 4, 42, 5, 6], [0, 42], [
303 [5, 6],
304 [3, 4],
305 [1, 2],
306 ]);
307
308 // empty tokens
309 tokenize_test(&rtokenize, [1, 2, 0, 0, 0, 3, 4], [0], [
310 [3, 4],
311 [],
312 [],
313 [1, 2],
314 ]);
315
316 // leading empty tokens
317 tokenize_test(&rtokenize, [0, 1, 2, 3, 0], [0], [
318 [],
319 [1, 2, 3],
320 [],
321 ]);
322
323 // remaining_tokens
324 const tok = tokenize_test(&rtokenize, [1, 2, 0, 3, 4], [0], [
325 [3, 4],
326 ], 1);
327 assert(equal(remaining_tokens(&tok), [1, 2]));
328 };
329
330 @test fn split() void = {
331 const input = *(&"Hello, my name is Drew": *[]u8);
332 const space: [1]u8 = [' '];
333
334 const expected = [
335 *(&"Hello,": *[]u8),
336 *(&"my": *[]u8),
337 *(&"name": *[]u8),
338 *(&"is Drew": *[]u8),
339 ];
340 const actual = splitn(input, space[..], 4z)!;
341 assert(len(expected) == len(actual));
342 for (let i = 0z; i < len(expected); i += 1) {
343 assert(equal(expected[i], actual[i]));
344 };
345 free(actual);
346
347 const expected2 = [
348 *(&"Hello,": *[]u8),
349 *(&"my": *[]u8),
350 *(&"name": *[]u8),
351 *(&"is": *[]u8),
352 *(&"Drew": *[]u8),
353 ];
354 const actual2 = split(input, space[..])!;
355 assert(len(expected2) == len(actual2));
356 for (let i = 0z; i < len(expected2); i += 1) {
357 assert(equal(expected2[i], actual2[i]));
358 };
359 free(actual2);
360
361 const eq: [1]u8 = ['='];
362 const single = *(&"one": *[]u8);
363 const actual3 = splitn(single, eq[..], 2z)!;
364 const expected3 = [
365 *(&"one": *[]u8),
366 ];
367 assert(len(expected3) == len(actual3));
368 for (let i = 0z; i < len(expected3); i += 1) {
369 assert(equal(expected3[i], actual3[i]));
370 };
371 free(actual3);
372
373 const expected4 = [
374 *(&"Hello, my": *[]u8),
375 *(&"name": *[]u8),
376 *(&"is": *[]u8),
377 *(&"Drew": *[]u8),
378 ];
379 const actual4 = rsplitn(input, space[..], 4z)!;
380 assert(len(expected4) == len(actual4));
381 for (let i = 0z; i < len(expected4); i += 1) {
382 assert(equal(expected4[i], actual4[i]));
383 };
384 free(actual4);
385 };
386
387 // Returns the input slice "cut" along the first instance of a delimiter,
388 // returning everything up to the delimiter, and everything after the delimiter,
389 // in a tuple. The contents are borrowed from the input slice.
390 //
391 // The caller must ensure that 'delimiter' is not an empty slice.
392 export fn cut(in: []u8, delim: ([]u8 | u8)) ([]u8, []u8) = {
393 let ln = if (delim is u8) {
394 yield 1z;
395 } else {
396 let ln = len(delim: []u8);
397 assert(ln > 0, "bytes::cut called with empty delimiter");
398 yield ln;
399 };
400 match (index(in, delim)) {
401 case let i: size =>
402 return (in[..i], in[i + ln..]);
403 case void =>
404 return (in, []);
405 };
406 };
407
408 // Returns the input slice "cut" along the last instance of a delimiter,
409 // returning everything up to the delimiter, and everything after the delimiter,
410 // in a tuple. The contents are borrowed from the input slice.
411 //
412 // The caller must ensure that 'delimiter' is not an empty slice.
413 export fn rcut(in: []u8, delim: ([]u8 | u8)) ([]u8, []u8) = {
414 let ln = if (delim is u8) {
415 yield 1z;
416 } else {
417 let ln = len(delim: []u8);
418 assert(ln > 0, "bytes::rcut called with empty delimiter");
419 yield ln;
420 };
421 match (rindex(in, delim)) {
422 case let i: size =>
423 return (in[..i], in[i + ln..]);
424 case void =>
425 return (in, []);
426 };
427 };
428
429 @test fn cut() void = {
430 const c = cut(['a', 'b', 'c'], ['b']);
431 assert(equal(c.0, ['a']) && equal(c.1, ['c']));
432 const c = cut(['a', 'b', 'c'], 'b');
433 assert(equal(c.0, ['a']) && equal(c.1, ['c']));
434 const c = cut(['a', 'b', 'c', 'b', 'a'], 'b');
435 assert(equal(c.0, ['a']) && equal(c.1, ['c', 'b', 'a']));
436 const c = cut(['a', 'b', 'c'], 'x');
437 assert(equal(c.0, ['a', 'b', 'c']) && equal(c.1, []));
438 const c = cut([], 'x');
439 assert(equal(c.0, []) && equal(c.1, []));
440
441 const c = rcut(['a', 'b', 'c'], ['b']);
442 assert(equal(c.0, ['a']) && equal(c.1, ['c']));
443 const c = rcut(['a', 'b', 'c', 'b', 'a'], 'b');
444 assert(equal(c.0, ['a', 'b', 'c']) && equal(c.1, ['a']));
445 };