{"thread":{"id":"65442","subject":"[WIP PATCH] fast-export: emit deletions first","startedAt":"2026-04-06T06:36:33Z","lastAt":"2026-04-07T21:29:31Z","messageCount":8,"participants":["Raymond E. Pasco","Junio C Hamano","Jeff King","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"540967","messageId":"20260406063607.15353-1-ray@ameretat.dev","threadId":"65442","inReplyTo":null,"subject":"[WIP PATCH] fast-export: emit deletions first","fromName":"Raymond E. Pasco","fromEmail":"ray@ameretat.dev","sentAt":"2026-04-06T06:36:03Z","receivedAt":"2026-04-06T06:36:33Z","isPatch":true,"body":"fast-export chooses its output order by pathname, sorting longer\npaths earlier. However, this causes faulty output when the deleted\npath is a prefix of the added one. For example, deleting a file 'a' and\ncreating a file 'a/b' emits:\n\nfrom :prev_label\nM 100644 :blob_label a/b\nD a\n\nFix this by sorting deletions to come before other types of change.\n\nSigned-off-by: Raymond E. Pasco <ray@ameretat.dev>\n---\n\nThis is a quick and dirty fix for the bug. However, I do want to spend a\nlittle more time on it - it may be that we only want to reverse the sort\nwhen the deletion is specifically the prefix of some addition, and I\nwant to fence this off with new tests.\n\n builtin/fast-export.c | 6 ++++++\n 1 file changed, 6 insertions(+)\n\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex b90da5e616..82d73b2f43 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -354,6 +354,12 @@ static int depth_first(const void *a_, const void *b_)\n \tint len_a, len_b, len;\n \tint cmp;\n \n+\t/* emit deletions first */\n+\tint a_deletes = (a->status == DIFF_STATUS_DELETED);\n+\tint b_deletes = (b->status == DIFF_STATUS_DELETED);\n+\tif (a_deletes != b_deletes)\n+\t\treturn b_deletes - a_deletes;\n+\n \tname_a = a->one ? a->one->path : a->two->path;\n \tname_b = b->one ? b->one->path : b->two->path;\n \n-- \n2.54.0.rc0.605.g598a273b03.dirty\n\n"},{"id":"540986","messageId":"xmqqo6jwau34.fsf@gitster.g","threadId":"65442","inReplyTo":"20260406063607.15353-1-ray@ameretat.dev","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-04-06T17:15:27Z","receivedAt":"2026-04-06T17:15:30Z","isPatch":true,"body":"\"Raymond E. Pasco\" <ray@ameretat.dev> writes:\n\n> fast-export chooses its output order by pathname, sorting longer\n> paths earlier. However, this causes faulty output when the deleted\n> path is a prefix of the added one. For example, deleting a file 'a' and\n> creating a file 'a/b' emits:\n>\n> from :prev_label\n> M 100644 :blob_label a/b\n> D a\n>\n> Fix this by sorting deletions to come before other types of change.\n>\n> Signed-off-by: Raymond E. Pasco <ray@ameretat.dev>\n> ---\n>\n> This is a quick and dirty fix for the bug. However, I do want to spend a\n> little more time on it - it may be that we only want to reverse the sort\n> when the deletion is specifically the prefix of some addition, and I\n> want to fence this off with new tests.\n\nI recall doing something like this in \"git checkout\" and also \"git\nam\" to ensure that a thing deep in the hierarchy will not be\naffected by a D/F conflict at a shallower level, so I do not have\nobjection to this kind of change in principle.  I do not know if\ndepth_first() is the right place to make this decision or if the\nfunction should keep its name if it turns out to be the right place.\n\nIn any case, it is a bit surprising that fast-export survived this\nlong without having encountering the problem you are solving.  I\nwonder if fast-import handles such an output with some smart to\navoid the issue?\n\nThanks.\n\n>  builtin/fast-export.c | 6 ++++++\n>  1 file changed, 6 insertions(+)\n>\n> diff --git a/builtin/fast-export.c b/builtin/fast-export.c\n> index b90da5e616..82d73b2f43 100644\n> --- a/builtin/fast-export.c\n> +++ b/builtin/fast-export.c\n> @@ -354,6 +354,12 @@ static int depth_first(const void *a_, const void *b_)\n>  \tint len_a, len_b, len;\n>  \tint cmp;\n>  \n> +\t/* emit deletions first */\n> +\tint a_deletes = (a->status == DIFF_STATUS_DELETED);\n> +\tint b_deletes = (b->status == DIFF_STATUS_DELETED);\n> +\tif (a_deletes != b_deletes)\n> +\t\treturn b_deletes - a_deletes;\n> +\n>  \tname_a = a->one ? a->one->path : a->two->path;\n>  \tname_b = b->one ? b->one->path : b->two->path;\n"},{"id":"541023","messageId":"20260406212937.GA30202@coredump.intra.peff.net","threadId":"65442","inReplyTo":"xmqqo6jwau34.fsf@gitster.g","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-04-06T21:29:37Z","receivedAt":"2026-04-06T21:29:39Z","isPatch":true,"body":"On Mon, Apr 06, 2026 at 10:15:27AM -0700, Junio C Hamano wrote:\n\n> In any case, it is a bit surprising that fast-export survived this\n> long without having encountering the problem you are solving.  I\n> wonder if fast-import handles such an output with some smart to\n> avoid the issue?\n\nI think it has come up a few times, but we never actually applied a fix:\n\n  2015: https://lore.kernel.org/git/alpine.DEB.2.10.1508191532330.31851@buzzword-bingo.mit.edu/\n  2017: https://lore.kernel.org/git/1493079137-1838-1-git-send-email-miguel.torroja@gmail.com/\n  2023: https://lore.kernel.org/git/BBB169A5-0665-47C9-819B-6409A22AB699@lanl.gov/\n\nLooks like discussion got hung up on ordering other types of\nmodifications, like renames (which can actually have cycles). But I\ndon't see anything to contradict the view that putting deletions first\nsolves real problems and would not harm anything. And the answer to \"it\nhurts to fast-export with renames\" is probably \"don't do it\".\n\nIt's also possible that sorting should be the responsibility of the\nreceiver. I.e., should fast-import see:\n\n  M 100644 :blob_label a/b\n  D a\n\nand figure it out? Or maybe we want both (to help other consumers of\nfast-export, but also to help fast-import when consuming output of other\nsources).\n\n-Peff\n"},{"id":"541025","messageId":"CABPp-BHhXQc-s8rF1n+AQ0VodX2KuiahcAOcg2msR1eZrUSsCA@mail.gmail.com","threadId":"65442","inReplyTo":"20260406212937.GA30202@coredump.intra.peff.net","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2026-04-06T21:44:05Z","receivedAt":"2026-04-06T21:44:17Z","isPatch":true,"body":"On Mon, Apr 6, 2026 at 2:29 PM Jeff King <peff@peff.net> wrote:\n>\n> On Mon, Apr 06, 2026 at 10:15:27AM -0700, Junio C Hamano wrote:\n>\n> > In any case, it is a bit surprising that fast-export survived this\n> > long without having encountering the problem you are solving.  I\n> > wonder if fast-import handles such an output with some smart to\n> > avoid the issue?\n>\n> I think it has come up a few times, but we never actually applied a fix:\n>\n>   2015: https://lore.kernel.org/git/alpine.DEB.2.10.1508191532330.31851@buzzword-bingo.mit.edu/\n>   2017: https://lore.kernel.org/git/1493079137-1838-1-git-send-email-miguel.torroja@gmail.com/\n>   2023: https://lore.kernel.org/git/BBB169A5-0665-47C9-819B-6409A22AB699@lanl.gov/\n>\n> Looks like discussion got hung up on ordering other types of\n> modifications, like renames (which can actually have cycles). But I\n> don't see anything to contradict the view that putting deletions first\n> solves real problems and would not harm anything. And the answer to \"it\n> hurts to fast-export with renames\" is probably \"don't do it\".\n>\n> It's also possible that sorting should be the responsibility of the\n> receiver. I.e., should fast-import see:\n>\n>   M 100644 :blob_label a/b\n>   D a\n>\n> and figure it out? Or maybe we want both (to help other consumers of\n> fast-export, but also to help fast-import when consuming output of other\n> sources).\n\nWould re-ordering on fast-import's side introduce bugs or violate\nuser's assumptions?  Right now, fast-import has no check to prevent\nmore than one command for the same pathname being given, and has a\nlast-entry-wins ruling.  Thus filemodify PATH followed by filedelete\nPATH gives different results than reversing the order.  Most probably\nwouldn't care or want to ever do that, but I could see it as a way of\nallowing you to change your mind in the stream and override an earlier\ndirective you sent.\n\nFurther, from this paragraph:\n```\nZero or more `filemodify`, `filedelete`, `filecopy`, `filerename`,\n`filedeleteall` and `notemodify` commands\nmay be included to update the contents of the branch prior to\ncreating the commit.  These commands may be supplied in any order.\nHowever it is recommended that a `filedeleteall` command precede\nall `filemodify`, `filecopy`, `filerename` and `notemodify` commands in\nthe same commit, as `filedeleteall` wipes the branch clean (see below).\n```\nthe comment about ordering with `filedeleteall` does suggest that\nordering matters to fast-import and thus perhaps that we shouldn't be\nmessing with the order the stream-writer gave us.\n\nOn the creator side, I agree that fast-export would definitely want to\nsort its deletes before modifies to avoid D/F conflict issues.  That\ndoesn't help with renames, but I agree with you that the answer for\nrenames is probably \"then don't do that.\"\n"},{"id":"541028","messageId":"k3qg4jodn425cjvorvdl4j24ik7c4jwmwudwsowe4doth7devn@f5xbrskansmj","threadId":"65442","inReplyTo":"xmqqo6jwau34.fsf@gitster.g","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Raymond E. Pasco","fromEmail":"ray@ameretat.dev","sentAt":"2026-04-07T01:12:19Z","receivedAt":"2026-04-07T01:12:30Z","isPatch":true,"body":"On 26/04/06 10:15AM, Junio C Hamano wrote:\n> In any case, it is a bit surprising that fast-export survived this\n> long without having encountering the problem you are solving.  I\n> wonder if fast-import handles such an output with some smart to\n> avoid the issue?\n\nI was surprised too. The case where this was encountered was a repo\nthat had a directory symlink, and promoted it to a real directory,\nbut the symlink turned out to be a red herring, it's purely path\nprefixes.\n\nfast-import itself just does things in the order given; you might\nrename with copy followed by delete (though 'R'ename was added at\nsome point). It's on the stream author for this to make sense;\nfast-export doesn't use this pattern.\n"},{"id":"541034","messageId":"20260407042432.GA627864@coredump.intra.peff.net","threadId":"65442","inReplyTo":"CABPp-BHhXQc-s8rF1n+AQ0VodX2KuiahcAOcg2msR1eZrUSsCA@mail.gmail.com","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-04-07T04:24:32Z","receivedAt":"2026-04-07T04:24:34Z","isPatch":true,"body":"On Mon, Apr 06, 2026 at 02:44:05PM -0700, Elijah Newren wrote:\n\n> > It's also possible that sorting should be the responsibility of the\n> > receiver. I.e., should fast-import see:\n> >\n> >   M 100644 :blob_label a/b\n> >   D a\n> >\n> > and figure it out? Or maybe we want both (to help other consumers of\n> > fast-export, but also to help fast-import when consuming output of other\n> > sources).\n> \n> Would re-ordering on fast-import's side introduce bugs or violate\n> user's assumptions?  Right now, fast-import has no check to prevent\n> more than one command for the same pathname being given, and has a\n> last-entry-wins ruling.  Thus filemodify PATH followed by filedelete\n> PATH gives different results than reversing the order.  Most probably\n> wouldn't care or want to ever do that, but I could see it as a way of\n> allowing you to change your mind in the stream and override an earlier\n> directive you sent.\n\nHmm, good point. It probably is better to leave the reading side as-is,\nthen, to be on the safe side.\n\n-Peff\n"},{"id":"541035","messageId":"20260407042624.GB627864@coredump.intra.peff.net","threadId":"65442","inReplyTo":"k3qg4jodn425cjvorvdl4j24ik7c4jwmwudwsowe4doth7devn@f5xbrskansmj","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-04-07T04:26:24Z","receivedAt":"2026-04-07T04:26:26Z","isPatch":true,"body":"On Mon, Apr 06, 2026 at 09:12:19PM -0400, Raymond E. Pasco wrote:\n\n> On 26/04/06 10:15AM, Junio C Hamano wrote:\n> > In any case, it is a bit surprising that fast-export survived this\n> > long without having encountering the problem you are solving.  I\n> > wonder if fast-import handles such an output with some smart to\n> > avoid the issue?\n> \n> I was surprised too. The case where this was encountered was a repo\n> that had a directory symlink, and promoted it to a real directory,\n> but the symlink turned out to be a red herring, it's purely path\n> prefixes.\n\nThat's the original case from 2015, too. Which I guess is not too\nsurprising, since it's probably a more common conversion than a true\ndirectory-into-file. There was a patch with a test provided in one of\nthe threads I linked earlier, in case that helps, but it is pretty easy\nto write a new one.\n\n-Peff\n"},{"id":"541094","messageId":"qrxjw6qtagcfcwbzqjkoy37nu22no6kteskge3lpoyxmumzfqv@35hyc7dys63c","threadId":"65442","inReplyTo":"CABPp-BHhXQc-s8rF1n+AQ0VodX2KuiahcAOcg2msR1eZrUSsCA@mail.gmail.com","subject":"Re: [WIP PATCH] fast-export: emit deletions first","fromName":"Raymond E. Pasco","fromEmail":"ray@ameretat.dev","sentAt":"2026-04-07T21:28:46Z","receivedAt":"2026-04-07T21:29:31Z","isPatch":true,"body":"On 26/04/06 02:44PM, Elijah Newren wrote:\n> On the creator side, I agree that fast-export would definitely want to\n> sort its deletes before modifies to avoid D/F conflict issues.  That\n> doesn't help with renames, but I agree with you that the answer for\n> renames is probably \"then don't do that.\"\n\nfast-export does force 'R'enames (of a to b) to appear after other lines\noperating on a, 4ce6fb80 (fast-export: ensure that a renamed file is\nprinted after all references).\n\nI think all Ds first works for the patterns fast-export actually uses.\nAccording to a comment, the reason it's sorting by depth at all is a\nsubset of this, to put D a/b before M 120000 a, or similar.\n\nThe additional roundtripping tests I'm writing should handle all this, I\nhope. I think now is a good time to get round-trips down, since people\nmight potentially use fast-export | fast-import to switch hash functions\n(when commit and tag resigning are fully in fast-import).\n"}]}