Bazaar

Merge lp:~garyvdm/bzr/loggraphviz into lp:bzr

loggraphviz
Merge into bzr.dev

Proposed by Gary van der Merwe on 2010-11-18

Status:	Work in progress
Proposed branch:	lp:~garyvdm/bzr/loggraphviz
Merge into:	lp:bzr
Diff against target:	2822 lines (+2802/-0) 3 files modified bzrlib/loggraphviz.py (+1648/-0) bzrlib/tests/__init__.py (+1/-0) bzrlib/tests/test_loggraphviz.py (+1153/-0)
To merge this branch:	bzr merge lp:~garyvdm/bzr/loggraphviz
Related bugs:	Link a bug report

Reviewer	Review Type	Date Requested	Status
bzr-core		2010-11-18	Pending
Review via email: mp+41146@code.launchpad.net

Description of the change

This branch includes the loggraphviz module from qbzr, and is the module that implements the most of the logic for qlog, which I have refactored in the hopes that it may be used other plugins.

I have implemented a proof of concept loggerhead viz view which use this. This is available here: lp:~garyvdm/loggerhead/loggraphviz

There is still lots of work that I would like to do before this actually lands. E.g.:
* The doc strings need to be completed, improved, and reviewed.
* I want to have the api between the State objects, and Filters, especially how one adds a filter to a state more clearly defined.
* I need to mark private/internal methods with _.
* I want to do a bzr-gtk viz poc. viz has a number of features that qlog does not, i.e. progress bar, a revision command line argument to specify a tip., and a limit argument. Implementing these my result in api changes.
* I would like to still investigate doing partial loading of merge sorted revisions using bzr-history-db for the use of loggerhead. This may also result in api changes.

So I know this is not 100% ready, but I feel that as I have now done the loggerhead poc, I now feel the time is right to get some comments on the code.

lp:~garyvdm/bzr/loggraphviz updated on 2010-11-18

5539. By Gary van der Merwe on 2010-11-18: Restore the utf marker in test_loggraphviz.py.

Revision history for this message

John A Meinel (jameinel) wrote on 2010-11-18:

Download full text (6.7 KiB)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/18/2010 4:02 AM, Gary van der Merwe wrote:
> Gary van der Merwe has proposed merging lp:~garyvdm/bzr/loggraphviz into lp:bzr.
>
> Requested reviews:
> bzr-core (bzr-core)
>
>
> This branch includes the loggraphviz module from qbzr, and is the module that implements the most of the logic for qlog, which I have refactored in the hopes that it may be used other plugins.
>
> I have implemented a proof of concept loggerhead viz view which use this. This is available here: lp:~garyvdm/loggerhead/loggraphviz
>
> There is still lots of work that I would like to do before this actually lands. E.g.:
> * The doc strings need to be completed, improved, and reviewed.
> * I want to have the api between the State objects, and Filters, especially how one adds a filter to a state more clearly defined.
> * I need to mark private/internal methods with _.
> * I want to do a bzr-gtk viz poc. viz has a number of features that qlog does not, i.e. progress bar, a revision command line argument to specify a tip., and a limit argument. Implementing these my result in api changes.
> * I would like to still investigate doing partial loading of merge sorted revisions using bzr-history-db for the use of loggerhead. This may also result in api changes.
>
> So I know this is not 100% ready, but I feel that as I have now done the loggerhead poc, I now feel the time is right to get some comments on the code.

To start off, I think the work you've done on graph visualization is
great, and I agree that it would be good to pull the core of that into
bzrlib itself.

'loggraphviz' is a bit clumsy for me. I don't have great ideas, but at
the very least it should be "log_graph_viz". I think calling it
"graph_visualization", or even just "graph_viz" would be reasonable.

I don't think you need to call each class GraphVizFoo inside the
loggraphviz module, though we've had discussions about that (without
strict resolution, afaict).

For naming, I would think that something called "Loader()" would return
the state object as part of .load(), rather than internalizing it. Your
example is:

+.. python::
+ bi = loggraphviz.BranchInfo('branch-label', tree, branch)
+ graph_viz = loggraphviz.GraphVizLoader([bi], bi, False)
+ graph_viz.load()
+ state = loggraphviz.GraphVizFilterState(graph_viz)
+ computed = graph_viz.compute_viz(state)

I would say,

1) Do we need the BranchInfo? Could it be done slightly differently?
loader = GraphVizLoader()
loader.add_branch('branch-label', branch)
# loader.add_tree() ?
# loader.add_branch('branch-label', branch, tree=<optional>)
state = loader.process()
for node in state.iter_nodes():
...

Basically, BranchInfo can be an implementation detail, rather than
something you create and-then-add.

+ def __eq__(self, other):
+ if isinstance(other, BranchInfo):
+ return self.branch.base.__eq__(other.branch.base)
+ return False

^- it seems odd that you don't check whether the label, presence of a
tree, or index are the same. I wonder if we really want to use "__eq__"
for this comparison, versus ".same_branch(other)"

Namely setting __hash__ and __eq__ in this w...

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sorry for sending this twice, hit reply to early.

On 11/18/2010 4:02 AM, Gary van der Merwe wrote:
> Gary van der Merwe has proposed merging lp:~garyvdm/bzr/loggraphviz into lp:bzr.
> 
> Requested reviews:
>   bzr-core (bzr-core)
> 
> 
> This branch includes the loggraphviz module from qbzr, and is the module that implements the most of the logic for qlog, which I have refactored in the hopes that it may be used other plugins.
> 
> I have implemented a proof of concept loggerhead viz view which use this. This is available here: lp:~garyvdm/loggerhead/loggraphviz
> 
> There is still lots of work that I would like to do before this actually lands. E.g.:
> * The doc strings need to be completed, improved, and reviewed.
> * I want to have the api between the State objects, and Filters, especially how one adds a filter to a state more clearly defined.
> * I need to mark private/internal methods with _.
> * I want to do a bzr-gtk viz poc. viz has a number of features that qlog does not, i.e. progress bar, a revision command line argument to specify a tip., and a limit argument. Implementing these my result in api changes.
> * I would like to still investigate doing partial loading of merge sorted revisions using bzr-history-db for the use of loggerhead. This may also result in api changes.
> 
> So I know this is not 100% ready, but I feel that as I have now done the loggerhead poc, I now feel the time is right to get some comments on the code.

To start off, I think the work you've done on graph visualization is
great, and I agree that it would be good to pull the core of that into
bzrlib itself.

I didn't go through everything thoroughly. I certainly didn't audit your
logic, etc. I have a feeling a lot of that is already well polished by
having this used by qbzr for so long.

I don't think you need to call each class GraphVizFoo inside the
loggraphviz module, though we've had discussions about that (without
strict resolution, afaict).

For naming, I would think that something called "Loader()" would return
the state object as part of .load(), rather than internalizing it. Your
example is:

+.. python::
+  bi = loggraphviz.BranchInfo('branch-label', tree, branch)
+  graph_viz = loggraphviz.GraphVizLoader([bi], bi, False)
+  graph_viz.load()
+  state = loggraphviz.GraphVizFilterState(graph_viz)
+  computed = graph_viz.compute_viz(state)

I would say,

1) Do we need the BranchInfo? Could it be done slightly differently?
 loader = GraphVizLoader()
 loader.add_branch('branch-label', branch)
 # loader.add_tree() ?
 # loader.add_branch('branch-label', branch, tree=<optional>)
 state = loader.process()
 for node in state.iter_nodes():
    ...

Basically, BranchInfo can be an implementation detail, rather than
something you create and-then-add.

+    def __eq__(self, other):
+        if isinstance(other, BranchInfo):
+            return self.branch.base.__eq__(other.branch.base)
+        return False

^- it seems odd that you don't check whether the label, presence of a
tree, or index are the same. I wonder if we really want to use "__eq__"
for this comparison, versus ".same_branch(other)"

^- I realize this works (python ignores strings that aren't assigned),
but I'm pretty sure the bzr convention is to use comment lines, not strings.

If you really want to document them, then they should go in as:

:ivar merged_by: Revision indexes that this revision merges.

+    revid = property(lambda self: self._merge_sort_node.key)

^- .key() is a tuple [often StaticTuple], whereas revid would hint that
it is a simple string.

+    def get_revno_str(self):

^- probably reasonable to add '.revno_str()' as a property on the
underlying MergeSortNodes.

+class GraphVizLoader(object):
...
+    def update_ui(self):
+        pass
+
+    def throbber_show(self):
+        pass
+
+    def throbber_hide(self):
+        pass
+

^- These all seem related to 'View' code, while this is more of a Model
object.

...
+        if len(graph_parents) > 0:
+            enabled = gc.isenabled()
+            if enabled:
+                gc.disable()

^- I think I wrote this code, especially given the comments that follow.
:) Still, we probably want a try/finally around this, to help force the
state in case of an exception.

'make_kg()' only exists because of profiling limitations for lsprof (it
doesn't time the __init__ times for extension classes, so you need to
wrap that it a function it can profile.)

I realize it may be slower. But really, if it is a bottleneck in getting
stuff done, we should be going down to pyrex, rather than writing
hard-to-understand python code.

In general, 'compute_viz' is way too big. Not counting the inline
functions, it is 230 lines. I think it would be a lot easier to
understand as a collection of small functions.

Is there a reason PendingMergesGraphVizLoader and
WithWorkingTreeGraphVizLoader are separate classes? At most it seems
like configuration flags to a single loader object.

...

+self.assertComputed(
+  [(u'current:%s' % tree.basedir, 0, True,                # âŠ–
+    [(0, 0, 0, True), (0, 1, 2, True)],                   #
â”œâ”€â•®
+    ['branch - Working Tree']),                           #
â”‚ â”‚
+   ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)], #
â”‚ â—‹
+    ['branch - Pending Merge']),                          #
â”œâ”€â•¯
+   ('rev-a', 0, None, [], ['branch'])],                   # â—‹
+            computed, branch_labels=True)

^- I'm pretty sure we try to avoid UTF-8 in our source code.

Especially since you don't have a -*- coding: utf-8 -*- line.

But even accounting for that, I get:
+self.assertComputed(
+ [(gv.tree_revid(new_tree), 2, None, [(2, 2, 3, True)]),    #     ○
+                                                            #     │
+  ('rev-new', 2, None, [(2, 2, 0, True)]),                  #     ○
+                                                            #     │
+  (gv.tree_revid(old_tree), 1, None, [(1, 1, 2, True),      #   ○ │
+                                      (2, 2, 0, True)]),    #   │ │
+  ('rev-old', 1, None, [(1, 1, 0, True), (2, 2, 0, True)]), #   ○ │
+                                                            #   │ │
+  (gv.tree_revid(trunk_tree), 0, None, [                    # ○ │ │
+     (0, 0, 0, True), (1, 1, 0, True), (2, 2, 0, True)]),   # │ │ │
+  ('rev-trunk', 0, None, [(0, 0, 0, True), (1, 0, 0, True), # ○ │ │
+                          (2, 0, 0, True)]),                # ├─╯─╯
+  ('rev-a', 0, None, [])],                                  # ○
+            computed)

Which doesnt seem a lot better than:

#     o
#     |
#     o
#   o |
#   | |
#   o |
#   | |
# o | |
# | | |
# o | |
# |/-'
# o

And all those lines are >80 chars as well.

And I get some *really* strange results in whatever font Thunderbird
tries to set as default.

Oh and gvim doesn't have ╯ as a character, it just renders it as a '[]' box.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzlhAoACgkQJdeBCYSNAAPxsgCdHB0afA4hzqTtwWqJkE1vMoUa
kRgAoKtnaXveH28KpPkVG5LhvlMRO+p8
=Izqt
-----END PGP SIGNATURE-----

Revision history for this message

Gary van der Merwe (garyvdm) wrote on 2010-11-19:

Download full text (10.2 KiB)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 18/11/2010 21:55, John A Meinel wrote:
> To start off, I think the work you've done on graph visualization is
> great, and I agree that it would be good to pull the core of that into
> bzrlib itself.
>
> I'm being a bit picky here, but I'm hoping to provide some feedback to
> make it easier to grow the code in the future. I certainly don't want to
> turn you off about it. And some bits we could put comments of "this is
> how we want it to be in the future", without having to do all of the
> implementation up front.

This is what I am looking for. You have raised some real issues, and
given some good suggestions. Thanks.

> 'loggraphviz' is a bit clumsy for me. I don't have great ideas, but at
> the very least it should be "log_graph_viz". I think calling it
> "graph_visualization", or even just "graph_viz" would be reasonable.

I guess I called it *log*graphviz, because it is specific to then log
graph, an not generic to any other graph, but it is quite log, so
graph_viz sounds good.

> I don't think you need to call each class GraphVizFoo inside the
> loggraphviz module, though we've had discussions about that (without
> strict resolution, afaict).

> For naming, I would think that something called "Loader()" would return
> the state object as part of .load(), rather than internalizing it. Your
> example is:
>
> +.. python::
> + bi = loggraphviz.BranchInfo('branch-label', tree, branch)
> + graph_viz = loggraphviz.GraphVizLoader([bi], bi, False)
> + graph_viz.load()
> + state = loggraphviz.GraphVizFilterState(graph_viz)
> + computed = graph_viz.compute_viz(state)
>
> I would say,

No, but maybe loader is a bad name. The loader keeps a cache of what it
loads. You may have more than state object per loader. In the case of
loggerhead, the loader is cached, valid until then branch tip changes.
For each http request, a new state object is created, with data parsed
from the http query. Maybe the load method of the loader should be
called by the loaders __init__ method.

> 1) Do we need the BranchInfo? Could it be done slightly differently?
> loader = GraphVizLoader()
> loader.add_branch('branch-label', branch)
> # loader.add_tree() ?
> # loader.add_branch('branch-label', branch, tree=<optional>)
> state = loader.process()
> for node in state.iter_nodes():
> ...
>
> Basically, BranchInfo can be an implementation detail, rather than
> something you create and-then-add.

Currently, having the qlog create the BranchInfo reduces it's plumbing,
because the BranchInfo are not created in then same place as then
GraphVizLoader. I need to look at changing this.

> + def __eq__(self, other):
> + if isinstance(other, BranchInfo):
> + return self.branch.base.__eq__(other.branch.base)
> + return False
>
> ^- it seems odd that you don't check whether the label, presence of a
> tree, or index are the same. I wonder if we really want to use "__eq__"
> for this comparison, versus ".same_branch(other)"
>
> Namely setting __hash__ and __eq__ in this way means that 2 BranchInfo
> structures that have some differences are going to end up in the same
> dictionary slot...

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 18/11/2010 21:55, John A Meinel wrote:
> To start off, I think the work you've done on graph visualization is
> great, and I agree that it would be good to pull the core of that into
> bzrlib itself.
> 
> I'm being a bit picky here, but I'm hoping to provide some feedback to
> make it easier to grow the code in the future. I certainly don't want to
> turn you off about it. And some bits we could put comments of "this is
> how we want it to be in the future", without having to do all of the
> implementation up front.

This is what I am looking for. You have raised some real issues, and
given some good suggestions. Thanks.

I guess I called it *log*graphviz, because it is specific to then log
graph, an not generic to any other graph, but it is quite log, so
graph_viz sounds good.

> I don't think you need to call each class GraphVizFoo inside the
> loggraphviz module, though we've had discussions about that (without
> strict resolution, afaict).

> For naming, I would think that something called "Loader()" would return
> the state object as part of .load(), rather than internalizing it. Your
> example is:
> 
> +.. python::
> +  bi = loggraphviz.BranchInfo('branch-label', tree, branch)
> +  graph_viz = loggraphviz.GraphVizLoader([bi], bi, False)
> +  graph_viz.load()
> +  state = loggraphviz.GraphVizFilterState(graph_viz)
> +  computed = graph_viz.compute_viz(state)
> 
> I would say,

