regcomp.c

/***************************************************************
*                                                              *
*           This software is part of the ast package           *
*              Copyright (c) 1985-2000 AT&T Corp.              *
*      and it may only be used by you under license from       *
*                     AT&T Corp. ("AT&T")                      *
*       A copy of the Source Code Agreement is available       *
*              at the AT&T Internet web site URL               *
*                                                              *
*     http://www.research.att.com/sw/license/ast-open.html     *
*                                                              *
*     If you received this software without first entering     *
*       into a license with AT&T, you have an infringing       *
*           copy and cannot use it without violating           *
*             AT&T's intellectual property rights.             *
*                                                              *
*               This software was created by the               *
*               Network Services Research Center               *
*                      AT&T Labs 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"

#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
{
	unsigned long	l;	/* min length to left of x		*/
	unsigned long	k;	/* min length to left of y		*/
	unsigned long	m;	/* min length				*/
	unsigned int	a;	/* number of alternations		*/
	unsigned short	b;	/* number of backrefs			*/
	unsigned short	c;	/* number of closures			*/
	unsigned short	p;	/* number of parens (subexpressions)	*/
	unsigned short	s;	/* number of simple closures		*/
	unsigned short	t;	/* number of tries			*/
	Rex_t*		x;	/* max length REX_STRING		*/
	Rex_t*		y;	/* max length REX_TRIE			*/
} Stats_t;

typedef struct
{
	unsigned long	min;
	unsigned long	max;
	short		lex;
	short		len;
	short		push;
} Token_t;

typedef struct
{
	int		delimiter;	/* pattern delimiter		*/
	int		error;		/* last error			*/
	int		explicit;	/* explicit match on this char	*/
	int		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*	map;		/* for REG_ICASE		*/
	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		*/
	unsigned char	paren[2*(BACK_REF_MAX+2)];
					/* paren[i]==1 if \i defined	*/
} Cenv_t;

/*
 * allocate a new Rex_t node
 */

static Rex_t*
node(int type, int lo, int hi, size_t extra)
{
	register Rex_t*	e;

	if (e = (Rex_t*)alloc(0, sizeof(Rex_t) + extra))
	{
		memset(e, 0, sizeof(Rex_t) + extra);
		e->type = type;
		e->lo = lo;
		e->hi = hi;
		if (extra)
			e->re.data = (char*)e + sizeof(Rex_t);
	}
	return e;
}

/*
 * free a Trie_node_t node
 */

static void
triedrop(Trie_node_t* e)
{
	if (e)
	{
		triedrop(e->son);
		triedrop(e->sib);
		alloc(e, 0);
	}
}

/*
 * free a Rex_t node
 */

void
drop(Rex_t* e)
{
	int	i;
	Rex_t*	x;

	if (e && !state.nofree)
		do
		{
			switch (e->type)
			{
			case REX_ALT:
			case REX_CONJ:
				drop(e->re.group.expr.binary.left);
				drop(e->re.group.expr.binary.right);
				break;
			case REX_GROUP:
			case REX_NEG:
			case REX_REP:
				drop(e->re.group.expr.rex);
				break;
			case REX_TRIE:
				for (i = 0; i <= UCHAR_MAX; i++)
					triedrop(e->re.trie.root[i]);
				break;
			}
			x = e->next;
			alloc(e, 0);
		} while (e = x);
}

/*
 * assign subexpression numbers by a preorder tree walk
 */

