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

[Jeff King <peff@peff.net>]

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

> >> 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.

> 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