regx.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

		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++|0x10000;
	}
	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] = 0xFFFF;
			classp[n+1] = c1;
			classp[n+2] = c2;
			n += 3;
		}else
			classp[n++] = c1;
	}
	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 == 0xFFFF){
			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.
 */
void
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;	/* It's already there */
		}
	}
	p->inst = inst;
	p->se= *sep;
	(p+1)->inst = nil;
}

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 */
			if(++ntl >= NLIST){
	Overflow:
				warning(nil, "regexp list overflow\n");
				sel.r[0].q0 = -1;
				goto Return;
			}
			sempty.r[0].q0 = p;
			addinst(tl, startinst, &sempty);
		}
		/* 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(++nnl >= NLIST)
						goto Overflow;
					addinst(nl, inst->next, &tlp->se);
				}
				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(++ntl >= NLIST)
					goto Overflow;
				addinst(tlp, inst->right, &tlp->se);
				/* 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 */
			if(++ntl >= NLIST){
	Overflow:
				warning(nil, "regexp list overflow\n");
				sel.r[0].q0 = -1;
				goto Return;
			}
			/* the minus is so the optimizations in addinst work */
			sempty.r[0].q0 = -p;
			addinst(tl, bstartinst, &sempty);
		}
		/* 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(++nnl >= NLIST)
						goto Overflow;
					addinst(nl, inst->next, &tlp->se);
				}
				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(++ntl >= NLIST)
					goto Overflow;
				addinst(tlp, inst->right, &tlp->se);
				/* 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;
                }
}