{"thread":{"id":"62778","subject":"Histogram/patience diff matching lines with different counts","startedAt":"2025-01-09T21:31:56Z","lastAt":"2025-01-10T19:33:56Z","messageCount":2,"participants":["Martin von Zweigbergk","Jonathan Tan"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"510272","messageId":"CANiSa6jtwizbR4K-DqdKjVeZqAkbswnPXCBZZrrfNy2CKBEQVg@mail.gmail.com","threadId":"62778","inReplyTo":null,"subject":"Histogram/patience diff matching lines with different counts","fromName":"Martin von Zweigbergk","fromEmail":"martinvonz@gmail.com","sentAt":"2025-01-09T21:31:44Z","receivedAt":"2025-01-09T21:31:56Z","isPatch":false,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"Hi,\n\nLet's say you have this a file with this content:\n```\na\nb\nc\nd\ne\nf\n```\n\nThen you change it to this:\n```\na\nb2\nc\nd2\nc\ne2\nf\n```\n\nNote that most lines changed, but `c` remains unchanged but duplicated.\n\nNow `git diff --diff-algorithm=histogram` will show this diff:\n```\ndiff --git a/file b/file\nindex 0fdf397..7cfb042 100644\n--- a/file\n+++ b/file\n@@ -1,6 +1,7 @@\n a\n-b\n+b2\n c\n-d\n-e\n+d2\n+c\n+e2\n f\n```\n\nI'm surprised the first \"c\" line is considered unchanged. I thought\nhistogram diff was supposed to first match up unique lines between the\ntwo sides and then gradually try higher and higher counts if there\nwere no unique lines. In this case, only \"a\" and \"f\" have count 1\n(i.e. are unique) on both sides, so they would be matched up first.\nAfter that, \"c\" is unique on the left side but has a different count\n(namely 2) on the right side, so I would have thought that it should\nnot be considered matching. Does anyone know if it's implemented this\nway on purpose? Actually, I think I remember reading that Git falls\nback to Myers in some cases, so maybe that's what's going on here?\n\nAs some of you know, I work on the Jujutsu/jj VCS\n(https://github.com/jj-vcs/jj). We also use histogram diff (and only\nhistogram diff) and actually allowed matching up lines with different\ncounts a while ago, but I thought it seemed too arbitrary to line up\nthe first matches if there were different counts, so we changed that.\nThen we got a report from a user that Git behaves differently. See\nhttps://github.com/jj-vcs/jj/issues/761#issuecomment-2581219294 for\nmore details.\n\nThanks\n"},{"id":"510341","messageId":"20250110193353.493374-1-jonathantanmy@google.com","threadId":"62778","inReplyTo":"CANiSa6jtwizbR4K-DqdKjVeZqAkbswnPXCBZZrrfNy2CKBEQVg@mail.gmail.com","subject":"Re: Histogram/patience diff matching lines with different counts","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2025-01-10T19:33:53Z","receivedAt":"2025-01-10T19:33:56Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Martin von Zweigbergk <martinvonz@gmail.com> writes:\n> After that, \"c\" is unique on the left side but has a different count\n> (namely 2) on the right side, so I would have thought that it should\n> not be considered matching. Does anyone know if it's implemented this\n> way on purpose? \n\nThe purpose, if any, might be lost to history. The implementation of\nhistogram diff in Git seems to be a port from JGit (8c912eea94 (teach\n--histogram to diff, 2011-07-12)). The one in JGit [1] seems to be an\noriginal extension of patience diff by Shawn Pearce, who has passed away\na few years ago.\n\nThe class documentation comment in [1] does not give any rationale for\nor against rejecting lines with different counts, but quoting from it:\n\n> * By always selecting a LCS position with the lowest occurrence count, this\n> * algorithm behaves exactly like Bram Cohen's patience diff whenever there is a\n> * unique common element available between the two sequences. When no unique\n> * elements exist, the lowest occurrence element is chosen instead. This offers\n> * more readable diffs than simply falling back on the standard Myers' O(ND)\n> * algorithm would produce.\n\nI think it makes sense to reject lines with different counts, just like\nhow jj does it today, since the original motivation for low-occurring\nlines in both the patience diff and the histogram diff algorithms was\nto keep high-signal lines (i.e. not lines such as \"}\" and \"return;\") as\ncontext (instead of + or -), and if the count of a line differs, it is\nprobably not a high-signal line in the first place.\n\nI don't think it's worth changing it now, though, especially in Git. In\nthe scenario you describe, even if we change Git to reject lines with\ndifferent counts, failing to find a matching line means we fall back to\nMyers, which matches up the only \"c\" on the left and the first \"c\" on\nthe right anyway (so in the end, we still won't get the result that you\nmight want - reporting that the whole block has changed). (In jj's case,\nin which there is no fall back to Myers, I think it's reasonable to make\nhistogram diff work only with non-different counts, since the lack of\na fall back will indeed mean that we report that the whole block has\nchanged. This sounds like the \"highly ambiguous\" case that Bram Cohen,\nthe inventor of patience diff, mentions in [3].)\n\nTo further complicate things, in both JGit and Git, a line with\ndifferent counts is not considered matching only if the count in\n\"A\" (the left hand side) is greater than the count in \"B\" [2]. I can't\nthink of a reason for this asymmetry, and the class documentation\ncomment in [1] doesn't explain that either.\n\n[1] https://eclipse.googlesource.com/jgit/jgit/+/refs/heads/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java\n[2] https://eclipse.googlesource.com/jgit/jgit/+/refs/heads/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiffIndex.java#206\n[3] https://lore.kernel.org/git/alpine.DEB.1.00.0902052113590.7491@intel-tinevez-2-302/\n\n> As some of you know, I work on the Jujutsu/jj VCS\n> (https://github.com/jj-vcs/jj). We also use histogram diff (and only\n> histogram diff) and actually allowed matching up lines with different\n> counts a while ago, but I thought it seemed too arbitrary to line up\n> the first matches if there were different counts, so we changed that.\n> Then we got a report from a user that Git behaves differently. See\n> https://github.com/jj-vcs/jj/issues/761#issuecomment-2581219294 for\n> more details.\n> \n> Thanks\n\nI think that it is unavoidable that different VCSes may produce\ndifferent diffs. Even in Git itself, there are many options (including\nwhich algorithm to use) that can change the nature of the diff produced.\n"}]}