Re: Fwd: possible Improving diff algoritm

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Dec 13, 2012, 00:00 UTC
Message-ID: <50C91A88.1090306@alum.mit.edu>
In-Reply-To: <7vpq2f2az4.fsf@alter.siamese.dyndns.org>

On 12/12/2012 10:53 PM, Junio C Hamano wrote:

Show 31 quoted lines

> Morten Welinder <mwelinder@gmail.com> writes:
> 
>> Is there a reason why picking among the choices in a sliding window
>> must be contents neutral?
> 
> Sorry, you might be getting at something interesting but I do not
> understand the question.  I have no idea what you mean by "contents
> neutral".
> 
> Picking between these two choices
> 
>          /**                         +    /**                         
>     +     * Default parent           +     * Default parent           
>     +     *                          +     *                          
>     +     * @var int                 +     * @var int                 
>     +     * @access protected        +     * @access protected        
>     +     * @index                   +     * @index                   
>     +     */                         +     */                         
>     +    protected $defaultParent;   +    protected $defaultParent;   
>     +                                +                                
>     +    /**                              /**                         
> 
> would not affect the correctness of the patch.  You may pick
> whatever you deem the most desirable, but your answer must be a
> correct patch (the definition of "correct" here is "applying that
> patch to the preimage produces the intended postimage").
> 
> And I think if you inserted a block of text B after a context C
> where the tail of B matches the tail of C like the above, you can
> shift what you treat as "inserted" up and still come up with a
> correct patch.

I have the feeling that a few crude heuristics would go a long way towards improving diffs like this. For example:

* Prefer to have an add/remove block that has balanced begin/end pairs
(where begin/end pairs might be opening and closing parentheses,
brackets, braces, and angle brackets, "/*" and "*/", and perhaps a
couple of other things.  For SGML-like text begin and end tags could be
matched up.

It would be possible to read these begin/end pairs from a filetype-specific table or configuration setting, though this would add complication and would also make it possible that diffs generated by two different people are not identical if their configurations differ.

* Prefer to have a block where the first non-blank line of the block and
the first non-blank line after the block are indented by the same amount.

* Prefer to have a block with trailing (as opposed to leading or
embedded) blank lines--the more the better.

The beautiful thing is that even if the heuristics sometimes fail, the correctness of the patch (in the sense that you have defined) is not compromised.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/