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