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()