libcxx/utils/libcxx/graph.py

#===----------------------------------------------------------------------===##
#
# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
# See https://llvm.org/LICENSE.txt for license information.
# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#
#===----------------------------------------------------------------------===##

import platform
import os
from collections import defaultdict
import re
import libcxx.util


class DotEmitter(object):
  def __init__(self, name):
    self.name = name
    self.node_strings = {}
    self.edge_strings = []

  def addNode(self, node):
    res = str(node.id)
    if len(node.attributes):
      attr_strs = []
      for k,v in node.attributes.iteritems():
        attr_strs += ['%s="%s"' % (k, v)]
      res += ' [ %s ]' % (', '.join(attr_strs))
    res += ';'
    assert node.id not in self.node_strings
    self.node_strings[node.id] = res

  def addEdge(self, n1, n2):
    res = '%s -> %s;' % (n1.id, n2.id)
    self.edge_strings += [res]

  def node_key(self, n):
    id = n.id
    assert id.startswith('\w*\d+')

  def emit(self):
    node_definitions_list = []
    sorted_keys = self.node_strings.keys()
    sorted_keys.sort()
    for k in sorted_keys:
      node_definitions_list += [self.node_strings[k]]
    node_definitions = '\n  '.join(node_definitions_list)
    edge_list = '\n  '.join(self.edge_strings)
    return '''
digraph "{name}" {{
  {node_definitions}
  {edge_list}
}}    
'''.format(name=self.name, node_definitions=node_definitions, edge_list=edge_list).strip()


class DotReader(object):
  def __init__(self):
    self.graph = DirectedGraph(None)

  def abortParse(self, msg="bad input"):
    raise Exception(msg)

  def parse(self, data):
    lines = [l.strip() for l in data.splitlines() if l.strip()]
    maxIdx = len(lines)
    idx = 0
    if not self.parseIntroducer(lines[idx]):
      self.abortParse('failed to parse introducer')
    idx += 1
    while idx < maxIdx:
      if self.parseNodeDefinition(lines[idx]) or self.parseEdgeDefinition(lines[idx]):
        idx += 1
        continue
      else:
        break
    if idx == maxIdx or not self.parseCloser(lines[idx]):
      self.abortParse("no closing } found")
    return self.graph

  def parseEdgeDefinition(self, l):
    edge_re = re.compile('^\s*(\w+)\s+->\s+(\w+);\s*$')
    m = edge_re.match(l)
    if not m:
      return False
    n1 = m.group(1)
    n2 = m.group(2)
    self.graph.addEdge(n1, n2)
    return True

  def parseAttributes(self, raw_str):
    attribute_re = re.compile('^\s*(\w+)="([^"]+)"')
    parts = [l.strip() for l in raw_str.split(',') if l.strip()]
    attribute_dict = {}
    for a in parts:
      m = attribute_re.match(a)
      if not m:
        self.abortParse('Bad attribute "%s"' % a)
      attribute_dict[m.group(1)] = m.group(2)
    return attribute_dict

  def parseNodeDefinition(self, l):
    node_definition_re = re.compile('^\s*(\w+)\s+\[([^\]]+)\]\s*;\s*$')
    m = node_definition_re.match(l)
    if not m:
      return False
    id = m.group(1)
    attributes = self.parseAttributes(m.group(2))
    n = Node(id, edges=[], attributes=attributes)
    self.graph.addNode(n)
    return True

  def parseIntroducer(self, l):
    introducer_re = re.compile('^\s*digraph "([^"]+)"\s+{\s*$')
    m = introducer_re.match(l)
    if not m:
      return False
    self.graph.setName(m.group(1))
    return True

  def parseCloser(self, l):
    closer_re = re.compile('^\s*}\s*$')
    m = closer_re.match(l)
    if not m:
      return False
    return True

