presolve_compiler/
capture_escape.rs

1//! Explicit capture and escape facts for resumability admission.
2//!
3//! Canonical IR does not yet represent closure capture, suspension, or value
4//! escape. This product therefore accepts only explicit facts from a future
5//! lowering stage and rejects resume admission when any required coverage is
6//! unavailable.
7
8use std::collections::{BTreeMap, BTreeSet};
9
10use serde::Serialize;
11
12use crate::{
13    ControlFlowAccessV1, ControlFlowCoverageStatusV1, ControlFlowGraphV1, ControlFlowProvenanceV1,
14    FunctionCallCoverageV1, FunctionSummaryGraphV1,
15};
16
17pub const CAPTURE_ESCAPE_SCHEMA_VERSION: u32 = 1;
18
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
20#[serde(rename_all = "snake_case")]
21pub enum CaptureEscapeCoverageV1 {
22    Complete,
23    Unavailable,
24}
25
26#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize)]
27#[serde(rename_all = "snake_case")]
28pub enum CaptureEscapeKindV1 {
29    Capture,
30    Escape,
31}
32
33/// Evidence supplied by a closure/async lowering that owns capture semantics.
34#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
35pub struct CaptureEscapeFactV1 {
36    pub function: String,
37    pub access: ControlFlowAccessV1,
38    pub kind: CaptureEscapeKindV1,
39    pub provenance: ControlFlowProvenanceV1,
40}
41
42/// The closed fact input for capture and escape analysis.
43#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
44pub struct CaptureEscapeFactsV1 {
45    pub coverage: CaptureEscapeCoverageV1,
46    pub facts: Vec<CaptureEscapeFactV1>,
47}
48
49#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
50#[serde(rename_all = "snake_case")]
51pub enum ResumeCaptureAdmissionV1 {
52    Admissible,
53    RejectedUnavailableCoverage,
54    RejectedUnknownCall,
55}
56
57/// Deterministic capture and escape facts for one function.
58#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
59pub struct FunctionCaptureEscapeV1 {
60    pub function: String,
61    pub captures: Vec<ControlFlowAccessV1>,
62    pub escapes: Vec<ControlFlowAccessV1>,
63    pub resume_admission: ResumeCaptureAdmissionV1,
64}
65
66/// A versioned capture/escape analysis product.
67#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
68pub struct CaptureEscapeGraphV1 {
69    pub schema_version: u32,
70    pub functions: Vec<FunctionCaptureEscapeV1>,
71}
72
73#[derive(Debug, Clone, PartialEq, Eq)]
74pub enum CaptureEscapeErrorV1 {
75    MissingSummary(String),
76    UnknownFunction(String),
77    UnknownAccess {
78        function: String,
79        access: ControlFlowAccessV1,
80    },
81}
82
83impl std::fmt::Display for CaptureEscapeErrorV1 {
84    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
85        match self {
86            Self::MissingSummary(function) => {
87                write!(formatter, "missing function summary for {function}")
88            }
89            Self::UnknownFunction(function) => write!(
90                formatter,
91                "capture fact references unknown function {function}"
92            ),
93            Self::UnknownAccess { function, access } => write!(
94                formatter,
95                "capture fact for {function} references non-CFG access {:?}:{}",
96                access.kind, access.id
97            ),
98        }
99    }
100}
101
102impl std::error::Error for CaptureEscapeErrorV1 {}
103
104/// Builds stable capture/escape records and conservative resume admission.
105pub fn build_capture_escape_graph_v1(
106    control_flow: &ControlFlowGraphV1,
107    summaries: &FunctionSummaryGraphV1,
108    facts: &CaptureEscapeFactsV1,
109) -> Result<CaptureEscapeGraphV1, CaptureEscapeErrorV1> {
110    let summaries = summaries
111        .summaries
112        .iter()
113        .map(|summary| (summary.id.as_str(), summary))
114        .collect::<BTreeMap<_, _>>();
115    let functions = control_flow
116        .functions
117        .iter()
118        .map(|function| (function.id.as_str(), function))
119        .collect::<BTreeMap<_, _>>();
120    let mut grouped = functions
121        .keys()
122        .map(|id| (*id, BTreeSet::new()))
123        .collect::<BTreeMap<_, BTreeSet<(CaptureEscapeKindV1, ControlFlowAccessV1)>>>();
124
125    for fact in &facts.facts {
126        let Some(function) = functions.get(fact.function.as_str()) else {
127            return Err(CaptureEscapeErrorV1::UnknownFunction(fact.function.clone()));
128        };
129        let accesses = function
130            .blocks
131            .iter()
132            .flat_map(|block| block.reads.iter().chain(&block.writes))
133            .collect::<BTreeSet<_>>();
134        if !accesses.contains(&fact.access) {
135            return Err(CaptureEscapeErrorV1::UnknownAccess {
136                function: fact.function.clone(),
137                access: fact.access.clone(),
138            });
139        }
140        grouped
141            .entry(fact.function.as_str())
142            .or_default()
143            .insert((fact.kind, fact.access.clone()));
144    }
145
146    let mut results = Vec::new();
147    for function in &control_flow.functions {
148        let Some(summary) = summaries.get(function.id.as_str()) else {
149            return Err(CaptureEscapeErrorV1::MissingSummary(function.id.clone()));
150        };
151        let facts_for_function = &grouped[function.id.as_str()];
152        let captures = facts_for_function
153            .iter()
154            .filter(|(kind, _)| *kind == CaptureEscapeKindV1::Capture)
155            .map(|(_, access)| access.clone())
156            .collect();
157        let escapes = facts_for_function
158            .iter()
159            .filter(|(kind, _)| *kind == CaptureEscapeKindV1::Escape)
160            .map(|(_, access)| access.clone())
161            .collect();
162        let coverage_complete = facts.coverage == CaptureEscapeCoverageV1::Complete
163            && function.coverage.capture_escape == ControlFlowCoverageStatusV1::Available
164            && function.coverage.async_suspension == ControlFlowCoverageStatusV1::Available
165            && function.coverage.unknown_calls == ControlFlowCoverageStatusV1::Available
166            && function.coverage.resource_cancellation == ControlFlowCoverageStatusV1::Available
167            && summary.call_coverage == FunctionCallCoverageV1::Complete;
168        let resume_admission = if !coverage_complete {
169            ResumeCaptureAdmissionV1::RejectedUnavailableCoverage
170        } else if summary.has_transitive_unknown_call.unwrap_or(true) {
171            ResumeCaptureAdmissionV1::RejectedUnknownCall
172        } else {
173            ResumeCaptureAdmissionV1::Admissible
174        };
175        results.push(FunctionCaptureEscapeV1 {
176            function: function.id.clone(),
177            captures,
178            escapes,
179            resume_admission,
180        });
181    }
182    results.sort_by(|left, right| left.function.cmp(&right.function));
183    Ok(CaptureEscapeGraphV1 {
184        schema_version: CAPTURE_ESCAPE_SCHEMA_VERSION,
185        functions: results,
186    })
187}
188
189#[cfg(test)]
190mod tests {
191    use crate::{
192        ControlFlowAccessKindV1, ControlFlowBlockV1, ControlFlowCoverageV1, ControlFlowFunctionV1,
193        ControlFlowProvenanceV1, FunctionSummaryV1,
194    };
195
196    use super::*;
197
198    fn provenance() -> ControlFlowProvenanceV1 {
199        ControlFlowProvenanceV1 {
200            path: "src/App.tsx".into(),
201            start: 0,
202            end: 1,
203            line: 1,
204            column: 1,
205        }
206    }
207
208    fn graph(available: bool) -> ControlFlowGraphV1 {
209        let coverage = if available {
210            ControlFlowCoverageStatusV1::Available
211        } else {
212            ControlFlowCoverageStatusV1::Unavailable
213        };
214        ControlFlowGraphV1 {
215            schema_version: 1,
216            functions: vec![ControlFlowFunctionV1 {
217                module_path: "src/App.tsx".into(),
218                id: "app".into(),
219                name: "app".into(),
220                provenance: provenance(),
221                entry_block: "app/entry".into(),
222                blocks: vec![ControlFlowBlockV1 {
223                    id: "app/entry".into(),
224                    provenance: provenance(),
225                    reads: vec![ControlFlowAccessV1 {
226                        kind: ControlFlowAccessKindV1::Storage,
227                        id: "count".into(),
228                    }],
229                    writes: Vec::new(),
230                    observable_instructions: Vec::new(),
231                }],
232                branch_edges: Vec::new(),
233                loops: Vec::new(),
234                coverage: ControlFlowCoverageV1 {
235                    branch_topology: coverage,
236                    definite_dataflow: coverage,
237                    natural_loops: coverage,
238                    exception_paths: coverage,
239                    async_suspension: coverage,
240                    unknown_calls: coverage,
241                    capture_escape: coverage,
242                    resource_cancellation: coverage,
243                },
244            }],
245        }
246    }
247
248    fn summaries(unknown_call: bool) -> FunctionSummaryGraphV1 {
249        FunctionSummaryGraphV1 {
250            schema_version: 1,
251            summaries: vec![FunctionSummaryV1 {
252                id: "app".into(),
253                module_path: "src/App.tsx".into(),
254                direct_reads: Vec::new(),
255                direct_writes: Vec::new(),
256                direct_callees: Vec::new(),
257                has_direct_unknown_call: unknown_call,
258                call_coverage: FunctionCallCoverageV1::Complete,
259                transitive_reads: Some(Vec::new()),
260                transitive_writes: Some(Vec::new()),
261                transitive_callees: Some(Vec::new()),
262                has_transitive_unknown_call: Some(unknown_call),
263            }],
264        }
265    }
266
267    fn facts() -> CaptureEscapeFactsV1 {
268        CaptureEscapeFactsV1 {
269            coverage: CaptureEscapeCoverageV1::Complete,
270            facts: vec![CaptureEscapeFactV1 {
271                function: "app".into(),
272                access: ControlFlowAccessV1 {
273                    kind: ControlFlowAccessKindV1::Storage,
274                    id: "count".into(),
275                },
276                kind: CaptureEscapeKindV1::Capture,
277                provenance: provenance(),
278            }],
279        }
280    }
281
282    #[test]
283    fn retains_explicit_capture_facts_and_admits_only_complete_known_coverage() {
284        let output = build_capture_escape_graph_v1(&graph(true), &summaries(false), &facts())
285            .expect("valid capture evidence");
286        assert_eq!(output.schema_version, CAPTURE_ESCAPE_SCHEMA_VERSION);
287        assert_eq!(output.functions[0].captures[0].id, "count");
288        assert_eq!(
289            output.functions[0].resume_admission,
290            ResumeCaptureAdmissionV1::Admissible
291        );
292    }
293
294    #[test]
295    fn rejects_resume_when_cfg_coverage_or_calls_are_incomplete() {
296        let unavailable = build_capture_escape_graph_v1(&graph(false), &summaries(false), &facts())
297            .expect("valid capture evidence");
298        assert_eq!(
299            unavailable.functions[0].resume_admission,
300            ResumeCaptureAdmissionV1::RejectedUnavailableCoverage
301        );
302        let unknown = build_capture_escape_graph_v1(&graph(true), &summaries(true), &facts())
303            .expect("valid capture evidence");
304        assert_eq!(
305            unknown.functions[0].resume_admission,
306            ResumeCaptureAdmissionV1::RejectedUnknownCall
307        );
308    }
309}
presolve_compiler/capture_escape.rs

presolve_compiler/
capture_escape.rs
