[lit] Implement "-r" option for builtin "diff" command + a test using that.

[Dor1s]

Summary

That would allow to recursively compare directories in tests using
"diff -r" on Windows in a similar way as it can be done on Linux or Mac.

[vsk]

I haven't looked too closely, but I think this test might fail:

RUN: mkdir -p %t/A %t/B
RUN: touch %t/A/only_in_a %t/B/only_in_b
RUN: not diff -r %t/A %t/B

If there are tests for lit itself, it might be useful to check this one in.

[Dor1s]

In D41776#968593, @vsk wrote:

I haven't looked too closely, but I think this test might fail:

RUN: mkdir -p %t/A %t/B
RUN: touch %t/A/only_in_a %t/B/only_in_b
RUN: not diff -r %t/A %t/B

If there are tests for lit itself, it might be useful to check this one in.

That's a great point! I should add names for non empty files as well! Also will look for TestRunner tests, thanks Vedant!

[morehouse]

utils/lit/lit/TestRunner.py

378

Does os.walk have well-defined ordering? What if contents of dir1 are visited in a different order than dir2?

386

Do we also want to compare file names?

E.g., what if we have

dir1/a  # Contents: 12345
dir2/b  # Contents: 12345

Won't this implementation consider dir1 and dir2 to be the same?

[zturner]

Since a user of lit is going to expect diff -r to "just work", then it needs to match the semantics of what the tool diff -r actually does. The patch here will print "something" and return an error code if there are differences, but it won't print the same thing as the actual diff utility when used with -r. I think if we implement this in lit, we need to make the output look the same. For example, a person might try to use this to verify that two directories differ only in one file. (for example, one has an a.txt and another has a b.txt). So they might run diff -r and filecheck the output against this:

Only in d:\foo: a.txt
Only in d:\bar: b.txt

But the code here won't print that. In fact, if the *contents* of a.txt and b.txt are the same but just the names are different, then I think (from inspecting this patch) that the diff would actually succeed, since it just appends file contents to a buffer.

So I think if we want to implement diff -r here, you need to make sure it exactly matches the output of the unix tool for various inputs.

[Dor1s]

Fix a bug pointed out by vsk + add a test for lit.

[Dor1s]

Thanks for the comments, I'll work more on it in order to follow "diff" utility default output.

utils/lit/lit/TestRunner.py

378

I believe so, but either way it looks like this needs more work in order to provide the same output as a regular "diff" utility does.

386

Right, thanks!

[Dor1s]

Implement the same output as produced by regular diff utility + added tests for that.

[Dor1s]

Use None for empty directories instead of a fake string.

[Dor1s]

Please take a look :)

utils/lit/lit/TestRunner.py

378

Resolved now, as I put filepaths and contents into a dict.

utils/lit/tests/Inputs/shtest-shell/diff-r.txt

27

I was hoping to use FileCheck --check-prefix and different prefixes, but for some reason I'm getting weird errors, e.g.:

...
$ "not" "diff" "-r" "/usr/local/google/home/mmoroz/Projects/llvm/build/utils/lit/tests/Inputs/shtest-shell/Output/diff-r.txt.tmp/dir1" "/usr/local/google/home/mmoroz/Projects/llvm/build/utils/lit/tests/Inputs/shtest-shell/Output/diff-r.txt.tmp/dir2"
$ "FileCheck" "--check-prefix=ERROR1" "/usr/local/google/home/mmoroz/Projects/llvm/build/utils/lit/tests/Inputs/shtest-shell/diff-r.txt"
# command stderr:
/usr/local/google/home/mmoroz/Projects/llvm/build/utils/lit/tests/Inputs/shtest-shell/diff-r.txt:27:11: error: expected string not found in input
# ERROR1: Only in %t/dir1: dir1unique
          ^
<stdin>:1:1: note: scanning from here
Only in /usr/local/google/home/mmoroz/Projects/llvm/build/utils/lit/tests/Inputs/shtest-shell/Output/diff-r.txt.tmp/dir1: dir1unique
^
<stdin>:1:106: note: possible intended match here
Only in /usr/local/google/home/mmoroz/Projects/llvm/build/utils/lit/tests/Inputs/shtest-shell/Output/diff-r.txt.tmp/dir1: dir1unique
                                                                                                         ^

error: command failed with exit status: 1

I'm fine to proceed with grep, if reviewers don't mind.

[zturner]

utils/lit/tests/Inputs/shtest-shell/diff-r.txt

