1 #include "grep.h"
2
3 void*
mal(int n)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*
sal(int n)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*
ral(int type)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
error(char * s)51 error(char *s)
52 {
53 fprint(2, "grep: internal error: %s\n", s);
54 exits(s);
55 }
56
57 int
countor(Re * r)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*
oralloc(int t,Re * r,Re * b)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
case1(Re * c,Re * r)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*
addcase(Re * r)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
str2top(char * p)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
appendnext(Re * a,Re * b)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
patchnext(Re * a,Re * b)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
getrec(void)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
re2cat(Re2 a,Re2 b)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
re2star(Re2 a)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
re2or(Re2 a,Re2 b)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
re2char(int c0,int c1)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
reprint1(Re * a)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
reprint(char * s,Re * r)311 reprint(char *s, Re *r)
312 {
313 print("%s:\n", s);
314 gen++;
315 reprint1(r);
316 print("\n\n");
317 }
318