openbsd-compat/glob.c

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