xref: /plan9/sys/src/cmd/acme/regx.c (revision 82726826a7b3d40fb66339b4b0e95b60314f98b9)
17dd7cddfSDavid du Colombier #include <u.h>
27dd7cddfSDavid du Colombier #include <libc.h>
37dd7cddfSDavid du Colombier #include <draw.h>
47dd7cddfSDavid du Colombier #include <thread.h>
59a747e4fSDavid du Colombier #include <cursor.h>
67dd7cddfSDavid du Colombier #include <mouse.h>
77dd7cddfSDavid du Colombier #include <keyboard.h>
87dd7cddfSDavid du Colombier #include <frame.h>
97dd7cddfSDavid du Colombier #include <fcall.h>
107dd7cddfSDavid du Colombier #include <plumb.h>
117dd7cddfSDavid du Colombier #include "dat.h"
127dd7cddfSDavid du Colombier #include "fns.h"
137dd7cddfSDavid du Colombier 
147dd7cddfSDavid du Colombier Rangeset	sel;
157dd7cddfSDavid du Colombier Rune		*lastregexp;
167dd7cddfSDavid du Colombier 
177dd7cddfSDavid du Colombier /*
187dd7cddfSDavid du Colombier  * Machine Information
197dd7cddfSDavid du Colombier  */
207dd7cddfSDavid du Colombier typedef struct Inst Inst;
217dd7cddfSDavid du Colombier struct Inst
227dd7cddfSDavid du Colombier {
23*82726826SDavid du Colombier 	uint	type;	/* <= Runemax+1 ==> literal, otherwise action */
247dd7cddfSDavid du Colombier 	union {
257dd7cddfSDavid du Colombier 		int sid;
267dd7cddfSDavid du Colombier 		int subid;
277dd7cddfSDavid du Colombier 		int class;
287dd7cddfSDavid du Colombier 		Inst *other;
297dd7cddfSDavid du Colombier 		Inst *right;
307dd7cddfSDavid du Colombier 	};
317dd7cddfSDavid du Colombier 	union{
327dd7cddfSDavid du Colombier 		Inst *left;
337dd7cddfSDavid du Colombier 		Inst *next;
347dd7cddfSDavid du Colombier 	};
357dd7cddfSDavid du Colombier };
367dd7cddfSDavid du Colombier 
377dd7cddfSDavid du Colombier #define	NPROG	1024
387dd7cddfSDavid du Colombier Inst	program[NPROG];
397dd7cddfSDavid du Colombier Inst	*progp;
407dd7cddfSDavid du Colombier Inst	*startinst;	/* First inst. of program; might not be program[0] */
417dd7cddfSDavid du Colombier Inst	*bstartinst;	/* same for backwards machine */
427dd7cddfSDavid du Colombier Channel	*rechan;	/* chan(Inst*) */
437dd7cddfSDavid du Colombier 
447dd7cddfSDavid du Colombier typedef struct Ilist Ilist;
457dd7cddfSDavid du Colombier struct Ilist
467dd7cddfSDavid du Colombier {
477dd7cddfSDavid du Colombier 	Inst	*inst;		/* Instruction of the thread */
487dd7cddfSDavid du Colombier 	Rangeset se;
497dd7cddfSDavid du Colombier 	uint	startp;		/* first char of match */
507dd7cddfSDavid du Colombier };
517dd7cddfSDavid du Colombier 
52e6dcbf51SDavid du Colombier #define	NLIST	127
537dd7cddfSDavid du Colombier 
547dd7cddfSDavid du Colombier Ilist	*tl, *nl;	/* This list, next list */
55e6dcbf51SDavid du Colombier Ilist	list[2][NLIST+1];	/* +1 for trailing null */
567dd7cddfSDavid du Colombier static	Rangeset sempty;
577dd7cddfSDavid du Colombier 
587dd7cddfSDavid du Colombier /*
597dd7cddfSDavid du Colombier  * Actions and Tokens
607dd7cddfSDavid du Colombier  *
617dd7cddfSDavid du Colombier  *	0x100xx are operators, value == precedence
627dd7cddfSDavid du Colombier  *	0x200xx are tokens, i.e. operands for operators
637dd7cddfSDavid du Colombier  */
64*82726826SDavid du Colombier enum {
65*82726826SDavid du Colombier 	OPERATOR = Runemask+1,	/* Bitmask of all operators */
66*82726826SDavid du Colombier 	START	= OPERATOR,	/* Start, used for marker on stack */
67*82726826SDavid du Colombier 	RBRA,			/* Right bracket, ) */
68*82726826SDavid du Colombier 	LBRA,			/* Left bracket, ( */
69*82726826SDavid du Colombier 	OR,			/* Alternation, | */
70*82726826SDavid du Colombier 	CAT,			/* Concatentation, implicit operator */
71*82726826SDavid du Colombier 	STAR,			/* Closure, * */
72*82726826SDavid du Colombier 	PLUS,			/* a+ == aa* */
73*82726826SDavid du Colombier 	QUEST,			/* a? == a|nothing, i.e. 0 or 1 a's */
747dd7cddfSDavid du Colombier 
75*82726826SDavid du Colombier 	ANY	= OPERATOR<<1,	/* Any character but newline, . */
76*82726826SDavid du Colombier 	NOP,			/* No operation, internal use only */
77*82726826SDavid du Colombier 	BOL,			/* Beginning of line, ^ */
78*82726826SDavid du Colombier 	EOL,			/* End of line, $ */
79*82726826SDavid du Colombier 	CCLASS,			/* Character class, [] */
80*82726826SDavid du Colombier 	NCCLASS,		/* Negated character class, [^] */
81*82726826SDavid du Colombier 	END,			/* Terminate: match found */
82*82726826SDavid du Colombier 
83*82726826SDavid du Colombier 	ISATOR	= OPERATOR,
84*82726826SDavid du Colombier 	ISAND	= OPERATOR<<1,
85*82726826SDavid du Colombier };
867dd7cddfSDavid du Colombier 
877dd7cddfSDavid du Colombier /*
887dd7cddfSDavid du Colombier  * Parser Information
897dd7cddfSDavid du Colombier  */
907dd7cddfSDavid du Colombier typedef struct Node Node;
917dd7cddfSDavid du Colombier struct Node
927dd7cddfSDavid du Colombier {
937dd7cddfSDavid du Colombier 	Inst	*first;
947dd7cddfSDavid du Colombier 	Inst	*last;
957dd7cddfSDavid du Colombier };
967dd7cddfSDavid du Colombier 
977dd7cddfSDavid du Colombier #define	NSTACK	20
987dd7cddfSDavid du Colombier Node	andstack[NSTACK];
997dd7cddfSDavid du Colombier Node	*andp;
1007dd7cddfSDavid du Colombier int	atorstack[NSTACK];
1017dd7cddfSDavid du Colombier int	*atorp;
1027dd7cddfSDavid du Colombier int	lastwasand;	/* Last token was operand */
1037dd7cddfSDavid du Colombier int	cursubid;
1047dd7cddfSDavid du Colombier int	subidstack[NSTACK];
1057dd7cddfSDavid du Colombier int	*subidp;
1067dd7cddfSDavid du Colombier int	backwards;
1077dd7cddfSDavid du Colombier int	nbra;
1087dd7cddfSDavid du Colombier Rune	*exprp;		/* pointer to next character in source expression */
1097dd7cddfSDavid du Colombier #define	DCLASS	10	/* allocation increment */
1107dd7cddfSDavid du Colombier int	nclass;		/* number active */
1117dd7cddfSDavid du Colombier int	Nclass;		/* high water mark */
1127dd7cddfSDavid du Colombier Rune	**class;
1137dd7cddfSDavid du Colombier int	negateclass;
1147dd7cddfSDavid du Colombier 
115e6dcbf51SDavid du Colombier int	addinst(Ilist *l, Inst *inst, Rangeset *sep);
1167dd7cddfSDavid du Colombier void	newmatch(Rangeset*);
1177dd7cddfSDavid du Colombier void	bnewmatch(Rangeset*);
1187dd7cddfSDavid du Colombier void	pushand(Inst*, Inst*);
1197dd7cddfSDavid du Colombier void	pushator(int);
1207dd7cddfSDavid du Colombier Node	*popand(int);
1217dd7cddfSDavid du Colombier int	popator(void);
1227dd7cddfSDavid du Colombier void	startlex(Rune*);
1237dd7cddfSDavid du Colombier int	lex(void);
1247dd7cddfSDavid du Colombier void	operator(int);
1257dd7cddfSDavid du Colombier void	operand(int);
1267dd7cddfSDavid du Colombier void	evaluntil(int);
1277dd7cddfSDavid du Colombier void	optimize(Inst*);
1287dd7cddfSDavid du Colombier void	bldcclass(void);
1297dd7cddfSDavid du Colombier 
1307dd7cddfSDavid du Colombier void
rxinit(void)1317dd7cddfSDavid du Colombier rxinit(void)
1327dd7cddfSDavid du Colombier {
1337dd7cddfSDavid du Colombier 	rechan = chancreate(sizeof(Inst*), 0);
1347dd7cddfSDavid du Colombier 	lastregexp = runemalloc(1);
1357dd7cddfSDavid du Colombier }
1367dd7cddfSDavid du Colombier 
1377dd7cddfSDavid du Colombier void
regerror(char * e)1387dd7cddfSDavid du Colombier regerror(char *e)
1397dd7cddfSDavid du Colombier {
1407dd7cddfSDavid du Colombier 	lastregexp[0] = 0;
1417dd7cddfSDavid du Colombier 	warning(nil, "regexp: %s\n", e);
1427dd7cddfSDavid du Colombier 	sendp(rechan, nil);
1437dd7cddfSDavid du Colombier 	threadexits(nil);
1447dd7cddfSDavid du Colombier }
1457dd7cddfSDavid du Colombier 
1467dd7cddfSDavid du Colombier Inst *
newinst(int t)1477dd7cddfSDavid du Colombier newinst(int t)
1487dd7cddfSDavid du Colombier {
1497dd7cddfSDavid du Colombier 	if(progp >= &program[NPROG])
1507dd7cddfSDavid du Colombier 		regerror("expression too long");
1517dd7cddfSDavid du Colombier 	progp->type = t;
1527dd7cddfSDavid du Colombier 	progp->left = nil;
1537dd7cddfSDavid du Colombier 	progp->right = nil;
1547dd7cddfSDavid du Colombier 	return progp++;
1557dd7cddfSDavid du Colombier }
1567dd7cddfSDavid du Colombier 
1577dd7cddfSDavid du Colombier void
realcompile(void * arg)1587dd7cddfSDavid du Colombier realcompile(void *arg)
1597dd7cddfSDavid du Colombier {
1607dd7cddfSDavid du Colombier 	int token;
1617dd7cddfSDavid du Colombier 	Rune *s;
1627dd7cddfSDavid du Colombier 
16359cc4ca5SDavid du Colombier 	threadsetname("regcomp");
1647dd7cddfSDavid du Colombier 	s = arg;
1657dd7cddfSDavid du Colombier 	startlex(s);
1667dd7cddfSDavid du Colombier 	atorp = atorstack;
1677dd7cddfSDavid du Colombier 	andp = andstack;
1687dd7cddfSDavid du Colombier 	subidp = subidstack;
1697dd7cddfSDavid du Colombier 	cursubid = 0;
1707dd7cddfSDavid du Colombier 	lastwasand = FALSE;
1717dd7cddfSDavid du Colombier 	/* Start with a low priority operator to prime parser */
1727dd7cddfSDavid du Colombier 	pushator(START-1);
1737dd7cddfSDavid du Colombier 	while((token=lex()) != END){
1747dd7cddfSDavid du Colombier 		if((token&ISATOR) == OPERATOR)
1757dd7cddfSDavid du Colombier 			operator(token);
1767dd7cddfSDavid du Colombier 		else
1777dd7cddfSDavid du Colombier 			operand(token);
1787dd7cddfSDavid du Colombier 	}
1797dd7cddfSDavid du Colombier 	/* Close with a low priority operator */
1807dd7cddfSDavid du Colombier 	evaluntil(START);
1817dd7cddfSDavid du Colombier 	/* Force END */
1827dd7cddfSDavid du Colombier 	operand(END);
1837dd7cddfSDavid du Colombier 	evaluntil(START);
1847dd7cddfSDavid du Colombier 	if(nbra)
1857dd7cddfSDavid du Colombier 		regerror("unmatched `('");
1867dd7cddfSDavid du Colombier 	--andp;	/* points to first and only operand */
1877dd7cddfSDavid du Colombier 	sendp(rechan, andp->first);
18859cc4ca5SDavid du Colombier 	threadexits(nil);
1897dd7cddfSDavid du Colombier }
1907dd7cddfSDavid du Colombier 
1917dd7cddfSDavid du Colombier /* r is null terminated */
1927dd7cddfSDavid du Colombier int
rxcompile(Rune * r)1937dd7cddfSDavid du Colombier rxcompile(Rune *r)
1947dd7cddfSDavid du Colombier {
1957dd7cddfSDavid du Colombier 	int i, nr;
1967dd7cddfSDavid du Colombier 	Inst *oprogp;
1977dd7cddfSDavid du Colombier 
1987dd7cddfSDavid du Colombier 	nr = runestrlen(r)+1;
1997dd7cddfSDavid du Colombier 	if(runeeq(lastregexp, runestrlen(lastregexp)+1, r, nr)==TRUE)
2007dd7cddfSDavid du Colombier 		return TRUE;
2017dd7cddfSDavid du Colombier 	lastregexp[0] = 0;
2027dd7cddfSDavid du Colombier 	for(i=0; i<nclass; i++)
2037dd7cddfSDavid du Colombier 		free(class[i]);
2047dd7cddfSDavid du Colombier 	nclass = 0;
2057dd7cddfSDavid du Colombier 	progp = program;
2067dd7cddfSDavid du Colombier 	backwards = FALSE;
2077dd7cddfSDavid du Colombier 	bstartinst = nil;
2087dd7cddfSDavid du Colombier 	threadcreate(realcompile, r, STACK);
2097dd7cddfSDavid du Colombier 	startinst = recvp(rechan);
2107dd7cddfSDavid du Colombier 	if(startinst == nil)
2117dd7cddfSDavid du Colombier 		return FALSE;
2127dd7cddfSDavid du Colombier 	optimize(program);
2137dd7cddfSDavid du Colombier 	oprogp = progp;
2147dd7cddfSDavid du Colombier 	backwards = TRUE;
2157dd7cddfSDavid du Colombier 	threadcreate(realcompile, r, STACK);
2167dd7cddfSDavid du Colombier 	bstartinst = recvp(rechan);
2177dd7cddfSDavid du Colombier 	if(bstartinst == nil)
2187dd7cddfSDavid du Colombier 		return FALSE;
2197dd7cddfSDavid du Colombier 	optimize(oprogp);
2207dd7cddfSDavid du Colombier 	lastregexp = runerealloc(lastregexp, nr);
2217dd7cddfSDavid du Colombier 	runemove(lastregexp, r, nr);
2227dd7cddfSDavid du Colombier 	return TRUE;
2237dd7cddfSDavid du Colombier }
2247dd7cddfSDavid du Colombier 
2257dd7cddfSDavid du Colombier void
operand(int t)2267dd7cddfSDavid du Colombier operand(int t)
2277dd7cddfSDavid du Colombier {
2287dd7cddfSDavid du Colombier 	Inst *i;
2297dd7cddfSDavid du Colombier 	if(lastwasand)
2307dd7cddfSDavid du Colombier 		operator(CAT);	/* catenate is implicit */
2317dd7cddfSDavid du Colombier 	i = newinst(t);
2327dd7cddfSDavid du Colombier 	if(t == CCLASS){
2337dd7cddfSDavid du Colombier 		if(negateclass)
2347dd7cddfSDavid du Colombier 			i->type = NCCLASS;	/* UGH */
2357dd7cddfSDavid du Colombier 		i->class = nclass-1;		/* UGH */
2367dd7cddfSDavid du Colombier 	}
2377dd7cddfSDavid du Colombier 	pushand(i, i);
2387dd7cddfSDavid du Colombier 	lastwasand = TRUE;
2397dd7cddfSDavid du Colombier }
2407dd7cddfSDavid du Colombier 
2417dd7cddfSDavid du Colombier void
operator(int t)2427dd7cddfSDavid du Colombier operator(int t)
2437dd7cddfSDavid du Colombier {
2447dd7cddfSDavid du Colombier 	if(t==RBRA && --nbra<0)
2457dd7cddfSDavid du Colombier 		regerror("unmatched `)'");
2467dd7cddfSDavid du Colombier 	if(t==LBRA){
2477dd7cddfSDavid du Colombier 		cursubid++;	/* silently ignored */
2487dd7cddfSDavid du Colombier 		nbra++;
2497dd7cddfSDavid du Colombier 		if(lastwasand)
2507dd7cddfSDavid du Colombier 			operator(CAT);
2517dd7cddfSDavid du Colombier 	}else
2527dd7cddfSDavid du Colombier 		evaluntil(t);
2537dd7cddfSDavid du Colombier 	if(t!=RBRA)
2547dd7cddfSDavid du Colombier 		pushator(t);
2557dd7cddfSDavid du Colombier 	lastwasand = FALSE;
2567dd7cddfSDavid du Colombier 	if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
2577dd7cddfSDavid du Colombier 		lastwasand = TRUE;	/* these look like operands */
2587dd7cddfSDavid du Colombier }
2597dd7cddfSDavid du Colombier 
2607dd7cddfSDavid du Colombier void
pushand(Inst * f,Inst * l)2617dd7cddfSDavid du Colombier pushand(Inst *f, Inst *l)
2627dd7cddfSDavid du Colombier {
2637dd7cddfSDavid du Colombier 	if(andp >= &andstack[NSTACK])
2647dd7cddfSDavid du Colombier 		error("operand stack overflow");
2657dd7cddfSDavid du Colombier 	andp->first = f;
2667dd7cddfSDavid du Colombier 	andp->last = l;
2677dd7cddfSDavid du Colombier 	andp++;
2687dd7cddfSDavid du Colombier }
2697dd7cddfSDavid du Colombier 
2707dd7cddfSDavid du Colombier void
pushator(int t)2717dd7cddfSDavid du Colombier pushator(int t)
2727dd7cddfSDavid du Colombier {
2737dd7cddfSDavid du Colombier 	if(atorp >= &atorstack[NSTACK])
2747dd7cddfSDavid du Colombier 		error("operator stack overflow");
2757dd7cddfSDavid du Colombier 	*atorp++=t;
2767dd7cddfSDavid du Colombier 	if(cursubid >= NRange)
2777dd7cddfSDavid du Colombier 		*subidp++= -1;
2787dd7cddfSDavid du Colombier 	else
2797dd7cddfSDavid du Colombier 		*subidp++=cursubid;
2807dd7cddfSDavid du Colombier }
2817dd7cddfSDavid du Colombier 
2827dd7cddfSDavid du Colombier Node *
popand(int op)2837dd7cddfSDavid du Colombier popand(int op)
2847dd7cddfSDavid du Colombier {
2857dd7cddfSDavid du Colombier 	char buf[64];
2867dd7cddfSDavid du Colombier 
2877dd7cddfSDavid du Colombier 	if(andp <= &andstack[0])
2887dd7cddfSDavid du Colombier 		if(op){
2897dd7cddfSDavid du Colombier 			sprint(buf, "missing operand for %c", op);
2907dd7cddfSDavid du Colombier 			regerror(buf);
2917dd7cddfSDavid du Colombier 		}else
2927dd7cddfSDavid du Colombier 			regerror("malformed regexp");
2937dd7cddfSDavid du Colombier 	return --andp;
2947dd7cddfSDavid du Colombier }
2957dd7cddfSDavid du Colombier 
2967dd7cddfSDavid du Colombier int
popator()2977dd7cddfSDavid du Colombier popator()
2987dd7cddfSDavid du Colombier {
2997dd7cddfSDavid du Colombier 	if(atorp <= &atorstack[0])
3007dd7cddfSDavid du Colombier 		error("operator stack underflow");
3017dd7cddfSDavid du Colombier 	--subidp;
3027dd7cddfSDavid du Colombier 	return *--atorp;
3037dd7cddfSDavid du Colombier }
3047dd7cddfSDavid du Colombier 
3057dd7cddfSDavid du Colombier void
evaluntil(int pri)3067dd7cddfSDavid du Colombier evaluntil(int pri)
3077dd7cddfSDavid du Colombier {
3087dd7cddfSDavid du Colombier 	Node *op1, *op2, *t;
3097dd7cddfSDavid du Colombier 	Inst *inst1, *inst2;
3107dd7cddfSDavid du Colombier 
3117dd7cddfSDavid du Colombier 	while(pri==RBRA || atorp[-1]>=pri){
3127dd7cddfSDavid du Colombier 		switch(popator()){
3137dd7cddfSDavid du Colombier 		case LBRA:
3147dd7cddfSDavid du Colombier 			op1 = popand('(');
3157dd7cddfSDavid du Colombier 			inst2 = newinst(RBRA);
3167dd7cddfSDavid du Colombier 			inst2->subid = *subidp;
3177dd7cddfSDavid du Colombier 			op1->last->next = inst2;
3187dd7cddfSDavid du Colombier 			inst1 = newinst(LBRA);
3197dd7cddfSDavid du Colombier 			inst1->subid = *subidp;
3207dd7cddfSDavid du Colombier 			inst1->next = op1->first;
3217dd7cddfSDavid du Colombier 			pushand(inst1, inst2);
3227dd7cddfSDavid du Colombier 			return;		/* must have been RBRA */
3237dd7cddfSDavid du Colombier 		default:
3247dd7cddfSDavid du Colombier 			error("unknown regexp operator");
3257dd7cddfSDavid du Colombier 			break;
3267dd7cddfSDavid du Colombier 		case OR:
3277dd7cddfSDavid du Colombier 			op2 = popand('|');
3287dd7cddfSDavid du Colombier 			op1 = popand('|');
3297dd7cddfSDavid du Colombier 			inst2 = newinst(NOP);
3307dd7cddfSDavid du Colombier 			op2->last->next = inst2;
3317dd7cddfSDavid du Colombier 			op1->last->next = inst2;
3327dd7cddfSDavid du Colombier 			inst1 = newinst(OR);
3337dd7cddfSDavid du Colombier 			inst1->right = op1->first;
3347dd7cddfSDavid du Colombier 			inst1->left = op2->first;
3357dd7cddfSDavid du Colombier 			pushand(inst1, inst2);
3367dd7cddfSDavid du Colombier 			break;
3377dd7cddfSDavid du Colombier 		case CAT:
3387dd7cddfSDavid du Colombier 			op2 = popand(0);
3397dd7cddfSDavid du Colombier 			op1 = popand(0);
3407dd7cddfSDavid du Colombier 			if(backwards && op2->first->type!=END){
3417dd7cddfSDavid du Colombier 				t = op1;
3427dd7cddfSDavid du Colombier 				op1 = op2;
3437dd7cddfSDavid du Colombier 				op2 = t;
3447dd7cddfSDavid du Colombier 			}
3457dd7cddfSDavid du Colombier 			op1->last->next = op2->first;
3467dd7cddfSDavid du Colombier 			pushand(op1->first, op2->last);
3477dd7cddfSDavid du Colombier 			break;
3487dd7cddfSDavid du Colombier 		case STAR:
3497dd7cddfSDavid du Colombier 			op2 = popand('*');
3507dd7cddfSDavid du Colombier 			inst1 = newinst(OR);
3517dd7cddfSDavid du Colombier 			op2->last->next = inst1;
3527dd7cddfSDavid du Colombier 			inst1->right = op2->first;
3537dd7cddfSDavid du Colombier 			pushand(inst1, inst1);
3547dd7cddfSDavid du Colombier 			break;
3557dd7cddfSDavid du Colombier 		case PLUS:
3567dd7cddfSDavid du Colombier 			op2 = popand('+');
3577dd7cddfSDavid du Colombier 			inst1 = newinst(OR);
3587dd7cddfSDavid du Colombier 			op2->last->next = inst1;
3597dd7cddfSDavid du Colombier 			inst1->right = op2->first;
3607dd7cddfSDavid du Colombier 			pushand(op2->first, inst1);
3617dd7cddfSDavid du Colombier 			break;
3627dd7cddfSDavid du Colombier 		case QUEST:
3637dd7cddfSDavid du Colombier 			op2 = popand('?');
3647dd7cddfSDavid du Colombier 			inst1 = newinst(OR);
3657dd7cddfSDavid du Colombier 			inst2 = newinst(NOP);
3667dd7cddfSDavid du Colombier 			inst1->left = inst2;
3677dd7cddfSDavid du Colombier 			inst1->right = op2->first;
3687dd7cddfSDavid du Colombier 			op2->last->next = inst2;
3697dd7cddfSDavid du Colombier 			pushand(inst1, inst2);
3707dd7cddfSDavid du Colombier 			break;
3717dd7cddfSDavid du Colombier 		}
3727dd7cddfSDavid du Colombier 	}
3737dd7cddfSDavid du Colombier }
3747dd7cddfSDavid du Colombier 
3757dd7cddfSDavid du Colombier 
3767dd7cddfSDavid du Colombier void
optimize(Inst * start)3777dd7cddfSDavid du Colombier optimize(Inst *start)
3787dd7cddfSDavid du Colombier {
3797dd7cddfSDavid du Colombier 	Inst *inst, *target;
3807dd7cddfSDavid du Colombier 
3817dd7cddfSDavid du Colombier 	for(inst=start; inst->type!=END; inst++){
3827dd7cddfSDavid du Colombier 		target = inst->next;
3837dd7cddfSDavid du Colombier 		while(target->type == NOP)
3847dd7cddfSDavid du Colombier 			target = target->next;
3857dd7cddfSDavid du Colombier 		inst->next = target;
3867dd7cddfSDavid du Colombier 	}
3877dd7cddfSDavid du Colombier }
3887dd7cddfSDavid du Colombier 
3897dd7cddfSDavid du Colombier void
startlex(Rune * s)3907dd7cddfSDavid du Colombier startlex(Rune *s)
3917dd7cddfSDavid du Colombier {
3927dd7cddfSDavid du Colombier 	exprp = s;
3937dd7cddfSDavid du Colombier 	nbra = 0;
3947dd7cddfSDavid du Colombier }
3957dd7cddfSDavid du Colombier 
3967dd7cddfSDavid du Colombier 
3977dd7cddfSDavid du Colombier int
lex(void)3987dd7cddfSDavid du Colombier lex(void){
3997dd7cddfSDavid du Colombier 	int c;
4007dd7cddfSDavid du Colombier 
4017dd7cddfSDavid du Colombier 	c = *exprp++;
4027dd7cddfSDavid du Colombier 	switch(c){
4037dd7cddfSDavid du Colombier 	case '\\':
4047dd7cddfSDavid du Colombier 		if(*exprp)
4057dd7cddfSDavid du Colombier 			if((c= *exprp++)=='n')
4067dd7cddfSDavid du Colombier 				c='\n';
4077dd7cddfSDavid du Colombier 		break;
4087dd7cddfSDavid du Colombier 	case 0:
4097dd7cddfSDavid du Colombier 		c = END;
4107dd7cddfSDavid du Colombier 		--exprp;	/* In case we come here again */
4117dd7cddfSDavid du Colombier 		break;
4127dd7cddfSDavid du Colombier 	case '*':
4137dd7cddfSDavid du Colombier 		c = STAR;
4147dd7cddfSDavid du Colombier 		break;
4157dd7cddfSDavid du Colombier 	case '?':
4167dd7cddfSDavid du Colombier 		c = QUEST;
4177dd7cddfSDavid du Colombier 		break;
4187dd7cddfSDavid du Colombier 	case '+':
4197dd7cddfSDavid du Colombier 		c = PLUS;
4207dd7cddfSDavid du Colombier 		break;
4217dd7cddfSDavid du Colombier 	case '|':
4227dd7cddfSDavid du Colombier 		c = OR;
4237dd7cddfSDavid du Colombier 		break;
4247dd7cddfSDavid du Colombier 	case '.':
4257dd7cddfSDavid du Colombier 		c = ANY;
4267dd7cddfSDavid du Colombier 		break;
4277dd7cddfSDavid du Colombier 	case '(':
4287dd7cddfSDavid du Colombier 		c = LBRA;
4297dd7cddfSDavid du Colombier 		break;
4307dd7cddfSDavid du Colombier 	case ')':
4317dd7cddfSDavid du Colombier 		c = RBRA;
4327dd7cddfSDavid du Colombier 		break;
4337dd7cddfSDavid du Colombier 	case '^':
4347dd7cddfSDavid du Colombier 		c = BOL;
4357dd7cddfSDavid du Colombier 		break;
4367dd7cddfSDavid du Colombier 	case '$':
4377dd7cddfSDavid du Colombier 		c = EOL;
4387dd7cddfSDavid du Colombier 		break;
4397dd7cddfSDavid du Colombier 	case '[':
4407dd7cddfSDavid du Colombier 		c = CCLASS;
4417dd7cddfSDavid du Colombier 		bldcclass();
4427dd7cddfSDavid du Colombier 		break;
4437dd7cddfSDavid du Colombier 	}
4447dd7cddfSDavid du Colombier 	return c;
4457dd7cddfSDavid du Colombier }
4467dd7cddfSDavid du Colombier 
4477dd7cddfSDavid du Colombier int
nextrec(void)4487dd7cddfSDavid du Colombier nextrec(void)
4497dd7cddfSDavid du Colombier {
4507dd7cddfSDavid du Colombier 	if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
4517dd7cddfSDavid du Colombier 		regerror("malformed `[]'");
4527dd7cddfSDavid du Colombier 	if(exprp[0] == '\\'){
4537dd7cddfSDavid du Colombier 		exprp++;
4547dd7cddfSDavid du Colombier 		if(*exprp=='n'){
4557dd7cddfSDavid du Colombier 			exprp++;
4567dd7cddfSDavid du Colombier 			return '\n';
4577dd7cddfSDavid du Colombier 		}
458*82726826SDavid du Colombier 		return *exprp++|(Runemax+1);
4597dd7cddfSDavid du Colombier 	}
4607dd7cddfSDavid du Colombier 	return *exprp++;
4617dd7cddfSDavid du Colombier }
4627dd7cddfSDavid du Colombier 
4637dd7cddfSDavid du Colombier void
bldcclass(void)4647dd7cddfSDavid du Colombier bldcclass(void)
4657dd7cddfSDavid du Colombier {
4667dd7cddfSDavid du Colombier 	int c1, c2, n, na;
4677dd7cddfSDavid du Colombier 	Rune *classp;
4687dd7cddfSDavid du Colombier 
4697dd7cddfSDavid du Colombier 	classp = runemalloc(DCLASS);
4707dd7cddfSDavid du Colombier 	n = 0;
4717dd7cddfSDavid du Colombier 	na = DCLASS;
4727dd7cddfSDavid du Colombier 	/* we have already seen the '[' */
4737dd7cddfSDavid du Colombier 	if(*exprp == '^'){
4747dd7cddfSDavid du Colombier 		classp[n++] = '\n';	/* don't match newline in negate case */
4757dd7cddfSDavid du Colombier 		negateclass = TRUE;
4767dd7cddfSDavid du Colombier 		exprp++;
4777dd7cddfSDavid du Colombier 	}else
4787dd7cddfSDavid du Colombier 		negateclass = FALSE;
4797dd7cddfSDavid du Colombier 	while((c1 = nextrec()) != ']'){
4807dd7cddfSDavid du Colombier 		if(c1 == '-'){
4817dd7cddfSDavid du Colombier     Error:
4827dd7cddfSDavid du Colombier 			free(classp);
4837dd7cddfSDavid du Colombier 			regerror("malformed `[]'");
4847dd7cddfSDavid du Colombier 		}
4857dd7cddfSDavid du Colombier 		if(n+4 >= na){		/* 3 runes plus NUL */
4867dd7cddfSDavid du Colombier 			na += DCLASS;
4877dd7cddfSDavid du Colombier 			classp = runerealloc(classp, na);
4887dd7cddfSDavid du Colombier 		}
4897dd7cddfSDavid du Colombier 		if(*exprp == '-'){
4907dd7cddfSDavid du Colombier 			exprp++;	/* eat '-' */
4917dd7cddfSDavid du Colombier 			if((c2 = nextrec()) == ']')
4927dd7cddfSDavid du Colombier 				goto Error;
493*82726826SDavid du Colombier 			classp[n+0] = Runemax;
4947dd7cddfSDavid du Colombier 			classp[n+1] = c1;
4957dd7cddfSDavid du Colombier 			classp[n+2] = c2;
4967dd7cddfSDavid du Colombier 			n += 3;
4977dd7cddfSDavid du Colombier 		}else
4987dd7cddfSDavid du Colombier 			classp[n++] = c1;
4997dd7cddfSDavid du Colombier 	}
5007dd7cddfSDavid du Colombier 	classp[n] = 0;
5017dd7cddfSDavid du Colombier 	if(nclass == Nclass){
5027dd7cddfSDavid du Colombier 		Nclass += DCLASS;
5037dd7cddfSDavid du Colombier 		class = realloc(class, Nclass*sizeof(Rune*));
5047dd7cddfSDavid du Colombier 	}
5057dd7cddfSDavid du Colombier 	class[nclass++] = classp;
5067dd7cddfSDavid du Colombier }
5077dd7cddfSDavid du Colombier 
5087dd7cddfSDavid du Colombier int
classmatch(int classno,int c,int negate)5097dd7cddfSDavid du Colombier classmatch(int classno, int c, int negate)
5107dd7cddfSDavid du Colombier {
5117dd7cddfSDavid du Colombier 	Rune *p;
5127dd7cddfSDavid du Colombier 
5137dd7cddfSDavid du Colombier 	p = class[classno];
5147dd7cddfSDavid du Colombier 	while(*p){
515*82726826SDavid du Colombier 		if(*p == Runemax){
5167dd7cddfSDavid du Colombier 			if(p[1]<=c && c<=p[2])
5177dd7cddfSDavid du Colombier 				return !negate;
5187dd7cddfSDavid du Colombier 			p += 3;
5197dd7cddfSDavid du Colombier 		}else if(*p++ == c)
5207dd7cddfSDavid du Colombier 			return !negate;
5217dd7cddfSDavid du Colombier 	}
5227dd7cddfSDavid du Colombier 	return negate;
5237dd7cddfSDavid du Colombier }
5247dd7cddfSDavid du Colombier 
5257dd7cddfSDavid du Colombier /*
5267dd7cddfSDavid du Colombier  * Note optimization in addinst:
5277dd7cddfSDavid du Colombier  * 	*l must be pending when addinst called; if *l has been looked
5287dd7cddfSDavid du Colombier  *		at already, the optimization is a bug.
5297dd7cddfSDavid du Colombier  */
530e6dcbf51SDavid du Colombier int
addinst(Ilist * l,Inst * inst,Rangeset * sep)5317dd7cddfSDavid du Colombier addinst(Ilist *l, Inst *inst, Rangeset *sep)
5327dd7cddfSDavid du Colombier {
5337dd7cddfSDavid du Colombier 	Ilist *p;
5347dd7cddfSDavid du Colombier 
5357dd7cddfSDavid du Colombier 	for(p = l; p->inst; p++){
5367dd7cddfSDavid du Colombier 		if(p->inst==inst){
5377dd7cddfSDavid du Colombier 			if((sep)->r[0].q0 < p->se.r[0].q0)
5387dd7cddfSDavid du Colombier 				p->se= *sep;	/* this would be bug */
539e6dcbf51SDavid du Colombier 			return 0;	/* It's already there */
5407dd7cddfSDavid du Colombier 		}
5417dd7cddfSDavid du Colombier 	}
5427dd7cddfSDavid du Colombier 	p->inst = inst;
5437dd7cddfSDavid du Colombier 	p->se= *sep;
5447dd7cddfSDavid du Colombier 	(p+1)->inst = nil;
545e6dcbf51SDavid du Colombier 	return 1;
5467dd7cddfSDavid du Colombier }
5477dd7cddfSDavid du Colombier 
5487dd7cddfSDavid du Colombier int
rxnull(void)5497dd7cddfSDavid du Colombier rxnull(void)
5507dd7cddfSDavid du Colombier {
5517dd7cddfSDavid du Colombier 	return startinst==nil || bstartinst==nil;
5527dd7cddfSDavid du Colombier }
5537dd7cddfSDavid du Colombier 
55459cc4ca5SDavid du Colombier /* either t!=nil or r!=nil, and we match the string in the appropriate place */
5557dd7cddfSDavid du Colombier int
rxexecute(Text * t,Rune * r,uint startp,uint eof,Rangeset * rp)55659cc4ca5SDavid du Colombier rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
5577dd7cddfSDavid du Colombier {
5587dd7cddfSDavid du Colombier 	int flag;
5597dd7cddfSDavid du Colombier 	Inst *inst;
5607dd7cddfSDavid du Colombier 	Ilist *tlp;
5617dd7cddfSDavid du Colombier 	uint p;
5627dd7cddfSDavid du Colombier 	int nnl, ntl;
56359cc4ca5SDavid du Colombier 	int nc, c;
5647dd7cddfSDavid du Colombier 	int wrapped;
5657dd7cddfSDavid du Colombier 	int startchar;
5667dd7cddfSDavid du Colombier 
5677dd7cddfSDavid du Colombier 	flag = 0;
5687dd7cddfSDavid du Colombier 	p = startp;
5697dd7cddfSDavid du Colombier 	startchar = 0;
5707dd7cddfSDavid du Colombier 	wrapped = 0;
5717dd7cddfSDavid du Colombier 	nnl = 0;
5727dd7cddfSDavid du Colombier 	if(startinst->type<OPERATOR)
5737dd7cddfSDavid du Colombier 		startchar = startinst->type;
5747dd7cddfSDavid du Colombier 	list[0][0].inst = list[1][0].inst = nil;
5757dd7cddfSDavid du Colombier 	sel.r[0].q0 = -1;
57659cc4ca5SDavid du Colombier 	if(t != nil)
57759cc4ca5SDavid du Colombier 		nc = t->file->nc;
57859cc4ca5SDavid du Colombier 	else
57959cc4ca5SDavid du Colombier 		nc = runestrlen(r);
5807dd7cddfSDavid du Colombier 	/* Execute machine once for each character */
5817dd7cddfSDavid du Colombier 	for(;;p++){
5827dd7cddfSDavid du Colombier 	doloop:
58359cc4ca5SDavid du Colombier 		if(p>=eof || p>=nc){
5847dd7cddfSDavid du Colombier 			switch(wrapped++){
5857dd7cddfSDavid du Colombier 			case 0:		/* let loop run one more click */
5867dd7cddfSDavid du Colombier 			case 2:
5877dd7cddfSDavid du Colombier 				break;
5887dd7cddfSDavid du Colombier 			case 1:		/* expired; wrap to beginning */
5897dd7cddfSDavid du Colombier 				if(sel.r[0].q0>=0 || eof!=Infinity)
5907dd7cddfSDavid du Colombier 					goto Return;
5917dd7cddfSDavid du Colombier 				list[0][0].inst = list[1][0].inst = nil;
5927dd7cddfSDavid du Colombier 				p = 0;
5937dd7cddfSDavid du Colombier 				goto doloop;
5947dd7cddfSDavid du Colombier 			default:
5957dd7cddfSDavid du Colombier 				goto Return;
5967dd7cddfSDavid du Colombier 			}
5977dd7cddfSDavid du Colombier 			c = 0;
5987dd7cddfSDavid du Colombier 		}else{
5997dd7cddfSDavid du Colombier 			if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
6007dd7cddfSDavid du Colombier 				break;
60159cc4ca5SDavid du Colombier 			if(t != nil)
6027dd7cddfSDavid du Colombier 				c = textreadc(t, p);
60359cc4ca5SDavid du Colombier 			else
60459cc4ca5SDavid du Colombier 				c = r[p];
6057dd7cddfSDavid du Colombier 		}
6067dd7cddfSDavid du Colombier 		/* fast check for first char */
6077dd7cddfSDavid du Colombier 		if(startchar && nnl==0 && c!=startchar)
6087dd7cddfSDavid du Colombier 			continue;
6097dd7cddfSDavid du Colombier 		tl = list[flag];
6107dd7cddfSDavid du Colombier 		nl = list[flag^=1];
6117dd7cddfSDavid du Colombier 		nl->inst = nil;
6127dd7cddfSDavid du Colombier 		ntl = nnl;
6137dd7cddfSDavid du Colombier 		nnl = 0;
6147dd7cddfSDavid du Colombier 		if(sel.r[0].q0<0 && (!wrapped || p<startp || startp==eof)){
6157dd7cddfSDavid du Colombier 			/* Add first instruction to this list */
616e6dcbf51SDavid du Colombier 			sempty.r[0].q0 = p;
617e6dcbf51SDavid du Colombier 			if(addinst(tl, startinst, &sempty))
6187dd7cddfSDavid du Colombier 			if(++ntl >= NLIST){
6197dd7cddfSDavid du Colombier 	Overflow:
6207dd7cddfSDavid du Colombier 				warning(nil, "regexp list overflow\n");
6217dd7cddfSDavid du Colombier 				sel.r[0].q0 = -1;
6227dd7cddfSDavid du Colombier 				goto Return;
6237dd7cddfSDavid du Colombier 			}
6247dd7cddfSDavid du Colombier 		}
6257dd7cddfSDavid du Colombier 		/* Execute machine until this list is empty */
6267dd7cddfSDavid du Colombier 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
6277dd7cddfSDavid du Colombier 	Switchstmt:
6287dd7cddfSDavid du Colombier 			switch(inst->type){
6297dd7cddfSDavid du Colombier 			default:	/* regular character */
6307dd7cddfSDavid du Colombier 				if(inst->type==c){
6317dd7cddfSDavid du Colombier 	Addinst:
632e6dcbf51SDavid du Colombier 					if(addinst(nl, inst->next, &tlp->se))
6337dd7cddfSDavid du Colombier 					if(++nnl >= NLIST)
6347dd7cddfSDavid du Colombier 						goto Overflow;
6357dd7cddfSDavid du Colombier 				}
6367dd7cddfSDavid du Colombier 				break;
6377dd7cddfSDavid du Colombier 			case LBRA:
6387dd7cddfSDavid du Colombier 				if(inst->subid>=0)
6397dd7cddfSDavid du Colombier 					tlp->se.r[inst->subid].q0 = p;
6407dd7cddfSDavid du Colombier 				inst = inst->next;
6417dd7cddfSDavid du Colombier 				goto Switchstmt;
6427dd7cddfSDavid du Colombier 			case RBRA:
6437dd7cddfSDavid du Colombier 				if(inst->subid>=0)
6447dd7cddfSDavid du Colombier 					tlp->se.r[inst->subid].q1 = p;
6457dd7cddfSDavid du Colombier 				inst = inst->next;
6467dd7cddfSDavid du Colombier 				goto Switchstmt;
6477dd7cddfSDavid du Colombier 			case ANY:
6487dd7cddfSDavid du Colombier 				if(c!='\n')
6497dd7cddfSDavid du Colombier 					goto Addinst;
6507dd7cddfSDavid du Colombier 				break;
6517dd7cddfSDavid du Colombier 			case BOL:
65259cc4ca5SDavid du Colombier 				if(p==0 || (t!=nil && textreadc(t, p-1)=='\n') || (r!=nil && r[p-1]=='\n')){
6537dd7cddfSDavid du Colombier 	Step:
6547dd7cddfSDavid du Colombier 					inst = inst->next;
6557dd7cddfSDavid du Colombier 					goto Switchstmt;
6567dd7cddfSDavid du Colombier 				}
6577dd7cddfSDavid du Colombier 				break;
6587dd7cddfSDavid du Colombier 			case EOL:
6597dd7cddfSDavid du Colombier 				if(c == '\n')
6607dd7cddfSDavid du Colombier 					goto Step;
6617dd7cddfSDavid du Colombier 				break;
6627dd7cddfSDavid du Colombier 			case CCLASS:
6637dd7cddfSDavid du Colombier 				if(c>=0 && classmatch(inst->class, c, 0))
6647dd7cddfSDavid du Colombier 					goto Addinst;
6657dd7cddfSDavid du Colombier 				break;
6667dd7cddfSDavid du Colombier 			case NCCLASS:
6677dd7cddfSDavid du Colombier 				if(c>=0 && classmatch(inst->class, c, 1))
6687dd7cddfSDavid du Colombier 					goto Addinst;
6697dd7cddfSDavid du Colombier 				break;
6707dd7cddfSDavid du Colombier 			case OR:
6717dd7cddfSDavid du Colombier 				/* evaluate right choice later */
672e7f22645SDavid du Colombier 				if(addinst(tlp, inst->right, &tlp->se))
6737dd7cddfSDavid du Colombier 				if(++ntl >= NLIST)
6747dd7cddfSDavid du Colombier 					goto Overflow;
6757dd7cddfSDavid du Colombier 				/* efficiency: advance and re-evaluate */
6767dd7cddfSDavid du Colombier 				inst = inst->left;
6777dd7cddfSDavid du Colombier 				goto Switchstmt;
6787dd7cddfSDavid du Colombier 			case END:	/* Match! */
6797dd7cddfSDavid du Colombier 				tlp->se.r[0].q1 = p;
6807dd7cddfSDavid du Colombier 				newmatch(&tlp->se);
6817dd7cddfSDavid du Colombier 				break;
6827dd7cddfSDavid du Colombier 			}
6837dd7cddfSDavid du Colombier 		}
6847dd7cddfSDavid du Colombier 	}
6857dd7cddfSDavid du Colombier     Return:
6867dd7cddfSDavid du Colombier 	*rp = sel;
6877dd7cddfSDavid du Colombier 	return sel.r[0].q0 >= 0;
6887dd7cddfSDavid du Colombier }
6897dd7cddfSDavid du Colombier 
6907dd7cddfSDavid du Colombier void
newmatch(Rangeset * sp)6917dd7cddfSDavid du Colombier newmatch(Rangeset *sp)
6927dd7cddfSDavid du Colombier {
6937dd7cddfSDavid du Colombier 	if(sel.r[0].q0<0 || sp->r[0].q0<sel.r[0].q0 ||
6947dd7cddfSDavid du Colombier 	   (sp->r[0].q0==sel.r[0].q0 && sp->r[0].q1>sel.r[0].q1))
6957dd7cddfSDavid du Colombier 		sel = *sp;
6967dd7cddfSDavid du Colombier }
6977dd7cddfSDavid du Colombier 
6987dd7cddfSDavid du Colombier int
rxbexecute(Text * t,uint startp,Rangeset * rp)6997dd7cddfSDavid du Colombier rxbexecute(Text *t, uint startp, Rangeset *rp)
7007dd7cddfSDavid du Colombier {
7017dd7cddfSDavid du Colombier 	int flag;
7027dd7cddfSDavid du Colombier 	Inst *inst;
7037dd7cddfSDavid du Colombier 	Ilist *tlp;
7047dd7cddfSDavid du Colombier 	int p;
7057dd7cddfSDavid du Colombier 	int nnl, ntl;
7067dd7cddfSDavid du Colombier 	int c;
7077dd7cddfSDavid du Colombier 	int wrapped;
7087dd7cddfSDavid du Colombier 	int startchar;
7097dd7cddfSDavid du Colombier 
7107dd7cddfSDavid du Colombier 	flag = 0;
7117dd7cddfSDavid du Colombier 	nnl = 0;
7127dd7cddfSDavid du Colombier 	wrapped = 0;
7137dd7cddfSDavid du Colombier 	p = startp;
7147dd7cddfSDavid du Colombier 	startchar = 0;
7157dd7cddfSDavid du Colombier 	if(bstartinst->type<OPERATOR)
7167dd7cddfSDavid du Colombier 		startchar = bstartinst->type;
7177dd7cddfSDavid du Colombier 	list[0][0].inst = list[1][0].inst = nil;
7187dd7cddfSDavid du Colombier 	sel.r[0].q0= -1;
7197dd7cddfSDavid du Colombier 	/* Execute machine once for each character, including terminal NUL */
7207dd7cddfSDavid du Colombier 	for(;;--p){
7217dd7cddfSDavid du Colombier 	doloop:
7227dd7cddfSDavid du Colombier 		if(p <= 0){
7237dd7cddfSDavid du Colombier 			switch(wrapped++){
7247dd7cddfSDavid du Colombier 			case 0:		/* let loop run one more click */
7257dd7cddfSDavid du Colombier 			case 2:
7267dd7cddfSDavid du Colombier 				break;
7277dd7cddfSDavid du Colombier 			case 1:		/* expired; wrap to end */
7287dd7cddfSDavid du Colombier 				if(sel.r[0].q0>=0)
7297dd7cddfSDavid du Colombier 					goto Return;
7307dd7cddfSDavid du Colombier 				list[0][0].inst = list[1][0].inst = nil;
7317dd7cddfSDavid du Colombier 				p = t->file->nc;
7327dd7cddfSDavid du Colombier 				goto doloop;
7337dd7cddfSDavid du Colombier 			case 3:
7347dd7cddfSDavid du Colombier 			default:
7357dd7cddfSDavid du Colombier 				goto Return;
7367dd7cddfSDavid du Colombier 			}
7377dd7cddfSDavid du Colombier 			c = 0;
7387dd7cddfSDavid du Colombier 		}else{
7397dd7cddfSDavid du Colombier 			if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
7407dd7cddfSDavid du Colombier 				break;
7417dd7cddfSDavid du Colombier 			c = textreadc(t, p-1);
7427dd7cddfSDavid du Colombier 		}
7437dd7cddfSDavid du Colombier 		/* fast check for first char */
7447dd7cddfSDavid du Colombier 		if(startchar && nnl==0 && c!=startchar)
7457dd7cddfSDavid du Colombier 			continue;
7467dd7cddfSDavid du Colombier 		tl = list[flag];
7477dd7cddfSDavid du Colombier 		nl = list[flag^=1];
7487dd7cddfSDavid du Colombier 		nl->inst = nil;
7497dd7cddfSDavid du Colombier 		ntl = nnl;
7507dd7cddfSDavid du Colombier 		nnl = 0;
7517dd7cddfSDavid du Colombier 		if(sel.r[0].q0<0 && (!wrapped || p>startp)){
7527dd7cddfSDavid du Colombier 			/* Add first instruction to this list */
753e6dcbf51SDavid du Colombier 			/* the minus is so the optimizations in addinst work */
754e6dcbf51SDavid du Colombier 			sempty.r[0].q0 = -p;
755e6dcbf51SDavid du Colombier 			if(addinst(tl, bstartinst, &sempty))
7567dd7cddfSDavid du Colombier 			if(++ntl >= NLIST){
7577dd7cddfSDavid du Colombier 	Overflow:
7587dd7cddfSDavid du Colombier 				warning(nil, "regexp list overflow\n");
7597dd7cddfSDavid du Colombier 				sel.r[0].q0 = -1;
7607dd7cddfSDavid du Colombier 				goto Return;
7617dd7cddfSDavid du Colombier 			}
7627dd7cddfSDavid du Colombier 		}
7637dd7cddfSDavid du Colombier 		/* Execute machine until this list is empty */
7647dd7cddfSDavid du Colombier 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
7657dd7cddfSDavid du Colombier 	Switchstmt:
7667dd7cddfSDavid du Colombier 			switch(inst->type){
7677dd7cddfSDavid du Colombier 			default:	/* regular character */
7687dd7cddfSDavid du Colombier 				if(inst->type == c){
7697dd7cddfSDavid du Colombier 	Addinst:
770e6dcbf51SDavid du Colombier 					if(addinst(nl, inst->next, &tlp->se))
7717dd7cddfSDavid du Colombier 					if(++nnl >= NLIST)
7727dd7cddfSDavid du Colombier 						goto Overflow;
7737dd7cddfSDavid du Colombier 				}
7747dd7cddfSDavid du Colombier 				break;
7757dd7cddfSDavid du Colombier 			case LBRA:
7767dd7cddfSDavid du Colombier 				if(inst->subid>=0)
7777dd7cddfSDavid du Colombier 					tlp->se.r[inst->subid].q0 = p;
7787dd7cddfSDavid du Colombier 				inst = inst->next;
7797dd7cddfSDavid du Colombier 				goto Switchstmt;
7807dd7cddfSDavid du Colombier 			case RBRA:
7817dd7cddfSDavid du Colombier 				if(inst->subid >= 0)
7827dd7cddfSDavid du Colombier 					tlp->se.r[inst->subid].q1 = p;
7837dd7cddfSDavid du Colombier 				inst = inst->next;
7847dd7cddfSDavid du Colombier 				goto Switchstmt;
7857dd7cddfSDavid du Colombier 			case ANY:
7867dd7cddfSDavid du Colombier 				if(c != '\n')
7877dd7cddfSDavid du Colombier 					goto Addinst;
7887dd7cddfSDavid du Colombier 				break;
7897dd7cddfSDavid du Colombier 			case BOL:
7907dd7cddfSDavid du Colombier 				if(c=='\n' || p==0){
7917dd7cddfSDavid du Colombier 	Step:
7927dd7cddfSDavid du Colombier 					inst = inst->next;
7937dd7cddfSDavid du Colombier 					goto Switchstmt;
7947dd7cddfSDavid du Colombier 				}
7957dd7cddfSDavid du Colombier 				break;
7967dd7cddfSDavid du Colombier 			case EOL:
7977dd7cddfSDavid du Colombier 				if(p<t->file->nc && textreadc(t, p)=='\n')
7987dd7cddfSDavid du Colombier 					goto Step;
7997dd7cddfSDavid du Colombier 				break;
8007dd7cddfSDavid du Colombier 			case CCLASS:
8017dd7cddfSDavid du Colombier 				if(c>0 && classmatch(inst->class, c, 0))
8027dd7cddfSDavid du Colombier 					goto Addinst;
8037dd7cddfSDavid du Colombier 				break;
8047dd7cddfSDavid du Colombier 			case NCCLASS:
8057dd7cddfSDavid du Colombier 				if(c>0 && classmatch(inst->class, c, 1))
8067dd7cddfSDavid du Colombier 					goto Addinst;
8077dd7cddfSDavid du Colombier 				break;
8087dd7cddfSDavid du Colombier 			case OR:
8097dd7cddfSDavid du Colombier 				/* evaluate right choice later */
810e6dcbf51SDavid du Colombier 				if(addinst(tl, inst->right, &tlp->se))
8117dd7cddfSDavid du Colombier 				if(++ntl >= NLIST)
8127dd7cddfSDavid du Colombier 					goto Overflow;
8137dd7cddfSDavid du Colombier 				/* efficiency: advance and re-evaluate */
8147dd7cddfSDavid du Colombier 				inst = inst->left;
8157dd7cddfSDavid du Colombier 				goto Switchstmt;
8167dd7cddfSDavid du Colombier 			case END:	/* Match! */
8177dd7cddfSDavid du Colombier 				tlp->se.r[0].q0 = -tlp->se.r[0].q0; /* minus sign */
8187dd7cddfSDavid du Colombier 				tlp->se.r[0].q1 = p;
8197dd7cddfSDavid du Colombier 				bnewmatch(&tlp->se);
8207dd7cddfSDavid du Colombier 				break;
8217dd7cddfSDavid du Colombier 			}
8227dd7cddfSDavid du Colombier 		}
8237dd7cddfSDavid du Colombier 	}
8247dd7cddfSDavid du Colombier     Return:
8257dd7cddfSDavid du Colombier 	*rp = sel;
8267dd7cddfSDavid du Colombier 	return sel.r[0].q0 >= 0;
8277dd7cddfSDavid du Colombier }
8287dd7cddfSDavid du Colombier 
8297dd7cddfSDavid du Colombier void
bnewmatch(Rangeset * sp)8307dd7cddfSDavid du Colombier bnewmatch(Rangeset *sp)
8317dd7cddfSDavid du Colombier {
8327dd7cddfSDavid du Colombier         int  i;
8337dd7cddfSDavid du Colombier 
8347dd7cddfSDavid du Colombier         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))
8357dd7cddfSDavid du Colombier                 for(i = 0; i<NRange; i++){       /* note the reversal; q0<=q1 */
8367dd7cddfSDavid du Colombier                         sel.r[i].q0 = sp->r[i].q1;
8377dd7cddfSDavid du Colombier                         sel.r[i].q1 = sp->r[i].q0;
8387dd7cddfSDavid du Colombier                 }
8397dd7cddfSDavid du Colombier }
840