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