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