z3py.py

Go to the documentation of this file.

 
 
"""Z3 is a high performance theorem prover developed at Microsoft Research.
 
Z3 is used in many applications such as: software/hardware verification and testing,
constraint solving, analysis of hybrid systems, security, biology (in silico analysis),
and geometrical problems.
 
 
Please send feedback, comments and/or corrections on the Issue tracker for
https://github.com/Z3prover/z3.git. Your comments are very valuable.
 
Small example:
 
>>> x = Int('x')
>>> y = Int('y')
>>> s = Solver()
>>> s.add(x > 0)
>>> s.add(x < 2)
>>> s.add(y == x + 1)
>>> s.check()
sat
>>> m = s.model()
>>> m[x]
1
>>> m[y]
2
 
Z3 exceptions:
 
>>> try:
...   x = BitVec('x', 32)
...   y = Bool('y')
...   # the expression x + y is type incorrect
...   n = x + y
... except Z3Exception as ex:
...   print("failed: %s" % ex)
failed: sort mismatch
"""
from . import z3core
from .z3core import *
from .z3types import *
from .z3consts import *
from .z3printer import *
from fractions import Fraction
import sys
import io
import math
import copy
if sys.version_info.major >= 3:
    from typing import Iterable
 
Z3_DEBUG = __debug__
 
 
def z3_debug():
    global Z3_DEBUG
    return Z3_DEBUG
 
 
if sys.version_info.major < 3:
    def _is_int(v):
        return isinstance(v, (int, long))
else:
    def _is_int(v):
        return isinstance(v, int)
 
 
def enable_trace(msg):
    Z3_enable_trace(msg)
 
 
def disable_trace(msg):
    Z3_disable_trace(msg)
 
 
def get_version_string():
    major = ctypes.c_uint(0)
    minor = ctypes.c_uint(0)
    build = ctypes.c_uint(0)
    rev = ctypes.c_uint(0)
    Z3_get_version(major, minor, build, rev)
    return "%s.%s.%s" % (major.value, minor.value, build.value)
 
 
def get_version():
    major = ctypes.c_uint(0)
    minor = ctypes.c_uint(0)
    build = ctypes.c_uint(0)
    rev = ctypes.c_uint(0)
    Z3_get_version(major, minor, build, rev)
    return (major.value, minor.value, build.value, rev.value)
 
 
def get_full_version():
    return Z3_get_full_version()
 
 
def _z3_assert(cond, msg):
    if not cond:
        raise Z3Exception(msg)
 
 
def _z3_check_cint_overflow(n, name):
    _z3_assert(ctypes.c_int(n).value == n, name + " is too large")
 
 
def open_log(fname):
    """Log interaction to a file. This function must be invoked immediately after init(). """
    Z3_open_log(fname)
 
 
def append_log(s):
    """Append user-defined string to interaction log. """
    Z3_append_log(s)
 
 
def to_symbol(s, ctx=None):
    """Convert an integer or string into a Z3 symbol."""
    if _is_int(s):
        return Z3_mk_int_symbol(_get_ctx(ctx).ref(), s)
    else:
        return Z3_mk_string_symbol(_get_ctx(ctx).ref(), s)
 
 
def _symbol2py(ctx, s):
    """Convert a Z3 symbol back into a Python object. """
    if Z3_get_symbol_kind(ctx.ref(), s) == Z3_INT_SYMBOL:
        return "k!%s" % Z3_get_symbol_int(ctx.ref(), s)
    else:
        return Z3_get_symbol_string(ctx.ref(), s)
 
# Hack for having nary functions that can receive one argument that is the
# list of arguments.
# Use this when function takes a single list of arguments
 
 
def _get_args(args):
    try:
        if len(args) == 1 and (isinstance(args[0], tuple) or isinstance(args[0], list)):
            return args[0]
        elif len(args) == 1 and (isinstance(args[0], set) or isinstance(args[0], AstVector)):
            return [arg for arg in args[0]]
        else:
            return args
    except TypeError:  # len is not necessarily defined when args is not a sequence (use reflection?)
        return args
 
# Use this when function takes multiple arguments
 
 
def _get_args_ast_list(args):
    try:
        if isinstance(args, (set, AstVector, tuple)):
            return [arg for arg in args]
        else:
            return args
    except Exception:
        return args
 
 
def _to_param_value(val):
    if isinstance(val, bool):
        return "true" if val else "false"
    return str(val)
 
 
def z3_error_handler(c, e):
    # Do nothing error handler, just avoid exit(0)
    # The wrappers in z3core.py will raise a Z3Exception if an error is detected
    return
 
 
class Context:
    """A Context manages all other Z3 objects, global configuration options, etc.
 
    Z3Py uses a default global context. For most applications this is sufficient.
    An application may use multiple Z3 contexts. Objects created in one context
    cannot be used in another one. However, several objects may be "translated" from
    one context to another. It is not safe to access Z3 objects from multiple threads.
    The only exception is the method `interrupt()` that can be used to interrupt() a long
    computation.
    The initialization method receives global configuration options for the new context.
    """
 
    def __init__(self, *args, **kws):
        if z3_debug():
            _z3_assert(len(args) % 2 == 0, "Argument list must have an even number of elements.")
        conf = Z3_mk_config()
        for key in kws:
            value = kws[key]
            Z3_set_param_value(conf, str(key).upper(), _to_param_value(value))
        prev = None
        for a in args:
            if prev is None:
                prev = a
            else:
                Z3_set_param_value(conf, str(prev), _to_param_value(a))
                prev = None
        self.ctxctx = Z3_mk_context_rc(conf)
        self.ownerowner = True
        self.eheh = Z3_set_error_handler(self.ctxctx, z3_error_handler)
        Z3_set_ast_print_mode(self.ctxctx, Z3_PRINT_SMTLIB2_COMPLIANT)
        Z3_del_config(conf)
 
    def __del__(self):
        if Z3_del_context is not None and self.ownerowner:
            Z3_del_context(self.ctxctx)
        self.ctxctx = None
        self.eheh = None
 
    def ref(self):
        """Return a reference to the actual C pointer to the Z3 context."""
        return self.ctxctx
 
    def interrupt(self):
        """Interrupt a solver performing a satisfiability test, a tactic processing a goal, or simplify functions.
 
        This method can be invoked from a thread different from the one executing the
        interruptible procedure.
        """
        Z3_interrupt(self.refref())
 
    def param_descrs(self):
        """Return the global parameter description set."""
        return ParamDescrsRef(Z3_get_global_param_descrs(self.refref()), self)
        
 
# Global Z3 context
_main_ctx = None
 
 
def main_ctx():
    """Return a reference to the global Z3 context.
 
    >>> x = Real('x')
    >>> x.ctx == main_ctx()
    True
    >>> c = Context()
    >>> c == main_ctx()
    False
    >>> x2 = Real('x', c)
    >>> x2.ctx == c
    True
    >>> eq(x, x2)
    False
    """
    global _main_ctx
    if _main_ctx is None:
        _main_ctx = Context()
    return _main_ctx
 
 
def _get_ctx(ctx):
    if ctx is None:
        return main_ctx()
    else:
        return ctx
 
 
def get_ctx(ctx):
    return _get_ctx(ctx)
 
 
def set_param(*args, **kws):
    """Set Z3 global (or module) parameters.
 
    >>> set_param(precision=10)
    """
    if z3_debug():
        _z3_assert(len(args) % 2 == 0, "Argument list must have an even number of elements.")
    new_kws = {}
    for k in kws:
        v = kws[k]
        if not set_pp_option(k, v):
            new_kws[k] = v
    for key in new_kws:
        value = new_kws[key]
        Z3_global_param_set(str(key).upper(), _to_param_value(value))
    prev = None
    for a in args:
        if prev is None:
            prev = a
        else:
            Z3_global_param_set(str(prev), _to_param_value(a))
            prev = None
 
 
def reset_params():
    """Reset all global (or module) parameters.
    """
    Z3_global_param_reset_all()
 
 
def set_option(*args, **kws):
    """Alias for 'set_param' for backward compatibility.
    """
    return set_param(*args, **kws)
 
 
def get_param(name):
    """Return the value of a Z3 global (or module) parameter
 
    >>> get_param('nlsat.reorder')
    'true'
    """
    ptr = (ctypes.c_char_p * 1)()
    if Z3_global_param_get(str(name), ptr):
        r = z3core._to_pystr(ptr[0])
        return r
    raise Z3Exception("failed to retrieve value for '%s'" % name)
 
 
 
# Mark objects that use pretty printer
 
 
class Z3PPObject:
    """Superclass for all Z3 objects that have support for pretty printing."""
 
    def use_pp(self):
        return True
 
    def _repr_html_(self):
        in_html = in_html_mode()
        set_html_mode(True)
        res = repr(self)
        set_html_mode(in_html)
        return res
 
 
class AstRef(Z3PPObject):
    """AST are Direct Acyclic Graphs (DAGs) used to represent sorts, declarations and expressions."""
 
    def __init__(self, ast, ctx=None):
        self.astast = ast
        self.ctxctx = _get_ctx(ctx)
        Z3_inc_ref(self.ctxctx.ref(), self.as_astas_ast())
 
    def __del__(self):
        if self.ctxctx.ref() is not None and self.astast is not None and Z3_dec_ref is not None:
            Z3_dec_ref(self.ctxctx.ref(), self.as_astas_ast())
            self.astast = None
 
    def __deepcopy__(self, memo={}):
        return _to_ast_ref(self.astast, self.ctxctx)
 
    def __str__(self):
        return obj_to_string(self)
 
    def __repr__(self):
        return obj_to_string(self)
 
    def __eq__(self, other):
        return self.eqeq(other)
 
    def __hash__(self):
        return self.hashhash()
 
    def __nonzero__(self):
        return self.__bool____bool__()
 
    def __bool__(self):
        if is_true(self):
            return True
        elif is_false(self):
            return False
        elif is_eq(self) and self.num_args() == 2:
            return self.arg(0).eq(self.arg(1))
        else:
            raise Z3Exception("Symbolic expressions cannot be cast to concrete Boolean values.")
 
    def sexpr(self):
        """Return a string representing the AST node in s-expression notation.
 
        >>> x = Int('x')
        >>> ((x + 1)*x).sexpr()
        '(* (+ x 1) x)'
        """
        return Z3_ast_to_string(self.ctx_refctx_ref(), self.as_astas_ast())
 
    def as_ast(self):
        """Return a pointer to the corresponding C Z3_ast object."""
        return self.astast
 
    def get_id(self):
        """Return unique identifier for object. It can be used for hash-tables and maps."""
        return Z3_get_ast_id(self.ctx_refctx_ref(), self.as_astas_ast())
 
    def ctx_ref(self):
        """Return a reference to the C context where this AST node is stored."""
        return self.ctxctx.ref()
 
    def eq(self, other):
        """Return `True` if `self` and `other` are structurally identical.
 
        >>> x = Int('x')
        >>> n1 = x + 1
        >>> n2 = 1 + x
        >>> n1.eq(n2)
        False
        >>> n1 = simplify(n1)
        >>> n2 = simplify(n2)
        >>> n1.eq(n2)
        True
        """
        if z3_debug():
            _z3_assert(is_ast(other), "Z3 AST expected")
        return Z3_is_eq_ast(self.ctx_refctx_ref(), self.as_astas_ast(), other.as_ast())
 
    def translate(self, target):
        """Translate `self` to the context `target`. That is, return a copy of `self` in the context `target`.
 
        >>> c1 = Context()
        >>> c2 = Context()
        >>> x  = Int('x', c1)
        >>> y  = Int('y', c2)
        >>> # Nodes in different contexts can't be mixed.
        >>> # However, we can translate nodes from one context to another.
        >>> x.translate(c2) + y
        x + y
        """
        if z3_debug():
            _z3_assert(isinstance(target, Context), "argument must be a Z3 context")
        return _to_ast_ref(Z3_translate(self.ctxctx.ref(), self.as_astas_ast(), target.ref()), target)
 
    def __copy__(self):
        return self.translatetranslate(self.ctxctx)
 
    def hash(self):
        """Return a hashcode for the `self`.
 
        >>> n1 = simplify(Int('x') + 1)
        >>> n2 = simplify(2 + Int('x') - 1)
        >>> n1.hash() == n2.hash()
        True
        """
        return Z3_get_ast_hash(self.ctx_refctx_ref(), self.as_astas_ast())
 
 
def is_ast(a):
    """Return `True` if `a` is an AST node.
 
    >>> is_ast(10)
    False
    >>> is_ast(IntVal(10))
    True
    >>> is_ast(Int('x'))
    True
    >>> is_ast(BoolSort())
    True
    >>> is_ast(Function('f', IntSort(), IntSort()))
    True
    >>> is_ast("x")
    False
    >>> is_ast(Solver())
    False
    """
    return isinstance(a, AstRef)
 
 
def eq(a, b):
    """Return `True` if `a` and `b` are structurally identical AST nodes.
 
    >>> x = Int('x')
    >>> y = Int('y')
    >>> eq(x, y)
    False
    >>> eq(x + 1, x + 1)
    True
    >>> eq(x + 1, 1 + x)
    False
    >>> eq(simplify(x + 1), simplify(1 + x))
    True
    """
    if z3_debug():
        _z3_assert(is_ast(a) and is_ast(b), "Z3 ASTs expected")
    return a.eq(b)
 
 
def _ast_kind(ctx, a):
    if is_ast(a):
        a = a.as_ast()
    return Z3_get_ast_kind(ctx.ref(), a)
 
 
def _ctx_from_ast_arg_list(args, default_ctx=None):
    ctx = None
    for a in args:
        if is_ast(a) or is_probe(a):
            if ctx is None:
                ctx = a.ctx
            else:
                if z3_debug():
                    _z3_assert(ctx == a.ctx, "Context mismatch")
    if ctx is None:
        ctx = default_ctx
    return ctx
 
 
def _ctx_from_ast_args(*args):
    return _ctx_from_ast_arg_list(args)
 
 
def _to_func_decl_array(args):
    sz = len(args)
    _args = (FuncDecl * sz)()
    for i in range(sz):
        _args[i] = args[i].as_func_decl()
    return _args, sz
 
 
def _to_ast_array(args):
    sz = len(args)
    _args = (Ast * sz)()
    for i in range(sz):
        _args[i] = args[i].as_ast()
    return _args, sz
 
 
def _to_ref_array(ref, args):
    sz = len(args)
    _args = (ref * sz)()
    for i in range(sz):
        _args[i] = args[i].as_ast()
    return _args, sz
 
 
def _to_ast_ref(a, ctx):
    k = _ast_kind(ctx, a)
    if k == Z3_SORT_AST:
        return _to_sort_ref(a, ctx)
    elif k == Z3_FUNC_DECL_AST:
        return _to_func_decl_ref(a, ctx)
    else:
        return _to_expr_ref(a, ctx)
 
 
 
 
def _sort_kind(ctx, s):
    return Z3_get_sort_kind(ctx.ref(), s)
 
 