27

You can't use substitutions like %t in a check prefix. Those are expanded only in run lines. The general solution for this is to wrap that part in a regex. So for example, instead of this:

ERROR1: Only in %t/dir1: dir1unique

You would write this:

ERROR1: Only in {{.*}}dir1: dir1unique

That said, I would really prefer if we could use the check lines instead of grep, since that's the canonical way of writing tests and there are other advantages as well (CHECK-NEXT, etc)

[Dor1s]

Use logical OR for exitCode assignment to avoid overwriting its value from 1 to 0.

[Dor1s]

Use FileCheck with different prefixes for different errors instead of grep.

[Dor1s]

utils/lit/tests/Inputs/shtest-shell/diff-r.txt

27

That totally works! Thank you, Zachary!

I've tried that before as well, but I put string into double-quotes, so the regex didn't work for me neither :)

[zturner]

utils/lit/lit/TestRunner.py

383–385

Would it be more efficient to just save off the paths instead of reading the lines up front? You can imagine a case where a folder has a ton of files, but the other folder has none of those files. Reading all those lines up front and making a strong reference to them is going to consume a huge amount of memory. But you might not even need the contents of the file because the file might not exist in the other folder anyway, in which case you can early out on it. It seems like all you need to do is build up a tuple like (dirname, child_dirs, files), where child_dirs is itself a list of tuples of the exact same form. But don't read the contents until you know you have to do the comparison, and throw the contents away before you do the next comparison, to guarantee your'e not loading an entire directory tree's worth of file contents into memory at once.

395

s/compate/compare/

418

s/compate/compare/

424–427

This looks a little strange to me. stdout.write doesn't add a newline does it? Wouldn't this mash everything together on a single line? Any reason not to use print here?

432

s/compate/compare/

[Dor1s]

An optimized version that works, but needs some cleanup + more tests.

[Dor1s]

utils/lit/lit/TestRunner.py

383–385

Agreed. Implemented a solution that does that and follows behavior of GNU diffutils better. I'll do a cleanup a bit later and ask for another round of review :)

424–427

Good catch, print sounds good. Thanks!

[Dor1s]

Did a cleanup + extended the test.

[Dor1s]

By the way, I'm having some troubles running shtest-shell on Linux. Is there any proper way to run it, or maybe we have a test bot that can do it for me? In the worst case I can try that on Windows, but it would take some extra time...

[zturner]

This looks good to me. One minor suggestion is to make sure this works with Python 3. If you're already confident it does, you don't have to do anything. But we do have at least one bot running Python 3, and i've been hit with Py3 specific errors before and had to fix it while the bot was broken. Either way, up to you. Thanks for working on this!

In D41776#970072, @Dor1s wrote:

By the way, I'm having some troubles running shtest-shell on Linux. Is there any proper way to run it, or maybe we have a test bot that can do it for me? In the worst case I can try that on Windows, but it would take some extra time...

Someone else will need to answer this one, as I have really no idea :-/ Sorry

[Dor1s]

Thanks for the review and for the heads up. I've spent enough time trying to set up a work environment on Windows, but still can't say that it works fine. I'll land this and see how it goes on the bots.

[Dor1s]

In D41776#971253, @Dor1s wrote:

Thanks for the review and for the heads up. I've spent enough time trying to set up a work environment on Windows, but still can't say that it works fine. I'll land this and see how it goes on the bots.

Well, I figured out some troubles locally, will fix it before landing.

[Dor1s]

Split the tests in a way that they would really work

[Dor1s]

1. For some reason, it appears to be important to use stdout.write instead of print, so replacing these.

2. Commands implemented in TestRunner.py can't be used as part of a pipeline, this is why there are several diff-error-* tests. I don't see a better way to test negative scenarios rather than split my test into diff-r-error-* and check their output in shtest-shell.py as it's done for existing tests

[Dor1s]

Committing, fingers crossed.

test/tools/llvm-cov/multithreaded-report.test

 # Test "report" command with and without multiple threads.
 
-# Temporarily disable the test on Windows as it doesn't support "diff -r".
-REQUIRES: shell
-
 RUN: llvm-cov report -num-threads=1 \
 RUN:   -path-equivalence=/tmp,%S/Inputs \
 RUN:   -instr-profile %S/Inputs/multithreaded_report/main.profdata \
 RUN:   %S/Inputs/multithreaded_report/main.covmapping > %t.1.report
 
 RUN: llvm-cov report -num-threads=10 \
 RUN:   -path-equivalence=/tmp,%S/Inputs \
 RUN:   -instr-profile %S/Inputs/multithreaded_report/main.profdata \

