/***********************************************************************

*                                                                      *

*               This software is part of the ast package               *

*          Copyright (c) 1985-2012 AT&T Intellectual Property          *

*                      and is licensed under the                       *

*                 Eclipse Public License, Version 1.0                  *

*                    by AT&T Intellectual Property                     *

*                                                                      *

*                A copy of the License is available at                 *

*          http://www.eclipse.org/org/documents/epl-v10.html           *

*         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *

*                                                                      *

*              Information and Software Systems Research               *

*                            AT&T Research                             *

*                           Florham Park NJ                            *

*                                                                      *

*                 Glenn Fowler <gsf@research.att.com>                  *

*                  David Korn <dgk@research.att.com>                   *

*                   Phong Vo <kpv@research.att.com>                    *

*                                                                      *

***********************************************************************/

#pragma prototyped

/*

 * posix regex compiler

 */

#include "reglib.h"

#if _PACKAGE_ast

#include "lclib.h"

#endif

#define serialize		re_serialize	/* hp.ia64 <unistd.h>! */

#define C_ESC			(-1)

#define C_MB			(-2)

#if _AST_REGEX_DEBUG

#define DEBUG_TEST(f,y,n)	((debug&(debug_flag=f))?(y):(n))

#define DEBUG_CODE(f,y,n)	do if(debug&(f)){y}else{n} while(0)

#define DEBUG_INIT()		do { char* t; if (!debug) { debug = 0x80000000; if (t = getenv("_AST_regex_comp_debug")) debug |= strtoul(t, NiL, 0); } } while (0)

static unsigned long	debug;

static unsigned long	debug_flag;

#else

#define DEBUG_INIT()

#define DEBUG_TEST(f,y,n)	(n)

#define DEBUG_CODE(f,y,n)	do {n} while(0)

#endif

#if _PACKAGE_ast

typedef struct Cchr_s

{

	Dtlink_t	lnk;

	unsigned char	nam[2];

	Ckey_t		key;

} Cchr_t;

#endif

#define eat(p)		do{if ((p)->token.push)(p)->token.push=0;else (p)->cursor+=(p)->token.len;}while (0)

/*

 * determine whether greedy matching will work, i.e. produce

 * the best match first.  such expressions are "easy", and

 * need no backtracking once a complete match is found.  

 * if an expression has backreferences or alts it's hard

 * else if it has only one closure it's easy

 * else if all closures are simple (i.e. one-character) it's easy

 * else it's hard.

 */

typedef struct Stats_s

{

	unsigned long	l;	/* min length to left of x		*/

	unsigned long	k;	/* min length to left of y		*/

	unsigned long	m;	/* min length				*/

	unsigned long	n;	/* max length				*/

	unsigned short	a;	/* number of alternations		*/

	unsigned short	b;	/* number of backrefs			*/

	unsigned short	c;	/* number of closures			*/

	unsigned short	e;	/* $					*/

	unsigned short	i;	/* number of negations			*/

	unsigned short	p;	/* number of named subexpressions	*/

	unsigned short	s;	/* number of simple closures		*/

	unsigned short	t;	/* number of tries			*/

	unsigned short	u;	/* number of unnamed subexpressions	*/

	Rex_t*		x;	/* max length REX_STRING		*/

	Rex_t*		y;	/* max length REX_TRIE			*/

} Stats_t;

typedef struct Token_s

{

	unsigned long	min;

	unsigned long	max;

	short		lex;

	short		len;

	short		esc;

	short		att;

	short		push;

} Token_t;

typedef struct Cenv_s

