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