Annotation of src/usr.bin/make/direxpand.c, Revision 1.5
1.5 ! espie 1: /* $OpenBSD$ */
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 "config.h"
66: #include "defines.h"
67: #include "lst.h"
68: #include "dir.h"
69: #include "direxpand.h"
70: #include "error.h"
71: #include "memory.h"
72: #include "str.h"
73:
74: /* Handles simple wildcard expansion on a path. */
75: static void PathMatchFilesi(const char *, const char *, Lst, Lst);
76: /* Handles wildcards expansion except for curly braces. */
77: static void DirExpandWildi(const char *, const char *, Lst, Lst);
78: #define DirExpandWild(s, l1, l2) DirExpandWildi(s, strchr(s, '\0'), l1, l2)
79: /* Handles wildcard expansion including curly braces. */
80: static void DirExpandCurlyi(const char *, const char *, Lst, Lst);
81:
82: /* Debugging: show each word in an expansion list. */
83: static void DirPrintWord(void *);
84:
85: /*-
86: *-----------------------------------------------------------------------
87: * PathMatchFilesi --
88: * Traverse directories in the path, calling Dir_MatchFiles for each.
89: * NOTE: This doesn't handle patterns in directories.
90: *-----------------------------------------------------------------------
91: */
92: static void
93: PathMatchFilesi(const char *word, const char *eword, Lst path, Lst expansions)
94: {
95: LstNode ln; /* Current node */
96:
97: for (ln = Lst_First(path); ln != NULL; ln = Lst_Adv(ln))
1.4 espie 98: Dir_MatchFilesi(word, eword, (struct PathEntry *)Lst_Datum(ln),
99: expansions);
1.1 espie 100: }
101:
102: /*-
103: *-----------------------------------------------------------------------
104: * DirExpandWildi:
105: * Expand all wild cards in a fully qualified name, except for
106: * curly braces.
107: * Side-effect:
108: * Will hash any directory in which a file is found, and add it to
109: * the path, on the assumption that future lookups will find files
110: * there as well.
111: *-----------------------------------------------------------------------
112: */
113: static void
114: DirExpandWildi(const char *word, const char *eword, Lst path, Lst expansions)
115: {
1.4 espie 116: const char *cp;
117: const char *slash; /* keep track of first slash before wildcard */
1.1 espie 118:
119: slash = memchr(word, '/', eword - word);
120: if (slash == NULL) {
121: /* First the files in dot. */
122: Dir_MatchFilesi(word, eword, dot, expansions);
123:
124: /* Then the files in every other directory on the path. */
125: PathMatchFilesi(word, eword, path, expansions);
126: return;
127: }
128: /* The thing has a directory component -- find the first wildcard
129: * in the string. */
130: slash = word;
131: for (cp = word; cp != eword; cp++) {
132: if (*cp == '/')
133: slash = cp;
134: if (*cp == '?' || *cp == '[' || *cp == '*') {
135:
136: if (slash != word) {
137: char *dirpath;
138:
1.3 espie 139: /* If the glob isn't in the first component,
140: * try and find all the components up to
1.1 espie 141: * the one with a wildcard. */
142: dirpath = Dir_FindFilei(word, slash+1, path);
1.3 espie 143: /* dirpath is null if we can't find the
144: * leading component
145: * XXX: Dir_FindFile won't find internal
146: * components. i.e. if the path contains
147: * ../Etc/Object and we're looking for Etc,
1.1 espie 148: * it won't be found. */
149: if (dirpath != NULL) {
150: char *dp;
151: LIST temp;
152:
153: dp = strchr(dirpath, '\0');
154: while (dp > dirpath && dp[-1] == '/')
155: dp--;
156:
157: Lst_Init(&temp);
158: Dir_AddDiri(&temp, dirpath, dp);
1.3 espie 159: PathMatchFilesi(slash+1, eword, &temp,
1.1 espie 160: expansions);
161: Lst_Destroy(&temp, NOFREE);
162: }
163: } else
164: /* Start the search from the local directory. */
165: PathMatchFilesi(word, eword, path, expansions);
166: return;
167: }
168: }
169: /* Return the file -- this should never happen. */
170: PathMatchFilesi(word, eword, path, expansions);
171: }
172:
173: /*-
174: *-----------------------------------------------------------------------
175: * DirExpandCurly --
176: * Expand curly braces like the C shell, and other wildcards as per
177: * Str_Match.
178: * XXX: if curly expansion yields a result with
179: * no wildcards, the result is placed on the list WITHOUT CHECKING
180: * FOR ITS EXISTENCE.
181: *-----------------------------------------------------------------------
182: */
183: static void
184: DirExpandCurlyi(const char *word, const char *eword, Lst path, Lst expansions)
185: {
186: const char *cp2;/* Pointer for checking for wildcards in
187: * expansion before calling Dir_Expand */
188: LIST curled; /* Queue of words to expand */
189: char *toexpand; /* Current word to expand */
190: bool dowild; /* Wildcard left after curlies ? */
191:
192: /* Determine once and for all if there is something else going on */
193: dowild = false;
194: for (cp2 = word; cp2 != eword; cp2++)
195: if (*cp2 == '*' || *cp2 == '?' || *cp2 == '[') {
196: dowild = true;
197: break;
198: }
199:
200: /* Prime queue with copy of initial word */
201: Lst_Init(&curled);
202: Lst_EnQueue(&curled, Str_dupi(word, eword));
203: while ((toexpand = (char *)Lst_DeQueue(&curled)) != NULL) {
204: const char *brace;
205: const char *start;
206: /* Start of current chunk of brace clause */
207: const char *end;/* Character after the closing brace */
208: int bracelevel; /* Keep track of nested braces. If we hit
209: * the right brace with bracelevel == 0,
210: * this is the end of the clause. */
1.3 espie 211: size_t endLen; /* The length of the ending non-curlied
1.1 espie 212: * part of the current expansion */
213:
214: /* End case: no curly left to expand */
215: brace = strchr(toexpand, '{');
216: if (brace == NULL) {
217: if (dowild) {
218: DirExpandWild(toexpand, path, expansions);
219: free(toexpand);
220: } else
221: Lst_AtEnd(expansions, toexpand);
222: continue;
1.3 espie 223: }
1.1 espie 224:
225: start = brace+1;
226:
1.3 espie 227: /* Find the end of the brace clause first, being wary of
1.1 espie 228: * nested brace clauses. */
229: for (end = start, bracelevel = 0;; end++) {
230: if (*end == '{')
231: bracelevel++;
232: else if (*end == '\0') {
233: Error("Unterminated {} clause \"%s\"", start);
234: return;
235: } else if (*end == '}' && bracelevel-- == 0)
236: break;
237: }
238: end++;
239: endLen = strlen(end);
240:
241: for (;;) {
242: char *file; /* To hold current expansion */
243: const char *cp; /* Current position in brace clause */
1.3 espie 244:
1.1 espie 245: /* Find the end of the current expansion */
1.3 espie 246: for (bracelevel = 0, cp = start;
247: bracelevel != 0 || (*cp != '}' && *cp != ',');
1.1 espie 248: cp++) {
249: if (*cp == '{')
250: bracelevel++;
251: else if (*cp == '}')
252: bracelevel--;
253: }
254:
255: /* Build the current combination and enqueue it. */
1.3 espie 256: file = emalloc((brace - toexpand) + (cp - start) +
1.1 espie 257: endLen + 1);
258: if (brace != toexpand)
259: memcpy(file, toexpand, brace-toexpand);
260: if (cp != start)
261: memcpy(file+(brace-toexpand), start, cp-start);
1.3 espie 262: memcpy(file+(brace-toexpand)+(cp-start), end,
1.1 espie 263: endLen + 1);
264: Lst_EnQueue(&curled, file);
265: if (*cp == '}')
266: break;
267: start = cp+1;
268: }
269: free(toexpand);
270: }
271: }
272:
273: /* Side effects:
274: * Dir_Expandi will hash directories that were not yet visited */
275: void
276: Dir_Expandi(const char *word, const char *eword, Lst path, Lst expansions)
277: {
278: const char *cp;
279:
280: if (DEBUG(DIR)) {
281: char *s = Str_dupi(word, eword);
282: printf("expanding \"%s\"...", s);
283: free(s);
284: }
285:
286: cp = memchr(word, '{', eword - word);
287: if (cp)
288: DirExpandCurlyi(word, eword, path, expansions);
289: else
290: DirExpandWildi(word, eword, path, expansions);
291:
292: if (DEBUG(DIR)) {
293: Lst_Every(expansions, DirPrintWord);
294: fputc('\n', stdout);
295: }
296: }
297:
298: static void
299: DirPrintWord(void *word)
300: {
301: printf("%s ", (char *)word);
302: }
303:
304:
305: /* XXX: This code is not 100% correct ([^]] fails) */
306: bool
307: Dir_HasWildcardsi(const char *name, const char *ename)
308: {
309: const char *cp;
310: bool wild = false;
311: unsigned long brace = 0, bracket = 0;
312:
313: for (cp = name; cp != ename; cp++) {
314: switch (*cp) {
315: case '{':
316: brace++;
317: wild = true;
318: break;
319: case '}':
320: if (brace == 0)
321: return false;
322: brace--;
323: break;
324: case '[':
325: bracket++;
326: wild = true;
327: break;
328: case ']':
329: if (bracket == 0)
330: return false;
331: bracket--;
332: break;
333: case '?':
334: case '*':
335: wild = true;
336: break;
337: default:
338: break;
339: }
340: }
341: return wild && bracket == 0 && brace == 0;
342: }
343:
344: