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