[PATCH] hgweb: follow renames and copies in file log (issue1576)

[Martin Geisler]

Kevin Gessner <kevin at fogcreek.com> writes:

> On Wed, Apr 6, 2011 at 11:03 AM, Dirkjan Ochtman <dirkjan at ochtman.nl> wrote:
>> On Wed, Apr 6, 2011 at 16:34, Kevin Gessner <kevin at fogcreek.com> wrote:
>>> # HG changeset patch
>>> # User Kevin Gessner <kevin at fogcreek.com>
>>> # Date 1301949717 14400
>>> # Node ID 6df5de9f4dcbb71c4654a8d1c3181a96194d8579
>>> # Parent  086c9f203a53ee4b20a83d06c6e966ecc8a30cbf
>>> hgweb: follow renames and copies in file log (issue1576)
>>> --- a/mercurial/hgweb/webcommands.py
>>> +++ b/mercurial/hgweb/webcommands.py
>>> @@ -631,21 +631,34 @@
>>>     morevars = copy.copy(tmpl.defaults['sessionvars'])
>>>     morevars['revcount'] = revcount * 2
>>>
>>> -    count = fctx.filerev() + 1
>>> -    start = max(0, fctx.filerev() - revcount + 1) # first rev on this page
>>> +    def follow(fctx):
>>> +        l = []
>>> +        while fctx:
>>> +            l.insert(0, fctx)
>>> +            renamed = fctx.filectx(0).renamed()
>>> +            if renamed:
>>> +                fctx = web.repo.filectx(renamed[0], fileid=renamed[1])
>>> +            else:
>>> +                fctx = None
>>> +        return l
>>> +
>>> +    allfctx = follow(fctx)
>>
>> - This looks like it will repeatedly call list.insert(0, something),
>> which is potentially a big performance liability. Inserting at the
>> start of the list shifts all elements in the list to the right, so
>> you probably don't want to do it in this kind of loop.
>
> Is there a data structure more appropriate for this (e.g. does python
> have a linked list)? I'm walking the filelog in forward order, and
> need the output in the reverse. Would append() in a loop + reverse()
> be more efficient?

Yes, list.append is amortized O(1) so that is more efficient. Using a
double-ended queue gives you you O(1) access to both ends of the list:

  http://docs.python.org/library/collections.html#collections.deque

-- 
Martin Geisler

aragost Trifork
Professional Mercurial support
http://mercurial.aragost.com/kick-start/