python - Z3:找出变量的所有可能值

Question

我尝试获取有限域变量的所有可能值(例如 Bool 和枚举类型)，但不确定在 Z3 中执行此操作的正确方法是什么。我已经写了类似下面的内容，但想知道在 Z3 中是否有更好的方法。另外，有没有办法确定变量是否具有有限域或无限域？

下面，vsort是变量的排序值(例如Int('x').sort())

if vsort.kind() == Z3_BOOL_SORT:
    return [BoolVal(True), BoolVal(False)]
elif vsort.kind()  == Z3_DATATYPE_SORT:
    return [vsort.constructor(i)()
            for i in range(vsort.num_constructors())]
else:
    raise AssertionError('dont know how to deal with this sort')

Answer 1

你的方向是正确的。但是，代码缺少两个重要的情况:位向量和非枚举类型的有限数据类型(例如，一对有限类型)。这是考虑这两种额外情况的代码。函数 universe(s) 返回排序 s 的 Universe 中的元素。

顺便说一句，一个可能的改进是使用迭代器而不是列表。因此，我们甚至可以支持无限排序，例如整数和递归数据类型(例如列表)，并按需生成元素。

from z3 import *
import itertools

def universe(vsort):
    found = set()
    def rec(vsort):
        id = Z3_get_ast_id(vsort.ctx_ref(), vsort.as_ast())
        if id in found:
            raise AssertionError('recursive sorts are not supported')
        found.add(id)
        ctx = vsort.ctx
        if vsort.kind() == Z3_BOOL_SORT:
            return [ BoolVal(False, ctx), BoolVal(True, ctx) ]
        elif vsort.kind() == Z3_BV_SORT:
            sz = vsort.size()
            return [ BitVecVal(i, vsort) for i in range(2**sz) ]
        elif vsort.kind()  == Z3_DATATYPE_SORT:
            r = []
            for i in range(vsort.num_constructors()):
                c = vsort.constructor(i)
                if c.arity() == 0:
                    r.append(c())
                else:
                    domain_universe = []
                    for j in range(c.arity()):
                        domain_universe.append(rec(c.domain(j)))
                    r = r + [ c(*args) for args in itertools.product(*domain_universe) ]
            return r
        else:
            raise AssertionError('dont know how to deal with this sort')
    return rec(vsort)

以下是一些示例:

print universe(BoolSort())
>> [False, True]
print universe(BitVecSort(4))
>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
S, elems = EnumSort('S', ['a', 'b', 'c', 'd'])
print universe(S)
>> [a, b, c, d]


# Create a Pair (Bool, S)
d = Datatype('Pair')
d.declare('mkpair', ('bval', BoolSort()), ('sval', S))
D = d.create()
print universe(D)
>> [mkpair(False, a), mkpair(False, b), mkpair(False, c), mkpair(False, d), mkpair(True, a), mkpair(True, b), mkpair(True, c), mkpair(True, d)]

# Create a Choice sort where each element is a Pair or a BitVector of size 4.
c = Datatype('Choice')
c.declare('aspair', ('pval', D))
c.declare('asbv', ('bval', BitVecSort(4)))
C = c.create()
print universe(C)
>> [aspair(mkpair(False, a)), aspair(mkpair(False, b)), aspair(mkpair(False, c)), aspair(mkpair(False, d)), aspair(mkpair(True, a)), aspair(mkpair(True, b)), aspair(mkpair(True, c)), aspair(mkpair(True, d)), asbv(0), asbv(1), asbv(2), asbv(3), asbv(4), asbv(5), asbv(6), asbv(7), asbv(8), asbv(9), asbv(10), asbv(11), asbv(12), asbv(13), asbv(14), asbv(15)]

l = Datatype('List')
l.declare('cons', ('car', BoolSort()), ('cdr', l))
l.declare('nil')
List = l.create()
print universe(List)
>> Traceback (most recent call last):
>> ...
>> AssertionError: recursive sorts are not supported