#include <u.h>
#include <libc.h>
#include <draw.h>
#include <thread.h>
#include <cursor.h>
#include <mouse.h>
#include <keyboard.h>
#include <frame.h>
#include <fcall.h>
#include <plumb.h>
#include "dat.h"
#include "fns.h"

Rangeset        sel;
Rune            *lastregexp;

/*
* Machine Information
*/
typedef struct Inst Inst;
struct Inst
{
       uint    type;   /* <= Runemax+1 ==> literal, otherwise action */
       union {
               int sid;
               int subid;
               int class;
               Inst *other;
               Inst *right;
       };
       union{
               Inst *left;
               Inst *next;
       };
};

#define NPROG   1024
Inst    program[NPROG];
Inst    *progp;
Inst    *startinst;     /* First inst. of program; might not be program[0] */
Inst    *bstartinst;    /* same for backwards machine */
Channel *rechan;        /* chan(Inst*) */

typedef struct Ilist Ilist;
struct Ilist
{
       Inst    *inst;          /* Instruction of the thread */
       Rangeset se;
       uint    startp;         /* first char of match */
};

#define NLIST   127

Ilist   *tl, *nl;       /* This list, next list */
Ilist   list[2][NLIST+1];       /* +1 for trailing null */
static  Rangeset sempty;

/*
* Actions and Tokens
*
*      0x100xx are operators, value == precedence
*      0x200xx are tokens, i.e. operands for operators
*/
enum {
       OPERATOR = Runemask+1,  /* Bitmask of all operators */
       START   = OPERATOR,     /* Start, used for marker on stack */
       RBRA,                   /* Right bracket, ) */
       LBRA,                   /* Left bracket, ( */
       OR,                     /* Alternation, | */
       CAT,                    /* Concatentation, implicit operator */
       STAR,                   /* Closure, * */
       PLUS,                   /* a+ == aa* */
       QUEST,                  /* a? == a|nothing, i.e. 0 or 1 a's */

       ANY     = OPERATOR<<1,  /* Any character but newline, . */
       NOP,                    /* No operation, internal use only */
       BOL,                    /* Beginning of line, ^ */
       EOL,                    /* End of line, $ */
       CCLASS,                 /* Character class, [] */
       NCCLASS,                /* Negated character class, [^] */
       END,                    /* Terminate: match found */

       ISATOR  = OPERATOR,
       ISAND   = OPERATOR<<1,
};

/*
* Parser Information
*/
typedef struct Node Node;
struct Node
{
       Inst    *first;
       Inst    *last;
};

#define NSTACK  20
Node    andstack[NSTACK];
Node    *andp;
int     atorstack[NSTACK];
int     *atorp;
int     lastwasand;     /* Last token was operand */
int     cursubid;
int     subidstack[NSTACK];
int     *subidp;
int     backwards;
int     nbra;
Rune    *exprp;         /* pointer to next character in source expression */
#define DCLASS  10      /* allocation increment */
int     nclass;         /* number active */
int     Nclass;         /* high water mark */
Rune    **class;
int     negateclass;

int     addinst(Ilist *l, Inst *inst, Rangeset *sep);
void    newmatch(Rangeset*);
void    bnewmatch(Rangeset*);
void    pushand(Inst*, Inst*);
void    pushator(int);
Node    *popand(int);
int     popator(void);
void    startlex(Rune*);
int     lex(void);
void    operator(int);
void    operand(int);
void    evaluntil(int);
void    optimize(Inst*);
void    bldcclass(void);

void
rxinit(void)
{
       rechan = chancreate(sizeof(Inst*), 0);
       lastregexp = runemalloc(1);
}

void
regerror(char *e)
{
       lastregexp[0] = 0;
       warning(nil, "regexp: %s\n", e);
       sendp(rechan, nil);
       threadexits(nil);
}

Inst *
newinst(int t)
{
       if(progp >= &program[NPROG])
               regerror("expression too long");
       progp->type = t;
       progp->left = nil;
       progp->right = nil;
       return progp++;
}

