home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / program / language / perl / Source / C / Regcomp < prev    next >
Encoding:
Text File  |  1990-11-13  |  29.3 KB  |  1,343 lines
  1. /* NOTE: this is derived from Henry Spencer's regexp code, and should not
  2.  * confused with the original package (see point 3 below).  Thanks, Henry!
  3.  */
  4.  
  5. /* Additional note: this code is very heavily munged from Henry's version
  6.  * in places.  In some spots I've traded clarity for efficiency, so don't
  7.  * blame Henry for some of the lack of readability.
  8.  */
  9.  
  10. /* $Header: regcomp.c,v 3.0.1.8 90/11/10 01:57:46 lwall Locked $
  11.  *
  12.  * $Log:    regcomp.c,v $
  13.  * Revision 3.0.1.8  90/11/10  01:57:46  lwall
  14.  * patch38: patterns with multiple constant strings occasionally malfed
  15.  * patch38: patterns like /foo.*foo/ sped up some
  16.  * 
  17.  * Revision 3.0.1.7  90/10/20  02:18:32  lwall
  18.  * patch37: /foo.*bar$/ wrongly optimized to do tail matching on "foo"
  19.  * 
  20.  * Revision 3.0.1.6  90/10/16  10:17:33  lwall
  21.  * patch29: patterns with multiple short literal strings sometimes failed
  22.  * 
  23.  * Revision 3.0.1.5  90/08/13  22:23:29  lwall
  24.  * patch28: /x{m}/ didn't work right
  25.  * 
  26.  * Revision 3.0.1.4  90/08/09  05:05:33  lwall
  27.  * patch19: sped up /x+y/ patterns greatly by not retrying on every x
  28.  * patch19: inhibited backoff on patterns anchored to the end like /\s+$/
  29.  * patch19: sped up {m,n} on simple items
  30.  * patch19: optimized /.*whatever/ to /^.*whatever/
  31.  * patch19: fixed character classes to allow backslashing hyphen
  32.  * 
  33.  * Revision 3.0.1.3  90/03/12  16:59:22  lwall
  34.  * patch13: pattern matches can now use \0 to mean \000
  35.  * 
  36.  * Revision 3.0.1.2  90/02/28  18:08:35  lwall
  37.  * patch9: /[\200-\377]/ didn't work on machines with signed chars
  38.  * 
  39.  * Revision 3.0.1.1  89/11/11  04:51:04  lwall
  40.  * patch2: /[\000]/ didn't work
  41.  * 
  42.  * Revision 3.0  89/10/18  15:22:29  lwall
  43.  * 3.0 baseline
  44.  * 
  45.  */
  46.  
  47. /*
  48.  * regcomp and regexec -- regsub and regerror are not used in perl
  49.  *
  50.  *    Copyright (c) 1986 by University of Toronto.
  51.  *    Written by Henry Spencer.  Not derived from licensed software.
  52.  *
  53.  *    Permission is granted to anyone to use this software for any
  54.  *    purpose on any computer system, and to redistribute it freely,
  55.  *    subject to the following restrictions:
  56.  *
  57.  *    1. The author is not responsible for the consequences of use of
  58.  *        this software, no matter how awful, even if they arise
  59.  *        from defects in it.
  60.  *
  61.  *    2. The origin of this software must not be misrepresented, either
  62.  *        by explicit claim or by omission.
  63.  *
  64.  *    3. Altered versions must be plainly marked as such, and must not
  65.  *        be misrepresented as being the original software.
  66.  *
  67.  *
  68.  ****    Alterations to Henry's code are...
  69.  ****
  70.  ****    Copyright (c) 1989, Larry Wall
  71.  ****
  72.  ****    You may distribute under the terms of the GNU General Public License
  73.  ****    as specified in the README file that comes with the perl 3.0 kit.
  74.  *
  75.  * Beware that some of this code is subtly aware of the way operator
  76.  * precedence is structured in regular expressions.  Serious changes in
  77.  * regular-expression syntax might require a total rethink.
  78.  */
  79. #include "EXTERN.h"
  80. #include "perl.h"
  81. #include "INTERN.h"
  82. #include "regcomp.h"
  83.  
  84. #ifndef STATIC
  85. #define    STATIC    static
  86. #endif
  87.  
  88. #define    ISMULT1(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  89. #define    ISMULT2(s)    ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
  90.     ((*s) == '{' && regcurly(s)))
  91. #define    META    "^$.[()|?+*\\"
  92.  
  93. /*
  94.  * Flags to be passed up and down.
  95.  */
  96. #define    HASWIDTH    01    /* Known never to match null string. */
  97. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  98. #define    SPSTART        04    /* Starts with * or +. */
  99. #define    WORST        0    /* Worst case. */
  100.  
  101. /*
  102.  * Global work variables for regcomp().
  103.  */
  104. static char *regprecomp;        /* uncompiled string. */
  105. static char *regparse;        /* Input-scan pointer. */
  106. static char *regxend;        /* End of input for compile */
  107. static int regnpar;        /* () count. */
  108. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  109. static long regsize;        /* Code size. */
  110. static int regfold;
  111. static int regsawbracket;    /* Did we do {d,d} trick? */
  112.  
  113. /*
  114.  * Forward declarations for regcomp()'s friends.
  115.  */
  116. STATIC int regcurly PROTO((char *));
  117. STATIC char *reg PROTO((int, int *));
  118. STATIC char *regbranch PROTO((int *));
  119. STATIC char *regpiece PROTO((int *));
  120. STATIC char *regatom PROTO((int *));
  121. STATIC char *regclass PROTO((void));
  122. STATIC char *regnode PROTO((int));        /* Was (char) */
  123. STATIC void regc PROTO((int));            /* Was (char) */
  124. STATIC void reginsert PROTO((int, char *));    /* Was (char, char *) */
  125. STATIC void regtail PROTO((char *, char *));
  126. STATIC void regoptail PROTO((char *, char *));
  127.  
  128. /*
  129.  - regcomp - compile a regular expression into internal code
  130.  *
  131.  * We can't allocate space until we know how big the compiled form will be,
  132.  * but we can't compile it (and thus know how big it is) until we've got a
  133.  * place to put the code.  So we cheat:  we compile it twice, once with code
  134.  * generation turned off and size counting turned on, and once "for real".
  135.  * This also means that we don't allocate space until we are sure that the
  136.  * thing really will compile successfully, and we never have to move the
  137.  * code and thus invalidate pointers into it.  (Note that it has to be in
  138.  * one piece because free() must be able to free it all.) [NB: not true in perl]
  139.  *
  140.  * Beware that the optimization-preparation code in here knows about some
  141.  * of the structure of the compiled regexp.  [I'll say.]
  142.  */
  143. regexp *
  144. regcomp(exp,xend,fold)
  145. char *exp;
  146. char *xend;
  147. int fold;
  148. {
  149.     register regexp *r;
  150.     register char *scan;
  151.     register STR *longish;
  152.     STR *longest;
  153.     register int len;
  154.     register char *first;
  155.     int flags;
  156.     int backish;
  157.     int backest;
  158.     int curback;
  159.     int sawplus = 0;
  160.  
  161.     if (exp == NULL)
  162.         fatal("NULL regexp argument");
  163.  
  164.     /* First pass: determine size, legality. */
  165.     regfold = fold;
  166.     regparse = exp;
  167.     regxend = xend;
  168.     regprecomp = nsavestr(exp,xend-exp);
  169.     regsawbracket = 0;
  170.     regnpar = 1;
  171.     regsize = 0L;
  172.     regcode = ®dummy;
  173.     regc(MAGIC);
  174.     if (reg(0, &flags) == NULL) {
  175.         Safefree(regprecomp);
  176.         return(NULL);
  177.     }
  178.  
  179.     /* Small enough for pointer-storage convention? */
  180.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  181.         FAIL("regexp too big");
  182.  
  183.     /* Allocate space. */
  184.     Newc(1001, r, sizeof(regexp) + (unsigned)regsize, char, regexp);
  185.     if (r == NULL)
  186.         FAIL("regexp out of space");
  187.  
  188.     /* Second pass: emit code. */
  189.     if (regsawbracket)
  190.         bcopy(regprecomp,exp,xend-exp);
  191.     r->precomp = regprecomp;
  192.     r->subbase = NULL;
  193.     regparse = exp;
  194.     regnpar = 1;
  195.     regcode = r->program;
  196.     regc(MAGIC);
  197.     if (reg(0, &flags) == NULL)
  198.         return(NULL);
  199.  
  200.     /* Dig out information for optimizations. */
  201.     r->regstart = Nullstr;    /* Worst-case defaults. */
  202.     r->reganch = 0;
  203.     r->regmust = Nullstr;
  204.     r->regback = -1;
  205.     r->regstclass = Nullch;
  206.     scan = r->program+1;            /* First BRANCH. */
  207.     if (OP(regnext(scan)) == END) {/* Only one top-level choice. */
  208.         scan = NEXTOPER(scan);
  209.  
  210.         first = scan;
  211.         while ((OP(first) > OPEN && OP(first) < CLOSE) ||
  212.             (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
  213.             (OP(first) == PLUS) ||
  214.             (OP(first) == CURLY && ARG1(first) > 0) ) {
  215.             if (OP(first) == CURLY)
  216.                 first += 4;
  217.             else if (OP(first) == PLUS)
  218.                 sawplus = 2;
  219.             first = NEXTOPER(first);
  220.         }
  221.  
  222.         /* Starting-point info. */
  223.         if (OP(first) == EXACTLY) {
  224.             r->regstart =
  225.                 str_make(OPERAND(first)+1,*OPERAND(first));
  226.             if (r->regstart->str_cur > !(sawstudy|fold))
  227.                 fbmcompile(r->regstart,fold);
  228.         }
  229.         else if ((exp = index(simple,OP(first))) != Nullch && exp > simple)
  230.             r->regstclass = first;
  231.         else if (OP(first) == BOUND || OP(first) == NBOUND)
  232.             r->regstclass = first;
  233.         else if (OP(first) == BOL ||
  234.             (OP(first) == STAR && OP(NEXTOPER(first)) == ANY) )
  235.             r->reganch = 1;        /* kinda turn .* into ^.* */
  236.         r->reganch |= sawplus;
  237.  
  238. #ifdef DEBUGGING
  239.         if (debug & 512)
  240.             fprintf(stderr,"first %d next %d offset %d\n",
  241.               OP(first), OP(NEXTOPER(first)), first - scan);
  242. #endif
  243.         /*
  244.          * If there's something expensive in the r.e., find the
  245.          * longest literal string that must appear and make it the
  246.          * regmust.  Resolve ties in favor of later strings, since
  247.          * the regstart check works with the beginning of the r.e.
  248.          * and avoiding duplication strengthens checking.  Not a
  249.          * strong reason, but sufficient in the absence of others.
  250.          * [Now we resolve ties in favor of the earlier string if
  251.          * it happens that curback has been invalidated, since the
  252.          * earlier string may buy us something the later one won't.]
  253.          */
  254.         longish = str_make("",0);
  255.         longest = str_make("",0);
  256.         len = 0;
  257.         curback = 0;
  258.         backish = 0;
  259.         backest = 0;
  260.         while (OP(scan) != END) {
  261.             if (OP(scan) == BRANCH) {
  262.                 if (OP(regnext(scan)) == BRANCH) {
  263.                 curback = -30000;
  264.                 while (OP(scan) == BRANCH)
  265.                     scan = regnext(scan);
  266.                 }
  267.                 else    /* single branch is ok */
  268.                 scan = NEXTOPER(scan);
  269.             }
  270.             if (OP(scan) == EXACTLY) {
  271.                 first = scan;
  272.                 while (OP(regnext(scan)) >= CLOSE)
  273.                 scan = regnext(scan);
  274.                 if (curback - backish == len) {
  275.                 str_ncat(longish, OPERAND(first)+1,
  276.                     *OPERAND(first));
  277.                 len += *OPERAND(first);
  278.                 curback += *OPERAND(first);
  279.                 first = regnext(scan);
  280.                 }
  281.                 else if (*OPERAND(first) >= len + (curback >= 0)) {
  282.                 len = *OPERAND(first);
  283.                 str_nset(longish, OPERAND(first)+1,len);
  284.                 backish = curback;
  285.                 curback += len;
  286.                 first = regnext(scan);
  287.                 }
  288.                 else
  289.                 curback += *OPERAND(first);
  290.             }
  291.             else if (index(varies,OP(scan))) {
  292.                 curback = -30000;
  293.                 len = 0;
  294.                 if (longish->str_cur > longest->str_cur) {
  295.                 str_sset(longest,longish);
  296.                 backest = backish;
  297.                 }
  298.                 str_nset(longish,"",0);
  299.             }
  300.             else if (index(simple,OP(scan))) {
  301.                 curback++;
  302.                 len = 0;
  303.                 if (longish->str_cur > longest->str_cur) {
  304.                 str_sset(longest,longish);
  305.                 backest = backish;
  306.                 }
  307.                 str_nset(longish,"",0);
  308.             }
  309.             scan = regnext(scan);
  310.         }
  311.  
  312.         /* Prefer earlier on tie, unless we can tail match latter */
  313.  
  314.         if (longish->str_cur + (OP(first) == EOL) > longest->str_cur) {
  315.             str_sset(longest,longish);
  316.             backest = backish;
  317.         }
  318.         else
  319.             str_nset(longish,"",0);
  320.         if (longest->str_cur
  321.             &&
  322.             (!r->regstart
  323.              ||
  324.              !fbminstr((unsigned char *)(r->regstart->str_ptr),
  325.               (unsigned char *)(r->regstart->str_ptr + r->regstart->str_cur),
  326.               longest)
  327.             )
  328.            )
  329.         {
  330.             r->regmust = longest;
  331.             if (backest < 0)
  332.                 backest = -1;
  333.             r->regback = backest;
  334.             if (longest->str_cur
  335.               > !(sawstudy || fold || OP(first) == EOL) )
  336.                 fbmcompile(r->regmust,fold);
  337.             r->regmust->str_u.str_useful = 100;
  338.             if (OP(first) == EOL && longish->str_cur)
  339.                 r->regmust->str_pok |= SP_TAIL;
  340.         }
  341.         else
  342.             str_free(longest);
  343.         str_free(longish);
  344.     }
  345.  
  346.     r->do_folding = fold;
  347.     r->nparens = regnpar - 1;
  348. #ifdef DEBUGGING
  349.     if (debug & 512)
  350.         regdump(r);
  351. #endif
  352.     return(r);
  353. }
  354.  
  355. /*
  356.  - reg - regular expression, i.e. main body or parenthesized thing
  357.  *
  358.  * Caller must absorb opening parenthesis.
  359.  *
  360.  * Combining parenthesis handling with the base level of regular expression
  361.  * is a trifle forced, but the need to tie the tails of the branches to what
  362.  * follows makes it hard to avoid.
  363.  */
  364. static char *
  365. reg(paren, flagp)
  366. int paren;            /* Parenthesized? */
  367. int *flagp;
  368. {
  369.     register char *ret;
  370.     register char *br;
  371.     register char *ender;
  372.     register int parno;
  373.     int flags;
  374.  
  375.     *flagp = HASWIDTH;    /* Tentatively. */
  376.  
  377.     /* Make an OPEN node, if parenthesized. */
  378.     if (paren) {
  379.         if (regnpar >= NSUBEXP)
  380.             FAIL("too many () in regexp");
  381.         parno = regnpar;
  382.         regnpar++;
  383.         ret = regnode(OPEN+parno);
  384.     } else
  385.         ret = NULL;
  386.  
  387.     /* Pick up the branches, linking them together. */
  388.     br = regbranch(&flags);
  389.     if (br == NULL)
  390.         return(NULL);
  391.     if (ret != NULL)
  392.         regtail(ret, br);    /* OPEN -> first. */
  393.     else
  394.         ret = br;
  395.     if (!(flags&HASWIDTH))
  396.         *flagp &= ~HASWIDTH;
  397.     *flagp |= flags&SPSTART;
  398.     while (*regparse == '|') {
  399.         regparse++;
  400.         br = regbranch(&flags);
  401.         if (br == NULL)
  402.             return(NULL);
  403.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  404.         if (!(flags&HASWIDTH))
  405.             *flagp &= ~HASWIDTH;
  406.         *flagp |= flags&SPSTART;
  407.     }
  408.  
  409.     /* Make a closing node, and hook it on the end. */
  410.     ender = regnode((paren) ? CLOSE+parno : END);    
  411.     regtail(ret, ender);
  412.  
  413.     /* Hook the tails of the branches to the closing node. */
  414.     for (br = ret; br != NULL; br = regnext(br))
  415.         regoptail(br, ender);
  416.  
  417.     /* Check for proper termination. */
  418.     if (paren && *regparse++ != ')') {
  419.         FAIL("unmatched () in regexp");
  420.     } else if (!paren && regparse < regxend) {
  421.         if (*regparse == ')') {
  422.             FAIL("unmatched () in regexp");
  423.         } else
  424.             FAIL("junk on end of regexp");    /* "Can't happen". */
  425.         /* NOTREACHED */
  426.     }
  427.  
  428.     return(ret);
  429. }
  430.  
  431. /*
  432.  - regbranch - one alternative of an | operator
  433.  *
  434.  * Implements the concatenation operator.
  435.  */
  436. static char *
  437. regbranch(flagp)
  438. int *flagp;
  439. {
  440.     register char *ret;
  441.     register char *chain;
  442.     register char *latest;
  443.     int flags;
  444.  
  445.     *flagp = WORST;        /* Tentatively. */
  446.  
  447.     ret = regnode(BRANCH);
  448.     chain = NULL;
  449.     while (regparse < regxend && *regparse != '|' && *regparse != ')') {
  450.         latest = regpiece(&flags);
  451.         if (latest == NULL)
  452.             return(NULL);
  453.         *flagp |= flags&HASWIDTH;
  454.         if (chain == NULL)    /* First piece. */
  455.             *flagp |= flags&SPSTART;
  456.         else
  457.             regtail(chain, latest);
  458.         chain = latest;
  459.     }
  460.     if (chain == NULL)    /* Loop ran zero times. */
  461.         (void) regnode(NOTHING);
  462.  
  463.     return(ret);
  464. }
  465.  
  466. /*
  467.  - regpiece - something followed by possible [*+?]
  468.  *
  469.  * Note that the branching code sequences used for ? and the general cases
  470.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  471.  * both the endmarker for their branch list and the body of the last branch.
  472.  * It might seem that this node could be dispensed with entirely, but the
  473.  * endmarker role is not redundant.
  474.  */
  475. static char *
  476. regpiece(flagp)
  477. int *flagp;
  478. {
  479.     register char *ret;
  480.     register char op;
  481.     register char *next;
  482.     int flags;
  483.     char *origparse = regparse;
  484.     int orignpar = regnpar;
  485.     char *max;
  486.     int iter;
  487.     char ch;
  488.  
  489.     ret = regatom(&flags);
  490.     if (ret == NULL)
  491.         return(NULL);
  492.  
  493.     op = *regparse;
  494.  
  495.     /* Here's a total kludge: if after the atom there's a {\d+,?\d*}
  496.      * then we decrement the first number by one and reset our
  497.      * parsing back to the beginning of the same atom.  If the first number
  498.      * is down to 0, decrement the second number instead and fake up
  499.      * a ? after it.  Given the way this compiler doesn't keep track
  500.      * of offsets on the first pass, this is the only way to replicate
  501.      * a piece of code.  Sigh.
  502.      */
  503.     if (op == '{' && regcurly(regparse)) {
  504.         next = regparse + 1;
  505.         max = Nullch;
  506.         while (isdigit(*next) || *next == ',') {
  507.         if (*next == ',') {
  508.             if (max)
  509.             break;
  510.             else
  511.             max = next;
  512.         }
  513.         next++;
  514.         }
  515.         if (*next == '}') {        /* got one */
  516.         if (!max)
  517.             max = next;
  518.         regparse++;
  519.         iter = atoi(regparse);
  520.         if (flags&SIMPLE) {    /* we can do it right after all */
  521.             int tmp;
  522.  
  523.             reginsert(CURLY, ret);
  524.             if (*max == ',')
  525.             max++;
  526.             else
  527.             max = regparse;
  528.             tmp = atoi(max);
  529.             if (tmp && tmp < iter)
  530.             fatal("Can't do {n,m} with n > m");
  531.             if (regcode != ®dummy) {
  532. #ifdef REGALIGN
  533.             *(unsigned short *)(ret+3) = iter;
  534.             *(unsigned short *)(ret+5) = tmp;
  535. #else
  536.             ret[3] = iter >> 8; ret[4] = iter & 0377;
  537.             ret[5] = tmp  >> 8; ret[6] = tmp  & 0377;
  538. #endif
  539.             }
  540.             regparse = next;
  541.             goto nest_check;
  542.         }
  543.         regsawbracket++;    /* remember we clobbered exp */
  544.         if (iter > 0) {
  545.             ch = *max;
  546.             sprintf(regparse,"%.*d", max-regparse, iter - 1);
  547.             *max = ch;
  548.             if (*max == ',' && max[1] != '}') {
  549.             if (atoi(max+1) <= 0)
  550.                 fatal("Can't do {n,m} with n > m");
  551.             ch = *next;
  552.             sprintf(max+1,"%.*d", next-(max+1), atoi(max+1) - 1);
  553.             *next = ch;
  554.             }
  555.             if (iter != 1 || *max == ',') {
  556.             regparse = origparse;    /* back up input pointer */
  557.             regnpar = orignpar;    /* don't make more parens */
  558.             }
  559.             else {
  560.             regparse = next;
  561.             goto nest_check;
  562.             }
  563.             *flagp = flags;
  564.             return ret;
  565.         }
  566.         if (*max == ',') {
  567.             max++;
  568.             iter = atoi(max);
  569.             if (max == next) {        /* any number more? */
  570.             regparse = next;
  571.             op = '*';        /* fake up one with a star */
  572.             }
  573.             else if (iter > 0) {
  574.             op = '?';        /* fake up optional atom */
  575.             ch = *next;
  576.             sprintf(max,"%.*d", next-max, iter - 1);
  577.             *next = ch;
  578.             if (iter == 1)
  579.                 regparse = next;
  580.             else {
  581.                 regparse = origparse - 1; /* offset ++ below */
  582.                 regnpar = orignpar;
  583.             }
  584.             }
  585.             else
  586.             fatal("Can't do {n,0}");
  587.         }
  588.         else
  589.             fatal("Can't do {0}");
  590.         }
  591.     }
  592.  
  593.     if (!ISMULT1(op)) {
  594.         *flagp = flags;
  595.         return(ret);
  596.     }
  597.  
  598.     if (!(flags&HASWIDTH) && op != '?')
  599.         FAIL("regexp *+ operand could be empty");
  600.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  601.  
  602.     if (op == '*' && (flags&SIMPLE))
  603.         reginsert(STAR, ret);
  604.     else if (op == '*') {
  605.         /* Emit x* as (x&|), where & means "self". */
  606.         reginsert(BRANCH, ret);            /* Either x */
  607.         regoptail(ret, regnode(BACK));        /* and loop */
  608.         regoptail(ret, ret);            /* back */
  609.         regtail(ret, regnode(BRANCH));        /* or */
  610.         regtail(ret, regnode(NOTHING));        /* null. */
  611.     } else if (op == '+' && (flags&SIMPLE))
  612.         reginsert(PLUS, ret);
  613.     else if (op == '+') {
  614.         /* Emit x+ as x(&|), where & means "self". */
  615.         next = regnode(BRANCH);            /* Either */
  616.         regtail(ret, next);
  617.         regtail(regnode(BACK), ret);        /* loop back */
  618.         regtail(next, regnode(BRANCH));        /* or */
  619.         regtail(ret, regnode(NOTHING));        /* null. */
  620.     } else if (op == '?') {
  621.         /* Emit x? as (x|) */
  622.         reginsert(BRANCH, ret);            /* Either x */
  623.         regtail(ret, regnode(BRANCH));        /* or */
  624.         next = regnode(NOTHING);        /* null. */
  625.         regtail(ret, next);
  626.         regoptail(ret, next);
  627.     }
  628.       nest_check:
  629.     regparse++;
  630.     if (ISMULT2(regparse))
  631.         FAIL("nested *?+ in regexp");
  632.  
  633.     return(ret);
  634. }
  635.  
  636. /*
  637.  - regatom - the lowest level
  638.  *
  639.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  640.  * it can turn them into a single node, which is smaller to store and
  641.  * faster to run.  Backslashed characters are exceptions, each becoming a
  642.  * separate node; the code is simpler that way and it's not worth fixing.
  643.  *
  644.  * [Yes, it is worth fixing, some scripts can run twice the speed.]
  645.  */
  646. static char *
  647. regatom(flagp)
  648. int *flagp;
  649. {
  650.     register char *ret;
  651.     int flags;
  652.  
  653.     *flagp = WORST;        /* Tentatively. */
  654.  
  655.     switch (*regparse++) {
  656.     case '^':
  657.         ret = regnode(BOL);
  658.         break;
  659.     case '$':
  660.         ret = regnode(EOL);
  661.         break;
  662.     case '.':
  663.         ret = regnode(ANY);
  664.         *flagp |= HASWIDTH|SIMPLE;
  665.         break;
  666.     case '[':
  667.         ret = regclass();
  668.         *flagp |= HASWIDTH|SIMPLE;
  669.         break;
  670.     case '(':
  671.         ret = reg(1, &flags);
  672.         if (ret == NULL)
  673.             return(NULL);
  674.         *flagp |= flags&(HASWIDTH|SPSTART);
  675.         break;
  676.     case '|':
  677.     case ')':
  678.         FAIL("internal urp in regexp");    /* Supposed to be caught earlier. */
  679.         break;
  680.     case '?':
  681.     case '+':
  682.     case '*':
  683.         FAIL("?+* follows nothing in regexp");
  684.         break;
  685.     case '\\':
  686.         switch (*regparse) {
  687.         case 'w':
  688.             ret = regnode(ALNUM);
  689.             *flagp |= HASWIDTH|SIMPLE;
  690.             regparse++;
  691.             break;
  692.         case 'W':
  693.             ret = regnode(NALNUM);
  694.             *flagp |= HASWIDTH|SIMPLE;
  695.             regparse++;
  696.             break;
  697.         case 'b':
  698.             ret = regnode(BOUND);
  699.             *flagp |= SIMPLE;
  700.             regparse++;
  701.             break;
  702.         case 'B':
  703.             ret = regnode(NBOUND);
  704.             *flagp |= SIMPLE;
  705.             regparse++;
  706.             break;
  707.         case 's':
  708.             ret = regnode(SPACE);
  709.             *flagp |= HASWIDTH|SIMPLE;
  710.             regparse++;
  711.             break;
  712.         case 'S':
  713.             ret = regnode(NSPACE);
  714.             *flagp |= HASWIDTH|SIMPLE;
  715.             regparse++;
  716.             break;
  717.         case 'd':
  718.             ret = regnode(DIGIT);
  719.             *flagp |= HASWIDTH|SIMPLE;
  720.             regparse++;
  721.             break;
  722.         case 'D':
  723.             ret = regnode(NDIGIT);
  724.             *flagp |= HASWIDTH|SIMPLE;
  725.             regparse++;
  726.             break;
  727.         case 'n':
  728.         case 'r':
  729.         case 't':
  730.         case 'f':
  731.             goto defchar;
  732.         case '0': case '1': case '2': case '3': case '4':
  733.         case '5': case '6': case '7': case '8': case '9':
  734.             if (isdigit(regparse[1]) || *regparse == '0')
  735.                 goto defchar;
  736.             else {
  737.                 ret = regnode(REF + *regparse++ - '0');
  738.                 *flagp |= SIMPLE;
  739.             }
  740.             break;
  741.         case '\0':
  742.             if (regparse >= regxend)
  743.                 FAIL("trailing \\ in regexp");
  744.             /* FALL THROUGH */
  745.         default:
  746.             goto defchar;
  747.         }
  748.         break;
  749.     default: {
  750.             register int len;
  751.             register char ender;
  752.             register char *p;
  753.             char *oldp;
  754.             int foo;
  755.  
  756.             defchar:
  757.             ret = regnode(EXACTLY);
  758.             regc(0);        /* save spot for len */
  759.             for (len=0, p=regparse-1;
  760.               len < 127 && p < regxend;
  761.               len++)
  762.             {
  763.                 oldp = p;
  764.                 switch (*p) {
  765.                 case '^':
  766.                 case '$':
  767.                 case '.':
  768.                 case '[':
  769.                 case '(':
  770.                 case ')':
  771.                 case '|':
  772.                 goto loopdone;
  773.                 case '\\':
  774.                 switch (*++p) {
  775.                 case 'w':
  776.                 case 'W':
  777.                 case 'b':
  778.                 case 'B':
  779.                 case 's':
  780.                 case 'S':
  781.                 case 'd':
  782.                 case 'D':
  783.                     --p;
  784.                     goto loopdone;
  785.                 case 'n':
  786.                     ender = '\n';
  787.                     p++;
  788.                     break;
  789.                 case 'r':
  790.                     ender = '\r';
  791.                     p++;
  792.                     break;
  793.                 case 't':
  794.                     ender = '\t';
  795.                     p++;
  796.                     break;
  797.                 case 'f':
  798.                     ender = '\f';
  799.                     p++;
  800.                     break;
  801.                 case '0': case '1': case '2': case '3':case '4':
  802.                 case '5': case '6': case '7': case '8':case '9':
  803.                     if (isdigit(p[1]) || *p == '0') {
  804.                     foo = *p - '0';
  805.                     if (isdigit(p[1]))
  806.                         foo = (foo<<3) + *++p - '0';
  807.                     if (isdigit(p[1]))
  808.                         foo = (foo<<3) + *++p - '0';
  809.                     ender = foo;
  810.                     p++;
  811.                     }
  812.                     else {
  813.                     --p;
  814.                     goto loopdone;
  815.                     }
  816.                     break;
  817.                 case '\0':
  818.                     if (p >= regxend)
  819.                     FAIL("trailing \\ in regexp");
  820.                     /* FALL THROUGH */
  821.                 default:
  822.                     ender = *p++;
  823.                     break;
  824.                 }
  825.                 break;
  826.                 default:
  827.                 ender = *p++;
  828.                 break;
  829.                 }
  830.                 if (regfold && isupper(ender))
  831.                     ender = tolower(ender);
  832.                 if (ISMULT2(p)) { /* Back off on ?+*. */
  833.                 if (len)
  834.                     p = oldp;
  835.                 else {
  836.                     len++;
  837.                     regc(ender);
  838.                 }
  839.                 break;
  840.                 }
  841.                 regc(ender);
  842.             }
  843.             loopdone:
  844.             regparse = p;
  845.             if (len <= 0)
  846.                 FAIL("internal disaster in regexp");
  847.             *flagp |= HASWIDTH;
  848.             if (len == 1)
  849.                 *flagp |= SIMPLE;
  850.             if (regcode != ®dummy)
  851.                 *OPERAND(ret) = len;
  852.             regc('\0');
  853.         }
  854.         break;
  855.     }
  856.  
  857.     return(ret);
  858. }
  859.  
  860. static void
  861. regset(bits,def,c)
  862. char *bits;
  863. int def;
  864. register int c;
  865. {
  866.     if (regcode == ®dummy)
  867.         return;
  868.     c &= 255;
  869.     if (def)
  870.         bits[c >> 3] &= ~(1 << (c & 7));
  871.     else
  872.         bits[c >> 3] |=  (1 << (c & 7));
  873. }
  874.  
  875. static char *
  876. regclass()
  877. {
  878.     register char *bits;
  879.     register int class;
  880.     register int lastclass;
  881.     register int range = 0;
  882.     register char *ret;
  883.     register int def;
  884.  
  885.     ret = regnode(ANYOF);
  886.     if (*regparse == '^') {    /* Complement of range. */
  887.         regparse++;
  888.         def = 0;
  889.     } else {
  890.         def = 255;
  891.     }
  892.     bits = regcode;
  893.     for (class = 0; class < 32; class++)
  894.         regc(def);
  895.     if (*regparse == ']' || *regparse == '-')
  896.         goto skipcond;        /* allow 1st char to be ] or - */
  897.     while (regparse < regxend && *regparse != ']') {
  898.           skipcond:
  899.         class = UCHARAT(regparse++);
  900.         if (class == '\\') {
  901.             class = UCHARAT(regparse++);
  902.             switch (class) {
  903.             case 'w':
  904.                 for (class = 'a'; class <= 'z'; class++)
  905.                     regset(bits,def,class);
  906.                 for (class = 'A'; class <= 'Z'; class++)
  907.                     regset(bits,def,class);
  908.                 for (class = '0'; class <= '9'; class++)
  909.                     regset(bits,def,class);
  910.                 regset(bits,def,'_');
  911.                 lastclass = 1234;
  912.                 continue;
  913.             case 's':
  914.                 regset(bits,def,' ');
  915.                 regset(bits,def,'\t');
  916.                 regset(bits,def,'\r');
  917.                 regset(bits,def,'\f');
  918.                 regset(bits,def,'\n');
  919.                 lastclass = 1234;
  920.                 continue;
  921.             case 'd':
  922.                 for (class = '0'; class <= '9'; class++)
  923.                     regset(bits,def,class);
  924.                 lastclass = 1234;
  925.                 continue;
  926.             case 'n':
  927.                 class = '\n';
  928.                 break;
  929.             case 'r':
  930.                 class = '\r';
  931.                 break;
  932.             case 't':
  933.                 class = '\t';
  934.                 break;
  935.             case 'f':
  936.                 class = '\f';
  937.                 break;
  938.             case 'b':
  939.                 class = '\b';
  940.                 break;
  941.             case '0': case '1': case '2': case '3': case '4':
  942.             case '5': case '6': case '7': case '8': case '9':
  943.                 class -= '0';
  944.                 if (isdigit(*regparse)) {
  945.                     class <<= 3;
  946.                     class += *regparse++ - '0';
  947.                 }
  948.                 if (isdigit(*regparse)) {
  949.                     class <<= 3;
  950.                     class += *regparse++ - '0';
  951.                 }
  952.                 break;
  953.             }
  954.         }
  955.         if (range) {
  956.             if (lastclass > class)
  957.                 FAIL("invalid [] range in regexp");
  958.             range = 0;
  959.         }
  960.         else {
  961.             lastclass = class;
  962.             if (*regparse == '-' && regparse+1 < regxend &&
  963.                 regparse[1] != ']') {
  964.                 regparse++;
  965.                 range = 1;
  966.                 continue;    /* do it next time */
  967.             }
  968.         }
  969.         for ( ; lastclass <= class; lastclass++) {
  970.             regset(bits,def,lastclass);
  971.             if (regfold && isupper(lastclass))
  972.                 regset(bits,def,tolower(lastclass));
  973.         }
  974.         lastclass = class;
  975.     }
  976.     if (*regparse != ']')
  977.         FAIL("unmatched [] in regexp");
  978.     regparse++;
  979.     return ret;
  980. }
  981.  
  982. /*
  983.  - regnode - emit a node
  984.  */
  985. static char *            /* Location. */
  986. regnode(op)
  987. int op;
  988. {
  989.     register char *ret;
  990.     register char *ptr;
  991.  
  992.     ret = regcode;
  993.     if (ret == ®dummy) {
  994. #ifdef REGALIGN
  995.         if (!(regsize & 1))
  996.             regsize++;
  997. #endif
  998.         regsize += 3;
  999.         return(ret);
  1000.     }
  1001.  
  1002. #ifdef REGALIGN
  1003. #ifndef lint
  1004.     if (!((long)ret & 1))
  1005.         *ret++ = 127;
  1006. #endif
  1007. #endif
  1008.     ptr = ret;
  1009.     *ptr++ = op;
  1010.     *ptr++ = '\0';        /* Null "next" pointer. */
  1011.     *ptr++ = '\0';
  1012.     regcode = ptr;
  1013.  
  1014.     return(ret);
  1015. }
  1016.  
  1017. /*
  1018.  - regc - emit (if appropriate) a byte of code
  1019.  */
  1020. static void
  1021. regc(b)
  1022. int b;
  1023. {
  1024.     if (regcode != ®dummy)
  1025.         *regcode++ = b;
  1026.     else
  1027.         regsize++;
  1028. }
  1029.  
  1030. /*
  1031.  - reginsert - insert an operator in front of already-emitted operand
  1032.  *
  1033.  * Means relocating the operand.
  1034.  */
  1035. static void
  1036. reginsert(op, opnd)
  1037. int op;
  1038. char *opnd;
  1039. {
  1040.     register char *src;
  1041.     register char *dst;
  1042.     register char *place;
  1043.     register offset = (op == CURLY ? 4 : 0);
  1044.  
  1045.     if (regcode == ®dummy) {
  1046. #ifdef REGALIGN
  1047.         regsize += 4L + offset;
  1048. #else
  1049.         regsize += 3L + offset;
  1050. #endif
  1051.         return;
  1052.     }
  1053.  
  1054.     src = regcode;
  1055. #ifdef REGALIGN
  1056.     regcode += 4 + offset;
  1057. #else
  1058.     regcode += 3 + offset;
  1059. #endif
  1060.     dst = regcode;
  1061.     while (src > opnd)
  1062.         *--dst = *--src;
  1063.  
  1064.     place = opnd;        /* Op node, where operand used to be. */
  1065.     *place++ = op;
  1066.     *place++ = '\0';
  1067.     *place++ = '\0';
  1068.     while (offset-- > 0)
  1069.         *place++ = '\0';
  1070. }
  1071.  
  1072. /*
  1073.  - regtail - set the next-pointer at the end of a node chain
  1074.  */
  1075. static void
  1076. regtail(p, val)
  1077. char *p;
  1078. char *val;
  1079. {
  1080.     register char *scan;
  1081.     register char *temp;
  1082.     register int offset;
  1083.  
  1084.     if (p == ®dummy)
  1085.         return;
  1086.  
  1087.     /* Find last node. */
  1088.     scan = p;
  1089.     for (;;) {
  1090.         temp = regnext(scan);
  1091.         if (temp == NULL)
  1092.             break;
  1093.         scan = temp;
  1094.     }
  1095.  
  1096. #ifdef REGALIGN
  1097.     offset = val - scan;
  1098. #ifndef lint
  1099.     *(short*)(scan+1) = offset;
  1100. #else
  1101.     offset = offset;
  1102. #endif
  1103. #else
  1104.     if (OP(scan) == BACK)
  1105.         offset = scan - val;
  1106.     else
  1107.         offset = val - scan;
  1108.     *(scan+1) = (offset>>8)&0377;
  1109.     *(scan+2) = offset&0377;
  1110. #endif
  1111. }
  1112.  
  1113. /*
  1114.  - regoptail - regtail on operand of first argument; nop if operandless
  1115.  */
  1116. static void
  1117. regoptail(p, val)
  1118. char *p;
  1119. char *val;
  1120. {
  1121.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  1122.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  1123.         return;
  1124.     regtail(NEXTOPER(p), val);
  1125. }
  1126.  
  1127. /*
  1128.  - regcurly - a little FSA that accepts {\d+,?\d*}
  1129.  */
  1130. STATIC int
  1131. regcurly(s)
  1132. register char *s;
  1133. {
  1134.     if (*s++ != '{')
  1135.     return FALSE;
  1136.     if (!isdigit(*s))
  1137.     return FALSE;
  1138.     while (isdigit(*s))
  1139.     s++;
  1140.     if (*s == ',')
  1141.     s++;
  1142.     while (isdigit(*s))
  1143.     s++;
  1144.     if (*s != '}')
  1145.     return FALSE;
  1146.     return TRUE;
  1147. }
  1148.  
  1149. #ifdef DEBUGGING
  1150.  
  1151. /*
  1152.  - regdump - dump a regexp onto stderr in vaguely comprehensible form
  1153.  */
  1154. void
  1155. regdump(r)
  1156. regexp *r;
  1157. {
  1158.     register char *s;
  1159.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1160.     register char *next;
  1161.  
  1162.  
  1163.     s = r->program + 1;
  1164.     while (op != END) {    /* While that wasn't END last time... */
  1165. #ifdef REGALIGN
  1166.         if (!((long)s & 1))
  1167.             s++;
  1168. #endif
  1169.         op = OP(s);
  1170.         fprintf(stderr,"%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1171.         if (op == CURLY)
  1172.             s += 4;
  1173.         next = regnext(s);
  1174.         if (next == NULL)        /* Next ptr. */
  1175.             fprintf(stderr,"(0)");
  1176.         else 
  1177.             fprintf(stderr,"(%d)", (s-r->program)+(next-s));
  1178.         s += 3;
  1179.         if (op == ANYOF) {
  1180.             s += 32;
  1181.         }
  1182.         if (op == EXACTLY) {
  1183.             /* Literal string, where present. */
  1184.             s++;
  1185.             while (*s != '\0') {
  1186.                 (void)putchar(*s);
  1187.                 s++;
  1188.             }
  1189.             s++;
  1190.         }
  1191.         (void)putchar('\n');
  1192.     }
  1193.  
  1194.     /* Header fields of interest. */
  1195.     if (r->regstart)
  1196.         fprintf(stderr,"start `%s' ", r->regstart->str_ptr);
  1197.     if (r->regstclass)
  1198.         fprintf(stderr,"stclass `%s' ", regprop(r->regstclass));
  1199.     if (r->reganch & 1)
  1200.         fprintf(stderr,"anchored ");
  1201.     if (r->reganch & 2)
  1202.         fprintf(stderr,"plus ");
  1203.     if (r->regmust != NULL)
  1204.         fprintf(stderr,"must have \"%s\" back %d ", r->regmust->str_ptr,
  1205.           r->regback);
  1206.     fprintf(stderr,"\n");
  1207. }
  1208.  
  1209. /*
  1210.  - regprop - printable representation of opcode
  1211.  */
  1212. char *
  1213. regprop(op)
  1214. char *op;
  1215. {
  1216.     register char *p;
  1217.  
  1218.     (void) strcpy(buf, ":");
  1219.  
  1220.     switch (OP(op)) {
  1221.     case BOL:
  1222.         p = "BOL";
  1223.         break;
  1224.     case EOL:
  1225.         p = "EOL";
  1226.         break;
  1227.     case ANY:
  1228.         p = "ANY";
  1229.         break;
  1230.     case ANYOF:
  1231.         p = "ANYOF";
  1232.         break;
  1233.     case BRANCH:
  1234.         p = "BRANCH";
  1235.         break;
  1236.     case EXACTLY:
  1237.         p = "EXACTLY";
  1238.         break;
  1239.     case NOTHING:
  1240.         p = "NOTHING";
  1241.         break;
  1242.     case BACK:
  1243.         p = "BACK";
  1244.         break;
  1245.     case END:
  1246.         p = "END";
  1247.         break;
  1248.     case ALNUM:
  1249.         p = "ALNUM";
  1250.         break;
  1251.     case NALNUM:
  1252.         p = "NALNUM";
  1253.         break;
  1254.     case BOUND:
  1255.         p = "BOUND";
  1256.         break;
  1257.     case NBOUND:
  1258.         p = "NBOUND";
  1259.         break;
  1260.     case SPACE:
  1261.         p = "SPACE";
  1262.         break;
  1263.     case NSPACE:
  1264.         p = "NSPACE";
  1265.         break;
  1266.     case DIGIT:
  1267.         p = "DIGIT";
  1268.         break;
  1269.     case NDIGIT:
  1270.         p = "NDIGIT";
  1271.         break;
  1272.     case CURLY:
  1273.         (void)sprintf(buf+strlen(buf), "CURLY {%d,%d}",
  1274.             ARG1(op),ARG2(op));
  1275.         p = NULL;
  1276.         break;
  1277.     case REF:
  1278.     case REF+1:
  1279.     case REF+2:
  1280.     case REF+3:
  1281.     case REF+4:
  1282.     case REF+5:
  1283.     case REF+6:
  1284.     case REF+7:
  1285.     case REF+8:
  1286.     case REF+9:
  1287.         (void)sprintf(buf+strlen(buf), "REF%d", OP(op)-REF);
  1288.         p = NULL;
  1289.         break;
  1290.     case OPEN+1:
  1291.     case OPEN+2:
  1292.     case OPEN+3:
  1293.     case OPEN+4:
  1294.     case OPEN+5:
  1295.     case OPEN+6:
  1296.     case OPEN+7:
  1297.     case OPEN+8:
  1298.     case OPEN+9:
  1299.         (void)sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1300.         p = NULL;
  1301.         break;
  1302.     case CLOSE+1:
  1303.     case CLOSE+2:
  1304.     case CLOSE+3:
  1305.     case CLOSE+4:
  1306.     case CLOSE+5:
  1307.     case CLOSE+6:
  1308.     case CLOSE+7:
  1309.     case CLOSE+8:
  1310.     case CLOSE+9:
  1311.         (void)sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1312.         p = NULL;
  1313.         break;
  1314.     case STAR:
  1315.         p = "STAR";
  1316.         break;
  1317.     case PLUS:
  1318.         p = "PLUS";
  1319.         break;
  1320.     default:
  1321.         FAIL("corrupted regexp opcode");
  1322.     }
  1323.     if (p != NULL)
  1324.         (void) strcat(buf, p);
  1325.     return(buf);
  1326. }
  1327. #endif /* DEBUGGING */
  1328.  
  1329. void
  1330. regfree(r)
  1331. struct regexp *r;
  1332. {
  1333.     if (r->precomp)
  1334.         Safefree(r->precomp);
  1335.     if (r->subbase)
  1336.         Safefree(r->subbase);
  1337.     if (r->regmust)
  1338.         str_free(r->regmust);
  1339.     if (r->regstart)
  1340.         str_free(r->regstart);
  1341.     Safefree(r);
  1342. }
  1343.