Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite3b2c85

Browse files
gh-134873: Fix quadratic complexity in os.path.expandvars()
1 parent8e8786f commite3b2c85

File tree

5 files changed

+97
-116
lines changed

5 files changed

+97
-116
lines changed

‎Lib/ntpath.py

Lines changed: 41 additions & 85 deletions
Original file line numberDiff line numberDiff line change
@@ -400,17 +400,23 @@ def expanduser(path):
400400
# XXX With COMMAND.COM you can use any characters in a variable name,
401401
# XXX except '^|<>='.
402402

403+
_varpattern=r"'[^']*'?|%(%|[^%]*%?)|\$(\$|[-\w]+|\{[^}]*\}?)"
404+
_varsub=None
405+
_varsubb=None
406+
403407
defexpandvars(path):
404408
"""Expand shell variables of the forms $var, ${var} and %var%.
405409
406410
Unknown variables are left unchanged."""
407411
path=os.fspath(path)
412+
global_varsub,_varsubb
408413
ifisinstance(path,bytes):
409414
ifb'$'notinpathandb'%'notinpath:
410415
returnpath
411-
importstring
412-
varchars=bytes(string.ascii_letters+string.digits+'_-','ascii')
413-
quote=b'\''
416+
ifnot_varsubb:
417+
importre
418+
_varsubb=re.compile(_varpattern.encode(),re.ASCII).sub
419+
sub=_varsubb
414420
percent=b'%'
415421
brace=b'{'
416422
rbrace=b'}'
@@ -419,94 +425,44 @@ def expandvars(path):
419425
else:
420426
if'$'notinpathand'%'notinpath:
421427
returnpath
422-
importstring
423-
varchars=string.ascii_letters+string.digits+'_-'
424-
quote='\''
428+
ifnot_varsub:
429+
importre
430+
_varsub=re.compile(_varpattern,re.ASCII).sub
431+
sub=_varsub
425432
percent='%'
426433
brace='{'
427434
rbrace='}'
428435
dollar='$'
429436
environ=os.environ
430-
res=path[:0]
431-
index=0
432-
pathlen=len(path)
433-
whileindex<pathlen:
434-
c=path[index:index+1]
435-
ifc==quote:# no expansion within single quotes
436-
path=path[index+1:]
437-
pathlen=len(path)
438-
try:
439-
index=path.index(c)
440-
res+=c+path[:index+1]
441-
exceptValueError:
442-
res+=c+path
443-
index=pathlen-1
444-
elifc==percent:# variable or '%'
445-
ifpath[index+1:index+2]==percent:
446-
res+=c
447-
index+=1
448-
else:
449-
path=path[index+1:]
450-
pathlen=len(path)
451-
try:
452-
index=path.index(percent)
453-
exceptValueError:
454-
res+=percent+path
455-
index=pathlen-1
456-
else:
457-
var=path[:index]
458-
try:
459-
ifenvironisNone:
460-
value=os.fsencode(os.environ[os.fsdecode(var)])
461-
else:
462-
value=environ[var]
463-
exceptKeyError:
464-
value=percent+var+percent
465-
res+=value
466-
elifc==dollar:# variable or '$$'
467-
ifpath[index+1:index+2]==dollar:
468-
res+=c
469-
index+=1
470-
elifpath[index+1:index+2]==brace:
471-
path=path[index+2:]
472-
pathlen=len(path)
473-
try:
474-
index=path.index(rbrace)
475-
exceptValueError:
476-
res+=dollar+brace+path
477-
index=pathlen-1
478-
else:
479-
var=path[:index]
480-
try:
481-
ifenvironisNone:
482-
value=os.fsencode(os.environ[os.fsdecode(var)])
483-
else:
484-
value=environ[var]
485-
exceptKeyError:
486-
value=dollar+brace+var+rbrace
487-
res+=value
488-
else:
489-
var=path[:0]
490-
index+=1
491-
c=path[index:index+1]
492-
whilecandcinvarchars:
493-
var+=c
494-
index+=1
495-
c=path[index:index+1]
496-
try:
497-
ifenvironisNone:
498-
value=os.fsencode(os.environ[os.fsdecode(var)])
499-
else:
500-
value=environ[var]
501-
exceptKeyError:
502-
value=dollar+var
503-
res+=value
504-
ifc:
505-
index-=1
437+
438+
defrepl(m):
439+
lastindex=m.lastindex
440+
iflastindexisNone:
441+
returnm[0]
442+
name=m[lastindex]
443+
iflastindex==1:
444+
ifname==percent:
445+
returnname
446+
ifnotname.endswith(percent):
447+
returnm[0]
448+
name=name[:-1]
506449
else:
507-
res+=c
508-
index+=1
509-
returnres
450+
ifname==dollar:
451+
returnname
452+
ifname.startswith(brace):
453+
ifnotname.endswith(rbrace):
454+
returnm[0]
455+
name=name[1:-1]
456+
457+
try:
458+
ifenvironisNone:
459+
returnos.fsencode(os.environ[os.fsdecode(name)])
460+
else:
461+
returnenviron[name]
462+
exceptKeyError:
463+
returnm[0]
464+
465+
returnsub(repl,path)
510466

