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

2 files changed, 242 insertions, 40 deletions

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