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