clippy_utils/mir/
possible_borrower.rs

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

clippy_utils/mir/
possible_borrower.rs
