contrib/bmake/str.c

   1 /*      $NetBSD: str.c,v 1.85 2021/05/30 21:16:54 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.85 2021/05/30 21:16:54 rillig Exp $");
  75
  76 /* Return the concatenation of s1 and s2, freshly allocated. */
  77 char *
  78 str_concat2(const char *s1, const char *s2)
  79 {
  80         size_t len1 = strlen(s1);
  81         size_t len2 = strlen(s2);
  82         char *result = bmake_malloc(len1 + len2 + 1);
  83         memcpy(result, s1, len1);
  84         memcpy(result + len1, s2, len2 + 1);
  85         return result;
  86 }
  87
  88 /* Return the concatenation of s1, s2 and s3, freshly allocated. */
  89 char *
  90 str_concat3(const char *s1, const char *s2, const char *s3)
  91 {
  92         size_t len1 = strlen(s1);
  93         size_t len2 = strlen(s2);
  94         size_t len3 = strlen(s3);
  95         char *result = bmake_malloc(len1 + len2 + len3 + 1);
  96         memcpy(result, s1, len1);
  97         memcpy(result + len1, s2, len2);
  98         memcpy(result + len1 + len2, s3, len3 + 1);
  99         return result;
 100 }
 101
 102 /*
 103  * Fracture a string into an array of words (as delineated by tabs or spaces)
 104  * taking quotation marks into account.
 105  *
 106  * If expand is true, quotes are removed and escape sequences such as \r, \t,
 107  * etc... are expanded. In this case, return NULL on parse errors.
 108  *
 109  * Returns the fractured words, which must be freed later using Words_Free,
 110  * unless the returned Words.words was NULL.
 111  */
 112 SubstringWords
 113 Substring_Words(const char *str, bool expand)
 114 {
 115         size_t str_len;
 116         char *words_buf;
 117         size_t words_cap;
 118         Substring *words;
 119         size_t words_len;
 120         char inquote;
 121         char *word_start;
 122         char *word_end;
 123         const char *str_p;
 124
 125         /* XXX: why only hspace, not whitespace? */
 126         cpp_skip_hspace(&str);  /* skip leading space chars. */
 127
 128         /* words_buf holds the words, separated by '\0'. */
 129         str_len = strlen(str);
 130         words_buf = bmake_malloc(str_len + 1);
 131
 132         words_cap = str_len / 5 > 50 ? str_len / 5 : 50;
 133         words = bmake_malloc((words_cap + 1) * sizeof(words[0]));
 134
 135         /*
 136          * copy the string; at the same time, parse backslashes,
 137          * quotes and build the word list.
 138          */
 139         words_len = 0;
 140         inquote = '\0';
 141         word_start = words_buf;
 142         word_end = words_buf;
 143         for (str_p = str;; str_p++) {
 144                 char ch = *str_p;
 145                 switch (ch) {
 146                 case '"':
 147                 case '\'':
 148                         if (inquote != '\0') {
 149                                 if (inquote == ch)
 150                                         inquote = '\0';
 151                                 else
 152                                         break;
 153                         } else {
 154                                 inquote = ch;
 155                                 /* Don't miss "" or '' */
 156                                 if (word_start == NULL && str_p[1] == inquote) {
 157                                         if (!expand) {
 158                                                 word_start = word_end;
 159                                                 *word_end++ = ch;
 160                                         } else
 161                                                 word_start = word_end + 1;
 162                                         str_p++;
 163                                         inquote = '\0';
 164                                         break;
 165                                 }
 166                         }
 167                         if (!expand) {
 168                                 if (word_start == NULL)
 169                                         word_start = word_end;
 170                                 *word_end++ = ch;
 171                         }
 172                         continue;
 173                 case ' ':
 174                 case '\t':
 175                 case '\n':
 176                         if (inquote != '\0')
 177                                 break;
 178                         if (word_start == NULL)
 179                                 continue;
 180                         /* FALLTHROUGH */
 181                 case '\0':
 182                         /*
 183                          * end of a token -- make sure there's enough words
 184                          * space and save off a pointer.
 185                          */
 186                         if (word_start == NULL)
 187                                 goto done;
 188
 189                         *word_end++ = '\0';
 190                         if (words_len == words_cap) {
 191                                 size_t new_size;
 192                                 words_cap *= 2;
 193                                 new_size = (words_cap + 1) * sizeof(words[0]);
 194                                 words = bmake_realloc(words, new_size);
 195                         }
 196                         words[words_len++] =
 197                             Substring_Init(word_start, word_end - 1);
 198                         word_start = NULL;
 199                         if (ch == '\n' || ch == '\0') {
 200                                 if (expand && inquote != '\0') {
 201                                         SubstringWords res;
 202
 203                                         free(words);
 204                                         free(words_buf);
 205
 206                                         res.words = NULL;
 207                                         res.len = 0;
 208                                         res.freeIt = NULL;
 209                                         return res;
 210                                 }
 211                                 goto done;
 212                         }
 213                         continue;
 214                 case '\\':
 215                         if (!expand) {
 216                                 if (word_start == NULL)
 217                                         word_start = word_end;
 218                                 *word_end++ = '\\';
 219                                 /* catch '\' at end of line */
 220                                 if (str_p[1] == '\0')
 221                                         continue;
 222                                 ch = *++str_p;
 223                                 break;
 224                         }
 225
 226                         switch (ch = *++str_p) {
 227                         case '\0':
 228                         case '\n':
 229                                 /* hmmm; fix it up as best we can */
 230                                 ch = '\\';
 231                                 str_p--;
 232                                 break;
 233                         case 'b':
 234                                 ch = '\b';
 235                                 break;
 236                         case 'f':
 237                                 ch = '\f';
 238                                 break;
 239                         case 'n':
 240                                 ch = '\n';
 241                                 break;
 242                         case 'r':
 243                                 ch = '\r';
 244                                 break;
 245                         case 't':
 246                                 ch = '\t';
 247                                 break;
 248                         }
 249                         break;
 250                 }
 251                 if (word_start == NULL)
 252                         word_start = word_end;
 253                 *word_end++ = ch;
 254         }
 255 done:
 256         words[words_len] = Substring_Init(NULL, NULL);  /* useful for argv */
 257
 258         {
 259                 SubstringWords result;
 260
 261                 result.words = words;
 262                 result.len = words_len;
 263                 result.freeIt = words_buf;
 264                 return result;
 265         }
 266 }
 267
 268 Words
 269 Str_Words(const char *str, bool expand)
 270 {
 271         SubstringWords swords;
 272         Words words;
 273         size_t i;
 274
 275         swords = Substring_Words(str, expand);
 276         if (swords.words == NULL) {
 277                 words.words = NULL;
 278                 words.len = 0;
 279                 words.freeIt = NULL;
 280                 return words;
 281         }
 282
 283         words.words = bmake_malloc((swords.len + 1) * sizeof(words.words[0]));
 284         words.len = swords.len;
 285         words.freeIt = swords.freeIt;
 286         for (i = 0; i < swords.len + 1; i++)
 287                 words.words[i] = UNCONST(swords.words[i].start);
 288         free(swords.words);
 289         return words;
 290 }
 291
 292 /*
 293  * Str_Match -- Test if a string matches a pattern like "*.[ch]".
 294  * The following special characters are known *?\[] (as in fnmatch(3)).
 295  *
 296  * XXX: this function does not detect or report malformed patterns.
 297  */
 298 bool
 299 Str_Match(const char *str, const char *pat)
 300 {
 301         for (;;) {
 302                 /*
 303                  * See if we're at the end of both the pattern and the
 304                  * string. If so, we succeeded.  If we're at the end of the
 305                  * pattern but not at the end of the string, we failed.
 306                  */
 307                 if (*pat == '\0')
 308                         return *str == '\0';
 309                 if (*str == '\0' && *pat != '*')
 310                         return false;
 311
 312                 /*
 313                  * A '*' in the pattern matches any substring.  We handle this
 314                  * by calling ourselves for each suffix of the string.
 315                  */
 316                 if (*pat == '*') {
 317                         pat++;
 318                         while (*pat == '*')
 319                                 pat++;
 320                         if (*pat == '\0')
 321                                 return true;
 322                         while (*str != '\0') {
 323                                 if (Str_Match(str, pat))
 324                                         return true;
 325                                 str++;
 326                         }
 327                         return false;
 328                 }
 329
 330                 /* A '?' in the pattern matches any single character. */
 331                 if (*pat == '?')
 332                         goto thisCharOK;
 333
 334                 /*
 335                  * A '[' in the pattern matches a character from a list.
 336                  * The '[' is followed by the list of acceptable characters,
 337                  * or by ranges (two characters separated by '-'). In these
 338                  * character lists, the backslash is an ordinary character.
 339                  */
 340                 if (*pat == '[') {
 341                         bool neg = pat[1] == '^';
 342                         pat += neg ? 2 : 1;
 343
 344                         for (;;) {
 345                                 if (*pat == ']' || *pat == '\0') {
 346                                         if (neg)
 347                                                 break;
 348                                         return false;
 349                                 }
 350                                 /*
 351                                  * XXX: This naive comparison makes the
 352                                  * control flow of the pattern parser
 353                                  * dependent on the actual value of the
 354                                  * string.  This is unpredictable.  It may be
 355                                  * though that the code only looks wrong but
 356                                  * actually all code paths result in the same
 357                                  * behavior.  This needs further tests.
 358                                  */
 359                                 if (*pat == *str)
 360                                         break;
 361                                 if (pat[1] == '-') {
 362                                         if (pat[2] == '\0')
 363                                                 return neg;
 364                                         if (*pat <= *str && pat[2] >= *str)
 365                                                 break;
 366                                         if (*pat >= *str && pat[2] <= *str)
 367                                                 break;
 368                                         pat += 2;
 369                                 }
 370                                 pat++;
 371                         }
 372                         if (neg && *pat != ']' && *pat != '\0')
 373                                 return false;
 374                         while (*pat != ']' && *pat != '\0')
 375                                 pat++;
 376                         if (*pat == '\0')
 377                                 pat--;
 378                         goto thisCharOK;
 379                 }
 380
 381                 /*
 382                  * A backslash in the pattern matches the character following
 383                  * it exactly.
 384                  */
 385                 if (*pat == '\\') {
 386                         pat++;
 387                         if (*pat == '\0')
 388                                 return false;
 389                 }
 390
 391                 if (*pat != *str)
 392                         return false;
 393
 394         thisCharOK:
 395                 pat++;
 396                 str++;
 397         }
 398 }