/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved	*/

/*
 * routines to do regular expression matching
 *
 * Entry points:
 *
 *	re_comp(s)
 *		char *s;
 *	 ... returns 0 if the string s was compiled successfully,
 *		     a pointer to an error message otherwise.
 *	     If passed 0 or a null string returns without changing
 *           the currently compiled re (see note 11 below).
 *
 *	re_exec(s)
 *		char *s;
 *	 ... returns 1 if the string s matches the last compiled regular
 *		       expression,
 *		     0 if the string s failed to match the last compiled
 *		       regular expression, and
 *		    -1 if the compiled regular expression was invalid
 *		       (indicating an internal error).
 *
 * The strings passed to both re_comp and re_exec may have trailing or
 * embedded newline characters; they are terminated by nulls.
 *
 * The identity of the author of these routines is lost in antiquity;
 * this is essentially the same as the re code in the original V6 ed.
 *
 * The regular expressions recognized are described below. This description
 * is essentially the same as that for ed.
 *
 *	A regular expression specifies a set of strings of characters.
 *	A member of this set of strings is said to be matched by
 *	the regular expression.  In the following specification for
 *	regular expressions the word `character' means any character but NUL.
 *
 *	1.  Any character except a special character matches itself.
 *	    Special characters are the regular expression delimiter plus
 *	    \ [ . and sometimes ^ * $.
 *	2.  A . matches any character.
 *	3.  A \ followed by any character except a digit or ( )
 *	    matches that character.
 *	4.  A nonempty string s bracketed [s] (or [^s]) matches any
 *	    character in (or not in) s. In s, \ has no special meaning,
 *	    and ] may only appear as the first letter. A substring
 *	    a-b, with a and b in ascending ASCII order, stands for
 *	    the inclusive range of ASCII characters.
 *	5.  A regular expression of form 1-4 followed by * matches a
 *	    sequence of 0 or more matches of the regular expression.
 *	6.  A regular expression, x, of form 1-8, bracketed \(x\)
 *	    matches what x matches.
 *	7.  A \ followed by a digit n matches a copy of the string that the
 *	    bracketed regular expression beginning with the nth \( matched.
 *	8.  A regular expression of form 1-8, x, followed by a regular
 *	    expression of form 1-7, y matches a match for x followed by
 *	    a match for y, with the x match being as long as possible
 *	    while still permitting a y match.
 *	9.  A regular expression of form 1-8 preceded by ^ (or followed
 *	    by $), is constrained to matches that begin at the left
 *	    (or end at the right) end of a line.
 *	10. A regular expression of form 1-9 picks out the longest among
 *	    the leftmost matches in a line.
 *	11. An empty regular expression stands for a copy of the last
 *	    regular expression encountered.
 */

#include "lint.h"

#include <stdlib.h>
#include <re_comp.h>
#include <stddef.h>
#include <sys/types.h>

/*
 * constants for re's
 */
#define	CBRA	1
#define	CCHR	2
#define	CDOT	4
#define	CCL	6
#define	NCCL	8
#define	CDOL	10
#define	CEOF	11
#define	CKET	12
#define	CBACK	18

#define	CSTAR	01

#define	ESIZE	512
#define	NBRA	9

static struct re_globals {
	char	_expbuf[ESIZE];
	char	*_braslist[NBRA], *_braelist[NBRA];
	char	_circf;
} *re_globals;
#define	expbuf (_re->_expbuf)
#define	braslist (_re->_braslist)
#define	braelist (_re->_braelist)
#define	circf (_re->_circf)

static int advance(const char *, char *);
static int backref(int, const char *);
static int cclass(char *, char, int);

/*
 * compile the regular expression argument into a dfa
 */
