# Re: Change set based shallow clone

2 messages from 2006-09-09 to 2006-09-09. Participants: linux@horizon.com, Marco Costalba.
Thread: https://gitlist.dev/t/5523

## linux@horizon.com, 2006-09-09 10:31

Subject: Re: Change set based shallow clone
Message-ID: <20060909103157.23388.qmail@science.horizon.com>
URL: https://gitlist.dev/e/20060909103157.23388.qmail%40science.horizon.com

```
> If the out of order revisions are a small amount of the total then
> could be possible to have something like
> 
> git rev-list --topo-order --with-appended-fixups HEAD
> 
> Where, while git-rev-list is working _whithout sorting the whole tree
> first_, when finds an out of order revision stores it in a fixup-list
> buffer and *at the end* of normal git-rev-lsit the buffer is flushed
> to receiver, so that the drawing logic does not change and the out of
> order revisions arrive at the end, already packed, sorted and prepared
> by git-rev-list.

I don't think I understand your proposal.  The problem arises when
git-rev-list finds a commit that it should have listed before something
that it has already output.

Just for example:

Commit D: Ancestor B
Commit B: Ancestor A
Commit C: Ancestor B

Commit C is the problem, because if git-rev-list has already output B,
there's no way to back up and insert it in the right place.

How is waiting to output the already-behind-schedule commit C going
to help anything?  The idea in gitk is to rewind the layout algorithm
to before B was added, insert C, and replay from there.  This is
most efficient if C is encountered as soon after its correct place
as possible.

```

## Marco Costalba, 2006-09-09 13:00

Subject: Re: Change set based shallow clone
Message-ID: <e5bfff550609090600k4e4b1ae0s1cbee5e3fa01cba@mail.gmail.com>
URL: https://gitlist.dev/e/e5bfff550609090600k4e4b1ae0s1cbee5e3fa01cba%40mail.gmail.com
In-Reply-To: <20060909103157.23388.qmail@science.horizon.com>

```
On 9 Sep 2006 06:31:57 -0400, linux@horizon.com <linux@horizon.com> wrote:
> > If the out of order revisions are a small amount of the total then
> > could be possible to have something like
> >
> > git rev-list --topo-order --with-appended-fixups HEAD
> >
> > Where, while git-rev-list is working _whithout sorting the whole tree
> > first_, when finds an out of order revision stores it in a fixup-list
> > buffer and *at the end* of normal git-rev-lsit the buffer is flushed
> > to receiver, so that the drawing logic does not change and the out of
> > order revisions arrive at the end, already packed, sorted and prepared
> > by git-rev-list.
>
> I don't think I understand your proposal.  The problem arises when
> git-rev-list finds a commit that it should have listed before something
> that it has already output.
>
> Just for example:
>
> Commit D: Ancestor B
> Commit B: Ancestor A
> Commit C: Ancestor B
>
> Commit C is the problem, because if git-rev-list has already output B,
> there's no way to back up and insert it in the right place.
>
> How is waiting to output the already-behind-schedule commit C going
> to help anything?

It helps in a number of ways from receiver point of view.

- Receiver doesn't need to keep a sorted list of loaded revisions.

- Receiver doesn't need to stop parsing input and redraw the graph in
the middle of the loading.

- Receiver doesn't need to  check for possible out of order commits
when loading data, but can be assured data that arrives is
--topo-order consistent (although my not be complete)

- Split the in order parsing code (performance critical and common
case) from fixup-code (run at the end and on a small set of commits).

- Much faster implementation because the sorting is done only in
git-rev-list and only once.

Following your example my suggestion was something like this:

Instead of:

git-rev-list HEAD

Commit D: Ancestor B
Commit B: Ancestor A
Commit C: Ancestor B
Commit A: Ancestor E
Commit E: Ancestor F
Commit F: Ancestor G
....
Commit V: Ancestor Z

git-rev-list --topo-order ----with-appended-fixups HEAD

sends something like:

Commit D: Ancestor B
Commit B: Ancestor A
Commit A: Ancestor E
Commit E: Ancestor F
Commit F: Ancestor G
....
Commit V: Ancestor Z
(* end of correct sorted commits and start of out of order commits*)
Commit C: Ancestor B
......
Commit  N: Ancestor M

So that receiver drawing code designed with working with --topo-order
kind output could as usual draws the graph until Commit V: Ancestor Z
(but without waiting for git-rev-list latency!!) and the new fixup
code could *at the end* loop across *already sorted* fixup set:

Commit C: Ancestor B
......
Commit  N: Ancestor M

and update the graph in one go. Of course some flag/syntax should be
introduced to trigger the end of sorted code and beginning of fixups
in git-rev-list output stream.

       Marco

```