4 files changed, 24 insertions, 13 deletions
diff --git a/src/nvim/regexp.c b/src/nvim/regexp.c
index 3e287e590b..dddd347822 100644
--- a/src/nvim/regexp.c
+++ b/src/nvim/regexp.c
@@ -6984,10 +6984,12 @@ regprog_T *vim_regcomp(char_u *expr_arg, int re_flags)
   /*
    * First try the NFA engine, unless backtracking was requested.
    */
-  if (regexp_engine != BACKTRACKING_ENGINE)
-    prog = nfa_regengine.regcomp(expr, re_flags);
-  else
+  if (regexp_engine != BACKTRACKING_ENGINE) {
+    prog = nfa_regengine.regcomp(expr,
+        re_flags + (regexp_engine == AUTOMATIC_ENGINE ? RE_AUTO : 0));
+  } else {
     prog = bt_regengine.regcomp(expr, re_flags);
+  }
 
   // Check for error compiling regexp with initial engine.
   if (prog == NULL) {
@@ -7003,15 +7005,13 @@ regprog_T *vim_regcomp(char_u *expr_arg, int re_flags)
             BT_REGEXP_DEBUG_LOG_NAME);
     }
 #endif
-    // If the NFA engine failed, try the backtracking engine.
-    // Disabled for now, both engines fail on the same patterns.
-    // Re-enable when regcomp() fails when the pattern would work better
-    // with the other engine.
-    //
-    // if (regexp_engine == AUTOMATIC_ENGINE) {
-    //   prog = bt_regengine.regcomp(expr, re_flags);
-    //   regexp_engine = BACKTRACKING_ENGINE;
-    // }
+    // If the NFA engine failed, try the backtracking engine. The NFA engine
+    // also fails for patterns that it can't handle well but are still valid
+    // patterns, thus a retry should work.
+    if (regexp_engine == AUTOMATIC_ENGINE) {
+      regexp_engine = BACKTRACKING_ENGINE;
+      prog = bt_regengine.regcomp(expr, re_flags);
+    }
   }
 
   if (prog != NULL) {
diff --git a/src/nvim/regexp.h b/src/nvim/regexp.h
index 1af01fe411..37513d8c27 100644
--- a/src/nvim/regexp.h
+++ b/src/nvim/regexp.h
@@ -5,6 +5,7 @@
 #define RE_MAGIC        1       /* 'magic' option */
 #define RE_STRING       2       /* match in string instead of buffer text */
 #define RE_STRICT       4       /* don't allow [abc] without ] */
+#define RE_AUTO         8       /* automatic engine selection */
 
 /* values for reg_do_extmatch */
 #define REX_SET        1       /* to allow \z\(...\), */
diff --git a/src/nvim/regexp_nfa.c b/src/nvim/regexp_nfa.c
index 4ef91814ac..d9dc09b623 100644
--- a/src/nvim/regexp_nfa.c
+++ b/src/nvim/regexp_nfa.c
@@ -315,6 +315,9 @@ typedef struct {
   int has_pim;                  /* TRUE when any state has a PIM */
 } nfa_list_T;
 
+/// re_flags passed to nfa_regcomp().
+static int nfa_re_flags;
+
 /* NFA regexp \ze operator encountered. */
 static int nfa_has_zend;
 
@@ -1894,6 +1897,12 @@ static int nfa_regpiece(void)
       return OK;
     }
 
+    // The engine is very inefficient (uses too many states) when the maximum is
+    // much larger than the minimum. Bail out if we can use the other engine.
+    if ((nfa_re_flags & RE_AUTO) && maxval > minval + 200) {
+      return FAIL;
+    }
+
     /* Ignore previous call to nfa_regatom() */
     post_ptr = post_start + my_post_start;
     /* Save parse state after the repeated atom and the \{} */
@@ -6287,6 +6296,7 @@ static regprog_T *nfa_regcomp(char_u *expr, int re_flags)
     return NULL;
 
   nfa_regengine.expr = expr;
+  nfa_re_flags = re_flags;
 
   init_class_tab();
 
diff --git a/src/nvim/version.c b/src/nvim/version.c
index 2ebc080eb8..d43108d29a 100644
--- a/src/nvim/version.c
+++ b/src/nvim/version.c
@@ -216,7 +216,7 @@ static int included_patches[] = {
   //596 NA
   595,
   594,
-  //593,
+  593,
   //592 NA
   //591 NA
   590,