1# copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
2# contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
3#
4# This file is part of logilab-common.
5#
6# logilab-common is free software: you can redistribute it and/or modify it under
7# the terms of the GNU Lesser General Public License as published by the Free
8# Software Foundation, either version 2.1 of the License, or (at your option) any
9# later version.
10#
11# logilab-common is distributed in the hope that it will be useful, but WITHOUT
12# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13# FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
14# details.
15#
16# You should have received a copy of the GNU Lesser General Public License along
17# with logilab-common.  If not, see <http://www.gnu.org/licenses/>.
18"""Graph manipulation utilities.
19
20(dot generation adapted from pypy/translator/tool/make_dot.py)
21"""
22
23__docformat__ = "restructuredtext en"
24
25__metaclass__ = type
26
27import os.path as osp
28import os
29import sys
30import tempfile
31import codecs
32import errno
33
34def escape(value):
35    """Make <value> usable in a dot file."""
36    lines = [line.replace('"', '\\"') for line in value.split('\n')]
37    data = '\\l'.join(lines)
38    return '\\n' + data
39
40def target_info_from_filename(filename):
41    """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png')."""
42    basename = osp.basename(filename)
43    storedir = osp.dirname(osp.abspath(filename))
44    target = filename.split('.')[-1]
45    return storedir, basename, target
46
47
48class DotBackend:
49    """Dot File backend."""
50    def __init__(self, graphname, rankdir=None, size=None, ratio=None,
51            charset='utf-8', renderer='dot', additionnal_param={}):
52        self.graphname = graphname
53        self.renderer = renderer
54        self.lines = []
55        self._source = None
56        self.emit("digraph %s {" % normalize_node_id(graphname))
57        if rankdir:
58            self.emit('rankdir=%s' % rankdir)
59        if ratio:
60            self.emit('ratio=%s' % ratio)
61        if size:
62            self.emit('size="%s"' % size)
63        if charset:
64            assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \
65                   'unsupported charset %s' % charset
66            self.emit('charset="%s"' % charset)
67        for param in sorted(additionnal_param.items()):
68            self.emit('='.join(param))
69
70    def get_source(self):
71        """returns self._source"""
72        if self._source is None:
73            self.emit("}\n")
74            self._source = '\n'.join(self.lines)
75            del self.lines
76        return self._source
77
78    source = property(get_source)
79
80    def generate(self, outputfile=None, dotfile=None, mapfile=None):
81        """Generates a graph file.
82
83        :param outputfile: filename and path [defaults to graphname.png]
84        :param dotfile: filename and path [defaults to graphname.dot]
85
86        :rtype: str
87        :return: a path to the generated file
88        """
89        import subprocess # introduced in py 2.4
90        name = self.graphname
91        if not dotfile:
92            # if 'outputfile' is a dot file use it as 'dotfile'
93            if outputfile and outputfile.endswith(".dot"):
94                dotfile = outputfile
95            else:
96                dotfile = '%s.dot' % name
97        if outputfile is not None:
98            storedir, basename, target = target_info_from_filename(outputfile)
99            if target != "dot":
100                pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
101                os.close(pdot)
102            else:
103                dot_sourcepath = osp.join(storedir, dotfile)
104        else:
105            target = 'png'
106            pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
107            ppng, outputfile = tempfile.mkstemp(".png", name)
108            os.close(pdot)
109            os.close(ppng)
110        pdot = codecs.open(dot_sourcepath, 'w', encoding='utf8')
111        pdot.write(self.source)
112        pdot.close()
113        if target != 'dot':
114            if sys.platform == 'win32':
115                use_shell = True
116            else:
117                use_shell = False
118            try:
119                if mapfile:
120                    subprocess.call([self.renderer,  '-Tcmapx', '-o', mapfile, '-T', target, dot_sourcepath, '-o', outputfile],
121                                    shell=use_shell)
122                else:
123                    subprocess.call([self.renderer, '-T',  target,
124                                     dot_sourcepath, '-o',  outputfile],
125                                    shell=use_shell)
126            except OSError as e:
127                if e.errno == errno.ENOENT:
128                    e.strerror = 'File not found: {0}'.format(self.renderer)
129                    raise
130            os.unlink(dot_sourcepath)
131        return outputfile
132
133    def emit(self, line):
134        """Adds <line> to final output."""
135        self.lines.append(line)
136
137    def emit_edge(self, name1, name2, **props):
138        """emit an edge from <name1> to <name2>.
139        edge properties: see http://www.graphviz.org/doc/info/attrs.html
140        """
141        attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
142        n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
143        self.emit('%s -> %s [%s];' % (n_from, n_to, ', '.join(sorted(attrs))) )
144
145    def emit_node(self, name, **props):
146        """emit a node with given properties.
147        node properties: see http://www.graphviz.org/doc/info/attrs.html
148        """
149        attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
150        self.emit('%s [%s];' % (normalize_node_id(name), ', '.join(sorted(attrs))))
151
152def normalize_node_id(nid):
153    """Returns a suitable DOT node id for `nid`."""
154    return '"%s"' % nid
155
156class GraphGenerator:
157    def __init__(self, backend):
158        # the backend is responsible to output the graph in a particular format
159        self.backend = backend
160
161    # XXX doesn't like space in outpufile / mapfile
162    def generate(self, visitor, propshdlr, outputfile=None, mapfile=None):
163        # the visitor
164        # the property handler is used to get node and edge properties
165        # according to the graph and to the backend
166        self.propshdlr = propshdlr
167        for nodeid, node in visitor.nodes():
168            props = propshdlr.node_properties(node)
169            self.backend.emit_node(nodeid, **props)
170        for subjnode, objnode, edge in visitor.edges():
171            props = propshdlr.edge_properties(edge, subjnode, objnode)
172            self.backend.emit_edge(subjnode, objnode, **props)
173        return self.backend.generate(outputfile=outputfile, mapfile=mapfile)
174
175
176class UnorderableGraph(Exception):
177    pass
178
179def ordered_nodes(graph):
180    """takes a dependency graph dict as arguments and return an ordered tuple of
181    nodes starting with nodes without dependencies and up to the outermost node.
182
183    If there is some cycle in the graph, :exc:`UnorderableGraph` will be raised.
184
185    Also the given graph dict will be emptied.
186    """
187    # check graph consistency
188    cycles = get_cycles(graph)
189    if cycles:
190        cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles])
191        raise UnorderableGraph('cycles in graph: %s' % cycles)
192    vertices = set(graph)
193    to_vertices = set()
194    for edges in graph.values():
195        to_vertices |= set(edges)
196    missing_vertices = to_vertices - vertices
197    if missing_vertices:
198        raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices))
199    # order vertices
200    order = []
201    order_set = set()
202    old_len = None
203    while graph:
204        if old_len == len(graph):
205            raise UnorderableGraph('unknown problem with %s' % graph)
206        old_len = len(graph)
207        deps_ok = []
208        for node, node_deps in graph.items():
209            for dep in node_deps:
210                if dep not in order_set:
211                    break
212            else:
213                deps_ok.append(node)
214        order.append(deps_ok)
215        order_set |= set(deps_ok)
216        for node in deps_ok:
217            del graph[node]
218    result = []
219    for grp in reversed(order):
220        result.extend(sorted(grp))
221    return tuple(result)
222
223
224def get_cycles(graph_dict, vertices=None):
225    '''given a dictionary representing an ordered graph (i.e. key are vertices
226    and values is a list of destination vertices representing edges), return a
227    list of detected cycles
228    '''
229    if not graph_dict:
230        return ()
231    result = []
232    if vertices is None:
233        vertices = graph_dict.keys()
234    for vertice in vertices:
235        _get_cycles(graph_dict, [], set(), result, vertice)
236    return result
237
238def _get_cycles(graph_dict, path, visited, result, vertice):
239    """recursive function doing the real work for get_cycles"""
240    if vertice in path:
241        cycle = [vertice]
242        for node in path[::-1]:
243            if node == vertice:
244                break
245            cycle.insert(0, node)
246        # make a canonical representation
247        start_from = min(cycle)
248        index = cycle.index(start_from)
249        cycle = cycle[index:] + cycle[0:index]
250        # append it to result if not already in
251        if not cycle in result:
252            result.append(cycle)
253        return
254    path.append(vertice)
255    try:
256        for node in graph_dict[vertice]:
257            # don't check already visited nodes again
258            if node not in visited:
259                _get_cycles(graph_dict, path, visited, result, node)
260                visited.add(node)
261    except KeyError:
262        pass
263    path.pop()
264
265def has_path(graph_dict, fromnode, tonode, path=None):
266    """generic function taking a simple graph definition as a dictionary, with
267    node has key associated to a list of nodes directly reachable from it.
268
269    Return None if no path exists to go from `fromnode` to `tonode`, else the
270    first path found (as a list including the destination node at last)
271    """
272    if path is None:
273        path = []
274    elif fromnode in path:
275        return None
276    path.append(fromnode)
277    for destnode in graph_dict[fromnode]:
278        if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
279            return path[1:] + [tonode]
280    path.pop()
281    return None
282
283