home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume29 / regex-glob / part01 / match.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-06  |  9.1 KB  |  320 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. */
  13.  
  14. /*
  15.    Wildcard Pattern Matching
  16. */
  17.  
  18.  
  19. #include "match.h"
  20.  
  21. #define ABORT 2     /* end of search indicator */
  22.  
  23. BOOLEAN regex_match_after_star (char *pattern, char *text);
  24.  
  25. /*----------------------------------------------------------------------------
  26. *
  27. * Return TRUE if PATTERN has any special wildcard characters
  28. *
  29. ----------------------------------------------------------------------------*/
  30.  
  31. BOOLEAN is_pattern (char *p)
  32. {
  33.     while ( *p ) {
  34.         switch ( *p++ ) {
  35.             case '?':
  36.             case '*':
  37.             case '[':
  38.                 return TRUE;
  39.             case '\\':
  40.                 if ( !*p++ ) return FALSE;
  41.         }
  42.     }
  43.     return FALSE;
  44. }
  45.  
  46.  
  47. /*----------------------------------------------------------------------------
  48. *
  49. *  Match the pattern PATTERN against the string TEXT;
  50. *  return TRUE if it matches, FALSE otherwise.
  51. *
  52. *  A match means the entire string TEXT is used up in matching.
  53. *
  54. *  In the pattern string:
  55. *       `*' matches any sequence of characters
  56. *       `?' matches any character
  57. *       [SET] matches any character in the specified set,
  58. *       [!SET] or [^SET] matches any character not in the specified set.
  59. *
  60. *  Note: the standard regex character '+' (one or more) should by
  61. *        simulated by using "?*" which is equivelant here.
  62. *
  63. *  A set is composed of characters or ranges; a range looks like
  64. *  character hyphen character (as in 0-9 or A-Z).
  65. *  [0-9a-zA-Z_] is the set of characters allowed in C identifiers.
  66. *  Any other character in the pattern must be matched exactly.
  67. *
  68. *  To suppress the special syntactic significance of any of `[]*?!^-\',
  69. *  and match the character exactly, precede it with a `\'.
  70. *
  71. ----------------------------------------------------------------------------*/
  72.  
  73. BOOLEAN regex_match ( register char *p, register char *t )
  74. {
  75.     register char range_start, range_end;  /* start and end in range */
  76.  
  77.     BOOLEAN invert;             /* is this [..] or [!..] */
  78.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  79.     BOOLEAN loop;               /* should I terminate? */
  80.  
  81.     for ( ; *p; p++, t++ ) {
  82.  
  83.         /* if this is the end of the text then this is the end of the match */
  84.         if (!*t) {
  85.             return ( *p == '*' && *++p == '\0' ) ? TRUE : ABORT;
  86.         }
  87.  
  88.         /* determine and react to pattern type */
  89.         switch ( *p ) {
  90.  
  91.             /* single any character match */
  92.             case '?':
  93.                 break;
  94.  
  95.             /* multiple any character match */
  96.             case '*':
  97.                 return regex_match_after_star (p, t);
  98.  
  99.             /* [..] construct, single member/exclusion character match */
  100.             case '[': {
  101.  
  102.                 /* move to beginning of range */
  103.                 p++;
  104.  
  105.                 /* check if this is a member match or exclusion match */
  106.                 invert = FALSE;
  107.                 if ( *p == '!' || *p == '^') {
  108.                     invert = TRUE;
  109.                     p++;
  110.                 }
  111.  
  112.                 /* if closing bracket here or at range start then we have a
  113.                    malformed pattern */
  114.                 if ( *p == ']' ) {
  115.                     return ABORT;
  116.                 }
  117.  
  118.                 member_match = FALSE;
  119.                 loop = TRUE;
  120.  
  121.                 while ( loop ) {
  122.  
  123.                     /* if end of construct then loop is done */
  124.                     if (*p == ']') {
  125.                         loop = FALSE;
  126.                         continue;
  127.                     }
  128.  
  129.                     /* matching a '!', '^', '-', '\' or a ']' */
  130.                     if ( *p == '\\' ) {
  131.                         range_start = range_end = *++p;
  132.                     }
  133.                     else {
  134.                         range_start = range_end = *p;
  135.                     }
  136.  
  137.                     /* if end of pattern then bad pattern (Missing ']') */
  138.                     if (!range_start)
  139.                         return ABORT;
  140.  
  141.                     /* move to next pattern char */
  142.                     p++;
  143.  
  144.                     /* check for range bar */
  145.                     if (*p == '-') {
  146.  
  147.                         /* get the range end */
  148.                         range_end = *++p;
  149.  
  150.                         /* special character range end */
  151.                         if (range_end == '\\')
  152.                             range_end = *++p;
  153.  
  154.                         /* if end of pattern or construct then bad pattern */
  155.                         if (range_end == '\0' || range_end == ']')
  156.                             return ABORT;
  157.                     }
  158.  
  159.                     /* if the text character is in range then match found.
  160.                        make sure the range letters have the proper
  161.                        relationship to one another before comparison */
  162.                     if ( range_start < range_end  ) {
  163.                         if (*t >= range_start && *t <= range_end) {
  164.                             member_match = TRUE;
  165.                             loop = FALSE;
  166.                         }
  167.                     }
  168.                     else {
  169.                         if (*t >= range_end && *t <= range_start) {
  170.                             member_match = TRUE;
  171.                             loop = FALSE;
  172.                         }
  173.                     }
  174.                 }
  175.  
  176.                 /* if there was a match in an exclusion set then no match */
  177.                 /* if there was no match in a member set then no match */
  178.                 if ((invert && member_match) ||
  179.                    !(invert || member_match))
  180.                     return FALSE;
  181.  
  182.                 /* if this is not an exclusion then skip the rest of the [...]
  183.                     construct that already matched. */
  184.                 if (member_match) {
  185.                     while (*p != ']') {
  186.  
  187.                         /* bad pattern (Missing ']') */
  188.                         if (!*p)
  189.                             return ABORT;
  190.  
  191.                         /* skip exact match */
  192.                         if (*p == '\\') {
  193.                             p++;
  194.                         }
  195.  
  196.                         /* move to next pattern char */
  197.                         p++;
  198.                     }
  199.                 }
  200.  
  201.                 break;
  202.             }
  203.  
  204.             /* next character is quoted and must match exactly */
  205.             case '\\':
  206.  
  207.                 /* move pattern pointer to quoted char and fall through */
  208.                 p++;
  209.  
  210.             /* must match this character exactly */
  211.             default:
  212.                 if (*p != *t)
  213.                     return FALSE;
  214.         }
  215.     }
  216.  
  217.     /* if end of text not reached then the pattern fails */
  218.     return !*t;
  219. }
  220.  
  221.  
  222. /*----------------------------------------------------------------------------
  223. *
  224. * recursively call regex_match with final segment of PATTERN and of TEXT.
  225. *
  226. ----------------------------------------------------------------------------*/
  227.  
  228. BOOLEAN regex_match_after_star (register char *p, register char *t)
  229. {
  230.     register BOOLEAN match;
  231.     register nextp;
  232.  
  233.     /* pass over existing ? and * in pattern */
  234.     while ( *p == '?' || *p == '*' ) {
  235.  
  236.         /* take one char for each ? */
  237.         if ( *p == '?' ) {
  238.  
  239.             /* if end of text then no match */
  240.             if ( !*t++ ) {
  241.                 return ABORT;
  242.             }
  243.         }
  244.  
  245.         /* move to next char in pattern */
  246.         p++;
  247.     }
  248.  
  249.     /* if end of pattern we have matched regardless of text left */
  250.     if ( !*p ) {
  251.         return TRUE;
  252.     }
  253.  
  254.     /* get the next character to match which must be a literal or '[' */
  255.     nextp = *p;
  256.     if ( nextp == '\\' )
  257.         nextp = p[1];
  258.  
  259.     /* Continue until we run out of text or definite result seen */
  260.     match = FALSE;
  261.     while ( match == FALSE ) {
  262.  
  263.         /* a precondition for matching is that the next character
  264.            in the pattern match the next character in the text or that
  265.            the next pattern is the beginning of a range.  Increment text
  266.            pointer as we go here */
  267.         if ( *p == *t || nextp == '[' ) {
  268.             match = regex_match(p, t);
  269.         }
  270.  
  271.         /* if the end of text is reached then no match */
  272.         if ( !*t++ ) match = ABORT;
  273.     }
  274.  
  275.     /* return result */
  276.     return match;
  277. }
  278.  
  279. /*----------------------------------------------------------------------------
  280. *
  281. * This is a shell to regex_match to return only a true BOOLEAN value
  282. *
  283. ----------------------------------------------------------------------------*/
  284.  
  285. BOOLEAN match( char *p, char *t)
  286. {
  287.     return ( regex_match(p,t) == TRUE ) ? TRUE : FALSE;
  288. }
  289.  
  290.  
  291. #ifdef TEST
  292.  
  293.     /*
  294.     * This test main expects as first arg the pattern and as second arg
  295.     * the match string.  Output is yaeh or nay on match.
  296.     */
  297.  
  298. #include <stdio.h>
  299.  
  300.     int main(int argc, char *argv[])
  301.     {
  302.         if (argc == 3) {
  303.             if (is_pattern(argv[1])) {
  304.                 if (match(argv[1],argv[2])) {
  305.                     printf("    Match Successful\n");
  306.                 }
  307.                 else {
  308.                     printf("    Match Fails\n");
  309.                 }
  310.             }
  311.             else {
  312.                 printf("    Bad Pattern\n");
  313.             }
  314.         }
  315.         else printf("    Bad Breath\n");
  316.         return(0);
  317.     }
  318.  
  319. #endif
  320.