1 //! See The Book chapter on the borrow checker for more details.
3 #![allow(non_camel_case_types)]
5 pub use LoanPathKind::*;
6 pub use LoanPathElem::*;
10 use rustc::hir::HirId;
13 use rustc::middle::borrowck::{BorrowCheckResult, SignalledError};
14 use rustc::hir::def_id::{DefId, LocalDefId};
15 use rustc::middle::mem_categorization as mc;
16 use rustc::middle::mem_categorization::Categorization;
17 use rustc::middle::region;
18 use rustc::middle::free_region::RegionRelations;
19 use rustc::ty::{self, Ty, TyCtxt};
20 use rustc::ty::query::Providers;
23 use std::cell::{Cell};
26 use std::hash::{Hash, Hasher};
31 use crate::dataflow::{DataFlowContext, BitwiseOperator, DataFlowOperator, KillFrom};
39 #[derive(Clone, Copy)]
40 pub struct LoanDataFlowOperator;
42 pub type LoanDataFlow<'tcx> = DataFlowContext<'tcx, LoanDataFlowOperator>;
44 pub fn check_crate(tcx: TyCtxt<'_>) {
45 tcx.par_body_owners(|body_owner_def_id| {
46 tcx.ensure().borrowck(body_owner_def_id);
50 pub fn provide(providers: &mut Providers<'_>) {
51 *providers = Providers {
57 /// Collection of conclusions determined via borrow checker analyses.
58 pub struct AnalysisData<'tcx> {
59 pub all_loans: Vec<Loan<'tcx>>,
60 pub loans: DataFlowContext<'tcx, LoanDataFlowOperator>,
61 pub move_data: move_data::FlowedMoveData<'tcx>,
64 fn borrowck(tcx: TyCtxt<'_>, owner_def_id: DefId) -> &BorrowCheckResult {
65 assert!(tcx.use_ast_borrowck() || tcx.migrate_borrowck());
67 debug!("borrowck(body_owner_def_id={:?})", owner_def_id);
69 let owner_id = tcx.hir().as_local_hir_id(owner_def_id).unwrap();
71 match tcx.hir().get(owner_id) {
73 // We get invoked with anything that has MIR, but some of
74 // those things (notably the synthesized constructors from
75 // tuple structs/variants) do not have an associated body
76 // and do not need borrowchecking.
77 return tcx.arena.alloc(BorrowCheckResult {
78 signalled_any_error: SignalledError::NoErrorsSeen,
84 let body_id = tcx.hir().body_owned_by(owner_id);
85 let tables = tcx.typeck_tables_of(owner_def_id);
86 let region_scope_tree = tcx.region_scope_tree(owner_def_id);
87 let body = tcx.hir().body(body_id);
88 let mut bccx = BorrowckCtxt {
94 signalled_any_error: Cell::new(SignalledError::NoErrorsSeen),
97 // Eventually, borrowck will always read the MIR, but at the
98 // moment we do not. So, for now, we always force MIR to be
99 // constructed for a given fn, since this may result in errors
100 // being reported and we want that to happen.
102 // Note that `mir_validated` is a "stealable" result; the
103 // thief, `optimized_mir()`, forces borrowck, so we know that
104 // is not yet stolen.
105 tcx.ensure().mir_validated(owner_def_id);
107 // option dance because you can't capture an uninitialized variable
110 if let Some(AnalysisData { all_loans,
112 move_data: flowed_moves }) =
113 build_borrowck_dataflow_data(&mut bccx, false, body_id,
115 cfg = Some(cfg::CFG::new(bccx.tcx, &body));
116 cfg.as_mut().unwrap()
119 check_loans::check_loans(&mut bccx, &loan_dfcx, &flowed_moves, &all_loans, body);
122 tcx.arena.alloc(BorrowCheckResult {
123 signalled_any_error: bccx.signalled_any_error.into_inner(),
127 fn build_borrowck_dataflow_data<'a, 'c, 'tcx, F>(this: &mut BorrowckCtxt<'a, 'tcx>,
128 force_analysis: bool,
129 body_id: hir::BodyId,
131 -> Option<AnalysisData<'tcx>>
132 where F: FnOnce(&mut BorrowckCtxt<'a, 'tcx>) -> &'c cfg::CFG
134 // Check the body of fn items.
135 let (all_loans, move_data) =
136 gather_loans::gather_loans_in_fn(this, body_id);
138 if !force_analysis && move_data.is_empty() && all_loans.is_empty() {
139 // large arrays of data inserted as constants can take a lot of
140 // time and memory to borrow-check - see issue #36799. However,
141 // they don't have places, so no borrow-check is actually needed.
142 // Recognize that case and skip borrow-checking.
143 debug!("skipping loan propagation for {:?} because of no loans", body_id);
146 debug!("propagating loans in {:?}", body_id);
149 let cfg = get_cfg(this);
151 DataFlowContext::new(this.tcx,
155 LoanDataFlowOperator,
157 for (loan_idx, loan) in all_loans.iter().enumerate() {
158 loan_dfcx.add_gen(loan.gen_scope.item_local_id(), loan_idx);
159 loan_dfcx.add_kill(KillFrom::ScopeEnd,
160 loan.kill_scope.item_local_id(),
163 loan_dfcx.add_kills_from_flow_exits(cfg);
164 loan_dfcx.propagate(cfg, this.body);
166 let flowed_moves = move_data::FlowedMoveData::new(move_data,
171 Some(AnalysisData { all_loans,
173 move_data:flowed_moves })
176 /// Accessor for introspective clients inspecting `AnalysisData` and
177 /// the `BorrowckCtxt` itself , e.g., the flowgraph visualizer.
178 pub fn build_borrowck_dataflow_data_for_fn<'a, 'tcx>(
180 body_id: hir::BodyId,
182 -> (BorrowckCtxt<'a, 'tcx>, AnalysisData<'tcx>)
184 let owner_id = tcx.hir().body_owner(body_id);
185 let owner_def_id = tcx.hir().local_def_id(owner_id);
186 let tables = tcx.typeck_tables_of(owner_def_id);
187 let region_scope_tree = tcx.region_scope_tree(owner_def_id);
188 let body = tcx.hir().body(body_id);
189 let mut bccx = BorrowckCtxt {
195 signalled_any_error: Cell::new(SignalledError::NoErrorsSeen),
198 let dataflow_data = build_borrowck_dataflow_data(&mut bccx, true, body_id, |_| cfg);
199 (bccx, dataflow_data.unwrap())
202 // ----------------------------------------------------------------------
205 pub struct BorrowckCtxt<'a, 'tcx> {
208 // tables for the current thing we are checking; set to
209 // Some in `borrowck_fn` and cleared later
210 tables: &'a ty::TypeckTables<'tcx>,
212 region_scope_tree: &'tcx region::ScopeTree,
216 body: &'tcx hir::Body,
218 signalled_any_error: Cell<SignalledError>,
222 impl<'a, 'tcx: 'a> BorrowckCtxt<'a, 'tcx> {
223 fn signal_error(&self) {
224 self.signalled_any_error.set(SignalledError::SawSomeError);
228 ///////////////////////////////////////////////////////////////////////////
229 // Loans and loan paths
231 /// Record of a loan that was issued.
232 pub struct Loan<'tcx> {
234 loan_path: Rc<LoanPath<'tcx>>,
235 kind: ty::BorrowKind,
236 restricted_paths: Vec<Rc<LoanPath<'tcx>>>,
238 /// gen_scope indicates where loan is introduced. Typically the
239 /// loan is introduced at the point of the borrow, but in some
240 /// cases, notably method arguments, the loan may be introduced
241 /// only later, once it comes into scope. See also
242 /// `GatherLoanCtxt::compute_gen_scope`.
243 gen_scope: region::Scope,
245 /// kill_scope indicates when the loan goes out of scope. This is
246 /// either when the lifetime expires or when the local variable
247 /// which roots the loan-path goes out of scope, whichever happens
248 /// faster. See also `GatherLoanCtxt::compute_kill_scope`.
249 kill_scope: region::Scope,
252 impl<'tcx> Loan<'tcx> {
253 pub fn loan_path(&self) -> Rc<LoanPath<'tcx>> {
254 self.loan_path.clone()
259 pub struct LoanPath<'tcx> {
260 kind: LoanPathKind<'tcx>,
264 impl<'tcx> PartialEq for LoanPath<'tcx> {
265 fn eq(&self, that: &LoanPath<'tcx>) -> bool {
266 self.kind == that.kind
270 impl<'tcx> Hash for LoanPath<'tcx> {
271 fn hash<H: Hasher>(&self, state: &mut H) {
272 self.kind.hash(state);
276 #[derive(PartialEq, Eq, Hash, Debug)]
277 pub enum LoanPathKind<'tcx> {
278 LpVar(hir::HirId), // `x` in README.md
279 LpUpvar(ty::UpvarId), // `x` captured by-value into closure
280 LpDowncast(Rc<LoanPath<'tcx>>, DefId), // `x` downcast to particular enum variant
281 LpExtend(Rc<LoanPath<'tcx>>, mc::MutabilityCategory, LoanPathElem<'tcx>)
284 impl<'tcx> LoanPath<'tcx> {
285 fn new(kind: LoanPathKind<'tcx>, ty: Ty<'tcx>) -> LoanPath<'tcx> {
286 LoanPath { kind: kind, ty: ty }
289 fn to_type(&self) -> Ty<'tcx> { self.ty }
292 // FIXME (pnkfelix): See discussion here
293 // https://github.com/pnkfelix/rust/commit/
294 // b2b39e8700e37ad32b486b9a8409b50a8a53aa51#commitcomment-7892003
295 const DOWNCAST_PRINTED_OPERATOR: &'static str = " as ";
297 // A local, "cleaned" version of `mc::InteriorKind` that drops
298 // information that is not relevant to loan-path analysis. (In
299 // particular, the distinction between how precisely an array-element
300 // is tracked is irrelevant here.)
301 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
302 pub enum InteriorKind {
303 InteriorField(mc::FieldIndex),
307 trait ToInteriorKind { fn cleaned(self) -> InteriorKind; }
308 impl ToInteriorKind for mc::InteriorKind {
309 fn cleaned(self) -> InteriorKind {
311 mc::InteriorField(name) => InteriorField(name),
312 mc::InteriorElement(_) => InteriorElement,
318 // - a pointer dereference (`*P` in README.md)
319 // - a field reference, with an optional definition of the containing
320 // enum variant (`P.f` in README.md)
321 // `DefId` is present when the field is part of struct that is in
322 // a variant of an enum. For instance in:
323 // `enum E { X { foo: u32 }, Y { foo: u32 }}`
324 // each `foo` is qualified by the definitition id of the variant (`X` or `Y`).
325 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
326 pub enum LoanPathElem<'tcx> {
327 LpDeref(mc::PointerKind<'tcx>),
328 LpInterior(Option<DefId>, InteriorKind),
331 fn closure_to_block(closure_id: LocalDefId, tcx: TyCtxt<'_>) -> HirId {
332 let closure_id = tcx.hir().local_def_id_to_hir_id(closure_id);
333 match tcx.hir().get(closure_id) {
334 Node::Expr(expr) => match expr.node {
335 hir::ExprKind::Closure(.., body_id, _, _) => {
339 bug!("encountered non-closure id: {}", closure_id)
342 _ => bug!("encountered non-expr id: {}", closure_id)
346 impl<'a, 'tcx> LoanPath<'tcx> {
347 pub fn kill_scope(&self, bccx: &BorrowckCtxt<'a, 'tcx>) -> region::Scope {
350 bccx.region_scope_tree.var_scope(hir_id.local_id)
352 LpUpvar(upvar_id) => {
353 let block_id = closure_to_block(upvar_id.closure_expr_id, bccx.tcx);
354 region::Scope { id: block_id.local_id, data: region::ScopeData::Node }
356 LpDowncast(ref base, _) |
357 LpExtend(ref base, ..) => base.kill_scope(bccx),
362 // Avoid "cannot borrow immutable field `self.x` as mutable" as that implies that a field *can* be
363 // mutable independently of the struct it belongs to. (#35937)
364 pub fn opt_loan_path_is_field<'tcx>(cmt: &mc::cmt_<'tcx>) -> (Option<Rc<LoanPath<'tcx>>>, bool) {
365 let new_lp = |v: LoanPathKind<'tcx>| Rc::new(LoanPath::new(v, cmt.ty));
368 Categorization::Rvalue(..) |
369 Categorization::ThreadLocal(..) |
370 Categorization::StaticItem => {
374 Categorization::Local(id) => {
375 (Some(new_lp(LpVar(id))), false)
378 Categorization::Upvar(mc::Upvar { id, .. }) => {
379 (Some(new_lp(LpUpvar(id))), false)
382 Categorization::Deref(ref cmt_base, pk) => {
383 let lp = opt_loan_path_is_field(cmt_base);
385 new_lp(LpExtend(lp, cmt.mutbl, LpDeref(pk)))
389 Categorization::Interior(ref cmt_base, ik) => {
390 (opt_loan_path(cmt_base).map(|lp| {
391 let opt_variant_id = match cmt_base.cat {
392 Categorization::Downcast(_, did) => Some(did),
395 new_lp(LpExtend(lp, cmt.mutbl, LpInterior(opt_variant_id, ik.cleaned())))
399 Categorization::Downcast(ref cmt_base, variant_def_id) => {
400 let lp = opt_loan_path_is_field(cmt_base);
402 new_lp(LpDowncast(lp, variant_def_id))
408 /// Computes the `LoanPath` (if any) for a `cmt`.
409 /// Note that this logic is somewhat duplicated in
410 /// the method `compute()` found in `gather_loans::restrictions`,
411 /// which allows it to share common loan path pieces as it
412 /// traverses the CMT.
413 pub fn opt_loan_path<'tcx>(cmt: &mc::cmt_<'tcx>) -> Option<Rc<LoanPath<'tcx>>> {
414 opt_loan_path_is_field(cmt).0
417 ///////////////////////////////////////////////////////////////////////////
420 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
421 pub fn is_subregion_of(&self,
422 r_sub: ty::Region<'tcx>,
423 r_sup: ty::Region<'tcx>)
426 let region_rels = RegionRelations::new(self.tcx,
428 &self.region_scope_tree,
429 &self.tables.free_region_map);
430 region_rels.is_subregion_of(r_sub, r_sup)
433 pub fn append_loan_path_to_string(&self,
434 loan_path: &LoanPath<'tcx>,
436 match loan_path.kind {
437 LpUpvar(ty::UpvarId { var_path: ty::UpvarPath { hir_id: id }, closure_expr_id: _ }) => {
438 out.push_str(&self.tcx.hir().name(id).as_str());
441 out.push_str(&self.tcx.hir().name(id).as_str());
444 LpDowncast(ref lp_base, variant_def_id) => {
446 self.append_loan_path_to_string(&lp_base, out);
447 out.push_str(DOWNCAST_PRINTED_OPERATOR);
448 out.push_str(&self.tcx.def_path_str(variant_def_id));
452 LpExtend(ref lp_base, _, LpInterior(_, InteriorField(mc::FieldIndex(_, info)))) => {
453 self.append_autoderefd_loan_path_to_string(&lp_base, out);
455 out.push_str(&info.as_str());
458 LpExtend(ref lp_base, _, LpInterior(_, InteriorElement)) => {
459 self.append_autoderefd_loan_path_to_string(&lp_base, out);
460 out.push_str("[..]");
463 LpExtend(ref lp_base, _, LpDeref(_)) => {
465 self.append_loan_path_to_string(&lp_base, out);
470 pub fn append_autoderefd_loan_path_to_string(&self,
471 loan_path: &LoanPath<'tcx>,
473 match loan_path.kind {
474 LpExtend(ref lp_base, _, LpDeref(_)) => {
475 // For a path like `(*x).f` or `(*x)[3]`, autoderef
476 // rules would normally allow users to omit the `*x`.
477 // So just serialize such paths to `x.f` or x[3]` respectively.
478 self.append_autoderefd_loan_path_to_string(&lp_base, out)
481 LpDowncast(ref lp_base, variant_def_id) => {
483 self.append_autoderefd_loan_path_to_string(&lp_base, out);
484 out.push_str(DOWNCAST_PRINTED_OPERATOR);
485 out.push_str(&self.tcx.def_path_str(variant_def_id));
489 LpVar(..) | LpUpvar(..) | LpExtend(.., LpInterior(..)) => {
490 self.append_loan_path_to_string(loan_path, out)
495 pub fn loan_path_to_string(&self, loan_path: &LoanPath<'tcx>) -> String {
496 let mut result = String::new();
497 self.append_loan_path_to_string(loan_path, &mut result);
501 pub fn cmt_to_cow_str(&self, cmt: &mc::cmt_<'tcx>) -> Cow<'static, str> {
502 cmt.descriptive_string(self.tcx)
505 pub fn cmt_to_path_or_string(&self, cmt: &mc::cmt_<'tcx>) -> String {
506 match opt_loan_path(cmt) {
507 Some(lp) => format!("`{}`", self.loan_path_to_string(&lp)),
508 None => self.cmt_to_cow_str(cmt).into_owned(),
513 impl BitwiseOperator for LoanDataFlowOperator {
515 fn join(&self, succ: usize, pred: usize) -> usize {
516 succ | pred // loans from both preds are in scope
520 impl DataFlowOperator for LoanDataFlowOperator {
522 fn initial_value(&self) -> bool {
523 false // no loans in scope by default
527 impl fmt::Debug for InteriorKind {
528 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
530 InteriorField(mc::FieldIndex(_, info)) => write!(f, "{}", info),
531 InteriorElement => write!(f, "[]"),
536 impl<'tcx> fmt::Debug for Loan<'tcx> {
537 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
538 write!(f, "Loan_{}({:?}, {:?}, {:?}-{:?}, {:?})",
544 self.restricted_paths)
548 impl<'tcx> fmt::Debug for LoanPath<'tcx> {
549 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
552 write!(f, "$({})", ty::tls::with(|tcx| tcx.hir().node_to_string(id)))
555 LpUpvar(ty::UpvarId{ var_path: ty::UpvarPath {hir_id: var_id}, closure_expr_id }) => {
556 let s = ty::tls::with(|tcx| {
557 tcx.hir().node_to_string(var_id)
559 write!(f, "$({} captured by id={:?})", s, closure_expr_id)
562 LpDowncast(ref lp, variant_def_id) => {
563 let variant_str = if variant_def_id.is_local() {
564 ty::tls::with(|tcx| tcx.def_path_str(variant_def_id))
566 format!("{:?}", variant_def_id)
568 write!(f, "({:?}{}{})", lp, DOWNCAST_PRINTED_OPERATOR, variant_str)
571 LpExtend(ref lp, _, LpDeref(_)) => {
572 write!(f, "{:?}.*", lp)
575 LpExtend(ref lp, _, LpInterior(_, ref interior)) => {
576 write!(f, "{:?}.{:?}", lp, interior)
582 impl<'tcx> fmt::Display for LoanPath<'tcx> {
583 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
586 write!(f, "$({})", ty::tls::with(|tcx| tcx.hir().hir_to_user_string(id)))
589 LpUpvar(ty::UpvarId{ var_path: ty::UpvarPath { hir_id }, closure_expr_id: _ }) => {
590 let s = ty::tls::with(|tcx| {
591 tcx.hir().node_to_string(hir_id)
593 write!(f, "$({} captured by closure)", s)
596 LpDowncast(ref lp, variant_def_id) => {
597 let variant_str = if variant_def_id.is_local() {
598 ty::tls::with(|tcx| tcx.def_path_str(variant_def_id))
600 format!("{:?}", variant_def_id)
602 write!(f, "({}{}{})", lp, DOWNCAST_PRINTED_OPERATOR, variant_str)
605 LpExtend(ref lp, _, LpDeref(_)) => {
606 write!(f, "{}.*", lp)
609 LpExtend(ref lp, _, LpInterior(_, ref interior)) => {
610 write!(f, "{}.{:?}", lp, interior)