home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / language / slperl / wildmat.c < prev   
Encoding:
C/C++ Source or Header  |  1993-10-23  |  11.8 KB  |  508 lines
  1. /*  $Revision: 4.0.1.1 $
  2. **
  3. **  Do shell-style pattern matching for ?, \, [], and * characters.
  4. **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
  5. **  could cause a segmentation violation.  It is 8bit clean.
  6. **
  7. **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  8. **  Rich $alz is now <rsalz@bbn.com>.
  9. **  April, 1991:  Replaced mutually-recursive calls with in-line code
  10. **  for the star character.
  11. **
  12. **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
  13. **  This can greatly speed up failing wildcard patterns.  For example:
  14. **    pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  15. **    text 1:     -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  16. **    text 2:     -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
  17. **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  18. **  the ABORT, then it takes 22310 calls to fail.  Ugh.  The following
  19. **  explanation is from Lars:
  20. **  The precondition that must be fulfilled is that DoMatch will consume
  21. **  at least one character in text.  This is true if *p is neither '*' nor
  22. **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
  23. **  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
  24. **  FALSE, each star-loop has to run to the end of the text; with ABORT
  25. **  only the last one does.
  26. **
  27. **  Once the control of one instance of DoMatch enters the star-loop, that
  28. **  instance will return either TRUE or ABORT, and any calling instance
  29. **  will therefore return immediately after (without calling recursively
  30. **  again).  In effect, only one star-loop is ever active.  It would be
  31. **  possible to modify the code to maintain this context explicitly,
  32. **  eliminating all recursive calls at the cost of some complication and
  33. **  loss of clarity (and the ABORT stuff seems to be unclear enough by
  34. **  itself).  I think it would be unwise to try to get this into a
  35. **  released version unless you have a good test data base to try it out
  36. **  on.
  37. */
  38.  
  39. #define TRUE            1
  40. #define FALSE            0
  41. #define ABORT            -1
  42.  
  43.  
  44.     /* What character marks an inverted character class? */
  45. #define NEGATE_CLASS        '^'
  46.     /* Is "*" a common pattern? */
  47. #define OPTIMIZE_JUST_STAR
  48.     /* Do tar(1) matching rules, which ignore a trailing slash? */
  49. #undef MATCH_TAR_PATTERN
  50.  
  51.  
  52. /*
  53. **  Match text and p, return TRUE, FALSE, or ABORT.
  54. */
  55. static int
  56. DoMatch(text, p)
  57.     char    *text;
  58.     char    *p;
  59. {
  60.     int    last;
  61.     int    matched;
  62.     int    reverse;
  63.  
  64.     for ( ; *p; text++, p++) {
  65.     if (*text == '\0' && *p != '*')
  66.         return ABORT;
  67.     switch (*p) {
  68.     case '\\':
  69.         /* Literal match with following character. */
  70.         p++;
  71.         /* FALLTHROUGH */
  72.     default:
  73.         if (*text != *p)
  74.         return FALSE;
  75.         continue;
  76.     case '?':
  77.         /* Match anything. */
  78.         continue;
  79.     case '*':
  80.         while (*++p == '*')
  81.         /* Consecutive stars act just like one. */
  82.         continue;
  83.         if (*p == '\0')
  84.         /* Trailing star matches everything. */
  85.         return TRUE;
  86.         while (*text)
  87.         if ((matched = DoMatch(text++, p)) != FALSE)
  88.             return matched;
  89.         return ABORT;
  90.     case '[':
  91.         reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
  92.         if (reverse)
  93.         /* Inverted character class. */
  94.         p++;
  95.         for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
  96.         /* This next line requires a good C compiler. */
  97.         if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
  98.             matched = TRUE;
  99.         if (matched == reverse)
  100.         return FALSE;
  101.         continue;
  102.     }
  103.     }
  104.  
  105. #ifdef    MATCH_TAR_PATTERN
  106.     if (*text == '/')
  107.     return TRUE;
  108. #endif    /* MATCH_TAR_ATTERN */
  109.     return *text == '\0';
  110. }
  111.  
  112.  
  113. /*
  114. **  User-level routine.  Returns TRUE or FALSE.
  115. */
  116. int
  117. wildmat(text, p)
  118.     char    *text;
  119.     char    *p;
  120. {
  121. #ifdef    OPTIMIZE_JUST_STAR
  122.     if (p[0] == '*' && p[1] == '\0')
  123.     return TRUE;
  124. #endif    /* OPTIMIZE_JUST_STAR */
  125.     return DoMatch(text, p) == TRUE;
  126. }
  127.  
  128. #include <stdio.h>
  129. #include <sys/types.h>
  130. #include <dirent.h>
  131. #include <sys/stat.h>
  132. #if __STDC__
  133. #ifdef unix
  134. #define _SIZE_T    /* unix defines size_t in sys/types.h */
  135. #endif
  136. #ifndef _COMPILER_H
  137. #  include <compiler.h>
  138. #endif
  139. #include <stddef.h>
  140. #include <stdlib.h>
  141. #else
  142. extern char *malloc(), *realloc();
  143. extern char *rindex(),  *strdup();
  144. #define __PROTO(x) ()
  145. #endif
  146. #include <string.h>
  147.  
  148. #define MAX_DIR    32    /* max depth of dir recursion */
  149. static struct {
  150.     char *dir, *patt;
  151. } dir_stack[MAX_DIR];
  152. static int stack_p;
  153. static char **matches;
  154. static int nmatches;
  155.  
  156. static void *ck_memalloc __PROTO((void *));
  157. #define ck_strdup(p) ck_memalloc(strdup(p))
  158. #define ck_malloc(s) ck_memalloc(malloc(s))
  159. #define ck_realloc(p, s) ck_memalloc(realloc(p, s))
  160.  
  161.  
  162. #define DEBUGX(x) 
  163.  
  164. /*
  165.  * return true if patt contains a wildcard char
  166.  */
  167. int contains_wild(patt)
  168. char *patt;
  169. {
  170.     char c;
  171.     char *p;
  172.  
  173.     /* only check for wilds in the basename part of the pathname only */
  174.     if((p = rindex(patt, '/')) == NULL)
  175.     p = rindex(patt, '\\');
  176.     if(!p)
  177.     p = patt;
  178.  
  179.     while((c = *p++))
  180.     if((c == '*') || (c == '?') || (c == '['))
  181.         return 1;
  182.     return 0;
  183. }
  184.  
  185. #ifndef ZOO
  186. void free_all()
  187. {
  188.     char **p;
  189.  
  190.     if(!matches)
  191.     return;
  192.  
  193.     for(p = matches; *p; p++)
  194.     free(*p);
  195.     free(matches);
  196.     matches = NULL;
  197. }
  198. #endif
  199.  
  200. static void push(dir, patt)
  201. char *dir;
  202. char *patt;
  203. {
  204.     if(stack_p < (MAX_DIR - 2))
  205.     stack_p++;
  206.     else
  207.     {
  208.     fprintf(stderr,"directory stack overflow\n");
  209.     exit(99);
  210.     }
  211.     dir_stack[stack_p].dir = dir;
  212.     dir_stack[stack_p].patt = patt;
  213. }
  214.  
  215. /*
  216.  * glob patt
  217.  * if decend_dir is true, recursively decend any directories encountered.
  218.  * returns pointer to all matches encountered.
  219.  * if the initial patt is a directory, and decend_dir is true, it is
  220.  * equivalent to specifying the pattern "patt\*"
  221.  *
  222.  * Restrictions:
  223.  *  - handles wildcards only in the base part of a pathname
  224.  *    ie: will not handle \foo\*\bar\ (wildcard in the middle of pathname)
  225.  *
  226.  *  - max dir recursion is MAX_DIR
  227.  *
  228.  *  - on certain failures it will just skip potential matches as if they
  229.  *    were not present.
  230.  *
  231.  *  ++jrb    bammi@cadence.com
  232.  */
  233. static char **do_match __PROTO((int decend_dir));
  234.  
  235. char **glob(patt, decend_dir)
  236. char *patt;
  237. int decend_dir;
  238. {
  239.     char *dir, *basepatt, *p;
  240.     struct stat s;
  241.  
  242.     DEBUGX((fprintf(stderr,"glob(%s, %d)\n", patt, decend_dir)));
  243.     matches = NULL;
  244.     nmatches = 0;
  245.     stack_p = -1;
  246.  
  247.     /* first check for wildcards */
  248.     if(contains_wild(patt))
  249.     {
  250.     /* break it up into dir and base patt, do_matches and return */
  251.     p = ck_strdup(patt);
  252.     if((basepatt = rindex(p, '/')) == NULL)
  253.         basepatt = rindex(p, '\\');
  254.         if(basepatt)
  255.         {
  256.         dir = p;
  257.         *basepatt++ = '\0';
  258.         basepatt = ck_strdup(basepatt);
  259.         }
  260.         else
  261.         {
  262.         dir = ck_strdup(".");
  263.         basepatt = p;
  264.         }
  265.  
  266.         if(strcmp(basepatt, "*.*") == 0)
  267.         {
  268.             /* the desktop, and other braindead shells strike again */
  269.             basepatt[1] = '\0';
  270.         }
  271.     push(dir, basepatt);
  272.     DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
  273.     return do_match(decend_dir);
  274.     }
  275.  
  276.     /* if no wilds, check for dir */
  277.     if(decend_dir && (!stat(patt, &s)))
  278.     {
  279.     if((s.st_mode & S_IFMT) == S_IFDIR)
  280.     {   /* is a dir */
  281.         size_t len = strlen(patt);
  282.         
  283.         dir = ck_strdup(patt);
  284.         --len;
  285.         if(len && ((dir[len] == '/') 
  286. #ifdef atarist
  287.            || (dir[len] == '\\')
  288. #endif
  289.          ))
  290.         dir[len] = '\0';
  291.         basepatt = ck_strdup("*");
  292.         push(dir, basepatt);
  293.         DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
  294.         return do_match(decend_dir);
  295.         }
  296.     }
  297.     return NULL;
  298. }
  299.  
  300. static char **do_match(decend_dir)
  301. int decend_dir;
  302. {
  303.     DIR *dirp;
  304.     struct dirent *d;
  305.     struct stat s;
  306.     char *dir, *basepatt;
  307.  
  308.     while(stack_p >= 0)
  309.     {
  310.     dir = ck_strdup(dir_stack[stack_p].dir); 
  311.     free(dir_stack[stack_p].dir);
  312.         basepatt = ck_strdup(dir_stack[stack_p].patt);
  313.     free(dir_stack[stack_p--].patt);
  314.     
  315.         DEBUGX((fprintf(stderr,"dir %s patt %s stack %d\n", dir, basepatt, stack_p)));
  316.  
  317.         dirp = opendir(dir);
  318.     if(!dirp)
  319.     {
  320.         free(dir);
  321.         DEBUGX((fprintf(stderr,"no dir\n")));
  322.         continue;
  323.         }
  324.     
  325.         while((d = readdir(dirp)))
  326.         {
  327.         char *p = ck_malloc(strlen(dir) + strlen(d->d_name) + 2L);
  328.             if(strcmp(dir, "."))
  329.                                      /* If we have a full pathname then */
  330.         {                 /* let's append the directory info */
  331.         strcpy(p, dir);
  332. #ifndef unix
  333.         strcat(p, "\\");
  334. #else
  335.         strcat(p, "/");
  336. #endif
  337.         strcat(p, d->d_name);
  338.         }
  339.         else              /* Otherwise, the name is just fine, */
  340.         strcpy(p, d->d_name); /* there's no need for './' -- bjsjr */
  341.  
  342.         DEBUGX((fprintf(stderr, "Testing %s\n", p)));
  343.         if(!stat(p, &s))    /* if stat fails, ignore it */
  344.             {
  345.             if( ((s.st_mode & S_IFMT) == S_IFREG) ||
  346.             ((s.st_mode & S_IFMT) == S_IFLNK) )
  347.             {  /* it is a file/symbolic link */
  348.             if(wildmat(d->d_name, basepatt))
  349.             {  /* it matches pattern */
  350.             DEBUGX((fprintf(stderr,"File Matched\n")));
  351.             if(matches == NULL)
  352.                 matches = (char **)ck_malloc(sizeof(char *));
  353.             else
  354.                 matches = (char **)
  355.                   ck_realloc(matches, (nmatches+1)*sizeof(char *)); 
  356.             matches[nmatches++] = p;
  357.             } /* no match */
  358.             else
  359.             {
  360.             DEBUGX((fprintf(stderr,"No File Match\n")));
  361.                 free(p);
  362.             }
  363.         } else if(decend_dir && ((s.st_mode & S_IFMT) == S_IFDIR))
  364.         {
  365.             if(!((!strcmp(d->d_name,".")) || (!strcmp(d->d_name, "..")
  366. #ifdef atarist
  367.                      || (!strcmp(d->d_name, ".dir"))
  368. #endif
  369.                 )))
  370.             {
  371.             char *push_p = ck_strdup("*");
  372.             push(p, push_p);
  373.             DEBUGX((fprintf(stderr,"Dir pushed\n")));
  374.             }
  375.             else
  376.             {
  377.             DEBUGX((fprintf(stderr, "DIR skipped\n")));
  378.             free(p);
  379.             }
  380.             }
  381.         else
  382.         {
  383.             DEBUGX((fprintf(stderr, "Not a dir/no decend\n")));
  384.             free(p);
  385.         }
  386.         } /* stat */
  387.         else
  388.         {
  389.         DEBUGX((fprintf(stderr, "Stat failed\n")));
  390.         free(p);
  391.         }
  392.         } /* while readdir */
  393.         closedir(dirp);
  394.     free(basepatt);
  395.     free(dir);
  396.     DEBUGX((fprintf(stderr, "Dir done\n\n")));
  397.     } /* while dirs in stack */
  398.     
  399.     if(!nmatches)
  400.     {
  401.     DEBUGX((fprintf(stderr, "No matches\n")));
  402.     return NULL;
  403.     }
  404.     
  405.     matches = (char **)realloc(matches, (nmatches+1)*sizeof(char *));
  406.     if(!matches)
  407.     {  return NULL; }
  408.     matches[nmatches] = NULL;
  409.     DEBUGX((fprintf(stderr, "%d matches\n", nmatches)));    
  410.     return matches;
  411. }
  412.  
  413. #ifdef ZOO
  414. #include "errors.i"
  415. #endif
  416.  
  417. static void *ck_memalloc(p)
  418. void *p;
  419. {
  420.     if(!p)
  421.     {
  422. #ifndef ZOO
  423.         fprintf(stderr, "Out of memory\n");
  424.     exit(98);
  425. #else
  426.         prterror('f', no_memory);
  427. #endif
  428.     }
  429.     return p;
  430. }
  431.  
  432. #ifdef TEST_GLOB
  433. void test(path, dec)
  434. char *path;
  435. int dec;
  436. {
  437.     char **m;
  438.     char **matches;
  439.  
  440.     printf("Testing %s %d\n", path, dec);
  441.     matches = glob(path, dec);
  442.     if(!matches)
  443.     {
  444.     printf("No matches\n");
  445.     }
  446.     else
  447.     {
  448.         for(m = matches; *m; m++)
  449.         printf("%s\n", *m);
  450.     putchar('\n');
  451.         free_all();
  452.     }
  453. }
  454.  
  455. int main()
  456. {
  457. #ifndef unix
  458.     test("e:\\lib\\*.olb", 0);
  459.     test("e:\\lib", 0);
  460.     test("e:\\lib\\", 1);
  461. #else
  462.     test("/net/acae127/home/bammi/News/comp.sources.misc/*.c", 0);
  463.     test("/net/acae127/home/bammi/News/comp.sources.misc", 0);
  464.     test("/net/acae127/home/bammi/News/comp.sources.misc", 1);
  465.     test("/net/acae127/home/bammi/atari/cross-gcc", 1);
  466. #endif
  467.     
  468.     return 0;
  469. }
  470.  
  471. #endif
  472.  
  473. #ifdef    TEST_WILDMAT
  474. #include <stdio.h>
  475.  
  476. /* Yes, we use gets not fgets.  Sue me. */
  477. extern char    *gets();
  478.  
  479.  
  480. main()
  481. {
  482.     char    pattern[80];
  483.     char    text[80];
  484.  
  485.     printf("Wildmat tester.  Enter pattern, then strings to test.\n");
  486.     printf("A blank line gets prompts for a new pattern; a blank pattern\n");
  487.     printf("exits the program.\n\n");
  488.  
  489.     for ( ; ; ) {
  490.     printf("Enter pattern:  ");
  491.     if (gets(pattern) == NULL)
  492.         break;
  493.     for ( ; ; ) {
  494.         printf("Enter text:  ");
  495.         if (gets(text) == NULL)
  496.         exit(0);
  497.         if (text[0] == '\0')
  498.         /* Blank line; go back and get a new pattern. */
  499.         break;
  500.         printf("      %s\n", wildmat(text, pattern) ? "YES" : "NO");
  501.     }
  502.     }
  503.  
  504.     exit(0);
  505.     /* NOTREACHED */
  506. }
  507. #endif    /* TEST_WILDMAT */
  508.