class levels():
def set_context(**kwargs):
def get_context():
def header(s, l=levels.info):
def format(*args):
def log(*args, **kwargs):
def line(*args, **kwargs):
def rewrite(*args, **kwargs):
def persistent(name, *args, **kwargs):
def unpersistent(*args):
def local_context(**kwargs):
def log_level(l):
    def wrapper(f):
        def wrapped(*args, **kwargs):
def log_enable(l):
    def wrapper(f):
        def wrapped(*args, **kwargs):
def log_context(l):
    def wrapper():
def _init_level(): 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,
} def fix_expr_has_inner_loop(expr):
    from soap.expression.fixpoint import FixExpr
    if isinstance(expr, FixExpr):
        expr = expr.loop_state
    return _has_inner_loop(expr) class BinaryArithExpr(BinaryExpression, ArithExpr):
    """Binary arithmetic expressions."""

    __slots__ = ()

    def _attr(self):
        if self.op in COMMUTATIVITY_OPERATORS:
            args = frozenset(self.args)
        else:
            args = tuple(self.args)
        return (self.op, args) class SelectExpr(TernaryArithExpr):
    """Ternary expression with TERNARY_SELECT_OP operator."""

    __slots__ = ()

    def __init__(self, a1, a2, a3):
        super().__init__(TERNARY_SELECT_OP, a1, a2, a3)

    @property
    def bool_expr(self):
        return self.a1

    @property
    def true_expr(self):
        return self.a2

    @property
    def false_expr(self):
        return self.a3

    def format(self):
        return '{} ? {} : {}'.format(*self._args_to_str()) class BinaryBoolExpr(BinaryExpression, BoolExpr):
    """Binary boolean expressions."""

    __slots__ = () class FixExpr(QuaternaryArithExpr):
    """Fixpoint expression."""

    def __init__(self, a1, a2, a3, a4):
        super().__init__(FIXPOINT_OP, a1, a2, a3, a4)

    @property
    def bool_expr(self):
        return self.a1

    @property
    def loop_state(self):
        return self.a2

    @property
    def loop_var(self):
        return self.a3

    @property
    def init_state(self):
        return self.a4

    def format(self):
        fixpoint_var = underline('e')
        s = ('{op}(λ{fvar}.({bool_expr} ? {fvar} % {loop_state} : {var}))'
             ' % {init_state}')
        return s.format(
            fvar=fixpoint_var, op=self.op, bool_expr=self.bool_expr,
            loop_state=self.loop_state.format(), var=self.loop_var,
            init_state=self.init_state.format()) 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 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 ArithmeticEvaluator(base_dispatcher()):
    def generic_execute(self, expr, state):
    def execute_numeral(self, expr, state):
    def execute_PartitionLabel(self, expr, state):
    def _execute_args(self, expr, state):
    def execute_Variable(self, expr, state):
    def execute_UnaryArithExpr(self, expr, state):
    def execute_BinaryArithExpr(self, expr, state):
    def execute_Subscript(self, expr, state):
    def execute_AccessExpr(self, expr, state):
    def execute_UpdateExpr(self, expr, state):
    def execute_SelectExpr(self, expr, state):
    def execute_FixExpr(self, expr, state):
    def execute_PreUnrollExpr(self, expr, state):
    def execute_MetaState(self, meta_state, state):
    def __call__(self, expr, state):
    def __eq__(self, other):
    def __hash__(self):