utils/lit/lit/TestRunner.py

for dir in args:
                 stderr.write("Error: 'mkdir' command failed, %s\n" % str(err))
                 exitCode = 1
     return ShellCommandResult(cmd, "", stderr.getvalue(), exitCode, False)
 
 def executeBuiltinDiff(cmd, cmd_shenv):
     """executeBuiltinDiff - Compare files line by line."""
     args = expand_glob_expressions(cmd.args, cmd_shenv.cwd)[1:]
     try:
-        opts, args = getopt.gnu_getopt(args, "wbu", ["strip-trailing-cr"])
+        opts, args = getopt.gnu_getopt(args, "wbur", ["strip-trailing-cr"])
     except getopt.GetoptError as err:
         raise InternalShellError(cmd, "Unsupported: 'diff':  %s" % str(err))
 
-    filelines, filepaths = ([] for i in range(2))
+    filelines, filepaths, dir_trees = ([] for i in range(3))
     ignore_all_space = False
     ignore_space_change = False
     unified_diff = False
+    recursive_diff = False
     strip_trailing_cr = False
     for o, a in opts:
         if o == "-w":
             ignore_all_space = True
         elif o == "-b":
             ignore_space_change = True
         elif o == "-u":
             unified_diff = True
+        elif o == "-r":
+            recursive_diff = True
         elif o == "--strip-trailing-cr":
             strip_trailing_cr = True
         else:
             assert False, "unhandled option"
 
     if len(args) != 2:
         raise InternalShellError(cmd, "Error:  missing or extra operand")
 
-    stderr = StringIO()
-    stdout = StringIO()
-    exitCode = 0
-    try:
-        for file in args:
-            if not os.path.isabs(file):
-                file = os.path.realpath(os.path.join(cmd_shenv.cwd, file))
-            filepaths.append(file)
+    def getDirTree(path, basedir=""):
+        # Tree is a tuple of form (dirname, child_trees).
+        # An empty dir has child_trees = [], a file has child_trees = None.
+        child_trees = []
+        for dirname, child_dirs, files in os.walk(os.path.join(basedir, path)):
+            for child_dir in child_dirs:
+                child_trees.append(getDirTree(child_dir, dirname))
+            for filename in files:
+                child_trees.append((filename, None))
+            return path, sorted(child_trees)
+
+    def compareTwoFiles(filepaths):
+        filelines = []
+        for file in filepaths:
             with open(file, 'r') as f:
                 filelines.append(f.readlines())
 
+        exitCode = 0 
         def compose2(f, g):
             return lambda x: f(g(x))
 
         f = lambda x: x
         if strip_trailing_cr:
             f = compose2(lambda line: line.rstrip('\r'), f)
         if ignore_all_space or ignore_space_change:
             ignoreSpace = lambda line, separator: separator.join(line.split())
             ignoreAllSpaceOrSpaceChange = functools.partial(ignoreSpace, separator='' if ignore_all_space else ' ')
             f = compose2(ignoreAllSpaceOrSpaceChange, f)
 
         for idx, lines in enumerate(filelines):
             filelines[idx]= [f(line) for line in lines]
 
         func = difflib.unified_diff if unified_diff else difflib.context_diff
         for diff in func(filelines[0], filelines[1], filepaths[0], filepaths[1]):
             stdout.write(diff)
             exitCode = 1
