Debian Codegraph @

src/string.c

raw
1 /*
2 * string.c - string implementation
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 LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/configP.h"
37 #include "gauche/priv/stringP.h"
38 #include "gauche/priv/writerP.h"
39 #include "gauche/char_attr.h"
40
41 #include <string.h>
42 #include <ctype.h>
43
44 void Scm_DStringDump(FILE *out, ScmDString *dstr);
45 static ScmObj make_string_cursor(ScmString *src, const char *cursor);
46
47 static void string_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx);
48 SCM_DEFINE_BUILTIN_CLASS(Scm_StringClass, string_print, NULL, NULL, NULL,
49 SCM_CLASS_SEQUENCE_CPL);
50
51 #define CHECK_SIZE(siz) \
52 do { \
53 if ((siz) > SCM_STRING_MAX_SIZE) { \
54 Scm_Error("string size too big: %ld", (siz)); \
55 } \
56 } while (0)
57
58 /* Internal primitive constructor. LEN can be negative if the string
59 is incomplete. */
60 static ScmString *make_str(ScmSmallInt len, ScmSmallInt siz,
61 const char *p, u_long flags,
62 const void *index)
63 {
64 if (len < 0) flags |= SCM_STRING_INCOMPLETE;
65 if (flags & SCM_STRING_INCOMPLETE) len = siz;
66
67 if (siz > SCM_STRING_MAX_SIZE) {
68 Scm_Error("string size too big: %ld", siz);
69 }
70 if (len > siz) {
71 Scm_Error("string length (%ld) exceeds size (%ld)", len, siz);
72 }
73
74 ScmString *s = SCM_NEW(ScmString);
75 SCM_SET_CLASS(s, SCM_CLASS_STRING);
76 s->body = NULL;
77 s->initialBody.flags = flags & SCM_STRING_FLAG_MASK;
78 s->initialBody.length = len;
79 s->initialBody.size = siz;
80 s->initialBody.start = p;
81 s->initialBody.index = index;
82 return s;
83 }
84
85 #define DUMP_LENGTH 50
86
87 /* for debug */
88 void Scm_StringDump(FILE *out, ScmObj str)
89 {
90 const ScmStringBody *b = SCM_STRING_BODY(str);
91 ScmSmallInt s = SCM_STRING_BODY_SIZE(b);
92 const char *p = SCM_STRING_BODY_START(b);
93
94 fprintf(out, "STR(len=%ld,siz=%ld) \"", SCM_STRING_BODY_LENGTH(b), s);
95 for (int i=0; i < DUMP_LENGTH && s > 0;) {
96 int n = SCM_CHAR_NFOLLOWS(*p) + 1;
97 for (; n > 0 && s > 0; p++, n--, s--, i++) {
98 putc(*p, out);
99 }
100 }
101 if (s > 0) {
102 fputs("...\"\n", out);
103 } else {
104 fputs("\"\n", out);
105 }
106 }
107
108 /* Like GC_strndup, but we don't require the source string to be
109 NUL-terminated (instead, we trust the caller that the size
110 argument is in valid range.) */
111 char *Scm_StrdupPartial(const char *src, size_t size)
112 {
113 char *dst = SCM_NEW_ATOMIC_ARRAY(char, size+1);
114 memcpy(dst, src, size);
115 dst[size] = '\0';
116 return dst;
117 }
118
119 /*
120 * Multibyte length calculation
121 */
122
123 /* We have multiple similar functions, due to performance reasons. */
124
125 /* Calculate both length and size of C-string str.
126 If str is incomplete, *plen gets -1. */
127 static inline ScmSmallInt count_size_and_length(const char *str,
128 ScmSmallInt *psize, /* out */
129 ScmSmallInt *plen) /* out */
130 {
131 char c;
132 int incomplete = FALSE;
133 const char *p = str;
134 ScmSmallInt size = 0, len = 0;
135 while ((c = *p++) != 0) {
136 int i = SCM_CHAR_NFOLLOWS(c);
137 len++;
138 size += i+1;
139
140 ScmChar ch;
141 SCM_CHAR_GET(p-1, ch);
142 if (ch == SCM_CHAR_INVALID) incomplete = TRUE;
143 /* Check every octet to avoid skipping over terminating NUL. */
144 while (i-- > 0) {
145 if (!*p++) { incomplete = TRUE; goto eos; }
146 }
147 }
148 eos:
149 if (incomplete) len = -1;
150 *psize = size;
151 *plen = len;
152 return len;
153 }
154
155 /* Calculate length of known size string. str can contain NUL character. */
156 static inline ScmSmallInt count_length(const char *str, ScmSmallInt size)
157 {
158 ScmSmallInt count = 0;
159 while (size-- > 0) {
160 unsigned char c = (unsigned char)*str;
161 int i = SCM_CHAR_NFOLLOWS(c);
162 if (i < 0 || i > size) return -1;
163 ScmChar ch;
164 SCM_CHAR_GET(str, ch);
165 if (ch == SCM_CHAR_INVALID) return -1;
166 count++;
167 str += i+1;
168 size -= i;
169 }
170 return count;
171 }
172
173 /* Returns length of string, starts from str and end at stop.
174 If stop is NULL, str is regarded as C-string (NUL terminated).
175 If the string is incomplete, returns -1. */
176 ScmSmallInt Scm_MBLen(const char *str, const char *stop)
177 {
178 ScmSmallInt size = (stop == NULL)? (ScmSmallInt)strlen(str) : (stop - str);
179 ScmSmallInt len = count_length(str, size);
180 if (len > SCM_STRING_MAX_LENGTH) {
181 Scm_Error("Scm_MBLen: length too big: %ld", len);
182 }
183 return len;
184 }
185
186 /*----------------------------------------------------------------
187 * Cursors
188 */
189
190 static void cursor_print(ScmObj obj, ScmPort *port,
191 ScmWriteContext *mode SCM_UNUSED)
192 {
193 Scm_Printf(port, "#<string-cursor-large %ld>",
194 SCM_STRING_CURSOR_LARGE_OFFSET(obj));
195 }
196
197 static ScmClass *cursor_cpl[] = {
198 SCM_CLASS_STATIC_PTR(Scm_StringCursorClass),
199 SCM_CLASS_STATIC_PTR(Scm_TopClass),
200 NULL
201 };
202
203 SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_StringCursorClass, NULL);
204 SCM_DEFINE_BUILTIN_CLASS(Scm_StringCursorLargeClass, cursor_print, NULL, NULL,
205 NULL, cursor_cpl);
206
207 /* Common routine to get hold of the pointer from string cursor.
208 Returns NULL if SC isn't a string cursor.
209 Raise an error if sc is not in the range. */
210 static inline const char *string_cursor_ptr(const ScmStringBody *sb, ScmObj sc)
211 {
212 const char *ptr = NULL;
213 if (SCM_STRING_CURSOR_LARGE_P(sc)) {
214 if (SCM_STRING_BODY_START(sb) != SCM_STRING_CURSOR_LARGE_START(sc)) {
215 Scm_Error("invalid cursor (made for string '%s'): %S",
216 SCM_STRING_CURSOR_LARGE_START(sc), sc);
217 }
218 ptr = SCM_STRING_CURSOR_LARGE_POINTER(sb, sc);
219 } else if (SCM_STRING_CURSOR_SMALL_P(sc)) {
220 ptr = SCM_STRING_CURSOR_SMALL_POINTER(sb, sc);
221 } else {
222 return NULL;
223 }
224 if (ptr < SCM_STRING_BODY_START(sb) ||
225 ptr > SCM_STRING_BODY_END(sb)) {
226 Scm_Error("cursor out of range: %S", sc);
227 }
228 return ptr;
229 }
230
231 /* Returns -1 if sc isn't a cursor. No range check performed. */
232 static inline ScmSmallInt string_cursor_offset(ScmObj sc) {
233 if (SCM_STRING_CURSOR_LARGE_P(sc)) {
234 return SCM_STRING_CURSOR_LARGE_OFFSET(sc);
235 } else if (SCM_STRING_CURSOR_SMALL_P(sc)) {
236 return SCM_STRING_CURSOR_SMALL_OFFSET(sc);
237 } else {
238 return -1;
239 }
240 }
241
242 /*----------------------------------------------------------------
243 * Constructors
244 */
245
246 /* General constructor. */
247 ScmObj Scm_MakeString(const char *str, ScmSmallInt size, ScmSmallInt len,
248 u_long flags)
249 {
250 flags &= ~SCM_STRING_TERMINATED;
251
252 if (size < 0) {
253 count_size_and_length(str, &size, &len);
254 flags |= SCM_STRING_TERMINATED;
255 } else {
256 if (len < 0) len = count_length(str, size);
257 }
258 /* Range of size and len will be checked in make_str */
259
260 ScmString *s;
261 if (flags & SCM_STRING_COPYING) {
262 flags |= SCM_STRING_TERMINATED; /* SCM_STRDUP_PARTIAL terminates the result str */
263 s = make_str(len, size, SCM_STRDUP_PARTIAL(str, size), flags, NULL);
264 } else {
265 s = make_str(len, size, str, flags, NULL);
266 }
267 return SCM_OBJ(s);
268 }
269
270 ScmObj Scm_MakeFillString(ScmSmallInt len, ScmChar fill)
271 {
272 if (len < 0) Scm_Error("length out of range: %ld", len);
273 ScmSmallInt csize = SCM_CHAR_NBYTES(fill);
274 CHECK_SIZE(csize*len);
275 char *ptr = SCM_NEW_ATOMIC2(char *, csize*len+1);
276 char *p = ptr;
277 for (ScmSmallInt i=0; i<len; i++, p+=csize) {
278 SCM_CHAR_PUT(p, fill);
279 }
280 ptr[csize*len] = '\0';
281 return SCM_OBJ(make_str(len, csize*len, ptr, SCM_STRING_TERMINATED, NULL));
282 }
283
284 ScmObj Scm_ListToString(ScmObj chars)
285 {
286 ScmSmallInt size = 0, len = 0;
287
288 ScmObj cp;
289 SCM_FOR_EACH(cp, chars) {
290 if (!SCM_CHARP(SCM_CAR(cp)))
291 Scm_Error("character required, but got %S", SCM_CAR(cp));
292 ScmChar ch = SCM_CHAR_VALUE(SCM_CAR(cp));
293 size += SCM_CHAR_NBYTES(ch);
294 len++;
295 CHECK_SIZE(size);
296 }
297 char *buf = SCM_NEW_ATOMIC2(char *, size+1);
298 char *bufp = buf;
299 SCM_FOR_EACH(cp, chars) {
300 ScmChar ch = SCM_CHAR_VALUE(SCM_CAR(cp));
301 SCM_CHAR_PUT(bufp, ch);
302 bufp += SCM_CHAR_NBYTES(ch);
303 }
304 *bufp = '\0';
305 return Scm_MakeString(buf, size, len, 0);
306 }
307
308 /* Extract string as C-string. This one guarantees to return
309 mutable string (we always copy) */
310 char *Scm_GetString(ScmString *str)
311 {
312 const ScmStringBody *b = SCM_STRING_BODY(str);
313 return SCM_STRDUP_PARTIAL(SCM_STRING_BODY_START(b), SCM_STRING_BODY_SIZE(b));
314 }
315
316 /* Common routine for Scm_GetStringConst and Scm_GetStringContent */
317 static const char *get_string_from_body(const ScmStringBody *b)
318 {
319 ScmSmallInt size = SCM_STRING_BODY_SIZE(b);
320 if (SCM_STRING_BODY_HAS_FLAG(b, SCM_STRING_TERMINATED)) {
321 /* we can use string data as C-string */
322 return SCM_STRING_BODY_START(b);
323 } else {
324 char *p = SCM_STRDUP_PARTIAL(SCM_STRING_BODY_START(b), size);
325 /* kludge! This breaks 'const' qualification, but we know
326 this is an idempotent operation from the outside. Note that
327 this is safe even multiple threads execute this part
328 simultaneously. */
329 ((ScmStringBody*)b)->start = p; /* discard const qualifier */
330 ((ScmStringBody*)b)->flags |= SCM_STRING_TERMINATED;
331 return p;
332 }
333 }
334
335 /* Extract string as C-string. Returned string is immutable,
336 so we can directly return the body of the string. We do not
337 allow string containing NUL to be passed to C world, for it
338 would be a security risk.
339 TODO: Let the string body have a flag so that we don't need
340 to scan the string every time.
341 */
342 const char *Scm_GetStringConst(ScmString *str)
343 {
344 const ScmStringBody *b = SCM_STRING_BODY(str);
345 if (memchr(SCM_STRING_BODY_START(b), 0, SCM_STRING_BODY_SIZE(b))) {
346 Scm_Error("A string containing NUL character is not allowed: %S",
347 SCM_OBJ(str));
348 }
349 return get_string_from_body(b);
350 }
351
352 /* Atomically extracts C-string, length, size, and incomplete flag.
353 MT-safe. */
354 /* NB: Output parameters are int's for the ABI compatibility. */
355 const char *Scm_GetStringContent(ScmString *str,
356 ScmSmallInt *psize, /* out */
357 ScmSmallInt *plength, /* out */
358 u_long *pflags) /* out */
359 {
360 const ScmStringBody *b = SCM_STRING_BODY(str);
361 if (psize) *psize = SCM_STRING_BODY_SIZE(b);
362 if (plength) *plength = SCM_STRING_BODY_LENGTH(b);
363 if (pflags) *pflags = SCM_STRING_BODY_FLAGS(b);
364 return get_string_from_body(b);
365 }
366
367
368 /* Copy string. You can modify the flags of the newly created string
369 by FLAGS and MASK arguments; for the bits set in MASK, corresponding
370 bits in FLAGS are copied to the new string, and for other bits, the
371 original flags are copied.
372
373 The typical semantics of copy-string is achieved by passing 0 to
374 FLAGS and SCM_STRING_IMMUTABLE to MASK (i.e. reset IMMUTABLE flag,
375 and keep other flags intact.
376
377 NB: This routine doesn't check whether specified flag is valid
378 with the string content, i.e. you can drop INCOMPLETE flag with
379 copying, while the string content won't be checked if it consists
380 valid complete string. */
381 ScmObj Scm_CopyStringWithFlags(ScmString *x, u_long flags, u_long mask)
382 {
383 const ScmStringBody *b = SCM_STRING_BODY(x);
384 ScmSmallInt size = SCM_STRING_BODY_SIZE(b);
385 ScmSmallInt len = SCM_STRING_BODY_LENGTH(b);
386 const char *start = SCM_STRING_BODY_START(b);
387 const void *index = b->index;
388 u_long newflags = ((SCM_STRING_BODY_FLAGS(b) & ~mask)
389 | (flags & mask));
390
391 return SCM_OBJ(make_str(len, size, start, newflags, index));
392 }
393
394 /* OBSOLETED */
395 ScmObj Scm_StringCompleteToIncomplete(ScmString *x)
396 {
397 Scm_Warn("Obsoleted C API Scm_StringCompleteToIncomplete called");
398 ScmObj proc = SCM_UNDEFINED;
399 SCM_BIND_PROC(proc, "string-complete->incomplete", Scm_GaucheModule());
400 return Scm_ApplyRec1(proc, SCM_OBJ(x));
401 }
402
403 /* OBSOLETED */
404 ScmObj Scm_StringIncompleteToComplete(ScmString *x,
405 int handling,
406 ScmChar substitute)
407 {
408 Scm_Warn("Obsoleted C API Scm_StringIncompleteToComplete called");
409 ScmObj proc = SCM_UNDEFINED;
410 SCM_BIND_PROC(proc, "string-incomplete->complete", Scm_GaucheModule());
411 ScmObj r;
412 if (handling == SCM_ILLEGAL_CHAR_REJECT) {
413 r = Scm_ApplyRec1(proc, SCM_OBJ(x));
414 } else if (handling == SCM_ILLEGAL_CHAR_OMIT) {
415 r = Scm_ApplyRec2(proc, SCM_OBJ(x), SCM_MAKE_KEYWORD("omit"));
416 } else {
417 r = Scm_ApplyRec2(proc, SCM_OBJ(x), SCM_MAKE_CHAR(substitute));
418 }
419 return r;
420 }
421
422 /*----------------------------------------------------------------
423 * Comparison
424 */
425
426 /* TODO: merge Equal and Cmp API; required generic comparison protocol */
427 int Scm_StringEqual(ScmString *x, ScmString *y)
428 {
429 const ScmStringBody *xb = SCM_STRING_BODY(x);
430 const ScmStringBody *yb = SCM_STRING_BODY(y);
431 if ((SCM_STRING_BODY_FLAGS(xb)^SCM_STRING_BODY_FLAGS(yb))&SCM_STRING_INCOMPLETE) {
432 return FALSE;
433 }
434 if (SCM_STRING_BODY_SIZE(xb) != SCM_STRING_BODY_SIZE(yb)) {
435 return FALSE;
436 }
437 return (memcmp(SCM_STRING_BODY_START(xb),
438 SCM_STRING_BODY_START(yb),
439 SCM_STRING_BODY_SIZE(xb)) == 0? TRUE : FALSE);
440 }
441
442 int Scm_StringCmp(ScmString *x, ScmString *y)
443 {
444 const ScmStringBody *xb = SCM_STRING_BODY(x);
445 const ScmStringBody *yb = SCM_STRING_BODY(y);
446 ScmSmallInt sizx = SCM_STRING_BODY_SIZE(xb);
447 ScmSmallInt sizy = SCM_STRING_BODY_SIZE(yb);
448 ScmSmallInt siz = (sizx < sizy)? sizx : sizy;
449 int r = memcmp(SCM_STRING_BODY_START(xb), SCM_STRING_BODY_START(yb), siz);
450 if (r == 0) {
451 if (sizx == sizy) {
452 if (SCM_STRING_BODY_INCOMPLETE_P(xb)) {
453 if (SCM_STRING_BODY_INCOMPLETE_P(yb)) return 0;
454 else return 1;
455 } else {
456 if (SCM_STRING_BODY_INCOMPLETE_P(yb)) return -1;
457 else return 0;
458 }
459 }
460 if (sizx < sizy) return -1;
461 else return 1;
462 } else if (r < 0) {
463 return -1;
464 } else {
465 return 1;
466 }
467 }
468
469 /* single-byte case insensitive comparison */
470 static int sb_strcasecmp(const char *px, ScmSmallInt sizx,
471 const char *py, ScmSmallInt sizy)
472 {
473 for (; sizx > 0 && sizy > 0; sizx--, sizy--, px++, py++) {
474 char cx = tolower((u_char)*px);
475 char cy = tolower((u_char)*py);
476 if (cx == cy) continue;
477 return (cx - cy);
478 }
479 if (sizx > 0) return 1;
480 if (sizy > 0) return -1;
481 return 0;
482 }
483
484 /* multi-byte case insensitive comparison */
485 static int mb_strcasecmp(const char *px, ScmSmallInt lenx,
486 const char *py, ScmSmallInt leny)
487 {
488 int ix, iy;
489 for (; lenx > 0 && leny > 0; lenx--, leny--, px+=ix, py+=iy) {
490 int cx, cy;
491 SCM_CHAR_GET(px, cx);
492 SCM_CHAR_GET(py, cy);
493 int ccx = SCM_CHAR_UPCASE(cx);
494 int ccy = SCM_CHAR_UPCASE(cy);
495 if (ccx != ccy) return (ccx - ccy);
496 ix = SCM_CHAR_NBYTES(cx);
497 iy = SCM_CHAR_NBYTES(cy);
498 }
499 if (lenx > 0) return 1;
500 if (leny > 0) return -1;
501 return 0;
502 }
503
504 int Scm_StringCiCmp(ScmString *x, ScmString *y)
505 {
506 const ScmStringBody *xb = SCM_STRING_BODY(x);
507 const ScmStringBody *yb = SCM_STRING_BODY(y);
508
509 if ((SCM_STRING_BODY_FLAGS(xb)^SCM_STRING_BODY_FLAGS(yb))&SCM_STRING_INCOMPLETE) {
510 Scm_Error("cannot compare incomplete strings in case-insensitive way: %S, %S",
511 SCM_OBJ(x), SCM_OBJ(y));
512 }
513 ScmSmallInt sizx = SCM_STRING_BODY_SIZE(xb);
514 ScmSmallInt lenx = SCM_STRING_BODY_LENGTH(xb);
515 ScmSmallInt sizy = SCM_STRING_BODY_SIZE(yb);
516 ScmSmallInt leny = SCM_STRING_BODY_LENGTH(yb);
517 const char *px = SCM_STRING_BODY_START(xb);
518 const char *py = SCM_STRING_BODY_START(yb);
519
520 if (sizx == lenx && sizy == leny) {
521 return sb_strcasecmp(px, sizx, py, sizy);
522 } else {
523 return mb_strcasecmp(px, lenx, py, leny);
524 }
525 }
526
527 /*----------------------------------------------------------------
528 * Reference
529 */
530
531 /* Advance ptr for NCHARS characters. Args assumed in boundary. */
532 static inline const char *forward_pos(const ScmStringBody *body,
533 const char *current,
534 ScmSmallInt nchars)
535 {
536 if (body && (SCM_STRING_BODY_SINGLE_BYTE_P(body) ||
537 SCM_STRING_BODY_INCOMPLETE_P(body))) {
538 return current + nchars;
539 }
540
541 while (nchars--) {
542 int n = SCM_CHAR_NFOLLOWS(*current);
543 current += n + 1;
544 }
545 return current;
546 }
547
548 /* Index -> ptr. Args assumed in boundary. */
549 static const char *index2ptr(const ScmStringBody *body,
550 ScmSmallInt nchars)
551 {
552 if (body->index == NULL) {
553 return forward_pos(body, SCM_STRING_BODY_START(body), nchars);
554 }
555 ScmStringIndex *index = STRING_INDEX(body->index);
556 ScmSmallInt off = 0;
557 ScmSmallInt array_off = (nchars>>STRING_INDEX_SHIFT(index))+1;
558 /* If array_off is 1, we don't need lookup - the character is in the
559 first segment. */
560 if (array_off > 1) {
561 switch (STRING_INDEX_TYPE(index)) {
562 case STRING_INDEX8:
563 SCM_ASSERT(array_off < (ScmSmallInt)index->index8[1]);
564 off = index->index8[array_off];
565 break;
566 case STRING_INDEX16:
567 SCM_ASSERT(array_off < (ScmSmallInt)index->index16[1]);
568 off = index->index16[array_off];
569 break;
570 case STRING_INDEX32:
571 SCM_ASSERT(array_off < (ScmSmallInt)index->index32[1]);
572 off = index->index32[array_off];
573 break;
574 case STRING_INDEX64:
575 SCM_ASSERT(array_off < (ScmSmallInt)index->index64[1]);
576 off = index->index64[array_off];
577 break;
578 default:
579 Scm_Panic("String index contains unrecognized signature (%02x). "
580 "Possible memory corruption. Aborting...",
581 index->signature);
582 }
583 }
584 return forward_pos(body,
585 SCM_STRING_BODY_START(body) + off,
586 nchars & (STRING_INDEX_INTERVAL(index)-1));
587 }
588
589
590 /* string-ref.
591 * If POS is out of range,
592 * - returns SCM_CHAR_INVALID if range_error is FALSE
593 * - raise error otherwise.
594 * This differs from Scheme version, which takes an optional 'fallback'
595 * argument which will be returned when POS is out-of-range. We can't
596 * have the same semantics since the return type is limited.
597 */
598 ScmChar Scm_StringRef(ScmString *str, ScmSmallInt pos, int range_error)
599 {
600 const ScmStringBody *b = SCM_STRING_BODY(str);
601 ScmSmallInt len = SCM_STRING_BODY_LENGTH(b);
602
603 /* we can't allow string-ref on incomplete strings, since it may yield
604 invalid character object. */
605 if (SCM_STRING_BODY_INCOMPLETE_P(b)) {
606 Scm_Error("incomplete string not allowed : %S", str);
607 }
608 if (pos < 0 || pos >= len) {
609 if (range_error) {
610 Scm_Error("argument out of range: %ld", pos);
611 } else {
612 return SCM_CHAR_INVALID;
613 }
614 }
615
616 const char *p = NULL;
617 if (SCM_STRING_BODY_SINGLE_BYTE_P(b)) {
618 p = SCM_STRING_BODY_START(b) + pos;
619 } else {
620 p = index2ptr(b, pos);
621 }
622
623 if (SCM_STRING_BODY_SINGLE_BYTE_P(b)) {
624 return (ScmChar)(*(unsigned char *)p);
625 } else {
626 ScmChar c;
627 SCM_CHAR_GET(p, c);
628 return c;
629 }
630 }
631
632 /* The meaning and rationale of range_error is the same as Scm_StringRef.
633 * Returns -1 if OFFSET is out-of-range and RANGE_ERROR is FALSE.
634 * (Because of this, the return type is not ScmByte but int.
635 */
636 int Scm_StringByteRef(ScmString *str, ScmSmallInt offset, int range_error)
637 {
638 const ScmStringBody *b = SCM_STRING_BODY(str);
639 if (offset < 0 || offset >= SCM_STRING_BODY_SIZE(b)) {
640 if (range_error) {
641 Scm_Error("argument out of range: %ld", offset);
642 } else {
643 return -1;
644 }
645 }
646 return (ScmByte)SCM_STRING_BODY_START(b)[offset];
647 }
648
649 /* External interface of index2ptr. Returns the pointer to the
650 offset-th character in str. */
651 /* NB: this function allows offset == length of the string; in that
652 case, the return value points the location past the string body,
653 but it is necessary sometimes to do a pointer arithmetic with the
654 returned values. */
655 const char *Scm_StringBodyPosition(const ScmStringBody *b, ScmSmallInt offset)
656 {
657 if (offset < 0 || offset > SCM_STRING_BODY_LENGTH(b)) {
658 Scm_Error("argument out of range: %ld", offset);
659 }
660 return index2ptr(b, offset);
661 }
662
663 /* This is old API and now DEPRECATED. It's difficult to use this safely,
664 since you don't have a way to get the string length consistent at the
665 moment you call this function. Use Scm_StringBodyPosition instead. */
666 const char *Scm_StringPosition(ScmString *str, ScmSmallInt offset)
667 {
668 return Scm_StringBodyPosition(SCM_STRING_BODY(str), offset);
669 }
670
671 /*----------------------------------------------------------------
672 * Concatenation
673 */
674
675 ScmObj Scm_StringAppend2(ScmString *x, ScmString *y)
676 {
677 const ScmStringBody *xb = SCM_STRING_BODY(x);
678 const ScmStringBody *yb = SCM_STRING_BODY(y);
679 ScmSmallInt sizex = SCM_STRING_BODY_SIZE(xb);
680 ScmSmallInt lenx = SCM_STRING_BODY_LENGTH(xb);
681 ScmSmallInt sizey = SCM_STRING_BODY_SIZE(yb);
682 ScmSmallInt leny = SCM_STRING_BODY_LENGTH(yb);
683 CHECK_SIZE(sizex+sizey);
684 u_long flags = 0;
685 char *p = SCM_NEW_ATOMIC2(char *,sizex + sizey + 1);
686
687 memcpy(p, xb->start, sizex);
688 memcpy(p+sizex, yb->start, sizey);
689 p[sizex + sizey] = '\0';
690 flags |= SCM_STRING_TERMINATED;
691
692 if (SCM_STRING_BODY_INCOMPLETE_P(xb) || SCM_STRING_BODY_INCOMPLETE_P(yb)) {
693 flags |= SCM_STRING_INCOMPLETE; /* yields incomplete string */
694 }
695 return SCM_OBJ(make_str(lenx+leny, sizex+sizey, p, flags, NULL));
696 }
697
698 ScmObj Scm_StringAppendC(ScmString *x, const char *str,
699 ScmSmallInt sizey, ScmSmallInt leny)
700 {
701 const ScmStringBody *xb = SCM_STRING_BODY(x);
702 ScmSmallInt sizex = SCM_STRING_BODY_SIZE(xb);
703 ScmSmallInt lenx = SCM_STRING_BODY_LENGTH(xb);
704 u_long flags = 0;
705
706 if (sizey < 0) count_size_and_length(str, &sizey, &leny);
707 else if (leny < 0) leny = count_length(str, sizey);
708 CHECK_SIZE(sizex+sizey);
709
710 char *p = SCM_NEW_ATOMIC2(char *, sizex + sizey + 1);
711 memcpy(p, xb->start, sizex);
712 memcpy(p+sizex, str, sizey);
713 p[sizex+sizey] = '\0';
714 flags |= SCM_STRING_TERMINATED;
715
716 if (SCM_STRING_BODY_INCOMPLETE_P(xb) || leny < 0) {
717 flags |= SCM_STRING_INCOMPLETE;
718 }
719 return SCM_OBJ(make_str(lenx + leny, sizex + sizey, p, flags, NULL));
720 }
721
722 ScmObj Scm_StringAppend(ScmObj strs)
723 {
724 #define BODY_ARRAY_SIZE 32
725 ScmSmallInt size = 0, len = 0;
726 u_long flags = 0;
727 const ScmStringBody *bodies_s[BODY_ARRAY_SIZE], **bodies;
728
729 /* It is trickier than it appears, since the strings may be modified
730 by another thread during we're dealing with it. So in the first
731 pass to sum up the lengths of strings, we extract the string bodies
732 and save it. */
733 ScmSmallInt numstrs = Scm_Length(strs);
734 if (numstrs < 0) Scm_Error("improper list not allowed: %S", strs);
735 if (numstrs > BODY_ARRAY_SIZE) {
736 bodies = SCM_NEW_ARRAY(const ScmStringBody*, numstrs);
737 } else {
738 bodies = bodies_s;
739 }
740
741 ScmSmallInt i = 0;
742 ScmObj cp;
743 SCM_FOR_EACH(cp, strs) {
744 const ScmStringBody *b;
745 if (!SCM_STRINGP(SCM_CAR(cp))) {
746 Scm_Error("string required, but got %S", SCM_CAR(cp));
747 }
748 b = SCM_STRING_BODY(SCM_CAR(cp));
749 size += SCM_STRING_BODY_SIZE(b);
750 len += SCM_STRING_BODY_LENGTH(b);
751 CHECK_SIZE(size);
752 if (SCM_STRING_BODY_INCOMPLETE_P(b)) {
753 flags |= SCM_STRING_INCOMPLETE;
754 }
755 bodies[i++] = b;
756 }
757
758 char *buf = SCM_NEW_ATOMIC2(char *, size+1);
759 char *bufp = buf;
760 for (i=0; i<numstrs; i++) {
761 const ScmStringBody *b = bodies[i];
762 memcpy(bufp, SCM_STRING_BODY_START(b), SCM_STRING_BODY_SIZE(b));
763 bufp += SCM_STRING_BODY_SIZE(b);
764 }
765 *bufp = '\0';
766 bodies = NULL; /* to help GC */
767 flags |= SCM_STRING_TERMINATED;
768 return SCM_OBJ(make_str(len, size, buf, flags, NULL));
769 #undef BODY_ARRAY_SIZE
770 }
771
772 ScmObj Scm_StringJoin(ScmObj strs, ScmString *delim, int grammar)
773 {
774 #define BODY_ARRAY_SIZE 32
775 ScmSmallInt size = 0, len = 0;
776 u_long flags = 0;
777 const ScmStringBody *bodies_s[BODY_ARRAY_SIZE], **bodies;
778
779 ScmSmallInt nstrs = Scm_Length(strs);
780 if (nstrs < 0) Scm_Error("improper list not allowed: %S", strs);
781 if (nstrs == 0) {
782 if (grammar == SCM_STRING_JOIN_STRICT_INFIX) {
783 Scm_Error("can't join empty list of strings with strict-infix grammar");
784 }
785 return SCM_MAKE_STR("");
786 }
787
788 if (nstrs > BODY_ARRAY_SIZE) {
789 bodies = SCM_NEW_ARRAY(const ScmStringBody *, nstrs);
790 } else {
791 bodies = bodies_s;
792 }
793
794 const ScmStringBody *dbody = SCM_STRING_BODY(delim);
795 ScmSmallInt dsize = SCM_STRING_BODY_SIZE(dbody);
796 ScmSmallInt dlen = SCM_STRING_BODY_LENGTH(dbody);
797 if (SCM_STRING_BODY_INCOMPLETE_P(dbody)) {
798 flags |= SCM_STRING_INCOMPLETE;
799 }
800
801 ScmSmallInt i = 0, ndelim;
802 ScmObj cp;
803 SCM_FOR_EACH(cp, strs) {
804 const ScmStringBody *b;
805 if (!SCM_STRINGP(SCM_CAR(cp))) {
806 Scm_Error("string required, but got %S", SCM_CAR(cp));
807 }
808 b = SCM_STRING_BODY(SCM_CAR(cp));
809 size += SCM_STRING_BODY_SIZE(b);
810 len += SCM_STRING_BODY_LENGTH(b);
811 CHECK_SIZE(size);
812 if (SCM_STRING_BODY_INCOMPLETE_P(b)) {
813 flags |= SCM_STRING_INCOMPLETE;
814 }
815 bodies[i++] = b;
816 }
817 if (grammar == SCM_STRING_JOIN_INFIX
818 || grammar == SCM_STRING_JOIN_STRICT_INFIX) {
819 ndelim = nstrs - 1;
820 } else {
821 ndelim = nstrs;
822 }
823 size += dsize * ndelim;
824 len += dlen * ndelim;
825 CHECK_SIZE(size);
826
827 char *buf = SCM_NEW_ATOMIC2(char *, size+1);
828 char *bufp = buf;
829 if (grammar == SCM_STRING_JOIN_PREFIX) {
830 memcpy(bufp, SCM_STRING_BODY_START(dbody), dsize);
831 bufp += dsize;
832 }
833 for (i=0; i<nstrs; i++) {
834 const ScmStringBody *b = bodies[i];
835 memcpy(bufp, SCM_STRING_BODY_START(b), SCM_STRING_BODY_SIZE(b));
836 bufp += SCM_STRING_BODY_SIZE(b);
837 if (i < nstrs-1) {
838 memcpy(bufp, SCM_STRING_BODY_START(dbody), dsize);
839 bufp += dsize;
840 }
841 }
842 if (grammar == SCM_STRING_JOIN_SUFFIX) {
843 memcpy(bufp, SCM_STRING_BODY_START(dbody), dsize);
844 bufp += dsize;
845 }
846 *bufp = '\0';
847 bodies = NULL; /* to help GC */
848 flags |= SCM_STRING_TERMINATED;
849 return SCM_OBJ(make_str(len, size, buf, flags, NULL));
850 #undef BODY_ARRAY_SIZE
851 }
852
853 /*----------------------------------------------------------------
854 * Mutation
855 */
856
857 /*
858 * String mutation is extremely heavy operation in Gauche,
859 * and only provided for compatibility to RnRS. At C API level
860 * there's no point in using string mutation at all. A single
861 * API, which replaces the string body, is provided at C level.
862 */
863
864 ScmObj Scm_StringReplaceBody(ScmString *str, const ScmStringBody *newbody)
865 {
866 if (SCM_STRING_IMMUTABLE_P(str)) {
867 Scm_Error("attempted to modify an immutable string: %S", str);
868 }
869
870 /* Atomically replaces the str's body (no MT hazard) */
871 str->body = newbody;
872
873 /* TODO: If the initialBody of str isn't shared,
874 nullify str->initialBody.start so that the original string is
875 GCed. It should be done after implementing 'shared' flag
876 into the string body. */
877 return SCM_OBJ(str);
878 }
879
880 /*----------------------------------------------------------------
881 * Substring
882 */
883
884 static ScmObj substring(const ScmStringBody *xb,
885 ScmSmallInt start, ScmSmallInt end,
886 int byterange, int immutable)
887 {
888 ScmSmallInt len = byterange? SCM_STRING_BODY_SIZE(xb) : SCM_STRING_BODY_LENGTH(xb);
889 u_long flags = SCM_STRING_BODY_FLAGS(xb);
890 if (!immutable) flags &= ~SCM_STRING_IMMUTABLE;
891
892 SCM_CHECK_START_END(start, end, len);
893
894 if (byterange) {
895 if (end != len) flags &= ~SCM_STRING_TERMINATED;
896 flags |= SCM_STRING_INCOMPLETE;
897 return SCM_OBJ(make_str(end - start,
898 end - start,
899 SCM_STRING_BODY_START(xb) + start,
900 flags, NULL));
901 } else {
902 const char *s, *e;
903 s = index2ptr(xb, start);
904 if (len == end) {
905 e = SCM_STRING_BODY_END(xb);
906 } else {
907 /* kludge - if we don't have index, forward_pos is faster. */
908 if (start > 0 && xb->index == NULL) {
909 e = forward_pos(xb, s, end - start);
910 } else {
911 e = index2ptr(xb, end);
912 }
913 flags &= ~SCM_STRING_TERMINATED;
914 }
915 return SCM_OBJ(make_str(end - start,
916 (ScmSmallInt)(e - s), s, flags, NULL));
917 }
918 }
919
920 static ScmObj substring_cursor(const ScmStringBody *xb,
921 const char *start,
922 const char *end,
923 int immutable)
924 {
925 u_long flags = SCM_STRING_BODY_FLAGS(xb);
926 if (!immutable) flags &= ~SCM_STRING_IMMUTABLE;
927
928 if (start < SCM_STRING_BODY_START(xb) ||
929 start > SCM_STRING_BODY_END(xb)) {
930 Scm_Error("start argument out of range: %S", start);
931 }
932 else if (end > SCM_STRING_BODY_END(xb)) {
933 Scm_Error("end argument out of range: %S", end);
934 } else if (end < start) {
935 Scm_Error("end argument must be greater than or "
936 "equal to the start argument: %S vs %S", end, start);
937 }
938
939 if (end != SCM_STRING_BODY_END(xb)) {
940 flags &= ~SCM_STRING_TERMINATED;
941 }
942
943 ScmSmallInt len;
944 if (SCM_STRING_BODY_SINGLE_BYTE_P(xb)) {
945 len = (ScmSmallInt)(end - start);
946 } else {
947 len = Scm_MBLen(start, end);
948 }
949
950 return SCM_OBJ(make_str(len,
951 (ScmSmallInt)(end - start),
952 start, flags, NULL));
953 }
954
955 ScmObj Scm_Substring(ScmString *x, ScmSmallInt start, ScmSmallInt end,
956 int byterangep)
957 {
958 return substring(SCM_STRING_BODY(x), start, end, byterangep, FALSE);
959 }
960
961 /* Auxiliary procedure to support optional start/end parameter specified
962 in lots of SRFI-13 functions. If start and end is specified and restricts
963 string range, call substring. Otherwise returns x itself.
964 If input string is immutable, the result is also immutable. If the caller
965 needs a mutable string it should call CopyString anyway, for the caller
966 doesn't know if the input string is just passed through.
967 */
968 ScmObj Scm_MaybeSubstring(ScmString *x, ScmObj start, ScmObj end)
969 {
970 const ScmStringBody *xb = SCM_STRING_BODY(x);
971 int no_start = SCM_UNBOUNDP(start) || SCM_UNDEFINEDP(start) || SCM_FALSEP(start);
972 int no_end = SCM_UNBOUNDP(end) || SCM_UNDEFINEDP(end) || SCM_FALSEP(end);
973 ScmSmallInt istart = -1, iend = -1, ostart = -1, oend = -1;
974
975 int immutable = SCM_STRING_BODY_HAS_FLAG(xb, SCM_STRING_IMMUTABLE);
976
977 if (no_start)
978 istart = 0;
979 else if (SCM_STRING_CURSOR_P(start))
980 ostart = string_cursor_offset(start);
981 else if (SCM_INTP(start))
982 istart = SCM_INT_VALUE(start);
983 else
984 Scm_Error("exact integer or cursor required for start, but got %S", start);
985
986 if (no_end) {
987 if (istart == 0 || ostart == 0) {
988 return SCM_OBJ(x);
989 }
990 iend = SCM_STRING_BODY_LENGTH(xb);
991 } else if (SCM_STRING_CURSOR_P(end))
992 oend = string_cursor_offset(end);
993 else if (SCM_INTP(end))
994 iend = SCM_INT_VALUE(end);
995 else
996 Scm_Error("exact integer or cursor required for end, but got %S", end);
997
998 if (no_start && oend != -1) {
999 return substring_cursor(xb,
1000 SCM_STRING_BODY_START(xb),
1001 SCM_STRING_BODY_START(xb) + oend,
1002 immutable);
1003 }
1004 if (ostart != -1 && oend != -1) {
1005 return substring_cursor(xb,
1006 SCM_STRING_BODY_START(xb) + ostart,
1007 SCM_STRING_BODY_START(xb) + oend,
1008 immutable);
1009 }
1010 if (ostart != -1 && no_end) {
1011 return substring_cursor(xb,
1012 SCM_STRING_BODY_START(xb) + ostart,
1013 SCM_STRING_BODY_END(xb),
1014 immutable);
1015 }
1016
1017 if (ostart != -1) {
1018 istart = Scm_GetInteger(Scm_StringCursorIndex(x, start));
1019 }
1020 if (oend != -1) {
1021 iend = Scm_GetInteger(Scm_StringCursorIndex(x, end));
1022 }
1023
1024 return substring(xb, istart, iend, FALSE, immutable);
1025 }
1026
1027 /*----------------------------------------------------------------
1028 * Search & parse
1029 */
1030
1031 /* Boyer-Moore string search. assuming siz1 > siz2, siz2 < 256. */
1032 static ScmSmallInt boyer_moore(const char *ss1, ScmSmallInt siz1,
1033 const char *ss2, ScmSmallInt siz2)
1034 {
1035 unsigned char shift[256];
1036 for (ScmSmallInt i=0; i<256; i++) { shift[i] = siz2; }
1037 for (ScmSmallInt j=0; j<siz2-1; j++) {
1038 shift[(unsigned char)ss2[j]] = siz2-j-1;
1039 }
1040 for (ScmSmallInt i=siz2-1; i<siz1; i+=shift[(unsigned char)ss1[i]]) {
1041 ScmSmallInt j, k;
1042 for (j=siz2-1, k = i; j>=0 && ss1[k] == ss2[j]; j--, k--)
1043 ;
1044 if (j == -1) return k+1;
1045 }
1046 return -1;
1047 }
1048
1049 static ScmSmallInt boyer_moore_reverse(const char *ss1, ScmSmallInt siz1,
1050 const char *ss2, ScmSmallInt siz2)
1051 {
1052 unsigned char shift[256];
1053 for (ScmSmallInt i=0; i<256; i++) { shift[i] = siz2; }
1054 for (ScmSmallInt j=siz2-1; j>0; j--) {
1055 shift[(unsigned char)ss2[j]] = j;
1056 }
1057 for (ScmSmallInt i=siz1-siz2+1; i>=0; i-=shift[(unsigned char)ss1[i]]) {
1058 ScmSmallInt j, k;
1059 for (j=0, k = i; j<siz2 && ss1[k] == ss2[j]; j++, k++)
1060 ;
1061 if (j == siz2) return i;
1062 }
1063 return -1;
1064 }
1065
1066 /* Primitive routines to search a substring s2 within s1.
1067 Returns NOT_FOUND if not found, FOUND_BOTH_INDEX if both byte index
1068 (*bi) and character index (*ci) is calculted, FOUND_BYTE_INDEX
1069 if only byte index is calculated.
1070
1071 With utf-8, we can scan a string as if it si just a bytestring. However,
1072 we need to calculate character index after we find the match. It is still
1073 a total win, for finding out non-matches using Boyer-Moore is a lot
1074 faster than naive way.
1075 */
1076
1077 /* return value of string_scan */
1078 #define NOT_FOUND 0 /* string not found */
1079 #define FOUND_BOTH_INDEX 1 /* string found, and both indexes are calculated */
1080 #define FOUND_BYTE_INDEX 2 /* string found, and only byte index is calc'd */
1081
1082 /* glibc has memrchr, but we need to provide fallback anyway and
1083 we don't need it to be highly tuned, so we just roll our own. */
1084 static const void *my_memrchr(const void *s, int c, size_t n)
1085 {
1086 const char *p = (const char*)s + n - 1;
1087 for (;p >= (const char*)s; p--) {
1088 if ((int)*p == c) return p;
1089 }
1090 return NULL;
1091 }
1092
1093 /* NB: len1 and len2 only used in certain internal CES. */
1094 static int string_search(const char *s1, ScmSmallInt siz1,
1095 ScmSmallInt len1 SCM_UNUSED,
1096 const char *s2, ScmSmallInt siz2,
1097 ScmSmallInt len2 SCM_UNUSED,
1098 ScmSmallInt *bi /* out */,
1099 ScmSmallInt *ci /* out */)
1100 {
1101 if (siz2 == 0) {
1102 *bi = *ci = 0;
1103 return FOUND_BOTH_INDEX;
1104 }
1105
1106 if (siz2 == 1) {
1107 /* Single ASCII character search case. This is a huge win. */
1108 const char *z = memchr(s1, s2[0], siz1);
1109 if (z) { *bi = *ci = z - s1; return FOUND_BYTE_INDEX; }
1110 else return NOT_FOUND;
1111 } else {
1112 ScmSmallInt i;
1113 /* Shortcut for single-byte strings */
1114 if (siz1 < siz2) return NOT_FOUND;
1115 if (siz1 < 256 || siz2 >= 256) {
1116 /* brute-force search */
1117 for (i=0; i<=siz1-siz2; i++) {
1118 if (memcmp(s2, s1+i, siz2) == 0) break;
1119 }
1120 if (i == siz1-siz2+1) return NOT_FOUND;
1121 } else {
1122 i = boyer_moore(s1, siz1, s2, siz2);
1123 if (i < 0) return NOT_FOUND;
1124 }
1125 *bi = *ci = i;
1126 return FOUND_BYTE_INDEX;
1127 }
1128 }
1129
1130 /* NB: len2 is only used in some internal CES */
1131 static int string_search_reverse(const char *s1, ScmSmallInt siz1,
1132 ScmSmallInt len1,
1133 const char *s2, ScmSmallInt siz2,
1134 ScmSmallInt len2 SCM_UNUSED,
1135 ScmSmallInt *bi /* out */,
1136 ScmSmallInt *ci /* out */)
1137 {
1138 if (siz2 == 0) {
1139 *bi = siz1;
1140 *ci = len1;
1141 return FOUND_BOTH_INDEX;
1142 }
1143
1144 if (siz2 == 1) {
1145 /* Single ASCII character search case. This is a huge win. */
1146 const char *z = my_memrchr(s1, s2[0], siz1);
1147 if (z) { *bi = *ci = z - s1; return FOUND_BYTE_INDEX; }
1148 else return NOT_FOUND;
1149 } else {
1150 ScmSmallInt i;
1151 /* short cut for single-byte strings */
1152 if (siz1 < siz2) return NOT_FOUND;
1153 if (siz1 < 256 || siz2 >= 256) {
1154 /* brute-force search */
1155 for (i=siz1-siz2; i>=0; i--) {
1156 if (memcmp(s2, s1+i, siz2) == 0) break;
1157 }
1158 if (i < 0) return NOT_FOUND;
1159 } else {
1160 i = boyer_moore_reverse(s1, siz1, s2, siz2);
1161 if (i < 0) return NOT_FOUND;
1162 }
1163 *bi = *ci = i;
1164 return FOUND_BYTE_INDEX;
1165 }
1166 }
1167
1168 /* Scan s2 in s1, and calculates appropriate return value(s) according to
1169 retmode. Returns # of values, 1 or 2.
1170
1171 SCM_STRING_SCAN_INDEX : v1 <- the index of s1
1172 s1 = "abcde" and s2 = "cd" => 2
1173 SCM_STRING_SCAN_CURSOR : v1 <- the cursor of s1
1174 s1 = "abcde" and s2 = "cd" => #<string-cursor 2>
1175 SCM_STRING_SCAN_BEFORE : v1 <- substring of s1 before s2
1176 s1 = "abcde" and s2 = "cd" => "ab"
1177 SCM_STRING_SCAN_AFTER : v1 <- substring of s1 after s2
1178 s1 = "abcde" and s2 = "cd" => "e"
1179 SCM_STRING_SCAN_BEFORE2 : v1 <- substring of s1 before s2, v2 <- rest
1180 s1 = "abcde" and s2 = "cd" => "ab" and "cde"
1181 SCM_STRING_SCAN_AFTER2 : v1 <- substring of s1 up to s2, v2 <- rest
1182 s1 = "abcde" and s2 = "cd" => "abcd" and "e"
1183 SCM_STRING_SCAN_BOTH : v1 <- substring of s1 before, v2 <- after s2
1184 s1 = "abcde" and s2 = "cd" => "ab" and "e"
1185 */
1186 static int string_scan(ScmString *ss1, const char *s2,
1187 ScmSmallInt siz2, ScmSmallInt len2,
1188 int incomplete2,
1189 int retmode,
1190 int (*searcher)(const char*, ScmSmallInt, ScmSmallInt,
1191 const char*, ScmSmallInt, ScmSmallInt,
1192 ScmSmallInt*, ScmSmallInt*),
1193 ScmObj *v1, /* out */
1194 ScmObj *v2) /* out */
1195 {
1196 ScmSmallInt bi = 0, ci = 0;
1197 const ScmStringBody *sb = SCM_STRING_BODY(ss1);
1198 const char *s1 = SCM_STRING_BODY_START(sb);
1199 ScmSmallInt siz1 = SCM_STRING_BODY_SIZE(sb);
1200 ScmSmallInt len1 = SCM_STRING_BODY_LENGTH(sb);
1201
1202 if (retmode < 0 || retmode >= SCM_STRING_SCAN_NUM_RETMODES) {
1203 Scm_Error("return mode out fo range: %d", retmode);
1204 }
1205
1206 int incomplete =
1207 (SCM_STRING_BODY_INCOMPLETE_P(sb) || incomplete2)
1208 ? SCM_STRING_INCOMPLETE : 0;
1209
1210 /* prefiltering - if both string is complete, and s1 is sbstring
1211 and s2 is mbstring, we know there's no match. */
1212 int retcode =
1213 (!incomplete && (siz1 == len1) && (siz2 != len2))
1214 ? NOT_FOUND
1215 : searcher(s1, siz1, len1, s2, siz2, len2, &bi, &ci);
1216
1217 if (retcode == NOT_FOUND) {
1218 switch (retmode) {
1219 case SCM_STRING_SCAN_INDEX:
1220 case SCM_STRING_SCAN_CURSOR:
1221 case SCM_STRING_SCAN_BEFORE:
1222 case SCM_STRING_SCAN_AFTER:
1223 *v1 = SCM_FALSE;
1224 return 1;
1225 default:
1226 *v1 = SCM_FALSE;
1227 *v2 = SCM_FALSE;
1228 return 2;
1229 }
1230 }
1231
1232 if (retmode != SCM_STRING_SCAN_CURSOR
1233 && (retcode == FOUND_BYTE_INDEX && !incomplete)) {
1234 ci = count_length(s1, bi);
1235 }
1236
1237 switch (retmode) {
1238 case SCM_STRING_SCAN_INDEX:
1239 *v1 = Scm_MakeInteger(ci);
1240 return 1;
1241 case SCM_STRING_SCAN_CURSOR:
1242 *v1 = make_string_cursor(ss1, s1 + bi);
1243 return 1;
1244 case SCM_STRING_SCAN_BEFORE:
1245 *v1 = Scm_MakeString(s1, bi, ci, incomplete);
1246 return 1;
1247 case SCM_STRING_SCAN_AFTER:
1248 *v1 = Scm_MakeString(s1+bi+siz2, siz1-bi-siz2,
1249 len1-ci-len2, incomplete);
1250 return 1;
1251 case SCM_STRING_SCAN_BEFORE2:
1252 *v1 = Scm_MakeString(s1, bi, ci, incomplete);
1253 *v2 = Scm_MakeString(s1+bi, siz1-bi, len1-ci, incomplete);
1254 return 2;
1255 case SCM_STRING_SCAN_AFTER2:
1256 *v1 = Scm_MakeString(s1, bi+siz2, ci+len2, incomplete);
1257 *v2 = Scm_MakeString(s1+bi+siz2, siz1-bi-siz2,
1258 len1-ci-len2, incomplete);
1259 return 2;
1260 case SCM_STRING_SCAN_BOTH:
1261 *v1 = Scm_MakeString(s1, bi, ci, incomplete);;
1262 *v2 = Scm_MakeString(s1+bi+siz2, siz1-bi-siz2,
1263 len1-ci-len2, incomplete);
1264 return 2;
1265 }
1266 return 0; /* dummy */
1267 }
1268
1269 ScmObj Scm_StringScan(ScmString *s1, ScmString *s2, int retmode)
1270 {
1271 ScmObj v1, v2;
1272 const ScmStringBody *s2b = SCM_STRING_BODY(s2);
1273 int nvals = string_scan(s1,
1274 SCM_STRING_BODY_START(s2b),
1275 SCM_STRING_BODY_SIZE(s2b),
1276 SCM_STRING_BODY_LENGTH(s2b),
1277 SCM_STRING_BODY_INCOMPLETE_P(s2b),
1278 retmode, string_search, &v1, &v2);
1279 if (nvals == 1) return v1;
1280 else return Scm_Values2(v1, v2);
1281 }
1282
1283 ScmObj Scm_StringScanChar(ScmString *s1, ScmChar ch, int retmode)
1284 {
1285 ScmObj v1, v2;
1286 char buf[SCM_CHAR_MAX_BYTES];
1287 SCM_CHAR_PUT(buf, ch);
1288 int nvals = string_scan(s1, buf, SCM_CHAR_NBYTES(ch), 1, FALSE, retmode,
1289 string_search, &v1, &v2);
1290 if (nvals == 1) return v1;
1291 else return Scm_Values2(v1, v2);
1292 }
1293
1294 ScmObj Scm_StringScanRight(ScmString *s1, ScmString *s2, int retmode)
1295 {
1296 ScmObj v1, v2;
1297 const ScmStringBody *s2b = SCM_STRING_BODY(s2);
1298 int nvals = string_scan(s1,
1299 SCM_STRING_BODY_START(s2b),
1300 SCM_STRING_BODY_SIZE(s2b),
1301 SCM_STRING_BODY_LENGTH(s2b),
1302 SCM_STRING_BODY_INCOMPLETE_P(s2b),
1303 retmode, string_search_reverse, &v1, &v2);
1304 if (nvals == 1) return v1;
1305 else return Scm_Values2(v1, v2);
1306 }
1307
1308 ScmObj Scm_StringScanCharRight(ScmString *s1, ScmChar ch, int retmode)
1309 {
1310 ScmObj v1, v2;
1311 char buf[SCM_CHAR_MAX_BYTES];
1312 SCM_CHAR_PUT(buf, ch);
1313 int nvals = string_scan(s1, buf, SCM_CHAR_NBYTES(ch), 1, FALSE, retmode,
1314 string_search_reverse, &v1, &v2);
1315 if (nvals == 1) return v1;
1316 else return Scm_Values2(v1, v2);
1317 }
1318
1319 #undef NOT_FOUND
1320 #undef FOUND_BOTH_INDEX
1321 #undef FOUND_BYTE_INDEX
1322
1323 /* Split string by char. Char itself is not included in the result.
1324 If LIMIT >= 0, up to that number of matches are considered (i.e.
1325 up to LIMIT+1 strings are returned). LIMIT < 0 makes the number
1326 of matches unlimited.
1327 TODO: If CH is a utf-8 multi-byte char, Boyer-Moore skip table is
1328 calculated every time we call string_scan, which is a waste. Some
1329 mechanism to cache the skip table would be nice.
1330 */
1331 ScmObj Scm_StringSplitByCharWithLimit(ScmString *str, ScmChar ch, int limit)
1332 {
1333 char buf[SCM_CHAR_MAX_BYTES];
1334 int nb = SCM_CHAR_NBYTES(ch);
1335 ScmObj head = SCM_NIL, tail = SCM_NIL;
1336
1337 if (limit == 0) return SCM_LIST1(SCM_OBJ(str)); /* trivial case */
1338
1339 SCM_CHAR_PUT(buf, ch);
1340
1341 for (;;) {
1342 ScmObj v1, v2;
1343 (void)string_scan(str, buf, nb, 1, FALSE, SCM_STRING_SCAN_BOTH,
1344 string_search, &v1, &v2);
1345 if (SCM_FALSEP(v1)) {
1346 SCM_APPEND1(head, tail, SCM_OBJ(str));
1347 break;
1348 } else {
1349 SCM_APPEND1(head, tail, v1);
1350 if (--limit == 0) { SCM_APPEND1(head, tail, v2); break; }
1351 }
1352 str = SCM_STRING(v2);
1353 }
1354 return head;
1355 }
1356
1357 /* For ABI compatibility - On 1.0, let's make this have limit arg and
1358 drop Scm_StringSplitByCharWithLimit. */
1359 ScmObj Scm_StringSplitByChar(ScmString *str, ScmChar ch)
1360 {
1361 return Scm_StringSplitByCharWithLimit(str, ch, -1);
1362 }
1363
1364 /*----------------------------------------------------------------
1365 * Miscellaneous functions
1366 */
1367
1368 ScmObj Scm_StringToList(ScmString *str)
1369 {
1370 const ScmStringBody *b = SCM_STRING_BODY(str);
1371 ScmObj start = SCM_NIL, end = SCM_NIL;
1372 const char *bufp = SCM_STRING_BODY_START(b);
1373 ScmSmallInt len = SCM_STRING_BODY_LENGTH(b);
1374
1375 if (SCM_STRING_BODY_INCOMPLETE_P(b))
1376 Scm_Error("incomplete string not supported: %S", str);
1377 while (len-- > 0) {
1378 ScmChar ch;
1379 SCM_CHAR_GET(bufp, ch);
1380 bufp += SCM_CHAR_NBYTES(ch);
1381 SCM_APPEND1(start, end, SCM_MAKE_CHAR(ch));
1382 }
1383 return start;
1384 }
1385
1386 /* Convert cstring array to a list of Scheme strings. Cstring array
1387 can be NULL terminated (in case size < 0) or its size is explicitly
1388 specified (size >= 0). FLAGS is passed to Scm_MakeString. */
1389 ScmObj Scm_CStringArrayToList(const char **array, ScmSmallInt size, u_long flags)
1390 {
1391 ScmObj h = SCM_NIL, t = SCM_NIL;
1392 if (size < 0) {
1393 for (;*array; array++) {
1394 ScmObj s = Scm_MakeString(*array, -1, -1, flags);
1395 SCM_APPEND1(h, t, s);
1396 }
1397 } else {
1398 for (ScmSmallInt i=0; i<size; i++, array++) {
1399 ScmObj s = Scm_MakeString(*array, -1, -1, flags);
1400 SCM_APPEND1(h, t, s);
1401 }
1402 }
1403 return h;
1404 }
1405
1406 /* common routine for Scm_ListTo[Const]CStringArray */
1407 static ScmSmallInt list_to_cstring_array_check(ScmObj lis, int errp)
1408 {
1409 ScmObj lp;
1410 ScmSmallInt len = 0;
1411 SCM_FOR_EACH(lp, lis) {
1412 if (!SCM_STRINGP(SCM_CAR(lp))) {
1413 if (errp) Scm_Error("a proper list of strings is required, but the list contains non-string element: %S", SCM_CAR(lp));
1414 else return -1;
1415 }
1416 len++;
1417 }
1418 return len;
1419 }
1420
1421 /* Convert list of Scheme strings into C const char* string array, NULL
1422 terminated.
1423 If errp == FALSE, returns NULL on error.
1424 otherwise, signals an error. */
1425 const char **Scm_ListToConstCStringArray(ScmObj lis, int errp)
1426 {
1427 ScmSmallInt len = list_to_cstring_array_check(lis, errp);
1428 if (len < 0) return NULL;
1429 const char **array = SCM_NEW_ARRAY(const char*, len+1);
1430 const char **p = array;
1431 ScmObj lp;
1432 SCM_FOR_EACH(lp, lis) {
1433 *p++ = Scm_GetStringConst(SCM_STRING(SCM_CAR(lp)));
1434 }
1435 *p = NULL; /* termination */
1436 return array;
1437 }
1438
1439 /* Convert list of Scheme strings into C char* string array, NULL
1440 terminated.
1441 If errp == FALSE, returns NULL on error.
1442 otherwise, signals an error.
1443 If provided, alloc is used to allocate both a pointer array and char
1444 arrays. Otherwise, SCM_ALLOC is used. */
1445 char **Scm_ListToCStringArray(ScmObj lis, int errp, void *(*alloc)(size_t))
1446 {
1447 char **array, **p;
1448 ScmSmallInt len = list_to_cstring_array_check(lis, errp);
1449 if (len < 0) return NULL;
1450
1451 if (alloc) {
1452 p = array = (char **)alloc((len+1) * sizeof(char *));
1453 ScmObj lp;
1454 SCM_FOR_EACH(lp, lis) {
1455 const char *s = Scm_GetStringConst(SCM_STRING(SCM_CAR(lp)));
1456 *p = (char *)alloc(strlen(s) + 1);
1457 strcpy(*p, s);
1458 p++;
1459 }
1460 } else {
1461 p = array = SCM_NEW_ARRAY(char*, len+1);
1462 ScmObj lp;
1463 SCM_FOR_EACH(lp, lis) {
1464 *p++ = Scm_GetString(SCM_STRING(SCM_CAR(lp)));
1465 }
1466 }
1467 *p = NULL; /* termination */
1468 return array;
1469 }
1470
1471 /*----------------------------------------------------------------
1472 * printer
1473 */
1474
1475 /* ch is single byte if bytemode is true */
1476 static inline void string_putc(ScmChar ch, ScmPort *port, int bytemode)
1477 {
1478 const int ESCAPE_BUF_MAX = 12;
1479 char buf[ESCAPE_BUF_MAX];
1480 switch (ch) {
1481 case '\\': SCM_PUTZ("\\\\", -1, port); break;
1482 case '"': SCM_PUTZ("\\\"", -1, port); break;
1483 case '\n': SCM_PUTZ("\\n", -1, port); break;
1484 case '\t': SCM_PUTZ("\\t", -1, port); break;
1485 case '\r': SCM_PUTZ("\\r", -1, port); break;
1486 case '\f': SCM_PUTZ("\\f", -1, port); break;
1487 case '\0': SCM_PUTZ("\\0", -1, port); break;
1488 default:
1489 if (ch < 0x80 || bytemode) {
1490 if (ch < ' ' || ch == 0x7f || bytemode) {
1491 /* TODO: Should we provide 'legacy-compatible writer mode,
1492 which does not use ';' terminator? */
1493 snprintf(buf, ESCAPE_BUF_MAX, "\\x%02x;", (unsigned char)ch);
1494 SCM_PUTZ(buf, -1, port);
1495 } else {
1496 SCM_PUTC(ch, port);
1497 }
1498 } else {
1499 switch (Scm_CharGeneralCategory(ch)) {
1500 case SCM_CHAR_CATEGORY_Cc:
1501 case SCM_CHAR_CATEGORY_Cf:
1502 case SCM_CHAR_CATEGORY_Cs:
1503 case SCM_CHAR_CATEGORY_Co:
1504 case SCM_CHAR_CATEGORY_Cn:
1505 if (ch < 0x10000) {
1506 snprintf(buf, ESCAPE_BUF_MAX, "\\x%04x;", (u_int)ch);
1507 } else {
1508 snprintf(buf, ESCAPE_BUF_MAX, "\\x%x;", (u_int)ch);
1509 }
1510 SCM_PUTZ(buf, -1, port);
1511 break;
1512 default:
1513 SCM_PUTC(ch, port);
1514 }
1515 }
1516 }
1517 }
1518
1519 static void string_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx)
1520 {
1521 ScmString *str = SCM_STRING(obj);
1522 int limit = (ctx->controls? ctx->controls->stringLength : -1);
1523 int trimmed = FALSE;
1524
1525 if (Scm_WriteContextMode(ctx) == SCM_WRITE_DISPLAY) {
1526 /* Display mode isn't affected by string-length control */
1527 SCM_PUTS(str, port);
1528 } else {
1529 const ScmStringBody *b = SCM_STRING_BODY(str);
1530 if (SCM_STRING_BODY_SINGLE_BYTE_P(b)) {
1531 const char *cp = SCM_STRING_BODY_START(b);
1532 ScmSmallInt size = SCM_STRING_BODY_SIZE(b);
1533 if (limit >= 0 && limit < size) {
1534 trimmed = TRUE; size = limit;
1535 }
1536
1537 if (SCM_STRING_BODY_INCOMPLETE_P(b)) {
1538 /* TODO: Should we provide legacy-compatible writer mode,
1539 which puts #*"..." instead? */
1540 SCM_PUTZ("#**\"", -1, port);
1541 } else {
1542 SCM_PUTC('"', port);
1543 }
1544 while (--size >= 0) {
1545 string_putc(*cp++, port, SCM_STRING_BODY_INCOMPLETE_P(b));
1546 }
1547 } else {
1548 const char *cp = SCM_STRING_BODY_START(b);
1549 ScmSmallInt len = SCM_STRING_BODY_LENGTH(b);
1550 if (limit >= 0 && limit < len) {
1551 trimmed = TRUE; len = limit;
1552 }
1553
1554 SCM_PUTC('"', port);
1555 while (--len >= 0) {
1556 ScmChar ch;
1557 SCM_CHAR_GET(cp, ch);
1558 string_putc(ch, port, FALSE);
1559 cp += SCM_CHAR_NBYTES(ch);
1560 }
1561 }
1562 if (trimmed) {
1563 SCM_PUTZ(SCM_WRITTEN_ELLIPSIS, -1, port);
1564 }
1565 SCM_PUTC('"', port);
1566 }
1567 }
1568
1569 /*==================================================================
1570 *
1571 * String index building
1572 *
1573 */
1574
1575 static int string_body_index_needed(const ScmStringBody *sb)
1576 {
1577 return (!SCM_STRING_BODY_SINGLE_BYTE_P(sb)
1578 && !SCM_STRING_BODY_INCOMPLETE_P(sb)
1579 && SCM_STRING_BODY_SIZE(sb) >= 64);
1580 }
1581
1582 int Scm_StringBodyFastIndexableP(const ScmStringBody *sb)
1583 {
1584 return (!string_body_index_needed(sb)
1585 || SCM_STRING_BODY_HAS_INDEX(sb));
1586 }
1587
1588 static size_t compute_index_size(const ScmStringBody *sb, int interval)
1589 {
1590 ScmSmallInt len = SCM_STRING_BODY_LENGTH(sb);
1591 /* We don't store the first entry (0th character == 0th byte), and
1592 we use two extra entry for the signature and index_size. So
1593 we need +1. */
1594 return ((len + interval - 1)/interval) + 1;
1595 }
1596
1597 static void *build_index_array(const ScmStringBody *sb)
1598 {
1599 /* Signature byte is repeated in the first element of the vector */
1600 #define SIG8(type,sig) (type)(sig)
1601 #define SIG16(type,sig) ((type)((sig)<<8)|(sig))
1602 #define SIG32(type,sig) ((type)(SIG16(type,sig)<<16)|SIG16(type,sig))
1603 #define SIG64(type,sig) ((type)(SIG32(type,sig)<<32)|SIG32(type,sig))
1604
1605 #define BUILD_ARRAY(type_, typeenum_, shift_, sigrep_) \
1606 do { \
1607 int interval = 1 << (shift_); \
1608 size_t index_size = compute_index_size(sb, interval); \
1609 type_ *vec = SCM_NEW_ATOMIC_ARRAY(type_, index_size); \
1610 u_long sig = STRING_INDEX_SIGNATURE(shift_, typeenum_); \
1611 vec[0] = sigrep_(type_,sig); \
1612 vec[1] = (type_)index_size; \
1613 const char *p = SCM_STRING_BODY_START(sb); \
1614 for (size_t i = 2; i < index_size; i++) { \
1615 const char *q = forward_pos(sb, p, interval); \
1616 vec[i] = (type_)(q - SCM_STRING_BODY_START(sb)); \
1617 p = q; \
1618 } \
1619 return vec; \
1620 } while (0)
1621
1622 /* Technically we can use index8 even if size is bigger than 256,
1623 as long as the last indexed character is within the range. But
1624 checking it is too much. */
1625 if (sb->size < 256) {
1626 BUILD_ARRAY(uint8_t, STRING_INDEX8, 4, SIG8);
1627 } else if (sb->size < 8192) {
1628 /* 32 chars interval */
1629 BUILD_ARRAY(uint16_t, STRING_INDEX16, 5, SIG16);
1630 } else if (sb->size < 65536) {
1631 /* 64 chars interval */
1632 BUILD_ARRAY(uint16_t, STRING_INDEX16, 6, SIG16);
1633 }
1634 #if SIZEOF_LONG == 4
1635 else {
1636 /* 128 chars interval */
1637 BUILD_ARRAY(uint32_t, STRING_INDEX32, 7, SIG32);
1638 }
1639 #else /* SIZEOF_LONG != 4 */
1640 else if (sb->size < (1L<<32)) {
1641 /* 128 chars interval */
1642 BUILD_ARRAY(uint32_t, STRING_INDEX32, 7, SIG32);
1643 } else {
1644 /* 256 chars interval */
1645 BUILD_ARRAY(uint64_t, STRING_INDEX64, 8, SIG64);
1646 }
1647 #endif
1648 #undef BUILD_ARRAY
1649 }
1650
1651 void Scm_StringBodyBuildIndex(ScmStringBody *sb)
1652 {
1653 if (!string_body_index_needed(sb) || SCM_STRING_BODY_HAS_INDEX(sb)) return;
1654 /* This is idempotent, atomic operation; no need to lock. */
1655 sb->index = build_index_array(sb);
1656 }
1657
1658 /* For debugging */
1659 void Scm_StringBodyIndexDump(const ScmStringBody *sb, ScmPort *port)
1660 {
1661 ScmStringIndex *index = STRING_INDEX(sb->index);
1662 if (index == NULL) {
1663 Scm_Printf(port, "(nil)\n");
1664 return;
1665 }
1666 int interval = STRING_INDEX_INTERVAL(index);
1667 size_t index_size = 0;
1668
1669 switch (STRING_INDEX_TYPE(index)) {
1670 case STRING_INDEX8:
1671 Scm_Printf(port, "index8 ");
1672 index_size = (size_t)index->index8[1];
1673 break;
1674 case STRING_INDEX16:
1675 Scm_Printf(port, "index16 ");
1676 index_size = (size_t)index->index16[1];
1677 break;
1678 case STRING_INDEX32:
1679 Scm_Printf(port, "index32 ");
1680 index_size = (size_t)index->index32[1];
1681 break;
1682 case STRING_INDEX64:
1683 Scm_Printf(port, "index64 ");
1684 index_size = (size_t)index->index64[1];
1685 break;
1686 default:
1687 Scm_Printf(port, "unknown(%02x) ", (uint8_t)STRING_INDEX_TYPE(index));
1688 }
1689 Scm_Printf(port, " interval %d size %d\n", interval, index_size-1);
1690 Scm_Printf(port, " 0 0\n");
1691 for (size_t i = 2; i < index_size; i++) {
1692 switch (STRING_INDEX_TYPE(index)) {
1693 case STRING_INDEX8:
1694 Scm_Printf(port, " %8ld %8u\n", i-1, index->index8[i]); break;
1695 case STRING_INDEX16:
1696 Scm_Printf(port, " %8ld %8u\n", i-1, index->index16[i]); break;
1697 case STRING_INDEX32:
1698 Scm_Printf(port, " %8ld %8u\n", i-1, index->index32[i]); break;
1699 case STRING_INDEX64:
1700 Scm_Printf(port, " %8ld %8lu\n",i-1, index->index64[i]); break;
1701 }
1702 }
1703 }
1704
1705
1706 /*==================================================================
1707 *
1708 * String cursor API
1709 *
1710 */
1711
1712 /* Public interface */
1713 int Scm_StringCursorP(ScmObj obj)
1714 {
1715 return SCM_STRING_CURSOR_P(obj);
1716 }
1717
1718 static ScmObj make_string_cursor(ScmString *src, const char *ptr)
1719 {
1720 const ScmStringBody *srcb = SCM_STRING_BODY(src);
1721
1722 if (ptr < SCM_STRING_BODY_START(srcb) ||
1723 ptr > SCM_STRING_BODY_END(srcb)) {
1724 Scm_Error("cursor out of range of %S: %ld",
1725 SCM_OBJ(src),
1726 (ScmSmallInt)(ptr - SCM_STRING_BODY_START(srcb)));
1727 }
1728
1729 ScmSmallInt offset = (ScmSmallInt)(ptr - SCM_STRING_BODY_START(srcb));
1730 if (!SCM_VM_RUNTIME_FLAG_IS_SET(Scm_VM(), SCM_SAFE_STRING_CURSORS) &&
1731 SCM_STRING_CURSOR_FITS_SMALL_P(offset)) {
1732 return SCM_MAKE_STRING_CURSOR_SMALL(offset);
1733 }
1734
1735 ScmStringCursorLarge *sc = SCM_NEW(ScmStringCursorLarge);
1736 SCM_SET_CLASS(sc, SCM_CLASS_STRING_CURSOR_LARGE);
1737 sc->offset = offset;
1738 sc->start = SCM_STRING_BODY_START(srcb);
1739 return SCM_OBJ(sc);
1740 }
1741
1742 ScmObj Scm_MakeStringCursorFromIndex(ScmString *src, ScmSmallInt index)
1743 {
1744 const ScmStringBody *srcb = SCM_STRING_BODY(src);
1745 ScmSmallInt len = SCM_STRING_BODY_LENGTH(srcb);
1746 if (index < 0 || index > len) {
1747 Scm_Error("index out of range: %ld", index);
1748 }
1749 return make_string_cursor(src, index2ptr(srcb, index));
1750 }
1751
1752 ScmObj Scm_MakeStringCursorEnd(ScmString *src)
1753 {
1754 const ScmStringBody *srcb = SCM_STRING_BODY(src);
1755
1756 ScmSmallInt offset = SCM_STRING_BODY_END(srcb) - SCM_STRING_BODY_START(srcb);
1757 if (!SCM_VM_RUNTIME_FLAG_IS_SET(Scm_VM(), SCM_SAFE_STRING_CURSORS) &&
1758 SCM_STRING_CURSOR_FITS_SMALL_P(offset)) {
1759 return SCM_MAKE_STRING_CURSOR_SMALL(offset);
1760 }
1761 ScmStringCursorLarge *sc = SCM_NEW(ScmStringCursorLarge);
1762 SCM_SET_CLASS(sc, SCM_CLASS_STRING_CURSOR_LARGE);
1763 sc->offset = offset;
1764 sc->start = SCM_STRING_BODY_START(srcb);
1765 return SCM_OBJ(sc);
1766 }
1767
1768 ScmObj Scm_StringCursorIndex(ScmString *src, ScmObj sc)
1769 {
1770 if (SCM_INTP(sc) || SCM_BIGNUMP(sc)) {
1771 return sc; /* no validation */
1772 }
1773
1774 const ScmStringBody *srcb = SCM_STRING_BODY(src);
1775 const char *ptr = NULL;
1776
1777 if ((ptr = string_cursor_ptr(srcb, sc)) == NULL) {
1778 Scm_Error("must be either an index or a cursor: %S", sc);
1779 }
1780
1781 if (SCM_STRING_BODY_SINGLE_BYTE_P(srcb) ||
1782 SCM_STRING_BODY_INCOMPLETE_P(srcb)) {
1783 return SCM_MAKE_INT(ptr - SCM_STRING_BODY_START(srcb));
1784 }
1785
1786 const char *current = SCM_STRING_BODY_START(srcb);
1787 ScmSmallInt len = SCM_STRING_BODY_LENGTH(srcb);
1788 ScmSmallInt index = 0;
1789 while (index < len && current < ptr) {
1790 current += SCM_CHAR_NFOLLOWS(*current) + 1;
1791 index++;
1792 }
1793 if (current != ptr) {
1794 Scm_Error("cursor not pointed at the beginning of a character: %S", sc);
1795 }
1796
1797 return SCM_MAKE_INT(index);
1798 }
1799
1800 ScmObj Scm_StringCursorForward(ScmString* s, ScmObj sc, int nchars)
1801 {
1802 if (nchars < 0) {
1803 Scm_Error("nchars is negative: %ld", nchars);
1804 }
1805
1806 if (SCM_INTEGERP(sc)) {
1807 return Scm_MakeStringCursorFromIndex(s, Scm_GetInteger(sc) + nchars);
1808 }
1809
1810 const ScmStringBody *srcb = SCM_STRING_BODY(s);
1811 const char *ptr = string_cursor_ptr(srcb, sc);
1812 if (ptr == NULL) {
1813 Scm_Error("must be either an index or a cursor: %S", sc);
1814 }
1815 return make_string_cursor(s, forward_pos(srcb, ptr, nchars));
1816 }
1817
1818 ScmObj Scm_StringCursorBack(ScmString* s, ScmObj sc, int nchars)
1819 {
1820 if (nchars < 0) {
1821 Scm_Error("nchars is negative: %ld", nchars);
1822 }
1823
1824 if (SCM_INTP(sc) || SCM_BIGNUMP(sc)) {
1825 return Scm_MakeStringCursorFromIndex(s, Scm_GetInteger(sc) - nchars);
1826 }
1827
1828 const ScmStringBody *srcb = SCM_STRING_BODY(s);
1829 const char *ptr = string_cursor_ptr(srcb, sc);
1830 if (ptr == NULL) {
1831 Scm_Error("must be either an index or a cursor: %S", sc);
1832 }
1833
1834 if (SCM_STRING_BODY_SINGLE_BYTE_P(srcb) ||
1835 SCM_STRING_BODY_INCOMPLETE_P(srcb)) {
1836 return make_string_cursor(s, ptr - nchars);
1837 }
1838
1839 while (nchars--) {
1840 const char *prev;
1841 SCM_CHAR_BACKWARD(ptr, SCM_STRING_BODY_START(srcb), prev);
1842 if (!prev) {
1843 Scm_Error("nchars out of range: %ld", nchars);
1844 }
1845 ptr = prev;
1846 }
1847
1848 return make_string_cursor(s, ptr);
1849 }
1850
1851 ScmChar Scm_StringRefCursor(ScmString* s, ScmObj sc, int range_error)
1852 {
1853 if (SCM_INTP(sc)) {
1854 return Scm_StringRef(s, SCM_INT_VALUE(sc), range_error);
1855 }
1856
1857 const ScmStringBody *srcb = SCM_STRING_BODY(s);
1858
1859 /* we can't allow string-ref on incomplete strings, since it may yield
1860 invalid character object. */
1861 if (SCM_STRING_BODY_INCOMPLETE_P(srcb)) {
1862 Scm_Error("incomplete string not allowed : %S", s);
1863 }
1864
1865 const char *ptr = string_cursor_ptr(srcb, sc);
1866 if (ptr == NULL) {
1867 Scm_Error("must be either an index or a cursor: %S", sc);
1868 }
1869 if (ptr == SCM_STRING_BODY_END(srcb)) {
1870 if (range_error) {
1871 Scm_Error("cursor is at the end: %S", sc);
1872 }
1873 return SCM_CHAR_INVALID;
1874 }
1875 ScmChar ch;
1876 SCM_CHAR_GET(ptr, ch);
1877 return ch;
1878 }
1879
1880 ScmObj Scm_SubstringCursor(ScmString *str,
1881 ScmObj start_scm, ScmObj end_scm)
1882 {
1883 const ScmStringBody *sb = SCM_STRING_BODY(str);
1884 const char *start = string_cursor_ptr(sb, start_scm);
1885 const char *end = string_cursor_ptr(sb, end_scm);
1886
1887 if (start && end) {
1888 return substring_cursor(sb, start, end, FALSE);
1889 }
1890
1891 return substring(SCM_STRING_BODY(str),
1892 Scm_GetInteger(Scm_StringCursorIndex(str, start_scm)),
1893 Scm_GetInteger(Scm_StringCursorIndex(str, end_scm)),
1894 FALSE, FALSE);
1895 }
1896
1897 int Scm_StringCursorCompare(ScmObj sc1, ScmObj sc2,
1898 int (*numcmp)(ScmObj, ScmObj))
1899 {
1900 /*
1901 * Handle indexes separately, we can't mix index and cursor
1902 * because cursor is byte offset, not index.
1903 */
1904 if (SCM_INTP(sc1) && SCM_INTP(sc2)) {
1905 return numcmp(sc1, sc2);
1906 }
1907
1908 ScmSmallInt i1 = string_cursor_offset(sc1);
1909 ScmSmallInt i2 = string_cursor_offset(sc2);
1910 if (i1 < 0 || i2 < 0) {
1911 Scm_Error("arguments must be either both cursors or both indexes: %S vs %S", sc1, sc2);
1912 }
1913 return numcmp(SCM_MAKE_INT(i1), SCM_MAKE_INT(i2));
1914 }
1915
1916 /*==================================================================
1917 *
1918 * Dynamic strings
1919 *
1920 */
1921
1922 /* I used to use realloc() to grow the storage; now I avoid it, for
1923 Boehm GC's realloc almost always copies the original content and
1924 we don't get any benefit.
1925 The growing string is kept in the chained chunks. The size of
1926 chunk getting bigger as the string grows, until a certain threshold.
1927 The memory for actual chunks and the chain is allocated separately,
1928 in order to use SCM_NEW_ATOMIC.
1929 */
1930
1931 /* NB: it is important that DString functions don't call any
1932 * time-consuming procedures except memory allocation. Some of
1933 * mutex code in other parts relies on that fact.
1934 */
1935
1936 /* maximum chunk size */
1937 #define DSTRING_MAX_CHUNK_SIZE 8180
1938
1939 void Scm_DStringInit(ScmDString *dstr)
1940 {
1941 dstr->init.bytes = 0;
1942 dstr->anchor = dstr->tail = NULL;
1943 dstr->current = dstr->init.data;
1944 dstr->end = dstr->current + SCM_DSTRING_INIT_CHUNK_SIZE;
1945 dstr->lastChunkSize = SCM_DSTRING_INIT_CHUNK_SIZE;
1946 dstr->length = 0;
1947 }
1948
1949 ScmSmallInt Scm_DStringSize(ScmDString *dstr)
1950 {
1951 ScmSmallInt size;
1952 if (dstr->tail) {
1953 size = dstr->init.bytes;
1954 dstr->tail->chunk->bytes = dstr->current - dstr->tail->chunk->data;
1955 for (ScmDStringChain *chain = dstr->anchor; chain; chain = chain->next) {
1956 size += chain->chunk->bytes;
1957 }
1958 } else {
1959 size = dstr->init.bytes = dstr->current - dstr->init.data;
1960 }
1961 if (size > SCM_STRING_MAX_SIZE) {
1962 Scm_Error("Scm_DStringSize: size exceeded the range: %ld", size);
1963 }
1964 return size;
1965 }
1966
1967 static ScmDStringChunk *newChunk(ScmSmallInt size)
1968 {
1969 return SCM_NEW_ATOMIC2(ScmDStringChunk*,
1970 (sizeof(ScmDStringChunk)
1971 +size-SCM_DSTRING_INIT_CHUNK_SIZE));
1972 }
1973
1974 void Scm__DStringRealloc(ScmDString *dstr, ScmSmallInt minincr)
1975 {
1976 /* sets the byte count of the last chunk */
1977 if (dstr->tail) {
1978 dstr->tail->chunk->bytes = dstr->current - dstr->tail->chunk->data;
1979 } else {
1980 dstr->init.bytes = dstr->current - dstr->init.data;
1981 }
1982
1983 /* determine the size of the new chunk. the increase factor 3 is
1984 somewhat arbitrary, determined by rudimental benchmarking. */
1985 ScmSmallInt newsize = dstr->lastChunkSize * 3;
1986 if (newsize > DSTRING_MAX_CHUNK_SIZE) {
1987 newsize = DSTRING_MAX_CHUNK_SIZE;
1988 }
1989 if (newsize < minincr) {
1990 newsize = minincr;
1991 }
1992
1993 ScmDStringChunk *newchunk = newChunk(newsize);
1994 newchunk->bytes = 0;
1995 ScmDStringChain *newchain = SCM_NEW(ScmDStringChain);
1996
1997 newchain->next = NULL;
1998 newchain->chunk = newchunk;
1999 if (dstr->tail) {
2000 dstr->tail->next = newchain;
2001 dstr->tail = newchain;
2002 } else {
2003 dstr->anchor = dstr->tail = newchain;
2004 }
2005 dstr->current = newchunk->data;
2006 dstr->end = newchunk->data + newsize;
2007 dstr->lastChunkSize = newsize;
2008 }
2009
2010 /* Retrieve accumulated string. */
2011 static const char *dstring_getz(ScmDString *dstr,
2012 ScmSmallInt *psiz,
2013 ScmSmallInt *plen,
2014 int noalloc)
2015 {
2016 ScmSmallInt size, len;
2017 char *buf;
2018 if (dstr->anchor == NULL) {
2019 /* we only have one chunk */
2020 size = dstr->current - dstr->init.data;
2021 CHECK_SIZE(size);
2022 len = dstr->length;
2023 if (noalloc) {
2024 buf = dstr->init.data;
2025 } else {
2026 buf = SCM_STRDUP_PARTIAL(dstr->init.data, size);
2027 }
2028 } else {
2029 ScmDStringChain *chain = dstr->anchor;
2030 char *bptr;
2031
2032 size = Scm_DStringSize(dstr);
2033 CHECK_SIZE(size);
2034 len = dstr->length;
2035 bptr = buf = SCM_NEW_ATOMIC2(char*, size+1);
2036
2037 memcpy(bptr, dstr->init.data, dstr->init.bytes);
2038 bptr += dstr->init.bytes;
2039 for (; chain; chain = chain->next) {
2040 memcpy(bptr, chain->chunk->data, chain->chunk->bytes);
2041 bptr += chain->chunk->bytes;
2042 }
2043 *bptr = '\0';
2044 }
2045 if (len < 0) len = count_length(buf, size);
2046 if (plen) *plen = len;
2047 if (psiz) *psiz = size;
2048 return buf;
2049 }
2050
2051 ScmObj Scm_DStringGet(ScmDString *dstr, u_long flags)
2052 {
2053 ScmSmallInt len, size;
2054 const char *str = dstring_getz(dstr, &size, &len, FALSE);
2055 return SCM_OBJ(make_str(len, size, str, flags|SCM_STRING_TERMINATED, NULL));
2056 }
2057
2058 /* For conveninence. Note that dstr may already contain NUL byte in it,
2059 in that case you'll get chopped string. */
2060 const char *Scm_DStringGetz(ScmDString *dstr)
2061 {
2062 ScmSmallInt len, size;
2063 return dstring_getz(dstr, &size, &len, FALSE);
2064 }
2065
2066 /* Concatenate all chains in DString into one chunk. Externally nothing
2067 really changes, but this can be used to optimize allocation. */
2068 void Scm_DStringWeld(ScmDString *dstr)
2069 {
2070 if (dstr->anchor == NULL) return; /* nothing to do */
2071 ScmDStringChain *chain = dstr->anchor;
2072 ScmSmallInt size = Scm_DStringSize(dstr);
2073 ScmSmallInt bufsiz = size + (dstr->end - dstr->current);
2074 ScmDStringChunk *newchunk = newChunk(bufsiz);
2075 newchunk->bytes = size;
2076 char *bptr = newchunk->data;
2077 memcpy(bptr, dstr->init.data, dstr->init.bytes);
2078 bptr += dstr->init.bytes;
2079 for (; chain; chain = chain->next) {
2080 memcpy(bptr, chain->chunk->data, chain->chunk->bytes);
2081 bptr += chain->chunk->bytes;
2082 }
2083 dstr->init.bytes = 0;
2084 dstr->anchor->chunk = newchunk;
2085 dstr->anchor->next = NULL;
2086 dstr->tail = dstr->anchor;
2087 dstr->current = newchunk->data + size;
2088 dstr->end = newchunk->data + bufsiz;
2089 dstr->lastChunkSize = bufsiz;
2090 }
2091
2092 /* Returns the current content of DString, along with byte size and character
2093 length. The returned pointer may not be NUL-terminated.
2094
2095 Unlike Scm_DStringGet[z], returned pointer can directly points into
2096 the internal buffer of Scm_DString; especially, this never allocates
2097 if DString only uses initial buffer. The caller should be aware that
2098 the returned content may be altered by further DString operation. */
2099 const char *Scm_DStringPeek(ScmDString *dstr,
2100 ScmSmallInt *size, ScmSmallInt *len)
2101 {
2102 Scm_DStringWeld(dstr);
2103 if (dstr->anchor == NULL) {
2104 if (size) *size = dstr->current - dstr->init.data;
2105 if (len) *len = dstr->length;
2106 return dstr->init.data;
2107 } else {
2108 if (size) *size = dstr->anchor->chunk->bytes;
2109 if (len) *len = dstr->length;
2110 return dstr->anchor->chunk->data;
2111 }
2112 }
2113
2114 void Scm_DStringPutz(ScmDString *dstr, const char *str, ScmSmallInt size)
2115 {
2116 if (size < 0) size = strlen(str);
2117 if (dstr->current + size > dstr->end) {
2118 Scm__DStringRealloc(dstr, size);
2119 }
2120 memcpy(dstr->current, str, size);
2121 dstr->current += size;
2122 if (dstr->length >= 0) {
2123 ScmSmallInt len = count_length(str, size);
2124 if (len >= 0) dstr->length += len;
2125 else dstr->length = -1;
2126 }
2127 }
2128
2129 void Scm_DStringAdd(ScmDString *dstr, ScmString *str)
2130 {
2131 const ScmStringBody *b = SCM_STRING_BODY(str);
2132 ScmSmallInt size = SCM_STRING_BODY_SIZE(b);
2133 if (size == 0) return;
2134 if (dstr->current + size > dstr->end) {
2135 Scm__DStringRealloc(dstr, size);
2136 }
2137 memcpy(dstr->current, SCM_STRING_BODY_START(b), size);
2138 dstr->current += size;
2139 if (dstr->length >= 0 && !SCM_STRING_BODY_INCOMPLETE_P(b)) {
2140 dstr->length += SCM_STRING_BODY_LENGTH(b);
2141 } else {
2142 dstr->length = -1;
2143 }
2144 }
2145
2146 void Scm_DStringPutb(ScmDString *ds, char byte)
2147 {
2148 SCM_DSTRING_PUTB(ds, byte);
2149 }
2150
2151 void Scm_DStringPutc(ScmDString *ds, ScmChar ch)
2152 {
2153 SCM_DSTRING_PUTC(ds, ch);
2154 }
2155
2156 /* Truncate DString at the specified size.
2157 Returns after-truncation size (it may be smaller than newsize if
2158 the original DString isn't as large as newsize. */
2159 ScmSmallInt Scm_DStringTruncate(ScmDString *dstr, ScmSmallInt newsize)
2160 {
2161 ScmSmallInt origsize = Scm_DStringSize(dstr);
2162
2163 if (newsize < dstr->init.bytes) {
2164 dstr->init.bytes = newsize;
2165 dstr->anchor = NULL;
2166 dstr->tail = NULL;
2167 dstr->current = dstr->init.data + newsize;
2168 dstr->end = dstr->init.data + SCM_DSTRING_INIT_CHUNK_SIZE;
2169 } else {
2170 if (newsize >= origsize) return origsize;
2171 ScmDStringChain *chain = dstr->anchor;
2172 ScmSmallInt ss = dstr->init.bytes;
2173 for (; chain; chain = chain->next) {
2174 if (newsize < ss + chain->chunk->bytes) {
2175 /* truncate this chunk */
2176 if (chain == dstr->tail) {
2177 chain->chunk->bytes = newsize - ss;
2178 dstr->current = chain->chunk->data + newsize - ss;
2179 } else {
2180 dstr->lastChunkSize = chain->chunk->bytes;
2181 dstr->end = chain->chunk->data + chain->chunk->bytes;
2182 chain->chunk->bytes = newsize - ss;
2183 chain->next = NULL;
2184 dstr->tail = chain;
2185 dstr->current = chain->chunk->data + newsize - ss;
2186 }
2187 break;
2188 }
2189 ss += chain->chunk->bytes;
2190 }
2191 SCM_ASSERT(chain != NULL);
2192 }
2193
2194 /* If we accumulated only ASCII, we can adjust length as well. */
2195 if (dstr->length == origsize || newsize == 0) dstr->length = newsize;
2196 else dstr->length = -1;
2197 return newsize;
2198 }
2199
2200
2201 /* for debug */
2202 void Scm_DStringDump(FILE *out, ScmDString *dstr)
2203 {
2204 fprintf(out, "DString %p\n", dstr);
2205 if (dstr->anchor) {
2206 fprintf(out, " chunk0[%3ld] = \"", dstr->init.bytes);
2207 SCM_IGNORE_RESULT(fwrite(dstr->init.data, 1, dstr->init.bytes, out));
2208 fprintf(out, "\"\n");
2209 ScmDStringChain *chain = dstr->anchor;
2210 for (int i=1; chain; chain = chain->next, i++) {
2211 ScmSmallInt size = (chain->next? chain->chunk->bytes : (dstr->current - dstr->tail->chunk->data));
2212 fprintf(out, " chunk%d[%3ld] = \"", i, size);
2213 SCM_IGNORE_RESULT(fwrite(chain->chunk->data, 1, size, out));
2214 fprintf(out, "\"\n");
2215 }
2216 } else {
2217 ScmSmallInt size = dstr->current - dstr->init.data;
2218 fprintf(out, " chunk0[%3ld] = \"", size);
2219 SCM_IGNORE_RESULT(fwrite(dstr->init.data, 1, size, out));
2220 fprintf(out, "\"\n");
2221 }
2222 }