CppCon 2018: Hana Dusíková “Compile Time Regular Expressions”

CppCon

AI-assisted summary of CppCon 2018: Hana Dusíková “Compile Time Regular Expressions” — original source. Check the original for full context.

Source published: 2018-10-24

Key ideas

Compile Time Regular Expressions (CTRE) utilizes C++20 Class Non-Type Template Parameters (NTTPs) to parse regular expression strings and construct an Abstract Syntax Tree purely at compile time, eliminating runtime parsing overhead. (5:20)
In large-scale benchmarks matching against a ~2 GB CSV file, CTRE completed execution in 3.9 seconds, outperforming egrep (50 s), GCC libstdc++ std::regex (55 s), and Clang libc++ std::regex (21 minutes). (37:53)
CTRE compiles regular expressions in linear time O(N) relative to pattern length, adding roughly 200 ms per unique pattern on modern hardware while generating as few as 24 to 98 lines of optimized assembly compared to ~20,000 lines linked by std::regex. (43:03)
Because all matching functions are constexpr and completely avoid dynamic heap allocations, the exact same functional traversal can validate strings at compile time or compile into native machine code for runtime std::string_view evaluation. (50:05)

Detailed notes

## Background Published on YouTube by CppCon on October 24, 2018, this presentation features Hana Dusíková demonstrating her Compile Time Regular Expressions (CTRE) library. The session covers how C++20 features allow regular expressions to be constructed directly from compile-time strings, eliminating the runtime parsing overhead and linked-library dependencies inherent in traditional regex engines while comparing generated code against existing solutions in Compiler Explorer.

## TL;DR Hana Dusíková introduces CTRE, an open-source library that parses regular expression strings at compile time using an internal LL(1) parser driven by C++ function overloading and Class Non-Type Template Parameters. By shifting pattern validation and Abstract Syntax Tree (AST) construction entirely into constexpr template metaprogramming, the engine generates compact machine code and guarantees linear compile-time parsing complexity without runtime constructor costs. Real-world benchmarks against std::regex and PCRE2 demonstrate dramatic runtime speedups on large datasets while avoiding template error cascades and binary bloat. Dusíková concludes with live Compiler Explorer demonstrations, explaining how a purely functional, heap-free matching pipeline enables identical code to validate strings at compile time or compile into tightly optimized assembly for runtime evaluation.

## Atmosphere & style The presentation carries an engaging, approachable, and self-deprecating tone, characterized by Dusíková's deadpan humor about slide generation bugs, fear of Flex and Bison, and playful jabs at standard library performance. The room reacts with genuine enthusiasm, bursting into spontaneous applause and laughter at extreme runtime contrasts—especially libc++'s multi-minute execution times. Despite tackling intricate template metaprogramming concepts and formal language theory, the dialogue between Dusíková and attendees like Bryce Adelstein Lelbach and Odin Holmes feels warm, interactive, and deeply collegial.

## Bulletin - [05:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=320s) Compile Time Regular Expressions (CTRE) utilizes C++20 Class Non-Type Template Parameters (NTTPs) to parse regular expression strings and construct an Abstract Syntax Tree purely at compile time, eliminating runtime parsing overhead. - [37:53](https://www.youtube.com/watch?v=QM3W36COnE4&t=2273s) In large-scale benchmarks matching against a ~2 GB CSV file, CTRE completed execution in 3.9 seconds, outperforming egrep (50 s), GCC libstdc++ std::regex (55 s), and Clang libc++ std::regex (21 minutes). - [43:03](https://www.youtube.com/watch?v=QM3W36COnE4&t=2583s) CTRE compiles regular expressions in linear time O(N) relative to pattern length, adding roughly 200 ms per unique pattern on modern hardware while generating as few as 24 to 98 lines of optimized assembly compared to ~20,000 lines linked by std::regex. - [50:05](https://www.youtube.com/watch?v=QM3W36COnE4&t=3005s) Because all matching functions are constexpr and completely avoid dynamic heap allocations, the exact same functional traversal can validate strings at compile time or compile into native machine code for runtime std::string_view evaluation.

## Key takeaways - [00:00](https://www.youtube.com/watch?v=QM3W36COnE4&t=0s) Traditional regular expression engines like std::regex impose severe runtime penalties by parsing pattern strings and building automata at runtime, an exponential complexity process that should be calculated via constexpr instead. - [00:00](https://www.youtube.com/watch?v=QM3W36COnE4&t=0s) std::regex lacks native support for std::string_view, forcing developers into cumbersome iterator pair syntax. - [05:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=320s) C++20 Class Non-Type Template Parameters (NTTPs) allow fixed literal string wrappers to be passed directly as template arguments, enabling compile-time regex pattern definitions. - [05:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=320s) Invalid regular expression syntax triggers clean, concise static_assert failure messages at compile time rather than massive template error cascades. - [05:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=320s) CTRE generates exceptionally lean assembly (~98 lines for CSV extraction and ~24 lines for literal matching), avoiding the roughly 20,000 lines of runtime engine assembly required by std::regex. - [11:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=680s) The pattern parsing engine is built as an LL(1) table-driven parser that operates at compile time using purely functional transformations and function overloading as the transition function. - [14:49](https://www.youtube.com/watch?v=QM3W36COnE4&t=889s) By completely decoupling the generic LL(1) parser algorithm from the grammar definition struct, the same engine architecture can theoretically parse other grammars like JSON or Brainfuck. - [18:04](https://www.youtube.com/watch?v=QM3W36COnE4&t=1084s) Specialized variants of the LL(1) grammar allow the compile-time parser to operate in linear O(N) time with zero backtracking during pattern parsing. - [22:38](https://www.youtube.com/watch?v=QM3W36COnE4&t=1358s) Semantic action markers embedded within grammar rules transform the parse tree into an Abstract Syntax Tree (AST) expression template using functional modify() template overloads. - [31:29](https://www.youtube.com/watch?v=QM3W36COnE4&t=1889s) The runtime matching engine executes recursive matching across stack-based type lists without runtime abstraction overhead. - [37:53](https://www.youtube.com/watch?v=QM3W36COnE4&t=2273s) While Deterministic Finite Automata (DFAs) provide rapid matching, they struggle with tracking submatch boundaries, necessitating backtracking non-deterministic finite automata (NFAs) for full capture support. - [43:03](https://www.youtube.com/watch?v=QM3W36COnE4&t=2583s) Counterintuitively, compiling translation units with CTRE is often faster than compiling std::regex headers because the standard library's heavy runtime engine strains compiler optimization passes. - [43:03](https://www.youtube.com/watch?v=QM3W36COnE4&t=2583s) Duplicate regex instantiations across a translation unit incur virtually zero additional compile time due to compiler template instantiation caching. - [48:56](https://www.youtube.com/watch?v=QM3W36COnE4&t=2936s) Practical regular expression lengths are currently constrained to around 1,000 characters by compiler recursion depth limits, though input grammar complexity itself does not degrade parse performance. - [46:53](https://www.youtube.com/watch?v=QM3W36COnE4&t=2813s) Hana Dusíková advocates that modern modernizations should eventually be merged directly into standard C++ so that std::regex natively evaluates regular expressions at compile time.

## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=QM3W36COnE4&t=0s) Introduction and Motivation for Compile-Time Regular Expressions

Hana Dusíková opens the talk welcoming the audience, joking that if anyone wants to take her place on stage they are welcome to do so. She introduces herself as a senior researcher at Avast living in Brno, Czech Republic (Czechia), where she organizes the local Avast C++ meetup. She notes that she will soon represent the Czech national body for WG21, the ISO C++ standards committee. She also quips that while she is an amateur photographer, as of the previous week she decided to stop hiking, adding with a smile, “Bryce will tell you more.”

Turning to the core subject, regular expressions serve three main tasks across programming: matching an input subject against a pattern, extracting matching sub-content, or modifying parts of the subject. Matching alone can be executed using a deterministic finite automaton (DFA), which runs significantly faster than the backtracking or search-based approaches required for capturing content. Basic regular expressions (such as `[a-c0-9]+`) vary across dialects like ECMAScript, Perl, and PCRE in advanced capabilities, but their fundamental mechanics remain identical. In standard C++, using regular expressions requires instantiating an engine object with a pattern and invoking an algorithm like `std::regex_match`:

```cpp std::regex r{"[a-c0-9]+"}; std::regex_match(str.begin(), str.end(), r); ```

Dusíková points out an immediate annoyance: because `std::regex` lacks direct support for `std::string_view`, developers are forced to pass iterator pairs. The fundamental pipeline in C++ and C is identical across almost every language: define a pattern string, pass it to a constructor to build the engine, and execute matches against inputs.

```mermaid flowchart LR accTitle: Traditional Regex Lifecycle accDescr: Pipeline showing pattern parsing and automaton building at runtime followed by matching. subgraph S1["Runtime Constructor"] A["Pattern String"] --> B["Parser"] B --> C["Automaton / Tree"] end subgraph S2["Runtime Execution"] C --> D["Match Input Subject"] end ```

Building and matching within the same hot function must be avoided at all costs due to severe performance penalties. The constructor carries the burden of parsing the pattern string and constructing complex internal representations—whether trees, lookup tables, or finite state machines. Dusíková emphasizes that building a deterministic finite automaton is an exponential-complexity algorithm.

To avoid repeated constructor invocations, engineers traditionally write hand-rolled state machines in several hundred lines of code, but this is tedious, error-prone, and difficult to maintain. Alternatively, third-party code generators like Flex and Bison introduce heavy build pipeline complexity and portability headaches across target platforms. While interpreted languages like Perl provide built-in language-level support, C++ has historically lacked native regular expressions. Dusíková argues that running the parser and constructor dynamically makes no sense when the pattern is fixed:

> “So, if you have application installed on million of mobile phones, each mobile phone, every time, do the same calculation. Why? It should be constexpr. It should be pre-calculated.”

Developers should treat regular expressions just like compiled C++ code: “No one will use interpret of Python in their code to match string, but we are doing it with regular expressions.” An ideal implementation demands zero runtime cost for parsing the pattern, absolute maximum throughput, and zero overhead.

---

[05:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=320s) C++20 Class NTTPs, CTRE Syntax, and Assembly Output

Dusíková presents the modern interface made possible by the Compile Time Regular Expression (CTRE) library. Users express patterns directly inside template arguments alongside the subject string:

```cpp ctre::match<"[a-c0-9]+">(subject); ```

This syntax is readable, easy to maintain, and backed by elegant mechanics. In C++20, this design leverages Class Non-Type Template Parameters (Class NTTPs), allowing class types to serve as template arguments. While the core language feature was merged into the C++ working draft, compilers did not yet fully implement standard library support at the time. To bridge this gap, Dusíková relies on the N3599 extension (`template <typename Char, Char... Cs> operator""_ctre()`) authored by Richard Smith, supported in GCC since version 4 and in Clang.

The compile-time approach unlocks expressive patterns and ironclad static verification: - **Compile-Time Testing:** Expressions can be evaluated directly in `constexpr` contexts; if an expression fails to match test data, the binary simply refuses to compile. - **Structured Data Extraction:** Capturing first and last names from CSV inputs requires only reading match captures cleanly (e.g., `match.get<1>()`, `match.get<2>()`). - **Structured Bindings Support:** Date extraction directly integrates with C++17 structured bindings (`auto [all, year, month, day] = ctre::match<"...">(input);`).