+        return exitCode
+
+    def printDirVsFile(dir_path, file_path):
+        if os.path.getsize(file_path):
+            msg = "File %s is a directory while file %s is a regular file"
+        else:
+            msg = "File %s is a directory while file %s is a regular empty file"
+        print(msg % (dir_path, file_path))
+
+    def printFileVsDir(file_path, dir_path):
+        if os.path.getsize(file_path):
+            msg = "File %s is a regular file while file %s is a directory"
+        else:
+            msg = "File %s is a regular empty file while file %s is a directory"
+        print(msg % (file_path, dir_path))
+
+    def printOnlyIn(basedir, path, name):
+        print("Only in %s: %s" % (os.path.join(basedir, path), name))
+
+    def compareDirTrees(dir_trees, base_paths=["", ""]):
+        # Dirnames of the trees are not checked, it's caller's responsibility,
+        # as top-level dirnames are always different. Base paths are important
+        # for doing os.walk, but we don't put it into tree's dirname in order
+        # to speed up string comparison below and while sorting in getDirTree.
+        left_tree, right_tree = dir_trees[0], dir_trees[1]
+        left_base, right_base = base_paths[0], base_paths[1]
+
+        # Compare two files or report file vs. directory mismatch.
+        if left_tree[1] is None and right_tree[1] is None:
+            return compareTwoFiles([os.path.join(left_base, left_tree[0]),
+                                    os.path.join(right_base, right_tree[0])])
+
+        if left_tree[1] is None and right_tree[1] is not None:
+            printFileVsDir(os.path.join(left_base, left_tree[0]),
+                           os.path.join(right_base, right_tree[0]))
+            return 1
+
+        if left_tree[1] is not None and right_tree[1] is None:
+            printDirVsFile(os.path.join(left_base, left_tree[0]),
+                           os.path.join(right_base, right_tree[0]))
+            return 1
+
+        # Compare two directories via recursive use of compareDirTrees.
+        exitCode = 0
+        left_names = [node[0] for node in left_tree[1]]
+        right_names = [node[0] for node in right_tree[1]]
+        l, r = 0, 0
+        while l < len(left_names) and r < len(right_names):
+            # Names are sorted in getDirTree, rely on that order.
+            if left_names[l] < right_names[r]:
+                exitCode = 1
+                printOnlyIn(left_base, left_tree[0], left_names[l])
+                l += 1
+            elif left_names[l] > right_names[r]:
+                exitCode = 1
+                printOnlyIn(right_base, right_tree[0], right_names[r])
+                r += 1
+            else:
+                exitCode |= compareDirTrees([left_tree[1][l], right_tree[1][r]],
+                                            [os.path.join(left_base, left_tree[0]),
+                                            os.path.join(right_base, right_tree[0])])
+                l += 1
+                r += 1
+
+        # At least one of the trees has ended. Report names from the other tree.
+        while l < len(left_names):
+            exitCode = 1
+            printOnlyIn(left_base, left_tree[0], left_names[l])
+            l += 1
+        while r < len(right_names):
+            exitCode = 1
+            printOnlyIn(right_base, right_tree[0], right_names[r])
+            r += 1
+        return exitCode
+
+    stderr = StringIO()
+    stdout = StringIO()
+    exitCode = 0
+    try:
+        for file in args:
+            if not os.path.isabs(file):
+                file = os.path.realpath(os.path.join(cmd_shenv.cwd, file))
+    
+            if recursive_diff:
+                dir_trees.append(getDirTree(file))
+            else:
+                filepaths.append(file)
+
+        if not recursive_diff:
+            exitCode = compareTwoFiles(filepaths)
+        else:
+            exitCode = compareDirTrees(dir_trees)
+
     except IOError as err:
         stderr.write("Error: 'diff' command failed, %s\n" % str(err))
         exitCode = 1
 
     return ShellCommandResult(cmd, stdout.getvalue(), stderr.getvalue(), exitCode, False)
 
 def executeBuiltinRm(cmd, cmd_shenv):
     """executeBuiltinRm - Removes (deletes) files or directories."""

utils/lit/tests/Inputs/shtest-shell/diff-r.txt

