{"thread":{"id":"48928","subject":"FYI: histogram diff bug","startedAt":"2018-07-20T19:57:46Z","lastAt":"2018-07-20T19:57:46Z","messageCount":1,"participants":["Stefan Beller"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"353182","messageId":"CAGZ79kZYO6hHiAM8Sfp3J=VX11c=0-7YDSx3_EAKt5-uvvt-Ew@mail.gmail.com","threadId":"48928","inReplyTo":null,"subject":"FYI: histogram diff bug","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-20T19:57:31Z","receivedAt":"2018-07-20T19:57:46Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"  seq 1 100 >one\n  echo 99 > two\n  seq 1 2 98 >>two\n  git diff --no-index --histogram one two\n\nIn addition to the recent patches[1], I found another bug in the\nhistogram algorithm,\nwhich can be produced with the instructions given above. At least I\nthink it is a bug as\nthe diff looks terrible to me. (It is a correct diff, but the output\nis just bad.)\n\n[1] https://public-inbox.org/git/20180719221942.179565-1-sbeller@google.com/\n\nAnd I think the issue is in the algorithm, which is basically as follows:\n\n1) build up information about one side (\"scanA()\"), by putting each\n    line into a hashmap (and counting its occurrences, such that you\n    can make the histogram)\n\n2) \"find_LCS\" on the other side (B) by trying low occurrence lines\n  and seeing how long the common consequential string match is.\n  (I think this LCS refers to [2], not to be confused with [3])\n\n3) The whole mental model of the difference\n    between both sides now look like:\n\n      stuff before the LCS\n      LCS\n      stuff after the LCS\n\n    As the LCS has no output associated with it, just call recursively\n    do_histogram on the remainders before and after.\n\nThis is my rough understanding of the algorithm so far.\n    (I am unsure about the exact find_LCS part how and why to\n    pick certain candidates for finding the LCS).\n\nThe big issue however is the count of LCS, so far we assumed\nthere is only one! In the example given above there are many,\ni.e. lots of \"longest\" common continuous substrings of length 1.\nWe are unfortunate to pick \"99\" as the LCS and recurse before\nand after; the other LCSs would be a better pick.\n\nSo I think we would need to find \"all LCS\", which there can be\nmore than one at the same time, and then fill the gaps between\nthem using recursion.\nAs the order of LCSs can be different in the two sides,\nwe actually have to produce a diff of LCSs and those which are\nout of order need to be emitted as full edits (deletes or creates).\nIn the example above we'd want to have \"99\" to be a full create\nand delete instead of being *the* anchor; all other LCSs ought to\nbe anchors for the first (zero'th?) level of recursion.\n\nThis bug is also present in JGit which this algorithm was ported\nfrom, hence jgit-dev is cc'd (and furthers my suspicion that the\nissue is not in the port but in the algorithm itself).\n\n[2] https://en.wikipedia.org/wiki/Longest_common_substring_problem\n[3] https://en.wikipedia.org/wiki/Longest_common_subsequence_problem\n\nI'll think about this and see if I can fix it properly,\nThoughts or Opinions?\n\nStefan\n"}]}