Annotation of src/usr.bin/make/direxpand.c, Revision 1.2
1.2 ! espie 1: /* $OpenBSD: direxpand.c,v 1.1 2007/09/16 10:14:26 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 "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.2 ! espie 98: Dir_MatchFilesi(word, eword, (struct PathEntry *)Lst_Datum(ln), expansions);
1.1 espie 99: }
100:
101: /*-
102: *-----------------------------------------------------------------------
103: * DirExpandWildi:
104: * Expand all wild cards in a fully qualified name, except for
105: * curly braces.
106: * Side-effect:
107: * Will hash any directory in which a file is found, and add it to
108: * the path, on the assumption that future lookups will find files
109: * there as well.
110: *-----------------------------------------------------------------------
111: */
112: static void
113: DirExpandWildi(const char *word, const char *eword, Lst path, Lst expansions)
114: {
115: const char *cp;
116: const char *slash; /* keep track of first slash before wildcard */
117:
118: slash = memchr(word, '/', eword - word);
119: if (slash == NULL) {
120: /* First the files in dot. */
121: Dir_MatchFilesi(word, eword, dot, expansions);
122:
123: /* Then the files in every other directory on the path. */
124: PathMatchFilesi(word, eword, path, expansions);
125: return;
126: }
127: /* The thing has a directory component -- find the first wildcard
128: * in the string. */
129: slash = word;
130: for (cp = word; cp != eword; cp++) {
131: if (*cp == '/')
132: slash = cp;
133: if (*cp == '?' || *cp == '[' || *cp == '*') {
134:
135: if (slash != word) {
136: char *dirpath;
137:
138: /* If the glob isn't in the first component,
139: * try and find all the components up to
140: * the one with a wildcard. */
141: dirpath = Dir_FindFilei(word, slash+1, path);
142: /* dirpath is null if we can't find the
143: * leading component
144: * XXX: Dir_FindFile won't find internal
145: * components. i.e. if the path contains
146: * ../Etc/Object and we're looking for Etc,
147: * it won't be found. */
148: if (dirpath != NULL) {
149: char *dp;
150: LIST temp;
151:
152: dp = strchr(dirpath, '\0');
153: while (dp > dirpath && dp[-1] == '/')
154: dp--;
155:
156: Lst_Init(&temp);
157: Dir_AddDiri(&temp, dirpath, dp);
158: PathMatchFilesi(slash+1, eword, &temp,
159: expansions);
160: Lst_Destroy(&temp, NOFREE);
161: }
162: } else
163: /* Start the search from the local directory. */
164: PathMatchFilesi(word, eword, path, expansions);
165: return;
166: }
167: }
168: /* Return the file -- this should never happen. */
169: PathMatchFilesi(word, eword, path, expansions);
170: }
171:
172: /*-
173: *-----------------------------------------------------------------------
174: * DirExpandCurly --
175: * Expand curly braces like the C shell, and other wildcards as per
176: * Str_Match.
177: * XXX: if curly expansion yields a result with
178: * no wildcards, the result is placed on the list WITHOUT CHECKING
179: * FOR ITS EXISTENCE.
180: *-----------------------------------------------------------------------
181: */
182: static void
183: DirExpandCurlyi(const char *word, const char *eword, Lst path, Lst expansions)
184: {
185: const char *cp2;/* Pointer for checking for wildcards in
186: * expansion before calling Dir_Expand */
187: LIST curled; /* Queue of words to expand */
188: char *toexpand; /* Current word to expand */
189: bool dowild; /* Wildcard left after curlies ? */
190:
191: /* Determine once and for all if there is something else going on */
192: dowild = false;
193: for (cp2 = word; cp2 != eword; cp2++)
194: if (*cp2 == '*' || *cp2 == '?' || *cp2 == '[') {
195: dowild = true;
196: break;
197: }
198:
199: /* Prime queue with copy of initial word */
200: Lst_Init(&curled);
201: Lst_EnQueue(&curled, Str_dupi(word, eword));
202: while ((toexpand = (char *)Lst_DeQueue(&curled)) != NULL) {
203: const char *brace;
204: const char *start;
205: /* Start of current chunk of brace clause */
206: const char *end;/* Character after the closing brace */
207: int bracelevel; /* Keep track of nested braces. If we hit
208: * the right brace with bracelevel == 0,
209: * this is the end of the clause. */
210: size_t endLen; /* The length of the ending non-curlied
211: * part of the current expansion */
212:
213: /* End case: no curly left to expand */
214: brace = strchr(toexpand, '{');
215: if (brace == NULL) {
216: if (dowild) {
217: DirExpandWild(toexpand, path, expansions);
218: free(toexpand);
219: } else
220: Lst_AtEnd(expansions, toexpand);
221: continue;
222: }
223:
224: start = brace+1;
225:
226: /* Find the end of the brace clause first, being wary of
227: * nested brace clauses. */
228: for (end = start, bracelevel = 0;; end++) {
229: if (*end == '{')
230: bracelevel++;
231: else if (*end == '\0') {
232: Error("Unterminated {} clause \"%s\"", start);
233: return;
234: } else if (*end == '}' && bracelevel-- == 0)
235: break;
236: }
237: end++;
238: endLen = strlen(end);
239:
240: for (;;) {
241: char *file; /* To hold current expansion */
242: const char *cp; /* Current position in brace clause */
243:
244: /* Find the end of the current expansion */
245: for (bracelevel = 0, cp = start;
246: bracelevel != 0 || (*cp != '}' && *cp != ',');
247: cp++) {
248: if (*cp == '{')
249: bracelevel++;
250: else if (*cp == '}')
251: bracelevel--;
252: }
253:
254: /* Build the current combination and enqueue it. */
255: file = emalloc((brace - toexpand) + (cp - start) +
256: endLen + 1);
257: if (brace != toexpand)
258: memcpy(file, toexpand, brace-toexpand);
259: if (cp != start)
260: memcpy(file+(brace-toexpand), start, cp-start);
261: memcpy(file+(brace-toexpand)+(cp-start), end,
262: endLen + 1);
263: Lst_EnQueue(&curled, file);
264: if (*cp == '}')
265: break;
266: start = cp+1;
267: }
268: free(toexpand);
269: }
270: }
271:
272: /* Side effects:
273: * Dir_Expandi will hash directories that were not yet visited */
274: void
275: Dir_Expandi(const char *word, const char *eword, Lst path, Lst expansions)
276: {
277: const char *cp;
278:
279: if (DEBUG(DIR)) {
280: char *s = Str_dupi(word, eword);
281: printf("expanding \"%s\"...", s);
282: free(s);
283: }
284:
285: cp = memchr(word, '{', eword - word);
286: if (cp)
287: DirExpandCurlyi(word, eword, path, expansions);
288: else
289: DirExpandWildi(word, eword, path, expansions);
290:
291: if (DEBUG(DIR)) {
292: Lst_Every(expansions, DirPrintWord);
293: fputc('\n', stdout);
294: }
295: }
296:
297: static void
298: DirPrintWord(void *word)
299: {
300: printf("%s ", (char *)word);
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: