Add helper for splitting expressions

I've had to implement the logic for walking reverse dependencies (from
select) a couple of times now, and it's always a bit tricky to get
right. Reduce code duplication and simplify things by adding a helper
function split_expr() that splits an expression into a list of either
its AND or OR operands.

A nice side effect is that e.g. the warning generated for selecting a
symbol with unsatisfied direct dependencies now lists the selecting
symbols in the order that they appear in the Kconfig files.

split_expr() might be helpful for splitting other types of expressions
as well, e.g. to put operands on separate lines when generating
documentation.

2 files changed, 109 insertions, 44 deletions

diff --git a/kconfiglib.py b/kconfiglib.py
index d9cd4f0..487fd56 100644
--- a/kconfiglib.py
+++ b/kconfiglib.py
@@ -3390,53 +3390,36 @@ class Symbol(object):
         # unsatisfied direct dependencies (dependencies from 'depends on', ifs,
         # and menus) is selected by some other symbol
 
-        def check_select(select):
-            # Returns a warning string if 'select' is actually selecting us,
-            # and the empty string otherwise. nonlocal would be handy for
-            # appending to warn_msg directly, but it's Python 3 only.
+        msg = "{} has unsatisfied direct dependencies ({}), but is " \
+              "currently being selected by the following symbols:" \
+              .format(_name_and_loc(self), expr_str(self.direct_dep))
 
+        # The reverse dependencies from each select are ORed together
+        for select in split_expr(self.rev_dep, OR):
             select_val = expr_value(select)
             if not select_val:
                 # Only include selects that are not n
-                return ""
+                continue
 
-            if isinstance(select, tuple):
-                # (AND, <sym>, <condition>)
-                selecting_sym = select[1]
-            else:
-                # <sym>
-                selecting_sym = select
+            # - 'select A if B' turns into A && B
+            # - 'select A' just turns into A
+            #
+            # In both cases, we can split on AND and pick the first operand
+            selecting_sym = split_expr(select, AND)[0]
 
-            msg = "\n - {}, with value {}, direct dependencies {} " \
-                  "(value: {})" \
-                  .format(_name_and_loc(selecting_sym),
-                          selecting_sym.str_value,
-                          expr_str(selecting_sym.direct_dep),
-                          TRI_TO_STR[expr_value(selecting_sym.direct_dep)])
+            msg += "\n - {}, with value {}, direct dependencies {} " \
+                   "(value: {})" \
+                   .format(_name_and_loc(selecting_sym),
+                           selecting_sym.str_value,
+                           expr_str(selecting_sym.direct_dep),
+                           TRI_TO_STR[expr_value(selecting_sym.direct_dep)])
 
             if isinstance(select, tuple):
                 msg += ", and select condition {} (value: {})" \
                        .format(expr_str(select[2]),
                                TRI_TO_STR[expr_value(select[2])])
 
-            return msg
-
-        warn_msg = "{} has unsatisfied direct dependencies ({}), but is " \
-                   "currently being selected by the following symbols:" \
-                   .format(_name_and_loc(self), expr_str(self.direct_dep))
-
-        # This relies on us using the following format for the select
-        # expression:
-        #
-        #   (OR, (OR, (OR, <expr 1>, <expr 2>), <expr 3>), <expr 4>)
-        expr = self.rev_dep
-        while isinstance(expr, tuple) and expr[0] == OR:
-            warn_msg += check_select(expr[2])
-            # Go to next select
-            expr = expr[1]
-        warn_msg += check_select(expr)
-
-        self.kconfig._warn(warn_msg)
+        self.kconfig._warn(msg)
 
 class Choice(object):
     """
@@ -4159,6 +4142,50 @@ def expr_str(expr):
                              _REL_TO_STR[expr[0]],
                              expr_str(expr[2]))
 
+def split_expr(expr, op):
+    """
+    Returns a list containing the top-level AND or OR operands in the
+    expression 'expr', in the same (left-to-right) order as they appear in
+    the expression.
+
+    This can be handy e.g. for splitting (weak) reverse dependencies
+    from 'select' and 'imply' into individual selects/implies.
+
+    op:
+      Either AND to get AND operands, or OR to get OR operands.
+
+      (Having this as an operand might be more future-safe than having two
+      hardcoded functions.)
+
+
+    Pseudo-code examples:
+
+      split_expr( A                    , OR  )  ->  [A]
+      split_expr( A && B               , OR  )  ->  [A && B]
+      split_expr( A || B               , OR  )  ->  [A, B]
+      split_expr( A || B               , AND )  ->  [A || B]
+      split_expr( A || B || (C && D)   , OR  )  ->  [A, B, C && D]
+
+      # Second || is not at the top level
+      split_expr( A || (B && (C || D)) , OR )  ->  [A, B && (C || D)]
+
+      # Parentheses don't matter as long as we stay at the top level (don't
+      # encounter any non-'op' nodes)
+      split_expr( (A || B) || C        , OR )  ->  [A, B, C]
+      split_expr( A || (B || C)        , OR )  ->  [A, B, C]
+    """
+    res = []
+
+    def rec(subexpr):
+        if isinstance(subexpr, tuple) and subexpr[0] == op:
+            rec(subexpr[1])
+            rec(subexpr[2])
+        else:
+            res.append(subexpr)
+
+    rec(expr)
+    return res
+
 def escape(s):
     r"""
     Escapes the string 's' in the same fashion as is done for display in
