6
\$\begingroup\$

(See the next and second iteration here.)

I have this toy implementation of the diff utility in Java:

com.github.coderodde.diff.Diff.java

package com.github.coderodde.diff;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Diff {

    private static final String NL = "\n";

    public static void main(String[] args) {
        if (args.length != 2) {
            return;
        }

        File oldSourceFile = new File(args[0]);
        File newSourceFile = new File(args[1]);

        BufferedReader oldSourceBufferedReader = null;
        BufferedReader newSourceBufferedReader = null;

        try  {
            oldSourceBufferedReader = 
                    new BufferedReader(new FileReader(oldSourceFile));

            newSourceBufferedReader = 
                    new BufferedReader(new FileReader(newSourceFile));
        } catch (IOException ex) {
            System.err.println("I/O failed: " + ex.getMessage());
            System.exit(1);
        }

        List<String> oldSourceLines = new ArrayList<>();
        List<String> newSourceLines = new ArrayList<>();

        String oldSourceLine;
        String newSourceLine;

        try {
            while ((oldSourceLine = oldSourceBufferedReader.readLine()) != null) {
                oldSourceLines.add(oldSourceLine);
            }

            while ((newSourceLine = newSourceBufferedReader.readLine()) != null) {
                newSourceLines.add(newSourceLine);
            }
        } catch (IOException ex) {
            System.err.println("I/O failed: " + ex.getMessage());
            System.exit(1);
        }

        System.out.println(computeDiff(oldSourceLines, newSourceLines));
    }

    private static String computeDiff(List<String> oldSourceLines,
                                      List<String> newSourceLines) {
        int[][] matrix = computeLongestCommonSubsequenceData(oldSourceLines, 
                                                             newSourceLines);

        return printDiff(matrix, oldSourceLines, newSourceLines);
    }

    private static int[][] computeLongestCommonSubsequenceData(
            List<String> oldSourceLines,
            List<String> newSourceLines) {
        int[][] matrix = new int[oldSourceLines.size() + 1]
                                [newSourceLines.size() + 1];

        for (int i = 1; i <= oldSourceLines.size(); ++i) {
            for (int j = 1; j <= newSourceLines.size(); ++j) {
                if (oldSourceLines.get(i - 1)
                        .equals(newSourceLines.get(j - 1))) {
                    matrix[i][j] = matrix[i - 1][j - 1] + 1;
                } else {
                    matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]);
                }
            }
        }

        return matrix;
    }

    private static String printDiff(int[][] matrix, 
                                    List<String> oldSourceLines,
                                    List<String> newSourceLines) {

        StringBuilder stringBuilder = new StringBuilder();

        printDiff(stringBuilder, 
                  matrix, 
                  oldSourceLines, 
                  newSourceLines, 
                  oldSourceLines.size() - 1, 
                  newSourceLines.size() - 1);

        return stringBuilder.toString();
    }

    private static void printDiff(StringBuilder stringBuilder,
                                  int[][] matrix,
                                  List<String> oldSourceLines,
                                  List<String> newSourceLines,
                                  int i, 
                                  int j) {
        if (i >= 0 
                && j >= 0 
                && oldSourceLines.get(i).equals(newSourceLines.get(j))) {
            printDiff(stringBuilder, 
                      matrix, 
                      oldSourceLines, 
                      newSourceLines, 
                      i - 1, 
                      j - 1);

            stringBuilder.append("  ").append(oldSourceLines.get(i)).append(NL);
        } else if (j > 0 && (i == 0 || matrix[i][j - 1] >= matrix[i - 1][j])) {
            printDiff(stringBuilder,
                      matrix, 
                      oldSourceLines, 
                      newSourceLines, 
                      i, 
                      j - 1);

            stringBuilder.append("+ ").append(newSourceLines.get(j)).append(NL);
        } else if (i > 0 && (j == 0 || matrix[i][j - 1] < matrix[i - 1][j])) {
            printDiff(stringBuilder,
                      matrix, 
                      oldSourceLines, 
                      newSourceLines, 
                      i - 1, 
                      j);

            stringBuilder.append("- ").append(oldSourceLines.get(i)).append(NL);
        }
    }
}

