contrib/bmake/str.c

   1 /*      $NetBSD: str.c,v 1.70 2020/10/24 20:51:49 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.70 2020/10/24 20:51:49 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 /* Return the concatenation of s1, s2, s3 and s4, freshly allocated. */
 103 char *
 104 str_concat4(const char *s1, const char *s2, const char *s3, const char *s4)
 105 {
 106         size_t len1 = strlen(s1);
 107         size_t len2 = strlen(s2);
 108         size_t len3 = strlen(s3);
 109         size_t len4 = strlen(s4);
 110         char *result = bmake_malloc(len1 + len2 + len3 + len4 + 1);
 111         memcpy(result, s1, len1);
 112         memcpy(result + len1, s2, len2);
 113         memcpy(result + len1 + len2, s3, len3);
 114         memcpy(result + len1 + len2 + len3, s4, len4 + 1);
 115         return result;
 116 }
 117
 118 /* Fracture a string into an array of words (as delineated by tabs or spaces)
 119  * taking quotation marks into account.  Leading tabs/spaces are ignored.
 120  *
 121  * If expand is TRUE, quotes are removed and escape sequences such as \r, \t,
 122  * etc... are expanded. In this case, the return value is NULL on parse
 123  * errors.
 124  *
 125  * Returns the fractured words, which must be freed later using Words_Free.
 126  * If expand was TRUE and there was a parse error, words is NULL, and in that
 127  * case, nothing needs to be freed.
 128  */
 129 Words
 130 Str_Words(const char *str, Boolean expand)
 131 {
 132         size_t str_len;
 133         char *words_buf;
 134         size_t words_cap;
 135         char **words;
 136         size_t words_len;
 137         char inquote;
 138         char *word_start;
 139         char *word_end;
 140         const char *str_p;
 141
 142         /* skip leading space chars. */
 143         for (; *str == ' ' || *str == '\t'; ++str)
 144                 continue;
 145
 146         /* words_buf holds the words, separated by '\0'. */
 147         str_len = strlen(str);
 148         words_buf = bmake_malloc(strlen(str) + 1);
 149
 150         words_cap = str_len / 5 > 50 ? str_len / 5 : 50;
 151         words = bmake_malloc((words_cap + 1) * sizeof(char *));
 152
 153         /*
 154          * copy the string; at the same time, parse backslashes,
 155          * quotes and build the word list.
 156          */
 157         words_len = 0;
 158         inquote = '\0';
 159         word_start = words_buf;
 160         word_end = words_buf;
 161         for (str_p = str;; ++str_p) {
 162                 char ch = *str_p;
 163                 switch (ch) {
 164                 case '"':
 165                 case '\'':
 166                         if (inquote) {
 167                                 if (inquote == ch)
 168                                         inquote = '\0';
 169                                 else
 170                                         break;
 171                         } else {
 172                                 inquote = ch;
 173                                 /* Don't miss "" or '' */
 174                                 if (word_start == NULL && str_p[1] == inquote) {
 175                                         if (!expand) {
 176                                                 word_start = word_end;
 177                                                 *word_end++ = ch;
 178                                         } else
 179                                                 word_start = word_end + 1;
 180                                         str_p++;
 181                                         inquote = '\0';
 182                                         break;
 183                                 }
 184                         }
 185                         if (!expand) {
 186                                 if (word_start == NULL)
 187                                         word_start = word_end;
 188                                 *word_end++ = ch;
 189                         }
 190                         continue;
 191                 case ' ':
 192                 case '\t':
 193                 case '\n':
 194                         if (inquote)
 195                                 break;
 196                         if (word_start == NULL)
 197                                 continue;
 198                         /* FALLTHROUGH */
 199                 case '\0':
 200                         /*
 201                          * end of a token -- make sure there's enough words
 202                          * space and save off a pointer.
 203                          */
 204                         if (word_start == NULL)
 205                                 goto done;
 206
 207                         *word_end++ = '\0';
 208                         if (words_len == words_cap) {
 209                                 size_t new_size;
 210                                 words_cap *= 2;         /* ramp up fast */
 211                                 new_size = (words_cap + 1) * sizeof(char *);
 212                                 words = bmake_realloc(words, new_size);
 213                         }
 214                         words[words_len++] = word_start;
 215                         word_start = NULL;
 216                         if (ch == '\n' || ch == '\0') {
 217                                 if (expand && inquote) {
 218                                         free(words);
 219                                         free(words_buf);
 220                                         return (Words){ NULL, 0, NULL };
 221                                 }
 222                                 goto done;
 223                         }
 224                         continue;
 225                 case '\\':
 226                         if (!expand) {
 227                                 if (word_start == NULL)
 228                                         word_start = word_end;
 229                                 *word_end++ = '\\';
 230                                 /* catch '\' at end of line */
 231                                 if (str_p[1] == '\0')
 232                                         continue;
 233                                 ch = *++str_p;
 234                                 break;
 235                         }
 236
 237                         switch (ch = *++str_p) {
 238                         case '\0':
 239                         case '\n':
 240                                 /* hmmm; fix it up as best we can */
 241                                 ch = '\\';
 242                                 --str_p;
 243                                 break;
 244                         case 'b':
 245                                 ch = '\b';
 246                                 break;
 247                         case 'f':
 248                                 ch = '\f';
 249                                 break;
 250                         case 'n':
 251                                 ch = '\n';
 252                                 break;
 253                         case 'r':
 254                                 ch = '\r';
 255                                 break;
 256                         case 't':
 257                                 ch = '\t';
 258                                 break;
 259                         }
 260                         break;
 261                 }
 262                 if (word_start == NULL)
 263                         word_start = word_end;
 264                 *word_end++ = ch;
 265         }
 266 done:
 267         words[words_len] = NULL;
 268         return (Words){ words, words_len, words_buf };
 269 }
 270
 271 /*
 272  * Str_Match -- Test if a string matches a pattern like "*.[ch]".
 273  *
 274  * XXX this function does not detect or report malformed patterns.
 275  *
 276  * Results:
 277  *      Non-zero is returned if string matches the pattern, 0 otherwise. The
 278  *      matching operation permits the following special characters in the
 279  *      pattern: *?\[] (as in fnmatch(3)).
 280  *
 281  * Side effects: None.
 282  */
 283 Boolean
 284 Str_Match(const char *str, const char *pat)
 285 {
 286         for (;;) {
 287                 /*
 288                  * See if we're at the end of both the pattern and the
 289                  * string. If, we succeeded.  If we're at the end of the
 290                  * pattern but not at the end of the string, we failed.
 291                  */
 292                 if (*pat == 0)
 293                         return *str == 0;
 294                 if (*str == 0 && *pat != '*')
 295                         return FALSE;
 296
 297                 /*
 298                  * A '*' in the pattern matches any substring.  We handle this
 299                  * by calling ourselves for each suffix of the string.
 300                  */
 301                 if (*pat == '*') {
 302                         pat++;
 303                         while (*pat == '*')
 304                                 pat++;
 305                         if (*pat == 0)
 306                                 return TRUE;
 307                         while (*str != 0) {
 308                                 if (Str_Match(str, pat))
 309                                         return TRUE;
 310                                 str++;
 311                         }
 312                         return FALSE;
 313                 }
 314
 315                 /* A '?' in the pattern matches any single character. */
 316                 if (*pat == '?')
 317                         goto thisCharOK;
 318
 319                 /*
 320                  * A '[' in the pattern matches a character from a list.
 321                  * The '[' is followed by the list of acceptable characters,
 322                  * or by ranges (two characters separated by '-'). In these
 323                  * character lists, the backslash is an ordinary character.
 324                  */
 325                 if (*pat == '[') {
 326                         Boolean neg = pat[1] == '^';
 327                         pat += neg ? 2 : 1;
 328
 329                         for (;;) {
 330                                 if (*pat == ']' || *pat == 0) {
 331                                         if (neg)
 332                                                 break;
 333                                         return FALSE;
 334                                 }
 335                                 if (*pat == *str)
 336                                         break;
 337                                 if (pat[1] == '-') {
 338                                         if (pat[2] == 0)
 339                                                 return neg;
 340                                         if (*pat <= *str && pat[2] >= *str)
 341                                                 break;
 342                                         if (*pat >= *str && pat[2] <= *str)
 343                                                 break;
 344                                         pat += 2;
 345                                 }
 346                                 pat++;
 347                         }
 348                         if (neg && *pat != ']' && *pat != 0)
 349                                 return FALSE;
 350                         while (*pat != ']' && *pat != 0)
 351                                 pat++;
 352                         if (*pat == 0)
 353                                 pat--;
 354                         goto thisCharOK;
 355                 }
 356
 357                 /*
 358                  * A backslash in the pattern matches the character following
 359                  * it exactly.
 360                  */
 361                 if (*pat == '\\') {
 362                         pat++;
 363                         if (*pat == 0)
 364                                 return FALSE;
 365                 }
 366
 367                 if (*pat != *str)
 368                         return FALSE;
 369
 370         thisCharOK:
 371                 pat++;
 372                 str++;
 373         }
 374 }