/* * Copyright (c) 2000, 2001 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. */#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"/* * 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 max length of the error-reporting string. There is no point * in this being longer than the width of a typical terminal window. * In composing error messages, I have assumed that this number is * at least 80, so you don't decrease it below this number. */#define ERRLEN 200struct ExpandFile {  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 */  char errmsg[ERRLEN+1];  /* Error-report buffer */  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);/*....................................................................... * 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) {    fprintf(stderr, "new_ExpandFile: Insufficient memory.\n");    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->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';  ef->errmsg[0] = '\0';/* * 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("new_ExpandFile", 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) {    fprintf(stderr,        "new_ExpandFile: Insufficient memory to allocate array of files.\n");    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("del_ExpandFile", 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 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)      strcpy(ef->errmsg, "ef_expand_file: NULL path argument");    else      fprintf(stderr, "ef_expand_file: NULL argument(s).\n");    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)) {	  strcpy(ef->errmsg, "Insufficient memory to record path");	  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) {      strcpy(ef->errmsg, "No files match");      return NULL;    };