git.gag.com Git - debian/sudo/blob - glob.c

   1 /*
   2  * Copyright (c) 2008-2010 Todd C. Miller <Todd.Miller@courtesan.com>
   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  *      @(#)glob.c      8.3 (Berkeley) 10/13/93
  34  */
  35
  36 /*
  37  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  38  *
  39  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  40  *
  41  * Optional extra services, controlled by flags not defined by POSIX:
  42  *
  43  * GLOB_MAGCHAR:
  44  *      Set in gl_flags if pattern contained a globbing character.
  45  * GLOB_TILDE:
  46  *      expand ~user/foo to the /home/dir/of/user/foo
  47  * GLOB_BRACE:
  48  *      expand {1,2}{a,b} to 1a 1b 2a 2b
  49  * gl_matchc:
  50  *      Number of matches in the current invocation of glob.
  51  */
  52
  53 #include <config.h>
  54
  55 #include <sys/param.h>
  56 #include <sys/stat.h>
  57
  58 #include <stdio.h>
  59 #ifdef STDC_HEADERS
  60 # include <stdlib.h>
  61 # include <stddef.h>
  62 #else
  63 # ifdef HAVE_STDLIB_H
  64 #  include <stdlib.h>
  65 # endif
  66 #endif /* STDC_HEADERS */
  67 #if defined(HAVE_MALLOC_H) && !defined(STDC_HEADERS)
  68 # include <malloc.h>
  69 #endif /* HAVE_MALLOC_H && !STDC_HEADERS */
  70 #ifdef HAVE_STRING_H
  71 # include <string.h>
  72 #endif /* HAVE_STRING_H */
  73 #ifdef HAVE_STRINGS_H
  74 # include <strings.h>
  75 #endif /* HAVE_STRINGS_H */
  76 #ifdef HAVE_UNISTD_H
  77 # include <unistd.h>
  78 #endif /* HAVE_UNISTD_H */
  79 #include <ctype.h>
  80 #ifdef HAVE_DIRENT_H
  81 # include <dirent.h>
  82 #else
  83 # define dirent direct
  84 # ifdef HAVE_SYS_NDIR_H
  85 #  include <sys/ndir.h>
  86 # endif
  87 # ifdef HAVE_SYS_DIR_H
  88 #  include <sys/dir.h>
  89 # endif
  90 # ifdef HAVE_NDIR_H
  91 #  include <ndir.h>
  92 # endif
  93 #endif
  94 #include <errno.h>
  95 #include <limits.h>
  96 #include <pwd.h>
  97
  98 #include <compat.h>
  99 #include "emul/glob.h"
 100 #include "emul/charclass.h"
 101
 102 #define DOLLAR          '$'
 103 #define DOT             '.'
 104 #define EOS             '\0'
 105 #define LBRACKET        '['
 106 #define NOT             '!'
 107 #define QUESTION        '?'
 108 #define QUOTE           '\\'
 109 #define RANGE           '-'
 110 #define RBRACKET        ']'
 111 #define SEP             '/'
 112 #define STAR            '*'
 113 #define TILDE           '~'
 114 #define UNDERSCORE      '_'
 115 #define LBRACE          '{'
 116 #define RBRACE          '}'
 117 #define SLASH           '/'
 118 #define COMMA           ','
 119
 120 #ifndef DEBUG
 121
 122 #define M_QUOTE         0x8000
 123 #define M_PROTECT       0x4000
 124 #define M_MASK          0xffff
 125 #define M_ASCII         0x00ff
 126
 127 typedef unsigned short Char;
 128
 129 #else
 130
 131 #define M_QUOTE         0x80
 132 #define M_PROTECT       0x40
 133 #define M_MASK          0xff
 134 #define M_ASCII         0x7f
 135
 136 typedef char Char;
 137
 138 #endif
 139
 140
 141 #define CHAR(c)         ((Char)((c)&M_ASCII))
 142 #define META(c)         ((Char)((c)|M_QUOTE))
 143 #define M_ALL           META('*')
 144 #define M_END           META(']')
 145 #define M_NOT           META('!')
 146 #define M_ONE           META('?')
 147 #define M_RNG           META('-')
 148 #define M_SET           META('[')
 149 #define M_CLASS         META(':')
 150 #define ismeta(c)       (((c)&M_QUOTE) != 0)
 151
 152
 153 static int       compare __P((const void *, const void *));
 154 static int       g_Ctoc __P((const Char *, char *, unsigned int));
 155 static int       g_lstat __P((Char *, struct stat *, glob_t *));
 156 static DIR      *g_opendir __P((Char *, glob_t *));
 157 static Char     *g_strchr __P((const Char *, int));
 158 static int       g_strncmp __P((const Char *, const char *, size_t));
 159 static int       g_stat __P((Char *, struct stat *, glob_t *));
 160 static int       glob0 __P((const Char *, glob_t *));
 161 static int       glob1 __P((Char *, Char *, glob_t *));
 162 static int       glob2 __P((Char *, Char *, Char *, Char *, Char *, Char *,
 163                     glob_t *));
 164 static int       glob3 __P((Char *, Char *, Char *, Char *, Char *, Char *,
 165                     Char *, Char *, glob_t *));
 166 static int       globextend __P((const Char *, glob_t *));
 167 static const Char *
 168                  globtilde __P((const Char *, Char *, size_t, glob_t *));
 169 static int       globexp1 __P((const Char *, glob_t *));
 170 static int       globexp2 __P((const Char *, const Char *, glob_t *, int *));
 171 static int       match __P((Char *, Char *, Char *));
 172 #ifdef DEBUG
 173 static void      qprintf __P((const char *, Char *));
 174 #endif
 175
 176 extern struct passwd *sudo_getpwnam __P((const char *));
 177 extern struct passwd *sudo_getpwuid __P((uid_t));
 178
 179 int
 180 glob(pattern, flags, errfunc, pglob)
 181         const char *pattern;
 182         int flags, (*errfunc) __P((const char *, int));
 183         glob_t *pglob;
 184 {
 185         const unsigned char *patnext;
 186         int c;
 187         Char *bufnext, *bufend, patbuf[PATH_MAX];
 188
 189         patnext = (unsigned char *) pattern;
 190         if (!(flags & GLOB_APPEND)) {
 191                 pglob->gl_pathc = 0;
 192                 pglob->gl_pathv = NULL;
 193                 if (!(flags & GLOB_DOOFFS))
 194                         pglob->gl_offs = 0;
 195         }
 196         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 197         pglob->gl_errfunc = errfunc;
 198         pglob->gl_matchc = 0;
 199
 200         bufnext = patbuf;
 201         bufend = bufnext + PATH_MAX - 1;
 202         if (flags & GLOB_NOESCAPE)
 203                 while (bufnext < bufend && (c = *patnext++) != EOS)
 204                         *bufnext++ = c;
 205         else {
 206                 /* Protect the quoted characters. */
 207                 while (bufnext < bufend && (c = *patnext++) != EOS)
 208                         if (c == QUOTE) {
 209                                 if ((c = *patnext++) == EOS) {
 210                                         c = QUOTE;
 211                                         --patnext;
 212                                 }
 213                                 *bufnext++ = c | M_PROTECT;
 214                         } else
 215                                 *bufnext++ = c;
 216         }
 217         *bufnext = EOS;
 218
 219         if (flags & GLOB_BRACE)
 220                 return globexp1(patbuf, pglob);
 221         else
 222                 return glob0(patbuf, pglob);
 223 }
 224
 225 /*
 226  * Expand recursively a glob {} pattern. When there is no more expansion
 227  * invoke the standard globbing routine to glob the rest of the magic
 228  * characters
 229  */
 230 static int
 231 globexp1(pattern, pglob)
 232         const Char *pattern;
 233         glob_t *pglob;
 234 {
 235         const Char* ptr = pattern;
 236         int rv;
 237
 238         /* Protect a single {}, for find(1), like csh */
 239         if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
 240                 return glob0(pattern, pglob);
 241
 242         while ((ptr = (const Char *) g_strchr(ptr, LBRACE)) != NULL)
 243                 if (!globexp2(ptr, pattern, pglob, &rv))
 244                         return rv;
 245
 246         return glob0(pattern, pglob);
 247 }
 248
 249
 250 /*
 251  * Recursive brace globbing helper. Tries to expand a single brace.
 252  * If it succeeds then it invokes globexp1 with the new pattern.
 253  * If it fails then it tries to glob the rest of the pattern and returns.
 254  */
 255 static int
 256 globexp2(ptr, pattern, pglob, rv)
 257         const Char *ptr, *pattern;
 258         glob_t *pglob;
 259         int *rv;
 260 {
 261         int     i;
 262         Char   *lm, *ls;
 263         const Char *pe, *pm, *pl;
 264         Char    patbuf[PATH_MAX];
 265
 266         /* copy part up to the brace */
 267         for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
 268                 continue;
 269         *lm = EOS;
 270         ls = lm;
 271
 272         /* Find the balanced brace */
 273         for (i = 0, pe = ++ptr; *pe; pe++)
 274                 if (*pe == LBRACKET) {
 275                         /* Ignore everything between [] */
 276                         for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
 277                                 continue;
 278                         if (*pe == EOS) {
 279                                 /*
 280                                  * We could not find a matching RBRACKET.
 281                                  * Ignore and just look for RBRACE
 282                                  */
 283                                 pe = pm;
 284                         }
 285                 } else if (*pe == LBRACE)
 286                         i++;
 287                 else if (*pe == RBRACE) {
 288                         if (i == 0)
 289                                 break;
 290                         i--;
 291                 }
 292
 293         /* Non matching braces; just glob the pattern */
 294         if (i != 0 || *pe == EOS) {
 295                 *rv = glob0(patbuf, pglob);
 296                 return 0;
 297         }
 298
 299         for (i = 0, pl = pm = ptr; pm <= pe; pm++) {
 300                 switch (*pm) {
 301                 case LBRACKET:
 302                         /* Ignore everything between [] */
 303                         for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
 304                                 continue;
 305                         if (*pm == EOS) {
 306                                 /*
 307                                  * We could not find a matching RBRACKET.
 308                                  * Ignore and just look for RBRACE
 309                                  */
 310                                 pm = pl;
 311                         }
 312                         break;
 313
 314                 case LBRACE:
 315                         i++;
 316                         break;
 317
 318                 case RBRACE:
 319                         if (i) {
 320                                 i--;
 321                                 break;
 322                         }
 323                         /* FALLTHROUGH */
 324                 case COMMA:
 325                         if (i && *pm == COMMA)
 326                                 break;
 327                         else {
 328                                 /* Append the current string */
 329                                 for (lm = ls; (pl < pm); *lm++ = *pl++)
 330                                         continue;
 331
 332                                 /*
 333                                  * Append the rest of the pattern after the
 334                                  * closing brace
 335                                  */
 336                                 for (pl = pe + 1; (*lm++ = *pl++) != EOS; )
 337                                         continue;
 338
 339                                 /* Expand the current pattern */
 340 #ifdef DEBUG
 341                                 qprintf("globexp2:", patbuf);
 342 #endif
 343                                 *rv = globexp1(patbuf, pglob);
 344
 345                                 /* move after the comma, to the next string */
 346                                 pl = pm + 1;
 347                         }
 348                         break;
 349
 350                 default:
 351                         break;
 352                 }
 353         }
 354         *rv = 0;
 355         return 0;
 356 }
 357
 358
 359
 360 /*
 361  * expand tilde from the passwd file.
 362  */
 363 static const Char *
 364 globtilde(pattern, patbuf, patbuf_len, pglob)
 365         const Char *pattern;
 366         Char *patbuf;
 367         size_t patbuf_len;
 368         glob_t *pglob;
 369 {
 370         struct passwd *pwd;
 371         char *h;
 372         const Char *p;
 373         Char *b, *eb;
 374
 375         if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
 376                 return pattern;
 377
 378         /* Copy up to the end of the string or / */
 379         eb = &patbuf[patbuf_len - 1];
 380         for (p = pattern + 1, h = (char *) patbuf;
 381             h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
 382                 continue;
 383
 384         *h = EOS;
 385
 386         if (((char *) patbuf)[0] == EOS) {
 387                 /*
 388                  * handle a plain ~ or ~/ by expanding $HOME
 389                  * first and then trying the password file
 390                  */
 391                 if ((h = getenv("HOME")) == NULL) {
 392                         if ((pwd = sudo_getpwuid(getuid())) == NULL)
 393                                 return pattern;
 394                         else
 395                                 h = pwd->pw_dir;
 396                 }
 397         } else {
 398                 /*
 399                  * Expand a ~user
 400                  */
 401                 if ((pwd = sudo_getpwnam((char*) patbuf)) == NULL)
 402                         return pattern;
 403                 else
 404                         h = pwd->pw_dir;
 405         }
 406
 407         /* Copy the home directory */
 408         for (b = patbuf; b < eb && *h; *b++ = *h++)
 409                 continue;
 410
 411         /* Append the rest of the pattern */
 412         while (b < eb && (*b++ = *p++) != EOS)
 413                 continue;
 414         *b = EOS;
 415
 416         return patbuf;
 417 }
 418
 419 static int
 420 g_strncmp(s1, s2, n)
 421         const Char *s1;
 422         const char *s2;
 423         size_t n;
 424 {
 425         int rv = 0;
 426
 427         while (n--) {
 428                 rv = *(Char *)s1 - *(const unsigned char *)s2++;
 429                 if (rv)
 430                         break;
 431                 if (*s1++ == '\0')
 432                         break;
 433         }
 434         return rv;
 435 }
 436
 437 static int
 438 g_charclass(patternp, bufnextp)
 439         const Char **patternp;
 440         Char **bufnextp;
 441 {
 442         const Char *pattern = *patternp + 1;
 443         Char *bufnext = *bufnextp;
 444         const Char *colon;
 445         struct cclass *cc;
 446         size_t len;
 447
 448         if ((colon = g_strchr(pattern, ':')) == NULL || colon[1] != ']')
 449                 return 1;       /* not a character class */
 450
 451         len = (size_t)(colon - pattern);
 452         for (cc = cclasses; cc->name != NULL; cc++) {
 453                 if (!g_strncmp(pattern, cc->name, len) && cc->name[len] == '\0')
 454                         break;
 455         }
 456         if (cc->name == NULL)
 457                 return -1;      /* invalid character class */
 458         *bufnext++ = M_CLASS;
 459         *bufnext++ = (Char)(cc - &cclasses[0]);
 460         *bufnextp = bufnext;
 461         *patternp += len + 3;
 462
 463         return 0;
 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(pattern, pglob)
 475         const Char *pattern;
 476         glob_t *pglob;
 477 {
 478         const Char *qpatnext;
 479         int c, err, oldpathc;
 480         Char *bufnext, patbuf[PATH_MAX];
 481
 482         qpatnext = globtilde(pattern, patbuf, PATH_MAX, pglob);
 483         oldpathc = pglob->gl_pathc;
 484         bufnext = patbuf;
 485
 486         /* We don't need to check for buffer overflow any more. */
 487         while ((c = *qpatnext++) != EOS) {
 488                 switch (c) {
 489                 case LBRACKET:
 490                         c = *qpatnext;
 491                         if (c == NOT)
 492                                 ++qpatnext;
 493                         if (*qpatnext == EOS ||
 494                             g_strchr(qpatnext+1, RBRACKET) == NULL) {
 495                                 *bufnext++ = LBRACKET;
 496                                 if (c == NOT)
 497                                         --qpatnext;
 498                                 break;
 499                         }
 500                         *bufnext++ = M_SET;
 501                         if (c == NOT)
 502                                 *bufnext++ = M_NOT;
 503                         c = *qpatnext++;
 504                         do {
 505                                 if (c == LBRACKET && *qpatnext == ':') {
 506                                         do {
 507                                                 err = g_charclass(&qpatnext,
 508                                                     &bufnext);
 509                                                 if (err)
 510                                                         break;
 511                                                 c = *qpatnext++;
 512                                         } while (c == LBRACKET && *qpatnext == ':');
 513                                         if (err == -1 &&
 514                                             !(pglob->gl_flags & GLOB_NOCHECK))
 515                                                 return GLOB_NOMATCH;
 516                                         if (c == RBRACKET)
 517                                                 break;
 518                                 }
 519                                 *bufnext++ = CHAR(c);
 520                                 if (*qpatnext == RANGE &&
 521                                     (c = qpatnext[1]) != RBRACKET) {
 522                                         *bufnext++ = M_RNG;
 523                                         *bufnext++ = CHAR(c);
 524                                         qpatnext += 2;
 525                                 }
 526                         } while ((c = *qpatnext++) != RBRACKET);
 527                         pglob->gl_flags |= GLOB_MAGCHAR;
 528                         *bufnext++ = M_END;
 529                         break;
 530                 case QUESTION:
 531                         pglob->gl_flags |= GLOB_MAGCHAR;
 532                         *bufnext++ = M_ONE;
 533                         break;
 534                 case STAR:
 535                         pglob->gl_flags |= GLOB_MAGCHAR;
 536                         /* collapse adjacent stars to one,
 537                          * to avoid exponential behavior
 538                          */
 539                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
 540                                 *bufnext++ = M_ALL;
 541                         break;
 542                 default:
 543                         *bufnext++ = CHAR(c);
 544                         break;
 545                 }
 546         }
 547         *bufnext = EOS;
 548 #ifdef DEBUG
 549         qprintf("glob0:", patbuf);
 550 #endif
 551
 552         if ((err = glob1(patbuf, patbuf + PATH_MAX - 1, pglob)) != 0)
 553                 return(err);
 554
 555         /*
 556          * If there was no match we are going to append the pattern
 557          * if GLOB_NOCHECK was specified.
 558          */
 559         if (pglob->gl_pathc == oldpathc) {
 560                 if (pglob->gl_flags & GLOB_NOCHECK)
 561                         return(globextend(pattern, pglob));
 562                 else
 563                         return(GLOB_NOMATCH);
 564         }
 565         if (!(pglob->gl_flags & GLOB_NOSORT))
 566                 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 567                     pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 568         return(0);
 569 }
 570
 571 static int
 572 compare(p, q)
 573         const void *p, *q;
 574 {
 575         return(strcmp(*(char **)p, *(char **)q));
 576 }
 577
 578 static int
 579 glob1(pattern, pattern_last,  pglob)
 580         Char *pattern, *pattern_last;
 581         glob_t *pglob;
 582 {
 583         Char pathbuf[PATH_MAX];
 584
 585         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
 586         if (*pattern == EOS)
 587                 return(0);
 588         return(glob2(pathbuf, pathbuf + PATH_MAX - 1,
 589             pathbuf, pathbuf + PATH_MAX - 1,
 590             pattern, pattern_last, pglob));
 591 }
 592
 593 /*
 594  * The functions glob2 and glob3 are mutually recursive; there is one level
 595  * of recursion for each segment in the pattern that contains one or more
 596  * meta characters.
 597  */
 598 static int
 599 glob2(pathbuf, pathbuf_last, pathend, pathend_last, pattern, pattern_last, pglob)
 600         Char *pathbuf, *pathbuf_last;
 601         Char *pathend, *pathend_last;
 602         Char *pattern, *pattern_last;
 603         glob_t *pglob;
 604 {
 605         struct stat sb;
 606         Char *p, *q;
 607         int anymeta;
 608
 609         /*
 610          * Loop over pattern segments until end of pattern or until
 611          * segment with meta character found.
 612          */
 613         for (anymeta = 0;;) {
 614                 if (*pattern == EOS) {          /* End of pattern? */
 615                         *pathend = EOS;
 616                         if (g_lstat(pathbuf, &sb, pglob))
 617                                 return(0);
 618
 619                         if (((pglob->gl_flags & GLOB_MARK) &&
 620                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
 621                             (S_ISLNK(sb.st_mode) &&
 622                             (g_stat(pathbuf, &sb, pglob) == 0) &&
 623                             S_ISDIR(sb.st_mode)))) {
 624                                 if (pathend+1 > pathend_last)
 625                                         return (1);
 626                                 *pathend++ = SEP;
 627                                 *pathend = EOS;
 628                         }
 629                         ++pglob->gl_matchc;
 630                         return(globextend(pathbuf, pglob));
 631                 }
 632
 633                 /* Find end of next segment, copy tentatively to pathend. */
 634                 q = pathend;
 635                 p = pattern;
 636                 while (*p != EOS && *p != SEP) {
 637                         if (ismeta(*p))
 638                                 anymeta = 1;
 639                         if (q+1 > pathend_last)
 640                                 return (1);
 641                         *q++ = *p++;
 642                 }
 643
 644                 if (!anymeta) {         /* No expansion, do next segment. */
 645                         pathend = q;
 646                         pattern = p;
 647                         while (*pattern == SEP) {
 648                                 if (pathend+1 > pathend_last)
 649                                         return (1);
 650                                 *pathend++ = *pattern++;
 651                         }
 652                 } else
 653                         /* Need expansion, recurse. */
 654                         return(glob3(pathbuf, pathbuf_last, pathend,
 655                             pathend_last, pattern, pattern_last,
 656                             p, pattern_last, pglob));
 657         }
 658         /* NOTREACHED */
 659 }
 660
 661 static int
 662 glob3(pathbuf, pathbuf_last, pathend, pathend_last, pattern, pattern_last,
 663     restpattern, restpattern_last, pglob)
 664         Char *pathbuf, *pathbuf_last, *pathend, *pathend_last;
 665         Char *pattern, *pattern_last, *restpattern, *restpattern_last;
 666         glob_t *pglob;
 667 {
 668         struct dirent *dp;
 669         DIR *dirp;
 670         int err;
 671         char buf[PATH_MAX];
 672
 673         if (pathend > pathend_last)
 674                 return (1);
 675         *pathend = EOS;
 676         errno = 0;
 677
 678         if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
 679                 /* TODO: don't call for ENOENT or ENOTDIR? */
 680                 if (pglob->gl_errfunc) {
 681                         if (g_Ctoc(pathbuf, buf, sizeof(buf)))
 682                                 return(GLOB_ABORTED);
 683                         if (pglob->gl_errfunc(buf, errno) ||
 684                             pglob->gl_flags & GLOB_ERR)
 685                                 return(GLOB_ABORTED);
 686                 }
 687                 return(0);
 688         }
 689
 690         err = 0;
 691
 692         /* Search directory for matching names. */
 693         while ((dp = readdir(dirp))) {
 694                 unsigned char *sc;
 695                 Char *dc;
 696
 697                 /* Initial DOT must be matched literally. */
 698                 if (dp->d_name[0] == DOT && *pattern != DOT)
 699                         continue;
 700                 dc = pathend;
 701                 sc = (unsigned char *) dp->d_name;
 702                 while (dc < pathend_last && (*dc++ = *sc++) != EOS)
 703                         continue;
 704                 if (dc >= pathend_last) {
 705                         *dc = EOS;
 706                         err = 1;
 707                         break;
 708                 }
 709
 710                 if (!match(pathend, pattern, restpattern)) {
 711                         *pathend = EOS;
 712                         continue;
 713                 }
 714                 err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
 715                     restpattern, restpattern_last, pglob);
 716                 if (err)
 717                         break;
 718         }
 719
 720         closedir(dirp);
 721         return(err);
 722 }
 723
 724 /*
 725  * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
 726  * add the new item, and update gl_pathc.
 727  *
 728  * This assumes the BSD realloc, which only copies the block when its size
 729  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 730  * behavior.
 731  *
 732  * Return 0 if new item added, error code if memory couldn't be allocated.
 733  *
 734  * Invariant of the glob_t structure:
 735  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 736  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 737  */
 738 static int
 739 globextend(path, pglob)
 740         const Char *path;
 741         glob_t *pglob;
 742 {
 743         char **pathv;
 744         int i;
 745         unsigned int newsize, len;
 746         char *copy;
 747         const Char *p;
 748
 749         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 750         pathv = pglob->gl_pathv ?
 751             (char **)realloc((char *)pglob->gl_pathv, newsize) :
 752             (char **)malloc(newsize);
 753         if (pathv == NULL) {
 754                 if (pglob->gl_pathv) {
 755                         free(pglob->gl_pathv);
 756                         pglob->gl_pathv = NULL;
 757                 }
 758                 return(GLOB_NOSPACE);
 759         }
 760
 761         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 762                 /* first time around -- clear initial gl_offs items */
 763                 pathv += pglob->gl_offs;
 764                 for (i = pglob->gl_offs; --i >= 0; )
 765                         *--pathv = NULL;
 766         }
 767         pglob->gl_pathv = pathv;
 768
 769         for (p = path; *p++;)
 770                 continue;
 771         len = (size_t)(p - path);
 772         if ((copy = malloc(len)) != NULL) {
 773                 if (g_Ctoc(path, copy, len)) {
 774                         free(copy);
 775                         return(GLOB_NOSPACE);
 776                 }
 777                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 778         }
 779         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 780
 781         return(copy == NULL ? GLOB_NOSPACE : 0);
 782 }
 783
 784 /*
 785  * pattern matching function for filenames.  Each occurrence of the *
 786  * pattern causes a recursion level.
 787  */
 788 static int
 789 match(name, pat, patend)
 790         Char *name, *pat, *patend;
 791 {
 792         int ok, negate_range;
 793         Char c, k;
 794
 795         while (pat < patend) {
 796                 c = *pat++;
 797                 switch (c & M_MASK) {
 798                 case M_ALL:
 799                         if (pat == patend)
 800                                 return(1);
 801                         do {
 802                             if (match(name, pat, patend))
 803                                     return(1);
 804                         } while (*name++ != EOS);
 805                         return(0);
 806                 case M_ONE:
 807                         if (*name++ == EOS)
 808                                 return(0);
 809                         break;
 810                 case M_SET:
 811                         ok = 0;
 812                         if ((k = *name++) == EOS)
 813                                 return(0);
 814                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
 815                                 ++pat;
 816                         while (((c = *pat++) & M_MASK) != M_END) {
 817                                 if ((c & M_MASK) == M_CLASS) {
 818                                         int idx = *pat & M_MASK;
 819                                         if (idx < NCCLASSES &&
 820                                             cclasses[idx].isctype(k))
 821                                                 ok = 1;
 822                                         ++pat;
 823                                 }
 824                                 if ((*pat & M_MASK) == M_RNG) {
 825                                         if (c <= k && k <= pat[1])
 826                                                 ok = 1;
 827                                         pat += 2;
 828                                 } else if (c == k)
 829                                         ok = 1;
 830                         }
 831                         if (ok == negate_range)
 832                                 return(0);
 833                         break;
 834                 default:
 835                         if (*name++ != c)
 836                                 return(0);
 837                         break;
 838                 }
 839         }
 840         return(*name == EOS);
 841 }
 842
 843 /* Free allocated data belonging to a glob_t structure. */
 844 void
 845 globfree(pglob)
 846         glob_t *pglob;
 847 {
 848         int i;
 849         char **pp;
 850
 851         if (pglob->gl_pathv != NULL) {
 852                 pp = pglob->gl_pathv + pglob->gl_offs;
 853                 for (i = pglob->gl_pathc; i--; ++pp)
 854                         if (*pp)
 855                                 free(*pp);
 856                 free(pglob->gl_pathv);
 857                 pglob->gl_pathv = NULL;
 858         }
 859 }
 860
 861 static DIR *
 862 g_opendir(str, pglob)
 863         Char *str;
 864         glob_t *pglob;
 865 {
 866         char buf[PATH_MAX];
 867
 868         if (!*str) {
 869                 buf[0] = '.';
 870                 buf[1] = '\0';
 871         } else {
 872                 if (g_Ctoc(str, buf, sizeof(buf)))
 873                         return(NULL);
 874         }
 875         return(opendir(buf));
 876 }
 877
 878 static int
 879 g_lstat(fn, sb, pglob)
 880         Char *fn;
 881         struct stat *sb;
 882         glob_t *pglob;
 883 {
 884         char buf[PATH_MAX];
 885
 886         if (g_Ctoc(fn, buf, sizeof(buf)))
 887                 return(-1);
 888         return(lstat(buf, sb));
 889 }
 890
 891 static int
 892 g_stat(fn, sb, pglob)
 893         Char *fn;
 894         struct stat *sb;
 895         glob_t *pglob;
 896 {
 897         char buf[PATH_MAX];
 898
 899         if (g_Ctoc(fn, buf, sizeof(buf)))
 900                 return(-1);
 901         return(stat(buf, sb));
 902 }
 903
 904 static Char *
 905 g_strchr(str, ch)
 906         const Char *str;
 907         int ch;
 908 {
 909         do {
 910                 if (*str == ch)
 911                         return ((Char *)str);
 912         } while (*str++);
 913         return (NULL);
 914 }
 915
 916 static int
 917 g_Ctoc(str, buf, len)
 918         const Char *str;
 919         char *buf;
 920         unsigned int len;
 921 {
 922
 923         while (len--) {
 924                 if ((*buf++ = *str++) == EOS)
 925                         return (0);
 926         }
 927         return (1);
 928 }
 929
 930 #ifdef DEBUG
 931 static void
 932 qprintf(str, s)
 933         const char *str;
 934         Char *s;
 935 {
 936         Char *p;
 937
 938         (void)printf("%s:\n", str);
 939         for (p = s; *p; p++)
 940                 (void)printf("%c", CHAR(*p));
 941         (void)printf("\n");
 942         for (p = s; *p; p++)
 943                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
 944         (void)printf("\n");
 945         for (p = s; *p; p++)
 946                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
 947         (void)printf("\n");
 948 }
 949 #endif