Rev 2: some small updates. in http://bzr.arbash-meinel.com/plugins/per_file_graph
John Arbash Meinel
john at arbash-meinel.com
Wed Jul 9 18:16:12 BST 2008
At http://bzr.arbash-meinel.com/plugins/per_file_graph
------------------------------------------------------------
revno: 2
revision-id: john at arbash-meinel.com-20080709171611-887q56aflfcsady3
parent: 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 12:16:11 -0500
message:
some small updates.
Unfortunately, the graph I'm interested in is far to complex to
really get a handle on, even with a lot of filtering... :(
modified:
__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 --------------
=== modified file '__init__.py'
--- a/__init__.py 2008-07-09 14:49:08 +0000
+++ b/__init__.py 2008-07-09 17:16:11 +0000
@@ -20,6 +20,7 @@
commands,
errors,
option,
+ trace,
)
@@ -28,16 +29,61 @@
takes_options = [option.Option('collapse',
help='Collapse linear regions of the graph'),
+ option.Option('prune',
+ help='Remove all ancestors of the unique lca'),
+ option.Option('mark', help='Color lca nodes'),
+ option.Option('remove-after-lca',
+ help='Remove nodes that are after lca, but before'
+ ' parents'),
]
takes_args = ['filename', 'outfile?']
encoding = 'exact'
- def run(self, filename, outfile=None, collapse=False):
+ _lca_colors = ['red', 'green', 'cyan', 'gold', 'coral', 'darkorchid']
+ _unique_lca_color = 'chocolate'
+
+ def run(self, filename, outfile=None, collapse=False, prune=False,
+ mark=False, remove_after_lca=False):
import dict_to_dot, per_file_graph
d, tip = per_file_graph.get_per_file_graph(filename)
+
+ colors = {}
+ if prune or mark or remove_after_lca:
+ from bzrlib import graph
+ g = graph.Graph(graph.DictParentsProvider(d))
+ parents = d[tip]
+ if len(parents) < 2:
+ raise errors.BzrCommandError('pruning and marking only'
+ ' make sense when there are multiple ancestors')
+ lca_color_idx = 0
+ lca = parents
+ first_lca = None
+ while len(lca) > 1:
+ for node in lca:
+ colors[node] = self._lca_colors[lca_color_idx]
+ lca_color_idx = (lca_color_idx + 1) % len(self._lca_colors)
+ lca = g.find_lca(*lca)
+ if first_lca is None:
+ first_lca = tuple(lca)
+
+ if len(lca) == 0:
+ trace.note('no global unique lca')
+ else:
+ # Now we have just one node
+ unique_lca = lca.pop()
+ colors[unique_lca] = self._unique_lca_color
+ if prune:
+ d = per_file_graph.remove_ancestors_of(d, unique_lca)
+
+ if remove_after_lca:
+ d = per_file_graph.remove_between(d, parents, first_lca)
+ d[tip] = parents
+ if not mark:
+ colors = {}
if collapse:
d = per_file_graph.collapse_graph(d)
- dot_lines = dict_to_dot.dict_to_dot(d, tip)
+
+ dot_lines = dict_to_dot.dict_to_dot(d, tip, colors)
if outfile is None:
self.outf.writelines(dot_lines)
else:
=== modified file 'dict_to_dot.py'
--- a/dict_to_dot.py 2008-07-09 14:49:08 +0000
+++ b/dict_to_dot.py 2008-07-09 17:16:11 +0000
@@ -4,11 +4,12 @@
import sys
-def dict_to_dot(d, tip):
+def dict_to_dot(d, tip, colors={}):
"""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)
+ :param colors: Color specific nodes
:return: lines for a dot representation
"""
from bzrlib import tsort
@@ -17,23 +18,43 @@
# Map from crazy revision ids => dotted revnos
revnos = {}
sorted_result = tsort.merge_sort(d, tip, generate_revno=True)
+ mainline = set()
for seq_num, name, depth, dotted_revno, eom in sorted_result:
revno = '.'.join(map(str, dotted_revno))
revnos[name] = revno
+ if depth == 0:
+ mainline.add(name)
- for child, parent_ids in d.iteritems():
+ def process(child):
+ parents = d[child]
+ processed.add(child)
revno = revnos.get(child, child)
first = True
- for parent_id in parent_ids:
- parent_revno = revnos.get(parent_id, parent_id)
+ for parent in parents:
+ parent_revno = revnos.get(parent, parent)
if first:
first = False
- weight = 'weight=10'
+ if child in mainline and parent in mainline:
+ weight = 'weight=100'
+ else:
+ weight = 'weight=10'
else:
weight = ''
lines.append('"%s" -> "%s"[%s];\n' % (parent_revno, revno, weight))
+ processed = set()
+ for seq_num, child, depth, dotted_revno, eom in reversed(sorted_result):
+ process(child)
+
+ remaining = set(d) - processed
+ for node in remaining:
+ process(node)
+
+ for node, color in colors.iteritems():
+ revno = revnos.get(node, node)
+ lines.append('"%s"[style=filled,fillcolor="%s"];\n' % (revno, color))
+
lines.append('}\n')
return lines
=== modified file 'per_file_graph.py'
--- a/per_file_graph.py 2008-07-09 14:49:08 +0000
+++ b/per_file_graph.py 2008-07-09 17:16:11 +0000
@@ -2,11 +2,14 @@
"""Convert a python dictionary representation into a dot graph."""
import sys
+from bzrlib import (
+ graph,
+ revision,
+ workingtree,
+ )
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)
@@ -16,7 +19,7 @@
basis_tree.lock_read()
try:
file_id = wt.path2id(relpath)
- tip = (file_id, 'this:')
+ tip = (file_id, revision.CURRENT_REVISION)
last_mod_rev = basis_tree.inventory[file_id].revision
file_parents = [last_mod_rev]
@@ -115,6 +118,61 @@
return result
+def _find_ancestors(d, children):
+ """Find all ancestors of the given children."""
+ ancestors = set()
+ # Note that we don't remove ancestor_node itself, only the ancestors of
+ # ancestor_node
+ pending = list(children)
+ while pending:
+ next = pending.pop()
+ parents = d[next]
+ # Make sure we can stop if the nodes have already been marked
+ extra_parents = [p for p in parents if p not in ancestors]
+ pending.extend(extra_parents)
+ ancestors.update(extra_parents)
+ return ancestors
+
+def remove_ancestors_of(d, ancestor_node):
+ """Remove all ancestors of ancestor_node from the graph.
+
+ :param d: A graph of {node:[parents]}
+ :param ancestor_node: Remove ancestors of this node, but not this node
+ itself.
+ :return: A filtered graph of the same form as 'd', all references to
+ removed ancestors will be removed from the graph.
+ """
+ all_nodes = set(d)
+ ancestors = set()
+ # Note that we don't remove ancestor_node itself, only the ancestors of
+ # ancestor_node
+ ancestors = _find_ancestors(d, [ancestor_node])
+ remaining_nodes = all_nodes - ancestors
+ result = {}
+ for node, parents in d.iteritems():
+ if node in ancestors:
+ continue
+ simple_parents = tuple([p for p in parents if p not in ancestors])
+ result[node] = simple_parents
+ return result
+
+
+def remove_between(d, tips, ancestors):
+ """Remove the nodes between tips and ancestors.
+
+ This replaces the intermediate nodes with a quick jump.
+ """
+ result = {}
+ for ancestor in _find_ancestors(d, ancestors):
+ result[ancestor] = d[ancestor]
+ for ancestor in ancestors:
+ result[ancestor] = d[ancestor]
+ ancestors = tuple(ancestors)
+ for t in tips:
+ result[t] = ancestors
+ return result
+
+
def main(args):
import optparse
p = optparse.OptionParser('%prog filename')
=== modified file 'test_per_file_graph.py'
--- a/test_per_file_graph.py 2008-07-09 14:49:08 +0000
+++ b/test_per_file_graph.py 2008-07-09 17:16:11 +0000
@@ -56,3 +56,16 @@
# 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)
+
+
+class TestRemoveAncestors(tests.TestCase):
+
+ def assertRemoved(self, expected, original, ancestor_node):
+ self.assertEqual(expected, per_file_graph.remove_ancestors_of(
+ original, ancestor_node))
+
+ def test_simple(self):
+ self.assertRemoved({1:(2,), 2:()}, {1:[2], 2:[3], 3:[]}, 2)
+
+ def test_extra_references(self):
+ self.assertRemoved({1:(2,), 2:()}, {1:[2, 4], 2:[3], 3:[4], 4:[]}, 2)
More information about the bazaar-commits
mailing list