crypto/openssh/openbsd-compat/glob.c

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