From acb28e922bec72e5901810d53d7746d9978185f1 Mon Sep 17 00:00:00 2001 From: wm4 Date: Mon, 18 Sep 2017 22:35:37 +0200 Subject: build: use unified dependency expressions instead of weird fields Instead of "deps", "deps_neg", and "deps_any" fields, just have a single "deps" field, which changes from an array to a string. The string is now an expression, which can contain the operators &&, ||, !, and allows grouping with ( ). It's probably overkill. If it gets a maintenance burden, we can switch to specifiying the dep expressions as ASTs (or maybe eval()-able Python expressions), and we could simplify the code that determines the reason why a dependency is not fulfilled. The latter involves a complicated conversion of the expression AST to DNF. The parser is actually pretty simple, and pretty much follows: https://en.wikipedia.org/wiki/Shunting_yard_algorithm --- waftools/dependencies.py | 64 ++++++-------- waftools/deps_parser.py | 218 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 242 insertions(+), 40 deletions(-) create mode 100644 waftools/deps_parser.py (limited to 'waftools') diff --git a/waftools/dependencies.py b/waftools/dependencies.py index 994e1d10b2..3cef6a3562 100644 --- a/waftools/dependencies.py +++ b/waftools/dependencies.py @@ -2,6 +2,7 @@ from waflib.Errors import ConfigurationError, WafError from waflib.Configure import conf from waflib.Build import BuildContext from waflib.Logs import pprint +import deps_parser import inflector class DependencyError(Exception): @@ -16,11 +17,9 @@ class Dependency(object): self.attributes = self.__parse_attributes__(dependency) known_deps.add(self.identifier) - for dep_key in ['deps', 'deps_any', 'deps_neg']: - if dep_key in self.attributes: - deps = self.attributes[dep_key] - self.ctx.ensure_dependency_is_known(*deps) + if 'deps' in self.attributes: + self.ctx.ensure_dependency_is_known(self.attributes['deps']) def __parse_attributes__(self, dependency): if 'os_specific_checks' in dependency: @@ -36,9 +35,7 @@ class Dependency(object): try: self.check_group_disabled() self.check_disabled() - self.check_any_dependencies() self.check_dependencies() - self.check_negative_dependencies() except DependencyError: # No check was run, since the prerequisites of the dependency are # not satisfied. Make sure the define is 'undefined' so that we @@ -67,27 +64,12 @@ class Dependency(object): self.attributes['fmsg'] = "You manually enabled the feature '{0}', but \ the autodetection check failed.".format(self.identifier) - def check_any_dependencies(self): - if 'deps_any' in self.attributes: - deps = set(self.attributes['deps_any']) - if len(deps & self.satisfied_deps) == 0: - self.skip("not found any of {0}".format(", ".join(deps))) - raise DependencyError - def check_dependencies(self): if 'deps' in self.attributes: - deps = set(self.attributes['deps']) - if not deps <= self.satisfied_deps: - missing_deps = deps - self.satisfied_deps - self.skip("{0} not found".format(", ".join(missing_deps))) - raise DependencyError - - def check_negative_dependencies(self): - if 'deps_neg' in self.attributes: - deps = set(self.attributes['deps_neg']) - conflicting_deps = deps & self.satisfied_deps - if len(conflicting_deps) > 0: - self.skip("{0} found".format(", ".join(conflicting_deps)), 'CYAN') + ok, why = deps_parser.check_dependency_expr(self.attributes['deps'], + self.satisfied_deps) + if not ok: + self.skip(why) raise DependencyError def check_autodetect_func(self): @@ -145,13 +127,19 @@ def configure(ctx): __detect_target_os_dependency__(ctx) @conf -def ensure_dependency_is_known(ctx, *depnames): - deps = set([d for d in depnames if not d.startswith('os-')]) - if not deps <= ctx.known_deps: - raise ConfigurationError( - "error in dependencies definition: some dependencies in" - " {0} are unknown.".format(deps)) - +def ensure_dependency_is_known(ctx, depnames): + def check(ast): + if isinstance(ast, deps_parser.AstSym): + if (not ast.name.startswith('os-')) and ast.name not in ctx.known_deps: + raise ConfigurationError( + "error in dependencies definition: dependency {0} in" + " {1} is unknown.".format(ast.name, depnames)) + elif isinstance(ast, deps_parser.AstOp): + for sub in ast.sub: + check(sub) + else: + assert False + check(deps_parser.parse_expr(depnames)) @conf def mark_satisfied(ctx, dependency_identifier): @@ -174,7 +162,9 @@ def parse_dependencies(ctx, dependencies): @conf def dependency_satisfied(ctx, dependency_identifier): ctx.ensure_dependency_is_known(dependency_identifier) - return dependency_identifier in ctx.satisfied_deps + ok, _ = deps_parser.check_dependency_expr(dependency_identifier, + ctx.satisfied_deps) + return ok @conf def store_dependencies_lists(ctx): @@ -194,13 +184,7 @@ def filtered_sources(ctx, sources): return source def __check_filter__(dependency): - if dependency.find('!') == 0: - dependency = dependency.lstrip('!') - ctx.ensure_dependency_is_known(dependency) - return dependency not in ctx.satisfied_deps - else: - ctx.ensure_dependency_is_known(dependency) - return dependency in ctx.satisfied_deps + return dependency_satisfied(ctx, dependency) def __unpack_and_check_filter__(source): try: diff --git a/waftools/deps_parser.py b/waftools/deps_parser.py new file mode 100644 index 0000000000..ef7888da30 --- /dev/null +++ b/waftools/deps_parser.py @@ -0,0 +1,218 @@ + +class ParseError(Exception): + pass + +class AstOp(object): + def __init__(self, op, sub): + self.op = op + self.sub = sub + + def __repr__(self): + if len(self.sub) == 1: + return self.op + str(self.sub[0]) + return "(" + (" " + self.op + " ").join([str(x) for x in self.sub]) + ")" + +class AstSym(object): + def __init__(self, name): + assert type(name) is type("") + self.name = name + + def __repr__(self): + return self.name + +Arity = { "!": 1, "&&": 2, "||": 2 } +Precedence = { "!": 3, "&&": 2, "||": 1 } +Tokens = list(Arity.keys()) + ["(", ")"] + +# return (token, rest), or (None, "") if nothing left +def read_tok(expr): + expr = expr.strip() + for t in Tokens: + if expr.startswith(t): + return (t, expr[len(t):]) + if expr == "": + return (None, "") + sym = "" + while len(expr) and ((expr[0].lower() >= 'a' and expr[0].lower() <= 'z') or + (expr[0] >= '0' and expr[0] <= '9') or + (expr[0] in ["_", "-", "."])): + sym += expr[0] + expr = expr[1:] + if len(sym): + return sym, expr + raise ParseError("unknown token in '%s'" % expr) + +def parse_expr(expr): + opstack = [] + outstack = [] + def out(sym): + if sym in Arity: + sub = [] + for i in range(Arity[sym]): + if len(outstack) == 0: + raise ParseError("missing operator argument") + sub.insert(0, outstack.pop()) + outstack.append(AstOp(sym, sub)) + elif sym == "(": + raise ParseError("missing closing ')'") + elif not isinstance(sym, AstSym): + raise ParseError("bogus symbol '%s'" % sym) + else: + outstack.append(sym) + while True: + tok, expr = read_tok(expr) + if tok is None: + break + if tok in Arity: + while len(opstack) and opstack[-1] != '(' and \ + Precedence[opstack[-1]] > Precedence[tok]: + out(opstack.pop()) + opstack.append(tok) + elif tok == "(": + opstack.append(tok) + elif tok == ")": + while True: + if not len(opstack): + raise ParseError("missing '(' for ')'") + sym = opstack.pop() + if sym == "(": + break + out(sym) + else: + out(AstSym(tok)) # Assume a terminal + while len(opstack): + out(opstack.pop()) + if len(outstack) != 1: + raise ParseError("empty expression or extra symbols (%s)" % outstack) + return outstack.pop() + +def convert_dnf(ast): + + # no nested ! (negation normal form) + def simplify_negation(ast): + if isinstance(ast, AstOp): + if ast.op == "!": + sub = ast.sub[0] + if isinstance(sub, AstOp): + if sub.op == "!": + return sub.sub[0] + elif sub.op in ["&&", "||"]: + sub.op = "||" if sub.op == "&&" else "&&" + sub.sub = [AstOp("!", [x]) for x in sub.sub] + return simplify_negation(sub) + else: + ast.sub = [simplify_negation(x) for x in ast.sub] + return ast + + # a && (b && c) => a && b && c + def flatten(ast): + if isinstance(ast, AstOp): + can_flatten = ast.op in ["&&", "||"] + nsub = [] + for sub in ast.sub: + sub = flatten(sub) + if isinstance(sub, AstOp) and sub.op == ast.op and can_flatten: + nsub.extend(sub.sub) + else: + nsub.append(sub) + ast.sub = nsub + if len(ast.sub) == 1 and can_flatten: + return ast.sub[0] + return ast + + # a && (b || c) && d => (a && d && b) || (a && d && c) + def redist(ast): + def recombine(a, stuff): + return AstOp("||", [AstOp("&&", [a, n]) for n in stuff]) + if isinstance(ast, AstOp): + ast.sub = [flatten(redist(x)) for x in ast.sub] + if ast.op == "&&": + for sub in ast.sub: + if isinstance(sub, AstOp) and sub.op == "||": + if len(ast.sub) == 1: + return redist(sub) + other = None + for n in ast.sub: + if n is not sub: + if other is None: + other = n + else: + other = flatten(AstOp("&&", [other, n])) + return flatten(redist(recombine(other, sub.sub))) + return ast + + return redist(flatten(simplify_negation(ast))) + +# Returns (success_as_bool, failure_reason_as_string) +def check_dependency_expr(expr, deps): + ast = parse_expr(expr) + def eval_ast(ast): + if isinstance(ast, AstSym): + return ast.name in deps + elif isinstance(ast, AstOp): + vals = [eval_ast(x) for x in ast.sub] + if ast.op == "&&": + return vals[0] and vals[1] + elif ast.op == "||": + return vals[0] or vals[1] + elif ast.op == "!": + return not vals[0] + assert False + if eval_ast(ast): + return True, None + + # Now the same thing again, but more complicated, and informing what is + # missing. + ast = convert_dnf(ast) + + # ast now is a or-combined list of and-combined deps. Each dep can have a + # negation (marking a conflict). Each case of and-combined deps is a way + # to satisfy the deps expression. Instead of dumping full information, + # distinguish the following cases, and only mention the one that applies, + # in order: + # 1. the first missing dep of a case that has missing deps only + # 2. the first conflicting dep at all + + def do_op(ast, op, cb): + if isinstance(ast, AstOp) and ast.op == op: + for sub in ast.sub: + cb(sub) + else: + cb(ast) + + def get_sub_list(node, op): + if isinstance(node, AstOp) and node.op == op: + return node.sub + else: + return [node] + + conflict_dep = None + missing_dep = None + + for group in get_sub_list(ast, "||"): + group_conflict = None + group_missing_dep = None + for elem in get_sub_list(group, "&&"): + neg = False + if isinstance(elem, AstOp) and elem.op == "!": + neg = True + elem = elem.sub[0] + if not isinstance(elem, AstSym): + continue # broken DNF? + name = elem.name + present = name in deps + if (not present) and (not neg) and (group_missing_dep is None): + group_missing_dep = name + if present and neg and (group_conflict is None): + group_conflict = name + if (missing_dep is None) and (group_conflict is None): + missing_dep = group_missing_dep + if conflict_dep is None: + conflict_dep = group_conflict + + reason = "unknown" + if missing_dep is not None: + reason = "%s not found" % (missing_dep) + elif conflict_dep is not None: + reason = "%s found" % (conflict_dep) + return False, reason -- cgit v1.2.3