static int
serialize(Rex_t* e, int n)
{
	do
	{
		e->serial = n++;
		switch (e->type)
		{
		case REX_ALT:
			n = serialize(e->re.group.expr.binary.left, n);
			e->re.group.expr.binary.serial = n++;
			n = serialize(e->re.group.expr.binary.right, n);
			break;
		case REX_CONJ:
			n = serialize(e->re.group.expr.binary.left, n);
			n = serialize(e->re.group.expr.binary.right, n);
			break;
		case REX_GROUP:
		case REX_NEG:
		case REX_REP:
			n = serialize(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(Rex_t* e, Rex_t* f)
{
	Rex_t*	g;

	if (!f)
	{
		drop(e);
		return 0;
	}
	if (e->type == REX_NULL)
	{
		drop(e);
		return f;
	}
	if (f->type == REX_NULL)
	{
		g = f->next;
		f->next = 0;
		drop(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(f);
				f = g;
			}
		}
	}
	e->next = f;
	return e;
}


/*
 * collect re statistics
 */

static int
stats(register Cenv_t* env, register Rex_t* e)
{
	register unsigned int	n;
	register unsigned int	m;
	unsigned char		c;
	unsigned char		b;
	unsigned long		l;
	unsigned long		k;
	unsigned long		t;
	Rex_t*			x;
	Rex_t*			y;

	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;
			n = env->stats.m;
			env->stats.m = 0;
			if (stats(env, e->re.group.expr.binary.left))
				return 1;
			m = env->stats.m;
			env->stats.m = 0;
			if (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 += n) < m)
				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_DOT:
		case REX_ONECHAR:
			n = env->stats.m;
			if ((env->stats.m += e->lo) < 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:
			n = env->stats.m;
			env->stats.m = 0;
			if (stats(env, e->re.group.expr.binary.left))
				return 1;
			m = env->stats.m;
			env->stats.m = 0;
			if (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 += n) < m)
				return 1;
			break;
		case REX_GROUP:
			if (++env->stats.p <= 0)
				return 1;
			if (stats(env, e->re.group.expr.rex))
				return 1;
			break;
		case REX_NEG:
			x = env->stats.x;
			l = env->stats.l;
			y = env->stats.y;
			k = env->stats.k;
			t = env->stats.t;
			n = 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 += n) < 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_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;
			n = 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;
			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 += n) < m)
				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;
			}
			break;
		case REX_STRING:
			n = env->stats.m;
			if ((env->stats.m += e->re.string.size) < n)
				return 1;
			if (!env->stats.x || env->stats.x->re.string.size < e->re.string.size)
			{
				env->stats.x = e;
				env->stats.l = n;
			}
			break;
		case REX_TRIE:
			if (++env->stats.s <= 0)
				return 1;
			n = env->stats.m;
			if ((env->stats.m += e->re.trie.min) < n)
				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 = n;
			}
			break;
		}
	} while (e = e->next);
	return 0;
}

static int
magic(register Cenv_t* env, register int c, int escaped)
{
	int	o = c;
	short*	mp;

	if (mp = state.magic[c])
	{
		c = mp[env->type+escaped];
		if (c == T_LEFT)
		{
			char*	sp;
			char*	np;

			errno = 0;
			sp = (char*)env->cursor + env->token.len;
			env->token.min = env->token.max = strtoul(sp, &np, 10);
			if (!*np)
			{
				env->error = REG_EBRACE;
				goto bad;
			}
			if (np == sp)
			{
				env->error = REG_BADBR;
				goto bad;
			}
			sp = np;
			if (*sp == ',')
			{
				sp++;
				env->token.max = strtoul(sp, &np, 10);
				if (!*np)
				{
					env->error = REG_EBRACE;
					goto bad;
				}
				else if (np == sp)
					env->token.max = RE_DUP_INF;
				else if (env->token.max > RE_DUP_MAX)
				{
					env->error = REG_BADBR;
					goto bad;
				}
				sp = np;
			}
			if (errno  && env->token.max != RE_DUP_INF || env->token.min > env->token.max || env->token.min > RE_DUP_MAX)
			{
				env->error = REG_BADBR;
				goto bad;
			}
			if (*sp == '\\')
			{
				if (!escaped)
					goto bad;
				sp++;
			}
			else if (escaped)
			{
				env->error = REG_BADBR;
				goto bad;
			}
			if (*sp++ != '}')
			{
				env->error = REG_BADBR;
				goto bad;
			}
			env->token.len = sp - (char*)env->cursor;
		}
		else if (c == T_RIGHT)
		{
			env->error = REG_EBRACE;
			goto bad;
		}
		else if (c == T_BAD)
		{
			if (escaped && (env->flags & REG_LENIENT) && (c = mp[env->type+escaped+1]) >= T_META)
				return c;
			goto bad;
		}
		if (env->type >= SRE && c >= T_META)
		{
			if (c == T_DOT)
				c = '.';
			else if (c < T_OPEN)
			{
				if (env->type == KRE && *(env->cursor + env->token.len) == '(')
				{
					env->token.len++;
					if (c != T_AT)
						env->token.lex = c;
					c = T_OPEN;
				}
				else if (c == T_STAR)
					c = T_DOTSTAR;
				else if (c == T_QUES)
					c = T_DOT;
				else if (c == T_PLUS)
					c = '+';
				else if (c == T_BANG)
					c = '!';
			}
			else if (c > T_BACK)
			{
				c = (c - T_BACK) * 2 - 1;
				c = (c > env->parno || !env->paren[c]) ? o : T_BACK + c;
			}
		}
	}
	else if (escaped && !(env->flags & REG_LENIENT) && !mp && o != ']')
	{
		env->error = REG_BADESC;
		goto bad;
	}
	return c;
 bad:
	if (env->flags & REG_LENIENT)
		return o;
	if (!env->error && escaped)
	{
		if (mp || o == ']')
			return o;
		env->error = REG_BADESC;
	}
	return T_BAD;
}

static int
token(register Cenv_t* env)
{
	int	c;

	if (env->token.push)
		return env->token.lex;
	env->token.lex = 0;
	env->token.len = 1;
	c = *env->cursor;
	if (c == 0 || env->delimiter && (c == env->delimiter || c == '\n'))
		return T_END;
	if (c == '\n' && (env->flags & REG_MULTIPLE) && !env->delimiter)
	{
		if (env->parnest)
		{
			env->error = REG_EPAREN;
			return T_BAD;
		}
		env->parno = 0;
		env->pattern = env->cursor + 1;
		return T_BAR;
	}
	if (env->flags & REG_LITERAL)
		return c;
	if (env->posixkludge)
	{
		env->posixkludge = 0;
		if (c == '*')
			return c;
	}
	if (c == '\\')
	{
		if (env->flags & REG_SHELL_ESCAPED)
			return c;
		if (!(c = *(env->cursor + 1)) || env->delimiter && c == '\n')
		{
			if (env->flags & REG_LENIENT)
				return '\\';
			env->error = REG_EESCAPE;
			return T_BAD;
		}
		env->token.len++;
		if (env->delimiter && c == 'n')
			return '\n';
		else if (c == env->delimiter)
			return magic(env, c, 0);
		else if (c == '(' && env->type == BRE)
			env->posixkludge = 1;
		else if (c == ')' && env->type == BRE && env->parnest <= 0)
		{
			env->error = REG_EPAREN;
			return T_BAD;
		}
		return magic(env, c, 1);
	}
	else if (c == '$')
	{
		if (env->type < SRE && (*(env->cursor + 1) == 0 || env->delimiter && (*(env->cursor + 1) == env->delimiter || *(env->cursor + 1) == '\n')) || (env->flags & REG_MULTIPLE) && *(env->cursor + 1) == '\n')
			return T_DOLL;
	}
	else if (c == '^')
	{
		if (env->type == BRE && env->cursor == env->pattern)
		{
			env->posixkludge = 1;
			return T_CFLX;
		}
	}
	else if (c == ')')
	{
		if (env->type != BRE && env->parnest <= 0)
			return c;
	}
	else if (c == '/' && env->explicit == '/')
	{
		while (*(env->cursor + env->token.len) == c)
			env->token.len++;
		return T_SLASHPLUS;
	}
	return magic(env, c, 0);
}

