Re: [Monotone-devel] [PATCH] mtn-bisect and toposort/log question

[William Uther]

On 11/08/2007, at 2:21 AM, Łukasz Krotowski wrote:

> Hi,
> I attached patch with first version of mtn-bisect script. It's  
> regression
> search tool modeled after git-bisect. It doesn't provide git's  
> automation
> and logging for now. And has some not tested fail paths, and some  
> not found
> bugs also. Nevertheless it was quite helpful in searching for first  
> revision
> with possible bug: <http://savannah.nongnu.org/bugs/?20711>.

Looks like a great tool.

> Also, I've got a question. With both mtn automate toposort and mtn log
> (monotone, branch net.venge.monotone) there is such output:
>
> 1) 11a06ec25f1d3382189b3d39cc0f9e6c7983186f 2007-06-14T21:28:32
> 2) 55434f89a7caebea111d02af424d7bdd35b357a1 2007-05-25T17:15:33
> 3) 2d18283fb2482e98ac5f9d29076804b9d8adbb13 2007-05-24T20:41:22
> 4) 09655aae0a7b9ab2a30f5a9ed36cc8719838d5a1 2007-06-14T12:22:34
> ...
>
> Revision (1) is merge of (2) and (4). I know it's topological order  
> but it's
> also somehow illogical. ;) Is there possibility to adjust toposort  
> algorithm
> to select such a order where merge ancestors are sorted by time cert?

I have also wanted such a sort order.  At the moment ikiwiki history  
looks quite strange when using my patch for similar reasons.  I don't  
think it is a one-line change though, in that you want to make sure  
you keep a topologically sorted order, just using times as a hint.

Having said that, for something like mtn-bisect, I would have thought  
that you actually want to take into account the structure of the  
graph.  Just doing divide-and-conquer on the topological sort may not  
be as efficient as you can get.  e.g.  If I have the following graph  
structure:

   A
  / \
 C   L
 |   |
 D   M
 |   |
 E   N
 |   |
 F   O
  \ /
   X

where A is the oldest rev and is good, and X is the newest rev and is  
bad.

If I wanted to divide the number of remaining revs that might have  
the fault in two, I want to test O or F next.  It will tell me which  
side of the graph has the problem.

Oo - and in fact, time ordering would be actively bad.  Suppose I end  
up with a time ordering of the above revisions of:

A C L D M E N F O X

Let's assume that the bug was introduced in rev C.  Let's also assume  
that I test rev M first (i.e. my first test is on the opposite branch  
with a time after the time of the bad revision).  In that case I'll  
assume that all the revs before M in my time-ordering are good, and  
this is a bad assumption.  Topologically sorting where you're keeping  
runs of revisions 'close' and ignoring time would be better, although  
I doubt that is guaranteed to work.

> It would make log output more readable. And when it comes to mtn- 
> bisect
> order as above causes false positives (revisions 1 and 4 are marked  
> bad and
> 2, 3 good, which make them local maximum): (1) can be found as  
> first bad
> revision.

As I just noted, I think time order would be worse for false  
positives.  You need to take the graph structure into account.

Cheers,

Will        :-}