1import re 2 3class BooleanExpression: 4 # A simple evaluator of boolean expressions. 5 # 6 # Grammar: 7 # expr :: or_expr 8 # or_expr :: and_expr ('||' and_expr)* 9 # and_expr :: not_expr ('&&' not_expr)* 10 # not_expr :: '!' not_expr 11 # '(' or_expr ')' 12 # match_expr 13 # match_expr :: braced_regex 14 # identifier 15 # braced_regex match_expr 16 # identifier match_expr 17 # identifier :: [-+=._a-zA-Z0-9]+ 18 # braced_regex :: '{{' python_regex '}}' 19 20 # Evaluates `string` as a boolean expression. 21 # Returns True or False. Throws a ValueError on syntax error. 22 # 23 # Variables in `variables` are true. 24 # Regexes that match any variable in `variables` are true. 25 # 'true' is true. 26 # All other identifiers are false. 27 @staticmethod 28 def evaluate(string, variables): 29 try: 30 parser = BooleanExpression(string, set(variables)) 31 return parser.parseAll() 32 except ValueError as e: 33 raise ValueError(str(e) + ('\nin expression: %r' % string)) 34 35 ##### 36 37 def __init__(self, string, variables): 38 self.tokens = BooleanExpression.tokenize(string) 39 self.variables = variables 40 self.variables.add('true') 41 self.value = None 42 self.token = None 43 44 # Singleton end-of-expression marker. 45 END = object() 46 47 # Tokenization pattern. 48 Pattern = re.compile(r'\A\s*([()]|&&|\|\||!|(?:[-+=._a-zA-Z0-9]+|\{\{.+?\}\})+)\s*(.*)\Z') 49 50 @staticmethod 51 def tokenize(string): 52 while True: 53 m = re.match(BooleanExpression.Pattern, string) 54 if m is None: 55 if string == "": 56 yield BooleanExpression.END; 57 return 58 else: 59 raise ValueError("couldn't parse text: %r" % string) 60 61 token = m.group(1) 62 string = m.group(2) 63 yield token 64 65 def quote(self, token): 66 if token is BooleanExpression.END: 67 return '<end of expression>' 68 else: 69 return repr(token) 70 71 def accept(self, t): 72 if self.token == t: 73 self.token = next(self.tokens) 74 return True 75 else: 76 return False 77 78 def expect(self, t): 79 if self.token == t: 80 if self.token != BooleanExpression.END: 81 self.token = next(self.tokens) 82 else: 83 raise ValueError("expected: %s\nhave: %s" % 84 (self.quote(t), self.quote(self.token))) 85 86 @staticmethod 87 def isMatchExpression(token): 88 if (token is BooleanExpression.END or token == '&&' or token == '||' or 89 token == '!' or token == '(' or token == ')'): 90 return False 91 return True 92 93 def parseMATCH(self): 94 regex = '' 95 for part in filter(None, re.split(r'(\{\{.+?\}\})', self.token)): 96 if part.startswith('{{'): 97 assert part.endswith('}}') 98 regex += '(?:{})'.format(part[2:-2]) 99 else: 100 regex += re.escape(part) 101 regex = re.compile(regex) 102 self.value = any(regex.fullmatch(var) for var in self.variables) 103 self.token = next(self.tokens) 104 105 def parseNOT(self): 106 if self.accept('!'): 107 self.parseNOT() 108 self.value = not self.value 109 elif self.accept('('): 110 self.parseOR() 111 self.expect(')') 112 elif not BooleanExpression.isMatchExpression(self.token): 113 raise ValueError("expected: '!', '(', '{{', or identifier\nhave: %s" % 114 self.quote(self.token)) 115 else: 116 self.parseMATCH() 117 118 def parseAND(self): 119 self.parseNOT() 120 while self.accept('&&'): 121 left = self.value 122 self.parseNOT() 123 right = self.value 124 # this is technically the wrong associativity, but it 125 # doesn't matter for this limited expression grammar 126 self.value = left and right 127 128 def parseOR(self): 129 self.parseAND() 130 while self.accept('||'): 131 left = self.value 132 self.parseAND() 133 right = self.value 134 # this is technically the wrong associativity, but it 135 # doesn't matter for this limited expression grammar 136 self.value = left or right 137 138 def parseAll(self): 139 self.token = next(self.tokens) 140 self.parseOR() 141 self.expect(BooleanExpression.END) 142 return self.value 143 144 145####### 146# Tests 147 148import unittest 149 150class TestBooleanExpression(unittest.TestCase): 151 def test_variables(self): 152 variables = {'its-true', 'false-lol-true', 'under_score', 153 'e=quals', 'd1g1ts'} 154 self.assertTrue(BooleanExpression.evaluate('true', variables)) 155 self.assertTrue(BooleanExpression.evaluate('its-true', variables)) 156 self.assertTrue(BooleanExpression.evaluate('false-lol-true', variables)) 157 self.assertTrue(BooleanExpression.evaluate('under_score', variables)) 158 self.assertTrue(BooleanExpression.evaluate('e=quals', variables)) 159 self.assertTrue(BooleanExpression.evaluate('d1g1ts', variables)) 160 self.assertTrue(BooleanExpression.evaluate('{{its.+}}', variables)) 161 self.assertTrue(BooleanExpression.evaluate('{{false-[lo]+-true}}', variables)) 162 self.assertTrue(BooleanExpression.evaluate('{{(true|false)-lol-(true|false)}}', variables)) 163 self.assertTrue(BooleanExpression.evaluate('d1g{{[0-9]}}ts', variables)) 164 self.assertTrue(BooleanExpression.evaluate('d1g{{[0-9]}}t{{[a-z]}}', variables)) 165 self.assertTrue(BooleanExpression.evaluate('{{d}}1g{{[0-9]}}t{{[a-z]}}', variables)) 166 self.assertTrue(BooleanExpression.evaluate('d1{{(g|1)+}}ts', variables)) 167 168 self.assertFalse(BooleanExpression.evaluate('false', variables)) 169 self.assertFalse(BooleanExpression.evaluate('True', variables)) 170 self.assertFalse(BooleanExpression.evaluate('true-ish', variables)) 171 self.assertFalse(BooleanExpression.evaluate('not_true', variables)) 172 self.assertFalse(BooleanExpression.evaluate('tru', variables)) 173 self.assertFalse(BooleanExpression.evaluate('{{its-true.+}}', variables)) 174 175 def test_matching(self): 176 expr1 = 'linux && (target={{aarch64-.+}} || target={{x86_64-.+}})' 177 self.assertTrue(BooleanExpression.evaluate(expr1, {'linux', 'target=x86_64-unknown-linux-gnu'})) 178 self.assertFalse(BooleanExpression.evaluate(expr1, {'linux', 'target=i386-unknown-linux-gnu'})) 179 180 expr2 = 'use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12}} && !no-exceptions' 181 self.assertTrue(BooleanExpression.evaluate(expr2, {'use_system_cxx_lib', 'target=arm64-apple-macosx10.12'})) 182 self.assertFalse(BooleanExpression.evaluate(expr2, {'use_system_cxx_lib', 'target=arm64-apple-macosx10.12', 'no-exceptions'})) 183 self.assertFalse(BooleanExpression.evaluate(expr2, {'use_system_cxx_lib', 'target=arm64-apple-macosx10.15'})) 184 185 def test_operators(self): 186 self.assertTrue(BooleanExpression.evaluate('true || true', {})) 187 self.assertTrue(BooleanExpression.evaluate('true || false', {})) 188 self.assertTrue(BooleanExpression.evaluate('false || true', {})) 189 self.assertFalse(BooleanExpression.evaluate('false || false', {})) 190 191 self.assertTrue(BooleanExpression.evaluate('true && true', {})) 192 self.assertFalse(BooleanExpression.evaluate('true && false', {})) 193 self.assertFalse(BooleanExpression.evaluate('false && true', {})) 194 self.assertFalse(BooleanExpression.evaluate('false && false', {})) 195 196 self.assertFalse(BooleanExpression.evaluate('!true', {})) 197 self.assertTrue(BooleanExpression.evaluate('!false', {})) 198 199 self.assertTrue(BooleanExpression.evaluate(' ((!((false) )) ) ', {})) 200 self.assertTrue(BooleanExpression.evaluate('true && (true && (true))', {})) 201 self.assertTrue(BooleanExpression.evaluate('!false && !false && !! !false', {})) 202 self.assertTrue(BooleanExpression.evaluate('false && false || true', {})) 203 self.assertTrue(BooleanExpression.evaluate('(false && false) || true', {})) 204 self.assertFalse(BooleanExpression.evaluate('false && (false || true)', {})) 205 206 # Evaluate boolean expression `expr`. 207 # Fail if it does not throw a ValueError containing the text `error`. 208 def checkException(self, expr, error): 209 try: 210 BooleanExpression.evaluate(expr, {}) 211 self.fail("expression %r didn't cause an exception" % expr) 212 except ValueError as e: 213 if -1 == str(e).find(error): 214 self.fail(("expression %r caused the wrong ValueError\n" + 215 "actual error was:\n%s\n" + 216 "expected error was:\n%s\n") % (expr, e, error)) 217 except BaseException as e: 218 self.fail(("expression %r caused the wrong exception; actual " + 219 "exception was: \n%r") % (expr, e)) 220 221 def test_errors(self): 222 self.checkException("ba#d", 223 "couldn't parse text: '#d'\n" + 224 "in expression: 'ba#d'") 225 226 self.checkException("true and true", 227 "expected: <end of expression>\n" + 228 "have: 'and'\n" + 229 "in expression: 'true and true'") 230 231 self.checkException("|| true", 232 "expected: '!', '(', '{{', or identifier\n" + 233 "have: '||'\n" + 234 "in expression: '|| true'") 235 236 self.checkException("true &&", 237 "expected: '!', '(', '{{', or identifier\n" + 238 "have: <end of expression>\n" + 239 "in expression: 'true &&'") 240 241 self.checkException("", 242 "expected: '!', '(', '{{', or identifier\n" + 243 "have: <end of expression>\n" + 244 "in expression: ''") 245 246 self.checkException("*", 247 "couldn't parse text: '*'\n" + 248 "in expression: '*'") 249 250 self.checkException("no wait stop", 251 "expected: <end of expression>\n" + 252 "have: 'wait'\n" + 253 "in expression: 'no wait stop'") 254 255 self.checkException("no-$-please", 256 "couldn't parse text: '$-please'\n" + 257 "in expression: 'no-$-please'") 258 259 self.checkException("(((true && true) || true)", 260 "expected: ')'\n" + 261 "have: <end of expression>\n" + 262 "in expression: '(((true && true) || true)'") 263 264 self.checkException("true (true)", 265 "expected: <end of expression>\n" + 266 "have: '('\n" + 267 "in expression: 'true (true)'") 268 269 self.checkException("( )", 270 "expected: '!', '(', '{{', or identifier\n" + 271 "have: ')'\n" + 272 "in expression: '( )'") 273 274 self.checkException("abc{{def", 275 "couldn't parse text: '{{def'\n" + 276 "in expression: 'abc{{def'") 277 278 self.checkException("{{}}", 279 "couldn't parse text: '{{}}'\n" + 280 "in expression: '{{}}'") 281 282 283if __name__ == '__main__': 284 unittest.main() 285