Re: git-rerere observations and feature suggestions

Karl Hasselström [off-list ref] writes:

So how many parents can a commit have, exactly? Is there a hard limit
somewhere, or just a point beyond which some git tools will start
behaving strangely?

There is no hard limit at the data structure level.

git-commit-tree has a hard limit of accepting 16 parents.  git-blame has
the same 16-parent limit while following the history (but the one in
'next' has lifted the latter limitation).

But that is purely academic.  Anybody who does an octopus with more than 8
legs should get his head examined ;-).

On 2008-06-19 00:30:43 -0700, Junio C Hamano wrote:

Karl Hasselström [off-list ref] writes:

quoted

So how many parents can a commit have, exactly? Is there a hard
limit somewhere, or just a point beyond which some git tools will
start behaving strangely?

There is no hard limit at the data structure level.

git-commit-tree has a hard limit of accepting 16 parents. git-blame
has the same 16-parent limit while following the history (but the
one in 'next' has lifted the latter limitation).

Thanks.

But that is purely academic. Anybody who does an octopus with more
than 8 legs should get his head examined ;-).

Catalin and I are tossing ideas around for how to represent the
history of an StGit patch stack (using a git commit for each log
entry). One complication is that we have to keep references to all
unapplied patches so that gc will leave them alone (and so that they
will get carried along during a pull, in the future). And the number
of unapplied patches is potentially large, so I thought we'd be going
to have to make a tree of "merge" commits to connect them all up.

(What we'd really like, of course, is a way to refer to a set of
commits such that they are guaranteed to be reachable (in the gc and
pull sense), but not considered "parents".)

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

On Thu, Jun 19, 2008 at 10:21:56AM +0200, Karl Hasselström [off-list ref] wrote:

Catalin and I are tossing ideas around for how to represent the
history of an StGit patch stack (using a git commit for each log
entry). One complication is that we have to keep references to all
unapplied patches so that gc will leave them alone (and so that they
will get carried along during a pull, in the future). And the number
of unapplied patches is potentially large, so I thought we'd be going
to have to make a tree of "merge" commits to connect them all up.

(What we'd really like, of course, is a way to refer to a set of
commits such that they are guaranteed to be reachable (in the gc and
pull sense), but not considered "parents".)

I had a similar problem in git/vmiklos.git on repo.or.cz, while working
on builtin-rebase: I squash several patches using rebase -i before
sending a series, but it's nice to have the old long list of small
patches in case I would need them later.

What I did is to have a rebase-history branch: each commit in it is an
octopus merge:

- The first parent is the previous rebase-history ref

- The second is the old HEAD

- The third is the new HEAD

This way I can use git rebase -i without worrying about loosing history,
even if reflogs are not shared among machines.

(It may or may not be a good idea to do something like this in StGit, I
just though I share this idea here.)

On 2008-06-19 10:33:56 +0200, Miklos Vajna wrote:

On Thu, Jun 19, 2008 at 10:21:56AM +0200, Karl Hasselström
[off-list ref] wrote:

quoted

Catalin and I are tossing ideas around for how to represent the
history of an StGit patch stack (using a git commit for each log
entry). One complication is that we have to keep references to all
unapplied patches so that gc will leave them alone (and so that
they will get carried along during a pull, in the future). And the
number of unapplied patches is potentially large, so I thought
we'd be going to have to make a tree of "merge" commits to connect
them all up.

(What we'd really like, of course, is a way to refer to a set of
commits such that they are guaranteed to be reachable (in the gc
and pull sense), but not considered "parents".)

I had a similar problem in git/vmiklos.git on repo.or.cz, while
working on builtin-rebase: I squash several patches using rebase -i
before sending a series, but it's nice to have the old long list of
small patches in case I would need them later.

What I did is to have a rebase-history branch: each commit in it is
an octopus merge:

- The first parent is the previous rebase-history ref

- The second is the old HEAD

