1 8ad51794 2004-03-25 devnull #include	"grep.h"
  2 8ad51794 2004-03-25 devnull 
  3 8ad51794 2004-03-25 devnull void*
  4 8ad51794 2004-03-25 devnull mal(int n)
  5 8ad51794 2004-03-25 devnull {
  6 8ad51794 2004-03-25 devnull 	static char *s;
  7 8ad51794 2004-03-25 devnull 	static int m = 0;
  8 8ad51794 2004-03-25 devnull 	void *v;
  9 8ad51794 2004-03-25 devnull 
 10 8ad51794 2004-03-25 devnull 	n = (n+3) & ~3;
 11 8ad51794 2004-03-25 devnull 	if(m < n) {
 12 8ad51794 2004-03-25 devnull 		if(n > Nhunk) {
 13 8ad51794 2004-03-25 devnull 			v = sbrk(n);
 14 8ad51794 2004-03-25 devnull 			memset(v, 0, n);
 15 8ad51794 2004-03-25 devnull 			return v;
 16 8ad51794 2004-03-25 devnull 		}
 17 8ad51794 2004-03-25 devnull 		s = sbrk(Nhunk);
 18 8ad51794 2004-03-25 devnull 		m = Nhunk;
 19 8ad51794 2004-03-25 devnull 	}
 20 8ad51794 2004-03-25 devnull 	v = s;
 21 8ad51794 2004-03-25 devnull 	s += n;
 22 8ad51794 2004-03-25 devnull 	m -= n;
 23 8ad51794 2004-03-25 devnull 	memset(v, 0, n);
 24 8ad51794 2004-03-25 devnull 	return v;
 25 8ad51794 2004-03-25 devnull }
 26 8ad51794 2004-03-25 devnull 
 27 8ad51794 2004-03-25 devnull State*
 28 8ad51794 2004-03-25 devnull sal(int n)
 29 8ad51794 2004-03-25 devnull {
 30 8ad51794 2004-03-25 devnull 	State *s;
 31 8ad51794 2004-03-25 devnull 
 32 8ad51794 2004-03-25 devnull 	s = mal(sizeof(*s));
 33 cbeb0b26 2006-04-01 devnull /*	s->next = mal(256*sizeof(*s->next)); */
 34 8ad51794 2004-03-25 devnull 	s->count = n;
 35 8ad51794 2004-03-25 devnull 	s->re = mal(n*sizeof(*state0->re));
 36 8ad51794 2004-03-25 devnull 	return s;
 37 8ad51794 2004-03-25 devnull }
 38 8ad51794 2004-03-25 devnull 
 39 8ad51794 2004-03-25 devnull Re*
 40 8ad51794 2004-03-25 devnull ral(int type)
 41 8ad51794 2004-03-25 devnull {
 42 8ad51794 2004-03-25 devnull 	Re *r;
 43 8ad51794 2004-03-25 devnull 
 44 8ad51794 2004-03-25 devnull 	r = mal(sizeof(*r));
 45 8ad51794 2004-03-25 devnull 	r->type = type;
 46 8ad51794 2004-03-25 devnull 	maxfollow++;
 47 8ad51794 2004-03-25 devnull 	return r;
 48 8ad51794 2004-03-25 devnull }
 49 8ad51794 2004-03-25 devnull 
 50 8ad51794 2004-03-25 devnull void
 51 8ad51794 2004-03-25 devnull error(char *s)
 52 8ad51794 2004-03-25 devnull {
 53 8ad51794 2004-03-25 devnull 	fprint(2, "grep: internal error: %s\n", s);
 54 8ad51794 2004-03-25 devnull 	exits(s);
 55 8ad51794 2004-03-25 devnull }
 56 8ad51794 2004-03-25 devnull 
 57 8ad51794 2004-03-25 devnull int
 58 8ad51794 2004-03-25 devnull countor(Re *r)
 59 8ad51794 2004-03-25 devnull {
 60 8ad51794 2004-03-25 devnull 	int n;
 61 8ad51794 2004-03-25 devnull 
 62 8ad51794 2004-03-25 devnull 	n = 0;
 63 8ad51794 2004-03-25 devnull loop:
 64 8ad51794 2004-03-25 devnull 	switch(r->type) {
 65 8ad51794 2004-03-25 devnull 	case Tor:
 66 285b4f85 2004-03-25 devnull 		n += countor(r->u.alt);
 67 8ad51794 2004-03-25 devnull 		r = r->next;
 68 8ad51794 2004-03-25 devnull 		goto loop;
 69 8ad51794 2004-03-25 devnull 	case Tclass:
 70 285b4f85 2004-03-25 devnull 		return n + r->u.x.hi - r->u.x.lo + 1;
 71 8ad51794 2004-03-25 devnull 	}
 72 8ad51794 2004-03-25 devnull 	return n;
 73 8ad51794 2004-03-25 devnull }
 74 8ad51794 2004-03-25 devnull 
 75 8ad51794 2004-03-25 devnull Re*
 76 8ad51794 2004-03-25 devnull oralloc(int t, Re *r, Re *b)
 77 8ad51794 2004-03-25 devnull {
 78 8ad51794 2004-03-25 devnull 	Re *a;
 79 8ad51794 2004-03-25 devnull 
 80 8ad51794 2004-03-25 devnull 	if(b == 0)
 81 8ad51794 2004-03-25 devnull 		return r;
 82 8ad51794 2004-03-25 devnull 	a = ral(t);
 83 285b4f85 2004-03-25 devnull 	a->u.alt = r;
 84 8ad51794 2004-03-25 devnull 	a->next = b;
 85 8ad51794 2004-03-25 devnull 	return a;
 86 8ad51794 2004-03-25 devnull }
 87 8ad51794 2004-03-25 devnull 
 88 8ad51794 2004-03-25 devnull void
 89 8ad51794 2004-03-25 devnull case1(Re *c, Re *r)
 90 8ad51794 2004-03-25 devnull {
 91 8ad51794 2004-03-25 devnull 	int n;
 92 8ad51794 2004-03-25 devnull 
 93 8ad51794 2004-03-25 devnull loop:
 94 8ad51794 2004-03-25 devnull 	switch(r->type) {
 95 8ad51794 2004-03-25 devnull 	case Tor:
 96 285b4f85 2004-03-25 devnull 		case1(c, r->u.alt);
 97 8ad51794 2004-03-25 devnull 		r = r->next;
 98 8ad51794 2004-03-25 devnull 		goto loop;
 99 8ad51794 2004-03-25 devnull 
100 8ad51794 2004-03-25 devnull 	case Tclass:	/* add to character */
101 285b4f85 2004-03-25 devnull 		for(n=r->u.x.lo; n<=r->u.x.hi; n++)
102 285b4f85 2004-03-25 devnull 			c->u.cases[n] = oralloc(Tor, r->next, c->u.cases[n]);
103 8ad51794 2004-03-25 devnull 		break;
104 8ad51794 2004-03-25 devnull 
105 8ad51794 2004-03-25 devnull 	default:	/* add everything unknown to next */
106 8ad51794 2004-03-25 devnull 		c->next = oralloc(Talt, r, c->next);
107 8ad51794 2004-03-25 devnull 		break;
108 8ad51794 2004-03-25 devnull 	}
109 8ad51794 2004-03-25 devnull }
110 8ad51794 2004-03-25 devnull 
111 8ad51794 2004-03-25 devnull Re*
112 8ad51794 2004-03-25 devnull addcase(Re *r)
113 8ad51794 2004-03-25 devnull {
114 8ad51794 2004-03-25 devnull 	int i, n;
115 8ad51794 2004-03-25 devnull 	Re *a;
116 8ad51794 2004-03-25 devnull 
117 8ad51794 2004-03-25 devnull 	if(r->gen == gen)
118 8ad51794 2004-03-25 devnull 		return r;
119 8ad51794 2004-03-25 devnull 	r->gen = gen;
120 8ad51794 2004-03-25 devnull 	switch(r->type) {
121 8ad51794 2004-03-25 devnull 	default:
122 8ad51794 2004-03-25 devnull 		error("addcase");
123 8ad51794 2004-03-25 devnull 
124 8ad51794 2004-03-25 devnull 	case Tor:
125 8ad51794 2004-03-25 devnull 		n = countor(r);
126 8ad51794 2004-03-25 devnull 		if(n >= Caselim) {
127 8ad51794 2004-03-25 devnull 			a = ral(Tcase);
128 285b4f85 2004-03-25 devnull 			a->u.cases = mal(256*sizeof(*a->u.cases));
129 8ad51794 2004-03-25 devnull 			case1(a, r);
130 8ad51794 2004-03-25 devnull 			for(i=0; i<256; i++)
131 285b4f85 2004-03-25 devnull 				if(a->u.cases[i]) {
132 285b4f85 2004-03-25 devnull 					r = a->u.cases[i];
133 8ad51794 2004-03-25 devnull 					if(countor(r) < n)
134 285b4f85 2004-03-25 devnull 						a->u.cases[i] = addcase(r);
135 8ad51794 2004-03-25 devnull 				}
136 8ad51794 2004-03-25 devnull 			return a;
137 8ad51794 2004-03-25 devnull 		}
138 8ad51794 2004-03-25 devnull 		return r;
139 8ad51794 2004-03-25 devnull 
140 8ad51794 2004-03-25 devnull 	case Talt:
141 8ad51794 2004-03-25 devnull 		r->next = addcase(r->next);
142 285b4f85 2004-03-25 devnull 		r->u.alt = addcase(r->u.alt);
143 8ad51794 2004-03-25 devnull 		return r;
144 8ad51794 2004-03-25 devnull 
145 8ad51794 2004-03-25 devnull 	case Tbegin:
146 8ad51794 2004-03-25 devnull 	case Tend:
147 8ad51794 2004-03-25 devnull 	case Tclass:
148 8ad51794 2004-03-25 devnull 		return r;
149 8ad51794 2004-03-25 devnull 	}
150 8ad51794 2004-03-25 devnull }
151 8ad51794 2004-03-25 devnull 
152 8ad51794 2004-03-25 devnull void
153 8ad51794 2004-03-25 devnull str2top(char *p)
154 8ad51794 2004-03-25 devnull {
155 8ad51794 2004-03-25 devnull 	Re2 oldtop;
156 8ad51794 2004-03-25 devnull 
157 8ad51794 2004-03-25 devnull 	oldtop = topre;
158 8ad51794 2004-03-25 devnull 	input = p;
159 8ad51794 2004-03-25 devnull 	topre.beg = 0;
160 8ad51794 2004-03-25 devnull 	topre.end = 0;
161 8ad51794 2004-03-25 devnull 	yyparse();
162 8ad51794 2004-03-25 devnull 	gen++;
163 8ad51794 2004-03-25 devnull 	if(topre.beg == 0)
164 8ad51794 2004-03-25 devnull 		yyerror("syntax");
165 8ad51794 2004-03-25 devnull 	if(oldtop.beg)
166 8ad51794 2004-03-25 devnull 		topre = re2or(oldtop, topre);
167 8ad51794 2004-03-25 devnull }
168 8ad51794 2004-03-25 devnull 
169 8ad51794 2004-03-25 devnull void
170 8ad51794 2004-03-25 devnull appendnext(Re *a, Re *b)
171 8ad51794 2004-03-25 devnull {
172 8ad51794 2004-03-25 devnull 	Re *n;
173 8ad51794 2004-03-25 devnull 
174 8ad51794 2004-03-25 devnull 	while(n = a->next)
175 8ad51794 2004-03-25 devnull 		a = n;
176 8ad51794 2004-03-25 devnull 	a->next = b;
177 8ad51794 2004-03-25 devnull }
178 8ad51794 2004-03-25 devnull 
179 8ad51794 2004-03-25 devnull void
180 8ad51794 2004-03-25 devnull patchnext(Re *a, Re *b)
181 8ad51794 2004-03-25 devnull {
182 8ad51794 2004-03-25 devnull 	Re *n;
183 8ad51794 2004-03-25 devnull 
184 8ad51794 2004-03-25 devnull 	while(a) {
185 8ad51794 2004-03-25 devnull 		n = a->next;
186 8ad51794 2004-03-25 devnull 		a->next = b;
187 8ad51794 2004-03-25 devnull 		a = n;
188 8ad51794 2004-03-25 devnull 	}
189 8ad51794 2004-03-25 devnull }
190 8ad51794 2004-03-25 devnull 
191 8ad51794 2004-03-25 devnull int
192 8ad51794 2004-03-25 devnull getrec(void)
193 8ad51794 2004-03-25 devnull {
194 8ad51794 2004-03-25 devnull 	int c;
195 8ad51794 2004-03-25 devnull 
196 8ad51794 2004-03-25 devnull 	if(flags['f']) {
197 8ad51794 2004-03-25 devnull 		c = Bgetc(rein);
198 8ad51794 2004-03-25 devnull 		if(c <= 0)
199 8ad51794 2004-03-25 devnull 			return 0;
200 8ad51794 2004-03-25 devnull 	} else
201 8ad51794 2004-03-25 devnull 		c = *input++ & 0xff;
202 8ad51794 2004-03-25 devnull 	if(flags['i'] && c >= 'A' && c <= 'Z')
203 8ad51794 2004-03-25 devnull 		c += 'a'-'A';
204 8ad51794 2004-03-25 devnull 	if(c == '\n')
205 8ad51794 2004-03-25 devnull 		lineno++;
206 8ad51794 2004-03-25 devnull 	return c;
207 8ad51794 2004-03-25 devnull }
208 8ad51794 2004-03-25 devnull 
209 8ad51794 2004-03-25 devnull Re2
210 8ad51794 2004-03-25 devnull re2cat(Re2 a, Re2 b)
211 8ad51794 2004-03-25 devnull {
212 8ad51794 2004-03-25 devnull 	Re2 c;
213 8ad51794 2004-03-25 devnull 
214 8ad51794 2004-03-25 devnull 	c.beg = a.beg;
215 8ad51794 2004-03-25 devnull 	c.end = b.end;
216 8ad51794 2004-03-25 devnull 	patchnext(a.end, b.beg);
217 8ad51794 2004-03-25 devnull 	return c;
218 8ad51794 2004-03-25 devnull }
219 8ad51794 2004-03-25 devnull 
220 8ad51794 2004-03-25 devnull Re2
221 8ad51794 2004-03-25 devnull re2star(Re2 a)
222 8ad51794 2004-03-25 devnull {
223 8ad51794 2004-03-25 devnull 	Re2 c;
224 8ad51794 2004-03-25 devnull 
225 8ad51794 2004-03-25 devnull 	c.beg = ral(Talt);
226 285b4f85 2004-03-25 devnull 	c.beg->u.alt = a.beg;
227 8ad51794 2004-03-25 devnull 	patchnext(a.end, c.beg);
228 8ad51794 2004-03-25 devnull 	c.end = c.beg;
229 8ad51794 2004-03-25 devnull 	return c;
230 8ad51794 2004-03-25 devnull }
231 8ad51794 2004-03-25 devnull 
232 8ad51794 2004-03-25 devnull Re2
233 8ad51794 2004-03-25 devnull re2or(Re2 a, Re2 b)
234 8ad51794 2004-03-25 devnull {
235 8ad51794 2004-03-25 devnull 	Re2 c;
236 8ad51794 2004-03-25 devnull 
237 8ad51794 2004-03-25 devnull 	c.beg = ral(Tor);
238 285b4f85 2004-03-25 devnull 	c.beg->u.alt = b.beg;
239 8ad51794 2004-03-25 devnull 	c.beg->next = a.beg;
240 8ad51794 2004-03-25 devnull 	c.end = b.end;
241 8ad51794 2004-03-25 devnull 	appendnext(c.end,  a.end);
242 8ad51794 2004-03-25 devnull 	return c;
243 8ad51794 2004-03-25 devnull }
244 8ad51794 2004-03-25 devnull 
245 8ad51794 2004-03-25 devnull Re2
246 8ad51794 2004-03-25 devnull re2char(int c0, int c1)
247 8ad51794 2004-03-25 devnull {
248 8ad51794 2004-03-25 devnull 	Re2 c;
249 8ad51794 2004-03-25 devnull 
250 8ad51794 2004-03-25 devnull 	c.beg = ral(Tclass);
251 285b4f85 2004-03-25 devnull 	c.beg->u.x.lo = c0 & 0xff;
252 285b4f85 2004-03-25 devnull 	c.beg->u.x.hi = c1 & 0xff;
253 8ad51794 2004-03-25 devnull 	c.end = c.beg;
254 8ad51794 2004-03-25 devnull 	return c;
255 8ad51794 2004-03-25 devnull }
256 8ad51794 2004-03-25 devnull 
257 8ad51794 2004-03-25 devnull void
258 8ad51794 2004-03-25 devnull reprint1(Re *a)
259 8ad51794 2004-03-25 devnull {
260 8ad51794 2004-03-25 devnull 	int i, j;
261 8ad51794 2004-03-25 devnull 
262 8ad51794 2004-03-25 devnull loop:
263 8ad51794 2004-03-25 devnull 	if(a == 0)
264 8ad51794 2004-03-25 devnull 		return;
265 8ad51794 2004-03-25 devnull 	if(a->gen == gen)
266 8ad51794 2004-03-25 devnull 		return;
267 8ad51794 2004-03-25 devnull 	a->gen = gen;
268 8ad51794 2004-03-25 devnull 	print("%p: ", a);
269 8ad51794 2004-03-25 devnull 	switch(a->type) {
270 8ad51794 2004-03-25 devnull 	default:
271 8ad51794 2004-03-25 devnull 		print("type %d\n", a->type);
272 8ad51794 2004-03-25 devnull 		error("print1 type");
273 8ad51794 2004-03-25 devnull 
274 8ad51794 2004-03-25 devnull 	case Tcase:
275 8ad51794 2004-03-25 devnull 		print("case ->%p\n", a->next);
276 8ad51794 2004-03-25 devnull 		for(i=0; i<256; i++)
277 285b4f85 2004-03-25 devnull 			if(a->u.cases[i]) {
278 8ad51794 2004-03-25 devnull 				for(j=i+1; j<256; j++)
279 285b4f85 2004-03-25 devnull 					if(a->u.cases[i] != a->u.cases[j])
280 8ad51794 2004-03-25 devnull 						break;
281 285b4f85 2004-03-25 devnull 				print("	[%.2x-%.2x] ->%p\n", i, j-1, a->u.cases[i]);
282 8ad51794 2004-03-25 devnull 				i = j-1;
283 8ad51794 2004-03-25 devnull 			}
284 8ad51794 2004-03-25 devnull 		for(i=0; i<256; i++)
285 285b4f85 2004-03-25 devnull 			reprint1(a->u.cases[i]);
286 8ad51794 2004-03-25 devnull 		break;
287 8ad51794 2004-03-25 devnull 
288 8ad51794 2004-03-25 devnull 	case Tbegin:
289 8ad51794 2004-03-25 devnull 		print("^ ->%p\n", a->next);
290 8ad51794 2004-03-25 devnull 		break;
291 8ad51794 2004-03-25 devnull 
292 8ad51794 2004-03-25 devnull 	case Tend:
293 8ad51794 2004-03-25 devnull 		print("$ ->%p\n", a->next);
294 8ad51794 2004-03-25 devnull 		break;
295 8ad51794 2004-03-25 devnull 
296 8ad51794 2004-03-25 devnull 	case Tclass:
297 285b4f85 2004-03-25 devnull 		print("[%.2x-%.2x] ->%p\n", a->u.x.lo, a->u.x.hi, a->next);
298 8ad51794 2004-03-25 devnull 		break;
299 8ad51794 2004-03-25 devnull 
300 8ad51794 2004-03-25 devnull 	case Tor:
301 8ad51794 2004-03-25 devnull 	case Talt:
302 285b4f85 2004-03-25 devnull 		print("| %p ->%p\n", a->u.alt, a->next);
303 285b4f85 2004-03-25 devnull 		reprint1(a->u.alt);
304 8ad51794 2004-03-25 devnull 		break;
305 8ad51794 2004-03-25 devnull 	}
306 8ad51794 2004-03-25 devnull 	a = a->next;
307 8ad51794 2004-03-25 devnull 	goto loop;
308 8ad51794 2004-03-25 devnull }
309 8ad51794 2004-03-25 devnull 
310 8ad51794 2004-03-25 devnull void
311 8ad51794 2004-03-25 devnull reprint(char *s, Re *r)
312 8ad51794 2004-03-25 devnull {
313 8ad51794 2004-03-25 devnull 	print("%s:\n", s);
314 8ad51794 2004-03-25 devnull 	gen++;
315 8ad51794 2004-03-25 devnull 	reprint1(r);
316 8ad51794 2004-03-25 devnull 	print("\n\n");
317 8ad51794 2004-03-25 devnull }