xref: /freebsd/contrib/bmake/str.c (revision ebacd8013fe5f7fdf9f6a5b286f6680dd2891036)
1 /*	$NetBSD: str.c,v 1.94 2022/12/07 10:28:48 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.94 2022/12/07 10:28:48 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  * Test if a string matches a pattern like "*.[ch]". The pattern matching
317  * characters are '*', '?' and '[]', 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 }
404