def base_dispatcher(dispatch_name='execute'):
    class Dispatcher(BaseDispatcher):
        pass
    Dispatcher.dispatch_name = dispatch_name
    return Dispatcher def cached(f):
    class NonLocals(object):
        pass
    CACHE_CAPACITY = 1000000
    cache = {}
    NonLocals.full = False
    NonLocals.hits = NonLocals.misses = NonLocals.currsize = 0
    NonLocals.root = []
    NonLocals.root[:] = [NonLocals.root, NonLocals.root, None, None]
    PREV, NEXT, KEY, RESULT = range(4)

    def decorated(*args, **kwargs):
        if not kwargs:
            key_tuple = args
        else:
            key_tuple = (args, tuple(sorted(kwargs.items(), key=hash)))
        key = pickle.dumps(key_tuple)
        link = cache.get(key)
        if link is not None:
            p, n, k, r = link
            p[NEXT] = n
            n[PREV] = p
            last = NonLocals.root[PREV]
            last[NEXT] = NonLocals.root[PREV] = link
            link[PREV] = last
            link[NEXT] = NonLocals.root
            NonLocals.hits += 1
            return r
        r = f(*args, **kwargs)
        if NonLocals.full:
            NonLocals.root[KEY] = key
            NonLocals.root[RESULT] = r
            cache[key] = NonLocals.root
            NonLocals.root = NonLocals.root[NEXT]
            del cache[NonLocals.root[KEY]]
            NonLocals.root[KEY] = NonLocals.root[RESULT] = None
        else:
            last = NonLocals.root[PREV]
            link = [last, NonLocals.root, key, r]
            cache[key] = last[NEXT] = NonLocals.root[PREV] = link
            NonLocals.currsize += 1
            NonLocals.full = (NonLocals.currsize == CACHE_CAPACITY)
        NonLocals.misses += 1
        return r

    def cache_info():
        return NonLocals.hits, NonLocals.misses, NonLocals.currsize

    def cache_clear():
        cache.clear()
        NonLocals.root[:] = [NonLocals.root, NonLocals.root, None, None]
        NonLocals.hits = NonLocals.misses = NonLocals.currsize = 0
        NonLocals.full = False

    d = functools.wraps(f)(decorated)
    d.cache_info = cache_info
    d.cache_clear = cache_clear
    d.wrapped_func = f

    global _cached_funcs
    _cached_funcs.append(d)

    return d ADD_OP = '+'
SUBTRACT_OP = '-'
UNARY_SUBTRACT_OP = '_'
MULTIPLY_OP = '*'
DIVIDE_OP = '/'
EXPONENTIATE_OP = 'exp'
EQUAL_OP = '=='
NOT_EQUAL_OP = '!='
GREATER_OP = '>'
GREATER_EQUAL_OP = '>='
LESS_OP = '<'
LESS_EQUAL_OP = '<='
UNARY_NEGATION_OP = '!'
AND_OP = '&&'
OR_OP = '||'
VARIABLE_OP = 'v'
EXTERNAL_OP = 'extern'
TERNARY_SELECT_OP = '?'
FIXPOINT_OP = 'fix'
FOR_OP = 'for'
STATE_GETTER_OP = '()'
BARRIER_OP = ','
INDEX_ACCESS_OP = 'access'
INDEX_UPDATE_OP = 'update'
SUBSCRIPT_OP = 'subscript'
ARITHMETIC_OPERATORS = [
    ADD_OP, SUBTRACT_OP, UNARY_SUBTRACT_OP, MULTIPLY_OP, DIVIDE_OP,
    EXPONENTIATE_OP, TERNARY_SELECT_OP, FIXPOINT_OP, FOR_OP, BARRIER_OP,
]
COMPARISON_OPERATORS = [
    EQUAL_OP, NOT_EQUAL_OP, GREATER_OP, LESS_OP, GREATER_EQUAL_OP,
    LESS_EQUAL_OP,
]
BOOLEAN_OPERATORS = COMPARISON_OPERATORS + [
    UNARY_NEGATION_OP, AND_OP, OR_OP
]
TRADITIONAL_OPERATORS = [
    ADD_OP, SUBTRACT_OP, UNARY_SUBTRACT_OP, MULTIPLY_OP, DIVIDE_OP,
    EQUAL_OP, NOT_EQUAL_OP, GREATER_OP, LESS_OP, GREATER_EQUAL_OP,
    LESS_EQUAL_OP, UNARY_NEGATION_OP, AND_OP, OR_OP
]
SPECIAL_OPERATORS = [
    TERNARY_SELECT_OP, FIXPOINT_OP
]
OPERATORS = BOOLEAN_OPERATORS + ARITHMETIC_OPERATORS + SPECIAL_OPERATORS
UNARY_OPERATORS = [UNARY_SUBTRACT_OP, UNARY_NEGATION_OP]
BINARY_OPERATORS = list(set(OPERATORS) - set(UNARY_OPERATORS))
ASSOCIATIVITY_OPERATORS = [ADD_OP, MULTIPLY_OP, EQUAL_OP, AND_OP, OR_OP]
COMMUTATIVITY_OPERATORS = ASSOCIATIVITY_OPERATORS
COMMUTATIVE_DISTRIBUTIVITY_OPERATOR_PAIRS = [(MULTIPLY_OP, ADD_OP)]
LEFT_DISTRIBUTIVITY_OPERATOR_PAIRS = \
    COMMUTATIVE_DISTRIBUTIVITY_OPERATOR_PAIRS
