1da2e3ebdSchin /***********************************************************************
2da2e3ebdSchin * *
3da2e3ebdSchin * This software is part of the ast package *
4*b30d1939SAndy Fiddaman * Copyright (c) 1985-2012 AT&T Intellectual Property *
5da2e3ebdSchin * and is licensed under the *
6*b30d1939SAndy Fiddaman * Eclipse Public License, Version 1.0 *
77c2fbfb3SApril Chin * by AT&T Intellectual Property *
8da2e3ebdSchin * *
9da2e3ebdSchin * A copy of the License is available at *
10*b30d1939SAndy Fiddaman * http://www.eclipse.org/org/documents/epl-v10.html *
11*b30d1939SAndy Fiddaman * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12da2e3ebdSchin * *
13da2e3ebdSchin * Information and Software Systems Research *
14da2e3ebdSchin * AT&T Research *
15da2e3ebdSchin * Florham Park NJ *
16da2e3ebdSchin * *
17da2e3ebdSchin * Glenn Fowler <gsf@research.att.com> *
18da2e3ebdSchin * David Korn <dgk@research.att.com> *
19da2e3ebdSchin * Phong Vo <kpv@research.att.com> *
20da2e3ebdSchin * *
21da2e3ebdSchin ***********************************************************************/
22da2e3ebdSchin #pragma prototyped
23da2e3ebdSchin
24da2e3ebdSchin /*
25da2e3ebdSchin * posix regex compiler
26da2e3ebdSchin */
27da2e3ebdSchin
28da2e3ebdSchin #include "reglib.h"
29da2e3ebdSchin
30da2e3ebdSchin #if _PACKAGE_ast
31da2e3ebdSchin #include "lclib.h"
32da2e3ebdSchin #endif
33da2e3ebdSchin
34da2e3ebdSchin #define serialize re_serialize /* hp.ia64 <unistd.h>! */
35da2e3ebdSchin
36da2e3ebdSchin #define C_ESC (-1)
37da2e3ebdSchin #define C_MB (-2)
38da2e3ebdSchin
39da2e3ebdSchin #if _AST_REGEX_DEBUG
40da2e3ebdSchin
41da2e3ebdSchin #define DEBUG_TEST(f,y,n) ((debug&(debug_flag=f))?(y):(n))
42da2e3ebdSchin #define DEBUG_CODE(f,y,n) do if(debug&(f)){y}else{n} while(0)
43da2e3ebdSchin #define DEBUG_INIT() do { char* t; if (!debug) { debug = 0x80000000; if (t = getenv("_AST_regex_comp_debug")) debug |= strtoul(t, NiL, 0); } } while (0)
44da2e3ebdSchin
45da2e3ebdSchin static unsigned long debug;
46da2e3ebdSchin static unsigned long debug_flag;
47da2e3ebdSchin
48da2e3ebdSchin #else
49da2e3ebdSchin
50da2e3ebdSchin #define DEBUG_INIT()
51da2e3ebdSchin #define DEBUG_TEST(f,y,n) (n)
52da2e3ebdSchin #define DEBUG_CODE(f,y,n) do {n} while(0)
53da2e3ebdSchin
54da2e3ebdSchin #endif
55da2e3ebdSchin
56da2e3ebdSchin #if _PACKAGE_ast
57da2e3ebdSchin
58da2e3ebdSchin typedef struct Cchr_s
59da2e3ebdSchin {
60da2e3ebdSchin Dtlink_t lnk;
61da2e3ebdSchin unsigned char nam[2];
62da2e3ebdSchin Ckey_t key;
63da2e3ebdSchin } Cchr_t;
64da2e3ebdSchin
65da2e3ebdSchin #endif
66da2e3ebdSchin
67da2e3ebdSchin #define eat(p) do{if ((p)->token.push)(p)->token.push=0;else (p)->cursor+=(p)->token.len;}while (0)
68da2e3ebdSchin
69da2e3ebdSchin /*
70da2e3ebdSchin * determine whether greedy matching will work, i.e. produce
71da2e3ebdSchin * the best match first. such expressions are "easy", and
72da2e3ebdSchin * need no backtracking once a complete match is found.
73da2e3ebdSchin * if an expression has backreferences or alts it's hard
74da2e3ebdSchin * else if it has only one closure it's easy
75da2e3ebdSchin * else if all closures are simple (i.e. one-character) it's easy
76da2e3ebdSchin * else it's hard.
77da2e3ebdSchin */
78da2e3ebdSchin
79da2e3ebdSchin typedef struct Stats_s
80da2e3ebdSchin {
81da2e3ebdSchin unsigned long l; /* min length to left of x */
82da2e3ebdSchin unsigned long k; /* min length to left of y */
83da2e3ebdSchin unsigned long m; /* min length */
84da2e3ebdSchin unsigned long n; /* max length */
85da2e3ebdSchin unsigned short a; /* number of alternations */
86da2e3ebdSchin unsigned short b; /* number of backrefs */
87da2e3ebdSchin unsigned short c; /* number of closures */
883e14f97fSRoger A. Faulkner unsigned short e; /* $ */
89da2e3ebdSchin unsigned short i; /* number of negations */
90da2e3ebdSchin unsigned short p; /* number of named subexpressions */
91da2e3ebdSchin unsigned short s; /* number of simple closures */
92da2e3ebdSchin unsigned short t; /* number of tries */
93da2e3ebdSchin unsigned short u; /* number of unnamed subexpressions */
94da2e3ebdSchin Rex_t* x; /* max length REX_STRING */
95da2e3ebdSchin Rex_t* y; /* max length REX_TRIE */
96da2e3ebdSchin } Stats_t;
97da2e3ebdSchin
98da2e3ebdSchin typedef struct Token_s
99da2e3ebdSchin {
100da2e3ebdSchin unsigned long min;
101da2e3ebdSchin unsigned long max;
102da2e3ebdSchin short lex;
103da2e3ebdSchin short len;
104da2e3ebdSchin short esc;
105da2e3ebdSchin short att;
106da2e3ebdSchin short push;
107da2e3ebdSchin } Token_t;
108da2e3ebdSchin
109da2e3ebdSchin typedef struct Cenv_s
110da2e3ebdSchin {
111da2e3ebdSchin int delimiter; /* pattern delimiter */
112da2e3ebdSchin int error; /* last error */
113da2e3ebdSchin int explicit; /* explicit match on this char */
114da2e3ebdSchin int mappeddot; /* inverse mapped '.' */
115da2e3ebdSchin int mappednewline; /* inverse mapped '\n' */
116da2e3ebdSchin int mappedslash; /* inverse mapped '/' */
117da2e3ebdSchin regflags_t flags; /* flags arg to regcomp */
118da2e3ebdSchin int type; /* BRE,ERE,ARE,SRE,KRE */
119da2e3ebdSchin unsigned char* cursor; /* curent point in re */
120da2e3ebdSchin unsigned char* pattern; /* the original pattern */
121da2e3ebdSchin unsigned char* literal; /* literal restart pattern */
122da2e3ebdSchin int parno; /* number of last open paren */
123da2e3ebdSchin int parnest; /* paren nest count */
124da2e3ebdSchin int posixkludge; /* to make * nonspecial */
125da2e3ebdSchin Token_t token; /* token lookahead */
126da2e3ebdSchin Stats_t stats; /* RE statistics */
127da2e3ebdSchin int terminator; /* pattern terminator */
128da2e3ebdSchin Rex_t* paren[2*(BACK_REF_MAX+2)];
129da2e3ebdSchin /* paren[i]!=0 if \i defined */
130da2e3ebdSchin regex_t* regex; /* user handle */
131da2e3ebdSchin regdisc_t* disc; /* user discipline */
132da2e3ebdSchin unsigned char* map; /* external to native ccode map */
133da2e3ebdSchin unsigned char* MAP; /* fold and/or map */
134da2e3ebdSchin } Cenv_t;
135da2e3ebdSchin
136da2e3ebdSchin /*
137da2e3ebdSchin * allocate a new Rex_t node
138da2e3ebdSchin */
139da2e3ebdSchin
140*b30d1939SAndy Fiddaman #if _BLD_DEBUG
141*b30d1939SAndy Fiddaman #define node(a,b,c,d,e) node(a,b,c,d,e, const char* file, unsigned int line)
142*b30d1939SAndy Fiddaman #endif
143*b30d1939SAndy Fiddaman
144da2e3ebdSchin static Rex_t*
node(Cenv_t * env,int type,int lo,int hi,size_t extra)145da2e3ebdSchin node(Cenv_t* env, int type, int lo, int hi, size_t extra)
146da2e3ebdSchin {
147da2e3ebdSchin register Rex_t* e;
148da2e3ebdSchin
149*b30d1939SAndy Fiddaman DEBUG_TEST(0x0800,(sfprintf(sfstdout, "%s:%d node(%d,%d,%d,%u)\n", file, line, type, lo, hi, sizeof(Rex_t) + extra)),(0));
150da2e3ebdSchin if (e = (Rex_t*)alloc(env->disc, 0, sizeof(Rex_t) + extra))
151da2e3ebdSchin {
152da2e3ebdSchin memset(e, 0, sizeof(Rex_t) + extra);
153da2e3ebdSchin e->type = type;
154da2e3ebdSchin e->marked = 0;
155da2e3ebdSchin e->lo = lo;
156da2e3ebdSchin e->hi = hi;
157da2e3ebdSchin e->flags = env->flags;
158da2e3ebdSchin e->map = (e->flags & REG_ICASE) ? env->MAP : env->map;
159da2e3ebdSchin e->explicit = env->explicit;
160da2e3ebdSchin if (extra)
161da2e3ebdSchin e->re.data = (char*)e + sizeof(Rex_t);
162da2e3ebdSchin }
163da2e3ebdSchin return e;
164da2e3ebdSchin }
165da2e3ebdSchin
166*b30d1939SAndy Fiddaman #if _BLD_DEBUG
167*b30d1939SAndy Fiddaman #undef node
168*b30d1939SAndy Fiddaman #define node(a,b,c,d,e) node(a,b,c,d,e,__FILE__,__LINE__)
169*b30d1939SAndy Fiddaman #endif
170*b30d1939SAndy Fiddaman
171da2e3ebdSchin /*
172da2e3ebdSchin * free a Trie_node_t node
173da2e3ebdSchin */
174da2e3ebdSchin
175da2e3ebdSchin static void
triedrop(regdisc_t * disc,Trie_node_t * e)176da2e3ebdSchin triedrop(regdisc_t* disc, Trie_node_t* e)
177da2e3ebdSchin {
178da2e3ebdSchin if (e)
179da2e3ebdSchin {
180da2e3ebdSchin triedrop(disc, e->son);
181da2e3ebdSchin triedrop(disc, e->sib);
182da2e3ebdSchin alloc(disc, e, 0);
183da2e3ebdSchin }
184da2e3ebdSchin }
185da2e3ebdSchin
186da2e3ebdSchin /*
187da2e3ebdSchin * free a Rex_t node
188da2e3ebdSchin */
189da2e3ebdSchin
190da2e3ebdSchin void
drop(regdisc_t * disc,Rex_t * e)191da2e3ebdSchin drop(regdisc_t* disc, Rex_t* e)
192da2e3ebdSchin {
193da2e3ebdSchin int i;
194da2e3ebdSchin Rex_t* x;
195da2e3ebdSchin
196da2e3ebdSchin if (e && !(disc->re_flags & REG_NOFREE))
197da2e3ebdSchin do
198da2e3ebdSchin {
199da2e3ebdSchin switch (e->type)
200da2e3ebdSchin {
201da2e3ebdSchin case REX_ALT:
202da2e3ebdSchin case REX_CONJ:
203da2e3ebdSchin drop(disc, e->re.group.expr.binary.left);
204da2e3ebdSchin drop(disc, e->re.group.expr.binary.right);
205da2e3ebdSchin break;
206da2e3ebdSchin case REX_GROUP:
207da2e3ebdSchin case REX_GROUP_AHEAD:
208da2e3ebdSchin case REX_GROUP_AHEAD_NOT:
209da2e3ebdSchin case REX_GROUP_BEHIND:
210da2e3ebdSchin case REX_GROUP_BEHIND_NOT:
211da2e3ebdSchin case REX_GROUP_CUT:
212da2e3ebdSchin case REX_NEG:
213da2e3ebdSchin case REX_REP:
214da2e3ebdSchin drop(disc, e->re.group.expr.rex);
215da2e3ebdSchin break;
216da2e3ebdSchin case REX_TRIE:
217da2e3ebdSchin for (i = 0; i <= UCHAR_MAX; i++)
218da2e3ebdSchin triedrop(disc, e->re.trie.root[i]);
219da2e3ebdSchin break;
220da2e3ebdSchin }
221da2e3ebdSchin x = e->next;
222da2e3ebdSchin alloc(disc, e, 0);
223da2e3ebdSchin } while (e = x);
224da2e3ebdSchin }
225da2e3ebdSchin
226da2e3ebdSchin /*
227da2e3ebdSchin * mark e and descendants minimal
228da2e3ebdSchin */
229da2e3ebdSchin
230da2e3ebdSchin static void
mark(register Rex_t * e,int set)231da2e3ebdSchin mark(register Rex_t* e, int set)
232da2e3ebdSchin {
233da2e3ebdSchin if (e && !e->marked)
234da2e3ebdSchin do
235da2e3ebdSchin {
236da2e3ebdSchin e->marked = 1;
237da2e3ebdSchin if (set)
238da2e3ebdSchin e->flags |= REG_MINIMAL;
239da2e3ebdSchin else
240da2e3ebdSchin e->flags &= ~REG_MINIMAL;
241da2e3ebdSchin switch (e->type)
242da2e3ebdSchin {
243da2e3ebdSchin case REX_ALT:
244da2e3ebdSchin case REX_CONJ:
245da2e3ebdSchin case REX_GROUP_COND:
246da2e3ebdSchin if (e->re.group.expr.binary.left)
247da2e3ebdSchin mark(e->re.group.expr.binary.left, set);
248da2e3ebdSchin if (e->re.group.expr.binary.right)
249da2e3ebdSchin mark(e->re.group.expr.binary.right, set);
250da2e3ebdSchin break;
251da2e3ebdSchin case REX_GROUP:
252da2e3ebdSchin case REX_GROUP_AHEAD:
253da2e3ebdSchin case REX_GROUP_AHEAD_NOT:
254da2e3ebdSchin case REX_GROUP_BEHIND:
255da2e3ebdSchin case REX_GROUP_BEHIND_NOT:
256da2e3ebdSchin case REX_GROUP_CUT:
257da2e3ebdSchin case REX_NEG:
258da2e3ebdSchin case REX_REP:
259da2e3ebdSchin case REX_TRIE:
260da2e3ebdSchin mark(e->re.group.expr.rex, set);
261da2e3ebdSchin break;
262da2e3ebdSchin }
263da2e3ebdSchin } while (e = e->next);
264da2e3ebdSchin }
265da2e3ebdSchin
266da2e3ebdSchin /*
267da2e3ebdSchin * assign subexpression numbers by a preorder tree walk
268da2e3ebdSchin */
269da2e3ebdSchin
270da2e3ebdSchin static int
serialize(Cenv_t * env,Rex_t * e,int n)271da2e3ebdSchin serialize(Cenv_t* env, Rex_t* e, int n)
272da2e3ebdSchin {
273da2e3ebdSchin do
274da2e3ebdSchin {
275da2e3ebdSchin e->serial = n++;
276da2e3ebdSchin switch (e->type)
277da2e3ebdSchin {
278da2e3ebdSchin case REX_ALT:
279da2e3ebdSchin case REX_GROUP_COND:
280da2e3ebdSchin if (e->re.group.expr.binary.left)
281da2e3ebdSchin n = serialize(env, e->re.group.expr.binary.left, n);
282da2e3ebdSchin e->re.group.expr.binary.serial = n++;
283da2e3ebdSchin if (e->re.group.expr.binary.right)
284da2e3ebdSchin n = serialize(env, e->re.group.expr.binary.right, n);
285da2e3ebdSchin break;
286da2e3ebdSchin case REX_CONJ:
287da2e3ebdSchin n = serialize(env, e->re.group.expr.binary.left, n);
288da2e3ebdSchin n = serialize(env, e->re.group.expr.binary.right, n);
289da2e3ebdSchin break;
290da2e3ebdSchin case REX_GROUP:
291da2e3ebdSchin case REX_GROUP_AHEAD:
292da2e3ebdSchin case REX_GROUP_AHEAD_NOT:
293da2e3ebdSchin case REX_GROUP_BEHIND:
294da2e3ebdSchin case REX_GROUP_BEHIND_NOT:
295da2e3ebdSchin case REX_GROUP_CUT:
296da2e3ebdSchin case REX_NEG:
297da2e3ebdSchin case REX_REP:
298da2e3ebdSchin n = serialize(env, e->re.group.expr.rex, n);
299da2e3ebdSchin break;
300da2e3ebdSchin }
301da2e3ebdSchin } while (e = e->next);
302da2e3ebdSchin return n;
303da2e3ebdSchin }
304da2e3ebdSchin
305da2e3ebdSchin /*
306da2e3ebdSchin * catenate e and f into a sequence, collapsing them if possible
307da2e3ebdSchin */
308da2e3ebdSchin
309da2e3ebdSchin static Rex_t*
cat(Cenv_t * env,Rex_t * e,Rex_t * f)310da2e3ebdSchin cat(Cenv_t* env, Rex_t* e, Rex_t* f)
311da2e3ebdSchin {
312da2e3ebdSchin Rex_t* g;
313da2e3ebdSchin
314da2e3ebdSchin if (!f)
315da2e3ebdSchin {
316da2e3ebdSchin drop(env->disc, e);
317da2e3ebdSchin return 0;
318da2e3ebdSchin }
319da2e3ebdSchin if (e->type == REX_NULL)
320da2e3ebdSchin {
321da2e3ebdSchin drop(env->disc, e);
322da2e3ebdSchin return f;
323da2e3ebdSchin }
324da2e3ebdSchin if (f->type == REX_NULL)
325da2e3ebdSchin {
326da2e3ebdSchin g = f->next;
327da2e3ebdSchin f->next = 0;
328da2e3ebdSchin drop(env->disc, f);
329da2e3ebdSchin f = g;
330da2e3ebdSchin }
331da2e3ebdSchin else if (e->type == REX_DOT && f->type == REX_DOT)
332da2e3ebdSchin {
333da2e3ebdSchin unsigned int m = e->lo + f->lo;
334da2e3ebdSchin unsigned int n = e->hi + f->hi;
335da2e3ebdSchin
336da2e3ebdSchin if (m <= RE_DUP_MAX)
337da2e3ebdSchin {
338da2e3ebdSchin if (e->hi > RE_DUP_MAX || f->hi > RE_DUP_MAX)
339da2e3ebdSchin {
340da2e3ebdSchin n = RE_DUP_INF;
341da2e3ebdSchin goto combine;
342da2e3ebdSchin }
343da2e3ebdSchin else if (n <= RE_DUP_MAX)
344da2e3ebdSchin {
345da2e3ebdSchin combine:
346da2e3ebdSchin e->lo = m;
347da2e3ebdSchin e->hi = n;
348da2e3ebdSchin g = f->next;
349da2e3ebdSchin f->next = 0;
350da2e3ebdSchin drop(env->disc, f);
351da2e3ebdSchin f = g;
352da2e3ebdSchin }
353da2e3ebdSchin }
354da2e3ebdSchin }
355da2e3ebdSchin e->next = f;
356da2e3ebdSchin return e;
357da2e3ebdSchin }
358da2e3ebdSchin
359da2e3ebdSchin /*
360da2e3ebdSchin * collect re statistics
361da2e3ebdSchin */
362da2e3ebdSchin
363da2e3ebdSchin static int
stats(register Cenv_t * env,register Rex_t * e)364da2e3ebdSchin stats(register Cenv_t* env, register Rex_t* e)
365da2e3ebdSchin {
366da2e3ebdSchin register unsigned long n;
367da2e3ebdSchin register unsigned long m;
368da2e3ebdSchin unsigned long cm;
369da2e3ebdSchin unsigned long nm;
370da2e3ebdSchin unsigned long cn;
371da2e3ebdSchin unsigned long nn;
372da2e3ebdSchin unsigned long l;
373da2e3ebdSchin unsigned long k;
374da2e3ebdSchin unsigned long t;
375da2e3ebdSchin Rex_t* q;
376da2e3ebdSchin Rex_t* x;
377da2e3ebdSchin Rex_t* y;
378da2e3ebdSchin unsigned char c;
379da2e3ebdSchin unsigned char b;
380da2e3ebdSchin
381da2e3ebdSchin do
382da2e3ebdSchin {
383da2e3ebdSchin switch (e->type)
384da2e3ebdSchin {
385da2e3ebdSchin case REX_ALT:
386da2e3ebdSchin x = env->stats.x;
387da2e3ebdSchin l = env->stats.l;
388da2e3ebdSchin y = env->stats.y;
389da2e3ebdSchin k = env->stats.k;
390da2e3ebdSchin t = env->stats.t;
391da2e3ebdSchin if (++env->stats.a <= 0)
392da2e3ebdSchin return 1;
393da2e3ebdSchin cm = env->stats.m;
394da2e3ebdSchin env->stats.m = 0;
395da2e3ebdSchin cn = env->stats.n;
396da2e3ebdSchin env->stats.n = 0;
397da2e3ebdSchin if (stats(env, e->re.group.expr.binary.left))
398da2e3ebdSchin return 1;
399da2e3ebdSchin m = env->stats.m;
400da2e3ebdSchin env->stats.m = 0;
401da2e3ebdSchin n = env->stats.n;
402da2e3ebdSchin env->stats.n = 0;
403da2e3ebdSchin if (e->re.group.expr.binary.right && stats(env, e->re.group.expr.binary.right))
404da2e3ebdSchin return 1;
405da2e3ebdSchin if (env->stats.m > m)
406da2e3ebdSchin env->stats.m = m;
407da2e3ebdSchin else
408da2e3ebdSchin m = env->stats.m;
409da2e3ebdSchin if ((env->stats.m += cm) < m)
410da2e3ebdSchin return 1;
411da2e3ebdSchin if (env->stats.n < n)
412da2e3ebdSchin env->stats.n = n;
413da2e3ebdSchin else
414da2e3ebdSchin n = env->stats.n;
415da2e3ebdSchin if ((env->stats.n += cn) < n)
416da2e3ebdSchin return 1;
417da2e3ebdSchin env->stats.x = x;
418da2e3ebdSchin env->stats.l = l;
419da2e3ebdSchin env->stats.y = y;
420da2e3ebdSchin env->stats.k = k;
421da2e3ebdSchin env->stats.t = t;
422da2e3ebdSchin break;
423da2e3ebdSchin case REX_BACK:
424da2e3ebdSchin if (++env->stats.b <= 0)
425da2e3ebdSchin return 1;
426da2e3ebdSchin break;
427da2e3ebdSchin case REX_CLASS:
428da2e3ebdSchin case REX_COLL_CLASS:
429da2e3ebdSchin case REX_DOT:
430da2e3ebdSchin case REX_ONECHAR:
431da2e3ebdSchin n = env->stats.m;
432da2e3ebdSchin if ((env->stats.m += e->lo) < n)
433da2e3ebdSchin return 1;
434da2e3ebdSchin if (e->hi != RE_DUP_INF)
435da2e3ebdSchin {
436da2e3ebdSchin n = env->stats.n;
437da2e3ebdSchin if ((env->stats.n += e->hi) < n)
438da2e3ebdSchin return 1;
439da2e3ebdSchin }
440da2e3ebdSchin if (e->lo != e->hi)
441da2e3ebdSchin {
442da2e3ebdSchin if (++env->stats.c <= 0)
443da2e3ebdSchin return 1;
444da2e3ebdSchin if (++env->stats.s <= 0)
445da2e3ebdSchin return 1;
446da2e3ebdSchin }
447da2e3ebdSchin break;
448da2e3ebdSchin case REX_CONJ:
449da2e3ebdSchin cm = env->stats.m;
450da2e3ebdSchin env->stats.m = 0;
451da2e3ebdSchin cn = env->stats.n;
452da2e3ebdSchin env->stats.n = 0;
453da2e3ebdSchin if (stats(env, e->re.group.expr.binary.left))
454da2e3ebdSchin return 1;
455da2e3ebdSchin nm = env->stats.m;
456da2e3ebdSchin env->stats.m = 0;
457da2e3ebdSchin nn = env->stats.n;
458da2e3ebdSchin env->stats.n = 0;
459da2e3ebdSchin if (stats(env, e->re.group.expr.binary.right))
460da2e3ebdSchin return 1;
461da2e3ebdSchin if (env->stats.m < nm)
462da2e3ebdSchin env->stats.m = nm;
463da2e3ebdSchin else
464da2e3ebdSchin nm = env->stats.m;
465da2e3ebdSchin if ((env->stats.m += cm) < nm)
466da2e3ebdSchin return 1;
467da2e3ebdSchin if (env->stats.n < nn)
468da2e3ebdSchin env->stats.n = nn;
469da2e3ebdSchin else
470da2e3ebdSchin nn = env->stats.n;
471da2e3ebdSchin if ((env->stats.n += cn) < nn)
472da2e3ebdSchin return 1;
473da2e3ebdSchin break;
4743e14f97fSRoger A. Faulkner case REX_END:
4753e14f97fSRoger A. Faulkner env->stats.e = 1;
4763e14f97fSRoger A. Faulkner break;
477da2e3ebdSchin case REX_GROUP:
478da2e3ebdSchin if (e->re.group.number && ++env->stats.p <= 0 || !e->re.group.number && ++env->stats.u <= 0)
479da2e3ebdSchin return 1;
480da2e3ebdSchin if (stats(env, e->re.group.expr.rex))
481da2e3ebdSchin return 1;
482da2e3ebdSchin break;
483da2e3ebdSchin case REX_GROUP_AHEAD:
484da2e3ebdSchin case REX_GROUP_AHEAD_NOT:
485da2e3ebdSchin case REX_GROUP_BEHIND:
486da2e3ebdSchin case REX_GROUP_BEHIND_NOT:
487da2e3ebdSchin m = env->stats.m;
488da2e3ebdSchin n = env->stats.n;
489da2e3ebdSchin x = env->stats.x;
490da2e3ebdSchin y = env->stats.y;
491da2e3ebdSchin if (stats(env, e->re.group.expr.rex))
492da2e3ebdSchin return 1;
493da2e3ebdSchin env->stats.m = m;
494da2e3ebdSchin env->stats.n = n;
495da2e3ebdSchin env->stats.x = x;
496da2e3ebdSchin env->stats.y = y;
497da2e3ebdSchin switch (e->type)
498da2e3ebdSchin {
499da2e3ebdSchin case REX_GROUP_AHEAD:
500da2e3ebdSchin case REX_GROUP_BEHIND:
501da2e3ebdSchin if (++env->stats.u <= 0)
502da2e3ebdSchin return 1;
503da2e3ebdSchin break;
504da2e3ebdSchin }
505da2e3ebdSchin break;
506da2e3ebdSchin case REX_GROUP_COND:
507da2e3ebdSchin if (++env->stats.u <= 0)
508da2e3ebdSchin return 1;
509da2e3ebdSchin m = env->stats.m;
510da2e3ebdSchin n = env->stats.n;
511da2e3ebdSchin x = env->stats.x;
512da2e3ebdSchin y = env->stats.y;
513da2e3ebdSchin if (e->re.group.size > 0 && ++env->stats.b <= 0)
514da2e3ebdSchin return 1;
515da2e3ebdSchin if (e->re.group.expr.binary.left && stats(env, e->re.group.expr.binary.left))
516da2e3ebdSchin return 1;
517da2e3ebdSchin if (q = e->re.group.expr.binary.right)
518da2e3ebdSchin {
519da2e3ebdSchin if (q->re.group.expr.binary.left && stats(env, q->re.group.expr.binary.left))
520da2e3ebdSchin return 1;
521da2e3ebdSchin if (q->re.group.expr.binary.right && stats(env, q->re.group.expr.binary.right))
522da2e3ebdSchin return 1;
523da2e3ebdSchin }
524da2e3ebdSchin env->stats.m = m;
525da2e3ebdSchin env->stats.n = n;
526da2e3ebdSchin env->stats.x = x;
527da2e3ebdSchin env->stats.y = y;
528da2e3ebdSchin break;
529da2e3ebdSchin case REX_GROUP_CUT:
530da2e3ebdSchin if (++env->stats.u <= 0)
531da2e3ebdSchin return 1;
532da2e3ebdSchin m = env->stats.m;
533da2e3ebdSchin n = env->stats.n;
534da2e3ebdSchin x = env->stats.x;
535da2e3ebdSchin y = env->stats.y;
536da2e3ebdSchin if (stats(env, e->re.group.expr.rex))
537da2e3ebdSchin return 1;
538da2e3ebdSchin env->stats.m = m;
539da2e3ebdSchin env->stats.n = n;
540da2e3ebdSchin env->stats.x = x;
541da2e3ebdSchin env->stats.y = y;
542da2e3ebdSchin break;
543da2e3ebdSchin case REX_NEG:
544da2e3ebdSchin env->stats.i++;
545da2e3ebdSchin x = env->stats.x;
546da2e3ebdSchin l = env->stats.l;
547da2e3ebdSchin y = env->stats.y;
548da2e3ebdSchin k = env->stats.k;
549da2e3ebdSchin t = env->stats.t;
550da2e3ebdSchin cm = env->stats.m;
551da2e3ebdSchin env->stats.m = 0;
552da2e3ebdSchin if (stats(env, e->re.group.expr.rex))
553da2e3ebdSchin return 1;
554da2e3ebdSchin env->stats.m = !env->stats.m;
555da2e3ebdSchin if ((env->stats.m += cm) < cm)
556da2e3ebdSchin return 1;
557da2e3ebdSchin env->stats.x = x;
558da2e3ebdSchin env->stats.l = l;
559da2e3ebdSchin env->stats.y = y;
560da2e3ebdSchin env->stats.k = k;
561da2e3ebdSchin env->stats.t = t;
562da2e3ebdSchin break;
563da2e3ebdSchin case REX_REP:
564da2e3ebdSchin x = env->stats.x;
565da2e3ebdSchin l = env->stats.l;
566da2e3ebdSchin y = env->stats.y;
567da2e3ebdSchin k = env->stats.k;
568da2e3ebdSchin t = env->stats.t;
569da2e3ebdSchin if (++env->stats.c <= 0)
570da2e3ebdSchin return 1;
571da2e3ebdSchin b = env->stats.b;
572da2e3ebdSchin c = env->stats.c;
573da2e3ebdSchin cm = env->stats.m;
574da2e3ebdSchin env->stats.m = 0;
575da2e3ebdSchin if (stats(env, e->re.group.expr.rex))
576da2e3ebdSchin return 1;
577da2e3ebdSchin if (env->stats.m == 1 && b == env->stats.b && c == env->stats.c && ++env->stats.s <= 0)
578da2e3ebdSchin return 1;
579da2e3ebdSchin if (e->lo < 1)
580da2e3ebdSchin {
581da2e3ebdSchin env->stats.x = x;
582da2e3ebdSchin env->stats.l = l;
583da2e3ebdSchin env->stats.y = y;
584da2e3ebdSchin env->stats.k = k;
585da2e3ebdSchin env->stats.t = t;
586da2e3ebdSchin env->stats.m = cm;
587da2e3ebdSchin }
588da2e3ebdSchin else
589da2e3ebdSchin {
590da2e3ebdSchin m = env->stats.m;
591da2e3ebdSchin if ((env->stats.m *= e->lo) > 0 && env->stats.m < m)
592da2e3ebdSchin return 1;
593da2e3ebdSchin m = env->stats.m;
594da2e3ebdSchin if ((env->stats.m += cm) < m)
595da2e3ebdSchin return 1;
596da2e3ebdSchin if (env->stats.x != x)
597da2e3ebdSchin env->stats.l = cm;
598da2e3ebdSchin if (env->stats.y != y)
599da2e3ebdSchin env->stats.k = cm;
600da2e3ebdSchin }
601da2e3ebdSchin break;
602da2e3ebdSchin case REX_STRING:
6037c2fbfb3SApril Chin if (!e->map)
604da2e3ebdSchin {
6057c2fbfb3SApril Chin cm = env->stats.m;
6067c2fbfb3SApril Chin if ((env->stats.m += e->re.string.size) < cm)
6077c2fbfb3SApril Chin return 1;
6087c2fbfb3SApril Chin cn = env->stats.n;
6097c2fbfb3SApril Chin if ((env->stats.n += e->re.string.size) < cn)
6107c2fbfb3SApril Chin return 1;
6117c2fbfb3SApril Chin if (!env->stats.x || env->stats.x->re.string.size < e->re.string.size)
6127c2fbfb3SApril Chin {
6137c2fbfb3SApril Chin env->stats.x = e;
6147c2fbfb3SApril Chin env->stats.l = cm;
6157c2fbfb3SApril Chin }
616da2e3ebdSchin }
617da2e3ebdSchin break;
618da2e3ebdSchin case REX_TRIE:
619da2e3ebdSchin if (++env->stats.s <= 0)
620da2e3ebdSchin return 1;
621da2e3ebdSchin cm = env->stats.m;
622da2e3ebdSchin if ((env->stats.m += e->re.trie.min) < cm)
623da2e3ebdSchin return 1;
624da2e3ebdSchin cn = env->stats.n;
625da2e3ebdSchin if ((env->stats.n += e->re.trie.max) < cn)
626da2e3ebdSchin return 1;
627da2e3ebdSchin env->stats.t++;
628da2e3ebdSchin if (!env->stats.y || env->stats.y->re.trie.min < e->re.trie.min)
629da2e3ebdSchin {
630da2e3ebdSchin env->stats.y = e;
631da2e3ebdSchin env->stats.k = cm;
632da2e3ebdSchin }
633da2e3ebdSchin break;
634da2e3ebdSchin }
635da2e3ebdSchin } while (e = e->next);
636da2e3ebdSchin return 0;
637da2e3ebdSchin }
638da2e3ebdSchin
639da2e3ebdSchin static int token(Cenv_t*);
640da2e3ebdSchin
641da2e3ebdSchin static int
magic(register Cenv_t * env,register int c,int escaped)642da2e3ebdSchin magic(register Cenv_t* env, register int c, int escaped)
643da2e3ebdSchin {
644da2e3ebdSchin register char* sp;
645da2e3ebdSchin register int n;
646da2e3ebdSchin int o = c;
647da2e3ebdSchin int e = env->error;
648da2e3ebdSchin int l = env->token.len;
649da2e3ebdSchin short* mp;
650da2e3ebdSchin char* ep;
651da2e3ebdSchin
652da2e3ebdSchin if (mp = state.magic[c])
653da2e3ebdSchin {
654da2e3ebdSchin c = mp[env->type+escaped];
655da2e3ebdSchin if (c >= T_META)
656da2e3ebdSchin {
657da2e3ebdSchin sp = (char*)env->cursor + env->token.len;
658da2e3ebdSchin switch (c)
659da2e3ebdSchin {
660da2e3ebdSchin case T_LEFT:
661da2e3ebdSchin n = 0;
662da2e3ebdSchin ep = sp;
663da2e3ebdSchin while (*sp >= '0' && *sp <= '9')
664da2e3ebdSchin {
665da2e3ebdSchin if (n > (INT_MAX / 10))
666da2e3ebdSchin {
667da2e3ebdSchin env->error = REG_BADBR;
668da2e3ebdSchin goto bad;
669da2e3ebdSchin }
670da2e3ebdSchin n = n * 10 + *sp++ - '0';
671da2e3ebdSchin }
672da2e3ebdSchin if (sp == ep)
673da2e3ebdSchin {
6747c2fbfb3SApril Chin if (env->type < SRE || *sp != ',')
6757c2fbfb3SApril Chin {
6767c2fbfb3SApril Chin env->error = *sp ? REG_BADBR : REG_EBRACE;
6777c2fbfb3SApril Chin goto bad;
6787c2fbfb3SApril Chin }
679da2e3ebdSchin }
680da2e3ebdSchin else if (n > RE_DUP_MAX)
681da2e3ebdSchin {
682da2e3ebdSchin env->error = REG_BADBR;
683da2e3ebdSchin goto bad;
684da2e3ebdSchin }
685da2e3ebdSchin env->token.min = n;
686da2e3ebdSchin if (*sp == ',')
687da2e3ebdSchin {
688da2e3ebdSchin n = 0;
689da2e3ebdSchin ep = ++sp;
690da2e3ebdSchin while (*sp >= '0' && *sp <= '9')
691da2e3ebdSchin {
692da2e3ebdSchin if (n > (INT_MAX / 10))
693da2e3ebdSchin {
694da2e3ebdSchin env->error = REG_BADBR;
695da2e3ebdSchin goto bad;
696da2e3ebdSchin }
697da2e3ebdSchin n = n * 10 + *sp++ - '0';
698da2e3ebdSchin }
699da2e3ebdSchin if (sp == ep)
700da2e3ebdSchin n = RE_DUP_INF;
701da2e3ebdSchin else if (n < env->token.min)
702da2e3ebdSchin {
703da2e3ebdSchin env->error = REG_BADBR;
704da2e3ebdSchin goto bad;
705da2e3ebdSchin }
706da2e3ebdSchin }
707da2e3ebdSchin env->token.max = n;
708da2e3ebdSchin switch (*sp)
709da2e3ebdSchin {
710da2e3ebdSchin case 0:
711da2e3ebdSchin env->error = REG_EBRACE;
712da2e3ebdSchin goto bad;
713da2e3ebdSchin case '\\':
714da2e3ebdSchin if (!escaped)
715da2e3ebdSchin {
716da2e3ebdSchin env->error = REG_BADBR;
717da2e3ebdSchin goto bad;
718da2e3ebdSchin }
719da2e3ebdSchin sp++;
720da2e3ebdSchin break;
721da2e3ebdSchin default:
722da2e3ebdSchin if (escaped)
723da2e3ebdSchin {
724da2e3ebdSchin env->error = REG_BADBR;
725da2e3ebdSchin goto bad;
726da2e3ebdSchin }
727da2e3ebdSchin break;
728da2e3ebdSchin }
729da2e3ebdSchin switch (*sp++)
730da2e3ebdSchin {
731da2e3ebdSchin case 0:
732da2e3ebdSchin env->error = REG_EBRACE;
733da2e3ebdSchin goto bad;
734da2e3ebdSchin case '}':
735da2e3ebdSchin break;
736da2e3ebdSchin default:
737da2e3ebdSchin env->error = REG_BADBR;
738da2e3ebdSchin goto bad;
739da2e3ebdSchin }
740da2e3ebdSchin env->token.len = sp - (char*)env->cursor;
741da2e3ebdSchin break;
742da2e3ebdSchin case T_RIGHT:
743da2e3ebdSchin env->error = REG_EBRACE;
744da2e3ebdSchin goto bad;
745da2e3ebdSchin case T_OPEN:
746da2e3ebdSchin if (env->type < SRE && *sp == '?')
747da2e3ebdSchin {
748da2e3ebdSchin env->token.len++;
749da2e3ebdSchin env->token.lex = 0;
750da2e3ebdSchin goto group;
751da2e3ebdSchin }
752da2e3ebdSchin break;
753da2e3ebdSchin case T_ESCAPE:
754da2e3ebdSchin c = chresc(sp - 2, &ep);
755da2e3ebdSchin if (ep < sp)
756da2e3ebdSchin goto bad;
757da2e3ebdSchin env->token.len += ep - sp;
758da2e3ebdSchin if (c >= T_META)
759da2e3ebdSchin {
760da2e3ebdSchin env->token.lex = c;
761da2e3ebdSchin c = C_ESC;
762da2e3ebdSchin }
763da2e3ebdSchin return c;
764da2e3ebdSchin case T_BACK+0:
765da2e3ebdSchin case T_BACK+1:
766da2e3ebdSchin case T_BACK+2:
767da2e3ebdSchin case T_BACK+3:
768da2e3ebdSchin case T_BACK+4:
769da2e3ebdSchin case T_BACK+5:
770da2e3ebdSchin case T_BACK+6:
771da2e3ebdSchin case T_BACK+7:
772da2e3ebdSchin n = chresc(sp - 2, &ep);
773da2e3ebdSchin if (ep > sp + 1)
774da2e3ebdSchin {
775da2e3ebdSchin env->token.len += ep - sp;
776da2e3ebdSchin return n;
777da2e3ebdSchin }
778da2e3ebdSchin /*FALLTHROUGH*/
779da2e3ebdSchin case T_BACK+8:
780da2e3ebdSchin case T_BACK+9:
781*b30d1939SAndy Fiddaman if (env->type == SRE || c == T_BACK && !(env->flags & (REG_LENIENT|REG_REGEXP)))
782da2e3ebdSchin {
783da2e3ebdSchin env->error = REG_BADESC;
784da2e3ebdSchin goto bad;
785da2e3ebdSchin }
786da2e3ebdSchin if ((env->flags & REG_MULTIREF) && isdigit(*sp))
787da2e3ebdSchin {
788da2e3ebdSchin c = (c - T_BACK) * 10 + (*sp - '0');
789da2e3ebdSchin if (c > 0 && c <= env->parno && env->paren[c])
790da2e3ebdSchin c += T_BACK;
791da2e3ebdSchin else
792da2e3ebdSchin c = chresc(sp - 2, &ep);
793da2e3ebdSchin env->token.len++;
794da2e3ebdSchin }
795da2e3ebdSchin if (c == T_BACK)
796da2e3ebdSchin c = 0;
797da2e3ebdSchin break;
798da2e3ebdSchin case T_BAD:
799*b30d1939SAndy Fiddaman if (escaped == 1 && (env->flags & (REG_LENIENT|REG_REGEXP)) && (c = mp[env->type+escaped+2]) >= T_META)
800da2e3ebdSchin return c;
801da2e3ebdSchin goto bad;
802da2e3ebdSchin }
803da2e3ebdSchin if (env->type >= SRE)
804da2e3ebdSchin {
805da2e3ebdSchin if (c == T_DOT)
806da2e3ebdSchin c = '.';
807da2e3ebdSchin else if (c < T_OPEN)
808da2e3ebdSchin {
809da2e3ebdSchin if (env->type == KRE && *(env->cursor + env->token.len) == '-' && *(env->cursor + env->token.len + 1) == '(')
810da2e3ebdSchin {
811da2e3ebdSchin env->token.len++;
812da2e3ebdSchin env->token.att = 1;
813da2e3ebdSchin }
814da2e3ebdSchin if (env->type == KRE && *(env->cursor + env->token.len) == '(')
815da2e3ebdSchin {
816da2e3ebdSchin env->token.len++;
817da2e3ebdSchin switch (c)
818da2e3ebdSchin {
819da2e3ebdSchin case T_AT:
820da2e3ebdSchin break;
821da2e3ebdSchin case T_PERCENT:
822da2e3ebdSchin env->token.lex = c;
823da2e3ebdSchin goto group;
824da2e3ebdSchin case T_TILDE:
825da2e3ebdSchin env->token.lex = 0;
826da2e3ebdSchin goto group;
827da2e3ebdSchin default:
828da2e3ebdSchin env->token.lex = c;
829da2e3ebdSchin break;
830da2e3ebdSchin }
831da2e3ebdSchin c = T_OPEN;
832da2e3ebdSchin }
833da2e3ebdSchin else if (c == T_STAR)
834da2e3ebdSchin c = T_DOTSTAR;
835da2e3ebdSchin else if (c == T_QUES)
836da2e3ebdSchin c = T_DOT;
837da2e3ebdSchin else
838da2e3ebdSchin {
839da2e3ebdSchin c = o;
840da2e3ebdSchin env->token.len = l;
841da2e3ebdSchin }
842da2e3ebdSchin }
843da2e3ebdSchin else if (c > T_BACK)
844da2e3ebdSchin {
845da2e3ebdSchin c = (c - T_BACK) * 2 - 1;
846da2e3ebdSchin c = (c > env->parno || !env->paren[c]) ? o : T_BACK + c;
847da2e3ebdSchin }
848da2e3ebdSchin else if (env->type == KRE && !env->parnest && (env->flags & REG_SHELL_GROUP))
849da2e3ebdSchin {
850da2e3ebdSchin if (c == T_AND)
851da2e3ebdSchin c = '&';
852da2e3ebdSchin else if (c == T_BAR)
853da2e3ebdSchin c = '|';
854da2e3ebdSchin else if (c == T_OPEN)
855da2e3ebdSchin c = '(';
856da2e3ebdSchin }
857da2e3ebdSchin }
858da2e3ebdSchin }
859da2e3ebdSchin }
860da2e3ebdSchin else if (escaped == 2)
861da2e3ebdSchin {
862da2e3ebdSchin if (env->type >= SRE && !(env->flags & REG_SHELL_ESCAPED) || (env->flags & REG_ESCAPE) && (c == '[' || c == '-' || c == ']' || env->delimiter && c == env->delimiter))
863da2e3ebdSchin /*ok*/;
864da2e3ebdSchin else
865da2e3ebdSchin {
866da2e3ebdSchin env->error = REG_BADESC;
867da2e3ebdSchin goto bad;
868da2e3ebdSchin }
869da2e3ebdSchin }
870*b30d1939SAndy Fiddaman else if (escaped && !(env->flags & (REG_LENIENT|REG_REGEXP)) && c != ']')
871da2e3ebdSchin {
872da2e3ebdSchin env->error = REG_BADESC;
873da2e3ebdSchin goto bad;
874da2e3ebdSchin }
875da2e3ebdSchin return c;
876da2e3ebdSchin group:
877da2e3ebdSchin sp = (char*)env->cursor + env->token.len;
878da2e3ebdSchin switch (*sp++)
879da2e3ebdSchin {
880da2e3ebdSchin case ')':
881da2e3ebdSchin break;
882da2e3ebdSchin case '#':
883da2e3ebdSchin for (;;)
884da2e3ebdSchin {
885da2e3ebdSchin switch (*sp++)
886da2e3ebdSchin {
887da2e3ebdSchin case 0:
888da2e3ebdSchin env->error = REG_EPAREN;
889da2e3ebdSchin return T_BAD;
890da2e3ebdSchin case ')':
891da2e3ebdSchin break;
892da2e3ebdSchin default:
893da2e3ebdSchin continue;
894da2e3ebdSchin }
895da2e3ebdSchin break;
896da2e3ebdSchin }
897da2e3ebdSchin break;
898da2e3ebdSchin default:
899da2e3ebdSchin return T_GROUP;
900da2e3ebdSchin }
901da2e3ebdSchin env->cursor = (unsigned char*)sp;
902da2e3ebdSchin return token(env);
903da2e3ebdSchin bad:
904da2e3ebdSchin if (escaped == 2)
905da2e3ebdSchin env->error = e;
906*b30d1939SAndy Fiddaman else if (env->flags & (REG_LENIENT|REG_REGEXP))
907da2e3ebdSchin return o;
908da2e3ebdSchin else if (escaped == 1 && !env->error)
909da2e3ebdSchin {
910da2e3ebdSchin if (mp || o == ']')
911da2e3ebdSchin return o;
912da2e3ebdSchin env->error = REG_BADESC;
913da2e3ebdSchin }
914da2e3ebdSchin return T_BAD;
915da2e3ebdSchin }
916da2e3ebdSchin
917da2e3ebdSchin static int
token(register Cenv_t * env)918da2e3ebdSchin token(register Cenv_t* env)
919da2e3ebdSchin {
920da2e3ebdSchin int c;
921da2e3ebdSchin int posixkludge;
922da2e3ebdSchin
923da2e3ebdSchin if (env->token.push)
924da2e3ebdSchin return env->token.lex;
925da2e3ebdSchin env->token.att = env->token.esc = 0;
926da2e3ebdSchin if ((env->token.len = MBSIZE(env->cursor)) > 1)
927da2e3ebdSchin return env->token.lex = C_MB;
928da2e3ebdSchin env->token.lex = 0;
929da2e3ebdSchin for (;;)
930da2e3ebdSchin {
931da2e3ebdSchin c = *env->cursor;
932da2e3ebdSchin if (c == 0 || c == env->delimiter || c == env->terminator)
933da2e3ebdSchin return T_END;
934da2e3ebdSchin if (!(env->flags & REG_COMMENT))
935da2e3ebdSchin break;
936da2e3ebdSchin if (c == '#')
937da2e3ebdSchin {
938da2e3ebdSchin do
939da2e3ebdSchin {
940da2e3ebdSchin c = *++env->cursor;
941da2e3ebdSchin if (c == 0 || c == env->delimiter)
942da2e3ebdSchin return T_END;
943da2e3ebdSchin } while (c != '\n');
944da2e3ebdSchin }
945da2e3ebdSchin else if (!isspace(c))
946da2e3ebdSchin break;
947da2e3ebdSchin env->cursor++;
948da2e3ebdSchin }
949da2e3ebdSchin if (c == '\n' && (env->flags & REG_MULTIPLE) && !env->delimiter)
950da2e3ebdSchin {
951da2e3ebdSchin if (env->parnest)
952da2e3ebdSchin {
953da2e3ebdSchin env->error = REG_EPAREN;
954da2e3ebdSchin return T_BAD;
955da2e3ebdSchin }
956da2e3ebdSchin env->parno = 0;
957da2e3ebdSchin env->pattern = env->cursor + 1;
958da2e3ebdSchin return T_BAR;
959da2e3ebdSchin }
960da2e3ebdSchin if (env->flags & REG_LITERAL)
961da2e3ebdSchin return c;
962da2e3ebdSchin if (posixkludge = env->posixkludge)
963da2e3ebdSchin {
964da2e3ebdSchin env->posixkludge = 0;
965da2e3ebdSchin if (c == '*')
966da2e3ebdSchin return c;
967da2e3ebdSchin }
968da2e3ebdSchin if (c == '\\')
969da2e3ebdSchin {
970da2e3ebdSchin if (env->flags & REG_SHELL_ESCAPED)
971da2e3ebdSchin return c;
972da2e3ebdSchin if (!(c = *(env->cursor + 1)) || c == env->terminator)
973da2e3ebdSchin {
974*b30d1939SAndy Fiddaman if (env->flags & (REG_LENIENT|REG_REGEXP))
975da2e3ebdSchin {
976da2e3ebdSchin if (c)
977da2e3ebdSchin {
978da2e3ebdSchin env->token.esc = env->token.len;
979da2e3ebdSchin env->token.len += MBSIZE(env->cursor + 1);
980da2e3ebdSchin return c;
981da2e3ebdSchin }
982da2e3ebdSchin return '\\';
983da2e3ebdSchin }
984da2e3ebdSchin env->error = REG_EESCAPE;
985da2e3ebdSchin return T_BAD;
986da2e3ebdSchin }
987da2e3ebdSchin env->token.esc = env->token.len;
988da2e3ebdSchin env->token.len += MBSIZE(env->cursor + 1);
989da2e3ebdSchin if (env->delimiter && c == 'n')
990da2e3ebdSchin return '\n';
991da2e3ebdSchin else if (c == env->delimiter)
992da2e3ebdSchin return magic(env, c, 0);
993da2e3ebdSchin else if (c == '(' && env->type == BRE)
994da2e3ebdSchin env->posixkludge = 1;
995da2e3ebdSchin else if (c == ')' && env->type == BRE && env->parnest <= 0)
996da2e3ebdSchin {
997da2e3ebdSchin env->error = REG_EPAREN;
998da2e3ebdSchin return T_BAD;
999da2e3ebdSchin }
1000da2e3ebdSchin else if (isspace(c) && (env->flags & REG_COMMENT))
1001da2e3ebdSchin return c;
1002da2e3ebdSchin return magic(env, c, 1);
1003da2e3ebdSchin }
1004da2e3ebdSchin else if (c == '$')
1005da2e3ebdSchin {
1006da2e3ebdSchin if (env->type == BRE && (*(env->cursor + 1) == 0 || *(env->cursor + 1) == env->delimiter || *(env->cursor + 1) == env->terminator || *(env->cursor + 1) == '\\' && *(env->cursor + 2) == ')') || (env->flags & REG_MULTIPLE) && *(env->cursor + 1) == '\n')
1007da2e3ebdSchin return T_DOLL;
1008da2e3ebdSchin }
1009da2e3ebdSchin else if (c == '^')
1010da2e3ebdSchin {
10113e14f97fSRoger A. Faulkner if (env->type == BRE && (env->cursor == env->pattern || posixkludge == 1))
1012da2e3ebdSchin {
10133e14f97fSRoger A. Faulkner env->posixkludge = 2;
1014da2e3ebdSchin return T_CFLX;
1015da2e3ebdSchin }
1016da2e3ebdSchin }
1017da2e3ebdSchin else if (c == ')')
1018da2e3ebdSchin {
1019da2e3ebdSchin if (env->type != BRE && env->parnest <= 0)
1020da2e3ebdSchin return c;
1021da2e3ebdSchin }
1022da2e3ebdSchin else if (c == '/' && env->explicit == env->mappedslash)
1023da2e3ebdSchin {
1024da2e3ebdSchin while (*(env->cursor + env->token.len) == c)
1025da2e3ebdSchin env->token.len++;
1026da2e3ebdSchin return T_SLASHPLUS;
1027da2e3ebdSchin }
1028da2e3ebdSchin return magic(env, c, 0);
1029da2e3ebdSchin }
1030da2e3ebdSchin
1031da2e3ebdSchin static Celt_t*
col(Celt_t * ce,int ic,unsigned char * bp,int bw,int bc,unsigned char * ep,int ew,int ec)1032da2e3ebdSchin col(Celt_t* ce, int ic, unsigned char* bp, int bw, int bc, unsigned char* ep, int ew, int ec)
1033da2e3ebdSchin {
10347c2fbfb3SApril Chin register char* s;
1035da2e3ebdSchin register unsigned char* k;
1036da2e3ebdSchin register unsigned char* e;
1037da2e3ebdSchin register int c;
1038da2e3ebdSchin register int cc;
1039da2e3ebdSchin int bt;
1040da2e3ebdSchin int et;
1041da2e3ebdSchin Ckey_t key;
1042da2e3ebdSchin
1043da2e3ebdSchin cc = 0;
1044da2e3ebdSchin for (;;)
1045da2e3ebdSchin {
1046da2e3ebdSchin k = key;
1047da2e3ebdSchin if (bw == 1)
1048da2e3ebdSchin {
1049da2e3ebdSchin c = bc;
1050da2e3ebdSchin if (ic)
1051da2e3ebdSchin {
10527c2fbfb3SApril Chin if (isupper(c))
1053da2e3ebdSchin {
10547c2fbfb3SApril Chin c = tolower(c);
10557c2fbfb3SApril Chin cc = -1;
1056da2e3ebdSchin }
10577c2fbfb3SApril Chin else if (islower(c))
1058da2e3ebdSchin {
10597c2fbfb3SApril Chin c = toupper(c);
10607c2fbfb3SApril Chin cc = -1;
1061da2e3ebdSchin }
1062da2e3ebdSchin }
1063da2e3ebdSchin *k++ = c;
1064da2e3ebdSchin }
1065da2e3ebdSchin else if (bw < COLL_KEY_MAX)
1066da2e3ebdSchin {
10677c2fbfb3SApril Chin s = (char*)bp;
10687c2fbfb3SApril Chin if (ic)
1069da2e3ebdSchin {
10707c2fbfb3SApril Chin c = mbchar(s);
10717c2fbfb3SApril Chin if (iswupper(c))
1072da2e3ebdSchin {
10737c2fbfb3SApril Chin c = towlower(c);
10747c2fbfb3SApril Chin cc = 1;
1075da2e3ebdSchin }
10767c2fbfb3SApril Chin else if (iswlower(c))
10777c2fbfb3SApril Chin {
10787c2fbfb3SApril Chin c = towupper(c);
10797c2fbfb3SApril Chin cc = 1;
10807c2fbfb3SApril Chin }
10817c2fbfb3SApril Chin }
10827c2fbfb3SApril Chin if (cc > 0)
10837c2fbfb3SApril Chin {
10847c2fbfb3SApril Chin cc = -1;
10853e14f97fSRoger A. Faulkner k += mbconv((char*)k, c);
1086da2e3ebdSchin }
10877c2fbfb3SApril Chin else
10887c2fbfb3SApril Chin for (e = k + bw; k < e; *k++ = *s++);
1089da2e3ebdSchin }
1090da2e3ebdSchin *k = 0;
1091da2e3ebdSchin mbxfrm(ce->beg, key, COLL_KEY_MAX);
1092da2e3ebdSchin if (ep)
1093da2e3ebdSchin {
1094da2e3ebdSchin k = key;
1095da2e3ebdSchin c = mbchar(k);
1096da2e3ebdSchin if (iswupper(c))
1097da2e3ebdSchin bt = COLL_range_uc;
1098da2e3ebdSchin else if (iswlower(c))
1099da2e3ebdSchin bt = COLL_range_lc;
1100da2e3ebdSchin else
1101da2e3ebdSchin bt = COLL_range;
1102da2e3ebdSchin k = key;
1103da2e3ebdSchin if (ew == 1)
1104da2e3ebdSchin {
1105da2e3ebdSchin c = ec;
1106da2e3ebdSchin if (ic)
1107da2e3ebdSchin {
11087c2fbfb3SApril Chin if (isupper(c))
1109da2e3ebdSchin {
11107c2fbfb3SApril Chin c = tolower(c);
11117c2fbfb3SApril Chin cc = -1;
1112da2e3ebdSchin }
11137c2fbfb3SApril Chin else if (islower(c))
1114da2e3ebdSchin {
11157c2fbfb3SApril Chin c = toupper(c);
11167c2fbfb3SApril Chin cc = -1;
1117da2e3ebdSchin }
1118da2e3ebdSchin }
1119da2e3ebdSchin *k++ = c;
1120da2e3ebdSchin }
1121da2e3ebdSchin else if (ew < COLL_KEY_MAX)
1122da2e3ebdSchin {
11237c2fbfb3SApril Chin s = (char*)ep;
11247c2fbfb3SApril Chin if (ic)
1125da2e3ebdSchin {
11267c2fbfb3SApril Chin c = mbchar(s);
11277c2fbfb3SApril Chin if (iswupper(c))
1128da2e3ebdSchin {
11297c2fbfb3SApril Chin c = towlower(c);
11307c2fbfb3SApril Chin cc = 1;
11317c2fbfb3SApril Chin }
11327c2fbfb3SApril Chin else if (iswlower(c))
11337c2fbfb3SApril Chin {
11347c2fbfb3SApril Chin c = towupper(c);
11357c2fbfb3SApril Chin cc = 1;
1136da2e3ebdSchin }
1137da2e3ebdSchin }
11387c2fbfb3SApril Chin if (cc > 0)
11397c2fbfb3SApril Chin {
11407c2fbfb3SApril Chin cc = -1;
11413e14f97fSRoger A. Faulkner k += mbconv((char*)k, c);
11427c2fbfb3SApril Chin }
11437c2fbfb3SApril Chin else
11447c2fbfb3SApril Chin for (e = k + ew; k < e; *k++ = *s++);
1145da2e3ebdSchin }
1146da2e3ebdSchin *k = 0;
1147da2e3ebdSchin mbxfrm(ce->end, key, COLL_KEY_MAX);
1148da2e3ebdSchin k = key;
1149da2e3ebdSchin c = mbchar(k);
1150da2e3ebdSchin if (iswupper(c))
1151da2e3ebdSchin et = COLL_range_uc;
1152da2e3ebdSchin else if (iswlower(c))
1153da2e3ebdSchin et = COLL_range_lc;
1154da2e3ebdSchin else
1155da2e3ebdSchin et = COLL_range;
1156da2e3ebdSchin ce->typ = bt == et ? bt : COLL_range;
1157da2e3ebdSchin }
1158da2e3ebdSchin else
1159da2e3ebdSchin ce->typ = COLL_char;
1160da2e3ebdSchin ce++;
1161da2e3ebdSchin if (!ic || !cc)
1162da2e3ebdSchin break;
1163da2e3ebdSchin ic = 0;
1164da2e3ebdSchin }
1165da2e3ebdSchin return ce;
1166da2e3ebdSchin }
1167da2e3ebdSchin
1168da2e3ebdSchin static Rex_t*
bra(Cenv_t * env)1169da2e3ebdSchin bra(Cenv_t* env)
1170da2e3ebdSchin {
1171da2e3ebdSchin Rex_t* e;
1172da2e3ebdSchin int c;
1173da2e3ebdSchin int i;
1174da2e3ebdSchin int w;
1175da2e3ebdSchin int neg;
1176da2e3ebdSchin int last;
1177da2e3ebdSchin int inrange;
1178da2e3ebdSchin int complicated;
1179da2e3ebdSchin int collate;
1180da2e3ebdSchin int elements;
1181da2e3ebdSchin unsigned char* first;
1182da2e3ebdSchin unsigned char* start;
1183da2e3ebdSchin unsigned char* begin;
1184da2e3ebdSchin unsigned char* s;
1185da2e3ebdSchin regclass_t f;
1186da2e3ebdSchin unsigned char buf[4 * (COLL_KEY_MAX + 1)];
1187da2e3ebdSchin #if _PACKAGE_ast
1188da2e3ebdSchin int ic;
1189da2e3ebdSchin char mbc[COLL_KEY_MAX + 1];
1190da2e3ebdSchin #endif
1191da2e3ebdSchin
1192da2e3ebdSchin if (!(e = node(env, REX_CLASS, 1, 1, sizeof(Set_t))))
1193da2e3ebdSchin return 0;
1194da2e3ebdSchin collate = complicated = elements = 0;
1195da2e3ebdSchin if (*env->cursor == '^' || env->type >= SRE && *env->cursor == '!')
1196da2e3ebdSchin {
1197da2e3ebdSchin env->cursor++;
1198*b30d1939SAndy Fiddaman complicated = neg = 1;
1199da2e3ebdSchin }
1200da2e3ebdSchin else
1201da2e3ebdSchin neg = 0;
12027c2fbfb3SApril Chin first = env->cursor;
12037c2fbfb3SApril Chin start = first + MBSIZE(first);
1204da2e3ebdSchin if (*env->cursor == 0 || *(env->cursor + 1) == 0 || *env->cursor == env->terminator || *(env->cursor + 1) == env->terminator || (env->flags & REG_ESCAPE) && (*env->cursor == env->delimiter || *env->cursor != '\\' && *(env->cursor + 1) == env->delimiter))
1205da2e3ebdSchin goto error;
1206da2e3ebdSchin begin = env->cursor + MBSIZE(env->cursor);
1207da2e3ebdSchin
1208da2e3ebdSchin /*
1209da2e3ebdSchin * inrange: 0=no, 1=possibly, 2=definitely
1210da2e3ebdSchin */
1211da2e3ebdSchin
1212da2e3ebdSchin inrange = 0;
1213da2e3ebdSchin for (;;)
1214da2e3ebdSchin {
12153e14f97fSRoger A. Faulkner if (!(c = *env->cursor) || c == env->terminator || c == env->delimiter && (env->flags & REG_ESCAPE))
1216da2e3ebdSchin goto error;
1217da2e3ebdSchin env->cursor += (w = MBSIZE(env->cursor));
1218*b30d1939SAndy Fiddaman if (c == '\\' && ((env->flags & REG_CLASS_ESCAPE) || *env->cursor == env->delimiter && (env->flags & REG_ESCAPE)))
1219da2e3ebdSchin {
1220da2e3ebdSchin if (*env->cursor)
1221da2e3ebdSchin {
1222da2e3ebdSchin if (*env->cursor == 'n')
1223da2e3ebdSchin {
1224da2e3ebdSchin env->cursor++;
1225da2e3ebdSchin c = '\n';
1226da2e3ebdSchin }
1227da2e3ebdSchin else if (env->type < SRE || !(env->flags & REG_SHELL_ESCAPED))
1228da2e3ebdSchin {
1229da2e3ebdSchin env->token.len = 1;
1230da2e3ebdSchin w = magic(env, *env->cursor, 2);
1231da2e3ebdSchin if (env->token.len > 1 || w != T_BAD)
1232da2e3ebdSchin {
1233da2e3ebdSchin if (env->token.len == 1 && (f = classfun(w)))
1234da2e3ebdSchin {
1235da2e3ebdSchin if (inrange > 1)
1236da2e3ebdSchin {
1237*b30d1939SAndy Fiddaman if (env->type < SRE && !(env->flags & (REG_LENIENT|REG_REGEXP)))
1238da2e3ebdSchin goto erange;
1239da2e3ebdSchin inrange = 0;
1240da2e3ebdSchin }
1241da2e3ebdSchin env->cursor++;
1242da2e3ebdSchin for (c = 0; c <= UCHAR_MAX; c++)
1243da2e3ebdSchin if ((*f)(c))
1244da2e3ebdSchin setadd(e->re.charclass, c);
1245da2e3ebdSchin complicated++;
1246da2e3ebdSchin elements++;
1247da2e3ebdSchin continue;
1248da2e3ebdSchin }
1249da2e3ebdSchin if (env->token.len > 1 || w >= 0 && w < T_META)
1250da2e3ebdSchin {
1251da2e3ebdSchin c = w;
1252da2e3ebdSchin if (c > UCHAR_MAX)
1253da2e3ebdSchin {
1254*b30d1939SAndy Fiddaman if (env->type < SRE && !(env->flags & (REG_LENIENT|REG_REGEXP)) && !mbwide())
1255da2e3ebdSchin goto erange;
1256da2e3ebdSchin c = UCHAR_MAX;
1257da2e3ebdSchin }
1258da2e3ebdSchin env->cursor += env->token.len;
1259da2e3ebdSchin }
1260da2e3ebdSchin }
1261da2e3ebdSchin }
1262da2e3ebdSchin }
1263da2e3ebdSchin }
1264da2e3ebdSchin else if (c == ']')
1265da2e3ebdSchin {
1266da2e3ebdSchin if (env->cursor == begin)
1267da2e3ebdSchin {
1268da2e3ebdSchin last = c;
1269da2e3ebdSchin inrange = 1;
1270da2e3ebdSchin continue;
1271da2e3ebdSchin }
1272da2e3ebdSchin if (inrange != 0)
1273da2e3ebdSchin {
1274da2e3ebdSchin setadd(e->re.charclass, last);
1275da2e3ebdSchin elements++;
1276da2e3ebdSchin if (inrange == 2)
1277da2e3ebdSchin {
1278da2e3ebdSchin setadd(e->re.charclass, '-');
1279da2e3ebdSchin elements++;
1280da2e3ebdSchin }
1281da2e3ebdSchin }
1282da2e3ebdSchin break;
1283da2e3ebdSchin }
1284da2e3ebdSchin else if (c == '-')
1285da2e3ebdSchin {
1286da2e3ebdSchin if (!inrange && env->cursor != begin && *env->cursor != ']')
1287da2e3ebdSchin {
1288*b30d1939SAndy Fiddaman if (env->type < SRE && !(env->flags & (REG_LENIENT|REG_REGEXP)))
1289da2e3ebdSchin goto erange;
1290da2e3ebdSchin continue;
1291da2e3ebdSchin }
1292da2e3ebdSchin else if (inrange == 1)
1293da2e3ebdSchin {
1294da2e3ebdSchin inrange = 2;
1295da2e3ebdSchin complicated++;
1296da2e3ebdSchin continue;
1297da2e3ebdSchin }
1298da2e3ebdSchin }
1299da2e3ebdSchin else if (c == '[')
1300da2e3ebdSchin {
1301da2e3ebdSchin switch (*env->cursor)
1302da2e3ebdSchin {
1303da2e3ebdSchin case 0:
1304da2e3ebdSchin goto error;
1305da2e3ebdSchin case ':':
1306*b30d1939SAndy Fiddaman if (env->flags & REG_REGEXP)
130734f9b3eeSRoland Mainz goto normal;
1308da2e3ebdSchin if (inrange == 1)
1309da2e3ebdSchin {
1310da2e3ebdSchin setadd(e->re.charclass, last);
1311da2e3ebdSchin elements++;
1312da2e3ebdSchin }
1313da2e3ebdSchin if (!(f = regclass((char*)env->cursor, (char**)&env->cursor)))
1314da2e3ebdSchin {
1315da2e3ebdSchin if (env->cursor == start && (c = *(env->cursor + 1)))
1316da2e3ebdSchin {
1317da2e3ebdSchin s = start = env->cursor + 1;
1318da2e3ebdSchin while (*++s && *s != ':');
1319da2e3ebdSchin if (*s == ':' && *(s + 1) == ']' && *(s + 2) == ']')
1320da2e3ebdSchin {
1321da2e3ebdSchin if ((i = (s - start)) == 1)
1322da2e3ebdSchin {
1323da2e3ebdSchin switch (c)
1324da2e3ebdSchin {
1325da2e3ebdSchin case '<':
1326da2e3ebdSchin i = REX_WBEG;
1327da2e3ebdSchin break;
1328da2e3ebdSchin case '>':
1329da2e3ebdSchin i = REX_WEND;
1330da2e3ebdSchin break;
1331da2e3ebdSchin default:
1332da2e3ebdSchin i = 0;
1333da2e3ebdSchin break;
1334da2e3ebdSchin }
1335da2e3ebdSchin if (i)
1336da2e3ebdSchin {
1337da2e3ebdSchin env->cursor = s + 3;
1338da2e3ebdSchin drop(env->disc, e);
1339da2e3ebdSchin return node(env, i, 0, 0, 0);
1340da2e3ebdSchin }
1341da2e3ebdSchin }
1342da2e3ebdSchin }
1343da2e3ebdSchin }
1344da2e3ebdSchin env->error = REG_ECTYPE;
1345da2e3ebdSchin goto error;
1346da2e3ebdSchin }
1347da2e3ebdSchin for (c = 0; c <= UCHAR_MAX; c++)
1348da2e3ebdSchin if ((*f)(c))
1349da2e3ebdSchin setadd(e->re.charclass, c);
1350da2e3ebdSchin inrange = 0;
1351da2e3ebdSchin complicated++;
1352da2e3ebdSchin elements++;
1353da2e3ebdSchin continue;
1354da2e3ebdSchin case '=':
1355*b30d1939SAndy Fiddaman if (env->flags & REG_REGEXP)
135634f9b3eeSRoland Mainz goto normal;
1357da2e3ebdSchin if (inrange == 2)
1358da2e3ebdSchin goto erange;
1359da2e3ebdSchin if (inrange == 1)
1360da2e3ebdSchin {
1361da2e3ebdSchin setadd(e->re.charclass, last);
1362da2e3ebdSchin elements++;
1363da2e3ebdSchin }
1364*b30d1939SAndy Fiddaman if ((c = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)buf, sizeof(buf), NiL)) < 0)
1365da2e3ebdSchin goto ecollate;
1366da2e3ebdSchin if (c > 1)
1367da2e3ebdSchin collate++;
1368da2e3ebdSchin else
1369da2e3ebdSchin setadd(e->re.charclass, buf[0]);
1370da2e3ebdSchin c = buf[0];
1371da2e3ebdSchin inrange = 0;
1372da2e3ebdSchin complicated++;
1373da2e3ebdSchin elements++;
1374da2e3ebdSchin continue;
1375da2e3ebdSchin case '.':
1376*b30d1939SAndy Fiddaman if (env->flags & REG_REGEXP)
137734f9b3eeSRoland Mainz goto normal;
1378*b30d1939SAndy Fiddaman if ((c = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)buf, sizeof(buf), NiL)) < 0)
1379da2e3ebdSchin goto ecollate;
1380da2e3ebdSchin if (c > 1)
1381da2e3ebdSchin collate++;
1382da2e3ebdSchin c = buf[0];
1383da2e3ebdSchin complicated++;
1384da2e3ebdSchin break;
1385da2e3ebdSchin default:
138634f9b3eeSRoland Mainz normal:
1387da2e3ebdSchin if (*env->cursor == env->terminator || *env->cursor == env->delimiter && (env->flags & REG_ESCAPE))
1388da2e3ebdSchin goto error;
1389da2e3ebdSchin break;
1390da2e3ebdSchin }
1391da2e3ebdSchin }
1392da2e3ebdSchin else if (w > 1)
1393da2e3ebdSchin complicated++;
1394da2e3ebdSchin if (inrange == 2)
1395da2e3ebdSchin {
13963e14f97fSRoger A. Faulkner if (last <= c)
13973e14f97fSRoger A. Faulkner {
13983e14f97fSRoger A. Faulkner for (i = last; i <= c; i++)
13993e14f97fSRoger A. Faulkner setadd(e->re.charclass, i);
1400*b30d1939SAndy Fiddaman inrange = env->type >= SRE || (env->flags & (REG_LENIENT|REG_REGEXP));
14013e14f97fSRoger A. Faulkner elements += 2;
14023e14f97fSRoger A. Faulkner }
14033e14f97fSRoger A. Faulkner else if (env->type >= SRE)
1404da2e3ebdSchin {
1405da2e3ebdSchin setadd(e->re.charclass, last);
1406da2e3ebdSchin setadd(e->re.charclass, c);
14073e14f97fSRoger A. Faulkner elements += 2;
14083e14f97fSRoger A. Faulkner inrange = 1;
1409da2e3ebdSchin }
1410*b30d1939SAndy Fiddaman else if (!(env->flags & (REG_LENIENT|REG_REGEXP)))
14113e14f97fSRoger A. Faulkner goto erange;
1412da2e3ebdSchin else
14133e14f97fSRoger A. Faulkner inrange = 0;
1414da2e3ebdSchin }
1415da2e3ebdSchin else if (inrange == 1)
1416da2e3ebdSchin {
1417da2e3ebdSchin setadd(e->re.charclass, last);
1418da2e3ebdSchin elements++;
1419da2e3ebdSchin }
1420da2e3ebdSchin else
1421da2e3ebdSchin inrange = 1;
1422da2e3ebdSchin last = c;
1423da2e3ebdSchin }
1424da2e3ebdSchin #if _PACKAGE_ast
1425da2e3ebdSchin if (complicated && mbcoll())
1426da2e3ebdSchin {
1427da2e3ebdSchin Dt_t* dt;
1428da2e3ebdSchin Cchr_t* cc;
1429da2e3ebdSchin Cchr_t* tc;
1430da2e3ebdSchin Cchr_t* xc;
1431da2e3ebdSchin Celt_t* ce;
1432da2e3ebdSchin Cchr_t key;
1433da2e3ebdSchin int rw;
1434da2e3ebdSchin int rc;
1435*b30d1939SAndy Fiddaman wchar_t wc;
1436da2e3ebdSchin unsigned char* rp;
1437da2e3ebdSchin unsigned char* pp;
14387c2fbfb3SApril Chin char cb[2][COLL_KEY_MAX+1];
1439da2e3ebdSchin
1440da2e3ebdSchin static Dtdisc_t disc;
1441da2e3ebdSchin
1442da2e3ebdSchin static const char primary[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
1443da2e3ebdSchin
1444da2e3ebdSchin if (!(dt = (Dt_t*)LCINFO(AST_LC_COLLATE)->data))
1445da2e3ebdSchin {
1446da2e3ebdSchin disc.key = offsetof(Cchr_t, key);
1447*b30d1939SAndy Fiddaman if ((cc = newof(0, Cchr_t, elementsof(primary), 0)) && (dt = dtopen(&disc, Dtoset)))
1448da2e3ebdSchin {
1449da2e3ebdSchin for (i = 0; i < elementsof(primary) - 1; i++, cc++)
1450da2e3ebdSchin {
1451da2e3ebdSchin cc->nam[0] = primary[i];
1452da2e3ebdSchin mbxfrm(cc->key, cc->nam, COLL_KEY_MAX);
1453da2e3ebdSchin dtinsert(dt, cc);
1454da2e3ebdSchin }
1455da2e3ebdSchin for (i = 0; i < elementsof(cc->key); i++)
1456da2e3ebdSchin cc->key[i] = ~0;
1457da2e3ebdSchin dtinsert(dt, cc);
1458da2e3ebdSchin LCINFO(AST_LC_COLLATE)->data = (void*)dt;
1459da2e3ebdSchin }
1460da2e3ebdSchin else
1461da2e3ebdSchin {
1462da2e3ebdSchin if (cc)
1463da2e3ebdSchin free(cc);
1464da2e3ebdSchin drop(env->disc, e);
1465da2e3ebdSchin return 0;
1466da2e3ebdSchin }
1467da2e3ebdSchin }
1468da2e3ebdSchin if (dt)
1469da2e3ebdSchin {
1470da2e3ebdSchin drop(env->disc, e);
1471da2e3ebdSchin if (ic = env->flags & REG_ICASE)
1472da2e3ebdSchin elements *= 2;
1473*b30d1939SAndy Fiddaman if (!(e = node(env, REX_COLL_CLASS, 1, 1, (elements + 3) * sizeof(Celt_t))))
1474da2e3ebdSchin return 0;
1475da2e3ebdSchin ce = (Celt_t*)e->re.data;
1476da2e3ebdSchin e->re.collate.invert = neg;
1477da2e3ebdSchin e->re.collate.elements = ce;
1478da2e3ebdSchin env->cursor = first;
1479da2e3ebdSchin inrange = 0;
1480da2e3ebdSchin for (;;)
1481da2e3ebdSchin {
1482da2e3ebdSchin if ((c = *env->cursor) == 0 || c == env->terminator || (env->flags & REG_ESCAPE) && c == env->delimiter)
1483da2e3ebdSchin goto error;
1484da2e3ebdSchin pp = env->cursor;
1485da2e3ebdSchin env->cursor += (w = MBSIZE(env->cursor));
1486*b30d1939SAndy Fiddaman if (c == '\\' && ((env->flags & REG_CLASS_ESCAPE) || *env->cursor == env->delimiter && (env->flags & REG_ESCAPE)))
1487da2e3ebdSchin {
1488da2e3ebdSchin if (*env->cursor)
1489da2e3ebdSchin {
1490da2e3ebdSchin if (*env->cursor == 'n')
1491da2e3ebdSchin {
1492da2e3ebdSchin pp = env->cursor++;
1493da2e3ebdSchin c = '\n';
1494da2e3ebdSchin }
1495da2e3ebdSchin else if (env->type < SRE || !(env->flags & REG_SHELL_ESCAPED))
1496da2e3ebdSchin {
1497da2e3ebdSchin env->token.len = 1;
1498da2e3ebdSchin w = magic(env, *env->cursor, 2);
1499da2e3ebdSchin if (env->token.len > 1 || w != T_BAD)
1500da2e3ebdSchin {
1501da2e3ebdSchin if (env->token.len == 1 && (f = classfun(w)))
1502da2e3ebdSchin {
1503da2e3ebdSchin if (inrange > 1)
1504da2e3ebdSchin {
1505*b30d1939SAndy Fiddaman if (env->type < SRE && !(env->flags & (REG_LENIENT|REG_REGEXP)))
1506da2e3ebdSchin goto erange;
1507da2e3ebdSchin inrange = 0;
1508da2e3ebdSchin }
1509da2e3ebdSchin env->cursor++;
1510da2e3ebdSchin ce->fun = f;
1511da2e3ebdSchin ce->typ = COLL_call;
1512da2e3ebdSchin ce++;
1513da2e3ebdSchin continue;
1514da2e3ebdSchin }
1515da2e3ebdSchin if (env->token.len > 1 || w >= 0 && w < T_META)
1516da2e3ebdSchin {
1517da2e3ebdSchin c = w;
15183e14f97fSRoger A. Faulkner w = mbconv(mbc, c);
1519da2e3ebdSchin pp = (unsigned char*)mbc;
1520da2e3ebdSchin env->cursor += env->token.len;
1521da2e3ebdSchin }
1522da2e3ebdSchin }
1523da2e3ebdSchin }
1524da2e3ebdSchin }
1525da2e3ebdSchin }
1526da2e3ebdSchin else if (c == ']')
1527da2e3ebdSchin {
1528da2e3ebdSchin if (env->cursor == begin)
1529da2e3ebdSchin {
1530da2e3ebdSchin rp = pp;
1531da2e3ebdSchin rw = w;
1532da2e3ebdSchin inrange = 1;
1533da2e3ebdSchin continue;
1534da2e3ebdSchin }
1535da2e3ebdSchin if (inrange != 0)
1536da2e3ebdSchin {
1537da2e3ebdSchin ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
1538da2e3ebdSchin if (inrange == 2)
1539da2e3ebdSchin ce = col(ce, ic, NiL, 1, '-', NiL, 0, 0);
1540da2e3ebdSchin }
1541da2e3ebdSchin break;
1542da2e3ebdSchin }
1543da2e3ebdSchin else if (c == '-')
1544da2e3ebdSchin {
1545da2e3ebdSchin if (!inrange && env->cursor != begin && *env->cursor != ']')
1546da2e3ebdSchin {
1547*b30d1939SAndy Fiddaman if (env->type < SRE && !(env->flags & (REG_LENIENT|REG_REGEXP)))
1548da2e3ebdSchin goto erange;
1549da2e3ebdSchin continue;
1550da2e3ebdSchin }
1551da2e3ebdSchin else if (inrange == 1)
1552da2e3ebdSchin {
1553da2e3ebdSchin inrange = 2;
1554da2e3ebdSchin continue;
1555da2e3ebdSchin }
1556da2e3ebdSchin }
1557da2e3ebdSchin else if (c == '[')
1558da2e3ebdSchin {
1559da2e3ebdSchin switch (*env->cursor)
1560da2e3ebdSchin {
1561da2e3ebdSchin case 0:
1562da2e3ebdSchin goto error;
1563da2e3ebdSchin case ':':
1564*b30d1939SAndy Fiddaman if (env->flags & REG_REGEXP)
156534f9b3eeSRoland Mainz goto complicated_normal;
1566da2e3ebdSchin if (inrange == 1)
1567da2e3ebdSchin ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
1568da2e3ebdSchin if (!(f = regclass((char*)env->cursor, (char**)&env->cursor)))
1569da2e3ebdSchin {
1570da2e3ebdSchin if (env->cursor == start && (c = *(env->cursor + 1)) && *(env->cursor + 2) == ':' && *(env->cursor + 3) == ']' && *(env->cursor + 4) == ']')
1571da2e3ebdSchin {
1572da2e3ebdSchin switch (c)
1573da2e3ebdSchin {
1574da2e3ebdSchin case '<':
1575da2e3ebdSchin i = REX_WBEG;
1576da2e3ebdSchin break;
1577da2e3ebdSchin case '>':
1578da2e3ebdSchin i = REX_WEND;
1579da2e3ebdSchin break;
1580da2e3ebdSchin default:
1581da2e3ebdSchin i = 0;
1582da2e3ebdSchin break;
1583da2e3ebdSchin }
1584da2e3ebdSchin if (i)
1585da2e3ebdSchin {
1586da2e3ebdSchin env->cursor += 5;
1587da2e3ebdSchin drop(env->disc, e);
1588da2e3ebdSchin return node(env, i, 0, 0, 0);
1589da2e3ebdSchin }
1590da2e3ebdSchin }
1591da2e3ebdSchin env->error = REG_ECTYPE;
1592da2e3ebdSchin goto error;
1593da2e3ebdSchin }
1594da2e3ebdSchin ce->fun = f;
1595da2e3ebdSchin ce->typ = COLL_call;
1596da2e3ebdSchin ce++;
1597da2e3ebdSchin inrange = 0;
1598da2e3ebdSchin continue;
1599da2e3ebdSchin case '=':
1600*b30d1939SAndy Fiddaman if (env->flags & REG_REGEXP)
160134f9b3eeSRoland Mainz goto complicated_normal;
1602da2e3ebdSchin if (inrange == 2)
1603da2e3ebdSchin goto erange;
1604da2e3ebdSchin if (inrange == 1)
1605da2e3ebdSchin ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
16067c2fbfb3SApril Chin pp = (unsigned char*)cb[inrange];
1607da2e3ebdSchin rp = env->cursor + 1;
1608*b30d1939SAndy Fiddaman if ((rw = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)pp, COLL_KEY_MAX, &wc)) < 0)
1609da2e3ebdSchin goto ecollate;
1610da2e3ebdSchin c = 0;
1611da2e3ebdSchin if (ic)
1612da2e3ebdSchin {
16137c2fbfb3SApril Chin if (iswupper(wc))
1614da2e3ebdSchin {
16157c2fbfb3SApril Chin wc = towlower(wc);
16163e14f97fSRoger A. Faulkner rw = mbconv((char*)pp, wc);
16177c2fbfb3SApril Chin c = 'u';
1618da2e3ebdSchin }
16197c2fbfb3SApril Chin else if (iswlower(wc))
16207c2fbfb3SApril Chin c = 'l';
16217c2fbfb3SApril Chin }
1622*b30d1939SAndy Fiddaman i = 1;
16237c2fbfb3SApril Chin for (;;)
16247c2fbfb3SApril Chin {
16257c2fbfb3SApril Chin mbxfrm(key.key, (char*)pp, COLL_KEY_MAX);
16267c2fbfb3SApril Chin if (!(cc = (Cchr_t*)dtsearch(dt, &key)) && !(cc = (Cchr_t*)dtprev(dt, &key)))
1627*b30d1939SAndy Fiddaman {
1628*b30d1939SAndy Fiddaman if (i)
1629*b30d1939SAndy Fiddaman {
1630*b30d1939SAndy Fiddaman c = *pp;
1631*b30d1939SAndy Fiddaman goto singleton;
1632*b30d1939SAndy Fiddaman }
16337c2fbfb3SApril Chin goto ecollate;
1634*b30d1939SAndy Fiddaman }
16357c2fbfb3SApril Chin xc = (tc = (Cchr_t*)dtprev(dt, cc)) && !strcasecmp((char*)tc->nam, (char*)cc->nam) ? tc : cc;
16367c2fbfb3SApril Chin if (c == 'l' || c == 'L' && !(c = 0))
1637da2e3ebdSchin ce->typ = COLL_range_lc;
16387c2fbfb3SApril Chin else if (c == 'u' || c == 'U' && !(c = 0))
1639da2e3ebdSchin ce->typ = COLL_range_uc;
1640da2e3ebdSchin else
1641da2e3ebdSchin ce->typ = COLL_range;
1642da2e3ebdSchin strcpy((char*)ce->beg, (char*)xc->key);
1643da2e3ebdSchin if (!(cc = (Cchr_t*)dtnext(dt, cc)))
1644*b30d1939SAndy Fiddaman {
1645*b30d1939SAndy Fiddaman if (i)
1646*b30d1939SAndy Fiddaman {
1647*b30d1939SAndy Fiddaman c = *pp;
1648*b30d1939SAndy Fiddaman goto singleton;
1649*b30d1939SAndy Fiddaman }
1650da2e3ebdSchin goto ecollate;
1651*b30d1939SAndy Fiddaman }
1652da2e3ebdSchin if (!strcasecmp((char*)xc->nam, (char*)cc->nam) && (tc = (Cchr_t*)dtnext(dt, cc)))
1653da2e3ebdSchin cc = tc;
1654da2e3ebdSchin strcpy((char*)ce->end, (char*)cc->key);
1655da2e3ebdSchin ce->max = -1;
1656da2e3ebdSchin ce++;
1657da2e3ebdSchin if (!c)
1658da2e3ebdSchin break;
16597c2fbfb3SApril Chin if (c == 'u')
16607c2fbfb3SApril Chin {
16617c2fbfb3SApril Chin wc = towlower(wc);
16627c2fbfb3SApril Chin c = 'L';
16637c2fbfb3SApril Chin }
16647c2fbfb3SApril Chin else
16657c2fbfb3SApril Chin {
16667c2fbfb3SApril Chin wc = towupper(wc);
16677c2fbfb3SApril Chin c = 'U';
16687c2fbfb3SApril Chin }
16693e14f97fSRoger A. Faulkner rw = mbconv((char*)pp, wc);
1670*b30d1939SAndy Fiddaman i = 0;
1671da2e3ebdSchin }
1672da2e3ebdSchin inrange = 0;
16737c2fbfb3SApril Chin c = *pp;
1674da2e3ebdSchin continue;
1675da2e3ebdSchin case '.':
1676*b30d1939SAndy Fiddaman if (env->flags & REG_REGEXP)
167734f9b3eeSRoland Mainz goto complicated_normal;
16787c2fbfb3SApril Chin pp = (unsigned char*)cb[inrange];
1679*b30d1939SAndy Fiddaman if ((w = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)pp, COLL_KEY_MAX, NiL)) < 0)
1680da2e3ebdSchin goto ecollate;
1681*b30d1939SAndy Fiddaman c = *pp;
1682da2e3ebdSchin break;
1683da2e3ebdSchin default:
168434f9b3eeSRoland Mainz complicated_normal:
1685da2e3ebdSchin if (*env->cursor == env->terminator || *env->cursor == env->delimiter && (env->flags & REG_ESCAPE))
1686da2e3ebdSchin goto error;
1687da2e3ebdSchin break;
1688da2e3ebdSchin }
1689da2e3ebdSchin }
1690*b30d1939SAndy Fiddaman singleton:
1691da2e3ebdSchin if (inrange == 2)
1692da2e3ebdSchin {
1693da2e3ebdSchin ce = col(ce, ic, rp, rw, rc, pp, w, c);
1694da2e3ebdSchin if (strcmp((char*)ce->beg, (char*)ce->end) > 0)
1695da2e3ebdSchin {
1696*b30d1939SAndy Fiddaman if (env->type < SRE && !(env->flags & (REG_LENIENT|REG_REGEXP)))
1697da2e3ebdSchin goto erange;
1698da2e3ebdSchin (ce-1)->typ = COLL_char;
1699da2e3ebdSchin strcpy((char*)ce->beg, (char*)(ce-1)->end);
1700da2e3ebdSchin ce->typ = COLL_char;
1701da2e3ebdSchin ce++;
1702da2e3ebdSchin }
1703*b30d1939SAndy Fiddaman inrange = env->type >= SRE || (env->flags & (REG_LENIENT|REG_REGEXP));
1704da2e3ebdSchin }
1705da2e3ebdSchin else if (inrange == 1)
1706da2e3ebdSchin ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
1707da2e3ebdSchin else
1708da2e3ebdSchin inrange = 1;
1709da2e3ebdSchin rp = pp;
1710da2e3ebdSchin rw = w;
1711da2e3ebdSchin rc = c;
1712da2e3ebdSchin }
1713da2e3ebdSchin ce->typ = COLL_end;
1714da2e3ebdSchin return e;
1715da2e3ebdSchin }
1716da2e3ebdSchin }
1717da2e3ebdSchin #endif
1718da2e3ebdSchin if (collate)
1719da2e3ebdSchin goto ecollate;
1720da2e3ebdSchin if (env->flags & REG_ICASE)
1721da2e3ebdSchin for (i = 0; i <= UCHAR_MAX; i++)
1722da2e3ebdSchin if (settst(e->re.charclass, i))
1723da2e3ebdSchin {
1724da2e3ebdSchin if (isupper(i))
1725da2e3ebdSchin c = tolower(i);
1726da2e3ebdSchin else if (islower(i))
1727da2e3ebdSchin c = toupper(i);
1728da2e3ebdSchin else
1729da2e3ebdSchin continue;
1730da2e3ebdSchin setadd(e->re.charclass, c);
1731da2e3ebdSchin }
1732da2e3ebdSchin if (neg)
1733da2e3ebdSchin {
1734da2e3ebdSchin for (i = 0; i < elementsof(e->re.charclass->bits); i++)
1735da2e3ebdSchin e->re.charclass->bits[i] ^= ~0;
1736da2e3ebdSchin if (env->explicit >= 0)
1737da2e3ebdSchin setclr(e->re.charclass, env->explicit);
1738da2e3ebdSchin }
1739da2e3ebdSchin return e;
1740da2e3ebdSchin ecollate:
1741da2e3ebdSchin env->error = REG_ECOLLATE;
1742da2e3ebdSchin goto error;
1743da2e3ebdSchin erange:
1744da2e3ebdSchin env->error = REG_ERANGE;
1745da2e3ebdSchin error:
1746da2e3ebdSchin drop(env->disc, e);
1747da2e3ebdSchin if (!env->error)
1748da2e3ebdSchin env->error = REG_EBRACK;
1749da2e3ebdSchin return 0;
1750da2e3ebdSchin }
1751da2e3ebdSchin
1752da2e3ebdSchin static Rex_t*
ccl(Cenv_t * env,int type)1753da2e3ebdSchin ccl(Cenv_t* env, int type)
1754da2e3ebdSchin {
1755da2e3ebdSchin int i;
1756da2e3ebdSchin Rex_t* e;
1757da2e3ebdSchin Celt_t* ce;
1758da2e3ebdSchin regclass_t f;
1759da2e3ebdSchin
1760da2e3ebdSchin if (!(f = classfun(type)))
1761da2e3ebdSchin {
1762da2e3ebdSchin env->error = REG_BADESC;
1763da2e3ebdSchin return 0;
1764da2e3ebdSchin }
1765da2e3ebdSchin if (!mbcoll())
1766da2e3ebdSchin {
1767da2e3ebdSchin if (!(e = node(env, REX_CLASS, 1, 1, sizeof(Set_t))))
1768da2e3ebdSchin return 0;
1769da2e3ebdSchin for (i = 0; i <= UCHAR_MAX; i++)
1770da2e3ebdSchin if ((*f)(i))
1771da2e3ebdSchin setadd(e->re.charclass, i);
1772da2e3ebdSchin if (env->explicit >= 0)
1773da2e3ebdSchin setclr(e->re.charclass, env->explicit);
1774da2e3ebdSchin }
1775da2e3ebdSchin else
1776da2e3ebdSchin {
1777da2e3ebdSchin if (!(e = node(env, REX_COLL_CLASS, 1, 1, 2 * sizeof(Celt_t))))
1778da2e3ebdSchin return 0;
1779da2e3ebdSchin ce = (Celt_t*)e->re.data;
1780da2e3ebdSchin e->re.collate.invert = 0;
1781da2e3ebdSchin e->re.collate.elements = ce;
1782da2e3ebdSchin ce->fun = f;
17837c2fbfb3SApril Chin ce->typ = COLL_call;
1784da2e3ebdSchin ce++;
1785da2e3ebdSchin ce->typ = COLL_end;
1786da2e3ebdSchin }
1787da2e3ebdSchin return e;
1788da2e3ebdSchin }
1789da2e3ebdSchin
1790da2e3ebdSchin static Rex_t*
rep(Cenv_t * env,Rex_t * e,int number,int last)1791da2e3ebdSchin rep(Cenv_t* env, Rex_t* e, int number, int last)
1792da2e3ebdSchin {
1793da2e3ebdSchin Rex_t* f;
1794da2e3ebdSchin unsigned long m = 0;
1795da2e3ebdSchin unsigned long n = RE_DUP_INF;
1796da2e3ebdSchin int minimal = -1;
1797da2e3ebdSchin
1798da2e3ebdSchin if (!e)
1799da2e3ebdSchin return 0;
1800da2e3ebdSchin switch (token(env))
1801da2e3ebdSchin {
1802da2e3ebdSchin case T_BANG:
1803da2e3ebdSchin eat(env);
1804da2e3ebdSchin if (!(f = node(env, REX_NEG, m, n, 0)))
1805da2e3ebdSchin {
1806da2e3ebdSchin drop(env->disc, e);
1807da2e3ebdSchin return 0;
1808da2e3ebdSchin }
1809da2e3ebdSchin f->re.group.expr.rex = e;
1810da2e3ebdSchin return f;
1811da2e3ebdSchin case T_QUES:
1812da2e3ebdSchin eat(env);
1813da2e3ebdSchin n = 1;
1814da2e3ebdSchin break;
1815da2e3ebdSchin case T_STAR:
1816da2e3ebdSchin eat(env);
1817da2e3ebdSchin break;
1818da2e3ebdSchin case T_PLUS:
1819da2e3ebdSchin eat(env);
1820da2e3ebdSchin m = 1;
1821da2e3ebdSchin break;
1822da2e3ebdSchin case T_LEFT:
1823da2e3ebdSchin eat(env);
1824da2e3ebdSchin m = env->token.min;
1825da2e3ebdSchin n = env->token.max;
1826da2e3ebdSchin break;
1827da2e3ebdSchin default:
1828da2e3ebdSchin return e;
1829da2e3ebdSchin }
1830da2e3ebdSchin if (env->token.att)
1831da2e3ebdSchin minimal = 1;
1832da2e3ebdSchin else if (env->type < SRE)
1833da2e3ebdSchin switch (token(env))
1834da2e3ebdSchin {
1835da2e3ebdSchin case T_QUES:
1836da2e3ebdSchin eat(env);
1837da2e3ebdSchin minimal = !(env->flags & REG_MINIMAL);
1838da2e3ebdSchin break;
1839da2e3ebdSchin case T_STAR: /*AST*/
1840da2e3ebdSchin eat(env);
1841da2e3ebdSchin minimal = !!(env->flags & REG_MINIMAL);
1842da2e3ebdSchin break;
1843da2e3ebdSchin }
1844da2e3ebdSchin switch (e->type)
1845da2e3ebdSchin {
1846da2e3ebdSchin case REX_DOT:
1847da2e3ebdSchin case REX_CLASS:
1848da2e3ebdSchin case REX_COLL_CLASS:
1849da2e3ebdSchin case REX_ONECHAR:
1850da2e3ebdSchin e->lo = m;
1851da2e3ebdSchin e->hi = n;
1852da2e3ebdSchin if (minimal >= 0)
1853da2e3ebdSchin mark(e, minimal);
1854da2e3ebdSchin return e;
1855da2e3ebdSchin #if HUH_2002_08_07
1856da2e3ebdSchin case REX_BEG:
1857da2e3ebdSchin #endif
1858da2e3ebdSchin case REX_BEG_STR:
1859da2e3ebdSchin case REX_END_STR:
1860da2e3ebdSchin case REX_FIN_STR:
1861da2e3ebdSchin case REX_WBEG:
1862da2e3ebdSchin case REX_WEND:
1863da2e3ebdSchin case REX_WORD:
1864da2e3ebdSchin case REX_WORD_NOT:
1865da2e3ebdSchin env->error = REG_BADRPT;
1866da2e3ebdSchin drop(env->disc, e);
1867da2e3ebdSchin return 0;
1868da2e3ebdSchin }
1869da2e3ebdSchin if (m == 1 && n == 1)
1870da2e3ebdSchin {
1871da2e3ebdSchin if (minimal >= 0)
1872da2e3ebdSchin mark(e, minimal);
1873da2e3ebdSchin return e;
1874da2e3ebdSchin }
1875da2e3ebdSchin if (!(f = node(env, REX_REP, m, n, 0)))
1876da2e3ebdSchin {
1877da2e3ebdSchin drop(env->disc, e);
1878da2e3ebdSchin return 0;
1879da2e3ebdSchin }
1880da2e3ebdSchin f->re.group.expr.rex = e;
1881da2e3ebdSchin f->re.group.number = number;
1882da2e3ebdSchin f->re.group.last = last;
1883da2e3ebdSchin if (minimal >= 0)
1884da2e3ebdSchin mark(f, minimal);
1885da2e3ebdSchin if (m <= n && n)
1886da2e3ebdSchin {
1887da2e3ebdSchin for (; e && e->type >= REX_GROUP && e->type <= REX_GROUP_CUT; e = e->re.group.expr.rex);
1888da2e3ebdSchin if (e && e->type == REX_NEG)
1889da2e3ebdSchin f->type = REX_GROUP;
1890da2e3ebdSchin }
1891da2e3ebdSchin return f;
1892da2e3ebdSchin }
1893da2e3ebdSchin
1894da2e3ebdSchin static int
isstring(Rex_t * e)1895da2e3ebdSchin isstring(Rex_t* e)
1896da2e3ebdSchin {
1897da2e3ebdSchin switch (e->type)
1898da2e3ebdSchin {
1899da2e3ebdSchin case REX_ONECHAR:
1900da2e3ebdSchin return e->lo == 1 && e->hi == 1;
1901da2e3ebdSchin case REX_STRING:
1902da2e3ebdSchin return 1;
1903da2e3ebdSchin }
1904da2e3ebdSchin return 0;
1905da2e3ebdSchin }
1906da2e3ebdSchin
1907da2e3ebdSchin static Trie_node_t*
trienode(Cenv_t * env,int c)1908da2e3ebdSchin trienode(Cenv_t* env, int c)
1909da2e3ebdSchin {
1910da2e3ebdSchin Trie_node_t* t;
1911da2e3ebdSchin
1912da2e3ebdSchin if (t = (Trie_node_t*)alloc(env->disc, 0, sizeof(Trie_node_t)))
1913da2e3ebdSchin {
1914da2e3ebdSchin memset(t, 0, sizeof(Trie_node_t));
1915da2e3ebdSchin t->c = c;
1916da2e3ebdSchin }
1917da2e3ebdSchin return t;
1918da2e3ebdSchin }
1919da2e3ebdSchin
1920da2e3ebdSchin static int
insert(Cenv_t * env,Rex_t * f,Rex_t * g)1921da2e3ebdSchin insert(Cenv_t* env, Rex_t* f, Rex_t* g)
1922da2e3ebdSchin {
1923da2e3ebdSchin unsigned char* s;
1924da2e3ebdSchin unsigned char* e;
1925da2e3ebdSchin Trie_node_t* t;
1926da2e3ebdSchin int len;
1927da2e3ebdSchin unsigned char tmp[2];
1928da2e3ebdSchin
1929da2e3ebdSchin switch (f->type)
1930da2e3ebdSchin {
1931da2e3ebdSchin case REX_ONECHAR:
1932da2e3ebdSchin *(s = tmp) = f->re.onechar;
1933da2e3ebdSchin e = s + 1;
1934da2e3ebdSchin break;
1935da2e3ebdSchin case REX_STRING:
1936da2e3ebdSchin s = f->re.string.base;
1937da2e3ebdSchin e = s + f->re.string.size;
1938da2e3ebdSchin break;
1939da2e3ebdSchin default:
1940da2e3ebdSchin return 1;
1941da2e3ebdSchin }
1942da2e3ebdSchin if (!(t = g->re.trie.root[*s]) && !(t = g->re.trie.root[*s] = trienode(env, *s)))
1943da2e3ebdSchin return 1;
1944da2e3ebdSchin for (len = 1;;)
1945da2e3ebdSchin {
1946da2e3ebdSchin if (t->c == *s)
1947da2e3ebdSchin {
1948da2e3ebdSchin if (++s >= e)
1949da2e3ebdSchin break;
1950da2e3ebdSchin if (!t->son && !(t->son = trienode(env, *s)))
1951da2e3ebdSchin return 1;
1952da2e3ebdSchin t = t->son;
1953da2e3ebdSchin len++;
1954da2e3ebdSchin }
1955da2e3ebdSchin else
1956da2e3ebdSchin {
1957da2e3ebdSchin if (!t->sib && !(t->sib = trienode(env, *s)))
1958da2e3ebdSchin return 1;
1959da2e3ebdSchin t = t->sib;
1960da2e3ebdSchin }
1961da2e3ebdSchin }
1962da2e3ebdSchin if (g->re.trie.min > len)
1963da2e3ebdSchin g->re.trie.min = len;
1964da2e3ebdSchin if (g->re.trie.max < len)
1965da2e3ebdSchin g->re.trie.max = len;
1966da2e3ebdSchin t->end = 1;
1967da2e3ebdSchin return 0;
1968da2e3ebdSchin }
1969da2e3ebdSchin
1970da2e3ebdSchin /*
1971da2e3ebdSchin * trie() tries to combine nontrivial e and f into a REX_TRIE
1972da2e3ebdSchin * unless 0 is returned, e and f are deleted as far as possible
1973da2e3ebdSchin * also called by regcomb
1974da2e3ebdSchin */
1975da2e3ebdSchin
1976da2e3ebdSchin static Rex_t*
trie(Cenv_t * env,Rex_t * e,Rex_t * f)1977da2e3ebdSchin trie(Cenv_t* env, Rex_t* e, Rex_t* f)
1978da2e3ebdSchin {
1979da2e3ebdSchin Rex_t* g;
1980da2e3ebdSchin
1981da2e3ebdSchin if (e->next || f->next || !isstring(e) || e->flags != f->flags)
1982da2e3ebdSchin return 0;
1983da2e3ebdSchin if (isstring(f))
1984da2e3ebdSchin {
1985da2e3ebdSchin if (!(g = node(env, REX_TRIE, 0, 0, (UCHAR_MAX + 1) * sizeof(Trie_node_t*))))
1986da2e3ebdSchin return 0;
1987da2e3ebdSchin g->re.trie.min = INT_MAX;
1988da2e3ebdSchin if (insert(env, f, g))
1989da2e3ebdSchin goto nospace;
1990da2e3ebdSchin drop(env->disc, f);
1991da2e3ebdSchin }
1992da2e3ebdSchin else if (f->type != REX_TRIE)
1993da2e3ebdSchin return 0;
1994da2e3ebdSchin else
1995da2e3ebdSchin g = f;
1996da2e3ebdSchin if (insert(env, e, g))
1997da2e3ebdSchin goto nospace;
1998da2e3ebdSchin drop(env->disc, e);
1999da2e3ebdSchin return g;
2000da2e3ebdSchin nospace:
2001da2e3ebdSchin if (g != f)
2002da2e3ebdSchin drop(env->disc, g);
2003da2e3ebdSchin return 0;
2004da2e3ebdSchin }
2005da2e3ebdSchin
2006da2e3ebdSchin static Rex_t* alt(Cenv_t*, int, int);
2007da2e3ebdSchin
2008da2e3ebdSchin static int
chr(register Cenv_t * env,int * escaped)2009da2e3ebdSchin chr(register Cenv_t* env, int* escaped)
2010da2e3ebdSchin {
2011da2e3ebdSchin unsigned char* p;
2012da2e3ebdSchin int c;
2013da2e3ebdSchin
2014da2e3ebdSchin *escaped = 0;
2015da2e3ebdSchin if (!(c = *env->cursor))
2016da2e3ebdSchin return -1;
2017da2e3ebdSchin env->cursor++;
2018da2e3ebdSchin if (c == '\\')
2019da2e3ebdSchin {
2020da2e3ebdSchin if (env->flags & REG_SHELL_ESCAPED)
2021da2e3ebdSchin return c;
2022da2e3ebdSchin if (!(c = *(env->cursor + 1)) || c == env->terminator)
2023da2e3ebdSchin {
2024*b30d1939SAndy Fiddaman if (env->flags & (REG_LENIENT|REG_REGEXP))
2025da2e3ebdSchin return c ? c : '\\';
2026da2e3ebdSchin env->error = REG_EESCAPE;
2027da2e3ebdSchin return -1;
2028da2e3ebdSchin }
2029da2e3ebdSchin p = env->cursor;
2030da2e3ebdSchin c = chresc((char*)env->cursor - 1, (char**)&env->cursor);
2031da2e3ebdSchin *escaped = env->cursor - p;
2032da2e3ebdSchin }
2033da2e3ebdSchin return c;
2034da2e3ebdSchin }
2035da2e3ebdSchin
2036da2e3ebdSchin /*
2037da2e3ebdSchin * open the perly gates
2038da2e3ebdSchin */
2039da2e3ebdSchin
2040da2e3ebdSchin static Rex_t*
grp(Cenv_t * env,int parno)2041da2e3ebdSchin grp(Cenv_t* env, int parno)
2042da2e3ebdSchin {
2043da2e3ebdSchin Rex_t* e;
2044da2e3ebdSchin Rex_t* f;
2045da2e3ebdSchin int c;
2046*b30d1939SAndy Fiddaman int g;
2047da2e3ebdSchin int i;
2048da2e3ebdSchin int n;
2049da2e3ebdSchin int x;
2050da2e3ebdSchin int esc;
2051da2e3ebdSchin int typ;
2052da2e3ebdSchin int beg;
2053da2e3ebdSchin unsigned char* p;
2054da2e3ebdSchin
2055*b30d1939SAndy Fiddaman g = env->flags;
2056da2e3ebdSchin beg = env->pattern == env->cursor - env->token.len;
2057da2e3ebdSchin if (!(c = env->token.lex) && (c = *env->cursor))
2058da2e3ebdSchin env->cursor++;
2059da2e3ebdSchin env->token.len = 0;
2060da2e3ebdSchin env->parnest++;
2061da2e3ebdSchin typ = -1;
2062da2e3ebdSchin switch (c)
2063da2e3ebdSchin {
2064da2e3ebdSchin case '-':
2065da2e3ebdSchin case '+':
2066da2e3ebdSchin case 'a':
2067da2e3ebdSchin case 'g':
2068da2e3ebdSchin case 'i':
2069da2e3ebdSchin case 'l':
2070da2e3ebdSchin case 'm':
2071da2e3ebdSchin case 'p':
2072da2e3ebdSchin case 'r':
2073da2e3ebdSchin case 's':
2074da2e3ebdSchin case 'x':
2075da2e3ebdSchin case 'A':
2076da2e3ebdSchin case 'B':
2077da2e3ebdSchin case 'E':
2078da2e3ebdSchin case 'F':
2079da2e3ebdSchin case 'G':
2080da2e3ebdSchin case 'I':
2081da2e3ebdSchin case 'K':
20827c2fbfb3SApril Chin case 'L':
20837c2fbfb3SApril Chin case 'M': /* glob(3) */
20847c2fbfb3SApril Chin case 'N': /* glob(3) */
20857c2fbfb3SApril Chin case 'O': /* glob(3) */
20863e14f97fSRoger A. Faulkner case 'P':
20877c2fbfb3SApril Chin case 'R': /* pcre */
2088da2e3ebdSchin case 'S':
2089da2e3ebdSchin case 'U': /* pcre */
2090*b30d1939SAndy Fiddaman case 'V':
2091da2e3ebdSchin case 'X': /* pcre */
2092da2e3ebdSchin x = REX_GROUP;
2093da2e3ebdSchin i = 1;
2094da2e3ebdSchin env->token.push = 1;
2095da2e3ebdSchin for (;;)
2096da2e3ebdSchin {
2097da2e3ebdSchin switch (c)
2098da2e3ebdSchin {
20997c2fbfb3SApril Chin case ')':
21007c2fbfb3SApril Chin if (!(env->flags & REG_LITERAL))
21017c2fbfb3SApril Chin {
21027c2fbfb3SApril Chin env->error = REG_BADRPT;
21037c2fbfb3SApril Chin return 0;
21047c2fbfb3SApril Chin }
21057c2fbfb3SApril Chin /*FALLTHROUGH*/
2106da2e3ebdSchin case 0:
2107da2e3ebdSchin case T_CLOSE:
2108da2e3ebdSchin x = 0;
2109da2e3ebdSchin goto done;
2110da2e3ebdSchin case ':':
2111da2e3ebdSchin eat(env);
2112da2e3ebdSchin if (token(env) == T_CLOSE)
2113da2e3ebdSchin x = 0;
2114da2e3ebdSchin goto done;
2115da2e3ebdSchin case '-':
2116da2e3ebdSchin i = 0;
2117da2e3ebdSchin break;
2118da2e3ebdSchin case '+':
2119da2e3ebdSchin i = 1;
2120da2e3ebdSchin break;
2121da2e3ebdSchin case 'a':
2122da2e3ebdSchin if (i)
2123da2e3ebdSchin env->flags |= (REG_LEFT|REG_RIGHT);
2124da2e3ebdSchin else
2125da2e3ebdSchin env->flags &= ~(REG_LEFT|REG_RIGHT);
2126da2e3ebdSchin break;
2127da2e3ebdSchin case 'g':
2128da2e3ebdSchin if (i)
2129da2e3ebdSchin env->flags &= ~REG_MINIMAL;
2130da2e3ebdSchin else
2131da2e3ebdSchin env->flags |= REG_MINIMAL;
2132da2e3ebdSchin break;
2133da2e3ebdSchin case 'i':
2134da2e3ebdSchin if (i)
2135da2e3ebdSchin env->flags |= REG_ICASE;
2136da2e3ebdSchin else
2137da2e3ebdSchin env->flags &= ~REG_ICASE;
2138da2e3ebdSchin break;
2139da2e3ebdSchin case 'l':
2140da2e3ebdSchin if (i)
2141da2e3ebdSchin env->flags |= REG_LEFT;
2142da2e3ebdSchin else
2143da2e3ebdSchin env->flags &= ~REG_LEFT;
2144da2e3ebdSchin break;
2145da2e3ebdSchin case 'm':
2146da2e3ebdSchin if (i)
2147da2e3ebdSchin env->flags |= REG_NEWLINE;
2148da2e3ebdSchin else
2149da2e3ebdSchin env->flags &= ~REG_NEWLINE;
2150da2e3ebdSchin env->explicit = (env->flags & (REG_NEWLINE|REG_SPAN)) == REG_NEWLINE ? env->mappednewline : -1;
2151da2e3ebdSchin break;
2152da2e3ebdSchin case 'p':
2153da2e3ebdSchin if (i)
2154da2e3ebdSchin env->flags &= ~REG_LENIENT;
2155da2e3ebdSchin else
2156da2e3ebdSchin env->flags |= REG_LENIENT;
2157da2e3ebdSchin break;
2158da2e3ebdSchin case 'r':
2159da2e3ebdSchin if (i)
2160da2e3ebdSchin env->flags |= REG_RIGHT;
2161da2e3ebdSchin else
2162da2e3ebdSchin env->flags &= ~REG_RIGHT;
2163da2e3ebdSchin break;
2164da2e3ebdSchin case 's':
2165da2e3ebdSchin if (i)
2166da2e3ebdSchin env->flags |= REG_SPAN;
2167da2e3ebdSchin else
2168da2e3ebdSchin env->flags &= ~REG_SPAN;
2169da2e3ebdSchin env->explicit = (env->flags & (REG_NEWLINE|REG_SPAN)) == REG_NEWLINE ? env->mappednewline : -1;
2170da2e3ebdSchin break;
2171da2e3ebdSchin case 'x':
2172da2e3ebdSchin if (i)
2173da2e3ebdSchin env->flags |= REG_COMMENT;
2174da2e3ebdSchin else
2175da2e3ebdSchin env->flags &= ~REG_COMMENT;
2176da2e3ebdSchin break;
2177*b30d1939SAndy Fiddaman case 'X':
2178*b30d1939SAndy Fiddaman if (typ >= 0 || env->type == ERE && (env->flags & REG_CLASS_ESCAPE))
2179*b30d1939SAndy Fiddaman break; /* PCRE_EXTRA */
2180*b30d1939SAndy Fiddaman /*FALLTHROUGH*/
2181da2e3ebdSchin case 'A':
2182*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2183da2e3ebdSchin env->flags |= REG_AUGMENTED|REG_EXTENDED;
2184da2e3ebdSchin typ = ARE;
2185da2e3ebdSchin break;
2186da2e3ebdSchin case 'B':
2187da2e3ebdSchin case 'G':
2188*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2189da2e3ebdSchin typ = BRE;
2190da2e3ebdSchin break;
2191da2e3ebdSchin case 'E':
2192*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2193da2e3ebdSchin env->flags |= REG_EXTENDED;
2194da2e3ebdSchin typ = ERE;
2195da2e3ebdSchin break;
2196da2e3ebdSchin case 'F':
2197da2e3ebdSchin case 'L':
2198*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2199da2e3ebdSchin env->flags |= REG_LITERAL;
2200da2e3ebdSchin typ = ERE;
2201da2e3ebdSchin break;
2202da2e3ebdSchin case 'K':
2203*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2204da2e3ebdSchin env->flags |= REG_AUGMENTED|REG_SHELL|REG_LEFT|REG_RIGHT;
2205da2e3ebdSchin typ = KRE;
2206da2e3ebdSchin break;
2207da2e3ebdSchin case 'M':
2208da2e3ebdSchin /* used by caller to disable glob(3) GLOB_BRACE */
2209da2e3ebdSchin break;
2210da2e3ebdSchin case 'N':
2211da2e3ebdSchin /* used by caller to disable glob(3) GLOB_NOCHECK */
2212da2e3ebdSchin break;
22137c2fbfb3SApril Chin case 'O':
2214da2e3ebdSchin /* used by caller to disable glob(3) GLOB_STARSTAR */
2215da2e3ebdSchin break;
22163e14f97fSRoger A. Faulkner case 'P':
2217*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
22183e14f97fSRoger A. Faulkner env->flags |= REG_EXTENDED|REG_CLASS_ESCAPE;
22193e14f97fSRoger A. Faulkner typ = ERE;
22203e14f97fSRoger A. Faulkner break;
2221da2e3ebdSchin case 'S':
2222*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2223da2e3ebdSchin env->flags |= REG_SHELL|REG_LEFT|REG_RIGHT;
2224da2e3ebdSchin typ = SRE;
2225da2e3ebdSchin break;
2226da2e3ebdSchin case 'U': /* PCRE_UNGREEDY */
2227*b30d1939SAndy Fiddaman if (typ >= 0 || env->type == ERE && (env->flags & REG_CLASS_ESCAPE))
2228*b30d1939SAndy Fiddaman {
2229*b30d1939SAndy Fiddaman if (i)
2230*b30d1939SAndy Fiddaman env->flags |= REG_MINIMAL;
2231*b30d1939SAndy Fiddaman else
2232*b30d1939SAndy Fiddaman env->flags &= ~REG_MINIMAL;
2233*b30d1939SAndy Fiddaman }
2234da2e3ebdSchin break;
2235*b30d1939SAndy Fiddaman case 'V':
2236*b30d1939SAndy Fiddaman env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_REGEXP|REG_SHELL|REG_LEFT|REG_RIGHT);
2237*b30d1939SAndy Fiddaman env->flags |= REG_REGEXP;
2238*b30d1939SAndy Fiddaman typ = BRE;
2239da2e3ebdSchin break;
2240da2e3ebdSchin default:
2241da2e3ebdSchin env->error = REG_BADRPT;
2242da2e3ebdSchin return 0;
2243da2e3ebdSchin }
2244da2e3ebdSchin eat(env);
2245da2e3ebdSchin c = token(env);
2246da2e3ebdSchin }
2247da2e3ebdSchin done:
2248da2e3ebdSchin break;
2249da2e3ebdSchin case ':':
2250da2e3ebdSchin x = REX_GROUP;
2251da2e3ebdSchin break;
2252da2e3ebdSchin case '=':
2253da2e3ebdSchin x = REX_GROUP_AHEAD;
2254da2e3ebdSchin break;
2255da2e3ebdSchin case '!':
2256da2e3ebdSchin x = REX_GROUP_AHEAD_NOT;
2257da2e3ebdSchin break;
2258da2e3ebdSchin case '<':
2259da2e3ebdSchin switch (token(env))
2260da2e3ebdSchin {
2261da2e3ebdSchin case '=':
2262da2e3ebdSchin x = REX_GROUP_BEHIND;
2263da2e3ebdSchin break;
2264da2e3ebdSchin case '!':
2265da2e3ebdSchin case T_BANG:
2266da2e3ebdSchin x = REX_GROUP_BEHIND_NOT;
2267da2e3ebdSchin break;
2268da2e3ebdSchin default:
2269da2e3ebdSchin env->error = REG_BADRPT;
2270da2e3ebdSchin return 0;
2271da2e3ebdSchin }
2272da2e3ebdSchin eat(env);
2273da2e3ebdSchin break;
2274da2e3ebdSchin case '>':
2275da2e3ebdSchin x = REX_GROUP_CUT;
2276da2e3ebdSchin break;
2277da2e3ebdSchin case '%':
2278da2e3ebdSchin case T_PERCENT:
2279da2e3ebdSchin e = node(env, REX_NEST, 0, 0, (UCHAR_MAX + 1) * sizeof(unsigned short));
2280da2e3ebdSchin e->re.nest.primary = isalnum(*env->cursor) ? -1 : *env->cursor;
2281da2e3ebdSchin n = 1;
2282da2e3ebdSchin for (;;)
2283da2e3ebdSchin {
2284da2e3ebdSchin switch (i = chr(env, &esc))
2285da2e3ebdSchin {
2286da2e3ebdSchin case -1:
2287da2e3ebdSchin case 0:
2288da2e3ebdSchin invalid:
2289da2e3ebdSchin env->cursor -= esc + 1;
2290da2e3ebdSchin env->error = REG_EPAREN;
2291da2e3ebdSchin return 0;
2292da2e3ebdSchin case 'D':
2293da2e3ebdSchin x = REX_NEST_delimiter;
2294da2e3ebdSchin /*FALLTHROUGH*/
2295da2e3ebdSchin delimiter:
2296da2e3ebdSchin if ((i = chr(env, &esc)) < 0)
2297da2e3ebdSchin goto invalid;
2298da2e3ebdSchin if (e->re.nest.type[i] & ~x)
2299da2e3ebdSchin goto invalid;
2300da2e3ebdSchin e->re.nest.type[i] = x;
2301da2e3ebdSchin continue;
2302da2e3ebdSchin case 'E':
2303da2e3ebdSchin x = REX_NEST_escape;
2304da2e3ebdSchin goto delimiter;
2305da2e3ebdSchin case 'L':
2306da2e3ebdSchin x = REX_NEST_literal;
2307da2e3ebdSchin goto quote;
2308da2e3ebdSchin case 'O':
2309da2e3ebdSchin switch (i = chr(env, &esc))
2310da2e3ebdSchin {
2311da2e3ebdSchin case 'T':
2312da2e3ebdSchin e->re.nest.type[UCHAR_MAX+1] |= REX_NEST_terminator;
2313da2e3ebdSchin break;
2314da2e3ebdSchin default:
2315da2e3ebdSchin goto invalid;
2316da2e3ebdSchin }
2317da2e3ebdSchin continue;
2318da2e3ebdSchin case 'Q':
2319da2e3ebdSchin x = REX_NEST_quote;
2320da2e3ebdSchin /*FALLTHROUGH*/
2321da2e3ebdSchin quote:
2322da2e3ebdSchin if ((i = chr(env, &esc)) < 0)
2323da2e3ebdSchin goto invalid;
2324da2e3ebdSchin if (e->re.nest.type[i] & ~x)
2325da2e3ebdSchin goto invalid;
2326da2e3ebdSchin e->re.nest.type[i] = x|REX_NEST_open|REX_NEST_close|(i<<REX_NEST_SHIFT);
2327da2e3ebdSchin continue;
2328da2e3ebdSchin case 'S':
2329da2e3ebdSchin x = REX_NEST_separator;
2330da2e3ebdSchin goto delimiter;
2331da2e3ebdSchin case 'T':
2332da2e3ebdSchin x = REX_NEST_terminator;
2333da2e3ebdSchin goto delimiter;
2334da2e3ebdSchin case '|':
2335da2e3ebdSchin case '&':
2336da2e3ebdSchin if (!esc)
2337da2e3ebdSchin goto invalid;
2338da2e3ebdSchin goto nesting;
2339da2e3ebdSchin case '(':
2340da2e3ebdSchin if (!esc)
2341da2e3ebdSchin n++;
2342da2e3ebdSchin goto nesting;
2343da2e3ebdSchin case ')':
2344da2e3ebdSchin if (!esc && !--n)
2345da2e3ebdSchin break;
2346da2e3ebdSchin goto nesting;
2347da2e3ebdSchin default:
2348da2e3ebdSchin nesting:
2349da2e3ebdSchin if (isalnum(i) || (e->re.nest.type[i] & (REX_NEST_close|REX_NEST_escape|REX_NEST_literal|REX_NEST_quote|REX_NEST_delimiter|REX_NEST_separator|REX_NEST_terminator)))
2350da2e3ebdSchin goto invalid;
2351da2e3ebdSchin e->re.nest.type[i] = REX_NEST_open;
2352da2e3ebdSchin if ((x = chr(env, &esc)) < 0 || (e->re.nest.type[x] & (REX_NEST_close|REX_NEST_escape|REX_NEST_delimiter|REX_NEST_separator|REX_NEST_terminator)))
2353da2e3ebdSchin goto invalid;
2354da2e3ebdSchin if (!esc)
2355da2e3ebdSchin {
2356da2e3ebdSchin if (x == ')' && !--n)
2357da2e3ebdSchin goto invalid;
2358da2e3ebdSchin else if (x == '(')
2359da2e3ebdSchin n++;
2360da2e3ebdSchin }
2361da2e3ebdSchin e->re.nest.type[x] |= REX_NEST_close;
2362da2e3ebdSchin e->re.nest.type[i] |= x << REX_NEST_SHIFT;
2363da2e3ebdSchin continue;
2364da2e3ebdSchin }
2365da2e3ebdSchin break;
2366da2e3ebdSchin }
2367da2e3ebdSchin env->parnest--;
2368da2e3ebdSchin if (c == T_PERCENT)
2369da2e3ebdSchin for (n = 0; n < 2; n++)
2370da2e3ebdSchin {
2371da2e3ebdSchin parno = ++env->parno;
2372da2e3ebdSchin if (!(f = node(env, REX_GROUP, 0, 0, 0)))
2373da2e3ebdSchin {
2374da2e3ebdSchin drop(env->disc, e);
2375da2e3ebdSchin return 0;
2376da2e3ebdSchin }
2377da2e3ebdSchin if (parno < elementsof(env->paren))
2378da2e3ebdSchin env->paren[parno] = f;
2379da2e3ebdSchin f->re.group.back = 0;
2380da2e3ebdSchin f->re.group.number = parno;
2381da2e3ebdSchin f->re.group.expr.rex = e;
2382da2e3ebdSchin e = f;
2383da2e3ebdSchin }
2384da2e3ebdSchin return e;
2385da2e3ebdSchin case '(':
2386da2e3ebdSchin c = 0;
2387da2e3ebdSchin if (isdigit(*env->cursor))
2388da2e3ebdSchin {
2389da2e3ebdSchin f = 0;
2390da2e3ebdSchin do
2391da2e3ebdSchin {
2392da2e3ebdSchin if (c > (INT_MAX / 10))
2393da2e3ebdSchin {
2394da2e3ebdSchin env->error = REG_BADRPT;
2395da2e3ebdSchin return 0;
2396da2e3ebdSchin }
2397da2e3ebdSchin c = c * 10 + (*env->cursor++ - '0');
2398da2e3ebdSchin } while (isdigit(*env->cursor));
2399da2e3ebdSchin if (*env->cursor++ != ')')
2400da2e3ebdSchin {
2401da2e3ebdSchin env->error = REG_BADRPT;
2402da2e3ebdSchin return 0;
2403da2e3ebdSchin }
2404da2e3ebdSchin if (c && env->type >= SRE)
2405da2e3ebdSchin c = c * 2 - 1;
2406da2e3ebdSchin if (!c || c > env->parno || !env->paren[c])
2407da2e3ebdSchin {
2408*b30d1939SAndy Fiddaman if (!(env->flags & (REG_LENIENT|REG_REGEXP)))
2409da2e3ebdSchin {
2410da2e3ebdSchin env->error = REG_ESUBREG;
2411da2e3ebdSchin return 0;
2412da2e3ebdSchin }
2413da2e3ebdSchin if (c)
2414da2e3ebdSchin c = -1;
2415da2e3ebdSchin }
2416da2e3ebdSchin }
2417da2e3ebdSchin else
2418da2e3ebdSchin {
2419da2e3ebdSchin if (env->type < SRE && *env->cursor++ != '?')
2420da2e3ebdSchin {
2421da2e3ebdSchin env->error = REG_BADRPT;
2422da2e3ebdSchin return 0;
2423da2e3ebdSchin }
2424da2e3ebdSchin if (!(f = grp(env, parno + 1)) && env->error)
2425da2e3ebdSchin return 0;
2426da2e3ebdSchin }
2427da2e3ebdSchin if (!(e = node(env, REX_GROUP_COND, 0, 0, 0)))
2428da2e3ebdSchin {
2429da2e3ebdSchin drop(env->disc, f);
2430da2e3ebdSchin return 0;
2431da2e3ebdSchin }
2432da2e3ebdSchin e->re.group.size = c;
2433da2e3ebdSchin e->re.group.expr.binary.left = f;
2434da2e3ebdSchin if (!(e->re.group.expr.binary.right = alt(env, parno, 1)))
2435da2e3ebdSchin {
2436da2e3ebdSchin drop(env->disc, e);
2437da2e3ebdSchin return 0;
2438da2e3ebdSchin }
2439da2e3ebdSchin if (token(env) != T_CLOSE)
2440da2e3ebdSchin {
2441da2e3ebdSchin env->error = REG_EPAREN;
2442da2e3ebdSchin return 0;
2443da2e3ebdSchin }
2444da2e3ebdSchin eat(env);
2445da2e3ebdSchin env->parnest--;
2446da2e3ebdSchin return rep(env, e, parno, parno);
2447da2e3ebdSchin case '{':
2448da2e3ebdSchin p = env->cursor;
2449da2e3ebdSchin n = 1;
2450da2e3ebdSchin while (c = *env->cursor)
2451da2e3ebdSchin {
2452da2e3ebdSchin if (c == '\\' && *(env->cursor + 1))
2453da2e3ebdSchin env->cursor++;
2454da2e3ebdSchin else if (c == '{')
2455da2e3ebdSchin n++;
2456da2e3ebdSchin else if (c == '}' && !--n)
2457da2e3ebdSchin break;
2458da2e3ebdSchin else if (c == env->delimiter || c == env->terminator)
2459da2e3ebdSchin break;
2460da2e3ebdSchin env->cursor++;
2461da2e3ebdSchin }
2462da2e3ebdSchin if (c != '}')
2463da2e3ebdSchin {
2464da2e3ebdSchin env->error = REG_EBRACE;
2465da2e3ebdSchin return 0;
2466da2e3ebdSchin }
2467da2e3ebdSchin if (*++env->cursor != ')')
2468da2e3ebdSchin {
2469da2e3ebdSchin env->error = REG_EPAREN;
2470da2e3ebdSchin return 0;
2471da2e3ebdSchin }
2472da2e3ebdSchin env->cursor++;
2473da2e3ebdSchin env->parnest--;
2474da2e3ebdSchin if (env->disc->re_version < REG_VERSION_EXEC)
2475da2e3ebdSchin {
2476da2e3ebdSchin env->error = REG_BADRPT;
2477da2e3ebdSchin return 0;
2478da2e3ebdSchin }
2479da2e3ebdSchin if (!env->disc->re_execf)
2480da2e3ebdSchin return 0;
2481da2e3ebdSchin if (!(e = node(env, REX_EXEC, 0, 0, 0)))
2482da2e3ebdSchin return 0;
2483da2e3ebdSchin e->re.exec.text = (const char*)p;
2484da2e3ebdSchin e->re.exec.size = env->cursor - p - 2;
2485da2e3ebdSchin if (!env->disc->re_compf)
2486da2e3ebdSchin e->re.exec.data = 0;
2487da2e3ebdSchin else
2488da2e3ebdSchin e->re.exec.data = (*env->disc->re_compf)(env->regex, e->re.exec.text, e->re.exec.size, env->disc);
2489da2e3ebdSchin return e;
2490da2e3ebdSchin case '0': case '1': case '2': case '3': case '4':
2491da2e3ebdSchin case '5': case '6': case '7': case '8': case '9':
2492da2e3ebdSchin c -= '0';
2493da2e3ebdSchin while (isdigit(*env->cursor))
2494da2e3ebdSchin {
2495da2e3ebdSchin if (c > (INT_MAX / 10))
2496da2e3ebdSchin {
2497da2e3ebdSchin env->error = REG_ESUBREG;
2498da2e3ebdSchin return 0;
2499da2e3ebdSchin }
2500da2e3ebdSchin c = c * 10 + *env->cursor++ - '0';
2501da2e3ebdSchin }
2502da2e3ebdSchin if (*env->cursor == ')')
2503da2e3ebdSchin {
2504da2e3ebdSchin env->cursor++;
2505da2e3ebdSchin env->parnest--;
2506da2e3ebdSchin env->token.len = 1;
2507da2e3ebdSchin if (c > env->parno || !env->paren[c])
2508da2e3ebdSchin {
2509da2e3ebdSchin env->error = REG_ESUBREG;
2510da2e3ebdSchin return 0;
2511da2e3ebdSchin }
2512da2e3ebdSchin env->paren[c]->re.group.back = 1;
2513da2e3ebdSchin return rep(env, node(env, REX_BACK, c, 0, 0), 0, 0);
2514da2e3ebdSchin }
2515da2e3ebdSchin /*FALLTHROUGH*/
2516da2e3ebdSchin default:
2517da2e3ebdSchin env->error = REG_BADRPT;
2518da2e3ebdSchin return 0;
2519da2e3ebdSchin }
2520*b30d1939SAndy Fiddaman p = env->pattern;
2521*b30d1939SAndy Fiddaman i = env->type;
2522*b30d1939SAndy Fiddaman if (x)
2523*b30d1939SAndy Fiddaman {
2524*b30d1939SAndy Fiddaman if (typ >= 0)
2525*b30d1939SAndy Fiddaman env->type = typ;
2526*b30d1939SAndy Fiddaman if (!(e = alt(env, parno, 0)))
2527*b30d1939SAndy Fiddaman goto nope;
2528*b30d1939SAndy Fiddaman env->flags = g;
2529*b30d1939SAndy Fiddaman env->type = i;
2530*b30d1939SAndy Fiddaman }
2531da2e3ebdSchin c = token(env);
2532da2e3ebdSchin env->parnest--;
25337c2fbfb3SApril Chin if (c != T_CLOSE && (!(env->flags & REG_LITERAL) || c != ')'))
2534da2e3ebdSchin {
2535da2e3ebdSchin env->error = REG_EPAREN;
2536*b30d1939SAndy Fiddaman goto nope;
2537da2e3ebdSchin }
2538da2e3ebdSchin eat(env);
2539*b30d1939SAndy Fiddaman if (typ >= 0 && beg)
2540*b30d1939SAndy Fiddaman env->pattern = env->cursor;
2541da2e3ebdSchin if (!x)
2542*b30d1939SAndy Fiddaman {
2543*b30d1939SAndy Fiddaman if (typ >= 0)
2544*b30d1939SAndy Fiddaman env->type = typ;
2545da2e3ebdSchin return 0;
2546*b30d1939SAndy Fiddaman }
2547da2e3ebdSchin if (!(f = node(env, x, 0, 0, 0)))
2548da2e3ebdSchin {
2549da2e3ebdSchin drop(env->disc, e);
2550*b30d1939SAndy Fiddaman goto nope;
2551da2e3ebdSchin }
2552da2e3ebdSchin f->re.group.expr.rex = e;
2553da2e3ebdSchin if (x == REX_GROUP_BEHIND || x == REX_GROUP_BEHIND_NOT)
2554da2e3ebdSchin {
2555da2e3ebdSchin if (stats(env, e))
2556da2e3ebdSchin {
2557da2e3ebdSchin drop(env->disc, f);
2558da2e3ebdSchin if (!env->error)
2559da2e3ebdSchin env->error = REG_ECOUNT;
2560*b30d1939SAndy Fiddaman goto nope;
2561da2e3ebdSchin }
2562da2e3ebdSchin f->re.group.size = env->stats.m;
2563da2e3ebdSchin memset(&env->stats, 0, sizeof(env->stats));
2564da2e3ebdSchin }
2565da2e3ebdSchin switch (x)
2566da2e3ebdSchin {
2567da2e3ebdSchin case REX_GROUP:
2568da2e3ebdSchin case REX_GROUP_CUT:
2569da2e3ebdSchin f = rep(env, f, parno, env->parno);
2570da2e3ebdSchin break;
2571da2e3ebdSchin }
2572*b30d1939SAndy Fiddaman if (f)
2573*b30d1939SAndy Fiddaman return f;
2574*b30d1939SAndy Fiddaman nope:
2575*b30d1939SAndy Fiddaman env->flags = g;
2576*b30d1939SAndy Fiddaman env->pattern = p;
2577*b30d1939SAndy Fiddaman env->type = i;
2578*b30d1939SAndy Fiddaman return 0;
2579da2e3ebdSchin }
2580da2e3ebdSchin
2581da2e3ebdSchin static Rex_t*
seq(Cenv_t * env)2582da2e3ebdSchin seq(Cenv_t* env)
2583da2e3ebdSchin {
2584da2e3ebdSchin Rex_t* e;
2585da2e3ebdSchin Rex_t* f;
2586da2e3ebdSchin Token_t tok;
2587da2e3ebdSchin int c;
2588da2e3ebdSchin int i;
2589da2e3ebdSchin int n;
2590da2e3ebdSchin int x;
2591da2e3ebdSchin int parno;
2592da2e3ebdSchin int type;
2593da2e3ebdSchin regflags_t flags;
2594da2e3ebdSchin unsigned char* s;
2595da2e3ebdSchin unsigned char* p;
2596da2e3ebdSchin unsigned char* t;
2597da2e3ebdSchin unsigned char* u;
2598da2e3ebdSchin unsigned char buf[256];
2599da2e3ebdSchin
2600da2e3ebdSchin for (;;)
2601da2e3ebdSchin {
2602da2e3ebdSchin s = buf;
2603da2e3ebdSchin while ((c = token(env)) < T_META && s < &buf[sizeof(buf) - env->token.len])
2604da2e3ebdSchin {
2605da2e3ebdSchin x = c;
2606da2e3ebdSchin p = env->cursor;
2607da2e3ebdSchin if (c >= 0)
2608da2e3ebdSchin {
2609da2e3ebdSchin n = 1;
2610da2e3ebdSchin *s++ = (env->flags & REG_ICASE) ? toupper(c) : c;
2611da2e3ebdSchin }
26127c2fbfb3SApril Chin else if (c == C_ESC || (env->flags & REG_ICASE))
2613da2e3ebdSchin {
26147c2fbfb3SApril Chin c = (c == C_ESC) ? env->token.lex : mbchar(p);
26157c2fbfb3SApril Chin if (env->flags & REG_ICASE)
26167c2fbfb3SApril Chin c = towupper(c);
26177c2fbfb3SApril Chin if ((&buf[sizeof(buf)] - s) < MB_CUR_MAX)
26187c2fbfb3SApril Chin break;
26193e14f97fSRoger A. Faulkner if ((n = mbconv((char*)s, c)) < 0)
26207c2fbfb3SApril Chin *s++ = c;
26217c2fbfb3SApril Chin else if (n)
26227c2fbfb3SApril Chin s += n;
26237c2fbfb3SApril Chin else
2624da2e3ebdSchin {
2625da2e3ebdSchin n = 1;
2626da2e3ebdSchin *s++ = 0;
2627da2e3ebdSchin }
2628da2e3ebdSchin }
2629da2e3ebdSchin else
2630da2e3ebdSchin {
2631da2e3ebdSchin n = env->token.len - env->token.esc;
2632da2e3ebdSchin for (t = p, u = s + n; s < u; *s++ = *t++);
2633da2e3ebdSchin }
2634da2e3ebdSchin eat(env);
2635da2e3ebdSchin }
2636da2e3ebdSchin if (c == T_BAD)
2637da2e3ebdSchin return 0;
2638da2e3ebdSchin if (s > buf)
2639da2e3ebdSchin switch (c)
2640da2e3ebdSchin {
2641da2e3ebdSchin case T_STAR:
2642da2e3ebdSchin case T_PLUS:
2643da2e3ebdSchin case T_LEFT:
2644da2e3ebdSchin case T_QUES:
2645da2e3ebdSchin case T_BANG:
2646da2e3ebdSchin if ((s -= n) == buf)
2647da2e3ebdSchin e = 0;
2648da2e3ebdSchin else
2649da2e3ebdSchin {
2650da2e3ebdSchin i = s - buf;
2651da2e3ebdSchin if (!(e = node(env, REX_STRING, 0, 0, i)))
2652da2e3ebdSchin return 0;
2653da2e3ebdSchin memcpy((char*)(e->re.string.base = (unsigned char*)e->re.data), (char*)buf, i);
2654da2e3ebdSchin e->re.string.size = i;
2655da2e3ebdSchin }
2656da2e3ebdSchin if (x >= 0)
2657da2e3ebdSchin {
2658da2e3ebdSchin if (!(f = node(env, REX_ONECHAR, 1, 1, 0)))
2659da2e3ebdSchin {
2660da2e3ebdSchin drop(env->disc, e);
2661da2e3ebdSchin return 0;
2662da2e3ebdSchin }
2663da2e3ebdSchin f->re.onechar = (env->flags & REG_ICASE) ? toupper(x) : x;
2664da2e3ebdSchin }
2665da2e3ebdSchin else
2666da2e3ebdSchin {
26677c2fbfb3SApril Chin if (!(f = node(env, REX_STRING, 0, 0, n)))
2668da2e3ebdSchin return 0;
26697c2fbfb3SApril Chin memcpy((char*)(f->re.string.base = (unsigned char*)f->re.data), (char*)p, n);
26707c2fbfb3SApril Chin f->re.string.size = n;
2671da2e3ebdSchin }
2672da2e3ebdSchin if (!(f = rep(env, f, 0, 0)) || !(f = cat(env, f, seq(env))))
2673da2e3ebdSchin {
2674da2e3ebdSchin drop(env->disc, e);
2675da2e3ebdSchin return 0;
2676da2e3ebdSchin }
2677da2e3ebdSchin if (e)
2678da2e3ebdSchin f = cat(env, e, f);
2679da2e3ebdSchin return f;
2680da2e3ebdSchin default:
2681da2e3ebdSchin c = s - buf;
2682da2e3ebdSchin if (!(e = node(env, REX_STRING, 0, 0, c)))
2683da2e3ebdSchin return 0;
2684da2e3ebdSchin memcpy((char*)(e->re.string.base = (unsigned char*)e->re.data), (char*)buf, c);
2685da2e3ebdSchin e->re.string.size = c;
2686da2e3ebdSchin return cat(env, e, seq(env));
2687da2e3ebdSchin }
2688da2e3ebdSchin else if (c > T_BACK)
2689da2e3ebdSchin {
2690da2e3ebdSchin eat(env);
2691da2e3ebdSchin c -= T_BACK;
2692da2e3ebdSchin if (c > env->parno || !env->paren[c])
2693da2e3ebdSchin {
2694da2e3ebdSchin env->error = REG_ESUBREG;
2695da2e3ebdSchin return 0;
2696da2e3ebdSchin }
2697da2e3ebdSchin env->paren[c]->re.group.back = 1;
2698da2e3ebdSchin e = rep(env, node(env, REX_BACK, c, 0, 0), 0, 0);
2699da2e3ebdSchin }
2700da2e3ebdSchin else
2701da2e3ebdSchin switch (c)
2702da2e3ebdSchin {
2703da2e3ebdSchin case T_AND:
2704da2e3ebdSchin case T_CLOSE:
2705da2e3ebdSchin case T_BAR:
2706da2e3ebdSchin case T_END:
2707da2e3ebdSchin return node(env, REX_NULL, 0, 0, 0);
2708da2e3ebdSchin case T_DOLL:
2709da2e3ebdSchin eat(env);
2710da2e3ebdSchin e = rep(env, node(env, REX_END, 0, 0, 0), 0, 0);
2711da2e3ebdSchin break;
2712da2e3ebdSchin case T_CFLX:
2713da2e3ebdSchin eat(env);
2714da2e3ebdSchin if ((e = node(env, REX_BEG, 0, 0, 0)) && (env->flags & REG_EXTENDED))
2715da2e3ebdSchin e = rep(env, e, 0, 0);
2716da2e3ebdSchin break;
2717da2e3ebdSchin case T_OPEN:
2718da2e3ebdSchin tok = env->token;
2719da2e3ebdSchin eat(env);
2720da2e3ebdSchin flags = env->flags;
2721da2e3ebdSchin type = env->type;
2722da2e3ebdSchin if (env->token.att)
2723da2e3ebdSchin env->flags |= REG_MINIMAL;
2724da2e3ebdSchin env->parnest++;
2725da2e3ebdSchin if (env->type == KRE)
2726da2e3ebdSchin ++env->parno;
2727da2e3ebdSchin parno = ++env->parno;
2728da2e3ebdSchin if (!(e = alt(env, parno + 1, 0)))
2729da2e3ebdSchin break;
2730*b30d1939SAndy Fiddaman if (e->type == REX_NULL && env->type == ERE && !(env->flags & (REG_NULL|REG_REGEXP)))
2731da2e3ebdSchin {
2732da2e3ebdSchin drop(env->disc, e);
2733da2e3ebdSchin env->error = (*env->cursor == 0 || *env->cursor == env->delimiter || *env->cursor == env->terminator) ? REG_EPAREN : REG_ENULL;
2734da2e3ebdSchin return 0;
2735da2e3ebdSchin }
2736da2e3ebdSchin if (token(env) != T_CLOSE)
2737da2e3ebdSchin {
2738da2e3ebdSchin drop(env->disc, e);
2739da2e3ebdSchin env->error = REG_EPAREN;
2740da2e3ebdSchin return 0;
2741da2e3ebdSchin }
2742da2e3ebdSchin env->parnest--;
2743da2e3ebdSchin eat(env);
2744da2e3ebdSchin if (!(f = node(env, REX_GROUP, 0, 0, 0)))
2745da2e3ebdSchin {
2746da2e3ebdSchin drop(env->disc, e);
2747da2e3ebdSchin return 0;
2748da2e3ebdSchin }
2749da2e3ebdSchin if (parno < elementsof(env->paren))
2750da2e3ebdSchin env->paren[parno] = f;
2751da2e3ebdSchin f->re.group.back = 0;
2752da2e3ebdSchin f->re.group.number = parno;
2753da2e3ebdSchin f->re.group.expr.rex = e;
2754da2e3ebdSchin if (tok.lex)
2755da2e3ebdSchin {
2756da2e3ebdSchin tok.push = 1;
2757da2e3ebdSchin env->token = tok;
2758da2e3ebdSchin }
2759da2e3ebdSchin if (!(e = rep(env, f, parno, env->parno)))
2760da2e3ebdSchin return 0;
2761da2e3ebdSchin if (env->type == KRE)
2762da2e3ebdSchin {
2763da2e3ebdSchin if (!(f = node(env, REX_GROUP, 0, 0, 0)))
2764da2e3ebdSchin {
2765da2e3ebdSchin drop(env->disc, e);
2766da2e3ebdSchin return 0;
2767da2e3ebdSchin }
2768da2e3ebdSchin if (--parno < elementsof(env->paren))
2769da2e3ebdSchin env->paren[parno] = f;
2770da2e3ebdSchin f->re.group.back = 0;
2771da2e3ebdSchin f->re.group.number = parno;
2772da2e3ebdSchin f->re.group.expr.rex = e;
2773da2e3ebdSchin e = f;
2774da2e3ebdSchin }
2775da2e3ebdSchin env->flags = flags;
2776da2e3ebdSchin env->type = type;
2777da2e3ebdSchin break;
2778da2e3ebdSchin case T_GROUP:
2779da2e3ebdSchin p = env->cursor;
2780da2e3ebdSchin eat(env);
2781da2e3ebdSchin flags = env->flags;
2782da2e3ebdSchin type = env->type;
2783da2e3ebdSchin if (!(e = grp(env, env->parno + 1)))
2784da2e3ebdSchin {
2785da2e3ebdSchin if (env->error)
2786da2e3ebdSchin return 0;
2787da2e3ebdSchin if (env->literal == env->pattern && env->literal == p)
2788da2e3ebdSchin env->literal = env->cursor;
2789da2e3ebdSchin continue;
2790da2e3ebdSchin }
2791da2e3ebdSchin env->flags = flags;
2792da2e3ebdSchin env->type = type;
2793da2e3ebdSchin break;
2794da2e3ebdSchin case T_BRA:
2795da2e3ebdSchin eat(env);
2796da2e3ebdSchin if (e = bra(env))
2797da2e3ebdSchin e = rep(env, e, 0, 0);
2798da2e3ebdSchin break;
2799da2e3ebdSchin case T_ALNUM:
2800da2e3ebdSchin case T_ALNUM_NOT:
2801da2e3ebdSchin case T_DIGIT:
2802da2e3ebdSchin case T_DIGIT_NOT:
2803da2e3ebdSchin case T_SPACE:
2804da2e3ebdSchin case T_SPACE_NOT:
2805da2e3ebdSchin eat(env);
2806da2e3ebdSchin if (e = ccl(env, c))
2807da2e3ebdSchin e = rep(env, e, 0, 0);
2808da2e3ebdSchin break;
2809da2e3ebdSchin case T_LT:
2810da2e3ebdSchin eat(env);
2811da2e3ebdSchin e = rep(env, node(env, REX_WBEG, 0, 0, 0), 0, 0);
2812da2e3ebdSchin break;
2813da2e3ebdSchin case T_GT:
2814da2e3ebdSchin eat(env);
2815da2e3ebdSchin e = rep(env, node(env, REX_WEND, 0, 0, 0), 0, 0);
2816da2e3ebdSchin break;
2817da2e3ebdSchin case T_DOT:
2818da2e3ebdSchin eat(env);
2819da2e3ebdSchin e = rep(env, node(env, REX_DOT, 1, 1, 0), 0, 0);
2820da2e3ebdSchin break;
2821da2e3ebdSchin case T_DOTSTAR:
2822da2e3ebdSchin eat(env);
2823da2e3ebdSchin env->token.lex = T_STAR;
2824da2e3ebdSchin env->token.push = 1;
2825da2e3ebdSchin e = rep(env, node(env, REX_DOT, 1, 1, 0), 0, 0);
2826da2e3ebdSchin break;
2827da2e3ebdSchin case T_SLASHPLUS:
2828da2e3ebdSchin eat(env);
2829da2e3ebdSchin env->token.lex = T_PLUS;
2830da2e3ebdSchin env->token.push = 1;
2831da2e3ebdSchin if (e = node(env, REX_ONECHAR, 1, 1, 0))
2832da2e3ebdSchin {
2833da2e3ebdSchin e->re.onechar = '/';
2834da2e3ebdSchin e = rep(env, e, 0, 0);
2835da2e3ebdSchin }
2836da2e3ebdSchin break;
2837da2e3ebdSchin case T_WORD:
2838da2e3ebdSchin eat(env);
2839da2e3ebdSchin e = rep(env, node(env, REX_WORD, 0, 0, 0), 0, 0);
2840da2e3ebdSchin break;
2841da2e3ebdSchin case T_WORD_NOT:
2842da2e3ebdSchin eat(env);
2843da2e3ebdSchin e = rep(env, node(env, REX_WORD_NOT, 0, 0, 0), 0, 0);
2844da2e3ebdSchin break;
2845da2e3ebdSchin case T_BEG_STR:
2846da2e3ebdSchin eat(env);
2847da2e3ebdSchin e = rep(env, node(env, REX_BEG_STR, 0, 0, 0), 0, 0);
2848da2e3ebdSchin break;
2849da2e3ebdSchin case T_END_STR:
2850da2e3ebdSchin eat(env);
2851da2e3ebdSchin e = rep(env, node(env, REX_END_STR, 0, 0, 0), 0, 0);
2852da2e3ebdSchin break;
2853da2e3ebdSchin case T_FIN_STR:
2854da2e3ebdSchin eat(env);
2855da2e3ebdSchin e = rep(env, node(env, REX_FIN_STR, 0, 0, 0), 0, 0);
2856da2e3ebdSchin break;
2857da2e3ebdSchin default:
2858da2e3ebdSchin env->error = REG_BADRPT;
2859da2e3ebdSchin return 0;
2860da2e3ebdSchin }
2861da2e3ebdSchin if (e && *env->cursor != 0 && *env->cursor != env->delimiter && *env->cursor != env->terminator)
2862da2e3ebdSchin e = cat(env, e, seq(env));
2863da2e3ebdSchin return e;
2864da2e3ebdSchin }
2865da2e3ebdSchin }
2866da2e3ebdSchin
2867da2e3ebdSchin static Rex_t*
con(Cenv_t * env)2868da2e3ebdSchin con(Cenv_t* env)
2869da2e3ebdSchin {
2870da2e3ebdSchin Rex_t* e;
2871da2e3ebdSchin Rex_t* f;
2872da2e3ebdSchin Rex_t* g;
2873da2e3ebdSchin
2874da2e3ebdSchin if (!(e = seq(env)) || !(env->flags & REG_AUGMENTED) || token(env) != T_AND)
2875da2e3ebdSchin return e;
2876da2e3ebdSchin eat(env);
2877da2e3ebdSchin if (!(f = con(env)))
2878da2e3ebdSchin {
2879da2e3ebdSchin drop(env->disc, e);
2880da2e3ebdSchin return 0;
2881da2e3ebdSchin }
2882da2e3ebdSchin if (!(g = node(env, REX_CONJ, 0, 0, 0)))
2883da2e3ebdSchin {
2884da2e3ebdSchin drop(env->disc, e);
2885da2e3ebdSchin drop(env->disc, f);
2886da2e3ebdSchin return 0;
2887da2e3ebdSchin }
2888da2e3ebdSchin g->re.group.expr.binary.left = e;
2889da2e3ebdSchin g->re.group.expr.binary.right = f;
2890da2e3ebdSchin return g;
2891da2e3ebdSchin }
2892da2e3ebdSchin
2893da2e3ebdSchin static Rex_t*
alt(Cenv_t * env,int number,int cond)2894da2e3ebdSchin alt(Cenv_t* env, int number, int cond)
2895da2e3ebdSchin {
2896da2e3ebdSchin Rex_t* e;
2897da2e3ebdSchin Rex_t* f;
2898da2e3ebdSchin Rex_t* g;
2899da2e3ebdSchin
2900da2e3ebdSchin if (!(e = con(env)))
2901da2e3ebdSchin return 0;
2902da2e3ebdSchin else if (token(env) != T_BAR)
2903da2e3ebdSchin {
2904da2e3ebdSchin if (!cond)
2905da2e3ebdSchin return e;
2906da2e3ebdSchin f = 0;
2907da2e3ebdSchin if (e->type == REX_NULL)
2908da2e3ebdSchin goto bad;
2909da2e3ebdSchin }
2910da2e3ebdSchin else
2911da2e3ebdSchin {
2912da2e3ebdSchin eat(env);
2913da2e3ebdSchin if (!(f = alt(env, number, 0)))
2914da2e3ebdSchin {
2915da2e3ebdSchin drop(env->disc, e);
2916da2e3ebdSchin return 0;
2917da2e3ebdSchin }
2918*b30d1939SAndy Fiddaman if ((e->type == REX_NULL || f->type == REX_NULL) && !(env->flags & (REG_NULL|REG_REGEXP)))
2919da2e3ebdSchin goto bad;
2920da2e3ebdSchin if (!cond && (g = trie(env, e, f)))
2921da2e3ebdSchin return g;
2922da2e3ebdSchin }
2923da2e3ebdSchin if (!(g = node(env, REX_ALT, 0, 0, 0)))
2924da2e3ebdSchin {
2925da2e3ebdSchin env->error = REG_ESPACE;
2926da2e3ebdSchin goto bad;
2927da2e3ebdSchin }
2928da2e3ebdSchin g->re.group.number = number;
2929da2e3ebdSchin g->re.group.last = env->parno;
2930da2e3ebdSchin g->re.group.expr.binary.left = e;
2931da2e3ebdSchin g->re.group.expr.binary.right = f;
2932da2e3ebdSchin return g;
2933da2e3ebdSchin bad:
2934da2e3ebdSchin drop(env->disc, e);
2935da2e3ebdSchin drop(env->disc, f);
2936da2e3ebdSchin if (!env->error)
2937da2e3ebdSchin env->error = REG_ENULL;
2938da2e3ebdSchin return 0;
2939da2e3ebdSchin }
2940da2e3ebdSchin
2941da2e3ebdSchin /*
2942da2e3ebdSchin * add v to REX_BM tables
2943da2e3ebdSchin */
2944da2e3ebdSchin
2945da2e3ebdSchin static void
bmstr(Cenv_t * env,register Rex_t * a,unsigned char * v,int n,Bm_mask_t b)2946da2e3ebdSchin bmstr(Cenv_t* env, register Rex_t* a, unsigned char* v, int n, Bm_mask_t b)
2947da2e3ebdSchin {
2948da2e3ebdSchin int c;
2949da2e3ebdSchin int m;
2950da2e3ebdSchin size_t z;
2951da2e3ebdSchin
2952da2e3ebdSchin for (m = 0; m < n; m++)
2953da2e3ebdSchin {
2954da2e3ebdSchin if (!(z = n - m - 1))
2955da2e3ebdSchin z = HIT;
2956da2e3ebdSchin c = v[m];
2957da2e3ebdSchin a->re.bm.mask[m][c] |= b;
2958da2e3ebdSchin if (z == HIT || !a->re.bm.skip[c] || a->re.bm.skip[c] > z && a->re.bm.skip[c] < HIT)
2959da2e3ebdSchin a->re.bm.skip[c] = z;
2960da2e3ebdSchin if (a->flags & REG_ICASE)
2961da2e3ebdSchin {
2962da2e3ebdSchin if (isupper(c))
2963da2e3ebdSchin c = tolower(c);
2964da2e3ebdSchin else if (islower(c))
2965da2e3ebdSchin c = toupper(c);
2966da2e3ebdSchin else
2967da2e3ebdSchin continue;
2968da2e3ebdSchin a->re.bm.mask[m][c] |= b;
2969da2e3ebdSchin if (z == HIT || !a->re.bm.skip[c] || a->re.bm.skip[c] > z && a->re.bm.skip[c] < HIT)
2970da2e3ebdSchin a->re.bm.skip[c] = z;
2971da2e3ebdSchin }
2972da2e3ebdSchin }
2973da2e3ebdSchin }
2974da2e3ebdSchin
2975da2e3ebdSchin /*
2976da2e3ebdSchin * set up BM table from trie
2977da2e3ebdSchin */
2978da2e3ebdSchin
2979da2e3ebdSchin static int
bmtrie(Cenv_t * env,Rex_t * a,unsigned char * v,Trie_node_t * x,int n,int m,Bm_mask_t b)2980da2e3ebdSchin bmtrie(Cenv_t* env, Rex_t* a, unsigned char* v, Trie_node_t* x, int n, int m, Bm_mask_t b)
2981da2e3ebdSchin {
2982da2e3ebdSchin do
2983da2e3ebdSchin {
2984da2e3ebdSchin v[m] = x->c;
2985da2e3ebdSchin if (m >= (n - 1))
2986da2e3ebdSchin {
2987da2e3ebdSchin bmstr(env, a, v, n, b);
2988da2e3ebdSchin if (!(b <<= 1))
2989da2e3ebdSchin {
2990da2e3ebdSchin b = 1;
2991da2e3ebdSchin a->re.bm.complete = 0;
2992da2e3ebdSchin }
2993da2e3ebdSchin else if (x->son)
2994da2e3ebdSchin a->re.bm.complete = 0;
2995da2e3ebdSchin }
2996da2e3ebdSchin else if (x->son)
2997da2e3ebdSchin b = bmtrie(env, a, v, x->son, n, m + 1, b);
2998da2e3ebdSchin } while (x = x->sib);
2999da2e3ebdSchin return b;
3000da2e3ebdSchin }
3001da2e3ebdSchin
3002da2e3ebdSchin /*
3003da2e3ebdSchin * rewrite the expression tree for some special cases
3004da2e3ebdSchin * 1. it is a null expression - illegal
3005da2e3ebdSchin * 2. max length fixed string found -- use BM algorithm
3006da2e3ebdSchin * 3. it begins with an unanchored string - use KMP algorithm
3007da2e3ebdSchin * 0 returned on success
3008da2e3ebdSchin */
3009da2e3ebdSchin
3010da2e3ebdSchin static int
special(Cenv_t * env,regex_t * p)3011da2e3ebdSchin special(Cenv_t* env, regex_t* p)
3012da2e3ebdSchin {
3013da2e3ebdSchin Rex_t* a;
3014da2e3ebdSchin Rex_t* e;
3015da2e3ebdSchin Rex_t* t;
3016da2e3ebdSchin Rex_t* x;
3017da2e3ebdSchin Rex_t* y;
3018da2e3ebdSchin unsigned char* s;
3019da2e3ebdSchin int* f;
3020da2e3ebdSchin int n;
3021da2e3ebdSchin int m;
3022da2e3ebdSchin int k;
3023da2e3ebdSchin
3024da2e3ebdSchin DEBUG_INIT();
3025da2e3ebdSchin if (e = p->env->rex)
3026da2e3ebdSchin {
3027da2e3ebdSchin if ((x = env->stats.x) && x->re.string.size < 3)
3028da2e3ebdSchin x = 0;
3029da2e3ebdSchin if ((t = env->stats.y) && t->re.trie.min < 3)
3030da2e3ebdSchin t = 0;
3031da2e3ebdSchin if (x && t)
3032da2e3ebdSchin {
3033da2e3ebdSchin if (x->re.string.size >= t->re.trie.min)
3034da2e3ebdSchin t = 0;
3035da2e3ebdSchin else
3036da2e3ebdSchin x = 0;
3037da2e3ebdSchin }
30387c2fbfb3SApril Chin if (x || t)
3039da2e3ebdSchin {
3040da2e3ebdSchin Bm_mask_t** mask;
3041da2e3ebdSchin Bm_mask_t* h;
3042da2e3ebdSchin unsigned char* v;
3043da2e3ebdSchin size_t* q;
3044*b30d1939SAndy Fiddaman size_t l;
3045da2e3ebdSchin int i;
3046da2e3ebdSchin int j;
3047da2e3ebdSchin
3048da2e3ebdSchin if (x)
3049da2e3ebdSchin {
3050da2e3ebdSchin y = x;
3051da2e3ebdSchin n = m = x->re.string.size;
3052da2e3ebdSchin l = env->stats.l;
3053da2e3ebdSchin }
3054da2e3ebdSchin else
3055da2e3ebdSchin {
3056da2e3ebdSchin y = t;
3057da2e3ebdSchin n = t->re.trie.min;
3058da2e3ebdSchin m = t->re.trie.max;
3059da2e3ebdSchin l = env->stats.k;
3060da2e3ebdSchin }
3061da2e3ebdSchin if (!(q = (size_t*)alloc(env->disc, 0, (n + 1) * sizeof(size_t))))
3062da2e3ebdSchin return 1;
3063da2e3ebdSchin if (!(a = node(env, REX_BM, 0, 0, n * (sizeof(Bm_mask_t*) + (UCHAR_MAX + 1) * sizeof(Bm_mask_t)) + (UCHAR_MAX + n + 2) * sizeof(size_t))))
3064da2e3ebdSchin {
3065da2e3ebdSchin alloc(env->disc, q, 0);
3066da2e3ebdSchin return 1;
3067da2e3ebdSchin }
3068da2e3ebdSchin a->flags = y->flags;
3069da2e3ebdSchin a->map = y->map;
3070da2e3ebdSchin a->re.bm.size = n;
3071da2e3ebdSchin a->re.bm.back = (y == e || y == e->re.group.expr.rex) ? (m - n) : -1;
3072da2e3ebdSchin a->re.bm.left = l - 1;
3073da2e3ebdSchin a->re.bm.right = env->stats.m - l - n;
30743e14f97fSRoger A. Faulkner a->re.bm.complete = (env->stats.e || y != e && (e->type != REX_GROUP || y != e->re.group.expr.rex) || e->next || ((a->re.bm.left + a->re.bm.right) >= 0)) ? 0 : n;
3075da2e3ebdSchin h = (Bm_mask_t*)&a->re.bm.mask[n];
3076da2e3ebdSchin a->re.bm.skip = (size_t*)(h + n * (UCHAR_MAX + 1));
3077da2e3ebdSchin a->re.bm.fail = &a->re.bm.skip[UCHAR_MAX + 1];
3078da2e3ebdSchin for (m = 0; m <= UCHAR_MAX; m++)
3079da2e3ebdSchin a->re.bm.skip[m] = n;
3080da2e3ebdSchin a->re.bm.skip[0] = a->re.bm.skip[env->mappednewline] = (y->next && y->next->type == REX_END) ? HIT : (n + a->re.bm.left);
3081da2e3ebdSchin for (i = 1; i <= n; i++)
3082da2e3ebdSchin a->re.bm.fail[i] = 2 * n - i;
3083da2e3ebdSchin mask = a->re.bm.mask;
3084da2e3ebdSchin for (m = 0; m < n; m++)
3085da2e3ebdSchin {
3086da2e3ebdSchin mask[m] = h;
3087da2e3ebdSchin h += UCHAR_MAX + 1;
3088da2e3ebdSchin }
3089da2e3ebdSchin if (x)
3090da2e3ebdSchin bmstr(env, a, x->re.string.base, n, 1);
3091da2e3ebdSchin else
3092da2e3ebdSchin {
3093da2e3ebdSchin v = (unsigned char*)q;
3094da2e3ebdSchin memset(v, 0, n);
3095da2e3ebdSchin m = 1;
3096da2e3ebdSchin for (i = 0; i <= UCHAR_MAX; i++)
3097da2e3ebdSchin if (t->re.trie.root[i])
3098da2e3ebdSchin m = bmtrie(env, a, v, t->re.trie.root[i], n, 0, m);
3099da2e3ebdSchin }
3100da2e3ebdSchin mask--;
3101da2e3ebdSchin memset(q, 0, n * sizeof(*q));
3102da2e3ebdSchin for (k = (j = n) + 1; j > 0; j--, k--)
3103da2e3ebdSchin {
3104da2e3ebdSchin DEBUG_TEST(0x0010,(sfprintf(sfstderr, "BM#0: k=%d j=%d\n", k, j)),(0));
3105da2e3ebdSchin for (q[j] = k; k <= n; k = q[k])
3106da2e3ebdSchin {
3107da2e3ebdSchin for (m = 0; m <= UCHAR_MAX; m++)
3108da2e3ebdSchin if (mask[k][m] == mask[j][m])
3109da2e3ebdSchin {
3110da2e3ebdSchin DEBUG_TEST(0x0010,sfprintf(sfstderr, "CUT1: mask[%d][%c]=mask[%d][%c]\n", k, m, j, m), (0));
3111da2e3ebdSchin goto cut;
3112da2e3ebdSchin }
3113da2e3ebdSchin DEBUG_TEST(0x0010,sfprintf(sfstderr, "BM#2: fail[%d]=%d => %d\n", k, a->re.bm.fail[k], (a->re.bm.fail[k] > n - j) ? (n - j) : a->re.bm.fail[k]), (0));
3114da2e3ebdSchin if (a->re.bm.fail[k] > n - j)
3115da2e3ebdSchin a->re.bm.fail[k] = n - j;
3116da2e3ebdSchin }
3117da2e3ebdSchin cut: ;
3118da2e3ebdSchin }
3119da2e3ebdSchin for (i = 1; i <= n; i++)
3120da2e3ebdSchin if (a->re.bm.fail[i] > n + k - i)
3121da2e3ebdSchin {
3122da2e3ebdSchin DEBUG_TEST(0x0010,sfprintf(sfstderr, "BM#4: fail[%d]=%d => %d\n", i, a->re.bm.fail[i], n + k - i), (0));
3123da2e3ebdSchin a->re.bm.fail[i] = n + k - i;
3124da2e3ebdSchin }
3125da2e3ebdSchin #if _AST_REGEX_DEBUG
3126da2e3ebdSchin if (DEBUG_TEST(0x0020,(1),(0)))
3127da2e3ebdSchin {
3128da2e3ebdSchin sfprintf(sfstderr, "STAT: complete=%d n=%d k=%d l=%d r=%d y=%d:%d e=%d:%d\n", a->re.bm.complete, n, k, a->re.bm.left, a->re.bm.right, y->type, y->next ? y->next->type : 0, e->type, e->next ? e->next->type : 0);
3129da2e3ebdSchin for (m = 0; m < n; m++)
3130da2e3ebdSchin for (i = 1; i <= UCHAR_MAX; i++)
3131da2e3ebdSchin if (a->re.bm.mask[m][i])
3132da2e3ebdSchin sfprintf(sfstderr, "MASK: [%d]['%c'] = %032..2u\n", m, i, a->re.bm.mask[m][i]);
3133da2e3ebdSchin for (i = ' '; i <= UCHAR_MAX; i++)
3134da2e3ebdSchin if (a->re.bm.skip[i] >= HIT)
3135da2e3ebdSchin sfprintf(sfstderr, "SKIP: ['%c'] = *\n", i);
3136da2e3ebdSchin else if (a->re.bm.skip[i] > 0 && a->re.bm.skip[i] < n)
3137da2e3ebdSchin sfprintf(sfstderr, "SKIP: ['%c'] = %3d\n", i, a->re.bm.skip[i]);
3138da2e3ebdSchin for (j = 31; j >= 0; j--)
3139da2e3ebdSchin {
3140da2e3ebdSchin sfprintf(sfstderr, " ");
3141da2e3ebdSchin next:
3142da2e3ebdSchin for (m = 0; m < n; m++)
3143da2e3ebdSchin {
3144da2e3ebdSchin for (i = 0040; i < 0177; i++)
3145da2e3ebdSchin if (a->re.bm.mask[m][i] & (1 << j))
3146da2e3ebdSchin {
3147da2e3ebdSchin sfprintf(sfstderr, " %c", i);
3148da2e3ebdSchin break;
3149da2e3ebdSchin }
3150da2e3ebdSchin if (i >= 0177)
3151da2e3ebdSchin {
3152da2e3ebdSchin if (j > 0)
3153da2e3ebdSchin {
3154da2e3ebdSchin j--;
3155da2e3ebdSchin goto next;
3156da2e3ebdSchin }
3157da2e3ebdSchin sfprintf(sfstderr, " ?");
3158da2e3ebdSchin }
3159da2e3ebdSchin }
3160da2e3ebdSchin sfprintf(sfstderr, "\n");
3161da2e3ebdSchin }
3162da2e3ebdSchin sfprintf(sfstderr, "FAIL: ");
3163da2e3ebdSchin for (m = 1; m <= n; m++)
3164da2e3ebdSchin sfprintf(sfstderr, "%3d", a->re.bm.fail[m]);
3165da2e3ebdSchin sfprintf(sfstderr, "\n");
3166da2e3ebdSchin }
3167da2e3ebdSchin #endif
3168da2e3ebdSchin alloc(env->disc, q, 0);
3169da2e3ebdSchin a->next = e;
3170da2e3ebdSchin p->env->rex = a;
3171da2e3ebdSchin return 0;
3172da2e3ebdSchin }
3173da2e3ebdSchin switch (e->type)
3174da2e3ebdSchin {
3175da2e3ebdSchin case REX_BEG:
3176da2e3ebdSchin if (env->flags & REG_NEWLINE)
3177da2e3ebdSchin return 0;
3178da2e3ebdSchin break;
3179da2e3ebdSchin case REX_GROUP:
3180da2e3ebdSchin if (env->stats.b)
3181da2e3ebdSchin return 0;
3182da2e3ebdSchin e = e->re.group.expr.rex;
3183da2e3ebdSchin if (e->type != REX_DOT)
3184da2e3ebdSchin return 0;
3185da2e3ebdSchin /*FALLTHROUGH*/
3186da2e3ebdSchin case REX_DOT:
3187da2e3ebdSchin if (e->lo == 0 && e->hi == RE_DUP_INF)
3188da2e3ebdSchin break;
3189da2e3ebdSchin return 0;
3190da2e3ebdSchin case REX_NULL:
3191*b30d1939SAndy Fiddaman if (env->flags & (REG_NULL|REG_REGEXP))
3192da2e3ebdSchin break;
3193da2e3ebdSchin env->error = REG_ENULL;
3194da2e3ebdSchin return 1;
3195da2e3ebdSchin case REX_STRING:
31967c2fbfb3SApril Chin if ((env->flags & (REG_LEFT|REG_LITERAL|REG_RIGHT)) || e->map)
3197da2e3ebdSchin return 0;
3198da2e3ebdSchin s = e->re.string.base;
3199da2e3ebdSchin n = e->re.string.size;
3200da2e3ebdSchin if (!(a = node(env, REX_KMP, 0, 0, n * (sizeof(int*) + 1))))
3201da2e3ebdSchin return 1;
3202da2e3ebdSchin a->flags = e->flags;
3203da2e3ebdSchin a->map = e->map;
3204da2e3ebdSchin f = a->re.string.fail;
3205da2e3ebdSchin memcpy((char*)(a->re.string.base = (unsigned char*)&f[n]), (char*)s, n);
3206da2e3ebdSchin s = a->re.string.base;
3207da2e3ebdSchin a->re.string.size = n;
3208da2e3ebdSchin f[0] = m = -1;
3209da2e3ebdSchin for (k = 1; k < n; k++)
3210da2e3ebdSchin {
3211da2e3ebdSchin while (m >= 0 && s[m+1] != s[k])
3212da2e3ebdSchin m = f[m];
3213da2e3ebdSchin if (s[m+1] == s[k])
3214da2e3ebdSchin m++;
3215da2e3ebdSchin f[k] = m;
3216da2e3ebdSchin }
3217da2e3ebdSchin a->next = e->next;
3218da2e3ebdSchin p->env->rex = a;
3219da2e3ebdSchin e->next = 0;
3220da2e3ebdSchin drop(env->disc, e);
3221da2e3ebdSchin break;
3222da2e3ebdSchin default:
3223da2e3ebdSchin return 0;
3224da2e3ebdSchin }
3225da2e3ebdSchin }
3226da2e3ebdSchin p->env->once = 1;
3227da2e3ebdSchin return 0;
3228da2e3ebdSchin }
3229da2e3ebdSchin
3230da2e3ebdSchin int
regcomp(regex_t * p,const char * pattern,regflags_t flags)3231da2e3ebdSchin regcomp(regex_t* p, const char* pattern, regflags_t flags)
3232da2e3ebdSchin {
3233da2e3ebdSchin Rex_t* e;
3234da2e3ebdSchin Rex_t* f;
3235da2e3ebdSchin regdisc_t* disc;
3236da2e3ebdSchin unsigned char* fold;
3237da2e3ebdSchin int i;
3238da2e3ebdSchin Cenv_t env;
3239da2e3ebdSchin
3240da2e3ebdSchin if (!p)
3241da2e3ebdSchin return REG_BADPAT;
3242da2e3ebdSchin if (flags & REG_DISCIPLINE)
3243da2e3ebdSchin {
3244da2e3ebdSchin flags &= ~REG_DISCIPLINE;
3245da2e3ebdSchin disc = p->re_disc;
3246da2e3ebdSchin }
3247da2e3ebdSchin else
3248da2e3ebdSchin disc = &state.disc;
3249da2e3ebdSchin if (!disc->re_errorlevel)
3250da2e3ebdSchin disc->re_errorlevel = 2;
3251da2e3ebdSchin p->env = 0;
3252da2e3ebdSchin if (!pattern)
3253da2e3ebdSchin return fatal(disc, REG_BADPAT, pattern);
3254da2e3ebdSchin if (!state.initialized)
3255da2e3ebdSchin {
3256da2e3ebdSchin state.initialized = 1;
3257da2e3ebdSchin for (i = 0; i < elementsof(state.escape); i++)
3258da2e3ebdSchin state.magic[state.escape[i].key] = state.escape[i].val;
3259da2e3ebdSchin }
3260da2e3ebdSchin if (!(fold = (unsigned char*)LCINFO(AST_LC_CTYPE)->data))
3261da2e3ebdSchin {
3262da2e3ebdSchin if (!(fold = newof(0, unsigned char, UCHAR_MAX, 1)))
3263da2e3ebdSchin return fatal(disc, REG_ESPACE, pattern);
3264da2e3ebdSchin for (i = 0; i <= UCHAR_MAX; i++)
3265da2e3ebdSchin fold[i] = toupper(i);
3266da2e3ebdSchin LCINFO(AST_LC_CTYPE)->data = (void*)fold;
3267da2e3ebdSchin }
3268da2e3ebdSchin again:
3269da2e3ebdSchin if (!(p->env = (Env_t*)alloc(disc, 0, sizeof(Env_t))))
3270da2e3ebdSchin return fatal(disc, REG_ESPACE, pattern);
3271da2e3ebdSchin memset(p->env, 0, sizeof(*p->env));
3272da2e3ebdSchin memset(&env, 0, sizeof(env));
3273da2e3ebdSchin env.regex = p;
3274da2e3ebdSchin env.flags = flags;
3275da2e3ebdSchin env.disc = p->env->disc = disc;
3276da2e3ebdSchin if (env.flags & REG_AUGMENTED)
3277da2e3ebdSchin env.flags |= REG_EXTENDED;
3278da2e3ebdSchin env.mappeddot = '.';
3279da2e3ebdSchin env.mappednewline = '\n';
3280da2e3ebdSchin env.mappedslash = '/';
3281da2e3ebdSchin if (disc->re_version >= REG_VERSION_MAP && disc->re_map)
3282da2e3ebdSchin {
3283da2e3ebdSchin env.map = disc->re_map;
3284da2e3ebdSchin env.MAP = p->env->fold;
3285da2e3ebdSchin for (i = 0; i <= UCHAR_MAX; i++)
3286da2e3ebdSchin {
3287da2e3ebdSchin env.MAP[i] = fold[env.map[i]];
3288da2e3ebdSchin if (env.map[i] == '.')
3289da2e3ebdSchin env.mappeddot = i;
3290da2e3ebdSchin if (env.map[i] == '\n')
3291da2e3ebdSchin env.mappednewline = i;
3292da2e3ebdSchin if (env.map[i] == '/')
3293da2e3ebdSchin env.mappedslash = i;
3294da2e3ebdSchin }
3295da2e3ebdSchin }
3296da2e3ebdSchin else
3297da2e3ebdSchin env.MAP = fold;
3298da2e3ebdSchin env.type = (env.flags & REG_AUGMENTED) ? ARE : (env.flags & REG_EXTENDED) ? ERE : BRE;
3299da2e3ebdSchin env.explicit = -1;
3300da2e3ebdSchin if (env.flags & REG_SHELL)
3301da2e3ebdSchin {
3302da2e3ebdSchin if (env.flags & REG_SHELL_PATH)
3303da2e3ebdSchin env.explicit = env.mappedslash;
3304*b30d1939SAndy Fiddaman if (!(env.flags & REG_SHELL_ESCAPED))
3305*b30d1939SAndy Fiddaman env.flags |= REG_CLASS_ESCAPE;
3306da2e3ebdSchin env.flags |= REG_LENIENT|REG_NULL;
3307da2e3ebdSchin env.type = env.type == BRE ? SRE : KRE;
3308da2e3ebdSchin }
3309*b30d1939SAndy Fiddaman else
3310*b30d1939SAndy Fiddaman env.flags &= ~(REG_SHELL_DOT|REG_SHELL_ESCAPED|REG_SHELL_GROUP|REG_SHELL_PATH);
3311da2e3ebdSchin if ((env.flags & (REG_NEWLINE|REG_SPAN)) == REG_NEWLINE)
3312da2e3ebdSchin env.explicit = env.mappednewline;
3313da2e3ebdSchin p->env->leading = (env.flags & REG_SHELL_DOT) ? env.mappeddot : -1;
3314da2e3ebdSchin env.posixkludge = !(env.flags & (REG_EXTENDED|REG_SHELL));
3315da2e3ebdSchin env.token.lex = 0;
3316da2e3ebdSchin env.token.push = 0;
3317da2e3ebdSchin if (env.flags & REG_DELIMITED)
3318da2e3ebdSchin {
3319da2e3ebdSchin switch (env.delimiter = *pattern++)
3320da2e3ebdSchin {
3321da2e3ebdSchin case 0:
3322da2e3ebdSchin case '\\':
3323da2e3ebdSchin case '\n':
3324da2e3ebdSchin case '\r':
3325da2e3ebdSchin env.error = REG_EDELIM;
3326da2e3ebdSchin goto bad;
3327da2e3ebdSchin }
3328da2e3ebdSchin env.terminator = '\n';
3329da2e3ebdSchin }
3330da2e3ebdSchin env.literal = env.pattern = env.cursor = (unsigned char*)pattern;
3331da2e3ebdSchin if (!(p->env->rex = alt(&env, 1, 0)))
3332da2e3ebdSchin goto bad;
3333da2e3ebdSchin if (env.parnest)
3334da2e3ebdSchin {
3335da2e3ebdSchin env.error = REG_EPAREN;
3336da2e3ebdSchin goto bad;
3337da2e3ebdSchin }
3338*b30d1939SAndy Fiddaman if ((env.flags & REG_LEFT) && p->env->rex->type != REX_BEG)
3339da2e3ebdSchin {
3340*b30d1939SAndy Fiddaman if (p->env->rex->type == REX_ALT)
3341*b30d1939SAndy Fiddaman env.flags &= ~REG_FIRST;
3342*b30d1939SAndy Fiddaman if (!(e = node(&env, REX_BEG, 0, 0, 0)))
3343da2e3ebdSchin {
3344*b30d1939SAndy Fiddaman regfree(p);
3345*b30d1939SAndy Fiddaman return fatal(disc, REG_ESPACE, pattern);
3346da2e3ebdSchin }
3347*b30d1939SAndy Fiddaman e->next = p->env->rex;
3348*b30d1939SAndy Fiddaman p->env->rex = e;
3349*b30d1939SAndy Fiddaman p->env->once = 1;
3350da2e3ebdSchin }
3351da2e3ebdSchin for (e = p->env->rex; e->next; e = e->next);
3352da2e3ebdSchin p->env->done.type = REX_DONE;
3353da2e3ebdSchin p->env->done.flags = e->flags;
3354*b30d1939SAndy Fiddaman if ((env.flags & REG_RIGHT) && e->type != REX_END)
3355da2e3ebdSchin {
3356*b30d1939SAndy Fiddaman if (p->env->rex->type == REX_ALT)
3357*b30d1939SAndy Fiddaman env.flags &= ~REG_FIRST;
3358*b30d1939SAndy Fiddaman if (!(f = node(&env, REX_END, 0, 0, 0)))
3359da2e3ebdSchin {
3360*b30d1939SAndy Fiddaman regfree(p);
3361*b30d1939SAndy Fiddaman return fatal(disc, REG_ESPACE, pattern);
3362da2e3ebdSchin }
3363*b30d1939SAndy Fiddaman f->flags = e->flags;
3364*b30d1939SAndy Fiddaman f->map = e->map;
3365*b30d1939SAndy Fiddaman e->next = f;
3366da2e3ebdSchin }
3367da2e3ebdSchin if (stats(&env, p->env->rex))
3368da2e3ebdSchin {
3369da2e3ebdSchin if (!env.error)
3370da2e3ebdSchin env.error = REG_ECOUNT;
3371da2e3ebdSchin goto bad;
3372da2e3ebdSchin }
3373da2e3ebdSchin if (env.stats.b)
3374da2e3ebdSchin p->env->hard = p->env->separate = 1;
3375da2e3ebdSchin else if (!(env.flags & REG_FIRST) && (env.stats.a || env.stats.c > 1 && env.stats.c != env.stats.s || env.stats.t && (env.stats.t > 1 || env.stats.a || env.stats.c)))
3376da2e3ebdSchin p->env->hard = 1;
3377da2e3ebdSchin if (p->env->hard || env.stats.c || env.stats.i)
3378da2e3ebdSchin p->env->stats.re_min = p->env->stats.re_max = -1;
3379da2e3ebdSchin else
3380da2e3ebdSchin {
3381da2e3ebdSchin if (!(p->env->stats.re_min = env.stats.m))
3382da2e3ebdSchin p->env->stats.re_min = -1;
3383da2e3ebdSchin if (!(p->env->stats.re_max = env.stats.n))
3384da2e3ebdSchin p->env->stats.re_max = -1;
3385da2e3ebdSchin }
3386da2e3ebdSchin if (special(&env, p))
3387da2e3ebdSchin goto bad;
3388da2e3ebdSchin serialize(&env, p->env->rex, 1);
3389da2e3ebdSchin p->re_nsub = env.stats.p;
3390da2e3ebdSchin if (env.type == KRE)
3391da2e3ebdSchin p->re_nsub /= 2;
3392da2e3ebdSchin if (env.flags & REG_DELIMITED)
3393da2e3ebdSchin {
3394da2e3ebdSchin p->re_npat = env.cursor - env.pattern + 1;
3395da2e3ebdSchin if (*env.cursor == env.delimiter)
3396da2e3ebdSchin p->re_npat++;
3397da2e3ebdSchin else if (env.flags & REG_MUSTDELIM)
3398da2e3ebdSchin {
3399da2e3ebdSchin env.error = REG_EDELIM;
3400da2e3ebdSchin goto bad;
3401da2e3ebdSchin }
3402da2e3ebdSchin else
3403da2e3ebdSchin env.flags &= ~REG_DELIMITED;
3404da2e3ebdSchin }
3405da2e3ebdSchin p->env->explicit = env.explicit;
3406da2e3ebdSchin p->env->flags = env.flags & REG_COMP;
3407da2e3ebdSchin p->env->min = env.stats.m;
3408da2e3ebdSchin p->env->nsub = env.stats.p + env.stats.u;
3409da2e3ebdSchin p->env->refs = 1;
3410da2e3ebdSchin return 0;
3411da2e3ebdSchin bad:
3412da2e3ebdSchin regfree(p);
3413da2e3ebdSchin if (!env.error)
3414da2e3ebdSchin env.error = REG_ESPACE;
3415da2e3ebdSchin if (env.type >= SRE && env.error != REG_ESPACE && !(flags & REG_LITERAL))
3416da2e3ebdSchin {
3417da2e3ebdSchin flags |= REG_LITERAL;
3418da2e3ebdSchin pattern = (const char*)env.literal;
3419da2e3ebdSchin goto again;
3420da2e3ebdSchin }
3421da2e3ebdSchin return fatal(disc, env.error, pattern);
3422da2e3ebdSchin }
3423da2e3ebdSchin
3424da2e3ebdSchin /*
3425da2e3ebdSchin * regcomp() on sized pattern
3426da2e3ebdSchin * the lazy way around adding and checking env.end
3427da2e3ebdSchin */
3428da2e3ebdSchin
3429da2e3ebdSchin int
regncomp(regex_t * p,const char * pattern,size_t size,regflags_t flags)3430da2e3ebdSchin regncomp(regex_t* p, const char* pattern, size_t size, regflags_t flags)
3431da2e3ebdSchin {
3432da2e3ebdSchin char* s;
3433da2e3ebdSchin int r;
3434da2e3ebdSchin
3435da2e3ebdSchin if (!(s = malloc(size + 1)))
3436da2e3ebdSchin return fatal((flags & REG_DISCIPLINE) ? p->re_disc : &state.disc, REG_ESPACE, pattern);
3437da2e3ebdSchin memcpy(s, pattern, size);
3438da2e3ebdSchin s[size] = 0;
3439da2e3ebdSchin r = regcomp(p, s, flags);
3440da2e3ebdSchin free(s);
3441da2e3ebdSchin return r;
3442da2e3ebdSchin }
3443da2e3ebdSchin
3444da2e3ebdSchin /*
3445da2e3ebdSchin * combine two compiled regular expressions if possible,
3446da2e3ebdSchin * replacing first with the combination and freeing second.
3447da2e3ebdSchin * return 0 on success.
3448da2e3ebdSchin * the only combinations handled are building a Trie
3449da2e3ebdSchin * from String|Kmp|Trie and String|Kmp
3450da2e3ebdSchin */
3451da2e3ebdSchin
3452da2e3ebdSchin int
regcomb(regex_t * p,regex_t * q)3453da2e3ebdSchin regcomb(regex_t* p, regex_t* q)
3454da2e3ebdSchin {
3455da2e3ebdSchin Rex_t* e = p->env->rex;
3456da2e3ebdSchin Rex_t* f = q->env->rex;
3457da2e3ebdSchin Rex_t* g;
34583e14f97fSRoger A. Faulkner Rex_t* h;
3459da2e3ebdSchin Cenv_t env;
3460da2e3ebdSchin
3461da2e3ebdSchin if (!e || !f)
3462da2e3ebdSchin return fatal(p->env->disc, REG_BADPAT, NiL);
3463da2e3ebdSchin if (p->env->separate || q->env->separate)
3464da2e3ebdSchin return REG_ESUBREG;
3465da2e3ebdSchin memset(&env, 0, sizeof(env));
3466da2e3ebdSchin env.disc = p->env->disc;
3467da2e3ebdSchin if (e->type == REX_BM)
3468da2e3ebdSchin {
3469da2e3ebdSchin p->env->rex = e->next;
3470da2e3ebdSchin e->next = 0;
3471da2e3ebdSchin drop(env.disc, e);
3472da2e3ebdSchin e = p->env->rex;
3473da2e3ebdSchin }
3474da2e3ebdSchin if (f->type == REX_BM)
3475da2e3ebdSchin {
3476da2e3ebdSchin q->env->rex = f->next;
3477da2e3ebdSchin f->next = 0;
3478da2e3ebdSchin drop(env.disc, f);
3479da2e3ebdSchin f = q->env->rex;
3480da2e3ebdSchin }
3481da2e3ebdSchin if (e->type == REX_BEG && f->type == REX_BEG)
3482da2e3ebdSchin {
3483da2e3ebdSchin p->env->flags |= REG_LEFT;
3484da2e3ebdSchin p->env->rex = e->next;
3485da2e3ebdSchin e->next = 0;
3486da2e3ebdSchin drop(env.disc, e);
3487da2e3ebdSchin e = p->env->rex;
3488da2e3ebdSchin q->env->rex = f->next;
3489da2e3ebdSchin f->next = 0;
3490da2e3ebdSchin drop(env.disc, f);
3491da2e3ebdSchin f = q->env->rex;
3492da2e3ebdSchin }
34933e14f97fSRoger A. Faulkner for (g = e; g->next; g = g->next);
34943e14f97fSRoger A. Faulkner for (h = f; h->next; h = h->next);
34953e14f97fSRoger A. Faulkner if (g->next && g->next->type == REX_END && h->next && h->next->type == REX_END)
3496da2e3ebdSchin {
3497da2e3ebdSchin p->env->flags |= REG_RIGHT;
34983e14f97fSRoger A. Faulkner drop(env.disc, g->next);
34993e14f97fSRoger A. Faulkner g->next = 0;
35003e14f97fSRoger A. Faulkner drop(env.disc, h->next);
35013e14f97fSRoger A. Faulkner h->next = 0;
3502da2e3ebdSchin }
3503da2e3ebdSchin if (!(g = trie(&env, f, e)))
3504da2e3ebdSchin return fatal(p->env->disc, REG_BADPAT, NiL);
3505da2e3ebdSchin p->env->rex = g;
3506da2e3ebdSchin if (!q->env->once)
3507da2e3ebdSchin p->env->once = 0;
3508da2e3ebdSchin q->env->rex = 0;
3509da2e3ebdSchin if (p->env->flags & REG_LEFT)
3510da2e3ebdSchin {
3511da2e3ebdSchin if (!(e = node(&env, REX_BEG, 0, 0, 0)))
3512da2e3ebdSchin {
3513da2e3ebdSchin regfree(p);
3514da2e3ebdSchin return fatal(p->env->disc, REG_ESPACE, NiL);
3515da2e3ebdSchin }
3516da2e3ebdSchin e->next = p->env->rex;
3517da2e3ebdSchin p->env->rex = e;
3518da2e3ebdSchin p->env->once = 1;
3519da2e3ebdSchin }
3520da2e3ebdSchin if (p->env->flags & REG_RIGHT)
3521da2e3ebdSchin {
3522da2e3ebdSchin for (f = p->env->rex; f->next; f = f->next);
3523da2e3ebdSchin if (f->type != REX_END)
3524da2e3ebdSchin {
3525da2e3ebdSchin if (!(e = node(&env, REX_END, 0, 0, 0)))
3526da2e3ebdSchin {
3527da2e3ebdSchin regfree(p);
3528da2e3ebdSchin return fatal(p->env->disc, REG_ESPACE, NiL);
3529da2e3ebdSchin }
3530da2e3ebdSchin f->next = e;
3531da2e3ebdSchin }
3532da2e3ebdSchin }
3533da2e3ebdSchin env.explicit = p->env->explicit;
3534da2e3ebdSchin env.flags = p->env->flags;
3535da2e3ebdSchin env.disc = p->env->disc;
3536da2e3ebdSchin if (stats(&env, p->env->rex))
3537da2e3ebdSchin {
3538da2e3ebdSchin regfree(p);
3539da2e3ebdSchin return fatal(p->env->disc, env.error ? env.error : REG_ECOUNT, NiL);
3540da2e3ebdSchin }
3541da2e3ebdSchin if (special(&env, p))
3542da2e3ebdSchin {
3543da2e3ebdSchin regfree(p);
3544da2e3ebdSchin return fatal(p->env->disc, env.error ? env.error : REG_ESPACE, NiL);
3545da2e3ebdSchin }
3546da2e3ebdSchin p->env->min = g->re.trie.min;
3547da2e3ebdSchin return 0;
3548da2e3ebdSchin }
3549da2e3ebdSchin
3550da2e3ebdSchin /*
3551da2e3ebdSchin * copy a reference of p into q
3552da2e3ebdSchin * p and q may then have separate regsubcomp() instantiations
3553da2e3ebdSchin */
3554da2e3ebdSchin
3555da2e3ebdSchin int
regdup(regex_t * p,regex_t * q)3556da2e3ebdSchin regdup(regex_t* p, regex_t* q)
3557da2e3ebdSchin {
3558da2e3ebdSchin if (!p || !q)
3559da2e3ebdSchin return REG_BADPAT;
3560da2e3ebdSchin *q = *p;
3561da2e3ebdSchin p->env->refs++;
3562da2e3ebdSchin q->re_sub = 0;
3563da2e3ebdSchin return 0;
3564da2e3ebdSchin }
3565