OpenSolaris Launch

1 files changed, 1450 insertions, 0 deletions

diff --git a/usr/src/lib/libtecla/common/expand.c b/usr/src/lib/libtecla/common/expand.c
new file mode 100644
index 0000000000..db00c7bfff
--- /dev/null
+++ b/usr/src/lib/libtecla/common/expand.c
@@ -0,0 +1,1450 @@
+/*
+ * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
+ * 
+ * All rights reserved.
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, and/or sell copies of the Software, and to permit persons
+ * to whom the Software is furnished to do so, provided that the above
+ * copyright notice(s) and this permission notice appear in all copies of
+ * the Software and that both the above copyright notice(s) and this
+ * permission notice appear in supporting documentation.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
+ * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
+ * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
+ * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
+ * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
+ * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ * 
+ * Except as contained in this notice, the name of a copyright holder
+ * shall not be used in advertising or otherwise to promote the sale, use
+ * or other dealings in this Software without prior written authorization
+ * of the copyright holder.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+/*
+ * If file-system access is to be excluded, this module has no function,
+ * so all of its code should be excluded.
+ */
+#ifndef WITHOUT_FILE_SYSTEM
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+#include "freelist.h"
+#include "direader.h"
+#include "pathutil.h"
+#include "homedir.h"
+#include "stringrp.h"
+#include "libtecla.h"
+#include "ioutil.h"
+#include "expand.h"
+#include "errmsg.h"
+
+/*
+ * Specify the number of elements to extend the files[] array by
+ * when it proves to be too small. This also sets the initial size
+ * of the array.
+ */
+#define MATCH_BLK_FACT 256
+
+/*
+ * A list of directory iterators is maintained using nodes of the
+ * following form.
+ */
+typedef struct DirNode DirNode;
+struct DirNode {
+  DirNode *next;       /* The next directory in the list */
+  DirNode *prev;       /* The node that precedes this node in the list */
+  DirReader *dr;       /* The directory reader object */
+};
+
+typedef struct {
+  FreeList *mem;       /* Memory for DirNode list nodes */
+  DirNode *head;       /* The head of the list of used and unused cache nodes */
+  DirNode *next;       /* The next unused node between head and tail */
+  DirNode *tail;       /* The tail of the list of unused cache nodes */
+} DirCache;
+
+/*
+ * Specify how many directory cache nodes to allocate at a time.
+ */
+#define DIR_CACHE_BLK 20
+
+/*
+ * Set the maximum length allowed for usernames.
+ */
+#define USR_LEN 100
+
+/*
+ * Set the maximum length allowed for environment variable names.
+ */
+#define ENV_LEN 100
+
+/*
+ * Set the default number of spaces place between columns when listing
+ * a set of expansions.
+ */
+#define EF_COL_SEP 2
+
+struct ExpandFile {
+  ErrMsg *err;            /* The error reporting buffer */
+  StringGroup *sg;        /* A list of string segments in which */
+                          /*  matching filenames are stored. */
+  DirCache cache;         /* The cache of directory reader objects */
+  PathName *path;         /* The pathname being matched */
+  HomeDir *home;          /* Home-directory lookup object */
+  int files_dim;          /* The allocated dimension of result.files[] */
+  char usrnam[USR_LEN+1]; /* A user name */
+  char envnam[ENV_LEN+1]; /* An environment variable name */
+  FileExpansion result;   /* The container used to return the results of */
+                          /*  expanding a path. */
+};
+
+static int ef_record_pathname(ExpandFile *ef, const char *pathname,
+			      int remove_escapes);
+static char *ef_cache_pathname(ExpandFile *ef, const char *pathname,
+			       int remove_escapes);
+static void ef_clear_files(ExpandFile *ef);
+
+static DirNode *ef_open_dir(ExpandFile *ef, const char *pathname);
+static DirNode *ef_close_dir(ExpandFile *ef, DirNode *node);
+static char *ef_expand_special(ExpandFile *ef, const char *path, int pathlen);
+static int ef_match_relative_pathname(ExpandFile *ef, DirReader *dr,
+				      const char *pattern, int separate);
+static int ef_matches_range(int c, const char *pattern, const char **endp);
+static int ef_string_matches_pattern(const char *file, const char *pattern,
+				      int xplicit, const char *nextp);
+static int ef_cmp_strings(const void *v1, const void *v2);
+
+/*
+ * Encapsulate the formatting information needed to layout a
+ * multi-column listing of expansions.
+ */
+typedef struct {
+  int term_width;     /* The width of the terminal (characters) */
+  int column_width;   /* The number of characters within in each column. */
+  int ncol;           /* The number of columns needed */
+  int nline;          /* The number of lines needed */
+} EfListFormat;
+
+/*
+ * Given the current terminal width, and a list of file expansions,
+ * determine how to best use the terminal width to display a multi-column
+ * listing of expansions.
+ */
+static void ef_plan_listing(FileExpansion *result, int term_width,
+			    EfListFormat *fmt);
+
+/*
+ * Display a given line of a multi-column list of file-expansions.
+ */
+static int ef_format_line(FileExpansion *result, EfListFormat *fmt, int lnum,
+			  GlWriteFn *write_fn, void *data);
+
+/*.......................................................................
+ * Create the resources needed to expand filenames.
+ *
+ * Output:
+ *  return  ExpandFile *  The new object, or NULL on error.
+ */
+ExpandFile *new_ExpandFile(void)
+{
+  ExpandFile *ef;  /* The object to be returned */
+/*
+ * Allocate the container.
+ */
+  ef = (ExpandFile *) malloc(sizeof(ExpandFile));
+  if(!ef) {
+    errno = ENOMEM;
+    return NULL;
+  };
+/*
+ * Before attempting any operation that might fail, initialize the
+ * container at least up to the point at which it can safely be passed
+ * to del_ExpandFile().
+ */
+  ef->err = NULL;
+  ef->sg = NULL;
+  ef->cache.mem = NULL;
+  ef->cache.head = NULL;
+  ef->cache.next = NULL;
+  ef->cache.tail = NULL;
+  ef->path = NULL;
+  ef->home = NULL;
+  ef->result.files = NULL;
+  ef->result.nfile = 0;
+  ef->usrnam[0] = '\0';
+  ef->envnam[0] = '\0';
+/*
+ * Allocate a place to record error messages.
+ */
+  ef->err = _new_ErrMsg();
+  if(!ef->err)
+    return del_ExpandFile(ef);
+/*
+ * Allocate a list of string segments for storing filenames.
+ */
+  ef->sg = _new_StringGroup(_pu_pathname_dim());
+  if(!ef->sg)
+    return del_ExpandFile(ef);
+/*
+ * Allocate a freelist for allocating directory cache nodes.
+ */
+  ef->cache.mem = _new_FreeList(sizeof(DirNode), DIR_CACHE_BLK);
+  if(!ef->cache.mem)
+    return del_ExpandFile(ef);
+/*
+ * Allocate a pathname buffer.
+ */
+  ef->path = _new_PathName();
+  if(!ef->path)
+    return del_ExpandFile(ef);
+/*
+ * Allocate an object for looking up home-directories.
+ */
+  ef->home = _new_HomeDir();
+  if(!ef->home)
+    return del_ExpandFile(ef);
+/*
+ * Allocate an array for files. This will be extended later if needed.
+ */
+  ef->files_dim = MATCH_BLK_FACT;
+  ef->result.files = (char **) malloc(sizeof(ef->result.files[0]) *
+				      ef->files_dim);
+  if(!ef->result.files) {
+    errno = ENOMEM;
+    return del_ExpandFile(ef);
+  };
+  return ef;
+}
+
+/*.......................................................................
+ * Delete a ExpandFile object.
+ *
+ * Input:
+ *  ef     ExpandFile *  The object to be deleted.
+ * Output:
+ *  return ExpandFile *  The deleted object (always NULL).
+ */
+ExpandFile *del_ExpandFile(ExpandFile *ef)
+{
+  if(ef) {
+    DirNode *dnode;
+/*
+ * Delete the string segments.
+ */
+    ef->sg = _del_StringGroup(ef->sg);
+/*
+ * Delete the cached directory readers.
+ */
+    for(dnode=ef->cache.head; dnode; dnode=dnode->next)
+      dnode->dr = _del_DirReader(dnode->dr);
+/*
+ * Delete the memory from which the DirNode list was allocated, thus
+ * deleting the list at the same time.
+ */
+    ef->cache.mem = _del_FreeList(ef->cache.mem, 1);
+    ef->cache.head = ef->cache.tail = ef->cache.next = NULL;
+/*
+ * Delete the pathname buffer.
+ */
+    ef->path = _del_PathName(ef->path);
+/*
+ * Delete the home-directory lookup object.
+ */
+    ef->home = _del_HomeDir(ef->home);
+/*
+ * Delete the array of pointers to files.
+ */
+    if(ef->result.files) {
+      free(ef->result.files);
+      ef->result.files = NULL;
+    };
+/*
+ * Delete the error report buffer.
+ */
+    ef->err = _del_ErrMsg(ef->err);
+/*
+ * Delete the container.
+ */
+    free(ef);
+  };
+  return NULL;
+}
+
+/*.......................................................................
+ * Expand a pathname, converting ~user/ and ~/ patterns at the start
+ * of the pathname to the corresponding home directories, replacing
+ * $envvar with the value of the corresponding environment variable,
+ * and then, if there are any wildcards, matching these against existing
+ * filenames.
+ *
+ * If no errors occur, a container is returned containing the array of
+ * files that resulted from the expansion. If there were no wildcards
+ * in the input pathname, this will contain just the original pathname
+ * after expansion of ~ and $ expressions. If there were any wildcards,
+ * then the array will contain the files that matched them. Note that
+ * if there were any wildcards but no existing files match them, this
+ * is counted as an error and NULL is returned.
+ *
+ * The supported wildcards and their meanings are:
+ *  *        -  Match any sequence of zero or more characters.
+ *  ?        -  Match any single character.
+ *  [chars]  -  Match any single character that appears in 'chars'.
+ *              If 'chars' contains an expression of the form a-b,
+ *              then any character between a and b, including a and b,
+ *              matches. The '-' character looses its special meaning
+ *              as a range specifier when it appears at the start
+ *              of the sequence of characters.
+ *  [^chars] -  The same as [chars] except that it matches any single
+ *              character that doesn't appear in 'chars'.
+ *
+ * Wildcard expressions are applied to individual filename components.
+ * They don't match across directory separators. A '.' character at
+ * the beginning of a filename component must also be matched
+ * explicitly by a '.' character in the input pathname, since these
+ * are UNIX's hidden files.
+ *
+ * Input:
+ *  ef         ExpandFile *  The pathname expansion resource object.
+ *  path             char *  The path name to be expanded.
+ *  pathlen           int    The length of the suffix of path[] that
+ *                           constitutes the filename to be expanded,
+ *                           or -1 to specify that the whole of the
+ *                           path string should be used. Note that
+ *                           regardless of the value of this argument,
+ *                           path[] must contain a '\0' terminated
+ *                           string, since this function checks that
+ *                           pathlen isn't mistakenly too long.
+ * Output:
+ *  return  FileExpansion *  A pointer to a container within the given
+ *                           ExpandFile object. This contains an array
+ *                           of the pathnames that resulted from expanding
+ *                           ~ and $ expressions and from matching any
+ *                           wildcards, sorted into lexical order.
+ *                           This container and its contents will be
+ *                           recycled on subsequent calls, so if you need
+ *                           to keep the results of two successive runs,
+ *                           you will either have to allocate a private
+ *                           copy of the array, or use two ExpandFile
+ *                           objects.
+ *
+ *                           On error NULL is returned. A description
+ *                           of the error can be acquired by calling the
+ *                           ef_last_error() function.
+ */
+FileExpansion *ef_expand_file(ExpandFile *ef, const char *path, int pathlen)
+{
+  DirNode *dnode;       /* A directory-reader cache node */
+  const char *dirname;  /* The name of the top level directory of the search */
+  const char *pptr;     /* A pointer into path[] */
+  int wild;             /* True if the path contains any wildcards */
+/*
+ * Check the arguments.
+ */
+  if(!ef || !path) {
+    if(ef) {
+      _err_record_msg(ef->err, "ef_expand_file: NULL path argument",
+		      END_ERR_MSG);
+    };
+    errno = EINVAL;
+    return NULL;
+  };
+/*
+ * If the caller specified that the whole of path[] be matched,
+ * work out the corresponding length.
+ */
+  if(pathlen < 0 || pathlen > strlen(path))
+    pathlen = strlen(path);
+/*
+ * Discard previous expansion results.
+ */
+  ef_clear_files(ef);
+/*
+ * Preprocess the path, expanding ~/, ~user/ and $envvar references,
+ * using ef->path as a work directory and returning a pointer to
+ * a copy of the resulting pattern in the cache.
+ */
+  path = ef_expand_special(ef, path, pathlen);
+  if(!path)
+    return NULL;
+/*
+ * Clear the pathname buffer.
+ */
+  _pn_clear_path(ef->path);
+/*
+ * Does the pathname contain any wildcards?
+ */
+  for(wild=0,pptr=path; !wild && *pptr; pptr++) {
+    switch(*pptr) {
+    case '\\':                      /* Skip escaped characters */
+      if(pptr[1])
+	pptr++;
+      break; 
+    case '*': case '?': case '[':   /* A wildcard character? */
+      wild = 1;
+      break;
+    };
+  };
+/*
+ * If there are no wildcards to match, copy the current expanded
+ * path into the output array, removing backslash escapes while doing so.
+ */
+  if(!wild) {
+    if(ef_record_pathname(ef, path, 1))
+      return NULL;
+/*
+ * Does the filename exist?
+ */
+    ef->result.exists = _pu_file_exists(ef->result.files[0]);
+/*
+ * Match wildcards against existing files.
+ */
+  } else {
+/*
+ * Only existing files that match the pattern will be returned in the
+ * cache.
+ */
+    ef->result.exists = 1;
+/*
+ * Treat matching of the root-directory as a special case since it
+ * isn't contained in a directory.
+ */
+    if(strcmp(path, FS_ROOT_DIR) == 0) {
+      if(ef_record_pathname(ef, FS_ROOT_DIR, 0))
+	return NULL;
+    } else {
+/*
+ * What should the top level directory of the search be?
+ */
+      if(strncmp(path, FS_ROOT_DIR, FS_ROOT_DIR_LEN) == 0) {
+	dirname = FS_ROOT_DIR;
+	if(!_pn_append_to_path(ef->path, FS_ROOT_DIR, -1, 0)) {
+	  _err_record_msg(ef->err, "Insufficient memory to record path",
+			  END_ERR_MSG);
+	  return NULL;
+	};
+	path += FS_ROOT_DIR_LEN;
+      } else {
+	dirname = FS_PWD;
+      };
+/*
+ * Open the top-level directory of the search.
+ */
+      dnode = ef_open_dir(ef, dirname);
+      if(!dnode)
+	return NULL;
+/*
+ * Recursively match successive directory components of the path.
+ */
+      if(ef_match_relative_pathname(ef, dnode->dr, path, 0)) {
+	dnode = ef_close_dir(ef, dnode);
+	return NULL;
+      };
+/*
+ * Cleanup.
+ */
+      dnode = ef_close_dir(ef, dnode);
+    };
+/*
+ * No files matched?
+ */
+    if(ef->result.nfile < 1) {
+      _err_record_msg(ef->err, "No files match", END_ERR_MSG);
+      return NULL;
+    };
+/*
+ * Sort the pathnames that matched.
+ */
+    qsort(ef->result.files, ef->result.nfile, sizeof(ef->result.files[0]),
+	  ef_cmp_strings);
+  };
+/*
+ * Return the result container.
+ */
+  return &ef->result;
+}
+
+/*.......................................................................
+ * Attempt to recursively match the given pattern with the contents of
+ * the current directory, descending sub-directories as needed.
+ *
+ * Input:
+ *  ef      ExpandFile *  The pathname expansion resource object.
+ *  dr       DirReader *  The directory reader object of the directory
+ *                        to be searched.
+ *  pattern const char *  The pattern to match with files in the current
+ *                        directory.
+ *  separate       int    When appending a filename from the specified
+ *                        directory to ef->pathname, insert a directory
+ *                        separator between the existing pathname and
+ *                        the filename, unless separate is zero.
+ * Output:
+ *  return         int    0 - OK.
+ *                        1 - Error.
+ */
+static int ef_match_relative_pathname(ExpandFile *ef, DirReader *dr,
+				       const char *pattern, int separate)
+{
+  const char *nextp;  /* The pointer to the character that follows the part */
+                      /*  of the pattern that is to be matched with files */
+                      /*  in the current directory. */
+  char *file;         /* The name of the file being matched */
+  int pathlen;        /* The length of ef->pathname[] on entry to this */
+                      /*  function */
+/*
+ * Record the current length of the pathname string recorded in
+ * ef->pathname[].
+ */
+  pathlen = strlen(ef->path->name);
+/*
+ * Get a pointer to the character that follows the end of the part of
+ * the pattern that should be matched to files within the current directory.
+ * This will either point to a directory separator, or to the '\0' terminator
+ * of the pattern string.
+ */
+  for(nextp=pattern; *nextp && strncmp(nextp, FS_DIR_SEP, FS_DIR_SEP_LEN) != 0;
+      nextp++)
+    ;
+/*
+ * Read each file from the directory, attempting to match it to the
+ * current pattern.
+ */
+  while((file=_dr_next_file(dr)) != NULL) {
+/*
+ * Does the latest file match the pattern up to nextp?
+ */
+    if(ef_string_matches_pattern(file, pattern, file[0]=='.', nextp)) {
+/*
+ * Append the new directory entry to the current matching pathname.
+ */
+      if((separate && _pn_append_to_path(ef->path, FS_DIR_SEP, -1, 0)==NULL) ||
+	 _pn_append_to_path(ef->path, file, -1, 0)==NULL) {
+	_err_record_msg(ef->err, "Insufficient memory to record path",
+			END_ERR_MSG);
+	return 1;
+      };
+/*
+ * If we have reached the end of the pattern, record the accumulated
+ * pathname in the list of matching files.
+ */
+      if(*nextp == '\0') {
+	if(ef_record_pathname(ef, ef->path->name, 0))
+	  return 1;
+/*
+ * If the matching directory entry is a subdirectory, and the
+ * next character of the pattern is a directory separator,
+ * recursively call the current function to scan the sub-directory
+ * for matches.
+ */
+      } else if(_pu_path_is_dir(ef->path->name) &&
+		strncmp(nextp, FS_DIR_SEP, FS_DIR_SEP_LEN) == 0) {
+/*
+ * If the pattern finishes with the directory separator, then
+ * record the pathame as matching.
+ */
+	if(nextp[FS_DIR_SEP_LEN] == '\0') {
+	  if(ef_record_pathname(ef, ef->path->name, 0))
+	    return 1;
+/*
+ * Match files within the directory.
+ */
+	} else {
+	  DirNode *subdnode = ef_open_dir(ef, ef->path->name);
+	  if(subdnode) {
+	    if(ef_match_relative_pathname(ef, subdnode->dr,
+					   nextp+FS_DIR_SEP_LEN, 1)) {
+	      subdnode = ef_close_dir(ef, subdnode);
+	      return 1;
+	    };
+	    subdnode = ef_close_dir(ef, subdnode);
+	  };
+	};
+      };
+/*
+ * Remove the latest filename from the pathname string, so that
+ * another matching file can be appended.
+ */
+      ef->path->name[pathlen] = '\0';
+    };
+  };
+  return 0;
+}
+
+/*.......................................................................
+ * Record a new matching filename.
+ *
+ * Input:
+ *  ef        ExpandFile *  The filename-match resource object.
+ *  pathname  const char *  The pathname to record.
+ *  remove_escapes   int    If true, remove backslash escapes in the
+ *                          recorded copy of the pathname.
+ * Output:
+ *  return           int     0 - OK.
+ *                           1 - Error (ef->err will contain a
+ *                                      description of the error).
+ */
+static int ef_record_pathname(ExpandFile *ef, const char *pathname,
+			      int remove_escapes)
+{
+  char *copy;          /* The recorded copy of pathname[] */
+/*
+ * Attempt to make a copy of the pathname in the cache.
+ */
+  copy = ef_cache_pathname(ef, pathname, remove_escapes);
+  if(!copy)
+    return 1;
+/*
+ * If there isn't room to record a pointer to the recorded pathname in the
+ * array of files, attempt to extend the array.
+ */
+  if(ef->result.nfile + 1 > ef->files_dim) {
+    int files_dim = ef->files_dim + MATCH_BLK_FACT;
+    char **files = (char **) realloc(ef->result.files,
+				     files_dim * sizeof(files[0]));
+    if(!files) {
+      _err_record_msg(ef->err,
+	     "Insufficient memory to record all of the matching filenames",
+	     END_ERR_MSG);
+      errno = ENOMEM;
+      return 1;
+    };
+    ef->result.files = files;
+    ef->files_dim = files_dim;
+  };
+/*
+ * Record a pointer to the new match.
+ */
+  ef->result.files[ef->result.nfile++] = copy;
+  return 0;
+}
+
+/*.......................................................................
+ * Record a pathname in the cache.
+ *
+ * Input:
+ *  ef       ExpandFile *  The filename-match resource object.
+ *  pathname       char *  The pathname to record.
+ *  remove_escapes  int    If true, remove backslash escapes in the
+ *                         copy of the pathname.
+ * Output:
+ *  return         char *  The pointer to the copy of the pathname.
+ *                         On error NULL is returned and a description
+ *                         of the error is left in ef->err.
+ */
+static char *ef_cache_pathname(ExpandFile *ef, const char *pathname,
+			       int remove_escapes)
+{
+  char *copy = _sg_store_string(ef->sg, pathname, remove_escapes);
+  if(!copy)
+    _err_record_msg(ef->err, "Insufficient memory to store pathname",
+		    END_ERR_MSG);
+  return copy;
+}
+
+/*.......................................................................
+ * Clear the results of the previous expansion operation, ready for the
+ * next.
+ *
+ * Input:
+ *  ef    ExpandFile *  The pathname expansion resource object.
+ */
+static void ef_clear_files(ExpandFile *ef)
+{
+  _clr_StringGroup(ef->sg);
+  _pn_clear_path(ef->path);
+  ef->result.exists = 0;
+  ef->result.nfile = 0;
+  _err_clear_msg(ef->err);
+  return;
+}
+
+/*.......................................................................
+ * Get a new directory reader object from the cache.
+ *
+ * Input:
+ *  ef        ExpandFile *  The pathname expansion resource object.
+ *  pathname  const char *  The pathname of the directory.
+ * Output:
+ *  return       DirNode *  The cache entry of the new directory reader,
+ *                          or NULL on error. On error, ef->err will
+ *                          contain a description of the error.
+ */
+static DirNode *ef_open_dir(ExpandFile *ef, const char *pathname)
+{
+  char *errmsg = NULL;  /* An error message from a called function */
+  DirNode *node;        /* The cache node used */
+/*
+ * Get the directory reader cache.
+ */
+  DirCache *cache = &ef->cache;
+/*
+ * Extend the cache if there are no free cache nodes.
+ */
+  if(!cache->next) {
+    node = (DirNode *) _new_FreeListNode(cache->mem);
+    if(!node) {
+      _err_record_msg(ef->err, "Insufficient memory to open a new directory",
+		      END_ERR_MSG);
+      return NULL;
+    };
+/*
+ * Initialize the cache node.
+ */
+    node->next = NULL;
+    node->prev = NULL;
+    node->dr = NULL;
+/*
+ * Allocate a directory reader object.
+ */
+    node->dr = _new_DirReader();
+    if(!node->dr) {
+      _err_record_msg(ef->err, "Insufficient memory to open a new directory",
+		      END_ERR_MSG);
+      node = (DirNode *) _del_FreeListNode(cache->mem, node);
+      return NULL;
+    };
+/*
+ * Append the node to the cache list.
+ */
+    node->prev = cache->tail;
+    if(cache->tail)
+      cache->tail->next = node;
+    else
+      cache->head = node;
+    cache->next = cache->tail = node;
+  };
+/*
+ * Get the first unused node, but don't remove it from the list yet.
+ */
+  node = cache->next;
+/*
+ * Attempt to open the specified directory.
+ */
+  if(_dr_open_dir(node->dr, pathname, &errmsg)) {
+    _err_record_msg(ef->err, errmsg, END_ERR_MSG);
+    return NULL;
+  };
+/*
+ * Now that we have successfully opened the specified directory,
+ * remove the cache node from the list, and relink the list around it.
+ */
+  cache->next = node->next;
+  if(node->prev)
+    node->prev->next = node->next;
+  else
+    cache->head = node->next;
+  if(node->next)
+    node->next->prev = node->prev;
+  else
+    cache->tail = node->prev;
+  node->next = node->prev = NULL;
+/*
+ * Return the successfully initialized cache node to the caller.
+ */
+  return node;
+}
+
+/*.......................................................................
+ * Return a directory reader object to the cache, after first closing
+ * the directory that it was managing.
+ *
+ * Input:
+ *  ef    ExpandFile *  The pathname expansion resource object.
+ *  node     DirNode *  The cache entry of the directory reader, as returned
+ *                      by ef_open_dir().
+ * Output:
+ *  return   DirNode *  The deleted DirNode (ie. allways NULL).
+ */
+static DirNode *ef_close_dir(ExpandFile *ef, DirNode *node)
+{
+/*
+ * Get the directory reader cache.
+ */
+  DirCache *cache = &ef->cache;
+/*
+ * Close the directory.
+ */
+  _dr_close_dir(node->dr);
+/*
+ * Return the node to the tail of the cache list.
+ */
+  node->next = NULL;
+  node->prev = cache->tail;
+  if(cache->tail)
+    cache->tail->next = node;
+  else
+    cache->head = cache->tail = node;
+  if(!cache->next)
+    cache->next = node;
+  return NULL;
+}
+
+/*.......................................................................
+ * Return non-zero if the specified file name matches a given glob
+ * pattern.
+ *
+ * Input:
+ *  file     const char *  The file-name component to be matched to the pattern.
+ *  pattern  const char *  The start of the pattern to match against file[].
+ *  xplicit         int    If non-zero, the first character must be matched
+ *                         explicitly (ie. not with a wildcard).
+ *  nextp    const char *  The pointer to the the character following the
+ *                         end of the pattern in pattern[].
+ * Output:
+ *  return    int          0 - Doesn't match.
+ *                         1 - The file-name string matches the pattern.
+ */
+static int ef_string_matches_pattern(const char *file, const char *pattern,
+				      int xplicit, const char *nextp)
+{
+  const char *pptr = pattern; /* The pointer used to scan the pattern */
+  const char *fptr = file;    /* The pointer used to scan the filename string */
+/*
+ * Match each character of the pattern in turn.
+ */
+  while(pptr < nextp) {
+/*
+ * Handle the next character of the pattern.
+ */
+    switch(*pptr) {
+/*
+ * A match zero-or-more characters wildcard operator.
+ */
+    case '*':
+/*
+ * Skip the '*' character in the pattern.
+ */
+      pptr++;
+/*
+ * If wildcards aren't allowed, the pattern doesn't match.
+ */
+      if(xplicit)
+	return 0;
+/*
+ * If the pattern ends with a the '*' wildcard, then the
+ * rest of the filename matches this.
+ */
+      if(pptr >= nextp)
+	return 1;
+/*
+ * Using the wildcard to match successively longer sections of
+ * the remaining characters of the filename, attempt to match
+ * the tail of the filename against the tail of the pattern.
+ */
+      for( ; *fptr; fptr++) {
+	if(ef_string_matches_pattern(fptr, pptr, 0, nextp))
+	  return 1;
+      };
+      return 0; /* The pattern following the '*' didn't match */
+      break;
+/*
+ * A match-one-character wildcard operator.
+ */
+    case '?':
+/*
+ * If there is a character to be matched, skip it and advance the
+ * pattern pointer.
+ */
+      if(!xplicit && *fptr) {
+        fptr++;
+        pptr++;
+/*
+ * If we hit the end of the filename string, there is no character
+ * matching the operator, so the string doesn't match.
+ */
+      } else {
+        return 0;
+      };
+      break;
+/*
+ * A character range operator, with the character ranges enclosed
+ * in matching square brackets.
+ */
+    case '[':
+      if(xplicit || !ef_matches_range(*fptr++, ++pptr, &pptr))
+        return 0;
+      break;
+/*
+ * A backslash in the pattern prevents the following character as
+ * being seen as a special character.
+ */
+    case '\\':
+      pptr++;
+      /* Note fallthrough to default */
+/*
+ * A normal character to be matched explicitly.
+ */
+    default:
+      if(*fptr == *pptr) {
+        fptr++;
+        pptr++;
+      } else {
+        return 0;
+      };
+      break;
+    };
+/*
+ * After passing the first character, turn off the explicit match
+ * requirement.
+ */
+    xplicit = 0;
+  };
+/*
+ * To get here the pattern must have been exhausted. If the filename
+ * string matched, then the filename string must also have been
+ * exhausted.
+ */
+  return *fptr == '\0';
+}
+
+/*.......................................................................
+ * Match a character range expression terminated by an unescaped close
+ * square bracket.
+ *
+ * Input:
+ *  c               int     The character to be matched with the range
+ *                          pattern.
+ *  pattern  const char *   The range pattern to be matched (ie. after the
+ *                          initiating '[' character).
+ *  endp     const char **  On output a pointer to the character following the
+ *                          range expression will be assigned to *endp.
+ * Output:
+ *  return          int     0 - Doesn't match.
+ *                          1 - The character matched.
+ */
+static int ef_matches_range(int c, const char *pattern, const char **endp)
+{
+  const char *pptr = pattern;  /* The pointer used to scan the pattern */
+  int invert = 0;              /* True to invert the sense of the match */
+  int matched = 0;             /* True if the character matched the pattern */
+/*
+ * If the first character is a caret, the sense of the match is
+ * inverted and only if the character isn't one of those in the
+ * range, do we say that it matches.
+ */
+  if(*pptr == '^') {
+    pptr++;
+    invert = 1;
+  };
+/*
+ * The hyphen is only a special character when it follows the first
+ * character of the range (not including the caret).
+ */
+  if(*pptr == '-') {
+    pptr++;
+    if(c == '-') {
+      *endp = pptr;
+      matched = 1;
+    };
+/*
+ * Skip other leading '-' characters since they make no sense.
+ */
+    while(*pptr == '-')
+      pptr++;
+  };
+/*
+ * The hyphen is only a special character when it follows the first
+ * character of the range (not including the caret or a hyphen).
+ */
+  if(*pptr == ']') {
+    pptr++;
+    if(c == ']') {
+      *endp = pptr;
+      matched = 1;
+    };
+  };
+/*
+ * Having dealt with the characters that have special meanings at
+ * the beginning of a character range expression, see if the
+ * character matches any of the remaining characters of the range,
+ * up until a terminating ']' character is seen.
+ */
+  while(!matched && *pptr && *pptr != ']') {
+/*
+ * Is this a range of characters signaled by the two end characters
+ * separated by a hyphen?
+ */
+    if(*pptr == '-') {
+      if(pptr[1] != ']') {
+        if(c >= pptr[-1] && c <= pptr[1])
+	  matched = 1;
+	pptr += 2;
+      };
+/*
+ * A normal character to be compared directly.
+ */
+    } else if(*pptr++ == c) {
+      matched = 1;
+    };
+  };
+/*
+ * Find the terminating ']'.
+ */
+  while(*pptr && *pptr != ']')
+    pptr++;
+/*
+ * Did we find a terminating ']'?
+ */
+  if(*pptr == ']') {
+    *endp = pptr + 1;
+    return matched ? !invert : invert;
+  };
+/*
+ * If the pattern didn't end with a ']' then it doesn't match, regardless
+ * of the value of the required sense of the match.
+ */
+  *endp = pptr;
+  return 0;
+}
+
+/*.......................................................................
+ * This is a qsort() comparison function used to sort strings.
+ *
+ * Input:
+ *  v1, v2   void *  Pointers to the two strings to be compared.
+ * Output:
+ *  return    int    -1 -> v1 < v2.
+ *                    0 -> v1 == v2
+ *                    1 -> v1 > v2
+ */
+static int ef_cmp_strings(const void *v1, const void *v2)
+{
+  char * const *s1 = (char * const *) v1;
+  char * const *s2 = (char * const *) v2;
+  return strcmp(*s1, *s2);
+}
+
+/*.......................................................................
+ * Preprocess a path, expanding ~/, ~user/ and $envvar references, using
+ * ef->path as a work buffer, then copy the result into a cache entry,
+ * and return a pointer to this copy.
+ *
+ * Input:
+ *  ef    ExpandFile *  The resource object of the file matcher.
+ *  pathlen      int    The length of the prefix of path[] to be expanded.
+ * Output:
+ *  return      char *  A pointer to a copy of the output path in the
+ *                      cache. On error NULL is returned, and a description
+ *                      of the error is left in ef->err.
+ */
+static char *ef_expand_special(ExpandFile *ef, const char *path, int pathlen)
+{
+  int spos;      /* The index of the start of the path segment that needs */
+                 /*  to be copied from path[] to the output pathname. */
+  int ppos;      /* The index of a character in path[] */
+  char *pptr;    /* A pointer into the output path */
+  int escaped;   /* True if the previous character was a '\' */
+  int i;
+/*
+ * Clear the pathname buffer.
+ */
+  _pn_clear_path(ef->path);
+/*
+ * We need to perform two passes, one to expand environment variables
+ * and a second to do tilde expansion. This caters for the case
+ * where an initial dollar expansion yields a tilde expression.
+ */
+  escaped = 0;
+  for(spos=ppos=0; ppos < pathlen; ppos++) {
+    int c = path[ppos];
+    if(escaped) {
+      escaped = 0;
+    } else if(c == '\\') {
+      escaped = 1;
+    } else if(c == '$') {
+      int envlen;   /* The length of the environment variable */
+      char *value;  /* The value of the environment variable */
+/*
+ * Record the preceding unrecorded part of the pathname.
+ */
+      if(spos < ppos && _pn_append_to_path(ef->path, path + spos, ppos-spos, 0)
+	 == NULL) {
+	_err_record_msg(ef->err, "Insufficient memory to expand path",
+			END_ERR_MSG);
+	return NULL;
+      };
+/*
+ * Skip the dollar.
+ */
+      ppos++;
+/*
+ * Copy the environment variable name that follows the dollar into
+ * ef->envnam[], stopping if a directory separator or end of string
+ * is seen.
+ */
+      for(envlen=0; envlen<ENV_LEN && ppos < pathlen &&
+	  strncmp(path + ppos, FS_DIR_SEP, FS_DIR_SEP_LEN); envlen++)
+	ef->envnam[envlen] = path[ppos++];
+/*
+ * If the username overflowed the buffer, treat it as invalid (note that
+ * on most unix systems only 8 characters are allowed in a username,
+ * whereas our ENV_LEN is much bigger than that.
+ */
+      if(envlen >= ENV_LEN) {
+	_err_record_msg(ef->err, "Environment variable name too long",
+			END_ERR_MSG);
+	return NULL;
+      };
+/*
+ * Terminate the environment variable name.
+ */
+      ef->envnam[envlen] = '\0';
+/*
+ * Lookup the value of the environment variable.
+ */
+      value = getenv(ef->envnam);
+      if(!value) {
+	_err_record_msg(ef->err, "No expansion found for: $", ef->envnam,
+			END_ERR_MSG);
+	return NULL;
+      };
+/*
+ * Copy the value of the environment variable into the output pathname.
+ */
+      if(_pn_append_to_path(ef->path, value, -1, 0) == NULL) {
+	_err_record_msg(ef->err, "Insufficient memory to expand path",
+			END_ERR_MSG);
+	return NULL;
+      };
+/*
+ * Record the start of the uncopied tail of the input pathname.
+ */
+      spos = ppos;
+    };
+  };
+/*
+ * Record the uncopied tail of the pathname.
+ */
+  if(spos < ppos && _pn_append_to_path(ef->path, path + spos, ppos-spos, 0)
+     == NULL) {
+    _err_record_msg(ef->err, "Insufficient memory to expand path", END_ERR_MSG);
+    return NULL;
+  };
+/*
+ * If the first character of the resulting pathname is a tilde,
+ * then attempt to substitute the home directory of the specified user.
+ */
+  pptr = ef->path->name;
+  if(*pptr == '~' && path[0] != '\\') {
+    int usrlen;           /* The length of the username following the tilde */
+    const char *homedir;  /* The home directory of the user */
+    int homelen;          /* The length of the home directory string */
+    int plen;             /* The current length of the path */
+    int skip=0;           /* The number of characters to skip after the ~user */
+/*
+ * Get the current length of the output path.
+ */
+    plen = strlen(ef->path->name);
+/*
+ * Skip the tilde.
+ */
+    pptr++;
+/*
+ * Copy the optional username that follows the tilde into ef->usrnam[].
+ */
+    for(usrlen=0; usrlen<USR_LEN && *pptr &&
+	strncmp(pptr, FS_DIR_SEP, FS_DIR_SEP_LEN); usrlen++)
+      ef->usrnam[usrlen] = *pptr++;
+/*
+ * If the username overflowed the buffer, treat it as invalid (note that
+ * on most unix systems only 8 characters are allowed in a username,
+ * whereas our USR_LEN is much bigger than that.
+ */
+    if(usrlen >= USR_LEN) {
+      _err_record_msg(ef->err, "Username too long", END_ERR_MSG);
+      return NULL;
+    };
+/*
+ * Terminate the username string.
+ */
+    ef->usrnam[usrlen] = '\0';
+/*
+ * Lookup the home directory of the user.
+ */
+    homedir = _hd_lookup_home_dir(ef->home, ef->usrnam);
+    if(!homedir) {
+      _err_record_msg(ef->err, _hd_last_home_dir_error(ef->home), END_ERR_MSG);
+      return NULL;
+    };
+    homelen = strlen(homedir);
+/*
+ * ~user and ~ are usually followed by a directory separator to
+ * separate them from the file contained in the home directory.
+ * If the home directory is the root directory, then we don't want
+ * to follow the home directory by a directory separator, so we must
+ * erase it.
+ */
+    if(strcmp(homedir, FS_ROOT_DIR) == 0 &&
+       strncmp(pptr, FS_DIR_SEP, FS_DIR_SEP_LEN) == 0) {
+      skip = FS_DIR_SEP_LEN;
+    };
+/*
+ * If needed, increase the size of the pathname buffer to allow it
+ * to accomodate the home directory instead of the tilde expression.
+ * Note that pptr may not be valid after this call.
+ */
+    if(_pn_resize_path(ef->path, plen - usrlen - 1 - skip + homelen)==NULL) {
+      _err_record_msg(ef->err, "Insufficient memory to expand filename",
+		      END_ERR_MSG);
+      return NULL;
+    };
+/*
+ * Move the part of the pathname that follows the tilde expression to
+ * the end of where the home directory will need to be inserted.
+ */
+    memmove(ef->path->name + homelen,
+	    ef->path->name + 1 + usrlen + skip, plen - usrlen - 1 - skip+1);
+/*
+ * Write the home directory at the beginning of the string.
+ */
+    for(i=0; i<homelen; i++)
+      ef->path->name[i] = homedir[i];
+  };
+/*
+ * Copy the result into the cache, and return a pointer to the copy.
+ */
+  return ef_cache_pathname(ef, ef->path->name, 0);
+}
+
+/*.......................................................................
+ * Return a description of the last path-expansion error that occurred.
+ *
+ * Input:
+ *  ef     ExpandFile *   The path-expansion resource object.
+ * Output:
+ *  return       char *   The description of the last error.
+ */
+const char *ef_last_error(ExpandFile *ef)
+{
+  return ef ? _err_get_msg(ef->err) : "NULL ExpandFile argument";
+}
+
+/*.......................................................................
+ * Print out an array of matching files.
+ *
+ * Input:
+ *  result  FileExpansion *   The container of the sorted array of
+ *                            expansions.
+ *  fp               FILE *   The output stream to write to.
+ *  term_width        int     The width of the terminal.
+ * Output:
+ *  return            int     0 - OK.
+ *                            1 - Error.
+ */
+int ef_list_expansions(FileExpansion *result, FILE *fp, int term_width)
+{
+  return _ef_output_expansions(result, _io_write_stdio, fp, term_width);
+}
+
+/*.......................................................................
+ * Print out an array of matching files via a callback.
+ *
+ * Input:
+ *  result  FileExpansion *  The container of the sorted array of
+ *                           expansions.
+ *  write_fn    GlWriteFn *  The function to call to write the
+ *                           expansions or 0 to discard the output.
+ *  data             void *  Anonymous data to pass to write_fn().
+ *  term_width        int    The width of the terminal.
+ * Output:
+ *  return            int    0 - OK.
+ *                           1 - Error.
+ */
+int _ef_output_expansions(FileExpansion *result, GlWriteFn *write_fn,
+			  void *data, int term_width)
+{
+  EfListFormat fmt; /* List formatting information */
+  int lnum;          /* The sequential number of the line to print next */
+/*
+ * Not enough space to list anything?
+ */
+  if(term_width < 1)
+    return 0;
+/*
+ * Do we have a callback to write via, and any expansions to be listed?
+ */
+  if(write_fn && result && result->nfile>0) {
+/*
+ * Work out how to arrange the listing into fixed sized columns.
+ */
+    ef_plan_listing(result, term_width, &fmt);
+/*
+ * Print the listing to the specified stream.
+ */
+    for(lnum=0; lnum < fmt.nline; lnum++) {
+      if(ef_format_line(result, &fmt, lnum, write_fn, data))
+	return 1;
+    };
+  };
+  return 0;
+}
+
+/*.......................................................................
+ * Work out how to arrange a given array of completions into a listing
+ * of one or more fixed size columns.
+ *
+ * Input:
+ *  result   FileExpansion *   The set of completions to be listed.
+ *  term_width         int     The width of the terminal. A lower limit of
+ *                             zero is quietly enforced.
+ * Input/Output:
+ *  fmt       EfListFormat *   The formatting information will be assigned
+ *                             to the members of *fmt.
+ */
+static void ef_plan_listing(FileExpansion *result, int term_width,
+			    EfListFormat *fmt)
+{
+  int maxlen;    /* The length of the longest matching string */
+  int i;
+/*
+ * Ensure that term_width >= 0.
+ */
+  if(term_width < 0)
+    term_width = 0;
+/*
+ * Start by assuming the worst case, that either nothing will fit
+ * on the screen, or that there are no matches to be listed.
+ */
+  fmt->term_width = term_width;
+  fmt->column_width = 0;
+  fmt->nline = fmt->ncol = 0;
+/*
+ * Work out the maximum length of the matching strings.
+ */
+  maxlen = 0;
+  for(i=0; i<result->nfile; i++) {
+    int len = strlen(result->files[i]);
+    if(len > maxlen)
+      maxlen = len;
+  };
+/*
+ * Nothing to list?
+ */
+  if(maxlen == 0)
+    return;
+/*
+ * Split the available terminal width into columns of
+ * maxlen + EF_COL_SEP characters.
+ */
+  fmt->column_width = maxlen;
+  fmt->ncol = fmt->term_width / (fmt->column_width + EF_COL_SEP);
+/*
+ * If the column width is greater than the terminal width, zero columns
+ * will have been selected. Set a lower limit of one column. Leave it
+ * up to the caller how to deal with completions who's widths exceed
+ * the available terminal width.
+ */
+  if(fmt->ncol < 1)
+    fmt->ncol = 1;
+/*
+ * How many lines of output will be needed?
+ */
+  fmt->nline = (result->nfile + fmt->ncol - 1) / fmt->ncol;
+  return;
+}
+
+/*.......................................................................
+ * Render one line of a multi-column listing of completions, using a
+ * callback function to pass the output to an arbitrary destination.
+ *
+ * Input:
+ *  result   FileExpansion *  The container of the sorted array of
+ *                            completions.
+ *  fmt       EfListFormat *  Formatting information.
+ *  lnum               int    The index of the line to print, starting
+ *                            from 0, and incrementing until the return
+ *                            value indicates that there is nothing more
+ *                            to be printed.
+ *  write_fn     GlWriteFn *  The function to call to write the line, or
+ *                            0 to discard the output.
+ *  data              void *  Anonymous data to pass to write_fn().
+ * Output:
+ *  return             int    0 - Line printed ok.
+ *                            1 - Nothing to print.
+ */
+static int ef_format_line(FileExpansion *result, EfListFormat *fmt, int lnum,
+			  GlWriteFn *write_fn, void *data)
+{
+  int col;             /* The index of the list column being output */
+/*
+ * If the line index is out of bounds, there is nothing to be written.
+ */
+  if(lnum < 0 || lnum >= fmt->nline)
+    return 1;
+/*
+ * If no output function has been provided, return as though the line
+ * had been printed.
+ */
+  if(!write_fn)
+    return 0;
+/*
+ * Print the matches in 'ncol' columns, sorted in line order within each
+ * column.
+ */
+  for(col=0; col < fmt->ncol; col++) {
+    int m = col*fmt->nline + lnum;
+/*
+ * Is there another match to be written? Note that in general
+ * the last line of a listing will have fewer filled columns
+ * than the initial lines.
+ */
+    if(m < result->nfile) {
+      char *file = result->files[m];
+/*
+ * How long are the completion and type-suffix strings?
+ */
+      int flen = strlen(file);
+/*
+ * Write the completion string.
+ */
+      if(write_fn(data, file, flen) != flen)
+	return 1;
+/*
+ * If another column follows the current one, pad to its start with spaces.
+ */
+      if(col+1 < fmt->ncol) {
+/*
+ * The following constant string of spaces is used to pad the output.
+ */
+	static const char spaces[] = "                    ";
+	static const int nspace = sizeof(spaces) - 1;
+/*
+ * Pad to the next column, using as few sub-strings of the spaces[]
+ * array as possible.
+ */
+	int npad = fmt->column_width + EF_COL_SEP - flen;
+	while(npad>0) {
+	  int n = npad > nspace ? nspace : npad;
+	  if(write_fn(data, spaces + nspace - n, n) != n)
+	    return 1;
+	  npad -= n;
+	};
+      };
+    };
+  };
+/*
+ * Start a new line.
+ */
+  {
+    char s[] = "\r\n";
+    int n = strlen(s);
+    if(write_fn(data, s, n) != n)
+      return 1;
+  };
+  return 0;
+}
+
+#endif  /* ifndef WITHOUT_FILE_SYSTEM */