fast-export: emit deletions first
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
@@ -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
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 aFix this by sorting deletions to come before other types of change.
Quoted 7 lines
Signed-off-by Raymond E. Pasco <[email protected]>---
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@@ -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;
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
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 aand 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."
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 aand 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
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).
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.
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