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 "missing.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 extern void pw_delref __P((struct passwd *));
 179
 180 int
 181 glob(pattern, flags, errfunc, pglob)
 182         const char *pattern;
 183         int flags, (*errfunc) __P((const char *, int));
 184         glob_t *pglob;
 185 {
 186         const unsigned char *patnext;
 187         int c;
 188         Char *bufnext, *bufend, patbuf[PATH_MAX];
 189
 190         patnext = (unsigned char *) pattern;
 191         if (!(flags & GLOB_APPEND)) {
 192                 pglob->gl_pathc = 0;
 193                 pglob->gl_pathv = NULL;
 194                 if (!(flags & GLOB_DOOFFS))
 195                         pglob->gl_offs = 0;
 196         }
 197         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 198         pglob->gl_errfunc = errfunc;
 199         pglob->gl_matchc = 0;
 200
 201         bufnext = patbuf;
 202         bufend = bufnext + PATH_MAX - 1;
 203         if (flags & GLOB_NOESCAPE)
 204                 while (bufnext < bufend && (c = *patnext++) != EOS)
 205                         *bufnext++ = c;
 206         else {
 207                 /* Protect the quoted characters. */
 208                 while (bufnext < bufend && (c = *patnext++) != EOS)
 209                         if (c == QUOTE) {
 210                                 if ((c = *patnext++) == EOS) {
 211                                         c = QUOTE;
 212                                         --patnext;
 213                                 }
 214                                 *bufnext++ = c | M_PROTECT;
 215                         } else
 216                                 *bufnext++ = c;
 217         }
 218         *bufnext = EOS;
 219
 220         if (flags & GLOB_BRACE)
 221                 return globexp1(patbuf, pglob);
 222         else
 223                 return glob0(patbuf, pglob);
 224 }
 225
 226 /*
 227  * Expand recursively a glob {} pattern. When there is no more expansion
 228  * invoke the standard globbing routine to glob the rest of the magic
 229  * characters
 230  */
 231 static int
 232 globexp1(pattern, pglob)
 233         const Char *pattern;
 234         glob_t *pglob;
 235 {
 236         const Char* ptr = pattern;
 237         int rv;
 238
 239         /* Protect a single {}, for find(1), like csh */
 240         if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
 241                 return glob0(pattern, pglob);
 242
 243         while ((ptr = (const Char *) g_strchr(ptr, LBRACE)) != NULL)
 244                 if (!globexp2(ptr, pattern, pglob, &rv))
 245                         return rv;
 246
 247         return glob0(pattern, pglob);
 248 }
 249
 250
 251 /*
 252  * Recursive brace globbing helper. Tries to expand a single brace.
 253  * If it succeeds then it invokes globexp1 with the new pattern.
 254  * If it fails then it tries to glob the rest of the pattern and returns.
 255  */
 256 static int
 257 globexp2(ptr, pattern, pglob, rv)
 258         const Char *ptr, *pattern;
 259         glob_t *pglob;
 260         int *rv;
 261 {
 262         int     i;
 263         Char   *lm, *ls;
 264         const Char *pe, *pm, *pl;
 265         Char    patbuf[PATH_MAX];
 266
 267         /* copy part up to the brace */
 268         for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
 269                 continue;
 270         *lm = EOS;
 271         ls = lm;
 272
 273         /* Find the balanced brace */
 274         for (i = 0, pe = ++ptr; *pe; pe++)
 275                 if (*pe == LBRACKET) {
 276                         /* Ignore everything between [] */
 277                         for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
 278                                 continue;
 279                         if (*pe == EOS) {
 280                                 /*
 281                                  * We could not find a matching RBRACKET.
 282                                  * Ignore and just look for RBRACE
 283                                  */
 284                                 pe = pm;
 285                         }
 286                 } else if (*pe == LBRACE)
 287                         i++;
 288                 else if (*pe == RBRACE) {
 289                         if (i == 0)
 290                                 break;
 291                         i--;
 292                 }
 293
 294         /* Non matching braces; just glob the pattern */
 295         if (i != 0 || *pe == EOS) {
 296                 *rv = glob0(patbuf, pglob);
 297                 return 0;
 298         }
 299
 300         for (i = 0, pl = pm = ptr; pm <= pe; pm++) {
 301                 switch (*pm) {
 302                 case LBRACKET:
 303                         /* Ignore everything between [] */
 304                         for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
 305                                 continue;
 306                         if (*pm == EOS) {
 307                                 /*
 308                                  * We could not find a matching RBRACKET.
 309                                  * Ignore and just look for RBRACE
 310                                  */
 311                                 pm = pl;
 312                         }
 313                         break;
 314
 315                 case LBRACE:
 316                         i++;
 317                         break;
 318
 319                 case RBRACE:
 320                         if (i) {
 321                                 i--;
 322                                 break;
 323                         }
 324                         /* FALLTHROUGH */
 325                 case COMMA:
 326                         if (i && *pm == COMMA)
 327                                 break;
 328                         else {
 329                                 /* Append the current string */
 330                                 for (lm = ls; (pl < pm); *lm++ = *pl++)
 331                                         continue;
 332
 333                                 /*
 334                                  * Append the rest of the pattern after the
 335                                  * closing brace
 336                                  */
 337                                 for (pl = pe + 1; (*lm++ = *pl++) != EOS; )
 338                                         continue;
 339
 340                                 /* Expand the current pattern */
 341 #ifdef DEBUG
 342                                 qprintf("globexp2:", patbuf);
 343 #endif
 344                                 *rv = globexp1(patbuf, pglob);
 345
 346                                 /* move after the comma, to the next string */
 347                                 pl = pm + 1;
 348                         }
 349                         break;
 350
 351                 default:
 352                         break;
 353                 }
 354         }
 355         *rv = 0;
 356         return 0;
 357 }
 358
 359
 360
 361 /*
 362  * expand tilde from the passwd file.
 363  */
 364 static const Char *
 365 globtilde(pattern, patbuf, patbuf_len, pglob)
 366         const Char *pattern;
 367         Char *patbuf;
 368         size_t patbuf_len;
 369         glob_t *pglob;
 370 {
 371         struct passwd *pwd = NULL;
 372         char *h;
 373         const Char *p;
 374         Char *b, *eb;
 375
 376         if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
 377                 return pattern;
 378
 379         /* Copy up to the end of the string or / */
 380         eb = &patbuf[patbuf_len - 1];
 381         for (p = pattern + 1, h = (char *) patbuf;
 382             h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
 383                 continue;
 384
 385         *h = EOS;
 386
 387         if (((char *) patbuf)[0] == EOS) {
 388                 /*
 389                  * handle a plain ~ or ~/ by expanding $HOME
 390                  * first and then trying the password file
 391                  */
 392                 if ((h = getenv("HOME")) == NULL) {
 393                         if ((pwd = sudo_getpwuid(getuid())) == NULL)
 394                                 return pattern;
 395                         else
 396                                 h = pwd->pw_dir;
 397                 }
 398         } else {
 399                 /*
 400                  * Expand a ~user
 401                  */
 402                 if ((pwd = sudo_getpwnam((char*) patbuf)) == NULL)
 403                         return pattern;
 404                 else
 405                         h = pwd->pw_dir;
 406         }
 407
 408         /* Copy the home directory */
 409         for (b = patbuf; b < eb && *h; *b++ = *h++)
 410                 continue;
 411
 412         /* Append the rest of the pattern */
 413         while (b < eb && (*b++ = *p++) != EOS)
 414                 continue;
 415         *b = EOS;
 416
 417         if (pwd)
 418             pw_delref(pwd);
 419
 420         return patbuf;
 421 }
 422
 423 static int
 424 g_strncmp(s1, s2, n)
 425         const Char *s1;
 426         const char *s2;
 427         size_t n;
 428 {
 429         int rv = 0;
 430
 431         while (n--) {
 432                 rv = *(Char *)s1 - *(const unsigned char *)s2++;
 433                 if (rv)
 434                         break;
 435                 if (*s1++ == '\0')
 436                         break;
 437         }
 438         return rv;
 439 }
 440
 441 static int
 442 g_charclass(patternp, bufnextp)
 443         const Char **patternp;
 444         Char **bufnextp;
 445 {
 446         const Char *pattern = *patternp + 1;
 447         Char *bufnext = *bufnextp;
 448         const Char *colon;
 449         struct cclass *cc;
 450         size_t len;
 451
 452         if ((colon = g_strchr(pattern, ':')) == NULL || colon[1] != ']')
 453                 return 1;       /* not a character class */
 454
 455         len = (size_t)(colon - pattern);
 456         for (cc = cclasses; cc->name != NULL; cc++) {
 457                 if (!g_strncmp(pattern, cc->name, len) && cc->name[len] == '\0')
 458                         break;
 459         }
 460         if (cc->name == NULL)
 461                 return -1;      /* invalid character class */
 462         *bufnext++ = M_CLASS;
 463         *bufnext++ = (Char)(cc - &cclasses[0]);
 464         *bufnextp = bufnext;
 465         *patternp += len + 3;
 466
 467         return 0;
 468 }
 469
 470 /*
 471  * The main glob() routine: compiles the pattern (optionally processing
 472  * quotes), calls glob1() to do the real pattern matching, and finally
 473  * sorts the list (unless unsorted operation is requested).  Returns 0
 474  * if things went well, nonzero if errors occurred.  It is not an error
 475  * to find no matches.
 476  */
 477 static int
 478 glob0(pattern, pglob)
 479         const Char *pattern;
 480         glob_t *pglob;
 481 {
 482         const Char *qpatnext;
 483         int c, err, oldpathc;
 484         Char *bufnext, patbuf[PATH_MAX];
 485
 486         qpatnext = globtilde(pattern, patbuf, PATH_MAX, pglob);
 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                                 if (c == LBRACKET && *qpatnext == ':') {
 510                                         do {
 511                                                 err = g_charclass(&qpatnext,
 512                                                     &bufnext);
 513                                                 if (err)
 514                                                         break;
 515                                                 c = *qpatnext++;
 516                                         } while (c == LBRACKET && *qpatnext == ':');
 517                                         if (err == -1 &&
 518                                             !(pglob->gl_flags & GLOB_NOCHECK))
 519                                                 return GLOB_NOMATCH;
 520                                         if (c == RBRACKET)
 521                                                 break;
 522                                 }
 523                                 *bufnext++ = CHAR(c);
 524                                 if (*qpatnext == RANGE &&
 525                                     (c = qpatnext[1]) != RBRACKET) {
 526                                         *bufnext++ = M_RNG;
 527                                         *bufnext++ = CHAR(c);
 528                                         qpatnext += 2;
 529                                 }
 530                         } while ((c = *qpatnext++) != RBRACKET);
 531                         pglob->gl_flags |= GLOB_MAGCHAR;
 532                         *bufnext++ = M_END;
 533                         break;
 534                 case QUESTION:
 535                         pglob->gl_flags |= GLOB_MAGCHAR;
 536                         *bufnext++ = M_ONE;
 537                         break;
 538                 case STAR:
 539                         pglob->gl_flags |= GLOB_MAGCHAR;
 540                         /* collapse adjacent stars to one,
 541                          * to avoid exponential behavior
 542                          */
 543                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
 544                                 *bufnext++ = M_ALL;
 545                         break;
 546                 default:
 547                         *bufnext++ = CHAR(c);
 548                         break;
 549                 }
 550         }
 551         *bufnext = EOS;
 552 #ifdef DEBUG
 553         qprintf("glob0:", patbuf);
 554 #endif
 555
 556         if ((err = glob1(patbuf, patbuf + PATH_MAX - 1, pglob)) != 0)
 557                 return err;
 558
 559         /*
 560          * If there was no match we are going to append the pattern
 561          * if GLOB_NOCHECK was specified.
 562          */
 563         if (pglob->gl_pathc == oldpathc) {
 564                 if (pglob->gl_flags & GLOB_NOCHECK)
 565                         return globextend(pattern, pglob);
 566                 else
 567                         return GLOB_NOMATCH;
 568         }
 569         if (!(pglob->gl_flags & GLOB_NOSORT))
 570                 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 571                     pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 572         return 0;
 573 }
 574
 575 static int
 576 compare(p, q)
 577         const void *p, *q;
 578 {
 579         return strcmp(*(char **)p, *(char **)q);
 580 }
 581
 582 static int
 583 glob1(pattern, pattern_last,  pglob)
 584         Char *pattern, *pattern_last;
 585         glob_t *pglob;
 586 {
 587         Char pathbuf[PATH_MAX];
 588
 589         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
 590         if (*pattern == EOS)
 591                 return 0;
 592         return glob2(pathbuf, pathbuf + PATH_MAX - 1,
 593             pathbuf, pathbuf + PATH_MAX - 1,
 594             pattern, pattern_last, pglob);
 595 }
 596
 597 /*
 598  * The functions glob2 and glob3 are mutually recursive; there is one level
 599  * of recursion for each segment in the pattern that contains one or more
 600  * meta characters.
 601  */
 602 static int
 603 glob2(pathbuf, pathbuf_last, pathend, pathend_last, pattern, pattern_last, pglob)
 604         Char *pathbuf, *pathbuf_last;
 605         Char *pathend, *pathend_last;
 606         Char *pattern, *pattern_last;
 607         glob_t *pglob;
 608 {
 609         struct stat sb;
 610         Char *p, *q;
 611         int anymeta;
 612
 613         /*
 614          * Loop over pattern segments until end of pattern or until
 615          * segment with meta character found.
 616          */
 617         for (anymeta = 0;;) {
 618                 if (*pattern == EOS) {          /* End of pattern? */
 619                         *pathend = EOS;
 620                         if (g_lstat(pathbuf, &sb, pglob))
 621                                 return 0;
 622
 623                         if (((pglob->gl_flags & GLOB_MARK) &&
 624                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
 625                             (S_ISLNK(sb.st_mode) &&
 626                             (g_stat(pathbuf, &sb, pglob) == 0) &&
 627                             S_ISDIR(sb.st_mode)))) {
 628                                 if (pathend+1 > pathend_last)
 629                                         return 1;
 630                                 *pathend++ = SEP;
 631                                 *pathend = EOS;
 632                         }
 633                         ++pglob->gl_matchc;
 634                         return globextend(pathbuf, pglob);
 635                 }
 636
 637                 /* Find end of next segment, copy tentatively to pathend. */
 638                 q = pathend;
 639                 p = pattern;
 640                 while (*p != EOS && *p != SEP) {
 641                         if (ismeta(*p))
 642                                 anymeta = 1;
 643                         if (q+1 > pathend_last)
 644                                 return 1;
 645                         *q++ = *p++;
 646                 }
 647
 648                 if (!anymeta) {         /* No expansion, do next segment. */
 649                         pathend = q;
 650                         pattern = p;
 651                         while (*pattern == SEP) {
 652                                 if (pathend+1 > pathend_last)
 653                                         return 1;
 654                                 *pathend++ = *pattern++;
 655                         }
 656                 } else
 657                         /* Need expansion, recurse. */
 658                         return glob3(pathbuf, pathbuf_last, pathend,
 659                             pathend_last, pattern, pattern_last,
 660                             p, pattern_last, pglob);
 661         }
 662         /* NOTREACHED */
 663 }
 664
 665 static int
 666 glob3(pathbuf, pathbuf_last, pathend, pathend_last, pattern, pattern_last,
 667     restpattern, restpattern_last, pglob)
 668         Char *pathbuf, *pathbuf_last, *pathend, *pathend_last;
 669         Char *pattern, *pattern_last, *restpattern, *restpattern_last;
 670         glob_t *pglob;
 671 {
 672         struct dirent *dp;
 673         DIR *dirp;
 674         int err;
 675         char buf[PATH_MAX];
 676
 677         if (pathend > pathend_last)
 678                 return 1;
 679         *pathend = EOS;
 680         errno = 0;
 681
 682         if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
 683                 /* TODO: don't call for ENOENT or ENOTDIR? */
 684                 if (pglob->gl_errfunc) {
 685                         if (g_Ctoc(pathbuf, buf, sizeof(buf)))
 686                                 return GLOB_ABORTED;
 687                         if (pglob->gl_errfunc(buf, errno) ||
 688                             pglob->gl_flags & GLOB_ERR)
 689                                 return GLOB_ABORTED;
 690                 }
 691                 return 0;
 692         }
 693
 694         err = 0;
 695
 696         /* Search directory for matching names. */
 697         while ((dp = readdir(dirp))) {
 698                 unsigned char *sc;
 699                 Char *dc;
 700
 701                 /* Initial DOT must be matched literally. */
 702                 if (dp->d_name[0] == DOT && *pattern != DOT)
 703                         continue;
 704                 dc = pathend;
 705                 sc = (unsigned char *) dp->d_name;
 706                 while (dc < pathend_last && (*dc++ = *sc++) != EOS)
 707                         continue;
 708                 if (dc >= pathend_last) {
 709                         *dc = EOS;
 710                         err = 1;
 711                         break;
 712                 }
 713
 714                 if (!match(pathend, pattern, restpattern)) {
 715                         *pathend = EOS;
 716                         continue;
 717                 }
 718                 err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
 719                     restpattern, restpattern_last, pglob);
 720                 if (err)
 721                         break;
 722         }
 723
 724         closedir(dirp);
 725         return err;
 726 }
 727
 728 /*
 729  * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
 730  * add the new item, and update gl_pathc.
 731  *
 732  * This assumes the BSD realloc, which only copies the block when its size
 733  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 734  * behavior.
 735  *
 736  * Return 0 if new item added, error code if memory couldn't be allocated.
 737  *
 738  * Invariant of the glob_t structure:
 739  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 740  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 741  */
 742 static int
 743 globextend(path, pglob)
 744         const Char *path;
 745         glob_t *pglob;
 746 {
 747         char **pathv;
 748         int i;
 749         unsigned int newsize, len;
 750         char *copy;
 751         const Char *p;
 752
 753         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 754         pathv = pglob->gl_pathv ?
 755             (char **)realloc((char *)pglob->gl_pathv, newsize) :
 756             (char **)malloc(newsize);
 757         if (pathv == NULL) {
 758                 if (pglob->gl_pathv) {
 759                         free(pglob->gl_pathv);
 760                         pglob->gl_pathv = NULL;
 761                 }
 762                 return GLOB_NOSPACE;
 763         }
 764
 765         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 766                 /* first time around -- clear initial gl_offs items */
 767                 pathv += pglob->gl_offs;
 768                 for (i = pglob->gl_offs; --i >= 0; )
 769                         *--pathv = NULL;
 770         }
 771         pglob->gl_pathv = pathv;
 772
 773         for (p = path; *p++;)
 774                 continue;
 775         len = (size_t)(p - path);
 776         if ((copy = malloc(len)) != NULL) {
 777                 if (g_Ctoc(path, copy, len)) {
 778                         free(copy);
 779                         return GLOB_NOSPACE;
 780                 }
 781                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 782         }
 783         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 784
 785         return copy == NULL ? GLOB_NOSPACE : 0;
 786 }
 787
 788 /*
 789  * pattern matching function for filenames.  Each occurrence of the *
 790  * pattern causes a recursion level.
 791  */
 792 static int
 793 match(name, pat, patend)
 794         Char *name, *pat, *patend;
 795 {
 796         int ok, negate_range;
 797         Char c, k;
 798
 799         while (pat < patend) {
 800                 c = *pat++;
 801                 switch (c & M_MASK) {
 802                 case M_ALL:
 803                         if (pat == patend)
 804                                 return 1;
 805                         do {
 806                             if (match(name, pat, patend))
 807                                     return 1;
 808                         } while (*name++ != EOS);
 809                         return 0;
 810                 case M_ONE:
 811                         if (*name++ == EOS)
 812                                 return 0;
 813                         break;
 814                 case M_SET:
 815                         ok = 0;
 816                         if ((k = *name++) == EOS)
 817                                 return 0;
 818                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
 819                                 ++pat;
 820                         while (((c = *pat++) & M_MASK) != M_END) {
 821                                 if ((c & M_MASK) == M_CLASS) {
 822                                         int idx = *pat & M_MASK;
 823                                         if (idx < NCCLASSES &&
 824                                             cclasses[idx].isctype(k))
 825                                                 ok = 1;
 826                                         ++pat;
 827                                 }
 828                                 if ((*pat & M_MASK) == M_RNG) {
 829                                         if (c <= k && k <= pat[1])
 830                                                 ok = 1;
 831                                         pat += 2;
 832                                 } else if (c == k)
 833                                         ok = 1;
 834                         }
 835                         if (ok == negate_range)
 836                                 return 0;
 837                         break;
 838                 default:
 839                         if (*name++ != c)
 840                                 return 0;
 841                         break;
 842                 }
 843         }
 844         return *name == EOS;
 845 }
 846
 847 /* Free allocated data belonging to a glob_t structure. */
 848 void
 849 globfree(pglob)
 850         glob_t *pglob;
 851 {
 852         int i;
 853         char **pp;
 854
 855         if (pglob->gl_pathv != NULL) {
 856                 pp = pglob->gl_pathv + pglob->gl_offs;
 857                 for (i = pglob->gl_pathc; i--; ++pp)
 858                         if (*pp)
 859                                 free(*pp);
 860                 free(pglob->gl_pathv);
 861                 pglob->gl_pathv = NULL;
 862         }
 863 }
 864
 865 static DIR *
 866 g_opendir(str, pglob)
 867         Char *str;
 868         glob_t *pglob;
 869 {
 870         char buf[PATH_MAX];
 871
 872         if (!*str) {
 873                 buf[0] = '.';
 874                 buf[1] = '\0';
 875         } else {
 876                 if (g_Ctoc(str, buf, sizeof(buf)))
 877                         return NULL;
 878         }
 879         return opendir(buf);
 880 }
 881
 882 static int
 883 g_lstat(fn, sb, pglob)
 884         Char *fn;
 885         struct stat *sb;
 886         glob_t *pglob;
 887 {
 888         char buf[PATH_MAX];
 889
 890         if (g_Ctoc(fn, buf, sizeof(buf)))
 891                 return -1;
 892         return lstat(buf, sb);
 893 }
 894
 895 static int
 896 g_stat(fn, sb, pglob)
 897         Char *fn;
 898         struct stat *sb;
 899         glob_t *pglob;
 900 {
 901         char buf[PATH_MAX];
 902
 903         if (g_Ctoc(fn, buf, sizeof(buf)))
 904                 return -1;
 905         return stat(buf, sb);
 906 }
 907
 908 static Char *
 909 g_strchr(str, ch)
 910         const Char *str;
 911         int ch;
 912 {
 913         do {
 914                 if (*str == ch)
 915                         return (Char *)str;
 916         } while (*str++);
 917         return NULL;
 918 }
 919
 920 static int
 921 g_Ctoc(str, buf, len)
 922         const Char *str;
 923         char *buf;
 924         unsigned int len;
 925 {
 926
 927         while (len--) {
 928                 if ((*buf++ = *str++) == EOS)
 929                         return 0;
 930         }
 931         return 1;
 932 }
 933
 934 #ifdef DEBUG
 935 static void
 936 qprintf(str, s)
 937         const char *str;
 938         Char *s;
 939 {
 940         Char *p;
 941
 942         (void)printf("%s:\n", str);
 943         for (p = s; *p; p++)
 944                 (void)printf("%c", CHAR(*p));
 945         (void)printf("\n");
 946         for (p = s; *p; p++)
 947                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
 948         (void)printf("\n");
 949         for (p = s; *p; p++)
 950                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
 951         (void)printf("\n");
 952 }
 953 #endif