#smt #smt-lib #solver

已删除 amzn-smt-ir

SMT问题中间表示

0.1.0 2022年9月12日

#14 in #smt-lib

Apache-2.0

250KB
6K SLoC

amzn-smt-ir

amzn-smt-ir 是一个用于处理 SMT-LIB 公式的 Rust 库。

表示

逻辑

SMT-LIB 逻辑由 amzn_smt_ir::Logic trait 表示,该 trait 封装了逻辑中操作的类型(稍后详述)以及是否允许存在量词和非解释函数(对应于 SMT-LIB 逻辑名称中的 QFQuantifier-Free)和 UF (包括 Uninterpreted Functions)前缀)。希望省略非 Core 操作、量词或非解释函数的逻辑可以指定 amzn_smt_ir::Void 作为相应的关联类型 -- 由于 Void 是不可居住的,因此在类型级别上,结果逻辑中的项不可能包含相应的组件。

操作

注意: 此库将 SMT 函数称为 "操作",以避免与 Rust 的 Fn 特性混淆。

SMT-LIB 理论函数表示为 enum。例如,SMT-LIB Core 的简化版本可能如下所示

enum CoreOp<Term> {
	Not(Term),
	And(Vec<Term>),
	Ite(Term, Term, Term),
}

这使得在类型级别上编码不同函数之间的区别成为可能,例如编码 not 是一元函数,ite 是三元函数,而 and 可以接受任意数量的参数(因为它被注解为 :left-assoc)。

注意: 索引函数定义为包含一个索引数组作为其第一个元组字段,例如,对于位向量 extract 函数,定义为 Extract([IIndex; 2], Term)

预定义的 Logic 和它们对应的操作类型定义在 amzn_smt_ir::logic 模块中。用户还可以使用提供的 derive 宏定义自定义 Logic 和操作,以实现预期的特性(请参阅 "Derives" 部分)。

术语通过 amzn_smt_ir::Term<L: Logic> 来表示,它代表逻辑 L 中的 SMT 术语。

enum Term<T: Logic> {
    /// A constant value.
    Constant(IConst),

    /// A variable representing a value.
    Variable(IVar<T::Var>),

    /// An operation in SMT-LIB's Core theory.
    CoreOp(ICoreOp<T>),

    /// A non-Core operation.
    OtherOp(IOp<T>),

    /// An uninterpreted function.
    UF(IUF<T>),

    /// Simultaneous let-binding e.g. `(let ((x true) (y false)) (and x y))`
    Let(ILet<T>),

    /// SMT-LIB `match` expression -- not yet supported
    Match(IMatch<T>),

    /// Quantified term.
    Quantifier(IQuantifier<T>),
}

注意:由于 Core 在每个逻辑中都是隐式包含的,因此 CoreOp 可能存在于任何类型的 Term 中。

类型名前缀 I 表示这些类型被内联(以防止重复,也称为 哈希内联)。前缀为 I 的类型实际上是指向一个唯一的副本的指针,这些副本存储在以哈希为键的查找表中。当实例化这些类型之一时,首先检查相应的表是否包含该值;如果包含,则返回现有副本的指针;如果不包含,则在表中存储该值并返回新副本的指针。I 前缀类型通过将操作委托给内部值来实现 Rust 的大多数标准特性,尽管 PartialEqEq 是通过指针相等来实现的(因为每个值都有一个唯一的副本,所以它们是等价的)。

遍历

该库提供了两种遍历 IR 节点的模式。

计算

Visit 家族的特性和 VisitorVisitSuperVisit 提供了一种遍历 IR 节点并构建一些结果(存储在 Visitor 中)的访问者模式。有关详细信息,请参阅特性和各自的文档。

转换

Fold 家族的特性和 FolderFoldSuperFold 提供了一种将 IR 节点转换为其他 IR 节点的模式。有关详细信息,请参阅特性和各自的文档。

导出

该库提供了三个用于生成作为操作使用的类型预期实现的导出宏(即 L::OpL: Logic

  • Operation:实现 Operation 特性,该特性确定如何从函数符号和参数列表中解析操作,以及实现 Iterate 特性,该特性允许通过 Args 特性构建函数参数的迭代器,以及为将类型转换为 IOpTerm 实现的 DebugDisplayFrom
  • Visit:实现 SuperVisit 特性,以执行操作枚举的标准递归遍历。
  • Fold:实现 SuperFold 特性,以执行操作枚举的标准递归转换。

依赖关系

~9-16MB
~176K SLoC