static Rex_t*
bra(Cenv_t* env)
{
	Rex_t*		e;
	int		c;
	int		i;
	int		neg;
	int		last;
	int		inrange;
	unsigned char*	start;
	unsigned char*	begin;
	regclass_t	f;

	if (!(e = node(REX_CLASS, 1, 1, sizeof(Set_t))))
		return 0;
	start = env->cursor + 1;
	if (*env->cursor == (env->type >= SRE ? '!' : '^'))
	{
		env->cursor++;
		neg = 1;
	}
	else neg = 0;
	if (*env->cursor == 0 || *(env->cursor + 1) == 0 || env->delimiter && (*env->cursor == '\n' || *(env->cursor + 1) == '\n' || (env->flags & REG_ESCAPE) && (*env->cursor == env->delimiter || *env->cursor != '\\' && *(env->cursor + 1) == env->delimiter)))
		goto error;
	begin = env->cursor + 1;

	/*
	 * 0=no, 1=possibly, 2=definitely
	 */

	inrange = 0;
	for (;;)
	{
		if (!(c = *env->cursor) || env->delimiter && (c == '\n' || (env->flags & REG_ESCAPE) && c == env->delimiter))
			goto error;
		env->cursor++;
		if (c == '\\')
		{
			if (*env->cursor)
			{
				if (env->delimiter && *env->cursor == 'n')
				{
					env->cursor++;
					c = '\n';
				}
				else if (env->type >= SRE && !(env->flags & REG_SHELL_ESCAPED) || env->delimiter && (env->flags & REG_ESCAPE) && *env->cursor == env->delimiter)
					c = *env->cursor++;
			}
		}
		else if (c == ']')
		{
			if (env->cursor == begin)
			{
				last = c;
				inrange = 1;
				continue;
			}
			if (inrange != 0)
			{
				setadd(e->re.charclass, last);
				if (inrange == 2)
					setadd(e->re.charclass, '-');
			}
			break;
		}
		else if (c == '-')
		{
			if (!inrange && env->cursor != begin && *env->cursor != ']')
			{
				if (env->type < SRE && !(env->flags & REG_LENIENT))
					goto erange;
				inrange = 1;
				continue;
			}
			else if (inrange == 1)
			{
				inrange = 2;
				continue;
			}
		}
		else if (c == '[')
		{
			switch (*env->cursor)
			{
			case 0:
				goto error;
			case ':':
				if (inrange == 1)
					setadd(e->re.charclass, last);
				if (!(f = regclass((char*)env->cursor, (char**)&env->cursor)))
				{
					if (env->cursor == start && (c = *(env->cursor + 1)) && *(env->cursor + 2) == ':' && *(env->cursor + 3) == ']' && *(env->cursor + 4) == ']')
					{
						switch (c)
						{
						case '<':
							i = REX_WBEG;
							break;
						case '>':
							i = REX_WEND;
							break;
						default:
							i = 0;
							break;
						}
						if (i)
						{
							env->cursor += 5;
							drop(e);
							return node(i, 0, 0, 0);
						}
					}
					env->error = REG_ECTYPE;
					goto error;
				}
				for (c = 0; c <= UCHAR_MAX; c++)
					if ((*f)(c))
						setadd(e->re.charclass, c);
				inrange = 0;
				continue;
			case '=':
				if (inrange == 2)
					goto erange;
				if (inrange == 1)
					setadd(e->re.charclass, last);
				if ((c = regcollate((char*)env->cursor, (char**)&env->cursor)) == -1)
				{
					env->error = REG_ECOLLATE;
					goto error;
				}
				setadd(e->re.charclass, c);
				inrange = 0;
				continue;
			case '.':
				if ((c = regcollate((char*)env->cursor, (char**)&env->cursor)) == -1)
				{
					env->error = REG_ECOLLATE;
					goto error;
				}
				break;
			case '\n':
				if (env->delimiter)
					goto error;
				/*FALLTHROUGH*/
			default:
				if (*env->cursor == env->delimiter && (env->flags & REG_ESCAPE))
					goto error;
				break;
			}
		}
		if (inrange == 2)
		{
			if (last > c)
			{
				if (env->type < SRE && !(env->flags & REG_LENIENT))
					goto erange;
				setadd(e->re.charclass, last);
				setadd(e->re.charclass, c);
			}
			else for (i = last; i <= c; i++)
				setadd(e->re.charclass, i);
			inrange = env->type >= SRE || (env->flags & REG_LENIENT);
		}
		else if (inrange == 1)
			setadd(e->re.charclass, last);
		else inrange = 1;
		last = c;
	}
	if (env->flags & REG_ICASE)
		for (i = 0; i <= UCHAR_MAX; i++)
			if (settst(e->re.charclass, i))
			{
				if (isupper(i))
					setadd(e->re.charclass, tolower(i));
				else setadd(e->re.charclass, toupper(i));
			}
	if (neg)
	{
		for (i = 0; i < elementsof(e->re.charclass->bits); i++)
			e->re.charclass->bits[i] ^= ~0;
		if (env->explicit)
			setclr(e->re.charclass, env->explicit);
	}
	return e;
 erange:
	env->error = REG_ERANGE;
 error:
	drop(e);
	if (!env->error)
		env->error = REG_EBRACK;
	return 0;
}

