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