cairo_lang_lowering/borrow_check/
mod.rs1#[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#[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#[derive(Copy, Clone, Debug)]
62pub enum DropPosition {
63 Panic(LocationId),
65 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 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 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
278pub type PotentialDestructCalls = UnorderedHashMap<BlockId, Vec<FunctionId>>;
280
281pub 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}