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