Bounded Lookaround Implementation - Proof of Concept
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.2k
- PR merge metrics
- No merged PRs in 30d
Description
Hi RE2 maintainers and community,
I've been following the lookaround feature request (#156) and understand the design principles behind RE2, particularly regarding constructs that require backtracking.
I'd like to present a proof-of-concept implementation that attempts to address the core concerns while providing bounded lookaround functionality.
## Goals
1. Maintain O(n) time complexity - No exponential worst cases
2. Respect RE2's design philosophy - No backtracking required
3. Provide practical utility - Cover most common lookaround use cases
4. Stay true to RE2's safety guarantees - Bounded memory, predictable performance
## Implementation Approach
**Bounded Lookaround**:
- Lookbehind: Limited to 255 characters backward (configurable at compile time)
- Lookahead: Naturally bounded by remaining text length
- Each lookaround compiles to a separate subprogram
- Execution integrated into NFA engine (no DFA support)
**Time Complexity**: O(n × m × k) where:
- n = input length
- m = number of lookaround assertions
- k = bounded subpattern complexity (max 255 chars)
Still linear in input length, but with higher constant factors.
**Architecture**:
```
Pattern: (?
Contributor guide
Assessment
This issue has not been assessed yet.