google / google/re2

Bounded Lookaround Implementation - Proof of Concept

Open
#585 1 comment 4 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.