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