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