| 1 |
;;; |
| 2 |
;;; tr.scm - transliterate characters |
| 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 |
;;; tr(1) equivalent. |
| 35 |
|
| 36 |
(define-module text.tr |
| 37 |
(use scheme.list) |
| 38 |
(use srfi.13) |
| 39 |
(use gauche.generator) |
| 40 |
(export tr transliterate string-tr string-transliterate |
| 41 |
build-transliterator) |
| 42 |
) |
| 43 |
(select-module text.tr) |
| 44 |
|
| 45 |
(define (tr from to . options) |
| 46 |
((apply build-transliterator from to options))) |
| 47 |
|
| 48 |
(define transliterate tr) ;alias |
| 49 |
|
| 50 |
(define (string-tr str from to . options) |
| 51 |
(with-string-io str (cut apply tr from to options))) |
| 52 |
|
| 53 |
(define string-transliterate string-tr) ;alias |
| 54 |
|
| 55 |
(define (build-transliterator from to :key ((:delete d?) #f) ((:squeeze s?) #f) |
| 56 |
((:complement c?) #f) ((:table-size size) 256) |
| 57 |
(input #f) (output #f)) |
| 58 |
(let1 tab (build-tr-table from to size c?) |
| 59 |
(^[] |
| 60 |
(let ([in (or input (current-input-port))] |
| 61 |
[out (or output (current-output-port))]) |
| 62 |
(let loop ([char (read-char in)] [prev #f]) |
| 63 |
(unless (eof-object? char) |
| 64 |
(let1 c (tr-table-ref tab (char->integer char)) |
| 65 |
(cond |
| 66 |
[(char? c) ;transliterated |
| 67 |
(unless (and s? (eqv? prev c)) (display c out)) |
| 68 |
(loop (read-char in) c)] |
| 69 |
[c ;char is not in from-set |
| 70 |
(display char out) |
| 71 |
(loop (read-char in) #f)] |
| 72 |
[(not d?) ;char is in from but not to, and no :d |
| 73 |
(unless (and s? (eqv? prev char)) (display char out)) |
| 74 |
(loop (read-char in) char)] |
| 75 |
[else |
| 76 |
(loop (read-char in) prev)])))))))) |
| 77 |
|
| 78 |
;;-------------------------------------------------------------------- |
| 79 |
;; Parse character array syntax |
| 80 |
;; |
| 81 |
;; We can't naively expand character ranges, for it may be huge |
| 82 |
;; when multibyte characters involved. |
| 83 |
;; |
| 84 |
;; The character array spec is canonicalized to the list of |
| 85 |
;; those elements: |
| 86 |
;; |
| 87 |
;; (<n> <char>) - a single character (repeat <n> times) |
| 88 |
;; (<n> <from> <to>) - character range from <from> to <to>, inclusive. |
| 89 |
;; the size is <n>. |
| 90 |
|
| 91 |
;; "A-Za-z" => ((26 #\A #\Z) (26 #\a #\z)) |
| 92 |
;; The grouping never crosses the boundary of table-size, i.e. if the table |
| 93 |
;; size is 70 ('F'), "A-Z" => ((6 #\A #\F) (20 #\G #\Z)) |
| 94 |
(define (build-char-array spec table-size) |
| 95 |
(with-input-from-string spec |
| 96 |
(^[] |
| 97 |
(define (check-stray c) |
| 98 |
(when (eof-object? c) |
| 99 |
(error "stray backslash in tr spec" spec))) |
| 100 |
(define (start c r) |
| 101 |
(cond [(eof-object? c) (reverse r)] |
| 102 |
[(char=? c #\\) (let1 c (read-char) |
| 103 |
(check-stray c) |
| 104 |
(maybe-range c (read-char) r))] |
| 105 |
[else (maybe-range c (read-char) r)])) |
| 106 |
(define (maybe-range c c1 r) |
| 107 |
(cond [(eof-object? c1) (reverse (cons (list 1 c) r))] |
| 108 |
[(char=? c1 #\-) (range c (read-char) r)] |
| 109 |
[(char=? c1 #\*) (repeat c (read-char) 0 r)] |
| 110 |
[(char=? c1 #\\) |
| 111 |
(let1 c1 (read-char) |
| 112 |
(check-stray c1) |
| 113 |
(maybe-range c1 (read-char) (cons (list 1 c) r)))] |
| 114 |
[else (maybe-range c1 (read-char) (cons (list 1 c) r))])) |
| 115 |
(define (range from to r) |
| 116 |
(cond [(eof-object? to) (reverse (list* (list 1 #\-) (list 1 from) r))] |
| 117 |
[else |
| 118 |
(let* ([fromi (char->integer from)] |
| 119 |
[toi (char->integer to)] |
| 120 |
[size (- toi fromi -1)]) |
| 121 |
(when (negative? size) |
| 122 |
(errorf "wrong character order: ~a-~a" from to)) |
| 123 |
(if (and (< fromi table-size) (<= table-size toi)) |
| 124 |
(start (read-char) |
| 125 |
(list* (list (- toi table-size) |
| 126 |
(integer->char table-size) |
| 127 |
to) |
| 128 |
(list (- table-size fromi) |
| 129 |
from |
| 130 |
(integer->char (- table-size 1))) |
| 131 |
r)) |
| 132 |
(start (read-char) |
| 133 |
(cons (list size from to) r))))])) |
| 134 |
(define (repeat c d n r) |
| 135 |
(cond [(eof-object? d) |
| 136 |
(reverse (cons (list (if (= n 0) *char-code-max* n) c) r))] |
| 137 |
[(char-numeric? d) |
| 138 |
(repeat c (read-char) (+ (* n 10) (digit->integer d)) r)] |
| 139 |
[else |
| 140 |
(start d (cons (list (if (= n 0) *char-code-max* n) c) r))])) |
| 141 |
|
| 142 |
(start (read-char) '())))) |
| 143 |
|
| 144 |
;; size of the array |
| 145 |
(define (char-array-size array) |
| 146 |
(fold (^[elt n] (+ (car elt) n)) 0 array)) |
| 147 |
|
| 148 |
;; ref |
| 149 |
(define (char-array-ref array index) |
| 150 |
(let loop ([array array] |
| 151 |
[cnt 0]) |
| 152 |
(cond [(null? array) #f] |
| 153 |
[(>= index (+ cnt (caar array))) |
| 154 |
(loop (cdr array) (+ cnt (caar array)))] |
| 155 |
[(null? (cddar array)) (cadar array)] |
| 156 |
[else (let ([from (char->integer (cadar array))] |
| 157 |
[to (char->integer (caddar array))]) |
| 158 |
(integer->char (+ from (- index cnt))))]))) |
| 159 |
|
| 160 |
;; complement. array doesn't contain repeat. |
| 161 |
(define (complement-char-array array table-size) |
| 162 |
(define (add-range from to rest) |
| 163 |
(if (and (< from table-size) (<= table-size to)) |
| 164 |
(list* (list (- to table-size -1) |
| 165 |
(integer->char table-size) |
| 166 |
(integer->char to)) |
| 167 |
(list (- table-size from) |
| 168 |
(integer->char from) |
| 169 |
(integer->char (- table-size 1))) |
| 170 |
rest) |
| 171 |
(cons (list (- to from -1) (integer->char from) (integer->char to)) |
| 172 |
rest))) |
| 173 |
(let loop ([in (sort-by array cadr)] |
| 174 |
[out '()] |
| 175 |
[index 0]) |
| 176 |
(if (null? in) |
| 177 |
(if (<= index *char-code-max*) |
| 178 |
(reverse! (add-range index *char-code-max* out)) |
| 179 |
(reverse! out)) |
| 180 |
(let* ([lo (char->integer (cadar in))] |
| 181 |
[hi (+ lo (caar in))]) |
| 182 |
(if (< index lo) |
| 183 |
(loop (cdr in) |
| 184 |
(add-range index (- lo 1) out) |
| 185 |
hi) |
| 186 |
(loop (cdr in) out hi)))))) |
| 187 |
|
| 188 |
;; `split' the char array at given index |
| 189 |
;; (split-char-array '((26 #\A #\Z)) 1) => ((1 #\A)) and ((25 #\B #\Z)) |
| 190 |
(define (split-char-array array index) |
| 191 |
(define (split-segment segment index) |
| 192 |
(let ([size (car segment)] |
| 193 |
[from (cadr segment)]) |
| 194 |
(if (null? (cddr segment)) |
| 195 |
(values (list index from) |
| 196 |
(list (- size index) from)) |
| 197 |
(values (list index |
| 198 |
from |
| 199 |
(integer->char (+ index (char->integer from) -1))) |
| 200 |
(list (- size index) |
| 201 |
(integer->char (+ index (char->integer from))) |
| 202 |
(caddr segment)))))) |
| 203 |
(if (zero? index) |
| 204 |
(values '() array) |
| 205 |
(let loop ([in array] |
| 206 |
[out '()] |
| 207 |
[cnt 0]) |
| 208 |
(if (null? in) |
| 209 |
(values (reverse out) '()) |
| 210 |
(let* ([size (caar in)] |
| 211 |
[next (+ cnt size)]) |
| 212 |
(cond [(< index next) |
| 213 |
(receive (lo hi) |
| 214 |
(split-segment (car in) (- index cnt)) |
| 215 |
(values (reverse (cons lo out)) (cons hi (cdr in))))] |
| 216 |
[(= index next) |
| 217 |
(values (reverse (cons (car in) out)) (cdr in))] |
| 218 |
[else |
| 219 |
(loop (cdr in) (cons (car in) out) next)])))))) |
| 220 |
|
| 221 |
;; "from" character list shouldn't contain |
| 222 |
(define (check-from-spec-validity spec array) |
| 223 |
(dolist [segment array] |
| 224 |
(when (and (< 1 (car segment)) (null? (cddr segment))) |
| 225 |
(error "from-spec can't contain repeat characters" spec)))) |
| 226 |
|
| 227 |
;;-------------------------------------------------------------------- |
| 228 |
;; Table of transliteration |
| 229 |
;; |
| 230 |
;; A vector is used for characters whose code < 256. Indexed by the |
| 231 |
;; input character. The value may be either |
| 232 |
;; |
| 233 |
;; * a character to be transliterated |
| 234 |
;; * #f - no entry |
| 235 |
;; * procedure |
| 236 |
;; |
| 237 |
;; List is used for larger characters. |
| 238 |
;; |
| 239 |
;; The list is consisted by the elements of one of the following type: |
| 240 |
;; |
| 241 |
;; (from to <integer>) |
| 242 |
;; An input character between from and to (inclusive) is |
| 243 |
;; transliterated to (<integer> + index - from) |
| 244 |
;; |
| 245 |
;; (from to <char>) |
| 246 |
;; An input character between from and to (inclusive) is |
| 247 |
;; transliterated to <char> |
| 248 |
;; |
| 249 |
;; (from to procedure) |
| 250 |
;; The procedure is called. |
| 251 |
;; |
| 252 |
|
| 253 |
(define-class <tr-table> () |
| 254 |
((vector-size :init-keyword :vector-size :initform 256) |
| 255 |
(vector) |
| 256 |
(sparse :initform '()) |
| 257 |
)) |
| 258 |
|
| 259 |
(define-method initialize ((self <tr-table>) initargs) |
| 260 |
(next-method) |
| 261 |
(let1 size (~ self 'vector-size) |
| 262 |
(set! (~ self'vector) (make-vector size #t)))) |
| 263 |
|
| 264 |
;; Returns |
| 265 |
;; char - mapped char |
| 266 |
;; #f - appears in from-set but not to-set |
| 267 |
;; #t - doesn't appear in from-set |
| 268 |
(define (tr-table-ref tab index) |
| 269 |
(if (< index (~ tab 'vector-size)) |
| 270 |
(vector-ref (~ tab'vector) index) |
| 271 |
(let loop ([e (~ tab'sparse)]) |
| 272 |
(cond [(null? e) #t] |
| 273 |
[(<= (caar e) index (cadar e)) |
| 274 |
(let1 v (caddar e) |
| 275 |
(if (integer? v) |
| 276 |
(integer->char (+ v (- index (caar e)))) |
| 277 |
v))] |
| 278 |
[else (loop (cdr e))])))) |
| 279 |
|
| 280 |
(define (build-tr-table from-spec to-spec size compl?) |
| 281 |
(rlet1 tab (make <tr-table> :vector-size size) |
| 282 |
(let ([from-ca (build-char-array from-spec size)] |
| 283 |
[to-ca (build-char-array to-spec size)]) |
| 284 |
(check-from-spec-validity from-spec from-ca) |
| 285 |
(fill-tr-table tab |
| 286 |
(if compl? |
| 287 |
(complement-char-array from-ca size) |
| 288 |
from-ca) |
| 289 |
to-ca)))) |
| 290 |
|
| 291 |
(define (fill-tr-table tab from-ca to-ca) |
| 292 |
(let loop ([from-ca from-ca] |
| 293 |
[to-ca to-ca]) |
| 294 |
(if (null? from-ca) |
| 295 |
tab |
| 296 |
(let* ([vsiz (~ tab 'vector-size)] |
| 297 |
[from-seg (car from-ca)] |
| 298 |
[size (car from-seg)]) |
| 299 |
(receive (to-segs to-rest) (split-char-array to-ca size) |
| 300 |
(if (< (char->integer (cadr from-seg)) vsiz) |
| 301 |
(fill-tr-vector tab from-seg to-segs) |
| 302 |
(fill-tr-sparse tab from-seg to-segs)) |
| 303 |
(loop (cdr from-ca) to-rest)))))) |
| 304 |
|
| 305 |
(define (fill-tr-vector tab from-seg to-ca) |
| 306 |
(do ([v (~ tab'vector)] |
| 307 |
[size (car from-seg)] |
| 308 |
[from-ch (char->integer (cadr from-seg)) (+ from-ch 1)] |
| 309 |
[cnt 0 (+ cnt 1)]) |
| 310 |
[(= cnt size)] |
| 311 |
;; This check avois overwriting entry when from-list contains duplicate |
| 312 |
;; character. We consider only the first character for mapping. |
| 313 |
(when (eqv? #t (vector-ref v from-ch)) |
| 314 |
(vector-set! v from-ch (char-array-ref to-ca cnt))))) |
| 315 |
|
| 316 |
(define (fill-tr-sparse tab from-seg to-ca) |
| 317 |
(let loop ([from-ch (char->integer (cadr from-seg))] |
| 318 |
[to-segs to-ca] |
| 319 |
[r '()]) |
| 320 |
(if (null? to-segs) |
| 321 |
(let* ([from-end (+ (car from-seg) (char->integer (cadr from-seg)))] |
| 322 |
[rr (if (< from-ch from-end) |
| 323 |
(reverse (cons (list from-ch (- from-end 1) #f) r)) |
| 324 |
(reverse r))]) |
| 325 |
(set! (~ tab'sparse) (append! (~ tab'sparse) rr))) |
| 326 |
(let* ([to-seg (car to-segs)] |
| 327 |
[to-size (car to-seg)] |
| 328 |
[entry (list from-ch (+ from-ch to-size -1) |
| 329 |
(if (null? (cddr to-seg)) |
| 330 |
(cadr to-seg) |
| 331 |
(char->integer (cadr to-seg))))]) |
| 332 |
(loop (+ from-ch to-size) (cdr to-segs) (cons entry r)))))) |