> 1) Do we need the BranchInfo? Could it be done slightly differently?
>  loader = GraphVizLoader()
>  loader.add_branch('branch-label', branch)
>  # loader.add_tree() ?
>  # loader.add_branch('branch-label', branch, tree=<optional>)
>  state = loader.process()
>  for node in state.iter_nodes():
>     ...
> 
> Basically, BranchInfo can be an implementation detail, rather than
> something you create and-then-add.

Currently, having the qlog create the BranchInfo reduces it's plumbing,
because the BranchInfo are not created in then same place as then
GraphVizLoader. I need to look at changing this.

> +    def __eq__(self, other):
> +        if isinstance(other, BranchInfo):
> +            return self.branch.base.__eq__(other.branch.base)
> +        return False
> 
> ^- it seems odd that you don't check whether the label, presence of a
> tree, or index are the same. I wonder if we really want to use "__eq__"
> for this comparison, versus ".same_branch(other)"
> 
> Namely setting __hash__ and __eq__ in this way means that 2 BranchInfo
> structures that have some differences are going to end up in the same
> dictionary slot if you do my_info[bi] = X, my_info[bi2] = X, which may
> or may not be what you really want.

I'm actually going to remove these. They no longer needed.

> +        """Revision indexes that this revision merges"""
> +        self.merged_by = None
> +        """Revision index that merges this revision."""
> +        self.branch_id = self._merge_sort_node.revno[0:-1]
> 
> ^- I realize this works (python ignores strings that aren't assigned),
> but I'm pretty sure the bzr convention is to use comment lines, not strings.
> 
> If you really want to document them, then they should go in as:
> 
>  :ivar merged_by: Revision indexes that this revision merges.
> 
> Oh, and you put the docstrings after the variable, whereas I think it
> would be more common to put it before. All the more reason to put it in
> as instance variable documentation in the class's docstring.

Yes - I was doing that when I did not know about the :ivar method of
documenting variables. You will see then newer documentation is like
that, and I need to change these.

> +    revid = property(lambda self: self._merge_sort_node.key)
> 
> ^- .key() is a tuple [often StaticTuple], whereas revid would hint that
> it is a simple string.

key() in this case is a string, because then keys of the dict passed to
the KnownGraph are strings.

> +    def get_revno_str(self):
> 
> ^- probably reasonable to add '.revno_str()' as a property on the
> underlying MergeSortNodes.

> +class GraphVizLoader(object):
> ...
> +    def update_ui(self):
> +        pass
> +
> +    def throbber_show(self):
> +        pass
> +
> +    def throbber_hide(self):
> +        pass
> +
> 
> ^- These all seem related to 'View' code, while this is more of a Model
> object.

Hmmm - At the moment, I have a mixin the implements these. A much better
design would be to pass then view to then loader, and have then view
implement these. That would be a much better design.

> ...
> +        if len(graph_parents) > 0:
> +            enabled = gc.isenabled()
> +            if enabled:
> +                gc.disable()
> 
> ^- I think I wrote this code, especially given the comments that follow.
> :) Still, we probably want a try/finally around this, to help force the
> state in case of an exception.

Indeed.

> You have a lot of functions like "compute_viz" that make heavy use of
> local variables. It would be clearer if we wrote that into a separate
> class GraphVizComputer and made the shared state be class variables,
> rather than local variables.
> 
> I realize it may be slower. But really, if it is a bottleneck in getting
> stuff done, we should be going down to pyrex, rather than writing
> hard-to-understand python code.
> 
> In general, 'compute_viz' is way too big. Not counting the inline
> functions, it is 230 lines. I think it would be a lot easier to
> understand as a collection of small functions.

Good idea. I've come to dislike the inline functions. I don't think that
moving this to it's own class will make it slower, as it will only be
instantiating one instance of this object per compute.

> Is there a reason PendingMergesGraphVizLoader and
> WithWorkingTreeGraphVizLoader are separate classes? At most it seems
> like configuration flags to a single loader object.

When I first wrote them, the differences were more substantial. Through
refactoring, I have reduced then differences.

> +self.assertComputed(
> +  [(u'current:%s' % tree.basedir, 0, True,                # âŠ–
> +    [(0, 0, 0, True), (0, 1, 2, True)],                   #
> â”œâ”€â•®
> +    ['branch - Working Tree']),                           #
> â”‚ â”‚
> +   ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)], #
> â”‚ â—‹
> +    ['branch - Pending Merge']),                          #
> â”œâ”€â•¯
> +   ('rev-a', 0, None, [], ['branch'])],                   # â—‹
> +            computed, branch_labels=True)
> 
> ^- I'm pretty sure we try to avoid UTF-8 in our source code.
> 
> Especially since you don't have a -*- coding: utf-8 -*- line.

I had the # -*- coding: utf-8 -*- line in then qbzr copy. I removed by
mistake when I changed the copyright. I restored the line shortly after
I submitted the mp when I saw that the diff that launchpad sent was not
encoded correctly.

> But even accounting for that, I get:
> +self.assertComputed(
> + [(gv.tree_revid(new_tree), 2, None, [(2, 2, 3, True)]),    #     ○
> +                                                            #     │
> +  ('rev-new', 2, None, [(2, 2, 0, True)]),                  #     ○
> +                                                            #     │
> +  (gv.tree_revid(old_tree), 1, None, [(1, 1, 2, True),      #   ○ │
> +                                      (2, 2, 0, True)]),    #   │ │
> +  ('rev-old', 1, None, [(1, 1, 0, True), (2, 2, 0, True)]), #   ○ │
> +                                                            #   │ │
> +  (gv.tree_revid(trunk_tree), 0, None, [                    # ○ │ │
> +     (0, 0, 0, True), (1, 1, 0, True), (2, 2, 0, True)]),   # │ │ │
> +  ('rev-trunk', 0, None, [(0, 0, 0, True), (1, 0, 0, True), # ○ │ │
> +                          (2, 0, 0, True)]),                # ├─╯─╯
> +  ('rev-a', 0, None, [])],                                  # ○
> +            computed)
> 
> Which doesnt seem a lot better than:
> 
> #     o
> #     |
> #     o
> #   o |
> #   | |
> #   o |
> #   | |
> # o | |
> # | | |
> # o | |
> # |/-'
> # o
>
> Oh and gvim doesn't have ╯ as a character, it just renders it as a
'[]' box.

That does seem better.

These ascii^H^H^H^H^H unicode art are created by the format_graph_lines
method at the bottom of this file. It is also used when by
assertComputed. It does have a option to output to ascii, but it is alot
more difficult to read. Examples of this output:

Ascii       Unicode
 #     *    #     ○
 #     |    #     │
 #   * |    #   ○ │
 #   | |    #   │ │
 # * | |    # ○ │ │
 # |---     # ├─╯─╯
 # *        # ○

That ok. But when the graphs get a bit more complicated, it starts to fail.

# +        # ⊕
  # |---     # ├┄╮─╮
  # | : *    # │ ┆ ○
  # |  -|-   # │ ╰┄┼┄╮
  # |   | *  # │   │ ○
  # |   | |  # │   │ │
  # ~   | |  # ⊖   │ │
  # |-  | |  # ├─╮ │ │
  # | * | |  # │ ○ │ │
  # |-----   # ├─╯─╯─╯
  # *        # ○

The unicode versions made it much easier for me to debug problems.

> And I get some *really* strange results in whatever font Thunderbird
> tries to set as default.

Was that not because I left out the # -*- coding: utf-8 -*- line?  Do
the unicode characters show fine in this mail?

> And all those lines are >80 chars as well.

I did start trying to fit them in to < 80 chars, but this was time
consuming, and for me, makes it harder to read.

Here is a quote from PEP 8, which I feel applies:

> Two good reasons to break a particular rule:
>
> (1) When applying the rule would make the code less readable, even for
>     someone who is used to reading code that follows the rules.

Thanks alot for the review. You have give me lots of ideas on how to
improve this.

Gary
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzmPswACgkQd/3EdwGKOh29VACeJaw3QjFlMSSY602FQw7VvAIn
7/kAoItKldupr3CUBENiL8i/nMERwpf/
=hsUh
-----END PGP SIGNATURE-----

Revision history for this message

John A Meinel (jameinel) wrote on 2010-11-19:

Download full text (3.6 KiB)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

...

> Ascii Unicode
> # * # ○
> # | # │
> # * | # ○ │
> # | | # │ │
> # * | | # ○ │ │
> # |--- # ├─╯─╯
> # * # ○
>
>
> That ok. But when the graphs get a bit more complicated, it starts to fail.
>
> # + # ⊕
> # |--- # ├┄╮─╮
> # | : * # │ ┆ ○
> # | -|- # │ ╰┄┼┄╮
> # | | * # │ │ ○
> # | | | # │ │ │
> # ~ | | # ⊖ │ │
> # |- | | # ├─╮ │ │
> # | * | | # │ ○ │ │
> # |----- # ├─╯─╯─╯
> # * # ○
>
> The unicode versions made it much easier for me to debug problems.
>
>> And I get some *really* strange results in whatever font Thunderbird
>> tries to set as default.
>
> Was that not because I left out the # -*- coding: utf-8 -*- line? Do
> the unicode characters show fine in this mail?

I'm attaching the screenshot of the default font that Thunderbird is
using. Even stranger, it looks better, but still poorly aligned when
replying to your email. But it is completely unreadable in Vim. I did
eventually find a font where it looks ok (Deja Vu Sans Mono). But most
other fonts (Courier New especially) just show garbage.

I do understand how it could help you, but I'm curious if it doesn't
just add confusion for a lot of other people....

>
>> And all those lines are >80 chars as well.
>
> I did start trying to fit them in to < 80 chars, but this was time
> consuming, and for me, makes it harder to read.
>
> Here is a quote from PEP 8, which I feel applies:
>
>> Two good reasons to break a particular rule:
>>
>> (1) When applying the rule would make the code less readable, even for
>> someone who is used to reading code that follows the rules.
>

Couldn't you just put the graph by itself in a comment ahead of time? I
do this in bzrlib/tests/test_graph.py and it worked well for me.

If you did that, then you could even put both the ascii and unicode
versions. So you would have:

+ self.assertComputed(
+ [('rev-f', 0, True, [(0, 0, 0, True), (0, 2, 3, True)]),
+ ('rev-e', 2, True, [(0, 0, 0, True), (2, 2, 2, True)]),
+ ('rev-d', 0, True, [(0, 0, 0, True), (0, 1, 2, True), (2,
2, 2, True)]),
+ ('rev-c', 1, None, [(0, 0, 0, True), (1, 1, 2, True), (2,
1, 2, True)]),
+ ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)]),
+ ('rev-a', 0, None, [])]
+ computed)

That allows:
a) Less that 80 chars
b) You don't have the artificial extra blank lines in the list output
c) Put the ascii first. At least when I look at it, Unicode is more
likely to screw up the spacing, causing the ascii art to get
incorrectly drawn.

I realize it doesn't give you a strict line-to-line correspondence of
which list entry corresponds to what graph entry. But as long as t...

Unmerged revisions

5539. By Gary van der Merwe on 2010-11-18: Restore the utf marker in test_loggraphviz.py.
5538. By Gary van der Merwe on 2010-11-12: Make it possible to call GraphVizFilterState.collapse_expand_rev without changing the state, but rather return a new branch_line_state dict.
5537. By Gary van der Merwe on 2010-11-09: Assign copyright to Canonical Ltd.
5536. By Gary van der Merwe on 2010-11-09: Get tests to run.
5535. By Gary van der Merwe on 2010-11-09: Copy loggraphviz.py form qbzr rev 1336 revid:<email address hidden>

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk

Subscribers

People subscribed via source and target branches

to all changes:

Alejandro Cornejo2

Bazaar Codereview Subscribers

Benoit Pierre

Gary van der Merwe

Gmood

Karl Bielefeldt

Mahmoud Hassan

Matt Nordhoff

Mohd Fikri Mohd Amin

MrJOHN

Václav Haisman

bzr PQM

vincenzo

to status/vote changes:

Alexander Belchenko

amandla2023

 === added file 'bzrlib/loggraphviz.py'
 --- bzrlib/loggraphviz.py	1970-01-01 00:00:00 +0000
 +++ bzrlib/loggraphviz.py	2010-11-18 10:15:44 +0000
