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)
 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_ALLDIRS, add the passed directory also */
 669   if (add_current)
 670     {
 671       sdlen = strlen (dir);
 672       nextname = (char *)malloc (sdlen + 1);
 673       nextlink = (struct globval *) malloc (sizeof (struct globval));
 674       if (nextlink == 0 || nextname == 0)
 675         lose = 1;
 676       else
 677         {
 678           nextlink->name = nextname;
 679           nextlink->next = lastlink;
 680           lastlink = nextlink;
 681           if (flags & GX_NULLDIR)
 682             nextname[0] = '\0';
 683           else
 684             bcopy (dir, nextname, sdlen + 1);
 685           ++count;
 686         }
 687     }
 688
 689   if (lose == 0)
 690     {
 691       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 692       lose |= name_vector == NULL;
 693     }
 694
 695   /* Have we run out of memory?  */
 696   if (lose)
 697     {
 698       tmplink = 0;
 699
 700       /* Here free the strings we have got.  */
 701       while (lastlink)
 702         {
 703           /* Since we build the list in reverse order, the first N entries
 704              will be allocated with malloc, if firstmalloc is set, from
 705              lastlink to firstmalloc. */
 706           if (firstmalloc)
 707             {
 708               if (lastlink == firstmalloc)
 709                 firstmalloc = 0;
 710               tmplink = lastlink;
 711             }
 712           else
 713             tmplink = 0;
 714           free (lastlink->name);
 715           lastlink = lastlink->next;
 716           FREE (tmplink);
 717         }
 718
 719       QUIT;
 720
 721       return ((char **)NULL);
 722     }
 723
 724   /* Copy the name pointers from the linked list into the vector.  */
 725   for (tmplink = lastlink, i = 0; i < count; ++i)
 726     {
 727       name_vector[i] = tmplink->name;
 728       tmplink = tmplink->next;
 729     }
 730
 731   name_vector[count] = NULL;
 732
 733   /* If we allocated some of the struct globvals, free them now. */
 734   if (firstmalloc)
 735     {
 736       tmplink = 0;
 737       while (lastlink)
 738         {
 739           tmplink = lastlink;
 740           if (lastlink == firstmalloc)
 741             lastlink = firstmalloc = 0;
 742           else
 743             lastlink = lastlink->next;
 744           free (tmplink);
 745         }
 746     }
 747
 748   return (name_vector);
 749 }
 750
 751 /* Return a new array which is the concatenation of each string in ARRAY
 752    to DIR.  This function expects you to pass in an allocated ARRAY, and
 753    it takes care of free()ing that array.  Thus, you might think of this
 754    function as side-effecting ARRAY.  This should handle GX_MARKDIRS. */
 755 static char **
 756 glob_dir_to_array (dir, array, flags)
 757      char *dir, **array;
 758      int flags;
 759 {
 760   register unsigned int i, l;
 761   int add_slash;
 762   char **result, *new;
 763   struct stat sb;
 764
 765   l = strlen (dir);
 766   if (l == 0)
 767     {
 768       if (flags & GX_MARKDIRS)
 769         for (i = 0; array[i]; i++)
 770           {
 771             if ((stat (array[i], &sb) == 0) && S_ISDIR (sb.st_mode))
 772               {
 773                 l = strlen (array[i]);
 774                 new = (char *)realloc (array[i], l + 2);
 775                 if (new == 0)
 776                   return NULL;
 777                 new[l] = '/';
 778                 new[l+1] = '\0';
 779                 array[i] = new;
 780               }
 781           }
 782       return (array);
 783     }
 784
 785   add_slash = dir[l - 1] != '/';
 786
 787   i = 0;
 788   while (array[i] != NULL)
 789     ++i;
 790
 791   result = (char **) malloc ((i + 1) * sizeof (char *));
 792   if (result == NULL)
 793     return (NULL);
 794
 795   for (i = 0; array[i] != NULL; i++)
 796     {
 797       /* 3 == 1 for NUL, 1 for slash at end of DIR, 1 for GX_MARKDIRS */
 798       result[i] = (char *) malloc (l + strlen (array[i]) + 3);
 799
 800       if (result[i] == NULL)
 801         return (NULL);
 802
 803       strcpy (result[i], dir);
 804       if (add_slash)
 805         result[i][l] = '/';
 806       strcpy (result[i] + l + add_slash, array[i]);
 807       if (flags & GX_MARKDIRS)
 808         {
 809           if ((stat (result[i], &sb) == 0) && S_ISDIR (sb.st_mode))
 810             {
 811               size_t rlen;
 812               rlen = strlen (result[i]);
 813               result[i][rlen] = '/';
 814               result[i][rlen+1] = '\0';
 815             }
 816         }
 817     }
 818   result[i] = NULL;
 819
 820   /* Free the input array.  */
 821   for (i = 0; array[i] != NULL; i++)
 822     free (array[i]);
 823   free ((char *) array);
 824
 825   return (result);
 826 }
 827
 828 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 829    marking the end of the array with a null-pointer as an element.
 830    If no pathnames match, then the array is empty (first element is null).
 831    If there isn't enough memory, then return NULL.
 832    If a file system error occurs, return -1; `errno' has the error code.  */
 833 char **
 834 glob_filename (pathname, flags)
 835      char *pathname;
 836      int flags;
 837 {
 838   char **result;
 839   unsigned int result_size;
 840   char *directory_name, *filename, *dname;
 841   unsigned int directory_len;
 842   int free_dirname;                     /* flag */
 843   int dflags;
 844
 845   result = (char **) malloc (sizeof (char *));
 846   result_size = 1;
 847   if (result == NULL)
 848     return (NULL);
 849
 850   result[0] = NULL;
 851
 852   directory_name = NULL;
 853
 854   /* Find the filename.  */
 855   filename = strrchr (pathname, '/');
 856   if (filename == NULL)
 857     {
 858       filename = pathname;
 859       directory_name = "";
 860       directory_len = 0;
 861       free_dirname = 0;
 862     }
 863   else
 864     {
 865       directory_len = (filename - pathname) + 1;
 866       directory_name = (char *) malloc (directory_len + 1);
 867
 868       if (directory_name == 0)          /* allocation failed? */
 869         return (NULL);
 870
 871       bcopy (pathname, directory_name, directory_len);
 872       directory_name[directory_len] = '\0';
 873       ++filename;
 874       free_dirname = 1;
 875     }
 876
 877   /* If directory_name contains globbing characters, then we
 878      have to expand the previous levels.  Just recurse. */
 879   if (glob_pattern_p (directory_name))
 880     {
 881       char **directories;
 882       register unsigned int i;
 883
 884       dflags = flags & ~GX_MARKDIRS;
 885       if ((flags & GX_GLOBSTAR) && directory_name[0] == '*' && directory_name[1] == '*' && (directory_name[2] == '/' || directory_name[2] == '\0'))
 886         dflags |= GX_ALLDIRS|GX_ADDCURDIR;
 887
 888       if (directory_name[directory_len - 1] == '/')
 889         directory_name[directory_len - 1] = '\0';
 890
 891       directories = glob_filename (directory_name, dflags);
 892
 893       if (free_dirname)
 894         {
 895           free (directory_name);
 896           directory_name = NULL;
 897         }
 898
 899       if (directories == NULL)
 900         goto memory_error;
 901       else if (directories == (char **)&glob_error_return)
 902         {
 903           free ((char *) result);
 904           return ((char **) &glob_error_return);
 905         }
 906       else if (*directories == NULL)
 907         {
 908           free ((char *) directories);
 909           free ((char *) result);
 910           return ((char **) &glob_error_return);
 911         }
 912
 913       /* We have successfully globbed the preceding directory name.
 914          For each name in DIRECTORIES, call glob_vector on it and
 915          FILENAME.  Concatenate the results together.  */
 916       for (i = 0; directories[i] != NULL; ++i)
 917         {
 918           char **temp_results;
 919
 920           /* Scan directory even on a NULL filename.  That way, `*h/'
 921              returns only directories ending in `h', instead of all
 922              files ending in `h' with a `/' appended. */
 923           dname = directories[i];
 924           dflags = flags & ~GX_MARKDIRS;
 925           if ((flags & GX_GLOBSTAR) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
 926             dflags |= GX_ALLDIRS|GX_ADDCURDIR;
 927           if (dname[0] == '\0' && filename[0])
 928             {
 929               dflags |= GX_NULLDIR;
 930               dname = ".";      /* treat null directory name and non-null filename as current directory */
 931             }
 932           temp_results = glob_vector (filename, dname, dflags);
 933
 934           /* Handle error cases. */
 935           if (temp_results == NULL)
 936             goto memory_error;
 937           else if (temp_results == (char **)&glob_error_return)
 938             /* This filename is probably not a directory.  Ignore it.  */
 939             ;
 940           else
 941             {
 942               char **array;
 943               register unsigned int l;
 944
 945               array = glob_dir_to_array (directories[i], temp_results, flags);
 946               l = 0;
 947               while (array[l] != NULL)
 948                 ++l;
 949
 950               result =
 951                 (char **)realloc (result, (result_size + l) * sizeof (char *));
 952
 953               if (result == NULL)
 954                 goto memory_error;
 955
 956               for (l = 0; array[l] != NULL; ++l)
 957                 result[result_size++ - 1] = array[l];
 958
 959               result[result_size - 1] = NULL;
 960
 961               /* Note that the elements of ARRAY are not freed.  */
 962               free ((char *) array);
 963             }
 964         }
 965       /* Free the directories.  */
 966       for (i = 0; directories[i]; i++)
 967         free (directories[i]);
 968
 969       free ((char *) directories);
 970
 971       return (result);
 972     }
 973
 974   /* If there is only a directory name, return it. */
 975   if (*filename == '\0')
 976     {
 977       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 978       if (result == NULL)
 979         return (NULL);
 980       /* Handle GX_MARKDIRS here. */
 981       result[0] = (char *) malloc (directory_len + 1);
 982       if (result[0] == NULL)
 983         goto memory_error;
 984       bcopy (directory_name, result[0], directory_len + 1);
 985       if (free_dirname)
 986         free (directory_name);
 987       result[1] = NULL;
 988       return (result);
 989     }
 990   else
 991     {
 992       char **temp_results;
 993
 994       /* There are no unquoted globbing characters in DIRECTORY_NAME.
 995          Dequote it before we try to open the directory since there may
 996          be quoted globbing characters which should be treated verbatim. */
 997       if (directory_len > 0)
 998         dequote_pathname (directory_name);
 999
1000       /* We allocated a small array called RESULT, which we won't be using.
1001          Free that memory now. */
1002       free (result);
1003
1004       /* Just return what glob_vector () returns appended to the
1005          directory name. */
1006       dflags = flags & ~GX_MARKDIRS;
1007       if (directory_len == 0)
1008         dflags |= GX_NULLDIR;
1009       if ((flags & GX_GLOBSTAR) && filename[0] == '*' && filename[1] == '*' && filename[2] == '\0')
1010         dflags |= GX_ALLDIRS|GX_ADDCURDIR;
1011       temp_results = glob_vector (filename,
1012                                   (directory_len == 0 ? "." : directory_name),
1013                                   dflags);
1014
1015       if (temp_results == NULL || temp_results == (char **)&glob_error_return)
1016         {
1017           if (free_dirname)
1018             free (directory_name);
1019           return (temp_results);
1020         }
1021
1022       result = glob_dir_to_array ((dflags & GX_ALLDIRS) ? "" : directory_name, temp_results, flags);
1023       if (free_dirname)
1024         free (directory_name);
1025       return (result);
1026     }
1027
1028   /* We get to memory_error if the program has run out of memory, or
1029      if this is the shell, and we have been interrupted. */
1030  memory_error:
1031   if (result != NULL)
1032     {
1033       register unsigned int i;
1034       for (i = 0; result[i] != NULL; ++i)
1035         free (result[i]);
1036       free ((char *) result);
1037     }
1038
1039   if (free_dirname && directory_name)
1040     free (directory_name);
1041
1042   QUIT;
1043
1044   return (NULL);
1045 }
1046
1047 #if defined (TEST)
1048
1049 main (argc, argv)
1050      int argc;
1051      char **argv;
1052 {
1053   unsigned int i;
1054
1055   for (i = 1; i < argc; ++i)
1056     {
1057       char **value = glob_filename (argv[i], 0);
1058       if (value == NULL)
1059         puts ("Out of memory.");
1060       else if (value == &glob_error_return)
1061         perror (argv[i]);
1062       else
1063         for (i = 0; value[i] != NULL; i++)
1064           puts (value[i]);
1065     }
1066
1067   exit (0);
1068 }
1069 #endif  /* TEST.  */