511467

512468
# Normalize a path, e.g. A//B, A/./B and A/foo/../B all become A\B.

‎Lib/posixpath.py

Lines changed: 20 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -284,56 +284,53 @@ def expanduser(path):
284284
# This expands the forms $variable and ${variable} only.
285285
# Non-existent variables are left unchanged.
286286

287-
_varprog=None
288-
_varprogb=None
287+
_varpattern=r'\$(\w+|\{[^}]*\}?)'
288+
_varsub=None
289+
_varsubb=None
289290

290291
defexpandvars(path):
291292
"""Expand shell variables of form $var and ${var}. Unknown variables
292293
are left unchanged."""
293294
path=os.fspath(path)
294-
global_varprog,_varprogb
295+
global_varsub,_varsubb
295296
ifisinstance(path,bytes):
296297
ifb'$'notinpath:
297298
returnpath
298-
ifnot_varprogb:
299+
ifnot_varsubb:
299300
importre
300-
_varprogb=re.compile(br'\$(\w+|\{[^}]*\})',re.ASCII)
301-
search=_varprogb.search
301+
_varsubb=re.compile(_varpattern.encode(),re.ASCII).sub
302+
sub=_varsubb
302303
start=b'{'
303304
end=b'}'
304305
environ=getattr(os,'environb',None)
305306
else:
306307
if'$'notinpath:
307308
returnpath
308-
ifnot_varprog:
309+
ifnot_varsub:
309310
importre
310-
_varprog=re.compile(r'\$(\w+|\{[^}]*\})',re.ASCII)
311-
search=_varprog.search
311+
_varsub=re.compile(_varpattern,re.ASCII).sub
312+
sub=_varsub
312313
start='{'
313314
end='}'
314315
environ=os.environ
315-
i=0
316-
whileTrue:
317-
m=search(path,i)
318-
ifnotm:
319-
break
320-
i,j=m.span(0)
321-
name=m.group(1)
322-
ifname.startswith(start)andname.endswith(end):
316+
317+
defrepl(m):
318+
name=m[1]
319+
ifname.startswith(start):
320+
ifnotname.endswith(end):
321+
returnm[0]
323322
name=name[1:-1]
324323
try:
325324
ifenvironisNone:
326325
value=os.fsencode(os.environ[os.fsdecode(name)])
327326
else:
328327
value=environ[name]
329328
exceptKeyError:
330-
i=j
329+
returnm[0]
331330
else:
332-
tail=path[j:]
333-
path=path[:i]+value
334-
i=len(path)
335-
path+=tail
336-
returnpath
331+
returnvalue
332+
333+
returnsub(repl,path)
337334

338335

339336
# Normalize a path, e.g. A//B, A/./B and A/foo/../B all become A/B.

‎Lib/test/test_genericpath.py

Lines changed: 17 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -7,9 +7,9 @@
77
importsys
88
importunittest
99
importwarnings
10-
fromtest.supportimport(
11-
is_apple,os_helper,warnings_helper
12-
)
10+
fromtestimportsupport
11+
fromtest.supportimportos_helper
12+
fromtest.supportimportwarnings_helper
1313
fromtest.support.script_helperimportassert_python_ok
1414
fromtest.support.os_helperimportFakePath
1515

@@ -445,6 +445,19 @@ def check(value, expected):
445445
os.fsencode('$bar%s bar'%nonascii))
446446
check(b'$spam}bar',os.fsencode('%s}bar'%nonascii))
447447