Critique request

What do you think? Would it be better to hide the diff process into a class, for instance?

\$\endgroup\$
1
  • \$\begingroup\$ diff("a\nb\nd\ne\ng"), List.of("a\nc\nd\nf\ng")) returns " a\n- b\n+ c\n- d\n- e\n+ d\n+ f\n g" instead of " a\n- b\n+ c\n d\n- e\n+ f\n g". Is that correct? \$\endgroup\$ Commented Jul 3, 2022 at 21:59

2 Answers 2

4
\$\begingroup\$
private static final String NL = "\n";

I don't think that NL is a particularly good name. Generally it is not needed either. For a system utility, I'd go for System.lineSeparator().

public static void main(String[] args) {

There is a lot of duplicate code in the main method because reading the files is parallelized. Reading the files can be separated out into a a single method so that the duplicate code is not required (in this case just calling readLines would do the same thing I suppose).

if (args.length != 2) {
    return;
}

I'd at least return a message to the user what kind of arguments are required, and then use System.exit() with a return/status code. You do this later on, strangely enough, so symmetry is also missing.

    BufferedReader oldSourceBufferedReader = null;
    BufferedReader newSourceBufferedReader = null;

    try  {
        oldSourceBufferedReader = 
                new BufferedReader(new FileReader(oldSourceFile));

I'd expect try-with-resources to be used here, it would remove a lot of unnecessary code, and would avoid any null handling.

    return printDiff(matrix, oldSourceLines, newSourceLines);

printDiff is a bad name, as the method doesn't actually print anything.

    int[][] matrix = new int[oldSourceLines.size() + 1]
                            [newSourceLines.size() + 1];

Here you can see clearly what happens, but it is unclear from the code why the matrix has the calculated size. Whenever that happens you need code comments.

Furthermore, it seems your matrix is over-dimensioned in both directions by one, as you only index i - 1 and j - 1.

 for (int i = 1; i <= oldSourceLines.size(); ++i) {

Nah, you should always try and use zero based indexing. Whenever you need one more, you can add it when needed. Subtraction always confuses things.

The same goes for ++i. Sometimes people things that ++i is faster, but it is no different than i++ and less clear.

private static void printDiff(StringBuilder stringBuilder,
                              int[][] matrix,
                              List<String> oldSourceLines,
                              List<String> newSourceLines,
                              int i, 
                              int j) {

This is a recursive method, and recursive methods should always be documented. Furthermore, for recursive methods, it is pretty important to make it very clear when the end is reached. I would recommend to check for a negative i and j to quickly return. Also, to make the method more readable, you could simply change i and / or j and then perform the recursion at the end.


Design. Yes, you always need a specific class that you instantiate, so that you can use it from other code without having to use main.

Currently the used algorithm is not described. This is vital for maintainability. Always document the algorithm and / or provide a reference to the method used.

When creating a diff I would strongly suggest to make sure that you don't need to read entire files in memory. Files can be huge after all. Otherwise you may want to limit the file size

\$\endgroup\$
2
  • \$\begingroup\$ Depending on what's being diff'd, I don't think filesize is in most cases a concern. If you wanted a diff of a very huge text file, or even a binary, maybe. Otherwise, I don't see the issue loading everything into memory. \$\endgroup\$ Commented Jul 4, 2022 at 4:48
  • \$\begingroup\$ @ChrisSchneider I'd try and avoid crashes if a large file is selected by accident, at the very least. And diffs of log files can make sense, even if it is a fringe use case. \$\endgroup\$ Commented Jul 4, 2022 at 9:20
5
\$\begingroup\$

Rather than your readLine() loops prefer Files.readAllLines(). This has the side-effect of fixing a problem where your BufferedReader instances are not protected within a try-with-resources block (since no readers will be necessary).

Consider writing an error message if the number of CLI arguments is incorrect. You should probably also System.exit(1); rather than only return, as the latter will make it look like the program succeeded.

printDiff could be better-named as formatDiff since it doesn't actually print.

Otherwise seems fine (though I have not critically examined the inner diff algorithm).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.