| 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 |
| # match_expr :: braced_regex |
| # identifier |
| # braced_regex match_expr |
| # identifier match_expr |
| # identifier :: [-+=._a-zA-Z0-9]+ |
| # 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. |
| # All other identifiers are false. |
| @staticmethod |
| def evaluate(string, variables): |
| try: |
| parser = BooleanExpression(string, set(variables)) |
| return parser.parseAll() |
| except ValueError as e: |
| raise ValueError(str(e) + ("\nin expression: %r" % string)) |
| |
| ##### |
| |
| def __init__(self, string, variables): |
| self.tokens = BooleanExpression.tokenize(string) |
| self.variables = variables |
| self.variables.add("true") |
| 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)) |
| ) |
| |
| @staticmethod |
| def isMatchExpression(token): |
| if ( |
| token is BooleanExpression.END |
| or token == "&&" |
| or token == "||" |
| or token == "!" |
| or token == "(" |
| or token == ")" |
| ): |
| return False |
| return True |
| |
| 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) |
| |
| def parseNOT(self): |
| if self.accept("!"): |
| self.parseNOT() |
| self.value = not self.value |
| elif self.accept("("): |
| self.parseOR() |
| self.expect(")") |
| elif not BooleanExpression.isMatchExpression(self.token): |
| raise ValueError( |
| "expected: '!', '(', '{{', or identifier\nhave: %s" |
| % self.quote(self.token) |
| ) |
| else: |
| self.parseMATCH() |
| |
| 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.assertTrue(BooleanExpression.evaluate("{{its.+}}", variables)) |
| self.assertTrue(BooleanExpression.evaluate("{{false-[lo]+-true}}", variables)) |
| self.assertTrue( |
| BooleanExpression.evaluate("{{(true|false)-lol-(true|false)}}", variables) |
| ) |
| self.assertTrue(BooleanExpression.evaluate("d1g{{[0-9]}}ts", variables)) |
| self.assertTrue(BooleanExpression.evaluate("d1g{{[0-9]}}t{{[a-z]}}", variables)) |
| self.assertTrue( |
| BooleanExpression.evaluate("{{d}}1g{{[0-9]}}t{{[a-z]}}", variables) |
| ) |
| self.assertTrue(BooleanExpression.evaluate("d1{{(g|1)+}}ts", 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)) |
| self.assertFalse(BooleanExpression.evaluate("{{its-true.+}}", variables)) |
| |
| def test_matching(self): |
| expr1 = "linux && (target={{aarch64-.+}} || target={{x86_64-.+}})" |
| self.assertTrue( |
| BooleanExpression.evaluate( |
| expr1, {"linux", "target=x86_64-unknown-linux-gnu"} |
| ) |
| ) |
| self.assertFalse( |
| BooleanExpression.evaluate( |
| expr1, {"linux", "target=i386-unknown-linux-gnu"} |
| ) |
| ) |
| |
| expr2 = "use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12}} && !no-exceptions" |
| self.assertTrue( |
| BooleanExpression.evaluate( |
| expr2, {"use_system_cxx_lib", "target=arm64-apple-macosx10.12"} |
| ) |
| ) |
| self.assertFalse( |
| BooleanExpression.evaluate( |
| expr2, |
| { |
| "use_system_cxx_lib", |
| "target=arm64-apple-macosx10.12", |
| "no-exceptions", |
| }, |
| ) |
| ) |
| self.assertFalse( |
| BooleanExpression.evaluate( |
| expr2, {"use_system_cxx_lib", "target=arm64-apple-macosx10.15"} |
| ) |
| ) |
| |
| 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 identifier\n" |
| + "have: '||'\n" |
| + "in expression: '|| true'", |
| ) |
| |
| self.checkException( |
| "true &&", |
| "expected: '!', '(', '{{', or identifier\n" |
| + "have: <end of expression>\n" |
| + "in expression: 'true &&'", |
| ) |
| |
| self.checkException( |
| "", |
| "expected: '!', '(', '{{', 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 identifier\n" |
| + "have: ')'\n" |
| + "in expression: '( )'", |
| ) |
| |
| self.checkException( |
| "abc{{def", "couldn't parse text: '{{def'\n" + "in expression: 'abc{{def'" |
| ) |
| |
| self.checkException( |
| "{{}}", "couldn't parse text: '{{}}'\n" + "in expression: '{{}}'" |
| ) |
| |
| |
| if __name__ == "__main__": |
| unittest.main() |
