1 /* $NetBSD: glob.c,v 1.32 2012/12/18 01:39:56 christos Exp $ */ 2 3 /* 4 * Copyright (c) 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Guido van Rossum. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include <sys/cdefs.h> 36 #if defined(LIBC_SCCS) && !defined(lint) 37 #if 0 38 static char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93"; 39 #else 40 __RCSID("$NetBSD: glob.c,v 1.32 2012/12/18 01:39:56 christos Exp $"); 41 #endif 42 #endif /* LIBC_SCCS and not lint */ 43 44 /* 45 * glob(3) -- a superset of the one defined in POSIX 1003.2. 46 * 47 * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 48 * 49 * Optional extra services, controlled by flags not defined by POSIX: 50 * 51 * GLOB_MAGCHAR: 52 * Set in gl_flags if pattern contained a globbing character. 53 * GLOB_NOMAGIC: 54 * Same as GLOB_NOCHECK, but it will only append pattern if it did 55 * not contain any magic characters. [Used in csh style globbing] 56 * GLOB_ALTDIRFUNC: 57 * Use alternately specified directory access functions. 58 * GLOB_TILDE: 59 * expand ~user/foo to the /home/dir/of/user/foo 60 * GLOB_BRACE: 61 * expand {1,2}{a,b} to 1a 1b 2a 2b 62 * GLOB_PERIOD: 63 * allow metacharacters to match leading dots in filenames. 64 * GLOB_NO_DOTDIRS: 65 * . and .. are hidden from wildcards, even if GLOB_PERIOD is set. 66 * gl_matchc: 67 * Number of matches in the current invocation of glob. 68 */ 69 70 #include "namespace.h" 71 #include <sys/param.h> 72 #include <sys/stat.h> 73 74 #include <assert.h> 75 #include <ctype.h> 76 #include <dirent.h> 77 #include <errno.h> 78 #include <glob.h> 79 #include <pwd.h> 80 #include <stdio.h> 81 #include <stddef.h> 82 #include <stdlib.h> 83 #include <string.h> 84 #include <unistd.h> 85 86 #ifdef HAVE_NBTOOL_CONFIG_H 87 #define NO_GETPW_R 88 #endif 89 90 #define GLOB_LIMIT_STRING 65536 /* number of readdirs */ 91 #define GLOB_LIMIT_STAT 128 /* number of stat system calls */ 92 #define GLOB_LIMIT_READDIR 16384 /* total buffer size of path strings */ 93 #define GLOB_LIMIT_PATH 1024 /* number of path elements */ 94 #define GLOB_LIMIT_BRACE 128 /* Number of brace calls */ 95 96 struct glob_limit { 97 size_t l_string; 98 size_t l_stat; 99 size_t l_readdir; 100 size_t l_brace; 101 }; 102 103 /* 104 * XXX: For NetBSD 1.4.x compatibility. (kill me l8r) 105 */ 106 #ifndef _DIAGASSERT 107 #define _DIAGASSERT(a) 108 #endif 109 110 #define DOLLAR '$' 111 #define DOT '.' 112 #define EOS '\0' 113 #define LBRACKET '[' 114 #define NOT '!' 115 #define QUESTION '?' 116 #define QUOTE '\\' 117 #define RANGE '-' 118 #define RBRACKET ']' 119 #define SEP '/' 120 #define STAR '*' 121 #define TILDE '~' 122 #define UNDERSCORE '_' 123 #define LBRACE '{' 124 #define RBRACE '}' 125 #define SLASH '/' 126 #define COMMA ',' 127 128 #ifndef USE_8BIT_CHARS 129 130 #define M_QUOTE 0x8000 131 #define M_PROTECT 0x4000 132 #define M_MASK 0xffff 133 #define M_ASCII 0x00ff 134 135 typedef u_short Char; 136 137 #else 138 139 #define M_QUOTE (Char)0x80 140 #define M_PROTECT (Char)0x40 141 #define M_MASK (Char)0xff 142 #define M_ASCII (Char)0x7f 143 144 typedef char Char; 145 146 #endif 147 148 149 #define CHAR(c) ((Char)((c)&M_ASCII)) 150 #define META(c) ((Char)((c)|M_QUOTE)) 151 #define M_ALL META('*') 152 #define M_END META(']') 153 #define M_NOT META('!') 154 #define M_ONE META('?') 155 #define M_RNG META('-') 156 #define M_SET META('[') 157 #define ismeta(c) (((c)&M_QUOTE) != 0) 158 159 160 static int compare(const void *, const void *); 161 static int g_Ctoc(const Char *, char *, size_t); 162 static int g_lstat(Char *, __gl_stat_t *, glob_t *); 163 static DIR *g_opendir(Char *, glob_t *); 164 static Char *g_strchr(const Char *, int); 165 static int g_stat(Char *, __gl_stat_t *, glob_t *); 166 static int glob0(const char *, const Char *, glob_t *, struct glob_limit *); 167 static int glob1(Char *, glob_t *, struct glob_limit *); 168 static int glob2(Char *, Char *, Char *, const Char *, glob_t *, 169 struct glob_limit *); 170 static int glob3(Char *, Char *, Char *, const Char *, const Char *, 171 const Char *, glob_t *, struct glob_limit *); 172 static int globextend(const Char *, glob_t *, struct glob_limit *); 173 static const Char *globtilde(const Char *, Char *, size_t, glob_t *); 174 static int globexp1(const char *, const Char *, glob_t *, struct glob_limit *); 175 static int globexp2(const char *, const Char *, const Char *, glob_t *, int *, 176 struct glob_limit *); 177 static int match(const Char *, const Char *, const Char *); 178 #ifdef DEBUG 179 static void qprintf(const char *, Char *); 180 #endif 181 182 int 183 glob(const char * __restrict pattern, int flags, int (*errfunc)(const char *, 184 int), glob_t * __restrict pglob) 185 { 186 const u_char *patnext; 187 int c; 188 Char *bufnext, *bufend, patbuf[MAXPATHLEN+1]; 189 struct glob_limit limit = { 0, 0, 0, 0 }; 190 191 _DIAGASSERT(pattern != NULL); 192 193 patnext = (const u_char *) pattern; 194 if (!(flags & GLOB_APPEND)) { 195 pglob->gl_pathc = 0; 196 pglob->gl_pathv = NULL; 197 if (!(flags & GLOB_DOOFFS)) 198 pglob->gl_offs = 0; 199 } 200 pglob->gl_flags = flags & ~GLOB_MAGCHAR; 201 pglob->gl_errfunc = errfunc; 202 pglob->gl_matchc = 0; 203 204 bufnext = patbuf; 205 bufend = bufnext + MAXPATHLEN; 206 if (flags & GLOB_NOESCAPE) { 207 while (bufnext < bufend && (c = *patnext++) != EOS) 208 *bufnext++ = c; 209 } else { 210 /* Protect the quoted characters. */ 211 while (bufnext < bufend && (c = *patnext++) != EOS) 212 if (c == QUOTE) { 213 if ((c = *patnext++) == EOS) { 214 c = QUOTE; 215 --patnext; 216 } 217 *bufnext++ = c | M_PROTECT; 218 } 219 else 220 *bufnext++ = c; 221 } 222 *bufnext = EOS; 223 224 if (flags & GLOB_BRACE) 225 return globexp1(pattern, patbuf, pglob, &limit); 226 else 227 return glob0(pattern, patbuf, pglob, &limit); 228 } 229 230 /* 231 * Expand recursively a glob {} pattern. When there is no more expansion 232 * invoke the standard globbing routine to glob the rest of the magic 233 * characters 234 */ 235 static int 236 globexp1(const char *orig, const Char *pattern, glob_t *pglob, struct glob_limit *limit) 237 { 238 const Char* ptr = pattern; 239 int rv; 240 241 _DIAGASSERT(pattern != NULL); 242 _DIAGASSERT(pglob != NULL); 243 244 if ((pglob->gl_flags & GLOB_LIMIT) && 245 limit->l_brace++ >= GLOB_LIMIT_BRACE) { 246 errno = 0; 247 return GLOB_NOSPACE; 248 } 249 250 /* Protect a single {}, for find(1), like csh */ 251 if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS) 252 return glob0(orig, pattern, pglob, limit); 253 254 while ((ptr = (const Char *) g_strchr(ptr, LBRACE)) != NULL) 255 if (!globexp2(orig, ptr, pattern, pglob, &rv, limit)) 256 return rv; 257 258 return glob0(orig, pattern, pglob, limit); 259 } 260 261 262 /* 263 * Recursive brace globbing helper. Tries to expand a single brace. 264 * If it succeeds then it invokes globexp1 with the new pattern. 265 * If it fails then it tries to glob the rest of the pattern and returns. 266 */ 267 static int 268 globexp2(const char *orig, const Char *ptr, const Char *pattern, glob_t *pglob, int *rv, 269 struct glob_limit *limit) 270 { 271 int i; 272 Char *lm, *ls; 273 const Char *pe, *pm, *pl; 274 Char patbuf[MAXPATHLEN + 1]; 275 276 _DIAGASSERT(ptr != NULL); 277 _DIAGASSERT(pattern != NULL); 278 _DIAGASSERT(pglob != NULL); 279 _DIAGASSERT(rv != NULL); 280 281 /* copy part up to the brace */ 282 for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 283 continue; 284 ls = lm; 285 286 /* Find the balanced brace */ 287 for (i = 0, pe = ++ptr; *pe; pe++) 288 if (*pe == LBRACKET) { 289 /* Ignore everything between [] */ 290 for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++) 291 continue; 292 if (*pe == EOS) { 293 /* 294 * We could not find a matching RBRACKET. 295 * Ignore and just look for RBRACE 296 */ 297 pe = pm; 298 } 299 } 300 else if (*pe == LBRACE) 301 i++; 302 else if (*pe == RBRACE) { 303 if (i == 0) 304 break; 305 i--; 306 } 307 308 /* Non matching braces; just glob the pattern */ 309 if (i != 0 || *pe == EOS) { 310 /* 311 * we use `pattern', not `patbuf' here so that that 312 * unbalanced braces are passed to the match 313 */ 314 *rv = glob0(orig, pattern, pglob, limit); 315 return 0; 316 } 317 318 for (i = 0, pl = pm = ptr; pm <= pe; pm++) { 319 switch (*pm) { 320 case LBRACKET: 321 /* Ignore everything between [] */ 322 for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++) 323 continue; 324 if (*pm == EOS) { 325 /* 326 * We could not find a matching RBRACKET. 327 * Ignore and just look for RBRACE 328 */ 329 pm = pl; 330 } 331 break; 332 333 case LBRACE: 334 i++; 335 break; 336 337 case RBRACE: 338 if (i) { 339 i--; 340 break; 341 } 342 /* FALLTHROUGH */ 343 case COMMA: 344 if (i && *pm == COMMA) 345 break; 346 else { 347 /* Append the current string */ 348 for (lm = ls; (pl < pm); *lm++ = *pl++) 349 continue; 350 /* 351 * Append the rest of the pattern after the 352 * closing brace 353 */ 354 for (pl = pe + 1; (*lm++ = *pl++) != EOS;) 355 continue; 356 357 /* Expand the current pattern */ 358 #ifdef DEBUG 359 qprintf("globexp2", patbuf); 360 #endif 361 *rv = globexp1(orig, patbuf, pglob, limit); 362 363 /* move after the comma, to the next string */ 364 pl = pm + 1; 365 } 366 break; 367 368 default: 369 break; 370 } 371 } 372 *rv = 0; 373 return 0; 374 } 375 376 377 378 /* 379 * expand tilde from the passwd file. 380 */ 381 static const Char * 382 globtilde(const Char *pattern, Char *patbuf, size_t patsize, glob_t *pglob) 383 { 384 struct passwd *pwd; 385 const char *h; 386 const Char *p; 387 Char *b; 388 char *d; 389 Char *pend = &patbuf[patsize / sizeof(Char)]; 390 #ifndef NO_GETPW_R 391 struct passwd pwres; 392 char pwbuf[1024]; 393 #endif 394 395 pend--; 396 397 _DIAGASSERT(pattern != NULL); 398 _DIAGASSERT(patbuf != NULL); 399 _DIAGASSERT(pglob != NULL); 400 401 if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE)) 402 return pattern; 403 404 /* Copy up to the end of the string or / */ 405 for (p = pattern + 1, d = (char *)(void *)patbuf; 406 d < (char *)(void *)pend && *p && *p != SLASH; 407 *d++ = *p++) 408 continue; 409 410 if (d == (char *)(void *)pend) 411 return NULL; 412 413 *d = EOS; 414 d = (char *)(void *)patbuf; 415 416 if (*d == EOS) { 417 /* 418 * handle a plain ~ or ~/ by expanding $HOME 419 * first and then trying the password file 420 */ 421 if ((h = getenv("HOME")) == NULL) { 422 #ifdef NO_GETPW_R 423 if ((pwd = getpwuid(getuid())) == NULL) 424 #else 425 if (getpwuid_r(getuid(), &pwres, pwbuf, sizeof(pwbuf), 426 &pwd) != 0 || pwd == NULL) 427 #endif 428 return pattern; 429 else 430 h = pwd->pw_dir; 431 } 432 } 433 else { 434 /* 435 * Expand a ~user 436 */ 437 #ifdef NO_GETPW_R 438 if ((pwd = getpwnam(d)) == NULL) 439 #else 440 if (getpwnam_r(d, &pwres, pwbuf, sizeof(pwbuf), &pwd) != 0 || 441 pwd == NULL) 442 #endif 443 return pattern; 444 else 445 h = pwd->pw_dir; 446 } 447 448 /* Copy the home directory */ 449 for (b = patbuf; b < pend && *h; *b++ = *h++) 450 continue; 451 452 if (b == pend) 453 return NULL; 454 455 /* Append the rest of the pattern */ 456 while (b < pend && (*b++ = *p++) != EOS) 457 continue; 458 459 if (b == pend) 460 return NULL; 461 462 return patbuf; 463 } 464 465 466 /* 467 * The main glob() routine: compiles the pattern (optionally processing 468 * quotes), calls glob1() to do the real pattern matching, and finally 469 * sorts the list (unless unsorted operation is requested). Returns 0 470 * if things went well, nonzero if errors occurred. It is not an error 471 * to find no matches. 472 */ 473 static int 474 glob0(const char *orig, const Char *pattern, glob_t *pglob, struct glob_limit *limit) 475 { 476 const Char *qpatnext; 477 int c, error; 478 __gl_size_t oldpathc; 479 Char *bufnext, patbuf[MAXPATHLEN+1]; 480 481 _DIAGASSERT(pattern != NULL); 482 _DIAGASSERT(pglob != NULL); 483 484 if ((qpatnext = globtilde(pattern, patbuf, sizeof(patbuf), 485 pglob)) == NULL) 486 return GLOB_ABEND; 487 oldpathc = pglob->gl_pathc; 488 bufnext = patbuf; 489 490 /* We don't need to check for buffer overflow any more. */ 491 while ((c = *qpatnext++) != EOS) { 492 switch (c) { 493 case LBRACKET: 494 c = *qpatnext; 495 if (c == NOT) 496 ++qpatnext; 497 if (*qpatnext == EOS || 498 g_strchr(qpatnext+1, RBRACKET) == NULL) { 499 *bufnext++ = LBRACKET; 500 if (c == NOT) 501 --qpatnext; 502 break; 503 } 504 *bufnext++ = M_SET; 505 if (c == NOT) 506 *bufnext++ = M_NOT; 507 c = *qpatnext++; 508 do { 509 *bufnext++ = CHAR(c); 510 if (*qpatnext == RANGE && 511 (c = qpatnext[1]) != RBRACKET) { 512 *bufnext++ = M_RNG; 513 *bufnext++ = CHAR(c); 514 qpatnext += 2; 515 } 516 } while ((c = *qpatnext++) != RBRACKET); 517 pglob->gl_flags |= GLOB_MAGCHAR; 518 *bufnext++ = M_END; 519 break; 520 case QUESTION: 521 pglob->gl_flags |= GLOB_MAGCHAR; 522 *bufnext++ = M_ONE; 523 break; 524 case STAR: 525 pglob->gl_flags |= GLOB_MAGCHAR; 526 /* collapse adjacent stars to one [or three if globstar] 527 * to avoid exponential behavior 528 */ 529 if (bufnext == patbuf || bufnext[-1] != M_ALL || 530 ((pglob->gl_flags & GLOB_STAR) != 0 && 531 (bufnext - 1 == patbuf || bufnext[-2] != M_ALL || 532 bufnext - 2 == patbuf || bufnext[-3] != M_ALL))) 533 *bufnext++ = M_ALL; 534 break; 535 default: 536 *bufnext++ = CHAR(c); 537 break; 538 } 539 } 540 *bufnext = EOS; 541 #ifdef DEBUG 542 qprintf("glob0", patbuf); 543 #endif 544 545 if ((error = glob1(patbuf, pglob, limit)) != 0) 546 return error; 547 548 if (pglob->gl_pathc == oldpathc) { 549 /* 550 * If there was no match we are going to append the pattern 551 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was 552 * specified and the pattern did not contain any magic 553 * characters GLOB_NOMAGIC is there just for compatibility 554 * with csh. 555 */ 556 if ((pglob->gl_flags & GLOB_NOCHECK) || 557 ((pglob->gl_flags & (GLOB_NOMAGIC|GLOB_MAGCHAR)) 558 == GLOB_NOMAGIC)) { 559 const u_char *patnext; 560 Char *bufend; 561 bufend = patbuf + MAXPATHLEN; 562 patnext = (const unsigned char *)orig; 563 bufnext = patbuf; 564 while (bufnext < bufend && (c = *patnext++) != EOS) 565 *bufnext++ = c; 566 567 *bufnext = EOS; 568 569 return globextend(patbuf, pglob, limit); 570 } else { 571 return GLOB_NOMATCH; 572 } 573 } else if (!(pglob->gl_flags & GLOB_NOSORT)) { 574 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 575 (size_t)pglob->gl_pathc - oldpathc, sizeof(char *), 576 compare); 577 } 578 579 return 0; 580 } 581 582 static int 583 compare(const void *p, const void *q) 584 { 585 586 _DIAGASSERT(p != NULL); 587 _DIAGASSERT(q != NULL); 588 589 return strcoll(*(const char * const *)p, *(const char * const *)q); 590 } 591 592 static int 593 glob1(Char *pattern, glob_t *pglob, struct glob_limit *limit) 594 { 595 Char pathbuf[MAXPATHLEN+1]; 596 597 _DIAGASSERT(pattern != NULL); 598 _DIAGASSERT(pglob != NULL); 599 600 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 601 if (*pattern == EOS) 602 return 0; 603 /* 604 * we save one character so that we can use ptr >= limit, 605 * in the general case when we are appending non nul chars only. 606 */ 607 return glob2(pathbuf, pathbuf, 608 pathbuf + (sizeof(pathbuf) / sizeof(*pathbuf)) - 1, pattern, 609 pglob, limit); 610 } 611 612 /* 613 * The functions glob2 and glob3 are mutually recursive; there is one level 614 * of recursion for each segment in the pattern that contains one or more 615 * meta characters. 616 */ 617 static int 618 glob2(Char *pathbuf, Char *pathend, Char *pathlim, const Char *pattern, 619 glob_t *pglob, struct glob_limit *limit) 620 { 621 __gl_stat_t sb; 622 const Char *p; 623 Char *q; 624 int anymeta; 625 Char *pend; 626 ptrdiff_t diff; 627 628 _DIAGASSERT(pathbuf != NULL); 629 _DIAGASSERT(pathend != NULL); 630 _DIAGASSERT(pattern != NULL); 631 _DIAGASSERT(pglob != NULL); 632 633 #ifdef DEBUG 634 qprintf("glob2", pathbuf); 635 #endif 636 /* 637 * Loop over pattern segments until end of pattern or until 638 * segment with meta character found. 639 */ 640 for (anymeta = 0;;) { 641 if (*pattern == EOS) { /* End of pattern? */ 642 *pathend = EOS; 643 if (g_lstat(pathbuf, &sb, pglob)) 644 return 0; 645 646 if ((pglob->gl_flags & GLOB_LIMIT) && 647 limit->l_stat++ >= GLOB_LIMIT_STAT) { 648 errno = 0; 649 *pathend++ = SEP; 650 *pathend = EOS; 651 return GLOB_NOSPACE; 652 } 653 if (((pglob->gl_flags & GLOB_MARK) && 654 pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) || 655 (S_ISLNK(sb.st_mode) && 656 (g_stat(pathbuf, &sb, pglob) == 0) && 657 S_ISDIR(sb.st_mode)))) { 658 if (pathend >= pathlim) 659 return GLOB_ABORTED; 660 *pathend++ = SEP; 661 *pathend = EOS; 662 } 663 ++pglob->gl_matchc; 664 return globextend(pathbuf, pglob, limit); 665 } 666 667 /* Find end of next segment, copy tentatively to pathend. */ 668 q = pathend; 669 p = pattern; 670 while (*p != EOS && *p != SEP) { 671 if (ismeta(*p)) 672 anymeta = 1; 673 if (q >= pathlim) 674 return GLOB_ABORTED; 675 *q++ = *p++; 676 } 677 678 /* 679 * No expansion, or path ends in slash-dot shash-dot-dot, 680 * do next segment. 681 */ 682 if (pglob->gl_flags & GLOB_PERIOD) { 683 for (pend = pathend; pend > pathbuf && pend[-1] == '/'; 684 pend--) 685 continue; 686 diff = pend - pathbuf; 687 } else { 688 /* XXX: GCC */ 689 diff = 0; 690 pend = pathend; 691 } 692 693 if ((!anymeta) || 694 ((pglob->gl_flags & GLOB_PERIOD) && 695 (diff >= 1 && pend[-1] == DOT) && 696 (diff >= 2 && (pend[-2] == SLASH || pend[-2] == DOT)) && 697 (diff < 3 || pend[-3] == SLASH))) { 698 pathend = q; 699 pattern = p; 700 while (*pattern == SEP) { 701 if (pathend >= pathlim) 702 return GLOB_ABORTED; 703 *pathend++ = *pattern++; 704 } 705 } else /* Need expansion, recurse. */ 706 return glob3(pathbuf, pathend, pathlim, pattern, p, 707 pattern, pglob, limit); 708 } 709 /* NOTREACHED */ 710 } 711 712 static int 713 glob3(Char *pathbuf, Char *pathend, Char *pathlim, const Char *pattern, 714 const Char *restpattern, const Char *pglobstar, glob_t *pglob, 715 struct glob_limit *limit) 716 { 717 struct dirent *dp; 718 DIR *dirp; 719 __gl_stat_t sbuf; 720 int error; 721 char buf[MAXPATHLEN]; 722 int globstar = 0; 723 int chase_symlinks = 0; 724 const Char *termstar = NULL; 725 726 /* 727 * The readdirfunc declaration can't be prototyped, because it is 728 * assigned, below, to two functions which are prototyped in glob.h 729 * and dirent.h as taking pointers to differently typed opaque 730 * structures. 731 */ 732 struct dirent *(*readdirfunc)(void *); 733 734 _DIAGASSERT(pathbuf != NULL); 735 _DIAGASSERT(pathend != NULL); 736 _DIAGASSERT(pattern != NULL); 737 _DIAGASSERT(restpattern != NULL); 738 _DIAGASSERT(pglob != NULL); 739 740 *pathend = EOS; 741 errno = 0; 742 743 while (pglobstar < restpattern) { 744 if ((pglobstar[0] & M_MASK) == M_ALL && 745 (pglobstar[1] & M_MASK) == M_ALL) { 746 globstar = 1; 747 chase_symlinks = (pglobstar[2] & M_MASK) == M_ALL; 748 termstar = pglobstar + (2 + chase_symlinks); 749 break; 750 } 751 pglobstar++; 752 } 753 754 if (globstar) { 755 error = pglobstar == pattern && termstar == restpattern ? 756 *restpattern == EOS ? 757 glob2(pathbuf, pathend, pathlim, restpattern - 1, pglob, 758 limit) : 759 glob2(pathbuf, pathend, pathlim, restpattern + 1, pglob, 760 limit) : 761 glob3(pathbuf, pathend, pathlim, pattern, restpattern, 762 termstar, pglob, limit); 763 if (error) 764 return error; 765 *pathend = EOS; 766 } 767 768 if (*pathbuf && (g_lstat(pathbuf, &sbuf, pglob) || 769 !S_ISDIR(sbuf.st_mode) 770 #ifdef S_IFLINK 771 && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode)) 772 #endif 773 )) 774 return 0; 775 776 if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 777 if (pglob->gl_errfunc) { 778 if (g_Ctoc(pathbuf, buf, sizeof(buf))) 779 return GLOB_ABORTED; 780 if (pglob->gl_errfunc(buf, errno) || 781 pglob->gl_flags & GLOB_ERR) 782 return GLOB_ABORTED; 783 } 784 /* 785 * Posix/XOpen: glob should return when it encounters a 786 * directory that it cannot open or read 787 * XXX: Should we ignore ENOTDIR and ENOENT though? 788 * I think that Posix had in mind EPERM... 789 */ 790 if (pglob->gl_flags & GLOB_ERR) 791 return GLOB_ABORTED; 792 793 return 0; 794 } 795 796 error = 0; 797 798 /* Search directory for matching names. */ 799 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 800 readdirfunc = pglob->gl_readdir; 801 else 802 readdirfunc = (struct dirent *(*)(void *)) readdir; 803 while ((dp = (*readdirfunc)(dirp)) != NULL) { 804 u_char *sc; 805 Char *dc; 806 807 if ((pglob->gl_flags & GLOB_LIMIT) && 808 limit->l_readdir++ >= GLOB_LIMIT_READDIR) { 809 errno = 0; 810 *pathend++ = SEP; 811 *pathend = EOS; 812 error = GLOB_NOSPACE; 813 break; 814 } 815 816 /* 817 * Initial DOT must be matched literally, unless we have 818 * GLOB_PERIOD set. 819 */ 820 if ((pglob->gl_flags & GLOB_PERIOD) == 0) 821 if (dp->d_name[0] == DOT && *pattern != DOT) 822 continue; 823 /* 824 * If GLOB_NO_DOTDIRS is set, . and .. vanish. 825 */ 826 if ((pglob->gl_flags & GLOB_NO_DOTDIRS) && 827 (dp->d_name[0] == DOT) && 828 ((dp->d_name[1] == EOS) || 829 ((dp->d_name[1] == DOT) && (dp->d_name[2] == EOS)))) 830 continue; 831 /* 832 * The resulting string contains EOS, so we can 833 * use the pathlim character, if it is the nul 834 */ 835 for (sc = (u_char *) dp->d_name, dc = pathend; 836 dc <= pathlim && (*dc++ = *sc++) != EOS;) 837 continue; 838 839 /* 840 * Have we filled the buffer without seeing EOS? 841 */ 842 if (dc > pathlim && *pathlim != EOS) { 843 /* 844 * Abort when requested by caller, otherwise 845 * reset pathend back to last SEP and continue 846 * with next dir entry. 847 */ 848 if (pglob->gl_flags & GLOB_ERR) { 849 error = GLOB_ABORTED; 850 break; 851 } 852 else { 853 *pathend = EOS; 854 continue; 855 } 856 } 857 858 if (globstar) { 859 #ifdef S_IFLNK 860 if (!chase_symlinks && 861 (g_lstat(pathbuf, &sbuf, pglob) || 862 S_ISLNK(sbuf.st_mode))) 863 continue; 864 #endif 865 866 if (!match(pathend, pattern, termstar)) 867 continue; 868 869 if (--dc < pathlim - 2) 870 *dc++ = SEP; 871 *dc = EOS; 872 error = glob2(pathbuf, dc, pathlim, pglobstar, 873 pglob, limit); 874 if (error) 875 break; 876 *pathend = EOS; 877 } else { 878 if (!match(pathend, pattern, restpattern)) { 879 *pathend = EOS; 880 continue; 881 } 882 error = glob2(pathbuf, --dc, pathlim, restpattern, 883 pglob, limit); 884 if (error) 885 break; 886 } 887 } 888 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 889 (*pglob->gl_closedir)(dirp); 890 else 891 closedir(dirp); 892 893 /* 894 * Again Posix X/Open issue with regards to error handling. 895 */ 896 if ((error || errno) && (pglob->gl_flags & GLOB_ERR)) 897 return GLOB_ABORTED; 898 899 return error; 900 } 901 902 903 /* 904 * Extend the gl_pathv member of a glob_t structure to accommodate a new item, 905 * add the new item, and update gl_pathc. 906 * 907 * This assumes the BSD realloc, which only copies the block when its size 908 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 909 * behavior. 910 * 911 * Return 0 if new item added, error code if memory couldn't be allocated. 912 * 913 * Invariant of the glob_t structure: 914 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 915 * gl_pathv points to (gl_offs + gl_pathc + 1) items. 916 */ 917 static int 918 globextend(const Char *path, glob_t *pglob, struct glob_limit *limit) 919 { 920 char **pathv; 921 size_t i, newsize, len; 922 char *copy; 923 const Char *p; 924 925 _DIAGASSERT(path != NULL); 926 _DIAGASSERT(pglob != NULL); 927 928 newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 929 if ((pglob->gl_flags & GLOB_LIMIT) && 930 newsize > GLOB_LIMIT_PATH * sizeof(*pathv)) 931 goto nospace; 932 pathv = pglob->gl_pathv ? realloc(pglob->gl_pathv, newsize) : 933 malloc(newsize); 934 if (pathv == NULL) 935 return GLOB_NOSPACE; 936 937 if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 938 /* first time around -- clear initial gl_offs items */ 939 pathv += pglob->gl_offs; 940 for (i = pglob->gl_offs + 1; --i > 0; ) 941 *--pathv = NULL; 942 } 943 pglob->gl_pathv = pathv; 944 945 for (p = path; *p++;) 946 continue; 947 len = (size_t)(p - path); 948 limit->l_string += len; 949 if ((copy = malloc(len)) != NULL) { 950 if (g_Ctoc(path, copy, len)) { 951 free(copy); 952 return GLOB_ABORTED; 953 } 954 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 955 } 956 pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 957 958 if ((pglob->gl_flags & GLOB_LIMIT) && 959 (newsize + limit->l_string) >= GLOB_LIMIT_STRING) 960 goto nospace; 961 962 return copy == NULL ? GLOB_NOSPACE : 0; 963 nospace: 964 errno = 0; 965 return GLOB_NOSPACE; 966 } 967 968 969 /* 970 * pattern matching function for filenames. Each occurrence of the * 971 * pattern causes a recursion level. 972 */ 973 static int 974 match(const Char *name, const Char *pat, const Char *patend) 975 { 976 int ok, negate_range; 977 Char c, k; 978 979 _DIAGASSERT(name != NULL); 980 _DIAGASSERT(pat != NULL); 981 _DIAGASSERT(patend != NULL); 982 983 while (pat < patend) { 984 c = *pat++; 985 switch (c & M_MASK) { 986 case M_ALL: 987 while (pat < patend && (*pat & M_MASK) == M_ALL) 988 pat++; /* eat consecutive '*' */ 989 if (pat == patend) 990 return 1; 991 for (; !match(name, pat, patend); name++) 992 if (*name == EOS) 993 return 0; 994 return 1; 995 case M_ONE: 996 if (*name++ == EOS) 997 return 0; 998 break; 999 case M_SET: 1000 ok = 0; 1001 if ((k = *name++) == EOS) 1002 return 0; 1003 if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS) 1004 ++pat; 1005 while (((c = *pat++) & M_MASK) != M_END) 1006 if ((*pat & M_MASK) == M_RNG) { 1007 if (c <= k && k <= pat[1]) 1008 ok = 1; 1009 pat += 2; 1010 } else if (c == k) 1011 ok = 1; 1012 if (ok == negate_range) 1013 return 0; 1014 break; 1015 default: 1016 if (*name++ != c) 1017 return 0; 1018 break; 1019 } 1020 } 1021 return *name == EOS; 1022 } 1023 1024 /* Free allocated data belonging to a glob_t structure. */ 1025 void 1026 globfree(glob_t *pglob) 1027 { 1028 size_t i; 1029 char **pp; 1030 1031 _DIAGASSERT(pglob != NULL); 1032 1033 if (pglob->gl_pathv != NULL) { 1034 pp = pglob->gl_pathv + pglob->gl_offs; 1035 for (i = pglob->gl_pathc; i--; ++pp) 1036 if (*pp) 1037 free(*pp); 1038 free(pglob->gl_pathv); 1039 pglob->gl_pathv = NULL; 1040 pglob->gl_pathc = 0; 1041 } 1042 } 1043 1044 #ifndef __LIBC12_SOURCE__ 1045 int 1046 glob_pattern_p(const char *pattern, int quote) 1047 { 1048 int range = 0; 1049 1050 for (; *pattern; pattern++) 1051 switch (*pattern) { 1052 case QUESTION: 1053 case STAR: 1054 return 1; 1055 1056 case QUOTE: 1057 if (quote && pattern[1] != EOS) 1058 ++pattern; 1059 break; 1060 1061 case LBRACKET: 1062 range = 1; 1063 break; 1064 1065 case RBRACKET: 1066 if (range) 1067 return 1; 1068 break; 1069 default: 1070 break; 1071 } 1072 1073 return 0; 1074 } 1075 #endif 1076 1077 static DIR * 1078 g_opendir(Char *str, glob_t *pglob) 1079 { 1080 char buf[MAXPATHLEN]; 1081 1082 _DIAGASSERT(str != NULL); 1083 _DIAGASSERT(pglob != NULL); 1084 1085 if (!*str) 1086 (void)strlcpy(buf, ".", sizeof(buf)); 1087 else { 1088 if (g_Ctoc(str, buf, sizeof(buf))) 1089 return NULL; 1090 } 1091 1092 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 1093 return (*pglob->gl_opendir)(buf); 1094 1095 return opendir(buf); 1096 } 1097 1098 static int 1099 g_lstat(Char *fn, __gl_stat_t *sb, glob_t *pglob) 1100 { 1101 char buf[MAXPATHLEN]; 1102 1103 _DIAGASSERT(fn != NULL); 1104 _DIAGASSERT(sb != NULL); 1105 _DIAGASSERT(pglob != NULL); 1106 1107 if (g_Ctoc(fn, buf, sizeof(buf))) 1108 return -1; 1109 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 1110 return (*pglob->gl_lstat)(buf, sb); 1111 return lstat(buf, sb); 1112 } 1113 1114 static int 1115 g_stat(Char *fn, __gl_stat_t *sb, glob_t *pglob) 1116 { 1117 char buf[MAXPATHLEN]; 1118 1119 _DIAGASSERT(fn != NULL); 1120 _DIAGASSERT(sb != NULL); 1121 _DIAGASSERT(pglob != NULL); 1122 1123 if (g_Ctoc(fn, buf, sizeof(buf))) 1124 return -1; 1125 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 1126 return (*pglob->gl_stat)(buf, sb); 1127 return stat(buf, sb); 1128 } 1129 1130 static Char * 1131 g_strchr(const Char *str, int ch) 1132 { 1133 1134 _DIAGASSERT(str != NULL); 1135 1136 do { 1137 if (*str == ch) 1138 return __UNCONST(str); 1139 } while (*str++); 1140 return NULL; 1141 } 1142 1143 static int 1144 g_Ctoc(const Char *str, char *buf, size_t len) 1145 { 1146 char *dc; 1147 1148 _DIAGASSERT(str != NULL); 1149 _DIAGASSERT(buf != NULL); 1150 1151 if (len == 0) 1152 return 1; 1153 1154 for (dc = buf; len && (*dc++ = *str++) != EOS; len--) 1155 continue; 1156 1157 return len == 0; 1158 } 1159 1160 #ifdef DEBUG 1161 static void 1162 qprintf(const char *str, Char *s) 1163 { 1164 Char *p; 1165 1166 _DIAGASSERT(str != NULL); 1167 _DIAGASSERT(s != NULL); 1168 1169 (void)printf("%s:\n", str); 1170 for (p = s; *p; p++) 1171 (void)printf("%c", CHAR(*p)); 1172 (void)printf("\n"); 1173 for (p = s; *p; p++) 1174 (void)printf("%c", *p & M_PROTECT ? '"' : ' '); 1175 (void)printf("\n"); 1176 for (p = s; *p; p++) 1177 (void)printf("%c", ismeta(*p) ? '_' : ' '); 1178 (void)printf("\n"); 1179 } 1180 #endif 1181