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