char *
re_comp(const char *sp)
{
	char	c;
	struct re_globals *_re = re_globals;
	char	*ep;
	char	cclcnt, numbra = 0;
	char	*lastep = NULL;
	char	bracket[NBRA];
	char	*bracketp = &bracket[0];
	char	*retoolong = "Regular expression too long";

	if (_re == NULL) {
		_re = (struct re_globals *)calloc(1, sizeof (*_re));
		if (_re == NULL)
			return ("Out of memory");
		re_globals = _re;
	}
	ep = expbuf;

#define	comerr(msg) {expbuf[0] = 0; return (msg); }

	if (sp == NULL || *sp == '\0') {
		if (*ep == 0)
			return ("No previous regular expression");
		return (NULL);
	}
	if (*sp == '^') {
		circf = 1;
		sp++;
	}
	else
		circf = 0;
	for (;;) {
		if (ep >= &expbuf[ESIZE])
			comerr(retoolong);
		if ((c = *sp++) == '\0') {
			if (bracketp != bracket)
				comerr("unmatched \\(");
			*ep++ = CEOF;
			*ep++ = 0;
			return (NULL);
		}
		if (c != '*')
			lastep = ep;
		switch (c) {

		case '.':
			*ep++ = CDOT;
			continue;

		case '*':
			if (lastep == NULL || *lastep == CBRA ||
			    *lastep == CKET)
				goto defchar;
			*lastep |= CSTAR;
			continue;

		case '$':
			if (*sp != '\0')
				goto defchar;
			*ep++ = CDOL;
			continue;

		case '[':
			*ep++ = CCL;
			*ep++ = 0;
			cclcnt = 1;
			if ((c = *sp++) == '^') {
				c = *sp++;
				ep[-2] = NCCL;
			}
			do {
				if (c == '\0')
					comerr("missing ]");
				if (c == '-' && ep [-1] != 0) {
					if ((c = *sp++) == ']') {
						*ep++ = '-';
						cclcnt++;
						break;
					}
					while (ep[-1] < c) {
						*ep = ep[-1] + 1;
						ep++;
						cclcnt++;
						if (ep >= &expbuf[ESIZE])
							comerr(retoolong);
					}
				}
				*ep++ = c;
				cclcnt++;
				if (ep >= &expbuf[ESIZE])
					comerr(retoolong);
			} while ((c = *sp++) != ']');
			lastep[1] = cclcnt;
			continue;

		case '\\':
			if ((c = *sp++) == '(') {
				if (numbra >= NBRA)
					comerr("too many \\(\\) pairs");
				*bracketp++ = numbra;
				*ep++ = CBRA;
				*ep++ = numbra++;
				continue;
			}
			if (c == ')') {
				if (bracketp <= bracket)
					comerr("unmatched \\)");
				*ep++ = CKET;
				*ep++ = *--bracketp;
				continue;
			}
			if (c >= '1' && c < ('1' + NBRA)) {
				*ep++ = CBACK;
				*ep++ = c - '1';
				continue;
			}
			*ep++ = CCHR;
			*ep++ = c;
			continue;

		defchar:
		default:
			*ep++ = CCHR;
			*ep++ = c;
		}
	}
}

/*
 * match the argument string against the compiled re
 */
int
re_exec(const char *p1)
{
	struct re_globals *_re = re_globals;
	char	*p2;
	int	c;
	int	rv;

	if (_re == NULL)
		return (0);
	p2 = expbuf;
	for (c = 0; c < NBRA; c++) {
		braslist[c] = 0;
		braelist[c] = 0;
	}
	if (circf)
		return ((advance(p1, p2)));
	/*
	 * fast check for first character
	 */
	if (*p2 == CCHR) {
		c = p2[1];
		do {
			if (*p1 != c)
				continue;
			rv = advance(p1, p2);
			if (rv != 0)
				return (rv);
		} while (*p1++);
		return (0);
	}
	/*
	 * regular algorithm
	 */
	do {
		rv = advance(p1, p2);
		if (rv != 0)
			return (rv);
	} while (*p1++);
	return (0);
}

/*
 * try to match the next thing in the dfa
 */
static int
advance(const char *lp, char *ep)
{
	const char	*curlp;
	ptrdiff_t	ct;
	int		i;
	int		rv;
	struct re_globals *_re = re_globals;

	for (;;)
		switch (*ep++) {

		case CCHR:
			if (*ep++ == *lp++)
				continue;
			return (0);

		case CDOT:
			if (*lp++)
				continue;
			return (0);

		case CDOL:
			if (*lp == '\0')
				continue;
			return (0);

		case CEOF:
			return (1);

		case CCL:
			if (cclass(ep, *lp++, 1)) {
				ep += *ep;
				continue;
			}
			return (0);

		case NCCL:
			if (cclass(ep, *lp++, 0)) {
				ep += *ep;
				continue;
			}
			return (0);

		case CBRA:
			braslist[*ep++] = (char *)lp;
			continue;

		case CKET:
			braelist[*ep++] = (char *)lp;
			continue;

		case CBACK:
			if (braelist[i = *ep++] == NULL)
				return (-1);
			if (backref(i, lp)) {
				lp += braelist[i] - braslist[i];
				continue;
			}
			return (0);

		case CBACK|CSTAR:
			if (braelist[i = *ep++] == NULL)
				return (-1);
			curlp = lp;
			ct = braelist[i] - braslist[i];
			while (backref(i, lp))
				lp += ct;
			while (lp >= curlp) {
				rv = advance(lp, ep);
				if (rv != 0)
					return (rv);
				lp -= ct;
			}
			continue;

		case CDOT|CSTAR:
			curlp = lp;
			while (*lp++)
				;
			goto star;

		case CCHR|CSTAR:
			curlp = lp;
			while (*lp++ == *ep)
				;
			ep++;
			goto star;

		case CCL|CSTAR:
		case NCCL|CSTAR:
			curlp = lp;
			while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
				;
			ep += *ep;
			goto star;

		star:
			do {
				lp--;
				rv = advance(lp, ep);
				if (rv != 0)
					return (rv);
			} while (lp > curlp);
			return (0);

		default:
			return (-1);
		}
}

static int
backref(int i, const char *lp)
{
	char	*bp;
	struct re_globals *_re = re_globals;

	bp = braslist[i];
	while (*bp++ == *lp++)
		if (bp >= braelist[i])
			return (1);
	return (0);
}

static int
cclass(char *set, char c, int af)
{
	int	n;

	if (c == 0)
		return (0);
	n = *set++;
	while (--n)
		if (*set++ == c)
			return (af);
	return (! af);
}