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