presolve_compiler/
control_flow.rs

1//! Immutable control-flow projections over canonical compiler IR.
2//!
3//! This product exposes only facts represented by `IntermediateRepresentation`.
4//! Its coverage markers prevent later analyses from mistaking absent exception,
5//! suspension, or unknown-call IR for a proven empty set.
6
7use std::collections::BTreeSet;
8
9use serde::Serialize;
10
11use crate::intermediate_representation::ir_instruction_operands;
12use crate::{
13    IntermediateRepresentation, IrBranchArm, IrInstructionKind, IrOperand, SourceProvenance,
14};
15
16pub const CONTROL_FLOW_SCHEMA_VERSION: u32 = 1;
17
18/// A deterministic, Presolve-owned per-function control-flow product.
19#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
20pub struct ControlFlowGraphV1 {
21    pub schema_version: u32,
22    pub functions: Vec<ControlFlowFunctionV1>,
23}
24
25/// Control-flow and data-access facts for one canonical IR function.
26#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
27pub struct ControlFlowFunctionV1 {
28    pub module_path: String,
29    pub id: String,
30    pub name: String,
31    pub provenance: ControlFlowProvenanceV1,
32    pub entry_block: String,
33    pub blocks: Vec<ControlFlowBlockV1>,
34    pub branch_edges: Vec<ControlFlowBranchEdgeV1>,
35    pub loops: Vec<ControlFlowLoopV1>,
36    pub coverage: ControlFlowCoverageV1,
37}
38
39/// A basic block with exact IR-visible reads and writes.
40#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
41pub struct ControlFlowBlockV1 {
42    pub id: String,
43    pub provenance: ControlFlowProvenanceV1,
44    pub reads: Vec<ControlFlowAccessV1>,
45    pub writes: Vec<ControlFlowAccessV1>,
46    pub observable_instructions: Vec<String>,
47}
48
49/// One directed conditional edge in canonical IR.
50#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
51pub struct ControlFlowBranchEdgeV1 {
52    pub from: String,
53    pub to: String,
54    pub arm: ControlFlowBranchArmV1,
55    pub provenance: ControlFlowProvenanceV1,
56}
57
58#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize)]
59#[serde(rename_all = "snake_case")]
60pub enum ControlFlowBranchArmV1 {
61    True,
62    False,
63}
64
65/// Natural-loop facts already retained by canonical IR.
66#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
67pub struct ControlFlowLoopV1 {
68    pub id: String,
69    pub header: String,
70    pub body: Vec<String>,
71    pub latches: Vec<String>,
72    pub exits: Vec<String>,
73    pub provenance: ControlFlowProvenanceV1,
74}
75
76/// One IR-owned data access; `kind` prevents values and semantic slots sharing
77/// a textual ID from being conflated by later analyses.
78#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize)]
79pub struct ControlFlowAccessV1 {
80    pub kind: ControlFlowAccessKindV1,
81    pub id: String,
82}
83
84#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize)]
85#[serde(rename_all = "snake_case")]
86pub enum ControlFlowAccessKindV1 {
87    Value,
88    Storage,
89    ContextSlot,
90    Computed,
91    Resource,
92}
93
94/// Whether a required analysis dimension is encoded by the current IR.
95#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
96#[serde(rename_all = "snake_case")]
97pub enum ControlFlowCoverageStatusV1 {
98    Available,
99    Unavailable,
100}
101
102/// Explicit fail-closed coverage for a function control-flow projection.
103#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
104pub struct ControlFlowCoverageV1 {
105    pub branch_topology: ControlFlowCoverageStatusV1,
106    pub definite_dataflow: ControlFlowCoverageStatusV1,
107    pub natural_loops: ControlFlowCoverageStatusV1,
108    pub exception_paths: ControlFlowCoverageStatusV1,
109    pub async_suspension: ControlFlowCoverageStatusV1,
110    pub unknown_calls: ControlFlowCoverageStatusV1,
111    pub capture_escape: ControlFlowCoverageStatusV1,
112    pub resource_cancellation: ControlFlowCoverageStatusV1,
113}
114
115/// Serializable source provenance retained through the CFG projection.
116#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
117pub struct ControlFlowProvenanceV1 {
118    pub path: String,
119    pub start: usize,
120    pub end: usize,
121    pub line: usize,
122    pub column: usize,
123}
124
125/// Projects all canonical IR functions into stable control-flow records.
126#[must_use]
127pub fn build_control_flow_graph_v1(ir: &IntermediateRepresentation) -> ControlFlowGraphV1 {
128    let mut functions = ir
129        .modules
130        .iter()
131        .flat_map(|module| {
132            module.functions.iter().map(move |function| {
133                project_function(module.path.to_string_lossy().as_ref(), function)
134            })
135        })
136        .collect::<Vec<_>>();
137    functions.sort_by(|left, right| {
138        left.module_path
139            .cmp(&right.module_path)
140            .then_with(|| left.id.cmp(&right.id))
141    });
142    ControlFlowGraphV1 {
143        schema_version: CONTROL_FLOW_SCHEMA_VERSION,
144        functions,
145    }
146}
147
148fn project_function(module_path: &str, function: &crate::IrFunction) -> ControlFlowFunctionV1 {
149    let mut blocks = function
150        .blocks
151        .iter()
152        .map(|block| {
153            let mut reads = BTreeSet::new();
154            let mut writes = BTreeSet::new();
155            let mut observable_instructions = Vec::new();
156            for instruction in &block.instructions {
157                collect_instruction_accesses(&instruction.kind, &mut reads, &mut writes);
158                for operand in ir_instruction_operands(&instruction.kind) {
159                    match operand {
160                        IrOperand::Value(value) => {
161                            reads.insert(access(ControlFlowAccessKindV1::Value, value.to_string()));
162                        }
163                        IrOperand::Storage(storage) => {
164                            reads.insert(access(
165                                ControlFlowAccessKindV1::Storage,
166                                storage.to_string(),
167                            ));
168                        }
169                        IrOperand::Constant(_) => {}
170                    }
171                }
172                if let Some(result) = &instruction.result {
173                    writes.insert(access(ControlFlowAccessKindV1::Value, result.to_string()));
174                }
175                if instruction.kind.is_observable_side_effect() {
176                    observable_instructions.push(instruction.id.to_string());
177                }
178            }
179            ControlFlowBlockV1 {
180                id: block.id.to_string(),
181                provenance: provenance(&block.provenance),
182                reads: reads.into_iter().collect(),
183                writes: writes.into_iter().collect(),
184                observable_instructions,
185            }
186        })
187        .collect::<Vec<_>>();
188    blocks.sort_by(|left, right| left.id.cmp(&right.id));
189
190    let mut branch_edges = function
191        .branch_edges
192        .iter()
193        .map(|edge| ControlFlowBranchEdgeV1 {
194            from: edge.from.to_string(),
195            to: edge.to.to_string(),
196            arm: match edge.arm {
197                IrBranchArm::True => ControlFlowBranchArmV1::True,
198                IrBranchArm::False => ControlFlowBranchArmV1::False,
199            },
200            provenance: provenance(&edge.provenance),
201        })
202        .collect::<Vec<_>>();
203    branch_edges.sort_by(|left, right| {
204        left.from
205            .cmp(&right.from)
206            .then_with(|| left.to.cmp(&right.to))
207            .then_with(|| left.arm.cmp(&right.arm))
208    });
209
210    let mut loops = function
211        .loops
212        .iter()
213        .map(|loop_| ControlFlowLoopV1 {
214            id: loop_.id.to_string(),
215            header: loop_.header.to_string(),
216            body: sorted_ids(&loop_.body),
217            latches: sorted_ids(&loop_.latches),
218            exits: sorted_ids(&loop_.exits),
219            provenance: provenance(&loop_.provenance),
220        })
221        .collect::<Vec<_>>();
222    loops.sort_by(|left, right| left.id.cmp(&right.id));
223
224    ControlFlowFunctionV1 {
225        module_path: module_path.to_owned(),
226        id: function.id.to_string(),
227        name: function.name.clone(),
228        provenance: provenance(&function.provenance),
229        entry_block: function.entry_block.to_string(),
230        blocks,
231        branch_edges,
232        loops,
233        coverage: ControlFlowCoverageV1 {
234            branch_topology: ControlFlowCoverageStatusV1::Available,
235            definite_dataflow: ControlFlowCoverageStatusV1::Available,
236            natural_loops: ControlFlowCoverageStatusV1::Available,
237            exception_paths: ControlFlowCoverageStatusV1::Unavailable,
238            async_suspension: ControlFlowCoverageStatusV1::Unavailable,
239            unknown_calls: ControlFlowCoverageStatusV1::Unavailable,
240            capture_escape: ControlFlowCoverageStatusV1::Unavailable,
241            resource_cancellation: ControlFlowCoverageStatusV1::Unavailable,
242        },
243    }
244}
245
246fn collect_instruction_accesses(
247    kind: &IrInstructionKind,
248    reads: &mut BTreeSet<ControlFlowAccessV1>,
249    writes: &mut BTreeSet<ControlFlowAccessV1>,
250) {
251    match kind {
252        IrInstructionKind::InitializeStorage { storage } => {
253            writes.insert(access(
254                ControlFlowAccessKindV1::Storage,
255                storage.to_string(),
256            ));
257        }
258        IrInstructionKind::InitializeContextSlot { slot, .. } => {
259            writes.insert(access(
260                ControlFlowAccessKindV1::ContextSlot,
261                slot.to_string(),
262            ));
263        }
264        IrInstructionKind::LoadStorage { storage } => {
265            reads.insert(access(
266                ControlFlowAccessKindV1::Storage,
267                storage.to_string(),
268            ));
269        }
270        IrInstructionKind::LoadContextSlot { slot } => {
271            reads.insert(access(
272                ControlFlowAccessKindV1::ContextSlot,
273                slot.to_string(),
274            ));
275        }
276        IrInstructionKind::LoadComputed { computed } => {
277            reads.insert(access(
278                ControlFlowAccessKindV1::Computed,
279                computed.to_string(),
280            ));
281        }
282        IrInstructionKind::LoadResource { declaration } => {
283            reads.insert(access(
284                ControlFlowAccessKindV1::Resource,
285                declaration.to_string(),
286            ));
287        }
288        IrInstructionKind::StoreStorage { storage, .. } => {
289            writes.insert(access(
290                ControlFlowAccessKindV1::Storage,
291                storage.to_string(),
292            ));
293        }
294        IrInstructionKind::Nop
295        | IrInstructionKind::Constant { .. }
296        | IrInstructionKind::Copy { .. }
297        | IrInstructionKind::GetMember { .. }
298        | IrInstructionKind::GetIndex { .. }
299        | IrInstructionKind::Select { .. }
300        | IrInstructionKind::Template { .. }
301        | IrInstructionKind::PurePackageCall { .. }
302        | IrInstructionKind::CapabilityCall { .. }
303        | IrInstructionKind::CapabilityAssign { .. }
304        | IrInstructionKind::Binary { .. }
305        | IrInstructionKind::Unary { .. } => {}
306    }
307}
308
309fn access(kind: ControlFlowAccessKindV1, id: String) -> ControlFlowAccessV1 {
310    ControlFlowAccessV1 { kind, id }
311}
312
313fn sorted_ids(values: &[crate::IrBlockId]) -> Vec<String> {
314    let mut values = values.iter().map(ToString::to_string).collect::<Vec<_>>();
315    values.sort();
316    values.dedup();
317    values
318}
319
320fn provenance(value: &SourceProvenance) -> ControlFlowProvenanceV1 {
321    ControlFlowProvenanceV1 {
322        path: value.path.to_string_lossy().into_owned(),
323        start: value.span.start,
324        end: value.span.end,
325        line: value.span.line,
326        column: value.span.column,
327    }
328}
329
330#[cfg(test)]
331mod tests {
332    use std::collections::BTreeMap;
333
334    use crate::{
335        ContextIrReport, IntermediateRepresentation, IrBlock, IrBlockId, IrBranchArm, IrBranchEdge,
336        IrConstant, IrFunction, IrInstruction, IrInstructionId, IrInstructionKind, IrModule,
337        IrOperand, IrStorageId, IrValueId, SemanticId, SourceProvenance,
338    };
339
340    use super::{
341        build_control_flow_graph_v1, ControlFlowAccessKindV1, ControlFlowCoverageStatusV1,
342        CONTROL_FLOW_SCHEMA_VERSION,
343    };
344
345    #[test]
346    fn projects_branch_and_definite_dataflow_from_canonical_ir() {
347        let function = SemanticId::component(Some("x-counter"), "Counter").method("increment");
348        let entry = IrBlockId::entry_for(&function);
349        let when_true = IrBlockId::for_function(&function, "when-true");
350        let when_false = IrBlockId::for_function(&function, "when-false");
351        let storage = IrStorageId::for_semantic_origin(
352            &SemanticId::component(Some("x-counter"), "Counter").state_field("count"),
353        );
354        let source = SourceProvenance::new(
355            "src/Counter.tsx",
356            presolve_parser::SourceSpan {
357                start: 4,
358                end: 9,
359                line: 1,
360                column: 5,
361            },
362        );
363        let representation = IntermediateRepresentation {
364            modules: vec![IrModule {
365                path: "src/Counter.tsx".into(),
366                components: Vec::new(),
367                storages: Vec::new(),
368                storage_initializers: Vec::new(),
369                template_entrypoints: Vec::new(),
370                functions: vec![IrFunction {
371                    id: function.clone(),
372                    name: "increment".to_owned(),
373                    provenance: source.clone(),
374                    entry_block: entry.clone(),
375                    blocks: vec![
376                        IrBlock {
377                            id: entry.clone(),
378                            provenance: source.clone(),
379                            instructions: vec![IrInstruction {
380                                id: IrInstructionId::for_block(&entry, 0),
381                                provenance: source.clone(),
382                                result: Some(IrValueId::for_function(&function, 0)),
383                                semantic_origin: None,
384                                kind: IrInstructionKind::LoadStorage {
385                                    storage: storage.clone(),
386                                },
387                            }],
388                        },
389                        IrBlock {
390                            id: when_true.clone(),
391                            provenance: source.clone(),
392                            instructions: vec![IrInstruction {
393                                id: IrInstructionId::for_block(&when_true, 0),
394                                provenance: source.clone(),
395                                result: None,
396                                semantic_origin: None,
397                                kind: IrInstructionKind::StoreStorage {
398                                    storage: storage.clone(),
399                                    value: IrOperand::Value(IrValueId::for_function(&function, 0)),
400                                },
401                            }],
402                        },
403                        IrBlock {
404                            id: when_false.clone(),
405                            provenance: source.clone(),
406                            instructions: vec![IrInstruction {
407                                id: IrInstructionId::for_block(&when_false, 0),
408                                provenance: source.clone(),
409                                result: Some(IrValueId::for_function(&function, 1)),
410                                semantic_origin: None,
411                                kind: IrInstructionKind::Constant {
412                                    value: IrConstant::Number("0".into()),
413                                },
414                            }],
415                        },
416                    ],
417                    branch_edges: vec![
418                        IrBranchEdge {
419                            from: entry.clone(),
420                            to: when_true,
421                            arm: IrBranchArm::True,
422                            provenance: source.clone(),
423                        },
424                        IrBranchEdge {
425                            from: entry,
426                            to: when_false,
427                            arm: IrBranchArm::False,
428                            provenance: source.clone(),
429                        },
430                    ],
431                    values: BTreeMap::new(),
432                    loops: Vec::new(),
433                }],
434                computed_evaluations: Vec::new(),
435                effect_executions: Vec::new(),
436            }],
437            context_ir: ContextIrReport::default(),
438        };
439
440        let graph = build_control_flow_graph_v1(&representation);
441        assert_eq!(graph.schema_version, CONTROL_FLOW_SCHEMA_VERSION);
442        let function = &graph.functions[0];
443        assert_eq!(function.branch_edges.len(), 2);
444        assert_eq!(
445            function.coverage.definite_dataflow,
446            ControlFlowCoverageStatusV1::Available
447        );
448        assert_eq!(
449            function.coverage.exception_paths,
450            ControlFlowCoverageStatusV1::Unavailable
451        );
452        let entry = function
453            .blocks
454            .iter()
455            .find(|block| block.id.ends_with("block:entry"))
456            .unwrap();
457        assert!(entry
458            .reads
459            .iter()
460            .any(|access| access.kind == ControlFlowAccessKindV1::Storage));
461        assert!(entry
462            .writes
463            .iter()
464            .any(|access| access.kind == ControlFlowAccessKindV1::Value));
465        let when_true = function
466            .blocks
467            .iter()
468            .find(|block| block.id.ends_with("block:when-true"))
469            .unwrap();
470        assert!(when_true
471            .reads
472            .iter()
473            .any(|access| access.kind == ControlFlowAccessKindV1::Value));
474        assert!(when_true
475            .writes
476            .iter()
477            .any(|access| access.kind == ControlFlowAccessKindV1::Storage));
478    }
479}
presolve_compiler/control_flow.rs

presolve_compiler/
control_flow.rs