Anticipating skepticism that templates will emit bloated assembly, Dusíková shares concrete compiler benchmarks. Compiling the CSV first-and-last-name extraction with CTRE generates a lean, tightly optimized 98 lines of assembly. In contrast, while compiler optimizers should theoretically recognize intent and collapse `std::regex`, the standard library alternative generates nearly 20,000 lines of assembly because the entire runtime engine runtime apparatus is linked into the binary.

```mermaid flowchart TD accTitle: CTRE Error Handling and Assembly Comparison accDescr: Contrasting CTRE's compact assembly and static errors with std::regex bloating. subgraph CTRE["Compile-Time Regular Expressions (CTRE)"] direction TB C1["constexpr Pattern Parsing"] --> C2["98 lines of clean assembly"] C1 --> C3["Concise 2-line compile error on invalid syntax"] end subgraph STD["std::regex (Runtime)"] direction TB S1["Runtime Construction"] --> S2["~20,000 lines of assembly included"] end ```

When audience members ask whether malformed regexes cause the notorious template error cascades of C++03, Dusíková demonstrates that invalid syntax triggers a clean two-line error highlighting `regular expression syntax error` via `static_assert`. An audience member asks if all errors remain that concise; Dusíková clarifies that every syntax error detected by the parser is trapped in a `static_assert`.

Addressing questions about literal escapes, she confirms that users can utilize raw string literals to avoid double-backslash escaping (`R"(\d+)"`). When another attendee asks about MSVC support, she explains that while the original string literal operator template extension paper was rejected, the adoption of Class NTTPs in C++20 guarantees vendor support across all conforming toolchains going forward. CTRE targets full PCRE compatibility, making input validation cheap, maintainable, and blistering fast.

---

