Expected Behavior

We need support for generating tree like diffs. Similar to a file system diff where you have folders compared as well as files. In our case, we have groups of groups and we currently create separate diffs for each group. Having hierarchy support will enable us to create a single unified diff for the customer.

Actual Behavior

Hierarchy not supported

Specifications

• Version: 4.0
• Platform: Win/Linux
• Subsystem:

It's nice to have zero-dependency implementations. I think it's possible to split library into 2 or modules:

diff-utils-core
diff-utils-myers
diff-utils-jgit

or (just moving jgit dependency out of core library):

diff-utils
diff-utils-jgit

Describe the bug UnifiedDiffReader.parseUnifiedDiff throws UnifiedDiffParserException on a patch which apparently looks good:

https://raw.githubusercontent.com/bazelbuild/bazel/master/third_party/aws-sdk-auth-lite/patches-vs-1.11.297/01-bazel-strip-unused.patch

To Reproduce Run this program:

String patch = new Scanner(new URL(
    "https://raw.githubusercontent.com/bazelbuild/bazel/master/third_party/aws-sdk-auth-lite/patches-vs-1.11.297/01-bazel-strip-unused.patch"
).openStream(), "UTF-8").useDelimiter("\\A").next();

UnifiedDiffReader.parseUnifiedDiff(new StringBufferInputStream(patch));

Expected behavior

No Exceptions.

Actual behavior

Dec 14, 2020 9:49:46 PM com.github.difflib.unifieddiff.UnifiedDiffReader processLine WARNING: >>> no rule matched \ No newline at end of file Exception in thread "main" com.github.difflib.unifieddiff.UnifiedDiffParserException: expected file start line not found at com.github.difflib.unifieddiff.UnifiedDiffReader.parse(UnifiedDiffReader.java:95) at com.github.difflib.unifieddiff.UnifiedDiffReader.parseUnifiedDiff(UnifiedDiffReader.java:146) ...

System

• Java version: openjdk-11
• Version: 4.9

Notes

:wave: java-diff-utils maintainers again! Here is another corner case I found. The patch comes from the Bazel project, so once again it's OK to include in tests.

Expected Behavior

ResultSet from JDBC converted into Strings and then added to a List should show the same differences as a List = Arrays.asList() created by hand.

When using this (entered by hand)

List<String> listOne = Arrays.asList("MASS_TABLE,ID,NUMBER,22,N,", "MASS_TABLE,ISSUEID,NUMBER,22,Y,", "MASS_TABLE,MODIFIED,NUMBER,22,Y,", "MASS_TABLE,SYSTEMNAME,VARCHAR2,1020,Y,");
List<String> listTwo = Arrays.asList("ATOM_TABLE,ID,NUMBER,22,N,", "ATOM_TABLE,ISSUEID,NUMBER,22,Y,", "ATOM_TABLE,MODIFIED,NUMBER,22,Y,", "ATOM_TABLE,ACRONYM,VARCHAR2,255,Y," );

You will get this when ran through the DiffGenerator:

|~MASS_TABLE~,ID,NUMBER,22,N, | **ATOM_TABLE**,ID,NUMBER,22,N,|
|~MASS_TABLE~,ISSUEID,NUMBER,22,Y, | **ATOM_TABLE**,ISSUEID,NUMBER,22,Y,|
|~MASS_TABLE~,MODIFIED,NUMBER,22,Y, | **ATOM_TABLE**,MODIFIED,NUMBER,22,Y,|
|~MASS_TABLE~,~SYSTEMNAME~,VARCHAR2,~1020~,Y, | **ATOM_TABLE**,**ACRONYM**,VARCHAR2,**255**,Y,|

Actual Behavior

DiffGenerator shows apparently incorrect results.

Example:

