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