1#===----------------------------------------------------------------------===##
2#
3# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4# See https://llvm.org/LICENSE.txt for license information.
5# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6#
7#===----------------------------------------------------------------------===##
8
9import platform
10import os
11from collections import defaultdict
12import re
13import libcxx.util
14
15
16class DotEmitter(object):
17  def __init__(self, name):
18    self.name = name
19    self.node_strings = {}
20    self.edge_strings = []
21
22  def addNode(self, node):
23    res = str(node.id)
24    if len(node.attributes):
25      attr_strs = []
26      for k,v in node.attributes.iteritems():
27        attr_strs += ['%s="%s"' % (k, v)]
28      res += ' [ %s ]' % (', '.join(attr_strs))
29    res += ';'
30    assert node.id not in self.node_strings
31    self.node_strings[node.id] = res
32
33  def addEdge(self, n1, n2):
34    res = '%s -> %s;' % (n1.id, n2.id)
35    self.edge_strings += [res]
36
37  def node_key(self, n):
38    id = n.id
39    assert id.startswith('\w*\d+')
40
41  def emit(self):
42    node_definitions_list = []
43    sorted_keys = self.node_strings.keys()
44    sorted_keys.sort()
45    for k in sorted_keys:
46      node_definitions_list += [self.node_strings[k]]
47    node_definitions = '\n  '.join(node_definitions_list)
48    edge_list = '\n  '.join(self.edge_strings)
49    return '''
50digraph "{name}" {{
51  {node_definitions}
52  {edge_list}
53}}
54'''.format(name=self.name, node_definitions=node_definitions, edge_list=edge_list).strip()
55
56
57class DotReader(object):
58  def __init__(self):
59    self.graph = DirectedGraph(None)
60
61  def abortParse(self, msg="bad input"):
62    raise Exception(msg)
63
64  def parse(self, data):
65    lines = [l.strip() for l in data.splitlines() if l.strip()]
66    maxIdx = len(lines)
67    idx = 0
68    if not self.parseIntroducer(lines[idx]):
69      self.abortParse('failed to parse introducer')
70    idx += 1
71    while idx < maxIdx:
72      if self.parseNodeDefinition(lines[idx]) or self.parseEdgeDefinition(lines[idx]):
73        idx += 1
74        continue
75      else:
76        break
77    if idx == maxIdx or not self.parseCloser(lines[idx]):
78      self.abortParse("no closing } found")
79    return self.graph
80
81  def parseEdgeDefinition(self, l):
82    edge_re = re.compile('^\s*(\w+)\s+->\s+(\w+);\s*$')
83    m = edge_re.match(l)
84    if not m:
85      return False
86    n1 = m.group(1)
87    n2 = m.group(2)
88    self.graph.addEdge(n1, n2)
89    return True
90
91  def parseAttributes(self, raw_str):
92    attribute_re = re.compile('^\s*(\w+)="([^"]+)"')
93    parts = [l.strip() for l in raw_str.split(',') if l.strip()]
94    attribute_dict = {}
95    for a in parts:
96      m = attribute_re.match(a)
97      if not m:
98        self.abortParse('Bad attribute "%s"' % a)
99      attribute_dict[m.group(1)] = m.group(2)
100    return attribute_dict
101
102  def parseNodeDefinition(self, l):
103    node_definition_re = re.compile('^\s*(\w+)\s+\[([^\]]+)\]\s*;\s*$')
104    m = node_definition_re.match(l)
105    if not m:
106      return False
107    id = m.group(1)
108    attributes = self.parseAttributes(m.group(2))
109    n = Node(id, edges=[], attributes=attributes)
110    self.graph.addNode(n)
111    return True
112
113  def parseIntroducer(self, l):
114    introducer_re = re.compile('^\s*digraph "([^"]+)"\s+{\s*$')
115    m = introducer_re.match(l)
116    if not m:
117      return False
118    self.graph.setName(m.group(1))
119    return True
120
121  def parseCloser(self, l):
122    closer_re = re.compile('^\s*}\s*$')
123    m = closer_re.match(l)
124    if not m:
125      return False
126    return True
127
128class Node(object):
129  def __init__(self, id, edges=[], attributes={}):
130    self.id = id
131    self.edges = set(edges)
132    self.attributes = dict(attributes)
133
134  def addEdge(self, dest):
135    self.edges.add(dest)
136
137  def __eq__(self, another):
138    if isinstance(another, str):
139      return another == self.id
140    return hasattr(another, 'id') and self.id == another.id
141
142  def __hash__(self):
143    return hash(self.id)
144
145  def __str__(self):
146    return self.attributes["label"]
147
148  def __repr__(self):
149    return self.__str__()
150    res = self.id
151    if len(self.attributes):
152      attr = []
153      for k,v in self.attributes.iteritems():
154        attr += ['%s="%s"' % (k, v)]
155      res += ' [%s ]' % (', '.join(attr))
156    return res
157
158class DirectedGraph(object):
159  def __init__(self, name=None, nodes=None):
160    self.name = name
161    self.nodes = set() if nodes is None else set(nodes)
162
163  def setName(self, n):
164    self.name = n
165
166  def _getNode(self, n_or_id):
167    if isinstance(n_or_id, Node):
168      return n_or_id
169    return self.getNode(n_or_id)
170
171  def getNode(self, str_id):
172    assert isinstance(str_id, str) or isinstance(str_id, Node)
173    for s in self.nodes:
174      if s == str_id:
175        return s
176    return None
177
178  def getNodeByLabel(self, l):
179    found = None
180    for s in self.nodes:
181      if s.attributes['label'] == l:
182        assert found is None
183        found = s
184    return found
185
186  def addEdge(self, n1, n2):
187    n1 = self._getNode(n1)
188    n2 = self._getNode(n2)
189    assert n1 in self.nodes
190    assert n2 in self.nodes
191    n1.addEdge(n2)
192
193  def addNode(self, n):
194    self.nodes.add(n)
195
196  def removeNode(self, n):
197    n = self._getNode(n)
198    for other_n in self.nodes:
199      if other_n == n:
200        continue
201      new_edges = set()
202      for e in other_n.edges:
203        if e != n:
204          new_edges.add(e)
205      other_n.edges = new_edges
206    self.nodes.remove(n)
207
208  def toDot(self):
209    dot = DotEmitter(self.name)
210    for n in self.nodes:
211      dot.addNode(n)
212      for ndest in n.edges:
213        dot.addEdge(n, ndest)
214    return dot.emit()
215
216  @staticmethod
217  def fromDot(str):
218    reader = DotReader()
219    graph = reader.parse(str)
220    return graph
221
222  @staticmethod
223  def fromDotFile(fname):
224    with open(fname, 'r') as f:
225      return DirectedGraph.fromDot(f.read())
226
227  def toDotFile(self, fname):
228    with open(fname, 'w') as f:
229      f.write(self.toDot())
230
231  def __repr__(self):
232    return self.toDot()
233
234class BFS(object):
235  def __init__(self, start):
236    self.visited = set()
237    self.to_visit = []
238    self.start = start
239
240  def __nonzero__(self):
241    return len(self.to_visit) != 0
242
243  def empty(self):
244    return len(self.to_visit) == 0
245
246  def push_back(self, node):
247    assert node not in self.visited
248    self.visited.add(node)
249    self.to_visit += [node]
250
251  def maybe_push_back(self, node):
252    if node in self.visited:
253      return
254    self.push_back(node)
255
256  def pop_front(self):
257    assert len(self.to_visit)
258    elem = self.to_visit[0]
259    del self.to_visit[0]
260    return elem
261
262  def seen(self, n):
263    return n in self.visited
264
265
266
267class CycleFinder(object):
268  def __init__(self, graph):
269    self.graph = graph
270
271  def findCycleForNode(self, n):
272    assert n in self.graph.nodes
273    all_paths = {}
274    all_cycles = []
275    bfs = BFS(n)
276    bfs.push_back(n)
277    all_paths[n] = [n]
278    while bfs:
279      n = bfs.pop_front()
280      assert n in all_paths
281      for e in n.edges:
282        en = self.graph.getNode(e)
283        if not bfs.seen(en):
284          new_path = list(all_paths[n])
285          new_path.extend([en])
286          all_paths[en] = new_path
287          bfs.push_back(en)
288        if en == bfs.start:
289          all_cycles += [all_paths[n]]
290    return all_cycles
291
292  def findCyclesInGraph(self):
293    all_cycles = []
294    for n in self.graph.nodes:
295      cycle = self.findCycleForNode(n)
296      if cycle:
297        all_cycles += [(n, cycle)]
298    return all_cycles
299