tobogganSe connecter

packages

The Louise packages, each released on its own

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

Fmt: reformat the repository (ADR 0059 rev. 9)69f7c16 · il y a 3 sem.
698 lignes · 16169 octetsBrut · Historique
1/// UUIDs (RFC 9562): version 7, and short text forms that sort like the
2/// IDs themselves.
3///
4/// import uuid
5///
6/// let id = uuid.v7() // reads `clock` and `random`
7/// uuid.to_rfc(id) // "0190f5a2-7c1e-7d3a-9b2c-4e5f60718293"
8/// show(id) // Crockford base 32, 26 characters
9/// uuid.encode(id, uuid.base62()) // 22 characters
10/// uuid.decode("01J3TT8Z0Y7MX6PB5S0SJ8S4WK", uuid.crockford()) // Ok(...) or an error
11///
12/// A version 7 UUID starts with its creation time in milliseconds, so IDs
13/// sort by creation time (`<`, and the text of every alphabet here). Within
14/// one millisecond, the order is random. The time is readable by anyone who
15/// sees the ID: don't use v7 IDs where the creation time is a secret. They
16/// are not secrets either: session tokens should stay `random.token`.
17///
18/// Text forms: `to_rfc`/`from_rfc` (the 36-character hex form), and
19/// `encode`/`decode` with an alphabet: `crockford()` (the default, used by
20/// `show`), `hex()`, `base58()`, `base62()`, or your own (`alphabet`).
21/// Every encoding has a fixed width, padded with the alphabet's first
22/// character, and alphabets must be in ascending ASCII order: so comparing
23/// two encoded IDs as text gives the same order as comparing the IDs.
24
25import std/bytes as raw
26import std/int as bits
27import std/list
28import std/random.{type random}
29import std/time.{type clock}
30
31/// A UUID: 16 bytes. Compared byte by byte, so version 7 IDs compare by
32/// creation time.
33@derive Eq Ord Hash
34pub opaque type Uuid { Uuid(Bytes) }
35
36/// The UUID whose bytes are `b`; `None` unless there are 16.
37pub fn from_bytes :: b: Bytes -> Option<Uuid>
38{
39 if raw.length b == 16
40 {
41 Some(Uuid(b))
42 }
43 else
44 {
45 None
46 }
47}
48
49/// The 16 bytes of `id`.
50pub fn to_bytes :: id: Uuid -> Bytes
51{
52 match id { Uuid(b) -> b }
53}
54
55/// The nil UUID: every bit 0.
56pub fn nil :: -> Uuid
57{
58 Uuid(raw.from_list (list.map (list.range 1 16) fn _ { 0 }))
59}
60
61/// The max UUID: every bit 1.
62pub fn max :: -> Uuid
63{
64 Uuid(raw.from_list (list.map (list.range 1 16) fn _ { 255 }))
65}
66
67// ---- version 7 ---------------------------------------------------------------------
68
69/// A new version 7 UUID: the current Unix time in milliseconds, then 74
70/// random bits. Panics if the clock is before 1970.
71pub fn v7 :: -> Uuid / <clock, random>
72{
73 v7_from (time.unix_ms (time.now ())) (random.bytes 10)
74}
75
76/// The version 7 UUID of `unix_ms` and 10 bytes of `randomness` (RFC 9562,
77/// section 5.7): the time as 48 bits, big-endian; the version (7); 12 bits
78/// from the first two bytes; the variant (`10`); 62 bits from the rest.
79/// Panics unless `unix_ms` is in `[0, 2^48)` and there are 10 bytes.
80pub fn v7_from :: unix_ms: Int randomness: Bytes -> Uuid
81{
82 if unix_ms < 0 || unix_ms >= 281474976710656
83 {
84 panic "uuid.v7_from: the time {unix_ms} is not in [0, 2^48) milliseconds"
85 }
86 if raw.length randomness != 10
87 {
88 panic "uuid.v7_from: expected 10 random bytes, got {raw.length randomness}"
89 }
90 let r = raw.to_list randomness
91 match r
92 { [r0, r1, r2, ..rest] ->
93 {
94 let time_bytes =
95 list.map
96 (list.range 0 5)
97 fn i { bits.low_bits (bits.shift_right unix_ms (8 * (5 - i))) 8 }
98 Uuid( raw.from_list
99 (list.append time_bytes [112 + r0 % 16, r1, 128 + r2 % 64, ..rest])
100 )
101 }
102 , _ -> panic "uuid.v7_from: expected 10 random bytes"
103 }
104}
105
106/// The version: 4 for random UUIDs, 7 for time-ordered ones (the high
107/// nibble of byte 6).
108pub fn version :: id: Uuid -> Int
109{
110 byte id 6 / 16
111}
112
113/// When a version 7 UUID was made, in Unix milliseconds; `None` for any
114/// other UUID (another version, or not RFC 9562's variant).
115pub fn timestamp :: id: Uuid -> Option<Int>
116{
117 if version id == 7 && byte id 8 / 64 == 2
118 {
119 Some(list.fold (list.range 0 5) 0 fn acc i { acc * 256 + byte id i })
120 }
121 else
122 {
123 None
124 }
125}
126
127fn byte :: id: Uuid i: Int -> Int
128{
129 match raw.get (to_bytes id) i { Some(b) -> b, None -> 0 }
130}
131
132/// 2^128: one more than the largest UUID.
133fn limit :: -> Int
134{
135 bits.shift_left 1 128
136}
137
138// ---- the RFC 9562 text form ----------------------------------------------------------
139
140/// `id` as 32 lowercase hex digits in groups of 8-4-4-4-12:
141/// `017f22e2-79b0-7cc3-98c4-dc0c0c07398f`.
142pub fn to_rfc :: id: Uuid -> String
143{
144 let digits = raw.from_string (encode id (hex ()))
145 let part = fn start: Int end: Int
146 {
147 raw.to_string_lossy (raw.slice digits start end)
148 }
149 "{part 0 8}-{part 8 12}-{part 12 16}-{part 16 20}-{part 20 32}"
150}
151
152/// The UUID of an RFC 9562 text form: exactly 36 characters, hex digits in
153/// either case, dashes after the 8th, 12th, 16th and 20th digit.
154pub fn from_rfc :: text: String -> Option<Uuid>
155{
156 let b = raw.from_string text
157 let dashes = [8, 13, 18, 23]
158 let dashed = list.all dashes fn i { raw.get b i == Some(45) }
159 if raw.length b != 36 || !dashed
160 {
161 None
162 }
163 else
164 {
165 let digits = list.filter (raw.to_list b) fn c { c != 45 }
166 match raw.to_string (raw.from_list digits)
167 { Ok(hex_digits) -> decode hex_digits (hex ()) |> ok_or_none
168 , Error(_) -> None
169 }
170 }
171}
172
173fn ok_or_none :: r: Result<a, e> -> Option<a>
174{
175 match r { Ok(x) -> Some(x), Error(_) -> None }
176}
177
178// ---- alphabets -----------------------------------------------------------------------
179
180/// The characters of a text form, from digit 0 up. Built by `alphabet`,
181/// or one of the presets.
182pub opaque type Alphabet
183{ /// `chars` (in ascending ASCII order), the number of them, the digits of
184 /// an encoding, the bits per digit when the base is a power of 2 (0
185 /// otherwise), whether `decode` also reads a letter in the other case,
186 /// and other characters `decode` reads, with their digit.
187 Alphabet(
188 chars: Bytes
189 , base: Int
190 , width: Int
191 , bits: Int
192 , fold_case: Bool
193 , aliases: List<(Int, Int)>
194 )
195}
196
197/// Why `alphabet` refused some characters.
198@derive Eq Show Debug
199pub type AlphabetError
200{ /// Fewer than 2 characters.
201 TooShort
202 /// A character that appears twice.
203, Repeated(String)
204 /// A character outside RFC 3986's unreserved set (`A-Z a-z 0-9 - . _ ~`),
205 /// which would need escaping in a URL.
206, NotUrlSafe(String)
207 /// A character that is not after the one before it in ASCII, so text
208 /// would not sort like the IDs. The character is named.
209, NotAscending(String)
210}
211
212/// An alphabet of the characters of `chars`, digit 0 first: at least 2,
213/// each once, URL-safe, in ascending ASCII order. Checking them takes a
214/// few microseconds: build an alphabet once and keep it.
215pub fn alphabet :: chars: String -> Result<Alphabet, AlphabetError>
216{
217 let codes = raw.to_list (raw.from_string chars)
218 match ( list.filter codes fn c { !url_safe c }
219 , first_repeated codes []
220 , first_descent codes
221 )
222 { _ if list.length codes < 2 -> Error(TooShort)
223 , ([c, ..], _, _) -> Error(NotUrlSafe(char c))
224 , (_, Some(c), _) -> Error(Repeated(char c))
225 , (_, _, Some(c)) -> Error(NotAscending(char c))
226 , _ ->
227 {
228 let base = list.length codes
229 Ok( Alphabet( raw.from_list codes
230 , base
231 , width_for base 0 1
232 , bits_for base
233 , False
234 , []
235 )
236 )
237 }
238 }
239}
240
241/// A preset: `chars` are known to be valid, and `width` and `k` right
242/// (the tests check them against `alphabet`), so nothing is computed per
243/// call.
244fn preset ::
245 chars: String
246 width: Int
247 k: Int
248 fold_case: Bool
249 aliases: List<(Int, Int)>
250 -> Alphabet
251{
252 let b = raw.from_string chars
253 Alphabet(b, raw.length b, width, k, fold_case, aliases)
254}
255
256/// The smallest `n` with `base^n >= 2^128`.
257fn width_for :: base: Int n: Int reach: Int -> Int
258{
259 if reach >= limit ()
260 {
261 n
262 }
263 else
264 {
265 width_for base (n + 1) (reach * base)
266 }
267}
268
269/// `k` when `base` is `2^k`, else 0.
270fn bits_for :: base: Int -> Int
271{
272 if bits.and base (base - 1) == 0
273 {
274 bits.bit_length base - 1
275 }
276 else
277 {
278 0
279 }
280}
281
282/// RFC 3986's unreserved characters.
283fn url_safe :: c: Int -> Bool
284{
285 c >= 48 && c <= 57 || c >= 65 && c <= 90 || c >= 97 && c <= 122 || c == 45
286 || c == 46
287 || c == 95
288 || c == 126
289}
290
291fn first_repeated :: codes: List<Int> seen: List<Int> -> Option<Int>
292{
293 match codes
294 { [] -> None
295 , [c, ..rest] -> if list.any seen fn s { s == c }
296 {
297 Some(c)
298 }
299 else
300 {
301 first_repeated rest [c, ..seen]
302 }
303 }
304}
305
306fn first_descent :: codes: List<Int> -> Option<Int>
307{
308 match codes
309 { [a, b, ..rest] -> if b <= a { Some(b) } else { first_descent [b, ..rest] }
310 , _ -> None
311 }
312}
313
314/// The one-character string of an ASCII code.
315fn char :: c: Int -> String
316{
317 raw.to_string_lossy (raw.from_list [c])
318}
319
320/// The number of characters of every encoding with `a`.
321pub fn width :: a: Alphabet -> Int
322{
323 match a { Alphabet(_, _, w, _, _, _) -> w }
324}
325
326/// Lowercase hex, 32 characters (`decode` also reads uppercase).
327pub fn hex :: -> Alphabet
328{
329 preset "0123456789abcdef" 32 4 True []
330}
331
332/// Crockford's base 32, 26 characters: digits and uppercase letters
333/// without I, L, O and U. `decode` also reads lowercase, and I and L as 1,
334/// O as 0 (in either case), as Crockford specifies. The default: `show`
335/// uses it.
336pub fn crockford :: -> Alphabet
337{
338 preset
339 "0123456789ABCDEFGHJKMNPQRSTVWXYZ"
340 26
341 5
342 True
343 [(73, 1), (76, 1), (79, 0)]
344}
345
346/// Bitcoin's base 58, 22 characters: no 0, O, I or l, which look alike.
347pub fn base58 :: -> Alphabet
348{
349 preset
350 "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
351 22
352 0
353 False
354 []
355}
356
357/// Digits, uppercase, then lowercase letters: 22 characters.
358pub fn base62 :: -> Alphabet
359{
360 preset
361 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
362 22
363 0
364 False
365 []
366}
367
368/// The digit of the character `c`, or -1. `chars` is in ascending order,
369/// so it is searched by halves.
370fn digit_of ::
371 c: Int
372 chars: Bytes
373 fold_case: Bool
374 aliases: List<(Int, Int)>
375 -> Int
376{
377 let d = search chars c 0 (raw.length chars)
378 if d >= 0
379 {
380 d
381 }
382 else
383 {
384 match list.find aliases fn alias { alias.0 == c }
385 { Some((_, alias)) -> alias
386 , None if fold_case && is_letter c ->
387 digit_of (other_case c) chars False aliases
388 , None -> -1
389 }
390 }
391}
392
393/// The index of `c` in `chars[lo..hi)`, or -1.
394fn search :: chars: Bytes c: Int lo: Int hi: Int -> Int
395{
396 if lo >= hi
397 {
398 -1
399 }
400 else
401 {
402 let mid = (lo + hi) / 2
403 let x = raw.read_u8 chars mid
404 if x == c
405 {
406 mid
407 }
408 else if x < c
409 {
410 search chars c (mid + 1) hi
411 }
412 else
413 {
414 search chars c lo mid
415 }
416 }
417}
418
419/// A letter in the other case (ASCII).
420fn other_case :: c: Int -> Int
421{
422 if c >= 97
423 {
424 c - 32
425 }
426 else
427 {
428 c + 32
429 }
430}
431
432fn is_letter :: c: Int -> Bool
433{
434 c >= 65 && c <= 90 || c >= 97 && c <= 122
435}
436
437// ---- encoding ------------------------------------------------------------------------
438
439// An alphabet of 2^k characters is read and written k bits at a time, in
440// small `Int`s: the bits not yet consumed are `acc`, with `p` = 2^(their
441// number), so plain arithmetic (inlined) does what shifts and masks
442// would (calls into the runtime). Other bases go through the id's value,
443// a 128-bit `Int`.
444
445/// `id` with `a`'s characters: its 128 bits as a number in base
446/// `a`'s size, padded to `width(a)` with the first character.
447pub fn encode :: id: Uuid a: Alphabet -> String
448{
449 match a
450 { Alphabet(chars, base, w, k, _, _) if k > 0 ->
451 {
452 // `w * k` bits: the id's 128 after `w * k - 128` zero bits, which
453 // count as already read.
454 let out = raw.builder_with_capacity w
455 raw.build_string
456 (encode_bits (to_bytes id) 0 chars base 0 (pow2 (w * k - 128)) out)
457 }
458 , Alphabet(chars, base, w, _, _, _) ->
459 {
460 let value =
461 list.fold (raw.to_list (to_bytes id)) 0 fn acc b { acc * 256 + b }
462 raw.to_string_lossy (raw.from_list (digits value base w chars []))
463 }
464 }
465}
466
467/// The digits of bytes `i..16` of `b`, after the bits `acc` (`p` = 2^n).
468fn encode_bits ::
469 b: Bytes
470 i: Int
471 chars: Bytes
472 base: Int
473 acc: Int
474 p: Int
475 out: raw.Builder
476 -> raw.Builder
477{
478 if p >= base
479 {
480 let p = p / base
481 let out = raw.append_byte out (raw.read_u8 chars (acc / p))
482 encode_bits b i chars base (acc % p) p out
483 }
484 else if i == 16
485 {
486 out
487 }
488 else
489 {
490 encode_bits b (i + 1) chars base (acc * 256 + raw.read_u8 b i) (p * 256) out
491 }
492}
493
494fn pow2 :: n: Int -> Int
495{
496 if n == 0
497 {
498 1
499 }
500 else
501 {
502 2 * pow2 (n - 1)
503 }
504}
505
506/// The last `n` digits of `value` in base `base`, as `chars`' codes,
507/// before `acc`.
508fn digits ::
509 value: Int
510 base: Int
511 n: Int
512 chars: Bytes
513 acc: List<Int>
514 -> List<Int>
515{
516 if n == 0
517 {
518 acc
519 }
520 else
521 {
522 let code = raw.read_u8 chars (value % base)
523 digits (value / base) base (n - 1) chars [code, ..acc]
524 }
525}
526
527/// Why `decode` refused a text.
528@derive Eq Show Debug
529pub type DecodeError
530{ /// Not the alphabet's width: the length found.
531 WrongLength(Int)
532 /// A character that is not one of the alphabet's: its position.
533, InvalidChar(Int)
534 /// The value is 2^128 or more: it is no UUID's.
535, TooLarge
536}
537
538/// The UUID `text` encodes with `a`.
539pub fn decode :: text: String a: Alphabet -> Result<Uuid, DecodeError>
540{
541 let text = raw.from_string text
542 match a
543 { Alphabet(_, _, w, _, _, _) if raw.length text != w ->
544 Error(WrongLength(raw.length text))
545 , Alphabet(chars, base, w, k, fold, aliases) if k > 0 ->
546 {
547 // The first digit only holds the id's top bits: the rest of its
548 // bits are the padding, and must be 0.
549 let top = base / pow2 (w * k - 128)
550 let out = raw.builder_with_capacity 16
551 decode_bits text 0 chars fold aliases base top False 0 1 out
552 }
553 , Alphabet
554 ( chars
555 , base
556 , _
557 , _
558 , fold
559 , aliases
560 ) -> match value_of text 0 0 chars base fold aliases
561 { Error(e) -> Error(e)
562 , Ok(v) if v >= limit () -> Error(TooLarge)
563 , Ok(v) -> Ok(Uuid(raw.from_list (bytes_of v 16 [])))
564 }
565 }
566}
567
568/// The bytes of characters `i..` of `text`, after the bits `acc` (`p` =
569/// 2^n). A first digit of `top` or more makes the id too large, which is
570/// only reported when no character is invalid.
571fn decode_bits ::
572 text: Bytes
573 i: Int
574 chars: Bytes
575 fold: Bool
576 aliases: List<(Int, Int)>
577 base: Int
578 top: Int
579 too_large: Bool
580 acc: Int
581 p: Int
582 out: raw.Builder
583 -> Result<Uuid, DecodeError>
584{
585 if p >= 256
586 {
587 let p = p / 256
588 let out = raw.append_byte out (acc / p)
589 decode_bits text i chars fold aliases base top too_large (acc % p) p out
590 }
591 else if i == raw.length text
592 {
593 if too_large
594 {
595 Error(TooLarge)
596 }
597 else
598 {
599 Ok(Uuid(raw.build out))
600 }
601 }
602 else
603 {
604 let d = digit_of (raw.read_u8 text i) chars fold aliases
605 if d < 0
606 {
607 Error(InvalidChar(i))
608 }
609 else if i == 0
610 {
611 decode_bits
612 text
613 1
614 chars
615 fold
616 aliases
617 base
618 top
619 (d >= top)
620 (d % top)
621 top
622 out
623 }
624 else
625 {
626 decode_bits
627 text
628 (i + 1)
629 chars
630 fold
631 aliases
632 base
633 top
634 too_large
635 (acc * base + d)
636 (p * base)
637 out
638 }
639 }
640}
641
642/// The value of `text` from character `at`, after `acc`.
643fn value_of ::
644 text: Bytes
645 at: Int
646 acc: Int
647 chars: Bytes
648 base: Int
649 fold: Bool
650 aliases: List<(Int, Int)>
651 -> Result<Int, DecodeError>
652{
653 if at == raw.length text
654 {
655 Ok(acc)
656 }
657 else
658 {
659 let d = digit_of (raw.read_u8 text at) chars fold aliases
660 if d < 0
661 {
662 Error(InvalidChar(at))
663 }
664 else
665 {
666 value_of text (at + 1) (acc * base + d) chars base fold aliases
667 }
668 }
669}
670
671/// The last `n` bytes of `v`, big-endian, before `acc`.
672fn bytes_of :: v: Int n: Int acc: List<Int> -> List<Int>
673{
674 if n == 0
675 {
676 acc
677 }
678 else
679 {
680 bytes_of (v / 256) (n - 1) [v % 256, ..acc]
681 }
682}
683
684impl Show<Uuid>
685{
686 fn show :: id
687 {
688 encode id (crockford ())
689 }
690}
691
692impl Debug<Uuid>
693{
694 fn debug :: id
695 {
696 "uuid.Uuid({to_rfc id})"
697 }
698}