Re: [RFC] Applying a graft to a tree and "rippling" the changes through

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

Ryan wrote:
> Junio wrote:
> > Also another rhetorical, tongue-in-cheek question.  What is your
> > plan to ripple the graft through to update signed tags?  ;-)
> 
> :) Well, since I can't resist answering your rhetorical question:
> 
> They signed a specific DAG.  I'm providing a richer, more complete DAG
> that is a pure-superset of the one they signed.  It is not, however,
> equivalent, so their signature is not related to the superset DAG I have
> created.  In practice, however, I don't expect that any tag-signers
> would state that there is a meaningful difference between the two DAGs,
> from the perspective of their signature.

Well, that seems the perfect place to mention an idea that's running
in my head since a couple of days, related to the grafing problem.
I'll write it here in case the idea would look interesting to others,
who may then find a solution to the problem stated by Junio.

Current commit objects refer to a child tree, but to parent _commits_.
Whereas it seems necessary to walk through the history line, and
easily get a changelog, it is semantically quite not right: the
changes we record with a commit indeed come from modification of
trees, not of commits.  That is, the resulting tree does not depend on
the history of the parent trees, but on the parent trees themselves.
And similarly, tags usually denote a particular state of the tree,
"somewhat" independantly of its history: linux-2.6.11 is the same
beast, whereas the repository holds full history since 0.1 or not.

Indeed that emphasizes that the history lines are on living on a
higher level of abstraction that commits.  Now what if we used
trees->tree commits, instead of the current commits->tree ones ?  The
main problem would be to be able to reconstruct those history lines,
so that we can still extract the log - what's a better model if we
loose functionnality ? ;)

However, I must admit that at this point, I have not found a
reasonable solution to this problem.

Any genius with a solution out there ? :)
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Johannes Schindelin]

Hi,

On Fri, 18 Nov 2005, Yann Dirson wrote:

> Current commit objects refer to a child tree, but to parent _commits_.
> Whereas it seems necessary to walk through the history line, and
> easily get a changelog, it is semantically quite not right:

Yes, it is. You base *your* work on *some* work. So, even if the trees may 
be equal, the base isn't.

> Indeed that emphasizes that the history lines are on living on a
> higher level of abstraction that commits.  Now what if we used
> trees->tree commits, instead of the current commits->tree ones ?

Now, how exactly would that be more abstract? Trees are just that: 
collections of files. Noone tells you what the idea was, which led from 
the last tree(s) to this one. That is not abstract.

> Any genius with a solution out there ? :)

Not a genius, but me: Write down your ideas in the commit message. That it 
the place to put abstract thoughts into.

Ciao,
Dscho

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[sf]

Yann Dirson wrote:
...
> Current commit objects refer to a child tree, but to parent _commits_.
> Whereas it seems necessary to walk through the history line, and
> easily get a changelog, it is semantically quite not right: the
> changes we record with a commit indeed come from modification of
> trees, not of commits.  That is, the resulting tree does not depend on
> the history of the parent trees, but on the parent trees themselves.

I would go even further: The resulting tree does not depend on anything. 
A tree is a tree is a tree.

A commit is really just the statement: "I changed the tree from state A 
to state B". After all, the commit message does not describe the new 
state (neither the old state) but does describe the changes.

> And similarly, tags usually denote a particular state of the tree,
> "somewhat" independantly of its history: linux-2.6.11 is the same
> beast, whereas the repository holds full history since 0.1 or not.

Exactly, the tree "linux-2.6.11" is the tree "linux-2.6.11". How it came 
about is totally irrelevant if you are only interested in this 
particular version (does anyone download all linux-*.tar.bz2 just to get 
  linux-2.6.11.tar.bz2?).

> Indeed that emphasizes that the history lines are on living on a
> higher level of abstraction that commits.  Now what if we used
> trees->tree commits, instead of the current commits->tree ones ?  The
> main problem would be to be able to reconstruct those history lines,
> so that we can still extract the log - what's a better model if we
> loose functionnality ? ;)

You can traverse tree -> commit -> tree -> commit -> tree ... to get the 
history. No functionality lost.

> However, I must admit that at this point, I have not found a
> reasonable solution to this problem.
> 
> Any genius with a solution out there ? :)

In your model you have a mapping from commits to sets of trees (by way 
of commit objects). Now you create the "inverse" mapping from trees to 
sets of commits. Both mappings together enable you to walk the history.

Why is git's model different?

1. You have to watch out for circles in history (Git's model ensures 
that history is always a DAG).

2. Your model is harder to implement in the typical case (But deleting 
from repositiories, partial repositories, augmenting or cutting history 
etc. are hard to implement as it is now, if not outright impossible).

3. It is the way repositories have been organized ever since CVS (Git 
throws out some concepts of the CVS model, but not all).


Regards
	Stephan

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Josef Weidendorfer]

On Friday 18 November 2005 00:07, Yann Dirson wrote:
> Current commit objects refer to a child tree, but to parent _commits_.
> Whereas it seems necessary to walk through the history line, and
> easily get a changelog, it is semantically quite not right: the
> changes we record with a commit indeed come from modification of
> trees, not of commits.

