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

Apache-2.0

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的大部分标准特质,尽管PartialEqEq是通过指针相等性实现的(由于每个值都存在唯一副本,因此等效)。

遍历

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

计算

Visit系列特质(VisitorVisitSuperVisit)提供了遍历IR节点并构建某些结果(存储在Visitor中)的访问者模式。有关详细信息,请参阅特质的相应文档。

转换

Fold系列特质(FolderFoldSuperFold)提供了一种将IR节点转换为其他IR节点的模式。有关详细信息,请参阅特质的相应文档。

派生

该库提供了三个派生宏,用于生成用作操作的类型(即L::OpL: Logic)所期望的特质实现。

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

依赖项

~7–14MB
~153K SLoC