Re: jk/tag-contains (Re: What's cooking in git.git (Jul 2010, #05; Wed, 28))

From: Jeff King <peff@peff.net>
Date: Aug 5, 2010, 17:56 UTC
Message-ID: <20100805175640.GB15760@sigill>
In-Reply-To: <7vocdlpsmw.fsf@alter.siamese.dyndns.org>

On Sun, Aug 01, 2010 at 09:04:23PM -0700, Junio C Hamano wrote:

> Sorry, but I am right in the middle of phisically moving, so my weekend
> and evening git time has been nil recently.

Didn't you just do that? ;P

Show 8 quoted lines

> >> Additional things to do (this is mostly a note to myself):
> >> 
> >>  - refuse to commit with a timestamp long before any parent
> >
> > Agreed.
> 
> You need to be careful here, though.  What if you pulled from somebody
> whose clock is set grossly in the future?

Reading the rest of this thread and thinking about it more, I think warning is the best thing we can do. Because only the user is in a position to know whether it is their clock or the previous commit that is in error. And if it is the previous commit, then only the user knows what the next logical step is: redo the commit, complain to somebody else, or just ignore and continue.

Show 7 quoted lines

> I wonder if we can make fsck to notice a commit with a wrong timestamp
> (i.e. older than some of its parents) and make a note of it (hopefully
> they are miniscule minority)---then during the revision traversal when we
> hit such a commit, we perhaps ignore its timestamp (pretending as if its
> timestamp is one of its children or parent---I haven't thought about the
> details, but the note fsck leaves can record what adjusted timestamp
> should be used) to fix the issue?

That's basically a finer-grained version of what I implemented. Mine finds the _worst_ skew for the whole graph, and never lets you optimize a traversal cutoff more than that skew. So it is nicely bounded space-wise, as it is always a single integer, but you waste effort on the entire traversal because a couple of commits are skewed. Yours optimizes perfectly, but needs O(skewed commits) storage. Which is probably a better tradeoff when the number of skewed commits is tiny (which is what we expect).

I think your technique would work, but with one note. You probably want to pull the timestamp from the parent (pulling from the child makes no sense to me, as there can be an infinite number of children), but you need to process the parent first and pull from its _corrected_ timestamp. Because at least in the linux-2.6 case, there is a run of skewed commits. So if you have something like:

  A -- B -- C -- D

A, timestamp = 1000 B, timestamp = 900 C, timestamp = 950 D, timestamp = 1100

where obviously the timestamps are shortened to be readable, but are meant to be seconds-since-epoch. You'd probably want to end up with:

A, timestamp = 1000 B, timestamp = 1001 C, timestamp = 1002 D, timestamp = 1100

which means recursing all the way to the root, and fixing timestamps as you back out.

This seems like just a straight sha1->int mapping, which presumably one could do using "git notes". Though I worry it could slow down traversal for all of the lookup misses for non-skewed commits.

-Peff