Skip to content

Commit 5e88d19

Browse files
CPython Developersyouknowone
CPython Developers
authored and
youknowone
committed
Update fnmatch from CPython 3.10
1 parent 6472e4f commit 5e88d19

File tree

2 files changed

+236
-19
lines changed

2 files changed

+236
-19
lines changed

‎Lib/fnmatch.py‎

Lines changed: 86 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -9,16 +9,19 @@
99
The function translate(PATTERN) returns a regular expression
1010
corresponding to PATTERN. (It does not compile it.)
1111
"""
12-
try:
13-
import os
14-
except ImportError:
15-
import _dummy_os as os
12+
import os
1613
import posixpath
1714
import re
1815
import functools
1916

2017
__all__ = ["filter", "fnmatch", "fnmatchcase", "translate"]
2118

19+
# Build a thread-safe incrementing counter to help create unique regexp group
20+
# names across calls.
21+
from itertools import count
22+
_nextgroupnum = count().__next__
23+
del count
24+
2225
def fnmatch(name, pat):
2326
"""Test whether FILENAME matches PATTERN.
2427
@@ -49,7 +52,7 @@ def _compile_pattern(pat):
4952
return re.compile(res).match
5053

5154
def filter(names, pat):
52-
"""Return the subset of the list NAMES that match PAT."""
55+
"""Construct a list from those elements of the iterable NAMES that match PAT."""
5356
result = []
5457
pat = os.path.normcase(pat)
5558
match = _compile_pattern(pat)
@@ -80,15 +83,19 @@ def translate(pat):
8083
There is no way to quote meta-characters.
8184
"""
8285

86+
STAR = object()
87+
res = []
88+
add = res.append
8389
i, n = 0, len(pat)
84-
res = ''
8590
while i < n:
8691
c = pat[i]
8792
i = i+1
8893
if c == '*':
89-
res = res + '.*'
94+
# compress consecutive `*` into one
95+
if (not res) or res[-1] is not STAR:
96+
add(STAR)
9097
elif c == '?':
91-
res = res + '.'
98+
add('.')
9299
elif c == '[':
93100
j = i
94101
if j < n and pat[j] == '!':
@@ -98,10 +105,10 @@ def translate(pat):
98105
while j < n and pat[j] != ']':
99106
j = j+1
100107
if j >= n:
101-
res = res + '\\['
108+
add('\\[')
102109
else:
103110
stuff = pat[i:j]
104-
if '--' not in stuff:
111+
if '-' not in stuff:
105112
stuff = stuff.replace('\\', r'\\')
106113
else:
107114
chunks = []
@@ -113,19 +120,80 @@ def translate(pat):
113120
chunks.append(pat[i:k])
114121
i = k+1
115122
k = k+3
116-
chunks.append(pat[i:j])
123+
chunk = pat[i:j]
124+
if chunk:
125+
chunks.append(chunk)
126+
else:
127+
chunks[-1] += '-'
128+
# Remove empty ranges -- invalid in RE.
129+
for k in range(len(chunks)-1, 0, -1):
130+
if chunks[k-1][-1] > chunks[k][0]:
131+
chunks[k-1] = chunks[k-1][:-1] + chunks[k][1:]
132+
del chunks[k]
117133
# Escape backslashes and hyphens for set difference (--).
118134
# Hyphens that create ranges shouldn't be escaped.
119135
stuff = '-'.join(s.replace('\\', r'\\').replace('-', r'\-')
120136
for s in chunks)
121137
# Escape set operations (&&, ~~ and ||).
122138
stuff = re.sub(r'([&~|])', r'\\\1', stuff)
123139
i = j+1
124-
if stuff[0] == '!':
125-
stuff = '^' + stuff[1:]
126-
elif stuff[0] in ('^', '['):
127-
stuff = '\\' + stuff
128-
res = '%s[%s]' % (res, stuff)
140+
if not stuff:
141+
# Empty range: never match.
142+
add('(?!)')
143+
elif stuff == '!':
144+
# Negated empty range: match any character.
145+
add('.')
146+
else:
147+
if stuff[0] == '!':
148+
stuff = '^' + stuff[1:]
149+
elif stuff[0] in ('^', '['):
150+
stuff = '\\' + stuff
151+
add(f'[{stuff}]')
152+
else:
153+
add(re.escape(c))
154+
assert i == n
155+
156+
# Deal with STARs.
157+
inp = res
158+
res = []
159+
add = res.append
160+
i, n = 0, len(inp)
161+
# Fixed pieces at the start?
162+
while i < n and inp[i] is not STAR:
163+
add(inp[i])
164+
i += 1
165+
# Now deal with STAR fixed STAR fixed ...
166+
# For an interior `STAR fixed` pairing, we want to do a minimal
167+
# .*? match followed by `fixed`, with no possibility of backtracking.
168+
# We can't spell that directly, but can trick it into working by matching
169+
# .*?fixed
170+
# in a lookahead assertion, save the matched part in a group, then
171+
# consume that group via a backreference. If the overall match fails,
172+
# the lookahead assertion won't try alternatives. So the translation is:
173+
# (?=(?P<name>.*?fixed))(?P=name)
174+
# Group names are created as needed: g0, g1, g2, ...
175+
# The numbers are obtained from _nextgroupnum() to ensure they're unique
176+
# across calls and across threads. This is because people rely on the
177+
# undocumented ability to join multiple translate() results together via
178+
# "|" to build large regexps matching "one of many" shell patterns.
179+
while i < n:
180+
assert inp[i] is STAR
181+
i += 1
182+
if i == n:
183+
add(".*")
184+
break
185+
assert inp[i] is not STAR
186+
fixed = []
187+
while i < n and inp[i] is not STAR:
188+
fixed.append(inp[i])
189+
i += 1
190+
fixed = "".join(fixed)
191+
if i == n:
192+
add(".*")
193+
add(fixed)
129194
else:
130-
res = res + re.escape(c)
131-
return r'(?s:%s)\Z' % res
195+
groupnum = _nextgroupnum()
196+
add(f"(?=(?P<g{groupnum}>.*?{fixed}))(?P=g{groupnum})")
197+
assert i == n
198+
res = "".join(res)
199+
return fr'(?s:{res})\Z'

‎Lib/test/test_fnmatch.py‎

Lines changed: 150 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import unittest
44
import os
5+
import string
56
import warnings
67

78
from fnmatch import fnmatch, fnmatchcase, translate, filter
@@ -45,6 +46,13 @@ def test_fnmatch(self):
4546
check('\nfoo', 'foo*', False)
4647
check('\n', '*')
4748

49+
def test_slow_fnmatch(self):
50+
check = self.check_match
51+
check('a' * 50, '*a*a*a*a*a*a*a*a*a*a')
52+
# The next "takes forever" if the regexp translation is
53+
# straightforward. See bpo-40480.
54+
check('a' * 50 + 'b', '*a*a*a*a*a*a*a*a*a*a', False)
55+
4856
def test_mix_bytes_str(self):
4957
self.assertRaises(TypeError, fnmatch, 'test', b'*')
5058
self.assertRaises(TypeError, fnmatch, b'test', '*')
@@ -86,6 +94,119 @@ def test_sep(self):
8694
check('usr/bin', 'usr\\bin', normsep)
8795
check('usr\\bin', 'usr\\bin')
8896

97+
def test_char_set(self):
98+
ignorecase = os.path.normcase('ABC') == os.path.normcase('abc')
99+
check = self.check_match
100+
tescases = string.ascii_lowercase + string.digits + string.punctuation
101+
for c in tescases:
102+
check(c, '[az]', c in 'az')
103+
check(c, '[!az]', c not in 'az')
104+
# Case insensitive.
105+
for c in tescases:
106+
check(c, '[AZ]', (c in 'az') and ignorecase)
107+
check(c, '[!AZ]', (c not in 'az') or not ignorecase)
108+
for c in string.ascii_uppercase:
109+
check(c, '[az]', (c in 'AZ') and ignorecase)
110+
check(c, '[!az]', (c not in 'AZ') or not ignorecase)
111+
# Repeated same character.
112+
for c in tescases:
113+
check(c, '[aa]', c == 'a')
114+
# Special cases.
115+
for c in tescases:
116+
check(c, '[^az]', c in '^az')
117+
check(c, '[[az]', c in '[az')
118+
check(c, r'[!]]', c != ']')
119+
check('[', '[')
120+
check('[]', '[]')
121+
check('[!', '[!')
122+
check('[!]', '[!]')
123+
124+
def test_range(self):
125+
ignorecase = os.path.normcase('ABC') == os.path.normcase('abc')
126+
normsep = os.path.normcase('\\') == os.path.normcase('/')
127+
check = self.check_match
128+
tescases = string.ascii_lowercase + string.digits + string.punctuation
129+
for c in tescases:
130+
check(c, '[b-d]', c in 'bcd')
131+
check(c, '[!b-d]', c not in 'bcd')
132+
check(c, '[b-dx-z]', c in 'bcdxyz')
133+
check(c, '[!b-dx-z]', c not in 'bcdxyz')
134+
# Case insensitive.
135+
for c in tescases:
136+
check(c, '[B-D]', (c in 'bcd') and ignorecase)
137+
check(c, '[!B-D]', (c not in 'bcd') or not ignorecase)
138+
for c in string.ascii_uppercase:
139+
check(c, '[b-d]', (c in 'BCD') and ignorecase)
140+
check(c, '[!b-d]', (c not in 'BCD') or not ignorecase)
141+
# Upper bound == lower bound.
142+
for c in tescases:
143+
check(c, '[b-b]', c == 'b')
144+
# Special cases.
145+
for c in tescases:
146+
check(c, '[!-#]', c not in '-#')
147+
check(c, '[!--.]', c not in '-.')
148+
check(c, '[^-`]', c in '^_`')
149+
if not (normsep and c == '/'):
150+
check(c, '[[-^]', c in r'[\]^')
151+
check(c, r'[\-^]', c in r'\]^')
152+
check(c, '[b-]', c in '-b')
153+
check(c, '[!b-]', c not in '-b')
154+
check(c, '[-b]', c in '-b')
155+
check(c, '[!-b]', c not in '-b')
156+
check(c, '[-]', c in '-')
157+
check(c, '[!-]', c not in '-')
158+
# Upper bound is less that lower bound: error in RE.
159+
for c in tescases:
160+
check(c, '[d-b]', False)
161+
check(c, '[!d-b]', True)
162+
check(c, '[d-bx-z]', c in 'xyz')
163+
check(c, '[!d-bx-z]', c not in 'xyz')
164+
check(c, '[d-b^-`]', c in '^_`')
165+
if not (normsep and c == '/'):
166+
check(c, '[d-b[-^]', c in r'[\]^')
167+
168+
def test_sep_in_char_set(self):
169+
normsep = os.path.normcase('\\') == os.path.normcase('/')
170+
check = self.check_match
171+
check('/', r'[/]')
172+
check('\\', r'[\]')
173+
check('/', r'[\]', normsep)
174+
check('\\', r'[/]', normsep)
175+
check('[/]', r'[/]', False)
176+
check(r'[\\]', r'[/]', False)
177+
check('\\', r'[\t]')
178+
check('/', r'[\t]', normsep)
179+
check('t', r'[\t]')
180+
check('\t', r'[\t]', False)
181+
182+
def test_sep_in_range(self):
183+
normsep = os.path.normcase('\\') == os.path.normcase('/')
184+
check = self.check_match
185+
check('a/b', 'a[.-0]b', not normsep)
186+
check('a\\b', 'a[.-0]b', False)
187+
check('a\\b', 'a[Z-^]b', not normsep)
188+
check('a/b', 'a[Z-^]b', False)
189+
190+
check('a/b', 'a[/-0]b', not normsep)
191+
check(r'a\b', 'a[/-0]b', False)
192+
check('a[/-0]b', 'a[/-0]b', False)
193+
check(r'a[\-0]b', 'a[/-0]b', False)
194+
195+
check('a/b', 'a[.-/]b')
196+
check(r'a\b', 'a[.-/]b', normsep)
197+
check('a[.-/]b', 'a[.-/]b', False)
198+
check(r'a[.-\]b', 'a[.-/]b', False)
199+
200+
check(r'a\b', r'a[\-^]b')
201+
check('a/b', r'a[\-^]b', normsep)
202+
check(r'a[\-^]b', r'a[\-^]b', False)
203+
check('a[/-^]b', r'a[\-^]b', False)
204+
205+
check(r'a\b', r'a[Z-\]b', not normsep)
206+
check('a/b', r'a[Z-\]b', False)
207+
check(r'a[Z-\]b', r'a[Z-\]b', False)
208+
check('a[Z-/]b', r'a[Z-\]b', False)
209+
89210
def test_warnings(self):
90211
with warnings.catch_warnings():
91212
warnings.simplefilter('error', Warning)
@@ -101,6 +222,7 @@ def test_warnings(self):
101222
class TranslateTestCase(unittest.TestCase):
102223

103224
def test_translate(self):
225+
import re
104226
self.assertEqual(translate('*'), r'(?s:.*)\Z')
105227
self.assertEqual(translate('?'), r'(?s:.)\Z')
106228
self.assertEqual(translate('a?b*'), r'(?s:a.b.*)\Z')
@@ -109,7 +231,34 @@ def test_translate(self):
109231
self.assertEqual(translate('[!x]'), r'(?s:[^x])\Z')
110232
self.assertEqual(translate('[^x]'), r'(?s:[\^x])\Z')
111233
self.assertEqual(translate('[x'), r'(?s:\[x)\Z')
112-
234+
# from the docs
235+
self.assertEqual(translate('*.txt'), r'(?s:.*\.txt)\Z')
236+
# squash consecutive stars
237+
self.assertEqual(translate('*********'), r'(?s:.*)\Z')
238+
self.assertEqual(translate('A*********'), r'(?s:A.*)\Z')
239+
self.assertEqual(translate('*********A'), r'(?s:.*A)\Z')
240+
self.assertEqual(translate('A*********?[?]?'), r'(?s:A.*.[?].)\Z')
241+
# fancy translation to prevent exponential-time match failure
242+
t = translate('**a*a****a')
243+
digits = re.findall(r'\d+', t)
244+
self.assertEqual(len(digits), 4)
245+
self.assertEqual(digits[0], digits[1])
246+
self.assertEqual(digits[2], digits[3])
247+
g1 = f"g{digits[0]}" # e.g., group name "g4"
248+
g2 = f"g{digits[2]}" # e.g., group name "g5"
249+
self.assertEqual(t,
250+
fr'(?s:(?=(?P<{g1}>.*?a))(?P={g1})(?=(?P<{g2}>.*?a))(?P={g2}).*a)\Z')
251+
# and try pasting multiple translate results - it's an undocumented
252+
# feature that this works; all the pain of generating unique group
253+
# names across calls exists to support this
254+
r1 = translate('**a**a**a*')
255+
r2 = translate('**b**b**b*')
256+
r3 = translate('*c*c*c*')
257+
fatre = "|".join([r1, r2, r3])
258+
self.assertTrue(re.match(fatre, 'abaccad'))
259+
self.assertTrue(re.match(fatre, 'abxbcab'))
260+
self.assertTrue(re.match(fatre, 'cbabcaxc'))
261+
self.assertFalse(re.match(fatre, 'dabccbad'))
113262

114263
class FilterTestCase(unittest.TestCase):
115264

0 commit comments

Comments
 (0)