moon-octagon

    Integer octagonal abstract domains, relational transfer functions and independently checkable witnesses in pure MoonBit

    octagon
    abstract-interpretation
    integer-constraints
    invariants
    Download zip
    Author
    Version
    0.2.0
    License
    MIT
    Last updated
    9 hours ago
    Downloads
    13

    No dependencies

    #moon-octagon

    ci

    纯 MoonBit 整数关系约束与不变量分析库。 保留 x+y≤c、x−y≤c、x≤c 等关系,提供整数紧闭包、不可变抽象状态、赋值与投影、分支合并、循环不变量及可检查的反例。不是一个只有命令行的演示:核心公开 API 可被其他 MoonBit 项目直接调用。

    #为什么需要它

    独立区间知道 x∈[0,100]、y∈[0,100],却无法保留两者的总量限制 x+y≤100。八边形域使用带符号变量的差分约束矩阵,在可控的三次方闭包成本内保留这类关系。

    本地实现覆盖三个不同工作流,全部有可运行输入:

    使用者与输入已实现输出例子
    程序分析工具:初始变量范围、循环条件、顺序赋值关系不变量、归纳性复核、预算耗尽状态;x++、y-- 保留 x+y=10,退出时推出 y=0examples/loop.json
    配置检查工具:主副本资源的上下界与总量约束总量边界、规则蕴含判定、违反候选规则的整数反例、原始规则冲突子集examples/configuration.json
    设备数据处理工具:整数刻度测量区间、通道差值容差联合可行域、收紧后的各通道范围及一致的整数样本;首通道 [20,23] 且差值在 ±2 内,第二通道为 [18,25]examples/sensors.json

    #本地运行

    需要 MoonBit moonc 0.10.21(本地实测 v0.10.21+06da1ed44,moon 0.1.20261117)和 Node.js ≥22;无第三方包依赖,仅官方 core。当前工具链的 #derive、JSON 自由函数等接口不承诺兼容旧编译器。

    # 安装方式见 https://www.moonbitlang.com/download ;也可以指向已有工具链: $env:MOON_HOME = 'C:\path\to\moon' $env:Path = "$env:MOON_HOME\bin;$env:Path" moon run examples/relations --target js -j 1 moon run examples/interval-gap --target js -j 1 node scripts/cli.mjs examples/configuration.json node scripts/cli.mjs examples/sensors.json node scripts/cli.mjs examples/loop.json node scripts/cli.mjs examples/parity-conflict.json

    examples/interval-gap 对同一份 x0+x1<=100 预算同时给出独立区间结论(和上界 200)与关系域结论(上界 100),并打印 render 的规范形式。

    scripts/cli.mjs 负责输入读取、调用构建产物及进程退出码;所有模型校验与分析都在 MoonBit 中执行。它直接导入 MoonBit 导出的 JS 函数,不把大文件塞进进程参数。输入可来自文件或 stdin(-),--out FILE 把结果写到文件,--batch 对每项保留独立 ok 状态。退出码:成功 0,请求错误 2,用法错误 64,构建/内部失败 1;node --test scripts/cli.test.mjs 覆盖 stdin、批处理和错误码。

    #调用库

    Mooncakes 包:haol-05/moon-octagon 0.2.0(服务端 build_status=success)。用 moon add haol-05/moon-octagon 安装,或在 moon.pkg 中导入 "haol-05/moon-octagon" @oct:

    let s = @oct.from_constraints(2, [
    @oct.lower(0, 0L),
    @oct.lower(1, 0L),
    @oct.relation(@oct.positive(0), @oct.positive(1), 100L),
    ])
    let joint_limit = s.entails(
    @oct.relation(@oct.positive(0), @oct.positive(1), 100L),
    )
    let after_copy = s.assign(1, @oct.negative(0), 100L)
    // after_copy 保留 x+y=100;原 s 不变。

    完整公开接口在 pkg.generated.mbti,独立调用示例在 examples/relations/main.mbt。会失败的调用抛出 OctagonError,调用者显式捕获或传播。

    接口组已实现行为
    构造与查询top、bottom、from_constraints、refine、interval、intervals、bound、entails、contains、constraints、render
    集合与状态变换meet、join、subset_of、equivalent、forget、forget_many、assign、set_constant、widen、execute
    证据witness、check、check_all、satisfies、explain_conflict、verify_conflict、render_constraint
    循环与集成analyze_loop、verify_invariant、process_json、process_batch_json、report
    文本与区间层parse_constraints、to_text、box_top、box_bottom、Octagon::to_box、Box::to_octagon、Box::meet/join/widen/subset_of/entails/assign/forget/set_constant/witness/render/to_text、box_join_all、box_meet_all
    多状态与 CFGassign_parallel、rename、join_all、meet_all、analyze_blocks(Block、CfgResult)与 JSON text/box/cfg

    文本前端接受 x0 in [0,100]、x0 <= c、x0 >= c、x0 + x1 <= c、x0 - x1 <= c 与 x0 + x1 = c,按行或分号分隔,# 起注释;to_text 输出可回读的约束文本。Box 是同一输入上的独立区间层,用于廉价预分析或与八边形域对照;analyze_blocks 在最多 64 个基本块上做有界 worklist 分析,回边处才 widening。

    #数学语义与边界

    • 变量属于数学整数 Z,不是实数,也不是 MoonBit Int 的溢出回绕模型。将本库用于机器整数程序前,宿主必须保证不溢出或自行建模。
    • 支持 ±x≤c 与 ±x±y≤c;不支持任意线性系数、非线性、概率、资源排程、源代码解析或完整编译器验证。传感器示例使用整数刻度,不虚构实数误差覆盖。
    • 闭包是整数紧闭包,能识别 x+y=1 且 x=y 这种实数可行而整数不可行的系统。join 是最小八边形上近似,可能引入原分支没有的状态。
    • check 的 Refuted 给出抽象域中的具体整数反例,不自动证明真实程序可达。空域返回 Vacuous,与 Proven 分开。
    • 循环只分析单个显式建模的 while 迭代:延迟 widening、有限 narrowing,最后复核初始化与保持性。BudgetExhausted 只给部分迭代状态,不算不变量;没有终止性证明。
    • widening 保留未经闭包的左操作数;查询在副本上闭包。自行连续调用时请不要将 canonical() 的结果替换回 widening 序列,否则不再保证有限链稳定。
    • 冲突子集是 包含意义极小,不是约束数最少;验证器从原始下标重建每次删约束的系统。验证复用闭包内核,不宣称来自另一个证明器。
    • 规模、算术预算、JSON 契约见 docs/SEMANTICS.md。上限是故障边界,非所有最坏组合的响应时间承诺。

    #验证与工程交付

    moon fmt --check moon check --target js --deny-warn -j 1 moon check --target wasm --deny-warn -j 1 moon check --target wasm-gc --deny-warn -j 1 moon build --target js -j 1 moon test --target js --deny-warn -j 1 node --test scripts/cli.test.mjs node scripts/verify.mjs

    本地已验证 JS / Wasm / WasmGC 每目标 68 项测试(含固定种子随机系统、文本/区间层回读、并行赋值、CFG 与空域/预算/协议错误路径),额外独立枚举 1,046 个系统、21,216 次查询、320 次赋值、320 次 join/meet、64 组冲突证据;其中穷举了 28 条二元有符号规则的所有 406 种无序二规则组合。测试目标是有限模型中的语义,不把有限测试当成形式化证明。详见 docs/VALIDATION.md,可复跑收据写在 _build/reports/independent-oracle.json。

    GitHub Actions(ci.yml)在 Linux 上分四个作业运行格式检查、三个目标的 check/build/test、Native 构建测试、示例和独立 oracle;作业结果以 Actions 页面为准。

    本机 Windows Native 受当前 runtime 仅支持 MSVC 的限制,使用已有 GCC 时编译官方 runtime 失败,因此不报告本机 Native 通过;CI 的 Linux native 作业单独运行并在 Actions 记录。

    本项目与已有区间分析、SMT/符号执行、Cassowary、STN 存在数学和用途相邻关系。GitHub 仓库/README/代码与 Mooncakes 都已检索,有限范围未发现相同整数八边形域核心;不能保证全网零重叠或官方过审。 具体查询与源码证据见 SOURCES.md。

    MIT 许可证。算法来自公开文献的独立实现,不是新数学算法,也不是 APRON 完整移植。源码仓库已公开在 https://github.com/haol-05/moon-octagon,Mooncakes 0.2.0 已发布并通过服务端构建;没有提交报名或进入官方初审。

    OctagonError

    pub suberror OctagonError {
    Invalid(String)
    Limit(String)
    Arithmetic(String)
    } derive(
    Debug
    )

    Assignment

    pub(all) struct Assignment {
    target : Int
    source : Term
    offset : Int64
    }

    One right-hand side of a simultaneous assignment.

    Block

    pub(all) struct Block {
    conditions : Array[Constraint]
    body : Array[Transfer]
    successors : Array[Int]
    }

    One basic block: a guard, a straight-line transfer body, and successors.

    Box

    pub struct Box {
    dimensions : Int
    lower : Array[Int64?]
    upper : Array[Int64?]
    empty : Bool
    }

    Independent per-variable integer intervals. This cheap layer is what the octagon domain improves on; conversion helpers make the precision gap measurable. All operations return fresh states.

    Box::assign

    fn Box::assign(self : Box, target : Int, source : Term, offset : Int64) -> Box raise OctagonError

    Box::contains

    fn Box::contains(self : Box, values : Array[Int64]) -> Bool raise OctagonError

    Box::entails

    fn Box::entails(self : Box, c : Constraint) -> Bool raise OctagonError

    Box::equivalent

    fn Box::equivalent(self : Box, other : Box) -> Bool raise OctagonError

    Box::forget

    fn Box::forget(self : Box, target : Int) -> Box raise OctagonError

    Box::interval

    fn Box::interval(self : Box, i : Int) -> Interval? raise OctagonError

    Box::is_bottom

    fn Box::is_bottom(self : Box) -> Bool

    Box::is_top

    fn Box::is_top(self : Box) -> Bool

    Box::join

    fn Box::join(self : Box, other : Box) -> Box raise OctagonError

    Box::meet

    fn Box::meet(self : Box, other : Box) -> Box raise OctagonError

    Box::render

    fn Box::render(self : Box) -> String

    Box::set_constant

    fn Box::set_constant(self : Box, target : Int, value : Int64) -> Box raise OctagonError

    Box::size

    fn Box::size(self : Box) -> Int

    Box::subset_of

    fn Box::subset_of(self : Box, other : Box) -> Bool raise OctagonError

    Box::to_octagon

    fn Box::to_octagon(self : Box) -> Octagon raise OctagonError

    Build the weakest octagon containing this box; all relations are dropped.

    Box::to_text

    fn Box::to_text(self : Box) -> String raise OctagonError

    Serialise the box as constraint text accepted by parse_constraints.

    Box::widen

    fn Box::widen(self : Box, next : Box) -> Box raise OctagonError

    Threshold widening: any endpoint that moves becomes unbounded.

    Box::witness

    fn Box::witness(self : Box) -> Array[Int64]? raise OctagonError

    Choose a concrete point inside the box, or None for the empty box.

    CfgResult

    pub(all) struct CfgResult {
    states : Array[Octagon]
    status : CfgStatus
    steps : Int
    }

    CfgStatus

    pub(all) enum CfgStatus {
    CfgStable
    CfgBudgetExhausted
    }

    Conflict

    pub(all) struct Conflict {
    indices : Array[Int]
    checks : Int
    } derive(Eq,
    Debug
    ,
    ToJson
    )

    Constraint

    pub(all) struct Constraint {
    left : Term
    right : Term?
    bound : Int64
    } derive(Eq,
    Debug
    ,
    ToJson
    )

    left + right <= bound. None makes this a unary constraint.

    Interval

    pub(all) struct Interval {
    lower : Int64?
    upper : Int64?
    } derive(Eq,
    Debug
    ,
    ToJson
    )

    None means unbounded; an empty domain has no interval.

    LoopResult

    pub struct LoopResult {
    head : Octagon
    status : LoopStatus
    iterations : Int
    }

    LoopResult::invariant

    fn LoopResult::invariant(self : LoopResult) -> Octagon

    LoopResult::iterations

    fn LoopResult::iterations(self : LoopResult) -> Int

    LoopResult::status

    fn LoopResult::status(self : LoopResult) -> LoopStatus

    LoopStatus

    pub enum LoopStatus {
    Inductive
    BudgetExhausted
    } derive(
    Debug
    ,
    ToJson
    )

    Octagon

    pub struct Octagon {
    dimensions : Int
    matrix : Array[Array[Int64]]
    empty : Bool
    }

    Immutable domain over mathematical integers, independent of machine overflow semantics.

    Octagon::assign

    fn Octagon::assign(self : Octagon, target : Int, source : Term, offset : Int64) -> Octagon raise OctagonError

    Exact octagonal image of x[target] := sign * x[source] + offset. Simultaneous RHS semantics also handles target == source.

    Octagon::assign_parallel

    fn Octagon::assign_parallel(self : Octagon, assignments : Array[Assignment]) -> Octagon raise OctagonError

    Apply all assignments simultaneously: every right-hand side reads the old state. Targets must be distinct. At most 8 assignments fit in 24 dimensions.

    Octagon::bound

    fn Octagon::bound(self : Octagon, a : Term, b : Term?) -> Int64? raise OctagonError

    Tight upper bound for a signed unary or binary expression. Empty => error. None => expression is unbounded above.

    Octagon::canonical

    fn Octagon::canonical(self : Octagon) -> Octagon raise OctagonError

    Octagon::check

    fn Octagon::check(self : Octagon, c : Constraint) -> Verdict raise OctagonError

    Octagon::check_all

    fn Octagon::check_all(self : Octagon, constraints : Array[Constraint]) -> Array[Verdict] raise OctagonError

    Batch version of check. Every input is validated even for an empty domain, and at most 512 candidates are accepted per call.

    Octagon::constraints

    fn Octagon::constraints(self : Octagon) -> Array[Constraint] raise OctagonError

    Export a complete canonical conjunction; callers receive fresh owned arrays.

    Octagon::contains

    fn Octagon::contains(self : Octagon, values : Array[Int64]) -> Bool raise OctagonError

    Octagon::entails

    fn Octagon::entails(self : Octagon, c : Constraint) -> Bool raise OctagonError

    Octagon::equivalent

    fn Octagon::equivalent(self : Octagon, other : Octagon) -> Bool raise OctagonError

    Octagon::execute

    fn Octagon::execute(self : Octagon, operations : Array[Transfer]) -> Octagon raise OctagonError

    Octagon::forget

    fn Octagon::forget(self : Octagon, target : Int) -> Octagon raise OctagonError

    Existential projection. Consequences among retained variables survive.

    Octagon::forget_many

    fn Octagon::forget_many(self : Octagon, targets : Array[Int]) -> Octagon raise OctagonError

    Existential projection of several variables in one closure. The result does not depend on the order of targets; an empty list returns a canonical copy of the domain.

    Octagon::interval

    fn Octagon::interval(self : Octagon, i : Int) -> Interval? raise OctagonError

    Octagon::intervals

    fn Octagon::intervals(self : Octagon) -> Array[Interval?] raise OctagonError

    All variable intervals from a single canonicalisation. Entries are None only when the domain is empty.

    Octagon::is_bottom

    fn Octagon::is_bottom(self : Octagon) -> Bool

    Octagon::is_top

    fn Octagon::is_top(self : Octagon) -> Bool

    Octagon::join

    fn Octagon::join(self : Octagon, other : Octagon) -> Octagon raise OctagonError

    Least octagonal overapproximation of union. It may include extra integer states.

    Octagon::meet

    fn Octagon::meet(self : Octagon, other : Octagon) -> Octagon raise OctagonError

    Octagon::refine

    fn Octagon::refine(self : Octagon, constraints : Array[Constraint]) -> Octagon raise OctagonError

    Intersection with guards; all inputs validated even for an empty domain.

    Octagon::rename

    fn Octagon::rename(self : Octagon, permutation : Array[Int]) -> Octagon raise OctagonError

    Rename variables so that new x_i equals old x_permutation[i]. The permutation must be a bijection over 0..dimensions-1.

    Octagon::render

    fn Octagon::render(self : Octagon) -> String raise OctagonError

    Stable single-line rendering for logs and examples: per-variable intervals followed by every non-redundant binary bound of the canonical conjunction. Only the four signed sums are printed because the flipped entries are their closure mirrors. Use constraints or report for machine output.

    Octagon::report

    Stable JSON output with explicit empty/unbounded states and decimal Int64 strings.

    Octagon::set_constant

    fn Octagon::set_constant(self : Octagon, target : Int, value : Int64) -> Octagon raise OctagonError

    Octagon::size

    fn Octagon::size(self : Octagon) -> Int

    Octagon::subset_of

    fn Octagon::subset_of(self : Octagon, other : Octagon) -> Bool raise OctagonError

    Octagon::to_box

    fn Octagon::to_box(self : Octagon) -> Box raise OctagonError

    Forget every relation and keep only the independent intervals.

    Octagon::to_text

    fn Octagon::to_text(self : Octagon) -> String raise OctagonError

    Serialise a non-empty domain as a parseable constraint text. The empty text denotes the top domain. Bottom has no finite conjunction and raises Invalid.

    Octagon::widen

    fn Octagon::widen(self : Octagon, next : Octagon) -> Octagon raise OctagonError

    Standard matrix widening. Preserve this raw result as the next left operand. Closing it between widen calls can destroy the finite-chain guarantee. Query methods close a copy without modifying this representation.

    Octagon::witness

    fn Octagon::witness(self : Octagon) -> Array[Int64]? raise OctagonError

    Deterministically fix one variable at a time using integer tight closure. A concrete witness is checked against the original domain before return.

    Term

    pub(all) struct Term {
    variable : Int
    sign : Int
    } derive(Eq,
    Debug
    ,
    ToJson
    )

    A signed variable term. Sign must be +1 or -1.

    Transfer

    pub(all) enum Transfer {
    Guard(Array[Constraint])
    Assign(Int, Term, Int64)
    Set(Int, Int64)
    Forget(Int)
    } derive(
    Debug
    )

    Sequential transfer operations over integer relations.

    Verdict

    pub enum Verdict {
    Vacuous
    Proven
    Refuted(Array[Int64])
    } derive(
    Debug
    ,
    ToJson
    )

    Proven means implication over the abstract state, not concrete reachability.

    analyze_blocks

    fn analyze_blocks(entry : Octagon, blocks : Array[Block], max_steps? : Int, widen_after? : Int) -> CfgResult raise OctagonError

    Bounded worklist analysis over a small control-flow graph. Every block is analysed with the octagon domain; joins happen at successors and widening starts after widen_after visits of the same successor. The result keeps partial states when the step budget runs out, exactly like the loop analysis, so callers must check status.

    analyze_loop

    fn analyze_loop(entry : Octagon, conditions : Array[Constraint], body : Array[Transfer], max_iterations? : Int, widen_after? : Int, narrowing_steps? : Int) -> LoopResult raise OctagonError

    Analyze a single while-loop with deterministic widening and bounded narrowing. BudgetExhausted states are partial iterates, never certified invariants.

    bottom

    fn bottom(n : Int) -> Octagon raise OctagonError

    box_bottom

    fn box_bottom(n : Int) -> Box raise OctagonError

    box_join_all

    fn box_join_all(states : Array[Box]) -> Box raise OctagonError

    Least box containing every state in a non-empty compatible family.

    box_meet_all

    fn box_meet_all(states : Array[Box]) -> Box raise OctagonError

    Exact intersection of a non-empty compatible family of boxes.

    box_top

    fn box_top(n : Int) -> Box raise OctagonError

    explain_conflict

    fn explain_conflict(n : Int, constraints : Array[Constraint], max_checks? : Int) -> Conflict? raise OctagonError

    Returns an inclusion-minimal inconsistent subset of original constraint indices. This is not a minimum-cardinality subset; work is explicitly budgeted.

    from_constraints

    fn from_constraints(n : Int, constraints : Array[Constraint]) -> Octagon raise OctagonError

    join_all

    fn join_all(states : Array[Octagon]) -> Octagon raise OctagonError

    Least octagonal upper bound of a non-empty family of compatible states.

    lower

    fn lower(i : Int, value : Int64) -> Constraint

    meet_all

    fn meet_all(states : Array[Octagon]) -> Octagon raise OctagonError

    Exact intersection of a non-empty family of compatible states.

    negative

    fn negative(i : Int) -> Term

    parse_constraints

    fn parse_constraints(dimensions : Int, input : String) -> Array[Constraint] raise OctagonError

    Parse a small line-oriented constraint language for the integer octagon domain. Statements are separated by newlines or semicolons; '#' starts a comment. Supported forms:

    x0 in [0, 100] x0 <= 100 x0 >= 0 x0 + x1 <= 100 x0 - x1 <= 2 -x0 + x1 <= 2

    Dimensions are supplied by the caller; all indices and bounds are validated.

    positive

    fn positive(i : Int) -> Term

    process_batch_json

    fn process_batch_json(input : String) -> String

    Independent results for up to 64 requests, including per-item errors.

    process_json

    fn process_json(input : String) -> String

    Pure bounded JSON entry. Duplicate object keys are rejected by the core parser.

    relation

    fn relation(a : Term, b : Term, bound : Int64) -> Constraint

    render_constraint

    fn render_constraint(c : Constraint) -> String

    Human-readable form of one constraint, using the same signed-sum syntax as Octagon::render. Bounds are printed exactly as stored.

    satisfies

    fn satisfies(values : Array[Int64], c : Constraint) -> Bool raise OctagonError

    Direct evaluation of a concrete integer vector, without solving or closure.

    top

    fn top(n : Int) -> Octagon raise OctagonError

    upper

    fn upper(i : Int, value : Int64) -> Constraint

    verify_conflict

    fn verify_conflict(n : Int, constraints : Array[Constraint], evidence : Conflict) -> Bool raise OctagonError

    Rebuilds subsets from original inputs, checking inconsistency and every deletion.

    verify_invariant

    fn verify_invariant(entry : Octagon, candidate : Octagon, conditions : Array[Constraint], body : Array[Transfer]) -> Bool raise OctagonError

    Re-check initialization and preservation, independently of iteration status.