expand.c

xorp源码hg

/*
 * 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 200

struct 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;
    };