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 def isIdentifier(self, t): 83 if (t is BooleanExpression.END or t == '&&' or t == '||' or 84 t == '!' or t == '(' or t == ')'): 85 return False 86 return True 87 88 def parseNOT(self): 89 if self.accept('!'): 90 self.parseNOT() 91 self.value = not self.value 92 elif self.accept('('): 93 self.parseOR() 94 self.expect(')') 95 elif not self.isIdentifier(self.token): 96 raise ValueError("expected: '!' or '(' or identifier\nhave: %s" % 97 self.quote(self.token)) 98 else: 99 self.value = (self.token in self.variables or 100 self.token in self.triple) 101 self.token = next(self.tokens) 102 103 def parseAND(self): 104 self.parseNOT() 105 while self.accept('&&'): 106 left = self.value 107 self.parseNOT() 108 right = self.value 109 # this is technically the wrong associativity, but it 110 # doesn't matter for this limited expression grammar 111 self.value = left and right 112 113 def parseOR(self): 114 self.parseAND() 115 while self.accept('||'): 116 left = self.value 117 self.parseAND() 118 right = self.value 119 # this is technically the wrong associativity, but it 120 # doesn't matter for this limited expression grammar 121 self.value = left or right 122 123 def parseAll(self): 124 self.token = next(self.tokens) 125 self.parseOR() 126 self.expect(BooleanExpression.END) 127 return self.value 128 129 130####### 131# Tests 132 133import unittest 134 135class TestBooleanExpression(unittest.TestCase): 136 def test_variables(self): 137 variables = {'its-true', 'false-lol-true', 'under_score', 138 'e=quals', 'd1g1ts'} 139 self.assertTrue(BooleanExpression.evaluate('true', variables)) 140 self.assertTrue(BooleanExpression.evaluate('its-true', variables)) 141 self.assertTrue(BooleanExpression.evaluate('false-lol-true', variables)) 142 self.assertTrue(BooleanExpression.evaluate('under_score', variables)) 143 self.assertTrue(BooleanExpression.evaluate('e=quals', variables)) 144 self.assertTrue(BooleanExpression.evaluate('d1g1ts', variables)) 145 146 self.assertFalse(BooleanExpression.evaluate('false', variables)) 147 self.assertFalse(BooleanExpression.evaluate('True', variables)) 148 self.assertFalse(BooleanExpression.evaluate('true-ish', variables)) 149 self.assertFalse(BooleanExpression.evaluate('not_true', variables)) 150 self.assertFalse(BooleanExpression.evaluate('tru', variables)) 151 152 def test_triple(self): 153 triple = 'arch-vendor-os' 154 self.assertTrue(BooleanExpression.evaluate('arch-', {}, triple)) 155 self.assertTrue(BooleanExpression.evaluate('ar', {}, triple)) 156 self.assertTrue(BooleanExpression.evaluate('ch-vend', {}, triple)) 157 self.assertTrue(BooleanExpression.evaluate('-vendor-', {}, triple)) 158 self.assertTrue(BooleanExpression.evaluate('-os', {}, triple)) 159 self.assertFalse(BooleanExpression.evaluate('arch-os', {}, triple)) 160 161 def test_operators(self): 162 self.assertTrue(BooleanExpression.evaluate('true || true', {})) 163 self.assertTrue(BooleanExpression.evaluate('true || false', {})) 164 self.assertTrue(BooleanExpression.evaluate('false || true', {})) 165 self.assertFalse(BooleanExpression.evaluate('false || false', {})) 166 167 self.assertTrue(BooleanExpression.evaluate('true && true', {})) 168 self.assertFalse(BooleanExpression.evaluate('true && false', {})) 169 self.assertFalse(BooleanExpression.evaluate('false && true', {})) 170 self.assertFalse(BooleanExpression.evaluate('false && false', {})) 171 172 self.assertFalse(BooleanExpression.evaluate('!true', {})) 173 self.assertTrue(BooleanExpression.evaluate('!false', {})) 174 175 self.assertTrue(BooleanExpression.evaluate(' ((!((false) )) ) ', {})) 176 self.assertTrue(BooleanExpression.evaluate('true && (true && (true))', {})) 177 self.assertTrue(BooleanExpression.evaluate('!false && !false && !! !false', {})) 178 self.assertTrue(BooleanExpression.evaluate('false && false || true', {})) 179 self.assertTrue(BooleanExpression.evaluate('(false && false) || true', {})) 180 self.assertFalse(BooleanExpression.evaluate('false && (false || true)', {})) 181 182 # Evaluate boolean expression `expr`. 183 # Fail if it does not throw a ValueError containing the text `error`. 184 def checkException(self, expr, error): 185 try: 186 BooleanExpression.evaluate(expr, {}) 187 self.fail("expression %r didn't cause an exception" % expr) 188 except ValueError as e: 189 if -1 == str(e).find(error): 190 self.fail(("expression %r caused the wrong ValueError\n" + 191 "actual error was:\n%s\n" + 192 "expected error was:\n%s\n") % (expr, e, error)) 193 except BaseException as e: 194 self.fail(("expression %r caused the wrong exception; actual " + 195 "exception was: \n%r") % (expr, e)) 196 197 def test_errors(self): 198 self.checkException("ba#d", 199 "couldn't parse text: '#d'\n" + 200 "in expression: 'ba#d'") 201 202 self.checkException("true and true", 203 "expected: <end of expression>\n" + 204 "have: 'and'\n" + 205 "in expression: 'true and true'") 206 207 self.checkException("|| true", 208 "expected: '!' or '(' or identifier\n" + 209 "have: '||'\n" + 210 "in expression: '|| true'") 211 212 self.checkException("true &&", 213 "expected: '!' or '(' or identifier\n" + 214 "have: <end of expression>\n" + 215 "in expression: 'true &&'") 216 217 self.checkException("", 218 "expected: '!' or '(' or identifier\n" + 219 "have: <end of expression>\n" + 220 "in expression: ''") 221 222 self.checkException("*", 223 "couldn't parse text: '*'\n" + 224 "in expression: '*'") 225 226 self.checkException("no wait stop", 227 "expected: <end of expression>\n" + 228 "have: 'wait'\n" + 229 "in expression: 'no wait stop'") 230 231 self.checkException("no-$-please", 232 "couldn't parse text: '$-please'\n" + 233 "in expression: 'no-$-please'") 234 235 self.checkException("(((true && true) || true)", 236 "expected: ')'\n" + 237 "have: <end of expression>\n" + 238 "in expression: '(((true && true) || true)'") 239 240 self.checkException("true (true)", 241 "expected: <end of expression>\n" + 242 "have: '('\n" + 243 "in expression: 'true (true)'") 244 245 self.checkException("( )", 246 "expected: '!' or '(' or identifier\n" + 247 "have: ')'\n" + 248 "in expression: '( )'") 249 250if __name__ == '__main__': 251 unittest.main() 252