1# Copyright 2009-2013, 2019 Peter A. Bigot
2#
3# SPDX-License-Identifier: Apache-2.0
4
5# This implementation is derived from the one in
6# [PyXB](https://github.com/pabigot/pyxb), stripped down and modified
7# specifically to manage edtlib Node instances.
8
9import collections
10
11class Graph:
12    """
13    Represent a directed graph with edtlib Node objects as nodes.
14
15    This is used to determine order dependencies among nodes in a
16    devicetree.  An edge from C{source} to C{target} indicates that
17    some aspect of C{source} requires that some aspect of C{target}
18    already be available.
19    """
20
21    def __init__(self, root=None):
22        self.__roots = None
23        if root is not None:
24            self.__roots = {root}
25        self.__edge_map = collections.defaultdict(set)
26        self.__reverse_map = collections.defaultdict(set)
27        self.__nodes = set()
28
29    def add_node(self, node):
30        """
31        Add a node without any target to the graph.
32        """
33        self.__nodes.add(node)
34
35    def add_edge(self, source, target):
36        """
37        Add a directed edge from the C{source} to the C{target}.
38
39        The nodes are added to the graph if necessary.
40        """
41        self.__edge_map[source].add(target)
42        if source != target:
43            self.__reverse_map[target].add(source)
44        self.__nodes.add(source)
45        self.__nodes.add(target)
46
47    def roots(self):
48        """
49        Return the set of nodes calculated to be roots (i.e., those
50        that have no incoming edges).
51
52        This caches the roots calculated in a previous invocation.
53
54        @rtype: C{set}
55        """
56        if not self.__roots:
57            self.__roots = set()
58            for n in self.__nodes:
59                if n not in self.__reverse_map:
60                    self.__roots.add(n)
61        return self.__roots
62
63    def _tarjan(self):
64        # Execute Tarjan's algorithm on the graph.
65        #
66        # Tarjan's algorithm
67        # (http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
68        # computes the strongly-connected components
69        # (http://en.wikipedia.org/wiki/Strongly_connected_component)
70        # of the graph: i.e., the sets of nodes that form a minimal
71        # closed set under edge transition.  In essence, the loops.
72        # We use this to detect groups of components that have a
73        # dependency cycle, and to impose a total order on components
74        # based on dependencies.
75
76        self.__stack = []
77        self.__scc_order = []
78        self.__index = 0
79        self.__tarjan_index = {}
80        self.__tarjan_low_link = {}
81        for v in self.__nodes:
82            self.__tarjan_index[v] = None
83        roots = sorted(self.roots(), key=node_key)
84        if self.__nodes and not roots:
85            raise Exception('TARJAN: No roots found in graph with {} nodes'.format(len(self.__nodes)))
86
87        for r in roots:
88            self._tarjan_root(r)
89
90        # Assign ordinals for edtlib
91        ordinal = 0
92        for scc in self.__scc_order:
93            # Zephyr customization: devicetree Node graphs should have
94            # no loops, so all SCCs should be singletons.  That may
95            # change in the future, but for now we only give an
96            # ordinal to singletons.
97            if len(scc) == 1:
98                scc[0].dep_ordinal = ordinal
99                ordinal += 1
100
101    def _tarjan_root(self, v):
102        # Do the work of Tarjan's algorithm for a given root node.
103
104        if self.__tarjan_index.get(v) is not None:
105            # "Root" was already reached.
106            return
107        self.__tarjan_index[v] = self.__tarjan_low_link[v] = self.__index
108        self.__index += 1
109        self.__stack.append(v)
110        source = v
111        for target in sorted(self.__edge_map[source], key=node_key):
112            if self.__tarjan_index[target] is None:
113                self._tarjan_root(target)
114                self.__tarjan_low_link[v] = min(self.__tarjan_low_link[v], self.__tarjan_low_link[target])
115            elif target in self.__stack:
116                self.__tarjan_low_link[v] = min(self.__tarjan_low_link[v], self.__tarjan_low_link[target])
117
118        if self.__tarjan_low_link[v] == self.__tarjan_index[v]:
119            scc = []
120            while True:
121                scc.append(self.__stack.pop())
122                if v == scc[-1]:
123                    break
124            self.__scc_order.append(scc)
125
126    def scc_order(self):
127        """Return the strongly-connected components in order.
128
129        The data structure is a list, in dependency order, of strongly
130        connected components (which can be single nodes).  Appearance
131        of a node in a set earlier in the list indicates that it has
132        no dependencies on any node that appears in a subsequent set.
133        This order is preferred over a depth-first-search order for
134        code generation, since it detects loops.
135        """
136        if not self.__scc_order:
137            self._tarjan()
138        return self.__scc_order
139    __scc_order = None
140
141    def depends_on(self, node):
142        """Get the nodes that 'node' directly depends on."""
143        return sorted(self.__edge_map[node], key=node_key)
144
145    def required_by(self, node):
146        """Get the nodes that directly depend on 'node'."""
147        return sorted(self.__reverse_map[node], key=node_key)
148
149def node_key(node):
150    # This sort key ensures that sibling nodes with the same name will
151    # use unit addresses as tiebreakers. That in turn ensures ordinals
152    # for otherwise indistinguishable siblings are in increasing order
153    # by unit address, which is convenient for displaying output.
154
155    if node.parent:
156        parent_path = node.parent.path
157    else:
158        parent_path = '/'
159
160    if node.unit_addr is not None:
161        name = node.name.rsplit('@', 1)[0]
162        unit_addr = node.unit_addr
163    else:
164        name = node.name
165        unit_addr = -1
166
167    return (parent_path, name, unit_addr)
168