Re: [RFH] revision limiting sometimes ignored

Junio C Hamano [off-list ref] writes:

As Linus earlier said, the question really is: for positive
commits in "newlist", have we not missed any its UNINTERESTING
descendants?

For a toy-scale graph, a parallel merge-base traversal like what
show-branch does may work, but for a real workload, newlist
would contain literally hundreds of commits, so using unaltered
"merge-base" algorithm is probably not an option either.

After exiting the while (list) we need to prove that each
positive commit in "newlist" cannot be reached by any of the
negative commit still in "list".

Even though "newlist" may have thousands of commits, we do not
have to inspect all of them.  In order to prove that we
traversed everything that matters, we will only need to look at
the ones whose ancestors are not in "newlist" (bottom commits)
and see if each of them can be reached from the negative ones.
If a non-bottom commit is reachable from one of the negative
ones, then the bottom commit that is ancestor of that non-bottom
commit surely is reachable as well.

We can make one pass to mark everything on "newlist" with one
bit from flags, and then another pass to mark the positive ones
whose parent has that bit set, so we would need two bits in
total while finding out the set of bottom commits (we can reuse
these two bits after we know what they are).

Once we find the set of bottom commits in "newlist", we would
need to prove that none of them can be reached from any of the
negative commits still in "list".  We can do this traversal
using two bits from flags, exactly like commit.c::merge_bases()

    for each bottom commit B {
	L = empty list
	B.flags |= PARENT2
	L.append(B)
	for each negative commit C in "list from limit_list()"
            C.flags |= PARENT1
            L.append(C)
	while (L) {
	    C = shift L;
	    flag = C.flags & (PARENT1|PARENT2);
            if (flag ==  (PARENT1|PARENT2))
 		continue; /* common */
	    for each parent P of commit C:
		pflag = P.flags & (PARENT1|PARENT2);
		if (pflag == flag)
                    continue;
		P.flags |= flags;
                L.append(P)
	}
        if (B.flags & PARENT1)
            we still need to traverse -- everybody_uninteresting()
	    in limit_list() main loop was not enough!
    }