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