+# Check recursive diff ("diff -r").
+
+# Create two directories for further comparison.
+# RUN: rm -rf %t/dir1 %t/dir2
+# RUN: mkdir -p %t/dir1 %t/dir2
+
+# Create same files in both of the dirs.
+# RUN: echo "hello" > %t/dir1/f1
+# RUN: echo "hello" > %t/dir2/f1
+
+# Create same subdirectories with same contents.
+# RUN: mkdir -p %t/dir1/subdir %t/dir2/subdir
+# RUN: echo "12345" > %t/dir1/subdir/f01
+# RUN: echo "12345" > %t/dir2/subdir/f01
+# RUN: echo -e "xxx\nzzz\nyyy" > %t/dir1/subdir/f02
+# RUN: echo -e "xxx\nzzz\nyyy" > %t/dir2/subdir/f02
+
+# Create empty subdirectories with same names.
+# RUN: mkdir -p %t/dir1/empty_subdir %t/dir2/empty_subdir
+# RUN: diff -r %t/dir1 %t/dir2
+
+# Add two empty files with different names, "diff -r" should fail.
+# RUN: touch %t/dir1/dir1unique
+# RUN: touch %t/dir2/dir2unique
+# RUN: not diff -r %t/dir1 %t/dir2 | FileCheck --check-prefix=ERROR1 %s
+# ERROR1: Only in {{.*}}/dir1: dir1unique
+# ERROR1: Only in {{.*}}/dir2: dir2unique
+# RUN: rm %t/dir1/dir1unique %t/dir2/dir2unique
+
+# Same filenames but different content, "diff -r" should fail.
+# RUN: echo "00000" > %t/dir2/subdir/f01
+# RUN: not diff -r %t/dir1 %t/dir2 | FileCheck --check-prefix=ERROR2 %s
+# ERROR2: diff -r {{.*}}/dir1/subdir/f01 {{.*}}/dir2/subdir/f01
+# ERROR2: < 12345
+# ERROR2: > 00000
+
+# Restore the original contents.
+# RUN: echo "12345" > %t/dir2/subdir/f01
+
+# An extra file in one of the directories, "diff -r" should fail.
+# RUN: touch %t/dir2/extrafile
+# RUN: not diff -r %t/dir1 %t/dir2 | FileCheck --check-prefix=ERROR3 %s
+# ERROR3: Only in {{.*}}/dir2: extrafile
+
+# Non-empty extra file, "diff -r" should fail.
+# RUN: echo "content" > %t/dir2/extrafile
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR4 %s
+# ERROR4: Only in {{.*}}/dir2: extrafile
+# RUN: rm %t/dir2/extrafile
+
+# Empty extra directory, "diff -r" should fail.
+# RUN: mkdir -p %t/dir1/extra_subdir
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR5 %s
+# ERROR5: Only in {{.*}}/dir1: extra_subdir
+
+# Directory vs. empty file mismatch, diff -r should fail.
+# RUN: touch %t/dir2/extra_subdir
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR6 %s
+# ERROR6: File {{.*}}dir1/extra_subdir is a directory while file {{.*}}dir2/extra_subdir is a regular empty file
+
+# Directory vs. non empty file mismatch, diff -r should fail.
+# RUN: echo ZYX > %t/dir2/extra_subdir
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR7 %s
+# ERROR7: File {{.*}}dir1/extra_subdir is a directory while file {{.*}}dir2/extra_subdir is a regular file
+# RUN: rm %t/dir2/extra_subdir
+
+# Non-empty extra directory, diff -r should fail.
+# RUN: mkdir -p %t/dir1/extra_subdir/dir
+# RUN: echo "1337" > %t/dir1/extra_subdir/dir/file
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR8 %s
+# ERROR8: Only in {{.*}}/dir1: extra_subdir
+# RUN: rm -rf %t/dir1/extra_subdir
+
+# Empty file vs directory mismatch, diff -r should fail.
+# RUN: touch %t/dir1/extra_file
+# RUN: mkdir -p %t/dir2/extra_file
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR9 %s
+# ERROR9: File {{.*}}dir1/extra_file is a regular empty file while file {{.*}}dir2/extra_file is a directory
+
+# Non empty file vs directory mismatch, diff -r should fail.
+# RUN: echo qwerty > %t/dir1/extra_file
+# RUN: not diff -r %t/dir1 %t/dir2  | FileCheck --check-prefix=ERROR10 %s
+# ERROR10: File {{.*}}dir1/extra_file is a regular file while file {{.*}}dir2/extra_file is a directory
+# RUN: rm -rf %t/dir1/extra_file %t/dir2/extra_file
+
+# Sanity check for the test directory.
+# RUN: diff -r %t/dir1 %t/dir2
+# RUN: rm -rf %t/dir1 %t/dir2

utils/lit/tests/shtest-shell.py

 # CHECK: FAIL: shtest-shell :: diff-error-6.txt
 # CHECK: *** TEST 'shtest-shell :: diff-error-6.txt' FAILED ***
 # CHECK: $ "diff"
 # CHECK: # command stderr:
 # CHECK: Error:  missing or extra operand
 # CHECK: error: command failed with exit status: 127
 # CHECK: ***
 
+# CHECK: PASS: shtest-shell :: diff-r.txt
+
 # CHECK: FAIL: shtest-shell :: error-0.txt
 # CHECK: *** TEST 'shtest-shell :: error-0.txt' FAILED ***
 # CHECK: $ "not-a-real-command"
 # CHECK: # command stderr:
 # CHECK: 'not-a-real-command': command not found
 # CHECK: error: command failed with exit status: 127
 # CHECK: ***