Annotation of src/usr.bin/make/direxpand.c, Revision 1.9
1.9 ! espie 1: /* $OpenBSD: direxpand.c,v 1.8 2016/10/21 16:12:38 espie Exp $ */
1.1 espie 2: /*
3: * Copyright (c) 1999,2007 Marc Espie.
4: *
5: * Extensive code changes for the OpenBSD project.
6: *
7: * Redistribution and use in source and binary forms, with or without
8: * modification, are permitted provided that the following conditions
9: * are met:
10: * 1. Redistributions of source code must retain the above copyright
11: * notice, this list of conditions and the following disclaimer.
12: * 2. Redistributions in binary form must reproduce the above copyright
13: * notice, this list of conditions and the following disclaimer in the
14: * documentation and/or other materials provided with the distribution.
15: *
16: * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
17: * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD
20: * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27: */
28: /*
29: * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
30: * Copyright (c) 1988, 1989 by Adam de Boor
31: * Copyright (c) 1989 by Berkeley Softworks
32: * All rights reserved.
33: *
34: * This code is derived from software contributed to Berkeley by
35: * Adam de Boor.
36: *
37: * Redistribution and use in source and binary forms, with or without
38: * modification, are permitted provided that the following conditions
39: * are met:
40: * 1. Redistributions of source code must retain the above copyright
41: * notice, this list of conditions and the following disclaimer.
42: * 2. Redistributions in binary form must reproduce the above copyright
43: * notice, this list of conditions and the following disclaimer in the
44: * documentation and/or other materials provided with the distribution.
45: * 3. Neither the name of the University nor the names of its contributors
46: * may be used to endorse or promote products derived from this software
47: * without specific prior written permission.
48: *
49: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
50: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
53: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
55: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
56: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
58: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
59: * SUCH DAMAGE.
60: */
61:
62: #include <stdio.h>
63: #include <stdlib.h>
64: #include <string.h>
65: #include "defines.h"
66: #include "lst.h"
67: #include "dir.h"
68: #include "direxpand.h"
69: #include "error.h"
70: #include "memory.h"
71: #include "str.h"
72:
73: /* Handles simple wildcard expansion on a path. */
74: static void PathMatchFilesi(const char *, const char *, Lst, Lst);
75: /* Handles wildcards expansion except for curly braces. */
76: static void DirExpandWildi(const char *, const char *, Lst, Lst);
77: #define DirExpandWild(s, l1, l2) DirExpandWildi(s, strchr(s, '\0'), l1, l2)
78: /* Handles wildcard expansion including curly braces. */
79: static void DirExpandCurlyi(const char *, const char *, Lst, Lst);
80:
81: /* Debugging: show each word in an expansion list. */
82: static void DirPrintWord(void *);
83:
84: /*-
85: *-----------------------------------------------------------------------
86: * PathMatchFilesi --
87: * Traverse directories in the path, calling Dir_MatchFiles for each.
88: * NOTE: This doesn't handle patterns in directories.
89: *-----------------------------------------------------------------------
90: */
91: static void
92: PathMatchFilesi(const char *word, const char *eword, Lst path, Lst expansions)
93: {
94: LstNode ln; /* Current node */
95:
96: for (ln = Lst_First(path); ln != NULL; ln = Lst_Adv(ln))
1.8 espie 97: Dir_MatchFilesi(word, eword, Lst_Datum(ln), expansions);
1.1 espie 98: }
99:
100: /*-
101: *-----------------------------------------------------------------------
102: * DirExpandWildi:
103: * Expand all wild cards in a fully qualified name, except for
104: * curly braces.
105: * Side-effect:
106: * Will hash any directory in which a file is found, and add it to
107: * the path, on the assumption that future lookups will find files
108: * there as well.
109: *-----------------------------------------------------------------------
110: */
111: static void
112: DirExpandWildi(const char *word, const char *eword, Lst path, Lst expansions)
113: {
1.4 espie 114: const char *cp;
115: const char *slash; /* keep track of first slash before wildcard */
1.1 espie 116:
117: slash = memchr(word, '/', eword - word);
118: if (slash == NULL) {
119: /* First the files in dot. */
120: Dir_MatchFilesi(word, eword, dot, expansions);
121:
122: /* Then the files in every other directory on the path. */
123: PathMatchFilesi(word, eword, path, expansions);
124: return;
125: }
126: /* The thing has a directory component -- find the first wildcard
127: * in the string. */
128: slash = word;
129: for (cp = word; cp != eword; cp++) {
130: if (*cp == '/')
131: slash = cp;
132: if (*cp == '?' || *cp == '[' || *cp == '*') {
133:
134: if (slash != word) {
135: char *dirpath;
136:
1.3 espie 137: /* If the glob isn't in the first component,
138: * try and find all the components up to
1.1 espie 139: * the one with a wildcard. */
140: dirpath = Dir_FindFilei(word, slash+1, path);
1.3 espie 141: /* dirpath is null if we can't find the
142: * leading component
143: * XXX: Dir_FindFile won't find internal
144: * components. i.e. if the path contains
145: * ../Etc/Object and we're looking for Etc,
1.1 espie 146: * it won't be found. */
147: if (dirpath != NULL) {
148: char *dp;
149: LIST temp;
150:
151: dp = strchr(dirpath, '\0');
152: while (dp > dirpath && dp[-1] == '/')
153: dp--;
154:
155: Lst_Init(&temp);
156: Dir_AddDiri(&temp, dirpath, dp);
1.3 espie 157: PathMatchFilesi(slash+1, eword, &temp,
1.1 espie 158: expansions);
159: Lst_Destroy(&temp, NOFREE);
160: }
161: } else
162: /* Start the search from the local directory. */
163: PathMatchFilesi(word, eword, path, expansions);
164: return;
165: }
166: }
167: /* Return the file -- this should never happen. */
168: PathMatchFilesi(word, eword, path, expansions);
169: }
170:
171: /*-
172: *-----------------------------------------------------------------------
173: * DirExpandCurly --
174: * Expand curly braces like the C shell, and other wildcards as per
175: * Str_Match.
176: * XXX: if curly expansion yields a result with
177: * no wildcards, the result is placed on the list WITHOUT CHECKING
178: * FOR ITS EXISTENCE.
179: *-----------------------------------------------------------------------
180: */
181: static void
182: DirExpandCurlyi(const char *word, const char *eword, Lst path, Lst expansions)
183: {
184: const char *cp2;/* Pointer for checking for wildcards in
185: * expansion before calling Dir_Expand */
186: LIST curled; /* Queue of words to expand */
187: char *toexpand; /* Current word to expand */
188: bool dowild; /* Wildcard left after curlies ? */
189:
190: /* Determine once and for all if there is something else going on */
191: dowild = false;
192: for (cp2 = word; cp2 != eword; cp2++)
193: if (*cp2 == '*' || *cp2 == '?' || *cp2 == '[') {
194: dowild = true;
195: break;
196: }
197:
198: /* Prime queue with copy of initial word */
199: Lst_Init(&curled);
200: Lst_EnQueue(&curled, Str_dupi(word, eword));
1.8 espie 201: while ((toexpand = Lst_DeQueue(&curled)) != NULL) {
1.1 espie 202: const char *brace;
203: const char *start;
204: /* Start of current chunk of brace clause */
205: const char *end;/* Character after the closing brace */
206: int bracelevel; /* Keep track of nested braces. If we hit
207: * the right brace with bracelevel == 0,
208: * this is the end of the clause. */
1.3 espie 209: size_t endLen; /* The length of the ending non-curlied
1.1 espie 210: * part of the current expansion */
211:
212: /* End case: no curly left to expand */
213: brace = strchr(toexpand, '{');
214: if (brace == NULL) {
215: if (dowild) {
216: DirExpandWild(toexpand, path, expansions);
217: free(toexpand);
218: } else
219: Lst_AtEnd(expansions, toexpand);
220: continue;
1.3 espie 221: }
1.1 espie 222:
223: start = brace+1;
224:
1.3 espie 225: /* Find the end of the brace clause first, being wary of
1.1 espie 226: * nested brace clauses. */
227: for (end = start, bracelevel = 0;; end++) {
228: if (*end == '{')
229: bracelevel++;
230: else if (*end == '\0') {
231: Error("Unterminated {} clause \"%s\"", start);
232: return;
233: } else if (*end == '}' && bracelevel-- == 0)
234: break;
235: }
236: end++;
237: endLen = strlen(end);
238:
239: for (;;) {
240: char *file; /* To hold current expansion */
241: const char *cp; /* Current position in brace clause */
1.3 espie 242:
1.1 espie 243: /* Find the end of the current expansion */
1.3 espie 244: for (bracelevel = 0, cp = start;
245: bracelevel != 0 || (*cp != '}' && *cp != ',');
1.1 espie 246: cp++) {
247: if (*cp == '{')
248: bracelevel++;
249: else if (*cp == '}')
250: bracelevel--;
251: }
252:
253: /* Build the current combination and enqueue it. */
1.3 espie 254: file = emalloc((brace - toexpand) + (cp - start) +
1.1 espie 255: endLen + 1);
256: if (brace != toexpand)
257: memcpy(file, toexpand, brace-toexpand);
258: if (cp != start)
259: memcpy(file+(brace-toexpand), start, cp-start);
1.3 espie 260: memcpy(file+(brace-toexpand)+(cp-start), end,
1.1 espie 261: endLen + 1);
262: Lst_EnQueue(&curled, file);
263: if (*cp == '}')
264: break;
265: start = cp+1;
266: }
267: free(toexpand);
268: }
269: }
270:
271: /* Side effects:
272: * Dir_Expandi will hash directories that were not yet visited */
273: void
274: Dir_Expandi(const char *word, const char *eword, Lst path, Lst expansions)
275: {
276: const char *cp;
277:
278: if (DEBUG(DIR)) {
279: char *s = Str_dupi(word, eword);
280: printf("expanding \"%s\"...", s);
281: free(s);
282: }
283:
284: cp = memchr(word, '{', eword - word);
285: if (cp)
286: DirExpandCurlyi(word, eword, path, expansions);
287: else
288: DirExpandWildi(word, eword, path, expansions);
289:
290: if (DEBUG(DIR)) {
291: Lst_Every(expansions, DirPrintWord);
292: fputc('\n', stdout);
293: }
294: }
295:
296: static void
297: DirPrintWord(void *word)
298: {
1.7 espie 299: const char *s = word;
1.6 espie 300: printf("%s ", s);
1.1 espie 301: }
302:
303:
304: /* XXX: This code is not 100% correct ([^]] fails) */
305: bool
306: Dir_HasWildcardsi(const char *name, const char *ename)
307: {
308: const char *cp;
309: bool wild = false;
310: unsigned long brace = 0, bracket = 0;
311:
312: for (cp = name; cp != ename; cp++) {
313: switch (*cp) {
314: case '{':
315: brace++;
316: wild = true;
317: break;
318: case '}':
319: if (brace == 0)
320: return false;
321: brace--;
322: break;
323: case '[':
324: bracket++;
325: wild = true;
326: break;
327: case ']':
328: if (bracket == 0)
329: return false;
330: bracket--;
331: break;
332: case '?':
333: case '*':
334: wild = true;
335: break;
336: default:
337: break;
338: }
339: }
340: return wild && bracket == 0 && brace == 0;
341: }
342:
343: