The RegExp Engine: Irregexp, Backtracking and the Experimental Engine

TL;DR: A regexp in V8 is a tree of nodes (src/regexp/regexp-ast.h) that the compiler turns into a backtracking automaton — a machine with an explicit backtrack stack, not a DFA. The engine can run that automaton two ways: as bytecode in an interpreter, or as native code. Before either runs, a quick check filter can reject the subject without entering the engine at all. And when the backtracker exceeds 50 000 backtracks, V8 can bail out to a completely different engine — a breadth-first NFA simulation that runs in linear time.

Regular expressions are the one place in JavaScript where the language specifies a non-regular computation. Backreferences and lookaround make the match problem NP-hard in general, so no DFA exists, so every engine has to backtrack. Backtracking has a failure mode — exponential time on patterns like /(a+)+b/ against a string of as — and V8’s answer to that failure mode is one of the more interesting pieces of the codebase: a second, completely different engine that it can fall back to.

Four engines, one regex

Before anything else: a RegExp object in V8 is not one thing. The RegExpData it points at has a type tag, and there are three:

cpp
// src/builtins/builtins-regexp-gen.cc:820
    int32_t values[] = {
        static_cast<uint8_t>(RegExpData::Type::IRREGEXP),
        static_cast<uint8_t>(RegExpData::Type::ATOM),
        static_cast<uint8_t>(RegExpData::Type::EXPERIMENTAL),
    };
    Label* labels[] = {&next, &atom, &next};

ATOM — the pattern is a literal string with no metacharacters, so the “regexp” is a string search. V8 uses Boyer-Moore-ish scanning for this and never enters the regexp engine at all.
IRREGEXP — the real thing: a backtracking automaton, in bytecode or in native code.
EXPERIMENTAL — the breadth-first engine.

The choice of type happens once, at construction time, in RegExpImpl::Compile:

cpp
// src/regexp/regexp.cc:428
  if (v8_flags.enable_experimental_regexp_engine ||
      v8_flags.enable_experimental_regexp_engine_on_excessive_backtracks) {
    is_linear_executable = regexp::ExperimentalRegExp::CanBeHandled(
        parse_result.tree, original_source, flags, parse_result.capture_count);
  }

is_linear_executable is a property of the pattern: it means the breadth-first engine can handle it at all. Patterns with backreferences or unsupported lookaround cannot, and the flag is baked into the RegExpData:

cpp
// src/regexp/regexp.cc:476
  if (!has_been_compiled) {
    const bool can_be_zero_length = parse_result.tree->min_match() == 0;
    using Bits = IrRegExpData::Bits;
    const uint32_t bit_field =
        Bits::CanBeZeroLengthBit::encode(can_be_zero_length) |
        Bits::IsLinearExecutableBit::encode(is_linear_executable);
    regexp::RegExpImpl::IrregexpInitialize(
        isolate, re, original_source, escaped_source, flags,
        parse_result.capture_count, backtrack_limit, bit_field);
  }

The atom fast path is chosen with a genuinely cute heuristic. A pattern that is a single atom is only worth compiling as an atom if the string search would not be faster than the regexp engine, and the test is “does the pattern have few distinct characters?”:

cpp
// src/regexp/regexp.cc:198
// Identifies the sort of regexps where the regexp engine is faster
// than the code used for atom matches.
bool HasFewDifferentCharacters(DirectHandle<String> pattern) {
  uint32_t length =
      std::min(regexp::kMaxLookaheadForBoyerMoore, pattern->length());
  if (length <= regexp::kPatternTooShortForBoyerMoore) return false;
  const int kMod = 128;
  bool character_found[kMod];
  uint32_t different = 0;
  memset(&character_found[0], 0, sizeof(character_found));
  for (uint32_t i = 0; i < length; i++) {
    int ch = (pattern->Get(i) & (kMod - 1));
    if (!character_found[ch]) {
      character_found[ch] = true;
      different++;
      // We declare a regexp low-alphabet if it has at least 3 times as many
      // characters as it has different characters.
      if (different * 3 > length) return false;
    }
  }
  return true;
}