("NUMBER" on the first row, and "VARCHAR" on the last row show marks ("**") in front of the word to indicate the difference, but don't show the corresponding marks behind it). Also, as the results go further, some differences will be marked on the first list and no corresponding marks will be shown at all on the second list.

| ~MASS_TABLE~,ID,NUMBER,22,N, | **ATOM_TABLE**,**ID**,**NUMBER,22,N, |
| ~MASS_TABLE~,ISSUEID,NUMBER,22,Y, | ATOM_TABLE,ISSUEID,NUMBER,22,Y, |
| ~MASS_TABLE~,MODIFIED,NUMBER,22,Y, | ATOM_TABLE,MODIFIED,NUMBER,22,Y, |
| ~MASS_TABLE~,SYSTEMNAME,VARCHAR2,~1020~,Y, | ATOM_TABLE,ACRONYM,**VARCHAR2,**255**,Y, |

Steps to Reproduce the Problem

1.Connect to two different Oracle Databases and run a SQL query, saving information as text from ResultSet into different List 2.Compare the two Lists in the DiffGenerator 3.Compare these results to the results when the information is put in by hand and compared using DiffGenerator.

Shows as expected:

  List<String> listOne = Arrays.asList("MASS_TABLE,ID,NUMBER,22,N,", "MASS_TABLE,ISSUEID,NUMBER,22,Y,", "MASS_TABLE,MODIFIED,NUMBER,22,Y,", "MASS_TABLE,SYSTEMNAME,VARCHAR2,1020,Y,");
        List<String> listTwo = Arrays.asList("ATOM_TABLE,ID,NUMBER,22,N,", "ATOM_TABLE,ISSUEID,NUMBER,22,Y,", "ATOM_TABLE,MODIFIED,NUMBER,22,Y,", "ATOM_TABLE,ACRONYM,VARCHAR2,255,Y," );

        DiffRowGenerator generator = DiffRowGenerator.create()
                .showInlineDiffs(true)
                .inlineDiffByWord(true)
                .oldTag(f -> "~")
                .newTag(f -> "**") 
                .build();

        List<DiffRow> diffRowList;

        try {
            diffRowList = generator.generateDiffRows(listOne, listTwo);

            for (DiffRow diffRow : diffRowList) {
                System.out.println("|" + diffRow.getOldLine() + "|" + diffRow.getNewLine() + "|");
            }
        } catch (DiffException e) {
            e.printStackTrace();
        }

Does not show as expected, using database:

...
  List<String> databaseSchemaList = new ArrayList<>();
        try {
            conn = DBHelper.getConnection(databaseName);
            stmt = Objects.requireNonNull(conn).createStatement();
            rs = stmt.executeQuery(query);

            while (rs.next()) {
                int columnCount = rs.getMetaData().getColumnCount();
                StringBuilder rsStringBuilder = new StringBuilder();
                for (int i = 1; i <= columnCount; i++) {
                    Object rsObject = rs.getObject(i);
                    String rsString = (rsObject == null) ? "NULL" : rsObject.toString();
                    rsStringBuilder.append(rsString).append(",");
                }         
                databaseSchemaList.add(rsStringBuilder.toString());
            }
       
        } catch (Exception e) {
            e.printStackTrace();
        } finally {     
            ...
        }
        return databaseSchemaList;   
    }

    private void getComparisonResults(List<String> listOne, List<String> listTwo) {

        DiffRowGenerator generator = DiffRowGenerator.create()
                .showInlineDiffs(true)
                .inlineDiffByWord(true)
                .oldTag(f -> "~") 
                .newTag(f -> "**")
                .build();

        List<DiffRow> diffRowList;

        try {
            diffRowList = generator.generateDiffRows(listOne, listTwo);

            for (DiffRow diffRow : diffRowList) {
                System.out.println("| " + diffRow.getOldLine() + " | " + diffRow.getNewLine() + " |");
            }
      ...
}

 public static void main(String[] args) {

        SchemaComparison schemaComparison = new SchemaComparison();

        //get list from each database
        List<String> aSchemaList = schemaComparison.getDatabaseSchemaList(DatabaseName.A);
        List<String> bSchemaList = schemaComparison.getDatabaseSchemaList(DatabaseName.B);

       //run comparison
        schemaComparison.getComparisonResults(aSchemaList,bSchemaList);

    }

Specifications

• Version: 2.3 SNAPSHOT
• Platform: Windows 7
• Subsystem: Oracle Database 11g, IntelliJ 2018.1

Bumps checkstyle from 8.18 to 8.29.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Expected Behavior

DiffRowGenerator would leave < and > the way they are

Actual Behavior

DiffRowGenerator replaces < and > with their html entities.

Steps to Reproduce the Problem

1. Run DiffRowGenerator.create().generateDiffRows(List.of("<"), List.of("<"))
2. Observe that the resulting String has &lt; instead of <

Specifications

• Version: 4.0
• Platform: Linux
• Subsystem:

Using reportLinesUnchanged is not an option since that means tags are missing if an entire line is added/deleted. Having something like replaceSomeHTMLEntities with default true but optionally disableable would be nice, or being able to supply a general string normalisation function.

If needed/wanted I can PR this.

Describe the bug Update to 4.4 in our JabRef (modularized application) fails. Gradle complains about the module name:

cannot determine module name for /home/travis/.gradle/caches/modules-2/files-2.1/io.github.java-diff-utils/java-diff-utils/4.4/87ebb16140d120da919b62117865954da06981b6/java-diff-utils-4.4.jar
/home/travis/build/JabRef/jabref/src/main/java/org/jabref/gui/mergeentries/DiffHighlighting.java:10: error: package com.github.difflib does not exist

import com.github.difflib.DiffUtils;

To Reproduce Use the 4.4 in a modularized java project For reference, this is the PR which is failing: https://github.com/JabRef/jabref/pull/5594

I tried also to add the parent as well:

 compile 'io.github.java-diff-utils:java-diff-utils-parent:4.4'
  compile 'io.github.java-diff-utils:java-diff-utils:4.4'

Expected behavior No errors

System

• Java version 13
• Version 4.4

I am trying to iterate through the deltas =, however I would like to get list of lines that are common between the two sets of List by checking if (delta.getType() == DeltaType.EQUAL) { }

However I am not able to see how to get this. The JUnit code and test examples do not show this examples. Please help?

Hi,

I have moved from the initial Google diff project to this one as I prefer the package naming convention and the class refactoring. Also thank you for maintaining this library.

The Myers’s algorithm is considered the best for Diff calculation, however it has complexity O(NR) and relies on matrices in order to evaluate all the possibilities.

It is not adapted for large files and has performance issues.

1. A possible first improvement could be to reduce the size of the 2 input string, by removing the common sequence at the start and at the end.

Example: Identify the initial common prefix: org.apache.commons.lang.StringUtils.getCommonPrefix(…) Identify the final common prefix (reverse the string and get common prefix): org.apache.commons.lang.StringUtils.reverse(…) org.apache.commons.lang.StringUtils.getCommonPrefix(…)

Once the Delta are calculated, you could restore the initial and final Delta. (positions of existing Deltas need to be adjusted with the first common Delta)

2. Another possible improvement could be to identify the longest common subsequence (ex: org.apache.commons.text.similarity.LongestCommonSubsequence) and to split the Strings according to this value. Then calculate the Delta on the splitted strings and aggregate them at the end by adjusting the positions and also adding the common longest Delta.

Optimization 1 and 2 can be applied in the same time.

Many thanks, Guillaume

Below an interesting post for potential improvements: https://denisbider.blogspot.com/2019/11/a-better-sliding-matrix-diff-algorithm.html

https://neil.fraser.name/writing/diff/ section 3 mentions post-processing cleanup that https://github.com/google/diff-match-patch applies to the output. Does your library provide something similar?

Hi there, I ran into a problem when I tried to create a unified diff for the creation of a new file, which seams not to be supported by your library right now.

As far as I can see, this feature is very easy to implement and could help others as well.

It requires just a small change in the UnifiedDiffUtils.processDeltas() method, some changes in the method signatures to get the info about the new File creation into the methods and maybe another method to keep calls to old method signature running with default values.

Actually it just those few lines in the main logic that could cover file creation:

if (createNewFile) {
            origStart = 0; // the 0 here will trigger the creation of the new file
 } else {
            origStart = curDelta.getSource().getPosition() + 1 - contextSize;
            // NOTE: +1 to overcome the 0-offset Position
            if (origStart < 1) {
                origStart = 1;
            }
 }

Cheers, Eva

It requires significant digging to figure out how to use the library to generate a simple textual diff between two strings. I suggest adding a handful of example code snippets to the README.md file rather than directing readers to the wiki, which itself redirects to the not particularly compelling examples page.

The examples on the examples page would be more compelling if they included the input and outputs of the snippets.

In short, java-diff-utils assumes that a hunk is a line on its own. I'm parsing the output of git log -p that produces "inline" hunks like that: @@ -4,6 +4,9 @@ import com.github.javaparser.JavaParser; and that is not supported. I have no idea that format is OK with the unidiff specifications but the change to support that hunk format seems minimal.

I am trying to parse a rather large diff file with UnifiedDiff udf = UnifiedDiffReader.parseUnifiedDiff(diff);

It is choking on the file and giving me the error message:

Jul 28, 2022 12:52:33 AM com.github.difflib.unifieddiff.UnifiedDiffReader processLine
WARNING:   >>> no rule matched 
Exception in thread "main" com.github.difflib.unifieddiff.UnifiedDiffParserException: expected file start line not found
	at com.github.difflib.unifieddiff.UnifiedDiffReader.parse(UnifiedDiffReader.java:120)
	at com.github.difflib.unifieddiff.UnifiedDiffReader.parseUnifiedDiff(UnifiedDiffReader.java:191)

The source code shows that the "no rule matched" line is supposed to include the offending line, but in this case that is an empty line. Naturally I want to turn on some finer logging to show some context of the previous lines so I can find the bad line in my diff file. How do I do that?

BTW the error message could be greatly improved by including the line number.

Describe the bug I would expect an implementation of the Myers diff algorithm to behave (at least asymptotically) equal. Unfortunately, this is not the case for this implementation: Starting with ~100k lines that are compared, the time consumption growth heavily (at least more than linear).

You can see this in the following graph:

To Reproduce Steps to reproduce the behavior:

1. Use https://github.com/DaGeRe/diff-benchmark (which contains 414ae6.zip and afdedc.zip which contain data that can be compared)
2. Run [runJavaDiff.sh](https://github.com/DaGeRe/diff-benchmark/blob/main/java-difflib-benchmark/runJavaDiff.sh) and runBashDiff.sh to obtain the measurement values.
3. Copy the measurement data and execute plot.plt to obtain the graph.

Expected behavior The duration of the diff execution should grow linear with count of analyzed lines.

System

• Java version 1.8
• Version 4.11

Describe the bug When comparing two LinkedList-Instances, the performance is very poor. I compared ~1,1 million lines, and VisualVM showed me that several minutes where spent at https://github.com/java-diff-utils/java-diff-utils/blob/bc65f9703c137b3a7d2906eeaf064588dd36c125/java-diff-utils/src/main/java/com/github/difflib/algorithm/myers/MeyersDiff.java#L115. With an ArrayList, this was reduced to a few seconds.

From my point of view, there are two possible solutions:

1. Create a benchmark, refactor this from .get to Iterator-usages and check whether this improves the performance by the benchmark
2. Change to always require ArrayList instead just List, and document this in generateDiffRows to the end users.

To Reproduce I'll create a benchmark if someone would try to refactor .get to Iterator-usages.

Expected behavior This should either run fast or it should be clear that an ArrayList is required.

System

• Java version 1.8, but should happen with every version
• Version 4.11