Re: A generalization of git notes from blobs to trees - git metadata?

Johan Herland [off-list ref] writes:

Furthermore, although we currently assume that all note objects are blobs, 
someone (who?) has already suggested (as mentioned in the notes TODO list) 
that a note object could also be a _tree_ object that can be unpacked/read 
to reveal further "sub-notes".

I would advice you not to go there.  How would you even _merge_ such a
thing with other notes attached to the same object?  What determines the
path in that tree object?

Clueless ones can freely make misguided suggestions without thinking
things through and make things unnecessarily complex without real gain.
You do not have to listen to every one of them.

On Sat, Feb 06, 2010 at 06:21:37PM -0800, Junio C Hamano wrote:

Johan Herland [off-list ref] writes:

quoted

Furthermore, although we currently assume that all note objects are blobs, 
someone (who?) has already suggested (as mentioned in the notes TODO list) 
that a note object could also be a _tree_ object that can be unpacked/read 
to reveal further "sub-notes".

I would advice you not to go there.  How would you even _merge_ such a
thing with other notes attached to the same object?  What determines the
path in that tree object?

Clueless ones can freely make misguided suggestions without thinking
things through and make things unnecessarily complex without real gain.
You do not have to listen to every one of them.

I think I may have been the one to suggest trees or notes at one point.
But let me clarify that this is not exactly what the OP is proposing in
this thread.

My suggestion was that some use cases may have many key/value pairs of
notes for a single sha1. We basically have two options:

  1. store each in a separate notes ref, with each sha1 mapping to
     a blob. The note "name" is the name of the ref.

  2. store notes in a single notes ref, with each sha1 mapping to a
     tree with named sub-notes. The note "name" is the combination of
     ref-name and tree entry name.

The advantage of (1) is that notes are not bound tightly to each other.
I can distribute the notes tree for one "name" independent of the
others.  The advantage of (2) is that it is faster and smaller. In (1),
each note has a separate index, and we must traverse each note index
separately.

In practice, I would expect to use (1) for logically separate datasets.
For example, automatic bug-tracking notes would go in a different ref
from human annotations. But I would expect to use (2) if I had, say, 5
different pieces of bug tracking information and I wanted an easy way to
refer to them individually.

And a specialized merge for that is straightforward. In the simplest
case, you simply say "notes of this ref are tree-type, or they are
blob-type" and then you have no merge problems. But if you want to get
fancy, you can say that a conflict between "sha1/blob" and
"sha1/tree/key" should automatically "promote" the first one into
"sha1/tree/default" or some other canonical name.

Note that all of this is my pie-in-the-sky "here is what I was thinking
of when I looked at notes a long time ago". I don't care strongly if it
gets implemented or not at this point; I just wanted to add some context
to what Johan had in his notes todo list (or maybe I am wrong, and what
is in his todo list was based on something totally different said by
somebody else, and I have just confused the issue more. :) ).

With respect to the idea of storing an arbitrary tree, I agree it is
probably too complex with respect to merging. In addition, it makes
things like "git log --format=%N" confusing. I think you would do better
to simply store a tree sha1 inside the note blob, and callers who were
interested in the tree contents could then dereference it and examine as
they saw fit.  The only caveat is that you need some way of telling git
that the referenced trees are reachable and not to be pruned.

-Peff

On Sun, Feb 7, 2010 at 4:02 PM, Jeff King [off-list ref] wrote:

On Sat, Feb 06, 2010 at 06:21:37PM -0800, Junio C Hamano wrote:

quoted

Johan Herland [off-list ref] writes:

quoted

Furthermore, although we currently assume that all note objects are blobs,
someone (who?) has already suggested (as mentioned in the notes TODO list)
that a note object could also be a _tree_ object that can be unpacked/read
to reveal further "sub-notes".

I would advice you not to go there.  How would you even _merge_ such a
thing with other notes attached to the same object?  What determines the
path in that tree object?

Clueless ones can freely make misguided suggestions without thinking
things through and make things unnecessarily complex without real gain.
You do not have to listen to every one of them.

I think I may have been the one to suggest trees or notes at one point.
But let me clarify that this is not exactly what the OP is proposing in
this thread.

