home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW cawf 4.0.9 / regexp.c < prev    next >
Encoding:
Text File  |  1995-12-01  |  28.7 KB  |  1,126 lines  |  [TEXT/KAHL]
  1. e node.  (Note that much of the
  2.  * code generation knows about this implicit relationship.)
  3.  *
  4.  * Using two bytes for the "next" pointer is vast overkill for most things,
  5.  * but allows patterns to get big without disasters.
  6.  */
  7. #define    OP(p)    (*(p))
  8. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  9. #define    OPERAND(p)    ((p) + 3)
  10.  
  11. /*
  12.  * See regmagic.h for one further detail of program structure.
  13.  */
  14.  
  15.  
  16. /*
  17.  * Utility definitions.
  18.  */
  19. #ifndef CHARBITS
  20. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  21. #else
  22. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  23. #endif
  24.  
  25. #define    FAIL(m)    { regerror(m); return(NULL); }
  26. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  27. #define    META    "^$.[()|?+*\\"
  28.  
  29. /*
  30.  * Flags to be passed up and down.
  31.  */
  32. #define    HASWIDTH    01    /* Known never to match null string. */
  33. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  34. #define    SPSTART        04    /* Starts with * or +. */
  35. #define    WORST        0    /* Worst case. */
  36. #define STATIC 
  37. /*
  38.  * Global work variables for regcomp().
  39.  */
  40.  
  41. STATIC char *regparse;        /* Input-scan pointer. */
  42. STATIC int regnpar;        /* () count. */
  43. STATIC unsigned char regdummy;
  44. STATIC unsigned char *regcode;    /* Code-emit pointer; ®dummy = don't. */
  45. STATIC long regsize;        /* Code size. */
  46.  
  47. /*
  48.  * Forward declarations for regcomp()'s friends.
  49.  */
  50. _PROTOTYPE(STATIC unsigned char *reg, (int paren, int *flagp ));
  51. _PROTOTYPE(STATIC unsigned char *regbranch, (int *flagp ));
  52. _PROTOTYPE(STATIC unsigned char *regpiece, (int *flagp ));
  53. _PROTOTYPE(STATIC unsigned char *regatom, (int *flagp ));
  54. _PROTOTYPE(STATIC unsigned char *regnode, (int op ));
  55. _PROTOTYPE(STATIC void regc, (int b ));
  56. _PROTOTYPE(STATIC void reginsert, (int op, unsigned char *opnd ));
  57. _PROTOTYPE(STATIC void regtail, (unsigned char *p, unsigned char *val ));
  58. _PROTOTYPE(STATIC void regoptail, (unsigned char *p, unsigned char *val ));
  59. _PROTOTYPE(STATIC int regtry, (regexp *prog, unsigned char *string ));
  60. _PROTOTYPE(STATIC int regmatch, (unsigned char *prog ));
  61. _PROTOTYPE(STATIC int regrepeat, (unsigned char *p ));
  62. _PROTOTYPE(STATIC unsigned char *regnext, (unsigned char *p ));
  63. _PROTOTYPE(STATIC unsigned char *regprop, (unsigned char *op ));
  64.  
  65. #ifdef STRCSPN
  66. _PROTOTYPE(STATIC int strcspn, (unsigned char *s1, unsigned char *s2 ));
  67. #endif
  68.  
  69. /*
  70.  - regcomp - compile a regular expression into internal code
  71.  *
  72.  * We can't allocate space until we know how big the compiled form will be,
  73.  * but we can't compile it (and thus know how big it is) until we've got a
  74.  * place to put the code.  So we cheat:  we compile it twice, once with code
  75.  * generation turned off and size counting turned on, and once "for real".
  76.  * This also means that we don't allocate space until we are sure that the
  77.  * thing really will compile successfully, and we never have to move the
  78.  * code and thus invalidate pointers into it.  (Note that it has to be in
  79.  * one piece because free() must be able to free it all.)
  80.  *
  81.  * Beware that the optimization-preparation code in here knows about some
  82.  * of the structure of the compiled regexp.
  83.  */
  84. regexp *
  85. regcomp(exp)
  86. char *exp;
  87. {
  88.     register regexp *r;
  89.     register unsigned char *scan;
  90.     register unsigned char *longest;
  91.     register int len;
  92.     int flags;
  93.  
  94.     if (exp == NULL)
  95.         FAIL("NULL argument");
  96.  
  97.     /* First pass: determine size, legality. */
  98.     regparse = exp;
  99.     regnpar = 1;
  100.     regsize = 0L;
  101.     regcode = ®dummy;
  102.     regc(MAGIC);
  103.     if (reg(0, &flags) == NULL)
  104.         return(NULL);
  105.  
  106.     /* Small enough for pointer-storage convention? */
  107.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  108.         FAIL("regexp too big");
  109.  
  110.     /* Allocate space. */
  111.     r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  112.     if (r == NULL)
  113.         FAIL("out of space");
  114.  
  115.     /* Second pass: emit code. */
  116.     regparse = exp;
  117.     regnpar = 1;
  118.     regcode = r->program;
  119.     regc(MAGIC);
  120.     if (reg(0, &flags) == NULL)
  121.         return(NULL);
  122.  
  123.     /* Dig out information for optimizations. */
  124.     r->regstart = '\0';    /* Worst-case defaults. */
  125.     r->reganch = 0;
  126.     r->regmust = NULL;
  127.     r->regmlen = 0;
  128.     scan = r->program+1;            /* First BRANCH. */
  129.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  130.         scan = OPERAND(scan);
  131.  
  132.         /* Starting-point info. */
  133.         if (OP(scan) == EXACTLY)
  134.             r->regstart = *OPERAND(scan);
  135.         else if (OP(scan) == BOL)
  136.             r->reganch++;
  137.  
  138.         /*
  139.          * If there's something expensive in the r.e., find the
  140.          * longest literal string that must appear and make it the
  141.          * regmust.  Resolve ties in favor of later strings, since
  142.          * the regstart check works with the beginning of the r.e.
  143.          * and avoiding duplication strengthens checking.  Not a
  144.          * strong reason, but sufficient in the absence of others.
  145.          */
  146.         if (flags&SPSTART) {
  147.             longest = NULL;
  148.             len = 0;
  149.             for (; scan != NULL; scan = regnext(scan))
  150.                 if (OP(scan) == EXACTLY
  151.                 && strlen((char *)OPERAND(scan)) >= len) {
  152.                     longest = OPERAND(scan);
  153.                     len = strlen((char *)OPERAND(scan));
  154.                 }
  155.             r->regmust = longest;
  156.             r->regmlen = len;
  157.         }
  158.     }
  159.  
  160.     return(r);
  161. }
  162.  
  163. /*
  164.  - reg - regular expression, i.e. main body or parenthesized thing
  165.  *
  166.  * Caller must absorb opening parenthesis.
  167.  *
  168.  * Combining parenthesis handling with the base level of regular expression
  169.  * is a trifle forced, but the need to tie the tails of the branches to what
  170.  * follows makes it hard to avoid.
  171.  */
  172. STATIC unsigned char *
  173. reg(paren, flagp)
  174. int paren;            /* Parenthesized? */
  175. int *flagp;
  176. {
  177.     register unsigned char *ret;
  178.     register unsigned char *br;
  179.     register unsigned char *ender;
  180.     register int parno;
  181.     int flags;
  182.  
  183.     *flagp = HASWIDTH;    /* Tentatively. */
  184.  
  185.     /* Make an OPEN node, if parenthesized. */
  186.     if (paren) {
  187.         if (regnpar >= NSUBEXP)
  188.             FAIL("too many ()");
  189.         parno = regnpar;
  190.         regnpar++;
  191.         ret = regnode(OPEN+parno);
  192.     } else
  193.         ret = NULL;
  194.  
  195.     /* Pick up the branches, linking them together. */
  196.     br = regbranch(&flags);
  197.     if (br == NULL)
  198.         return(NULL);
  199.     if (ret != NULL)
  200.         regtail(ret, br);    /* OPEN -> first. */
  201.     else
  202.         ret = br;
  203.     if (!(flags&HASWIDTH))
  204.         *flagp &= ~HASWIDTH;
  205.     *flagp |= flags&SPSTART;
  206.     while (*regparse == '|') {
  207.         regparse++;
  208.         br = regbranch(&flags);
  209.         if (br == NULL)
  210.             return(NULL);
  211.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  212.         if (!(flags&HASWIDTH))
  213.             *flagp &= ~HASWIDTH;
  214.         *flagp |= flags&SPSTART;
  215.     }
  216.  
  217.     /* Make a closing node, and hook it on the end. */
  218.     ender = regnode((paren) ? CLOSE+parno : END);    
  219.     regtail(ret, ender);
  220.  
  221.     /* Hook the tails of the branches to the closing node. */
  222.     for (br = ret; br != NULL; br = regnext(br))
  223.         regoptail(br, ender);
  224.  
  225.     /* Check for proper termination. */
  226.     if (paren && *regparse++ != ')') {
  227.         FAIL("unmatched ()");
  228.     } else if (!paren && *regparse != '\0') {
  229.         if (*regparse == ')') {
  230.             FAIL("unmatched ()");
  231.         } else
  232.             FAIL("junk on end");    /* "Can't happen". */
  233.         /* NOTREACHED */
  234.     }
  235.  
  236.     return(ret);
  237. }
  238.  
  239. /*
  240.  - regbranch - one alternative of an | operator
  241.  *
  242.  * Implements the concatenation operator.
  243.  */
  244. STATIC unsigned char *
  245. regbranch(flagp)
  246. int *flagp;
  247. {
  248.     register unsigned char *ret;
  249.     register unsigned char *chain;
  250.     register unsigned char *latest;
  251.     int flags;
  252.  
  253.     *flagp = WORST;        /* Tentatively. */
  254.  
  255.     ret = regnode(BRANCH);
  256.     chain = NULL;
  257.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  258.         latest = regpiece(&flags);
  259.         if (latest == NULL)
  260.             return(NULL);
  261.         *flagp |= flags&HASWIDTH;
  262.         if (chain == NULL)    /* First piece. */
  263.             *flagp |= flags&SPSTART;
  264.         else
  265.             regtail(chain, latest);
  266.         chain = latest;
  267.     }
  268.     if (chain == NULL)    /* Loop ran zero times. */
  269.         (void) regnode(NOTHING);
  270.  
  271.     return(ret);
  272. }
  273.  
  274. /*
  275.  - regpiece - something followed by possible [*+?]
  276.  *
  277.  * Note that the branching code sequences used for ? and the general cases
  278.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  279.  * both the endmarker for their branch list and the body of the last branch.
  280.  * It might seem that this node could be dispensed with entirely, but the
  281.  * endmarker role is not redundant.
  282.  */
  283. STATIC unsigned char *
  284. regpiece(flagp)
  285. int *flagp;
  286. {
  287.     register unsigned char *ret;
  288.     register unsigned char op;
  289.     register unsigned char *next;
  290.     int flags;
  291.  
  292.     ret = regatom(&flags);
  293.     if (ret == NULL)
  294.         return(NULL);
  295.  
  296.     op = *regparse;
  297.     if (!ISMULT(op)) {
  298.         *flagp = flags;
  299.         return(ret);
  300.     }
  301.  
  302.     if (!(flags&HASWIDTH) && op != '?')
  303.         FAIL("*+ operand could be empty");
  304.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  305.  
  306.     if (op == '*' && (flags&SIMPLE))
  307.         reginsert(STAR, ret);
  308.     else if (op == '*') {
  309.         /* Emit x* as (x&|), where & means "self". */
  310.         reginsert(BRANCH, ret);            /* Either x */
  311.         regoptail(ret, regnode(BACK));        /* and loop */
  312.         regoptail(ret, ret);            /* back */
  313.         regtail(ret, regnode(BRANCH));        /* or */
  314.         regtail(ret, regnode(NOTHING));        /* null. */
  315.     } else if (op == '+' && (flags&SIMPLE))
  316.         reginsert(PLUS, ret);
  317.     else if (op == '+') {
  318.         /* Emit x+ as x(&|), where & means "self". */
  319.         next = regnode(BRANCH);            /* Either */
  320.         regtail(ret, next);
  321.         regtail(regnode(BACK), ret);        /* loop back */
  322.         regtail(next, regnode(BRANCH));        /* or */
  323.         regtail(ret, regnode(NOTHING));        /* null. */
  324.     } else if (op == '?') {
  325.         /* Emit x? as (x|) */
  326.         reginsert(BRANCH, ret);            /* Either x */
  327.         regtail(ret, regnode(BRANCH));        /* or */
  328.         next = regnode(NOTHING);        /* null. */
  329.         regtail(ret, next);
  330.         regoptail(ret, next);
  331.     }
  332.     regparse++;
  333.     if (ISMULT(*regparse))
  334.         FAIL("nested *?+");
  335.  
  336.     return(ret);
  337. }
  338.  
  339. /*
  340.  - regatom - the lowest level
  341.  *
  342.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  343.  * it can turn them into a single node, which is smaller to store and
  344.  * faster to run.  Backslashed characters are exceptions, each becoming a
  345.  * separate node; the code is simpler that way and it's not worth fixing.
  346.  */
  347. STATIC unsigned char *
  348. regatom(flagp)
  349. int *flagp;
  350. {
  351.     register unsigned char *ret;
  352.     int flags;
  353.  
  354.     *flagp = WORST;        /* Tentatively. */
  355.  
  356.     switch (*regparse++) {
  357.     case '^':
  358.         ret = regnode(BOL);
  359.         break;
  360.     case '$':
  361.         ret = regnode(EOL);
  362.         break;
  363.     case '.':
  364.         ret = regnode(ANY);
  365.         *flagp |= HASWIDTH|SIMPLE;
  366.         break;
  367.     case '[': {
  368.             register int class;
  369.             register int classend;
  370.  
  371.             if (*regparse == '^') {    /* Complement of range. */
  372.                 ret = regnode(ANYBUT);
  373.                 regparse++;
  374.             } else
  375.                 ret = regnode(ANYOF);
  376.             if (*regparse == ']' || *regparse == '-')
  377.                 regc(*regparse++);
  378.             while (*regparse != '\0' && *regparse != ']') {
  379.                 if (*regparse == '-') {
  380.                     regparse++;
  381.                     if (*regparse == ']' || *regparse == '\0')
  382.                         regc('-');
  383.                     else {
  384.                         class = UCHARAT(regparse-2)+1;
  385.                         classend = UCHARAT(regparse);
  386.                         if (class > classend+1)
  387.                             FAIL("invalid [] range");
  388.                         for (; class <= classend; class++)
  389.                             regc(class);
  390.                         regparse++;
  391.                     }
  392.                 } else
  393.                     regc(*regparse++);
  394.             }
  395.             regc('\0');
  396.             if (*regparse != ']')
  397.                 FAIL("unmatched []");
  398.             regparse++;
  399.             *flagp |= HASWIDTH|SIMPLE;
  400.         }
  401.         break;
  402.     case '(':
  403.         ret = reg(1, &flags);
  404.         if (ret == NULL)
  405.             return(NULL);
  406.         *flagp |= flags&(HASWIDTH|SPSTART);
  407.         break;
  408.     case '\0':
  409.     case '|':
  410.     case ')':
  411.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  412.         break;
  413.     case '?':
  414.     case '+':
  415.     case '*':
  416.         FAIL("?+* follows nothing");
  417.         break;
  418.     case '\\':
  419.         if (*regparse == '\0')
  420.             FAIL("trailing \\");
  421.         ret = regnode(EXACTLY);
  422.         regc(*regparse++);
  423.         regc('\0');
  424.         *flagp |= HASWIDTH|SIMPLE;
  425.         break;
  426.     default: {
  427.             register int len;
  428.             register unsigned char ender;
  429.  
  430.             regparse--;
  431. #ifdef    STRCSPN
  432.             len = strcspn(regparse, (unsigned char *)META);
  433. #else
  434.             len = strcspn((char *)regparse, META);
  435. #endif
  436.             if (len <= 0)
  437.                 FAIL("internal disaster");
  438.             ender = *(regparse+len);
  439.             if (len > 1 && ISMULT(ender))
  440.                 len--;        /* Back off clear of ?+* operand. */
  441.             *flagp |= HASWIDTH;
  442.             if (len == 1)
  443.                 *flagp |= SIMPLE;
  444.             ret = regnode(EXACTLY);
  445.             while (len > 0) {
  446.                 regc(*regparse++);
  447.                 len--;
  448.             }
  449.             regc('\0');
  450.         }
  451.         break;
  452.     }
  453.  
  454.     return(ret);
  455. }
  456.  
  457. /*
  458.  - regnode - emit a node
  459.  */
  460. STATIC unsigned char *            /* Location. */
  461. regnode(iop)
  462. int iop;
  463. {
  464.     register unsigned char *ret;
  465.     register unsigned char *ptr;
  466.     unsigned char op;
  467.  
  468.     op = (unsigned char) iop;
  469.     ret = regcode;
  470.     if (ret == ®dummy) {
  471.         regsize += 3;
  472.         return(ret);
  473.     }
  474.  
  475.     ptr = ret;
  476.     *ptr++ = op;
  477.     *ptr++ = '\0';        /* Null "next" pointer. */
  478.     *ptr++ = '\0';
  479.     regcode = ptr;
  480.  
  481.     return(ret);
  482. }
  483.  
  484. /*
  485.  - regc - emit (if appropriate) a byte of code
  486.  */
  487. STATIC void
  488. regc(ib)
  489. int ib;
  490. {
  491.     unsigned char b;
  492.  
  493.     b = (unsigned char) ib;
  494.     if (regcode != ®dummy)
  495.         *regcode++ = b;
  496.     else
  497.         regsize++;
  498. }
  499.  
  500. /*
  501.  - reginsert - insert an operator in front of already-emitted operand
  502.  *
  503.  * Means relocating the operand.
  504.  */
  505. STATIC void
  506. reginsert(iop, opnd)
  507. int iop;
  508. unsigned char *opnd;
  509. {
  510.     register unsigned char *src;
  511.     register unsigned char *dst;
  512.     register unsigned char *place;
  513.     unsigned char op;
  514.  
  515.     op = (unsigned char) iop;
  516.     if (regcode == ®dummy) {
  517.         regsize += 3;
  518.         return;
  519.     }
  520.  
  521.     src = regcode;
  522.     regcode += 3;
  523.     dst = regcode;
  524.     while (src > opnd)
  525.         *--dst = *--src;
  526.  
  527.     place = opnd;        /* Op node, where operand used to be. */
  528.     *place++ = op;
  529.     *place++ = '\0';
  530.     *place++ = '\0';
  531. }
  532.  
  533. /*
  534.  - regtail - set the next-pointer at the end of a node chain
  535.  */
  536. STATIC void
  537. regtail(p, val)
  538. unsigned char *p;
  539. unsigned char *val;
  540. {
  541.     register unsigned char *scan;
  542.     register unsigned char *temp;
  543.     register int offset;
  544.  
  545.     if (p == ®dummy)
  546.         return;
  547.  
  548.     /* Find last node. */
  549.     scan = p;
  550.     for (;;) {
  551.         temp = regnext(scan);
  552.         if (temp == NULL)
  553.             break;
  554.         scan = temp;
  555.     }
  556.  
  557.     if (OP(scan) == BACK)
  558.         offset = scan - val;
  559.     else
  560.         offset = val - scan;
  561.     *(scan+1) = (offset>>8)&0377;
  562.     *(scan+2) = offset&0377;
  563. }
  564.  
  565. /*
  566.  - regoptail - regtail on operand of first argument; nop if operandless
  567.  */
  568. STATIC void
  569. regoptail(p, val)
  570. unsigned char *p;
  571. unsigned char *val;
  572. {
  573.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  574.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  575.         return;
  576.     regtail(OPERAND(p), val);
  577. }
  578.  
  579. /*
  580.  * regexec and friends
  581.  */
  582.  
  583. /*
  584.  * Global work variables for regexec().
  585.  */
  586. STATIC unsigned char *reginput;        /* String-input pointer. */
  587. STATIC unsigned char *regbol;        /* Beginning of input, for ^ check. */
  588. STATIC unsigned char **regstartp;    /* Pointer to startp array. */
  589. STATIC unsigned char **regendp;        /* Ditto for endp. */
  590.  
  591. #ifdef DEBUG
  592. int regnarrate = 0;
  593. void regdump();
  594. STATIC unsigned char *regprop();
  595. #endif
  596.  
  597. /*
  598.  - regexec - match a regexp against a string
  599.  */
  600. int
  601. regexec(prog, string)
  602. register regexp *prog;
  603. register unsigned char *string;
  604. {
  605.     register unsigned char *s;
  606. #ifndef    STDLIB
  607.     extern char *strchr();
  608. #endif
  609.  
  610.     /* Be paranoid... */
  611.     if (prog == NULL || string == NULL) {
  612.         regerror("NULL parameter");
  613.         return(0);
  614.     }
  615.  
  616.     /* Check validity of program. */
  617.     if (UCHARAT(prog->program) != MAGIC) {
  618.         regerror("corrupted program");
  619.         return(0);
  620.     }
  621.  
  622.     /* If there is a "must appear" string, look for it. */
  623.     if (prog->regmust != NULL) {
  624.         s = string;
  625.         while ((s = (unsigned char *)strchr((char *)s,prog->regmust[0]))
  626.         != NULL) {
  627.             if (strncmp((char *)s, (char *)prog->regmust,
  628.                 prog->regmlen)
  629.             == 0)
  630.                 break;    /* Found it. */
  631.             s++;
  632.         }
  633.         if (s == NULL)    /* Not present. */
  634.             return(0);
  635.     }
  636.  
  637.     /* Mark beginning of line for ^ . */
  638.     regbol = string;
  639.  
  640.     /* Simplest case:  anchored match need be tried only once. */
  641.     if (prog->reganch)
  642.         return(regtry(prog, string));
  643.  
  644.     /* Messy cases:  unanchored match. */
  645.     s = string;
  646.     if (prog->regstart != '\0')
  647.         /* We know what char it must start with. */
  648.         while ((s = (unsigned char *)strchr((char *)s, prog->regstart))
  649.         != NULL) {
  650.             if (regtry(prog, s))
  651.                 return(1);
  652.             s++;
  653.         }
  654.     else
  655.         /* We don't -- general case. */
  656.         do {
  657.             if (regtry(prog, s))
  658.                 return(1);
  659.         } while (*s++ != '\0');
  660.  
  661.     /* Failure. */
  662.     return(0);
  663. }
  664.  
  665. /*
  666.  - regtry - try match at specific point
  667.  */
  668. STATIC int            /* 0 failure, 1 success */
  669. regtry(prog, string)
  670. regexp *prog;
  671. unsigned char *string;
  672. {
  673.     register int i;
  674.     register unsigned char **sp;
  675.     register unsigned char **ep;
  676.  
  677.     reginput = string;
  678.     regstartp = prog->startp;
  679.     regendp = prog->endp;
  680.  
  681.     sp = prog->startp;
  682.     ep = prog->endp;
  683.     for (i = NSUBEXP; i > 0; i--) {
  684.         *sp++ = NULL;
  685.         *ep++ = NULL;
  686.     }
  687.     if (regmatch(prog->program + 1)) {
  688.         prog->startp[0] = string;
  689.         prog->endp[0] = reginput;
  690.         return(1);
  691.     } else
  692.         return(0);
  693. }
  694.  
  695. /*
  696.  - regmatch - main matching routine
  697.  *
  698.  * Conceptually the strategy is simple:  check to see whether the current
  699.  * node matches, call self recursively to see whether the rest matches,
  700.  * and then act accordingly.  In practice we make some effort to avoid
  701.  * recursion, in particular by going through "ordinary" nodes (that don't
  702.  * need to know whether the rest of the match failed) by a loop instead of
  703.  * by recursion.
  704.  */
  705. STATIC int            /* 0 failure, 1 success */
  706. regmatch(prog)
  707. unsigned char *prog;
  708. {
  709.     register unsigned char *scan;    /* Current node. */
  710.     unsigned char *next;        /* Next node. */
  711. #ifndef    STDLIB
  712.     extern char *strchr();
  713. #endif
  714.  
  715.     scan = prog;
  716. #ifdef DEBUG
  717.     if (scan != NULL && regnarrate)
  718.         fprintf(stderr, "%s(\n", regprop(scan));
  719. #endif
  720.     while (scan != NULL) {
  721. #ifdef DEBUG
  722.         if (regnarrate)
  723.             fprintf(stderr, "%s...\n", regprop(scan));
  724. #endif
  725.         next = regnext(scan);
  726.  
  727.         switch (OP(scan)) {
  728.         case BOL:
  729.             if (reginput != regbol)
  730.                 return(0);
  731.             break;
  732.         case EOL:
  733.             if (*reginput != '\0')
  734.                 return(0);
  735.             break;
  736.         case ANY:
  737.             if (*reginput == '\0')
  738.                 return(0);
  739.             reginput++;
  740.             break;
  741.         case EXACTLY: {
  742.                 register int len;
  743.                 register unsigned char *opnd;
  744.  
  745.                 opnd = OPERAND(scan);
  746.                 /* Inline the first character, for speed. */
  747.                 if (*opnd != *reginput)
  748.                     return(0);
  749.                 len = strlen((char *)opnd);
  750.                 if (len > 1 && strncmp((char *)opnd,
  751.                    (char *)reginput, len)
  752.                 != 0)
  753.                     return(0);
  754.                 reginput += len;
  755.             }
  756.             break;
  757.         case ANYOF:
  758.             if (*reginput == '\0'
  759.             || strchr((char *)OPERAND(scan), *reginput) == NULL)
  760.                 return(0);
  761.             reginput++;
  762.             break;
  763.         case ANYBUT:
  764.             if (*reginput == '\0'
  765.             || strchr((char *)OPERAND(scan), *reginput) != NULL)
  766.                 return(0);
  767.             reginput++;
  768.             break;
  769.         case NOTHING:
  770.             break;
  771.         case BACK:
  772.             break;
  773.         case OPEN+1:
  774.         case OPEN+2:
  775.         case OPEN+3:
  776.         case OPEN+4:
  777.         case OPEN+5:
  778.         case OPEN+6:
  779.         case OPEN+7:
  780.         case OPEN+8:
  781.         case OPEN+9: {
  782.                 register int no;
  783.                 register unsigned char *save;
  784.  
  785.                 no = OP(scan) - OPEN;
  786.                 save = reginput;
  787.  
  788.                 if (regmatch(next)) {
  789.                     /*
  790.                      * Don't set startp if some later
  791.                      * invocation of the same parentheses
  792.                      * already has.
  793.                      */
  794.                     if (regstartp[no] == NULL)
  795.                         regstartp[no] = save;
  796.                     return(1);
  797.                 } else
  798.                     return(0);
  799.             }
  800.             break;
  801.         case CLOSE+1:
  802.         case CLOSE+2:
  803.         case CLOSE+3:
  804.         case CLOSE+4:
  805.         case CLOSE+5:
  806.         case CLOSE+6:
  807.         case CLOSE+7:
  808.         case CLOSE+8:
  809.         case CLOSE+9: {
  810.                 register int no;
  811.                 register unsigned char *save;
  812.  
  813.                 no = OP(scan) - CLOSE;
  814.                 save = reginput;
  815.  
  816.                 if (regmatch(next)) {
  817.                     /*
  818.                      * Don't set endp if some later
  819.                      * invocation of the same parentheses
  820.                      * already has.
  821.                      */
  822.                     if (regendp[no] == NULL)
  823.                         regendp[no] = save;
  824.                     return(1);
  825.                 } else
  826.                     return(0);
  827.             }
  828.             break;
  829.         case BRANCH: {
  830.                 register unsigned char *save;
  831.  
  832.                 if (OP(next) != BRANCH)        /* No choice. */
  833.                     next = OPERAND(scan);    /* Avoid recursion. */
  834.                 else {
  835.                     do {
  836.                         save = reginput;
  837.                         if (regmatch(OPERAND(scan)))
  838.                             return(1);
  839.                         reginput = save;
  840.                         scan = regnext(scan);
  841.                     } while (scan != NULL && OP(scan) == BRANCH);
  842.                     return(0);
  843.                     /* NOTREACHED */
  844.                 }
  845.             }
  846.             break;
  847.         case STAR:
  848.         case PLUS: {
  849.                 register unsigned char nextch;
  850.                 register int no;
  851.                 register unsigned char *save;
  852.                 register int min;
  853.  
  854.                 /*
  855.                  * Lookahead to avoid useless match attempts
  856.                  * when we know what character comes next.
  857.                  */
  858.                 nextch = '\0';
  859.                 if (OP(next) == EXACTLY)
  860.                     nextch = *OPERAND(next);
  861.                 min = (OP(scan) == STAR) ? 0 : 1;
  862.                 save = reginput;
  863.                 no = regrepeat(OPERAND(scan));
  864.                 while (no >= min) {
  865.                     /* If it could work, try it. */
  866.                     if (nextch == '\0' || *reginput == nextch)
  867.                         if (regmatch(next))
  868.                             return(1);
  869.                     /* Couldn't or didn't -- back up. */
  870.                     no--;
  871.                     reginput = save + no;
  872.                 }
  873.                 return(0);
  874.             }
  875.             break;
  876.         case END:
  877.             return(1);    /* Success! */
  878.             break;
  879.         default:
  880.             regerror("memory corruption");
  881.             return(0);
  882.             break;
  883.         }
  884.  
  885.         scan = next;
  886.     }
  887.  
  888.     /*
  889.      * We get here only if there's trouble -- normally "case END" is
  890.      * the terminating point.
  891.      */
  892.     regerror("corrupted pointers");
  893.     return(0);
  894. }
  895.  
  896. /*
  897.  - regrepeat - repeatedly match something simple, report how many
  898.  */
  899. STATIC int
  900. regrepeat(p)
  901. unsigned char *p;
  902. {
  903.     register int count = 0;
  904.     register unsigned char *scan;
  905.     register unsigned char *opnd;
  906.  
  907.     scan = reginput;
  908.     opnd = OPERAND(p);
  909.     switch (OP(p)) {
  910.     case ANY:
  911.         count = strlen((char *)scan);
  912.         scan += count;
  913.         break;
  914.     case EXACTLY:
  915.         while (*opnd == *scan) {
  916.             count++;
  917.             scan++;
  918.         }
  919.         break;
  920.     case ANYOF:
  921.         while (*scan != '\0' && strchr((char *)opnd, *scan) != NULL) {
  922.             count++;
  923.             scan++;
  924.         }
  925.         break;
  926.     case ANYBUT:
  927.         while (*scan != '\0' && strchr((char *)opnd, *scan) == NULL) {
  928.             count++;
  929.             scan++;
  930.         }
  931.         break;
  932.     default:        /* Oh dear.  Called inappropriately. */
  933.         regerror("internal foulup");
  934.         count = 0;    /* Best compromise. */
  935.         break;
  936.     }
  937.     reginput = scan;
  938.  
  939.     return(count);
  940. }
  941.  
  942. /*
  943.  - regnext - dig the "next" pointer out of a node
  944.  */
  945. STATIC unsigned char *
  946. regnext(p)
  947. register unsigned char *p;
  948. {
  949.     register int offset;
  950.  
  951.     if (p == ®dummy)
  952.         return(NULL);
  953.  
  954.     offset = NEXT(p);
  955.     if (offset == 0)
  956.         return(NULL);
  957.  
  958.     if (OP(p) == BACK)
  959.         return(p-offset);
  960.     else
  961.         return(p+offset);
  962. }
  963.  
  964. #ifdef DEBUG
  965.  
  966. STATIC unsigned char *regprop();
  967.  
  968. /*
  969.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  970.  */
  971. void
  972. regdump(r)
  973. regexp *r;
  974. {
  975.     register unsigned char *s;
  976.     register unsigned char op = EXACTLY;    /* Arbitrary non-END op. */
  977.     register unsigned char *next;
  978.     extern char *strchr();
  979.  
  980.  
  981.     s = r->program + 1;
  982.     while (op != END) {    /* While that wasn't END last time... */
  983.         op = OP(s);
  984.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  985.         next = regnext(s);
  986.         if (next == NULL)        /* Next ptr. */
  987.             printf("(0)");
  988.         else 
  989.             printf("(%d)", (s-r->program)+(next-s));
  990.         s += 3;
  991.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  992.             /* Literal string, where present. */
  993.             while (*s != '\0') {
  994.                 putchar(*s);
  995.                 s++;
  996.             }
  997.             s++;
  998.         }
  999.         putchar('\n');
  1000.     }
  1001.  
  1002.     /* Header fields of interest. */
  1003.     if (r->regstart != '\0')
  1004.         printf("start `%c' ", r->regstart);
  1005.     if (r->reganch)
  1006.         printf("anchored ");
  1007.     if (r->regmust != NULL)
  1008.         printf("must have \"%s\"", r->regmust);
  1009.     printf("\n");
  1010. }
  1011.  
  1012. /*
  1013.  - regprop - printable representation of opcode
  1014.  */
  1015. STATIC unsigned char *
  1016. regprop(op)
  1017. unsigned char *op;
  1018. {
  1019.     register unsigned char *p;
  1020.     STATIC unsigned char buf[50];
  1021.  
  1022.     (void) strcpy(buf, ":");
  1023.  
  1024.     switch (OP(op)) {
  1025.     case BOL:
  1026.         p = "BOL";
  1027.         break;
  1028.     case EOL:
  1029.         p = "EOL";
  1030.         break;
  1031.     case ANY:
  1032.         p = "ANY";
  1033.         break;
  1034.     case ANYOF:
  1035.         p = "ANYOF";
  1036.         break;
  1037.     case ANYBUT:
  1038.         p = "ANYBUT";
  1039.         break;
  1040.     case BRANCH:
  1041.         p = "BRANCH";
  1042.         break;
  1043.     case EXACTLY:
  1044.         p = "EXACTLY";
  1045.         break;
  1046.     case NOTHING:
  1047.         p = "NOTHING";
  1048.         break;
  1049.     case BACK:
  1050.         p = "BACK";
  1051.         break;
  1052.     case END:
  1053.         p = "END";
  1054.         break;
  1055.     case OPEN+1:
  1056.     case OPEN+2:
  1057.     case OPEN+3:
  1058.     case OPEN+4:
  1059.     case OPEN+5:
  1060.     case OPEN+6:
  1061.     case OPEN+7:
  1062.     case OPEN+8:
  1063.     case OPEN+9:
  1064.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1065.         p = NULL;
  1066.         break;
  1067.     case CLOSE+1:
  1068.     case CLOSE+2:
  1069.     case CLOSE+3:
  1070.     case CLOSE+4:
  1071.     case CLOSE+5:
  1072.     case CLOSE+6:
  1073.     case CLOSE+7:
  1074.     case CLOSE+8:
  1075.     case CLOSE+9:
  1076.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1077.         p = NULL;
  1078.         break;
  1079.     case STAR:
  1080.         p = "STAR";
  1081.         break;
  1082.     case PLUS:
  1083.         p = "PLUS";
  1084.         break;
  1085.     default:
  1086.         regerror("corrupted opcode");
  1087.         break;
  1088.     }
  1089.     if (p != NULL)
  1090.         (void) strcat(buf, p);
  1091.     return(buf);
  1092. }
  1093. #endif
  1094.  
  1095. /*
  1096.  * The following is provided for those people who do not have strcspn() in
  1097.  * their C libraries.  They should get off their butts and do something
  1098.  * about it; at least one public-domain implementation of those (highly
  1099.  * useful) string routines has been published on Usenet.
  1100.  */
  1101. #ifdef STRCSPN
  1102. /*
  1103.  * strcspn - find length of initial segment of s1 consisting entirely
  1104.  * of characters not from s2
  1105.  */
  1106.  
  1107. STATIC int
  1108. strcspn(s1, s2)
  1109. unsigned char *s1;
  1110. unsigned char *s2;
  1111. {
  1112.     register unsigned char *scan1;
  1113.     register unsigned char *scan2;
  1114.     register int count;
  1115.  
  1116.     count = 0;
  1117.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1118.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1119.             if (*scan1 == *scan2++)
  1120.                 return(count);
  1121.         count++;
  1122.     }
  1123.     return(count);
  1124. }
  1125. #endif
  1126.