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