?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
dmake: do not set MAKEFLAGS=k
[unleashed/tickless.git] / usr / src / lib / libast / common / regex / regdecomp.c
blob1f239615b1dfb848080390b4381dd810aebb95bf
1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #pragma prototyped
23
24 /*
25 * posix regex decompiler
26 */
27
28 #include "reglib.h"
29
30 #undef ismeta
31 #define ismeta(c,t,e,d) (state.magic[c] && state.magic[c][(t)+(e)] >= T_META || (c) == (d))
32 #define meta(f,c,t,e,d) do { if (ismeta(c,t,e,d)) sfputc(f, '\\'); sfputc(f, c); } while (0)
33
34 static void
35 detrie(Trie_node_t* x, Sfio_t* sp, char* b, char* p, char* e, int delimiter)
36 {
37 register Trie_node_t* y;
38 char* o;
39 int k;
40
41 o = p;
42 k = 1;
43 do
44 {
45 if (k)
46 {
47 o = p;
48 if (p < e)
49 *p++ = x->c;
50 }
51 sfputc(sp, x->c);
52 for (y = x->sib; y; y = y->sib)
53 {
54 sfputc(sp, '|');
55 sfputc(sp, '<');
56 sfwrite(sp, b, p - b);
57 sfputc(sp, '>');
58 detrie(y, sp, b, p, e, delimiter);
59 }
60 if (x->end && x->son)
61 {
62 sfputc(sp, '|');
63 sfputc(sp, '{');
64 sfwrite(sp, b, p - b);
65 sfputc(sp, '}');
66 p = o;
67 }
68 } while (x = x->son);
69 }
70
71 static int
72 decomp(register Rex_t* e, Sfio_t* sp, int type, int delimiter, regflags_t flags)
73 {
74 Rex_t* q;
75 unsigned char* s;
76 unsigned char* t;
77 int c;
78 int m;
79 int cb;
80 int cd;
81 int cr;
82 int ib;
83 int ie;
84 int nb;
85 int ne;
86 unsigned char ic[2*UCHAR_MAX];
87 unsigned char nc[2*UCHAR_MAX];
88
89 do
90 {
91 switch (e->type)
92 {
93 case REX_ALT:
94 if (decomp(e->re.group.expr.binary.left, sp, type, delimiter, flags))
95 return 1;
96 sfputc(sp, '|');
97 if (e->re.group.expr.binary.right && decomp(e->re.group.expr.binary.right, sp, type, delimiter, flags))
98 return 1;
99 break;
100 case REX_BACK:
101 sfprintf(sp, "\\%d", e->lo);
102 break;
103 case REX_BEG:
104 if (type < SRE)
105 sfputc(sp, '^');
106 break;
107 case REX_END:
108 if (type < SRE)
109 sfputc(sp, '$');
110 break;
111 case REX_WBEG:
112 meta(sp, '<', type, 1, delimiter);
113 break;
114 case REX_WEND:
115 meta(sp, '<', type, 1, delimiter);
116 break;
117 case REX_WORD:
118 sfprintf(sp, "\\w");
119 break;
120 case REX_CLASS:
121 case REX_COLL_CLASS:
122 case REX_ONECHAR:
123 case REX_DOT:
124 case REX_REP:
125 if (type >= SRE)
126 {
127 c = ')';
128 if (e->hi == RE_DUP_INF)
129 {
130 if (!e->lo)
131 sfputc(sp, '*');
132 else if (e->lo == 1)
133 sfputc(sp, '+');
134 else
135 sfprintf(sp, "{%d,}", e->lo);
136 }
137 else if (e->hi != 1)
138 sfprintf(sp, "{%d,%d}", e->lo, e->hi);
139 else if (e->lo == 0)
140 sfputc(sp, '?');
141 else
142 c = 0;
143 }
144 switch (e->type)
145 {
146 case REX_REP:
147 if (decomp(e->re.group.expr.rex, sp, type, delimiter, flags))
148 return 1;
149 break;
150 case REX_CLASS:
151 sfputc(sp, '[');
152 nb = ne = ib = ie = -2;
153 cb = cd = cr = 0;
154 s = nc;
155 t = ic;
156 for (m = 0; m <= UCHAR_MAX; m++)
157 if (settst(e->re.charclass, m))
158 {
159 if (m == ']')
160 cb = 1;
161 else if (m == '-')
162 cr = 1;
163 else if (m == delimiter)
164 cd = 1;
165 else if (nb < 0)
166 ne = nb = m;
167 else if (ne == (m - 1))
168 ne = m;
169 else
170 {
171 if (ne == nb)
172 *s++ = ne;
173 else
174 {
175 *s++ = nb;
176 *s++ = '-';
177 *s++ = ne;
178 }
179 ne = nb = m;
180 }
181 }
182 else
183 {
184 if (m == ']')
185 cb = -1;
186 else if (m == '-')
187 cr = -1;
188 else if (m == delimiter)
189 cd = -1;
190 else if (ib < 0)
191 ie = ib = m;
192 else if (ie == (m - 1))
193 ie = m;
194 else
195 {
196 if (ie == ib)
197 *t++ = ie;
198 else
199 {
200 *t++ = ib;
201 *t++ = '-';
202 *t++ = ie;
203 }
204 ie = ib = m;
205 }
206 }
207 if (nb >= 0)
208 {
209 *s++ = nb;
210 if (ne != nb)
211 {
212 *s++ = '-';
213 *s++ = ne;
214 }
215 }
216 if (ib >= 0)
217 {
218 *t++ = ib;
219 if (ie != ib)
220 {
221 *t++ = '-';
222 *t++ = ie;
223 }
224 }
225 if ((t - ic + 1) < (s - nc + (nc[0] == '^')))
226 {
227 sfputc(sp, '^');
228 if (cb < 0)
229 sfputc(sp, ']');
230 if (cr < 0)
231 sfputc(sp, '-');
232 if (cd < 0 && delimiter > 0)
233 {
234 if (flags & REG_ESCAPE)
235 sfputc(sp, '\\');
236 sfputc(sp, delimiter);
237 }
238 sfwrite(sp, ic, t - ic);
239 }
240 else
241 {
242 if (cb > 0)
243 sfputc(sp, ']');
244 if (cr > 0)
245 sfputc(sp, '-');
246 if (cd > 0 && delimiter > 0)
247 {
248 if (flags & REG_ESCAPE)
249 sfputc(sp, '\\');
250 sfputc(sp, delimiter);
251 }
252 if (nc[0] == '^')
253 {
254 sfwrite(sp, nc + 1, s - nc - 1);
255 sfputc(sp, '^');
256 }
257 else
258 sfwrite(sp, nc, s - nc);
259 }
260 sfputc(sp, ']');
261 break;
262 case REX_COLL_CLASS:
263 break;
264 case REX_ONECHAR:
265 meta(sp, e->re.onechar, type, 0, delimiter);
266 break;
267 case REX_DOT:
268 sfputc(sp, '.');
269 break;
270 }
271 if (type < SRE)
272 {
273 if (e->hi == RE_DUP_INF)
274 {
275 if (!e->lo)
276 sfputc(sp, '*');
277 else if (e->lo == 1 && ismeta('+', type, 0, delimiter))
278 meta(sp, '+', type, 1, delimiter);
279 else
280 {
281 meta(sp, '{', type, 1, delimiter);
282 sfprintf(sp, "%d,", e->lo);
283 meta(sp, '}', type, 1, delimiter);
284 }
285 }
286 else if (e->hi != 1 || e->lo == 0 && !ismeta('?', type, 0, delimiter))
287 {
288 meta(sp, '{', type, 1, delimiter);
289 sfprintf(sp, "%d,%d", e->lo, e->hi);
290 meta(sp, '}', type, 1, delimiter);
291 }
292 else if (e->lo == 0)
293 meta(sp, '?', type, 1, delimiter);
294 }
295 else if (c)
296 sfputc(sp, c);
297 break;
298 case REX_STRING:
299 case REX_KMP:
300 t = (s = e->re.string.base) + e->re.string.size;
301 while (s < t)
302 {
303 c = *s++;
304 meta(sp, c, type, 0, delimiter);
305 }
306 break;
307 case REX_TRIE:
308 ib = 0;
309 for (c = 0; c <= UCHAR_MAX; c++)
310 if (e->re.trie.root[c])
311 {
312 char pfx[1024];
313
314 if (ib)
315 sfputc(sp, '|');
316 else
317 ib = 1;
318 detrie(e->re.trie.root[c], sp, pfx, pfx, &pfx[sizeof(pfx)], delimiter);
319 }
320 break;
321 case REX_NEG:
322 if (type >= SRE)
323 sfprintf(sp, "!(");
324 if (decomp(e->re.group.expr.rex, sp, type, delimiter, flags))
325 return 1;
326 if (type >= SRE)
327 sfputc(sp, ')');
328 else
329 sfputc(sp, '!');
330 break;
331 case REX_CONJ:
332 if (decomp(e->re.group.expr.binary.left, sp, type, delimiter, flags))
333 return 1;
334 sfputc(sp, '&');
335 if (decomp(e->re.group.expr.binary.right, sp, type, delimiter, flags))
336 return 1;
337 break;
338 case REX_GROUP:
339 if (type >= SRE)
340 sfputc(sp, '@');
341 meta(sp, '(', type, 1, delimiter);
342 if (decomp(e->re.group.expr.rex, sp, type, delimiter, flags))
343 return 1;
344 meta(sp, ')', type, 1, delimiter);
345 break;
346 case REX_GROUP_AHEAD:
347 case REX_GROUP_AHEAD_NOT:
348 case REX_GROUP_BEHIND:
349 case REX_GROUP_BEHIND_NOT:
350 meta(sp, '(', type, 1, delimiter);
351 sfputc(sp, '?');
352 if (decomp(e->re.group.expr.rex, sp, type, delimiter, flags))
353 return 1;
354 meta(sp, ')', type, 1, delimiter);
355 break;
356 case REX_GROUP_COND:
357 meta(sp, '(', type, 1, delimiter);
358 sfputc(sp, '?');
359 if (e->re.group.expr.binary.left && decomp(e->re.group.expr.binary.left, sp, type, delimiter, flags))
360 return 1;
361 if (q = e->re.group.expr.binary.right)
362 {
363 sfputc(sp, ':');
364 if (q->re.group.expr.binary.left && decomp(q->re.group.expr.binary.left, sp, type, delimiter, flags))
365 return 1;
366 sfputc(sp, ':');
367 if (q->re.group.expr.binary.right && decomp(q->re.group.expr.binary.right, sp, type, delimiter, flags))
368 return 1;
369 }
370 meta(sp, ')', type, 1, delimiter);
371 break;
372 case REX_GROUP_CUT:
373 meta(sp, '(', type, 1, delimiter);
374 sfputc(sp, '?');
375 if (decomp(e->re.group.expr.rex, sp, type, delimiter, flags))
376 return 1;
377 meta(sp, ')', type, 1, delimiter);
378 break;
379 case REX_BM:
380 break;
381 default:
382 sfprintf(sp, "<ERROR:REX_%d>", e->type);
383 break;
384 }
385 } while (e = e->next);
386 return 0;
387 }
388
389 /*
390 * reconstruct pattern from compiled re p into sp
391 */
392
393 size_t
394 regdecomp(regex_t* p, regflags_t flags, char* buf, size_t n)
395 {
396 Sfio_t* sp;
397 char* s;
398 int type;
399 int delimiter;
400 size_t r;
401
402 if (!(sp = sfstropen()))
403 return 0;
404 if (flags == (regflags_t)~0)
405 flags = p->env->flags;
406 switch (flags & (REG_AUGMENTED|REG_EXTENDED|REG_SHELL))
407 {
408 case 0:
409 type = BRE;
410 break;
411 case REG_AUGMENTED:
412 case REG_AUGMENTED|REG_EXTENDED:
413 type = ARE;
414 break;
415 case REG_EXTENDED:
416 type = ERE;
417 break;
418 case REG_SHELL:
419 type = SRE;
420 break;
421 default:
422 type = KRE;
423 break;
424 }
425 if (flags & REG_DELIMITED)
426 {
427 delimiter = '/';
428 sfputc(sp, delimiter);
429 }
430 else
431 delimiter = -1;
432 if (decomp(p->env->rex, sp, type, delimiter, flags))
433 r = 0;
434 else
435 {
436 if (delimiter > 0)
437 sfputc(sp, delimiter);
438 if ((r = sfstrtell(sp) + 1) <= n)
439 {
440 if (!(s = sfstruse(sp)))
441 r = 0;
442 else
443 memcpy(buf, s, r);
444 }
445 }
446 sfstrclose(sp);
447 return r;
448 }
unleashed repo fork