109467b48Spatrickimport re 209467b48Spatrick 309467b48Spatrickclass BooleanExpression: 409467b48Spatrick # A simple evaluator of boolean expressions. 509467b48Spatrick # 609467b48Spatrick # Grammar: 709467b48Spatrick # expr :: or_expr 809467b48Spatrick # or_expr :: and_expr ('||' and_expr)* 909467b48Spatrick # and_expr :: not_expr ('&&' not_expr)* 1009467b48Spatrick # not_expr :: '!' not_expr 1109467b48Spatrick # '(' or_expr ')' 1273471bf0Spatrick # match_expr 1373471bf0Spatrick # match_expr :: braced_regex 1409467b48Spatrick # identifier 1573471bf0Spatrick # braced_regex match_expr 1673471bf0Spatrick # identifier match_expr 1709467b48Spatrick # identifier :: [-+=._a-zA-Z0-9]+ 1873471bf0Spatrick # braced_regex :: '{{' python_regex '}}' 1909467b48Spatrick 2009467b48Spatrick # Evaluates `string` as a boolean expression. 2109467b48Spatrick # Returns True or False. Throws a ValueError on syntax error. 2209467b48Spatrick # 2309467b48Spatrick # Variables in `variables` are true. 2473471bf0Spatrick # Regexes that match any variable in `variables` are true. 2509467b48Spatrick # 'true' is true. 2609467b48Spatrick # All other identifiers are false. 2709467b48Spatrick @staticmethod 28*d415bd75Srobert def evaluate(string, variables): 2909467b48Spatrick try: 30*d415bd75Srobert parser = BooleanExpression(string, set(variables)) 3109467b48Spatrick return parser.parseAll() 3209467b48Spatrick except ValueError as e: 3309467b48Spatrick raise ValueError(str(e) + ('\nin expression: %r' % string)) 3409467b48Spatrick 3509467b48Spatrick ##### 3609467b48Spatrick 37*d415bd75Srobert def __init__(self, string, variables): 3809467b48Spatrick self.tokens = BooleanExpression.tokenize(string) 3909467b48Spatrick self.variables = variables 4009467b48Spatrick self.variables.add('true') 4109467b48Spatrick self.value = None 4209467b48Spatrick self.token = None 4309467b48Spatrick 4409467b48Spatrick # Singleton end-of-expression marker. 4509467b48Spatrick END = object() 4609467b48Spatrick 4709467b48Spatrick # Tokenization pattern. 4873471bf0Spatrick Pattern = re.compile(r'\A\s*([()]|&&|\|\||!|(?:[-+=._a-zA-Z0-9]+|\{\{.+?\}\})+)\s*(.*)\Z') 4909467b48Spatrick 5009467b48Spatrick @staticmethod 5109467b48Spatrick def tokenize(string): 5209467b48Spatrick while True: 5309467b48Spatrick m = re.match(BooleanExpression.Pattern, string) 5409467b48Spatrick if m is None: 5509467b48Spatrick if string == "": 5609467b48Spatrick yield BooleanExpression.END; 5709467b48Spatrick return 5809467b48Spatrick else: 5909467b48Spatrick raise ValueError("couldn't parse text: %r" % string) 6009467b48Spatrick 6109467b48Spatrick token = m.group(1) 6209467b48Spatrick string = m.group(2) 6309467b48Spatrick yield token 6409467b48Spatrick 6509467b48Spatrick def quote(self, token): 6609467b48Spatrick if token is BooleanExpression.END: 6709467b48Spatrick return '<end of expression>' 6809467b48Spatrick else: 6909467b48Spatrick return repr(token) 7009467b48Spatrick 7109467b48Spatrick def accept(self, t): 7209467b48Spatrick if self.token == t: 7309467b48Spatrick self.token = next(self.tokens) 7409467b48Spatrick return True 7509467b48Spatrick else: 7609467b48Spatrick return False 7709467b48Spatrick 7809467b48Spatrick def expect(self, t): 7909467b48Spatrick if self.token == t: 8009467b48Spatrick if self.token != BooleanExpression.END: 8109467b48Spatrick self.token = next(self.tokens) 8209467b48Spatrick else: 8309467b48Spatrick raise ValueError("expected: %s\nhave: %s" % 8409467b48Spatrick (self.quote(t), self.quote(self.token))) 8509467b48Spatrick 86097a140dSpatrick @staticmethod 8773471bf0Spatrick def isMatchExpression(token): 88097a140dSpatrick if (token is BooleanExpression.END or token == '&&' or token == '||' or 89097a140dSpatrick token == '!' or token == '(' or token == ')'): 9009467b48Spatrick return False 9109467b48Spatrick return True 9209467b48Spatrick 9373471bf0Spatrick def parseMATCH(self): 9473471bf0Spatrick regex = '' 9573471bf0Spatrick for part in filter(None, re.split(r'(\{\{.+?\}\})', self.token)): 9673471bf0Spatrick if part.startswith('{{'): 9773471bf0Spatrick assert part.endswith('}}') 9873471bf0Spatrick regex += '(?:{})'.format(part[2:-2]) 9973471bf0Spatrick else: 10073471bf0Spatrick regex += re.escape(part) 10173471bf0Spatrick regex = re.compile(regex) 102*d415bd75Srobert self.value = any(regex.fullmatch(var) for var in self.variables) 10373471bf0Spatrick self.token = next(self.tokens) 10473471bf0Spatrick 10509467b48Spatrick def parseNOT(self): 10609467b48Spatrick if self.accept('!'): 10709467b48Spatrick self.parseNOT() 10809467b48Spatrick self.value = not self.value 10909467b48Spatrick elif self.accept('('): 11009467b48Spatrick self.parseOR() 11109467b48Spatrick self.expect(')') 11273471bf0Spatrick elif not BooleanExpression.isMatchExpression(self.token): 11373471bf0Spatrick raise ValueError("expected: '!', '(', '{{', or identifier\nhave: %s" % 11409467b48Spatrick self.quote(self.token)) 11509467b48Spatrick else: 11673471bf0Spatrick self.parseMATCH() 11709467b48Spatrick 11809467b48Spatrick def parseAND(self): 11909467b48Spatrick self.parseNOT() 12009467b48Spatrick while self.accept('&&'): 12109467b48Spatrick left = self.value 12209467b48Spatrick self.parseNOT() 12309467b48Spatrick right = self.value 12409467b48Spatrick # this is technically the wrong associativity, but it 12509467b48Spatrick # doesn't matter for this limited expression grammar 12609467b48Spatrick self.value = left and right 12709467b48Spatrick 12809467b48Spatrick def parseOR(self): 12909467b48Spatrick self.parseAND() 13009467b48Spatrick while self.accept('||'): 13109467b48Spatrick left = self.value 13209467b48Spatrick self.parseAND() 13309467b48Spatrick right = self.value 13409467b48Spatrick # this is technically the wrong associativity, but it 13509467b48Spatrick # doesn't matter for this limited expression grammar 13609467b48Spatrick self.value = left or right 13709467b48Spatrick 13809467b48Spatrick def parseAll(self): 13909467b48Spatrick self.token = next(self.tokens) 14009467b48Spatrick self.parseOR() 14109467b48Spatrick self.expect(BooleanExpression.END) 14209467b48Spatrick return self.value 14309467b48Spatrick 14409467b48Spatrick 14509467b48Spatrick####### 14609467b48Spatrick# Tests 14709467b48Spatrick 14809467b48Spatrickimport unittest 14909467b48Spatrick 15009467b48Spatrickclass TestBooleanExpression(unittest.TestCase): 15109467b48Spatrick def test_variables(self): 15209467b48Spatrick variables = {'its-true', 'false-lol-true', 'under_score', 15309467b48Spatrick 'e=quals', 'd1g1ts'} 15409467b48Spatrick self.assertTrue(BooleanExpression.evaluate('true', variables)) 15509467b48Spatrick self.assertTrue(BooleanExpression.evaluate('its-true', variables)) 15609467b48Spatrick self.assertTrue(BooleanExpression.evaluate('false-lol-true', variables)) 15709467b48Spatrick self.assertTrue(BooleanExpression.evaluate('under_score', variables)) 15809467b48Spatrick self.assertTrue(BooleanExpression.evaluate('e=quals', variables)) 15909467b48Spatrick self.assertTrue(BooleanExpression.evaluate('d1g1ts', variables)) 16073471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('{{its.+}}', variables)) 16173471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('{{false-[lo]+-true}}', variables)) 16273471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('{{(true|false)-lol-(true|false)}}', variables)) 16373471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('d1g{{[0-9]}}ts', variables)) 16473471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('d1g{{[0-9]}}t{{[a-z]}}', variables)) 16573471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('{{d}}1g{{[0-9]}}t{{[a-z]}}', variables)) 16673471bf0Spatrick self.assertTrue(BooleanExpression.evaluate('d1{{(g|1)+}}ts', variables)) 16709467b48Spatrick 16809467b48Spatrick self.assertFalse(BooleanExpression.evaluate('false', variables)) 16909467b48Spatrick self.assertFalse(BooleanExpression.evaluate('True', variables)) 17009467b48Spatrick self.assertFalse(BooleanExpression.evaluate('true-ish', variables)) 17109467b48Spatrick self.assertFalse(BooleanExpression.evaluate('not_true', variables)) 17209467b48Spatrick self.assertFalse(BooleanExpression.evaluate('tru', variables)) 17373471bf0Spatrick self.assertFalse(BooleanExpression.evaluate('{{its-true.+}}', variables)) 17409467b48Spatrick 17573471bf0Spatrick def test_matching(self): 17673471bf0Spatrick expr1 = 'linux && (target={{aarch64-.+}} || target={{x86_64-.+}})' 17773471bf0Spatrick self.assertTrue(BooleanExpression.evaluate(expr1, {'linux', 'target=x86_64-unknown-linux-gnu'})) 17873471bf0Spatrick self.assertFalse(BooleanExpression.evaluate(expr1, {'linux', 'target=i386-unknown-linux-gnu'})) 17973471bf0Spatrick 18073471bf0Spatrick expr2 = 'use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12}} && !no-exceptions' 18173471bf0Spatrick self.assertTrue(BooleanExpression.evaluate(expr2, {'use_system_cxx_lib', 'target=arm64-apple-macosx10.12'})) 18273471bf0Spatrick self.assertFalse(BooleanExpression.evaluate(expr2, {'use_system_cxx_lib', 'target=arm64-apple-macosx10.12', 'no-exceptions'})) 18373471bf0Spatrick self.assertFalse(BooleanExpression.evaluate(expr2, {'use_system_cxx_lib', 'target=arm64-apple-macosx10.15'})) 18473471bf0Spatrick 18509467b48Spatrick def test_operators(self): 18609467b48Spatrick self.assertTrue(BooleanExpression.evaluate('true || true', {})) 18709467b48Spatrick self.assertTrue(BooleanExpression.evaluate('true || false', {})) 18809467b48Spatrick self.assertTrue(BooleanExpression.evaluate('false || true', {})) 18909467b48Spatrick self.assertFalse(BooleanExpression.evaluate('false || false', {})) 19009467b48Spatrick 19109467b48Spatrick self.assertTrue(BooleanExpression.evaluate('true && true', {})) 19209467b48Spatrick self.assertFalse(BooleanExpression.evaluate('true && false', {})) 19309467b48Spatrick self.assertFalse(BooleanExpression.evaluate('false && true', {})) 19409467b48Spatrick self.assertFalse(BooleanExpression.evaluate('false && false', {})) 19509467b48Spatrick 19609467b48Spatrick self.assertFalse(BooleanExpression.evaluate('!true', {})) 19709467b48Spatrick self.assertTrue(BooleanExpression.evaluate('!false', {})) 19809467b48Spatrick 19909467b48Spatrick self.assertTrue(BooleanExpression.evaluate(' ((!((false) )) ) ', {})) 20009467b48Spatrick self.assertTrue(BooleanExpression.evaluate('true && (true && (true))', {})) 20109467b48Spatrick self.assertTrue(BooleanExpression.evaluate('!false && !false && !! !false', {})) 20209467b48Spatrick self.assertTrue(BooleanExpression.evaluate('false && false || true', {})) 20309467b48Spatrick self.assertTrue(BooleanExpression.evaluate('(false && false) || true', {})) 20409467b48Spatrick self.assertFalse(BooleanExpression.evaluate('false && (false || true)', {})) 20509467b48Spatrick 20609467b48Spatrick # Evaluate boolean expression `expr`. 20709467b48Spatrick # Fail if it does not throw a ValueError containing the text `error`. 20809467b48Spatrick def checkException(self, expr, error): 20909467b48Spatrick try: 21009467b48Spatrick BooleanExpression.evaluate(expr, {}) 21109467b48Spatrick self.fail("expression %r didn't cause an exception" % expr) 21209467b48Spatrick except ValueError as e: 21309467b48Spatrick if -1 == str(e).find(error): 21409467b48Spatrick self.fail(("expression %r caused the wrong ValueError\n" + 21509467b48Spatrick "actual error was:\n%s\n" + 21609467b48Spatrick "expected error was:\n%s\n") % (expr, e, error)) 21709467b48Spatrick except BaseException as e: 21809467b48Spatrick self.fail(("expression %r caused the wrong exception; actual " + 21909467b48Spatrick "exception was: \n%r") % (expr, e)) 22009467b48Spatrick 22109467b48Spatrick def test_errors(self): 22209467b48Spatrick self.checkException("ba#d", 22309467b48Spatrick "couldn't parse text: '#d'\n" + 22409467b48Spatrick "in expression: 'ba#d'") 22509467b48Spatrick 22609467b48Spatrick self.checkException("true and true", 22709467b48Spatrick "expected: <end of expression>\n" + 22809467b48Spatrick "have: 'and'\n" + 22909467b48Spatrick "in expression: 'true and true'") 23009467b48Spatrick 23109467b48Spatrick self.checkException("|| true", 23273471bf0Spatrick "expected: '!', '(', '{{', or identifier\n" + 23309467b48Spatrick "have: '||'\n" + 23409467b48Spatrick "in expression: '|| true'") 23509467b48Spatrick 23609467b48Spatrick self.checkException("true &&", 23773471bf0Spatrick "expected: '!', '(', '{{', or identifier\n" + 23809467b48Spatrick "have: <end of expression>\n" + 23909467b48Spatrick "in expression: 'true &&'") 24009467b48Spatrick 24109467b48Spatrick self.checkException("", 24273471bf0Spatrick "expected: '!', '(', '{{', or identifier\n" + 24309467b48Spatrick "have: <end of expression>\n" + 24409467b48Spatrick "in expression: ''") 24509467b48Spatrick 24609467b48Spatrick self.checkException("*", 24709467b48Spatrick "couldn't parse text: '*'\n" + 24809467b48Spatrick "in expression: '*'") 24909467b48Spatrick 25009467b48Spatrick self.checkException("no wait stop", 25109467b48Spatrick "expected: <end of expression>\n" + 25209467b48Spatrick "have: 'wait'\n" + 25309467b48Spatrick "in expression: 'no wait stop'") 25409467b48Spatrick 25509467b48Spatrick self.checkException("no-$-please", 25609467b48Spatrick "couldn't parse text: '$-please'\n" + 25709467b48Spatrick "in expression: 'no-$-please'") 25809467b48Spatrick 25909467b48Spatrick self.checkException("(((true && true) || true)", 26009467b48Spatrick "expected: ')'\n" + 26109467b48Spatrick "have: <end of expression>\n" + 26209467b48Spatrick "in expression: '(((true && true) || true)'") 26309467b48Spatrick 26409467b48Spatrick self.checkException("true (true)", 26509467b48Spatrick "expected: <end of expression>\n" + 26609467b48Spatrick "have: '('\n" + 26709467b48Spatrick "in expression: 'true (true)'") 26809467b48Spatrick 26909467b48Spatrick self.checkException("( )", 27073471bf0Spatrick "expected: '!', '(', '{{', or identifier\n" + 27109467b48Spatrick "have: ')'\n" + 27209467b48Spatrick "in expression: '( )'") 27309467b48Spatrick 27473471bf0Spatrick self.checkException("abc{{def", 27573471bf0Spatrick "couldn't parse text: '{{def'\n" + 27673471bf0Spatrick "in expression: 'abc{{def'") 27773471bf0Spatrick 27873471bf0Spatrick self.checkException("{{}}", 27973471bf0Spatrick "couldn't parse text: '{{}}'\n" + 28073471bf0Spatrick "in expression: '{{}}'") 28173471bf0Spatrick 28273471bf0Spatrick 28309467b48Spatrickif __name__ == '__main__': 28409467b48Spatrick unittest.main() 285