9base

revived minimalist port of Plan 9 userland to Unix
git clone git://git.suckless.org/9base
Log | Files | Refs | README | LICENSE

regexp.c (15453B)


      1 #include "sam.h"
      2 
      3 Rangeset	sel;
      4 String		lastregexp;
      5 /*
      6  * Machine Information
      7  */
      8 typedef struct Inst Inst;
      9 
     10 struct Inst
     11 {
     12 	long	type;	/* < 0x10000 ==> literal, otherwise action */
     13 	union {
     14 		int rsid;
     15 		int rsubid;
     16 		int class;
     17 		struct Inst *rother;
     18 		struct Inst *rright;
     19 	} r;
     20 	union{
     21 		struct Inst *lleft;
     22 		struct Inst *lnext;
     23 	} l;
     24 };
     25 #define	sid	r.rsid
     26 #define	subid	r.rsubid
     27 #define	rclass	r.class
     28 #define	other	r.rother
     29 #define	right	r.rright
     30 #define	left	l.lleft
     31 #define	next	l.lnext
     32 
     33 #define	NPROG	1024
     34 Inst	program[NPROG];
     35 Inst	*progp;
     36 Inst	*startinst;	/* First inst. of program; might not be program[0] */
     37 Inst	*bstartinst;	/* same for backwards machine */
     38 
     39 typedef struct Ilist Ilist;
     40 struct Ilist
     41 {
     42 	Inst	*inst;		/* Instruction of the thread */
     43 	Rangeset se;
     44 	Posn	startp;		/* first char of match */
     45 };
     46 
     47 #define	NLIST	127
     48 
     49 Ilist	*tl, *nl;	/* This list, next list */
     50 Ilist	list[2][NLIST+1];	/* +1 for trailing null */
     51 static	Rangeset sempty;
     52 
     53 /*
     54  * Actions and Tokens
     55  *
     56  *	0x100xx are operators, value == precedence
     57  *	0x200xx are tokens, i.e. operands for operators
     58  */
     59 #define	OPERATOR	0x10000	/* Bitmask of all operators */
     60 #define	START		0x10000	/* Start, used for marker on stack */
     61 #define	RBRA		0x10001	/* Right bracket, ) */
     62 #define	LBRA		0x10002	/* Left bracket, ( */
     63 #define	OR		0x10003	/* Alternation, | */
     64 #define	CAT		0x10004	/* Concatentation, implicit operator */
     65 #define	STAR		0x10005	/* Closure, * */
     66 #define	PLUS		0x10006	/* a+ == aa* */
     67 #define	QUEST		0x10007	/* a? == a|nothing, i.e. 0 or 1 a's */
     68 #define	ANY		0x20000	/* Any character but newline, . */
     69 #define	NOP		0x20001	/* No operation, internal use only */
     70 #define	BOL		0x20002	/* Beginning of line, ^ */
     71 #define	EOL		0x20003	/* End of line, $ */
     72 #define	CCLASS		0x20004	/* Character class, [] */
     73 #define	NCCLASS		0x20005	/* Negated character class, [^] */
     74 #define	END		0x20077	/* Terminate: match found */
     75 
     76 #define	ISATOR		0x10000
     77 #define	ISAND		0x20000
     78 
     79 /*
     80  * Parser Information
     81  */
     82 typedef struct Node Node;
     83 struct Node
     84 {
     85 	Inst	*first;
     86 	Inst	*last;
     87 };
     88 
     89 #define	NSTACK	20
     90 Node	andstack[NSTACK];
     91 Node	*andp;
     92 int	atorstack[NSTACK];
     93 int	*atorp;
     94 int	lastwasand;	/* Last token was operand */
     95 int	cursubid;
     96 int	subidstack[NSTACK];
     97 int	*subidp;
     98 int	backwards;
     99 int	nbra;
    100 Rune	*exprp;		/* pointer to next character in source expression */
    101 #define	DCLASS	10	/* allocation increment */
    102 int	nclass;		/* number active */
    103 int	Nclass;		/* high water mark */
    104 Rune	**class;
    105 int	negateclass;
    106 
    107 int	addinst(Ilist *l, Inst *inst, Rangeset *sep);
    108 void	newmatch(Rangeset*);
    109 void	bnewmatch(Rangeset*);
    110 void	pushand(Inst*, Inst*);
    111 void	pushator(int);
    112 Node	*popand(int);
    113 int	popator(void);
    114 void	startlex(Rune*);
    115 int	lex(void);
    116 void	operator(int);
    117 void	operand(int);
    118 void	evaluntil(int);
    119 void	optimize(Inst*);
    120 void	bldcclass(void);
    121 
    122 void
    123 regerror(Err e)
    124 {
    125 	Strzero(&lastregexp);
    126 	error(e);
    127 }
    128 
    129 void
    130 regerror_c(Err e, int c)
    131 {
    132 	Strzero(&lastregexp);
    133 	error_c(e, c);
    134 }
    135 
    136 Inst *
    137 newinst(int t)
    138 {
    139 	if(progp >= &program[NPROG])
    140 		regerror(Etoolong);
    141 	progp->type = t;
    142 	progp->left = 0;
    143 	progp->right = 0;
    144 	return progp++;
    145 }
    146 
    147 Inst *
    148 realcompile(Rune *s)
    149 {
    150 	int token;
    151 
    152 	startlex(s);
    153 	atorp = atorstack;
    154 	andp = andstack;
    155 	subidp = subidstack;
    156 	cursubid = 0;
    157 	lastwasand = FALSE;
    158 	/* Start with a low priority operator to prime parser */
    159 	pushator(START-1);
    160 	while((token=lex()) != END){
    161 		if((token&ISATOR) == OPERATOR)
    162 			operator(token);
    163 		else
    164 			operand(token);
    165 	}
    166 	/* Close with a low priority operator */
    167 	evaluntil(START);
    168 	/* Force END */
    169 	operand(END);
    170 	evaluntil(START);
    171 	if(nbra)
    172 		regerror(Eleftpar);
    173 	--andp;	/* points to first and only operand */
    174 	return andp->first;
    175 }
    176 
    177 void
    178 compile(String *s)
    179 {
    180 	int i;
    181 	Inst *oprogp;
    182 
    183 	if(Strcmp(s, &lastregexp)==0)
    184 		return;
    185 	for(i=0; i<nclass; i++)
    186 		free(class[i]);
    187 	nclass = 0;
    188 	progp = program;
    189 	backwards = FALSE;
    190 	startinst = realcompile(s->s);
    191 	optimize(program);
    192 	oprogp = progp;
    193 	backwards = TRUE;
    194 	bstartinst = realcompile(s->s);
    195 	optimize(oprogp);
    196 	Strduplstr(&lastregexp, s);
    197 }
    198 
    199 void
    200 operand(int t)
    201 {
    202 	Inst *i;
    203 	if(lastwasand)
    204 		operator(CAT);	/* catenate is implicit */
    205 	i = newinst(t);
    206 	if(t == CCLASS){
    207 		if(negateclass)
    208 			i->type = NCCLASS;	/* UGH */
    209 		i->rclass = nclass-1;		/* UGH */
    210 	}
    211 	pushand(i, i);
    212 	lastwasand = TRUE;
    213 }
    214 
    215 void
    216 operator(int t)
    217 {
    218 	if(t==RBRA && --nbra<0)
    219 		regerror(Erightpar);
    220 	if(t==LBRA){
    221 /*
    222  *		if(++cursubid >= NSUBEXP)
    223  *			regerror(Esubexp);
    224  */
    225 		cursubid++;	/* silently ignored */
    226 		nbra++;
    227 		if(lastwasand)
    228 			operator(CAT);
    229 	}else
    230 		evaluntil(t);
    231 	if(t!=RBRA)
    232 		pushator(t);
    233 	lastwasand = FALSE;
    234 	if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
    235 		lastwasand = TRUE;	/* these look like operands */
    236 }
    237 
    238 void
    239 cant(char *s)
    240 {
    241 	char buf[100];
    242 
    243 	sprint(buf, "regexp: can't happen: %s", s);
    244 	panic(buf);
    245 }
    246 
    247 void
    248 pushand(Inst *f, Inst *l)
    249 {
    250 	if(andp >= &andstack[NSTACK])
    251 		cant("operand stack overflow");
    252 	andp->first = f;
    253 	andp->last = l;
    254 	andp++;
    255 }
    256 
    257 void
    258 pushator(int t)
    259 {
    260 	if(atorp >= &atorstack[NSTACK])
    261 		cant("operator stack overflow");
    262 	*atorp++=t;
    263 	if(cursubid >= NSUBEXP)
    264 		*subidp++= -1;
    265 	else
    266 		*subidp++=cursubid;
    267 }
    268 
    269 Node *
    270 popand(int op)
    271 {
    272 	if(andp <= &andstack[0])
    273 		if(op)
    274 			regerror_c(Emissop, op);
    275 		else
    276 			regerror(Ebadregexp);
    277 	return --andp;
    278 }
    279 
    280 int
    281 popator(void)
    282 {
    283 	if(atorp <= &atorstack[0])
    284 		cant("operator stack underflow");
    285 	--subidp;
    286 	return *--atorp;
    287 }
    288 
    289 void
    290 evaluntil(int pri)
    291 {
    292 	Node *op1, *op2, *t;
    293 	Inst *inst1, *inst2;
    294 
    295 	while(pri==RBRA || atorp[-1]>=pri){
    296 		switch(popator()){
    297 		case LBRA:
    298 			op1 = popand('(');
    299 			inst2 = newinst(RBRA);
    300 			inst2->subid = *subidp;
    301 			op1->last->next = inst2;
    302 			inst1 = newinst(LBRA);
    303 			inst1->subid = *subidp;
    304 			inst1->next = op1->first;
    305 			pushand(inst1, inst2);
    306 			return;		/* must have been RBRA */
    307 		default:
    308 			panic("unknown regexp operator");
    309 			break;
    310 		case OR:
    311 			op2 = popand('|');
    312 			op1 = popand('|');
    313 			inst2 = newinst(NOP);
    314 			op2->last->next = inst2;
    315 			op1->last->next = inst2;
    316 			inst1 = newinst(OR);
    317 			inst1->right = op1->first;
    318 			inst1->left = op2->first;
    319 			pushand(inst1, inst2);
    320 			break;
    321 		case CAT:
    322 			op2 = popand(0);
    323 			op1 = popand(0);
    324 			if(backwards && op2->first->type!=END)
    325 				t = op1, op1 = op2, op2 = t;
    326 			op1->last->next = op2->first;
    327 			pushand(op1->first, op2->last);
    328 			break;
    329 		case STAR:
    330 			op2 = popand('*');
    331 			inst1 = newinst(OR);
    332 			op2->last->next = inst1;
    333 			inst1->right = op2->first;
    334 			pushand(inst1, inst1);
    335 			break;
    336 		case PLUS:
    337 			op2 = popand('+');
    338 			inst1 = newinst(OR);
    339 			op2->last->next = inst1;
    340 			inst1->right = op2->first;
    341 			pushand(op2->first, inst1);
    342 			break;
    343 		case QUEST:
    344 			op2 = popand('?');
    345 			inst1 = newinst(OR);
    346 			inst2 = newinst(NOP);
    347 			inst1->left = inst2;
    348 			inst1->right = op2->first;
    349 			op2->last->next = inst2;
    350 			pushand(inst1, inst2);
    351 			break;
    352 		}
    353 	}
    354 }
    355 
    356 
    357 void
    358 optimize(Inst *start)
    359 {
    360 	Inst *inst, *target;
    361 
    362 	for(inst=start; inst->type!=END; inst++){
    363 		target = inst->next;
    364 		while(target->type == NOP)
    365 			target = target->next;
    366 		inst->next = target;
    367 	}
    368 }
    369 
    370 #ifdef	DEBUG
    371 void
    372 dumpstack(void){
    373 	Node *stk;
    374 	int *ip;
    375 
    376 	dprint("operators\n");
    377 	for(ip = atorstack; ip<atorp; ip++)
    378 		dprint("0%o\n", *ip);
    379 	dprint("operands\n");
    380 	for(stk = andstack; stk<andp; stk++)
    381 		dprint("0%o\t0%o\n", stk->first->type, stk->last->type);
    382 }
    383 void
    384 dump(void){
    385 	Inst *l;
    386 
    387 	l = program;
    388 	do{
    389 		dprint("%d:\t0%o\t%d\t%d\n", l-program, l->type,
    390 			l->left-program, l->right-program);
    391 	}while(l++->type);
    392 }
    393 #endif
    394 
    395 void
    396 startlex(Rune *s)
    397 {
    398 	exprp = s;
    399 	nbra = 0;
    400 }
    401 
    402 
    403 int
    404 lex(void){
    405 	int c= *exprp++;
    406 
    407 	switch(c){
    408 	case '\\':
    409 		if(*exprp)
    410 			if((c= *exprp++)=='n')
    411 				c='\n';
    412 		break;
    413 	case 0:
    414 		c = END;
    415 		--exprp;	/* In case we come here again */
    416 		break;
    417 	case '*':
    418 		c = STAR;
    419 		break;
    420 	case '?':
    421 		c = QUEST;
    422 		break;
    423 	case '+':
    424 		c = PLUS;
    425 		break;
    426 	case '|':
    427 		c = OR;
    428 		break;
    429 	case '.':
    430 		c = ANY;
    431 		break;
    432 	case '(':
    433 		c = LBRA;
    434 		break;
    435 	case ')':
    436 		c = RBRA;
    437 		break;
    438 	case '^':
    439 		c = BOL;
    440 		break;
    441 	case '$':
    442 		c = EOL;
    443 		break;
    444 	case '[':
    445 		c = CCLASS;
    446 		bldcclass();
    447 		break;
    448 	}
    449 	return c;
    450 }
    451 
    452 long
    453 nextrec(void){
    454 	if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
    455 		regerror(Ebadclass);
    456 	if(exprp[0] == '\\'){
    457 		exprp++;
    458 		if(*exprp=='n'){
    459 			exprp++;
    460 			return '\n';
    461 		}
    462 		return *exprp++|0x10000;
    463 	}
    464 	return *exprp++;
    465 }
    466 
    467 void
    468 bldcclass(void)
    469 {
    470 	long c1, c2, n, na;
    471 	Rune *classp;
    472 
    473 	classp = emalloc(DCLASS*RUNESIZE);
    474 	n = 0;
    475 	na = DCLASS;
    476 	/* we have already seen the '[' */
    477 	if(*exprp == '^'){
    478 		classp[n++] = '\n';	/* don't match newline in negate case */
    479 		negateclass = TRUE;
    480 		exprp++;
    481 	}else
    482 		negateclass = FALSE;
    483 	while((c1 = nextrec()) != ']'){
    484 		if(c1 == '-'){
    485     Error:
    486 			free(classp);
    487 			regerror(Ebadclass);
    488 		}
    489 		if(n+4 >= na){		/* 3 runes plus NUL */
    490 			na += DCLASS;
    491 			classp = erealloc(classp, na*RUNESIZE);
    492 		}
    493 		if(*exprp == '-'){
    494 			exprp++;	/* eat '-' */
    495 			if((c2 = nextrec()) == ']')
    496 				goto Error;
    497 			classp[n+0] = Runemax;
    498 			classp[n+1] = c1;
    499 			classp[n+2] = c2;
    500 			n += 3;
    501 		}else
    502 			classp[n++] = c1;
    503 	}
    504 	classp[n] = 0;
    505 	if(nclass == Nclass){
    506 		Nclass += DCLASS;
    507 		class = erealloc(class, Nclass*sizeof(Rune*));
    508 	}
    509 	class[nclass++] = classp;
    510 }
    511 
    512 int
    513 classmatch(int classno, int c, int negate)
    514 {
    515 	Rune *p;
    516 
    517 	p = class[classno];
    518 	while(*p){
    519 		if(*p == Runemax){
    520 			if(p[1]<=c && c<=p[2])
    521 				return !negate;
    522 			p += 3;
    523 		}else if(*p++ == c)
    524 			return !negate;
    525 	}
    526 	return negate;
    527 }
    528 
    529 /*
    530  * Note optimization in addinst:
    531  * 	*l must be pending when addinst called; if *l has been looked
    532  *		at already, the optimization is a bug.
    533  */
    534 int
    535 addinst(Ilist *l, Inst *inst, Rangeset *sep)
    536 {
    537 	Ilist *p;
    538 
    539 	for(p = l; p->inst; p++){
    540 		if(p->inst==inst){
    541 			if((sep)->p[0].p1 < p->se.p[0].p1)
    542 				p->se= *sep;	/* this would be bug */
    543 			return 0;	/* It's already there */
    544 		}
    545 	}
    546 	p->inst = inst;
    547 	p->se= *sep;
    548 	(p+1)->inst = 0;
    549 	return 1;
    550 }
    551 
    552 int
    553 execute(File *f, Posn startp, Posn eof)
    554 {
    555 	int flag = 0;
    556 	Inst *inst;
    557 	Ilist *tlp;
    558 	Posn p = startp;
    559 	int nnl = 0, ntl;
    560 	int c;
    561 	int wrapped = 0;
    562 	int startchar = startinst->type<OPERATOR? startinst->type : 0;
    563 
    564 	list[0][0].inst = list[1][0].inst = 0;
    565 	sel.p[0].p1 = -1;
    566 	/* Execute machine once for each character */
    567 	for(;;p++){
    568 	doloop:
    569 		c = filereadc(f, p);
    570 		if(p>=eof || c<0){
    571 			switch(wrapped++){
    572 			case 0:		/* let loop run one more click */
    573 			case 2:
    574 				break;
    575 			case 1:		/* expired; wrap to beginning */
    576 				if(sel.p[0].p1>=0 || eof!=INFINITY)
    577 					goto Return;
    578 				list[0][0].inst = list[1][0].inst = 0;
    579 				p = 0;
    580 				goto doloop;
    581 			default:
    582 				goto Return;
    583 			}
    584 		}else if(((wrapped && p>=startp) || sel.p[0].p1>0) && nnl==0)
    585 			break;
    586 		/* fast check for first char */
    587 		if(startchar && nnl==0 && c!=startchar)
    588 			continue;
    589 		tl = list[flag];
    590 		nl = list[flag^=1];
    591 		nl->inst = 0;
    592 		ntl = nnl;
    593 		nnl = 0;
    594 		if(sel.p[0].p1<0 && (!wrapped || p<startp || startp==eof)){
    595 			/* Add first instruction to this list */
    596 			sempty.p[0].p1 = p;
    597 			if(addinst(tl, startinst, &sempty))
    598 			if(++ntl >= NLIST)
    599 	Overflow:
    600 				error(Eoverflow);
    601 		}
    602 		/* Execute machine until this list is empty */
    603 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
    604 	Switchstmt:
    605 			switch(inst->type){
    606 			default:	/* regular character */
    607 				if(inst->type==c){
    608 	Addinst:
    609 					if(addinst(nl, inst->next, &tlp->se))
    610 					if(++nnl >= NLIST)
    611 						goto Overflow;
    612 				}
    613 				break;
    614 			case LBRA:
    615 				if(inst->subid>=0)
    616 					tlp->se.p[inst->subid].p1 = p;
    617 				inst = inst->next;
    618 				goto Switchstmt;
    619 			case RBRA:
    620 				if(inst->subid>=0)
    621 					tlp->se.p[inst->subid].p2 = p;
    622 				inst = inst->next;
    623 				goto Switchstmt;
    624 			case ANY:
    625 				if(c!='\n')
    626 					goto Addinst;
    627 				break;
    628 			case BOL:
    629 				if(p==0 || filereadc(f, p - 1)=='\n'){
    630 	Step:
    631 					inst = inst->next;
    632 					goto Switchstmt;
    633 				}
    634 				break;
    635 			case EOL:
    636 				if(c == '\n')
    637 					goto Step;
    638 				break;
    639 			case CCLASS:
    640 				if(c>=0 && classmatch(inst->rclass, c, 0))
    641 					goto Addinst;
    642 				break;
    643 			case NCCLASS:
    644 				if(c>=0 && classmatch(inst->rclass, c, 1))
    645 					goto Addinst;
    646 				break;
    647 			case OR:
    648 				/* evaluate right choice later */
    649 				if(addinst(tl, inst->right, &tlp->se))
    650 				if(++ntl >= NLIST)
    651 					goto Overflow;
    652 				/* efficiency: advance and re-evaluate */
    653 				inst = inst->left;
    654 				goto Switchstmt;
    655 			case END:	/* Match! */
    656 				tlp->se.p[0].p2 = p;
    657 				newmatch(&tlp->se);
    658 				break;
    659 			}
    660 		}
    661 	}
    662     Return:
    663 	return sel.p[0].p1>=0;
    664 }
    665 
    666 void
    667 newmatch(Rangeset *sp)
    668 {
    669 	int i;
    670 
    671 	if(sel.p[0].p1<0 || sp->p[0].p1<sel.p[0].p1 ||
    672 	   (sp->p[0].p1==sel.p[0].p1 && sp->p[0].p2>sel.p[0].p2))
    673 		for(i = 0; i<NSUBEXP; i++)
    674 			sel.p[i] = sp->p[i];
    675 }
    676 
    677 int
    678 bexecute(File *f, Posn startp)
    679 {
    680 	int flag = 0;
    681 	Inst *inst;
    682 	Ilist *tlp;
    683 	Posn p = startp;
    684 	int nnl = 0, ntl;
    685 	int c;
    686 	int wrapped = 0;
    687 	int startchar = bstartinst->type<OPERATOR? bstartinst->type : 0;
    688 
    689 	list[0][0].inst = list[1][0].inst = 0;
    690 	sel.p[0].p1= -1;
    691 	/* Execute machine once for each character, including terminal NUL */
    692 	for(;;--p){
    693 	doloop:
    694 		if((c = filereadc(f, p - 1))==-1){
    695 			switch(wrapped++){
    696 			case 0:		/* let loop run one more click */
    697 			case 2:
    698 				break;
    699 			case 1:		/* expired; wrap to end */
    700 				if(sel.p[0].p1>=0)
    701 			case 3:
    702 					goto Return;
    703 				list[0][0].inst = list[1][0].inst = 0;
    704 				p = f->b.nc;
    705 				goto doloop;
    706 			default:
    707 				goto Return;
    708 			}
    709 		}else if(((wrapped && p<=startp) || sel.p[0].p1>0) && nnl==0)
    710 			break;
    711 		/* fast check for first char */
    712 		if(startchar && nnl==0 && c!=startchar)
    713 			continue;
    714 		tl = list[flag];
    715 		nl = list[flag^=1];
    716 		nl->inst = 0;
    717 		ntl = nnl;
    718 		nnl = 0;
    719 		if(sel.p[0].p1<0 && (!wrapped || p>startp)){
    720 			/* Add first instruction to this list */
    721 			/* the minus is so the optimizations in addinst work */
    722 			sempty.p[0].p1 = -p;
    723 			if(addinst(tl, bstartinst, &sempty))
    724 			if(++ntl >= NLIST)
    725 	Overflow:
    726 				error(Eoverflow);
    727 		}
    728 		/* Execute machine until this list is empty */
    729 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
    730 	Switchstmt:
    731 			switch(inst->type){
    732 			default:	/* regular character */
    733 				if(inst->type == c){
    734 	Addinst:
    735 					if(addinst(nl, inst->next, &tlp->se))
    736 					if(++nnl >= NLIST)
    737 						goto Overflow;
    738 				}
    739 				break;
    740 			case LBRA:
    741 				if(inst->subid>=0)
    742 					tlp->se.p[inst->subid].p1 = p;
    743 				inst = inst->next;
    744 				goto Switchstmt;
    745 			case RBRA:
    746 				if(inst->subid >= 0)
    747 					tlp->se.p[inst->subid].p2 = p;
    748 				inst = inst->next;
    749 				goto Switchstmt;
    750 			case ANY:
    751 				if(c != '\n')
    752 					goto Addinst;
    753 				break;
    754 			case BOL:
    755 				if(c=='\n' || p==0){
    756 	Step:
    757 					inst = inst->next;
    758 					goto Switchstmt;
    759 				}
    760 				break;
    761 			case EOL:
    762 				if(p==f->b.nc || filereadc(f, p)=='\n')
    763 					goto Step;
    764 				break;
    765 			case CCLASS:
    766 				if(c>=0 && classmatch(inst->rclass, c, 0))
    767 					goto Addinst;
    768 				break;
    769 			case NCCLASS:
    770 				if(c>=0 && classmatch(inst->rclass, c, 1))
    771 					goto Addinst;
    772 				break;
    773 			case OR:
    774 				/* evaluate right choice later */
    775 				if(addinst(tlp, inst->right, &tlp->se))
    776 				if(++ntl >= NLIST)
    777 					goto Overflow;
    778 				/* efficiency: advance and re-evaluate */
    779 				inst = inst->left;
    780 				goto Switchstmt;
    781 			case END:	/* Match! */
    782 				tlp->se.p[0].p1 = -tlp->se.p[0].p1; /* minus sign */
    783 				tlp->se.p[0].p2 = p;
    784 				bnewmatch(&tlp->se);
    785 				break;
    786 			}
    787 		}
    788 	}
    789     Return:
    790 	return sel.p[0].p1>=0;
    791 }
    792 
    793 void
    794 bnewmatch(Rangeset *sp)
    795 {
    796         int  i;
    797         if(sel.p[0].p1<0 || sp->p[0].p1>sel.p[0].p2 || (sp->p[0].p1==sel.p[0].p2 && sp->p[0].p2<sel.p[0].p1))
    798                 for(i = 0; i<NSUBEXP; i++){       /* note the reversal; p1<=p2 */
    799                         sel.p[i].p1 = sp->p[i].p2;
    800                         sel.p[i].p2 = sp->p[i].p1;
    801                 }
    802 }