static Rex_t*
rep(Cenv_t* env, Rex_t* e, int number, int last)
{
	Rex_t*		f;
	unsigned long	m = 0;
	unsigned long	n = RE_DUP_INF;

	if (!e)
		return 0;
	switch (token(env))
	{
	case T_BANG:
		eat(env);
		if (!(f = node(REX_NEG, m, n, 0)))
		{
			drop(e);
			return 0;
		}
		f->re.group.expr.rex = e;
		return f;
	case T_QUES:
		eat(env);
		n = 1;
		break;
	case T_STAR:
		eat(env);
		break;
	case T_PLUS:
		eat(env);
		m = 1;
		break;
	case T_LEFT:
		eat(env);
		m = env->token.min;
		n = env->token.max;
		break;
	default:
		return e;
	}
	switch (e->type)
	{
	case REX_DOT:
	case REX_CLASS:
	case REX_ONECHAR:
		e->lo = m;
		e->hi = n;
		return e;
	}
	if (!(f = node(REX_REP, m, n, 0)))
	{
		drop(e);
		return 0;
	}
	f->re.group.expr.rex = e;
	f->re.group.number = number;
	f->re.group.last = last;
	return f;
}

static int
isstring(Rex_t* e)
{
	switch (e->type)
	{
	case REX_ONECHAR:
		return e->lo == 1 && e->hi == 1;
	case REX_STRING:
		return 1;
	}
	return 0;
}

static Trie_node_t*
trienode(int c)
{
	Trie_node_t*	t;

	if (t = (Trie_node_t*)alloc(0, sizeof(Trie_node_t)))
	{
		memset(t, 0, sizeof(Trie_node_t));
		t->c = c;
	}
	return t;
}

static int
insert(Rex_t* f, Rex_t* g)
{
	unsigned char*	s;
	Trie_node_t*	t;
	int		len;
	unsigned char	tmp[2];

	switch (f->type)
	{
	case REX_ONECHAR:
		s = tmp;
		s[0] = f->re.onechar;
		s[1] = 0;
		break;
	case REX_STRING:
		s = f->re.string.base;
		break;
	default:
		return 1;
	}
	if (!(t = g->re.trie.root[*s]) && !(t = g->re.trie.root[*s] = trienode(*s)))
		return 1;
	for (len = 1;;)
	{
		if (t->c == *s)
		{
			if (!*++s)
				break;
			if (!t->son && !(t->son = trienode(*s)))
				return 1;
			t = t->son;
			len++;
		}
		else
		{
			if (!t->sib && !(t->sib = trienode(*s)))
				return 1;
			t = t->sib;
		}
	}
	if (len < g->re.trie.min)
		g->re.trie.min = len;
	t->end = 1;
	return 0;
}

/*
 * trie() tries to combine nontrivial e and f into a REX_TRIE
 * unless 0 is returned, e and f are deleted as far as possible
 * also called by regcomb
 */

static Rex_t*
trie(Rex_t* e, Rex_t* f)
{
	Rex_t*	g;

	if (e->next || f->next || !isstring(e))
		return 0;
	if (isstring(f))
	{
		if (!(g = node(REX_TRIE, 0, 0, (UCHAR_MAX + 1) * sizeof(Trie_node_t*))))
			return 0;
		g->re.trie.min = INT_MAX;
		if (insert(f, g))
			goto nospace;
		drop(f);
	}
	else if (f->type != REX_TRIE)
		return 0;
	else g = f;
	if (insert(e, g))
		goto nospace;
	drop(e);
	return g;
 nospace:
	if (g != f)
		drop(g);
	return 0;
}

static Rex_t*		alt(Cenv_t*, int);

static Rex_t*
seq(Cenv_t* env)
{
	Rex_t*		e;
	Rex_t*		f;
	Token_t		tok;
	int		c;
	int		last;
	int		parno;
	unsigned char*	s;
	unsigned char	buf[256];

	for (;;)
	{
		for (s = buf; (c = token(env)) < T_META && s < &buf[sizeof(buf)-1]; last = c)
		{	
			*s++ = env->map[c];