1 b2cfc4e2 2003-09-30 devnull #include "lib9.h"
  2 b2cfc4e2 2003-09-30 devnull #include "regexp9.h"
  3 b2cfc4e2 2003-09-30 devnull #include "regcomp.h"
  4 b2cfc4e2 2003-09-30 devnull 
  5 b2cfc4e2 2003-09-30 devnull /*
  6 b2cfc4e2 2003-09-30 devnull  *  return	0 if no match
  7 b2cfc4e2 2003-09-30 devnull  *		>0 if a match
  8 b2cfc4e2 2003-09-30 devnull  *		<0 if we ran out of _relist space
  9 b2cfc4e2 2003-09-30 devnull  */
 10 b2cfc4e2 2003-09-30 devnull static int
 11 b2cfc4e2 2003-09-30 devnull rregexec1(Reprog *progp,	/* program to run */
 12 b2cfc4e2 2003-09-30 devnull 	Rune *bol,		/* string to run machine on */
 13 b2cfc4e2 2003-09-30 devnull 	Resub *mp,		/* subexpression elements */
 14 b2cfc4e2 2003-09-30 devnull 	int ms,			/* number of elements at mp */
 15 b2cfc4e2 2003-09-30 devnull 	Reljunk *j)
 16 b2cfc4e2 2003-09-30 devnull {
 17 b2cfc4e2 2003-09-30 devnull 	int flag=0;
 18 b2cfc4e2 2003-09-30 devnull 	Reinst *inst;
 19 b2cfc4e2 2003-09-30 devnull 	Relist *tlp;
 20 b2cfc4e2 2003-09-30 devnull 	Rune *s;
 21 b2cfc4e2 2003-09-30 devnull 	int i, checkstart;
 22 b2cfc4e2 2003-09-30 devnull 	Rune r, *rp, *ep;
 23 b2cfc4e2 2003-09-30 devnull 	Relist* tl;		/* This list, next list */
 24 b2cfc4e2 2003-09-30 devnull 	Relist* nl;
 25 b2cfc4e2 2003-09-30 devnull 	Relist* tle;		/* ends of this and next list */
 26 b2cfc4e2 2003-09-30 devnull 	Relist* nle;
 27 b2cfc4e2 2003-09-30 devnull 	int match;
 28 b2cfc4e2 2003-09-30 devnull 
 29 b2cfc4e2 2003-09-30 devnull 	match = 0;
 30 b2cfc4e2 2003-09-30 devnull 	checkstart = j->startchar;
 31 b2cfc4e2 2003-09-30 devnull 	if(mp)
 32 b2cfc4e2 2003-09-30 devnull 		for(i=0; i<ms; i++) {
 33 b2cfc4e2 2003-09-30 devnull 			mp[i].s.rsp = 0;
 34 b2cfc4e2 2003-09-30 devnull 			mp[i].e.rep = 0;
 35 b2cfc4e2 2003-09-30 devnull 		}
 36 b2cfc4e2 2003-09-30 devnull 	j->relist[0][0].inst = 0;
 37 b2cfc4e2 2003-09-30 devnull 	j->relist[1][0].inst = 0;
 38 b2cfc4e2 2003-09-30 devnull 
 39 b2cfc4e2 2003-09-30 devnull 	/* Execute machine once for each character, including terminal NUL */
 40 b2cfc4e2 2003-09-30 devnull 	s = j->rstarts;
 41 b2cfc4e2 2003-09-30 devnull 	do{
 42 b2cfc4e2 2003-09-30 devnull 
 43 b2cfc4e2 2003-09-30 devnull 		/* fast check for first char */
 44 b2cfc4e2 2003-09-30 devnull 		if(checkstart) {
 45 b2cfc4e2 2003-09-30 devnull 			switch(j->starttype) {
 46 b2cfc4e2 2003-09-30 devnull 			case RUNE:
 47 b2cfc4e2 2003-09-30 devnull 				while(*s != j->startchar) {
 48 62390091 2004-03-05 devnull 					if(*s == 0 || s == j->reol)
 49 b2cfc4e2 2003-09-30 devnull 						return match;
 50 b2cfc4e2 2003-09-30 devnull 					s++;
 51 b2cfc4e2 2003-09-30 devnull 				}
 52 b2cfc4e2 2003-09-30 devnull 				break;
 53 b2cfc4e2 2003-09-30 devnull 			case BOL:
 54 b2cfc4e2 2003-09-30 devnull 				if(s == bol)
 55 b2cfc4e2 2003-09-30 devnull 					break;
 56 b2cfc4e2 2003-09-30 devnull 				while(*s != '\n') {
 57 62390091 2004-03-05 devnull 					if(*s == 0 || s == j->reol)
 58 b2cfc4e2 2003-09-30 devnull 						return match;
 59 b2cfc4e2 2003-09-30 devnull 					s++;
 60 b2cfc4e2 2003-09-30 devnull 				}
 61 b2cfc4e2 2003-09-30 devnull 				break;
 62 b2cfc4e2 2003-09-30 devnull 			}
 63 b2cfc4e2 2003-09-30 devnull 		}
 64 b2cfc4e2 2003-09-30 devnull 
 65 b2cfc4e2 2003-09-30 devnull 		r = *s;
 66 b2cfc4e2 2003-09-30 devnull 
 67 b2cfc4e2 2003-09-30 devnull 		/* switch run lists */
 68 b2cfc4e2 2003-09-30 devnull 		tl = j->relist[flag];
 69 b2cfc4e2 2003-09-30 devnull 		tle = j->reliste[flag];
 70 b2cfc4e2 2003-09-30 devnull 		nl = j->relist[flag^=1];
 71 b2cfc4e2 2003-09-30 devnull 		nle = j->reliste[flag];
 72 b2cfc4e2 2003-09-30 devnull 		nl->inst = 0;
 73 b2cfc4e2 2003-09-30 devnull 
 74 b2cfc4e2 2003-09-30 devnull 		/* Add first instruction to current list */
 75 62390091 2004-03-05 devnull 		_rrenewemptythread(tl, progp->startinst, ms, s);
 76 b2cfc4e2 2003-09-30 devnull 
 77 b2cfc4e2 2003-09-30 devnull 		/* Execute machine until current list is empty */
 78 b2cfc4e2 2003-09-30 devnull 		for(tlp=tl; tlp->inst; tlp++){
 79 b2cfc4e2 2003-09-30 devnull 			for(inst=tlp->inst; ; inst = inst->u2.next){
 80 b2cfc4e2 2003-09-30 devnull 				switch(inst->type){
 81 b2cfc4e2 2003-09-30 devnull 				case RUNE:	/* regular character */
 82 b2cfc4e2 2003-09-30 devnull 					if(inst->u1.r == r)
 83 62390091 2004-03-05 devnull 						if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
 84 b2cfc4e2 2003-09-30 devnull 							return -1;
 85 b2cfc4e2 2003-09-30 devnull 					break;
 86 b2cfc4e2 2003-09-30 devnull 				case LBRA:
 87 b2cfc4e2 2003-09-30 devnull 					tlp->se.m[inst->u1.subid].s.rsp = s;
 88 b2cfc4e2 2003-09-30 devnull 					continue;
 89 b2cfc4e2 2003-09-30 devnull 				case RBRA:
 90 b2cfc4e2 2003-09-30 devnull 					tlp->se.m[inst->u1.subid].e.rep = s;
 91 b2cfc4e2 2003-09-30 devnull 					continue;
 92 b2cfc4e2 2003-09-30 devnull 				case ANY:
 93 b2cfc4e2 2003-09-30 devnull 					if(r != '\n')
 94 62390091 2004-03-05 devnull 						if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
 95 b2cfc4e2 2003-09-30 devnull 							return -1;
 96 b2cfc4e2 2003-09-30 devnull 					break;
 97 b2cfc4e2 2003-09-30 devnull 				case ANYNL:
 98 62390091 2004-03-05 devnull 					if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
 99 b2cfc4e2 2003-09-30 devnull 							return -1;
100 b2cfc4e2 2003-09-30 devnull 					break;
101 b2cfc4e2 2003-09-30 devnull 				case BOL:
102 b2cfc4e2 2003-09-30 devnull 					if(s == bol || *(s-1) == '\n')
103 b2cfc4e2 2003-09-30 devnull 						continue;
104 b2cfc4e2 2003-09-30 devnull 					break;
105 b2cfc4e2 2003-09-30 devnull 				case EOL:
106 b2cfc4e2 2003-09-30 devnull 					if(s == j->reol || r == 0 || r == '\n')
107 b2cfc4e2 2003-09-30 devnull 						continue;
108 b2cfc4e2 2003-09-30 devnull 					break;
109 b2cfc4e2 2003-09-30 devnull 				case CCLASS:
110 b2cfc4e2 2003-09-30 devnull 					ep = inst->u1.cp->end;
111 b2cfc4e2 2003-09-30 devnull 					for(rp = inst->u1.cp->spans; rp < ep; rp += 2)
112 b2cfc4e2 2003-09-30 devnull 						if(r >= rp[0] && r <= rp[1]){
113 62390091 2004-03-05 devnull 							if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
114 b2cfc4e2 2003-09-30 devnull 								return -1;
115 b2cfc4e2 2003-09-30 devnull 							break;
116 b2cfc4e2 2003-09-30 devnull 						}
117 b2cfc4e2 2003-09-30 devnull 					break;
118 b2cfc4e2 2003-09-30 devnull 				case NCCLASS:
119 b2cfc4e2 2003-09-30 devnull 					ep = inst->u1.cp->end;
120 b2cfc4e2 2003-09-30 devnull 					for(rp = inst->u1.cp->spans; rp < ep; rp += 2)
121 b2cfc4e2 2003-09-30 devnull 						if(r >= rp[0] && r <= rp[1])
122 b2cfc4e2 2003-09-30 devnull 							break;
123 b2cfc4e2 2003-09-30 devnull 					if(rp == ep)
124 62390091 2004-03-05 devnull 						if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
125 b2cfc4e2 2003-09-30 devnull 							return -1;
126 b2cfc4e2 2003-09-30 devnull 					break;
127 b2cfc4e2 2003-09-30 devnull 				case OR:
128 b2cfc4e2 2003-09-30 devnull 					/* evaluate right choice later */
129 62390091 2004-03-05 devnull 					if(_renewthread(tlp, inst->u1.right, ms, &tlp->se) == tle)
130 b2cfc4e2 2003-09-30 devnull 						return -1;
131 b2cfc4e2 2003-09-30 devnull 					/* efficiency: advance and re-evaluate */
132 b2cfc4e2 2003-09-30 devnull 					continue;
133 b2cfc4e2 2003-09-30 devnull 				case END:	/* Match! */
134 b2cfc4e2 2003-09-30 devnull 					match = 1;
135 b2cfc4e2 2003-09-30 devnull 					tlp->se.m[0].e.rep = s;
136 b2cfc4e2 2003-09-30 devnull 					if(mp != 0)
137 b2cfc4e2 2003-09-30 devnull 						_renewmatch(mp, ms, &tlp->se);
138 b2cfc4e2 2003-09-30 devnull 					break;
139 b2cfc4e2 2003-09-30 devnull 				}
140 b2cfc4e2 2003-09-30 devnull 				break;
141 b2cfc4e2 2003-09-30 devnull 			}
142 b2cfc4e2 2003-09-30 devnull 		}
143 b2cfc4e2 2003-09-30 devnull 		if(s == j->reol)
144 b2cfc4e2 2003-09-30 devnull 			break;
145 b2cfc4e2 2003-09-30 devnull 		checkstart = j->startchar && nl->inst==0;
146 b2cfc4e2 2003-09-30 devnull 		s++;
147 b2cfc4e2 2003-09-30 devnull 	}while(r);
148 b2cfc4e2 2003-09-30 devnull 	return match;
149 b2cfc4e2 2003-09-30 devnull }
150 b2cfc4e2 2003-09-30 devnull 
151 b2cfc4e2 2003-09-30 devnull static int
152 b2cfc4e2 2003-09-30 devnull rregexec2(Reprog *progp,	/* program to run */
153 b2cfc4e2 2003-09-30 devnull 	Rune *bol,	/* string to run machine on */
154 b2cfc4e2 2003-09-30 devnull 	Resub *mp,	/* subexpression elements */
155 b2cfc4e2 2003-09-30 devnull 	int ms,		/* number of elements at mp */
156 b2cfc4e2 2003-09-30 devnull 	Reljunk *j
157 b2cfc4e2 2003-09-30 devnull )
158 b2cfc4e2 2003-09-30 devnull {
159 b2cfc4e2 2003-09-30 devnull 	Relist relist0[5*LISTSIZE], relist1[5*LISTSIZE];
160 b2cfc4e2 2003-09-30 devnull 
161 b2cfc4e2 2003-09-30 devnull 	/* mark space */
162 b2cfc4e2 2003-09-30 devnull 	j->relist[0] = relist0;
163 b2cfc4e2 2003-09-30 devnull 	j->relist[1] = relist1;
164 b2cfc4e2 2003-09-30 devnull 	j->reliste[0] = relist0 + nelem(relist0) - 2;
165 b2cfc4e2 2003-09-30 devnull 	j->reliste[1] = relist1 + nelem(relist1) - 2;
166 b2cfc4e2 2003-09-30 devnull 
167 b2cfc4e2 2003-09-30 devnull 	return rregexec1(progp, bol, mp, ms, j);
168 b2cfc4e2 2003-09-30 devnull }
169 b2cfc4e2 2003-09-30 devnull 
170 b2cfc4e2 2003-09-30 devnull extern int
171 b2cfc4e2 2003-09-30 devnull rregexec(Reprog *progp,	/* program to run */
172 b2cfc4e2 2003-09-30 devnull 	Rune *bol,	/* string to run machine on */
173 b2cfc4e2 2003-09-30 devnull 	Resub *mp,	/* subexpression elements */
174 b2cfc4e2 2003-09-30 devnull 	int ms)		/* number of elements at mp */
175 b2cfc4e2 2003-09-30 devnull {
176 b2cfc4e2 2003-09-30 devnull 	Reljunk j;
177 b2cfc4e2 2003-09-30 devnull 	Relist relist0[LISTSIZE], relist1[LISTSIZE];
178 b2cfc4e2 2003-09-30 devnull 	int rv;
179 b2cfc4e2 2003-09-30 devnull 
180 b2cfc4e2 2003-09-30 devnull 	/*
181 b2cfc4e2 2003-09-30 devnull  	 *  use user-specified starting/ending location if specified
182 b2cfc4e2 2003-09-30 devnull 	 */
183 b2cfc4e2 2003-09-30 devnull 	j.rstarts = bol;
184 b2cfc4e2 2003-09-30 devnull 	j.reol = 0;
185 b2cfc4e2 2003-09-30 devnull 	if(mp && ms>0){
186 b2cfc4e2 2003-09-30 devnull 		if(mp->s.sp)
187 b2cfc4e2 2003-09-30 devnull 			j.rstarts = mp->s.rsp;
188 b2cfc4e2 2003-09-30 devnull 		if(mp->e.ep)
189 b2cfc4e2 2003-09-30 devnull 			j.reol = mp->e.rep;
190 b2cfc4e2 2003-09-30 devnull 	}
191 b2cfc4e2 2003-09-30 devnull 	j.starttype = 0;
192 b2cfc4e2 2003-09-30 devnull 	j.startchar = 0;
193 62390091 2004-03-05 devnull 	if(progp->startinst->type == RUNE && progp->startinst->u1.r < Runeself) {
194 b2cfc4e2 2003-09-30 devnull 		j.starttype = RUNE;
195 b2cfc4e2 2003-09-30 devnull 		j.startchar = progp->startinst->u1.r;
196 b2cfc4e2 2003-09-30 devnull 	}
197 b2cfc4e2 2003-09-30 devnull 	if(progp->startinst->type == BOL)
198 b2cfc4e2 2003-09-30 devnull 		j.starttype = BOL;
199 b2cfc4e2 2003-09-30 devnull 
200 b2cfc4e2 2003-09-30 devnull 	/* mark space */
201 b2cfc4e2 2003-09-30 devnull 	j.relist[0] = relist0;
202 b2cfc4e2 2003-09-30 devnull 	j.relist[1] = relist1;
203 b2cfc4e2 2003-09-30 devnull 	j.reliste[0] = relist0 + nelem(relist0) - 2;
204 b2cfc4e2 2003-09-30 devnull 	j.reliste[1] = relist1 + nelem(relist1) - 2;
205 b2cfc4e2 2003-09-30 devnull 
206 b2cfc4e2 2003-09-30 devnull 	rv = rregexec1(progp, bol, mp, ms, &j);
207 b2cfc4e2 2003-09-30 devnull 	if(rv >= 0)
208 b2cfc4e2 2003-09-30 devnull 		return rv;
209 b2cfc4e2 2003-09-30 devnull 	rv = rregexec2(progp, bol, mp, ms, &j);
210 b2cfc4e2 2003-09-30 devnull 	if(rv >= 0)
211 b2cfc4e2 2003-09-30 devnull 		return rv;
212 b2cfc4e2 2003-09-30 devnull 	return -1;
213 b2cfc4e2 2003-09-30 devnull }