Yes. The change to a tree (which is equalent to 2 trees - new old and
the new one; or for merges multiple old ones and the new one) does not
depend on any history. Unfortunately, we have no separate object to
specify the "the change to a tree". We include this information into
the commit object, and thus, bind it to the history.

This could be changed in git, i.e. put the tree relationship into a
separate object; even comments could be split up in change related and
history related. The question is: is this useful, is there any
important usage scenario that rectifies such a change?
I do not really think so.

> That is, the resulting tree does not depend on 
> the history of the parent trees, but on the parent trees themselves.

No, the resulting tree is an independent object, it is the tree ;-)
Do not confuse this with the commit pointing to the tree.

> And similarly, tags usually denote a particular state of the tree,
> "somewhat" independantly of its history: linux-2.6.11 is the same
> beast, whereas the repository holds full history since 0.1 or not.

I agree that tags for tree objects are useful, but what is the problem?
You can do this already.

But tags for commit objects are equally useful, especially signed ones:
they include a fixed history which can not be changed. Eg. they include
all the people which attributed code to the project, and this is important
for license questions. This is the reason that "grafting" should stay
a local workaround.

That the concrete tag "linux-2.6.11" points to a commit, and not to the
tree object, probably was done on purpose; i.e. the creator of the tag
wanted to include the history. If not, he could have made the tag for the
tree object directly.

> Indeed that emphasizes that the history lines are on living on a
> higher level of abstraction that commits.

Hmm.. If you only have tree changes, there is no history. The history
specifies an order of the changes. The changes themselve do not include
any such order.

> Now what if we used 
> trees->tree commits, instead of the current commits->tree ones ?

It would be better to not talk about "commits" for tree changes (perhaps
with comments about the change). As said above, tree change objects
could be introduced. The question is why?

> The
> main problem would be to be able to reconstruct those history lines,
> so that we can still extract the log

No problem: You still have the chain of commits, and one commit points
to the parent commit(s) and the corresponding new introduced tree change
objects.

> - what's a better model if we 
> loose functionnality ? ;)

There is nothing lost. If you regard the comments entered at "git commit"
time as purely change related, this comments can be put together with the
tree change object. So if you "apply a graft to a tree", (signed) tags for tree
changes would include the comment, and stay valid after "regrafting".
But why would anyone want to sign a change?

> However, I must admit that at this point, I have not found a
> reasonable solution to this problem.
> 
> Any genius with a solution out there ? :)

What is the difficult problem here?

Josef

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Linus Torvalds]

On Fri, 18 Nov 2005, sf wrote:
> 
> I would go even further: The resulting tree does not depend on anything. A
> tree is a tree is a tree.

Agreed.

> A commit is really just the statement: "I changed the tree from state A to
> state B". After all, the commit message does not describe the new state
> (neither the old state) but does describe the changes.

No.

A commit is _not_ just the statement of change between two trees.

It's a statement of _history_ of the resulting tree. This is important. 
It's why a commit does not just point to the previous tree, but to the 
previous commit(s).

And that's really important. If you don't have a history of what has 
happened, then all the trees are just random collections of files. They're 
not a project any more.

So a commit doesn't just say "tree A changed into tree B". It very much 
says something much much stronger, which includes how you got to A in the 
first place.

The history is also what allow a commit to be meaningful. Without that 
history, you could never say "I fixed the bug that was introduced by xyz", 
which is often a very integral part of _why_ the change happened.

There are lots of changelog entries that don't necessarily make sense 
without knowing what went before them, so history is actually important 
even in a local sense - it's often what allows the explanation to make 
sense.

			Linus

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Fri, 18 Nov 2005, sf wrote:
>> 
>> A commit is really just the statement: "I changed the tree from state A to
>> state B". After all, the commit message does not describe the new state
>> (neither the old state) but does describe the changes.
>
> There are lots of changelog entries that don't necessarily make sense 
> without knowing what went before them, so history is actually important 
> even in a local sense - it's often what allows the explanation to make 
> sense.

I agree with what you said about commit objects and what they
are meant to describe.  At the same time, I am sympathetic if
somebody wants to be able to say just "The change this commit
brings in can be used to modify the behaviour X to Y".  An
implied prerequisite for such a statement is that you can apply
such a change only to something that has behaviour X, and
internally works in a certain way to exhibit that behaviour, to
begin with (IOW, otherwise the patch does not apply).  While
your "commit describes all the history leading to it" obviously
satisfies that prerequisite, it is stronger than necessary.

For that matter, "tree A changed into tree B" is stronger than
necessary as well.  There are trees other than tree A that has
the same behaviour X, and applying such a change would be valid
to modify its behaviour to Y.

You are absolutely right that commit messages should be taken in
the context of the history leading to it.  However, when we
exchange patches via e-mail, or do "rebase" in the repository,
we also use the commit message to label the change -- and with
that usage, the log message becomes less about describing the
history and more about "modifies X to Y", so it is easy to get
confused.

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Linus Torvalds]

