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 "shell.h"
  52
  53 #include "glob.h"
  54 #include "strmatch.h"
  55
  56 #if !defined (HAVE_BCOPY) && !defined (bcopy)
  57 #  define bcopy(s, d, n) ((void) memcpy ((d), (s), (n)))
  58 #endif /* !HAVE_BCOPY && !bcopy */
  59
  60 #if !defined (NULL)
  61 #  if defined (__STDC__)
  62 #    define NULL ((void *) 0)
  63 #  else
  64 #    define NULL 0x0
  65 #  endif /* __STDC__ */
  66 #endif /* !NULL */
  67
  68 #if !defined (FREE)
  69 #  define FREE(x)       if (x) free (x)
  70 #endif
  71
  72 /* Don't try to alloca() more than this much memory for `struct globval'
  73    in glob_vector() */
  74 #ifndef ALLOCA_MAX
  75 #  define ALLOCA_MAX    100000
  76 #endif
  77
  78 struct globval
  79   {
  80     struct globval *next;
  81     char *name;
  82   };
  83
  84 extern void throw_to_top_level __P((void));
  85 extern int sh_eaccess __P((char *, int));
  86 extern char *sh_makepath __P((const char *, const char *, int));
  87
  88 extern int extended_glob;
  89
  90 /* Global variable which controls whether or not * matches .*.
  91    Non-zero means don't match .*.  */
  92 int noglob_dot_filenames = 1;
  93
  94 /* Global variable which controls whether or not filename globbing
  95    is done without regard to case. */
  96 int glob_ignore_case = 0;
  97
  98 /* Global variable to return to signify an error in globbing. */
  99 char *glob_error_return;
 100
 101 static struct globval finddirs_error_return;
 102
 103 /* Some forward declarations. */
 104 static int skipname __P((char *, char *, int));
 105 #if HANDLE_MULTIBYTE
 106 static int mbskipname __P((char *, char *, int));
 107 #endif
 108 #if HANDLE_MULTIBYTE
 109 static void udequote_pathname __P((char *));
 110 static void wdequote_pathname __P((char *));
 111 #else
 112 #  define dequote_pathname udequote_pathname
 113 #endif
 114 static void dequote_pathname __P((char *));
 115 static int glob_testdir __P((char *));
 116 static char **glob_dir_to_array __P((char *, char **, int));
 117
 118 /* Compile `glob_loop.c' for single-byte characters. */
 119 #define CHAR    unsigned char
 120 #define INT     int
 121 #define L(CS)   CS
 122 #define INTERNAL_GLOB_PATTERN_P internal_glob_pattern_p
 123 #include "glob_loop.c"
 124
 125 /* Compile `glob_loop.c' again for multibyte characters. */
 126 #if HANDLE_MULTIBYTE
 127
 128 #define CHAR    wchar_t
 129 #define INT     wint_t
 130 #define L(CS)   L##CS
 131 #define INTERNAL_GLOB_PATTERN_P internal_glob_wpattern_p
 132 #include "glob_loop.c"
 133
 134 #endif /* HANDLE_MULTIBYTE */
 135
 136 /* And now a function that calls either the single-byte or multibyte version
 137    of internal_glob_pattern_p. */
 138 int
 139 glob_pattern_p (pattern)
 140      const char *pattern;
 141 {
 142 #if HANDLE_MULTIBYTE
 143   size_t n;
 144   wchar_t *wpattern;
 145   int r;
 146
 147   if (MB_CUR_MAX == 1)
 148     return (internal_glob_pattern_p ((unsigned char *)pattern));
 149
 150   /* Convert strings to wide chars, and call the multibyte version. */
 151   n = xdupmbstowcs (&wpattern, NULL, pattern);
 152   if (n == (size_t)-1)
 153     /* Oops.  Invalid multibyte sequence.  Try it as single-byte sequence. */
 154     return (internal_glob_pattern_p ((unsigned char *)pattern));
 155
 156   r = internal_glob_wpattern_p (wpattern);
 157   free (wpattern);
 158
 159   return r;
 160 #else
 161   return (internal_glob_pattern_p (pattern));
 162 #endif
 163 }
 164
 165 /* Return 1 if DNAME should be skipped according to PAT.  Mostly concerned
 166    with matching leading `.'. */
 167
 168 static int
 169 skipname (pat, dname, flags)
 170      char *pat;
 171      char *dname;
 172      int flags;
 173 {
 174   /* If a leading dot need not be explicitly matched, and the pattern
 175      doesn't start with a `.', don't match `.' or `..' */
 176   if (noglob_dot_filenames == 0 && pat[0] != '.' &&
 177         (pat[0] != '\\' || pat[1] != '.') &&
 178         (dname[0] == '.' &&
 179           (dname[1] == '\0' || (dname[1] == '.' && dname[2] == '\0'))))
 180     return 1;
 181
 182   /* If a dot must be explicity matched, check to see if they do. */
 183   else if (noglob_dot_filenames && dname[0] == '.' && pat[0] != '.' &&
 184         (pat[0] != '\\' || pat[1] != '.'))
 185     return 1;
 186
 187   return 0;
 188 }
 189
 190 #if HANDLE_MULTIBYTE
 191 /* Return 1 if DNAME should be skipped according to PAT.  Handles multibyte
 192    characters in PAT and DNAME.  Mostly concerned with matching leading `.'. */
 193
 194 static int
 195 mbskipname (pat, dname, flags)
 196      char *pat, *dname;
 197      int flags;
 198 {
 199   int ret;
 200   wchar_t *pat_wc, *dn_wc;
 201   size_t pat_n, dn_n;
 202
 203   pat_n = xdupmbstowcs (&pat_wc, NULL, pat);
 204   dn_n = xdupmbstowcs (&dn_wc, NULL, dname);
 205
 206   ret = 0;
 207   if (pat_n != (size_t)-1 && dn_n !=(size_t)-1)
 208     {
 209       /* If a leading dot need not be explicitly matched, and the
 210          pattern doesn't start with a `.', don't match `.' or `..' */
 211       if (noglob_dot_filenames == 0 && pat_wc[0] != L'.' &&
 212             (pat_wc[0] != L'\\' || pat_wc[1] != L'.') &&
 213             (dn_wc[0] == L'.' &&
 214               (dn_wc[1] == L'\0' || (dn_wc[1] == L'.' && dn_wc[2] == L'\0'))))
 215         ret = 1;
 216
 217       /* If a leading dot must be explicity matched, check to see if the
 218          pattern and dirname both have one. */
 219      else if (noglob_dot_filenames && dn_wc[0] == L'.' &&
 220            pat_wc[0] != L'.' &&
 221            (pat_wc[0] != L'\\' || pat_wc[1] != L'.'))
 222         ret = 1;
 223     }
 224
 225   FREE (pat_wc);
 226   FREE (dn_wc);
 227
 228   return ret;
 229 }
 230 #endif /* HANDLE_MULTIBYTE */
 231
 232 /* Remove backslashes quoting characters in PATHNAME by modifying PATHNAME. */
 233 static void
 234 udequote_pathname (pathname)
 235      char *pathname;
 236 {
 237   register int i, j;
 238
 239   for (i = j = 0; pathname && pathname[i]; )
 240     {
 241       if (pathname[i] == '\\')
 242         i++;
 243
 244       pathname[j++] = pathname[i++];
 245
 246       if (pathname[i - 1] == 0)
 247         break;
 248     }
 249   pathname[j] = '\0';
 250 }
 251
 252 #if HANDLE_MULTIBYTE
 253 /* Remove backslashes quoting characters in PATHNAME by modifying PATHNAME. */
 254 static void
 255 wdequote_pathname (pathname)
 256      char *pathname;
 257 {
 258   mbstate_t ps;
 259   size_t len, n;
 260   wchar_t *wpathname;
 261   int i, j;
 262   wchar_t *orig_wpathname;
 263
 264   len = strlen (pathname);
 265   /* Convert the strings into wide characters.  */
 266   n = xdupmbstowcs (&wpathname, NULL, pathname);
 267   if (n == (size_t) -1)
 268     /* Something wrong. */
 269     return;
 270   orig_wpathname = wpathname;
 271
 272   for (i = j = 0; wpathname && wpathname[i]; )
 273     {
 274       if (wpathname[i] == L'\\')
 275         i++;
 276
 277       wpathname[j++] = wpathname[i++];
 278
 279       if (wpathname[i - 1] == L'\0')
 280         break;
 281     }
 282   wpathname[j] = L'\0';
 283
 284   /* Convert the wide character string into unibyte character set. */
 285   memset (&ps, '\0', sizeof(mbstate_t));
 286   n = wcsrtombs(pathname, (const wchar_t **)&wpathname, len, &ps);
 287   pathname[len] = '\0';
 288
 289   /* Can't just free wpathname here; wcsrtombs changes it in many cases. */
 290   free (orig_wpathname);
 291 }
 292
 293 static void
 294 dequote_pathname (pathname)
 295      char *pathname;
 296 {
 297   if (MB_CUR_MAX > 1)
 298     wdequote_pathname (pathname);
 299   else
 300     udequote_pathname (pathname);
 301 }
 302 #endif /* HANDLE_MULTIBYTE */
 303
 304 /* Test whether NAME exists. */
 305
 306 #if defined (HAVE_LSTAT)
 307 #  define GLOB_TESTNAME(name)  (lstat (name, &finfo))
 308 #else /* !HAVE_LSTAT */
 309 #  if !defined (AFS)
 310 #    define GLOB_TESTNAME(name)  (sh_eaccess (nextname, F_OK))
 311 #  else /* AFS */
 312 #    define GLOB_TESTNAME(name)  (access (nextname, F_OK))
 313 #  endif /* AFS */
 314 #endif /* !HAVE_LSTAT */
 315
 316 /* Return 0 if DIR is a directory, -1 otherwise. */
 317 static int
 318 glob_testdir (dir)
 319      char *dir;
 320 {
 321   struct stat finfo;
 322
 323   if (stat (dir, &finfo) < 0)
 324     return (-1);
 325
 326   if (S_ISDIR (finfo.st_mode) == 0)
 327     return (-1);
 328
 329   return (0);
 330 }
 331
 332 /* Recursively scan SDIR for directories matching PAT (PAT is always `**').
 333    FLAGS is simply passed down to the recursive call to glob_vector.  Returns
 334    a list of matching directory names.  EP, if non-null, is set to the last
 335    element of the returned list.  NP, if non-null, is set to the number of
 336    directories in the returned list.  These two variables exist for the
 337    convenience of the caller (always glob_vector). */
 338 static struct globval *
 339 finddirs (pat, sdir, flags, ep, np)
 340      char *pat;
 341      char *sdir;
 342      int flags;
 343      struct globval **ep;
 344      int *np;
 345 {
 346   char **r, *n;
 347   int ndirs;
 348   struct globval *ret, *e, *g;
 349
 350 /*itrace("finddirs: pat = `%s' sdir = `%s' flags = 0x%x", pat, sdir, flags);*/
 351   e = ret = 0;
 352   r = glob_vector (pat, sdir, flags);
 353   if (r == 0 || r[0] == 0)
 354     {
 355       if (np)
 356         *np = 0;
 357       if (ep)
 358         *ep = 0;
 359       if (r && r != &glob_error_return)
 360         free (r);
 361       return (struct globval *)0;
 362     }
 363   for (ndirs = 0; r[ndirs] != 0; ndirs++)
 364     {
 365       g = (struct globval *) malloc (sizeof (struct globval));
 366       if (g == 0)
 367         {
 368           while (ret)           /* free list built so far */
 369             {
 370               g = ret->next;
 371               free (ret);
 372               ret = g;
 373             }
 374
 375           free (r);
 376           if (np)
 377             *np = 0;
 378           if (ep)
 379             *ep = 0;
 380           return (&finddirs_error_return);
 381         }
 382       if (e == 0)
 383         e = g;
 384
 385       g->next = ret;
 386       ret = g;
 387
 388       g->name = r[ndirs];
 389     }
 390
 391   free (r);
 392   if (ep)
 393     *ep = e;
 394   if (np)
 395     *np = ndirs;
 396
 397   return ret;
 398 }
 399
 400
 401 /* Return a vector of names of files in directory DIR
 402    whose names match glob pattern PAT.
 403    The names are not in any particular order.
 404    Wildcards at the beginning of PAT do not match an initial period.
 405
 406    The vector is terminated by an element that is a null pointer.
 407
 408    To free the space allocated, first free the vector's elements,
 409    then free the vector.
 410
 411    Return 0 if cannot get enough memory to hold the pointer
 412    and the names.
 413
 414    Return -1 if cannot access directory DIR.
 415    Look in errno for more information.  */
 416
 417 char **
 418 glob_vector (pat, dir, flags)
 419      char *pat;
 420      char *dir;
 421      int flags;
 422 {
 423   DIR *d;
 424   register struct dirent *dp;
 425   struct globval *lastlink, *e, *dirlist;
 426   register struct globval *nextlink;
 427   register char *nextname, *npat, *subdir;
 428   unsigned int count;
 429   int lose, skip, ndirs, isdir, sdlen, add_current;
 430   register char **name_vector;
 431   register unsigned int i;
 432   int mflags;           /* Flags passed to strmatch (). */
 433   int pflags;           /* flags passed to sh_makepath () */
 434   int nalloca;
 435   struct globval *firstmalloc, *tmplink;
 436
 437   lastlink = 0;
 438   count = lose = skip = add_current = 0;
 439
 440   firstmalloc = 0;
 441   nalloca = 0;
 442
 443 /*itrace("glob_vector: pat = `%s' dir = `%s' flags = 0x%x", pat, dir, flags);*/
 444   /* If PAT is empty, skip the loop, but return one (empty) filename. */
 445   if (pat == 0 || *pat == '\0')
 446     {
 447       if (glob_testdir (dir) < 0)
 448         return ((char **) &glob_error_return);
 449
 450       nextlink = (struct globval *)alloca (sizeof (struct globval));
 451       if (nextlink == NULL)
 452         return ((char **) NULL);
 453
 454       nextlink->next = (struct globval *)0;
 455       nextname = (char *) malloc (1);
 456       if (nextname == 0)
 457         lose = 1;
 458       else
 459         {
 460           lastlink = nextlink;
 461           nextlink->name = nextname;
 462           nextname[0] = '\0';
 463           count = 1;
 464         }
 465
 466       skip = 1;
 467     }
 468
 469   /* If the filename pattern (PAT) does not contain any globbing characters,
 470      we can dispense with reading the directory, and just see if there is
 471      a filename `DIR/PAT'.  If there is, and we can access it, just make the
 472      vector to return and bail immediately. */
 473   if (skip == 0 && glob_pattern_p (pat) == 0)
 474     {
 475       int dirlen;
 476       struct stat finfo;
 477
 478       if (glob_testdir (dir) < 0)
 479         return ((char **) &glob_error_return);
 480
 481       dirlen = strlen (dir);
 482       nextname = (char *)malloc (dirlen + strlen (pat) + 2);
 483       npat = (char *)malloc (strlen (pat) + 1);
 484       if (nextname == 0 || npat == 0)
 485         lose = 1;
 486       else
 487         {
 488           strcpy (npat, pat);
 489           dequote_pathname (npat);
 490
 491           strcpy (nextname, dir);
 492           nextname[dirlen++] = '/';
 493           strcpy (nextname + dirlen, npat);
 494
 495           if (GLOB_TESTNAME (nextname) >= 0)
 496             {
 497               free (nextname);
 498               nextlink = (struct globval *)alloca (sizeof (struct globval));
 499               if (nextlink)
 500                 {
 501                   nextlink->next = (struct globval *)0;
 502                   lastlink = nextlink;
 503                   nextlink->name = npat;
 504                   count = 1;
 505                 }
 506               else
 507                 lose = 1;
 508             }
 509           else
 510             {
 511               free (nextname);
 512               free (npat);
 513             }
 514         }
 515
 516       skip = 1;
 517     }
 518
 519   if (skip == 0)
 520     {
 521       /* Open the directory, punting immediately if we cannot.  If opendir
 522          is not robust (i.e., it opens non-directories successfully), test
 523          that DIR is a directory and punt if it's not. */
 524 #if defined (OPENDIR_NOT_ROBUST)
 525       if (glob_testdir (dir) < 0)
 526         return ((char **) &glob_error_return);
 527 #endif
 528
 529       d = opendir (dir);
 530       if (d == NULL)
 531         return ((char **) &glob_error_return);
 532
 533       /* Compute the flags that will be passed to strmatch().  We don't
 534          need to do this every time through the loop. */
 535       mflags = (noglob_dot_filenames ? FNM_PERIOD : 0) | FNM_PATHNAME;
 536
 537 #ifdef FNM_CASEFOLD
 538       if (glob_ignore_case)
 539         mflags |= FNM_CASEFOLD;
 540 #endif
 541
 542       if (extended_glob)
 543         mflags |= FNM_EXTMATCH;
 544
 545       add_current = ((flags & (GX_ALLDIRS|GX_ADDCURDIR)) == (GX_ALLDIRS|GX_ADDCURDIR));
 546
 547       /* Scan the directory, finding all names that match.
 548          For each name that matches, allocate a struct globval
 549          on the stack and store the name in it.
 550          Chain those structs together; lastlink is the front of the chain.  */
 551       while (1)
 552         {
 553           /* Make globbing interruptible in the shell. */
 554           if (interrupt_state || terminating_signal)
 555             {
 556               lose = 1;
 557               break;
 558             }
 559
 560           dp = readdir (d);
 561           if (dp == NULL)
 562             break;
 563
 564           /* If this directory entry is not to be used, try again. */
 565           if (REAL_DIR_ENTRY (dp) == 0)
 566             continue;
 567
 568 #if 0
 569           if (dp->d_name == 0 || *dp->d_name == 0)
 570             continue;
 571 #endif
 572
 573 #if HANDLE_MULTIBYTE
 574           if (MB_CUR_MAX > 1 && mbskipname (pat, dp->d_name, flags))
 575             continue;
 576           else
 577 #endif
 578           if (skipname (pat, dp->d_name, flags))
 579             continue;
 580
 581           /* If we're only interested in directories, don't bother with files */
 582           if (flags & (GX_MATCHDIRS|GX_ALLDIRS))
 583             {
 584               pflags = (flags & GX_ALLDIRS) ? MP_RMDOT : 0;
 585               if (flags & GX_NULLDIR)
 586                 pflags |= MP_IGNDOT;
 587               subdir = sh_makepath (dir, dp->d_name, pflags);
 588               isdir = glob_testdir (subdir);
 589               if (isdir < 0 && (flags & GX_MATCHDIRS))
 590                 {
 591                   free (subdir);
 592                   continue;
 593                 }
 594             }
 595
 596           if (flags & GX_ALLDIRS)
 597             {
 598               if (isdir == 0)
 599                 {
 600                   dirlist = finddirs (pat, subdir, (flags & ~GX_ADDCURDIR), &e, &ndirs);
 601                   if (dirlist == &finddirs_error_return)
 602                     {
 603                       free (subdir);
 604                       lose = 1;
 605                       break;
 606                     }
 607                   if (ndirs)            /* add recursive directories to list */
 608                     {
 609                       if (firstmalloc == 0)
 610                         firstmalloc = e;
 611                       e->next = lastlink;
 612                       lastlink = dirlist;
 613                       count += ndirs;
 614                     }
 615                 }
 616
 617               nextlink = (struct globval *) malloc (sizeof (struct globval));
 618               if (firstmalloc == 0)
 619                 firstmalloc = nextlink;
 620               sdlen = strlen (subdir);
 621               nextname = (char *) malloc (sdlen + 1);
 622               if (nextlink == 0 || nextname == 0)
 623                 {
 624                   free (subdir);
 625                   lose = 1;
 626                   break;
 627                 }
 628               nextlink->next = lastlink;
 629               lastlink = nextlink;
 630               nextlink->name = nextname;
 631               bcopy (subdir, nextname, sdlen + 1);
 632               free (subdir);
 633               ++count;
 634               continue;
 635             }
 636
 637           if (strmatch (pat, dp->d_name, mflags) != FNM_NOMATCH)
 638             {
 639               if (nalloca < ALLOCA_MAX)
 640                 {
 641                   nextlink = (struct globval *) alloca (sizeof (struct globval));
 642                   nalloca += sizeof (struct globval);
 643                 }
 644               else
 645                 {
 646                   nextlink = (struct globval *) malloc (sizeof (struct globval));
 647                   if (firstmalloc == 0)
 648                     firstmalloc = nextlink;
 649                 }
 650
 651               nextname = (char *) malloc (D_NAMLEN (dp) + 1);
 652               if (nextlink == 0 || nextname == 0)
 653                 {
 654                   lose = 1;
 655                   break;
 656                 }
 657               nextlink->next = lastlink;
 658               lastlink = nextlink;
 659               nextlink->name = nextname;
 660               bcopy (dp->d_name, nextname, D_NAMLEN (dp) + 1);
 661               ++count;
 662             }
 663         }
 664
 665       (void) closedir (d);
 666     }
 667
 668   /* compat: if GX_ADDCURDIR, add the passed directory also.  Add an empty
 669      directory name as a placeholder if GX_NULLDIR (in which case the passed
 670      directory name is "."). */
 671   if (add_current)
 672     {
 673       sdlen = strlen (dir);
 674       nextname = (char *)malloc (sdlen + 1);
 675       nextlink = (struct globval *) malloc (sizeof (struct globval));
 676       if (nextlink == 0 || nextname == 0)
 677         lose = 1;
 678       else
 679         {
 680           nextlink->name = nextname;
 681           nextlink->next = lastlink;
 682           lastlink = nextlink;
 683           if (flags & GX_NULLDIR)
 684             nextname[0] = '\0';
 685           else
 686             bcopy (dir, nextname, sdlen + 1);
 687           ++count;
 688         }
 689     }
 690
 691   if (lose == 0)
 692     {
 693       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 694       lose |= name_vector == NULL;
 695     }
 696
 697   /* Have we run out of memory?  */
 698   if (lose)
 699     {
 700       tmplink = 0;
 701
 702       /* Here free the strings we have got.  */
 703       while (lastlink)
 704         {
 705           /* Since we build the list in reverse order, the first N entries
 706              will be allocated with malloc, if firstmalloc is set, from
 707              lastlink to firstmalloc. */
 708           if (firstmalloc)
 709             {
 710               if (lastlink == firstmalloc)
 711                 firstmalloc = 0;
 712               tmplink = lastlink;
 713             }
 714           else
 715             tmplink = 0;
 716           free (lastlink->name);
 717           lastlink = lastlink->next;
 718           FREE (tmplink);
 719         }
 720
 721       QUIT;
 722
 723       return ((char **)NULL);
 724     }
 725
 726   /* Copy the name pointers from the linked list into the vector.  */
 727   for (tmplink = lastlink, i = 0; i < count; ++i)
 728     {
 729       name_vector[i] = tmplink->name;
 730       tmplink = tmplink->next;
 731     }
 732
 733   name_vector[count] = NULL;
 734
 735   /* If we allocated some of the struct globvals, free them now. */
 736   if (firstmalloc)
 737     {
 738       tmplink = 0;
 739       while (lastlink)
 740         {
 741           tmplink = lastlink;
 742           if (lastlink == firstmalloc)
 743             lastlink = firstmalloc = 0;
 744           else
 745             lastlink = lastlink->next;
 746           free (tmplink);
 747         }
 748     }
 749
 750   return (name_vector);
 751 }
 752
 753 /* Return a new array which is the concatenation of each string in ARRAY
 754    to DIR.  This function expects you to pass in an allocated ARRAY, and
 755    it takes care of free()ing that array.  Thus, you might think of this
 756    function as side-effecting ARRAY.  This should handle GX_MARKDIRS. */
 757 static char **
 758 glob_dir_to_array (dir, array, flags)
 759      char *dir, **array;
 760      int flags;
 761 {
 762   register unsigned int i, l;
 763   int add_slash;
 764   char **result, *new;
 765   struct stat sb;
 766
 767   l = strlen (dir);
 768   if (l == 0)
 769     {
 770       if (flags & GX_MARKDIRS)
 771         for (i = 0; array[i]; i++)
 772           {
 773             if ((stat (array[i], &sb) == 0) && S_ISDIR (sb.st_mode))
 774               {
 775                 l = strlen (array[i]);
 776                 new = (char *)realloc (array[i], l + 2);
 777                 if (new == 0)
 778                   return NULL;
 779                 new[l] = '/';
 780                 new[l+1] = '\0';
 781                 array[i] = new;
 782               }
 783           }
 784       return (array);
 785     }
 786
 787   add_slash = dir[l - 1] != '/';
 788
 789   i = 0;
 790   while (array[i] != NULL)
 791     ++i;
 792
 793   result = (char **) malloc ((i + 1) * sizeof (char *));
 794   if (result == NULL)
 795     return (NULL);
 796
 797   for (i = 0; array[i] != NULL; i++)
 798     {
 799       /* 3 == 1 for NUL, 1 for slash at end of DIR, 1 for GX_MARKDIRS */
 800       result[i] = (char *) malloc (l + strlen (array[i]) + 3);
 801
 802       if (result[i] == NULL)
 803         return (NULL);
 804
 805       strcpy (result[i], dir);
 806       if (add_slash)
 807         result[i][l] = '/';
 808       strcpy (result[i] + l + add_slash, array[i]);
 809       if (flags & GX_MARKDIRS)
 810         {
 811           if ((stat (result[i], &sb) == 0) && S_ISDIR (sb.st_mode))
 812             {
 813               size_t rlen;
 814               rlen = strlen (result[i]);
 815               result[i][rlen] = '/';
 816               result[i][rlen+1] = '\0';
 817             }
 818         }
 819     }
 820   result[i] = NULL;
 821
 822   /* Free the input array.  */
 823   for (i = 0; array[i] != NULL; i++)
 824     free (array[i]);
 825   free ((char *) array);
 826
 827   return (result);
 828 }
 829
 830 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 831    marking the end of the array with a null-pointer as an element.
 832    If no pathnames match, then the array is empty (first element is null).
 833    If there isn't enough memory, then return NULL.
 834    If a file system error occurs, return -1; `errno' has the error code.  */
 835 char **
 836 glob_filename (pathname, flags)
 837      char *pathname;
 838      int flags;
 839 {
 840   char **result;
 841   unsigned int result_size;
 842   char *directory_name, *filename, *dname;
 843   unsigned int directory_len;
 844   int free_dirname;                     /* flag */
 845   int dflags;
 846
 847   result = (char **) malloc (sizeof (char *));
 848   result_size = 1;
 849   if (result == NULL)
 850     return (NULL);
 851
 852   result[0] = NULL;
 853
 854   directory_name = NULL;
 855
 856   /* Find the filename.  */
 857   filename = strrchr (pathname, '/');
 858   if (filename == NULL)
 859     {
 860       filename = pathname;
 861       directory_name = "";
 862       directory_len = 0;
 863       free_dirname = 0;
 864     }
 865   else
 866     {
 867       directory_len = (filename - pathname) + 1;
 868       directory_name = (char *) malloc (directory_len + 1);
 869
 870       if (directory_name == 0)          /* allocation failed? */
 871         return (NULL);
 872
 873       bcopy (pathname, directory_name, directory_len);
 874       directory_name[directory_len] = '\0';
 875       ++filename;
 876       free_dirname = 1;
 877     }
 878
 879   /* If directory_name contains globbing characters, then we
 880      have to expand the previous levels.  Just recurse. */
 881   if (glob_pattern_p (directory_name))
 882     {
 883       char **directories;
 884       register unsigned int i;
 885
 886       dflags = flags & ~GX_MARKDIRS;
 887       if ((flags & GX_GLOBSTAR) && directory_name[0] == '*' && directory_name[1] == '*' && (directory_name[2] == '/' || directory_name[2] == '\0'))
 888         dflags |= GX_ALLDIRS|GX_ADDCURDIR;
 889
 890       if (directory_name[directory_len - 1] == '/')
 891         directory_name[directory_len - 1] = '\0';
 892
 893       directories = glob_filename (directory_name, dflags);
 894
 895       if (free_dirname)
 896         {
 897           free (directory_name);
 898           directory_name = NULL;
 899         }
 900
 901       if (directories == NULL)
 902         goto memory_error;
 903       else if (directories == (char **)&glob_error_return)
 904         {
 905           free ((char *) result);
 906           return ((char **) &glob_error_return);
 907         }
 908       else if (*directories == NULL)
 909         {
 910           free ((char *) directories);
 911           free ((char *) result);
 912           return ((char **) &glob_error_return);
 913         }
 914
 915       /* We have successfully globbed the preceding directory name.
 916          For each name in DIRECTORIES, call glob_vector on it and
 917          FILENAME.  Concatenate the results together.  */
 918       for (i = 0; directories[i] != NULL; ++i)
 919         {
 920           char **temp_results;
 921
 922           /* XXX -- we've recursively scanned any directories resulting from
 923              a `**', so turn off the flag.  We turn it on again below if
 924              filename is `**' */
 925           /* Scan directory even on a NULL filename.  That way, `*h/'
 926              returns only directories ending in `h', instead of all
 927              files ending in `h' with a `/' appended. */
 928           dname = directories[i];
 929           dflags = flags & ~(GX_MARKDIRS|GX_ALLDIRS|GX_ADDCURDIR);
 930           if ((flags & GX_GLOBSTAR) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
 931             dflags |= GX_ALLDIRS|GX_ADDCURDIR;
 932           if (dname[0] == '\0' && filename[0])
 933             {
 934               dflags |= GX_NULLDIR;
 935               dname = ".";      /* treat null directory name and non-null filename as current directory */
 936             }
 937           temp_results = glob_vector (filename, dname, dflags);
 938
 939           /* Handle error cases. */
 940           if (temp_results == NULL)
 941             goto memory_error;
 942           else if (temp_results == (char **)&glob_error_return)
 943             /* This filename is probably not a directory.  Ignore it.  */
 944             ;
 945           else
 946             {
 947               char **array;
 948               register unsigned int l;
 949
 950               /* If we're expanding **, we don't need to glue the directory
 951                  name to the results; we've already done it in glob_vector */
 952               if ((dflags & GX_ALLDIRS) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
 953                 array = temp_results;
 954               else
 955                 array = glob_dir_to_array (directories[i], temp_results, flags);
 956               l = 0;
 957               while (array[l] != NULL)
 958                 ++l;
 959
 960               result =
 961                 (char **)realloc (result, (result_size + l) * sizeof (char *));
 962
 963               if (result == NULL)
 964                 goto memory_error;
 965
 966               for (l = 0; array[l] != NULL; ++l)
 967                 result[result_size++ - 1] = array[l];
 968
 969               result[result_size - 1] = NULL;
 970
 971               /* Note that the elements of ARRAY are not freed.  */
 972               if (array != temp_results)
 973                 free ((char *) array);
 974             }
 975         }
 976       /* Free the directories.  */
 977       for (i = 0; directories[i]; i++)
 978         free (directories[i]);
 979
 980       free ((char *) directories);
 981
 982       return (result);
 983     }
 984
 985   /* If there is only a directory name, return it. */
 986   if (*filename == '\0')
 987     {
 988       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 989       if (result == NULL)
 990         return (NULL);
 991       /* Handle GX_MARKDIRS here. */
 992       result[0] = (char *) malloc (directory_len + 1);
 993       if (result[0] == NULL)
 994         goto memory_error;
 995       bcopy (directory_name, result[0], directory_len + 1);
 996       if (free_dirname)
 997         free (directory_name);
 998       result[1] = NULL;
 999       return (result);
1000     }
1001   else
1002     {
1003       char **temp_results;
1004
1005       /* There are no unquoted globbing characters in DIRECTORY_NAME.
1006          Dequote it before we try to open the directory since there may
1007          be quoted globbing characters which should be treated verbatim. */
1008       if (directory_len > 0)
1009         dequote_pathname (directory_name);
1010
1011       /* We allocated a small array called RESULT, which we won't be using.
1012          Free that memory now. */
1013       free (result);
1014
1015       /* Just return what glob_vector () returns appended to the
1016          directory name. */
1017       /* If flags & GX_ALLDIRS, we're called recursively */
1018       dflags = flags & ~GX_MARKDIRS;
1019       if (directory_len == 0)
1020         dflags |= GX_NULLDIR;
1021       if ((flags & GX_GLOBSTAR) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
1022         {
1023           dflags |= GX_ALLDIRS|GX_ADDCURDIR;
1024 #if 0
1025           /* If we want all directories (dflags & GX_ALLDIRS) and we're not
1026              being called recursively as something like `echo **/*.o'
1027              ((flags & GX_ALLDIRS) == 0), we want to prevent glob_vector from
1028              adding a null directory name to the front of the temp_results
1029              array.  We turn off ADDCURDIR if not called recursively and
1030              dlen == 0 */
1031 #endif
1032           if (directory_len == 0 && (flags & GX_ALLDIRS) == 0)
1033             dflags &= ~GX_ADDCURDIR;
1034         }
1035       temp_results = glob_vector (filename,
1036                                   (directory_len == 0 ? "." : directory_name),
1037                                   dflags);
1038
1039       if (temp_results == NULL || temp_results == (char **)&glob_error_return)
1040         {
1041           if (free_dirname)
1042             free (directory_name);
1043           return (temp_results);
1044         }
1045
1046       result = glob_dir_to_array ((dflags & GX_ALLDIRS) ? "" : directory_name, temp_results, flags);
1047       if (free_dirname)
1048         free (directory_name);
1049       return (result);
1050     }
1051
1052   /* We get to memory_error if the program has run out of memory, or
1053      if this is the shell, and we have been interrupted. */
1054  memory_error:
1055   if (result != NULL)
1056     {
1057       register unsigned int i;
1058       for (i = 0; result[i] != NULL; ++i)
1059         free (result[i]);
1060       free ((char *) result);
1061     }
1062
1063   if (free_dirname && directory_name)
1064     free (directory_name);
1065
1066   QUIT;
1067
1068   return (NULL);
1069 }
1070
1071 #if defined (TEST)
1072
1073 main (argc, argv)
1074      int argc;
1075      char **argv;
1076 {
1077   unsigned int i;
1078
1079   for (i = 1; i < argc; ++i)
1080     {
1081       char **value = glob_filename (argv[i], 0);
1082       if (value == NULL)
1083         puts ("Out of memory.");
1084       else if (value == &glob_error_return)
1085         perror (argv[i]);
1086       else
1087         for (i = 0; value[i] != NULL; i++)
1088           puts (value[i]);
1089     }
1090
1091   exit (0);
1092 }
1093 #endif  /* TEST.  */