void
realcompile(void *arg)
{
       int token;
       Rune *s;

       threadsetname("regcomp");
       s = arg;
       startlex(s);
       atorp = atorstack;
       andp = andstack;
       subidp = subidstack;
       cursubid = 0;
       lastwasand = FALSE;
       /* Start with a low priority operator to prime parser */
       pushator(START-1);
       while((token=lex()) != END){
               if((token&ISATOR) == OPERATOR)
                       operator(token);
               else
                       operand(token);
       }
       /* Close with a low priority operator */
       evaluntil(START);
       /* Force END */
       operand(END);
       evaluntil(START);
       if(nbra)
               regerror("unmatched `('");
       --andp; /* points to first and only operand */
       sendp(rechan, andp->first);
       threadexits(nil);
}

/* r is null terminated */
int
rxcompile(Rune *r)
{
       int i, nr;
       Inst *oprogp;

       nr = runestrlen(r)+1;
       if(runeeq(lastregexp, runestrlen(lastregexp)+1, r, nr)==TRUE)
               return TRUE;
       lastregexp[0] = 0;
       for(i=0; i<nclass; i++)
               free(class[i]);
       nclass = 0;
       progp = program;
       backwards = FALSE;
       bstartinst = nil;
       threadcreate(realcompile, r, STACK);
       startinst = recvp(rechan);
       if(startinst == nil)
               return FALSE;
       optimize(program);
       oprogp = progp;
       backwards = TRUE;
       threadcreate(realcompile, r, STACK);
       bstartinst = recvp(rechan);
       if(bstartinst == nil)
               return FALSE;
       optimize(oprogp);
       lastregexp = runerealloc(lastregexp, nr);
       runemove(lastregexp, r, nr);
       return TRUE;
}

void
operand(int t)
{
       Inst *i;
       if(lastwasand)
               operator(CAT);  /* catenate is implicit */
       i = newinst(t);
       if(t == CCLASS){
               if(negateclass)
                       i->type = NCCLASS;      /* UGH */
               i->class = nclass-1;            /* UGH */
       }
       pushand(i, i);
       lastwasand = TRUE;
}

void
operator(int t)
{
       if(t==RBRA && --nbra<0)
               regerror("unmatched `)'");
       if(t==LBRA){
               cursubid++;     /* silently ignored */
               nbra++;
               if(lastwasand)
                       operator(CAT);
       }else
               evaluntil(t);
       if(t!=RBRA)
               pushator(t);
       lastwasand = FALSE;
       if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
               lastwasand = TRUE;      /* these look like operands */
}

void
pushand(Inst *f, Inst *l)
{
       if(andp >= &andstack[NSTACK])
               error("operand stack overflow");
       andp->first = f;
       andp->last = l;
       andp++;
}

void
pushator(int t)
{
       if(atorp >= &atorstack[NSTACK])
               error("operator stack overflow");
       *atorp++=t;
       if(cursubid >= NRange)
               *subidp++= -1;
       else
               *subidp++=cursubid;
}

Node *
popand(int op)
{
       char buf[64];

       if(andp <= &andstack[0])
               if(op){
                       sprint(buf, "missing operand for %c", op);
                       regerror(buf);
               }else
                       regerror("malformed regexp");
       return --andp;
}

int
popator()
{
       if(atorp <= &atorstack[0])
               error("operator stack underflow");
       --subidp;
       return *--atorp;
}

void
evaluntil(int pri)
{
       Node *op1, *op2, *t;
       Inst *inst1, *inst2;

       while(pri==RBRA || atorp[-1]>=pri){
               switch(popator()){
               case LBRA:
                       op1 = popand('(');
                       inst2 = newinst(RBRA);
                       inst2->subid = *subidp;
                       op1->last->next = inst2;
                       inst1 = newinst(LBRA);
                       inst1->subid = *subidp;
                       inst1->next = op1->first;
                       pushand(inst1, inst2);
                       return;         /* must have been RBRA */
               default:
                       error("unknown regexp operator");
                       break;
               case OR:
                       op2 = popand('|');
                       op1 = popand('|');
                       inst2 = newinst(NOP);
                       op2->last->next = inst2;
                       op1->last->next = inst2;
                       inst1 = newinst(OR);
                       inst1->right = op1->first;
                       inst1->left = op2->first;
                       pushand(inst1, inst2);
                       break;
               case CAT:
                       op2 = popand(0);
                       op1 = popand(0);
                       if(backwards && op2->first->type!=END){
                               t = op1;
                               op1 = op2;
                               op2 = t;
                       }
                       op1->last->next = op2->first;
                       pushand(op1->first, op2->last);
                       break;
               case STAR:
                       op2 = popand('*');
                       inst1 = newinst(OR);
                       op2->last->next = inst1;
                       inst1->right = op2->first;
                       pushand(inst1, inst1);
                       break;
               case PLUS:
                       op2 = popand('+');
                       inst1 = newinst(OR);
                       op2->last->next = inst1;
                       inst1->right = op2->first;
                       pushand(op2->first, inst1);
                       break;
               case QUEST:
                       op2 = popand('?');
                       inst1 = newinst(OR);
                       inst2 = newinst(NOP);
                       inst1->left = inst2;
                       inst1->right = op2->first;
                       op2->last->next = inst2;
                       pushand(inst1, inst2);
                       break;
               }
       }
}