My suggestion was that some use cases may have many key/value pairs of
notes for a single sha1. We basically have two options:

 1. store each in a separate notes ref, with each sha1 mapping to
    a blob. The note "name" is the name of the ref.

 2. store notes in a single notes ref, with each sha1 mapping to a
    tree with named sub-notes. The note "name" is the combination of
    ref-name and tree entry name.

So, of course, options (1) and (2) need not be exclusive. Use Option
(1) for different metadata sets and option (2) to partition individual
datasets.

With respect to the idea of storing an arbitrary tree, I agree it is
probably too complex with respect to merging. In addition, it makes
things like "git log --format=%N" confusing. I think you would do better
to simply store a tree sha1 inside the note blob, and callers who were
interested in the tree contents could then dereference it and examine as
they saw fit.  The only caveat is that you need some way of telling git
that the referenced trees are reachable and not to be pruned.

As I see it, the existing use of notes is a special instance of a more
general metadata capability in which the metadata is constrained to be
a single blob. If notes continued to be constrained in this way, there
is no reason to change anything with respect to its current userspace
behaviour. That said, most of the plumbing which enabled notes could
be generalized to enable the arbitrary tree case [ which admittedly, I
have yet to sell successfully !]

In one sense, there is a sense in the merge issue doesn't exist. When
the maintainer publishes a tag no-one expects to have to deal with
downstream conflicting definitions of the tag. Likewise, if the
maintainer were to publish the /man and /html metadata trees (per my
previous example) for a release tag, anyone who received
/refs/metadata/doc would expect to receive the metadata trees as
published by the maintainer. Anyone who didn't wouldn't have to pull
/refs/metadata/doc.

I can see there are use cases where multiple parties might want to
contribute metadata and I do not currently have a good solution to
that problem, but that is not to say there isn't one - surely it is
just a question of applying a little intellect creatively?

jon.

Jon Seymour [off-list ref] writes:

[cut]

As I see it, the existing use of notes is a special instance of a more
general metadata capability in which the metadata is constrained to be
a single blob. If notes continued to be constrained in this way, there
is no reason to change anything with respect to its current userspace
behaviour. That said, most of the plumbing which enabled notes could
be generalized to enable the arbitrary tree case [ which admittedly, I
have yet to sell successfully !]

In one sense, there is a sense in the merge issue doesn't exist. When
the maintainer publishes a tag no-one expects to have to deal with
downstream conflicting definitions of the tag. Likewise, if the
maintainer were to publish the /man and /html metadata trees (per my
previous example) for a release tag, anyone who received
/refs/metadata/doc would expect to receive the metadata trees as
published by the maintainer. Anyone who didn't wouldn't have to pull
/refs/metadata/doc.

I can see there are use cases where multiple parties might want to
contribute metadata and I do not currently have a good solution to
that problem, but that is not to say there isn't one - surely it is
just a question of applying a little intellect creatively?

Are you trying to repeat fail of Apple's / MacOS / HFS+ filesystem
data/resource forks, and Microsoft's Alternate Data Streams in git? :-)

-- 
Jakub Narebski
Poland
ShadeHawk on #git

On Sun, Feb 7, 2010 at 8:15 PM, Jakub Narebski [off-list ref] wrote:

Jon Seymour [off-list ref] writes:

[cut]

quoted

As I see it, the existing use of notes is a special instance of a more
general metadata capability in which the metadata is constrained to be
a single blob. If notes continued to be constrained in this way, there
is no reason to change anything with respect to its current userspace
behaviour. That said, most of the plumbing which enabled notes could
be generalized to enable the arbitrary tree case [ which admittedly, I
have yet to sell successfully !]

In one sense, there is a sense in the merge issue doesn't exist. When
the maintainer publishes a tag no-one expects to have to deal with
downstream conflicting definitions of the tag. Likewise, if the
maintainer were to publish the /man and /html metadata trees (per my
previous example) for a release tag, anyone who received
/refs/metadata/doc would expect to receive the metadata trees as
published by the maintainer. Anyone who didn't wouldn't have to pull
/refs/metadata/doc.

I can see there are use cases where multiple parties might want to
contribute metadata and I do not currently have a good solution to
that problem, but that is not to say there isn't one - surely it is
just a question of applying a little intellect creatively?

