home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume33 / problem / part03 / regexp.C < prev   
Encoding:
C/C++ Source or Header  |  1992-10-19  |  26.1 KB  |  847 lines
  1. /*
  2. ** regexp - a C++-ized version of Henry Spencers regexp package.
  3. **
  4. ** regexp.C regexp.C 1.7   Delta\'d: 15:39:42 9/22/92   Mike Lijewski, CNSF
  5. **
  6. **
  7. ** @\(#\)regexp.c    1.3 of 18 April 87
  8. **
  9. **    Copyright \(c\) 1986 by University of Toronto.
  10. **    Written by Henry Spencer.  Not derived from licensed software.
  11. **
  12. **    Permission is granted to anyone to use this software for any
  13. **    purpose on any computer system, and to redistribute it freely,
  14. **    subject to the following restrictions:
  15. **
  16. **    1. The author is not responsible for the consequences of use of
  17. **        this software, no matter how awful, even if they arise
  18. **        from defects in it.
  19. **
  20. **    2. The origin of this software must not be misrepresented, either
  21. **        by explicit claim or by omission.
  22. **
  23. **    3. Altered versions must be plainly marked as such, and must not
  24. **        be misrepresented as being the original software.
  25. **
  26. ** Beware that some of this code is subtly aware of the way operator
  27. ** precedence is structured in regular expressions.  Serious changes in
  28. ** regular-expression syntax might require a total rethink.
  29. */
  30.  
  31. #include <stdio.h>
  32. #include <stdlib.h>
  33. #include <string.h>
  34.  
  35. #include "regexp.h"
  36.  
  37. /*
  38. ** The "internal use only" fields in regexp.h are present to pass info from
  39. ** compile to execute that permits the execute phase to run lots faster on
  40. ** simple cases.  They are:
  41. **
  42. ** regstart    char that must begin a match; \'\0\' if none obvious
  43. ** reganch    is the match anchored \(at beginning-of-line only\)?
  44. ** regmust    string \(pointer into program\) that match must include, or 0
  45. ** regmlen    length of regmust string
  46. **
  47. ** Regstart and reganch permit very fast decisions on suitable starting points
  48. ** for a match, cutting down the work a lot.  Regmust permits fast rejection
  49. ** of lines that cannot possibly match.  The regmust tests are costly enough
  50. ** that regcomp\(\) supplies a regmust only if the r.e. contains something
  51. ** potentially expensive \(at present, the only such thing detected is * or +
  52. ** at the start of the r.e., which can involve a lot of backup\).  Regmlen is
  53. ** supplied because the test in regexec\(\) needs it and regcomp\(\) is computing
  54. ** it anyway.
  55. */
  56.  
  57. /*
  58. ** Structure for regexp "program".  This is essentially a linear encoding
  59. ** of a nondeterministic finite-state machine \(aka syntax charts or
  60. ** "railroad normal form" in parsing technology\).  Each node is an opcode
  61. ** plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  62. ** all nodes except BRANCH implement concatenation; a "next" pointer with
  63. ** a BRANCH on both ends of it is connecting two alternatives.  \(Here we
  64. ** have one of the subtle syntax dependencies:  an individual BRANCH \(as
  65. ** opposed to a collection of them\) is never concatenated with anything
  66. ** because of operator precedence.\)  The operand of some types of node is
  67. ** a literal string; for others, it is a node leading into a sub-FSM.  In
  68. ** particular, the operand of a BRANCH node is the first node of the branch.
  69. ** \(NB this is *not* a tree structure:  the tail of the branch connects
  70. ** to the thing following the set of BRANCHes.\)  The opcodes are:
  71. */
  72.  
  73. /* definition    number    opnd?    meaning */
  74. const int END     = 0;    /* no    End of program. */
  75. const int BOL     = 1;    /* no    Match "" at beginning of line. */
  76. const int EOL     = 2;    /* no    Match "" at end of line. */
  77. const int ANY     = 3;    /* no    Match any one character. */
  78. const int ANYOF   = 4;    /* str    Match any character in this string. */
  79. const int ANYBUT  = 5;    /* str    Match any character not in this string. */
  80. const int BRANCH  = 6;    /* node    Match this alternative, or the next... */
  81. const int BACK    = 7;    /* no    Match "", "next" ptr points backward. */
  82. const int EXACTLY = 8;    /* str    Match this string. */
  83. const int NOTHING = 9;    /* no    Match empty string. */
  84. const int STAR    = 10;    /* node    Match this \(simple\) thing 0 or more times. */
  85. const int PLUS    = 11;    /* node    Match this \(simple\) thing 1 or more times. */
  86. const int OPEN    = 20;    /* no    Mark this point in input as start of #n. */
  87.             /*    OPEN+1 is number 1, etc. */
  88. const int CLOSE   = 30;    /* no    Analogous to OPEN. */
  89.  
  90. /*
  91. ** Opcode notes:
  92. **
  93. ** BRANCH    The set of branches constituting a single choice are hooked
  94. **        together with their "next" pointers, since precedence prevents
  95. **        anything being concatenated to any individual branch.  The
  96. **        "next" pointer of the last BRANCH in a choice points to the
  97. **        thing following the whole choice.  This is also where the
  98. **        final "next" pointer of each individual branch points; each
  99. **        branch starts with the operand node of a BRANCH node.
  100. **
  101. ** BACK        Normal "next" pointers all implicitly point forward; BACK
  102. **        exists to make loop structures possible.
  103. **
  104. ** STAR,PLUS    \'?\', and complex \'*\' and \'+\', are implemented as circular
  105. **        BRANCH structures using BACK.  Simple cases \(one character
  106. **        per match\) are implemented with STAR and PLUS for speed
  107. **        and to minimize recursive plunges.
  108. **
  109. ** OPEN,CLOSE    ...are numbered at compile time.
  110. */
  111.  
  112. /*
  113. ** A node is one char of opcode followed by two chars of "next" pointer.
  114. ** "Next" pointers are stored as two 8-bit pieces, high order first.  The
  115. ** value is a positive offset from the opcode of the node containing it.
  116. ** An operand, if any, simply follows the node.  \(Note that much of the
  117. ** code generation knows about this implicit relationship.\)
  118. **
  119. ** Using two bytes for the "next" pointer is vast overkill for most things,
  120. ** but allows patterns to get big without disasters.
  121. */
  122.  
  123. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  124.  
  125. const int MAGIC = 0234;
  126. const char *const META = "^$.[()|?+*\\";
  127.  
  128. inline char OP(const char *const &p) { return *p;                            }
  129. inline char *OPERAND(char *p)     { return p + 3;                            }
  130. inline int UCHARAT(const char *p) { return (int)*(unsigned char *)p;         }
  131. inline int FAIL(const char *m)      { REerror = m; return 0;                   }
  132. inline int ISMULT(char c)         { return c == '*' || c == '+' || c == '?'; }
  133.  
  134. // Flags to be passed up and down.
  135. const int HASWIDTH = 01;    /* Known never to match null string. */
  136. const int SIMPLE   = 02;    /* Simple enough to be STAR/PLUS operand. */
  137. const int SPSTART  = 04;    /* Starts with * or +. */
  138. const int WORST    = 0;     /* Worst case. */
  139.  
  140. // our definition of REerror
  141. const char *REerror;
  142.  
  143. // Global work variables for regcomp\(\).
  144. static const char *regparse;    /* Input-scan pointer. */
  145. static int   regnpar;        /* \(\) count. */
  146. static char  regdummy;
  147. static char *regcode;        /* Code-emit pointer; ®dummy = don\'t. */
  148. static long  regsize;        /* Code size. */
  149.  
  150. /*
  151. ** regnext - dig the "next" pointer out of a node
  152. */
  153.  
  154. static char *regnext(char *p)
  155. {
  156.     if (p == ®dummy) return 0;
  157.     int offset = NEXT(p);
  158.     if (offset == 0) return 0;
  159.     return (OP(p) == BACK) ? p-offset : p+offset;
  160. }
  161.  
  162. /*
  163. ** regtail - set the next-pointer at the end of a node chain
  164. */
  165.  
  166. static void regtail(char *p, char *val)
  167. {
  168.     if (p == ®dummy) return;
  169.     
  170.     /* Find last node. */
  171.     char *scan = p;
  172.     char *temp;
  173.     for (;;) {
  174.         temp = regnext(scan);
  175.         if (temp == 0) break;
  176.         scan = temp;
  177.     }
  178.  
  179.     int offset = (OP(scan) == BACK) ? scan - val : val - scan;
  180.     *(scan+1) = (offset>>8)&0377;
  181.     *(scan+2) = offset&0377;
  182. }
  183.  
  184. /*
  185. ** regoptail - regtail on operand of first argument; nop if operandless
  186. */
  187.  
  188. static void regoptail(char *p, char *val)
  189. {
  190.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  191.     if (p == 0 || p == ®dummy || OP(p) != BRANCH) return;
  192.     regtail(OPERAND(p), val);
  193. }
  194.  
  195. /*
  196. ** regnode - emit a node
  197. */
  198.  
  199. static char *regnode(char op)
  200. {
  201.     char *ret = regcode;
  202.     if (ret == ®dummy) { regsize += 3; return ret; }
  203.     char *ptr = ret;
  204.     *ptr++ = op;
  205.     *ptr++ = '\0';  /* Null "next" pointer. */
  206.     *ptr++ = '\0';
  207.     regcode = ptr;
  208.     return ret;
  209. }
  210.  
  211. /*
  212. ** reginsert - insert an operator in front of already-emitted operand
  213. **
  214. ** Means relocating the operand.
  215. */
  216.  
  217. static void reginsert(char op, char *opnd)
  218. {
  219.     if (regcode == ®dummy) { regsize += 3; return; }
  220.     
  221.     char *src = regcode;
  222.     regcode += 3;
  223.     char *dst = regcode;
  224.     while (src > opnd) *--dst = *--src;
  225.     
  226.     char *place = opnd; // Op node, where operand used to be.
  227.     *place++ = op;
  228.     *place++ = '\0';
  229.     *place++ = '\0';
  230. }
  231.  
  232. /*
  233. ** regc - emit \(if appropriate\) a byte of code
  234. */
  235.  
  236. static inline void regc(char b)
  237. {
  238.     if (regcode != ®dummy)
  239.         *regcode++ = b;
  240.     else
  241.         regsize++;
  242. }
  243.  
  244. // forward reference
  245. static char *reg(int paren, int *flagp);
  246.  
  247. /*
  248. ** regatom - the lowest level
  249. **
  250. ** Optimization:  gobbles an entire sequence of ordinary characters so that
  251. ** it can turn them into a single node, which is smaller to store and
  252. ** faster to run.  Backslashed characters are exceptions, each becoming a
  253. ** separate node; the code is simpler that way and it\'s not worth fixing.
  254. */
  255.  
  256. static char *regatom(int *flagp)
  257. {
  258.     char *ret;
  259.     int flags;
  260.     
  261.     *flagp = WORST;        /* Tentatively. */
  262.     
  263.     switch (*regparse++) {
  264.       case '^': ret = regnode(BOL); break;
  265.       case '$': ret = regnode(EOL); break;
  266.       case '.': ret = regnode(ANY); *flagp |= HASWIDTH|SIMPLE; break;
  267.       case '[': {
  268.           if (*regparse == '^') {    /* Complement of range. */
  269.               ret = regnode(ANYBUT);
  270.               regparse++;
  271.           } else
  272.               ret = regnode(ANYOF);
  273.           if (*regparse == ']' || *regparse == '-') regc(*regparse++);
  274.           while (*regparse != '\0' && *regparse != ']') {
  275.               if (*regparse == '-') {
  276.                   regparse++;
  277.                   if (*regparse == ']' || *regparse == '\0')
  278.                       regc('-');
  279.                   else {
  280.                       int theclass = UCHARAT(regparse-2)+1;
  281.                       int classend = UCHARAT(regparse);
  282.                       if (theclass > classend+1) FAIL("invalid [] range");
  283.                       for (; theclass <= classend; theclass++) regc(theclass);
  284.                       regparse++;
  285.                   }
  286.               } else
  287.                   regc(*regparse++);
  288.           }
  289.           regc('\0');
  290.           if (*regparse != ']') FAIL("unmatched []");
  291.           regparse++;
  292.           *flagp |= HASWIDTH|SIMPLE;
  293.       }
  294.         break;
  295.       case '(':
  296.         ret = reg(1, &flags);
  297.         if (ret == 0) return 0;
  298.         *flagp |= flags&(HASWIDTH|SPSTART);
  299.         break;
  300.       case '\0':
  301.       case '|':
  302.       case ')':
  303.         FAIL("internal urp"); break; /* Supposed to be caught earlier. */
  304.       case '?':
  305.       case '+':
  306.       case '*':
  307.         FAIL("?+* follows nothing"); break;
  308.       case '\\':
  309.         if (*regparse == '\0') FAIL("trailing \\");
  310.         ret = regnode(EXACTLY);
  311.         regc(*regparse++);
  312.         regc('\0');
  313.         *flagp |= HASWIDTH|SIMPLE;
  314.         break;
  315.       default: {
  316.           regparse--;
  317.           int len = (int) strcspn(regparse, META);
  318.           if (len <= 0) FAIL("internal disaster");
  319.           char ender = *(regparse+len);
  320.           if (len > 1 && ISMULT(ender)) len--; // Back off clear of ?+* operand
  321.           *flagp |= HASWIDTH;
  322.           if (len == 1) *flagp |= SIMPLE;
  323.           ret = regnode(EXACTLY);
  324.           while (len > 0) { regc(*regparse++); len--; }
  325.           regc('\0');
  326.       }
  327.         break;
  328.     }
  329.     return ret;
  330. }
  331.  
  332. /*
  333. ** regpiece - something followed by possible \[*+?\]
  334. **
  335. ** Note that the branching code sequences used for ? and the general cases
  336. ** of * and + are somewhat optimized:  they use the same NOTHING node as
  337. ** both the endmarker for their branch list and the body of the last branch.
  338. ** It might seem that this node could be dispensed with entirely, but the
  339. ** endmarker role is not redundant.
  340. */
  341.  
  342. static char *regpiece(int *flagp)
  343. {
  344.     int flags;
  345.     char *ret = regatom(&flags);
  346.     if (ret == 0) return 0;
  347.     
  348.     char op = *regparse;
  349.     if (!ISMULT(op)) { *flagp = flags; return ret; }
  350.     
  351.     if (!(flags&HASWIDTH) && op != '?') FAIL("*+ operand could be empty");
  352.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  353.  
  354.     char *next;
  355.     if (op == '*' && (flags&SIMPLE))
  356.         reginsert(STAR, ret);
  357.     else if (op == '*') {
  358.         /* Emit x* as \(x&|\), where & means "self". */
  359.         reginsert(BRANCH, ret);            /* Either x */
  360.         regoptail(ret, regnode(BACK));        /* and loop */
  361.         regoptail(ret, ret);            /* back */
  362.         regtail(ret, regnode(BRANCH));        /* or */
  363.         regtail(ret, regnode(NOTHING));        /* null. */
  364.     } else if (op == '+' && (flags&SIMPLE))
  365.         reginsert(PLUS, ret);
  366.     else if (op == '+') {
  367.         /* Emit x+ as x\(&|\), where & means "self". */
  368.         next = regnode(BRANCH);            /* Either */
  369.         regtail(ret, next);
  370.         regtail(regnode(BACK), ret);        /* loop back */
  371.         regtail(next, regnode(BRANCH));        /* or */
  372.         regtail(ret, regnode(NOTHING));        /* null. */
  373.     } else if (op == '?') {
  374.         /* Emit x? as \(x|\) */
  375.         reginsert(BRANCH, ret);            /* Either x */
  376.         regtail(ret, regnode(BRANCH));        /* or */
  377.         next = regnode(NOTHING);        /* null. */
  378.         regtail(ret, next);
  379.         regoptail(ret, next);
  380.     }
  381.     regparse++;
  382.     if (ISMULT(*regparse)) FAIL("nested *?+");
  383.     return ret;
  384. }
  385.  
  386. /*
  387. ** regbranch - one alternative of an | operator
  388. **
  389. ** Implements the concatenation operator.
  390. */
  391.  
  392. static char *regbranch(int *flagp)
  393. {
  394.     *flagp = WORST; /* Tentatively. */
  395.     char *latest;
  396.     int flags;
  397.  
  398.     char *ret = regnode(BRANCH);
  399.     char *chain = 0;
  400.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  401.         latest = regpiece(&flags);
  402.         if (latest == 0) return 0;
  403.         *flagp |= flags&HASWIDTH;
  404.         if (chain == 0)    /* First piece. */
  405.             *flagp |= flags&SPSTART;
  406.         else
  407.             regtail(chain, latest);
  408.         chain = latest;
  409.     }
  410.     if (chain == 0) (void) regnode(NOTHING); /* Loop ran zero times. */
  411.     return ret;
  412. }
  413.  
  414. /*
  415. ** reg - regular expression, i.e. main body or parenthesized thing
  416. **
  417. ** Caller must absorb opening parenthesis.
  418. **
  419. ** Combining parenthesis handling with the base level of regular expression
  420. ** is a trifle forced, but the need to tie the tails of the branches to what
  421. ** follows makes it hard to avoid.
  422. */
  423.  
  424. static char *reg(int paren, int *flagp)
  425. {
  426.     *flagp = HASWIDTH;    /* Tentatively. */
  427.     char *ret;
  428.     int parno;
  429.     
  430.     /* Make an OPEN node, if parenthesized. */
  431.     if (paren) {
  432.         if (regnpar >= NSUBEXP) FAIL("too many ()");
  433.         parno = regnpar;
  434.         regnpar++;
  435.         ret = regnode(OPEN+parno);
  436.     } else
  437.         ret = 0;
  438.     
  439.     /* Pick up the branches, linking them together. */
  440.     int flags;
  441.     char *br = regbranch(&flags);
  442.     if (br == 0) return(0);
  443.     if (ret != 0)
  444.         regtail(ret, br);    /* OPEN -> first. */
  445.     else
  446.         ret = br;
  447.     if (!(flags&HASWIDTH)) *flagp &= ~HASWIDTH;
  448.     *flagp |= flags&SPSTART;
  449.     while (*regparse == '|') {
  450.         regparse++;
  451.         br = regbranch(&flags);
  452.         if (br == 0) return 0;
  453.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  454.         if (!(flags&HASWIDTH)) *flagp &= ~HASWIDTH;
  455.         *flagp |= flags&SPSTART;
  456.     }
  457.     
  458.     /* Make a closing node, and hook it on the end. */
  459.     char *ender = regnode((paren) ? CLOSE+parno : END);    
  460.     regtail(ret, ender);
  461.     
  462.     /* Hook the tails of the branches to the closing node. */
  463.     for (br = ret; br != 0; br = regnext(br)) regoptail(br, ender);
  464.     
  465.     /* Check for proper termination. */
  466.     if (paren && *regparse++ != ')') {
  467.         FAIL("unmatched ()");
  468.     } else if (!paren && *regparse != '\0') {
  469.         if (*regparse == ')') {
  470.             FAIL("unmatched ()");
  471.         } else
  472.             FAIL("junk on end");    /* "Can\'t happen". */
  473.         /* NOTREACHED */
  474.     }
  475.     return ret;
  476. }
  477.  
  478. /*
  479. ** regcomp - compile a regular expression into internal code
  480. **
  481. ** We can\'t allocate space until we know how big the compiled form will be,
  482. ** but we can\'t compile it \(and thus know how big it is\) until we\'ve got a
  483. ** place to put the code.  So we cheat:  we compile it twice, once with code
  484. ** generation turned off and size counting turned on, and once "for real".
  485. ** This also means that we don\'t allocate space until we are sure that the
  486. ** thing really will compile successfully, and we never have to move the
  487. ** code and thus invalidate pointers into it.  \(Note that it has to be in
  488. ** one piece because free\(\) must be able to free it all.\)
  489. **
  490. ** Beware that the optimization-preparation code in here knows about some
  491. ** of the structure of the compiled regexp.
  492. */
  493.  
  494. regexp *regcomp(const char *exp)
  495. {
  496.     if (exp == 0) FAIL("0 argument");
  497.     
  498.     /* First pass: determine size, legality. */
  499.     regparse = exp;
  500.     regnpar = 1;
  501.     regsize = 0L;
  502.     regcode = ®dummy;
  503.     regc(MAGIC);
  504.  
  505.     int flags;
  506.     if (reg(0, &flags) == 0) return 0;
  507.     
  508.     /* Small enough for pointer-storage convention? */
  509.     if (regsize >= 32767L) FAIL("regexp too big"); // Probably could be 65535L
  510.     
  511.     /* Allocate space. */
  512.     regexp *r = (regexp *) new char[sizeof(regexp) + (unsigned)regsize];
  513.     if (r == 0) FAIL("out of space");
  514.     
  515.     /* Second pass: emit code. */
  516.     regparse = exp;
  517.     regnpar  = 1;
  518.     regcode  = r->program;
  519.     regc(MAGIC);
  520.     if (reg(0, &flags) == 0) return 0;
  521.     
  522.     /* Dig out information for optimizations. */
  523.     r->regstart = '\0';    /* Worst-case defaults. */
  524.     r->reganch = 0;
  525.     r->regmust = 0;
  526.     r->regmlen = 0;
  527.     char *scan = r->program+1;         // First BRANCH.
  528.     if (OP(regnext(scan)) == END) {  // Only one top-level choice.
  529.         scan = OPERAND(scan);
  530.         /* Starting-point info. */
  531.         if (OP(scan) == EXACTLY)
  532.             r->regstart = *OPERAND(scan);
  533.         else if (OP(scan) == BOL)
  534.             r->reganch++;
  535.         /*
  536.          * If there\'s something expensive in the r.e., find the
  537.          * longest literal string that must appear and make it the
  538.          * regmust.  Resolve ties in favor of later strings, since
  539.          * the regstart check works with the beginning of the r.e.
  540.          * and avoiding duplication strengthens checking.  Not a
  541.          * strong reason, but sufficient in the absence of others.
  542.          */
  543.         char *longest;
  544.         int len;
  545.         if (flags&SPSTART) {
  546.             longest = 0;
  547.             len = 0;
  548.             for (; scan != 0; scan = regnext(scan))
  549.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  550.                     longest = OPERAND(scan);
  551.                     len = (int) strlen(OPERAND(scan));
  552.                 }
  553.             r->regmust = longest;
  554.             r->regmlen = len;
  555.         }
  556.     }
  557.     return r;
  558. }
  559.  
  560. /*
  561. ** regexec and friends
  562. */
  563.  
  564. /*
  565. ** Global work variables for regexec\(\).
  566. */
  567. static char *reginput;        /* String-input pointer. */
  568. static char *regbol;        /* Beginning of input, for ^ check. */
  569. static char **regstartp;    /* Pointer to startp array. */
  570. static char **regendp;        /* Ditto for endp. */
  571.  
  572. #ifdef DEBUG
  573. int regnarrate = 0;
  574. void regdump();
  575. static char *regprop();
  576. #endif
  577.  
  578. /*
  579. ** regrepeat - repeatedly match something simple, report how many
  580. */
  581.  
  582. static int regrepeat(char *p)
  583. {
  584.     int count = 0;
  585.     char *scan = reginput;
  586.     char *opnd = OPERAND(p);
  587.     switch (OP(p)) {
  588.       case ANY:
  589.         count = (int) strlen(scan);
  590.         scan += count;
  591.         break;
  592.       case EXACTLY:
  593.         while (*opnd == *scan) { count++; scan++; }
  594.         break;
  595.       case ANYOF:
  596.         while (*scan != '\0' && strchr(opnd, *scan) != 0) {
  597.             count++;
  598.             scan++;
  599.         }
  600.         break;
  601.       case ANYBUT:
  602.         while (*scan != '\0' && strchr(opnd, *scan) == 0) {
  603.             count++;
  604.             scan++;
  605.         }
  606.         break;
  607.       default:        /* Oh dear.  Called inappropriately. */
  608.         REerror = "internal foulup";
  609.         count = 0;    /* Best compromise. */
  610.         break;
  611.     }
  612.     reginput = scan;
  613.     return count;
  614. }
  615.  
  616. /*
  617. ** regmatch - main matching routine
  618. **
  619. ** Conceptually the strategy is simple:  check to see whether the current
  620. ** node matches, call self recursively to see whether the rest matches,
  621. ** and then act accordingly.  In practice we make some effort to avoid
  622. ** recursion, in particular by going through "ordinary" nodes \(that don\'t
  623. ** need to know whether the rest of the match failed\) by a loop instead of
  624. ** by recursion.
  625. **
  626. ** 0 failure, 1 success
  627. */
  628.  
  629. static int regmatch(char *prog)
  630. {
  631.     char *scan = prog;    /* Current node. */
  632.     char *next;        /* Next node. */
  633.     
  634. #ifdef DEBUG
  635.     if (scan != 0 && regnarrate) fprintf(stderr, "%s(\n", regprop(scan));
  636. #endif
  637.     while (scan != 0) {
  638. #ifdef DEBUG
  639.         if (regnarrate) fprintf(stderr, "%s...\n", regprop(scan));
  640. #endif
  641.         next = regnext(scan);
  642.         
  643.         switch (OP(scan)) {
  644.           case BOL: if (reginput != regbol) return 0; break;
  645.           case EOL: if (*reginput != '\0') return 0; break;
  646.           case ANY: if (*reginput == '\0') return(0); reginput++; break;
  647.           case EXACTLY: {
  648.               char *opnd = OPERAND(scan);
  649.               /* Inline the first character, for speed. */
  650.               if (*opnd != *reginput) return 0;
  651.               int len = (int) strlen(opnd);
  652.               if (len > 1 && strncmp(opnd, reginput, len) != 0) return 0;
  653.               reginput += len;
  654.           }
  655.             break;
  656.           case ANYOF:
  657.             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == 0)
  658.                 return 0;
  659.             reginput++;
  660.             break;
  661.           case ANYBUT:
  662.             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != 0)
  663.                 return 0;
  664.             reginput++;
  665.             break;
  666.           case NOTHING: break;
  667.           case BACK: break;
  668.           case OPEN+1:
  669.           case OPEN+2:
  670.           case OPEN+3:
  671.           case OPEN+4:
  672.           case OPEN+5:
  673.           case OPEN+6:
  674.           case OPEN+7:
  675.           case OPEN+8:
  676.           case OPEN+9: {
  677.               int no     = OP(scan) - OPEN;
  678.               char *save = reginput;
  679.               if (regmatch(next)) {
  680.                   /*
  681.                   ** Don\'t set startp if some later invocation of the same
  682.                   ** parentheses already has.
  683.                   */
  684.                   if (regstartp[no] == 0) regstartp[no] = save; return 1;
  685.               } else
  686.                   return 0;
  687.           }
  688.           case CLOSE+1:
  689.           case CLOSE+2:
  690.           case CLOSE+3:
  691.           case CLOSE+4:
  692.           case CLOSE+5:
  693.           case CLOSE+6:
  694.           case CLOSE+7:
  695.           case CLOSE+8:
  696.           case CLOSE+9: {
  697.               int no     = OP(scan) - CLOSE;
  698.               char *save = reginput;
  699.               if (regmatch(next)) {
  700.                   /*
  701.                   ** Don\'t set endp if some later invocation of the same
  702.                   ** parentheses already has.
  703.                   */
  704.                   if (regendp[no] == 0) regendp[no] = save;
  705.                   return 1;
  706.               } else
  707.                   return 0;
  708.           }
  709.           case BRANCH: {
  710.               char *save;
  711.               if (OP(next) != BRANCH)        /* No choice. */
  712.                   next = OPERAND(scan);    /* Avoid recursion. */
  713.               else {
  714.                   do {
  715.                       save = reginput;
  716.                       if (regmatch(OPERAND(scan))) return(1);
  717.                       reginput = save;
  718.                       scan = regnext(scan);
  719.                   } while (scan != 0 && OP(scan) == BRANCH);
  720.                   return 0;
  721.               }
  722.           }
  723.             break;
  724.           case STAR:
  725.           case PLUS: {
  726.               /*
  727.               ** Lookahead to avoid useless match attempts
  728.               ** when we know what character comes next.
  729.               */
  730.               char nextch = '\0';
  731.               if (OP(next) == EXACTLY) nextch = *OPERAND(next);
  732.               int min = (OP(scan) == STAR) ? 0 : 1;
  733.               char *save = reginput;
  734.               int no = regrepeat(OPERAND(scan));
  735.               while (no >= min) {
  736.                   /* If it could work, try it. */
  737.                   if (nextch == '\0' || *reginput == nextch)
  738.                       if (regmatch(next)) return(1);
  739.                   /* Couldn\'t or didn\'t -- back up. */
  740.                   no--;
  741.                   reginput = save + no;
  742.               }
  743.               return 0;
  744.           }
  745.           case END: return 1;    /* Success! */
  746.           default: REerror = "memory corruption"; return 0;
  747.         }
  748.         scan = next;
  749.     }
  750.     
  751.     /*
  752.      * We get here only if there\'s trouble -- normally "case END" is
  753.      * the terminating point.
  754.      */
  755.     REerror = "corrupted pointers";
  756.     return 0;
  757. }
  758.  
  759. /*
  760. ** regtry - try match at specific point
  761. **
  762. ** 0 failure, 1 success
  763. */
  764.  
  765. static int regtry(regexp *prog, char *string)
  766. {
  767.     reginput  = string;
  768.     regstartp = prog->startp;
  769.     regendp   = prog->endp;
  770.     
  771.     char **sp = prog->startp;
  772.     char **ep = prog->endp;
  773.     for (int i = NSUBEXP; i > 0; i--) { *sp++ = 0; *ep++ = 0; }
  774.     if (regmatch(prog->program + 1)) {
  775.         prog->startp[0] = string;
  776.         prog->endp[0] = reginput;
  777.         return 1;
  778.     } else
  779.         return 0;
  780. }
  781.  
  782. /*
  783. **  - regexec - match a regexp against a string
  784. **/
  785.  
  786. int regexec(regexp *prog, char *string)
  787. {
  788.     char *s;
  789.     
  790.     /* Be paranoid... */
  791.     if (prog == 0 || string == 0) { REerror = "0 parameter"; return 0; }
  792.     
  793.     /* Check validity of program. */
  794.     if (UCHARAT(prog->program) != MAGIC) {
  795.         REerror = "corrupted program";
  796.         return 0;
  797.     }
  798.     
  799.     /* If there is a "must appear" string, look for it. */
  800.     if (prog->regmust != 0) {
  801.         s = string;
  802.         while ((s = strchr(s, prog->regmust[0])) != 0) {
  803.             if (strncmp(s, prog->regmust, prog->regmlen) == 0) break; // Found
  804.             s++;
  805.         }
  806.         if (s == 0) return(0); /* Not present. */
  807.     }
  808.     
  809.     /* Mark beginning of line for ^ . */
  810.     regbol = string;
  811.     
  812.     /* Simplest case:  anchored match need be tried only once. */
  813.     if (prog->reganch) return(regtry(prog, string));
  814.     
  815.     /* Messy cases:  unanchored match. */
  816.     s = string;
  817.     if (prog->regstart != '\0')
  818.         /* We know what char it must start with. */
  819.         while ((s = strchr(s, prog->regstart)) != 0) {
  820.             if (regtry(prog, s)) return 1;
  821.             s++;
  822.         }
  823.     else
  824.         /* We don\'t -- general case. */
  825.         do {
  826.             if (regtry(prog, s)) return(1);
  827.         } while (*s++ != '\0');
  828.     
  829.     /* Failure. */
  830.     return 0;
  831. }
  832.  
  833. #ifdef TEST
  834. int main()
  835. {
  836.      char *str = "do";
  837.      char *test1 = "do it";
  838.      char *test2 = "dog it";
  839.      char *test3 = "don't do it";
  840.     regexp *rxp = regcomp(str);
  841.     if (!rxp) printf("regcomp() failed on %s\n", str);
  842.     if (regexec(rxp, test1)) printf("matched %s\n", test1);
  843.     if (regexec(rxp, test2)) printf("matched %s\n", test2);
  844.     if (regexec(rxp, test3)) printf("matched %s\n", test3);
  845. }
  846. #endif
  847.