From: Junio C Hamano <hidden> Date: 2016-06-15 23:08:39
Jeff King [off-list ref] writes:
I don't know how the client invoked git, but we can guess what happened
and simulate with:
git tag shallow ecd7ea6033fe8a05d5c21f3a54355fded6942659
git tag old 067f265bb512c95b22b83ccd121b9facbddcf6b1
git tag new d7a6d9295d718c6015be496880f1a293bdd89185
git clone --no-local --bare --branch=shallow --depth=1 . clone.git
cd clone.git
git fetch origin old:refs/tags/old
git fetch origin new:refs/tags/new
Of the two follow-up fetches in the clone, the first is reasonably fast
(it just grabs a few new commits on top of the shallow base), but the
second is expensive (it grabs the merge which pulls in the whole
history). If we add "--depth=1" to each of those fetches, everything
remains fast.
Is this user error to call "git fetch" without "--depth" in the
subsequent cases? Or should git remember that we are in a shallow repo,
and presume that the user by default wants to keep things shallow?
Hmph, you shouldn't, and I somehow thought that you do not, have to
explicitly say things like "--deepen" to break the original
shallowness, but your example illustrates that the logic to do so is
not well thought out. A new side branch will prevent you from
hitting an already-known shallow cut-off and traverse down to the
root.
Giving a random "depth" in subsequent fetch would however not work
very well, I suspect, as that is very prone to make the part of the
history the user originally obtained, and presumably used to build
her own history, into an island that is unconnected to the updated
tip of the history.
I also do not offhand think of a good way to use the topology or
timestamp to figure out the best "depth" to truncate the side branch
at. The server side may be able to figure out that things before 'F'
in your picture is not relevant for a client that has the shallow
cut-off at 067f265, but the side branch can be forked arbitrarily
long in the past, or it may not even share the ancient part of the
history and has its own root commit.
On Tue, Mar 8, 2016 at 6:47 AM, Junio C Hamano [off-list ref] wrote:
Jeff King [off-list ref] writes:
quoted
I don't know how the client invoked git, but we can guess what happened
and simulate with:
git tag shallow ecd7ea6033fe8a05d5c21f3a54355fded6942659
git tag old 067f265bb512c95b22b83ccd121b9facbddcf6b1
git tag new d7a6d9295d718c6015be496880f1a293bdd89185
git clone --no-local --bare --branch=shallow --depth=1 . clone.git
cd clone.git
git fetch origin old:refs/tags/old
git fetch origin new:refs/tags/new
Of the two follow-up fetches in the clone, the first is reasonably fast
(it just grabs a few new commits on top of the shallow base), but the
second is expensive (it grabs the merge which pulls in the whole
history). If we add "--depth=1" to each of those fetches, everything
remains fast.
Is this user error to call "git fetch" without "--depth" in the
subsequent cases? Or should git remember that we are in a shallow repo,
and presume that the user by default wants to keep things shallow?
Hmph, you shouldn't, and I somehow thought that you do not, have to
explicitly say things like "--deepen" to break the original
shallowness, but your example illustrates that the logic to do so is
not well thought out. A new side branch will prevent you from
hitting an already-known shallow cut-off and traverse down to the
root.
Yep. It "works" by design.
Giving a random "depth" in subsequent fetch would however not work
very well, I suspect, as that is very prone to make the part of the
history the user originally obtained, and presumably used to build
her own history, into an island that is unconnected to the updated
tip of the history.
The new --deepen, --shallow-since and --shallow-exclude should be
better in this aspect and we can send them all the time without
affecting original cut points. Well, deepen can't be used here because
it needs shallow cut points as anchor in the first place.
I also do not offhand think of a good way to use the topology or
timestamp to figure out the best "depth" to truncate the side branch
at. The server side may be able to figure out that things before 'F'
in your picture is not relevant for a client that has the shallow
cut-off at 067f265, but the side branch can be forked arbitrarily
long in the past, or it may not even share the ancient part of the
history and has its own root commit.
If a shallow point can reach root without seeing another shallow
point, we can mark all reachable commits from it shallow. If it sees
another shallow point, maybe we can mark at the merge point of them..
We can also send "here is --depth=10, but only apply it on new refs".
That should mitigate the problem a bit. But I'm not sure if I can
solve it completely.
--
Duy
From: Jeff King <hidden> Date: 2016-06-15 23:08:39
On Mon, Mar 07, 2016 at 03:47:53PM -0800, Junio C Hamano wrote:
quoted
Is this user error to call "git fetch" without "--depth" in the
subsequent cases? Or should git remember that we are in a shallow repo,
and presume that the user by default wants to keep things shallow?
Hmph, you shouldn't, and I somehow thought that you do not, have to
explicitly say things like "--deepen" to break the original
shallowness, but your example illustrates that the logic to do so is
not well thought out. A new side branch will prevent you from
hitting an already-known shallow cut-off and traverse down to the
root.
Giving a random "depth" in subsequent fetch would however not work
very well, I suspect, as that is very prone to make the part of the
history the user originally obtained, and presumably used to build
her own history, into an island that is unconnected to the updated
tip of the history.
Yeah, if we just recorded the original "--depth=1", each fetch would
make its own little island. Eventually your "shallow" file would bloat.
I'm not sure what that would do for the performance of subsequent
operations.
I also do not offhand think of a good way to use the topology or
timestamp to figure out the best "depth" to truncate the side branch
at. The server side may be able to figure out that things before 'F'
in your picture is not relevant for a client that has the shallow
cut-off at 067f265, but the side branch can be forked arbitrarily
long in the past, or it may not even share the ancient part of the
history and has its own root commit.
Right. I think conceptually that we want a graph cut, across all
branches. But you can't compute that cut at the time of the original
shallow clone, as we might not even have the side branches yet. So it
has to be computed at the time of the subsequent fetch.
You could make an arbitrary cut across all branches based on the
timestamp of the --shallow bottom. That would create new shallow bottoms
on any parallel lines of development that are brought in, from "around
the same time". But I'm uncomfortable relying on timestamps, and I
suspect there are some pretty bad corner cases with skew.
What if we instead marked the parent of a shallow commit UNINTERESTING?
Something like:
In this case it means we pull in all of that side branch, down to the
fork point. If it went back to ancient history (or even had its own root
commit), then so be it; that's what the user asked for. But I think
this would cover the common case of people shallow-cloning and fetching
a normal workflow.
There are two problems, though:
1. We use UNINTERESTING for two things in pack-objects: to avoid
sending the commits, but also to assume that the user has the
objects, for making thin-pack deltas.
We want only the former, but not the latter (if you apply my patch
and try a fetch, you'll see that the client is missing bases from
the resulting pack).
2. We've effectively re-shallowed the client at the fork point. We
have to tell them that somehow, or they're going to complain that
we didn't send them all of the objects.
So I think the solution to both is that we need to do a _separate_
traversal with all of the positive tips we're going to send, and the
parents of any shallow commits the client has, to find their fork points
(i.e., merge bases). And then we add those fork points to the shallow
list (grafting out their parents), and communicate them to the client to
add to its shallow setup.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 23:08:39
On Tue, Mar 08, 2016 at 07:53:35AM +0700, Duy Nguyen wrote:
quoted
I also do not offhand think of a good way to use the topology or
timestamp to figure out the best "depth" to truncate the side branch
at. The server side may be able to figure out that things before 'F'
in your picture is not relevant for a client that has the shallow
cut-off at 067f265, but the side branch can be forked arbitrarily
long in the past, or it may not even share the ancient part of the
history and has its own root commit.
If a shallow point can reach root without seeing another shallow
point, we can mark all reachable commits from it shallow. If it sees
another shallow point, maybe we can mark at the merge point of them..
Hmph, I read your email before sending my other response, but somehow I
didn't quite understand what you were saying. Now after having written
my long-winded other one, I think I just re-invented the same thing you
are proposing here. ;)
We can also send "here is --depth=10, but only apply it on new refs".
That should mitigate the problem a bit. But I'm not sure if I can
solve it completely.
I think "new refs" isn't something we can rely on. For example, in this
case the old history may have been merged in and the ref deleted before
the fetcher shows up.
-Peff
On Tue, Mar 8, 2016 at 7:14 PM, Jeff King [off-list ref] wrote:
...
So I think the solution to both is that we need to do a _separate_
traversal with all of the positive tips we're going to send, and the
parents of any shallow commits the client has, to find their fork points
(i.e., merge bases). And then we add those fork points to the shallow
list (grafting out their parents), and communicate them to the client to
add to its shallow setup.
Good news. We have the mechanism in place, I think.
get_shallow_commits_by_rev_list() (from 'pu') will produce the right
shallow points for sending back to the client if you pass "--not
<current shallow points>" to it. It's meant to be used for
--shallow-exclude and --shallow-since, but if neither is given (nor
--depth) I guess we can run it with current shallow points. I wonder
if we can detect some common cases and avoid commit traversing this
way though.
--
Duy
From: Jeff King <hidden> Date: 2016-06-15 23:08:39
On Tue, Mar 08, 2016 at 07:33:43PM +0700, Duy Nguyen wrote:
On Tue, Mar 8, 2016 at 7:14 PM, Jeff King [off-list ref] wrote:
quoted
...
So I think the solution to both is that we need to do a _separate_
traversal with all of the positive tips we're going to send, and the
parents of any shallow commits the client has, to find their fork points
(i.e., merge bases). And then we add those fork points to the shallow
list (grafting out their parents), and communicate them to the client to
add to its shallow setup.
Good news. We have the mechanism in place, I think.
get_shallow_commits_by_rev_list() (from 'pu') will produce the right
shallow points for sending back to the client if you pass "--not
<current shallow points>" to it. It's meant to be used for
--shallow-exclude and --shallow-since, but if neither is given (nor
--depth) I guess we can run it with current shallow points. I wonder
if we can detect some common cases and avoid commit traversing this
way though.
I tried that, but I couldn't quite get it to work. I don't think we need
any special rev-list, though; we can just find the boundary points of
that traversal and mark them as new shallows.
I think this patch does roughly the right thing:
Though I think perhaps we should also be adding those BOUNDARY commits
to the "shallows" object array? This works because the "--shallow" we
pass to pack-objects comes by reading the commit-graft list manipulated
by register_shallow(), so I'm not sure if it matters.
_But_, the client is not prepared to handle this. We send "shallow"
lines that it is not expecting, since it did not ask for any depth. So I
think this logic would have to kick in only when the client tells us to
do so.
I hacked around it with:
@@ -830,6 +830,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,sort_ref_list(&ref,ref_compare_name);qsort(sought,nr_sought,sizeof(*sought),cmp_ref_by_name);+args->deepen=1;if((args->depth>0||is_repository_shallow())&&!server_supports("shallow"))die("Server does not support shallow clients");
and confirmed that the resulting "git fetch origin new" from my earlier
example does a sane thing.
So what next? I think there's some protocol work here, and I think the
overall design of that needs to be considered alongside the other
"deepen" options your topic in pu adds (and of which I'm largely
ignorant). Does this sufficiently interest you to pick up and roll into
your other shallow work?
-Peff
From: Jeff King <hidden> Date: 2016-06-15 23:08:39
On Tue, Mar 08, 2016 at 08:25:24AM -0500, Jeff King wrote:
quoted
Good news. We have the mechanism in place, I think.
get_shallow_commits_by_rev_list() (from 'pu') will produce the right
shallow points for sending back to the client if you pass "--not
<current shallow points>" to it. It's meant to be used for
--shallow-exclude and --shallow-since, but if neither is given (nor
--depth) I guess we can run it with current shallow points. I wonder
if we can detect some common cases and avoid commit traversing this
way though.
I tried that, but I couldn't quite get it to work. I don't think we need
any special rev-list, though; we can just find the boundary points of
that traversal and mark them as new shallows.
By the way, I found a bug during my initial attempts with
get_shallow_commits_by_rev_list(). One of the loops uses "p" to traverse
a linked list, and then re-uses "p" again for another list traversal
inside the body of the loop. When the inner loop finishes, "p" is
left as NULL, and then the outer loop tries to access "p->next", which
segfaults.
I _think_ this is just a mistaken re-use of the variable, and can be
fixed with a new iteration variable for the inner loop, like:
On Tue, Mar 8, 2016 at 8:30 PM, Jeff King [off-list ref] wrote:
On Tue, Mar 08, 2016 at 08:25:24AM -0500, Jeff King wrote:
quoted
quoted
Good news. We have the mechanism in place, I think.
get_shallow_commits_by_rev_list() (from 'pu') will produce the right
shallow points for sending back to the client if you pass "--not
<current shallow points>" to it. It's meant to be used for
--shallow-exclude and --shallow-since, but if neither is given (nor
--depth) I guess we can run it with current shallow points. I wonder
if we can detect some common cases and avoid commit traversing this
way though.
I tried that, but I couldn't quite get it to work. I don't think we need
any special rev-list, though; we can just find the boundary points of
that traversal and mark them as new shallows.
By the way, I found a bug during my initial attempts with
get_shallow_commits_by_rev_list().
Hehe. Thanks. Will check why tests missed it and reroll with Ramsay's
fix once -rc period is over.
--
Duy
Nice. I didn't know about --boundary. But will it work correctly in
this case?
--- B ---- C ---- F
/ /
--- D ---- E ---- G
C and D will be current shallow cut points. People "want" F and G.
"rev-list --boundary F G ^C ^D" would mark E as boundary/shallow too,
correct? If so the history from G will be one depth short on a normal
fetch.
+ for (i = 0; i < want_obj.nr; i++) {
+ struct object *o = want_obj.objects[i].item;
+ argv_array_push(&av, oid_to_hex(&o->oid));
}
+ for (i = 0; i < shallows.nr; i++) {
+ struct object *o = shallows.objects[i].item;
+ argv_array_pushf(&av, "^%s", oid_to_hex(&o->oid));
+ }
+
+ init_revisions(&revs, NULL);
+ setup_revisions(av.argc, av.argv, &revs, NULL);
+ if (prepare_revision_walk(&revs))
+ die("revision walk setup failed");
+
+ while ((c = get_revision(&revs))) {
+ if (!(c->object.flags & BOUNDARY))
+ continue;
+ register_shallow(c->object.oid.hash);
+ packet_write(1, "shallow %s",
+ oid_to_hex(&c->object.oid));
+ }
...
_But_, the client is not prepared to handle this. We send "shallow"
lines that it is not expecting, since it did not ask for any depth. So I
think this logic would have to kick in only when the client tells us to
do so.
Urgh.. not good. Perhaps a new extension to let the server know the
client can handle spontaneous "deepen" commands and only activate new
mode when the extension is present?
So what next? I think there's some protocol work here, and I think the
overall design of that needs to be considered alongside the other
"deepen" options your topic in pu adds (and of which I'm largely
ignorant). Does this sufficiently interest you to pick up and roll into
your other shallow work?
I can pick it up if you are busy with other stuff. But I'm also having
a couple other topics at the moment, so it may not progress very fast.
--
Duy
Nice. I didn't know about --boundary. But will it work correctly in
this case?
--- B ---- C ---- F
/ /
--- D ---- E ---- G
C and D will be current shallow cut points. People "want" F and G.
"rev-list --boundary F G ^C ^D" would mark E as boundary/shallow too,
correct? If so the history from G will be one depth short on a normal
fetch.
IMHO, that is the right thing. They asked for "C" as a shallow cut-off
point, so anything that is a parent of "C" should be omitted as shallow,
too. It has nothing to do with the numeric depth, which was just the
starting point for generating the shallow cutoffs.
That's just my mental model, though. I admit I don't actually use
shallow clones myself, and maybe people would expect something else.
quoted
_But_, the client is not prepared to handle this. We send "shallow"
lines that it is not expecting, since it did not ask for any depth. So I
think this logic would have to kick in only when the client tells us to
do so.
Urgh.. not good. Perhaps a new extension to let the server know the
client can handle spontaneous "deepen" commands and only activate new
mode when the extension is present?
Yeah, we definitely need an extension. I'm not sure if the extension
should be "I know about spontaneous shallow/deepen responses; it's OK to
send them to me" or "I want you to include the shallow points I send as
boundary cutoffs for further shallow-ing of newly fetched history".
They amount to the same thing when implementing _this_ feature, but the
latter leaves us room in the future for a client to say "sure, I
understand your spontaneous responses, but I explicitly _don't_ want you
to do the boundary computation". I don't know if that is useful or not,
but it might not hurt to have later on (and by adding it now, it "just
works" later on with older servers/clients).
quoted
So what next? I think there's some protocol work here, and I think the
overall design of that needs to be considered alongside the other
"deepen" options your topic in pu adds (and of which I'm largely
ignorant). Does this sufficiently interest you to pick up and roll into
your other shallow work?
I can pick it up if you are busy with other stuff. But I'm also having
a couple other topics at the moment, so it may not progress very fast.
Thanks. I don't think it is too urgent; it has been that way for a
while. I certainly have plenty of other things to work on, but mostly I
just feel a bit out of my depth on the shallow stuff. I haven't given it
any real thought, and you obviously have.
-Peff