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