1/*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
3 *
4 * All rights reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, and/or sell copies of the Software, and to permit persons
11 * to whom the Software is furnished to do so, provided that the above
12 * copyright notice(s) and this permission notice appear in all copies of
13 * the Software and that both the above copyright notice(s) and this
14 * permission notice appear in supporting documentation.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
19 * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
20 * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
21 * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
22 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
23 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
24 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
25 *
26 * Except as contained in this notice, the name of a copyright holder
27 * shall not be used in advertising or otherwise to promote the sale, use
28 * or other dealings in this Software without prior written authorization
29 * of the copyright holder.
30 */
31
32/*
33 * If file-system access is to be excluded, this module has no function,
34 * so all of its code should be excluded.
35 */
36#ifndef WITHOUT_FILE_SYSTEM
37
38#include <stdio.h>
39#include <stdlib.h>
40#include <string.h>
41#include <errno.h>
42
43#include "freelist.h"
44#include "direader.h"
45#include "pathutil.h"
46#include "homedir.h"
47#include "stringrp.h"
48#include "libtecla.h"
49#include "ioutil.h"
50#include "expand.h"
51#include "errmsg.h"
52
53/*
54 * Specify the number of elements to extend the files[] array by
55 * when it proves to be too small. This also sets the initial size
56 * of the array.
57 */
58#define MATCH_BLK_FACT 256
59
60/*
61 * A list of directory iterators is maintained using nodes of the
62 * following form.
63 */
64typedef struct DirNode DirNode;
65struct DirNode {
66  DirNode *next;       /* The next directory in the list */
67  DirNode *prev;       /* The node that precedes this node in the list */
68  DirReader *dr;       /* The directory reader object */
69};
70
71typedef struct {
72  FreeList *mem;       /* Memory for DirNode list nodes */
73  DirNode *head;       /* The head of the list of used and unused cache nodes */
74  DirNode *next;       /* The next unused node between head and tail */
75  DirNode *tail;       /* The tail of the list of unused cache nodes */
76} DirCache;
77
78/*
79 * Specify how many directory cache nodes to allocate at a time.
80 */
81#define DIR_CACHE_BLK 20
82
83/*
84 * Set the maximum length allowed for usernames.
85 */
86#define USR_LEN 100
87
88/*
89 * Set the maximum length allowed for environment variable names.
90 */
91#define ENV_LEN 100
92
93/*
94 * Set the default number of spaces place between columns when listing
95 * a set of expansions.
96 */
97#define EF_COL_SEP 2
98
99struct ExpandFile {
100  ErrMsg *err;            /* The error reporting buffer */
101  StringGroup *sg;        /* A list of string segments in which */
102                          /*  matching filenames are stored. */
103  DirCache cache;         /* The cache of directory reader objects */
104  PathName *path;         /* The pathname being matched */
105  HomeDir *home;          /* Home-directory lookup object */
106  int files_dim;          /* The allocated dimension of result.files[] */
107  char usrnam[USR_LEN+1]; /* A user name */
108  char envnam[ENV_LEN+1]; /* An environment variable name */
109  FileExpansion result;   /* The container used to return the results of */
110                          /*  expanding a path. */
111};
112
113static int ef_record_pathname(ExpandFile *ef, const char *pathname,
114			      int remove_escapes);
115static char *ef_cache_pathname(ExpandFile *ef, const char *pathname,
116			       int remove_escapes);
117static void ef_clear_files(ExpandFile *ef);
118
119static DirNode *ef_open_dir(ExpandFile *ef, const char *pathname);
120static DirNode *ef_close_dir(ExpandFile *ef, DirNode *node);
121static char *ef_expand_special(ExpandFile *ef, const char *path, int pathlen);
122static int ef_match_relative_pathname(ExpandFile *ef, DirReader *dr,
123				      const char *pattern, int separate);
124static int ef_matches_range(int c, const char *pattern, const char **endp);
125static int ef_string_matches_pattern(const char *file, const char *pattern,
126				      int xplicit, const char *nextp);
127static int ef_cmp_strings(const void *v1, const void *v2);
128
129/*
130 * Encapsulate the formatting information needed to layout a
131 * multi-column listing of expansions.
132 */
133typedef struct {
134  int term_width;     /* The width of the terminal (characters) */
135  int column_width;   /* The number of characters within in each column. */
136  int ncol;           /* The number of columns needed */
137  int nline;          /* The number of lines needed */
138} EfListFormat;
139
140/*
141 * Given the current terminal width, and a list of file expansions,
142 * determine how to best use the terminal width to display a multi-column
143 * listing of expansions.
144 */
145static void ef_plan_listing(FileExpansion *result, int term_width,
146			    EfListFormat *fmt);
147
148/*
149 * Display a given line of a multi-column list of file-expansions.
150 */
151static int ef_format_line(FileExpansion *result, EfListFormat *fmt, int lnum,
152			  GlWriteFn *write_fn, void *data);
153
154/*.......................................................................
155 * Create the resources needed to expand filenames.
156 *
157 * Output:
158 *  return  ExpandFile *  The new object, or NULL on error.
159 */
160ExpandFile *new_ExpandFile(void)
161{
162  ExpandFile *ef;  /* The object to be returned */
163/*
164 * Allocate the container.
165 */
166  ef = (ExpandFile *) malloc(sizeof(ExpandFile));
167  if(!ef) {
168    errno = ENOMEM;
169    return NULL;
170  };
171/*
172 * Before attempting any operation that might fail, initialize the
173 * container at least up to the point at which it can safely be passed
174 * to del_ExpandFile().
175 */
176  ef->err = NULL;
177  ef->sg = NULL;
178  ef->cache.mem = NULL;
179  ef->cache.head = NULL;
180  ef->cache.next = NULL;
181  ef->cache.tail = NULL;
182  ef->path = NULL;
183  ef->home = NULL;
184  ef->result.files = NULL;
185  ef->result.nfile = 0;
186  ef->usrnam[0] = '\0';
187  ef->envnam[0] = '\0';
188/*
189 * Allocate a place to record error messages.
190 */
191  ef->err = _new_ErrMsg();
192  if(!ef->err)
193    return del_ExpandFile(ef);
194/*
195 * Allocate a list of string segments for storing filenames.
196 */
197  ef->sg = _new_StringGroup(_pu_pathname_dim());
198  if(!ef->sg)
199    return del_ExpandFile(ef);
200/*
201 * Allocate a freelist for allocating directory cache nodes.
202 */
203  ef->cache.mem = _new_FreeList(sizeof(DirNode), DIR_CACHE_BLK);
204  if(!ef->cache.mem)
205    return del_ExpandFile(ef);
206/*
207 * Allocate a pathname buffer.
208 */
209  ef->path = _new_PathName();
210  if(!ef->path)
211    return del_ExpandFile(ef);
212/*
213 * Allocate an object for looking up home-directories.
214 */
215  ef->home = _new_HomeDir();
216  if(!ef->home)
217    return del_ExpandFile(ef);
218/*
219 * Allocate an array for files. This will be extended later if needed.
220 */
221  ef->files_dim = MATCH_BLK_FACT;
222  ef->result.files = (char **) malloc(sizeof(ef->result.files[0]) *
223				      ef->files_dim);
224  if(!ef->result.files) {
225    errno = ENOMEM;
226    return del_ExpandFile(ef);
227  };
228  return ef;
229}
230
231/*.......................................................................
232 * Delete a ExpandFile object.
233 *
234 * Input:
235 *  ef     ExpandFile *  The object to be deleted.
236 * Output:
237 *  return ExpandFile *  The deleted object (always NULL).
238 */
239ExpandFile *del_ExpandFile(ExpandFile *ef)
240{
241  if(ef) {
242    DirNode *dnode;
243/*
244 * Delete the string segments.
245 */
246    ef->sg = _del_StringGroup(ef->sg);
247/*
248 * Delete the cached directory readers.
249 */
250    for(dnode=ef->cache.head; dnode; dnode=dnode->next)
251      dnode->dr = _del_DirReader(dnode->dr);
252/*
253 * Delete the memory from which the DirNode list was allocated, thus
254 * deleting the list at the same time.
255 */
256    ef->cache.mem = _del_FreeList(ef->cache.mem, 1);
257    ef->cache.head = ef->cache.tail = ef->cache.next = NULL;
258/*
259 * Delete the pathname buffer.
260 */
261    ef->path = _del_PathName(ef->path);
262/*
263 * Delete the home-directory lookup object.
264 */
265    ef->home = _del_HomeDir(ef->home);
266/*
267 * Delete the array of pointers to files.
268 */
269    if(ef->result.files) {
270      free(ef->result.files);
271      ef->result.files = NULL;
272    };
273/*
274 * Delete the error report buffer.
275 */
276    ef->err = _del_ErrMsg(ef->err);
277/*
278 * Delete the container.
279 */
280    free(ef);
281  };
282  return NULL;
283}
284
285/*.......................................................................
286 * Expand a pathname, converting ~user/ and ~/ patterns at the start
287 * of the pathname to the corresponding home directories, replacing
288 * $envvar with the value of the corresponding environment variable,
289 * and then, if there are any wildcards, matching these against existing
290 * filenames.
291 *
292 * If no errors occur, a container is returned containing the array of
293 * files that resulted from the expansion. If there were no wildcards
294 * in the input pathname, this will contain just the original pathname
295 * after expansion of ~ and $ expressions. If there were any wildcards,
296 * then the array will contain the files that matched them. Note that
297 * if there were any wildcards but no existing files match them, this
298 * is counted as an error and NULL is returned.
299 *
300 * The supported wildcards and their meanings are:
301 *  *        -  Match any sequence of zero or more characters.
302 *  ?        -  Match any single character.
303 *  [chars]  -  Match any single character that appears in 'chars'.
304 *              If 'chars' contains an expression of the form a-b,
305 *              then any character between a and b, including a and b,
306 *              matches. The '-' character looses its special meaning
307 *              as a range specifier when it appears at the start
308 *              of the sequence of characters.
309 *  [^chars] -  The same as [chars] except that it matches any single
310 *              character that doesn't appear in 'chars'.
311 *
312 * Wildcard expressions are applied to individual filename components.
313 * They don't match across directory separators. A '.' character at
314 * the beginning of a filename component must also be matched
315 * explicitly by a '.' character in the input pathname, since these
316 * are UNIX's hidden files.
317 *
318 * Input:
319 *  ef         ExpandFile *  The pathname expansion resource object.
320 *  path             char *  The path name to be expanded.
321 *  pathlen           int    The length of the suffix of path[] that
322 *                           constitutes the filename to be expanded,
323 *                           or -1 to specify that the whole of the
324 *                           path string should be used. Note that
325 *                           regardless of the value of this argument,
326 *                           path[] must contain a '\0' terminated
327 *                           string, since this function checks that
328 *                           pathlen isn't mistakenly too long.
329 * Output:
330 *  return  FileExpansion *  A pointer to a container within the given
331 *                           ExpandFile object. This contains an array
332 *                           of the pathnames that resulted from expanding
333 *                           ~ and $ expressions and from matching any
334 *                           wildcards, sorted into lexical order.
335 *                           This container and its contents will be
336 *                           recycled on subsequent calls, so if you need
337 *                           to keep the results of two successive runs,
338 *                           you will either have to allocate a private
339 *                           copy of the array, or use two ExpandFile
340 *                           objects.
341 *
342 *                           On error NULL is returned. A description
343 *                           of the error can be acquired by calling the
344 *                           ef_last_error() function.
345 */
346FileExpansion *ef_expand_file(ExpandFile *ef, const char *path, int pathlen)
347{
348  DirNode *dnode;       /* A directory-reader cache node */
349  const char *dirname;  /* The name of the top level directory of the search */
350  const char *pptr;     /* A pointer into path[] */
351  int wild;             /* True if the path contains any wildcards */
352/*
353 * Check the arguments.
354 */
355  if(!ef || !path) {
356    if(ef) {
357      _err_record_msg(ef->err, "ef_expand_file: NULL path argument",
358		      END_ERR_MSG);
359    };
360    errno = EINVAL;
361    return NULL;
362  };
363/*
364 * If the caller specified that the whole of path[] be matched,
365 * work out the corresponding length.
366 */
367  if(pathlen < 0 || pathlen > strlen(path))
368    pathlen = strlen(path);
369/*
370 * Discard previous expansion results.
371 */
372  ef_clear_files(ef);
373/*
374 * Preprocess the path, expanding ~/, ~user/ and $envvar references,
375 * using ef->path as a work directory and returning a pointer to
376 * a copy of the resulting pattern in the cache.
377 */
378  path = ef_expand_special(ef, path, pathlen);
379  if(!path)
380    return NULL;
381/*
382 * Clear the pathname buffer.
383 */
384  _pn_clear_path(ef->path);
385/*
386 * Does the pathname contain any wildcards?
387 */
388  for(wild=0,pptr=path; !wild && *pptr; pptr++) {
389    switch(*pptr) {
390    case '\\':                      /* Skip escaped characters */
391      if(pptr[1])
392	pptr++;
393      break;
394    case '*': case '?': case '[':   /* A wildcard character? */
395      wild = 1;
396      break;
397    };
398  };
399/*
400 * If there are no wildcards to match, copy the current expanded
401 * path into the output array, removing backslash escapes while doing so.
402 */
403  if(!wild) {
404    if(ef_record_pathname(ef, path, 1))
405      return NULL;
406/*
407 * Does the filename exist?
408 */
409    ef->result.exists = _pu_file_exists(ef->result.files[0]);
410/*
411 * Match wildcards against existing files.
412 */
413  } else {
414/*
415 * Only existing files that match the pattern will be returned in the
416 * cache.
417 */
418    ef->result.exists = 1;
419/*
420 * Treat matching of the root-directory as a special case since it
421 * isn't contained in a directory.
422 */
423    if(strcmp(path, FS_ROOT_DIR) == 0) {
424      if(ef_record_pathname(ef, FS_ROOT_DIR, 0))
425	return NULL;
426    } else {
427/*
428 * What should the top level directory of the search be?
429 */
430      if(strncmp(path, FS_ROOT_DIR, FS_ROOT_DIR_LEN) == 0) {
431	dirname = FS_ROOT_DIR;
432	if(!_pn_append_to_path(ef->path, FS_ROOT_DIR, -1, 0)) {
433	  _err_record_msg(ef->err, "Insufficient memory to record path",
434			  END_ERR_MSG);
435	  return NULL;
436	};
437	path += FS_ROOT_DIR_LEN;
438      } else {
439	dirname = FS_PWD;
440      };
441/*
442 * Open the top-level directory of the search.
443 */
444      dnode = ef_open_dir(ef, dirname);
445      if(!dnode)
446	return NULL;
447/*
448 * Recursively match successive directory components of the path.
449 */
450      if(ef_match_relative_pathname(ef, dnode->dr, path, 0)) {
451	dnode = ef_close_dir(ef, dnode);
452	return NULL;
453      };
454/*
455 * Cleanup.
456 */
457      dnode = ef_close_dir(ef, dnode);
458    };
459/*
460 * No files matched?
461 */
462    if(ef->result.nfile < 1) {
463      _err_record_msg(ef->err, "No files match", END_ERR_MSG);
464      return NULL;
465    };
466/*
467 * Sort the pathnames that matched.
468 */
469    qsort(ef->result.files, ef->result.nfile, sizeof(ef->result.files[0]),
470	  ef_cmp_strings);
471  };
472/*
473 * Return the result container.
474 */
475  return &ef->result;
476}
477
478/*.......................................................................
479 * Attempt to recursively match the given pattern with the contents of
480 * the current directory, descending sub-directories as needed.
481 *
482 * Input:
483 *  ef      ExpandFile *  The pathname expansion resource object.
484 *  dr       DirReader *  The directory reader object of the directory
485 *                        to be searched.
486 *  pattern const char *  The pattern to match with files in the current
487 *                        directory.
488 *  separate       int    When appending a filename from the specified
489 *                        directory to ef->pathname, insert a directory
490 *                        separator between the existing pathname and
491 *                        the filename, unless separate is zero.
492 * Output:
493 *  return         int    0 - OK.
494 *                        1 - Error.
495 */
496static int ef_match_relative_pathname(ExpandFile *ef, DirReader *dr,
497				       const char *pattern, int separate)
498{
499  const char *nextp;  /* The pointer to the character that follows the part */
500                      /*  of the pattern that is to be matched with files */
501                      /*  in the current directory. */
502  char *file;         /* The name of the file being matched */
503  int pathlen;        /* The length of ef->pathname[] on entry to this */
504                      /*  function */
505/*
506 * Record the current length of the pathname string recorded in
507 * ef->pathname[].
508 */
509  pathlen = strlen(ef->path->name);
510/*
511 * Get a pointer to the character that follows the end of the part of
512 * the pattern that should be matched to files within the current directory.
513 * This will either point to a directory separator, or to the '\0' terminator
514 * of the pattern string.
515 */
516  for(nextp=pattern; *nextp && strncmp(nextp, FS_DIR_SEP, FS_DIR_SEP_LEN) != 0;
517      nextp++)
518    ;
519/*
520 * Read each file from the directory, attempting to match it to the
521 * current pattern.
522 */
523  while((file=_dr_next_file(dr)) != NULL) {
524/*
525 * Does the latest file match the pattern up to nextp?
526 */
527    if(ef_string_matches_pattern(file, pattern, file[0]=='.', nextp)) {
528/*
529 * Append the new directory entry to the current matching pathname.
530 */
531      if((separate && _pn_append_to_path(ef->path, FS_DIR_SEP, -1, 0)==NULL) ||
532	 _pn_append_to_path(ef->path, file, -1, 0)==NULL) {
533	_err_record_msg(ef->err, "Insufficient memory to record path",
534			END_ERR_MSG);
535	return 1;
536      };
537/*
538 * If we have reached the end of the pattern, record the accumulated
539 * pathname in the list of matching files.
540 */
541      if(*nextp == '\0') {
542	if(ef_record_pathname(ef, ef->path->name, 0))
543	  return 1;
544/*
545 * If the matching directory entry is a subdirectory, and the
546 * next character of the pattern is a directory separator,
547 * recursively call the current function to scan the sub-directory
548 * for matches.
549 */
550      } else if(_pu_path_is_dir(ef->path->name) &&
551		strncmp(nextp, FS_DIR_SEP, FS_DIR_SEP_LEN) == 0) {
552/*
553 * If the pattern finishes with the directory separator, then
554 * record the pathame as matching.
555 */
556	if(nextp[FS_DIR_SEP_LEN] == '\0') {
557	  if(ef_record_pathname(ef, ef->path->name, 0))
558	    return 1;
559/*
560 * Match files within the directory.
561 */
562	} else {
563	  DirNode *subdnode = ef_open_dir(ef, ef->path->name);
564	  if(subdnode) {
565	    if(ef_match_relative_pathname(ef, subdnode->dr,
566					   nextp+FS_DIR_SEP_LEN, 1)) {
567	      subdnode = ef_close_dir(ef, subdnode);
568	      return 1;
569	    };
570	    subdnode = ef_close_dir(ef, subdnode);
571	  };
572	};
573      };
574/*
575 * Remove the latest filename from the pathname string, so that
576 * another matching file can be appended.
577 */
578      ef->path->name[pathlen] = '\0';
579    };
580  };
581  return 0;
582}
583
584/*.......................................................................
585 * Record a new matching filename.
586 *
587 * Input:
588 *  ef        ExpandFile *  The filename-match resource object.
589 *  pathname  const char *  The pathname to record.
590 *  remove_escapes   int    If true, remove backslash escapes in the
591 *                          recorded copy of the pathname.
592 * Output:
593 *  return           int     0 - OK.
594 *                           1 - Error (ef->err will contain a
595 *                                      description of the error).
596 */
597static int ef_record_pathname(ExpandFile *ef, const char *pathname,
598			      int remove_escapes)
599{
600  char *copy;          /* The recorded copy of pathname[] */
601/*
602 * Attempt to make a copy of the pathname in the cache.
603 */
604  copy = ef_cache_pathname(ef, pathname, remove_escapes);
605  if(!copy)
606    return 1;
607/*
608 * If there isn't room to record a pointer to the recorded pathname in the
609 * array of files, attempt to extend the array.
610 */
611  if(ef->result.nfile + 1 > ef->files_dim) {
612    int files_dim = ef->files_dim + MATCH_BLK_FACT;
613    char **files = (char **) realloc(ef->result.files,
614				     files_dim * sizeof(files[0]));
615    if(!files) {
616      _err_record_msg(ef->err,
617	     "Insufficient memory to record all of the matching filenames",
618	     END_ERR_MSG);
619      errno = ENOMEM;
620      return 1;
621    };
622    ef->result.files = files;
623    ef->files_dim = files_dim;
624  };
625/*
626 * Record a pointer to the new match.
627 */
628  ef->result.files[ef->result.nfile++] = copy;
629  return 0;
630}
631
632/*.......................................................................
633 * Record a pathname in the cache.
634 *
635 * Input:
636 *  ef       ExpandFile *  The filename-match resource object.
637 *  pathname       char *  The pathname to record.
638 *  remove_escapes  int    If true, remove backslash escapes in the
639 *                         copy of the pathname.
640 * Output:
641 *  return         char *  The pointer to the copy of the pathname.
642 *                         On error NULL is returned and a description
643 *                         of the error is left in ef->err.
644 */
645static char *ef_cache_pathname(ExpandFile *ef, const char *pathname,
646			       int remove_escapes)
647{
648  char *copy = _sg_store_string(ef->sg, pathname, remove_escapes);
649  if(!copy)
650    _err_record_msg(ef->err, "Insufficient memory to store pathname",
651		    END_ERR_MSG);
652  return copy;
653}
654
655/*.......................................................................
656 * Clear the results of the previous expansion operation, ready for the
657 * next.
658 *
659 * Input:
660 *  ef    ExpandFile *  The pathname expansion resource object.
661 */
662static void ef_clear_files(ExpandFile *ef)
663{
664  _clr_StringGroup(ef->sg);
665  _pn_clear_path(ef->path);
666  ef->result.exists = 0;
667  ef->result.nfile = 0;
668  _err_clear_msg(ef->err);
669  return;
670}
671
672/*.......................................................................
673 * Get a new directory reader object from the cache.
674 *
675 * Input:
676 *  ef        ExpandFile *  The pathname expansion resource object.
677 *  pathname  const char *  The pathname of the directory.
678 * Output:
679 *  return       DirNode *  The cache entry of the new directory reader,
680 *                          or NULL on error. On error, ef->err will
681 *                          contain a description of the error.
682 */
683static DirNode *ef_open_dir(ExpandFile *ef, const char *pathname)
684{
685  char *errmsg = NULL;  /* An error message from a called function */
686  DirNode *node;        /* The cache node used */
687/*
688 * Get the directory reader cache.
689 */
690  DirCache *cache = &ef->cache;
691/*
692 * Extend the cache if there are no free cache nodes.
693 */
694  if(!cache->next) {
695    node = (DirNode *) _new_FreeListNode(cache->mem);
696    if(!node) {
697      _err_record_msg(ef->err, "Insufficient memory to open a new directory",
698		      END_ERR_MSG);
699      return NULL;
700    };
701/*
702 * Initialize the cache node.
703 */
704    node->next = NULL;
705    node->prev = NULL;
706    node->dr = NULL;
707/*
708 * Allocate a directory reader object.
709 */
710    node->dr = _new_DirReader();
711    if(!node->dr) {
712      _err_record_msg(ef->err, "Insufficient memory to open a new directory",
713		      END_ERR_MSG);
714      node = (DirNode *) _del_FreeListNode(cache->mem, node);
715      return NULL;
716    };
717/*
718 * Append the node to the cache list.
719 */
720    node->prev = cache->tail;
721    if(cache->tail)
722      cache->tail->next = node;
723    else
724      cache->head = node;
725    cache->next = cache->tail = node;
726  };
727/*
728 * Get the first unused node, but don't remove it from the list yet.
729 */
730  node = cache->next;
731/*
732 * Attempt to open the specified directory.
733 */
734  if(_dr_open_dir(node->dr, pathname, &errmsg)) {
735    _err_record_msg(ef->err, errmsg, END_ERR_MSG);
736    return NULL;
737  };
738/*
739 * Now that we have successfully opened the specified directory,
740 * remove the cache node from the list, and relink the list around it.
741 */
742  cache->next = node->next;
743  if(node->prev)
744    node->prev->next = node->next;
745  else
746    cache->head = node->next;
747  if(node->next)
748    node->next->prev = node->prev;
749  else
750    cache->tail = node->prev;
751  node->next = node->prev = NULL;
752/*
753 * Return the successfully initialized cache node to the caller.
754 */
755  return node;
756}
757
758/*.......................................................................
759 * Return a directory reader object to the cache, after first closing
760 * the directory that it was managing.
761 *
762 * Input:
763 *  ef    ExpandFile *  The pathname expansion resource object.
764 *  node     DirNode *  The cache entry of the directory reader, as returned
765 *                      by ef_open_dir().
766 * Output:
767 *  return   DirNode *  The deleted DirNode (ie. allways NULL).
768 */
769static DirNode *ef_close_dir(ExpandFile *ef, DirNode *node)
770{
771/*
772 * Get the directory reader cache.
773 */
774  DirCache *cache = &ef->cache;
775/*
776 * Close the directory.
777 */
778  _dr_close_dir(node->dr);
779/*
780 * Return the node to the tail of the cache list.
781 */
782  node->next = NULL;
783  node->prev = cache->tail;
784  if(cache->tail)
785    cache->tail->next = node;
786  else
787    cache->head = cache->tail = node;
788  if(!cache->next)
789    cache->next = node;
790  return NULL;
791}
792
793/*.......................................................................
794 * Return non-zero if the specified file name matches a given glob
795 * pattern.
796 *
797 * Input:
798 *  file     const char *  The file-name component to be matched to the pattern.
799 *  pattern  const char *  The start of the pattern to match against file[].
800 *  xplicit         int    If non-zero, the first character must be matched
801 *                         explicitly (ie. not with a wildcard).
802 *  nextp    const char *  The pointer to the the character following the
803 *                         end of the pattern in pattern[].
804 * Output:
805 *  return    int          0 - Doesn't match.
806 *                         1 - The file-name string matches the pattern.
807 */
808static int ef_string_matches_pattern(const char *file, const char *pattern,
809				      int xplicit, const char *nextp)
810{
811  const char *pptr = pattern; /* The pointer used to scan the pattern */
812  const char *fptr = file;    /* The pointer used to scan the filename string */
813/*
814 * Match each character of the pattern in turn.
815 */
816  while(pptr < nextp) {
817/*
818 * Handle the next character of the pattern.
819 */
820    switch(*pptr) {
821/*
822 * A match zero-or-more characters wildcard operator.
823 */
824    case '*':
825/*
826 * Skip the '*' character in the pattern.
827 */
828      pptr++;
829/*
830 * If wildcards aren't allowed, the pattern doesn't match.
831 */
832      if(xplicit)
833	return 0;
834/*
835 * If the pattern ends with a the '*' wildcard, then the
836 * rest of the filename matches this.
837 */
838      if(pptr >= nextp)
839	return 1;
840/*
841 * Using the wildcard to match successively longer sections of
842 * the remaining characters of the filename, attempt to match
843 * the tail of the filename against the tail of the pattern.
844 */
845      for( ; *fptr; fptr++) {
846	if(ef_string_matches_pattern(fptr, pptr, 0, nextp))
847	  return 1;
848      };
849      return 0; /* The pattern following the '*' didn't match */
850      break;
851/*
852 * A match-one-character wildcard operator.
853 */
854    case '?':
855/*
856 * If there is a character to be matched, skip it and advance the
857 * pattern pointer.
858 */
859      if(!xplicit && *fptr) {
860        fptr++;
861        pptr++;
862/*
863 * If we hit the end of the filename string, there is no character
864 * matching the operator, so the string doesn't match.
865 */
866      } else {
867        return 0;
868      };
869      break;
870/*
871 * A character range operator, with the character ranges enclosed
872 * in matching square brackets.
873 */
874    case '[':
875      if(xplicit || !ef_matches_range(*fptr++, ++pptr, &pptr))
876        return 0;
877      break;
878/*
879 * A backslash in the pattern prevents the following character as
880 * being seen as a special character.
881 */
882    case '\\':
883      pptr++;
884      /* Note fallthrough to default */
885/*
886 * A normal character to be matched explicitly.
887 */
888      /* FALLTHROUGH */
889    default:
890      if(*fptr == *pptr) {
891        fptr++;
892        pptr++;
893      } else {
894        return 0;
895      };
896      break;
897    };
898/*
899 * After passing the first character, turn off the explicit match
900 * requirement.
901 */
902    xplicit = 0;
903  };
904/*
905 * To get here the pattern must have been exhausted. If the filename
906 * string matched, then the filename string must also have been
907 * exhausted.
908 */
909  return *fptr == '\0';
910}
911
912/*.......................................................................
913 * Match a character range expression terminated by an unescaped close
914 * square bracket.
915 *
916 * Input:
917 *  c               int     The character to be matched with the range
918 *                          pattern.
919 *  pattern  const char *   The range pattern to be matched (ie. after the
920 *                          initiating '[' character).
921 *  endp     const char **  On output a pointer to the character following the
922 *                          range expression will be assigned to *endp.
923 * Output:
924 *  return          int     0 - Doesn't match.
925 *                          1 - The character matched.
926 */
927static int ef_matches_range(int c, const char *pattern, const char **endp)
928{
929  const char *pptr = pattern;  /* The pointer used to scan the pattern */
930  int invert = 0;              /* True to invert the sense of the match */
931  int matched = 0;             /* True if the character matched the pattern */
932/*
933 * If the first character is a caret, the sense of the match is
934 * inverted and only if the character isn't one of those in the
935 * range, do we say that it matches.
936 */
937  if(*pptr == '^') {
938    pptr++;
939    invert = 1;
940  };
941/*
942 * The hyphen is only a special character when it follows the first
943 * character of the range (not including the caret).
944 */
945  if(*pptr == '-') {
946    pptr++;
947    if(c == '-') {
948      *endp = pptr;
949      matched = 1;
950    };
951/*
952 * Skip other leading '-' characters since they make no sense.
953 */
954    while(*pptr == '-')
955      pptr++;
956  };
957/*
958 * The hyphen is only a special character when it follows the first
959 * character of the range (not including the caret or a hyphen).
960 */
961  if(*pptr == ']') {
962    pptr++;
963    if(c == ']') {
964      *endp = pptr;
965      matched = 1;
966    };
967  };
968/*
969 * Having dealt with the characters that have special meanings at
970 * the beginning of a character range expression, see if the
971 * character matches any of the remaining characters of the range,
972 * up until a terminating ']' character is seen.
973 */
974  while(!matched && *pptr && *pptr != ']') {
975/*
976 * Is this a range of characters signaled by the two end characters
977 * separated by a hyphen?
978 */
979    if(*pptr == '-') {
980      if(pptr[1] != ']') {
981        if(c >= pptr[-1] && c <= pptr[1])
982	  matched = 1;
983	pptr += 2;
984      };
985/*
986 * A normal character to be compared directly.
987 */
988    } else if(*pptr++ == c) {
989      matched = 1;
990    };
991  };
992/*
993 * Find the terminating ']'.
994 */
995  while(*pptr && *pptr != ']')
996    pptr++;
997/*
998 * Did we find a terminating ']'?
999 */
1000  if(*pptr == ']') {
1001    *endp = pptr + 1;
1002    return matched ? !invert : invert;
1003  };
1004/*
1005 * If the pattern didn't end with a ']' then it doesn't match, regardless
1006 * of the value of the required sense of the match.
1007 */
1008  *endp = pptr;
1009  return 0;
1010}
1011
1012/*.......................................................................
1013 * This is a qsort() comparison function used to sort strings.
1014 *
1015 * Input:
1016 *  v1, v2   void *  Pointers to the two strings to be compared.
1017 * Output:
1018 *  return    int    -1 -> v1 < v2.
1019 *                    0 -> v1 == v2
1020 *                    1 -> v1 > v2
1021 */
1022static int ef_cmp_strings(const void *v1, const void *v2)
1023{
1024  char * const *s1 = (char * const *) v1;
1025  char * const *s2 = (char * const *) v2;
1026  return strcmp(*s1, *s2);
1027}
1028
1029/*.......................................................................
1030 * Preprocess a path, expanding ~/, ~user/ and $envvar references, using
1031 * ef->path as a work buffer, then copy the result into a cache entry,
1032 * and return a pointer to this copy.
1033 *
1034 * Input:
1035 *  ef    ExpandFile *  The resource object of the file matcher.
1036 *  pathlen      int    The length of the prefix of path[] to be expanded.
1037 * Output:
1038 *  return      char *  A pointer to a copy of the output path in the
1039 *                      cache. On error NULL is returned, and a description
1040 *                      of the error is left in ef->err.
1041 */
1042static char *ef_expand_special(ExpandFile *ef, const char *path, int pathlen)
1043{
1044  int spos;      /* The index of the start of the path segment that needs */
1045                 /*  to be copied from path[] to the output pathname. */
1046  int ppos;      /* The index of a character in path[] */
1047  char *pptr;    /* A pointer into the output path */
1048  int escaped;   /* True if the previous character was a '\' */
1049  int i;
1050/*
1051 * Clear the pathname buffer.
1052 */
1053  _pn_clear_path(ef->path);
1054/*
1055 * We need to perform two passes, one to expand environment variables
1056 * and a second to do tilde expansion. This caters for the case
1057 * where an initial dollar expansion yields a tilde expression.
1058 */
1059  escaped = 0;
1060  for(spos=ppos=0; ppos < pathlen; ppos++) {
1061    int c = path[ppos];
1062    if(escaped) {
1063      escaped = 0;
1064    } else if(c == '\\') {
1065      escaped = 1;
1066    } else if(c == '$') {
1067      int envlen;   /* The length of the environment variable */
1068      char *value;  /* The value of the environment variable */
1069/*
1070 * Record the preceding unrecorded part of the pathname.
1071 */
1072      if(spos < ppos && _pn_append_to_path(ef->path, path + spos, ppos-spos, 0)
1073	 == NULL) {
1074	_err_record_msg(ef->err, "Insufficient memory to expand path",
1075			END_ERR_MSG);
1076	return NULL;
1077      };
1078/*
1079 * Skip the dollar.
1080 */
1081      ppos++;
1082/*
1083 * Copy the environment variable name that follows the dollar into
1084 * ef->envnam[], stopping if a directory separator or end of string
1085 * is seen.
1086 */
1087      for(envlen=0; envlen<ENV_LEN && ppos < pathlen &&
1088	  strncmp(path + ppos, FS_DIR_SEP, FS_DIR_SEP_LEN); envlen++)
1089	ef->envnam[envlen] = path[ppos++];
1090/*
1091 * If the username overflowed the buffer, treat it as invalid (note that
1092 * on most unix systems only 8 characters are allowed in a username,
1093 * whereas our ENV_LEN is much bigger than that.
1094 */
1095      if(envlen >= ENV_LEN) {
1096	_err_record_msg(ef->err, "Environment variable name too long",
1097			END_ERR_MSG);
1098	return NULL;
1099      };
1100/*
1101 * Terminate the environment variable name.
1102 */
1103      ef->envnam[envlen] = '\0';
1104/*
1105 * Lookup the value of the environment variable.
1106 */
1107      value = getenv(ef->envnam);
1108      if(!value) {
1109	_err_record_msg(ef->err, "No expansion found for: $", ef->envnam,
1110			END_ERR_MSG);
1111	return NULL;
1112      };
1113/*
1114 * Copy the value of the environment variable into the output pathname.
1115 */
1116      if(_pn_append_to_path(ef->path, value, -1, 0) == NULL) {
1117	_err_record_msg(ef->err, "Insufficient memory to expand path",
1118			END_ERR_MSG);
1119	return NULL;
1120      };
1121/*
1122 * Record the start of the uncopied tail of the input pathname.
1123 */
1124      spos = ppos;
1125    };
1126  };
1127/*
1128 * Record the uncopied tail of the pathname.
1129 */
1130  if(spos < ppos && _pn_append_to_path(ef->path, path + spos, ppos-spos, 0)
1131     == NULL) {
1132    _err_record_msg(ef->err, "Insufficient memory to expand path", END_ERR_MSG);
1133    return NULL;
1134  };
1135/*
1136 * If the first character of the resulting pathname is a tilde,
1137 * then attempt to substitute the home directory of the specified user.
1138 */
1139  pptr = ef->path->name;
1140  if(*pptr == '~' && path[0] != '\\') {
1141    int usrlen;           /* The length of the username following the tilde */
1142    const char *homedir;  /* The home directory of the user */
1143    int homelen;          /* The length of the home directory string */
1144    int plen;             /* The current length of the path */
1145    int skip=0;           /* The number of characters to skip after the ~user */
1146/*
1147 * Get the current length of the output path.
1148 */
1149    plen = strlen(ef->path->name);
1150/*
1151 * Skip the tilde.
1152 */
1153    pptr++;
1154/*
1155 * Copy the optional username that follows the tilde into ef->usrnam[].
1156 */
1157    for(usrlen=0; usrlen<USR_LEN && *pptr &&
1158	strncmp(pptr, FS_DIR_SEP, FS_DIR_SEP_LEN); usrlen++)
1159      ef->usrnam[usrlen] = *pptr++;
1160/*
1161 * If the username overflowed the buffer, treat it as invalid (note that
1162 * on most unix systems only 8 characters are allowed in a username,
1163 * whereas our USR_LEN is much bigger than that.
1164 */
1165    if(usrlen >= USR_LEN) {
1166      _err_record_msg(ef->err, "Username too long", END_ERR_MSG);
1167      return NULL;
1168    };
1169/*
1170 * Terminate the username string.
1171 */
1172    ef->usrnam[usrlen] = '\0';
1173/*
1174 * Lookup the home directory of the user.
1175 */
1176    homedir = _hd_lookup_home_dir(ef->home, ef->usrnam);
1177    if(!homedir) {
1178      _err_record_msg(ef->err, _hd_last_home_dir_error(ef->home), END_ERR_MSG);
1179      return NULL;
1180    };
1181    homelen = strlen(homedir);
1182/*
1183 * ~user and ~ are usually followed by a directory separator to
1184 * separate them from the file contained in the home directory.
1185 * If the home directory is the root directory, then we don't want
1186 * to follow the home directory by a directory separator, so we must
1187 * erase it.
1188 */
1189    if(strcmp(homedir, FS_ROOT_DIR) == 0 &&
1190       strncmp(pptr, FS_DIR_SEP, FS_DIR_SEP_LEN) == 0) {
1191      skip = FS_DIR_SEP_LEN;
1192    };
1193/*
1194 * If needed, increase the size of the pathname buffer to allow it
1195 * to accomodate the home directory instead of the tilde expression.
1196 * Note that pptr may not be valid after this call.
1197 */
1198    if(_pn_resize_path(ef->path, plen - usrlen - 1 - skip + homelen)==NULL) {
1199      _err_record_msg(ef->err, "Insufficient memory to expand filename",
1200		      END_ERR_MSG);
1201      return NULL;
1202    };
1203/*
1204 * Move the part of the pathname that follows the tilde expression to
1205 * the end of where the home directory will need to be inserted.
1206 */
1207    memmove(ef->path->name + homelen,
1208	    ef->path->name + 1 + usrlen + skip, plen - usrlen - 1 - skip+1);
1209/*
1210 * Write the home directory at the beginning of the string.
1211 */
1212    for(i=0; i<homelen; i++)
1213      ef->path->name[i] = homedir[i];
1214  };
1215/*
1216 * Copy the result into the cache, and return a pointer to the copy.
1217 */
1218  return ef_cache_pathname(ef, ef->path->name, 0);
1219}
1220
1221/*.......................................................................
1222 * Return a description of the last path-expansion error that occurred.
1223 *
1224 * Input:
1225 *  ef     ExpandFile *   The path-expansion resource object.
1226 * Output:
1227 *  return       char *   The description of the last error.
1228 */
1229const char *ef_last_error(ExpandFile *ef)
1230{
1231  return ef ? _err_get_msg(ef->err) : "NULL ExpandFile argument";
1232}
1233
1234/*.......................................................................
1235 * Print out an array of matching files.
1236 *
1237 * Input:
1238 *  result  FileExpansion *   The container of the sorted array of
1239 *                            expansions.
1240 *  fp               FILE *   The output stream to write to.
1241 *  term_width        int     The width of the terminal.
1242 * Output:
1243 *  return            int     0 - OK.
1244 *                            1 - Error.
1245 */
1246int ef_list_expansions(FileExpansion *result, FILE *fp, int term_width)
1247{
1248  return _ef_output_expansions(result, _io_write_stdio, fp, term_width);
1249}
1250
1251/*.......................................................................
1252 * Print out an array of matching files via a callback.
1253 *
1254 * Input:
1255 *  result  FileExpansion *  The container of the sorted array of
1256 *                           expansions.
1257 *  write_fn    GlWriteFn *  The function to call to write the
1258 *                           expansions or 0 to discard the output.
1259 *  data             void *  Anonymous data to pass to write_fn().
1260 *  term_width        int    The width of the terminal.
1261 * Output:
1262 *  return            int    0 - OK.
1263 *                           1 - Error.
1264 */
1265int _ef_output_expansions(FileExpansion *result, GlWriteFn *write_fn,
1266			  void *data, int term_width)
1267{
1268  EfListFormat fmt; /* List formatting information */
1269  int lnum;          /* The sequential number of the line to print next */
1270/*
1271 * Not enough space to list anything?
1272 */
1273  if(term_width < 1)
1274    return 0;
1275/*
1276 * Do we have a callback to write via, and any expansions to be listed?
1277 */
1278  if(write_fn && result && result->nfile>0) {
1279/*
1280 * Work out how to arrange the listing into fixed sized columns.
1281 */
1282    ef_plan_listing(result, term_width, &fmt);
1283/*
1284 * Print the listing to the specified stream.
1285 */
1286    for(lnum=0; lnum < fmt.nline; lnum++) {
1287      if(ef_format_line(result, &fmt, lnum, write_fn, data))
1288	return 1;
1289    };
1290  };
1291  return 0;
1292}
1293
1294/*.......................................................................
1295 * Work out how to arrange a given array of completions into a listing
1296 * of one or more fixed size columns.
1297 *
1298 * Input:
1299 *  result   FileExpansion *   The set of completions to be listed.
1300 *  term_width         int     The width of the terminal. A lower limit of
1301 *                             zero is quietly enforced.
1302 * Input/Output:
1303 *  fmt       EfListFormat *   The formatting information will be assigned
1304 *                             to the members of *fmt.
1305 */
1306static void ef_plan_listing(FileExpansion *result, int term_width,
1307			    EfListFormat *fmt)
1308{
1309  int maxlen;    /* The length of the longest matching string */
1310  int i;
1311/*
1312 * Ensure that term_width >= 0.
1313 */
1314  if(term_width < 0)
1315    term_width = 0;
1316/*
1317 * Start by assuming the worst case, that either nothing will fit
1318 * on the screen, or that there are no matches to be listed.
1319 */
1320  fmt->term_width = term_width;
1321  fmt->column_width = 0;
1322  fmt->nline = fmt->ncol = 0;
1323/*
1324 * Work out the maximum length of the matching strings.
1325 */
1326  maxlen = 0;
1327  for(i=0; i<result->nfile; i++) {
1328    int len = strlen(result->files[i]);
1329    if(len > maxlen)
1330      maxlen = len;
1331  };
1332/*
1333 * Nothing to list?
1334 */
1335  if(maxlen == 0)
1336    return;
1337/*
1338 * Split the available terminal width into columns of
1339 * maxlen + EF_COL_SEP characters.
1340 */
1341  fmt->column_width = maxlen;
1342  fmt->ncol = fmt->term_width / (fmt->column_width + EF_COL_SEP);
1343/*
1344 * If the column width is greater than the terminal width, zero columns
1345 * will have been selected. Set a lower limit of one column. Leave it
1346 * up to the caller how to deal with completions who's widths exceed
1347 * the available terminal width.
1348 */
1349  if(fmt->ncol < 1)
1350    fmt->ncol = 1;
1351/*
1352 * How many lines of output will be needed?
1353 */
1354  fmt->nline = (result->nfile + fmt->ncol - 1) / fmt->ncol;
1355  return;
1356}
1357
1358/*.......................................................................
1359 * Render one line of a multi-column listing of completions, using a
1360 * callback function to pass the output to an arbitrary destination.
1361 *
1362 * Input:
1363 *  result   FileExpansion *  The container of the sorted array of
1364 *                            completions.
1365 *  fmt       EfListFormat *  Formatting information.
1366 *  lnum               int    The index of the line to print, starting
1367 *                            from 0, and incrementing until the return
1368 *                            value indicates that there is nothing more
1369 *                            to be printed.
1370 *  write_fn     GlWriteFn *  The function to call to write the line, or
1371 *                            0 to discard the output.
1372 *  data              void *  Anonymous data to pass to write_fn().
1373 * Output:
1374 *  return             int    0 - Line printed ok.
1375 *                            1 - Nothing to print.
1376 */
1377static int ef_format_line(FileExpansion *result, EfListFormat *fmt, int lnum,
1378			  GlWriteFn *write_fn, void *data)
1379{
1380  int col;             /* The index of the list column being output */
1381/*
1382 * If the line index is out of bounds, there is nothing to be written.
1383 */
1384  if(lnum < 0 || lnum >= fmt->nline)
1385    return 1;
1386/*
1387 * If no output function has been provided, return as though the line
1388 * had been printed.
1389 */
1390  if(!write_fn)
1391    return 0;
1392/*
1393 * Print the matches in 'ncol' columns, sorted in line order within each
1394 * column.
1395 */
1396  for(col=0; col < fmt->ncol; col++) {
1397    int m = col*fmt->nline + lnum;
1398/*
1399 * Is there another match to be written? Note that in general
1400 * the last line of a listing will have fewer filled columns
1401 * than the initial lines.
1402 */
1403    if(m < result->nfile) {
1404      char *file = result->files[m];
1405/*
1406 * How long are the completion and type-suffix strings?
1407 */
1408      int flen = strlen(file);
1409/*
1410 * Write the completion string.
1411 */
1412      if(write_fn(data, file, flen) != flen)
1413	return 1;
1414/*
1415 * If another column follows the current one, pad to its start with spaces.
1416 */
1417      if(col+1 < fmt->ncol) {
1418/*
1419 * The following constant string of spaces is used to pad the output.
1420 */
1421	static const char spaces[] = "                    ";
1422	static const int nspace = sizeof(spaces) - 1;
1423/*
1424 * Pad to the next column, using as few sub-strings of the spaces[]
1425 * array as possible.
1426 */
1427	int npad = fmt->column_width + EF_COL_SEP - flen;
1428	while(npad>0) {
1429	  int n = npad > nspace ? nspace : npad;
1430	  if(write_fn(data, spaces + nspace - n, n) != n)
1431	    return 1;
1432	  npad -= n;
1433	};
1434      };
1435    };
1436  };
1437/*
1438 * Start a new line.
1439 */
1440  {
1441    char s[] = "\r\n";
1442    int n = strlen(s);
1443    if(write_fn(data, s, n) != n)
1444      return 1;
1445  };
1446  return 0;
1447}
1448
1449#endif  /* ifndef WITHOUT_FILE_SYSTEM */
1450