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