[11:20](https://www.youtube.com/watch?v=QM3W36COnE4&t=680s) Inside the Engine: Generic LL(1) Parser Architecture

Diving into the mechanics of transforming strings into C++ types, Dusíková explains:

> “I'm using generic LL(1) parser, which I write, to convert pattern of a string into a type.”

The parser accepts a PCRE-compatible grammar as a parameter, making the underlying engine adaptable to alternative regex dialects. The parser's output type encodes the pattern into an expression template (without evaluating expressions directly), which is subsequently evaluated against the input subject.

An LL(1) parser operates deterministically using an internal symbol stack: 1. It initializes with a distinct start symbol pushed onto the stack. 2. At every iteration, it inspects the top stack symbol alongside the current lookahead character from the input stream. 3. Based on the `(stack_symbol, input_character)` tuple in the parsing table, the parser executes one of four transitions: - Push a replacement sequence of symbols onto the stack. - Pop a symbol or push an empty string ($\epsilon$-transition). - Consume (pop) the matched character from the input and advance. - Reject the input immediately if no valid transition cell exists. 4. If the stack is empty exactly when the input stream is fully consumed, the parser successfully accepts the input.

Dusíková explains the challenge of implementing this formal table-driven automaton inside C++ templates where dynamic heap allocations are impossible. Having rewritten the library six distinct times, she restarted from scratch specifically while preparing this presentation and discovered an even cleaner implementation strategy.

The symbols manipulated on the parser stack are represented entirely as empty tag structs:

```cpp struct start_symbol {}; struct symbol_a {}; struct symbol_b {}; ```

Because these structs carry no runtime data or state, the entire compile-time parser operates purely through types and template metaprogramming transformations.

[14:49](https://www.youtube.com/watch?v=QM3W36COnE4&t=889s) Representing the LL(1) Table in Modern C++

```mermaid flowchart TD accTitle: LL(1) Parser Step Architecture accDescr: Decision flow showing how symbol matching, stack pushing, popping, accepting, and rejecting work via overload resolution.

subgraph InputState ["Input State"] InChar["Current Character"] StackSym["Top Stack Symbol"] end

subgraph Resolution ["Overload Resolution"] Match{"Compare Stack & Input"} Match -->|"Mismatch / Transition Rule"| Push["Push Symbols to Stack"] Match -->|"Same Symbol"| Pop["Pop from Stack & Advance Input"] Match -->|"No Matching Rule"| Reject["Reject (false)"] Match -->|"Empty Stack & Empty Input"| Accept["Accept (true)"] end

InputState --> Resolution ```

Dusíková explains how to encode an LL(1) parse table into C++. Rather than relying on massive run-time state tables, she turns to a foundational language mechanism: “And then, I will use the most modern C plus plus features. Function or overloading.” Overload resolution acts as the transition function for the automaton. If a rule specifies a non-terminal symbol and a particular lookahead character, the function overload returns a list of symbols to push onto the parsing stack. If the symbol on the top of the stack matches the input symbol, it pops the symbol and consumes the character. If no valid transition exists in the table, it rejects; and if both the stack and the input stream are simultaneously empty, the parser accepts. Because the logic operates strictly at the type level to drive the automaton, the functions do not require executable runtime bodies: “I'm sure this function doesn't need anybody 'cause it just need to know the pattern type, nothing else.”

The grammar itself is encapsulated in a dedicated `struct` passed as a template parameter to the parser algorithm. This architectural decoupling makes the parser engine generic. By supplying an alternate grammar definition, the exact same compile-time engine can parse JSON, regular expressions, or even esoteric languages like Brainfuck. A member of the audience asks whether the grammar supports backreferences. Dusíková clarifies the distinction between the stages: “We are talking about parsing the pattern, not yet about regular expression.” She reassures the audience that backreferences are indeed supported later by the library.

- An LL(1) parser table is encoded purely through C++ function overloading, relying on return types to decide whether to push, pop, accept, or reject. - The parse stack is represented using a compile-time `type_list` structure with functional operations: `push`, `pop`, and `top` (which returns an explicit empty stack symbol when exhausted). - Designing compile-time code requires shifting away from procedural idioms: “Compile-time programming starts very easy if you think functionally. You should forget about using variables, cycles, everything is a conversion and different function eroding.”

---

[18:04](https://www.youtube.com/watch?v=QM3W36COnE4&t=1084s) Handling Compile-Time String Inputs with Fixed String

To feed a literal regular expression into the compile-time parser, Dusíková relies on the `fixed_string` proposal championed by Jeff Snyder, who is present in the audience. Passing string literals into templates had historically been notoriously cumbersome, requiring macro workarounds or unpacking characters into variadic packs (`char_pack`). Using Snyder's technique, a `fixed_string` stores its contents directly inside an internal member array. This approach is substantially faster to compile than older compiler-specific extension hacks.

This mechanism is enabled by C++20 features: class types in non-type template parameters (NTTP), combined with template argument deduction placeholders. Instead of being restricted to integral values, pointers, or references, developers can use a literal class value directly as a template argument. Dusíková notes that `std::fixed_string` (or equivalent structural string wrappers) will likely become a standardized part of C++20.

```mermaid flowchart LR accTitle: Extracting Characters from Fixed String accDescr: Character retrieval checking bounds to return either a Terminal symbol or Epsilon.

Request["Character Request at Index N"] --> Check{"Index N < String Size?"} Check -->|"Yes"| Term["Return Terminal<char>"] Check -->|"No"| Eps["Return Epsilon"] ```

To drive the LL(1) parser, the implementation queries characters by index from the `fixed_string`: - If the requested position is within the bounds of the string length, the accessor returns a `terminal<char>` type wrapping that character. - If the index reaches or exceeds the string length, it returns an `epsilon` symbol, signaling the end of the input stream. - Using this specialized LL(1) formulation, parsing achieves linear complexity: “And actually, because I'm using special variant of LL one grammar, it's O N calculation.”

---

[20:27](https://www.youtube.com/watch?v=QM3W36COnE4&t=1227s) The Recursive Compile-Time Parsing Loop

Dusíková walks through the implementation of the recursive parser. The parser function is structured intentionally with verbose type aliases to illustrate that every stage evaluates strictly at compile time: “Everything is type here.” The entry-point function initiates parsing by taking a stack primed with the start symbol `S` along with the input `fixed_string`. At each step, it inspects the top symbol of the stack and the current input character, and delegates to the grammar overloads to determine the next action.

```mermaid flowchart TD accTitle: Compile-Time Move Function Transitions accDescr: Recursive move logic dispatching to push symbols, advance input, reject, or accept.

Move["parse::move(...)"] --> Action{"Table Decision"} Action -->|"Push Rule"| P["Push new symbols to stack & Recurse"] Action -->|"Terminal Match"| A["Pop stack, Advance index & Recurse"] Action -->|"Reject State"| R["Return false"] Action -->|"Accept State"| Acc["Return true"] ```

The transition logic is encapsulated inside a `move` helper function. When a rule specifies pushing symbols, `move` prepends the new types to the remaining stack and recurses. When a terminal matches the current input, it advances the string index by one character and pops the stack. If a reject state is encountered, it returns `false`; upon reaching the accept state, it returns `true`.

An audience member asks about compiler failure modes on invalid or excessively long inputs, and whether compilation times explode. Dusíková explains that if an input exceeds compiler recursion thresholds, it will stop around the compiler's depth limit (typically around 1,000 characters). However, for practical regular expressions, which are usually short (at most around 200 characters), this is well within acceptable boundaries. Because the grammar pops an input symbol at each step without backtracking, compile times do not blow up: “No, it's O N actually because it's a linear length of input.”

---

[22:38](https://www.youtube.com/watch?v=QM3W36COnE4&t=1358s) Generating Expression Templates via Semantic Actions

A parser that merely yields a compile-time `true` or `false` validates syntax, but it cannot execute a match. To generate an executable regular expression engine, the parser must construct an Abstract Syntax Tree (AST) in the form of an expression template: “We need to build an expression template from our parser. So, we need to somehow modify the parser to give some input other than just boolean.”

```mermaid flowchart TD accTitle: AST Construction via Semantic Actions accDescr: How parser encounters semantic action markers on the stack and modifies the subject AST.

Token["Parse Token / Hit Action Symbol"] --> CheckSym{"Is Top Symbol a Semantic Action?"} CheckSym -->|"Regular Grammar Symbol"| MoveDirect["Forward Subject Unmodified to move()"] CheckSym -->|"Semantic Action Symbol"| Mod["Call modify(symbol, subject)"] Mod --> NewSubj["Produce New Subject AST Type"] NewSubj --> Forward["Pass New Subject to Parser Continuation"] ```

To achieve this, Dusíková modifies the parser signature and the grammar: 1. **The Subject Type:** A new accumulator parameter, termed `Subject` (defaulting to an empty `type_list`), is threaded through the recursive parsing functions. 2. **Semantic Actions:** Special action symbols are embedded into the grammar production rules alongside regular non-terminals. These actions are tagged so the parser can detect them at compile time using C++20 Concepts. 3. **AST Construction:** When the parser encounters a semantic action marker on its stack, it intercepts the evaluation, pops the marker, calls a `modify(...)` function that updates the `Subject` type, and passes the resulting type downstream. 4. **Result Typing:** Instead of returning a `bool`, the modified parser's return type is deduced as `auto`, returning a composite result holding both a success flag and the fully constructed AST type.

---

[25:30](https://www.youtube.com/watch?v=QM3W36COnE4&t=1530s) Live AST Tree Transformations

Dusíková demonstrates the parse tree and its corresponding semantic actions using an interactive visual presentation. In the parse tree, nodes represent symbols on the stack expanding downward from the start symbol `S`. At the leaves, distinctive colored markers represent semantic actions.

When the parser encounters a character action, it pushes a character node into the AST stack. Subsequent characters are pushed onto the stack in sequence. When an operator such as a `+` (plus) is processed, it does not perform arithmetic: “In this case, it's not operation like numerical plus, it's take one char from stack and it wrap it into plus.” Similarly, sequence actions take the top two elements from the stack and wrap them into a `sequence<A, B>` node.

An audience member asks whether the AST shown on the slides corresponds to the raw de-mangled C++ type: > - **Audience Member:** “Yeah, so this is the thought of it. If we were to de-mangle the type, this is what we would actually see?” > - **Hana Dusíková:** “Yeah.”

Dusíková demonstrates live adjustments to regular expression strings on the slide, showing how the rendered output type dynamically adapts to inputs like `a+` or optionals. She tests playful examples like `(Jeff is best)?`, eliciting laughter from the audience. When an audience member notices that space characters do not display properly in a demo string, Dusíková jokes about slide generation bugs: > “Question was how it works with blank character. It's my mistake. I forgot to add quotes here. It's generated by JavaScript in this case. Library is right in C plus plus, the slides are not.”

---

[27:42](https://www.youtube.com/watch?v=QM3W36COnE4&t=1662s) Implementation of the Modify Transformations

The AST transformation functions (`modify`) are purely functional type-level transformations without runtime bodies. Dusíková walks through the signatures that construct each regex node:

- **Character Push:** Takes the current `Subject` type list and prepends a `char_tag<C>`: “Notice again, there is no body, just signature of a function. It's functional.” - **Optional (`?`):** Pops the top item from the stack, wraps it into an `optional<T>` template, and places it back onto the stack. - **Cycles/Repetitions (`+`, `*`):** Takes the top element, wraps it into a repetition node, and pushes it back. - **Sequences:** Pops two adjacent elements off the stack and packages them into a `sequence<A, B>`. Because stack operations reverse order, the function accounts for operand order: “Notice they are in another order because on stack they are in there. Only this one is at the top.” - **Extended Sequences & Alternations:** When additional elements are joined into existing sequences or alternations (`A | B`), overloaded variants take the existing composite node, append the new item, and return the combined type: “It's functional programming with C plus plus syntax.” - **Character Classes:** Specific actions map shorthand sequences like `\d` or `\w` directly to predefined symbol classes, such as `digit_class` or `alpha_class`.

Once parsing concludes, the AST output type is completely known to the compiler. It can be validated using static assertions (`static_assert`) to ensure that the pattern compiles to the exact expected AST type before transitioning to execution. Dusíková then introduces the next phase of the pipeline: taking this parsed expression template and evaluating it against runtime target strings using the `regex_match` function.

[31:29](https://www.youtube.com/watch?v=QM3W36COnE4&t=1889s) The Matching Engine and Stack-Based Type Lists

Hana Dusíková explains the bridge between the compile-time parser and the actual runtime evaluation. Once the regular expression pattern string has been verified using `static_assert`, the expression template tree is extracted directly from the parser as clean, fully evaluated types. The compiler has finished computing the structure, leaving no leftover parsing overhead for runtime. The top-level `match` function accepts the begin and end iterators of the subject string and is initialized with a stack-like list containing the parsed regular expression elements. Dusíková emphasizes the architecture of the engine: “Everything here is based on the type list.”

```mermaid flowchart TD accTitle: Compile-Time Parsing to Execution Flow accDescr: Diagram showing how a regex pattern moves from static validation to recursive stack matching.

subgraph CompileTime["Compile-Time Phase"] A["Pattern String Literal"] --> B["Parser & static_assert Validation"] B --> C["Extracted Expression Template Tree"] end

subgraph Runtime["Matching Phase"] C --> D["Top-level match(begin, end, type_list)"] D --> E{"Is type_list empty?"} E -- "Yes" --> F["Check if at end of input"] E -- "No" --> G["Pop symbol from stack & match against iterator"] G -- "Match succeeds" --> H["Advance iterator & recurse with tail"] G -- "Match fails" --> I["Backtrack or return false"] end ```

The underlying matching engine relies on a custom return type consisting of a forward iterator paired with a boolean success flag, needed to propagate intermediate positions. Dusíková walks through individual symbol handlers implemented via template function overloads: - **Empty stack terminal:** When the matching list is exhausted, the engine checks whether the current iterator has reached the end of the input; if so, it returns `true`, otherwise `false`. - **Character literals:** If the input is exhausted or the character at the current iterator does not match the expected literal, matching fails (`false`). Otherwise, it advances the iterator by one position and calls `match` on the remainder of the type list. - **Character classes (`\d`, `\w`):** Operates symmetrically to character literals by verifying that the input has not ended, checking character category membership (digits or alphabetic characters), and advancing the iterator upon a match. - **Sequences:** When a sequence node is popped from the top of the stack, the engine unwraps its inner elements, pushes them back onto the stack in order, and recurses inline without runtime abstraction penalties.

---

[34:09](https://www.youtube.com/watch?v=QM3W36COnE4&t=2049s) Alternation, Cycles, and Recursive Backtracking

Dusíková steps through the recursive rules for composite operators, beginning with optional expressions and alternations. An optional construct first attempts to match the inner content followed by the remaining stack; if that branch fails, it falls back to matching only the remainder of the stack behind the optional node. An audience member asks whether the return signature should explicitly show a `std::pair<Iterator, bool>`. Dusíková clarifies that it is an internal pair struct with implicit conversions tailored to fit on the presentation slide. For alternation (`head` | `tail`), the engine tries `head` concatenated with the trailing pattern; if that evaluation fails, it recursively evaluates the `tail` choices, returning `false` if it encounters an empty alternation branch.

The presentation then turns to repeating quantifiers (plus and star cycles). Dusíková notes a slide title mix-up between `+` and `*`, laughing as she explains the matching mechanics for unbounded loops. To implement greedy matching with backtracking, the engine evaluates the inner body of the loop followed by a special synthetic `end of cycle` marker. This marker records the iterator boundary every time an iteration completes. The engine then attempts to match the remainder of the overall pattern from that point forward; if the tail fails to match, the engine steps back to try additional iterations or terminate the cycle:

> “So depending on pattern your search can be quick or slow. So, you should think about your pattern as a code, not just write some regular expression which works. That's not what we are. We are C++ level experts, we should write great pattern.”

Dusíková points out that the simplified code shown on the slides omits captures, backreferences, and lookarounds to avoid overwhelming the audience: “I didn't want to scare you.” The full library, CTRE, implements extensive PCRE-compatible features including vector-based capture registries and lookaround assertions.

---

[37:53](https://www.youtube.com/watch?v=QM3W36COnE4&t=2273s) Runtime Benchmarks Against std::regex and PCRE2

To evaluate real-world performance, Dusíková benchmarks CTRE against `std::regex` and PCRE2 by feeding a large CSV file of almost 2 gigabytes into GCC- and Clang-compiled test harnesses.

```mermaid flowchart LR accTitle: Runtime Performance Comparison on 2GB CSV File accDescr: Bar chart representing runtime matching speed on Pattern 1.

subgraph RuntimeP1["Pattern 1 Runtime (GCC)"] CTRE["CTRE: 3.9 s"] EGREP["egrep: 50 s"] STD["std::regex (libstdc++): 55 s"] LIBCXX["std::regex (libc++): 21 min"] end ```

The initial benchmark yields striking differences: - `egrep`: 50 seconds - `std::regex` (GCC / libstdc++): 55 seconds - `CTRE`: 3.9 seconds - `std::regex` (Clang / libc++): 21 minutes

The audience breaks into applause at CTRE's speed, followed by laughter at libc++'s 21-minute run time, which Dusíková calls “embarrassing.” Marshall Clow quips from the audience, “The two samples doesn't seem consistent,” prompting Dusíková to test multiple patterns. An audience member asks whether the `std::regex_constants::optimize` flag was passed to libc++; Dusíková responds: “I tried, it didn't help.”

An audience member asks whether Dusíková considered converting patterns to a deterministic finite automaton (DFA) rather than using a backtracking non-deterministic finite automaton (NFA) / depth-first search. Dusíková confirms she has worked on DFA generation but points out the fundamental limitation: “Problem with deterministic finite state machine is that is hard to implement captures.” For patterns requiring capture groups, pure DFAs cannot easily track submatch boundaries, though hybrid approaches remain an active area of investigation. On a backtracking-heavy pattern, PCRE2 edges out CTRE slightly, while libc++ balloons to 27 minutes—and on the first test run, `std::regex` hung entirely, forcing her to kill the process.

---

[43:03](https://www.youtube.com/watch?v=QM3W36COnE4&t=2583s) Compile-Time Costs and Best Practices

Dusíková moves to compile-time benchmarks, measuring the raw time needed to compile translation units with identical header sets (excluding link time). Counterintuitively, `std::regex` takes longer to compile than CTRE under Clang, and is slower still under GCC. Suspecting that the compiler's optimization passes were getting bogged down processing `std::regex` template machinery, Dusíková disabled optimizations, but the compilation time gap persisted:

> “So, sometimes compile-time programming is even quicker than ordinary programming. It's counterintuitive, but it is.”

Bryce Adelstein Lelbach and other attendees probe how regular expression complexity scales during compilation. Dusíková shares concrete performance metrics from her MacBook: - Distinct regular expressions add approximately 200 milliseconds of compile-time overhead each (e.g., five unique expressions in a translation unit cost roughly 1.0 second). - Duplicate expressions in the same translation unit incur virtually zero additional compile time because template instantiations are cached by the compiler. - Compile-time parsing complexity scales linearly, $\mathcal{O}(N)$, with the length and complexity of the regular expression string.

Wrapping up the technical presentation, Dusíková highlights key takeaways for modern meta-programming: - Heavy reliance on recursion and overload resolution provides an expressive, highly optimizable pipeline. - Pure functional programming techniques keep compile-time logic maintainable: “You should forget about variables if you do compile-time programming because it just gives you more complexity.” - Always inspect compiler assembly to ensure the optimizer flattens recursive template abstractions into efficient machine code.

The session transitions to the audience Q&A, with an attendee asking whether compile-time and runtime regular expression engines can share a unified implementation without duplicating logic, and requesting that annotated example code be published.

[46:53](https://www.youtube.com/watch?v=QM3W36COnE4&t=2813s) The Vision for `std::regex` and Live Demo on Compiler Explorer

Hana Dusíková reflects on the ultimate goal of compile-time regular expressions, expressing hope for future C++ revisions. She suggests that once all required language machinery is fully `constexpr`, developers should not need a specialized third-party library; standard regular expressions should handle compile-time evaluation natively. As Dusíková puts it: “So, this is just experiment and it works pretty great, but in future, we should use `std::regex` and it should be great if someone care.” The audience laughs at her dry aside about whether anyone will actually take the initiative to fix and modernize `std::regex`.

To show how accessible the library is, Dusíková opens Compiler Explorer (Godbolt) in her browser, enlarges the view, and shows the audience how to select CTRE version 2 from the library menu. She types out a live example matching the literal `"abc"` using `ctre::match` against a `std::string_view`. When compiling unoptimized code, the generated output is massive, but once compiler optimizations are turned on, the entire matcher collapses into a tiny footprint. She points out that with optimizations enabled, it compiles down to about 24 lines of assembly, eliciting laughter from the audience.

[48:56](https://www.youtube.com/watch?v=QM3W36COnE4&t=2936s) Expression Size Limits and Comparisons to Boost

The Q&A session opens with an attendee asking about limits on regular expression size. Dusíková clarifies that currently the practical ceiling is roughly 1,000 characters, constrained primarily by compiler recursion depth limits. When asked if she has formal benchmarks measuring this boundary, she explains that while she ran benchmarks, she omitted them from the presentation to avoid slide overload, but she plans to include them in the documentation or share them afterward.

Another attendee asks whether CTRE has been benchmarked against Boost.Regex or Boost.Xpressive, and how its parser generator compares to Boost.Spirit X3. Dusíková responds candidly about her lack of extensive background with Boost, drawing laughs when she admits: “Unfortunately, I'm procrastinator so I finished my slide yesterday.” She promises to run comparative benchmarks against Boost libraries and publish the results.

[50:05](https://www.youtube.com/watch?v=QM3W36COnE4&t=3005s) Functional Style, Grammars, and Compile-Time Matching

An audience member asks about the fundamental limits of translating functional-style techniques into compile-time C++, wondering whether hard technical boundaries prevent broader applications. Dusíková explains that the primary obstacle is input length. Because compile-time evaluation must operate without standard heap allocations within recursive structures, parsing massive inputs like large JSON files is impractical. Furthermore, the parser design relies on an LL(1) grammar, requiring grammars free of left recursion, though an LR or LALR approach could theoretically be built under different trade-offs.

```mermaid flowchart TD accTitle: Compile-Time vs Runtime Execution Path in CTRE accDescr: Flow diagram showing how input regex strings are processed through constexpr evaluation into compact native machine instructions.

subgraph CompileTime["Compile-Time Pipeline"] A["Regex String Literal (e.g. 'abc')"] --> B["LL(1) Parser Engine (constexpr)"] B --> C["Finite Automaton AST"] C --> D["Inline constexpr Matcher Functions"] end

subgraph Evaluation["Matching Evaluation"] D -->|"String literal input"| E["Pure Compile-Time Match (constexpr bool)"] D -->|"Runtime std::string_view"| F["Assembly Matcher (~24 lines optimized)"] end ```

Another attendee asks for clarification regarding how CTRE executes matching at compile time versus runtime, noting they were confused by how the matching engine could handle both without separate implementations. Dusíková clarifies that every matching function is marked `constexpr` and avoids dynamic memory allocations entirely. Because no stateful heap allocations occur, the exact same functional traversal can execute purely during compilation when passed compile-time constants, or compile down into tight machine code when passed a runtime `std::string_view`. She mentions that on some slides the `constexpr` keyword was omitted purely for visual brevity, and reassures the audience that her full slides would be uploaded online within an hour.

[52:00](https://www.youtube.com/watch?v=QM3W36COnE4&t=3120s) Trampolining, Translation Units, and Future Grammars

Odin Holmes steps up to praise Dusíková's work, declaring: “First of all, this is the awesomest thing that anyone's done with meta programming ever.” He then asks whether compiler recursion depth limits could be bypassed using a trampolining technique. Dusíková admits that she is unfamiliar with trampolining, prompting Holmes to offer to discuss the idea with her offline.

The discussion then covers practical build-time management and grammar complexity: - **Extern templates and translation units:** An attendee asks if `extern template` can prevent slow re-compilations across multiple translation units. Dusíková explains that developers can wrap the regular expression match inside a normal wrapper function defined in a single translation unit, ensuring the pattern compiles only once and keeps overall project build times low. - **Parsing more complex languages:** Another attendee asks whether grammar complexity itself poses a barrier, or if an ambitious developer could write an `eval()` or a full C++ parser using these techniques. Dusíková notes that grammar complexity does not hurt performance because the grammar is deterministic; the only true constraint remains the length of the input. She quips: “If you are crazy enough, yeah.”

[53:48](https://www.youtube.com/watch?v=QM3W36COnE4&t=3228s) Comparison to PCRE JIT and Parser Generators

The session concludes with questions comparing CTRE to established industry tools. An attendee asks why PCRE (Perl Compatible Regular Expressions) demonstrates such fast execution. Dusíková explains that PCRE is an exceptionally mature codebase, and modern versions integrate a Just-In-Time (JIT) compiler that translates regexes directly into native machine instructions at runtime, achieving very high speeds.

A final question notes that CTRE's compile-time automaton generation strongly resembles the approach taken by classic tools like Flex or Lex, and asks if Dusíková has benchmarked her engine against Lex-generated state machines. Dusíková brings the room to laughter with her honest reaction, stating: “I didn't benchmark it against Flex or Bison because I am scared of them.” The attendee accepts the answer with an amused "Fair enough," and the talk concludes to enthusiastic audience applause.

## Notable quotes > [43:03](https://www.youtube.com/watch?v=QM3W36COnE4&t=2583s) You should forget about variables if you do compile-time programming because it just gives you more complexity. — Hana Dusíková

> [00:00](https://www.youtube.com/watch?v=QM3W36COnE4&t=0s) So, if you have application installed on million of mobile phones, each mobile phone, every time, do the same calculation. Why? It should be constexpr. It should be pre-calculated. — Hana Dusíková

> [00:00](https://www.youtube.com/watch?v=QM3W36COnE4&t=0s) No one will use interpret of Python in their code to match string, but we are doing it with regular expressions. — Hana Dusíková

## Mentioned Hana Dusíková, Avast, WG21, Bryce Adelstein Lelbach, Marshall Clow, Jeff Snyder, Richard Smith, Odin Holmes, CTRE, std::regex, PCRE, PCRE2, GCC, Clang, MSVC, Compiler Explorer, Boost.Regex, Boost.Xpressive, Boost.Spirit, Flex, Bison, egrep

## Video description http://CppCon.org — Presentation Slides, PDFs, Source Code and other presenter materials are available at: https://github.com/CppCon/CppCon2018 — I will present a library that utilizes a feature of C++20 to build regular expressions from compile-time strings. This is a novel approach that doesn't have ordinary disadvantages of other regular expression implementations like having to use a linked library or a run-time cost of parsing and interpreting an internal finite machine.

You will see implementation details of the library and problems I have run into during its writing. In the last part of the talk, I will compare other implementations of regular expression engines and show compiled code in Compiler Explorer. — Hana Dusíková, Avast Senior Researcher

Hana is working as a senior researcher in Avast Software. Her responsibility is exploring new ideas and optimizing existing ones. She also propagates modern C++ techniques and libraries in internal techtalks and gives talks at local C++ meetups.

She studied computer science at Mendel university and subsequently taught several courses there, including: Data Structures, Computability and Complexity, and Formal Languages and Automata. — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com *-----* *--* *-----*

[Source](https://www.youtube.com/watch?v=QM3W36COnE4)

中文简报

CppCon 2018：Hana Dusíková 谈“编译期正则表达式” Hana Dusíková 介绍了开源库 CTRE。该库利用由 C++ 函数重载和类非类型模板参数（NTTP）驱动的内部 LL(1) 解析器，在编译期解析正则表达式字符串。通过将模式验证与抽象语法树（AST）构建完全转移到 constexpr 模板元编程中，该引擎能生成紧凑的机器码，并保证线性的编译期解析复杂度，且无需付出运行时构造函数成本。针对 std::regex 和 PCRE2 的实际基准测试显示，它在大型数据集上实现了显著的运行时提速，同时避免了模板错误级联与二进制体积膨胀。Dusíková 最后展示了 Compiler Explorer 现场演示，解释了纯函数式、免堆内存分配的匹配流水线如何让同一套代码既能在编译期校验字符串，又能编译为高度优化的汇编以供运行时求值。编译期正则表达式（CTRE）利用 C++20 类非类型模板参数（NTTP）纯粹在编译期解析正则表达式字符串并构建抽象语法树，消除了运行时解析开销。 (5:20) 在针对约 2 GB CSV 文件的大规模匹配基准测试中，CTRE 在 3.9 秒内完成执行，性能优于 egrep（50 秒）、GCC libstdc++ std::regex（55 秒）以及 Clang libc++ std::regex（21 分钟）。 (37:53) CTRE 编译正则表达式的时间相对于模式长度呈 O(N) 线性复杂度，在现代硬件上每个独特模式约增加 200 毫秒，且仅生成 24 至 98 行优化汇编代码，而 std::regex 链接的代码量约为 20,000 行。 (43:03) 由于所有匹配函数均为 constexpr 且完全避免动态堆内存分配，完全相同的函数式遍历既能在编译期校验字符串，也能编译为原生机器码用于运行时的 std::string_view 求值。 (50:05)

Reading summary

Hana Dusíková argues that static regular expressions should be parsed and compiled ahead of time rather than repeatedly constructed at runtime. Through her Compile Time Regular Expression (CTRE) library, she demonstrates that modern C++ template metaprogramming can shift regex parsing to compile time, drastically reducing binary size, eliminating runtime parsing overhead, and outperforming standard library implementations. Runtime Inefficiencies of Standard Regular Expressions (0:00) Traditional C++ regular expressions rely on runtime engine construction, where functions such as std::regex_match require instantiating an engine object that dynamically parses pattern strings and builds state machines. Dusíková emphasizes that building deterministic finite automata involves exponential-complexity algorithms. When applied to fixed strings inside hot loops or distributed client applications, repeating this initialization at runtime wastes significant computing cycles and risks severe performance bottlenecks. Standard library implementations also introduce heavy binary bloat. In a benchmark extracting comma-separated values, Dusíková demonstrates that std::regex pulls in an extensive runtime apparatus that emits nearly 20,000 lines of assembly. By contrast, an equivalent compile-time implementation generates only 98 lines. She also notes practical usability drawbacks in the standard library, such as the historical lack of direct std::string_view support, which forces developers to manage manual iterator pairs. Architecture of the Compile-Time LL(1) Parser (11:20) To parse regex patterns entirely at compile time, CTRE uses a generic LL(1) parser that converts string patterns into C++ expression template types. Operating deterministically with an internal symbol stack, the parser executes transitions—pushing symbols, popping tokens, advancing input, or rejecting invalid syntax. Because dynamic memory allocation is unavailable during template metaprogramming, Dusíková represents stack symbols as empty tag structs that manipulate types rather than runtime state. The parser encodes its state transition table using standard C++ function overloading, relying on return types to decide grammar transitions without executing function bodies. Input patterns are ingested using C++20 Class Non-Type Template Parameters (Class NTTPs) and fixed-string wrappers that store characters in internal member arrays. This design processes input characters deterministically, achieving linear compile-time parsing complexity (O(N)) without backtracking explosions. AST Generation and Type-Level Semantic Actions (22:38) Syntax validation alone is insufficient to execute matches; the compile-time parser must output an Abstract Syntax Tree (AST). CTRE accomplishes this by threading an accumulator subject type through the recursive parser loop and embedding semantic action markers into the grammar rules. When the parser encounters an action symbol, it intercepts execution, pops the marker, and invokes a modify function overload to transform the accumulator. These modify functions operate purely functionally without runtime bodies, wrapping elements into composite AST structures such as sequence, optional, and repetition nodes. If a developer provides an invalid regular expression, the parser halts at compile time via static_assert, generating concise two-line error messages instead of verbose template error cascades. The fully resolved AST is completely known to the compiler before binary execution begins. Matching Execution and Benchmark Performance (37:53) Runtime evaluation traverses the compiled expression template using recursive function overloads that match characters and character classes against input iterators. Because pure deterministic finite automata cannot easily track submatch boundaries for capture groups, CTRE employs a backtracking approach with synthetic end-of-cycle markers to support greedy repetition and PCRE-compatible features like captures and lookarounds. In runtime benchmarks scanning an approximately 2-gigabyte CSV file, CTRE completed execution in 3.9 seconds, compared to 50 seconds for egrep, 55 seconds for GCC's std::regex, and 21 minutes for Clang's libc++ implementation. Benchmarks measuring compilation cost indicate that each unique regular expression adds roughly 200 milliseconds of compile time on tested hardware, while repeated instances of identical expressions incur negligible cost due to compiler template memoization. Constraints, Dual-Mode Execution, and Standards Vision (46:53) Because CTRE's matching routines are marked constexpr and avoid dynamic memory allocations, the identical codebase supports dual execution paths: patterns can validate string literals strictly during compilation or compile into lean native assembly (collapsing to roughly 24 lines under optimization) when evaluating runtime std::string_view inputs. Dusíková notes that current inputs face a practical upper boundary of approximately 1,000 characters due to compiler recursion limits, though typical patterns rarely exceed 200 characters. Dusíková envisions compile-time evaluation eventually becoming the baseline standard for C++, suggesting that developers should not require standalone third-party libraries once language-level constexpr features mature. She argues that future revisions of the ISO C++ standard library should modernize std::regex to evaluate static patterns ahead of time natively. Dusíková demonstrates that functional, type-level compile-time programming can eliminate the performance trade-offs historically associated with regular expressions in C++. Unresolved questions include whether compiler recursion limits can be bypassed via techniques like trampolining, and whether the ISO C++ committee will ultimately modernize std::regex to support native compile-time execution.

精炼阅读摘要

捷克研究员 Hana Dusíková 提出了编译期正则表达式库（CTRE），主张将固定正则模式的解析与自动机构建转移至编译阶段完成，以消除运行期重复构造的高额开销，并在性能与二进制体积上大幅超越标准的 std::regex。传统正则的运行期瓶颈与编译期范式转换 (0:00) 在传统 C++ 编程中，使用 std::regex 时通常需要在运行期通过构造函数解析模式字符串并构建内部状态机或语法树。Dusíková 指出，构建确定性有限自动机（DFA）本身是一个指数级复杂度的算法，在每次程序运行或安装在数百万台移动设备上时重复进行完全相同的计算是不合逻辑的。传统的手写状态机代码量庞大、极易出错，而 Flex 或 Bison 等第三方代码生成工具又引入了复杂的构建流程和跨平台移植难题。 Dusíková 认为，对固定不变的正则模式应该像对待编译型 C++ 代码一样处理，实现零运行期解析开销与最大吞吐量。基于 C++20 的非类型类模板参数（Class NTTP，前期通过 N3599 字符串字面量运算符扩展兼容）以及 Jeff Snyder 提出的 fixed_string 技术，CTRE 允许开发者直接将正则表达式写在模板参数中，例如 ctre::match<"[a-c0-9]+">(subject)。模式语法错误能够在编译期通过 static_assert 以简短的两行错误信息直接拦截，彻底避免了 C++ 常见的冗长模板报错。基于纯函数式重载的通用 LL(1) 解析引擎 (11:20) CTRE 的核心是一个运行在类型系统的通用 LL(1) 解析器，该解析器将正则表达式字符串转换为表达式模板（Expression Template）抽象语法树（AST）。由于编译期缺乏常规的动态堆内存分配，Dusíková 采用函数重载来对 LL(1) 转换表进行编码。解析栈由包含空标签结构体（如 struct symbol_a {};）的编译期类型列表（type_list）实现，每一步通过重载决议判断是压栈、出栈、匹配终结符、拒绝还是接受。所有转移函数均无需运行时函数体，完全依靠返回值类型驱动逻辑。为了生成可匹配的执行引擎，Dusíková 在文法推导规则中嵌入了语义动作标记。当解析栈遇到特定语义动作时，解析器调用无函数体的 modify 函数对累积的 Subject AST 类型进行转换，例如将栈顶字符包装为 char_tag、将重复修饰符转化为 repetition 节点或包装为 sequence<A, B>。这一解析过程具备 O(N) 的线性复杂度，不仅支持 PCRE 兼容文法，其抽象的文法解耦设计理论上还能扩展解析 JSON 等其他结构化文本。栈驱动匹配引擎与针对 std::regex 的性能对比 (31:29) 在匹配阶段，经过 static_assert 验证后的 AST 类型直接传入顶层 match 函数。该函数接收待匹配字符串的迭代器范围，并利用类型列表展开为递归遍历。匹配引擎内部采用特化的迭代器与布尔状态对来传播状态：字符字面量与字符集（如 \d、\w）在迭代器处验证并递归处理尾部；可选分支与多选（|）执行回溯尝试；循环结构（+、*）则通过记录边界的特殊周期结束标记实现贪婪回溯。在针对近 2GB CSV 数据文件的基准测试中，CTRE 的运行吞吐量展现出对标准库的压倒性优势。在 GCC 环境下处理特定模式时，egrep 耗时 50 秒，GCC 的 std::regex（libstdc++）耗时 55 秒，而 CTRE 仅需 3.9 秒；Clang 的 std::regex（libc++）耗时甚至高达 21 分钟。在代码生成层面，解析 CSV 姓名的 CTRE 实现仅生成 98 行高度优化的精简汇编（在 Compiler Explorer 上简单模式甚至可低至 24 行），而 std::regex 由于链接了庞大的运行时引擎，生成了近 20,000 行汇编代码。编译成本、边界限制与应用最佳实践 (43:03) 针对使用模板元编程导致编译过慢的担忧，基准测试显示 std::regex 在 Clang 和 GCC 下的纯编译耗时反而普遍高于 CTRE。Dusíková 在 MacBook 上的测试表明，每个独立的不同正则表达式大约增加 200 毫秒编译耗时，且由于编译器具备模板实例化缓存机制，同一编译单元内的重复模式几乎不增加额外开销。不过，CTRE 目前实用的正则长度上限约为 1,000 个字符，其硬性瓶颈主要受限于编译器的递归深度限制，而非文法本身的复杂度。针对多编译单元的项目构建管理，Dusíková 建议将正则匹配调用封装在单个翻译单元的常规包装函数中，以避免多处重复编译。此外，CTRE 的所有匹配函数均带有 constexpr 修饰且无堆内存分配，这意味着相同的代码既可在传入编译期常量时于编译期完成计算，也可在传入 std::string_view 时被优化编译为高效的原生机器指令。 Dusíková 强调 CTRE 是一次将元编程技术推向极值的探索，最终目标是期望未来的 C++ 标准库能够吸收这种 constexpr 原生编译期设计，使 std::regex 具备零开销与高吞吐能力；然而，诸如支持捕获组时纯 DFA 难以记录子匹配边界的矛盾、编译器深度递归约束以及超长文本编译期处理等难题，仍有待未来语言演进或混合技术进一步解决。

Source quotes

[43:03] Hana Dusíková: You should forget about variables if you do compile-time programming because it just gives you more complexity. [0:00] Hana Dusíková: So, if you have application installed on million of mobile phones, each mobile phone, every time, do the same calculation. Why? It should be constexpr. It should be pre-calculated. [0:00] Hana Dusíková: No one will use interpret of Python in their code to match string, but we are doing it with regular expressions.

Original transcript

[0:00] - Good morning to you all. [0:03] I'm so glad you are here and I'm so excited to stay here [0:08] and if someone wants to switch with me, okay. [0:12] Anyway, I'm going to talk about regular expressions. [0:16] My name is Hana Dusikova, [0:18] I work in Avast, I live in Brno, Czech Republic or Czechia, [0:23] I'm organizing a local Avast C plus plus meetup, [0:26] and I soon will be Czech national body for WG 21, [0:31] and I'm an amateur photographer [0:33] and ending in last week, I stop hiking. [0:37] (people laughing) [0:40] Bryce will tell you more. [0:42] Okay, let's talk about regular expressions. [0:47] What can I do with a regular expression? [0:49] There are three things you can do with regular expression: [0:53] match the subject against a pattern, [0:57] you can extract the content of your subject, [1:02] or you can modify parts of your subject, [1:05] depends on algorithm expression used. [1:09] You can do these things. [1:13] For example, matching. [1:15] This can be done with a definitive machine, [1:17] a determinate definitive machine, [1:19] which is much quicker than that search [1:22] for extracting of content. [1:26] Okay, regular expression looks like this pattern, [1:29] A B C or zero to nine plus, [1:33] which match correctors A B C or zero to nine. [1:39] There are many dialects, ECMA, Perl, PCRE, name it. [1:45] They are slightly different in more advanced feature, [1:48] but the basics are usually the same. [1:54] Okay. [1:55] How can I use regular expression in C plus plus? [1:57] As everything else, some parameter for your constructor, [2:03] the constructor is called, build something, [2:05] the constructor will build something, [2:08] and then equal some function which will match your input. [2:11] In this case, I use a pair of iterators [2:14] because instead of library there is no support [2:17] for string view and std: :regex. [2:21] In C, it's exactly the same. [2:24] There is a pattern, there is a constructor, [2:28] and there is some matching. [2:31] So, pattern is the same in almost every language. [2:36] You build your grammar expression, you match against it. [2:40] Never do building and matching in same function [2:43] because it's slow. [2:45] So, what's going in the constructor? [2:47] You are parsing the pattern, which can be hard for some, [2:53] and you are building a data-structure, tree, table, [2:57] depends on your algorithm, [3:00] and the calculation are very expensive, [3:05] depends on parsing, algorithm, and what you are using. [3:09] If you are trying to build the deterministic finite machine, [3:13] it's exponential, complex algorithm to create the machine. [3:20] How can you avoid to calling a constructor? [3:23] You can do same thing differently. [3:26] You can write your deterministic [3:27] finite data model by yourself. [3:29] It's like a few hundred lines of code. [3:32] Some can do, some cannot, but it's hard to maintain [3:36] and you can easily introduce an error. [3:40] Also, you can use external utility like Flex Bison [3:44] or something which build the machine for you, [3:48] but it gives you much more complexity [3:51] for your pipeline and it's not portable to other platforms, [3:55] so no one want to use it. [3:58] Okay, really? [4:00] Is there no other way? [4:01] For example, battle. [4:03] Support and language for irregular expressions. [4:08] C plus plus don't, but there is a way [4:11] how to do it differently. [4:15] Because this talk is not about regular expression, [4:17] this talk is about compile time regular expression. [4:20] We can move the work of the constructor [4:23] to compile that in compile time [4:26] because each time constructor is called, [4:29] output is the same. [4:31] So, if you have application installed [4:33] on million of mobile phones, [4:34] each mobile phone, every time, do the same calculation. [4:37] Why? [4:38] It should be called expert. [4:39] It should be pre-calculated. [4:43] Okay. [4:46] What do I want? [4:47] I want to work with a regular expression as with a code [4:50] because it's just old. [4:51] No one will use interpret of Python in their code [4:54] to match string, but we are doing it [4:58] with regular expressions. [5:02] Also, I don't want to pay any runtime cost [5:04] for parsing the pattern. [5:08] It's nonsense. [5:09] And I want my regular expression to be quick as possible [5:12] with zero overhead, as everything in C plus plus should be. [5:17] Okay. [5:20] I want this. [5:22] Is there someone who wants same thing? [5:26] Raise your hand. [5:28] Okay. [5:31] Everyone, understand the syntax? [5:33] You have pattern and you have your subject. [5:36] That's easy. [5:38] It's readable, it's easy mountable, [5:41] and goes behind, it's utterly simple. [5:46] This is actually possible in C plus plus 20 [5:48] with class non-type template parameters, [5:51] which is always merged into their draft, [5:54] but no library support for this yet. [5:58] Maybe. [6:02] And I linked to my library, it's called CTRE, [6:06] Compile Time Regular Expression, which works same. [6:10] But there is no compiler which support [6:15] non-type template parameters yet, [6:17] so there is no compiler. [6:20] It's just able to compile it. [6:22] But I use feature that's macro, [6:24] so my tech compiler will be here, it will work. [6:28] Until then, you can use Clang or UCC [6:31] with string template parameters multiplied... [6:37] Template and string, literals [6:40] and it's the same thing only a little different [6:45] and it's based on N three five nine nine extension [6:49] by Richard Smith and it's in GCC from version four [6:55] and Clang, I don't know. [6:58] Okay. [7:00] Example, Constexpr. [7:02] You can test your expression in compile time. [7:06] Your program will not compile or rejects, [7:09] doesn't match what you want. [7:15] There is another example. [7:17] You can extract something from the string [7:20] during compile time and check it. [7:28] You can extract a name from CSV-like input [7:31] with simple pattern and get first capture [7:37] and second capture and I return it. [7:39] I'll say this. [7:44] You can extract a date from string [7:48] with extraction bindings. [7:52] Year, month, day. [7:55] It's that easy. [8:00] But this must be horrible assembly, you say. [8:04] Not really. [8:05] (people laughing) [8:07] There is an example of code. [8:10] It's 98 lines of assembly for the example [8:12] with first and last name. [8:16] That's all. [8:20] I don't need you to read it, but it's that simple. [8:23] (people laughing) [8:27] In theory, optimizer should see your intent [8:31] even with strategics. [8:33] So in theory, the compiler should emit same assembly [8:36] for std: :regex. [8:39] Unfortunately, it doesn't. [8:42] There is an example. [8:43] It's almost 20,000 lines of code. [8:46] (people laughing) [8:49] Complete std: :regex information is included [8:53] for some reason. [8:56] Okay. [8:59] What about errors, you say? [9:01] If I write wrong expression, [9:06] you can expect very long errors [9:08] like you are used to C plus plus oh three, [9:11] but really it's two lines. [9:15] It will give you regular expression syntax error. [9:21] In future, I can give you more, but not yet. [9:27] (man speaking in audience) [9:28] Sorry? [9:29] (man speaking in audience) [9:31] I don't understand. [9:33] - [Man] Does every error do that? [9:36] - Yeah. [9:37] Question was is every error is to length? [9:42] Every syntax error of regular expression [9:45] is catch by a parser and it's static assert currently. [9:48] I tried use tonight, but it gives me three or four lines. [9:52] So, this is a little better. [9:56] There is the main error. [10:00] Okay, question? [10:01] - [Man 1] Looking at some of the previous examples [10:04] with double back slashes in them, [10:06] can a user-defined literals work with loss frame literals? [10:11] - Question is if I can use literals. [10:15] Yes, you can. [10:16] - [Man 1] Okay. [10:16] - You can unique literals, [10:19] you can use all literals as you want. [10:20] It's up to the language. [10:24] Okay, so compile time... [10:26] Another question? [10:28] - [Man 2] You mention just the same plan [10:30] with the (speech muffled) [10:31] - Question is if there is visual studio support. [10:35] It's not... [10:36] It's exception, which was superpose of the paper, [10:39] the language, it was rejected, [10:41] but there is another paper which was already [10:44] included in the draft, so NC plus plus 20 [10:46] we will still be able to support this library. [10:51] Okay. [10:53] Compile time regular expression library is easy to use [10:56] because it's use familiar [10:59] and known regular expression syntax. [11:01] Actually, I am aim to be PC Arri compatible. [11:06] It's perfect for checking your inputs [11:07] because it's cheap for you and easy to maintain. [11:11] Also, emits nice assembly [11:14] and about performance, we will talk at the end of the talk. [11:20] Okay, the parser. [11:23] That was the boring part of this talk. [11:24] I want to show you how it works, to give you something. [11:29] Maybe you are saying it's crazy [11:32] and I do not understand. [11:34] Right, it's not very simple [11:39] and all examples are very simplified [11:41] and they are different than the library code [11:43] because library codes do much more things [11:45] than the examples here. [11:49] How does it work? [11:51] I'm using generic LL one parser, which I write, [11:55] and to convert pattern of a string into a type. [12:01] The parser uses a provided PCRE compatible grammar [12:05] of the parameter, so we can give it different dialects [12:11] of regular expression rather easily. [12:14] Output type encodes the parser and goes the pattern [12:19] into expression template, but without expressions. [12:24] And then last part is evaluation of the expression template [12:28] against your subject to match it. [12:33] Okay. [12:34] To get you up to speed with LL one parser, [12:38] how LL one parser works. [12:40] It starts with a start symbol on the stack. [12:44] There is some sort of a stack in the code. [12:47] On every step, it pops one symbol from the stack [12:50] and checks current character at the input. [12:55] Based on the pair of the symbol and character, [12:57] it decides to push a string of symbols to the stack, [13:02] it pop a character from the input, move to the next, [13:07] or reject for input. [13:10] At the end, when there is an empty stack, [13:12] empty input, it accepts. [13:17] This is simplified or expression grammar for LL one. [13:23] On the top you can see symbols from input, [13:25] on the left you can see symbols from the stack, [13:28] and if these cells are selected, [13:35] I push something on the stack. [13:37] If these cells are selected, I will push empty string. [13:41] If I match these details, I pop input [13:45] and move to the next character. [13:47] If I match the empty one, I will reject [13:51] and if I match the right bottom one, I will accept. [13:58] Okay. [14:00] How can I write it in C plus plus? [14:02] Because it's stable, it's formal, [14:05] especially if you want to do it during compile time. [14:07] You cannot allocate anything. [14:10] So, it's not really hard, only for beginners, [14:14] and then I found... [14:16] Actually, write the library six time [14:19] and I was preparing for this talk, [14:21] I decide to write it again from scratch and make notes [14:25] and I found even better way than in previous version. [14:31] I need to somehow use symbols on the stack. [14:37] For me, it's just at this track [14:38] and I need to mark start symbol for the parser. [14:43] That's all. [14:44] These stacks are empty. [14:46] There is nothing else in them. [14:49] How can I represent the LL one table in C plus plus? [14:53] This is formal definition, semi-formal definition [14:57] how the function of LL one works. [15:02] I need to use some struct to be able to give [15:06] the grammar other parameter. [15:10] And then, I will use the most modern C plus plus features. [15:17] Function or overloading. [15:20] So, if there's symbol and some character, [15:24] I will give list of symbols, [15:26] which I will going to push to stack. [15:29] If that is same symbol on the input and on the stack, [15:32] I will pop it. [15:35] If there is a sync, if there is no other batch, [15:39] I will reject, and if there is empty stack [15:42] and nothing on input, I will accept. [15:46] I'm sure this function doesn't need anybody [15:49] 'cause it just need to know the pattern type, nothing else. [15:57] Yeah. [15:59] The decision is based on the function overload resolution [16:01] and pattern type is the value for my automata. [16:11] Continue. [16:12] Why is the grammar on the struct? [16:14] I want to give the grammar to parser as algorithm, [16:18] so I giving the PC grammar in this case whatever I want [16:23] and if I prepare grammar, I can parse JSON, [16:29] I can parse regular expression. [16:32] It might help, you can find a parser for Brainfuck. [16:39] Yeah, there is a grammar. [16:44] How do I implement the stack? [16:46] I need something for stack, so I use a type list. [16:49] A question? [16:51] - [Man 3] Going back to the grammar, [16:52] does it support he back references? [16:55] - We are talking about parsing the pattern, [16:59] not yet about regular expression. [17:01] And sorry, question was if it support back references? [17:04] We will get to it. [17:06] The library does support back references. [17:10] Okay. [17:12] Type list. [17:14] That's my type list. [17:16] And few function which might be [17:19] on the type list, also stack. [17:21] I can push something to my list, [17:25] it's the first parameter, and get another list, [17:30] which is my stack of the output. [17:32] It's functional programming, actually. [17:34] I can pop something from the stack. [17:37] I can look at the top of my stack [17:41] and it is empty, it gives me symbol, empty stack. [17:49] Compile-time programming starts very easy [17:51] if you think functionally. [17:52] You should forget about using variables, cycles, [17:57] everything is a conversion and different function eroding. [18:04] Okay, how do I implement input string? [18:07] Actually, borrow this from Jeff Sneider's proposal. [18:11] He's here? [18:13] Hi. [18:15] Which is fixed string. [18:18] Which store content in member, [18:25] which is much quicker than chart box [18:28] of the extension I'm using for older version of compilers. [18:34] There is template deduction rule [18:36] which it allows template deduction place holder [18:41] in template parameter. [18:51] And template parameter, in this case, [18:56] because a class entity in non-type template parameters [18:58] allows you to use almost any type other template argument. [19:04] Not type, value. [19:09] And std: :fixed string will be probably part [19:12] of C plus plus 20, depends. [19:17] Okay. [19:18] How do I use the input string? [19:19] I need to extract terminal or epsilons from fixed string. [19:23] Fixed string is used like this. [19:25] I just place string there as the argument for this parameter [19:33] and if position of my request that char [19:39] is less than size of string, I will return terminal. [19:46] Otherwise, I will write it to an epsilon. [19:51] How does it fit together? [19:52] You can use my LL one parser like this. [19:56] Just go parser, give it grammar, give it input, [19:59] and check if it's correct, if it's match. [20:05] And actually, because I'm using special variant [20:09] of LL one grammar, it's O N calculation. [20:15] Okay. [20:19] Think functionally, use function overloading resolution [20:23] and recursion in compile time. [20:27] Okay, this is first part of parser. [20:31] I actually make it a little more verbose [20:33] so I can show you that it's actually types. [20:36] Everything is type here. [20:43] There is constant, correct? [20:44] I am calling. [20:46] And there is a function parse, [20:47] which I'm giving stack with start symbol [20:52] and based on that, I prepare a stack [20:56] without current top symbol. [20:59] I look under top symbol and then I look on current char [21:05] and then I decide with grammar what should I do next? [21:11] And based on that, I will call function move [21:15] which looks like this, in case I'm pushing something [21:18] in the stack. [21:22] I push it in the stack. [21:25] If I'm popping input, I will move to next character. [21:31] And in case I will find reject, I will write them false. [21:36] And if I found accept, I will let them through. [21:39] Oh, sorry. [21:42] And that's all LL one parser in compile time. [21:47] Question? [21:49] - [Man 4] Yeah, have you gave this parse [21:52] something that won't parse? [21:53] Does it compile (speech muffled) [21:57] that they have to do these things compiled like that [21:59] or do they go through the (speech muffled)? [22:00] - Question is if I tried to give the parser a long input? [22:05] - [Man 4] Yeah. [22:06] - Yeah, I tried and after 1000 characters, [22:10] it will stop under the original limit of compiler. [22:13] For my use case it's okay because my regular expression [22:17] usually are pretty short, tops 200 characters. [22:22] - [Man 4] And it doesn't get very slow to compile? [22:24] - No, it's O N actually [22:26] because it's a linear length of input. [22:31] Because I modify grammar, so in every step I pop one input. [22:38] So, but this is returning only boolean value. [22:42] How do I get the pattern from it? [22:48] Is there something missing? [22:51] Yes. [22:53] We need to build an expression template from our parser. [22:58] So, we need to somehow modify the parser [22:59] to give some input other than just boolean. [23:05] I mean, we are building the expression template. [23:08] How can I build it from a string? [23:12] I need to modify my parsing algorithm. [23:16] I'm adding argument of some type, [23:20] subject I'm modifying during parsing, [23:22] and also I need to add a special type of symbol into grammar [23:27] which whenever I hit them, they need to do some modification [23:32] on my subject. [23:36] And I will use my type list again [23:38] because it's most useful thing ever invented [23:41] from sliced bread. [23:44] This is the LL one grammar I shall do just a moment ago [23:49] and these are new symbols and the rest are grammar. [23:52] Whenever I hit them, I need to modify [23:55] my output type somehow. [24:01] Semantic Action looks like other symbol on stack, [24:04] but I need to somehow mark them, [24:05] so I'm using some form of text to my algorithm [24:12] so I can, during compile time, check for them bit concepts. [24:20] What are the changes in the parser? [24:22] You need to introduce different pattern type. [24:26] It's auto, not boolean. [24:28] There is a new argument subject, [24:31] which is default-ly empty list [24:37] and there is a new section. [24:38] If I notice the semantic action I need to modify function [24:46] with symbol I run into which produce char [24:51] and do it subject and then I will pass the next subject [24:57] to the regular expression. [24:59] In case I will not hit induce symbol, [25:03] I will just pass current subject to move function. [25:09] Move function will just let the subject through. [25:14] There's nothing else. [25:16] But accept and reject needs to return there [25:22] a boolean and the output type. [25:30] There is a diagram which show you how it works. [25:34] Every circle is symbol on stack, starting with S. [25:40] Every child of the symbol is pushed by the symbol, [25:43] same as parsing, and at the bottom you can see [25:47] colorful semantic action symbols [25:49] and whenever I hit them, I will do something with the stack. [25:53] For example, when I hit char, I'll insert char, [25:56] produce one to the stack. [25:59] Whenever I hit another char, I push another one [26:01] and then there is a plus. [26:04] In this case, it's not operation like numerical plus, [26:07] it's take one char from stack and it wrap it into plus [26:14] and that is action sequence which take two symbols [26:19] from stack and wrap them into sequence. [26:25] Any question? [26:26] - [Man 5] Yeah, so this is the thought of it. [26:28] If we were to de-mangle the type, [26:29] this is what we would actually see? [26:31] - Yeah. [26:32] - [Man 5] Okay. [26:33] - Question was at the bottom, if it's de-mangled type, [26:36] which we will see, it's there. [26:39] On the top, we can see regular expression [26:42] and on the bottom we can see output type of my parser. [26:46] We can modify it. [26:50] (people laughing and applauding) [26:57] Or as you can see, you can have A plus or optional [27:02] and it uses same technique as I'm using in my parser. [27:10] Or we can have like this. [27:15] We have alternation, optional of A, or optional of B, [27:18] which is nonsense, so we will do this. [27:24] Okay. [27:26] Let try with Jeff is best, yeah? [27:31] (people laughing) [27:36] Okay. [27:39] Difficult. [27:42] What about the modify function? [27:44] How it looks like? [27:46] It's something complex. [27:50] For example, this is a function for pushing characters [27:53] on the stack. [27:55] Notice again, there is no body, [27:58] just signature of a function. [28:00] It's functional. [28:03] There is a symbol which controls which modify function [28:08] I will use and that is a term I got from the parser [28:11] and that is previous content of stack [28:15] and I'm returning new stack with char at the beginning. [28:24] Okay. [28:25] If I want to make something optional, [28:27] I will make symbol optional. [28:32] Take top most thing from the stack [28:35] and wrap it and return to stack. [28:43] Making cycles. [28:45] Based on symbol, I will take something from the stack [28:49] and wrap it and return back. [28:58] Creating sequence. [28:59] I will take two symbols from the top of stack [29:04] and return it as a sequence. [29:05] Notice they are in another order [29:09] because on stack they are in there. [29:11] Only this one is at the top. [29:16] But, if I want to make sequence of more items, [29:21] I need to add other to sequence. [29:23] So, I will look on the stack. [29:26] There is a symbol and subsequence [29:28] and I will return sequence of the symbol [29:30] and my latest one. [29:33] It's functional programming with C plus plus syntax. [29:40] Making alternate. [29:42] It's again, I will take two symbols from the stack [29:46] and wrap it and return back to the stack. [29:54] Adding to alternate is same as adding to sequence. [29:56] The pattern here is simple. [30:00] I will take from the top of stack from symbol [30:04] and add it to alternate. [30:06] That's all. [30:08] If I want to place a digit or a alpha class, [30:12] I will add a symbol of alpha class or regex to the stack. [30:16] Okay. [30:18] So, we have expression template. [30:19] What's next? [30:25] Yeah, question? [30:26] (man speaking off mic) [30:31] Yeah. [30:34] Question was how it works with blank character. [30:37] It's my mistake. [30:38] I forgot to add quotes here. [30:41] It's generated by JavaScript in this case. [30:44] (man speaking off mic) [30:51] Library is right in C plus plus, the slides are not. [30:54] I don't have any IOTD graphics. [30:57] (laughing) [31:01] Okay. [31:03] Pattern and same input. [31:05] So, we can check learning compile time [31:07] if our pattern is same as output type, [31:11] so we can test our patterns if they are exactly [31:14] what we want them to be. [31:17] Okay, how do we evaluate the expression template? [31:25] We need the Res match function, which is called, [31:29] as I showed you before, and we need to check it [31:33] for our pattern is correct with static assert. [31:37] And then, we extract our regular expression [31:41] as the expression template from the parser [31:44] and it's clean because it's already calculated, [31:47] compiler is finishing it. [31:51] And then, I'm going to go other match function, [31:55] which I give characters, begin and end, grand one, [32:01] and I'm giving a list with my regular expression in it [32:07] and I check for success. [32:11] List. [32:12] List again? [32:14] Everything here is based on the type list. [32:18] Yes. [32:21] Okay. [32:23] What happen if... [32:24] Oh, yeah. [32:25] The match function in our monitor [32:27] it wants pair of forward iterator [32:29] and boolean if it success or not. [32:33] It's needed for implementation. [32:37] Okay, if I notice empty list, [32:41] so I already match for regular expression, [32:45] I need to check if it's the end of input [32:49] and they're done through, [32:50] otherwise I'm returning false. [32:54] Okay. [32:56] Matching character. [33:00] I got from the list. [33:04] I need to check if it's end of input [33:09] and I return false. [33:11] If it's different character than I expect, it's false. [33:15] Otherwise, I will move to next term in our iterator [33:21] and rest of the stack [33:24] and of course, it repeat again. [33:29] Matching alpha and digit class is same. [33:31] If there is digit or alpha class I will check [33:34] if there is no end because there can be any character [33:38] at the end and I check if it's the character [33:43] and move to the next again. [33:49] Matching a sequence. [33:51] I will take sequence from the top of stack [33:54] and unwrap it and return it back to stack [33:57] and I write a call again. [33:59] Everything is a question here. [34:01] Simple, so everything is in line. [34:09] Matching optional. [34:10] If I match internal of option and then the rest [34:16] behind optional, I will return through [34:19] or I will try only the rest behind optional. [34:25] Question? [34:26] - [Man 6] Should there be a comma bool [34:29] in your pair return type? [34:33] - No, it's my pair and is there implicitly. [34:37] Question was if there should be a comma bool in my pair. [34:41] It's my own pair in this case. [34:45] I can use separate pair, but it didn't fit to my slide. [34:50] - [Man 6] Okay. [34:51] I just wanted to make sure. [34:53] - Yeah, okay. [34:56] Matching an alternate. [34:57] I will try. [34:59] There is a head and tail in alternate. [35:01] I will try head and the rest behind alternate [35:05] and it will return success [35:07] or if it's a fail, I will try rest of alternate. [35:11] If I hit empty alternate, I will return false. [35:18] Okay. [35:20] Matching a plus-cycle. [35:21] This is utterly complex, [35:24] but I'm introduce in this case, [35:30] I'm showing close of cycle. [35:32] It's easier to implement and there's no backtracking. [35:35] So, I try to match at least one inner content of... [35:47] Sorry, it's star start of cycle in this case. [35:49] Different title, sorry. [35:51] Star cycle. [35:52] I will try to match... [35:57] I think I did mistake here. [35:58] Anyway, I will try to match content of cycle [36:02] and then there is a special symbol end of cycle, [36:05] which will give me return every time I hit it [36:08] and iterate where I end. [36:11] And I try rest of the cycle and if I'm successful, [36:15] I'm returning success. [36:18] If I'm not successful, I will star the end [36:21] of the inner cycle and try it again. [36:28] And if I'm not successful, I'm returning false. [36:40] This is actually star cycle, not plus cycle. [36:43] Wrong title. [36:54] Okay. [36:54] And star cycle, it looks same. [36:58] This should be plus cycle now. [37:00] Yeah, sorry. [37:04] Only difference is that I try to match outer part [37:09] of my cycle before and if I'm successful, [37:11] I'm ending the cycle successfully [37:15] because it's star cycle and there is no need [37:18] for any match for inner part of cycle. [37:21] And that's all different. [37:24] Okay, but in this examples, there are no captures [37:26] or any advanced regular expression functionality. [37:31] I didn't want to scare you. [37:32] (people laughing) [37:35] So, you can see it in my library, [37:38] which is far more complex. [37:40] Must be CR compatible. [37:42] I have vector reference, I'm working on look behind [37:48] and these things. [37:53] Benchmarks. [37:55] Probably you are wonder how it's slow or quick [37:59] 'cause it's a lot of meta programming here. [38:04] So, this is called a measured. [38:07] This is a code in my library. [38:10] There is some pattern and then I read to get input [38:14] from some of the input. [38:16] I know, it's slow. [38:19] And I try match it and write it output. [38:23] Same benchmark I did for std: :regex. [38:29] Exactly same, semantically. [38:33] Pattern, matching. [38:35] Same for PCRE two library. [38:39] Pattern, matching. [38:43] Yeah. [38:44] Okay. [38:45] For the pattern and GC Compiler, [38:47] I have big file, almost two gigabytes, CSV file [38:52] and I type too much with pattern on the top. [38:55] EGREP took 50 seconds to parse it. [38:58] Std: :regex, 55 seconds. [39:01] CTRE library, three point nine second. [39:06] (audience applauding) [39:12] I actually proud that it's quicker than PCRE in this case. [39:17] Anyway, because PCRE is doing your thing. [39:20] Anyway, Lib C plus plus, and Clang, 21 minutes. [39:26] Too much, same pattern. [39:28] That's embarrassing. (people laughing) [39:31] - [Man 7] Yes, it is. [39:33] - Yeah, it is. (people laughing) [39:37] So, I tried looks like std: regex [39:40] and Lib C double plus is slow. [39:44] It is. [39:45] So, I tried different pattern. [39:47] GCC. [39:50] I'm still the best one. [39:53] Yeah. [39:55] EGREP, 32 seconds. [39:57] Because every improvisation you're using some form [40:00] of backtracking or depth first search, [40:02] so depending on pattern your search can be quick or slow. [40:09] So, you should think about your pattern as a code, [40:14] not just write some regular expression which works. [40:17] That's not what we are. [40:19] We are C plus plus level experts, [40:21] we should write great pattern. [40:23] Yes? [40:24] - [Man 8] You're using non-deterministic finite state [40:27] of common (speech covered by coughing) [40:29] - Yeah. [40:30] In this case I'm using depth first search, I think. [40:31] - [Man 8] Do you consider translating into a DFA? [40:38] 'Cause that regex doesn't really need backtracking. [40:40] - Yeah, I was thinking about converting [40:44] to deterministic auto machine, but I'm working on it. [40:50] It's hard. [40:51] - Yeah, it's hard. (people laughing) [40:52] - Sorry? [40:54] Sorry, question was? [40:56] If I tried to convert a regular expression [40:59] into deterministic automata. [41:03] And I did. [41:04] I'm not finished yet. [41:07] But problem with deterministic finite state machine [41:11] is that is hard to implement captures. [41:15] It is. [41:16] So, if you want captures you cannot have [41:18] deterministic finite output machine. [41:21] But there can be some modifier and parser should be able [41:26] to decide what we should do. [41:28] Anyway, I tried this pattern with Clang. [41:32] In this case, it was only two minutes and a half. [41:38] Okay. [41:39] So std: regex in Lib C double plus is consistently bad. [41:43] (people laughing) [41:45] - [Man 9] Marshall. [41:46] - [Marshall] I don't know. [41:47] The two samples doesn't seem consistent. [41:48] (people laughing) - Yeah. [41:52] Marshall is saying that the two samples [41:54] are not saying it's consistent. [41:57] I try more of them. [41:58] (people laughing) [42:00] Yeah? - I'd just like to say [42:02] I'm not going to disagree with your conclusion. [42:03] - Yes, question? [42:05] - [Man 10] Std: :regex does take an optimized flag [42:07] if you want to tell it to try harder [42:09] to make the the regex faster. [42:11] Did you try that? [42:12] Does it do everything with C plus plus? [42:14] - The question is if I tried optimize flock [42:16] in Lib C plus plus. [42:17] I tried, it didn't help. [42:19] (people laughing) [42:23] Okay, I tried another pattern, [42:25] which used more backtracking. [42:26] In this case, PCRE is little quicker. [42:30] Std: :regex is slower from all of it [42:34] and I'm using EGREP as a baseline [42:36] because everyone is using EGREP. [42:39] In Clang, it take 27 minutes. [42:42] (people laughing) [42:44] Actually, on first time, I killed std: :regex. [42:50] It stuck somehow. [42:54] So, as I was benchmarking, I found something interesting. [42:58] Not that Lib C plus plus is slow. [43:03] First, compile time benchmark. [43:05] I compiled everything with same set of headers, [43:09] so it's mostly about the compilation alone. [43:13] I didn't measure linking, only compilation. [43:20] I found that std: :regex is compiling slower [43:23] than my library. [43:24] (people applauding) [43:32] In this case, I found Lib C plus plus... [43:38] This was Clang. [43:39] In GCC one, it's even slower. [43:43] I thought maybe it's my optimizer's trying [43:45] to optimize large amount of code of std: :regex, [43:49] so I disabled optimization. [43:51] It's still there. [43:56] So, sometimes compile time programming is even quicker [44:05] than ordinary programming. [44:07] It's counterintuitive, but it is. [44:10] - [Man 11] What's the baseline in that? [44:12] - Baseline is an empty file without any code. [44:18] - [Man 11] But that would depend on the complex [44:21] regular expression, right? [44:22] - Sorry, I didn't hear you. [44:23] - [Man 11] For compiling with your library [44:27] would depend on the complexity [44:28] if there was regular expression or just the length. [44:31] - Yeah, question is if a compilation of my library [44:36] depends on complex regular expression. [44:38] Yes, you are correct. [44:41] Yes, Bryce? [44:42] - [Bryce] But did std: :regex shift? [44:44] - Std: :regex shouldn't. [44:45] - [Bryce] No. [44:46] - Yeah, I will get into it. [44:49] What's the behavior of the library? [44:51] Multiple different regular expression [44:53] cost 200 milliseconds each on my MacBook. [44:56] So, if you have five regular expression [44:58] in your translation unit, it cost you only one second. [45:02] Bryce, yes? [45:03] - [Bryce] This is compile time? [45:04] - Yeah, compile time. [45:05] Yeah. [45:07] If you use multiple same regular expression [45:09] on different places in your translation unit, [45:10] it cost you virtually nothing. [45:13] Compile cached. [45:15] And cost of one regular expression parsing is linear [45:18] with its complexity. [45:19] I mean complexity, it's length [45:22] because algorithm which build the mature, it's OM. [45:32] What did we learn? [45:34] Recursion and function overloading resolution [45:36] are powerful tools and you should use them. [45:41] And pure function programming keeps you code simple. [45:47] You should forget about variables [45:48] if you do compile programming [45:51] because it just gives you more complexity. [45:56] Trust your compiler, but checks its output. [46:00] And thank you. [46:01] (people applauding) [46:13] Okay, question? [46:16] We'll use a mic. [46:18] - [Man 12] Hi, I'm wondering if there's any way to unify [46:23] a compile time implementation of a library [46:25] with a runtime one because otherwise for every piece [46:30] of functionality that you want to implement, [46:32] you'd have to implement it twice. [46:34] And is there a way that we can use this kind [46:36] of implementation in both contexts? [46:38] And then, just a brief request: [46:40] can you make the annotated example code [46:43] available for learning purposes? [46:46] - Yeah. [46:48] Question is... [46:50] Oh, I don't need to repeat it. [46:53] Yeah, in future, hopefully, when everything will be [46:56] considered expert, you will not need this type of library. [46:58] You will just use std: :regex and it will work same. [47:01] It should work, theoretically. [47:03] So, this is just experiment and it works pretty great, [47:08] but in future, we should use std: :regex [47:10] and it should be great if someone care. [47:14] (people laughing) [47:15] And there are a few examples in my library. [47:20] I'll make it up and you can play with it on Cobalt. [47:29] Just go to Cobalt page and I need to reset it. [47:39] Can you... [47:40] I will make it larger. [47:44] And there is a library button [47:45] and there is a CTRE library and check V two [47:50] and then you can play. [48:10] Literals and ABC, CTRE match against string view. [48:18] Return. [48:21] Okay. [48:22] Yeah, string view. [48:28] And that should work. [48:32] (man speaking off mic) [48:33] Yeah. [48:34] Yeah. [48:38] I always forget. [48:41] Okay? [48:41] It's in un-optimized code. [48:43] It's big. [48:44] I enable optimization and it's like 24 lines of assembly. [48:50] (people laughing) [48:53] Next question? [48:56] Yeah, you? [48:57] - [Man 13] You mentioned that there is a limit [49:00] on how big the regular expression can be. [49:03] - Yeah, it's actually around 1000 chars currently [49:08] because limit of recursion in compiler. [49:12] - [Man 13] I wonder if you had benchmark for this [49:15] - Yeah, I had, but it was a lot of slides [49:19] and a lot of... [49:20] I can show it to you later [49:23] or it should be maybe inside of my documentation. [49:28] I'm not sure. [49:29] Next question? [49:31] - [Man 14] Did you consider benchmarking against [49:34] Boost Xpressive or Boost Regex, firstly? [49:38] And secondly, can you comment on your parser generator [49:43] in comparisons to, say, Boost Spirit X three? [49:47] - I'm not many experiences with Boost. [49:50] I will try it and I will write it [49:55] into the documentation. [49:57] Unfortunately, I'm procrastinator so I finished [50:01] my slide yesterday. [50:02] (people laughing) [50:04] Okay? [50:05] - [Man 15] Is anything you can imagine in the functional [50:07] programming style translatable to compile time [50:10] C plus plus with such techniques [50:13] or are there hard limitations of practical limitations [50:15] in some specific cases? - In this case [50:18] the limit is the length of the string, [50:20] so it's not practical for parsing, for example JSON [50:24] because JSON are usually pretty big [50:27] and also, it's limited by LL one grammar, [50:30] so there are limits, you should have grammar [50:34] without all of the corosion and few limits on the grammar. [50:39] But you can write your LL error parser, [50:41] which have different... [50:44] You know. [50:48] - [Man 16] You kinda went through the slide [50:49] where you're showing the matching kinda quickly. [50:52] - Sorry? [50:53] - [Man 16] I was a little confused as to how [50:55] some of the could happen at compile time [50:58] because you showed an example early on [51:00] showing that you could actually do [51:02] a regular expression match, not just build a parser [51:05] but actually do the match at compile time, [51:09] but when I saw the code of the actual runtime match, [51:12] I said how would that work at compile time? [51:15] - Because every function is constexpr [51:19] and there are no allocation inside it [51:21] so it can use it as part of [51:25] - [Man 16] They're all functional? [51:26] They're not store... [51:28] Yeah, see. [51:29] See, the IT where you're storing [51:33] - This part? [51:34] Matching it against some string. [51:40] That's just a few liners and it works. [51:45] (man speaking off mic) [51:47] Yeah, and for the sake of slides, it's not constexpr. [51:49] - [Man] Uh huh. [51:50] I'll have to look at it more carefully. [51:52] Thank you. - Yeah. [51:54] I will publish my slides in an hour, I think. [52:00] Yes, Odin? [52:01] - [Odin] First of all, this is the awesomest thing [52:02] that anyone's done with meta programming ever. [52:05] (people laughing and applauding) [52:07] - Thank you. [52:12] - [Odin] It seems like, to get around the recursive [52:17] depth limit, you could do some kind of trampolining. [52:21] Have you tried that out or is there something I'm missing? [52:24] - I never heard of your technique. [52:26] - [Odin] Oh, okay. [52:27] We'll talk. - Yeah. [52:32] - [Man 17] For purposes of compile time, [52:34] is it possible to use extern templates [52:37] so that you just compile the thing once [52:39] and then use it in other translation units? [52:44] - You can place your pattern in too much function [52:48] and use it as ordinary function. [52:53] So, you will compile all your pattern only once [52:55] in front of session unit [52:57] and then use as ordinary function. [53:00] It keeps your compilation time low. [53:07] - [Man 18] Hey, you said the the limitation [53:09] is mostly the size of the regular expression given. [53:12] Did you see a problem with just the grammar itself [53:14] or should it stop people from experimenting [53:18] more complex grammar? [53:20] - No, it doesn't depend on grammar [53:22] because grammar is deterministic. [53:24] So, it's only limited by size of your input. [53:28] - [Man 18] Okay, so someone crazy could come next here [53:32] with Evol implemented that way, [53:35] like something that passes C plus plus. [53:37] (people laughing) [53:39] - If you are crazy enough, yeah. [53:40] (people laughing) (man speaking off mic) [53:43] - [Man 18] Yeah, exactly. [53:45] (people laughing) [53:48] - [Man 19] Hi, do you have any idea why PCRE is so fast? [53:54] - It's you think and it's library which is very old [54:00] and mature and in last version, they added getint, [54:03] so they are somehow build the native code [54:06] and tried it and it runs as fast. [54:10] - [Man 20] First, thanks for the great talk [54:12] and the great work. [54:13] It was very amazing. - Thank you. [54:15] - [Man 20] And then, in some way you re-implemented [54:17] Flex or Lex in C plus plus Complex. [54:21] Did you benchmark against a pattern generated from Flex? [54:26] It'd be interesting because that's the very same approach. [54:28] - I didn't benchmark it against Flex or Bison [54:31] because I am scared of them. [54:34] - Okay. (people laughing) [54:36] Fair enough. [54:37] - Okay. [54:38] Okay, thank you. [54:40] (people applauding)