{"thread":{"id":"32322","subject":"Fwd: possible Improving diff algoritm","startedAt":"2012-12-12T15:03:08Z","lastAt":"2012-12-15T12:16:27Z","messageCount":18,"participants":["Kevin","Junio C Hamano","Brian J. Murrell","Morten Welinder","Andrew Ardill","Javier Domingo","Michael Haggerty","Geert Bosch","Bernhard R. Link"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"204748","messageId":"CAO54GHD3C2RKUvE5jK_XOCVbbDuE_c5xfe28rOL+DaE5anL-Wg@mail.gmail.com","threadId":"32322","inReplyTo":"CAO54GHC4AXQO1MbU2qXMdcDO5mtUFhrXfXND5evc93kQhNfCrw@mail.gmail.com","subject":"Fwd: possible Improving diff algoritm","fromName":"Kevin","fromEmail":"ikke@ikke.info","sentAt":"2012-12-12T15:03:08Z","receivedAt":"2012-12-12T15:03:08Z","isPatch":false,"sender":{"key":"ikke@ikke.info","avatar":"https://gravatar.com/avatar/60a0d08eeccb16914fdbfc7f3441548dc827dc436d5c6900ec6600e274e53c5b?d=mp&s=160"},"body":"Regularly I notice that the diffs that are provided (through diff, or\nadd -p) tend to disconnect changes that belong to each other and\nreport lines being changed that are not changed.\n\nAn example for this is:\n\n /**\n+ * Default parent\n+ *\n+ * @var int\n+ * @access protected\n+ * @index\n+ */\n+ protected $defaultParent;\n+\n+ /**\n\nI understand this is a valid view of what is changed, but not a very\nlogical view from the point of the user.\n\nI wondered if there is a way to improve this, or would that have other\nconsequences.\n"},{"id":"204769","messageId":"7vvcc73yzh.fsf@alter.siamese.dyndns.org","threadId":"32322","inReplyTo":"CAO54GHD3C2RKUvE5jK_XOCVbbDuE_c5xfe28rOL+DaE5anL-Wg@mail.gmail.com","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-12T18:29:54Z","receivedAt":"2012-12-12T18:29:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin writes:\n\n> Regularly I notice that the diffs that are provided (through diff, or\n> add -p) tend to disconnect changes that belong to each other and\n> report lines being changed that are not changed.\n>\n> An example for this is:\n>\n> /**\n> + * Default parent\n> + *\n> + * @var int\n> + * @access protected\n> + * @index\n> + */\n> + protected $defaultParent;\n> +\n> + /**\n>\n> I understand this is a valid view of what is changed, but not a very\n> logical view from the point of the user.\n>\n> I wondered if there is a way to improve this, or would that have other\n> consequences.\n\nI think your example shows a case where the end of the pre-context\nmatches the end of the added text in the hunk, and it appears it may\nproduce a better result if you shift the hunk up. But I think that\nworks only half the time. Imagine:\n\n @@ -K,L +M,N @@\n }\n \n +void new_function(void)\n +{\n + printf(\"hello, world.\\n\");\n +}\n +\n void existing_one(void)\n {\n printf(\"goodbye, world.\\n\");\n\nHere the end of the pre-context matches the end of the added lines,\nbut it will produce worse result if you blindly apply the \"shift the\nhunk up\" trick:\n\n ... what was before the } we saw in the precontext ...\n +}\n +\n +void new_function(void)\n +{\n + printf(\"hello, world.\\n\");\n }\n \n void existing_one(void)\n\nSo I think with s/Regularly/About half the time/, your observation\nabove is correct.\n\nI think the reason you perceived this as \"Regularly\" is that you do\nnot notice nor appreciate it when things go right (half the time),\nbut you tend to notice and remember only when a wrong side happened\nto have been picked (the other half).\n"},{"id":"204770","messageId":"50C8D16B.8060702@interlinx.bc.ca","threadId":"32322","inReplyTo":"7vvcc73yzh.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Brian J. Murrell","fromEmail":"brian@interlinx.bc.ca","sentAt":"2012-12-12T18:48:11Z","receivedAt":"2012-12-12T18:48:11Z","isPatch":false,"sender":{"key":"brian@interlinx.bc.ca","avatar":null},"body":"On 12-12-12 01:29 PM, Junio C Hamano wrote:\n> \n> Here the end of the pre-context matches the end of the added lines,\n> but it will produce worse result if you blindly apply the \"shift the\n> hunk up\" trick:\n\nYeah. I would not think a blind shift would be appropriate. But I\nwonder if diff can take whitespace hints about when to shift and when\nnot to.\n\nIt would still never be perfect but might be more accurate than it is\nnow. Can't imagine it would be any worse.\n\nb.\n\n\n"},{"id":"204773","messageId":"CAO54GHANKuv_+S-FJzrTfeFyiXcKDbm5hLGdADQ7GVMh7jEMxw@mail.gmail.com","threadId":"32322","inReplyTo":"7vvcc73yzh.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Kevin","fromEmail":"ikke@ikke.info","sentAt":"2012-12-12T19:30:01Z","receivedAt":"2012-12-12T19:30:01Z","isPatch":false,"sender":{"key":"ikke@ikke.info","avatar":"https://gravatar.com/avatar/60a0d08eeccb16914fdbfc7f3441548dc827dc436d5c6900ec6600e274e53c5b?d=mp&s=160"},"body":"Yeah, I didn't mention it, but I didn't think it was doing this wrong\nin a systematic way. I only wondered if there was some kind of\nheuristic that could improve the cases where it goes wrong, without\naffecting the cases where it would do it right.\n\nI know this is not an easy problem, lest it would already been fixed.\n\nOn Wed, Dec 12, 2012 at 7:29 PM, Junio C Hamano wrote:\n> Kevin writes:\n>\n>> Regularly I notice that the diffs that are provided (through diff, or\n>> add -p) tend to disconnect changes that belong to each other and\n>> report lines being changed that are not changed.\n>>\n>> An example for this is:\n>>\n>> /**\n>> + * Default parent\n>> + *\n>> + * @var int\n>> + * @access protected\n>> + * @index\n>> + */\n>> + protected $defaultParent;\n>> +\n>> + /**\n>>\n>> I understand this is a valid view of what is changed, but not a very\n>> logical view from the point of the user.\n>>\n>> I wondered if there is a way to improve this, or would that have other\n>> consequences.\n>\n> I think your example shows a case where the end of the pre-context\n> matches the end of the added text in the hunk, and it appears it may\n> produce a better result if you shift the hunk up. But I think that\n> works only half the time. Imagine:\n>\n> @@ -K,L +M,N @@\n> }\n>\n> +void new_function(void)\n> +{\n> + printf(\"hello, world.\\n\");\n> +}\n> +\n> void existing_one(void)\n> {\n> printf(\"goodbye, world.\\n\");\n>\n> Here the end of the pre-context matches the end of the added lines,\n> but it will produce worse result if you blindly apply the \"shift the\n> hunk up\" trick:\n>\n> ... what was before the } we saw in the precontext ...\n> +}\n> +\n> +void new_function(void)\n> +{\n> + printf(\"hello, world.\\n\");\n> }\n>\n> void existing_one(void)\n>\n> So I think with s/Regularly/About half the time/, your observation\n> above is correct.\n>\n> I think the reason you perceived this as \"Regularly\" is that you do\n> not notice nor appreciate it when things go right (half the time),\n> but you tend to notice and remember only when a wrong side happened\n> to have been picked (the other half).\n"},{"id":"204782","messageId":"7vtxrr2evm.fsf@alter.siamese.dyndns.org","threadId":"32322","inReplyTo":"7vvcc73yzh.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-12T20:29:33Z","receivedAt":"2012-12-12T20:29:33Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Kevin writes:\n>\n>> Regularly I notice that the diffs that are provided (through diff, or\n>> add -p) tend to disconnect changes that belong to each other and\n>> report lines being changed that are not changed.\n>>\n>> An example for this is:\n>>\n>> /**\n>> + * Default parent\n>> + *\n>> + * @var int\n>> + * @access protected\n>> + * @index\n>> + */\n>> + protected $defaultParent;\n>> +\n>> + /**\n>>\n>> I understand this is a valid view of what is changed, but not a very\n>> logical view from the point of the user.\n>>\n>> I wondered if there is a way to improve this, or would that have other\n>> consequences.\n\nI forgot to mention consequences. Changing it obviously changes the\nshape of the diff, hence changes the patch id. Anything that caches\noutput from \"git cherry\" to match up \"identical patches\" will need\nto discard and repopulate its cache. Your \"rerere\" database will go\nstale.\n\nAlso \"kup\" tool used at k.org allows an uploader to pretend to\nupload an incremental diff between two known commits by only sending\nthe GPG signature of the diff the uploader generates. The actual\ndiff is generated on the k.org machine locally and deposited next to\nthe GPG signature file, with the expectation that the signture\nmatches the diff. Changing the output from diff between two\nversions will break the optimization and force the uploader to\nupload the diff over the wire.\n"},{"id":"204783","messageId":"CANv4PNm45xGBn2veKi1o0wB4K9NgsbtCsiymHNO4xbCDpJ5tDg@mail.gmail.com","threadId":"32322","inReplyTo":"7vvcc73yzh.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2012-12-12T21:40:32Z","receivedAt":"2012-12-12T21:40:32Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"> So I think with s/Regularly/About half the time/, your observation\n> above is correct.\n>\n> I think the reason you perceived this as \"Regularly\" is that you do\n> not notice nor appreciate it when things go right (half the time),\n> but you tend to notice and remember only when a wrong side happened\n> to have been picked (the other half).\n\nIs there a reason why picking among the choices in a sliding window\nmust be contents neutral?\n\nI see these \"illogical\" (== stylistically not matching user intent) diffs\nquite often. C comments (as in the example given) and #ifdef blocks\nare typical cases.\n\nPurely anecdotically, I have seen more trouble applying \"illogical\"\ndiffs than I would have expected from the corresponding \"logical\" diffs.\n\nMorten\n"},{"id":"204784","messageId":"7vpq2f2az4.fsf@alter.siamese.dyndns.org","threadId":"32322","inReplyTo":"CANv4PNm45xGBn2veKi1o0wB4K9NgsbtCsiymHNO4xbCDpJ5tDg@mail.gmail.com","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-12T21:53:51Z","receivedAt":"2012-12-12T21:53:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Morten Welinder writes:\n\n> Is there a reason why picking among the choices in a sliding window\n> must be contents neutral?\n\nSorry, you might be getting at something interesting but I do not\nunderstand the question. I have no idea what you mean by \"contents\nneutral\".\n\nPicking between these two choices\n\n /** + /** \n + * Default parent + * Default parent \n + * + * \n + * @var int + * @var int \n + * @access protected + * @access protected \n + * @index + * @index \n + */ + */ \n + protected $defaultParent; + protected $defaultParent; \n + + \n + /** /** \n\nwould not affect the correctness of the patch. You may pick\nwhatever you deem the most desirable, but your answer must be a\ncorrect patch (the definition of \"correct\" here is \"applying that\npatch to the preimage produces the intended postimage\").\n\nAnd I think if you inserted a block of text B after a context C\nwhere the tail of B matches the tail of C like the above, you can\nshift what you treat as \"inserted\" up and still come up with a\ncorrect patch.\n\nThe output being \"a correct patch\" is not the only thing we need to\nconsider, though, as I mentioned in another response to Kevin\nregarding the \"consequences\".\n"},{"id":"204792","messageId":"CAH5451=4dqqMnQa-R6O4ZrHOPSpHU9joWqf2UuOkbLtU9f8bkQ@mail.gmail.com","threadId":"32322","inReplyTo":"7vpq2f2az4.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Andrew Ardill","fromEmail":"andrew.ardill@gmail.com","sentAt":"2012-12-12T22:34:41Z","receivedAt":"2012-12-12T22:34:41Z","isPatch":false,"sender":{"key":"andrew.ardill@gmail.com","avatar":"https://gravatar.com/avatar/da14cb7c091dd44dc6c63a4d3361b149acaf25226dc78eb4131a17b93d9b0993?d=mp&s=160"},"body":"On 13 December 2012 08:53, Junio C Hamano wrote:\n> The output being \"a correct patch\" is not the only thing we need to\n> consider, though, as I mentioned in another response to Kevin\n> regarding the \"consequences\".\n\nThe main benefit of picking a more 'natural' diff is a usability one.\nI know that when a chunk begins and ends one line after the logical\nbreak point (typically with braces in my experience) mentally parsing\nthe diff becomes significantly harder. If there was a way to teach git\nwhere it should try and break out a chunk (potentially per filetype?)\nthis is a good thing for readability, and I think would outweigh any\ntemporary pain with regards to cached rerere and diff data.\n\nRegards,\n\nAndrew Ardill\n"},{"id":"204806","messageId":"CALZVapnzYBhPU1nR=eCSnm73c9-SpHq34DHu7OWCkouCQS0FxQ@mail.gmail.com","threadId":"32322","inReplyTo":"CAH5451=4dqqMnQa-R6O4ZrHOPSpHU9joWqf2UuOkbLtU9f8bkQ@mail.gmail.com","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Javier Domingo","fromEmail":"javierdo1@gmail.com","sentAt":"2012-12-12T23:32:53Z","receivedAt":"2012-12-12T23:32:53Z","isPatch":false,"sender":{"key":"javierdo1@gmail.com","avatar":"https://gravatar.com/avatar/0f43d4d2e5f4320e8b5e1a46914213c5459dd0de261ab1587f222827f863d727?d=mp&s=160"},"body":"I must say it is _quite_ helpfull having the diffs well done (natural\ndiffs as here named), just because when you want to review a patch on\nthe fly, this sort of things are annoying.\n\nI just wanted to say my opinion. No idea on how to fix that, nor why\ndoes it happen.\n\nJavier Domingo\n\n\n2012/12/12 Andrew Ardill :\n> On 13 December 2012 08:53, Junio C Hamano wrote:\n>> The output being \"a correct patch\" is not the only thing we need to\n>> consider, though, as I mentioned in another response to Kevin\n>> regarding the \"consequences\".\n>\n> The main benefit of picking a more 'natural' diff is a usability one.\n> I know that when a chunk begins and ends one line after the logical\n> break point (typically with braces in my experience) mentally parsing\n> the diff becomes significantly harder. If there was a way to teach git\n> where it should try and break out a chunk (potentially per filetype?)\n> this is a good thing for readability, and I think would outweigh any\n> temporary pain with regards to cached rerere and diff data.\n>\n> Regards,\n>\n> Andrew Ardill\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"204808","messageId":"7vobhy25wd.fsf@alter.siamese.dyndns.org","threadId":"32322","inReplyTo":"CALZVapnzYBhPU1nR=eCSnm73c9-SpHq34DHu7OWCkouCQS0FxQ@mail.gmail.com","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-12T23:43:30Z","receivedAt":"2012-12-12T23:43:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Javier Domingo writes:\n\n> I must say it is _quite_ helpfull having the diffs well done (natural\n> diffs as here named), just because when you want to review a patch on\n> the fly, this sort of things are annoying.\n\nI do not think anybody is arguing that it would not help the human\nusers to shift the hunk boundaries in the case Kevin's original\nmessage demonstrated.\n"},{"id":"204810","messageId":"CALZVap=4hx6bwbuDpR5PUt-b6EtVAskw1FRo5N7zuvQRcGaqdQ@mail.gmail.com","threadId":"32322","inReplyTo":"7vobhy25wd.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Javier Domingo","fromEmail":"javierdo1@gmail.com","sentAt":"2012-12-12T23:49:02Z","receivedAt":"2012-12-12T23:49:02Z","isPatch":false,"sender":{"key":"javierdo1@gmail.com","avatar":"https://gravatar.com/avatar/0f43d4d2e5f4320e8b5e1a46914213c5459dd0de261ab1587f222827f863d727?d=mp&s=160"},"body":"So, how can it be fixed? or is diff command's problem?\nJavier Domingo\n\n\n2012/12/13 Junio C Hamano :\n> Javier Domingo writes:\n>\n>> I must say it is _quite_ helpfull having the diffs well done (natural\n>> diffs as here named), just because when you want to review a patch on\n>> the fly, this sort of things are annoying.\n>\n> I do not think anybody is arguing that it would not help the human\n> users to shift the hunk boundaries in the case Kevin's original\n> message demonstrated.\n>\n"},{"id":"204812","messageId":"50C91A88.1090306@alum.mit.edu","threadId":"32322","inReplyTo":"7vpq2f2az4.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-12-13T00:00:08Z","receivedAt":"2012-12-13T00:00:08Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 12/12/2012 10:53 PM, Junio C Hamano wrote:\n> Morten Welinder writes:\n> \n>> Is there a reason why picking among the choices in a sliding window\n>> must be contents neutral?\n> \n> Sorry, you might be getting at something interesting but I do not\n> understand the question. I have no idea what you mean by \"contents\n> neutral\".\n> \n> Picking between these two choices\n> \n> /** + /** \n> + * Default parent + * Default parent \n> + * + * \n> + * @var int + * @var int \n> + * @access protected + * @access protected \n> + * @index + * @index \n> + */ + */ \n> + protected $defaultParent; + protected $defaultParent; \n> + + \n> + /** /** \n> \n> would not affect the correctness of the patch. You may pick\n> whatever you deem the most desirable, but your answer must be a\n> correct patch (the definition of \"correct\" here is \"applying that\n> patch to the preimage produces the intended postimage\").\n> \n> And I think if you inserted a block of text B after a context C\n> where the tail of B matches the tail of C like the above, you can\n> shift what you treat as \"inserted\" up and still come up with a\n> correct patch.\n\nI have the feeling that a few crude heuristics would go a long way\ntowards improving diffs like this. For example:\n\n* Prefer to have an add/remove block that has balanced begin/end pairs\n(where begin/end pairs might be opening and closing parentheses,\nbrackets, braces, and angle brackets, \"/*\" and \"*/\", and perhaps a\ncouple of other things. For SGML-like text begin and end tags could be\nmatched up.\n\nIt would be possible to read these begin/end pairs from a\nfiletype-specific table or configuration setting, though this would add\ncomplication and would also make it possible that diffs generated by two\ndifferent people are not identical if their configurations differ.\n\n* Prefer to have a block where the first non-blank line of the block and\nthe first non-blank line after the block are indented by the same amount.\n\n* Prefer to have a block with trailing (as opposed to leading or\nembedded) blank lines--the more the better.\n\nThe beautiful thing is that even if the heuristics sometimes fail, the\ncorrectness of the patch (in the sense that you have defined) is not\ncompromised.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"204819","messageId":"CANv4PNnC1J54TSpHuBOpY=rbuU_naysYkmoyi=utNF0vWK1CnA@mail.gmail.com","threadId":"32322","inReplyTo":"7vpq2f2az4.fsf@alter.siamese.dyndns.org","subject":"Re: Fwd: possible Improving diff algoritm","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2012-12-13T01:55:59Z","receivedAt":"2012-12-13T01:55:59Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":">> Is there a reason why picking among the choices in a sliding window\n>> must be contents neutral?\n>\n> Sorry, you might be getting at something interesting but I do not\n> understand the question. I have no idea what you mean by \"contents\n> neutral\".\n\nI was merely asking if an algorithm to pick between the\n2+ choices was allowed to look at the contents of the\nlines.\n\nI.e., an algorithm would look at the C comment\nexample and determine that the choice starting containing\na full inserted comment is preferable over the one that\nappears to close one comment and open a new.\n\nAnd the in inserted-function case it would prefer the one\nwhere the matching { and } are in correct order.\n\nMorten\n"},{"id":"204821","messageId":"B1564B28-9BB9-48A2-B59E-7D7C0B0DDECF@adacore.com","threadId":"32322","inReplyTo":"CANv4PNnC1J54TSpHuBOpY=rbuU_naysYkmoyi=utNF0vWK1CnA@mail.gmail.com","subject":"Re: possible Improving diff algoritm","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2012-12-13T04:58:57Z","receivedAt":"2012-12-13T04:58:57Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Dec 12, 2012, at 20:55, Morten Welinder wrote:\n> I was merely asking if an algorithm to pick between the\n> 2+ choices was allowed to look at the contents of the\n> lines.\n> \n> I.e., an algorithm would look at the C comment\n> example and determine that the choice starting containing\n> a full inserted comment is preferable over the one that\n> appears to close one comment and open a new.\n> \n> And the in inserted-function case it would prefer the one\n> where the matching { and } are in correct order.\n\n /** + /** \n + * Default parent + * Default parent \n + * + * \n + * @var int + * @var int \n + * @access protected + * @access protected \n + * @index + * @index \n + */ + */ \n + protected $defaultParent; + protected $defaultParent; \n + + \n + /** /** \n\nIt would seem that just looking at the line length (stripped) of\nthe last line, might be sufficient for cost function to minimize.\nHere the some would be 3 vs 0. In case of ties, use the last\npossibility with minimum cost.\n\nI think it would be nice if the cost function we choose does not\ndepend on file type, as that is something that is very dependent\non the exact local configuration and might hinder comparison of\npatches. If something really simple gets us 90% there, that would\nbe preferable over extra complexity.\n\n -Geert\n\nJunio's other example:\n\n }\n\n +void new_function(void)\n +{\n + printf(\"hello, world.\\n\");\n +}\n +\n void existing_one(void)\n {\n printf(\"goodbye, world.\\n\");\n\n=> Cost 0\n\n +}\n +\n +void new_function(void)\n +{\n + printf(\"hello, world.\\n\");\n }\n=> Cost 27\n\nKevin's example:\n /**\n+ * Default parent\n+ *\n+ * @var int\n+ * @access protected\n+ * @index\n+ */\n+ protected $defaultParent;\n+\n+ /**\n\n=> Cost 3\n\n+ /**\n+ * Default parent\n+ *\n+ * @var int\n+ * @access protected\n+ * @index\n+ */\n+ protected $defaultParent;\n+\n /**\n=> cost 0\n"},{"id":"204824","messageId":"7vzk1izcv6.fsf@alter.siamese.dyndns.org","threadId":"32322","inReplyTo":"B1564B28-9BB9-48A2-B59E-7D7C0B0DDECF@adacore.com","subject":"Re: possible Improving diff algoritm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-13T06:26:37Z","receivedAt":"2012-12-13T06:26:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Geert Bosch writes:\n\n> It would seem that just looking at the line length (stripped) of\n> the last line, might be sufficient for cost function to minimize.\n> Here the some would be 3 vs 0. In case of ties, use the last\n> possibility with minimum cost.\n\n-- 8< --\n#ifdef A\n\nsome stuff\nabout A\n\n#endif\n#ifdef Z\n\nsome more stuff\nabout Z\n\n#endif\n-- >8 --\n\nIf you insert a block for M following the existing formatting\nconvention in the middle, your heuristics will pick the blank line\nafter \"about A\" as having minimum cost, no?\n\nYou inherently have to know the nature of the payload, as your eyes\nthat judge the result use that knowledge when doing so, I am afraid.\nI think your \"define a function that gives a good score to lines\nthat are likely to be good breaking points\" idea has merit, but I\nthink that should be tied to the content type, most likely via the\nattribute mechanism.\n\nIn any case, I consider this as a low-impact (as Michael Haggerty\nnoted, it is impossible to introduce a bug that subtly break the\noutput; your result is either totally borked or is correct) and\nlow-hanging fruit (it can be done as a postprocessing phase after\nthe xdiff machinery has done the heavy-lifting of computing LCA), if\nsomebody wants to experiment and implement one. As long as the new\nheuristics is hidden behind an explicit command line option to avoid\nother \"consequences\", I wouldn't discourage interested parties from\nworking on it. It is not just my itch, though.\n"},{"id":"204867","messageId":"CALZVap=r0toqWT7aJxiKtezmR8s4QDd0x92JX-eBLWhKaJsmOw@mail.gmail.com","threadId":"32322","inReplyTo":"7vzk1izcv6.fsf@alter.siamese.dyndns.org","subject":"Re: possible Improving diff algoritm","fromName":"Javier Domingo","fromEmail":"javierdo1@gmail.com","sentAt":"2012-12-14T12:20:29Z","receivedAt":"2012-12-14T12:20:29Z","isPatch":false,"sender":{"key":"javierdo1@gmail.com","avatar":"https://gravatar.com/avatar/0f43d4d2e5f4320e8b5e1a46914213c5459dd0de261ab1587f222827f863d727?d=mp&s=160"},"body":"I think the idea of being preferable to have a blank line at the end\nof the added/deleted block is key in this case.\n\nJavier Domingo\n\n\n2012/12/13 Junio C Hamano :\n> Geert Bosch writes:\n>\n>> It would seem that just looking at the line length (stripped) of\n>> the last line, might be sufficient for cost function to minimize.\n>> Here the some would be 3 vs 0. In case of ties, use the last\n>> possibility with minimum cost.\n>\n> -- 8< --\n> #ifdef A\n>\n> some stuff\n> about A\n>\n> #endif\n> #ifdef Z\n>\n> some more stuff\n> about Z\n>\n> #endif\n> -- >8 --\n>\n> If you insert a block for M following the existing formatting\n> convention in the middle, your heuristics will pick the blank line\n> after \"about A\" as having minimum cost, no?\n>\n> You inherently have to know the nature of the payload, as your eyes\n> that judge the result use that knowledge when doing so, I am afraid.\n> I think your \"define a function that gives a good score to lines\n> that are likely to be good breaking points\" idea has merit, but I\n> think that should be tied to the content type, most likely via the\n> attribute mechanism.\n>\n> In any case, I consider this as a low-impact (as Michael Haggerty\n> noted, it is impossible to introduce a bug that subtly break the\n> output; your result is either totally borked or is correct) and\n> low-hanging fruit (it can be done as a postprocessing phase after\n> the xdiff machinery has done the heavy-lifting of computing LCA), if\n> somebody wants to experiment and implement one. As long as the new\n> heuristics is hidden behind an explicit command line option to avoid\n> other \"consequences\", I wouldn't discourage interested parties from\n> working on it. It is not just my itch, though.\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"204886","messageId":"20121214222938.GB19410@client.brlink.eu","threadId":"32322","inReplyTo":"CALZVap=r0toqWT7aJxiKtezmR8s4QDd0x92JX-eBLWhKaJsmOw@mail.gmail.com","subject":"Re: possible Improving diff algoritm","fromName":"Bernhard R. Link","fromEmail":"brl+git@mail.brlink.eu","sentAt":"2012-12-14T22:29:38Z","receivedAt":"2012-12-14T22:29:38Z","isPatch":false,"sender":{"key":"brl+git@mail.brlink.eu","avatar":null},"body":"* Javier Domingo [121214 13:20]:\n> I think the idea of being preferable to have a blank line at the end\n> of the added/deleted block is key in this case.\n\nFor symmetry I'd suggest to make it preferable to have blank lines\nat the end or the beginning.\n\n {\n old\n+ }\n+\n+ {\n+ new\n }\n\nvs\n\n {\n old\n }\n+\n+ {\n+ new\n+ }\n\nis just the same case in blue.\n(Although empty lines alone feels not quite optimal, it is at least a\ngood start).\n\n Bernhard R. Link\n"},{"id":"204907","messageId":"CALZVapnNFMAMM_UVjgR01DZ2MZhQbJHm7dMLpGzdRqhzrzBuyg@mail.gmail.com","threadId":"32322","inReplyTo":"20121214222938.GB19410@client.brlink.eu","subject":"Re: possible Improving diff algoritm","fromName":"Javier Domingo","fromEmail":"javierdo1@gmail.com","sentAt":"2012-12-15T12:16:27Z","receivedAt":"2012-12-15T12:16:27Z","isPatch":false,"sender":{"key":"javierdo1@gmail.com","avatar":"https://gravatar.com/avatar/0f43d4d2e5f4320e8b5e1a46914213c5459dd0de261ab1587f222827f863d727?d=mp&s=160"},"body":"If just empty lines alone, then it is forced to say there is a new\nline. That is beyond this use-case.\nJavier Domingo\n\n\n2012/12/14 Bernhard R. Link :\n> * Javier Domingo [121214 13:20]:\n>> I think the idea of being preferable to have a blank line at the end\n>> of the added/deleted block is key in this case.\n>\n> For symmetry I'd suggest to make it preferable to have blank lines\n> at the end or the beginning.\n>\n> {\n> old\n> + }\n> +\n> + {\n> + new\n> }\n>\n> vs\n>\n> {\n> old\n> }\n> +\n> + {\n> + new\n> + }\n>\n> is just the same case in blue.\n> (Although empty lines alone feels not quite optimal, it is at least a\n> good start).\n>\n> Bernhard R. Link\n"}]}