summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/Make_cyg.mak3
-rw-r--r--src/Make_ming.mak3
-rw-r--r--src/Make_mvc.mak2
-rw-r--r--src/Makefile12
-rw-r--r--src/option.c8
-rw-r--r--src/option.h1
-rw-r--r--src/regexp.c445
-rw-r--r--src/regexp.h78
-rw-r--r--src/regexp_nfa.c3819
-rw-r--r--src/structs.h13
-rw-r--r--src/testdir/Make_amiga.mak3
-rw-r--r--src/testdir/Make_dos.mak2
-rw-r--r--src/testdir/Make_ming.mak2
-rw-r--r--src/testdir/Make_os2.mak2
-rw-r--r--src/testdir/Make_vms.mms5
-rw-r--r--src/testdir/Makefile7
-rw-r--r--src/testdir/test64.in180
-rw-r--r--src/testdir/test64.ok330
-rw-r--r--src/testdir/test95.in63
-rw-r--r--src/testdir/test95.ok6
-rw-r--r--src/version.c2
21 files changed, 4757 insertions, 229 deletions
diff --git a/src/Make_cyg.mak b/src/Make_cyg.mak
index b00ae3b71..d72282aa8 100644
--- a/src/Make_cyg.mak
+++ b/src/Make_cyg.mak
@@ -672,6 +672,9 @@ endif
$(OUTDIR)/netbeans.o: netbeans.c $(INCL) $(NBDEBUG_DEP)
$(CC) -c $(CFLAGS) netbeans.c -o $(OUTDIR)/netbeans.o
+$(OUTDIR)/regexp.o: regexp.c regexp_nfa.c $(INCL)
+ $(CC) -c $(CFLAGS) regexp.c -o $(OUTDIR)/regexp.o
+
$(OUTDIR)/if_mzsch.o: if_mzsch.c $(INCL) if_mzsch.h $(MZ_EXTRA_DEP)
$(CC) -c $(CFLAGS) if_mzsch.c -o $(OUTDIR)/if_mzsch.o
diff --git a/src/Make_ming.mak b/src/Make_ming.mak
index b8d7b200e..3670e7102 100644
--- a/src/Make_ming.mak
+++ b/src/Make_ming.mak
@@ -765,6 +765,9 @@ if_perl.c: if_perl.xs typemap
$(OUTDIR)/netbeans.o: netbeans.c $(INCL) $(NBDEBUG_INCL) $(NBDEBUG_SRC)
$(CC) -c $(CFLAGS) netbeans.c -o $(OUTDIR)/netbeans.o
+$(OUTDIR)/regexp.o: regexp.c regexp_nfa.c $(INCL)
+ $(CC) -c $(CFLAGS) regexp.c -o $(OUTDIR)/regexp.o
+
$(OUTDIR)/if_mzsch.o: if_mzsch.c $(INCL) if_mzsch.h $(MZ_EXTRA_DEP)
$(CC) -c $(CFLAGS) if_mzsch.c -o $(OUTDIR)/if_mzsch.o
diff --git a/src/Make_mvc.mak b/src/Make_mvc.mak
index 2a4a3e8c4..acd1346ab 100644
--- a/src/Make_mvc.mak
+++ b/src/Make_mvc.mak
@@ -1166,7 +1166,7 @@ $(OUTDIR)/popupmnu.obj: $(OUTDIR) popupmnu.c $(INCL)
$(OUTDIR)/quickfix.obj: $(OUTDIR) quickfix.c $(INCL)
-$(OUTDIR)/regexp.obj: $(OUTDIR) regexp.c $(INCL)
+$(OUTDIR)/regexp.obj: $(OUTDIR) regexp.c regexp_nfa.c $(INCL)
$(OUTDIR)/screen.obj: $(OUTDIR) screen.c $(INCL)
diff --git a/src/Makefile b/src/Makefile
index fb821ca8c..67a53bb0e 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -454,7 +454,7 @@ CClink = $(CC)
# MULTIBYTE - To edit multi-byte characters.
# Uncomment this when you want to edit a multibyte language.
-# It's automatically enabled with big features or IME support.
+# It's automatically enabled with normal features, GTK or IME support.
# Note: Compile on a machine where setlocale() actually works, otherwise the
# configure tests may fail.
#CONF_OPT_MULTIBYTE = --enable-multibyte
@@ -2664,7 +2664,7 @@ objects/popupmnu.o: popupmnu.c
objects/quickfix.o: quickfix.c
$(CCC) -o $@ quickfix.c
-objects/regexp.o: regexp.c
+objects/regexp.o: regexp.c regexp_nfa.c
$(CCC) -o $@ regexp.c
objects/screen.o: screen.c
@@ -2938,10 +2938,10 @@ objects/quickfix.o: quickfix.c vim.h auto/config.h feature.h os_unix.h \
auto/osdef.h ascii.h keymap.h term.h macros.h option.h structs.h \
regexp.h gui.h gui_beval.h proto/gui_beval.pro ex_cmds.h proto.h \
globals.h farsi.h arabic.h
-objects/regexp.o: regexp.c vim.h auto/config.h feature.h os_unix.h auto/osdef.h \
- ascii.h keymap.h term.h macros.h option.h structs.h regexp.h gui.h \
- gui_beval.h proto/gui_beval.pro ex_cmds.h proto.h globals.h farsi.h \
- arabic.h
+objects/regexp.o: regexp.c regexp_nfa.c vim.h auto/config.h feature.h os_unix.h \
+ auto/osdef.h ascii.h keymap.h term.h macros.h option.h structs.h \
+ regexp.h gui.h gui_beval.h proto/gui_beval.pro ex_cmds.h proto.h \
+ globals.h farsi.h arabic.h
objects/screen.o: screen.c vim.h auto/config.h feature.h os_unix.h auto/osdef.h \
ascii.h keymap.h term.h macros.h option.h structs.h regexp.h gui.h \
gui_beval.h proto/gui_beval.pro ex_cmds.h proto.h globals.h farsi.h \
diff --git a/src/option.c b/src/option.c
index cfe464c5b..325f061d9 100644
--- a/src/option.c
+++ b/src/option.c
@@ -2077,6 +2077,9 @@ static struct vimoption
(char_u *)NULL, PV_NONE,
#endif
{(char_u *)2000L, (char_u *)0L} SCRIPTID_INIT},
+ {"regexpengine", "re", P_NUM|P_VI_DEF,
+ (char_u *)&p_re, PV_NONE,
+ {(char_u *)0L, (char_u *)0L} SCRIPTID_INIT},
{"relativenumber", "rnu", P_BOOL|P_VI_DEF|P_RWIN,
(char_u *)VAR_WIN, PV_RNU,
{(char_u *)FALSE, (char_u *)0L} SCRIPTID_INIT},
@@ -8604,6 +8607,11 @@ set_num_option(opt_idx, varp, value, errbuf, errbuflen, opt_flags)
errmsg = e_positive;
p_hi = 0;
}
+ if (p_re < 0 || p_re > 2)
+ {
+ errmsg = e_invarg;
+ p_re = 0;
+ }
if (p_report < 0)
{
errmsg = e_positive;
diff --git a/src/option.h b/src/option.h
index 8b982f580..b11316faa 100644
--- a/src/option.h
+++ b/src/option.h
@@ -653,6 +653,7 @@ EXTERN char_u *p_cdpath; /* 'cdpath' */
EXTERN long p_rdt; /* 'redrawtime' */
#endif
EXTERN int p_remap; /* 'remap' */
+EXTERN long p_re; /* 'regexpengine' */
EXTERN long p_report; /* 'report' */
#if defined(FEAT_WINDOWS) && defined(FEAT_QUICKFIX)
EXTERN long p_pvh; /* 'previewheight' */
diff --git a/src/regexp.c b/src/regexp.c
index e456b5d5f..a1f71ab97 100644
--- a/src/regexp.c
+++ b/src/regexp.c
@@ -38,9 +38,20 @@
* Named character class support added by Walter Briscoe (1998 Jul 01)
*/
+/* Uncomment the first if you do not want to see debugging logs or files
+ * related to regular expressions, even when compiling with -DDEBUG.
+ * Uncomment the second to get the regexp debugging. */
+/* #undef DEBUG */
+/* #define DEBUG */
+
#include "vim.h"
-#undef DEBUG
+#ifdef DEBUG
+/* show/save debugging data when BT engine is used */
+# define BT_REGEXP_DUMP
+/* save the debugging data to a file instead of displaying it */
+# define BT_REGEXP_LOG
+#endif
/*
* The "internal use only" fields in regexp.h are present to pass info from
@@ -326,9 +337,10 @@ toggle_Magic(x)
/* Used for an error (down from) vim_regcomp(): give the error message, set
* rc_did_emsg and return NULL */
#define EMSG_RET_NULL(m) return (EMSG(m), rc_did_emsg = TRUE, (void *)NULL)
-#define EMSG_M_RET_NULL(m, c) return (EMSG2((m), (c) ? "" : "\\"), rc_did_emsg = TRUE, (void *)NULL)
#define EMSG_RET_FAIL(m) return (EMSG(m), rc_did_emsg = TRUE, FAIL)
-#define EMSG_ONE_RET_NULL EMSG_M_RET_NULL(_("E369: invalid item in %s%%[]"), reg_magic == MAGIC_ALL)
+#define EMSG2_RET_NULL(m, c) return (EMSG2((m), (c) ? "" : "\\"), rc_did_emsg = TRUE, (void *)NULL)
+#define EMSG2_RET_FAIL(m, c) return (EMSG2((m), (c) ? "" : "\\"), rc_did_emsg = TRUE, FAIL)
+#define EMSG_ONE_RET_NULL EMSG2_RET_NULL(_("E369: invalid item in %s%%[]"), reg_magic == MAGIC_ALL)
#define MAX_LIMIT (32767L << 16L)
@@ -336,11 +348,18 @@ static int re_multi_type __ARGS((int));
static int cstrncmp __ARGS((char_u *s1, char_u *s2, int *n));
static char_u *cstrchr __ARGS((char_u *, int));
+#ifdef BT_REGEXP_DUMP
+static void regdump __ARGS((char_u *, bt_regprog_T *));
+#endif
#ifdef DEBUG
-static void regdump __ARGS((char_u *, regprog_T *));
static char_u *regprop __ARGS((char_u *));
#endif
+static char_u e_missingbracket[] = N_("E769: Missing ] after %s[");
+static char_u e_unmatchedpp[] = N_("E53: Unmatched %s%%(");
+static char_u e_unmatchedp[] = N_("E54: Unmatched %s(");
+static char_u e_unmatchedpar[] = N_("E55: Unmatched %s)");
+
#define NOT_MULTI 0
#define MULTI_ONE 1
#define MULTI_MULT 2
@@ -630,7 +649,13 @@ static char_u META_flags[] = {
};
#endif
-static int curchr;
+static int curchr; /* currently parsed character */
+/* Previous character. Note: prevchr is sometimes -1 when we are not at the
+ * start, eg in /[ ^I]^ the pattern was never found even if it existed,
+ * because ^ was taken to be magic -- webb */
+static int prevchr;
+static int prevprevchr; /* previous-previous character */
+static int nextchr; /* used for ungetchr() */
/* arguments for reg() */
#define REG_NOPAREN 0 /* toplevel reg() */
@@ -680,6 +705,9 @@ static int read_limits __ARGS((long *, long *));
static void regtail __ARGS((char_u *, char_u *));
static void regoptail __ARGS((char_u *, char_u *));
+static regengine_T bt_regengine;
+static regengine_T nfa_regengine;
+
/*
* Return TRUE if compiled regular expression "prog" can match a line break.
*/
@@ -762,6 +790,7 @@ char *EQUIVAL_CLASS_C[16] = {
/*
* Produce the bytes for equivalence class "c".
* Currently only handles latin1, latin9 and utf-8.
+ * NOTE: When changing this function, also change nfa_emit_equi_class()
*/
static void
reg_equi_class(c)
@@ -1239,8 +1268,11 @@ skip_regexp(startp, dirc, magic, newp)
return p;
}
+static regprog_T *bt_regcomp __ARGS((char_u *expr, int re_flags));
+
/*
- * vim_regcomp() - compile a regular expression into internal code
+ * bt_regcomp() - compile a regular expression into internal code for the
+ * traditional back track matcher.
* Returns the program in allocated space. Returns NULL for an error.
*
* We can't allocate space until we know how big the compiled form will be,
@@ -1259,12 +1291,12 @@ skip_regexp(startp, dirc, magic, newp)
* of the structure of the compiled regexp.
* "re_flags": RE_MAGIC and/or RE_STRING.
*/
- regprog_T *
-vim_regcomp(expr, re_flags)
+ static regprog_T *
+bt_regcomp(expr, re_flags)
char_u *expr;
int re_flags;
{
- regprog_T *r;
+ bt_regprog_T *r;
char_u *scan;
char_u *longest;
int len;
@@ -1291,7 +1323,7 @@ vim_regcomp(expr, re_flags)
#endif
/* Allocate space. */
- r = (regprog_T *)lalloc(sizeof(regprog_T) + regsize, TRUE);
+ r = (bt_regprog_T *)lalloc(sizeof(bt_regprog_T) + regsize, TRUE);
if (r == NULL)
return NULL;
@@ -1386,10 +1418,11 @@ vim_regcomp(expr, re_flags)
r->regmlen = len;
}
}
-#ifdef DEBUG
+#ifdef BT_REGEXP_DUMP
regdump(expr, r);
#endif
- return r;
+ r->engine = &bt_regengine;
+ return (regprog_T *)r;
}
/*
@@ -1436,7 +1469,7 @@ vim_regcomp_had_eol()
#endif
/*
- * reg - regular expression, i.e. main body or parenthesized thing
+ * Parse regular expression, i.e. main body or parenthesized thing.
*
* Caller must absorb opening parenthesis.
*
@@ -1473,7 +1506,7 @@ reg(paren, flagp)
{
/* Make a MOPEN node. */
if (regnpar >= NSUBEXP)
- EMSG_M_RET_NULL(_("E51: Too many %s("), reg_magic == MAGIC_ALL);
+ EMSG2_RET_NULL(_("E51: Too many %s("), reg_magic == MAGIC_ALL);
parno = regnpar;
++regnpar;
ret = regnode(MOPEN + parno);
@@ -1534,14 +1567,14 @@ reg(paren, flagp)
else
#endif
if (paren == REG_NPAREN)
- EMSG_M_RET_NULL(_("E53: Unmatched %s%%("), reg_magic == MAGIC_ALL);
+ EMSG2_RET_NULL(_(e_unmatchedpp), reg_magic == MAGIC_ALL);
else
- EMSG_M_RET_NULL(_("E54: Unmatched %s("), reg_magic == MAGIC_ALL);
+ EMSG2_RET_NULL(_(e_unmatchedp), reg_magic == MAGIC_ALL);
}
else if (paren == REG_NOPAREN && peekchr() != NUL)
{
if (curchr == Magic(')'))
- EMSG_M_RET_NULL(_("E55: Unmatched %s)"), reg_magic == MAGIC_ALL);
+ EMSG2_RET_NULL(_(e_unmatchedpar), reg_magic == MAGIC_ALL);
else
EMSG_RET_NULL(_(e_trailing)); /* "Can't happen". */
/* NOTREACHED */
@@ -1556,7 +1589,7 @@ reg(paren, flagp)
}
/*
- * Handle one alternative of an | operator.
+ * Parse one alternative of an | operator.
* Implements the & operator.
*/
static char_u *
@@ -1599,7 +1632,7 @@ regbranch(flagp)
}
/*
- * Handle one alternative of an | or & operator.
+ * Parse one alternative of an | or & operator.
* Implements the concatenation operator.
*/
static char_u *
@@ -1679,7 +1712,7 @@ regconcat(flagp)
}
/*
- * regpiece - something followed by possible [*+=]
+ * Parse something followed by possible [*+=].
*
* Note that the branching code sequences used for = and the general cases
* of * and + are somewhat optimized: they use the same NOTHING node as
@@ -1759,7 +1792,7 @@ regpiece(flagp)
}
}
if (lop == END)
- EMSG_M_RET_NULL(_("E59: invalid character after %s@"),
+ EMSG2_RET_NULL(_("E59: invalid character after %s@"),
reg_magic == MAGIC_ALL);
/* Look behind must match with behind_pos. */
if (lop == BEHIND || lop == NOBEHIND)
@@ -1793,7 +1826,7 @@ regpiece(flagp)
else
{
if (num_complex_braces >= 10)
- EMSG_M_RET_NULL(_("E60: Too many complex %s{...}s"),
+ EMSG2_RET_NULL(_("E60: Too many complex %s{...}s"),
reg_magic == MAGIC_ALL);
reginsert(BRACE_COMPLEX + num_complex_braces, ret);
regoptail(ret, regnode(BACK));
@@ -1820,8 +1853,20 @@ regpiece(flagp)
return ret;
}
+/* When making changes to classchars also change nfa_classcodes. */
+static char_u *classchars = (char_u *)".iIkKfFpPsSdDxXoOwWhHaAlLuU";
+static int classcodes[] = {
+ ANY, IDENT, SIDENT, KWORD, SKWORD,
+ FNAME, SFNAME, PRINT, SPRINT,
+ WHITE, NWHITE, DIGIT, NDIGIT,
+ HEX, NHEX, OCTAL, NOCTAL,
+ WORD, NWORD, HEAD, NHEAD,
+ ALPHA, NALPHA, LOWER, NLOWER,
+ UPPER, NUPPER
+};
+
/*
- * regatom - the lowest level
+ * Parse the lowest level.
*
* Optimization: gobbles an entire sequence of ordinary characters so that
* it can turn them into a single node, which is smaller to store and
@@ -1836,15 +1881,6 @@ regatom(flagp)
int cpo_lit; /* 'cpoptions' contains 'l' flag */
int cpo_bsl; /* 'cpoptions' contains '\' flag */
int c;
- static char_u *classchars = (char_u *)".iIkKfFpPsSdDxXoOwWhHaAlLuU";
- static int classcodes[] = {ANY, IDENT, SIDENT, KWORD, SKWORD,
- FNAME, SFNAME, PRINT, SPRINT,
- WHITE, NWHITE, DIGIT, NDIGIT,
- HEX, NHEX, OCTAL, NOCTAL,
- WORD, NWORD, HEAD, NHEAD,
- ALPHA, NALPHA, LOWER, NLOWER,
- UPPER, NUPPER
- };
char_u *p;
int extra = 0;
@@ -2140,7 +2176,7 @@ regatom(flagp)
while ((c = getchr()) != ']')
{
if (c == NUL)
- EMSG_M_RET_NULL(_("E69: Missing ] after %s%%["),
+ EMSG2_RET_NULL(_("E69: Missing ] after %s%%["),
reg_magic == MAGIC_ALL);
br = regnode(BRANCH);
if (ret == NULL)
@@ -2156,7 +2192,7 @@ regatom(flagp)
return NULL;
}
if (ret == NULL)
- EMSG_M_RET_NULL(_("E70: Empty %s%%[]"),
+ EMSG2_RET_NULL(_("E70: Empty %s%%[]"),
reg_magic == MAGIC_ALL);
lastbranch = regnode(BRANCH);
br = regnode(NOTHING);
@@ -2200,7 +2236,7 @@ regatom(flagp)
}
if (i < 0)
- EMSG_M_RET_NULL(
+ EMSG2_RET_NULL(
_("E678: Invalid character after %s%%[dxouU]"),
reg_magic == MAGIC_ALL);
#ifdef FEAT_MBYTE
@@ -2272,7 +2308,7 @@ regatom(flagp)
}
}
- EMSG_M_RET_NULL(_("E71: Invalid character after %s%%"),
+ EMSG2_RET_NULL(_("E71: Invalid character after %s%%"),
reg_magic == MAGIC_ALL);
}
}
@@ -2567,8 +2603,7 @@ collection:
break;
}
else if (reg_strict)
- EMSG_M_RET_NULL(_("E769: Missing ] after %s["),
- reg_magic > MAGIC_OFF);
+ EMSG2_RET_NULL(_(e_missingbracket), reg_magic > MAGIC_OFF);
}
/* FALLTHROUGH */
@@ -2659,7 +2694,7 @@ use_multibytecode(c)
#endif
/*
- * emit a node
+ * Emit a node.
* Return pointer to generated code.
*/
static char_u *
@@ -2711,7 +2746,7 @@ regmbc(c)
#endif
/*
- * reginsert - insert an operator in front of already-emitted operand
+ * Insert an operator in front of already-emitted operand
*
* Means relocating the operand.
*/
@@ -2742,7 +2777,7 @@ reginsert(op, opnd)
}
/*
- * reginsert_limits - insert an operator in front of already-emitted operand.
+ * Insert an operator in front of already-emitted operand.
* The operator has the given limit values as operands. Also set next pointer.
*
* Means relocating the operand.
@@ -2794,7 +2829,7 @@ re_put_long(p, val)
}
/*
- * regtail - set the next-pointer at the end of a node chain
+ * Set the next-pointer at the end of a node chain.
*/
static void
regtail(p, val)
@@ -2835,7 +2870,7 @@ regtail(p, val)
}
/*
- * regoptail - regtail on item after a BRANCH; nop if none
+ * Like regtail, on item after a BRANCH; nop if none.
*/
static void
regoptail(p, val)
@@ -2851,22 +2886,15 @@ regoptail(p, val)
}
/*
- * getchr() - get the next character from the pattern. We know about
- * magic and such, so therefore we need a lexical analyzer.
+ * Functions for getting characters from the regexp input.
*/
-/* static int curchr; */
-static int prevprevchr;
-static int prevchr;
-static int nextchr; /* used for ungetchr() */
-/*
- * Note: prevchr is sometimes -1 when we are not at the start,
- * eg in /[ ^I]^ the pattern was never found even if it existed, because ^ was
- * taken to be magic -- webb
- */
static int at_start; /* True when on the first character */
static int prev_at_start; /* True when on the second character */
+/*
+ * Start parsing at "str".
+ */
static void
initchr(str)
char_u *str;
@@ -2878,6 +2906,9 @@ initchr(str)
prev_at_start = FALSE;
}
+/*
+ * Get the next character without advancing.
+ */
static int
peekchr()
{
@@ -3086,6 +3117,10 @@ skipchr_keepstart()
prevprevchr = prpr;
}
+/*
+ * Get the next character from the pattern. We know about magic and such, so
+ * therefore we need a lexical analyzer.
+ */
static int
getchr()
{
@@ -3340,8 +3375,8 @@ typedef struct regbehind_S
} regbehind_T;
static char_u *reg_getline __ARGS((linenr_T lnum));
-static long vim_regexec_both __ARGS((char_u *line, colnr_T col, proftime_T *tm));
-static long regtry __ARGS((regprog_T *prog, colnr_T col));
+static long bt_regexec_both __ARGS((char_u *line, colnr_T col, proftime_T *tm));
+static long regtry __ARGS((bt_regprog_T *prog, colnr_T col));
static void cleanup_subexpr __ARGS((void));
#ifdef FEAT_SYN_HL
static void cleanup_zsubexpr __ARGS((void));
@@ -3398,7 +3433,7 @@ static colnr_T ireg_maxcol;
/*
* Sometimes need to save a copy of a line. Since alloc()/free() is very
* slow, we keep one allocated piece of memory and only re-allocate it when
- * it's too small. It's freed in vim_regexec_both() when finished.
+ * it's too small. It's freed in bt_regexec_both() when finished.
*/
static char_u *reg_tofree = NULL;
static unsigned reg_tofreelen;
@@ -3556,6 +3591,8 @@ static lpos_T reg_endzpos[NSUBEXP]; /* idem, end pos */
/* TRUE if using multi-line regexp. */
#define REG_MULTI (reg_match == NULL)
+static int bt_regexec __ARGS((regmatch_T *rmp, char_u *line, colnr_T col));
+
/*
* Match a regexp against a string.
* "rmp->regprog" is a compiled regexp as returned by vim_regcomp().
@@ -3563,8 +3600,8 @@ static lpos_T reg_endzpos[NSUBEXP]; /* idem, end pos */
*
* Return TRUE if there is a match, FALSE if not.
*/
- int
-vim_regexec(rmp, line, col)
+ static int
+bt_regexec(rmp, line, col)
regmatch_T *rmp;
char_u *line; /* string to match against */
colnr_T col; /* column to start looking for match */
@@ -3580,16 +3617,19 @@ vim_regexec(rmp, line, col)
ireg_icombine = FALSE;
#endif
ireg_maxcol = 0;
- return (vim_regexec_both(line, col, NULL) != 0);
+ return (bt_regexec_both(line, col, NULL) != 0);
}
#if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
|| defined(FIND_REPLACE_DIALOG) || defined(PROTO)
+
+static int bt_regexec_nl __ARGS((regmatch_T *rmp, char_u *line, colnr_T col));
+
/*
* Like vim_regexec(), but consider a "\n" in "line" to be a line break.
*/
- int
-vim_regexec_nl(rmp, line, col)
+ static int
+bt_regexec_nl(rmp, line, col)
regmatch_T *rmp;
char_u *line; /* string to match against */
colnr_T col; /* column to start looking for match */
@@ -3605,10 +3645,12 @@ vim_regexec_nl(rmp, line, col)
ireg_icombine = FALSE;
#endif
ireg_maxcol = 0;
- return (vim_regexec_both(line, col, NULL) != 0);
+ return (bt_regexec_both(line, col, NULL) != 0);
}
#endif
+static long bt_regexec_multi __ARGS((regmmatch_T *rmp, win_T *win, buf_T *buf, linenr_T lnum, colnr_T col, proftime_T *tm));
+
/*
* Match a regexp against multiple lines.
* "rmp->regprog" is a compiled regexp as returned by vim_regcomp().
@@ -3617,8 +3659,8 @@ vim_regexec_nl(rmp, line, col)
* Return zero if there is no match. Return number of lines contained in the
* match otherwise.
*/
- long
-vim_regexec_multi(rmp, win, buf, lnum, col, tm)
+ static long
+bt_regexec_multi(rmp, win, buf, lnum, col, tm)
regmmatch_T *rmp;
win_T *win; /* window in which to search or NULL */
buf_T *buf; /* buffer in which to search */
@@ -3641,7 +3683,7 @@ vim_regexec_multi(rmp, win, buf, lnum, col, tm)
#endif
ireg_maxcol = rmp->rmm_maxcol;
- r = vim_regexec_both(NULL, col, tm);
+ r = bt_regexec_both(NULL, col, tm);
return r;
}
@@ -3651,12 +3693,12 @@ vim_regexec_multi(rmp, win, buf, lnum, col, tm)
* lines ("line" is NULL, use reg_getline()).
*/
static long
-vim_regexec_both(line, col, tm)
+bt_regexec_both(line, col, tm)
char_u *line;
colnr_T col; /* column to start looking for match */
proftime_T *tm UNUSED; /* timeout limit or NULL */
{
- regprog_T *prog;
+ bt_regprog_T *prog;
char_u *s;
long retval = 0L;
@@ -3682,14 +3724,14 @@ vim_regexec_both(line, col, tm)
if (REG_MULTI)
{
- prog = reg_mmatch->regprog;
+ prog = (bt_regprog_T *)reg_mmatch->regprog;
line = reg_getline((linenr_T)0);
reg_startpos = reg_mmatch->startpos;
reg_endpos = reg_mmatch->endpos;
}
else
{
- prog = reg_match->regprog;
+ prog = (bt_regprog_T *)reg_match->regprog;
reg_startp = reg_match->startp;
reg_endp = reg_match->endp;
}
@@ -3931,7 +3973,7 @@ unref_extmatch(em)
*/
static long
regtry(prog, col)
- regprog_T *prog;
+ bt_regprog_T *prog;
colnr_T col;
{
reginput = regline + col;
@@ -4063,7 +4105,7 @@ regmatch(scan)
#define RA_NOMATCH 5 /* didn't match */
/* Make "regstack" and "backpos" empty. They are allocated and freed in
- * vim_regexec_both() to reduce malloc()/free() calls. */
+ * bt_regexec_both() to reduce malloc()/free() calls. */
regstack.ga_len = 0;
backpos.ga_len = 0;
@@ -4072,14 +4114,14 @@ regmatch(scan)
*/
for (;;)
{
- /* Some patterns my cause a long time to match, even though they are not
+ /* Some patterns may cause a long time to match, even though they are not
* illegal. E.g., "\([a-z]\+\)\+Q". Allow breaking them with CTRL-C. */
fast_breakcheck();
#ifdef DEBUG
if (scan != NULL && regnarrate)
{
- mch_errmsg(regprop(scan));
+ mch_errmsg((char *)regprop(scan));
mch_errmsg("(\n");
}
#endif
@@ -4100,7 +4142,7 @@ regmatch(scan)
#ifdef DEBUG
if (regnarrate)
{
- mch_errmsg(regprop(scan));
+ mch_errmsg((char *)regprop(scan));
mch_errmsg("...\n");
# ifdef FEAT_SYN_HL
if (re_extmatch_in != NULL)
@@ -4112,7 +4154,7 @@ regmatch(scan)
{
mch_errmsg(" \"");
if (re_extmatch_in->matches[i] != NULL)
- mch_errmsg(re_extmatch_in->matches[i]);
+ mch_errmsg((char *)re_extmatch_in->matches[i]);
mch_errmsg("\"\n");
}
}
@@ -6091,9 +6133,14 @@ regnext(p)
static int
prog_magic_wrong()
{
- if (UCHARAT(REG_MULTI
- ? reg_mmatch->regprog->program
- : reg_match->regprog->program) != REGMAGIC)
+ regprog_T *prog;
+
+ prog = REG_MULTI ? reg_mmatch->regprog : reg_match->regprog;
+ if (prog->engine == &nfa_regengine)
+ /* For NFA matcher we don't check the magic */
+ return FALSE;
+
+ if (UCHARAT(((bt_regprog_T *)prog)->program) != REGMAGIC)
{
EMSG(_(e_re_corr));
return TRUE;
@@ -6318,7 +6365,7 @@ re_num_cmp(val, scan)
}
-#ifdef DEBUG
+#ifdef BT_REGEXP_DUMP
/*
* regdump - dump a regexp onto stdout in vaguely comprehensible form
@@ -6326,14 +6373,22 @@ re_num_cmp(val, scan)
static void
regdump(pattern, r)
char_u *pattern;
- regprog_T *r;
+ bt_regprog_T *r;
{
char_u *s;
int op = EXACTLY; /* Arbitrary non-END op. */
char_u *next;
char_u *end = NULL;
+ FILE *f;
- printf("\r\nregcomp(%s):\r\n", pattern);
+#ifdef BT_REGEXP_LOG
+ f = fopen("bt_regexp_log.log", "a");
+#else
+ f = stdout;
+#endif
+ if (f == NULL)
+ return;
+ fprintf(f, "-------------------------------------\n\r\nregcomp(%s):\r\n", pattern);
s = r->program + 1;
/*
@@ -6343,18 +6398,18 @@ regdump(pattern, r)
while (op != END || s <= end)
{
op = OP(s);
- printf("%2d%s", (int)(s - r->program), regprop(s)); /* Where, what. */
+ fprintf(f, "%2d%s", (int)(s - r->program), regprop(s)); /* Where, what. */
next = regnext(s);
if (next == NULL) /* Next ptr. */
- printf("(0)");
+ fprintf(f, "(0)");
else
- printf("(%d)", (int)((s - r->program) + (next - s)));
+ fprintf(f, "(%d)", (int)((s - r->program) + (next - s)));
if (end < next)
end = next;
if (op == BRACE_LIMITS)
{
/* Two short ints */
- printf(" minval %ld, maxval %ld", OPERAND_MIN(s), OPERAND_MAX(s));
+ fprintf(f, " minval %ld, maxval %ld", OPERAND_MIN(s), OPERAND_MAX(s));
s += 8;
}
s += 3;
@@ -6363,25 +6418,33 @@ regdump(pattern, r)
|| op == EXACTLY)
{
/* Literal string, where present. */
+ fprintf(f, "\nxxxxxxxxx\n");
while (*s != NUL)
- printf("%c", *s++);
+ fprintf(f, "%c", *s++);
+ fprintf(f, "\nxxxxxxxxx\n");
s++;
}
- printf("\r\n");
+ fprintf(f, "\r\n");
}
/* Header fields of interest. */
if (r->regstart != NUL)
- printf("start `%s' 0x%x; ", r->regstart < 256
+ fprintf(f, "start `%s' 0x%x; ", r->regstart < 256
? (char *)transchar(r->regstart)
: "multibyte", r->regstart);
if (r->reganch)
- printf("anchored; ");
+ fprintf(f, "anchored; ");
if (r->regmust != NULL)
- printf("must have \"%s\"", r->regmust);
- printf("\r\n");
+ fprintf(f, "must have \"%s\"", r->regmust);
+ fprintf(f, "\r\n");
+
+#ifdef BT_REGEXP_LOG
+ fclose(f);
+#endif
}
+#endif /* BT_REGEXP_DUMP */
+#ifdef DEBUG
/*
* regprop - printable representation of opcode
*/
@@ -6389,12 +6452,12 @@ regdump(pattern, r)
regprop(op)
char_u *op;
{
- char_u *p;
- static char_u buf[50];
+ char *p;
+ static char buf[50];
- (void) strcpy(buf, ":");
+ STRCPY(buf, ":");
- switch (OP(op))
+ switch ((int) OP(op))
{
case BOL:
p = "BOL";
@@ -6761,10 +6824,10 @@ regprop(op)
break;
}
if (p != NULL)
- (void) strcat(buf, p);
- return buf;
+ STRCAT(buf, p);
+ return (char_u *)buf;
}
-#endif
+#endif /* DEBUG */
#ifdef FEAT_MBYTE
static void mb_decompose __ARGS((int c, int *c1, int *c2, int *c3));
@@ -7667,3 +7730,187 @@ reg_submatch(no)
return retval;
}
#endif
+
+static regengine_T bt_regengine =
+{
+ bt_regcomp,
+ bt_regexec,
+#if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
+ || defined(FIND_REPLACE_DIALOG) || defined(PROTO)
+ bt_regexec_nl,
+#endif
+ bt_regexec_multi
+#ifdef DEBUG
+ ,(char_u *)""
+#endif
+};
+
+
+#include "regexp_nfa.c"
+
+static regengine_T nfa_regengine =
+{
+ nfa_regcomp,
+ nfa_regexec,
+#if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
+ || defined(FIND_REPLACE_DIALOG) || defined(PROTO)
+ nfa_regexec_nl,
+#endif
+ nfa_regexec_multi
+#ifdef DEBUG
+ ,(char_u *)""
+#endif
+};
+
+/* Which regexp engine to use? Needed for vim_regcomp().
+ * Must match with 'regexpengine'. */
+static int regexp_engine = 0;
+#define AUTOMATIC_ENGINE 0
+#define BACKTRACKING_ENGINE 1
+#define NFA_ENGINE 2
+#ifdef DEBUG
+static char_u regname[][30] = {
+ "AUTOMATIC Regexp Engine",
+ "BACKTACKING Regexp Engine",
+ "NFA Regexp Engine"
+ };
+#endif
+
+/*
+ * Compile a regular expression into internal code.
+ * Returns the program in allocated memory. Returns NULL for an error.
+ */
+ regprog_T *
+vim_regcomp(expr_arg, re_flags)
+ char_u *expr_arg;
+ int re_flags;
+{
+ regprog_T *prog = NULL;
+ char_u *expr = expr_arg;
+
+ syntax_error = FALSE;
+ regexp_engine = p_re;
+
+ /* Check for prefix "\%#=", that sets the regexp engine */
+ if (STRNCMP(expr, "\\%#=", 4) == 0)
+ {
+ int newengine = expr[4] - '0';
+
+ if (newengine == AUTOMATIC_ENGINE
+ || newengine == BACKTRACKING_ENGINE
+ || newengine == NFA_ENGINE)
+ {
+ regexp_engine = expr[4] - '0';
+ expr += 5;
+#ifdef DEBUG
+ EMSG3("New regexp mode selected (%d): %s", regexp_engine,
+ regname[newengine]);
+#endif
+ }
+ else
+ {
+ EMSG(_("E864: \\%#= can only be followed by 0, 1, or 2. The automatic engine will be used "));
+ regexp_engine = AUTOMATIC_ENGINE;
+ }
+ }
+#ifdef DEBUG
+ bt_regengine.expr = expr;
+ nfa_regengine.expr = expr;
+#endif
+
+ /*
+ * First try the NFA engine, unless backtracking was requested.
+ */
+ if (regexp_engine != BACKTRACKING_ENGINE)
+ prog = nfa_regengine.regcomp(expr, re_flags);
+ else
+ prog = bt_regengine.regcomp(expr, re_flags);
+
+ if (prog == NULL) /* error compiling regexp with initial engine */
+ {
+#ifdef DEBUG
+ if (regexp_engine != BACKTRACKING_ENGINE) /* debugging log for NFA */
+ {
+ FILE *f;
+ f = fopen("debug.log", "a");
+ if (f)
+ {
+ if (!syntax_error)
+ fprintf(f, "NFA engine could not handle \"%s\"\n", expr);
+ else
+ fprintf(f, "Syntax error in \"%s\"\n", expr);
+ fclose(f);
+ }
+ else
+ EMSG("(NFA) Could not open \"debug.log\" to write !!!");
+ /*
+ if (syntax_error)
+ EMSG("NFA Regexp: Syntax Error !");
+ */
+ }
+#endif
+ /*
+ * If NFA engine failed, then revert to the backtracking engine.
+ * Except when there was a syntax error, which was properly handled by
+ * NFA engine.
+ */
+ if (regexp_engine == AUTOMATIC_ENGINE)
+ if (!syntax_error)
+ prog = bt_regengine.regcomp(expr, re_flags);
+
+ } /* endif prog==NULL */
+
+
+ return prog;
+}
+
+/*
+ * Match a regexp against a string.
+ * "rmp->regprog" is a compiled regexp as returned by vim_regcomp().
+ * Uses curbuf for line count and 'iskeyword'.
+ *
+ * Return TRUE if there is a match, FALSE if not.
+ */
+ int
+vim_regexec(rmp, line, col)
+ regmatch_T *rmp;
+ char_u *line; /* string to match against */
+ colnr_T col; /* column to start looking for match */
+{
+ return rmp->regprog->engine->regexec(rmp, line, col);
+}
+
+#if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
+ || defined(FIND_REPLACE_DIALOG) || defined(PROTO)
+/*
+ * Like vim_regexec(), but consider a "\n" in "line" to be a line break.
+ */
+ int
+vim_regexec_nl(rmp, line, col)
+ regmatch_T *rmp;
+ char_u *line;
+ colnr_T col;
+{
+ return rmp->regprog->engine->regexec_nl(rmp, line, col);
+}
+#endif
+
+/*
+ * Match a regexp against multiple lines.
+ * "rmp->regprog" is a compiled regexp as returned by vim_regcomp().
+ * Uses curbuf for line count and 'iskeyword'.
+ *
+ * Return zero if there is no match. Return number of lines contained in the
+ * match otherwise.
+ */
+ long
+vim_regexec_multi(rmp, win, buf, lnum, col, tm)
+ regmmatch_T *rmp;
+ win_T *win; /* window in which to search or NULL */
+ buf_T *buf; /* buffer in which to search */
+ linenr_T lnum; /* nr of line to start looking for match */
+ colnr_T col; /* column to start looking for match */
+ proftime_T *tm; /* timeout limit or NULL */
+{
+ return rmp->regprog->engine->regexec_multi(rmp, win, buf, lnum, col, tm);
+}
diff --git a/src/regexp.h b/src/regexp.h
index 09c8d0c79..55b4722b8 100644
--- a/src/regexp.h
+++ b/src/regexp.h
@@ -22,20 +22,76 @@
#define NSUBEXP 10
/*
+ * In the NFA engine: how many braces are allowed.
+ * TODO(RE): Use dynamic memory allocation instead of static, like here
+ */
+#define NFA_MAX_BRACES 20
+
+typedef struct regengine regengine_T;
+
+typedef struct thread thread_T;
+
+/*
* Structure returned by vim_regcomp() to pass on to vim_regexec().
+ * This is the general structure. For the actual matcher, two specific
+ * structures are used. See code below.
+ */
+typedef struct regprog
+{
+ regengine_T *engine;
+ unsigned regflags;
+} regprog_T;
+
+/*
+ * Structure used by the back track matcher.
* These fields are only to be used in regexp.c!
- * See regep.c for an explanation.
+ * See regexp.c for an explanation.
*/
typedef struct
{
+ /* These two members implement regprog_T */
+ regengine_T *engine;
+ unsigned regflags;
+
int regstart;
char_u reganch;
char_u *regmust;
int regmlen;
- unsigned regflags;
char_u reghasz;
- char_u program[1]; /* actually longer.. */
-} regprog_T;
+ char_u program[1]; /* actually longer.. */
+} bt_regprog_T;
+
+/*
+ * Structure representing a NFA state.
+ * A NFA state may have no outgoing edge, when it is a NFA_MATCH state.
+ */
+typedef struct nfa_state nfa_state_T;
+struct nfa_state
+{
+ int c;
+ nfa_state_T *out;
+ nfa_state_T *out1;
+ int id;
+ int lastlist;
+ int visits;
+ thread_T *lastthread;
+ int negated;
+};
+
+/*
+ * Structure used by the NFA matcher.
+ */
+typedef struct
+{
+ /* These two members implement regprog_T */
+ regengine_T *engine;
+ unsigned regflags;
+
+ regprog_T regprog;
+ nfa_state_T *start;
+ int nstate;
+ nfa_state_T state[0]; /* actually longer.. */
+} nfa_regprog_T;
/*
* Structure to be used for single-line matching.
@@ -78,4 +134,18 @@ typedef struct
char_u *matches[NSUBEXP];
} reg_extmatch_T;
+struct regengine
+{
+ regprog_T *(*regcomp)(char_u*, int);
+ int (*regexec)(regmatch_T*, char_u*, colnr_T);
+#if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
+ || defined(FIND_REPLACE_DIALOG) || defined(PROTO)
+ int (*regexec_nl)(regmatch_T*, char_u*, colnr_T);
+#endif
+ long (*regexec_multi)(regmmatch_T*, win_T*, buf_T*, linenr_T, colnr_T, proftime_T*);
+#ifdef DEBUG
+ char_u *expr;
+#endif
+};
+
#endif /* _REGEXP_H */
diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
new file mode 100644
index 000000000..51e355a5f
--- /dev/null
+++ b/src/regexp_nfa.c
@@ -0,0 +1,3819 @@
+/* vi:set ts=8 sts=4 sw=4:
+ *
+ * NFA regular expression implementation.
+ *
+ * This file is included in "regexp.c".
+ */
+
+#ifdef DEBUG
+/* Comment this out to disable log files. They can get pretty big */
+# define ENABLE_LOG
+# define LOG_NAME "log_nfarun.log"
+#endif
+
+/* Upper limit allowed for {m,n} repetitions handled by NFA */
+#define NFA_BRACES_MAXLIMIT 10
+/* For allocating space for the postfix representation */
+#define NFA_POSTFIX_MULTIPLIER (NFA_BRACES_MAXLIMIT + 2)*2
+/* Size of stack, used when converting the postfix regexp into NFA */
+#define NFA_STACK_SIZE 1024
+
+enum
+{
+ NFA_SPLIT = -1024,
+ NFA_MATCH,
+ NFA_SKIP_CHAR, /* matches a 0-length char */
+ NFA_END_NEG_RANGE, /* Used when expanding [^ab] */
+
+ NFA_CONCAT,
+ NFA_OR,
+ NFA_STAR,
+ NFA_PLUS,
+ NFA_QUEST,
+ NFA_QUEST_NONGREEDY, /* Non-greedy version of \? */
+ NFA_NOT, /* used for [^ab] negated char ranges */
+
+ NFA_BOL, /* ^ Begin line */
+ NFA_EOL, /* $ End line */
+ NFA_BOW, /* \< Begin word */
+ NFA_EOW, /* \> End word */
+ NFA_BOF, /* \%^ Begin file */
+ NFA_EOF, /* \%$ End file */
+ NFA_NEWL,
+ NFA_ZSTART, /* Used for \zs */
+ NFA_ZEND, /* Used for \ze */
+ NFA_NOPEN, /* Start of subexpression marked with \%( */
+ NFA_NCLOSE, /* End of subexpr. marked with \%( ... \) */
+ NFA_START_INVISIBLE,
+ NFA_END_INVISIBLE,
+ NFA_MULTIBYTE, /* Next nodes in NFA are part of the same
+ multibyte char */
+ NFA_END_MULTIBYTE, /* End of multibyte char in the NFA */
+ NFA_COMPOSING, /* Next nodes in NFA are part of the
+ composing multibyte char */
+ NFA_END_COMPOSING, /* End of a composing char in the NFA */
+
+ /* The following are used only in the postfix form, not in the NFA */
+ NFA_PREV_ATOM_NO_WIDTH, /* Used for \@= */
+ NFA_PREV_ATOM_NO_WIDTH_NEG, /* Used for \@! */
+ NFA_PREV_ATOM_JUST_BEFORE, /* Used for \@<= */
+ NFA_PREV_ATOM_JUST_BEFORE_NEG, /* Used for \@<! */
+ NFA_PREV_ATOM_LIKE_PATTERN, /* Used for \@> */
+
+ NFA_MOPEN,
+ NFA_MCLOSE = NFA_MOPEN + NSUBEXP,
+
+ /* NFA_FIRST_NL */
+ NFA_ANY = NFA_MCLOSE + NSUBEXP, /* Match any one character. */
+ NFA_ANYOF, /* Match any character in this string. */
+ NFA_ANYBUT, /* Match any character not in this string. */
+ NFA_IDENT, /* Match identifier char */
+ NFA_SIDENT, /* Match identifier char but no digit */
+ NFA_KWORD, /* Match keyword char */
+ NFA_SKWORD, /* Match word char but no digit */
+ NFA_FNAME, /* Match file name char */
+ NFA_SFNAME, /* Match file name char but no digit */
+ NFA_PRINT, /* Match printable char */
+ NFA_SPRINT, /* Match printable char but no digit */
+ NFA_WHITE, /* Match whitespace char */
+ NFA_NWHITE, /* Match non-whitespace char */
+ NFA_DIGIT, /* Match digit char */
+ NFA_NDIGIT, /* Match non-digit char */
+ NFA_HEX, /* Match hex char */
+ NFA_NHEX, /* Match non-hex char */
+ NFA_OCTAL, /* Match octal char */
+ NFA_NOCTAL, /* Match non-octal char */
+ NFA_WORD, /* Match word char */
+ NFA_NWORD, /* Match non-word char */
+ NFA_HEAD, /* Match head char */
+ NFA_NHEAD, /* Match non-head char */
+ NFA_ALPHA, /* Match alpha char */
+ NFA_NALPHA, /* Match non-alpha char */
+ NFA_LOWER, /* Match lowercase char */
+ NFA_NLOWER, /* Match non-lowercase char */
+ NFA_UPPER, /* Match uppercase char */
+ NFA_NUPPER, /* Match non-uppercase char */
+ NFA_FIRST_NL = NFA_ANY + ADD_NL,
+ NFA_LAST_NL = NFA_NUPPER + ADD_NL,
+
+ /* Character classes [:alnum:] etc */
+ NFA_CLASS_ALNUM,
+ NFA_CLASS_ALPHA,
+ NFA_CLASS_BLANK,
+ NFA_CLASS_CNTRL,
+ NFA_CLASS_DIGIT,
+ NFA_CLASS_GRAPH,
+ NFA_CLASS_LOWER,
+ NFA_CLASS_PRINT,
+ NFA_CLASS_PUNCT,
+ NFA_CLASS_SPACE,
+ NFA_CLASS_UPPER,
+ NFA_CLASS_XDIGIT,
+ NFA_CLASS_TAB,
+ NFA_CLASS_RETURN,
+ NFA_CLASS_BACKSPACE,
+ NFA_CLASS_ESCAPE
+};
+
+/* Keep in sync with classchars. */
+static int nfa_classcodes[] = {
+ NFA_ANY, NFA_IDENT, NFA_SIDENT, NFA_KWORD,NFA_SKWORD,
+ NFA_FNAME, NFA_SFNAME, NFA_PRINT, NFA_SPRINT,
+ NFA_WHITE, NFA_NWHITE, NFA_DIGIT, NFA_NDIGIT,
+ NFA_HEX, NFA_NHEX, NFA_OCTAL, NFA_NOCTAL,
+ NFA_WORD, NFA_NWORD, NFA_HEAD, NFA_NHEAD,
+ NFA_ALPHA, NFA_NALPHA, NFA_LOWER, NFA_NLOWER,
+ NFA_UPPER, NFA_NUPPER
+};
+
+static char_u e_misplaced[] = N_("E866: (NFA regexp) Misplaced %c");
+
+/*
+ * NFA errors can be of 3 types:
+ * *** NFA runtime errors, when something unknown goes wrong. The NFA fails
+ * silently and revert the to backtracking engine.
+ * syntax_error = FALSE;
+ * *** Regexp syntax errors, when the input regexp is not syntactically correct.
+ * The NFA engine displays an error message, and nothing else happens.
+ * syntax_error = TRUE
+ * *** Unsupported features, when the input regexp uses an operator that is not
+ * implemented in the NFA. The NFA engine fails silently, and reverts to the
+ * old backtracking engine.
+ * syntax_error = FALSE
+ * "The NFA fails" means that "compiling the regexp with the NFA fails":
+ * nfa_regcomp() returns FAIL.
+ */
+static int syntax_error = FALSE;
+
+/* NFA regexp \ze operator encountered. */
+static int nfa_has_zend = FALSE;
+
+static int *post_start; /* holds the postfix form of r.e. */
+static int *post_end;
+static int *post_ptr;
+
+static int nstate; /* Number of states in the NFA. */
+static int istate; /* Index in the state vector, used in new_state() */
+static int nstate_max; /* Upper bound of estimated number of states. */
+
+
+static int nfa_regcomp_start __ARGS((char_u*expr, int re_flags));
+static int nfa_recognize_char_class __ARGS((char_u *start, char_u *end, int extra_newl));
+static int nfa_emit_equi_class __ARGS((int c, int neg));
+static void nfa_inc __ARGS((char_u **p));
+static void nfa_dec __ARGS((char_u **p));
+static int nfa_regatom __ARGS((void));
+static int nfa_regpiece __ARGS((void));
+static int nfa_regconcat __ARGS((void));
+static int nfa_regbranch __ARGS((void));
+static int nfa_reg __ARGS((int paren));
+#ifdef DEBUG
+static void nfa_set_code __ARGS((int c));
+static void nfa_postfix_dump __ARGS((char_u *expr, int retval));
+static void nfa_print_state __ARGS((FILE *debugf, nfa_state_T *state, int ident));
+static void nfa_dump __ARGS((nfa_regprog_T *prog));
+#endif
+static int *re2post __ARGS((void));
+static nfa_state_T *new_state __ARGS((int c, nfa_state_T *out, nfa_state_T *out1));
+static nfa_state_T *post2nfa __ARGS((int *postfix, int *end, int nfa_calc_size));
+static int check_char_class __ARGS((int class, int c));
+static void st_error __ARGS((int *postfix, int *end, int *p));
+static void nfa_save_listids __ARGS((nfa_state_T *start, int *list));
+static void nfa_restore_listids __ARGS((nfa_state_T *start, int *list));
+static void nfa_set_null_listids __ARGS((nfa_state_T *start));
+static void nfa_set_neg_listids __ARGS((nfa_state_T *start));
+static long nfa_regtry __ARGS((nfa_state_T *start, colnr_T col));
+static long nfa_regexec_both __ARGS((char_u *line, colnr_T col));
+static regprog_T *nfa_regcomp __ARGS((char_u *expr, int re_flags));
+static int nfa_regexec __ARGS((regmatch_T *rmp, char_u *line, colnr_T col));
+static long nfa_regexec_multi __ARGS((regmmatch_T *rmp, win_T *win, buf_T *buf, linenr_T lnum, colnr_T col, proftime_T *tm));
+
+/* helper functions used when doing re2post() ... regatom() parsing */
+#define EMIT(c) do { \
+ if (post_ptr >= post_end) \
+ return FAIL; \
+ *post_ptr++ = c; \
+ } while (0)
+
+#define EMIT_MBYTE(c) \
+ len = (*mb_char2bytes)(c, buf); \
+ EMIT(buf[0]); \
+ for (i = 1; i < len; i++) \
+ { \
+ EMIT(buf[i]); \
+ EMIT(NFA_CONCAT); \
+ } \
+ EMIT(NFA_MULTIBYTE);
+
+#define EMIT_COMPOSING_UTF(input) \
+ len = utfc_ptr2len(input); \
+ EMIT(input[0]); \
+ for (i = 1; i < len; i++) \
+ { \
+ EMIT(input[i]); \
+ EMIT(NFA_CONCAT); \
+ } \
+ EMIT(NFA_COMPOSING);
+
+/*
+ * Initialize internal variables before NFA compilation.
+ * Return OK on success, FAIL otherwise.
+ */
+ static int
+nfa_regcomp_start(expr, re_flags)
+ char_u *expr;
+ int re_flags; /* see vim_regcomp() */
+{
+ int postfix_size;
+
+ nstate = 0;
+ istate = 0;
+ /* A reasonable estimation for size */
+ nstate_max = (STRLEN(expr) + 1) * NFA_POSTFIX_MULTIPLIER;
+
+ /* Size for postfix representation of expr */
+ postfix_size = sizeof(*post_start) * nstate_max;
+ post_start = (int *)lalloc(postfix_size, TRUE);
+ if (post_start == NULL)
+ return FAIL;
+ vim_memset(post_start, 0, postfix_size);
+ post_ptr = post_start;
+ post_end = post_start + postfix_size;
+ nfa_has_zend = FALSE;
+
+ regcomp_start(expr, re_flags);
+
+ return OK;
+}
+
+/*
+ * Search between "start" and "end" and try to recognize a
+ * character class in expanded form. For example [0-9].
+ * On success, return the id the character class to be emitted.
+ * On failure, return 0 (=FAIL)
+ * Start points to the first char of the range, while end should point
+ * to the closing brace.
+ */
+ static int
+nfa_recognize_char_class(start, end, extra_newl)
+ char_u *start;
+ char_u *end;
+ int extra_newl;
+{
+ int i;
+ /* Each of these variables takes up a char in "config[]",
+ * in the order they are here. */
+ int not = FALSE, af = FALSE, AF = FALSE, az = FALSE, AZ = FALSE,
+ o7 = FALSE, o9 = FALSE, underscore = FALSE, newl = FALSE;
+ char_u *p;
+#define NCONFIGS 16
+ int classid[NCONFIGS] = {
+ NFA_DIGIT, NFA_NDIGIT, NFA_HEX, NFA_NHEX,
+ NFA_OCTAL, NFA_NOCTAL, NFA_WORD, NFA_NWORD,
+ NFA_HEAD, NFA_NHEAD, NFA_ALPHA, NFA_NALPHA,
+ NFA_LOWER, NFA_NLOWER, NFA_UPPER, NFA_NUPPER
+ };
+ char_u myconfig[9];
+ char_u config[NCONFIGS][9] = {
+ "000000100", /* digit */
+ "100000100", /* non digit */
+ "011000100", /* hex-digit */
+ "111000100", /* non hex-digit */
+ "000001000", /* octal-digit */
+ "100001000", /* [^0-7] */
+ "000110110", /* [0-9A-Za-z_] */
+ "100110110", /* [^0-9A-Za-z_] */
+ "000110010", /* head of word */
+ "100110010", /* not head of word */
+ "000110000", /* alphabetic char a-z */
+ "100110000", /* non alphabetic char */
+ "000100000", /* lowercase letter */
+ "100100000", /* non lowercase */
+ "000010000", /* uppercase */
+ "100010000" /* non uppercase */
+ };
+
+ if (extra_newl == TRUE)
+ newl = TRUE;
+
+ if (*end != ']')
+ return FAIL;
+ p = start;
+ if (*p == '^')
+ {
+ not = TRUE;
+ p ++;
+ }
+
+ while (p < end)
+ {
+ if (p + 2 < end && *(p + 1) == '-')
+ {
+ switch (*p)
+ {
+ case '0':
+ if (*(p + 2) == '9')
+ {
+ o9 = TRUE;
+ break;
+ }
+ else
+ if (*(p + 2) == '7')
+ {
+ o7 = TRUE;
+ break;
+ }
+ case 'a':
+ if (*(p + 2) == 'z')
+ {
+ az = TRUE;
+ break;
+ }
+ else
+ if (*(p + 2) == 'f')
+ {
+ af = TRUE;
+ break;
+ }
+ case 'A':
+ if (*(p + 2) == 'Z')
+ {
+ AZ = TRUE;
+ break;
+ }
+ else
+ if (*(p + 2) == 'F')
+ {
+ AF = TRUE;
+ break;
+ }
+ /* FALLTHROUGH */
+ default:
+ return FAIL;
+ }
+ p += 3;
+ }
+ else if (p + 1 < end && *p == '\\' && *(p + 1) == 'n')
+ {
+ newl = TRUE;
+ p += 2;
+ }
+ else if (*p == '_')
+ {
+ underscore = TRUE;
+ p ++;
+ }
+ else if (*p == '\n')
+ {
+ newl = TRUE;
+ p ++;
+ }
+ else
+ return FAIL;
+ } /* while (p < end) */
+
+ if (p != end)
+ return FAIL;
+
+ /* build the config that represents the ranges we gathered */
+ STRCPY(myconfig, "000000000");
+ if (not == TRUE)
+ myconfig[0] = '1';
+ if (af == TRUE)
+ myconfig[1] = '1';
+ if (AF == TRUE)
+ myconfig[2] = '1';
+ if (az == TRUE)
+ myconfig[3] = '1';
+ if (AZ == TRUE)
+ myconfig[4] = '1';
+ if (o7 == TRUE)
+ myconfig[5] = '1';
+ if (o9 == TRUE)
+ myconfig[6] = '1';
+ if (underscore == TRUE)
+ myconfig[7] = '1';
+ if (newl == TRUE)
+ {
+ myconfig[8] = '1';
+ extra_newl = ADD_NL;
+ }
+ /* try to recognize character classes */
+ for (i = 0; i < NCONFIGS; i++)
+ if (STRNCMP(myconfig, config[i],8) == 0)
+ return classid[i] + extra_newl;
+
+ /* fallthrough => no success so far */
+ return FAIL;
+
+#undef NCONFIGS
+}
+
+/*
+ * Produce the bytes for equivalence class "c".
+ * Currently only handles latin1, latin9 and utf-8.
+ * Emits bytes in postfix notation: 'a,b,NFA_OR,c,NFA_OR' is
+ * equivalent to 'a OR b OR c'
+ *
+ * NOTE! When changing this function, also update reg_equi_class()
+ */
+ static int
+nfa_emit_equi_class(c, neg)
+ int c;
+ int neg;
+{
+ int first = TRUE;
+ int glue = neg == TRUE ? NFA_CONCAT : NFA_OR;
+#define EMIT2(c) \
+ EMIT(c); \
+ if (neg == TRUE) { \
+ EMIT(NFA_NOT); \
+ } \
+ if (first == FALSE) \
+ EMIT(glue); \
+ else \
+ first = FALSE; \
+
+#ifdef FEAT_MBYTE
+ if (enc_utf8 || STRCMP(p_enc, "latin1") == 0
+ || STRCMP(p_enc, "iso-8859-15") == 0)
+#endif
+ {
+ switch (c)
+ {
+ case 'A': case '\300': case '\301': case '\302':
+ case '\303': case '\304': case '\305':
+ EMIT2('A'); EMIT2('\300'); EMIT2('\301');
+ EMIT2('\302'); EMIT2('\303'); EMIT2('\304');
+ EMIT2('\305');
+ return OK;
+
+ case 'C': case '\307':
+ EMIT2('C'); EMIT2('\307');
+ return OK;
+
+ case 'E': case '\310': case '\311': case '\312': case '\313':
+ EMIT2('E'); EMIT2('\310'); EMIT2('\311');
+ EMIT2('\312'); EMIT2('\313');
+ return OK;
+
+ case 'I': case '\314': case '\315': case '\316': case '\317':
+ EMIT2('I'); EMIT2('\314'); EMIT2('\315');
+ EMIT2('\316'); EMIT2('\317');
+ return OK;
+
+ case 'N': case '\321':
+ EMIT2('N'); EMIT2('\321');
+ return OK;
+
+ case 'O': case '\322': case '\323': case '\324': case '\325':
+ case '\326':
+ EMIT2('O'); EMIT2('\322'); EMIT2('\323');
+ EMIT2('\324'); EMIT2('\325'); EMIT2('\326');
+ return OK;
+
+ case 'U': case '\331': case '\332': case '\333': case '\334':
+ EMIT2('U'); EMIT2('\331'); EMIT2('\332');
+ EMIT2('\333'); EMIT2('\334');
+ return OK;
+
+ case 'Y': case '\335':
+ EMIT2('Y'); EMIT2('\335');
+ return OK;
+
+ case 'a': case '\340': case '\341': case '\342':
+ case '\343': case '\344': case '\345':
+ EMIT2('a'); EMIT2('\340'); EMIT2('\341');
+ EMIT2('\342'); EMIT2('\343'); EMIT2('\344');
+ EMIT2('\345');
+ return OK;
+
+ case 'c': case '\347':
+ EMIT2('c'); EMIT2('\347');
+ return OK;
+
+ case 'e': case '\350': case '\351': case '\352': case '\353':
+ EMIT2('e'); EMIT2('\350'); EMIT2('\351');
+ EMIT2('\352'); EMIT2('\353');
+ return OK;
+
+ case 'i': case '\354': case '\355': case '\356': case '\357':
+ EMIT2('i'); EMIT2('\354'); EMIT2('\355');
+ EMIT2('\356'); EMIT2('\357');
+ return OK;
+
+ case 'n': case '\361':
+ EMIT2('n'); EMIT2('\361');
+ return OK;
+
+ case 'o': case '\362': case '\363': case '\364': case '\365':
+ case '\366':
+ EMIT2('o'); EMIT2('\362'); EMIT2('\363');
+ EMIT2('\364'); EMIT2('\365'); EMIT2('\366');
+ return OK;
+
+ case 'u': case '\371': case '\372': case '\373': case '\374':
+ EMIT2('u'); EMIT2('\371'); EMIT2('\372');
+ EMIT2('\373'); EMIT2('\374');
+ return OK;
+
+ case 'y': case '\375': case '\377':
+ EMIT2('y'); EMIT2('\375'); EMIT2('\377');
+ return OK;
+
+ default:
+ return FAIL;
+ }
+ }
+
+ EMIT(c);
+ return OK;
+#undef EMIT2
+}
+
+/*
+ * Code to parse regular expression.
+ *
+ * We try to reuse parsing functions in regexp.c to
+ * minimize surprise and keep the syntax consistent.
+ */
+
+/*
+ * Increments the pointer "p" by one (multi-byte) character.
+ */
+ static void
+nfa_inc(p)
+ char_u **p;
+{
+#ifdef FEAT_MBYTE
+ if (has_mbyte)
+ mb_ptr2char_adv(p);
+ else
+#endif
+ *p = *p + 1;
+}
+
+/*
+ * Decrements the pointer "p" by one (multi-byte) character.
+ */
+ static void
+nfa_dec(p)
+ char_u **p;
+{
+#ifdef FEAT_MBYTE
+ char_u *p2, *oldp;
+
+ if (has_mbyte)
+ {
+ oldp = *p;
+ /* Try to find the multibyte char that advances to the current
+ * position. */
+ do
+ {
+ *p = *p - 1;
+ p2 = *p;
+ mb_ptr2char_adv(&p2);
+ } while (p2 != oldp);
+ }
+#else
+ *p = *p - 1;
+#endif
+}
+
+/*
+ * Parse the lowest level.
+ *
+ * An atom can be one of a long list of items. Many atoms match one character
+ * in the text. It is often an ordinary character or a character class.
+ * Braces can be used to make a pattern into an atom. The "\z(\)" construct
+ * is only for syntax highlighting.
+ *
+ * atom ::= ordinary-atom
+ * or \( pattern \)
+ * or \%( pattern \)
+ * or \z( pattern \)
+ */
+ static int
+nfa_regatom()
+{
+ int c;
+ int charclass;
+ int equiclass;
+ int collclass;
+ int got_coll_char;
+ char_u *p;
+ char_u *endp;
+#ifdef FEAT_MBYTE
+ char_u *old_regparse = regparse;
+ int clen;
+ int len;
+ static char_u buf[30];
+ int i;
+#endif
+ int extra = 0;
+ int first;
+ int emit_range;
+ int negated;
+ int result;
+ int startc = -1;
+ int endc = -1;
+ int oldstartc = -1;
+ int cpo_lit; /* 'cpoptions' contains 'l' flag */
+ int cpo_bsl; /* 'cpoptions' contains '\' flag */
+ int glue; /* ID that will "glue" nodes together */
+
+ cpo_lit = vim_strchr(p_cpo, CPO_LITERAL) != NULL;
+ cpo_bsl = vim_strchr(p_cpo, CPO_BACKSL) != NULL;
+
+ c = getchr();
+
+#ifdef FEAT_MBYTE
+ /* clen has the length of the current char, without composing chars */
+ clen = (*mb_char2len)(c);
+ if (has_mbyte && clen > 1)
+ goto nfa_do_multibyte;
+#endif
+ switch (c)
+ {
+ case Magic('^'):
+ EMIT(NFA_BOL);
+ break;
+
+ case Magic('$'):
+ EMIT(NFA_EOL);
+#if defined(FEAT_SYN_HL) || defined(PROTO)
+ had_eol = TRUE;
+#endif
+ break;
+
+ case Magic('<'):
+ EMIT(NFA_BOW);
+ break;
+
+ case Magic('>'):
+ EMIT(NFA_EOW);
+ break;
+
+ case Magic('_'):
+ c = no_Magic(getchr());
+ if (c == '^') /* "\_^" is start-of-line */
+ {
+ EMIT(NFA_BOL);
+ break;
+ }
+ if (c == '$') /* "\_$" is end-of-line */
+ {
+ EMIT(NFA_EOL);
+#if defined(FEAT_SYN_HL) || defined(PROTO)
+ had_eol = TRUE;
+#endif
+ break;
+ }
+
+ extra = ADD_NL;
+
+ /* "\_[" is collection plus newline */
+ if (c == '[')
+ /* TODO: make this work
+ * goto collection; */
+ return FAIL;
+
+ /* "\_x" is character class plus newline */
+ /*FALLTHROUGH*/
+
+ /*
+ * Character classes.
+ */
+ case Magic('.'):
+ case Magic('i'):
+ case Magic('I'):
+ case Magic('k'):
+ case Magic('K'):
+ case Magic('f'):
+ case Magic('F'):
+ case Magic('p'):
+ case Magic('P'):
+ case Magic('s'):
+ case Magic('S'):
+ case Magic('d'):
+ case Magic('D'):
+ case Magic('x'):
+ case Magic('X'):
+ case Magic('o'):
+ case Magic('O'):
+ case Magic('w'):
+ case Magic('W'):
+ case Magic('h'):
+ case Magic('H'):
+ case Magic('a'):
+ case Magic('A'):
+ case Magic('l'):
+ case Magic('L'):
+ case Magic('u'):
+ case Magic('U'):
+ p = vim_strchr(classchars, no_Magic(c));
+ if (p == NULL)
+ {
+ return FAIL; /* runtime error */
+ }
+#ifdef FEAT_MBYTE
+ /* When '.' is followed by a composing char ignore the dot, so that
+ * the composing char is matched here. */
+ if (enc_utf8 && c == Magic('.') && utf_iscomposing(peekchr()))
+ {
+ c = getchr();
+ goto nfa_do_multibyte;
+ }
+#endif
+ EMIT(nfa_classcodes[p - classchars]);
+ if (extra == ADD_NL)
+ {
+ EMIT(NFA_NEWL);
+ EMIT(NFA_OR);
+ regflags |= RF_HASNL;
+ }
+ break;
+
+ case Magic('n'):
+ if (reg_string)
+ /* In a string "\n" matches a newline character. */
+ EMIT(NL);
+ else
+ {
+ /* In buffer text "\n" matches the end of a line. */
+ EMIT(NFA_NEWL);
+ regflags |= RF_HASNL;
+ }
+ break;
+
+ case Magic('('):
+ if (nfa_reg(REG_PAREN) == FAIL)
+ return FAIL; /* cascaded error */
+ break;
+
+ case NUL:
+ syntax_error = TRUE;
+ EMSG_RET_FAIL(_("E865: (NFA) Regexp end encountered prematurely"));
+
+ case Magic('|'):
+ case Magic('&'):
+ case Magic(')'):
+ syntax_error = TRUE;
+ EMSG2(_(e_misplaced), no_Magic(c));
+ return FAIL;
+
+ case Magic('='):
+ case Magic('?'):
+ case Magic('+'):
+ case Magic('@'):
+ case Magic('*'):
+ case Magic('{'):
+ /* these should follow an atom, not form an atom */
+ syntax_error = TRUE;
+ EMSG2(_(e_misplaced), no_Magic(c));
+ return FAIL;
+
+ case Magic('~'): /* previous substitute pattern */
+ /* Not supported yet */
+ return FAIL;
+
+ case Magic('1'):
+ case Magic('2'):
+ case Magic('3'):
+ case Magic('4'):
+ case Magic('5'):
+ case Magic('6'):
+ case Magic('7'):
+ case Magic('8'):
+ case Magic('9'):
+ /* not supported yet */
+ return FAIL;
+
+ case Magic('z'):
+ c = no_Magic(getchr());
+ switch (c)
+ {
+ case 's':
+ EMIT(NFA_ZSTART);
+ break;
+ case 'e':
+ EMIT(NFA_ZEND);
+ nfa_has_zend = TRUE;
+ /* TODO: Currently \ze does not work properly. */
+ return FAIL;
+ /* break; */
+ case '1':
+ case '2':
+ case '3':
+ case '4':
+ case '5':
+ case '6':
+ case '7':
+ case '8':
+ case '9':
+ case '(':
+ /* \z1...\z9 and \z( not yet supported */
+ return FAIL;
+ default:
+ syntax_error = TRUE;
+ EMSG2(_("E867: (NFA) Unknown operator '\\z%c'"),
+ no_Magic(c));
+ return FAIL;
+ }
+ break;
+
+ case Magic('%'):
+ c = no_Magic(getchr());
+ switch (c)
+ {
+ /* () without a back reference */
+ case '(':
+ if (nfa_reg(REG_NPAREN) == FAIL)
+ return FAIL;
+ EMIT(NFA_NOPEN);
+ break;
+
+ case 'd': /* %d123 decimal */
+ case 'o': /* %o123 octal */
+ case 'x': /* %xab hex 2 */
+ case 'u': /* %uabcd hex 4 */
+ case 'U': /* %U1234abcd hex 8 */
+ /* Not yet supported */
+ return FAIL;
+
+ c = coll_get_char();
+#ifdef FEAT_MBYTE
+ if ((*mb_char2len)(c) > 1)
+ {
+ EMIT_MBYTE(c);
+ }
+ else
+#endif
+ EMIT(c);
+ break;
+
+ /* Catch \%^ and \%$ regardless of where they appear in the
+ * pattern -- regardless of whether or not it makes sense. */
+ case '^':
+ EMIT(NFA_BOF);
+ /* Not yet supported */
+ return FAIL;
+ break;
+
+ case '$':
+ EMIT(NFA_EOF);
+ /* Not yet supported */
+ return FAIL;
+ break;
+
+ case '#':
+ /* not supported yet */
+ return FAIL;
+ break;
+
+ case 'V':
+ /* not supported yet */
+ return FAIL;
+ break;
+
+ case '[':
+ /* \%[abc] not supported yet */
+ return FAIL;
+
+ default:
+ /* not supported yet */
+ return FAIL;
+ }
+ break;
+
+/* collection: */
+ case Magic('['):
+ /*
+ * Glue is emitted between several atoms from the [].
+ * It is either NFA_OR, or NFA_CONCAT.
+ *
+ * [abc] expands to 'a b NFA_OR c NFA_OR' (in postfix notation)
+ * [^abc] expands to 'a NFA_NOT b NFA_NOT NFA_CONCAT c NFA_NOT
+ * NFA_CONCAT NFA_END_NEG_RANGE NFA_CONCAT' (in postfix
+ * notation)
+ *
+ */
+
+
+/* Emit negation atoms, if needed.
+ * The CONCAT below merges the NOT with the previous node. */
+#define TRY_NEG() \
+ if (negated == TRUE) \
+ { \
+ EMIT(NFA_NOT); \
+ }
+
+/* Emit glue between important nodes : CONCAT or OR. */
+#define EMIT_GLUE() \
+ if (first == FALSE) \
+ EMIT(glue); \
+ else \
+ first = FALSE;
+
+ p = regparse;
+ endp = skip_anyof(p);
+ if (*endp == ']')
+ {
+ /*
+ * Try to reverse engineer character classes. For example,
+ * recognize that [0-9] stands for \d and [A-Za-z_] with \h,
+ * and perform the necessary substitutions in the NFA.
+ */
+ result = nfa_recognize_char_class(regparse, endp,
+ extra == ADD_NL);
+ if (result != FAIL)
+ {
+ if (result >= NFA_DIGIT && result <= NFA_NUPPER)
+ EMIT(result);
+ else /* must be char class + newline */
+ {
+ EMIT(result - ADD_NL);
+ EMIT(NFA_NEWL);
+ EMIT(NFA_OR);
+ }
+ regparse = endp;
+ nfa_inc(&regparse);
+ return OK;
+ }
+ /*
+ * Failed to recognize a character class. Use the simple
+ * version that turns [abc] into 'a' OR 'b' OR 'c'
+ */
+ startc = endc = oldstartc = -1;
+ first = TRUE; /* Emitting first atom in this sequence? */
+ negated = FALSE;
+ glue = NFA_OR;
+ if (*regparse == '^') /* negated range */
+ {
+ negated = TRUE;
+ glue = NFA_CONCAT;
+ nfa_inc(&regparse);
+ }
+ if (*regparse == '-')
+ {
+ startc = '-';
+ EMIT(startc);
+ TRY_NEG();
+ EMIT_GLUE();
+ nfa_inc(&regparse);
+ }
+ /* Emit the OR branches for each character in the [] */
+ emit_range = FALSE;
+ while (regparse < endp)
+ {
+ oldstartc = startc;
+ startc = -1;
+ got_coll_char = FALSE;
+ if (*regparse == '[')
+ {
+ /* Check for [: :], [= =], [. .] */
+ equiclass = collclass = 0;
+ charclass = get_char_class(&regparse);
+ if (charclass == CLASS_NONE)
+ {
+ equiclass = get_equi_class(&regparse);
+ if (equiclass == 0)
+ collclass = get_coll_element(&regparse);
+ }
+
+ /* Character class like [:alpha:] */
+ if (charclass != CLASS_NONE)
+ {
+ switch (charclass)
+ {
+ case CLASS_ALNUM:
+ EMIT(NFA_CLASS_ALNUM);
+ break;
+ case CLASS_ALPHA:
+ EMIT(NFA_CLASS_ALPHA);
+ break;
+ case CLASS_BLANK:
+ EMIT(NFA_CLASS_BLANK);
+ break;
+ case CLASS_CNTRL:
+ EMIT(NFA_CLASS_CNTRL);
+ break;
+ case CLASS_DIGIT:
+ EMIT(NFA_CLASS_DIGIT);
+ break;
+ case CLASS_GRAPH:
+ EMIT(NFA_CLASS_GRAPH);
+ break;
+ case CLASS_LOWER:
+ EMIT(NFA_CLASS_LOWER);
+ break;
+ case CLASS_PRINT:
+ EMIT(NFA_CLASS_PRINT);
+ break;
+ case CLASS_PUNCT:
+ EMIT(NFA_CLASS_PUNCT);
+ break;
+ case CLASS_SPACE:
+ EMIT(NFA_CLASS_SPACE);
+ break;
+ case CLASS_UPPER:
+ EMIT(NFA_CLASS_UPPER);
+ break;
+ case CLASS_XDIGIT:
+ EMIT(NFA_CLASS_XDIGIT);
+ break;
+ case CLASS_TAB:
+ EMIT(NFA_CLASS_TAB);
+ break;
+ case CLASS_RETURN:
+ EMIT(NFA_CLASS_RETURN);
+ break;
+ case CLASS_BACKSPACE:
+ EMIT(NFA_CLASS_BACKSPACE);
+ break;
+ case CLASS_ESCAPE:
+ EMIT(NFA_CLASS_ESCAPE);
+ break;
+ }
+ TRY_NEG();
+ EMIT_GLUE();
+ continue;
+ }
+ /* Try equivalence class [=a=] and the like */
+ if (equiclass != 0)
+ {
+ result = nfa_emit_equi_class(equiclass, negated);
+ if (result == FAIL)
+ {
+ /* should never happen */
+ EMSG_RET_FAIL(_("E868: Error building NFA with equivalence class!"));
+ }
+ EMIT_GLUE();
+ continue;
+ }
+ /* Try collating class like [. .] */
+ if (collclass != 0)
+ {
+ startc = collclass; /* allow [.a.]-x as a range */
+ /* Will emit the proper atom at the end of the
+ * while loop. */
+ }
+ }
+ /* Try a range like 'a-x' or '\t-z' */
+ if (*regparse == '-')
+ {
+ emit_range = TRUE;
+ startc = oldstartc;
+ nfa_inc(&regparse);
+ continue; /* reading the end of the range */
+ }
+
+ /* Now handle simple and escaped characters.
+ * Only "\]", "\^", "\]" and "\\" are special in Vi. Vim
+ * accepts "\t", "\e", etc., but only when the 'l' flag in
+ * 'cpoptions' is not included.
+ * Posix doesn't recognize backslash at all.
+ */
+ if (*regparse == '\\'
+ && !cpo_bsl
+ && regparse + 1 <= endp
+ && (vim_strchr(REGEXP_INRANGE, regparse[1]) != NULL
+ || (!cpo_lit
+ && vim_strchr(REGEXP_ABBR, regparse[1])
+ != NULL)
+ )
+ )
+ {
+ nfa_inc(&regparse);
+
+ if (*regparse == 'n' || *regparse == 'n')
+ startc = reg_string ? NL : NFA_NEWL;
+ else
+ if (*regparse == 'd'
+ || *regparse == 'o'
+ || *regparse == 'x'
+ || *regparse == 'u'
+ || *regparse == 'U'
+ )
+ {
+ /* TODO(RE) This needs more testing */
+ startc = coll_get_char();
+ got_coll_char = TRUE;
+ nfa_dec(&regparse);
+ }
+ else
+ {
+ /* \r,\t,\e,\b */
+ startc = backslash_trans(*regparse);
+ }
+ }
+
+ /* Normal printable char */
+ if (startc == -1)
+#ifdef FEAT_MBYTE
+ startc = (*mb_ptr2char)(regparse);
+#else
+ startc = *regparse;
+#endif
+
+ /* Previous char was '-', so this char is end of range. */
+ if (emit_range)
+ {
+ endc = startc; startc = oldstartc;
+ if (startc > endc)
+ EMSG_RET_FAIL(_(e_invrange));
+#ifdef FEAT_MBYTE
+ if (has_mbyte && ((*mb_char2len)(startc) > 1
+ || (*mb_char2len)(endc) > 1))
+ {
+ if (endc > startc + 256)
+ EMSG_RET_FAIL(_(e_invrange));
+ /* Emit the range. "startc" was already emitted, so
+ * skip it. */
+ for (c = startc + 1; c <= endc; c++)
+ {
+ if ((*mb_char2len)(c) > 1)
+ {
+ EMIT_MBYTE(c);
+ }
+ else
+ EMIT(c);
+ TRY_NEG();
+ EMIT_GLUE();
+ }
+ emit_range = FALSE;
+ }
+ else
+#endif
+ {
+#ifdef EBCDIC
+ int alpha_only = FALSE;
+
+ /* for alphabetical range skip the gaps
+ * 'i'-'j', 'r'-'s', 'I'-'J' and 'R'-'S'. */
+ if (isalpha(startc) && isalpha(endc))
+ alpha_only = TRUE;
+#endif
+ /* Emit the range. "startc" was already emitted, so
+ * skip it. */
+ for (c = startc + 1; c <= endc; c++)
+#ifdef EBCDIC
+ if (!alpha_only || isalpha(startc))
+#endif
+ {
+ EMIT(c);
+ TRY_NEG();
+ EMIT_GLUE();
+ }
+ emit_range = FALSE;
+ }
+ }
+ else
+ {
+ /*
+ * This char (startc) is not part of a range. Just
+ * emit it.
+ *
+ * Normally, simply emit startc. But if we get char
+ * code=0 from a collating char, then replace it with
+ * 0x0a.
+ *
+ * This is needed to completely mimic the behaviour of
+ * the backtracking engine.
+ */
+ if (got_coll_char == TRUE && startc == 0)
+ EMIT(0x0a);
+ else
+#ifdef FEAT_MBYTE
+ if ((*mb_char2len)(startc) > 1)
+ {
+ EMIT_MBYTE(startc);
+ }
+ else
+#endif
+ EMIT(startc);
+ TRY_NEG();
+ EMIT_GLUE();
+ }
+
+ nfa_inc(&regparse);
+ } /* while (p < endp) */
+
+ nfa_dec(&regparse);
+ if (*regparse == '-') /* if last, '-' is just a char */
+ {
+ EMIT('-');
+ TRY_NEG();
+ EMIT_GLUE();
+ }
+ nfa_inc(&regparse);
+
+ if (extra == ADD_NL) /* \_[] also matches \n */
+ {
+ EMIT(reg_string ? NL : NFA_NEWL);
+ TRY_NEG();
+ EMIT_GLUE();
+ }
+
+ /* skip the trailing ] */
+ regparse = endp;
+ nfa_inc(&regparse);
+ if (negated == TRUE)
+ {
+ /* Mark end of negated char range */
+ EMIT(NFA_END_NEG_RANGE);
+ EMIT(NFA_CONCAT);
+ }
+ return OK;
+ } /* if exists closing ] */
+ else if (reg_strict)
+ {
+ syntax_error = TRUE;
+ EMSG_RET_FAIL(_(e_missingbracket));
+ }
+
+ /* FALLTHROUGH */
+ default:
+ {
+#ifdef FEAT_MBYTE
+ int plen;
+
+nfa_do_multibyte:
+ /* length of current char, with composing chars,
+ * from pointer */
+ plen = (*mb_ptr2len)(old_regparse);
+ if (enc_utf8 && clen != plen)
+ {
+ /* A composing character is always handled as a
+ * separate atom, surrounded by NFA_COMPOSING and
+ * NFA_END_COMPOSING. Note that right now we are
+ * building the postfix form, not the NFA itself;
+ * a composing char could be: a, b, c, NFA_COMPOSING
+ * where 'a', 'b', 'c' are chars with codes > 256.
+ */
+ EMIT_COMPOSING_UTF(old_regparse);
+ regparse = old_regparse + plen;
+ }
+ else
+ /* A multi-byte character is always handled as a
+ * separate atom, surrounded by NFA_MULTIBYTE and
+ * NFA_END_MULTIBYTE */
+ if (plen > 1)
+ {
+ EMIT_MBYTE(c);
+ }
+ else
+#endif
+ {
+ c = no_Magic(c);
+ EMIT(c);
+ }
+ return OK;
+ }
+ }
+
+#undef TRY_NEG
+#undef EMIT_GLUE
+
+ return OK;
+}
+
+/*
+ * Parse something followed by possible [*+=].
+ *
+ * A piece is an atom, possibly followed by a multi, an indication of how many
+ * times the atom can be matched. Example: "a*" matches any sequence of "a"
+ * characters: "", "a", "aa", etc.
+ *
+ * piece ::= atom
+ * or atom multi
+ */
+ static int
+nfa_regpiece()
+{
+ int i;
+ int op;
+ int ret;
+ long minval, maxval;
+ int greedy = TRUE; /* Braces are prefixed with '-' ? */
+ char_u *old_regparse, *new_regparse;
+ int c2;
+ int *old_post_ptr, *my_post_start;
+ int old_regnpar;
+ int quest;
+
+ /* Save the current position in the regexp, so that we can use it if
+ * <atom>{m,n} is next. */
+ old_regparse = regparse;
+ /* Save current number of open parenthesis, so we can use it if
+ * <atom>{m,n} is next */
+ old_regnpar = regnpar;
+ /* store current pos in the postfix form, for \{m,n} involving 0s */
+ my_post_start = post_ptr;
+
+ ret = nfa_regatom();
+ if (ret == FAIL)
+ return FAIL; /* cascaded error */
+
+ op = peekchr();
+ if (re_multi_type(op) == NOT_MULTI)
+ return OK;
+
+ skipchr();
+ switch (op)
+ {
+ case Magic('*'):
+ EMIT(NFA_STAR);
+ break;
+
+ case Magic('+'):
+ /*
+ * Trick: Normally, (a*)\+ would match the whole input "aaa". The
+ * first and only submatch would be "aaa". But the backtracking
+ * engine interprets the plus as "try matching one more time", and
+ * a* matches a second time at the end of the input, the empty
+ * string.
+ * The submatch will the empty string.
+ *
+ * In order to be consistent with the old engine, we disable
+ * NFA_PLUS, and replace <atom>+ with <atom><atom>*
+ */
+ /* EMIT(NFA_PLUS); */
+ regnpar = old_regnpar;
+ regparse = old_regparse;
+ curchr = -1;
+ if (nfa_regatom() == FAIL)
+ return FAIL;
+ EMIT(NFA_STAR);
+ EMIT(NFA_CONCAT);
+ skipchr(); /* skip the \+ */
+ break;
+
+ case Magic('@'):
+ op = no_Magic(getchr());
+ switch(op)
+ {
+ case '=':
+ EMIT(NFA_PREV_ATOM_NO_WIDTH);
+ break;
+ case '!':
+ case '<':
+ case '>':
+ /* Not supported yet */
+ return FAIL;
+ default:
+ syntax_error = TRUE;
+ EMSG2(_("E869: (NFA) Unknown operator '\\@%c'"), op);
+ return FAIL;
+ }
+ break;
+
+ case Magic('?'):
+ case Magic('='):
+ EMIT(NFA_QUEST);
+ break;
+
+ case Magic('{'):
+ /* a{2,5} will expand to 'aaa?a?a?'
+ * a{-1,3} will expand to 'aa??a??', where ?? is the nongreedy
+ * version of '?'
+ * \v(ab){2,3} will expand to '(ab)(ab)(ab)?', where all the
+ * parenthesis have the same id
+ */
+
+ greedy = TRUE;
+ c2 = peekchr();
+ if (c2 == '-' || c2 == Magic('-'))
+ {
+ skipchr();
+ greedy = FALSE;
+ }
+ if (!read_limits(&minval, &maxval))
+ {
+ syntax_error = TRUE;
+ EMSG_RET_FAIL(_("E870: (NFA regexp) Error reading repetition limits"));
+ }
+ /* <atom>{0,inf}, <atom>{0,} and <atom>{} are equivalent to
+ * <atom>* */
+ if (minval == 0 && maxval == MAX_LIMIT && greedy)
+ {
+ EMIT(NFA_STAR);
+ break;
+ }
+
+ if (maxval > NFA_BRACES_MAXLIMIT)
+ {
+ /* This would yield a huge automaton and use too much memory.
+ * Revert to old engine */
+ return FAIL;
+ }
+
+ /* Special case: x{0} or x{-0} */
+ if (maxval == 0)
+ {
+ /* Ignore result of previous call to nfa_regatom() */
+ post_ptr = my_post_start;
+ /* NFA_SKIP_CHAR has 0-length and works everywhere */
+ EMIT(NFA_SKIP_CHAR);
+ return OK;
+ }
+
+ /* Ignore previous call to nfa_regatom() */
+ post_ptr = my_post_start;
+ /* Save pos after the repeated atom and the \{} */
+ new_regparse = regparse;
+
+ new_regparse = regparse;
+ quest = (greedy == TRUE? NFA_QUEST : NFA_QUEST_NONGREEDY);
+ for (i = 0; i < maxval; i++)
+ {
+ /* Goto beginning of the repeated atom */
+ regparse = old_regparse;
+ curchr = -1;
+ /* Restore count of parenthesis */
+ regnpar = old_regnpar;
+ old_post_ptr = post_ptr;
+ if (nfa_regatom() == FAIL)
+ return FAIL;
+ /* after "minval" times, atoms are optional */
+ if (i + 1 > minval)
+ EMIT(quest);
+ if (old_post_ptr != my_post_start)
+ EMIT(NFA_CONCAT);
+ }
+
+ /* Go to just after the repeated atom and the \{} */
+ regparse = new_regparse;
+ curchr = -1;
+
+ break;
+
+
+ default:
+ break;
+ } /* end switch */
+
+ if (re_multi_type(peekchr()) != NOT_MULTI)
+ {
+ /* Can't have a multi follow a multi. */
+ syntax_error = TRUE;
+ EMSG_RET_FAIL(_("E871: (NFA regexp) Can't have a multi follow a multi !"));
+ }
+
+ return OK;
+}
+
+/*
+ * Parse one or more pieces, concatenated. It matches a match for the
+ * first piece, followed by a match for the second piece, etc. Example:
+ * "f[0-9]b", first matches "f", then a digit and then "b".
+ *
+ * concat ::= piece
+ * or piece piece
+ * or piece piece piece
+ * etc.
+ */
+ static int
+nfa_regconcat()
+{
+ int cont = TRUE;
+ int first = TRUE;
+
+ while (cont)
+ {
+ switch (peekchr())
+ {
+ case NUL:
+ case Magic('|'):
+ case Magic('&'):
+ case Magic(')'):
+ cont = FALSE;
+ break;
+
+ case Magic('Z'):
+#ifdef FEAT_MBYTE
+ regflags |= RF_ICOMBINE;
+#endif
+ skipchr_keepstart();
+ break;
+ case Magic('c'):
+ regflags |= RF_ICASE;
+ skipchr_keepstart();
+ break;
+ case Magic('C'):
+ regflags |= RF_NOICASE;
+ skipchr_keepstart();
+ break;
+ case Magic('v'):
+ reg_magic = MAGIC_ALL;
+ skipchr_keepstart();
+ curchr = -1;
+ break;
+ case Magic('m'):
+ reg_magic = MAGIC_ON;
+ skipchr_keepstart();
+ curchr = -1;
+ break;
+ case Magic('M'):
+ reg_magic = MAGIC_OFF;
+ skipchr_keepstart();
+ curchr = -1;
+ break;
+ case Magic('V'):
+ reg_magic = MAGIC_NONE;
+ skipchr_keepstart();
+ curchr = -1;
+ break;
+
+ default:
+ if (nfa_regpiece() == FAIL)
+ return FAIL;
+ if (first == FALSE)
+ EMIT(NFA_CONCAT);
+ else
+ first = FALSE;
+ break;
+ }
+ }
+
+ return OK;
+}
+
+/*
+ * Parse a branch, one or more concats, separated by "\&". It matches the
+ * last concat, but only if all the preceding concats also match at the same
+ * position. Examples:
+ * "foobeep\&..." matches "foo" in "foobeep".
+ * ".*Peter\&.*Bob" matches in a line containing both "Peter" and "Bob"
+ *
+ * branch ::= concat
+ * or concat \& concat
+ * or concat \& concat \& concat
+ * etc.
+ */
+ static int
+nfa_regbranch()
+{
+ int ch;
+ int *old_post_ptr;
+
+ old_post_ptr = post_ptr;
+
+ /* First branch, possibly the only one */
+ if (nfa_regconcat() == FAIL)
+ return FAIL;
+
+ ch = peekchr();
+ /* Try next concats */
+ while (ch == Magic('&'))
+ {
+ skipchr();
+ EMIT(NFA_NOPEN);
+ EMIT(NFA_PREV_ATOM_NO_WIDTH);
+ old_post_ptr = post_ptr;
+ if (nfa_regconcat() == FAIL)
+ return FAIL;
+ /* if concat is empty, skip a input char. But do emit a node */
+ if (old_post_ptr == post_ptr)
+ EMIT(NFA_SKIP_CHAR);
+ EMIT(NFA_CONCAT);
+ ch = peekchr();
+ }
+
+ /* Even if a branch is empty, emit one node for it */
+ if (old_post_ptr == post_ptr)
+ EMIT(NFA_SKIP_CHAR);
+
+ return OK;
+}
+
+/*
+ * Parse a pattern, one or more branches, separated by "\|". It matches
+ * anything that matches one of the branches. Example: "foo\|beep" matches
+ * "foo" and matches "beep". If more than one branch matches, the first one
+ * is used.
+ *
+ * pattern ::= branch
+ * or branch \| branch
+ * or branch \| branch \| branch
+ * etc.
+ */
+ static int
+nfa_reg(paren)
+ int paren; /* REG_NOPAREN, REG_PAREN, REG_NPAREN or REG_ZPAREN */
+{
+ int parno = 0;
+
+#ifdef FEAT_SYN_HL
+#endif
+ if (paren == REG_PAREN)
+ {
+ if (regnpar >= NSUBEXP) /* Too many `(' */
+ {
+ syntax_error = TRUE;
+ EMSG_RET_FAIL(_("E872: (NFA regexp) Too many '('"));
+ }
+ parno = regnpar++;
+ }
+
+ if (nfa_regbranch() == FAIL)
+ return FAIL; /* cascaded error */
+
+ while (peekchr() == Magic('|'))
+ {
+ skipchr();
+ if (nfa_regbranch() == FAIL)
+ return FAIL; /* cascaded error */
+ EMIT(NFA_OR);
+ }
+
+ /* Check for proper termination. */
+ if (paren != REG_NOPAREN && getchr() != Magic(')'))
+ {
+ syntax_error = TRUE;
+ if (paren == REG_NPAREN)
+ EMSG2_RET_FAIL(_(e_unmatchedpp), reg_magic == MAGIC_ALL);
+ else
+ EMSG2_RET_FAIL(_(e_unmatchedp), reg_magic == MAGIC_ALL);
+ }
+ else if (paren == REG_NOPAREN && peekchr() != NUL)
+ {
+ syntax_error = TRUE;
+ if (peekchr() == Magic(')'))
+ EMSG2_RET_FAIL(_(e_unmatchedpar), reg_magic == MAGIC_ALL);
+ else
+ EMSG_RET_FAIL(_("E873: (NFA regexp) proper termination error"));
+ }
+ /*
+ * Here we set the flag allowing back references to this set of
+ * parentheses.
+ */
+ if (paren == REG_PAREN)
+ {
+ had_endbrace[parno] = TRUE; /* have seen the close paren */
+ EMIT(NFA_MOPEN + parno);
+ }
+
+ return OK;
+}
+
+typedef struct
+{
+ char_u *start[NSUBEXP];
+ char_u *end[NSUBEXP];
+ lpos_T startpos[NSUBEXP];
+ lpos_T endpos[NSUBEXP];
+} regsub_T;
+
+static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m));
+
+#ifdef DEBUG
+static char_u code[50];
+
+ static void
+nfa_set_code(c)
+ int c;
+{
+ int addnl = FALSE;
+
+ if (c >= NFA_FIRST_NL && c <= NFA_LAST_NL)
+ {
+ addnl = TRUE;
+ c -= ADD_NL;
+ }
+
+ STRCPY(code, "");
+ switch (c)
+ {
+ case NFA_MATCH: STRCPY(code, "NFA_MATCH "); break;
+ case NFA_SPLIT: STRCPY(code, "NFA_SPLIT "); break;
+ case NFA_CONCAT: STRCPY(code, "NFA_CONCAT "); break;
+ case NFA_NEWL: STRCPY(code, "NFA_NEWL "); break;
+ case NFA_ZSTART: STRCPY(code, "NFA_ZSTART"); break;
+ case NFA_ZEND: STRCPY(code, "NFA_ZEND"); break;
+
+ case NFA_PREV_ATOM_NO_WIDTH:
+ STRCPY(code, "NFA_PREV_ATOM_NO_WIDTH"); break;
+ case NFA_NOPEN: STRCPY(code, "NFA_MOPEN_INVISIBLE"); break;
+ case NFA_NCLOSE: STRCPY(code, "NFA_MCLOSE_INVISIBLE"); break;
+ case NFA_START_INVISIBLE: STRCPY(code, "NFA_START_INVISIBLE"); break;
+ case NFA_END_INVISIBLE: STRCPY(code, "NFA_END_INVISIBLE"); break;
+
+ case NFA_MULTIBYTE: STRCPY(code, "NFA_MULTIBYTE"); break;
+ case NFA_END_MULTIBYTE: STRCPY(code, "NFA_END_MULTIBYTE"); break;
+
+ case NFA_COMPOSING: STRCPY(code, "NFA_COMPOSING"); break;
+ case NFA_END_COMPOSING: STRCPY(code, "NFA_END_COMPOSING"); break;
+
+ case NFA_MOPEN + 0:
+ case NFA_MOPEN + 1:
+ case NFA_MOPEN + 2:
+ case NFA_MOPEN + 3:
+ case NFA_MOPEN + 4:
+ case NFA_MOPEN + 5:
+ case NFA_MOPEN + 6:
+ case NFA_MOPEN + 7:
+ case NFA_MOPEN + 8:
+ case NFA_MOPEN + 9:
+ STRCPY(code, "NFA_MOPEN(x)");
+ code[10] = c - NFA_MOPEN + '0';
+ break;
+ case NFA_MCLOSE + 0:
+ case NFA_MCLOSE + 1:
+ case NFA_MCLOSE + 2:
+ case NFA_MCLOSE + 3:
+ case NFA_MCLOSE + 4:
+ case NFA_MCLOSE + 5:
+ case NFA_MCLOSE + 6:
+ case NFA_MCLOSE + 7:
+ case NFA_MCLOSE + 8:
+ case NFA_MCLOSE + 9:
+ STRCPY(code, "NFA_MCLOSE(x)");
+ code[11] = c - NFA_MCLOSE + '0';
+ break;
+ case NFA_EOL: STRCPY(code, "NFA_EOL "); break;
+ case NFA_BOL: STRCPY(code, "NFA_BOL "); break;
+ case NFA_EOW: STRCPY(code, "NFA_EOW "); break;
+ case NFA_BOW: STRCPY(code, "NFA_BOW "); break;
+ case NFA_STAR: STRCPY(code, "NFA_STAR "); break;
+ case NFA_PLUS: STRCPY(code, "NFA_PLUS "); break;
+ case NFA_NOT: STRCPY(code, "NFA_NOT "); break;
+ case NFA_SKIP_CHAR: STRCPY(code, "NFA_SKIP_CHAR"); break;
+ case NFA_OR: STRCPY(code, "NFA_OR"); break;
+ case NFA_QUEST: STRCPY(code, "NFA_QUEST"); break;
+ case NFA_QUEST_NONGREEDY: STRCPY(code, "NFA_QUEST_NON_GREEDY"); break;
+ case NFA_END_NEG_RANGE: STRCPY(code, "NFA_END_NEG_RANGE"); break;
+ case NFA_CLASS_ALNUM: STRCPY(code, "NFA_CLASS_ALNUM"); break;
+ case NFA_CLASS_ALPHA: STRCPY(code, "NFA_CLASS_ALPHA"); break;
+ case NFA_CLASS_BLANK: STRCPY(code, "NFA_CLASS_BLANK"); break;
+ case NFA_CLASS_CNTRL: STRCPY(code, "NFA_CLASS_CNTRL"); break;
+ case NFA_CLASS_DIGIT: STRCPY(code, "NFA_CLASS_DIGIT"); break;
+ case NFA_CLASS_GRAPH: STRCPY(code, "NFA_CLASS_GRAPH"); break;
+ case NFA_CLASS_LOWER: STRCPY(code, "NFA_CLASS_LOWER"); break;
+ case NFA_CLASS_PRINT: STRCPY(code, "NFA_CLASS_PRINT"); break;
+ case NFA_CLASS_PUNCT: STRCPY(code, "NFA_CLASS_PUNCT"); break;
+ case NFA_CLASS_SPACE: STRCPY(code, "NFA_CLASS_SPACE"); break;
+ case NFA_CLASS_UPPER: STRCPY(code, "NFA_CLASS_UPPER"); break;
+ case NFA_CLASS_XDIGIT: STRCPY(code, "NFA_CLASS_XDIGIT"); break;
+ case NFA_CLASS_TAB: STRCPY(code, "NFA_CLASS_TAB"); break;
+ case NFA_CLASS_RETURN: STRCPY(code, "NFA_CLASS_RETURN"); break;
+ case NFA_CLASS_BACKSPACE: STRCPY(code, "NFA_CLASS_BACKSPACE"); break;
+ case NFA_CLASS_ESCAPE: STRCPY(code, "NFA_CLASS_ESCAPE"); break;
+
+ case NFA_ANY: STRCPY(code, "NFA_ANY"); break;
+ case NFA_IDENT: STRCPY(code, "NFA_IDENT"); break;
+ case NFA_SIDENT:STRCPY(code, "NFA_SIDENT"); break;
+ case NFA_KWORD: STRCPY(code, "NFA_KWORD"); break;
+ case NFA_SKWORD:STRCPY(code, "NFA_SKWORD"); break;
+ case NFA_FNAME: STRCPY(code, "NFA_FNAME"); break;
+ case NFA_SFNAME:STRCPY(code, "NFA_SFNAME"); break;
+ case NFA_PRINT: STRCPY(code, "NFA_PRINT"); break;
+ case NFA_SPRINT:STRCPY(code, "NFA_SPRINT"); break;
+ case NFA_WHITE: STRCPY(code, "NFA_WHITE"); break;
+ case NFA_NWHITE:STRCPY(code, "NFA_NWHITE"); break;
+ case NFA_DIGIT: STRCPY(code, "NFA_DIGIT"); break;
+ case NFA_NDIGIT:STRCPY(code, "NFA_NDIGIT"); break;
+ case NFA_HEX: STRCPY(code, "NFA_HEX"); break;
+ case NFA_NHEX: STRCPY(code, "NFA_NHEX"); break;
+ case NFA_OCTAL: STRCPY(code, "NFA_OCTAL"); break;
+ case NFA_NOCTAL:STRCPY(code, "NFA_NOCTAL"); break;
+ case NFA_WORD: STRCPY(code, "NFA_WORD"); break;
+ case NFA_NWORD: STRCPY(code, "NFA_NWORD"); break;
+ case NFA_HEAD: STRCPY(code, "NFA_HEAD"); break;
+ case NFA_NHEAD: STRCPY(code, "NFA_NHEAD"); break;
+ case NFA_ALPHA: STRCPY(code, "NFA_ALPHA"); break;
+ case NFA_NALPHA:STRCPY(code, "NFA_NALPHA"); break;
+ case NFA_LOWER: STRCPY(code, "NFA_LOWER"); break;
+ case NFA_NLOWER:STRCPY(code, "NFA_NLOWER"); break;
+ case NFA_UPPER: STRCPY(code, "NFA_UPPER"); break;
+ case NFA_NUPPER:STRCPY(code, "NFA_NUPPER"); break;
+
+ default:
+ STRCPY(code, "CHAR(x)");
+ code[5] = c;
+ }
+
+ if (addnl == TRUE)
+ STRCAT(code, " + NEWLINE ");
+
+}
+
+#ifdef ENABLE_LOG
+static FILE *log_fd;
+
+/*
+ * Print the postfix notation of the current regexp.
+ */
+ static void
+nfa_postfix_dump(expr, retval)
+ char_u *expr;
+ int retval;
+{
+ int *p;
+ FILE *f;
+
+ f = fopen("LOG.log", "a");
+ if (f != NULL)
+ {
+ fprintf(f, "\n-------------------------\n");
+ if (retval == FAIL)
+ fprintf(f, ">>> NFA engine failed ... \n");
+ else if (retval == OK)
+ fprintf(f, ">>> NFA engine succeeded !\n");
+ fprintf(f, "Regexp: \"%s\"\nPostfix notation (char): \"", expr);
+ for (p=post_start; *p; p++)
+ {
+ nfa_set_code(*p);
+ fprintf(f, "%s, ", code);
+ }
+ fprintf(f, "\"\nPostfix notation (int): ");
+ for (p=post_start; *p; p++)
+ fprintf(f, "%d ", *p);
+ fprintf(f, "\n\n");
+ fclose(f);
+ }
+}
+
+/*
+ * Print the NFA starting with a root node "state".
+ */
+ static void
+nfa_print_state(debugf, state, ident)
+ FILE *debugf;
+ nfa_state_T *state;
+ int ident;
+{
+ int i;
+
+ if (state == NULL)
+ return;
+
+ fprintf(debugf, "(%2d)", abs(state->id));
+ for (i = 0; i < ident; i++)
+ fprintf(debugf, "%c", ' ');
+
+ nfa_set_code(state->c);
+ fprintf(debugf, "%s %s (%d) (id=%d)\n",
+ state->negated ? "NOT" : "", code, state->c, abs(state->id));
+ if (state->id < 0)
+ return;
+
+ state->id = abs(state->id) * -1;
+ nfa_print_state(debugf, state->out, ident + 4);
+ nfa_print_state(debugf, state->out1, ident + 4);
+}
+
+/*
+ * Print the NFA state machine.
+ */
+ static void
+nfa_dump(prog)
+ nfa_regprog_T *prog;
+{
+ FILE *debugf = fopen("LOG.log", "a");
+
+ if (debugf != NULL)
+ {
+ nfa_print_state(debugf, prog->start, 0);
+ fclose(debugf);
+ }
+}
+#endif /* ENABLE_LOG */
+#endif /* DEBUG */
+
+/*
+ * Parse r.e. @expr and convert it into postfix form.
+ * Return the postfix string on success, NULL otherwise.
+ */
+ static int *
+re2post()
+{
+ if (nfa_reg(REG_NOPAREN) == FAIL)
+ return NULL;
+ EMIT(NFA_MOPEN);
+ return post_start;
+}
+
+/* NB. Some of the code below is inspired by Russ's. */
+
+/*
+ * Represents an NFA state plus zero or one or two arrows exiting.
+ * if c == MATCH, no arrows out; matching state.
+ * If c == SPLIT, unlabeled arrows to out and out1 (if != NULL).
+ * If c < 256, labeled arrow with character c to out.
+ */
+
+static nfa_state_T *state_ptr; /* points to nfa_prog->state */
+
+/*
+ * Allocate and initialize nfa_state_T.
+ */
+ static nfa_state_T *
+new_state(c, out, out1)
+ int c;
+ nfa_state_T *out;
+ nfa_state_T *out1;
+{
+ nfa_state_T *s;
+
+ if (istate >= nstate)
+ return NULL;
+
+ s = &state_ptr[istate++];
+
+ s->c = c;
+ s->out = out;
+ s->out1 = out1;
+
+ s->id = istate;
+ s->lastlist = 0;
+ s->lastthread = NULL;
+ s->visits = 0;
+ s->negated = FALSE;
+
+ return s;
+}
+
+/*
+ * A partially built NFA without the matching state filled in.
+ * Frag_T.start points at the start state.
+ * Frag_T.out is a list of places that need to be set to the
+ * next state for this fragment.
+ */
+typedef union Ptrlist Ptrlist;
+struct Frag
+{
+ nfa_state_T *start;
+ Ptrlist *out;
+};
+typedef struct Frag Frag_T;
+
+static Frag_T frag __ARGS((nfa_state_T *start, Ptrlist *out));
+static Ptrlist *list1 __ARGS((nfa_state_T **outp));
+static void patch __ARGS((Ptrlist *l, nfa_state_T *s));
+static Ptrlist *append __ARGS((Ptrlist *l1, Ptrlist *l2));
+static void st_push __ARGS((Frag_T s, Frag_T **p, Frag_T *stack_end));
+static Frag_T st_pop __ARGS((Frag_T **p, Frag_T *stack));
+
+/*
+ * Initialize Frag_T struct.
+ */
+ static Frag_T
+frag(start, out)
+ nfa_state_T *start;
+ Ptrlist *out;
+{
+ Frag_T n = { start, out };
+ return n;
+}
+
+/*
+ * Since the out pointers in the list are always
+ * uninitialized, we use the pointers themselves
+ * as storage for the Ptrlists.
+ */
+union Ptrlist
+{
+ Ptrlist *next;
+ nfa_state_T *s;
+};
+
+/*
+ * Create singleton list containing just outp.
+ */
+ static Ptrlist *
+list1(outp)
+ nfa_state_T **outp;
+{
+ Ptrlist *l;
+
+ l = (Ptrlist *)outp;
+ l->next = NULL;
+ return l;
+}
+
+/*
+ * Patch the list of states at out to point to start.
+ */
+ static void
+patch(l, s)
+ Ptrlist *l;
+ nfa_state_T *s;
+{
+ Ptrlist *next;
+
+ for (; l; l = next)
+ {
+ next = l->next;
+ l->s = s;
+ }
+}
+
+
+/*
+ * Join the two lists l1 and l2, returning the combination.
+ */
+ static Ptrlist *
+append(l1, l2)
+ Ptrlist *l1;
+ Ptrlist *l2;
+{
+ Ptrlist *oldl1;
+
+ oldl1 = l1;
+ while (l1->next)
+ l1 = l1->next;
+ l1->next = l2;
+ return oldl1;
+}
+
+/*
+ * Stack used for transforming postfix form into NFA.
+ */
+static Frag_T empty;
+
+ static void
+st_error(postfix, end, p)
+ int *postfix;
+ int *end;
+ int *p;
+{
+ FILE *df;
+ int *p2;
+
+ df = fopen("stack.err", "a");
+ if (df)
+ {
+ fprintf(df, "Error popping the stack!\n");
+#ifdef DEBUG
+ fprintf(df, "Current regexp is \"%s\"\n", nfa_regengine.expr);
+#endif
+ fprintf(df, "Postfix form is: ");
+#ifdef DEBUG
+ for (p2 = postfix; p2 < end; p2++)
+ {
+ nfa_set_code(*p2);
+ fprintf(df, "%s, ", code);
+ }
+ nfa_set_code(*p);
+ fprintf(df, "\nCurrent position is: ");
+ for (p2 = postfix; p2 <= p; p2 ++)
+ {
+ nfa_set_code(*p2);
+ fprintf(df, "%s, ", code);
+ }
+#else
+ for (p2 = postfix; p2 < end; p2++)
+ {
+ fprintf(df, "%d, ", *p2);
+ }
+ fprintf(df, "\nCurrent position is: ");
+ for (p2 = postfix; p2 <= p; p2 ++)
+ {
+ fprintf(df, "%d, ", *p2);
+ }
+#endif
+ fprintf(df, "\n--------------------------\n");
+ fclose(df);
+ }
+ EMSG(_("E874: (NFA) Could not pop the stack !"));
+}
+
+/*
+ * Push an item onto the stack.
+ */
+ static void
+st_push(s, p, stack_end)
+ Frag_T s;
+ Frag_T **p;
+ Frag_T *stack_end;
+{
+ Frag_T *stackp = *p;
+
+ if (stackp >= stack_end)
+ return;
+ *stackp = s;
+ *p = *p + 1;
+}
+
+/*
+ * Pop an item from the stack.
+ */
+ static Frag_T
+st_pop(p, stack)
+ Frag_T **p;
+ Frag_T *stack;
+{
+ Frag_T *stackp;
+
+ *p = *p - 1;
+ stackp = *p;
+ if (stackp < stack)
+ return empty;
+ return **p;
+}
+
+/*
+ * Convert a postfix form into its equivalent NFA.
+ * Return the NFA start state on success, NULL otherwise.
+ */
+ static nfa_state_T *
+post2nfa(postfix, end, nfa_calc_size)
+ int *postfix;
+ int *end;
+ int nfa_calc_size;
+{
+ int *p;
+ int mopen;
+ int mclose;
+ Frag_T *stack = NULL;
+ Frag_T *stackp = NULL;
+ Frag_T *stack_end = NULL;
+ Frag_T e1;
+ Frag_T e2;
+ Frag_T e;
+ nfa_state_T *s;
+ nfa_state_T *s1;
+ nfa_state_T *matchstate;
+
+ if (postfix == NULL)
+ return NULL;
+
+#define PUSH(s) st_push ((s), &stackp, stack_end)
+#define POP() st_pop(&stackp, stack); \
+ if (stackp < stack) \
+ { \
+ st_error(postfix, end, p); \
+ return NULL; \
+ }
+
+ if (nfa_calc_size == FALSE)
+ {
+ /* Allocate space for the stack. Max states on the stack : nstate */
+ stack = (Frag_T *) lalloc((nstate + 1)*sizeof(Frag_T), TRUE);
+ stackp = stack;
+ stack_end = stack + NFA_STACK_SIZE;
+ }
+
+ for (p = postfix; p < end; ++p)
+ {
+ switch (*p)
+ {
+ case NFA_CONCAT:
+ /* Catenation.
+ * Pay attention: this operator does not exist
+ * in the r.e. itself (it is implicit, really).
+ * It is added when r.e. is translated to postfix
+ * form in re2post().
+ *
+ * No new state added here. */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate += 0;
+ break;
+ }
+ e2 = POP();
+ e1 = POP();
+ patch(e1.out, e2.start);
+ PUSH(frag(e1.start, e2.out));
+ break;
+
+ case NFA_NOT:
+ /* Negation of a character */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate += 0;
+ break;
+ }
+ e1 = POP();
+ e1.start->negated = TRUE;
+ if (e1.start->c == NFA_MULTIBYTE || e1.start->c == NFA_COMPOSING)
+ e1.start->out1->negated = TRUE;
+ PUSH(e1);
+ break;
+
+ case NFA_OR:
+ /* Alternation */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ e2 = POP();
+ e1 = POP();
+ s = new_state(NFA_SPLIT, e1.start, e2.start);
+ if (s == NULL)
+ return NULL;
+ PUSH(frag(s, append(e1.out, e2.out)));
+ break;
+
+ case NFA_STAR:
+ /* Zero or more */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ e = POP();
+ s = new_state(NFA_SPLIT, e.start, NULL);
+ if (s == NULL)
+ return NULL;
+ patch(e.out, s);
+ PUSH(frag(s, list1(&s->out1)));
+ break;
+
+ case NFA_QUEST:
+ /* one or zero atoms=> greedy match */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ e = POP();
+ s = new_state(NFA_SPLIT, e.start, NULL);
+ if (s == NULL)
+ return NULL;
+ PUSH(frag(s, append(e.out, list1(&s->out1))));
+ break;
+
+ case NFA_QUEST_NONGREEDY:
+ /* zero or one atoms => non-greedy match */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ e = POP();
+ s = new_state(NFA_SPLIT, NULL, e.start);
+ if (s == NULL)
+ return NULL;
+ PUSH(frag(s, append(e.out, list1(&s->out))));
+ break;
+
+ case NFA_PLUS:
+ /* One or more */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ e = POP();
+ s = new_state(NFA_SPLIT, e.start, NULL);
+ if (s == NULL)
+ return NULL;
+ patch(e.out, s);
+ PUSH(frag(e.start, list1(&s->out1)));
+ break;
+
+ case NFA_SKIP_CHAR:
+ /* Symbol of 0-length, Used in a repetition
+ * with max/min count of 0 */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ s = new_state(NFA_SKIP_CHAR, NULL, NULL);
+ if (s == NULL)
+ return NULL;
+ PUSH(frag(s, list1(&s->out)));
+ break;
+
+ case NFA_PREV_ATOM_NO_WIDTH:
+ /* The \@= operator: match the preceding atom with 0 width.
+ * Surrounds the preceding atom with START_INVISIBLE and
+ * END_INVISIBLE, similarly to MOPEN.
+ */
+ /* TODO: Maybe this drops the speed? */
+ return NULL;
+
+ if (nfa_calc_size == TRUE)
+ {
+ nstate += 2;
+ break;
+ }
+ e = POP();
+ s1 = new_state(NFA_END_INVISIBLE, NULL, NULL);
+ if (s1 == NULL)
+ return NULL;
+ patch(e.out, s1);
+
+ s = new_state(NFA_START_INVISIBLE, e.start, s1);
+ if (s == NULL)
+ return NULL;
+ PUSH(frag(s, list1(&s1->out)));
+ break;
+
+ case NFA_MOPEN + 0: /* Submatch */
+ case NFA_MOPEN + 1:
+ case NFA_MOPEN + 2:
+ case NFA_MOPEN + 3:
+ case NFA_MOPEN + 4:
+ case NFA_MOPEN + 5:
+ case NFA_MOPEN + 6:
+ case NFA_MOPEN + 7:
+ case NFA_MOPEN + 8:
+ case NFA_MOPEN + 9:
+ case NFA_NOPEN: /* \%( "Invisible Submatch" */
+ case NFA_MULTIBYTE: /* mbyte char */
+ case NFA_COMPOSING: /* composing char */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate += 2;
+ break;
+ }
+
+ mopen = *p;
+ switch (*p)
+ {
+ case NFA_NOPEN:
+ mclose = NFA_NCLOSE;
+ break;
+ case NFA_MULTIBYTE:
+ mclose = NFA_END_MULTIBYTE;
+ break;
+ case NFA_COMPOSING:
+ mclose = NFA_END_COMPOSING;
+ break;
+ default:
+ /* NFA_MOPEN(0) ... NFA_MOPEN(9) */
+ mclose = *p + NSUBEXP;
+ break;
+ }
+
+ /* Allow "NFA_MOPEN" as a valid postfix representation for
+ * the empty regexp "". In this case, the NFA will be
+ * NFA_MOPEN -> NFA_MCLOSE. Note that this also allows
+ * empty groups of parenthesis, and empty mbyte chars */
+ if (stackp == stack)
+ {
+ s = new_state(mopen, NULL, NULL);
+ if (s == NULL)
+ return NULL;
+ s1 = new_state(mclose, NULL, NULL);
+ if (s1 == NULL)
+ return NULL;
+ patch(list1(&s->out), s1);
+ PUSH(frag(s, list1(&s1->out)));
+ break;
+ }
+
+ /* At least one node was emitted before NFA_MOPEN, so
+ * at least one node will be between NFA_MOPEN and NFA_MCLOSE */
+ e = POP();
+ s = new_state(mopen, e.start, NULL); /* `(' */
+ if (s == NULL)
+ return NULL;
+
+ s1 = new_state(mclose, NULL, NULL); /* `)' */
+ if (s1 == NULL)
+ return NULL;
+ patch(e.out, s1);
+
+ if (mopen == NFA_MULTIBYTE || mopen == NFA_COMPOSING)
+ /* MULTIBYTE->out1 = END_MULTIBYTE
+ * COMPOSING->out1 = END_COMPOSING */
+ patch(list1(&s->out1), s1);
+
+ PUSH(frag(s, list1(&s1->out)));
+ break;
+
+ case NFA_ZSTART:
+ case NFA_ZEND:
+ default:
+ /* Operands */
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ break;
+ }
+ s = new_state(*p, NULL, NULL);
+ if (s == NULL)
+ return NULL;
+ PUSH(frag(s, list1(&s->out)));
+ break;
+
+ } /* switch(*p) */
+
+ } /* for(p = postfix; *p; ++p) */
+
+ if (nfa_calc_size == TRUE)
+ {
+ nstate ++;
+ return NULL; /* Return value when counting size is ignored anyway */
+ }
+
+ e = POP();
+ if (stackp != stack)
+ EMSG_RET_NULL(_("E875: (NFA regexp) (While converting from postfix to NFA), too many states left on stack"));
+
+ if (istate >= nstate)
+ EMSG_RET_NULL(_("E876: (NFA regexp) Not enough space to store the whole NFA "));
+
+ vim_free(stack);
+
+ matchstate = &state_ptr[istate++]; /* the match state */
+ matchstate->c = NFA_MATCH;
+ matchstate->out = matchstate->out1 = NULL;
+
+ patch(e.out, matchstate);
+ return e.start;
+
+#undef POP1
+#undef PUSH1
+#undef POP2
+#undef PUSH2
+#undef POP
+#undef PUSH
+}
+
+/****************************************************************
+ * NFA execution code.
+ ****************************************************************/
+
+/* thread_T contains runtime information of a NFA state */
+struct thread
+{
+ nfa_state_T *state;
+ regsub_T sub; /* submatch info */
+};
+
+typedef struct
+{
+ thread_T *t;
+ int n;
+} List;
+
+static void addstate __ARGS((List *l, nfa_state_T *state, regsub_T *m, int off, int lid, int *match));
+
+ static void
+addstate(l, state, m, off, lid, match)
+ List *l; /* runtime state list */
+ nfa_state_T *state; /* state to update */
+ regsub_T *m; /* pointers to subexpressions */
+ int off;
+ int lid;
+ int *match; /* found match? */
+{
+ regsub_T save;
+ int subidx = 0;
+
+ if (l == NULL || state == NULL)
+ return;
+
+ switch (state->c)
+ {
+ case NFA_SPLIT:
+ case NFA_NOT:
+ case NFA_NOPEN:
+ case NFA_NCLOSE:
+ case NFA_MCLOSE:
+ case NFA_MCLOSE + 1:
+ case NFA_MCLOSE + 2:
+ case NFA_MCLOSE + 3:
+ case NFA_MCLOSE + 4:
+ case NFA_MCLOSE + 5:
+ case NFA_MCLOSE + 6:
+ case NFA_MCLOSE + 7:
+ case NFA_MCLOSE + 8:
+ case NFA_MCLOSE + 9:
+ /* Do not remember these nodes in list "thislist" or "nextlist" */
+ break;
+
+ default:
+ if (state->lastlist == lid)
+ {
+ if (++state->visits > 2)
+ return;
+ }
+ else
+ {
+ /* add the state to the list */
+ state->lastlist = lid;
+ state->lastthread = &l->t[l->n++];
+ state->lastthread->state = state;
+ state->lastthread->sub = *m;
+ }
+ }
+
+#ifdef ENABLE_LOG
+ nfa_set_code(state->c);
+ fprintf(log_fd, "> Adding state %d to list. Character %s, code %d\n",
+ abs(state->id), code, state->c);
+#endif
+ switch (state->c)
+ {
+ case NFA_MATCH:
+ *match = TRUE;
+ break;
+
+ case NFA_SPLIT:
+ addstate(l, state->out, m, off, lid, match);
+ addstate(l, state->out1, m, off, lid, match);
+ break;
+
+ case NFA_SKIP_CHAR:
+ addstate(l, state->out, m, off, lid, match);
+ break;
+
+#if 0
+ case NFA_END_NEG_RANGE:
+ /* Nothing to handle here. nfa_regmatch() will take care of it */
+ break;
+
+ case NFA_NOT:
+ EMSG(_("E999: (NFA regexp internal error) Should not process NOT node !"));
+#ifdef ENABLE_LOG
+ fprintf(f, "\n\n>>> E999: Added state NFA_NOT to a list ... Something went wrong ! Why wasn't it processed already? \n\n");
+#endif
+ break;
+
+ case NFA_COMPOSING:
+ /* nfa_regmatch() will match all the bytes of this composing char. */
+ break;
+
+ case NFA_MULTIBYTE:
+ /* nfa_regmatch() will match all the bytes of this multibyte char. */
+ break;
+#endif
+
+ case NFA_END_MULTIBYTE:
+ /* Successfully matched this mbyte char */
+ addstate(l, state->out, m, off, lid, match);
+ break;
+
+ case NFA_NOPEN:
+ case NFA_NCLOSE:
+ addstate(l, state->out, m, off, lid, match);
+ break;
+
+ /* If this state is reached, then a recursive call of nfa_regmatch()
+ * succeeded. the next call saves the found submatches in the
+ * first state after the "invisible" branch. */
+#if 0
+ case NFA_END_INVISIBLE:
+ break;
+#endif
+
+ case NFA_MOPEN + 0:
+ case NFA_MOPEN + 1:
+ case NFA_MOPEN + 2:
+ case NFA_MOPEN + 3:
+ case NFA_MOPEN + 4:
+ case NFA_MOPEN + 5:
+ case NFA_MOPEN + 6:
+ case NFA_MOPEN + 7:
+ case NFA_MOPEN + 8:
+ case NFA_MOPEN + 9:
+ case NFA_ZSTART:
+ subidx = state->c - NFA_MOPEN;
+ if (state->c == NFA_ZSTART)
+ subidx = 0;
+
+ if (REG_MULTI)
+ {
+ save.startpos[subidx] = m->startpos[subidx];
+ save.endpos[subidx] = m->endpos[subidx];
+ m->startpos[subidx].lnum = reglnum;
+ m->startpos[subidx].col = reginput - regline + off;
+ }
+ else
+ {
+ save.start[subidx] = m->start[subidx];
+ save.end[subidx] = m->end[subidx];
+ m->start[subidx] = reginput + off;
+ }
+
+ addstate(l, state->out, m, off, lid, match);
+
+ if (REG_MULTI)
+ {
+ m->startpos[subidx] = save.startpos[subidx];
+ m->endpos[subidx] = save.endpos[subidx];
+ }
+ else
+ {
+ m->start[subidx] = save.start[subidx];
+ m->end[subidx] = save.end[subidx];
+ }
+ break;
+
+ case NFA_MCLOSE + 0:
+ if (nfa_has_zend == TRUE)
+ {
+ addstate(l, state->out, m, off, lid, match);
+ break;
+ }
+ case NFA_MCLOSE + 1:
+ case NFA_MCLOSE + 2:
+ case NFA_MCLOSE + 3:
+ case NFA_MCLOSE + 4:
+ case NFA_MCLOSE + 5:
+ case NFA_MCLOSE + 6:
+ case NFA_MCLOSE + 7:
+ case NFA_MCLOSE + 8:
+ case NFA_MCLOSE + 9:
+ case NFA_ZEND:
+ subidx = state->c - NFA_MCLOSE;
+ if (state->c == NFA_ZEND)
+ subidx = 0;
+
+ if (REG_MULTI)
+ {
+ save.startpos[subidx] = m->startpos[subidx];
+ save.endpos[subidx] = m->endpos[subidx];
+ m->endpos[subidx].lnum = reglnum;
+ m->endpos[subidx].col = reginput - regline + off;
+ }
+ else
+ {
+ save.start[subidx] = m->start[subidx];
+ save.end[subidx] = m->end[subidx];
+ m->end[subidx] = reginput + off;
+ }
+
+ addstate(l, state->out, m, off, lid, match);
+
+ if (REG_MULTI)
+ {
+ m->startpos[subidx] = save.startpos[subidx];
+ m->endpos[subidx] = save.endpos[subidx];
+ }
+ else
+ {
+ m->start[subidx] = save.start[subidx];
+ m->end[subidx] = save.end[subidx];
+ }
+ break;
+ }
+}
+
+/*
+ * Check character class "class" against current character c.
+ */
+ static int
+check_char_class(class, c)
+ int class;
+ int c;
+{
+ switch (class)
+ {
+ case NFA_CLASS_ALNUM:
+ if (isalnum(c))
+ return OK;
+ break;
+ case NFA_CLASS_ALPHA:
+ if (isalpha(c))
+ return OK;
+ break;
+ case NFA_CLASS_BLANK:
+ if (c == ' ' || c == '\t')
+ return OK;
+ break;
+ case NFA_CLASS_CNTRL:
+ if (iscntrl(c))
+ return OK;
+ break;
+ case NFA_CLASS_DIGIT:
+ if (VIM_ISDIGIT(c))
+ return OK;
+ break;
+ case NFA_CLASS_GRAPH:
+ if (isgraph(c))
+ return OK;
+ break;
+ case NFA_CLASS_LOWER:
+ if (MB_ISLOWER(c))
+ return OK;
+ break;
+ case NFA_CLASS_PRINT:
+ if (vim_isprintc(c))
+ return OK;
+ break;
+ case NFA_CLASS_PUNCT:
+ if (ispunct(c))
+ return OK;
+ break;
+ case NFA_CLASS_SPACE:
+ if ((c >=9 && c <= 13) || (c == ' '))
+ return OK;
+ break;
+ case NFA_CLASS_UPPER:
+ if (MB_ISUPPER(c))
+ return OK;
+ break;
+ case NFA_CLASS_XDIGIT:
+ if (vim_isxdigit(c))
+ return OK;
+ break;
+ case NFA_CLASS_TAB:
+ if (c == '\t')
+ return OK;
+ break;
+ case NFA_CLASS_RETURN:
+ if (c == '\r')
+ return OK;
+ break;
+ case NFA_CLASS_BACKSPACE:
+ if (c == '\b')
+ return OK;
+ break;
+ case NFA_CLASS_ESCAPE:
+ if (c == '\033')
+ return OK;
+ break;
+
+ default:
+ /* should not be here :P */
+ EMSG_RET_FAIL(_("E877: (NFA regexp) Invalid character class "));
+ }
+ return FAIL;
+}
+
+/*
+ * Set all NFA nodes' list ID equal to -1.
+ */
+ static void
+nfa_set_neg_listids(start)
+ nfa_state_T *start;
+{
+ if (start == NULL)
+ return;
+ if (start->lastlist >= 0)
+ {
+ start->lastlist = -1;
+ nfa_set_neg_listids(start->out);
+ nfa_set_neg_listids(start->out1);
+ }
+}
+
+/*
+ * Set all NFA nodes' list ID equal to 0.
+ */
+ static void
+nfa_set_null_listids(start)
+ nfa_state_T *start;
+{
+ if (start == NULL)
+ return;
+ if (start->lastlist == -1)
+ {
+ start->lastlist = 0;
+ nfa_set_null_listids(start->out);
+ nfa_set_null_listids(start->out1);
+ }
+}
+
+/*
+ * Save list IDs for all NFA states in "list".
+ */
+ static void
+nfa_save_listids(start, list)
+ nfa_state_T *start;
+ int *list;
+{
+ if (start == NULL)
+ return;
+ if (start->lastlist != -1)
+ {
+ list[abs(start->id)] = start->lastlist;
+ start->lastlist = -1;
+ nfa_save_listids(start->out, list);
+ nfa_save_listids(start->out1, list);
+ }
+}
+
+/*
+ * Restore list IDs from "list" to all NFA states.
+ */
+ static void
+nfa_restore_listids(start, list)
+ nfa_state_T *start;
+ int *list;
+{
+ if (start == NULL)
+ return;
+ if (start->lastlist == -1)
+ {
+ start->lastlist = list[abs(start->id)];
+ nfa_restore_listids(start->out, list);
+ nfa_restore_listids(start->out1, list);
+ }
+}
+
+/*
+ * Main matching routine.
+ *
+ * Run NFA to determine whether it matches reginput.
+ *
+ * Return TRUE if there is a match, FALSE otherwise.
+ * Note: Caller must ensure that: start != NULL.
+ */
+ static int
+nfa_regmatch(start, submatch, m)
+ nfa_state_T *start;
+ regsub_T *submatch;
+ regsub_T *m;
+{
+ int c = -1;
+ int n;
+ int i = 0;
+ int result;
+ int size = 0;
+ int match = FALSE;
+ int flag = 0;
+ int old_reglnum = -1;
+ int reginput_updated = FALSE;
+ thread_T *t;
+ char_u *cc;
+ char_u *old_reginput = NULL;
+ char_u *old_regline = NULL;
+ nfa_state_T *sta;
+ nfa_state_T *end;
+ List list[3];
+ List *listtbl[2][2];
+ List *ll;
+ int listid = 1;
+ int endnode = 0;
+ List *thislist;
+ List *nextlist;
+ List *neglist;
+ int *listids = NULL;
+ int j = 0;
+ int len = 0;
+#ifdef DEBUG
+ FILE *debug = fopen("list.log", "a");
+
+ if (debug == NULL)
+ {
+ EMSG(_("(NFA) COULD NOT OPEN list.log !"));
+ return FALSE;
+ }
+#endif
+
+ /* Allocate memory for the lists of nodes */
+ size = (nstate + 1) * sizeof(thread_T);
+ list[0].t = (thread_T *)lalloc(size, TRUE);
+ list[1].t = (thread_T *)lalloc(size, TRUE);
+ list[2].t = (thread_T *)lalloc(size, TRUE);
+ if (list[0].t == NULL || list[1].t == NULL || list[2].t == NULL)
+ goto theend;
+ vim_memset(list[0].t, 0, size);
+ vim_memset(list[1].t, 0, size);
+ vim_memset(list[2].t, 0, size);
+
+#ifdef ENABLE_LOG
+ log_fd = fopen(LOG_NAME, "a");
+ if (log_fd != NULL)
+ {
+ fprintf(log_fd, "**********************************\n");
+ nfa_set_code(start->c);
+ fprintf(log_fd, " RUNNING nfa_regmatch() starting with state %d, code %s\n",
+ abs(start->id), code);
+ fprintf(log_fd, "**********************************\n");
+ }
+ else
+ {
+ EMSG(_("Could not open temporary log file for writing, displaying on stderr ... "));
+ log_fd = stderr;
+ }
+#endif
+
+ thislist = &list[0];
+ thislist->n = 0;
+ nextlist = &list[1];
+ nextlist->n = 0;
+ neglist = &list[2];
+ neglist->n = 0;
+#ifdef ENABLE_LOG
+ fprintf(log_fd, "(---) STARTSTATE\n");
+#endif
+ addstate(thislist, start, m, 0, listid, &match);
+
+ /* There are two cases when the NFA advances: 1. input char matches the
+ * NFA node and 2. input char does not match the NFA node, but the next
+ * node is NFA_NOT. The following macro calls addstate() according to
+ * these rules. It is used A LOT, so use the "listtbl" table for speed */
+ listtbl[0][0] = NULL;
+ listtbl[0][1] = neglist;
+ listtbl[1][0] = nextlist;
+ listtbl[1][1] = NULL;
+#define ADD_POS_NEG_STATE(node) \
+ ll = listtbl[result ? 1 : 0][node->negated]; \
+ if (ll != NULL) \
+ addstate(ll, node->out , &t->sub, n, listid + 1, &match);
+
+
+ /*
+ * Run for each character.
+ */
+ do {
+again:
+#ifdef FEAT_MBYTE
+ if (has_mbyte)
+ {
+ c = (*mb_ptr2char)(reginput);
+ n = (*mb_ptr2len)(reginput);
+ }
+ else
+#endif
+ {
+ c = *reginput;
+ n = 1;
+ }
+ if (c == NUL)
+ n = 0;
+ cc = (char_u *)&c;
+
+ /* swap lists */
+ thislist = &list[flag];
+ nextlist = &list[flag ^= 1];
+ nextlist->n = 0; /* `clear' nextlist */
+ listtbl[1][0] = nextlist;
+ ++listid;
+
+#ifdef ENABLE_LOG
+ fprintf(log_fd, "------------------------------------------\n");
+ fprintf(log_fd, ">>> Reginput is \"%s\"\n", reginput);
+ fprintf(log_fd, ">>> Advanced one character ... Current char is %c (code %d) \n", c, (int)c);
+ fprintf(log_fd, ">>> Thislist has %d states available: ", thislist->n);
+ for (i = 0; i< thislist->n; i++)
+ fprintf(log_fd, "%d ", abs(thislist->t[i].state->id));
+ fprintf(log_fd, "\n");
+#endif
+
+#ifdef DEBUG
+ fprintf(debug, "\n-------------------\n");
+#endif
+
+ /* compute nextlist */
+ for (i = 0; i < thislist->n || neglist->n > 0; ++i)
+ {
+ if (neglist->n > 0)
+ {
+ t = &neglist->t[0];
+ neglist->n --;
+ i--;
+ }
+ else
+ t = &thislist->t[i];
+
+#ifdef DEBUG
+ nfa_set_code(t->state->c);
+ fprintf(debug, "%s, ", code);
+#endif
+#ifdef ENABLE_LOG
+ nfa_set_code(t->state->c);
+ fprintf(log_fd, "(%d) %s, code %d ... \n", abs(t->state->id),
+ code, (int)t->state->c);
+#endif
+
+ /*
+ * Handle the possible codes of the current state.
+ * The most important is NFA_MATCH.
+ */
+ switch (t->state->c)
+ {
+ case NFA_MATCH:
+ match = TRUE;
+ *submatch = t->sub;
+#ifdef ENABLE_LOG
+ for (j = 0; j < 4; j++)
+ if (REG_MULTI)
+ fprintf(log_fd, "\n *** group %d, start: c=%d, l=%d, end: c=%d, l=%d",
+ j,
+ t->sub.startpos[j].col,
+ (int)t->sub.startpos[j].lnum,
+ t->sub.endpos[j].col,
+ (int)t->sub.endpos[j].lnum);
+ else
+ fprintf(log_fd, "\n *** group %d, start: \"%s\", end: \"%s\"",
+ j,
+ (char *)t->sub.start[j],
+ (char *)t->sub.end[j]);
+ fprintf(log_fd, "\n");
+#endif
+ goto nextchar; /* found the left-most longest match */
+
+ case NFA_END_INVISIBLE:
+ /* This is only encountered after a NFA_START_INVISIBLE node.
+ * They surround a zero-width group, used with "\@=" and "\&".
+ * If we got here, it means that the current "invisible" group
+ * finished successfully, so return control to the parent
+ * nfa_regmatch(). Submatches are stored in *m, and used in
+ * the parent call. */
+ if (start->c == NFA_MOPEN + 0)
+ addstate(thislist, t->state->out, &t->sub, 0, listid,
+ &match);
+ else
+ {
+ *m = t->sub;
+ match = TRUE;
+ }
+ break;
+
+ case NFA_START_INVISIBLE:
+ /* Save global variables, and call nfa_regmatch() to check if
+ * the current concat matches at this position. The concat
+ * ends with the node NFA_END_INVISIBLE */
+ old_reginput = reginput;
+ old_regline = regline;
+ old_reglnum = reglnum;
+ if (listids == NULL)
+ {
+ listids = (int *) lalloc(sizeof(int) * nstate, TRUE);
+ if (listids == NULL)
+ {
+ EMSG(_("E878: (NFA) Could not allocate memory for branch traversal!"));
+ return 0;
+ }
+ }
+#ifdef ENABLE_LOG
+ if (log_fd != stderr)
+ fclose(log_fd);
+ log_fd = NULL;
+#endif
+ /* Have to clear the listid field of the NFA nodes, so that
+ * nfa_regmatch() and addstate() can run properly after
+ * recursion. */
+ nfa_save_listids(start, listids);
+ nfa_set_null_listids(start);
+ result = nfa_regmatch(t->state->out, submatch, m);
+ nfa_set_neg_listids(start);
+ nfa_restore_listids(start, listids);
+
+#ifdef ENABLE_LOG
+ log_fd = fopen(LOG_NAME, "a");
+ if (log_fd != NULL)
+ {
+ fprintf(log_fd, "****************************\n");
+ fprintf(log_fd, "FINISHED RUNNING nfa_regmatch() recursively\n");
+ fprintf(log_fd, "MATCH = %s\n", result == TRUE ? "OK" : "FALSE");
+ fprintf(log_fd, "****************************\n");
+ }
+ else
+ {
+ EMSG(_("Could not open temporary log file for writing, displaying on stderr ... "));
+ log_fd = stderr;
+ }
+#endif
+ if (result == TRUE)
+ {
+ /* Restore position in input text */
+ reginput = old_reginput;
+ regline = old_regline;
+ reglnum = old_reglnum;
+ /* Copy submatch info from the recursive call */
+ if (REG_MULTI)
+ for (j = 1; j < NSUBEXP; j++)
+ {
+ t->sub.startpos[j] = m->startpos[j];
+ t->sub.endpos[j] = m->endpos[j];
+ }
+ else
+ for (j = 1; j < NSUBEXP; j++)
+ {
+ t->sub.start[j] = m->start[j];
+ t->sub.end[j] = m->end[j];
+ }
+ /* t->state->out1 is the corresponding END_INVISIBLE node */
+ addstate(thislist, t->state->out1->out, &t->sub, 0, listid,
+ &match);
+ }
+ else
+ {
+ /* continue with next input char */
+ reginput = old_reginput;
+ }
+ break;
+
+ case NFA_BOL:
+ if (reginput == regline)
+ addstate(thislist, t->state->out, &t->sub, 0, listid,
+ &match);
+ break;
+
+ case NFA_EOL:
+ if (c == NUL)
+ addstate(thislist, t->state->out, &t->sub, 0, listid,
+ &match);
+ break;
+
+ case NFA_BOW:
+ {
+ int bow = TRUE;
+
+ if (c == NUL)
+ bow = FALSE;
+#ifdef FEAT_MBYTE
+ else if (has_mbyte)
+ {
+ int this_class;
+
+ /* Get class of current and previous char (if it exists). */
+ this_class = mb_get_class(reginput);
+ if (this_class <= 1)
+ bow = FALSE;
+ else if (reg_prev_class() == this_class)
+ bow = FALSE;
+ }
+#endif
+ else if (!vim_iswordc(c)
+ || (reginput > regline && vim_iswordc(reginput[-1])))
+ bow = FALSE;
+ if (bow)
+ addstate(thislist, t->state->out, &t->sub, 0, listid,
+ &match);
+ break;
+ }
+
+ case NFA_EOW:
+ {
+ int eow = TRUE;
+
+ if (reginput == regline)
+ eow = FALSE;
+#ifdef FEAT_MBYTE
+ else if (has_mbyte)
+ {
+ int this_class, prev_class;
+
+ /* Get class of current and previous char (if it exists). */
+ this_class = mb_get_class(reginput);
+ prev_class = reg_prev_class();
+ if (this_class == prev_class
+ || prev_class == 0 || prev_class == 1)
+ eow = FALSE;
+ }
+#endif
+ else if (!vim_iswordc(reginput[-1])
+ || (reginput[0] != NUL && vim_iswordc(c)))
+ eow = FALSE;
+ if (eow)
+ addstate(thislist, t->state->out, &t->sub, 0, listid,
+ &match);
+ break;
+ }
+
+ case NFA_MULTIBYTE:
+ case NFA_COMPOSING:
+ switch (t->state->c)
+ {
+ case NFA_MULTIBYTE: endnode = NFA_END_MULTIBYTE; break;
+ case NFA_COMPOSING: endnode = NFA_END_COMPOSING; break;
+ default: endnode = 0;
+ }
+
+ result = OK;
+ sta = t->state->out;
+ len = 1;
+ while (sta->c != endnode && len <= n)
+ {
+ if (reginput[len-1] != sta->c)
+ {
+ result = OK - 1;
+ break;
+ }
+ len++;
+ sta = sta->out;
+ }
+
+ /* if input char length doesn't match regexp char length */
+ if (len -1 < n || sta->c != endnode)
+ result = OK - 1;
+ end = t->state->out1; /* NFA_END_MULTIBYTE or
+ NFA_END_COMPOSING */
+ /* If \Z was present, then ignore composing characters */
+ if (regflags & RF_ICOMBINE)
+ result = 1 ^ sta->negated;
+ ADD_POS_NEG_STATE(end);
+ break;
+
+ case NFA_NEWL:
+ if (!reg_line_lbr && REG_MULTI
+ && c == NUL && reglnum <= reg_maxline)
+ {
+ if (reginput_updated == FALSE)
+ {
+ reg_nextline();
+ reginput_updated = TRUE;
+ }
+ addstate(nextlist, t->state->out, &t->sub, n, listid + 1,
+ &match);
+ }
+ break;
+
+ case NFA_CLASS_ALNUM:
+ case NFA_CLASS_ALPHA:
+ case NFA_CLASS_BLANK:
+ case NFA_CLASS_CNTRL:
+ case NFA_CLASS_DIGIT:
+ case NFA_CLASS_GRAPH:
+ case NFA_CLASS_LOWER:
+ case NFA_CLASS_PRINT:
+ case NFA_CLASS_PUNCT:
+ case NFA_CLASS_SPACE:
+ case NFA_CLASS_UPPER:
+ case NFA_CLASS_XDIGIT:
+ case NFA_CLASS_TAB:
+ case NFA_CLASS_RETURN:
+ case NFA_CLASS_BACKSPACE:
+ case NFA_CLASS_ESCAPE:
+ result = check_char_class(t->state->c, c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_END_NEG_RANGE:
+ /* This follows a series of negated nodes, like:
+ * CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */
+ if (c > 0)
+ addstate(nextlist, t->state->out, &t->sub, n, listid + 1,
+ &match);
+ break;
+
+ case NFA_ANY:
+ /* Any printable char, not just any char. '\0' (end of input)
+ * must not match */
+ if (c > 0)
+ addstate(nextlist, t->state->out, &t->sub, n, listid + 1,
+ &match);
+ break;
+
+ /*
+ * Character classes like \a for alpha, \d for digit etc.
+ */
+ case NFA_IDENT: /* \i */
+ result = vim_isIDc(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_SIDENT: /* \I */
+ result = !VIM_ISDIGIT(c) && vim_isIDc(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_KWORD: /* \k */
+ result = vim_iswordp(cc);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_SKWORD: /* \K */
+ result = !VIM_ISDIGIT(c) && vim_iswordp(cc);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_FNAME: /* \f */
+ result = vim_isfilec(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_SFNAME: /* \F */
+ result = !VIM_ISDIGIT(c) && vim_isfilec(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_PRINT: /* \p */
+ result = ptr2cells(cc) == 1;
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_SPRINT: /* \P */
+ result = !VIM_ISDIGIT(c) && ptr2cells(cc) == 1;
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_WHITE: /* \s */
+ result = vim_iswhite(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NWHITE: /* \S */
+ result = c != NUL && !vim_iswhite(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_DIGIT: /* \d */
+ result = ri_digit(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NDIGIT: /* \D */
+ result = c != NUL && !ri_digit(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_HEX: /* \x */
+ result = ri_hex(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NHEX: /* \X */
+ result = c != NUL && !ri_hex(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_OCTAL: /* \o */
+ result = ri_octal(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NOCTAL: /* \O */
+ result = c != NUL && !ri_octal(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_WORD: /* \w */
+ result = ri_word(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NWORD: /* \W */
+ result = c != NUL && !ri_word(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_HEAD: /* \h */
+ result = ri_head(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NHEAD: /* \H */
+ result = c != NUL && !ri_head(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_ALPHA: /* \a */
+ result = ri_alpha(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NALPHA: /* \A */
+ result = c != NUL && !ri_alpha(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_LOWER: /* \l */
+ result = ri_lower(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NLOWER: /* \L */
+ result = c != NUL && !ri_lower(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_UPPER: /* \u */
+ result = ri_upper(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ case NFA_NUPPER: /* \U */
+ result = c != NUL && !ri_upper(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+
+ default: /* regular character */
+ result = (no_Magic(t->state->c) == c);
+ if (!result)
+ result = ireg_ic == TRUE
+ && MB_TOLOWER(t->state->c) == MB_TOLOWER(c);
+ ADD_POS_NEG_STATE(t->state);
+ break;
+ }
+
+ } /* for (thislist = thislist; thislist->state; thislist++) */
+
+ /* The first found match is the leftmost one, but there may be a
+ * longer one. Keep running the NFA, but don't start from the
+ * beginning. Also, do not add the start state in recursive calls of
+ * nfa_regmatch(), because recursive calls should only start in the
+ * first position. */
+ if (match == FALSE && start->c == NFA_MOPEN + 0)
+ {
+#ifdef ENABLE_LOG
+ fprintf(log_fd, "(---) STARTSTATE\n");
+#endif
+ addstate(nextlist, start, m, n, listid + 1, &match);
+ }
+
+ if (reginput_updated)
+ {
+ reginput_updated = FALSE;
+ goto again;
+ }
+
+#ifdef ENABLE_LOG
+ fprintf(log_fd, ">>> Thislist had %d states available: ", thislist->n);
+ for (i = 0; i< thislist->n; i++)
+ fprintf(log_fd, "%d ", abs(thislist->t[i].state->id));
+ fprintf(log_fd, "\n");
+#endif
+
+nextchar:
+ reginput += n;
+ } while (c || reginput_updated);
+
+#ifdef ENABLE_LOG
+ if (log_fd != stderr)
+ fclose(log_fd);
+ log_fd = NULL;
+#endif
+
+theend:
+ /* Free memory */
+ vim_free(list[0].t);
+ vim_free(list[1].t);
+ vim_free(list[2].t);
+ list[0].t = list[1].t = list[2].t = NULL;
+ if (listids != NULL)
+ vim_free(listids);
+#undef ADD_POS_NEG_STATE
+#ifdef DEBUG
+ fclose(debug);
+#endif
+
+ return match;
+}
+
+/*
+ * Try match of "prog" with at regline["col"].
+ * Returns 0 for failure, number of lines contained in the match otherwise.
+ */
+ static long
+nfa_regtry(start, col)
+ nfa_state_T *start;
+ colnr_T col;
+{
+ int i;
+ regsub_T sub, m;
+#ifdef ENABLE_LOG
+ FILE *f;
+#endif
+
+ reginput = regline + col;
+ need_clear_subexpr = TRUE;
+
+#ifdef ENABLE_LOG
+ f = fopen(LOG_NAME, "a");
+ if (f != NULL)
+ {
+ fprintf(f, "\n\n\n\n\n\n\t\t=======================================================\n");
+ fprintf(f, " =======================================================\n");
+#ifdef DEBUG
+ fprintf(f, "\tRegexp is \"%s\"\n", nfa_regengine.expr);
+#endif
+ fprintf(f, "\tInput text is \"%s\" \n", reginput);
+ fprintf(f, " =======================================================\n\n\n\n\n\n\n");
+ nfa_print_state(f, start, 0);
+ fprintf(f, "\n\n");
+ fclose(f);
+ }
+ else
+ EMSG(_("Could not open temporary log file for writing "));
+#endif
+
+ if (REG_MULTI)
+ {
+ /* Use 0xff to set lnum to -1 */
+ vim_memset(sub.startpos, 0xff, sizeof(lpos_T) * NSUBEXP);
+ vim_memset(sub.endpos, 0xff, sizeof(lpos_T) * NSUBEXP);
+ vim_memset(m.startpos, 0xff, sizeof(lpos_T) * NSUBEXP);
+ vim_memset(m.endpos, 0xff, sizeof(lpos_T) * NSUBEXP);
+ }
+ else
+ {
+ vim_memset(sub.start, 0, sizeof(char_u *) * NSUBEXP);
+ vim_memset(sub.end, 0, sizeof(char_u *) * NSUBEXP);
+ vim_memset(m.start, 0, sizeof(char_u *) * NSUBEXP);
+ vim_memset(m.end, 0, sizeof(char_u *) * NSUBEXP);
+ }
+
+ if (nfa_regmatch(start, &sub, &m) == FALSE)
+ return 0;
+
+ cleanup_subexpr();
+ if (REG_MULTI)
+ {
+ for (i = 0; i < NSUBEXP; i++)
+ {
+ reg_startpos[i] = sub.startpos[i];
+ reg_endpos[i] = sub.endpos[i];
+ }
+
+ if (reg_startpos[0].lnum < 0)
+ {
+ reg_startpos[0].lnum = 0;
+ reg_startpos[0].col = col;
+ }
+ if (reg_endpos[0].lnum < 0)
+ {
+ reg_endpos[0].lnum = reglnum;
+ reg_endpos[0].col = (int)(reginput - regline);
+ }
+ else
+ /* Use line number of "\ze". */
+ reglnum = reg_endpos[0].lnum;
+ }
+ else
+ {
+ for (i = 0; i < NSUBEXP; i++)
+ {
+ reg_startp[i] = sub.start[i];
+ reg_endp[i] = sub.end[i];
+ }
+
+ if (reg_startp[0] == NULL)
+ reg_startp[0] = regline + col;
+ if (reg_endp[0] == NULL)
+ reg_endp[0] = reginput;
+ }
+
+ return 1 + reglnum;
+}
+
+/*
+ * Match a regexp against a string ("line" points to the string) or multiple
+ * lines ("line" is NULL, use reg_getline()).
+ *
+ * Returns 0 for failure, number of lines contained in the match otherwise.
+ */
+ static long
+nfa_regexec_both(line, col)
+ char_u *line;
+ colnr_T col; /* column to start looking for match */
+{
+ nfa_regprog_T *prog;
+ long retval = 0L;
+ int i;
+
+ if (REG_MULTI)
+ {
+ prog = (nfa_regprog_T *)reg_mmatch->regprog;
+ line = reg_getline((linenr_T)0); /* relative to the cursor */
+ reg_startpos = reg_mmatch->startpos;
+ reg_endpos = reg_mmatch->endpos;
+ }
+ else
+ {
+ prog = (nfa_regprog_T *)reg_match->regprog;
+ reg_startp = reg_match->startp;
+ reg_endp = reg_match->endp;
+ }
+
+ /* Be paranoid... */
+ if (prog == NULL || line == NULL)
+ {
+ EMSG(_(e_null));
+ goto theend;
+ }
+
+ /* If the start column is past the maximum column: no need to try. */
+ if (ireg_maxcol > 0 && col >= ireg_maxcol)
+ goto theend;
+
+ /* If pattern contains "\c" or "\C": overrule value of ireg_ic */
+ if (prog->regflags & RF_ICASE)
+ ireg_ic = TRUE;
+ else if (prog->regflags & RF_NOICASE)
+ ireg_ic = FALSE;
+
+#ifdef FEAT_MBYTE
+ /* If pattern contains "\Z" overrule value of ireg_icombine */
+ if (prog->regflags & RF_ICOMBINE)
+ ireg_icombine = TRUE;
+#endif
+
+ regline = line;
+ reglnum = 0; /* relative to line */
+
+ nstate = prog->nstate;
+
+ for (i = 0; i < nstate; ++i)
+ {
+ prog->state[i].id = i;
+ prog->state[i].lastlist = 0;
+ prog->state[i].visits = 0;
+ prog->state[i].lastthread = NULL;
+ }
+
+ retval = nfa_regtry(prog->start, col);
+
+theend:
+ return retval;
+}
+
+/*
+ * Compile a regular expression into internal code for the NFA matcher.
+ * Returns the program in allocated space. Returns NULL for an error.
+ */
+ static regprog_T *
+nfa_regcomp(expr, re_flags)
+ char_u *expr;
+ int re_flags;
+{
+ nfa_regprog_T *prog;
+ int prog_size;
+ int *postfix;
+
+ if (expr == NULL)
+ return NULL;
+
+#ifdef DEBUG
+ nfa_regengine.expr = expr;
+#endif
+
+ init_class_tab();
+
+ if (nfa_regcomp_start(expr, re_flags) == FAIL)
+ return NULL;
+
+ /* Space for compiled regexp */
+ prog_size = sizeof(nfa_regprog_T) + sizeof(nfa_state_T) * nstate_max;
+ prog = (nfa_regprog_T *)lalloc(prog_size, TRUE);
+ if (prog == NULL)
+ goto fail;
+ vim_memset(prog, 0, prog_size);
+
+ /* Build postfix form of the regexp. Needed to build the NFA
+ * (and count its size) */
+ postfix = re2post();
+ if (postfix == NULL)
+ goto fail; /* Cascaded (syntax?) error */
+
+ /*
+ * In order to build the NFA, we parse the input regexp twice:
+ * 1. first pass to count size (so we can allocate space)
+ * 2. second to emit code
+ */
+#ifdef ENABLE_LOG
+ {
+ FILE *f = fopen(LOG_NAME, "a");
+
+ if (f != NULL)
+ {
+ fprintf(f, "\n*****************************\n\n\n\n\tCompiling regexp \"%s\" ... hold on !\n", expr);
+ fclose(f);
+ }
+ }
+#endif
+
+ /*
+ * PASS 1
+ * Count number of NFA states in "nstate". Do not build the NFA.
+ */
+ post2nfa(postfix, post_ptr, TRUE);
+ state_ptr = prog->state;
+
+ /*
+ * PASS 2
+ * Build the NFA
+ */
+ prog->start = post2nfa(postfix, post_ptr, FALSE);
+ if (prog->start == NULL)
+ goto fail;
+
+ prog->regflags = regflags;
+ prog->engine = &nfa_regengine;
+ prog->nstate = nstate;
+#ifdef ENABLE_LOG
+ nfa_postfix_dump(expr, OK);
+ nfa_dump(prog);
+#endif
+
+out:
+ vim_free(post_start);
+ post_start = post_ptr = post_end = NULL;
+ state_ptr = NULL;
+ return (regprog_T *)prog;
+
+fail:
+ vim_free(prog);
+ prog = NULL;
+#ifdef ENABLE_LOG
+ nfa_postfix_dump(expr, FAIL);
+#endif
+#ifdef DEBUG
+ nfa_regengine.expr = NULL;
+#endif
+ goto out;
+}
+
+
+/*
+ * Match a regexp against a string.
+ * "rmp->regprog" is a compiled regexp as returned by nfa_regcomp().
+ * Uses curbuf for line count and 'iskeyword'.
+ *
+ * Return TRUE if there is a match, FALSE if not.
+ */
+ static int
+nfa_regexec(rmp, line, col)
+ regmatch_T *rmp;
+ char_u *line; /* string to match against */
+ colnr_T col; /* column to start looking for match */
+{
+ reg_match = rmp;
+ reg_mmatch = NULL;
+ reg_maxline = 0;
+ reg_line_lbr = FALSE;
+ reg_buf = curbuf;
+ reg_win = NULL;
+ ireg_ic = rmp->rm_ic;
+#ifdef FEAT_MBYTE
+ ireg_icombine = FALSE;
+#endif
+ ireg_maxcol = 0;
+ return (nfa_regexec_both(line, col) != 0);
+}
+
+#if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
+ || defined(FIND_REPLACE_DIALOG) || defined(PROTO)
+
+static int nfa_regexec_nl __ARGS((regmatch_T *rmp, char_u *line, colnr_T col));
+
+/*
+ * Like nfa_regexec(), but consider a "\n" in "line" to be a line break.
+ */
+ static int
+nfa_regexec_nl(rmp, line, col)
+ regmatch_T *rmp;
+ char_u *line; /* string to match against */
+ colnr_T col; /* column to start looking for match */
+{
+ reg_match = rmp;
+ reg_mmatch = NULL;
+ reg_maxline = 0;
+ reg_line_lbr = TRUE;
+ reg_buf = curbuf;
+ reg_win = NULL;
+ ireg_ic = rmp->rm_ic;
+#ifdef FEAT_MBYTE
+ ireg_icombine = FALSE;
+#endif
+ ireg_maxcol = 0;
+ return (nfa_regexec_both(line, col) != 0);
+}
+#endif
+
+
+/*
+ * Match a regexp against multiple lines.
+ * "rmp->regprog" is a compiled regexp as returned by vim_regcomp().
+ * Uses curbuf for line count and 'iskeyword'.
+ *
+ * Return zero if there is no match. Return number of lines contained in the
+ * match otherwise.
+ *
+ * Note: the body is the same as bt_regexec() except for nfa_regexec_both()
+ *
+ * ! Also NOTE : match may actually be in another line. e.g.:
+ * when r.e. is \nc, cursor is at 'a' and the text buffer looks like
+ *
+ * +-------------------------+
+ * |a |
+ * |b |
+ * |c |
+ * | |
+ * +-------------------------+
+ *
+ * then nfa_regexec_multi() returns 3. while the original
+ * vim_regexec_multi() returns 0 and a second call at line 2 will return 2.
+ *
+ * FIXME if this behavior is not compatible.
+ */
+ static long
+nfa_regexec_multi(rmp, win, buf, lnum, col, tm)
+ regmmatch_T *rmp;
+ win_T *win; /* window in which to search or NULL */
+ buf_T *buf; /* buffer in which to search */
+ linenr_T lnum; /* nr of line to start looking for match */
+ colnr_T col; /* column to start looking for match */
+ proftime_T *tm UNUSED; /* timeout limit or NULL */
+{
+ long r;
+ buf_T *save_curbuf = curbuf;
+
+ reg_match = NULL;
+ reg_mmatch = rmp;
+ reg_buf = buf;
+ reg_win = win;
+ reg_firstlnum = lnum;
+ reg_maxline = reg_buf->b_ml.ml_line_count - lnum;
+ reg_line_lbr = FALSE;
+ ireg_ic = rmp->rmm_ic;
+#ifdef FEAT_MBYTE
+ ireg_icombine = FALSE;
+#endif
+ ireg_maxcol = rmp->rmm_maxcol;
+
+ /* Need to switch to buffer "buf" to make vim_iswordc() work. */
+ curbuf = buf;
+ r = nfa_regexec_both(NULL, col);
+ curbuf = save_curbuf;
+
+ return r;
+}
+
+#ifdef DEBUG
+# undef ENABLE_LOG
+#endif
diff --git a/src/structs.h b/src/structs.h
index e84a2b612..d7bb88e5a 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -63,15 +63,16 @@ typedef struct growarray
#define GA_EMPTY {0, 0, 0, 0, NULL}
-/*
- * This is here because regexp.h needs pos_T and below regprog_T is used.
- */
-#include "regexp.h"
-
typedef struct window_S win_T;
typedef struct wininfo_S wininfo_T;
typedef struct frame_S frame_T;
typedef int scid_T; /* script ID */
+typedef struct file_buffer buf_T; /* forward declaration */
+
+/*
+ * This is here because regexp.h needs pos_T and below regprog_T is used.
+ */
+#include "regexp.h"
/*
* This is here because gui.h needs the pos_T and win_T, and win_T needs gui.h
@@ -526,8 +527,6 @@ typedef struct
# endif
} cmdmod_T;
-typedef struct file_buffer buf_T; /* forward declaration */
-
#define MF_SEED_LEN 8
struct memfile
diff --git a/src/testdir/Make_amiga.mak b/src/testdir/Make_amiga.mak
index 66c324357..1bd176c14 100644
--- a/src/testdir/Make_amiga.mak
+++ b/src/testdir/Make_amiga.mak
@@ -33,7 +33,7 @@ SCRIPTS = test1.out test3.out test4.out test5.out test6.out \
test76.out test77.out test78.out test79.out test80.out \
test81.out test82.out test83.out test84.out test88.out \
test89.out test90.out test91.out test92.out test93.out \
- test94.out
+ test94.out test95.out
.SUFFIXES: .in .out
@@ -144,3 +144,4 @@ test91.out: test91.in
test92.out: test92.in
test93.out: test93.in
test94.out: test94.in
+test95.out: test95.in
diff --git a/src/testdir/Make_dos.mak b/src/testdir/Make_dos.mak
index 3c2f9386b..679f16ce5 100644
--- a/src/testdir/Make_dos.mak
+++ b/src/testdir/Make_dos.mak
@@ -32,7 +32,7 @@ SCRIPTS = test3.out test4.out test5.out test6.out test7.out \
test79.out test80.out test81.out test82.out test83.out \
test84.out test85.out test86.out test87.out test88.out \
test89.out test90.out test91.out test92.out test93.out \
- test94.out
+ test94.out test95.out
SCRIPTS32 = test50.out test70.out
diff --git a/src/testdir/Make_ming.mak b/src/testdir/Make_ming.mak
index 6ae101b07..579376672 100644
--- a/src/testdir/Make_ming.mak
+++ b/src/testdir/Make_ming.mak
@@ -52,7 +52,7 @@ SCRIPTS = test3.out test4.out test5.out test6.out test7.out \
test79.out test80.out test81.out test82.out test83.out \
test84.out test85.out test86.out test87.out test88.out \
test89.out test90.out test91.out test92.out test93.out \
- test94.out
+ test94.out test95.out
SCRIPTS32 = test50.out test70.out
diff --git a/src/testdir/Make_os2.mak b/src/testdir/Make_os2.mak
index 2d6543b43..801443402 100644
--- a/src/testdir/Make_os2.mak
+++ b/src/testdir/Make_os2.mak
@@ -33,7 +33,7 @@ SCRIPTS = test1.out test3.out test4.out test5.out test6.out \
test76.out test77.out test78.out test79.out test80.out \
test81.out test82.out test83.out test84.out test88.out \
test89.out test90.out test91.out test92.out test93.out \
- test94.out
+ test94.out test95.out
.SUFFIXES: .in .out
diff --git a/src/testdir/Make_vms.mms b/src/testdir/Make_vms.mms
index 7770a6e7f..5ab0e415d 100644
--- a/src/testdir/Make_vms.mms
+++ b/src/testdir/Make_vms.mms
@@ -4,7 +4,7 @@
# Authors: Zoltan Arpadffy, <arpadffy@polarhome.com>
# Sandor Kopanyi, <sandor.kopanyi@mailbox.hu>
#
-# Last change: 2013 Apr 12
+# Last change: 2013 May 18
#
# This has been tested on VMS 6.2 to 8.3 on DEC Alpha, VAX and IA64.
# Edit the lines in the Configuration section below to select.
@@ -77,7 +77,8 @@ SCRIPT = test1.out test2.out test3.out test4.out test5.out \
test71.out test72.out test74.out test75.out test76.out \
test77.out test78.out test79.out test80.out test81.out \
test82.out test83.out test84.out test88.out test89.out \
- test90.out test91.out test92.out test93.out test94.out
+ test90.out test91.out test92.out test93.out test94.out \
+ test95.out
# Known problems:
# Test 30: a problem around mac format - unknown reason
diff --git a/src/testdir/Makefile b/src/testdir/Makefile
index f76f6459b..6573e8ac7 100644
--- a/src/testdir/Makefile
+++ b/src/testdir/Makefile
@@ -29,7 +29,7 @@ SCRIPTS = test1.out test2.out test3.out test4.out test5.out test6.out \
test79.out test80.out test81.out test82.out test83.out \
test84.out test85.out test86.out test87.out test88.out \
test89.out test90.out test91.out test92.out test93.out \
- test94.out
+ test94.out test95.out
SCRIPTS_GUI = test16.out
@@ -85,13 +85,16 @@ test1.out: test1.in
fi"
# Check if the test.out file matches test.ok.
- @/bin/sh -c "if test -f test.out; then\
+ @/bin/sh -c "if test -f test.out; then \
if diff test.out $*.ok; \
then mv -f test.out $*.out; \
else echo $* FAILED >>test.log; mv -f test.out $*.failed; \
fi \
else echo $* NO OUTPUT >>test.log; \
fi"
+ @/bin/sh -c "if test -f valgrind; then\
+ mv -f valgrind valgrind.$*; \
+ fi"
-rm -rf X* test.ok viminfo
test49.out: test49.vim
diff --git a/src/testdir/test64.in b/src/testdir/test64.in
index d45e357a9..be7128286 100644
--- a/src/testdir/test64.in
+++ b/src/testdir/test64.in
@@ -1,4 +1,5 @@
-Test for regexp patterns.
+Test for regexp patterns without multi-byte support.
+See test95 for multi-byte tests.
A pattern that gives the expected result produces OK, so that we know it was
actually tried.
@@ -14,6 +15,11 @@ STARTTEST
:" etc.
:" When there is no match use only the first two items.
:let tl = []
+
+:""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+:"""" Previously written tests """"""""""""""""""""""""""""""""
+:""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+
:call add(tl, ['ab', 'aab', 'ab'])
:call add(tl, ['b', 'abcdef', 'b'])
:call add(tl, ['bc*', 'abccccdef', 'bcccc'])
@@ -132,6 +138,164 @@ STARTTEST
:"
:call add(tl, ['\v(a*)+', 'aaaa', 'aaaa', ''])
:call add(tl, ['x', 'abcdef'])
+
+:""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+:""""" Simple tests """""""""""""""""""""""""""""""""""""""""""
+:""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
+
+:" Search single groups
+:call add(tl, ['ab', 'aab', 'ab'])
+:call add(tl, ['ab', 'baced'])
+:call add(tl, ['ab', ' ab ', 'ab'])
+
+:" Search multi-modifiers
+:call add(tl, ['x*', 'xcd', 'x'])
+:call add(tl, ['x*', 'xxxxxxxxxxxxxxxxsofijiojgf', 'xxxxxxxxxxxxxxxx'])
+:call add(tl, ['x*', 'abcdoij', '']) " empty match is good
+:call add(tl, ['x\+', 'abcdoin']) " no match here
+:call add(tl, ['x\+', 'abcdeoijdfxxiuhfij', 'xx'])
+:call add(tl, ['x\+', 'xxxxx', 'xxxxx'])
+:call add(tl, ['x\+', 'abc x siufhiush xxxxxxxxx', 'x'])
+:call add(tl, ['x\=', 'x sdfoij', 'x'])
+:call add(tl, ['x\=', 'abc sfoij', '']) " empty match is good
+:call add(tl, ['x\=', 'xxxxxxxxx c', 'x'])
+:call add(tl, ['x\?', 'x sdfoij', 'x'])
+:call add(tl, ['x\?', 'abc sfoij', '']) " empty match is good
+:call add(tl, ['x\?', 'xxxxxxxxxx c', 'x'])
+
+:call add(tl, ['a\{0,0}', 'abcdfdoij', ''])
+:call add(tl, ['a\{0,1}', 'asiubid axxxaaa', 'a']) " same thing as 'a?'
+:call add(tl, ['a\{1,0}', 'asiubid axxxaaa', 'a']) " same thing as 'a\{0,1}'
+:call add(tl, ['a\{3,6}', 'aa siofuh'])
+:call add(tl, ['a\{3,6}', 'aaaaa asfoij afaa', 'aaaaa'])
+:call add(tl, ['a\{3,6}', 'aaaaaaaa', 'aaaaaa'])
+:call add(tl, ['a\{0}', 'asoiuj', ''])
+:call add(tl, ['a\{2}', 'aaaa', 'aa'])
+:call add(tl, ['a\{2}', 'iuash fiusahfliusah fiushfilushfi uhsaifuh askfj nasfvius afg aaaa sfiuhuhiushf', 'aa'])
+:call add(tl, ['a\{2}', 'abcdefghijklmnopqrestuvwxyz1234567890'])
+:call add(tl, ['a\{0,}', 'oij sdigfusnf', '']) " same thing as 'a*'
+:call add(tl, ['a\{0,}', 'aaaaa aa', 'aaaaa'])
+:call add(tl, ['a\{2,}', 'sdfiougjdsafg'])
+:call add(tl, ['a\{2,}', 'aaaaasfoij ', 'aaaaa'])
+:call add(tl, ['a\{,0}', 'oidfguih iuhi hiu aaaa', ''])
+:call add(tl, ['a\{,5}', 'abcd', 'a'])
+:call add(tl, ['a\{,5}', 'aaaaaaaaaa', 'aaaaa'])
+:call add(tl, ['a\{}', 'bbbcddiuhfcd', '']) " same thing as 'a*'
+:call add(tl, ['a\{}', 'aaaaioudfh coisf jda', 'aaaa'])
+
+:call add(tl, ['a\{-0,0}', 'abcdfdoij', ''])
+:call add(tl, ['a\{-0,1}', 'asiubid axxxaaa', '']) " anti-greedy version of 'a?'
+:call add(tl, ['a\{-3,6}', 'aa siofuh'])
+:call add(tl, ['a\{-3,6}', 'aaaaa asfoij afaa', 'aaa'])
+:call add(tl, ['a\{-3,6}', 'aaaaaaaa', 'aaa'])
+:call add(tl, ['a\{-0}', 'asoiuj', ''])
+:call add(tl, ['a\{-2}', 'aaaa', 'aa'])
+:call add(tl, ['a\{-2}', 'abcdefghijklmnopqrestuvwxyz1234567890'])
+:call add(tl, ['a\{-0,}', 'oij sdigfusnf', ''])
+:call add(tl, ['a\{-0,}', 'aaaaa aa', ''])
+:call add(tl, ['a\{-2,}', 'sdfiougjdsafg'])
+:call add(tl, ['a\{-2,}', 'aaaaasfoij ', 'aa'])
+:call add(tl, ['a\{-,0}', 'oidfguih iuhi hiu aaaa', ''])
+:call add(tl, ['a\{-,5}', 'abcd', ''])
+:call add(tl, ['a\{-,5}', 'aaaaaaaaaa', ''])
+:call add(tl, ['a\{-}', 'bbbcddiuhfcd', '']) " anti-greedy version of 'a*'
+:call add(tl, ['a\{-}', 'aaaaioudfh coisf jda', ''])
+
+:" Test groups of characters and submatches
+:call add(tl, ['\(abc\)*', 'abcabcabc', 'abcabcabc', 'abc'])
+:call add(tl, ['\(ab\)\+', 'abababaaaaa', 'ababab', 'ab'])
+:call add(tl, ['\(abaaaaa\)*cd', 'cd', 'cd', ''])
+:call add(tl, ['\(test1\)\? \(test2\)\?', 'test1 test3', 'test1 ', 'test1', ''])
+:call add(tl, ['\(test1\)\= \(test2\) \(test4443\)\=', ' test2 test4443 yupiiiiiiiiiii', ' test2 test4443', '', 'test2', 'test4443'])
+:call add(tl, ['\(\(sub1\) hello \(sub 2\)\)', 'asterix sub1 hello sub 2 obelix', 'sub1 hello sub 2', 'sub1 hello sub 2', 'sub1', 'sub 2'])
+:call add(tl, ['\(\(\(yyxxzz\)\)\)', 'abcdddsfiusfyyzzxxyyxxzz', 'yyxxzz', 'yyxxzz', 'yyxxzz', 'yyxxzz'])
+:call add(tl, ['\v((ab)+|c+)+', 'abcccaba', 'abcccab', 'ab', 'ab'])
+:call add(tl, ['\v((ab)|c*)+', 'abcccaba', 'abcccab', '', 'ab'])
+:call add(tl, ['\v(a(c*)+b)+', 'acbababaaa', 'acbabab', 'ab', ''])
+:call add(tl, ['\v(a|b*)+', 'aaaa', 'aaaa', ''])
+
+:" Test greedy-ness and lazy-ness
+:call add(tl, ['a\{-2,7}','aaaaaaaaaaaaa', 'aa'])
+:call add(tl, ['a\{2,7}','aaaaaaaaaaaaaaaaaaaa', 'aaaaaaa'])
+:call add(tl, ['\vx(.{-,8})yz(.*)','xayxayzxayzxayz','xayxayzxayzxayz','ayxa','xayzxayz'])
+:call add(tl, ['\vx(.*)yz(.*)','xayxayzxayzxayz','xayxayzxayzxayz', 'ayxayzxayzxa',''])
+:call add(tl, ['\v(a{1,2}){-2,3}','aaaaaaa','aaaa','aa'])
+:call add(tl, ['\v(a{-1,3})+','aa','aa','a'])
+
+:" Test Character classes
+:call add(tl, ['\d\+e\d\d','test 10e23 fd','10e23'])
+
+:" Test collections and character range []
+:call add(tl, ['\v[a]', 'abcd', 'a'])
+:call add(tl, ['a[bcd]', 'abcd', 'ab'])
+:call add(tl, ['a[b-d]', 'acbd', 'ac'])
+:call add(tl, ['[a-d][e-f][x-x]d', 'cexdxx', 'cexd'])
+:call add(tl, ['\v[[:alpha:]]+', 'abcdefghijklmnopqrstuvwxyz6','abcdefghijklmnopqrstuvwxyz'])
+:call add(tl, ['[[:alpha:]\+]', '6x8','x'])
+:call add(tl, ['[^abc]\+','abcabcabc'])
+:call add(tl, ['[^abc]','defghiasijvoinasoiunbvb','d'])
+:call add(tl, ['[^abc]\+','ddddddda','ddddddd'])
+:call add(tl, ['[^a-d]\+','aaaAAAZIHFNCddd','AAAZIHFNC'])
+:call add(tl, ['[a-f]*','iiiiiiii',''])
+:call add(tl, ['[a-f]*','abcdefgh','abcdef'])
+:call add(tl, ['[^a-f]\+','abcdefgh','gh'])
+:call add(tl, ['[a-c]\{-3,6}','abcabc','abc'])
+:call add(tl, ['[^[:alpha:]]\+','abcccadfoij7787ysf287yrnccdu','7787'])
+:call add(tl, ['[-a]', '-', '-'])
+:call add(tl, ['[a-]', '-', '-'])
+:call add(tl, ['[-./[:alnum:]_~]\+', 'log13.file', 'log13.file']) " filename regexp
+:call add(tl, ['[\]\^\-\\]\+', '\^\\\-\---^', '\^\\\-\---^']) " special chars
+:call add(tl, ['[[.a.]]\+', 'aa', 'aa']) " collation elem
+:call add(tl, ['abc[0-9]*ddd', 'siuhabc ii']) " middle of regexp
+:call add(tl, ['abc[0-9]*ddd', 'adf abc44482ddd oijs', 'abc44482ddd'])
+:call add(tl, ['\_[0-9]\+', 'asfi9888u', '9888'])
+:call add(tl, ['[0-9\n]\+', 'asfi9888u', '9888'])
+
+
+:"""" Test recognition of some character classes
+:call add(tl, ['[0-9]', '8', '8'])
+:call add(tl, ['[^0-9]', '8'])
+:call add(tl, ['[0-9a-fA-F]*', '0a7', '0a7'])
+:call add(tl, ['[^0-9A-Fa-f]\+', '0a7'])
+:call add(tl, ['[a-z_A-Z0-9]\+', 'aso_sfoij', 'aso_sfoij'])
+:call add(tl, ['[a-z]', 'a', 'a'])
+:call add(tl, ['[a-zA-Z]', 'a', 'a'])
+:call add(tl, ['[A-Z]', 'a'])
+:call add(tl, ['\C[^A-Z]\+', 'ABCOIJDEOIFNSD jsfoij sa', ' jsfoij sa'])
+
+:"""" Tests for \z features
+:call add(tl, ['xx \ze test', 'xx ']) " must match after \ze
+:call add(tl, ['abc\zeend', 'oij abcend', 'abc'])
+:call add(tl, ['abc\zsdd', 'ddabcddxyzt', 'dd'])
+:call add(tl, ['aa \zsax', ' ax']) " must match before \zs
+:call add(tl, ['abc \zsmatch\ze abc', 'abc abc abc match abc abc', 'match'])
+:call add(tl, ['\v(a \zsif .*){2}', 'a if then a if last', 'if last', 'a if last'])
+
+:"""" Tests for \@ features
+:call add(tl, ['abc\@=', 'abc', 'ab'])
+:call add(tl, ['abc\@=cd', 'abcd', 'abcd'])
+:call add(tl, ['abc\@=', 'ababc', 'ab'])
+:call add(tl, ['abcd\@=e', 'abcd']) " will never match, no matter the input text
+:call add(tl, ['abcd\@=e', 'any text in here ... ']) " will never match
+:call add(tl, ['\v(abc)@=..', 'xabcd', 'ab', 'abc'])
+:call add(tl, ['\(.*John\)\@=.*Bob', 'here is John, and here is B']) " no match
+:call add(tl, ['\(John.*\)\@=.*Bob', 'John is Bobs friend', 'John is Bob', 'John is Bobs friend'])
+:call add(tl, ['.*John\&.*Bob', 'here is John, and here is B']) " no match
+:call add(tl, ['.*John\&.*Bob', 'John is Bobs friend', 'John is Bob'])
+:call add(tl, ['\v(test1)@=.*yep', 'this is a test1, yep it is', 'test1, yep', 'test1'])
+
+:"""" Combining different tests and features
+:call add(tl, ['[[:alpha:]]\{-2,6}', '787abcdiuhsasiuhb4', 'ab'])
+:call add(tl, ['[^[=a=]]\+', 'ddaãâbcd', 'dd'])
+:call add(tl, ['', 'abcd', ''])
+:call add(tl, ['\v(())', 'any possible text', ''])
+:call add(tl, ['\v%(ab(xyz)c)', ' abxyzc ', 'abxyzc', 'xyz'])
+:call add(tl, ['\v(test|)empty', 'tesempty', 'empty', ''])
+:call add(tl, ['\v(a|aa)(a|aa)', 'aaa', 'aa', 'a', 'a'])
+
+
+:"""" Run the tests
+
:"
:for t in tl
: let l = matchlist(t[1], t[0])
@@ -143,7 +307,7 @@ STARTTEST
: elseif len(t) > 2 && l[0] != t[2]
: $put ='ERROR: pat: \"' . t[0] . '\", text: \"' . t[1] . '\", match: \"' . l[0] . '\", expected: \"' . t[2] . '\"'
: else
-: $put ='OK'
+: $put ='OK - ' . t[0]
: endif
: if len(l) > 0
:" check all the nine submatches
@@ -161,7 +325,17 @@ STARTTEST
: endif
:endfor
:unlet t tl e l
-:/^Results/,$wq! test.out
+
+:" Check that \_[0-9] matching EOL does not break a following \>
+:" This only works on a buffer line, not with expression evaluation
+/^Find this
+/\<\(\(25\_[0-5]\|2\_[0-4]\_[0-9]\|\_[01]\?\_[0-9]\_[0-9]\?\)\.\)\{3\}\(25\_[0-5]\|2\_[0-4]\_[0-9]\|\_[01]\?\_[0-9]\_[0-9]\?\)\>
+y$Gop:"
+
+:/\%#=1^Results/,$wq! test.out
ENDTEST
+Find this:
+localnet/192.168.0.1
+
Results of test64:
diff --git a/src/testdir/test64.ok b/src/testdir/test64.ok
index 1692aae25..c315a23eb 100644
--- a/src/testdir/test64.ok
+++ b/src/testdir/test64.ok
@@ -1,102 +1,230 @@
Results of test64:
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
-OK
+OK - ab
+OK - b
+OK - bc*
+OK - bc\{-}
+OK - bc\{-}\(d\)
+OK - bc*
+OK - c*
+OK - bc*
+OK - c*
+OK - bc\+
+OK - bc\+
+OK - a\|ab
+OK - c\?
+OK - bc\?
+OK - bc\?
+OK - \va{1}
+OK - \va{2}
+OK - \va{2}
+OK - \va{2}
+OK - \va{2}
+OK - \va{2}
+OK - \va{2}
+OK - \vb{1}
+OK - \vba{2}
+OK - \vba{3}
+OK - \v(ab){1}
+OK - \v(ab){1}
+OK - \v(ab){1}
+OK - \v(ab){0,2}
+OK - \v(ab){0,2}
+OK - \v(ab){1,2}
+OK - \v(ab){1,2}
+OK - \v(ab){2,4}
+OK - \v(ab){2,4}
+OK - \v(ab){2}
+OK - \v(ab){2}
+OK - \v(ab){2}
+OK - \v(ab){2}
+OK - \v((ab){2}){2}
+OK - \v((ab){2}){2}
+OK - \v(a{1}){1}
+OK - \v(a{2}){1}
+OK - \v(a{2}){1}
+OK - \v(a{2}){1}
+OK - \v(a{1}){2}
+OK - \v(a{1}){2}
+OK - \v(a{2})+
+OK - \v(a{2})+
+OK - \v(a{2}){1}
+OK - \v(a{1}){2}
+OK - \v(a{1}){1}
+OK - \v(a{2}){2}
+OK - \v(a{2}){2}
+OK - \v(a+){2}
+OK - \v(a{3}){2}
+OK - \v(a{1,2}){2}
+OK - \v(a{1,3}){2}
+OK - \v(a{1,3}){2}
+OK - \v(a{1,3}){3}
+OK - \v(a{1,2}){2}
+OK - \v(a+)+
+OK - \v(a+)+
+OK - \v(a+){1,2}
+OK - \v(a+)(a+)
+OK - \v(a{3})+
+OK - \v(a|b|c)+
+OK - \v(a|b|c){2}
+OK - \v(abc){2}
+OK - \v(abc){2}
+OK - a*
+OK - \v(a*)+
+OK - \v((ab)+)+
+OK - \v(((ab)+)+)+
+OK - \v(((ab)+)+)+
+OK - \v(a{0,2})+
+OK - \v(a*)+
+OK - \v((a*)+)+
+OK - \v((ab)*)+
+OK - \va{1,3}
+OK - \va{2,3}
+OK - \v((ab)+|c*)+
+OK - \v(a{2})|(b{3})
+OK - \va{2}|b{2}
+OK - \v(a)+|(c)+
+OK - \vab{2,3}c
+OK - \vab{2,3}c
+OK - \vab{2,3}cd{2,3}e
+OK - \va(bc){2}d
+OK - \va*a{2}
+OK - \va*a{2}
+OK - \va*a{2}
+OK - \va*a{2}
+OK - \va*b*|a*c*
+OK - \va{1}b{1}|a{1}b{1}
+OK - \v(a)
+OK - \v(a)(b)
+OK - \v(ab)(b)(c)
+OK - \v((a)(b))
+OK - \v(a)|(b)
+OK - \v(a*)+
+OK - x
+OK - ab
+OK - ab
+OK - ab
+OK - x*
+OK - x*
+OK - x*
+OK - x\+
+OK - x\+
+OK - x\+
+OK - x\+
+OK - x\=
+OK - x\=
+OK - x\=
+OK - x\?
+OK - x\?
+OK - x\?
+OK - a\{0,0}
+OK - a\{0,1}
+OK - a\{1,0}
+OK - a\{3,6}
+OK - a\{3,6}
+OK - a\{3,6}
+OK - a\{0}
+OK - a\{2}
+OK - a\{2}
+OK - a\{2}
+OK - a\{0,}
+OK - a\{0,}
+OK - a\{2,}
+OK - a\{2,}
+OK - a\{,0}
+OK - a\{,5}
+OK - a\{,5}
+OK - a\{}
+OK - a\{}
+OK - a\{-0,0}
+OK - a\{-0,1}
+OK - a\{-3,6}
+OK - a\{-3,6}
+OK - a\{-3,6}
+OK - a\{-0}
+OK - a\{-2}
+OK - a\{-2}
+OK - a\{-0,}
+OK - a\{-0,}
+OK - a\{-2,}
+OK - a\{-2,}
+OK - a\{-,0}
+OK - a\{-,5}
+OK - a\{-,5}
+OK - a\{-}
+OK - a\{-}
+OK - \(abc\)*
+OK - \(ab\)\+
+OK - \(abaaaaa\)*cd
+OK - \(test1\)\? \(test2\)\?
+OK - \(test1\)\= \(test2\) \(test4443\)\=
+OK - \(\(sub1\) hello \(sub 2\)\)
+OK - \(\(\(yyxxzz\)\)\)
+OK - \v((ab)+|c+)+
+OK - \v((ab)|c*)+
+OK - \v(a(c*)+b)+
+OK - \v(a|b*)+
+OK - a\{-2,7}
+OK - a\{2,7}
+OK - \vx(.{-,8})yz(.*)
+OK - \vx(.*)yz(.*)
+OK - \v(a{1,2}){-2,3}
+OK - \v(a{-1,3})+
+OK - \d\+e\d\d
+OK - \v[a]
+OK - a[bcd]
+OK - a[b-d]
+OK - [a-d][e-f][x-x]d
+OK - \v[[:alpha:]]+
+OK - [[:alpha:]\+]
+OK - [^abc]\+
+OK - [^abc]
+OK - [^abc]\+
+OK - [^a-d]\+
+OK - [a-f]*
+OK - [a-f]*
+OK - [^a-f]\+
+OK - [a-c]\{-3,6}
+OK - [^[:alpha:]]\+
+OK - [-a]
+OK - [a-]
+OK - [-./[:alnum:]_~]\+
+OK - [\]\^\-\\]\+
+OK - [[.a.]]\+
+OK - abc[0-9]*ddd
+OK - abc[0-9]*ddd
+OK - \_[0-9]\+
+OK - [0-9\n]\+
+OK - [0-9]
+OK - [^0-9]
+OK - [0-9a-fA-F]*
+OK - [^0-9A-Fa-f]\+
+OK - [a-z_A-Z0-9]\+
+OK - [a-z]
+OK - [a-zA-Z]
+OK - [A-Z]
+OK - \C[^A-Z]\+
+OK - xx \ze test
+OK - abc\zeend
+OK - abc\zsdd
+OK - aa \zsax
+OK - abc \zsmatch\ze abc
+OK - \v(a \zsif .*){2}
+OK - abc\@=
+OK - abc\@=cd
+OK - abc\@=
+OK - abcd\@=e
+OK - abcd\@=e
+OK - \v(abc)@=..
+OK - \(.*John\)\@=.*Bob
+OK - \(John.*\)\@=.*Bob
+OK - .*John\&.*Bob
+OK - .*John\&.*Bob
+OK - \v(test1)@=.*yep
+OK - [[:alpha:]]\{-2,6}
+OK - [^[=a=]]\+
+OK -
+OK - \v(())
+OK - \v%(ab(xyz)c)
+OK - \v(test|)empty
+OK - \v(a|aa)(a|aa)
+192.168.0.1
diff --git a/src/testdir/test95.in b/src/testdir/test95.in
new file mode 100644
index 000000000..78a999f56
--- /dev/null
+++ b/src/testdir/test95.in
@@ -0,0 +1,63 @@
+Test for regexp patterns with multi-byte support.
+See test64 for the non-multi-byte tests.
+
+A pattern that gives the expected result produces OK, so that we know it was
+actually tried.
+
+STARTTEST
+:so small.vim
+:so mbyte.vim
+:" tl is a List of Lists with:
+:" regexp pattern
+:" text to test the pattern on
+:" expected match (optional)
+:" expected submatch 1 (optional)
+:" expected submatch 2 (optional)
+:" etc.
+:" When there is no match use only the first two items.
+:let tl = []
+
+:"""" Multi-byte character tests. These will fail unless vim is compiled
+:"""" with Multibyte (FEAT_MBYTE) or BIG/HUGE features.
+:call add(tl, ['[[:alpha:][=a=]]\+', '879 aiaãâaiuvna ', 'aiaãâaiuvna'])
+:call add(tl, ['[[=a=]]\+', 'ddaãâbcd', 'aãâ']) " equivalence classes
+:call add(tl, ['[^ม ]\+', 'มม oijasoifjos ifjoisj f osij j มมมมม abcd', 'oijasoifjos'])
+:call add(tl, [' [^ ]\+', 'start มabcdม ', ' มabcdม'])
+:call add(tl, ['[ม[:alpha:][=a=]]\+', '879 aiaãมâมaiuvna ', 'aiaãมâมaiuvna'])
+
+:"""" Run the tests
+
+:"
+:for t in tl
+: let l = matchlist(t[1], t[0])
+:" check the match itself
+: if len(l) == 0 && len(t) > 2
+: $put ='ERROR: pat: \"' . t[0] . '\", text: \"' . t[1] . '\", did not match, expected: \"' . t[2] . '\"'
+: elseif len(l) > 0 && len(t) == 2
+: $put ='ERROR: pat: \"' . t[0] . '\", text: \"' . t[1] . '\", match: \"' . l[0] . '\", expected no match'
+: elseif len(t) > 2 && l[0] != t[2]
+: $put ='ERROR: pat: \"' . t[0] . '\", text: \"' . t[1] . '\", match: \"' . l[0] . '\", expected: \"' . t[2] . '\"'
+: else
+: $put ='OK - ' . t[0]
+: endif
+: if len(l) > 0
+:" check all the nine submatches
+: for i in range(1, 9)
+: if len(t) <= i + 2
+: let e = ''
+: else
+: let e = t[i + 2]
+: endif
+: if l[i] != e
+: $put ='ERROR: pat: \"' . t[0] . '\", text: \"' . t[1] . '\", submatch ' . i . ': \"' . l[i] . '\", expected: \"' . e . '\"'
+: endif
+: endfor
+: unlet i
+: endif
+:endfor
+:unlet t tl e l
+
+:/\%#=1^Results/,$wq! test.out
+ENDTEST
+
+Results of test95:
diff --git a/src/testdir/test95.ok b/src/testdir/test95.ok
new file mode 100644
index 000000000..d135b0eb8
--- /dev/null
+++ b/src/testdir/test95.ok
@@ -0,0 +1,6 @@
+Results of test95:
+OK - [[:alpha:][=a=]]\+
+OK - [[=a=]]\+
+OK - [^ม ]\+
+OK - [^ ]\+
+OK - [ม[:alpha:][=a=]]\+
diff --git a/src/version.c b/src/version.c
index b897c0973..86c012fec 100644
--- a/src/version.c
+++ b/src/version.c
@@ -729,6 +729,8 @@ static char *(features[]) =
static int included_patches[] =
{ /* Add new patch number below this line */
/**/
+ 970,
+/**/
969,
/**/
968,
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 13:49:37 +0000