Add version comparison in BooleanExpression for lit testing

[dstuttard]

Summary

This change updates BooleanExpression (used in REQUIRES or UNSUPPORTED) to have
an additional ability for comparison. For example you can have

REQUIRES: something > <integer>

Where the comparison can be any of the usual ones (<,>,<=,>=,==,!=)

[ldionne]

Something like this would be extremely useful in the libc++ test suite! However, IMO it would be a lot more useful if we could:

1. Expand substitutions in these expressions (do we do that?)
2. Do string matching as well. That way I could do something like REQUIRES: %{stdlib} == libcxx. I wouldn't actually do that exactly, but you get the point.

In fact, after that, I don't think we need the available_versions part of the config anymore. You just add a substitution like %{a-version} and then you just have to check for %{a-version} > 4. WDYT?

[dstuttard]

I don't think substitutions are expanded on REQUIRES and UNSUPPORTED lines.

It's an interesting suggestion though - I'll take a look and see how easy that is.

[dstuttard]

I think it would be quite an invasive change to apply substitutions to lines other than RUN

It would require the following changes:
REQUIRES, UNSUPPORTED etc are dealt with during the parseIntegratedTestScript phase at the moment - that would have to change (increasing execution time - and may surface some issues).
REQUIRES etc are global - whereas substitutions are not - and can be changed as the script runs. What version of the substitution should apply, I guess it could be the context of the actual REQUIRES/UNSUPPORTED (this would require more significant changes to the file though as these would require tracking in the same way as RUN and DEFINE/REDEFINE etc).

I'm not that familiar with this codebase, so I might be wrong.

I could add the ability to compare strings to the current implementation if you are prepared to accept the available_versions addition instead?

[jdenny]

In D154594#4489052, @dstuttard wrote:

REQUIRES etc are global - whereas substitutions are not - and can be changed as the script runs. What version of the substitution should apply, I guess it could be the context of the actual REQUIRES/UNSUPPORTED (this would require more significant changes to the file though as these would require tracking in the same way as RUN and DEFINE/REDEFINE etc).

Is there any reason lit cannot require REQUIRES, XFAIL, etc. to appear before all RUN, DEFINE, and REDEFINE?

About the patch in general....

It seems these directives are heading in the same direction as RUN has been (see the PYTHON directive proposal for an alternative in that case). That is, we're incrementally developing our own full-blown expression language, and we still want more. Could we use python's eval to accept python's syntax instead?

My only concern about using python in this case is that the syntax would likely become more verbose. For example,

XFAIL: target=powerpc{{.*}}, system-darwin

might become

XFAIL-PY: re.match('powerpc.*', lit.target) or lit.has('system-darwin')

However, now I don't have to figure out what , means in the case of XFAIL as it's explicit in python, and I can immediately build arbitrarily complex expressions, including integer and string comparisons. For substitutions, I'm proposing lit.expand in PYTHON directives, and we could use that here too.

As in the case of PYTHON directives, I feel using python would lower the learning curve for lit users, reduce the burden for lit developers and reviewers, and significantly increase the power of these expressions. Again, the syntax would likely have to be more verbose, but that currently seems to me like a minor concern in comparison.

llvm/utils/lit/lit/BooleanExpression.py

+import operator
 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 ')'
-    #                   match_expr
+    #                   cmp_expr
+    #   cmp_expr     :: match_expr (cmp_op integer)?
     #   match_expr   :: braced_regex
     #                   identifier
     #                   braced_regex match_expr
     #                   identifier match_expr
     #   identifier   :: [-+=._a-zA-Z0-9]+
+    #   integer      :: [-+0-9]+
+    #   cmp_op       :: '<' | '>' | '<=' | '>=' | '==' | '!='
     #   braced_regex :: '{{' python_regex '}}'
 
     # Evaluates `string` as a boolean expression.
     # Returns True or False. Throws a ValueError on syntax error.
     #
     # Variables in `variables` are true.
     # Regexes that match any variable in `variables` are true.
     # 'true' is true.
+    # Variables or Regexes in "cmp_expr" of form "var/regex cmpop int"
+    #  are compared against versions
+    # Variables in versions are evaluated for true/false
+    # Regexes that match in versions must all evaluate true
     # All other identifiers are false.
     @staticmethod
