1 /* $OpenBSD: direxpand.c,v 1.8 2016/10/21 16:12:38 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, Lst_Datum(ln), expansions); 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 = 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 const char *s = word; 301 printf("%s ", s); 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