Re: [PATCH] diff compaction heuristic: favor shortest neighboring blank lines

[Michael Haggerty <mhagger@alum.mit.edu>]

On 06/17/2016 06:09 PM, Stefan Beller wrote:
> I think before spending more time on discussing and implementing new
> (hopefully better) heuristics, I'd want to step back and try to be a bit more
> systematic, i.e. I'll want to collect lots of test cases in different languages
> and use cases. A mini test suite, maybe?

Stefan,

I've also been playing around with diff heuristics and also trying to
find some good test data. Have you put together some test cases yet?

In case you are interested, the current iteration of my heuristic
considers six things to determine a "score" for breaking a diff above a
particular line:

* `blank` -- is the line blank?
* `indent` -- the indentation of the line (if it is not blank)
* `pre_blank` -- is the preceding line blank?
* `pre_indent` -- the indentation of the closest preceding non-blank
  line
* `post_blank` -- is the following line blank?
* `post_indent` -- the indentation of the closest following non-blank
  line

The meat of the scoring algorithm is below. I compute the score for the
beginning and the end of the insert/delete block for each candidate
shift of an insertion/deletion hunk, then choose the one that has the
lowest score.

There are some adjustable "bonus" values below. The values shown give
quite good results for C, shell, Python, XML, Ruby, CSS, YAML, and HTML
in the couple of projects that I've tried it on. But I haven't done
enough systematic testing over a large enough corpus to know whether the
parameters could be improved or whether there are types of code that it
performs really terribly on.

Right now my program doesn't output diffs in the usual format, but
rather as a diff notated with various information. So it's not in a form
that other people could use so easily. Here's an example:

> vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
>                   *
>                   * Default behaviour is to initialize the notes tree from the tree object
>                   * specified by the given (or default) notes ref.
>                   */
>                  #define NOTES_INIT_EMPTY 1
>     |     -4     
>     |     -6 +   /*
>     ||    28 +  + * By default, the notes tree is only readable, and the notes ref can be
>     ||       +  + * any treeish. The notes tree can however be made writable with this flag,
>     ||       +  + * in which case only strict ref names can be used.
>     ||       +  + */
>     ||       +  +#define NOTES_INIT_WRITABLE 2
>      |       +  +
>      |          +/*
>                   * Initialize the given notes_tree with the notes tree structure at the given
>                   * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment
>                   * variable is used, and if that is missing, the default notes ref is used
>                   * ("refs/notes/commits").
>                   *
>                   * If you need to re-initialize a notes_tree structure (e.g. when switching from
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The two columns of vertical bars show the highest and lowest range of
lines that this insertion block can be shifted to. The numbers show the
score for breaking the diff above that line. The first column of +/- is
where this version of the heuristic would place the diff, and the second
column is where the master version of Git would place it.

My program can also search for and output "slideable" insertion/deletion
blocks, so it can be used to find diffs that are theoretically capable
of being optimized, even if they don't happen to be handled differently
by two different algorithms.

Let me know if you want to collaborate on this somehow.

Michael

Scoring heuristic:

>     # A place to accumulate bonus factors (positive makes this
>     # index more favored):
>     bonus = 0
> 
>     # Bonuses based on the location of blank lines:
>     if pre_blank and not blank:
>         bonus += 3
>     elif blank and not pre_blank:
>         bonus += 2
>     elif blank and pre_blank:
>         bonus += 1
> 
>     # Now fill in missing indent values:
>     if pre_indent is None:
>         pre_indent = 0
> 
>     if post_indent is None:
>         post_indent = 0
> 
>     if blank:
>         indent = post_indent
> 
>     if indent > pre_indent:
>         # The line is indented more than its predecessor. It is
>         # preferable to keep these lines together, so we score it
>         # based on the larger indent:
>         score = indent
>         bonus -= 4
> 
>     elif indent < pre_indent:
>         # The line is indented less than its predecessor. It could
>         # be that this line is the start of a new block (e.g., of
>         # an "else" block, or of a block without a block
>         # terminator) or it could be the end of the previous
>         # block.
>         if indent < post_indent:
>             # The following line is indented more. So it is likely
>             # that this line is the start of a block. It's a
>             # pretty good place to split, so score it based on the
>             # smaller indent:
>             score = indent
>             bonus += 2
>         else:
>             # This was probably the end of a block. We score based
>             # on the line's own indent:
>             score = indent
> 
>     else:
>         # The line has the same indentation level as its
>         # predecessor. We score it based on its own indent:
>         score = indent
> 
>     return 10 * score - bonus