RIGHT_DISTRIBUTIVITY_OPERATOR_PAIRS = \
    COMMUTATIVE_DISTRIBUTIVITY_OPERATOR_PAIRS
LEFT_DISTRIBUTIVITY_OPERATORS, LEFT_DISTRIBUTION_OVER_OPERATORS = \
    list(zip(*LEFT_DISTRIBUTIVITY_OPERATOR_PAIRS))
RIGHT_DISTRIBUTIVITY_OPERATORS, RIGHT_DISTRIBUTION_OVER_OPERATORS = \
    list(zip(*RIGHT_DISTRIBUTIVITY_OPERATOR_PAIRS))
COMPARISON_NEGATE_DICT = {
    LESS_OP: GREATER_EQUAL_OP,
    LESS_EQUAL_OP: GREATER_OP,
    GREATER_OP: LESS_EQUAL_OP,
    GREATER_EQUAL_OP: LESS_OP,
    EQUAL_OP: NOT_EQUAL_OP,
    NOT_EQUAL_OP: EQUAL_OP,
}
COMPARISON_MIRROR_DICT = {
    LESS_OP: GREATER_OP,
    LESS_EQUAL_OP: GREATER_EQUAL_OP,
    GREATER_OP: LESS_OP,
    GREATER_EQUAL_OP: LESS_EQUAL_OP,
    EQUAL_OP: EQUAL_OP,
    NOT_EQUAL_OP: NOT_EQUAL_OP,
} class BinaryBoolExpr(BinaryExpression, BoolExpr):
    """Binary boolean expressions."""

    __slots__ = () class Subscript(Expression):
    __slots__ = ()
    _str_brackets = False

    def __init__(self, *subscript):
        super().__init__(SUBSCRIPT_OP, *subscript)

    def __iter__(self):
        return iter(self.args)

    def format(self):
        return ''.join('[' + a.format() + ']' for a in self.args)

    def __repr__(self):
        return '{}({!r})'.format(self.__class__.__name__, self.args) def error_norm(errors):
    return _norm_func_map[context.norm](errors) class ErrorSemantics(Lattice):
    """The error semantics."""
    def __init__(self, v=None, e=None, top=False, bottom=False):
        super().__init__(top=top, bottom=bottom)
        if top or bottom:
            self.v = self.e = FloatInterval(top=top, bottom=bottom)
            return

        def error(v, e):
            if isinstance(e, FloatInterval):
                return e
            if e is not None:
                return overapproximate_error(e)
            if isinstance(v, Lattice):
                if v.is_top():
                    return FloatInterval(top=True)
                if v.is_bottom():
                    return FloatInterval(bottom=True)
            v_min, v_max = _unpack(v)
            if _are_instance(v, (int, mpz_type)):
                abs_val = max(abs(v_min), abs(v_max))
                if mpfr(abs_val) == abs_val:
                    # some integers cannot be expressed exactly in fp values
                    return FloatInterval(0)
            if v_min == v_max:
                return round_off_error_from_exact(v_min)
            return round_off_error(FloatInterval(v))

        if isinstance(v, ErrorSemantics):
            self.v, self.e = v
        else:
            self.v, self.e = FloatInterval(v), error(v, e)

    def is_top(self):
        return self.v.is_top()

    def is_bottom(self):
        return self.v.is_bottom()

    @_decorate_coerce
    def join(self, other, cls):
        if cls is not None:
            return cls(self) | cls(other)
        return self.__class__(self.v | other.v, self.e | other.e)

    @_decorate_coerce
    def meet(self, other, cls):
        if cls is not None:
            return cls(self) & cls(other)
        return self.__class__(self.v & other.v, self.e & other.e)

    @_decorate_coerce
    def le(self, other, cls):
        if cls is not None:
            return cls(self).le(cls(other))
        return self.v.le(other.v) and self.e.le(other.e)

    def __iter__(self):
        return iter((self.v, self.e))

    def __contains__(self, v):
        return self.v.min <= v <= self.v.max

    @_decorate_operator
    def __add__(self, other, cls):
        if cls is not None:
            return cls(self) + cls(other)
        self_v_min, self_v_max = self.v
        other_v_min, other_v_max = other.v
        if _propagate_constant and \
           self_v_min == self_v_max and other_v_min == other_v_max:
            v = mpq(self_v_min) + mpq(other_v_min)
            e = round_off_error_from_exact(v)
        else:
            v = self.v + other.v
            e = round_off_error(v)
        e += self.e + other.e
        return self.__class__(v, e)
    __radd__ = __add__

    @_decorate_operator
    def __sub__(self, other, cls):
        if cls is not None:
            return cls(self) - cls(other)
        self_v_min, self_v_max = self.v
        other_v_min, other_v_max = other.v
        if _propagate_constant and \
           self_v_min == self_v_max and other_v_min == other_v_max:
            v = mpq(self_v_min) - mpq(other_v_min)
            e = round_off_error_from_exact(v)
        else:
            v = self.v - other.v
            e = round_off_error(v)
        e += self.e - other.e
        return self.__class__(v, e)

    @_decorate_operator
    def __rsub__(self, other, cls):
        if cls is not None:
            return cls(other) - cls(self)
        return other - self

    @_decorate_operator
    def __mul__(self, other, cls):
        if cls is not None:
            return cls(self) * cls(other)
        e = self.e * other.e
        self_v_min, self_v_max = self.v
        other_v_min, other_v_max = other.v
        if _propagate_constant and \
           self_v_min == self_v_max and other_v_min == other_v_max:
            v = mpq(self_v_min) * mpq(other_v_min)
            e += round_off_error_from_exact(v)
        else:
            v = self.v * other.v
            e += round_off_error(v)
        e += self.v * other.e + other.v * self.e
        return self.__class__(v, e)
    __rmul__ = __mul__

    @_decorate_operator
    def __truediv__(self, other, cls):
        if cls is not None:
            return cls(self) / cls(other)
        self_v_min, self_v_max = self.v
        other_v_min, other_v_max = other.v
        if _propagate_constant and \
           self_v_min == self_v_max and other_v_min == other_v_max:
            v = mpq(self_v_min) / mpq(other_v_min)
            er = round_off_error_from_exact(v)
            v = mpfr(v)
        else:
            v = self.v / other.v
            er = round_off_error(v)
        e = self.e - v * other.e
        e /= other.v + other.e
        e += er
        return self.__class__(v, e)

    @_decorate_operator
    def __rtruediv__(self, other, cls):
        if cls is not None:
            return cls(other) / cls(self)
        return other / self

    def __neg__(self):
        if self.is_top() or self.is_bottom():
            return self
        return self.__class__(-self.v, -self.e)

    def exp(self):
        if self.is_top() or self.is_bottom():
            return self
        v_min, v_max = self.v
        if _propagate_constant and v_min == v_max:
            v = gmpy2.exp(mpq(v_min))
        else:
            v = self.v.exp()
        # exponentiation generally computes irrational numbers
        e = round_off_error(v)
        e += (self.e.exp() - 1) * v
        return self.__class__(v, e)

    @_decorate_operator
    def widen(self, other, cls):
        if cls is not None:
            return cls(self).widen(cls(other))
        return self.__class__(self.v.widen(other.v), self.e | other.e)

    def __abs__(self):
        return self.v + self.e

    def __getitem__(self, key):
        try:
            k_min, k_max = key
        except (TypeError, ValueError):
            raise KeyError(
                'Do not know how to produce the error interval from {}'
                .format(key))
        return ErrorSemantics(self.v, [k_min, k_max])

    def __str__(self):
        v = str(self.v)
        e = '' if self.e.min == self.e.max == 0 else str(self.e)
        if not e:
            return v
        if self.v.min == self.v.max:
            v = '[{}]'.format(v)
        if self.e.min == self.e.max:
            e = '[{}]'.format(e)
        return v + e

    def __repr__(self):
        return '{cls}({value!r}, {error!r})'.format(
            cls=self.__class__.__name__, value=self.v, error=self.e)

    def __hash__(self):
        self._hash = hash_val = hash((self.v, self.e))
        return hash_val class IntegerInterval(Interval):
    """The interval containing integer values."""
    def __init__(self, v=None, top=False, bottom=False):
        super().__init__(v, top=top, bottom=bottom)
        try:
            if self.min not in (-inf, inf):
                self.min = mpz(self.min)
            if self.max not in (-inf, inf):
                self.max = mpz(self.max)
        except AttributeError:
            'The interval is a top or bottom.'

    def __truediv__(self, other):
        return FloatInterval(self) / other class IntegerIntervalArray(MultiDimensionalArray):
    value_class = IntegerInterval class ErrorSemanticsArray(MultiDimensionalArray):
    value_class = ErrorSemantics
