Out of memory with diff.colormoved enabled

> There is an infinite loop when colormoved is used with --ignore-space-change:
> 
> git init
> seq 20 > test
> git add test
> sed -i 's/9/42/' test
> git -c diff.colormoved diff --ignore-space-change -- test

> On Thu, Oct 12, 2017 at 10:53:23PM +0300, Orgad Shaneh wrote:
>
>> There is an infinite loop when colormoved is used with --ignore-space-change:
>>
>> git init
>> seq 20 > test
>> git add test
>> sed -i 's/9/42/' test
>> git -c diff.colormoved diff --ignore-space-change -- test
>
> Thanks for an easy reproduction recipe.

> This fixes it, but I have no idea if it's doing the right thing:
>
> diff --git a/diff.c b/diff.c
> index 69f03570ad..e8dedc7357 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -713,13 +713,17 @@ static int next_byte(const char **cp, const char **endp,
>                 return -1;
>
>         if (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_CHANGE)) {
> -               while (*cp < *endp && isspace(**cp))
> +               int saw_whitespace = 0;
> +               while (*cp < *endp && isspace(**cp)) {
>                         (*cp)++;
> +                       saw_whitespace = 1;
> +               }
>                 /*
>                  * After skipping a couple of whitespaces, we still have to
>                  * account for one space.
>                  */
> -               return (int)' ';
> +               if (saw_whitespace)
> +                       return (int)' ';

>         }
>
>         if (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE)) {
>
> I guess it would be equally correct to not enter that if-block unless
> isspace(**cp).

> Fix this by entering the conditional only when we actually
> see whitespace. We can apply this also to the
> IGNORE_WHITESPACE change. That code path isn't buggy
> (because it falls through to returning the next
> non-whitespace byte), but it makes the logic more clear if
> we only bother to look at whitespace flags after seeing that
> the next byte is whitespace.

> On Thu, Oct 12, 2017 at 08:18:37PM -0400, Jeff King wrote:
>
>> Fix this by entering the conditional only when we actually
>> see whitespace. We can apply this also to the
>> IGNORE_WHITESPACE change. That code path isn't buggy
>> (because it falls through to returning the next
>> non-whitespace byte), but it makes the logic more clear if
>> we only bother to look at whitespace flags after seeing that
>> the next byte is whitespace.
>
> I think there actually _is_ a bug in that code path, but it's unrelated
> to this one. If you have whitespace at the end of the buffer, then we'd
> advance *cp until it matches *endp, and then return whatever is at *endp
> (which is nonsense, or probably a NUL) rather than returning "-1".

> I'm out of time for tonight and not familiar enough with the color-moved
> code to come up with a reasonable test case quickly, but maybe you can
> see if that can trigger bad behavior?
>
> -Peff

> On Thu, Oct 12, 2017 at 08:18:37PM -0400, Jeff King wrote:
> 
> > Fix this by entering the conditional only when we actually
> > see whitespace. We can apply this also to the
> > IGNORE_WHITESPACE change. That code path isn't buggy
> > (because it falls through to returning the next
> > non-whitespace byte), but it makes the logic more clear if
> > we only bother to look at whitespace flags after seeing that
> > the next byte is whitespace.
> 
> I think there actually _is_ a bug in that code path, but it's unrelated
> to this one. If you have whitespace at the end of the buffer, then we'd
> advance *cp until it matches *endp, and then return whatever is at *endp
> (which is nonsense, or probably a NUL) rather than returning "-1".
> 
> I'm out of time for tonight and not familiar enough with the color-moved
> code to come up with a reasonable test case quickly, but maybe you can
> see if that can trigger bad behavior?

> So. That leaves me with:
> 
>   - I'm unclear on whether next_byte() is meant to return that trailing
>     NUL or not. I don't think it causes any bugs, but it certainly
>     confused me for a function to take a cp/endp pair of pointers, and
>     then dereference endp. It might be worth either fixing or clarifying
>     with a comment.
> 
>   - Those loops to eat trailing whitespace are doing nothing. I'm not
>     sure if that all works out because next_byte() eats whitespaces or
>     not (I think not, because it doesn't eat whitespace for the
>     IGNORE_WHITESPACE_AT_EOL case). But I'm not quite sure what a test
>     would look like.

> Jeff King <peff@peff.net> writes:
>
>> it does. It just adjusts our "end pointer" to point to the last valid
>> character in the string (rather than one past), which seems to be the
>> convention that those loops (and next_byte) expect.
>
> Yeah I am not sure if I like this comparison at the beginning of the
> function:
>
>         static int next_byte(const char **cp, const char **endp,
>                              const struct diff_options *diffopt)
>         {
>                 int retval;
>
>                 if (*cp > *endp)
>                         return -1;
>
> but it says endp _is_ part of valid input, contrary to my intuition.
>
> And your change to the initialization of ae/be in moved_entry_cmp()
> makes it consistent with it, I think.
>
> But doesn't it mean ae computation in get_string_hash() also needs a
> massaging?

> > Yeah I am not sure if I like this comparison at the beginning of the
> > function:
> >
> >         static int next_byte(const char **cp, const char **endp,
> >                              const struct diff_options *diffopt)
> >         {
> >                 int retval;
> >
> >                 if (*cp > *endp)
> >                         return -1;
> >
> > but it says endp _is_ part of valid input, contrary to my intuition.
> >
> > And your change to the initialization of ae/be in moved_entry_cmp()
> > makes it consistent with it, I think.
> >
> > But doesn't it mean ae computation in get_string_hash() also needs a
> > massaging?
> 
> Ah, forget the last two lines.  You do do the massaging in your
> patch.

> Jeff King <peff@peff.net> writes:
> 
> > it does. It just adjusts our "end pointer" to point to the last valid
> > character in the string (rather than one past), which seems to be the
> > convention that those loops (and next_byte) expect.
> 
> Yeah I am not sure if I like this comparison at the beginning of the
> function:
> 
>         static int next_byte(const char **cp, const char **endp,
>                              const struct diff_options *diffopt)
>         {
>                 int retval;
> 
>                 if (*cp > *endp)
>                         return -1;
> 
> but it says endp _is_ part of valid input, contrary to my intuition.

>
> It's late here, so I'll wait for comments from Stefan and then try to
> wrap it up with a commit message and test tomorrow.
>
> -Peff

>
> +test_expect_success 'clean up whitespace-test colors' '
> +       git config --unset color.diff.oldMoved &&
> +       git config --unset color.diff.newMoved
> +'

> On Thu, Oct 19, 2017 at 1:24 PM, Jeff King <peff@peff.net> wrote:
> 
> >
> > +test_expect_success 'clean up whitespace-test colors' '
> > +       git config --unset color.diff.oldMoved &&
> > +       git config --unset color.diff.newMoved
> > +'
> 
> This could be part of the previous test as
> 
>   test_config color.diff.oldMoved "magenta" &&
>   test_config color.diff.newMoved "cyan" &&
> 
> in the beginning. (That way we also do not pollute the setup,
> but keeping it test local).

> We test that lines with whitespace changes are not found by
> "--color-moved" by default, but are found if "-w" is added.
> Let's add one more twist: a line that has non-whitespace
> changes should not be marked as a pure move.
>
> This is perhaps an obvious case for us to get right (and we
> do), but as we add more whitespace tests, they will form a
> pattern of "make sure this case is a move and this other
> case is not".
>
> Note that we have to add a line to our moved block, since
> having a too-small block doesn't trigger the "moved"
> heuristics.  And we also add a line of context to ensure
> that there's more context lines than moved lines (so the
> diff shows us moving the lines up, rather than moving the
> context down).
>
> Signed-off-by: Jeff King <peff@peff.net>

> Commit fa5ba2c1dd (diff: fix infinite loop with
> --color-moved --ignore-space-change, 2017-10-12) added a
> test to make sure that "--color-moved -b" doesn't run
> forever, but the test in question doesn't actually have any
> moved lines in it.
>
> Let's scrap that test and add a variant of the existing
> "--color-moved -w" test, but this time we'll check that we
> find the move with whitespace changes, but not arbitrary
> whitespace additions.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---

>  test_expect_success 'clean up whitespace-test colors' '
>         git config --unset color.diff.oldMoved &&
>         git config --unset color.diff.newMoved
> @@ -1549,13 +1613,4 @@ test_expect_success 'move detection with submodules' '
>         test_cmp expect decoded_actual
>  '
>
> -test_expect_success 'move detection with whitespace changes' '
> -       test_when_finished "git reset --hard" &&
> -       test_seq 10 >test &&
> -       git add test &&
> -       sed s/3/42/ <test >test.tmp &&
> -       mv test.tmp test &&
> -       git -c diff.colormoved diff --ignore-space-change -- test
> -'

> > +
> > +       git diff HEAD --no-renames --color-moved --color |
> > +               grep -v "index" |
> > +               test_decode_color >actual &&
> 
> The -v index grep makes it future proof (for a new hash)!
> I like that. What I do not like is the pipe at the end of
> git-diff as we certainly want to inspect the return code
> (or for a segfault ;)

> > +       git diff HEAD --no-renames -b --color-moved --color |
> > +               grep -v "index" |
> > +               test_decode_color >actual &&
> 
> Do we need (or rather want) to give --color additionally,
> instead of having --color-moved imply it? I guess this is
> extra carefulness from the "color always" series?

> > -test_expect_success 'move detection with whitespace changes' '
> > -       test_when_finished "git reset --hard" &&
> > -       test_seq 10 >test &&
> > -       git add test &&
> > -       sed s/3/42/ <test >test.tmp &&
> > -       mv test.tmp test &&
> > -       git -c diff.colormoved diff --ignore-space-change -- test
> > -'
> 
> Ok, this is covered above in testing for the unchanged lines (1-5)

> The code for handling whitespace with --color-moved
> represents partial strings as a pair of pointers. There are
> two possible conventions for the end pointer:
>
>   1. It points to the byte right after the end of the
>      string.
>
>   2. It points to the final byte of the string.
>
> But we seem to use both conventions in the code:
>
>   a. we assign the initial pointers from the NUL-terminated
>      string using (1)
>
>   b. we eat trailing whitespace by checking the second
>      pointer for isspace(), which needs (2)
>
>   c. the next_byte() function checks for end-of-string with
>      "if (cp > endp)", which is (2)
>
>   d. in next_byte() we skip past internal whitespace with
>      "while (cp < end)", which is (1)
>
> This creates fewer bugs than you might think, because there
> are some subtle interactions. Because of (a) and (c), we
> always return the NUL-terminator from next_byte(). But all
> of the callers of next_byte() happen to handle that
> gracefully.
>
> Because of the mismatch between (d) and (c), next_byte()
> could accidentally return a whitespace character right at
> endp. But because of the interaction of (a) and (b), we fail
> to actually chomp trailing whitespace, meaning our endp
> _always_ points to a NUL, canceling out the problem.
>
> But that does leave (b) as a real bug: when ignoring
> whitespace only at the end-of-line, we don't correctly trim
> it, and fail to match up lines.
>
> We can fix the whole thing by moving consistently to one
> convention. Since convention (1) is idiomatic in our code
> base, we'll pick that one.
>
> The existing "-w" and "-b" tests continue to pass, and a new
> "--ignore-space-at-eol" shows off the breakage we're fixing.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  diff.c                     | 15 +++++++----
>  t/t4015-diff-whitespace.sh | 67 ++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 77 insertions(+), 5 deletions(-)
>
> diff --git a/diff.c b/diff.c
> index 6fd288420b..09081a207c 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -712,7 +712,7 @@ static int next_byte(const char **cp, const char **endp,
>  {
>         int retval;
>
> -       if (*cp > *endp)
> +       if (*cp >= *endp)
>                 return -1;

>                         while (*cp < *endp && isspace(**cp))
>                                 (*cp)++;
> -                       /* return the first non-ws character via the usual below */
> +                       /*
> +                        * return the first non-ws character via the usual
> +                        * below, unless we ate all of the bytes
> +                        */
> +                       if (*cp >= *endp)
> +                               return -1;

> -               while (ae > ap && isspace(*ae))
> +               while (ae > ap && isspace(ae[-1]))
>                         ae--;
> -               while (be > bp && isspace(*be))
> +               while (be > bp && isspace(be[-1]))
>                         be--;

> @@ -1463,6 +1463,73 @@ test_expect_success 'move detection ignoring whitespace changes' '
>         test_cmp expected actual
>  '
>
> +test_expect_failure 'move detection ignoring whitespace at eol' '
> +       git reset --hard &&
> +       # Lines 6-9 have new eol whitespace, but 9 also has it in the middle
> +       q_to_tab <<-\EOF >lines.txt &&
> +       long line 6Q
> +       long line 7Q
> +       long line 8Q
> +       longQline 9Q
> +       line 1
> +       line 2
> +       line 3
> +       line 4
> +       line 5
> +       EOF
> +
> +       # avoid cluttering the output with complaints about our eol whitespace
> +       test_config core.whitespace -blank-at-eol &&

> > +test_expect_failure 'move detection ignoring whitespace at eol' '
> > +       git reset --hard &&
> > +       # Lines 6-9 have new eol whitespace, but 9 also has it in the middle
> > +       q_to_tab <<-\EOF >lines.txt &&
> > +       long line 6Q
> > +       long line 7Q
> > +       long line 8Q
> > +       longQline 9Q
> > +       line 1
> > +       line 2
> > +       line 3
> > +       line 4
> > +       line 5
> > +       EOF
> > +
> > +       # avoid cluttering the output with complaints about our eol whitespace
> > +       test_config core.whitespace -blank-at-eol &&
> 
> We avoid the eol space change as we want to test the move detection
> without interference. Do we want to test it with that as well?

> [snip]
>
> --- a/t/t4015-diff-whitespace.sh
> +++ b/t/t4015-diff-whitespace.sh
> @@ -1463,6 +1463,73 @@ test_expect_success 'move detection ignoring whitespace changes' '
>  	test_cmp expected actual
>  '
>
> +test_expect_failure 'move detection ignoring whitespace at eol' '

> On Thu, Oct 19, 2017 at 04:29:26PM -0400, Jeff King wrote:
> > [snip]
> >
> > --- a/t/t4015-diff-whitespace.sh
> > +++ b/t/t4015-diff-whitespace.sh
> > @@ -1463,6 +1463,73 @@ test_expect_success 'move detection ignoring whitespace changes' '
> >  	test_cmp expected actual
> >  '
> >
> > +test_expect_failure 'move detection ignoring whitespace at eol' '
> 
> Shouldn't this be test_expect_success? According to the commit
> message "and a new "--ignore-space-at-eol" shows off the breakage
> we're fixing.". I didn't actually run the code so I don't know if
> the test fails or not.

> For computing moved lines, we feed the characters of each
> line into a hash. When we've been asked to ignore
> whitespace, then we pick each character using next_byte(),
> which returns -1 on end-of-string, which it determines using
> the start/end pointers we feed it.
>
> However our check of its return value treats "0" the same as
> "-1", meaning we'd quit if the string has an embedded NUL.

>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I noticed that we make an extra copy of each line here, just to feed it
> to memihash! I guess "-w" is not a critical-performance code path, but
> this could be fixed if we could do memhash() incrementally (e.g., by
> putting the FNV state into a struct and letting callers "add" to it
> incrementally). Maybe an interesting #leftoverbits, though I'd want to
> see timing tests that show it's worth doing.
>

> > This is unlikely to ever come up in practice since our line
> > boundaries generally come from calling strlen() in the first
> > place.
> 
> get_string_hash is called from
>  prepare_entry, which in turn is called from
>   add_lines_to_move_detection or mark_color_as_moved
>    diff_flush_patch_all_file_pairs
> 
> that constructs the arguments in
> diff_flush_patch
>  run_diff
>   run_diff_cmd
>    builtin_diff (part "/* Crazy xdl interfaces.. */")
>     xdi_diff_outf( fn_out_consume as arg!)
>      xdi_diff
>       xdl_diff
>        xdl_call_hunk_func
>         -> fn_out_consume(cb, line, len)
> 
> xdl_call_hunk_func however uses pointer arithmetic instead
> of strlen. So I think this sentence is not a good idea to put in
> the commit message.
> 
> It may not occur in practice, due to binary files detection using
> NUL as a signal, but conceptually our move-colored(!) diffs
> should be compatible with NULs with this patch now.

> On Thu, Oct 19, 2017 at 02:31:20PM -0700, Stefan Beller wrote:
>
>> > This is unlikely to ever come up in practice since our line
>> > boundaries generally come from calling strlen() in the first
>> > place.
>>
>> get_string_hash is called from
>>  prepare_entry, which in turn is called from
>>   add_lines_to_move_detection or mark_color_as_moved
>>    diff_flush_patch_all_file_pairs
>>
>> that constructs the arguments in
>> diff_flush_patch
>>  run_diff
>>   run_diff_cmd
>>    builtin_diff (part "/* Crazy xdl interfaces.. */")
>>     xdi_diff_outf( fn_out_consume as arg!)
>>      xdi_diff
>>       xdl_diff
>>        xdl_call_hunk_func
>>         -> fn_out_consume(cb, line, len)
>>
>> xdl_call_hunk_func however uses pointer arithmetic instead
>> of strlen. So I think this sentence is not a good idea to put in
>> the commit message.
>>
>> It may not occur in practice, due to binary files detection using
>> NUL as a signal, but conceptually our move-colored(!) diffs
>> should be compatible with NULs with this patch now.
>
> Good catch. I just skimmed over all the diff_emit_* functions, which use
> strlen(). But at the bottom is emit_add_line(), which has a real length
> marker from xdiff.

> On Thu, Oct 19, 2017 at 01:04:59AM -0400, Jeff King wrote:
>
>> So. That leaves me with:
>>
>>   - I'm unclear on whether next_byte() is meant to return that trailing
>>     NUL or not. I don't think it causes any bugs, but it certainly
>>     confused me for a function to take a cp/endp pair of pointers, and
>>     then dereference endp. It might be worth either fixing or clarifying
>>     with a comment.
>>
>>   - Those loops to eat trailing whitespace are doing nothing. I'm not
>>     sure if that all works out because next_byte() eats whitespaces or
>>     not (I think not, because it doesn't eat whitespace for the
>>     IGNORE_WHITESPACE_AT_EOL case). But I'm not quite sure what a test
>>     would look like.
>
> I had trouble constructing a test at first, but I think my test lines
> just weren't long enough to trigger the movement heuristics. If I switch
> to something besides seq, I can do:
>
>   # any input that has reasonably sized lines
>   look e | head -50 >file
>   git add file
>
>   perl -i -ne '
>     # pick up lines 20-25 to move to line 40, and
>     # add some trailing whitespace to them
>     if ($. >= 20 && $. <= 25) {
>       s/$/     /;
>       $hold .= $_;
>     } else {
>       print $hold if ($. == 40);
>       print;
>     }
>   ' file
>
>   git diff --color-moved --ignore-space-at-eol
>
> I think that _should_ show the block as moved, but it doesn't. But if I
> apply this patch:
>
> diff --git a/diff.c b/diff.c
> index 93dccd1817..375d9cf447 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -743,8 +743,8 @@ static int moved_entry_cmp(const struct diff_options *diffopt,
>                            const struct moved_entry *b,
>                            const void *keydata)
>  {
> -       const char *ap = a->es->line, *ae = a->es->line + a->es->len;
> -       const char *bp = b->es->line, *be = b->es->line + b->es->len;
> +       const char *ap = a->es->line, *ae = a->es->line + a->es->len - 1;
> +       const char *bp = b->es->line, *be = b->es->line + b->es->len - 1;
>
>         if (!(diffopt->xdl_opts & XDF_WHITESPACE_FLAGS))
>                 return a->es->len != b->es->len  || memcmp(ap, bp, a->es->len);
> @@ -771,7 +771,7 @@ static unsigned get_string_hash(struct emitted_diff_symbol *es, struct diff_opti
>  {
>         if (o->xdl_opts & XDF_WHITESPACE_FLAGS) {
>                 static struct strbuf sb = STRBUF_INIT;
> -               const char *ap = es->line, *ae = es->line + es->len;
> +               const char *ap = es->line, *ae = es->line + es->len - 1;
>                 int c;
>
>                 strbuf_reset(&sb);
>
> it does. It just adjusts our "end pointer" to point to the last valid
> character in the string (rather than one past),

> > @@ -771,7 +771,7 @@ static unsigned get_string_hash(struct emitted_diff_symbol *es, struct diff_opti
> >  {
> >         if (o->xdl_opts & XDF_WHITESPACE_FLAGS) {
> >                 static struct strbuf sb = STRBUF_INIT;
> > -               const char *ap = es->line, *ae = es->line + es->len;
> > +               const char *ap = es->line, *ae = es->line + es->len - 1;
> >                 int c;
> >
> >                 strbuf_reset(&sb);
> >
> > it does. It just adjusts our "end pointer" to point to the last valid
> > character in the string (rather than one past),
> 
> Thanks for spotting. I can send a proper patch with tests if you'd like.