src/dir.c

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