void
optimize(Inst *start)
{
       Inst *inst, *target;

       for(inst=start; inst->type!=END; inst++){
               target = inst->next;
               while(target->type == NOP)
                       target = target->next;
               inst->next = target;
       }
}

void
startlex(Rune *s)
{
       exprp = s;
       nbra = 0;
}


int
lex(void){
       int c;

       c = *exprp++;
       switch(c){
       case '\\':
               if(*exprp)
                       if((c= *exprp++)=='n')
                               c='\n';
               break;
       case 0:
               c = END;
               --exprp;        /* In case we come here again */
               break;
       case '*':
               c = STAR;
               break;
       case '?':
               c = QUEST;
               break;
       case '+':
               c = PLUS;
               break;
       case '|':
               c = OR;
               break;
       case '.':
               c = ANY;
               break;
       case '(':
               c = LBRA;
               break;
       case ')':
               c = RBRA;
               break;
       case '^':
               c = BOL;
               break;
       case '$':
               c = EOL;
               break;
       case '[':
               c = CCLASS;
               bldcclass();
               break;
       }
       return c;
}

int
nextrec(void)
{
       if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
               regerror("malformed `[]'");
       if(exprp[0] == '\\'){
               exprp++;
               if(*exprp=='n'){
                       exprp++;
                       return '\n';
               }
               return *exprp++|(Runemask+1);
       }
       return *exprp++;
}

void
bldcclass(void)
{
       int c1, c2, n, na;
       Rune *classp;

       classp = runemalloc(DCLASS);
       n = 0;
       na = DCLASS;
       /* we have already seen the '[' */
       if(*exprp == '^'){
               classp[n++] = '\n';     /* don't match newline in negate case */
               negateclass = TRUE;
               exprp++;
       }else
               negateclass = FALSE;
       while((c1 = nextrec()) != ']'){
               if(c1 == '-'){
   Error:
                       free(classp);
                       regerror("malformed `[]'");
               }
               if(n+4 >= na){          /* 3 runes plus NUL */
                       na += DCLASS;
                       classp = runerealloc(classp, na);
               }
               if(*exprp == '-'){
                       exprp++;        /* eat '-' */
                       if((c2 = nextrec()) == ']')
                               goto Error;
                       classp[n+0] = Runemax;
                       classp[n+1] = c1 & Runemask;
                       classp[n+2] = c2 & Runemask;
                       n += 3;
               }else
                       classp[n++] = c1 & Runemask;
       }
       classp[n] = 0;
       if(nclass == Nclass){
               Nclass += DCLASS;
               class = realloc(class, Nclass*sizeof(Rune*));
       }
       class[nclass++] = classp;
}

int
classmatch(int classno, int c, int negate)
{
       Rune *p;

       p = class[classno];
       while(*p){
               if(*p == Runemax){
                       if(p[1]<=c && c<=p[2])
                               return !negate;
                       p += 3;
               }else if(*p++ == c)
                       return !negate;
       }
       return negate;
}

/*
* Note optimization in addinst:
*      *l must be pending when addinst called; if *l has been looked
*              at already, the optimization is a bug.
*/
int
addinst(Ilist *l, Inst *inst, Rangeset *sep)
{
       Ilist *p;

       for(p = l; p->inst; p++){
               if(p->inst==inst){
                       if((sep)->r[0].q0 < p->se.r[0].q0)
                               p->se= *sep;    /* this would be bug */
                       return 0;       /* It's already there */
               }
       }
       p->inst = inst;
       p->se= *sep;
       (p+1)->inst = nil;
       return 1;
}