def _to_norm(value):
def error_eval(expr, state, to_norm=True): @cached
def bool_eval(expr, state):
    if state.is_bottom():
        return state, state
    constraints = construct(expr)
    true_list, false_list = [], []
    for cstr in constraints:
        cstr_list = []
        for cmp_expr in cstr:
            cmp_eval_list = [
                _comparison_eval(cmp_expr, state)
                for cmp_expr in _bool_transform(cmp_expr)]
            cstr_list += cmp_eval_list
        if not cstr_list:
            # empty, don't know how to constraint values
            return state, state
        true, false = zip(*cstr_list)
        true_list.append(meet(true))
        false_list.append(join(false))
    return join(true_list), meet(false_list) def expand_expr(expr, meta_state):
    if isinstance(expr, FixExpr):
        return expression_factory(
            expr.op, expr.bool_expr, expr.loop_state, expr.loop_var,
            expand_meta_state(expr.init_state, meta_state))
    if is_expression(expr):
        args = [expand_expr(a, meta_state) for a in expr.args]
        return expression_factory(expr.op, *args)
    if is_variable(expr):
        try:
            new_expr = meta_state[expr]
        except KeyError:
            raise KeyError(
                'Cannot expand the expression {expr}, missing variable in '
                '{state}'.format(expr=expr, state=meta_state))
        return new_expr
    if is_numeral(expr):
        return expr
    raise TypeError(
        'Do not know how to expand the expression {expr} with expression '
        'state {state}.'.format(expr=expr, state=meta_state)) def expand_meta_state(meta_state, state):
    """Expand meta_state with state."""
    return _eval_meta_state_with_func(expand_expr, meta_state, state) class MultiDimensionalArray(Lattice, collections.Sequence):
    __slots__ = ('_flat_items', 'scalar', 'shape', '_c_top', '_c_bottom')
    value_class = None

    def __init__(self, items=None, scalar=None, _flat_items=None,
                 _shape=None, bottom=False, top=False):
        super().__init__(bottom=bottom, top=top)
        self.shape = _shape
        if top or bottom:
            return
        self.scalar = scalar
        if scalar is None:
            self._init_flat_items(items, _flat_items, _shape)

    def is_scalar(self):
        return self.scalar is not None

    def _init_flat_items(self, items, _flat_items, _shape):
        def append_flat_items(flattened_flat_items, items):
            n = [len(items)]
            if not isinstance(items[0], (list, tuple)):
                flattened_flat_items += items
                return n
            first_len_list = None
            for each in items:
                each_len_list = append_flat_items(flattened_flat_items, each)
                if first_len_list is None:
                    first_len_list = each_len_list
                if each_len_list != first_len_list:
                    raise ValueError('Shape mismatch.')
            return n + first_len_list

        if _flat_items is not None:
            self.shape = _shape
            if not isinstance(_flat_items, tuple):
                _flat_items = tuple(_flat_items)
            self._flat_items = _flat_items
        else:
            flattened_flat_items = []
            shape = tuple(append_flat_items(flattened_flat_items, items))
            self.shape = _shape or shape
            self._flat_items = tuple(
                item if isinstance(item, self.value_class) else
                self.value_class(item) for item in flattened_flat_items)

        # set up shape_prod for index translation
        shape_prod = []
        prod = 1
        for size in reversed(self.shape):
            shape_prod.append(prod)
            prod *= size
        self._shape_prod = tuple(reversed(shape_prod))

    @property
    def size(self):
        return functools.reduce(lambda x, y: x * y, self.shape)

    def is_top(self):
        try:
            return self._c_top
        except AttributeError:
            pass
        if self.scalar is not None:
            top = self.scalar.is_top()
        else:
            top = all(i.is_top() for i in self._flat_items)
        self._c_top = top
        return top

    def is_bottom(self):
        try:
            return self._c_top
        except AttributeError:
            pass
        if self.scalar is not None:
            bot = self.scalar.is_bottom()
        else:
            bot = all(i.is_bottom() for i in self._flat_items)
        self._c_bottom = bot
        return bot

    def join(self, other):
        if self.shape != other.shape:
            raise ValueError('Shape mismatch.')
        if self.scalar is not None:
            return self.__class__(
                scalar=self.scalar.join(other.scalar), _shape=self.shape)
        items = tuple(
            x.join(y) for x, y in zip(self._flat_items, other._flat_items))
        return self.__class__(_flat_items=items, _shape=self.shape)

    def meet(self, other):
        if self.shape != other.shape:
            raise ValueError('Shape mismatch.')
        if self.scalar is not None:
            return self.__class__(
                scalar=self.scalar.meet(other.scalar), _shape=self.shape)
        items = tuple(
            x.meet(y) for x, y in zip(self._flat_items, other._flat_items))
        return self.__class__(_flat_items=items, _shape=self.shape)

    def _to_flat_index(self, index):
        return sum((i * p for i, p in zip(index, self._shape_prod)))

    def to_nested_list(self):
        items = self._flat_items
        # woah?
        for s in reversed(self.shape[1:]):
            items = [list(items[i:i + s]) for i in range(0, len(items), s)]
        return items

    def transpose(self):
        if len(self.shape) != 2:
            raise TypeError('The array being transposed is not a matrix.')
        raise NotImplementedError

    @property
    def T(self):
        return self.transpose()

    def _normalize_index(self, index):
        if not isinstance(index, collections.Sequence):
            index = [index]

        index_iterer = []
        for (i, s) in zip(index, self.shape):
            if isinstance(i, int):
                if not (0 <= i < s):
                    raise IndexError('Index out of range')
                index_iterer.append([i])
            elif isinstance(i, (list, IntegerInterval)):
                min_val, max_val = i
                if not (0 <= min_val <= max_val < s):
                    raise IndexError(
                        'Index interval {} out of range {}'.format(i, s))
                index_iterer.append(range(min_val, max_val + 1))
            else:
                raise TypeError(
                    'Index must be an integer or an IntegerInterval.')
        return tuple(itertools.product(*index_iterer))

    def __getitem__(self, index):
        top = self.is_top()
        bottom = self.is_bottom()
        if top or bottom:
            return self.value_class(top=top, bottom=bottom)

        if self.scalar is not None:
            return self.scalar

        # fast path for one-dimensional arrays
        if isinstance(index, int):
            return self._flat_items[index]

        items = []
        for i in self._normalize_index(index):
            item = self._flat_items[self._to_flat_index(i)]
            items.append(item)
        return join(items)

    def update(self, index, value):
        top = self.is_top()
        bottom = self.is_bottom()
        shape = self.shape

        if self.scalar is not None:
            if top or bottom:
                return self
            value = value.join(self.scalar)
            return self.__class__(scalar=value, _shape=shape)

        if top or bottom:
            # extrapolate items in the matrix
            other_value = self.value_class(top=top, bottom=bottom)
            items = [other_value] * self.size
        else:
            cls = self.value_class
            if not isinstance(value, cls):
                value = cls(value)
            items = list(self._flat_items)

        # fast path for one-dimensional arrays
        if isinstance(index, int):
            items[index] = value
            return self.__class__(_flat_items=items, _shape=shape)

        indices = self._normalize_index(index)

        # only a specific item is changed
        if len(indices) == 1:
            items[self._to_flat_index(indices[0])] = value
            return self.__class__(_flat_items=items, _shape=shape)

        for index in indices:
            index = self._to_flat_index(index)
            items[index] |= value

        return self.__class__(_flat_items=items, _shape=shape)

    def le(self, other):
        if self.shape != other.shape:
            raise ValueError('Cannot compare arrays with different shapes.')
        if self.scalar is not None:
            return self.scalar.le(other.scalar)
        return all(
            x.le(y) for x, y in zip(self._flat_items, other._flat_items))

    def widen(self, other):
        if self.scalar is not None:
            return self.__class__(
                scalar=self.scalar.widen(other.scalar), _shape=self.shape)
        items = [
            x.widen(y) for x, y in zip(self._flat_items, other._flat_items)]
        return self.__class__(_flat_items=items, _shape=self.shape)

    def __len__(self):
        return self.size()

    def __eq__(self, other):
        if not isinstance(other, self.__class__):
            return False
        if self.shape != other.shape:
            return False
        if self.scalar is not None:
            return self.scalar == other.scalar
        return self._flat_items == other._flat_items

    def __hash__(self):
        if self.scalar is not None:
            hash_val = hash((self.scalar, self.shape))
        else:
            hash_val = hash((self._flat_items, self.shape))
        self._hash = hash_val
        return hash_val

    def _format_matrix(self):
        items = []
        widths = [0] * self.shape[1]
        for row in self.to_nested_list():
            new_row = []
            for idx, val in enumerate(row):
                val = str(val)
                new_row.append(val)
                widths[idx] = max(widths[idx], len(val))
            items.append(new_row)
        if len(widths) == 1:
            return '[{}]'.format(
                '\n '.join(
                    '{val:^{len}}'.format(val=row[0], len=widths[0])
                    for row in items))
        return '[{}]'.format(
            '\n '.join(
                '[{}]'.format(' '.join(
                    '{val:^{len}}'.format(val=v, len=widths[i])
                    for i, v in enumerate(row)))
                for row in items))

    def __str__(self):
        if self.scalar is not None:
            shape = 'x'.join(str(s) for s in self.shape)
            return '[{}: {}]'.format(shape, self.scalar)
        if len(self.shape) == 1:
            return '[{}]'.format(', '.join(str(v) for v in self._flat_items))
        if len(self.shape) == 2:
            return self._format_matrix()
        return str(self.to_nested_list())

    def __repr__(self):
        if self.scalar is not None:
            return '{}(scalar={!r}, _shape={!r})'.format(
                self.__class__.__name__, self.scalar, self.shape)
        return '{}({!r})'.format(self.__class__.__name__, self._flat_items)
