cairndom

    Portable control-flow dominance, frontiers, loops and exit-path analysis.

    graph
    dominators
    compiler
    control-flow
    Download zip
    Author
    Version
    0.8.1
    License
    Apache-2.0
    Last updated
    1 hour ago
    Downloads
    63

    No dependencies

    #CairnDom

    CairnDom 是纯 MoonBit 控制流图分析基础库,提供支配树、支配边界、后支配关系、控制依赖、自然循环、强连通分量、变量活跃性、按使用点的值来源解释和 SSA 候选位置规划。它可以作为编译器、静态分析器及图工具的公共算法组件。命令行工具直接读取语言无关的图文件,生成可供人工核对或程序消费的 JSON 与 DOT。

    例如,图中的两个分支分别定义一个变量,SDK 可根据迭代支配边界找出 SSA 的 phi 候选位置。CLI 则直接指出分支汇合点、循环头、回边来源、不可达节点,以及哪些可达节点没有到达声明出口的路径。

    #运行

    使用官方 MoonBit 工具链,最低支持 moonc 0.10.20。本版验证的精确版本为 0.10.20+65efd5b93。纯库支持 Wasm GC 和 JavaScript。文件 CLI 要求 Node.js 22.16+。

    moon build --target js --release --deny-warn node _build/js/release/build/cmd/main/main.js analyze examples/branch-loop.json node _build/js/release/build/cmd/main/main.js analyze examples/branch-loop.json --format json-summary node _build/js/release/build/cmd/main/main.js analyze examples/branch-loop.json --format dot --out graph.dot node _build/js/release/build/cmd/main/main.js plan-ssa examples/ssa-branch.json node _build/js/release/build/cmd/main/main.js plan-ssa examples/ssa-branch.json --out phi-plan.json node _build/js/release/build/cmd/main/main.js query examples/queries.json node _build/js/release/build/cmd/main/main.js trace-values examples/value-origins.json node _build/js/release/build/cmd/main/main.js trace-values examples/value-origins.json --out value-origins.json

    样例报告中,left 和 right 的支配边界都是 join,head 与 body 形成一个以 head 为头的自然循环,dead 不可达。蓝色虚线 DOT 边是直接支配关系,普通边保留原始控制流。DOT 是图描述文件,可由支持该格式的工具进一步渲染。

    plan-ssa 的样例中,两个分支定义 value 与 unused,汇合块仅使用 value 和 parameter。输出会为 value 在 join 安排候选,为未使用的 unused 删除候选,并将 parameter 列入 entry_values_required。报告的 status 为 locations_only,其中同时给出各块活跃集合和按变量分组的候选;不会生成重命名后的指令或可执行程序。该命令只输出 JSON,并复用相同的输入校验与新文件独占发布约定。

    trace-values 读取同一 cairndom.program.v1 格式,解释每个可达使用点的可能来源。新样例中只有 left 分支定义 value,因此 join 的使用既可能来自 left,也可能需要原始入口值;parameter 需要调用方提供入口值。join 随后定义 value,所以 tail 的使用只来自 join。dead 被列入不可达块,不参与来源。这可以帮助分析器定位需要参数或初值的具体使用块。

    不传 --out 时结果写 stdout。错误为 stderr 上的 JSON,退出码 2。退出码 0 表示成功生成分析,图中仍可能存在不可达节点、多入口循环或无法到达出口的节点。

    标准输出处理写入回调、背压和流错误;写出时接收端已关闭等可观测 I/O 故障返回 2。失败之前可能已写出报告前缀,管道输出不具有 --out 新文件发布的原子性。标准错误也无法写入时仍保留退出码 2。

    --out 的目标必须是新文件,父目录须已存在且支持硬链接。完整报告先写入同目录暂存区并同步,再独占发布,拒绝覆盖输入及已有文件。中断或清理失败可能留下 .cairndom-* 暂存目录。文件操作面向可信本地目录,时间与身份复查提供顺序观测。

    #输入与分析语义

    { "schema": "cairndom.graph.v1", "nodes": ["entry", "left", "right", "join", "exit"], "entry": "entry", "exits": ["exit"], "edges": [["entry","left"], ["entry","right"], ["left","join"], ["right","join"], ["join","exit"]] }

    节点 ID 大小写敏感,长 1 到 64,只接受 ASCII 字母、数字、下划线、点和连字符。入口必须存在,出口必须是没有出边的节点。支持空出口列表、自循环、一般有向环和不可约图。重复节点、重复边、未知引用、未知 JSON 字段及重复键会报错。

    最多支持 512 个节点、8,192 条边。CLI 输入为普通 UTF-8 文件,最多 2 MiB,输出最多 16 MiB。符号链接路径和特殊文件会被拒绝。节点与集合按输入节点索引排序,固定图的输出确定。

    SDK 构建或编辑图后,可用 graph_json_text(graph) 生成同一 cairndom.graph.v1 格式,再交给 parse_graph 或文件 CLI。导出前会校验图,保留节点、边和出口的输入顺序;分析报告本身是另一种格式,不应当作原图重新导入。

    支配关系仅覆盖入口可达子图。入口自身的直接支配节点为空,不可达节点也为空,应同时检查 reachable。

    后支配使用虚拟出口,仅针对入口可达且最终到达声明出口的有限路径。报告以 can_reach_exit 和 postdominator_is_virtual_exit 区分无出口路径与虚拟父节点。这种分析不会证明所有执行都终止,分支进入永久循环时尤其需要保留该范围解释。控制依赖采用同一有限出口路径范围。

    control_dependence_witnesses(graph) 返回造成控制依赖的原始分支边。JSON 报告中的 control_witnesses 保留 controller、successor 和 dependent,可区分同一分支的不同出口,也能解释循环的自控制依赖;该信息同样遵守有限出口路径范围。

    边级证据上限为 65,536 条。超过上限时 SDK 报错;JSON 报告保留按索引排序的前缀,并将 control_witnesses_complete 标为 false,节点级控制依赖仍完整。需要完整边级证据的调用方必须检查此标志。这个上限避免密集分支图生成数百万条重复展开记录。

    如果只需要节点级分析,使用 analyze --format json-summary 或快照的 summary_json_text()。摘要使用独立格式 cairndom.analysis-summary.v1,保留可达性、支配关系、控制依赖、自然循环和强连通分量,跳过边级证据的计算与输出。密集图的完整报告若因边级证据过大而无法导出,摘要仍可能适用。两种 JSON 输出都受各自入口的 16 MiB 上限约束。

    自然循环由“循环头支配回边来源”定义,同一头的回边合并。多入口 SCC 会单独标记,它们可能没有自然循环头。SCC 的 multiple_entries 只描述该分量的入口数,完整的嵌套不可约性分类仍属后续工作。

    SDK 的 loop_boundaries(graph) 为每个自然循环列出进入边、离开边和返回循环头的回边,按端点索引排序,排除不可达前驱。嵌套循环分别计算边界;包含图入口的循环不会凭空添加进入边。没有离开边仅表示图结构,不构成终止性证明。展开总量限制为 65,536 个边记录,超限会报错,避免返回不完整边界。

    #SDK

    moon add Novanke/cairndom@0.8.1

    在调用方 moon.pkg 中导入 "Novanke/cairndom" @dom。可直接构建 Graph,或调用 parse_graph。核心入口为 analyze,也可单独调用 dominators 或 postdominators。图边使用节点数组索引。

    let result = @dom.analyze(graph)
    let required = @dom.dominates(result.forward, entry_index, target_index)
    let phi_candidates = @dom.iterated_frontier(result.forward, definition_indices)

    iterated_frontier 可接收调用方提供的 live_in 节点做剪枝。该接口计算候选位置,调用方负责变量定义、活跃性和具体 IR。后支配树中的虚拟出口索引为 graph.nodes.length()。分析结果拥有输入数组的副本。序列化函数要求结果仍保持 analyze 生成的有效结构,编辑图后应再次分析。

    需要先查看完整分析、再导出同一份 JSON/DOT 的编辑器或 SDK 程序,可以保存不可变快照:

    let saved = @dom.prepare_analysis(graph)
    let inspected = saved.analysis()
    let json = saved.json_text()
    let dot = saved.dot_text()

    prepare_analysis 只调用一次完整 analyze。analysis() 深层复制图、两棵支配树及边界集合、循环、强连通分量和控制依赖;每次读取都可独立修改。修改原始图或检查副本,都不会改变快照之后导出的内容。JSON 与 DOT 继续使用原有格式;导出时仍会生成序列化内容和边级证据,并非缓存字符串。需要分析修改后的图时,应重新调用 prepare_analysis,而不是修改检查副本。

    快照的 json_text() 限制为 16 MiB,超限报错时仍可检查分析并导出 DOT;当前图尺寸上限可保证 DOT 小于该限制。边级证据保留原有的有界前缀与 control_witnesses_complete 标志,需要完整证据时仍须检查该标志。AnalysisSnapshot 是进程内对象,没有把报告重新解析为快照的接口。现有可修改的 Analysis、旧序列化接口和 CLI 行为保持不变。examples/sdk 会修改原图与检查副本,再断言已保存的两种导出保持一致。

    完整 JSON 的快照和 CLI 入口在追加每段输出前核对剩余字节,超限时停止序列化。SDK 可用 saved.json_text_limit(bytes) 指定 0 到 16 MiB 的预算,刚好达到预算也可导出。CLI 的 16 MiB 包含末尾换行,整份报告生成成功后才写入文件或标准输出。原有的 analysis_json_text(result) 继续提供无字节预算的字符串接口。

    公开支配查询会先检查树的完整结构,拒绝父链成环、断链、无效根和损坏的边界集合。结构检查无法证明手工填写的支配边界与原图在数学上相符;编辑图后应重新调用 analyze 或 dominators。

    反复查询同一棵树时,用 index_dominance(tree) 一次校验并建立不可变快照:

    let index = @dom.index_dominance(result.forward)
    let yes = index.dominates(ancestor_index, target_index)
    let common = index.nearest_common([left_index, right_index])

    索引按 DFS 区间判断支配,单次为 O(1);公共支配节点使用倍增祖先表,k 个操作数为 O(k log n)。索引不暴露内部数组,原树之后的修改不会影响已有答案;图变化后需重新分析和建立索引。这是算法复杂度说明,不是运行时间承诺。空集合或含不可达节点的最近公共查询返回 None,越界索引始终报错。后支配索引可返回虚拟出口索引。

    只需要后支配关系或分支的公共后继区域时,可以直接建立后支配索引:

    let post = @dom.index_dominance(@dom.postdominators(graph))
    let shared_region = post.nearest_common([left_index, right_index])

    postdominators(graph) 保留完整图校验,但不计算正向支配树、控制依赖、循环或强连通分量。结果与 analyze(graph).post 相同,继续采用前述有限出口路径语义。根索引是 graph.nodes.length(),数组长度是原节点数加一;没有入口可达的声明出口时,仅虚拟根可达。不可达的出口或前驱不会参与结果。返回数组独立持有数据,可以交给 index_dominance 再做多次查询。这里缩小了实际执行的分析范围,不作未经测量的耗时承诺。

    文件批量查询使用 cairndom.queries.v1:包含 graph、tree(forward 或 post)和 queries。每项为 {"operation":"dominates","ancestor":"entry","node":"join"} 或 {"operation":"nearest_common","nodes":["left","right"]}。query 命令只建立一次索引;样例中两个分支的最近公共支配节点是 entry,join 和 exit 的是 join。JSON 入口也可直接通过 SDK 的 query_json_text 调用。

    tree: "post" 的 SDK JSON 与 CLI 查询现在直接使用 postdominators,已有输入格式、输出格式、顺序及边界限制保持兼容;analyze 仍返回完整分析。

    查询最多 4,096 项、合计 16,384 个操作数,输入 2 MiB,输出 16 MiB。操作数使用原图 ID,支持重复节点和空列表;不接受虚拟出口作为输入 ID。found: false 表示没有结果,found: true 且 virtual_exit: true 表示结果是后支配虚拟出口,二者不能混同。后支配继续采用前述有限出口路径范围。

    FlowProgram 为每个块提供变量定义和使用集合,liveness(program) 返回按变量索引排序的 live_in / live_out。这里的 uses 表示块内该变量首次定义之前的使用,同一变量可同时出现在使用和定义中。活跃性覆盖全部入口可达路径,包括永久循环;不可达块的结果为空,声明出口不会裁掉这些数据流路径。

    最多允许 512 个变量和 16,384 个定义/使用关联。变量 ID 与节点 ID 使用相同语法;定义、使用的行数必须等于图节点数,每行的变量索引需合法且不重复。返回集合独立持有数组,编辑输入不会改变已有结果。

    程序事实的文件格式为 cairndom.program.v1,通过 parse_program / program_json_text 导入导出:

    {"schema":"cairndom.program.v1", "graph":{"schema":"cairndom.graph.v1","nodes":["entry","exit"],"entry":"entry","exits":["exit"],"edges":[["entry","exit"]]}, "variables":["value"], "blocks":[{"node":"entry","defines":["value"],"uses":[]},{"node":"exit","defines":[],"uses":["value"]}]}

    blocks 中未列出的节点表示空定义/使用集合,重复块或未知 ID 会报错。每个列出的块必须包含 node、defines 和 uses。导出按图节点和声明变量顺序排列事实,不修改调用方数组;导入与导出都限制为 2 MiB,以保持文件可重新读取。

    plan_ssa(program) 将活跃性与迭代支配边界连接起来,对每个变量返回定义块、活跃入口块和剪枝后的 phi_nodes。未使用的变量不产生候选,不可达块的事实不参与规划。SsaPlan 保留输入程序的完整副本。

    每项中的 requires_entry_value 表示变量在入口块的本地定义之前就需要值。调用方应提供参数或初始值,或按源语言规则报告缺少初始化。该工具生成候选位置,不推断语句顺序、不重命名变量、不改写 IR,也不保证一个程序已经转换为可执行的 SSA。

    需要“查看规划后保存同一份报告”的 SDK 程序,可保存不可变快照:

    let saved = @dom.prepare_ssa(program)
    let inspected = saved.plan()
    // 查看 inspected.placements、inspected.liveness 和 inspected.program。
    let report = saved.json_text()

    prepare_ssa 只计算一次活跃性和 phi 规划,内部独立持有完整结果。plan() 每次返回可修改的深层副本;修改原始程序或该副本,都不会改变快照及其 JSON。json_text() 序列化同一次计算,保留 cairndom.ssa-plan.v1 格式和 16 MiB 上限,不会重新规划。大报告仍可通过 plan() 检查,导出超过上限时明确报错。

    ssa_plan_json_text(program) 仍是按当前程序即时计算并导出的便捷入口。快照用于保存已查看的结果,不用于导出对检查副本所做的修改;图或变量事实改变后,需要新的规划时应重新调用 prepare_ssa。快照是进程内对象,JSON 报告没有新增反序列化为规划对象的接口。完整的 examples/ssa_sdk 会修改原始输入与检查副本,再断言已保存的报告保持一致。

    按使用点查看可能的最后定义块和入口值,可使用独立的值来源分析:

    let origins = @dom.trace_values(program)
    let uses = origins.uses()
    let saved_program = origins.program()
    let report = origins.json_text()

    每个 UseOrigins 包含使用块索引 node、变量索引 variable、排序后的来源块 definitions 和 requires_entry_value。结果按块和变量索引排序,索引对应 origins.program() 的原始节点与变量顺序。program() 和 uses() 都返回独立可修改的副本;修改输入或副本,不会改变已保存结果及其 JSON。is_reachable(node) 可区分不可达块与没有使用的可达块,越界索引报错。

    来源沿所有入口可达路径计算,包含永久循环;声明出口不会裁掉这些路径。同一块的使用发生在本地定义之前,但本块上一轮循环的定义可以成为来源。后续定义会阻断更早定义。requires_entry_value 表示原始入口值可能到达这个使用点,调用方应提供参数或初值,或按自身语言规则处理;它不直接证明源程序存在未初始化错误。这里不分析值、分支条件、别名或语句顺序,也不转换 IR。

    总来源关系上限为 65,536,每个使用点的入口值标志也计作一条关系;超过上限整体报错,不返回截断结果。每个使用点的反向搜索使用 O(n) 临时空间,工作量为 O(n + e),另需存储完整结果;不承诺未经测量的耗时。JSON 为 cairndom.value-origins.v1,包括 uses、unreachable_blocks、source_relation_count 和 source_relation_limit,输出仍限制为 16 MiB。CLI 沿用新文件独占发布约定,分析失败时不会留下半份目标报告。

    完整示例会执行断言并输出分析与 phi 候选点。

    moon run examples/sdk --target wasm-gc --release --deny-warn moon run examples/sdk --target js --release --deny-warn moon run examples/ssa_sdk --target wasm-gc --release --deny-warn moon run examples/ssa_sdk --target js --release --deny-warn moon run examples/query_sdk --target wasm-gc --release --deny-warn moon run examples/query_sdk --target js --release --deny-warn

    #验证与维护

    moon fmt --check moon check --target wasm-gc --deny-warn moon check --target js --deny-warn moon test --target wasm-gc --deny-warn moon test --target js --deny-warn moon build --target js --release --deny-warn python scripts/verify_cli.py python scripts/verify_ssa_cli.py python scripts/verify_queries.py python scripts/verify_stdout.py python scripts/verify_value_origins.py

    独立核对方法、复现结果及后续方向见 验证记录。CI 在 Windows/Linux 上执行双后端检查、测试、示例和真实文件核对。

    独立的节点删除、集合方程、正向定义来源状态遍历和用例生成位于 MoonBit 的 verification/reference,不调用生产分析算法生成预期答案。Python 只负责真实文件、进程、管道及故障注入适配;四个文件验证入口共享同一输出契约,另有标准输出验证入口。moon build --target js --release 同时构建参考命令,验证脚本也接受 --oracle 指定它的位置。生产库、测试、独立验证器与主机适配的语言统计分别记录在 语言构成说明。

    #算法与来源

    采用 Cooper–Harvey–Kennedy 支配算法、迭代 DFS、反向图与虚拟出口、Kosaraju SCC 和经典自然循环构造。实现依据算法定义独立编写,算法本身有既有研究基础。运行时只依赖 MoonBit 标准库。

    该项目与作者已有的 JSON 迁移、小册子拼版、BitTorrent 元数据和套件备料项目用途及代码独立。MoonBit 生态已有通用图及编译器内部的部分支配分析实现,本项目的交付重点是统一的语言无关 CFG API、出口范围明确的分析和可直接运行的离线工具。公开检索无法覆盖全部未公开参赛资料。

    项目使用 AI 辅助实现及技术文档编写,采用 Apache-2.0 许可证。算法参考及生态对照见 来源说明。

    GraphError

    pub(all) suberror GraphError {
    Invalid(String)
    } derive(
    Debug
    )

    Analysis

    pub(all) struct Analysis {
    graph : Graph
    forward : Dominance
    post : Dominance
    loops : Array[NaturalLoop]
    components : Array[Component]
    control_dependencies : Array[Array[Int]]
    }

    post uses a virtual exit at index graph.nodes.length(). It describes finite paths reaching a declared exit and does not prove program termination.

    AnalysisSnapshot

    type AnalysisSnapshot

    An owned full graph analysis. Inspection copies cannot change its saved JSON/DOT exports; the underlying graph analysis is computed only once.

    AnalysisSnapshot::analysis

    Return an independently mutable inspection copy of every graph/tree, loop, component and control array. Edits affect neither later reads nor exports.

    AnalysisSnapshot::dot_text

    fn AnalysisSnapshot::dot_text(self : AnalysisSnapshot) -> String

    Serialize the same saved analysis as DOT, without recomputing analyze. Validated node/edge limits bound DOT output below the JSON export limit.

    AnalysisSnapshot::json_text

    fn AnalysisSnapshot::json_text(self : AnalysisSnapshot) -> String raise GraphError

    Serialize the saved analysis using the existing cairndom.analysis.v1 format. Witness expansion retains its completeness flag and bounded prefix. Exports exceeding 16 MiB raise GraphError without changing the saved analysis.

    AnalysisSnapshot::json_text_limit

    fn AnalysisSnapshot::json_text_limit(self : AnalysisSnapshot, limit : Int) -> String raise GraphError

    Write the same full report with an inclusive UTF-8 byte limit, excluding any final newline added by the caller. Accepts budgets from 0 to 16 MiB. The writer stops at the first over-budget fragment and returns no report.

    AnalysisSnapshot::summary_json_text

    fn AnalysisSnapshot::summary_json_text(self : AnalysisSnapshot) -> String raise GraphError

    Export node-level analysis as cairndom.analysis-summary.v1. The summary keeps node-level control dependencies and skips edge-witness expansion. Exports exceeding 16 MiB raise GraphError.

    Component

    pub(all) struct Component {
    members : Array[Int]
    entry_nodes : Array[Int]
    cyclic : Bool
    multiple_entries : Bool
    }

    entry_nodes include the graph entry and members with external predecessors. Multiple entries diagnose this SCC. They do not classify every nested cycle.

    ControlWitness

    pub(all) struct ControlWitness {
    controller : Int
    successor : Int
    dependent : Int
    } derive(Eq,
    Debug
    )

    An original edge controller -> successor makes dependent control-dependent on controller. Indices refer to the analyzed graph's nodes.

    ControlWitness::equal

    ControlWitness::not_equal

    fn ControlWitness::not_equal(x : ControlWitness, y : ControlWitness) -> Bool

    Dominance

    pub(all) struct Dominance {
    root : Int
    reachable : Array[Bool]
    immediate : Array[Int?]
    frontiers : Array[Array[Int]]
    }

    root is reachable and has no immediate parent. Unreachable nodes also have no parent, so consult reachable. Frontiers and arrays are in node order.

    DominanceIndex

    type DominanceIndex

    Opaque snapshot of a structurally checked dominator tree. Arrays are owned privately: later mutations of the input tree cannot change indexed answers.

    DominanceIndex::dominates

    fn DominanceIndex::dominates(self : DominanceIndex, ancestor : Int, node : Int) -> Bool raise GraphError

    Constant-time interval containment after construction. Unreachable operands yield false, including reflexive queries. Both indices are checked first.

    DominanceIndex::immediate_parent

    fn DominanceIndex::immediate_parent(self : DominanceIndex, node : Int) -> Int? raise GraphError

    Returns None for the root and for unreachable nodes.

    DominanceIndex::is_reachable

    fn DominanceIndex::is_reachable(self : DominanceIndex, node : Int) -> Bool raise GraphError

    Reachability from this tree's root. For postdominance this means a declared exit is reachable within the documented finite-exit-path scope.

    DominanceIndex::nearest_common

    fn DominanceIndex::nearest_common(self : DominanceIndex, nodes : Array[Int]) -> Int? raise GraphError

    Nearest shared dominator of all supplied nodes, O(k log n) after indexing. Empty input or any unreachable operand gives None. Every index is validated, even after an unreachable operand. Postdominance can return its virtual root.

    DominanceIndex::node_count

    fn DominanceIndex::node_count(self : DominanceIndex) -> Int

    Number of slots, including unreachable vertices and any synthetic exit.

    DominanceIndex::root

    fn DominanceIndex::root(self : DominanceIndex) -> Int

    Root index, including the synthetic exit for a postdominator snapshot.

    FlowProgram

    pub(all) struct FlowProgram {
    graph : Graph
    variables : Array[String]
    definitions : Array[Array[Int]]
    uses : Array[Array[Int]]
    }

    Block-level variable facts indexed by graph node, with variable indices into variables. A use is a use before any local definition of that variable. Thus a variable may appear in both a block's uses and definitions.

    Graph

    pub(all) struct Graph {
    nodes : Array[String]
    edges : Array[(Int, Int)]
    entry : Int
    exits : Array[Int]
    }

    Directed graph. Edges use indices into nodes. Exits must be terminal nodes.

    Liveness

    pub(all) struct Liveness {
    reachable : Array[Bool]
    live_in : Array[Array[Int]]
    live_out : Array[Array[Int]]
    }

    Backward may-liveness on all entry-reachable paths, including paths in permanent cycles. Unreachable blocks have empty sets. Sets contain variable indices in input variable order, and all result arrays are independently owned.

    LoopBoundary

    pub(all) struct LoopBoundary {
    header : Int
    entering_edges : Array[(Int, Int)]
    leaving_edges : Array[(Int, Int)]
    back_edges : Array[(Int, Int)]
    } derive(Eq,
    Debug
    )

    Original entry-reachable edges entering, leaving, and returning to the header of a natural loop. Each edge list is sorted by source then target index.

    LoopBoundary::equal

    LoopBoundary::not_equal

    fn LoopBoundary::not_equal(x : LoopBoundary, y : LoopBoundary) -> Bool

    NaturalLoop

    pub(all) struct NaturalLoop {
    header : Int
    latches : Array[Int]
    members : Array[Int]
    parent : Int?
    }

    PhiPlacement

    pub(all) struct PhiPlacement {
    variable : Int
    definitions : Array[Int]
    live_in : Array[Int]
    phi_nodes : Array[Int]
    requires_entry_value : Bool
    }

    Locations for one variable, not renamed instructions or executable SSA. requires_entry_value means the variable is live before the first block's local definitions: the caller must supply a parameter/initial value or report a missing initialization according to the source language's own rules.

    SsaPlan

    pub(all) struct SsaPlan {
    program : FlowProgram
    liveness : Liveness
    placements : Array[PhiPlacement]
    }

    A self-contained input snapshot plus backward liveness and pruned IDF sites.

    SsaSnapshot

    type SsaSnapshot

    An owned SSA planning result. Only defensive copies are exposed; JSON export always describes the original computation, not edits to an inspection copy.

    SsaSnapshot::json_text

    fn SsaSnapshot::json_text(self : SsaSnapshot) -> String raise GraphError

    Export this exact saved computation as cairndom.ssa-plan.v1 without running liveness or phi planning again. The existing 16 MiB report limit applies.

    SsaSnapshot::plan

    fn SsaSnapshot::plan(self : SsaSnapshot) -> SsaPlan

    Return an independently mutable inspection copy. Every nested array is copied, including the graph, facts, liveness and per-variable placements. Editing this value neither changes later reads nor the exported report.

    UseOrigins

    pub(all) struct UseOrigins {
    node : Int
    variable : Int
    definitions : Array[Int]
    requires_entry_value : Bool
    } derive(Eq,
    Debug
    )

    Possible last-definition blocks for a use before the block's local defs. requires_entry_value records a possible caller-supplied incoming value; it does not establish a source-language missing-initialization error.

    UseOrigins::equal

    fn UseOrigins::equal(UseOrigins, UseOrigins) -> Bool

    UseOrigins::not_equal

    fn UseOrigins::not_equal(x : UseOrigins, y : UseOrigins) -> Bool

    ValueOrigins

    type ValueOrigins

    Privately owned input and complete per-use results. Inspection methods return defensive copies so later caller edits cannot alter saved answers.

    ValueOrigins::is_reachable

    fn ValueOrigins::is_reachable(self : ValueOrigins, node : Int) -> Bool raise GraphError

    Entry reachability, independent of declared exits or eventual termination.

    ValueOrigins::json_text

    fn ValueOrigins::json_text(self : ValueOrigins) -> String raise GraphError

    Serialize the saved, complete result using original block/variable IDs. Inspection-copy edits cannot change this report. Output is limited to 16 MiB.

    ValueOrigins::program

    fn ValueOrigins::program(self : ValueOrigins) -> FlowProgram

    Return an independently mutable input snapshot, including all graph arrays and nested definition/use rows. Editing it cannot change these origins.

    ValueOrigins::uses

    Return complete origins in node/variable order, copying each definitions array as well as the outer list. Unreachable uses are absent.

    analysis_dot

    fn analysis_dot(result : Analysis) -> String

    A DOT graph showing original edges and dashed immediate-dominator edges. Node IDs use the validated ASCII identifier grammar.

    analysis_json_text

    fn analysis_json_text(result : Analysis) -> String

    Report indices as original string IDs, with explicit reachability and exit scope. A virtual postdominator parent is distinguished from no exit path.

    analyze

    fn analyze(input : Graph) -> Analysis raise GraphError

    Analyze the entry-reachable graph. Postdominance and control dependence are conditioned on finite paths reaching the explicitly declared terminal exits.

    control_dependence_witnesses

    fn control_dependence_witnesses(graph : Graph) -> Array[ControlWitness] raise GraphError

    Return edge-level witnesses sorted by controller, successor, then dependent. As with analyze, control dependence is conditioned on finite paths reaching declared terminal exits. Unreachable edges and edges without such paths are excluded; this does not establish termination of every execution. Raise GraphError if more than 65,536 witnesses would be returned.

    dominates

    fn dominates(tree : Dominance, ancestor : Int, node : Int) -> Bool raise GraphError

    Reflexive dominance is defined only for nodes reachable from the root. Public mutable trees are checked structurally before answering any query.

    dominators

    fn dominators(graph : Graph) -> Dominance raise GraphError

    Compute entry-rooted immediate dominators and dominance frontiers. Only paths reachable from entry participate; unreachable predecessors are ignored.

    graph_json_text

    fn graph_json_text(graph : Graph) -> String raise GraphError

    Serialize a validated graph to cairndom.graph.v1. Node, edge and exit order is preserved so SDK-built/edited graphs can be saved and consumed by the CLI.

    index_dominance

    fn index_dominance(tree : Dominance) -> DominanceIndex raise GraphError

    Validate a public tree once, then index its parent topology. Frontier validity is structural only, as with dominates; indexing cannot establish that supplied dominance/frontier sets correspond to an original graph.

    iterated_frontier

    fn iterated_frontier(tree : Dominance, definitions : Array[Int], live_in? : Array[Int]?) -> Array[Int] raise GraphError

    Iterated dominance frontier, for example SSA phi-placement candidates. live_in restricts propagation to the caller's live-in nodes when provided. This identifies locations only. It does not rewrite an IR or infer liveness.

    liveness

    fn liveness(program : FlowProgram) -> Liveness raise GraphError

    Compute the least fixed point live_out[b] = union live_in[successor] and live_in[b] = uses[b] union (live_out[b] minus definitions[b]). Only reachable successors participate; declared exits do not restrict this analysis. The solver uses iterative backward propagation, with at most one queued propagation per reachable block and variable, and never recurses.

    loop_boundaries

    fn loop_boundaries(graph : Graph) -> Array[LoopBoundary] raise GraphError

    Describe natural-loop boundaries in header order, excluding unreachable edges. A loop containing the graph entry has no synthetic entering edge. An empty leaving-edge list describes graph structure, not termination. Raise GraphError if the combined edge lists would exceed 65,536 pairs.

    parse_graph

    fn parse_graph(input : String) -> Graph raise GraphError

    Parse cairndom.graph.v1 with string node IDs and strict JSON keys.

    parse_program

    fn parse_program(input : String) -> FlowProgram raise GraphError

    Parse cairndom.program.v1 with a complete nested cairndom.graph.v1 graph. Each listed block requires node, defines and uses. Omitted nodes have empty facts; duplicate blocks, facts, IDs and unknown fields are rejected. Uses retain the FlowProgram convention of occurring before local definitions.

    plan_ssa

    fn plan_ssa(input : FlowProgram) -> SsaPlan raise GraphError

    Plan live-in-pruned phi sites on entry-reachable blocks. Unreachable facts are validated but do not affect the plan. Blocks' uses precede local defs. This does not infer statement ordering, rename variables or rewrite an IR.

    postdominators

    fn postdominators(input : Graph) -> Dominance raise GraphError

    Compute postdominance without forward dominators, control dependencies, loops or SCCs. Scope is finite paths from entry reaching declared terminal exits, exactly as analyze(graph).post; this is not a termination proof. The root is the virtual exit at graph.nodes.length(), and all arrays have one extra slot for it. With no reachable declared exit only that root is reachable. Returned arrays are independently owned.

    prepare_analysis

    fn prepare_analysis(graph : Graph) -> AnalysisSnapshot raise GraphError

    Compute and retain one full analysis. Serialization is deferred so a graph whose JSON exceeds the export limit remains inspectable and DOT-exportable.

    prepare_ssa

    fn prepare_ssa(program : FlowProgram) -> SsaSnapshot raise GraphError

    Validate and compute once, then retain the complete plan privately. Changes to the input program after construction do not affect this snapshot.

    program_json_text

    fn program_json_text(program : FlowProgram) -> String raise GraphError

    Serialize a validated FlowProgram as cairndom.program.v1. Every graph node gets a block in node order, and facts follow declared variable order. Sorting uses private copies and never mutates the caller's rows. Exports exceeding the parser's 2 MiB input limit are rejected so successful exports round trip.

    query_json_text

    fn query_json_text(input : String) -> String raise GraphError

    Answer a named cairndom.queries.v1 batch with one immutable tree index. Every query is checked before execution. Only original graph IDs are valid operands; a common virtual postdominator is reported with found=true, node=null and virtual_exit=true. Empty or unreachable sets have found=false. Input is limited to 2 MiB, 4096 queries and 16384 total node operands; each nearest_common list may contain at most 512 IDs, preserving order/duplicates.

    ssa_plan_json_text

    fn ssa_plan_json_text(program : FlowProgram) -> String raise GraphError

    Compute a fresh plan and serialize cairndom.ssa-plan.v1 using original IDs. The report contains phi locations and entry-value requirements, without IR rewriting or variable renaming. Unreachable input facts remain visible but contribute no liveness or placement results. Output is limited to 16 MiB.

    trace_values

    fn trace_values(input : FlowProgram) -> ValueOrigins raise GraphError

    Explain each entry-reachable use over all finite entry-to-use paths, including uses in permanent loops. Uses precede local definitions; a block's own definition can reach its use through a previous loop iteration. Results are ordered by node then variable, with definition blocks sorted by node index. At most 65,536 source/use relations are returned, counting each incoming-value flag as one source. Oversized complete results raise an error rather than returning a partial list. Each reverse search uses O(n) scratch space and O(n + e) work, without a block/variable/source state matrix.