# Structure
> **职责**：把 CFG、图事实和 canonical SSA 冻结成一个可直接执行的 `StructurePlan`。
>
> **不负责**：生成 HIR/AST、命名、可读性改写，或在后层重新选择结构候选。
## 入口与输出
```text
LoweredProto
-> Cfg / GraphFacts / DataflowFacts
-> Structure 内部 evidence
-> StructurePlan
-> StructureFacts {
outcome: Ready { plan, debug_bindings } | Failed(ProtoFailure),
children
}
```
入口是 `src/structure/analyze.rs::analyze_structure_proto`。proto tree 的调度采用显式
postorder frame：CFG、GraphFacts、DataflowFacts、StructureFacts 按 child 完成顺序回填父节点，
不会把词法深度映射到 Rust 调用栈；child fact 数量不一致直接返回结构错误。branch、loop、短路、
scope 和不可规约 SCC 只是 Structure 内部 evidence；冲突消解后不再暴露给 HIR。
GraphFacts 则保留通用 SCC partition 和稠密的 cyclic-block 查询：不可规约
evidence 与 HIR 的词法绑定共用这份图事实，不各自重做可达性扫描。
Dataflow 冻结后，Structure 还会建立 `DebugBindingFacts`：每个 source debug local 在其
`start_pc` 对应的 low-instruction 边界查询 reaching canonical SSA，而不是回到最早 producer。
这使跨多条指令完成的 table/closure 初始化仍能绑定到源码生命周期入口。多个源码 scope
若竞争同一 SSA，只在 dump 中保留冲突证据，不向 HIR 发布名字候选；compiler-internal
local 不进入这张表。
proto 的 child 已全部完成后才构造并验证当前 final plan。Strict 下任一错误立即返回；Permissive
下当前节点改为 `Failed(ProtoFailure)`，其中最后完成层固定为 Dataflow，并用
`structure/diagnostic.rs` 序列化该 proto 的 low-IR、读写集合和 phi 候选。失败节点不拥有半成品
`StructurePlan`，因此 HIR 不会消费未通过 validator 的 arena，也不会在后层重选候选。
跨 proto 的结果仍按词法 child slot 保持顺序；输入层的 `Arc` 共享只减少 immutable template
复制，不改变每个 slot 的 `ProtoRef`、capture provenance 或 HIR proto identity。异常 flat-DAG
展开在 parser 的 occurrence budget 截断，Structure 不接收未验证的部分树。
这里的恢复边界只覆盖 final Structure 分析。CFG、GraphFacts 和 Dataflow 在当前节点进入
Structure 之前必须完整成功；这些事实构建失败仍终止整个 chunk，因为此时无法构造可信的最后
完成产物。源码 proto 编号采用独立的稳定前序计数，不复用后续 HIR arena 下标；HIR 可能插入
synthetic composite proto，二者不能混为同一 identity。
## 模块布局
Structure 的逻辑 owner 与物理文件边界分开：父模块保存共享上下文和阶段顺序，子模块按
同一 owner 内的关注点组织，不复制 CFG、SSA、region arena 或校验状态。
```text
src/structure/
analyze.rs Structure 总调度与最终 facts 汇总
analyze/ debug binding、condition arc、value decision、loop continuation 等输入整理
branches.rs / branches/ fence、region、one-arm 与候选分类
loops.rs / loops/ natural loop、continue、repeat refine、shape 与 exit
phi_facts.rs / phi_facts/ incoming、ownership、branch arm、forward action 与安装
short_circuit/
branch_exit.rs branch-exit 总入口与共享工作区
branch_exit/ closed component/DAG、linear chain 与 guard 构建
common.rs Structure evidence 与 final plan 数据模型
common/plan_access.rs StructurePlan 的只读查询接口
plan.rs final plan 组装入口
plan/finalize.rs 最终 requirements、navigation 与 validator 收尾
plan/arena.rs region/container arena 共享上下文与构建调度
plan/arena/ payload、route、layout、loop rewrite、edge semantics 等主题
plan/loop_protocol.rs loop VM protocol 与 value-action 数据模型
plan/loop_protocol/ protocol 分析、迭代、repeat/generic-for、value action 与 finalize
plan/validate.rs validator 总入口
plan/validate/ region、edge、branch、loop、phi、label、cleanup 等不变量组
diagnostic.rs 无 debug feature 时也可用的恢复诊断 dump
```
`arena.rs`、`loop_protocol.rs` 和 `validate.rs` 的子模块共享各自父模块的私有类型；这种拆分
只是把同一阶段的规则按主题定位，不能把一次构建或一次验证变成多套可独立变更的事实源。
## 混合 Region / Island 模型
`StructurePlan` 是分层控制流图，不把所有 CFG 强压成树：
```text
containment tree
Sequence
Branch
Loop
Block
Unstructured island ---> island 内仍保留局部 CFG 边
```
- `Sequence / Branch / Loop / Block` 使用唯一父节点的 containment tree。
- 无法满足单入口和声明出口约束的最小闭合区域成为 `Unstructured` island。
- island 的 layout 可以包含普通 block 或已验证的 structured child。
- containment 决定唯一 ownership；island 内部允许多入口、多出口和回边。
- 可规约结构不会因为目标方言支持 `goto` 而被主动降级成 island。
- bytecode 无法区分源码 `goto` 与等价 loop/branch，因此不承诺保留原始拼写；只有
最终控制语义确实无法结构化时才保留 planned `Goto`。
## Final Plan
核心 arena 都使用稠密 newtype ID：
| `RegionId -> RegionPlan` | containment tree 与 island layout |
| `BlockRef -> Option<RegionId>` | 每个 reachable block 的唯一直接 owner |
| `BlockRef -> BlockTerminatorPlan` | 每个物理 block 的指令范围、终结指令与精确 successor edge |
| `EdgeRef -> EdgePlan` | 每条 CFG edge 的唯一 transfer、forward route 和 phi copies |
| `BranchPlanId / LoopPlanId / ConditionPlanId / ValueDecisionPlanId` | 已选且已规范化的语法和值决策 payload |
| `LabelPlanId -> LabelPlan` | Structure 预分配的 label、入口 cleanup 相对位置及 VM TBC scope barrier |
| `PhiId -> PhiPlan` | 每个 phi incoming 的唯一 value disposition |
| `InstrRef -> CleanupDisposition` | 每个 cleanup 的唯一 region/scope owner |
| `PlanRequirements` | 实际 transfer 推导出的语法能力与 unresolved 诊断 |
`RegionPlan` 的形状：
- `Block { block }`
- `Sequence { children }`
- `Branch { condition, then_arm, else_arm, continuation }`
- `ValueDecision { plan, continuation }`
- `Loop { preheader, control, body, normal_tail, exits }`
- `Unstructured { entry, entry_ports, exits, layout }`
`EdgePlan` 是控制与值动作的唯一来源：
- `Fallthrough`
- `BranchArm`
- `LoopBack`
- `Break`
- `Continue`
- `Return / TailCall`
- `Goto(LabelPlanId, GotoReason)`
- edge 同时执行的 canonical phi copies
VM-for 语法隐式消费的 control/binding copy 仍保留 canonical SSA 事实，但必须以精确
`EdgeCopyOrigin(edge, phi)` 冻结为 loop value-action 的 `elided` disposition。普通 body
回边可以同时保留业务 carried copy；不得为了隐藏 control copy 而吸收整条混合回边。
numeric index 与 binding 共槽且仍有源码 body use 时，preheader 的 `BodyPrologue` bridge
必须保留；只有 normal latch 上“目标为当前 header binding phi、来源为 VM-for control”
的精确 copy，才能在完成 escape 校验后交给 `for` 语法消费。下一轮的源码 body 先重新
执行该 bridge，因此不得把这条规则扩大到 preheader、exit 或同寄存器的普通 body def。
透明 jump pad 只能通过 plan 中冻结的 forward route 被跳过。route 上的 phi copy 必须按
执行顺序复合，不能把顺序赋值错误拼成并行赋值；被转发 pad 也不得在后续再次执行同一
value action。
## 构建阶段
### 1. 提取 evidence
复用 CFG、dom/postdom、canonical SSA 和方言 protocol recognizer，提取 natural loop、
branch、短路、cleanup 与不可规约 SCC。此阶段允许 evidence 重叠，但不得丢弃尚未拥有
最终 disposition 的 edge 或 phi incoming。
### 2. 规范化 containment
- GraphFacts 一次建立 SCC/cyclic-block 事实，并合并同 header 的全部
natural-loop backedge，只保留一份 union domain；Structure 不再重算 SCC，也不再
保存或重选逐 backedge 的 raw natural-loop candidate。
- 若同一 union domain 同时包含唯一 VM-for latch 与不执行该 latch 的 residual cycle，
Structure 允许用一次多源反向 partition 证明 `VM-for wrapper + structured cycle child`。
两者可以共享物理 entry，但每个 block 的直接 containment owner 仍唯一。例如 Luau
numeric-for body 入口同时是内层 `while` header 时，内层回边不能降成会推进迭代器的
`continue`。partition 无法形成严格包含关系或出现多个冲突 VM latch 时，不任选回边，
而是保守交给单一 merged loop / island。共享 header 的 residual 若无法通过通用 sibling
latch 布局判据，只有在它是严格可规约子域、不含唯一 VM latch，且全部边界出口精确
落到该 latch 时才能作为 child；numeric latch 是推进外层迭代器的唯一协议动作。
- 按 loop kind 冻结 `preheader / control / body / normal_tail / continuation` 分区。
- while 的 natural-loop domain 可能漏掉从正文条件进入、随后只抵达当前 continuation、
函数出口或永不退出的词法 arm。Structure 只在 arm 单入口、entry 支配全部 block、除唯一
入口边外没有额外 predecessor、没有未归属 residual，且任意边都不能回到已冻结 natural
domain 时将它收回 loop body；无出口的闭合 SCC 不得被放到 loop 外并用 goto 重新接入。
- while/numeric/generic-for 只有在全部语法正常出口汇入同一条无环尾链、且 body 存在
直达 continuation 的提前 break 时，才冻结 `normal_tail`。payload 同时记录 normal/early
exit edge，以及 tail 到 continuation 的完整 completion edge 集；最终 validator 用
region boundary 精确核对入口/出口数量。HIR 不得重扫 CFG 推断这类只在正常退出时
执行的源码尾部。normal exit 的 `Break(loop)` 只结束源码 loop 并进入显式 tail；它可以
复用 `ExclusiveBreak` forward route 复合透明 Move/copy pad，但仍属于 `normal_exits`，
不能写 early guard。completion value action 由 Structure route composer 精确复合，只有
真正绕过 tail 的 early break 才写 guard。
- branch continuation 只使用本轮有界可达性和后支配边界；不能借下一轮回边证明 arm
可达，也不能把 terminal/break-only arm 当 continuation。loop-owned break 把严格后支配点
推到 loop exit 时，只有当前 loop 同时认领该 exit、两臂存在唯一共同 soft merge，且嵌套
escape guard 的物理 arm entry 或唯一 successor 精确抵达该 exit，才把正常路径收回 soft
merge；terminal arm 不进入该处的 phi/value arm。
- loop body 内 `IfElse` 的严格合流若是本轮 escape/control，而一条原始 arm 是单前驱
`Guard`、该 guard 的正常合流精确等于另一条 arm，Structure 会先在最近的同一 loop owner
内把它恢复成 one-arm prefix；不能因最后一段 body 线性落入 control，就把可规约的连续
continue guard 聚合成 multi-entry island。
- `IfElse` 的 strict exit 已有 branch-value phi 闭合时，shared tail 不能被改写为
single-pass fence。嵌套短路会让同一源码 arm 的多个 leaf 直接进入 exit；此时应按
原始两臂的 dominance 分区复用完整 value-merge 证明，不得因浅层 arm 不支配所有
escape predecessor 就伪造 `break`/island/goto。这份分区只处理 header 与 shared tail
都不在环内的 branch；cyclic 边界的 loop-carried phi 仍交给 loop/single-pass owner，
任意归属歧义也保守拒绝。
- 即使 strict exit 没有活跃 result phi，只要线性 tail 完全由 `IfElse` 的一臂支配，
且其余直达 exit 的 predecessor 全部由另一臂支配，这两组边就是普通分支的独立完成
路径，不是“共享 tail + early break”。numeric/generic-for 的语法退出也不能因此把
外层 branch 伪装成 single-pass `repeat ... until true`；只有两臂都不独占 tail 时才
继续考虑 single-pass fence。
- single-pass fence 不能位于 `Break/Continue` 的物理来源与其祖先目标之间；HIR 会把 fence
物化成 synthetic `repeat ... until true`，Lua 的无标签控制只能命中最近词法循环。
候选层应拒绝 loop pre-exit 域，最终 validator 再按 region ancestor 关系兜底，并覆盖
VM-for payload 在 child loop 后隐式发射、没有直接 `Break` edge transfer 的 propagated break。
- 最终 `Continue` transfer 只消费 Structure 冻结的 candidate/semantic continue edge；condition
选择可用 target predecessor 证据拒绝混合 terminal action，但不得据此改写 edge owner。
对普通 while/generic-for，若 normal arm 的唯一 local frontier 就是迭代入口，优先恢复
branch-around-tail；带语句的 Guard continuation 只有在另一条本轮回边存在、且 loop
partition 证明它跳过同级 body tail 时，才覆盖 natural backedge 的隐式迭代语义。
repeat/numeric/unknown 仍保留专用判据。
- selected condition 必须覆盖完整控制语义，并精确声明 truthy/falsy exits；不完整
short-circuit evidence 回退为普通 structured branch，而不是静默吞掉条件节点。
- repeat 的多个短路叶可以汇入同一条纯 jump backedge suffix；每条语义 arc 都保留完整
物理 route，但共享 connector 只能在同一 condition、同一真假出口和同一 transfer 下复用。
节点、内部 connector 或不同 edge action 不能借此共享，否则回退而不是重复认领控制块。
- repeat 形态精化与 selected condition 必须消费同一份安全裁剪后的短路边界。含可观察
副作用或逃逸定义的后继节点不能先作为 repeat 尾条件证据、再在最终 condition 中被
截断；否则剩余出口仍可能指向 loop body，却被误当作循环外 continuation。
- 退化 generic-for 的 immediate-break 只允许零迭代出口先经过一层透明 jump 后汇入
body target；body target 本身可能就是祖先 loop latch，不能再对称穿透。候选识别、
normal-tail 判定、protocol freeze 与 validator 必须复用同一非对称合同。
- 两个 short-circuit 候选只有在都通过相同语义验证、覆盖 block/node 数也相同时，才用
相邻判断的 debug 行号一致性替代任意 block-id 裁决。缺失行号记为中性；该排序不改变
candidate membership、phi、edge transfer、backedge、break/continue 或 residual goto。
- short-circuit/value-decision 沿透明 jump pad 进入下一个判断头时，pad 必须同时进入候选
containment 和冻结 route；只记录目标 header 会把 pad 到共享 header 的边误报为外部
入口，使本来单入口的值 DAG 退化成 island。
- crossing 或多入口残余合并成最小 island；structured child 仍保持独立 owner。
### 3. 冻结控制、值、cleanup 与 label
- 每条 CFG edge 只得到一个 `EdgeTransfer`。
- VM-for 的 `LoopExit` 若同时离开祖先 single-pass fence，edge owner 仍是最内层 for
region，transfer 为指向该 fence 的 `Break`；HIR 在源码 `for ... end` 后发射这个
祖先退出。不能把 owner 提升给 fence，也不能为同一物理 edge 复制两份 transfer。
- 每个 phi incoming 只属于
`RegionInput / RegionResult / LoopCarried / EdgeCopy / Dead / DiagnosticUnresolved` 之一。
- 每个 `Close/Tbc` 只属于一个 cleanup disposition。
- goto 和多入口 island 的目标由 Structure 一次分配 `LabelPlanId`；HIR 不扫描 CFG
动态发现 label。
- label 保存 VM 已知的 TBC active-set，并冻结为 `BeforeBlock` 或
`AfterCleanup(InstrRef)`。部分入口仍携带 TBC 的 join 必须把 label 放在入口 `Close`
之后；goto 不得进入 source 尚未激活的 `<close>` scope。后期恢复出来的普通 local
仍由最终 AST scope verifier 复核。
### 4. 强校验并冻结
最终校验至少证明：
1. 每个 reachable block 恰有一个 containment owner。
2. containment 无环；除 root 外每个 region 恰有一个 parent。
3. structured region 单入口，所有跨边界 edge 都有声明的 transfer。
4. 多入口只出现在 island 的 `entry_ports`；island layout、entry、exit 全部闭合。
5. 每条 CFG edge、phi incoming 和 cleanup 恰有一个 disposition；混合回边上的 canonical
copy 也必须逐项证明由普通 edge lowering 或精确 loop value-action 消费。
6. label arena、`label_by_block`、goto transfer 和 requirement 精确互相对应。
7. forward route 连续、无环、不穿越 label/cleanup/scope barrier，且 value action 只执行一次。
8. `required_features` 与实际 `Goto/Continue` transfer 完全一致。
9. unresolved value 只能变成显式 requirement，不能猜默认值。
违反合同返回 `StructureError`。用户输入不得触发 Structure/HIR 的 `panic!`、`assert!`
或 `expect`。
## 方言能力
`ControlFlowCaps` 由 Structure 与 AST 共享，Structure 不反向依赖 AST：
| Lua 5.1 | 否 | 否 |
| Lua 5.2–5.5 | 是 | 否 |
| LuaJIT | 是 | 否 |
| Luau | 否 | 是 |
等价的可规约 `continue` 优先成为 structured branch-around-tail；Luau 可以保留
`Continue`。真正不可规约且目标无 goto 时，strict 生成返回 unsupported error，
permissive 生成带错误头的诊断伪源码；不引入 dispatcher/state-machine fallback。
| 全结构化 | `Source` | `Source` | `Source` |
| 含 island / planned goto | 可编译 `Source` | 明确 unsupported error | 带错误头的 `DiagnosticPseudocode` |
| 含 unresolved value | 拒绝 | 拒绝 | 显式 unresolved 诊断，不猜值 |
## 复杂度合同
plan 构建和验证目标为：
```text
O(blocks + edges + phi incomings + instructions)
```
当前 final edge/phi/cleanup 冻结、validator 和普通 branch containment 已满足这份
incidence 合同。普通规约 loop 查询由共享 loop forest 与 dense direct-owner/part 索引提供；
只有为了 branch/phi/cleanup subset 证明而保留的精确 natural-loop evidence，或人工构造的
交叠 CFG，才有 `O(blocks × loop-depth)` 的显式上界。因此 Structure 对普通输入满足线性
持久化合同，但不对任意人工交叠 CFG 承诺纯线性。
实现约束：
- dense ID 查询使用 `Vec`、epoch stamp 或预计算 tree index。
- canonical SSA 在 use index 完成后一次冻结稠密的 phi 死活 mask；Structure 选择与
validator 只做 O(1) 查询，不得各自重建树集合或重复传播 incoming。
- short-circuit value/guard DAG 在 analyzer 级复用 epoch-stamped node workspace；不能为
每个 phi 或 branch candidate 分配、清零一张 `blocks` 长度的索引。value dependency
到达候选入口 phi 时即归为 `RegionInput`，不得沿历史 SSA 链反复回溯。
- region ancestor/owner 合并使用一次 Euler interval；edge-copy 的透明 `Move` 来源按
`DefId` 一次压缩，不能为每个 incoming 重走链。
- `NaturalLoopForest` 在 parent/children 冻结后复用同一份 preorder/subtree-end 区间做严格
loop ancestor 判断，owner 查询为 `O(1)`；这只替换 owner 比较的查询方式，不替换
`NaturalLoop.blocks` 等 subset/member evidence，因此不会改变交叠 domain 的保守分支。
- 普通 branch domain 保存 dominator preorder interval；存在 island 时先建一次 island
union prefix，仅实际与 island 相交的 branch 才物化精确保护集合。validator 的 CFG
reachability 同样先投影为稠密 bit arena。
- 每条 CFG edge、phi incoming 和 cleanup 只在线性 pass 中登记。
- propagated-break 的跨层合法性在 loop preorder 中压缩成稠密 target 索引；validator
使用一次 region preorder、一次 edge pass 和一次逆序 completion 汇总，不按 loop
重扫全部 edge，也不在逐 edge 分类时沿 loop-parent 链上爬。
- 不为每个候选复制完整 block 集，不做候选 all-pairs 集合比较。
- natural loop 当前对每个 header 只运行一次多源 predecessor worklist，避免同 header
backedge 重扫；`NaturalLoopForest` 与 `LoopRewriteIndex` 已消除普通规约输入的持久祖先
incidence，交叠候选才保留显式 evidence。
VM-for residual partition 至多再按协议分区运行一次，不按 backedge 重走全图。
- GraphFacts 现同步冻结 `NaturalLoopForest`：每个 loop 只有一个 parent、每个 block 只有
一个可证明的 innermost owner，`direct_blocks` 总量按 block 计，lowering 可沿共享 parent
iterator 查询祖先而不复制 `block × depth` 列表。不可规约的交叠 domain 标成 ambiguous
并保守返回空 owner。旧 `NaturalLoop.blocks` 仍作为 candidate 的精确 evidence；它和
`LoopCandidate.blocks/body_scope_blocks` 的全量集合是 subset/成员证明所需的语义域，不是
可用 innermost owner 替换的缓存，因此 `O(blocks × loop-depth)` 是人工交叠 CFG 的明确
evidence 上界，而非未完成的 owner-index TODO。
- `LoopRewriteIndex` 对 semantic candidate 采用同一份 owner 合同：正常嵌套只冻结
`innermost_by_block + parent`，成员计数/Euler/score 顺序不一致的 block 才保留显式
fallback。这样 lowering 的普通查询不再持久化 `block × ancestor` 列表；fallback 是
交叠候选的语义证据，不是静默降级。
- `LoopCandidate.control_blocks` 只表达稀疏的规范化控制 pad，使用排序去重的
`Vec<BlockRef>` 保留集合合同；`blocks` 与 `body_scope_blocks` 仍保留完整域，不能把
高频 subset/clone 消费者误当成同一类稀疏事实。
- 不按 region 深度复制 boundary、label 或 entry/exit edge。
- forward route 使用共享表示或保留 pad；不能为多个入口复制同一长后缀。
- 禁止全路径枚举、全对可达性和在 validator 中重建第二套 owner arena。
## HIR 消费边界
HIR 只能通过 `StructurePlan` 查询 region、edge、value、cleanup、condition 和 label。
禁止重新：
- 按 header 选择 branch/loop candidate；
- 猜 continuation、break/continue 或 label；
- 用 `visited` 决定 ownership；
- checkpoint/rollback 整棵结构路径；
- 从 CFG 重建 phi owner 或 scope barrier。
表达式内联失败可以保留 temp，但不得改变控制计划。
## Debug
`--dump structure --detail verbose` 展示：
- region containment tree 与 island layout；
- block terminator identity、condition DAG 与 value-decision DAG；
- edge transfer、forward route 和 phi copies；
- phi/value owner；
- cleanup owner；
- planned labels 与 scope barrier；
- required / unavailable features。
dump 只显示 final plan，不再输出 raw candidates 或旧 `BlockOwner/EdgeOwner` 双轨。