tamnd / tamnd/firepanda

B2. RE2 and the eight pattern methods

Open
#158 10 comments 0 reactions 0 assignees View on GitHub
area/string parity
Dominant language
Mojo
Stars
1
Forks
0
PR merge metrics
PR metrics pending

Description

This is a regex engine, not a string method, and it is the largest single item in M6. It gets its own issue for the same reason the specification says it should be scoped separately.

RE2 rather than backtracking, which is a design decision and not a shortcut: linear time matching means a pattern from user data cannot hang the process, and a dataframe library runs patterns over a million rows where a pathological backtrack is not a hypothetical.

### The eight

`contains`, `count`, `extract`, `extractall`, `findall`, `fullmatch`, `match`, `replace`, plus the `regex=True` path of `split` and `rsplit`.

### The divergences this creates

Lookaround and backreferences are not expressible in RE2 and never will be. A pattern using either raises, with a message naming the offending construct rather than saying the pattern is invalid, so that a user who wrote `(?<=foo)bar` is told which part is the problem. Both are registered divergences in the compat registry with cases that assert the raise, which means they stay in the denominator forever rather than being quietly excused.

### Done when

- [ ] A compiler from pattern to automaton with the syntax pandas users actually write: character classes, anchors, groups, named groups, alternation, the quantifiers, non greedy forms, and the inline flags
- [x] Unicode character classes, since `\w` over non ASCII is the case that separates a real engine from a toy
- [x] Capture groups, because `extract` and `extractall` are entirely about them and `replace` needs the numbered references on the replacement side
- [x] A rejected pattern raises with the construct named
- [ ] The eight methods at L3 100 percent, with lookaround and backreferences registered as divergences before the cases land
- [ ] A fuzz corpus of patterns and inputs, since this is the component where a wrong answer is most likely to be silent

### How this is measured

The target above is an L3 rate over this workstream's callables, reported by `pixi run conformance` in [firepanda-compat](https://github.com/tamnd/firepanda-compat) and enforced by the CI ratchet rather than by a person ticking a box. L3 means every parameter takes every one of its values and the combinations that interact are enumerated. The levels are defined in [01-what-100-percent-means.md](https://github.com/tamnd/firepanda-compat/blob/main/docs/specs/01-what-100-percent-means.md), the counts come from [02-the-surface.md](https://github.com/tamnd/firepanda-compat/blob/main/docs/specs/02-the-surface.md), and the ordering argument for this milestone is in [08-m6.md](https://github.com/tamnd/firepanda-compat/blob/main/docs/specs/08-m6.md).

Anything we deliberately will not do goes in the divergence registry with a reason before this issue closes, and a registered divergence still runs and still has to diverge.

Part of #8, milestone M6.

Contributor guide

Open the contributing guide

Research direction

Start with the RE2/compiler design described here, then read the linked firepanda-compat specifications, especially 01-what-100-percent-means.md, 02-the-surface.md, and 08-m6.md; run pixi run conformance to establish the current baseline. Done requires all eight methods to reach the stated L3 target, divergences to be registered and tested, and a fuzz corpus to cover patterns and inputs.

Written by the indexing model from the issue text.

Assessment

Tech stack
pandas
Domain
data-engineering, testing
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.