Skip to contentSkip to conversation

fast-export: emit deletions first

PATCH In review Raymond E. Pasco 4 participants 8 messages Apr 6 – Apr 7

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 fast-export: emit deletions first

fast-export chooses its output order by pathname, sorting longer paths earlier. However, this causes faulty output when the deleted path is a prefix of the added one. For example, deleting a file 'a' and creating a file 'a/b' emits:

from :prev_label
M 100644 :blob_label a/b
D a

Fix this by sorting deletions to come before other types of change.

---

This is a quick and dirty fix for the bug. However, I do want to spend a little more time on it - it may be that we only want to reverse the sort when the deletion is specifically the prefix of some addition, and I want to fence this off with new tests.

 builtin/fast-export.c | 6 ++++++
 1 file changed, 6 insertions(+)
builtin/fast-export.c +6 -0
index b90da5e616..82d73b2f43 100644
@@ -354,6 +354,12 @@ static int depth_first(const void *a_, const void *b_)
 	int len_a, len_b, len;
 	int cmp;
 
+	/* emit deletions first */
+	int a_deletes = (a->status == DIFF_STATUS_DELETED);
+	int b_deletes = (b->status == DIFF_STATUS_DELETED);
+	if (a_deletes != b_deletes)
+		return b_deletes - a_deletes;
+
 	name_a = a->one ? a->one->path : a->two->path;
 	name_b = b->one ? b->one->path : b->two->path;
 
Signature · 1 line
2.54.0.rc0.605.g598a273b03.dirty
#1 lore raw
Quoted 11 lines · Raymond E. Pasco

fast-export chooses its output order by pathname, sorting longer paths earlier. However, this causes faulty output when the deleted path is a prefix of the added one. For example, deleting a file 'a' and creating a file 'a/b' emits:

from :prev_label
M 100644 :blob_label a/b
D a

Fix this by sorting deletions to come before other types of change.

Quoted 7 lines

---

This is a quick and dirty fix for the bug. However, I do want to spend a little more time on it - it may be that we only want to reverse the sort when the deletion is specifically the prefix of some addition, and I want to fence this off with new tests.

I recall doing something like this in "git checkout" and also "git am" to ensure that a thing deep in the hierarchy will not be affected by a D/F conflict at a shallower level, so I do not have objection to this kind of change in principle. I do not know if depth_first() is the right place to make this decision or if the function should keep its name if it turns out to be the right place.

In any case, it is a bit surprising that fast-export survived this long without having encountering the problem you are solving. I wonder if fast-import handles such an output with some smart to avoid the issue?

Thanks.

Quoted 19 lines
 builtin/fast-export.c | 6 ++++++
 1 file changed, 6 insertions(+)
builtin/fast-export.c +6 -0
index b90da5e616..82d73b2f43 100644
@@ -354,6 +354,12 @@ static int depth_first(const void *a_, const void *b_)
 	int len_a, len_b, len;
 	int cmp;
 
+	/* emit deletions first */
+	int a_deletes = (a->status == DIFF_STATUS_DELETED);
+	int b_deletes = (b->status == DIFF_STATUS_DELETED);
+	if (a_deletes != b_deletes)
+		return b_deletes - a_deletes;
+
 	name_a = a->one ? a->one->path : a->two->path;
 	name_b = b->one ? b->one->path : b->two->path;
#2 lore raw
Quoted 4 lines · Junio C Hamano

In any case, it is a bit surprising that fast-export survived this long without having encountering the problem you are solving. I wonder if fast-import handles such an output with some smart to avoid the issue?

I think it has come up a few times, but we never actually applied a fix:

2015: https://lore.kernel.org/git/[email protected]/
2017: https://lore.kernel.org/git/[email protected]/
2023: https://lore.kernel.org/git/[email protected]/

Looks like discussion got hung up on ordering other types of modifications, like renames (which can actually have cycles). But I don't see anything to contradict the view that putting deletions first solves real problems and would not harm anything. And the answer to "it hurts to fast-export with renames" is probably "don't do it".

It's also possible that sorting should be the responsibility of the receiver. I.e., should fast-import see:

M 100644 :blob_label a/b
D a

and figure it out? Or maybe we want both (to help other consumers of fast-export, but also to help fast-import when consuming output of other sources).

-Peff

#3 lore raw
Quoted 23 lines · Jeff King
Quoted 4 lines · Junio C Hamano

In any case, it is a bit surprising that fast-export survived this long without having encountering the problem you are solving. I wonder if fast-import handles such an output with some smart to avoid the issue?

I think it has come up a few times, but we never actually applied a fix:

