Debian Codegraph @

libsrc/srfi/13.scm

raw
1 ;;;
2 ;;; srfi-13.scm - string library
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 (define-module srfi.13
35 (export string-null? string-every string-any
36 string-tabulate reverse-list->string
37 substring/shared string-copy!
38 string-take string-take-right
39 string-drop string-drop-right
40 string-pad string-pad-right
41 string-trim string-trim-right string-trim-both
42 string-compare string-compare-ci
43 string= string<> string< string> string<= string>=
44 string-ci= string-ci<> string-ci< string-ci> string-ci<= string-ci>=
45 string-hash string-hash-ci
46 string-prefix-length string-suffix-length
47 string-prefix-length-ci string-suffix-length-ci
48 string-prefix? string-suffix?
49 string-prefix-ci? string-suffix-ci?
50 string-index string-index-right
51 string-skip string-skip-right
52 string-count string-contains string-contains-ci
53 string-titlecase string-titlecase!
54 string-upcase string-upcase!
55 string-downcase string-downcase!
56 string-reverse string-reverse!
57 string-concatenate string-append/shared string-concatenate/shared
58 string-concatenate-reverse string-concatenate-reverse/shared
59 string-map string-map!
60 string-fold string-fold-right
61 string-unfold string-unfold-right
62 string-for-each string-for-each-index
63 xsubstring string-xcopy!
64 string-replace string-tokenize
65 string-filter string-delete
66 string-parse-start+end string-parse-final-start+end
67 let-string-start+end
68 check-substring-spec substring-spec-ok?
69 make-kmp-restart-vector
70 kmp-step
71 string-kmp-partial-search
72
73 ;; Gauche supports the following functions natively, but
74 ;; we re-export them so that they will be available by
75 ;; importing SRFI-13 into vanilla environment.
76 string? make-string string string->list list->string
77 string-join string-length string-ref string-copy
78 string-set! string-fill!
79 string-append string-map string-for-each
80 ))
81 (select-module srfi.13)
82
83 ;; Utility macro to handle char/char-set/pred match.
84 ;; To avoid closure creation in inner loop, this returns a static procedure
85 ;; that takes char/char-set/pred and char.
86 ;; NB: This is not exported, but shared with SRFI-152.
87 (define-inline (%get-char-pred char/char-set/pred)
88 (cond [(char? char/char-set/pred) char=?]
89 [(char-set? char/char-set/pred) char-set-contains?]
90 [(procedure? char/char-set/pred) %char-pred/pred]
91 [else (error "argument needs to be either a character, a char-set, \
92 or a procedure:" char/char-set/pred)]))
93
94 (define (%char-pred/pred c/s/p x) (c/s/p x))
95
96 (define %hash-string (with-module gauche.internal %hash-string))
97 (define %string-replace-body! (with-module gauche.internal %string-replace-body!))
98 ;;;
99 ;;; Predicates
100 ;;;
101
102 (define (string-null? str)
103 (assume-type str <string>)
104 (equal? "" str))
105
106 (define (string-every c/s/p s . args)
107 (let* ((src (open-input-string (apply opt-substring s args)))
108 (pred (%get-char-pred c/s/p)))
109 (let loop ((ch (read-char src))
110 (r #t))
111 (cond ((not r) #f)
112 ((eof-object? ch) r)
113 (else (loop (read-char src) (pred c/s/p ch)))))))
114
115 (define (string-any c/s/p s . args)
116 (let* ((src (open-input-string (apply opt-substring s args)))
117 (pred (%get-char-pred c/s/p)))
118 (let loop ((ch (read-char src)))
119 (cond ((eof-object? ch) #f)
120 ((pred c/s/p ch))
121 (else (loop (read-char src)))))))
122
123 ;;;
124 ;;; Generators
125 ;;;
126
127 (define (string-tabulate proc len)
128 (check-arg (^l (and (integer? l) (>= l 0))) len)
129 (let ((sink (open-output-string)))
130 (do ((i 0 (+ i 1)))
131 ((>= i len) (get-output-string sink))
132 (write-char (proc i) sink))))
133
134 (define (reverse-list->string char-list)
135 (list->string (reverse char-list)))
136
137 ;;;
138 ;;; Selectors
139 ;;;
140
141 (define substring/shared string-copy) ; same in Gauche
142
143 (define (string-copy! target tstart s . args)
144 (assume-type target <string>)
145 (check-arg (^x (and (integer? x) (>= x 0))) tstart)
146 (let* ((str (apply opt-substring s args))
147 (slen (string-length str))
148 (tlen (string-length target)))
149 (when (> (+ tstart slen) tlen)
150 (error "copy operation runs off the target string:" target))
151 (if (= slen tlen)
152 (%string-replace-body! target str)
153 (%string-replace-body! target
154 (string-append (substring target 0 tstart)
155 str
156 (substring target
157 (+ tstart slen)
158 tlen))))))
159
160 (define (string-pad s len :optional (char #\space) start end)
161 (assume-type char <char>)
162 (let* ((str (opt-substring s start end))
163 (slen (string-length str)))
164 (cond ((< slen len)
165 (string-append (make-string (- len slen) char) str))
166 ((> slen len)
167 (string-take-right str len))
168 (else str))))
169
170 (define (string-pad-right s len :optional (char #\space) start end)
171 (assume-type char <char>)
172 (let* ((str (opt-substring s start end))
173 (slen (string-length str)))
174 (cond ((< slen len)
175 (string-append str (make-string (- len slen) char)))
176 ((> slen len)
177 (string-take str len))
178 (else str))))
179
180 (define (string-take s nchars)
181 (assume-type s <string>)
182 (when (or (< nchars 0) (> nchars (string-length s)))
183 (error "argument out of range:" nchars))
184 (opt-substring s 0 nchars))
185
186 (define (string-drop s nchars)
187 (assume-type s <string>)
188 (when (or (< nchars 0) (> nchars (string-length s)))
189 (error "argument out of range:" nchars))
190 (opt-substring s nchars))
191
192 (define (string-take-right s nchars)
193 (assume-type s <string>)
194 (when (or (< nchars 0) (> nchars (string-length s)))
195 (error "argument out of range:" nchars))
196 (opt-substring s (- (string-length s) nchars)))
197
198 (define (string-drop-right s nchars)
199 (assume-type s <string>)
200 (when (or (< nchars 0) (> nchars (string-length s)))
201 (error "argument out of range:" nchars))
202 (opt-substring s 0 (- (string-length s) nchars)))
203
204 (define (string-trim s :optional
205 (c/s/p #[\s])
206 (start 0)
207 (end (string-cursor-end s)))
208 (substring s (values-ref (%string-skip s c/s/p start end) 0) end))
209
210 (define (string-trim-right s :optional
211 (c/s/p #[\s])
212 (start 0)
213 (end (string-cursor-end s)))
214 (substring s start (values-ref (%string-skip-right s c/s/p start end) 0)))
215
216 (define (string-trim-both s :optional
217 (c/s/p #[\s])
218 (start 0)
219 (end (string-cursor-end s)))
220 (let1 new-start (values-ref (%string-skip s c/s/p start end) 0)
221 (substring s new-start
222 (values-ref (%string-skip-right s c/s/p new-start end) 0))))
223
224 ;;;
225 ;;; Comparison functions
226 ;;;
227
228 (define (%string-compare-int off str1 str2 cmp< cmp> proc< proc= proc>)
229 (let ((end1 (string-cursor-end str1))
230 (end2 (string-cursor-end str2)))
231 (let loop ((cur1 (string-cursor-start str1))
232 (cur2 (string-cursor-start str2))
233 (off off))
234 (cond ((string-cursor=? cur1 end1)
235 (if (string-cursor=? cur2 end2) (proc= off) (proc< off)))
236 ((string-cursor=? cur2 end2)
237 (proc> off))
238 ((cmp< (string-ref str1 cur1) (string-ref str2 cur2))
239 (proc< off))
240 ((cmp> (string-ref str1 cur1) (string-ref str2 cur2))
241 (proc> off))
242 (else (loop (string-cursor-next str1 cur1)
243 (string-cursor-next str2 cur2)
244 (+ off 1)))))))
245
246 (define (string-compare s1 s2 proc< proc= proc>
247 :optional (start1 0) end1 start2 end2)
248 (assume-type s1 <string>)
249 (assume-type s2 <string>)
250 (let ((str1 (opt-substring s1 start1 end1))
251 (str2 (opt-substring s2 start2 end2)))
252 (%string-compare-int start1 str1 str2
253 char<? char>?
254 proc< proc= proc>)))
255
256 (define (string-compare-ci s1 s2 proc< proc= proc>
257 :optional (start1 0) end1 start2 end2)
258 (assume-type s1 <string>)
259 (assume-type s2 <string>)
260 (let ((str1 (opt-substring s1 start1 end1))
261 (str2 (opt-substring s2 start2 end2)))
262 (%string-compare-int start1 str1 str2
263 char-ci<? char-ci>?
264 proc< proc= proc>)))
265
266 (define (string= s1 s2 . args)
267 (assume-type s1 <string>)
268 (assume-type s2 <string>)
269 (apply string-compare
270 s1 s2 (^_ #f) (^_ #t) (^_ #f)
271 args))
272
273 (define (string<> s1 s2 . args)
274 (assume-type s1 <string>)
275 (assume-type s2 <string>)
276 (apply string-compare
277 s1 s2 (^_ #t) (^_ #f) (^_ #t)
278 args))
279
280 (define (string< s1 s2 . args)
281 (assume-type s1 <string>)
282 (assume-type s2 <string>)
283 (apply string-compare
284 s1 s2 (^_ #t) (^_ #f) (^_ #f)
285 args))
286
287 (define (string<= s1 s2 . args)
288 (assume-type s1 <string>)
289 (assume-type s2 <string>)
290 (apply string-compare
291 s1 s2 (^_ #t) (^_ #t) (^_ #f)
292 args))
293
294 (define (string> s1 s2 . args)
295 (assume-type s1 <string>)
296 (assume-type s2 <string>)
297 (apply string-compare
298 s1 s2 (^_ #f) (^_ #f) (^_ #t)
299 args))
300
301 (define (string>= s1 s2 . args)
302 (assume-type s1 <string>)
303 (assume-type s2 <string>)
304 (apply string-compare
305 s1 s2 (^_ #f) (^_ #t) (^_ #t)
306 args))
307
308 (define (string-ci= s1 s2 . args)
309 (assume-type s1 <string>)
310 (assume-type s2 <string>)
311 (apply string-compare-ci
312 s1 s2 (^_ #f) (^_ #t) (^_ #f)
313 args))
314
315 (define (string-ci<> s1 s2 . args)
316 (assume-type s1 <string>)
317 (assume-type s2 <string>)
318 (apply string-compare-ci
319 s1 s2 (^_ #t) (^_ #f) (^_ #t)
320 args))
321
322 (define (string-ci< s1 s2 . args)
323 (assume-type s1 <string>)
324 (assume-type s2 <string>)
325 (apply string-compare-ci
326 s1 s2 (^_ #t) (^_ #f) (^_ #f)
327 args))
328
329 (define (string-ci<= s1 s2 . args)
330 (assume-type s1 <string>)
331 (assume-type s2 <string>)
332 (apply string-compare-ci
333 s1 s2 (^_ #t) (^_ #t) (^_ #f)
334 args))
335
336 (define (string-ci> s1 s2 . args)
337 (assume-type s1 <string>)
338 (assume-type s2 <string>)
339 (apply string-compare-ci
340 s1 s2 (^_ #f) (^_ #f) (^_ #t)
341 args))
342
343 (define (string-ci>= s1 s2 . args)
344 (assume-type s1 <string>)
345 (assume-type s2 <string>)
346 (apply string-compare-ci
347 s1 s2 (^_ #f) (^_ #t) (^_ #t)
348 args))
349
350 ;;;
351 ;;; Hash functions
352 ;;;
353
354 (define (string-hash s :optional bound start end)
355 (assume-type s <string>)
356 (%hash-string (opt-substring s start end) bound))
357
358 (define (string-hash-ci s :optional bound start end)
359 (assume-type s <string>)
360 ;; oops! optimization required!
361 (%hash-string (string-upcase (opt-substring s start end)) bound))
362
363 ;;;
364 ;;; Prefix and suffix
365 ;;;
366
367 (define (%string-prefix-int str1 str2 =)
368 (let ((end1 (string-cursor-end str1))
369 (end2 (string-cursor-end str2)))
370 (let loop ((cur1 (string-cursor-start str1))
371 (cur2 (string-cursor-start str2))
372 (count 0))
373 (if (and (string-cursor<? cur1 end1)
374 (string-cursor<? cur2 end2)
375 (= (string-ref str1 cur1) (string-ref str2 cur2)))
376 (loop (string-cursor-next str1 cur1)
377 (string-cursor-next str2 cur2)
378 (+ count 1))
379 count))))
380
381 (define (string-prefix-length s1 s2 :optional start1 end1 start2 end2)
382 (assume-type s1 <string>)
383 (assume-type s2 <string>)
384 (let ((str1 (opt-substring s1 start1 end1))
385 (str2 (opt-substring s2 start2 end2)))
386 (%string-prefix-int str1 str2 char=?)))
387
388 (define (string-prefix-length-ci s1 s2 :optional start1 end1 start2 end2)
389 (assume-type s1 <string>)
390 (assume-type s2 <string>)
391 (let ((str1 (opt-substring s1 start1 end1))
392 (str2 (opt-substring s2 start2 end2)))
393 (%string-prefix-int str1 str2 char-ci=?)))
394
395 (define (string-prefix? s1 s2 :optional start1 end1 start2 end2)
396 (assume-type s1 <string>)
397 (assume-type s2 <string>)
398 (let ((str1 (opt-substring s1 start1 end1))
399 (str2 (opt-substring s2 start2 end2)))
400 (= (%string-prefix-int str1 str2 char=?)
401 (string-length str1))))
402
403 (define (string-prefix-ci? s1 s2 :optional start1 end1 start2 end2)
404 (assume-type s1 <string>)
405 (assume-type s2 <string>)
406 (let ((str1 (opt-substring s1 start1 end1))
407 (str2 (opt-substring s2 start2 end2)))
408 (= (%string-prefix-int str1 str2 char-ci=?)
409 (string-length str1))))
410
411 (define (%string-suffix-int str1 str2 =)
412 (let ((start1 (string-cursor-start str1))
413 (start2 (string-cursor-start str2)))
414 (let loop ((cur1 (string-cursor-end str1))
415 (cur2 (string-cursor-end str2))
416 (count 0))
417 (if (and (string-cursor>? cur1 start1)
418 (string-cursor>? cur2 start2))
419 (let ([new-cur1 (string-cursor-prev str1 cur1)]
420 [new-cur2 (string-cursor-prev str2 cur2)])
421 (if (= (string-ref str1 new-cur1)
422 (string-ref str2 new-cur2))
423 (loop new-cur1 new-cur2 (+ count 1))
424 count))
425 count))))
426
427 (define (string-suffix-length s1 s2 :optional start1 end1 start2 end2)
428 (assume-type s1 <string>)
429 (assume-type s2 <string>)
430 (let ((str1 (opt-substring s1 start1 end1))
431 (str2 (opt-substring s2 start2 end2)))
432 (%string-suffix-int str1 str2 char=?)))
433
434 (define (string-suffix-length-ci s1 s2 :optional start1 end1 start2 end2)
435 (assume-type s1 <string>)
436 (assume-type s2 <string>)
437 (let ((str1 (opt-substring s1 start1 end1))
438 (str2 (opt-substring s2 start2 end2)))
439 (%string-suffix-int str1 str2 char-ci=?)))
440
441 (define (string-suffix? s1 s2 :optional start1 end1 start2 end2)
442 (assume-type s1 <string>)
443 (assume-type s2 <string>)
444 (let ((str1 (opt-substring s1 start1 end1))
445 (str2 (opt-substring s2 start2 end2)))
446 (= (%string-suffix-int str1 str2 char=?)
447 (string-length str1))))
448
449 (define (string-suffix-ci? s1 s2 :optional start1 end1 start2 end2)
450 (assume-type s1 <string>)
451 (assume-type s2 <string>)
452 (let ((str1 (opt-substring s1 start1 end1))
453 (str2 (opt-substring s2 start2 end2)))
454 (= (%string-suffix-int str1 str2 char-ci=?)
455 (string-length str1))))
456
457 ;;;
458 ;;; Search
459 ;;;
460
461 ;; These % variants return two values, the result as cursor, and the
462 ;; cursor indicates 'not found'.
463 (define (%string-index s c/s/p
464 :optional
465 (start 0)
466 (end (string-cursor-end s)))
467 (assume-type s <string>)
468 (let ([pred (%get-char-pred c/s/p)]
469 [end (string-index->cursor s end)])
470 (let loop ([cur (string-index->cursor s start)])
471 (if (or (string-cursor=? cur end)
472 (pred c/s/p (string-ref s cur)))
473 (values cur end)
474 (loop (string-cursor-next s cur))))))
475
476 (define (%string-index-right s c/s/p
477 :optional
478 (start 0)
479 (end (string-cursor-end s)))
480 (assume-type s <string>)
481 (let ([pred (%get-char-pred c/s/p)]
482 [start (string-index->cursor s start)])
483 (let loop ([cur (string-index->cursor s end)])
484 (if (string-cursor>? cur start)
485 (let ([prev (string-cursor-prev s cur)])
486 (if (pred c/s/p (string-ref s prev))
487 (values cur start)
488 (loop prev)))
489 (values cur start)))))
490
491 (define (%string-skip s c/s/p
492 :optional
493 (start 0)
494 (end (string-cursor-end s)))
495 (assume-type s <string>)
496 (let ([pred (%get-char-pred c/s/p)]
497 [end (string-index->cursor s end)])
498 (let loop ([cur (string-index->cursor s start)])
499 (if (and (string-cursor<? cur end)
500 (pred c/s/p (string-ref s cur)))
501 (loop (string-cursor-next s cur))
502 (values cur end)))))
503
504 (define (%string-skip-right s c/s/p
505 :optional
506 (start 0)
507 (end (string-cursor-end s)))
508 (assume-type s <string>)
509 (let ([pred (%get-char-pred c/s/p)]
510 [start (string-index->cursor s start)])
511 (let loop ([cur (string-index->cursor s end)])
512 (if (string-cursor>? cur start)
513 (let ([prev (string-cursor-prev s cur)])
514 (if (pred c/s/p (string-ref s prev))
515 (loop prev)
516 (values cur start)))
517 (values cur start)))))
518
519 (define (string-index s c/s/p . args)
520 (receive (location limit) (apply %string-index s c/s/p args)
521 (if (string-cursor=? location limit)
522 #f
523 (string-cursor->index s location))))
524
525 (define (string-index-right s c/s/p . args)
526 (receive (location limit) (apply %string-index-right s c/s/p args)
527 (if (string-cursor=? location limit)
528 #f
529 (- (string-cursor->index s location) 1))))
530
531 (define (string-skip s c/s/p . args)
532 (receive (location limit) (apply %string-skip s c/s/p args)
533 (if (string-cursor=? location limit)
534 #f
535 (string-cursor->index s location))))
536
537 (define (string-skip-right s c/s/p . args)
538 (receive (location limit) (apply %string-skip-right s c/s/p args)
539 (if (string-cursor=? location limit)
540 #f
541 (- (string-cursor->index s location) 1))))
542
543 (define (string-count s c/s/p
544 :optional
545 (start 0)
546 (end (string-cursor-end s)))
547 (assume-type s <string>)
548 (let ([pred (%get-char-pred c/s/p)]
549 [end (string-index->cursor s end)])
550 (let loop ((cur (string-index->cursor s start))
551 (count 0))
552 (if (string-cursor=? cur end)
553 count
554 (loop (string-cursor-next s cur)
555 (if (pred c/s/p (string-ref s cur))
556 (+ count 1)
557 count))))))
558
559 (define (string-contains s1 s2 :optional (start1 0) end1 start2 end2)
560 (assume-type s1 <string>)
561 (assume-type s2 <string>)
562 (let* ([str1 (opt-substring s1 start1 end1)]
563 [str2 (opt-substring s2 start2 end2)]
564 [res (string-scan str1 str2)])
565 (and res (+ start1 res))))
566
567 ;; not tuned (maybe to be moved to native)
568 (define (string-contains-ci s1 s2 :optional (start1 0) end1 start2 end2)
569 (assume-type s1 <string>)
570 (assume-type s2 <string>)
571 (let* ([str1 (string-upcase (opt-substring s1 start1 end1))]
572 [str2 (string-upcase (opt-substring s2 start2 end2))]
573 [res (string-scan str1 str2)])
574 (and res (+ start1 res))))
575
576 ;;;
577 ;;; Case mapping
578 ;;;
579
580 (define (string-upcase s . args)
581 (let ((src (open-input-string (apply opt-substring s args)))
582 (dst (open-output-string)))
583 (let loop ((ch (read-char src)))
584 (if (eof-object? ch)
585 (get-output-string dst)
586 (begin (write-char (char-upcase ch) dst)
587 (loop (read-char src)))))))
588
589 (define (string-downcase s . args)
590 (let ((src (open-input-string (apply opt-substring s args)))
591 (dst (open-output-string)))
592 (let loop ((ch (read-char src)))
593 (if (eof-object? ch)
594 (get-output-string dst)
595 (begin (write-char (char-downcase ch) dst)
596 (loop (read-char src)))))))
597
598 (define *%cased-char-set* #[A-Za-z]) ;; fixme
599
600 (define (string-titlecase s . args)
601 (let ((src (open-input-string (apply opt-substring s args)))
602 (dst (open-output-string)))
603 (let loop ((title? #t)
604 (ch (read-char src)))
605 (cond ((eof-object? ch) (get-output-string dst))
606 ((char-set-contains? *%cased-char-set* ch)
607 (if title?
608 (write-char (char-upcase ch) dst) ;; This should be char-titlecase
609 (write-char (char-downcase ch) dst))
610 (loop #f (read-char src)))
611 (else
612 (write-char ch dst)
613 (loop #t (read-char src))))
614 )))
615
616 (define (%string-*case! converter)
617 (lambda (s :optional (start 0) (end (string-length s)))
618 (if (and (= (string-cursor->index s start) 0)
619 (= (string-cursor->index s end) (string-length s)))
620 (%string-replace-body! s (converter s))
621 (string-copy! s start (converter s start end)))))
622
623 (define string-upcase! (%string-*case! string-upcase))
624 (define string-downcase! (%string-*case! string-downcase))
625 (define string-titlecase! (%string-*case! string-titlecase))
626
627 ;;;
628 ;;; Reverse & append
629 ;;;
630
631 (define (string-reverse s :optional
632 (start 0)
633 (end (string-cursor-end s)))
634 (let ((start (string-index->cursor s start))
635 (dst (open-output-string)))
636 (let loop ((cur (string-index->cursor s end)))
637 (if (string-cursor=? cur start)
638 (get-output-string dst)
639 (let ([new-cur (string-cursor-prev s cur)])
640 (write-char (string-ref s new-cur) dst)
641 (loop new-cur))))))
642
643 (define (string-reverse! s . args)
644 (let ((rev (apply string-reverse s args)))
645 (string-copy! s (get-optional args 0) rev)))
646
647 (define (string-concatenate lis)
648 (cond
649 ((null? lis) "")
650 ((not (pair? lis))
651 (error "string-concatenate: argument ouf of domain:" lis))
652 ((and (null? (cdr lis)) (string? (car lis)))
653 (string-copy (car lis)))
654 (else
655 (let loop ((l lis)
656 (out (open-output-string :private? #t))
657 (incomplete? #f))
658 (if (pair? l)
659 (let ((e (car l)))
660 (unless (string? e)
661 (error "string-concatenate: argument contains non-string:" e))
662 (display e out)
663 (loop (cdr l) out (or incomplete? (string-incomplete? e))))
664 (if incomplete?
665 (string-complete->incomplete (get-output-string out))
666 (get-output-string out)))))))
667
668 (define string-concatenate/shared string-concatenate)
669
670 (define string-append/shared string-append)
671
672 (define (string-concatenate-reverse list . args)
673 (cond ((null? args)
674 (string-concatenate (reverse list)))
675 ((null? (cdr args))
676 (string-concatenate (reverse (cons (car args) list))))
677 (else
678 (string-concatenate (reverse (cons (string-take (car args)
679 (cadr args))
680 list))))))
681
682 (define string-concatenate-reverse/shared
683 string-concatenate-reverse)
684
685 ;;;
686 ;;; Mappers
687 ;;;
688
689 (define (string-map! proc s . args)
690 (assume-type s <string>)
691 (let ((mapped (apply string-map proc s args)))
692 (string-copy! s (get-optional args 0) mapped)))
693
694 (define (string-fold kons knil s
695 :optional
696 (start 0)
697 (end (string-cursor-end s)))
698 (assume-type s <string>)
699 (let ([end (string-index->cursor s end)])
700 (let loop ([cur (string-index->cursor s start)]
701 [r knil])
702 (if (string-cursor=? cur end)
703 r
704 (loop (string-cursor-next s cur)
705 (kons (string-ref s cur) r))))))
706
707 (define (string-fold-right kons knil s
708 :optional
709 (start 0)
710 (end (string-cursor-end s)))
711 (assume-type s <string>)
712 (let ([start (string-index->cursor s start)])
713 (let loop ([cur (string-index->cursor s end)]
714 [r knil])
715 (if (string-cursor=? cur start)
716 r
717 (let ([new-cur (string-cursor-prev s cur)])
718 (loop new-cur
719 (kons (string-ref s new-cur) r)))))))
720
721 (define (string-unfold p f g seed
722 :optional (base "") (make-final (^_ "")))
723 (let ((dest (open-output-string)))
724 (display base dest)
725 (let loop ((seed seed))
726 (if (p seed)
727 (begin (display (make-final seed) dest)
728 (get-output-string dest))
729 (begin (write-char (f seed) dest)
730 (loop (g seed)))))))
731
732 (define (string-unfold-right p f g seed
733 :optional (base "") (make-final (^_ "")))
734 (let ((dest (open-output-string)))
735 (let loop ((seed seed))
736 (if (p seed)
737 (string-append (make-final seed)
738 (string-reverse (get-output-string dest))
739 base)
740 (begin (write-char (f seed) dest)
741 (loop (g seed)))))))
742
743 (define (string-for-each-index proc s :optional (start 0) (end (string-length s)))
744 (assume-type s <string>)
745 (do ((i start (+ i 1)))
746 ((>= i end))
747 (proc i)))
748
749 ;;;
750 ;;; Rotator
751 ;;;
752
753 (define (xsubstring s from :optional to start end)
754 (assume-type s <string>)
755 (check-arg (^x (and (integer? x) (exact? x))) from)
756 (let* ([str (opt-substring s start end)]
757 [len (string-length str)]
758 [dest (open-output-string)])
759 ;; Fill TO if it's not provided; also check the validity.
760 (cond [(undefined? to) (set! to (+ from len))]
761 [(not (and (integer? to) (exact? to)))
762 (error "argument out of domain:" to)]
763 [(= len 0)
764 (error "zero length source string is not allowed")]
765 [(< to from)
766 (errorf "argument out of range (from, to): (~s, ~s)" from to)])
767 ;; Adjust the range
768 (let* ([from. (modulo from len)]
769 [to. (- to (- from from.))])
770 (let ([start-cur (string-cursor-start str)]
771 [end-cur (string-cursor-end str)])
772 (let loop ([count from.]
773 [cur (string-index->cursor str from.)])
774 (cond [(>= count to.)
775 (get-output-string dest)]
776 [(string-cursor=? cur end-cur)
777 ;; infinite loop if start-cur == end-cur, but that
778 ;; can't happen because we catch len == 0 earlier
779 (loop count start-cur)]
780 [else
781 (write-char (string-ref str cur) dest)
782 (loop (+ count 1) (string-cursor-next str cur))]))))))
783
784 (define (string-xcopy! target tstart s sfrom . args)
785 (assume-type target <string>)
786 (check-arg (^x (and (integer? x) (exact? x))) tstart)
787 (let1 result (apply xsubstring s sfrom args)
788 (string-copy! target tstart result)))
789
790 ;;;
791 ;;; Miscellaneous
792 ;;;
793
794 (define (string-replace s1 s2 start1 end1 . args)
795 (assume-type s1 <string>)
796 (assume-type s2 <string>)
797 (string-append (substring s1 0 start1)
798 (apply opt-substring s2 args)
799 (substring s1 end1 (string-length s1))))
800
801 (define (string-tokenize s :optional (token-set #[\S]) start end)
802 (assume-type s <string>)
803 (letrec ([src (open-input-string (opt-substring s start end))]
804 [in-word (^[ch dst r]
805 (cond [(eof-object? ch)
806 (reverse! (cons (get-output-string dst) r))]
807 [(char-set-contains? token-set ch)
808 (write-char ch dst)
809 (in-word (read-char src) dst r)]
810 [else
811 (out-word (read-char src)
812 (cons (get-output-string dst) r))]))]
813 [out-word (^[ch r]
814 (cond [(eof-object? ch) (reverse! r)]
815 [(char-set-contains? token-set ch)
816 (let ((dst (open-output-string)))
817 (write-char ch dst)
818 (in-word (read-char src) dst r))]
819 [else
820 (out-word (read-char src) r)]))])
821 (out-word (read-char src) '())))
822
823 ;;;
824 ;;; Filter
825 ;;;
826
827 ;; The argument order of string-filter and string-delete is changed
828 ;; by post-finalization amendment. In order to avoid breaking existing
829 ;; code, we accept old argument oder as well.
830
831 (define (string-filter c/s/p s . args)
832 (if (string? c/s/p)
833 (apply string-filter s c/s/p args) ;; for the backward compatibility
834 (let ([src (open-input-string (apply opt-substring s args))]
835 [dest (open-output-string)]
836 [pred (%get-char-pred c/s/p)])
837 (let loop ([ch (read-char src)])
838 (cond [(eof-object? ch) (get-output-string dest)]
839 [(pred c/s/p ch) (write-char ch dest) (loop (read-char src))]
840 [else (loop (read-char src))])))))
841
842 (define (string-delete c/s/p s . args)
843 (if (string? c/s/p)
844 (apply string-delete s c/s/p args) ;; for the backward compatibility
845 (let ([src (open-input-string (apply opt-substring s args))]
846 [dest (open-output-string)]
847 [pred (%get-char-pred c/s/p)])
848 (let loop ([ch (read-char src)])
849 (cond [(eof-object? ch) (get-output-string dest)]
850 [(pred c/s/p ch) (loop (read-char src))]
851 [else (write-char ch dest) (loop (read-char src))])))))
852
853 ;;; Low-level procedures. These are included for completeness, but
854 ;;; I'm not using these in other SRFI-13 routines, since it is more
855 ;;; efficient to let opt-substring handle argument checking as well.
856
857 (define (string-parse-start+end proc s args)
858 (assume-type s <string>)
859 (let ((slen (string-length s)))
860 (let-optionals* args (start end)
861 (if (undefined? start)
862 (values '() 0 slen)
863 (if (not (and (integer? start) (exact? start) (<= 0 start slen)))
864 (errorf "~s: argument out of range: ~s" proc start)
865 (if (undefined? end)
866 (values '() start slen)
867 (if (not (and (integer? end) (exact? end) (<= start end slen)))
868 (errorf "~s: argument out of range: ~s" proc end)
869 (values (cddr args) start end))
870 )
871 )
872 )
873 )))
874
875 (define (string-parse-final-start+end proc s args)
876 (assume-type s <string>)
877 (let ((slen (string-length s)))
878 (let-optionals* args (start end)
879 (if (undefined? start)
880 (values '() 0 slen)
881 (if (not (and (integer? start) (exact? start) (<= 0 start slen)))
882 (errorf "~s: argument out of range: ~s" proc start)
883 (if (undefined? end)
884 (values '() start slen)
885 (if (not (and (integer? end) (exact? end) (<= start end slen)))
886 (errorf "~s: argument out of range: ~s" proc end)
887 (if (not (null? (cddr args)))
888 (errorf "~s: too many arguments" proc)
889 (values (cddr args) start end)))
890 )
891 )
892 )
893 )))
894
895 (define-syntax let-string-start+end
896 (syntax-rules ()
897 ((_ (?start ?end ?rest) ?proc ?s ?args . ?body)
898 (call-with-values
899 (lambda () (string-parse-start+end ?proc ?s ?args))
900 (lambda (?rest ?start ?end) . ?body)))
901 ((_ (?start ?end) ?proc ?s ?args . ?body)
902 (call-with-values
903 (lambda () (string-parse-final-start+end ?proc ?s ?args))
904 (lambda (?start ?end) . ?body)))
905 ))
906
907 (define (check-substring-spec proc s start end)
908 (unless (substring-spec-ok? s start end)
909 (errorf "~s: invalid substring spec: ~s (~s, ~s)" proc s start end)))
910
911 (define (substring-spec-ok? s start end)
912 (and (string? s)
913 (integer? start) (exact? start)
914 (integer? end) (exact? end)
915 (<= 0 start end (string-length s))))
916
917 ;;;
918 ;;; Knuth-Morris-Pratt search
919 ;;;
920
921 ;; Knuth-Morris-Pratt search constructs.
922 ;;
923 ;; The SRFI-13 specification assumes accessing the pattern by index is
924 ;; a lightweight operation, but it may not be true in Gauche if the pattern
925 ;; contains multibyte characters. So the programs using these functions
926 ;; may not be very efficient, in spite of the efforts for efficiency put
927 ;; in the original SRFI design.
928 ;; TODO: see if cursors can be used instead of index.
929
930 (define (make-kmp-restart-vector s :optional (c= char=?) start end)
931 (let* ((pat (opt-substring s start end))
932 (rv (make-vector (string-length pat) -1))
933 (plen (string-length pat))
934 (plen-1 (- plen 1)))
935 (do ((i 0 (+ i 1)))
936 ((= i plen-1) rv)
937 (let loop ((k (+ (vector-ref rv i) 1)))
938 (if (and (> k 0)
939 (not (c= (string-ref pat i) (string-ref pat (- k 1)))))
940 (loop (+ (vector-ref rv (- k 1)) 1))
941 (vector-set! rv (+ i 1) k)))
942 )
943 ))
944
945 (define (kmp-step pat rv c i c= p-start)
946 (let loop ((i i))
947 (if (c= c (string-ref pat (+ i p-start)))
948 (+ i 1)
949 (let ((i (vector-ref rv i)))
950 (if (= i -1) 0 (loop i))))))
951
952 ;; This is inefficient if input string s contains multibyte characters.
953 (define (string-kmp-partial-search pat rv s i :optional
954 (c= char=?) (p-start 0) start end)
955 (let ((patlen (vector-length rv)))
956 (let lp ((si start)
957 (vi i))
958 (cond ((= vi patlen) (- si))
959 ((= si end) vi)
960 (else (lp (+ si 1)
961 (kmp-step pat rv (string-ref s si)
962 vi c= p-start)))))))