{

	int		delimiter;	/* pattern delimiter		*/

	int		error;		/* last error			*/

	int		explicit;	/* explicit match on this char	*/

	int		mappeddot;	/* inverse mapped '.'		*/

	int		mappednewline;	/* inverse mapped '\n'		*/

	int		mappedslash;	/* inverse mapped '/'		*/

	regflags_t	flags;		/* flags arg to regcomp		*/

	int		type;		/* BRE,ERE,ARE,SRE,KRE		*/

	unsigned char*	cursor;		/* curent point in re		*/

	unsigned char*	pattern;	/* the original pattern		*/

	unsigned char*	literal;	/* literal restart pattern	*/

	int		parno;		/* number of last open paren	*/

	int		parnest;	/* paren nest count		*/

	int		posixkludge; 	/* to make * nonspecial		*/

	Token_t		token;		/* token lookahead		*/

	Stats_t		stats;		/* RE statistics		*/

	int		terminator;	/* pattern terminator		*/

	Rex_t*		paren[2*(BACK_REF_MAX+2)];

					/* paren[i]!=0 if \i defined	*/

	regex_t*	regex;		/* user handle			*/

	regdisc_t*	disc;		/* user discipline		*/

	unsigned char*	map;		/* external to native ccode map	*/

	unsigned char*	MAP;		/* fold and/or map		*/

} Cenv_t;

/*

 * allocate a new Rex_t node

 */

#if _BLD_DEBUG

#define node(a,b,c,d,e)	node(a,b,c,d,e, const char* file, unsigned int line)

#endif

static Rex_t*

node(Cenv_t* env, int type, int lo, int hi, size_t extra)

{

	register Rex_t*	e;

	DEBUG_TEST(0x0800,(sfprintf(sfstdout, "%s:%d node(%d,%d,%d,%u)\n", file, line, type, lo, hi, sizeof(Rex_t) + extra)),(0));

	if (e = (Rex_t*)alloc(env->disc, 0, sizeof(Rex_t) + extra))

	{

		memset(e, 0, sizeof(Rex_t) + extra);

		e->type = type;

		e->marked = 0;

		e->lo = lo;

		e->hi = hi;

		e->flags = env->flags;

		e->map = (e->flags & REG_ICASE) ? env->MAP : env->map;

		e->explicit = env->explicit;

		if (extra)

			e->re.data = (char*)e + sizeof(Rex_t);

	}

	return e;

}

#if _BLD_DEBUG

#undef	node

#define node(a,b,c,d,e)	node(a,b,c,d,e,__FILE__,__LINE__)

#endif

/*

 * free a Trie_node_t node

 */

static void

triedrop(regdisc_t* disc, Trie_node_t* e)

{

	if (e)

	{

		triedrop(disc, e->son);

		triedrop(disc, e->sib);

		alloc(disc, e, 0);

	}

}

/*

 * free a Rex_t node

 */

void

drop(regdisc_t* disc, Rex_t* e)

{

	int	i;

	Rex_t*	x;

	if (e && !(disc->re_flags & REG_NOFREE))

		do

		{

			switch (e->type)

			{

			case REX_ALT:

			case REX_CONJ:

				drop(disc, e->re.group.expr.binary.left);

				drop(disc, e->re.group.expr.binary.right);

				break;

			case REX_GROUP:

			case REX_GROUP_AHEAD:

			case REX_GROUP_AHEAD_NOT:

			case REX_GROUP_BEHIND:

			case REX_GROUP_BEHIND_NOT:

			case REX_GROUP_CUT:

			case REX_NEG:

			case REX_REP:

				drop(disc, e->re.group.expr.rex);

				break;

			case REX_TRIE:

				for (i = 0; i <= UCHAR_MAX; i++)

					triedrop(disc, e->re.trie.root[i]);

				break;

			}

			x = e->next;

			alloc(disc, e, 0);

		} while (e = x);

}

/*

 * mark e and descendants minimal

 */

static void

mark(register Rex_t* e, int set)

{

	if (e && !e->marked)

		do

		{

			e->marked = 1;

			if (set)

				e->flags |= REG_MINIMAL;

			else

				e->flags &= ~REG_MINIMAL;

			switch (e->type)

			{

			case REX_ALT:

			case REX_CONJ:

			case REX_GROUP_COND:

				if (e->re.group.expr.binary.left)

					mark(e->re.group.expr.binary.left, set);

				if (e->re.group.expr.binary.right)

					mark(e->re.group.expr.binary.right, set);

				break;

			case REX_GROUP:

			case REX_GROUP_AHEAD:

			case REX_GROUP_AHEAD_NOT:

			case REX_GROUP_BEHIND:

			case REX_GROUP_BEHIND_NOT:

			case REX_GROUP_CUT:

			case REX_NEG:

			case REX_REP:

			case REX_TRIE:

				mark(e->re.group.expr.rex, set);

				break;

			}

		} while (e = e->next);

}

