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