“Low alphabet” means the pattern has at most one third as many distinct characters as it has characters. A pattern like aaaaaaa... is low alphabet (Boyer-Moore will fly through it), and a pattern like abcdefghij... is not (the regexp engine with its first-character filter will beat a naive search). The & (kMod - 1) is a cheap approximation of “distinct characters” that only looks at the low 7 bits, which is good enough for a heuristic.

The parser: text to a tree

The regexp parser (src/regexp/regexp-parser.cc) is a template over the character type and over a parse mode:

cpp
// src/regexp/regexp-parser.cc:35
enum class ParseMode {
  kBuildAST,      // Full parsing including AST Building.
  kVerifySyntax,  // Verify Syntax only. No AST is created.
};

The kVerifySyntax mode exists for RegExp.prototype[Symbol.match]-style speculative parsing and for the embedder API that only wants to know whether a pattern is valid. It runs the same grammar with the AST construction stubbed out.

The AST is a tree of RegExpNode subclasses (Text, ClassRanges, Disjunction, Quantifier, Assertion, Capture, BackReference). Each node knows the minimum and maximum length it can match, which is the first thing the compiler uses:

cpp
// src/regexp/regexp-ast.h:245
  virtual int min_match() = 0;
  virtual int max_match() = 0;

Those bounds drive real optimisations. The most obvious one: if a pattern is anchored at the end but not at the start, and its maximum match length is short, the machine can start matching at length - max_length instead of at the beginning:

cpp
// src/regexp/regexp.cc:1470
  bool is_end_anchored =
      data->tree->IsCertainlyAnchoredAtEnd(Node::kRecursionBudget);
  bool is_start_anchored =
      data->tree->IsCertainlyAnchoredAtStart(Node::kRecursionBudget);
  int max_length = data->tree->max_match();
  static const int kMaxBacksearchLimit = 1024;
  if (is_end_anchored && !is_start_anchored && !IsSticky(flags) &&
      max_length < kMaxBacksearchLimit) {
    macro_assembler->SetCurrentPositionFromEnd(max_length);
  }

SetCurrentPositionFromEnd is a one-line change to the machine’s starting position that turns an O(n) scan into an O(1) one for patterns like /foo$/. The kMaxBacksearchLimit = 1024 cap is there because if the maximum match length is large, the “how far from the end” arithmetic is not worth the risk of a large backtrack.

The Node::kRecursionBudget = 200 in those calls is a stack guard: the analysis functions recurse over the tree, and a pathological pattern could otherwise blow the C++ stack. The budget caps the recursion, and the answer degrades to “I don’t know”.

The `.*?` prefix

The single most surprising thing in the compiler is that an unanchored pattern gets a .*? glued to the front of it:

