Introduce generator for lefthand branch history

[Martin von Gagern]

Aaron Bentley wrote:
> Martin von Gagern wrote:
>> The closest thing to a linear history which bzr provides is the
>> lefthand history. It is currently accessible by the
>> bzrlib.branch.Branch._lefthand_history method, which generates a list,
>> starting with the oldest real revision and ending with the argument
>> revision.
> 
>> I propose that you make that function public and official.
> 
> We already have a public, official method for getting the lefthand
> revision history of a branch: Branch.revision_history.

That one doesn't take arguments but always generates the history from
tip. So certainly useful, but not what I requested here.

>> Therefore you
>> could turn the function into a generator, yielding revisions of lefthand
>> ancestors starting at the argument and ending at the initial commit.
> 
> We have this already, in the form of
> Repository.iter_reverse_revision_history.

That looks like what I had in mind. Thanks a lot!

Now that I think of it, it makes sense to find such a thing in history.
But I started by looking at how Branch.revision_history is implemented
internally, and that works by using Branch._lefthand_history, which does
all the work by itself, without delegating to
Repository.iter_reverse_revision_history. You could consider changing
this to avoid code duplication, but that's an internal affair for you.

> A given revision may have many descendants, and they are unordered--
> there's no such thing as a left-hand descendant.  You need to specify
> how you would choose which descendants to follow before we can discuss
> this sensibly.

I know this needs proper specification. I have something in mind, but I
guess it's easiest explained by implementing it, therefore I'll not
discuss this further until then.

> There will probably be serious performance consequences, because bzr is
> not built to walk forwards in a performant way, and there are no indices
> of parent -> child relationships.

I fear so. On the other hand, there are quite a lot of parts in trac-bzr
which call Repository.get_ancestry, so often the whole ancestry gets
processed. I assume the cost for the generation of dotted revision
numbers is on a similar scale. Therefore it should be possible to
achieve simple calculations on the complete parent map in a comparable
timeframe. Maybe using cython as you do. Will see...

Greetings,
 Martin


> 
> Aaron

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20091127/1abc51e0/attachment-0001.pgp