summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorBram Moolenaar <Bram@vim.org>2013-05-19 19:40:29 +0200
committerBram Moolenaar <Bram@vim.org>2013-05-19 19:40:29 +0200
commitfbc0d2ea1e13fb55c267b72d64046e5ef984b97f (patch)
tree8c539274e29070536bb28615e32d236983361246 /src
parent6fa41fb3746e5ab2f793de713879afc9b1e25647 (diff)
downloadvim-git-fbc0d2ea1e13fb55c267b72d64046e5ef984b97f.tar.gz
updated for version 7.3.970v7.3.970
Problem: Syntax highlighting can be slow. Solution: Include the NFA regexp engine. Add the 'regexpengine' option to select which one is used. (various authors, including Ken Takata, Andrei Aiordachioaie, Russ Cox, Xiaozhou Liua, Ian Young)
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,
View Lorry Controller Status