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