Debian Codegraph @

libsrc/scheme/charset.scm

raw
1 ;;;
2 ;;; scheme.charset
3 ;;;
4 ;;; Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; Originally SRFI-14
35 ;; Basic operators are built in the Gauche kernel. This module
36 ;; defines auxiliary procedures.
37 ;;
38 ;; Some of the procedures are implemented with no optimization
39 ;; effort. I included them just for completeness.
40 ;; If you think you need faster operation, please optimize it and
41 ;; send me a patch.
42 ;;
43 ;; ucs-range->char-set performs poorly if the given charcter code
44 ;; is outside ASCII and the native character encoding is not utf-8.
45
46 ;; Functions supported by the core interpreter:
47 ;; char-set char-set? char-set-contains? char-set-copy
48 ;; char-set-complement char-set-complement!
49 ;; %char-set-equal? %char-set-add-chars! %char-set-add-range!
50 ;; %char-set-add! %char-set-ranges
51 ;; Functions not in SRFI but defined here
52 ;; integer-range->char-set integer-range->char-set!
53
54 (define-module scheme.charset
55 (export char-set= char-set<=
56 char-set-cursor char-set-ref char-set-cursor-next end-of-char-set?
57 char-set-fold char-set-unfold char-set-unfold!
58 char-set-for-each char-set-map
59 list->char-set list->char-set! string->char-set string->char-set!
60 char-set-filter char-set-filter!
61 ucs-range->char-set ucs-range->char-set!
62 integer-range->char-set integer-range->char-set!
63 ->char-set
64 char-set-count char-set->list char-set->string
65 char-set-every char-set-any
66 char-set-adjoin char-set-adjoin! char-set-delete char-set-delete!
67 char-set-complement char-set-complement!
68 char-set-union char-set-union!
69 char-set-intersection char-set-intersection!
70 char-set-difference char-set-difference!
71 char-set-xor char-set-xor!
72 char-set-diff+intersection char-set-diff+intersection!
73 char-set:lower-case char-set:upper-case char-set:title-case
74 char-set:letter char-set:digit char-set:letter+digit
75 char-set:graphic char-set:printing char-set:whitespace
76 char-set:iso-control char-set:punctuation char-set:symbol
77 char-set:hex-digit char-set:blank char-set:ascii
78 char-set:empty char-set:full
79
80 ;; The followings are defined in core
81 char-set char-set? char-set-contains? char-set-copy
82 char-set-hash char-set-size
83 char-set-complement char-set-complement!
84 ))
85 (select-module scheme.charset)
86
87 ;; used in ->char-set
88 (autoload gauche.lazy x->lseq)
89
90 ;; some built-in support
91 (define %char-set-equal? (with-module gauche.internal %char-set-equal?))
92 (define %char-set<=? (with-module gauche.internal %char-set<=?))
93 (define %char-set-add-chars! (with-module gauche.internal %char-set-add-chars!))
94 (define %char-set-add-range! (with-module gauche.internal %char-set-add-range!))
95 (define %char-set-add! (with-module gauche.internal %char-set-add!))
96 (define %char-set-ranges (with-module gauche.internal %char-set-ranges))
97 (define %char-set-predefined (with-module gauche.internal %char-set-predefined))
98
99 (define char-set-complement (with-module gauche char-set-complement))
100 (define char-set-complement! (with-module gauche char-set-complement!))
101
102 ;; Predefined charsets - built-in
103
104 ;;-------------------------------------------------------------------
105 ;; Comparison
106 (define char-set=
107 (case-lambda [() #t]
108 [args (every %char-set-equal? args (cdr args))]))
109
110 (define char-set<=
111 (case-lambda [() #t]
112 [args (every %char-set<=? args (cdr args))]))
113
114 ;;-------------------------------------------------------------------
115 ;; Iteration
116 ;;
117
118 ;; slow implementation. minimal error check.
119 ;; cursor === (code . ranges) | #f
120
121 (define (char-set-cursor cs)
122 (let1 ranges (%char-set-ranges cs)
123 (if (null? ranges) #f (cons (caar ranges) ranges))))
124
125 (define (char-set-ref cs cursor)
126 (if (and (pair? cursor) (integer? (car cursor)))
127 (integer->char (car cursor))
128 (error "bad character-set cursor:" cursor)))
129
130 (define (char-set-cursor-next cs cursor)
131 (if (pair? cursor)
132 (let ([code (car cursor)]
133 [range (cadr cursor)])
134 (cond [(< code (cdr range)) (cons (+ code 1) (cdr cursor))]
135 [(null? (cddr cursor)) #f]
136 [else (cons (caaddr cursor) (cddr cursor))]))
137 (error "bad character-set cursor:" cursor)))
138
139 (define (end-of-char-set? cursor) (not cursor))
140
141 ;; functional ops
142
143 (define (char-set-fold kons knil cs)
144 (let loop ([cursor (char-set-cursor cs)]
145 [result knil])
146 (if (end-of-char-set? cursor)
147 result
148 (loop (char-set-cursor-next cs cursor)
149 (kons (char-set-ref cs cursor) result)))))
150
151 (define (char-set-unfold! pred fun gen seed base)
152 (let loop ([seed seed])
153 (if (pred seed)
154 base
155 (let1 c (fun seed)
156 (%char-set-add-range! base c c)
157 (loop (gen seed))))))
158
159 (define (char-set-unfold pred fun gen seed :optional (base char-set:empty))
160 (char-set-unfold! pred fun gen seed (char-set-copy base)))
161
162 (define (char-set-for-each proc cs)
163 (let loop ([cursor (char-set-cursor cs)])
164 (unless (end-of-char-set? cursor)
165 (proc (char-set-ref cs cursor))
166 (loop (char-set-cursor-next cs cursor)))))
167
168 (define (char-set-map proc cs)
169 (rlet1 new (char-set)
170 (let loop ([cursor (char-set-cursor cs)])
171 (unless (end-of-char-set? cursor)
172 (let1 c (proc (char-set-ref cs cursor))
173 (%char-set-add-range! new c c)
174 (loop (char-set-cursor-next cs cursor)))))))
175
176 ;;-------------------------------------------------------------------
177 ;; Construction
178 ;;
179
180 ;; char-set-copy : native
181 ;; char-set : native
182
183 (define (list->char-set chars :optional (base char-set:empty))
184 (%char-set-add-chars! (char-set-copy base) chars))
185
186 (define (list->char-set! chars base)
187 (%char-set-add-chars! base chars))
188
189 (define (string->char-set str :optional (base char-set:empty))
190 (%char-set-add-chars! (char-set-copy base) (string->list str)))
191
192 (define (string->char-set! str base)
193 (%char-set-add-chars! base (string->list str)))
194
195 (define (char-set-filter pred cs :optional (base char-set:empty))
196 (char-set-filter! pred cs (char-set-copy base)))
197
198 (define (char-set-filter! pred cs base)
199 (let loop ([cursor (char-set-cursor cs)])
200 (if (end-of-char-set? cursor)
201 base
202 (let1 c (char-set-ref cs cursor)
203 (when (pred c) (%char-set-add-range! base c c))
204 (loop (char-set-cursor-next cs cursor))))))
205
206 (define (integer-range->char-set low upper :optional (error? #f)
207 (base char-set:empty))
208 (integer-range->char-set! low upper error? (char-set-copy base)))
209
210 (define (integer-range->char-set! low upper error? base)
211 (when (< low 0)
212 (if error?
213 (error "argument out of range:" low)
214 (set! low 0)))
215 (when (> upper (+ *char-code-max* 1))
216 (if error?
217 (error "argument out of range:" upper)
218 (set! upper (+ *char-code-max* 1))))
219 (%char-set-add-range! base low (- upper 1)))
220
221 (define (ucs-range->char-set low upper :optional (error? #f)
222 (base char-set:empty))
223 (ucs-range->char-set! low upper error? (char-set-copy base)))
224
225 (define ucs-range->char-set!
226 (if (eq? (gauche-character-encoding) 'utf-8)
227 integer-range->char-set!
228 (^[low upper error? base]
229 (when (< low 0)
230 (if error?
231 (error "argument out of range:" low)
232 (set! low 0)))
233 (if (< upper 128)
234 (%char-set-add-range! base low (- upper 1))
235 (begin
236 (when (< low 128)
237 (%char-set-add-range! base low 128)
238 (set! low 128))
239 (do ([i low (+ i 1)])
240 [(>= i upper) base]
241 (let1 c (ucs->char i)
242 (if c
243 (%char-set-add-range! base c c)
244 (if error?
245 (errorf "unicode character #\\u~8,'0x is not supported in the native character set (~a)"
246 i (gauche-character-encoding)))))
247 )))
248 )
249 ))
250
251 (define (->char-set obj)
252 (cond [(list? obj) (list->char-set obj)]
253 [(string? obj) (string->char-set obj)]
254 [(char-set? obj) obj]
255 [(char? obj) (char-set obj)]
256 [(is-a? obj <collection>) (list->char-set (x->lseq obj))]
257 [else (errorf "cannot coerse ~s into a char-set" obj)]))
258
259 ;;-------------------------------------------------------------------
260 ;; Querying
261 ;;
262
263 (define (char-set-count pred cs)
264 (char-set-fold (^[c r] (if (pred c) (+ r 1) r)) 0 cs))
265
266 (define (char-set->list cs)
267 (char-set-fold cons '() cs))
268
269 (define (char-set->string cs)
270 (list->string (char-set-fold cons '() cs)))
271
272 ;; char-set-contains? : native
273
274 (define (char-set-every pred cs)
275 (let loop ((cursor (char-set-cursor cs)))
276 (cond ((end-of-char-set? cursor))
277 ((pred (char-set-ref cs cursor))
278 (loop (char-set-cursor-next cs cursor)))
279 (else #f))))
280
281 (define (char-set-any pred cs)
282 (let loop ((cursor (char-set-cursor cs)))
283 (cond ((end-of-char-set? cursor) #f)
284 ((pred (char-set-ref cs cursor)) #t)
285 (else (loop (char-set-cursor-next cs cursor))))))
286
287 ;;-------------------------------------------------------------------
288 ;; Algebra
289 ;;
290
291 ;; auxiliary functions for range operation other than adjoin and union.
292 ;; (adjoin and union can use native functions). These can also be defined
293 ;; in C, but I don't see the needs of performance yet.
294 (define (%char-set-sub-range ranges from to)
295 (let loop ((ranges ranges)
296 (result '()))
297 (if (null? ranges)
298 (reverse result)
299 (let ((lo (caar ranges))
300 (hi (cdar ranges))
301 (next (cdr ranges)))
302 (if (<= lo from hi)
303 (if (<= lo to hi)
304 (if (= lo from)
305 (if (= to hi)
306 (loop next result)
307 (loop next (acons (+ to 1) hi result)))
308 (if (= to hi)
309 (loop next (acons lo (- from 1) result))
310 (loop next (list* (cons (+ to 1) hi)
311 (cons lo (- from 1))
312 result))))
313 (if (= lo from)
314 (loop next result)
315 (loop next (acons lo (- from 1) result))))
316 (if (<= lo to hi)
317 (if (= to hi)
318 (loop next result)
319 (loop next (acons (+ to 1) hi result)))
320 (if (and (< from lo) (< hi to))
321 (loop next result)
322 (loop next (acons lo hi result)))))
323 ))
324 ))
325
326 (define (%char-set-sub-chars range chars)
327 (let loop ((range range)
328 (chars chars))
329 (if (null? chars)
330 range
331 (let ((code (char->integer (car chars))))
332 (loop (%char-set-sub-range range code code) (cdr chars))))))
333
334 (define (%ranges->char-set ranges)
335 (let ((base (char-set)))
336 (for-each (^[range] (%char-set-add-range! base (car range) (cdr range)))
337 ranges)
338 base))
339
340 (define (char-set-adjoin base . chars)
341 (if (null? chars) base (%char-set-add-chars! (char-set-copy base) chars)))
342
343 (define (char-set-adjoin! base . chars)
344 (%char-set-add-chars! base chars))
345
346 (define (char-set-delete base . chars)
347 (%ranges->char-set (%char-set-sub-chars (%char-set-ranges base) chars)))
348
349 (define char-set-delete! char-set-delete)
350
351 (define (char-set-union . charsets)
352 (if (null? charsets)
353 char-set:empty
354 (let loop ((base (char-set-copy (car charsets)))
355 (rest (cdr charsets)))
356 (if (null? rest)
357 base
358 (loop (%char-set-add! base (car rest)) (cdr rest))))))
359
360 (define (char-set-union! base . charsets)
361 (if (null? charsets)
362 base
363 (let loop ((base base) (rest charsets))
364 (if (null? rest)
365 base
366 (loop (%char-set-add! base (car rest)) (cdr rest))))))
367
368 (define (%char-set-intersection2 x y)
369 (char-set-difference x (char-set-complement y)))
370
371 (define (char-set-intersection . charsets)
372 (cond ((null? charsets) char-set:full)
373 ((null? (cdr charsets)) (car charsets))
374 (else (apply char-set-intersection
375 (%char-set-intersection2 (car charsets) (cadr charsets))
376 (cddr charsets)))))
377
378 (define (char-set-intersection! base . charsets)
379 (if (null? charsets)
380 base
381 (apply char-set-intersection base charsets)))
382
383 (define (char-set-difference base . charsets)
384 (define (char-range-sub2 ranges sub)
385 (let loop ((ranges ranges) (sub sub))
386 (if (null? sub)
387 ranges
388 (loop (%char-set-sub-range ranges (caar sub) (cdar sub))
389 (cdr sub)))))
390
391 (let loop ((ranges (%char-set-ranges base))
392 (sets charsets))
393 (if (null? sets)
394 (%ranges->char-set ranges)
395 (loop (char-range-sub2 ranges (%char-set-ranges (car sets)))
396 (cdr sets))))
397 )
398 (define char-set-difference! char-set-difference)
399
400 (define (%char-set-xor2 x y)
401 (char-set-difference (char-set-union x y)
402 (%char-set-intersection2 x y)))
403
404 (define (char-set-xor . charsets)
405 (cond ((null? charsets) char-set:empty)
406 ((null? (cdr charsets)) (car charsets))
407 (else (apply char-set-xor
408 (%char-set-xor2 (car charsets) (cadr charsets))
409 (cddr charsets)))))
410
411 (define (char-set-xor! base . charsets)
412 (if (null? charsets)
413 base
414 (apply char-set-xor base charsets)))
415
416 (define (char-set-diff+intersection base . charsets)
417 (values (apply char-set-difference base charsets)
418 (char-set-intersection base (apply char-set-union charsets))))
419
420 ;; NB: We don't modify the arguments so far; if we do modify them,
421 ;; we need to be careful about the operation order.
422 (define (char-set-diff+intersection! cs1 cs2 . charsets)
423 (values (apply char-set-difference cs1 cs2 charsets)
424 (char-set-intersection cs1 (apply char-set-union cs2 charsets))))