ClickHouse / ClickHouse/ClickHouse

skipPosixNamedClass at a range upper bound: `[0-[:` eats the class end

Open
#119,580 0 comments 0 reactions 0 assignees View on GitHub
comp-regular-function
Dominant language
C++
Stars
49.9k
Forks
9k
Avg merge
21h 32m
Merged PRs (30d)
515

Description

### Describe what's wrong

**`match`, `countMatches` and `extract` silently return no match for a pattern whose character class contains a range ending in `[` followed by `:` when a `:]` appears later in the pattern. `match(materialize('q:]'), 'abc[0-[:]]|q:]')` returns 0 on this PR and 1 on 26.7/26.8; `replaceRegexpOne` (raw RE2, no prefilter) matches the same string.**

- **Root cause:** `[`src/Common/OptimizedRegularExpression.cpp:483`](https://github.com/ClickHouse/ClickHouse/blob/30c98e714f85f24/src/Common/OptimizedRegularExpression.cpp#L483)` dispatches to `skipPosixNamedClass` at every `[` inside an open class. RE2 only attempts `[:name:]` at a class ITEM START (the loop head of `ParseCharClass`); when the previous item is followed by `-` and the next byte is not `]`, `ParseCCRange` consumes the following character as the range's upper bound without the `[:` check. So in `[0-[:]` RE2 reads `[` as the upper bound of `0-[`, then `:` as a member, then closes the class at the next `]` - while the analyzer consumes `[:]]|q:]` as a named class. The analyzer's class then ends later than RE2's, hiding the top-level alternation.

Analysis details (evidence, affected locations, impact)

**Why we believe this is a bug:** `match` -> `Regexps::createRegexp` -> `OptimizedRegularExpression` ctor (`OptimizedRegularExpression.cpp:686`) -> `analyze` -> `analyzeImpl`. At `case '['` with `in_square_braces` set (`:483`) the new helper `skipPosixNamedClass` (`:148`) is called for every `[` in the class body and returns the position after the first `:]` found anywhere in the rest of the pattern. For `abc[0-[:]]|q:]` that is past the class's own `]` and past the top-level `|`, so `has_alternative_on_depth_0` is never set, `required_substring` stays `abc`, and `OptimizedRegularExpression::match` (`:832-843`) rejects every subject that does not contain `abc`.

**Affected locations:**
- [`src/Common/OptimizedRegularExpression.cpp:483`](https://github.com/ClickHouse/ClickHouse/blob/30c98e714f85f24/src/Common/OptimizedRegularExpression.cpp#L483) — `case '['` inside an open class calls `skipPosixNamedClass` unconditionally, including at a range's upper bound
- [`src/Common/OptimizedRegularExpression.cpp:148`](https://github.com/ClickHouse/ClickHouse/blob/30c98e714f85f24/src/Common/OptimizedRegularExpression.cpp#L148) — `skipPosixNamedClass` assumes `pos` is at a class item start

**Impact:** Silent wrong results (missing rows, empty extracts) for any pattern with a top-level alternation whose left branch holds a character class containing a range whose upper bound is `[` followed by `:`, when a `:]` occurs later in the pattern. `match` and `countMatches` return 0 and `extract` returns an empty string for subjects RE2 matches. The same `required_substring` feeds text and bloom-filter-text skip-index pruning, so indexed tables drop those granules as well. This is a regression: 26.7.1.1 and 26.8.1.1 answer these patterns correctly.

### Does it reproduce on most recent release?

Yes — confirmed on current `master` (commit `30c98e714f85f24`).

### How to reproduce

[▶ Run on ClickHouse Fiddle](https://fiddle.clickhouse.com/22884ea2-de20-498d-ac24-d7e0d4b3e15a)

Reproducer

```sql
-- A `[` written as the upper bound of a range inside a character class is a member of the class,
-- not the start of a POSIX named class: `[0-[:]` is the class of `0`..`[` and `:`, and the `|`
-- after it is a top-level alternation.

SELECT match(materialize('q:]'), 'abc[0-[:]]|q:]'), replaceRegexpOne(materialize('q:]'), 'abc[0-[:]]|q:]', 'X');
SELECT countMatches(materialize('q:]'), 'abc[0-[:]]|q:]');
SELECT extract(materialize('q:]'), 'abc[0-[:]]|(q:])');
SELECT match(materialize('abc0]'), 'abc[0-[:]]|q:]'), match(materialize('abc0'), 'abc[0-[:]]|q:]');
```

### Expected behavior

Expected output of the reproducer above:

```
1 X
1
q:]
1 0
```

### Error message and/or stacktrace

Actual output of the reproducer above on `master` (`30c98e714f85f24`):

```
0 X
0

1 0
```

Suggested fix

Only attempt `skipPosixNamedClass` at a class item start. Mirror `ParseCCRange`: inside a class, when the current byte is `-`, it is not the first body position and the next byte is not `]`, consume the `-` and the following item (honouring a `\` escape) before returning to the switch, so a range's upper bound is never re-examined by `case '['`.

Additional context

**Open risks:**
- Over-consumption at a range upper bound also drops literals that follow the class (a weaker prefilter, not wrong results); the same guard fixes both.
- Bounding the `:]` search to the enclosing class - a plausible fix for the quadratic scan reported separately - would mask this case but would then diverge from RE2 for `[[:alpha` patterns whose `:]` genuinely lies past the class. The two fixes need to be designed together.

Found during automated review of [PR #118342](https://github.com/ClickHouse/ClickHouse/pull/118342). Severity P2 · Finding `h_pr118342_101`

cc @alexey-milovidov (from #118342)

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.