Debian Codegraph @

lib/data/ulid.scm

raw
1 ;;;
2 ;;; data.ulid - ULID
3 ;;;
4
5 ;; This is Gauche-specific port of https://github.com/shirok/scheme-ulid
6
7 ;; Copyright 2022-2024 by Shiro Kawai <[email protected]>
8
9 ;; Permission is hereby granted, free of charge, to any person obtaining
10 ;; a copy of this software and associated documentation files (the
11 ;; "Software"), to deal in the Software without restriction, including
12 ;; without limitation the rights to use, copy, modify, merge, publish,
13 ;; distribute, sublicense, and/or sell copies of the Software, and to
14 ;; permit persons to whom the Software is furnished to do so, subject to
15 ;; the following conditions:
16
17 ;; The above copyright notice and this permission notice shall be
18 ;; included in all copies or substantial portions of the Software.
19
20 ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 ;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 ;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 ;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 ;; LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 ;; OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 ;; WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27
28 (define-module data.ulid
29 (use gauche.record)
30 (use gauche.uvector)
31 (use scheme.bitwise)
32 (use scheme.vector)
33 (use srfi.13)
34 (use srfi.19)
35 (use srfi.27)
36 (export make-ulid-generator
37 ulid?
38 ulid-timestamp
39 ulid-randomness
40 ulid=?
41 ulid<?
42 ulid-hash
43 ulid-comparator
44 ulid->string
45 ulid->integer
46 ulid->bytevector
47 string->ulid
48 integer->ulid
49 bytevector->ulid))
50 (select-module data.ulid)
51
52 (define (milliseconds-from-epoch)
53 (receive (secs usecs) (sys-gettimeofday)
54 (+ (* secs 1000) (quotient usecs 1000))))
55
56 (define (wait-a-bit ri) (sys-nanosleep 500000))
57
58 (define *randomness-range* (expt 2 80))
59 (define *digits* (string->vector "0123456789ABCDEFGHJKMNPQRSTVWXYZ"))
60
61 ;; Ulid record
62 (define-record-type ulid %make-ulid ulid?
63 (timestamp ulid-timestamp)
64 (randomness ulid-randomness))
65
66 (define ulid-random-source
67 (rlet1 s (make-random-source)
68 (random-source-randomize! s)))
69
70 ;; API
71 ;; NB: The ULID spec says ULID generation may fail if randomness is very close
72 ;; to 2^80 and lots of ULIDs are generated in the same millisecond, causing
73 ;; randomness field to overflow. We can, however, wait just one millisecond
74 ;; to overcome that situation.
75 (define (make-ulid-generator :optional (random-source ulid-random-source))
76 (let ((randomness (random-source-make-integers random-source))
77 (last-ts 0)
78 (last-rn 0))
79 (define (make-it ts rn)
80 (set! last-ts ts)
81 (set! last-rn rn)
82 (%make-ulid ts rn))
83 (^(:optional (timestamp #f))
84 (let retry ()
85 (let ((ts (or timestamp (milliseconds-from-epoch))))
86 (if (not (= ts last-ts))
87 (make-it ts (randomness *randomness-range*))
88 (if (< last-rn (- *randomness-range* 1))
89 (make-it ts (+ last-rn 1))
90 (begin
91 (wait-a-bit randomness)
92 (retry)))))))))
93
94 ;; API
95 (define (ulid=? u1 u2)
96 (assume (ulid? u1))
97 (assume (ulid? u2))
98 (and (= (ulid-timestamp u1) (ulid-timestamp u2))
99 (= (ulid-randomness u1) (ulid-randomness u2))))
100
101 ;; API
102 (define (ulid<? u1 u2)
103 (assume (ulid? u1))
104 (assume (ulid? u2))
105 (or (< (ulid-timestamp u1) (ulid-timestamp u2))
106 (and (= (ulid-timestamp u1) (ulid-timestamp u2))
107 (< (ulid-randomness u1) (ulid-randomness u2)))))
108
109 ;; API
110 (define (ulid-hash u)
111 (bitwise-xor (default-hash (ulid-timestamp u))
112 (default-hash (ulid-randomness u))))
113
114 ;; API
115 (define ulid-comparator
116 (make-comparator ulid? ulid=? ulid<? ulid-hash))
117
118 ;; API
119 (define (ulid->bytevector ulid)
120 (assume (ulid? ulid))
121 (let ((uv (make-u8vector 16))
122 (ts (ulid-timestamp ulid))
123 (rn (ulid-randomness ulid)))
124 (u8vector-set! uv 0 (arithmetic-shift ts -40))
125 (u8vector-set! uv 1 (bitwise-and (arithmetic-shift ts -32) #xff))
126 (u8vector-set! uv 2 (bitwise-and (arithmetic-shift ts -24) #xff))
127 (u8vector-set! uv 3 (bitwise-and (arithmetic-shift ts -16) #xff))
128 (u8vector-set! uv 4 (bitwise-and (arithmetic-shift ts -8) #xff))
129 (u8vector-set! uv 5 (bitwise-and ts #xff))
130
131 (u8vector-set! uv 6 (arithmetic-shift rn -72))
132 (u8vector-set! uv 7 (bitwise-and (arithmetic-shift rn -64) #xff))
133 (u8vector-set! uv 8 (bitwise-and (arithmetic-shift rn -56) #xff))
134 (u8vector-set! uv 9 (bitwise-and (arithmetic-shift rn -48) #xff))
135 (u8vector-set! uv 10 (bitwise-and (arithmetic-shift rn -40) #xff))
136 (u8vector-set! uv 11 (bitwise-and (arithmetic-shift rn -32) #xff))
137 (u8vector-set! uv 12 (bitwise-and (arithmetic-shift rn -24) #xff))
138 (u8vector-set! uv 13 (bitwise-and (arithmetic-shift rn -16) #xff))
139 (u8vector-set! uv 14 (bitwise-and (arithmetic-shift rn -8) #xff))
140 (u8vector-set! uv 15 (bitwise-and rn #xff))
141 uv))
142
143 ;; API
144 (define (ulid->integer ulid)
145 (+ (arithmetic-shift (ulid-timestamp ulid) 80)
146 (ulid-randomness ulid)))
147
148 ;; API
149 (define (ulid->string ulid)
150 (do ((i 0 (+ i 1))
151 (v (ulid->integer ulid) (arithmetic-shift v -5))
152 (cs '() (cons (vector-ref *digits* (bitwise-and v #x1f)) cs)))
153 ((= i 26) (list->string cs))))
154
155
156 ;; API
157 (define (bytevector->ulid uv)
158 (define (get-uint start size)
159 (do ((i start (+ i 1))
160 (size size (- size 1))
161 (v 0 (+ (arithmetic-shift v 8) (u8vector-ref uv i))))
162 ((zero? size) v)))
163 (assume (and (u8vector? uv) (= (bytevector-length uv) 16)))
164 (%make-ulid (get-uint 0 6) (get-uint 6 10)))
165
166 ;; API
167 (define (integer->ulid n)
168 (assume (and (exact? n) (positive? n) (< n (expt 2 128))))
169 (%make-ulid (arithmetic-shift n -80)
170 (bitwise-and n (- (expt 2 80) 1))))
171
172 ;; API
173 (define (string->ulid s)
174 (assume (and (string? s) (= (string-length s) 26)))
175 (let ((val
176 (string-fold (lambda (ch n)
177 (let ((d (vector-index (lambda (c) (char-ci=? ch c))
178 *digits*)))
179 (unless d
180 (error "Invalid character as ULID:" ch))
181 (+ (arithmetic-shift n 5) d)))
182 0 s)))
183 (when (>= val (expt 2 128))
184 (error "ULID string representation out of range:" s))
185 (integer->ulid val)))
186
187 ;; Fancier printing, if possible
188 (define-method write-object ((u ulid) port)
189 (format port "#<ulid ~a>" (ulid->string u)))