int
rxnull(void)
{
       return startinst==nil || bstartinst==nil;
}

/* either t!=nil or r!=nil, and we match the string in the appropriate place */
int
rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
{
       int flag;
       Inst *inst;
       Ilist *tlp;
       uint p;
       int nnl, ntl;
       int nc, c;
       int wrapped;
       int startchar;

       flag = 0;
       p = startp;
       startchar = 0;
       wrapped = 0;
       nnl = 0;
       if(startinst->type<OPERATOR)
               startchar = startinst->type;
       list[0][0].inst = list[1][0].inst = nil;
       sel.r[0].q0 = -1;
       if(t != nil)
               nc = t->file->nc;
       else
               nc = runestrlen(r);
       /* Execute machine once for each character */
       for(;;p++){
       doloop:
               if(p>=eof || p>=nc){
                       switch(wrapped++){
                       case 0:         /* let loop run one more click */
                       case 2:
                               break;
                       case 1:         /* expired; wrap to beginning */
                               if(sel.r[0].q0>=0 || eof!=Infinity)
                                       goto Return;
                               list[0][0].inst = list[1][0].inst = nil;
                               p = 0;
                               goto doloop;
                       default:
                               goto Return;
                       }
                       c = 0;
               }else{
                       if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
                               break;
                       if(t != nil)
                               c = textreadc(t, p);
                       else
                               c = r[p];
               }
               /* fast check for first char */
               if(startchar && nnl==0 && c!=startchar)
                       continue;
               tl = list[flag];
               nl = list[flag^=1];
               nl->inst = nil;
               ntl = nnl;
               nnl = 0;
               if(sel.r[0].q0<0 && (!wrapped || p<startp || startp==eof)){
                       /* Add first instruction to this list */
                       sempty.r[0].q0 = p;
                       if(addinst(tl, startinst, &sempty))
                       if(++ntl >= NLIST){
       Overflow:
                               warning(nil, "regexp list overflow\n");
                               sel.r[0].q0 = -1;
                               goto Return;
                       }
               }
               /* Execute machine until this list is empty */
               for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
       Switchstmt:
                       switch(inst->type){
                       default:        /* regular character */
                               if(inst->type==c){
       Addinst:
                                       if(addinst(nl, inst->next, &tlp->se))
                                       if(++nnl >= NLIST)
                                               goto Overflow;
                               }
                               break;
                       case LBRA:
                               if(inst->subid>=0)
                                       tlp->se.r[inst->subid].q0 = p;
                               inst = inst->next;
                               goto Switchstmt;
                       case RBRA:
                               if(inst->subid>=0)
                                       tlp->se.r[inst->subid].q1 = p;
                               inst = inst->next;
                               goto Switchstmt;
                       case ANY:
                               if(c!='\n')
                                       goto Addinst;
                               break;
                       case BOL:
                               if(p==0 || (t!=nil && textreadc(t, p-1)=='\n') || (r!=nil && r[p-1]=='\n')){
       Step:
                                       inst = inst->next;
                                       goto Switchstmt;
                               }
                               break;
                       case EOL:
                               if(c == '\n')
                                       goto Step;
                               break;
                       case CCLASS:
                               if(c>=0 && classmatch(inst->class, c, 0))
                                       goto Addinst;
                               break;
                       case NCCLASS:
                               if(c>=0 && classmatch(inst->class, c, 1))
                                       goto Addinst;
                               break;
                       case OR:
                               /* evaluate right choice later */
                               if(addinst(tlp, inst->right, &tlp->se))
                               if(++ntl >= NLIST)
                                       goto Overflow;
                               /* efficiency: advance and re-evaluate */
                               inst = inst->left;
                               goto Switchstmt;
                       case END:       /* Match! */
                               tlp->se.r[0].q1 = p;
                               newmatch(&tlp->se);
                               break;
                       }
               }
       }
   Return:
       *rp = sel;
       return sel.r[0].q0 >= 0;
}

void
newmatch(Rangeset *sp)
{
       if(sel.r[0].q0<0 || sp->r[0].q0<sel.r[0].q0 ||
          (sp->r[0].q0==sel.r[0].q0 && sp->r[0].q1>sel.r[0].q1))
               sel = *sp;
}

