##// END OF EJS Templates
Fix #13654, improve performance of auto match for quotes...
Fix #13654, improve performance of auto match for quotes As pointed out in #13654, auto matching of quotes may take a long time if the prefix is long. To be more precise, the longer the text before the first quote, the slower it is. This is all caused by the regex pattern used: `r'^([^"]+|"[^"]*")*$'`, which I suspect is O(2^N) slow. ```python In [1]: text = "function_with_long_nameeee('arg" In [2]: import re In [3]: pattern = re.compile(r"^([^']+|'[^']*')*$") In [4]: %timeit pattern.match(text) 10.3 s ± 67.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [5]: %timeit pattern.match("1'") 312 ns ± 0.775 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) In [6]: %timeit pattern.match("12'") 462 ns ± 1.95 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) In [7]: %timeit pattern.match("123'") 766 ns ± 6.32 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) In [8]: %timeit pattern.match("1234'") 1.59 µs ± 20.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) ``` But the pattern we want here can actually be detected with a Python implemention in O(N) time.

File last commit:

r13392:bace1f46
r27762:c179c2a5
Show More
test_wildcard.py
143 lines | 4.6 KiB | text/x-python | PythonLexer
"""Some tests for the wildcard utilities."""
#-----------------------------------------------------------------------------
# Library imports
#-----------------------------------------------------------------------------
# Stdlib
import unittest
# Our own
from IPython.utils import wildcard
#-----------------------------------------------------------------------------
# Globals for test
#-----------------------------------------------------------------------------
class obj_t(object):
pass
root = obj_t()
l = ["arna","abel","ABEL","active","bob","bark","abbot"]
q = ["kate","loop","arne","vito","lucifer","koppel"]
for x in l:
o = obj_t()
setattr(root,x,o)
for y in q:
p = obj_t()
setattr(o,y,p)
root._apan = obj_t()
root._apan.a = 10
root._apan._a = 20
root._apan.__a = 20
root.__anka = obj_t()
root.__anka.a = 10
root.__anka._a = 20
root.__anka.__a = 20
root._APAN = obj_t()
root._APAN.a = 10
root._APAN._a = 20
root._APAN.__a = 20
root.__ANKA = obj_t()
root.__ANKA.a = 10
root.__ANKA._a = 20
root.__ANKA.__a = 20
#-----------------------------------------------------------------------------
# Test cases
#-----------------------------------------------------------------------------
class Tests (unittest.TestCase):
def test_case(self):
ns=root.__dict__
tests=[
("a*", ["abbot","abel","active","arna",]),
("?b*.?o*",["abbot.koppel","abbot.loop","abel.koppel","abel.loop",]),
("_a*", []),
("_*anka", ["__anka",]),
("_*a*", ["__anka",]),
]
for pat,res in tests:
res.sort()
a=sorted(wildcard.list_namespace(ns,"all",pat,ignore_case=False,
show_all=False).keys())
self.assertEqual(a,res)
def test_case_showall(self):
ns=root.__dict__
tests=[
("a*", ["abbot","abel","active","arna",]),
("?b*.?o*",["abbot.koppel","abbot.loop","abel.koppel","abel.loop",]),
("_a*", ["_apan"]),
("_*anka", ["__anka",]),
("_*a*", ["__anka","_apan",]),
]
for pat,res in tests:
res.sort()
a=sorted(wildcard.list_namespace(ns,"all",pat,ignore_case=False,
show_all=True).keys())
self.assertEqual(a,res)
def test_nocase(self):
ns=root.__dict__
tests=[
("a*", ["abbot","abel","ABEL","active","arna",]),
("?b*.?o*",["abbot.koppel","abbot.loop","abel.koppel","abel.loop",
"ABEL.koppel","ABEL.loop",]),
("_a*", []),
("_*anka", ["__anka","__ANKA",]),
("_*a*", ["__anka","__ANKA",]),
]
for pat,res in tests:
res.sort()
a=sorted(wildcard.list_namespace(ns,"all",pat,ignore_case=True,
show_all=False).keys())
self.assertEqual(a,res)
def test_nocase_showall(self):
ns=root.__dict__
tests=[
("a*", ["abbot","abel","ABEL","active","arna",]),
("?b*.?o*",["abbot.koppel","abbot.loop","abel.koppel","abel.loop",
"ABEL.koppel","ABEL.loop",]),
("_a*", ["_apan","_APAN"]),
("_*anka", ["__anka","__ANKA",]),
("_*a*", ["__anka","__ANKA","_apan","_APAN"]),
]
for pat,res in tests:
res.sort()
a=sorted(wildcard.list_namespace(ns,"all",pat,ignore_case=True,
show_all=True).keys())
a.sort()
self.assertEqual(a,res)
def test_dict_attributes(self):
"""Dictionaries should be indexed by attributes, not by keys. This was
causing Github issue 129."""
ns = {"az":{"king":55}, "pq":{1:0}}
tests = [
("a*", ["az"]),
("az.k*", ["az.keys"]),
("pq.k*", ["pq.keys"])
]
for pat, res in tests:
res.sort()
a = sorted(wildcard.list_namespace(ns, "all", pat, ignore_case=False,
show_all=True).keys())
self.assertEqual(a, res)
def test_dict_dir(self):
class A(object):
def __init__(self):
self.a = 1
self.b = 2
def __getattribute__(self, name):
if name=="a":
raise AttributeError
return object.__getattribute__(self, name)
a = A()
adict = wildcard.dict_dir(a)
assert "a" not in adict # change to assertNotIn method in >= 2.7
self.assertEqual(adict["b"], 2)