448+
@support.requires_resource('cpu')
449+
deftest_expandvars_large(self):
450+
expandvars=self.pathmodule.expandvars
451+
withos_helper.EnvironmentVarGuard()asenv:
452+
env.clear()
453+
env["A"]="B"
454+
n=100_000
455+
self.assertEqual(expandvars('$A'*n),'B'*n)
456+
self.assertEqual(expandvars('${A}'*n),'B'*n)
457+
self.assertEqual(expandvars('$A!'*n),'B!'*n)
458+
self.assertEqual(expandvars('${A}A'*n),'BA'*n)
459+
self.assertEqual(expandvars('${'*10*n),'${'*10*n)
460+
448461
deftest_abspath(self):
449462
self.assertIn("foo",self.pathmodule.abspath("foo"))
450463
withwarnings.catch_warnings():
@@ -502,7 +515,7 @@ def test_nonascii_abspath(self):
502515
# directory (when the bytes name is used).
503516
andsys.platformnotin {
504517
"win32","emscripten","wasi"
505-
}andnotis_apple
518+
}andnotsupport.is_apple
506519
):
507520
name=os_helper.TESTFN_UNDECODABLE
508521
elifos_helper.TESTFN_NONASCII:

‎Lib/test/test_ntpath.py

Lines changed: 18 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,8 @@
66
importsys
77
importunittest
88
importwarnings
9-
fromtest.supportimportTestFailed,cpython_only,os_helper
9+
fromtestimportsupport
10+
fromtest.supportimportos_helper
1011
fromtest.support.os_helperimportFakePath
1112
fromtestimporttest_genericpath
1213
fromtempfileimportTemporaryFile
@@ -56,7 +57,7 @@ def tester(fn, wantResult):
5657
fn=fn.replace("\\","\\\\")
5758
gotResult=eval(fn)
5859
ifwantResult!=gotResultand_norm(wantResult)!=_norm(gotResult):
59-
raiseTestFailed("%s should return: %s but returned: %s" \
60+
raisesupport.TestFailed("%s should return: %s but returned: %s" \
6061
%(str(fn),str(wantResult),str(gotResult)))
6162

6263
# then with bytes
@@ -72,7 +73,7 @@ def tester(fn, wantResult):
7273
warnings.simplefilter("ignore",DeprecationWarning)
7374
gotResult=eval(fn)
7475
if_norm(wantResult)!=_norm(gotResult):
75-
raiseTestFailed("%s should return: %s but returned: %s" \
76+
raisesupport.TestFailed("%s should return: %s but returned: %s" \
7677
%(str(fn),str(wantResult),repr(gotResult)))
7778

7879

@@ -875,6 +876,19 @@ def check(value, expected):
875876
check('%spam%bar','%sbar'%nonascii)
876877
check('%{}%bar'.format(nonascii),'ham%sbar'%nonascii)
877878

879+
@support.requires_resource('cpu')
880+
deftest_expandvars_large(self):
881+
expandvars=ntpath.expandvars
882+
withos_helper.EnvironmentVarGuard()asenv:
883+
env.clear()
884+
env["A"]="B"
885+
n=100_000
886+
self.assertEqual(expandvars('%A%'*n),'B'*n)
887+
self.assertEqual(expandvars('%A%A'*n),'BA'*n)
888+
self.assertEqual(expandvars("''"*n+'%%'),"''"*n+'%')
889+
self.assertEqual(expandvars("%%"*n),"%"*n)
890+
self.assertEqual(expandvars("$$"*n),"$"*n)
891+
878892
deftest_expanduser(self):
879893
tester('ntpath.expanduser("test")','test')
880894

@@ -1292,7 +1306,7 @@ def test_con_device(self):
12921306
self.assertTrue(os.path.exists(r"\\.\CON"))
12931307

12941308
@unittest.skipIf(sys.platform!='win32',"Fast paths are only for win32")
1295-
@cpython_only
1309+
@support.cpython_only
12961310
deftest_fast_paths_in_use(self):
12971311
# There are fast paths of these functions implemented in posixmodule.c.
12981312
# Confirm that they are being used, and not the Python fallbacks in
Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Fix quadratic complexity in:func:`os.path.expandvars`.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp