conditions.py 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365
  1. # Copyright 2021 The Chromium Authors. All rights reserved.
  2. # Use of this source code is governed by a BSD-style license that can be
  3. # found in the LICENSE file.
  4. """
  5. Conditions represent a build configuration under which to disable a test.
  6. This file contains a canonical list of conditions and their properties, and code
  7. for composing, parsing, and simplifying them. This is independent of their
  8. representation within any particular test format.
  9. """
  10. import collections
  11. import functools
  12. import itertools
  13. import types
  14. from typing import List, Optional, Union, Set, Tuple
  15. import errors
  16. class BaseCondition:
  17. """BaseCondition is a class for sentinel values ALWAYS and NEVER."""
  18. # These represent a condition that's always true, and a condition that's never
  19. # true.
  20. ALWAYS = BaseCondition()
  21. NEVER = BaseCondition()
  22. @functools.total_ordering
  23. class Terminal:
  24. """A boolean variable, the value of which depends on the configuration."""
  25. def __init__(self, name: str, group: Optional[str]):
  26. """
  27. Args:
  28. name: The generic name for this terminal. Used to specify conditions on
  29. the command line.
  30. group: The group to which this condition belongs. Every Terminal with the
  31. same group is mutually exclusive. For example, "os" - we can't be
  32. compiling for Linux and Mac at the same time.
  33. We also add fields for each test format, initialised to None. It's up to the
  34. file defining the relevant code to fill these out.
  35. """
  36. self.name: str = name
  37. self.group: Optional[str] = group
  38. self.gtest_info = None
  39. self.expectations_info = None
  40. def __str__(self):
  41. return (f"Terminal('{self.name}')")
  42. def __repr__(self):
  43. return str(self)
  44. def __lt__(self, other):
  45. """Define a consistent ordering for conditions written into test files"""
  46. if not isinstance(other, Terminal):
  47. return False
  48. # Ungrouped terminals should compare greater than grouped, and compare based
  49. # on name to each-other.
  50. if (self.group is not None) == (other.group is not None):
  51. return (self.group, self.name) < (other.group, other.name)
  52. return self.group is not None
  53. # TODO: We could probably just use object identity here (and for __hash__),
  54. # since we only use a fixed set of Terminal objects.
  55. def __eq__(self, other):
  56. # Names are expected to be unique keys
  57. return isinstance(other, Terminal) and self.name == other.name
  58. def __hash__(self):
  59. return hash(self.name)
  60. # TODO: We should think about how to incorporate overlapping conditions. For
  61. # instance, multiple versions of the same OS, where we might just specify "Mac"
  62. # to refer to any version, or "Mac-10.15" for that specific version. Or "x86" to
  63. # refer to the architecture as a whole, regardless of 32 vs 64-bit.
  64. #
  65. # We could handle this via expanding the higher-level one, for instance "Mac"
  66. # being parsed directly into (or, ["Mac-10.15", "Mac-11", ...]). But we'd also
  67. # need to handle this on the other end, to reduce it back down after
  68. # simplifying.
  69. TERMINALS = [
  70. Terminal('android', group='os'),
  71. Terminal('chromeos', group='os'),
  72. Terminal('fuchsia', group='os'),
  73. Terminal('ios', group='os'),
  74. Terminal('linux', group='os'),
  75. Terminal('mac', group='os'),
  76. Terminal('win', group='os'),
  77. Terminal('arm64', group='arch'),
  78. Terminal('x86', group='arch'),
  79. Terminal('x86-64', group='arch'),
  80. Terminal('lacros', group='lacros/ash'),
  81. Terminal('ash', group='lacros/ash'),
  82. Terminal('asan', group=None),
  83. Terminal('msan', group=None),
  84. Terminal('tsan', group=None),
  85. ]
  86. # Terminals should have unique names.
  87. assert len({t.name for t in TERMINALS}) == len(TERMINALS)
  88. # A condition can be one of three things:
  89. # 1. A BaseCondition (ALWAYS or NEVER).
  90. # 2. An operator, represented as a tuple with the operator name followed by its
  91. # arguments.
  92. # 3. A Terminal.
  93. Condition = Union[BaseCondition, tuple, Terminal]
  94. def get_term(name: str) -> Terminal:
  95. """Look up a Terminal by name."""
  96. t = next((t for t in TERMINALS if t.name == name), None)
  97. if t is not None:
  98. return t
  99. raise ValueError(f"Unknown condition '{name}'")
  100. # TODO: We should check that the parsed condition makes sense with respect to
  101. # condition groups. For instance, the condition 'linux & mac' can never be true.
  102. def parse(condition_strs: List[str]) -> Condition:
  103. """Parse a list of condition strings, as passed on the command line.
  104. Each element of condition_strs is a set of Terminal names joined with '&'s.
  105. The list is implicitly 'or'ed together.
  106. """
  107. # When no conditions are given, this is taken to mean "always".
  108. if not condition_strs:
  109. return ALWAYS
  110. try:
  111. return op_of('or', [
  112. op_of('and', [get_term(x.strip()) for x in cond.split('&')])
  113. for cond in condition_strs
  114. ])
  115. except ValueError as e:
  116. # Catching the exception raised by get_term.
  117. valid_conds = '\n'.join(sorted(f'\t{term.name}' for term in TERMINALS))
  118. raise errors.UserError(f"{e}\nValid conditions are:\n{valid_conds}")
  119. def op_of(op: str, args: List[Condition]) -> Condition:
  120. """Make an operator, simplifying the single-argument case."""
  121. if len(args) == 1:
  122. return args[0]
  123. return (op, args)
  124. def merge(existing_cond: Condition, new_cond: Condition) -> Condition:
  125. """Merge two conditions together.
  126. Given an existing condition, parsed from a file, and a new condition to be
  127. added, combine the two to produce a merged condition.
  128. """
  129. # If currently ALWAYS, merging would only ever produce ALWAYS too. In this
  130. # case the user likely want to change the conditions or re-enable.
  131. if existing_cond == ALWAYS:
  132. return new_cond
  133. # If currently NEVER, ignore the current value - NEVER or X = X
  134. if existing_cond == NEVER:
  135. return new_cond
  136. # If new cond is ALWAYS, ignore the current value - X or ALWAYS = ALWAYS
  137. if new_cond == ALWAYS:
  138. return ALWAYS
  139. # Similar to the first branch, if the user has specified NEVER then ignore the
  140. # current value, as they're re-enabling it.
  141. if new_cond == NEVER:
  142. return NEVER
  143. # Otherwise, take the union of the two conditions
  144. cond = ('or', [existing_cond, new_cond])
  145. return simplify(cond)
  146. def generate_condition_groups(terms: List[Terminal]) -> List[Set[Terminal]]:
  147. """Partition a list of Terminals by their 'group' attribute."""
  148. by_group = collections.defaultdict(set)
  149. ungrouped = []
  150. for term in terms:
  151. if term.group is not None:
  152. by_group[term.group].add(term)
  153. else:
  154. # Every Terminal without a 'group' attribute gets its own group, as
  155. # they're not mutually exclusive with anything.
  156. ungrouped.append({term})
  157. groups = list(by_group.values())
  158. groups += ungrouped
  159. return groups
  160. # Pre-compute condition groups for use when simplifying.
  161. CONDITION_GROUPS = generate_condition_groups(TERMINALS)
  162. def simplify(cond: Condition) -> Condition:
  163. """Given a Condition, produce an equivalent but simpler Condition.
  164. This function uses the Quine-McCluskey algorithm. It's not implemented very
  165. efficiently, but it works and is fast enough for now.
  166. """
  167. if isinstance(cond, BaseCondition):
  168. return cond
  169. # Quine-McCluskey uses three values - true, false, and "don't care". The
  170. # latter represents two things:
  171. # * For values of input variables, the case where either true or false will
  172. # suffice. This is used when combining conditions that differ only in that
  173. # variable into one where that variable isn't specified.
  174. # * For resulting values of the function, the case where we don't care what
  175. # value the function produces. We use this for mutually exclusive
  176. # conditions. For example, (linux & mac) is impossible, so we assign this a
  177. # "don't care" value. This avoids producing a bunch of redundant stuff like
  178. # (linux & ~mac).
  179. DONT_CARE = 2
  180. # First, compute the truth table of the function. We produce a set of
  181. # "minterms", which are the combinations of input values for which the output
  182. # is 1. We also produce a set of "don't care" values, which are the
  183. # combinations of input values for which we don't care what the output is.
  184. #
  185. # Both of these are represented via tuples of {0, 1} values, which the value
  186. # at index 'i' corresponds to variables[i].
  187. # TODO: This could use a more efficient representation. Some packed integer
  188. # using two bits per element or something.
  189. variables = list(sorted(find_terminals(cond)))
  190. dont_cares = []
  191. min_terms = []
  192. for possible_input in itertools.product([0, 1], repeat=len(variables)):
  193. # Generate every possible input, and evaluate the condition for that input.
  194. # This is exponential in the number of variables, but in practice the number
  195. # should be low (and is strictly bounded by len(TERMINALS)).
  196. true_vars = {variables[i] for i, val in enumerate(possible_input) if val}
  197. if any(len(group & true_vars) > 1 for group in CONDITION_GROUPS):
  198. # Any combination which sets more than one variable from the same group to
  199. # 1 is impossible, so we don't care about the output.
  200. dont_cares.append(possible_input)
  201. elif evaluate(cond, true_vars):
  202. min_terms.append(possible_input)
  203. # The meat of the algorithm. Try to combine minterms which differ by only a
  204. # single variable.
  205. # For example, (0, 1) and (0, 0) can be combined into (0, DONT_CARE), as the
  206. # value of the second variable doesn't affect the output.
  207. #
  208. # We work in rounds, combining together all minterms from the previous round
  209. # that can be. This may include combining the same minterm with multiple
  210. # different minterms. Keep going until no more minterms can be combined.
  211. #
  212. # Any minterm which can't be combined with another is a "prime implicant",
  213. # that is, it's a necessary part of the representation of the function. The
  214. # union of all prime implicants specifies the function.
  215. combined_some_minterms = True
  216. prev_round = set(min_terms + dont_cares)
  217. prime_implicants: List[Tuple] = []
  218. while combined_some_minterms:
  219. new_implicants = set()
  220. used = set()
  221. combined_some_minterms = False
  222. # TODO: Rather than taking combinations of the entire set of minterms, we
  223. # can instead group by the number of '1's. Then we only need to combine
  224. # elements from adjacent groups.
  225. for a, b in itertools.combinations(prev_round, 2):
  226. diff_index = None
  227. for i, (x, y) in enumerate(zip(a, b)):
  228. if x != y:
  229. if diff_index is not None:
  230. # In this case there are at least two points of difference, so these
  231. # two can't be combined.
  232. break
  233. diff_index = i
  234. else:
  235. if diff_index is not None:
  236. # Replace the sole differing variable with DONT_CARE to produce the
  237. # combined minterm. Flag both inputs as having been used, and
  238. # therefore as not being prime implicants.
  239. new_implicants.add(a[:diff_index] + (DONT_CARE, ) +
  240. a[diff_index + 1:])
  241. used |= {a, b}
  242. combined_some_minterms = True
  243. # Collect any minterms that weren't used in this round as prime implicants.
  244. prime_implicants.extend(prev_round - used)
  245. prev_round = new_implicants
  246. # TODO: This isn't yet minimal - the set of prime implicants may have some
  247. # redundancy which can be reduced further. For now we just accept that and
  248. # use this set as-is. If we encounter any case for which we don't produce the
  249. # minimal result, we'll need to implement something like Petrick's method.
  250. # Finally, create our simplified condition using the computed set of prime
  251. # implicants.
  252. # TODO: Ordering. We should define some stable ordering to use. We probably
  253. # want to group stuff based on CONDITION_GROUPS, so all the OS-related
  254. # conditions are together, for instance. And then alphabetically within that.
  255. or_args: List[Condition] = []
  256. for pi in sorted(prime_implicants):
  257. and_args: List[Condition] = []
  258. for i, x in enumerate(pi):
  259. if x == DONT_CARE:
  260. continue
  261. var = variables[i]
  262. if x == 0:
  263. and_args.append(('not', var))
  264. else:
  265. assert x == 1
  266. and_args.append(var)
  267. or_args.append(op_of('and', and_args))
  268. return op_of('or', or_args)
  269. def find_terminals(cond: Condition) -> Set[Terminal]:
  270. """Find all leaf Terminal nodes of this Condition."""
  271. if isinstance(cond, BaseCondition):
  272. return set()
  273. if isinstance(cond, Terminal):
  274. return {cond}
  275. assert isinstance(cond, tuple)
  276. op, args = cond
  277. if op == 'not':
  278. return find_terminals(args)
  279. return {var for arg in args for var in find_terminals(arg)}
  280. def evaluate(cond: Condition, true_vars: Set[Terminal]) -> bool:
  281. """Evaluate a condition with a given set of true variables."""
  282. if isinstance(cond, BaseCondition):
  283. return cond is ALWAYS
  284. if isinstance(cond, Terminal):
  285. return cond in true_vars
  286. # => must be a tuple
  287. op, args = cond
  288. if op == 'not':
  289. return not evaluate(args, true_vars)
  290. return {'or': any, 'and': all}[op](evaluate(arg, true_vars) for arg in args)