clippy_utils/mir/
possible_borrower.rs

Help
1use super::possible_origin::PossibleOriginVisitor;
2use super::transitive_relation::TransitiveRelation;
3use crate::ty::is_copy;
4use rustc_data_structures::fx::FxHashMap;
5use rustc_index::bit_set::DenseBitSet;
6use rustc_lint::LateContext;
7use rustc_middle::mir::visit::Visitor as _;
8use rustc_middle::mir::{self, Mutability};
9use rustc_middle::ty::{self, TyCtxt, TypeVisitor};
10use rustc_mir_dataflow::impls::MaybeStorageLive;
11use rustc_mir_dataflow::{Analysis, ResultsCursor};
12use std::borrow::Cow;
13use std::ops::ControlFlow;
14
15/// Collects the possible borrowers of each local.
16/// For example, `b = &a; c = &a;` will make `b` and (transitively) `c`
17/// possible borrowers of `a`.
18#[allow(clippy::module_name_repetitions)]
19struct PossibleBorrowerVisitor<'a, 'b, 'tcx> {
20    possible_borrower: TransitiveRelation,
21    body: &'b mir::Body<'tcx>,
22    cx: &'a LateContext<'tcx>,
23    possible_origin: FxHashMap<mir::Local, DenseBitSet<mir::Local>>,
24}
25
26impl<'a, 'b, 'tcx> PossibleBorrowerVisitor<'a, 'b, 'tcx> {
27    fn new(
28        cx: &'a LateContext<'tcx>,
29        body: &'b mir::Body<'tcx>,
30        possible_origin: FxHashMap<mir::Local, DenseBitSet<mir::Local>>,
31    ) -> Self {
32        Self {
33            possible_borrower: TransitiveRelation::default(),
34            body,
35            cx,
36            possible_origin,
37        }
38    }
39
40    fn into_map(
41        self,
42        cx: &'a LateContext<'tcx>,
43        maybe_live: ResultsCursor<'b, 'tcx, MaybeStorageLive<'tcx>>,
44    ) -> PossibleBorrowerMap<'b, 'tcx> {
45        let mut map = FxHashMap::default();
46        for row in (1..self.body.local_decls.len()).map(mir::Local::from_usize) {
47            if is_copy(cx, self.body.local_decls[row].ty) {
48                continue;
49            }
50
51            let mut borrowers = self.possible_borrower.reachable_from(row, self.body.local_decls.len());
52            borrowers.remove(mir::Local::from_usize(0));
53            if !borrowers.is_empty() {
54                map.insert(row, borrowers);
55            }
56        }
57
58        let bs = DenseBitSet::new_empty(self.body.local_decls.len());
59        PossibleBorrowerMap {
60            map,
61            maybe_live,
62            bitset: (bs.clone(), bs),
63        }
64    }
65}
66
67impl<'tcx> mir::visit::Visitor<'tcx> for PossibleBorrowerVisitor<'_, '_, 'tcx> {
68    fn visit_assign(&mut self, place: &mir::Place<'tcx>, rvalue: &mir::Rvalue<'_>, _location: mir::Location) {
69        let lhs = place.local;
70        match rvalue {
71            mir::Rvalue::Ref(_, _, borrowed) | mir::Rvalue::CopyForDeref(borrowed) => {
72                self.possible_borrower.add(borrowed.local, lhs);
73            },
74            other => {
75                if ContainsRegion
76                    .visit_ty(place.ty(&self.body.local_decls, self.cx.tcx).ty)
77                    .is_continue()
78                {
79                    return;
80                }
81                rvalue_locals(other, |rhs| {
82                    if lhs != rhs {
83                        self.possible_borrower.add(rhs, lhs);
84                    }
85                });
86            },
87        }
88    }
89
90    fn visit_terminator(&mut self, terminator: &mir::Terminator<'_>, _loc: mir::Location) {
91        if let mir::TerminatorKind::Call {
92            args,
93            destination: mir::Place { local: dest, .. },
94            ..
95        } = &terminator.kind
96        {
97            // TODO add doc
98            // If the call returns something with lifetimes,
99            // let's conservatively assume the returned value contains lifetime of all the arguments.
100            // For example, given `let y: Foo<'a> = foo(x)`, `y` is considered to be a possible borrower of `x`.
101
102            let mut immutable_borrowers = vec![];
103            let mut mutable_borrowers = vec![];
104
105            for op in args {
106                match &op.node {
107                    mir::Operand::Copy(p) | mir::Operand::Move(p) => {
108                        if let ty::Ref(_, _, Mutability::Mut) = self.body.local_decls[p.local].ty.kind() {
109                            mutable_borrowers.push(p.local);
110                        } else {
111                            immutable_borrowers.push(p.local);
112                        }
113                    },
114                    mir::Operand::Constant(..) => (),
115                }
116            }
117
118            let mut mutable_variables: Vec<mir::Local> = mutable_borrowers
119                .iter()
120                .filter_map(|r| self.possible_origin.get(r))
121                .flat_map(DenseBitSet::iter)
122                .collect();
123
124            if ContainsRegion.visit_ty(self.body.local_decls[*dest].ty).is_break() {
125                mutable_variables.push(*dest);
126            }
127
128            for y in mutable_variables {
129                for x in &immutable_borrowers {
130                    self.possible_borrower.add(*x, y);
131                }
132                for x in &mutable_borrowers {
133                    self.possible_borrower.add(*x, y);
134                }
135            }
136        }
137    }
138}
139
140struct ContainsRegion;
141
142impl TypeVisitor<TyCtxt<'_>> for ContainsRegion {
143    type Result = ControlFlow<()>;
144
145    fn visit_region(&mut self, _: ty::Region<'_>) -> Self::Result {
146        ControlFlow::Break(())
147    }
148}
149
150fn rvalue_locals(rvalue: &mir::Rvalue<'_>, mut visit: impl FnMut(mir::Local)) {
151    use rustc_middle::mir::Rvalue::{Aggregate, BinaryOp, Cast, Repeat, UnaryOp, Use};
152
153    let mut visit_op = |op: &mir::Operand<'_>| match op {
154        mir::Operand::Copy(p) | mir::Operand::Move(p) => visit(p.local),
155        mir::Operand::Constant(..) => (),
156    };
157
158    match rvalue {
159        Use(op) | Repeat(op, _) | Cast(_, op, _) | UnaryOp(_, op) => visit_op(op),
160        Aggregate(_, ops) => ops.iter().for_each(visit_op),
161        BinaryOp(_, box (lhs, rhs)) => {
162            visit_op(lhs);
163            visit_op(rhs);
164        },
165        _ => (),
166    }
167}
168
169/// Result of `PossibleBorrowerVisitor`.
170#[allow(clippy::module_name_repetitions)]
171pub struct PossibleBorrowerMap<'b, 'tcx> {
172    /// Mapping `Local -> its possible borrowers`
173    pub map: FxHashMap<mir::Local, DenseBitSet<mir::Local>>,
174    maybe_live: ResultsCursor<'b, 'tcx, MaybeStorageLive<'tcx>>,
175    // Caches to avoid allocation of `DenseBitSet` on every query
176    pub bitset: (DenseBitSet<mir::Local>, DenseBitSet<mir::Local>),
177}
178
179impl<'b, 'tcx> PossibleBorrowerMap<'b, 'tcx> {
180    pub fn new(cx: &LateContext<'tcx>, mir: &'b mir::Body<'tcx>) -> Self {
181        let possible_origin = {
182            let mut vis = PossibleOriginVisitor::new(mir);
183            vis.visit_body(mir);
184            vis.into_map(cx)
185        };
186        let maybe_storage_live_result =
187            MaybeStorageLive::new(Cow::Owned(DenseBitSet::new_empty(mir.local_decls.len())))
188                .iterate_to_fixpoint(cx.tcx, mir, Some("redundant_clone"))
189                .into_results_cursor(mir);
190        let mut vis = PossibleBorrowerVisitor::new(cx, mir, possible_origin);
191        vis.visit_body(mir);
192        vis.into_map(cx, maybe_storage_live_result)
193    }
194
195    /// Returns true if the set of borrowers of `borrowed` living at `at` matches with `borrowers`.
196    pub fn only_borrowers(&mut self, borrowers: &[mir::Local], borrowed: mir::Local, at: mir::Location) -> bool {
197        self.bounded_borrowers(borrowers, borrowers, borrowed, at)
198    }
199
200    /// Returns true if the set of borrowers of `borrowed` living at `at` includes at least `below`
201    /// but no more than `above`.
202    pub fn bounded_borrowers(
203        &mut self,
204        below: &[mir::Local],
205        above: &[mir::Local],
206        borrowed: mir::Local,
207        at: mir::Location,
208    ) -> bool {
209        self.maybe_live.seek_after_primary_effect(at);
210
211        self.bitset.0.clear();
212        let maybe_live = &mut self.maybe_live;
213        if let Some(bitset) = self.map.get(&borrowed) {
214            for b in bitset.iter().filter(move |b| maybe_live.get().contains(*b)) {
215                self.bitset.0.insert(b);
216            }
217        } else {
218            return false;
219        }
220
221        self.bitset.1.clear();
222        for b in below {
223            self.bitset.1.insert(*b);
224        }
225
226        if !self.bitset.0.superset(&self.bitset.1) {
227            return false;
228        }
229
230        for b in above {
231            self.bitset.0.remove(*b);
232        }
233
234        self.bitset.0.is_empty()
235    }
236
237    pub fn local_is_alive_at(&mut self, local: mir::Local, at: mir::Location) -> bool {
238        self.maybe_live.seek_after_primary_effect(at);
239        self.maybe_live.get().contains(local)
240    }
241}
clippy_utils/mir/possible_borrower.rs

clippy_utils/mir/
possible_borrower.rs
