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