Debian Codegraph @

libsrc/text/tr.scm

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