]>
Commit | Line | Data |
---|---|---|
cdc7bbd5 XL |
1 | use clippy_utils::diagnostics::{span_lint_hir, span_lint_hir_and_then}; |
2 | use clippy_utils::source::snippet_opt; | |
3 | use clippy_utils::ty::{has_drop, is_copy, is_type_diagnostic_item, walk_ptrs_ty_depth}; | |
4 | use clippy_utils::{fn_has_unsatisfiable_preds, match_def_path, paths}; | |
f20569fa XL |
5 | use if_chain::if_chain; |
6 | use rustc_data_structures::{fx::FxHashMap, transitive_relation::TransitiveRelation}; | |
7 | use rustc_errors::Applicability; | |
8 | use rustc_hir::intravisit::FnKind; | |
9 | use rustc_hir::{def_id, Body, FnDecl, HirId}; | |
10 | use rustc_index::bit_set::{BitSet, HybridBitSet}; | |
11 | use rustc_lint::{LateContext, LateLintPass}; | |
12 | use rustc_middle::mir::{ | |
13 | self, traversal, | |
14 | visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor as _}, | |
136023e0 | 15 | Mutability, |
f20569fa XL |
16 | }; |
17 | use rustc_middle::ty::{self, fold::TypeVisitor, Ty}; | |
18 | use rustc_mir::dataflow::{Analysis, AnalysisDomain, GenKill, GenKillAnalysis, ResultsCursor}; | |
19 | use rustc_session::{declare_lint_pass, declare_tool_lint}; | |
20 | use rustc_span::source_map::{BytePos, Span}; | |
21 | use rustc_span::sym; | |
22 | use std::convert::TryFrom; | |
23 | use std::ops::ControlFlow; | |
24 | ||
25 | macro_rules! unwrap_or_continue { | |
26 | ($x:expr) => { | |
27 | match $x { | |
28 | Some(x) => x, | |
29 | None => continue, | |
30 | } | |
31 | }; | |
32 | } | |
33 | ||
34 | declare_clippy_lint! { | |
35 | /// **What it does:** Checks for a redundant `clone()` (and its relatives) which clones an owned | |
36 | /// value that is going to be dropped without further use. | |
37 | /// | |
38 | /// **Why is this bad?** It is not always possible for the compiler to eliminate useless | |
39 | /// allocations and deallocations generated by redundant `clone()`s. | |
40 | /// | |
41 | /// **Known problems:** | |
42 | /// | |
43 | /// False-negatives: analysis performed by this lint is conservative and limited. | |
44 | /// | |
45 | /// **Example:** | |
46 | /// ```rust | |
47 | /// # use std::path::Path; | |
48 | /// # #[derive(Clone)] | |
49 | /// # struct Foo; | |
50 | /// # impl Foo { | |
51 | /// # fn new() -> Self { Foo {} } | |
52 | /// # } | |
53 | /// # fn call(x: Foo) {} | |
54 | /// { | |
55 | /// let x = Foo::new(); | |
56 | /// call(x.clone()); | |
57 | /// call(x.clone()); // this can just pass `x` | |
58 | /// } | |
59 | /// | |
60 | /// ["lorem", "ipsum"].join(" ").to_string(); | |
61 | /// | |
62 | /// Path::new("/a/b").join("c").to_path_buf(); | |
63 | /// ``` | |
64 | pub REDUNDANT_CLONE, | |
65 | perf, | |
66 | "`clone()` of an owned value that is going to be dropped immediately" | |
67 | } | |
68 | ||
69 | declare_lint_pass!(RedundantClone => [REDUNDANT_CLONE]); | |
70 | ||
71 | impl<'tcx> LateLintPass<'tcx> for RedundantClone { | |
72 | #[allow(clippy::too_many_lines)] | |
73 | fn check_fn( | |
74 | &mut self, | |
75 | cx: &LateContext<'tcx>, | |
76 | _: FnKind<'tcx>, | |
77 | _: &'tcx FnDecl<'_>, | |
78 | body: &'tcx Body<'_>, | |
79 | _: Span, | |
80 | _: HirId, | |
81 | ) { | |
82 | let def_id = cx.tcx.hir().body_owner_def_id(body.id()); | |
83 | ||
84 | // Building MIR for `fn`s with unsatisfiable preds results in ICE. | |
85 | if fn_has_unsatisfiable_preds(cx, def_id.to_def_id()) { | |
86 | return; | |
87 | } | |
88 | ||
89 | let mir = cx.tcx.optimized_mir(def_id.to_def_id()); | |
90 | ||
136023e0 XL |
91 | let possible_origin = { |
92 | let mut vis = PossibleOriginVisitor::new(mir); | |
93 | vis.visit_body(mir); | |
94 | vis.into_map(cx) | |
95 | }; | |
f20569fa XL |
96 | let maybe_storage_live_result = MaybeStorageLive |
97 | .into_engine(cx.tcx, mir) | |
98 | .pass_name("redundant_clone") | |
99 | .iterate_to_fixpoint() | |
100 | .into_results_cursor(mir); | |
101 | let mut possible_borrower = { | |
136023e0 | 102 | let mut vis = PossibleBorrowerVisitor::new(cx, mir, possible_origin); |
cdc7bbd5 | 103 | vis.visit_body(mir); |
f20569fa XL |
104 | vis.into_map(cx, maybe_storage_live_result) |
105 | }; | |
106 | ||
107 | for (bb, bbdata) in mir.basic_blocks().iter_enumerated() { | |
108 | let terminator = bbdata.terminator(); | |
109 | ||
110 | if terminator.source_info.span.from_expansion() { | |
111 | continue; | |
112 | } | |
113 | ||
114 | // Give up on loops | |
115 | if terminator.successors().any(|s| *s == bb) { | |
116 | continue; | |
117 | } | |
118 | ||
119 | let (fn_def_id, arg, arg_ty, clone_ret) = | |
120 | unwrap_or_continue!(is_call_with_ref_arg(cx, mir, &terminator.kind)); | |
121 | ||
122 | let from_borrow = match_def_path(cx, fn_def_id, &paths::CLONE_TRAIT_METHOD) | |
123 | || match_def_path(cx, fn_def_id, &paths::TO_OWNED_METHOD) | |
124 | || (match_def_path(cx, fn_def_id, &paths::TO_STRING_METHOD) | |
125 | && is_type_diagnostic_item(cx, arg_ty, sym::string_type)); | |
126 | ||
127 | let from_deref = !from_borrow | |
128 | && (match_def_path(cx, fn_def_id, &paths::PATH_TO_PATH_BUF) | |
129 | || match_def_path(cx, fn_def_id, &paths::OS_STR_TO_OS_STRING)); | |
130 | ||
131 | if !from_borrow && !from_deref { | |
132 | continue; | |
133 | } | |
134 | ||
cdc7bbd5 | 135 | if let ty::Adt(def, _) = arg_ty.kind() { |
f20569fa XL |
136 | if match_def_path(cx, def.did, &paths::MEM_MANUALLY_DROP) { |
137 | continue; | |
138 | } | |
139 | } | |
140 | ||
136023e0 | 141 | // `{ arg = &cloned; clone(move arg); }` or `{ arg = &cloned; to_path_buf(arg); }` |
f20569fa XL |
142 | let (cloned, cannot_move_out) = unwrap_or_continue!(find_stmt_assigns_to(cx, mir, arg, from_borrow, bb)); |
143 | ||
144 | let loc = mir::Location { | |
145 | block: bb, | |
146 | statement_index: bbdata.statements.len(), | |
147 | }; | |
148 | ||
149 | // `Local` to be cloned, and a local of `clone` call's destination | |
150 | let (local, ret_local) = if from_borrow { | |
151 | // `res = clone(arg)` can be turned into `res = move arg;` | |
152 | // if `arg` is the only borrow of `cloned` at this point. | |
153 | ||
154 | if cannot_move_out || !possible_borrower.only_borrowers(&[arg], cloned, loc) { | |
155 | continue; | |
156 | } | |
157 | ||
158 | (cloned, clone_ret) | |
159 | } else { | |
160 | // `arg` is a reference as it is `.deref()`ed in the previous block. | |
161 | // Look into the predecessor block and find out the source of deref. | |
162 | ||
163 | let ps = &mir.predecessors()[bb]; | |
164 | if ps.len() != 1 { | |
165 | continue; | |
166 | } | |
167 | let pred_terminator = mir[ps[0]].terminator(); | |
168 | ||
169 | // receiver of the `deref()` call | |
170 | let (pred_arg, deref_clone_ret) = if_chain! { | |
171 | if let Some((pred_fn_def_id, pred_arg, pred_arg_ty, res)) = | |
172 | is_call_with_ref_arg(cx, mir, &pred_terminator.kind); | |
173 | if res == cloned; | |
174 | if cx.tcx.is_diagnostic_item(sym::deref_method, pred_fn_def_id); | |
175 | if is_type_diagnostic_item(cx, pred_arg_ty, sym::PathBuf) | |
176 | || is_type_diagnostic_item(cx, pred_arg_ty, sym::OsString); | |
177 | then { | |
178 | (pred_arg, res) | |
179 | } else { | |
180 | continue; | |
181 | } | |
182 | }; | |
183 | ||
184 | let (local, cannot_move_out) = | |
185 | unwrap_or_continue!(find_stmt_assigns_to(cx, mir, pred_arg, true, ps[0])); | |
186 | let loc = mir::Location { | |
187 | block: bb, | |
188 | statement_index: mir.basic_blocks()[bb].statements.len(), | |
189 | }; | |
190 | ||
191 | // This can be turned into `res = move local` if `arg` and `cloned` are not borrowed | |
192 | // at the last statement: | |
193 | // | |
194 | // ``` | |
195 | // pred_arg = &local; | |
196 | // cloned = deref(pred_arg); | |
197 | // arg = &cloned; | |
198 | // StorageDead(pred_arg); | |
199 | // res = to_path_buf(cloned); | |
200 | // ``` | |
201 | if cannot_move_out || !possible_borrower.only_borrowers(&[arg, cloned], local, loc) { | |
202 | continue; | |
203 | } | |
204 | ||
205 | (local, deref_clone_ret) | |
206 | }; | |
207 | ||
cdc7bbd5 XL |
208 | let clone_usage = if local == ret_local { |
209 | CloneUsage { | |
210 | cloned_used: false, | |
211 | cloned_consume_or_mutate_loc: None, | |
212 | clone_consumed_or_mutated: true, | |
213 | } | |
214 | } else { | |
215 | let clone_usage = visit_clone_usage(local, ret_local, mir, bb); | |
216 | if clone_usage.cloned_used && clone_usage.clone_consumed_or_mutated { | |
217 | // cloned value is used, and the clone is modified or moved | |
218 | continue; | |
219 | } else if let Some(loc) = clone_usage.cloned_consume_or_mutate_loc { | |
220 | // cloned value is mutated, and the clone is alive. | |
221 | if possible_borrower.is_alive_at(ret_local, loc) { | |
222 | continue; | |
f20569fa | 223 | } |
cdc7bbd5 XL |
224 | } |
225 | clone_usage | |
226 | }; | |
f20569fa | 227 | |
cdc7bbd5 XL |
228 | let span = terminator.source_info.span; |
229 | let scope = terminator.source_info.scope; | |
230 | let node = mir.source_scopes[scope] | |
231 | .local_data | |
232 | .as_ref() | |
233 | .assert_crate_local() | |
234 | .lint_root; | |
235 | ||
236 | if_chain! { | |
237 | if let Some(snip) = snippet_opt(cx, span); | |
238 | if let Some(dot) = snip.rfind('.'); | |
239 | then { | |
240 | let sugg_span = span.with_lo( | |
241 | span.lo() + BytePos(u32::try_from(dot).unwrap()) | |
242 | ); | |
243 | let mut app = Applicability::MaybeIncorrect; | |
244 | ||
245 | let call_snip = &snip[dot + 1..]; | |
246 | // Machine applicable when `call_snip` looks like `foobar()` | |
247 | if let Some(call_snip) = call_snip.strip_suffix("()").map(str::trim) { | |
248 | if call_snip.as_bytes().iter().all(|b| b.is_ascii_alphabetic() || *b == b'_') { | |
249 | app = Applicability::MachineApplicable; | |
f20569fa | 250 | } |
cdc7bbd5 | 251 | } |
f20569fa | 252 | |
cdc7bbd5 XL |
253 | span_lint_hir_and_then(cx, REDUNDANT_CLONE, node, sugg_span, "redundant clone", |diag| { |
254 | diag.span_suggestion( | |
255 | sugg_span, | |
256 | "remove this", | |
257 | String::new(), | |
258 | app, | |
259 | ); | |
260 | if clone_usage.cloned_used { | |
261 | diag.span_note( | |
262 | span, | |
263 | "cloned value is neither consumed nor mutated", | |
f20569fa | 264 | ); |
cdc7bbd5 XL |
265 | } else { |
266 | diag.span_note( | |
267 | span.with_hi(span.lo() + BytePos(u32::try_from(dot).unwrap())), | |
268 | "this value is dropped without further use", | |
269 | ); | |
270 | } | |
271 | }); | |
272 | } else { | |
273 | span_lint_hir(cx, REDUNDANT_CLONE, node, span, "redundant clone"); | |
f20569fa XL |
274 | } |
275 | } | |
276 | } | |
277 | } | |
278 | } | |
279 | ||
280 | /// If `kind` is `y = func(x: &T)` where `T: !Copy`, returns `(DefId of func, x, T, y)`. | |
281 | fn is_call_with_ref_arg<'tcx>( | |
282 | cx: &LateContext<'tcx>, | |
283 | mir: &'tcx mir::Body<'tcx>, | |
284 | kind: &'tcx mir::TerminatorKind<'tcx>, | |
285 | ) -> Option<(def_id::DefId, mir::Local, Ty<'tcx>, mir::Local)> { | |
286 | if_chain! { | |
287 | if let mir::TerminatorKind::Call { func, args, destination, .. } = kind; | |
288 | if args.len() == 1; | |
289 | if let mir::Operand::Move(mir::Place { local, .. }) = &args[0]; | |
290 | if let ty::FnDef(def_id, _) = *func.ty(&*mir, cx.tcx).kind(); | |
291 | if let (inner_ty, 1) = walk_ptrs_ty_depth(args[0].ty(&*mir, cx.tcx)); | |
292 | if !is_copy(cx, inner_ty); | |
293 | then { | |
294 | Some((def_id, *local, inner_ty, destination.as_ref().map(|(dest, _)| dest)?.as_local()?)) | |
295 | } else { | |
296 | None | |
297 | } | |
298 | } | |
299 | } | |
300 | ||
301 | type CannotMoveOut = bool; | |
302 | ||
303 | /// Finds the first `to = (&)from`, and returns | |
304 | /// ``Some((from, whether `from` cannot be moved out))``. | |
305 | fn find_stmt_assigns_to<'tcx>( | |
306 | cx: &LateContext<'tcx>, | |
307 | mir: &mir::Body<'tcx>, | |
308 | to_local: mir::Local, | |
309 | by_ref: bool, | |
310 | bb: mir::BasicBlock, | |
311 | ) -> Option<(mir::Local, CannotMoveOut)> { | |
312 | let rvalue = mir.basic_blocks()[bb].statements.iter().rev().find_map(|stmt| { | |
313 | if let mir::StatementKind::Assign(box (mir::Place { local, .. }, v)) = &stmt.kind { | |
314 | return if *local == to_local { Some(v) } else { None }; | |
315 | } | |
316 | ||
317 | None | |
318 | })?; | |
319 | ||
320 | match (by_ref, &*rvalue) { | |
321 | (true, mir::Rvalue::Ref(_, _, place)) | (false, mir::Rvalue::Use(mir::Operand::Copy(place))) => { | |
322 | Some(base_local_and_movability(cx, mir, *place)) | |
323 | }, | |
324 | (false, mir::Rvalue::Ref(_, _, place)) => { | |
325 | if let [mir::ProjectionElem::Deref] = place.as_ref().projection { | |
326 | Some(base_local_and_movability(cx, mir, *place)) | |
327 | } else { | |
328 | None | |
329 | } | |
330 | }, | |
331 | _ => None, | |
332 | } | |
333 | } | |
334 | ||
335 | /// Extracts and returns the undermost base `Local` of given `place`. Returns `place` itself | |
336 | /// if it is already a `Local`. | |
337 | /// | |
338 | /// Also reports whether given `place` cannot be moved out. | |
339 | fn base_local_and_movability<'tcx>( | |
340 | cx: &LateContext<'tcx>, | |
341 | mir: &mir::Body<'tcx>, | |
342 | place: mir::Place<'tcx>, | |
343 | ) -> (mir::Local, CannotMoveOut) { | |
344 | use rustc_middle::mir::PlaceRef; | |
345 | ||
346 | // Dereference. You cannot move things out from a borrowed value. | |
347 | let mut deref = false; | |
348 | // Accessing a field of an ADT that has `Drop`. Moving the field out will cause E0509. | |
349 | let mut field = false; | |
350 | // If projection is a slice index then clone can be removed only if the | |
351 | // underlying type implements Copy | |
352 | let mut slice = false; | |
353 | ||
354 | let PlaceRef { local, mut projection } = place.as_ref(); | |
355 | while let [base @ .., elem] = projection { | |
356 | projection = base; | |
357 | deref |= matches!(elem, mir::ProjectionElem::Deref); | |
358 | field |= matches!(elem, mir::ProjectionElem::Field(..)) | |
359 | && has_drop(cx, mir::Place::ty_from(local, projection, &mir.local_decls, cx.tcx).ty); | |
360 | slice |= matches!(elem, mir::ProjectionElem::Index(..)) | |
361 | && !is_copy(cx, mir::Place::ty_from(local, projection, &mir.local_decls, cx.tcx).ty); | |
362 | } | |
363 | ||
364 | (local, deref || field || slice) | |
365 | } | |
366 | ||
cdc7bbd5 XL |
367 | #[derive(Default)] |
368 | struct CloneUsage { | |
369 | /// Whether the cloned value is used after the clone. | |
370 | cloned_used: bool, | |
371 | /// The first location where the cloned value is consumed or mutated, if any. | |
372 | cloned_consume_or_mutate_loc: Option<mir::Location>, | |
373 | /// Whether the clone value is mutated. | |
374 | clone_consumed_or_mutated: bool, | |
f20569fa | 375 | } |
cdc7bbd5 XL |
376 | fn visit_clone_usage(cloned: mir::Local, clone: mir::Local, mir: &mir::Body<'_>, bb: mir::BasicBlock) -> CloneUsage { |
377 | struct V { | |
378 | cloned: mir::Local, | |
379 | clone: mir::Local, | |
380 | result: CloneUsage, | |
f20569fa | 381 | } |
cdc7bbd5 XL |
382 | impl<'tcx> mir::visit::Visitor<'tcx> for V { |
383 | fn visit_basic_block_data(&mut self, block: mir::BasicBlock, data: &mir::BasicBlockData<'tcx>) { | |
384 | let statements = &data.statements; | |
385 | for (statement_index, statement) in statements.iter().enumerate() { | |
386 | self.visit_statement(statement, mir::Location { block, statement_index }); | |
387 | } | |
f20569fa | 388 | |
cdc7bbd5 XL |
389 | self.visit_terminator( |
390 | data.terminator(), | |
391 | mir::Location { | |
392 | block, | |
393 | statement_index: statements.len(), | |
394 | }, | |
395 | ); | |
f20569fa XL |
396 | } |
397 | ||
cdc7bbd5 XL |
398 | fn visit_place(&mut self, place: &mir::Place<'tcx>, ctx: PlaceContext, loc: mir::Location) { |
399 | let local = place.local; | |
400 | ||
401 | if local == self.cloned | |
402 | && !matches!( | |
403 | ctx, | |
404 | PlaceContext::MutatingUse(MutatingUseContext::Drop) | PlaceContext::NonUse(_) | |
405 | ) | |
406 | { | |
407 | self.result.cloned_used = true; | |
408 | self.result.cloned_consume_or_mutate_loc = self.result.cloned_consume_or_mutate_loc.or_else(|| { | |
409 | matches!( | |
410 | ctx, | |
411 | PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) | |
412 | | PlaceContext::MutatingUse(MutatingUseContext::Borrow) | |
413 | ) | |
414 | .then(|| loc) | |
415 | }); | |
416 | } else if local == self.clone { | |
417 | match ctx { | |
418 | PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) | |
419 | | PlaceContext::MutatingUse(MutatingUseContext::Borrow) => { | |
420 | self.result.clone_consumed_or_mutated = true; | |
421 | }, | |
422 | _ => {}, | |
423 | } | |
f20569fa XL |
424 | } |
425 | } | |
426 | } | |
cdc7bbd5 XL |
427 | |
428 | let init = CloneUsage { | |
429 | cloned_used: false, | |
430 | cloned_consume_or_mutate_loc: None, | |
431 | // Consider non-temporary clones consumed. | |
432 | // TODO: Actually check for mutation of non-temporaries. | |
433 | clone_consumed_or_mutated: mir.local_kind(clone) != mir::LocalKind::Temp, | |
434 | }; | |
435 | traversal::ReversePostorder::new(mir, bb) | |
436 | .skip(1) | |
437 | .fold(init, |usage, (tbb, tdata)| { | |
438 | // Short-circuit | |
439 | if (usage.cloned_used && usage.clone_consumed_or_mutated) || | |
440 | // Give up on loops | |
441 | tdata.terminator().successors().any(|s| *s == bb) | |
442 | { | |
443 | return CloneUsage { | |
444 | cloned_used: true, | |
445 | clone_consumed_or_mutated: true, | |
446 | ..usage | |
447 | }; | |
448 | } | |
449 | ||
450 | let mut v = V { | |
451 | cloned, | |
452 | clone, | |
453 | result: usage, | |
454 | }; | |
455 | v.visit_basic_block_data(tbb, tdata); | |
456 | v.result | |
457 | }) | |
f20569fa XL |
458 | } |
459 | ||
460 | /// Determines liveness of each local purely based on `StorageLive`/`Dead`. | |
461 | #[derive(Copy, Clone)] | |
462 | struct MaybeStorageLive; | |
463 | ||
464 | impl<'tcx> AnalysisDomain<'tcx> for MaybeStorageLive { | |
465 | type Domain = BitSet<mir::Local>; | |
466 | const NAME: &'static str = "maybe_storage_live"; | |
467 | ||
468 | fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain { | |
469 | // bottom = dead | |
470 | BitSet::new_empty(body.local_decls.len()) | |
471 | } | |
472 | ||
473 | fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain) { | |
474 | for arg in body.args_iter() { | |
475 | state.insert(arg); | |
476 | } | |
477 | } | |
478 | } | |
479 | ||
480 | impl<'tcx> GenKillAnalysis<'tcx> for MaybeStorageLive { | |
481 | type Idx = mir::Local; | |
482 | ||
483 | fn statement_effect(&self, trans: &mut impl GenKill<Self::Idx>, stmt: &mir::Statement<'tcx>, _: mir::Location) { | |
484 | match stmt.kind { | |
485 | mir::StatementKind::StorageLive(l) => trans.gen(l), | |
486 | mir::StatementKind::StorageDead(l) => trans.kill(l), | |
487 | _ => (), | |
488 | } | |
489 | } | |
490 | ||
491 | fn terminator_effect( | |
492 | &self, | |
493 | _trans: &mut impl GenKill<Self::Idx>, | |
494 | _terminator: &mir::Terminator<'tcx>, | |
495 | _loc: mir::Location, | |
496 | ) { | |
497 | } | |
498 | ||
499 | fn call_return_effect( | |
500 | &self, | |
501 | _in_out: &mut impl GenKill<Self::Idx>, | |
502 | _block: mir::BasicBlock, | |
503 | _func: &mir::Operand<'tcx>, | |
504 | _args: &[mir::Operand<'tcx>], | |
505 | _return_place: mir::Place<'tcx>, | |
506 | ) { | |
507 | // Nothing to do when a call returns successfully | |
508 | } | |
509 | } | |
510 | ||
511 | /// Collects the possible borrowers of each local. | |
512 | /// For example, `b = &a; c = &a;` will make `b` and (transitively) `c` | |
513 | /// possible borrowers of `a`. | |
514 | struct PossibleBorrowerVisitor<'a, 'tcx> { | |
515 | possible_borrower: TransitiveRelation<mir::Local>, | |
516 | body: &'a mir::Body<'tcx>, | |
517 | cx: &'a LateContext<'tcx>, | |
136023e0 | 518 | possible_origin: FxHashMap<mir::Local, HybridBitSet<mir::Local>>, |
f20569fa XL |
519 | } |
520 | ||
521 | impl<'a, 'tcx> PossibleBorrowerVisitor<'a, 'tcx> { | |
136023e0 XL |
522 | fn new( |
523 | cx: &'a LateContext<'tcx>, | |
524 | body: &'a mir::Body<'tcx>, | |
525 | possible_origin: FxHashMap<mir::Local, HybridBitSet<mir::Local>>, | |
526 | ) -> Self { | |
f20569fa XL |
527 | Self { |
528 | possible_borrower: TransitiveRelation::default(), | |
529 | cx, | |
530 | body, | |
136023e0 | 531 | possible_origin, |
f20569fa XL |
532 | } |
533 | } | |
534 | ||
535 | fn into_map( | |
536 | self, | |
537 | cx: &LateContext<'tcx>, | |
538 | maybe_live: ResultsCursor<'tcx, 'tcx, MaybeStorageLive>, | |
539 | ) -> PossibleBorrowerMap<'a, 'tcx> { | |
540 | let mut map = FxHashMap::default(); | |
541 | for row in (1..self.body.local_decls.len()).map(mir::Local::from_usize) { | |
542 | if is_copy(cx, self.body.local_decls[row].ty) { | |
543 | continue; | |
544 | } | |
545 | ||
546 | let borrowers = self.possible_borrower.reachable_from(&row); | |
547 | if !borrowers.is_empty() { | |
548 | let mut bs = HybridBitSet::new_empty(self.body.local_decls.len()); | |
549 | for &c in borrowers { | |
550 | if c != mir::Local::from_usize(0) { | |
551 | bs.insert(c); | |
552 | } | |
553 | } | |
554 | ||
555 | if !bs.is_empty() { | |
556 | map.insert(row, bs); | |
557 | } | |
558 | } | |
559 | } | |
560 | ||
561 | let bs = BitSet::new_empty(self.body.local_decls.len()); | |
562 | PossibleBorrowerMap { | |
563 | map, | |
564 | maybe_live, | |
565 | bitset: (bs.clone(), bs), | |
566 | } | |
567 | } | |
568 | } | |
569 | ||
570 | impl<'a, 'tcx> mir::visit::Visitor<'tcx> for PossibleBorrowerVisitor<'a, 'tcx> { | |
571 | fn visit_assign(&mut self, place: &mir::Place<'tcx>, rvalue: &mir::Rvalue<'_>, _location: mir::Location) { | |
572 | let lhs = place.local; | |
573 | match rvalue { | |
574 | mir::Rvalue::Ref(_, _, borrowed) => { | |
575 | self.possible_borrower.add(borrowed.local, lhs); | |
576 | }, | |
577 | other => { | |
578 | if ContainsRegion | |
579 | .visit_ty(place.ty(&self.body.local_decls, self.cx.tcx).ty) | |
580 | .is_continue() | |
581 | { | |
582 | return; | |
583 | } | |
584 | rvalue_locals(other, |rhs| { | |
585 | if lhs != rhs { | |
586 | self.possible_borrower.add(rhs, lhs); | |
587 | } | |
588 | }); | |
589 | }, | |
590 | } | |
591 | } | |
592 | ||
593 | fn visit_terminator(&mut self, terminator: &mir::Terminator<'_>, _loc: mir::Location) { | |
594 | if let mir::TerminatorKind::Call { | |
595 | args, | |
596 | destination: Some((mir::Place { local: dest, .. }, _)), | |
597 | .. | |
598 | } = &terminator.kind | |
599 | { | |
136023e0 | 600 | // TODO add doc |
f20569fa XL |
601 | // If the call returns something with lifetimes, |
602 | // let's conservatively assume the returned value contains lifetime of all the arguments. | |
603 | // For example, given `let y: Foo<'a> = foo(x)`, `y` is considered to be a possible borrower of `x`. | |
136023e0 XL |
604 | |
605 | let mut immutable_borrowers = vec![]; | |
606 | let mut mutable_borrowers = vec![]; | |
f20569fa XL |
607 | |
608 | for op in args { | |
609 | match op { | |
610 | mir::Operand::Copy(p) | mir::Operand::Move(p) => { | |
136023e0 XL |
611 | if let ty::Ref(_, _, Mutability::Mut) = self.body.local_decls[p.local].ty.kind() { |
612 | mutable_borrowers.push(p.local); | |
613 | } else { | |
614 | immutable_borrowers.push(p.local); | |
615 | } | |
f20569fa | 616 | }, |
cdc7bbd5 | 617 | mir::Operand::Constant(..) => (), |
f20569fa XL |
618 | } |
619 | } | |
136023e0 XL |
620 | |
621 | let mut mutable_variables: Vec<mir::Local> = mutable_borrowers | |
622 | .iter() | |
623 | .filter_map(|r| self.possible_origin.get(r)) | |
624 | .flat_map(HybridBitSet::iter) | |
625 | .collect(); | |
626 | ||
627 | if ContainsRegion.visit_ty(self.body.local_decls[*dest].ty).is_break() { | |
628 | mutable_variables.push(*dest); | |
629 | } | |
630 | ||
631 | for y in mutable_variables { | |
632 | for x in &immutable_borrowers { | |
633 | self.possible_borrower.add(*x, y); | |
634 | } | |
635 | for x in &mutable_borrowers { | |
636 | self.possible_borrower.add(*x, y); | |
637 | } | |
638 | } | |
639 | } | |
640 | } | |
641 | } | |
642 | ||
643 | /// Collect possible borrowed for every `&mut` local. | |
644 | /// For exampel, `_1 = &mut _2` generate _1: {_2,...} | |
645 | /// Known Problems: not sure all borrowed are tracked | |
646 | struct PossibleOriginVisitor<'a, 'tcx> { | |
647 | possible_origin: TransitiveRelation<mir::Local>, | |
648 | body: &'a mir::Body<'tcx>, | |
649 | } | |
650 | ||
651 | impl<'a, 'tcx> PossibleOriginVisitor<'a, 'tcx> { | |
652 | fn new(body: &'a mir::Body<'tcx>) -> Self { | |
653 | Self { | |
654 | possible_origin: TransitiveRelation::default(), | |
655 | body, | |
656 | } | |
657 | } | |
658 | ||
659 | fn into_map(self, cx: &LateContext<'tcx>) -> FxHashMap<mir::Local, HybridBitSet<mir::Local>> { | |
660 | let mut map = FxHashMap::default(); | |
661 | for row in (1..self.body.local_decls.len()).map(mir::Local::from_usize) { | |
662 | if is_copy(cx, self.body.local_decls[row].ty) { | |
663 | continue; | |
664 | } | |
665 | ||
666 | let borrowers = self.possible_origin.reachable_from(&row); | |
667 | if !borrowers.is_empty() { | |
668 | let mut bs = HybridBitSet::new_empty(self.body.local_decls.len()); | |
669 | for &c in borrowers { | |
670 | if c != mir::Local::from_usize(0) { | |
671 | bs.insert(c); | |
672 | } | |
673 | } | |
674 | ||
675 | if !bs.is_empty() { | |
676 | map.insert(row, bs); | |
677 | } | |
678 | } | |
679 | } | |
680 | map | |
681 | } | |
682 | } | |
683 | ||
684 | impl<'a, 'tcx> mir::visit::Visitor<'tcx> for PossibleOriginVisitor<'a, 'tcx> { | |
685 | fn visit_assign(&mut self, place: &mir::Place<'tcx>, rvalue: &mir::Rvalue<'_>, _location: mir::Location) { | |
686 | let lhs = place.local; | |
687 | match rvalue { | |
688 | // Only consider `&mut`, which can modify origin place | |
689 | mir::Rvalue::Ref(_, rustc_middle::mir::BorrowKind::Mut { .. }, borrowed) | | |
690 | // _2: &mut _; | |
691 | // _3 = move _2 | |
692 | mir::Rvalue::Use(mir::Operand::Move(borrowed)) | | |
693 | // _3 = move _2 as &mut _; | |
694 | mir::Rvalue::Cast(_, mir::Operand::Move(borrowed), _) | |
695 | => { | |
696 | self.possible_origin.add(lhs, borrowed.local); | |
697 | }, | |
698 | _ => {}, | |
f20569fa XL |
699 | } |
700 | } | |
701 | } | |
702 | ||
703 | struct ContainsRegion; | |
704 | ||
705 | impl TypeVisitor<'_> for ContainsRegion { | |
706 | type BreakTy = (); | |
707 | ||
708 | fn visit_region(&mut self, _: ty::Region<'_>) -> ControlFlow<Self::BreakTy> { | |
709 | ControlFlow::BREAK | |
710 | } | |
711 | } | |
712 | ||
713 | fn rvalue_locals(rvalue: &mir::Rvalue<'_>, mut visit: impl FnMut(mir::Local)) { | |
714 | use rustc_middle::mir::Rvalue::{Aggregate, BinaryOp, Cast, CheckedBinaryOp, Repeat, UnaryOp, Use}; | |
715 | ||
716 | let mut visit_op = |op: &mir::Operand<'_>| match op { | |
717 | mir::Operand::Copy(p) | mir::Operand::Move(p) => visit(p.local), | |
cdc7bbd5 | 718 | mir::Operand::Constant(..) => (), |
f20569fa XL |
719 | }; |
720 | ||
721 | match rvalue { | |
722 | Use(op) | Repeat(op, _) | Cast(_, op, _) | UnaryOp(_, op) => visit_op(op), | |
723 | Aggregate(_, ops) => ops.iter().for_each(visit_op), | |
724 | BinaryOp(_, box (lhs, rhs)) | CheckedBinaryOp(_, box (lhs, rhs)) => { | |
725 | visit_op(lhs); | |
726 | visit_op(rhs); | |
727 | } | |
728 | _ => (), | |
729 | } | |
730 | } | |
731 | ||
732 | /// Result of `PossibleBorrowerVisitor`. | |
733 | struct PossibleBorrowerMap<'a, 'tcx> { | |
734 | /// Mapping `Local -> its possible borrowers` | |
735 | map: FxHashMap<mir::Local, HybridBitSet<mir::Local>>, | |
736 | maybe_live: ResultsCursor<'a, 'tcx, MaybeStorageLive>, | |
737 | // Caches to avoid allocation of `BitSet` on every query | |
738 | bitset: (BitSet<mir::Local>, BitSet<mir::Local>), | |
739 | } | |
740 | ||
741 | impl PossibleBorrowerMap<'_, '_> { | |
742 | /// Returns true if the set of borrowers of `borrowed` living at `at` matches with `borrowers`. | |
743 | fn only_borrowers(&mut self, borrowers: &[mir::Local], borrowed: mir::Local, at: mir::Location) -> bool { | |
744 | self.maybe_live.seek_after_primary_effect(at); | |
745 | ||
746 | self.bitset.0.clear(); | |
747 | let maybe_live = &mut self.maybe_live; | |
748 | if let Some(bitset) = self.map.get(&borrowed) { | |
749 | for b in bitset.iter().filter(move |b| maybe_live.contains(*b)) { | |
750 | self.bitset.0.insert(b); | |
751 | } | |
752 | } else { | |
753 | return false; | |
754 | } | |
755 | ||
756 | self.bitset.1.clear(); | |
757 | for b in borrowers { | |
758 | self.bitset.1.insert(*b); | |
759 | } | |
760 | ||
761 | self.bitset.0 == self.bitset.1 | |
762 | } | |
cdc7bbd5 XL |
763 | |
764 | fn is_alive_at(&mut self, local: mir::Local, at: mir::Location) -> bool { | |
765 | self.maybe_live.seek_after_primary_effect(at); | |
766 | self.maybe_live.contains(local) | |
767 | } | |
f20569fa | 768 | } |