@@ -0,0 +1,1648 @@
++# Copyright (C) 2009, 2010 Canonical 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
++
++"""
++Layout a revision graph for visual representation, allowing for filtering and
++collapsible branches.
++
++Usage example
++=============
++
++.. python::
++  bi = loggraphviz.BranchInfo('branch-label', tree, branch)
++  graph_viz = loggraphviz.GraphVizLoader([bi], bi, False)
++  graph_viz.load()
++  state = loggraphviz.GraphVizFilterState(graph_viz)
++  computed = graph_viz.compute_viz(state)
++
++"""
++
++import gc
++from itertools import izip
++
++from bzrlib import errors
++from bzrlib.bzrdir import BzrDir
++from bzrlib.transport.local import LocalTransport
++from bzrlib.revision import NULL_REVISION, CURRENT_REVISION
++from bzrlib.graph import (
++    Graph,
++    StackedParentsProvider,
++    KnownGraph,
++    DictParentsProvider,
++    )
++
++
++class BranchInfo(object):
++    """Wrapper for a branch, it's working tree, if available, and a label."""
++
++    def __init__(self, label, tree, branch, index=None):
++        self.label = label
++        self.tree = tree
++        self.branch = branch
++        self.index = index
++
++    def __hash__(self):
++        return self.branch.base.__hash__()
++
++    def __eq__(self, other):
++        if isinstance(other, BranchInfo):
++            return self.branch.base.__eq__(other.branch.base)
++        return False
++
++
++class RevisionData(object):
++    """
++    Container for data for a revision in the graph that gets calculated
++    when the graph is loaded.
++    """
++
++    # Instance of this object are typically named "rev".
++
++    __slots__ = ["index", "_merge_sort_node", "branch", "_revno_str",
++                 "merges", "merged_by", 'branch_id', 'color']
++
++    def __init__(self, index, merge_sort_node):
++        """Create a new RevisionData instance."""
++        self.index = index
++        self._merge_sort_node = merge_sort_node
++        self.branch = None
++        self._revno_str = None
++        self.merges = []
++        """Revision indexes that this revision merges"""
++        self.merged_by = None
++        """Revision index that merges this revision."""
++        self.branch_id = self._merge_sort_node.revno[0:-1]
++        self.color = reduce(lambda x, y: x + y, self.branch_id, 0)
++
++    revid = property(lambda self: self._merge_sort_node.key)
++    merge_depth = property(lambda self: self._merge_sort_node.merge_depth)
++    revno_sequence = property(lambda self: self._merge_sort_node.revno)
++    end_of_merge = property(lambda self: self._merge_sort_node.end_of_merge)
++
++    def get_revno_str(self):
++        if self._revno_str is None:
++            self._revno_str = ".".join(["%d" % (revno)
++                                for revno in self.revno_sequence])
++            if self.revid.startswith(CURRENT_REVISION):
++                self._revno_str += " ?"
++        return self._revno_str
++    revno_str = property(get_revno_str)
++
++    def __repr__(self):
++        return "%s <%s %s>" % (self.__class__.__name__, self.revno_str,
++                              self.revid)
++
++class BranchLine(object):
++    """Container for data for a branch line, aka merge line."""
++
++    __slots__ = ["branch_id", "revs", "merges", "merged_by",
++                 "color", "merge_depth"]
++
++    def __init__(self, branch_id):
++        self.branch_id = branch_id
++        self.revs = []
++        self.merges = []
++        self.merged_by = []
++        self.merge_depth = 0
++
++    def __repr__(self):
++        return "%s <%s>" % (self.__class__.__name__, self.branch_id)
++
++
++class GhostRevisionError(errors.InternalBzrError):
++
++    _fmt = "{%(revision_id)s} is a ghost."
++
++    def __init__(self, revision_id):
++        errors.BzrError.__init__(self)
++        self.revision_id = revision_id
++
++
++class GraphVizLoader(object):
++    """
++    Loads graph for branches and provides computed layout for visual
++    representation.
++    """
++
++    # Most list/dicts related to revisions are unfiltered. When we do a graph
++    # layout, we filter these revisions. A revision may be filter out because:
++    # * It's branch is hidden (or collapsed).
++    # * We have a specified file_id(s), and the revision does not touch the
++    #   file_id(s).
++    # * We have a search, and the revision does not match the search.
++    #
++    # The main list of unfiltered revisions is self.revisions. A revisions
++    # index in revisions are normally called index. The main list of filtered
++    # revisions is filtered_revs. Revision indexes in this list are called
++    # f_index.
++
++    def __init__(self, branches, primary_bi, no_graph):
++        self.branches = branches
++        """List of BranchInfo for each branch."""
++        self.primary_bi = primary_bi
++        self.no_graph = no_graph
++
++        self.repos = []
++        self.local_repo_copies = []
++        """A list of repositories that revisions will be attempted to be loaded
++        from first."""
++
++        self.revid_head_info = {}
++        """Dict with a keys of head revid and value of
++            (list of (branch, label),
++             list of revids that are unique to this head)
++
++            We can't just store the BranchInfo, because the label may have
++            have addition text in it, e.g. "Working Tree", "Pending Merges"
++        """
++
++        self.revid_branch_info = {}
++
++        self.ghosts = set()
++
++        self.revisions = []
++        """List of RevisionInfo from merge_sort."""
++
++        self.revid_rev = {}
++        self.graph_children = {}
++
++        self.tags = {}      # map revid -> tags set
++
++    def load(self):
++        # Get a unique list of repositories. If the url is the same,
++        # we consider it the same repositories
++        repo_urls = set()
++        for bi in self.branches:
++            repo = bi.branch.repository
++            if repo.base not in repo_urls:
++                repo_urls.add(repo.base)
++                self.repos.append(repo)
++
++        no_local_repos = True
++        for repo in self.repos:
++            if repo_is_local(repo):
++                no_local_repos = False
++        if no_local_repos:
++            self.load_current_dir_repo()
++        self.repos.sort(key=lambda repo: not repo_is_local(repo))
++
++        self.lock_read_branches()
++        try:
++            head_revids, graph_parents = self.load_graph_parents()
++            self.process_graph_parents(head_revids, graph_parents)
++
++            self.compute_head_info()
++            del self.graph
++
++            if not self.no_graph:
++                self.compute_branch_lines()
++                self.compute_merge_info()
++
++            self.load_tags()
++        finally:
++            self.unlock_branches()
++
++
++    def load_current_dir_repo(self):
++        # There are no local repositories. Try open the repository
++        # of the current directory, and try load revisions data from
++        # this before trying from remote repositories. This makes
++        # the common use case of viewing a remote branch that is
++        # related to the current branch much faster, because most
++        # of the revision can be loaded from the local repository.
++        try:
++            bzrdir, relpath = BzrDir.open_containing(u".")
++            repo = bzrdir.find_repository()
++            self.repos.add(repo)
++            self.local_repo_copies.append(repo)
++        except Exception:
++            pass
++
++    def update_ui(self):
++        pass
++
++    def throbber_show(self):
++        pass
++
++    def throbber_hide(self):
++        pass
++
++    def lock_read_branches(self):
++        for bi in self.branches:
++            bi.branch.lock_read()
++        for repo in self.repos:
++            repo.lock_read()
++
++    def unlock_branches(self):
++        for bi in self.branches:
++            bi.branch.unlock()
++        for repo in self.repos:
++            repo.unlock()
++
++    #def lock_read_repos(self):
++    #    for repo in self.repos.itervalues():
++    #        repo.lock_read()
++    #
++    #def unlock_repos(self):
++    #    for repo in self.repos.itervalues():
++    #        repo.unlock()
++
++    def load_tags(self):
++        self.tags = {}
++        for bi in self.branches:
++            # revid to tags map
++            branch_tags = bi.branch.tags.get_reverse_tag_dict()
++            for revid, tags in branch_tags.iteritems():
++                if revid in self.tags:
++                    self.tags[revid].update(set(tags))
++                else:
++                    self.tags[revid] = set(tags)
++
++    def append_head_info(self, revid, branch_info, tag):
++        if not revid == NULL_REVISION:
++            if not revid in self.revid_head_info:
++                self.revid_head_info[revid] = ([], [])
++            self.revid_head_info[revid][0].append((branch_info, tag))
++
++            # So that early calls to get_revid_branch work
++            self.revid_branch_info[revid] = branch_info
++
++    def load_branch_heads(self, bi):
++        branch_heads = []
++
++        def append_head_info(revid, branch_info, label):
++            self.append_head_info(revid, branch_info, label)
++            branch_heads.append(revid)
++
++        if len(self.branches) > 0:
++            label = bi.label
++        else:
++            label = None
++
++        branch_last_revision = bi.branch.last_revision()
++        append_head_info(branch_last_revision, bi, bi.label)
++        self.update_ui()
++
++        if bi.tree:
++            parent_ids = bi.tree.get_parent_ids()
++            if parent_ids:
++                # first parent is last revision of the tree
++                revid = parent_ids[0]
++                if revid != branch_last_revision:
++                    # working tree is out of date
++                    if label:
++                        wt_label = "%s - Working Tree" % label
++                    else:
++                        wt_label = "Working Tree"
++                    append_head_info(revid, bi, wt_label)
++                # other parents are pending merges
++                for revid in parent_ids[1:]:
++                    if label:
++                        pm_label = "%s - Pending Merge" % label
++                    else:
++                        pm_label = "Pending Merge"
++                    append_head_info(revid, bi, pm_label)
++            self.update_ui()
++        return branch_heads, branch_heads, ()
++
++    def load_graph_parents(self):
++        """Load the heads of the graph, and the graph parents"""
++
++        extra_parents = {}
++        branches_heads = []
++
++        def load_branch_heads(bi, insert_at_begin=False):
++            load_heads, sort_heads, extra_parents_ = self.load_branch_heads(bi)
++            for key, parents in extra_parents_:
++                extra_parents[key] = parents
++            if insert_at_begin:
++                branches_heads.insert(0, (load_heads, sort_heads))
++            else:
++                branches_heads.append((load_heads, sort_heads))
++
++        for bi in self.branches:
++            # Don't do the primary branch, as that will be inserted later at
++            # the first position.
++            if bi != self.primary_bi:
++                load_branch_heads(bi)
++
++        if len(branches_heads) >= 2:
++            head_revids = [revid for load_heads, sort_heads in branches_heads
++                                 for revid in load_heads]
++            head_revs = self.load_revisions(head_revids)
++
++            get_max_timestamp = lambda branch_heads: max(
++                [head_revs[revid].timestamp for revid in branch_heads[0]])
++            branches_heads.sort(key=get_max_timestamp, reverse=True)
++
++        if self.primary_bi:
++            load_branch_heads(self.primary_bi, True)
++
++        load_heads = [revid for load_heads_, sort_heads_ in branches_heads
++                      for revid in load_heads_]
++        sort_heads = [revid for load_heads_, sort_heads_ in branches_heads
++                      for revid in sort_heads_]
++
++        parents_providers = [repo._make_parents_provider() \
++                             for repo in self.repos]
++        parents_providers.append(DictParentsProvider(extra_parents))
++        self.graph = Graph(StackedParentsProvider(parents_providers))
++
++        return sort_heads, self.graph.iter_ancestry(sort_heads)
++
++    def process_graph_parents(self, head_revids, graph_parents_iter):
++        graph_parents = {}
++        self.ghosts = set()
++
++        for (revid, parent_revids) in graph_parents_iter:
++            if revid == NULL_REVISION:
++                continue
++            if parent_revids is None:
++                #Ghost
++                graph_parents[revid] = ()
++                self.ghosts.add(revid)
++            elif parent_revids == (NULL_REVISION,):
++                graph_parents[revid] = ()
++            else:
++                graph_parents[revid] = parent_revids
++            if len(graph_parents) % 100 == 0:
++                self.update_ui()
++
++        graph_parents["top:"] = head_revids
++
++        if len(graph_parents) > 0:
++            enabled = gc.isenabled()
++            if enabled:
++                gc.disable()
++
++            def make_kg():
++                return KnownGraph(graph_parents)
++            self.known_graph = make_kg()
++
++            merge_sorted_revisions = self.known_graph.merge_sort('top:')
++            # So far, we are a bit faster than the pure-python code. But the
++            # last step hurts. Specifically, we take
++            #   377ms KnownGraph(self.graph_parents)
++            #   263ms kg.merge_sort() [640ms combined]
++            #  1322ms self.revisions = [...]
++            # vs
++            #  1152ms tsort.merge_sort(self.graph_parents)
++            #   691ms self.revisions = [...]
++            #
++            # It is a gc thing... :(
++            # Adding gc.disable() / gc.enable() around this whole loop changes
++            # things to be:
++            #   100ms   KnownGraph(self.graph_parents)
++            #    77ms   kg.merge_sort() [177ms combined]
++            #   174ms   self.revisions = [...]
++            # vs
++            #   639ms   tsort.merge_sort(self.graph_parents)
++            #   150ms   self.revisions = [...]
++            # Also known as "wow that's a lot faster". This is because KG()
++            # creates a bunch of Python objects, then merge_sort() creates a
++            # bunch more. And then self.revisions() creates another whole set.
++            # And all of these are moderately long lived, so you have a *lot*
++            # of allocations without removals (which triggers the gc checker
++            # over and over again.) And they probably don't live in cycles
++            # anyway, so you can skip it for now, and just run at the end.
++
++            # self.revisions *is* a little bit slower. Probably because pyrex
++            # MergeSortNodes use long integers rather than PyIntObject and thus
++            # create them on-the-fly.
++
++            # Get rid of the 'top:' revision
++            merge_sorted_revisions.pop(0)
++            self.revisions = [RevisionData(index, node)
++                for index, node in enumerate(merge_sorted_revisions)]
++            if enabled:
++                gc.enable()
++        else:
++            self.revisions = ()
++
++        self.revid_rev = {}
++        self.revno_rev = {}
++
++        self.max_mainline_revno = 0
++
++        for rev in self.revisions:
++            self.max_mainline_revno = max(self.max_mainline_revno,
++                                          rev.revno_sequence[0])
++            self.revid_rev[rev.revid] = rev
++            self.revno_rev[rev.revno_sequence] = rev
++
++    def branch_id_sort_key(self, x):
++        merge_depth = self.branch_lines[x].merge_depth
++
++        # Note: This greatly affects the layout of the graph.
++        #
++        # Branch line that have a smaller merge depth should be to the left
++        # of those with bigger merge depths.
++        #
++        # For branch lines that have the same parent in the mainline -
++        # those with bigger branch numbers to be to the rights. E.g. for
++        # the following dag, you want the graph to appear as on the left,
++        # not as on the right:
++        #
++        # 3     F_       F
++        #       | \      |\
++        # 1.2.1 |  E     | E
++        #       |  |     | \
++        # 2     D  |     D_|
++        #       |\ |     | +_
++        # 1.1.2 | C|     | | C
++        #       | |/     |  \|
++        # 1.1.1 | B      |   B
++        #       |/       | /
++        # 1     A        A
++        #
++        # Otherwise, those with a greater mainline parent revno should
++        # appear to the left.
++
++        if len(x) == 0:
++            return (merge_depth)
++        else:
++            return (merge_depth, -x[0], x[1])
++
++    def compute_branch_lines(self):
++        self.branch_lines = {}
++
++        """A list of branch lines (aka merge lines).
++
++        For a revisions, the revision number less the least significant
++        digit is the branch_id, and used as the key for the dict. Hence
++        revision with the same revision number less the least significant
++        digit are considered to be in the same branch line. e.g.: for
++        revisions 290.12.1 and 290.12.2, the branch_id would be 290.12,
++        and these two revisions will be in the same branch line.
++
++        """
++
++        self.branch_ids = []
++        """List of branch ids, sorted in the order that the branches will
++        be shown, from left to right on the graph."""
++
++        for rev in self.revisions:
++
++            branch_line = None
++            if rev.branch_id not in self.branch_lines:
++                branch_line = BranchLine(rev.branch_id)
++                self.branch_lines[rev.branch_id] = branch_line
++            else:
++                branch_line = self.branch_lines[rev.branch_id]
++
++            branch_line.revs.append(rev)
++            branch_line.merge_depth = max(rev.merge_depth,
++                                          branch_line.merge_depth)
++            rev.branch = branch_line
++
++        self.branch_ids = self.branch_lines.keys()
++
++        self.branch_ids.sort(key=self.branch_id_sort_key)
++
++    def compute_merge_info(self):
++
++        def set_merged_by(rev, merged_by, merged_by_rev, do_branches=False):
++            if merged_by is None:
++                return
++
++            if merged_by_rev is None:
++                merged_by_rev = self.revisions[merged_by]
++            rev.merged_by = merged_by
++            merged_by_rev.merges.append(rev.index)
++
++            if do_branches:
++                branch_id = rev.branch_id
++                branch_merged_by = self.branch_lines[branch_id].merged_by
++                merged_by_branch_id = self.revisions[merged_by].branch_id
++                merged_by_branch_merges = \
++                    self.branch_lines[merged_by_branch_id].merges
++
++                if not branch_id in merged_by_branch_merges:
++                    merged_by_branch_merges.append(branch_id)
++                if not merged_by_branch_id in branch_merged_by:
++                    branch_merged_by.append(merged_by_branch_id)
++
++        for rev in self.revisions:
++
++            parents = [self.revid_rev[parent] for parent in
++                       self.known_graph.get_parent_keys(rev.revid)]
++
++            if len(parents) > 0:
++                if rev.branch_id == parents[0].branch_id:
++                    set_merged_by(parents[0], rev.merged_by, None)
++
++            for parent in parents[1:]:
++                if rev.merge_depth <= parent.merge_depth:
++                    set_merged_by(parent, rev.index, rev, do_branches=True)
++
++    def compute_head_info(self):
++        def get_revid_head(heads):
++            map = {}
++            for i in xrange(len(heads)):
++                prev_revids = [revid for revid, head in heads[:i]]
++                unique_ancestors = self.graph.find_unique_ancestors(
++                    heads[i][0], prev_revids)
++                for ancestor_revid in unique_ancestors:
++                    map[ancestor_revid] = heads[i][1]
++            return map
++
++        if len(self.branches) > 1:
++            head_revid_branch_info = sorted(
++                [(revid, branch_info)
++                 for revid, (head_info, ur) in self.revid_head_info.iteritems()
++                 for (branch_info, tag) in head_info],
++                key=lambda x: not repo_is_local(x[1].branch.repository))
++            self.revid_branch_info = get_revid_head(head_revid_branch_info)
++        else:
++            self.revid_branch_info = {}
++
++        head_count = 0
++        for head_info, ur in self.revid_head_info.itervalues():
++            head_count += len(head_info)
++
++        if head_count > 1:
++            # Populate unique revisions for heads
++            for revid, (head_info, ur) in self.revid_head_info.iteritems():
++                rev = None
++                if revid in self.revid_rev:
++                    rev = self.revid_rev[revid]
++                if rev and rev.merged_by:
++                    # This head has been merged.
++                    # d
++                    # |\
++                    # b c
++                    # |/
++                    # a
++                    # if revid == c,then we want other_revids = [b]
++
++                    merged_by_revid = self.revisions[rev.merged_by].revid
++                    other_revids = [self.known_graph
++                                    .get_parent_keys(merged_by_revid)[0]]
++                else:
++                    other_revids = [other_revid for other_revid \
++                        in self.revid_head_info.iterkeys() \
++                        if not other_revid == revid]
++                ur.append(revid)
++                ur.extend([revid for revid \
++                    in self.graph.find_unique_ancestors(revid, other_revids) \
++                    if not revid == NULL_REVISION and revid in self.revid_rev])
++                ur.sort(key=lambda x: self.revid_rev[x].index)
++
++    def compute_viz(self, state):
++
++        # Overview:
++        # Work out which revision need to be displayed.
++        # Create ComputedGraphViz and ComputedRevisionData objects
++        # Assign columns for branches, and lines that go between branches.
++        #   These are intermingled, because some of the lines need to come
++        #   before it's branch, and others need to come after. Other lines
++        #   (such a the line from the last rev in a branch) are treated a
++        #   special cases.
++        # Return ComputedGraphViz object
++        gc_enabled = gc.isenabled()
++        gc.disable()
++        try:
++            computed = ComputedGraphViz(self)
++            computed.filtered_revs = [ComputedRevisionData(rev) for rev in
++                                      state.get_filtered_revisions()]
++
++            c_revisions = computed.revisions
++            for f_index, c_rev in enumerate(computed.filtered_revs):
++                c_revisions[c_rev.rev.index] = c_rev
++                c_rev.f_index = f_index
++
++            for (revid, (head_info,
++                         unique_revids)) in self.revid_head_info.iteritems():
++
++                for unique_revid in unique_revids:
++                    rev = self.revid_rev[unique_revid]
++                    c_rev = c_revisions[rev.index]
++                    if c_rev is not None:
++                        c_rev.branch_labels.extend(head_info)
++                        break
++        finally:
++            if gc_enabled:
++                gc.enable()
++
++        if self.no_graph:
++            for c_rev in computed.filtered_revs:
++                c_rev.col_index = c_rev.rev.merge_depth * 0.5
++            return computed
++
++        # This will hold a tuple of (child, parent, col_index, direct) for each
++        # line that needs to be drawn. If col_index is not none, then the line
++        # is drawn along that column, else the the line can be drawn directly
++        # between the child and parent because either the child and parent are
++        # in the same branch line, or the child and parent are 1 row apart.
++        lines = []
++        lines_by_column = []
++
++        def branch_line_col_search_order(start_col_index):
++            for col_index in range(start_col_index, len(lines_by_column)):
++                yield col_index
++            #for col_index in range(parent_col_index-1, -1, -1):
++            #    yield col_index
++
++        def line_col_search_order(parent_col_index, child_col_index):
++            if parent_col_index is not None and child_col_index is not None:
++                max_index = max(parent_col_index, child_col_index)
++                min_index = min(parent_col_index, child_col_index)
++                # First yield the columns between the child and parent.
++                for col_index in range(max_index, min_index - 1, -1):
++                    yield col_index
++            elif child_col_index is not None:
++                max_index = child_col_index
++                min_index = child_col_index
++                yield child_col_index
++            elif parent_col_index is not None:
++                max_index = parent_col_index
++                min_index = parent_col_index
++                yield parent_col_index
++            else:
++                max_index = 0
++                min_index = 0
++                yield 0
++            i = 1
++            # then yield the columns on either side.
++            while max_index + i < len(lines_by_column) or \
++                  min_index - i > -1:
++                if max_index + i < len(lines_by_column):
++                    yield max_index + i
++                #if min_index - i > -1:
++                #    yield min_index - i
++                i += 1
++
++        def is_col_free_for_range(col_index, child_f_index, parent_f_index):
++            return not any(
++                range_overlaps(child_f_index, parent_f_index,
++                               line_child_f_index, line_parent_f_index)
++                for line_child_f_index, line_parent_f_index
++                in lines_by_column[col_index])
++
++        def find_free_column(col_search_order, child_f_index, parent_f_index):
++            for col_index in col_search_order:
++                if is_col_free_for_range(col_index,
++                                             child_f_index, parent_f_index):
++                    break
++            else:
++                # No free columns found. Add an empty one on the end.
++                col_index = len(lines_by_column)
++                lines_by_column.append([])
++            return col_index
++
++        def append_line(child, parent, direct, col_index=None):
++            lines.append((child, parent, col_index, direct))
++
++            if col_index is not None:
++                lines_by_column[int(round(col_index))].append(
++                    (child.f_index, parent.f_index))
++
++        def find_visible_parent(c_rev, parent, twisty_hidden_parents):
++            if c_revisions[parent.index] is not None:
++                return (c_rev, c_revisions[parent.index], True)
++            else:
++                if parent.index in twisty_hidden_parents:
++                    # no need to draw a line if there is a twisty,
++                    # except if this is the last in the branch.
++                    return None
++                # The parent was not visible. Search for a ancestor
++                # that is. Stop searching if we make a hop, i.e. we
++                # go away from our branch, and we come back to it.
++                has_seen_different_branch = False
++                while c_revisions[parent.index] is None:
++                    if not parent.branch_id == c_rev.rev.branch_id:
++                        has_seen_different_branch = True
++                    # find grand parent.
++                    g_parent_ids = (self.known_graph
++                                    .get_parent_keys(parent.revid))
++
++                    if len(g_parent_ids) == 0:
++                        return None
++                    else:
++                        parent = self.revid_rev[g_parent_ids[0]]
++
++                    if (has_seen_different_branch and
++                        parent.branch_id == branch_id):
++                        # We have gone away and come back to our
++                        # branch. Stop.
++                        return None
++                if parent:
++                    # Not Direct
++                    return (c_rev, c_revisions[parent.index], False)
++
++        def append_branch_parent_lines(branch_rev_visible_parents):
++            groups = group_overlapping(branch_rev_visible_parents)
++            for parents, start, end, group_key in groups:
++                # Since all parents go from the same branch line to the
++                # same branch line, we can use the col indexes of the
++                # parent.
++                if end - start == 1:
++                    col_index = None
++                else:
++                    col_search_order = line_col_search_order(
++                        parents[0][1].col_index, parents[0][0].col_index)
++                    col_index = find_free_column(col_search_order,
++                                                 start, end)
++
++                col_offset_increment = 1.0 / len(parents)
++                for i, (c_rev, parent_c_rev, direct) in enumerate(parents):
++                    if col_index is None:
++                        col_index_offset = None
++                    else:
++                        col_index_offset = (col_index - 0.5 +
++                                            (i * col_offset_increment) +
++                                            (col_offset_increment / 2))
++                    append_line(c_rev, parent_c_rev,
++                                direct, col_index_offset)
++
++        for branch_id in self.branch_ids:
++            if not branch_id in state.branch_line_state:
++                continue
++
++            branch_line = self.branch_lines[branch_id]
++            branch_revs = [c_revisions[rev.index]
++                           for rev in branch_line.revs
++                           if c_revisions[rev.index] is not None]
++
++            if not branch_revs:
++                continue
++
++            branch_rev_visible_parents_post = []
++            branch_rev_visible_parents_pre = []
++            # Lists of ([(c_rev, parent_c_rev, is_direct)],
++            #            start, end, group_key]
++
++            last_c_rev = branch_revs[-1]
++            last_rev_left_parents = (self.known_graph
++                                     .get_parent_keys(last_c_rev.rev.revid))
++            if last_rev_left_parents:
++                last_parent = find_visible_parent(
++                    last_c_rev, self.revid_rev[last_rev_left_parents[0]], [])
++            else:
++                last_parent = None
++
++            sprout_with_lines = {}
++
++            merged_by_max_col_index = 0
++
++            # In this loop:
++            # * Populate twisty_branch_ids and twisty_state
++            # * Find visible parents.
++            # * Append lines that go before the branch line.
++            # * Append lines to children for sprouts.
++            for c_rev in branch_revs:
++                rev = c_rev.rev
++
++                if rev.merged_by is not None:
++                    merged_by_c_rev = c_revisions[rev.merged_by]
++                    if merged_by_c_rev:
++                        merged_by_max_col_index = max(
++                            merged_by_max_col_index, merged_by_c_rev.col_index)
++
++                parents = [self.revid_rev[parent_revid] for parent_revid in
++                           self.known_graph.get_parent_keys(rev.revid)]
++
++                twisty_hidden_parents = []
++                # Find and add necessary twisties
++                for parent in parents:
++                    if parent.branch_id == branch_id:
++                        continue
++                    if parent.branch_id == ():
++                        continue
++                    if parent.branch_id in branch_line.merged_by:
++                        continue
++                    parent_branch = self.branch_lines[parent.branch_id]
++                    # Does this branch have any visible revisions
++                    pb_visible = (parent_branch.branch_id in
++                                  state.branch_line_state)
++                    for pb_rev in parent_branch.revs:
++                        if pb_visible:
++                            visible = c_revisions[pb_rev.index] is not None
++                        else:
++                            visible = state\
++                                .get_revision_visible_if_branch_visible(pb_rev)
++                        if visible:
++                            (c_rev.twisty_expands_branch_ids
++                             .append(parent_branch.branch_id))
++                            if not pb_visible:
++                                twisty_hidden_parents.append(parent.index)
++                            break
++
++                # Work out if the twisty needs to show a + or -. If all
++                # twisty_branch_ids are visible, show - else +.
++                if len(c_rev.twisty_expands_branch_ids) > 0:
++                    c_rev.twisty_state = True
++                    for twisty_branch_id in c_rev.twisty_expands_branch_ids:
++                        if not twisty_branch_id in state.branch_line_state:
++                            c_rev.twisty_state = False
++                            break
++
++                # Don't include left hand parents All of these parents in the
++                # branch can be drawn with one line.
++                parents = parents[1:]
++
++                branch_id_sort_key = self.branch_id_sort_key(branch_id)
++                for i, parent in enumerate(parents):
++                    parent_info = find_visible_parent(c_rev, parent,
++                                                      twisty_hidden_parents)
++                    if parent_info:
++                        c_rev, parent_c_rev, direct = parent_info
++                        if (last_parent and
++                            parent_c_rev.f_index <= last_parent[1].f_index and
++                            self.branch_id_sort_key(parent_c_rev.rev.branch_id)
++                            < branch_id_sort_key):
++                            # This line goes before the branch line
++                            dest = branch_rev_visible_parents_pre
++                        else:
++                            # This line goes after
++                            dest = branch_rev_visible_parents_post
++
++                        line_len = parent_c_rev.f_index - c_rev.f_index
++                        if line_len == 1:
++                            group_key = None
++                        else:
++                            group_key = parent_c_rev.rev.branch_id
++
++                        dest.append(([parent_info],
++                                     c_rev.f_index,
++                                     parent_c_rev.f_index,
++                                     group_key))
++
++                # This may be a sprout. Add line to first visible child
++                if c_rev.rev.merged_by is not None:
++                    merged_by = self.revisions[c_rev.rev.merged_by]
++                    if c_revisions[merged_by.index] is None and\
++                       branch_revs[0].f_index == c_rev.f_index:
++                        # The revision that merges this revision is not
++                        # visible, and it is the first visible revision in
++                        # the branch line. This is a sprout.
++                        #
++                        # XXX What if multiple merges with --force,
++                        # aka octopus merge?
++                        #
++                        # Search until we find a descendant that is visible.
++
++                        while merged_by is not None and \
++                              c_revisions[merged_by.index] is None:
++                            if merged_by.merged_by is not None:
++                                merged_by = self.revisions[merged_by.merged_by]
++                            else:
++                                merged_by = None
++
++                        if merged_by is not None:
++                            # Ensure only one line to a descendant.
++                            if (merged_by.index not in sprout_with_lines):
++                                sprout_with_lines[merged_by.index] = True
++                                parent = c_revisions[merged_by.index]
++                                if parent is not None:
++                                    if c_rev.f_index - parent.f_index == 1:
++                                        col_index = None
++                                    else:
++                                        col_search_order = line_col_search_order(
++                                            parent.col_index, c_rev.col_index)
++                                        col_index = find_free_column(
++                                            col_search_order,
++                                            parent.f_index, c_rev.f_index)
++                                    append_line(parent, c_rev, False,
++                                                col_index)
++
++            # Find a column for this branch.
++            #
++            # Find the col_index for the direct parent branch. This will
++            # be the starting point when looking for a free column.
++
++            append_branch_parent_lines(branch_rev_visible_parents_pre)
++
++            if branch_id == ():
++                start_col_index = 0
++            else:
++                start_col_index = 1
++
++            if last_parent and last_parent[0].col_index is not None:
++                parent_col_index = last_parent[1].col_index
++                start_col_index = max(start_col_index, parent_col_index)
++
++            start_col_index = max(start_col_index, merged_by_max_col_index)
++
++            col_search_order = branch_line_col_search_order(start_col_index)
++
++            if last_parent:
++                col_index = find_free_column(col_search_order,
++                                             branch_revs[0].f_index,
++                                             last_parent[1].f_index)
++            else:
++                col_index = find_free_column(col_search_order,
++                                             branch_revs[0].f_index,
++                                             branch_revs[-1].f_index)
++
++            # Free column for this branch found. Set node for all
++            # revision in this branch.
++            for rev in branch_revs:
++                rev.col_index = col_index
++
++            append_line(branch_revs[0], branch_revs[-1], True, col_index)
++            if last_parent:
++                append_line(last_parent[0], last_parent[1],
++                            last_parent[2], col_index)
++
++            branch_rev_visible_parents_post.reverse()
++            append_branch_parent_lines(branch_rev_visible_parents_post)
++
++        # It has now been calculated which column a line must go into. Now
++        # copy the lines in to computed_revisions.
++        for (child, parent, line_col_index, direct) in lines:
++
++            parent_color = parent.rev.color
++
++            line_length = parent.f_index - child.f_index
++            if line_length == 0:
++                # Nothing to do
++                pass
++            elif line_length == 1:
++                child.lines.append(
++                    (child.col_index,
++                     parent.col_index,
++                     parent_color,
++                     direct))
++            else:
++                # line from the child's column to the lines column
++                child.lines.append(
++                    (child.col_index,
++                     line_col_index,
++                     parent_color,
++                     direct))
++                # lines down the line's column
++                for line_part_f_index in range(child.f_index + 1,
++                                               parent.f_index - 1):
++                    computed.filtered_revs[line_part_f_index].lines.append(
++                        (line_col_index,
++                         line_col_index,
++                         parent_color,
++                         direct))
++                # line from the line's column to the parent's column
++                computed.filtered_revs[parent.f_index - 1].lines.append(
++                    (line_col_index,
++                     parent.col_index,
++                     parent_color,
++                     direct))
++
++        return computed
++
++    def get_revid_branch_info(self, revid):
++        """This returns a branch info whos branch contains the revision.
++
++        If the revision exists more than one branch, it will only return the
++        first branch info. """
++
++        if revid in self.ghosts:
++            raise GhostRevisionError(revid)
++
++        if len(self.branches) == 1 or revid not in self.revid_branch_info:
++            return self.branches[0]
++        return self.revid_branch_info[revid]
++
++    def get_revid_branch(self, revid):
++        return self.get_revid_branch_info(revid).branch
++
++    def get_revid_repo(self, revid):
++        return self.get_revid_branch_info(revid).branch.repository
++
++    def get_repo_revids(self, revids):
++        """Returns list of tuple of (repo, revids)"""
++        repo_revids = {}
++        for repo in self.repos:
++            repo_revids[repo.base] = []
++
++        for local_repo_copy in self.local_repo_copies:
++            for revid in self.repos[local_repo_copy].has_revisions(revids):
++                revids.remove(revid)
++                repo_revids[local_repo_copy].append(revid)
++
++        for revid in revids:
++            try:
++                repo = self.get_revid_repo(revid)
++            except GhostRevisionError:
++                pass
++            else:
++                repo_revids[repo.base].append(revid)
++
++        return [(repo, repo_revids[repo.base])
++                for repo in self.repos]
++
++    def load_revisions(self, revids):
++        return_revisions = {}
++        for repo, revids in self.get_repo_revids(revids):
++            if revids:
++                repo.lock_read()
++                try:
++                    self.update_ui()
++                    for rev in repo.get_revisions(revids):
++                        return_revisions[rev.revision_id] = rev
++                finally:
++                    repo.unlock()
++        return return_revisions
++
++
++def repo_is_local(repo):
++    return isinstance(repo.bzrdir.transport, LocalTransport)
++
++def group_overlapping(groups):
++    """ Groups items with overlapping ranges together.
++
++    :param groups: List of uncollapsed groups.
++    :param group: (start of range, end of range, items in group)
++    :return: List of collapsed groups.
++
++    """
++
++    has_change = True
++    while has_change:
++        has_change = False
++        a = 0
++        while a < len(groups):
++            inner_has_change = False
++            items_a, start_a, end_a, group_key_a = groups[a]
++            if group_key_a is not None:
++                b = a + 1
++                while b < len(groups):
++                    items_b, start_b, end_b, group_key_b = groups[b]
++                    if (group_key_a == group_key_b and
++                        range_overlaps(start_a, end_a, start_b, end_b)):
++                            # overlaps. Merge b into a
++                            items_a.extend(items_b)
++                            start_a = min(start_a, start_b)
++                            end_a = max(end_a, end_b)
++                            del groups[b]
++                            has_change = True
++                            inner_has_change = True
++                    else:
++                        b += 1
++                if inner_has_change:
++                    groups[a] = (items_a, start_a, end_a, group_key_a)
++            a += 1
++
++    return groups
++
++def range_overlaps (start_a, end_a, start_b, end_b):
++    """Tests if two ranges overlap."""
++    return (start_b < start_a < end_b or
++            start_b < end_a < end_b or
++            (start_a <= start_b and end_a >= end_b))
++
++
++class PendingMergesGraphVizLoader(GraphVizLoader):
++    """GraphVizLoader that only loads pending merges.
++
++    As only the pending merges are passed to merge_sort, the revno
++    are incorrect, and should be ignored.
++
++    Only works on a single branch.
++
++    """
++
++    def load_graph_parents(self):
++        if not len(self.branches) == 1 or not len(self.repos) == 1:
++            AssertionError("load_graph_pending_merges should only be called \
++                           when 1 branch and repo has been opened.")
++
++        bi = self.branches[0]
++        if bi.tree is None:
++            AssertionError("PendingMergesGraphVizLoader must have a working "
++                           "tree.")
++
++        self.graph = bi.branch.repository.get_graph()
++        tree_heads = bi.tree.get_parent_ids()
++        other_revisions = [tree_heads[0], ]
++        self.update_ui()
++
++        self.append_head_info('root:', bi, None)
++        pending_merges = []
++        for head in tree_heads[1:]:
++            self.append_head_info(head, bi, None)
++            pending_merges.extend(
++                self.graph.find_unique_ancestors(head, other_revisions))
++            other_revisions.append(head)
++            self.update_ui()
++
++        graph_parents = self.graph.get_parent_map(pending_merges)
++        graph_parents["root:"] = ()
++        self.update_ui()
++
++        for (revid, parents) in graph_parents.items():
++            new_parents = []
++            for index, parent in enumerate(parents):
++                if parent in graph_parents:
++                    new_parents.append(parent)
++                elif index == 0:
++                    new_parents.append("root:")
++            graph_parents[revid] = tuple(new_parents)
++
++        return ["root:", ] + tree_heads[1:], graph_parents.items()
++
++
++class WithWorkingTreeGraphVizLoader(GraphVizLoader):
++    """
++    GraphVizLoader that shows uncommitted working tree changes as a node
++    in the graph, as if it was already committed.
++    """
++
++    def tree_revid(self, tree):
++        return CURRENT_REVISION + tree.basedir.encode('unicode-escape')
++
++    def load(self):
++        self.working_trees = {}
++        for bi in self.branches:
++            if not bi.tree is None:
++                self.working_trees[self.tree_revid(bi.tree)] = bi.tree
++
++        super(WithWorkingTreeGraphVizLoader, self).load()
++
++    def load_branch_heads(self, bi):
++        # returns load_heads, sort_heads and also calls append_head_info.
++        #
++        # == For branch with tree ==
++        # Graph                   | load_heads | sort_heads | append_head_info
++        # wt                      | No         | Yes        | Yes
++        # | \                     |            |            |
++        # | 1.1.2 pending merge   | Yes        | No         | Yes
++        # 2 |     basis rev       | Yes        | No         | Yes
++        #
++        # == For branch with tree not up to date ==
++        # Graph                   | load_heads | sort_heads | append_head_info
++        #   wt                    | No         | Yes        | Yes
++        #   | \                   |            |            |
++        #   | 1.1.2 pending merge | Yes        | No         | Yes
++        # 3/  |     branch tip    | Yes        | Yes        | Yes
++        # 2   |     basis rev     | Yes        | No         | No
++        #
++        # == For branch without tree ==
++        # branch tip              | Yes        | head       | yes
++
++        load_heads = []
++        sort_heads = []
++        extra_parents = []
++
++        if len(self.branches) > 0:
++            label = bi.label
++        else:
++            label = None
++
++        branch_last_revision = bi.branch.last_revision()
++        self.append_head_info(branch_last_revision, bi, bi.label)
++        load_heads.append(branch_last_revision)
++        self.update_ui()
++
++        if bi.tree:
++            wt_revid = self.tree_revid(bi.tree)
++            if label:
++                wt_label = "%s - Working Tree" % label
++            else:
++                wt_label = "Working Tree"
++            self.append_head_info(wt_revid, bi, wt_label)
++            parent_ids = bi.tree.get_parent_ids()
++
++            extra_parents.append((wt_revid, parent_ids))
++            load_heads.extend(parent_ids)
++
++            if parent_ids:
++                # first parent is last revision of the tree
++                if parent_ids[0] != branch_last_revision:
++                    # tree is not up to date.
++                    sort_heads.append(branch_last_revision)
++
++                # other parents are pending merges
++                for revid in parent_ids[1:]:
++                    if label:
++                        pm_label = "%s - Pending Merge" % label
++                    else:
++                        pm_label = "Pending Merge"
++                    self.append_head_info(revid, bi, pm_label)
++
++            sort_heads.append(wt_revid)
++            self.update_ui()
++        else:
++            sort_heads.append(branch_last_revision)
++
++        return load_heads, sort_heads, extra_parents
++
++
++class GraphVizFilterState(object):
++    """
++    Records the state of which branch lines are expanded, and what filters
++    are applied.
++    """
++
++    def __init__(self, graph_viz, filter_changed_callback=None):
++        self.graph_viz = graph_viz
++        self.filter_changed_callback = filter_changed_callback
++
++        self.branch_line_state = {}
++        "If a branch_id is in this dict, it is visible. The value of the dict "
++        "indicates which branches expanded this branch."
++
++        for revid in self.graph_viz.revid_head_info:
++            rev = self.graph_viz.revid_rev[revid]
++            self.branch_line_state[rev.branch_id] = None
++
++        self.filters = []
++
++        # This keeps a cache of the filter state so that when one of the
++        # filters notifies us of a change, we can check if anything did change.
++
++        self.filter_cache = [None for rev in self.graph_viz.revisions]
++
++    def get_filtered_revisions(self):
++        if self.graph_viz.no_graph:
++            rev_whos_branch_is_visible = self.graph_viz.revisions
++        else:
++            rev_whos_branch_is_visible = []
++            for branch_id in self.branch_line_state.iterkeys():
++                try:
++                    branch_line = self.graph_viz.branch_lines[branch_id]
++                except KeyError:
++                    continue
++                rev_whos_branch_is_visible.extend(branch_line.revs)
++            rev_whos_branch_is_visible.sort(key=lambda rev: rev.index)
++
++        visible = self.get_revision_visible_if_branch_visible
++        return (rev for rev in rev_whos_branch_is_visible if visible(rev))
++
++    def get_revision_visible_if_branch_visible(self, rev):
++        rev_filter_cache = self.filter_cache[rev.index]
++        if rev_filter_cache is None:
++            rev_filter_cache = \
++                self._get_revision_visible_if_branch_visible(rev)
++            self.filter_cache[rev.index] = rev_filter_cache
++        return rev_filter_cache
++
++    def _get_revision_visible_if_branch_visible(self, rev):
++        filters_value = True
++        for filter in self.filters:
++            if not filter.get_revision_visible(rev):
++                filters_value = False
++                break
++        if filters_value:
++            return True
++
++        if not self.graph_viz.no_graph:
++            for merged_index in rev.merges:
++                merged_rev = self.graph_viz.revisions[merged_index]
++                if self.get_revision_visible_if_branch_visible(merged_rev):
++                    return True
++
++        return False
++
++    def filter_changed(self, revs=None, last_call=True):
++        if revs is None:
++            self.filter_cache = [None for rev in self.graph_viz.revisions]
++            if self.filter_changed_callback:
++                self.filter_changed_callback()
++        else:
++            pending_revs = revs
++            processed_revs = set()
++            prev_cached_revs = []
++            while pending_revs:
++                rev = pending_revs.pop(0)
++                if rev in processed_revs:
++                    continue
++                processed_revs.add(rev)
++
++                rev_filter_cache = self.filter_cache[rev.index]
++
++                if rev_filter_cache is not None:
++                    prev_cached_revs.append((rev, rev_filter_cache))
++                self.filter_cache[rev.index] = None
++
++                if not self.graph_viz.no_graph:
++                    if rev.merged_by is not None:
++                        pending_revs.append(
++                            self.graph_viz.revisions[rev.merged_by])
++
++            # Check if any visibilities have changes. If they have, call
++            # filter_changed_callback
++            for rev, prev_visible in prev_cached_revs:
++                visible = self.get_revision_visible_if_branch_visible(rev)
++                if visible != prev_visible:
++                    if self.filter_changed_callback:
++                        self.filter_changed_callback()
++                    break
++
++    def ensure_rev_visible(self, rev):
++        if self.graph_viz.no_graph:
++            return False
++
++        branch_id = rev.branch_id
++        if branch_id not in self.branch_line_state:
++            self.branch_line_state[branch_id] = None
++            if self.filter_changed_callback:
++                self.filter_changed_callback()
++            return True
++        return False
++
++    def collapse_expand_rev(self, c_rev, in_place_mod=True):
++        if in_place_mod:
++            branch_line_state = self.branch_line_state
++        else:
++            # create a copy of the state dict
++            branch_line_state = dict(self.branch_line_state)
++
++        if c_rev is None:
++            return False
++        visible = not c_rev.twisty_state
++        branch_ids = zip(
++            c_rev.twisty_expands_branch_ids,
++            [c_rev.rev.branch_id] * len(c_rev.twisty_expands_branch_ids))
++
++        seen_branch_ids = set(branch_id
++                              for branch_id, expanded_by in branch_ids)
++        has_change = False
++        while branch_ids:
++            branch_id, expanded_by = branch_ids.pop()
++            if (branch_id in branch_line_state) != visible:
++                has_change = True
++            if not visible:
++                del branch_line_state[branch_id]
++                parents = self.graph_viz.branch_lines[branch_id].merges
++                for parent_branch_id in parents:
++                    parent_visible = parent_branch_id in branch_line_state
++                    if (not parent_visible or
++                        parent_branch_id in seen_branch_ids):
++                        continue
++
++                    if branch_line_state[parent_branch_id] == branch_id:
++                        # This branch expanded the parent branch, so we must
++                        # collapse it.
++                        branch_ids.append((parent_branch_id, branch_id))
++                        seen_branch_ids.add(parent_branch_id)
++                    else:
++                        # Check if this parent has any other visible branches
++                        # that merge it.
++                        has_visible = False
++                        parent = self.graph_viz.branch_lines[parent_branch_id]
++                        for merged_by_branch_id in parent.merged_by:
++                            if merged_by_branch_id in branch_line_state:
++                                has_visible = True
++                                break
++                        if not has_visible:
++                            branch_ids.append((parent_branch_id, branch_id))
++                            seen_branch_ids.add(parent_branch_id)
++            else:
++                branch_line_state[branch_id] = expanded_by
++        if has_change and self.filter_changed_callback and in_place_mod:
++            self.filter_changed_callback()
++        return branch_line_state
++
++    def expand_all_branch_lines(self):
++        for branch_id in self.graph_viz.branch_lines.keys():
++            if branch_id not in self.branch_line_state:
++                self.branch_line_state[branch_id] = None
++
++
++class FileIdFilter (object):
++    """
++    Filter that only shows revisions that modify one of the specified files.
++    """
++
++    def __init__(self, graph_viz, filter_changed_callback, file_ids):
++        self.graph_viz = graph_viz
++        self.filter_changed_callback = filter_changed_callback
++        self.file_ids = file_ids
++        self.has_dir = False
++        self.filter_file_id = [False for rev in self.graph_viz.revisions]
++
++        # don't filter working tree nodes
++        if isinstance(self.graph_viz, WithWorkingTreeGraphVizLoader):
++            for wt_revid in self.graph_viz.working_trees.iterkeys():
++                try:
++                    rev_index = self.graph_viz.revid_rev[wt_revid].index
++                    self.filter_file_id[rev_index] = True
++                except KeyError:
++                    pass
++
++
++    def uses_inventory(self):
++        return self.has_dir
++
++    def load(self, revids=None):
++        """Load which revisions affect the file_ids"""
++        if self.file_ids:
++            self.graph_viz.throbber_show()
++
++            for bi in self.graph_viz.branches:
++                tree = bi.tree
++                if tree is None:
++                    tree = bi.branch.basis_tree()
++
++                tree.lock_read()
++                try:
++                    for file_id in self.file_ids:
++                        if tree.kind(file_id) in ('directory',
++                                                  'tree-reference'):
++                            self.has_dir = True
++                            break
++                    if self.has_dir:
++                        break
++                finally:
++                    tree.unlock()
++
++            if revids is None:
++                revids = [rev.revid for rev in self.graph_viz.revisions]
++
++            for repo, revids in self.graph_viz.get_repo_revids(revids):
++                if self.uses_inventory():
++                    chunk_size = 200
++                else:
++                    chunk_size = 500
++
++                for start in xrange(0, len(revids), chunk_size):
++                    self.load_filter_file_id_chunk(repo,
++                            revids[start:start + chunk_size])
++
++            self.load_filter_file_id_chunk_finished()
++
++    def load_filter_file_id_chunk(self, repo, revids):
++        def check_text_keys(text_keys):
++            changed_revs = []
++            for file_id, revid in repo.texts.get_parent_map(text_keys):
++                rev = self.graph_viz.revid_rev[revid]
++                self.filter_file_id[rev.index] = True
++                changed_revs.append(rev)
++
++            self.graph_viz.update_ui()
++            self.filter_changed_callback(changed_revs, False)
++            self.graph_viz.update_ui()
++
++        repo.lock_read()
++        try:
++            if not self.uses_inventory():
++                text_keys = [(file_id, revid)
++                                for revid in revids
++                                for file_id in self.file_ids]
++                check_text_keys(text_keys)
++            else:
++                text_keys = []
++                # We have to load the inventory for each revisions, to find
++                # the children of any directories.
++                for inv, revid in izip(repo.iter_inventories(revids), revids):
++                    entries = inv.iter_entries_by_dir(
++                                         specific_file_ids=self.file_ids)
++                    for path, entry in entries:
++                        text_keys.append((entry.file_id, revid))
++                        if entry.kind == "directory":
++                            sub_entries = inv.iter_entries(from_dir=entry)
++                            for rc_path, rc_entry in sub_entries:
++                                text_keys.append((rc_entry.file_id, revid))
++
++                    self.graph_viz.update_ui()
++
++                check_text_keys(text_keys)
++        finally:
++            repo.unlock()
++
++    def load_filter_file_id_chunk_finished(self):
++        self.filter_changed_callback([], True)
++        self.graph_viz.throbber_hide()
++
++    def get_revision_visible(self, rev):
++        return self.filter_file_id[rev.index]
++
++
++class WorkingTreeHasChangeFilter(object):
++    """
++    Filter out working trees that don't have any changes.
++    """
++
++    def __init__(self, graph_viz, filter_changed_callback, file_ids):
++        self.graph_viz = graph_viz
++        self.file_ids = file_ids
++        if not isinstance(graph_viz, WithWorkingTreeGraphVizLoader):
++            raise TypeError('graph_viz expected to be a '
++                            'WithWorkingTreeGraphVizLoader')
++        self.filter_changed_callback = filter_changed_callback
++        self.tree_revids_with_changes = set()
++
++    def load(self):
++        """Load if the working trees have changes."""
++        self.tree_revids_with_changes = set()
++        self.graph_viz.throbber_show()
++        try:
++            for wt_revid, tree in self.graph_viz.working_trees.iteritems():
++                if self.has_changes(tree):
++                    self.tree_revids_with_changes.add(wt_revid)
++                rev = self.graph_viz.revid_rev[wt_revid]
++                self.filter_changed_callback([rev], False)
++            self.filter_changed_callback([], True)
++        finally:
++            self.graph_viz.throbber_hide()
++
++    def has_changes(self, tree):
++        """Quickly check that the tree contains at least one commitable change.
++
++        :param _from_tree: tree to compare against to find changes (default to
++            the basis tree and is intended to be used by tests).
++
++        :return: True if a change is found. False otherwise
++        """
++        tree.lock_read()
++        try:
++            # Copied from mutabletree, cause we need file_ids too.
++            # Check pending merges
++            if len(tree.get_parent_ids()) > 1:
++                return True
++            from_tree = tree.basis_tree()
++
++            specific_files = None
++            if self.file_ids:
++                specific_files = [tree.id2path(file_id)
++                                  for file_id in self.file_ids]
++
++            changes = tree.iter_changes(from_tree,
++                                        specific_files=specific_files)
++            try:
++                change = changes.next()
++                # Exclude root (talk about black magic... --vila 20090629)
++                if change[4] == (None, None):
++                    change = changes.next()
++                return True
++            except StopIteration:
++                # No changes
++                return False
++        finally:
++            tree.unlock()
++
++    def get_revision_visible(self, rev):
++        if rev.revid.startswith(CURRENT_REVISION):
++            return rev.revid in self.tree_revids_with_changes
++        else:
++            return True
++
++
++class ComputedRevisionData(object):
++    """Container for computed layout data for a revision.
++
++    :ivar rev: Reference to RevisionData. Use to get revno, revid, color and
++        others.
++    :ivar f_index: Index in `ComputedGraphViz.filtered_revs`.
++    :ivar col_index: Column index to place node for revision in.
++    :ivar lines: Lines that need to be drawn from from this revision's line to
++        the next revision's line. Note that not all these lines relate to this
++        revision, but be a part of a longer line that is passing this revision.
++
++        Each line is a tuple of `(end col_index, start col_index, color,
++        direct)`.
++
++        If direct is False, it indicates that this line represents an
++        ancestry, with revisions that are filtered. This should be shown as
++        a dotted line.
++
++    :ivar branch_labels: Labels for branch tips.
++    :ivar twisty_state: State of the revision:
++
++        * None: No twisty.
++        * True: There are branch lines that this revision merges that can
++          expanded. Show a '+'.
++        * False: All branches that this revision merges are already expanded.
++          Show a '-'.
++    :ivar twisty_expands_branch_ids: Branch lines that will be expanded if the
++        twisty is clicked.
++    """
++
++    # Instance of this object are typically named "c_rev".
++    __slots__ = ['rev', 'f_index', 'lines', 'col_index', 'branch_labels',
++                 'twisty_state', 'twisty_expands_branch_ids']
++
++    def __init__(self, rev):
++        self.rev = rev
++        self.lines = []
++        self.col_index = None
++        self.twisty_state = None
++        self.twisty_expands_branch_ids = []
++        self.branch_labels = []
++
++
++class ComputedGraphViz(object):
++    """Computed layout data for a graph.
++
++    :ivar graph_viz: Reference to parent `GraphVizLoader`.
++    :ivar filtered_revs: List `ComputedRevisionData`. Only visible revisions
++        are included.
++    :ivar revisions: List `ComputedRevisionData`. Revision that are not
++        visible are None.
++    """
++    def __init__(self, graph_viz):
++        self.graph_viz = graph_viz
++        self.filtered_revs = []
++        self.revisions = [None for i in xrange(len(graph_viz.revisions))]
 === modified file 'bzrlib/tests/__init__.py'
 --- bzrlib/tests/__init__.py	2010-10-18 17:06:37 +0000
 +++ bzrlib/tests/__init__.py	2010-11-18 10:15:44 +0000