from soap import logger
from soap.context import context
from soap.common.cache import cached
from soap.expression import (
    operators, BinaryArithExpr, BinaryBoolExpr, FixExpr, SelectExpr,
    fix_expr_has_inner_loop
)
from soap.semantics.error import IntegerInterval, ErrorSemantics
from soap.semantics.functions.arithmetic import arith_eval
from soap.semantics.functions.boolean import bool_eval
from soap.semantics.functions.meta import (
    expand_expr, expand_meta_state
)
from soap.semantics.linalg import MultiDimensionalArray
    from soap.semantics.state import BoxState
        from soap.semantics.schedule.extract import (
            ForLoopNestExtractor, ForLoopExtractorTripCountError
        )
    from soap.semantics.state import BoxState
    from soap.semantics.state.meta import MetaState
    from soap.semantics.state.meta import MetaState
    from soap.semantics.schedule.common import iter_point_count
    from soap.transformer.linalg import linear_algebra_simplify
    from soap.semantics.schedule.extract import ForLoopExtractor
    if isinstance(value, BoxState):
        return BoxState({
            key: _extrapolate(key_value, factor)
            for key, key_value in value.items()})
    raise TypeError('Do not know how to extrapolate {}'.format(value))


class TripCount(object):
    def __init__(self, fix_expr):
        super().__init__()
        self.fix_expr = fix_expr

    def get(self):
        try:
            return self._trip_count
        except AttributeError:
            pass
        extractor = ForLoopNestExtractor(self.fix_expr)
        try:
            trip_count = extractor.trip_count
        except ForLoopExtractorTripCountError as e:
            logger.warning(
                'Failed to find trip count for loop {}, reason: {}'
                .format(self.fix_expr, e))
            trip_count = None
        self._trip_count = trip_count
        return trip_count


