presolve_compiler/
function_summary.rs

1//! Stable function summaries derived from control-flow and explicit call facts.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use serde::Serialize;
6
7use crate::{ControlFlowAccessV1, ControlFlowGraphV1, ControlFlowProvenanceV1};
8
9pub const FUNCTION_SUMMARY_SCHEMA_VERSION: u32 = 1;
10
11/// Call evidence supplied by a canonical lowering stage.
12#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
13pub struct FunctionCallFactV1 {
14    pub caller: String,
15    pub callee: Option<String>,
16    pub provenance: ControlFlowProvenanceV1,
17}
18
19/// Whether the supplied call facts account for every call in the selected scope.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
21#[serde(rename_all = "snake_case")]
22pub enum FunctionCallCoverageV1 {
23    Complete,
24    Unavailable,
25}
26
27/// The closed call-fact input to the function-summary projection.
28#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
29pub struct FunctionCallFactsV1 {
30    pub coverage: FunctionCallCoverageV1,
31    pub calls: Vec<FunctionCallFactV1>,
32}
33
34/// Stable direct and transitive facts for one function.
35#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
36pub struct FunctionSummaryV1 {
37    pub id: String,
38    pub module_path: String,
39    pub direct_reads: Vec<ControlFlowAccessV1>,
40    pub direct_writes: Vec<ControlFlowAccessV1>,
41    pub direct_callees: Vec<String>,
42    pub has_direct_unknown_call: bool,
43    pub call_coverage: FunctionCallCoverageV1,
44    #[serde(skip_serializing_if = "Option::is_none")]
45    pub transitive_reads: Option<Vec<ControlFlowAccessV1>>,
46    #[serde(skip_serializing_if = "Option::is_none")]
47    pub transitive_writes: Option<Vec<ControlFlowAccessV1>>,
48    #[serde(skip_serializing_if = "Option::is_none")]
49    pub transitive_callees: Option<Vec<String>>,
50    #[serde(skip_serializing_if = "Option::is_none")]
51    pub has_transitive_unknown_call: Option<bool>,
52}
53
54/// A versioned function-summary projection.
55#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
56pub struct FunctionSummaryGraphV1 {
57    pub schema_version: u32,
58    pub summaries: Vec<FunctionSummaryV1>,
59}
60
61/// Invalid call evidence cannot silently alter a function summary.
62#[derive(Debug, Clone, PartialEq, Eq)]
63pub enum FunctionSummaryErrorV1 {
64    UnknownCaller(String),
65    UnknownCallee { caller: String, callee: String },
66}
67
68impl std::fmt::Display for FunctionSummaryErrorV1 {
69    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
70        match self {
71            Self::UnknownCaller(caller) => {
72                write!(formatter, "call fact references unknown caller {caller}")
73            }
74            Self::UnknownCallee { caller, callee } => {
75                write!(
76                    formatter,
77                    "call fact from {caller} references unknown callee {callee}"
78                )
79            }
80        }
81    }
82}
83
84impl std::error::Error for FunctionSummaryErrorV1 {}
85
86/// Builds direct summaries and, only for complete call coverage, transitive facts.
87pub fn build_function_summary_graph_v1(
88    control_flow: &ControlFlowGraphV1,
89    call_facts: &FunctionCallFactsV1,
90) -> Result<FunctionSummaryGraphV1, FunctionSummaryErrorV1> {
91    let functions = control_flow
92        .functions
93        .iter()
94        .map(|function| (function.id.clone(), function))
95        .collect::<BTreeMap<_, _>>();
96    let mut calls = functions
97        .keys()
98        .cloned()
99        .map(|id| (id, Vec::new()))
100        .collect::<BTreeMap<_, Vec<&FunctionCallFactV1>>>();
101    for fact in &call_facts.calls {
102        if !functions.contains_key(&fact.caller) {
103            return Err(FunctionSummaryErrorV1::UnknownCaller(fact.caller.clone()));
104        }
105        if let Some(callee) = &fact.callee {
106            if !functions.contains_key(callee) {
107                return Err(FunctionSummaryErrorV1::UnknownCallee {
108                    caller: fact.caller.clone(),
109                    callee: callee.clone(),
110                });
111            }
112        }
113        calls.entry(fact.caller.clone()).or_default().push(fact);
114    }
115
116    let direct = functions
117        .iter()
118        .map(|(id, function)| {
119            let reads = function
120                .blocks
121                .iter()
122                .flat_map(|block| block.reads.iter().cloned())
123                .collect::<BTreeSet<_>>();
124            let writes = function
125                .blocks
126                .iter()
127                .flat_map(|block| block.writes.iter().cloned())
128                .collect::<BTreeSet<_>>();
129            let callees = calls[id]
130                .iter()
131                .filter_map(|fact| fact.callee.clone())
132                .collect::<BTreeSet<_>>();
133            let unknown = calls[id].iter().any(|fact| fact.callee.is_none());
134            (
135                id.clone(),
136                SummaryAggregate {
137                    reads,
138                    writes,
139                    callees,
140                    unknown,
141                },
142            )
143        })
144        .collect::<BTreeMap<_, _>>();
145    let transitive = match call_facts.coverage {
146        FunctionCallCoverageV1::Complete => Some(derive_transitive_summaries(&direct)),
147        FunctionCallCoverageV1::Unavailable => None,
148    };
149    let summaries = functions
150        .iter()
151        .map(|(id, function)| {
152            let direct = &direct[id];
153            let transitive = transitive.as_ref().map(|summaries| &summaries[id]);
154            FunctionSummaryV1 {
155                id: id.clone(),
156                module_path: function.module_path.clone(),
157                direct_reads: direct.reads.iter().cloned().collect(),
158                direct_writes: direct.writes.iter().cloned().collect(),
159                direct_callees: direct.callees.iter().cloned().collect(),
160                has_direct_unknown_call: direct.unknown,
161                call_coverage: call_facts.coverage,
162                transitive_reads: transitive.map(|summary| summary.reads.iter().cloned().collect()),
163                transitive_writes: transitive
164                    .map(|summary| summary.writes.iter().cloned().collect()),
165                transitive_callees: transitive
166                    .map(|summary| summary.callees.iter().cloned().collect()),
167                has_transitive_unknown_call: transitive.map(|summary| summary.unknown),
168            }
169        })
170        .collect();
171    Ok(FunctionSummaryGraphV1 {
172        schema_version: FUNCTION_SUMMARY_SCHEMA_VERSION,
173        summaries,
174    })
175}
176
177#[derive(Debug, Clone, PartialEq, Eq)]
178struct SummaryAggregate {
179    reads: BTreeSet<ControlFlowAccessV1>,
180    writes: BTreeSet<ControlFlowAccessV1>,
181    callees: BTreeSet<String>,
182    unknown: bool,
183}
184
185fn derive_transitive_summaries(
186    direct: &BTreeMap<String, SummaryAggregate>,
187) -> BTreeMap<String, SummaryAggregate> {
188    let mut summaries = direct.clone();
189    let mut changed = true;
190    while changed {
191        changed = false;
192        for (id, direct_summary) in direct {
193            let mut next = direct_summary.clone();
194            for callee in &direct_summary.callees {
195                let callee_summary = &summaries[callee];
196                next.reads.extend(callee_summary.reads.iter().cloned());
197                next.writes.extend(callee_summary.writes.iter().cloned());
198                next.callees.extend(callee_summary.callees.iter().cloned());
199                next.unknown |= callee_summary.unknown;
200            }
201            if summaries.get(id) != Some(&next) {
202                summaries.insert(id.clone(), next);
203                changed = true;
204            }
205        }
206    }
207    summaries
208}
209
210#[cfg(test)]
211mod tests {
212    use crate::{
213        ControlFlowAccessKindV1, ControlFlowAccessV1, ControlFlowBlockV1,
214        ControlFlowCoverageStatusV1, ControlFlowCoverageV1, ControlFlowFunctionV1,
215        ControlFlowGraphV1, ControlFlowProvenanceV1,
216    };
217
218    use super::{
219        build_function_summary_graph_v1, FunctionCallCoverageV1, FunctionCallFactV1,
220        FunctionCallFactsV1,
221    };
222
223    fn provenance() -> ControlFlowProvenanceV1 {
224        ControlFlowProvenanceV1 {
225            path: "src/App.tsx".into(),
226            start: 0,
227            end: 1,
228            line: 1,
229            column: 1,
230        }
231    }
232
233    fn function(id: &str, module_path: &str, read: &str, write: &str) -> ControlFlowFunctionV1 {
234        ControlFlowFunctionV1 {
235            module_path: module_path.into(),
236            id: id.into(),
237            name: id.into(),
238            provenance: provenance(),
239            entry_block: format!("{id}/entry"),
240            blocks: vec![ControlFlowBlockV1 {
241                id: format!("{id}/entry"),
242                provenance: provenance(),
243                observable_instructions: Vec::new(),
244                reads: vec![ControlFlowAccessV1 {
245                    kind: ControlFlowAccessKindV1::Storage,
246                    id: read.into(),
247                }],
248                writes: vec![ControlFlowAccessV1 {
249                    kind: ControlFlowAccessKindV1::Storage,
250                    id: write.into(),
251                }],
252            }],
253            branch_edges: Vec::new(),
254            loops: Vec::new(),
255            coverage: ControlFlowCoverageV1 {
256                branch_topology: ControlFlowCoverageStatusV1::Available,
257                definite_dataflow: ControlFlowCoverageStatusV1::Available,
258                natural_loops: ControlFlowCoverageStatusV1::Available,
259                exception_paths: ControlFlowCoverageStatusV1::Unavailable,
260                async_suspension: ControlFlowCoverageStatusV1::Unavailable,
261                unknown_calls: ControlFlowCoverageStatusV1::Unavailable,
262                capture_escape: ControlFlowCoverageStatusV1::Unavailable,
263                resource_cancellation: ControlFlowCoverageStatusV1::Unavailable,
264            },
265        }
266    }
267
268    #[test]
269    fn summarizes_cross_module_calls_transitively_and_keeps_unknown_calls_conservative() {
270        let graph = ControlFlowGraphV1 {
271            schema_version: 1,
272            functions: vec![
273                function("app", "src/App.tsx", "app-read", "app-write"),
274                function("helper", "src/helper.ts", "helper-read", "helper-write"),
275            ],
276        };
277        let facts = FunctionCallFactsV1 {
278            coverage: FunctionCallCoverageV1::Complete,
279            calls: vec![
280                FunctionCallFactV1 {
281                    caller: "app".into(),
282                    callee: Some("helper".into()),
283                    provenance: provenance(),
284                },
285                FunctionCallFactV1 {
286                    caller: "helper".into(),
287                    callee: None,
288                    provenance: provenance(),
289                },
290            ],
291        };
292        let summary = build_function_summary_graph_v1(&graph, &facts).expect("valid call facts");
293        let app = summary
294            .summaries
295            .iter()
296            .find(|summary| summary.id == "app")
297            .unwrap();
298        assert_eq!(app.direct_callees, vec!["helper"]);
299        assert!(app
300            .transitive_reads
301            .as_ref()
302            .unwrap()
303            .iter()
304            .any(|access| access.id == "helper-read"));
305        assert!(app.has_transitive_unknown_call.unwrap());
306    }
307
308    #[test]
309    fn leaves_transitive_facts_unavailable_when_call_coverage_is_unavailable() {
310        let graph = ControlFlowGraphV1 {
311            schema_version: 1,
312            functions: vec![function("app", "src/App.tsx", "read", "write")],
313        };
314        let facts = FunctionCallFactsV1 {
315            coverage: FunctionCallCoverageV1::Unavailable,
316            calls: Vec::new(),
317        };
318        let summary = build_function_summary_graph_v1(&graph, &facts).expect("valid empty facts");
319        assert!(summary.summaries[0].transitive_reads.is_none());
320        assert!(summary.summaries[0].has_transitive_unknown_call.is_none());
321    }
322}
presolve_compiler/function_summary.rs

presolve_compiler/
function_summary.rs
