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