cairo_lang_lowering/borrow_check/
mod.rs

1#[cfg(test)]
2#[path = "test.rs"]
3mod test;
4
5use cairo_lang_defs::ids::TraitFunctionId;
6use cairo_lang_diagnostics::{DiagnosticNote, Maybe};
7use cairo_lang_semantic::corelib::{destruct_trait_fn, panic_destruct_trait_fn};
8use cairo_lang_semantic::items::functions::{GenericFunctionId, ImplGenericFunctionId};
9use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
10use cairo_lang_utils::{Intern, LookupIntern};
11use itertools::{Itertools, zip_eq};
12
13use self::analysis::{Analyzer, StatementLocation};
14pub use self::demand::Demand;
15use self::demand::{AuxCombine, DemandReporter};
16use crate::blocks::Blocks;
17use crate::borrow_check::analysis::BackAnalysis;
18use crate::db::LoweringGroup;
19use crate::diagnostic::LoweringDiagnosticKind::*;
20use crate::diagnostic::{LoweringDiagnostics, LoweringDiagnosticsBuilder};
21use crate::ids::{FunctionId, LocationId, SemanticFunctionIdEx};
22use crate::{BlockId, FlatLowered, MatchInfo, Statement, VarRemapping, VarUsage, VariableId};
23
24pub mod analysis;
25pub mod demand;
26
27pub type BorrowCheckerDemand = Demand<VariableId, LocationId, PanicState>;
28pub struct BorrowChecker<'a> {
29    db: &'a dyn LoweringGroup,
30    diagnostics: &'a mut LoweringDiagnostics,
31    lowered: &'a FlatLowered,
32    success: Maybe<()>,
33    potential_destruct_calls: PotentialDestructCalls,
34    destruct_fn: TraitFunctionId,
35    panic_destruct_fn: TraitFunctionId,
36    is_panic_destruct_fn: bool,
37}
38
39/// A state saved for each position in the back analysis.
40/// Used to determine if this flow is guaranteed to end in a panic.
41#[derive(Copy, Clone, Default)]
42pub enum PanicState {
43    EndsWithPanic,
44    #[default]
45    Otherwise,
46}
47impl AuxCombine for PanicState {
48    fn merge<'a, I: Iterator<Item = &'a Self>>(mut iter: I) -> Self
49    where
50        Self: 'a,
51    {
52        if iter.all(|x| matches!(x, Self::EndsWithPanic)) {
53            Self::EndsWithPanic
54        } else {
55            Self::Otherwise
56        }
57    }
58}
59
60// Represents the item that caused the triggered the need for a drop.
61#[derive(Copy, Clone, Debug)]
62pub enum DropPosition {
63    // The trigger is a call to a panicable function.
64    Panic(LocationId),
65    // The trigger is a divergence in control flow.
66    Diverge(LocationId),
67}
68impl DropPosition {
69    fn as_note(self, db: &dyn LoweringGroup) -> DiagnosticNote {
70        let (text, location) = match self {
71            Self::Panic(location) => {
72                ("the variable needs to be dropped due to the potential panic here", location)
73            }
74            Self::Diverge(location) => {
75                ("the variable needs to be dropped due to the divergence here", location)
76            }
77        };
78        DiagnosticNote::with_location(
79            text.into(),
80            location.lookup_intern(db).stable_location.diagnostic_location(db.upcast()),
81        )
82    }
83}
84
85impl DemandReporter<VariableId, PanicState> for BorrowChecker<'_> {
86    // Note that for in BorrowChecker `IntroducePosition` is used to pass the cause of
87    // the drop.
88    type IntroducePosition = (Option<DropPosition>, BlockId);
89    type UsePosition = LocationId;
90
91    fn drop_aux(
92        &mut self,
93        (opt_drop_position, block_id): (Option<DropPosition>, BlockId),
94        var_id: VariableId,
95        panic_state: PanicState,
96    ) {
97        let var = &self.lowered.variables[var_id];
98        let Err(drop_err) = var.droppable.clone() else {
99            return;
100        };
101        let mut add_called_fn = |impl_id, function| {
102            self.potential_destruct_calls.entry(block_id).or_default().push(
103                cairo_lang_semantic::FunctionLongId {
104                    function: cairo_lang_semantic::ConcreteFunction {
105                        generic_function: GenericFunctionId::Impl(ImplGenericFunctionId {
106                            impl_id,
107                            function,
108                        }),
109                        generic_args: vec![],
110                    },
111                }
112                .intern(self.db)
113                .lowered(self.db),
114            );
115        };
116        let destruct_err = match var.destruct_impl.clone() {
117            Ok(impl_id) => {
118                add_called_fn(impl_id, self.destruct_fn);
119                return;
120            }
121            Err(err) => err,
122        };
123        let panic_destruct_err = if matches!(panic_state, PanicState::EndsWithPanic) {
124            match var.panic_destruct_impl.clone() {
125                Ok(impl_id) => {
126                    add_called_fn(impl_id, self.panic_destruct_fn);
127                    return;
128                }
129                Err(err) => Some(err),
130            }
131        } else {
132            None
133        };
134
135        let mut location = var.location.lookup_intern(self.db);
136        if let Some(drop_position) = opt_drop_position {
137            location = location.with_note(drop_position.as_note(self.db));
138        }
139        let semantic_db = self.db.upcast();
140        self.success = Err(self.diagnostics.report_by_location(
141            location
142                .with_note(DiagnosticNote::text_only(drop_err.format(semantic_db)))
143                .with_note(DiagnosticNote::text_only(destruct_err.format(semantic_db)))
144                .maybe_with_note(
145                    panic_destruct_err
146                        .map(|err| DiagnosticNote::text_only(err.format(semantic_db))),
147                ),
148            VariableNotDropped { drop_err, destruct_err },
149        ));
150    }
151
152    fn dup(&mut self, position: LocationId, var_id: VariableId, next_usage_position: LocationId) {
153        let var = &self.lowered.variables[var_id];
154        if let Err(inference_error) = var.copyable.clone() {
155            self.success = Err(self.diagnostics.report_by_location(
156                next_usage_position
157                    .lookup_intern(self.db)
158                    .add_note_with_location(self.db, "variable was previously used here", position)
159                    .with_note(DiagnosticNote::text_only(inference_error.format(self.db.upcast()))),
160                VariableMoved { inference_error },
161            ));
162        }
163    }
164}
165
166impl Analyzer<'_> for BorrowChecker<'_> {
167    type Info = BorrowCheckerDemand;
168
169    fn visit_stmt(
170        &mut self,
171        info: &mut Self::Info,
172        (block_id, _): StatementLocation,
173        stmt: &Statement,
174    ) {
175        info.variables_introduced(self, stmt.outputs(), (None, block_id));
176        match stmt {
177            Statement::Call(stmt) => {
178                if let Ok(signature) = stmt.function.signature(self.db) {
179                    if signature.panicable {
180                        // Be prepared to panic here.
181                        let panic_demand = BorrowCheckerDemand {
182                            aux: PanicState::EndsWithPanic,
183                            ..Default::default()
184                        };
185                        let location = (Some(DropPosition::Panic(stmt.location)), block_id);
186                        *info = BorrowCheckerDemand::merge_demands(
187                            &[(panic_demand, location), (info.clone(), location)],
188                            self,
189                        );
190                    }
191                }
192            }
193            Statement::Desnap(stmt) => {
194                let var = &self.lowered.variables[stmt.output];
195                if let Err(inference_error) = var.copyable.clone() {
196                    self.success = Err(self.diagnostics.report_by_location(
197                        var.location.lookup_intern(self.db).with_note(DiagnosticNote::text_only(
198                            inference_error.format(self.db.upcast()),
199                        )),
200                        DesnappingANonCopyableType { inference_error },
201                    ));
202                }
203            }
204            _ => {}
205        }
206        info.variables_used(
207            self,
208            stmt.inputs().iter().map(|VarUsage { var_id, location }| (var_id, *location)),
209        );
210    }
211
212    fn visit_goto(
213        &mut self,
214        info: &mut Self::Info,
215        _statement_location: StatementLocation,
216        _target_block_id: BlockId,
217        remapping: &VarRemapping,
218    ) {
219        info.apply_remapping(
220            self,
221            remapping
222                .iter()
223                .map(|(dst, VarUsage { var_id: src, location })| (dst, (src, *location))),
224        );
225    }
226
227    fn merge_match(
228        &mut self,
229        (block_id, _): StatementLocation,
230        match_info: &MatchInfo,
231        infos: impl Iterator<Item = Self::Info>,
232    ) -> Self::Info {
233        let infos: Vec<_> = infos.collect();
234        let arm_demands = zip_eq(match_info.arms(), &infos)
235            .map(|(arm, demand)| {
236                let mut demand = demand.clone();
237                demand.variables_introduced(self, &arm.var_ids, (None, block_id));
238                (demand, (Some(DropPosition::Diverge(*match_info.location())), block_id))
239            })
240            .collect_vec();
241        let mut demand = BorrowCheckerDemand::merge_demands(&arm_demands, self);
242        demand.variables_used(
243            self,
244            match_info.inputs().iter().map(|VarUsage { var_id, location }| (var_id, *location)),
245        );
246        demand
247    }
248
249    fn info_from_return(
250        &mut self,
251        _statement_location: StatementLocation,
252        vars: &[VarUsage],
253    ) -> Self::Info {
254        let mut info = if self.is_panic_destruct_fn {
255            BorrowCheckerDemand { aux: PanicState::EndsWithPanic, ..Default::default() }
256        } else {
257            BorrowCheckerDemand::default()
258        };
259
260        info.variables_used(
261            self,
262            vars.iter().map(|VarUsage { var_id, location }| (var_id, *location)),
263        );
264        info
265    }
266
267    fn info_from_panic(
268        &mut self,
269        _statement_location: StatementLocation,
270        data: &VarUsage,
271    ) -> Self::Info {
272        let mut info = BorrowCheckerDemand { aux: PanicState::EndsWithPanic, ..Default::default() };
273        info.variables_used(self, std::iter::once((&data.var_id, data.location)));
274        info
275    }
276}
277
278/// The possible destruct calls per block.
279pub type PotentialDestructCalls = UnorderedHashMap<BlockId, Vec<FunctionId>>;
280
281/// Report borrow checking diagnostics.
282/// Returns the potential destruct function calls per block.
283pub fn borrow_check(
284    db: &dyn LoweringGroup,
285    is_panic_destruct_fn: bool,
286    lowered: &mut FlatLowered,
287) -> PotentialDestructCalls {
288    if lowered.blocks.has_root().is_err() {
289        return Default::default();
290    }
291    let mut diagnostics = LoweringDiagnostics::default();
292    diagnostics.extend(std::mem::take(&mut lowered.diagnostics));
293    let destruct_fn = destruct_trait_fn(db.upcast());
294    let panic_destruct_fn = panic_destruct_trait_fn(db.upcast());
295
296    let checker = BorrowChecker {
297        db,
298        diagnostics: &mut diagnostics,
299        lowered,
300        success: Ok(()),
301        potential_destruct_calls: Default::default(),
302        destruct_fn,
303        panic_destruct_fn,
304        is_panic_destruct_fn,
305    };
306    let mut analysis = BackAnalysis::new(lowered, checker);
307    let mut root_demand = analysis.get_root_info();
308    root_demand.variables_introduced(
309        &mut analysis.analyzer,
310        &lowered.parameters,
311        (None, BlockId::root()),
312    );
313    let block_extra_calls = analysis.analyzer.potential_destruct_calls;
314    let success = analysis.analyzer.success;
315    assert!(root_demand.finalize(), "Undefined variable should not happen at this stage");
316
317    if let Err(diag_added) = success {
318        lowered.blocks = Blocks::new_errored(diag_added);
319    }
320
321    lowered.diagnostics = diagnostics.build();
322    block_extra_calls
323}