Debian Codegraph @

Lib/test/test_zipfile/_path/test_complexity.py

raw
1 import io
2 import itertools
3 import math
4 import re
5 import string
6 import unittest
7 import zipfile
8
9 from ._functools import compose
10 from ._itertools import consume
11 from ._support import import_or_skip
12
13 big_o = import_or_skip('big_o')
14 pytest = import_or_skip('pytest')
15
16
17 class TestComplexity(unittest.TestCase):
18 @pytest.mark.flaky
19 def test_implied_dirs_performance(self):
20 best, others = big_o.big_o(
21 compose(consume, zipfile._path.CompleteDirs._implied_dirs),
22 lambda size: [
23 '/'.join(string.ascii_lowercase + str(n)) for n in range(size)
24 ],
25 max_n=1000,
26 min_n=1,
27 )
28 assert best <= big_o.complexities.Linear
29
30 def make_zip_path(self, depth=1, width=1) -> zipfile.Path:
31 """
32 Construct a Path with width files at every level of depth.
33 """
34 zf = zipfile.ZipFile(io.BytesIO(), mode='w')
35 pairs = itertools.product(self.make_deep_paths(depth), self.make_names(width))
36 for path, name in pairs:
37 zf.writestr(f"{path}{name}.txt", b'')
38 zf.filename = "big un.zip"
39 return zipfile.Path(zf)
40
41 @classmethod
42 def make_names(cls, width, letters=string.ascii_lowercase):
43 """
44 >>> list(TestComplexity.make_names(1))
45 ['a']
46 >>> list(TestComplexity.make_names(2))
47 ['a', 'b']
48 >>> list(TestComplexity.make_names(30))
49 ['aa', 'ab', ..., 'bd']
50 >>> list(TestComplexity.make_names(17124))
51 ['aaa', 'aab', ..., 'zip']
52 """
53 # determine how many products are needed to produce width
54 n_products = max(1, math.ceil(math.log(width, len(letters))))
55 inputs = (letters,) * n_products
56 combinations = itertools.product(*inputs)
57 names = map(''.join, combinations)
58 return itertools.islice(names, width)
59
60 @classmethod
61 def make_deep_paths(cls, depth):
62 return map(cls.make_deep_path, range(depth))
63
64 @classmethod
65 def make_deep_path(cls, depth):
66 return ''.join(('d/',) * depth)
67
68 def test_baseline_regex_complexity(self):
69 best, others = big_o.big_o(
70 lambda path: re.fullmatch(r'[^/]*\\.txt', path),
71 self.make_deep_path,
72 max_n=100,
73 min_n=1,
74 )
75 assert best <= big_o.complexities.Constant
76
77 @pytest.mark.flaky
78 def test_glob_depth(self):
79 best, others = big_o.big_o(
80 lambda path: consume(path.glob('*.txt')),
81 self.make_zip_path,
82 max_n=100,
83 min_n=1,
84 )
85 assert best <= big_o.complexities.Linear
86
87 @pytest.mark.flaky
88 def test_glob_width(self):
89 best, others = big_o.big_o(
90 lambda path: consume(path.glob('*.txt')),
91 lambda size: self.make_zip_path(width=size),
92 max_n=100,
93 min_n=1,
94 )
95 assert best <= big_o.complexities.Linear
96
97 @pytest.mark.flaky
98 def test_glob_width_and_depth(self):
99 best, others = big_o.big_o(
100 lambda path: consume(path.glob('*.txt')),
101 lambda size: self.make_zip_path(depth=size, width=size),
102 max_n=10,
103 min_n=1,
104 )
105 assert best <= big_o.complexities.Linear