lib/glob/glob.c

   1 /* glob.c -- file-name wildcard pattern matching for Bash.
   2
   3    Copyright (C) 1985-2009 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne-Again SHell.
   6
   7    Bash is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 /* To whomever it may concern: I have never seen the code which most
  22    Unix programs use to perform this function.  I wrote this from scratch
  23    based on specifications for the pattern matching.  --RMS.  */
  24
  25 #include <config.h>
  26
  27 #if !defined (__GNUC__) && !defined (HAVE_ALLOCA_H) && defined (_AIX)
  28   #pragma alloca
  29 #endif /* _AIX && RISC6000 && !__GNUC__ */
  30
  31 #include "bashtypes.h"
  32
  33 #if defined (HAVE_UNISTD_H)
  34 #  include <unistd.h>
  35 #endif
  36
  37 #include "bashansi.h"
  38 #include "posixdir.h"
  39 #include "posixstat.h"
  40 #include "shmbutil.h"
  41 #include "xmalloc.h"
  42
  43 #include "filecntl.h"
  44 #if !defined (F_OK)
  45 #  define F_OK 0
  46 #endif
  47
  48 #include "stdc.h"
  49 #include "memalloc.h"
  50
  51 #include <signal.h>
  52
  53 #include "shell.h"
  54
  55 #include "glob.h"
  56 #include "strmatch.h"
  57
  58 #if !defined (HAVE_BCOPY) && !defined (bcopy)
  59 #  define bcopy(s, d, n) ((void) memcpy ((d), (s), (n)))
  60 #endif /* !HAVE_BCOPY && !bcopy */
  61
  62 #if !defined (NULL)
  63 #  if defined (__STDC__)
  64 #    define NULL ((void *) 0)
  65 #  else
  66 #    define NULL 0x0
  67 #  endif /* __STDC__ */
  68 #endif /* !NULL */
  69
  70 #if !defined (FREE)
  71 #  define FREE(x)       if (x) free (x)
  72 #endif
  73
  74 /* Don't try to alloca() more than this much memory for `struct globval'
  75    in glob_vector() */
  76 #ifndef ALLOCA_MAX
  77 #  define ALLOCA_MAX    100000
  78 #endif
  79
  80 struct globval
  81   {
  82     struct globval *next;
  83     char *name;
  84   };
  85
  86 extern void throw_to_top_level __P((void));
  87 extern int sh_eaccess __P((char *, int));
  88 extern char *sh_makepath __P((const char *, const char *, int));
  89 extern int signal_is_pending __P((int));
  90 extern void run_pending_traps __P((void));
  91
  92 extern int extended_glob;
  93
  94 /* Global variable which controls whether or not * matches .*.
  95    Non-zero means don't match .*.  */
  96 int noglob_dot_filenames = 1;
  97
  98 /* Global variable which controls whether or not filename globbing
  99    is done without regard to case. */
 100 int glob_ignore_case = 0;
 101
 102 /* Global variable to return to signify an error in globbing. */
 103 char *glob_error_return;
 104
 105 static struct globval finddirs_error_return;
 106
 107 /* Some forward declarations. */
 108 static int skipname __P((char *, char *, int));
 109 #if HANDLE_MULTIBYTE
 110 static int mbskipname __P((char *, char *, int));
 111 #endif
 112 #if HANDLE_MULTIBYTE
 113 static void udequote_pathname __P((char *));
 114 static void wdequote_pathname __P((char *));
 115 #else
 116 #  define dequote_pathname udequote_pathname
 117 #endif
 118 static void dequote_pathname __P((char *));
 119 static int glob_testdir __P((char *, int));
 120 static char **glob_dir_to_array __P((char *, char **, int));
 121
 122 /* Make sure these names continue to agree with what's in smatch.c */
 123 extern char *glob_patscan __P((char *, char *, int));
 124 extern wchar_t *glob_patscan_wc __P((wchar_t *, wchar_t *, int));
 125
 126 extern char *glob_dirscan __P((char *, int));
 127
 128 /* Compile `glob_loop.c' for single-byte characters. */
 129 #define CHAR    unsigned char
 130 #define INT     int
 131 #define L(CS)   CS
 132 #define INTERNAL_GLOB_PATTERN_P internal_glob_pattern_p
 133 #include "glob_loop.c"
 134
 135 /* Compile `glob_loop.c' again for multibyte characters. */
 136 #if HANDLE_MULTIBYTE
 137
 138 #define CHAR    wchar_t
 139 #define INT     wint_t
 140 #define L(CS)   L##CS
 141 #define INTERNAL_GLOB_PATTERN_P internal_glob_wpattern_p
 142 #include "glob_loop.c"
 143
 144 #endif /* HANDLE_MULTIBYTE */
 145
 146 /* And now a function that calls either the single-byte or multibyte version
 147    of internal_glob_pattern_p. */
 148 int
 149 glob_pattern_p (pattern)
 150      const char *pattern;
 151 {
 152 #if HANDLE_MULTIBYTE
 153   size_t n;
 154   wchar_t *wpattern;
 155   int r;
 156
 157   if (MB_CUR_MAX == 1)
 158     return (internal_glob_pattern_p ((unsigned char *)pattern));
 159
 160   /* Convert strings to wide chars, and call the multibyte version. */
 161   n = xdupmbstowcs (&wpattern, NULL, pattern);
 162   if (n == (size_t)-1)
 163     /* Oops.  Invalid multibyte sequence.  Try it as single-byte sequence. */
 164     return (internal_glob_pattern_p ((unsigned char *)pattern));
 165
 166   r = internal_glob_wpattern_p (wpattern);
 167   free (wpattern);
 168
 169   return r;
 170 #else
 171   return (internal_glob_pattern_p (pattern));
 172 #endif
 173 }
 174
 175 #if EXTENDED_GLOB
 176 /* Return 1 if all subpatterns in the extended globbing pattern PAT indicate
 177    that the name should be skipped.  XXX - doesn't handle pattern negation,
 178    not sure if it should */
 179 static int
 180 extglob_skipname (pat, dname, flags)
 181      char *pat, *dname;
 182      int flags;
 183 {
 184   char *pp, *pe, *t, *se;
 185   int n, r, negate;
 186
 187   negate = *pat == '!';
 188   pp = pat + 2;
 189   se = pp + strlen (pp) - 1;            /* end of string */
 190   pe = glob_patscan (pp, se, 0);        /* end of extglob pattern (( */
 191   /* we should check for invalid extglob pattern here */
 192   if (pe == 0)
 193     return 0;
 194
 195   /* if pe != se we have more of the pattern at the end of the extglob
 196      pattern. Check the easy case first ( */
 197   if (pe == se && *pe == ')' && (t = strchr (pp, '|')) == 0)
 198     {
 199       *pe = '\0';
 200 #if defined (HANDLE_MULTIBYTE)
 201       r = mbskipname (pp, dname, flags);
 202 #else
 203       r = skipname (pp, dname, flags);  /*(*/
 204 #endif
 205       *pe = ')';
 206       return r;
 207     }
 208
 209   /* check every subpattern */
 210   while (t = glob_patscan (pp, pe, '|'))
 211     {
 212       n = t[-1];
 213       t[-1] = '\0';
 214 #if defined (HANDLE_MULTIBYTE)
 215       r = mbskipname (pp, dname, flags);
 216 #else
 217       r = skipname (pp, dname, flags);
 218 #endif
 219       t[-1] = n;
 220       if (r == 0)       /* if any pattern says not skip, we don't skip */
 221         return r;
 222       pp = t;
 223     }   /*(*/
 224
 225   /* glob_patscan might find end of pattern */
 226   if (pp == se)
 227     return r;
 228
 229   /* but if it doesn't then we didn't match a leading dot */
 230   return 0;
 231 }
 232 #endif
 233
 234 /* Return 1 if DNAME should be skipped according to PAT.  Mostly concerned
 235    with matching leading `.'. */
 236 static int
 237 skipname (pat, dname, flags)
 238      char *pat;
 239      char *dname;
 240      int flags;
 241 {
 242 #if EXTENDED_GLOB
 243   if (extglob_pattern_p (pat))          /* XXX */
 244     return (extglob_skipname (pat, dname, flags));
 245 #endif
 246
 247   /* If a leading dot need not be explicitly matched, and the pattern
 248      doesn't start with a `.', don't match `.' or `..' */
 249   if (noglob_dot_filenames == 0 && pat[0] != '.' &&
 250         (pat[0] != '\\' || pat[1] != '.') &&
 251         (dname[0] == '.' &&
 252           (dname[1] == '\0' || (dname[1] == '.' && dname[2] == '\0'))))
 253     return 1;
 254
 255   /* If a dot must be explicitly matched, check to see if they do. */
 256   else if (noglob_dot_filenames && dname[0] == '.' && pat[0] != '.' &&
 257         (pat[0] != '\\' || pat[1] != '.'))
 258     return 1;
 259
 260   return 0;
 261 }
 262
 263 #if HANDLE_MULTIBYTE
 264
 265 static int
 266 wchkname (pat_wc, dn_wc)
 267      wchar_t *pat_wc, *dn_wc;
 268 {
 269   /* If a leading dot need not be explicitly matched, and the
 270      pattern doesn't start with a `.', don't match `.' or `..' */
 271   if (noglob_dot_filenames == 0 && pat_wc[0] != L'.' &&
 272         (pat_wc[0] != L'\\' || pat_wc[1] != L'.') &&
 273         (dn_wc[0] == L'.' &&
 274           (dn_wc[1] == L'\0' || (dn_wc[1] == L'.' && dn_wc[2] == L'\0'))))
 275     return 1;
 276
 277   /* If a leading dot must be explicitly matched, check to see if the
 278      pattern and dirname both have one. */
 279  else if (noglob_dot_filenames && dn_wc[0] == L'.' &&
 280         pat_wc[0] != L'.' &&
 281            (pat_wc[0] != L'\\' || pat_wc[1] != L'.'))
 282     return 1;
 283
 284   return 0;
 285 }
 286
 287 static int
 288 wextglob_skipname (pat, dname, flags)
 289      wchar_t *pat, *dname;
 290      int flags;
 291 {
 292 #if EXTENDED_GLOB
 293   wchar_t *pp, *pe, *t, n, *se;
 294   int r, negate;
 295
 296   negate = *pat == L'!';
 297   pp = pat + 2;
 298   se = pp + wcslen (pp) - 1;    /*(*/
 299   pe = glob_patscan_wc (pp, se, 0);
 300
 301   if (pe == se && *pe == ')' && (t = wcschr (pp, L'|')) == 0)
 302     {
 303       *pe = L'\0';
 304       r = wchkname (pp, dname); /*(*/
 305       *pe = L')';
 306       return r;
 307     }
 308
 309   /* check every subpattern */
 310   while (t = glob_patscan_wc (pp, pe, '|'))
 311     {
 312       n = t[-1];
 313       t[-1] = L'\0';
 314       r = wchkname (pp, dname);
 315       t[-1] = n;
 316       if (r == 0)
 317         return 0;
 318       pp = t;
 319     }
 320
 321   if (pp == pe)         /* glob_patscan_wc might find end of pattern */
 322     return r;
 323
 324   /* but if it doesn't then we didn't match a leading dot */
 325   return 0;
 326 #else
 327   return (wchkname (pat, dname));
 328 #endif
 329 }
 330
 331 /* Return 1 if DNAME should be skipped according to PAT.  Handles multibyte
 332    characters in PAT and DNAME.  Mostly concerned with matching leading `.'. */
 333 static int
 334 mbskipname (pat, dname, flags)
 335      char *pat, *dname;
 336      int flags;
 337 {
 338   int ret, ext;
 339   wchar_t *pat_wc, *dn_wc;
 340   size_t pat_n, dn_n;
 341
 342   if (mbsmbchar (dname) == 0 && mbsmbchar (pat) == 0)
 343     return (skipname (pat, dname, flags));
 344
 345   ext = 0;
 346 #if EXTENDED_GLOB
 347   ext = extglob_pattern_p (pat);
 348 #endif
 349
 350   pat_wc = dn_wc = (wchar_t *)NULL;
 351
 352   pat_n = xdupmbstowcs (&pat_wc, NULL, pat);
 353   if (pat_n != (size_t)-1)
 354     dn_n = xdupmbstowcs (&dn_wc, NULL, dname);
 355
 356   ret = 0;
 357   if (pat_n != (size_t)-1 && dn_n !=(size_t)-1)
 358     ret = ext ? wextglob_skipname (pat_wc, dn_wc, flags) : wchkname (pat_wc, dn_wc);
 359   else
 360     ret = skipname (pat, dname, flags);
 361
 362   FREE (pat_wc);
 363   FREE (dn_wc);
 364
 365   return ret;
 366 }
 367 #endif /* HANDLE_MULTIBYTE */
 368
 369 /* Remove backslashes quoting characters in PATHNAME by modifying PATHNAME. */
 370 static void
 371 udequote_pathname (pathname)
 372      char *pathname;
 373 {
 374   register int i, j;
 375
 376   for (i = j = 0; pathname && pathname[i]; )
 377     {
 378       if (pathname[i] == '\\')
 379         i++;
 380
 381       pathname[j++] = pathname[i++];
 382
 383       if (pathname[i - 1] == 0)
 384         break;
 385     }
 386   if (pathname)
 387     pathname[j] = '\0';
 388 }
 389
 390 #if HANDLE_MULTIBYTE
 391 /* Remove backslashes quoting characters in PATHNAME by modifying PATHNAME. */
 392 static void
 393 wdequote_pathname (pathname)
 394      char *pathname;
 395 {
 396   mbstate_t ps;
 397   size_t len, n;
 398   wchar_t *wpathname;
 399   int i, j;
 400   wchar_t *orig_wpathname;
 401
 402   len = strlen (pathname);
 403   /* Convert the strings into wide characters.  */
 404   n = xdupmbstowcs (&wpathname, NULL, pathname);
 405   if (n == (size_t) -1)
 406     {
 407       /* Something wrong.  Fall back to single-byte */
 408       udequote_pathname (pathname);
 409       return;
 410     }
 411   orig_wpathname = wpathname;
 412
 413   for (i = j = 0; wpathname && wpathname[i]; )
 414     {
 415       if (wpathname[i] == L'\\')
 416         i++;
 417
 418       wpathname[j++] = wpathname[i++];
 419
 420       if (wpathname[i - 1] == L'\0')
 421         break;
 422     }
 423   if (wpathname)
 424     wpathname[j] = L'\0';
 425
 426   /* Convert the wide character string into unibyte character set. */
 427   memset (&ps, '\0', sizeof(mbstate_t));
 428   n = wcsrtombs(pathname, (const wchar_t **)&wpathname, len, &ps);
 429   pathname[len] = '\0';
 430
 431   /* Can't just free wpathname here; wcsrtombs changes it in many cases. */
 432   free (orig_wpathname);
 433 }
 434
 435 static void
 436 dequote_pathname (pathname)
 437      char *pathname;
 438 {
 439   if (MB_CUR_MAX > 1)
 440     wdequote_pathname (pathname);
 441   else
 442     udequote_pathname (pathname);
 443 }
 444 #endif /* HANDLE_MULTIBYTE */
 445
 446 /* Test whether NAME exists. */
 447
 448 #if defined (HAVE_LSTAT)
 449 #  define GLOB_TESTNAME(name)  (lstat (name, &finfo))
 450 #else /* !HAVE_LSTAT */
 451 #  if !defined (AFS)
 452 #    define GLOB_TESTNAME(name)  (sh_eaccess (name, F_OK))
 453 #  else /* AFS */
 454 #    define GLOB_TESTNAME(name)  (access (name, F_OK))
 455 #  endif /* AFS */
 456 #endif /* !HAVE_LSTAT */
 457
 458 /* Return 0 if DIR is a directory, -1 otherwise. */
 459 static int
 460 glob_testdir (dir, flags)
 461      char *dir;
 462      int flags;
 463 {
 464   struct stat finfo;
 465   int r;
 466
 467 /*itrace("glob_testdir: testing %s" flags = %d, dir, flags);*/
 468 #if defined (HAVE_LSTAT)
 469   r = (flags & GX_ALLDIRS) ? lstat (dir, &finfo) : stat (dir, &finfo);
 470 #else
 471   r = stat (dir, &finfo);
 472 #endif
 473   if (r < 0)
 474     return (-1);
 475
 476   if (S_ISDIR (finfo.st_mode) == 0)
 477     return (-1);
 478
 479   return (0);
 480 }
 481
 482 /* Recursively scan SDIR for directories matching PAT (PAT is always `**').
 483    FLAGS is simply passed down to the recursive call to glob_vector.  Returns
 484    a list of matching directory names.  EP, if non-null, is set to the last
 485    element of the returned list.  NP, if non-null, is set to the number of
 486    directories in the returned list.  These two variables exist for the
 487    convenience of the caller (always glob_vector). */
 488 static struct globval *
 489 finddirs (pat, sdir, flags, ep, np)
 490      char *pat;
 491      char *sdir;
 492      int flags;
 493      struct globval **ep;
 494      int *np;
 495 {
 496   char **r, *n;
 497   int ndirs;
 498   struct globval *ret, *e, *g;
 499
 500 /*itrace("finddirs: pat = `%s' sdir = `%s' flags = 0x%x", pat, sdir, flags);*/
 501   e = ret = 0;
 502   r = glob_vector (pat, sdir, flags);
 503   if (r == 0 || r[0] == 0)
 504     {
 505       if (np)
 506         *np = 0;
 507       if (ep)
 508         *ep = 0;
 509       if (r && r != &glob_error_return)
 510         free (r);
 511       return (struct globval *)0;
 512     }
 513   for (ndirs = 0; r[ndirs] != 0; ndirs++)
 514     {
 515       g = (struct globval *) malloc (sizeof (struct globval));
 516       if (g == 0)
 517         {
 518           while (ret)           /* free list built so far */
 519             {
 520               g = ret->next;
 521               free (ret);
 522               ret = g;
 523             }
 524
 525           free (r);
 526           if (np)
 527             *np = 0;
 528           if (ep)
 529             *ep = 0;
 530           return (&finddirs_error_return);
 531         }
 532       if (e == 0)
 533         e = g;
 534
 535       g->next = ret;
 536       ret = g;
 537
 538       g->name = r[ndirs];
 539     }
 540
 541   free (r);
 542   if (ep)
 543     *ep = e;
 544   if (np)
 545     *np = ndirs;
 546
 547   return ret;
 548 }
 549
 550 /* Return a vector of names of files in directory DIR
 551    whose names match glob pattern PAT.
 552    The names are not in any particular order.
 553    Wildcards at the beginning of PAT do not match an initial period.
 554
 555    The vector is terminated by an element that is a null pointer.
 556
 557    To free the space allocated, first free the vector's elements,
 558    then free the vector.
 559
 560    Return 0 if cannot get enough memory to hold the pointer
 561    and the names.
 562
 563    Return -1 if cannot access directory DIR.
 564    Look in errno for more information.  */
 565
 566 char **
 567 glob_vector (pat, dir, flags)
 568      char *pat;
 569      char *dir;
 570      int flags;
 571 {
 572   DIR *d;
 573   register struct dirent *dp;
 574   struct globval *lastlink, *e, *dirlist;
 575   register struct globval *nextlink;
 576   register char *nextname, *npat, *subdir;
 577   unsigned int count;
 578   int lose, skip, ndirs, isdir, sdlen, add_current, patlen;
 579   register char **name_vector;
 580   register unsigned int i;
 581   int mflags;           /* Flags passed to strmatch (). */
 582   int pflags;           /* flags passed to sh_makepath () */
 583   int nalloca;
 584   struct globval *firstmalloc, *tmplink;
 585   char *convfn;
 586
 587   lastlink = 0;
 588   count = lose = skip = add_current = 0;
 589
 590   firstmalloc = 0;
 591   nalloca = 0;
 592
 593 /*itrace("glob_vector: pat = `%s' dir = `%s' flags = 0x%x", pat, dir, flags);*/
 594   /* If PAT is empty, skip the loop, but return one (empty) filename. */
 595   if (pat == 0 || *pat == '\0')
 596     {
 597       if (glob_testdir (dir, 0) < 0)
 598         return ((char **) &glob_error_return);
 599
 600       nextlink = (struct globval *)alloca (sizeof (struct globval));
 601       if (nextlink == NULL)
 602         return ((char **) NULL);
 603
 604       nextlink->next = (struct globval *)0;
 605       nextname = (char *) malloc (1);
 606       if (nextname == 0)
 607         lose = 1;
 608       else
 609         {
 610           lastlink = nextlink;
 611           nextlink->name = nextname;
 612           nextname[0] = '\0';
 613           count = 1;
 614         }
 615
 616       skip = 1;
 617     }
 618
 619   patlen = (pat && *pat) ? strlen (pat) : 0;
 620
 621   /* If the filename pattern (PAT) does not contain any globbing characters,
 622      we can dispense with reading the directory, and just see if there is
 623      a filename `DIR/PAT'.  If there is, and we can access it, just make the
 624      vector to return and bail immediately. */
 625   if (skip == 0 && glob_pattern_p (pat) == 0)
 626     {
 627       int dirlen;
 628       struct stat finfo;
 629
 630       if (glob_testdir (dir, 0) < 0)
 631         return ((char **) &glob_error_return);
 632
 633       dirlen = strlen (dir);
 634       nextname = (char *)malloc (dirlen + patlen + 2);
 635       npat = (char *)malloc (patlen + 1);
 636       if (nextname == 0 || npat == 0)
 637         {
 638           FREE (nextname);
 639           FREE (npat);
 640           lose = 1;
 641         }
 642       else
 643         {
 644           strcpy (npat, pat);
 645           dequote_pathname (npat);
 646
 647           strcpy (nextname, dir);
 648           nextname[dirlen++] = '/';
 649           strcpy (nextname + dirlen, npat);
 650
 651           if (GLOB_TESTNAME (nextname) >= 0)
 652             {
 653               free (nextname);
 654               nextlink = (struct globval *)alloca (sizeof (struct globval));
 655               if (nextlink)
 656                 {
 657                   nextlink->next = (struct globval *)0;
 658                   lastlink = nextlink;
 659                   nextlink->name = npat;
 660                   count = 1;
 661                 }
 662               else
 663                 {
 664                   free (npat);
 665                   lose = 1;
 666                 }
 667             }
 668           else
 669             {
 670               free (nextname);
 671               free (npat);
 672             }
 673         }
 674
 675       skip = 1;
 676     }
 677
 678   if (skip == 0)
 679     {
 680       /* Open the directory, punting immediately if we cannot.  If opendir
 681          is not robust (i.e., it opens non-directories successfully), test
 682          that DIR is a directory and punt if it's not. */
 683 #if defined (OPENDIR_NOT_ROBUST)
 684       if (glob_testdir (dir, 0) < 0)
 685         return ((char **) &glob_error_return);
 686 #endif
 687
 688       d = opendir (dir);
 689       if (d == NULL)
 690         return ((char **) &glob_error_return);
 691
 692       /* Compute the flags that will be passed to strmatch().  We don't
 693          need to do this every time through the loop. */
 694       mflags = (noglob_dot_filenames ? FNM_PERIOD : 0) | FNM_PATHNAME;
 695
 696 #ifdef FNM_CASEFOLD
 697       if (glob_ignore_case)
 698         mflags |= FNM_CASEFOLD;
 699 #endif
 700
 701       if (extended_glob)
 702         mflags |= FNM_EXTMATCH;
 703
 704       add_current = ((flags & (GX_ALLDIRS|GX_ADDCURDIR)) == (GX_ALLDIRS|GX_ADDCURDIR));
 705
 706       /* Scan the directory, finding all names that match.
 707          For each name that matches, allocate a struct globval
 708          on the stack and store the name in it.
 709          Chain those structs together; lastlink is the front of the chain.  */
 710       while (1)
 711         {
 712           /* Make globbing interruptible in the shell. */
 713           if (interrupt_state || terminating_signal)
 714             {
 715               lose = 1;
 716               break;
 717             }
 718           else if (signal_is_pending (SIGINT))  /* XXX - make SIGINT traps responsive */
 719             {
 720               lose = 1;
 721               break;
 722             }
 723
 724           dp = readdir (d);
 725           if (dp == NULL)
 726             break;
 727
 728           /* If this directory entry is not to be used, try again. */
 729           if (REAL_DIR_ENTRY (dp) == 0)
 730             continue;
 731
 732 #if 0
 733           if (dp->d_name == 0 || *dp->d_name == 0)
 734             continue;
 735 #endif
 736
 737 #if HANDLE_MULTIBYTE
 738           if (MB_CUR_MAX > 1 && mbskipname (pat, dp->d_name, flags))
 739             continue;
 740           else
 741 #endif
 742           if (skipname (pat, dp->d_name, flags))
 743             continue;
 744
 745           /* If we're only interested in directories, don't bother with files */
 746           if (flags & (GX_MATCHDIRS|GX_ALLDIRS))
 747             {
 748               pflags = (flags & GX_ALLDIRS) ? MP_RMDOT : 0;
 749               if (flags & GX_NULLDIR)
 750                 pflags |= MP_IGNDOT;
 751               subdir = sh_makepath (dir, dp->d_name, pflags);
 752               isdir = glob_testdir (subdir, flags);
 753               if (isdir < 0 && (flags & GX_MATCHDIRS))
 754                 {
 755                   free (subdir);
 756                   continue;
 757                 }
 758             }
 759
 760           if (flags & GX_ALLDIRS)
 761             {
 762               if (isdir == 0)
 763                 {
 764                   dirlist = finddirs (pat, subdir, (flags & ~GX_ADDCURDIR), &e, &ndirs);
 765                   if (dirlist == &finddirs_error_return)
 766                     {
 767                       free (subdir);
 768                       lose = 1;
 769                       break;
 770                     }
 771                   if (ndirs)            /* add recursive directories to list */
 772                     {
 773                       if (firstmalloc == 0)
 774                         firstmalloc = e;
 775                       e->next = lastlink;
 776                       lastlink = dirlist;
 777                       count += ndirs;
 778                     }
 779                 }
 780
 781               nextlink = (struct globval *) malloc (sizeof (struct globval));
 782               if (firstmalloc == 0)
 783                 firstmalloc = nextlink;
 784               sdlen = strlen (subdir);
 785               nextname = (char *) malloc (sdlen + 1);
 786               if (nextlink == 0 || nextname == 0)
 787                 {
 788                   FREE (nextlink);
 789                   FREE (nextname);
 790                   free (subdir);
 791                   lose = 1;
 792                   break;
 793                 }
 794               nextlink->next = lastlink;
 795               lastlink = nextlink;
 796               nextlink->name = nextname;
 797               bcopy (subdir, nextname, sdlen + 1);
 798               free (subdir);
 799               ++count;
 800               continue;
 801             }
 802           else if (flags & GX_MATCHDIRS)
 803             free (subdir);
 804
 805           convfn = fnx_fromfs (dp->d_name, D_NAMLEN (dp));
 806           if (strmatch (pat, convfn, mflags) != FNM_NOMATCH)
 807             {
 808               if (nalloca < ALLOCA_MAX)
 809                 {
 810                   nextlink = (struct globval *) alloca (sizeof (struct globval));
 811                   nalloca += sizeof (struct globval);
 812                 }
 813               else
 814                 {
 815                   nextlink = (struct globval *) malloc (sizeof (struct globval));
 816                   if (firstmalloc == 0)
 817                     firstmalloc = nextlink;
 818                 }
 819
 820               nextname = (char *) malloc (D_NAMLEN (dp) + 1);
 821               if (nextlink == 0 || nextname == 0)
 822                 {
 823                   FREE (nextlink);
 824                   FREE (nextname);
 825                   lose = 1;
 826                   break;
 827                 }
 828               nextlink->next = lastlink;
 829               lastlink = nextlink;
 830               nextlink->name = nextname;
 831               bcopy (dp->d_name, nextname, D_NAMLEN (dp) + 1);
 832               ++count;
 833             }
 834         }
 835
 836       (void) closedir (d);
 837     }
 838
 839   /* compat: if GX_ADDCURDIR, add the passed directory also.  Add an empty
 840      directory name as a placeholder if GX_NULLDIR (in which case the passed
 841      directory name is "."). */
 842   if (add_current)
 843     {
 844       sdlen = strlen (dir);
 845       nextname = (char *)malloc (sdlen + 1);
 846       nextlink = (struct globval *) malloc (sizeof (struct globval));
 847       if (nextlink == 0 || nextname == 0)
 848         {
 849           FREE (nextlink);
 850           FREE (nextname);
 851           lose = 1;
 852         }
 853       else
 854         {
 855           nextlink->name = nextname;
 856           nextlink->next = lastlink;
 857           lastlink = nextlink;
 858           if (flags & GX_NULLDIR)
 859             nextname[0] = '\0';
 860           else
 861             bcopy (dir, nextname, sdlen + 1);
 862           ++count;
 863         }
 864     }
 865
 866   if (lose == 0)
 867     {
 868       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 869       lose |= name_vector == NULL;
 870     }
 871
 872   /* Have we run out of memory?  */
 873   if (lose)
 874     {
 875       tmplink = 0;
 876
 877       /* Here free the strings we have got.  */
 878       while (lastlink)
 879         {
 880           /* Since we build the list in reverse order, the first N entries
 881              will be allocated with malloc, if firstmalloc is set, from
 882              lastlink to firstmalloc. */
 883           if (firstmalloc)
 884             {
 885               if (lastlink == firstmalloc)
 886                 firstmalloc = 0;
 887               tmplink = lastlink;
 888             }
 889           else
 890             tmplink = 0;
 891           free (lastlink->name);
 892           lastlink = lastlink->next;
 893           FREE (tmplink);
 894         }
 895
 896       /* Don't call QUIT; here; let higher layers deal with it. */
 897
 898       return ((char **)NULL);
 899     }
 900
 901   /* Copy the name pointers from the linked list into the vector.  */
 902   for (tmplink = lastlink, i = 0; i < count; ++i)
 903     {
 904       name_vector[i] = tmplink->name;
 905       tmplink = tmplink->next;
 906     }
 907
 908   name_vector[count] = NULL;
 909
 910   /* If we allocated some of the struct globvals, free them now. */
 911   if (firstmalloc)
 912     {
 913       tmplink = 0;
 914       while (lastlink)
 915         {
 916           tmplink = lastlink;
 917           if (lastlink == firstmalloc)
 918             lastlink = firstmalloc = 0;
 919           else
 920             lastlink = lastlink->next;
 921           free (tmplink);
 922         }
 923     }
 924
 925   return (name_vector);
 926 }
 927
 928 /* Return a new array which is the concatenation of each string in ARRAY
 929    to DIR.  This function expects you to pass in an allocated ARRAY, and
 930    it takes care of free()ing that array.  Thus, you might think of this
 931    function as side-effecting ARRAY.  This should handle GX_MARKDIRS. */
 932 static char **
 933 glob_dir_to_array (dir, array, flags)
 934      char *dir, **array;
 935      int flags;
 936 {
 937   register unsigned int i, l;
 938   int add_slash;
 939   char **result, *new;
 940   struct stat sb;
 941
 942   l = strlen (dir);
 943   if (l == 0)
 944     {
 945       if (flags & GX_MARKDIRS)
 946         for (i = 0; array[i]; i++)
 947           {
 948             if ((stat (array[i], &sb) == 0) && S_ISDIR (sb.st_mode))
 949               {
 950                 l = strlen (array[i]);
 951                 new = (char *)realloc (array[i], l + 2);
 952                 if (new == 0)
 953                   return NULL;
 954                 new[l] = '/';
 955                 new[l+1] = '\0';
 956                 array[i] = new;
 957               }
 958           }
 959       return (array);
 960     }
 961
 962   add_slash = dir[l - 1] != '/';
 963
 964   i = 0;
 965   while (array[i] != NULL)
 966     ++i;
 967
 968   result = (char **) malloc ((i + 1) * sizeof (char *));
 969   if (result == NULL)
 970     return (NULL);
 971
 972   for (i = 0; array[i] != NULL; i++)
 973     {
 974       /* 3 == 1 for NUL, 1 for slash at end of DIR, 1 for GX_MARKDIRS */
 975       result[i] = (char *) malloc (l + strlen (array[i]) + 3);
 976
 977       if (result[i] == NULL)
 978         {
 979           int ind;
 980           for (ind = 0; ind < i; ind++)
 981             free (result[ind]);
 982           free (result);
 983           return (NULL);
 984         }
 985
 986       strcpy (result[i], dir);
 987       if (add_slash)
 988         result[i][l] = '/';
 989       strcpy (result[i] + l + add_slash, array[i]);
 990       if (flags & GX_MARKDIRS)
 991         {
 992           if ((stat (result[i], &sb) == 0) && S_ISDIR (sb.st_mode))
 993             {
 994               size_t rlen;
 995               rlen = strlen (result[i]);
 996               result[i][rlen] = '/';
 997               result[i][rlen+1] = '\0';
 998             }
 999         }
1000     }
1001   result[i] = NULL;
1002
1003   /* Free the input array.  */
1004   for (i = 0; array[i] != NULL; i++)
1005     free (array[i]);
1006   free ((char *) array);
1007
1008   return (result);
1009 }
1010
1011 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
1012    marking the end of the array with a null-pointer as an element.
1013    If no pathnames match, then the array is empty (first element is null).
1014    If there isn't enough memory, then return NULL.
1015    If a file system error occurs, return -1; `errno' has the error code.  */
1016 char **
1017 glob_filename (pathname, flags)
1018      char *pathname;
1019      int flags;
1020 {
1021   char **result;
1022   unsigned int result_size;
1023   char *directory_name, *filename, *dname, *fn;
1024   unsigned int directory_len;
1025   int free_dirname;                     /* flag */
1026   int dflags;
1027
1028   result = (char **) malloc (sizeof (char *));
1029   result_size = 1;
1030   if (result == NULL)
1031     return (NULL);
1032
1033   result[0] = NULL;
1034
1035   directory_name = NULL;
1036
1037   /* Find the filename.  */
1038   filename = strrchr (pathname, '/');
1039 #if defined (EXTENDED_GLOB)
1040   if (filename && extended_glob)
1041     {
1042       fn = glob_dirscan (pathname, '/');
1043 #if DEBUG_MATCHING
1044       if (fn != filename)
1045         fprintf (stderr, "glob_filename: glob_dirscan: fn (%s) != filename (%s)\n", fn ? fn : "(null)", filename);
1046 #endif
1047       filename = fn;
1048     }
1049 #endif
1050
1051   if (filename == NULL)
1052     {
1053       filename = pathname;
1054       directory_name = "";
1055       directory_len = 0;
1056       free_dirname = 0;
1057     }
1058   else
1059     {
1060       directory_len = (filename - pathname) + 1;
1061       directory_name = (char *) malloc (directory_len + 1);
1062
1063       if (directory_name == 0)          /* allocation failed? */
1064         return (NULL);
1065
1066       bcopy (pathname, directory_name, directory_len);
1067       directory_name[directory_len] = '\0';
1068       ++filename;
1069       free_dirname = 1;
1070     }
1071
1072   /* If directory_name contains globbing characters, then we
1073      have to expand the previous levels.  Just recurse. */
1074   if (directory_len > 0 && glob_pattern_p (directory_name))
1075     {
1076       char **directories, *d, *p;
1077       register unsigned int i;
1078       int all_starstar, last_starstar;
1079
1080       all_starstar = last_starstar = 0;
1081       d = directory_name;
1082       dflags = flags & ~GX_MARKDIRS;
1083       /* Collapse a sequence of ** patterns separated by one or more slashes
1084          to a single ** terminated by a slash or NUL */
1085       if ((flags & GX_GLOBSTAR) && d[0] == '*' && d[1] == '*' && (d[2] == '/' || d[2] == '\0'))
1086         {
1087           p = d;
1088           while (d[0] == '*' && d[1] == '*' && (d[2] == '/' || d[2] == '\0'))
1089             {
1090               p = d;
1091               if (d[2])
1092                 {
1093                   d += 3;
1094                   while (*d == '/')
1095                     d++;
1096                   if (*d == 0)
1097                     break;
1098                 }
1099             }
1100           if (*d == 0)
1101             all_starstar = 1;
1102           d = p;
1103           dflags |= GX_ALLDIRS|GX_ADDCURDIR;
1104           directory_len = strlen (d);
1105         }
1106
1107       /* If there is a non [star][star]/ component in directory_name, we
1108          still need to collapse trailing sequences of [star][star]/ into
1109          a single one and note that the directory name ends with [star][star],
1110          so we can compensate if filename is [star][star] */
1111       if ((flags & GX_GLOBSTAR) && all_starstar == 0)
1112         {
1113           int dl, prev;
1114           prev = dl = directory_len;
1115           while (dl >= 4 && d[dl - 1] == '/' &&
1116                            d[dl - 2] == '*' &&
1117                            d[dl - 3] == '*' &&
1118                            d[dl - 4] == '/')
1119             prev = dl, dl -= 3;
1120           if (dl != directory_len)
1121             last_starstar = 1;
1122           directory_len = prev;
1123         }
1124
1125       /* If the directory name ends in [star][star]/ but the filename is
1126          [star][star], just remove the final [star][star] from the directory
1127          so we don't have to scan everything twice. */
1128       if (last_starstar && directory_len > 4 &&
1129             filename[0] == '*' && filename[1] == '*' && filename[2] == 0)
1130         {
1131           directory_len -= 3;
1132         }
1133
1134       if (d[directory_len - 1] == '/')
1135         d[directory_len - 1] = '\0';
1136
1137       directories = glob_filename (d, dflags);
1138
1139       if (free_dirname)
1140         {
1141           free (directory_name);
1142           directory_name = NULL;
1143         }
1144
1145       if (directories == NULL)
1146         goto memory_error;
1147       else if (directories == (char **)&glob_error_return)
1148         {
1149           free ((char *) result);
1150           return ((char **) &glob_error_return);
1151         }
1152       else if (*directories == NULL)
1153         {
1154           free ((char *) directories);
1155           free ((char *) result);
1156           return ((char **) &glob_error_return);
1157         }
1158
1159       /* If we have something like [star][star]/[star][star], it's no use to
1160          glob **, then do it again, and throw half the results away.  */
1161       if (all_starstar && filename[0] == '*' && filename[1] == '*' && filename[2] == 0)
1162         {
1163           free ((char *) directories);
1164           free (directory_name);
1165           directory_name = NULL;
1166           directory_len = 0;
1167           goto only_filename;
1168         }
1169
1170       /* We have successfully globbed the preceding directory name.
1171          For each name in DIRECTORIES, call glob_vector on it and
1172          FILENAME.  Concatenate the results together.  */
1173       for (i = 0; directories[i] != NULL; ++i)
1174         {
1175           char **temp_results;
1176           int shouldbreak;
1177
1178           shouldbreak = 0;
1179           /* XXX -- we've recursively scanned any directories resulting from
1180              a `**', so turn off the flag.  We turn it on again below if
1181              filename is `**' */
1182           /* Scan directory even on a NULL filename.  That way, `*h/'
1183              returns only directories ending in `h', instead of all
1184              files ending in `h' with a `/' appended. */
1185           dname = directories[i];
1186           dflags = flags & ~(GX_MARKDIRS|GX_ALLDIRS|GX_ADDCURDIR);
1187           if ((flags & GX_GLOBSTAR) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
1188             dflags |= GX_ALLDIRS|GX_ADDCURDIR;
1189           if (dname[0] == '\0' && filename[0])
1190             {
1191               dflags |= GX_NULLDIR;
1192               dname = ".";      /* treat null directory name and non-null filename as current directory */
1193             }
1194           temp_results = glob_vector (filename, dname, dflags);
1195
1196           /* Handle error cases. */
1197           if (temp_results == NULL)
1198             goto memory_error;
1199           else if (temp_results == (char **)&glob_error_return)
1200             /* This filename is probably not a directory.  Ignore it.  */
1201             ;
1202           else
1203             {
1204               char **array;
1205               register unsigned int l;
1206
1207               /* If we're expanding **, we don't need to glue the directory
1208                  name to the results; we've already done it in glob_vector */
1209               if ((dflags & GX_ALLDIRS) && filename[0] == '*' && filename[1] == '*' && (filename[2] == '\0' || filename[2] == '/'))
1210                 {
1211                   /* When do we remove null elements from temp_results?  And
1212                      how to avoid duplicate elements in the final result? */
1213                   /* If (dflags & GX_NULLDIR) glob_filename potentially left a
1214                      NULL placeholder in the temp results just in case
1215                      glob_vector/glob_dir_to_array did something with it, but
1216                      if it didn't, and we're not supposed to be passing them
1217                      through for some reason ((flags & GX_NULLDIR) == 0) we
1218                      need to remove all the NULL elements from the beginning
1219                      of TEMP_RESULTS. */
1220                   /* If we have a null directory name and ** as the filename,
1221                      we have just searched for everything from the current
1222                      directory on down. Break now (shouldbreak = 1) to avoid
1223                      duplicate entries in the final result. */
1224 #define NULL_PLACEHOLDER(x)     ((x) && *(x) && **(x) == 0)
1225                   if ((dflags & GX_NULLDIR) && (flags & GX_NULLDIR) == 0 &&
1226                         NULL_PLACEHOLDER (temp_results))
1227 #undef NULL_PLACEHOLDER
1228                     {
1229                       register int i, n;
1230                       for (n = 0; temp_results[n] && *temp_results[n] == 0; n++)
1231                         ;
1232                       i = n;
1233                       do
1234                         temp_results[i - n] = temp_results[i];
1235                       while (temp_results[i++] != 0);
1236                       array = temp_results;
1237                       shouldbreak = 1;
1238                     }
1239                   else
1240                     array = temp_results;
1241                 }
1242               else
1243                 array = glob_dir_to_array (directories[i], temp_results, flags);
1244               l = 0;
1245               while (array[l] != NULL)
1246                 ++l;
1247
1248               result =
1249                 (char **)realloc (result, (result_size + l) * sizeof (char *));
1250
1251               if (result == NULL)
1252                 goto memory_error;
1253
1254               for (l = 0; array[l] != NULL; ++l)
1255                 result[result_size++ - 1] = array[l];
1256
1257               result[result_size - 1] = NULL;
1258
1259               /* Note that the elements of ARRAY are not freed.  */
1260               if (array != temp_results)
1261                 free ((char *) array);
1262               else if ((dflags & GX_ALLDIRS) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
1263                 free (temp_results);    /* expanding ** case above */
1264
1265               if (shouldbreak)
1266                 break;
1267             }
1268         }
1269       /* Free the directories.  */
1270       for (i = 0; directories[i]; i++)
1271         free (directories[i]);
1272
1273       free ((char *) directories);
1274
1275       return (result);
1276     }
1277
1278 only_filename:
1279   /* If there is only a directory name, return it. */
1280   if (*filename == '\0')
1281     {
1282       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
1283       if (result == NULL)
1284         return (NULL);
1285       /* Handle GX_MARKDIRS here. */
1286       result[0] = (char *) malloc (directory_len + 1);
1287       if (result[0] == NULL)
1288         goto memory_error;
1289       bcopy (directory_name, result[0], directory_len + 1);
1290       if (free_dirname)
1291         free (directory_name);
1292       result[1] = NULL;
1293       return (result);
1294     }
1295   else
1296     {
1297       char **temp_results;
1298
1299       /* There are no unquoted globbing characters in DIRECTORY_NAME.
1300          Dequote it before we try to open the directory since there may
1301          be quoted globbing characters which should be treated verbatim. */
1302       if (directory_len > 0)
1303         dequote_pathname (directory_name);
1304
1305       /* We allocated a small array called RESULT, which we won't be using.
1306          Free that memory now. */
1307       free (result);
1308
1309       /* Just return what glob_vector () returns appended to the
1310          directory name. */
1311       /* If flags & GX_ALLDIRS, we're called recursively */
1312       dflags = flags & ~GX_MARKDIRS;
1313       if (directory_len == 0)
1314         dflags |= GX_NULLDIR;
1315       if ((flags & GX_GLOBSTAR) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
1316         {
1317           dflags |= GX_ALLDIRS|GX_ADDCURDIR;
1318 #if 0
1319           /* If we want all directories (dflags & GX_ALLDIRS) and we're not
1320              being called recursively as something like `echo [star][star]/[star].o'
1321              ((flags & GX_ALLDIRS) == 0), we want to prevent glob_vector from
1322              adding a null directory name to the front of the temp_results
1323              array.  We turn off ADDCURDIR if not called recursively and
1324              dlen == 0 */
1325 #endif
1326           if (directory_len == 0 && (flags & GX_ALLDIRS) == 0)
1327             dflags &= ~GX_ADDCURDIR;
1328         }
1329       temp_results = glob_vector (filename,
1330                                   (directory_len == 0 ? "." : directory_name),
1331                                   dflags);
1332
1333       if (temp_results == NULL || temp_results == (char **)&glob_error_return)
1334         {
1335           if (free_dirname)
1336             free (directory_name);
1337           QUIT;                 /* XXX - shell */
1338           run_pending_traps ();
1339           return (temp_results);
1340         }
1341
1342       result = glob_dir_to_array ((dflags & GX_ALLDIRS) ? "" : directory_name, temp_results, flags);
1343
1344       if (free_dirname)
1345         free (directory_name);
1346       return (result);
1347     }
1348
1349   /* We get to memory_error if the program has run out of memory, or
1350      if this is the shell, and we have been interrupted. */
1351  memory_error:
1352   if (result != NULL)
1353     {
1354       register unsigned int i;
1355       for (i = 0; result[i] != NULL; ++i)
1356         free (result[i]);
1357       free ((char *) result);
1358     }
1359
1360   if (free_dirname && directory_name)
1361     free (directory_name);
1362
1363   QUIT;
1364   run_pending_traps ();
1365
1366   return (NULL);
1367 }
1368
1369 #if defined (TEST)
1370
1371 main (argc, argv)
1372      int argc;
1373      char **argv;
1374 {
1375   unsigned int i;
1376
1377   for (i = 1; i < argc; ++i)
1378     {
1379       char **value = glob_filename (argv[i], 0);
1380       if (value == NULL)
1381         puts ("Out of memory.");
1382       else if (value == &glob_error_return)
1383         perror (argv[i]);
1384       else
1385         for (i = 0; value[i] != NULL; i++)
1386           puts (value[i]);
1387     }
1388
1389   exit (0);
1390 }
1391 #endif  /* TEST.  */