kpdecker / jsdiff

A javascript text differencing implementation.
BSD 3-Clause "New" or "Revised" License
7.69k stars 491 forks source link

parsePatch chokes on some valid patches #524

Closed ExplodingCabbage closed 2 weeks ago

ExplodingCabbage commented 4 weeks ago

I stumbled across this while working on adding code to preserve leading and trailing garbage.

Test script that runs fine on v5.2.0 but crashes on master:

diff = require('.');

patchstr =         'diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md\n' +
        'index 20b807a..4a96aff 100644\n' +
        '--- a/CONTRIBUTING.md\n' +
        '+++ b/CONTRIBUTING.md\n' +
        '@@ -2,6 +2,8 @@\n' +
        ' \n' +
        ' ## Pull Requests\n' +
        ' \n' +
        '+bla bla bla\n' +
        '+\n' +
        ' We also accept [pull requests][pull-request]!\n' +
        ' \n' +
        ' Generally we like to see pull requests that\n' +
        'diff --git a/README.md b/README.md\n' +
        'index 06eebfa..40919a6 100644\n' +
        '--- a/README.md\n' +
        '+++ b/README.md\n' +
        '@@ -1,5 +1,7 @@\n' +
        ' # jsdiff\n' +
        ' \n' +
        '+foo\n' +
        '+\n' +
        ' [![Build Status](https://secure.travis-ci.org/kpdecker/jsdiff.svg)](http://travis-ci.org/kpdecker/jsdiff)\n' +
        ' [![Sauce Test Status](https://saucelabs.com/buildstatus/jsdiff)](https://saucelabs.com/u/jsdiff)\n' +
        ' \n' +
        "@@ -225,3 +227,5 @@ jsdiff deviates from the published algorithm in a couple of ways that don't affe\n" +
        ' \n' +
        " * jsdiff keeps track of the diff for each diagonal using a linked list of change objects for each diagonal, rather than the historical array of furthest-reaching D-paths on each diagonal contemplated on page 8 of Myers's paper.\n" +
        ' * jsdiff skips considering diagonals where the furthest-reaching D-path would go off the edge of the edit graph. This dramatically reduces the time cost (from quadratic to linear) in cases where the new text just appends or truncates content at the end of the old text.\n' +
        '+\n' +
        '+bar\n'

diff.parsePatch(diff.formatPatch(diff.parsePatch(patchstr)));

I need to add a test to catch this, then fix it, before anything else.

ExplodingCabbage commented 4 weeks ago

Aha - I haven't introduced a new bug, just revealed an existing one. Adding {strict: true} to the parsePatch calls lets me repro on v5.2.0.

Still needs fixing.