@@ -3739,6 +3739,7 @@
          'bzrlib.tests.test_lockable_files',
          'bzrlib.tests.test_lockdir',
          'bzrlib.tests.test_log',
++        'bzrlib.tests.test_loggraphviz',
          'bzrlib.tests.test_lru_cache',
          'bzrlib.tests.test_lsprof',
          'bzrlib.tests.test_mail_client',
 === added file 'bzrlib/tests/test_loggraphviz.py'
 --- bzrlib/tests/test_loggraphviz.py	1970-01-01 00:00:00 +0000
 +++ bzrlib/tests/test_loggraphviz.py	2010-11-18 10:15:44 +0000
@@ -0,0 +1,1153 @@
++# -*- coding: utf-8 -*-
++# Copyright (C) 2010 Canonical 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
++
++from bzrlib.tests import TestCase, TestCaseWithTransport
++from StringIO import StringIO
++
++from bzrlib import loggraphviz
++from bzrlib.revision import NULL_REVISION
++
++# TODO:
++# Tag loading
++# Branch labels + Filtering
++# Ghosts
++# file_ids filtering
++
++class TestLogGraphVizMixin(object):
++    def computed_to_list(self, computed, branch_labels=False):
++        if not branch_labels:
++            item = lambda c_rev: (c_rev.rev.revid,
++                                  c_rev.col_index,
++                                  c_rev.twisty_state,
++                                  sorted(c_rev.lines),)
++        else:
++            item = lambda c_rev: (c_rev.rev.revid,
++                                  c_rev.col_index,
++                                  c_rev.twisty_state,
++                                  sorted(c_rev.lines),
++                                  [label for bi, label in c_rev.branch_labels])
++
++        return [item(c_rev) for c_rev in computed.filtered_revs]
++
++    def assertComputed(self, expected_list, computed, branch_labels=False):
++        computed_list = self.computed_to_list(computed, branch_labels)
++        if not expected_list == computed_list:
++            raise AssertionError(
++                "not equal: \nexpected_list = \n%scomputed_list = \n%s"
++                % (format_graph_lines(expected_list, use_unicode=True),
++                   format_graph_lines(computed_list, use_unicode=True),))
++
++
++class TestLogGraphVizWithBranches(TestCaseWithTransport, TestLogGraphVizMixin):
++
++    def test_no_commits(self):
++        br = self.make_branch('.')
++
++        bi = loggraphviz.BranchInfo('', None, br)
++        gv = loggraphviz.GraphVizLoader([bi], bi, False)
++        gv.load()
++
++        self.assertEqual(len(gv.revisions), 0)
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++        self.assertEqual(len(computed.revisions), 0)
++
++    def make_banches_for_tips_date_sorted(self):
++        builder = self.make_branch_builder('trunk')
++        builder.start_series()
++        builder.build_snapshot('rev-a', None, [
++            ('add', ('', 'TREE_ROOT', 'directory', '')),])
++        builder.build_snapshot('rev-old', ['rev-a'], [])
++        builder.build_snapshot('rev-new', ['rev-a'], [])
++        builder.build_snapshot('rev-trunk', ['rev-a'], [])
++        builder.finish_series()
++
++        trunk = builder.get_branch()
++        #trunk.set_last_revision('rev-trunk')
++
++        old = trunk.bzrdir.sprout('../old', revision_id='rev-old').open_branch()
++
++        new = trunk.bzrdir.sprout('../new', revision_id='rev-new').open_branch()
++
++        return trunk, old, new
++
++    def test_branch_tips_date_sorted(self):
++        trunk, old, new = self.make_banches_for_tips_date_sorted()
++
++        trunk_bi = loggraphviz.BranchInfo('trunk', None, trunk)
++        gv = loggraphviz.GraphVizLoader(
++            [trunk_bi,
++             loggraphviz.BranchInfo('old', None, old),
++             loggraphviz.BranchInfo('new', None, new),],
++            trunk_bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-new', 2, None, [(2, 2, 0, True)])                 , #     ○
++                                                                       #     │
++             ('rev-old', 1, None, [(1, 1, 0, True), (2, 2, 0, True)]), #   ○ │
++                                                                       #   │ │
++             ('rev-trunk', 0, None, [(0, 0, 0, True), (1, 0, 0, True), # ○ │ │
++                                     (2, 0, 0, True)]),                # ├─╯─╯
++             ('rev-a', 0, None, [])                                  ],# ○
++            computed)
++
++    def test_branch_tips_date_sorted_with_working_tree_provider(self):
++        trunk, old, new = self.make_banches_for_tips_date_sorted()
++        trunk_tree = trunk.bzrdir.create_workingtree()
++        old_tree = old.bzrdir.open_workingtree()
++        new_tree = new.bzrdir.open_workingtree()
++
++        trunk_bi = loggraphviz.BranchInfo('trunk', trunk_tree, trunk)
++        gv = loggraphviz.WithWorkingTreeGraphVizLoader(
++            [trunk_bi,
++             loggraphviz.BranchInfo('old', old_tree, old),
++             loggraphviz.BranchInfo('new', new_tree, new),],
++            trunk_bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [(gv.tree_revid(new_tree), 2, None, [(2, 2, 3, True)]),    #     ○
++                                                                       #     │
++             ('rev-new', 2, None, [(2, 2, 0, True)]),                  #     ○
++                                                                       #     │
++             (gv.tree_revid(old_tree), 1, None, [(1, 1, 2, True),      #   ○ │
++                                                 (2, 2, 0, True)]),    #   │ │
++             ('rev-old', 1, None, [(1, 1, 0, True), (2, 2, 0, True)]), #   ○ │
++                                                                       #   │ │
++             (gv.tree_revid(trunk_tree), 0, None, [                    # ○ │ │
++                (0, 0, 0, True), (1, 1, 0, True), (2, 2, 0, True)]),   # │ │ │
++             ('rev-trunk', 0, None, [(0, 0, 0, True), (1, 0, 0, True), # ○ │ │
++                                     (2, 0, 0, True)]),                # ├─╯─╯
++             ('rev-a', 0, None, [])],                                  # ○
++            computed)
++
++
++    def make_tree_with_pending_merge(self, path):
++        builder = self.make_branch_builder('branch')
++        builder.start_series()
++        builder.build_snapshot('rev-a', None, [
++            ('add', ('', 'TREE_ROOT', 'directory', '')),])
++        builder.build_snapshot('rev-b', ['rev-a'], [])
++        builder.finish_series()
++
++        branch = builder.get_branch()
++        branch.set_last_revision_info(1, 'rev-a') # go back to rev-a
++        tree = branch.bzrdir.create_workingtree()
++        tree.merge_from_branch(branch, to_revision='rev-b')
++
++        return tree
++
++    def make_tree_not_up_to_date(self, path):
++        builder = self.make_branch_builder('branch')
++        builder.start_series()
++        builder.build_snapshot('rev-a', None, [
++            ('add', ('', 'TREE_ROOT', 'directory', '')),])
++        builder.build_snapshot('rev-b', ['rev-a'], [])
++        builder.finish_series()
++
++        branch = builder.get_branch()
++        tree = branch.bzrdir.create_workingtree()
++        tree.update(revision='rev-a')
++        return tree
++
++    def test_pending_merge(self):
++        tree = self.make_tree_with_pending_merge('branch')
++
++        bi = loggraphviz.BranchInfo(None, tree, tree.branch)
++        gv = loggraphviz.GraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-b', 1, None, [(1, 0, 0, True)], ['Pending Merge']), #   ○
++                                                                       # ╭─╯
++             ('rev-a', 0, None, [], [None])                          ],# ○
++            computed, branch_labels=True)
++
++    def test_out_of_date_wt(self):
++        tree = self.make_tree_not_up_to_date('branch')
++        bi = loggraphviz.BranchInfo(None, tree, tree.branch)
++        gv = loggraphviz.GraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-b', 0, None, [(0, 0, 0, True)], [None]), # ○
++                                                            # │
++             ('rev-a', 0, None, [], ['Working Tree'])     ],# ○
++            computed, branch_labels=True)
++
++    def test_with_working_tree_provider(self):
++        tree = self.make_tree_with_pending_merge('branch')
++
++        bi = loggraphviz.BranchInfo('branch', tree, tree.branch)
++        gv = loggraphviz.WithWorkingTreeGraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [(u'current:%s' % tree.basedir, 0, True,                # ⊖
++              [(0, 0, 0, True), (0, 1, 2, True)],                   # ├─╮
++              ['branch - Working Tree']),                           # │ │
++             ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)], # │ ○
++              ['branch - Pending Merge']),                          # ├─╯
++             ('rev-a', 0, None, [], ['branch'])],                   # ○
++            computed, branch_labels=True)
++
++    def test_with_working_tree_provider_out_of_date_wt(self):
++        tree = self.make_tree_not_up_to_date('branch')
++        bi = loggraphviz.BranchInfo('branch', tree, tree.branch)
++        gv = loggraphviz.WithWorkingTreeGraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [(u'current:%s' % tree.basedir, 1, None, [(1, 1, 0, True)], #   ○
++              ['branch - Working Tree']),                               #   │
++             ('rev-b', 0, None, [(0, 0, 0, True), (1, 0, 0, True)],     # ○ │
++              ['branch']),                                              # ├─╯
++             ('rev-a', 0, None, [], []) ],                              # ○
++            computed, branch_labels=True)
++
++    def test_with_working_tree_provider_filtered(self):
++        # This test makes sure that lable for a Working Tree shows for on it's
++        # nearest visble unique ansestor when the working tree node is
++        # filtered.
++        builder = self.make_branch_builder('branch')
++        builder.start_series()
++        builder.build_snapshot('rev-a', None, [
++            ('add', ('', 'TREE_ROOT', 'directory', '')),])
++        builder.build_snapshot('rev-b', ['rev-a'], [])
++        builder.build_snapshot('rev-c', ['rev-a'], [])
++        builder.finish_series()
++
++        branch = builder.get_branch()
++        tree = branch.bzrdir.create_workingtree()
++        tree.update(revision='rev-b')
++
++        bi = loggraphviz.BranchInfo('branch', tree, tree.branch)
++        gv = loggraphviz.WithWorkingTreeGraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.filters.append(BasicFilterer(set([
++            'current:%s' % tree.basedir.encode('unicode-escape')])))
++        computed = gv.compute_viz(state)
++        self.assertComputed(
++            [('rev-b', 1, None, [(1, 1, 0, True)], ['branch - Working Tree'])  , #   ○
++                                                                                 #   │
++             ('rev-c', 0, None, [(0, 0, 0, True), (1, 0, 0, True)], ['branch']), # ○ │
++                                                                                 # ├─╯
++             ('rev-a', 0, None, [], [])                                        ],# ○
++            computed, branch_labels=True)
++
++    def test_pending_merges_provider(self):
++        tree = self.make_tree_with_pending_merge('branch')
++
++        bi = loggraphviz.BranchInfo(None, tree, tree.branch)
++        gv = loggraphviz.PendingMergesGraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-b', 1, None, [(1, 0, 0, True)]), #   ○
++                                                    # ╭─╯
++             ('root:', 0, None, [])               ],# ○
++            computed)
++
++    def test_with_ghost(self):
++        tree = self.make_branch_and_tree('tree')
++        tree.commit('a', rev_id='rev-a')
++        tree.add_parent_tree_id('rev-b')
++        tree.commit('c', rev_id='rev-c')
++        # rev-b is a ghost. We think he is there, but he dose not exist. Boo!
++
++        bi = loggraphviz.BranchInfo(None, tree, tree.branch)
++        gv = loggraphviz.GraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.expand_all_branch_lines()
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-c', 0, True, [(0, 0, 0, True), (0, 1, 1, True)]), # ⊖
++                                                                     # ├─╮
++             ('rev-b', 1, None, [(0, 0, 0, True)])                 , # │ ○
++                                                                     # │
++             ('rev-a', 0, None, [])                                ],# ○
++            computed)
++
++    def test_with_ghost_mainline(self):
++        tree = self.make_branch_and_tree('tree')
++        tree.add_parent_tree_id('rev-a', allow_leftmost_as_ghost=True)
++        tree.commit('b', rev_id='rev-b')
++
++        bi = loggraphviz.BranchInfo(None, tree, tree.branch)
++        gv = loggraphviz.GraphVizLoader([bi], bi, False)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-b', 0, None, [(0, 0, 0, True)]), # ○
++                                                    # │
++             ('rev-a', 0, None, [])               ],# ○
++            computed)
++
++    def test_get_revid_branch_info(self):
++        builder = self.make_branch_builder('trunk')
++        builder.start_series()
++        builder.build_snapshot('rev-a', None, [
++            ('add', ('', 'TREE_ROOT', 'directory', '')),])
++        builder.build_snapshot('rev-branch', ['rev-a'], [])
++        builder.build_snapshot('rev-trunk', ['rev-a'], [])
++        builder.finish_series()
++        #   ○ branch
++        #   │
++        # ○ │ trunk
++        # ├─╯
++        # ○ rev-a
++
++        trunk = builder.get_branch()
++        #trunk.set_last_revision('rev-trunk')
++
++        branch = trunk.bzrdir.sprout('../branch',
++                                     revision_id='rev-branch').open_branch()
++
++        trunk_bi = loggraphviz.BranchInfo('trunk', None, trunk)
++        branch_bi = loggraphviz.BranchInfo('branch', None, branch)
++        gv = loggraphviz.GraphVizLoader(
++            [trunk_bi, branch_bi],
++            trunk_bi, False)
++        gv.load()
++
++        self.assertEqual(trunk_bi, gv.get_revid_branch_info('rev-trunk'))
++        self.assertEqual(branch_bi, gv.get_revid_branch_info('rev-branch'))
++
++        # may return either
++        self.assertIn(gv.get_revid_branch_info('rev-a'),
++                      (branch_bi, trunk_bi))
++
++    def test_get_revid_branch_info_with_ghost(self):
++        tree = self.make_branch_and_tree('tree')
++        tree.commit('a', rev_id='rev-a')
++        tree.add_parent_tree_id('rev-b')
++        tree.commit('c', rev_id='rev-c')
++        # rev-b is a ghost. We think he is there, but he dose not exist. Boo!
++        # c
++        # ├─╮
++        # │ b
++        # │
++        # a
++
++        bi = loggraphviz.BranchInfo(None, tree, tree.branch)
++        gv = loggraphviz.GraphVizLoader([bi], bi, False)
++        gv.load()
++
++        self.assertRaises(loggraphviz.GhostRevisionError,
++                          gv.get_revid_branch_info, 'rev-b')
++
++class TestLogGraphVizLayouts(TestCase, TestLogGraphVizMixin):
++
++    def test_basic_branch_line(self):
++        gv = BasicGraphVizLoader(('rev-d',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', ),
++         'rev-d': ('rev-b', 'rev-c'),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++
++        # only mainline.
++        self.assertComputed(
++            [('rev-d', 0, False, [(0, 0, 0, True)]), # ⊕
++                                                     # │
++             ('rev-b', 0, None, [(0, 0, 0, True)]) , # ○
++                                                     # │
++             ('rev-a', 0, None, [])                ],# ○
++             computed)
++
++        state.collapse_expand_rev(computed.filtered_revs[0])
++        computed = gv.compute_viz(state)
++
++        # expanded branch line.
++        self.assertComputed(
++            [('rev-d', 0, True, [(0, 0, 0, True), (0, 1, 2, True)]), # ⊖
++                                                                     # ├─╮
++             ('rev-c', 1, None, [(0, 0, 0, True), (1, 1, 0, True)]), # │ ○
++                                                                     # │ │
++             ('rev-b', 0, None, [(0, 0, 0, True), (1, 0, 0, True)]), # ○ │
++                                                                     # ├─╯
++             ('rev-a', 0, None, [])                                ],# ○
++            computed)
++
++    def test_branch_line_order(self):
++        gv = BasicGraphVizLoader(('rev-f',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-b', ),
++         'rev-d': ('rev-a', 'rev-c'),
++         'rev-e': ('rev-b', ),
++         'rev-f': ('rev-d', 'rev-e' ),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.expand_all_branch_lines()
++        computed = gv.compute_viz(state)
++
++        # branch lines should not cross over
++        self.assertComputed(
++            [('rev-f', 0, True, [(0, 0, 0, True), (0, 2, 3, True)])                 , # ⊖
++                                                                                      # ├───╮
++             ('rev-e', 2, True, [(0, 0, 0, True), (2, 2, 2, True)])                 , # │   ⊖
++                                                                                      # │   │
++             ('rev-d', 0, True, [(0, 0, 0, True), (0, 1, 2, True), (2, 2, 2, True)]), # ⊖   │
++                                                                                      # ├─╮ │
++             ('rev-c', 1, None, [(0, 0, 0, True), (1, 1, 2, True), (2, 1, 2, True)]), # │ ○ │
++                                                                                      # │ ├─╯
++             ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)])                 , # │ ○
++                                                                                      # ├─╯
++             ('rev-a', 0, None, [])                                                 ],# ○
++             computed)
++
++    def test_branch_line_order2(self):
++        gv = BasicGraphVizLoader(('rev-h',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-b', ),
++         'rev-d': ('rev-a', ),
++         'rev-e': ('rev-d', 'rev-b' ),
++         'rev-f': ('rev-e', ),
++         'rev-g': ('rev-e', 'rev-f' ),
++         'rev-h': ('rev-c', 'rev-g' ),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.expand_all_branch_lines()
++        computed = gv.compute_viz(state)
++
++        # branch lines should not cross over
++        self.assertComputed(
++            [('rev-h', 0, True, [(0, 0, 0, True), (0, 2, 2, True)])                 , # ⊖
++                                                                                      # ├───╮
++             ('rev-g', 2, True, [(0, 0, 0, True), (2, 2, 2, True), (2, 3, 3, True)]), # │   ⊖
++                                                                                      # │   ├─╮
++             ('rev-f', 3, None, [(0, 0, 0, True), (2, 2, 2, True), (3, 2, 2, True)]), # │   │ ○
++                                                                                      # │   ├─╯
++             ('rev-e', 2, None, [(0, 0, 0, True), (2, 1, 0, True), (2, 2, 2, True)]), # │   ○
++                                                                                      # │ ╭─┤
++             ('rev-d', 2, None, [(0, 0, 0, True), (1, 1, 0, True), (2, 2, 0, True)]), # │ │ ○
++                                                                                      # │ │ │
++             ('rev-c', 0, None, [(0, 0, 0, True), (1, 0, 0, True), (2, 2, 0, True)]), # ○ │ │
++                                                                                      # ├─╯ │
++             ('rev-b', 0, None, [(0, 0, 0, True), (2, 0, 0, True)])                 , # ○   │
++                                                                                      # ├───╯
++             ('rev-a', 0, None, [])                                                 ],# ○
++             computed)
++
++    def test_octopus_merge(self):
++        gv = BasicGraphVizLoader(('rev-e',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', ),
++         'rev-d': ('rev-a', ),
++         'rev-e': ('rev-a', 'rev-b', 'rev-c', 'rev-d'),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.expand_all_branch_lines()
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-e', 0, True, [(0, 0, 0, True), (0, 1, 2, True), (0, 2, 3, True), (0, 3, 4, True)]), # ⊖
++                                                                                                       # ├─╮─╮─╮
++             ('rev-b', 3, None, [(0, 0, 0, True), (1, 1, 2, True), (2, 2, 3, True), (3, 3, 0, True)]), # │ │ │ ○
++                                                                                                       # │ │ │ │
++             ('rev-c', 2, None, [(0, 0, 0, True), (1, 1, 2, True), (2, 2, 0, True), (3, 3, 0, True)]), # │ │ ○ │
++                                                                                                       # │ │ │ │
++             ('rev-d', 1, None, [(0, 0, 0, True), (1, 0, 0, True), (2, 0, 0, True), (3, 0, 0, True)]), # │ ○ │ │
++                                                                                                       # ├─╯─╯─╯
++             ('rev-a', 0, None, [])                                                                  ],# ○
++            computed)
++
++    def test_lots_of_merges_between_branch_lines(self):
++        gv = BasicGraphVizLoader(('rev-g',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-b', ),
++         'rev-d': ('rev-a', ),
++         'rev-e': ('rev-d', 'rev-b',),
++         'rev-f': ('rev-e', 'rev-c',),
++         'rev-g': ('rev-c', 'rev-f',),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.expand_all_branch_lines()
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-g', 0, True, [(0, 0, 0, True), (0, 2, 2, True)])                                           , # ⊖
++                                                                                                                # ├───╮
++             ('rev-f', 2, None, [(0, 0, 0, True), (2, 0.75, 0, True), (2, 2, 2, True)])                       , # │   ○
++                                                                                                                # │ ╭─┤
++             ('rev-e', 2, None, [(0, 0, 0, True), (0.75, 0.75, 0, True), (2, 1.25, 0, True), (2, 2, 2, True)]), # │ │ ○
++                                                                                                                # │ ├─┤
++             ('rev-d', 2, None, [(0, 0, 0, True), (0.75, 0, 0, True), (1.25, 1.25, 0, True), (2, 2, 0, True)]), # │ │ ○
++                                                                                                                # ├─┤ │
++             ('rev-c', 0, None, [(0, 0, 0, True), (1.25, 0, 0, True), (2, 2, 0, True)])                       , # ○ │ │
++                                                                                                                # ├─╯ │
++             ('rev-b', 0, None, [(0, 0, 0, True), (2, 0, 0, True)])                                           , # ○   │
++                                                                                                                # ├───╯
++             ('rev-a', 0, None, [])                                                                           ],# ○
++            computed)
++
++    def test_hidden_branch_line_hides_child_line(self):
++        gv = BasicGraphVizLoader(('rev-g',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', ),
++         'rev-d': ('rev-b', 'rev-c', ),
++         'rev-e': ('rev-b', 'rev-d', ),
++         'rev-f': ('rev-c', ),
++         'rev-g': ('rev-e', 'rev-f', ),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.branch_line_state[(2, 1)] = None
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-g', 0, False, [(0, 0, 0, True)])                 , # ⊕
++                                                                      # │
++             ('rev-e', 0, True, [(0, 0, 0, True), (0, 1, 3, True)]) , # ⊖
++                                                                      # ├─╮
++             ('rev-d', 1, False, [(0, 0, 0, True), (1, 0, 0, True)]), # │ ⊕
++                                                                      # ├─╯
++             ('rev-b', 0, None, [(0, 0, 0, True)])                  , # ○
++                                                                      # │
++             ('rev-a', 0, None, [])                                 ],# ○
++             computed)
++
++    def test_merge_line_hidden(self):
++        gv = BasicGraphVizLoader(('rev-d',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', 'rev-b'),
++         'rev-d': ('rev-a', 'rev-c'),
++        })
++        # d
++        # ├─╮
++        # │ c
++        # │ ├─╮
++        # │ │ b
++        # ├─╯─╯
++        # a
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.branch_line_state[(1, 1)] = None
++
++        computed = gv.compute_viz(state)
++        # when the merge by branch line, we should show a non direct line
++        self.assertComputed(
++            [('rev-d', 0, False, [(0, 0, 0, True), (0, 1, 2, False)]), # ⊕
++                                                                       # ├┄╮
++             ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)])  , # │ ○
++                                                                       # ├─╯
++             ('rev-a', 0, None, [])                                  ],# ○
++            computed)
++
++    def test_merge_line_hidden2(self):
++        gv = BasicGraphVizLoader(('rev-e',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-z': ('rev-a', ),
++         'rev-y': ('rev-a', 'rev-z', ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', ),
++         'rev-d': ('rev-a', 'rev-c'),
++         'rev-e': ('rev-y', 'rev-b', 'rev-d'),
++        })
++        # f
++        # ├─╮─╮
++        # │ b │
++        # │ │ │
++        # │ │ e
++        # │ │ ├─╮
++        # │ │ │ d
++        # ├─╯─╯─╯
++        # a
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        #state.expand_all_branch_lines()
++        state.branch_line_state[(1, 1)] = None
++        state.branch_line_state[(1, 2)] = None
++        #state.branch_line_state[(1, 3)] = None
++        state.branch_line_state[(1, 4)] = None
++
++        computed = gv.compute_viz(state)
++        # when the merge by branch line, we should show a non direct line
++        # this could layout better, but that's another story...
++        self.assertComputed(
++            [('rev-e', 0, False, [(0, 0, 0, True), (0, 1, 3, False), (0, 2, 5, True)])               , # ⊕
++                                                                                                       # ├┄╮─╮
++             ('rev-b', 2, None, [(0, 0, 0, True), (1, 3, 3, False), (2, 2, 0, True)])                , # │ ┆ ○
++                                                                                                       # │ ╰┄┼┄╮
++             ('rev-c', 3, None, [(0, 0, 0, True), (2, 2, 0, True), (3, 3, 0, True)])                 , # │   │ ○
++                                                                                                       # │   │ │
++             ('rev-y', 0, True, [(0, 0, 0, True), (0, 1, 2, True), (2, 2, 0, True), (3, 3, 0, True)]), # ⊖   │ │
++                                                                                                       # ├─╮ │ │
++             ('rev-z', 1, None, [(0, 0, 0, True), (1, 0, 0, True), (2, 0, 0, True), (3, 0, 0, True)]), # │ ○ │ │
++                                                                                                       # ├─╯─╯─╯
++             ('rev-a', 0, None, [])                                                                  ],# ○
++            computed)
++
++    def test_merge_line_hidden_merge_rev_filtered(self):
++        gv = BasicGraphVizLoader(('rev-e',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-b', ),
++         'rev-d': ('rev-a', 'rev-c'),
++         'rev-e': ('rev-a', 'rev-d'),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.filters.append(BasicFilterer(set(['rev-c'])))
++        state.branch_line_state[(1, 1)] = None
++
++        computed = gv.compute_viz(state)
++
++        # when the merge by branch line, we should show a non direct line
++        self.assertComputed(
++            [('rev-e', 0, False, [(0, 0, 0, True), (0, 1, 2, False)]), # ⊕
++                                                                       # ├┄╮
++             ('rev-b', 1, None, [(0, 0, 0, True), (1, 0, 0, True)])  , # │ ○
++                                                                       # ├─╯
++             ('rev-a', 0, None, [])                                  ],# ○
++            computed)
++
++    def test_non_direct_hidden_branch(self):
++        gv = BasicGraphVizLoader(('rev-f',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-b', ),
++         'rev-d': ('rev-a', 'rev-c', ),
++         'rev-e': ('rev-b', ),
++         'rev-f': ('rev-d', 'rev-e', ),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.branch_line_state[(1, 2)] = None
++
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-f', 0, True, [(0, 0, 0, True), (0, 1, 3, True)])  , # ⊖
++                                                                       # ├─╮
++             ('rev-e', 1, False, [(0, 0, 0, True), (1, 1, 0, False)]), # │ ⊕
++                                                                       # │ ┆
++             ('rev-d', 0, False, [(0, 0, 0, True), (1, 0, 0, False)]), # ⊕ ┆
++                                                                       # ├┄╯
++             ('rev-a', 0, None, [])                                  ],# ○
++            computed)
++
++    def test_non_direct_hidden_parent(self):
++        gv = BasicGraphVizLoader(('rev-e',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-b', ),
++         'rev-d': ('rev-a', 'rev-c'),
++         'rev-e': ('rev-a', 'rev-d'),
++        })
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.filters.append(BasicFilterer(set(['rev-c'])))
++        state.expand_all_branch_lines()
++
++        computed = gv.compute_viz(state)
++
++        self.assertComputed(
++            [('rev-e', 0, True, [(0, 0, 0, True), (0, 1, 3, True)])                  , # ⊖
++                                                                                       # ├─╮
++             ('rev-d', 1, True, [(0, 0, 0, True), (1, 1, 0, True), (1, 2, 2, False)]), # │ ⊖
++                                                                                       # │ ├┄╮
++             ('rev-b', 2, None, [(0, 0, 0, True), (1, 0, 0, True), (2, 0, 0, True)]) , # │ │ ○
++                                                                                       # ├─╯─╯
++             ('rev-a', 0, None, [])                                                  ],# ○
++            computed)
++
++    def test_no_graph(self):
++        gv = BasicGraphVizLoader(('rev-d',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', ),
++         'rev-d': ('rev-b', 'rev-c'),
++        }, no_graph=True)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        computed = gv.compute_viz(state)
++        self.assertComputed(
++            [('rev-d', 0.0, None, []), # ○
++                                       #
++             ('rev-c', 0.5, None, []), #  ○
++                                       #
++             ('rev-b', 0.0, None, []), # ○
++                                       #
++             ('rev-a', 0.0, None, [])],# ○
++            computed)
++
++    def test_no_graph_filtered(self):
++        gv = BasicGraphVizLoader(('rev-d',), {
++         'rev-a': (NULL_REVISION, ),
++         'rev-b': ('rev-a', ),
++         'rev-c': ('rev-a', ),
++         'rev-d': ('rev-b', 'rev-c'),
++        }, no_graph=True)
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        state.filters.append(BasicFilterer(set(['rev-b'])))
++        computed = gv.compute_viz(state)
++        self.assertComputed(
++            [('rev-d', 0.0, None, []), # ○
++                                       #
++             ('rev-c', 0.5, None, []), #  ○
++                                       #
++             ('rev-a', 0.0, None, [])],# ○
++            computed)
++
++class TestLogGraphProviderState(TestCase):
++
++    def assertFilteredRevisions(self, expected_revids, state):
++        revids = [rev.revid for rev in state.get_filtered_revisions()]
++        self.assertEqual(list(expected_revids), revids)
++
++    def test_collapse_expand_rev_basic(self):
++        gv = BasicGraphVizLoader(('c',), {
++         'a': (NULL_REVISION, ),
++         'b': ('a', ),
++         'c': ('a', 'b'),
++        })
++        gv.load()
++        # c
++        # ├─╮
++        # │ b
++        # ├─╯
++        # a
++
++        state = loggraphviz.GraphVizFilterState(gv)
++
++        # just mainline showing
++        self.assertFilteredRevisions('ca', state)
++
++        # bla - we need a computed to call collapse_expand_rev
++        # expand 'c'
++        state.collapse_expand_rev(gv.compute_viz(state).filtered_revs[0])
++
++        # all should be showing
++        self.assertFilteredRevisions('cba', state)
++
++        # colapse 'c'
++        state.collapse_expand_rev(gv.compute_viz(state).filtered_revs[0])
++
++        # just mainline showing
++        self.assertFilteredRevisions('ca', state)
++
++    def get_expanded_by_graph_provider(self):
++        gv = BasicGraphVizLoader(('f',), {
++         'a': (NULL_REVISION, ),
++         'b': ('a', ),
++         'c': ('a', 'b'),
++         'd': ('a', 'c', ),
++         'e': ('b', ),
++         'f': ('d', 'e')
++        })
++        gv.load()
++        # f
++        # ├───╮
++        # │   e
++        # │   │
++        # d   │
++        # ├─╮ │
++        # │ c │
++        # │ │\│
++        # │ │ b
++        # ├─╯─╯
++        # a
++        return gv
++
++    def test_collapse_colapses_sub_expand(self):
++        gv = self.get_expanded_by_graph_provider()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        # just mainline showing
++        self.assertFilteredRevisions('fda', state)
++
++        # expand 'd'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[2])
++        # branchline c now showing
++        self.assertFilteredRevisions('fdca', state)
++
++        # expand 'c'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[3])
++        # all showing
++        self.assertFilteredRevisions('fedcba', state)
++
++        # colapse 'd'
++        state.collapse_expand_rev(gv.compute_viz(state).filtered_revs[2])
++        # cause c expanded branchline eb, and d expanded c, d colapses
++        # just mainline showing
++        self.assertFilteredRevisions('fda', state)
++
++    def test_collapse_dosent_colapses_prev_expand(self):
++        gv = self.get_expanded_by_graph_provider()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        # just mainline showing
++        self.assertFilteredRevisions('fda', state)
++
++        # expand 'f'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[0])
++        # branchline eb now showing
++        self.assertFilteredRevisions('fedba', state)
++
++        # expand 'd'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[2])
++        # all showing
++        self.assertFilteredRevisions('fedcba', state)
++
++        # colapse 'd'
++        state.collapse_expand_rev(gv.compute_viz(state).filtered_revs[2])
++        # cause branchline eb was expanded by f, and not d, collapsing d dose
++        # not collapse branchline eb, even though it expanded it
++        # branchline eb and mainline left showing
++        self.assertFilteredRevisions('fedba', state)
++
++    def test_collapse_deep_expanded_by(self):
++        # This use to error at one point
++        gv = BasicGraphVizLoader(('g',), {
++         'a': (NULL_REVISION, ),
++         'b': ('a', ),
++         'c': ('a', 'b'),
++         'd': ('a', 'c', ),
++         'e': ('b', ),
++         'f': ('d', 'e'),
++         'g': ('a', 'f'),
++        })
++        # g v-----1.3
++        # ├─╮
++        # │ f   v-1.1
++        # │ ├───╮
++        # │ │   e
++        # │ │   │
++        # │ d v-│-1.2
++        # │ ├─╮ │
++        # │ │ c │
++        # │ │ │\│
++        # │ │ │ b
++        # ├─╯─╯─╯
++        # a
++
++        gv.load()
++
++        state = loggraphviz.GraphVizFilterState(gv)
++        # just mainline showing
++        self.assertFilteredRevisions('ga', state)
++
++        # expand 'g'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[0])
++        # branchline fd now showing
++        self.assertFilteredRevisions('gfda', state)
++
++        # expand 'f'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[1])
++        # branchline eb now showing
++        self.assertFilteredRevisions('gfedba', state)
++
++        # expand 'd'
++        state.collapse_expand_rev(gv.compute_viz(state).revisions[3])
++        # branchline c now showing (all showing)
++        self.assertFilteredRevisions('gfedcba', state)
++
++        # colapse 'g'
++        state.collapse_expand_rev(gv.compute_viz(state).filtered_revs[0])
++        # back to just mainline showing
++        self.assertFilteredRevisions('ga', state)
++
++    def test_filter(self):
++        gv = BasicGraphVizLoader(('e',), {
++         'a': (NULL_REVISION, ),
++         'b': ('a', ),
++         'c': ('a', 'b'),
++         'd': ('c', ),
++         'e': ('d', ),
++        })
++        gv.load()
++        # e
++        # │
++        # d
++        # │
++        # c
++        # ├─╮
++        # │ b
++        # ├─╯
++        # a
++
++        state = loggraphviz.GraphVizFilterState(gv)
++
++        # expand 'c'
++        state.collapse_expand_rev(gv.compute_viz(state).filtered_revs[2])
++
++        # all should be showing
++        self.assertFilteredRevisions('edcba', state)
++
++        state.filters.append(BasicFilterer(('d', 'c', 'a')))
++        state.filter_changed()
++        # d and a not showing bucause of filter
++        # c shows even though it is filtered, because it merges a revision
++        # that is not filtered.
++        self.assertFilteredRevisions('ecb', state)
++
++
++
++class BasicGraphVizLoader(loggraphviz.GraphVizLoader):
++
++    def __init__(self, heads, graph_dict, no_graph=False):
++        self.heads = heads
++        self.graph_dict = graph_dict
++        bi = loggraphviz.BranchInfo(None, None, None)
++        loggraphviz.GraphVizLoader.__init__(self, [bi], bi, no_graph)
++
++    def load(self):
++        for head in self.heads:
++            self.append_head_info(head, self.branches[0], head)
++
++        self.process_graph_parents(self.heads, self.graph_dict.items())
++
++        self.compute_head_info()
++
++        if not self.no_graph:
++            self.compute_branch_lines()
++            self.compute_merge_info()
++
++
++class BasicFilterer(object):
++    def __init__(self, filtered_revids):
++        self.filtered_revids = filtered_revids
++
++    def get_revision_visible(self, rev):
++        return rev.revid not in self.filtered_revids
++
++def print_computed(computed):
++    print_lines([(c_rev.rev.revid,
++                 c_rev.col_index,
++                 c_rev.twisty_state,
++                 c_rev.lines,)
++                for c_rev in computed.filtered_revs])
++
++def print_lines(list):
++    print ''
++    print format_graph_lines(list)
++
++def format_graph_lines(list, use_unicode=True):
++    if not list:
++        return list.__repr__() + '\n'
++    s = StringIO()
++    item_repr = [item.__repr__() for item in list]
++    repr_width = max([len(repr) for repr in item_repr])
++    if use_unicode:
++        twisty_char = {None: u'○',
++                      True: u'⊖',
++                      False: u'⊕'}
++        ver_char = {True: u'│',
++                    False: u'┆'}
++
++        hor_char = {True: {u' ': u'─',
++                           u'│': u'┼',
++                           u'┆': u'┼'},
++                    False: {u' ': u'┄',
++                           u'│': u'┼',
++                           u'┆': u'┼'}}
++
++        tl_char = {u' ': u'╭',
++                   u'│': u'├',
++                   u'┆': u'├',
++                   u'─': u'┬',
++                   u'┄': u'┬',
++                   u'┴': u'┼',
++                   u'┤': u'┼',}
++
++        tr_char = {u' ': u'╮',
++                   u'│': u'┤',
++                   u'┆': u'┤',
++                   u'─': u'┬',
++                   u'┄': u'┬',
++                   u'┴': u'┼',
++                   u'├': u'┼',}
++
++        bl_char = {u' ': u'╰',
++                   u'│': u'├',
++                   u'┆': u'├',
++                   u'─': u'┴',
++                   u'┄': u'┴',
++                   u'┬': u'┼',
++                   u'┤': u'┼',}
++
++        br_char = {u' ': u'╯',
++                   u'│': u'┤',
++                   u'┆': u'┤',
++                   u'─': u'┴',
++                   u'┄': u'┴',
++                   u'┬': u'┼',
++                   u'├': u'┼',}
++    else:
++        twisty_char = {None: '*',
++                      True: '~',
++                      False: '+'}
++        ver_char = {True: '|',
++                    False: ':'}
++
++        hor_char = {True: {' ': '-',},
++                    False: {' ': '-'}}
++
++        tl_char = {}
++
++        tr_char = {}
++
++        bl_char = {}
++
++        br_char = {}
++
++    for row, (item, repr) in enumerate(zip(list, item_repr)):
++        if row == 0:
++            s.write('[')
++        else:
++            s.write(' ')
++        s.write(repr.ljust(repr_width))
++        if row == len(list)-1:
++            s.write('] # ')
++        else:
++            s.write(', # ')
++
++        if len(item) == 4:
++            revid, col_index, twisty_state, lines = item
++        if len(item) == 5:
++            revid, col_index, twisty_state, lines, labels = item
++
++        all_cols = [col_index]
++        all_cols += [start for start, end, color, direct in lines]
++        all_cols += [end for start, end, color, direct in lines]
++        num_cols = (max(all_cols) + 1) * 2
++        this_line = [' ' for i in range(num_cols)]
++        next_line = [' ' for i in range(num_cols)]
++
++        for start, end, color, direct in lines:
++            if start is None or end is None:
++                continue
++            start = int(round(start))
++            end = int(round(end))
++            if start == end:
++                this_line[start * 2] = ver_char[direct]
++                next_line[start * 2] = ver_char[direct]
++            else:
++                this_line[start * 2] = ver_char[direct]
++
++        def replace_char(line, i, char_dict):
++            old_char = line[i]
++            if old_char in char_dict:
++                line[i] = char_dict[old_char]
++
++        for start, end, color, direct in lines:
++            if start is None or end is None:
++                continue
++            start = int(round(start))
++            end = int(round(end))
++            if start < end:
++                for i in range(start * 2 + 1, end * 2):
++                    replace_char(next_line, i, hor_char[direct])
++                replace_char(next_line, start * 2, bl_char)
++                replace_char(next_line, end * 2, tr_char)
++            elif start > end:
++                for i in range(end * 2 + 1, start * 2):
++                    replace_char(next_line, i, hor_char[direct])
++                replace_char(next_line, start * 2, br_char)
++                replace_char(next_line, end * 2, tl_char)
++
++        this_line[int(col_index * 2)] = twisty_char[twisty_state]
++
++        s.write(''.join(this_line))
++        s.write('\n')
++
++        if not row == len(list)-1:
++            s.write('# '.rjust(repr_width + 5))
++            s.write(''.join(next_line))
++            s.write('\n')
++    return s.getvalue()
++
++
++class TestGroupOverlapping(TestCase):
++    def test_group_overlapping(self):
++        lines = [
++            (['a1'], 1, 3, 'a'),
++            (['a2'], 2, 5, 'a'),
++            (['a3'], 4, 6, 'a'),
++            (['a4'], 6, 8, 'a'),
++            (['b1'], 1, 3, 'b'),
++            (['b2'], 2, 5, 'b'),
++            (['n1'], 1, 8, None),
++            (['n2'], 1, 8, None),
++            ]
++        groups = loggraphviz.group_overlapping(lines)
++        self.assertEqual(
++            [(['a1', 'a2', 'a3'], 1, 6, 'a'),
++             (['a4'], 6, 8, 'a'),
++             (['b1', 'b2'], 1, 5, 'b'),
++             (['n1'], 1, 8, None),
++             (['n2'], 1, 8, None)],
++            groups)

Bazaar

Merge lp:~garyvdm/bzr/loggraphviz into lp:bzr

Commit message

Description of the change

Unmerged revisions

Preview Diff

Subscribers