| 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)))) |