def _is_fast_finish(
        iteration, entry_state, entry_join_state, exit_join_state, loop_state,
        loop_end_join_state, trip_count):

    if trip_count is None:
        logger.warning('Cannot enable fast path.')
        return

    fast_factor = context.fast_factor
    if fast_factor <= 0 or fast_factor >= 1:
        return

    curr_factor = iteration / trip_count
    if curr_factor < fast_factor:
        return

    info = {
        'entry': entry_join_state,
        'exit': exit_join_state | loop_state,
        'last_entry': entry_state,
        'last_exit': loop_state,
        'end': loop_end_join_state,
    }
    factor = curr_factor / fast_factor
    info = {
        key: value if value.is_bottom() else
        _extrapolate(value, factor) for key, value in info.items()}
    info.update(trip_count=trip_count, path='fast_factor')
    return info


@cached
def fixpoint_eval(fix_expr, state, run_init_state=False):
    """
    Computes the least fixpoint of the function F::

    F(g) = lambda v . {
        (g v) * loop_state   if bool_expr v == true
        g v                  otherwise
    """

    state = state or BoxState(bottom=True)

    if run_init_state:
        state = arith_eval(fix_expr.init_state, state)

    if state.is_bottom():
        # shortcut for bottom values
        return {
            'entry': state,
            'exit': state,
            'last_entry': state,
            'last_exit': state,
            'end': state,
            'trip_count': 0,
            'path': 'bottom_shortcut',
        }

    loop_meta_state = fix_expr.loop_state
    bool_expr = fix_expr.bool_expr
    trip_count = TripCount(fix_expr)

    if context.fast_outer and fix_expr_has_inner_loop(fix_expr):
        exit_state = arith_eval(loop_meta_state, state)
        return {
            'entry': state,
            'exit': exit_state,
            'last_entry': state,
            'last_exit': exit_state,
            'end': exit_state,
            'trip_count': trip_count.get(),
            'path': 'fast_outer',
        }

    iteration = 0
    state_class = state.__class__

    # input state
    loop_state = state

    # initial state values
    entry_state = entry_join_state = exit_join_state = state.empty()
    prev_entry_state = prev_entry_join_state = state.empty()
    prev_loop_state = loop_end_join_state = state.empty()

    while True:
        iteration += 1

        logger.persistent('Iteration', iteration, l=logger.levels.debug)

        # split state by the conditional of the while loop

        entry_state, exit_state = bool_eval(bool_expr, loop_state)