2015: https://lore.kernel.org/git/[email protected]/
2017: https://lore.kernel.org/git/[email protected]/
2023: https://lore.kernel.org/git/[email protected]/

Looks like discussion got hung up on ordering other types of modifications, like renames (which can actually have cycles). But I don't see anything to contradict the view that putting deletions first solves real problems and would not harm anything. And the answer to "it hurts to fast-export with renames" is probably "don't do it".

It's also possible that sorting should be the responsibility of the receiver. I.e., should fast-import see:

Quoted 6 lines

M 100644 :blob_label a/b
D a

and figure it out? Or maybe we want both (to help other consumers of fast-export, but also to help fast-import when consuming output of other sources).

Would re-ordering on fast-import's side introduce bugs or violate user's assumptions? Right now, fast-import has no check to prevent more than one command for the same pathname being given, and has a last-entry-wins ruling. Thus filemodify PATH followed by filedelete PATH gives different results than reversing the order. Most probably wouldn't care or want to ever do that, but I could see it as a way of allowing you to change your mind in the stream and override an earlier directive you sent.

Further, from this paragraph:

```
Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`,
`filedeleteall` and `notemodify` commands
may be included to update the contents of the branch prior to
creating the commit.  These commands may be supplied in any order.
However it is recommended that a `filedeleteall` command precede
all `filemodify`, `filecopy`, `filerename` and `notemodify` commands in
the same commit, as `filedeleteall` wipes the branch clean (see below).
```

the comment about ordering with filedeleteall does suggest that ordering matters to fast-import and thus perhaps that we shouldn't be messing with the order the stream-writer gave us.

On the creator side, I agree that fast-export would definitely want to sort its deletes before modifies to avoid D/F conflict issues. That doesn't help with renames, but I agree with you that the answer for renames is probably "then don't do that."

#4 lore raw
Quoted 10 lines · Elijah Newren
Quoted 9 lines

It's also possible that sorting should be the responsibility of the receiver. I.e., should fast-import see:

M 100644 :blob_label a/b
D a

and figure it out? Or maybe we want both (to help other consumers of fast-export, but also to help fast-import when consuming output of other sources).

Quoted 8 lines

Would re-ordering on fast-import's side introduce bugs or violate user's assumptions? Right now, fast-import has no check to prevent more than one command for the same pathname being given, and has a last-entry-wins ruling. Thus filemodify PATH followed by filedelete PATH gives different results than reversing the order. Most probably wouldn't care or want to ever do that, but I could see it as a way of allowing you to change your mind in the stream and override an earlier directive you sent.

Hmm, good point. It probably is better to leave the reading side as-is, then, to be on the safe side.

-Peff

#5 lore raw
In reply to Elijah Newren
Quoted 4 lines · Elijah Newren

On the creator side, I agree that fast-export would definitely want to sort its deletes before modifies to avoid D/F conflict issues. That doesn't help with renames, but I agree with you that the answer for renames is probably "then don't do that."

fast-export does force 'R'enames (of a to b) to appear after other lines operating on a, 4ce6fb80 (fast-export: ensure that a renamed file is printed after all references).

I think all Ds first works for the patterns fast-export actually uses. According to a comment, the reason it's sorting by depth at all is a subset of this, to put D a/b before M 120000 a, or similar.

The additional roundtripping tests I'm writing should handle all this, I hope. I think now is a good time to get round-trips down, since people might potentially use fast-export | fast-import to switch hash functions (when commit and tag resigning are fully in fast-import).

#6 lore raw
In reply to Junio C Hamano
Quoted 4 lines · Junio C Hamano

In any case, it is a bit surprising that fast-export survived this long without having encountering the problem you are solving. I wonder if fast-import handles such an output with some smart to avoid the issue?

I was surprised too. The case where this was encountered was a repo that had a directory symlink, and promoted it to a real directory, but the symlink turned out to be a red herring, it's purely path prefixes.

fast-import itself just does things in the order given; you might rename with copy followed by delete (though 'R'ename was added at some point). It's on the stream author for this to make sense; fast-export doesn't use this pattern.

#7 lore raw
Quoted 10 lines · Raymond E. Pasco
Quoted 4 lines · Junio C Hamano

In any case, it is a bit surprising that fast-export survived this long without having encountering the problem you are solving. I wonder if fast-import handles such an output with some smart to avoid the issue?

I was surprised too. The case where this was encountered was a repo that had a directory symlink, and promoted it to a real directory, but the symlink turned out to be a red herring, it's purely path prefixes.

That's the original case from 2015, too. Which I guess is not too surprising, since it's probably a more common conversion than a true directory-into-file. There was a patch with a test provided in one of the threads I linked earlier, in case that helps, but it is pretty easy to write a new one.

-Peff