home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / c / wildf113.zip / FILMATCH.C next >
C/C++ Source or Header  |  1991-04-20  |  16KB  |  493 lines
  1. /*
  2.  EPSHeader
  3.  
  4.    File: filmatch.c
  5.    Author: J. Kercheval
  6.    Created: Thu, 03/14/1991  22:22:01
  7. */
  8.  
  9. /*
  10.  EPSRevision History
  11.  
  12.    J. Kercheval  Wed, 02/20/1991  22:29:01  Released to Public Domain
  13.    J. Kercheval  Fri, 02/22/1991  15:29:01  fix '\' bugs (two :( of them)
  14.    J. Kercheval  Sun, 03/10/1991  19:31:29  add error return to matche()
  15.    J. Kercheval  Sun, 03/10/1991  20:11:11  add is_valid_pattern code
  16.    J. Kercheval  Sun, 03/10/1991  20:37:11  beef up main()
  17.    J. Kercheval  Tue, 03/12/1991  22:25:10  Released as V1.1 to Public Domain
  18.    J. Kercheval  Thu, 03/14/1991  22:22:25  remove '\' for DOS file parsing
  19.    J. Kercheval  Thu, 03/28/1991  20:58:27  include filmatch.h
  20. */
  21.  
  22. /*
  23.    Wildcard Pattern Matching
  24. */
  25.  
  26.  
  27. #include "filmatch.h"
  28.  
  29. int matche_after_star (register char *pattern, register char *text);
  30. int fast_match_after_star (register char *pattern, register char *text);
  31.  
  32. /*----------------------------------------------------------------------------
  33. *
  34. * Return TRUE if PATTERN has any special wildcard characters
  35. *
  36. ----------------------------------------------------------------------------*/
  37.  
  38. BOOLEAN is_pattern (char *p)
  39. {
  40.     while ( *p ) {
  41.         switch ( *p++ ) {
  42.             case '?':
  43.             case '*':
  44.             case '[':
  45.                 return TRUE;
  46.         }
  47.     }
  48.     return FALSE;
  49. }
  50.  
  51.  
  52. /*----------------------------------------------------------------------------
  53. *
  54. * Return TRUE if PATTERN has is a well formed regular expression according
  55. * to the above syntax
  56. *
  57. * error_type is a return code based on the type of pattern error.  Zero is
  58. * returned in error_type if the pattern is a valid one.  error_type return
  59. * values are as follows:
  60. *
  61. *   PATTERN_VALID - pattern is well formed
  62. *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  63. *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  64. *   PATTERN_EMPTY - [..] construct is empty (ie [])
  65. *
  66. ----------------------------------------------------------------------------*/
  67.  
  68. BOOLEAN is_valid_pattern (char *p, int *error_type)
  69. {
  70.     
  71.     /* init error_type */
  72.     *error_type = PATTERN_VALID;
  73.     
  74.     /* loop through pattern to EOS */
  75.     while( *p ) {
  76.  
  77.         /* determine pattern type */
  78.         switch( *p ) {
  79.  
  80.             /* the [..] construct must be well formed */
  81.             case '[':
  82.                 p++;
  83.  
  84.                 /* if the next character is ']' then bad pattern */
  85.                 if ( *p == ']' ) {
  86.                     *error_type = PATTERN_EMPTY;
  87.                     return FALSE;
  88.                 }
  89.                 
  90.                 /* if end of pattern here then bad pattern */
  91.                 if ( !*p ) {
  92.                     *error_type = PATTERN_CLOSE;
  93.                     return FALSE;
  94.                 }
  95.  
  96.                 /* loop to end of [..] construct */
  97.                 while( *p != ']' ) {
  98.  
  99.                     /* check for literal escape */
  100.                     if( *p == '\\' ) {
  101.                         p++;
  102.  
  103.                         /* if end of pattern here then bad pattern */
  104.                         if ( !*p++ ) {
  105.                             *error_type = PATTERN_ESC;
  106.                             return FALSE;
  107.                         }
  108.                     }
  109.                     else
  110.                         p++;
  111.  
  112.                     /* if end of pattern here then bad pattern */
  113.                     if ( !*p ) {
  114.                         *error_type = PATTERN_CLOSE;
  115.                         return FALSE;
  116.                     }
  117.  
  118.                     /* if this a range */
  119.                     if( *p == '-' ) {
  120.  
  121.                         /* we must have an end of range */
  122.                         if ( !*++p || *p == ']' ) {
  123.                             *error_type = PATTERN_RANGE;
  124.                             return FALSE;
  125.                         }
  126.                         else {
  127.  
  128.                             /* check for literal escape */
  129.                             if( *p == '\\' )
  130.                                 p++;
  131.  
  132.                             /* if end of pattern here then bad pattern */
  133.                             if ( !*p++ ) {
  134.                                 *error_type = PATTERN_ESC;
  135.                                 return FALSE;
  136.                             }
  137.                         }
  138.                     }
  139.                 }
  140.                 break;
  141.  
  142.             /* all other characters are valid pattern elements */
  143.             case '*':
  144.             case '?':
  145.             default:
  146.                 p++;                              /* "normal" character */
  147.                 break;
  148.          }
  149.      }
  150.  
  151.      return TRUE;
  152. }
  153.  
  154.  
  155. /*----------------------------------------------------------------------------
  156. *
  157. *  Match the pattern PATTERN against the string TEXT;
  158. *
  159. *  returns MATCH_VALID if pattern matches, or an errorcode as follows
  160. *  otherwise:
  161. *
  162. *            MATCH_PATTERN  - bad pattern
  163. *            MATCH_RANGE    - match failure on [..] construct
  164. *            MATCH_ABORT    - premature end of text string
  165. *            MATCH_END      - premature end of pattern string
  166. *            MATCH_VALID    - valid match
  167. *
  168. *
  169. *  A match means the entire string TEXT is used up in matching.
  170. *
  171. *  In the pattern string:
  172. *       `*' matches any sequence of characters (zero or more)
  173. *       `?' matches any character
  174. *       [SET] matches any character in the specified set,
  175. *       [!SET] or [^SET] matches any character not in the specified set.
  176. *       \ is allowed within a set to escape a character like ']' or '-'
  177. *
  178. *  A set is composed of characters or ranges; a range looks like
  179. *  character hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the
  180. *  minimal set of characters allowed in the [..] pattern construct.
  181. *  Other characters are allowed (ie. 8 bit characters) if your system
  182. *  will support them.
  183. *
  184. *  To suppress the special syntactic significance of any of `[]*?!^-\',
  185. *  within a [..] construct and match the character exactly, precede it
  186. *  with a `\'.
  187. *
  188. ----------------------------------------------------------------------------*/
  189.  
  190. int matche ( register char *p, register char *t )
  191. {
  192.     register char range_start, range_end;  /* start and end in range */
  193.  
  194.     BOOLEAN invert;             /* is this [..] or [!..] */
  195.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  196.     BOOLEAN loop;               /* should I terminate? */
  197.  
  198.     for ( ; *p; p++, t++ ) {
  199.  
  200.         /* if this is the end of the text then this is the end of the match */
  201.         if (!*t) {
  202.             return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
  203.         }
  204.  
  205.         /* determine and react to pattern type */
  206.         switch ( *p ) {
  207.  
  208.             /* single any character match */
  209.             case '?':
  210.                 break;
  211.  
  212.             /* multiple any character match */
  213.             case '*':
  214.                 return matche_after_star (p, t);
  215.  
  216.             /* [..] construct, single member/exclusion character match */
  217.             case '[': {
  218.  
  219.                 /* move to beginning of range */
  220.                 p++;
  221.  
  222.                 /* check if this is a member match or exclusion match */
  223.                 invert = FALSE;
  224.                 if ( *p == '!' || *p == '^') {
  225.                     invert = TRUE;
  226.                     p++;
  227.                 }
  228.  
  229.                 /* if closing bracket here or at range start then we have a
  230.                    malformed pattern */
  231.                 if ( *p == ']' ) {
  232.                     return MATCH_PATTERN;
  233.                 }
  234.  
  235.                 member_match = FALSE;
  236.                 loop = TRUE;
  237.  
  238.                 while ( loop ) {
  239.  
  240.                     /* if end of construct then loop is done */
  241.                     if (*p == ']') {
  242.                         loop = FALSE;
  243.                         continue;
  244.                     }
  245.  
  246.                     /* matching a '!', '^', '-', '\' or a ']' */
  247.                     if ( *p == '\\' ) {
  248.                         range_start = range_end = *++p;
  249.                     }
  250.                     else {
  251.                         range_start = range_end = *p;
  252.                     }
  253.  
  254.                     /* if end of pattern then bad pattern (Missing ']') */
  255.                     if (!*p)
  256.                         return MATCH_PATTERN;
  257.  
  258.                     /* check for range bar */
  259.                     if (*++p == '-') {
  260.  
  261.                         /* get the range end */
  262.                         range_end = *++p;
  263.  
  264.                         /* if end of pattern or construct then bad pattern */
  265.                         if (range_end == '\0' || range_end == ']')
  266.                             return MATCH_PATTERN;
  267.  
  268.                         /* special character range end */
  269.                         if (range_end == '\\') {
  270.                             range_end = *++p;
  271.  
  272.                             /* if end of text then we have a bad pattern */
  273.                             if (!range_end)
  274.                                 return MATCH_PATTERN;
  275.                         }
  276.  
  277.                         /* move just beyond this range */
  278.                         p++;
  279.                     }
  280.  
  281.                     /* if the text character is in range then match found.
  282.                        make sure the range letters have the proper
  283.                        relationship to one another before comparison */
  284.                     if ( range_start < range_end  ) {
  285.                         if (*t >= range_start && *t <= range_end) {
  286.                             member_match = TRUE;
  287.                             loop = FALSE;
  288.                         }
  289.                     }
  290.                     else {
  291.                         if (*t >= range_end && *t <= range_start) {
  292.                             member_match = TRUE;
  293.                             loop = FALSE;
  294.                         }
  295.                     }
  296.                 }
  297.  
  298.                 /* if there was a match in an exclusion set then no match */
  299.                 /* if there was no match in a member set then no match */
  300.                 if ((invert && member_match) ||
  301.                    !(invert || member_match))
  302.                     return MATCH_RANGE;
  303.  
  304.                 /* if this is not an exclusion then skip the rest of the [...]
  305.                     construct that already matched. */
  306.                 if (member_match) {
  307.                     while (*p != ']') {
  308.  
  309.                         /* bad pattern (Missing ']') */
  310.                         if (!*p)
  311.                             return MATCH_PATTERN;
  312.  
  313.                         /* skip exact match */
  314.                         if (*p == '\\') {
  315.                             p++;
  316.  
  317.                             /* if end of text then we have a bad pattern */
  318.                             if (!*p)
  319.                                 return MATCH_PATTERN;
  320.                         }
  321.  
  322.                         /* move to next pattern char */
  323.                         p++;
  324.                     }
  325.                 }
  326.  
  327.                 break;
  328.             }
  329.  
  330.             /* must match this character exactly */
  331.             default:
  332.                 if (*p != *t)
  333.                     return MATCH_LITERAL;
  334.         }
  335.     }
  336.  
  337.     /* if end of text not reached then the pattern fails */
  338.     if ( *t )
  339.         return MATCH_END;
  340.     else
  341.         return MATCH_VALID;
  342. }
  343.  
  344.  
  345. /*----------------------------------------------------------------------------
  346. *
  347. * recursively call matche() with final segment of PATTERN and of TEXT.
  348. *
  349. ----------------------------------------------------------------------------*/
  350.  
  351. int matche_after_star (register char *p, register char *t)
  352. {
  353.     register int match = 0;
  354.     register nextp;
  355.  
  356.     /* pass over existing ? and * in pattern */
  357.     while ( *p == '?' || *p == '*' ) {
  358.  
  359.         /* take one char for each ? and + */
  360.         if ( *p == '?' ) {
  361.  
  362.             /* if end of text then no match */
  363.             if ( !*t++ ) {
  364.                 return MATCH_ABORT;
  365.             }
  366.         }
  367.  
  368.         /* move to next char in pattern */
  369.         p++;
  370.     }
  371.  
  372.     /* if end of pattern we have matched regardless of text left */
  373.     if ( !*p ) {
  374.         return MATCH_VALID;
  375.     }
  376.  
  377.     /* get the next character to match which must be a literal or '[' */
  378.     nextp = *p;
  379.  
  380.     /* Continue until we run out of text or definite result seen */
  381.     do {
  382.  
  383.         /* a precondition for matching is that the next character
  384.            in the pattern match the next character in the text or that
  385.            the next pattern char is the beginning of a range.  Increment
  386.            text pointer as we go here */
  387.         if ( nextp == *t || nextp == '[' ) {
  388.             match = matche(p, t);
  389.         }
  390.  
  391.         /* if the end of text is reached then no match */
  392.         if ( !*t++ ) match = MATCH_ABORT;
  393.  
  394.     } while ( match != MATCH_VALID && 
  395.               match != MATCH_ABORT &&
  396.               match != MATCH_PATTERN);
  397.  
  398.     /* return result */
  399.     return match;
  400. }
  401.  
  402.  
  403. /*----------------------------------------------------------------------------
  404. *
  405. * match() is a shell to matche() to return only BOOLEAN values.
  406. *
  407. ----------------------------------------------------------------------------*/
  408.  
  409. BOOLEAN match( char *p, char *t )
  410. {
  411.     int error_type;
  412.     error_type = matche(p,t);
  413.     return (error_type == MATCH_VALID ) ? TRUE : FALSE;
  414. }
  415.  
  416.  
  417. #ifdef TEST
  418.  
  419.     /*
  420.     * This test main expects as first arg the pattern and as second arg
  421.     * the match string.  Output is yaeh or nay on match.  If nay on
  422.     * match then the error code is parsed and written.
  423.     */
  424.  
  425.     #include <stdio.h>
  426.  
  427.     int main(int argc, char *argv[])
  428.     {
  429.         int error;
  430.         int is_valid_error;
  431.  
  432.         if (argc != 3) {
  433.             printf("Usage:  MATCH Pattern Text\n");
  434.         }
  435.         else {
  436.             printf("Pattern: %s\n", argv[1]);
  437.             printf("Text   : %s\n", argv[2]);
  438.             
  439.             if (!is_pattern(argv[1])) {
  440.                 printf("    First Argument Is Not A Pattern\n");
  441.             }
  442.             else {
  443.                 match(argv[1],argv[2]) ? printf("TRUE") : printf("FALSE");
  444.                 error = matche(argv[1],argv[2]);
  445.                 is_valid_pattern(argv[1],&is_valid_error);
  446.  
  447.                 switch ( error ) {
  448.                     case MATCH_VALID:
  449.                         printf("    Match Successful");
  450.                         if (is_valid_error != PATTERN_VALID)
  451.                             printf(" -- is_valid_pattern() is complaining\n");
  452.                         else
  453.                             printf("\n");
  454.                         break;
  455.                     case MATCH_RANGE:
  456.                         printf("    Match Failed on [..]\n");
  457.                         break;
  458.                     case MATCH_ABORT:
  459.                         printf("    Match Failed on Early Text Termination\n");
  460.                         break;
  461.                     case MATCH_END:
  462.                         printf("    Match Failed on Early Pattern Termination\n");
  463.                         break;
  464.                     case MATCH_PATTERN:
  465.                         switch ( is_valid_error ) {
  466.                             case PATTERN_VALID:
  467.                                 printf("    Internal Disagreement On Pattern\n");
  468.                                 break;
  469.                             case PATTERN_RANGE:
  470.                                 printf("    No End of Range in [..] Construct\n");
  471.                                 break;
  472.                             case PATTERN_CLOSE:
  473.                                 printf("    [..] Construct is Open\n");
  474.                                 break;
  475.                             case PATTERN_EMPTY:
  476.                                 printf("    [..] Construct is Empty\n");
  477.                                 break;
  478.                             default:
  479.                                 printf("    Internal Error in is_valid_pattern()\n");
  480.                         }
  481.                         break;
  482.                     default:
  483.                         printf("    Internal Error in matche()\n");
  484.                         break;
  485.                 }
  486.             }
  487.  
  488.         }
  489.         return(0);
  490.     }
  491.  
  492. #endif
  493.