Automattic / Automattic/harper
The `Repeating` `Pattern` is unintuitively greedy
- Dominant language
- Rust
- Stars
- 15.4k
- Forks
- 627
- Avg merge
- 1d 15h
- Merged PRs (30d)
- 106
Description
I intuitively expected `harper-core/src/expr/repeating.rs` to match only the exact requested number of repetitions.
Perhaps the wording in the comment is a little ambiguous though?
```rs
/// An expression that will match one or more repetitions of the same expression.
///
/// Somewhat reminiscent of the `+*` operator in Regex.
```
The regex `+` operator, "the Kleene Plus", means "1 or more" and the `*` one, "the Kleene Star", means "0 or more". Neither of these involve a maximum number and the comment doesn't mention one.
There is another regex quantifier operator `{}`, "Range", which is the one that include specified minimum and/or maximum number of repetitions. `{n}` matches exactly `n` times and `{n,m}` matches between `n` times and `m` times inclusive.
But the constructor does include one:
```rs
pub fn new(expr: Box, required_repetitions: usize) -> Self {
Self {
inner: expr,
required_repetitions,
}
}
```
When the pattern matched is specific this doesn't seem to matter and the `Pattern` seems to work as expected, but when it's general, it's unexpectedly greedy.
My use case was making sure that a pattern was not followed by certain tokens, which is a common Harper idiom in linters that use `All`, `.but_not()`, and certain other elements. I was matching a pattern with seven or nine elements as long as it wasn't followed by a certain word (and its preceding whitespace). Normally we use a `SequenceExpr` with the needed number of `.t_any()` since it doesn't waste any effort on checking the `Token`'s properties, only that there is a token. I thought it would be cleaner to use `Repeating`.
But it actually matches those seven or nine tokens, plus any subsequent tokens until the end of the chunk.
We definitely use the "n or more logic" in linters, via the `.then_one_or_more()` and `.then_zero_or_more()`, so we need both the current functionality and the `{}` functionality. Or at least to clearly document how it really works.
If we decide to split it we should rename it. Perhaps `NOrMore` but camel-case makes that hard to grok. `Kleene` would work but we'd want to include in the comments whey that name. Or may `MinimumRepeating` or `OpenRepeating` for this one and a new `ClosedRepeating` for the new one?
I asked an AI to bikeshed some naming ideas:
* **`MinRepeating` & `ExactRepeating`**: Very explicit, easy to read in CamelCase.
* **`UnboundedRepeating` & `BoundedRepeating`**: Standard compiler terminology.
* **`AtLeastRepeating` & `FixedRepeating`**: Highly descriptive of the actual logic.
Maybe just adding a second `Option<>` parameter for max repetitions will work?
Contributor guide
Research direction
Start in harper-core/src/expr/repeating.rs, reading Pattern::new and the existing repetition helpers such as then_one_or_more() and then_zero_or_more(). Determine how to preserve the current “n or more” behavior while supporting exact or bounded repetition, or document the current semantics clearly. Done means the chosen API and its greedy behavior are unambiguous.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- devtools
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100