edtlib: propertize EDT.scc_order, set up graph earlier
Make the scc_order method a property instead. This is in keeping with
the "General biased advice" at the top of file.
The actual order is therefore lazily initialized in this commit and
the order is not computed by the time __init__() returns. The next
commit will invoke scc_order by the time the constructor returns.
This is preparation work for adding a lookup table from dependency
ordinals to nodes. The combination of these two changes will make
intializing that lookup table a bit easier.
Signed-off-by: Martí Bolívar <marti.bolivar@nordicsemi.no>
diff --git a/scripts/dts/edtlib.py b/scripts/dts/edtlib.py
index 6aab575..9c6f73c 100644
--- a/scripts/dts/edtlib.py
+++ b/scripts/dts/edtlib.py
@@ -149,6 +149,16 @@
bindings_dirs:
The bindings directory paths passed to __init__()
+ scc_order:
+ A list of lists of Nodes. All elements of each list
+ depend on each other, and the Nodes in any list do not depend
+ on any Node in a subsequent list. Each list defines a Strongly
+ Connected Component (SCC) of the graph.
+
+ For an acyclic graph each list will be a singleton. Cycles
+ will be represented by lists with multiple nodes. Cycles are
+ not expected to be present in devicetree graphs.
+
The standard library's pickle module can be used to marshal and
unmarshal EDT objects.
"""
@@ -207,10 +217,9 @@
self._init_compat2binding(bindings_dirs)
self._init_nodes()
+ self._init_graph()
self._init_luts()
- self._define_order()
-
# Drop the reference to the open warn file. This is necessary
# to make this object pickleable, but also allows it to get
# garbage collected and closed if nobody else is using it.
@@ -261,26 +270,20 @@
return "<EDT for '{}', binding directories '{}'>".format(
self.dts_path, self.bindings_dirs)
+ @property
def scc_order(self):
- """
- Returns a list of lists of Nodes where all elements of each list
- depend on each other, and the Nodes in any list do not depend
- on any Node in a subsequent list. Each list defines a Strongly
- Connected Component (SCC) of the graph.
-
- For an acyclic graph each list will be a singleton. Cycles
- will be represented by lists with multiple nodes. Cycles are
- not expected to be present in devicetree graphs.
- """
try:
return self._graph.scc_order()
except Exception as e:
raise EDTError(e)
- def _define_order(self):
+ def _init_graph(self):
# Constructs a graph of dependencies between Node instances,
- # then calculates a partial order over the dependencies. The
- # algorithm supports detecting dependency loops.
+ # which is usable for computing a partial order over the dependencies.
+ # The algorithm supports detecting dependency loops.
+ #
+ # Actually computing the SCC order is lazily deferred to the
+ # first time the scc_order property is read.
self._graph = Graph()
@@ -306,11 +309,6 @@
for intr in node.interrupts:
self._graph.add_edge(node, intr.controller)
- # Calculate an order that ensures no node is before any node
- # it depends on. This sets the dep_ordinal field in each
- # Node.
- self.scc_order()
-
def _init_compat2binding(self, bindings_dirs):
# Creates self._compat2binding. This is a dictionary that maps
# (<compatible>, <bus>) tuples (both strings) to (<binding>, <path>)
diff --git a/scripts/dts/gen_defines.py b/scripts/dts/gen_defines.py
index 3bf91f3..3895ef4 100755
--- a/scripts/dts/gen_defines.py
+++ b/scripts/dts/gen_defines.py
@@ -155,7 +155,7 @@
Nodes in dependency order (ordinal and path):
"""
- for scc in edt.scc_order():
+ for scc in edt.scc_order:
if len(scc) > 1:
err("cycle in devicetree involving "
+ ", ".join(node.path for node in scc))
diff --git a/scripts/dts/gen_legacy_defines.py b/scripts/dts/gen_legacy_defines.py
index e4b4569..0baa8d3 100755
--- a/scripts/dts/gen_legacy_defines.py
+++ b/scripts/dts/gen_legacy_defines.py
@@ -98,7 +98,7 @@
Nodes in dependency order (ordinal and path):
"""
- for scc in edt.scc_order():
+ for scc in edt.scc_order:
if len(scc) > 1:
err("cycle in devicetree involving "
+ ", ".join(node.path for node in scc))
