Teach lit to expand glob expressions

[zturner]

Summary

This is a proposed solution to D30371. libfuzzer and compiler-rt in general often need to pass lists of files as inputs to the tools, frequently involving wildcard expressions, and this is not easy to do portably given the difference in environment between Windows and non-Windows platforms. Usually it involves some hacky call to xargs, but then when you mix find into the equation you run into trouble with Windows tools.

This patch adds a new lit substitution, %[[expr]] which will be treated as a glob expression and replaced in the input. Note that all glob expressions are expanded before doing any other substitutions, and because of this you can use traditional substitutions as part of a glob expression, which allows you to root your paths %S, %T, etc.

A simple test is added to demonstrate the use of the syntax.

[mehdi_amini]

llvm/utils/lit/lit/TestRunner.py

739

Where is tmpDir used?

762

I'm not totally sure about why a loop is needed here? Can't it be done in a single pass?
Also could we write a pattern that would infinite loop this?

I was expecting first to do ln = doDirectSubstitutions(ln) and then process the "glob" expressions.

[zturner]

llvm/utils/lit/lit/TestRunner.py

739

It's not, I meant to remove this.

762

If you have multiple glob expressions in a single line, each iteration will only find the first one, but we need to replace all of them.

You're right, I can probably replace all the "direct" substitutions first.

[mehdi_amini]

llvm/utils/lit/lit/TestRunner.py

762

Right but re.findall or re.finditer would allow to iterate over the expression with a single regex query.
I'm not worried about efficiency, just readability, the iterative algorithm you're using makes me think that there is a "feature" to the iterative mode (like one expansion depends on the previous one), which I don't think is intentional here (having a file named %[[.*]] is what I meant with "infinite loop" earlier.

[zturner]

The reason I didn't use findall or finditer is because they only return the portion inside the capture group, so you lose the information about the original replacement string, making the code to actually replace the outer part a little obnoxious.

[mehdi_amini]

I believe you :)

LGTM then.

[aizatsky]

I am confused you say glob expansion happens before other substitution. Shouldn't it be in the opposite order if you want %[[%T/*]] to work?

[MatzeB]

In my experience being explicit and mention every thing file instead of globbing is more stable and protects against tests failing because of accidental circumstances like files lying around that are not tracked by version control (anymore?). I haven't looked at the specifics of https://reviews.llvm.org/D30371, but are we really adding a new lit feature to simplify a single test using a bad pattern?

[zturner]

This might look like a single test, but this issue has come up repeatedly in compiler-rt and libfuzzer.

here is the list of all tests that have a run line matching the expression RUN: .*\*.*. Note this doesn't catch all instances of using a wildcard.

