]> git.proxmox.com Git - rustc.git/blame - src/librustc_borrowck/borrowck/gather_loans/mod.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_borrowck / borrowck / gather_loans / mod.rs
CommitLineData
1a4d82fc
JJ
1// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11// ----------------------------------------------------------------------
12// Gathering loans
13//
14// The borrow check proceeds in two phases. In phase one, we gather the full
15// set of loans that are required at any point. These are sorted according to
16// their associated scopes. In phase two, checking loans, we will then make
17// sure that all of these loans are honored.
18
19use borrowck::*;
20use borrowck::move_data::MoveData;
21use rustc::middle::expr_use_visitor as euv;
54a0048b 22use rustc::infer;
1a4d82fc 23use rustc::middle::mem_categorization as mc;
92a42be0 24use rustc::middle::mem_categorization::Categorization;
1a4d82fc 25use rustc::middle::region;
54a0048b
SL
26use rustc::ty::{self, TyCtxt};
27use rustc::traits::ProjectionMode;
62682a34 28
1a4d82fc
JJ
29use syntax::ast;
30use syntax::codemap::Span;
e9174d1e 31use syntax::ast::NodeId;
54a0048b
SL
32use rustc::hir;
33use rustc::hir::Expr;
34use rustc::hir::intravisit;
35use rustc::hir::intravisit::Visitor;
1a4d82fc 36
9cc50fc6
SL
37use self::restrictions::RestrictionResult;
38
1a4d82fc
JJ
39mod lifetime;
40mod restrictions;
41mod gather_moves;
42mod move_error;
43
44pub fn gather_loans_in_fn<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
45 fn_id: NodeId,
e9174d1e
SL
46 decl: &hir::FnDecl,
47 body: &hir::Block)
1a4d82fc
JJ
48 -> (Vec<Loan<'tcx>>,
49 move_data::MoveData<'tcx>) {
50 let mut glcx = GatherLoanCtxt {
51 bccx: bccx,
52 all_loans: Vec::new(),
e9174d1e 53 item_ub: bccx.tcx.region_maps.node_extent(body.id),
1a4d82fc
JJ
54 move_data: MoveData::new(),
55 move_error_collector: move_error::MoveErrorCollector::new(),
56 };
57
58 let param_env = ty::ParameterEnvironment::for_item(bccx.tcx, fn_id);
54a0048b
SL
59 let infcx = infer::new_infer_ctxt(bccx.tcx,
60 &bccx.tcx.tables,
61 Some(param_env),
62 ProjectionMode::AnyFinal);
1a4d82fc 63 {
c1a9b12d 64 let mut euv = euv::ExprUseVisitor::new(&mut glcx, &infcx);
1a4d82fc
JJ
65 euv.walk_fn(decl, body);
66 }
67
68 glcx.report_potential_errors();
69 let GatherLoanCtxt { all_loans, move_data, .. } = glcx;
70 (all_loans, move_data)
71}
72
73struct GatherLoanCtxt<'a, 'tcx: 'a> {
74 bccx: &'a BorrowckCtxt<'a, 'tcx>,
75 move_data: move_data::MoveData<'tcx>,
76 move_error_collector: move_error::MoveErrorCollector<'tcx>,
77 all_loans: Vec<Loan<'tcx>>,
78 /// `item_ub` is used as an upper-bound on the lifetime whenever we
79 /// ask for the scope of an expression categorized as an upvar.
80 item_ub: region::CodeExtent,
81}
82
83impl<'a, 'tcx> euv::Delegate<'tcx> for GatherLoanCtxt<'a, 'tcx> {
84 fn consume(&mut self,
85 consume_id: ast::NodeId,
86 _consume_span: Span,
87 cmt: mc::cmt<'tcx>,
88 mode: euv::ConsumeMode) {
62682a34
SL
89 debug!("consume(consume_id={}, cmt={:?}, mode={:?})",
90 consume_id, cmt, mode);
1a4d82fc
JJ
91
92 match mode {
93 euv::Move(move_reason) => {
94 gather_moves::gather_move_from_expr(
92a42be0 95 self.bccx, &self.move_data, &mut self.move_error_collector,
1a4d82fc
JJ
96 consume_id, cmt, move_reason);
97 }
98 euv::Copy => { }
99 }
100 }
101
102 fn matched_pat(&mut self,
e9174d1e 103 matched_pat: &hir::Pat,
1a4d82fc
JJ
104 cmt: mc::cmt<'tcx>,
105 mode: euv::MatchMode) {
62682a34
SL
106 debug!("matched_pat(matched_pat={:?}, cmt={:?}, mode={:?})",
107 matched_pat,
108 cmt,
1a4d82fc
JJ
109 mode);
110
92a42be0 111 if let Categorization::Downcast(..) = cmt.cat {
1a4d82fc 112 gather_moves::gather_match_variant(
92a42be0 113 self.bccx, &self.move_data, &mut self.move_error_collector,
1a4d82fc
JJ
114 matched_pat, cmt, mode);
115 }
116 }
117
118 fn consume_pat(&mut self,
e9174d1e 119 consume_pat: &hir::Pat,
1a4d82fc
JJ
120 cmt: mc::cmt<'tcx>,
121 mode: euv::ConsumeMode) {
62682a34
SL
122 debug!("consume_pat(consume_pat={:?}, cmt={:?}, mode={:?})",
123 consume_pat,
124 cmt,
1a4d82fc
JJ
125 mode);
126
127 match mode {
128 euv::Copy => { return; }
129 euv::Move(_) => { }
130 }
131
132 gather_moves::gather_move_from_pat(
92a42be0 133 self.bccx, &self.move_data, &mut self.move_error_collector,
1a4d82fc
JJ
134 consume_pat, cmt);
135 }
136
137 fn borrow(&mut self,
138 borrow_id: ast::NodeId,
139 borrow_span: Span,
140 cmt: mc::cmt<'tcx>,
141 loan_region: ty::Region,
142 bk: ty::BorrowKind,
143 loan_cause: euv::LoanCause)
144 {
62682a34 145 debug!("borrow(borrow_id={}, cmt={:?}, loan_region={:?}, \
1a4d82fc 146 bk={:?}, loan_cause={:?})",
62682a34 147 borrow_id, cmt, loan_region,
1a4d82fc
JJ
148 bk, loan_cause);
149
150 self.guarantee_valid(borrow_id,
151 borrow_span,
152 cmt,
153 bk,
154 loan_region,
155 loan_cause);
156 }
157
158 fn mutate(&mut self,
159 assignment_id: ast::NodeId,
160 assignment_span: Span,
161 assignee_cmt: mc::cmt<'tcx>,
162 mode: euv::MutateMode)
163 {
c1a9b12d
SL
164 self.guarantee_assignment_valid(assignment_id,
165 assignment_span,
166 assignee_cmt,
167 mode);
1a4d82fc
JJ
168 }
169
170 fn decl_without_init(&mut self, id: ast::NodeId, span: Span) {
171 gather_moves::gather_decl(self.bccx, &self.move_data, id, span, id);
172 }
173}
174
c34b1796 175/// Implements the A-* rules in README.md.
1a4d82fc
JJ
176fn check_aliasability<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
177 borrow_span: Span,
c1a9b12d 178 loan_cause: AliasableViolationKind,
1a4d82fc
JJ
179 cmt: mc::cmt<'tcx>,
180 req_kind: ty::BorrowKind)
181 -> Result<(),()> {
182
c34b1796
AL
183 let aliasability = cmt.freely_aliasable(bccx.tcx);
184 debug!("check_aliasability aliasability={:?} req_kind={:?}",
185 aliasability, req_kind);
186
187 match (aliasability, req_kind) {
188 (mc::Aliasability::NonAliasable, _) => {
1a4d82fc
JJ
189 /* Uniquely accessible path -- OK for `&` and `&mut` */
190 Ok(())
191 }
62682a34
SL
192 (mc::Aliasability::FreelyAliasable(mc::AliasableStatic), ty::ImmBorrow) => {
193 // Borrow of an immutable static item.
194 Ok(())
1a4d82fc 195 }
62682a34 196 (mc::Aliasability::FreelyAliasable(mc::AliasableStaticMut), _) => {
1a4d82fc
JJ
197 // Even touching a static mut is considered unsafe. We assume the
198 // user knows what they're doing in these cases.
199 Ok(())
200 }
c34b1796
AL
201 (mc::Aliasability::ImmutableUnique(_), ty::MutBorrow) => {
202 bccx.report_aliasability_violation(
203 borrow_span,
c1a9b12d 204 loan_cause,
c34b1796
AL
205 mc::AliasableReason::UnaliasableImmutable);
206 Err(())
207 }
208 (mc::Aliasability::FreelyAliasable(alias_cause), ty::UniqueImmBorrow) |
209 (mc::Aliasability::FreelyAliasable(alias_cause), ty::MutBorrow) => {
1a4d82fc
JJ
210 bccx.report_aliasability_violation(
211 borrow_span,
c1a9b12d 212 loan_cause,
1a4d82fc
JJ
213 alias_cause);
214 Err(())
215 }
216 (_, _) => {
217 Ok(())
218 }
219 }
220}
221
c1a9b12d
SL
222/// Implements the M-* rules in README.md.
223fn check_mutability<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
224 borrow_span: Span,
225 cause: AliasableViolationKind,
226 cmt: mc::cmt<'tcx>,
227 req_kind: ty::BorrowKind)
228 -> Result<(),()> {
229 debug!("check_mutability(cause={:?} cmt={:?} req_kind={:?}",
230 cause, cmt, req_kind);
231 match req_kind {
232 ty::UniqueImmBorrow | ty::ImmBorrow => {
233 match cmt.mutbl {
234 // I am intentionally leaving this here to help
235 // refactoring if, in the future, we should add new
236 // kinds of mutability.
237 mc::McImmutable | mc::McDeclared | mc::McInherited => {
238 // both imm and mut data can be lent as imm;
239 // for mutable data, this is a freeze
240 Ok(())
241 }
242 }
243 }
244
245 ty::MutBorrow => {
246 // Only mutable data can be lent as mutable.
247 if !cmt.mutbl.is_mutable() {
248 Err(bccx.report(BckError { span: borrow_span,
249 cause: cause,
250 cmt: cmt,
251 code: err_mutbl }))
252 } else {
253 Ok(())
254 }
255 }
256 }
257}
258
1a4d82fc 259impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
54a0048b 260 pub fn tcx(&self) -> &'a TyCtxt<'tcx> { self.bccx.tcx }
1a4d82fc 261
c1a9b12d
SL
262 /// Guarantees that `cmt` is assignable, or reports an error.
263 fn guarantee_assignment_valid(&mut self,
264 assignment_id: ast::NodeId,
265 assignment_span: Span,
266 cmt: mc::cmt<'tcx>,
267 mode: euv::MutateMode) {
268
269 let opt_lp = opt_loan_path(&cmt);
270 debug!("guarantee_assignment_valid(assignment_id={}, cmt={:?}) opt_lp={:?}",
271 assignment_id, cmt, opt_lp);
272
92a42be0 273 if let Categorization::Local(..) = cmt.cat {
c1a9b12d
SL
274 // Only re-assignments to locals require it to be
275 // mutable - this is checked in check_loans.
276 } else {
277 // Check that we don't allow assignments to non-mutable data.
278 if check_mutability(self.bccx, assignment_span, MutabilityViolation,
279 cmt.clone(), ty::MutBorrow).is_err() {
280 return; // reported an error, no sense in reporting more.
281 }
282 }
283
284 // Check that we don't allow assignments to aliasable data
285 if check_aliasability(self.bccx, assignment_span, MutabilityViolation,
286 cmt.clone(), ty::MutBorrow).is_err() {
287 return; // reported an error, no sense in reporting more.
288 }
289
290 match opt_lp {
291 Some(lp) => {
92a42be0 292 if let Categorization::Local(..) = cmt.cat {
c1a9b12d
SL
293 // Only re-assignments to locals require it to be
294 // mutable - this is checked in check_loans.
295 } else {
296 self.mark_loan_path_as_mutated(&lp);
297 }
298 gather_moves::gather_assignment(self.bccx, &self.move_data,
299 assignment_id, assignment_span,
300 lp, cmt.id, mode);
301 }
302 None => {
303 // This can occur with e.g. `*foo() = 5`. In such
304 // cases, there is no need to check for conflicts
305 // with moves etc, just ignore.
306 }
307 }
308 }
309
1a4d82fc
JJ
310 /// Guarantees that `addr_of(cmt)` will be valid for the duration of `static_scope_r`, or
311 /// reports an error. This may entail taking out loans, which will be added to the
312 /// `req_loan_map`.
313 fn guarantee_valid(&mut self,
314 borrow_id: ast::NodeId,
315 borrow_span: Span,
316 cmt: mc::cmt<'tcx>,
317 req_kind: ty::BorrowKind,
318 loan_region: ty::Region,
319 cause: euv::LoanCause) {
62682a34 320 debug!("guarantee_valid(borrow_id={}, cmt={:?}, \
1a4d82fc
JJ
321 req_mutbl={:?}, loan_region={:?})",
322 borrow_id,
62682a34 323 cmt,
1a4d82fc
JJ
324 req_kind,
325 loan_region);
326
327 // a loan for the empty region can never be dereferenced, so
328 // it is always safe
329 if loan_region == ty::ReEmpty {
330 return;
331 }
332
333 // Check that the lifetime of the borrow does not exceed
334 // the lifetime of the data being borrowed.
335 if lifetime::guarantee_lifetime(self.bccx, self.item_ub,
336 borrow_span, cause, cmt.clone(), loan_region,
337 req_kind).is_err() {
338 return; // reported an error, no sense in reporting more.
339 }
340
341 // Check that we don't allow mutable borrows of non-mutable data.
c1a9b12d 342 if check_mutability(self.bccx, borrow_span, BorrowViolation(cause),
1a4d82fc
JJ
343 cmt.clone(), req_kind).is_err() {
344 return; // reported an error, no sense in reporting more.
345 }
346
347 // Check that we don't allow mutable borrows of aliasable data.
c1a9b12d 348 if check_aliasability(self.bccx, borrow_span, BorrowViolation(cause),
1a4d82fc
JJ
349 cmt.clone(), req_kind).is_err() {
350 return; // reported an error, no sense in reporting more.
351 }
352
353 // Compute the restrictions that are required to enforce the
354 // loan is safe.
355 let restr = restrictions::compute_restrictions(
356 self.bccx, borrow_span, cause,
357 cmt.clone(), loan_region);
358
359 debug!("guarantee_valid(): restrictions={:?}", restr);
360
361 // Create the loan record (if needed).
362 let loan = match restr {
9cc50fc6 363 RestrictionResult::Safe => {
1a4d82fc
JJ
364 // No restrictions---no loan record necessary
365 return;
366 }
367
9cc50fc6 368 RestrictionResult::SafeIf(loan_path, restricted_paths) => {
1a4d82fc
JJ
369 let loan_scope = match loan_region {
370 ty::ReScope(scope) => scope,
371
e9174d1e
SL
372 ty::ReFree(ref fr) => fr.scope,
373
374 ty::ReStatic => self.item_ub,
1a4d82fc
JJ
375
376 ty::ReEmpty |
377 ty::ReLateBound(..) |
378 ty::ReEarlyBound(..) |
e9174d1e
SL
379 ty::ReVar(..) |
380 ty::ReSkolemized(..) => {
54a0048b 381 span_bug!(
1a4d82fc 382 cmt.span,
54a0048b
SL
383 "invalid borrow lifetime: {:?}",
384 loan_region);
1a4d82fc
JJ
385 }
386 };
387 debug!("loan_scope = {:?}", loan_scope);
388
e9174d1e 389 let borrow_scope = self.tcx().region_maps.node_extent(borrow_id);
1a4d82fc
JJ
390 let gen_scope = self.compute_gen_scope(borrow_scope, loan_scope);
391 debug!("gen_scope = {:?}", gen_scope);
392
7453a54e 393 let kill_scope = self.compute_kill_scope(loan_scope, &loan_path);
1a4d82fc
JJ
394 debug!("kill_scope = {:?}", kill_scope);
395
396 if req_kind == ty::MutBorrow {
7453a54e 397 self.mark_loan_path_as_mutated(&loan_path);
1a4d82fc
JJ
398 }
399
400 Loan {
401 index: self.all_loans.len(),
402 loan_path: loan_path,
403 kind: req_kind,
404 gen_scope: gen_scope,
405 kill_scope: kill_scope,
406 span: borrow_span,
407 restricted_paths: restricted_paths,
408 cause: cause,
409 }
410 }
411 };
412
62682a34
SL
413 debug!("guarantee_valid(borrow_id={}), loan={:?}",
414 borrow_id, loan);
1a4d82fc
JJ
415
416 // let loan_path = loan.loan_path;
417 // let loan_gen_scope = loan.gen_scope;
418 // let loan_kill_scope = loan.kill_scope;
419 self.all_loans.push(loan);
420
421 // if loan_gen_scope != borrow_id {
422 // FIXME(#6268) Nested method calls
423 //
424 // Typically, the scope of the loan includes the point at
425 // which the loan is originated. This
426 // This is a subtle case. See the test case
427 // <compile-fail/borrowck-bad-nested-calls-free.rs>
428 // to see what we are guarding against.
429
430 //let restr = restrictions::compute_restrictions(
431 // self.bccx, borrow_span, cmt, RESTR_EMPTY);
432 //let loan = {
433 // let all_loans = &mut *self.all_loans; // FIXME(#5074)
434 // Loan {
435 // index: all_loans.len(),
436 // loan_path: loan_path,
437 // cmt: cmt,
438 // mutbl: ConstMutability,
439 // gen_scope: borrow_id,
440 // kill_scope: kill_scope,
441 // span: borrow_span,
442 // restrictions: restrictions
443 // }
444 // }
1a4d82fc
JJ
445 }
446
447 pub fn mark_loan_path_as_mutated(&self, loan_path: &LoanPath) {
448 //! For mutable loans of content whose mutability derives
449 //! from a local variable, mark the mutability decl as necessary.
450
451 match loan_path.kind {
452 LpVar(local_id) |
453 LpUpvar(ty::UpvarId{ var_id: local_id, closure_expr_id: _ }) => {
454 self.tcx().used_mut_nodes.borrow_mut().insert(local_id);
455 }
456 LpDowncast(ref base, _) |
457 LpExtend(ref base, mc::McInherited, _) |
458 LpExtend(ref base, mc::McDeclared, _) => {
7453a54e 459 self.mark_loan_path_as_mutated(&base);
1a4d82fc
JJ
460 }
461 LpExtend(_, mc::McImmutable, _) => {
462 // Nothing to do.
463 }
464 }
465 }
466
467 pub fn compute_gen_scope(&self,
468 borrow_scope: region::CodeExtent,
469 loan_scope: region::CodeExtent)
470 -> region::CodeExtent {
471 //! Determine when to introduce the loan. Typically the loan
472 //! is introduced at the point of the borrow, but in some cases,
473 //! notably method arguments, the loan may be introduced only
474 //! later, once it comes into scope.
475
476 if self.bccx.tcx.region_maps.is_subscope_of(borrow_scope, loan_scope) {
477 borrow_scope
478 } else {
479 loan_scope
480 }
481 }
482
483 pub fn compute_kill_scope(&self, loan_scope: region::CodeExtent, lp: &LoanPath<'tcx>)
484 -> region::CodeExtent {
485 //! Determine when the loan restrictions go out of scope.
486 //! This is either when the lifetime expires or when the
487 //! local variable which roots the loan-path goes out of scope,
488 //! whichever happens faster.
489 //!
490 //! It may seem surprising that we might have a loan region
491 //! larger than the variable which roots the loan-path; this can
492 //! come about when variables of `&mut` type are re-borrowed,
493 //! as in this example:
494 //!
92a42be0
SL
495 //! struct Foo { counter: u32 }
496 //!
497 //! fn counter<'a>(v: &'a mut Foo) -> &'a mut u32 {
1a4d82fc
JJ
498 //! &mut v.counter
499 //! }
500 //!
501 //! In this case, the reference (`'a`) outlives the
502 //! variable `v` that hosts it. Note that this doesn't come up
503 //! with immutable `&` pointers, because borrows of such pointers
504 //! do not require restrictions and hence do not cause a loan.
505
506 let lexical_scope = lp.kill_scope(self.bccx.tcx);
507 let rm = &self.bccx.tcx.region_maps;
508 if rm.is_subscope_of(lexical_scope, loan_scope) {
509 lexical_scope
510 } else {
511 assert!(self.bccx.tcx.region_maps.is_subscope_of(loan_scope, lexical_scope));
512 loan_scope
513 }
514 }
515
516 pub fn report_potential_errors(&self) {
517 self.move_error_collector.report_potential_errors(self.bccx);
518 }
519}
520
521/// Context used while gathering loans on static initializers
522///
523/// This visitor walks static initializer's expressions and makes
524/// sure the loans being taken are sound.
525struct StaticInitializerCtxt<'a, 'tcx: 'a> {
526 bccx: &'a BorrowckCtxt<'a, 'tcx>,
527}
528
529impl<'a, 'tcx, 'v> Visitor<'v> for StaticInitializerCtxt<'a, 'tcx> {
530 fn visit_expr(&mut self, ex: &Expr) {
e9174d1e 531 if let hir::ExprAddrOf(mutbl, ref base) = ex.node {
54a0048b
SL
532 let infcx = infer::new_infer_ctxt(self.bccx.tcx,
533 &self.bccx.tcx.tables,
534 None,
535 ProjectionMode::AnyFinal);
c1a9b12d 536 let mc = mc::MemCategorizationContext::new(&infcx);
7453a54e 537 let base_cmt = mc.cat_expr(&base).unwrap();
1a4d82fc
JJ
538 let borrow_kind = ty::BorrowKind::from_mutbl(mutbl);
539 // Check that we don't allow borrows of unsafe static items.
c1a9b12d
SL
540 if check_aliasability(self.bccx, ex.span,
541 BorrowViolation(euv::AddrOf),
1a4d82fc
JJ
542 base_cmt, borrow_kind).is_err() {
543 return; // reported an error, no sense in reporting more.
544 }
545 }
546
92a42be0 547 intravisit::walk_expr(self, ex);
1a4d82fc
JJ
548 }
549}
550
e9174d1e 551pub fn gather_loans_in_static_initializer(bccx: &mut BorrowckCtxt, expr: &hir::Expr) {
1a4d82fc 552
62682a34 553 debug!("gather_loans_in_static_initializer(expr={:?})", expr);
1a4d82fc
JJ
554
555 let mut sicx = StaticInitializerCtxt {
556 bccx: bccx
557 };
558
559 sicx.visit_expr(expr);
560}