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