1 /* $OpenBSD: direxpand.c,v 1.9 2023/09/04 11:35:11 espie Exp $ */
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
PathMatchFilesi(const char * word,const char * eword,Lst path,Lst expansions)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))
97 Dir_MatchFilesi(word, eword, Lst_Datum(ln), expansions);
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
DirExpandWildi(const char * word,const char * eword,Lst path,Lst expansions)112 DirExpandWildi(const char *word, const char *eword, Lst path, Lst expansions)
113 {
114 const char *cp;
115 const char *slash; /* keep track of first slash before wildcard */
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
137 /* If the glob isn't in the first component,
138 * try and find all the components up to
139 * the one with a wildcard. */
140 dirpath = Dir_FindFilei(word, slash+1, path);
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,
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);
157 PathMatchFilesi(slash+1, eword, &temp,
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
DirExpandCurlyi(const char * word,const char * eword,Lst path,Lst expansions)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));
201 while ((toexpand = Lst_DeQueue(&curled)) != NULL) {
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. */
209 size_t endLen; /* The length of the ending non-curlied
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;
221 }
222
223 start = brace+1;
224
225 /* Find the end of the brace clause first, being wary of
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 */
242
243 /* Find the end of the current expansion */
244 for (bracelevel = 0, cp = start;
245 bracelevel != 0 || (*cp != '}' && *cp != ',');
246 cp++) {
247 if (*cp == '{')
248 bracelevel++;
249 else if (*cp == '}')
250 bracelevel--;
251 }
252
253 /* Build the current combination and enqueue it. */
254 file = emalloc((brace - toexpand) + (cp - start) +
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);
260 memcpy(file+(brace-toexpand)+(cp-start), end,
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
Dir_Expandi(const char * word,const char * eword,Lst path,Lst expansions)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
DirPrintWord(void * word)297 DirPrintWord(void *word)
298 {
299 const char *s = word;
300 printf("%s ", s);
301 }
302
303
304 /* XXX: This code is not 100% correct ([^]] fails) */
305 bool
Dir_HasWildcardsi(const char * name,const char * ename)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
344