Rev 1: Simple plugin for generating per-file graphs in http://bzr.arbash-meinel.com/plugins/per_file_graph
John Arbash Meinel
john at arbash-meinel.com
Wed Jul 9 15:49:08 BST 2008
At http://bzr.arbash-meinel.com/plugins/per_file_graph
------------------------------------------------------------
revno: 1
revision-id: john at arbash-meinel.com-20080709144908-1bgts2ul3w39hi1t
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: per_file_graph
timestamp: Wed 2008-07-09 09:49:08 -0500
message:
Simple plugin for generating per-file graphs
added:
__init__.py __init__.py-20080708224126-2f8i6vu6ubjt468r-1
dict_to_dot.py dict_to_dot.py-20080708224126-2f8i6vu6ubjt468r-2
per_file_graph.py per_file_graph.py-20080708224126-2f8i6vu6ubjt468r-3
test_per_file_graph.py test_per_file_graph.-20080709143328-zoammbywlmaa8zvt-1
-------------- next part --------------
=== added file '__init__.py'
--- a/__init__.py 1970-01-01 00:00:00 +0000
+++ b/__init__.py 2008-07-09 14:49:08 +0000
@@ -0,0 +1,60 @@
+# Copyright (C) 2008 Canonical Development Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+"""Generate output for per-file graphs."""
+
+from bzrlib import (
+ commands,
+ errors,
+ option,
+ )
+
+
+class cmd_per_file_graph(commands.Command):
+ """Output the per-file-graph for a given file."""
+
+ takes_options = [option.Option('collapse',
+ help='Collapse linear regions of the graph'),
+ ]
+ takes_args = ['filename', 'outfile?']
+ encoding = 'exact'
+
+ def run(self, filename, outfile=None, collapse=False):
+ import dict_to_dot, per_file_graph
+ d, tip = per_file_graph.get_per_file_graph(filename)
+ if collapse:
+ d = per_file_graph.collapse_graph(d)
+ dot_lines = dict_to_dot.dict_to_dot(d, tip)
+ if outfile is None:
+ self.outf.writelines(dot_lines)
+ else:
+ out = open(outfile, 'wb')
+ try:
+ out.writelines(dot_lines)
+ finally:
+ out.close()
+
+commands.register_command(cmd_per_file_graph)
+
+
+def load_tests(basic_tests, module, loader):
+ suite = loader.suiteClass()
+
+ test_files = [__name__ + '.' + x for x in [
+ 'test_per_file_graph',
+ ]]
+ suite.addTests(loader.loadTestsFromModuleNames(test_files))
+ return suite
=== added file 'dict_to_dot.py'
--- a/dict_to_dot.py 1970-01-01 00:00:00 +0000
+++ b/dict_to_dot.py 2008-07-09 14:49:08 +0000
@@ -0,0 +1,58 @@
+#!/bin/env python
+"""Convert a python dictionary representation into a dot graph."""
+
+import sys
+
+
+def dict_to_dot(d, tip):
+ """For the given dictionary, generate lines for 'dot' output.
+
+ :param d: A dictionary mapping {child: (parents,)}
+ :param tip: The tip revision (used to determine revnos)
+ :return: lines for a dot representation
+ """
+ from bzrlib import tsort
+ lines = ['digraph G {\n']
+
+ # Map from crazy revision ids => dotted revnos
+ revnos = {}
+ sorted_result = tsort.merge_sort(d, tip, generate_revno=True)
+ for seq_num, name, depth, dotted_revno, eom in sorted_result:
+ revno = '.'.join(map(str, dotted_revno))
+ revnos[name] = revno
+
+ for child, parent_ids in d.iteritems():
+ revno = revnos.get(child, child)
+ first = True
+ for parent_id in parent_ids:
+ parent_revno = revnos.get(parent_id, parent_id)
+ if first:
+ first = False
+ weight = 'weight=10'
+ else:
+ weight = ''
+
+ lines.append('"%s" -> "%s"[%s];\n' % (parent_revno, revno, weight))
+
+ lines.append('}\n')
+ return lines
+
+
+def main(args):
+ import optparse
+ p = optparse.OptionParser('echo graph | %prog tip')
+
+ opts, args = p.parse_args(args)
+ if len(args) != 1:
+ print 'You must supply a tip revision'
+ return -1
+ tip = eval(args[0])
+
+ # This is *very* unsafe, but what the heck...
+ d = eval(sys.stdin.read())
+ lines = dict_to_dot(d, tip)
+ sys.stdout.writelines(lines)
+
+
+if __name__ == '__main__':
+ sys.exit(main(sys.argv[1:]))
=== added file 'per_file_graph.py'
--- a/per_file_graph.py 1970-01-01 00:00:00 +0000
+++ b/per_file_graph.py 2008-07-09 14:49:08 +0000
@@ -0,0 +1,134 @@
+#!/bin/env python
+"""Convert a python dictionary representation into a dot graph."""
+
+import sys
+
+
+def get_per_file_graph(filename):
+ from bzrlib import graph, workingtree
+
+ overlay_dict = {}
+ overlay_pp = graph.DictParentsProvider(overlay_dict)
+ wt, relpath = workingtree.WorkingTree.open_containing(filename)
+ wt.lock_read()
+ try:
+ basis_tree = wt.basis_tree()
+ basis_tree.lock_read()
+ try:
+ file_id = wt.path2id(relpath)
+ tip = (file_id, 'this:')
+ last_mod_rev = basis_tree.inventory[file_id].revision
+
+ file_parents = [last_mod_rev]
+ parent_ids = wt.get_parent_ids()
+ for parent_id in parent_ids[1:]:
+ rev_tree = wt.branch.repository.revision_tree(parent_id)
+ last_mod_rev = rev_tree.inventory[file_id].revision
+ if last_mod_rev not in file_parents:
+ file_parents.append(last_mod_rev)
+
+ overlay_dict[tip] = tuple((file_id, p_id) for p_id in file_parents)
+
+ pp = graph._StackedParentsProvider([wt.branch.repository.texts,
+ overlay_pp])
+ g = graph.Graph(pp)
+ return dict(g.iter_ancestry([tip])), tip
+ finally:
+ basis_tree.unlock()
+ finally:
+ wt.unlock()
+
+
+def collapse_graph(d):
+ """Collapse regions of the graph that are 'linear'.
+
+ For example::
+
+ A:[B], B:[C]
+
+ can be collapsed by removing B and getting::
+
+ A:[C]
+
+ :param: A dictionary mapping children to their parents
+ :return: Another dictionary with 'linear' chains collapsed
+ """
+ # Note: this isn't a strictly minimal collapse. For example:
+ # A
+ # / \
+ # B C
+ # \ /
+ # D
+ # |
+ # E
+ # Will not have 'D' removed, even though 'E' could fit. Also:
+ # A
+ # | A
+ # B => |
+ # | C
+ # C
+ # A and C are both kept because they are edges of the graph. We *could* get
+ # rid of A if we wanted.
+ # A
+ # / \
+ # B C
+ # | |
+ # D E
+ # \ /
+ # F
+ # Will not have any nodes removed, even though you do have an
+ # 'uninteresting' linear D->B and E->C
+ children = {}
+ for child, parents in d.iteritems():
+ children.setdefault(child, [])
+ for p in parents:
+ children.setdefault(p, []).append(child)
+
+ orig_children = dict(children)
+ removed = set()
+ result = dict(d)
+ for node in d:
+ parents = result[node]
+ if len(parents) == 1:
+ parent_children = children[parents[0]]
+ if len(parent_children) != 1:
+ # This is not the only child
+ continue
+ node_children = children[node]
+ if len(node_children) != 1:
+ continue
+ child_parents = result.get(node_children[0], None)
+ if child_parents is None:
+ import pdb; pdb.set_trace()
+ if len(child_parents) != 1:
+ # This is not its only parent
+ continue
+ assert child_parents[0] == node
+ # The child of this node only points at it, and the parent only has
+ # this as a child. remove this node, and join the others together
+ result[node_children[0]] = parents
+ children[parents[0]] = node_children
+ del result[node]
+ del children[node]
+ removed.add(node)
+
+ return result
+
+
+def main(args):
+ import optparse
+ p = optparse.OptionParser('%prog filename')
+
+ opts, args = p.parse_args(args)
+ if len(args) != 1:
+ print 'you must supply a filename'
+ return -1
+
+ d, tip = get_per_file_graph(args[0])
+ from dict_to_dot import dict_to_dot
+ sys.stdout.writelines(dict_to_dot(d, tip))
+
+
+if __name__ == '__main__':
+ sys.exit(main(sys.argv[1:]))
+
=== added file 'test_per_file_graph.py'
--- a/test_per_file_graph.py 1970-01-01 00:00:00 +0000
+++ b/test_per_file_graph.py 2008-07-09 14:49:08 +0000
@@ -0,0 +1,58 @@
+# Copyright (C) 2008 Canonical Development Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+"""Tests for generating a per-file graph"""
+
+from bzrlib import tests
+
+from bzrlib.plugins.per_file_graph import per_file_graph
+
+
+class TestCollapseGraph(tests.TestCase):
+
+ def assertCollapsed(self, collapsed, original):
+ self.assertEqual(collapsed, per_file_graph.collapse_graph(original))
+
+ def test_collapse_nothing(self):
+ d = {1:[2, 3], 2:[], 3:[]}
+ self.assertCollapsed(d, d)
+ d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
+ self.assertCollapsed(d, d)
+
+ def test_collapse_chain(self):
+ # Any time we have a linear chain, we should be able to collapse
+ d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
+ self.assertCollapsed({1:[5], 5:[]}, d)
+ d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
+ self.assertCollapsed({5:[1], 1:[]}, d)
+ d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
+ self.assertCollapsed({5:[2], 2:[]}, d)
+
+ def test_collapse_with_multiple_children(self):
+ # 7
+ # |
+ # 6
+ # / \
+ # 4 5
+ # | |
+ # 3 2
+ # \ /
+ # 1
+ #
+ # 4 and 5 cannot be removed because 6 has 2 children
+ # 3 and 2 cannot be removed because 1 has 2 parents
+ d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
+ self.assertCollapsed(d, d)
More information about the bazaar-commits
mailing list