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 = sbrk(n);
14 memset(v, 0, n);
15 return v;
16 }
17 s = sbrk(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->alt);
67 r = r->next;
68 goto loop;
69 case Tclass:
70 return n + r->hi - r->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->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->alt);
97 r = r->next;
98 goto loop;
99
100 case Tclass: /* add to character */
101 for(n=r->lo; n<=r->hi; n++)
102 c->cases[n] = oralloc(Tor, r->next, c->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->cases = mal(256*sizeof(*a->cases));
129 case1(a, r);
130 for(i=0; i<256; i++)
131 if(a->cases[i]) {
132 r = a->cases[i];
133 if(countor(r) < n)
134 a->cases[i] = addcase(r);
135 }
136 return a;
137 }
138 return r;
139
140 case Talt:
141 r->next = addcase(r->next);
142 r->alt = addcase(r->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 if (*p == '\0')
160 yyerror("empty pattern"); /* can't be a file name here */
161 if (!flags['f'])
162 pattern = p;
163 topre.beg = 0;
164 topre.end = 0;
165 yyparse();
166 gen++;
167 if(topre.beg == 0)
168 yyerror("syntax");
169 if(oldtop.beg)
170 topre = re2or(oldtop, topre);
171 }
172
173 void
appendnext(Re * a,Re * b)174 appendnext(Re *a, Re *b)
175 {
176 Re *n;
177
178 while(n = a->next)
179 a = n;
180 a->next = b;
181 }
182
183 void
patchnext(Re * a,Re * b)184 patchnext(Re *a, Re *b)
185 {
186 Re *n;
187
188 while(a) {
189 n = a->next;
190 a->next = b;
191 a = n;
192 }
193 }
194
195 int
getrec(void)196 getrec(void)
197 {
198 int c;
199
200 if(flags['f']) {
201 c = Bgetc(rein);
202 if(c <= 0)
203 return 0;
204 } else
205 c = *input++ & 0xff;
206 if(flags['i'] && c >= 'A' && c <= 'Z')
207 c += 'a'-'A';
208 if(c == '\n')
209 lineno++;
210 return c;
211 }
212
213 Re2
re2cat(Re2 a,Re2 b)214 re2cat(Re2 a, Re2 b)
215 {
216 Re2 c;
217
218 c.beg = a.beg;
219 c.end = b.end;
220 patchnext(a.end, b.beg);
221 return c;
222 }
223
224 Re2
re2star(Re2 a)225 re2star(Re2 a)
226 {
227 Re2 c;
228
229 c.beg = ral(Talt);
230 c.beg->alt = a.beg;
231 patchnext(a.end, c.beg);
232 c.end = c.beg;
233 return c;
234 }
235
236 Re2
re2or(Re2 a,Re2 b)237 re2or(Re2 a, Re2 b)
238 {
239 Re2 c;
240
241 c.beg = ral(Tor);
242 c.beg->alt = b.beg;
243 c.beg->next = a.beg;
244 c.end = b.end;
245 appendnext(c.end, a.end);
246 return c;
247 }
248
249 Re2
re2char(int c0,int c1)250 re2char(int c0, int c1)
251 {
252 Re2 c;
253
254 c.beg = ral(Tclass);
255 c.beg->lo = c0 & 0xff;
256 c.beg->hi = c1 & 0xff;
257 c.end = c.beg;
258 return c;
259 }
260
261 void
reprint1(Re * a)262 reprint1(Re *a)
263 {
264 int i, j;
265
266 loop:
267 if(a == 0)
268 return;
269 if(a->gen == gen)
270 return;
271 a->gen = gen;
272 print("%p: ", a);
273 switch(a->type) {
274 default:
275 print("type %d\n", a->type);
276 error("print1 type");
277
278 case Tcase:
279 print("case ->%p\n", a->next);
280 for(i=0; i<256; i++)
281 if(a->cases[i]) {
282 for(j=i+1; j<256; j++)
283 if(a->cases[i] != a->cases[j])
284 break;
285 print(" [%.2x-%.2x] ->%p\n", i, j-1, a->cases[i]);
286 i = j-1;
287 }
288 for(i=0; i<256; i++)
289 reprint1(a->cases[i]);
290 break;
291
292 case Tbegin:
293 print("^ ->%p\n", a->next);
294 break;
295
296 case Tend:
297 print("$ ->%p\n", a->next);
298 break;
299
300 case Tclass:
301 print("[%.2x-%.2x] ->%p\n", a->lo, a->hi, a->next);
302 break;
303
304 case Tor:
305 case Talt:
306 print("| %p ->%p\n", a->alt, a->next);
307 reprint1(a->alt);
308 break;
309 }
310 a = a->next;
311 goto loop;
312 }
313
314 void
reprint(char * s,Re * r)315 reprint(char *s, Re *r)
316 {
317 print("%s:\n", s);
318 gen++;
319 reprint1(r);
320 print("\n\n");
321 }
322