import collections
from soap.common import base_dispatcher, cached
from soap.expression import operators, BinaryBoolExpr, Subscript
from soap.semantics.error import error_norm, ErrorSemantics, IntegerInterval
from soap.semantics.linalg import IntegerIntervalArray, ErrorSemanticsArray
        from soap.semantics.functions.boolean import bool_eval
        from soap.semantics.functions.fixpoint import fix_expr_eval


_unary_operator_function_dictionary = {
    operators.UNARY_SUBTRACT_OP: lambda x: -x,
    operators.EXPONENTIATE_OP: lambda x: x.exp(),
}
_binary_operator_function_dictionary = {
    operators.ADD_OP: lambda x, y: x + y,
    operators.SUBTRACT_OP: lambda x, y: x - y,
    operators.MULTIPLY_OP: lambda x, y: x * y,
    operators.DIVIDE_OP: lambda x, y: x / y,
    operators.BARRIER_OP: lambda x, y: error_norm([x, y]),
}


class ArithmeticEvaluator(base_dispatcher()):

    def generic_execute(self, expr, state):
        raise TypeError('Do not know how to evaluate {!r}'.format(expr))

    def execute_numeral(self, expr, state):
        return expr

    def execute_PartitionLabel(self, expr, state):
        return expr.bound

    def _execute_args(self, expr, state):
        args = []
        for arg in expr.args:
            args.append(self(arg, state))
        return args

    def execute_Variable(self, expr, state):
        return state[expr]

    def execute_UnaryArithExpr(self, expr, state):
        a, = self._execute_args(expr, state)
        try:
            op = _unary_operator_function_dictionary[expr.op]
        except KeyError:
            raise KeyError('Unrecognized operator type {!r}'.format(op))
        return op(a)

    def execute_BinaryArithExpr(self, expr, state):
        a1, a2 = self._execute_args(expr, state)
        try:
            op = _binary_operator_function_dictionary[expr.op]
        except KeyError:
            raise KeyError('Unrecognized operator type {!r}'.format(self.op))
        return op(a1, a2)

    def execute_Subscript(self, expr, state):
        return IntegerIntervalArray(self._execute_args(expr, state))

    def execute_AccessExpr(self, expr, state):
        array, subscript = self._execute_args(expr, state)
        if array.is_bottom() or any(s.is_bottom() for s in subscript):
            return array.value_class(bottom=True)
        return array[subscript]

    def execute_UpdateExpr(self, expr, state):
        array, subscript, value = self._execute_args(expr, state)
        if array.is_bottom():
            return array
        if any(s.is_bottom() for s in subscript):
            return array.__class__(_shape=array.shape, bottom=True)
        return array.update(subscript, value)

    def execute_SelectExpr(self, expr, state):
        eval_split = lambda split_expr, split_state: self(
            split_expr, split_state)
        true_state, false_state = bool_eval(expr.bool_expr, state)
        true_value = eval_split(expr.true_expr, true_state)
        false_value = eval_split(expr.false_expr, false_state)
        return true_value | false_value

    def execute_FixExpr(self, expr, state):
        return fix_expr_eval(expr, state)

    def execute_PreUnrollExpr(self, expr, state):
        return self.execute_FixExpr(expr.a, state)

    def execute_MetaState(self, meta_state, state):
        return state.__class__({
            var: self(expr, state) for var, expr in meta_state.items()})

    @cached
    def __call__(self, expr, state):
        return super().__call__(expr, state)

    def __eq__(self, other):
        return self.__class__ == other.__class__

    def __hash__(self):
        return hash(self.__class__)


arith_eval = ArithmeticEvaluator()


def _to_norm(value):
    if isinstance(value, IntegerIntervalArray):
        if value.is_scalar():
            return value.scalar
        return error_norm(ErrorSemantics(v, 0) for v in value._flat_items)
    if isinstance(value, ErrorSemanticsArray):
        if value.is_scalar():
            return value.scalar
        return error_norm(value._flat_items)
    if isinstance(value, collections.Mapping):
        return error_norm(_to_norm(val) for val in value.values())
    return value


def error_eval(expr, state, to_norm=True):
    if isinstance(expr, (BinaryBoolExpr, Subscript)):
        return 0
    value = arith_eval(expr, state)
    if to_norm:
        value = _to_norm(value)

    if isinstance(value, IntegerInterval):