cpp
// src/regexp/regexp-compiler.cc:6478
  if (!data->tree->IsCertainlyAnchoredAtStart(Node::kRecursionBudget) &&
      !IsSticky(flags())) {
    // Add a .*? at the beginning, outside the body capture, unless
    // this expression is anchored at the beginning or sticky.
    TRACE_GRAPH("* Add .*? at beginning of unanchored, non-sticky RegExp");
    has_search_prefix_ = true;
    Node* loop_node = Quantifier::ToNode(
        0, Tree::kInfinity, false,
        zone()->New<ClassRanges>(StandardCharacterSet::kEverything), this,
        captured_body, data->contains_anchor);

This is how “find the pattern anywhere in the string” is expressed in a machine that only knows how to match at the current position: try to match here; if that fails, consume one character and try again. Because the quantifier is lazy (.*? and not .*), the machine tries the match at every position before consuming, which gives leftmost-first semantics for free.

The comment at the end of the file explains that the compiler recognises this generated loop structurally, so it can tell it apart from a user-written [\s\S]*?foo:

cpp
// src/regexp/regexp-compiler.cc:4460
// The machine-generated `.*?` loop that PreprocessRegExp prepends to every
// unanchored, non-sticky pattern to retry the match at each start position.
// Recognized structurally: a two-alternative loop whose second alternative is
// an omnivorous (matches-anything) text looping back to the loop.  A
// user-written loop of that exact shape (e.g. /[\s\S]*?foo/) matches too, which
// is harmless -- its loop-exit backtrack has the same rescan-forward behavior.

From tree to machine

The compiler turns the tree into a graph of Nodes and then emits code for each node. The emission is a work list, not a recursive walk, because the graph is not a tree — choices create shared nodes and cycles:

cpp
// src/regexp/regexp-compiler.cc:398
  while (!work_list.empty()) {
    WorkItem item = work_list.back();
    Node* node = item.node;
    TRACE_WITH_NODE(this, "Popping from worklist ", node);
    work_list.pop_back();
    node->set_on_work_list(false);
    if (!node->label()->is_bound()) {
      if (node->Emit(this, &new_trace).IsError()) {
        work_list_ = nullptr;
        return ReportError();
      }
    }
  }
  // Emit must report every code generation error.
  CHECK(!IsRegExpTooBig());

The CHECK(!IsRegExpTooBig()) is load-bearing: the assembler reports errors by setting a flag, and the flag must be checked after every emission, because a half-emitted machine is not a machine.

The target of the emission is a RegExpMacroAssembler, and there are two implementations of it. One emits native code for a specific architecture; the other emits bytecode:

cpp
// src/regexp/regexp.cc:1440
  std::unique_ptr<RegExpMacroAssembler> macro_assembler;
  if (data->compilation_target == CompilationTarget::kNative) {
    // Native regexp implementation.
    DCHECK(!v8_flags.jitless);

    const int output_register_count =
        JSRegExp::RegistersForCaptureCount(data->capture_count);
    macro_assembler = CreateNativeMacroAssembler(isolate, zone, is_one_byte,
                                                 output_register_count);
  } else {
    DCHECK_EQ(data->compilation_target, CompilationTarget::kBytecode);
    // Interpreted regexp implementation.
    macro_assembler.reset(
        new BytecodeGenerator(isolate, zone,
                              is_one_byte ? RegExpMacroAssembler::LATIN1
                                          : RegExpMacroAssembler::UC16));

That is the key structural decision: the compiler does not know whether it is producing native code or bytecode. It emits against an abstract assembler interface, and the same node graph, the same analysis and the same quick-check computation serve both. The bytecode is not a lower-fidelity version of the native code — it is the same program in a different encoding.

The bytecode itself has a small set of operations, including some compound ones that only exist in bytecode and are peephole-generated:

cpp
// src/regexp/regexp-bytecodes.h:246
  /* Combination of:                                                        */
  /* LoadCurrentCharacter, CheckBitInTable and AdvanceCpAndGoto             */
  V(SkipUntilBitInTable,                                                       \
    (cp_offset, advance_by, table, bounds_check_offset, on_match,              \
     on_no_match),                                                             \

The backtracking machine

The machine has a set of registers. Each capture group has two (start and end), and there is a current-position register plus a set of backtrack-stack slots. A backtrack is a jump to a saved program counter plus a saved position.

In native code, the backtrack is a jump to a shared block:

cpp
// src/regexp/x64/regexp-macro-assembler-x64.cc:150
void RegExpMacroAssemblerX64::Backtrack() {
  // Defer to the shared backtrack block bound in GetCode: only there, with
  // the body fully emitted, is it known whether anything was ever pushed.
  // If nothing was, the only value a pop could yield is the fail label,
  // so the block reduces to Fail() and the backtrack stack (including the
  // fail label itself) is elided entirely.
  __ jmp(&backtrack_label_);
}

“Only there, with the body fully emitted, is it known whether anything was ever pushed” — this is a small but real optimisation: a pattern that never backtracks (say /abc/) needs no backtrack stack at all, and V8 only discovers that after it has emitted the whole body. So the decision is deferred to the very end.

The backtrack block itself is where the backtrack limit is enforced:

cpp
// src/regexp/x64/regexp-macro-assembler-x64.cc:159
void RegExpMacroAssemblerX64::EmitBacktrack() {
  CheckPreemption();
  if (has_backtrack_limit()) {
    Label next;
    __ incq(Operand(rbp, kBacktrackCountOffset));
    __ cmpq(Operand(rbp, kBacktrackCountOffset), Immediate(backtrack_limit()));
    __ j(not_equal, &next, Label::kNear);

    // Backtrack limit exceeded.
    if (can_fallback()) {
      __ jmp(&fallback_label_);
    } else {
      // Can't fallback, so we treat it as a failed match.
      Fail();
    }

    __ bind(&next);
  }

The same limit exists in the bytecode interpreter, and the check is identical:

cpp
// src/regexp/regexp-interpreter.cc:643
    BYTECODE(Backtrack, return_code) {
      static_assert(JSRegExp::kNoBacktrackLimit == 0);
      if (++backtrack_count == backtrack_limit) {
        return static_cast<IrregexpInterpreter::Result>(return_code);
      }

The backtrack limit and the fallback

The backtrack limit is not a safety valve that throws. It is the trigger for a different engine. Here is the whole policy, in one function:

cpp
// src/regexp/regexp.cc:1064
void SetBacktrackAndExperimentalFallback(
    regexp::RegExpMacroAssembler* macro_assembler,
    DirectHandle<IrRegExpData> re_data) {
  uint32_t backtrack_limit = re_data->backtrack_limit();
  if (v8_flags.enable_experimental_regexp_engine_on_excessive_backtracks &&
      re_data->is_linear_executable()) {
    if (backtrack_limit == JSRegExp::kNoBacktrackLimit) {
      backtrack_limit = v8_flags.regexp_backtracks_before_fallback;
    } else {
      backtrack_limit = std::min(
          backtrack_limit, v8_flags.regexp_backtracks_before_fallback.value());
    }
    re_data->set_backtrack_limit(backtrack_limit);
    macro_assembler->set_backtrack_limit(backtrack_limit);
    macro_assembler->set_can_fallback(true);
  } else {
    macro_assembler->set_backtrack_limit(backtrack_limit);
    macro_assembler->set_can_fallback(false);
  }
}

Two things to notice. First, the limit is only installed if the pattern can be handled by the other engine (is_linear_executable). Second, the fallback is a machine-level jump (__ jmp(&fallback_label_)), so the switch from backtracking to breadth-first happens without unwinding anything — the same registers, the same subject, the same output vector.

The threshold is 50 000 backtracks:

cpp
// src/flags/flag-definitions.h:3628
DEFINE_POSITIVE_SMI(
    regexp_backtracks_before_fallback, 50000,
    "number of backtracks during regexp execution before fall back "
    "to experimental engine if "
    "enable_experimental_regexp_engine_on_excessive_backtracks is set")

The fallback is an experimental feature flag, off by default:

cpp
// src/flags/flag-definitions.h:3624
DEFINE_EXPERIMENTAL_FEATURE(
    enable_experimental_regexp_engine_on_excessive_backtracks,
    "fall back to a breadth-first regexp engine on excessive "
    "backtracking")

And the result of the fallback is threaded back up through the exec path as a distinct return code:

cpp
// src/regexp/regexp.cc:1350
  if (res >= RegExp::RE_SUCCESS) {
    DCHECK_LE(res * output_register_count, result_offsets_vector_length);
    return res;
  } else if (res == RegExp::RE_FALLBACK_TO_EXPERIMENTAL) {
    return ExperimentalRegExp::OneshotExec(
        isolate, regexp_data, subject, previous_index, result_offsets_vector,
        result_offsets_vector_length);
  }

So the same RegExp.prototype.exec call, on the same subject, with the same pattern, can execute two completely different algorithms and produce the same answer.

The experimental engine

The experimental engine does not backtrack at all. It simulates an NFA in breadth-first order, which is linear in the length of the input. The source explains the semantics problem this creates at length:

cpp
// src/regexp/experimental/experimental-interpreter.cc:252
template <class Character>
class NfaInterpreter {
  // Executes a bytecode program in breadth-first mode, without backtracking.
  // `Character` can be instantiated with `uint8_t` or `base::uc16` for one byte
  // or two byte input strings.
  //
  // In contrast to the backtracking implementation, this has linear time
  // complexity in the length of the input string. Breadth-first mode means
  // that threads are executed in lockstep with respect to their input
  // position, i.e. the threads share a common input index.  This is similar
  // to breadth-first simulation of a non-deterministic finite automaton (nfa),
  // hence the name of the class.

And then the interesting part — matching a backtracking engine’s answer with a breadth-first engine requires emulating the backtracking engine’s priority order:

cpp
// src/regexp/experimental/experimental-interpreter.cc:278
  // However, if we execute breadth first, then we execute the 3 threads
  // - t1, which tries to match /abc/
  // - t2, which tries to match /../
  // - t3, which tries to match /[a-c]{10,}/
  // in lockstep i.e. by iterating over the input and feeding all threads one
  // character at a time.  t2 will execute an ACCEPT after two characters,
  // while t1 will only execute ACCEPT after three characters. Thus we find a
  // match for the second alternative before a match of the first alternative.

This is the crux. /abc|..|[a-c]{10,}/ on "abcccccccccccccc" must report "abc", because a backtracking engine tries the first alternative first. A naive breadth-first NFA would report "ab" because the second alternative accepts earlier. So the interpreter keeps a priority-ordered list of threads and, when a thread accepts, discards only the threads with lower priority:

cpp
// src/regexp/experimental/experimental-interpreter.cc:296
  // Thus the interpreter keeps track of a priority-ordered list of threads.
  // If a thread ACCEPTs, all threads with lower priority are discarded, and
  // the search continues with the threads with higher priority.  If no threads
  // with high priority are left, we return the match that was produced by the
  // ACCEPTing thread with highest priority.

That is the whole trick: linear time and backtracking-compatible results, by keeping the priority order that the backtracker would have had.

Tiering: interpret, then compile

The interpreter and the native code are not alternatives you pick at build time — they are tiers. The flag definitions spell out the three modes:

cpp
// src/flags/flag-definitions.h:3514
// The regexp engine runs in one of three modes. The default is single-tier:
// compile directly to native code on first use, expressed as tier-up with a
// zero-tick threshold so that regexp_tier_up_ticks stays a usable knob. A
// nonzero tick count selects the two-tier pipeline (interpret, then compile);
// regexp_interpret_all never compiles to native code (and is implied by
// jitless).

The default is --regexp-tier-up-ticks=0, which means “tier up immediately”: the first execution goes straight to native code. A non-zero tick count gives you the two-tier pipeline, where the bytecode interpreter runs the regexp N times before the native code is compiled.

The tick counter lives in the RegExpData:

cpp
// src/objects/js-regexp.cc:279
void IrRegExpData::TierUpTick() {
  int tier_up_ticks = ticks_until_tier_up();
  if (tier_up_ticks == 0) {
    return;
  }

  set_ticks_until_tier_up(tier_up_ticks - 1);
}

and the decision of which tier to use is a pure function of the tick count:

cpp
// src/objects/js-regexp.cc:293
bool IrRegExpData::ShouldProduceBytecode() {
  return v8_flags.regexp_interpret_all ||
         (v8_flags.regexp_tier_up && !MarkedForTierUp());
}

There is also a second tier-up trigger, based on the subject length. The interpreter is much slower than native code on long strings, so V8 forces the tier-up:

cpp
// src/regexp/regexp.cc:1286
  // Maybe force early tier up:
  if (v8_flags.regexp_tier_up) {
    if (subject->length() >= JSRegExp::kTierUpForSubjectLengthValue) {
      // For very long subject strings, the regexp interpreter is currently much
      // slower than the jitted code execution. If the tier-up strategy is
      // turned on, we want to avoid this performance penalty so we eagerly
      // tier-up if the subject string length is equal or greater than the given
      // heuristic value.
      regexp_data->MarkTierUpForNextExec();

kTierUpForSubjectLengthValue is 1000. And the second trigger is even odder: the interpreter does not implement global mode, so a global regexp always has to tier up:

cpp
// src/regexp/regexp.cc:1302
    } else if (static_cast<uint32_t>(original_register_count) <
               result_offsets_vector_length) {
      // Tier up because the interpreter doesn't do global execution.
      regexp_data->MarkTierUpForNextExec();

The detection of “the interpreter needs to give up” is not a flag but a return code. The interpreter returns RETRY when the subject string changed representation under it (a string can be internalised or externalised between the flattening and the match, and it can switch between Latin-1 and UTF-16), and the exec path handles it by restarting with the new encoding:

cpp
// src/regexp/regexp.cc:1211
  if (!regexp_data->ShouldProduceBytecode()) {
    do {
      EnsureCompiledIrregexp(isolate, regexp_data, subject, is_one_byte);
      SYNCHRONIZATION_POINT("IrregexpExecRaw_JIT");
      // The stack is used to allocate registers for the compiled regexp code.
      // This means that in case of failure, the output registers array is left
      // untouched and contains the capture results from the previous successful
      // match.  We can use that to set the last match info lazily.
      int res = NativeRegExpMacroAssembler::Match(regexp_data, subject,
                                                  is_one_byte, output,
                                                  output_size, index, isolate);

The quick check: rejecting before the engine

Before the engine runs at all, two filters can reject the subject. They are computed at compile time and stored in the RegExpData. The first is a four-character mask comparison, the second is a bitset of “characters a match can start with”:

cpp
// src/builtins/builtins-regexp-gen.cc:836
  // Throw out attempts that cannot match without entering the engine, using
  // two filters built during compilation: (chars & mask) == value over the
  // next four characters, and a bitset of what a match can start with.  A
  // regexp may have either, both, or neither, and running both rejects more
  // than either does alone.  This is RegExpData::QuickCheckRejects in CSA.

The mask filter reads four characters at once as a 32-bit word, masks them, and compares:

cpp
// src/builtins/builtins-regexp-gen.cc:858
    // Mask first.
    {
      TNode<Uint32T> mask = LoadObjectField<Uint32T>(
          data, offsetof(RegExpData, quick_check_mask_));
      GotoIf(Word32Equal(mask, Int32Constant(0)), &try_bitset);

      // Four characters have to be left to read four.  The bitset reads only
      // one, so a shorter tail skips ahead to it rather than giving up.
      GotoIf(IntPtrLessThan(remaining, IntPtrConstant(kUInt32Size / kCharSize)),
             &try_bitset);

      TNode<Uint32T> expected = LoadObjectField<Uint32T>(
          data, offsetof(RegExpData, quick_check_value_));

      TNode<Uint32T> loaded_word = Load<Uint32T>(string_data, actual_index);

      TNode<Word32T> masked_chars = Word32And(loaded_word, mask);
      Branch(Word32Equal(masked_chars, expected), &try_bitset, &out);
    }

The bitset filter is the “first character must be one of these” test, and it is a 256-bit table indexed by the byte value:

cpp
// src/builtins/builtins-regexp-gen.cc:878
    // A set bit means "no match can start with this character", so a regexp
    // without a bitset has all zeroes and falls through on its own.  Reads a
    // single character, so unlike the mask it works on a short tail too.

The masks are computed by the compiler from the first few characters the pattern can match. The compiler is careful to only build the four-byte mask on little-endian machines, because the mask is compared against four characters loaded as one word:

cpp
// src/regexp/regexp-compiler.cc:3188
  // Little-endian only: the mask is compared against four characters loaded as
  // one word, so byte order matters.  The bitset below indexes by character
  // value instead and works everywhere.
#ifdef V8_TARGET_LITTLE_ENDIAN

Not running the match at all

The last optimisation is the crudest and the most effective: don’t run the regexp. V8 keeps a per-isolate cache of regexp results, keyed by the subject string and the pattern:

cpp
// src/regexp/regexp.h:237
// Caches results for specific regexp queries on the isolate. At the time of
// writing, this is used during global calls to RegExp.prototype.exec and
// @@split.
class ResultsCache final : public AllStatic {

The lookup is a two-way set-associative probe into a flat FixedArray:

cpp
// src/regexp/regexp.cc:1729
  const int cache_size = SizeForType(type);
  uint32_t hash = key_string->hash();
  uint32_t index =
      ((hash & (cache_size - 1)) & ~(kArrayEntriesPerCacheEntry - 1));
  if (cache->get(index + kStringOffset) != key_string ||
      cache->get(index + kPatternOffset) != key_pattern) {
    index = ((index + kArrayEntriesPerCacheEntry) & (cache_size - 1));
    if (cache->get(index + kStringOffset) != key_string ||
        cache->get(index + kPatternOffset) != key_pattern) {
      return Smi::zero();
    }
  }

Each entry is four slots: the subject string, the pattern, the result array, and a snapshot of the last match info. That last slot is the “lazy result” mechanism. When the cache hits, the last match info — the RegExpMatchInfo object that RegExp.lastMatch and the deprecated RegExp.$1 properties read — is not recomputed; it is replayed from the snapshot:

cpp
// src/builtins/builtins-regexp-gen.cc:255
// Restores LastMatchInfo from a SnapshotLastMatchInfo result. An empty
// snapshot means the split loop never matched, so LastMatchInfo is left alone.
void RegExpBuiltinsAssembler::ReplayLastMatchInfo(
    TNode<Context> context, TNode<String> subject,
    TNode<FixedArray> last_match_cache) {

and the snapshot is taken when the result is computed:

cpp
// src/builtins/builtins-regexp-gen.cc:279
// Records the match LastMatchInfo currently holds, for a later hit to replay.
// Returns the empty array if the split loop never matched.
TNode<FixedArray> RegExpBuiltinsAssembler::SnapshotLastMatchInfo(
    TNode<Context> context, TNode<BoolT> did_match) {

The two cache sizes differ by use case, and the reason is stated in the source:

cpp
// src/regexp/regexp.h:263
  static constexpr int kRegExpResultsCacheSize = 0x100;
  // Splits reuse many more distinct (subject, pattern) pairs than the other
  // cache types.
  static constexpr int kRegExpSplitResultsCacheSize = 0x400;

256 entries for global exec and String.prototype.match, 1024 for split, because a split call site tends to see many different subjects with the same pattern.

The exec builtin

The last piece is how JavaScript gets to the machine. RegExp.prototype.exec is a Torque macro that dispatches on the RegExpData type, and for the IRREGEXP case it calls the generated code directly:

cpp
// src/builtins/builtins-regexp-gen.cc:695
TNode<RegExpMatchInfo> RegExpBuiltinsAssembler::RegExpExecInternal_Single(
    TNode<Context> context, TNode<JSRegExp> regexp, TNode<String> string,
    TNode<Number> last_index, Label* if_not_matched) {

The RegExpMatchInfo — the object that holds the capture offsets — is only filled in after a successful match:

cpp
// src/builtins/builtins-regexp-gen.cc:719
    TNode<UintPtrT> num_matches = RegExpExecInternal(
        context, regexp, data, string, last_index, result_offsets_vector,
        SmiToInt32(result_offsets_vector_length));

    GotoIf(IntPtrEqual(num_matches, IntPtrConstant(0)), &not_matched);

The native machine is called with nine arguments, and the comment on each one is worth reading because it tells you exactly what the machine does and does not care about:

cpp
// src/builtins/builtins-regexp-gen.cc:1001
    // Argument 2: Start of string data. This argument is ignored in the
    // interpreter.
    MachineType arg2_type = type_ptr;
    TNode<RawPtrT> arg2 = var_string_start.value();

    // Argument 3: End of string data. This argument is ignored in the
    // interpreter.

There is also a runtime fallback, for the case where the machine has not been compiled yet or the string is in a representation the machine cannot handle:

cpp
// src/runtime/runtime-regexp.cc:969
RUNTIME_FUNCTION(Runtime_RegExpExec) {
  HandleScope scope(isolate);
  DCHECK_EQ(4, args.length());
  DirectHandle<RegExpData> regexp_data =
      SbxCast<RegExpData>(TrustedCast<TrustedObject>(args.at<Object>(0)));

Note the result vector: it is not a JavaScript array, it is a raw int32_t* pointing into a per-isolate buffer:

cpp
// src/runtime/runtime-regexp.cc:980
  // This untagged arg must be passed as an implicit arg.
  int32_t* result_offsets_vector = reinterpret_cast<int32_t*>(
      isolate->isolate_data()->regexp_exec_vector_argument());

The offsets are copied out of that buffer into a RegExpMatchInfo only if a match happened. On failure, the buffer still holds the previous successful match’s offsets, which is exactly what makes the “set the last match info lazily” comment in IrregexpExecRaw possible.

Trade-offs

What it buys. A regex engine that runs at native speed for the common cases, that can reject most subjects without doing any work at all (the quick check), that never even enters the engine for the same subject twice (the results cache), and that has a guaranteed escape from exponential blowup (the experimental engine).

What it costs.

Three engines. A pattern can be an atom, an irregexp (bytecode or native), or an experimental regexp. Every behavioural question — what happens with a zero-length match, with lastIndex, with the d flag — has to be answered consistently in all of them.
The interpreter and the native code can disagree. They are generated from the same node graph, but the bytecode has a peephole pass that the native path does not, and the bytecode has extra operations with no native equivalent. V8 mitigates this with --regexp-assemble-from-bytecode, which assembles the native code from the bytecode rather than recompiling from the source, precisely so that the two tiers cannot drift:
cpp
```
// src/flags/flag-definitions.h:3545
DEFINE_BOOL(regexp_assemble_from_bytecode, false,
            "assemble regexp JIT-code from bytecode")
```
The experimental engine is a compatibility risk. It has to reproduce the priority order of a backtracking engine exactly, including lookaround, which it does with a precomputed table of “does this lookaround match at this position” of size input_size x lookaround_count. For a long subject that table is large.
The backtrack limit is a heuristic. 50 000 backtracks is not “enough for a reasonable pattern on a reasonable input”. It is a number, and patterns exist where 50 000 backtracks is a lot of work and 50 001 is a catastrophe.
The quick check is only computed for one-byte subjects. The CSA code bails out to the slow path for two-byte strings, so the filter only helps Latin-1 text.

The bottom line

V8’s regexp engine is a backtracking machine with three escape hatches. The machine itself is generated from a node graph by a compiler that emits against an abstract assembler, so the same analysis produces both bytecode and native code. In front of the machine sit two filters that can reject a subject without running it, and behind it sits a cache that can return a previous answer without running it either.

The genuinely interesting piece is the fallback: when the backtracker exceeds its budget, V8 does not throw or give up — it re-runs the same pattern with a breadth-first NFA simulation that is linear in the input length, and takes care to reproduce the backtracker’s leftmost-first priority order so that the answer is identical. That is the design idea worth stealing: a pathological case should change the algorithm, not the answer.

The thing people get wrong

“V8 uses a Thompson NFA / Pike VM / DFA for regexps” is wrong on all three counts. It uses a backtracking VM with an explicit backtrack stack, because that is the only thing that can implement backreferences and lookaround efficiently. The breadth-first engine exists, but it is an experimental fallback for pathological patterns, not the main engine.

The other common misconception is that /(a+)+b/ against a long string of as will hang V8. It will not, if the pattern is linear-executable, because the backtrack limit catches it and the fallback engine takes over. What it will do is take a while — 50 000 backtracks first, and then the breadth-first simulation, which allocates a table proportional to the input length. The protection is against unbounded time, not against slowness.