From: Michael J Gruber <git@drmicha.warpmail.net>
Date: Wed, 04 Mar 2015 15:06:17 GMT
Subject: Re: git describe --contains doesn't work properly for a commit
Message-ID: <54F71F69.3080500@drmicha.warpmail.net>
In-Reply-To: <20150304105408.GA19693@peff.net>

Jeff King venit, vidit, dixit 04.03.2015 11:54:
> On Thu, Feb 26, 2015 at 03:23:14PM +0100, Michal Hocko wrote:
> 
>> The commit in the middle was ammended to have committer date in the
>> past.
>> $ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd
>> tag~1
>>
>> but
>> $ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3
>> fatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'
>>
>> I guess this is the same issue reported previously here:
>> http://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html
> 
> Yes, the "describe --contains" algorithm uses timestamps to cut off the
> traversal, so it can do the wrong thing if there's clock skew. It has a
> "slop" margin of one day, but skew larger than that can fool it.
> 
>> Can this be fixed somehow or it would lead to other kind of issues?
> 
> The options are basically:
> 
>   1. Stop cutting off the traversal based on timestamps. This will make
>      the common case of valid timestamps much slower, though, as it will
>      have to walk all the way to the roots.
> 
>   2. Use a different slop mechanism. For example, keep walking up to 5
>      commits past a commit suspected to be past the cutoff. This is
>      relatively easy to do (we do it for "--since" checks), and would
>      catch your case above. But of course it does not catch all cases of
>      skew.
> 
>   3. Introduce a more trust-worthy mechanism for ordering commits. The
>      timestamp here is really just a proxy for the oft-discussed
>      "generation number" of the commit within the graph. We've avoided
>      adding generation numbers because of the storage/complexity issues.

Hmmh.

Storage: one int (or maybe less) per commit doesn't sound too bad. We
can probably do without on bare repos by default.

Complexity: Was that due to replace refs? Other than that, it seemed to
be simple: max(parent generation numbers)+1.

... or can reachability bitmaps help???

Michael