-    def evaluate(string, variables):
+    def evaluate(string, variables, versions = {}):
         try:
-            parser = BooleanExpression(string, set(variables))
+            parser = BooleanExpression(string, set(variables), versions)
             return parser.parseAll()
         except ValueError as e:
             raise ValueError(str(e) + ("\nin expression: %r" % string))
 
     #####
 
-    def __init__(self, string, variables):
+    def __init__(self, string, variables, versions):
         self.tokens = BooleanExpression.tokenize(string)
         self.variables = variables
         self.variables.add("true")
+        self.versions = versions
         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"
+        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 == "":
def isMatchExpression(token):
             or token == "||"
             or token == "!"
             or token == "("
             or token == ")"
         ):
             return False
         return True
 
+    @staticmethod
+    def isCmpExpression(token):
+        if (
+            token == "<"
+            or token == ">"
+            or token == "<="
+            or token == ">="
+            or token == "!="
+            or token == "=="
+        ):
+            return True
+        return False
+
+    def parseCMP(self, regex):
+        cmpop = None
+        if self.accept("<"):
+            cmpop = operator.lt
+        elif self.accept(">"):
+            cmpop = operator.gt
+        elif self.accept(">="):
+            cmpop = operator.ge
+        elif self.accept("<="):
+            cmpop = operator.le
+        elif self.accept("!="):
+            cmpop = operator.ne
+        elif self.accept("=="):
+            cmpop = operator.eq
+
+        if cmpop:
+            version_val = int(self.token) # Expecting int
+            matched_versions = list(filter(regex.match, self.versions.keys()))
+            if matched_versions:
+                # Make sure that ALL the version comparisons specified are true
+                self.value = all(cmpop(int(self.versions[var]), version_val) for var in matched_versions)
+            else:
+                self.value = False
+            self.token = next(self.tokens)
+        else:
+            raise ValueError(
+                "expected comparison operator: '<', '>', '>=', '<=', '!=', '=='")
+
     def parseMATCH(self):
         regex = ""
         for part in filter(None, re.split(r"(\{\{.+?\}\})", self.token)):
             if part.startswith("{{"):
                 assert part.endswith("}}")
                 regex += "(?:{})".format(part[2:-2])
             else:
                 regex += re.escape(part)
         regex = re.compile(regex)
-        self.value = any(regex.fullmatch(var) for var in self.variables)
         self.token = next(self.tokens)
+        if BooleanExpression.isCmpExpression(self.token):
+            self.parseCMP(regex)
+        else:
+            self.value = any(regex.fullmatch(var) for var in self.variables)
 
     def parseNOT(self):
         if self.accept("!"):
             self.parseNOT()
             self.value = not self.value
         elif self.accept("("):
             self.parseOR()
             self.expect(")")

 
 #######
 # Tests
 
 import unittest
 
 
 class TestBooleanExpression(unittest.TestCase):
