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