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