Skip to content

Commit 9d0a9a8

Browse files
committed
Fix from_regex handling of negative classes, re.ASCII, and zero-min repeats
Character classes now model the union of their members as an IntervalSet, rather than combining category/whitelist/blacklist sets in a way that let one member's exclusions (e.g. the underscore excluded by \W) remove characters explicitly added by another member (e.g. a literal _ in [\W_]). This also means a class member outside the alphabet no longer poisons the whole class, since only an empty intersection is a real incompatibility. The re.ASCII flag is now applied to what the positive categories \d \s \w match and to casefolding under re.IGNORECASE, instead of intersecting the entire class with the ascii range. Inverted categories like \D match the full unicode complement of their ascii counterpart, and explicit characters and ranges are unaffected by the flag, matching Python's re semantics. Repeats with a minimum of zero (a*, b?, x{0,n}) now generate the empty string when their subpattern is incompatible with the alphabet, instead of raising IncompatibleWithAlphabet for a pattern that has valid matches. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01G1XmctxYEDUxTdXHUCndEQ
1 parent a15954b commit 9d0a9a8

3 files changed

Lines changed: 179 additions & 82 deletions

File tree

‎hypothesis/RELEASE.rst‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
RELEASE_TYPE: patch
2+
3+
This patch fixes several :func:`~hypothesis.strategies.from_regex` bugs
4+
(:issue:`4857`, :issue:`4858`, and :issue:`4859`):
5+
6+
* Character classes which combine a negative category with other members, like
7+
``[\W_]``, now match the union of their members instead of incorrectly
8+
excluding characters.
9+
* The :obj:`python:re.ASCII` flag no longer restricts inverted categories such
10+
as ``\D`` (which matches all non-ascii characters), explicit characters or
11+
ranges in character classes, or casefolding of non-ascii characters.
12+
* Subpatterns which cannot be generated from the ``alphabet``, but may be
13+
repeated zero times - like ``b*`` in ``st.from_regex(r"a*b*", alphabet="a")``
14+
- no longer raise an error.

‎hypothesis/src/hypothesis/strategies/_internal/regex.py‎

Lines changed: 84 additions & 74 deletions
Original file line numberDiff line numberDiff line change
@@ -35,13 +35,10 @@
3535
from typing import Any, AnyStr
3636

3737
from hypothesis import reject, strategies as st
38-
from hypothesis.internal.charmap import CategoryName, as_general_categories, categories
38+
from hypothesis.internal.charmap import as_general_categories
3939
from hypothesis.internal.compat import add_note, int_to_byte
4040
from hypothesis.strategies import SearchStrategy
4141

42-
UNICODE_CATEGORIES = set(categories())
43-
44-
4542
SPACE_CHARS = set(" \t\n\r\f\v")
4643
UNICODE_SPACE_CHARS = SPACE_CHARS | set("\x1c\x1d\x1e\x1f\x85")
4744
UNICODE_DIGIT_CATEGORIES = {"Nd"}
@@ -132,12 +129,12 @@ class Context:
132129

133130

134131
class CharactersBuilder:
135-
"""Helper object that allows to configure `characters` strategy with
136-
various unicode categories and characters. Also allows negation of
137-
configured set.
132+
"""Helper object that collects the members of a regex character class -
133+
literal characters, ranges, and categories like ``\\d`` - and produces a
134+
strategy for the class. A class matches the union of its members, or the
135+
complement of that union for negated classes like ``[^...]``.
138136
139-
:param negate: If True, configure :func:`hypothesis.strategies.characters`
140-
to match anything other than configured character set
137+
:param negate: If True, generate the complement of the configured set
141138
:param flags: Regex flags. They affect how and which characters are matched
142139
"""
143140

@@ -148,34 +145,26 @@ def __init__(
148145
flags: re.RegexFlag = re.RegexFlag(0),
149146
alphabet: SearchStrategy,
150147
):
151-
self._categories: set[CategoryName] = set()
148+
self._intervals = IntervalSet()
152149
self._whitelist_chars: set[str] = set()
153-
self._blacklist_chars: set[str] = set()
154150
self._negate = negate
155-
self._ignorecase = flags & re.IGNORECASE
151+
self._flags = flags
156152
self.code_to_char: Any = chr
157153
self._alphabet = unwrap_strategies(alphabet)
158-
if flags & re.ASCII:
159-
self._alphabet = OneCharStringStrategy(
160-
self._alphabet.intervals & charmap.query(max_codepoint=127)
161-
)
162154

163155
@property
164156
def strategy(self) -> SearchStrategy:
165157
"""Returns resulting strategy that generates configured char set."""
166-
# Start by getting the set of all characters allowed by the pattern
167-
white_chars = self._whitelist_chars - self._blacklist_chars
168-
multi_chars = {c for c in white_chars if len(c) > 1}
169-
intervals = charmap.query(
170-
categories=self._categories,
171-
exclude_characters=self._blacklist_chars,
172-
include_characters=white_chars - multi_chars,
158+
# A character class matches the union of its members
159+
multi_chars = {c for c in self._whitelist_chars if len(c) > 1}
160+
intervals = self._intervals | IntervalSet.from_string(
161+
"".join(self._whitelist_chars - multi_chars)
173162
)
174-
# Then take the complement if this is from a negated character class
163+
# or the complement of that union, if it's a negated class
175164
if self._negate:
176165
intervals = charmap.query() - intervals
177166
multi_chars.clear()
178-
# and finally return the intersection with our alphabet
167+
# and finally we take the intersection with our alphabet
179168
intervals &= self._alphabet.intervals
180169
strategy = _intervals_to_strategy(intervals, description="This character class")
181170
if multi_chars:
@@ -184,43 +173,62 @@ def strategy(self) -> SearchStrategy:
184173

185174
def add_category(self, category):
186175
"""Update unicode state to match sre_parse object ``category``."""
187-
if category == sre.CATEGORY_DIGIT:
188-
self._categories |= UNICODE_DIGIT_CATEGORIES
189-
elif category == sre.CATEGORY_NOT_DIGIT:
190-
self._categories |= UNICODE_CATEGORIES - UNICODE_DIGIT_CATEGORIES
191-
elif category == sre.CATEGORY_SPACE:
192-
self._categories |= UNICODE_SPACE_CATEGORIES
193-
self._whitelist_chars |= UNICODE_SPACE_CHARS
194-
elif category == sre.CATEGORY_NOT_SPACE:
195-
self._categories |= UNICODE_CATEGORIES - UNICODE_SPACE_CATEGORIES
196-
self._blacklist_chars |= UNICODE_SPACE_CHARS
197-
elif category == sre.CATEGORY_WORD:
198-
self._categories |= UNICODE_WORD_CATEGORIES
199-
self._whitelist_chars.add("_")
200-
elif category == sre.CATEGORY_NOT_WORD:
201-
self._categories |= UNICODE_CATEGORIES - UNICODE_WORD_CATEGORIES
202-
self._blacklist_chars.add("_")
176+
# re.ASCII restricts the positive categories \d, \s, and \w to ascii
177+
# characters. The negative categories \D, \S, and \W match the full
178+
# complement of their positive counterpart, so under re.ASCII they
179+
# match *more* characters, not fewer.
180+
max_codepoint = 127 if self._flags & re.ASCII else None
181+
if category in (sre.CATEGORY_DIGIT, sre.CATEGORY_NOT_DIGIT):
182+
intervals = charmap.query(
183+
categories=UNICODE_DIGIT_CATEGORIES, max_codepoint=max_codepoint
184+
)
185+
elif category in (sre.CATEGORY_SPACE, sre.CATEGORY_NOT_SPACE):
186+
if max_codepoint is None:
187+
intervals = charmap.query(
188+
categories=UNICODE_SPACE_CATEGORIES,
189+
include_characters=UNICODE_SPACE_CHARS,
190+
)
191+
else:
192+
intervals = IntervalSet.from_string("".join(SPACE_CHARS))
193+
elif category in (sre.CATEGORY_WORD, sre.CATEGORY_NOT_WORD):
194+
intervals = charmap.query(
195+
categories=UNICODE_WORD_CATEGORIES,
196+
max_codepoint=max_codepoint,
197+
include_characters="_",
198+
)
203199
else:
204200
raise NotImplementedError(f"Unknown character category: {category}")
201+
if category in (
202+
sre.CATEGORY_NOT_DIGIT,
203+
sre.CATEGORY_NOT_SPACE,
204+
sre.CATEGORY_NOT_WORD,
205+
):
206+
intervals = charmap.query() - intervals
207+
self._intervals |= intervals
205208

206209
def add_char(self, c: str) -> None:
207210
"""Add given char to the whitelist."""
208211
self._whitelist_chars.add(c)
212+
swapped = c.swapcase()
209213
if (
210-
self._ignorecase
211-
and re.match(re.escape(c), c.swapcase(), flags=re.IGNORECASE) is not None
214+
self._flags & re.IGNORECASE
215+
and swapped != c
216+
and re.match(
217+
re.escape(c), swapped, flags=re.IGNORECASE | (self._flags & re.ASCII)
218+
)
219+
is not None
212220
):
213-
# Note that it is possible that `len(c.swapcase()) > 1`
214-
self._whitelist_chars.add(c.swapcase())
221+
# Note that it is possible that `len(c.swapcase()) > 1`, and that
222+
# under re.ASCII non-ascii characters do not case-fold at all.
223+
self._whitelist_chars.add(swapped)
215224

216225

217226
class BytesBuilder(CharactersBuilder):
218227
def __init__(self, *, negate: bool = False, flags: re.RegexFlag = re.RegexFlag(0)):
219228
self._whitelist_chars = set()
220-
self._blacklist_chars = set()
221229
self._negate = negate
230+
self._flags = flags
222231
self._alphabet = None
223-
self._ignorecase = flags & re.IGNORECASE
224232
self.code_to_char = int_to_byte
225233

226234
@property
@@ -440,7 +448,12 @@ def recurse(codes):
440448
if (
441449
context.flags & re.IGNORECASE
442450
and c != c.swapcase()
443-
and re.match(re.escape(c), c.swapcase(), re.IGNORECASE) is not None
451+
and re.match(
452+
re.escape(c),
453+
c.swapcase(),
454+
re.IGNORECASE | (context.flags & re.ASCII),
455+
)
456+
is not None
444457
and not chars_not_in_alphabet(alphabet, c.swapcase())
445458
):
446459
# We do the explicit check for swapped-case matching because
@@ -454,7 +467,12 @@ def recurse(codes):
454467
blacklist = {c}
455468
if (
456469
context.flags & re.IGNORECASE
457-
and re.match(re.escape(c), c.swapcase(), re.IGNORECASE) is not None
470+
and re.match(
471+
re.escape(c),
472+
c.swapcase(),
473+
re.IGNORECASE | (context.flags & re.ASCII),
474+
)
475+
is not None
458476
):
459477
# There are a few cases where .swapcase() returns two characters,
460478
# but is still a case-insensitive match. In such cases we add *both*
@@ -500,30 +518,16 @@ def recurse(codes):
500518
pass
501519
elif charset_code == sre.LITERAL:
502520
# Regex '[a]' (single char)
503-
c = builder.code_to_char(charset_value)
504-
if chars_not_in_alphabet(builder._alphabet, c):
505-
raise IncompatibleWithAlphabet(
506-
f"Literal {c!r} is not in the specified alphabet"
507-
)
508-
builder.add_char(c)
521+
# Note that we do not check the alphabet here: the class
522+
# matches the union of its members, so it only becomes
523+
# incompatible if *no* member intersects the alphabet -
524+
# which .strategy checks for.
525+
builder.add_char(builder.code_to_char(charset_value))
509526
elif charset_code == sre.RANGE:
510527
# Regex '[a-z]' (char range)
511528
low, high = charset_value
512-
chars = empty.join(map(builder.code_to_char, range(low, high + 1)))
513-
if len(chars) == len(
514-
invalid := chars_not_in_alphabet(alphabet, chars)
515-
):
516-
raise IncompatibleWithAlphabet(
517-
f"Charset '[{chr(low)}-{chr(high)}]' contains characters {invalid!r} "
518-
f"which are not in the specified alphabet"
519-
)
520-
for c in chars:
521-
if isinstance(c, int):
522-
c = int_to_byte(c)
523-
if c not in invalid:
524-
# add_char is typed as str, but BytesBuilder shares it
525-
# and add_char's body works for bytes too.
526-
builder.add_char(c) # type: ignore[arg-type]
529+
for code_point in range(low, high + 1):
530+
builder.add_char(builder.code_to_char(code_point))
527531
elif charset_code == sre.CATEGORY:
528532
# Regex '[\w]' (char category)
529533
builder.add_category(charset_value)
@@ -600,11 +604,17 @@ def recurse(codes):
600604
at_least, at_most, subregex = value
601605
if at_most == sre.MAXREPEAT:
602606
at_most = None
607+
try:
608+
sub = recurse(subregex)
609+
except IncompatibleWithAlphabet:
610+
# A subpattern which can't be generated from the alphabet is
611+
# fine if we're allowed to repeat it zero times.
612+
if at_least == 0:
613+
return st.just(empty)
614+
raise
603615
if at_least == 0 and at_most == 1:
604-
return st.just(empty) | recurse(subregex)
605-
return st.lists(recurse(subregex), min_size=at_least, max_size=at_most).map(
606-
empty.join
607-
)
616+
return st.just(empty) | sub
617+
return st.lists(sub, min_size=at_least, max_size=at_most).map(empty.join)
608618

609619
elif code == sre.GROUPREF_EXISTS:
610620
# Regex '(?(id/name)yes-pattern|no-pattern)'

‎hypothesis/tests/cover/test_regex.py‎

Lines changed: 81 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
# obtain one at https://mozilla.org/MPL/2.0/.
1010

1111
import re
12+
import string
1213
import sys
1314
import unicodedata
1415

@@ -43,6 +44,14 @@ def is_digit(s):
4344
return all(unicodedata.category(c) in UNICODE_DIGIT_CATEGORIES for c in s)
4445

4546

47+
def is_ascii_digit(s):
48+
return all(c in string.digits for c in s)
49+
50+
51+
def is_ascii_word(s):
52+
return all(c in string.ascii_letters + string.digits + "_" for c in s)
53+
54+
4655
def is_space(s):
4756
return all(c in SPACE_CHARS for c in s)
4857

@@ -205,10 +214,12 @@ def test_any_with_dotall_generate_newline_binary(pattern):
205214
@pytest.mark.parametrize("is_unicode", [False, True])
206215
@pytest.mark.parametrize("invert", [False, True])
207216
def test_groups(pattern, is_unicode, invert):
217+
# Under re.ASCII, the positive categories \d \s \w match only ascii
218+
# characters, and the negative categories \D \S \W match everything else.
208219
if "d" in pattern.lower():
209-
group_pred = is_digit
220+
group_pred = is_digit if is_unicode else is_ascii_digit
210221
elif "w" in pattern.lower():
211-
group_pred = is_word
222+
group_pred = is_word if is_unicode else is_ascii_word
212223
else:
213224
# Special behaviour due to \x1c, INFORMATION SEPARATOR FOUR
214225
group_pred = is_unicode_space if is_unicode else is_space
@@ -510,18 +521,13 @@ def test_can_pass_collections_for_alphabet(alphabet):
510521
"pattern, alphabet",
511522
[
512523
(r"[^\d\D]", st.characters()),
513-
(re.compile("[^\\u0000-\\u00ff]", re.ASCII), st.characters()),
514524
("[^abc]", st.sampled_from("abc")),
515525
("[\\d]", st.sampled_from("abc")),
516526
("\\d", st.sampled_from("abc")),
517527
("[^a]", st.just("a")),
518528
(".", st.just("\n")),
519-
("[^a]*", st.just("a")),
529+
("[^a]+", st.just("a")),
520530
("[a-z]", st.just("0")),
521-
(
522-
re.compile("[\\u0100-\\u0200]", re.ASCII | re.IGNORECASE),
523-
st.characters(min_codepoint=0x100),
524-
),
525531
],
526532
)
527533
def test_charsets_which_match_nothing_in_the_alphabet(pattern, alphabet):
@@ -536,6 +542,73 @@ def test_charset_matching_nothing_only_rules_out_its_own_branch():
536542
)
537543

538544

545+
def test_zero_minimum_repeats_incompatible_with_alphabet():
546+
# a subpattern which is incompatible with the alphabet can still be
547+
# repeated zero times - see issue #4857
548+
strategy = st.from_regex("a*b*", alphabet="a", fullmatch=True)
549+
find_any(strategy, lambda s: s == "")
550+
find_any(strategy, lambda s: s == "aa")
551+
assert_all_examples(strategy, lambda s: set(s) <= {"a"})
552+
assert_all_examples(
553+
st.from_regex("ab?", alphabet="a", fullmatch=True), lambda s: s == "a"
554+
)
555+
556+
557+
def test_ascii_inverted_categories_match_all_of_unicode():
558+
# \D under re.ASCII matches everything except [0-9], rather than being
559+
# restricted to ascii characters - see issue #4858
560+
regex = re.compile(r"\D", re.ASCII)
561+
assert regex.fullmatch("٣")
562+
assert_all_examples(
563+
st.from_regex(regex, alphabet="٣", fullmatch=True), lambda s: s == "٣"
564+
)
565+
566+
567+
@pytest.mark.parametrize(
568+
"pattern",
569+
[
570+
re.compile("[Ï-İ]", re.IGNORECASE | re.ASCII),
571+
re.compile("[^\\u0000-\\u00ff]", re.ASCII),
572+
re.compile("ï", re.IGNORECASE | re.ASCII),
573+
],
574+
)
575+
def test_ascii_flag_does_not_restrict_characters_or_ranges(pattern):
576+
# re.ASCII changes what \d \s \w match and restricts casefolding to ascii
577+
# characters, but explicit characters and ranges are unaffected - see
578+
# issue #4858
579+
assert_all_examples(
580+
base_regex_strategy(pattern, alphabet=st.characters()), pattern.fullmatch
581+
)
582+
583+
584+
def test_ascii_characters_still_fold_under_ascii_flag():
585+
strategy = st.from_regex(re.compile("i", re.IGNORECASE | re.ASCII), fullmatch=True)
586+
find_any(strategy, lambda s: s == "I")
587+
588+
589+
def test_class_with_negative_category_and_positive_members():
590+
# [\W_] matches the union of \W and {"_"} - see issue #4859
591+
regex = re.compile(r"[\W_]")
592+
assert_all_examples(
593+
st.from_regex(regex, alphabet="_", fullmatch=True), lambda s: s == "_"
594+
)
595+
find_any(st.from_regex(r"\A[\W_]\Z"), lambda s: s == "_")
596+
597+
598+
def test_negated_class_excludes_all_members():
599+
# [^\W_] matches the complement of the union: word characters except "_"
600+
regex = re.compile(r"[^\W_]")
601+
assert_all_examples(
602+
base_regex_strategy(regex, alphabet=st.characters()), regex.fullmatch
603+
)
604+
605+
606+
def test_negated_class_with_members_outside_alphabet():
607+
assert_all_examples(
608+
st.from_regex("[^bc]", alphabet="a", fullmatch=True), lambda s: s == "a"
609+
)
610+
611+
539612
@pytest.mark.parametrize(
540613
"alphabet, error_part",
541614
[

0 commit comments

Comments
 (0)