Add example that finds references to undefined symbols

Does a global search over all architectures in the kernel, which should
avoid false positives.

Referencing an undefined symbol in a particular architecture can be fine
in a Kconfig file that's shared by multiple architectures, but if the
symbol isn't defined by any architecture, it's likely to be an error (or
a potential cleanup).

3 files changed, 177 insertions, 27 deletions

diff --git a/README.rst b/README.rst
index 13385fb..ad8143f 100644
--- a/README.rst
+++ b/README.rst
@@ -203,6 +203,8 @@ The `examples/ <https://github.com/ulfalizer/Kconfiglib/blob/master/examples>`_
 
 - `print_tree.py <https://github.com/ulfalizer/Kconfiglib/blob/master/examples/print_tree.py>`_ prints a tree of all configuration items.
 
+- `list_undefined.py <https://github.com/ulfalizer/Kconfiglib/blob/master/examples/list_undefined.py>`_ finds references to symbols that are not defined by any architecture in the Linux kernel.
+
 - `merge_config.py <https://github.com/ulfalizer/Kconfiglib/blob/master/examples/merge_config.py>`_ merges configuration fragments to produce a complete .config, similarly to ``scripts/kconfig/merge_config.sh`` from the kernel.
 
 - `menuconfig.py <https://github.com/ulfalizer/Kconfiglib/blob/master/examples/menuconfig.py>`_ implements a configuration interface that uses notation similar to ``make menuconfig``. It's deliberately kept as simple as possible to demonstrate just the core concepts, and isn't something you'd actually want to use. Here's a screenshot:
diff --git a/examples/find_symbol.py b/examples/find_symbol.py
index 63790c2..b490e4d 100644
--- a/examples/find_symbol.py
+++ b/examples/find_symbol.py
@@ -167,39 +167,42 @@ def nodes_referencing_sym(node, sym_name):
 
     return res
 
-if len(sys.argv) < 3:
-    print('Pass symbol name (without "CONFIG_" prefix) with SCRIPT_ARG=<name>')
-    sys.exit(1)
+# find_undefined.py makes use nodes_referencing_sym(), so allow use to be
+# imported
+if __name__ == "__main__":
+    if len(sys.argv) < 3:
+        print('Pass symbol name (without "CONFIG_" prefix) with SCRIPT_ARG=<name>')
+        sys.exit(1)
 
-sym_name = sys.argv[2]
+    sym_name = sys.argv[2]
 
-kconf = Kconfig(sys.argv[1])
-nodes = nodes_referencing_sym(kconf.top_node, sym_name)
+    kconf = Kconfig(sys.argv[1])
+    nodes = nodes_referencing_sym(kconf.top_node, sym_name)
 
-if not nodes:
-    print("No reference to '{}' found".format(sym_name))
-    sys.exit()
+    if not nodes:
+        print("No reference to '{}' found".format(sym_name))
+        sys.exit()
 
-print("Found {} locations that reference '{}':\n".format(len(nodes), sym_name))
+    print("Found {} locations that reference '{}':\n".format(len(nodes), sym_name))
 
-for i, node in enumerate(nodes, 1):
-    print("========== Location {} ({}:{}) ==========\n".format(i, node.filename, node.linenr))
-    print(node)
+    for i, node in enumerate(nodes, 1):
+        print("========== Location {} ({}:{}) ==========\n".format(i, node.filename, node.linenr))
+        print(node)
 
-    parent_i = 0
+        parent_i = 0
 
-    # Print the parents of the menu node too
-    while True:
-        node = node.parent
-        if node is kconf.top_node:
-            # Don't print the top node. Would say something like the following,
-            # which isn't that interesting:
-            #
-            #   menu "Linux/$ARCH $KERNELVERSION Kernel Configuration"
-            break
+        # Print the parents of the menu node too
+        while True:
+            node = node.parent
+            if node is kconf.top_node:
+		# Don't print the top node. Would say something like the
+		# following, which isn't that interesting:
+                #
+		#   menu "Linux/$ARCH $KERNELVERSION Kernel Configuration"
+                break
 
-        parent_i += 1
+            parent_i += 1
 
