[lit] Allow boolean expressions in REQUIRES and XFAIL and UNSUPPORTED

[gparker42]

Summary

This change allows the conditions in lit test files (REQUIRES, XFAIL, UNSUPPORTED) to be boolean expressions.

The change is otherwise intended to preserve the behavior of existing conditions in test files. I verified that these test suites run unchanged on OS X: llvm; llvm-lit; swift; clang (after a small patch). Additional test coverage is appreciated.

A condition line is now a comma-separated list of boolean expressions. Comma-separated expressions act as if each expression were on its own condition line:
For REQUIRES, if every expression is true then the test will run.
For UNSUPPORTED, if every expression is false then the test will run.
For XFAIL, if every expression is false then the test is expected to succeed. As a special case "XFAIL: *" expects the test to fail.

Examples:

Test is expected fail on 64-bit Apple simulators and pass everywhere else

XFAIL: x86_64 && apple && !macosx

Test is unsupported on Windows and non-Ubuntu Linux and supported everywhere else

UNSUPPORTED: linux && !ubuntu, system-windows

Syntax:

• '&&', '||', '!', '(', ')'. 'true' is true. 'false' is false.
• Each test feature is a true identifier.
• Substrings of the target triple are true identifiers for UNSUPPORTED and XFAIL, but not for REQUIRES. This matches the current behavior. (FIXME should this be changed?)
• All other identifiers are false.
• Identifiers are [-+=._a-zA-Z0-9]* . This allows all feature variable names used in llvm and clang and swift and libc++ today.

[gparker42]

Added a comment about the new throw from Test.isExpectedToFail().
Fixed the run command for lit/tests/requires-missing.txt.

[probinson]

I'm unqualified to review the Python but one thing in the specification doesn't look right.

For XFAIL, if each expression is False then the test is expected to fail. As a special case "XFAIL: *" also expects the test to fail.

For XFAIL, if each expression is False then the test is expected to *pass*. As a special case "XFAIL: *" expects the test to fail.
The xfail-expr-* tests get this right.

[chapuni]

LGTM. I feel it might be exaggerated, though. :D

Random thoughts:

• Is ',' actually as same as 'or' ?
• Could we use not words but chars like "!" "&&" there?

utils/lit/lit/Test.py

5 ↗