/*

 * assign subexpression numbers by a preorder tree walk

 */

static int

serialize(Cenv_t* env, Rex_t* e, int n)

{

	do

	{

		e->serial = n++;

		switch (e->type)

		{

		case REX_ALT:

		case REX_GROUP_COND:

			if (e->re.group.expr.binary.left)

				n = serialize(env, e->re.group.expr.binary.left, n);

			e->re.group.expr.binary.serial = n++;

			if (e->re.group.expr.binary.right)

				n = serialize(env, e->re.group.expr.binary.right, n);

			break;

		case REX_CONJ:

			n = serialize(env, e->re.group.expr.binary.left, n);

			n = serialize(env, e->re.group.expr.binary.right, n);

			break;

		case REX_GROUP:

		case REX_GROUP_AHEAD:

		case REX_GROUP_AHEAD_NOT:

		case REX_GROUP_BEHIND:

		case REX_GROUP_BEHIND_NOT:

		case REX_GROUP_CUT:

		case REX_NEG:

		case REX_REP:

			n = serialize(env, e->re.group.expr.rex, n);

			break;

		}

	} while (e = e->next);

	return n;

}

/*

 * catenate e and f into a sequence, collapsing them if possible

 */

static Rex_t*

cat(Cenv_t* env, Rex_t* e, Rex_t* f)

{

	Rex_t*	g;

	if (!f)

	{

		drop(env->disc, e);

		return 0;

	}

	if (e->type == REX_NULL)

	{

		drop(env->disc, e);

		return f;

	}

	if (f->type == REX_NULL)

	{

		g = f->next;

		f->next = 0;

		drop(env->disc, f);

		f = g;

	}

	else if (e->type == REX_DOT && f->type == REX_DOT)

	{

		unsigned int	m = e->lo + f->lo;

		unsigned int	n = e->hi + f->hi;

		if (m <= RE_DUP_MAX)

		{

			if (e->hi > RE_DUP_MAX || f->hi > RE_DUP_MAX)

			{

				n = RE_DUP_INF;	

				goto combine;

			}

			else if (n <= RE_DUP_MAX)

			{

			combine:

				e->lo = m;

				e->hi = n;

				g = f->next;

				f->next = 0;

				drop(env->disc, f);

				f = g;

			}

		}

	}

	e->next = f;

	return e;

}

/*

 * collect re statistics

 */

static int

stats(register Cenv_t* env, register Rex_t* e)

