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