On Fri, 18 Nov 2005, Junio C Hamano wrote:
>
> At the same time, I am sympathetic if somebody wants to be able to say 
> just "The change this commit brings in can be used to modify the 
> behaviour X to Y".

Well, you can obviously use a commit that way, and indeed, every time we 
do a "rebase", that's effectively saying "I know the commit has history, 
but now I want to use it purely as a tree conversion".

I'm not convinced we ever really _need_ a pure "tree-to-tree" thing, 
although you can always do that by creating an extra commit with no parent 
and thus no history ;)

		Linus

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> I'm not convinced we ever really _need_ a pure "tree-to-tree" thing, 
> although you can always do that by creating an extra commit with no parent 
> and thus no history ;)

Nah, it is more like a commit object that records its tree and
another tree as its parent ;-).

I do not think tree-to-tree thing is very useful and that is
what I meant to say by "tree-to-tree is still stronger than
necessary".

What is recorded as a "change" by darcs feels more like "This
makes it to do Y instead of doing X", and it is not about
tree-to-tree.  I know David Roundy is lurking on this list;
David, do you have any comment on this?

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Linus Torvalds]

On Fri, 18 Nov 2005, Junio C Hamano wrote:
> 
> Nah, it is more like a commit object that records its tree and
> another tree as its parent ;-).

I don't think fsck would allow that. At least it wasn't _meant_ to allow 
it, and it should complain about an object having the wrong type.

And I'd hope that "git-commit-tree" would refuse to write such a thing.

		Linus

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Fri, Nov 18, 2005 at 02:57:05PM +0100, sf wrote:
> >Indeed that emphasizes that the history lines are on living on a
> >higher level of abstraction that commits.  Now what if we used
> >trees->tree commits, instead of the current commits->tree ones ?  The
> >main problem would be to be able to reconstruct those history lines,
> >so that we can still extract the log - what's a better model if we
> >loose functionnality ? ;)
> 
> You can traverse tree -> commit -> tree -> commit -> tree ... to get the 
> history. No functionality lost.

No, that would require that a tree knows about the commits leading to
it, which would mix levels of abstraction as well.

-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Fri, Nov 18, 2005 at 04:54:20PM +0100, Josef Weidendorfer wrote:
> On Friday 18 November 2005 00:07, Yann Dirson wrote:
> > Current commit objects refer to a child tree, but to parent _commits_.
> > Whereas it seems necessary to walk through the history line, and
> > easily get a changelog, it is semantically quite not right: the
> > changes we record with a commit indeed come from modification of
> > trees, not of commits.
> 
> Yes. The change to a tree (which is equalent to 2 trees - new old and
> the new one; or for merges multiple old ones and the new one) does not
> depend on any history. Unfortunately, we have no separate object to
> specify the "the change to a tree". We include this information into
> the commit object, and thus, bind it to the history.
> 
> This could be changed in git, i.e. put the tree relationship into a
> separate object; even comments could be split up in change related and
> history related. The question is: is this useful, is there any
> important usage scenario that rectifies such a change?

The scenario I have it mind is "archeological work" - see my post
under "info/grafts file" for details.  With luck for future work
vendors will switch to git and give access to their git history (or
use quilt or stgit and provide detailed patch stacks), so the need
could well disappear, but I would not could on it, as there are still
many firms working on a 2.4 base and only exporting monolithic
patches.


> > That is, the resulting tree does not depend on 
> > the history of the parent trees, but on the parent trees themselves.
> 
> No, the resulting tree is an independent object, it is the tree ;-)
> Do not confuse this with the commit pointing to the tree.

Right, that was a wrong wording.  I meant the resulting tree results
from the change and and the parent trees themselves, not from the
change and the previous history.


> But tags for commit objects are equally useful, especially signed ones:
> they include a fixed history which can not be changed. Eg. they include
> all the people which attributed code to the project, and this is important
> for license questions. This is the reason that "grafting" should stay
> a local workaround.

This, and chaining commits is also useful to prevent loops, as said in
another part of this thread.  But I wouldn't let such considerations
stop exploration first.  If we cannot find a reasonable and useful way
of applying those ideas without taking these 2 points into account as
a first approximation, there would be no point in adding these 2
constraints right away :).  It can be sufficient for now to be aware
of those and add them later.


> > Indeed that emphasizes that the history lines are on living on a
> > higher level of abstraction that commits.
> 
> Hmm.. If you only have tree changes, there is no history. The history
> specifies an order of the changes. The changes themselve do not include
> any such order.

Right, but that does not mean we cannot reconstruct history from those
changes.  It came to my mind during the last day, that if we had
commits only reference trees, we could construct from them the
equivalent of today's commit objects (which I'll call "history
objects" for clarity), but we could look at those generated "history
objects" as "cached" objects.  Together with a cache of tree->commit
reverse-mapping objects as Stephan mentionned, we could generate them
on-the-fly at commit time.

