Re: git doesn't finds the parent of a commit

["Stephen R. van den Berg" <srb@cuci.nl>]

Junio C Hamano wrote:
>"Stephen R. van den Berg" <srb@cuci.nl> writes:
>> I've had similar symptoms when I had circular references in the
>> repository.  They're not reported by any of the existing checks, I've
>> submitted a patch (resent it just now) which causes git to check for
>> (and report) circular references when using --topo-order on e.g.
>> git-rev-list.

>Assuming that we never have SHA-1 hash collisions, the graft mechansim is
>practically the only way to get yourself into the circular reference
>situation.

True, I think.

>Perhaps we should check this circularity when we install grafts instead of
>special casing the topo-order codepath?  How expensive would that
>alternative approach be?

Not practical in its current form.
Checking for circular references is O(n) in CPU and memory use relative
to the number of commits in the entire repository.

Consider:
- The proposed check in the topo-order path is very low-cost, it costs a
  single decrement/increment per commit (and will detect other circular
  references not caused by the grafts mechanism, if they ever should occur).
- If it is being done during the grafts install, then there should be a
  flag-file (at least), which indicates when the grafts file has changed
  since the last check.
- It could/should be added to git-fsck.
-- 
Sincerely,                                                          srb@cuci.nl
           Stephen R. van den Berg.