351 lines
12 KiB
Python
351 lines
12 KiB
Python
import re
|
|
|
|
|
|
class BooleanExpression:
|
|
# A simple evaluator of boolean expressions.
|
|
#
|
|
# Grammar:
|
|
# expr :: or_expr
|
|
# or_expr :: and_expr ('||' and_expr)*
|
|
# and_expr :: not_expr ('&&' not_expr)*
|
|
# not_expr :: '!' not_expr
|
|
# '(' or_expr ')'
|
|
# match_expr
|
|
# match_expr :: braced_regex
|
|
# identifier
|
|
# braced_regex match_expr
|
|
# identifier match_expr
|
|
# identifier :: [-+=._a-zA-Z0-9]+
|
|
# braced_regex :: '{{' python_regex '}}'
|
|
|
|
# Evaluates `string` as a boolean expression.
|
|
# Returns True or False. Throws a ValueError on syntax error.
|
|
#
|
|
# Variables in `variables` are true.
|
|
# Regexes that match any variable in `variables` are true.
|
|
# 'true' is true.
|
|
# All other identifiers are false.
|
|
@staticmethod
|
|
def evaluate(string, variables):
|
|
try:
|
|
parser = BooleanExpression(string, set(variables))
|
|
return parser.parseAll()
|
|
except ValueError as e:
|
|
raise ValueError(str(e) + ("\nin expression: %r" % string))
|
|
|
|
#####
|
|
|
|
def __init__(self, string, variables):
|
|
self.tokens = BooleanExpression.tokenize(string)
|
|
self.variables = variables
|
|
self.variables.add("true")
|
|
self.value = None
|
|
self.token = None
|
|
|
|
# Singleton end-of-expression marker.
|
|
END = object()
|
|
|
|
# Tokenization pattern.
|
|
Pattern = re.compile(
|
|
r"\A\s*([()]|&&|\|\||!|(?:[-+=._a-zA-Z0-9]+|\{\{.+?\}\})+)\s*(.*)\Z"
|
|
)
|
|
|
|
@staticmethod
|
|
def tokenize(string):
|
|
while True:
|
|
m = re.match(BooleanExpression.Pattern, string)
|
|
if m is None:
|
|
if string == "":
|
|
yield BooleanExpression.END
|
|
return
|
|
else:
|
|
raise ValueError("couldn't parse text: %r" % string)
|
|
|
|
token = m.group(1)
|
|
string = m.group(2)
|
|
yield token
|
|
|
|
def quote(self, token):
|
|
if token is BooleanExpression.END:
|
|
return "<end of expression>"
|
|
else:
|
|
return repr(token)
|
|
|
|
def accept(self, t):
|
|
if self.token == t:
|
|
self.token = next(self.tokens)
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def expect(self, t):
|
|
if self.token == t:
|
|
if self.token != BooleanExpression.END:
|
|
self.token = next(self.tokens)
|
|
else:
|
|
raise ValueError(
|
|
"expected: %s\nhave: %s" % (self.quote(t), self.quote(self.token))
|
|
)
|
|
|
|
@staticmethod
|
|
def isMatchExpression(token):
|
|
if (
|
|
token is BooleanExpression.END
|
|
or token == "&&"
|
|
or token == "||"
|
|
or token == "!"
|
|
or token == "("
|
|
or token == ")"
|
|
):
|
|
return False
|
|
return True
|
|
|
|
def parseMATCH(self):
|
|
regex = ""
|
|
for part in filter(None, re.split(r"(\{\{.+?\}\})", self.token)):
|
|
if part.startswith("{{"):
|
|
assert part.endswith("}}")
|
|
regex += "(?:{})".format(part[2:-2])
|
|
else:
|
|
regex += re.escape(part)
|
|
regex = re.compile(regex)
|
|
self.value = any(regex.fullmatch(var) for var in self.variables)
|
|
self.token = next(self.tokens)
|
|
|
|
def parseNOT(self):
|
|
if self.accept("!"):
|
|
self.parseNOT()
|
|
self.value = not self.value
|
|
elif self.accept("("):
|
|
self.parseOR()
|
|
self.expect(")")
|
|
elif not BooleanExpression.isMatchExpression(self.token):
|
|
raise ValueError(
|
|
"expected: '!', '(', '{{', or identifier\nhave: %s"
|
|
% self.quote(self.token)
|
|
)
|
|
else:
|
|
self.parseMATCH()
|
|
|
|
def parseAND(self):
|
|
self.parseNOT()
|
|
while self.accept("&&"):
|
|
left = self.value
|
|
self.parseNOT()
|
|
right = self.value
|
|
# this is technically the wrong associativity, but it
|
|
# doesn't matter for this limited expression grammar
|
|
self.value = left and right
|
|
|
|
def parseOR(self):
|
|
self.parseAND()
|
|
while self.accept("||"):
|
|
left = self.value
|
|
self.parseAND()
|
|
right = self.value
|
|
# this is technically the wrong associativity, but it
|
|
# doesn't matter for this limited expression grammar
|
|
self.value = left or right
|
|
|
|
def parseAll(self):
|
|
self.token = next(self.tokens)
|
|
self.parseOR()
|
|
self.expect(BooleanExpression.END)
|
|
return self.value
|
|
|
|
|
|
#######
|
|
# Tests
|
|
|
|
import unittest
|
|
|
|
|
|
class TestBooleanExpression(unittest.TestCase):
|
|
def test_variables(self):
|
|
variables = {"its-true", "false-lol-true", "under_score", "e=quals", "d1g1ts"}
|
|
self.assertTrue(BooleanExpression.evaluate("true", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("its-true", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("false-lol-true", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("under_score", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("e=quals", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("d1g1ts", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("{{its.+}}", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("{{false-[lo]+-true}}", variables))
|
|
self.assertTrue(
|
|
BooleanExpression.evaluate("{{(true|false)-lol-(true|false)}}", variables)
|
|
)
|
|
self.assertTrue(BooleanExpression.evaluate("d1g{{[0-9]}}ts", variables))
|
|
self.assertTrue(BooleanExpression.evaluate("d1g{{[0-9]}}t{{[a-z]}}", variables))
|
|
self.assertTrue(
|
|
BooleanExpression.evaluate("{{d}}1g{{[0-9]}}t{{[a-z]}}", variables)
|
|
)
|
|
self.assertTrue(BooleanExpression.evaluate("d1{{(g|1)+}}ts", variables))
|
|
|
|
self.assertFalse(BooleanExpression.evaluate("false", variables))
|
|
self.assertFalse(BooleanExpression.evaluate("True", variables))
|
|
self.assertFalse(BooleanExpression.evaluate("true-ish", variables))
|
|
self.assertFalse(BooleanExpression.evaluate("not_true", variables))
|
|
self.assertFalse(BooleanExpression.evaluate("tru", variables))
|
|
self.assertFalse(BooleanExpression.evaluate("{{its-true.+}}", variables))
|
|
|
|
def test_matching(self):
|
|
expr1 = "linux && (target={{aarch64-.+}} || target={{x86_64-.+}})"
|
|
self.assertTrue(
|
|
BooleanExpression.evaluate(
|
|
expr1, {"linux", "target=x86_64-unknown-linux-gnu"}
|
|
)
|
|
)
|
|
self.assertFalse(
|
|
BooleanExpression.evaluate(
|
|
expr1, {"linux", "target=i386-unknown-linux-gnu"}
|
|
)
|
|
)
|
|
|
|
expr2 = "use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12}} && !no-exceptions"
|
|
self.assertTrue(
|
|
BooleanExpression.evaluate(
|
|
expr2, {"use_system_cxx_lib", "target=arm64-apple-macosx10.12"}
|
|
)
|
|
)
|
|
self.assertFalse(
|
|
BooleanExpression.evaluate(
|
|
expr2,
|
|
{
|
|
"use_system_cxx_lib",
|
|
"target=arm64-apple-macosx10.12",
|
|
"no-exceptions",
|
|
},
|
|
)
|
|
)
|
|
self.assertFalse(
|
|
BooleanExpression.evaluate(
|
|
expr2, {"use_system_cxx_lib", "target=arm64-apple-macosx10.15"}
|
|
)
|
|
)
|
|
|
|
def test_operators(self):
|
|
self.assertTrue(BooleanExpression.evaluate("true || true", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("true || false", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("false || true", {}))
|
|
self.assertFalse(BooleanExpression.evaluate("false || false", {}))
|
|
|
|
self.assertTrue(BooleanExpression.evaluate("true && true", {}))
|
|
self.assertFalse(BooleanExpression.evaluate("true && false", {}))
|
|
self.assertFalse(BooleanExpression.evaluate("false && true", {}))
|
|
self.assertFalse(BooleanExpression.evaluate("false && false", {}))
|
|
|
|
self.assertFalse(BooleanExpression.evaluate("!true", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("!false", {}))
|
|
|
|
self.assertTrue(BooleanExpression.evaluate(" ((!((false) )) ) ", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("true && (true && (true))", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("!false && !false && !! !false", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("false && false || true", {}))
|
|
self.assertTrue(BooleanExpression.evaluate("(false && false) || true", {}))
|
|
self.assertFalse(BooleanExpression.evaluate("false && (false || true)", {}))
|
|
|
|
# Evaluate boolean expression `expr`.
|
|
# Fail if it does not throw a ValueError containing the text `error`.
|
|
def checkException(self, expr, error):
|
|
try:
|
|
BooleanExpression.evaluate(expr, {})
|
|
self.fail("expression %r didn't cause an exception" % expr)
|
|
except ValueError as e:
|
|
if -1 == str(e).find(error):
|
|
self.fail(
|
|
(
|
|
"expression %r caused the wrong ValueError\n"
|
|
+ "actual error was:\n%s\n"
|
|
+ "expected error was:\n%s\n"
|
|
)
|
|
% (expr, e, error)
|
|
)
|
|
except BaseException as e:
|
|
self.fail(
|
|
(
|
|
"expression %r caused the wrong exception; actual "
|
|
+ "exception was: \n%r"
|
|
)
|
|
% (expr, e)
|
|
)
|
|
|
|
def test_errors(self):
|
|
self.checkException(
|
|
"ba#d", "couldn't parse text: '#d'\n" + "in expression: 'ba#d'"
|
|
)
|
|
|
|
self.checkException(
|
|
"true and true",
|
|
"expected: <end of expression>\n"
|
|
+ "have: 'and'\n"
|
|
+ "in expression: 'true and true'",
|
|
)
|
|
|
|
self.checkException(
|
|
"|| true",
|
|
"expected: '!', '(', '{{', or identifier\n"
|
|
+ "have: '||'\n"
|
|
+ "in expression: '|| true'",
|
|
)
|
|
|
|
self.checkException(
|
|
"true &&",
|
|
"expected: '!', '(', '{{', or identifier\n"
|
|
+ "have: <end of expression>\n"
|
|
+ "in expression: 'true &&'",
|
|
)
|
|
|
|
self.checkException(
|
|
"",
|
|
"expected: '!', '(', '{{', or identifier\n"
|
|
+ "have: <end of expression>\n"
|
|
+ "in expression: ''",
|
|
)
|
|
|
|
self.checkException("*", "couldn't parse text: '*'\n" + "in expression: '*'")
|
|
|
|
self.checkException(
|
|
"no wait stop",
|
|
"expected: <end of expression>\n"
|
|
+ "have: 'wait'\n"
|
|
+ "in expression: 'no wait stop'",
|
|
)
|
|
|
|
self.checkException(
|
|
"no-$-please",
|
|
"couldn't parse text: '$-please'\n" + "in expression: 'no-$-please'",
|
|
)
|
|
|
|
self.checkException(
|
|
"(((true && true) || true)",
|
|
"expected: ')'\n"
|
|
+ "have: <end of expression>\n"
|
|
+ "in expression: '(((true && true) || true)'",
|
|
)
|
|
|
|
self.checkException(
|
|
"true (true)",
|
|
"expected: <end of expression>\n"
|
|
+ "have: '('\n"
|
|
+ "in expression: 'true (true)'",
|
|
)
|
|
|
|
self.checkException(
|
|
"( )",
|
|
"expected: '!', '(', '{{', or identifier\n"
|
|
+ "have: ')'\n"
|
|
+ "in expression: '( )'",
|
|
)
|
|
|
|
self.checkException(
|
|
"abc{{def", "couldn't parse text: '{{def'\n" + "in expression: 'abc{{def'"
|
|
)
|
|
|
|
self.checkException(
|
|
"{{}}", "couldn't parse text: '{{}}'\n" + "in expression: '{{}}'"
|
|
)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|