Are you trying to repeat fail of Apple's / MacOS / HFS+ filesystem
data/resource forks, and Microsoft's Alternate Data Streams in git? :-)

No I am not. I don't see why a metadata proposal is any more exposed
to subversive payloads than say, use of git merge -s ours [ a
subversive payload could be made reachable from a commit that
otherwise merges in favour of the legitimate source - who would know?
]

Really, I can't see why the rationale that makes a single blob used
for extending a commit message justified can't be used to justify
associating a metadata tree of arbitrary complexity to an arbitrary
sha1 object. What makes maintaining a mapping to a single blob
acceptable but maintaining a mapping to a tree unacceptable? Is there
really any fundamental difference?

jon.

To explain a little further why the metadata concept is different to
the resource fork or alternate data stream concept.

These two concepts were based on the idea of associating metadata with
the name of the resource and preserving the metadata along with the
resource as the resource evolved.

This is not the intent with the metadata concept. Rather, the idea is
to annotate the content (whether it be a commit, tree or blob) with
other content (a tree in the general metadata case, or a blob in the
git notes case)

The use cases I have in mind relate to caching "expensive (or
impractical) to re-derive" results from an input. So, for example,
storing /man and /html  trees for a given commit in a metadata commit
called "refs/metadata/doc" would be one case. Storing the foreign SCM
revision id that a git repo was pushed into would be another [ storing
it the commit message isn't an option because the commit has already
happened before the push ]. [ And granted: git notes can already be
used for this scenario ].

jon.

On Sun, Feb 7, 2010 at 8:41 PM, Jon Seymour [off-list ref] wrote:

On Sun, Feb 7, 2010 at 8:15 PM, Jakub Narebski [off-list ref] wrote:

quoted

Jon Seymour [off-list ref] writes:

[cut]

quoted

As I see it, the existing use of notes is a special instance of a more
general metadata capability in which the metadata is constrained to be
a single blob. If notes continued to be constrained in this way, there
is no reason to change anything with respect to its current userspace
behaviour. That said, most of the plumbing which enabled notes could
be generalized to enable the arbitrary tree case [ which admittedly, I
have yet to sell successfully !]

In one sense, there is a sense in the merge issue doesn't exist. When
the maintainer publishes a tag no-one expects to have to deal with
downstream conflicting definitions of the tag. Likewise, if the
maintainer were to publish the /man and /html metadata trees (per my
previous example) for a release tag, anyone who received
/refs/metadata/doc would expect to receive the metadata trees as
published by the maintainer. Anyone who didn't wouldn't have to pull
/refs/metadata/doc.

I can see there are use cases where multiple parties might want to
contribute metadata and I do not currently have a good solution to
that problem, but that is not to say there isn't one - surely it is
just a question of applying a little intellect creatively?

Are you trying to repeat fail of Apple's / MacOS / HFS+ filesystem
data/resource forks, and Microsoft's Alternate Data Streams in git? :-)

No I am not. I don't see why a metadata proposal is any more exposed
to subversive payloads than say, use of git merge -s ours [ a
subversive payload could be made reachable from a commit that
otherwise merges in favour of the legitimate source - who would know?
]

Really, I can't see why the rationale that makes a single blob used
for extending a commit message justified can't be used to justify
associating a metadata tree of arbitrary complexity to an arbitrary
sha1 object. What makes maintaining a mapping to a single blob
acceptable but maintaining a mapping to a tree unacceptable? Is there
really any fundamental difference?

jon.

On Sun, Feb 07, 2010 at 04:36:59PM +1100, Jon Seymour wrote:

As I see it, the existing use of notes is a special instance of a more
general metadata capability in which the metadata is constrained to be
a single blob. If notes continued to be constrained in this way, there
is no reason to change anything with respect to its current userspace
behaviour. That said, most of the plumbing which enabled notes could
be generalized to enable the arbitrary tree case [ which admittedly, I
have yet to sell successfully !]

I do agree that storing trees is a natural generalization of the current
notes implementation. Callers have to be made aware that they may see
trees, of course, but you could probably "demote" trees into their
representative sha1s for callers who were interested only in a blob
form.

