children, n^2 and solutions?

[Jason Harris]

On Jul 26, 2010, at 8:34 PM, Matt Mackall wrote:

> On Mon, 2010-07-26 at 18:58 +0200, Jason Harris wrote:
>> Fortunately / unfortunately MacHg works incrementally. That means if I
>> do hg log -r 200100:200200 it will give me the results about an order
>> of magnitude faster than hg debugdag. So if I were to use it I would
>> have to do the log command (to get the information to display to the
>> users) and then the debugdag command as well to get the structure.
>> Additionally the Tree can change at many hg instructions. Eg pull,
>> merge, strip, edit, collapse, etc can cause the tree to change, so
>> really a full update needs to be done on many commands...
> 
> Call debugdag -once- the first time you visit a repo, cache the graph on
> -your- side, and update it incrementally when the repo is changed.

Well thats just it you see. For example say the user does an histedit, or indeed opens up the terminal and calls the command line outside of MacHg (which I detect things have changed through FSEvents), or does many other commands. Basically you have to start again. You can't do it incrementally since you have no idea which revisions changed, which were added, and which were removed.... Thus you can't incrementally do it easily.

At one stage I did have a command at once stage which gave the changeset hash key of a series of revisions going back wards. Ie it gave relative to the tip the changeset corresponding to the revision of the tip minus 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 so this way with only 16 changesets requested I got a reasonable idea of where the graph would diverge from the old graph... This seemed to execute reasonably fast and from there I could figure out the approximate place the tree diverged and then start zeroing in on where it changed and then try and incrementally update from there, but this is all fairly non-trivial. In the end I abandoned this approach since it was problematic.

In addition now if I determine that the graph has changed how (other than a debugdag command) do I know what has changed?  Thus I would have to execute a debugdag command and then we have lost incrementally. Of course there are certain measures I could take and already this is more complicated than just making sure I look more than 100 children into the future and then back patch the extended links...

Anyways as I said my humble request would be to be able to use children in log in O(1) or O(n) which would be immensely useful to me, is a clean interface to Mercurial and is very "simple". If somehow someone finds it in their harts to put this on their schedules I would be extremely grateful! Thank you!

Cheers,
  Jas