4 个版本 (2 个重大更改)
0.3.0 | 2023 年 8 月 7 日 |
---|---|
0.2.1 | 2023 年 7 月 11 日 |
0.2.0 | 2023 年 2 月 23 日 |
0.1.0 | 2022 年 9 月 16 日 |
在 科学 中排名第 232
430KB
11K SLoC
amzn-smt-ir
amzn-smt-ir
是一个用于处理 SMT-LIB 公式的 Rust 库。
表示
逻辑
SMT-LIB 逻辑由 aws_smt_ir::Logic
trait 表示,该 trait 封装了逻辑中的操作类型(稍后详细介绍)以及是否允许存在量词和未定义函数(对应于 SMT-LIB 逻辑名称中的 QF
(Quantifier-Free) 和 UF
(包括 Uninterpreted Functions) 前缀)。希望排除非 Core
操作、量词或未定义函数的逻辑可以指定 aws_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
和它们相应的操作类型定义在 aws_smt_ir::logic
模块中。用户也可以使用提供的 derive 宏定义自定义 Logic
和操作,以实现预期的特性(请参阅 "Derives" 部分)。
项
术语通过以下格式表示:aws_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的大部分标准特质,尽管PartialEq
和Eq
是通过指针相等性实现的(由于每个值都存在唯一副本,因此等效)。
遍历
该库提供了两种遍历IR节点的模式。
计算
Visit
系列特质(Visitor
、Visit
和SuperVisit
)提供了遍历IR节点并构建某些结果(存储在Visitor
中)的访问者模式。有关详细信息,请参阅特质的相应文档。
转换
Fold
系列特质(Folder
、Fold
和SuperFold
)提供了一种将IR节点转换为其他IR节点的模式。有关详细信息,请参阅特质的相应文档。
派生
该库提供了三个派生宏,用于生成用作操作的类型(即L::Op
的L: Logic
)所期望的特质实现。
Operation
:实现了Operation
特质,该特质确定如何从函数符号和参数列表解析操作,实现了Iterate
特质,该特质允许通过Args
特质构建函数参数的迭代器,以及Debug
、Display
和From
实现,用于将类型转换为IOp
和Term
。Visit
:实现了用于执行操作枚举的标准递归遍历的SuperVisit
特质。Fold
:实现了用于执行操作枚举的标准递归转换的SuperFold
特质。
依赖项
~7–14MB
~153K SLoC