+    def test_versions(self):
+        versions = { "version1" : "10", "version2" : "20" }
+        self.assertTrue(BooleanExpression.evaluate("version1 < 20", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("version2 < 21", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("{{version.*}} < 21", (), versions))
+
+        self.assertFalse(BooleanExpression.evaluate("version1 < 5", (), versions))
+        self.assertFalse(BooleanExpression.evaluate("version2 < -15", (), versions))
+        self.assertFalse(BooleanExpression.evaluate("{{version.*}} < 15", (), versions))
+
+        self.assertTrue(BooleanExpression.evaluate("version1 > 5", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("version2 > 15", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("{{version.*}} > 5", (), versions))
+
+        self.assertFalse(BooleanExpression.evaluate("version1 > 10", (), versions))
+        self.assertFalse(BooleanExpression.evaluate("version2 > 30", (), versions))
+        self.assertFalse(BooleanExpression.evaluate("{{version.*}} > 10", (), versions))
+
+        self.assertTrue(BooleanExpression.evaluate("version1 == 10 && version2 != 30", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("version1 <= 10 && version2 >= 20", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("version1 == 20 || version2 != 30", (), versions))
+
+        self.assertFalse(BooleanExpression.evaluate("version1 == 20 && version2 == 20", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("version1 == 20 || version2 == 20", (), versions))
+
+        self.assertFalse(BooleanExpression.evaluate("version3 < 21", (), versions))
+        self.assertFalse(BooleanExpression.evaluate("version3 < 21 && version2 > 10", (), versions))
+        self.assertTrue(BooleanExpression.evaluate("version3 < 21 || version2 > 10", (), versions))
+
     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))
def test_errors(self):
         self.checkException(
             "abc{{def", "couldn't parse text: '{{def'\n" + "in expression: 'abc{{def'"
         )
 
         self.checkException(
             "{{}}", "couldn't parse text: '{{}}'\n" + "in expression: '{{}}'"
         )
 
+        self.checkException(
+            "version1 < broken",
+            "invalid literal for int() with base 10: 'broken'",
+        )
 
 if __name__ == "__main__":
     unittest.main()

llvm/utils/lit/lit/Test.py

def isWithinFeatureLimits(self):
             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):
+    def getMissingRequiredFeaturesFromList(self, features, versions):
         try:
             return [
                 item
                 for item in self.requires
-                if not BooleanExpression.evaluate(item, features)
+                if not BooleanExpression.evaluate(item, features, versions)
             ]
         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)
+        versions = self.config.available_versions
+        return self.getMissingRequiredFeaturesFromList(features, versions)
 
     def getUnsupportedFeatures(self):
         """
         getUnsupportedFeatures() -> list of strings
 
         Returns a list of features from UNSUPPORTED that are present
         in the test configuration's features.
         Throws ValueError if an UNSUPPORTED line has a syntax error.
         """
 
         features = self.config.available_features
+        versions = self.config.available_versions
 
         try:
             return [
                 item
                 for item in self.unsupported
-                if BooleanExpression.evaluate(item, features)
+                if BooleanExpression.evaluate(item, features, versions)
             ]
         except ValueError as e:
             raise ValueError("Error in UNSUPPORTED list:\n%s" % str(e))
 
     def getUsedFeatures(self):
         """
         getUsedFeatures() -> list of strings
 

llvm/utils/lit/lit/TestingConfig.py

def fromdefaults(litConfig):
 
         # Set the default available features based on the LitConfig.
         available_features = []
         if litConfig.useValgrind:
             available_features.append("valgrind")
             if litConfig.valgrindLeakCheck:
                 available_features.append("vg_leak")
 
+        available_versions = {}
+
         return TestingConfig(
             None,
             name="<unnamed>",
             suffixes=set(),
             test_format=None,
             environment=environment,
             substitutions=[],
             unsupported=False,
             test_exec_root=None,
             test_source_root=None,
             excludes=[],
             available_features=available_features,
             pipefail=True,
             standalone_tests=False,
+            available_versions=available_versions,
         )
 
     def load_from_path(self, path, litConfig):
         """
         load_from_path(path, litConfig)
 
         Load the configuration module at the provided path into the given config
         object.
def __init__(
         test_source_root,
         excludes,
         available_features,
         pipefail,
         limit_to_features=[],
         is_early=False,
         parallelism_group=None,
         standalone_tests=False,
+        available_versions={},
     ):
         self.parent = parent
         self.name = str(name)
         self.suffixes = set(suffixes)
         self.test_format = test_format
         self.environment = dict(environment)
         self.substitutions = list(substitutions)
         self.unsupported = unsupported
         self.test_exec_root = test_exec_root
         self.test_source_root = test_source_root
         self.excludes = set(excludes)
         self.available_features = set(available_features)
+        self.available_versions = available_versions
         self.pipefail = pipefail
         self.standalone_tests = standalone_tests
         # This list is used by TestRunner.py to restrict running only tests that
         # require one of the features in this list if this list is non-empty.
         # Configurations can set this list to restrict the set of tests to run.
         self.limit_to_features = set(limit_to_features)
         self.parallelism_group = parallelism_group
         self._recursiveExpansionLimit = None

llvm/utils/lit/tests/Inputs/show-used-features/mixed.txt

 
-// REQUIRES: my-require-feature-2 || my-require-feature-3, my-{{[require]*}}-feature-4
+// REQUIRES: my-require-feature-2 || my-require-feature-3, my-{{[require]*}}-feature-4, my-require-version > 10
 // UNSUPPORTED: my-unsupported-feature-2, my-unsupported-feature-3 && !my-{{[unsupported]*}}-feature-4
 // XFAIL: my-xfail-feature-2, my-xfail-feature-3, my-{{[xfail]*}}-feature-4

llvm/utils/lit/tests/Inputs/shtest-format/lit.cfg

 import lit.formats
 
 config.name = "shtest-format"
 config.suffixes = [".txt"]
 config.test_format = lit.formats.ShTest()
 config.test_source_root = None
 config.test_exec_root = None
 config.target_triple = "x86_64-unknown-unknown"
 config.available_features.add("target=%s" % config.target_triple)
 config.available_features.add("a-present-feature")
+config.available_versions["a-version"] = "2"
 config.substitutions.append(("%{python}", '"%s"' % (sys.executable)))

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

+# REQUIRES with a unfulfilled version. Test should not run
+REQUIRES: true
+REQUIRES: a-version-missing > 2, true
+REQUIRES: true
+RUN: false

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

+# REQUIRES with only true clauses and fulfilled version. Test should run.
+REQUIRES: a-version >= 2, true, !not-true
+REQUIRES: true
+RUN: true

llvm/utils/lit/tests/Inputs/shtest-format/version-unfulfilled.txt

+# REQUIRES with a unfulfilled version. Test should not run
+REQUIRES: true
+REQUIRES: a-version > 2, true
+REQUIRES: true
+RUN: false

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

+# REQUIRES with only true clauses and fulfilled version. Test should run.
+UNSUPPORTED: a-version < 2
+RUN: true

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

+# REQUIRES with only true clauses and fulfilled version. Test should not run.
+UNSUPPORTED: a-version >= 2
+RUN: true

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

 # CHECK: UNSUPPORTED: shtest-format :: requires-missing.txt
 # CHECK: PASS: shtest-format :: requires-present.txt
 # CHECK: UNRESOLVED: shtest-format :: requires-star.txt
 # CHECK: PASS: 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: UNSUPPORTED: shtest-format :: version-missing.txt
+# CHECK: PASS: shtest-format :: version-present.txt
+# CHECK: UNSUPPORTED: shtest-format :: version-unfulfilled.txt
+# CHECK: PASS: shtest-format :: version-unsupported-false.txt
+# CHECK: UNSUPPORTED: shtest-format :: version-unsupported-true.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: Failed Tests (4)
 # CHECK: shtest-format :: external_shell/fail.txt
 # CHECK: shtest-format :: external_shell/fail_with_bad_encoding.txt
 # CHECK: shtest-format :: external_shell/fail_with_control_chars.txt
 # CHECK: shtest-format :: fail.txt
 
 # CHECK: Unexpectedly Passed Tests (1)
 # CHECK: shtest-format :: xpass.txt
 
 # CHECK: Testing Time:
-# CHECK: Unsupported        : 3
-# CHECK: Passed             : 7
+# CHECK: Unsupported        : 6
+# CHECK: Passed             : 9
 # CHECK: Expectedly Failed  : 4
 # CHECK: Unresolved         : 3
 # CHECK: Failed             : 4
 # CHECK: Unexpectedly Passed: 1
 
 
 # XUNIT: <?xml version="1.0" encoding="UTF-8"?>
 # XUNIT-NEXT: <testsuites time="{{[0-9.]+}}">
-# XUNIT-NEXT: <testsuite name="shtest-format" tests="22" failures="8" skipped="3">
+# XUNIT-NEXT: <testsuite name="shtest-format" tests="27" failures="8" skipped="6">
 
 # XUNIT: <testcase classname="shtest-format.external_shell" name="fail.txt" time="{{[0-9]+\.[0-9]+}}">
 # XUNIT-NEXT: <failure{{[ ]*}}>
 # XUNIT: </failure>
 # XUNIT-NEXT: </testcase>
 
 
 # XUNIT: <testcase classname="shtest-format.external_shell" name="fail_with_bad_encoding.txt" time="{{[0-9]+\.[0-9]+}}">