1 /* $OpenBSD: direxpand.c,v 1.4 2007/09/17 12:22:52 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 "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)) 98 Dir_MatchFilesi(word, eword, (struct PathEntry *)Lst_Datum(ln), 99 expansions); 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 { 116 const char *cp; 117 const char *slash; /* keep track of first slash before wildcard */ 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 139 /* If the glob isn't in the first component, 140 * try and find all the components up to 141 * the one with a wildcard. */ 142 dirpath = Dir_FindFilei(word, slash+1, path); 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, 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); 159 PathMatchFilesi(slash+1, eword, &temp, 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. */ 211 size_t endLen; /* The length of the ending non-curlied 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; 223 } 224 225 start = brace+1; 226 227 /* Find the end of the brace clause first, being wary of 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 */ 244 245 /* Find the end of the current expansion */ 246 for (bracelevel = 0, cp = start; 247 bracelevel != 0 || (*cp != '}' && *cp != ','); 248 cp++) { 249 if (*cp == '{') 250 bracelevel++; 251 else if (*cp == '}') 252 bracelevel--; 253 } 254 255 /* Build the current combination and enqueue it. */ 256 file = emalloc((brace - toexpand) + (cp - start) + 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); 262 memcpy(file+(brace-toexpand)+(cp-start), end, 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 345