BSD 3 release

[unix-history] / usr / src / cmd / sdb / re.c

#include "head.h"
#define CBRA    1
#define CCHR    2
#define CDOT    4
#define CCL     6
#define NCCL    8
#define CDOL    10
#define CEOF    11
#define CKET    12
#define CBACK   18

#define CSTAR   01

#define LBSIZE  BUFSIZ
#define ESIZE   256
#define NBRA    9

char    expbuf[ESIZE];
int     circf;
char    *braslist[NBRA];
char    *braelist[NBRA];
char    bittab[] = {
       1,
       2,
       4,
       8,
       16,
       32,
       64,
       128
};

dore() {
       register int line;
       register char *p;
       
       circf = 0;
       line = fline;
       compile(re);
       do {
               if (redir) fnext();
               else fprev();
               p = fbuf;
               while(*p++ != '\n')
                       ;
               *--p = '\0';
               if (match(fbuf)) goto l1;
       } while (fline != line);
       error("No match");
l1:     *p = '\n';
       fprint();
}


compile(astr)
char *astr;
{
       register c;
       register char *ep, *sp;
       char *cstart;
       char *lastep;
       int cclcnt;
       char bracket[NBRA], *bracketp;
       int closed;
       char numbra;
       char neg;

       ep = expbuf;
       sp = astr;
       lastep = 0;
       bracketp = bracket;
       closed = numbra = 0;
       if (*sp == '^') {
               circf++;
               sp++;
       }
       for (;;) {
               if (ep >= &expbuf[ESIZE])
                       goto cerror;
               if ((c = *sp++) != '*')
                       lastep = ep;
               switch (c) {

               case '\0':
                       *ep++ = CEOF;
                       return;

               case '.':
                       *ep++ = CDOT;
                       continue;

               case '*':
                       if (lastep==0 || *lastep==CBRA || *lastep==CKET)
                               goto defchar;
                       *lastep |= CSTAR;
                       continue;

               case '$':
                       if (*sp != '\0')
                               goto defchar;
                       *ep++ = CDOL;
                       continue;

               case '[':
                       if(&ep[17] >= &expbuf[ESIZE])
                               goto cerror;
                       *ep++ = CCL;
                       neg = 0;
                       if((c = *sp++) == '^') {
                               neg = 1;
                               c = *sp++;
                       }
                       cstart = sp;
                       do {
                               if (c=='\0')
                                       goto cerror;
                               if (c=='-' && sp>cstart && *sp!=']') {
                                       for (c = sp[-2]; c<*sp; c++)
                                               ep[c>>3] |= bittab[c&07];
                                       sp++;
                               }
                               ep[c>>3] |= bittab[c&07];
                       } while((c = *sp++) != ']');
                       if(neg) {
                               for(cclcnt = 0; cclcnt < 16; cclcnt++)
                                       ep[cclcnt] ^= -1;
                               ep[0] &= 0376;
                       }

                       ep += 16;

                       continue;

               case '\\':
                       if((c = *sp++) == '(') {
                               if(numbra >= NBRA) {
                                       goto cerror;
                               }
                               *bracketp++ = numbra;
                               *ep++ = CBRA;
                               *ep++ = numbra++;
                               continue;
                       }
                       if(c == ')') {
                               if(bracketp <= bracket) {
                                       goto cerror;
                               }
                               *ep++ = CKET;
                               *ep++ = *--bracketp;
                               closed++;
                               continue;
                       }

                       if(c >= '1' && c <= '9') {
                               if((c -= '1') >= closed)
                                       goto cerror;
                               *ep++ = CBACK;
                               *ep++ = c;
                               continue;
                       }

               defchar:
               default:
                       *ep++ = CCHR;
                       *ep++ = c;
               }
       }
   cerror:
       errexit("RE error\n", (char *)NULL);
}

match(p1)
register char *p1; {
       register char *p2;
       register c;
               p2 = expbuf;
               if (circf) {
                       if (advance(p1, p2))
                               goto found;
                       goto nfound;
               }
               /* fast check for first character */
               if (*p2==CCHR) {
                       c = p2[1];
                       do {
                               if (*p1!=c)
                                       continue;
                               if (advance(p1, p2))
                                       goto found;
                       } while (*p1++);
                       goto nfound;
               }
               /* regular algorithm */
               do {
                       if (advance(p1, p2))
                               goto found;
               } while (*p1++);
       nfound:
               return(0);
       found:
               return(1);
}

advance(lp, ep)
register char *lp, *ep;
{
       register char *curlp;
       char c;
       char *bbeg;
       int ct;

       for (;;) switch (*ep++) {

       case CCHR:
               if (*ep++ == *lp++)
                       continue;
               return(0);

       case CDOT:
               if (*lp++)
                       continue;
               return(0);

       case CDOL:
               if (*lp=='\0')
                       continue;
               return(0);

       case CEOF:
               return(1);

       case CCL:
               c = *lp++ & 0177;
               if(ep[c>>3] & bittab[c & 07]) {
                       ep += 16;
                       continue;
               }
               return(0);
       case CBRA:
               braslist[*ep++] = lp;
               continue;

       case CKET:
               braelist[*ep++] = lp;
               continue;

       case CBACK:
               bbeg = braslist[*ep];
               if (braelist[*ep]==0)
                       return(0);
               ct = braelist[*ep++] - bbeg;
               if(ecmp(bbeg, lp, ct)) {
                       lp += ct;
                       continue;
               }
               return(0);

       case CBACK|CSTAR:
               bbeg = braslist[*ep];
               if (braelist[*ep]==0)
                       return(0);
               ct = braelist[*ep++] - bbeg;
               curlp = lp;
               while(ecmp(bbeg, lp, ct))
                       lp += ct;
               while(lp >= curlp) {
                       if(advance(lp, ep))     return(1);
                       lp -= ct;
               }
               return(0);


       case CDOT|CSTAR:
               curlp = lp;
               while (*lp++);
               goto star;

       case CCHR|CSTAR:
               curlp = lp;
               while (*lp++ == *ep);
               ep++;
               goto star;

       case CCL|CSTAR:
               curlp = lp;
               do {
                       c = *lp++ & 0177;
               } while(ep[c>>3] & bittab[c & 07]);
               ep += 16;
               goto star;

       star:
               if(--lp == curlp) {
                       continue;
               }

               if(*ep == CCHR) {
                       c = ep[1];
                       do {
                               if(*lp != c)
                                       continue;
                               if(advance(lp, ep))
                                       return(1);
                       } while(lp-- > curlp);
                       return(0);
               }

               do {
                       if (advance(lp, ep))
                               return(1);
               } while (lp-- > curlp);
               return(0);

       default:
               errexit("RE botch\n", (char *)NULL);
       }
}
ecmp(a, b, count)
char    *a, *b;
{
       register cc = count;
       while(cc--)
               if(*a++ != *b++)        return(0);
       return(1);
}


errexit(s)
char *s; {
       error(s);
       return;
}