Re: [RFC PATCH, WAS: "weird diff output?"] Implement better chunk heuristics.

[Jacob Keller <jacob.keller@gmail.com>]

On Thu, Apr 14, 2016 at 5:07 PM, Stefan Beller <sbeller@google.com> wrote:
> TODO(sbeller):
> * describe the discussion on why this is better
> * see if this can be tested?
>

Thanks for taking time to do this! It looks like a few things are
still missing, CRLF obviously, and making it a configuration option.

> Signed-off-by: Stefan Beller <sbeller@google.com>
> ---
>  xdiff/xdiffi.c | 39 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 39 insertions(+)
>
> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
> index 2358a2d..24eb9a0 100644
> --- a/xdiff/xdiffi.c
> +++ b/xdiff/xdiffi.c
> @@ -400,9 +400,16 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
>  }
>
>
> +static int starts_with_emptyline(const char *recs)
> +{
> +       return recs[0] == '\n'; /* CRLF not covered here */
> +}
> +
> +
>  int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>         long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
>         char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
> +       unsigned char has_emptyline;
>         xrecord_t **recs = xdf->recs;
>
>         /*
> @@ -436,6 +443,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>
>                 do {
>                         grpsiz = ix - ixs;
> +                       has_emptyline = 0;
>
>                         /*
>                          * If the line before the current change group, is equal to
> @@ -447,6 +455,8 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>                                 rchg[--ixs] = 1;
>                                 rchg[--ix] = 0;
>
> +                               has_emptyline |=
> +                                       starts_with_emptyline(recs[ix]->ptr);

I assume you're doing |= so that we don't overwrite the empty line
setting each loop here to 0 when it's false? That's a bit subtle, and
it took me a moment to figure out, since I am used to thinking of it
as bitwise | and not a boolean or like we're intending here (though
obviously we're using bitwise to perform that intended behavior).

>                                 /*
>                                  * This change might have joined two change groups,
>                                  * so we try to take this scenario in account by moving
> @@ -475,6 +485,9 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>                                 rchg[ixs++] = 0;
>                                 rchg[ix++] = 1;
>
> +                               has_emptyline |=
> +                                       starts_with_emptyline(recs[ix]->ptr);
> +
>                                 /*
>                                  * This change might have joined two change groups,
>                                  * so we try to take this scenario in account by moving
> @@ -498,6 +511,32 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>                         rchg[--ix] = 0;
>                         while (rchgo[--ixo]);
>                 }
> +
> +               /*
> +                * If a group can be moved back and forth, see if there is an
> +                * empty line in the moving space. If there is an empty line,
> +                * make sure the last empty line is the end of the group.
> +                *
> +                * As we shifted the group forward as far as possible, we only
> +                * need to shift it back if at all.
> +                */
> +               if (has_emptyline) {
> +                       while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
> +                              xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags) &&
> +                              !starts_with_emptyline(recs[ix - 1]->ptr)) {
> +                               rchg[--ixs] = 1;
> +                               rchg[--ix] = 0;
> +
> +                               /*
> +                                * This change did not join two change groups,
> +                                * as we did that before already, so there is no
> +                                * need to adapt the other-file, i.e.
> +                                * running
> +                                *     for (; rchg[ixs - 1]; ixs--);
> +                                *     while (rchgo[--ixo]);
> +                                */
> +                       }
> +               }
>         }

And this was the more difficult part which I wasn't able to fully
understand how to do. It seems pretty reasonable. I think we can make
it configurable by using a new XDIFF flag similar to how we handle
various diff options like the different diff algorithms, and then we
could add tests specific to ensure that the flag enables the behavior
we want on some known test cases.

I am not really sure how to thoroughly test it beyond that though.

Regards,
Jake

>
>         return 0;
> --
> 2.8.1.474.gffdc890.dirty
>