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