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