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 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 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 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 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 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 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