Remember that in a first approach, I'll only consider those history
objects as a means to get a history log or similar.

That would give us low-intrusion grafts: we can regenerate the
relevant part of the "history object" cache when a commit gets added
or replaced, similarly to what would be done at commit-creation time.
But we would not need to regenerate all subsequent commit objects, so
that all refs/tags pointing to those subsequent commits would not need
to be messed with.

Since we would then have history objects looking like current commits,
we could even get a similar safeguard against history loops.


And if we want to get the "signed tag certifies history" stuff, we
could envision making some of these history objects permanent.  But if
we allow history object to refer to tree parents as well, we do not
_need_to_ certify on every such tag the entire history plus changes
since the previous tag: a chain of "history objects" could stop on a
tree, thus making the tag a certificate of an incremental patch (ie,
what we get from signed patches in pub/linux/kernel, with the added
bonus of signing the invididual bits making up this patch).


> > However, I must admit that at this point, I have not found a
> > reasonable solution to this problem.
> > 
> > Any genius with a solution out there ? :)
> 
> What is the difficult problem here?

Getting a pure superset of the functionnality we currently have (while
not impairing git use in term of computing time).  But finally that
may not be as hard as I expected :)

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Fri, Nov 18, 2005 at 05:21:16PM -0800, Junio C Hamano wrote:
> I do not think tree-to-tree thing is very useful and that is
> what I meant to say by "tree-to-tree is still stronger than
> necessary".
> 
> What is recorded as a "change" by darcs feels more like "This
> makes it to do Y instead of doing X", and it is not about
> tree-to-tree.

I'm not sure we could go that path.  I see git and darcs as quite
opposed in approach, since darcs works by explicitely describing the
structure of changes, whereas git allows to use arbitrary ways to
derive this structure from the trees.

But then if we could reconcile those 2 approaches...

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Fri, Nov 18, 2005 at 12:28:56AM +0100, Johannes Schindelin wrote:
> On Fri, 18 Nov 2005, Yann Dirson wrote:
> 
> > Current commit objects refer to a child tree, but to parent _commits_.
> > Whereas it seems necessary to walk through the history line, and
> > easily get a changelog, it is semantically quite not right:
> 
> Yes, it is. You base *your* work on *some* work. So, even if the trees may 
> be equal, the base isn't.

Hm, I'm not sure I get your point here.

> > Indeed that emphasizes that the history lines are on living on a
> > higher level of abstraction that commits.  Now what if we used
> > trees->tree commits, instead of the current commits->tree ones ?
> 
> Now, how exactly would that be more abstract? Trees are just that: 
> collections of files. Noone tells you what the idea was, which led from 
> the last tree(s) to this one. That is not abstract.

Trees have an existence outside any consideration of what changes led
to them, as shown by the fact that git trees do not reference anything
outside them.  And it is right that, at that level, noone tells you
how you got there - not less nor more than when you fetch a
linux-x.y.z.tar.gz2 from kernel.org.

Then at a bit higher level, you can consider changes from a tree to a
tree.  What you usually do when you commit a change is explaining what
you change to the tree.  Then changes themselves are just derived from
the trees (iow, "abstracted from" the trees), and you augment this
information with a message explaining what you did.

Then at a still higher level, you can derive history lines from the
individual trees and changes, and augment this information, eg. by
signing them.


The fact is, currently git does not distinguish much between those 2nd
and 3rd levels.  It is my understanding that one of the most basic
design decisions of git was precisely to make the tool "aware" of the
1st level, and that it played an important part of why git works so
well: it maps to the reality closer than any other tool.

I was not convinced at all by the ideas when git appeared, but that
was probably because I was too much influenced by previous tools, all
focussing either on the history line (most of them), or on the changes
(darcs).

I think that if we can formalize into git the disctinction between
those two higher levels (and possibly other levels in the future), we
could get to an even more powerful and usable tool, even if, like git,
the basic ideas may look weird and possibly even counter-productive at
first sight.


As an example, here is an idea I had while formalizing the above 3rd
level: we also work at this level when rolling back a previous change,
since we take the history line into account.  We could add, at that
History level, the possiblity to record this information, by linking
to that previous commit.

Now maybe I was mistaken in thinking the objects at the History level
should be only "cached" and temporary objects - that, and loop
prevention, and signed history lines, make too many reasons for them
to be permanent already :).

But their existence as such should not prevent to work at a lower
level.  I'll have to reconsider the way I intended to design my
ArcheoloGIT toolkit, but I'm afraid it would need a new generation of
GIT ;)

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Sat, Nov 19, 2005 at 03:04:05PM +0100, Yann Dirson wrote:
> Trees have an existence outside any consideration of what changes led
> to them, as shown by the fact that git trees do not reference anything
> outside them.  And it is right that, at that level, noone tells you
> how you got there - not less nor more than when you fetch a
> linux-x.y.z.tar.gz2 from kernel.org.
> 
> Then at a bit higher level, you can consider changes from a tree to a
> tree.  What you usually do when you commit a change is explaining what
> you change to the tree.  Then changes themselves are just derived from
> the trees (iow, "abstracted from" the trees), and you augment this
> information with a message explaining what you did.
> 
> Then at a still higher level, you can derive history lines from the
> individual trees and changes, and augment this information, eg. by
> signing them.