int
rxbexecute(Text *t, uint startp, Rangeset *rp)
{
       int flag;
       Inst *inst;
       Ilist *tlp;
       int p;
       int nnl, ntl;
       int c;
       int wrapped;
       int startchar;

       flag = 0;
       nnl = 0;
       wrapped = 0;
       p = startp;
       startchar = 0;
       if(bstartinst->type<OPERATOR)
               startchar = bstartinst->type;
       list[0][0].inst = list[1][0].inst = nil;
       sel.r[0].q0= -1;
       /* Execute machine once for each character, including terminal NUL */
       for(;;--p){
       doloop:
               if(p <= 0){
                       switch(wrapped++){
                       case 0:         /* let loop run one more click */
                       case 2:
                               break;
                       case 1:         /* expired; wrap to end */
                               if(sel.r[0].q0>=0)
                                       goto Return;
                               list[0][0].inst = list[1][0].inst = nil;
                               p = t->file->nc;
                               goto doloop;
                       case 3:
                       default:
                               goto Return;
                       }
                       c = 0;
               }else{
                       if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
                               break;
                       c = textreadc(t, p-1);
               }
               /* fast check for first char */
               if(startchar && nnl==0 && c!=startchar)
                       continue;
               tl = list[flag];
               nl = list[flag^=1];
               nl->inst = nil;
               ntl = nnl;
               nnl = 0;
               if(sel.r[0].q0<0 && (!wrapped || p>startp)){
                       /* Add first instruction to this list */
                       /* the minus is so the optimizations in addinst work */
                       sempty.r[0].q0 = -p;
                       if(addinst(tl, bstartinst, &sempty))
                       if(++ntl >= NLIST){
       Overflow:
                               warning(nil, "regexp list overflow\n");
                               sel.r[0].q0 = -1;
                               goto Return;
                       }
               }
               /* Execute machine until this list is empty */
               for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
       Switchstmt:
                       switch(inst->type){
                       default:        /* regular character */
                               if(inst->type == c){
       Addinst:
                                       if(addinst(nl, inst->next, &tlp->se))
                                       if(++nnl >= NLIST)
                                               goto Overflow;
                               }
                               break;
                       case LBRA:
                               if(inst->subid>=0)
                                       tlp->se.r[inst->subid].q0 = p;
                               inst = inst->next;
                               goto Switchstmt;
                       case RBRA:
                               if(inst->subid >= 0)
                                       tlp->se.r[inst->subid].q1 = p;
                               inst = inst->next;
                               goto Switchstmt;
                       case ANY:
                               if(c != '\n')
                                       goto Addinst;
                               break;
                       case BOL:
                               if(c=='\n' || p==0){
       Step:
                                       inst = inst->next;
                                       goto Switchstmt;
                               }
                               break;
                       case EOL:
                               if(p<t->file->nc && textreadc(t, p)=='\n')
                                       goto Step;
                               break;
                       case CCLASS:
                               if(c>0 && classmatch(inst->class, c, 0))
                                       goto Addinst;
                               break;
                       case NCCLASS:
                               if(c>0 && classmatch(inst->class, c, 1))
                                       goto Addinst;
                               break;
                       case OR:
                               /* evaluate right choice later */
                               if(addinst(tl, inst->right, &tlp->se))
                               if(++ntl >= NLIST)
                                       goto Overflow;
                               /* efficiency: advance and re-evaluate */
                               inst = inst->left;
                               goto Switchstmt;
                       case END:       /* Match! */
                               tlp->se.r[0].q0 = -tlp->se.r[0].q0; /* minus sign */
                               tlp->se.r[0].q1 = p;
                               bnewmatch(&tlp->se);
                               break;
                       }
               }
       }
   Return:
       *rp = sel;
       return sel.r[0].q0 >= 0;
}

void
bnewmatch(Rangeset *sp)
{
       int  i;

       if(sel.r[0].q0<0 || sp->r[0].q0>sel.r[0].q1 || (sp->r[0].q0==sel.r[0].q1 && sp->r[0].q1<sel.r[0].q0))
               for(i = 0; i<NRange; i++){       /* note the reversal; q0<=q1 */
                       sel.r[i].q0 = sp->r[i].q1;
                       sel.r[i].q1 = sp->r[i].q0;
               }
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.