str: New functions for case-matching of substrings, prefixes, and suffixes.
[pspp] / src / libpspp / str.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 1997-9, 2000, 2006, 2009, 2010, 2011, 2012, 2014,
3    2020 Free Software Foundation, Inc.
4
5    This program is free software: you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation, either version 3 of the License, or
8    (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 #include "str.h"
21
22 #include <ctype.h>
23 #include <errno.h>
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <unistr.h>
27
28 #include "libpspp/cast.h"
29 #include "libpspp/i18n.h"
30 #include "libpspp/message.h"
31 #include "libpspp/pool.h"
32
33 #include "gl/c-ctype.h"
34 #include "gl/c-vasnprintf.h"
35 #include "gl/relocatable.h"
36 #include "gl/minmax.h"
37 #include "gl/xalloc.h"
38 #include "gl/xmemdup0.h"
39 #include "gl/xsize.h"
40 \f
41 /* Reverses the order of NBYTES bytes at address P, thus converting
42    between little- and big-endian byte orders.  */
43 void
44 buf_reverse (char *p, size_t nbytes)
45 {
46   char *h = p, *t = &h[nbytes - 1];
47   char temp;
48
49   nbytes /= 2;
50   while (nbytes--)
51     {
52       temp = *h;
53       *h++ = *t;
54       *t-- = temp;
55     }
56 }
57
58 /* Compares the SIZE bytes in A to those in B, disregarding case,
59    and returns a strcmp()-type result. */
60 int
61 buf_compare_case (const char *a_, const char *b_, size_t size)
62 {
63   const unsigned char *a = (unsigned char *) a_;
64   const unsigned char *b = (unsigned char *) b_;
65
66   while (size-- > 0)
67     {
68       unsigned char ac = toupper (*a++);
69       unsigned char bc = toupper (*b++);
70
71       if (ac != bc)
72         return ac > bc ? 1 : -1;
73     }
74
75   return 0;
76 }
77
78 /* Compares A of length A_LEN to B of length B_LEN.  The shorter
79    string is considered to be padded with spaces to the length of
80    the longer. */
81 int
82 buf_compare_rpad (const char *a, size_t a_len, const char *b, size_t b_len)
83 {
84   size_t min_len;
85   int result;
86
87   min_len = a_len < b_len ? a_len : b_len;
88   result = memcmp (a, b, min_len);
89   if (result != 0)
90     return result;
91   else
92     {
93       size_t idx;
94
95       if (a_len < b_len)
96         {
97           for (idx = min_len; idx < b_len; idx++)
98             if (' ' != b[idx])
99               return ' ' > b[idx] ? 1 : -1;
100         }
101       else
102         {
103           for (idx = min_len; idx < a_len; idx++)
104             if (a[idx] != ' ')
105               return a[idx] > ' ' ? 1 : -1;
106         }
107       return 0;
108     }
109 }
110
111 /* Compares strin A to string B.  The shorter string is
112    considered to be padded with spaces to the length of the
113    longer. */
114 int
115 str_compare_rpad (const char *a, const char *b)
116 {
117   return buf_compare_rpad (a, strlen (a), b, strlen (b));
118 }
119
120 /* Copies string SRC to buffer DST, of size DST_SIZE bytes.
121    DST is truncated to DST_SIZE bytes or padded on the right with
122    copies of PAD as needed. */
123 void
124 buf_copy_str_rpad (char *dst, size_t dst_size, const char *src, char pad)
125 {
126   size_t src_len = strlen (src);
127   if (src_len >= dst_size)
128     memcpy (dst, src, dst_size);
129   else
130     {
131       memcpy (dst, src, src_len);
132       memset (&dst[src_len], pad, dst_size - src_len);
133     }
134 }
135
136 /* Copies string SRC to buffer DST, of size DST_SIZE bytes.
137    DST is truncated to DST_SIZE bytes or padded on the left with
138    copies of PAD as needed. */
139 void
140 buf_copy_str_lpad (char *dst, size_t dst_size, const char *src, char pad)
141 {
142   size_t src_len = strlen (src);
143   if (src_len >= dst_size)
144     memcpy (dst, src, dst_size);
145   else
146     {
147       size_t n_pad = dst_size - src_len;
148       memset (&dst[0], pad, n_pad);
149       memcpy (dst + n_pad, src, src_len);
150     }
151 }
152
153 /* Copies buffer SRC, of SRC_SIZE bytes, to DST, of DST_SIZE bytes.
154    DST is truncated to DST_SIZE bytes or padded on the left with
155    copies of PAD as needed. */
156 void
157 buf_copy_lpad (char *dst, size_t dst_size,
158                const char *src, size_t src_size,
159                char pad)
160 {
161   if (src_size >= dst_size)
162     memmove (dst, src, dst_size);
163   else
164     {
165       memset (dst, pad, dst_size - src_size);
166       memmove (&dst[dst_size - src_size], src, src_size);
167     }
168 }
169
170 /* Copies buffer SRC, of SRC_SIZE bytes, to DST, of DST_SIZE bytes.
171    DST is truncated to DST_SIZE bytes or padded on the right with
172    copies of PAD as needed. */
173 void
174 buf_copy_rpad (char *dst, size_t dst_size,
175                const char *src, size_t src_size,
176                char pad)
177 {
178   if (src_size >= dst_size)
179     memmove (dst, src, dst_size);
180   else
181     {
182       memmove (dst, src, src_size);
183       memset (&dst[src_size], pad, dst_size - src_size);
184     }
185 }
186
187 /* Copies string SRC to string DST, which is in a buffer DST_SIZE
188    bytes long.
189    Truncates DST to DST_SIZE - 1 bytes or right-pads with
190    spaces to DST_SIZE - 1 bytes if necessary. */
191 void
192 str_copy_rpad (char *dst, size_t dst_size, const char *src)
193 {
194   if (dst_size > 0)
195     {
196       size_t src_len = strlen (src);
197       if (src_len < dst_size - 1)
198         {
199           memcpy (dst, src, src_len);
200           memset (&dst[src_len], ' ', dst_size - 1 - src_len);
201         }
202       else
203         memcpy (dst, src, dst_size - 1);
204       dst[dst_size - 1] = 0;
205     }
206 }
207
208 /* Copies SRC to DST, which is in a buffer DST_SIZE bytes long.
209    Truncates DST to DST_SIZE - 1 bytes, if necessary. */
210 void
211 str_copy_trunc (char *dst, size_t dst_size, const char *src)
212 {
213   size_t src_len = strlen (src);
214   assert (dst_size > 0);
215   if (src_len + 1 < dst_size)
216     memcpy (dst, src, src_len + 1);
217   else
218     {
219       memcpy (dst, src, dst_size - 1);
220       dst[dst_size - 1] = '\0';
221     }
222 }
223
224 /* Copies buffer SRC, of SRC_LEN bytes,
225    to DST, which is in a buffer DST_SIZE bytes long.
226    Truncates DST to DST_SIZE - 1 bytes, if necessary. */
227 void
228 str_copy_buf_trunc (char *dst, size_t dst_size,
229                     const char *src, size_t src_size)
230 {
231   size_t dst_len;
232   assert (dst_size > 0);
233
234   dst_len = src_size < dst_size ? src_size : dst_size - 1;
235   memcpy (dst, src, dst_len);
236   dst[dst_len] = '\0';
237 }
238
239 /* Converts each byte in S to uppercase.
240
241    This is suitable only for ASCII strings.  Use utf8_to_upper() for UTF-8
242    strings.*/
243 void
244 str_uppercase (char *s)
245 {
246   for (; *s != '\0'; s++)
247     *s = c_toupper ((unsigned char) *s);
248 }
249
250 /* Converts each byte in S to lowercase.
251
252    This is suitable only for ASCII strings.  Use utf8_to_lower() for UTF-8
253    strings.*/
254 void
255 str_lowercase (char *s)
256 {
257   for (; *s != '\0'; s++)
258     *s = c_tolower ((unsigned char) *s);
259 }
260
261 /* Converts NUMBER into a string in 26-adic notation in BUFFER,
262    which has room for SIZE bytes.  Uses uppercase if UPPERCASE is
263    true, otherwise lowercase, Returns true if successful, false
264    if NUMBER, plus a trailing null, is too large to fit in the
265    available space.
266
267    26-adic notation is "spreadsheet column numbering": 1 = A, 2 =
268    B, 3 = C, ... 26 = Z, 27 = AA, 28 = AB, 29 = AC, ...
269
270    26-adic notation is the special case of a k-adic numeration
271    system (aka bijective base-k numeration) with k=26.  In k-adic
272    numeration, the digits are {1, 2, 3, ..., k} (there is no
273    digit 0), and integer 0 is represented by the empty string.
274    For more information, see
275    http://en.wikipedia.org/wiki/Bijective_numeration. */
276 bool
277 str_format_26adic (unsigned long int number, bool uppercase,
278                    char buffer[], size_t size)
279 {
280   const char *alphabet
281     = uppercase ? "ABCDEFGHIJKLMNOPQRSTUVWXYZ" : "abcdefghijklmnopqrstuvwxyz";
282   size_t length = 0;
283
284   while (number-- > 0)
285     {
286       if (length >= size)
287         goto overflow;
288       buffer[length++] = alphabet[number % 26];
289       number /= 26;
290     }
291
292   if (length >= size)
293     goto overflow;
294   buffer[length] = '\0';
295
296   buf_reverse (buffer, length);
297   return true;
298
299 overflow:
300   if (length > 0)
301     buffer[0] = '\0';
302   return false;
303 }
304
305 /* Copies IN to buffer OUT with size OUT_SIZE, appending a null terminator.  If
306    IN is too long for OUT, or if IN contains a new-line, replaces the tail with
307    "...".
308
309    OUT_SIZE must be at least 16. */
310 void
311 str_ellipsize (struct substring in, char *out, size_t out_size)
312 {
313   assert (out_size >= 16);
314
315   size_t out_maxlen = out_size - 1;
316   if (in.length > out_maxlen - 3)
317     out_maxlen -= 3;
318
319   size_t out_len = 0;
320   while (out_len < in.length
321          && in.string[out_len] != '\n'
322          && in.string[out_len] != '\0'
323          && (in.string[out_len] != '\r'
324              || out_len + 1 >= in.length
325              || in.string[out_len + 1] != '\n'))
326     {
327       int mblen = u8_mblen (CHAR_CAST (const uint8_t *, in.string + out_len),
328                             in.length - out_len);
329       if (mblen < 0 || out_len + mblen > out_maxlen)
330         break;
331       out_len += mblen;
332     }
333
334   memcpy (out, in.string, out_len);
335   strcpy (&out[out_len], out_len < in.length ? "..." : "");
336 }
337
338 /* Sets the SIZE bytes starting at BLOCK to C,
339    and returns the byte following BLOCK. */
340 void *
341 mempset (void *block, int c, size_t size)
342 {
343   memset (block, c, size);
344   return (char *) block + size;
345 }
346 \f
347 /* Substrings. */
348
349 /* Returns a substring whose contents are the N bytes
350    starting at the (0-based) position START in SS. */
351 struct substring
352 ss_substr (struct substring ss, size_t start, size_t n)
353 {
354   if (start < ss.length)
355     return ss_buffer (ss.string + start, MIN (n, ss.length - start));
356   else
357     return ss_buffer (ss.string + ss.length, 0);
358 }
359
360 /* Returns a substring whose contents are the first N
361    bytes in SS. */
362 struct substring
363 ss_head (struct substring ss, size_t n)
364 {
365   return ss_buffer (ss.string, MIN (n, ss.length));
366 }
367
368 /* Returns a substring whose contents are the last N bytes
369    in SS. */
370 struct substring
371 ss_tail (struct substring ss, size_t n)
372 {
373   if (n < ss.length)
374     return ss_buffer (ss.string + (ss.length - n), n);
375   else
376     return ss;
377 }
378
379 /* Makes a malloc()'d, null-terminated copy of the contents of OLD
380    and stores it in NEW. */
381 void
382 ss_alloc_substring (struct substring *new, struct substring old)
383 {
384   new->string = xmemdup0 (old.string, old.length);
385   new->length = old.length;
386 }
387
388 /* Allocates room for a N-byte string in NEW. */
389 void
390 ss_alloc_uninit (struct substring *new, size_t n)
391 {
392   new->string = xmalloc (n);
393   new->length = n;
394 }
395
396 void
397 ss_realloc (struct substring *ss, size_t size)
398 {
399   ss->string = xrealloc (ss->string, size);
400 }
401
402 /* Makes a pool_alloc_unaligned()'d, null-terminated copy of the contents of
403    OLD in POOL, and stores it in NEW. */
404 void
405 ss_alloc_substring_pool (struct substring *new, struct substring old,
406                          struct pool *pool)
407 {
408   new->string = pool_alloc_unaligned (pool, old.length + 1);
409   new->length = old.length;
410   memcpy (new->string, old.string, old.length);
411   new->string[old.length] = '\0';
412 }
413
414 /* Allocates room for a N-byte string in NEW in POOL. */
415 void
416 ss_alloc_uninit_pool (struct substring *new, size_t n, struct pool *pool)
417 {
418   new->string = pool_alloc_unaligned (pool, n);
419   new->length = n;
420 }
421
422 /* Frees the string that SS points to. */
423 void
424 ss_dealloc (struct substring *ss)
425 {
426   free (ss->string);
427 }
428
429 /* Exchanges the contents of A and B. */
430 void
431 ss_swap (struct substring *a, struct substring *b)
432 {
433   struct substring tmp = *a;
434   *a = *b;
435   *b = tmp;
436 }
437
438 /* Truncates SS to at most N bytes in length. */
439 void
440 ss_truncate (struct substring *ss, size_t n)
441 {
442   if (ss->length > n)
443     ss->length = n;
444 }
445
446 /* Removes trailing bytes in TRIM_SET from SS.
447    Returns number of bytes removed. */
448 size_t
449 ss_rtrim (struct substring *ss, struct substring trim_set)
450 {
451   size_t n = 0;
452   while (n < ss->length
453          && ss_find_byte (trim_set,
454                           ss->string[ss->length - n - 1]) != SIZE_MAX)
455     n++;
456   ss->length -= n;
457   return n;
458 }
459
460 /* Removes leading bytes in TRIM_SET from SS.
461    Returns number of bytes removed. */
462 size_t
463 ss_ltrim (struct substring *ss, struct substring trim_set)
464 {
465   size_t n = ss_span (*ss, trim_set);
466   ss_advance (ss, n);
467   return n;
468 }
469
470 /* Trims leading and trailing bytes in TRIM_SET from SS. */
471 void
472 ss_trim (struct substring *ss, struct substring trim_set)
473 {
474   ss_ltrim (ss, trim_set);
475   ss_rtrim (ss, trim_set);
476 }
477
478 /* If the last byte in SS is C, removes it and returns true.
479    Otherwise, returns false without changing the string. */
480 bool
481 ss_chomp_byte (struct substring *ss, char c)
482 {
483   if (ss_last (*ss) == c)
484     {
485       ss->length--;
486       return true;
487     }
488   else
489     return false;
490 }
491
492 /* If SS ends with SUFFIX, removes it and returns true.
493    Otherwise, returns false without changing the string. */
494 bool
495 ss_chomp (struct substring *ss, struct substring suffix)
496 {
497   if (ss_ends_with (*ss, suffix))
498     {
499       ss->length -= suffix.length;
500       return true;
501     }
502   else
503     return false;
504 }
505
506 /* Divides SS into tokens separated by any of the DELIMITERS.
507    Each call replaces TOKEN by the next token in SS, or by an
508    empty string if no tokens remain.  Returns true if a token was
509    obtained, false otherwise.
510
511    Before the first call, initialize *SAVE_IDX to 0.  Do not
512    modify *SAVE_IDX between calls.
513
514    SS divides into exactly one more tokens than it contains
515    delimiters.  That is, a delimiter at the start or end of SS or
516    a pair of adjacent delimiters yields an empty token, and the
517    empty string contains a single token. */
518 bool
519 ss_separate (struct substring ss, struct substring delimiters,
520              size_t *save_idx, struct substring *token)
521 {
522   if (*save_idx <= ss_length (ss))
523     {
524       struct substring tmp = ss_substr (ss, *save_idx, SIZE_MAX);
525       size_t length = ss_cspan (tmp, delimiters);
526       *token = ss_head (tmp, length);
527       *save_idx += length + 1;
528       return true;
529     }
530   else
531     {
532       *token = ss_empty ();
533       return false;
534     }
535 }
536
537 /* Divides SS into tokens separated by any of the DELIMITERS,
538    merging adjacent delimiters so that the empty string is never
539    produced as a token.  Each call replaces TOKEN by the next
540    token in SS, or by an empty string if no tokens remain, and
541    then skips past the first delimiter following the token.
542    Returns true if a token was obtained, false otherwise.
543
544    Before the first call, initialize *SAVE_IDX to 0.  Do not
545    modify *SAVE_IDX between calls. */
546 bool
547 ss_tokenize (struct substring ss, struct substring delimiters,
548              size_t *save_idx, struct substring *token)
549 {
550   bool found_token;
551
552   ss_advance (&ss, *save_idx);
553   *save_idx += ss_ltrim (&ss, delimiters);
554   ss_get_bytes (&ss, ss_cspan (ss, delimiters), token);
555
556   found_token = ss_length (*token) > 0;
557   *save_idx += ss_length (*token) + (found_token?1:0);
558   return found_token;
559 }
560
561 /* Removes the first N bytes from SS. */
562 void
563 ss_advance (struct substring *ss, size_t n)
564 {
565   if (n > ss->length)
566     n = ss->length;
567   ss->string += n;
568   ss->length -= n;
569 }
570
571 /* If the first byte in SS is C, removes it and returns true.
572    Otherwise, returns false without changing the string. */
573 bool
574 ss_match_byte (struct substring *ss, char c)
575 {
576   if (ss_first (*ss) == c)
577     {
578       ss->string++;
579       ss->length--;
580       return true;
581     }
582   else
583     return false;
584 }
585
586 /* If the first byte in SS is in MATCH, removes it and
587    returns the byte that was removed.
588    Otherwise, returns EOF without changing the string. */
589 int
590 ss_match_byte_in (struct substring *ss, struct substring match)
591 {
592   int c = EOF;
593   if (ss->length > 0
594       && memchr (match.string, ss->string[0], match.length) != NULL)
595     {
596       c = ss->string[0];
597       ss->string++;
598       ss->length--;
599     }
600   return c;
601 }
602
603 /* If SS begins with TARGET, removes it and returns true.
604    Otherwise, returns false without changing SS. */
605 bool
606 ss_match_string (struct substring *ss, const struct substring target)
607 {
608   size_t length = ss_length (target);
609   if (ss_equals (ss_head (*ss, length), target))
610     {
611       ss_advance (ss, length);
612       return true;
613     }
614   else
615     return false;
616 }
617
618 /* If SS begins with TARGET, except possibly for case differences, removes it
619    and returns true.  Otherwise, returns false without changing SS. */
620 bool
621 ss_match_string_case (struct substring *ss, const struct substring target)
622 {
623   size_t length = ss_length (target);
624   if (ss_equals_case (ss_head (*ss, length), target))
625     {
626       ss_advance (ss, length);
627       return true;
628     }
629   else
630     return false;
631 }
632
633 /* Removes the first byte from SS and returns it.
634    If SS is empty, returns EOF without modifying SS. */
635 int
636 ss_get_byte (struct substring *ss)
637 {
638   int c = ss_first (*ss);
639   if (c != EOF)
640     {
641       ss->string++;
642       ss->length--;
643     }
644   return c;
645 }
646
647 /* Stores the prefix of SS up to the first DELIMITER in OUT (if
648    any).  Trims those same bytes from SS.  DELIMITER is
649    removed from SS but not made part of OUT.  Returns true if
650    DELIMITER was found (and removed), false otherwise. */
651 bool
652 ss_get_until (struct substring *ss, char delimiter, struct substring *out)
653 {
654   ss_get_bytes (ss, ss_cspan (*ss, ss_buffer (&delimiter, 1)), out);
655   return ss_match_byte (ss, delimiter);
656 }
657
658 /* Stores the first N bytes in SS in OUT (or fewer, if SS
659    is shorter than N bytes).  Trims the same bytes
660    from the beginning of SS.  Returns N. */
661 size_t
662 ss_get_bytes (struct substring *ss, size_t n, struct substring *out)
663 {
664   *out = ss_head (*ss, n);
665   ss_advance (ss, n);
666   return n;
667 }
668
669 /* Parses and removes an optionally signed decimal integer from
670    the beginning of SS.  Returns 0 if an error occurred,
671    otherwise the number of bytes removed from SS.  Stores
672    the integer's value into *VALUE. */
673 size_t
674 ss_get_long (struct substring *ss, long *value)
675 {
676   char tmp[64];
677   size_t length;
678
679   length = ss_span (*ss, ss_cstr ("+-"));
680   length += ss_span (ss_substr (*ss, length, SIZE_MAX), ss_cstr (CC_DIGITS));
681   if (length > 0 && length < sizeof tmp)
682     {
683       char *tail;
684
685       memcpy (tmp, ss_data (*ss), length);
686       tmp[length] = '\0';
687
688       *value = strtol (tmp, &tail, 10);
689       if (tail - tmp == length)
690         {
691           ss_advance (ss, length);
692           return length;
693         }
694     }
695   *value = 0;
696   return 0;
697 }
698
699 /* Returns true if SS is empty (has length 0 bytes),
700    false otherwise. */
701 bool
702 ss_is_empty (struct substring ss)
703 {
704   return ss.length == 0;
705 }
706
707 /* Returns the number of bytes in SS. */
708 size_t
709 ss_length (struct substring ss)
710 {
711   return ss.length;
712 }
713
714 /* Returns a pointer to the bytes in SS. */
715 char *
716 ss_data (struct substring ss)
717 {
718   return ss.string;
719 }
720
721 /* Returns a pointer just past the last byte in SS. */
722 char *
723 ss_end (struct substring ss)
724 {
725   return ss.string + ss.length;
726 }
727
728 /* Returns the byte in position IDX in SS, as a value in the
729    range of unsigned char.  Returns EOF if IDX is out of the
730    range of indexes for SS. */
731 int
732 ss_at (struct substring ss, size_t idx)
733 {
734   return idx < ss.length ? (unsigned char) ss.string[idx] : EOF;
735 }
736
737 /* Returns the first byte in SS as a value in the range of
738    unsigned char.  Returns EOF if SS is the empty string. */
739 int
740 ss_first (struct substring ss)
741 {
742   return ss_at (ss, 0);
743 }
744
745 /* Returns the last byte in SS as a value in the range of
746    unsigned char.  Returns EOF if SS is the empty string. */
747 int
748 ss_last (struct substring ss)
749 {
750   return ss.length > 0 ? (unsigned char) ss.string[ss.length - 1] : EOF;
751 }
752
753 /* Returns true if SS starts with PREFIX, false otherwise. */
754 bool
755 ss_starts_with (struct substring ss, struct substring prefix)
756 {
757   return (ss.length >= prefix.length
758           && !memcmp (ss.string, prefix.string, prefix.length));
759 }
760
761 /* Returns true if SS starts with PREFIX in any case, false otherwise. */
762 bool
763 ss_starts_with_case (struct substring ss, struct substring prefix)
764 {
765   return (ss.length >= prefix.length
766           && !memcasecmp (ss.string, prefix.string, prefix.length));
767 }
768
769 /* Returns true if SS ends with SUFFIX, false otherwise. */
770 bool
771 ss_ends_with (struct substring ss, struct substring suffix)
772 {
773   return (ss.length >= suffix.length
774           && !memcmp (&ss.string[ss.length - suffix.length], suffix.string,
775                       suffix.length));
776 }
777
778 /* Returns true if SS ends with SUFFIX in any case, false otherwise. */
779 bool
780 ss_ends_with_case (struct substring ss, struct substring suffix)
781 {
782   return (ss.length >= suffix.length
783           && !memcasecmp (&ss.string[ss.length - suffix.length], suffix.string,
784                           suffix.length));
785 }
786
787 /* Returns the number of contiguous bytes at the beginning
788    of SS that are in SKIP_SET. */
789 size_t
790 ss_span (struct substring ss, struct substring skip_set)
791 {
792   size_t i;
793   for (i = 0; i < ss.length; i++)
794     if (ss_find_byte (skip_set, ss.string[i]) == SIZE_MAX)
795       break;
796   return i;
797 }
798
799 /* Returns the number of contiguous bytes at the beginning
800    of SS that are not in SKIP_SET. */
801 size_t
802 ss_cspan (struct substring ss, struct substring stop_set)
803 {
804   size_t i;
805   for (i = 0; i < ss.length; i++)
806     if (ss_find_byte (stop_set, ss.string[i]) != SIZE_MAX)
807       break;
808   return i;
809 }
810
811 /* Returns the offset in SS of the first instance of C,
812    or SIZE_MAX if C does not occur in SS. */
813 size_t
814 ss_find_byte (struct substring ss, char c)
815 {
816   const char *p = memchr (ss.string, (int) c, ss.length);
817   return p != NULL ? p - ss.string : SIZE_MAX;
818 }
819
820 /* Returns the offset in HAYSTACK of the first instance of NEEDLE,
821    or SIZE_MAX if NEEDLE does not occur in HAYSTACK. */
822 size_t
823 ss_find_substring (struct substring haystack, struct substring needle)
824 {
825   const char *p = memmem (haystack.string, haystack.length,
826                           needle.string, needle.length);
827   return p != NULL ? p - haystack.string : SIZE_MAX;
828 }
829
830 /* Compares A and B and returns a strcmp()-type comparison
831    result. */
832 int
833 ss_compare (struct substring a, struct substring b)
834 {
835   int retval = memcmp (a.string, b.string, MIN (a.length, b.length));
836   if (retval == 0)
837     retval = a.length < b.length ? -1 : a.length > b.length;
838   return retval;
839 }
840
841 /* Compares A and B case-insensitively and returns a
842    strcmp()-type comparison result. */
843 int
844 ss_compare_case (struct substring a, struct substring b)
845 {
846   int retval = memcasecmp (a.string, b.string, MIN (a.length, b.length));
847   if (retval == 0)
848     retval = a.length < b.length ? -1 : a.length > b.length;
849   return retval;
850 }
851
852 /* Compares A and B and returns true if their contents are
853    identical, false otherwise. */
854 int
855 ss_equals (struct substring a, struct substring b)
856 {
857   return a.length == b.length && !memcmp (a.string, b.string, a.length);
858 }
859
860 /* Compares A and B and returns true if their contents are
861    identical except possibly for case differences, false
862    otherwise. */
863 int
864 ss_equals_case (struct substring a, struct substring b)
865 {
866   return a.length == b.length && !memcasecmp (a.string, b.string, a.length);
867 }
868
869 /* Returns the position in SS that the byte at P occupies.
870    P must point within SS or one past its end. */
871 size_t
872 ss_pointer_to_position (struct substring ss, const char *p)
873 {
874   size_t pos = p - ss.string;
875   assert (pos <= ss.length);
876   return pos;
877 }
878
879 /* Allocates and returns a null-terminated string that contains
880    SS. */
881 char *
882 ss_xstrdup (struct substring ss)
883 {
884   char *s = xmalloc (ss.length + 1);
885   memcpy (s, ss.string, ss.length);
886   s[ss.length] = '\0';
887   return s;
888 }
889 /* UTF-8. */
890
891 /* Returns the character represented by the UTF-8 sequence at the start of S.
892    The return value is either a Unicode code point in the range 0 to 0x10ffff,
893    or UINT32_MAX if S is empty. */
894 ucs4_t
895 ss_first_mb (struct substring s)
896 {
897   return ss_at_mb (s, 0);
898 }
899
900 /* Returns the number of bytes in the UTF-8 character at the beginning of S.
901
902    The return value is 0 if S is empty, otherwise between 1 and 4. */
903 int
904 ss_first_mblen (struct substring s)
905 {
906   return ss_at_mblen (s, 0);
907 }
908
909 /* Advances S past the UTF-8 character at its beginning.  Returns the Unicode
910    code point that was skipped (in the range 0 to 0x10ffff), or UINT32_MAX if S
911    was not modified because it was initially empty. */
912 ucs4_t
913 ss_get_mb (struct substring *s)
914 {
915   if (s->length > 0)
916     {
917       ucs4_t uc;
918       int n;
919
920       n = u8_mbtouc (&uc, CHAR_CAST (const uint8_t *, s->string), s->length);
921       s->string += n;
922       s->length -= n;
923       return uc;
924     }
925   else
926     return UINT32_MAX;
927 }
928
929 /* Returns the character represented by the UTF-8 sequence starting OFS bytes
930    into S.  The return value is either a Unicode code point in the range 0 to
931    0x10ffff, or UINT32_MAX if OFS is past the last byte in S.
932
933    (Returns 0xfffd if OFS points into the middle, not the beginning, of a UTF-8
934    sequence.)  */
935 ucs4_t
936 ss_at_mb (struct substring s, size_t ofs)
937 {
938   if (s.length > ofs)
939     {
940       ucs4_t uc;
941       u8_mbtouc (&uc, CHAR_CAST (const uint8_t *, s.string + ofs),
942                  s.length - ofs);
943       return uc;
944     }
945   else
946     return UINT32_MAX;
947 }
948
949 /* Returns the number of bytes represented by the UTF-8 sequence starting OFS
950    bytes into S.  The return value is 0 if OFS is past the last byte in S,
951    otherwise between 1 and 4. */
952 int
953 ss_at_mblen (struct substring s, size_t ofs)
954 {
955   if (s.length > ofs)
956     {
957       ucs4_t uc;
958       return u8_mbtouc (&uc, CHAR_CAST (const uint8_t *, s.string + ofs),
959                         s.length - ofs);
960     }
961   else
962     return 0;
963 }
964
965 size_t
966 ss_utf8_count_columns (struct substring s)
967 {
968   return utf8_count_columns (s.string, s.length);
969 }
970
971 /* Returns a substring of S starting at 0-based display column START and
972    running for N display columns. */
973 struct substring
974 ss_utf8_columns (struct substring s, size_t start, size_t n)
975 {
976   ss_advance (&s, utf8_columns_to_bytes (s.string, s.length, start));
977   s.length = utf8_columns_to_bytes (s.string, s.length, n);
978   return s;
979 }
980 \f
981 /* Initializes ST as an empty string. */
982 void
983 ds_init_empty (struct string *st)
984 {
985   st->ss = ss_empty ();
986   st->capacity = 0;
987 }
988
989 /* Initializes ST with initial contents S. */
990 void
991 ds_init_string (struct string *st, const struct string *s)
992 {
993   ds_init_substring (st, ds_ss (s));
994 }
995
996 /* Initializes ST with initial contents SS. */
997 void
998 ds_init_substring (struct string *st, struct substring ss)
999 {
1000   st->capacity = MAX (8, ss.length * 2);
1001   st->ss.string = xmalloc (st->capacity + 1);
1002   memcpy (st->ss.string, ss.string, ss.length);
1003   st->ss.length = ss.length;
1004 }
1005
1006 /* Initializes ST with initial contents S. */
1007 void
1008 ds_init_cstr (struct string *st, const char *s)
1009 {
1010   ds_init_substring (st, ss_cstr (s));
1011 }
1012
1013 /* Frees ST. */
1014 void
1015 ds_destroy (struct string *st)
1016 {
1017   if (st != NULL)
1018     {
1019       ss_dealloc (&st->ss);
1020       st->ss.string = NULL;
1021       st->ss.length = 0;
1022       st->capacity = 0;
1023     }
1024 }
1025
1026 /* Swaps the contents of strings A and B. */
1027 void
1028 ds_swap (struct string *a, struct string *b)
1029 {
1030   struct string tmp = *a;
1031   *a = *b;
1032   *b = tmp;
1033 }
1034
1035 /* Helper function for ds_register_pool. */
1036 static void
1037 free_string (void *st_)
1038 {
1039   struct string *st = st_;
1040   ds_destroy (st);
1041 }
1042
1043 /* Arranges for ST to be destroyed automatically as part of
1044    POOL. */
1045 void
1046 ds_register_pool (struct string *st, struct pool *pool)
1047 {
1048   pool_register (pool, free_string, st);
1049 }
1050
1051 /* Cancels the arrangement for ST to be destroyed automatically
1052    as part of POOL. */
1053 void
1054 ds_unregister_pool (struct string *st, struct pool *pool)
1055 {
1056   pool_unregister (pool, st);
1057 }
1058
1059 /* Copies SRC into DST.
1060    DST and SRC may be the same string. */
1061 void
1062 ds_assign_string (struct string *dst, const struct string *src)
1063 {
1064   ds_assign_substring (dst, ds_ss (src));
1065 }
1066
1067 /* Replaces DST by SS.
1068    SS may be a substring of DST. */
1069 void
1070 ds_assign_substring (struct string *dst, struct substring ss)
1071 {
1072   dst->ss.length = ss.length;
1073   ds_extend (dst, ss.length);
1074   memmove (dst->ss.string, ss.string, ss.length);
1075 }
1076
1077 /* Replaces DST by null-terminated string SRC.  SRC may overlap
1078    with DST. */
1079 void
1080 ds_assign_cstr (struct string *dst, const char *src)
1081 {
1082   ds_assign_substring (dst, ss_cstr (src));
1083 }
1084
1085 /* Truncates ST to zero length. */
1086 void
1087 ds_clear (struct string *st)
1088 {
1089   st->ss.length = 0;
1090 }
1091
1092 /* Returns a substring that contains ST. */
1093 struct substring
1094 ds_ss (const struct string *st)
1095 {
1096   return st->ss;
1097 }
1098
1099 /* Returns a substring that contains N bytes from ST
1100    starting at position START.
1101
1102    If START is greater than or equal to the length of ST, then
1103    the substring will be the empty string.  If START + N
1104    exceeds the length of ST, then the substring will only be
1105    ds_length(ST) - START bytes long. */
1106 struct substring
1107 ds_substr (const struct string *st, size_t start, size_t n)
1108 {
1109   return ss_substr (ds_ss (st), start, n);
1110 }
1111
1112 /* Returns a substring that contains the first N bytes in
1113    ST.  If N exceeds the length of ST, then the substring will
1114    contain all of ST. */
1115 struct substring
1116 ds_head (const struct string *st, size_t n)
1117 {
1118   return ss_head (ds_ss (st), n);
1119 }
1120
1121 /* Returns a substring that contains the last N bytes in
1122    ST.  If N exceeds the length of ST, then the substring will
1123    contain all of ST. */
1124 struct substring
1125 ds_tail (const struct string *st, size_t n)
1126 {
1127   return ss_tail (ds_ss (st), n);
1128 }
1129
1130 /* Ensures that ST can hold at least MIN_CAPACITY bytes plus a null
1131    terminator. */
1132 void
1133 ds_extend (struct string *st, size_t min_capacity)
1134 {
1135   if (min_capacity > st->capacity)
1136     {
1137       st->capacity *= 2;
1138       if (st->capacity < min_capacity)
1139         st->capacity = 2 * min_capacity;
1140
1141       st->ss.string = xrealloc (st->ss.string, st->capacity + 1);
1142     }
1143 }
1144
1145 /* Shrink ST to the minimum capacity need to contain its content. */
1146 void
1147 ds_shrink (struct string *st)
1148 {
1149   if (st->capacity != st->ss.length)
1150     {
1151       st->capacity = st->ss.length;
1152       st->ss.string = xrealloc (st->ss.string, st->capacity + 1);
1153     }
1154 }
1155
1156 /* Truncates ST to at most LENGTH bytes long. */
1157 void
1158 ds_truncate (struct string *st, size_t length)
1159 {
1160   ss_truncate (&st->ss, length);
1161 }
1162
1163 /* Removes trailing bytes in TRIM_SET from ST.
1164    Returns number of bytes removed. */
1165 size_t
1166 ds_rtrim (struct string *st, struct substring trim_set)
1167 {
1168   return ss_rtrim (&st->ss, trim_set);
1169 }
1170
1171 /* Removes leading bytes in TRIM_SET from ST.
1172    Returns number of bytes removed. */
1173 size_t
1174 ds_ltrim (struct string *st, struct substring trim_set)
1175 {
1176   size_t n = ds_span (st, trim_set);
1177   if (n > 0)
1178     ds_assign_substring (st, ds_substr (st, n, SIZE_MAX));
1179   return n;
1180 }
1181
1182 /* Trims leading and trailing bytes in TRIM_SET from ST.
1183    Returns number of bytes removed. */
1184 size_t
1185 ds_trim (struct string *st, struct substring trim_set)
1186 {
1187   size_t n = ds_rtrim (st, trim_set);
1188   return n + ds_ltrim (st, trim_set);
1189 }
1190
1191 /* If the last byte in ST is C, removes it and returns true.
1192    Otherwise, returns false without modifying ST. */
1193 bool
1194 ds_chomp_byte (struct string *st, char c)
1195 {
1196   return ss_chomp_byte (&st->ss, c);
1197 }
1198
1199 /* If ST ends with SUFFIX, removes it and returns true.
1200    Otherwise, returns false without modifying ST. */
1201 bool
1202 ds_chomp (struct string *st, struct substring suffix)
1203 {
1204   return ss_chomp (&st->ss, suffix);
1205 }
1206
1207 /* Divides ST into tokens separated by any of the DELIMITERS.
1208    Each call replaces TOKEN by the next token in ST, or by an
1209    empty string if no tokens remain.  Returns true if a token was
1210    obtained, false otherwise.
1211
1212    Before the first call, initialize *SAVE_IDX to 0.  Do not
1213    modify *SAVE_IDX between calls.
1214
1215    ST divides into exactly one more tokens than it contains
1216    delimiters.  That is, a delimiter at the start or end of ST or
1217    a pair of adjacent delimiters yields an empty token, and the
1218    empty string contains a single token. */
1219 bool
1220 ds_separate (const struct string *st, struct substring delimiters,
1221              size_t *save_idx, struct substring *token)
1222 {
1223   return ss_separate (ds_ss (st), delimiters, save_idx, token);
1224 }
1225
1226 /* Divides ST into tokens separated by any of the DELIMITERS,
1227    merging adjacent delimiters so that the empty string is never
1228    produced as a token.  Each call replaces TOKEN by the next
1229    token in ST, or by an empty string if no tokens remain.
1230    Returns true if a token was obtained, false otherwise.
1231
1232    Before the first call, initialize *SAVE_IDX to 0.  Do not
1233    modify *SAVE_IDX between calls. */
1234 bool
1235 ds_tokenize (const struct string *st, struct substring delimiters,
1236              size_t *save_idx, struct substring *token)
1237 {
1238   return ss_tokenize (ds_ss (st), delimiters, save_idx, token);
1239 }
1240
1241 /* Pad ST on the right with copies of PAD until ST is at least
1242    LENGTH bytes in size.  If ST is initially LENGTH
1243    bytes or longer, this is a no-op. */
1244 void
1245 ds_rpad (struct string *st, size_t length, char pad)
1246 {
1247   if (length > st->ss.length)
1248     ds_put_byte_multiple (st, pad, length - st->ss.length);
1249 }
1250
1251 /* Sets the length of ST to exactly NEW_LENGTH,
1252    either by truncating bytes from the end,
1253    or by padding on the right with PAD. */
1254 void
1255 ds_set_length (struct string *st, size_t new_length, char pad)
1256 {
1257   if (st->ss.length < new_length)
1258     ds_rpad (st, new_length, pad);
1259   else
1260     st->ss.length = new_length;
1261 }
1262
1263 /* Removes N bytes from ST starting at offset START. */
1264 void
1265 ds_remove (struct string *st, size_t start, size_t n)
1266 {
1267   if (n > 0 && start < st->ss.length)
1268     {
1269       if (st->ss.length - start <= n)
1270         {
1271           /* All bytes at or beyond START are deleted. */
1272           st->ss.length = start;
1273         }
1274       else
1275         {
1276           /* Some bytes remain and must be shifted into
1277              position. */
1278           memmove (st->ss.string + st->ss.length,
1279                    st->ss.string + st->ss.length + n,
1280                    st->ss.length - start - n);
1281           st->ss.length -= n;
1282         }
1283     }
1284   else
1285     {
1286       /* There are no bytes to delete or no bytes at or
1287          beyond START, hence deletion is a no-op. */
1288     }
1289 }
1290
1291 /* Returns true if ST is empty, false otherwise. */
1292 bool
1293 ds_is_empty (const struct string *st)
1294 {
1295   return ss_is_empty (st->ss);
1296 }
1297
1298 /* Returns the length of ST. */
1299 size_t
1300 ds_length (const struct string *st)
1301 {
1302   return ss_length (ds_ss (st));
1303 }
1304
1305 /* Returns the string data inside ST. */
1306 char *
1307 ds_data (const struct string *st)
1308 {
1309   return ss_data (ds_ss (st));
1310 }
1311
1312 /* Returns a pointer to the null terminator ST.
1313    This might not be an actual null byte unless ds_c_str() has
1314    been called since the last modification to ST. */
1315 char *
1316 ds_end (const struct string *st)
1317 {
1318   return ss_end (ds_ss (st));
1319 }
1320
1321 /* Returns the byte in position IDX in ST, as a value in the
1322    range of unsigned char.  Returns EOF if IDX is out of the
1323    range of indexes for ST. */
1324 int
1325 ds_at (const struct string *st, size_t idx)
1326 {
1327   return ss_at (ds_ss (st), idx);
1328 }
1329
1330 /* Returns the first byte in ST as a value in the range of
1331    unsigned char.  Returns EOF if ST is the empty string. */
1332 int
1333 ds_first (const struct string *st)
1334 {
1335   return ss_first (ds_ss (st));
1336 }
1337
1338 /* Returns the last byte in ST as a value in the range of
1339    unsigned char.  Returns EOF if ST is the empty string. */
1340 int
1341 ds_last (const struct string *st)
1342 {
1343   return ss_last (ds_ss (st));
1344 }
1345
1346 /* Returns true if ST ends with SUFFIX, false otherwise. */
1347 bool
1348 ds_ends_with (const struct string *st, struct substring suffix)
1349 {
1350   return ss_ends_with (st->ss, suffix);
1351 }
1352
1353 /* Returns the number of consecutive bytes at the beginning
1354    of ST that are in SKIP_SET. */
1355 size_t
1356 ds_span (const struct string *st, struct substring skip_set)
1357 {
1358   return ss_span (ds_ss (st), skip_set);
1359 }
1360
1361 /* Returns the number of consecutive bytes at the beginning
1362    of ST that are not in STOP_SET.  */
1363 size_t
1364 ds_cspan (const struct string *st, struct substring stop_set)
1365 {
1366   return ss_cspan (ds_ss (st), stop_set);
1367 }
1368
1369 /* Returns the position of the first occurrence of byte C in
1370    ST at or after position OFS, or SIZE_MAX if there is no such
1371    occurrence. */
1372 size_t
1373 ds_find_byte (const struct string *st, char c)
1374 {
1375   return ss_find_byte (ds_ss (st), c);
1376 }
1377
1378 /* Compares A and B and returns a strcmp()-type comparison
1379    result. */
1380 int
1381 ds_compare (const struct string *a, const struct string *b)
1382 {
1383   return ss_compare (ds_ss (a), ds_ss (b));
1384 }
1385
1386 /* Returns the position in ST that the byte at P occupies.
1387    P must point within ST or one past its end. */
1388 size_t
1389 ds_pointer_to_position (const struct string *st, const char *p)
1390 {
1391   return ss_pointer_to_position (ds_ss (st), p);
1392 }
1393
1394 /* Allocates and returns a null-terminated string that contains
1395    ST. */
1396 char *
1397 ds_xstrdup (const struct string *st)
1398 {
1399   return ss_xstrdup (ds_ss (st));
1400 }
1401
1402 /* Returns the allocation size of ST. */
1403 size_t
1404 ds_capacity (const struct string *st)
1405 {
1406   return st->capacity;
1407 }
1408
1409 /* Returns the value of ST as a null-terminated string. */
1410 char *
1411 ds_cstr (const struct string *st_)
1412 {
1413   struct string *st = CONST_CAST (struct string *, st_);
1414   if (st->ss.string == NULL)
1415     ds_extend (st, 1);
1416   st->ss.string[st->ss.length] = '\0';
1417   return st->ss.string;
1418 }
1419
1420 /* Returns the value of ST as a null-terminated string and then
1421    reinitialized ST as an empty string.  The caller must free the
1422    returned string with free(). */
1423 char *
1424 ds_steal_cstr (struct string *st)
1425 {
1426   char *s = ds_cstr (st);
1427   ds_init_empty (st);
1428   return s;
1429 }
1430
1431 /* Reads bytes from STREAM and appends them to ST, stopping
1432    after MAX_LENGTH bytes, after appending a newline, or
1433    after an I/O error or end of file was encountered, whichever
1434    comes first.  Returns true if at least one byte was added
1435    to ST, false if no bytes were read before an I/O error or
1436    end of file (or if MAX_LENGTH was 0).
1437
1438    This function treats LF and CR LF sequences as new-line,
1439    translating each of them to a single '\n' in ST. */
1440 bool
1441 ds_read_line (struct string *st, FILE *stream, size_t max_length)
1442 {
1443   size_t length;
1444
1445   for (length = 0; length < max_length; length++)
1446     {
1447       int c = getc (stream);
1448       switch (c)
1449         {
1450         case EOF:
1451           return length > 0;
1452
1453         case '\n':
1454           ds_put_byte (st, c);
1455           return true;
1456
1457         case '\r':
1458           c = getc (stream);
1459           if (c == '\n')
1460             {
1461               /* CR followed by LF is special: translate to \n. */
1462               ds_put_byte (st, '\n');
1463               return true;
1464             }
1465           else
1466             {
1467               /* CR followed by anything else is just CR. */
1468               ds_put_byte (st, '\r');
1469               if (c == EOF)
1470                 return true;
1471               ungetc (c, stream);
1472             }
1473           break;
1474
1475         default:
1476           ds_put_byte (st, c);
1477         }
1478     }
1479
1480   return length > 0;
1481 }
1482
1483 /* Removes a comment introduced by `#' from ST,
1484    ignoring occurrences inside quoted strings. */
1485 static void
1486 remove_comment (struct string *st)
1487 {
1488   char *cp;
1489   int quote = 0;
1490
1491   for (cp = ds_data (st); cp < ds_end (st); cp++)
1492     if (quote)
1493       {
1494         if (*cp == quote)
1495           quote = 0;
1496         else if (*cp == '\\')
1497           cp++;
1498       }
1499     else if (*cp == '\'' || *cp == '"')
1500       quote = *cp;
1501     else if (*cp == '#')
1502       {
1503         ds_truncate (st, cp - ds_cstr (st));
1504         break;
1505       }
1506 }
1507
1508 /* Reads a line from STREAM into ST, then preprocesses as follows:
1509
1510    - Splices lines terminated with `\'.
1511
1512    - Deletes comments introduced by `#' outside of single or double
1513      quotes.
1514
1515    - Deletes trailing white space.
1516
1517    Returns true if a line was successfully read, false on
1518    failure.  If LINE_NUMBER is non-null, then *LINE_NUMBER is
1519    incremented by the number of lines read. */
1520 bool
1521 ds_read_config_line (struct string *st, int *line_number, FILE *stream)
1522 {
1523   ds_clear (st);
1524   do
1525     {
1526       if (!ds_read_line (st, stream, SIZE_MAX))
1527         return false;
1528       (*line_number)++;
1529       ds_rtrim (st, ss_cstr (CC_SPACES));
1530     }
1531   while (ds_chomp_byte (st, '\\'));
1532
1533   remove_comment (st);
1534   return true;
1535 }
1536
1537 /* Attempts to read SIZE * N bytes from STREAM and append them
1538    to ST.
1539    Returns true if all the requested data was read, false otherwise. */
1540 bool
1541 ds_read_stream (struct string *st, size_t size, size_t n, FILE *stream)
1542 {
1543   if (size != 0)
1544     {
1545       size_t try_bytes = xtimes (n, size);
1546       if (size_in_bounds_p (xsum (ds_length (st), try_bytes)))
1547         {
1548           char *buffer = ds_put_uninit (st, try_bytes);
1549           size_t got_bytes = fread (buffer, 1, try_bytes, stream);
1550           ds_truncate (st, ds_length (st) - (try_bytes - got_bytes));
1551           return got_bytes == try_bytes;
1552         }
1553       else
1554         {
1555           errno = ENOMEM;
1556           return false;
1557         }
1558     }
1559   else
1560     return true;
1561 }
1562
1563 /* Concatenates S onto ST. */
1564 void
1565 ds_put_cstr (struct string *st, const char *s)
1566 {
1567   if (s != NULL)
1568     ds_put_substring (st, ss_cstr (s));
1569 }
1570
1571 /* Concatenates SS to ST. */
1572 void
1573 ds_put_substring (struct string *st, struct substring ss)
1574 {
1575   if (ss.length)
1576     memcpy (ds_put_uninit (st, ss_length (ss)), ss_data (ss), ss_length (ss));
1577 }
1578
1579 /* Returns ds_end(ST) and THEN increases the length by INCR. */
1580 char *
1581 ds_put_uninit (struct string *st, size_t incr)
1582 {
1583   char *end;
1584   ds_extend (st, ds_length (st) + incr);
1585   end = ds_end (st);
1586   st->ss.length += incr;
1587   return end;
1588 }
1589
1590 /* Moves the bytes in ST following offset OFS + OLD_LEN in ST to offset OFS +
1591    NEW_LEN and returns the byte at offset OFS.  The first min(OLD_LEN, NEW_LEN)
1592    bytes at the returned position are unchanged; if NEW_LEN > OLD_LEN then the
1593    following NEW_LEN - OLD_LEN bytes are initially indeterminate.
1594
1595    The intention is that the caller should write NEW_LEN bytes at the returned
1596    position, to effectively replace the OLD_LEN bytes previously at that
1597    position. */
1598 char *
1599 ds_splice_uninit (struct string *st,
1600                   size_t ofs, size_t old_len, size_t new_len)
1601 {
1602   if (new_len != old_len)
1603     {
1604       if (new_len > old_len)
1605         ds_extend (st, ds_length (st) + (new_len - old_len));
1606
1607       assert (ds_length (st) >= ofs + old_len);
1608
1609       memmove (ds_data (st) + (ofs + new_len),
1610                ds_data (st) + (ofs + old_len),
1611                ds_length (st) - (ofs + old_len));
1612       st->ss.length += new_len - old_len;
1613     }
1614   return ds_data (st) + ofs;
1615 }
1616
1617 /* Formats FORMAT as a printf string and appends the result to ST. */
1618 void
1619 ds_put_format (struct string *st, const char *format, ...)
1620 {
1621   va_list args;
1622
1623   va_start (args, format);
1624   ds_put_vformat (st, format, args);
1625   va_end (args);
1626 }
1627
1628 /* Formats FORMAT as a printf string as if in the C locale and appends the result to ST. */
1629 void
1630 ds_put_c_format (struct string *st, const char *format, ...)
1631 {
1632   va_list args;
1633
1634   va_start (args, format);
1635   ds_put_c_vformat (st, format, args);
1636   va_end (args);
1637 }
1638
1639 /* Formats FORMAT as a printf string and appends the result to ST. */
1640 void
1641 ds_put_vformat (struct string *st, const char *format, va_list args_)
1642 {
1643   int avail, needed;
1644   va_list args;
1645
1646   va_copy (args, args_);
1647   avail = st->ss.string != NULL ? st->capacity - st->ss.length + 1 : 0;
1648   needed = vsnprintf (st->ss.string + st->ss.length, avail, format, args);
1649   va_end (args);
1650
1651   if (needed >= avail)
1652     {
1653       va_copy (args, args_);
1654       vsnprintf (ds_put_uninit (st, needed), needed + 1, format, args);
1655       va_end (args);
1656     }
1657   else
1658     {
1659       /* Some old libc's returned -1 when the destination string
1660          was too short. */
1661       while (needed == -1)
1662         {
1663           ds_extend (st, (st->capacity + 1) * 2);
1664           avail = st->capacity - st->ss.length + 1;
1665
1666           va_copy (args, args_);
1667           needed = vsnprintf (ds_end (st), avail, format, args);
1668           va_end (args);
1669         }
1670       st->ss.length += needed;
1671     }
1672 }
1673
1674 /* Formats FORMAT as a printf string, as if in the C locale,
1675    and appends the result to ST. */
1676 void
1677 ds_put_c_vformat (struct string *st, const char *format, va_list args)
1678 {
1679   char buf[128];
1680   size_t len = sizeof buf;
1681   char *output = c_vasnprintf (buf, &len, format, args);
1682   if (output)
1683     {
1684       ds_put_cstr (st, output);
1685       if (output != buf)
1686         free (output);
1687     }
1688 }
1689
1690 /* Appends byte CH to ST. */
1691 void
1692 ds_put_byte (struct string *st, int ch)
1693 {
1694   ds_put_uninit (st, 1)[0] = ch;
1695 }
1696
1697 /* Appends N copies of byte CH to ST. */
1698 void
1699 ds_put_byte_multiple (struct string *st, int ch, size_t n)
1700 {
1701   memset (ds_put_uninit (st, n), ch, n);
1702 }
1703
1704 /* Appends Unicode code point UC to ST in UTF-8 encoding. */
1705 void
1706 ds_put_unichar (struct string *st, ucs4_t uc)
1707 {
1708   ds_extend (st, ds_length (st) + 6);
1709   st->ss.length += u8_uctomb (CHAR_CAST (uint8_t *, ds_end (st)), uc, 6);
1710 }
1711
1712 /* Appends N copies of S to ST. */
1713 void
1714 ds_put_substring_multiple (struct string *dst, struct substring src, size_t n)
1715 {
1716   char *p = ds_put_uninit (dst, n * src.length);
1717   for (size_t i = 0; i < n; i++)
1718     {
1719       memcpy (p, src.string, src.length);
1720       p += src.length;
1721     }
1722 }
1723
1724 /* If relocation has been enabled, replace ST,
1725    with its relocated version */
1726 void
1727 ds_relocate (struct string *st)
1728 {
1729   const char *orig = ds_cstr (st);
1730   const char *rel = relocate (orig);
1731
1732   if (orig != rel)
1733     {
1734       ds_clear (st);
1735       ds_put_cstr (st, rel);
1736       /* The documentation for relocate says that casting away const
1737         and then freeing is appropriate ... */
1738       free (CONST_CAST (char *, rel));
1739     }
1740 }
1741
1742
1743 \f
1744
1745 /* Operations on uint8_t "strings" */
1746
1747 /* Copies buffer SRC, of SRC_SIZE bytes, to DST, of DST_SIZE bytes.
1748    DST is truncated to DST_SIZE bytes or padded on the right with
1749    copies of PAD as needed. */
1750 void
1751 u8_buf_copy_rpad (uint8_t *dst, size_t dst_size,
1752                   const uint8_t *src, size_t src_size,
1753                   char pad)
1754 {
1755   if (src_size >= dst_size)
1756     memmove (dst, src, dst_size);
1757   else
1758     {
1759       memmove (dst, src, src_size);
1760       memset (&dst[src_size], pad, dst_size - src_size);
1761     }
1762 }