refactor: combine regexp files

regext_bt.c and regexp_nfa.c are inlined into regexp.c instead of
included as a header. This makes developer tools like clang-tidy and
clangd be able to understand the code better.

5 files changed, 13273 insertions, 13317 deletions

diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt
index 85e12d66de..71e99538c7 100644
--- a/src/nvim/CMakeLists.txt
+++ b/src/nvim/CMakeLists.txt
@@ -362,12 +362,6 @@ list(APPEND LINT_NVIM_SOURCES ${NVIM_SOURCES} ${NVIM_HEADERS})
 
 foreach(sfile ${NVIM_SOURCES})
   get_filename_component(f ${sfile} NAME)
-  if(${f} MATCHES "^(regexp_nfa.c)$")
-    list(APPEND to_remove ${sfile})
-  endif()
-  if(${f} MATCHES "^(regexp_bt.c)$")
-    list(APPEND to_remove ${sfile})
-  endif()
   if(WIN32 AND ${f} MATCHES "^(pty_process_unix.c)$")
     list(APPEND to_remove ${sfile})
   endif()
@@ -456,8 +450,6 @@ set(LUA_GEN_DEPS ${GENERATOR_PRELOAD} $<TARGET_FILE:nlua0>)
 # NVIM_GENERATED_SOURCES: generated source files
 # These lists must be mutually exclusive.
 foreach(sfile ${NVIM_SOURCES}
-              "${CMAKE_CURRENT_LIST_DIR}/regexp_bt.c"
-              "${CMAKE_CURRENT_LIST_DIR}/regexp_nfa.c"
               ${GENERATED_API_DISPATCH}
               "${GENERATED_UI_EVENTS_CALL}"
               "${GENERATED_UI_EVENTS_REMOTE}"
diff --git a/src/nvim/regexp.c b/src/nvim/regexp.c
index 568f399664..cbe2aababa 100644
--- a/src/nvim/regexp.c
+++ b/src/nvim/regexp.c
@@ -11,6 +11,7 @@
 
 #include <assert.h>
 #include <inttypes.h>
+#include <limits.h>
 #include <stdbool.h>
 #include <string.h>
 #include <sys/types.h>
@@ -35,12 +36,142 @@
 #include "nvim/os/input.h"
 #include "nvim/plines.h"
 #include "nvim/pos.h"
+#include "nvim/profile.h"
 #include "nvim/regexp.h"
 #include "nvim/regexp_defs.h"
 #include "nvim/strings.h"
 #include "nvim/types.h"
 #include "nvim/vim.h"
 
+// Structure used to save the current input state, when it needs to be
+// restored after trying a match.  Used by reg_save() and reg_restore().
+// Also stores the length of "backpos".
+typedef struct {
+  union {
+    uint8_t *ptr;       // rex.input pointer, for single-line regexp
+    lpos_T pos;        // rex.input pos, for multi-line regexp
+  } rs_u;
+  int rs_len;
+} regsave_T;
+
+// struct to save start/end pointer/position in for \(\)
+typedef struct {
+  union {
+    uint8_t *ptr;
+    lpos_T pos;
+  } se_u;
+} save_se_T;
+
+// Values for rs_state in regitem_T.
+typedef enum regstate_E {
+  RS_NOPEN = 0,         // NOPEN and NCLOSE
+  RS_MOPEN,             // MOPEN + [0-9]
+  RS_MCLOSE,            // MCLOSE + [0-9]
+  RS_ZOPEN,             // ZOPEN + [0-9]
+  RS_ZCLOSE,            // ZCLOSE + [0-9]
+  RS_BRANCH,            // BRANCH
+  RS_BRCPLX_MORE,       // BRACE_COMPLEX and trying one more match
+  RS_BRCPLX_LONG,       // BRACE_COMPLEX and trying longest match
+  RS_BRCPLX_SHORT,      // BRACE_COMPLEX and trying shortest match
+  RS_NOMATCH,           // NOMATCH
+  RS_BEHIND1,           // BEHIND / NOBEHIND matching rest
+  RS_BEHIND2,           // BEHIND / NOBEHIND matching behind part
+  RS_STAR_LONG,         // STAR/PLUS/BRACE_SIMPLE longest match
+  RS_STAR_SHORT,  // STAR/PLUS/BRACE_SIMPLE shortest match
+} regstate_T;
+
+// When there are alternatives a regstate_T is put on the regstack to remember
+// what we are doing.
+// Before it may be another type of item, depending on rs_state, to remember
+// more things.
+typedef struct regitem_S {
+  regstate_T rs_state;         // what we are doing, one of RS_ above
+  int16_t rs_no;            // submatch nr or BEHIND/NOBEHIND
+  uint8_t *rs_scan;         // current node in program
+  union {
+    save_se_T sesave;
+    regsave_T regsave;
+  } rs_un;                      // room for saving rex.input
+} regitem_T;
+
+// used for BEHIND and NOBEHIND matching
+typedef struct regbehind_S {
+  regsave_T save_after;
+  regsave_T save_behind;
+  int save_need_clear_subexpr;
+  save_se_T save_start[NSUBEXP];
+  save_se_T save_end[NSUBEXP];
+} regbehind_T;
+
+// Since the out pointers in the list are always
+// uninitialized, we use the pointers themselves
+// as storage for the Ptrlists.
+typedef union Ptrlist Ptrlist;
+union Ptrlist {
+  Ptrlist *next;
+  nfa_state_T *s;
+};
+
+struct Frag {
+  nfa_state_T *start;
+  Ptrlist *out;
+};
+typedef struct Frag Frag_T;
+
+typedef struct {
+  int in_use;       ///< number of subexpr with useful info
+
+  // When REG_MULTI is true list.multi is used, otherwise list.line.
+  union {
+    struct multipos {
+      linenr_T start_lnum;
+      linenr_T end_lnum;
+      colnr_T start_col;
+      colnr_T end_col;
+    } multi[NSUBEXP];
+    struct linepos {
+      uint8_t *start;
+      uint8_t *end;
+    } line[NSUBEXP];
+  } list;
+  colnr_T orig_start_col;  // list.multi[0].start_col without \zs
+} regsub_T;
+
+typedef struct {
+  regsub_T norm;      // \( .. \) matches
+  regsub_T synt;      // \z( .. \) matches
+} regsubs_T;
+
+// nfa_pim_T stores a Postponed Invisible Match.
+typedef struct nfa_pim_S nfa_pim_T;
+struct nfa_pim_S {
+  int result;                   // NFA_PIM_*, see below
+  nfa_state_T *state;           // the invisible match start state
+  regsubs_T subs;               // submatch info, only party used
+  union {
+    lpos_T pos;
+    uint8_t *ptr;
+  } end;                        // where the match must end
+};
+
+// nfa_thread_T contains execution information of a NFA state
+typedef struct {
+  nfa_state_T *state;
+  int count;
+  nfa_pim_T pim;                // if pim.result != NFA_PIM_UNUSED: postponed
+                                // invisible match
+  regsubs_T subs;               // submatch info, only party used
+} nfa_thread_T;
+
+// nfa_list_T contains the alternative NFA execution states.
+typedef struct {
+  nfa_thread_T *t;           ///< allocated array of states
+  int n;                        ///< nr of states currently in "t"
+  int len;                      ///< max nr of states in "t"
+  int id;                       ///< ID of the list
+  int has_pim;                  ///< true when any state has a PIM
+} nfa_list_T;
+
 #ifdef REGEXP_DEBUG
 // show/save debugging data when BT engine is used
 # define BT_REGEXP_DUMP
@@ -2264,12 +2395,13150 @@ static void init_regexec_multi(regmmatch_T *rmp, win_T *win, buf_T *buf, linenr_
   rex.reg_maxcol = rmp->rmm_maxcol;
 }
 
-// XXX Do not allow headers generator to catch definitions from regexp_nfa.c
-#ifndef DO_NOT_DEFINE_EMPTY_ATTRIBUTES
-# include "nvim/regexp_bt.c"
-# include "nvim/regexp_nfa.c"
+// regexp_bt.c {{{1
+
+// Backtracking regular expression implementation.
+//
+// NOTICE:
+//
+// This is NOT the original regular expression code as written by Henry
+// Spencer.  This code has been modified specifically for use with the VIM
+// editor, and should not be used separately from Vim.  If you want a good
+// regular expression library, get the original code.  The copyright notice
+// that follows is from the original.
+//
+// END NOTICE
+//
+//      Copyright (c) 1986 by University of Toronto.
+//      Written by Henry Spencer.  Not derived from licensed software.
+//
+//      Permission is granted to anyone to use this software for any
+//      purpose on any computer system, and to redistribute it freely,
+//      subject to the following restrictions:
+//
+//      1. The author is not responsible for the consequences of use of
+//              this software, no matter how awful, even if they arise
+//              from defects in it.
+//
+//      2. The origin of this software must not be misrepresented, either
+//              by explicit claim or by omission.
+//
+//      3. Altered versions must be plainly marked as such, and must not
+//              be misrepresented as being the original software.
+//
+// Beware that some of this code is subtly aware of the way operator
+// precedence is structured in regular expressions.  Serious changes in
+// regular-expression syntax might require a total rethink.
+//
+// Changes have been made by Tony Andrews, Olaf 'Rhialto' Seibert, Robert
+// Webb, Ciaran McCreesh and Bram Moolenaar.
+// Named character class support added by Walter Briscoe (1998 Jul 01)
+
+// The "internal use only" fields in regexp_defs.h are present to pass info from
+// compile to execute that permits the execute phase to run lots faster on
+// simple cases.  They are:
+//
+// regstart     char that must begin a match; NUL if none obvious; Can be a
+//              multi-byte character.
+// reganch      is the match anchored (at beginning-of-line only)?
+// regmust      string (pointer into program) that match must include, or NULL
+// regmlen      length of regmust string
+// regflags     RF_ values or'ed together
+//
+// Regstart and reganch permit very fast decisions on suitable starting points
+// for a match, cutting down the work a lot.  Regmust permits fast rejection
+// of lines that cannot possibly match.  The regmust tests are costly enough
+// that vim_regcomp() supplies a regmust only if the r.e. contains something
+// potentially expensive (at present, the only such thing detected is * or +
+// at the start of the r.e., which can involve a lot of backup).  Regmlen is
+// supplied because the test in vim_regexec() needs it and vim_regcomp() is
+// computing it anyway.
+
+// Structure for regexp "program".  This is essentially a linear encoding
+// of a nondeterministic finite-state machine (aka syntax charts or
+// "railroad normal form" in parsing technology).  Each node is an opcode
+// plus a "next" pointer, possibly plus an operand.  "Next" pointers of
+// all nodes except BRANCH and BRACES_COMPLEX implement concatenation; a "next"
+// pointer with a BRANCH on both ends of it is connecting two alternatives.
+// (Here we have one of the subtle syntax dependencies: an individual BRANCH
+// (as opposed to a collection of them) is never concatenated with anything
+// because of operator precedence).  The "next" pointer of a BRACES_COMPLEX
+// node points to the node after the stuff to be repeated.
+// The operand of some types of node is a literal string; for others, it is a
+// node leading into a sub-FSM.  In particular, the operand of a BRANCH node
+// is the first node of the branch.
+// (NB this is *not* a tree structure: the tail of the branch connects to the
+// thing following the set of BRANCHes.)
+//
+// pattern      is coded like:
+//
+//                        +-----------------+
+//                        |                 V
+// <aa>\|<bb>   BRANCH <aa> BRANCH <bb> --> END
+//                   |      ^    |          ^
+//                   +------+    +----------+
+//
+//
+//                     +------------------+
+//                     V                  |
+// <aa>*        BRANCH BRANCH <aa> --> BACK BRANCH --> NOTHING --> END
+//                   |      |               ^                      ^
+//                   |      +---------------+                      |
+//                   +---------------------------------------------+
+//
+//
+//                     +----------------------+
+//                     V                      |
+// <aa>\+       BRANCH <aa> --> BRANCH --> BACK  BRANCH --> NOTHING --> END
+//                   |               |           ^                      ^
+//                   |               +-----------+                      |
+//                   +--------------------------------------------------+
+//
+//
+//                                      +-------------------------+
+//                                      V                         |
+// <aa>\{}      BRANCH BRACE_LIMITS --> BRACE_COMPLEX <aa> --> BACK  END
+//                   |                              |                ^
+//                   |                              +----------------+
+//                   +-----------------------------------------------+
+//
+//
+// <aa>\@!<bb>  BRANCH NOMATCH <aa> --> END  <bb> --> END
+//                   |       |                ^       ^
+//                   |       +----------------+       |
+//                   +--------------------------------+
+//
+//                                                    +---------+
+//                                                    |         V
+// \z[abc]      BRANCH BRANCH  a  BRANCH  b  BRANCH  c  BRANCH  NOTHING --> END
+//                   |      |          |          |     ^                   ^
+//                   |      |          |          +-----+                   |
+//                   |      |          +----------------+                   |
+//                   |      +---------------------------+                   |
+//                   +------------------------------------------------------+
+//
+// They all start with a BRANCH for "\|" alternatives, even when there is only
+// one alternative.
+
+// The opcodes are:
+
+// definition   number             opnd?    meaning
+#define END             0       //      End of program or NOMATCH operand.
+#define BOL             1       //      Match "" at beginning of line.
+#define EOL             2       //      Match "" at end of line.
+#define BRANCH          3       // node Match this alternative, or the
+                                //      next...
+#define BACK            4       //      Match "", "next" ptr points backward.
+#define EXACTLY         5       // str  Match this string.
+#define NOTHING         6       //      Match empty string.
+#define STAR            7       // node Match this (simple) thing 0 or more
+                                //      times.
+#define PLUS            8       // node Match this (simple) thing 1 or more
+                                //      times.
+#define MATCH           9       // node match the operand zero-width
+#define NOMATCH         10      // node check for no match with operand
+#define BEHIND          11      // node look behind for a match with operand
+#define NOBEHIND        12      // node look behind for no match with operand
+#define SUBPAT          13      // node match the operand here
+#define BRACE_SIMPLE    14      // node Match this (simple) thing between m and
+                                //      n times (\{m,n\}).
+#define BOW             15      //      Match "" after [^a-zA-Z0-9_]
+#define EOW             16      //      Match "" at    [^a-zA-Z0-9_]
+#define BRACE_LIMITS    17      // nr nr  define the min & max for BRACE_SIMPLE
+                                //      and BRACE_COMPLEX.
+#define NEWL            18      //      Match line-break
+#define BHPOS           19      //      End position for BEHIND or NOBEHIND
+
+// character classes: 20-48 normal, 50-78 include a line-break
+#define ADD_NL          30
+#define FIRST_NL        ANY + ADD_NL
+#define ANY             20      //      Match any one character.
+#define ANYOF           21      // str  Match any character in this string.
+#define ANYBUT          22      // str  Match any character not in this
+                                //      string.
+#define IDENT           23      //      Match identifier char
+#define SIDENT          24      //      Match identifier char but no digit
+#define KWORD           25      //      Match keyword char
+#define SKWORD          26      //      Match word char but no digit
+#define FNAME           27      //      Match file name char
+#define SFNAME          28      //      Match file name char but no digit
+#define PRINT           29      //      Match printable char
+#define SPRINT          30      //      Match printable char but no digit
+#define WHITE           31      //      Match whitespace char
+#define NWHITE          32      //      Match non-whitespace char
+#define DIGIT           33      //      Match digit char
+#define NDIGIT          34      //      Match non-digit char
+#define HEX             35      //      Match hex char
+#define NHEX            36      //      Match non-hex char
+#define OCTAL           37      //      Match octal char
+#define NOCTAL          38      //      Match non-octal char
+#define WORD            39      //      Match word char
+#define NWORD           40      //      Match non-word char
+#define HEAD            41      //      Match head char
+#define NHEAD           42      //      Match non-head char
+#define ALPHA           43      //      Match alpha char
+#define NALPHA          44      //      Match non-alpha char
+#define LOWER           45      //      Match lowercase char
+#define NLOWER          46      //      Match non-lowercase char
+#define UPPER           47      //      Match uppercase char
+#define NUPPER          48      //      Match non-uppercase char
+#define LAST_NL         NUPPER + ADD_NL
+// -V:WITH_NL:560
+#define WITH_NL(op)     ((op) >= FIRST_NL && (op) <= LAST_NL)
+
+#define MOPEN           80   // -89 Mark this point in input as start of
+                             //     \( … \) subexpr.  MOPEN + 0 marks start of
+                             //     match.
+#define MCLOSE          90   // -99 Analogous to MOPEN.  MCLOSE + 0 marks
+                             //     end of match.
+#define BACKREF         100  // -109 node Match same string again \1-\9.
+
+#define ZOPEN          110  // -119 Mark this point in input as start of
+                            //  \z( … \) subexpr.
+#define ZCLOSE         120  // -129 Analogous to ZOPEN.
+#define ZREF           130  // -139 node Match external submatch \z1-\z9
+
+#define BRACE_COMPLEX   140  // -149 node Match nodes between m & n times
+
+#define NOPEN           150     // Mark this point in input as start of
+                                // \%( subexpr.
+#define NCLOSE          151     // Analogous to NOPEN.
+
+#define MULTIBYTECODE   200     // mbc  Match one multi-byte character
+#define RE_BOF          201     //      Match "" at beginning of file.
+#define RE_EOF          202     //      Match "" at end of file.
+#define CURSOR          203     //      Match location of cursor.
+
+#define RE_LNUM         204     // nr cmp  Match line number
+#define RE_COL          205     // nr cmp  Match column number
+#define RE_VCOL         206     // nr cmp  Match virtual column number
+
+#define RE_MARK         207     // mark cmp  Match mark position
+#define RE_VISUAL       208     //      Match Visual area
+#define RE_COMPOSING    209     // any composing characters
+
+// Flags to be passed up and down.
+#define HASWIDTH        0x1     // Known never to match null string.
+#define SIMPLE          0x2     // Simple enough to be STAR/PLUS operand.
+#define SPSTART         0x4     // Starts with * or +.
+#define HASNL           0x8     // Contains some \n.
+#define HASLOOKBH       0x10    // Contains "\@<=" or "\@<!".
+#define WORST           0       // Worst case.
+
+static int prevchr_len;         ///< byte length of previous char
+static int num_complex_braces;  ///< Complex \{...} count
+static uint8_t *regcode;         ///< Code-emit pointer, or JUST_CALC_SIZE
+static long regsize;            ///< Code size.
+static int reg_toolong;         ///< true when offset out of range
+static uint8_t had_endbrace[NSUBEXP];  ///< flags, true if end of () found
+static long brace_min[10];        ///< Minimums for complex brace repeats
+static long brace_max[10];        ///< Maximums for complex brace repeats
+static int brace_count[10];       ///< Current counts for complex brace repeats
+static int one_exactly = false;   ///< only do one char for EXACTLY
+
+// When making changes to classchars also change nfa_classcodes.
+static uint8_t *classchars = (uint8_t *)".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
+};
+
+// When regcode is set to this value, code is not emitted and size is computed
+// instead.
+#define JUST_CALC_SIZE  ((uint8_t *)-1)
+
+// used for STAR, PLUS and BRACE_SIMPLE matching
+typedef struct regstar_S {
+  int nextb;            // next byte
+  int nextb_ic;         // next byte reverse case
+  long count;
+  long minval;
+  long maxval;
+} regstar_T;
+
+// used to store input position when a BACK was encountered, so that we now if
+// we made any progress since the last time.
+typedef struct backpos_S {
+  uint8_t *bp_scan;         // "scan" where BACK was encountered
+  regsave_T bp_pos;           // last input position
+} backpos_T;
+
+// "regstack" and "backpos" are used by regmatch().  They are kept over calls
+// to avoid invoking malloc() and free() often.
+// "regstack" is a stack with regitem_T items, sometimes preceded by regstar_T
+// or regbehind_T.
+// "backpos_T" is a table with backpos_T for BACK
+static garray_T regstack = GA_EMPTY_INIT_VALUE;
+static garray_T backpos = GA_EMPTY_INIT_VALUE;
+
+static regsave_T behind_pos;
+
+// Both for regstack and backpos tables we use the following strategy of
+// allocation (to reduce malloc/free calls):
+// - Initial size is fairly small.
+// - When needed, the tables are grown bigger (8 times at first, double after
+//   that).
+// - After executing the match we free the memory only if the array has grown.
+//   Thus the memory is kept allocated when it's at the initial size.
+// This makes it fast while not keeping a lot of memory allocated.
+// A three times speed increase was observed when using many simple patterns.
+#define REGSTACK_INITIAL        2048
+#define BACKPOS_INITIAL         64
+
+// Opcode notes:
+//
+// BRANCH       The set of branches constituting a single choice are hooked
+//              together with their "next" pointers, since precedence prevents
+//              anything being concatenated to any individual branch.  The
+//              "next" pointer of the last BRANCH in a choice points to the
+//              thing following the whole choice.  This is also where the
+//              final "next" pointer of each individual branch points; each
+//              branch starts with the operand node of a BRANCH node.
+//
+// BACK         Normal "next" pointers all implicitly point forward; BACK
+//              exists to make loop structures possible.
+//
+// STAR,PLUS    '=', and complex '*' and '+', are implemented as circular
+//              BRANCH structures using BACK.  Simple cases (one character
+//              per match) are implemented with STAR and PLUS for speed
+//              and to minimize recursive plunges.
+//
+// BRACE_LIMITS This is always followed by a BRACE_SIMPLE or BRACE_COMPLEX
+//              node, and defines the min and max limits to be used for that
+//              node.
+//
+// MOPEN,MCLOSE ...are numbered at compile time.
+// ZOPEN,ZCLOSE ...ditto
+///
+//
+//
+// A node is one char of opcode followed by two chars of "next" pointer.
+// "Next" pointers are stored as two 8-bit bytes, high order first.  The
+// value is a positive offset from the opcode of the node containing it.
+// An operand, if any, simply follows the node.  (Note that much of the
+// code generation knows about this implicit relationship.)
+//
+// Using two bytes for the "next" pointer is vast overkill for most things,
+// but allows patterns to get big without disasters.
+#define OP(p)           ((int)(*(p)))
+#define NEXT(p)         (((*((p) + 1) & 0377) << 8) + (*((p) + 2) & 0377))
+#define OPERAND(p)      ((p) + 3)
+// Obtain an operand that was stored as four bytes, MSB first.
+#define OPERAND_MIN(p)  (((long)(p)[3] << 24) + ((long)(p)[4] << 16) \
+                         + ((long)(p)[5] << 8) + (long)(p)[6])
+// Obtain a second operand stored as four bytes.
+#define OPERAND_MAX(p)  OPERAND_MIN((p) + 4)
+// Obtain a second single-byte operand stored after a four bytes operand.
+#define OPERAND_CMP(p)  (p)[7]
+
+static uint8_t *reg(int paren, int *flagp);
+
+#ifdef BT_REGEXP_DUMP
+static void     regdump(uint8_t *, bt_regprog_T *);
+#endif
+
+#ifdef REGEXP_DEBUG
+static uint8_t *regprop(uint8_t *);
+
+static int regnarrate = 0;
+#endif
+
+// Setup to parse the regexp.  Used once to get the length and once to do it.
+static void regcomp_start(uint8_t *expr, int re_flags)                        // see vim_regcomp()
+{
+  initchr((char *)expr);
+  if (re_flags & RE_MAGIC) {
+    reg_magic = MAGIC_ON;
+  } else {
+    reg_magic = MAGIC_OFF;
+  }
+  reg_string = (re_flags & RE_STRING);
+  reg_strict = (re_flags & RE_STRICT);
+  get_cpo_flags();
+
+  num_complex_braces = 0;
+  regnpar = 1;
+  CLEAR_FIELD(had_endbrace);
+  regnzpar = 1;
+  re_has_z = 0;
+  regsize = 0L;
+  reg_toolong = false;
+  regflags = 0;
+  had_eol = false;
+}
+
+// Return true if MULTIBYTECODE should be used instead of EXACTLY for
+// character "c".
+static bool use_multibytecode(int c)
+{
+  return utf_char2len(c) > 1
+         && (re_multi_type(peekchr()) != NOT_MULTI
+             || utf_iscomposing(c));
+}
+
+// Emit (if appropriate) a byte of code
+static void regc(int b)
+{
+  if (regcode == JUST_CALC_SIZE) {
+    regsize++;
+  } else {
+    *regcode++ = (uint8_t)b;
+  }
+}
+
+// Emit (if appropriate) a multi-byte character of code
+static void regmbc(int c)
+{
+  if (regcode == JUST_CALC_SIZE) {
+    regsize += utf_char2len(c);
+  } else {
+    regcode += utf_char2bytes(c, (char *)regcode);
+  }
+}
+
+// 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(int c)
+{
+  {
+    switch (c) {
+    // Do not use '\300' style, it results in a negative number.
+    case 'A':
+    case 0xc0:
+    case 0xc1:
+    case 0xc2:
+    case 0xc3:
+    case 0xc4:
+    case 0xc5:
+    case 0x100:
+    case 0x102:
+    case 0x104:
+    case 0x1cd:
+    case 0x1de:
+    case 0x1e0:
+    case 0x1fa:
+    case 0x202:
+    case 0x226:
+    case 0x23a:
+    case 0x1e00:
+    case 0x1ea0:
+    case 0x1ea2:
+    case 0x1ea4:
+    case 0x1ea6:
+    case 0x1ea8:
+    case 0x1eaa:
+    case 0x1eac:
+    case 0x1eae:
+    case 0x1eb0:
+    case 0x1eb2:
+    case 0x1eb4:
+    case 0x1eb6:
+      regmbc('A'); regmbc(0xc0); regmbc(0xc1); regmbc(0xc2);
+      regmbc(0xc3); regmbc(0xc4); regmbc(0xc5);
+      regmbc(0x100); regmbc(0x102); regmbc(0x104);
+      regmbc(0x1cd); regmbc(0x1de); regmbc(0x1e0);
+      regmbc(0x1fa); regmbc(0x202); regmbc(0x226);
+      regmbc(0x23a); regmbc(0x1e00); regmbc(0x1ea0);
+      regmbc(0x1ea2); regmbc(0x1ea4); regmbc(0x1ea6);
+      regmbc(0x1ea8); regmbc(0x1eaa); regmbc(0x1eac);
+      regmbc(0x1eae); regmbc(0x1eb0); regmbc(0x1eb2);
+      regmbc(0x1eb4); regmbc(0x1eb6);
+      return;
+    case 'B':
+    case 0x181:
+    case 0x243:
+    case 0x1e02:
+    case 0x1e04:
+    case 0x1e06:
+      regmbc('B');
+      regmbc(0x181); regmbc(0x243); regmbc(0x1e02);
+      regmbc(0x1e04); regmbc(0x1e06);
+      return;
+    case 'C':
+    case 0xc7:
+    case 0x106:
+    case 0x108:
+    case 0x10a:
+    case 0x10c:
+    case 0x187:
+    case 0x23b:
+    case 0x1e08:
+    case 0xa792:
+      regmbc('C'); regmbc(0xc7);
+      regmbc(0x106); regmbc(0x108); regmbc(0x10a);
+      regmbc(0x10c); regmbc(0x187); regmbc(0x23b);
+      regmbc(0x1e08); regmbc(0xa792);
+      return;
+    case 'D':
+    case 0x10e:
+    case 0x110:
+    case 0x18a:
+    case 0x1e0a:
+    case 0x1e0c:
+    case 0x1e0e:
+    case 0x1e10:
+    case 0x1e12:
+      regmbc('D'); regmbc(0x10e); regmbc(0x110);
+      regmbc(0x18a); regmbc(0x1e0a); regmbc(0x1e0c);
+      regmbc(0x1e0e); regmbc(0x1e10); regmbc(0x1e12);
+      return;
+    case 'E':
+    case 0xc8:
+    case 0xc9:
+    case 0xca:
+    case 0xcb:
+    case 0x112:
+    case 0x114:
+    case 0x116:
+    case 0x118:
+    case 0x11a:
+    case 0x204:
+    case 0x206:
+    case 0x228:
+    case 0x246:
+    case 0x1e14:
+    case 0x1e16:
+    case 0x1e18:
+    case 0x1e1a:
+    case 0x1e1c:
+    case 0x1eb8:
+    case 0x1eba:
+    case 0x1ebc:
+    case 0x1ebe:
+    case 0x1ec0:
+    case 0x1ec2:
+    case 0x1ec4:
+    case 0x1ec6:
+      regmbc('E'); regmbc(0xc8); regmbc(0xc9);
+      regmbc(0xca); regmbc(0xcb); regmbc(0x112);
+      regmbc(0x114); regmbc(0x116); regmbc(0x118);
+      regmbc(0x11a); regmbc(0x204); regmbc(0x206);
+      regmbc(0x228); regmbc(0x246); regmbc(0x1e14);
+      regmbc(0x1e16); regmbc(0x1e18); regmbc(0x1e1a);
+      regmbc(0x1e1c); regmbc(0x1eb8); regmbc(0x1eba);
+      regmbc(0x1ebc); regmbc(0x1ebe); regmbc(0x1ec0);
+      regmbc(0x1ec2); regmbc(0x1ec4); regmbc(0x1ec6);
+      return;
+    case 'F':
+    case 0x191:
+    case 0x1e1e:
+    case 0xa798:
+      regmbc('F'); regmbc(0x191); regmbc(0x1e1e);
+      regmbc(0xa798);
+      return;
+    case 'G':
+    case 0x11c:
+    case 0x11e:
+    case 0x120:
+    case 0x122:
+    case 0x193:
+    case 0x1e4:
+    case 0x1e6:
+    case 0x1f4:
+    case 0x1e20:
+    case 0xa7a0:
+      regmbc('G'); regmbc(0x11c); regmbc(0x11e);
+      regmbc(0x120); regmbc(0x122); regmbc(0x193);
+      regmbc(0x1e4); regmbc(0x1e6); regmbc(0x1f4);
+      regmbc(0x1e20); regmbc(0xa7a0);
+      return;
+    case 'H':
+    case 0x124:
+    case 0x126:
+    case 0x21e:
+    case 0x1e22:
+    case 0x1e24:
+    case 0x1e26:
+    case 0x1e28:
+    case 0x1e2a:
+    case 0x2c67:
+      regmbc('H'); regmbc(0x124); regmbc(0x126);
+      regmbc(0x21e); regmbc(0x1e22); regmbc(0x1e24);
+      regmbc(0x1e26); regmbc(0x1e28); regmbc(0x1e2a);
+      regmbc(0x2c67);
+      return;
+    case 'I':
+    case 0xcc:
+    case 0xcd:
+    case 0xce:
+    case 0xcf:
+    case 0x128:
+    case 0x12a:
+    case 0x12c:
+    case 0x12e:
+    case 0x130:
+    case 0x197:
+    case 0x1cf:
+    case 0x208:
+    case 0x20a:
+    case 0x1e2c:
+    case 0x1e2e:
+    case 0x1ec8:
+    case 0x1eca:
+      regmbc('I'); regmbc(0xcc); regmbc(0xcd);
+      regmbc(0xce); regmbc(0xcf); regmbc(0x128);
+      regmbc(0x12a); regmbc(0x12c); regmbc(0x12e);
+      regmbc(0x130); regmbc(0x197); regmbc(0x1cf);
+      regmbc(0x208); regmbc(0x20a); regmbc(0x1e2c);
+      regmbc(0x1e2e); regmbc(0x1ec8); regmbc(0x1eca);
+      return;
+    case 'J':
+    case 0x134:
+    case 0x248:
+      regmbc('J'); regmbc(0x134); regmbc(0x248);
+      return;
+    case 'K':
+    case 0x136:
+    case 0x198:
+    case 0x1e8:
+    case 0x1e30:
+    case 0x1e32:
+    case 0x1e34:
+    case 0x2c69:
+    case 0xa740:
+      regmbc('K'); regmbc(0x136); regmbc(0x198);
+      regmbc(0x1e8); regmbc(0x1e30); regmbc(0x1e32);
+      regmbc(0x1e34); regmbc(0x2c69); regmbc(0xa740);
+      return;
+    case 'L':
+    case 0x139:
+    case 0x13b:
+    case 0x13d:
+    case 0x13f:
+    case 0x141:
+    case 0x23d:
+    case 0x1e36:
+    case 0x1e38:
+    case 0x1e3a:
+    case 0x1e3c:
+    case 0x2c60:
+      regmbc('L'); regmbc(0x139); regmbc(0x13b);
+      regmbc(0x13d); regmbc(0x13f); regmbc(0x141);
+      regmbc(0x23d); regmbc(0x1e36); regmbc(0x1e38);
+      regmbc(0x1e3a); regmbc(0x1e3c); regmbc(0x2c60);
+      return;
+    case 'M':
+    case 0x1e3e:
+    case 0x1e40:
+    case 0x1e42:
+      regmbc('M'); regmbc(0x1e3e); regmbc(0x1e40);
+      regmbc(0x1e42);
+      return;
+    case 'N':
+    case 0xd1:
+    case 0x143:
+    case 0x145:
+    case 0x147:
+    case 0x1f8:
+    case 0x1e44:
+    case 0x1e46:
+    case 0x1e48:
+    case 0x1e4a:
+    case 0xa7a4:
+      regmbc('N'); regmbc(0xd1);
+      regmbc(0x143); regmbc(0x145); regmbc(0x147);
+      regmbc(0x1f8); regmbc(0x1e44); regmbc(0x1e46);
+      regmbc(0x1e48); regmbc(0x1e4a); regmbc(0xa7a4);
+      return;
+    case 'O':
+    case 0xd2:
+    case 0xd3:
+    case 0xd4:
+    case 0xd5:
+    case 0xd6:
+    case 0xd8:
+    case 0x14c:
+    case 0x14e:
+    case 0x150:
+    case 0x19f:
+    case 0x1a0:
+    case 0x1d1:
+    case 0x1ea:
+    case 0x1ec:
+    case 0x1fe:
+    case 0x20c:
+    case 0x20e:
+    case 0x22a:
+    case 0x22c:
+    case 0x22e:
+    case 0x230:
+    case 0x1e4c:
+    case 0x1e4e:
+    case 0x1e50:
+    case 0x1e52:
+    case 0x1ecc:
+    case 0x1ece:
+    case 0x1ed0:
+    case 0x1ed2:
+    case 0x1ed4:
+    case 0x1ed6:
+    case 0x1ed8:
+    case 0x1eda:
+    case 0x1edc:
+    case 0x1ede:
+    case 0x1ee0:
+    case 0x1ee2:
+      regmbc('O'); regmbc(0xd2); regmbc(0xd3); regmbc(0xd4);
+      regmbc(0xd5); regmbc(0xd6); regmbc(0xd8);
+      regmbc(0x14c); regmbc(0x14e); regmbc(0x150);
+      regmbc(0x19f); regmbc(0x1a0); regmbc(0x1d1);
+      regmbc(0x1ea); regmbc(0x1ec); regmbc(0x1fe);
+      regmbc(0x20c); regmbc(0x20e); regmbc(0x22a);
+      regmbc(0x22c); regmbc(0x22e); regmbc(0x230);
+      regmbc(0x1e4c); regmbc(0x1e4e); regmbc(0x1e50);
+      regmbc(0x1e52); regmbc(0x1ecc); regmbc(0x1ece);
+      regmbc(0x1ed0); regmbc(0x1ed2); regmbc(0x1ed4);
+      regmbc(0x1ed6); regmbc(0x1ed8); regmbc(0x1eda);
+      regmbc(0x1edc); regmbc(0x1ede); regmbc(0x1ee0);
+      regmbc(0x1ee2);
+      return;
+    case 'P':
+    case 0x1a4:
+    case 0x1e54:
+    case 0x1e56:
+    case 0x2c63:
+      regmbc('P'); regmbc(0x1a4); regmbc(0x1e54);
+      regmbc(0x1e56); regmbc(0x2c63);
+      return;
+    case 'Q':
+    case 0x24a:
+      regmbc('Q'); regmbc(0x24a);
+      return;
+    case 'R':
+    case 0x154:
+    case 0x156:
+    case 0x158:
+    case 0x210:
+    case 0x212:
+    case 0x24c:
+    case 0x1e58:
+    case 0x1e5a:
+    case 0x1e5c:
+    case 0x1e5e:
+    case 0x2c64:
+    case 0xa7a6:
+      regmbc('R'); regmbc(0x154); regmbc(0x156);
+      regmbc(0x210); regmbc(0x212); regmbc(0x158);
+      regmbc(0x24c); regmbc(0x1e58); regmbc(0x1e5a);
+      regmbc(0x1e5c); regmbc(0x1e5e); regmbc(0x2c64);
+      regmbc(0xa7a6);
+      return;
+    case 'S':
+    case 0x15a:
+    case 0x15c:
+    case 0x15e:
+    case 0x160:
+    case 0x218:
+    case 0x1e60:
+    case 0x1e62:
+    case 0x1e64:
+    case 0x1e66:
+    case 0x1e68:
+    case 0x2c7e:
+    case 0xa7a8:
+      regmbc('S'); regmbc(0x15a); regmbc(0x15c);
+      regmbc(0x15e); regmbc(0x160); regmbc(0x218);
+      regmbc(0x1e60); regmbc(0x1e62); regmbc(0x1e64);
+      regmbc(0x1e66); regmbc(0x1e68); regmbc(0x2c7e);
+      regmbc(0xa7a8);
+      return;
+    case 'T':
+    case 0x162:
+    case 0x164:
+    case 0x166:
+    case 0x1ac:
+    case 0x1ae:
+    case 0x21a:
+    case 0x23e:
+    case 0x1e6a:
+    case 0x1e6c:
+    case 0x1e6e:
+    case 0x1e70:
+      regmbc('T'); regmbc(0x162); regmbc(0x164);
+      regmbc(0x166); regmbc(0x1ac); regmbc(0x23e);
+      regmbc(0x1ae); regmbc(0x21a); regmbc(0x1e6a);
+      regmbc(0x1e6c); regmbc(0x1e6e); regmbc(0x1e70);
+      return;
+    case 'U':
+    case 0xd9:
+    case 0xda:
+    case 0xdb:
+    case 0xdc:
+    case 0x168:
+    case 0x16a:
+    case 0x16c:
+    case 0x16e