GNU Octave  4.0.0
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
kpse.cc
Go to the documentation of this file.
1 // This file is not compiled to a separate object file. It is
2 // included in pathsearch.cc.
3 
4 /* Look up a filename in a path.
5 
6 Copyright (C) 2003-2015 John W. Eaton
7 Copyright (C) 1993, 94, 95, 96, 97, 98 Karl Berry.
8 Copyright (C) 1993, 94, 95, 96, 97 Karl Berry & O. Weber.
9 Copyright (C) 1992, 93, 94, 95, 96, 97 Free Software Foundation, Inc.
10 
11 This file is part of Octave.
12 
13 Octave is free software; you can redistribute it and/or modify it
14 under the terms of the GNU General Public License as published by the
15 Free Software Foundation; either version 3 of the License, or (at your
16 option) any later version.
17 
18 Octave is distributed in the hope that it will be useful, but WITHOUT
19 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
20 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 for more details.
22 
23 You should have received a copy of the GNU General Public License
24 along with Octave; see the file COPYING. If not, see
25 <http://www.gnu.org/licenses/>.
26 
27 */
28 
29 #if defined (HAVE_CONFIG_H)
30 #include <config.h>
31 #endif
32 
33 #include <map>
34 #include <string>
35 
36 /* System defines are for non-Unix systems only. (Testing for all Unix
37  variations should be done in configure.) Presently the defines used
38  are: DOS OS2 WIN32. I do not use any of these systems
39  myself; if you do, I'd be grateful for any changes. [email protected] */
40 
41 /* If we have either DOS or OS2, we are DOSISH. */
42 #if defined (DOS) || defined (OS2) || defined (WIN32) || defined (__MSDOS__)
43 #define DOSISH
44 #endif
45 
46 #if defined (DOSISH)
47 #define MONOCASE_FILENAMES /* case-insensitive filename comparisons */
48 #endif
49 
50 extern "C" {
51 #if defined (__MINGW32__)
52 #include <windows.h>
53 #include <fcntl.h>
54 #include <dirent.h>
55 #elif defined (WIN32)
56 #ifndef _MSC_VER
57 #define __STDC__ 1
58 #include "win32lib.h"
59 #endif
60 #endif /* not WIN32 */
61 
62 #ifdef __DJGPP__
63 #include <fcntl.h> /* for long filenames' stuff */
64 #include <dir.h> /* for 'getdisk' */
65 #include <io.h> /* for 'setmode' */
66 #endif
67 }
68 
69 /* Some drivers have partially integrated kpathsea changes. */
70 #ifndef KPATHSEA
71 #define KPATHSEA 32
72 #endif
73 
74 /* System dependencies that are figured out by 'configure'. If we are
75  compiling standalone, we get our c-auto.h. Otherwise, the package
76  containing us must provide this (unless it can somehow generate ours
77  from c-auto.in). We use <...> instead of "..." so that the current
78  cpp directory (i.e., kpathsea/) won't be searched. */
79 
80 /* If you want to find subdirectories in a directory with non-Unix
81  semantics (specifically, if a directory with no subdirectories does
82  not have exactly two links), define this. */
83 #if defined (__DJGPP__) || ! defined (DOSISH)
84 /* Surprise! DJGPP returns st_nlink exactly like on Unix. */
85 #define ST_NLINK_TRICK
86 #endif /* either not DOSISH or __DJGPP__ */
87 
88 #ifdef OS2
89 #define access ln_access
90 #define fopen ln_fopen
91 #define rename ln_rename
92 #define stat ln_stat
93 #endif /* OS2 */
94 
95 /* Define the characters which separate components of
96  filenames and environment variable paths. */
97 
98 /* What separates filename components? */
99 #ifndef DIR_SEP
100 #ifdef DOSISH
101 /* Either \'s or 's work. Wayne Sullivan's web2pc prefers /, so we'll
102  go with that. */
103 #define DIR_SEP '/'
104 #define DIR_SEP_STRING "/"
105 #define IS_DEVICE_SEP(ch) ((ch) == ':')
106 #define NAME_BEGINS_WITH_DEVICE(name) ((name.length ()>0) && IS_DEVICE_SEP((name)[1]))
107 /* On DOS, it's good to allow both \ and / between directories. */
108 #define IS_DIR_SEP(ch) ((ch) == '/' || (ch) == '\\')
109 #else
110 #define DIR_SEP '/'
111 #define DIR_SEP_STRING "/"
112 #endif /* not DOSISH */
113 #endif /* not DIR_SEP */
114 
115 #ifndef IS_DIR_SEP
116 #define IS_DIR_SEP(ch) ((ch) == DIR_SEP)
117 #endif
118 #ifndef IS_DEVICE_SEP /* No 'devices' on, e.g., Unix. */
119 #define IS_DEVICE_SEP(ch) 0
120 #endif
121 #ifndef NAME_BEGINS_WITH_DEVICE
122 #define NAME_BEGINS_WITH_DEVICE(name) 0
123 #endif
124 
125 #include "lo-error.h"
126 #include "oct-env.h"
127 #include "oct-passwd.h"
128 #include "str-vec.h"
129 
130 /* Header files that essentially all of our sources need, and
131  that all implementations have. We include these first, to help with
132  NULL being defined multiple times. */
133 #include <cstdio>
134 #include <cstdarg>
135 #include <cstdlib>
136 #include <cerrno>
137 #include <cassert>
138 
139 #include <sys/types.h>
140 #include <unistd.h>
141 
142 #include "sysdir.h"
143 #include "statdefs.h"
144 
145 /* define NAME_MAX, the maximum length of a single
146  component in a filename. No such limit may exist, or may vary
147  depending on the filesystem. */
148 
149 /* Most likely the system will truncate filenames if it is not POSIX,
150  and so we can use the BSD value here. */
151 #ifndef _POSIX_NAME_MAX
152 #define _POSIX_NAME_MAX 255
153 #endif
154 
155 #ifndef NAME_MAX
156 #define NAME_MAX _POSIX_NAME_MAX
157 #endif
158 
159 #include <cctype>
160 
161 /* What separates elements in environment variable path lists? */
162 #ifndef ENV_SEP
163 #if defined (SEPCHAR) && defined (SEPCHAR_STR)
164 #define ENV_SEP SEPCHAR
165 #define ENV_SEP_STRING SEPCHAR_STR
166 #elif defined (DOSISH)
167 #define ENV_SEP ';'
168 #define ENV_SEP_STRING ";"
169 #else
170 #define ENV_SEP ':'
171 #define ENV_SEP_STRING ":"
172 #endif /* not DOS */
173 #endif /* not ENV_SEP */
174 
175 #ifndef IS_ENV_SEP
176 #define IS_ENV_SEP(ch) ((ch) == ENV_SEP)
177 #endif
178 
179 /* define PATH_MAX, the maximum length of a filename. Since no such
180  limit may exist, it's preferable to dynamically grow filenames as
181  needed. */
182 
183 /* Cheat and define this as a manifest constant no matter what, instead
184  of using pathconf. I forget why we want to do this. */
185 
186 #ifndef _POSIX_PATH_MAX
187 #define _POSIX_PATH_MAX 255
188 #endif
189 
190 #ifndef PATH_MAX
191 #ifdef MAXPATHLEN
192 #define PATH_MAX MAXPATHLEN
193 #else
194 #define PATH_MAX _POSIX_PATH_MAX
195 #endif
196 #endif /* not PATH_MAX */
197 
198 /* If NO_DEBUG is defined (not recommended), skip all this. */
199 #ifndef NO_DEBUG
200 
201 /* OK, we'll have tracing support. */
202 #define KPSE_DEBUG
203 
204 /* Test if a bit is on. */
205 #define KPSE_DEBUG_P(bit) (kpathsea_debug & (1 << (bit)))
206 
207 #define KPSE_DEBUG_STAT 0 /* stat calls */
208 #define KPSE_DEBUG_HASH 1 /* hash lookups */
209 #define KPSE_DEBUG_FOPEN 2 /* fopen/fclose calls */
210 #define KPSE_DEBUG_PATHS 3 /* search path initializations */
211 #define KPSE_DEBUG_EXPAND 4 /* path element expansion */
212 #define KPSE_DEBUG_SEARCH 5 /* searches */
213 #define KPSE_DEBUG_VARS 6 /* variable values */
214 #define KPSE_LAST_DEBUG KPSE_DEBUG_VARS
215 
216 /* A printf for the debugging. */
217 #define DEBUGF_START() do { gnulib::fputs ("kdebug:", stderr)
218 #define DEBUGF_END() gnulib::fflush (stderr); } while (0)
219 
220 #define DEBUGF(str) \
221  DEBUGF_START (); gnulib::fputs (str, stderr); DEBUGF_END ()
222 #define DEBUGF1(str, e1) \
223  DEBUGF_START (); gnulib::fprintf (stderr, str, e1); DEBUGF_END ()
224 #define DEBUGF2(str, e1, e2) \
225  DEBUGF_START (); gnulib::fprintf (stderr, str, e1, e2); DEBUGF_END ()
226 #define DEBUGF3(str, e1, e2, e3) \
227  DEBUGF_START (); gnulib::fprintf (stderr, str, e1, e2, e3); DEBUGF_END ()
228 #define DEBUGF4(str, e1, e2, e3, e4) \
229  DEBUGF_START (); gnulib::fprintf (stderr, str, e1, e2, e3, e4); DEBUGF_END ()
230 
231 #endif /* not NO_DEBUG */
232 
233 #ifdef KPSE_DEBUG
234 static unsigned int kpathsea_debug = 0;
235 #endif
236 
237 #if defined (WIN32) && !defined (__MINGW32__)
238 
239 /* System description file for Windows NT. */
240 
241 /*
242  * Define symbols to identify the version of Unix this is.
243  * Define all the symbols that apply correctly.
244  */
245 
246 #ifndef DOSISH
247 #define DOSISH
248 #endif
249 
250 #ifndef MAXPATHLEN
251 #define MAXPATHLEN _MAX_PATH
252 #endif
253 
254 /* These have to be defined because our compilers treat __STDC__ as being
255  defined (most of them anyway). */
256 
257 #define access _access
258 #define stat _stat
259 #define strdup _strdup
260 
261 #define S_IFMT _S_IFMT
262 #define S_IFDIR _S_IFDIR
263 
264 /* Define this so that winsock.h definitions don't get included when
265  windows.h is... For this to have proper effect, config.h must
266  always be included before windows.h. */
267 #define _WINSOCKAPI_ 1
268 
269 #include <windows.h>
270 
271 /* For proper declaration of environ. */
272 #include <io.h>
273 #include <fcntl.h>
274 #include <process.h>
275 
276 /* ============================================================ */
277 
278 #endif /* WIN32 */
279 
280 /* Define common sorts of messages. */
281 
282 /* This should be called only after a system call fails. Don't exit
283  with status 'errno', because that might be 256, which would mean
284  success (exit statuses are truncated to eight bits). */
285 #define FATAL_PERROR(str) \
286  do \
287  { \
288  gnulib::fputs ("pathsearch: ", stderr); \
289  perror (str); exit (EXIT_FAILURE); \
290  } \
291  while (0)
292 
293 #define FATAL(str) \
294  do \
295  { \
296  gnulib::fputs ("pathsearch: fatal: ", stderr); \
297  gnulib::fputs (str, stderr); \
298  gnulib::fputs (".\n", stderr); \
299  exit (1); \
300  } \
301  while (0)
302 
303 #ifndef WIN32
304 static void xclosedir (DIR *d);
305 #endif
306 
307 /* It's a little bizarre to be using the same type for the list and the
308  elements of the list, but no reason not to in this case, I think --
309  we never need a NULL string in the middle of the list, and an extra
310  NULL/NULL element always at the end is inconsequential. */
311 
313 {
314  str_llist_elt (void) : str (), moved (0), next (0) { }
315 
316  ~str_llist_elt (void) { }
317 
318  std::string str;
319  int moved;
321 };
322 
325 
326 #define STR_LLIST(sl) ((sl).str)
327 #define STR_LLIST_MOVED(sl) ((sl).moved)
328 #define STR_LLIST_NEXT(sl) ((sl).next)
329 
330 static void str_llist_add (str_llist_type *l, const std::string& str);
331 
332 static void str_llist_float (str_llist_type *l, str_llist_elt_type *mover);
333 
334 static std::string kpse_var_expand (const std::string& src);
335 
336 static str_llist_type *kpse_element_dirs (const std::string& elt);
337 
338 static std::string kpse_expand (const std::string& s);
339 
340 static std::string kpse_expand_default (const std::string& path,
341  const std::string& dflt);
342 
343 static string_vector kpse_db_search (const std::string& name,
344  const std::string& path_elt, bool all);
345 
346 #include <ctime> /* for 'time' */
347 
348 static bool
350 {
351  return IS_ENV_SEP (c);
352 }
353 
354 /* These routines just check the return status from standard library
355  routines and abort if an error happens. */
356 
357 static FILE *
358 xfopen (const std::string& filename, const char *mode)
359 {
360  FILE *f;
361 
362  assert (! filename.empty () && mode);
363 
364  f = gnulib::fopen (filename.c_str (), mode);
365 
366  if (! f)
367  FATAL_PERROR (filename.c_str ());
368 
370  DEBUGF3 ("fopen (%s, %s) => 0x%lx\n", filename.c_str (), mode,
371  reinterpret_cast<intptr_t> (f));
372 
373  return f;
374 }
375 
376 /* A single (key,value) pair. */
377 
379 {
380  std::string key;
381  std::string value;
383 };
384 
385 /* The usual arrangement of buckets initialized to null. */
386 
388 {
390  unsigned size;
391 };
392 
393 static unsigned
394 kpse_hash (hash_table_type table, const std::string& key)
395 {
396  unsigned n = 0;
397 
398  /* Our keys aren't often anagrams of each other, so no point in
399  weighting the characters. */
400  size_t len = key.length ();
401  for (size_t i = 0; i < len; i++)
402  n = (n + n + key[i]) % table.size;
403 
404  return n;
405 }
406 
407 /* Look up STR in MAP. Return a (dynamically-allocated) list of the
408  corresponding strings or NULL if no match. */
409 
410 static string_vector
411 hash_lookup (hash_table_type table, const std::string& key)
412 {
414  string_vector ret;
415  unsigned n = kpse_hash (table, key);
416 
417  /* Look at everything in this bucket. */
418  for (p = table.buckets[n]; p; p = p->next)
419  if (key == p->key)
420  ret.append (p->value);
421 
422 #ifdef KPSE_DEBUG
424  {
425  DEBUGF1 ("hash_lookup (%s) =>", key.c_str ());
426  if (ret.empty ())
427  gnulib::fputs (" (nil)\n", stderr);
428  else
429  {
430  int len = ret.length ();
431  for (int i = 0; i < len; i++)
432  {
433  gnulib::putc (' ', stderr);
434  gnulib::fputs (ret[i].c_str (), stderr);
435  }
436  gnulib::putc ('\n', stderr);
437  }
438  gnulib::fflush (stderr);
439  }
440 #endif
441 
442  return ret;
443 }
444 
445 /* A way to step through a path, extracting one directory name at a
446  time. */
447 
449 {
450 public:
451 
452  kpse_path_iterator (const std::string& p)
453  : path (p), b (0), e (0), len (path.length ()) { set_end (); }
454 
456  : path (pi.path), b (pi.b), e (pi.e), len (pi.len) { }
457 
459  {
460  kpse_path_iterator retval (*this);
461  next ();
462  return retval;
463  }
464 
465  std::string operator * (void) { return path.substr (b, e-b); }
466 
467  bool operator != (const size_t sz) { return b != sz; }
468 
469 private:
470 
471  const std::string& path;
472  size_t b;
473  size_t e;
474  size_t len;
475 
476  void set_end (void)
477  {
478  e = b + 1;
479 
480  if (e == len)
481  ; /* OK, we have found the last element. */
482  else if (e > len)
483  b = e = std::string::npos;
484  else
485  {
486  /* Find the next colon not enclosed by braces (or the end of
487  the path). */
488 
489  int brace_level = 0;
490  while (e < len && ! (brace_level == 0 && kpse_is_env_sep (path[e])))
491  e++;
492  }
493  }
494 
495  void next (void)
496  {
497  b = e + 1;
498 
499  /* Skip any consecutive colons. */
500  while (b < len && kpse_is_env_sep (path[b]))
501  b++;
502 
503  if (b >= len)
504  b = e = std::string::npos;
505  else
506  set_end ();
507  }
508 
509  // No assignment.
511 };
512 
513 /* Here's the simple one, when a program just wants a value. */
514 
515 static std::string
516 kpse_var_value (const std::string& var)
517 {
518  std::string ret;
519 
520  std::string tmp = octave_env::getenv (var);
521 
522  if (! tmp.empty ())
523  ret = kpse_var_expand (tmp);
524 
525 #ifdef KPSE_DEBUG
527  DEBUGF2 ("variable: %s = %s\n", var.c_str (),
528  tmp.empty () ? "(nil)" : tmp.c_str ());
529 #endif
530 
531  return ret;
532 }
533 
534 /* Truncate any too-long components in NAME, returning the result. It's
535  too bad this is necessary. See comments in readable.c for why. */
536 
537 static std::string
538 kpse_truncate_filename (const std::string& name)
539 {
540  unsigned c_len = 0; /* Length of current component. */
541  unsigned ret_len = 0; /* Length of constructed result. */
542 
543  std::string ret = name;
544 
545  size_t len = name.length ();
546 
547  for (size_t i = 0; i < len; i++)
548  {
549  if (IS_DIR_SEP (name[i]) || IS_DEVICE_SEP (name[i]))
550  {
551  /* At a directory delimiter, reset component length. */
552  c_len = 0;
553  }
554  else if (c_len > NAME_MAX)
555  {
556  /* If past the max for a component, ignore this character. */
557  continue;
558  }
559 
560  /* Copy this character. */
561  ret[ret_len++] = name[i];
562  c_len++;
563  }
564 
565  ret.resize (ret_len);
566 
567  return ret;
568 }
569 
570 /* If access can read FN, run stat (assigning to stat buffer ST) and
571  check that fn is not a directory. Don't check for just being a
572  regular file, as it is potentially useful to read fifo's or some
573  kinds of devices. */
574 
575 #ifdef WIN32
576 static inline bool
577 READABLE (const std::string& fn, struct stat&)
578 {
579  const char *t = fn.c_str ();
580  return (GetFileAttributes (t) != 0xFFFFFFFF
581  && ! (GetFileAttributes (t) & FILE_ATTRIBUTE_DIRECTORY));
582 }
583 #else
584 static inline bool
585 READABLE (const std::string& fn, struct stat& st)
586 {
587  const char *t = fn.c_str ();
588  return (access (t, R_OK) == 0
589  && stat (t, &(st)) == 0 && ! S_ISDIR (st.st_mode));
590 }
591 #endif
592 
593 /* POSIX invented the brain-damage of not necessarily truncating
594  filename components; the system's behavior is defined by the value of
595  the symbol _POSIX_NO_TRUNC, but you can't change it dynamically!
596 
597  Generic const return warning. See extend-fname.c. */
598 
599 static std::string
600 kpse_readable_file (const std::string& name)
601 {
602  struct stat st;
603  std::string ret;
604 
605  if (READABLE (name, st))
606  {
607  ret = name;
608 
609 #ifdef ENAMETOOLONG
610  }
611  else if (errno == ENAMETOOLONG)
612  {
613  ret = kpse_truncate_filename (name);
614 
615  /* Perhaps some other error will occur with the truncated name,
616  so let's call access again. */
617 
618  if (! READABLE (ret, st))
619  {
620  /* Failed. */
621  ret = std::string ();
622  }
623 #endif /* ENAMETOOLONG */
624 
625  }
626  else
627  {
628  /* Some other error. */
629  if (errno == EACCES)
630  {
631  /* Maybe warn them if permissions are bad. */
632  perror (name.c_str ());
633  }
634 
635  ret = std::string ();
636  }
637 
638  return ret;
639 }
640 
641 /* Sorry this is such a system-dependent mess, but I can't see any way
642  to usefully generalize. */
643 
644 static bool
645 kpse_absolute_p (const std::string& filename, int relative_ok)
646 {
647  size_t len = filename.length ();
648 
649  int absolute = (len > 0 && IS_DIR_SEP (filename[0]))
650 #ifdef DOSISH
651  /* Novell allows non-alphanumeric drive letters. */
652  || (len > 0 && IS_DEVICE_SEP (filename[1]))
653 #endif /* DOSISH */
654 #ifdef WIN32
655  /* UNC names */
656  || (len > 1 && filename[0] == '\\' && filename[1] == '\\')
657 #endif
658  ;
659 
660  int explicit_relative
661  = relative_ok
662  && (len > 1
663  && filename[0] == '.'
664  && (IS_DIR_SEP (filename[1])
665  || (len > 2 && filename[1] == '.' && IS_DIR_SEP (filename[2]))));
666 
667  return absolute || explicit_relative;
668 }
669 
670 /* The very first search is for texmf.cnf, called when someone tries to
671  initialize the TFM path or whatever. init_path calls kpse_cnf_get
672  which calls kpse_all_path_search to find all the texmf.cnf's. We
673  need to do various special things in this case, since we obviously
674  don't yet have the configuration files when we're searching for the
675  configuration files. */
676 static bool first_search = true;
677 
678 /* This function is called after every search (except the first, since
679  we definitely want to allow enabling the logging in texmf.cnf) to
680  record the filename(s) found in $TEXMFLOG. */
681 
682 static void
683 log_search (const string_vector& filenames)
684 {
685  static FILE *log_file = 0;
686  static bool first_time = true; /* Need to open the log file? */
687 
688  if (first_time)
689  {
690  first_time = false;
691 
692  /* Get name from either envvar or config file. */
693  std::string log_name = kpse_var_value ("TEXMFLOG");
694 
695  if (! log_name.empty ())
696  {
697  log_file = xfopen (log_name.c_str (), "a");
698 
699  if (! log_file)
700  perror (log_name.c_str ());
701  }
702  }
703 
704  if (KPSE_DEBUG_P (KPSE_DEBUG_SEARCH) || log_file)
705  {
706  /* FILENAMES should never be null, but safety doesn't hurt. */
707  for (int e = 0; e < filenames.length () && ! filenames[e].empty (); e++)
708  {
709  std::string filename = filenames[e];
710 
711  /* Only record absolute filenames, for privacy. */
712  if (log_file && kpse_absolute_p (filename.c_str (), false))
713  gnulib::fprintf (log_file, "%lu %s\n",
714  static_cast<unsigned long> (time (0)),
715  filename.c_str ());
716 
717  /* And show them online, if debugging. We've already started
718  the debugging line in 'search', where this is called, so
719  just print the filename here, don't use DEBUGF. */
721  gnulib::fputs (filename.c_str (), stderr);
722  }
723  }
724 }
725 
726 /* Concatenate each element in DIRS with NAME (assume each ends with a
727  /, to save time). If SEARCH_ALL is false, return the first readable
728  regular file. Else continue to search for more. In any case, if
729  none, return a list containing just NULL.
730 
731  We keep a single buffer for the potential filenames and reallocate
732  only when necessary. I'm not sure it's noticeably faster, but it
733  does seem cleaner. (We do waste a bit of space in the return
734  value, though, since we don't shrink it to the final size returned.) */
735 
736 static string_vector
737 dir_list_search (str_llist_type *dirs, const std::string& name,
738  bool search_all)
739 {
740  str_llist_elt_type *elt;
741  string_vector ret;
742 
743  for (elt = *dirs; elt; elt = STR_LLIST_NEXT (*elt))
744  {
745  const std::string dir = STR_LLIST (*elt);
746 
747  std::string potential = dir + name;
748 
749  std::string tmp = kpse_readable_file (potential);
750 
751  if (! tmp.empty ())
752  {
753  ret.append (potential);
754 
755  /* Move this element towards the top of the list. */
756  str_llist_float (dirs, elt);
757 
758  if (! search_all)
759  return ret;
760  }
761  }
762 
763  return ret;
764 }
765 
766 /* This is called when NAME is absolute or explicitly relative; if it's
767  readable, return (a list containing) it; otherwise, return NULL. */
768 
769 static string_vector
770 absolute_search (const std::string& name)
771 {
772  string_vector ret_list;
773  std::string found = kpse_readable_file (name);
774 
775  /* Add 'found' to the return list even if it's null; that tells
776  the caller we didn't find anything. */
777  ret_list.append (found);
778 
779  return ret_list;
780 }
781 
782 /* This is the hard case -- look for NAME in PATH. If ALL is false,
783  return the first file found. Otherwise, search all elements of PATH. */
784 
785 static string_vector
786 path_search (const std::string& path, const std::string& name,
787  bool /* must_exist */, bool all)
788 {
789  string_vector ret_list;
790  bool done = false;
791 
792  for (kpse_path_iterator pi (path); ! done && pi != std::string::npos; pi++)
793  {
794  std::string elt = *pi;
795 
796  string_vector found;
797  bool allow_disk_search = true;
798 
799  if (elt.length () > 1 && elt[0] == '!' && elt[1] == '!')
800  {
801  /* Those magic leading chars in a path element means don't
802  search the disk for this elt. And move past the magic to
803  get to the name. */
804  allow_disk_search = false;
805  elt = elt.substr (2);
806  }
807 
808  /* Do not touch the device if present */
809  if (NAME_BEGINS_WITH_DEVICE (elt))
810  {
811  while (elt.length () > 3
812  && IS_DIR_SEP (elt[2]) && IS_DIR_SEP (elt[3]))
813  {
814  elt[2] = elt[1];
815  elt[1] = elt[0];
816  elt = elt.substr (1);
817  }
818  }
819  else
820  {
821  /* We never want to search the whole disk. */
822  while (elt.length () > 1
823  && IS_DIR_SEP (elt[0]) && IS_DIR_SEP (elt[1]))
824  elt = elt.substr (1);
825  }
826 
827  /* Try ls-R, unless we're searching for texmf.cnf. Our caller
828  (search), also tests first_search, and does the resetting. */
829  found = first_search ? string_vector () : kpse_db_search (name, elt, all);
830 
831  /* Search the filesystem if (1) the path spec allows it, and either
832  (2a) we are searching for texmf.cnf ; or
833  (2b) no db exists; or
834  (2c) no db's are relevant to this elt; or
835  (3) MUST_EXIST && NAME was not in the db.
836  In (2*), 'found' will be NULL.
837  In (3), 'found' will be an empty list. */
838 
839  if (allow_disk_search && found.empty ())
840  {
841  str_llist_type *dirs = kpse_element_dirs (elt);
842 
843  if (dirs && *dirs)
844  found = dir_list_search (dirs, name, all);
845  }
846 
847  /* Did we find anything anywhere? */
848  if (! found.empty ())
849  {
850  if (all)
851  ret_list.append (found);
852  else
853  {
854  ret_list.append (found[0]);
855  done = true;
856  }
857  }
858  }
859 
860  return ret_list;
861 }
862 
863 /* Search PATH for ORIGINAL_NAME. If ALL is false, or ORIGINAL_NAME is
864  absolute_p, check ORIGINAL_NAME itself. Otherwise, look at each
865  element of PATH for the first readable ORIGINAL_NAME.
866 
867  Always return a list; if no files are found, the list will
868  contain just NULL. If ALL is true, the list will be
869  terminated with NULL. */
870 
871 static string_vector
872 search (const std::string& path, const std::string& original_name,
873  bool must_exist, bool all)
874 {
875  string_vector ret_list;
876  bool absolute_p;
877 
878  /* Make a leading ~ count as an absolute filename, and expand $FOO's. */
879  std::string name = kpse_expand (original_name);
880 
881  /* If the first name is absolute or explicitly relative, no need to
882  consider PATH at all. */
883  absolute_p = kpse_absolute_p (name, true);
884 
886  DEBUGF4 ("start search (file=%s, must_exist=%d, find_all=%d, path=%s).\n",
887  name.c_str (), must_exist, all, path.c_str ());
888 
889  /* Find the file(s). */
890  ret_list = absolute_p ? absolute_search (name)
891  : path_search (path, name, must_exist, all);
892 
893  /* The very first search is for texmf.cnf. We can't log that, since
894  we want to allow setting TEXMFLOG in texmf.cnf. */
895  if (first_search)
896  {
897  first_search = false;
898  }
899  else
900  {
901  /* Record the filenames we found, if desired. And wrap them in a
902  debugging line if we're doing that. */
903 
905  DEBUGF1 ("search (%s) =>", original_name.c_str ());
906 
907  log_search (ret_list);
908 
910  gnulib::putc ('\n', stderr);
911  }
912 
913  return ret_list;
914 }
915 
916 /* Search PATH for the first NAME. */
917 
918 /* Call 'kpse_expand' on NAME. If the result is an absolute or
919  explicitly relative filename, check whether it is a readable
920  (regular) file.
921 
922  Otherwise, look in each of the directories specified in PATH (also do
923  tilde and variable expansion on elements in PATH), using a prebuilt
924  db (see db.h) if it's relevant for a given path element.
925 
926  If the prebuilt db doesn't exist, or if MUST_EXIST is true and NAME
927  isn't found in the prebuilt db, look on the filesystem. (I.e., if
928  MUST_EXIST is false, and NAME isn't found in the db, do *not* look on
929  the filesystem.)
930 
931  The caller must expand PATH. This is because it makes more sense to
932  do this once, in advance, instead of for every search using it.
933 
934  In any case, return the complete filename if found, otherwise NULL. */
935 
936 static std::string
937 kpse_path_search (const std::string& path, const std::string& name,
938  bool must_exist)
939 {
940  string_vector ret_list = search (path, name, must_exist, false);
941 
942  return ret_list.empty () ? std::string () : ret_list[0];
943 }
944 
945 /* Search all elements of PATH for files named NAME. Not sure if it's
946  right to assert 'must_exist' here, but it suffices now. */
947 
948 /* Like 'kpse_path_search' with MUST_EXIST true, but return a list of
949  all the filenames (or NULL if none), instead of taking the first. */
950 
951 static string_vector
952 kpse_all_path_search (const std::string& path, const std::string& name)
953 {
954  return search (path, name, true, true);
955 }
956 
957 /* This is the hard case -- look in each element of PATH for each
958  element of NAMES. If ALL is false, return the first file found.
959  Otherwise, search all elements of PATH. */
960 
961 static string_vector
962 path_find_first_of (const std::string& path, const string_vector& names,
963  bool /* must_exist */, bool all)
964 {
965  string_vector ret_list;
966  bool done = false;
967 
968  for (kpse_path_iterator pi (path); ! done && pi != std::string::npos; pi++)
969  {
970  std::string elt = *pi;
971 
972  str_llist_type *dirs;
973  str_llist_elt_type *dirs_elt;
974  string_vector found;
975  bool allow_disk_search = true;
976 
977  if (elt.length () > 1 && elt[0] == '!' && elt[1] == '!')
978  {
979  /* Those magic leading chars in a path element means don't
980  search the disk for this elt. And move past the magic to
981  get to the name. */
982 
983  allow_disk_search = false;
984  elt = elt.substr (2);
985  }
986 
987  /* Do not touch the device if present */
988 
989  if (NAME_BEGINS_WITH_DEVICE (elt))
990  {
991  while (elt.length () > 3
992  && IS_DIR_SEP (elt[2]) && IS_DIR_SEP (elt[3]))
993  {
994  elt[2] = elt[1];
995  elt[1] = elt[0];
996  elt = elt.substr (1);
997  }
998  }
999  else
1000  {
1001  /* We never want to search the whole disk. */
1002  while (elt.length () > 1
1003  && IS_DIR_SEP (elt[0]) && IS_DIR_SEP (elt[1]))
1004  elt = elt.substr (1);
1005  }
1006 
1007  /* We have to search one directory at a time. */
1008  dirs = kpse_element_dirs (elt);
1009  for (dirs_elt = *dirs; dirs_elt; dirs_elt = STR_LLIST_NEXT (*dirs_elt))
1010  {
1011  const std::string dir = STR_LLIST (*dirs_elt);
1012 
1013  int len = names.length ();
1014  for (int i = 0; i < len && !done; i++)
1015  {
1016  std::string name = names[i];
1017 
1018  /* Try ls-R, unless we're searching for texmf.cnf. Our caller
1019  (find_first_of), also tests first_search, and does the
1020  resetting. */
1021  found = first_search ? string_vector ()
1022  : kpse_db_search (name, dir.c_str (), all);
1023 
1024  /* Search the filesystem if (1) the path spec allows it,
1025  and either
1026 
1027  (2a) we are searching for texmf.cnf ; or
1028  (2b) no db exists; or
1029  (2c) no db's are relevant to this elt; or
1030  (3) MUST_EXIST && NAME was not in the db.
1031 
1032  In (2*), 'found' will be NULL.
1033  In (3), 'found' will be an empty list. */
1034 
1035  if (allow_disk_search && found.empty ())
1036  {
1037  static str_llist_type *tmp = 0;
1038 
1039  if (! tmp)
1040  {
1041  tmp = new str_llist_type;
1042  *tmp = 0;
1043  str_llist_add (tmp, "");
1044  }
1045 
1046  STR_LLIST (*(*tmp)) = dir;
1047 
1048  found = dir_list_search (tmp, name, all);
1049  }
1050 
1051  /* Did we find anything anywhere? */
1052  if (! found.empty ())
1053  {
1054  if (all)
1055  ret_list.append (found);
1056  else
1057  {
1058  ret_list.append (found[0]);
1059  done = true;
1060  }
1061  }
1062  }
1063  }
1064  }
1065 
1066  return ret_list;
1067 }
1068 
1069 static string_vector
1070 find_first_of (const std::string& path, const string_vector& names,
1071  bool must_exist, bool all)
1072 {
1073  string_vector ret_list;
1074 
1076  {
1077  gnulib::fputs ("start find_first_of ((", stderr);
1078 
1079  int len = names.length ();
1080 
1081  for (int i = 0; i < len; i++)
1082  {
1083  if (i == 0)
1084  gnulib::fputs (names[i].c_str (), stderr);
1085  else
1086  gnulib::fprintf (stderr, ", %s", names[i].c_str ());
1087  }
1088 
1089  gnulib::fprintf (stderr, "), path=%s, must_exist=%d).\n",
1090  path.c_str (), must_exist);
1091  }
1092 
1093  for (int i = 0; i < names.length (); i++)
1094  {
1095  std::string name = names[i];
1096 
1097  if (kpse_absolute_p (name, true))
1098  {
1099  /* If the name is absolute or explicitly relative, no need
1100  to consider PATH at all. If we find something, then we
1101  are done. */
1102 
1103  ret_list = absolute_search (name);
1104 
1105  if (! ret_list.empty ())
1106  return ret_list;
1107  }
1108  }
1109 
1110  /* Find the file. */
1111  ret_list = path_find_first_of (path, names, must_exist, all);
1112 
1113  /* The very first search is for texmf.cnf. We can't log that, since
1114  we want to allow setting TEXMFLOG in texmf.cnf. */
1115  if (first_search)
1116  {
1117  first_search = false;
1118  }
1119  else
1120  {
1121  /* Record the filenames we found, if desired. And wrap them in a
1122  debugging line if we're doing that. */
1123 
1125  {
1126  gnulib::fputs ("find_first_of (", stderr);
1127 
1128  int len = names.length ();
1129 
1130  for (int i = 0; i < len; i++)
1131  {
1132  if (i == 0)
1133  gnulib::fputs (names[i].c_str (), stderr);
1134  else
1135  gnulib::fprintf (stderr, ", %s", names[i].c_str ());
1136  }
1137 
1138  gnulib::fputs (") =>", stderr);
1139  }
1140 
1141  log_search (ret_list);
1142 
1144  gnulib::putc ('\n', stderr);
1145  }
1146 
1147  return ret_list;
1148 }
1149 
1150 /* Search each element of PATH for each element of NAMES. Return the
1151  first one found. */
1152 
1153 /* Search each element of PATH for each element in the list of NAMES.
1154  Return the first one found. */
1155 
1156 static std::string
1157 kpse_path_find_first_of (const std::string& path, const string_vector& names,
1158  bool must_exist)
1159 {
1160  string_vector ret_list = find_first_of (path, names, must_exist, false);
1161 
1162  return ret_list.empty () ? std::string () : ret_list[0];
1163 }
1164 
1165 /* Search each element of PATH for each element of NAMES and return a
1166  list containing everything found, in the order found. */
1167 
1168 /* Like 'kpse_path_find_first_of' with MUST_EXIST true, but return a
1169  list of all the filenames (or NULL if none), instead of taking the
1170  first. */
1171 
1172 static string_vector
1173 kpse_all_path_find_first_of (const std::string& path,
1174  const string_vector& names)
1175 {
1176  return find_first_of (path, names, true, true);
1177 }
1178 
1179 /* General expansion. Some of this file (the brace-expansion
1180  code from bash) is covered by the GPL; this is the only GPL-covered
1181  code in kpathsea. The part of the file that I wrote (the first
1182  couple of functions) is covered by the LGPL. */
1183 
1184 /* If NAME has a leading ~ or ~user, Unix-style, expand it to the user's
1185  home directory, and return a new malloced string. If no ~, or no
1186  <pwd.h>, just return NAME. */
1187 
1188 static std::string
1189 kpse_tilde_expand (const std::string& name)
1190 {
1191  std::string expansion;
1192 
1193  /* If no leading tilde, do nothing. */
1194  if (name.empty () || name[0] != '~')
1195  {
1196  expansion = name;
1197 
1198  /* If a bare tilde, return the home directory or '.'. (Very
1199  unlikely that the directory name will do anyone any good, but
1200  ... */
1201  }
1202  else if (name.length () == 1)
1203  {
1204  expansion = octave_env::get_home_directory ();
1205 
1206  if (expansion.empty ())
1207  expansion = ".";
1208 
1209  /* If '~/', remove any trailing / or replace leading // in $HOME.
1210  Should really check for doubled intermediate slashes, too. */
1211  }
1212  else if (IS_DIR_SEP (name[1]))
1213  {
1214  unsigned c = 1;
1215  std::string home = octave_env::get_home_directory ();
1216 
1217  if (home.empty ())
1218  home = ".";
1219 
1220  size_t home_len = home.length ();
1221 
1222  /* handle leading // */
1223  if (home_len > 1 && IS_DIR_SEP (home[0]) && IS_DIR_SEP (home[1]))
1224  home = home.substr (1);
1225 
1226  /* omit / after ~ */
1227  if (IS_DIR_SEP (home[home_len - 1]))
1228  c++;
1229 
1230  expansion = home + name.substr (c);
1231 
1232  /* If '~user' or '~user/', look up user in the passwd database (but
1233  OS/2 doesn't have this concept. */
1234  }
1235  else
1236 #ifdef HAVE_PWD_H
1237  {
1238  unsigned c = 2;
1239 
1240  /* find user name */
1241  while (name.length () > c && ! IS_DIR_SEP (name[c]))
1242  c++;
1243 
1244  std::string user = name.substr (1, c-1);
1245 
1246  /* We only need the cast here for (deficient) systems
1247  which do not declare 'getpwnam' in <pwd.h>. */
1249 
1250  /* If no such user, just use '.'. */
1251  std::string home = p ? p.dir () : std::string (".");
1252 
1253  if (home.empty ())
1254  home = ".";
1255 
1256  /* handle leading // */
1257  if (home.length () > 1 && IS_DIR_SEP (home[0]) && IS_DIR_SEP (home[1]))
1258  home = home.substr (1);
1259 
1260  /* If HOME ends in /, omit the / after ~user. */
1261  if (name.length () > c && IS_DIR_SEP (home[home.length () - 1]))
1262  c++;
1263 
1264  expansion = name.length () > c ? home : home + name.substr (c);
1265  }
1266 #else /* not HAVE_PWD_H */
1267  expansion = name;
1268 #endif /* not HAVE_PWD_H */
1269 
1270  return expansion;
1271 }
1272 
1273 /* Do variable expansion first so ~${USER} works. (Besides, it's what the
1274  shells do.) */
1275 
1276 /* Call kpse_var_expand and kpse_tilde_expand (in that order). Result
1277  is always in fresh memory, even if no expansions were done. */
1278 
1279 static std::string
1280 kpse_expand (const std::string& s)
1281 {
1282  std::string var_expansion = kpse_var_expand (s);
1283  return kpse_tilde_expand (var_expansion);
1284 }
1285 
1286 /* Forward declarations of functions from the original expand.c */
1287 static string_vector brace_expand (const std::string&);
1288 
1289 /* If $KPSE_DOT is defined in the environment, prepend it to any relative
1290  path components. */
1291 
1292 static std::string
1293 kpse_expand_kpse_dot (const std::string& path)
1294 {
1295  std::string ret;
1296  std::string kpse_dot = octave_env::getenv ("KPSE_DOT");
1297 
1298  if (kpse_dot.empty ())
1299  return path;
1300 
1301  for (kpse_path_iterator pi (path); pi != std::string::npos; pi++)
1302  {
1303  std::string elt = *pi;
1304 
1305  /* We assume that the !! magic is only used on absolute components.
1306  Single "." get special treatment, as does "./" or its equivalent. */
1307 
1308  size_t elt_len = elt.length ();
1309 
1310  if (kpse_absolute_p (elt, false)
1311  || (elt_len > 1 && elt[0] == '!' && elt[1] == '!'))
1312  ret += elt + ENV_SEP_STRING;
1313  else if (elt_len == 1 && elt[0] == '.')
1314  ret += kpse_dot + ENV_SEP_STRING;
1315  else if (elt_len > 1 && elt[0] == '.' && IS_DIR_SEP (elt[1]))
1316  ret += kpse_dot + elt.substr (1) + ENV_SEP_STRING;
1317  else
1318  ret += kpse_dot + DIR_SEP_STRING + elt + ENV_SEP_STRING;
1319  }
1320 
1321  int len = ret.length ();
1322  if (len > 0)
1323  ret.resize (len-1);
1324 
1325  return ret;
1326 }
1327 
1328 /* Do brace expansion on ELT; then do variable and ~ expansion on each
1329  element of the result; then do brace expansion again, in case a
1330  variable definition contained braces (e.g., $TEXMF). Return a
1331  string comprising all of the results separated by ENV_SEP_STRING. */
1332 
1333 static std::string
1334 kpse_brace_expand_element (const std::string& elt)
1335 {
1336  std::string ret;
1337 
1339 
1340  for (int i = 0; i < expansions.length (); i++)
1341  {
1342  /* Do $ and ~ expansion on each element. */
1343  std::string x = kpse_expand (expansions[i]);
1344 
1345  if (x != expansions[i])
1346  {
1347  /* If we did any expansions, do brace expansion again. Since
1348  recursive variable definitions are not allowed, this recursion
1349  must terminate. (In practice, it's unlikely there will ever be
1350  more than one level of recursion.) */
1351  x = kpse_brace_expand_element (x);
1352  }
1353 
1354  ret += x + ENV_SEP_STRING;
1355  }
1356 
1357  ret.resize (ret.length () - 1);
1358 
1359  return ret;
1360 }
1361 
1362 /* Do brace expansion and call 'kpse_expand' on each element of the
1363  result; return the final expansion (always in fresh memory, even if
1364  no expansions were done). We don't call 'kpse_expand_default'
1365  because there is a whole sequence of defaults to run through; see
1366  'kpse_init_format'. */
1367 
1368 static std::string
1369 kpse_brace_expand (const std::string& path)
1370 {
1371  /* Must do variable expansion first because if we have
1372  foo = .:~
1373  TEXINPUTS = $foo
1374  we want to end up with TEXINPUTS = .:/home/karl.
1375  Since kpse_path_element is not reentrant, we must get all
1376  the path elements before we start the loop. */
1377  std::string tmp = kpse_var_expand (path);
1378 
1379  std::string ret;
1380 
1381  for (kpse_path_iterator pi (tmp); pi != std::string::npos; pi++)
1382  {
1383  std::string elt = *pi;
1384 
1385  /* Do brace expansion first, so tilde expansion happens in {~ka,~kb}. */
1386  std::string expansion = kpse_brace_expand_element (elt);
1387  ret += expansion + ENV_SEP_STRING;
1388  }
1389 
1390  size_t len = ret.length ();
1391  if (len > 0)
1392  ret.resize (len-1);
1393 
1394  return kpse_expand_kpse_dot (ret);
1395 }
1396 
1397 /* Expand all special constructs in a path, and include only the actually
1398  existing directories in the result. */
1399 
1400 /* Do brace expansion and call 'kpse_expand' on each argument of the
1401  result, then expand any '//' constructs. The final expansion (always
1402  in fresh memory) is a path of all the existing directories that match
1403  the pattern. */
1404 
1405 static std::string
1406 kpse_path_expand (const std::string& path)
1407 {
1408  std::string ret;
1409  unsigned len;
1410 
1411  len = 0;
1412 
1413  /* Expand variables and braces first. */
1414  std::string tmp = kpse_brace_expand (path);
1415 
1416  /* Now expand each of the path elements, printing the results */
1417  for (kpse_path_iterator pi (tmp); pi != std::string::npos; pi++)
1418  {
1419  std::string elt = *pi;
1420 
1421  str_llist_type *dirs;
1422 
1423  /* Skip and ignore magic leading chars. */
1424  if (elt.length () > 1 && elt[0] == '!' && elt[1] == '!')
1425  elt = elt.substr (2);
1426 
1427  /* Do not touch the device if present */
1428  if (NAME_BEGINS_WITH_DEVICE (elt))
1429  {
1430  while (elt.length () > 3
1431  && IS_DIR_SEP (elt[2]) && IS_DIR_SEP (elt[3]))
1432  {
1433  elt[2] = elt[1];
1434  elt[1] = elt[0];
1435  elt = elt.substr (1);
1436  }
1437  }
1438  else
1439  {
1440  /* We never want to search the whole disk. */
1441  while (elt.length () > 1
1442  && IS_DIR_SEP (elt[0]) && IS_DIR_SEP (elt[1]))
1443  elt = elt.substr (1);
1444  }
1445 
1446  /* Search the disk for all dirs in the component specified.
1447  Be faster to check the database, but this is more reliable. */
1448  dirs = kpse_element_dirs (elt);
1449 
1450  if (dirs && *dirs)
1451  {
1452  str_llist_elt_type *dir;
1453 
1454  for (dir = *dirs; dir; dir = STR_LLIST_NEXT (*dir))
1455  {
1456  const std::string thedir = STR_LLIST (*dir);
1457  unsigned dirlen = thedir.length ();
1458 
1459  ret += thedir;
1460  len += dirlen;
1461 
1462  /* Retain trailing slash if that's the root directory. */
1463  if (dirlen == 1
1464  || (dirlen == 3 && NAME_BEGINS_WITH_DEVICE (thedir)
1465  && IS_DIR_SEP (thedir[2])))
1466  {
1467  ret += ENV_SEP_STRING;
1468  len++;
1469  }
1470 
1471  ret[len-1] = ENV_SEP;
1472  }
1473  }
1474  }
1475 
1476  if (len > 0)
1477  ret.resize (len-1);
1478 
1479  return ret;
1480 }
1481 
1482 /* braces.c -- code for doing word expansion in curly braces. Taken from
1483  bash 1.14.5. [And subsequently modified for kpatshea.]
1484 
1485  Copyright (C) 1987,1991 Free Software Foundation, Inc. */
1486 
1487 #define brace_whitespace(c) (! (c) || (c) == ' ' || (c) == '\t' || (c) == '\n')
1488 
1489 /* Basic idea:
1490 
1491  Segregate the text into 3 sections: preamble (stuff before an open brace),
1492  postamble (stuff after the matching close brace) and amble (stuff after
1493  preamble, and before postamble). Expand amble, and then tack on the
1494  expansions to preamble. Expand postamble, and tack on the expansions to
1495  the result so far. */
1496 
1497 /* Return a new array of strings which is the result of appending each
1498  string in ARR2 to each string in ARR1. The resultant array is
1499  len (arr1) * len (arr2) long. For convenience, ARR1 (and its contents)
1500  are free ()'ed. ARR1 can be NULL, in that case, a new version of ARR2
1501  is returned. */
1502 
1503 static string_vector
1504 array_concat (const string_vector& arr1, const string_vector& arr2)
1505 {
1506  string_vector result;
1507 
1508  if (arr1.empty ())
1509  result = arr2;
1510  else if (arr2.empty ())
1511  result = arr1;
1512  else
1513  {
1514  int len1 = arr1.length ();
1515  int len2 = arr2.length ();
1516 
1517  result = string_vector (len1 * len2);
1518 
1519  int k = 0;
1520  for (int i = 0; i < len2; i++)
1521  for (int j = 0; j < len1; j++)
1522  result[k++] = arr1[j] + arr2[i];
1523  }
1524 
1525  return result;
1526 }
1527 
1528 static int brace_gobbler (const std::string&, int&, int);
1529 static string_vector expand_amble (const std::string&);
1530 
1531 /* Return an array of strings; the brace expansion of TEXT. */
1532 static string_vector
1533 brace_expand (const std::string& text)
1534 {
1535  /* Find the text of the preamble. */
1536  int i = 0;
1537  int c = brace_gobbler (text, i, '{');
1538 
1539  std::string preamble = text.substr (0, i);
1540 
1541  string_vector result = string_vector (preamble);
1542 
1543  if (c == '{')
1544  {
1545  /* Find the amble. This is the stuff inside this set of braces. */
1546  int start = ++i;
1547  c = brace_gobbler (text, i, '}');
1548 
1549  /* What if there isn't a matching close brace? */
1550  if (! c)
1551  {
1552  (*current_liboctave_warning_with_id_handler)
1553  ("Octave:pathsearch-syntax",
1554  "%s: Unmatched {", text.c_str ());
1555 
1556  result = string_vector (text);
1557  }
1558  else
1559  {
1560  std::string amble = text.substr (start, i-start);
1561  result = array_concat (result, expand_amble (amble));
1562 
1563  std::string postamble = text.substr (i+1);
1564  result = array_concat (result, brace_expand (postamble));
1565  }
1566  }
1567 
1568  return result;
1569 }
1570 
1571 /* The character which is used to separate arguments. */
1572 static int brace_arg_separator = ',';
1573 
1574 /* Expand the text found inside of braces. We simply try to split the
1575  text at BRACE_ARG_SEPARATORs into separate strings. We then brace
1576  expand each slot which needs it, until there are no more slots which
1577  need it. */
1578 static string_vector
1579 expand_amble (const std::string& text)
1580 {
1581  string_vector result;
1582 
1583  size_t text_len = text.length ();
1584  size_t start;
1585  int i, c;
1586 
1587  for (start = 0, i = 0, c = 1; c && start < text_len; start = ++i)
1588  {
1589  int i0 = i;
1590  int c0 = brace_gobbler (text, i0, brace_arg_separator);
1591  int i1 = i;
1592  int c1 = brace_gobbler (text, i1, ENV_SEP);
1593  c = c0 | c1;
1594  i = (i0 < i1 ? i0 : i1);
1595 
1596  std::string tem = text.substr (start, i-start);
1597 
1598  string_vector partial = brace_expand (tem);
1599 
1600  if (result.empty ())
1601  result = partial;
1602  else
1603  result.append (partial);
1604  }
1605 
1606  return result;
1607 }
1608 
1609 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
1610  index of the character matching SATISFY. This understands about
1611  quoting. Return the character that caused us to stop searching;
1612  this is either the same as SATISFY, or 0. */
1613 static int
1614 brace_gobbler (const std::string& text, int& indx, int satisfy)
1615 {
1616  int c = 0;
1617  int level = 0;
1618  int quoted = 0;
1619  int pass_next = 0;
1620 
1621  size_t text_len = text.length ();
1622 
1623  size_t i = indx;
1624 
1625  for (; i < text_len; i++)
1626  {
1627  c = text[i];
1628 
1629  if (pass_next)
1630  {
1631  pass_next = 0;
1632  continue;
1633  }
1634 
1635  /* A backslash escapes the next character. This allows backslash to
1636  escape the quote character in a double-quoted string. */
1637  if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
1638  {
1639  pass_next = 1;
1640  continue;
1641  }
1642 
1643  if (quoted)
1644  {
1645  if (c == quoted)
1646  quoted = 0;
1647  continue;
1648  }
1649 
1650  if (c == '"' || c == '\'' || c == '`')
1651  {
1652  quoted = c;
1653  continue;
1654  }
1655 
1656  if (c == satisfy && !level && !quoted)
1657  {
1658  /* We ignore an open brace surrounded by whitespace, and also
1659  an open brace followed immediately by a close brace, that
1660  was preceded with whitespace. */
1661  if (c == '{'
1662  && ((i == 0 || brace_whitespace (text[i-1]))
1663  && (i+1 < text_len
1664  && (brace_whitespace (text[i+1]) || text[i+1] == '}'))))
1665  continue;
1666  /* If this is being compiled as part of bash, ignore the '{'
1667  in a '${ }' construct */
1668  if ((c != '{') || i == 0 || (text[i-1] != '$'))
1669  break;
1670  }
1671 
1672  if (c == '{')
1673  level++;
1674  else if (c == '}' && level)
1675  level--;
1676  }
1677 
1678  indx = i;
1679  return c;
1680 }
1681 
1682 /* For each file format, we record the following information. The main
1683  thing that is not part of this structure is the environment variable
1684  lists. They are used directly in tex-file.c. We could incorporate
1685  them here, but it would complicate the code a bit. We could also do
1686  it via variable expansion, but not now, maybe not ever:
1687  ${PKFONTS-${TEXFONTS-/usr/local/lib/texmf/fonts//}}. */
1688 
1690 {
1692  : type (), path (), raw_path (), path_source (), override_path (),
1693  client_path (), cnf_path (), default_path (), suffix ()
1694  { }
1695 
1697 
1698  std::string type; /* Human-readable description. */
1699  std::string path; /* The search path to use. */
1700  std::string raw_path; /* Pre-$~ (but post-default) expansion. */
1701  std::string path_source; /* Where the path started from. */
1702  std::string override_path; /* From client environment variable. */
1703  std::string client_path; /* E.g., from dvips's config.ps. */
1704  std::string cnf_path; /* From texmf.cnf. */
1705  std::string default_path; /* If all else fails. */
1706  string_vector suffix; /* For kpse_find_file to check for/append. */
1707 };
1708 
1709 /* The sole variable of that type, indexed by 'kpse_file_format_type'.
1710  Initialized by calls to 'kpse_find_file' for 'kpse_init_format'. */
1712 
1713 /* And EXPAND_DEFAULT calls kpse_expand_default on try_path and the
1714  present info->path. */
1715 #define EXPAND_DEFAULT(try_path, source_string) \
1716  do \
1717  { \
1718  if (! try_path.empty ()) \
1719  { \
1720  info.raw_path = try_path; \
1721  info.path = kpse_expand_default (try_path, info.path); \
1722  info.path_source = source_string; \
1723  } \
1724  } \
1725  while (0)
1726 
1727 static hash_table_type db; /* The hash table for all the ls-R's. */
1728 
1730 
1732 
1733 /* Return true if FILENAME could be in PATH_ELT, i.e., if the directory
1734  part of FILENAME matches PATH_ELT. Have to consider // wildcards, but
1735  $ and ~ expansion have already been done. */
1736 
1737 static bool
1738 match (const std::string& filename_arg, const std::string& path_elt_arg)
1739 {
1740  const char *filename = filename_arg.c_str ();
1741  const char *path_elt = path_elt_arg.c_str ();
1742 
1743  const char *original_filename = filename;
1744  bool matched = false;
1745 
1746  for (; *filename && *path_elt; filename++, path_elt++)
1747  {
1748  if (*filename == *path_elt) /* normal character match */
1749  ;
1750 
1751  else if (IS_DIR_SEP (*path_elt) /* at // */
1752  && original_filename < filename && IS_DIR_SEP (path_elt[-1]))
1753  {
1754  while (IS_DIR_SEP (*path_elt))
1755  path_elt++; /* get past second and any subsequent /'s */
1756 
1757  if (*path_elt == 0)
1758  {
1759  /* Trailing //, matches anything. We could make this
1760  part of the other case, but it seems pointless to do
1761  the extra work. */
1762  matched = true;
1763  break;
1764  }
1765  else
1766  {
1767  /* Intermediate //, have to match rest of PATH_ELT. */
1768  for (; !matched && *filename; filename++)
1769  {
1770  /* Try matching at each possible character. */
1771  if (IS_DIR_SEP (filename[-1]) && *filename == *path_elt)
1772  matched = match (filename, path_elt);
1773  }
1774 
1775  /* Prevent filename++ when *filename='\0'. */
1776  break;
1777  }
1778  }
1779  else
1780  /* normal character nonmatch, quit */
1781  break;
1782  }
1783 
1784  /* If we've reached the end of PATH_ELT, check that we're at the last
1785  component of FILENAME, we've matched. */
1786  if (! matched && *path_elt == 0)
1787  {
1788  /* Probably PATH_ELT ended with 'vf' or some such, and FILENAME
1789  ends with 'vf/ptmr.vf'. In that case, we'll be at a
1790  directory separator. On the other hand, if PATH_ELT ended
1791  with a / (as in 'vf/'), FILENAME being the same 'vf/ptmr.vf',
1792  we'll be at the 'p'. Upshot: if we're at a dir separator in
1793  FILENAME, skip it. But if not, that's ok, as long as there
1794  are no more dir separators. */
1795 
1796  if (IS_DIR_SEP (*filename))
1797  filename++;
1798 
1799  while (*filename && !IS_DIR_SEP (*filename))
1800  filename++;
1801 
1802  matched = *filename == 0;
1803  }
1804 
1805  return matched;
1806 }
1807 
1808 /* If DB_DIR is a prefix of PATH_ELT, return true; otherwise false.
1809  That is, the question is whether to try the db for a file looked up
1810  in PATH_ELT. If PATH_ELT == ".", for example, the answer is no. If
1811  PATH_ELT == "/usr/local/lib/texmf/fonts//tfm", the answer is yes.
1812 
1813  In practice, ls-R is only needed for lengthy subdirectory
1814  comparisons, but there's no gain to checking PATH_ELT to see if it is
1815  a subdir match, since the only way to do that is to do a string
1816  search in it, which is all we do anyway. */
1817 
1818 static bool
1819 elt_in_db (const std::string& db_dir, const std::string& path_elt)
1820 {
1821  bool found = false;
1822 
1823  size_t db_dir_len = db_dir.length ();
1824  size_t path_elt_len = path_elt.length ();
1825 
1826  size_t i = 0;
1827 
1828  while (! found && db_dir[i] == path_elt[i])
1829  {
1830  i++;
1831  /* If we've matched the entire db directory, it's good. */
1832  if (i == db_dir_len)
1833  found = true;
1834 
1835  /* If we've reached the end of PATH_ELT, but not the end of the db
1836  directory, it's no good. */
1837  else if (i == path_elt_len)
1838  break;
1839  }
1840 
1841  return found;
1842 }
1843 
1844 /* Avoid doing anything if this PATH_ELT is irrelevant to the databases. */
1845 
1846 /* Return list of matches for NAME in the ls-R file matching PATH_ELT. If
1847  ALL is set, return (null-terminated list) of all matches, else just
1848  the first. If no matches, return a pointer to an empty list. If no
1849  databases can be read, or PATH_ELT is not in any of the databases,
1850  return NULL. */
1851 
1852 static string_vector
1853 kpse_db_search (const std::string& name_arg,
1854  const std::string& orig_path_elt, bool all)
1855 {
1856  bool done;
1857  string_vector ret;
1858  string_vector aliases;
1859  bool relevant = false;
1860 
1861  std::string name = name_arg;
1862 
1863  /* If we failed to build the database (or if this is the recursive
1864  call to build the db path), quit. */
1865  if (! db.buckets)
1866  return ret;
1867 
1868  /* When tex-glyph.c calls us looking for, e.g., dpi600/cmr10.pk, we
1869  won't find it unless we change NAME to just 'cmr10.pk' and append
1870  '/dpi600' to PATH_ELT. We are justified in using a literal '/'
1871  here, since that's what tex-glyph.c unconditionally uses in
1872  DPI_BITMAP_SPEC. But don't do anything if the / begins NAME; that
1873  should never happen. */
1874  std::string path_elt;
1875  size_t last_slash = name.rfind ('/');
1876  if (last_slash != std::string::npos && last_slash != 0)
1877  {
1878  std::string dir_part = name.substr (0, last_slash);
1879  name = name.substr (last_slash + 1);
1880  }
1881  else
1882  path_elt = orig_path_elt;
1883 
1884  /* Don't bother doing any lookups if this 'path_elt' isn't covered by
1885  any of database directories. We do this not so much because the
1886  extra couple of hash lookups matter -- they don't -- but rather
1887  because we want to return NULL in this case, so path_search can
1888  know to do a disk search. */
1889  for (int e = 0; ! relevant && e < db_dir_list.length (); e++)
1890  relevant = elt_in_db (db_dir_list[e], path_elt);
1891 
1892  if (! relevant)
1893  return ret;
1894 
1895  /* If we have aliases for this name, use them. */
1896  if (alias_db.buckets)
1897  aliases = hash_lookup (alias_db, name);
1898 
1899  /* Push aliases up by one and insert the original name at the front. */
1900  int len = aliases.length ();
1901  aliases.resize (len+1);
1902  for (int i = len; i > 0; i--)
1903  aliases[i] = aliases[i - 1];
1904  aliases[0] = name;
1905 
1906  done = false;
1907  len = aliases.length ();
1908  for (int i = 0; i < len && !done; i++)
1909  {
1910  std::string atry = aliases[i];
1911 
1912  /* We have an ls-R db. Look up 'atry'. */
1913  string_vector db_dirs = hash_lookup (db, atry);
1914 
1915  /* For each filename found, see if it matches the path element. For
1916  example, if we have .../cx/cmr10.300pk and .../ricoh/cmr10.300pk,
1917  and the path looks like .../cx, we don't want the ricoh file. */
1918 
1919  int db_dirs_len = db_dirs.length ();
1920  for (int j = 0; j < db_dirs_len && !done; j++)
1921  {
1922  std::string db_file = db_dirs[j] + atry;
1923  bool matched = match (db_file, path_elt);
1924 
1925 #ifdef KPSE_DEBUG
1927  DEBUGF3 ("db:match (%s,%s) = %d\n",
1928  db_file.c_str (), path_elt.c_str (), matched);
1929 #endif
1930 
1931  /* We got a hit in the database. Now see if the file actually
1932  exists, possibly under an alias. */
1933  if (matched)
1934  {
1935  std::string found;
1936  std::string tmp = kpse_readable_file (db_file);
1937  if (! tmp.empty ())
1938  found = db_file;
1939  else
1940  {
1941  /* The hit in the DB doesn't exist in disk. Now try
1942  all its aliases. For example, suppose we have a
1943  hierarchy on CD, thus 'mf.bas', but ls-R contains
1944  'mf.base'. Find it anyway. Could probably work
1945  around this with aliases, but this is pretty easy
1946  and shouldn't hurt. The upshot is that if one of
1947  the aliases actually exists, we use that. */
1948 
1949  int aliases_len = aliases.length ();
1950 
1951  for (int k = 1; k < aliases_len && found.empty (); k++)
1952  {
1953  std::string aatry = db_dirs[j] + aliases[k];
1954  tmp = kpse_readable_file (aatry);
1955  if (! tmp.empty ())
1956  found = aatry;
1957  }
1958  }
1959 
1960  /* If we have a real file, add it to the list, maybe done. */
1961  if (! found.empty ())
1962  {
1963  ret.append (found);
1964 
1965  if (! (all || found.empty ()))
1966  done = true;
1967  }
1968  }
1969  }
1970  }
1971 
1972  return ret;
1973 }
1974 
1975 /* Expand extra colons. */
1976 
1977 /* Check for leading colon first, then trailing, then doubled, since
1978  that is fastest. Usually it will be leading or trailing. */
1979 
1980 /* Replace a leading or trailing or doubled : in PATH with DFLT. If
1981  no extra colons, return PATH. Only one extra colon is replaced.
1982  DFLT may not be NULL. */
1983 
1984 static std::string
1985 kpse_expand_default (const std::string& path, const std::string& fallback)
1986 {
1987  std::string expansion;
1988 
1989  size_t path_len = path.length ();
1990 
1991  if (path_len == 0)
1992  expansion = fallback;
1993 
1994  /* Solitary or leading :? */
1995  else if (IS_ENV_SEP (path[0]))
1996  {
1997  expansion = path_len == 1 ? fallback : fallback + path;
1998  }
1999 
2000  /* Sorry about the assignment in the middle of the expression, but
2001  conventions were made to be flouted and all that. I don't see the
2002  point of calling strlen twice or complicating the logic just to
2003  avoid the assignment (especially now that I've pointed it out at
2004  such great length). */
2005  else if (IS_ENV_SEP (path[path_len-1]))
2006  expansion = path + fallback;
2007 
2008  /* OK, not leading or trailing. Check for doubled. */
2009  else
2010  {
2011  /* What we'll return if we find none. */
2012  expansion = path;
2013 
2014  for (size_t i = 0; i < path_len; i++)
2015  {
2016  if (i + 1 < path_len
2017  && IS_ENV_SEP (path[i]) && IS_ENV_SEP (path[i+1]))
2018  {
2019  /* We have a doubled colon. */
2020 
2021  /* Copy stuff up to and including the first colon. */
2022  /* Copy in FALLBACK, and then the rest of PATH. */
2023  expansion = path.substr (0, i+1) + fallback + path.substr (i+1);
2024 
2025  break;
2026  }
2027  }
2028  }
2029 
2030  return expansion;
2031 }
2032 
2033 /* Translate a path element to its corresponding director{y,ies}. */
2034 
2035 /* To avoid giving prototypes for all the routines and then their real
2036  definitions, we give all the subroutines first. The entry point is
2037  the last routine in the file. */
2038 
2039 /* Make a copy of DIR (unless it's null) and save it in L. Ensure that
2040  DIR ends with a DIR_SEP for the benefit of later searches. */
2041 
2042 static void
2043 dir_list_add (str_llist_type *l, const std::string& dir)
2044 {
2045  char last_char = dir[dir.length () - 1];
2046 
2047  std::string saved_dir = dir;
2048 
2049  if (! (IS_DIR_SEP (last_char) || IS_DEVICE_SEP (last_char)))
2050  saved_dir += DIR_SEP_STRING;
2051 
2052  str_llist_add (l, saved_dir);
2053 }
2054 
2055 /* Return true if FN is a directory or a symlink to a directory,
2056  false if not. */
2057 
2058 static bool
2059 dir_p (const std::string& fn)
2060 {
2061 #ifdef WIN32
2062  unsigned int fa = GetFileAttributes (fn.c_str ());
2063  return (fa != 0xFFFFFFFF && (fa & FILE_ATTRIBUTE_DIRECTORY));
2064 #else
2065  struct stat stats;
2066  return stat (fn.c_str (), &stats) == 0 && S_ISDIR (stats.st_mode);
2067 #endif
2068 }
2069 
2070 /* If DIR is a directory, add it to the list L. */
2071 
2072 static void
2073 checked_dir_list_add (str_llist_type *l, const std::string& dir)
2074 {
2075  if (dir_p (dir))
2076  dir_list_add (l, dir);
2077 }
2078 
2079 /* The cache. Typically, several paths have the same element; for
2080  example, /usr/local/lib/texmf/fonts//. We don't want to compute the
2081  expansion of such a thing more than once. Even though we also cache
2082  the dir_links call, that's not enough -- without this path element
2083  caching as well, the execution time doubles. */
2084 
2086 {
2087  cache_entry (void) : key (), value (0) { }
2088 
2089  ~cache_entry (void) { }
2090 
2091  std::string key;
2093 };
2094 
2096 static unsigned cache_length = 0;
2097 
2098 /* Associate KEY with VALUE. We implement the cache as a simple linear
2099  list, since it's unlikely to ever be more than a dozen or so elements
2100  long. We don't bother to check here if PATH has already been saved;
2101  we always add it to our list. We copy KEY but not VALUE; not sure
2102  that's right, but it seems to be all that's needed. */
2103 
2104 static void
2105 cache (const std::string key, str_llist_type *value)
2106 {
2107  cache_entry *new_cache = new cache_entry [cache_length+1];
2108 
2109  for (unsigned i = 0; i < cache_length; i++)
2110  {
2111  new_cache[i].key = the_cache[i].key;
2112  new_cache[i].value = the_cache[i].value;
2113  }
2114 
2115  delete [] the_cache;
2116 
2117  the_cache = new_cache;
2118 
2119  the_cache[cache_length].key = key;
2120  the_cache[cache_length].value = value;
2121 
2122  cache_length++;
2123 }
2124 
2125 /* To retrieve, just check the list in order. */
2126 
2127 static str_llist_type *
2128 cached (const std::string& key)
2129 {
2130  unsigned p;
2131 
2132  for (p = 0; p < cache_length; p++)
2133  {
2134  if (key == the_cache[p].key)
2135  return the_cache[p].value;
2136  }
2137 
2138  return 0;
2139 }
2140 
2141 /* Handle the magic path constructs. */
2142 
2143 /* Declare recursively called routine. */
2144 static void expand_elt (str_llist_type *, const std::string&, unsigned);
2145 
2146 /* POST is a pointer into the original element (which may no longer be
2147  ELT) to just after the doubled DIR_SEP, perhaps to the null. Append
2148  subdirectories of ELT (up to ELT_LENGTH, which must be a /) to
2149  STR_LIST_PTR. */
2150 
2151 #ifdef WIN32
2152 
2153 /* Shared across recursive calls, it acts like a stack. */
2154 static std::string dirname;
2155 
2156 #else /* WIN32 */
2157 
2158 /* Return -1 if FN isn't a directory, else its number of links.
2159  Duplicate the call to stat; no need to incur overhead of a function
2160  call for that little bit of cleanliness. */
2161 
2162 static int
2163 dir_links (const std::string& fn)
2164 {
2165  std::map<std::string, long> link_table;
2166 
2167  long ret;
2168 
2169  if (link_table.find (fn) != link_table.end ())
2170  ret = link_table[fn];
2171  else
2172  {
2173  struct stat stats;
2174 
2175  ret = stat (fn.c_str (), &stats) == 0 && S_ISDIR (stats.st_mode)
2176  ? stats.st_nlink : static_cast<unsigned> (-1);
2177 
2178  link_table[fn] = ret;
2179 
2180 #ifdef KPSE_DEBUG
2182  DEBUGF2 ("dir_links (%s) => %ld\n", fn.c_str (), ret);
2183 #endif
2184  }
2185 
2186  return ret;
2187 }
2188 
2189 #endif /* WIN32 */
2190 
2191 static void
2192 do_subdir (str_llist_type *str_list_ptr, const std::string& elt,
2193  unsigned elt_length, const std::string& post)
2194 {
2195 #ifdef WIN32
2196  WIN32_FIND_DATA find_file_data;
2197  HANDLE hnd;
2198  int proceed;
2199 #else
2200  DIR *dir;
2201  struct dirent *e;
2202 #endif /* not WIN32 */
2203 
2204  std::string name = elt.substr (0, elt_length);
2205 
2206  assert (IS_DIR_SEP (elt[elt_length - 1])
2207  || IS_DEVICE_SEP (elt[elt_length - 1]));
2208 
2209 #if defined (WIN32)
2210 
2211  dirname = name + "/*.*"; /* "*.*" or "*" -- seems equivalent. */
2212 
2213  hnd = FindFirstFile (dirname.c_str (), &find_file_data);
2214 
2215  if (hnd == INVALID_HANDLE_VALUE)
2216  return;
2217 
2218  /* Include top level before subdirectories, if nothing to match. */
2219  if (post.empty ())
2220  dir_list_add (str_list_ptr, name);
2221  else
2222  {
2223  /* If we do have something to match, see if it exists. For
2224  example, POST might be 'pk/ljfour', and they might have a
2225  directory '$TEXMF/fonts/pk/ljfour' that we should find. */
2226  name += post;
2227  expand_elt (str_list_ptr, name, elt_length);
2228  name.resize (elt_length);
2229  }
2230 
2231  proceed = 1;
2232 
2233  while (proceed)
2234  {
2235  if (find_file_data.cFileName[0] != '.')
2236  {
2237  /* Construct the potential subdirectory name. */
2238  name += find_file_data.cFileName;
2239 
2240  if (find_file_data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
2241  {
2242  /* It's a directory, so append the separator. */
2243  name += DIR_SEP_STRING;
2244  unsigned potential_len = name.length ();
2245 
2246  do_subdir (str_list_ptr, name, potential_len, post);
2247  }
2248  name.resize (elt_length);
2249  }
2250 
2251  proceed = FindNextFile (hnd, &find_file_data);
2252  }
2253 
2254  FindClose (hnd);
2255 
2256 #else /* not WIN32 */
2257 
2258  /* If we can't open it, quit. */
2259  dir = gnulib::opendir (name.c_str ());
2260 
2261  if (! dir)
2262  return;
2263 
2264  /* Include top level before subdirectories, if nothing to match. */
2265  if (post.empty ())
2266  dir_list_add (str_list_ptr, name);
2267  else
2268  {
2269  /* If we do have something to match, see if it exists. For
2270  example, POST might be 'pk/ljfour', and they might have a
2271  directory '$TEXMF/fonts/pk/ljfour' that we should find. */
2272  name += post;
2273  expand_elt (str_list_ptr, name, elt_length);
2274  name.resize (elt_length);
2275  }
2276 
2277  while ((e = gnulib::readdir (dir)))
2278  {
2279  /* If it begins with a '.', never mind. (This allows "hidden"
2280  directories that the algorithm won't find.) */
2281 
2282  if (e->d_name[0] != '.')
2283  {
2284  int links;
2285 
2286  /* Construct the potential subdirectory name. */
2287  name += e->d_name;
2288 
2289  /* If we can't stat it, or if it isn't a directory, continue. */
2290  links = dir_links (name);
2291 
2292  if (links >= 0)
2293  {
2294  /* It's a directory, so append the separator. */
2295  name += DIR_SEP_STRING;
2296  unsigned potential_len = name.length ();
2297 
2298  /* Should we recurse? To see if the subdirectory is a
2299  leaf, check if it has two links (one for . and one for
2300  ..). This means that symbolic links to directories do
2301  not affect the leaf-ness. This is arguably wrong, but
2302  the only alternative I know of is to stat every entry
2303  in the directory, and that is unacceptably slow.
2304 
2305  The #ifdef here makes all this configurable at
2306  compile-time, so that if we're using VMS directories or
2307  some such, we can still find subdirectories, even if it
2308  is much slower. */
2309 #ifdef ST_NLINK_TRICK
2310  if (links != 2)
2311 #endif /* not ST_NLINK_TRICK */
2312  /* All criteria are met; find subdirectories. */
2313  do_subdir (str_list_ptr, name, potential_len, post);
2314 #ifdef ST_NLINK_TRICK
2315  else if (post.empty ())
2316  /* Nothing to match, no recursive subdirectories to
2317  look for: we're done with this branch. Add it. */
2318  dir_list_add (str_list_ptr, name);
2319 #endif
2320  }
2321 
2322  /* Remove the directory entry we just checked from 'name'. */
2323  name.resize (elt_length);
2324  }
2325  }
2326 
2327  xclosedir (dir);
2328 #endif /* not WIN32 */
2329 }
2330 
2331 /* Assume ELT is non-empty and non-NULL. Return list of corresponding
2332  directories (with no terminating NULL entry) in STR_LIST_PTR. Start
2333  looking for magic constructs at START. */
2334 
2335 static void
2336 expand_elt (str_llist_type *str_list_ptr, const std::string& elt,
2337  unsigned /* start */)
2338 {
2339 #if 0
2340  // We don't want magic constructs.
2341 
2342  size_t elt_len = elt.length ();
2343 
2344  size_t dir = start;
2345 
2346 
2347  while (dir < elt_len)
2348  {
2349  if (IS_DIR_SEP (elt[dir]))
2350  {
2351  /* If two or more consecutive /'s, find subdirectories. */
2352  if (++dir < elt_len && IS_DIR_SEP (elt[dir]))
2353  {
2354  size_t i = dir;
2355  while (i < elt_len && IS_DIR_SEP (elt[i]))
2356  i++;
2357 
2358  std::string post = elt.substr (i);
2359 
2360  do_subdir (str_list_ptr, elt, dir, post);
2361 
2362  return;
2363  }
2364 
2365  /* No special stuff at this slash. Keep going. */
2366  }
2367  else
2368  dir++;
2369  }
2370 #endif
2371 
2372  /* When we reach the end of ELT, it will be a normal filename. */
2373  checked_dir_list_add (str_list_ptr, elt);
2374 }
2375 
2376 /* Here is the entry point. Returns directory list for ELT. */
2377 
2378 /* Given a path element ELT, return a pointer to a NULL-terminated list
2379  of the corresponding (existing) directory or directories, with
2380  trailing slashes, or NULL. If ELT is the empty string, check the
2381  current working directory.
2382 
2383  It's up to the caller to expand ELT. This is because this routine is
2384  most likely only useful to be called from 'kpse_path_search', which
2385  has already assumed expansion has been done. */
2386 
2387 static str_llist_type *
2388 kpse_element_dirs (const std::string& elt)
2389 {
2390  str_llist_type *ret;
2391 
2392  /* If given nothing, return nothing. */
2393  if (elt.empty ())
2394  return 0;
2395 
2396  /* If we've already cached the answer for ELT, return it. */
2397  ret = cached (elt);
2398  if (ret)
2399  return ret;
2400 
2401  /* We're going to have a real directory list to return. */
2402  ret = new str_llist_type;
2403  *ret = 0;
2404 
2405  /* We handle the hard case in a subroutine. */
2406  expand_elt (ret, elt, 0);
2407 
2408  /* Remember the directory list we just found, in case future calls are
2409  made with the same ELT. */
2410  cache (elt, ret);
2411 
2412 #ifdef KPSE_DEBUG
2414  {
2415  DEBUGF1 ("path element %s =>", elt.c_str ());
2416  if (ret)
2417  {
2418  str_llist_elt_type *e;
2419  for (e = *ret; e; e = STR_LLIST_NEXT (*e))
2420  gnulib::fprintf (stderr, " %s", (STR_LLIST (*e)).c_str ());
2421  }
2422  gnulib::putc ('\n', stderr);
2423  gnulib::fflush (stderr);
2424  }
2425 #endif /* KPSE_DEBUG */
2426 
2427  return ret;
2428 }
2429 
2430 #ifndef WIN32
2431 void
2432 xclosedir (DIR *d)
2433 {
2434  int ret = gnulib::closedir (d);
2435 
2436  if (ret != 0)
2437  FATAL ("closedir failed");
2438 }
2439 #endif
2440 
2441 /* Implementation of a linked list of strings. */
2442 
2443 /* Add the new string STR to the end of the list L. */
2444 
2445 static void
2446 str_llist_add (str_llist_type *l, const std::string& str)
2447 {
2448  str_llist_elt_type *e;
2449  str_llist_elt_type *new_elt = new str_llist_elt_type;
2450 
2451  /* The new element will be at the end of the list. */
2452  STR_LLIST (*new_elt) = str;
2453  STR_LLIST_MOVED (*new_elt) = 0;
2454  STR_LLIST_NEXT (*new_elt) = 0;
2455 
2456  /* Find the current end of the list. */
2457  for (e = *l; e && STR_LLIST_NEXT (*e); e = STR_LLIST_NEXT (*e))
2458  ;
2459 
2460  if (! e)
2461  *l = new_elt;
2462  else
2463  STR_LLIST_NEXT (*e) = new_elt;
2464 }
2465 
2466 /* Move an element towards the top. The idea is that when a file is
2467  found in a given directory, later files will likely be in that same
2468  directory, and looking for the file in all the directories in between
2469  is thus a waste. */
2470 
2471 static void
2473 {
2474  str_llist_elt_type *last_moved, *unmoved;
2475 
2476  /* If we've already moved this element, never mind. */
2477  if (STR_LLIST_MOVED (*mover))
2478  return;
2479 
2480  /* Find the first unmoved element (to insert before). We're
2481  guaranteed this will terminate, since MOVER itself is currently
2482  unmoved, and it must be in L (by hypothesis). */
2483  for (last_moved = 0, unmoved = *l; STR_LLIST_MOVED (*unmoved);
2484  last_moved = unmoved, unmoved = STR_LLIST_NEXT (*unmoved))
2485  ;
2486 
2487  /* If we are the first unmoved element, nothing to relink. */
2488  if (unmoved != mover)
2489  {
2490  /* Remember 'mover's current successor, so we can relink 'mover's
2491  predecessor to it. */
2492  str_llist_elt_type *before_mover;
2493  str_llist_elt_type *after_mover = STR_LLIST_NEXT (*mover);
2494 
2495  /* Find 'mover's predecessor. */
2496  for (before_mover = unmoved; STR_LLIST_NEXT (*before_mover) != mover;
2497  before_mover = STR_LLIST_NEXT (*before_mover))
2498  ;
2499 
2500  /* 'before_mover' now links to 'after_mover'. */
2501  STR_LLIST_NEXT (*before_mover) = after_mover;
2502 
2503  /* Insert 'mover' before 'unmoved' and after 'last_moved' (or at
2504  the head of the list). */
2505  STR_LLIST_NEXT (*mover) = unmoved;
2506  if (! last_moved)
2507  *l = mover;
2508  else
2509  STR_LLIST_NEXT (*last_moved) = mover;
2510  }
2511 
2512  /* We've moved it. */
2513  STR_LLIST_MOVED (*mover) = 1;
2514 }
2515 
2516 /* Variable expansion. */
2517 
2518 /* We have to keep track of variables being expanded, otherwise
2519  constructs like TEXINPUTS = $TEXINPUTS result in an infinite loop.
2520  (Or indirectly recursive variables, etc.) Our simple solution is to
2521  add to a list each time an expansion is started, and check the list
2522  before expanding. */
2523 
2524 static std::map <std::string, bool> expansions;
2525 
2526 static void
2527 expanding (const std::string& var, bool xp)
2528 {
2529  expansions[var] = xp;
2530 }
2531 
2532 /* Return whether VAR is currently being expanding. */
2533 
2534 static bool
2535 expanding_p (const std::string& var)
2536 {
2537  return (expansions.find (var) != expansions.end ()) ? expansions[var] : false;
2538 }
2539 
2540 /* Append the result of value of 'var' to EXPANSION, where 'var' begins
2541  at START and ends at END. If 'var' is not set, do not complain.
2542  This is a subroutine for the more complicated expansion function. */
2543 
2544 static void
2545 expand (std::string &expansion, const std::string& var)
2546 {
2547  if (expanding_p (var))
2548  {
2549  (*current_liboctave_warning_with_id_handler)
2550  ("Octave:pathsearch-syntax",
2551  "kpathsea: variable '%s' references itself (eventually)",
2552  var.c_str ());
2553  }
2554  else
2555  {
2556  /* Check for an environment variable. */
2557  std::string value = octave_env::getenv (var);
2558 
2559  if (! value.empty ())
2560  {
2561  expanding (var, true);
2562  std::string tmp = kpse_var_expand (value);
2563  expanding (var, false);
2564  expansion += tmp;
2565  }
2566  }
2567 }
2568 
2569 /* Can't think of when it would be useful to change these (and the
2570  diagnostic messages assume them), but ... */
2571 #ifndef IS_VAR_START /* starts all variable references */
2572 #define IS_VAR_START(c) ((c) == '$')
2573 #endif
2574 #ifndef IS_VAR_CHAR /* variable name constituent */
2575 #define IS_VAR_CHAR(c) (isalnum (c) || (c) == '_')
2576 #endif
2577 #ifndef IS_VAR_BEGIN_DELIMITER /* start delimited variable name (after $) */
2578 #define IS_VAR_BEGIN_DELIMITER(c) ((c) == '{')
2579 #endif
2580 #ifndef IS_VAR_END_DELIMITER
2581 #define IS_VAR_END_DELIMITER(c) ((c) == '}')
2582 #endif
2583 
2584 /* Maybe we should support some or all of the various shell ${...}
2585  constructs, especially ${var-value}. */
2586 
2587 static std::string
2588 kpse_var_expand (const std::string& src)
2589 {
2590  std::string expansion;
2591 
2592  size_t src_len = src.length ();
2593 
2594  /* Copy everything but variable constructs. */
2595  for (size_t i = 0; i < src_len; i++)
2596  {
2597  if (IS_VAR_START (src[i]))
2598  {
2599  i++;
2600 
2601  /* Three cases: '$VAR', '${VAR}', '$<anything-else>'. */
2602  if (IS_VAR_CHAR (src[i]))
2603  {
2604  /* $V: collect name constituents, then expand. */
2605  size_t var_end = i;
2606 
2607  do
2608  {
2609  var_end++;
2610  }
2611  while (IS_VAR_CHAR (src[var_end]));
2612 
2613  var_end--; /* had to go one past */
2614  expand (expansion, src.substr (i, var_end - i + 1));
2615  i = var_end;
2616 
2617  }
2618  else if (IS_VAR_BEGIN_DELIMITER (src[i]))
2619  {
2620  /* ${: scan ahead for matching delimiter, then expand. */
2621  size_t var_end = ++i;
2622 
2623  while (var_end < src_len && !IS_VAR_END_DELIMITER (src[var_end]))
2624  var_end++;
2625 
2626  if (var_end == src_len)
2627  {
2628  (*current_liboctave_warning_with_id_handler)
2629  ("Octave:pathsearch-syntax",
2630  "%s: No matching } for ${", src.c_str ());
2631  i = var_end - 1; /* will incr to eos at top of loop */
2632  }
2633  else
2634  {
2635  expand (expansion, src.substr (i, var_end - i));
2636  i = var_end; /* will incr past } at top of loop*/
2637  }
2638  }
2639  else
2640  {
2641  /* $<something-else>: error. */
2642  (*current_liboctave_warning_with_id_handler)
2643  ("Octave:pathsearch-syntax",
2644  "%s: Unrecognized variable construct '$%c'",
2645  src.c_str (), src[i]);
2646 
2647  /* Just ignore those chars and keep going. */
2648  }
2649  }
2650  else
2651  expansion += src[i];
2652  }
2653 
2654  return expansion;
2655 }
#define KPSE_DEBUG_VARS
Definition: kpse.cc:213
int moved
Definition: kpse.cc:319
static void expand_elt(str_llist_type *, const std::string &, unsigned)
Definition: kpse.cc:2336
static void str_llist_float(str_llist_type *l, str_llist_elt_type *mover)
Definition: kpse.cc:2472
static string_vector kpse_all_path_search(const std::string &path, const std::string &name)
Definition: kpse.cc:952
#define IS_VAR_BEGIN_DELIMITER(c)
Definition: kpse.cc:2578
static void checked_dir_list_add(str_llist_type *l, const std::string &dir)
Definition: kpse.cc:2073
static hash_table_type db
Definition: kpse.cc:1727
static bool kpse_is_env_sep(char c)
Definition: kpse.cc:349
static std::string kpse_var_value(const std::string &var)
Definition: kpse.cc:516
str_llist_elt str_llist_elt_type
Definition: kpse.cc:323
const std::string & path
Definition: kpse.cc:471
std::string operator*(void)
Definition: kpse.cc:465
static string_vector find_first_of(const std::string &path, const string_vector &names, bool must_exist, bool all)
Definition: kpse.cc:1070
static bool READABLE(const std::string &fn, struct stat &st)
Definition: kpse.cc:585
#define DEBUGF4(str, e1, e2, e3, e4)
Definition: kpse.cc:228
std::string path
Definition: kpse.cc:1699
static bool dir_p(const std::string &fn)
Definition: kpse.cc:2059
static void xclosedir(DIR *d)
Definition: kpse.cc:2432
kpse_path_iterator & operator=(const kpse_path_iterator &)
#define ENV_SEP_STRING
Definition: kpse.cc:171
static string_vector dir_list_search(str_llist_type *dirs, const std::string &name, bool search_all)
Definition: kpse.cc:737
std::string cnf_path
Definition: kpse.cc:1704
static int brace_gobbler(const std::string &, int &, int)
Definition: kpse.cc:1614
#define KPSE_DEBUG_STAT
Definition: kpse.cc:207
static void expand(std::string &expansion, const std::string &var)
Definition: kpse.cc:2545
static std::string kpse_brace_expand_element(const std::string &elt)
Definition: kpse.cc:1334
#define ENV_SEP
Definition: kpse.cc:170
struct hash_element_type * next
Definition: kpse.cc:382
#define NAME_MAX
Definition: kpse.cc:156
static unsigned int kpathsea_debug
Definition: kpse.cc:234
bool empty(void) const
Definition: str-vec.h:73
#define DEBUGF2(str, e1, e2)
Definition: kpse.cc:224
#define brace_whitespace(c)
Definition: kpse.cc:1487
static string_vector path_find_first_of(const std::string &path, const string_vector &names, bool, bool all)
Definition: kpse.cc:962
unsigned size
Definition: kpse.cc:390
static bool expanding_p(const std::string &var)
Definition: kpse.cc:2535
static bool first_search
Definition: kpse.cc:676
#define IS_VAR_START(c)
Definition: kpse.cc:2572
static unsigned cache_length
Definition: kpse.cc:2096
static std::string kpse_readable_file(const std::string &name)
Definition: kpse.cc:600
kpse_path_iterator(const kpse_path_iterator &pi)
Definition: kpse.cc:455
Definition: kpse.cc:2085
static string_vector names(const map_type &lst)
Definition: help.cc:782
str_llist_elt(void)
Definition: kpse.cc:314
static str_llist_type * cached(const std::string &key)
Definition: kpse.cc:2128
static string_vector expand_amble(const std::string &)
Definition: kpse.cc:1579
static string_vector kpse_all_path_find_first_of(const std::string &path, const string_vector &names)
Definition: kpse.cc:1173
static string_vector search(const std::string &path, const std::string &original_name, bool must_exist, bool all)
Definition: kpse.cc:872
#define KPSE_DEBUG_SEARCH
Definition: kpse.cc:212
static std::map< std::string, bool > expansions
Definition: kpse.cc:2524
static string_vector path_search(const std::string &path, const std::string &name, bool, bool all)
Definition: kpse.cc:786
static string_vector kpse_db_search(const std::string &name, const std::string &path_elt, bool all)
Definition: kpse.cc:1853
static FILE * xfopen(const std::string &filename, const char *mode)
Definition: kpse.cc:358
static string_vector db_dir_list
Definition: kpse.cc:1731
hash_element_type ** buckets
Definition: kpse.cc:389
kpse_format_info_type(void)
Definition: kpse.cc:1691
static void dir_list_add(str_llist_type *l, const std::string &dir)
Definition: kpse.cc:2043
std::string dir(void) const
Definition: oct-passwd.cc:85
F77_RET_T const double const double double * d
~str_llist_elt(void)
Definition: kpse.cc:316
#define STR_LLIST_MOVED(sl)
Definition: kpse.cc:327
kpse_path_iterator operator++(int)
Definition: kpse.cc:458
void set_end(void)
Definition: kpse.cc:476
std::string path_source
Definition: kpse.cc:1701
static std::string kpse_path_find_first_of(const std::string &path, const string_vector &names, bool must_exist)
Definition: kpse.cc:1157
#define IS_VAR_CHAR(c)
Definition: kpse.cc:2575
static bool elt_in_db(const std::string &db_dir, const std::string &path_elt)
Definition: kpse.cc:1819
#define dirent
Definition: sysdir.h:37
static std::string kpse_expand_default(const std::string &path, const std::string &dflt)
Definition: kpse.cc:1985
#define STR_LLIST(sl)
Definition: kpse.cc:326
#define IS_DIR_SEP(ch)
Definition: kpse.cc:116
F77_RET_T const double const double * f
#define DEBUGF3(str, e1, e2, e3)
Definition: kpse.cc:226
#define KPSE_DEBUG_HASH
Definition: kpse.cc:208
static unsigned kpse_hash(hash_table_type table, const std::string &key)
Definition: kpse.cc:394
static void log_search(const string_vector &filenames)
Definition: kpse.cc:683
void resize(octave_idx_type n, const std::string &rfv=std::string())
Definition: str-vec.h:91
kpse_path_iterator(const std::string &p)
Definition: kpse.cc:452
#define KPSE_DEBUG_FOPEN
Definition: kpse.cc:209
#define FATAL(str)
Definition: kpse.cc:293
str_llist_type * value
Definition: kpse.cc:2092
static std::string getenv(const std::string &name)
Definition: oct-env.cc:238
string_vector & append(const std::string &s)
Definition: str-vec.cc:140
static std::string kpse_expand(const std::string &s)
Definition: kpse.cc:1280
struct str_llist_elt * next
Definition: kpse.cc:320
std::string override_path
Definition: kpse.cc:1702
string_vector suffix
Definition: kpse.cc:1706
str_llist_elt * str_llist_type
Definition: kpse.cc:324
std::string key
Definition: kpse.cc:2091
std::string key
Definition: kpse.cc:380
static void cache(const std::string key, str_llist_type *value)
Definition: kpse.cc:2105
static string_vector absolute_search(const std::string &name)
Definition: kpse.cc:770
#define DEBUGF1(str, e1)
Definition: kpse.cc:222
static std::string kpse_tilde_expand(const std::string &name)
Definition: kpse.cc:1189
void next(void)
Definition: kpse.cc:495
static hash_table_type alias_db
Definition: kpse.cc:1729
static str_llist_type * kpse_element_dirs(const std::string &elt)
Definition: kpse.cc:2388
#define KPSE_DEBUG_P(bit)
Definition: kpse.cc:205
~kpse_format_info_type(void)
Definition: kpse.cc:1696
static string_vector hash_lookup(hash_table_type table, const std::string &key)
Definition: kpse.cc:411
octave_idx_type length(void) const
Number of elements in the array.
Definition: Array.h:267
~cache_entry(void)
Definition: kpse.cc:2089
#define NAME_BEGINS_WITH_DEVICE(name)
Definition: kpse.cc:122
subroutine stat(x, n, av, var, xmin, xmax)
Definition: tstgmn.for:111
static int dir_links(const std::string &fn)
Definition: kpse.cc:2163
static cache_entry * the_cache
Definition: kpse.cc:2095
std::string type
Definition: kpse.cc:1698
cache_entry(void)
Definition: kpse.cc:2087
static int brace_arg_separator
Definition: kpse.cc:1572
static std::string kpse_var_expand(const std::string &src)
Definition: kpse.cc:2588
static string_vector brace_expand(const std::string &)
Definition: kpse.cc:1533
static string_vector array_concat(const string_vector &arr1, const string_vector &arr2)
Definition: kpse.cc:1504
#define STR_LLIST_NEXT(sl)
Definition: kpse.cc:328
#define DIR_SEP_STRING
Definition: kpse.cc:111
std::string default_path
Definition: kpse.cc:1705
std::string client_path
Definition: kpse.cc:1703
static void str_llist_add(str_llist_type *l, const std::string &str)
Definition: kpse.cc:2446
static std::string kpse_brace_expand(const std::string &path)
Definition: kpse.cc:1369
static kpse_format_info_type kpse_format_info
Definition: kpse.cc:1711
static std::string kpse_path_expand(const std::string &path)
Definition: kpse.cc:1406
static bool match(const std::string &filename_arg, const std::string &path_elt_arg)
Definition: kpse.cc:1738
static MArray< double > const octave_idx_type const octave_idx_type octave_idx_type octave_idx_type octave_idx_type c1
#define KPSE_DEBUG_EXPAND
Definition: kpse.cc:211
static std::string kpse_truncate_filename(const std::string &name)
Definition: kpse.cc:538
#define FATAL_PERROR(str)
Definition: kpse.cc:285
#define IS_VAR_END_DELIMITER(c)
Definition: kpse.cc:2581
static octave_passwd getpwnam(const std::string &nm)
Definition: oct-passwd.cc:141
bool operator!=(const size_t sz)
Definition: kpse.cc:467
std::string value
Definition: kpse.cc:381
static std::string kpse_expand_kpse_dot(const std::string &path)
Definition: kpse.cc:1293
static std::string kpse_path_search(const std::string &path, const std::string &name, bool must_exist)
Definition: kpse.cc:937
static void do_subdir(str_llist_type *str_list_ptr, const std::string &elt, unsigned elt_length, const std::string &post)
Definition: kpse.cc:2192
#define IS_DEVICE_SEP(ch)
Definition: kpse.cc:119
static void expanding(const std::string &var, bool xp)
Definition: kpse.cc:2527
std::string str
Definition: kpse.cc:318
std::string raw_path
Definition: kpse.cc:1700
F77_RET_T const double * x
static bool kpse_absolute_p(const std::string &filename, int relative_ok)
Definition: kpse.cc:645
static std::string get_home_directory(void)
Definition: oct-env.cc:146
#define IS_ENV_SEP(ch)
Definition: kpse.cc:176