IOW,
- 1st level describes states that existed
- 2nd level describes events that occured, causing the state to change
- 3rd level describes the succession of events

and for the record, I am likely to introduce with ArcheoloGIT a 4th
level, which will describe how our idea of history evolves over time.

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Johannes Schindelin]

Hi,

On Sat, 19 Nov 2005, Yann Dirson wrote:

> - 1st level describes states that existed
> - 2nd level describes events that occured, causing the state to change
> - 3rd level describes the succession of events

But using git's approach you have these levels. Only that you do not 
strictly record them as such:

	- 1st level is trees, agreed.

	- 2nd level is inside the commits, i.e. if you look at the tree(s)
	  of the parent commit(s), you can extract that tree->tree change.

	- 3rd level is not just the succession of events: commit->commit
	  is much stronger.

By the last, I mean that in the commit, by referencing the parent(s) 
(which itself references its parent(s)) you have the whole history. And by 
validating the commit object by its SHA1, you have the history immutable, 
too.

Now, the original purpose of this thread was to discuss a way to un-graft 
some commit objects, i.e. to re-record a history which was not recorded as 
such.

This may be nice for completeness purposes, but it contradicts the main 
idea behind git: You want to be certain about things. By signing off on 
some commit (together with the meta information about its parent(s) and 
the tree), you state that you actually placed your work on *that* 
particular history. And if you based your work on a commit I have, I can 
be certain that we agree.

The proposed rewriting of the history is very lax about that:

Say, you introduce a history line, where you start with -- say -- some 
obsolete proprietary code from some telephone company, and then change -- 
say, by a primitive algorithm -- the code to match git-0.99.8, all the 
time committing with some random commit message.

Then you make a graft which says git-0.99.8 was derived from that history 
, too. Now, you ungraft the tree. It looks like other developers and I 
signed off on working on a "derivative" of some obscure, copyrighted code.

Nice?

Hth,
Dscho

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

Hi,

On Sat, Nov 19, 2005 at 04:27:12PM +0100, Johannes Schindelin wrote:
> On Sat, 19 Nov 2005, Yann Dirson wrote:
> > - 1st level describes states that existed
> > - 2nd level describes events that occured, causing the state to change
> > - 3rd level describes the succession of events
> 
> But using git's approach you have these levels. Only that you do not 
> strictly record them as such:
> 
> 	- 1st level is trees, agreed.
> 
> 	- 2nd level is inside the commits, i.e. if you look at the tree(s)
> 	  of the parent commit(s), you can extract that tree->tree change.
> 
> 	- 3rd level is not just the succession of events: commit->commit
> 	  is much stronger.

I think we do agree on this too - it's just the usual problem with
written discussions.

> By the last, I mean that in the commit, by referencing the parent(s) 
> (which itself references its parent(s)) you have the whole history. And by 
> validating the commit object by its SHA1, you have the history immutable, 
> too.

Right.  But the 2nd and 3rd levels are not currently distinct in git.
See below.


> Now, the original purpose of this thread was to discuss a way to un-graft 
> some commit objects, i.e. to re-record a history which was not recorded as 
> such.
> 
> This may be nice for completeness purposes, but it contradicts the main 
> idea behind git: You want to be certain about things. By signing off on 
> some commit (together with the meta information about its parent(s) and 
> the tree), you state that you actually placed your work on *that* 
> particular history. And if you based your work on a commit I have, I can 
> be certain that we agree.

My proposal only introduces an additional level.  You will still be
able to sign history lines, and they will still be immutable.

This proposal is only meant to add some flexibility.  With the current
model, if I take Linus' 2.6 tree, I only have the 2.6 history back to
2.6.12rc2.  I would first like to note that any signed commit in this
tree can assert nothing prior to that version: we are only able to
check part of the history.

Now let's suppose that I am interested in adding some prior history,
say 2.6.11->2.6.12rc2.  I can add the tree and commit objects for that
range, and I now want to graft to current tree.  That is, I will add a
new history line, which will have to duplicate all subsequent commits
from the current tree.  That includes for example duplicating
comments, whereas in my model they would belong to the level below,
and would not need duplicating: the new history line will just
reference the lower-level commits, which do contain
comment/date/author information.  The history-level objects will
probably just need to contain the following information:

- commit to describe
- previous history
- history commiter, which may be distinct from the commiter of the
  change
- date of the record of the history object, which will be distinct
  from the commit date, except usually for the history line on which
  the change author works

We can then note that:

- to provide the same level of information with current objects, the
commits on the new history line would have to also point to their
counterpart in the original history line, adding information that
belongs to the 4th level (how our view of history evolves with time)

- the number of history objects could be made much less than the
number of commits, by using a single one to describe the full path
between two branchpoints of that history line:

