src/tools/swarming_client/tests/short_expression_finder_test.py

   1 #!/usr/bin/env python
   2 # Copyright 2013 The Swarming Authors. All rights reserved.
   3 # Use of this source code is governed under the Apache License, Version 2.0 that
   4 # can be found in the LICENSE file.
   5
   6 import itertools
   7 import os
   8 import sys
   9 import unittest
  10
  11 ROOT_DIR = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
  12 sys.path.insert(0, ROOT_DIR)
  13
  14 from utils import short_expression_finder
  15 from utils.short_expression_finder import ShortExpressionFinder, partitions
  16
  17
  18 # Access to a protected member XXX of a client class
  19 # pylint: disable=W0212
  20
  21
  22 def matching_configs(expr, variables_and_values):
  23   """Return configs for which expr evaluates to true."""
  24   variables, values = zip(*variables_and_values)
  25   return tuple(
  26     config for config in itertools.product(*values)
  27     if eval(expr, dict(zip(variables, config)))
  28   )
  29
  30
  31 class Tests(unittest.TestCase):
  32   def test_simple(self):
  33     sef = ShortExpressionFinder([('var', [17])])
  34     self.assertEqual('var==17', sef.get_expr([(17,)]))
  35
  36   def test_two_variables_four_values(self):
  37     vals1, vals2 = (1, 2), ("ab", "cd")
  38     sef = ShortExpressionFinder([('var1', vals1), ('var2', vals2)])
  39     all_configs = tuple(itertools.product(vals1, vals2))
  40     for val1 in vals1:
  41       for val2 in vals2:
  42         self.assertEqual('var1==%d and var2=="%s"' % (val1, val2),
  43                          sef.get_expr([(val1, val2)]))
  44     for val1 in vals1:
  45       self.assertEqual('var1==%d and (var2=="ab" or var2=="cd")' % val1,
  46                        sef.get_expr([(val1, "ab"), (val1, "cd")]))
  47     for val2 in vals2:
  48       self.assertEqual('(var1==1 or var1==2) and var2=="%s"' % val2,
  49                        sef.get_expr([(1, val2), (2, val2)]))
  50     self.assertEqual('(var1==1 or var1==2) and (var2=="ab" or var2=="cd")',
  51                      sef.get_expr(all_configs))
  52
  53   def check_expr(self, expr, variables_and_values):
  54     """Check that ShortExpressionFinder returns an expression that's logically
  55     equivalent to |expr| and equally simple, when given the matching configs.
  56     """
  57     configs = matching_configs(expr, variables_and_values)
  58     output_expr = ShortExpressionFinder(variables_and_values).get_expr(configs)
  59     output_configs = matching_configs(output_expr, variables_and_values)
  60     self.assertEqual(configs, output_configs)
  61     self.assertEqual(expr.count('=='), output_expr.count('=='))
  62     self.assertEqual(expr.count('('), output_expr.count('('))
  63
  64   def test_single_nontrivial_region(self):
  65     self.check_expr('((OS=="linux" or OS=="mac" or OS=="win") and chromeos==0)'
  66                     ' or (OS=="linux" and chromeos==1)',
  67                     [('OS', 'linux mac win'.split()), ('chromeos', (0, 1))])
  68
  69     self.check_expr('(OS=="linux" or OS=="mac" or OS=="win") and chromeos==0',
  70                     [('OS', 'linux mac win'.split()), ('chromeos', (0, 1))])
  71
  72     self.check_expr('OS=="linux" and (chromeos==0 or chromeos==1)',
  73                     [('OS', 'linux mac win'.split()), ('chromeos', (0, 1))])
  74
  75   def test_multiple_nontrivial_regions(self):
  76     # two disjoint regions of 1*2*1=2 and 2*1*2=4 configs, no overlap
  77     self.check_expr(
  78         '(p==2 and (q=="a" or q=="b") and r==10)'
  79         ' or ((p==1 or p==2) and q=="c" and (r==8 or r==10))',
  80         [('p', (1, 2, 3)), ('q', ('a', 'b', 'c')), ('r', (8, 9, 10))])
  81
  82     # two regions of 4 and 8 configs with overlap
  83     self.check_expr(
  84         '((p==1 or p==2) and (q=="a" or q=="b") and r==9)'
  85         ' or ((p==2 or p==3) and q=="a" and (r==8 or r==9))',
  86         [('p', (1, 2, 3)), ('q', ('a', 'b', 'c')), ('r', (8, 9, 10))])
  87
  88     # All configs except (p, q, r) == (2, 4, 6). There are simpler expressions
  89     # for this that don't fit ShortExpressionFinder's grammar.
  90     self.check_expr('((p==1 or p==2) and (q==3 or q==4) and r==5)'
  91                     ' or ((p==1 or p==2) and q==3 and r==6)'
  92                     ' or (p==1 and q==4 and r==6)',
  93                     [('p', (1, 2)), ('q', (3, 4)), ('r', (5, 6))])
  94
  95   def test_100_variables(self):
  96     # This is kind of a cheat because the complexity is ((2^k)-1)^n for n
  97     # variables of k values each. With k=2 this would be hopelessly slow.
  98     self.check_expr(' and '.join('var%d=="val%d"' % (n, n) for n in range(100)),
  99                     [('var%d' % n, ('val%d' % n,)) for n in range(100)])
 100
 101   def test_short_expression_finder_failure(self):
 102     # End users should never see these failures so it doesn't matter much how
 103     # exactly they fail.
 104     self.assertRaises(AssertionError, ShortExpressionFinder, [])
 105     self.assertRaises(AssertionError,
 106         ShortExpressionFinder, [('x', (1, 2)), ('no_values', ())])
 107     self.assertRaises(TypeError,
 108         ShortExpressionFinder, [('bad_type', (1, 2.5))])
 109     self.assertRaises(AssertionError,
 110         ShortExpressionFinder, [('bad name', (1, 2))])
 111     self.assertRaises(AssertionError,
 112         ShortExpressionFinder, [('x', ('bad value',))])
 113     self.assertRaises(TypeError,
 114         ShortExpressionFinder, [('x', (1, 'mixed_values'))])
 115     self.assertRaises(AssertionError,
 116         ShortExpressionFinder([('no_configs', (1, 2))]).get_expr, [])
 117     self.assertRaises(AssertionError,
 118         ShortExpressionFinder([('no_such_value', (1, 2))]).get_expr, [(3,)])
 119     self.assertRaises(AssertionError,
 120         ShortExpressionFinder([('wrong_length', (1, 2))]).get_expr, [(1, 3)])
 121
 122   def test_partitions(self):
 123     self.assertEqual(((None, None),), tuple(partitions(0, 2)))
 124     self.assertEqual((), tuple(partitions(1, 2)))
 125
 126     def count_partitions(parts, remaining):
 127       parts = tuple(parts)
 128       if parts == ((None, None),):
 129         self.assertEqual(0, remaining)
 130         return 1
 131       return sum(count_partitions(ns, remaining - n) for n, ns in parts)
 132
 133     # http://oeis.org/A002865
 134     expected = [1, 0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 41, 55, 66]
 135     for n, count in enumerate(expected):
 136       actual_count = count_partitions(partitions(n, 2), n)
 137       self.assertEqual(count, actual_count)
 138
 139     # This also checks that the call doesn't compute all
 140     # 23,127,843,459,154,899,464,880,444,632,250 partitions up front.
 141     self.assertEqual(501, len(tuple(partitions(1000, 1))))
 142
 143   def test_nones(self):
 144     ShortExpressionFinder([('foo', ('a',))])
 145     with self.assertRaises(TypeError):
 146       ShortExpressionFinder([('foo', ('a', None))])
 147
 148   def test_complex(self):
 149     # An end-to-end test that looks at behavior with 4 degrees (variables).
 150     variables = [
 151         # For example component build vs static build.
 152         ('lib', ('s', 'c')),
 153         ('cros', (0, 1)),
 154         ('OS', ('l', 'm', 'w')),
 155         ('brand', ('C', 'GC', 'Y')),
 156     ]
 157     expectations = [
 158         (
 159           [('s', 0, 'l', 'C')],
 160           'lib=="s" and cros==0 and OS=="l" and brand=="C"',
 161         ),
 162         (
 163           [('s', 0, 'l', 'C'), ('s', 0, 'm', 'C')],
 164           'lib=="s" and cros==0 and (OS=="l" or OS=="m") and brand=="C"',
 165         ),
 166         (
 167           [('s', 0, 'l', 'C'), ('s', 0, 'm', 'C'), ('s', 0, 'm', 'GC')],
 168           '(lib=="s" and cros==0 and OS=="l" and brand=="C") or '
 169           '(lib=="s" and cros==0 and OS=="m" and (brand=="C" or brand=="GC"))'
 170         ),
 171         (
 172           [('s', 0, 'l', 'C'), ('s', 0, 'm', 'C'), ('s', 0, 'w', 'C')],
 173           'lib=="s" and cros==0 and (OS=="l" or OS=="m" or OS=="w") and '
 174           'brand=="C"',
 175         ),
 176         (
 177           [
 178             ('s', 1, 'l', 'C'), ('s', 0, 'l', 'C'), ('s', 0, 'm', 'C'),
 179             ('s', 0, 'w', 'C'),
 180           ],
 181           # TODO(maruel): Could have been written slightly more efficiently.
 182           # 'lib=="s" and 'brand=="C" and (...)'
 183           '(lib=="s" and cros==1 and OS=="l" and brand=="C") or '
 184           '(lib=="s" and cros==0 and (OS=="l" or OS=="m" or OS=="w") and '
 185           'brand=="C")'
 186         ),
 187         (
 188           [('s', None, None, None)],
 189           'lib=="s"',
 190         ),
 191         (
 192           [('s', 1, None, None)],
 193           'lib=="s" and cros==1',
 194         ),
 195         (
 196           [(None, 1, None, None)],
 197           'cros==1',
 198         ),
 199         (
 200           [(None, 1, None, None), (None, 0, 'w', None), (None, 0, 'm', None)],
 201           # Note the ordering of the specification is lost.
 202           '(cros==0 and (OS=="m" or OS=="w")) or cros==1',
 203         ),
 204         (
 205           [('s', 1, 'l', None), ('c', 0, 'w', None), ('s', 0, 'm', None)],
 206           # TODO(maruel): Could have been written slightly more efficiently.
 207           '(lib=="s" and cros==0 and OS=="m") or '
 208           '(lib=="c" and cros==0 and OS=="w") or '
 209           '(lib=="s" and cros==1 and OS=="l")',
 210         ),
 211         (
 212           [('s', 1, 'l', None), ('c', 0, 'w', None), ('c', 0, 'm', None)],
 213           '(lib=="s" and cros==1 and OS=="l") or '
 214           '(lib=="c" and cros==0 and (OS=="m" or OS=="w"))',
 215         ),
 216         (
 217           [
 218             (None, 1, 'l', 'GC'), (None, 0, 'l', 'GC'), (None, None, 'm', 'GC'),
 219             (None, None, 'w', 'GC'),
 220           ],
 221           '((cros==0 or cros==1) and OS=="l" and brand=="GC") or '
 222           '((OS=="m" or OS=="w") and brand=="GC")',
 223         ),
 224     ]
 225     for i, (data, expected) in enumerate(expectations):
 226       s = short_expression_finder.ShortExpressionFinder(variables)
 227       actual = s.get_expr(data)
 228       self.assertEqual(
 229           expected, actual, '\n%r\n%r\n%r\n%s' % (data, expected, actual, i))
 230
 231
 232 class TestPrivateCode(unittest.TestCase):
 233   # Tests the non-exported functions.
 234   def test_calculate_cost_simple(self):
 235     values = ([17],)
 236     self.assertEqual(
 237         {2: {1: (1,)}}, short_expression_finder._calculate_costs(values, 1, 1))
 238
 239   def test_calculate_cost_1_x_0(self):
 240     # Degenerative case.
 241     values = ([17], [])
 242     self.assertEqual({}, short_expression_finder._calculate_costs(values, 1, 1))
 243
 244   def test_calculate_cost_1_x_2(self):
 245     values = ([1, 2], [3])
 246     expected = {
 247       3: {
 248         1: (1, 1),
 249         2: (2, 1),
 250       },
 251       5: {
 252         3: (3, 1),
 253       },
 254     }
 255     self.assertEqual(
 256         expected, short_expression_finder._calculate_costs(values, 1, 1))
 257
 258   def test_calculate_cost_2_x_2(self):
 259     values = ([1, 2], [3, 4])
 260     expected = {
 261       3: {
 262         1: (1, 1),
 263         2: (2, 1),
 264         4: (1, 2),
 265         8: (2, 2),
 266       },
 267       5: {
 268         3: (3, 1),
 269         5: (1, 3),
 270         10: (2, 3),
 271         12: (3, 2),
 272       },
 273       7: {
 274         15: (3, 3),
 275       },
 276     }
 277     self.assertEqual(
 278         expected, short_expression_finder._calculate_costs(values, 1, 1))
 279
 280   def test_format_or(self):
 281     values = ('linux', 'mac', 'win')
 282     expectations = [
 283         # No variable is bound. It's the 'global variable'.
 284         (0, ('', 0)),
 285         (1, ('OS=="linux"', 1)),
 286         (2, ('OS=="mac"', 1)),
 287         (3, ('OS=="linux" or OS=="mac"', 2)),
 288         (4, ('OS=="win"', 1)),
 289         (5, ('OS=="linux" or OS=="win"', 2)),
 290         (6, ('OS=="mac" or OS=="win"', 2)),
 291         (7, ('OS=="linux" or OS=="mac" or OS=="win"', 3)),
 292     ]
 293     for data, expected in expectations:
 294       self.assertEqual(
 295           expected, short_expression_finder._format_or('OS', values, data))
 296
 297   def test_format_and(self):
 298     # Create a 2D matrix.
 299     variables = ('chromeos', 'OS')
 300     values = ((0, 1), ('linux', 'mac', 'win'))
 301     expectations = [
 302         # No variable is bound. It's the 'global variable'.
 303         ((0, 0), ('', 0)),
 304         ((0, 1), ('OS=="linux"', 1)),
 305         ((0, 2), ('OS=="mac"', 1)),
 306         ((0, 3), ('OS=="linux" or OS=="mac"', 1)),
 307         ((1, 4), ('chromeos==0 and OS=="win"', 2)),
 308         ((1, 5), ('chromeos==0 and (OS=="linux" or OS=="win")', 2)),
 309         # _format_and() just renders what it receives.
 310         (
 311           (3, 5),
 312           ('(chromeos==0 or chromeos==1) and (OS=="linux" or OS=="win")', 2),
 313         ),
 314     ]
 315     for data, expected in expectations:
 316       self.assertEqual(
 317           expected,
 318           short_expression_finder._format_and(variables, values, data))
 319
 320   def test_format_expr(self):
 321     # Create a 2D matrix.
 322     variables = ('chromeos', 'OS')
 323     values = ((0, 1), ('linux', 'mac', 'win'))
 324     expectations = [
 325         (
 326           # Unbounded variable has a 0 as its bitfield.
 327           ((0, 0),),
 328           ('', 0),
 329         ),
 330         (
 331           # Unbounded variable has a 0 as its bitfield.
 332           ((0, 1),),
 333           ('OS=="linux"', 1),
 334         ),
 335         (
 336           # The function expects already reduced and sorted equations. It won't
 337           # reduce it on your behalf.
 338           ((0, 1),(2, 1)),
 339           ('OS=="linux" or (chromeos==1 and OS=="linux")', 2),
 340         ),
 341         (
 342           ((2, 0),(0, 4)),
 343           ('chromeos==1 or OS=="win"', 2),
 344         ),
 345         (
 346           # Notice smart use of parenthesis.
 347           ((1, 1),(0, 5)),
 348           ('(chromeos==0 and OS=="linux") or OS=="linux" or OS=="win"', 2),
 349         ),
 350     ]
 351     for data, expected in expectations:
 352       self.assertEqual(
 353           expected,
 354           short_expression_finder._format_expr(variables, values, data))
 355
 356   def test_internal_guts_2_variables(self):
 357     # chromeos can be: 0 or 1.
 358     # OS can be: linux, mac or win.
 359     variables = ('chromeos', 'OS')
 360     values = ((0, 1), ('linux', 'mac', 'win'))
 361
 362     # 1. is input data to _get_expr. It is all the possibilities that should be
 363     #    be matched for.
 364     # 2. is (bits, values) output from _get_expr, that is input in
 365     #    _find_reduced_cost.
 366     # 3. is (assertions) output from _find_reduced_cost, that is input in
 367     #    _format_expr.
 368     # 4. is string output from _format_expr.
 369     expectations = [
 370         (
 371           [(0, 'linux')],
 372           1L,
 373           ((1, 1),),
 374           ('chromeos==0 and OS=="linux"', 2),
 375         ),
 376         (
 377           [(1, 'linux'), (0, 'mac')],
 378           6L,
 379           ((2, 1), (1, 2)),
 380           ('(chromeos==1 and OS=="linux") or (chromeos==0 and OS=="mac")', 2),
 381         ),
 382         (
 383           [(1, 'linux'), (0, 'mac'), (0, 'win')],
 384           22L,
 385           ((2, 1), (1, 6)),
 386           (
 387             '(chromeos==1 and OS=="linux") or '
 388             '(chromeos==0 and (OS=="mac" or OS=="win"))',
 389             2,
 390           ),
 391         ),
 392     ]
 393     for line in expectations:
 394       # Note that none of these functions support free variable. It's
 395       # implemented by ShortExpressionFinder.get_expr(.
 396       to_get_expr, bits, to_format_expr, final_expected = line
 397       self.assertEqual(
 398           bits,
 399           short_expression_finder._get_expr(values, to_get_expr))
 400       self.assertEqual(
 401           to_format_expr,
 402           short_expression_finder._find_reduced_cost(1, 1, values, bits))
 403       self.assertEqual(
 404           final_expected,
 405           short_expression_finder._format_expr(
 406             variables, values, to_format_expr))
 407
 408   def test_internal_guts_4_variables(self):
 409     # Create a 4D matrix.
 410     # See test_internal_guts_2_variables for the explanations.
 411     variables = ('lib', 'cros', 'OS', 'brand')
 412     values = (('s', 'c'), (0, 1), ('l', 'm', 'w'), ('C', 'GC', 'Y'))
 413     expectations = [
 414         (
 415           [('s', 0, 'l', 'C')],
 416           1L,
 417           ((1, 1, 1, 1),),
 418           ('lib=="s" and cros==0 and OS=="l" and brand=="C"', 4),
 419         ),
 420         (
 421           # 2nd value for 1th variable.
 422           [('c', 0, 'l', 'C')],
 423           2L,
 424           ((2, 1, 1, 1),),
 425           ('lib=="c" and cros==0 and OS=="l" and brand=="C"', 4),
 426         ),
 427         (
 428           # 2nd value for 2th variable.
 429           [('s', 1, 'l', 'C')],
 430           4L,
 431           ((1, 2, 1, 1),),
 432           ('lib=="s" and cros==1 and OS=="l" and brand=="C"', 4),
 433         ),
 434         (
 435           # 2nd value for 3th variable.
 436           [('s', 0, 'm', 'C')],
 437           16L,
 438           ((1, 1, 2, 1),),
 439           ('lib=="s" and cros==0 and OS=="m" and brand=="C"', 4),
 440         ),
 441         (
 442           # 3nd value for 3th variable.
 443           [('s', 0, 'w', 'C')],
 444           256L,
 445           ((1, 1, 4, 1),),  # bitfields, not numbers.
 446           ('lib=="s" and cros==0 and OS=="w" and brand=="C"', 4),
 447         ),
 448         (
 449           # 2nd value for 4th variable.
 450           [('s', 0, 'l', 'GC')],
 451           4096L,
 452           ((1, 1, 1, 2),),
 453           ('lib=="s" and cros==0 and OS=="l" and brand=="GC"', 4),
 454         ),
 455         (
 456           # Last bit that can be set, all values are the last.
 457           # 100000000000000000000000000000000000 is 36th bit == 2*2*3*3.
 458           [('c', 1, 'w', 'Y')],
 459           34359738368L,
 460           ((2, 2, 4, 4),),
 461           ('lib=="c" and cros==1 and OS=="w" and brand=="Y"', 4),
 462         ),
 463         (
 464           # Same condition twice doesn't affect the result.
 465           [('s', 0, 'l', 'C'), ('s', 0, 'l', 'C')],
 466           # One real condition, only one bit set.
 467           1L,
 468           ((1, 1, 1, 1),),
 469           ('lib=="s" and cros==0 and OS=="l" and brand=="C"', 4),
 470         ),
 471         (
 472           # All values for 1st variable.
 473           [('s', 0, 'l', 'C'), ('c', 0, 'l', 'C')],
 474           # It has 2 bits set.
 475           3L,
 476           ((3, 1, 1, 1),),
 477           ('(lib=="s" or lib=="c") and cros==0 and OS=="l" and brand=="C"', 4),
 478         ),
 479         (
 480           # All values for 2nd variable.
 481           [('s', 0, 'l', 'C'), ('s', 1, 'l', 'C')],
 482           # It has 2 bits set.
 483           5L,
 484           ((1, 3, 1, 1),),
 485           ('lib=="s" and (cros==0 or cros==1) and OS=="l" and brand=="C"', 4),
 486         ),
 487     ]
 488     for line in expectations:
 489       # Note that none of these functions support free variable. It's
 490       # implemented by ShortExpressionFinder.get_expr().
 491       to_get_expr, bits, to_format_expr, final_expected = line
 492       self.assertEqual(
 493           bits,
 494           short_expression_finder._get_expr(values, to_get_expr))
 495       self.assertEqual(
 496           to_format_expr,
 497           short_expression_finder._find_reduced_cost(1, 1, values, bits))
 498       self.assertEqual(
 499           final_expected,
 500           short_expression_finder._format_expr(
 501             variables, values, to_format_expr))
 502
 503
 504 if __name__ == '__main__':
 505   VERBOSE = '-v' in sys.argv
 506   unittest.main()