(On Diff #50730)

It is failing on py3.

from lit.BooleanExpression import BooleanExpression

[gparker42]

, acts as or for UNSUPPORTED and XFAIL but as and for REQUIRES. Also I don't think we want to allow things like REQUIRES: (a, b) and c.

I chose the Python syntax for and/or/True/False on the assumption that we might want to allow more Python expressions in the future. (In fact my implementation started that way but it was overkill for my purposes.) Does anyone else have a preference here?

[gparker42]

Fix an import for Python 3.
Remove a duplicate copy of Test.isEarlyTest().

[• ddunbar]

My comments:

1. I am +1 on the change overall, I definitely think this will be nicer to have in place.

2. It would be good to get documentation for this, in docs/CommandGuide/lit.rst. There isn't much description of the "ShTest" format yet, but we should definitely try and improve that.

3. Since the primary clients of lit use "C-family" style boolean operators, I think my preference would be for using || / && / ! / true / false.

4. I find it a bit unfortunate that the semantics for "," aren't the same between XFAIL/UNSUPPORTED and REQUIRES... I'm not sure if this is just so natural that it all works out, or if it would be better to simply require using ||/&& explicitly. Any thoughts here, did you do a survey of what is in use currently? Could we migrate to dropping ','?

5. Would it be worth getting quoted string support? That might give a nice longer term path to having a clean syntax rather than the current identifier regex.

Thanks!

utils/lit/lit/BooleanExpression.py

45 ↗

(On Diff #50899)

This can be lifted out to a global constant to save on the regex compile.

125 ↗

(On Diff #50899)

I would write the tests for the basic parser inline here using the unit test style (see ShUtil.py), it is much more convenient and transparent than using lit for this kind of thing. The ShUtil tests themselves are run by the "tests/shell-parsing.py" test.

[gparker42]

I see 92 test lines using ',' in llvm and clang and swift tests. About half of those of those are XFAILs in llvm, but REQUIRES and UNSUPPORTED are also represented.

Identifiers with '-' are everywhere. (Target triples, for one.) ':' and '/' may in fact be unused; I may have found them previously in tests that had text like "UNSUPPORTED:" in places that weren't FileCheck commands. '=' is used in Swift's tests but we can change that.

[gparker42]

• Changed syntax to C-style ! || && instead of Python-style not or and.
• Removed REQUIRES-ANY (superseding r 271468)
• Removed identifier characters ":" and "/"
• Added identifier characters "." and "+" (used by target triples and libc++)
• Moved BooleanExpression tests to Python unittest.

[• ddunbar]

LGTM, but can you add a section on the format to lit.pod? I know we don't have complete docs on the format, but if you could at least add section on the syntax it would be good.

[gparker42]

I'll do that. docs/TestingGuide.rst needs to be updated too.

[Eugene.Zelenko]

Looks like patch was not committed.

[• ddunbar]

Greg, I assumed you had LLVM commit access and could land this?

[gparker42]

Sorry, haven't had time to commit this yet.

[gparker42]

Belatedly picking this up again.

• Resolved conflicts with custom keyword parser machinery in TestRunner.py
• Updated docs/TestingGuide.rst
• Loosened identifier syntax, in particular to allow more triple substrings like -linux-.

[gparker42]

Add an error message for REQUIRES-ANY: that suggests replacement by a REQUIRES: expression.

[EricWF]

Could you please give me heads up before you commit this so I can be standing by reading to fix the libc++ bots?

Libc++ uses requires any and so if you commit this without allowing libc++ to update it will break all of its builders.

[EricWF]

In an ideal world removing REQUIRES-ANY would be done as a separate change so as to give libc++ time to change.

[gparker42]

Sorry, I thought libc++ had abandoned REQUIRES-ANY in favor of custom parsers. I just pushed the commit a few minutes ago. I'll revert it until we can coordinate better.

[gparker42]

I'll reintroduce REQUIRES-ANY support so there is less disruption for libc++ developers.

[EricWF]

In D18185#654602, @gparker42 wrote:

I'll reintroduce REQUIRES-ANY support so there is less disruption for libc++ developers.

No need. I've already converted libc++ so it no longer uses REQUIRES-ANY. You should
be able to commit this patch know without breaking libc++.

[gparker42]

Reinstate support for REQUIRES-ANY:.

llvm/trunk/docs/TestingGuide.rst

.. code-block:: llvm
   ; AVX2: @test1
   ; AVX2: vpsubusw LCPI0_0(%rip), %xmm0, %xmm0
 
 So, if you're testing for a behaviour that you know is platform-specific or
 depends on special features of sub-architectures, you must add the specific
 triple, test with the specific FileCheck and put it into the specific
 directory that will filter out all other architectures.
 
-REQUIRES and REQUIRES-ANY directive
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-Some tests can be enabled only in specific situation - like having
-debug build. Use ``REQUIRES`` directive to specify those requirements.
+Constraining test execution
+---------------------------
+
+Some tests can be run only in specific configurations, such as
+with debug builds or on particular platforms. Use ``REQUIRES``
+and ``UNSUPPORTED`` to control when the test is enabled.
+
+Some tests are expected to fail. For example, there may be a known bug
+that the test detect. Use ``XFAIL`` to mark a test as an expected failure.
+An ``XFAIL`` test will be successful if its execution fails, and
+will be a failure if its execution succeeds.
 
 .. code-block:: llvm
 
-    ; This test will be only enabled in the build with asserts
+    ; This test will be only enabled in the build with asserts.
     ; REQUIRES: asserts
+    ; This test is disabled on Linux.
+    ; UNSUPPORTED: -linux-
+    ; This test is expected to fail on PowerPC.
+    ; XFAIL: powerpc
+
+``REQUIRES`` and ``UNSUPPORTED`` and ``XFAIL`` all accept a comma-separated
+list of boolean expressions. The values in each expression may be:
+
+- Features added to ``config.available_features`` by 
+  configuration files such as ``lit.cfg``.
+- Substrings of the target triple (``UNSUPPORTED`` and ``XFAIL`` only).
+
+| ``REQUIRES`` enables the test if all expressions are true.
+| ``UNSUPPORTED`` disables the test if any expression is true.
+| ``XFAIL`` expects the test to fail if any expression is true.
+
+As a special case, ``XFAIL: *`` is expected to fail everywhere.
+
+.. code-block:: llvm
 
-You can separate requirements by a comma.
-``REQUIRES`` means all listed requirements must be satisfied.
-``REQUIRES-ANY`` means at least one must be satisfied.
+    ; This test is disabled on Windows,
+    ; and is disabled on Linux, except for Android Linux.
+    ; UNSUPPORTED: windows, linux && !android
+    ; This test is expected to fail on both PowerPC and ARM.
+    ; XFAIL: powerpc || arm
 
-List of features that can be used in ``REQUIRES`` and ``REQUIRES-ANY`` can be
-found in lit.cfg files.
 
 Substitutions
 -------------
 
 Besides replacing LLVM tool names the following substitutions are performed in
 RUN lines:
 
 ``%%``

 To make RUN line writing easier, there are several helper programs. These
 helpers are in the PATH when running tests, so you can just call them using
 their name. For example:
 
 ``not``
    This program runs its arguments and then inverts the result code from it.
    Zero result codes become 1. Non-zero result codes become 0.
 
-Sometimes it is necessary to mark a test case as "expected fail" or
-XFAIL. You can easily mark a test as XFAIL just by including ``XFAIL:``
-on a line near the top of the file. This signals that the test case
-should succeed if the test fails. Such test cases are counted separately
-by the testing tool. To specify an expected fail, use the XFAIL keyword
-in the comments of the test program followed by a colon and one or more
-failure patterns. Each failure pattern can be either ``*`` (to specify
-fail everywhere), or a part of a target triple (indicating the test
-should fail on that platform), or the name of a configurable feature
-(for example, ``loadable_module``). If there is a match, the test is
-expected to fail. If not, the test is expected to succeed. To XFAIL
-everywhere just specify ``XFAIL: *``. Here is an example of an ``XFAIL``
-line:
-
-.. code-block:: llvm
-
-    ; XFAIL: darwin,sun
-
 To make the output more useful, :program:`lit` will scan
 the lines of the test case for ones that contain a pattern that matches
 ``PR[0-9]+``. This is the syntax for specifying a PR (Problem Report) number
 that is related to the test case. The number after "PR" specifies the
 LLVM bugzilla number. When a PR number is specified, it will be used in
 the pass/fail reporting. This is useful to quickly get some context when
 a test fails.
 

llvm/trunk/utils/lit/lit/BooleanExpression.py

+import re
+
+class BooleanExpression:
+    # A simple evaluator of boolean expressions.
+    #
+    # Grammar:
+    #   expr       :: or_expr
+    #   or_expr    :: and_expr ('||' and_expr)*
+    #   and_expr   :: not_expr ('&&' not_expr)*
+    #   not_expr   :: '!' not_expr
+    #                 '(' or_expr ')'
+    #                 identifier
+    #   identifier :: [-+=._a-zA-Z0-9]+
+
+    # Evaluates `string` as a boolean expression.
+    # Returns True or False. Throws a ValueError on syntax error.
+    #
+    # Variables in `variables` are true.
+    # Substrings of `triple` are true.
+    # 'true' is true.
+    # All other identifiers are false.
+    @staticmethod
+    def evaluate(string, variables, triple=""):
+        try:
+            parser = BooleanExpression(string, set(variables), triple)
+            return parser.parseAll()
+        except ValueError as e:
+            raise ValueError(str(e) + ('\nin expression: %r' % string))
+
+    #####
+
+    def __init__(self, string, variables, triple=""):
+        self.tokens = BooleanExpression.tokenize(string)
+        self.variables = variables
+        self.variables.add('true')
+        self.triple = triple
+        self.value = None
+        self.token = None
+
+    # Singleton end-of-expression marker.
+    END = object()
+
+    # Tokenization pattern.
+    Pattern = re.compile(r'\A\s*([()]|[-+=._a-zA-Z0-9]+|&&|\|\||!)\s*(.*)\Z')
+
+    @staticmethod
+    def tokenize(string):
+        while True:
+            m = re.match(BooleanExpression.Pattern, string)
+            if m is None:
+                if string == "":
+                    yield BooleanExpression.END;
+                    return
+                else:
+                    raise ValueError("couldn't parse text: %r" % string)
+
+            token = m.group(1)
+            string = m.group(2)
+            yield token
+
+    def quote(self, token):
+        if token is BooleanExpression.END:
+            return '<end of expression>'
+        else:
+            return repr(token)
+
+    def accept(self, t):
+        if self.token == t:
+            self.token = next(self.tokens)
+            return True
+        else:
+            return False
+
+    def expect(self, t):
+        if self.token == t:
+            if self.token != BooleanExpression.END:
+                self.token = next(self.tokens)
+        else:
+            raise ValueError("expected: %s\nhave: %s" %
+                             (self.quote(t), self.quote(self.token)))
+
+    def isIdentifier(self, t):
+        if (t is BooleanExpression.END or t == '&&' or t == '||' or
+            t == '!' or t == '(' or t == ')'):
+            return False
+        return True
+
+    def parseNOT(self):
+        if self.accept('!'):
+            self.parseNOT()
+            self.value = not self.value
+        elif self.accept('('):
+            self.parseOR()
+            self.expect(')')
+        elif not self.isIdentifier(self.token):
+            raise ValueError("expected: '!' or '(' or identifier\nhave: %s" %
+                             self.quote(self.token))
+        else:
+            self.value = (self.token in self.variables or
+                          self.token in self.triple)
+            self.token = next(self.tokens)
+
+    def parseAND(self):
+        self.parseNOT()
+        while self.accept('&&'):
+            left = self.value
+            self.parseNOT()
+            right = self.value
+            # this is technically the wrong associativity, but it
+            # doesn't matter for this limited expression grammar
+            self.value = left and right
+
+    def parseOR(self):
+        self.parseAND()
+        while self.accept('||'):
+            left = self.value
+            self.parseAND()
+            right = self.value
+            # this is technically the wrong associativity, but it
+            # doesn't matter for this limited expression grammar
+            self.value = left or right
+
+    def parseAll(self):
+        self.token = next(self.tokens)
+        self.parseOR()
+        self.expect(BooleanExpression.END)
+        return self.value
+
+
+#######
+# Tests
+
+import unittest
+
+class TestBooleanExpression(unittest.TestCase):
+    def test_variables(self):
+        variables = {'its-true', 'false-lol-true', 'under_score',
+                     'e=quals', 'd1g1ts'}
+        self.assertTrue(BooleanExpression.evaluate('true', variables))
+        self.assertTrue(BooleanExpression.evaluate('its-true', variables))
+        self.assertTrue(BooleanExpression.evaluate('false-lol-true', variables))
+        self.assertTrue(BooleanExpression.evaluate('under_score', variables))
+        self.assertTrue(BooleanExpression.evaluate('e=quals', variables))
+        self.assertTrue(BooleanExpression.evaluate('d1g1ts', variables))
+
+        self.assertFalse(BooleanExpression.evaluate('false', variables))
+        self.assertFalse(BooleanExpression.evaluate('True', variables))
+        self.assertFalse(BooleanExpression.evaluate('true-ish', variables))
+        self.assertFalse(BooleanExpression.evaluate('not_true', variables))
+        self.assertFalse(BooleanExpression.evaluate('tru', variables))
+
+    def test_triple(self):
+        triple = 'arch-vendor-os'
+        self.assertTrue(BooleanExpression.evaluate('arch-', {}, triple))
+        self.assertTrue(BooleanExpression.evaluate('ar', {}, triple))
+        self.assertTrue(BooleanExpression.evaluate('ch-vend', {}, triple))
+        self.assertTrue(BooleanExpression.evaluate('-vendor-', {}, triple))
+        self.assertTrue(BooleanExpression.evaluate('-os', {}, triple))
+        self.assertFalse(BooleanExpression.evaluate('arch-os', {}, triple))
+
+    def test_operators(self):
+        self.assertTrue(BooleanExpression.evaluate('true || true', {}))
+        self.assertTrue(BooleanExpression.evaluate('true || false', {}))
+        self.assertTrue(BooleanExpression.evaluate('false || true', {}))
+        self.assertFalse(BooleanExpression.evaluate('false || false', {}))
+
+        self.assertTrue(BooleanExpression.evaluate('true && true', {}))
+        self.assertFalse(BooleanExpression.evaluate('true && false', {}))
+        self.assertFalse(BooleanExpression.evaluate('false && true', {}))
+        self.assertFalse(BooleanExpression.evaluate('false && false', {}))
+
+        self.assertFalse(BooleanExpression.evaluate('!true', {}))
+        self.assertTrue(BooleanExpression.evaluate('!false', {}))
+
+        self.assertTrue(BooleanExpression.evaluate('   ((!((false) ))   ) ', {}))
+        self.assertTrue(BooleanExpression.evaluate('true && (true && (true))', {}))
+        self.assertTrue(BooleanExpression.evaluate('!false && !false && !! !false', {}))
+        self.assertTrue(BooleanExpression.evaluate('false && false || true', {}))
+        self.assertTrue(BooleanExpression.evaluate('(false && false) || true', {}))
+        self.assertFalse(BooleanExpression.evaluate('false && (false || true)', {}))
+
+    # Evaluate boolean expression `expr`.
+    # Fail if it does not throw a ValueError containing the text `error`.
+    def checkException(self, expr, error):
+        try:
+            BooleanExpression.evaluate(expr, {})
+            self.fail("expression %r didn't cause an exception" % expr)
+        except ValueError as e:
+            if -1 == str(e).find(error):
+                self.fail(("expression %r caused the wrong ValueError\n" +
+                           "actual error was:\n%s\n" +
+                           "expected error was:\n%s\n") % (expr, e, error))
+        except BaseException as e:
+            self.fail(("expression %r caused the wrong exception; actual " + 
+                      "exception was: \n%r") % (expr, e))
+
+    def test_errors(self):
+        self.checkException("ba#d",
+                            "couldn't parse text: '#d'\n" +
+                            "in expression: 'ba#d'")
+
+        self.checkException("true and true",
+                            "expected: <end of expression>\n" +
+                            "have: 'and'\n" +
+                            "in expression: 'true and true'")
+
+        self.checkException("|| true",
+                            "expected: '!' or '(' or identifier\n" +
+                            "have: '||'\n" +
+                            "in expression: '|| true'")
+
+        self.checkException("true &&",
+                            "expected: '!' or '(' or identifier\n" +
+                            "have: <end of expression>\n" +
+                            "in expression: 'true &&'")
+
+        self.checkException("",
+                            "expected: '!' or '(' or identifier\n" +
+                            "have: <end of expression>\n" +
+                            "in expression: ''")
+
+        self.checkException("*",
+                            "couldn't parse text: '*'\n" +
+                            "in expression: '*'")
+
+        self.checkException("no wait stop",
+                            "expected: <end of expression>\n" +
+                            "have: 'wait'\n" +
+                            "in expression: 'no wait stop'")
+
+        self.checkException("no-$-please",
+                            "couldn't parse text: '$-please'\n" +
+                            "in expression: 'no-$-please'")
+
+        self.checkException("(((true && true) || true)",
+                            "expected: ')'\n" +
+                            "have: <end of expression>\n" +
+                            "in expression: '(((true && true) || true)'")
+
+        self.checkException("true (true)",
+                            "expected: <end of expression>\n" +
+                            "have: '('\n" +
+                            "in expression: 'true (true)'")
+
+        self.checkException("( )",
+                            "expected: '!' or '(' or identifier\n" +
+                            "have: ')'\n" +
+                            "in expression: '( )'")
+
+if __name__ == '__main__':
+    unittest.main()

llvm/trunk/utils/lit/lit/Test.py

 import os
 from xml.sax.saxutils import escape
 from json import JSONEncoder
 
+from lit.BooleanExpression import BooleanExpression
+
 # Test result codes.
 
 class ResultCode(object):
     """Test result codes."""
 
     # We override __new__ and __getnewargs__ to ensure that pickling still
     # provides unique ResultCode objects in any particular instance.
     _instances = {}

 class Test:
     """Test - Information on a single test instance."""
 
     def __init__(self, suite, path_in_suite, config, file_path = None):
         self.suite = suite
         self.path_in_suite = path_in_suite
         self.config = config
         self.file_path = file_path
-        # A list of conditions under which this test is expected to fail. These
-        # can optionally be provided by test format handlers, and will be
-        # honored when the test result is supplied.
+
+        # A list of conditions under which this test is expected to fail.
+        # Each condition is a boolean expression of features and target
+        # triple parts. These can optionally be provided by test format
+        # handlers, and will be honored when the test result is supplied.
         self.xfails = []
+
+        # A list of conditions that must be satisfied before running the test.
+        # Each condition is a boolean expression of features. All of them
+        # must be True for the test to run.
+        # FIXME should target triple parts count here too?
+        self.requires = []
+
+        # A list of conditions that prevent execution of the test.
+        # Each condition is a boolean expression of features and target
+        # triple parts. All of them must be False for the test to run.
+        self.unsupported = []
+
         # The test result, once complete.
         self.result = None
 
     def setResult(self, result):
         if self.result is not None:
             raise ValueError("test result already set")
         if not isinstance(result, Result):
             raise ValueError("unexpected result type")
 
         self.result = result
 
         # Apply the XFAIL handling to resolve the result exit code.
+        try:
             if self.isExpectedToFail():
                 if self.result.code == PASS:
                     self.result.code = XPASS
                 elif self.result.code == FAIL:
                     self.result.code = XFAIL
+        except ValueError as e:
+            # Syntax error in an XFAIL line.
+            self.result.code = UNRESOLVED
+            self.result.output = str(e)
         
     def getFullName(self):
         return self.suite.config.name + ' :: ' + '/'.join(self.path_in_suite)
 
     def getFilePath(self):
         if self.file_path:
             return self.file_path
         return self.getSourcePath()
 
     def getSourcePath(self):
         return self.suite.getSourcePath(self.path_in_suite)
 
     def getExecPath(self):
         return self.suite.getExecPath(self.path_in_suite)
 
     def isExpectedToFail(self):
         """
         isExpectedToFail() -> bool
 
         Check whether this test is expected to fail in the current
         configuration. This check relies on the test xfails property which by
         some test formats may not be computed until the test has first been
         executed.
+        Throws ValueError if an XFAIL line has a syntax error.
         """
 
+        features = self.config.available_features
+        triple = getattr(self.suite.config, 'target_triple', "")
+
         # Check if any of the xfails match an available feature or the target.
         for item in self.xfails:
             # If this is the wildcard, it always fails.
             if item == '*':
                 return True
 
-            # If this is an exact match for one of the features, it fails.
-            if item in self.config.available_features:
+            # If this is a True expression of features and target triple parts,
+            # it fails.
+            try:
+                if BooleanExpression.evaluate(item, features, triple):
                     return True
+            except ValueError as e:
+                raise ValueError('Error in XFAIL list:\n%s' % str(e))
 
-            # If this is a part of the target triple, it fails.
-            if item and item in self.suite.config.target_triple:
-                return True
+        return False
+
+    def isWithinFeatureLimits(self):
+        """
+        isWithinFeatureLimits() -> bool
+
+        A test is within the feature limits set by run_only_tests if
+        1. the test's requirements ARE satisfied by the available features
+        2. the test's requirements ARE NOT satisfied after the limiting
+           features are removed from the available features
+
+        Throws ValueError if a REQUIRES line has a syntax error.
+        """
+
+        if not self.config.limit_to_features:
+            return True  # No limits. Run it.
+
+        # Check the requirements as-is (#1)
+        if self.getMissingRequiredFeatures():
+            return False
 
+        # Check the requirements after removing the limiting features (#2)
+        featuresMinusLimits = [f for f in self.config.available_features
+                               if not f in self.config.limit_to_features]
+        if not self.getMissingRequiredFeaturesFromList(featuresMinusLimits):
             return False
 
+        return True
+
+    def getMissingRequiredFeaturesFromList(self, features):
+        try:
+            return [item for item in self.requires
+                    if not BooleanExpression.evaluate(item, features)]
+        except ValueError as e:
+            raise ValueError('Error in REQUIRES list:\n%s' % str(e))
+
+    def getMissingRequiredFeatures(self):
+        """
+        getMissingRequiredFeatures() -> list of strings
+
+        Returns a list of features from REQUIRES that are not satisfied."
+        Throws ValueError if a REQUIRES line has a syntax error.
+        """
+
+        features = self.config.available_features
+        return self.getMissingRequiredFeaturesFromList(features)
+
+    def getUnsupportedFeatures(self):
+        """
+        getUnsupportedFeatures() -> list of strings
+
+        Returns a list of features from UNSUPPORTED that are present
+        in the test configuration's features or target triple.
+        Throws ValueError if an UNSUPPORTED line has a syntax error.
+        """
+
+        features = self.config.available_features
+        triple = getattr(self.suite.config, 'target_triple', "")
+
+        try:
+            return [item for item in self.unsupported
+                    if BooleanExpression.evaluate(item, features, triple)]
+        except ValueError as e:
+            raise ValueError('Error in UNSUPPORTED list:\n%s' % str(e))
+
     def isEarlyTest(self):
         """
         isEarlyTest() -> bool
 
         Check whether this test should be executed early in a particular run.
         This can be used for test suites with long running tests to maximize
         parallelism or where it is desirable to surface their failures early.
         """

llvm/trunk/utils/lit/lit/TestRunner.py

 from __future__ import absolute_import
 import os, signal, subprocess, sys
 import re
 import platform
 import tempfile
 import threading
 
 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):
         self.command = command
         self.message = message
 
 kIsWindows = platform.system() == 'Windows'
 

 
 
 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 value. Ex 'XFAIL:'
+    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
     LIST = 2
-    CUSTOM = 3
+    BOOLEAN_EXPR = 3
+    CUSTOM = 4
+
+    @staticmethod
+    def allowedKeywordSuffixes(value):
+        return { ParserKind.TAG:          ['.'],
+                 ParserKind.COMMAND:      [':'],
+                 ParserKind.LIST:         [':'],
+                 ParserKind.BOOLEAN_EXPR: [':'],
+                 ParserKind.CUSTOM:       [':', '.']
+               } [value]
+
+    @staticmethod
+    def str(value):
+        return { ParserKind.TAG:          'TAG',
+                 ParserKind.COMMAND:      'COMMAND',
+                 ParserKind.LIST:         'LIST',
+                 ParserKind.BOOLEAN_EXPR: 'BOOLEAN_EXPR',
+                 ParserKind.CUSTOM:       'CUSTOM'
+               } [value]
 
 
 class IntegratedTestKeywordParser(object):
     """A parser for LLVM/Clang style integrated test scripts.
 
     keyword: The keyword to parse for. It must end in either '.' or ':'.
     kind: An value of ParserKind.
     parser: A custom parser. This value may only be specified with
             ParserKind.CUSTOM.
     """
     def __init__(self, keyword, kind, parser=None, initial_value=None):
-        if not keyword.endswith('.') and not keyword.endswith(':'):
-            raise ValueError("keyword '%s' must end with either '.' or ':' "
-                             % keyword)
-        if keyword.endswith('.') and kind in \
-                [ParserKind.LIST, ParserKind.COMMAND]:
-            raise ValueError("Keyword '%s' should end in ':'" % keyword)
+        allowedSuffixes = ParserKind.allowedKeywordSuffixes(kind)
+        if len(keyword) == 0 or keyword[-1] not in allowedSuffixes:
+            if len(allowedSuffixes) == 1:
+                raise ValueError("Keyword '%s' of kind '%s' must end in '%s'"
+                                 % (keyword, ParserKind.str(kind),
+                                    allowedSuffixes[0]))
+            else:
+                raise ValueError("Keyword '%s' of kind '%s' must end in "
+                                 " one of '%s'"
+                                 % (keyword, ParserKind.str(kind),
+                                    ' '.join(allowedSuffixes)))
 
-        elif keyword.endswith(':') and kind in [ParserKind.TAG]:
-            raise ValueError("Keyword '%s' should end in '.'" % keyword)
         if parser is not None and kind != ParserKind.CUSTOM:
             raise ValueError("custom parsers can only be specified with "
                              "ParserKind.CUSTOM")
         self.keyword = keyword
         self.kind = kind
         self.parsed_lines = []
         self.value = initial_value
         self.parser = parser
 
         if kind == ParserKind.COMMAND:
             self.parser = self._handleCommand
         elif kind == ParserKind.LIST:
             self.parser = self._handleList
+        elif kind == ParserKind.BOOLEAN_EXPR:
+            self.parser = self._handleBooleanExpr
         elif kind == ParserKind.TAG:
-            if not keyword.endswith('.'):
-                raise ValueError("keyword '%s' should end with '.'" % keyword)
             self.parser = self._handleTag
         elif kind == ParserKind.CUSTOM:
             if parser is None:
                 raise ValueError("ParserKind.CUSTOM requires a custom parser")
             self.parser = parser
         else:
             raise ValueError("Unknown kind '%s'" % kind)
 
     def parseLine(self, line_number, line):
+        try:
             self.parsed_lines += [(line_number, line)]
             self.value = self.parser(line_number, line, self.value)
+        except ValueError as e:
+            raise ValueError(str(e) + ("\nin %s directive on test line %d" %
+                                       (self.keyword, line_number)))
 
     def getValue(self):
         return self.value
 
     @staticmethod
     def _handleTag(line_number, line, output):
         """A helper for parsing TAG type keywords"""
         return (not line.strip() or output)
class IntegratedTestKeywordParser(object):
     @staticmethod
     def _handleList(line_number, line, output):
         """A parser for LIST type keywords"""
         if output is None:
             output = []
         output.extend([s.strip() for s in line.split(',')])
         return output
 
+    @staticmethod
+    def _handleBooleanExpr(line_number, line, output):
+        """A parser for BOOLEAN_EXPR type keywords"""
+        if output is None:
+            output = []
+        output.extend([s.strip() for s in line.split(',')])
+        # Evaluate each expression to verify syntax.
+        # We don't want any results, just the raised ValueError.
+        for s in output:
+            if s != '*':
+                BooleanExpression.evaluate(s, [])
+        return output
+
+    @staticmethod
+    def _handleRequiresAny(line_number, line, output):
+        """A custom parser to transform REQUIRES-ANY: into REQUIRES:"""
+
+        # Extract the conditions specified in REQUIRES-ANY: as written.
+        conditions = []
+        IntegratedTestKeywordParser._handleList(line_number, line, conditions)
+
+        # Output a `REQUIRES: a || b || c` expression in its place.
+        expression = ' || '.join(conditions)
+        IntegratedTestKeywordParser._handleBooleanExpr(line_number,
+                                                       expression, output)
+        return output
 
 def parseIntegratedTestScript(test, additional_parsers=[],
                               require_script=True):
     """parseIntegratedTestScript - Scan an LLVM/Clang style integrated test
     script and extract the lines to 'RUN' as well as 'XFAIL' and 'REQUIRES'
-    'REQUIRES-ANY' and 'UNSUPPORTED' information.
+    and 'UNSUPPORTED' information.
 
     If additional parsers are specified then the test is also scanned for the
     keywords they specify and all matches are passed to the custom parser.
 
     If 'require_script' is False an empty script
     may be returned. This can be used for test formats where the actual script
     is optional or ignored.
     """
-    # Collect the test lines from the script.
-    sourcepath = test.getSourcePath()
+
+    # Install the built-in keyword parsers.
     script = []
-    requires = []
-    requires_any = []
-    unsupported = []
     builtin_parsers = [
         IntegratedTestKeywordParser('RUN:', ParserKind.COMMAND,
                                     initial_value=script),
-        IntegratedTestKeywordParser('XFAIL:', ParserKind.LIST,
+        IntegratedTestKeywordParser('XFAIL:', ParserKind.BOOLEAN_EXPR,
                                     initial_value=test.xfails),
-        IntegratedTestKeywordParser('REQUIRES:', ParserKind.LIST,
-                                    initial_value=requires),
-        IntegratedTestKeywordParser('REQUIRES-ANY:', ParserKind.LIST,
-                                    initial_value=requires_any),
-        IntegratedTestKeywordParser('UNSUPPORTED:', ParserKind.LIST,
-                                    initial_value=unsupported),
+        IntegratedTestKeywordParser('REQUIRES:', ParserKind.BOOLEAN_EXPR,
+                                    initial_value=test.requires),
+        IntegratedTestKeywordParser('REQUIRES-ANY:', ParserKind.CUSTOM,
+                                    IntegratedTestKeywordParser._handleRequiresAny, 
+                                    initial_value=test.requires), 
+        IntegratedTestKeywordParser('UNSUPPORTED:', ParserKind.BOOLEAN_EXPR,
+                                    initial_value=test.unsupported),
         IntegratedTestKeywordParser('END.', ParserKind.TAG)
     ]
     keyword_parsers = {p.keyword: p for p in builtin_parsers}
+    
+    # Install user-defined additional parsers.
     for parser in additional_parsers:
         if not isinstance(parser, IntegratedTestKeywordParser):
             raise ValueError('additional parser must be an instance of '
                              'IntegratedTestKeywordParser')
         if parser.keyword in keyword_parsers:
             raise ValueError("Parser for keyword '%s' already exists"
                              % parser.keyword)
         keyword_parsers[parser.keyword] = parser
         
+    # Collect the test lines from the script.
+    sourcepath = test.getSourcePath()
     for line_number, command_type, ln in \
             parseIntegratedTestScriptCommands(sourcepath,
                                               keyword_parsers.keys()):
         parser = keyword_parsers[command_type]
         parser.parseLine(line_number, ln)
         if command_type == 'END.' and parser.getValue() is True:
             break
 
     # Verify the script contains a run line.
     if require_script and not script:
         return lit.Test.Result(Test.UNRESOLVED, "Test has no run line!")
 
     # Check for unterminated run lines.
     if script and script[-1][-1] == '\\':
         return lit.Test.Result(Test.UNRESOLVED,
                                "Test has unterminated run lines (with '\\')")
 
-    # Check that we have the required features:
-    missing_required_features = [f for f in requires
-                                 if f not in test.config.available_features]
+    # Enforce REQUIRES:
+    missing_required_features = test.getMissingRequiredFeatures()
     if missing_required_features:
         msg = ', '.join(missing_required_features)
         return lit.Test.Result(Test.UNSUPPORTED,
-                               "Test requires the following features: %s"
-                               % msg)
-    requires_any_features = [f for f in requires_any
-                             if f in test.config.available_features]
-    if requires_any and not requires_any_features:
-        msg = ' ,'.join(requires_any)
-        return lit.Test.Result(Test.UNSUPPORTED,
-                               "Test requires any of the following features: "
-                               "%s" % msg)
-    unsupported_features = [f for f in unsupported
-                            if f in test.config.available_features]
+                               "Test requires the following unavailable "
+                               "features: %s" % msg)
+
+    # Enforce UNSUPPORTED:
+    unsupported_features = test.getUnsupportedFeatures()
     if unsupported_features:
         msg = ', '.join(unsupported_features)
         return lit.Test.Result(
             Test.UNSUPPORTED,
-            "Test is unsupported with the following features: %s" % msg)
+            "Test does not support the following features "
+            "and/or targets: %s" % msg)
 
-    unsupported_targets = [f for f in unsupported
-                           if f in test.suite.config.target_triple]
-    if unsupported_targets:
-        return lit.Test.Result(
-            Test.UNSUPPORTED,
-            "Test is unsupported with the following triple: %s" % (
-             test.suite.config.target_triple,))
-
-    if test.config.limit_to_features:
-        # Check that we have one of the limit_to_features features in requires.
-        limit_to_features_tests = [f for f in test.config.limit_to_features
-                                   if f in requires]
-        if not limit_to_features_tests:
-            msg = ', '.join(test.config.limit_to_features)
-            return lit.Test.Result(
-                Test.UNSUPPORTED,
-                "Test requires one of the limit_to_features features %s" % msg)
+    # Enforce limit_to_features.
+    if not test.isWithinFeatureLimits():
+        return lit.Test.Result(Test.UNSUPPORTED,
+                               "Test does not require any of the features "
+                               "specified in limit_to_features: %s" % msg)
+
     return script
 
 
 def _runShTest(test, litConfig, useExternalSh, script, tmpBase):
     # Create the output directory if it does not already exist.
     lit.util.mkdir_p(os.path.dirname(tmpBase))
 
     execdir = os.path.dirname(test.getExecPath())

llvm/trunk/utils/lit/tests/Inputs/shtest-format/requires-missing.txt

-RUN: true
-REQUIRES: a-missing-feature
+# REQUIRES with a false clause. Test should not run.
+REQUIRES: true
+REQUIRES: a-missing-feature, true
+REQUIRES: true
+RUN: false

llvm/trunk/utils/lit/tests/Inputs/shtest-format/requires-present.txt

+# REQUIRES with only true clauses. Test should run.
+REQUIRES: a-present-feature, true, !not-true
+REQUIRES: true
 RUN: true
-REQUIRES: a-present-feature

llvm/trunk/utils/lit/tests/Inputs/shtest-format/requires-star.txt

+# '*' only works in XFAIL
+REQUIRES: *
+RUN: false

llvm/trunk/utils/lit/tests/Inputs/shtest-format/requires-triple.txt

+# REQUIRES line that uses target triple, which doesn't work. Test should not run
+REQUIRES: x86_64
+RUN: false

llvm/trunk/utils/lit/tests/Inputs/shtest-format/unsupported-expr-false.txt

+# UNSUPPORTED with only false clauses. Test should run.
+UNSUPPORTED: false
+UNSUPPORTED: false, not-true
+UNSUPPORTED: false
+UNSUPPORTED: still-not-true
+UNSUPPORTED: false
+UNSUPPORTED: false
+UNSUPPORTED: false
+RUN: true

llvm/trunk/utils/lit/tests/Inputs/shtest-format/unsupported-expr-true.txt

+# UNSUPPORTED with a true clause. Test should not run.
+UNSUPPORTED: false
+UNSUPPORTED: false, false, false, _64-unk && a-present-feature, false
+RUN: false

llvm/trunk/utils/lit/tests/Inputs/shtest-format/unsupported-star.txt

+# '*' only works in XFAIL
+UNSUPPORTED: *
+RUN: false

llvm/trunk/utils/lit/tests/Inputs/shtest-format/xfail-expr-false.txt

+# XFAIL with only false clauses. Test should run.
+XFAIL: false, a-missing-feature || ! a-present-feature || ! x86_64, false
+RUN: true

llvm/trunk/utils/lit/tests/Inputs/shtest-format/xfail-expr-true.txt

+# XFAIL with a true clause. Test should not run.
+XFAIL: false
+XFAIL: false, a-present-feature && ! a-missing-feature && x86_64
+RUN: false

llvm/trunk/utils/lit/tests/boolean-parsing.py

+# Test the boolean expression parser
+# used for REQUIRES and UNSUPPORTED and XFAIL
+
+# RUN: %{python} -m lit.BooleanExpression

llvm/trunk/utils/lit/tests/shtest-format.py

 # CHECK-NEXT: line 2: failed test output on stdout
 
 # CHECK: UNRESOLVED: shtest-format :: no-test-line.txt
 # CHECK: PASS: shtest-format :: pass.txt
 # CHECK: UNSUPPORTED: shtest-format :: requires-any-missing.txt
 # CHECK: PASS: shtest-format :: requires-any-present.txt
 # CHECK: UNSUPPORTED: shtest-format :: requires-missing.txt
 # CHECK: PASS: shtest-format :: requires-present.txt
+# CHECK: UNRESOLVED: shtest-format :: requires-star.txt
+# CHECK: UNSUPPORTED: shtest-format :: requires-triple.txt
+# CHECK: PASS: shtest-format :: unsupported-expr-false.txt
+# CHECK: UNSUPPORTED: shtest-format :: unsupported-expr-true.txt
+# CHECK: UNRESOLVED: shtest-format :: unsupported-star.txt
 # CHECK: UNSUPPORTED: shtest-format :: unsupported_dir/some-test.txt
+# CHECK: PASS: shtest-format :: xfail-expr-false.txt
+# CHECK: XFAIL: shtest-format :: xfail-expr-true.txt
 # CHECK: XFAIL: shtest-format :: xfail-feature.txt
 # CHECK: XFAIL: shtest-format :: xfail-target.txt
 # CHECK: XFAIL: shtest-format :: xfail.txt
 # CHECK: XPASS: shtest-format :: xpass.txt
 # CHECK-NEXT: *** TEST 'shtest-format :: xpass.txt' FAILED ***
 # CHECK-NEXT: Script
 # CHECK-NEXT: --
 # CHECK-NEXT: true
 # CHECK-NEXT: --
 # CHECK: Testing Time
 
 # CHECK: Unexpected Passing Tests (1)
 # CHECK: shtest-format :: xpass.txt
 
 # CHECK: Failing Tests (3)
 # CHECK: shtest-format :: external_shell/fail.txt
 # CHECK: shtest-format :: external_shell/fail_with_bad_encoding.txt
 # CHECK: shtest-format :: fail.txt
 
-# CHECK: Expected Passes    : 5
-# CHECK: Expected Failures  : 3
-# CHECK: Unsupported Tests  : 3
-# CHECK: Unresolved Tests   : 1
+# CHECK: Expected Passes    : 7
+# CHECK: Expected Failures  : 4
+# CHECK: Unsupported Tests  : 5
+# CHECK: Unresolved Tests   : 3
 # CHECK: Unexpected Passes  : 1
 # CHECK: Unexpected Failures: 3

llvm/trunk/utils/lit/tests/unit/TestRunner.py

class TestIntegratedTestKeywordParser(unittest.TestCase):
 
     def test_custom(self):
         parsers = self.make_parsers()
         self.parse_test(parsers)
         custom_parser = self.get_parser(parsers, 'MY_CUSTOM:')
         value = custom_parser.getValue()
         self.assertItemsEqual(value, ['a', 'b', 'c'])
 
+    def test_bad_keywords(self):
+        def custom_parse(line_number, line, output):
+            return output
+        
+        try:
+            IntegratedTestKeywordParser("TAG_NO_SUFFIX", ParserKind.TAG),
+            self.fail("TAG_NO_SUFFIX failed to raise an exception")
+        except ValueError as e:
+            pass
+        except BaseException as e:
+            self.fail("TAG_NO_SUFFIX raised the wrong exception: %r" % e)
+
+        try:
+            IntegratedTestKeywordParser("TAG_WITH_COLON:", ParserKind.TAG),
+            self.fail("TAG_WITH_COLON: failed to raise an exception")
+        except ValueError as e:
+            pass
+        except BaseException as e:
+            self.fail("TAG_WITH_COLON: raised the wrong exception: %r" % e)
+
+        try:
+            IntegratedTestKeywordParser("LIST_WITH_DOT.", ParserKind.LIST),
+            self.fail("LIST_WITH_DOT. failed to raise an exception")
+        except ValueError as e:
+            pass
+        except BaseException as e:
+            self.fail("LIST_WITH_DOT. raised the wrong exception: %r" % e)
+
+        try:
+            IntegratedTestKeywordParser("CUSTOM_NO_SUFFIX",
+                                        ParserKind.CUSTOM, custom_parse),
+            self.fail("CUSTOM_NO_SUFFIX failed to raise an exception")
+        except ValueError as e:
+            pass
+        except BaseException as e:
+            self.fail("CUSTOM_NO_SUFFIX raised the wrong exception: %r" % e)
+
+        # Both '.' and ':' are allowed for CUSTOM keywords.
+        try:
+            IntegratedTestKeywordParser("CUSTOM_WITH_DOT.",
+                                        ParserKind.CUSTOM, custom_parse),
+        except BaseException as e:
+            self.fail("CUSTOM_WITH_DOT. raised an exception: %r" % e)
+        try:
+            IntegratedTestKeywordParser("CUSTOM_WITH_COLON:",
+                                        ParserKind.CUSTOM, custom_parse),
+        except BaseException as e:
+            self.fail("CUSTOM_WITH_COLON: raised an exception: %r" % e)
+
+        try:
+            IntegratedTestKeywordParser("CUSTOM_NO_PARSER:",
+                                        ParserKind.CUSTOM),
+            self.fail("CUSTOM_NO_PARSER: failed to raise an exception")
+        except ValueError as e:
+            pass
+        except BaseException as e:
+            self.fail("CUSTOM_NO_PARSER: raised the wrong exception: %r" % e)
 
 if __name__ == '__main__':
     TestIntegratedTestKeywordParser.load_keyword_parser_lit_tests()
     unittest.main(verbosity=2)