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