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