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