home *** CD-ROM | disk | FTP | other *** search
/ The Developer Connection…ice Driver Kit for OS/2 3 / DEV3-D1.ISO / source / util2src / rxpm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-22  |  15.9 KB  |  397 lines
  1. /*============================================================================*
  2.  * module: rxpm.c - Regular expression and pattern-matching subroutines
  3.  *
  4.  * (C)Copyright IBM Corporation, 1989, 1990, 1991.        Brian E. Yoder
  5.  *
  6.  * Externally-available functions contained in this module:
  7.  *   rexpand()  - Expand pattern-matching expression into a regular expression.
  8.  *   rcompile() - Compile a regular expression.
  9.  *   rmatch()   - Match a regular expression.
  10.  *   rscan()    - Scan for a regular expression.
  11.  *   rcmpmsg()  - Get error message based on error from rcompile().
  12.  *
  13.  * These subroutines use a modified version of the regexp.h header file
  14.  * that is supplied with PS/2 AIX.
  15.  *
  16.  * The regexp.h header file sets the static variable 'circf' whenever its
  17.  * compile() subroutine is called.  This variable is used by its step()
  18.  * subroutine and should be set to the value it had when the expression
  19.  * was compiled.  Therefore:
  20.  *
  21.  * The rcompile() subroutine in this module stores the value of 'circf'
  22.  * in the first 'sizeof(int)' bytes of the compiled-expression buffer.
  23.  * The rscan() subroutine extracts this value of 'circf' before calling
  24.  * the step() subroutine.
  25.  *
  26.  * 12/04/89 - Created by splitting the subroutines from pmt.c
  27.  * 12/05/89 - Initial version.
  28.  * 12/08/89 - In rmatch(), 'circf' is set to 1 to force a match starting
  29.  *            at the beginning of the string.  This improves performance
  30.  *            in the case of a failed match.
  31.  * 05/25/90 - Include libutil.h instead of rxpm.h.
  32.  * 04/04/91 - Ported from AIX to DOS and C/2. Includes <stdlib.h> and "util.h"
  33.  * 06/16/92 - rexpand() now changes a \! sequence into a !
  34.  * 07/22/92 - Convert function definitions to the new style.
  35.  *============================================================================*/
  36.  
  37. #include <stdio.h>
  38. #include <stdlib.h>
  39. #include <sys/types.h>
  40.  
  41. #include "util.h"
  42.  
  43. /*============================================================================*
  44.  * Regular expression data and macros needed by regexp.h
  45.  *============================================================================*/
  46.  
  47. static char *regexpr;          /* Pointer to regular expression to compile */
  48. static char *after_cexpr;      /* Pointer past compiled expression */
  49.  
  50. #define INIT        char *sp=regexpr;
  51. #define GETC()      (*sp++)
  52. #define PEEKC()     (*sp)
  53. #define UNGETC(c)   (--sp)
  54. #define RETURN(c)   {after_cexpr = c; return(0);}
  55. #define ERROR(x)    return(x)
  56.  
  57. #include "regexp.h"            /* Modified version of AIX's header file */
  58.  
  59. /*============================================================================*
  60.  * rexpand() - Expand pattern-matching expression into a regular expression.
  61.  *
  62.  * Description:
  63.  *   The pattern matching expression pointed to by 'expr' is expanded into
  64.  *   a full regular expression and stored in the buffer pointed to by
  65.  *   'rexpr'.  The 'erexpr' pointer should point just past the buffer in which
  66.  *   the expanded expression is to be stored.  Therefore, the maximum length
  67.  *   allowed for the expanded expression (including the null terminating byte!)
  68.  *   is (erexpr - rexpr) bytes.
  69.  *
  70.  * The following patterns are supported:
  71.  *
  72.  * Pattern      What it matches                    Examples
  73.  * -------      ------------------------------     ----------------------------
  74.  *
  75.  *   *          Matches any string, including      *ab* matches ab, blab,
  76.  *              the null string.                   and babies.
  77.  *
  78.  *   ?          Matches any single character.      ab?c matches any string
  79.  *                                                 that is 4 characters
  80.  *                                                 long, begins with ab,
  81.  *                                                 and ends with c.
  82.  *
  83.  *   [...]      Matches any one of the             [ABC]* matches any string
  84.  *              enclosed characters.               that begins with A, B, or C.
  85.  *
  86.  *   [.-.]      Matches any character              [A-Z]* matches any string
  87.  *              between the enclosed pair,         that begins with an uppercase
  88.  *              inclusive (range).                 letter.
  89.  *
  90.  *                                                 [a-zA-Z]* matches any string
  91.  *                                                 that begins with a letter.
  92.  *
  93.  *   [!...]     Matches any single character       [!XYZ]* matches any string
  94.  *              except one of those enclosed.      that does not begin with
  95.  *                                                 X, Y, or Z.
  96.  *
  97.  *   Enclosed characters can be combined with ranges.  Thus, [abcm-z]* matches
  98.  *   any string that begins with a, b, c, or m through z.
  99.  *
  100.  *   Additionally, any pattern may be followed by:
  101.  *     {m}      Matches exactly m occurrences of the pattern.
  102.  *     {m,}     Matches at least m occurrences of the pattern.
  103.  *     {m,n}    Matches at least m but no more than n occurrences of the pattern.
  104.  *
  105.  *              m and n must be integers from 0 to 255, inclusive.
  106.  *
  107.  *   The expression [a-zA-Z][0-9a-zA-Z]{0,} matches any string that begins
  108.  *   with a letter and is followed only by letters or numbers.
  109.  *
  110.  *   The expression [-+]{0,1}[0-9]{1,} matches any string that optionally
  111.  *   begins with a - or + sign and consists of one or more digits.
  112.  *
  113.  *   The expression "the {1,}cat" matches any string that begins with 'the',
  114.  *   ends with 'cat', and has one or more spaces in the middle.
  115.  *
  116.  *   The expression "[!.]{1,}" matches any string that does not contain a period.
  117.  *
  118.  * Notes:
  119.  *   If the pattern contains braces {} or a !, then 'escape' each brace by
  120.  *   putting a '\' before it.
  121.  *
  122.  * Returns:
  123.  *   0, if successful.
  124.  *   REGX_FULL, if the expanded expression won't fit in the buffer.
  125.  *
  126.  *   If successful, 'endp' contains a pointer to the location that is one byte
  127.  *   past the null terminating byte of the expanded expression.  If error,
  128.  *   then 'endp' contains a pointer to 'rexpr'.
  129.  *============================================================================*/
  130.  
  131. #define STORE(ch) if (to >= erexpr) return(REGX_FULL); *to++ = ch;
  132.  
  133. int rexpand(expr, rexpr, erexpr, endp)
  134.  
  135. char *expr;                    /* Pointer to pattern-matching expression */
  136. char *rexpr;                   /* Pointer to expansion buffer */
  137. char *erexpr;                  /* Pointer past end of expansion buffer */
  138. char **endp;                   /* Pointer to loc. in which to store pointer */
  139.                                /* to byte just past expanded expression */
  140.  
  141. {
  142.   char *from;                  /* Character pointers used to expand the */
  143.   char *to;                    /*    expression */
  144.  
  145.   from = expr;                     /* Point to start of each expression */
  146.   to = rexpr;
  147.  
  148.   *endp = rexpr;                   /* Initialize 'endp' to 'rexpr */
  149.  
  150.   if (rexpr >= erexpr)             /* If end pointer doesn't allow at least */
  151.      return(REGX_FULL);            /* one character: return w/error */
  152.  
  153.   while (*from != '\0')            /* For each character in 'expr': */
  154.   {
  155.      switch (*from)                    /* Handle special cases: */
  156.      {
  157.         case '.':                            /* Put '\' before */
  158.         case '$':                            /* these characters: */
  159.         case '{':
  160.         case '}':
  161.            STORE('\\');
  162.            STORE(*from);
  163.            break;
  164.  
  165.         case '\\':                           /* If escape character found: */
  166.            from++;                                /* Point to next character */
  167.            switch (*from)
  168.            {
  169.               case '{':                           /* Store these characters */
  170.               case '}':                           /* without the escape char: */
  171.               case '$':
  172.               case '!':
  173.                  STORE(*from);
  174.                  break;
  175.  
  176.               default:                            /* Otherwise: store the esc */
  177.                  STORE('\\');                     /* character, too */
  178.                  STORE(*from);
  179.                  break;
  180.            }
  181.            break;
  182.  
  183.         case '*':                            /* Put '.' before a '*' */
  184.            STORE('.');
  185.            STORE(*from);
  186.            break;
  187.  
  188.         case '?':                            /* Put '.' in place of '?' */
  189.            STORE('.');
  190.            break;
  191.  
  192.         case '!':                            /* Put '^' in place of '!' */
  193.            STORE('^');
  194.            break;
  195.  
  196.         default:                             /* For all other characters: */
  197.            STORE(*from);                          /* Just copy character */
  198.            break;
  199.      }
  200.  
  201.      from++;                           /* Bump pointer to next source char */
  202.   }
  203.  
  204.   STORE('\0');                     /* Store null after the expanded expression */
  205.   *endp = to;                      /* Store pointer past the null byte */
  206.   return(0);
  207. }
  208.  
  209. /*============================================================================*
  210.  * rcompile() - Compile a regular expression.
  211.  *
  212.  * Description:
  213.  *   The regular expression pointed to by 'expr' is compiled and stored in
  214.  *   the buffer pointed to by 'cexpr'.
  215.  *
  216.  *   The 'ecexpr' pointer should point just past the buffer in which
  217.  *   the compiled expression is to be stored.  Therefore, the maximum length
  218.  *   of the compiled expression is (ecexpr - cexpr) bytes.
  219.  *
  220.  *   The expression 'expr' being compiled is terminated by the 'endc' character.
  221.  *   Normally, this is the '\0' character, but it can be any character you choose.
  222.  *
  223.  * Returns:
  224.  *   0, if successful.  Otherwise, an error occurred.  The rcmpmsg() subroutine
  225.  *   returns a pointer to an error message based upon this return code.
  226.  *
  227.  *   If successful, 'endp' contains a pointer to the location one byte
  228.  *   past the compiled expression.  If an error occurred, then 'endp' points
  229.  *   to the beginning of the compiled expression buffer 'cexpr'.
  230.  *
  231.  * Notes:
  232.  *   The value of 'circf' (set by the compile() subroutine in regexp.h) is
  233.  *   stored as an integer in the first 'sizeof(int)' bytes of the compiled-
  234.  *   expression buffer.  The actual compiled expression immediately follows
  235.  *   this value.
  236.  *============================================================================*/
  237. int rcompile(
  238.  
  239. char *expr   ,                 /* Pointer to pattern-matching expression */
  240. char *cexpr  ,                 /* Where compiled expression is to be stored */
  241. char *ecexpr ,                 /* Pointer past end of compiled expr. buffer */
  242. char  endc   ,                 /* Character used to terminate the expression */
  243. char **endp  )                 /* Indirect pointer to end of compiled expr */
  244.  
  245. {
  246.   int   rc;                    /* Return code storage */
  247.  
  248.   regexpr = expr;              /* Point 'regexpr' to the regular expression */
  249.   *endp = cexpr;               /* Initialize 'endp' to start of compile buffer */
  250.  
  251.   if (cexpr >= ecexpr)         /* Check pointer to end of compile buffer */
  252.      return(REGX_FULL);
  253.  
  254.   if ((ecexpr - cexpr) < sizeof(int))  /* Be sure we have enough space for the */
  255.      return(REGX_FULL);                /* 'circf' value */
  256.  
  257.   rc = compile(regexpr,        /* Compile the reg. expression */
  258.           cexpr + sizeof(int),
  259.           ecexpr, endc);
  260.  
  261.   *(int *)cexpr = circf;       /* Store value of circf */
  262.  
  263.   if (rc == 0)                 /* If successful:  Store pointer to location */
  264.      *endp = after_cexpr;      /* past the end of the compiled expression */
  265.  
  266.   return(rc);                  /* Return w/error indication */
  267. }
  268.  
  269. /*============================================================================*
  270.  * rmatch() - Match a regular expression.
  271.  *
  272.  * Description:
  273.  *   The compiled regular expression pointed to by 'cexpr' is compared with
  274.  *   the string pointed to by 'str'.
  275.  *
  276.  * Returns:
  277.  *   RMATCH, if the compiled regular expression matched the entire string.
  278.  *   NO_RMATCH, otherwise.
  279.  *
  280.  * Note:
  281.  *   The value of 'circf' is set to 1 to force the step() subroutine to
  282.  *   match the beginning of the string.
  283.  *============================================================================*/
  284. int rmatch(
  285.  
  286. char *cexpr ,                  /* Pointer to compiled regular expression */
  287. char *str   )                  /* Pointer to string to match */
  288.  
  289. {
  290.   int   rc;                    /* Return code storage */
  291.  
  292.   circf = 1;                            /* Set value of 'circf' to 1 */
  293.  
  294.   rc = step(str, cexpr + sizeof(int));  /* Scan for cexpr within 'str' */
  295.  
  296.   if (rc == 0)                          /* If it's not in the string: */
  297.      return(NO_RMATCH);                       /* Return 'no match' */
  298.  
  299.   if ((*loc2 == '\0') && (loc1 == str)) /* If we matched entire string: */
  300.      return(RMATCH);                          /* Return 'match' */
  301.   else                                  /* Otherwise: */
  302.      return(NO_RMATCH);                       /* Return 'no match' */
  303. }
  304.  
  305. /*============================================================================*
  306.  * rscan() - Scan for a regular expression.
  307.  *
  308.  * Description:
  309.  *   The compiled regular expression pointed to by 'cexpr' is compared with
  310.  *   the string pointed to by 'str'.
  311.  *
  312.  * Returns:
  313.  *   RMATCH, if the compiled regular expression is found within the string.
  314.  *   NO_RMATCH, otherwise.
  315.  *
  316.  *   If RMATCH is returned, 'startp' contains a pointer to the first character
  317.  *   matched and 'endp' contains a pointer to the location immediately past
  318.  *   the last character matched.  Therefore, the total number of characters
  319.  *   matched is (*endp - *startp).
  320.  *
  321.  * Note:
  322.  *   The first 'sizeof(int)' bytes of the compiled expression must contain
  323.  *   the value of 'circf' at the time the expression was compiled.
  324.  *============================================================================*/
  325. int rscan(
  326.  
  327. char  *cexpr  ,                /* Pointer to compiled regular expression */
  328. char  *str    ,                /* Pointer to string to match */
  329. char **startp ,                /* Start of match */
  330. char **endp   )                /* End-of-match + 1 */
  331.  
  332. {
  333.   int   rc;                    /* Return code storage */
  334.  
  335.   circf = *(int *)cexpr;                /* Restore value of 'circf' */
  336.  
  337.   rc = step(str, cexpr + sizeof(int));  /* Scan for expr within 'str' */
  338.  
  339.   if (rc == 0)                          /* If it's not in the string: */
  340.      return(NO_RMATCH);                       /* Return 'no match' */
  341.  
  342.   *startp = loc1;                       /* Store pointer to start of match */
  343.   *endp = loc2;                         /* Store pointer past end of match */
  344.  
  345.   return(RMATCH);                       /* Return 'match' */
  346. }
  347.  
  348. /*============================================================================*
  349.  * rcmpmsg() - Get error message based on error from rcompile().
  350.  *
  351.  * Description:
  352.  *   This subroutine gets the error message that corresponds to the value
  353.  *   that is returned by the rcompile() subroutine.
  354.  *
  355.  * Returns:
  356.  *   A pointer to the appropriate error message.  See the REGX_ #defined
  357.  *   labels in "util.h".
  358.  *============================================================================*/
  359. char *rcmpmsg(int n)
  360.  
  361. {
  362.   switch (n)
  363.   {
  364.      case 0:
  365.         return("Successful");
  366.  
  367.      case 11:
  368.         return("Range endpoint too large");
  369.      case 16:
  370.         return("Bad number");
  371.      case 25:
  372.         return("\\digit out of range");
  373.      case 36:
  374.         return("Illegal or missing delimiter");
  375.      case 41:
  376.         return("No remembered search string");
  377.      case 42:
  378.         return("() imbalance");
  379.      case 43:
  380.         return("Too many (");
  381.      case 44:
  382.         return("More than two numbers given in {}");
  383.      case 45:
  384.         return("} expected after \\");
  385.      case 46:
  386.         return("First number exceeds second in {}");
  387.      case 49:
  388.         return("[] imbalance");
  389.      case 50:
  390.         return("Regular expression overflow");
  391.      case 51:
  392.         return("Out of memory");
  393.      default:
  394.         return("Unknown error from compile()");
  395.   }
  396. }
  397.