Re: [RFH] revision limiting sometimes ignored

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 3, 2008, 07:40 UTC
Message-ID: <7vbq6yzdvr.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <20080203071833.GA16273@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

> We could topologically order the commits going into limit_list (it just
> works most of the time because the date ordering is _mostly_ right).
> This guarantees that we deal with 'four' before 'one'. But topo sorting
> is expensive.

I recall we did a rather clever optimization in merge-base. I am starting to suspect that we would need a similar trick there.

The issue is:

 * We have pushed "one" out already to "newlist", but we haven't
   given UNINTERESTING bit to it yet.

 * We are responsible to mark "one" UNINTERESTING, if it can be
   reached from a commit that is UNINTERESTING.  We expect
   further looping of the "while (list)" and
   mark_parents_uninteresting() in that loop will eventually
   smudge it.

 * We can obviously prove that we marked all UNINTERESTING
   commits that matters by traversing _all_ history (i.e. make
   sure mark_parents_uninteresting() recurses, and wait until
   "list" truly becomes empty), but we would want to somehow
   optimize it.  The everybody_uninteresting() check was
   introduced for that purpose, but that is not a right
   optimization if commit timestamps are skewed like this.

The right optimization is probably:

 * Wait until everybody on "list" is UNINTERESTING.  IOW, keep
   the "everybody_uninteresting()" check with break as is.

   At that point "newlist" will contain all the commits that we
   might be interested in (e.g. "one").  The issue is reduced
   from "mark _all_ commits that can be reached from known
   UNINTERESTING ones" to "make sure the commits on the newlist
   that are reachable from UNINTERESTING ones in the "list" are
   marked as UNINTERESTING (e.g. "one" should be checked for
   reachability from the remaining UNINTERESTING commits in
   "list", we do not have to check for anything else).

 * After the loop exits, traverse from all non UNINTERESTING
   commits on the "newlist" and all remaining commits on the
   "list" (by definition, the latter are UNINTERESTING) down to
   their common merge base, propagating UNINTERESTING bit down.

   Once we do that, we have proven that "one" is reachable from
   any of the UNINTERESTING commit.