{

	register unsigned long	n;

	register unsigned long	m;

	unsigned long		cm;

	unsigned long		nm;

	unsigned long		cn;

	unsigned long		nn;

	unsigned long		l;

	unsigned long		k;

	unsigned long		t;

	Rex_t*			q;

	Rex_t*			x;

	Rex_t*			y;

	unsigned char		c;

	unsigned char		b;

	do

	{

		switch (e->type)

		{

		case REX_ALT:

			x = env->stats.x;

			l = env->stats.l;

			y = env->stats.y;

			k = env->stats.k;

			t = env->stats.t;

			if (++env->stats.a <= 0)

				return 1;

			cm = env->stats.m;

			env->stats.m = 0;

			cn = env->stats.n;

			env->stats.n = 0;

			if (stats(env, e->re.group.expr.binary.left))

				return 1;

			m = env->stats.m;

			env->stats.m = 0;

			n = env->stats.n;

			env->stats.n = 0;

			if (e->re.group.expr.binary.right && stats(env, e->re.group.expr.binary.right))

				return 1;

			if (env->stats.m > m)

				env->stats.m = m;

			else

				m = env->stats.m;

			if ((env->stats.m += cm) < m)

				return 1;

			if (env->stats.n < n)

				env->stats.n = n;

			else

				n = env->stats.n;

			if ((env->stats.n += cn) < n)

				return 1;

			env->stats.x = x;

			env->stats.l = l;

			env->stats.y = y;

			env->stats.k = k;

			env->stats.t = t;

			break;

		case REX_BACK:

			if (++env->stats.b <= 0)

				return 1;

			break;

		case REX_CLASS:

		case REX_COLL_CLASS:

		case REX_DOT:

		case REX_ONECHAR:

			n = env->stats.m;

			if ((env->stats.m += e->lo) < n)

				return 1;

			if (e->hi != RE_DUP_INF)

			{

				n = env->stats.n;

				if ((env->stats.n += e->hi) < n)

					return 1;

			}

			if (e->lo != e->hi)

			{

				if (++env->stats.c <= 0)

					return 1;

				if (++env->stats.s <= 0)

					return 1;

			}

			break;

		case REX_CONJ:

			cm = env->stats.m;

			env->stats.m = 0;

			cn = env->stats.n;

			env->stats.n = 0;

			if (stats(env, e->re.group.expr.binary.left))

				return 1;

			nm = env->stats.m;

			env->stats.m = 0;

			nn = env->stats.n;

			env->stats.n = 0;

			if (stats(env, e->re.group.expr.binary.right))

				return 1;

			if (env->stats.m < nm)

				env->stats.m = nm;

			else

				nm = env->stats.m;

			if ((env->stats.m += cm) < nm)

				return 1;

			if (env->stats.n < nn)

				env->stats.n = nn;

			else

				nn = env->stats.n;

			if ((env->stats.n += cn) < nn)

				return 1;

			break;

		case REX_END:

			env->stats.e = 1;

			break;

		case REX_GROUP:

			if (e->re.group.number && ++env->stats.p <= 0 || !e->re.group.number && ++env->stats.u <= 0)

				return 1;

			if (stats(env, e->re.group.expr.rex))

				return 1;

			break;

		case REX_GROUP_AHEAD:

		case REX_GROUP_AHEAD_NOT:

		case REX_GROUP_BEHIND:

		case REX_GROUP_BEHIND_NOT:

			m = env->stats.m;

			n = env->stats.n;

			x = env->stats.x;

			y = env->stats.y;

			if (stats(env, e->re.group.expr.rex))

				return 1;

			env->stats.m = m;

			env->stats.n = n;

			env->stats.x = x;

			env->stats.y = y;

			switch (e->type)

			{

			case REX_GROUP_AHEAD:

			case REX_GROUP_BEHIND:

				if (++env->stats.u <= 0)

					return 1;

				break;

			}

			break;

		case REX_GROUP_COND:

			if (++env->stats.u <= 0)

				return 1;

			m = env->stats.m;

			n = env->stats.n;

			x = env->stats.x;

			y = env->stats.y;

			if (e->re.group.size > 0 && ++env->stats.b <= 0)

				return 1;

			if (e->re.group.expr.binary.left && stats(env, e->re.group.expr.binary.left))

				return 1;

			if (q = e->re.group.expr.binary.right)

			{

				if (q->re.group.expr.binary.left && stats(env, q->re.group.expr.binary.left))

					return 1;

				if (q->re.group.expr.binary.right && stats(env, q->re.group.expr.binary.right))

					return 1;

			}

			env->stats.m = m;

			env->stats.n = n;

			env->stats.x = x;

			env->stats.y = y;

			break;

		case REX_GROUP_CUT:

			if (++env->stats.u <= 0)

				return 1;

			m = env->stats.m;

			n = env->stats.n;

			x = env->stats.x;

			y = env->stats.y;

			if (stats(env, e->re.group.expr.rex))

				return 1;

			env->stats.m = m;

			env->stats.n = n;

			env->stats.x = x;

			env->stats.y = y;

			break;

		case REX_NEG:

			env->stats.i++;

			x = env->stats.x;

			l = env->stats.l;

			y = env->stats.y;

			k = env->stats.k;

			t = env->stats.t;

			cm = env->stats.m;

			env->stats.m = 0;

			if (stats(env, e->re.group.expr.rex))

				return 1;

			env->stats.m = !env->stats.m;

			if ((env->stats.m += cm) < cm)

				return 1;

			env->stats.x = x;

			env->stats.l = l;

			env->stats.y = y;

			env->stats.k = k;

			env->stats.t = t;

			break;

		case REX_REP:

			x = env->stats.x;

			l = env->stats.l;

			y = env->stats.y;

			k = env->stats.k;

			t = env->stats.t;

			if (++env->stats.c <= 0)

				return 1;

			b = env->stats.b;

			c = env->stats.c;

			cm = env->stats.m;

			env->stats.m = 0;

			if (stats(env, e->re.group.expr.rex))

				return 1;

			if (env->stats.m == 1 && b == env->stats.b && c == env->stats.c && ++env->stats.s <= 0)

				return 1;

			if (e->lo < 1)

			{

				env->stats.x = x;

				env->stats.l = l;

				env->stats.y = y;

				env->stats.k = k;

				env->stats.t = t;

				env->stats.m = cm;

			}

			else

			{

				m = env->stats.m;

				if ((env->stats.m *= e->lo) > 0 && env->stats.m < m)

					return 1;

				m = env->stats.m;

				if ((env->stats.m += cm) < m)

					return 1;

				if (env->stats.x != x)

					env->stats.l = cm;

				if (env->stats.y != y)

					env->stats.k = cm;

			}

			break;

		case REX_STRING:

			if (!e->map)

			{

				cm = env->stats.m;

				if ((env->stats.m += e->re.string.size) < cm)

					return 1;

				cn = env->stats.n;

				if ((env->stats.n += e->re.string.size) < cn)

					return 1;

				if (!env->stats.x || env->stats.x->re.string.size < e->re.string.size)

				{

					env->stats.x = e;

					env->stats.l = cm;

				}

			}

			break;

		case REX_TRIE:

			if (++env->stats.s <= 0)

				return 1;

			cm = env->stats.m;

			if ((env->stats.m += e->re.trie.min) < cm)

				return 1;

			cn = env->stats.n;

			if ((env->stats.n += e->re.trie.max) < cn)

				return 1;

			env->stats.t++;

			if (!env->stats.y || env->stats.y->re.trie.min < e->re.trie.min)

			{

				env->stats.y = e;

				env->stats.k = cm;

			}

			break;

		}

	} while (e = e->next);

	return 0;

}

