src/globbing.c

   1 /*
   2  * globbing.c: interface to the POSIX glob routines
   3  *
   4  * Copyright (C) 1995 Graeme W. Wilford. (Wilf.)
   5  * Copyright (C) 2001, 2002, 2003, 2006, 2007, 2008 Colin Watson.
   6  *
   7  * This file is part of man-db.
   8  *
   9  * man-db is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * man-db is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with man-db; if not, write to the Free Software Foundation,
  21  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  22  *
  23  * Mon Mar 13 20:27:36 GMT 1995  Wilf. (G.Wilford@ee.surrey.ac.uk)
  24  */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #  include "config.h"
  28 #endif /* HAVE_CONFIG_H */
  29
  30 #include <string.h>
  31 #include <stdlib.h>
  32 #include <ctype.h>
  33 #include <glob.h>
  34 #include <sys/types.h>
  35 #include <dirent.h>
  36
  37 #include "fnmatch.h"
  38 #include "regex.h"
  39 #include "xvasprintf.h"
  40
  41 #include "manconfig.h"
  42
  43 #include "error.h"
  44 #include "hashtable.h"
  45 #include "cleanup.h"
  46 #include "xregcomp.h"
  47
  48 #include "globbing.h"
  49
  50 const char *extension;
  51 static const char *mandir_layout = MANDIR_LAYOUT;
  52
  53 static char *make_pattern (const char *name, const char *sec, int opts)
  54 {
  55         char *pattern;
  56
  57         if (opts & LFF_REGEX) {
  58                 if (extension) {
  59                         char *esc_ext = escape_shell (extension);
  60                         pattern = xasprintf ("%s\\..*%s.*", name, esc_ext);
  61                         free (esc_ext);
  62                 } else {
  63                         char *esc_sec = escape_shell (sec);
  64                         pattern = xasprintf ("%s\\.%s.*", name, esc_sec);
  65                         free (esc_sec);
  66                 }
  67         } else {
  68                 if (extension)
  69                         pattern = xasprintf ("%s.*%s*", name, extension);
  70                 else
  71                         pattern = xasprintf ("%s.%s*", name, sec);
  72         }
  73
  74         return pattern;
  75 }
  76
  77 #define LAYOUT_GNU      1
  78 #define LAYOUT_HPUX     2
  79 #define LAYOUT_IRIX     4
  80 #define LAYOUT_SOLARIS  8
  81 #define LAYOUT_BSD      16
  82
  83 static int parse_layout (const char *layout)
  84 {
  85         if (!*layout)
  86                 return LAYOUT_GNU | LAYOUT_HPUX | LAYOUT_IRIX |
  87                        LAYOUT_SOLARIS | LAYOUT_BSD;
  88         else {
  89                 int flags = 0;
  90
  91                 char *upper_layout = xstrdup (layout);
  92                 char *layoutp;
  93                 for (layoutp = upper_layout; *layoutp; layoutp++)
  94                         *layoutp = CTYPE (toupper, *layoutp);
  95
  96                 if (strstr (upper_layout, "GNU"))
  97                         flags |= LAYOUT_GNU;
  98                 if (strstr (upper_layout, "HPUX"))
  99                         flags |= LAYOUT_HPUX;
 100                 if (strstr (upper_layout, "IRIX"))
 101                         flags |= LAYOUT_IRIX;
 102                 if (strstr (upper_layout, "SOLARIS"))
 103                         flags |= LAYOUT_SOLARIS;
 104                 if (strstr (upper_layout, "BSD"))
 105                         flags |= LAYOUT_BSD;
 106
 107                 free (upper_layout);
 108                 return flags;
 109         }
 110 }
 111
 112 struct dirent_hashent {
 113         char **names;
 114         size_t names_len, names_max;
 115 };
 116
 117 static void dirent_hashtable_free (void *defn)
 118 {
 119         struct dirent_hashent *hashent = defn;
 120         size_t i;
 121
 122         for (i = 0; i < hashent->names_len; ++i)
 123                 free (hashent->names[i]);
 124         free (hashent->names);
 125         free (hashent);
 126 }
 127
 128 static struct hashtable *dirent_hash = NULL;
 129
 130 static int cache_compare (const void *a, const void *b)
 131 {
 132         const char *left = *(const char **) a;
 133         const char *right = *(const char **) b;
 134         return strcasecmp (left, right);
 135 }
 136
 137 static struct dirent_hashent *update_directory_cache (const char *path)
 138 {
 139         struct dirent_hashent *cache;
 140         DIR *dir;
 141         struct dirent *entry;
 142
 143         if (!dirent_hash) {
 144                 dirent_hash = hashtable_create (&dirent_hashtable_free);
 145                 push_cleanup ((cleanup_fun) hashtable_free, dirent_hash, 0);
 146         }
 147         cache = hashtable_lookup (dirent_hash, path, strlen (path));
 148
 149         /* Check whether we've got this one already. */
 150         if (cache) {
 151                 debug ("update_directory_cache %s: hit\n", path);
 152                 return cache;
 153         }
 154
 155         debug ("update_directory_cache %s: miss\n", path);
 156
 157         dir = opendir (path);
 158         if (!dir) {
 159                 debug_error ("can't open directory %s", path);
 160                 return NULL;
 161         }
 162
 163         cache = XMALLOC (struct dirent_hashent);
 164         cache->names_len = 0;
 165         cache->names_max = 1024;
 166         cache->names = XNMALLOC (cache->names_max, char *);
 167
 168         /* Dump all the entries into cache->names, resizing if necessary. */
 169         for (entry = readdir (dir); entry; entry = readdir (dir)) {
 170                 if (cache->names_len >= cache->names_max) {
 171                         cache->names_max *= 2;
 172                         cache->names =
 173                                 xnrealloc (cache->names, cache->names_max,
 174                                            sizeof (char *));
 175                 }
 176                 cache->names[cache->names_len++] = xstrdup (entry->d_name);
 177         }
 178
 179         qsort (cache->names, cache->names_len, sizeof *cache->names,
 180                &cache_compare);
 181
 182         hashtable_install (dirent_hash, path, strlen (path), cache);
 183         closedir (dir);
 184
 185         return cache;
 186 }
 187
 188 struct pattern_bsearch {
 189         char *pattern;
 190         size_t len;
 191 };
 192
 193 static int pattern_compare (const void *a, const void *b)
 194 {
 195         const struct pattern_bsearch *key = a;
 196         const char *memb = *(const char **) b;
 197         return strncasecmp (key->pattern, memb, key->len);
 198 }
 199
 200 static void clear_glob (glob_t *pglob)
 201 {
 202         /* look_for_file declares this static, so it's zero-initialised.
 203          * globfree() can deal with checking it before freeing.
 204          */
 205         globfree (pglob);
 206
 207         pglob->gl_pathc = 0;
 208         pglob->gl_pathv = NULL;
 209         pglob->gl_offs = 0;
 210 }
 211
 212 static void match_in_directory (const char *path, const char *pattern, int opts,
 213                                 glob_t *pglob, size_t *allocated)
 214 {
 215         struct dirent_hashent *cache;
 216         size_t my_allocated = 0;
 217         int flags;
 218         regex_t preg;
 219         struct pattern_bsearch pattern_start = { NULL, -1 };
 220         char **bsearched;
 221         size_t i;
 222
 223         if (!allocated)
 224                 allocated = &my_allocated;
 225         if (!*allocated)
 226                 clear_glob (pglob);
 227
 228         cache = update_directory_cache (path);
 229         if (!cache) {
 230                 debug ("directory cache update failed\n");
 231                 return;
 232         }
 233
 234         debug ("globbing pattern in %s: %s\n", path, pattern);
 235
 236         if (!*allocated) {
 237                 *allocated = 4;
 238                 pglob->gl_pathv = XNMALLOC (*allocated, char *);
 239                 pglob->gl_pathv[0] = NULL;
 240         }
 241
 242         if (opts & LFF_REGEX)
 243                 flags = REG_EXTENDED | REG_NOSUB |
 244                         ((opts & LFF_MATCHCASE) ? 0 : REG_ICASE);
 245         else
 246                 flags = (opts & LFF_MATCHCASE) ? 0 : FNM_CASEFOLD;
 247
 248         if (opts & LFF_REGEX) {
 249                 xregcomp (&preg, pattern, flags);
 250                 bsearched = cache->names;
 251         } else {
 252                 pattern_start.pattern = xstrndup (pattern,
 253                                                   strcspn (pattern, "?*{}\\"));
 254                 pattern_start.len = strlen (pattern_start.pattern);
 255                 bsearched = bsearch (&pattern_start, cache->names,
 256                                      cache->names_len, sizeof *cache->names,
 257                                      &pattern_compare);
 258                 if (!bsearched) {
 259                         free (pattern_start.pattern);
 260                         return;
 261                 }
 262                 while (bsearched > cache->names &&
 263                        !strncasecmp (pattern_start.pattern, *(bsearched - 1),
 264                                      pattern_start.len))
 265                         --bsearched;
 266         }
 267
 268         for (i = bsearched - cache->names; i < cache->names_len; ++i) {
 269                 if (opts & LFF_REGEX) {
 270                         if (regexec (&preg, cache->names[i], 0, NULL, 0) != 0)
 271                                 continue;
 272                 } else {
 273                         if (strncasecmp (pattern_start.pattern,
 274                                          cache->names[i], pattern_start.len))
 275                                 break;
 276
 277                         if (fnmatch (pattern, cache->names[i], flags) != 0)
 278                                 continue;
 279                 }
 280
 281                 debug ("matched: %s/%s\n", path, cache->names[i]);
 282
 283                 if (pglob->gl_pathc >= *allocated) {
 284                         *allocated *= 2;
 285                         pglob->gl_pathv = xnrealloc (
 286                                 pglob->gl_pathv, *allocated, sizeof (char *));
 287                 }
 288                 pglob->gl_pathv[pglob->gl_pathc++] =
 289                         xasprintf ("%s/%s", path, cache->names[i]);
 290         }
 291
 292         if (opts & LFF_REGEX)
 293                 regfree (&preg);
 294         else
 295                 free (pattern_start.pattern);
 296
 297         if (pglob->gl_pathc >= *allocated) {
 298                 *allocated *= 2;
 299                 pglob->gl_pathv = xnrealloc (pglob->gl_pathv,
 300                                              *allocated, sizeof (char *));
 301         }
 302         pglob->gl_pathv[pglob->gl_pathc] = NULL;
 303
 304         return;
 305 }
 306
 307 char **look_for_file (const char *hier, const char *sec,
 308                       const char *unesc_name, int cat, int opts)
 309 {
 310         char *pattern, *path = NULL;
 311         static glob_t gbuf;
 312         static int cleanup_installed = 0;
 313         static int layout = -1;
 314         char *name;
 315
 316         if (!cleanup_installed) {
 317                 /* appease valgrind */
 318                 push_cleanup ((cleanup_fun) globfree, &gbuf, 0);
 319                 cleanup_installed = 1;
 320         }
 321
 322         clear_glob (&gbuf);
 323
 324         /* This routine only does a minimum amount of matching. It does not
 325            find cat files in the alternate cat directory. */
 326
 327         if (layout == -1) {
 328                 layout = parse_layout (mandir_layout);
 329                 debug ("Layout is %s (%d)\n", mandir_layout, layout);
 330         }
 331
 332         if (opts & (LFF_REGEX | LFF_WILDCARD))
 333                 name = xstrdup (unesc_name);
 334         else
 335                 name = escape_shell (unesc_name);
 336
 337         /* allow lookups like "3x foo" to match "../man3/foo.3x" */
 338
 339         if (layout & LAYOUT_GNU) {
 340                 glob_t dirs;
 341                 size_t i;
 342                 size_t allocated = 0;
 343
 344                 memset (&dirs, 0, sizeof (dirs));
 345                 pattern = xasprintf ("%s\t*", cat ? "cat" : "man");
 346                 *strrchr (pattern, '\t') = *sec;
 347                 match_in_directory (hier, pattern, LFF_MATCHCASE, &dirs, NULL);
 348                 free (pattern);
 349
 350                 pattern = make_pattern (name, sec, opts);
 351                 for (i = 0; i < dirs.gl_pathc; ++i) {
 352                         if (path)
 353                                 *path = '\0';
 354                         match_in_directory (dirs.gl_pathv[i], pattern, opts,
 355                                             &gbuf, &allocated);
 356                 }
 357                 free (pattern);
 358                 globfree (&dirs);
 359         }
 360
 361         /* Try HPUX style compressed man pages */
 362         if ((layout & LAYOUT_HPUX) && gbuf.gl_pathc == 0) {
 363                 if (path)
 364                         *path = '\0';
 365                 path = appendstr (path, hier, cat ? "/cat" : "/man",
 366                                   sec, ".Z", (void *) 0);
 367                 pattern = make_pattern (name, sec, opts);
 368
 369                 match_in_directory (path, pattern, opts, &gbuf, NULL);
 370                 free (pattern);
 371         }
 372
 373         /* Try man pages without the section extension --- IRIX man pages */
 374         if ((layout & LAYOUT_IRIX) && gbuf.gl_pathc == 0) {
 375                 if (path)
 376                         *path = '\0';
 377                 path = appendstr (path, hier, cat ? "/cat" : "/man", sec,
 378                                   (void *) 0);
 379                 if (opts & LFF_REGEX)
 380                         pattern = xasprintf ("%s\\..*", name);
 381                 else
 382                         pattern = xasprintf ("%s.*", name);
 383
 384                 match_in_directory (path, pattern, opts, &gbuf, NULL);
 385                 free (pattern);
 386         }
 387
 388         /* Try Solaris style man page directories */
 389         if ((layout & LAYOUT_SOLARIS) && gbuf.gl_pathc == 0) {
 390                 if (path)
 391                         *path = '\0';
 392                 /* TODO: This needs to be man/sec*, not just man/sec. */
 393                 path = appendstr (path, hier, cat ? "/cat" : "/man", sec,
 394                                   (void *) 0);
 395                 pattern = make_pattern (name, sec, opts);
 396
 397                 match_in_directory (path, pattern, opts, &gbuf, NULL);
 398                 free (pattern);
 399         }
 400
 401         /* BSD cat pages take the extension .0 */
 402         if ((layout & LAYOUT_BSD) && gbuf.gl_pathc == 0) {
 403                 if (path)
 404                         *path = '\0';
 405                 if (cat) {
 406                         path = appendstr (path, hier, "/cat", sec, (void *) 0);
 407                         if (opts & LFF_REGEX)
 408                                 pattern = xasprintf ("%s\\.0.*", name);
 409                         else
 410                                 pattern = xasprintf ("%s.0*", name);
 411                 } else {
 412                         path = appendstr (path, hier, "/man", sec, (void *) 0);
 413                         pattern = make_pattern (name, sec, opts);
 414                 }
 415                 match_in_directory (path, pattern, opts, &gbuf, NULL);
 416                 free (pattern);
 417         }
 418
 419         free (name);
 420         free (path);
 421
 422         if (gbuf.gl_pathc == 0)
 423                 return NULL;
 424         else
 425                 return gbuf.gl_pathv;
 426 }
 427
 428 char **expand_path (const char *path)
 429 {
 430         int res = 0;
 431         char **result = NULL;
 432         glob_t globbuf;
 433         size_t i;
 434
 435         res = glob (path, GLOB_NOCHECK, NULL, &globbuf);
 436         /* if glob failed, return the given path */
 437         if (res != 0) {
 438                 result = XNMALLOC (2, char *);
 439                 result[0] = xstrdup (path);
 440                 result[1] = NULL;
 441                 return result;
 442         }
 443
 444         result = XNMALLOC (globbuf.gl_pathc + 1, char *);
 445         for (i = 0; i < globbuf.gl_pathc; i++) {
 446                 result[i] = xstrdup (globbuf.gl_pathv[i]);
 447         }
 448         result[globbuf.gl_pathc] = NULL;
 449
 450         globfree (&globbuf);
 451
 452         return result;
 453 }