@@ -4697,15 +4724,11 @@ def _warn_choice_select_imply(sym, expr, expr_type):
     msg = "the choice symbol {} is {} by the following symbols, which has " \
           "no effect: ".format(_name_and_loc(sym), expr_type)
 
-    while isinstance(expr, tuple) and expr[0] == OR:
-        msg += _select_imply_str(expr[2])
-        expr = expr[1]
-
-    sym.kconfig._warn(msg + _select_imply_str(expr))
+    # si = select/imply
+    for si in split_expr(expr, OR):
+        msg += "\n - " + _name_and_loc(split_expr(si, AND)[0])
 
-def _select_imply_str(select):
-    return "\n - " + \
-        _name_and_loc(select[1] if isinstance(select, tuple) else select)
+    sym.kconfig._warn(msg)
 
 #
 # Public global constants
diff --git a/testsuite.py b/testsuite.py
index 0cbe5d0..9a2f1fc 100644
--- a/testsuite.py
+++ b/testsuite.py
@@ -44,7 +44,10 @@
 from kconfiglib import Kconfig, Symbol, Choice, COMMENT, MENU, \
                        BOOL, TRISTATE, HEX, STRING, \
                        TRI_TO_STR, \
-                       KconfigSyntaxError, expr_value, escape, unescape
+                       escape, unescape, \
+                       expr_str, expr_value, split_expr, \
+                       OR, AND, \
+                       KconfigSyntaxError
 import difflib
 import errno
 import os
@@ -849,6 +852,45 @@ g
         fail("recursive 'source' did not raise exception")
 
 
+    print("Testing split_expr()")
+
+    def verify_split(to_split, op, operand_strs):
+        # The same hackage as in Kconfig.eval_string()
+        c._line = "if " + to_split
+        c._tokenize()
+        del c._tokens[0]
+        operands = split_expr(c._parse_expr(False), op)
+
+        verify(len(operands) == len(operand_strs),
+               "Wrong number of operands when {} was split by {}"
+               .format(to_split, "OR" if op == OR else "AND"))
+
+        for operand, operand_str in zip(operands, operand_strs):
+            verify_equal(expr_str(operand), operand_str)
+
+    verify_split("A",                    OR, ("A",                ))
+    verify_split("!A",                   OR, ("!A",               ))
+    verify_split("A = B",                OR, ("A = B",            ))
+    verify_split("A && B",               OR, ("A && B",           ))
+    verify_split("A || B",               OR, ("A", "B"            ))
+    verify_split("(A || B) || C",        OR, ("A", "B", "C"       ))
+    verify_split("A || (B || C)",        OR, ("A", "B", "C"       ))
+    verify_split("A || !(B || C)",       OR, ("A", "!(B || C)"    ))
+    verify_split("A || (B && (C || D))", OR, ("A", "B && (C || D)"))
+    verify_split("(A && (B || C)) || D", OR, ("A && (B || C)", "D"))
+
+    verify_split("A",                    AND, ("A",                ))
+    verify_split("!A",                   AND, ("!A",               ))
+    verify_split("A = B",                AND, ("A = B",            ))
+    verify_split("A || B",               AND, ("A || B",           ))
+    verify_split("A && B",               AND, ("A", "B"            ))
+    verify_split("(A && B) && C",        AND, ("A", "B", "C"       ))
+    verify_split("A && (B && C)",        AND, ("A", "B", "C"       ))
+    verify_split("A && !(B && C)",       AND, ("A", "!(B && C)"    ))
+    verify_split("A && (B || (C && D))", AND, ("A", "B || (C && D)"))
+    verify_split("(A || (B && C)) && D", AND, ("A || (B && C)", "D"))
+
+
     print("Testing visibility")
 
     c = Kconfig("Kconfiglib/tests/Kvisibility")