1 #include	"grep.h"
2 
3 /*
4  * incremental compiler.
5  * add the branch c to the
6  * state s.
7  */
8 void
9 increment(State *s, int c)
10 {
11 	int i;
12 	State *t, **tt;
13 	Re *re1, *re2;
14 
15 	nfollow = 0;
16 	gen++;
17 	matched = 0;
18 	for(i=0; i<s->count; i++)
19 		fol1(s->re[i], c);
20 	qsort(follow, nfollow, sizeof(*follow), fcmp);
21 	for(tt=&state0; t = *tt;) {
22 		if(t->count > nfollow) {
23 			tt = &t->linkleft;
24 			goto cont;
25 		}
26 		if(t->count < nfollow) {
27 			tt = &t->linkright;
28 			goto cont;
29 		}
30 		for(i=0; i<nfollow; i++) {
31 			re1 = t->re[i];
32 			re2 = follow[i];
33 			if(re1 > re2) {
34 				tt = &t->linkleft;
35 				goto cont;
36 			}
37 			if(re1 < re2) {
38 				tt = &t->linkright;
39 				goto cont;
40 			}
41 		}
42 		if(!!matched && !t->match) {
43 			tt = &t->linkleft;
44 			goto cont;
45 		}
46 		if(!matched && !!t->match) {
47 			tt = &t->linkright;
48 			goto cont;
49 		}
50 		s->next[c] = t;
51 		return;
52 	cont:;
53 	}
54 
55 	t = sal(nfollow);
56 	*tt = t;
57 	for(i=0; i<nfollow; i++) {
58 		re1 = follow[i];
59 		t->re[i] = re1;
60 	}
61 	s->next[c] = t;
62 	t->match = matched;
63 }
64 
65 int
66 fcmp(const void *va, const void *vb)
67 {
68 	Re **aa, **bb;
69 	Re *a, *b;
70 
71 	aa = (Re**)va;
72 	bb = (Re**)vb;
73 	a = *aa;
74 	b = *bb;
75 	if(a > b)
76 		return 1;
77 	if(a < b)
78 		return -1;
79 	return 0;
80 }
81 
82 void
83 fol1(Re *r, int c)
84 {
85 	Re *r1;
86 
87 loop:
88 	if(r->gen == gen)
89 		return;
90 	if(nfollow >= maxfollow)
91 		error("nfollow");
92 	r->gen = gen;
93 	switch(r->type) {
94 	default:
95 		error("fol1");
96 
97 	case Tcase:
98 		if(c >= 0 && c < 256)
99 		if(r1 = r->u.cases[c])
100 			follow[nfollow++] = r1;
101 		if(r = r->next)
102 			goto loop;
103 		break;
104 
105 	case Talt:
106 	case Tor:
107 		fol1(r->u.alt, c);
108 		r = r->next;
109 		goto loop;
110 
111 	case Tbegin:
112 		if(c == '\n' || c == Cbegin)
113 			follow[nfollow++] = r->next;
114 		break;
115 
116 	case Tend:
117 		if(c == '\n')
118 			matched = 1;
119 		break;
120 
121 	case Tclass:
122 		if(c >= r->u.x.lo && c <= r->u.x.hi)
123 			follow[nfollow++] = r->next;
124 		break;
125 	}
126 }
127 
128 Rune	tab1[] =
129 {
130 	0x007f,
131 	0x07ff
132 };
133 Rune	tab2[] =
134 {
135 	0x003f,
136 	0x0fff
137 };
138 
139 Re2
140 rclass(Rune p0, Rune p1)
141 {
142 	char xc0[6], xc1[6];
143 	int i, n, m;
144 	Re2 x;
145 
146 	if(p0 > p1)
147 		return re2char(0xff, 0xff);	/* no match */
148 
149 	/*
150 	 * bust range into same length
151 	 * character sequences
152 	 */
153 	for(i=0; i<nelem(tab1); i++) {
154 		m = tab1[i];
155 		if(p0 <= m && p1 > m)
156 			return re2or(rclass(p0, m), rclass(m+1, p1));
157 	}
158 
159 	/*
160 	 * bust range into part of a single page
161 	 * or into full pages
162 	 */
163 	for(i=0; i<nelem(tab2); i++) {
164 		m = tab2[i];
165 		if((p0 & ~m) != (p1 & ~m)) {
166 			if((p0 & m) != 0)
167 				return re2or(rclass(p0, p0|m), rclass((p0|m)+1, p1));
168 			if((p1 & m) != m)
169 				return re2or(rclass(p0, (p1&~m)-1), rclass(p1&~m, p1));
170 		}
171 	}
172 
173 	n = runetochar(xc0, &p0);
174 	i = runetochar(xc1, &p1);
175 	if(i != n)
176 		error("length");
177 
178 	x = re2char(xc0[0], xc1[0]);
179 	for(i=1; i<n; i++)
180 		x = re2cat(x, re2char(xc0[i], xc1[i]));
181 	return x;
182 }
183 
184 int
185 pcmp(const void *va, const void *vb)
186 {
187 	int n;
188 	Rune *a, *b;
189 
190 	a = (Rune*)va;
191 	b = (Rune*)vb;
192 
193 	n = a[0] - b[0];
194 	if(n)
195 		return n;
196 	return a[1] - b[1];
197 }
198 
199 /*
200  * convert character chass into
201  * run-pair ranges of matches.
202  * this is 10646/utf specific and
203  * needs to be changed for some
204  * other input character set.
205  * this is the key to a fast
206  * regular search of characters
207  * by looking at sequential bytes.
208  */
209 Re2
210 re2class(char *s)
211 {
212 	Rune pairs[200], *p, *q, ov;
213 	int nc;
214 	Re2 x;
215 
216 	nc = 0;
217 	if(*s == '^') {
218 		nc = 1;
219 		s++;
220 	}
221 
222 	p = pairs;
223 	s += chartorune(p, s);
224 	for(;;) {
225 		if(*p == '\\')
226 			s += chartorune(p, s);
227 		if(*p == 0)
228 			break;
229 		p[1] = *p;
230 		p += 2;
231 		s += chartorune(p, s);
232 		if(*p != '-')
233 			continue;
234 		s += chartorune(p, s);
235 		if(*p == '\\')
236 			s += chartorune(p, s);
237 		if(*p == 0)
238 			break;
239 		p[-1] = *p;
240 		s += chartorune(p, s);
241 	}
242 	*p = 0;
243 	qsort(pairs, (p-pairs)/2, 2*sizeof(*pairs), pcmp);
244 
245 	q = pairs;
246 	for(p=pairs+2; *p; p+=2) {
247 		if(p[0] > p[1])
248 			continue;
249 		if(p[0] > q[1] || p[1] < q[0]) {
250 			q[2] = p[0];
251 			q[3] = p[1];
252 			q += 2;
253 			continue;
254 		}
255 		if(p[0] < q[0])
256 			q[0] = p[0];
257 		if(p[1] > q[1])
258 			q[1] = p[1];
259 	}
260 	q[2] = 0;
261 
262 	p = pairs;
263 	if(nc) {
264 		x = rclass(0, p[0]-1);
265 		ov = p[1]+1;
266 		for(p+=2; *p; p+=2) {
267 			x = re2or(x, rclass(ov, p[0]-1));
268 			ov = p[1]+1;
269 		}
270 		x = re2or(x, rclass(ov, 0xffff));
271 	} else {
272 		x = rclass(p[0], p[1]);
273 		for(p+=2; *p; p+=2)
274 			x = re2or(x, rclass(p[0], p[1]));
275 	}
276 	return x;
277 }