class Node(object):
  def __init__(self, id, edges=[], attributes={}):
    self.id = id
    self.edges = set(edges)
    self.attributes = dict(attributes)

  def addEdge(self, dest):
    self.edges.add(dest)

  def __eq__(self, another):
    if isinstance(another, str):
      return another == self.id
    return hasattr(another, 'id') and self.id == another.id

  def __hash__(self):
    return hash(self.id)

  def __str__(self):
    return self.attributes["label"]

  def __repr__(self):
    return self.__str__()
    res = self.id
    if len(self.attributes):
      attr = []
      for k,v in self.attributes.iteritems():
        attr += ['%s="%s"' % (k, v)]
      res += ' [%s ]' % (', '.join(attr))
    return res

class DirectedGraph(object):
  def __init__(self, name=None, nodes=None):
    self.name = name
    self.nodes = set() if nodes is None else set(nodes)

  def setName(self, n):
    self.name = n

  def _getNode(self, n_or_id):
    if isinstance(n_or_id, Node):
      return n_or_id
    return self.getNode(n_or_id)

  def getNode(self, str_id):
    assert isinstance(str_id, str) or isinstance(str_id, Node)
    for s in self.nodes:
      if s == str_id:
        return s
    return None

  def getNodeByLabel(self, l):
    found = None
    for s in self.nodes:
      if s.attributes['label'] == l:
        assert found is None
        found = s
    return found

  def addEdge(self, n1, n2):
    n1 = self._getNode(n1)
    n2 = self._getNode(n2)
    assert n1 in self.nodes
    assert n2 in self.nodes
    n1.addEdge(n2)

  def addNode(self, n):
    self.nodes.add(n)

  def removeNode(self, n):
    n = self._getNode(n)
    for other_n in self.nodes:
      if other_n == n:
        continue
      new_edges = set()
      for e in other_n.edges:
        if e != n:
          new_edges.add(e)
      other_n.edges = new_edges
    self.nodes.remove(n)

  def toDot(self):
    dot = DotEmitter(self.name)
    for n in self.nodes:
      dot.addNode(n)
      for ndest in n.edges:
        dot.addEdge(n, ndest)
    return dot.emit()

  @staticmethod
  def fromDot(str):
    reader = DotReader()
    graph = reader.parse(str)
    return graph

  @staticmethod
  def fromDotFile(fname):
    with open(fname, 'r') as f:
      return DirectedGraph.fromDot(f.read())

  def toDotFile(self, fname):
    with open(fname, 'w') as f:
      f.write(self.toDot())

  def __repr__(self):
    return self.toDot()

class BFS(object):
  def __init__(self, start):
    self.visited = set()
    self.to_visit = []
    self.start = start

  def __nonzero__(self):
    return len(self.to_visit) != 0

  def empty(self):
    return len(self.to_visit) == 0

  def push_back(self, node):
    assert node not in self.visited
    self.visited.add(node)
    self.to_visit += [node]

  def maybe_push_back(self, node):
    if node in self.visited:
      return
    self.push_back(node)

  def pop_front(self):
    assert len(self.to_visit)
    elem = self.to_visit[0]
    del self.to_visit[0]
    return elem

  def seen(self, n):
    return n in self.visited



class CycleFinder(object):
  def __init__(self, graph):
    self.graph = graph

  def findCycleForNode(self, n):
    assert n in self.graph.nodes
    all_paths = {}
    all_cycles = []
    bfs = BFS(n)
    bfs.push_back(n)
    all_paths[n] = [n]
    while bfs:
      n = bfs.pop_front()
      assert n in all_paths
      for e in n.edges:
        en = self.graph.getNode(e)
        if not bfs.seen(en):
          new_path = list(all_paths[n])
          new_path.extend([en])
          all_paths[en] = new_path
          bfs.push_back(en)
        if en == bfs.start:
          all_cycles += [all_paths[n]]
    return all_cycles

  def findCyclesInGraph(self):
    all_cycles = []
    for n in self.graph.nodes:
      cycle = self.findCycleForNode(n)
      if cycle:
        all_cycles += [(n, cycle)]
    return all_cycles