parent: xxxxxx
parent: yyyyyy
commit: zzzzzz
commit: aaaaaa
commit: bbbbbb
committer: ...
date: ...

> The proposed rewriting of the history is very lax about that:
> 
> Say, you introduce a history line, where you start with -- say -- some 
> obsolete proprietary code from some telephone company, and then change -- 
> say, by a primitive algorithm -- the code to match git-0.99.8, all the 
> time committing with some random commit message.
> 
> Then you make a graft which says git-0.99.8 was derived from that history 
> , too. Now, you ungraft the tree. It looks like other developers and I 
> signed off on working on a "derivative" of some obscure, copyrighted code.

No, the grafted commits should not be accessible from a
previously-signed history line.  The operation you describe will
produce a different history line, and I can already do the same with
git now :)

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Matthias Urlichs]

Hi, Yann Dirson wrote:

> But the 2nd and 3rd levels are not currently distinct in git.

I don't think you *can* make them distinct. Sure, you could introduce 
"change" object which refers to a couple of source trees and a destination
tree, and then create a "history" object which links previous history and
a change, but what's the point? What can you do with such a thing
that you cannot do now, just as easily, besides slow down your programs
with an unnecessary level of indirection?

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
"To those who wish to punish others--or at least to see them punished, if
 the avengers are too cowardly to take matters in to their own hands-- the
 belief in a fiery, hideous hell appears to be a great source of comfort."
            [Steve Allen, "Steve Allen, on
             the Bible Religion & Morality"]

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Johannes Schindelin]

Hi,

On Sat, 19 Nov 2005, Matthias Urlichs wrote:

> [...] What can you do with such a thing that you cannot do now, just as 
> easily, besides slow down your programs with an unnecessary level of 
> indirection?

I tend to agree. In fact, if I would like to introduce earlier history 
(for the sake of archeology or whatever), I would import the earlier 
history into git, possibly finding the best match in the current 
development branch (for example, when the original project continued for a 
while to be tracked in CVS), and then make a merge between these two.

Then, I'd merge the new development's HEAD, and it would be fine:

ORIG1 .. ORIG2 .. .. ORIG_HEAD
                         |
                         |   GIT1 .. GIT2 .. .. GIT_HEAD
                         |   /                    /
                         | /                     /
                      UNIFYING_MERGE           /
                                   \         /
                                     \     /
                               NEW_HEAD_FOR_ARCHEOLOGICAL_PURPOSES

Where ORIG_HEAD's tree is identical with GIT1's tree. The resulting branch 
would serve every research purpose I can think of (just be sure not to 
use "-m" with git-whatchanged).

Ciao,
Dscho

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Matthias Urlichs]

[-- Attachment #1: Type: text/plain, Size: 961 bytes --]

Hi,

Johannes Schindelin:
> Then, I'd merge the new development's HEAD, and it would be fine:
> 
Why not simply use info/grafts?

ORIG1 .. ORIG2 .. .. ORIG_HEAD
                            \\
                             GIT1 .. GIT2 .. .. GIT_HEAD

where the \\ link is the graft entry.

If we want (need, these days -- the history is so long that gitk draws
spurious lines becase of 16-bit window coordinate overflow) to chop off
history at some point, we can use the newfangled date parser + config
file stuff to set a sane default.

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
July 4.  Statistics show that we loose more fools on this day than in all the
other days of the year put together.  This proves, by the number left in stock,
that one Fourth of July per year is now inadequate, the country has grown so.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Johannes Schindelin]

Hi,

On Sun, 20 Nov 2005, Matthias Urlichs wrote:

> Why not simply use info/grafts?

'Cause you can't fetch a graft. But I agree, instead of telling somebody: 
"I have this new branch which unifies history", you can send your friend a 
oneliner which appends a graft.

Ciao,
Dscho

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Sun, Nov 20, 2005 at 02:24:53AM +0100, Johannes Schindelin wrote:
> Hi,
> 
> On Sat, 19 Nov 2005, Matthias Urlichs wrote:
> 
> > [...] What can you do with such a thing that you cannot do now, just as 
> > easily, besides slow down your programs with an unnecessary level of 
> > indirection?
> 
> I tend to agree. In fact, if I would like to introduce earlier history 
> (for the sake of archeology or whatever), I would import the earlier 
> history into git, possibly finding the best match in the current 
> development branch (for example, when the original project continued for a 
> while to be tracked in CVS), and then make a merge between these two.
> 
> Then, I'd merge the new development's HEAD, and it would be fine:
> 
> ORIG1 .. ORIG2 .. .. ORIG_HEAD
>                          |
>                          |   GIT1 .. GIT2 .. .. GIT_HEAD
>                          |   /                    /
>                          | /                     /
>                       UNIFYING_MERGE           /
>                                    \         /
>                                      \     /
>                                NEW_HEAD_FOR_ARCHEOLOGICAL_PURPOSES
> 
> Where ORIG_HEAD's tree is identical with GIT1's tree. The resulting branch 
> would serve every research purpose I can think of (just be sure not to 
> use "-m" with git-whatchanged).