But what I am concerned with is that generalizing may violate some
assumptions made about how notes work. Notes trees can re-balance
themselves to some degree, I thought (though I am pretty out of the loop
on current notes developments). So during merges we need to normalize
tree representations (though we probably already need to do that for the
blob case). We would also need to do some magic with rename detection
during merges.  You would probably want rename detection _within_ a tree
stored as a note for a particular commit, but not between notes stored
for different commits.

Or perhaps you would not even want to do a tree-merge between notes at
all, and would rather see a conflict if two people noted two different
trees. This would make sense to me if you were doing something like
noting a build setup. If I note that commit X builds with a tree
pointing to version Y of the build tools, and you note that it builds
with version Z of the build tools, what should happen when we merge our
notes? I can imagine wanting a conflict, and resolving it to Y or Z
(perhaps whichever is more desirable). I can also see resolving it to Y
_and_ Z (iow, treating it like a list). But doing a merge on the two
trees of build tools (which are presumably somewhat immutable) is
probably not helpful.

Which to me argues in favor of adding the extra level of indirection.
The note should store the tree sha1, and those who want to treat it as a
tree can do so. Rename and merge issues just go away, as they operate on
the tree sha1 and not on the tree itself. And of course the
representation is just an implementation detail; you could still make a
"git metadata" wrapper to transparently store trees from the user's
perspective.

The only complication is that git doesn't know to follow those sha1s for
reachability analysis. In some cases that won't matter (like Junio's
html/man example), but I suspect in some it will. Perhaps there is some
way to flag the note entry as "this stores a sha1 that should be
followed by fsck, but not otherwise dereferenced".

I dunno. That is all just thinking out loud. It would help if we had
some really detailed concrete examples of notes being used in practice.

-Peff

On Sunday 07 February 2010, Jeff King wrote:

I think I may have been the one to suggest trees or notes at one point.
But let me clarify that this is not exactly what the OP is proposing in
this thread.

My suggestion was that some use cases may have many key/value pairs of
notes for a single sha1. We basically have two options:

  1. store each in a separate notes ref, with each sha1 mapping to
     a blob. The note "name" is the name of the ref.

  2. store notes in a single notes ref, with each sha1 mapping to a
     tree with named sub-notes. The note "name" is the combination of
     ref-name and tree entry name.

The advantage of (1) is that notes are not bound tightly to each other.
I can distribute the notes tree for one "name" independent of the
others.  The advantage of (2) is that it is faster and smaller. In (1),
each note has a separate index, and we must traverse each note index
separately.

In practice, I would expect to use (1) for logically separate datasets.
For example, automatic bug-tracking notes would go in a different ref
from human annotations. But I would expect to use (2) if I had, say, 5
different pieces of bug tracking information and I wanted an easy way to
refer to them individually.

And a specialized merge for that is straightforward. In the simplest
case, you simply say "notes of this ref are tree-type, or they are
blob-type" and then you have no merge problems. But if you want to get
fancy, you can say that a conflict between "sha1/blob" and
"sha1/tree/key" should automatically "promote" the first one into
"sha1/tree/default" or some other canonical name.

Note that all of this is my pie-in-the-sky "here is what I was thinking
of when I looked at notes a long time ago". I don't care strongly if it
gets implemented or not at this point; I just wanted to add some context
to what Johan had in his notes todo list (or maybe I am wrong, and what
is in his todo list was based on something totally different said by
somebody else, and I have just confused the issue more. :) ).

No, My TODO item was indeed based on your suggestion (although poorly 
represented by me, both in the TODO list, and in my original answer to Jon). 
However, note that I don't feel this specific itch myself, so I'm unlikely 
to scratch it.

With respect to the idea of storing an arbitrary tree, I agree it is
probably too complex with respect to merging. In addition, it makes
things like "git log --format=%N" confusing. I think you would do better
to simply store a tree sha1 inside the note blob, and callers who were
interested in the tree contents could then dereference it and examine as
they saw fit.  The only caveat is that you need some way of telling git
that the referenced trees are reachable and not to be pruned.

Agreed. Arbitrary trees as notes objects is probably not a good idea.


...Johan

-- 
Johan Herland, [off-list ref]
www.herland.net