1-- The parser-support text layer is deliberately byte-oriented. D181--D184
2-- add the hosted text identities, literals, indexing, direct ranges and
3-- scalar traversal without changing this module's opaque positions or
4-- bounded byte views.
5-- D182 also accepts this exact public position identity for O(1) utf8
6-- indexing; a position used that way must begin a codepoint.
7
8import core/map
9import core/sort
10
11position_value: type = struct
12 offset: usize
13end position_value
14
15--- Opaque byte offset for scanning. It does not retain or validate a source;
16--- when used to index UTF-8 it must identify a codepoint boundary.
17public position: type = position_value
18--- A byte read was requested at or beyond the end of its source.
19public past_end: atom
20--- The supplied bytes are not well-formed UTF-8.
21public invalid_text: atom
22--- The text is empty or contains a non-decimal digit where an unsigned
23--- integer is required.
24public invalid_number: atom
25--- The parsed unsigned decimal value exceeds `u32`.
26public number_overflow: atom
27--- The destination does not have room for the complete requested output.
28public no_space: atom
29
30byte_view: type = []u8
31
32--- The zero-offset position sentinel. It has the same offset as `first`; it
33--- is not a separate invalid-position tag.
34public nowhere: position = (offset: 0)
35
36--- Return a cursor at byte offset zero, including for an empty source.
37public first: (source: []u8) -> (result: position) =
38 _ = source
39 result = (offset: 0)
40end first
41
42--- Return whether the byte offset is at or beyond the source length.
43public at_end: (source: []u8, cursor: position) -> (yes: bool) =
44 yes = cursor.offset >= lenof source
45end at_end
46
47--- Return the byte offset stored in a position.
48public ordinal: (cursor: position) -> (offset: usize) =
49 offset = cursor.offset
50end ordinal
51
52--- Copy a cursor value without retaining the aggregate from which it was
53--- read.
54---
55--- Copy a position out of aggregate storage without borrowing that storage.
56--- This matters to scanners that retain the token start while advancing the
57--- cursor field from which it was read.
58public copied: (cursor: position) -> (result: position) =
59 result = (offset: cursor.offset)
60end copied
61
62--- Construct a cursor with the given byte offset. Does not check bounds or
63--- UTF-8 boundaries; later operations enforce their own requirements.
64---
65--- Reify an ordinal as an opaque position for byte-oriented scanners. The
66--- source argument makes the intended coordinate space explicit even though
67--- The compact representation stores only the offset.
68public at: (source: []u8, offset: usize) -> (result: position) =
69 _ = source
70 result = (offset: offset)
71end at
72
73--- Return a cursor one byte later. This is byte traversal, not Unicode-scalar
74--- traversal; offset overflow follows ordinary checked arithmetic.
75public next: (cursor: position) -> (result: position) =
76 result = (offset: cursor.offset + 1)
77end next
78
79--- Advance the cursor by one byte in place. Does not validate the source or
80--- skip a whole UTF-8 scalar.
81public advance: (inout cursor: position) -> none =
82 inc cursor.offset
83end advance
84
85--- Read one source byte at the cursor. Reports `past_end` before reading
86--- outside the source.
87public byte: (source: []u8, cursor: position)
88 -> (value: u8) ! past_end =
89 fail past_end when at_end(source, cursor)
90 value = source[cursor.offset]
91end byte
92
93--- Lend bytes between two cursor offsets, with an exclusive end. Requires an
94--- ordered interval within the source; invalid ranges follow the language's
95--- checked range behavior.
96public slice: (source: []u8, begins: position, ends: position)
97 -> (result: []u8 from source) =
98 result = source[begins.offset..<ends.offset]
99end slice
100
101valid_utf8: (source: []u8) -> (yes: bool) =
102 mut cursor: usize = 0
103 while cursor < lenof source do
104 lead: u8 = source[cursor]
105 if lead < 128 then
106 cursor += 1
107 elsif lead < 194 then
108 yes = false
109 return
110 elsif lead < 224 then
111 if lenof source - cursor < 2 then
112 yes = false
113 return
114 end if
115 second: u8 = source[cursor + 1]
116 if second < 128 or second > 191 then
117 yes = false
118 return
119 end if
120 cursor += 2
121 elsif lead < 240 then
122 if lenof source - cursor < 3 then
123 yes = false
124 return
125 end if
126 second: u8 = source[cursor + 1]
127 third: u8 = source[cursor + 2]
128 if second < 128 or second > 191
129 or third < 128 or third > 191
130 then
131 yes = false
132 return
133 end if
134 if lead == 224 and second < 160 then
135 yes = false
136 return
137 end if
138 if lead == 237 and second > 159 then
139 yes = false
140 return
141 end if
142 cursor += 3
143 elsif lead <= 244 then
144 if lenof source - cursor < 4 then
145 yes = false
146 return
147 end if
148 second: u8 = source[cursor + 1]
149 third: u8 = source[cursor + 2]
150 fourth: u8 = source[cursor + 3]
151 if second < 128 or second > 191
152 or third < 128 or third > 191
153 or fourth < 128 or fourth > 191
154 then
155 yes = false
156 return
157 end if
158 if lead == 240 and second < 144 then
159 yes = false
160 return
161 end if
162 if lead == 244 and second > 143 then
163 yes = false
164 return
165 end if
166 cursor += 4
167 else
168 yes = false
169 return
170 end if
171 end while
172 yes = true
173end valid_utf8
174
175--- Validate a byte slice and lend it as UTF-8 without allocation. Reports
176--- `invalid_text`; the caller keeps the bytes alive and valid while the view
177--- is used.
178---
179--- The checked adapters report foreign or file-data defects before the
180--- ordinary conversion establishes utf8's invariant. Their result is a
181--- source-derived view; no allocation, copy or canonical empty carrier is
182--- introduced.
183public from_bytes: (source: []u8)
184 -> (result: utf8 from source) ! invalid_text =
185 fail invalid_text when not valid_utf8(source)
186 result = utf8(source)
187end from_bytes
188
189--- Validate a terminated C string and lend it as UTF-8. The pointer must
190--- remain readable through its terminator; invalid UTF-8 reports
191--- `invalid_text`.
192public from_c: (source: cstring)
193 -> (result: utf8 from source) ! invalid_text =
194 raw: []u8 = byte_view(source)
195 result = try from_bytes(raw)
196end from_c
197
198--- Lend the encoded bytes of a UTF-8 view without copying or allocating.
199public bytes: (source: utf8) -> (result: []u8 from source) =
200 result = byte_view(source)
201end bytes
202
203--- Compare UTF-8 values by their encoded bytes. Does not normalize Unicode
204--- spelling.
205---
206--- Equality and containment are exact encoded-byte operations. Valid UTF-8
207--- has one shortest-form encoding per scalar sequence, so neither operation
208--- needs normalization or locale authority.
209public eq: (left: utf8, right: utf8) -> (same: bool) =
210 left_bytes: []u8 = bytes(left)
211 right_bytes: []u8 = bytes(right)
212 if lenof left_bytes <> lenof right_bytes then
213 same = false
214 return
215 end if
216 mut index: usize = 0
217 while index < lenof left_bytes do
218 if left_bytes[index] <> right_bytes[index] then
219 same = false
220 return
221 end if
222 inc index
223 end while
224 same = true
225end eq
226
227--- Test whether the sought UTF-8 byte sequence occurs in the source. Empty
228--- text matches; no normalization or allocation is performed.
229---
230--- Two-Way search uses a critical split of the sought bytes. Its two
231--- lexicographic passes and the search each take linear time; only scalar
232--- counters are kept, so neither a table nor a caller allocator is needed.
233public contains: (source: utf8, sought: utf8) -> (yes: bool) =
234 source_bytes: []u8 = bytes(source)
235 sought_bytes: []u8 = bytes(sought)
236 if lenof sought_bytes == 0 then
237 yes = true
238 return
239 end if
240 if lenof sought_bytes > lenof source_bytes then
241 yes = false
242 return
243 end if
244
245 sought_length: usize = lenof sought_bytes
246 mut cut: usize = 0
247 mut period: usize = 1
248 mut pass: usize = 0
249 while pass < 2 do
250 mut maximum: usize = 0
251 mut candidate: usize = 1
252 mut matched: usize = 0
253 mut local_period: usize = 1
254 while candidate < sought_length
255 and matched < sought_length - candidate
256 do
257 current: u8 = sought_bytes[candidate + matched]
258 best: u8 = sought_bytes[maximum + matched]
259 if (pass == 0 and current < best)
260 or (pass == 1 and best < current)
261 then
262 candidate += matched + 1
263 matched = 0
264 local_period = candidate - maximum
265 elsif current == best then
266 if matched + 1 == local_period then
267 candidate += local_period
268 matched = 0
269 else
270 inc matched
271 end if
272 else
273 maximum = candidate
274 inc candidate
275 matched = 0
276 local_period = 1
277 end if
278 end while
279 if pass == 0 or maximum >= cut then
280 cut = maximum
281 period = local_period
282 end if
283 inc pass
284 end while
285
286 -- A period of the right half is a period of the whole sought value
287 -- precisely when the left half agrees with its shifted copy.
288 mut periodic: bool = cut <= sought_length - period
289 mut offset: usize = 0
290 while periodic and offset < cut do
291 if sought_bytes[offset] <> sought_bytes[offset + period] then
292 periodic = false
293 end if
294 inc offset
295 end while
296 if not periodic then
297 if cut > sought_length - cut then
298 period = cut + 1
299 else
300 period = sought_length - cut + 1
301 end if
302 end if
303
304 mut start: usize = 0
305 mut memory: usize = 0
306 last: usize = lenof source_bytes - sought_length
307 while start <= last do
308 mut index: usize = cut
309 if periodic and memory > index then
310 index = memory
311 end if
312 while index < sought_length
313 and sought_bytes[index] == source_bytes[start + index]
314 do
315 inc index
316 end while
317 if index < sought_length then
318 start += index - cut + 1
319 memory = 0
320 else
321 index = memory
322 while index < cut
323 and sought_bytes[index] == source_bytes[start + index]
324 do
325 inc index
326 end while
327 if index >= cut then
328 yes = true
329 return
330 end if
331 start += period
332 if periodic then
333 memory = sought_length - period
334 end if
335 end if
336 end while
337 yes = false
338end contains
339
340--- Parse nonempty ASCII decimal digits into `u32`. Rejects signs, whitespace
341--- and non-digits with `invalid_number`, and excessive values with
342--- `number_overflow`.
343public to_u32: (source: utf8)
344 -> (result: u32) ! invalid_number | number_overflow =
345 digits: []u8 = bytes(source)
346 fail invalid_number when lenof digits == 0
347 mut value: u32 = 0
348 mut index: usize = 0
349 while index < lenof digits do
350 byte: u8 = digits[index]
351 fail invalid_number when byte < 48 or byte > 57
352 digit: u32 = u32(byte - 48)
353 fail number_overflow when value > 429496729
354 fail number_overflow when value == 429496729 and digit > 5
355 value = value * 10 + digit
356 inc index
357 end while
358 result = value
359end to_u32
360
361--- Append one byte at `used` and return the new used count. Checks capacity
362--- before writing and reports `no_space` without partial output.
363---
364--- Both writers preflight capacity before their first mutation. A no_space
365--- refusal therefore preserves every caller-owned byte and the written
366--- count, including the multi-byte decimal operation.
367public write_byte: (inout into: []mut u8, used: usize, value: u8)
368 -> (next: usize) ! no_space =
369 fail no_space when used >= lenof into
370 into[used] = value
371 next = used + 1
372end write_byte
373
374--- Append an unsigned decimal representation and return the new used count.
375--- Checks space for the whole number before writing; `no_space` leaves the
376--- buffer unchanged.
377public write_u32: (inout into: []mut u8, used: usize, value: u32)
378 -> (next: usize) ! no_space =
379 fail no_space when used > lenof into
380 mut digits: usize = 1
381 mut threshold: u32 = 10
382 while value >= threshold do
383 inc digits
384 break when threshold == 1000000000
385 threshold *= 10
386 end while
387 fail no_space when digits > lenof into - used
388
389 mut remaining: u32 = value
390 mut offset: usize = digits
391 while remaining >= 10 do
392 quotient: u32 = remaining / 10
393 digit: u8 = u8(remaining - quotient * 10)
394 dec offset
395 into[used + offset] = digit + 48
396 remaining = quotient
397 end while
398 into[used] = u8(remaining) + 48
399 next = used + digits
400end write_u32
401
402--- Lend the byte prefix of length `used`. Requires `used` within the source
403--- length; it does not validate UTF-8.
404public written: (source: []u8, used: usize)
405 -> (result: []u8 from source) ! no_space =
406 fail no_space when used > lenof source
407 result = source[0..<used]
408end written
409
410--- Hash UTF-8 encoded bytes consistently with `eq` and the byte-slice hash.
411--- No Unicode normalization or cryptographic guarantee is provided.
412---
413--- utf8 is a map key and sortable as it stands: equality, hash and order
414--- are over the encoded bytes, which valid UTF-8 makes unique per scalar
415--- sequence. The hash is 64-bit FNV-1a, the same as core/map's for []u8.
416public hash: (value: utf8) -> (result: u64) =
417 raw: []u8 = bytes(value)
418 mut folded: u64 = 14695981039346656037
419 mut index: usize = 0
420 while index < lenof raw do
421 folded = (folded ^ u64(raw[index])) *% 1099511628211
422 inc index
423 end while
424 result = folded
425end hash
426
427--- Compare encoded bytes lexicographically, with a shorter equal prefix
428--- sorting first. This is not locale-aware collation.
429---
430--- Byte-wise lexicographic order, which for valid UTF-8 is scalar order.
431public less: (left: utf8, right: utf8) -> (yes: bool) =
432 left_bytes: []u8 = bytes(left)
433 right_bytes: []u8 = bytes(right)
434 mut index: usize = 0
435 while index < lenof left_bytes and index < lenof right_bytes do
436 if left_bytes[index] <> right_bytes[index] then
437 yes = left_bytes[index] < right_bytes[index]
438 return
439 end if
440 inc index
441 end while
442 yes = lenof left_bytes < lenof right_bytes
443end less
444
445utf8 is map.equatable (eq: eq)
446utf8 is map.hashable (hash: hash)
447utf8 is sort.ordered (less: less)