- The third is the new HEAD

This way I can use git rebase -i without worrying about loosing
history, even if reflogs are not shared among machines.

(It may or may not be a good idea to do something like this in
StGit, I just though I share this idea here.)

What you're describing is pretty much what we're thinking about doing
-- have a log branch where each commit contains enough metadata to
recreate the complete patch stack state at that point in time, and has
all the parents it needs to be safe from gc.

The particular problem I'm asking about here is that due to StGit's
concept of "unapplied" patches that are per definition not reachable
from the current branch head, a given log entry might have to keep an
unbounded number of commits from being gc'ed. Thus my question about
what would blow up if we were to make a commit with 50 parents. Or
100. Or 1000, if our users are crazy enough. (The alternative being,
of course, to make a tree of octopuses with a fixed maximum fan-out.)

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

On Thu, Jun 19, 2008 at 11:19:03AM +0200, Karl Hasselström [off-list ref] wrote:

What you're describing is pretty much what we're thinking about doing
-- have a log branch where each commit contains enough metadata to
recreate the complete patch stack state at that point in time, and has
all the parents it needs to be safe from gc.

The particular problem I'm asking about here is that due to StGit's
concept of "unapplied" patches that are per definition not reachable
from the current branch head, a given log entry might have to keep an
unbounded number of commits from being gc'ed. Thus my question about
what would blow up if we were to make a commit with 50 parents. Or
100. Or 1000, if our users are crazy enough. (The alternative being,
of course, to make a tree of octopuses with a fixed maximum fan-out.)

I may miss something, but you have (at least) two options to store
"patches".

You can store them as a blob, make a tree of them and make a commit in
the log branch point to the tree. This one has the advantage of being
able to do a 'git log' on a particular patch of the patch set.

The other one is to create n+1 trees (and commits, where the first
commit has no parent) for n patches, and point to the last commit from
the log branch.

On 2008-06-19 12:06:37 +0200, Miklos Vajna wrote:

You can store them as a blob, make a tree of them and make a commit
in the log branch point to the tree. This one has the advantage of
being able to do a 'git log' on a particular patch of the patch set.

If I don't store the pre or post tree in its entirety, I lose the
ability to do patch application by three-way merge. (The current StGit
design assumes that we can always make a three-way merge as a last
resort when applying patches. Basically, StGit is just a fancy way to
rebase.)

But yes, this is a viable idea. (Though once I have to store one of
the trees, I believe it's actually simpler and cheaper to just store
the other tree as well, instead of having to compute the diff and
store that in a blob.)

The other one is to create n+1 trees (and commits, where the first
commit has no parent) for n patches, and point to the last commit
from the log branch.

There's actually no point in making more than one commit. A tree can
easily hold a lot of sub-trees.

I have an existing implementation that stores the pre and post tree
for each patch, plus some metadata (message, author). The issue with
this format is that every time we write a new log entry (that is, for
every StGit command), we have to call git multiple times in order to
write several new trees and blobs.

StGit normally represents each patch by a commit object, so it should
be faster to simply write a single new commit to the log that has some
metadata in its commit message and just refers to all the patches'
commit objects (by having them as parents). Which is why I was
inquiring about the maximum number of parents of a commit object.

( Some background: At a given point in time, your StGit stack consists
  of a few applied patches, and a few unapplied patches. The applied
  patches are just a linear sequence of commits at the top of your
  current branch, so we can trivially save them all from the garbage
  collector by making the stack top a parent of our log commit. The
  unapplied patches, however, are commits that are not reachable from
  the stack top -- they can be "pushed" onto the stack by rebasing, at
  which point they become applied, but until then we can't make any
  assumptions about them being ancestors of anything. So a log commit
  potentially has to have _every_ unapplied patch as a parent. (If we
  know that the commit of an unapplied patch used to be applied, we
  know that it's reachable from previous log commits, but we don't
  always know that.) )

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle