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 EQUAL_OP = '==' NOT_EQUAL_OP = '!=' GREATER_OP = '>' LESS_OP = '<' GREATER_EQUAL_OP = '>=' LESS_EQUAL_OP = '<=' UNARY_NEGATION_OP = '!' AND_OP = '&&' OR_OP = '||' BINARY_OPERATORS = list(set(OPERATORS) - set(UNARY_OPERATORS)) COMPARISON_OPERATORS = [
    EQUAL_OP, NOT_EQUAL_OP, GREATER_OP, LESS_OP, GREATER_EQUAL_OP,
    LESS_EQUAL_OP,
] 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,
} def is_variable(e):
    from soap.expression.variable import Variable
    return isinstance(e, Variable) class BinaryBoolExpr(BinaryExpression, BoolExpr):
    """Binary boolean expressions."""

    __slots__ = () def join(self, other):
    if self.is_top() or other.is_bottom():
        return self
    if self.is_bottom() or other.is_top():
        return other def meet(self, other):
    if self.is_top() or other.is_bottom():
        return other
    if self.is_bottom() or other.is_top():
        return self def _unpack(v):
def _are_instance(v, t):
def mpfr(v):
def mpq(v):
def ulp(v, underflow=True):
def overapproximate_error(e):
def round_off_error(v):
def round_off_error_from_exact(v):
def _coerce(self, other, always_return_class=True):
def _decorate_coerce(func):
    def wrapper(self, other):
def _decorate_operator(func):
    def wrapper(self, other):
    def __init__(self, v=None, top=False, bottom=False):
    def is_top(self):
    def is_bottom(self):
    def min(self):
    def min(self, v):
    def max(self):
    def max(self, v):
    def to_constant(self):
    def join(self, other, cls):
    def meet(self, other, cls):
    def le(self, other, cls):
    def __iter__(self):
    def __contains__(self, v):
    def __getitem__(self, key):
    def __add__(self, other, cls):
    def __sub__(self, other, cls):
    def __rsub__(self, other, cls):
    def __mul__(self, other, cls):
    def __truediv__(self, other, cls):
    def __rtruediv__(self, other, cls):
    def __neg__(self):
    def exp(self):
    def widen(self, other, cls):
    def __str__(self):
    def __repr__(self):
    def __hash__(self):
    def __init__(self, v=None, top=False, bottom=False):
    def __truediv__(self, other):
    def _vals_to_str(self):
    def __str__(self):
    def __init__(self, v=None, top=False, bottom=False):
    def __init__(self, v=None, top=False, bottom=False):
    def __init__(self, v=None, e=None, top=False, bottom=False):
        def error(v, e):
    def is_top(self):
    def is_bottom(self):
    def join(self, other, cls):
    def meet(self, other, cls):
    def le(self, other, cls):
    def __iter__(self):
    def __contains__(self, v):
    def __add__(self, other, cls):
    def __sub__(self, other, cls):
    def __rsub__(self, other, cls):
    def __mul__(self, other, cls):
    def __truediv__(self, other, cls):
    def __rtruediv__(self, other, cls):
    def __neg__(self):
    def exp(self):
    def widen(self, other, cls):
    def __abs__(self):
    def __getitem__(self, key):
    def __str__(self):
    def __repr__(self):
    def __hash__(self):
def _is_integer(v):
def cast(v=None):
def _ln_norm(errors, n):
def max_error(errors):
def geomean(errors):
def error_norm(errors):
class Interval(Lattice):
class IntegerInterval(Interval):
class _FloatIntervalFormatMixin(object):
class FloatInterval(_FloatIntervalFormatMixin, Interval):
class FractionInterval(_FloatIntervalFormatMixin, Interval):
class ErrorSemantics(Lattice):
import collections
import itertools
import math
from soap.common.cache import cached
from soap.context import context
from soap.expression import (
    BinaryBoolExpr, is_variable, LESS_OP, GREATER_OP, LESS_EQUAL_OP,
    GREATER_EQUAL_OP, EQUAL_OP, NOT_EQUAL_OP, UNARY_NEGATION_OP, AND_OP,
    OR_OP, COMPARISON_OPERATORS, BINARY_OPERATORS, COMPARISON_NEGATE_DICT,
    COMPARISON_MIRROR_DICT,
)
from soap.lattice import join, meet
from soap.semantics.error import (
    inf, ulp, mpz_type, mpfr_type,
    IntegerInterval, FloatInterval, ErrorSemantics
)
    from soap.semantics.functions.arithmetic import arith_eval
    from soap.transformer.utils import closure



def _rhs_eval(expr, state):
    bound = arith_eval(expr, state)
    if isinstance(bound, (int, mpz_type)):
        return IntegerInterval(bound)
    if isinstance(bound, (float, mpfr_type)):
        return FloatInterval(bound)
    if isinstance(bound, IntegerInterval):
        return bound
    if isinstance(bound, ErrorSemantics):
        # It cannot handle incorrect branching due to error in
        # evaluation of the expression.
        return bound.v
    raise TypeError(
        'Evaluation returns an unrecognized object: %r' % bound)


def _contract(op, dtype, bmin, bmax):
    if op not in [LESS_OP, GREATER_OP]:
        return bmin, bmax
    if dtype == IntegerInterval:
        bmin += 1
        bmax -= 1
    elif dtype == FloatInterval:
        bmin += ulp(bmin)

        bmax -= ulp(bmax)