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