Note: it's not only about research (ie. something that would be static
for browsing only), it's also about using the results of the research
in further developement.

Well, no doubt this approach can be used in many cases.  But it makes
IMHO the history somewhat confusing, and has limitations.  Let's say I
had a patch against ORIG2, and at a later date I find a successor for
it, based on GIT2.  I would not have an incarnation of GIT2 with ORIG2
as ancestor: to be on the safe side I would have had to duplicate the
whole GIT1..* history.

And after I have done some work on my branch of duplicate commits, if
I used the type of unifying merges you suggest, I'm stuck forever with
the old GIT1..GIT_HEAD line, whether I need it or not (if it comes
from import of 2.4 patches, and thus has no signed tags whatsoever, I
do not need it any more).

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Sun, Nov 20, 2005 at 12:44:28PM +0100, Johannes Schindelin wrote:
> On Sun, 20 Nov 2005, Matthias Urlichs wrote:
> 
> > Why not simply use info/grafts?
> 
> 'Cause you can't fetch a graft. But I agree, instead of telling somebody: 
> "I have this new branch which unifies history", you can send your friend a 
> oneliner which appends a graft.

It can also be useful to work with grafts locally, and then use a
script to convert the grafted tree into real commits.

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Johannes Schindelin]

Hi,

On Sun, 20 Nov 2005, Yann Dirson wrote:

> On Sun, Nov 20, 2005 at 02:24:53AM +0100, Johannes Schindelin wrote:
> > 
> > ORIG1 .. ORIG2 .. .. ORIG_HEAD
> >                          |
> >                          |   GIT1 .. GIT2 .. .. GIT_HEAD
> >                          |   /                    /
> >                          | /                     /
> >                       UNIFYING_MERGE           /
> >                                    \         /
> >                                      \     /
> >                                NEW_HEAD_FOR_ARCHEOLOGICAL_PURPOSES
> > 
> Note: it's not only about research (ie. something that would be static
> for browsing only), it's also about using the results of the research
> in further developement.

Then you could base your future development on 
NEW_HEAD_FOR_ARCHEOLOGICAL_PURPOSES.

> Well, no doubt this approach can be used in many cases.  But it makes
> IMHO the history somewhat confusing, and has limitations.  Let's say I
> had a patch against ORIG2, and at a later date I find a successor for
> it, based on GIT2.  I would not have an incarnation of GIT2 with ORIG2
> as ancestor: to be on the safe side I would have had to duplicate the
> whole GIT1..* history.

You could still branch from GIT2, cherry picking from the patch to ORIG2, 
and then committing the successor based on GIT2, thus reinstating the 
hypothetical history.

Note: the history may be confusing, but ask any history teacher: history 
*is* confusing! It is all about people. If you want to make it less 
confusing, I am afraid you have to leave the path of true history.

> And after I have done some work on my branch of duplicate commits, if
> I used the type of unifying merges you suggest, I'm stuck forever with
> the old GIT1..GIT_HEAD line, whether I need it or not (if it comes
> from import of 2.4 patches, and thus has no signed tags whatsoever, I
> do not need it any more).

But the GIT1..GIT_HEAD line was actually the correct history! Remember: He 
who forgets his past is doomed to repeat his mistakes! Don't pretend that 
the past was different than it was. It's not worth the hassle.

Ciao,
Dscho

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Matthias Urlichs]

[-- Attachment #1: Type: text/plain, Size: 2069 bytes --]

Hi,

Johannes Schindelin:
> > > ORIG1 .. ORIG2 .. .. ORIG_HEAD
> > >                          |
> > >                          |   GIT1 .. GIT2 .. .. GIT_HEAD
> > >                          |   /                    /
> > >                          | /                     /
> > >                       UNIFYING_MERGE           /
> > >                                    \         /
> > >                                      \     /
> > >                                NEW_HEAD_FOR_ARCHEOLOGICAL_PURPOSES
> > > 
> > Note: it's not only about research (ie. something that would be static
> > for browsing only), it's also about using the results of the research
> > in further developement.
> 
> Then you could base your future development on 
> NEW_HEAD_FOR_ARCHEOLOGICAL_PURPOSES.
> 
If you need a new HEAD *anyway*, then re-basing your trees would
IMHO be a better solution.

ORIG1 .. ORIG2 .. .. ORIG_HEAD
                         |
                         |   GIT1 .. GIT2 .. .. GIT_HEAD
                         |  //       //           //   \
                         | //       //           //    TAG
                      NEWGIT1 .. GIT2 .. .. NEW_HEAD
                                                   \
                                                  NEW_TAG

Those // links might be real parent pointers, which allows you to keep 
your old tags -- or not, which allows you to have a sane history. The
good part is that you can do this incrementally, so you won't need a
flag day.

