Initial revision

8 files changed, 5621 insertions, 0 deletions

diff --git a/lisp/re/README b/lisp/re/README
new file mode 100644
index 0000000..848e1e9
--- /dev/null
+++ b/lisp/re/README
@@ -0,0 +1,121 @@
+$XFree86: xc/programs/xedit/lisp/re/README,v 1.4 2002/11/15 07:01:32 paulo Exp $
+
+LAST UPDATED:	$Date$
+
+  This is a small regex library for fast matching tokens in text. It was built
+to be used by xedit and it's syntax highlight code. It is not compliant with
+IEEE Std 1003.2, but is expected to be used where very fast matching is
+required, and exotic patterns will not be used.
+
+  To understand what kind of patterns this library is expected to be used with,
+see the file <XRoot>xc/programs/xedit/lisp/modules/progmodes/c.lsp and some
+samples in the file tests.txt, with comments for patterns that will not work,
+or may give incorrect results.
+
+  The library is not built upon the standard regex library by Henry Spencer,
+but is completely written from scratch, but it's syntax is heavily based on
+that library, and the only reason for it to exist is that unfortunately
+the standard version does not fit the requirements needed by xedit.
+Anyways, I would like to thanks Henry for his regex library, it is a really
+very useful tool.
+
+  Small description of understood tokens:
+
+		M A T C H I N G
+------------------------------------------------------------------------
+.		Any character (won't match newline if compiled with RE_NEWLINE)
+\w		Any word letter (shortcut to [a-zA-Z0-9_]
+\W		Not a word letter (shortcut to [^a-zA-Z0-9_]
+\d		Decimal number
+\D		Not a decimal number
+\s		A space
+\S		Not a space
+\l		A lower case letter
+\u		An upper case letter
+\c		A control character, currently the range 1-32 (minus tab)
+\C		Not a control character
+\o		Octal number
+\O		Not an octal number
+\x		Hexadecimal number
+\X		Not an hexadecimal number
+\<		Beginning of a word (matches an empty string)
+\>		End of a word (matches an empty string)
+^		Beginning of a line (matches an empty string)
+$		End of a line (matches an empty string)
+[...]		Matches one of the characters inside the brackets
+		ranges are specified separating two characters with "-".
+		If the first character is "^", matches only if the
+		character is not in this range. To add a "]" make it
+		the first character, and to add a "-" make it the last.
+\1 to \9	Backreference, matches the text that was matched by a group,
+		that is, text that was matched by the pattern inside
+		"(" and ")".
+
+
+		O P E R A T O R S
+------------------------------------------------------------------------
+()		Any pattern inside works as a backreference, and is also
+		used to group patterns.
+|		Alternation, allows choosing different possibilities, like
+		character ranges, but allows patterns of different lengths.
+
+
+		R E P E T I T I O N
+------------------------------------------------------------------------
+<re>*		<re> may occur any number of times, including zero
+<re>+		<re> must occur at least once
+<re>?		<re> is optional
+<re>{<e>}	<re> must occur exactly <e> times
+<re>{<n>,}	<re> must occur at least <n> times
+<re>{,<m>}	<re> must not occur more than <m> times
+<re>{<n>,<m>}	<re> must occur at least <n> times, but no more than <m>
+
+
+  Note that "." is a special character, and when used with a repetition
+operator it changes completely its meaning. For example, ".*" matches
+anything up to the end of the input string (unless the pattern was compiled
+with RE_NEWLINE, in that case it will match anything, but a newline).
+
+
+  Limitations:
+
+o Only minimal matches supported. The engine has only one level "backtracking",
+  so, it also only does minimal matches to allow backreferences working
+  properly, and to avoid failing to match depending on the input.
+
+o Only one level "grouping", for example, with the pattern:
+	(a(b)c)
+   If "abc" is anywhere in the input, it will be in "\1", but there will
+  not exist a "\2" for "b".
+
+o Some "special repetitions" were not implemented, these are:
+	.{<e>}
+	.{<n>,}
+	.{,<m>}
+	.{<n>,<m>}
+
+o Some patterns will never match, for example:
+	\w*\d
+    Since "\w*" already includes all possible matches of "\d", "\d" will
+  only be tested when "\w*" failed. There are no plans to make such
+  patterns work.
+
+
+  Some of these limitations may be worked on future versions of the library,
+but this is not what the library is expected to do, and, adding support for
+correct handling of these would probably make the library slower, what is
+not the reason of it to exist in the first time.
+
+  If you need "true" regex than this library is not for you, but if all
+you need is support for very quickly finding simple patterns, than this
+library can be a very powerful tool, on some patterns it can run more
+than 200 times faster than "true" regex implementations! And this is
+the reason it was written.
+
+
+
+  Send comments and code to me (paulo@XFree86.Org) or to the XFree86
+mailing/patch lists.
+
+--
+Paulo
diff --git a/lisp/re/re.c b/lisp/re/re.c
new file mode 100644
index 0000000..d848a4b
--- /dev/null
+++ b/lisp/re/re.c
@@ -0,0 +1,2648 @@
+/*
+ * Copyright (c) 2002 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ *
+ * Author: Paulo César Pereira de Andrade
+ */
+
+/* $XFree86: xc/programs/xedit/lisp/re/re.c,v 1.9 2002/12/11 04:44:28 paulo Exp $ */
+
+#include <stdio.h>
+#include "rep.h"
+#define DEBUG
+/*
+ * Types
+ */
+
+/*  Information used when generating the final form of the compiled re.
+ */
+struct _re_inf {
+    rec_alt *alt;
+    unsigned char *cod;
+    long len;
+    long spc;
+
+    /* Start offset of special repetition instruction */
+    long sr[MAX_DEPTH];
+
+    /* Jump offset of special repetition instruction */
+    long sj[MAX_DEPTH];
+
+    /* Just a flag, to know if this nesting is for a special repetition */
+    char sp[MAX_DEPTH];
+
+    int bas;			/* Alternatives/repetitions depth */
+    int par;			/* Open parenthesis counter */
+    int ref;			/* Backreference counter */
+
+    rec_pat *apat;		/*  Alternatives duplicate patterns
+				 * if a special repetition is found,
+				 * this is done to somewhat simplify
+				 * the bytecode engine and still allow
+				 * some complex (and time consuming)
+				 * patterns. */
+
+    int flags;
+    int ecode;
+};
+
+/*  This structure is not associated with re_cod as it's data only matters
+ * to the current match search.
+ */
+struct _re_eng {
+    unsigned char *bas;		/* Base string pointer */
+    unsigned char *str;		/* String to search for pattern */
+    unsigned char *end;		/* Where to stop searching */
+    unsigned char *cod;		/* Pointer in the re_cod structure */
+    long off;			/* Number of used entries in so/eo etc */
+
+    /* Match offset/nesting information */
+    long so[MAX_DEPTH];		/* (s)tart of (m)atch */
+    long eo[MAX_DEPTH];		/* (e)nd of (m)atch */
+    long sv[MAX_DEPTH];		/* (s)a(v)e match end offset */
+    long re[MAX_DEPTH];		/* (re)petition count */
+    long ss[MAX_DEPTH];		/* (s)ave (s)tart of match */
+    unsigned char *rcod[MAX_DEPTH];	/* restart position in regex code */
+    unsigned char *rstr[MAX_DEPTH];	/* restart position in string */
+
+    /* Group/backreference information */
+    long goff;
+    long gso[9];
+    long geo[9];
+};
+
+/*
+ * Prototypes
+ */
+static void reinit(void);
+static int rec_check(re_inf*, int);
+static int rec_code(re_inf*, ReCode);
+static int rec_byte(re_inf*, int);
+static int rec_byte_byte(re_inf*, int, int);
+static int rec_code_byte(re_inf*, ReCode, int);
+static int rec_length(re_inf*, int);
+static int rec_code_byte_byte(re_inf*, ReCode, int, int);
+static int rec_build_alt(re_inf*, rec_alt*);
+static int rec_build_pat(re_inf*, rec_pat*);
+static int rec_build_rng(re_inf*, rec_rng*);
+static int rec_build_grp(re_inf*, rec_grp*);
+static int rec_build_stl(re_inf*, rec_stl*);
+static int rec_build_rep(re_inf*, rec_rep*);
+static int rec_inc_spc(re_inf*);
+static int rec_dec_spc(re_inf*);
+static int rec_add_spc(re_inf*, int);
+static int rec_off_spc(re_inf*);
+static int rec_alt_spc(re_inf*, int);
+static int rec_rep_spc(re_inf*, int);
+#ifdef DEBUG
+static void redump(re_cod*);
+#endif
+
+/*
+ * Initialization
+ */
+unsigned char re__alnum[256];
+unsigned char re__odigit[256];
+unsigned char re__ddigit[256];
+unsigned char re__xdigit[256];
+unsigned char re__control[256];
+
+/*
+ * Implementation
+ */
+int
+recomp(re_cod *preg, const char *pattern, int flags)
+{
+    int i, ecode;
+    re_inf inf;
+
+    reinit();
+
+    preg->cod = NULL;
+    inf.alt = irec_comp(pattern,
+			flags & RE_PEND ? preg->re_endp :
+				pattern + strlen(pattern),
+			flags, &ecode);
+    if (ecode != 0)
+	return (ecode);
+
+    inf.cod = NULL;
+    inf.len = inf.spc = 0;
+    inf.bas = 0;
+    inf.par = 0;
+    inf.ref = 0;
+    inf.apat = NULL;
+    inf.flags = flags;
+    inf.ecode = 0;
+    for (i = 0; i < MAX_DEPTH; i++)
+	inf.sp[i] = 0;
+
+    /* First byte is runtime modifier flags */
+    if (rec_byte(&inf, flags & (RE_NEWLINE | RE_NOSUB)) == 0 &&
+	rec_byte(&inf, 0xff) == 0 &&
+	rec_build_alt(&inf, inf.alt) == 0 &&
+	rec_rep_spc(&inf, 0) == 0 &&
+	rec_code(&inf, Re_Done) == 0) {
+	/*  Number of possible references, loops will not leave this
+	 * value correct, but it is cheap to read it from the second
+	 * byte, instead of adding several extra checks in the bytecode. */
+	if (inf.ref)
+	    inf.cod[1] = inf.ref - 1;
+	preg->cod = inf.cod;
+	/*  Public structure member */
+	preg->re_nsub = inf.ref;
+    }
+
+    irec_free_alt(inf.alt);
+    if (inf.ecode)
+	free(inf.cod);
+#ifdef DEBUG
+    else if (flags & RE_DUMP)
+	redump(preg);
+#endif
+
+    return (inf.ecode);
+}
+
+int
+reexec(const re_cod *preg, const char *string,
+       int nmatch, re_mat pmat[], int flags)
+{
+    unsigned char *ptr, *str, newline, nosub;
+    int len, si, ci, bas, i, j, k, l, m;
+    re_eng eng;
+
+    if (preg == NULL || preg->cod == NULL || nmatch < 0 ||
+	((flags & RE_STARTEND) &&
+	 (pmat == NULL || pmat[0].rm_eo < pmat[0].rm_so)))
+	return (RE_INVARG);
+
+    eng.str = (unsigned char*)string;
+    if (flags & RE_STARTEND) {
+	eng.end = eng.str + pmat[0].rm_eo;
+	eng.str += pmat[0].rm_so;
+    }
+    else
+	eng.end = eng.str + strlen(string);
+    eng.bas = eng.str;
+    nosub = preg->cod[0] & RE_NOSUB;
+    newline = preg->cod[0] & RE_NEWLINE;
+    eng.cod = preg->cod + 2;
+
+    if (!nosub && preg->cod[1] != 0xff) {
+	for (i = 0; i <= preg->cod[1]; i++) {
+	    eng.gso[i] = 0;
+	    eng.geo[i] = -1;
+	}
+    }
+
+    /* Setup to search for start of match from the first character */
+    eng.so[0] = 0;
+    eng.eo[0] = eng.sv[0] = -1;
+    eng.rcod[0] = eng.cod;
+    eng.rstr[0] = eng.str + 1;
+    eng.off = 0;
+    eng.goff = -1;
+    for (ci = si = 1;;) {
+reset:
+	switch (*eng.cod) {
+	    /****************************************************
+	     * One byte codes					*
+	     ****************************************************/
+	    case Re_Any:
+		if (eng.str == eng.end || (newline && eng.str[0] == '\n'))
+		    goto fail;
+		goto match;
+	    case Re_AnyEatAnyTimes:
+		if (newline) {
+		    for (ptr = eng.str; ptr < eng.end; ptr++) {
+			if (*ptr == '\n')
+			    break;
+		    }
+		    si = ptr - eng.str;
+		}
+		else
+		    si = eng.end - eng.str;
+		goto match;
+	    case Re_AnyEatMaybe:
+		si = eng.end > eng.str;
+		if (newline && si && eng.str[0] == '\n')
+		    si = 0;
+		goto match;
+	    case Re_AnyEatAtLeast:
+		if (newline) {
+		    for (ptr = eng.str; ptr < eng.end; ptr++) {
+			if (*ptr == '\n')
+			    break;
+		    }
+		    si = ptr - eng.str;
+		}
+		else
+		    si = eng.end - eng.str;
+		if (si == 0) {
+		    si = 1;
+		    goto fail;
+		}
+		goto match;
+	    case Re_Odigit:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (re__odigit[eng.str[0]])
+		    goto match;
+		goto fail;
+	    case Re_OdigitNot:
+		if (eng.str >= eng.end || re__odigit[eng.str[0]])
+		    goto fail;
+		goto match;
+	    case Re_Digit:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (re__ddigit[eng.str[0]])
+		    goto match;
+		goto fail;
+	    case Re_DigitNot:
+		if (eng.str >= eng.end || re__ddigit[eng.str[0]])
+		    goto fail;
+		goto match;
+	    case Re_Xdigit:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (re__xdigit[eng.str[0]])
+		    goto match;
+		goto fail;
+	    case Re_XdigitNot:
+		if (eng.str >= eng.end || re__xdigit[eng.str[0]])
+		    goto fail;
+		goto match;
+	    case Re_Space:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] == ' ' || eng.str[0] == '\t')
+		    goto match;
+		goto fail;
+	    case Re_SpaceNot:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] != ' ' && eng.str[0] != '\t')
+		    goto match;
+		goto fail;
+	    case Re_Tab:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] == '\t')
+		    goto match;
+		goto fail;
+	    case Re_Newline:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] == '\n')
+		    goto match;
+		goto fail;
+	    case Re_Lower:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] >= 'a' && eng.str[0] <= 'z')
+		    goto match;
+		goto fail;
+	    case Re_Upper:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] >= 'A' && eng.str[0] <= 'Z')
+		    goto match;
+		goto fail;
+	    case Re_Alnum:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (re__alnum[eng.str[0]])
+		    goto match;
+		goto fail;
+	    case Re_AlnumNot:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (re__alnum[eng.str[0]])
+		    goto fail;
+		goto match;
+	    case Re_Control:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (re__control[eng.str[0]])
+		    goto match;
+		goto fail;
+	    case Re_ControlNot:
+		if (eng.str >= eng.end || re__control[eng.str[0]])
+		    goto fail;
+		goto match;
+
+	    /****************************************************
+	     * One byte codes, match special emtpy strings	*
+	     ****************************************************/
+	    case Re_Bol:
+		if (eng.str == eng.bas) {
+		    if ((flags & RE_NOTBOL)) {
+			/* String does not start at the beginning of a line */
+			if (newline)
+			    goto fail;
+			goto wont;
+		    }
+		    si = 0;
+		    goto match;
+		}
+		if (newline && eng.str[-1] == '\n') {
+		    si = 0;
+		    goto match;
+		}
+		goto fail;
+	    case Re_Eol:
+		if (eng.str == eng.end) {
+		    if (flags & RE_NOTEOL)
+			/* String does not finish at the end of a line */
+			goto wont;
+		    si = 0;
+		    goto match;
+		}
+		if (newline && eng.str[0] == '\n') {
+		    si = 0;
+		    goto match;
+		}
+		goto fail;
+	    case Re_Bow:
+		if (eng.str >= eng.end ||
+		    (eng.str > eng.bas &&
+		     (re__alnum[eng.str[-1]])))
+		    goto fail;
+		if (re__alnum[eng.str[0]]) {
+		    si = 0;
+		    goto match;
+		}
+		goto fail;
+	    case Re_Eow:
+		if (eng.str == eng.bas ||
+		    (eng.str < eng.end &&
+		     re__alnum[eng.str[0]]))
+		    goto fail;
+		if (re__alnum[eng.str[-1]]) {
+		    si = 0;
+		    goto match;
+		}
+		goto fail;
+
+	    /****************************************************
+	     * One byte code, one byte argument			*
+	     ****************************************************/
+	    case Re_Literal:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] == eng.cod[1]) {
+		    ci = 2;
+		    goto match;
+		}
+		goto fail;
+	    case Re_LiteralNot:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] != eng.cod[1]) {
+		    ci = 2;
+		    goto match;
+		}
+		goto fail;
+	    case Re_SearchLiteral:
+		for (str = eng.str; str < eng.end; str++) {
+		    if (*str == eng.cod[1]) {
+			ci = 2;
+			eng.str = str;
+			goto match;
+		    }
+		}
+		/* This bytecode only happens in the toplevel */
+		eng.so[0] = str - eng.bas;
+		eng.str = str;
+		goto fail;
+
+	    /****************************************************
+	     * One byte code, two bytes argument		*
+	     ****************************************************/
+	    case Re_CaseLiteral:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] == eng.cod[1] || eng.str[0] == eng.cod[2]) {
+		    ci = 3;
+		    goto match;
+		}
+		goto fail;
+	    case Re_CaseLiteralNot:
+		if (eng.str >= eng.end)
+		    goto fail;
+		if (eng.str[0] != eng.cod[1] && eng.str[0] != eng.cod[2]) {
+		    ci = 3;
+		    goto match;
+		}
+		goto fail;
+	    case Re_SearchCaseLiteral:
+		for (str = eng.str; str < eng.end; str++) {
+		    if (*str == eng.cod[1] || *str == eng.cod[2]) {
+			ci = 3;
+			eng.str = str;
+			goto match;
+		    }
+		}
+		eng.so[0] = str - eng.bas;
+		eng.str = str;
+		goto fail;
+
+	    /****************************************************
+	     * One byte codes, two arguments, n bytes		*
+	     ****************************************************/
+	    case Re_String:
+		len = eng.cod[1];
+		if (len & 0x80) {
+		    i = 3;
+		    len = (len & 0x7f) + (eng.cod[2] << 7);
+		}
+		else
+		    i = 2;
+		if (eng.end - eng.str < len)
+		    goto fail;
+		ptr = eng.cod + i;
+		str = eng.str;
+		for (k = len; k > 0; k--) {
+		    if (*ptr++ != *str++)
+			goto fail;
+		}
+		ci = i + len;
+		si = len;
+		goto match;
+	    case Re_SearchString:
+		len = eng.cod[1];
+		if (len & 0x80) {
+		    i = 3;
+		    len = (len & 0x7f) + (eng.cod[2] << 7);
+		}
+		else
+		    i = 2;
+		for (str = eng.str; eng.end - str >= len; str = eng.str++) {
+		    for (ptr = eng.cod + i, str = eng.str, k = len; k > 0; k--)
+			if (*ptr++ != *str++)
+			    break;
+		    if (k == 0) {
+			/* Substring found */
+			ci = i + len;
+			si = str - eng.str;
+			goto match;
+		    }
+		}
+		eng.so[0] = eng.end - eng.bas;
+		eng.str = eng.end;
+		goto fail;
+
+	    case Re_CaseString:
+		len = eng.cod[1];
+		if (len & 0x80) {
+		    i = 3;
+		    len = (len & 0x7f) + (eng.cod[2] << 7);
+		}
+		else
+		    i = 2;
+
+		len >>= 1;
+		/*  Check if there are at least len/2 bytes left, string
+		 * is represented as two bytes, lower and upper case */
+		if (eng.end - eng.str < len)
+		    goto fail;
+		ptr = eng.cod + i;
+		str = eng.str;
+		for (k = len; k > 0; str++, ptr += 2, k--) {
+		    if (*str != ptr[0] && *str != ptr[1])
+			goto fail;
+		}
+		ci = i + (len << 1);
+		si = len;
+		goto match;
+	    case Re_SearchCaseString:
+		len = eng.cod[1];
+		if (len & 0x80) {
+		    i = 3;
+		    len = (len & 0x7f) + (eng.cod[2] << 7);
+		}
+		else
+		    i = 2;
+		len >>= 1;
+		for (str = eng.str; eng.end - str >= len; str = eng.str++) {
+		    for (ptr = eng.cod + i, str = eng.str, k = len;
+			 k > 0; k--, ptr += 2, str++)
+			if (ptr[0] != str[0] && ptr[1] != str[0])
+			    break;
+		    if (k == 0) {
+			/* Substring found */
+			ci = i + (len << 1);
+			si = str - eng.str;
+			goto match;
+		    }
+		}
+		eng.so[0] = eng.end - eng.bas;
+		eng.str = eng.end;
+		goto fail;
+
+	    case Re_StringList:
+		/* Number of strings */
+		k = eng.cod[1];
+
+		/* Where to jump after match */
+		bas = eng.cod[2] | (eng.cod[3] << 8);
+
+		str = eng.str;
+		ptr = eng.cod + k + 4;
+		l = eng.end - eng.str;
+		for (j = 0; j < k; j++) {
+		    len = eng.cod[j + 4];
+		    if (len <= l) {
+			for (i = 0; i < len; i++)
+			    if (ptr[i] != str[i])
+				goto next_stl;
+			goto stl_match;
+		    }
+next_stl:
+		    ptr += len;
+		}
+		goto fail;
+stl_match:
+		ci = bas;
+		si = len;
+		goto match;
+
+	    case Re_CaseStringList:
+		/* Number of strings */
+		k = eng.cod[1];
+
+		/* Where to jump after match */
+		bas = eng.cod[2] | (eng.cod[3] << 8);
+
+		str = eng.str;
+		ptr = eng.cod + k + 4;
+		l = eng.end - eng.str;
+		for (j = 0; j < k; j++) {
+		    len = eng.cod[j + 4];
+		    if ((len >> 1) <= l) {
+			for (i = m = 0; i < len; m++, i += 2)
+			    if (ptr[i] != str[m] && ptr[i + 1] != str[m])
+				goto next_cstl;
+			goto cstl_match;
+		    }
+next_cstl:
+		    ptr += len;
+		}
+		goto fail;
+cstl_match:
+		ci = bas;
+		si = len >> 1;
+		goto match;
+
+
+	    case Re_LargeStringList:
+		/* Where to jump after match */
+		bas = eng.cod[1] | (eng.cod[2] << 8);
+
+		str = eng.str;
+
+		/* First entry in index map */
+		ptr = eng.cod + 3;
+		i = (int)str[0] << 1;
+		j = ptr[i] | (ptr[i + 1] << 8);
+		if (j == 0xffff)
+		    /* No entry with this byte */
+		    goto fail;
+
+		/* Bytes left in input */
+		l = eng.end - eng.str;
+
+		/* First entry matching initial byte */
+		ptr += 512 + j;
+
+		for (len = ptr[0];
+		     str[0] == ptr[1];
+		     ptr += len + 1, len = ptr[0]) {
+		    if (len <= l) {
+			for (i = 1; i < len; i++) {
+			    if (ptr[i + 1] != str[i])
+				goto next_lstl;
+			}
+			ci = bas;
+			si = len;
+			goto match;
+		    }
+next_lstl:;
+		}
+		goto fail;
+
+	    case Re_LargeCaseStringList:
+		/* Where to jump after match */
+		bas = eng.cod[1] | (eng.cod[2] << 8);
+
+		str = eng.str;
+
+		/* First entry in index map */
+		ptr = eng.cod + 3;
+		i = (int)str[0] << 1;
+		j = ptr[i] | (ptr[i + 1] << 8);
+		if (j == 0xffff)
+		    /* No entry with this byte */
+		    goto fail;
+
+		/* Bytes left in input */
+		l = eng.end - eng.str;
+
+		/* First entry matching initial byte */
+		ptr += 512 + j;
+
+		for (len = ptr[0];
+		     str[0] == ptr[1] || str[0] == ptr[2];
+		     ptr += len + 1, len = ptr[0]) {
+		    if ((k = (len >> 1)) <= l) {
+			for (i = 2, j = 1; i < len; i += 2, j++) {
+			    if (ptr[i + 1] != str[j] && ptr[i + 2] != str[j])
+				goto next_lcstl;
+			}
+			ci = bas;
+			si = k;
+			goto match;
+		    }
+next_lcstl:;
+		}
+		goto fail;
+
+
+	    /****************************************************
+	     * Character range matching				*
+	     ****************************************************/
+	    case Re_Range:
+		if (eng.str < eng.end && eng.cod[eng.str[0] + 1]) {
+		    ci = 257;
+		    goto match;
+		}
+		goto fail;
+	    case Re_RangeNot:
+		if (eng.str >= eng.end || eng.cod[eng.str[0] + 1])
+		    goto fail;
+		ci = 257;
+		goto match;
+
+	    /****************************************************
+	     * Group handling					*
+	     ****************************************************/
+	    case Re_Open:
+		if (++eng.goff >= 9)
+		    return (RE_ASSERT);
+		eng.gso[eng.goff] = eng.str - eng.bas;
+		++eng.cod;
+		continue;
+	    case Re_Close:
+		eng.geo[eng.goff] = eng.str - eng.bas;
+		++eng.cod;
+		continue;
+	    case Re_Update:
+		bas = eng.cod[1];
+		eng.geo[eng.goff] = eng.str - eng.bas;
+		eng.cod += 2;		/* + Update + bas */
+		continue;
+
+	    /****************************************************
+	     * Backreference					*
+	     ****************************************************/
+	    case Re_Backref:
+		i = eng.cod[1];
+		j = eng.gso[i];
+		k = eng.geo[i];
+		len = k - j;
+		if (k < j || eng.end - eng.str < len)
+		    goto fail;
+		ptr = eng.bas + j;
+		str = eng.str;
+		for (l = len; l > 0; l--) {
+		    if (*ptr++ != *str++)
+			goto fail;
+		}
+		ci = 2;
+		si = len;
+		goto match;
+
+	    /****************************************************
+	     * Alternatives handling				*
+	     ****************************************************/
+	    case Re_Alt:
+		bas = eng.off;
+		if (++eng.off >= MAX_DEPTH)
+		    return (RE_ASSERT);
+
+		/* Get offset of next alternative */
+		i = eng.cod[1] | (eng.cod[2] << 8);
+
+		/* Setup for next alternative if the current fails */
+		eng.rcod[eng.off] = eng.cod + i + 1;	/* + Alt */
+
+		/* If fail, test the next alternative in the same string */
+		eng.rstr[eng.off] = eng.str;
+
+		/* Setup match offsets */
+		if (eng.so[bas] <= eng.eo[bas])
+		    eng.so[eng.off] = eng.eo[bas];
+		else
+		    eng.so[eng.off] = eng.so[bas];
+		eng.sv[eng.off] = eng.eo[eng.off] = eng.so[eng.off] - 1;
+
+		/* Save start of possible previous matches */
+		eng.ss[eng.off] = eng.so[bas];
+
+		/* Skip code */
+		eng.cod += 3;
+
+		/* Go try the first alternative */
+		continue;
+
+	    case Re_AltNext:
+		bas = eng.off - 1;
+		/* Check if matched and if it is a better match */
+		if (eng.sv[eng.off] - eng.so[eng.off] <
+		    eng.eo[eng.off] - eng.so[eng.off])
+		    eng.sv[eng.off] = eng.eo[eng.off];
+
+		/* Get offset of next alternative */
+		i = eng.cod[1] | (eng.cod[2] << 8);
+
+		/* Setup for next alternative if the current fails */
+		eng.rcod[eng.off] = eng.cod + i + 1;	/* + AltNext */
+
+		/* Setup match offset */
+		eng.eo[eng.off] = eng.so[eng.off] - 1;
+
+		/* Reset string for next alternative */
+		eng.str = eng.rstr[eng.off];
+
+		/* Skip code */
+		eng.cod += 3;
+
+		/* Go try the next alternative */
+		continue;
+
+	    case Re_AltDone:
+		bas = eng.off - 1;
+		/* Check if matched and if it is a better match */
+		if (eng.sv[eng.off] - eng.so[eng.off] <
+		    eng.eo[eng.off] - eng.so[eng.off])
+		    eng.sv[eng.off] = eng.eo[eng.off];
+
+		/* If there is a match */
+		if (eng.sv[eng.off] >= eng.so[eng.off]) {
+		    eng.so[bas] = eng.ss[eng.off];
+		    eng.eo[bas] = eng.sv[eng.off];
+		    eng.str = eng.bas + eng.eo[bas];
+
+		    /* Pop stack and skip code */
+		    --eng.off;
+		    ++eng.cod;
+
+		    /* Go try next regular expression pattern */
+		    continue;
+		}
+
+		/* Failed, reset string and pop stack */
+		eng.str = eng.rstr[eng.off];
+		--eng.off;
+		goto fail;
+
+
+	    /****************************************************
+	     * Repetition					*
+	     ****************************************************/
+
+		/*  Note that the repetition counter is not
+		 * updated for <re>*, <re>+ and <re>?
+		 * it is easy to updated, but since it is not
+		 * really useful, code to do it was removed
+		 * to save a few cpu cicles. */
+
+#define REPETITION_SETUP()					\
+	if (++eng.off >= MAX_DEPTH)				\
+	    return (RE_ASSERT);					\
+								\
+	/* Return here for recovery if match fail */		\
+	eng.rcod[eng.off] = eng.cod;				\
+								\
+	/* Setup match offsets */				\
+	if (eng.so[bas] <= eng.eo[bas])				\
+	    eng.so[eng.off] = eng.eo[bas];			\
+	else							\
+	    eng.so[eng.off] = eng.so[bas];			\
+	eng.ss[eng.off] = eng.so[bas];				\
+	eng.sv[eng.off] = eng.eo[eng.off] = eng.so[eng.off] - 1;\
+								\
+	/* Skip repetition instruction */			\
+	eng.cod += 4;
+
+
+	    case Re_AnyTimes:
+		bas = eng.cod[1];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    REPETITION_SETUP();
+		}
+		else {
+		    if (eng.eo[eng.off] >= eng.so[eng.off] &&
+			eng.eo[eng.off] > eng.sv[eng.off]) {
+			/* Update offset of match */
+			eng.sv[eng.off] = eng.eo[eng.off];
+
+			/* Skip repetition instruction */
+			eng.cod += 4;
+		    }
+		    else {
+			/* Match failed but it is ok */
+			len = eng.cod[2] | (eng.cod[3] << 8);
+			eng.so[bas] = eng.ss[eng.off];
+			if (eng.sv[eng.off] >= eng.so[eng.off])
+			    /* Something matched earlier, update */
+			    eng.eo[bas] = eng.sv[eng.off];
+			else if (eng.eo[bas] < eng.so[bas])
+			    /* Empty match */
+			    eng.eo[bas] = eng.so[bas];
+
+			/* Try next pattern at correct offset */
+			eng.str = eng.bas + eng.eo[bas];
+
+			/* Pop stack and skip code */
+			--eng.off;
+			eng.cod += len;
+		    }
+		}
+		continue;
+
+	    case Re_Maybe:
+		bas = eng.cod[1];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    REPETITION_SETUP();
+		}
+		else {
+		    /* Matched or first iteration is done */
+		    len = eng.cod[2] | (eng.cod[3] << 8);
+		    eng.so[bas] = eng.ss[eng.off];
+		    if (eng.eo[eng.off] > eng.so[eng.off]) {
+			/* Something matched earlier, update */
+			eng.eo[bas] = eng.eo[eng.off];
+			eng.str = eng.bas + eng.eo[bas];
+			/* Don't need to update counter */
+		    }
+		    else {
+			/* Empty match */
+			if (eng.eo[bas] < eng.so[bas])
+			    eng.eo[bas] = eng.so[bas];
+
+			/* Try next pattern at correct offset */
+			eng.str = eng.bas + eng.eo[bas];
+		    }
+
+		    /* Pop stack */
+		    --eng.off;
+
+		    /* Skip code */
+		    eng.cod += len;
+		}
+		continue;
+
+	    case Re_AtLeast:
+		bas = eng.cod[1];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    REPETITION_SETUP();
+		}
+		else {
+		    if (eng.eo[eng.off] >= eng.so[eng.off] &&
+			eng.eo[eng.off] > eng.sv[eng.off]) {
+			/* Update offset of match */
+			eng.sv[eng.off] = eng.eo[eng.off];
+
+			/* Skip repetition instruction */
+			eng.cod += 4;
+		    }
+		    else {
+			/* Last try failed */
+			len = eng.cod[2] | (eng.cod[3] << 8);
+			if (eng.sv[eng.off] >= eng.so[eng.off]) {
+			    /* Something matched earlier, update */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+			}
+			else {
+			    /*	Do it here, so that the fail label does
+			     * not need to do too expensive work for
+			     * simple patterns. */
+			    eng.so[bas] = eng.str - eng.bas;
+
+			    /* Zero matches, pop stack and restart */
+			    --eng.off;
+			    goto fail;
+			}
+
+			/* Pop stack and skip code */
+			--eng.off;
+			eng.cod += len;
+		    }
+		}
+		continue;
+
+
+	    /****************************************************
+	     * Repetition with arguments			*
+	     ****************************************************/
+	    case Re_Exact:
+#define COMPLEX_REPETITION_SETUP_0()				\
+	i = eng.cod[1];						\
+	bas = eng.cod[2];
+
+#define COMPLEX_REPETITION_SETUP()				\
+	/* First iteration */					\
+	if (++eng.off >= MAX_DEPTH)				\
+	    return (RE_ASSERT);					\
+								\
+	/*  Remeber number or repetitions */			\
+	eng.re[eng.off] = 0;					\
+								\
+	/* Return here for recovery if match fail */		\
+	eng.rcod[eng.off] = eng.cod;				\
+								\
+	/* Setup match offsets */				\
+	if (eng.so[bas] <= eng.eo[bas])				\
+	    eng.so[eng.off] = eng.eo[bas];			\
+	else							\
+	    eng.so[eng.off] = eng.so[bas];			\
+	eng.sv[eng.off] = eng.eo[eng.off] = eng.so[eng.off] - 1;\
+	eng.ss[eng.off] = eng.so[bas];				\
+								\
+	/* Skip repetition instruction */			\
+	eng.cod += 5;
+
+		COMPLEX_REPETITION_SETUP_0();
+		if (eng.off == bas) {
+		    /* First iteration */
+		    COMPLEX_REPETITION_SETUP();
+		}
+		else {
+		    if (eng.eo[eng.off] >= eng.so[eng.off] &&
+			eng.eo[eng.off] > eng.sv[eng.off]) {
+			/* Update offset of match */
+			eng.sv[eng.off] = eng.eo[eng.off];
+
+			/* Update repetition counter */
+			if (++eng.re[eng.off] == i) {
+			    /* Matched the required times */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+
+			    /* Update code */
+			    k = eng.cod[3] | (eng.cod[4] << 8);
+			    eng.cod += k;
+
+			    /* Pop stack and go for next pattern */
+			    --eng.off;
+			    continue;
+			}
+
+			/* Skip repetition instruction */
+			eng.cod += 5;
+		    }
+		    else {
+			/*  Do it here, so that the fail label does
+			 * not need to do too expensive work for
+			 * simple patterns. */
+			eng.so[bas] = eng.str - eng.bas;
+
+			/* Pop stack and restart */
+			--eng.off;
+			goto fail;
+		    }
+		}
+		continue;
+
+	    case Re_Min:
+		COMPLEX_REPETITION_SETUP_0();
+		if (eng.off == bas) {
+		    /* First iteration */
+		    COMPLEX_REPETITION_SETUP();
+		}
+		else {
+		    if (eng.eo[eng.off] >= eng.so[eng.off] &&
+			eng.eo[eng.off] > eng.sv[eng.off]) {
+			/* Update offset of match */
+			eng.sv[eng.off] = eng.eo[eng.off];
+
+			/* Update repetition counter */
+			++eng.re[eng.off];
+
+			/* Skip repetition instruction and try again */
+			eng.cod += 5;
+		    }
+		    else {
+			/* Match failed! */
+			if (eng.re[eng.off] < i) {
+			    /*	Do it here, so that the fail label does
+			     * not need to do too expensive work for
+			     * simple patterns. */
+			    eng.so[bas] = eng.str - eng.bas;
+
+			    /* Didn't match required number of times */
+			    --eng.off;
+			    goto fail;
+			}
+			else {
+			    /* Matched minimum number of times */
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+			    k = eng.cod[3] | (eng.cod[4] << 8);
+
+			    /* Update code and pop stack */
+			    eng.cod += k;
+			    --eng.off;
+			}
+		    }
+		}
+		continue;
+
+	    case Re_Max:
+		COMPLEX_REPETITION_SETUP_0();
+		if (eng.off == bas) {
+		    /* First iteration */
+		    COMPLEX_REPETITION_SETUP();
+		}
+		else {
+		    if (eng.eo[eng.off] >= eng.so[eng.off] &&
+			eng.eo[eng.off] > eng.sv[eng.off]) {
+			/* Update offset of match */
+			eng.sv[eng.off] = eng.eo[eng.off];
+
+			/* Update repetition counter */
+			if (++eng.re[eng.off] == i) {
+			    /* Matched the maximum times */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+
+			    k = eng.cod[3] | (eng.cod[4] << 8);
+
+			    /* Update code and pop stack */
+			    eng.cod += k;
+			    --eng.off;
+			    continue;
+			}
+
+			/* Skip repetition instruction and try again */
+			eng.cod += 5;
+		    }
+		    else {
+			/* No matches, but zero matches are ok */
+			k = eng.cod[3] | (eng.cod[4] << 8);
+			if (eng.sv[eng.off] >= eng.so[eng.off]) {
+			    /* Something matched earlier, update */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+			}
+			else {
+			    /* Empty match */
+			    if (eng.eo[bas] < eng.so[bas])
+				eng.eo[bas] = eng.so[bas];
+
+			    /* Try next pattern at correct offset */
+			    eng.str = eng.bas + eng.eo[bas];
+			}
+
+			/* Pop stack and update code */
+			--eng.off;
+			eng.cod += k;
+		    }
+		}
+		continue;
+
+	    case Re_MinMax:
+		bas = eng.cod[3];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    COMPLEX_REPETITION_SETUP();
+		}
+		else {
+		    if (eng.eo[eng.off] >= eng.so[eng.off] &&
+			eng.eo[eng.off] > eng.sv[eng.off]) {
+			/* Update offset of match */
+			eng.sv[eng.off] = eng.eo[eng.off];
+
+			/* Update repetition counter */
+			if (++eng.re[eng.off] == eng.cod[2]) {
+			    /* Matched the maximum times */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+			    k = eng.cod[4] | (eng.cod[5] << 8);
+
+			    /* Update code and pop stack */
+			    eng.cod += k;
+			    --eng.off;
+			    continue;
+			}
+
+			/* Skip repetition instruction and try again */
+			eng.cod += 6;
+		    }
+		    else {
+			/* Match failed! */
+			if (eng.re[eng.off] < eng.cod[1]) {
+			    /*	Do it here, so that the fail label does
+			     * not need to do too expensive work for
+			     * simple patterns. */
+			    eng.so[bas] = eng.str - eng.bas;
+
+			    /* Didn't match required number of times */
+			    --eng.off;
+			    goto fail;
+			}
+			else {
+			    /* Matched minimum number of times */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.sv[eng.off];
+			    eng.str = eng.bas + eng.eo[bas];
+			    k = eng.cod[4] | (eng.cod[5] << 8);
+
+			    /* Update code and pop stack */
+			    eng.cod += k;
+			    --eng.off;
+			}
+		    }
+		}
+		continue;
+
+
+	    /****************************************************
+	     * Special repetition handling			*
+	     ****************************************************/
+	    case Re_AnyAnyTimes:
+		/* code(1) + bas(1) + gbas(1) + jump(2) */
+		bas = eng.cod[1];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    if (++eng.off >= MAX_DEPTH)
+			return (RE_ASSERT);
+
+		    /* Return here for recovery if match fail */
+		    eng.rcod[eng.off] = eng.cod;
+
+		    /* If fail, test the next pattern at the same point */
+		    eng.rstr[eng.off] = eng.str;
+
+		    /* Setup match offsets */
+		    eng.so[eng.off] = eng.str - eng.bas;
+		    eng.eo[eng.off] = eng.so[eng.off] - 1;
+
+		    if (newline)
+			/*  Use the repetition counter to store start of
+			 * skipped string, to later check if skipping a
+			 * newline. */
+			eng.re[eng.off] = eng.so[eng.off];
+
+		    /* Save start of possible previous matches */
+		    eng.ss[eng.off] = eng.so[bas];
+
+		    /* Skip repetition instruction */
+		    eng.cod += 5;
+		}
+		else {
+		    /* -1 as an unsigned char */
+		    if (eng.cod[2] != 0xff)
+			eng.goff = eng.cod[2];
+		    else
+			eng.goff = -1;
+
+		    if (newline) {
+			ptr = eng.bas + eng.re[eng.off];
+			str = eng.bas + eng.so[eng.off];
+			for (; ptr < str; ptr++)
+			    if (*ptr == '\n') {
+				eng.cod = eng.rcod[0];
+				eng.so[0] = ptr - eng.bas + 1;
+				eng.eo[0] = eng.so[0] - 1;
+				eng.rstr[0] = eng.str = ptr + 1;
+				eng.off = 0;
+				goto reset;
+			    }
+			/* If looping, don't do too many noops */
+			eng.re[eng.off] = ptr - eng.bas;
+		    }
+
+		    if (eng.eo[eng.off] >= eng.so[eng.off]) {
+			/* Note that this is only true if all possibly
+			 * nested special repetitions also matched. */
+
+			if (eng.goff >= 0) {
+			    if (eng.cod[5] == Re_Update)
+				eng.gso[eng.goff] = eng.eo[bas] +
+						    (eng.so[bas] > eng.eo[bas]);
+			    else if (eng.geo[eng.goff] < eng.so[eng.off])
+				eng.geo[eng.goff] = eng.so[eng.off];
+			}
+
+			/* Jump relative offset */
+			len = eng.cod[3] | (eng.cod[4] << 8);
+
+			/* Restore offset from where started trying */
+			eng.so[bas] = eng.ss[eng.off];
+			eng.eo[bas] = eng.eo[eng.off];
+
+			/* Pop stack and skip code */
+			--eng.off;
+			eng.cod += len;
+		    }
+		    else {
+			/* Only give up if the entire string was scanned */
+			if (eng.str < eng.end) {
+			    /* Update restart point for next pattern */
+			    eng.str = ++eng.rstr[eng.off];
+
+			    /* Reset start of nested match */
+			    eng.so[eng.off] = eng.str - eng.bas;
+
+			    /* Skip repetition instruction */
+			    eng.cod += 5;
+			}
+			else {
+			    /* Entire string scanned and failed */
+
+			    /* Jump relative offset */
+			    len = eng.cod[3] | (eng.cod[4] << 8);
+
+			    /* Restore offset from where started trying */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.ss[eng.off] - 1;
+
+			    /* Pop stack and skip code */
+			    --eng.off;
+			    eng.cod += len;
+			}
+		    }
+		}
+		continue;
+
+	    /*  This is significantly different than matching <re>.*<re>
+	     * because it may need to restart several times since it is
+	     * possible to find too many false positives, for example:
+	     *	a.*b	=> once one "a" is found, scan all
+	     *		   the remaining string searching for a "b"
+	     *  a.?b	=> the string may have too many "a"s, but the
+	     *		   first occurrences of "a" may not be followed
+	     *		   by any-character and a "b" or a single "b".
+	     */
+	    case Re_AnyMaybe:
+		bas = eng.cod[1];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    if (++eng.off >= MAX_DEPTH)
+			return (RE_ASSERT);
+
+		    /* Return here for recovery if match fail */
+		    eng.rcod[eng.off] = eng.cod;
+
+		    /* First try without eating a byte */
+		    eng.rstr[eng.off] = eng.str;
+
+		    /* Remember this is the first try if match fail */
+		    eng.re[eng.off] = 0;
+
+		    /* Setup match offsets */
+		    eng.so[eng.off] = eng.str - eng.bas;
+		    eng.eo[eng.off] = eng.so[eng.off] - 1;
+
+		    /* Save start of possible previous matches */
+		    eng.ss[eng.off] = eng.so[bas];
+
+		    /* Skip repetition instruction */
+		    eng.cod += 5;
+		}
+		else {
+		    /* -1 as an unsigned char */
+		    if (eng.cod[2] != 0xff)
+			eng.goff = eng.cod[2];
+		    else
+			eng.goff = -1;
+
+		    if (eng.eo[eng.off] >= eng.so[eng.off]) {
+			/* Something matched */
+
+			if (eng.goff >= 0) {
+			    if (eng.cod[5] == Re_Update)
+				eng.gso[eng.goff] = eng.eo[bas] +
+						    (eng.so[bas] > eng.eo[bas]);
+			    else if (eng.geo[eng.goff] < eng.so[eng.off])
+				eng.geo[eng.goff] = eng.so[eng.off];
+			}
+
+			/* Jump relative offset */
+			len = eng.cod[3] | (eng.cod[4] << 8);
+
+			/* Update offset of match */
+			eng.eo[bas] = eng.eo[eng.off];
+
+			/* Pop stack and skip code */
+			--eng.off;
+			eng.cod += len;
+		    }
+		    else if (eng.re[eng.off] == 0 &&
+			     (!newline || eng.rstr[eng.off][1] != '\n')) {
+			/* Try this time skiping a byte */
+			++eng.re[eng.off];
+
+			/* Reset string, skip code and go try one time more */
+			eng.str = ++eng.rstr[eng.off];
+			eng.cod += 5;
+		    }
+		    else {
+			/* Failed to match */
+
+			/* Update offsets */
+			eng.eo[bas] = eng.ss[eng.off];
+			eng.so[bas] = eng.eo[bas] + 1;
+
+			eng.str = eng.rstr[eng.off] + (eng.re[eng.off] == 0);
+
+			/* Pop stack and return to toplevel code */
+			--eng.off;
+			if (eng.str >= eng.end)
+			    goto wont;
+			eng.cod = eng.rcod[bas];
+		    }
+		}
+		continue;
+
+	    /* .+ almost identical to .* but requires eating at least one byte */
+	    case Re_AnyAtLeast:
+		bas = eng.cod[1];
+		if (eng.off == bas) {
+		    /* First iteration */
+		    if (++eng.off >= MAX_DEPTH)
+			return (RE_ASSERT);
+
+		    /* Return here for recovery if match fail */
+		    eng.rcod[eng.off] = eng.cod;
+
+		    /* Skip one byte for the restart string */
+		    if (newline && eng.str[0] == '\n') {
+			/* Cannot skip newline */
+			eng.cod = eng.rcod[0];
+			eng.rstr[0] = ++eng.str;
+			eng.so[0] = eng.str - eng.bas;
+			eng.eo[0] = eng.so[0] - 1;
+			eng.off = 0;
+			goto reset;
+		    }
+		    eng.rstr[eng.off] = ++eng.str;
+
+		    /* Setup match offsets */
+		    eng.so[eng.off] = eng.str - eng.bas;
+		    eng.eo[eng.off] = eng.so[eng.off] - 1;
+
+		    if (newline)
+			/*  Use the repetition counter to store start of
+			 * skipped string, to later check if skipping a
+			 * newline. */
+			eng.re[eng.off] = eng.so[eng.off];
+
+		    /* Save start of possible previous matches */
+		    eng.ss[eng.off] = eng.so[bas];
+
+		    /* Skip repetition instruction */
+		    eng.cod += 5;
+		}
+		else {
+		    /* -1 as an unsigned char */
+		    if (eng.cod[2] != 0xff)
+			eng.goff = eng.cod[2];
+		    else
+			eng.goff = -1;
+
+		    if (newline) {
+			ptr = eng.bas + eng.re[eng.off];
+			str = eng.bas + eng.so[eng.off];
+			for (; ptr < str; ptr++)
+			    if (*ptr == '\n') {
+				eng.cod = eng.rcod[0];
+				eng.so[0] = ptr - eng.bas + 1;
+				eng.eo[0] = eng.so[0] - 1;
+				eng.rstr[0] = eng.str = ptr + 1;
+				eng.off = 0;
+				goto reset;
+			    }
+			/* If looping, don't do too many noops */
+			eng.re[eng.off] = ptr - eng.bas;
+		    }
+
+		    if (eng.eo[eng.off] >= eng.so[eng.off]) {
+			/* Note that this is only true if all possibly
+			 * nested special repetitions also matched. */
+
+			if (eng.goff >= 0) {
+			    if (eng.cod[5] == Re_Update)
+				eng.gso[eng.goff] = eng.eo[bas] +
+						    (eng.so[bas] > eng.eo[bas]);
+			    else if (eng.geo[eng.goff] < eng.so[eng.off])
+				eng.geo[eng.goff] = eng.so[eng.off];
+			}
+
+			/* Jump relative offset */
+			len = eng.cod[3] | (eng.cod[4] << 8);
+
+			/* Restore offset from where started trying */
+			eng.so[bas] = eng.ss[eng.off];
+			eng.eo[bas] = eng.eo[eng.off];
+
+			/* Pop stack and skip code */
+			--eng.off;
+			eng.cod += len;
+		    }
+		    else {
+			/* Only give up if the entire string was scanned */
+			if (eng.str < eng.end) {
+			    /* Update restart point for next pattern */
+			    eng.str = ++eng.rstr[eng.off];
+
+			    /* Reset start of nested match */
+			    eng.so[eng.off] = eng.str - eng.bas;
+
+			    /* Skip repetition instruction */
+			    eng.cod += 5;
+			}
+			else {
+			    /* Entire string scanned and failed */
+
+			    /* Jump relative offset */
+			    len = eng.cod[3] | (eng.cod[4] << 8);
+
+			    /* Restore offset from where started trying */
+			    eng.so[bas] = eng.ss[eng.off];
+			    eng.eo[bas] = eng.ss[eng.off] - 1;
+
+			    /* Pop stack and skip code */
+			    --eng.off;
+			    eng.cod += len;
+			}
+		    }
+		}
+		continue;
+
+
+	    /****************************************************
+	     * Repetition matched!				*
+	     ****************************************************/
+	    case Re_RepJump:
+		/* eng.cod[1] is toplevel offset of repetition */
+		if (eng.off > eng.cod[1])
+		    /* If still needs to try matches */
+		    eng.cod -= eng.cod[2];
+		else
+		    eng.cod += 3;	/* + RepJump + bas + len-size */
+		continue;
+
+	    case Re_RepLongJump:
+		/* eng.cod[1] is toplevel offset of repetition */
+		if (eng.off > eng.cod[1])
+		    /* If still needs to try matches */
+		    eng.cod -= eng.cod[2] | (eng.cod[3] << 8);
+		else
+		    eng.cod += 4;	/* + RepLongJump + bas + len-size */
+		continue;
+
+	    /****************************************************
+	     * Finished						*
+	     ****************************************************/
+	    case Re_DoneIf:
+		if (eng.eo[eng.off] >= eng.so[eng.off]) {
+		    eng.so[0] = eng.ss[eng.off];
+		    eng.eo[0] = eng.eo[eng.off];
+		    goto done;
+		}
+		++eng.cod;
+		continue;
+	    case Re_MaybeDone:
+		if (eng.eo[eng.off] >= eng.so[eng.off]) {
+		    eng.so[0] = eng.ss[eng.off];
+		    eng.eo[0] = eng.eo[eng.off];
+		    goto done;
+		}
+		++eng.cod;
+		continue;
+	    case Re_Done:
+		goto done;
+
+	    default:
+		/* Fatal internal error */
+		return (RE_ASSERT);
+	}
+
+
+wont:
+	/* Surely won't match */
+	if (eng.off == 0) {
+	    eng.eo[0] = eng.so[0] - 1;
+	    break;
+	}
+
+
+fail:
+	if (eng.off == 0) {
+	    /* If the entire string scanned */
+	    if (++eng.str > eng.end) {
+		eng.eo[0] = eng.so[0] - 1;
+		break;
+	    }
+	    eng.goff = -1;
+	    /* Update start of possible match after restart */
+	    if (eng.eo[0] >= eng.so[0]) {
+		/* If first fail */
+		eng.str = eng.rstr[0];
+		++eng.rstr[0];
+		eng.so[0] = eng.str - eng.bas;
+		eng.eo[0] = eng.so[eng.off] - 1;
+	    }
+	    else
+		/* Just trying at next byte */
+		++eng.so[0];
+	}
+	else
+	    /* Remember this match failed */
+	    eng.eo[eng.off] = eng.so[eng.off] - 1;
+
+	/* Restart code */
+	eng.cod = eng.rcod[eng.off];
+	continue;
+
+
+match:
+	/* If first match */
+	if (eng.eo[eng.off] < eng.so[eng.off]) {
+	    if (eng.off == 0)
+		eng.rstr[0] = eng.str + 1;
+	    eng.so[eng.off] = eng.eo[eng.off] = eng.str - eng.bas;
+	}
+	eng.eo[eng.off] += si;
+	eng.cod += ci;
+	eng.str += si;
+	ci = si = 1;
+	continue;
+
+done:
+	break;
+    }
+
+    if (nmatch) {
+	if (flags & RE_STARTEND)
+	    len = pmat[0].rm_so;
+	else
+	    len = 0;
+	if (!nosub) {
+	    if (preg->cod[1] != 0xff)
+		eng.goff = preg->cod[1];
+	    pmat[0].rm_so = eng.so[0];
+	    pmat[0].rm_eo = eng.eo[0];
+	    for (i = 1; i < nmatch; i++) {
+		if (i - 1 <= eng.goff) {
+		    pmat[i].rm_so = eng.gso[i - 1];
+		    pmat[i].rm_eo = eng.geo[i - 1];
+		}
+		else {
+		    pmat[i].rm_so = 0;
+		    pmat[i].rm_eo = -1;
+		}
+	    }
+	    if (len) {
+		/* Update offsets, since the match was done in a substring */
+		j = eng.goff + 2 > nmatch ? nmatch : eng.goff + 2;
+		for (i = 0; i < j; i++) {
+		    pmat[i].rm_so += len;
+		    pmat[i].rm_eo += len;
+		}
+	    }
+	}
+	else {
+	    /*	Already know these values, allow compiling the regex with
+	     * RE_NOSUB to use parenthesis only for grouping, but avoiding
+	     * the runtime overhead of keeping track of the subexpression
+	     * offsets. */
+	    pmat[0].rm_so = eng.so[0] + len;
+	    pmat[0].rm_eo = eng.eo[0] + len;
+	}
+    }
+
+    return (eng.so[0] <= eng.eo[0] ? 0 : RE_NOMATCH);
+}
+
+int
+reerror(int ecode, const re_cod *preg, char *ebuffer, int ebuffer_size)
+{
+    static char *errors[] = {
+	"No error",
+	"Failed to match",			/* NOMATCH */
+
+	/* Errors not generated */
+	"Invalid regular expression",		/* BADPAT */
+	"Invalid collating element",		/* ECOLLATE */
+	"Invalid character class",		/* ECTYPE */
+
+	"`\' applied to unescapable character",	/* EESCAPE */
+	"Invalid backreference number",		/* ESUBREG */
+	"Brackets `[ ]' not balanced",		/* EBRACK */
+	"Parentheses `( )' not balanced",	/* EPAREN */
+	"Braces `{ }' not balanced",		/* EBRACE */
+	"Invalid repetition count(s) in `{ }'",	/* BADBR */
+	"Invalid character range in `[ ]'",	/* ERANGE */
+	"Out of memory",			/* ESPACE */
+	"`?', `*', or `+' operand invalid",	/* BADRPT */
+	"Empty (sub)expression",		/* EMPTY */
+	"Assertion error - you found a bug",	/* ASSERT */
+	"Invalid argument"			/* INVARG */
+    };
+    char *str;
+
+    if (ecode >= 0 && ecode < sizeof(errors) / sizeof(errors[0]))
+	str = errors[ecode];
+    else
+	str = "Unknown error";
+
+    return (snprintf(ebuffer, ebuffer_size, "%s", str));
+}
+
+void
+refree(re_cod *cod)
+{
+    free(cod->cod);
+    cod->cod = NULL;
+}
+
+static void
+reinit(void)
+{
+    int i;
+    static int first = 1;
+
+    if (!first)
+	return;
+    first = 0;
+
+    re__alnum['_'] = 1;
+
+    for (i = '0'; i <= '7'; i++)
+	re__alnum[i] = re__odigit[i] = re__ddigit[i] = re__xdigit[i] = 1;
+
+    for (; i <= '9'; i++)
+	re__alnum[i] = re__ddigit[i] = re__xdigit[i] = 1;
+
+    for (i = 'a'; i <= 'f'; i++)
+	re__alnum[i] = re__xdigit[i] = 1;
+    for (; i <= 'z'; i++)
+	re__alnum[i] = 1;
+
+    for (i = 'A'; i <= 'F'; i++)
+	re__alnum[i] = re__xdigit[i] = 1;
+    for (; i <= 'Z'; i++)
+	re__alnum[i] = 1;
+
+    for (i = 1; i < 32; i++)
+	re__control[i] = 1;
+    re__control[127] = 1;
+    /* Don't show tabs as control characters */
+    re__control['\t'] = 0;
+}
+
+static int
+rec_check(re_inf *inf, int count)
+{
+    if (inf->len + count >= inf->spc) {
+	int spc;
+	unsigned char *cod;
+
+	if ((spc = (count % 64)) != 0)
+	    spc = 64 - spc;
+	spc += count + inf->spc;
+	if ((cod = realloc(inf->cod, spc)) == NULL)
+	    return (inf->ecode = RE_ESPACE);
+	inf->cod = cod;
+	inf->spc = spc;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_code(re_inf *inf, ReCode code)
+{
+    if (rec_check(inf, 1) == 0)
+	inf->cod[inf->len++] = code;
+
+    return (inf->ecode);
+}
+
+static int
+rec_byte(re_inf *inf, int value)
+{
+    if (rec_check(inf, 1) == 0)
+	inf->cod[inf->len++] = value;
+
+    return (inf->ecode);
+}
+
+static int
+rec_code_byte(re_inf *inf, ReCode code, int value)
+{
+    if (rec_check(inf, 2) == 0) {
+	inf->cod[inf->len++] = code;
+	inf->cod[inf->len++] = value;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_length(re_inf *inf, int length)
+{
+    int lo, hi, two;
+
+    if (length >= 16384)
+	return (inf->ecode = RE_ESPACE);
+
+    lo = length & 0xff;
+    hi = length & 0xff00;
+    two = ((length > 0x7f) != 0) + 1;
+    if (two == 2) {
+	hi <<= 1;
+	hi |= (lo & 0x80) != 0;
+	lo |= 0x80;
+    }
+
+    if (rec_check(inf, two) == 0) {
+	inf->cod[inf->len++] = lo;
+	if (two == 2)
+	    inf->cod[inf->len++] = hi >> 8;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_byte_byte(re_inf *inf, int value0, int value1)
+{
+    if (rec_check(inf, 2) == 0) {
+	inf->cod[inf->len++] = value0;
+	inf->cod[inf->len++] = value1;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_code_byte_byte(re_inf *inf, ReCode code, int value0, int value1)
+{
+    if (rec_check(inf, 3) == 0) {
+	inf->cod[inf->len++] = code;
+	inf->cod[inf->len++] = value0;
+	inf->cod[inf->len++] = value1;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_build_alt(re_inf *inf, rec_alt *alt)
+{
+    int offset, value, bas = inf->bas + 1;
+
+    if (alt) {
+	if (alt->next) {
+	    if (rec_inc_spc(inf))
+		return (inf->ecode);
+
+	    /* A real a list of alternatives */
+	    rec_code(inf, Re_Alt);
+
+	    offset = inf->len;		/* Remember current offset */
+	    rec_byte_byte(inf, 0, 0);	/* Reserve two bytes for retry address */
+	    while (alt && inf->ecode == 0) {
+		if (rec_build_pat(inf, alt->pat))
+		    break;
+		alt = alt->next;
+		if (alt && inf->ecode == 0) {
+		    /* Handle (hyper)complex repetitions */
+		    if (inf->bas != bas) {
+			/* Duplicate patterns up to end of expression */
+			rec_build_pat(inf, inf->apat);
+			/* Restore engine state for next alternative(s) */
+			rec_alt_spc(inf, bas - 1);
+		    }
+
+		    /* If the jump would be so long */
+		    if ((value = inf->len - offset) >= 16384) {
+			inf->ecode = RE_ESPACE;
+			break;
+		    }
+		    inf->cod[offset] = value & 0xff;
+		    inf->cod[offset + 1] = (value & 0xff00) >> 8;
+
+		    rec_code(inf, Re_AltNext);
+		    offset = inf->len;
+		    rec_byte_byte(inf, 0, 0);
+		}
+	    }
+	    if (inf->ecode == 0) {
+		/* Handle (hyper)complex repetitions */
+		if (inf->bas != bas) {
+		    /* Duplicate patterns up to end of expression */
+		    rec_build_pat(inf, inf->apat);
+		    /* Restore engine state for next alternative(s) */
+		    rec_alt_spc(inf, bas - 1);
+		}
+
+		/* If the jump would be so long */
+		if ((value = inf->len - offset) >= 16384)
+		    return (inf->ecode = RE_ESPACE);
+		inf->cod[offset] = value & 0xff;
+		inf->cod[offset + 1] = (value & 0xff00) >> 8;
+		/* Last jump is here */
+		rec_code(inf, Re_AltDone);
+	    }
+	    rec_dec_spc(inf);
+	}
+	else
+	    /* Single alternative */
+	    rec_build_pat(inf, alt->pat);
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_build_pat(re_inf *inf, rec_pat *pat)
+{
+    rec_pat *apat;
+    int length, offset = 0, distance, jump = 0, bas = 0;
+
+    while (pat && inf->ecode == 0) {
+	if (pat->rep) {
+	    bas = inf->bas;
+	    if (pat->type == Rep_Group && !inf->par && rec_code(inf, Re_Open))
+		return (inf->ecode);
+	    if (rec_inc_spc(inf))
+		return (inf->ecode);
+	    offset = inf->len;
+	    if (rec_build_rep(inf, pat->rep))
+		break;
+	    /* Reserve space to jump after repetition done */
+	    jump = inf->len;
+	    rec_byte_byte(inf, 0, 0);
+	}
+	switch (pat->type) {
+	    case Rep_AnyAnyTimes:
+	    case Rep_AnyMaybe:
+	    case Rep_AnyAtLeast:
+		if (rec_add_spc(inf, pat->type == Rep_AnyMaybe))
+		    return (inf->ecode);
+		if (rec_code(inf, (ReCode)pat->type) == 0 &&
+		    rec_byte(inf, inf->bas - 1) == 0 &&
+		    rec_byte(inf, inf->ref - 1) == 0)
+		    rec_off_spc(inf);
+		break;
+	    case Rep_Literal:
+	    case Rep_LiteralNot:
+	    case Rep_SearchLiteral:
+		rec_code_byte(inf, (ReCode)pat->type, pat->data.chr);
+		break;
+	    case Rep_CaseLiteral:
+	    case Rep_CaseLiteralNot:
+	    case Rep_SearchCaseLiteral:
+		rec_code_byte_byte(inf, (ReCode)pat->type,
+				   pat->data.cse.lower, pat->data.cse.upper);
+		break;
+	    case Rep_Range:
+	    case Rep_RangeNot:
+		if (rec_code(inf, (ReCode)pat->type) == 0)
+		    rec_build_rng(inf, pat->data.rng);
+		break;
+	    case Rep_String:
+	    case Rep_SearchString:
+	    case Rep_CaseString:
+	    case Rep_SearchCaseString:
+		rec_code(inf, (ReCode)pat->type);
+		length = strlen((char*)pat->data.str);
+		if (rec_length(inf, length) == 0 && rec_check(inf, length) == 0) {
+		    memcpy(inf->cod + inf->len, pat->data.str, length);
+		    inf->len += length;
+		}
+		break;
+	    case Rep_Any:
+	    case Rep_AnyEatAnyTimes:
+	    case Rep_AnyEatMaybe:
+	    case Rep_AnyEatAtLeast:
+	    case Rep_Odigit:
+	    case Rep_OdigitNot:
+	    case Rep_Digit:
+	    case Rep_DigitNot:
+	    case Rep_Xdigit:
+	    case Rep_XdigitNot:
+	    case Rep_Space:
+	    case Rep_SpaceNot:
+	    case Rep_Tab:
+	    case Rep_Newline:
+	    case Rep_Lower:
+	    case Rep_Upper:
+	    case Rep_Alnum:
+	    case Rep_AlnumNot:
+	    case Rep_Control:
+	    case Rep_ControlNot:
+	    case Rep_Bol:
+	    case Rep_Eol:
+	    case Rep_Bow:
+	    case Rep_Eow:
+		rec_code(inf, (ReCode)pat->type);
+		break;
+	    case Rep_Backref:
+		rec_code_byte(inf, Re_Backref, pat->data.chr);
+		break;
+	    case Rep_Group:
+		if (pat->rep == NULL && !inf->par && rec_code(inf, Re_Open))
+		    break;
+		apat = inf->apat;
+		inf->apat = pat->next;
+		rec_build_grp(inf, pat->data.grp);
+		inf->apat = apat;
+		break;
+	    case Rep_StringList:
+		rec_build_stl(inf, pat->data.stl);
+		break;
+	}
+	if (pat->rep) {
+#if 0
+	    if (rec_dec_spc(inf))
+		return (inf->ecode);
+#else
+	    if (rec_rep_spc(inf, bas))
+		return (inf->ecode);
+#endif
+	    distance = inf->len - offset;
+	    if (distance > 255) {
+		if (rec_code(inf, Re_RepLongJump) ||
+		    rec_byte(inf, inf->bas) ||
+		    rec_byte(inf, distance & 0xff) ||
+		    rec_byte(inf, (distance & 0xff00) >> 8))
+		break;
+	    }
+	    else if (rec_code(inf, Re_RepJump) ||
+		     rec_byte(inf, inf->bas) ||
+		     rec_byte(inf, distance))
+		break;
+	    distance = inf->len - offset;
+	    inf->cod[jump] = distance & 0xff;
+	    inf->cod[jump + 1] = (distance & 0xff00) >> 8;
+	}
+	pat = pat->next;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_build_rng(re_inf *inf, rec_rng *rng)
+{
+    if (rec_check(inf, sizeof(rng->range)) == 0) {
+	memcpy(inf->cod + inf->len, rng->range, sizeof(rng->range));
+	inf->len += sizeof(rng->range);
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_build_grp(re_inf *inf, rec_grp *grp)
+{
+    int par = inf->par;
+
+    if (!(inf->flags & RE_NOSUB)) {
+	++inf->par;
+	if (par == 0)
+	    ++inf->ref;
+	if (rec_build_alt(inf, grp->alt) == 0) {
+	    if (par == 0) {
+		if (grp->comp)
+		    rec_code_byte(inf, Re_Update, inf->ref - 1);
+		else
+		    rec_code(inf, Re_Close);
+	    }
+	}
+	--inf->par;
+    }
+    else
+	rec_build_alt(inf, grp->alt);
+
+    return (inf->ecode);
+}
+
+static int
+rec_build_stl(re_inf *inf, rec_stl *stl)
+{
+    int i, len, rlen;
+    ReCode code;
+
+    /* Calculate jump distance information */
+    rlen = stl->tlen + stl->nstrs + 4;
+    /* + code + nstrs + place-offset + data-length */
+
+    if (stl->nstrs >= LARGE_STL_COUNT) {
+	rlen += 511;		/* Don't write number of strings */
+	code = stl->type == Rep_StringList ?
+		Re_LargeStringList : Re_LargeCaseStringList;
+    }
+    else
+	code = (ReCode)stl->type;
+
+    if (rlen >= 16386)
+	return (inf->ecode = RE_ESPACE);
+    if (rec_check(inf, rlen) ||
+	rec_code(inf, code))
+	return (inf->ecode);
+
+    /* Space is allocated, just write the data */
+    if (stl->nstrs < LARGE_STL_COUNT)
+	inf->cod[inf->len++] = stl->nstrs;
+
+    inf->cod[inf->len++] = rlen & 0xff;
+    inf->cod[inf->len++] = (rlen & 0xff00) >> 8;
+
+    if (stl->nstrs < LARGE_STL_COUNT) {
+	for (i = 0; i < stl->nstrs; i++)
+	    inf->cod[inf->len++] = stl->lens[i];
+	for (i = 0; i < stl->nstrs; i++) {
+	    len = stl->lens[i];
+	    if (len > 2) {
+		memcpy(inf->cod + inf->len, stl->strs[i], len);
+		inf->len += len;
+	    }
+	    else {
+		if (len == 1)
+		    inf->cod[inf->len++] = (long)stl->strs[i];
+		else {
+		    inf->cod[inf->len++] = (long)stl->strs[i] & 0xff;
+		    inf->cod[inf->len++] = ((long)stl->strs[i] & 0xff00) >> 8;
+		}
+	    }
+	}
+    }
+    else {
+	/* The string length goes before the string itself */
+	int j, chl, chu;
+
+	/* Fill everything with an invalid jump address */
+	memset(inf->cod + inf->len, 0xff, 512);
+	for (i = len = 0, j = -1; i < stl->nstrs; i++) {
+	    chl = stl->lens[i] > 2 ? stl->strs[i][0] : (long)stl->strs[i] & 0xff;
+	    if (chl != j) {
+		inf->cod[inf->len + (chl << 1)] = len & 0xff;
+		inf->cod[inf->len + (chl << 1) + 1] = (len & 0xff00) >> 8;
+		if (code == Re_LargeCaseStringList) {
+		    chu = stl->lens[i] > 2 ?
+			stl->strs[i][1] : ((long)(stl->strs[i]) & 0xff00) >> 8;
+		    inf->cod[inf->len + (chu << 1)] = len & 0xff;
+		    inf->cod[inf->len + (chu << 1) + 1] = (len & 0xff00) >> 8;
+		}
+		j = chl;
+	    }
+	    len += stl->lens[i] + 1;
+	}
+	inf->len += 512;
+
+	for (i = 0; i < stl->nstrs; i++) {
+	    len = stl->lens[i];
+	    inf->cod[inf->len++] = len;
+	    if (len > 2) {
+		memcpy(inf->cod + inf->len, stl->strs[i], len);
+		inf->len += len;
+	    }
+	    else {
+		if (len == 1)
+		    inf->cod[inf->len++] = (long)stl->strs[i];
+		else {
+		    inf->cod[inf->len++] = (long)stl->strs[i] & 0xff;
+		    inf->cod[inf->len++] = ((long)stl->strs[i] & 0xff00) >> 8;
+		}
+	    }
+	}
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_build_rep(re_inf *inf, rec_rep *rep)
+{
+    if (rep) {
+	switch (rep->type) {
+	    case Rer_AnyTimes:
+	    case Rer_AtLeast:
+	    case Rer_Maybe:
+		rec_code(inf, (ReCode)rep->type);
+		break;
+	    case Rer_Exact:
+		if (rec_code(inf, Re_Exact) == 0)
+		    rec_byte(inf, rep->mine);
+		break;
+	    case Rer_Min:
+		if (rec_code(inf, Re_Min) == 0)
+		    rec_byte(inf, rep->mine);
+		break;
+	    case Rer_Max:
+		if (rec_code(inf, Re_Max) == 0)
+		    rec_byte(inf, rep->maxc);
+		break;
+	    case Rer_MinMax:
+		if (rec_code(inf, Re_MinMax) == 0 &&
+		    rec_byte(inf, rep->mine) == 0)
+		    rec_byte(inf, rep->maxc);
+		break;
+	}
+	/* It is incremented in rec_build_pat */
+	rec_byte(inf, inf->bas - 1);
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_inc_spc(re_inf *inf)
+{
+    if (++inf->bas >= MAX_DEPTH)
+	return (inf->ecode = RE_ESPACE);
+
+    return (inf->ecode);
+}
+
+static int
+rec_dec_spc(re_inf *inf)
+{
+    if (--inf->bas < 0)
+	return (inf->ecode = RE_ASSERT);
+
+    return (inf->ecode);
+}
+
+static int
+rec_add_spc(re_inf *inf, int maybe)
+{
+    if (++inf->bas >= MAX_DEPTH)
+	return (inf->ecode = RE_ESPACE);
+    inf->sp[inf->bas] = maybe + 1;
+
+    return (inf->ecode);
+}
+
+/* Could be joined with rec_rep_spc, code almost identical */
+static int
+rec_alt_spc(re_inf *inf, int top)
+{
+    int distance, i, bas = inf->bas;
+
+    while ((inf->bas > top) && inf->sp[inf->bas]) {
+	/* Jump to this repetition for cleanup */
+	distance = inf->len - inf->sr[inf->bas];
+
+	/* This will generate a jump to a jump decision opcode */
+	inf->sj[inf->bas] = inf->len;
+
+	if (distance > 255) {
+	    if (rec_code(inf, Re_RepLongJump) ||
+		rec_byte(inf, inf->bas - 1) ||
+		rec_byte(inf, distance & 0xff) ||
+		rec_byte(inf, (distance & 0xff00) >> 8))
+	    break;
+	}
+	else if (rec_code(inf, Re_RepJump) ||
+		 rec_byte(inf, inf->bas - 1) ||
+		 rec_byte(inf, distance))
+ 	    break;
+
+	/* Top of stack value before repetition, or end condition value */
+	--inf->bas;
+    }
+
+    i = inf->bas + 1;
+
+    if (inf->ecode == 0 && i <= bas && inf->sp[i]) {
+	/*  Only the repetition at the bottom jump to code after testing
+	 * all possibilities */
+	distance = inf->len - inf->sr[i];
+	inf->cod[inf->sr[i] + 3] = distance & 0xff;
+	inf->cod[inf->sr[i] + 4] = (distance & 0xff00) >> 8;
+
+	/* The bottom jump is here */
+	if (rec_code(inf, inf->sp[i] == 1 ? Re_DoneIf : Re_MaybeDone))
+	   return (inf->ecode);
+
+	/*  Generate jumps to the previous special repetition */
+	for (++i; i <= bas; i++) {
+	    if (inf->sp[i]) {
+		distance = inf->sj[i] - inf->sr[i];
+		inf->cod[inf->sr[i] + 3] = distance & 0xff;
+		inf->cod[inf->sr[i] + 4] = (distance & 0xff00) >> 8;
+	    }
+	}
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_rep_spc(re_inf *inf, int top)
+{
+    int distance, i, bas = inf->bas;
+
+    while (inf->bas > top) {
+	if (inf->sp[inf->bas]) {
+	    /* Jump to this repetition for cleanup */
+	    distance = inf->len - inf->sr[inf->bas];
+
+	    /* This will generate a jump to a jump decision opcode */
+	    inf->sj[inf->bas] = inf->len;
+
+	    if (distance > 255) {
+		if (rec_code(inf, Re_RepLongJump) ||
+		    rec_byte(inf, inf->bas - 1) ||
+		    rec_byte(inf, distance & 0xff) ||
+		    rec_byte(inf, (distance & 0xff00) >> 8))
+		break;
+	    }
+	    else if (rec_code(inf, Re_RepJump) ||
+		     rec_byte(inf, inf->bas - 1) ||
+		     rec_byte(inf, distance))
+		break;
+	}
+
+	/* Top of stack value before repetition, or end condition value */
+	--inf->bas;
+    }
+
+    /* Find first special repetition offset. XXX This should be a noop */
+    for (i = 0; i < bas; i++)
+	if (inf->sp[i])
+	    break;
+
+    if (inf->ecode == 0 && i <= bas && inf->sp[i]) {
+	/*  Only the repetition at the bottom jump to code after testing
+	 * all possibilities */
+	distance = inf->len - inf->sr[i];
+	inf->cod[inf->sr[i] + 3] = distance & 0xff;
+	inf->cod[inf->sr[i] + 4] = (distance & 0xff00) >> 8;
+
+	/*  Generate jumps to the previous special repetition */
+	for (++i; i <= bas; i++) {
+	    if (inf->sp[i]) {
+		distance = inf->sj[i] - inf->sr[i];
+		inf->cod[inf->sr[i] + 3] = distance & 0xff;
+		inf->cod[inf->sr[i] + 4] = (distance & 0xff00) >> 8;
+	    }
+	}
+    }
+
+    return (inf->ecode);
+}
+
+static int
+rec_off_spc(re_inf *inf)
+{
+    /* The jump address before the three bytes instruction */
+    inf->sr[inf->bas] = inf->len - 3;
+    /*  Don't know yet where to go after done with the special
+     * repetition, just reserve two bytes for the jump address. */
+    return (rec_byte_byte(inf, 0, 0));
+}
+
+#ifdef DEBUG
+static void
+redump(re_cod *code)
+{
+    int i, j, k;
+    unsigned char *cod = code->cod, *stl;
+
+    if (cod[0] & RE_NOSUB)
+	printf("Nosub\n");
+    if (cod[0] & RE_NEWLINE)
+	printf("Newline\n");
+    ++cod;
+    if (cod[0] != 0xff)
+	printf("%d backrefs\n", cod[0] + 1);
+    ++cod;
+    for (;;) {
+	switch (*cod++) {
+	    case Re_Open:
+		printf("Open");
+		break;
+	    case Re_Close:
+		printf("Close");
+		break;
+	    case Re_Update:
+		printf("Update (%d)", (int)*cod++);
+		break;
+	    case Re_Alt:
+		printf("Alt");
+		i = cod[0] | cod[1];
+		cod += 2;
+		printf(" %d", i);
+		break;
+	    case Re_AltNext:
+		printf("Alt-next");
+		i = cod[0] | cod[1];
+		cod += 2;
+		printf(" %d", i);
+		break;
+	    case Re_AltDone:
+		printf("Alt-done");
+		break;
+	    case Re_AnyTimes:
+		printf("-> Anytimes %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_AnyEatAnyTimes:
+		printf("Any-eat-anytimes");
+		break;
+	    case Re_AnyAnyTimes:
+		printf("-> Any-anytimes %d", (int)*cod++);
+		printf(" (%d)", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_AnyEatMaybe:
+		printf("Any-eat-maybe");
+		break;
+	    case Re_AnyMaybe:
+		printf("-> Any-maybe %d", (int)*cod++);
+		printf(" (%d)", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_AnyAtLeast:
+		printf("-> Any-atleast %d", (int)*cod++);
+		printf(" (%d)", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_AnyEatAtLeast:
+		printf("Any-eat-atleast");
+		break;
+	    case Re_Maybe:
+		printf("-> Maybe %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_AtLeast:
+		printf("-> Atleast %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_Exact:
+		printf("-> Exact ");
+		i = *cod++;
+		printf("%d", i);
+		printf(" %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_Min:
+		printf("-> Min ");
+		i = *cod++;
+		printf("%d", i);
+		printf(" %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_Max:
+		printf("-> Max ");
+		i = *cod++;
+		printf("%d", i);
+		printf(" %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_MinMax:
+		printf("-> Min-max ");
+		i = *cod++;
+		printf("%d ", i);
+		i = *cod++;
+		printf("%d", i);
+		printf(" %d", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		cod += 2;
+		printf(" /%d", i);
+		break;
+	    case Re_RepJump:
+		printf("<- Rep-jump %d ", (int)*cod++);
+		i = *cod++;
+		printf("%d", i);
+		break;
+	    case Re_RepLongJump:
+		printf("<- Rep-long-jump %d ", (int)*cod++);
+		i = cod[0] | (cod[1] << 8);
+		printf("%d", i);
+		break;
+	    case Re_Any:
+		printf("Any");
+		break;
+	    case Re_Odigit:
+		printf("Odigit");
+		break;
+	    case Re_OdigitNot:
+		printf("Odigit-not");
+		break;
+	    case Re_Digit:
+		printf("Digit");
+		break;
+	    case Re_DigitNot:
+		printf("Digit-not");
+		break;
+	    case Re_Xdigit:
+		printf("Xdigit");
+		break;
+	    case Re_XdigitNot:
+		printf("Xdigit-not");
+		break;
+	    case Re_Space:
+		printf("Space");
+		break;
+	    case Re_SpaceNot:
+		printf("Space-not");
+		break;
+	    case Re_Tab:
+		printf("Tab");
+		break;
+	    case Re_Newline:
+		printf("Newline");
+		break;
+	    case Re_Lower:
+		printf("Lower");
+		break;
+	    case Re_Upper:
+		printf("Upper");
+		break;
+	    case Re_Alnum:
+		printf("Alnum");
+		break;
+	    case Re_AlnumNot:
+		printf("Alnum-not");
+		break;
+	    case Re_Control:
+		printf("Control");
+		break;
+	    case Re_ControlNot:
+		printf("Control-not");
+		break;
+	    case Re_Bol:
+		printf("Bol");
+		break;
+	    case Re_Eol:
+		printf("Eol");
+		break;
+	    case Re_Bow:
+		printf("Bow");
+		break;
+	    case Re_Eow:
+		printf("Eow");
+		break;
+	    case Re_Range:
+		printf("Range ");
+		goto range;
+	    case Re_RangeNot:
+		printf("Range-not ");
+range:
+		for (i = 0; i < 256; i += 32) {
+		    for (j = k = 0; j < 32; j++)
+			k |= (*cod++ & 1) << (31 - j);
+		    printf("%x ", k);
+		}
+		break;
+	    case Re_Literal:
+		printf("Literal %c", *cod++);
+		break;
+	    case Re_LiteralNot:
+		printf("Literal-not %c", *cod++);
+		break;
+	    case Re_SearchLiteral:
+		printf("Search-literal %c", *cod++);
+		break;
+	    case Re_CaseLiteral:
+		printf("Case-literal %c", *cod++);
+		putchar(*cod++);
+		break;
+	    case Re_CaseLiteralNot:
+		printf("Case-literal-not %c", *cod++);
+		putchar(*cod++);
+		break;
+	    case Re_SearchCaseLiteral:
+		printf("Search-case-literal %c", *cod++);
+		putchar(*cod++);
+		break;
+	    case Re_String:
+		printf("String ");
+		goto string;
+	    case Re_SearchString:
+		printf("Search-string ");
+		goto string;
+	    case Re_CaseString:
+		printf("Case-string ");
+		goto string;
+	    case Re_SearchCaseString:
+		printf("Search-case-string ");
+string:
+		i = *cod++;
+		if (i & 0x80)
+		    i = (i & 0x7f) | (*cod++ << 7);
+		for (j = 0; j < i; j++)
+		    putchar(*cod++);
+		break;
+	    case Re_StringList:
+		printf("String-list");
+		goto string_list;
+	    case Re_CaseStringList:
+		printf("Case-string-list");
+string_list:
+		j = *cod++;
+		cod += 2;
+		stl = cod + j;
+		for (i = 0; i < j; i++) {
+		    k = *cod++;
+		    putchar(i ? ',' : ' ');
+		    fwrite(stl, k, 1, stdout);
+		    stl += k;
+		}
+		cod = stl;
+		break;
+	    case Re_LargeStringList:
+		printf("Large-string-list");
+large_string_list:
+		i = cod[0] | (cod[1] << 8);
+		stl = cod + i - 1;
+		for (i = 0, cod += 514; cod < stl; i++) {
+		    k = *cod++;
+		    putchar(i ? ',' : ' ');
+		    fwrite(cod, k, 1, stdout);
+		    cod += k;
+		}
+		cod = stl;
+		break;
+	    case Re_LargeCaseStringList:
+		printf("Large-case-string-list");
+		goto large_string_list;
+	    case Re_Backref:
+		printf("Backref %d", (int)*cod++);
+		break;
+	    case Re_DoneIf:
+		printf("Done-if");
+		break;
+	    case Re_MaybeDone:
+		printf("Maybe-done");
+		break;
+	    case Re_Done:
+		printf("Done\n");
+		return;
+	}
+	putchar('\n');
+    }
+}
+#endif
diff --git a/lisp/re/re.h b/lisp/re/re.h
new file mode 100644
index 0000000..332366e
--- /dev/null
+++ b/lisp/re/re.h
@@ -0,0 +1,123 @@
+/*
+ * Copyright (c) 2002 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ *
+ * Author: Paulo César Pereira de Andrade
+ */
+
+/* $XFree86: xc/programs/xedit/lisp/re/re.h,v 1.2 2002/09/23 01:25:41 paulo Exp $ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+
+#ifndef _re_h
+#define _re_h
+
+/*
+ * Defines
+ */
+
+	/* Compile flags options */
+#define REG_BASIC		0000	/* Not used */
+#define REG_EXTENDED		0001	/* Not used, only extended supported */
+
+#define RE_ICASE		0002
+#define RE_NOSUB		0004
+#define RE_NEWLINE		0010
+#define RE_NOSPEC		0020
+#define RE_PEND			0040
+#define RE_DUMP			0200
+
+
+
+	/* Execute flag options */
+#define RE_NOTBOL		1
+#define RE_NOTEOL		2
+#define RE_STARTEND		4
+#define RE_TRACE		00400	/* Not used/supported */
+#define RE_LARGE		01000	/* Not used/supported */
+#define RE_BACKR		02000	/* Not used/supported */
+
+	/* Value returned by reexec when match fails */
+#define RE_NOMATCH		1
+	/* Compile error values */
+#define RE_BADPAT		2
+#define RE_ECOLLATE		3
+#define RE_ECTYPE		4
+#define RE_EESCAPE		5
+#define RE_ESUBREG		6
+#define RE_EBRACK		7
+#define RE_EPAREN		8
+#define RE_EBRACE		9
+#define RE_EBADBR		10
+#define RE_ERANGE		11
+#define RE_ESPACE		12
+#define RE_BADRPT		13
+#define RE_EMPTY		14
+#define RE_ASSERT		15
+#define RE_INVARG		16
+#define RE_ATOI			255	/* Not used/supported */
+#define RE_ITOA			0400	/* Not used/supported */
+
+
+/*
+ * Types
+ */
+
+/* (re)gular expression (mat)ch result */
+typedef struct _re_mat {
+    long rm_so;
+    long rm_eo;
+} re_mat;
+
+/* (re)gular expression (cod)e */
+typedef struct _re_cod {
+    unsigned char *cod;
+    int re_nsub;		/* Public member */
+    const char *re_endp;	/* Support for RE_PEND */
+} re_cod;
+
+
+/*
+ * Prototypes
+ */
+	/* compile the given pattern string
+	 * returns 0 on success, error code otherwise */
+int recomp(re_cod *preg, const char *pattern, int flags);
+
+	/* execute the compiled pattern on the string.
+	 * returns 0 if matched, RE_NOMATCH if failed, error code otherwise */
+int reexec(const re_cod *preg, const char *string,
+	   int nmat, re_mat pmat[], int flags);
+
+	/* formats an error message for the given code in ebuffer */
+int reerror(int ecode, const re_cod *preg, char *ebuffer, int ebuffer_size);
+
+	/* frees the given parameter */
+void refree(re_cod *preg);
+
+
+#endif /* _re_h */
diff --git a/lisp/re/rec.c b/lisp/re/rec.c
new file mode 100644
index 0000000..20f9fd9
--- /dev/null
+++ b/lisp/re/rec.c
@@ -0,0 +1,1015 @@
+/*
+ * Copyright (c) 2002 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ *
+ * Author: Paulo César Pereira de Andrade
+ */
+
+/* $XFree86: xc/programs/xedit/lisp/re/rec.c,v 1.4 2003/01/16 06:25:52 paulo Exp $ */
+
+#include "rep.h"
+
+/*
+ * Types
+ */
+
+/*  Information used while compiling the intermediate format of the re. */
+typedef struct _irec_info {
+    unsigned char *ptr;		/* Pointer in the given regex pattern */
+    unsigned char *end;		/* End of regex pattern */
+    int flags;			/* Compile flags */
+    rec_alt *alt;		/* Toplevel first/single alternative */
+
+    rec_alt *palt;		/* Current alternative being compiled */
+    rec_grp *pgrp;		/* Current group, if any */
+    rec_pat *ppat;		/* Current pattern, if any */
+
+    /*  Number of open parenthesis, for error checking */
+    int nparens;
+
+    int ngrps;			/* Number of groups, for backreference */
+
+    int ecode;
+} irec_info;
+
+
+/*
+ * Prototypes
+ */
+
+	/* (i)ntermediate (r)egular (e)xpression (c)ompile
+	 *  Generates an intermediate stage compiled regex from
+	 * the specified pattern argument. Basically builds an
+	 * intermediate data structure to analyse and do syntax
+	 * error checking.
+	 */
+static void irec_simple_pattern(irec_info*, rec_pat_t);
+static void irec_literal_pattern(irec_info*, int);
+static void irec_case_literal_pattern(irec_info*, int);
+static void irec_open_group(irec_info*);
+static void irec_close_group(irec_info*);
+static void irec_range(irec_info*);
+static void irec_range_single(irec_info*, int);
+static void irec_range_complex(irec_info*, int, int);
+static void irec_escape(irec_info*);
+static void irec_simple_repetition(irec_info*, rec_rep_t);
+static void irec_complex_repetition(irec_info*);
+static void irec_add_repetition(irec_info*, rec_rep*);
+static void irec_free(irec_info*);
+static void irec_free_grp(rec_grp*);
+static void irec_free_pats(rec_pat*);
+
+
+/*
+ * Implementation
+ */
+rec_alt *
+irec_comp(const char *pattern, const char *endp, int flags, int *ecode)
+{
+    unsigned char *ptr;
+    rec_alt *alt;
+    irec_info inf;
+
+    if (pattern == NULL || endp < pattern) {
+	*ecode = RE_INVARG;
+	return (NULL);
+    }
+
+    if (endp == pattern) {
+	*ecode = RE_EMPTY;
+	return (NULL);
+    }
+
+    alt = calloc(1, sizeof(rec_alt));
+    if (alt == NULL) {
+	*ecode = RE_ESPACE;
+	return (NULL);
+    }
+
+    inf.ptr = (unsigned char*)pattern;
+    inf.end = (unsigned char*)endp;
+    inf.flags = flags;
+    inf.alt = inf.palt = alt;
+    inf.pgrp = NULL;
+    inf.ppat = NULL;
+    inf.nparens = inf.ngrps = 0;
+    inf.ecode = 0;
+
+    if (flags & RE_NOSPEC) {
+	/* Just searching for a character or substring */
+	for (; inf.ecode == 0 && inf.ptr < inf.end; inf.ptr++) {
+	    if (!(flags & RE_ICASE) ||
+		(!isupper(*inf.ptr) && !islower(*inf.ptr)))
+		irec_literal_pattern(&inf, *inf.ptr);
+	    else
+		irec_case_literal_pattern(&inf, *inf.ptr);
+	}
+    }
+    /* inf.ptr = inf.end is nul if flags & RE_NOSPEC */
+    for (; inf.ecode == 0 && inf.ptr < inf.end;) {
+	switch (*inf.ptr++) {
+	    case '*':
+		irec_simple_repetition(&inf, Rer_AnyTimes);
+		break;
+	    case '+':
+		irec_simple_repetition(&inf, Rer_AtLeast);
+		break;
+	    case '?':
+		irec_simple_repetition(&inf, Rer_Maybe);
+		break;
+	    case '.':
+		irec_simple_pattern(&inf, Rep_Any);
+		break;
+	    case '^':
+		if (flags & RE_NEWLINE)
+		    /* It is up to the user decide if this can match */
+		    irec_simple_pattern(&inf, Rep_Bol);
+		else {
+		    for (ptr = inf.ptr - 1;
+			 ptr > (unsigned char*)pattern && *ptr == '('; ptr--)
+			;
+		    /* If at the start of a pattern */
+		    if (ptr == (unsigned char*)pattern || *ptr == '|')
+			irec_simple_pattern(&inf, Rep_Bol);
+		    else
+			/* In the middle of a pattern, treat as literal */
+			irec_literal_pattern(&inf, '^');
+		}
+		break;
+	    case '$':
+		if (flags & RE_NEWLINE)
+		    irec_simple_pattern(&inf, Rep_Eol);
+		else {
+		    /* Look ahead to check if is the last char of a group */
+		    for (ptr = inf.ptr; ptr < inf.end && *ptr == ')'; ptr++)
+			;
+		    if (*ptr == '\0' || *ptr == '|')
+			/* Last character of pattern, an EOL match */
+			irec_simple_pattern(&inf, Rep_Eol);
+		    else
+			/* Normal character */
+			irec_literal_pattern(&inf, '$');
+		}
+		break;
+	    case '(':
+		irec_open_group(&inf);
+		break;
+	    case ')':
+		/* Look ahead to check if need to close the group now */
+		ptr = inf.ptr;
+		if (*ptr != '*' && *ptr != '+' && *ptr != '?' && *ptr != '{')
+		    /* If a repetition does not follow */
+		    irec_close_group(&inf);
+		else if (inf.pgrp == NULL)
+		    /* A repetition follows, but current group is implicit */
+		    inf.ecode = RE_EPAREN;
+		else
+		    /* Can do this as next character is known */
+		    inf.ppat = NULL;
+		break;
+	    case '[':
+		irec_range(&inf);
+		break;
+	    case ']':
+		irec_literal_pattern(&inf, ']');
+		break;
+	    case '{':
+		irec_complex_repetition(&inf);
+		break;
+	    case '}':
+		irec_literal_pattern(&inf, '}');
+		break;
+	    case '|':
+		    /* If first character in the pattern */
+		if (inf.ptr - 1 == (unsigned char*)pattern ||
+		    /* If last character in the pattern */
+		    inf.ptr >= inf.end ||
+		    /* If empty pattern */
+		    inf.ptr[0] == '|' ||
+		    inf.ptr[0] == ')')
+		    inf.ecode = RE_EMPTY;
+		else {
+		    rec_alt *alt = calloc(1, sizeof(rec_alt));
+
+		    if (alt) {
+			alt->prev = inf.palt;
+			inf.palt->next = alt;
+			inf.palt = alt;
+			inf.ppat = NULL;
+		    }
+		    else
+			inf.ecode = RE_ESPACE;
+		}
+		break;
+	    case '\\':
+		irec_escape(&inf);
+		break;
+	    default:
+		if (!(flags & RE_ICASE) ||
+		    (!isupper(inf.ptr[-1]) && !islower(inf.ptr[-1])))
+		    irec_literal_pattern(&inf, inf.ptr[-1]);
+		else
+		    irec_case_literal_pattern(&inf, inf.ptr[-1]);
+		break;
+	}
+    }
+
+    /* Check if not all groups closed */
+    if (inf.ecode == 0 && inf.nparens)
+	inf.ecode = RE_EPAREN;
+
+    if (inf.ecode == 0)
+	inf.ecode = orec_comp(inf.alt, flags);
+
+    /* If an error generated */
+    if (inf.ecode) {
+	irec_free(&inf);
+	alt = NULL;
+    }
+
+    *ecode = inf.ecode;
+
+    return (alt);
+}
+
+void
+irec_free_alt(rec_alt *alt)
+{
+    rec_alt *next;
+
+    while (alt) {
+	next = alt->next;
+	irec_free_pats(alt->pat);
+	free(alt);
+	alt = next;
+    }
+}
+
+
+
+static void
+irec_simple_pattern(irec_info *inf, rec_pat_t type)
+{
+    rec_pat *pat;
+
+    /* Always add a new pattern to list */
+    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    pat->type = type;
+    if ((pat->prev = inf->ppat) != NULL)
+	inf->ppat->next = pat;
+    else
+	inf->palt->pat = pat;
+    inf->ppat = pat;
+}
+
+static void
+irec_literal_pattern(irec_info *inf, int value)
+{
+    int length;
+    rec_pat *pat;
+    unsigned char chr, *str;
+
+	/* If there is a current pattern */
+    if (inf->ppat && inf->ppat->rep == NULL) {
+	switch (inf->ppat->type) {
+	    case Rep_Literal:
+		/* Start literal string */
+		chr = inf->ppat->data.chr;
+		if ((str = malloc(16)) == NULL) {
+		    inf->ecode = RE_ESPACE;
+		    return;
+		}
+		inf->ppat->type = Rep_String;
+		inf->ppat->data.str = str;
+		str[0] = chr;
+		str[1] = value;
+		str[2] = '\0';
+		return;
+
+	    case Rep_String:
+		/* Augments literal string */
+		length = strlen((char*)inf->ppat->data.str);
+		if ((length % 16) >= 14) {
+		    if ((str = realloc(inf->ppat->data.str,
+				       length + 18)) == NULL) {
+			inf->ecode = RE_ESPACE;
+			return;
+		    }
+		    inf->ppat->data.str = str;
+		}
+		inf->ppat->data.str[length] = value;
+		inf->ppat->data.str[length + 1] = '\0';
+		return;
+
+	    default:
+		/* Anything else is added as a new pattern list element */
+		break;
+	}
+    }
+
+    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    pat->type = Rep_Literal;
+    pat->data.chr = value;
+    if ((pat->prev = inf->ppat) != NULL)
+	inf->ppat->next = pat;
+    else
+	inf->palt->pat = pat;
+    inf->ppat = pat;
+}
+
+static void
+irec_case_literal_pattern(irec_info *inf, int value)
+{
+    int length;
+    rec_pat *pat;
+    unsigned char plower, pupper, lower, upper, *str;
+
+    lower = tolower(value);
+    upper = toupper(value);
+
+	/* If there is a current pattern */
+    if (inf->ppat && inf->ppat->rep == NULL) {
+	switch (inf->ppat->type) {
+	    case Rep_CaseLiteral:
+		/* Start case literal string */
+		plower = inf->ppat->data.cse.lower;
+		pupper = inf->ppat->data.cse.upper;
+		if ((str = malloc(32)) == NULL) {
+		    inf->ecode = RE_ESPACE;
+		    return;
+		}
+		inf->ppat->type = Rep_CaseString;
+		inf->ppat->data.str = str;
+		str[0] = plower;
+		str[1] = pupper;
+		str[2] = lower;
+		str[3] = upper;
+		str[4] = '\0';
+		return;
+
+	    case Rep_CaseString:
+		/* Augments case literal string */
+		length = strlen((char*)inf->ppat->data.str);
+		if (((length) % 32) >= 28) {
+		    if ((str = realloc(inf->ppat->data.str,
+				       length + 36)) == NULL) {
+			inf->ecode = RE_ESPACE;
+			return;
+		    }
+		    inf->ppat->data.str = str;
+		}
+		inf->ppat->data.str[length] = lower;
+		inf->ppat->data.str[length + 1] = upper;
+		inf->ppat->data.str[length + 2] = '\0';
+		return;
+
+	    default:
+		/* Anything else is added as a new pattern list element */
+		break;
+	}
+    }
+
+    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    pat->type = Rep_CaseLiteral;
+    pat->data.cse.lower = lower;
+    pat->data.cse.upper = upper;
+    pat->prev = inf->ppat;
+    if ((pat->prev = inf->ppat) != NULL)
+	inf->ppat->next = pat;
+    else
+	inf->palt->pat = pat;
+    inf->ppat = pat;
+}
+
+static void
+irec_open_group(irec_info *inf)
+{
+    rec_pat *pat;
+    rec_alt *alt;
+    rec_grp *grp;
+
+    if ((grp = calloc(1, sizeof(rec_grp))) == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+	free(grp);
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    if ((alt = calloc(1, sizeof(rec_alt))) == NULL) {
+	free(grp);
+	free(pat);
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    pat->type = Rep_Group;
+    pat->data.grp = grp;
+    grp->parent = pat;
+    grp->palt = inf->palt;
+    grp->pgrp = inf->pgrp;
+    grp->alt = alt;
+    grp->comp = 0;
+    if ((pat->prev = inf->ppat) != NULL)
+	inf->ppat->next = pat;
+    else
+	inf->palt->pat = pat;
+    inf->palt = alt;
+    inf->ppat = NULL;
+
+    /* Only toplevel parenthesis supported */
+    if (++inf->nparens == 1)
+	++inf->ngrps;
+
+    inf->pgrp = grp;
+}
+
+static void
+irec_close_group(irec_info *inf)
+{
+    if (inf->pgrp == NULL) {
+	inf->ecode = RE_EPAREN;
+	return;
+    }
+
+    inf->palt = inf->pgrp->palt;
+    inf->ppat = inf->pgrp->parent;
+    inf->pgrp = inf->pgrp->pgrp;
+
+    --inf->nparens;
+}
+
+static void
+irec_range(irec_info *inf)
+{
+    int count;
+    rec_pat *pat;
+    rec_rng *rng;
+    int not = inf->ptr[0] == '^';
+
+    if (not)
+	++inf->ptr;
+
+    pat = calloc(1, sizeof(rec_pat));
+    if (pat == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    rng = calloc(1, sizeof(rec_rng));
+    if (pat == NULL) {
+	free(pat);
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    pat->data.rng = rng;
+    pat->type = not ? Rep_RangeNot : Rep_Range;
+    if ((pat->prev = inf->ppat) != NULL)
+	inf->ppat->next = pat;
+    else
+	inf->palt->pat = pat;
+    inf->ppat = pat;
+
+    /* First pass, add everything seen */
+    for (count = 0; inf->ecode == 0; count++) {
+	/* If bracket not closed */
+	if (inf->ptr == inf->end) {
+	    inf->ecode = RE_EBRACK;
+	    return;
+	}
+	/* If not the first character */
+	else if (inf->ptr[0] == ']' && count)
+	    break;
+	else {
+	    /* If not a range of characters */
+	    if (inf->ptr[1] != '-' || inf->ptr[2] == ']') {
+		irec_range_single(inf, inf->ptr[0]);
+		++inf->ptr;
+	    }
+	    else {
+		if ((inf->flags & RE_NEWLINE) &&
+		    inf->ptr[0] < '\n' && inf->ptr[2] > '\n') {
+		    /*  Unless it is forced to be a delimiter, don't allow
+		     * a newline in a character range */
+		    if (inf->ptr[0] == '\n' - 1)
+			irec_range_single(inf, inf->ptr[0]);
+		    else
+			irec_range_complex(inf, inf->ptr[0], '\n' - 1);
+		    if (inf->ptr[2] == '\n' + 1)
+			irec_range_single(inf, inf->ptr[2]);
+		    else
+			irec_range_complex(inf, '\n' + 1, inf->ptr[2]);
+		}
+		else
+		    irec_range_complex(inf, inf->ptr[0], inf->ptr[2]);
+		inf->ptr += 3;
+	    }
+	}
+    }
+
+    /* Skip ] */
+    ++inf->ptr;
+}
+
+static void
+irec_range_single(irec_info *inf, int value)
+{
+    if (value >= 0 && value <= 255)
+	inf->ppat->data.rng->range[value] = 1;
+
+    if (inf->flags & RE_ICASE) {
+	if (islower(value)) {
+	    value = toupper(value);
+	    if (value >= 0 && value <= 255)
+		inf->ppat->data.rng->range[value] = 1;
+	}
+	else if (isupper(value)) {
+	    value = tolower(value);
+	    if (value >= 0 && value <= 255)
+		inf->ppat->data.rng->range[value] = 1;
+	}
+    }
+}
+
+static void
+irec_range_complex(irec_info *inf, int chrf, int chrt)
+{
+    if (chrf > chrt) {
+	inf->ecode = RE_ERANGE;
+	return;
+    }
+
+    for (; chrf <= chrt; chrf++)
+	irec_range_single(inf, chrf);
+}
+
+static void
+irec_escape(irec_info *inf)
+{
+    rec_pat *pat;
+    unsigned char chr = inf->ptr[0];
+
+    if (chr == 0) {
+	inf->ecode = RE_EESCAPE;
+	return;
+    }
+    ++inf->ptr;
+    switch (chr) {
+	case 'o':
+	    irec_simple_pattern(inf, Rep_Odigit);
+	    break;
+	case 'O':
+	    irec_simple_pattern(inf, Rep_OdigitNot);
+	    break;
+	case 'd':
+	    irec_simple_pattern(inf, Rep_Digit);
+	    break;
+	case 'D':
+	    irec_simple_pattern(inf, Rep_DigitNot);
+	    break;
+	case 'x':
+	    irec_simple_pattern(inf, Rep_Xdigit);
+	    break;
+	case 'X':
+	    irec_simple_pattern(inf, Rep_XdigitNot);
+	    break;
+	case 's':
+	    irec_simple_pattern(inf, Rep_Space);
+	    break;
+	case 'S':
+	    irec_simple_pattern(inf, Rep_SpaceNot);
+	    break;
+	case 't':
+	    irec_simple_pattern(inf, Rep_Tab);
+	    break;
+	case 'n':
+	    irec_simple_pattern(inf, Rep_Newline);
+	    break;
+	case 'l':
+	    irec_simple_pattern(inf, Rep_Lower);
+	    break;
+	case 'u':
+	    irec_simple_pattern(inf, Rep_Upper);
+	    break;
+	case 'w':
+	    irec_simple_pattern(inf, Rep_Alnum);
+	    break;
+	case 'W':
+	    irec_simple_pattern(inf, Rep_AlnumNot);
+	    break;
+	case 'c':
+	    irec_simple_pattern(inf, Rep_Control);
+	    break;
+	case 'C':
+	    irec_simple_pattern(inf, Rep_ControlNot);
+	    break;
+	case '<':
+	    irec_simple_pattern(inf, Rep_Bow);
+	    break;
+	case '>':
+	    irec_simple_pattern(inf, Rep_Eow);
+	    break;
+	case '1':	case '2':	case '3':
+	case '4':	case '5':	case '6':
+	case '7':	case '8':	case '9':
+	    if ((inf->flags & RE_NOSUB) || (chr -= '1') >= inf->ngrps) {
+		inf->ecode = RE_ESUBREG;
+		return;
+	    }
+	    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+		inf->ecode = RE_ESPACE;
+		return;
+	    }
+	    pat->type = Rep_Backref;
+	    pat->data.chr = chr;
+	    pat->prev = inf->ppat;
+	    if (inf->ppat)
+		inf->ppat->next = pat;
+	    else
+		inf->palt->pat = pat;
+	    inf->ppat = pat;
+	    break;
+
+	/* True literals */
+	case '0':
+	    irec_literal_pattern(inf, '\0');
+	    break;
+	case 'a':
+	    irec_literal_pattern(inf, '\a');
+	    break;
+	case 'b':
+	    irec_literal_pattern(inf, '\b');
+	    break;
+	case 'f':
+	    irec_literal_pattern(inf, '\f');
+	    break;
+	case 'r':
+	    irec_literal_pattern(inf, '\r');
+	    break;
+	case 'v':
+	    irec_literal_pattern(inf, '\v');
+	    break;
+
+	default:
+	    /* Don't check if case insensitive regular expression */
+	    irec_literal_pattern(inf, chr);
+	    break;
+    }
+}
+
+static void
+irec_simple_repetition(irec_info *inf, rec_rep_t type)
+{
+    rec_rep *rep;
+
+	/* If nowhere to add repetition */
+    if ((inf->pgrp == NULL && inf->ppat == NULL) ||
+	/* If repetition already added to last/current pattern */
+	(inf->pgrp == NULL && inf->ppat->rep != NULL) ||
+	/* If repetition already added to last/current group */
+	(inf->ppat == NULL && inf->pgrp->parent->rep != NULL)) {
+	inf->ecode = RE_BADRPT;
+	return;
+    }
+
+    if ((rep = calloc(1, sizeof(rec_rep))) == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+    rep->type = type;
+    irec_add_repetition(inf, rep);
+}
+
+static void
+irec_complex_repetition(irec_info *inf)
+{
+    int exact;
+    rec_rep *rep;
+    long mine, maxc;
+    unsigned char *end;
+
+	/* If nowhere to add repetition */
+    if ((inf->pgrp == NULL && inf->ppat == NULL) ||
+	/* If repetition already added to last/current pattern */
+	(inf->pgrp == NULL && inf->ppat->rep != NULL) ||
+	/* If repetition already added to last/current group */
+	(inf->ppat == NULL && inf->pgrp->parent->rep != NULL)) {
+	inf->ecode = RE_EBADBR;
+	return;
+    }
+
+    exact = 0;
+    mine = maxc = -1;
+    if (inf->ptr[0] == ',')
+	/* Specify max number of ocurrences only */
+	goto domax;
+    else if (!isdigit(inf->ptr[0]))
+	goto badbr;
+
+    mine = strtol((char*)inf->ptr, (char**)&end, 10);
+    inf->ptr = end;
+    if (inf->ptr[0] == '}') {
+	exact = 1;
+	++inf->ptr;
+	goto redone;
+    }
+    else if (inf->ptr[0] != ',')
+	goto badbr;
+
+domax:
+	/* Add one to skip comma */
+    ++inf->ptr;
+    if (inf->ptr[0] == '}') {
+	++inf->ptr;
+	goto redone;
+    }
+    else if (!isdigit(inf->ptr[0]))
+	goto badbr;
+    maxc = strtol((char*)inf->ptr, (char**)&end, 10);
+    inf->ptr = end;
+    if (inf->ptr[0] != '}')
+	goto badbr;
+    ++inf->ptr;
+
+redone:
+    if (mine == maxc) {
+	maxc = -1;
+	exact = 1;
+    }
+
+    /* Check range and if min-max parameters are valid */
+    if (mine >= 255 || maxc >= 255 ||
+	(mine >= 0 && maxc >= 0 && mine > maxc))
+	goto badbr;
+
+    /* Check for noop */
+    if (exact && mine == 1)
+	return;
+
+    if ((rep = calloc(1, sizeof(rec_rep))) == NULL) {
+	inf->ecode = RE_ESPACE;
+	return;
+    }
+
+	/* Convert {0,1} to ? */
+    if (mine == 0 && maxc == 1)
+	rep->type = Rer_Maybe;
+    else if (exact) {
+	rep->type = Rer_Exact;
+	rep->mine = mine;
+    }
+	/* Convert {0,} to * */
+    else if (mine == 0 && maxc == -1)
+	rep->type = Rer_AnyTimes;
+	/* Convert {1,} to + */
+    else if (mine == 1 && maxc == -1)
+	rep->type = Rer_AtLeast;
+    else if (maxc == -1) {
+	rep->type = Rer_Min;
+	rep->mine = mine;
+    }
+    else if (mine < 1) {
+	rep->type = Rer_Max;
+	rep->maxc = maxc;
+    }
+    else {
+	rep->type = Rer_MinMax;
+	rep->mine = mine;
+	rep->maxc = maxc;
+    }
+
+    irec_add_repetition(inf, rep);
+
+    return;
+
+badbr:
+    inf->ecode = RE_EBADBR;
+}
+
+/*  The rep argument is allocated and has no reference yet,
+ * if something fails it must be freed before returning.
+ */
+static void
+irec_add_repetition(irec_info *inf, rec_rep *rep)
+{
+    int length;
+    rec_pat *pat;
+    rec_grp *grp;
+    rec_rep_t rept;
+    unsigned char value, upper;
+
+    rept = rep->type;
+
+    if (inf->ppat == NULL) {
+	rec_pat *any;
+	rec_grp *grp = inf->pgrp;
+
+	if (rept == Rer_AnyTimes || rept == Rer_Maybe || rept == Re_AtLeast) {
+	    /* Convert (.)* to (.*), ((.))* not handled and may not match */
+	    any = NULL;
+
+	    if (grp->alt && grp->alt->pat) {
+		for (any = grp->alt->pat; any->next; any = any->next)
+		    ;
+		switch (any->type) {
+		    case Rep_Any:
+			break;
+		    case Rep_AnyAnyTimes:
+		    case Rep_AnyMaybe:
+		    case Rep_AnyAtLeast:
+			free(rep);
+			inf->ecode = RE_BADRPT;
+			return;
+		    default:
+			any = NULL;
+			break;
+		}
+	    }
+	    if (any) {
+		free(rep);
+		rep = NULL;
+		any->type = (rept == Rer_AnyTimes) ? Rep_AnyAnyTimes :
+			    (rept == Rer_AtLeast) ? Rep_AnyAtLeast :
+			    Rep_AnyMaybe;
+		while (grp) {
+		    ++grp->comp;
+		    grp = grp->pgrp;
+		}
+	    }
+	}
+	inf->pgrp->parent->rep = rep;
+	irec_close_group(inf);
+	return;
+    }
+
+    switch (inf->ppat->type) {
+	case Rep_Bol:
+	case Rep_Eol:
+	case Rep_Bow:
+	case Rep_Eow:
+	case Rep_AnyAnyTimes:
+	case Rep_AnyMaybe:
+	case Rep_AnyAtLeast:
+	    /* Markers that cannot repeat */
+	    free(rep);
+	    inf->ecode = RE_BADRPT;
+	    return;
+
+	case Rep_Any:
+	    grp = inf->pgrp;
+	    free(rep);
+	    if (rept == Rer_AnyTimes ||
+		rept == Rer_Maybe ||
+		rept == Rer_AtLeast) {
+		inf->ppat->type = (rept == Rer_AnyTimes) ?
+				   Rep_AnyAnyTimes :
+				  (rept == Rer_Maybe) ?
+				   Rep_AnyMaybe :
+				   Rep_AnyAtLeast;
+		while (grp) {
+		    ++grp->comp;
+		    grp = grp->pgrp;
+		}
+	    }
+	    else
+		/* XXX Not (yet) implemented */
+		inf->ecode = RE_BADRPT;
+	    rep = NULL;
+	    break;
+
+	case Rep_String:
+	    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+		free(rep);
+		inf->ecode = RE_ESPACE;
+		return;
+	    }
+
+	    length = strlen((char*)inf->ppat->data.str);
+	    pat->type = Rep_Literal;
+	    pat->prev = inf->ppat;
+	    pat->data.chr = inf->ppat->data.str[length - 1];
+	    if (length == 2) {
+		/* Must convert to two Rep_Literals */
+		value = inf->ppat->data.str[0];
+		free(inf->ppat->data.str);
+		inf->ppat->data.chr = value;
+		inf->ppat->type = Rep_Literal;
+	    }
+	    else
+		/* Must remove last character from string */
+		inf->ppat->data.str[length - 1] = '\0';
+	    inf->ppat->next = pat;
+	    inf->ppat = pat;
+	    break;
+
+	case Rep_CaseString:
+	    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+		free(rep);
+		inf->ecode = RE_ESPACE;
+		return;
+	    }
+
+	    length = strlen((char*)inf->ppat->data.str);
+	    pat->type = Rep_CaseLiteral;
+	    pat->prev = inf->ppat;
+	    pat->data.cse.lower = inf->ppat->data.str[length - 2];
+	    pat->data.cse.upper = inf->ppat->data.str[length - 1];
+	    if (length == 4) {
+		/* Must convert to two Rep_CaseLiterals */
+		value = inf->ppat->data.str[0];
+		upper = inf->ppat->data.str[1];
+		free(inf->ppat->data.str);
+		inf->ppat->data.cse.lower = value;
+		inf->ppat->data.cse.upper = upper;
+		inf->ppat->next = pat;
+		inf->ppat->type = Rep_CaseLiteral;
+	    }
+	    else
+		/* Must remove last character pair from string */
+		inf->ppat->data.str[length - 2] = '\0';
+	    inf->ppat->next = pat;
+	    inf->ppat = pat;
+	    break;
+
+	default:
+	    /* Anything else does not need special handling */
+	    break;
+    }
+
+    inf->ppat->rep = rep;
+}
+
+static void
+irec_free(irec_info *inf)
+{
+    irec_free_alt(inf->alt);
+}
+
+static void
+irec_free_grp(rec_grp *grp)
+{
+    if (grp->alt)
+	irec_free_alt(grp->alt);
+    free(grp);
+}
+
+static void
+irec_free_pats(rec_pat *pat)
+{
+    rec_pat *next;
+    rec_pat_t rect;
+
+    while (pat) {
+	next = pat->next;
+	if (pat->rep)
+	    free(pat->rep);
+	rect = pat->type;
+	if (rect == Rep_Range || rect == Rep_RangeNot)
+	    free(pat->data.rng);
+	else if (rect == Rep_Group)
+	    irec_free_grp(pat->data.grp);
+	else if (rect == Rep_StringList)
+	    orec_free_stl(pat->data.stl);
+	free(pat);
+	pat = next;
+    }
+}
diff --git a/lisp/re/reo.c b/lisp/re/reo.c
new file mode 100644
index 0000000..59cbf3b
--- /dev/null
+++ b/lisp/re/reo.c
@@ -0,0 +1,685 @@
+/*
+ * Copyright (c) 2002 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ *
+ * Author: Paulo César Pereira de Andrade
+ */
+
+/* $XFree86: xc/programs/xedit/lisp/re/reo.c,v 1.9 2002/11/15 07:01:33 paulo Exp $ */
+
+#include "rep.h"
+
+/*
+ *  This file is a placeholder to add code to analyse and optimize the
+ * intermediate data structure generated in rep.c.
+ *  Character ranges are optimized while being generated.
+ */
+
+/*
+ * Types
+ */
+typedef struct _orec_inf {
+    rec_alt *alt;			/* Main alternatives list */
+    rec_grp *grp;			/* Current group pointer */
+    int flags;
+    int ecode;
+} orec_inf;
+
+/*
+ * Prototypes
+ */
+static int orec_alt(orec_inf*, rec_alt*);
+static int orec_pat(orec_inf*, rec_pat*);
+static int orec_grp(orec_inf*, rec_grp*);
+static int orec_pat_bad_rpt(orec_inf*, rec_pat*);
+static int orec_pat_bad_forward_rpt(orec_inf*, rec_pat*);
+static int orec_pat_rng(orec_inf*, rec_pat*);
+static int orec_pat_cse(orec_inf*, rec_pat*);
+static int orec_pat_cse_can(orec_inf*, rec_pat*);
+static int orec_str_list(orec_inf*, rec_alt*, int, int);
+
+/*
+ * Initialization
+ */
+extern unsigned char re__alnum[256];
+extern unsigned char re__odigit[256];
+extern unsigned char re__ddigit[256];
+extern unsigned char re__xdigit[256];
+extern unsigned char re__control[256];
+
+/*
+ * Implementation
+ */
+int
+orec_comp(rec_alt *alt, int flags)
+{
+    orec_inf inf;
+
+    inf.alt = alt;
+    inf.grp = NULL;
+    inf.flags = flags;
+    inf.ecode = 0;
+
+    orec_alt(&inf, alt);
+
+    return (inf.ecode);
+}
+
+void
+orec_free_stl(rec_stl *stl)
+{
+    int i;
+
+    for (i = 0; i < stl->nstrs; i++) {
+	if (stl->lens[i] > 2)
+	    free(stl->strs[i]);
+    }
+
+    free(stl->lens);
+    free(stl->strs);
+    free(stl);
+}
+
+
+static int
+orec_alt(orec_inf *inf, rec_alt *alt)
+{
+    if (alt) {
+	rec_alt *ptr = alt;
+	int ret, count = 0, str = 1, cstr = 1, lits = 0, clits = 0;
+
+	/* Check if can build a string list */
+	if (ptr->next) {
+	    /* If more than one alternative */
+	    while (ptr && (str || cstr)) {
+		if (ptr->pat == NULL || ptr->pat->rep != NULL) {
+		    cstr = str = 0;
+		    break;
+		}
+		if ((inf->flags & RE_ICASE)) {
+		    if (!(ret = orec_pat_cse_can(inf, ptr->pat))) {
+			cstr = str = 0;
+			break;
+		    }
+		    if (ret == 1)
+			++lits;
+		    else if (ret == 2)
+			++clits;
+		}
+		else if (ptr->pat->next == NULL) {
+		    if (ptr->pat->type != Rep_String) {
+			if (ptr->pat->type != Rep_Literal) {
+			    str = 0;
+			    if (ptr->pat->type != Rep_CaseString) {
+				if (ptr->pat->type != Rep_CaseLiteral)
+				    cstr = 0;
+				else
+				    ++clits;
+			    }
+			    else if (strlen((char*)ptr->pat->data.str) >= 255)
+				str = cstr = 0;
+			}
+			else
+			    ++lits;
+		    }
+		    else if (strlen((char*)ptr->pat->data.str) >= 255)
+			str = cstr = 0;
+		}
+		else {
+		    str = cstr = 0;
+		    break;
+		}
+		if (++count >= 255)
+		    str = cstr = 0;
+		ptr = ptr->next;
+	    }
+
+	    if (str || cstr) {
+		if (inf->flags & RE_ICASE) {
+		    for (ptr = alt; ptr; ptr = ptr->next) {
+			if (orec_pat_cse(inf, ptr->pat))
+			    return (inf->ecode);
+		    }
+		    str = 0;
+		}
+		return (orec_str_list(inf, alt, str, count));
+	    }
+	}
+	else if (alt == inf->alt && alt->pat && alt->pat->rep == NULL) {
+	    /* If the toplevel single alternative */
+	    switch (alt->pat->type) {
+		/*  One of these will always be true for RE_NOSPEC,
+		 * but can also be optimized for simple patterns */
+		case Rep_Literal:
+		    alt->pat->type = Rep_SearchLiteral;
+		    break;
+		case Rep_CaseLiteral:
+		    alt->pat->type = Rep_SearchCaseLiteral;
+		    break;
+		case Rep_String:
+		    alt->pat->type = Rep_SearchString;
+		    break;
+		case Rep_CaseString:
+		    alt->pat->type = Rep_SearchCaseString;
+		    break;
+		default:
+		    break;
+	    }
+	}
+
+	while (alt) {
+	    orec_pat(inf, alt->pat);
+	    alt = alt->next;
+	}
+    }
+
+    return (inf->ecode);
+}
+
+static int
+orec_pat(orec_inf *inf, rec_pat *pat)
+{
+    rec_pat *next;
+
+    while (pat) {
+	switch (pat->type) {
+	    case Rep_AnyAnyTimes:
+		if (pat->next == NULL) {
+		    rec_grp *grp = inf->grp;
+
+		    next = NULL;
+		    while (grp) {
+			next = grp->parent->next;
+			/* Cannot check if is .*$ as the input
+			 * may be a substring */
+			if (next)
+			    break;
+			grp = grp->pgrp;
+		    }
+		    if (next == NULL) {
+			/*    <re>.*    */
+			pat->type = Rep_AnyEatAnyTimes;
+			grp = inf->grp;
+			while (grp) {
+			    --grp->comp;
+			    next = grp->parent->next;
+			    if (next)
+				break;
+			    grp = grp->pgrp;
+			}
+		    }
+		    else if (orec_pat_bad_rpt(inf, next))
+			return (inf->ecode);
+		}
+		else if (orec_pat_bad_rpt(inf, pat->next))
+		    return (inf->ecode);
+		break;
+	    case Rep_AnyMaybe:
+		if (pat->next == NULL) {
+		    rec_grp *grp = inf->grp;
+
+		    next = NULL;
+		    while (grp) {
+			next = grp->parent->next;
+			if (next)
+			    break;
+			grp = grp->pgrp;
+		    }
+		    if (next == NULL) {
+			/*    <re>.?    */
+			pat->type = Rep_AnyEatMaybe;
+			grp = inf->grp;
+			while (grp) {
+			    --grp->comp;
+			    next = grp->parent->next;
+			    if (next)
+				break;
+			    grp = grp->pgrp;
+			}
+		    }
+		    else if (orec_pat_bad_rpt(inf, next))
+			return (inf->ecode);
+		}
+		else if (orec_pat_bad_rpt(inf, pat->next))
+		    return (inf->ecode);
+		break;
+	    case Rep_AnyAtLeast:
+		if (pat->next == NULL) {
+		    rec_grp *grp = inf->grp;
+
+		    next = NULL;
+		    while (grp) {
+			next = grp->parent->next;
+			if (next)
+			    break;
+			grp = grp->pgrp;
+		    }
+		    if (next == NULL) {
+			/*    <re>.+    */
+			pat->type = Rep_AnyEatAtLeast;
+			grp = inf->grp;
+			while (grp) {
+			    --grp->comp;
+			    next = grp->parent->next;
+			    if (next)
+				break;
+			    grp = grp->pgrp;
+			}
+		    }
+		    else if (orec_pat_bad_rpt(inf, next))
+			return (inf->ecode);
+		}
+		else if (orec_pat_bad_rpt(inf, pat->next))
+		    return (inf->ecode);
+		break;
+	    case Rep_Range:
+	    case Rep_RangeNot:
+		orec_pat_rng(inf, pat);
+		break;
+	    case Rep_Group:
+		orec_grp(inf, pat->data.grp);
+		break;
+	    default:
+		break;
+	}
+	pat = pat->next;
+    }
+
+    return (inf->ecode);
+}
+
+static int
+orec_pat_bad_rpt(orec_inf *inf, rec_pat *pat)
+{
+    switch (pat->type) {
+	/* Not really an error, but aren't supported by the library.
+	 * Includes:  .*.*, .+<re>?  .*<re>*, (.*)(<re>*), etc.
+	 */
+
+	/* Not a repetition, but mathes anything... */
+	case Rep_Any:
+
+	/* Zero length matches */
+	case Rep_Eol:
+	    if (!(inf->flags & RE_NEWLINE))
+		break;
+	case Rep_Bol:
+	case Rep_Bow:
+	case Rep_Eow:
+
+	/* Repetitions */
+	case Rep_AnyAnyTimes:
+	case Rep_AnyMaybe:
+	case Rep_AnyAtLeast:
+	    inf->ecode = RE_BADRPT;
+	    break;
+
+	/* Check if the first group element is a complex pattern */
+	case Rep_Group:
+	    if (pat->rep == NULL) {
+		if (pat->data.grp->alt) {
+		    for (pat = pat->data.grp->alt->pat; pat; pat = pat->next) {
+			if (orec_pat_bad_rpt(inf, pat))
+			    break;
+		    }
+		}
+		break;
+	    }
+	    /*FALLTHROUGH*/
+	default:
+	    if (pat->rep)
+		inf->ecode = RE_BADRPT;
+	    break;
+    }
+
+    if (!inf->ecode && pat && pat->next)
+	orec_pat_bad_forward_rpt(inf, pat->next);
+
+    return (inf->ecode);
+}
+
+static int
+orec_pat_bad_forward_rpt(orec_inf *inf, rec_pat *pat)
+{
+    if (pat->rep) {
+	switch (pat->rep->type) {
+	    case Rer_MinMax:
+		if (pat->rep->mine > 0)
+		    break;
+	    case Rer_AnyTimes:
+	    case Rer_Maybe:
+	    case Rer_Max:
+		inf->ecode = RE_BADRPT;
+	    default:
+		break;
+	}
+    }
+    else if (pat->type == Rep_Group &&
+	     pat->data.grp->alt &&
+	     pat->data.grp->alt->pat)
+	orec_pat_bad_forward_rpt(inf, pat->data.grp->alt->pat);
+
+    return (inf->ecode);
+}
+
+static int
+orec_grp(orec_inf *inf, rec_grp *grp)
+{
+    rec_grp *prev = inf->grp;
+
+    inf->grp = grp;
+    orec_alt(inf, grp->alt);
+    /* Could also just say: inf->grp = grp->gparent */
+    inf->grp = prev;
+
+    return (inf->ecode);
+}
+
+static int
+orec_pat_rng(orec_inf *inf, rec_pat *pat)
+{
+    int i, j[2], count;
+    rec_pat_t type = pat->type;
+    unsigned char *range = pat->data.rng->range;
+
+    for (i = count = j[0] = j[1] = 0; i < 256; i++) {
+	if (range[i]) {
+	    if (count == 2) {
+		++count;
+		break;
+	    }
+	    j[count++] = i;
+	}
+    }
+
+    if (count == 1 ||
+	(count == 2 &&
+	 ((islower(j[0]) && toupper(j[0]) == j[1]) ||
+	  (isupper(j[0]) && tolower(j[0]) == j[1])))) {
+	free(pat->data.rng);
+	if (count == 1) {
+	    pat->data.chr = j[0];
+	    pat->type = type == Rep_Range ? Rep_Literal : Rep_LiteralNot;
+	}
+	else {
+	    pat->data.cse.upper = j[0];
+	    pat->data.cse.lower = j[1];
+	    pat->type = type == Rep_Range ? Rep_CaseLiteral : Rep_CaseLiteralNot;
+	}
+    }
+    else {
+	if (memcmp(re__alnum, range, 256) == 0)
+	    type = type == Rep_Range ? Rep_Alnum : Rep_AlnumNot;
+	else if (memcmp(re__odigit, range, 256) == 0)
+	    type = type == Rep_Range ? Rep_Odigit : Rep_OdigitNot;
+	else if (memcmp(re__ddigit, range, 256) == 0)
+	    type = type == Rep_Range ? Rep_Digit : Rep_DigitNot;
+	else if (memcmp(re__xdigit, range, 256) == 0)
+	    type = type == Rep_Range ? Rep_Xdigit : Rep_XdigitNot;
+	else if (memcmp(re__control, range, 256) == 0)
+	    type = type == Rep_Range ? Rep_Control : Rep_ControlNot;
+
+	if (type != pat->type) {
+	    free(pat->data.rng);
+	    pat->type = type;
+	}
+    }
+
+    return (inf->ecode);
+}
+
+/*  Join patterns if required, will only fail on memory allocation failure:
+ */
+static int
+orec_pat_cse(orec_inf *inf, rec_pat *pat)
+{
+    rec_pat_t type;
+    int i, len, length;
+    rec_pat *ptr, *next;
+    unsigned char *str, *tofree;
+
+    if (pat->next == NULL && pat->type == Rep_CaseString)
+	return (inf->ecode);
+
+    type = Rep_CaseString;
+
+    /* First calculate how many bytes will be required */
+    for (ptr = pat, length = 1; ptr; ptr = ptr->next) {
+	switch (ptr->type) {
+	    case Rep_Literal:
+		length += 2;
+		break;
+	    case Rep_String:
+		length += strlen((char*)ptr->data.str) << 1;
+		break;
+	    case Rep_CaseLiteral:
+		length += 2;
+		break;
+	    case Rep_CaseString:
+		length += strlen((char*)ptr->data.str);
+		break;
+	    default:
+		break;
+	}
+    }
+
+    if ((str = malloc(length)) == NULL)
+	return (inf->ecode = RE_ESPACE);
+
+    for (ptr = pat, length = 0; ptr; ptr = next) {
+	tofree = NULL;
+	next = ptr->next;
+	switch (ptr->type) {
+	    case Rep_Literal:
+		str[length++] = ptr->data.chr;
+		str[length++] = ptr->data.chr;
+		break;
+	    case Rep_String:
+		tofree = ptr->data.str;
+		len = strlen((char*)tofree);
+		for (i = 0; i < len; i++) {
+		    str[length++] = tofree[i];
+		    str[length++] = tofree[i];
+		}
+		break;
+	    case Rep_CaseLiteral:
+		str[length++] = ptr->data.cse.lower;
+		str[length++] = ptr->data.cse.upper;
+		break;
+	    case Rep_CaseString:
+		tofree = ptr->data.str;
+		len = strlen((char*)tofree);
+		memcpy(str + length, tofree, len);
+		length += len;
+		break;
+	    default:
+		break;
+	}
+	if (tofree)
+	    free(tofree);
+	if (ptr != pat)
+	    free(ptr);
+    }
+    str[length] = '\0';
+
+    pat->type = type;
+    pat->data.str = str;
+    pat->next = NULL;
+
+    return (inf->ecode);
+}
+
+/*  Return 0 if the patterns in the list cannot be merged, 1 if will
+ * be a simple string, 2 if a case string.
+ *  This is useful when building an alternative list that is composed
+ * only of strings, but the regex is case insensitive, in wich case
+ * the first pass may have splited some patterns, but if it is a member
+ * of an alternatives list, the cost of using a string list is smaller */
+static int
+orec_pat_cse_can(orec_inf *inf, rec_pat *pat)
+{
+    int ret;
+
+    if (pat == NULL)
+	return (0);
+
+    for (ret = 1; pat; pat = pat->next) {
+	if (pat->rep)
+	    return (0);
+	switch (pat->type) {
+	    case Rep_Literal:
+	    case Rep_String:
+		break;
+	    case Rep_CaseLiteral:
+	    case Rep_CaseString:
+		ret = 2;
+		break;
+	    default:
+		return (0);
+	}
+    }
+
+    return (ret);
+}
+
+
+/*  XXX If everything is a (case) byte, the pattern should be
+ * [abcde] instead of a|b|c|d|e (or [aAbBcCdDeE] instead of aA|bB|cC|dD|eE)
+ * as a string list works fine, but as a character range
+ * should be faster, and maybe could be converted here. But not
+ * very important, if performance is required, it should have already
+ * been done in the pattern.
+ */
+static int
+orec_str_list(orec_inf *inf, rec_alt *alt, int str, int count)
+{
+    rec_stl *stl;
+    rec_pat *pat;
+    rec_alt *ptr, *next;
+    int i, j, tlen, len, is;
+
+    if ((stl = calloc(1, sizeof(rec_stl))) == NULL)
+	return (inf->ecode = RE_ESPACE);
+
+    if ((stl->lens = malloc(sizeof(unsigned char) * count)) == NULL) {
+	free(stl);
+	return (inf->ecode = RE_ESPACE);
+    }
+
+    if ((stl->strs = malloc(sizeof(char*) * count)) == NULL) {
+	free(stl->lens);
+	free(stl);
+	return (inf->ecode = RE_ESPACE);
+    }
+
+    if ((pat = calloc(1, sizeof(rec_pat))) == NULL) {
+	free(stl->strs);
+	free(stl->lens);
+	free(stl);
+	return (inf->ecode = RE_ESPACE);
+    }
+
+    pat->data.stl = stl;
+    pat->type = Rep_StringList;
+    stl->type = str ? Resl_StringList : Resl_CaseStringList;
+    for (i = tlen = 0, ptr = alt; i < count; i++) {
+	next = ptr->next;
+	switch (ptr->pat->type) {
+	    case Rep_Literal:
+		is = len = 1;
+		break;
+	    case Rep_CaseLiteral:
+		is = len = 2;
+		break;
+	    default:
+		is = 0;
+		len = strlen((char*)ptr->pat->data.str);
+		break;
+	}
+	tlen += len;
+	stl->lens[i] = len;
+	if (!is) {
+	    if (len > 2)
+		stl->strs[i] = ptr->pat->data.str;
+	    else {
+		if (len == 1)
+		    stl->strs[i] = (void*)(long)(ptr->pat->data.str[0]);
+		else
+		    stl->strs[i] = (void*)(long)
+				   (ptr->pat->data.str[0] |
+				    ((int)ptr->pat->data.str[1] << 8));
+		free(ptr->pat->data.str);
+	    }
+	}
+	else {
+	    if (is == 1)
+		stl->strs[i] = (void*)(long)ptr->pat->data.chr;
+	    else
+		stl->strs[i] = (void*)(long)
+			       (ptr->pat->data.cse.lower |
+				(ptr->pat->data.cse.upper << 8));
+	}
+	free(ptr->pat);
+	if (i)
+	    free(ptr);
+	ptr = next;
+    }
+    stl->tlen = tlen;
+    stl->nstrs = count;
+
+    alt->pat = pat;
+    alt->next = NULL;
+
+    {
+	int li, lj;
+	unsigned char ci, cj, *str;
+
+	/*  Don't need a stable sort, there shouldn't be duplicated strings,
+	 * but don't check for it either. Only need to make sure that all
+	 * strings that start with the same byte are together */
+	for (i = 0; i < count; i++) {
+	    li = stl->lens[i];
+	    ci = li > 2 ? stl->strs[i][0] : (long)stl->strs[i] & 0xff;
+	    for (j = i + 1; j < count; j++) {
+		lj = stl->lens[j];
+		cj = lj > 2 ? stl->strs[j][0] : (long)stl->strs[j] & 0xff;
+		if ((count >= LARGE_STL_COUNT && cj < ci) ||
+		    (cj == ci && lj > li)) {
+		    /* If both strings start with the same byte,
+		     * put the longer first */
+		    str = stl->strs[j];
+		    stl->strs[j] = stl->strs[i];
+		    stl->strs[i] = str;
+		    stl->lens[j] = li;
+		    stl->lens[i] = lj;
+		    li ^= lj; lj ^= li; li ^= lj;
+		    ci ^= cj; cj ^= ci; ci ^= cj;
+		}
+	    }
+	}
+    }
+
+    return (inf->ecode);
+}
diff --git a/lisp/re/rep.h b/lisp/re/rep.h
new file mode 100644
index 0000000..5e4d5d5
--- /dev/null
+++ b/lisp/re/rep.h
@@ -0,0 +1,369 @@
+/*
+ * Copyright (c) 2002 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ *
+ * Author: Paulo César Pereira de Andrade
+ */
+
+/* $XFree86: xc/programs/xedit/lisp/re/rep.h,v 1.3 2002/11/25 02:35:32 paulo Exp $ */
+
+#include "re.h"
+
+#ifndef _rep_h
+#define _rep_h
+
+/*
+ * Local defines
+ */
+
+#ifdef MIN
+#undef MIN
+#endif
+#define MIN(a, b)	((a) < (b) ? (a) : (b))
+
+#ifdef MAX
+#undef MAX
+#endif
+#define MAX(a, b)	((a) > (b) ? (a) : (b))
+
+/*  This value can not be larger than 255, a depth value is the nesting of
+ * repetition operations and alternatives. The number of nested parenthesis
+ * does not matter, but a repetition on the pattern inside the parenthesis
+ * does. Note also that you cannot have more than 9 parenthesis pairs in
+ * an expression.
+ *  Depth is always at least 1. So for MAX_DEPTH 8, it is only allowed
+ * 7 complex repetitions. A complex repetition is a dot followed by an
+ * repetition operator. It is called a complex repetition because dot
+ * matches anything but the empty string, so the engine needs to test
+ * all possible combinations until the end of the string is found.
+ *  Repetitions like .* use one depth until the end of the string is found,
+ * for example a.*b.*c.*d has depth 4, while a*b*c*d has depth 2.
+ */
+#define MAX_DEPTH	8
+
+/*  Minimum number of strings to generate a "large" string list, that is,
+ * sort the strings and allocate 512 extra bytes to map the first string
+ * with a given initial byte. */
+#define LARGE_STL_COUNT	16
+
+/*
+ * Local types
+ */
+/* Intermediate compilation types declaration */
+	/* (r)egular (e)xpression (c)ompile (c)a(se) */
+typedef struct _rec_cse rec_cse;
+
+	/* (r)egular (e)xpression (c)ompile (r)a(ng)e */
+typedef struct _rec_rng rec_rng;
+
+	/* (r)egular (e)xpression (c)ompile (pat)tern */
+typedef struct _rec_pat rec_pat;
+
+	/* (r)egular (e)xpression (c)ompile (rep)etition */
+typedef struct _rec_rep rec_rep;
+
+	/* (r)egular (e)xpression (c)ompile (gr)ou(p) */
+typedef struct _rec_grp rec_grp;
+
+	/* (r)egular (e)xpression (c)ompile (alt)ernatives */
+typedef struct _rec_alt rec_alt;
+
+
+/* Optimization types */
+	/* (r)egular (e)xpression (c)ompile (st)ring (l)ist */
+typedef struct _rec_stl rec_stl;
+
+/* Final compilation and execution types */
+	/* (re)gular expression (inf)ormation */
+typedef struct _re_inf re_inf;
+
+	/* (re)gular expression (eng)ine */
+typedef struct _re_eng re_eng;
+
+
+/* Codes used by the engine */
+typedef enum {
+    /* Grouping */
+    Re_Open,			/* ( */
+    Re_Close,			/* ) */
+    Re_Update,			/* Like Re_Close, but is inside a loop */
+
+    /* Alternatives */
+    Re_Alt,			/* Start alternative list, + next offset */
+    Re_AltNext,			/* Next alternative, + next offset */
+    Re_AltDone,			/* Finish alternative list */
+
+    /* Repetition */
+    Re_AnyTimes,		/* * */
+    Re_Maybe,			/* ? */
+    Re_AtLeast,			/* +, at least one */
+
+    /* Repetition like */
+    Re_AnyAnyTimes,		/* .*<re> */
+    Re_AnyMaybe,		/* .?<re> */
+    Re_AnyAtLeast,		/* .+<re> */
+
+    Re_AnyEatAnyTimes,		/* Expression ends with .* */
+    Re_AnyEatMaybe,		/* Expression ends with .? */
+    Re_AnyEatAtLeast,		/* Expression ends with .+ */
+
+    /* Repetition with arguments */
+    Re_Exact,			/* {e} */
+    Re_Min,			/* {n,} */
+    Re_Max,			/* {,m} */
+    Re_MinMax,			/* {n,m} */
+
+    /* Repetition helper instruction */
+    Re_RepJump,			/* Special code, go back to repetition */
+    Re_RepLongJump,		/* Jump needs two bytes */
+	/*  After the repetition data, all repetitions have an offset
+	 * to the code after the repetition */
+
+    /* Matching */
+    Re_Any,			/* . */
+    Re_Odigit,			/* \o */
+    Re_OdigitNot,		/* \O */
+    Re_Digit,			/* \d */
+    Re_DigitNot,		/* \D */
+    Re_Xdigit,			/* \x */
+    Re_XdigitNot,		/* \x */
+    Re_Space,			/* \s */
+    Re_SpaceNot,		/* \S */
+    Re_Tab,			/* \t */
+    Re_Newline,			/* \n */
+    Re_Lower,			/* \l */
+    Re_Upper,			/* \u */
+    Re_Alnum,			/* \w */
+    Re_AlnumNot,		/* \W */
+    Re_Control,			/* \c */
+    Re_ControlNot,		/* \C */
+    Re_Bol,			/* ^ */
+    Re_Eol,			/* $ */
+    Re_Bow,			/* \< */
+    Re_Eow,			/* \> */
+
+    /* Range matching information */
+    Re_Range,			/* + 256 bytes */
+    Re_RangeNot,		/* + 256 bytes */
+
+    /* Matching with arguments */
+    Re_Literal,			/* + character */
+    Re_CaseLiteral,		/* + lower + upper */
+    Re_LiteralNot,		/* + character */
+    Re_CaseLiteralNot,		/* + lower + upper */
+    Re_String,			/* + length + string */
+    Re_CaseString,		/* + length + string in format lower-upper */
+
+    /* These are useful to start matching, or when RE_NOSPEC is used. */
+    Re_SearchLiteral,
+    Re_SearchCaseLiteral,
+    Re_SearchString,
+    Re_SearchCaseString,
+
+    Re_StringList,		/* + total-length + lengths + strings */
+    Re_CaseStringList,		/* + total-length + lengths + strings */
+
+    Re_LargeStringList,		/* + total-length + lengths + map + strings */
+    Re_LargeCaseStringList,	/* + total-length + lengths + map + strings */
+
+    /* Backreference */
+    Re_Backref,			/* + reference number */
+
+    /* The last codes */
+    Re_DoneIf,			/* Done if at end of input */
+    Re_MaybeDone,		/* Done */
+    Re_Done			/* If this code found, finished execution */
+} ReCode;
+
+
+/* (r)egular (e)xpresssion (pat)rern (t)ype */
+typedef enum _rec_pat_t {
+    Rep_Literal			= Re_Literal,
+    Rep_CaseLiteral		= Re_CaseLiteral,
+    Rep_LiteralNot		= Re_LiteralNot,
+    Rep_CaseLiteralNot		= Re_CaseLiteralNot,
+    Rep_Range			= Re_Range,
+    Rep_RangeNot		= Re_RangeNot,
+    Rep_String			= Re_String,
+    Rep_CaseString		= Re_CaseString,
+    Rep_SearchLiteral		= Re_SearchLiteral,
+    Rep_SearchCaseLiteral	= Re_SearchCaseLiteral,
+    Rep_SearchString		= Re_SearchString,
+    Rep_SearchCaseString	= Re_SearchCaseString,
+    Rep_Any			= Re_Any,
+    Rep_AnyAnyTimes		= Re_AnyAnyTimes,
+    Rep_AnyEatAnyTimes		= Re_AnyEatAnyTimes,
+    Rep_AnyMaybe		= Re_AnyMaybe,
+    Rep_AnyEatMaybe		= Re_AnyEatMaybe,
+    Rep_AnyAtLeast		= Re_AnyAtLeast,
+    Rep_AnyEatAtLeast		= Re_AnyEatAtLeast,
+    Rep_Odigit			= Re_Odigit,
+    Rep_OdigitNot		= Re_OdigitNot,
+    Rep_Digit			= Re_Digit,
+    Rep_DigitNot		= Re_DigitNot,
+    Rep_Xdigit			= Re_Xdigit,
+    Rep_XdigitNot		= Re_XdigitNot,
+    Rep_Space			= Re_Space,
+    Rep_SpaceNot		= Re_SpaceNot,
+    Rep_Tab			= Re_Tab,
+    Rep_Newline			= Re_Newline,
+    Rep_Lower			= Re_Lower,
+    Rep_Upper			= Re_Upper,
+    Rep_Alnum			= Re_Alnum,
+    Rep_AlnumNot		= Re_AlnumNot,
+    Rep_Control			= Re_Control,
+    Rep_ControlNot		= Re_ControlNot,
+    Rep_Bol			= Re_Bol,
+    Rep_Eol			= Re_Eol,
+    Rep_Bow			= Re_Bow,
+    Rep_Eow			= Re_Eow,
+    Rep_Backref			= Re_Backref,
+    Rep_StringList		= Re_StringList,
+    Rep_Group			= Re_Open
+} rec_pat_t;
+
+
+/* (r)egular (e)xpression (rep)etition (t)ype */
+typedef enum _rec_rep_t {
+    Rer_AnyTimes		= Re_AnyTimes,
+    Rer_AtLeast			= Re_AtLeast,
+    Rer_Maybe			= Re_Maybe,
+    Rer_Exact			= Re_Exact,
+    Rer_Min			= Re_Min,
+    Rer_Max			= Re_Max,
+    Rer_MinMax			= Re_MinMax
+} rec_rep_t;
+
+
+/*  Decide at re compilation time what is lowercase and what is uppercase */
+struct _rec_cse {
+    unsigned char lower;
+    unsigned char upper;
+};
+
+
+/*  A rec_rng is used only during compilation, just a character map */
+struct _rec_rng {
+    unsigned char range[256];
+};
+
+
+/*  A rec_pat is used only during compilation, and can be viewed as
+ * a regular expression element like a match to any character, a match
+ * to the beginning or end of the line, etc.
+ *  It is implemented as a linked list, and does not have nesting.
+ *  The data field can contain:
+ *	chr:	the value of a single character to match.
+ *	cse:	the upper and lower case value of a character to match.
+ *	rng:	a character map to match or not match.
+ *	str:	a simple string or a string where every two bytes
+ *		represents the character to match, in lower/upper
+ *		case sequence.
+ *  The rep field is not used for strings, strings are broken in the
+ * last character in this case. That is, strings are just a concatenation
+ * of several character matches.
+ */
+struct _rec_pat {
+    rec_pat_t type;
+    rec_pat *next, *prev;	/* Linked list information */
+    union {
+	unsigned char chr;
+	rec_cse cse;
+	rec_rng *rng;
+	rec_grp *grp;
+	unsigned char *str;
+	rec_stl *stl;
+    } data;
+    rec_rep *rep;		/* Pattern repetition information */
+};
+
+
+/*  A rec_rep is used only during compilation, and can be viewed as:
+ *
+ *	? or * or + or {<e>} or {<m>,} or {,<M>} or {<m>,<M>}
+ *
+ * where <e> is "exact", <m> is "minimum" and <M> is "maximum".
+ *  In the compiled step it can also be just a NULL pointer, that
+ * is actually equivalent to {1}.
+ */
+struct _rec_rep {
+    rec_rep_t type;
+    short mine;			/* minimum or exact number of matches */
+    short maxc;			/* maximum number of matches */
+};
+
+
+/*  A rec_alt is used only during compilation, and can be viewed as:
+ *
+ *	<re>|<re>
+ *
+ * where <re> is any regular expression. The expressions are nested
+ * using the grp field of the rec_pat structure.
+ */
+struct _rec_alt {
+    rec_alt *next, *prev;	/* Linked list information */
+    rec_pat *pat;
+};
+
+
+/*  A rec_grp is a place holder for expressions enclosed in parenthesis
+ * and is linked to the compilation data by an rec_pat structure. */
+struct _rec_grp {
+    rec_pat *parent;		/* Reference to parent pattern */
+    rec_alt *alt;		/* The pattern information */
+    rec_alt *palt;		/* Parent alternative */
+    rec_grp *pgrp;		/* Nested groups */
+    int comp;			/* (comp)lex repetition pattern inside group */
+};
+
+
+/* Optimization compilation types definition */
+	/* (r)egular (e)xpression (c)ompile (st)ring (l)ist (t)ype */
+typedef enum {
+    Resl_StringList		= Re_StringList,
+    Resl_CaseStringList		= Re_CaseStringList
+} rec_stl_t;
+
+struct _rec_stl {
+    rec_stl_t type;
+    int nstrs;			/* Number of strings in list */
+    int tlen;			/* Total length of all strings */
+    unsigned char *lens;	/* Vector of string lengths */
+    unsigned char **strs;	/* The strings */
+};
+
+
+/*
+ * Prototypes
+ */
+	/* rep.c */
+rec_alt *irec_comp(const char*, const char*, int, int*);
+void irec_free_alt(rec_alt*);
+
+	/* reo.c */
+int orec_comp(rec_alt*, int);
+void orec_free_stl(rec_stl*);
+
+#endif /* _rep_h */
diff --git a/lisp/re/tests.c b/lisp/re/tests.c
new file mode 100644
index 0000000..bd5c55d
--- /dev/null
+++ b/lisp/re/tests.c
@@ -0,0 +1,199 @@
+/*
+ * Copyright (c) 2002 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ *
+ * Author: Paulo César Pereira de Andrade
+ */
+
+/* $XFree86: xc/programs/xedit/lisp/re/tests.c,v 1.1 2002/09/08 02:29:50 paulo Exp $ */
+
+/*
+ * Compile with:	cc -o tests tests.c -L. -lre
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include "re.h"
+
+int
+main(int argc, char *argv[])
+{
+    re_cod cod;
+    re_mat mat[10];
+    int line, ecode, i, len, group, failed;
+    long eo, so;
+    char buf[8192];
+    char str[8192];
+    FILE *fp = fopen("tests.txt", "r");
+
+    if (fp == NULL) {
+	fprintf(stderr, "failed to open tests.txt\n");
+	exit(1);
+    }
+
+    ecode = line = group = failed = 0;
+    cod.cod = NULL;
+    while (fgets(buf, sizeof(buf), fp)) {
+	++line;
+	if (buf[0] == '#' || buf[0] == '\n')
+	    continue;
+	else if (buf[0] == '/') {
+	    char *ptr = strrchr(buf, '/');
+
+	    if (ptr == buf) {
+		fprintf(stderr, "syntax error at line %d\n", line);
+		break;
+	    }
+	    else {
+		int flags = 0;
+
+		refree(&cod);
+		for (*ptr++ = '\0'; *ptr; ptr++) {
+		    if (*ptr == 'i')
+			flags |= RE_ICASE;
+		    else if (*ptr == 'n')
+			flags |= RE_NEWLINE;
+		}
+		ecode = recomp(&cod, buf + 1, flags);
+		failed = ecode;
+	    }
+	}
+	else if (buf[0] == '>') {
+	    if (cod.cod == NULL) {
+		fprintf(stderr, "no previous pattern at line %d\n", line);
+		break;
+	    }
+	    len = strlen(buf) - 1;
+	    buf[len] = '\0';
+	    strcpy(str, buf + 1);
+	    for (i = 0, --len; i < len - 1; i++) {
+		if (str[i] == '\\') {
+		    memmove(str + i, str + i + 1, len);
+		    --len;
+		    switch (str[i]) {
+			case 'a':
+			    str[i] = '\a';
+			    break;
+			case 'b':
+			    str[i] = '\b';
+			    break;
+			case 'f':
+			    str[i] = '\f';
+			    break;
+			case 'n':
+			    str[i] = '\n';
+			    break;
+			case 'r':
+			    str[i] = '\r';
+			    break;
+			case 't':
+			    str[i] = '\t';
+			    break;
+			case 'v':
+			    str[i] = '\v';
+			    break;
+			default:
+			    break;
+		    }
+		}
+	    }
+	    group = 0;
+	    ecode = reexec(&cod, str, 10, &mat[0], 0);
+	    if (ecode && ecode != RE_NOMATCH) {
+		reerror(failed, &cod, buf, sizeof(buf));
+		fprintf(stderr, "%s, at line %d\n", buf, line);
+		break;
+	    }
+	}
+	else if (buf[0] == ':') {
+	    if (failed) {
+		len = strlen(buf) - 1;
+		buf[len] = '\0';
+		if (failed == RE_EESCAPE && strcmp(buf, ":EESCAPE") == 0)
+		    continue;
+		if (failed == RE_ESUBREG && strcmp(buf, ":ESUBREG") == 0)
+		    continue;
+		if (failed == RE_EBRACK && strcmp(buf, ":EBRACK") == 0)
+		    continue;
+		if (failed == RE_EPAREN && strcmp(buf, ":EPAREN") == 0)
+		    continue;
+		if (failed == RE_EBRACE && strcmp(buf, ":EBRACE") == 0)
+		    continue;
+		if (failed == RE_EBADBR && strcmp(buf, ":EBADBR") == 0)
+		    continue;
+		if (failed == RE_ERANGE && strcmp(buf, ":ERANGE") == 0)
+		    continue;
+		if (failed == RE_ESPACE && strcmp(buf, ":ESPACE") == 0)
+		    continue;
+		if (failed == RE_BADRPT && strcmp(buf, ":BADRPT") == 0)
+		    continue;
+		if (failed == RE_EMPTY && strcmp(buf, ":EMPTY") == 0)
+		    continue;
+		reerror(failed, &cod, buf, sizeof(buf));
+		fprintf(stderr, "Error value %d doesn't match: %s, at line %d\n",
+			failed, buf, line);
+		break;
+	    }
+	    else if (!ecode) {
+		fprintf(stderr, "found match when shoudn't, at line %d\n", line);
+		break;
+	    }
+	}
+	else {
+	    if (failed) {
+		reerror(failed, &cod, buf, sizeof(buf));
+		fprintf(stderr, "%s, at line %d\n", line);
+		break;
+	    }
+	    if (sscanf(buf, "%ld,%ld:", &so, &eo) != 2) {
+		fprintf(stderr, "expecting match offsets at line %d\n", line);
+		break;
+	    }
+	    else if (ecode) {
+		fprintf(stderr, "didn't match, at line %d\n", line);
+		break;
+	    }
+	    else if (group >= 10) {
+		fprintf(stderr, "syntax error at line %d (too many groups)\n",
+			line);
+		break;
+	    }
+	    else if (so != mat[group].rm_so || eo != mat[group].rm_eo) {
+		fprintf(stderr, "match failed at line %d, got %ld,%ld: ",
+			line, mat[group].rm_so, mat[group].rm_eo);
+		if (mat[group].rm_so < mat[group].rm_eo)
+		    fwrite(str + mat[group].rm_so,
+		 	   mat[group].rm_eo - mat[group].rm_so, 1, stderr);
+		fputc('\n', stderr);
+		break;
+	    }
+	    ++group;
+	}
+    }
+
+    fclose(fp);
+
+    return (ecode);
+}
diff --git a/lisp/re/tests.txt b/lisp/re/tests.txt
new file mode 100644
index 0000000..e3da032
--- /dev/null
+++ b/lisp/re/tests.txt
@@ -0,0 +1,461 @@
+#
+#  Copyright (c) 2002 by The XFree86 Project, Inc.
+#
+#  Permission is hereby granted, free of charge, to any person obtaining a
+#  copy of this software and associated documentation files (the "Software"),
+#  to deal in the Software without restriction, including without limitation
+#  the rights to use, copy, modify, merge, publish, distribute, sublicense,
+#  and/or sell copies of the Software, and to permit persons to whom the
+#  Software is furnished to do so, subject to the following conditions:
+#
+#  The above copyright notice and this permission notice shall be included in
+#  all copies or substantial portions of the Software.
+#
+#  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+#  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+#  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+#  THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+#  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+#  OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+#  SOFTWARE.
+#
+#  Except as contained in this notice, the name of the XFree86 Project shall
+#  not be used in advertising or otherwise to promote the sale, use or other
+#  dealings in this Software without prior written authorization from the
+#  XFree86 Project.
+#
+#  Author: Paulo César Pereira de Andrade
+#
+#
+# $XFree86: xc/programs/xedit/lisp/re/tests.txt,v 1.3 2002/11/08 08:01:00 paulo Exp $
+
+# Some tests for the library:
+#	lines starting with # are comments
+#	lines starting with / are a regular expression pattern
+#		The pattern must end with / and may be followed by:
+#			i -> ignore case
+#			n -> create newline sensitive regex
+#	lines starting with > are a string input to the last pattern
+#		To test newline sensitive matching, add \n to the string.
+#	lines starting with a number are the expected result
+#		If more than one line, every subsequent line is the
+#		value of an "subresult".
+#	:NOMATCH means that the string input should not match
+
+# Simple string
+/abc/
+>abc
+0,3: abc
+>aaaaaaaaaaaaaaabc
+14,17: abc
+>xxxxxxxxxxxxxxaaaaaaaaaaaaaaaaabcxx
+30,33: abc
+
+# String list
+/abc|bcd|cde/
+>abc
+0,3: abc
+>aabc
+1,4: abc
+>xxxbcdef
+3,6: bcd
+>abdzzzcdabcde
+8,11: abc
+>xxxxabdecdabdcde
+13,16: cde
+
+# Complex string
+/a?bc|ab?c|abc?/
+>abc
+0,3: abc
+>xxxb
+:NOMATCH
+>xxxbc
+3,5: bc
+>sssssab
+5,7: ab
+
+# Another complex string
+/a*bc|ab*c|abc*/
+>aaaaaaabc
+0,9: aaaaaaabc
+>xaaaaaaabc
+1,10: aaaaaaabc
+>xyzaaaaaaabc
+3,12: aaaaaaabc
+>abbc
+0,4: abbc
+>xxabbbbbc
+2,9: abbbbbc
+>abcccccccccc
+0,12: abcccccccccc
+>abccccccccccd
+0,12: abcccccccccc
+>xxxxxxxaaaaaaaaaabbbbbbbbbbbccccccccccc
+16,29: abbbbbbbbbbbc
+>xxxbbbbbbbbbc
+11,13: bc
+
+# Another complex string
+/a+bc|ab+c|abc+/
+>xxxbc
+:NOMATCH
+>xaaabc
+1,6: aaabc
+>zzzzaaaaabbc
+8,12: abbc
+>zzzzaaaabbbbbbcccc
+7,15: abbbbbbc
+
+# Simple pattern
+/a.c/
+>abc
+0,3: abc
+>aaac
+1,4: aac
+>xac
+:NOMATCH
+>xaac
+1,4: aac
+>xxabc
+2,5: abc
+>xxxaxc
+3,6: axc
+
+# Another simple pattern
+/a*c/
+>c
+0,1: c
+>xxxxxxxxc
+8,9: c
+>xxxxxxxcc
+7,8: c
+>ac
+0,2: ac
+>aaaac
+0,5: aaaac
+>xac
+1,3: ac
+>xxxaac
+3,6: aac
+>xxac
+2,4: ac
+>xxxxac
+4,6: ac
+
+# Another simple pattern
+/a+c/
+>xxaac
+2,5: aac
+>xxxaaaac
+3,8: aaaac
+>xaaaabac
+6,8: ac
+>xxxc
+:NOMATCH
+>xxxxaaaaccc
+4,9: aaaac
+
+# Another simple pattern
+/a{4}b/
+>xabxxaabxxxaaabxxxxaaaab
+19,24: aaaab
+>aaabaaaab
+4,9: aaaab
+
+# Another simple pattern
+/a{4,}b/
+>xxxaaaab
+3,8: aaaab
+>zaaabzzzaaaaaaaaaaaaaaaab
+8,25: aaaaaaaaaaaaaaaab
+
+# Another simple pattern
+/a{,4}b/
+>b
+0,1: b
+>xxxxxxxxb
+8,9: b
+>xaaaaaaaaab
+6,11: aaaab
+>xxxab
+3,5: ab
+>aaaaaxaaab
+6,10: aaab
+
+# Another simple pattern
+/a{2,4}b/
+>xab
+:NOMATCH
+>xaab
+1,4: aab
+>xaaab
+1,5: aaab
+>xxaaaab
+2,7: aaaab
+>xxxaaaaab
+4,9: aaaab
+
+# Some simple grouping tests
+/foo(bar|baz)fee/
+>feebarbazfoobarfee
+9,18: foobarfee
+12,15: bar
+>foofooobazfeefoobazfee
+13,22: foobazfee
+/f(oo|ee)ba[rz]/
+>barfoebaz
+:NOMATCH
+>bazfoobar
+3,9: foobar
+4,6: oo
+>barfeebaz
+3,9: feebaz
+4,6: ee
+/\<(int|char)\>/
+>aint character int foo
+15,18: int
+15,18: int
+
+# Some complex repetitions
+/foo.*bar/
+>barfoblaboofoobarfoobarfoobar
+11,17: foobar
+/foo.+bar/
+>foobar
+:NOMATCH
+>fobbarfooxbarfooybar
+6,13: fooxbar
+/foo.?bar/
+>xfoobar
+1,7: foobar
+>xxfooxxbar
+:NOMATCH
+>yyyfootbar
+3,10: footbar
+
+# Some nested complex repetitions
+/a.*b.*c/
+>abc
+0,3: abc
+>xxxxxxxxxabbbbbbbccaaaaabbbc
+9,18: abbbbbbbc
+/a.+b.*c/
+>xxxabc 
+:NOMATCH
+>xxaxbbc
+2,7: axbbc
+/a.+b.?c/
+>xaabc
+1,5: aabc
+>xxaabbc
+2,7: aabbc
+
+# Very complex repetitions
+/(foo.*|bar)fee/
+# XXX NOTE
+# This pattern does not return the correct offset for the group.
+# Support for this may and may not be added.
+
+>barfoofee
+3,9: foofee
+>foobarfee
+0,9: foobarfee
+>xxfobarfee
+4,10: barfee
+>barfooooooobarfee
+3,17: fooooooobarfee
+>xxfobarfeefoobar
+4,10: barfee
+/(foo.+|bar)fee/
+>barfoofee
+:NOMATCH
+>barfooxfee
+3,10: fooxfee
+/(foo.?|bar)fee/
+>foobar
+:NOMATCH
+>bafoofee
+2,8:foofee
+>bafooofeebarfee
+2,9: fooofee
+>bafoofeebarfee
+2,8: foofee
+
+# Simple backreference
+/(a|b|c)\1/
+>aa
+0,2: aa
+0,1: a
+/(a|b|c)(a|b|c)\1\2/
+>acac
+0,4: acac
+0,1: a
+1,2: c
+>xxxxacac
+4,8: acac
+4,5: a
+5,6: c
+>xxacabacbcacbbacbcaaccabcaca
+24,28: caca
+24,25: c
+25,26: a
+>xyabcccc
+4,8: cccc
+4,5: c
+5,6: c
+
+# Complex backreference
+/(a*b)\1/
+>xxxaaaaabaaaaab
+3,15: aaaaabaaaaab
+3,9: aaaaab
+/(ab+c)\1/
+>xaaabbbcabbbc
+3,13: abbbcabbbc
+3,8: abbbc
+/(ab?c)\1/
+>abcac
+:NOMATCH
+>abcacabcabc
+5,11: abcabc
+5,8: abc
+>abcacac
+3,7: acac
+3,5: acac
+
+# Very complex backreference
+/a(.*)b\1/
+>xxxab
+3,5: ab
+4,4: 
+>xxxxazzzbzzz
+4,12: azzzbzzz
+5,8: zzz
+
+# Case testing
+/abc/i
+>AbC
+0,3: AbC
+/[0-9][a-z]+/i
+>xxx0aaZxYT9
+3,10: 0aaZxYT
+/a.b/i
+>aaaaaaaaaaaxB
+10,13: axB
+/a.*z/i
+>xxxAaaaaZ
+3,9: AaaaaZ
+>xxaaaZaaa
+2,6: aaaZ
+/\<(lambda|defun|defmacro)\>/i
+>    (lambda
+5,11: lambda
+5,11: lambda
+/\<(nil|t)\>/i
+>it Nil
+3,6: Nil
+3,6: Nil
+/\<(begin|end)\>/i
+>beginning the ending EnD
+21,24: EnD
+21,24: EnD
+
+# Some newline tests
+/a.*/n
+>a\naaa
+0,1:a
+>xyza\naa
+3,4: a
+/a.+/n
+>a\naaa
+2,5: aaa
+>xyza\naa
+5,7: aa
+/a.?/n
+>a\naaa
+0,1: a
+>xyza\naa
+3,4: a
+
+# Newline tests envolving complex patterns
+/a.*b.*c/n
+>xxaa\nzyacb\nabc
+11,14: abc
+>xxxab\nabc\nc
+6,9: abc
+/a.+b.*c/n
+>ab\nbc\nabbc
+6,10: abbc
+/a.?b.*c/n
+>ab\ncabbc\ncc
+4,8: abbc
+/^foo$/n
+>bar\nfoobar\nfoo
+11,14: foo
+
+# Not so complex test involving a newline...
+/^\s*#\s*(define|include)\s+.+/n
+>#define\n#include x
+8,18: #include x
+9,16: include
+
+# Check if large strings are working
+/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/
+>zzzxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzzz
+3,259: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
+/ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~/
+>String here: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~/
+13,333: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567890~
+
+
+# Some complex repetitions not supported
+# Listed here only to make sure the library is not crashing on these
+#  Repetitions that match an empty match, or an empty string cannot follow
+# a complex repetition. A complex repetition is:
+#	.* or .+ or .?
+#	.{...} is not supported.
+/(.*)(\d*)/
+:BADRPT
+/(.*).(\d*)/
+:BADRPT
+/(.*)\<(\d*)/
+:BADRPT
+/(.*)\s(\d*)/
+:BADRPT
+/(.*)\D(\d*)/
+:BADRPT
+
+# This is a more clear pattern and partially works
+/(.*)\D(\d+)/
+>abcW12
+0,6: abcW12
+0,3: abc
+4,6: 12
+>abcW12abcW12
+0,6: abcW12
+0,3: abc
+4,6: 12
+# This wasn't working in the previous version, but now with only minimal
+# matches supported, it works.
+>abcW12abcW12a
+0,6: abcW12
+0,3: abc
+4,6: 12
+
+# Note the minimal match
+/.*\d/
+>a1a1a1aaaaaaa
+0,2: a1
+# Check match offsets
+/(.*)\d/
+>a1a1a1aaaaaaa
+0,2: a1
+0,1: a
+/.*(\d)/
+>a1a1a1aaaaaaa
+0,2: a1
+1,2: 1
+
+/.*(\d+)/
+:BADRPT