contrib/bmake/str.c

   1 /*      $NetBSD: str.c,v 1.93 2022/06/11 09:24:07 rillig Exp $  */
   2
   3 /*
   4  * Copyright (c) 1988, 1989, 1990, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Adam de Boor.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 /*
  36  * Copyright (c) 1989 by Berkeley Softworks
  37  * All rights reserved.
  38  *
  39  * This code is derived from software contributed to Berkeley by
  40  * Adam de Boor.
  41  *
  42  * Redistribution and use in source and binary forms, with or without
  43  * modification, are permitted provided that the following conditions
  44  * are met:
  45  * 1. Redistributions of source code must retain the above copyright
  46  *    notice, this list of conditions and the following disclaimer.
  47  * 2. Redistributions in binary form must reproduce the above copyright
  48  *    notice, this list of conditions and the following disclaimer in the
  49  *    documentation and/or other materials provided with the distribution.
  50  * 3. All advertising materials mentioning features or use of this software
  51  *    must display the following acknowledgement:
  52  *      This product includes software developed by the University of
  53  *      California, Berkeley and its contributors.
  54  * 4. Neither the name of the University nor the names of its contributors
  55  *    may be used to endorse or promote products derived from this software
  56  *    without specific prior written permission.
  57  *
  58  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  59  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  60  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  61  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  62  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  63  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  64  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  65  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  66  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  67  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  68  * SUCH DAMAGE.
  69  */
  70
  71 #include "make.h"
  72
  73 /*      "@(#)str.c      5.8 (Berkeley) 6/1/90"  */
  74 MAKE_RCSID("$NetBSD: str.c,v 1.93 2022/06/11 09:24:07 rillig Exp $");
  75
  76
  77 static HashTable interned_strings;
  78
  79
  80 /* Return the concatenation of s1 and s2, freshly allocated. */
  81 char *
  82 str_concat2(const char *s1, const char *s2)
  83 {
  84         size_t len1 = strlen(s1);
  85         size_t len2 = strlen(s2);
  86         char *result = bmake_malloc(len1 + len2 + 1);
  87         memcpy(result, s1, len1);
  88         memcpy(result + len1, s2, len2 + 1);
  89         return result;
  90 }
  91
  92 /* Return the concatenation of s1, s2 and s3, freshly allocated. */
  93 char *
  94 str_concat3(const char *s1, const char *s2, const char *s3)
  95 {
  96         size_t len1 = strlen(s1);
  97         size_t len2 = strlen(s2);
  98         size_t len3 = strlen(s3);
  99         char *result = bmake_malloc(len1 + len2 + len3 + 1);
 100         memcpy(result, s1, len1);
 101         memcpy(result + len1, s2, len2);
 102         memcpy(result + len1 + len2, s3, len3 + 1);
 103         return result;
 104 }
 105
 106 /*
 107  * Fracture a string into an array of words (as delineated by tabs or spaces)
 108  * taking quotation marks into account.
 109  *
 110  * If expand is true, quotes are removed and escape sequences such as \r, \t,
 111  * etc... are expanded. In this case, return NULL on parse errors.
 112  *
 113  * Returns the fractured words, which must be freed later using Words_Free,
 114  * unless the returned Words.words was NULL.
 115  */
 116 SubstringWords
 117 Substring_Words(const char *str, bool expand)
 118 {
 119         size_t str_len;
 120         char *words_buf;
 121         size_t words_cap;
 122         Substring *words;
 123         size_t words_len;
 124         char inquote;
 125         char *word_start;
 126         char *word_end;
 127         const char *str_p;
 128
 129         /* XXX: why only hspace, not whitespace? */
 130         cpp_skip_hspace(&str);  /* skip leading space chars. */
 131
 132         /* words_buf holds the words, separated by '\0'. */
 133         str_len = strlen(str);
 134         words_buf = bmake_malloc(str_len + 1);
 135
 136         words_cap = str_len / 5 > 50 ? str_len / 5 : 50;
 137         words = bmake_malloc((words_cap + 1) * sizeof(words[0]));
 138
 139         /*
 140          * copy the string; at the same time, parse backslashes,
 141          * quotes and build the word list.
 142          */
 143         words_len = 0;
 144         inquote = '\0';
 145         word_start = words_buf;
 146         word_end = words_buf;
 147         for (str_p = str;; str_p++) {
 148                 char ch = *str_p;
 149                 switch (ch) {
 150                 case '"':
 151                 case '\'':
 152                         if (inquote != '\0') {
 153                                 if (inquote == ch)
 154                                         inquote = '\0';
 155                                 else
 156                                         break;
 157                         } else {
 158                                 inquote = ch;
 159                                 /* Don't miss "" or '' */
 160                                 if (word_start == NULL && str_p[1] == inquote) {
 161                                         if (!expand) {
 162                                                 word_start = word_end;
 163                                                 *word_end++ = ch;
 164                                         } else
 165                                                 word_start = word_end + 1;
 166                                         str_p++;
 167                                         inquote = '\0';
 168                                         break;
 169                                 }
 170                         }
 171                         if (!expand) {
 172                                 if (word_start == NULL)
 173                                         word_start = word_end;
 174                                 *word_end++ = ch;
 175                         }
 176                         continue;
 177                 case ' ':
 178                 case '\t':
 179                 case '\n':
 180                         if (inquote != '\0')
 181                                 break;
 182                         if (word_start == NULL)
 183                                 continue;
 184                         /* FALLTHROUGH */
 185                 case '\0':
 186                         /*
 187                          * end of a token -- make sure there's enough words
 188                          * space and save off a pointer.
 189                          */
 190                         if (word_start == NULL)
 191                                 goto done;
 192
 193                         *word_end++ = '\0';
 194                         if (words_len == words_cap) {
 195                                 words_cap *= 2;
 196                                 words = bmake_realloc(words,
 197                                     (words_cap + 1) * sizeof(words[0]));
 198                         }
 199                         words[words_len++] =
 200                             Substring_Init(word_start, word_end - 1);
 201                         word_start = NULL;
 202                         if (ch == '\n' || ch == '\0') {
 203                                 if (expand && inquote != '\0') {
 204                                         SubstringWords res;
 205
 206                                         free(words);
 207                                         free(words_buf);
 208
 209                                         res.words = NULL;
 210                                         res.len = 0;
 211                                         res.freeIt = NULL;
 212                                         return res;
 213                                 }
 214                                 goto done;
 215                         }
 216                         continue;
 217                 case '\\':
 218                         if (!expand) {
 219                                 if (word_start == NULL)
 220                                         word_start = word_end;
 221                                 *word_end++ = '\\';
 222                                 /* catch lonely '\' at end of string */
 223                                 if (str_p[1] == '\0')
 224                                         continue;
 225                                 ch = *++str_p;
 226                                 break;
 227                         }
 228
 229                         switch (ch = *++str_p) {
 230                         case '\0':
 231                         case '\n':
 232                                 /* hmmm; fix it up as best we can */
 233                                 ch = '\\';
 234                                 str_p--;
 235                                 break;
 236                         case 'b':
 237                                 ch = '\b';
 238                                 break;
 239                         case 'f':
 240                                 ch = '\f';
 241                                 break;
 242                         case 'n':
 243                                 ch = '\n';
 244                                 break;
 245                         case 'r':
 246                                 ch = '\r';
 247                                 break;
 248                         case 't':
 249                                 ch = '\t';
 250                                 break;
 251                         }
 252                         break;
 253                 }
 254                 if (word_start == NULL)
 255                         word_start = word_end;
 256                 *word_end++ = ch;
 257         }
 258 done:
 259         words[words_len] = Substring_Init(NULL, NULL);  /* useful for argv */
 260
 261         {
 262                 SubstringWords result;
 263
 264                 result.words = words;
 265                 result.len = words_len;
 266                 result.freeIt = words_buf;
 267                 return result;
 268         }
 269 }
 270
 271 Words
 272 Str_Words(const char *str, bool expand)
 273 {
 274         SubstringWords swords;
 275         Words words;
 276         size_t i;
 277
 278         swords = Substring_Words(str, expand);
 279         if (swords.words == NULL) {
 280                 words.words = NULL;
 281                 words.len = 0;
 282                 words.freeIt = NULL;
 283                 return words;
 284         }
 285
 286         words.words = bmake_malloc((swords.len + 1) * sizeof(words.words[0]));
 287         words.len = swords.len;
 288         words.freeIt = swords.freeIt;
 289         for (i = 0; i < swords.len + 1; i++)
 290                 words.words[i] = UNCONST(swords.words[i].start);
 291         free(swords.words);
 292         return words;
 293 }
 294
 295 /*
 296  * XXX: In the extreme edge case that one of the characters is from the basic
 297  * execution character set and the other isn't, the result of the comparison
 298  * differs depending on whether plain char is signed or unsigned.
 299  *
 300  * An example is the character range from \xE4 to 'a', where \xE4 may come
 301  * from U+00E4 'Latin small letter A with diaeresis'.
 302  *
 303  * If char is signed, \xE4 evaluates to -28, the first half of the condition
 304  * becomes -28 <= '0' && '0' <= 'a', which evaluates to true.
 305  *
 306  * If char is unsigned, \xE4 evaluates to 228, the second half of the
 307  * condition becomes 'a' <= '0' && '0' <= 228, which evaluates to false.
 308  */
 309 static bool
 310 in_range(char e1, char c, char e2)
 311 {
 312         return (e1 <= c && c <= e2) || (e2 <= c && c <= e1);
 313 }
 314
 315 /*
 316  * Str_Match -- Test if a string matches a pattern like "*.[ch]".
 317  * The following special characters are known *?\[] (as in fnmatch(3)).
 318  *
 319  * XXX: this function does not detect or report malformed patterns.
 320  *
 321  * See varmod-match.mk for examples and edge cases.
 322  */
 323 bool
 324 Str_Match(const char *str, const char *pat)
 325 {
 326         for (; *pat != '\0'; pat++, str++) {
 327                 if (*pat == '*') {      /* match any substring */
 328                         pat++;
 329                         while (*pat == '*')
 330                                 pat++;
 331                         if (*pat == '\0')
 332                                 return true;
 333                         for (; *str != '\0'; str++)
 334                                 if (Str_Match(str, pat))
 335                                         return true;
 336                         return false;
 337                 }
 338
 339                 if (*str == '\0')
 340                         return false;
 341
 342                 if (*pat == '?')        /* match any single character */
 343                         continue;
 344
 345                 if (*pat == '[') {      /* match a character from a list */
 346                         bool neg = pat[1] == '^';
 347                         pat += neg ? 2 : 1;
 348
 349                         for (;;) {
 350                                 if (*pat == ']' || *pat == '\0') {
 351                                         if (neg)
 352                                                 break;
 353                                         return false;
 354                                 }
 355                                 if (*pat == *str)
 356                                         break;
 357                                 if (pat[1] == '-') {
 358                                         if (pat[2] == '\0')
 359                                                 return neg;
 360                                         if (in_range(pat[0], *str, pat[2]))
 361                                                 break;
 362                                         pat += 2;
 363                                 }
 364                                 pat++;
 365                         }
 366                         if (neg && *pat != ']' && *pat != '\0')
 367                                 return false;
 368                         while (*pat != ']' && *pat != '\0')
 369                                 pat++;
 370                         if (*pat == '\0')
 371                                 pat--;
 372                         continue;
 373                 }
 374
 375                 if (*pat == '\\')       /* match the next character exactly */
 376                         pat++;
 377
 378                 if (*pat != *str)
 379                         return false;
 380         }
 381         return *str == '\0';
 382 }
 383
 384 void
 385 Str_Intern_Init(void)
 386 {
 387         HashTable_Init(&interned_strings);
 388 }
 389
 390 void
 391 Str_Intern_End(void)
 392 {
 393 #ifdef CLEANUP
 394         HashTable_Done(&interned_strings);
 395 #endif
 396 }
 397
 398 /* Return a canonical instance of str, with unlimited lifetime. */
 399 const char *
 400 Str_Intern(const char *str)
 401 {
 402         return HashTable_CreateEntry(&interned_strings, str, NULL)->key;
 403 }