Properties of trees referencing commit objects (mode 160000)?

Properties of trees referencing commit objects (mode 160000)?

[Josh Triplett]

I'm building some tools to track commit objects, and I'm thinking of
using submodule-style references to commit objects in tree objects (mode
160000) to do so.  I'm trying to figure out some of the properties of
that.

Can a commit object referenced that way live in the same repository,
rather than some external repository?

Will git treat such a reference as keeping the commit object (and
everything recursively referenced by it) live and reachable?  If that
commit object is only reachable by the tree, and not by following the
parents of any commit directly referenced from refs/*, will git discard
it as unreachable?

- Josh Triplett

Re: Properties of trees referencing commit objects (mode 160000)?

[Jeff King]

On Sat, Mar 19, 2016 at 03:13:48PM -0700, Josh Triplett wrote:

> I'm building some tools to track commit objects, and I'm thinking of
> using submodule-style references to commit objects in tree objects (mode
> 160000) to do so.  I'm trying to figure out some of the properties of
> that.
> 
> Can a commit object referenced that way live in the same repository,
> rather than some external repository?

Yes, it can be in the same repository, but...

> Will git treat such a reference as keeping the commit object (and
> everything recursively referenced by it) live and reachable?  If that
> commit object is only reachable by the tree, and not by following the
> parents of any commit directly referenced from refs/*, will git discard
> it as unreachable?

No, we do not follow "gitlinks" like this for reachability. Neither for
pruning, nor for object transfer via push/fetch. So you'd need to have a
separate reference to it (or history containing it).

-Peff

Re: Properties of trees referencing commit objects (mode 160000)?

[Josh Triplett]

On Sun, Mar 20, 2016 at 12:18:04AM -0400, Jeff King wrote:
> On Sat, Mar 19, 2016 at 03:13:48PM -0700, Josh Triplett wrote:
> 
> > I'm building some tools to track commit objects, and I'm thinking of
> > using submodule-style references to commit objects in tree objects (mode
> > 160000) to do so.  I'm trying to figure out some of the properties of
> > that.
> > 
> > Can a commit object referenced that way live in the same repository,
> > rather than some external repository?
> 
> Yes, it can be in the same repository, but...

Will git clone/checkout/etc handle it properly in that case, in the
absence of a .gitmodules file?  Or would it only work with custom tools?

> > Will git treat such a reference as keeping the commit object (and
> > everything recursively referenced by it) live and reachable?  If that
> > commit object is only reachable by the tree, and not by following the
> > parents of any commit directly referenced from refs/*, will git discard
> > it as unreachable?
> 
> No, we do not follow "gitlinks" like this for reachability. Neither for
> pruning, nor for object transfer via push/fetch. So you'd need to have a
> separate reference to it (or history containing it).

Argh.  If I have a pile of disconnected commits, is there anything git
*would* follow to see them, other than a pile of refs?

I suppose I could artificially generate a stack of merge commits with
those otherwise disconnect commits as parents, which would let me
reference them all from a single ref.  Still unsatisfying, though.

Also, thanks, "gitlink" was the term I was trying to think of.

(I'd also be tempted to ask whether a patch to teach git to follow
gitlinks for reachability and/or object transfer would be acceptable.)

Re: Properties of trees referencing commit objects (mode 160000)?

[Jeff King]

On Sun, Mar 20, 2016 at 11:45:24AM -0700, Josh Triplett wrote:

> Will git clone/checkout/etc handle it properly in that case, in the
> absence of a .gitmodules file?  Or would it only work with custom tools?

I think checkout just creates an empty tree for any gitlinks, and waits
for the submodule code to fill it in.  So you'd need a custom tool. It's
easy enough to test, though:

    git init repo &&
    cd repo &&
    echo content >file && git add file && git commit -m base &&
    printf '160000 commit %s\t%s' "$(git rev-parse HEAD)" linked >tree &&
    tree=$(git mktree <tree) &&
    commit=$(echo foo | git commit-tree $tree) &&
    git checkout $commit

> > No, we do not follow "gitlinks" like this for reachability. Neither for
> > pruning, nor for object transfer via push/fetch. So you'd need to have a
> > separate reference to it (or history containing it).
> 
> Argh.  If I have a pile of disconnected commits, is there anything git
> *would* follow to see them, other than a pile of refs?

I don't think so. We follow refs, tag "object" fields, and commit
"parent" fields to get to commits, but never tree entries.

And I don't think it works to just tweak the mode to 100644 for the
commit entry; the checkout code will complain that it was expecting a
blob and got a commit.

> I suppose I could artificially generate a stack of merge commits with
> those otherwise disconnect commits as parents, which would let me
> reference them all from a single ref.  Still unsatisfying, though.

Yes, though you can do it all in one single merge commit. The tree of
that merge commit wouldn't matter, it could literally just be a pointer
to all of the parents (we used to have some limits on the number of
parents, but I don't think we do anymore?).

If you just threw away that stacked merge and made a new one any time it
was updated, I think it wouldn't end up very efficient for fetching. The
client would say "I have giant-merge-commit X", and the server would say
"well, I need to send you giant-merge-commit Y", but if it does not any
longer have X, it cannot realize that Y includes 99% of what is in X.

So I guess you'd want a history chain of those merges. I'm not quite
sure what your application is, so I don't know if that would be a pain
or not.

> (I'd also be tempted to ask whether a patch to teach git to follow
> gitlinks for reachability and/or object transfer would be acceptable.)

As always, I reserve all judgement on patches until I see them. :)

But I tend to think it would end up rather complex. Off the top of my
head, these are the three gotchas I can think of:

  1. The reachability rules must be agreed upon between both sides of
     the transfer. So you would need a protocol extension for "please
     consider gitlinks reachable" so that the sender knows to include
     them, and that when the client advertises commit X that can reach
     Y via gitlink, it can assume that the client does not need Y.

  2. There may be some issues with efficiently finding shared history
     during a transfer.  That process usually just looks at the commits,
     and then we hand the set of have/want commits to the pack
     generation code to figure out the full set of required objects (and
     in particular, we do not comb through all of the "have" commits for
     objects that might have become re-referenced; it's too expensive
     for too little gain).

     But with the flag from (1), we'd have commits buried inside trees.
     The packing code would figure out which objects to send, but I
     suspect you'd end up with some inefficiencies where an internal
     gitlink bumped from commit X to Y, and we _could_ know that the
     client already has X, but digging it up doesn't happen with the
     current code.

     I didn't think it through too hard, though, so perhaps it would all
     just work.

  3. The reachability is usually an invariant in the repository, but
     presumably this would be enabled through a config variable (it
     _can't_ be on all the time, because then true external submodules
     wouldn't work, and it can't just be "eh, reachable if you got it",
     because then transfers cannot assume the other side has it and
     would resend every time).

     So flipping that switch in an existing repository with gitlinks
     would probably put it in a broken state until it fetches all of the
     gitlinks.

-Peff

Re: Properties of trees referencing commit objects (mode 160000)?

[Junio C Hamano]

Josh Triplett <josh@joshtriplett.org> writes:

> On Sun, Mar 20, 2016 at 12:18:04AM -0400, Jeff King wrote:
>> On Sat, Mar 19, 2016 at 03:13:48PM -0700, Josh Triplett wrote:
>> 
>> > I'm building some tools to track commit objects, and I'm thinking of
>> > using submodule-style references to commit objects in tree objects (mode
>> > 160000) to do so.  I'm trying to figure out some of the properties of
>> > that.
>> > 
>> > Can a commit object referenced that way live in the same repository,
>> > rather than some external repository?
>> 
>> Yes, it can be in the same repository, but...
>
> Will git clone/checkout/etc handle it properly in that case, in the
> absence of a .gitmodules file?  Or would it only work with custom tools?

That depends on the definition of "proper".  The default "proper"
way for the core Git for submodules/gitlinks is to create an empty
directory.  If you want to populate a working tree for that, you'd
need "git submodule" support, but because you are writing "some
tools" on your own, there probably is a reason why you do not want
to use "git submodule", so I am guessing that your definition of
"proper" does not match either core Git or "git submodule" considers
"proper"?  In which case you would need to implement your own
semantics (you may not even want to have an empty directory there,
for example).


>> No, we do not follow "gitlinks" like this for reachability. Neither for
>> pruning, nor for object transfer via push/fetch. So you'd need to have a
>> separate reference to it (or history containing it).
>
> Argh.  If I have a pile of disconnected commits, is there anything git
> *would* follow to see them, other than a pile of refs?

No.

Re: Properties of trees referencing commit objects (mode 160000)?

[Josh Triplett]

On Sun, Mar 20, 2016 at 03:30:27PM -0700, Junio C Hamano wrote:
> Josh Triplett <josh@joshtriplett.org> writes:
> 
> > On Sun, Mar 20, 2016 at 12:18:04AM -0400, Jeff King wrote:
> >> On Sat, Mar 19, 2016 at 03:13:48PM -0700, Josh Triplett wrote:
> >> 
> >> > I'm building some tools to track commit objects, and I'm thinking of
> >> > using submodule-style references to commit objects in tree objects (mode
> >> > 160000) to do so.  I'm trying to figure out some of the properties of
> >> > that.
> >> > 
> >> > Can a commit object referenced that way live in the same repository,
> >> > rather than some external repository?
> >> 
> >> Yes, it can be in the same repository, but...
> >
> > Will git clone/checkout/etc handle it properly in that case, in the
> > absence of a .gitmodules file?  Or would it only work with custom tools?
> 
> That depends on the definition of "proper".  The default "proper"
> way for the core Git for submodules/gitlinks is to create an empty
> directory.  If you want to populate a working tree for that, you'd
> need "git submodule" support, but because you are writing "some
> tools" on your own, there probably is a reason why you do not want
> to use "git submodule", so I am guessing that your definition of
> "proper" does not match either core Git or "git submodule" considers
> "proper"?  In which case you would need to implement your own
> semantics (you may not even want to have an empty directory there,
> for example).

I can live with "creates an empty directory and doesn't choke or
complain".  I'd kinda hoped that git might notice it already has the
commit, and do something like checking out the files of that commit into
the working directory, but it isn't critical.

- Josh Triplett

Re: Properties of trees referencing commit objects (mode 160000)?

[Josh Triplett]

On Sun, Mar 20, 2016 at 04:07:25PM -0400, Jeff King wrote:
> On Sun, Mar 20, 2016 at 11:45:24AM -0700, Josh Triplett wrote:
> > > No, we do not follow "gitlinks" like this for reachability. Neither for
> > > pruning, nor for object transfer via push/fetch. So you'd need to have a
> > > separate reference to it (or history containing it).
> > 
> > Argh.  If I have a pile of disconnected commits, is there anything git
> > *would* follow to see them, other than a pile of refs?
> 
> I don't think so. We follow refs, tag "object" fields, and commit
> "parent" fields to get to commits, but never tree entries.

That does make sense, given your point (2) below about efficiency.

> And I don't think it works to just tweak the mode to 100644 for the
> commit entry; the checkout code will complain that it was expecting a
> blob and got a commit.

That much I assumed. :)

> > I suppose I could artificially generate a stack of merge commits with
> > those otherwise disconnect commits as parents, which would let me
> > reference them all from a single ref.  Still unsatisfying, though.
> 
> Yes, though you can do it all in one single merge commit. The tree of
> that merge commit wouldn't matter, it could literally just be a pointer
> to all of the parents (we used to have some limits on the number of
> parents, but I don't think we do anymore?).

I didn't want to assume that all the software assuming upper bounds on
octopus merges had disappeared.  And more importantly...

> If you just threw away that stacked merge and made a new one any time it
> was updated, I think it wouldn't end up very efficient for fetching. The
> client would say "I have giant-merge-commit X", and the server would say
> "well, I need to send you giant-merge-commit Y", but if it does not any
> longer have X, it cannot realize that Y includes 99% of what is in X.

...that.  And the linearly growing cost of recreating and working with
the merge commit as the number of parent commits grows.

> So I guess you'd want a history chain of those merges. I'm not quite
> sure what your application is, so I don't know if that would be a pain
> or not.

As it turns out, that fits fairly naturally.

I want to track the evolution of a patch series or other commit history,
through non-fast-forwarding actions like rebase, rebase -i, or commit
--amend.  Similar in spirit to reflog, but with intentional commits and
commit messages, and most importantly with the ability to share and
collaborate on it.  For each version of the patch series, I plan to
track the commit at the end of the series, and optionally the commit at
the base of the patch series (to simplify tracking of rebasing); I'll
use the tree object associated with the commit to track the cover
letter, and perhaps meta-changelog entries associated with v2/v3/vN of
the series.

Patch series almost always need to evolve through non-fast-forwarding
history.  And I've seen that done in two ways: either pull the patch
series out of git, put it in quilt or similar, and track the quilt
series with git; or pull the versioning of the patch series out of git
and track it with branch names like feature-v2, feature-2016-03-20,
feature-rebased, and feature-rebased-4.4-fixed-foo-fixed-bar.  That last
one closely matches a real-world example I've recently seen.  And that
starts to look a lot like the naming of files and documents in
organizations that haven't yet discovered the wonders of version
control.

I'd like to have the best of both worlds: handle the patch series in
git, *and* handle the versioning of the patch series in git.

> > (I'd also be tempted to ask whether a patch to teach git to follow
> > gitlinks for reachability and/or object transfer would be acceptable.)
> 
> As always, I reserve all judgement on patches until I see them. :)

Of course.  Obviously it's not possible to accept a patch that doesn't
exist yet, but it's possible to reject a patch that doesn't exist yet
based solely on description, saving the trouble of writing it. :)

> But I tend to think it would end up rather complex. Off the top of my
> head, these are the three gotchas I can think of:
> 
>   1. The reachability rules must be agreed upon between both sides of
>      the transfer. So you would need a protocol extension for "please
>      consider gitlinks reachable" so that the sender knows to include
>      them, and that when the client advertises commit X that can reach
>      Y via gitlink, it can assume that the client does not need Y.
> 
>   2. There may be some issues with efficiently finding shared history
>      during a transfer.  That process usually just looks at the commits,
>      and then we hand the set of have/want commits to the pack
>      generation code to figure out the full set of required objects (and
>      in particular, we do not comb through all of the "have" commits for
>      objects that might have become re-referenced; it's too expensive
>      for too little gain).
> 
>      But with the flag from (1), we'd have commits buried inside trees.
>      The packing code would figure out which objects to send, but I
>      suspect you'd end up with some inefficiencies where an internal
>      gitlink bumped from commit X to Y, and we _could_ know that the
>      client already has X, but digging it up doesn't happen with the
>      current code.
> 
>      I didn't think it through too hard, though, so perhaps it would all
>      just work.
> 
>   3. The reachability is usually an invariant in the repository, but
>      presumably this would be enabled through a config variable (it
>      _can't_ be on all the time, because then true external submodules
>      wouldn't work, and it can't just be "eh, reachable if you got it",
>      because then transfers cannot assume the other side has it and
>      would resend every time).
> 
>      So flipping that switch in an existing repository with gitlinks
>      would probably put it in a broken state until it fetches all of the
>      gitlinks.

This point in particular makes me completely disinclined to go down this
road.  It could never be mandatory, and having it optional seems
error-prone.

Thanks for the feedback and suggestions.

- Josh Triplett

Re: Properties of trees referencing commit objects (mode 160000)?

[Jeff King]

On Sun, Mar 20, 2016 at 04:22:02PM -0700, Josh Triplett wrote:

> I want to track the evolution of a patch series or other commit history,
> through non-fast-forwarding actions like rebase, rebase -i, or commit
> --amend.  Similar in spirit to reflog, but with intentional commits and
> commit messages, and most importantly with the ability to share and
> collaborate on it.  For each version of the patch series, I plan to
> track the commit at the end of the series, and optionally the commit at
> the base of the patch series (to simplify tracking of rebasing); I'll
> use the tree object associated with the commit to track the cover
> letter, and perhaps meta-changelog entries associated with v2/v3/vN of
> the series.
> 
> Patch series almost always need to evolve through non-fast-forwarding
> history.  And I've seen that done in two ways: either pull the patch
> series out of git, put it in quilt or similar, and track the quilt
> series with git; or pull the versioning of the patch series out of git
> and track it with branch names like feature-v2, feature-2016-03-20,
> feature-rebased, and feature-rebased-4.4-fixed-foo-fixed-bar.  That last
> one closely matches a real-world example I've recently seen.  And that
> starts to look a lot like the naming of files and documents in
> organizations that haven't yet discovered the wonders of version
> control.
> 
> I'd like to have the best of both worlds: handle the patch series in
> git, *and* handle the versioning of the patch series in git.

It seems like you could represent this in git by storing a merge commit
for each revision of the patch series, with one parent as the current
real tip of the series, and the other as the merge-commit for the
previous revision of the series. The tree would be the same as current
tip commit's tree. You could store metadata about the series in the
merge commits (presumably including some marker to say "I'm a special
series-revision commit, not a regular merge").

That's roughly the same as having "feature-v1", "feature-v2", etc, in a
tree, except that you have to walk down the parent pointers to discover
each entry, rather than walking the tree.

The resulting history would be viewable with naive "git log", but you
would probably want to use "--first-parent" to see just the revisions,
or some to-be-invented option to see just the most recent commits (e.g.,
something like: if the commit subject is "magic-token: my-series", then
skip this commit, show the second parent, and then walk down the first
parent chain, skipping commits until we hit a commit that doesn't have
"magic-token: my-series" in it).

And it would just work for transferring revisions. You'd probably have
one ref per patch series (pointing to the marker commit of the most
recent version), and the "real" clean history of the project would never
include any of the revision markers at all (though it could if you
really wanted to).

But I will be the first to admit that I haven't thought too hard on
this. It may even be that I just unconsciously regurgitated somebody
else's storage scheme. Once upon a time I was interesting in "topgit",
"guilt", and other tools, but I haven't looked at them in years.

So it may well be that somebody tried something like this, and already
discovered its downsides. :)

-Peff

Re: Properties of trees referencing commit objects (mode 160000)?

[Josh Triplett]

On Mon, Mar 21, 2016 at 01:57:13AM -0400, Jeff King wrote:
> On Sun, Mar 20, 2016 at 04:22:02PM -0700, Josh Triplett wrote:
> 
> > I want to track the evolution of a patch series or other commit history,
> > through non-fast-forwarding actions like rebase, rebase -i, or commit
> > --amend.  Similar in spirit to reflog, but with intentional commits and
> > commit messages, and most importantly with the ability to share and
> > collaborate on it.  For each version of the patch series, I plan to
> > track the commit at the end of the series, and optionally the commit at
> > the base of the patch series (to simplify tracking of rebasing); I'll
> > use the tree object associated with the commit to track the cover
> > letter, and perhaps meta-changelog entries associated with v2/v3/vN of
> > the series.
> > 
> > Patch series almost always need to evolve through non-fast-forwarding
> > history.  And I've seen that done in two ways: either pull the patch
> > series out of git, put it in quilt or similar, and track the quilt
> > series with git; or pull the versioning of the patch series out of git
> > and track it with branch names like feature-v2, feature-2016-03-20,
> > feature-rebased, and feature-rebased-4.4-fixed-foo-fixed-bar.  That last
> > one closely matches a real-world example I've recently seen.  And that
> > starts to look a lot like the naming of files and documents in
> > organizations that haven't yet discovered the wonders of version
> > control.
> > 
> > I'd like to have the best of both worlds: handle the patch series in
> > git, *and* handle the versioning of the patch series in git.
> 
> It seems like you could represent this in git by storing a merge commit
> for each revision of the patch series, with one parent as the current
> real tip of the series, and the other as the merge-commit for the
> previous revision of the series. The tree would be the same as current
> tip commit's tree. You could store metadata about the series in the
> merge commits (presumably including some marker to say "I'm a special
> series-revision commit, not a regular merge").

That's exactly what I'm planning to do now, ever since your initial
response said submodules wouldn't work.

> That's roughly the same as having "feature-v1", "feature-v2", etc, in a
> tree, except that you have to walk down the parent pointers to discover
> each entry, rather than walking the tree.
> 
> The resulting history would be viewable with naive "git log", but you
> would probably want to use "--first-parent" to see just the revisions,
> or some to-be-invented option to see just the most recent commits (e.g.,
> something like: if the commit subject is "magic-token: my-series", then
> skip this commit, show the second parent, and then walk down the first
> parent chain, skipping commits until we hit a commit that doesn't have
> "magic-token: my-series" in it).

Rather than relying on the numeric index of the commit parents for
semantic value, I planned to use the tree object.  I can still use
gitlinks for named references to commits from within the series, as long
as the commits linked from those trees have references via parents to
keep them alive.  For instance, /series within the commit can refer to
the commit object at the top of the series, /base (if present) can refer
to the base of the series (e.g. v4.4), and /cover (a blob) can contain
the cover letter.  Then "git series format" automatically knows the base
to start from, and "git series log" or "git series diff" will know the
difference between "reordered patches" and "rebased on a new base".

The working copy and .git/HEAD will point to the last commit in the
current version of the patch series, so that tools like "git rebase -i"
and similar can Just Work; "git series" will manage the separate ref
independently.

I'll need to provide a variety of additional tools here for showing what
has changed in a patch series; I'd eventually like to support a sensible
"git series diff" that can show things like "rebased on this base,
reordered three patches, dropped one, edited another, and changed the
cover letter".

> And it would just work for transferring revisions. You'd probably have
> one ref per patch series (pointing to the marker commit of the most
> recent version), and the "real" clean history of the project would never
> include any of the revision markers at all (though it could if you
> really wanted to).

Exactly the plan.  And you won't ever actually check out those refs into
your working copy; you'll check out the patch series commits they
reference instead.

> But I will be the first to admit that I haven't thought too hard on
> this. It may even be that I just unconsciously regurgitated somebody
> else's storage scheme. Once upon a time I was interesting in "topgit",
> "guilt", and other tools, but I haven't looked at them in years.
> 
> So it may well be that somebody tried something like this, and already
> discovered its downsides. :)

One major downside is that creating such a tool doesn't automatically
make things like a three-way merge of patch series easy.  It makes
recognizing the situation *possible* (unlike before when you couldn't
easily exchange records of non-fast-forwarding history with others), but
if your remote and you have both changed the patch series independently,
merging the two will still prove challenging.

One step at a time, though: first I want to make it possible to track
as a first-class concept, and then we can make better tooling on top
of that.

- Josh Triplett