[MERGE] Tree.get_matching_blocks

[Aaron Bentley]

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

Robert Collins wrote:
>> Tree.get_matching_blocks will be implemented on top of a cache for
>> comparison with the basis.
> 
> Does this imply a cache like svn does of all the basis texts ?

I don't think so.  I'm just talking about a cache of all the matching
blocks for files that differ from the basis.

> Is faster
> access to the historical data insufficient to get to where we want to ?

It is an improvement, but not sufficient.  It does not provide a way to
accelerate comparison of a text modified in the working tree with the
basis version of the text.  It does not provide a way to accelerate
comparison of a text modified in the working tree with a historical
version other than the basis tree.

>>   For historical trees, it will be derived from content deltas.
> 
> Does it require line based deltas?

It is not a strict requirement.  As long as whatever's stored can be
translated into line-based deltas, we should be fine.

> Whats the impact if historical files
> do not offer an exact matching diff immediately - will it fall back
> cleanly?

It will combine the historical comparisons it does have to produce the
historical comparison it needs.  (It will have to fall back if any
revisions in the build chain are not present, and therefore have no deltas).

> And do we have to use the same sequence matching operation for
> historical commits as for 'bzr diff'

It doesn't have to the the same.  It should be suitable for
human-readable diffs, though.

>> In addition to "diff" it can also speed up merge and commit.
> 
> Merge I can see, but I'm not sure about how it speeds up commit

Commit stores deltas in repositories.  We can use the cached comparisons
of working tree files (generated at diff or merge time) to avoid doing
sequence matching in order to generate the repository deltas.

> - we
> currently diff against all parents to generate our annotation cache.

At commit time, only things which we have a cached comparison for will
be accelerated.  Two things can produce cached comparisons: diff and merge.

diff will rarely cache comparisons against the righthand basis.
However, merge can also cache comparisons, and it can certainly cache
comparisons against the righthand basis.  Since the righthand parent is
produced by a merge, this means merge caching will cover a large portion
of righthand comparisons, also.

So after a merge, commit will be able to accelerate comparisons against
both the left and right parent texts.

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

iD8DBQFGoFD00F+nu1YWqI0RArw0AJ475iKUF+zy8sti6DUe5YuX1oxAUQCfXWH8
AEyr96136Hz/n4woNSUwc2Q=
=tVi3
-----END PGP SIGNATURE-----