-        print("---------- Parent {} ({}:{})  ----------\n"
-              .format(parent_i, node.filename, node.linenr))
-        print(node)
+            print("---------- Parent {} ({}:{})  ----------\n"
+                  .format(parent_i, node.filename, node.linenr))
+            print(node)
diff --git a/examples/list_undefined.py b/examples/list_undefined.py
new file mode 100644
index 0000000..56d1e4a
--- /dev/null
+++ b/examples/list_undefined.py
@@ -0,0 +1,145 @@
+# Prints a list of symbols that are referenced in the Kconfig files of some
+# architecture but not defined by the Kconfig files of any architecture.
+#
+# A Kconfig file might be shared between many architectures and legitimately
+# reference undefined symbols for some of them, but if no architecture defines
+# the symbol, it usually indicates a problem or potential cleanup.
+#
+# This script could be sped up a lot if needed. See the comment near the
+# nodes_referencing_sym() call.
+#
+# Run with the following command in the kernel root:
+#
+#   $ python(3) Kconfiglib/examples/list_undefined.py
+#
+# Example output:
+#
+#   Registering defined and undefined symbols for all arches
+#     Processing mips
+#     Processing ia64
+#     Processing metag
+#     ...
+#
+#   Finding references to each undefined symbol
+#     Processing mips
+#     Processing ia64
+#     Processing metag
+#     ...
+#
+#   The following globally undefined symbols were found, listed here
+#   together with the locations of the items that reference them.
+#   References might come from enclosing menus and ifs.
+#
+#     ARM_ERRATA_753970: arch/arm/mach-mvebu/Kconfig:56, arch/arm/mach-mvebu/Kconfig:39
+#     SUNXI_CCU_MP: drivers/clk/sunxi-ng/Kconfig:14
+#     SUNXI_CCU_DIV: drivers/clk/sunxi-ng/Kconfig:14
+#     AC97: sound/ac97/Kconfig:6
+#     ...
+from kconfiglib import Kconfig
+
+# Reuse a function from the find_symbol.py example
+from find_symbol import nodes_referencing_sym
+
+import os
+import subprocess
+
+# Referenced inside the Kconfig files
+os.environ["KERNELVERSION"] = str(
+    subprocess.check_output(("make", "kernelversion")).decode("utf-8").rstrip()
+)
+
+def all_arch_srcarch_pairs():
+    """
+    Generates all valid (ARCH, SRCARCH) tuples for the kernel, corresponding to
+    different architectures. SRCARCH holds the arch/ subdirectory.
+    """
+    for srcarch in os.listdir("arch"):
+        # Each subdirectory of arch/ containing a Kconfig file corresponds to
+        # an architecture
+        if os.path.exists(os.path.join("arch", srcarch, "Kconfig")):
+            yield (srcarch, srcarch)
+
+    # Some architectures define additional ARCH settings with ARCH != SRCARCH
+    # (search for "Additional ARCH settings for" in the top-level Makefile)
+
+    yield ("i386", "x86")
+    yield ("x86_64", "x86")
+
+    yield ("sparc32", "sparc")
+    yield ("sparc64", "sparc")
+
+    yield ("sh64", "sh")
+
+    yield ("tilepro", "tile")
+    yield ("tilegx", "tile")
+
+    yield ("um", "um")
+
+def all_arch_srcarch_kconfigs():
+    """
+    Generates Kconfig instances for all the architectures in the kernel
+    """
+    for arch, srcarch in all_arch_srcarch_pairs():
+        print("  Processing " + arch)
+
+        os.environ["ARCH"] = arch
+        os.environ["SRCARCH"] = srcarch
+
+        # um (User Mode Linux) uses a different base Kconfig file
+        yield Kconfig("Kconfig" if arch != "um" else "arch/x86/um/Kconfig",
+                      warn=False)
+
+
+print("Registering defined and undefined symbols for all arches")
+
+# Sets holding the names of all defined and undefined symbols, for all
+# architectures
+defined = set()
+undefined = set()
+
+for kconf in all_arch_srcarch_kconfigs():
+    for name, sym in kconf.syms.items():
+        if sym.nodes:
+            # If the symbol has a menu node, it is defined
+            defined.add(name)
+        else:
+            # Undefined symbol. We skip some of the uninteresting ones.
+
+            # Predefined
+            if name == "UNAME_RELEASE":
+                continue
+
+            # Due to how Kconfig works, integer literals show up as symbols
+            # (from e.g. 'default 1'). Skip those.
+            try:
+                int(name, 0)
+                continue
+            except ValueError:
+                pass
+
+            # Interesting undefined symbol
+            undefined.add(name)
+
+
+print("\nFinding references to each undefined symbol")
+
+# Maps each globally undefined symbol to the locations of the items (symbols,
+# choices, menus, ifs) that reference it
+undef_sym_refs = [(name, set()) for name in undefined - defined]
+
+for kconf in all_arch_srcarch_kconfigs():
+    for name, refs in undef_sym_refs:
+        # This means that we search the entire configuration tree for each
+        # undefined symbol, which is terribly inefficient. We could speed
+        # things up by tweaking nodes_referencing_sym() to compare each symbol
+        # to multiple symbols while walking the configuration tree.
+        for node in nodes_referencing_sym(kconf.top_node, name):
+            refs.add("{}:{}".format(node.filename, node.linenr))
+
+
+print("\nThe following globally undefined symbols were found, listed here\n"
+      "together with the locations of the items that reference them.\n"
+      "References might come from enclosing menus and ifs.\n")
+
+for name, refs in undef_sym_refs:
+    print("  {}: {}".format(name, ", ".join(refs)))