RegExp Engine (Irregexp) Architecture

This document describes the architecture of V8's regular expression engine, Irregexp.

Overview

Irregexp is a highly optimized regular expression engine. It does not use a simple backtracking NFA/DFA interpreter by default (though an experimental non-backtracking engine exists). Instead, it compiles regular expressions either directly into native machine code or into a specialized bytecode that is executed by a dedicated interpreter.

The Compilation Pipeline

Irregexp has its own complete mini-compiler pipeline:

1. Parsing: The Parser (src/regexp/regexp-parser.h) parses the regular expression pattern string into a specialized Abstract Syntax Tree (AST) defined in src/regexp/regexp-ast.h. Note that AST classes are not prefixed with RegExp (e.g., Tree, Disjunction).
2. Node Graph Generation: The AST is converted into a graph of Node objects (src/regexp/regexp-nodes.h). This graph represents the state machine for matching. Similar to AST classes, Node classes are not prefixed with RegExp (e.g., Node, TextNode).
3. Optimization: The engine performs analysis on the graph, such as computing eats_at_least (minimum characters needed to match) and setting up Boyer-Moore lookahead tables for fast scanning.
4. Code Generation: The Compiler (src/regexp/regexp-compiler.h) traverses the graph and generates code using RegExpMacroAssembler.
   • Native Target: Generates raw machine code for the target architecture.
   • Bytecode Target: Generates Irregexp bytecode.

Execution Modes

Irregexp can execute in two main modes, defined by regexp::CompilationTarget:

• kNative: The engine generates machine code. This provides the fastest execution but consumes more memory for the generated code.
• kBytecode: The engine generates bytecode. This is interpreted by IrregexpInterpreter (src/regexp/regexp-interpreter.h). This saves memory and is useful on platforms where JIT compilation is not allowed or for less frequently used regexps.

Key Optimizations

• Boyer-Moore Lookahead: For non-anchored regular expressions, Irregexp uses a Boyer-Moore-like skip table to quickly skip characters in the subject string that cannot possibly match the start of the pattern.
• Quick Check: A mechanism that loads multiple characters at once and uses a mask-and-compare strategy to quickly reject non-matches.
• Traces: During code generation, the compiler uses Trace objects to track the current state (character position, deferred actions, backtracking stack) to generate efficient code paths and avoid redundant work.

File Structure

• src/regexp/: Core RegExp implementation.
• src/regexp/regexp-parser.h / .cc: Parser.
• src/regexp/regexp-ast.h: AST definitions.
• src/regexp/regexp-compiler.h / .cc: Compiler.
• src/regexp/regexp-interpreter.h / .cc: Bytecode interpreter.
• src/regexp/regexp-nodes.h: Graph node definitions.