D:\src\llvm-mono\llvm\lib\Fuzzer\test\dump_coverage.test(3):RUN: xargs sancov -covered-functions LLVMFuzzer-NullDerefTest* %t_workdir/*.sancov | FileCheck %s --check-prefix=SANCOV
D:\src\llvm-mono\llvm\lib\Fuzzer\test\merge.test(10):RUN: cp %tmp/T0/* %tmp/T1/
D:\src\llvm-mono\llvm\lib\Fuzzer\test\merge.test(33):RUN: rm %tmp/T1/*
D:\src\llvm-mono\llvm\lib\Fuzzer\test\merge.test(34):RUN: cp %tmp/T0/* %tmp/T1/
D:\src\llvm-mono\llvm\lib\Fuzzer\test\merge.test(40):RUN: rm %tmp/T1/*
D:\src\llvm-mono\llvm\lib\Fuzzer\test\merge.test(41):RUN: cp %tmp/T0/* %tmp/T1/
D:\src\llvm-mono\llvm\lib\Fuzzer\test\merge.test(51):RUN: rm -rf  %tmp/T1/* %tmp/T2/*
D:\src\llvm-mono\llvm\lib\Fuzzer\test\minimize_crash.test(6):RUN: rm not_minimal_crash minimized-from-* exact_minimized_path
D:\src\llvm-mono\llvm\lib\Fuzzer\test\minimize_crash.test(8):RUN: echo -n 'abcd*xyz' > not_minimal_crash
D:\src\llvm-mono\llvm\test\tools\llvm-cov\llvm-cov.test(11):RUN: cp %p/Inputs/test* .

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior. LLDB (once it starts moving more towards list tests) will definitely need to be doing the same thing. So I don't believe this to be a one-off addition.

[zturner]

In D30380#688936, @zturner wrote:

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior. LLDB (once it starts moving more towards list tests) will definitely need to be doing the same thing. So I don't believe this to be a one-off addition.

s/list/lit/

[MatzeB]

In D30380#688937, @zturner wrote:

In D30380#688936, @zturner wrote:

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior. LLDB (once it starts moving more towards list tests) will definitely need to be doing the same thing. So I don't believe this to be a one-off addition.

s/list/lit/

I still consider it bad design if you don't know what your dynamic are doing/are supposed to be doing. Anyway it's a minor thing so go ahead with this if you must, I just hope people will not start to use this too much.

As for LLDB I would expect it to be complicated enough to want/need a custom lit test plugin anyway in which it can handle all the things it requires. I haven't looked at lldb code yet, maybe it is already using one?

[zturner]

In D30380#688941, @MatzeB wrote:

In D30380#688937, @zturner wrote:

In D30380#688936, @zturner wrote:

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior. LLDB (once it starts moving more towards list tests) will definitely need to be doing the same thing. So I don't believe this to be a one-off addition.

s/list/lit/

I still consider it bad design if you don't know what your dynamic are doing/are supposed to be doing. Anyway it's a minor thing so go ahead with this if you must, I just hope people will not start to use this too much.

As for LLDB I would expect it to be complicated enough to want/need a custom lit test plugin anyway in which it can handle all the things it requires. I haven't looked at lldb code yet, maybe it is already using one?

LLDB doesn't use lit at all, it uses completely different testing infrastructure. It's a longstanding goal to migrate this over to lit.

[mehdi_amini]

In D30380#688941, @MatzeB wrote:

In D30380#688937, @zturner wrote:

In D30380#688936, @zturner wrote:

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior.

That's a reason to look at the filesystem, that's not a reason that explain why a test does not know in advance which file will be generated or need to be looked at. Can you clarify this?

[zturner]

In D30380#688952, @mehdi_amini wrote:

In D30380#688941, @MatzeB wrote:

In D30380#688937, @zturner wrote:

In D30380#688936, @zturner wrote:

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior.

That's a reason to look at the filesystem, that's not a reason that explain why a test does not know in advance which file will be generated or need to be looked at. Can you clarify this?

One example is when the input to a tool is an executable file name, where on Windows you have to suffix it with .exe. You can see this in my earlier comment dump_coverage.test(3). It writes llvm-FuzzerDerefTest* which catches the filename either with or without a .exe suffix.

Other examples include where a test program can take many inputs, and you put all your input files in a single directory. Sure you could write out each one, but this is higher maintenance and much uglier to look at when reading the test. Every time you add or remove an input, you need to go remember to update the test.

[mehdi_amini]

In D30380#688967, @zturner wrote:

In D30380#688952, @mehdi_amini wrote:

In D30380#688941, @MatzeB wrote:

In D30380#688937, @zturner wrote:

In D30380#688936, @zturner wrote:

I don't think it's necessarily fair to classify these tests as poorly designed. dynamic tools, by design, often need to do things with the file system and the tests need to verify this behavior.

That's a reason to look at the filesystem, that's not a reason that explain why a test does not know in advance which file will be generated or need to be looked at. Can you clarify this?

One example is when the input to a tool is an executable file name, where on Windows you have to suffix it with .exe. You can see this in my earlier comment dump_coverage.test(3). It writes llvm-FuzzerDerefTest* which catches the filename either with or without a .exe suffix.

This is statically defined, so it could be solved with a lit expansion %exe_suffix

Other examples include where a test program can take many inputs, and you put all your input files in a single directory. Sure you could write out each one, but this is higher maintenance and much uglier to look at when reading the test. Every time you add or remove an input, you need to go remember to update the test.

Can you point at one such test? I'd be interested to see what kind of test does not need to be changed/updated anyway when adding an input.

[zturner]

+aizatsky and +kcc to comment on sanitizer specific stuff.

[MatzeB]

Other examples include where a test program can take many inputs, and you put all your input files in a single directory. Sure you could write out each one, but this is higher maintenance and much uglier to look at when reading the test. Every time you add or remove an input, you need to go remember to update the test.

The same discussion is going for decades of whether it is fine to use glob constructs in Makefiles (or cmakefiles) to not specify every single source file. I'd say most people think it is a bad idea to use glob there.

[MatzeB]

In D30380#688976, @MatzeB wrote:

Other examples include where a test program can take many inputs, and you put all your input files in a single directory. Sure you could write out each one, but this is higher maintenance and much uglier to look at when reading the test. Every time you add or remove an input, you need to go remember to update the test.

The same discussion is going for decades of whether it is fine to use glob constructs in Makefiles (or cmakefiles) to not specify every single source file. I'd say most people think it is a bad idea to use glob there.

And to give you an example of what can happen if you glob: Today if you run the unittests in llvm lit globs builddir/unittests for executables and runs everything it finds. The result is that when I removed a unittest a while back, the executable would stay on the incremental bots and they happily kept executing an old test and eventually break. This leads to stupid hacks like r261194 (short of fixing it properly and have cmake compile a definite list of unittest executables that need to be run).

[mehdi_amini]

I looked at the fuzzer test that triggered this in the first place: the issue is that it spawns multiple processes that dump their coverage file with the PID in the name. The PID can't be predict in advance obviously...

[rnk]

I don't think we can do this glob expansion in advance. We'd want to do it at the last minute before we do the subprocess.Popen call, to make it behave as consistently as possible with a real shell. If we can't do that, I'd rather keep using find+xargs. It's portable enough for most purposes.

[aizatsky]

PID is one of the reason there's '*' in compiler-rt tests: runtime information is often dumped in <basename>-<pid> files. These files are then fed to analysis tools by using '<basename>-*' shell glob.

If new glob expansion is made before RUN line execution, it won't find any of those files.

[zturner]

Move the globbing closer to the invocation of subprocess.Popen.

[rnk]

llvm/utils/lit/lit/TestRunner.py

147

Why look for double square brackets at all? The lit shell is supposed to be bash compatible, since we use bash on Linux and the internal shell on Windows. Can we just look for '*'?

[zturner]

llvm/utils/lit/lit/TestRunner.py

147

* is not the only character that might indicate the presence of a glob. There's also ?. And character classes in the form of [abc] are also valid glob patterns. We could look for the presence of either of these two characters, but the idea behind the double square brackets was to force the user to acknowledge that they're doing this, as well as to maintain consistency with the existing substitution patterns. So I do believe we need some kind of delimeter that says "Everything inside of here is a glob expression", and from there we just need to decide what is the best choice that allows the full syntax of a glob expression inside, while not interfering with valid filenames.

Now that I've pointed out [abc] though, this raises a concern that %[[Foo[abc]]] would be incorrectly parsed as Foo[abc. I used square braces originally so as not to confuse with %{pathsep}, but since we've already agreed that curly braces are ok and will not interfere with the shell, how about %{{expr}}?

[rnk]

We had some offline discussion about this. I would really like the lit shell to be as much like bash as possible to match test writers' expectations. As Mehdi mentioned, there are cases where an LLVM tool does not generate output in a predictable location, like clang crash recovery. I'd like to test this with regular shell globbing if possible. It sounds like Zach's going to give that a try.

I think we need to look for unescaped '*' and '?' in the lit shell lexer (ShUtil.py), replace that with an unambiguous escape sequence (%{globstart} and %{globquestion} or something), and then evaluate those immediately before Popen.

[zturner]

Look for glob expressions during tokenization but resolve right before launching the command.

[rnk]

lgtm

llvm/utils/lit/lit/ShCommands.py

38

This is a nicer design than what I suggested. :)

llvm/utils/lit/lit/ShUtil.py

101

Seems like a reasonable limitation to me.

[mehdi_amini]

Nice catch @rnk and nice improvements in the end :)

[MatzeB]

Have you tested these changes on a unix system yet? I think we concatenate all the RUN lines together into a single command on unix, so wouldn't that resolve the glob pattern before any of the commands that produce the intermediate files have even run?

I would really like the lit shell to be as much like bash as possible to match test writers' expectations.

+1 (though we should better say posix shell instead of bash)! In any way shell should be a very familiar language and should really be powerful enough for our needs.

llvm/test/Other/lit-globbing.ll

+RUN: echo TA > %T/TA.txt
+RUN: echo TB > %T/TB.txt
+RUN: echo TAB > %T/TAB.txt
+
+RUN: echo %T/TA* | FileCheck -check-prefix=STAR %s
+RUN: echo %T/'TA'* | FileCheck -check-prefix=STAR %s
+RUN: echo %T/T'A'* | FileCheck -check-prefix=STAR %s
+
+RUN: echo %T/T?.txt | FileCheck -check-prefix=QUESTION %s
+RUN: echo %T/'T'?.txt | FileCheck -check-prefix=QUESTION %s
+
+RUN: echo %T/T??.txt | FileCheck -check-prefix=QUESTION2 %s
+RUN: echo %T/'T'??.txt | FileCheck -check-prefix=QUESTION2 %s
+
+RUN: echo 'T*' 'T?.txt' 'T??.txt' | FileCheck -check-prefix=QUOTEDARGS %s
+
+STAR-NOT: TB.txt
+STAR: {{(TA.txt.*TAB.txt|TAB.txt.*TA.txt)}}
+
+QUESTION-NOT: TAB.txt
+QUESTION: {{(TA.txt.*TB.txt|TB.txt.*TA.txt)}}
+
+QUESTION2-NOT: TA.txt
+QUESTION2-NOT: TB.txt
+QUESTION2: TAB.txt
+
+QUOTEDARGS-NOT: .txt
+QUOTEDARGS: T* T?.txt T??.txt

llvm/utils/lit/lit/ShCommands.py

def toShell(self, file):
                 raise NotImplementedError('Unable to quote %r' % arg)
 
         for r in self.redirects:
             if len(r[0]) == 1:
                 file.write("%s '%s'" % (r[0][0], r[1]))
             else:
                 file.write("%s%s '%s'" % (r[0][1], r[0][0], r[1]))
 
+class GlobItem:
+    def __init__(self, pattern):
+        self.pattern = pattern
+
+    def __repr__(self):
+        return self.pattern
+
+    def __eq__(self, other):
+        if not isinstance(other, Command):
+            return False
+
+        return (self.pattern == other.pattern)
+
+    def resolve(self):
+        import glob
+        results = glob.glob(self.pattern)
+        return [self.pattern] if len(results) == 0 else results
+
 class Pipeline:
     def __init__(self, commands, negate=False, pipe_err=False):
         self.commands = commands
         self.negate = negate
         self.pipe_err = pipe_err
 
     def __repr__(self):
         return 'Pipeline(%r, %r, %r)' % (self.commands, self.negate,

llvm/utils/lit/lit/ShUtil.py

 from __future__ import absolute_import
 import itertools
 
 import lit.util
-from lit.ShCommands import Command, Pipeline, Seq
+from lit.ShCommands import Command, GlobItem, Pipeline, Seq
 
 class ShLexer:
     def __init__(self, data, win32Escapes = False):
         self.data = data
         self.pos = 0
         self.end = len(data)
         self.win32Escapes = win32Escapes
 
def lex_arg_fast(self, c):
         # If it has special characters, the fast path failed.
         if ('|' in chunk or '&' in chunk or 
             '<' in chunk or '>' in chunk or
             "'" in chunk or '"' in chunk or
             ';' in chunk or '\\' in chunk):
             return None
         
         self.pos = self.pos - 1 + len(chunk)
-        return chunk
+        return GlobItem(chunk) if '*' in chunk or '?' in chunk else chunk
         
     def lex_arg_slow(self, c):
         if c in "'\"":
             str = self.lex_arg_quoted(c)
         else:
             str = c
+        unquoted_glob_char = False
+        quoted_glob_char = False
         while self.pos != self.end:
             c = self.look()
             if c.isspace() or c in "|&;":
                 break
             elif c in '><':
                 # This is an annoying case; we treat '2>' as a single token so
                 # we don't have to track whitespace tokens.
 
                 # If the parse string isn't an integer, do the usual thing.
                 if not str.isdigit():
                     break
 
                 # Otherwise, lex the operator and convert to a redirection
                 # token.
                 num = int(str)
                 tok = self.lex_one_token()
                 assert isinstance(tok, tuple) and len(tok) == 1
                 return (tok[0], num)                    
-            elif c == '"':
+            elif c == '"' or c == "'":
                 self.eat()
-                str += self.lex_arg_quoted('"')
-            elif c == "'":
-                self.eat()
-                str += self.lex_arg_quoted("'")
+                quoted_arg = self.lex_arg_quoted(c)
+                if '*' in quoted_arg or '?' in quoted_arg:
+                    quoted_glob_char = True
+                str += quoted_arg
             elif not self.win32Escapes and c == '\\':
                 # Outside of a string, '\\' escapes everything.
                 self.eat()
                 if self.pos == self.end:
                     lit.util.warning(
                         "escape at end of quoted argument in: %r" % self.data)
                     return str
                 str += self.eat()
+            elif c in '*?':
+                unquoted_glob_char = True
+                str += self.eat()
             else:
                 str += self.eat()
-        return str
+        # If a quote character is present, lex_arg_quoted will remove the quotes
+        # and append the argument directly.  This causes a problem when the
+        # quoted portion contains a glob character, as the character will no
+        # longer be treated literally.  If glob characters occur *only* inside
+        # of quotes, then we can handle this by not globbing at all, and if
+        # glob characters occur *only* outside of quotes, we can still glob just
+        # fine.  But if a glob character occurs both inside and outside of
+        # quotes this presents a problem.  In practice this is such an obscure
+        # edge case that it doesn't seem worth the added complexity to support.
+        # By adding an assertion, it means some bot somewhere will catch this
+        # and flag the user of a non-portable test (which could almost certainly
+        # be re-written to work correctly without triggering this).
+        assert not (quoted_glob_char and unquoted_glob_char)
+        return GlobItem(str) if unquoted_glob_char else str
 
     def lex_arg_quoted(self, delim):
         str = ''
         while self.pos != self.end:
             c = self.eat()
             if c == delim:
                 return str
             elif c == '\\' and delim == '"':
def parse_command(self):
         while 1:
             tok = self.look()
 
             # EOF?
             if tok is None:
                 break
 
             # If this is an argument, just add it to the current command.
-            if isinstance(tok, str):
+            if isinstance(tok, (str, GlobItem)):
                 args.append(self.lex())
                 continue
 
             # Otherwise see if it is a terminator.
             assert isinstance(tok, tuple)
             if tok[0] in ('|',';','&','||','&&'):
                 break
             

llvm/utils/lit/lit/TestRunner.py

 from __future__ import absolute_import
 import os, signal, subprocess, sys
 import re
 import platform
 import tempfile
 import threading
 
+from lit.ShCommands import GlobItem
 import lit.ShUtil as ShUtil
 import lit.Test as Test
 import lit.util
 from lit.util import to_bytes, to_string
 from lit.BooleanExpression import BooleanExpression
 
 class InternalShellError(Exception):
     def __init__(self, command, message):
def executeShCmd(cmd, shenv, results, timeout=0):
     finalExitCode = _executeShCmd(cmd, shenv, results, timeoutHelper)
     timeoutHelper.cancel()
     timeoutInfo = None
     if timeoutHelper.timeoutReached():
         timeoutInfo = 'Reached timeout of {} seconds'.format(timeout)
 
     return (finalExitCode, timeoutInfo)
 
+def expand_glob_expressions(cmd, args):
+    result = [args[0]]
+    for arg in args[1:]:
+        if isinstance(arg, GlobItem):
+            result.extend(arg.resolve())
+        else:
+            result.append(arg)
+    return result
+
 def quote_windows_command(seq):
     """
     Reimplement Python's private subprocess.list2cmdline for MSys compatibility
 
     Based on CPython implementation here:
       https://hg.python.org/cpython/file/849826a900d2/Lib/subprocess.py#l422
 
     Some core util distributions (MSys) don't tokenize command line arguments
for i,j in enumerate(cmd.commands):
         if kAvoidDevNull:
             for i,arg in enumerate(args):
                 if arg == "/dev/null":
                     f = tempfile.NamedTemporaryFile(delete=False)
                     f.close()
                     named_temp_files.append(f.name)
                     args[i] = f.name
 
+        # Expand all glob expressions
+        args = expand_glob_expressions(j, args)
+
         # On Windows, do our own command line quoting for better compatibility
         # with some core utility distributions.
         if kIsWindows:
             args = quote_windows_command(args)
 
         try:
             procs.append(subprocess.Popen(args, cwd=cmd_shenv.cwd,
                                           executable = executable,
else:
                 ('%:s', sourcepath),
                 ('%:S', sourcedir),
                 ('%:p', sourcedir),
                 ('%:t', tmpBase + '.tmp'),
                 ('%:T', tmpDir),
                 ])
     return substitutions
 
 def applySubstitutions(script, substitutions):
     """Apply substitutions to the script.  Allow full regular expression syntax.
     Replace each matching occurrence of regular expression pattern a with
     substitution b in line ln."""
     def processLine(ln):
         # Apply substitutions
         for a,b in substitutions:
             if kIsWindows:
                 b = b.replace("\\","\\\\")
             ln = re.sub(a, b, ln)
 
         # Strip the trailing newline and any extra whitespace.
         return ln.strip()
     # Note Python 3 map() gives an iterator rather than a list so explicitly
     # convert to list before returning.
     return list(map(processLine, script))
 
 
 class ParserKind(object):
     """
     An enumeration representing the style of an integrated test keyword or
     command.
 
     TAG: A keyword taking no value. Ex 'END.'
     COMMAND: A keyword taking a list of shell commands. Ex 'RUN:'
     LIST: A keyword taking a comma-separated list of values.
     BOOLEAN_EXPR: A keyword taking a comma-separated list of 
         boolean expressions. Ex 'XFAIL:'
     CUSTOM: A keyword with custom parsing semantics.
     """
     TAG = 0
     COMMAND = 1