Annotation of src/usr.bin/make/direxpand.c, Revision 1.1
1.1 ! espie 1: /* $OpenBSD$ */
! 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 Path_ *)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 = (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: