Skip to content

Commit dbfa285

Browse files
authored
Aggressively reduce backtracking in CSS parsing regex logic (#300)
Use Atomic groups and possessive quantifiers to reduce backtracking. In most cases, only minimal backtracking is really required. Rework patterns so that most of them grab what they need and pass or fail.
1 parent 2e46475 commit dbfa285

5 files changed

Lines changed: 33 additions & 36 deletions

File tree

‎.github/workflows/build.yml‎

Lines changed: 1 addition & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -17,12 +17,8 @@ jobs:
1717
max-parallel: 4
1818
matrix:
1919
platform: [ubuntu-latest, windows-latest]
20-
hatch-env: [py310, py311, py312, py313, py314, py315, stdlib]
20+
hatch-env: [py311, py312, py313, py314, py315, stdlib]
2121
include:
22-
- hatch-env: py310
23-
python-version: '3.10'
24-
dev: dev
25-
continue-on-error: false
2622
- hatch-env: py311
2723
python-version: '3.11'
2824
dev: dev

‎docs/src/markdown/about/changelog.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,8 @@ icon: lucide/scroll-text
1313
the custom selector dependency must be defined first in the dictionary. This eliminates recursive processing of
1414
custom selectors. Users are encouraged to pre-compile custom selectors via
1515
`my_selectors = soupsive.CustomSelectors({custm: selector, ...})`.
16+
- **NEW**: Drop Python 3.10.
17+
- **NEW**: Aggressively use possessive quantifiers and atomic groups in CSS pattern parsing to reduce backtracking.
1618
- **NEW**: Eliminate recursion within the parser and the matcher.
1719
- **NEW**: Expose new parameter `max_selectors` that can be used to control the maximum allowed selectors in a given
1820
input.

‎hatch_build.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,6 @@ def update(self, metadata):
2929
'License :: OSI Approved :: MIT License',
3030
'Operating System :: OS Independent',
3131
'Programming Language :: Python :: 3',
32-
'Programming Language :: Python :: 3.10',
3332
'Programming Language :: Python :: 3.11',
3433
'Programming Language :: Python :: 3.12',
3534
'Programming Language :: Python :: 3.13',

‎pyproject.toml‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ name = "soupsieve"
99
description = "A modern CSS selector implementation for Beautiful Soup."
1010
readme = "README.md"
1111
license = "MIT"
12-
requires-python = ">=3.10"
12+
requires-python = ">=3.11"
1313
authors = [
1414
{ name = "Isaac Muse", email = "[email protected]" },
1515
]
@@ -150,10 +150,10 @@ dependencies = [
150150
]
151151

152152
[[tool.hatch.envs.dev.matrix]]
153-
python = ["3.10", "3.11", "3.12", "3.13", "3.14", "3.15"]
153+
python = ["3.11", "3.12", "3.13", "3.14", "3.15"]
154154

155155
[[tool.hatch.envs.dev-stdlib.matrix]]
156-
python = ["3.10", "3.11", "3.12", "3.13", "3.14", "3.15"]
156+
python = ["3.11", "3.12", "3.13", "3.14", "3.15"]
157157

158158
[tool.hatch.envs.dev.scripts]
159159
types = "mypy"

‎soupsieve/css_parser.py‎

Lines changed: 27 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -111,85 +111,85 @@
111111

112112
# Sub-patterns parts
113113
# Whitespace
114-
NEWLINE = r'(?:\r\n|(?!\r\n)[\n\f\r])'
114+
NEWLINE = r'(?>\r\n|[\n\f\r])'
115115
WS = fr'(?:[ \t]|{NEWLINE})'
116116
# Comments
117-
COMMENTS = r'(?:/\*(?:[^*]|\*(?!/))*\*/)'
117+
COMMENTS = r'(?:/\*(?:[^*]|\*(?!/))*+\*/)'
118118
# Whitespace with comments included
119119
WSC = fr'(?:{WS}|{COMMENTS})'
120120
# CSS escapes
121-
CSS_ESCAPES = fr'(?:\\(?:[a-f0-9]{{1,6}}{WS}?|[^\r\n\f]|$))'
122-
CSS_STRING_ESCAPES = fr'(?:\\(?:[a-f0-9]{{1,6}}{WS}?|{NEWLINE}|[^\r\n\f]|$))'
121+
CSS_ESCAPES = fr'(?:\\(?:[a-f0-9]{{1,6}}+{WS}?+|[^\r\n\f]|$))'
122+
CSS_STRING_ESCAPES = fr'(?:\\(?:[a-f0-9]{{1,6}}+{WS}?+|{NEWLINE}|[^\r\n\f]|$))'
123123
# CSS Identifier
124124
IDENTIFIER = fr'''
125-
(?:(?:--|-?(?:[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES}))
126-
(?:[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})*)
125+
(?:(?:--|-?+(?:[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES}))
126+
(?:[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})*+)
127127
'''
128128
# `nth` content
129-
NTH = fr'[-+]?(?:[0-9]+n?|n)(?:(?<=n){WSC}*[-+]{WSC}*[0-9]+)?'
129+
NTH = fr'[-+]?+(?:[0-9]++n?+|n)(?:(?<=n){WSC}*+[-+]{WSC}*+[0-9]++)?+'
130130
# Value: quoted string or identifier
131131
VALUE = fr'''
132-
(?:"(?:\\(?:{NEWLINE}|[^\r\n\f])|[^\\"\r\n\f])*"|
133-
'(?:\\(?:{NEWLINE}|[^\r\n\f])|[^\\'\r\n\f])*'|
132+
(?:"(?:\\(?:{NEWLINE}|[^\r\n\f])|[^\\"\r\n\f])*+"|
133+
'(?:\\(?:{NEWLINE}|[^\r\n\f])|[^\\'\r\n\f])*+'|
134134
{IDENTIFIER})
135135
'''
136136
# Attribute value comparison. `!=` is handled special as it is non-standard.
137-
ATTR = fr'(?:{WSC}*(?P<cmp>[!~^|*$]?=){WSC}*(?P<value>{VALUE})(?:{WSC}*(?P<case>[is]))?)?{WSC}*'
137+
ATTR = fr'(?:{WSC}*+(?P<cmp>[!~^|*$]?+=){WSC}*+(?P<value>{VALUE})(?:{WSC}*+(?P<case>[is]))?+)?+'
138138

139139
# Selector patterns
140140
# IDs (`#id`)
141141
PAT_ID = fr'\#{IDENTIFIER}'
142142
# Classes (`.class`)
143143
PAT_CLASS = fr'\.{IDENTIFIER}'
144144
# Prefix:Tag (`prefix|tag`)
145-
PAT_TAG = fr'(?P<tag_ns>(?:{IDENTIFIER}|\*)?\|)?(?P<tag_name>{IDENTIFIER}|\*)'
145+
PAT_TAG = fr'(?P<tag_ns>(?:{IDENTIFIER}|\*)?+\|)?+(?P<tag_name>{IDENTIFIER}|\*)'
146146
# Attributes (`[attr]`, `[attr=value]`, etc.)
147-
PAT_ATTR = fr'\[{WSC}*(?P<attr_ns>(?:{IDENTIFIER}|\*)?\|(?!=))?(?P<attr_name>{IDENTIFIER}){ATTR}{WSC}*\]'
147+
PAT_ATTR = fr'\[{WSC}*+(?P<attr_ns>(?:{IDENTIFIER}|\*)?+\|(?!=))?+(?P<attr_name>{IDENTIFIER}){ATTR}{WSC}*+\]'
148148
# Pseudo class (`:pseudo-class`, `:pseudo-class(`)
149-
PAT_PSEUDO_CLASS = fr'(?P<name>:{IDENTIFIER})(?P<open>\({WSC}*)?'
149+
PAT_PSEUDO_CLASS = fr'(?P<name>:{IDENTIFIER})(?P<open>\({WSC}*+)?+'
150150
# Pseudo class special patterns. Matches `:pseudo-class(` for special case pseudo classes.
151-
PAT_PSEUDO_CLASS_SPECIAL = fr'(?P<name>:{IDENTIFIER})(?P<open>\({WSC}*)'
151+
PAT_PSEUDO_CLASS_SPECIAL = fr'(?P<name>:{IDENTIFIER})(?P<open>\({WSC}*+)'
152152
# Custom pseudo class (`:--custom-pseudo`)
153153
PAT_PSEUDO_CLASS_CUSTOM = fr'(?P<name>:(?=--){IDENTIFIER})'
154154
# Nesting ampersand selector. Matches `&`
155155
PAT_AMP = r'&'
156156
# Closing pseudo group (`)`)
157-
PAT_PSEUDO_CLOSE = fr'{WSC}*\)'
157+
PAT_PSEUDO_CLOSE = fr'{WSC}*+\)'
158158
# Pseudo element (`::pseudo-element`)
159159
PAT_PSEUDO_ELEMENT = fr':{PAT_PSEUDO_CLASS}'
160160
# At rule (`@page`, etc.) (not supported)
161161
PAT_AT_RULE = fr'@P{IDENTIFIER}'
162162
# Pseudo class `nth-child` (`:nth-child(an+b [of S]?)`, `:first-child`, etc.)
163163
PAT_PSEUDO_NTH_CHILD = fr'''
164164
(?P<pseudo_nth_child>{PAT_PSEUDO_CLASS_SPECIAL}
165-
(?P<nth_child>{NTH}|even|odd))(?:{WSC}*\)|(?P<of>{COMMENTS}*{WS}{WSC}*of{COMMENTS}*{WS}{WSC}*))
165+
(?P<nth_child>{NTH}|even|odd))(?:{WSC}*+\)|(?P<of>{COMMENTS}*+{WS}{WSC}*+of{COMMENTS}*+{WS}{WSC}*+))
166166
'''
167167
# Pseudo class `nth-of-type` (`:nth-of-type(an+b)`, `:first-of-type`, etc.)
168168
PAT_PSEUDO_NTH_TYPE = fr'''
169169
(?P<pseudo_nth_type>{PAT_PSEUDO_CLASS_SPECIAL}
170-
(?P<nth_type>{NTH}|even|odd)){WSC}*\)
170+
(?P<nth_type>{NTH}|even|odd)){WSC}*+\)
171171
'''
172172
# Pseudo class language (`:lang("*-de", en)`)
173-
PAT_PSEUDO_LANG = fr'{PAT_PSEUDO_CLASS_SPECIAL}(?P<values>{VALUE}(?:{WSC}*,{WSC}*{VALUE})*){WSC}*\)'
173+
PAT_PSEUDO_LANG = fr'{PAT_PSEUDO_CLASS_SPECIAL}(?P<values>{VALUE}(?:{WSC}*+,{WSC}*+{VALUE})*+){WSC}*+\)'
174174
# Pseudo class direction (`:dir(ltr)`)
175-
PAT_PSEUDO_DIR = fr'{PAT_PSEUDO_CLASS_SPECIAL}(?P<dir>ltr|rtl){WSC}*\)'
175+
PAT_PSEUDO_DIR = fr'{PAT_PSEUDO_CLASS_SPECIAL}(?P<dir>ltr|rtl){WSC}*+\)'
176176
# Combining characters (`>`, `~`, ` `, `+`, `,`)
177-
PAT_COMBINE = fr'{COMMENTS}*(?={WS}|[,+>~]){WSC}*(?P<relation>[,+>~])?{WSC}*'
177+
PAT_COMBINE = fr'{COMMENTS}*+(?={WS}|[,+>~]){WSC}*+(?P<relation>[,+>~])?+{WSC}*+'
178178
# Extra: Contains (`:contains(text)`)
179-
PAT_PSEUDO_CONTAINS = fr'{PAT_PSEUDO_CLASS_SPECIAL}(?P<values>{VALUE}(?:{WSC}*,{WSC}*{VALUE})*){WSC}*\)'
179+
PAT_PSEUDO_CONTAINS = fr'{PAT_PSEUDO_CLASS_SPECIAL}(?P<values>{VALUE}(?:{WSC}*+,{WSC}*+{VALUE})*+){WSC}*+\)'
180180

181181
# Regular expressions
182182
# CSS escape pattern
183-
RE_CSS_ESC = re.compile(fr'(?:(\\[a-f0-9]{{1,6}}{WSC}?)|(\\[^\r\n\f])|(\\$))', re.I)
184-
RE_CSS_STR_ESC = re.compile(fr'(?:(\\[a-f0-9]{{1,6}}{WS}?)|(\\[^\r\n\f])|(\\$)|(\\{NEWLINE}))', re.I)
183+
RE_CSS_ESC = re.compile(fr'(?:(\\[a-f0-9]{{1,6}}+{WSC}?+)|(\\[^\r\n\f])|(\\$))', re.I)
184+
RE_CSS_STR_ESC = re.compile(fr'(?:(\\[a-f0-9]{{1,6}}+{WS}?+)|(\\[^\r\n\f])|(\\$)|(\\{NEWLINE}))', re.I)
185185
# Pattern to break up `nth` specifiers
186-
RE_NTH = re.compile(fr'(?P<s1>[-+])?(?P<a>[0-9]+n?|n)(?:(?<=n){WSC}*(?P<s2>[-+]){WSC}*(?P<b>[0-9]+))?', re.I)
186+
RE_NTH = re.compile(fr'(?P<s1>[-+])?+(?P<a>[0-9]++n?+|n)(?:(?<=n){WSC}*+(?P<s2>[-+]){WSC}*+(?P<b>[0-9]++))?+', re.I)
187187
# Pattern to iterate multiple values.
188-
RE_VALUES = re.compile(fr'(?:(?P<value>{VALUE})|(?P<split>{WSC}*,{WSC}*))', re.X)
188+
RE_VALUES = re.compile(fr'(?:(?P<value>{VALUE})|(?P<split>{WSC}*+,{WSC}*+))', re.X)
189189
# Whitespace checks
190190
RE_WS = re.compile(WS)
191-
RE_WS_BEGIN = re.compile(fr'^{WSC}*')
192-
RE_WS_END = re.compile(fr'^(?:[ \t]|(?:\n\r|(?!\n\r)[\n\f\r])|{COMMENTS})*')
191+
RE_WS_BEGIN = re.compile(fr'^{WSC}*+')
192+
RE_WS_END = re.compile(fr'^(?:[ \t]|(?>\n\r|[\n\f\r])|{COMMENTS})*+')
193193
RE_CUSTOM = re.compile(fr'^{PAT_PSEUDO_CLASS_CUSTOM}$', re.X)
194194
RE_PSEUDO_CLASS_SPECIAL = re.compile(PAT_PSEUDO_CLASS_SPECIAL, re.I | re.X | re.U)
195195
RE_PSEUDO_IGNORE = re.compile(PAT_PSEUDO_CLASS, re.X | re.I | re.U)

0 commit comments

Comments
 (0)