static int	token(Cenv_t*);

static int

magic(register Cenv_t* env, register int c, int escaped)

{

	register char*	sp;

	register int	n;

	int		o = c;

	int		e = env->error;

	int		l = env->token.len;

	short*		mp;

	char*		ep;

	if (mp = state.magic[c])

	{

		c = mp[env->type+escaped];

		if (c >= T_META)

		{

			sp = (char*)env->cursor + env->token.len;

			switch (c)

			{

			case T_LEFT:

				n = 0;

				ep = sp;

				while (*sp >= '0' && *sp <= '9')

				{

					if (n > (INT_MAX / 10))

					{

						env->error = REG_BADBR;

						goto bad;

					}

					n = n * 10 + *sp++ - '0';

				}

				if (sp == ep)

				{

					if (env->type < SRE || *sp != ',')

					{

						env->error = *sp ? REG_BADBR : REG_EBRACE;

						goto bad;

					}

				}

				else if (n > RE_DUP_MAX)

				{

					env->error = REG_BADBR;

					goto bad;

				}

				env->token.min = n;

				if (*sp == ',')

				{

					n = 0;

					ep = ++sp;

					while (*sp >= '0' && *sp <= '9')

					{

						if (n > (INT_MAX / 10))

						{

							env->error = REG_BADBR;

							goto bad;

						}

						n = n * 10 + *sp++ - '0';

					}

					if (sp == ep)

						n = RE_DUP_INF;

					else if (n < env->token.min)

					{

						env->error = REG_BADBR;

						goto bad;

					}

				}

				env->token.max = n;

				switch (*sp)

				{

				case 0:

					env->error = REG_EBRACE;

					goto bad;

				case '\\':

					if (!escaped)

					{

						env->error = REG_BADBR;

						goto bad;

					}

					sp++;

					break;

				default:

					if (escaped)

					{

						env->error = REG_BADBR;

						goto bad;

					}

					break;

				}

				switch (*sp++)

				{

				case 0:

					env->error = REG_EBRACE;

					goto bad;

				case '}':

					break;

				default:

					env->error = REG_BADBR;

					goto bad;

				}

				env->token.len = sp - (char*)env->cursor;

				break;

			case T_RIGHT:

				env->error = REG_EBRACE;

				goto bad;

			case T_OPEN:

				if (env->type < SRE && *sp == '?')

				{

					env->token.len++;

					env->token.lex = 0;

					goto group;

				}

				break;

			case T_ESCAPE:

				c = chresc(sp - 2, &ep);

				if (ep < sp)

					goto bad;

				env->token.len += ep - sp;

				if (c >= T_META)

				{

					env->token.lex = c;

					c = C_ESC;

				}

				return c;

			case T_BACK+0:

			case T_BACK+1:

			case T_BACK+2:

			case T_BACK+3:

			case T_BACK+4:

			case T_BACK+5:

			case T_BACK+6:

			case T_BACK+7:

				n = chresc(sp - 2, &ep);

				if (ep > sp + 1)

				{

					env->token.len += ep - sp;

					return n;

				}

				/*FALLTHROUGH*/

			case T_BACK+8:

			case T_BACK+9:

				if (env->type == SRE || c == T_BACK && !(env->flags & (REG_LENIENT|REG_REGEXP)))

				{

					env->error = REG_BADESC;

					goto bad;

				}

				if ((env->flags & REG_MULTIREF) && isdigit(*sp))

				{

					c = (c - T_BACK) * 10 + (*sp - '0');

					if (c > 0 && c <= env->parno && env->paren[c])

						c += T_BACK;

					else

						c = chresc(sp - 2, &ep);

					env->token.len++;

				}

				if (c == T_BACK)

					c = 0;

				break;

			case T_BAD:

				if (escaped == 1 && (env->flags & (REG_LENIENT|REG_REGEXP)) && (c = mp[env->type+escaped+2]) >= T_META)

					return c;

				goto bad;

			}

			if (env->type >= SRE)

			{

				if (c == T_DOT)

					c = '.';

				else if (c < T_OPEN)

				{

					if (env->type == KRE && *(env->cursor + env->token.len) == '-' && *(env->cursor + env->token.len + 1) == '(')

					{

						env->token.len++;

						env->token.att = 1;

					}

					if (env->type == KRE && *(env->cursor + env->token.len) == '(')

					{

						env->token.len++;

						switch (c)

						{

						case T_AT:

							break;

						case T_PERCENT:

							env->token.lex = c;

							goto group;

						case T_TILDE:

							env->token.lex = 0;

							goto group;

						default:

							env->token.lex = c;

							break;

						}

						c = T_OPEN;

					}

					else if (c == T_STAR)

						c = T_DOTSTAR;

					else if (c == T_QUES)

						c = T_DOT;

					else

					{

						c = o;

						env->token.len = l;

					}

				}

				else if (c > T_BACK)

				{

					c = (c - T_BACK) * 2 - 1;

					c = (c > env->parno || !env->paren[c]) ? o : T_BACK + c;

				}

				else if (env->type == KRE && !env->parnest && (env->flags & REG_SHELL_GROUP))

				{

					if (c == T_AND)

						c = '&';

					else if (c == T_BAR)

						c = '|';

					else if (c == T_OPEN)

						c = '(';

				}

			}

		}

	}

	else if (escaped == 2)

	{

		if (env->type >= SRE && !(env->flags & REG_SHELL_ESCAPED) || (env->flags & REG_ESCAPE) && (c == '[' || c == '-' || c == ']' || env->delimiter && c == env->delimiter))

			/*ok*/;

		else

		{

			env->error = REG_BADESC;

			goto bad;

		}

	}

	else if (escaped && !(env->flags & (REG_LENIENT|REG_REGEXP)) && c != ']')

	{

		env->error = REG_BADESC;

		goto bad;

	}

	return c;

 group:

	sp = (char*)env->cursor + env->token.len;

	switch (*sp++)

	{