class SortRef(AstRef):
    """A Sort is essentially a type. Every Z3 expression has a sort. A sort is an AST node."""
 
    def as_ast(self):
        return Z3_sort_to_ast(self.ctx_refctx_ref(), self.astast)
 
    def get_id(self):
        return Z3_get_ast_id(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
    def kind(self):
        """Return the Z3 internal kind of a sort.
        This method can be used to test if `self` is one of the Z3 builtin sorts.
 
        >>> b = BoolSort()
        >>> b.kind() == Z3_BOOL_SORT
        True
        >>> b.kind() == Z3_INT_SORT
        False
        >>> A = ArraySort(IntSort(), IntSort())
        >>> A.kind() == Z3_ARRAY_SORT
        True
        >>> A.kind() == Z3_INT_SORT
        False
        """
        return _sort_kind(self.ctxctx, self.astast)
 
    def subsort(self, other):
        """Return `True` if `self` is a subsort of `other`.
 
        >>> IntSort().subsort(RealSort())
        True
        """
        return False
 
    def cast(self, val):
        """Try to cast `val` as an element of sort `self`.
 
        This method is used in Z3Py to convert Python objects such as integers,
        floats, longs and strings into Z3 expressions.
 
        >>> x = Int('x')
        >>> RealSort().cast(x)
        ToReal(x)
        """
        if z3_debug():
            _z3_assert(is_expr(val), "Z3 expression expected")
            _z3_assert(self.eqeq(val.sort()), "Sort mismatch")
        return val
 
    def name(self):
        """Return the name (string) of sort `self`.
 
        >>> BoolSort().name()
        'Bool'
        >>> ArraySort(IntSort(), IntSort()).name()
        'Array'
        """
        return _symbol2py(self.ctxctx, Z3_get_sort_name(self.ctx_refctx_ref(), self.astast))
 
    def __eq__(self, other):
        """Return `True` if `self` and `other` are the same Z3 sort.
 
        >>> p = Bool('p')
        >>> p.sort() == BoolSort()
        True
        >>> p.sort() == IntSort()
        False
        """
        if other is None:
            return False
        return Z3_is_eq_sort(self.ctx_refctx_ref(), self.astast, other.ast)
 
    def __ne__(self, other):
        """Return `True` if `self` and `other` are not the same Z3 sort.
 
        >>> p = Bool('p')
        >>> p.sort() != BoolSort()
        False
        >>> p.sort() != IntSort()
        True
        """
        return not Z3_is_eq_sort(self.ctx_refctx_ref(), self.astast, other.ast)
 
    def __hash__(self):
        """ Hash code. """
        return AstRef.__hash__(self)
 
 
def is_sort(s):
    """Return `True` if `s` is a Z3 sort.
 
    >>> is_sort(IntSort())
    True
    >>> is_sort(Int('x'))
    False
    >>> is_expr(Int('x'))
    True
    """
    return isinstance(s, SortRef)
 
 
def _to_sort_ref(s, ctx):
    if z3_debug():
        _z3_assert(isinstance(s, Sort), "Z3 Sort expected")
    k = _sort_kind(ctx, s)
    if k == Z3_BOOL_SORT:
        return BoolSortRef(s, ctx)
    elif k == Z3_INT_SORT or k == Z3_REAL_SORT:
        return ArithSortRef(s, ctx)
    elif k == Z3_BV_SORT:
        return BitVecSortRef(s, ctx)
    elif k == Z3_ARRAY_SORT:
        return ArraySortRef(s, ctx)
    elif k == Z3_DATATYPE_SORT:
        return DatatypeSortRef(s, ctx)
    elif k == Z3_FINITE_DOMAIN_SORT:
        return FiniteDomainSortRef(s, ctx)
    elif k == Z3_FLOATING_POINT_SORT:
        return FPSortRef(s, ctx)
    elif k == Z3_ROUNDING_MODE_SORT:
        return FPRMSortRef(s, ctx)
    elif k == Z3_RE_SORT:
        return ReSortRef(s, ctx)
    elif k == Z3_SEQ_SORT:
        return SeqSortRef(s, ctx)
    elif k == Z3_CHAR_SORT:
        return CharSortRef(s, ctx)
    return SortRef(s, ctx)
 
 
def _sort(ctx, a):
    return _to_sort_ref(Z3_get_sort(ctx.ref(), a), ctx)
 
 
def DeclareSort(name, ctx=None):
    """Create a new uninterpreted sort named `name`.
 
    If `ctx=None`, then the new sort is declared in the global Z3Py context.
 
    >>> A = DeclareSort('A')
    >>> a = Const('a', A)
    >>> b = Const('b', A)
    >>> a.sort() == A
    True
    >>> b.sort() == A
    True
    >>> a == b
    a == b
    """
    ctx = _get_ctx(ctx)
    return SortRef(Z3_mk_uninterpreted_sort(ctx.ref(), to_symbol(name, ctx)), ctx)
 
 
 
 
class FuncDeclRef(AstRef):
    """Function declaration. Every constant and function have an associated declaration.
 
    The declaration assigns a name, a sort (i.e., type), and for function
    the sort (i.e., type) of each of its arguments. Note that, in Z3,
    a constant is a function with 0 arguments.
    """
 
    def as_ast(self):
        return Z3_func_decl_to_ast(self.ctx_refctx_ref(), self.astast)
 
    def get_id(self):
        return Z3_get_ast_id(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
    def as_func_decl(self):
        return self.astast
 
    def name(self):
        """Return the name of the function declaration `self`.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> f.name()
        'f'
        >>> isinstance(f.name(), str)
        True
        """
        return _symbol2py(self.ctxctx, Z3_get_decl_name(self.ctx_refctx_ref(), self.astast))
 
    def arity(self):
        """Return the number of arguments of a function declaration.
        If `self` is a constant, then `self.arity()` is 0.
 
        >>> f = Function('f', IntSort(), RealSort(), BoolSort())
        >>> f.arity()
        2
        """
        return int(Z3_get_arity(self.ctx_refctx_ref(), self.astast))
 
    def domain(self, i):
        """Return the sort of the argument `i` of a function declaration.
        This method assumes that `0 <= i < self.arity()`.
 
        >>> f = Function('f', IntSort(), RealSort(), BoolSort())
        >>> f.domain(0)
        Int
        >>> f.domain(1)
        Real
        """
        if z3_debug():
            _z3_assert(i < self.arityarity(), "Index out of bounds")
        return _to_sort_ref(Z3_get_domain(self.ctx_refctx_ref(), self.astast, i), self.ctxctx)
 
    def range(self):
        """Return the sort of the range of a function declaration.
        For constants, this is the sort of the constant.
 
        >>> f = Function('f', IntSort(), RealSort(), BoolSort())
        >>> f.range()
        Bool
        """
        return _to_sort_ref(Z3_get_range(self.ctx_refctx_ref(), self.astast), self.ctxctx)
 
    def kind(self):
        """Return the internal kind of a function declaration.
        It can be used to identify Z3 built-in functions such as addition, multiplication, etc.
 
        >>> x = Int('x')
        >>> d = (x + 1).decl()
        >>> d.kind() == Z3_OP_ADD
        True
        >>> d.kind() == Z3_OP_MUL
        False
        """
        return Z3_get_decl_kind(self.ctx_refctx_ref(), self.astast)
 
    def params(self):
        ctx = self.ctxctx
        n = Z3_get_decl_num_parameters(self.ctx_refctx_ref(), self.astast)
        result = [None for i in range(n)]
        for i in range(n):
            k = Z3_get_decl_parameter_kind(self.ctx_refctx_ref(), self.astast, i)
            if k == Z3_PARAMETER_INT:
                result[i] = Z3_get_decl_int_parameter(self.ctx_refctx_ref(), self.astast, i)
            elif k == Z3_PARAMETER_DOUBLE:
                result[i] = Z3_get_decl_double_parameter(self.ctx_refctx_ref(), self.astast, i)
            elif k == Z3_PARAMETER_RATIONAL:
                result[i] = Z3_get_decl_rational_parameter(self.ctx_refctx_ref(), self.astast, i)
            elif k == Z3_PARAMETER_SYMBOL:
                result[i] = Z3_get_decl_symbol_parameter(self.ctx_refctx_ref(), self.astast, i)
            elif k == Z3_PARAMETER_SORT:
                result[i] = SortRef(Z3_get_decl_sort_parameter(self.ctx_refctx_ref(), self.astast, i), ctx)
            elif k == Z3_PARAMETER_AST:
                result[i] = ExprRef(Z3_get_decl_ast_parameter(self.ctx_refctx_ref(), self.astast, i), ctx)
            elif k == Z3_PARAMETER_FUNC_DECL:
                result[i] = FuncDeclRef(Z3_get_decl_func_decl_parameter(self.ctx_refctx_ref(), self.astast, i), ctx)
            else:
                assert(False)
        return result
 
    def __call__(self, *args):
        """Create a Z3 application expression using the function `self`, and the given arguments.
 
        The arguments must be Z3 expressions. This method assumes that
        the sorts of the elements in `args` match the sorts of the
        domain. Limited coercion is supported.  For example, if
        args[0] is a Python integer, and the function expects a Z3
        integer, then the argument is automatically converted into a
        Z3 integer.
 
        >>> f = Function('f', IntSort(), RealSort(), BoolSort())
        >>> x = Int('x')
        >>> y = Real('y')
        >>> f(x, y)
        f(x, y)
        >>> f(x, x)
        f(x, ToReal(x))
        """
        args = _get_args(args)
        num = len(args)
        if z3_debug():
            _z3_assert(num == self.arityarity(), "Incorrect number of arguments to %s" % self)
        _args = (Ast * num)()
        saved = []
        for i in range(num):
            # self.domain(i).cast(args[i]) may create a new Z3 expression,
            # then we must save in 'saved' to prevent it from being garbage collected.
            tmp = self.domaindomain(i).cast(args[i])
            saved.append(tmp)
            _args[i] = tmp.as_ast()
        return _to_expr_ref(Z3_mk_app(self.ctx_refctx_ref(), self.astast, len(args), _args), self.ctxctx)
 
 
def is_func_decl(a):
    """Return `True` if `a` is a Z3 function declaration.
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> is_func_decl(f)
    True
    >>> x = Real('x')
    >>> is_func_decl(x)
    False
    """
    return isinstance(a, FuncDeclRef)
 
 
def Function(name, *sig):
    """Create a new Z3 uninterpreted function with the given sorts.
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> f(f(0))
    f(f(0))
    """
    sig = _get_args(sig)
    if z3_debug():
        _z3_assert(len(sig) > 0, "At least two arguments expected")
    arity = len(sig) - 1
    rng = sig[arity]
    if z3_debug():
        _z3_assert(is_sort(rng), "Z3 sort expected")
    dom = (Sort * arity)()
    for i in range(arity):
        if z3_debug():
            _z3_assert(is_sort(sig[i]), "Z3 sort expected")
        dom[i] = sig[i].ast
    ctx = rng.ctx
    return FuncDeclRef(Z3_mk_func_decl(ctx.ref(), to_symbol(name, ctx), arity, dom, rng.ast), ctx)
 
 
def FreshFunction(*sig):
    """Create a new fresh Z3 uninterpreted function with the given sorts.
    """
    sig = _get_args(sig)
    if z3_debug():
        _z3_assert(len(sig) > 0, "At least two arguments expected")
    arity = len(sig) - 1
    rng = sig[arity]
    if z3_debug():
        _z3_assert(is_sort(rng), "Z3 sort expected")
    dom = (z3.Sort * arity)()
    for i in range(arity):
        if z3_debug():
            _z3_assert(is_sort(sig[i]), "Z3 sort expected")
        dom[i] = sig[i].ast
    ctx = rng.ctx
    return FuncDeclRef(Z3_mk_fresh_func_decl(ctx.ref(), "f", arity, dom, rng.ast), ctx)
 
 
def _to_func_decl_ref(a, ctx):
    return FuncDeclRef(a, ctx)
 
 
def RecFunction(name, *sig):
    """Create a new Z3 recursive with the given sorts."""
    sig = _get_args(sig)
    if z3_debug():
        _z3_assert(len(sig) > 0, "At least two arguments expected")
    arity = len(sig) - 1
    rng = sig[arity]
    if z3_debug():
        _z3_assert(is_sort(rng), "Z3 sort expected")
    dom = (Sort * arity)()
    for i in range(arity):
        if z3_debug():
            _z3_assert(is_sort(sig[i]), "Z3 sort expected")
        dom[i] = sig[i].ast
    ctx = rng.ctx
    return FuncDeclRef(Z3_mk_rec_func_decl(ctx.ref(), to_symbol(name, ctx), arity, dom, rng.ast), ctx)
 
 
def RecAddDefinition(f, args, body):
    """Set the body of a recursive function.
       Recursive definitions can be simplified if they are applied to ground
       arguments.
    >>> ctx = Context()
    >>> fac = RecFunction('fac', IntSort(ctx), IntSort(ctx))
    >>> n = Int('n', ctx)
    >>> RecAddDefinition(fac, n, If(n == 0, 1, n*fac(n-1)))
    >>> simplify(fac(5))
    120
    >>> s = Solver(ctx=ctx)
    >>> s.add(fac(n) < 3)
    >>> s.check()
    sat
    >>> s.model().eval(fac(5))
    120
    """
    if is_app(args):
        args = [args]
    ctx = body.ctx
    args = _get_args(args)
    n = len(args)
    _args = (Ast * n)()
    for i in range(n):
        _args[i] = args[i].ast
    Z3_add_rec_def(ctx.ref(), f.ast, n, _args, body.ast)
 
 
 
 
class ExprRef(AstRef):
    """Constraints, formulas and terms are expressions in Z3.
 
    Expressions are ASTs. Every expression has a sort.
    There are three main kinds of expressions:
    function applications, quantifiers and bounded variables.
    A constant is a function application with 0 arguments.
    For quantifier free problems, all expressions are
    function applications.
    """
 
    def as_ast(self):
        return self.astast
 
    def get_id(self):
        return Z3_get_ast_id(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
    def sort(self):
        """Return the sort of expression `self`.
 
        >>> x = Int('x')
        >>> (x + 1).sort()
        Int
        >>> y = Real('y')
        >>> (x + y).sort()
        Real
        """
        return _sort(self.ctxctx, self.as_astas_astas_ast())
 
    def sort_kind(self):
        """Shorthand for `self.sort().kind()`.
 
        >>> a = Array('a', IntSort(), IntSort())
        >>> a.sort_kind() == Z3_ARRAY_SORT
        True
        >>> a.sort_kind() == Z3_INT_SORT
        False
        """
        return self.sortsort().kind()
 
    def __eq__(self, other):
        """Return a Z3 expression that represents the constraint `self == other`.
 
        If `other` is `None`, then this method simply returns `False`.
 
        >>> a = Int('a')
        >>> b = Int('b')
        >>> a == b
        a == b
        >>> a is None
        False
        """
        if other is None:
            return False
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_eq(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __hash__(self):
        """ Hash code. """
        return AstRef.__hash__(self)
 
    def __ne__(self, other):
        """Return a Z3 expression that represents the constraint `self != other`.
 
        If `other` is `None`, then this method simply returns `True`.
 
        >>> a = Int('a')
        >>> b = Int('b')
        >>> a != b
        a != b
        >>> a is not None
        True
        """
        if other is None:
            return True
        a, b = _coerce_exprs(self, other)
        _args, sz = _to_ast_array((a, b))
        return BoolRef(Z3_mk_distinct(self.ctx_refctx_ref(), 2, _args), self.ctxctx)
 
    def params(self):
        return self.decldecl().params()
 
    def decl(self):
        """Return the Z3 function declaration associated with a Z3 application.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> a = Int('a')
        >>> t = f(a)
        >>> eq(t.decl(), f)
        True
        >>> (a + 1).decl()
        +
        """
        if z3_debug():
            _z3_assert(is_app(self), "Z3 application expected")
        return FuncDeclRef(Z3_get_app_decl(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def num_args(self):
        """Return the number of arguments of a Z3 application.
 
        >>> a = Int('a')
        >>> b = Int('b')
        >>> (a + b).num_args()
        2
        >>> f = Function('f', IntSort(), IntSort(), IntSort(), IntSort())
        >>> t = f(a, b, 0)
        >>> t.num_args()
        3
        """
        if z3_debug():
            _z3_assert(is_app(self), "Z3 application expected")
        return int(Z3_get_app_num_args(self.ctx_refctx_ref(), self.as_astas_astas_ast()))
 
    def arg(self, idx):
        """Return argument `idx` of the application `self`.
 
        This method assumes that `self` is a function application with at least `idx+1` arguments.
 
        >>> a = Int('a')
        >>> b = Int('b')
        >>> f = Function('f', IntSort(), IntSort(), IntSort(), IntSort())
        >>> t = f(a, b, 0)
        >>> t.arg(0)
        a
        >>> t.arg(1)
        b
        >>> t.arg(2)
        0
        """
        if z3_debug():
            _z3_assert(is_app(self), "Z3 application expected")
            _z3_assert(idx < self.num_argsnum_args(), "Invalid argument index")
        return _to_expr_ref(Z3_get_app_arg(self.ctx_refctx_ref(), self.as_astas_astas_ast(), idx), self.ctxctx)
 
    def children(self):
        """Return a list containing the children of the given expression
 
        >>> a = Int('a')
        >>> b = Int('b')
        >>> f = Function('f', IntSort(), IntSort(), IntSort(), IntSort())
        >>> t = f(a, b, 0)
        >>> t.children()
        [a, b, 0]
        """
        if is_app(self):
            return [self.argarg(i) for i in range(self.num_argsnum_args())]
        else:
            return []
 
    def from_string(self, s):
        pass
 
    def serialize(self):
        s = Solver()
        f = Function('F', self.sort(), BoolSort(self.ctx))
        s.add(f(self))
        return s.sexpr()
 
def deserialize(st):
    """inverse function to the serialize method on ExprRef.
    It is made available to make it easier for users to serialize expressions back and forth between
    strings. Solvers can be serialized using the 'sexpr()' method.
    """
    s = Solver()
    s.from_string(st)
    if len(s.assertions()) != 1:
        raise Z3Exception("single assertion expected")
    fml = s.assertions()[0]
    if fml.num_args() != 1:
        raise Z3Exception("dummy function 'F' expected")
    return fml.arg(0)
 
def _to_expr_ref(a, ctx):
    if isinstance(a, Pattern):
        return PatternRef(a, ctx)
    ctx_ref = ctx.ref()
    k = Z3_get_ast_kind(ctx_ref, a)
    if k == Z3_QUANTIFIER_AST:
        return QuantifierRef(a, ctx)
    sk = Z3_get_sort_kind(ctx_ref, Z3_get_sort(ctx_ref, a))
    if sk == Z3_BOOL_SORT:
        return BoolRef(a, ctx)
    if sk == Z3_INT_SORT:
        if k == Z3_NUMERAL_AST:
            return IntNumRef(a, ctx)
        return ArithRef(a, ctx)
    if sk == Z3_REAL_SORT:
        if k == Z3_NUMERAL_AST:
            return RatNumRef(a, ctx)
        if _is_algebraic(ctx, a):
            return AlgebraicNumRef(a, ctx)
        return ArithRef(a, ctx)
    if sk == Z3_BV_SORT:
        if k == Z3_NUMERAL_AST:
            return BitVecNumRef(a, ctx)
        else:
            return BitVecRef(a, ctx)
    if sk == Z3_ARRAY_SORT:
        return ArrayRef(a, ctx)
    if sk == Z3_DATATYPE_SORT:
        return DatatypeRef(a, ctx)
    if sk == Z3_FLOATING_POINT_SORT:
        if k == Z3_APP_AST and _is_numeral(ctx, a):
            return FPNumRef(a, ctx)
        else:
            return FPRef(a, ctx)
    if sk == Z3_FINITE_DOMAIN_SORT:
        if k == Z3_NUMERAL_AST:
            return FiniteDomainNumRef(a, ctx)
        else:
            return FiniteDomainRef(a, ctx)
    if sk == Z3_ROUNDING_MODE_SORT:
        return FPRMRef(a, ctx)
    if sk == Z3_SEQ_SORT:
        return SeqRef(a, ctx)
    if sk == Z3_CHAR_SORT:
        return CharRef(a, ctx)
    if sk == Z3_RE_SORT:
        return ReRef(a, ctx)
    return ExprRef(a, ctx)
 
 
def _coerce_expr_merge(s, a):
    if is_expr(a):
        s1 = a.sort()
        if s is None:
            return s1
        if s1.eq(s):
            return s
        elif s.subsort(s1):
            return s1
        elif s1.subsort(s):
            return s
        else:
            if z3_debug():
                _z3_assert(s1.ctx == s.ctx, "context mismatch")
                _z3_assert(False, "sort mismatch")        
    else:
        return s
 
 
def _coerce_exprs(a, b, ctx=None):
    if not is_expr(a) and not is_expr(b):
        a = _py2expr(a, ctx)
        b = _py2expr(b, ctx)
    if isinstance(a, str) and isinstance(b, SeqRef):
        a = StringVal(a, b.ctx)
    if isinstance(b, str) and isinstance(a, SeqRef):
        b = StringVal(b, a.ctx)
    if isinstance(a, float) and isinstance(b, ArithRef):
        a = RealVal(a, b.ctx)
    if isinstance(b, float) and isinstance(a, ArithRef):
        b = RealVal(b, a.ctx)
 
    s = None
    s = _coerce_expr_merge(s, a)
    s = _coerce_expr_merge(s, b)
    a = s.cast(a)
    b = s.cast(b)
    return (a, b)
 
 
def _reduce(func, sequence, initial):
    result = initial
    for element in sequence:
        result = func(result, element)
    return result
 
 
def _coerce_expr_list(alist, ctx=None):
    has_expr = False
    for a in alist:
        if is_expr(a):
            has_expr = True
            break
    if not has_expr:
        alist = [_py2expr(a, ctx) for a in alist]
    s = _reduce(_coerce_expr_merge, alist, None)
    return [s.cast(a) for a in alist]
 
 
def is_expr(a):
    """Return `True` if `a` is a Z3 expression.
 
    >>> a = Int('a')
    >>> is_expr(a)
    True
    >>> is_expr(a + 1)
    True
    >>> is_expr(IntSort())
    False
    >>> is_expr(1)
    False
    >>> is_expr(IntVal(1))
    True
    >>> x = Int('x')
    >>> is_expr(ForAll(x, x >= 0))
    True
    >>> is_expr(FPVal(1.0))
    True
    """
    return isinstance(a, ExprRef)
 
 
def is_app(a):
    """Return `True` if `a` is a Z3 function application.
 
    Note that, constants are function applications with 0 arguments.
 
    >>> a = Int('a')
    >>> is_app(a)
    True
    >>> is_app(a + 1)
    True
    >>> is_app(IntSort())
    False
    >>> is_app(1)
    False
    >>> is_app(IntVal(1))
    True
    >>> x = Int('x')
    >>> is_app(ForAll(x, x >= 0))
    False
    """
    if not isinstance(a, ExprRef):
        return False
    k = _ast_kind(a.ctx, a)
    return k == Z3_NUMERAL_AST or k == Z3_APP_AST
 
 
def is_const(a):
    """Return `True` if `a` is Z3 constant/variable expression.
 
    >>> a = Int('a')
    >>> is_const(a)
    True
    >>> is_const(a + 1)
    False
    >>> is_const(1)
    False
    >>> is_const(IntVal(1))
    True
    >>> x = Int('x')
    >>> is_const(ForAll(x, x >= 0))
    False
    """
    return is_app(a) and a.num_args() == 0
 
 
def is_var(a):
    """Return `True` if `a` is variable.
 
    Z3 uses de-Bruijn indices for representing bound variables in
    quantifiers.
 
    >>> x = Int('x')
    >>> is_var(x)
    False
    >>> is_const(x)
    True
    >>> f = Function('f', IntSort(), IntSort())
    >>> # Z3 replaces x with bound variables when ForAll is executed.
    >>> q = ForAll(x, f(x) == x)
    >>> b = q.body()
    >>> b
    f(Var(0)) == Var(0)
    >>> b.arg(1)
    Var(0)
    >>> is_var(b.arg(1))
    True
    """
    return is_expr(a) and _ast_kind(a.ctx, a) == Z3_VAR_AST
 
 
def get_var_index(a):
    """Return the de-Bruijn index of the Z3 bounded variable `a`.
 
    >>> x = Int('x')
    >>> y = Int('y')
    >>> is_var(x)
    False
    >>> is_const(x)
    True
    >>> f = Function('f', IntSort(), IntSort(), IntSort())
    >>> # Z3 replaces x and y with bound variables when ForAll is executed.
    >>> q = ForAll([x, y], f(x, y) == x + y)
    >>> q.body()
    f(Var(1), Var(0)) == Var(1) + Var(0)
    >>> b = q.body()
    >>> b.arg(0)
    f(Var(1), Var(0))
    >>> v1 = b.arg(0).arg(0)
    >>> v2 = b.arg(0).arg(1)
    >>> v1
    Var(1)
    >>> v2
    Var(0)
    >>> get_var_index(v1)
    1
    >>> get_var_index(v2)
    0
    """
    if z3_debug():
        _z3_assert(is_var(a), "Z3 bound variable expected")
    return int(Z3_get_index_value(a.ctx.ref(), a.as_ast()))
 
 
def is_app_of(a, k):
    """Return `True` if `a` is an application of the given kind `k`.
 
    >>> x = Int('x')
    >>> n = x + 1
    >>> is_app_of(n, Z3_OP_ADD)
    True
    >>> is_app_of(n, Z3_OP_MUL)
    False
    """
    return is_app(a) and a.decl().kind() == k
 
 
def If(a, b, c, ctx=None):
    """Create a Z3 if-then-else expression.
 
    >>> x = Int('x')
    >>> y = Int('y')
    >>> max = If(x > y, x, y)
    >>> max
    If(x > y, x, y)
    >>> simplify(max)
    If(x <= y, y, x)
    """
    if isinstance(a, Probe) or isinstance(b, Tactic) or isinstance(c, Tactic):
        return Cond(a, b, c, ctx)
    else:
        ctx = _get_ctx(_ctx_from_ast_arg_list([a, b, c], ctx))
        s = BoolSort(ctx)
        a = s.cast(a)
        b, c = _coerce_exprs(b, c, ctx)
        if z3_debug():
            _z3_assert(a.ctx == b.ctx, "Context mismatch")
        return _to_expr_ref(Z3_mk_ite(ctx.ref(), a.as_ast(), b.as_ast(), c.as_ast()), ctx)
 
 
def Distinct(*args):
    """Create a Z3 distinct expression.
 
    >>> x = Int('x')
    >>> y = Int('y')
    >>> Distinct(x, y)
    x != y
    >>> z = Int('z')
    >>> Distinct(x, y, z)
    Distinct(x, y, z)
    >>> simplify(Distinct(x, y, z))
    Distinct(x, y, z)
    >>> simplify(Distinct(x, y, z), blast_distinct=True)
    And(Not(x == y), Not(x == z), Not(y == z))
    """
    args = _get_args(args)
    ctx = _ctx_from_ast_arg_list(args)
    if z3_debug():
        _z3_assert(ctx is not None, "At least one of the arguments must be a Z3 expression")
    args = _coerce_expr_list(args, ctx)
    _args, sz = _to_ast_array(args)
    return BoolRef(Z3_mk_distinct(ctx.ref(), sz, _args), ctx)
 
 
def _mk_bin(f, a, b):
    args = (Ast * 2)()
    if z3_debug():
        _z3_assert(a.ctx == b.ctx, "Context mismatch")
    args[0] = a.as_ast()
    args[1] = b.as_ast()
    return f(a.ctx.ref(), 2, args)
 
 
def Const(name, sort):
    """Create a constant of the given sort.
 
    >>> Const('x', IntSort())
    x
    """
    if z3_debug():
        _z3_assert(isinstance(sort, SortRef), "Z3 sort expected")
    ctx = sort.ctx
    return _to_expr_ref(Z3_mk_const(ctx.ref(), to_symbol(name, ctx), sort.ast), ctx)
 
 
def Consts(names, sort):
    """Create several constants of the given sort.
 
    `names` is a string containing the names of all constants to be created.
    Blank spaces separate the names of different constants.
 
    >>> x, y, z = Consts('x y z', IntSort())
    >>> x + y + z
    x + y + z
    """
    if isinstance(names, str):
        names = names.split(" ")
    return [Const(name, sort) for name in names]
 
 
def FreshConst(sort, prefix="c"):
    """Create a fresh constant of a specified sort"""
    ctx = _get_ctx(sort.ctx)
    return _to_expr_ref(Z3_mk_fresh_const(ctx.ref(), prefix, sort.ast), ctx)
 
 
def Var(idx, s):
    """Create a Z3 free variable. Free variables are used to create quantified formulas.
    A free variable with index n is bound when it occurs within the scope of n+1 quantified
    declarations.
    
    >>> Var(0, IntSort())
    Var(0)
    >>> eq(Var(0, IntSort()), Var(0, BoolSort()))
    False
    """
    if z3_debug():
        _z3_assert(is_sort(s), "Z3 sort expected")
    return _to_expr_ref(Z3_mk_bound(s.ctx_ref(), idx, s.ast), s.ctx)
 
 
def RealVar(idx, ctx=None):
    """
    Create a real free variable. Free variables are used to create quantified formulas.
    They are also used to create polynomials.
 
    >>> RealVar(0)
    Var(0)
    """
    return Var(idx, RealSort(ctx))
 
 
def RealVarVector(n, ctx=None):
    """
    Create a list of Real free variables.
    The variables have ids: 0, 1, ..., n-1
 
    >>> x0, x1, x2, x3 = RealVarVector(4)
    >>> x2
    Var(2)
    """
    return [RealVar(i, ctx) for i in range(n)]
 
 
 
 
class BoolSortRef(SortRef):
    """Boolean sort."""
 
    def cast(self, val):
        """Try to cast `val` as a Boolean.
 
        >>> x = BoolSort().cast(True)
        >>> x
        True
        >>> is_expr(x)
        True
        >>> is_expr(True)
        False
        >>> x.sort()
        Bool
        """
        if isinstance(val, bool):
            return BoolVal(val, self.ctxctx)
        if z3_debug():
            if not is_expr(val):
                msg = "True, False or Z3 Boolean expression expected. Received %s of type %s"
                _z3_assert(is_expr(val), msg % (val, type(val)))
            if not self.eqeq(val.sort()):
                _z3_assert(self.eqeq(val.sort()), "Value cannot be converted into a Z3 Boolean value")
        return val
 
    def subsort(self, other):
        return isinstance(other, ArithSortRef)
 
    def is_int(self):
        return True
 
    def is_bool(self):
        return True
 
 
class BoolRef(ExprRef):
    """All Boolean expressions are instances of this class."""
 
    def sort(self):
        return BoolSortRef(Z3_get_sort(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def __rmul__(self, other):
        return self * other
 
    def __mul__(self, other):
        """Create the Z3 expression `self * other`.
        """
        if isinstance(other, int) and other == 1:
            return If(self, 1, 0)
        if isinstance(other, int) and other == 0:
            return IntVal(0, self.ctxctx)
        if isinstance(other, BoolRef):
            other = If(other, 1, 0)
        return If(self, other, 0)
 
    
def is_bool(a):
    """Return `True` if `a` is a Z3 Boolean expression.
 
    >>> p = Bool('p')
    >>> is_bool(p)
    True
    >>> q = Bool('q')
    >>> is_bool(And(p, q))
    True
    >>> x = Real('x')
    >>> is_bool(x)
    False
    >>> is_bool(x == 0)
    True
    """
    return isinstance(a, BoolRef)
 
 
def is_true(a):
    """Return `True` if `a` is the Z3 true expression.
 
    >>> p = Bool('p')
    >>> is_true(p)
    False
    >>> is_true(simplify(p == p))
    True
    >>> x = Real('x')
    >>> is_true(x == 0)
    False
    >>> # True is a Python Boolean expression
    >>> is_true(True)
    False
    """
    return is_app_of(a, Z3_OP_TRUE)
 
 
def is_false(a):
    """Return `True` if `a` is the Z3 false expression.
 
    >>> p = Bool('p')
    >>> is_false(p)
    False
    >>> is_false(False)
    False
    >>> is_false(BoolVal(False))
    True
    """
    return is_app_of(a, Z3_OP_FALSE)
 
 
def is_and(a):
    """Return `True` if `a` is a Z3 and expression.
 
    >>> p, q = Bools('p q')
    >>> is_and(And(p, q))
    True
    >>> is_and(Or(p, q))
    False
    """
    return is_app_of(a, Z3_OP_AND)
 
 
def is_or(a):
    """Return `True` if `a` is a Z3 or expression.
 
    >>> p, q = Bools('p q')
    >>> is_or(Or(p, q))
    True
    >>> is_or(And(p, q))
    False
    """
    return is_app_of(a, Z3_OP_OR)
 
 
def is_implies(a):
    """Return `True` if `a` is a Z3 implication expression.
 
    >>> p, q = Bools('p q')
    >>> is_implies(Implies(p, q))
    True
    >>> is_implies(And(p, q))
    False
    """
    return is_app_of(a, Z3_OP_IMPLIES)
 
 
def is_not(a):
    """Return `True` if `a` is a Z3 not expression.
 
    >>> p = Bool('p')
    >>> is_not(p)
    False
    >>> is_not(Not(p))
    True
    """
    return is_app_of(a, Z3_OP_NOT)
 
 
def is_eq(a):
    """Return `True` if `a` is a Z3 equality expression.
 
    >>> x, y = Ints('x y')
    >>> is_eq(x == y)
    True
    """
    return is_app_of(a, Z3_OP_EQ)
 
 
def is_distinct(a):
    """Return `True` if `a` is a Z3 distinct expression.
 
    >>> x, y, z = Ints('x y z')
    >>> is_distinct(x == y)
    False
    >>> is_distinct(Distinct(x, y, z))
    True
    """
    return is_app_of(a, Z3_OP_DISTINCT)
 
 
def BoolSort(ctx=None):
    """Return the Boolean Z3 sort. If `ctx=None`, then the global context is used.
 
    >>> BoolSort()
    Bool
    >>> p = Const('p', BoolSort())
    >>> is_bool(p)
    True
    >>> r = Function('r', IntSort(), IntSort(), BoolSort())
    >>> r(0, 1)
    r(0, 1)
    >>> is_bool(r(0, 1))
    True
    """
    ctx = _get_ctx(ctx)
    return BoolSortRef(Z3_mk_bool_sort(ctx.ref()), ctx)
 
 
def BoolVal(val, ctx=None):
    """Return the Boolean value `True` or `False`. If `ctx=None`, then the global context is used.
 
    >>> BoolVal(True)
    True
    >>> is_true(BoolVal(True))
    True
    >>> is_true(True)
    False
    >>> is_false(BoolVal(False))
    True
    """
    ctx = _get_ctx(ctx)
    if val:
        return BoolRef(Z3_mk_true(ctx.ref()), ctx)
    else:
        return BoolRef(Z3_mk_false(ctx.ref()), ctx)
 
 
def Bool(name, ctx=None):
    """Return a Boolean constant named `name`. If `ctx=None`, then the global context is used.
 
    >>> p = Bool('p')
    >>> q = Bool('q')
    >>> And(p, q)
    And(p, q)
    """
    ctx = _get_ctx(ctx)
    return BoolRef(Z3_mk_const(ctx.ref(), to_symbol(name, ctx), BoolSort(ctx).ast), ctx)
 
 
def Bools(names, ctx=None):
    """Return a tuple of Boolean constants.
 
    `names` is a single string containing all names separated by blank spaces.
    If `ctx=None`, then the global context is used.
 
    >>> p, q, r = Bools('p q r')
    >>> And(p, Or(q, r))
    And(p, Or(q, r))
    """
    ctx = _get_ctx(ctx)
    if isinstance(names, str):
        names = names.split(" ")
    return [Bool(name, ctx) for name in names]
 
 
def BoolVector(prefix, sz, ctx=None):
    """Return a list of Boolean constants of size `sz`.
 
    The constants are named using the given prefix.
    If `ctx=None`, then the global context is used.
 
    >>> P = BoolVector('p', 3)
    >>> P
    [p__0, p__1, p__2]
    >>> And(P)
    And(p__0, p__1, p__2)
    """
    return [Bool("%s__%s" % (prefix, i)) for i in range(sz)]
 
 
def FreshBool(prefix="b", ctx=None):
    """Return a fresh Boolean constant in the given context using the given prefix.
 
    If `ctx=None`, then the global context is used.
 
    >>> b1 = FreshBool()
    >>> b2 = FreshBool()
    >>> eq(b1, b2)
    False
    """
    ctx = _get_ctx(ctx)
    return BoolRef(Z3_mk_fresh_const(ctx.ref(), prefix, BoolSort(ctx).ast), ctx)
 
 
def Implies(a, b, ctx=None):
    """Create a Z3 implies expression.
 
    >>> p, q = Bools('p q')
    >>> Implies(p, q)
    Implies(p, q)
    """
    ctx = _get_ctx(_ctx_from_ast_arg_list([a, b], ctx))
    s = BoolSort(ctx)
    a = s.cast(a)
    b = s.cast(b)
    return BoolRef(Z3_mk_implies(ctx.ref(), a.as_ast(), b.as_ast()), ctx)
 
 
def Xor(a, b, ctx=None):
    """Create a Z3 Xor expression.
 
    >>> p, q = Bools('p q')
    >>> Xor(p, q)
    Xor(p, q)
    >>> simplify(Xor(p, q))
    Not(p == q)
    """
    ctx = _get_ctx(_ctx_from_ast_arg_list([a, b], ctx))
    s = BoolSort(ctx)
    a = s.cast(a)
    b = s.cast(b)
    return BoolRef(Z3_mk_xor(ctx.ref(), a.as_ast(), b.as_ast()), ctx)
 
 
def Not(a, ctx=None):
    """Create a Z3 not expression or probe.
 
    >>> p = Bool('p')
    >>> Not(Not(p))
    Not(Not(p))
    >>> simplify(Not(Not(p)))
    p
    """
    ctx = _get_ctx(_ctx_from_ast_arg_list([a], ctx))
    if is_probe(a):
        # Not is also used to build probes
        return Probe(Z3_probe_not(ctx.ref(), a.probe), ctx)
    else:
        s = BoolSort(ctx)
        a = s.cast(a)
        return BoolRef(Z3_mk_not(ctx.ref(), a.as_ast()), ctx)
 
 
def mk_not(a):
    if is_not(a):
        return a.arg(0)
    else:
        return Not(a)
 
 
def _has_probe(args):
    """Return `True` if one of the elements of the given collection is a Z3 probe."""
    for arg in args:
        if is_probe(arg):
            return True
    return False
 
 
def And(*args):
    """Create a Z3 and-expression or and-probe.
 
    >>> p, q, r = Bools('p q r')
    >>> And(p, q, r)
    And(p, q, r)
    >>> P = BoolVector('p', 5)
    >>> And(P)
    And(p__0, p__1, p__2, p__3, p__4)
    """
    last_arg = None
    if len(args) > 0:
        last_arg = args[len(args) - 1]
    if isinstance(last_arg, Context):
        ctx = args[len(args) - 1]
        args = args[:len(args) - 1]
    elif len(args) == 1 and isinstance(args[0], AstVector):
        ctx = args[0].ctx
        args = [a for a in args[0]]
    else:
        ctx = None
    args = _get_args(args)
    ctx = _get_ctx(_ctx_from_ast_arg_list(args, ctx))
    if z3_debug():
        _z3_assert(ctx is not None, "At least one of the arguments must be a Z3 expression or probe")
    if _has_probe(args):
        return _probe_and(args, ctx)
    else:
        args = _coerce_expr_list(args, ctx)
        _args, sz = _to_ast_array(args)
        return BoolRef(Z3_mk_and(ctx.ref(), sz, _args), ctx)
 
 
def Or(*args):
    """Create a Z3 or-expression or or-probe.
 
    >>> p, q, r = Bools('p q r')
    >>> Or(p, q, r)
    Or(p, q, r)
    >>> P = BoolVector('p', 5)
    >>> Or(P)
    Or(p__0, p__1, p__2, p__3, p__4)
    """
    last_arg = None
    if len(args) > 0:
        last_arg = args[len(args) - 1]
    if isinstance(last_arg, Context):
        ctx = args[len(args) - 1]
        args = args[:len(args) - 1]
    elif len(args) == 1 and isinstance(args[0], AstVector):
        ctx = args[0].ctx
        args = [a for a in args[0]]
    else:
        ctx = None
    args = _get_args(args)
    ctx = _get_ctx(_ctx_from_ast_arg_list(args, ctx))
    if z3_debug():
        _z3_assert(ctx is not None, "At least one of the arguments must be a Z3 expression or probe")
    if _has_probe(args):
        return _probe_or(args, ctx)
    else:
        args = _coerce_expr_list(args, ctx)
        _args, sz = _to_ast_array(args)
        return BoolRef(Z3_mk_or(ctx.ref(), sz, _args), ctx)
 
 
 
 
class PatternRef(ExprRef):
    """Patterns are hints for quantifier instantiation.
 
    """
 
    def as_ast(self):
        return Z3_pattern_to_ast(self.ctx_refctx_ref(), self.astast)
 
    def get_id(self):
        return Z3_get_ast_id(self.ctx_refctx_ref(), self.as_astas_astas_astas_ast())
 
 
def is_pattern(a):
    """Return `True` if `a` is a Z3 pattern (hint for quantifier instantiation.
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> x = Int('x')
    >>> q = ForAll(x, f(x) == 0, patterns = [ f(x) ])
    >>> q
    ForAll(x, f(x) == 0)
    >>> q.num_patterns()
    1
    >>> is_pattern(q.pattern(0))
    True
    >>> q.pattern(0)
    f(Var(0))
    """
    return isinstance(a, PatternRef)
 
 
def MultiPattern(*args):
    """Create a Z3 multi-pattern using the given expressions `*args`
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> g = Function('g', IntSort(), IntSort())
    >>> x = Int('x')
    >>> q = ForAll(x, f(x) != g(x), patterns = [ MultiPattern(f(x), g(x)) ])
    >>> q
    ForAll(x, f(x) != g(x))
    >>> q.num_patterns()
    1
    >>> is_pattern(q.pattern(0))
    True
    >>> q.pattern(0)
    MultiPattern(f(Var(0)), g(Var(0)))
    """
    if z3_debug():
        _z3_assert(len(args) > 0, "At least one argument expected")
        _z3_assert(all([is_expr(a) for a in args]), "Z3 expressions expected")
    ctx = args[0].ctx
    args, sz = _to_ast_array(args)
    return PatternRef(Z3_mk_pattern(ctx.ref(), sz, args), ctx)
 
 
def _to_pattern(arg):
    if is_pattern(arg):
        return arg
    else:
        return MultiPattern(arg)
 
 
 
 
class QuantifierRef(BoolRef):
    """Universally and Existentially quantified formulas."""
 
    def as_ast(self):
        return self.astast
 
    def get_id(self):
        return Z3_get_ast_id(self.ctx_refctx_ref(), self.as_astas_astas_astas_ast())
 
    def sort(self):
        """Return the Boolean sort or sort of Lambda."""
        if self.is_lambdais_lambda():
            return _sort(self.ctxctx, self.as_astas_astas_astas_ast())
        return BoolSort(self.ctxctx)
 
    def is_forall(self):
        """Return `True` if `self` is a universal quantifier.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) == 0)
        >>> q.is_forall()
        True
        >>> q = Exists(x, f(x) != 0)
        >>> q.is_forall()
        False
        """
        return Z3_is_quantifier_forall(self.ctx_refctx_ref(), self.astast)
 
    def is_exists(self):
        """Return `True` if `self` is an existential quantifier.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) == 0)
        >>> q.is_exists()
        False
        >>> q = Exists(x, f(x) != 0)
        >>> q.is_exists()
        True
        """
        return Z3_is_quantifier_exists(self.ctx_refctx_ref(), self.astast)
 
    def is_lambda(self):
        """Return `True` if `self` is a lambda expression.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = Lambda(x, f(x))
        >>> q.is_lambda()
        True
        >>> q = Exists(x, f(x) != 0)
        >>> q.is_lambda()
        False
        """
        return Z3_is_lambda(self.ctx_refctx_ref(), self.astast)
 
    def __getitem__(self, arg):
        """Return the Z3 expression `self[arg]`.
        """
        if z3_debug():
            _z3_assert(self.is_lambdais_lambda(), "quantifier should be a lambda expression")
        return _array_select(self, arg)
 
    def weight(self):
        """Return the weight annotation of `self`.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) == 0)
        >>> q.weight()
        1
        >>> q = ForAll(x, f(x) == 0, weight=10)
        >>> q.weight()
        10
        """
        return int(Z3_get_quantifier_weight(self.ctx_refctx_ref(), self.astast))
 
    def num_patterns(self):
        """Return the number of patterns (i.e., quantifier instantiation hints) in `self`.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> g = Function('g', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) != g(x), patterns = [ f(x), g(x) ])
        >>> q.num_patterns()
        2
        """
        return int(Z3_get_quantifier_num_patterns(self.ctx_refctx_ref(), self.astast))
 
    def pattern(self, idx):
        """Return a pattern (i.e., quantifier instantiation hints) in `self`.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> g = Function('g', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) != g(x), patterns = [ f(x), g(x) ])
        >>> q.num_patterns()
        2
        >>> q.pattern(0)
        f(Var(0))
        >>> q.pattern(1)
        g(Var(0))
        """
        if z3_debug():
            _z3_assert(idx < self.num_patternsnum_patterns(), "Invalid pattern idx")
        return PatternRef(Z3_get_quantifier_pattern_ast(self.ctx_refctx_ref(), self.astast, idx), self.ctxctx)
 
    def num_no_patterns(self):
        """Return the number of no-patterns."""
        return Z3_get_quantifier_num_no_patterns(self.ctx_refctx_ref(), self.astast)
 
    def no_pattern(self, idx):
        """Return a no-pattern."""
        if z3_debug():
            _z3_assert(idx < self.num_no_patternsnum_no_patterns(), "Invalid no-pattern idx")
        return _to_expr_ref(Z3_get_quantifier_no_pattern_ast(self.ctx_refctx_ref(), self.astast, idx), self.ctxctx)
 
    def body(self):
        """Return the expression being quantified.
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) == 0)
        >>> q.body()
        f(Var(0)) == 0
        """
        return _to_expr_ref(Z3_get_quantifier_body(self.ctx_refctx_ref(), self.astast), self.ctxctx)
 
    def num_vars(self):
        """Return the number of variables bounded by this quantifier.
 
        >>> f = Function('f', IntSort(), IntSort(), IntSort())
        >>> x = Int('x')
        >>> y = Int('y')
        >>> q = ForAll([x, y], f(x, y) >= x)
        >>> q.num_vars()
        2
        """
        return int(Z3_get_quantifier_num_bound(self.ctx_refctx_ref(), self.astast))
 
    def var_name(self, idx):
        """Return a string representing a name used when displaying the quantifier.
 
        >>> f = Function('f', IntSort(), IntSort(), IntSort())
        >>> x = Int('x')
        >>> y = Int('y')
        >>> q = ForAll([x, y], f(x, y) >= x)
        >>> q.var_name(0)
        'x'
        >>> q.var_name(1)
        'y'
        """
        if z3_debug():
            _z3_assert(idx < self.num_varsnum_vars(), "Invalid variable idx")
        return _symbol2py(self.ctxctx, Z3_get_quantifier_bound_name(self.ctx_refctx_ref(), self.astast, idx))
 
    def var_sort(self, idx):
        """Return the sort of a bound variable.
 
        >>> f = Function('f', IntSort(), RealSort(), IntSort())
        >>> x = Int('x')
        >>> y = Real('y')
        >>> q = ForAll([x, y], f(x, y) >= x)
        >>> q.var_sort(0)
        Int
        >>> q.var_sort(1)
        Real
        """
        if z3_debug():
            _z3_assert(idx < self.num_varsnum_vars(), "Invalid variable idx")
        return _to_sort_ref(Z3_get_quantifier_bound_sort(self.ctx_refctx_ref(), self.astast, idx), self.ctxctx)
 
    def children(self):
        """Return a list containing a single element self.body()
 
        >>> f = Function('f', IntSort(), IntSort())
        >>> x = Int('x')
        >>> q = ForAll(x, f(x) == 0)
        >>> q.children()
        [f(Var(0)) == 0]
        """
        return [self.bodybody()]
 
 
def is_quantifier(a):
    """Return `True` if `a` is a Z3 quantifier.
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> x = Int('x')
    >>> q = ForAll(x, f(x) == 0)
    >>> is_quantifier(q)
    True
    >>> is_quantifier(f(x))
    False
    """
    return isinstance(a, QuantifierRef)
 
 
def _mk_quantifier(is_forall, vs, body, weight=1, qid="", skid="", patterns=[], no_patterns=[]):
    if z3_debug():
        _z3_assert(is_bool(body) or is_app(vs) or (len(vs) > 0 and is_app(vs[0])), "Z3 expression expected")
        _z3_assert(is_const(vs) or (len(vs) > 0 and all([is_const(v) for v in vs])), "Invalid bounded variable(s)")
        _z3_assert(all([is_pattern(a) or is_expr(a) for a in patterns]), "Z3 patterns expected")
        _z3_assert(all([is_expr(p) for p in no_patterns]), "no patterns are Z3 expressions")
    if is_app(vs):
        ctx = vs.ctx
        vs = [vs]
    else:
        ctx = vs[0].ctx
    if not is_expr(body):
        body = BoolVal(body, ctx)
    num_vars = len(vs)
    if num_vars == 0:
        return body
    _vs = (Ast * num_vars)()
    for i in range(num_vars):
        # TODO: Check if is constant
        _vs[i] = vs[i].as_ast()
    patterns = [_to_pattern(p) for p in patterns]
    num_pats = len(patterns)
    _pats = (Pattern * num_pats)()
    for i in range(num_pats):
        _pats[i] = patterns[i].ast
    _no_pats, num_no_pats = _to_ast_array(no_patterns)
    qid = to_symbol(qid, ctx)
    skid = to_symbol(skid, ctx)
    return QuantifierRef(Z3_mk_quantifier_const_ex(ctx.ref(), is_forall, weight, qid, skid,
                                                   num_vars, _vs,
                                                   num_pats, _pats,
                                                   num_no_pats, _no_pats,
                                                   body.as_ast()), ctx)
 
 
def ForAll(vs, body, weight=1, qid="", skid="", patterns=[], no_patterns=[]):
    """Create a Z3 forall formula.
 
    The parameters `weight`, `qid`, `skid`, `patterns` and `no_patterns` are optional annotations.
 
    >>> f = Function('f', IntSort(), IntSort(), IntSort())
    >>> x = Int('x')
    >>> y = Int('y')
    >>> ForAll([x, y], f(x, y) >= x)
    ForAll([x, y], f(x, y) >= x)
    >>> ForAll([x, y], f(x, y) >= x, patterns=[ f(x, y) ])
    ForAll([x, y], f(x, y) >= x)
    >>> ForAll([x, y], f(x, y) >= x, weight=10)
    ForAll([x, y], f(x, y) >= x)
    """
    return _mk_quantifier(True, vs, body, weight, qid, skid, patterns, no_patterns)
 
 
def Exists(vs, body, weight=1, qid="", skid="", patterns=[], no_patterns=[]):
    """Create a Z3 exists formula.
 
    The parameters `weight`, `qif`, `skid`, `patterns` and `no_patterns` are optional annotations.
 
 
    >>> f = Function('f', IntSort(), IntSort(), IntSort())
    >>> x = Int('x')
    >>> y = Int('y')
    >>> q = Exists([x, y], f(x, y) >= x, skid="foo")
    >>> q
    Exists([x, y], f(x, y) >= x)
    >>> is_quantifier(q)
    True
    >>> r = Tactic('nnf')(q).as_expr()
    >>> is_quantifier(r)
    False
    """
    return _mk_quantifier(False, vs, body, weight, qid, skid, patterns, no_patterns)
 
 
def Lambda(vs, body):
    """Create a Z3 lambda expression.
 
    >>> f = Function('f', IntSort(), IntSort(), IntSort())
    >>> mem0 = Array('mem0', IntSort(), IntSort())
    >>> lo, hi, e, i = Ints('lo hi e i')
    >>> mem1 = Lambda([i], If(And(lo <= i, i <= hi), e, mem0[i]))
    >>> mem1
    Lambda(i, If(And(lo <= i, i <= hi), e, mem0[i]))
    """
    ctx = body.ctx
    if is_app(vs):
        vs = [vs]
    num_vars = len(vs)
    _vs = (Ast * num_vars)()
    for i in range(num_vars):
        # TODO: Check if is constant
        _vs[i] = vs[i].as_ast()
    return QuantifierRef(Z3_mk_lambda_const(ctx.ref(), num_vars, _vs, body.as_ast()), ctx)
 
 
 
 
class ArithSortRef(SortRef):
    """Real and Integer sorts."""
 
    def is_real(self):
        """Return `True` if `self` is of the sort Real.
 
        >>> x = Real('x')
        >>> x.is_real()
        True
        >>> (x + 1).is_real()
        True
        >>> x = Int('x')
        >>> x.is_real()
        False
        """
        return self.kindkind() == Z3_REAL_SORT
 
    def is_int(self):
        """Return `True` if `self` is of the sort Integer.
 
        >>> x = Int('x')
        >>> x.is_int()
        True
        >>> (x + 1).is_int()
        True
        >>> x = Real('x')
        >>> x.is_int()
        False
        """
        return self.kindkind() == Z3_INT_SORT
 
    def is_bool(self):
        return False
 
    def subsort(self, other):
        """Return `True` if `self` is a subsort of `other`."""
        return self.is_intis_int() and is_arith_sort(other) and other.is_real()
 
    def cast(self, val):
        """Try to cast `val` as an Integer or Real.
 
        >>> IntSort().cast(10)
        10
        >>> is_int(IntSort().cast(10))
        True
        >>> is_int(10)
        False
        >>> RealSort().cast(10)
        10
        >>> is_real(RealSort().cast(10))
        True
        """
        if is_expr(val):
            if z3_debug():
                _z3_assert(self.ctxctxctx == val.ctx, "Context mismatch")
            val_s = val.sort()
            if self.eqeq(val_s):
                return val
            if val_s.is_int() and self.is_realis_real():
                return ToReal(val)
            if val_s.is_bool() and self.is_intis_int():
                return If(val, 1, 0)
            if val_s.is_bool() and self.is_realis_real():
                return ToReal(If(val, 1, 0))
            if z3_debug():
                _z3_assert(False, "Z3 Integer/Real expression expected")
        else:
            if self.is_intis_int():
                return IntVal(val, self.ctxctxctx)
            if self.is_realis_real():
                return RealVal(val, self.ctxctxctx)
            if z3_debug():
                msg = "int, long, float, string (numeral), or Z3 Integer/Real expression expected. Got %s"
                _z3_assert(False, msg % self)
 
 
def is_arith_sort(s):
    """Return `True` if s is an arithmetical sort (type).
 
    >>> is_arith_sort(IntSort())
    True
    >>> is_arith_sort(RealSort())
    True
    >>> is_arith_sort(BoolSort())
    False
    >>> n = Int('x') + 1
    >>> is_arith_sort(n.sort())
    True
    """
    return isinstance(s, ArithSortRef)
 
 
class ArithRef(ExprRef):
    """Integer and Real expressions."""
 
    def sort(self):
        """Return the sort (type) of the arithmetical expression `self`.
 
        >>> Int('x').sort()
        Int
        >>> (Real('x') + 1).sort()
        Real
        """
        return ArithSortRef(Z3_get_sort(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def is_int(self):
        """Return `True` if `self` is an integer expression.
 
        >>> x = Int('x')
        >>> x.is_int()
        True
        >>> (x + 1).is_int()
        True
        >>> y = Real('y')
        >>> (x + y).is_int()
        False
        """
        return self.sortsortsort().is_int()
 
    def is_real(self):
        """Return `True` if `self` is an real expression.
 
        >>> x = Real('x')
        >>> x.is_real()
        True
        >>> (x + 1).is_real()
        True
        """
        return self.sortsortsort().is_real()
 
    def __add__(self, other):
        """Create the Z3 expression `self + other`.
 
        >>> x = Int('x')
        >>> y = Int('y')
        >>> x + y
        x + y
        >>> (x + y).sort()
        Int
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(_mk_bin(Z3_mk_add, a, b), self.ctxctx)
 
    def __radd__(self, other):
        """Create the Z3 expression `other + self`.
 
        >>> x = Int('x')
        >>> 10 + x
        10 + x
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(_mk_bin(Z3_mk_add, b, a), self.ctxctx)
 
    def __mul__(self, other):
        """Create the Z3 expression `self * other`.
 
        >>> x = Real('x')
        >>> y = Real('y')
        >>> x * y
        x*y
        >>> (x * y).sort()
        Real
        """
        if isinstance(other, BoolRef):
            return If(other, self, 0)
        a, b = _coerce_exprs(self, other)
        return ArithRef(_mk_bin(Z3_mk_mul, a, b), self.ctxctx)
 
    def __rmul__(self, other):
        """Create the Z3 expression `other * self`.
 
        >>> x = Real('x')
        >>> 10 * x
        10*x
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(_mk_bin(Z3_mk_mul, b, a), self.ctxctx)
 
    def __sub__(self, other):
        """Create the Z3 expression `self - other`.
 
        >>> x = Int('x')
        >>> y = Int('y')
        >>> x - y
        x - y
        >>> (x - y).sort()
        Int
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(_mk_bin(Z3_mk_sub, a, b), self.ctxctx)
 
    def __rsub__(self, other):
        """Create the Z3 expression `other - self`.
 
        >>> x = Int('x')
        >>> 10 - x
        10 - x
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(_mk_bin(Z3_mk_sub, b, a), self.ctxctx)
 
    def __pow__(self, other):
        """Create the Z3 expression `self**other` (** is the power operator).
 
        >>> x = Real('x')
        >>> x**3
        x**3
        >>> (x**3).sort()
        Real
        >>> simplify(IntVal(2)**8)
        256
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(Z3_mk_power(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rpow__(self, other):
        """Create the Z3 expression `other**self` (** is the power operator).
 
        >>> x = Real('x')
        >>> 2**x
        2**x
        >>> (2**x).sort()
        Real
        >>> simplify(2**IntVal(8))
        256
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(Z3_mk_power(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __div__(self, other):
        """Create the Z3 expression `other/self`.
 
        >>> x = Int('x')
        >>> y = Int('y')
        >>> x/y
        x/y
        >>> (x/y).sort()
        Int
        >>> (x/y).sexpr()
        '(div x y)'
        >>> x = Real('x')
        >>> y = Real('y')
        >>> x/y
        x/y
        >>> (x/y).sort()
        Real
        >>> (x/y).sexpr()
        '(/ x y)'
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(Z3_mk_div(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __truediv__(self, other):
        """Create the Z3 expression `other/self`."""
        return self.__div____div__(other)
 
    def __rdiv__(self, other):
        """Create the Z3 expression `other/self`.
 
        >>> x = Int('x')
        >>> 10/x
        10/x
        >>> (10/x).sexpr()
        '(div 10 x)'
        >>> x = Real('x')
        >>> 10/x
        10/x
        >>> (10/x).sexpr()
        '(/ 10.0 x)'
        """
        a, b = _coerce_exprs(self, other)
        return ArithRef(Z3_mk_div(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __rtruediv__(self, other):
        """Create the Z3 expression `other/self`."""
        return self.__rdiv____rdiv__(other)
 
    def __mod__(self, other):
        """Create the Z3 expression `other%self`.
 
        >>> x = Int('x')
        >>> y = Int('y')
        >>> x % y
        x%y
        >>> simplify(IntVal(10) % IntVal(3))
        1
        """
        a, b = _coerce_exprs(self, other)
        if z3_debug():
            _z3_assert(a.is_int(), "Z3 integer expression expected")
        return ArithRef(Z3_mk_mod(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rmod__(self, other):
        """Create the Z3 expression `other%self`.
 
        >>> x = Int('x')
        >>> 10 % x
        10%x
        """
        a, b = _coerce_exprs(self, other)
        if z3_debug():
            _z3_assert(a.is_int(), "Z3 integer expression expected")
        return ArithRef(Z3_mk_mod(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __neg__(self):
        """Return an expression representing `-self`.
 
        >>> x = Int('x')
        >>> -x
        -x
        >>> simplify(-(-x))
        x
        """
        return ArithRef(Z3_mk_unary_minus(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def __pos__(self):
        """Return `self`.
 
        >>> x = Int('x')
        >>> +x
        x
        """
        return self
 
    def __le__(self, other):
        """Create the Z3 expression `other <= self`.
 
        >>> x, y = Ints('x y')
        >>> x <= y
        x <= y
        >>> y = Real('y')
        >>> x <= y
        ToReal(x) <= y
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_le(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __lt__(self, other):
        """Create the Z3 expression `other < self`.
 
        >>> x, y = Ints('x y')
        >>> x < y
        x < y
        >>> y = Real('y')
        >>> x < y
        ToReal(x) < y
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_lt(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __gt__(self, other):
        """Create the Z3 expression `other > self`.
 
        >>> x, y = Ints('x y')
        >>> x > y
        x > y
        >>> y = Real('y')
        >>> x > y
        ToReal(x) > y
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_gt(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __ge__(self, other):
        """Create the Z3 expression `other >= self`.
 
        >>> x, y = Ints('x y')
        >>> x >= y
        x >= y
        >>> y = Real('y')
        >>> x >= y
        ToReal(x) >= y
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_ge(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
 
def is_arith(a):
    """Return `True` if `a` is an arithmetical expression.
 
    >>> x = Int('x')
    >>> is_arith(x)
    True
    >>> is_arith(x + 1)
    True
    >>> is_arith(1)
    False
    >>> is_arith(IntVal(1))
    True
    >>> y = Real('y')
    >>> is_arith(y)
    True
    >>> is_arith(y + 1)
    True
    """
    return isinstance(a, ArithRef)
 
 
def is_int(a):
    """Return `True` if `a` is an integer expression.
 
    >>> x = Int('x')
    >>> is_int(x + 1)
    True
    >>> is_int(1)
    False
    >>> is_int(IntVal(1))
    True
    >>> y = Real('y')
    >>> is_int(y)
    False
    >>> is_int(y + 1)
    False
    """
    return is_arith(a) and a.is_int()
 
 
def is_real(a):
    """Return `True` if `a` is a real expression.
 
    >>> x = Int('x')
    >>> is_real(x + 1)
    False
    >>> y = Real('y')
    >>> is_real(y)
    True
    >>> is_real(y + 1)
    True
    >>> is_real(1)
    False
    >>> is_real(RealVal(1))
    True
    """
    return is_arith(a) and a.is_real()
 
 
def _is_numeral(ctx, a):
    return Z3_is_numeral_ast(ctx.ref(), a)
 
 
def _is_algebraic(ctx, a):
    return Z3_is_algebraic_number(ctx.ref(), a)
 
 
def is_int_value(a):
    """Return `True` if `a` is an integer value of sort Int.
 
    >>> is_int_value(IntVal(1))
    True
    >>> is_int_value(1)
    False
    >>> is_int_value(Int('x'))
    False
    >>> n = Int('x') + 1
    >>> n
    x + 1
    >>> n.arg(1)
    1
    >>> is_int_value(n.arg(1))
    True
    >>> is_int_value(RealVal("1/3"))
    False
    >>> is_int_value(RealVal(1))
    False
    """
    return is_arith(a) and a.is_int() and _is_numeral(a.ctx, a.as_ast())
 
 
def is_rational_value(a):
    """Return `True` if `a` is rational value of sort Real.
 
    >>> is_rational_value(RealVal(1))
    True
    >>> is_rational_value(RealVal("3/5"))
    True
    >>> is_rational_value(IntVal(1))
    False
    >>> is_rational_value(1)
    False
    >>> n = Real('x') + 1
    >>> n.arg(1)
    1
    >>> is_rational_value(n.arg(1))
    True
    >>> is_rational_value(Real('x'))
    False
    """
    return is_arith(a) and a.is_real() and _is_numeral(a.ctx, a.as_ast())
 
 
def is_algebraic_value(a):
    """Return `True` if `a` is an algebraic value of sort Real.
 
    >>> is_algebraic_value(RealVal("3/5"))
    False
    >>> n = simplify(Sqrt(2))
    >>> n
    1.4142135623?
    >>> is_algebraic_value(n)
    True
    """
    return is_arith(a) and a.is_real() and _is_algebraic(a.ctx, a.as_ast())
 
 
def is_add(a):
    """Return `True` if `a` is an expression of the form b + c.
 
    >>> x, y = Ints('x y')
    >>> is_add(x + y)
    True
    >>> is_add(x - y)
    False
    """
    return is_app_of(a, Z3_OP_ADD)
 
 
def is_mul(a):
    """Return `True` if `a` is an expression of the form b * c.
 
    >>> x, y = Ints('x y')
    >>> is_mul(x * y)
    True
    >>> is_mul(x - y)
    False
    """
    return is_app_of(a, Z3_OP_MUL)
 
 
def is_sub(a):
    """Return `True` if `a` is an expression of the form b - c.
 
    >>> x, y = Ints('x y')
    >>> is_sub(x - y)
    True
    >>> is_sub(x + y)
    False
    """
    return is_app_of(a, Z3_OP_SUB)
 
 
def is_div(a):
    """Return `True` if `a` is an expression of the form b / c.
 
    >>> x, y = Reals('x y')
    >>> is_div(x / y)
    True
    >>> is_div(x + y)
    False
    >>> x, y = Ints('x y')
    >>> is_div(x / y)
    False
    >>> is_idiv(x / y)
    True
    """
    return is_app_of(a, Z3_OP_DIV)
 
 
def is_idiv(a):
    """Return `True` if `a` is an expression of the form b div c.
 
    >>> x, y = Ints('x y')
    >>> is_idiv(x / y)
    True
    >>> is_idiv(x + y)
    False
    """
    return is_app_of(a, Z3_OP_IDIV)
 
 
def is_mod(a):
    """Return `True` if `a` is an expression of the form b % c.
 
    >>> x, y = Ints('x y')
    >>> is_mod(x % y)
    True
    >>> is_mod(x + y)
    False
    """
    return is_app_of(a, Z3_OP_MOD)
 
 
def is_le(a):
    """Return `True` if `a` is an expression of the form b <= c.
 
    >>> x, y = Ints('x y')
    >>> is_le(x <= y)
    True
    >>> is_le(x < y)
    False
    """
    return is_app_of(a, Z3_OP_LE)
 
 
def is_lt(a):
    """Return `True` if `a` is an expression of the form b < c.
 
    >>> x, y = Ints('x y')
    >>> is_lt(x < y)
    True
    >>> is_lt(x == y)
    False
    """
    return is_app_of(a, Z3_OP_LT)
 
 
def is_ge(a):
    """Return `True` if `a` is an expression of the form b >= c.
 
    >>> x, y = Ints('x y')
    >>> is_ge(x >= y)
    True
    >>> is_ge(x == y)
    False
    """
    return is_app_of(a, Z3_OP_GE)
 
 
def is_gt(a):
    """Return `True` if `a` is an expression of the form b > c.
 
    >>> x, y = Ints('x y')
    >>> is_gt(x > y)
    True
    >>> is_gt(x == y)
    False
    """
    return is_app_of(a, Z3_OP_GT)
 
 
def is_is_int(a):
    """Return `True` if `a` is an expression of the form IsInt(b).
 
    >>> x = Real('x')
    >>> is_is_int(IsInt(x))
    True
    >>> is_is_int(x)
    False
    """
    return is_app_of(a, Z3_OP_IS_INT)
 
 
def is_to_real(a):
    """Return `True` if `a` is an expression of the form ToReal(b).
 
    >>> x = Int('x')
    >>> n = ToReal(x)
    >>> n
    ToReal(x)
    >>> is_to_real(n)
    True
    >>> is_to_real(x)
    False
    """
    return is_app_of(a, Z3_OP_TO_REAL)
 
 
def is_to_int(a):
    """Return `True` if `a` is an expression of the form ToInt(b).
 
    >>> x = Real('x')
    >>> n = ToInt(x)
    >>> n
    ToInt(x)
    >>> is_to_int(n)
    True
    >>> is_to_int(x)
    False
    """
    return is_app_of(a, Z3_OP_TO_INT)
 
 
class IntNumRef(ArithRef):
    """Integer values."""
 
    def as_long(self):
        """Return a Z3 integer numeral as a Python long (bignum) numeral.
 
        >>> v = IntVal(1)
        >>> v + 1
        1 + 1
        >>> v.as_long() + 1
        2
        """
        if z3_debug():
            _z3_assert(self.is_intis_int(), "Integer value expected")
        return int(self.as_stringas_string())
 
    def as_string(self):
        """Return a Z3 integer numeral as a Python string.
        >>> v = IntVal(100)
        >>> v.as_string()
        '100'
        """
        return Z3_get_numeral_string(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
    def as_binary_string(self):
        """Return a Z3 integer numeral as a Python binary string.
        >>> v = IntVal(10)
        >>> v.as_binary_string()
        '1010'
        """
        return Z3_get_numeral_binary_string(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
 
class RatNumRef(ArithRef):
    """Rational values."""
 
    def numerator(self):
        """ Return the numerator of a Z3 rational numeral.
 
        >>> is_rational_value(RealVal("3/5"))
        True
        >>> n = RealVal("3/5")
        >>> n.numerator()
        3
        >>> is_rational_value(Q(3,5))
        True
        >>> Q(3,5).numerator()
        3
        """
        return IntNumRef(Z3_get_numerator(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def denominator(self):
        """ Return the denominator of a Z3 rational numeral.
 
        >>> is_rational_value(Q(3,5))
        True
        >>> n = Q(3,5)
        >>> n.denominator()
        5
        """
        return IntNumRef(Z3_get_denominator(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def numerator_as_long(self):
        """ Return the numerator as a Python long.
 
        >>> v = RealVal(10000000000)
        >>> v
        10000000000
        >>> v + 1
        10000000000 + 1
        >>> v.numerator_as_long() + 1 == 10000000001
        True
        """
        return self.numeratornumerator().as_long()
 
    def denominator_as_long(self):
        """ Return the denominator as a Python long.
 
        >>> v = RealVal("1/3")
        >>> v
        1/3
        >>> v.denominator_as_long()
        3
        """
        return self.denominatordenominator().as_long()
 
    def is_int(self):
        return False
 
    def is_real(self):
        return True
 
    def is_int_value(self):
        return self.denominatordenominator().is_int() and self.denominator_as_longdenominator_as_long() == 1
 
    def as_long(self):
        _z3_assert(self.is_int_valueis_int_value(), "Expected integer fraction")
        return self.numerator_as_longnumerator_as_long()
 
    def as_decimal(self, prec):
        """ Return a Z3 rational value as a string in decimal notation using at most `prec` decimal places.
 
        >>> v = RealVal("1/5")
        >>> v.as_decimal(3)
        '0.2'
        >>> v = RealVal("1/3")
        >>> v.as_decimal(3)
        '0.333?'
        """
        return Z3_get_numeral_decimal_string(self.ctx_refctx_ref(), self.as_astas_astas_ast(), prec)
 
    def as_string(self):
        """Return a Z3 rational numeral as a Python string.
 
        >>> v = Q(3,6)
        >>> v.as_string()
        '1/2'
        """
        return Z3_get_numeral_string(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
    def as_fraction(self):
        """Return a Z3 rational as a Python Fraction object.
 
        >>> v = RealVal("1/5")
        >>> v.as_fraction()
        Fraction(1, 5)
        """
        return Fraction(self.numerator_as_longnumerator_as_long(), self.denominator_as_longdenominator_as_long())
 
 
class AlgebraicNumRef(ArithRef):
    """Algebraic irrational values."""
 
    def approx(self, precision=10):
        """Return a Z3 rational number that approximates the algebraic number `self`.
        The result `r` is such that |r - self| <= 1/10^precision
 
        >>> x = simplify(Sqrt(2))
        >>> x.approx(20)
        6838717160008073720548335/4835703278458516698824704
        >>> x.approx(5)
        2965821/2097152
        """
        return RatNumRef(Z3_get_algebraic_number_upper(self.ctx_refctx_ref(), self.as_astas_astas_ast(), precision), self.ctxctx)
 
    def as_decimal(self, prec):
        """Return a string representation of the algebraic number `self` in decimal notation
        using `prec` decimal places.
 
        >>> x = simplify(Sqrt(2))
        >>> x.as_decimal(10)
        '1.4142135623?'
        >>> x.as_decimal(20)
        '1.41421356237309504880?'
        """
        return Z3_get_numeral_decimal_string(self.ctx_refctx_ref(), self.as_astas_astas_ast(), prec)
 
    def poly(self):
        return AstVector(Z3_algebraic_get_poly(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def index(self):
        return Z3_algebraic_get_i(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
 
def _py2expr(a, ctx=None):
    if isinstance(a, bool):
        return BoolVal(a, ctx)
    if _is_int(a):
        return IntVal(a, ctx)
    if isinstance(a, float):
        return RealVal(a, ctx)
    if isinstance(a, str):
        return StringVal(a, ctx)
    if is_expr(a):
        return a
    if z3_debug():
        _z3_assert(False, "Python bool, int, long or float expected")
 
 
def IntSort(ctx=None):
    """Return the integer sort in the given context. If `ctx=None`, then the global context is used.
 
    >>> IntSort()
    Int
    >>> x = Const('x', IntSort())
    >>> is_int(x)
    True
    >>> x.sort() == IntSort()
    True
    >>> x.sort() == BoolSort()
    False
    """
    ctx = _get_ctx(ctx)
    return ArithSortRef(Z3_mk_int_sort(ctx.ref()), ctx)
 
 
def RealSort(ctx=None):
    """Return the real sort in the given context. If `ctx=None`, then the global context is used.
 
    >>> RealSort()
    Real
    >>> x = Const('x', RealSort())
    >>> is_real(x)
    True
    >>> is_int(x)
    False
    >>> x.sort() == RealSort()
    True
    """
    ctx = _get_ctx(ctx)
    return ArithSortRef(Z3_mk_real_sort(ctx.ref()), ctx)
 
 
def _to_int_str(val):
    if isinstance(val, float):
        return str(int(val))
    elif isinstance(val, bool):
        if val:
            return "1"
        else:
            return "0"
    elif _is_int(val):
        return str(val)
    elif isinstance(val, str):
        return val
    if z3_debug():
        _z3_assert(False, "Python value cannot be used as a Z3 integer")
 
 
def IntVal(val, ctx=None):
    """Return a Z3 integer value. If `ctx=None`, then the global context is used.
 
    >>> IntVal(1)
    1
    >>> IntVal("100")
    100
    """
    ctx = _get_ctx(ctx)
    return IntNumRef(Z3_mk_numeral(ctx.ref(), _to_int_str(val), IntSort(ctx).ast), ctx)
 
 
def RealVal(val, ctx=None):
    """Return a Z3 real value.
 
    `val` may be a Python int, long, float or string representing a number in decimal or rational notation.
    If `ctx=None`, then the global context is used.
 
    >>> RealVal(1)
    1
    >>> RealVal(1).sort()
    Real
    >>> RealVal("3/5")
    3/5
    >>> RealVal("1.5")
    3/2
    """
    ctx = _get_ctx(ctx)
    return RatNumRef(Z3_mk_numeral(ctx.ref(), str(val), RealSort(ctx).ast), ctx)
 
 
def RatVal(a, b, ctx=None):
    """Return a Z3 rational a/b.
 
    If `ctx=None`, then the global context is used.
 
    >>> RatVal(3,5)
    3/5
    >>> RatVal(3,5).sort()
    Real
    """
    if z3_debug():
        _z3_assert(_is_int(a) or isinstance(a, str), "First argument cannot be converted into an integer")
        _z3_assert(_is_int(b) or isinstance(b, str), "Second argument cannot be converted into an integer")
    return simplify(RealVal(a, ctx) / RealVal(b, ctx))
 
 
def Q(a, b, ctx=None):
    """Return a Z3 rational a/b.
 
    If `ctx=None`, then the global context is used.
 
    >>> Q(3,5)
    3/5
    >>> Q(3,5).sort()
    Real
    """
    return simplify(RatVal(a, b, ctx=ctx))
 
 
def Int(name, ctx=None):
    """Return an integer constant named `name`. If `ctx=None`, then the global context is used.
 
    >>> x = Int('x')
    >>> is_int(x)
    True
    >>> is_int(x + 1)
    True
    """
    ctx = _get_ctx(ctx)
    return ArithRef(Z3_mk_const(ctx.ref(), to_symbol(name, ctx), IntSort(ctx).ast), ctx)
 
 
def Ints(names, ctx=None):
    """Return a tuple of Integer constants.
 
    >>> x, y, z = Ints('x y z')
    >>> Sum(x, y, z)
    x + y + z
    """
    ctx = _get_ctx(ctx)
    if isinstance(names, str):
        names = names.split(" ")
    return [Int(name, ctx) for name in names]
 
 
def IntVector(prefix, sz, ctx=None):
    """Return a list of integer constants of size `sz`.
 
    >>> X = IntVector('x', 3)
    >>> X
    [x__0, x__1, x__2]
    >>> Sum(X)
    x__0 + x__1 + x__2
    """
    ctx = _get_ctx(ctx)
    return [Int("%s__%s" % (prefix, i), ctx) for i in range(sz)]
 
 
def FreshInt(prefix="x", ctx=None):
    """Return a fresh integer constant in the given context using the given prefix.
 
    >>> x = FreshInt()
    >>> y = FreshInt()
    >>> eq(x, y)
    False
    >>> x.sort()
    Int
    """
    ctx = _get_ctx(ctx)
    return ArithRef(Z3_mk_fresh_const(ctx.ref(), prefix, IntSort(ctx).ast), ctx)
 
 
def Real(name, ctx=None):
    """Return a real constant named `name`. If `ctx=None`, then the global context is used.
 
    >>> x = Real('x')
    >>> is_real(x)
    True
    >>> is_real(x + 1)
    True
    """
    ctx = _get_ctx(ctx)
    return ArithRef(Z3_mk_const(ctx.ref(), to_symbol(name, ctx), RealSort(ctx).ast), ctx)
 
 
def Reals(names, ctx=None):
    """Return a tuple of real constants.
 
    >>> x, y, z = Reals('x y z')
    >>> Sum(x, y, z)
    x + y + z
    >>> Sum(x, y, z).sort()
    Real
    """
    ctx = _get_ctx(ctx)
    if isinstance(names, str):
        names = names.split(" ")
    return [Real(name, ctx) for name in names]
 
 
def RealVector(prefix, sz, ctx=None):
    """Return a list of real constants of size `sz`.
 
    >>> X = RealVector('x', 3)
    >>> X
    [x__0, x__1, x__2]
    >>> Sum(X)
    x__0 + x__1 + x__2
    >>> Sum(X).sort()
    Real
    """
    ctx = _get_ctx(ctx)
    return [Real("%s__%s" % (prefix, i), ctx) for i in range(sz)]
 
 
def FreshReal(prefix="b", ctx=None):
    """Return a fresh real constant in the given context using the given prefix.
 
    >>> x = FreshReal()
    >>> y = FreshReal()
    >>> eq(x, y)
    False
    >>> x.sort()
    Real
    """
    ctx = _get_ctx(ctx)
    return ArithRef(Z3_mk_fresh_const(ctx.ref(), prefix, RealSort(ctx).ast), ctx)
 
 
def ToReal(a):
    """ Return the Z3 expression ToReal(a).
 
    >>> x = Int('x')
    >>> x.sort()
    Int
    >>> n = ToReal(x)
    >>> n
    ToReal(x)
    >>> n.sort()
    Real
    """
    if z3_debug():
        _z3_assert(a.is_int(), "Z3 integer expression expected.")
    ctx = a.ctx
    return ArithRef(Z3_mk_int2real(ctx.ref(), a.as_ast()), ctx)
 
 
def ToInt(a):
    """ Return the Z3 expression ToInt(a).
 
    >>> x = Real('x')
    >>> x.sort()
    Real
    >>> n = ToInt(x)
    >>> n
    ToInt(x)
    >>> n.sort()
    Int
    """
    if z3_debug():
        _z3_assert(a.is_real(), "Z3 real expression expected.")
    ctx = a.ctx
    return ArithRef(Z3_mk_real2int(ctx.ref(), a.as_ast()), ctx)
 
 
def IsInt(a):
    """ Return the Z3 predicate IsInt(a).
 
    >>> x = Real('x')
    >>> IsInt(x + "1/2")
    IsInt(x + 1/2)
    >>> solve(IsInt(x + "1/2"), x > 0, x < 1)
    [x = 1/2]
    >>> solve(IsInt(x + "1/2"), x > 0, x < 1, x != "1/2")
    no solution
    """
    if z3_debug():
        _z3_assert(a.is_real(), "Z3 real expression expected.")
    ctx = a.ctx
    return BoolRef(Z3_mk_is_int(ctx.ref(), a.as_ast()), ctx)
 
 
def Sqrt(a, ctx=None):
    """ Return a Z3 expression which represents the square root of a.
 
    >>> x = Real('x')
    >>> Sqrt(x)
    x**(1/2)
    """
    if not is_expr(a):
        ctx = _get_ctx(ctx)
        a = RealVal(a, ctx)
    return a ** "1/2"
 
 
def Cbrt(a, ctx=None):
    """ Return a Z3 expression which represents the cubic root of a.
 
    >>> x = Real('x')
    >>> Cbrt(x)
    x**(1/3)
    """
    if not is_expr(a):
        ctx = _get_ctx(ctx)
        a = RealVal(a, ctx)
    return a ** "1/3"
 
 
 
 
class BitVecSortRef(SortRef):
    """Bit-vector sort."""
 
    def size(self):
        """Return the size (number of bits) of the bit-vector sort `self`.
 
        >>> b = BitVecSort(32)
        >>> b.size()
        32
        """
        return int(Z3_get_bv_sort_size(self.ctx_refctx_ref(), self.astast))
 
    def subsort(self, other):
        return is_bv_sort(other) and self.sizesize() < other.size()
 
    def cast(self, val):
        """Try to cast `val` as a Bit-Vector.
 
        >>> b = BitVecSort(32)
        >>> b.cast(10)
        10
        >>> b.cast(10).sexpr()
        '#x0000000a'
        """
        if is_expr(val):
            if z3_debug():
                _z3_assert(self.ctxctxctx == val.ctx, "Context mismatch")
            # Idea: use sign_extend if sort of val is a bitvector of smaller size
            return val
        else:
            return BitVecVal(val, self)
 
 
def is_bv_sort(s):
    """Return True if `s` is a Z3 bit-vector sort.
 
    >>> is_bv_sort(BitVecSort(32))
    True
    >>> is_bv_sort(IntSort())
    False
    """
    return isinstance(s, BitVecSortRef)
 
 
class BitVecRef(ExprRef):
    """Bit-vector expressions."""
 
    def sort(self):
        """Return the sort of the bit-vector expression `self`.
 
        >>> x = BitVec('x', 32)
        >>> x.sort()
        BitVec(32)
        >>> x.sort() == BitVecSort(32)
        True
        """
        return BitVecSortRef(Z3_get_sort(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def size(self):
        """Return the number of bits of the bit-vector expression `self`.
 
        >>> x = BitVec('x', 32)
        >>> (x + 1).size()
        32
        >>> Concat(x, x).size()
        64
        """
        return self.sortsortsort().size()
 
    def __add__(self, other):
        """Create the Z3 expression `self + other`.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x + y
        x + y
        >>> (x + y).sort()
        BitVec(32)
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvadd(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __radd__(self, other):
        """Create the Z3 expression `other + self`.
 
        >>> x = BitVec('x', 32)
        >>> 10 + x
        10 + x
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvadd(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __mul__(self, other):
        """Create the Z3 expression `self * other`.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x * y
        x*y
        >>> (x * y).sort()
        BitVec(32)
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvmul(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rmul__(self, other):
        """Create the Z3 expression `other * self`.
 
        >>> x = BitVec('x', 32)
        >>> 10 * x
        10*x
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvmul(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __sub__(self, other):
        """Create the Z3 expression `self - other`.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x - y
        x - y
        >>> (x - y).sort()
        BitVec(32)
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvsub(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rsub__(self, other):
        """Create the Z3 expression `other - self`.
 
        >>> x = BitVec('x', 32)
        >>> 10 - x
        10 - x
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvsub(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __or__(self, other):
        """Create the Z3 expression bitwise-or `self | other`.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x | y
        x | y
        >>> (x | y).sort()
        BitVec(32)
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvor(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __ror__(self, other):
        """Create the Z3 expression bitwise-or `other | self`.
 
        >>> x = BitVec('x', 32)
        >>> 10 | x
        10 | x
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvor(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __and__(self, other):
        """Create the Z3 expression bitwise-and `self & other`.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x & y
        x & y
        >>> (x & y).sort()
        BitVec(32)
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvand(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rand__(self, other):
        """Create the Z3 expression bitwise-or `other & self`.
 
        >>> x = BitVec('x', 32)
        >>> 10 & x
        10 & x
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvand(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __xor__(self, other):
        """Create the Z3 expression bitwise-xor `self ^ other`.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x ^ y
        x ^ y
        >>> (x ^ y).sort()
        BitVec(32)
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvxor(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rxor__(self, other):
        """Create the Z3 expression bitwise-xor `other ^ self`.
 
        >>> x = BitVec('x', 32)
        >>> 10 ^ x
        10 ^ x
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvxor(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __pos__(self):
        """Return `self`.
 
        >>> x = BitVec('x', 32)
        >>> +x
        x
        """
        return self
 
    def __neg__(self):
        """Return an expression representing `-self`.
 
        >>> x = BitVec('x', 32)
        >>> -x
        -x
        >>> simplify(-(-x))
        x
        """
        return BitVecRef(Z3_mk_bvneg(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def __invert__(self):
        """Create the Z3 expression bitwise-not `~self`.
 
        >>> x = BitVec('x', 32)
        >>> ~x
        ~x
        >>> simplify(~(~x))
        x
        """
        return BitVecRef(Z3_mk_bvnot(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def __div__(self, other):
        """Create the Z3 expression (signed) division `self / other`.
 
        Use the function UDiv() for unsigned division.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x / y
        x/y
        >>> (x / y).sort()
        BitVec(32)
        >>> (x / y).sexpr()
        '(bvsdiv x y)'
        >>> UDiv(x, y).sexpr()
        '(bvudiv x y)'
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvsdiv(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __truediv__(self, other):
        """Create the Z3 expression (signed) division `self / other`."""
        return self.__div____div__(other)
 
    def __rdiv__(self, other):
        """Create the Z3 expression (signed) division `other / self`.
 
        Use the function UDiv() for unsigned division.
 
        >>> x = BitVec('x', 32)
        >>> 10 / x
        10/x
        >>> (10 / x).sexpr()
        '(bvsdiv #x0000000a x)'
        >>> UDiv(10, x).sexpr()
        '(bvudiv #x0000000a x)'
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvsdiv(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __rtruediv__(self, other):
        """Create the Z3 expression (signed) division `other / self`."""
        return self.__rdiv____rdiv__(other)
 
    def __mod__(self, other):
        """Create the Z3 expression (signed) mod `self % other`.
 
        Use the function URem() for unsigned remainder, and SRem() for signed remainder.
 
        >>> x = BitVec('x', 32)
        >>> y = BitVec('y', 32)
        >>> x % y
        x%y
        >>> (x % y).sort()
        BitVec(32)
        >>> (x % y).sexpr()
        '(bvsmod x y)'
        >>> URem(x, y).sexpr()
        '(bvurem x y)'
        >>> SRem(x, y).sexpr()
        '(bvsrem x y)'
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvsmod(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rmod__(self, other):
        """Create the Z3 expression (signed) mod `other % self`.
 
        Use the function URem() for unsigned remainder, and SRem() for signed remainder.
 
        >>> x = BitVec('x', 32)
        >>> 10 % x
        10%x
        >>> (10 % x).sexpr()
        '(bvsmod #x0000000a x)'
        >>> URem(10, x).sexpr()
        '(bvurem #x0000000a x)'
        >>> SRem(10, x).sexpr()
        '(bvsrem #x0000000a x)'
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvsmod(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __le__(self, other):
        """Create the Z3 expression (signed) `other <= self`.
 
        Use the function ULE() for unsigned less than or equal to.
 
        >>> x, y = BitVecs('x y', 32)
        >>> x <= y
        x <= y
        >>> (x <= y).sexpr()
        '(bvsle x y)'
        >>> ULE(x, y).sexpr()
        '(bvule x y)'
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_bvsle(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __lt__(self, other):
        """Create the Z3 expression (signed) `other < self`.
 
        Use the function ULT() for unsigned less than.
 
        >>> x, y = BitVecs('x y', 32)
        >>> x < y
        x < y
        >>> (x < y).sexpr()
        '(bvslt x y)'
        >>> ULT(x, y).sexpr()
        '(bvult x y)'
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_bvslt(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __gt__(self, other):
        """Create the Z3 expression (signed) `other > self`.
 
        Use the function UGT() for unsigned greater than.
 
        >>> x, y = BitVecs('x y', 32)
        >>> x > y
        x > y
        >>> (x > y).sexpr()
        '(bvsgt x y)'
        >>> UGT(x, y).sexpr()
        '(bvugt x y)'
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_bvsgt(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __ge__(self, other):
        """Create the Z3 expression (signed) `other >= self`.
 
        Use the function UGE() for unsigned greater than or equal to.
 
        >>> x, y = BitVecs('x y', 32)
        >>> x >= y
        x >= y
        >>> (x >= y).sexpr()
        '(bvsge x y)'
        >>> UGE(x, y).sexpr()
        '(bvuge x y)'
        """
        a, b = _coerce_exprs(self, other)
        return BoolRef(Z3_mk_bvsge(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rshift__(self, other):
        """Create the Z3 expression (arithmetical) right shift `self >> other`
 
        Use the function LShR() for the right logical shift
 
        >>> x, y = BitVecs('x y', 32)
        >>> x >> y
        x >> y
        >>> (x >> y).sexpr()
        '(bvashr x y)'
        >>> LShR(x, y).sexpr()
        '(bvlshr x y)'
        >>> BitVecVal(4, 3)
        4
        >>> BitVecVal(4, 3).as_signed_long()
        -4
        >>> simplify(BitVecVal(4, 3) >> 1).as_signed_long()
        -2
        >>> simplify(BitVecVal(4, 3) >> 1)
        6
        >>> simplify(LShR(BitVecVal(4, 3), 1))
        2
        >>> simplify(BitVecVal(2, 3) >> 1)
        1
        >>> simplify(LShR(BitVecVal(2, 3), 1))
        1
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvashr(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __lshift__(self, other):
        """Create the Z3 expression left shift `self << other`
 
        >>> x, y = BitVecs('x y', 32)
        >>> x << y
        x << y
        >>> (x << y).sexpr()
        '(bvshl x y)'
        >>> simplify(BitVecVal(2, 3) << 1)
        4
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvshl(self.ctx_refctx_ref(), a.as_ast(), b.as_ast()), self.ctxctx)
 
    def __rrshift__(self, other):
        """Create the Z3 expression (arithmetical) right shift `other` >> `self`.
 
        Use the function LShR() for the right logical shift
 
        >>> x = BitVec('x', 32)
        >>> 10 >> x
        10 >> x
        >>> (10 >> x).sexpr()
        '(bvashr #x0000000a x)'
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvashr(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
    def __rlshift__(self, other):
        """Create the Z3 expression left shift `other << self`.
 
        Use the function LShR() for the right logical shift
 
        >>> x = BitVec('x', 32)
        >>> 10 << x
        10 << x
        >>> (10 << x).sexpr()
        '(bvshl #x0000000a x)'
        """
        a, b = _coerce_exprs(self, other)
        return BitVecRef(Z3_mk_bvshl(self.ctx_refctx_ref(), b.as_ast(), a.as_ast()), self.ctxctx)
 
 
class BitVecNumRef(BitVecRef):
    """Bit-vector values."""
 
    def as_long(self):
        """Return a Z3 bit-vector numeral as a Python long (bignum) numeral.
 
        >>> v = BitVecVal(0xbadc0de, 32)
        >>> v
        195936478
        >>> print("0x%.8x" % v.as_long())
        0x0badc0de
        """
        return int(self.as_stringas_string())
 
    def as_signed_long(self):
        """Return a Z3 bit-vector numeral as a Python long (bignum) numeral.
        The most significant bit is assumed to be the sign.
 
        >>> BitVecVal(4, 3).as_signed_long()
        -4
        >>> BitVecVal(7, 3).as_signed_long()
        -1
        >>> BitVecVal(3, 3).as_signed_long()
        3
        >>> BitVecVal(2**32 - 1, 32).as_signed_long()
        -1
        >>> BitVecVal(2**64 - 1, 64).as_signed_long()
        -1
        """
        sz = self.sizesize()
        val = self.as_longas_long()
        if val >= 2**(sz - 1):
            val = val - 2**sz
        if val < -2**(sz - 1):
            val = val + 2**sz
        return int(val)
 
    def as_string(self):
        return Z3_get_numeral_string(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
    def as_binary_string(self):
        return Z3_get_numeral_binary_string(self.ctx_refctx_ref(), self.as_astas_astas_ast())
 
 
def is_bv(a):
    """Return `True` if `a` is a Z3 bit-vector expression.
 
    >>> b = BitVec('b', 32)
    >>> is_bv(b)
    True
    >>> is_bv(b + 10)
    True
    >>> is_bv(Int('x'))
    False
    """
    return isinstance(a, BitVecRef)
 
 
def is_bv_value(a):
    """Return `True` if `a` is a Z3 bit-vector numeral value.
 
    >>> b = BitVec('b', 32)
    >>> is_bv_value(b)
    False
    >>> b = BitVecVal(10, 32)
    >>> b
    10
    >>> is_bv_value(b)
    True
    """
    return is_bv(a) and _is_numeral(a.ctx, a.as_ast())
 
 
def BV2Int(a, is_signed=False):
    """Return the Z3 expression BV2Int(a).
 
    >>> b = BitVec('b', 3)
    >>> BV2Int(b).sort()
    Int
    >>> x = Int('x')
    >>> x > BV2Int(b)
    x > BV2Int(b)
    >>> x > BV2Int(b, is_signed=False)
    x > BV2Int(b)
    >>> x > BV2Int(b, is_signed=True)
    x > If(b < 0, BV2Int(b) - 8, BV2Int(b))
    >>> solve(x > BV2Int(b), b == 1, x < 3)
    [x = 2, b = 1]
    """
    if z3_debug():
        _z3_assert(is_bv(a), "First argument must be a Z3 bit-vector expression")
    ctx = a.ctx
    # investigate problem with bv2int
    return ArithRef(Z3_mk_bv2int(ctx.ref(), a.as_ast(), is_signed), ctx)
 
 
def Int2BV(a, num_bits):
    """Return the z3 expression Int2BV(a, num_bits).
    It is a bit-vector of width num_bits and represents the
    modulo of a by 2^num_bits
    """
    ctx = a.ctx
    return BitVecRef(Z3_mk_int2bv(ctx.ref(), num_bits, a.as_ast()), ctx)
 
 
def BitVecSort(sz, ctx=None):
    """Return a Z3 bit-vector sort of the given size. If `ctx=None`, then the global context is used.
 
    >>> Byte = BitVecSort(8)
    >>> Word = BitVecSort(16)
    >>> Byte
    BitVec(8)
    >>> x = Const('x', Byte)
    >>> eq(x, BitVec('x', 8))
    True
    """
    ctx = _get_ctx(ctx)
    return BitVecSortRef(Z3_mk_bv_sort(ctx.ref(), sz), ctx)
 
 
def BitVecVal(val, bv, ctx=None):
    """Return a bit-vector value with the given number of bits. If `ctx=None`, then the global context is used.
 
    >>> v = BitVecVal(10, 32)
    >>> v
    10
    >>> print("0x%.8x" % v.as_long())
    0x0000000a
    """
    if is_bv_sort(bv):
        ctx = bv.ctx
        return BitVecNumRef(Z3_mk_numeral(ctx.ref(), _to_int_str(val), bv.ast), ctx)
    else:
        ctx = _get_ctx(ctx)
        return BitVecNumRef(Z3_mk_numeral(ctx.ref(), _to_int_str(val), BitVecSort(bv, ctx).ast), ctx)
 
 
def BitVec(name, bv, ctx=None):
    """Return a bit-vector constant named `name`. `bv` may be the number of bits of a bit-vector sort.
    If `ctx=None`, then the global context is used.
 
    >>> x  = BitVec('x', 16)
    >>> is_bv(x)
    True
    >>> x.size()
    16
    >>> x.sort()
    BitVec(16)
    >>> word = BitVecSort(16)
    >>> x2 = BitVec('x', word)
    >>> eq(x, x2)
    True
    """
    if isinstance(bv, BitVecSortRef):
        ctx = bv.ctx
    else:
        ctx = _get_ctx(ctx)
        bv = BitVecSort(bv, ctx)
    return BitVecRef(Z3_mk_const(ctx.ref(), to_symbol(name, ctx), bv.ast), ctx)
 
 
def BitVecs(names, bv, ctx=None):
    """Return a tuple of bit-vector constants of size bv.
 
    >>> x, y, z = BitVecs('x y z', 16)
    >>> x.size()
    16
    >>> x.sort()
    BitVec(16)
    >>> Sum(x, y, z)
    0 + x + y + z
    >>> Product(x, y, z)
    1*x*y*z
    >>> simplify(Product(x, y, z))
    x*y*z
    """
    ctx = _get_ctx(ctx)
    if isinstance(names, str):
        names = names.split(" ")
    return [BitVec(name, bv, ctx) for name in names]
 
 
def Concat(*args):
    """Create a Z3 bit-vector concatenation expression.
 
    >>> v = BitVecVal(1, 4)
    >>> Concat(v, v+1, v)
    Concat(Concat(1, 1 + 1), 1)
    >>> simplify(Concat(v, v+1, v))
    289
    >>> print("%.3x" % simplify(Concat(v, v+1, v)).as_long())
    121
    """
    args = _get_args(args)
    sz = len(args)
    if z3_debug():
        _z3_assert(sz >= 2, "At least two arguments expected.")
 
    ctx = None
    for a in args:
        if is_expr(a):
            ctx = a.ctx
            break
    if is_seq(args[0]) or isinstance(args[0], str):
        args = [_coerce_seq(s, ctx) for s in args]
        if z3_debug():
            _z3_assert(all([is_seq(a) for a in args]), "All arguments must be sequence expressions.")
        v = (Ast * sz)()
        for i in range(sz):
            v[i] = args[i].as_ast()
        return SeqRef(Z3_mk_seq_concat(ctx.ref(), sz, v), ctx)
 
    if is_re(args[0]):
        if z3_debug():
            _z3_assert(all([is_re(a) for a in args]), "All arguments must be regular expressions.")
        v = (Ast * sz)()
        for i in range(sz):
            v[i] = args[i].as_ast()
        return ReRef(Z3_mk_re_concat(ctx.ref(), sz, v), ctx)
 
    if z3_debug():
        _z3_assert(all([is_bv(a) for a in args]), "All arguments must be Z3 bit-vector expressions.")
    r = args[0]
    for i in range(sz - 1):
        r = BitVecRef(Z3_mk_concat(ctx.ref(), r.as_ast(), args[i + 1].as_ast()), ctx)
    return r
 
 
def Extract(high, low, a):
    """Create a Z3 bit-vector extraction expression.
    Extract is overloaded to also work on sequence extraction.
    The functions SubString and SubSeq are redirected to Extract.
    For this case, the arguments are reinterpreted as:
        high - is a sequence (string)
        low  - is an offset
        a    - is the length to be extracted
 
    >>> x = BitVec('x', 8)
    >>> Extract(6, 2, x)
    Extract(6, 2, x)
    >>> Extract(6, 2, x).sort()
    BitVec(5)
    >>> simplify(Extract(StringVal("abcd"),2,1))
    "c"
    """
    if isinstance(high, str):
        high = StringVal(high)
    if is_seq(high):
        s = high
        offset, length = _coerce_exprs(low, a, s.ctx)
        return SeqRef(Z3_mk_seq_extract(s.ctx_ref(), s.as_ast(), offset.as_ast(), length.as_ast()), s.ctx)
    if z3_debug():
        _z3_assert(low <= high, "First argument must be greater than or equal to second argument")
        _z3_assert(_is_int(high) and high >= 0 and _is_int(low) and low >= 0,
                   "First and second arguments must be non negative integers")
        _z3_assert(is_bv(a), "Third argument must be a Z3 bit-vector expression")
    return BitVecRef(Z3_mk_extract(a.ctx_ref(), high, low, a.as_ast()), a.ctx)
 
 
def _check_bv_args(a, b):
    if z3_debug():
        _z3_assert(is_bv(a) or is_bv(b), "First or second argument must be a Z3 bit-vector expression")
 
 
def ULE(a, b):
    """Create the Z3 expression (unsigned) `other <= self`.
 
    Use the operator <= for signed less than or equal to.
 
    >>> x, y = BitVecs('x y', 32)
    >>> ULE(x, y)
    ULE(x, y)
    >>> (x <= y).sexpr()
    '(bvsle x y)'
    >>> ULE(x, y).sexpr()
    '(bvule x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvule(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def ULT(a, b):
    """Create the Z3 expression (unsigned) `other < self`.
 
    Use the operator < for signed less than.
 
    >>> x, y = BitVecs('x y', 32)
    >>> ULT(x, y)
    ULT(x, y)
    >>> (x < y).sexpr()
    '(bvslt x y)'
    >>> ULT(x, y).sexpr()
    '(bvult x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvult(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def UGE(a, b):
    """Create the Z3 expression (unsigned) `other >= self`.
 
    Use the operator >= for signed greater than or equal to.
 
    >>> x, y = BitVecs('x y', 32)
    >>> UGE(x, y)
    UGE(x, y)
    >>> (x >= y).sexpr()
    '(bvsge x y)'
    >>> UGE(x, y).sexpr()
    '(bvuge x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvuge(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def UGT(a, b):
    """Create the Z3 expression (unsigned) `other > self`.
 
    Use the operator > for signed greater than.
 
    >>> x, y = BitVecs('x y', 32)
    >>> UGT(x, y)
    UGT(x, y)
    >>> (x > y).sexpr()
    '(bvsgt x y)'
    >>> UGT(x, y).sexpr()
    '(bvugt x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvugt(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def UDiv(a, b):
    """Create the Z3 expression (unsigned) division `self / other`.
 
    Use the operator / for signed division.
 
    >>> x = BitVec('x', 32)
    >>> y = BitVec('y', 32)
    >>> UDiv(x, y)
    UDiv(x, y)
    >>> UDiv(x, y).sort()
    BitVec(32)
    >>> (x / y).sexpr()
    '(bvsdiv x y)'
    >>> UDiv(x, y).sexpr()
    '(bvudiv x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BitVecRef(Z3_mk_bvudiv(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def URem(a, b):
    """Create the Z3 expression (unsigned) remainder `self % other`.
 
    Use the operator % for signed modulus, and SRem() for signed remainder.
 
    >>> x = BitVec('x', 32)
    >>> y = BitVec('y', 32)
    >>> URem(x, y)
    URem(x, y)
    >>> URem(x, y).sort()
    BitVec(32)
    >>> (x % y).sexpr()
    '(bvsmod x y)'
    >>> URem(x, y).sexpr()
    '(bvurem x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BitVecRef(Z3_mk_bvurem(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def SRem(a, b):
    """Create the Z3 expression signed remainder.
 
    Use the operator % for signed modulus, and URem() for unsigned remainder.
 
    >>> x = BitVec('x', 32)
    >>> y = BitVec('y', 32)
    >>> SRem(x, y)
    SRem(x, y)
    >>> SRem(x, y).sort()
    BitVec(32)
    >>> (x % y).sexpr()
    '(bvsmod x y)'
    >>> SRem(x, y).sexpr()
    '(bvsrem x y)'
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BitVecRef(Z3_mk_bvsrem(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def LShR(a, b):
    """Create the Z3 expression logical right shift.
 
    Use the operator >> for the arithmetical right shift.
 
    >>> x, y = BitVecs('x y', 32)
    >>> LShR(x, y)
    LShR(x, y)
    >>> (x >> y).sexpr()
    '(bvashr x y)'
    >>> LShR(x, y).sexpr()
    '(bvlshr x y)'
    >>> BitVecVal(4, 3)
    4
    >>> BitVecVal(4, 3).as_signed_long()
    -4
    >>> simplify(BitVecVal(4, 3) >> 1).as_signed_long()
    -2
    >>> simplify(BitVecVal(4, 3) >> 1)
    6
    >>> simplify(LShR(BitVecVal(4, 3), 1))
    2
    >>> simplify(BitVecVal(2, 3) >> 1)
    1
    >>> simplify(LShR(BitVecVal(2, 3), 1))
    1
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BitVecRef(Z3_mk_bvlshr(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def RotateLeft(a, b):
    """Return an expression representing `a` rotated to the left `b` times.
 
    >>> a, b = BitVecs('a b', 16)
    >>> RotateLeft(a, b)
    RotateLeft(a, b)
    >>> simplify(RotateLeft(a, 0))
    a
    >>> simplify(RotateLeft(a, 16))
    a
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BitVecRef(Z3_mk_ext_rotate_left(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def RotateRight(a, b):
    """Return an expression representing `a` rotated to the right `b` times.
 
    >>> a, b = BitVecs('a b', 16)
    >>> RotateRight(a, b)
    RotateRight(a, b)
    >>> simplify(RotateRight(a, 0))
    a
    >>> simplify(RotateRight(a, 16))
    a
    """
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BitVecRef(Z3_mk_ext_rotate_right(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def SignExt(n, a):
    """Return a bit-vector expression with `n` extra sign-bits.
 
    >>> x = BitVec('x', 16)
    >>> n = SignExt(8, x)
    >>> n.size()
    24
    >>> n
    SignExt(8, x)
    >>> n.sort()
    BitVec(24)
    >>> v0 = BitVecVal(2, 2)
    >>> v0
    2
    >>> v0.size()
    2
    >>> v  = simplify(SignExt(6, v0))
    >>> v
    254
    >>> v.size()
    8
    >>> print("%.x" % v.as_long())
    fe
    """
    if z3_debug():
        _z3_assert(_is_int(n), "First argument must be an integer")
        _z3_assert(is_bv(a), "Second argument must be a Z3 bit-vector expression")
    return BitVecRef(Z3_mk_sign_ext(a.ctx_ref(), n, a.as_ast()), a.ctx)
 
 
def ZeroExt(n, a):
    """Return a bit-vector expression with `n` extra zero-bits.
 
    >>> x = BitVec('x', 16)
    >>> n = ZeroExt(8, x)
    >>> n.size()
    24
    >>> n
    ZeroExt(8, x)
    >>> n.sort()
    BitVec(24)
    >>> v0 = BitVecVal(2, 2)
    >>> v0
    2
    >>> v0.size()
    2
    >>> v  = simplify(ZeroExt(6, v0))
    >>> v
    2
    >>> v.size()
    8
    """
    if z3_debug():
        _z3_assert(_is_int(n), "First argument must be an integer")
        _z3_assert(is_bv(a), "Second argument must be a Z3 bit-vector expression")
    return BitVecRef(Z3_mk_zero_ext(a.ctx_ref(), n, a.as_ast()), a.ctx)
 
 
def RepeatBitVec(n, a):
    """Return an expression representing `n` copies of `a`.
 
    >>> x = BitVec('x', 8)
    >>> n = RepeatBitVec(4, x)
    >>> n
    RepeatBitVec(4, x)
    >>> n.size()
    32
    >>> v0 = BitVecVal(10, 4)
    >>> print("%.x" % v0.as_long())
    a
    >>> v = simplify(RepeatBitVec(4, v0))
    >>> v.size()
    16
    >>> print("%.x" % v.as_long())
    aaaa
    """
    if z3_debug():
        _z3_assert(_is_int(n), "First argument must be an integer")
        _z3_assert(is_bv(a), "Second argument must be a Z3 bit-vector expression")
    return BitVecRef(Z3_mk_repeat(a.ctx_ref(), n, a.as_ast()), a.ctx)
 
 
def BVRedAnd(a):
    """Return the reduction-and expression of `a`."""
    if z3_debug():
        _z3_assert(is_bv(a), "First argument must be a Z3 bit-vector expression")
    return BitVecRef(Z3_mk_bvredand(a.ctx_ref(), a.as_ast()), a.ctx)
 
 
def BVRedOr(a):
    """Return the reduction-or expression of `a`."""
    if z3_debug():
        _z3_assert(is_bv(a), "First argument must be a Z3 bit-vector expression")
    return BitVecRef(Z3_mk_bvredor(a.ctx_ref(), a.as_ast()), a.ctx)
 
 
def BVAddNoOverflow(a, b, signed):
    """A predicate the determines that bit-vector addition does not overflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvadd_no_overflow(a.ctx_ref(), a.as_ast(), b.as_ast(), signed), a.ctx)
 
 
def BVAddNoUnderflow(a, b):
    """A predicate the determines that signed bit-vector addition does not underflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvadd_no_underflow(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def BVSubNoOverflow(a, b):
    """A predicate the determines that bit-vector subtraction does not overflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvsub_no_overflow(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def BVSubNoUnderflow(a, b, signed):
    """A predicate the determines that bit-vector subtraction does not underflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvsub_no_underflow(a.ctx_ref(), a.as_ast(), b.as_ast(), signed), a.ctx)
 
 
def BVSDivNoOverflow(a, b):
    """A predicate the determines that bit-vector signed division does not overflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvsdiv_no_overflow(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
def BVSNegNoOverflow(a):
    """A predicate the determines that bit-vector unary negation does not overflow"""
    if z3_debug():
        _z3_assert(is_bv(a), "First argument must be a Z3 bit-vector expression")
    return BoolRef(Z3_mk_bvneg_no_overflow(a.ctx_ref(), a.as_ast()), a.ctx)
 
 
def BVMulNoOverflow(a, b, signed):
    """A predicate the determines that bit-vector multiplication does not overflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvmul_no_overflow(a.ctx_ref(), a.as_ast(), b.as_ast(), signed), a.ctx)
 
 
def BVMulNoUnderflow(a, b):
    """A predicate the determines that bit-vector signed multiplication does not underflow"""
    _check_bv_args(a, b)
    a, b = _coerce_exprs(a, b)
    return BoolRef(Z3_mk_bvmul_no_underflow(a.ctx_ref(), a.as_ast(), b.as_ast()), a.ctx)
 
 
 
 
class ArraySortRef(SortRef):
    """Array sorts."""
 
    def domain(self):
        """Return the domain of the array sort `self`.
 
        >>> A = ArraySort(IntSort(), BoolSort())
        >>> A.domain()
        Int
        """
        return _to_sort_ref(Z3_get_array_sort_domain(self.ctx_refctx_ref(), self.astast), self.ctxctx)
 
    def domain_n(self, i):
        """Return the domain of the array sort `self`.
        """
        return _to_sort_ref(Z3_get_array_sort_domain_n(self.ctx_refctx_ref(), self.astast, i), self.ctxctx)
    
    def range(self):
        """Return the range of the array sort `self`.
 
        >>> A = ArraySort(IntSort(), BoolSort())
        >>> A.range()
        Bool
        """
        return _to_sort_ref(Z3_get_array_sort_range(self.ctx_refctx_ref(), self.astast), self.ctxctx)
 
 
class ArrayRef(ExprRef):
    """Array expressions. """
 
    def sort(self):
        """Return the array sort of the array expression `self`.
 
        >>> a = Array('a', IntSort(), BoolSort())
        >>> a.sort()
        Array(Int, Bool)
        """
        return ArraySortRef(Z3_get_sort(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
    def domain(self):
        """Shorthand for `self.sort().domain()`.
 
        >>> a = Array('a', IntSort(), BoolSort())
        >>> a.domain()
        Int
        """
        return self.sortsortsort().domain()
 
    def domain_n(self, i):
        """Shorthand for self.sort().domain_n(i)`."""
        return self.sortsortsort().domain_n(i)
 
    def range(self):
        """Shorthand for `self.sort().range()`.
 
        >>> a = Array('a', IntSort(), BoolSort())
        >>> a.range()
        Bool
        """
        return self.sortsortsort().range()
 
    def __getitem__(self, arg):
        """Return the Z3 expression `self[arg]`.
 
        >>> a = Array('a', IntSort(), BoolSort())
        >>> i = Int('i')
        >>> a[i]
        a[i]
        >>> a[i].sexpr()
        '(select a i)'
        """
        return _array_select(self, arg)
 
    def default(self):
        return _to_expr_ref(Z3_mk_array_default(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
 
def _array_select(ar, arg):
    if isinstance(arg, tuple):
        args = [ar.sort().domain_n(i).cast(arg[i]) for i in range(len(arg))]
        _args, sz = _to_ast_array(args)
        return _to_expr_ref(Z3_mk_select_n(ar.ctx_ref(), ar.as_ast(), sz, _args), ar.ctx)
    arg = ar.sort().domain().cast(arg)
    return _to_expr_ref(Z3_mk_select(ar.ctx_ref(), ar.as_ast(), arg.as_ast()), ar.ctx)
 
    
def is_array_sort(a):
    return Z3_get_sort_kind(a.ctx.ref(), Z3_get_sort(a.ctx.ref(), a.ast)) == Z3_ARRAY_SORT
 
 
def is_array(a):
    """Return `True` if `a` is a Z3 array expression.
 
    >>> a = Array('a', IntSort(), IntSort())
    >>> is_array(a)
    True
    >>> is_array(Store(a, 0, 1))
    True
    >>> is_array(a[0])
    False
    """
    return isinstance(a, ArrayRef)
 
 
def is_const_array(a):
    """Return `True` if `a` is a Z3 constant array.
 
    >>> a = K(IntSort(), 10)
    >>> is_const_array(a)
    True
    >>> a = Array('a', IntSort(), IntSort())
    >>> is_const_array(a)
    False
    """
    return is_app_of(a, Z3_OP_CONST_ARRAY)
 
 
def is_K(a):
    """Return `True` if `a` is a Z3 constant array.
 
    >>> a = K(IntSort(), 10)
    >>> is_K(a)
    True
    >>> a = Array('a', IntSort(), IntSort())
    >>> is_K(a)
    False
    """
    return is_app_of(a, Z3_OP_CONST_ARRAY)
 
 
def is_map(a):
    """Return `True` if `a` is a Z3 map array expression.
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> b = Array('b', IntSort(), IntSort())
    >>> a  = Map(f, b)
    >>> a
    Map(f, b)
    >>> is_map(a)
    True
    >>> is_map(b)
    False
    """
    return is_app_of(a, Z3_OP_ARRAY_MAP)
 
 
def is_default(a):
    """Return `True` if `a` is a Z3 default array expression.
    >>> d = Default(K(IntSort(), 10))
    >>> is_default(d)
    True
    """
    return is_app_of(a, Z3_OP_ARRAY_DEFAULT)
 
 
def get_map_func(a):
    """Return the function declaration associated with a Z3 map array expression.
 
    >>> f = Function('f', IntSort(), IntSort())
    >>> b = Array('b', IntSort(), IntSort())
    >>> a  = Map(f, b)
    >>> eq(f, get_map_func(a))
    True
    >>> get_map_func(a)
    f
    >>> get_map_func(a)(0)
    f(0)
    """
    if z3_debug():
        _z3_assert(is_map(a), "Z3 array map expression expected.")
    return FuncDeclRef(
        Z3_to_func_decl(
            a.ctx_ref(),
            Z3_get_decl_ast_parameter(a.ctx_ref(), a.decl().ast, 0),
        ),
        ctx=a.ctx,
    )
 
 
def ArraySort(*sig):
    """Return the Z3 array sort with the given domain and range sorts.
 
    >>> A = ArraySort(IntSort(), BoolSort())
    >>> A
    Array(Int, Bool)
    >>> A.domain()
    Int
    >>> A.range()
    Bool
    >>> AA = ArraySort(IntSort(), A)
    >>> AA
    Array(Int, Array(Int, Bool))
    """
    sig = _get_args(sig)
    if z3_debug():
        _z3_assert(len(sig) > 1, "At least two arguments expected")
    arity = len(sig) - 1
    r = sig[arity]
    d = sig[0]
    if z3_debug():
        for s in sig:
            _z3_assert(is_sort(s), "Z3 sort expected")
            _z3_assert(s.ctx == r.ctx, "Context mismatch")
    ctx = d.ctx
    if len(sig) == 2:
        return ArraySortRef(Z3_mk_array_sort(ctx.ref(), d.ast, r.ast), ctx)
    dom = (Sort * arity)()
    for i in range(arity):
        dom[i] = sig[i].ast
    return ArraySortRef(Z3_mk_array_sort_n(ctx.ref(), arity, dom, r.ast), ctx)
 
 
def Array(name, *sorts):
    """Return an array constant named `name` with the given domain and range sorts.
 
    >>> a = Array('a', IntSort(), IntSort())
    >>> a.sort()
    Array(Int, Int)
    >>> a[0]
    a[0]
    """
    s = ArraySort(sorts)
    ctx = s.ctx
    return ArrayRef(Z3_mk_const(ctx.ref(), to_symbol(name, ctx), s.ast), ctx)
 
 
def Update(a, *args):
    """Return a Z3 store array expression.
 
    >>> a    = Array('a', IntSort(), IntSort())
    >>> i, v = Ints('i v')
    >>> s    = Update(a, i, v)
    >>> s.sort()
    Array(Int, Int)
    >>> prove(s[i] == v)
    proved
    >>> j    = Int('j')
    >>> prove(Implies(i != j, s[j] == a[j]))
    proved
    """
    if z3_debug():
        _z3_assert(is_array_sort(a), "First argument must be a Z3 array expression")
    args = _get_args(args)
    ctx = a.ctx
    if len(args) <= 1:
        raise Z3Exception("array update requires index and value arguments")
    if len(args) == 2:
        i = args[0]
        v = args[1]
        i = a.sort().domain().cast(i)
        v = a.sort().range().cast(v)
        return _to_expr_ref(Z3_mk_store(ctx.ref(), a.as_ast(), i.as_ast(), v.as_ast()), ctx)
    v = a.sort().range().cast(args[-1])
    idxs = [a.sort().domain_n(i).cast(args[i]) for i in range(len(args)-1)]
    _args, sz = _to_ast_array(idxs)
    return _to_expr_ref(Z3_mk_store_n(ctx.ref(), a.as_ast(), sz, _args, v.as_ast()), ctx)
 
 
def Default(a):
    """ Return a default value for array expression.
    >>> b = K(IntSort(), 1)
    >>> prove(Default(b) == 1)
    proved
    """
    if z3_debug():
        _z3_assert(is_array_sort(a), "First argument must be a Z3 array expression")
    return a.default()
 
 
def Store(a, *args):
    """Return a Z3 store array expression.
 
    >>> a    = Array('a', IntSort(), IntSort())
    >>> i, v = Ints('i v')
    >>> s    = Store(a, i, v)
    >>> s.sort()
    Array(Int, Int)
    >>> prove(s[i] == v)
    proved
    >>> j    = Int('j')
    >>> prove(Implies(i != j, s[j] == a[j]))
    proved
    """
    return Update(a, args)
 
 
def Select(a, *args):
    """Return a Z3 select array expression.
 
    >>> a = Array('a', IntSort(), IntSort())
    >>> i = Int('i')
    >>> Select(a, i)
    a[i]
    >>> eq(Select(a, i), a[i])
    True
    """
    args = _get_args(args)
    if z3_debug():
        _z3_assert(is_array_sort(a), "First argument must be a Z3 array expression")
    return a[args]
 
 
def Map(f, *args):
    """Return a Z3 map array expression.
 
    >>> f = Function('f', IntSort(), IntSort(), IntSort())
    >>> a1 = Array('a1', IntSort(), IntSort())
    >>> a2 = Array('a2', IntSort(), IntSort())
    >>> b  = Map(f, a1, a2)
    >>> b
    Map(f, a1, a2)
    >>> prove(b[0] == f(a1[0], a2[0]))
    proved
    """
    args = _get_args(args)
    if z3_debug():
        _z3_assert(len(args) > 0, "At least one Z3 array expression expected")
        _z3_assert(is_func_decl(f), "First argument must be a Z3 function declaration")
        _z3_assert(all([is_array(a) for a in args]), "Z3 array expected expected")
        _z3_assert(len(args) == f.arity(), "Number of arguments mismatch")
    _args, sz = _to_ast_array(args)
    ctx = f.ctx
    return ArrayRef(Z3_mk_map(ctx.ref(), f.ast, sz, _args), ctx)
 
 
def K(dom, v):
    """Return a Z3 constant array expression.
 
    >>> a = K(IntSort(), 10)
    >>> a
    K(Int, 10)
    >>> a.sort()
    Array(Int, Int)
    >>> i = Int('i')
    >>> a[i]
    K(Int, 10)[i]
    >>> simplify(a[i])
    10
    """
    if z3_debug():
        _z3_assert(is_sort(dom), "Z3 sort expected")
    ctx = dom.ctx
    if not is_expr(v):
        v = _py2expr(v, ctx)
    return ArrayRef(Z3_mk_const_array(ctx.ref(), dom.ast, v.as_ast()), ctx)
 
 
def Ext(a, b):
    """Return extensionality index for one-dimensional arrays.
    >> a, b = Consts('a b', SetSort(IntSort()))
    >> Ext(a, b)
    Ext(a, b)
    """
    ctx = a.ctx
    if z3_debug():
        _z3_assert(is_array_sort(a) and (is_array(b) or b.is_lambda()), "arguments must be arrays")
    return _to_expr_ref(Z3_mk_array_ext(ctx.ref(), a.as_ast(), b.as_ast()), ctx)
 
 
def SetHasSize(a, k):
    ctx = a.ctx
    k = _py2expr(k, ctx)
    return _to_expr_ref(Z3_mk_set_has_size(ctx.ref(), a.as_ast(), k.as_ast()), ctx)
 
 
def is_select(a):
    """Return `True` if `a` is a Z3 array select application.
 
    >>> a = Array('a', IntSort(), IntSort())
    >>> is_select(a)
    False
    >>> i = Int('i')
    >>> is_select(a[i])
    True
    """
    return is_app_of(a, Z3_OP_SELECT)
 
 
def is_store(a):
    """Return `True` if `a` is a Z3 array store application.
 
    >>> a = Array('a', IntSort(), IntSort())
    >>> is_store(a)
    False
    >>> is_store(Store(a, 0, 1))
    True
    """
    return is_app_of(a, Z3_OP_STORE)
 
 
 
 
def SetSort(s):
    """ Create a set sort over element sort s"""
    return ArraySort(s, BoolSort())
 
 
def EmptySet(s):
    """Create the empty set
    >>> EmptySet(IntSort())
    K(Int, False)
    """
    ctx = s.ctx
    return ArrayRef(Z3_mk_empty_set(ctx.ref(), s.ast), ctx)
 
 
def FullSet(s):
    """Create the full set
    >>> FullSet(IntSort())
    K(Int, True)
    """
    ctx = s.ctx
    return ArrayRef(Z3_mk_full_set(ctx.ref(), s.ast), ctx)
 
 
def SetUnion(*args):
    """ Take the union of sets
    >>> a = Const('a', SetSort(IntSort()))
    >>> b = Const('b', SetSort(IntSort()))
    >>> SetUnion(a, b)
    union(a, b)
    """
    args = _get_args(args)
    ctx = _ctx_from_ast_arg_list(args)
    _args, sz = _to_ast_array(args)
    return ArrayRef(Z3_mk_set_union(ctx.ref(), sz, _args), ctx)
 
 
def SetIntersect(*args):
    """ Take the union of sets
    >>> a = Const('a', SetSort(IntSort()))
    >>> b = Const('b', SetSort(IntSort()))
    >>> SetIntersect(a, b)
    intersection(a, b)
    """
    args = _get_args(args)
    ctx = _ctx_from_ast_arg_list(args)
    _args, sz = _to_ast_array(args)
    return ArrayRef(Z3_mk_set_intersect(ctx.ref(), sz, _args), ctx)
 
 
def SetAdd(s, e):
    """ Add element e to set s
    >>> a = Const('a', SetSort(IntSort()))
    >>> SetAdd(a, 1)
    Store(a, 1, True)
    """
    ctx = _ctx_from_ast_arg_list([s, e])
    e = _py2expr(e, ctx)
    return ArrayRef(Z3_mk_set_add(ctx.ref(), s.as_ast(), e.as_ast()), ctx)
 
 
def SetDel(s, e):
    """ Remove element e to set s
    >>> a = Const('a', SetSort(IntSort()))
    >>> SetDel(a, 1)
    Store(a, 1, False)
    """
    ctx = _ctx_from_ast_arg_list([s, e])
    e = _py2expr(e, ctx)
    return ArrayRef(Z3_mk_set_del(ctx.ref(), s.as_ast(), e.as_ast()), ctx)
 
 
def SetComplement(s):
    """ The complement of set s
    >>> a = Const('a', SetSort(IntSort()))
    >>> SetComplement(a)
    complement(a)
    """
    ctx = s.ctx
    return ArrayRef(Z3_mk_set_complement(ctx.ref(), s.as_ast()), ctx)
 
 
def SetDifference(a, b):
    """ The set difference of a and b
    >>> a = Const('a', SetSort(IntSort()))
    >>> b = Const('b', SetSort(IntSort()))
    >>> SetDifference(a, b)
    setminus(a, b)
    """
    ctx = _ctx_from_ast_arg_list([a, b])
    return ArrayRef(Z3_mk_set_difference(ctx.ref(), a.as_ast(), b.as_ast()), ctx)
 
 
def IsMember(e, s):
    """ Check if e is a member of set s
    >>> a = Const('a', SetSort(IntSort()))
    >>> IsMember(1, a)
    a[1]
    """
    ctx = _ctx_from_ast_arg_list([s, e])
    e = _py2expr(e, ctx)
    return BoolRef(Z3_mk_set_member(ctx.ref(), e.as_ast(), s.as_ast()), ctx)
 
 
def IsSubset(a, b):
    """ Check if a is a subset of b
    >>> a = Const('a', SetSort(IntSort()))
    >>> b = Const('b', SetSort(IntSort()))
    >>> IsSubset(a, b)
    subset(a, b)
    """
    ctx = _ctx_from_ast_arg_list([a, b])
    return BoolRef(Z3_mk_set_subset(ctx.ref(), a.as_ast(), b.as_ast()), ctx)
 
 
 
 
def _valid_accessor(acc):
    """Return `True` if acc is pair of the form (String, Datatype or Sort). """
    if not isinstance(acc, tuple):
        return False
    if len(acc) != 2:
        return False
    return isinstance(acc[0], str) and (isinstance(acc[1], Datatype) or is_sort(acc[1]))
 
 
class Datatype:
    """Helper class for declaring Z3 datatypes.
 
    >>> List = Datatype('List')
    >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
    >>> List.declare('nil')
    >>> List = List.create()
    >>> # List is now a Z3 declaration
    >>> List.nil
    nil
    >>> List.cons(10, List.nil)
    cons(10, nil)
    >>> List.cons(10, List.nil).sort()
    List
    >>> cons = List.cons
    >>> nil  = List.nil
    >>> car  = List.car
    >>> cdr  = List.cdr
    >>> n = cons(1, cons(0, nil))
    >>> n
    cons(1, cons(0, nil))
    >>> simplify(cdr(n))
    cons(0, nil)
    >>> simplify(car(n))
    1
    """
 
    def __init__(self, name, ctx=None):
        self.ctxctx = _get_ctx(ctx)
        self.namename = name
        self.constructorsconstructors = []
 
    def __deepcopy__(self, memo={}):
        r = Datatype(self.namename, self.ctxctx)
        r.constructors = copy.deepcopy(self.constructorsconstructors)
        return r
 
    def declare_core(self, name, rec_name, *args):
        if z3_debug():
            _z3_assert(isinstance(name, str), "String expected")
            _z3_assert(isinstance(rec_name, str), "String expected")
            _z3_assert(
                all([_valid_accessor(a) for a in args]),
                "Valid list of accessors expected. An accessor is a pair of the form (String, Datatype|Sort)",
            )
        self.constructorsconstructors.append((name, rec_name, args))
 
    def declare(self, name, *args):
        """Declare constructor named `name` with the given accessors `args`.
        Each accessor is a pair `(name, sort)`, where `name` is a string and `sort` a Z3 sort
        or a reference to the datatypes being declared.
 
        In the following example `List.declare('cons', ('car', IntSort()), ('cdr', List))`
        declares the constructor named `cons` that builds a new List using an integer and a List.
        It also declares the accessors `car` and `cdr`. The accessor `car` extracts the integer
        of a `cons` cell, and `cdr` the list of a `cons` cell. After all constructors were declared,
        we use the method create() to create the actual datatype in Z3.
 
        >>> List = Datatype('List')
        >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
        >>> List.declare('nil')
        >>> List = List.create()
        """
        if z3_debug():
            _z3_assert(isinstance(name, str), "String expected")
            _z3_assert(name != "", "Constructor name cannot be empty")
        return self.declare_coredeclare_core(name, "is-" + name, *args)
 
    def __repr__(self):
        return "Datatype(%s, %s)" % (self.namename, self.constructorsconstructors)
 
    def create(self):
        """Create a Z3 datatype based on the constructors declared using the method `declare()`.
 
        The function `CreateDatatypes()` must be used to define mutually recursive datatypes.
 
        >>> List = Datatype('List')
        >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
        >>> List.declare('nil')
        >>> List = List.create()
        >>> List.nil
        nil
        >>> List.cons(10, List.nil)
        cons(10, nil)
        """
        return CreateDatatypes([self])[0]
 
 
class ScopedConstructor:
    """Auxiliary object used to create Z3 datatypes."""
 
    def __init__(self, c, ctx):
        self.cc = c
        self.ctxctx = ctx
 
    def __del__(self):
        if self.ctxctx.ref() is not None and Z3_del_constructor is not None:
            Z3_del_constructor(self.ctxctx.ref(), self.cc)
 
 
class ScopedConstructorList:
    """Auxiliary object used to create Z3 datatypes."""
 
    def __init__(self, c, ctx):
        self.cc = c
        self.ctxctx = ctx
 
    def __del__(self):
        if self.ctxctx.ref() is not None and Z3_del_constructor_list is not None:
            Z3_del_constructor_list(self.ctxctx.ref(), self.cc)
 
 
def CreateDatatypes(*ds):
    """Create mutually recursive Z3 datatypes using 1 or more Datatype helper objects.
 
    In the following example we define a Tree-List using two mutually recursive datatypes.
 
    >>> TreeList = Datatype('TreeList')
    >>> Tree     = Datatype('Tree')
    >>> # Tree has two constructors: leaf and node
    >>> Tree.declare('leaf', ('val', IntSort()))
    >>> # a node contains a list of trees
    >>> Tree.declare('node', ('children', TreeList))
    >>> TreeList.declare('nil')
    >>> TreeList.declare('cons', ('car', Tree), ('cdr', TreeList))
    >>> Tree, TreeList = CreateDatatypes(Tree, TreeList)
    >>> Tree.val(Tree.leaf(10))
    val(leaf(10))
    >>> simplify(Tree.val(Tree.leaf(10)))
    10
    >>> n1 = Tree.node(TreeList.cons(Tree.leaf(10), TreeList.cons(Tree.leaf(20), TreeList.nil)))
    >>> n1
    node(cons(leaf(10), cons(leaf(20), nil)))
    >>> n2 = Tree.node(TreeList.cons(n1, TreeList.nil))
    >>> simplify(n2 == n1)
    False
    >>> simplify(TreeList.car(Tree.children(n2)) == n1)
    True
    """
    ds = _get_args(ds)
    if z3_debug():
        _z3_assert(len(ds) > 0, "At least one Datatype must be specified")
        _z3_assert(all([isinstance(d, Datatype) for d in ds]), "Arguments must be Datatypes")
        _z3_assert(all([d.ctx == ds[0].ctx for d in ds]), "Context mismatch")
        _z3_assert(all([d.constructors != [] for d in ds]), "Non-empty Datatypes expected")
    ctx = ds[0].ctx
    num = len(ds)
    names = (Symbol * num)()
    out = (Sort * num)()
    clists = (ConstructorList * num)()
    to_delete = []
    for i in range(num):
        d = ds[i]
        names[i] = to_symbol(d.name, ctx)
        num_cs = len(d.constructors)
        cs = (Constructor * num_cs)()
        for j in range(num_cs):
            c = d.constructors[j]
            cname = to_symbol(c[0], ctx)
            rname = to_symbol(c[1], ctx)
            fs = c[2]
            num_fs = len(fs)
            fnames = (Symbol * num_fs)()
            sorts = (Sort * num_fs)()
            refs = (ctypes.c_uint * num_fs)()
            for k in range(num_fs):
                fname = fs[k][0]
                ftype = fs[k][1]
                fnames[k] = to_symbol(fname, ctx)
                if isinstance(ftype, Datatype):
                    if z3_debug():
                        _z3_assert(
                            ds.count(ftype) == 1,
                            "One and only one occurrence of each datatype is expected",
                        )
                    sorts[k] = None
                    refs[k] = ds.index(ftype)
                else:
                    if z3_debug():
                        _z3_assert(is_sort(ftype), "Z3 sort expected")
                    sorts[k] = ftype.ast
                    refs[k] = 0
            cs[j] = Z3_mk_constructor(ctx.ref(), cname, rname, num_fs, fnames, sorts, refs)
            to_delete.append(ScopedConstructor(cs[j], ctx))
        clists[i] = Z3_mk_constructor_list(ctx.ref(), num_cs, cs)
        to_delete.append(ScopedConstructorList(clists[i], ctx))
    Z3_mk_datatypes(ctx.ref(), num, names, out, clists)
    result = []
    # Create a field for every constructor, recognizer and accessor
    for i in range(num):
        dref = DatatypeSortRef(out[i], ctx)
        num_cs = dref.num_constructors()
        for j in range(num_cs):
            cref = dref.constructor(j)
            cref_name = cref.name()
            cref_arity = cref.arity()
            if cref.arity() == 0:
                cref = cref()
            setattr(dref, cref_name, cref)
            rref = dref.recognizer(j)
            setattr(dref, "is_" + cref_name, rref)
            for k in range(cref_arity):
                aref = dref.accessor(j, k)
                setattr(dref, aref.name(), aref)
        result.append(dref)
    return tuple(result)
 
 
class DatatypeSortRef(SortRef):
    """Datatype sorts."""
 
    def num_constructors(self):
        """Return the number of constructors in the given Z3 datatype.
 
        >>> List = Datatype('List')
        >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
        >>> List.declare('nil')
        >>> List = List.create()
        >>> # List is now a Z3 declaration
        >>> List.num_constructors()
        2
        """
        return int(Z3_get_datatype_sort_num_constructors(self.ctx_refctx_ref(), self.astast))
 
    def constructor(self, idx):
        """Return a constructor of the datatype `self`.
 
        >>> List = Datatype('List')
        >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
        >>> List.declare('nil')
        >>> List = List.create()
        >>> # List is now a Z3 declaration
        >>> List.num_constructors()
        2
        >>> List.constructor(0)
        cons
        >>> List.constructor(1)
        nil
        """
        if z3_debug():
            _z3_assert(idx < self.num_constructorsnum_constructors(), "Invalid constructor index")
        return FuncDeclRef(Z3_get_datatype_sort_constructor(self.ctx_refctx_ref(), self.astast, idx), self.ctxctx)
 
    def recognizer(self, idx):
        """In Z3, each constructor has an associated recognizer predicate.
 
        If the constructor is named `name`, then the recognizer `is_name`.
 
        >>> List = Datatype('List')
        >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
        >>> List.declare('nil')
        >>> List = List.create()
        >>> # List is now a Z3 declaration
        >>> List.num_constructors()
        2
        >>> List.recognizer(0)
        is(cons)
        >>> List.recognizer(1)
        is(nil)
        >>> simplify(List.is_nil(List.cons(10, List.nil)))
        False
        >>> simplify(List.is_cons(List.cons(10, List.nil)))
        True
        >>> l = Const('l', List)
        >>> simplify(List.is_cons(l))
        is(cons, l)
        """
        if z3_debug():
            _z3_assert(idx < self.num_constructorsnum_constructors(), "Invalid recognizer index")
        return FuncDeclRef(Z3_get_datatype_sort_recognizer(self.ctx_refctx_ref(), self.astast, idx), self.ctxctx)
 
    def accessor(self, i, j):
        """In Z3, each constructor has 0 or more accessor.
        The number of accessors is equal to the arity of the constructor.
 
        >>> List = Datatype('List')
        >>> List.declare('cons', ('car', IntSort()), ('cdr', List))
        >>> List.declare('nil')
        >>> List = List.create()
        >>> List.num_constructors()
        2
        >>> List.constructor(0)
        cons
        >>> num_accs = List.constructor(0).arity()
        >>> num_accs
        2
        >>> List.accessor(0, 0)
        car
        >>> List.accessor(0, 1)
        cdr
        >>> List.constructor(1)
        nil
        >>> num_accs = List.constructor(1).arity()
        >>> num_accs
        0
        """
        if z3_debug():
            _z3_assert(i < self.num_constructorsnum_constructors(), "Invalid constructor index")
            _z3_assert(j < self.constructorconstructor(i).arity(), "Invalid accessor index")
        return FuncDeclRef(
            Z3_get_datatype_sort_constructor_accessor(self.ctx_refctx_ref(), self.astast, i, j),
            ctx=self.ctxctx,
        )
 
 
class DatatypeRef(ExprRef):
    """Datatype expressions."""
 
    def sort(self):
        """Return the datatype sort of the datatype expression `self`."""
        return DatatypeSortRef(Z3_get_sort(self.ctx_refctx_ref(), self.as_astas_astas_ast()), self.ctxctx)
 
def DatatypeSort(name, ctx = None):
    """Create a reference to a sort that was declared, or will be declared, as a recursive datatype"""
    ctx = _get_ctx(ctx)
    return DatatypeSortRef(Z3_mk_datatype_sort(ctx.ref(), to_symbol(name, ctx)), ctx)
 
def TupleSort(name, sorts, ctx=None):
    """Create a named tuple sort base on a set of underlying sorts
    Example:
        >>> pair, mk_pair, (first, second) = TupleSort("pair", [IntSort(), StringSort()])
    """
    tuple = Datatype(name, ctx)
    projects = [("project%d" % i, sorts[i]) for i in range(len(sorts))]
    tuple.declare(name, *projects)
    tuple = tuple.create()
    return tuple, tuple.constructor(0), [tuple.accessor(0, i) for i in range(len(sorts))]
 
 
def DisjointSum(name, sorts, ctx=None):
    """Create a named tagged union sort base on a set of underlying sorts
    Example:
        >>> sum, ((inject0, extract0), (inject1, extract1)) = DisjointSum("+", [IntSort(), StringSort()])
    """
    sum = Datatype(name, ctx)
    for i in range(len(sorts)):
        sum.declare("inject%d" % i, ("project%d" % i, sorts[i]))
    sum = sum.create()
    return sum, [(sum.constructor(i), sum.accessor(i, 0)) for i in range(len(sorts))]
 
 
def EnumSort(name, values, ctx=None):
    """Return a new enumeration sort named `name` containing the given values.
 
    The result is a pair (sort, list of constants).
    Example:
        >>> Color, (red, green, blue) = EnumSort('Color', ['red', 'green', 'blue'])
    """
    if z3_debug():
        _z3_assert(isinstance(name, str), "Name must be a string")
        _z3_assert(all([isinstance(v, str) for v in values]), "Eumeration sort values must be strings")
        _z3_assert(len(values) > 0, "At least one value expected")
    ctx = _get_ctx(ctx)
    num = len(values)
    _val_names = (Symbol * num)()
    for i in range(num):
        _val_names[i] = to_symbol(values[i])
    _values = (FuncDecl * num)()
    _testers = (FuncDecl * num)()
    name = to_symbol(name)
    S = DatatypeSortRef(Z3_mk_enumeration_sort(ctx.ref(), name, num, _val_names, _values, _testers), ctx)
    V = []
    for i in range(num):
        V.append(FuncDeclRef(_values[i], ctx))
    V = [a() for a in V]
    return S, V
 
 
 
 
class ParamsRef:
    """Set of parameters used to configure Solvers, Tactics and Simplifiers in Z3.
 
    Consider using the function `args2params` to create instances of this object.
    """
 
    def __init__(self, ctx=None, params=None):
        self.ctxctx = _get_ctx(ctx)
        if params is None:
            self.paramsparams = Z3_mk_params(self.ctxctx.ref())
        else:
            self.paramsparams = params
        Z3_params_inc_ref(self.ctxctx.ref(), self.paramsparams)
 
    def __deepcopy__(self, memo={}):
        return ParamsRef(self.ctxctx, self.paramsparams)
 
    def __del__(self):
        if self.ctxctx.ref() is not None and Z3_params_dec_ref is not None:
            Z3_params_dec_ref(self.ctxctx.ref(), self.paramsparams)
 
    def set(self, name, val):
        """Set parameter name with value val."""
        if z3_debug():
            _z3_assert(isinstance(name, str), "parameter name must be a string")
        name_sym = to_symbol(name, self.ctxctx)
        if isinstance(val, bool):
            Z3_params_set_bool(self.ctxctx.ref(), self.paramsparams, name_sym, val)
        elif _is_int(val):
            Z3_params_set_uint(self.ctxctx.ref(), self.paramsparams, name_sym, val)
        elif isinstance(val, float):
            Z3_params_set_double(self.ctxctx.ref(), self.paramsparams, name_sym, val)
        elif isinstance(val, str):
            Z3_params_set_symbol(self.ctxctx.ref(), self.paramsparams, name_sym, to_symbol(val, self.ctxctx))
        else:
            if z3_debug():
                _z3_assert(False, "invalid parameter value")
 
    def __repr__(self):
        return Z3_params_to_string(self.ctxctx.ref(), self.paramsparams)
 
    def validate(self, ds):
        _z3_assert(isinstance(ds, ParamDescrsRef), "parameter description set expected")
        Z3_params_validate(self.ctxctx.ref(), self.paramsparams, ds.descr)
 
 
def args2params(arguments, keywords, ctx=None):
    """Convert python arguments into a Z3_params object.
    A ':' is added to the keywords, and '_' is replaced with '-'
 
    >>> args2params(['model', True, 'relevancy', 2], {'elim_and' : True})
    (params model true relevancy 2 elim_and true)
    """
    if z3_debug():
        _z3_assert(len(arguments) % 2 == 0, "Argument list must have an even number of elements.")
    prev = None
    r = ParamsRef(ctx)
    for a in arguments:
        if prev is None:
            prev = a
        else:
            r.set(prev, a)
            prev = None
    for k in keywords:
        v = keywords[k]
        r.set(k, v)
    return r
 
 
class ParamDescrsRef:
    """Set of parameter descriptions for Solvers, Tactics and Simplifiers in Z3.
    """
 
    def __init__(self, descr, ctx=None):
        _z3_assert(isinstance(descr, ParamDescrs), "parameter description object expected")
        self.ctxctx = _get_ctx(ctx)
        self.descrdescr = descr
        Z3_param_descrs_inc_ref(self.ctxctx.ref(), self.descrdescr)
 
    def __deepcopy__(self, memo={}):
        return ParamsDescrsRef(self.descrdescr, self.ctxctx)
 
    def __del__(self):
        if self.ctxctx.ref() is not None and Z3_param_descrs_dec_ref is not None:
            Z3_param_descrs_dec_ref(self.ctxctx.ref(), self.descrdescr)
 
    def size(self):
        """Return the size of in the parameter description `self`.
        """
        return int(Z3_param_descrs_size(self.ctxctx.ref(), self.descrdescr))
 
    def __len__(self):
        """Return the size of in the parameter description `self`.
        """
        return self.sizesize()
 
    def get_name(self, i):
        """Return the i-th parameter name in the parameter description `self`.
        """
        return _symbol2py(self.ctxctx, Z3_param_descrs_get_name(self.ctxctx.ref(), self.descrdescr, i))
 
    def get_kind(self, n):
        """Return the kind of the parameter named `n`.
        """
        return Z3_param_descrs_get_kind(self.ctxctx.ref(), self.descrdescr, to_symbol(n, self.ctxctx))
 
    def get_documentation(self, n):
        """Return the documentation string of the parameter named `n`.
        """
        return Z3_param_descrs_get_documentation(self.ctxctx.ref(), self.descrdescr, to_symbol(n, self.ctxctx))
 
    def __getitem__(self, arg):
        if _is_int(arg):
            return self.get_nameget_name(arg)
        else:
            return self.get_kindget_kind(arg)
 
    def __repr__(self):
        return Z3_param_descrs_to_string(self.ctxctx.ref(), self.descrdescr)
 
 
 
 
class Goal(Z3PPObject):
    """Goal is a collection of constraints we want to find a solution or show to be unsatisfiable (infeasible).
 
    Goals are processed using Tactics. A Tactic transforms a goal into a set of subgoals.
    A goal has a solution if one of its subgoals has a solution.
    A goal is unsatisfiable if all subgoals are unsatisfiable.
    """
 
    def __init__(self, models=True, unsat_cores=False, proofs=False, ctx=None, goal=None):
        if z3_debug():
            _z3_assert(goal is None or ctx is not None,
                       "If goal is different from None, then ctx must be also different from None")
        self.ctxctx = _get_ctx(ctx)
        self.goalgoal = goal
        if self.goalgoal is None:
            self.goalgoal = Z3_mk_goal(self.ctxctx.ref(), models, unsat_cores, proofs)
        Z3_goal_inc_ref(self.ctxctx.ref(), self.goalgoal)
 
    def __del__(self):
        if self.goalgoal is not None and self.ctxctx.ref() is not None and Z3_goal_dec_ref is not None:
            Z3_goal_dec_ref(self.ctxctx.ref(), self.goalgoal)
 
    def depth(self):
        """Return the depth of the goal `self`.
        The depth corresponds to the number of tactics applied to `self`.
 
        >>> x, y = Ints('x y')
        >>> g = Goal()
        >>> g.add(x == 0, y >= x + 1)
        >>> g.depth()
        0
        >>> r = Then('simplify', 'solve-eqs')(g)
        >>> # r has 1 subgoal
        >>> len(r)
        1
        >>> r[0].depth()
        2
        """
        return int(Z3_goal_depth(self.ctxctx.ref(), self.goalgoal))
 
    def inconsistent(self):
        """Return `True` if `self` contains the `False` constraints.
 
        >>> x, y = Ints('x y')
        >>> g = Goal()
        >>> g.inconsistent()
        False
        >>> g.add(x == 0, x == 1)
        >>> g
        [x == 0, x == 1]
        >>> g.inconsistent()
        False
        >>> g2 = Tactic('propagate-values')(g)[0]
        >>> g2.inconsistent()
        True
        """
        return Z3_goal_inconsistent(self.ctxctx.ref(), self.goalgoal)
 
    def prec(self):
        """Return the precision (under-approximation, over-approximation, or precise) of the goal `self`.
 
        >>> g = Goal()
        >>> g.prec() == Z3_GOAL_PRECISE
        True
        >>> x, y = Ints('x y')
        >>> g.add(x == y + 1)
        >>> g.prec() == Z3_GOAL_PRECISE
        True
        >>> t  = With(Tactic('add-bounds'), add_bound_lower=0, add_bound_upper=10)
        >>> g2 = t(g)[0]
        >>> g2
        [x == y + 1, x <= 10, x >= 0, y <= 10, y >= 0]
        >>> g2.prec() == Z3_GOAL_PRECISE
        False
        >>> g2.prec() == Z3_GOAL_UNDER
        True
        """
        return Z3_goal_precision(self.ctxctx.ref(), self.goalgoal)
 
    def precision(self):
        """Alias for `prec()`.
 
        >>> g = Goal()
        >>> g.precision() == Z3_GOAL_PRECISE
        True
        """
        return self.precprec()
 
    def size(self):
        """Return the number of constraints in the goal `self`.
 
        >>> g = Goal()
        >>> g.size()
        0
        >>> x, y = Ints('x y')
        >>> g.add(x == 0, y > x)
        >>> g.size()
        2
        """
        return int(Z3_goal_size(self.ctxctx.ref(), self.goalgoal))
 
    def __len__(self):
        """Return the number of constraints in the goal `self`.
 
        >>> g = Goal()
        >>> len(g)
        0
        >>> x, y = Ints('x y')
        >>> g.add(x == 0, y > x)
        >>> len(g)
        2
        """
        return self.sizesize()
 
    def get(self, i):
        """Return a constraint in the goal `self`.
 
        >>> g = Goal()
        >>> x, y = Ints('x y')
        >>> g.add(x == 0, y > x)
        >>> g.get(0)
        x == 0
        >>> g.get(1)
        y > x
        """
        return _to_expr_ref(Z3_goal_formula(self.ctxctx.ref(), self.goalgoal, i), self.ctxctx)
 
    def __getitem__(self, arg):
        """Return a constraint in the goal `self`.
 
        >>> g = Goal()
        >>> x, y = Ints('x y')
        >>> g.add(x == 0, y > x)
        >>> g[0]
        x == 0
        >>> g[1]
        y > x
        """
        if arg >= len(self):
            raise IndexError
        return self.getget(arg)
 
    def assert_exprs(self, *args):
        """Assert constraints into the goal.
 
        >>> x = Int('x')
        >>> g = Goal()
        >>> g.assert_exprs(x > 0, x < 2)
        >>> g
        [x > 0, x < 2]
        """
        args = _get_args(args)
        s = BoolSort(self.ctxctx)
        for arg in args:
            arg = s.cast(arg)
            Z3_goal_assert(self.ctxctx.ref(), self.goalgoal, arg.as_ast())
 
    def append(self, *args):
        """Add constraints.
 
        >>> x = Int('x')
        >>> g = Goal()
        >>> g.append(x > 0, x < 2)
        >>> g
        [x > 0, x < 2]
        """
        self.assert_exprsassert_exprs(*args)
 
    def insert(self, *args):
        """Add constraints.
 
        >>> x = Int('x')
        >>> g = Goal()
        >>> g.insert(x > 0, x < 2)
        >>> g
        [x > 0, x < 2]
        """
        self.assert_exprsassert_exprs(*args)
 
    def add(self, *args):
        """Add constraints.
 
        >>> x = Int('x')
        >>> g = Goal()
        >>> g.add(x > 0, x < 2)
        >>> g
        [x > 0, x < 2]
        """
        self.assert_exprsassert_exprs(*args)
 
    def convert_model(self, model):
        """Retrieve model from a satisfiable goal
        >>> a, b = Ints('a b')
        >>> g = Goal()
        >>> g.add(Or(a == 0, a == 1), Or(b == 0, b == 1), a > b)
        >>> t = Then(Tactic('split-clause'), Tactic('solve-eqs'))
        >>> r = t(g)
        >>> r[0]
        [Or(b == 0, b == 1), Not(0 <= b)]
        >>> r[1]
        [Or(b == 0, b == 1), Not(1 <= b)]
        >>> # Remark: the subgoal r[0] is unsatisfiable
        >>> # Creating a solver for solving the second subgoal
        >>> s = Solver()
        >>> s.add(r[1])
        >>> s.check()
        sat
        >>> s.model()
        [b = 0]
        >>> # Model s.model() does not assign a value to `a`
        >>> # It is a model for subgoal `r[1]`, but not for goal `g`
        >>> # The method convert_model creates a model for `g` from a model for `r[1]`.
        >>> r[1].convert_model(s.model())
        [b = 0, a = 1]
        """
        if z3_debug():
            _z3_assert(isinstance(model, ModelRef), "Z3 Model expected")
        return ModelRef(Z3_goal_convert_model(self.ctxctx.ref(), self.goalgoal, model.model), self.ctxctx)
 
    def __repr__(self):
        return obj_to_string(self)
 
    def sexpr(self):
        """Return a textual representation of the s-expression representing the goal."""
        return Z3_goal_to_string(self.ctxctx.ref(), self.goalgoal)
 
    def dimacs(self, include_names=True):
        """Return a textual representation of the goal in DIMACS format."""
        return Z3_goal_to_dimacs_string(self.ctxctx.ref(), self.goalgoal, include_names)
 
    def translate(self, target):
        """Copy goal `self` to context `target`.
 
        >>> x = Int('x')
        >>> g = Goal()
        >>> g.add(x > 10)
        >>> g
        [x > 10]
        >>> c2 = Context()
        >>> g2 = g.translate(c2)
        >>> g2
        [x > 10]
        >>> g.ctx == main_ctx()
        True
        >>> g2.ctx == c2
        True
        >>> g2.ctx == main_ctx()
        False
        """
        if z3_debug():
            _z3_assert(isinstance(target, Context), "target must be a context")
        return Goal(goal=Z3_goal_translate(self.ctxctx.ref(), self.goalgoal, target.ref()), ctx=target)
 
    def __copy__(self):
        return self.translatetranslate(self.ctxctx)
 
    def __deepcopy__(self, memo={}):
        return self.translatetranslate(self.ctxctx)
 
    def simplify(self, *arguments, **keywords):
        """Return a new simplified goal.
 
        This method is essentially invoking the simplify tactic.
 
        >>> g = Goal()
        >>> x = Int('x')
        >>> g.add(x + 1 >= 2)
        >>> g
        [x + 1 >= 2]
        >>> g2 = g.simplify()
        >>> g2
        [x >= 1]
        >>> # g was not modified
        >>> g
        [x + 1 >= 2]
        """
        t = Tactic("simplify")
        return t.apply(self, *arguments, **keywords)[0]
 
    def as_expr(self):
        """Return goal `self` as a single Z3 expression.
 
        >>> x = Int('x')
        >>> g = Goal()
        >>> g.as_expr()
        True
        >>> g.add(x > 1)
        >>> g.as_expr()
        x > 1
        >>> g.add(x < 10)
        >>> g.as_expr()
        And(x > 1, x < 10)
        """
        sz = len(self)
        if sz == 0:
            return BoolVal(True, self.ctxctx)
        elif sz == 1:
            return self.getget(0)
        else:
            return And([self.getget(i) for i in range(len(self))], self.ctxctx)
 
 
 
 
class AstVector(Z3PPObject):
    """A collection (vector) of ASTs."""
 
    def __init__(self, v=None, ctx=None):
        self.vectorvector = None
        if v is None:
            self.ctxctx = _get_ctx(ctx)
            self.vectorvector = Z3_mk_ast_vector(self.ctxctx.ref())
        else:
            self.vectorvector = v
            assert ctx is not None
            self.ctxctx = ctx
        Z3_ast_vector_inc_ref(self.ctxctx.ref(), self.vectorvector)
 
    def __del__(self):
        if self.vectorvector is not None and self.ctxctx.ref() is not None and Z3_ast_vector_dec_ref is not None:
            Z3_ast_vector_dec_ref(self.ctxctx.ref(), self.vectorvector)
 
    def __len__(self):
        """Return the size of the vector `self`.
 
        >>> A = AstVector()
        >>> len(A)
        0
        >>> A.push(Int('x'))
        >>> A.push(Int('x'))
        >>> len(A)
        2
        """
        return int(Z3_ast_vector_size(self.ctxctx.ref(), self.vectorvector))
 
    def __getitem__(self, i):
        """Return the AST at position `i`.
 
        >>> A = AstVector()
        >>> A.push(Int('x') + 1)
        >>> A.push(Int('y'))
        >>> A[0]
        x + 1
        >>> A[1]
        y
        """
 
        if isinstance(i, int):
            if i < 0:
                i += self.__len____len__()
 
            if i >= self.__len____len__():
                raise IndexError
            return _to_ast_ref(Z3_ast_vector_get(self.ctxctx.ref(), self.vectorvector, i), self.ctxctx)
 
        elif isinstance(i, slice):
            result = []
            for ii in range(*i.indices(self.__len____len__())):
                result.append(_to_ast_ref(
                    Z3_ast_vector_get(self.ctxctx.ref(), self.vectorvector, ii),
                    self.ctxctx,
                ))
            return result
 
    def __setitem__(self, i, v):
        """Update AST at position `i`.
 
        >>> A = AstVector()
        >>> A.push(Int('x') + 1)
        >>> A.push(Int('y'))
        >>> A[0]
        x + 1
        >>> A[0] = Int('x')
        >>> A[0]
        x
        """
        if i >= self.__len____len__():
            raise IndexError
        Z3_ast_vector_set(self.ctxctx.ref(), self.vectorvector, i, v.as_ast())
 
    def push(self, v):
        """Add `v` in the end of the vector.
 
        >>> A = AstVector()
        >>> len(A)
        0
        >>> A.push(Int('x'))
        >>> len(A)
        1
        """
        Z3_ast_vector_push(self.ctxctx.ref(), self.vectorvector, v.as_ast())
 
    def resize(self, sz):
        """Resize the vector to `sz` elements.
 
        >>> A = AstVector()
        >>> A.resize(10)
        >>> len(A)
        10
        >>> for i in range(10): A[i] = Int('x')
        >>> A[5]
        x
        """