Re: [RFH] revision limiting sometimes ignored

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 6, 2008, 06:05 UTC
Message-ID: <7vhcgm4o1p.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <7v7ihi7syj.fsf@gitster.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

Show 8 quoted lines

> 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!
    }