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

clippy_utils/mir/
possible_borrower.rs
