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