src/dir.c

   1 /* Directory hashing for GNU Make.
   2 Copyright (C) 1988-2020 Free Software Foundation, Inc.
   3 This file is part of GNU Make.
   4
   5 GNU Make is free software; you can redistribute it and/or modify it under the
   6 terms of the GNU General Public License as published by the Free Software
   7 Foundation; either version 3 of the License, or (at your option) any later
   8 version.
   9
  10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
  11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  12 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License along with
  15 this program.  If not, see <http://www.gnu.org/licenses/>.  */
  16
  17 #include "makeint.h"
  18 #include "hash.h"
  19 #include "filedef.h"
  20 #include "dep.h"
  21
  22 #ifdef  HAVE_DIRENT_H
  23 # include <dirent.h>
  24 # define NAMLEN(dirent) strlen((dirent)->d_name)
  25 # ifdef VMS
  26 /* its prototype is in vmsdir.h, which is not needed for HAVE_DIRENT_H */
  27 const char *vmsify (const char *name, int type);
  28 # endif
  29 #else
  30 # define dirent direct
  31 # define NAMLEN(dirent) (dirent)->d_namlen
  32 # ifdef HAVE_SYS_NDIR_H
  33 #  include <sys/ndir.h>
  34 # endif
  35 # ifdef HAVE_SYS_DIR_H
  36 #  include <sys/dir.h>
  37 # endif
  38 # ifdef HAVE_NDIR_H
  39 #  include <ndir.h>
  40 # endif
  41 # ifdef HAVE_VMSDIR_H
  42 #  include "vmsdir.h"
  43 # endif /* HAVE_VMSDIR_H */
  44 #endif
  45
  46 /* In GNU systems, <dirent.h> defines this macro for us.  */
  47 #ifdef _D_NAMLEN
  48 # undef NAMLEN
  49 # define NAMLEN(d) _D_NAMLEN(d)
  50 #endif
  51
  52 #if (defined (POSIX) || defined (VMS) || defined (WINDOWS32)) && !defined (__GNU_LIBRARY__)
  53 /* Posix does not require that the d_ino field be present, and some
  54    systems do not provide it. */
  55 # define REAL_DIR_ENTRY(dp) 1
  56 # define FAKE_DIR_ENTRY(dp)
  57 #else
  58 # define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  59 # define FAKE_DIR_ENTRY(dp) (dp->d_ino = 1)
  60 #endif /* POSIX */
  61 \f
  62 #ifdef __MSDOS__
  63 #include <ctype.h>
  64 #include <fcntl.h>
  65
  66 /* If it's MSDOS that doesn't have _USE_LFN, disable LFN support.  */
  67 #ifndef _USE_LFN
  68 #define _USE_LFN 0
  69 #endif
  70
  71 static const char *
  72 dosify (const char *filename)
  73 {
  74   static char dos_filename[14];
  75   char *df;
  76   int i;
  77
  78   if (filename == 0 || _USE_LFN)
  79     return filename;
  80
  81   /* FIXME: what about filenames which violate
  82      8+3 constraints, like "config.h.in", or ".emacs"?  */
  83   if (strpbrk (filename, "\"*+,;<=>?[\\]|") != 0)
  84     return filename;
  85
  86   df = dos_filename;
  87
  88   /* First, transform the name part.  */
  89   for (i = 0; i < 8 && ! STOP_SET (*filename, MAP_DOT|MAP_NUL); ++i)
  90     *df++ = tolower ((unsigned char)*filename++);
  91
  92   /* Now skip to the next dot.  */
  93   while (! STOP_SET (*filename, MAP_DOT|MAP_NUL))
  94     ++filename;
  95   if (*filename != '\0')
  96     {
  97       *df++ = *filename++;
  98       for (i = 0; i < 3 && ! STOP_SET (*filename, MAP_DOT|MAP_NUL); ++i)
  99         *df++ = tolower ((unsigned char)*filename++);
 100     }
 101
 102   /* Look for more dots.  */
 103   while (! STOP_SET (*filename, MAP_DOT|MAP_NUL))
 104     ++filename;
 105   if (*filename == '.')
 106     return filename;
 107   *df = 0;
 108   return dos_filename;
 109 }
 110 #endif /* __MSDOS__ */
 111
 112 #ifdef WINDOWS32
 113 #include "pathstuff.h"
 114 #endif
 115
 116 #ifdef _AMIGA
 117 #include <ctype.h>
 118 #endif
 119
 120 #ifdef HAVE_CASE_INSENSITIVE_FS
 121 static const char *
 122 downcase (const char *filename)
 123 {
 124   static PATH_VAR (new_filename);
 125   char *df;
 126
 127   if (filename == 0)
 128     return 0;
 129
 130   df = new_filename;
 131   while (*filename != '\0')
 132     {
 133       *df++ = tolower ((unsigned char)*filename);
 134       ++filename;
 135     }
 136
 137   *df = 0;
 138
 139   return new_filename;
 140 }
 141 #endif /* HAVE_CASE_INSENSITIVE_FS */
 142
 143 #ifdef VMS
 144
 145 static char *
 146 downcase_inplace(char *filename)
 147 {
 148   char *name;
 149   name = filename;
 150   while (*name != '\0')
 151     {
 152       *name = tolower ((unsigned char)*name);
 153       ++name;
 154     }
 155   return filename;
 156 }
 157
 158 #ifndef _USE_STD_STAT
 159 /* VMS 8.2 fixed the VMS stat output to have unique st_dev and st_ino
 160    when _USE_STD_STAT is used on the compile line.
 161
 162    Prior to _USE_STD_STAT support, the st_dev is a pointer to thread
 163    static memory containing the device of the last filename looked up.
 164
 165    Todo: find out if the ino_t still needs to be faked on a directory.
 166  */
 167
 168 /* Define this if the older VMS_INO_T is needed */
 169 #define VMS_INO_T 1
 170
 171 static int
 172 vms_hash (const char *name)
 173 {
 174   int h = 0;
 175
 176   while (*name)
 177     {
 178       unsigned char uc = *name;
 179       int g;
 180 #ifdef HAVE_CASE_INSENSITIVE_FS
 181       h = (h << 4) + (isupper (uc) ? tolower (uc) : uc);
 182 #else
 183       h = (h << 4) + uc;
 184 #endif
 185       name++;
 186       g = h & 0xf0000000;
 187       if (g)
 188         {
 189           h = h ^ (g >> 24);
 190           h = h ^ g;
 191         }
 192     }
 193   return h;
 194 }
 195
 196 /* fake stat entry for a directory */
 197 static int
 198 vmsstat_dir (const char *name, struct stat *st)
 199 {
 200   char *s;
 201   int h;
 202   DIR *dir;
 203
 204   dir = opendir (name);
 205   if (dir == 0)
 206     return -1;
 207   closedir (dir);
 208   s = strchr (name, ':');       /* find device */
 209   if (s)
 210     {
 211       /* to keep the compiler happy we said "const char *name", now we cheat */
 212       *s++ = 0;
 213       st->st_dev = (char *)vms_hash (name);
 214       h = vms_hash (s);
 215       *(s-1) = ':';
 216     }
 217   else
 218     {
 219       st->st_dev = 0;
 220       h = vms_hash (name);
 221     }
 222
 223   st->st_ino[0] = h & 0xff;
 224   st->st_ino[1] = h & 0xff00;
 225   st->st_ino[2] = h >> 16;
 226
 227   return 0;
 228 }
 229
 230 # define stat(__path, __sbuf) vmsstat_dir (__path, __sbuf)
 231
 232 #endif /* _USE_STD_STAT */
 233 #endif /* VMS */
 234 \f
 235 /* Hash table of directories.  */
 236
 237 #ifndef DIRECTORY_BUCKETS
 238 #define DIRECTORY_BUCKETS 199
 239 #endif
 240
 241 struct directory_contents
 242   {
 243     dev_t dev;                  /* Device and inode numbers of this dir.  */
 244 #ifdef WINDOWS32
 245     /* Inode means nothing on WINDOWS32. Even file key information is
 246      * unreliable because it is random per file open and undefined for remote
 247      * filesystems. The most unique attribute I can come up with is the fully
 248      * qualified name of the directory. Beware though, this is also
 249      * unreliable. I'm open to suggestion on a better way to emulate inode.  */
 250     char *path_key;
 251     time_t ctime;
 252     time_t mtime;        /* controls check for stale directory cache */
 253     int fs_flags;     /* FS_FAT, FS_NTFS, ... */
 254 # define FS_FAT      0x1
 255 # define FS_NTFS     0x2
 256 # define FS_UNKNOWN  0x4
 257 #else
 258 # ifdef VMS_INO_T
 259     ino_t ino[3];
 260 # else
 261     ino_t ino;
 262 # endif
 263 #endif /* WINDOWS32 */
 264     struct hash_table dirfiles; /* Files in this directory.  */
 265     DIR *dirstream;             /* Stream reading this directory.  */
 266   };
 267
 268 static unsigned long
 269 directory_contents_hash_1 (const void *key_0)
 270 {
 271   const struct directory_contents *key = key_0;
 272   unsigned long hash;
 273
 274 #ifdef WINDOWS32
 275   hash = 0;
 276   ISTRING_HASH_1 (key->path_key, hash);
 277   hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) key->ctime;
 278 #else
 279 # ifdef VMS_INO_T
 280   hash = (((unsigned int) key->dev << 4)
 281           ^ ((unsigned int) key->ino[0]
 282              + (unsigned int) key->ino[1]
 283              + (unsigned int) key->ino[2]));
 284 # else
 285   hash = ((unsigned int) key->dev << 4) ^ (unsigned int) key->ino;
 286 # endif
 287 #endif /* WINDOWS32 */
 288   return hash;
 289 }
 290
 291 static unsigned long
 292 directory_contents_hash_2 (const void *key_0)
 293 {
 294   const struct directory_contents *key = key_0;
 295   unsigned long hash;
 296
 297 #ifdef WINDOWS32
 298   hash = 0;
 299   ISTRING_HASH_2 (key->path_key, hash);
 300   hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ctime;
 301 #else
 302 # ifdef VMS_INO_T
 303   hash = (((unsigned int) key->dev << 4)
 304           ^ ~((unsigned int) key->ino[0]
 305               + (unsigned int) key->ino[1]
 306               + (unsigned int) key->ino[2]));
 307 # else
 308   hash = ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ino;
 309 # endif
 310 #endif /* WINDOWS32 */
 311
 312   return hash;
 313 }
 314
 315 /* Sometimes it's OK to use subtraction to get this value:
 316      result = X - Y;
 317    But, if we're not sure of the type of X and Y they may be too large for an
 318    int (on a 64-bit system for example).  So, use ?: instead.
 319    See Savannah bug #15534.
 320
 321    NOTE!  This macro has side-effects!
 322 */
 323
 324 #define MAKECMP(_x,_y)  ((_x)<(_y)?-1:((_x)==(_y)?0:1))
 325
 326 static int
 327 directory_contents_hash_cmp (const void *xv, const void *yv)
 328 {
 329   const struct directory_contents *x = xv;
 330   const struct directory_contents *y = yv;
 331   int result;
 332
 333 #ifdef WINDOWS32
 334   ISTRING_COMPARE (x->path_key, y->path_key, result);
 335   if (result)
 336     return result;
 337   result = MAKECMP(x->ctime, y->ctime);
 338   if (result)
 339     return result;
 340 #else
 341 # ifdef VMS_INO_T
 342   result = MAKECMP(x->ino[0], y->ino[0]);
 343   if (result)
 344     return result;
 345   result = MAKECMP(x->ino[1], y->ino[1]);
 346   if (result)
 347     return result;
 348   result = MAKECMP(x->ino[2], y->ino[2]);
 349   if (result)
 350     return result;
 351 # else
 352   result = MAKECMP(x->ino, y->ino);
 353   if (result)
 354     return result;
 355 # endif
 356 #endif /* WINDOWS32 */
 357
 358   return MAKECMP(x->dev, y->dev);
 359 }
 360
 361 /* Table of directory contents hashed by device and inode number.  */
 362 static struct hash_table directory_contents;
 363
 364 struct directory
 365   {
 366     const char *name;                   /* Name of the directory.  */
 367
 368     /* The directory's contents.  This data may be shared by several
 369        entries in the hash table, which refer to the same directory
 370        (identified uniquely by 'dev' and 'ino') under different names.  */
 371     struct directory_contents *contents;
 372   };
 373
 374 static unsigned long
 375 directory_hash_1 (const void *key)
 376 {
 377   return_ISTRING_HASH_1 (((const struct directory *) key)->name);
 378 }
 379
 380 static unsigned long
 381 directory_hash_2 (const void *key)
 382 {
 383   return_ISTRING_HASH_2 (((const struct directory *) key)->name);
 384 }
 385
 386 static int
 387 directory_hash_cmp (const void *x, const void *y)
 388 {
 389   return_ISTRING_COMPARE (((const struct directory *) x)->name,
 390                           ((const struct directory *) y)->name);
 391 }
 392
 393 /* Table of directories hashed by name.  */
 394 static struct hash_table directories;
 395
 396 /* Never have more than this many directories open at once.  */
 397
 398 #define MAX_OPEN_DIRECTORIES 10
 399
 400 static unsigned int open_directories = 0;
 401
 402
 403 /* Hash table of files in each directory.  */
 404
 405 struct dirfile
 406   {
 407     const char *name;           /* Name of the file.  */
 408     size_t length;
 409     short impossible;           /* This file is impossible.  */
 410     unsigned char type;
 411   };
 412
 413 static unsigned long
 414 dirfile_hash_1 (const void *key)
 415 {
 416   return_ISTRING_HASH_1 (((struct dirfile const *) key)->name);
 417 }
 418
 419 static unsigned long
 420 dirfile_hash_2 (const void *key)
 421 {
 422   return_ISTRING_HASH_2 (((struct dirfile const *) key)->name);
 423 }
 424
 425 static int
 426 dirfile_hash_cmp (const void *xv, const void *yv)
 427 {
 428   const struct dirfile *x = xv;
 429   const struct dirfile *y = yv;
 430   int result = (int) (x->length - y->length);
 431   if (result)
 432     return result;
 433   return_ISTRING_COMPARE (x->name, y->name);
 434 }
 435
 436 #ifndef DIRFILE_BUCKETS
 437 #define DIRFILE_BUCKETS 107
 438 #endif
 439 \f
 440 static int dir_contents_file_exists_p (struct directory_contents *dir,
 441                                        const char *filename);
 442 static struct directory *find_directory (const char *name);
 443
 444 /* Find the directory named NAME and return its 'struct directory'.  */
 445
 446 static struct directory *
 447 find_directory (const char *name)
 448 {
 449   struct directory *dir;
 450   struct directory **dir_slot;
 451   struct directory dir_key;
 452
 453   dir_key.name = name;
 454   dir_slot = (struct directory **) hash_find_slot (&directories, &dir_key);
 455   dir = *dir_slot;
 456
 457   if (HASH_VACANT (dir))
 458     {
 459       /* The directory was not found.  Create a new entry for it.  */
 460       const char *p = name + strlen (name);
 461       struct stat st;
 462       int r;
 463
 464       dir = xmalloc (sizeof (struct directory));
 465 #if defined(HAVE_CASE_INSENSITIVE_FS) && defined(VMS)
 466       /* Todo: Why is this only needed on VMS? */
 467       {
 468         char *lname = downcase_inplace (xstrdup (name));
 469         dir->name = strcache_add_len (lname, p - name);
 470         free (lname);
 471       }
 472 #else
 473       dir->name = strcache_add_len (name, p - name);
 474 #endif
 475       hash_insert_at (&directories, dir, dir_slot);
 476       /* The directory is not in the name hash table.
 477          Find its device and inode numbers, and look it up by them.  */
 478
 479 #if defined(WINDOWS32)
 480       {
 481         char tem[MAXPATHLEN], *tstart, *tend;
 482
 483         /* Remove any trailing slashes.  Windows32 stat fails even on
 484            valid directories if they end in a slash. */
 485         memcpy (tem, name, p - name + 1);
 486         tstart = tem;
 487         if (tstart[1] == ':')
 488           tstart += 2;
 489         for (tend = tem + (p - name - 1);
 490              tend > tstart && (*tend == '/' || *tend == '\\');
 491              tend--)
 492           *tend = '\0';
 493
 494         r = stat (tem, &st);
 495       }
 496 #else
 497       EINTRLOOP (r, stat (name, &st));
 498 #endif
 499
 500       if (r < 0)
 501         {
 502         /* Couldn't stat the directory.  Mark this by
 503            setting the 'contents' member to a nil pointer.  */
 504           dir->contents = 0;
 505         }
 506       else
 507         {
 508           /* Search the contents hash table; device and inode are the key.  */
 509
 510 #ifdef WINDOWS32
 511           char *w32_path;
 512 #endif
 513           struct directory_contents *dc;
 514           struct directory_contents **dc_slot;
 515           struct directory_contents dc_key;
 516
 517           dc_key.dev = st.st_dev;
 518 #ifdef WINDOWS32
 519           dc_key.path_key = w32_path = w32ify (name, 1);
 520           dc_key.ctime = st.st_ctime;
 521 #else
 522 # ifdef VMS_INO_T
 523           dc_key.ino[0] = st.st_ino[0];
 524           dc_key.ino[1] = st.st_ino[1];
 525           dc_key.ino[2] = st.st_ino[2];
 526 # else
 527           dc_key.ino = st.st_ino;
 528 # endif
 529 #endif
 530           dc_slot = (struct directory_contents **) hash_find_slot (&directory_contents, &dc_key);
 531           dc = *dc_slot;
 532
 533           if (HASH_VACANT (dc))
 534             {
 535               /* Nope; this really is a directory we haven't seen before.  */
 536 #ifdef WINDOWS32
 537               char  fs_label[BUFSIZ];
 538               char  fs_type[BUFSIZ];
 539               unsigned long  fs_serno;
 540               unsigned long  fs_flags;
 541               unsigned long  fs_len;
 542 #endif
 543               dc = (struct directory_contents *)
 544                 xmalloc (sizeof (struct directory_contents));
 545
 546               /* Enter it in the contents hash table.  */
 547               dc->dev = st.st_dev;
 548 #ifdef WINDOWS32
 549               dc->path_key = xstrdup (w32_path);
 550               dc->ctime = st.st_ctime;
 551               dc->mtime = st.st_mtime;
 552
 553               /* NTFS is the only WINDOWS32 filesystem that bumps mtime on a
 554                  directory when files are added/deleted from a directory.  */
 555               w32_path[3] = '\0';
 556               if (GetVolumeInformation (w32_path, fs_label, sizeof (fs_label),
 557                                         &fs_serno, &fs_len, &fs_flags, fs_type,
 558                                         sizeof (fs_type)) == FALSE)
 559                 dc->fs_flags = FS_UNKNOWN;
 560               else if (!strcmp (fs_type, "FAT"))
 561                 dc->fs_flags = FS_FAT;
 562               else if (!strcmp (fs_type, "NTFS"))
 563                 dc->fs_flags = FS_NTFS;
 564               else
 565                 dc->fs_flags = FS_UNKNOWN;
 566 #else
 567 # ifdef VMS_INO_T
 568               dc->ino[0] = st.st_ino[0];
 569               dc->ino[1] = st.st_ino[1];
 570               dc->ino[2] = st.st_ino[2];
 571 # else
 572               dc->ino = st.st_ino;
 573 # endif
 574 #endif /* WINDOWS32 */
 575               hash_insert_at (&directory_contents, dc, dc_slot);
 576               ENULLLOOP (dc->dirstream, opendir (name));
 577               if (dc->dirstream == 0)
 578                 /* Couldn't open the directory.  Mark this by setting the
 579                    'files' member to a nil pointer.  */
 580                 dc->dirfiles.ht_vec = 0;
 581               else
 582                 {
 583                   hash_init (&dc->dirfiles, DIRFILE_BUCKETS,
 584                              dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
 585                   /* Keep track of how many directories are open.  */
 586                   ++open_directories;
 587                   if (open_directories == MAX_OPEN_DIRECTORIES)
 588                     /* We have too many directories open already.
 589                        Read the entire directory and then close it.  */
 590                     dir_contents_file_exists_p (dc, 0);
 591                 }
 592             }
 593
 594           /* Point the name-hashed entry for DIR at its contents data.  */
 595           dir->contents = dc;
 596         }
 597     }
 598
 599   return dir;
 600 }
 601 \f
 602 /* Return 1 if the name FILENAME is entered in DIR's hash table.
 603    FILENAME must contain no slashes.  */
 604
 605 static int
 606 dir_contents_file_exists_p (struct directory_contents *dir,
 607                             const char *filename)
 608 {
 609   struct dirfile *df;
 610   struct dirent *d;
 611 #ifdef WINDOWS32
 612   struct stat st;
 613   int rehash = 0;
 614 #endif
 615
 616   if (dir == 0 || dir->dirfiles.ht_vec == 0)
 617     /* The directory could not be stat'd or opened.  */
 618     return 0;
 619
 620 #ifdef __MSDOS__
 621   filename = dosify (filename);
 622 #endif
 623
 624 #ifdef HAVE_CASE_INSENSITIVE_FS
 625   filename = downcase (filename);
 626 #endif
 627
 628 #ifdef __EMX__
 629   if (filename != 0)
 630     _fnlwr (filename); /* lower case for FAT drives */
 631 #endif
 632   if (filename != 0)
 633     {
 634       struct dirfile dirfile_key;
 635
 636       if (*filename == '\0')
 637         {
 638           /* Checking if the directory exists.  */
 639           return 1;
 640         }
 641       dirfile_key.name = filename;
 642       dirfile_key.length = strlen (filename);
 643       df = hash_find_item (&dir->dirfiles, &dirfile_key);
 644       if (df)
 645         return !df->impossible;
 646     }
 647
 648   /* The file was not found in the hashed list.
 649      Try to read the directory further.  */
 650
 651   if (dir->dirstream == 0)
 652     {
 653 #ifdef WINDOWS32
 654       /*
 655        * Check to see if directory has changed since last read. FAT
 656        * filesystems force a rehash always as mtime does not change
 657        * on directories (ugh!).
 658        */
 659       if (dir->path_key)
 660         {
 661           if ((dir->fs_flags & FS_FAT) != 0)
 662             {
 663               dir->mtime = time ((time_t *) 0);
 664               rehash = 1;
 665             }
 666           else if (stat (dir->path_key, &st) == 0 && st.st_mtime > dir->mtime)
 667             {
 668               /* reset date stamp to show most recent re-process.  */
 669               dir->mtime = st.st_mtime;
 670               rehash = 1;
 671             }
 672
 673           /* If it has been already read in, all done.  */
 674           if (!rehash)
 675             return 0;
 676
 677           /* make sure directory can still be opened; if not return.  */
 678           dir->dirstream = opendir (dir->path_key);
 679           if (!dir->dirstream)
 680             return 0;
 681         }
 682       else
 683 #endif
 684         /* The directory has been all read in.  */
 685         return 0;
 686     }
 687
 688   while (1)
 689     {
 690       /* Enter the file in the hash table.  */
 691       size_t len;
 692       struct dirfile dirfile_key;
 693       struct dirfile **dirfile_slot;
 694
 695       ENULLLOOP (d, readdir (dir->dirstream));
 696       if (d == 0)
 697         {
 698           if (errno)
 699             pfatal_with_name ("INTERNAL: readdir");
 700           break;
 701         }
 702
 703 #if defined(VMS) && defined(HAVE_DIRENT_H)
 704       /* In VMS we get file versions too, which have to be stripped off.
 705          Some versions of VMS return versions on Unix files even when
 706          the feature option to strip them is set.  */
 707       {
 708         char *p = strrchr (d->d_name, ';');
 709         if (p)
 710           *p = '\0';
 711       }
 712 #endif
 713       if (!REAL_DIR_ENTRY (d))
 714         continue;
 715
 716       len = NAMLEN (d);
 717       dirfile_key.name = d->d_name;
 718       dirfile_key.length = len;
 719       dirfile_slot = (struct dirfile **) hash_find_slot (&dir->dirfiles, &dirfile_key);
 720 #ifdef WINDOWS32
 721       /*
 722        * If re-reading a directory, don't cache files that have
 723        * already been discovered.
 724        */
 725       if (! rehash || HASH_VACANT (*dirfile_slot))
 726 #endif
 727         {
 728           df = xmalloc (sizeof (struct dirfile));
 729 #if defined(HAVE_CASE_INSENSITIVE_FS) && defined(VMS)
 730           /* TODO: Why is this only needed on VMS? */
 731           df->name = strcache_add_len (downcase_inplace (d->d_name), len);
 732 #else
 733           df->name = strcache_add_len (d->d_name, len);
 734 #endif
 735 #ifdef HAVE_STRUCT_DIRENT_D_TYPE
 736           df->type = d->d_type;
 737 #endif
 738           df->length = len;
 739           df->impossible = 0;
 740           hash_insert_at (&dir->dirfiles, df, dirfile_slot);
 741         }
 742       /* Check if the name matches the one we're searching for.  */
 743       if (filename != 0 && patheq (d->d_name, filename))
 744         return 1;
 745     }
 746
 747   /* If the directory has been completely read in,
 748      close the stream and reset the pointer to nil.  */
 749   if (d == 0)
 750     {
 751       --open_directories;
 752       closedir (dir->dirstream);
 753       dir->dirstream = 0;
 754     }
 755   return 0;
 756 }
 757
 758 /* Return 1 if the name FILENAME in directory DIRNAME
 759    is entered in the dir hash table.
 760    FILENAME must contain no slashes.  */
 761
 762 int
 763 dir_file_exists_p (const char *dirname, const char *filename)
 764 {
 765 #ifdef VMS
 766   if ((filename != NULL) && (dirname != NULL))
 767     {
 768       int want_vmsify;
 769       want_vmsify = (strpbrk (dirname, ":<[") != NULL);
 770       if (want_vmsify)
 771         filename = vmsify (filename, 0);
 772     }
 773 #endif
 774   return dir_contents_file_exists_p (find_directory (dirname)->contents,
 775                                      filename);
 776 }
 777 \f
 778 /* Return 1 if the file named NAME exists.  */
 779
 780 int
 781 file_exists_p (const char *name)
 782 {
 783   const char *dirend;
 784   const char *dirname;
 785   const char *slash;
 786
 787 #ifndef NO_ARCHIVES
 788   if (ar_name (name))
 789     return ar_member_date (name) != (time_t) -1;
 790 #endif
 791
 792   dirend = strrchr (name, '/');
 793 #ifdef VMS
 794   if (dirend == 0)
 795     {
 796       dirend = strrchr (name, ']');
 797       dirend == NULL ? dirend : dirend++;
 798     }
 799   if (dirend == 0)
 800     {
 801       dirend = strrchr (name, '>');
 802       dirend == NULL ? dirend : dirend++;
 803     }
 804   if (dirend == 0)
 805     {
 806       dirend = strrchr (name, ':');
 807       dirend == NULL ? dirend : dirend++;
 808     }
 809 #endif /* VMS */
 810 #ifdef HAVE_DOS_PATHS
 811   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
 812   {
 813     const char *bslash = strrchr (name, '\\');
 814     if (!dirend || bslash > dirend)
 815       dirend = bslash;
 816     /* The case of "d:file".  */
 817     if (!dirend && name[0] && name[1] == ':')
 818       dirend = name + 1;
 819   }
 820 #endif /* HAVE_DOS_PATHS */
 821   if (dirend == 0)
 822 #ifndef _AMIGA
 823     return dir_file_exists_p (".", name);
 824 #else /* !AMIGA */
 825     return dir_file_exists_p ("", name);
 826 #endif /* AMIGA */
 827
 828   slash = dirend;
 829   if (dirend == name)
 830     dirname = "/";
 831   else
 832     {
 833       char *p;
 834 #ifdef HAVE_DOS_PATHS
 835   /* d:/ and d: are *very* different...  */
 836       if (dirend < name + 3 && name[1] == ':' &&
 837           (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
 838         dirend++;
 839 #endif
 840       p = alloca (dirend - name + 1);
 841       memcpy (p, name, dirend - name);
 842       p[dirend - name] = '\0';
 843       dirname = p;
 844     }
 845 #ifdef VMS
 846   if (*slash == '/')
 847     slash++;
 848 #else
 849   slash++;
 850 #endif
 851   return dir_file_exists_p (dirname, slash);
 852 }
 853 \f
 854 /* Mark FILENAME as 'impossible' for 'file_impossible_p'.
 855    This means an attempt has been made to search for FILENAME
 856    as an intermediate file, and it has failed.  */
 857
 858 void
 859 file_impossible (const char *filename)
 860 {
 861   const char *dirend;
 862   const char *p = filename;
 863   struct directory *dir;
 864   struct dirfile *new;
 865
 866   dirend = strrchr (p, '/');
 867 #ifdef VMS
 868   if (dirend == NULL)
 869     {
 870       dirend = strrchr (p, ']');
 871       dirend == NULL ? dirend : dirend++;
 872     }
 873   if (dirend == NULL)
 874     {
 875       dirend = strrchr (p, '>');
 876       dirend == NULL ? dirend : dirend++;
 877     }
 878   if (dirend == NULL)
 879     {
 880       dirend = strrchr (p, ':');
 881       dirend == NULL ? dirend : dirend++;
 882     }
 883 #endif
 884 #ifdef HAVE_DOS_PATHS
 885   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
 886   {
 887     const char *bslash = strrchr (p, '\\');
 888     if (!dirend || bslash > dirend)
 889       dirend = bslash;
 890     /* The case of "d:file".  */
 891     if (!dirend && p[0] && p[1] == ':')
 892       dirend = p + 1;
 893   }
 894 #endif /* HAVE_DOS_PATHS */
 895   if (dirend == 0)
 896 #ifdef _AMIGA
 897     dir = find_directory ("");
 898 #else /* !AMIGA */
 899     dir = find_directory (".");
 900 #endif /* AMIGA */
 901   else
 902     {
 903       const char *dirname;
 904       const char *slash = dirend;
 905       if (dirend == p)
 906         dirname = "/";
 907       else
 908         {
 909           char *cp;
 910 #ifdef HAVE_DOS_PATHS
 911           /* d:/ and d: are *very* different...  */
 912           if (dirend < p + 3 && p[1] == ':' &&
 913               (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
 914             dirend++;
 915 #endif
 916           cp = alloca (dirend - p + 1);
 917           memcpy (cp, p, dirend - p);
 918           cp[dirend - p] = '\0';
 919           dirname = cp;
 920         }
 921       dir = find_directory (dirname);
 922 #ifdef VMS
 923       if (*slash == '/')
 924         filename = p = slash + 1;
 925       else
 926         filename = p = slash;
 927 #else
 928       filename = p = slash + 1;
 929 #endif
 930     }
 931
 932   if (dir->contents == 0)
 933     /* The directory could not be stat'd.  We allocate a contents
 934        structure for it, but leave it out of the contents hash table.  */
 935     dir->contents = xcalloc (sizeof (struct directory_contents));
 936
 937   if (dir->contents->dirfiles.ht_vec == 0)
 938     {
 939       hash_init (&dir->contents->dirfiles, DIRFILE_BUCKETS,
 940                  dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
 941     }
 942
 943   /* Make a new entry and put it in the table.  */
 944
 945   new = xmalloc (sizeof (struct dirfile));
 946   new->length = strlen (filename);
 947 #if defined(HAVE_CASE_INSENSITIVE_FS) && defined(VMS)
 948   /* todo: Why is this only needed on VMS? */
 949   new->name = strcache_add_len (downcase (filename), new->length);
 950 #else
 951   new->name = strcache_add_len (filename, new->length);
 952 #endif
 953   new->impossible = 1;
 954   hash_insert (&dir->contents->dirfiles, new);
 955 }
 956 \f
 957 /* Return nonzero if FILENAME has been marked impossible.  */
 958
 959 int
 960 file_impossible_p (const char *filename)
 961 {
 962   const char *dirend;
 963   struct directory_contents *dir;
 964   struct dirfile *dirfile;
 965   struct dirfile dirfile_key;
 966 #ifdef VMS
 967   int want_vmsify = 0;
 968 #endif
 969
 970   dirend = strrchr (filename, '/');
 971 #ifdef VMS
 972   if (dirend == NULL)
 973     {
 974       want_vmsify = (strpbrk (filename, "]>:^") != NULL);
 975       dirend = strrchr (filename, ']');
 976     }
 977   if (dirend == NULL && want_vmsify)
 978     dirend = strrchr (filename, '>');
 979   if (dirend == NULL && want_vmsify)
 980     dirend = strrchr (filename, ':');
 981 #endif
 982 #ifdef HAVE_DOS_PATHS
 983   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
 984   {
 985     const char *bslash = strrchr (filename, '\\');
 986     if (!dirend || bslash > dirend)
 987       dirend = bslash;
 988     /* The case of "d:file".  */
 989     if (!dirend && filename[0] && filename[1] == ':')
 990       dirend = filename + 1;
 991   }
 992 #endif /* HAVE_DOS_PATHS */
 993   if (dirend == 0)
 994 #ifdef _AMIGA
 995     dir = find_directory ("")->contents;
 996 #else /* !AMIGA */
 997     dir = find_directory (".")->contents;
 998 #endif /* AMIGA */
 999   else
1000     {
1001       const char *dirname;
1002       const char *slash = dirend;
1003       if (dirend == filename)
1004         dirname = "/";
1005       else
1006         {
1007           char *cp;
1008 #ifdef HAVE_DOS_PATHS
1009           /* d:/ and d: are *very* different...  */
1010           if (dirend < filename + 3 && filename[1] == ':' &&
1011               (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
1012             dirend++;
1013 #endif
1014           cp = alloca (dirend - filename + 1);
1015           memcpy (cp, filename, dirend - filename);
1016           cp[dirend - filename] = '\0';
1017           dirname = cp;
1018         }
1019       dir = find_directory (dirname)->contents;
1020 #ifdef VMS
1021       if (*slash == '/')
1022         filename = slash + 1;
1023       else
1024         filename = slash;
1025 #else
1026       filename = slash + 1;
1027 #endif
1028     }
1029
1030   if (dir == 0 || dir->dirfiles.ht_vec == 0)
1031     /* There are no files entered for this directory.  */
1032     return 0;
1033
1034 #ifdef __MSDOS__
1035   filename = dosify (filename);
1036 #endif
1037 #ifdef HAVE_CASE_INSENSITIVE_FS
1038   filename = downcase (filename);
1039 #endif
1040 #ifdef VMS
1041   if (want_vmsify)
1042     filename = vmsify (filename, 1);
1043 #endif
1044
1045   dirfile_key.name = filename;
1046   dirfile_key.length = strlen (filename);
1047   dirfile = hash_find_item (&dir->dirfiles, &dirfile_key);
1048   if (dirfile)
1049     return dirfile->impossible;
1050
1051   return 0;
1052 }
1053 \f
1054 /* Return the already allocated name in the
1055    directory hash table that matches DIR.  */
1056
1057 const char *
1058 dir_name (const char *dir)
1059 {
1060   return find_directory (dir)->name;
1061 }
1062 \f
1063 /* Print the data base of directories.  */
1064
1065 void
1066 print_dir_data_base (void)
1067 {
1068   unsigned int files;
1069   unsigned int impossible;
1070   struct directory **dir_slot;
1071   struct directory **dir_end;
1072
1073   puts (_("\n# Directories\n"));
1074
1075   files = impossible = 0;
1076
1077   dir_slot = (struct directory **) directories.ht_vec;
1078   dir_end = dir_slot + directories.ht_size;
1079   for ( ; dir_slot < dir_end; dir_slot++)
1080     {
1081       struct directory *dir = *dir_slot;
1082       if (! HASH_VACANT (dir))
1083         {
1084           if (dir->contents == 0)
1085             printf (_("# %s: could not be stat'd.\n"), dir->name);
1086           else if (dir->contents->dirfiles.ht_vec == 0)
1087             {
1088 #ifdef WINDOWS32
1089               printf (_("# %s (key %s, mtime %I64u): could not be opened.\n"),
1090                       dir->name, dir->contents->path_key,
1091                       (unsigned long long)dir->contents->mtime);
1092 #else  /* WINDOWS32 */
1093 #ifdef VMS_INO_T
1094               printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"),
1095                       dir->name, dir->contents->dev,
1096                       dir->contents->ino[0], dir->contents->ino[1],
1097                       dir->contents->ino[2]);
1098 #else
1099               printf (_("# %s (device %ld, inode %ld): could not be opened.\n"),
1100                       dir->name, (long int) dir->contents->dev,
1101                       (long int) dir->contents->ino);
1102 #endif
1103 #endif /* WINDOWS32 */
1104             }
1105           else
1106             {
1107               unsigned int f = 0;
1108               unsigned int im = 0;
1109               struct dirfile **files_slot;
1110               struct dirfile **files_end;
1111
1112               files_slot = (struct dirfile **) dir->contents->dirfiles.ht_vec;
1113               files_end = files_slot + dir->contents->dirfiles.ht_size;
1114               for ( ; files_slot < files_end; files_slot++)
1115                 {
1116                   struct dirfile *df = *files_slot;
1117                   if (! HASH_VACANT (df))
1118                     {
1119                       if (df->impossible)
1120                         ++im;
1121                       else
1122                         ++f;
1123                     }
1124                 }
1125 #ifdef WINDOWS32
1126               printf (_("# %s (key %s, mtime %I64u): "),
1127                       dir->name, dir->contents->path_key,
1128                       (unsigned long long)dir->contents->mtime);
1129 #else  /* WINDOWS32 */
1130 #ifdef VMS_INO_T
1131               printf (_("# %s (device %d, inode [%d,%d,%d]): "),
1132                       dir->name, dir->contents->dev,
1133                       dir->contents->ino[0], dir->contents->ino[1],
1134                       dir->contents->ino[2]);
1135 #else
1136               printf (_("# %s (device %ld, inode %ld): "),
1137                       dir->name,
1138                       (long)dir->contents->dev, (long)dir->contents->ino);
1139 #endif
1140 #endif /* WINDOWS32 */
1141               if (f == 0)
1142                 fputs (_("No"), stdout);
1143               else
1144                 printf ("%u", f);
1145               fputs (_(" files, "), stdout);
1146               if (im == 0)
1147                 fputs (_("no"), stdout);
1148               else
1149                 printf ("%u", im);
1150               fputs (_(" impossibilities"), stdout);
1151               if (dir->contents->dirstream == 0)
1152                 puts (".");
1153               else
1154                 puts (_(" so far."));
1155               files += f;
1156               impossible += im;
1157             }
1158         }
1159     }
1160
1161   fputs ("\n# ", stdout);
1162   if (files == 0)
1163     fputs (_("No"), stdout);
1164   else
1165     printf ("%u", files);
1166   fputs (_(" files, "), stdout);
1167   if (impossible == 0)
1168     fputs (_("no"), stdout);
1169   else
1170     printf ("%u", impossible);
1171   printf (_(" impossibilities in %lu directories.\n"), directories.ht_fill);
1172 }
1173 \f
1174 /* Hooks for globbing.  */
1175
1176 /* Structure describing state of iterating through a directory hash table.  */
1177
1178 struct dirstream
1179   {
1180     struct directory_contents *contents; /* The directory being read.  */
1181     struct dirfile **dirfile_slot; /* Current slot in table.  */
1182   };
1183
1184 /* Forward declarations.  */
1185 static __ptr_t open_dirstream (const char *);
1186 static struct dirent *read_dirstream (__ptr_t);
1187
1188 static __ptr_t
1189 open_dirstream (const char *directory)
1190 {
1191   struct dirstream *new;
1192   struct directory *dir = find_directory (directory);
1193
1194   if (dir->contents == 0 || dir->contents->dirfiles.ht_vec == 0)
1195     /* DIR->contents is nil if the directory could not be stat'd.
1196        DIR->contents->dirfiles is nil if it could not be opened.  */
1197     return 0;
1198
1199   /* Read all the contents of the directory now.  There is no benefit
1200      in being lazy, since glob will want to see every file anyway.  */
1201
1202   dir_contents_file_exists_p (dir->contents, 0);
1203
1204   new = xmalloc (sizeof (struct dirstream));
1205   new->contents = dir->contents;
1206   new->dirfile_slot = (struct dirfile **) new->contents->dirfiles.ht_vec;
1207
1208   return (__ptr_t) new;
1209 }
1210
1211 static struct dirent *
1212 read_dirstream (__ptr_t stream)
1213 {
1214   static char *buf;
1215   static size_t bufsz;
1216
1217   struct dirstream *const ds = (struct dirstream *) stream;
1218   struct directory_contents *dc = ds->contents;
1219   struct dirfile **dirfile_end = (struct dirfile **) dc->dirfiles.ht_vec + dc->dirfiles.ht_size;
1220
1221   while (ds->dirfile_slot < dirfile_end)
1222     {
1223       struct dirfile *df = *ds->dirfile_slot++;
1224       if (! HASH_VACANT (df) && !df->impossible)
1225         {
1226           /* The glob interface wants a 'struct dirent', so mock one up.  */
1227           struct dirent *d;
1228           size_t len = df->length + 1;
1229           size_t sz = sizeof (*d) - sizeof (d->d_name) + len;
1230           if (sz > bufsz)
1231             {
1232               bufsz *= 2;
1233               if (sz > bufsz)
1234                 bufsz = sz;
1235               buf = xrealloc (buf, bufsz);
1236             }
1237           d = (struct dirent *) buf;
1238 #ifdef __MINGW32__
1239 # if __MINGW32_MAJOR_VERSION < 3 || (__MINGW32_MAJOR_VERSION == 3 && \
1240                                      __MINGW32_MINOR_VERSION == 0)
1241           d->d_name = xmalloc (len);
1242 # endif
1243 #endif
1244           FAKE_DIR_ENTRY (d);
1245 #ifdef _DIRENT_HAVE_D_NAMLEN
1246           d->d_namlen = len - 1;
1247 #endif
1248 #ifdef HAVE_STRUCT_DIRENT_D_TYPE
1249           d->d_type = df->type;
1250 #endif
1251           memcpy (d->d_name, df->name, len);
1252           return d;
1253         }
1254     }
1255
1256   return 0;
1257 }
1258
1259 /* On 64 bit ReliantUNIX (5.44 and above) in LFS mode, stat() is actually a
1260  * macro for stat64().  If stat is a macro, make a local wrapper function to
1261  * invoke it.
1262  *
1263  * On MS-Windows, stat() "succeeds" for foo/bar/. where foo/bar is a
1264  * regular file; fix that here.
1265  */
1266 #if !defined(stat) && !defined(WINDOWS32) || defined(VMS)
1267 # ifndef VMS
1268 #  ifndef HAVE_SYS_STAT_H
1269 int stat (const char *path, struct stat *sbuf);
1270 #  endif
1271 # else
1272     /* We are done with the fake stat.  Go back to the real stat */
1273 #   ifdef stat
1274 #     undef stat
1275 #   endif
1276 # endif
1277 # define local_stat stat
1278 #else
1279 static int
1280 local_stat (const char *path, struct stat *buf)
1281 {
1282   int e;
1283 #ifdef WINDOWS32
1284   size_t plen = strlen (path);
1285
1286   /* Make sure the parent of "." exists and is a directory, not a
1287      file.  This is because 'stat' on Windows normalizes the argument
1288      foo/. => foo without checking first that foo is a directory.  */
1289   if (plen > 1 && path[plen - 1] == '.'
1290       && (path[plen - 2] == '/' || path[plen - 2] == '\\'))
1291     {
1292       char parent[MAXPATHLEN];
1293
1294       strncpy (parent, path, plen - 2);
1295       parent[plen - 2] = '\0';
1296       if (stat (parent, buf) < 0 || !_S_ISDIR (buf->st_mode))
1297         return -1;
1298     }
1299 #endif
1300
1301   EINTRLOOP (e, stat (path, buf));
1302   return e;
1303 }
1304 #endif
1305
1306 /* Similarly for lstat.  */
1307 #if !defined(lstat) && !defined(WINDOWS32) || defined(VMS)
1308 # ifndef VMS
1309 #  ifndef HAVE_SYS_STAT_H
1310 int lstat (const char *path, struct stat *sbuf);
1311 #  endif
1312 # else
1313     /* We are done with the fake lstat.  Go back to the real lstat */
1314 #   ifdef lstat
1315 #     undef lstat
1316 #   endif
1317 # endif
1318 # define local_lstat lstat
1319 #elif defined(WINDOWS32)
1320 /* Windows doesn't support lstat().  */
1321 # define local_lstat local_stat
1322 #else
1323 static int
1324 local_lstat (const char *path, struct stat *buf)
1325 {
1326   int e;
1327   EINTRLOOP (e, lstat (path, buf));
1328   return e;
1329 }
1330 #endif
1331
1332 void
1333 dir_setup_glob (glob_t *gl)
1334 {
1335   gl->gl_offs = 0;
1336   gl->gl_opendir = open_dirstream;
1337   gl->gl_readdir = read_dirstream;
1338   gl->gl_closedir = free;
1339   gl->gl_lstat = local_lstat;
1340   gl->gl_stat = local_stat;
1341 }
1342
1343 void
1344 hash_init_directories (void)
1345 {
1346   hash_init (&directories, DIRECTORY_BUCKETS,
1347              directory_hash_1, directory_hash_2, directory_hash_cmp);
1348   hash_init (&directory_contents, DIRECTORY_BUCKETS,
1349              directory_contents_hash_1, directory_contents_hash_2,
1350              directory_contents_hash_cmp);
1351 }