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