I seriously doubt that all of this is worth the effort, given that you
can do the same thing with a graft line... and most people could care
less whether their histor starts at 2.6.11-whatever, 2.4, or 0.11.
(*Has* anybody imported the old tarballs into git, by the way?)

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
lately waking up i'm not sure where i've been
		-- Indigo Girls, "Language or the Kiss"

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Ryan Anderson]

[-- Attachment #1: Type: text/plain, Size: 1440 bytes --]

Matthias Urlichs wrote:

> If you need a new HEAD *anyway*, then re-basing your trees would
> IMHO be a better solution.
> 
> ORIG1 .. ORIG2 .. .. ORIG_HEAD
>                          |
>                          |   GIT1 .. GIT2 .. .. GIT_HEAD
>                          |  //       //           //   \
>                          | //       //           //    TAG
>                       NEWGIT1 .. GIT2 .. .. NEW_HEAD
>                                                    \
>                                                   NEW_TAG
> 
> Those // links might be real parent pointers, which allows you to keep 
> your old tags -- or not, which allows you to have a sane history. The
> good part is that you can do this incrementally, so you won't need a
> flag day.

This is exactly what the script I started this thread with does. It
would be mostly useful if someone had serious development work based of
an old, out-of-git branch, and wanted to use the git merging tools to
get it merged into something based against the current development.

I would expect that they would then want to rebase it or do something
else to clean up the mess that is created, and apply it directly to the
current development tree, rather than leaving it as part of that very
messy tree.

My other goal was to provide myself (and others) an example of using the
barebones core tools for some strange tasks that no *real* porcelain
would ever find useful.



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Yann Dirson]

On Mon, Nov 21, 2005 at 03:24:28AM +0100, Matthias Urlichs wrote:
> If you need a new HEAD *anyway*, then re-basing your trees would
> IMHO be a better solution.

Hell, that does look like a nice solution using current git - thanks.
I'll have to dig into that, and I'll come back if/when I hit its
limits too hard ;)


> I seriously doubt that all of this is worth the effort, given that you
> can do the same thing with a graft line...

Well, unfortunately there is still some things to get ironed out
before we have grafts propagated without yet another wrapper - which
ends up with them being still really private at that time.

But then, grafts may povide an inexpensive scratch space, which could
then be carved into rebased objects when the historian gets happy with
his work.


> and most people could care
> less whether their histor starts at 2.6.11-whatever, 2.4, or 0.11.

Right !  But then someone will occasionally want to use a release
before the start of his history, and it would be a shame to force full
kernel history on all poor developers who only need fresh-enough code.

But I still think we could reconcile those 2 approaches, if we would
allow partial history lines (ie, signing eg. commit chain from 2.6.n
to 2.6.(n+1), with the initial commit starting on a tree and not a
faked "commit from nil").

This would indeed a generalisation of what we have, since we only have
a signed chain of commits from 2.6.12rc2 in the official repo - and
maybe one more ancient from bk history.  It would even formally
acknowledge that we do not have the whole of the real history, and it
would leave the Unknown to be well-delimited, for any explorers who
would want to rebuild it, in case it would have any value, IP-wise.

And, more practically, where will the current kernel repo be when its
size will be 100 or 10000 times its current size ?  That would allow
to split it without too many problems.

Best regards,
-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Paul Mackerras]

Matthias Urlichs writes:

> If we want (need, these days -- the history is so long that gitk draws
> spurious lines becase of 16-bit window coordinate overflow) to chop off

I have it on good authority that canvas coordinates in Tcl/Tk are
*not* limited to 16 bits.  The Tcl/Tk core developers acknowledged
that there might be a bug in the code that translates canvas
coordinates to X coordinates (which are 16 bit), and asked me for a
screenshot or repro-case to illustrate the problem.

However, I was unable to get current gitk to exhibit the problem, even
with Thomas Gleixner's enormous history.git repository.  Do you have a
specific example (repository and commit ID) where you see the problem
occur?

Paul.

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Matthias Urlichs]

[-- Attachment #1: Type: text/plain, Size: 676 bytes --]

Hi,

Paul Mackerras:
> However, I was unable to get current gitk to exhibit the problem, even
> with Thomas Gleixner's enormous history.git repository.  Do you have a
> specific example (repository and commit ID) where you see the problem
> occur?
> 
I've seen it in the past ... hmmm ... testing ... and it seems to
majickally have fixed itself.

Oh well...

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
The Tenth Commandment of Frisbee: The single most difficult move with a disc
is to put it down. (Just one more.)
					-- Dan Roddick

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC] Applying a graft to a tree and "rippling" the changes through

[Linus Torvalds]

On Wed, 23 Nov 2005, Matthias Urlichs wrote:

> Hi,
> 
> Paul Mackerras:
> > However, I was unable to get current gitk to exhibit the problem, even
> > with Thomas Gleixner's enormous history.git repository.  Do you have a
> > specific example (repository and commit ID) where you see the problem
> > occur?
> > 
> I've seen it in the past ... hmmm ... testing ... and it seems to
> majickally have fixed itself.

I saw it all the time before adding the "arrows" logic. 

With the arrows, the graph never gets so complex that you'd see it.

		Linus