]> git.proxmox.com Git - rustc.git/blame - src/librustc/middle/infer/error_reporting.rs
Imported Upstream version 1.2.0+dfsg1
[rustc.git] / src / librustc / middle / infer / error_reporting.rs
CommitLineData
1a4d82fc
JJ
1// Copyright 2012-2013 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//! Error Reporting Code for the inference engine
12//!
13//! Because of the way inference, and in particular region inference,
14//! works, it often happens that errors are not detected until far after
15//! the relevant line of code has been type-checked. Therefore, there is
16//! an elaborate system to track why a particular constraint in the
17//! inference graph arose so that we can explain to the user what gave
18//! rise to a particular error.
19//!
20//! The basis of the system are the "origin" types. An "origin" is the
21//! reason that a constraint or inference variable arose. There are
22//! different "origin" enums for different kinds of constraints/variables
23//! (e.g., `TypeOrigin`, `RegionVariableOrigin`). An origin always has
24//! a span, but also more information so that we can generate a meaningful
25//! error message.
26//!
27//! Having a catalogue of all the different reasons an error can arise is
28//! also useful for other reasons, like cross-referencing FAQs etc, though
29//! we are not really taking advantage of this yet.
30//!
31//! # Region Inference
32//!
33//! Region inference is particularly tricky because it always succeeds "in
34//! the moment" and simply registers a constraint. Then, at the end, we
35//! can compute the full graph and report errors, so we need to be able to
36//! store and later report what gave rise to the conflicting constraints.
37//!
38//! # Subtype Trace
39//!
40//! Determining whether `T1 <: T2` often involves a number of subtypes and
41//! subconstraints along the way. A "TypeTrace" is an extended version
42//! of an origin that traces the types and other values that were being
43//! compared. It is not necessarily comprehensive (in fact, at the time of
44//! this writing it only tracks the root values being compared) but I'd
45//! like to extend it to include significant "waypoints". For example, if
46//! you are comparing `(T1, T2) <: (T3, T4)`, and the problem is that `T2
47//! <: T4` fails, I'd like the trace to include enough information to say
48//! "in the 2nd element of the tuple". Similarly, failures when comparing
49//! arguments or return types in fn types should be able to cite the
50//! specific position, etc.
51//!
52//! # Reality vs plan
53//!
54//! Of course, there is still a LOT of code in typeck that has yet to be
55//! ported to this system, and which relies on string concatenation at the
56//! time of error detection.
57
58use self::FreshOrKept::*;
59
60use super::InferCtxt;
61use super::TypeTrace;
62use super::SubregionOrigin;
63use super::RegionVariableOrigin;
64use super::ValuePairs;
65use super::region_inference::RegionResolutionError;
66use super::region_inference::ConcreteFailure;
67use super::region_inference::SubSupConflict;
68use super::region_inference::SupSupConflict;
69use super::region_inference::GenericBoundFailure;
70use super::region_inference::GenericKind;
71use super::region_inference::ProcessedErrors;
72use super::region_inference::SameRegions;
73
74use std::collections::HashSet;
62682a34 75use ast_map;
1a4d82fc
JJ
76use middle::def;
77use middle::infer;
62682a34 78use middle::region;
1a4d82fc
JJ
79use middle::subst;
80use middle::ty::{self, Ty};
81use middle::ty::{Region, ReFree};
62682a34 82
1a4d82fc
JJ
83use std::cell::{Cell, RefCell};
84use std::char::from_u32;
62682a34 85use std::fmt;
1a4d82fc 86use syntax::ast;
c34b1796 87use syntax::ast_util::name_to_dummy_lifetime;
1a4d82fc 88use syntax::owned_slice::OwnedSlice;
62682a34 89use syntax::codemap::{Pos, Span};
1a4d82fc
JJ
90use syntax::parse::token;
91use syntax::print::pprust;
92use syntax::ptr::P;
1a4d82fc 93
62682a34
SL
94pub fn note_and_explain_region(tcx: &ty::ctxt,
95 prefix: &str,
96 region: ty::Region,
97 suffix: &str) {
98 fn item_scope_tag(item: &ast::Item) -> &'static str {
99 match item.node {
100 ast::ItemImpl(..) => "impl",
101 ast::ItemStruct(..) => "struct",
102 ast::ItemEnum(..) => "enum",
103 ast::ItemTrait(..) => "trait",
104 ast::ItemFn(..) => "function body",
105 _ => "item"
106 }
107 }
108
109 fn explain_span(tcx: &ty::ctxt, heading: &str, span: Span)
110 -> (String, Option<Span>) {
111 let lo = tcx.sess.codemap().lookup_char_pos_adj(span.lo);
112 (format!("the {} at {}:{}", heading, lo.line, lo.col.to_usize()),
113 Some(span))
114 }
115
116 let (description, span) = match region {
117 ty::ReScope(scope) => {
118 let new_string;
119 let unknown_scope = || {
120 format!("{}unknown scope: {:?}{}. Please report a bug.",
121 prefix, scope, suffix)
122 };
123 let span = match scope.span(&tcx.map) {
124 Some(s) => s,
125 None => return tcx.sess.note(&unknown_scope())
126 };
127 let tag = match tcx.map.find(scope.node_id()) {
128 Some(ast_map::NodeBlock(_)) => "block",
129 Some(ast_map::NodeExpr(expr)) => match expr.node {
130 ast::ExprCall(..) => "call",
131 ast::ExprMethodCall(..) => "method call",
132 ast::ExprMatch(_, _, ast::MatchSource::IfLetDesugar { .. }) => "if let",
133 ast::ExprMatch(_, _, ast::MatchSource::WhileLetDesugar) => "while let",
134 ast::ExprMatch(_, _, ast::MatchSource::ForLoopDesugar) => "for",
135 ast::ExprMatch(..) => "match",
136 _ => "expression",
137 },
138 Some(ast_map::NodeStmt(_)) => "statement",
139 Some(ast_map::NodeItem(it)) => item_scope_tag(&*it),
140 Some(_) | None => {
141 return tcx.sess.span_note(span, &unknown_scope());
142 }
143 };
144 let scope_decorated_tag = match scope {
145 region::CodeExtent::Misc(_) => tag,
146 region::CodeExtent::ParameterScope { .. } => {
147 "scope of parameters for function"
148 }
149 region::CodeExtent::DestructionScope(_) => {
150 new_string = format!("destruction scope surrounding {}", tag);
151 &new_string[..]
152 }
153 region::CodeExtent::Remainder(r) => {
154 new_string = format!("block suffix following statement {}",
155 r.first_statement_index);
156 &new_string[..]
157 }
158 };
159 explain_span(tcx, scope_decorated_tag, span)
160 }
161
162 ty::ReFree(ref fr) => {
163 let prefix = match fr.bound_region {
164 ty::BrAnon(idx) => {
165 format!("the anonymous lifetime #{} defined on", idx + 1)
166 }
167 ty::BrFresh(_) => "an anonymous lifetime defined on".to_owned(),
168 _ => {
169 format!("the lifetime {} as defined on",
170 fr.bound_region)
171 }
172 };
173
174 match tcx.map.find(fr.scope.node_id) {
175 Some(ast_map::NodeBlock(ref blk)) => {
176 let (msg, opt_span) = explain_span(tcx, "block", blk.span);
177 (format!("{} {}", prefix, msg), opt_span)
178 }
179 Some(ast_map::NodeItem(it)) => {
180 let tag = item_scope_tag(&*it);
181 let (msg, opt_span) = explain_span(tcx, tag, it.span);
182 (format!("{} {}", prefix, msg), opt_span)
183 }
184 Some(_) | None => {
185 // this really should not happen
186 (format!("{} unknown free region bounded by scope {:?}",
187 prefix, fr.scope), None)
188 }
189 }
190 }
191
192 ty::ReStatic => ("the static lifetime".to_owned(), None),
193
194 ty::ReEmpty => ("the empty lifetime".to_owned(), None),
195
196 ty::ReEarlyBound(ref data) => {
197 (format!("{}", token::get_name(data.name)), None)
198 }
199
200 // I believe these cases should not occur (except when debugging,
201 // perhaps)
202 ty::ReInfer(_) | ty::ReLateBound(..) => {
203 (format!("lifetime {:?}", region), None)
204 }
205 };
206 let message = format!("{}{}{}", prefix, description, suffix);
207 if let Some(span) = span {
208 tcx.sess.span_note(span, &message);
209 } else {
210 tcx.sess.note(&message);
211 }
212}
1a4d82fc
JJ
213
214pub trait ErrorReporting<'tcx> {
215 fn report_region_errors(&self,
216 errors: &Vec<RegionResolutionError<'tcx>>);
217
218 fn process_errors(&self, errors: &Vec<RegionResolutionError<'tcx>>)
219 -> Vec<RegionResolutionError<'tcx>>;
220
221 fn report_type_error(&self, trace: TypeTrace<'tcx>, terr: &ty::type_err<'tcx>);
222
223 fn report_and_explain_type_error(&self,
224 trace: TypeTrace<'tcx>,
225 terr: &ty::type_err<'tcx>);
226
227 fn values_str(&self, values: &ValuePairs<'tcx>) -> Option<String>;
228
62682a34 229 fn expected_found_str<T: fmt::Display + Resolvable<'tcx>>(
1a4d82fc
JJ
230 &self,
231 exp_found: &ty::expected_found<T>)
232 -> Option<String>;
233
234 fn report_concrete_failure(&self,
235 origin: SubregionOrigin<'tcx>,
236 sub: Region,
237 sup: Region);
238
239 fn report_generic_bound_failure(&self,
240 origin: SubregionOrigin<'tcx>,
241 kind: GenericKind<'tcx>,
242 sub: Region,
243 sups: Vec<Region>);
244
245 fn report_sub_sup_conflict(&self,
246 var_origin: RegionVariableOrigin,
247 sub_origin: SubregionOrigin<'tcx>,
248 sub_region: Region,
249 sup_origin: SubregionOrigin<'tcx>,
250 sup_region: Region);
251
252 fn report_sup_sup_conflict(&self,
253 var_origin: RegionVariableOrigin,
254 origin1: SubregionOrigin<'tcx>,
255 region1: Region,
256 origin2: SubregionOrigin<'tcx>,
257 region2: Region);
258
259 fn report_processed_errors(&self,
260 var_origin: &[RegionVariableOrigin],
261 trace_origin: &[(TypeTrace<'tcx>, ty::type_err<'tcx>)],
262 same_regions: &[SameRegions]);
263
264 fn give_suggestion(&self, same_regions: &[SameRegions]);
265}
266
267trait ErrorReportingHelpers<'tcx> {
268 fn report_inference_failure(&self,
269 var_origin: RegionVariableOrigin);
270
271 fn note_region_origin(&self,
272 origin: &SubregionOrigin<'tcx>);
273
274 fn give_expl_lifetime_param(&self,
275 decl: &ast::FnDecl,
276 unsafety: ast::Unsafety,
62682a34 277 constness: ast::Constness,
1a4d82fc
JJ
278 ident: ast::Ident,
279 opt_explicit_self: Option<&ast::ExplicitSelf_>,
280 generics: &ast::Generics,
62682a34 281 span: Span);
1a4d82fc
JJ
282}
283
284impl<'a, 'tcx> ErrorReporting<'tcx> for InferCtxt<'a, 'tcx> {
285 fn report_region_errors(&self,
286 errors: &Vec<RegionResolutionError<'tcx>>) {
287 let p_errors = self.process_errors(errors);
288 let errors = if p_errors.is_empty() { errors } else { &p_errors };
85aaf69f 289 for error in errors {
1a4d82fc
JJ
290 match error.clone() {
291 ConcreteFailure(origin, sub, sup) => {
292 self.report_concrete_failure(origin, sub, sup);
293 }
294
295 GenericBoundFailure(kind, param_ty, sub, sups) => {
296 self.report_generic_bound_failure(kind, param_ty, sub, sups);
297 }
298
299 SubSupConflict(var_origin,
300 sub_origin, sub_r,
301 sup_origin, sup_r) => {
302 self.report_sub_sup_conflict(var_origin,
303 sub_origin, sub_r,
304 sup_origin, sup_r);
305 }
306
307 SupSupConflict(var_origin,
308 origin1, r1,
309 origin2, r2) => {
310 self.report_sup_sup_conflict(var_origin,
311 origin1, r1,
312 origin2, r2);
313 }
314
315 ProcessedErrors(ref var_origins,
316 ref trace_origins,
317 ref same_regions) => {
318 if !same_regions.is_empty() {
85aaf69f
SL
319 self.report_processed_errors(&var_origins[..],
320 &trace_origins[..],
321 &same_regions[..]);
1a4d82fc
JJ
322 }
323 }
324 }
325 }
326 }
327
328 // This method goes through all the errors and try to group certain types
329 // of error together, for the purpose of suggesting explicit lifetime
330 // parameters to the user. This is done so that we can have a more
331 // complete view of what lifetimes should be the same.
332 // If the return value is an empty vector, it means that processing
333 // failed (so the return value of this method should not be used)
334 fn process_errors(&self, errors: &Vec<RegionResolutionError<'tcx>>)
335 -> Vec<RegionResolutionError<'tcx>> {
336 debug!("process_errors()");
337 let mut var_origins = Vec::new();
338 let mut trace_origins = Vec::new();
339 let mut same_regions = Vec::new();
340 let mut processed_errors = Vec::new();
85aaf69f 341 for error in errors {
1a4d82fc
JJ
342 match error.clone() {
343 ConcreteFailure(origin, sub, sup) => {
344 debug!("processing ConcreteFailure");
345 let trace = match origin {
346 infer::Subtype(trace) => Some(trace),
347 _ => None,
348 };
349 match free_regions_from_same_fn(self.tcx, sub, sup) {
350 Some(ref same_frs) if trace.is_some() => {
351 let trace = trace.unwrap();
352 let terr = ty::terr_regions_does_not_outlive(sup,
353 sub);
354 trace_origins.push((trace, terr));
355 append_to_same_regions(&mut same_regions, same_frs);
356 }
357 _ => processed_errors.push((*error).clone()),
358 }
359 }
360 SubSupConflict(var_origin, _, sub_r, _, sup_r) => {
85aaf69f 361 debug!("processing SubSupConflict sub: {:?} sup: {:?}", sub_r, sup_r);
1a4d82fc
JJ
362 match free_regions_from_same_fn(self.tcx, sub_r, sup_r) {
363 Some(ref same_frs) => {
364 var_origins.push(var_origin);
365 append_to_same_regions(&mut same_regions, same_frs);
366 }
367 None => processed_errors.push((*error).clone()),
368 }
369 }
370 SupSupConflict(..) => processed_errors.push((*error).clone()),
371 _ => () // This shouldn't happen
372 }
373 }
374 if !same_regions.is_empty() {
375 let common_scope_id = same_regions[0].scope_id;
85aaf69f 376 for sr in &same_regions {
1a4d82fc
JJ
377 // Since ProcessedErrors is used to reconstruct the function
378 // declaration, we want to make sure that they are, in fact,
379 // from the same scope
380 if sr.scope_id != common_scope_id {
381 debug!("returning empty result from process_errors because
382 {} != {}", sr.scope_id, common_scope_id);
383 return vec!();
384 }
385 }
386 let pe = ProcessedErrors(var_origins, trace_origins, same_regions);
387 debug!("errors processed: {:?}", pe);
388 processed_errors.push(pe);
389 }
390 return processed_errors;
391
392
393 struct FreeRegionsFromSameFn {
394 sub_fr: ty::FreeRegion,
395 sup_fr: ty::FreeRegion,
396 scope_id: ast::NodeId
397 }
398
399 impl FreeRegionsFromSameFn {
400 fn new(sub_fr: ty::FreeRegion,
401 sup_fr: ty::FreeRegion,
402 scope_id: ast::NodeId)
403 -> FreeRegionsFromSameFn {
404 FreeRegionsFromSameFn {
405 sub_fr: sub_fr,
406 sup_fr: sup_fr,
407 scope_id: scope_id
408 }
409 }
410 }
411
412 fn free_regions_from_same_fn(tcx: &ty::ctxt,
413 sub: Region,
414 sup: Region)
415 -> Option<FreeRegionsFromSameFn> {
416 debug!("free_regions_from_same_fn(sub={:?}, sup={:?})", sub, sup);
417 let (scope_id, fr1, fr2) = match (sub, sup) {
418 (ReFree(fr1), ReFree(fr2)) => {
419 if fr1.scope != fr2.scope {
420 return None
421 }
422 assert!(fr1.scope == fr2.scope);
85aaf69f 423 (fr1.scope.node_id, fr1, fr2)
1a4d82fc
JJ
424 },
425 _ => return None
426 };
427 let parent = tcx.map.get_parent(scope_id);
428 let parent_node = tcx.map.find(parent);
429 match parent_node {
430 Some(node) => match node {
431 ast_map::NodeItem(item) => match item.node {
432 ast::ItemFn(..) => {
433 Some(FreeRegionsFromSameFn::new(fr1, fr2, scope_id))
434 },
435 _ => None
436 },
437 ast_map::NodeImplItem(..) |
438 ast_map::NodeTraitItem(..) => {
439 Some(FreeRegionsFromSameFn::new(fr1, fr2, scope_id))
440 },
441 _ => None
442 },
443 None => {
444 debug!("no parent node of scope_id {}", scope_id);
445 None
446 }
447 }
448 }
449
450 fn append_to_same_regions(same_regions: &mut Vec<SameRegions>,
451 same_frs: &FreeRegionsFromSameFn) {
452 let scope_id = same_frs.scope_id;
453 let (sub_fr, sup_fr) = (same_frs.sub_fr, same_frs.sup_fr);
85aaf69f 454 for sr in &mut *same_regions {
1a4d82fc
JJ
455 if sr.contains(&sup_fr.bound_region)
456 && scope_id == sr.scope_id {
457 sr.push(sub_fr.bound_region);
458 return
459 }
460 }
461 same_regions.push(SameRegions {
462 scope_id: scope_id,
463 regions: vec!(sub_fr.bound_region, sup_fr.bound_region)
464 })
465 }
466 }
467
468 fn report_type_error(&self, trace: TypeTrace<'tcx>, terr: &ty::type_err<'tcx>) {
469 let expected_found_str = match self.values_str(&trace.values) {
470 Some(v) => v,
471 None => {
472 return; /* derived error */
473 }
474 };
475
85aaf69f
SL
476 span_err!(self.tcx.sess, trace.origin.span(), E0308,
477 "{}: {} ({})",
c34b1796 478 trace.origin,
1a4d82fc 479 expected_found_str,
62682a34 480 terr);
1a4d82fc
JJ
481
482 match trace.origin {
483 infer::MatchExpressionArm(_, arm_span) =>
484 self.tcx.sess.span_note(arm_span, "match arm with an incompatible type"),
485 _ => ()
486 }
487 }
488
489 fn report_and_explain_type_error(&self,
490 trace: TypeTrace<'tcx>,
491 terr: &ty::type_err<'tcx>) {
9346a6ac 492 let span = trace.origin.span();
1a4d82fc 493 self.report_type_error(trace, terr);
9346a6ac 494 ty::note_and_explain_type_err(self.tcx, terr, span);
1a4d82fc
JJ
495 }
496
497 /// Returns a string of the form "expected `{}`, found `{}`", or None if this is a derived
498 /// error.
499 fn values_str(&self, values: &ValuePairs<'tcx>) -> Option<String> {
500 match *values {
501 infer::Types(ref exp_found) => self.expected_found_str(exp_found),
502 infer::TraitRefs(ref exp_found) => self.expected_found_str(exp_found),
503 infer::PolyTraitRefs(ref exp_found) => self.expected_found_str(exp_found)
504 }
505 }
506
62682a34 507 fn expected_found_str<T: fmt::Display + Resolvable<'tcx>>(
1a4d82fc
JJ
508 &self,
509 exp_found: &ty::expected_found<T>)
510 -> Option<String>
511 {
512 let expected = exp_found.expected.resolve(self);
513 if expected.contains_error() {
514 return None;
515 }
516
517 let found = exp_found.found.resolve(self);
518 if found.contains_error() {
519 return None;
520 }
521
522 Some(format!("expected `{}`, found `{}`",
62682a34
SL
523 expected,
524 found))
1a4d82fc
JJ
525 }
526
527 fn report_generic_bound_failure(&self,
528 origin: SubregionOrigin<'tcx>,
529 bound_kind: GenericKind<'tcx>,
530 sub: Region,
531 _sups: Vec<Region>)
532 {
533 // FIXME: it would be better to report the first error message
534 // with the span of the parameter itself, rather than the span
535 // where the error was detected. But that span is not readily
536 // accessible.
537
538 let labeled_user_string = match bound_kind {
539 GenericKind::Param(ref p) =>
62682a34 540 format!("the parameter type `{}`", p),
1a4d82fc 541 GenericKind::Projection(ref p) =>
62682a34 542 format!("the associated type `{}`", p),
1a4d82fc
JJ
543 };
544
545 match sub {
546 ty::ReFree(ty::FreeRegion {bound_region: ty::BrNamed(..), ..}) => {
547 // Does the required lifetime have a nice name we can print?
85aaf69f
SL
548 span_err!(self.tcx.sess, origin.span(), E0309,
549 "{} may not live long enough", labeled_user_string);
c34b1796 550 self.tcx.sess.fileline_help(
1a4d82fc
JJ
551 origin.span(),
552 &format!(
553 "consider adding an explicit lifetime bound `{}: {}`...",
62682a34
SL
554 bound_kind,
555 sub));
1a4d82fc
JJ
556 }
557
558 ty::ReStatic => {
559 // Does the required lifetime have a nice name we can print?
85aaf69f
SL
560 span_err!(self.tcx.sess, origin.span(), E0310,
561 "{} may not live long enough", labeled_user_string);
c34b1796 562 self.tcx.sess.fileline_help(
1a4d82fc
JJ
563 origin.span(),
564 &format!(
565 "consider adding an explicit lifetime bound `{}: 'static`...",
62682a34 566 bound_kind));
1a4d82fc
JJ
567 }
568
569 _ => {
570 // If not, be less specific.
85aaf69f 571 span_err!(self.tcx.sess, origin.span(), E0311,
1a4d82fc 572 "{} may not live long enough",
85aaf69f 573 labeled_user_string);
c34b1796 574 self.tcx.sess.fileline_help(
1a4d82fc
JJ
575 origin.span(),
576 &format!(
577 "consider adding an explicit lifetime bound for `{}`",
62682a34 578 bound_kind));
1a4d82fc
JJ
579 note_and_explain_region(
580 self.tcx,
c34b1796 581 &format!("{} must be valid for ", labeled_user_string),
1a4d82fc
JJ
582 sub,
583 "...");
584 }
585 }
586
587 self.note_region_origin(&origin);
588 }
589
590 fn report_concrete_failure(&self,
591 origin: SubregionOrigin<'tcx>,
592 sub: Region,
593 sup: Region) {
594 match origin {
62682a34
SL
595 infer::Subtype(trace) |
596 infer::DefaultExistentialBound(trace) => {
1a4d82fc
JJ
597 let terr = ty::terr_regions_does_not_outlive(sup, sub);
598 self.report_and_explain_type_error(trace, &terr);
599 }
600 infer::Reborrow(span) => {
85aaf69f 601 span_err!(self.tcx.sess, span, E0312,
1a4d82fc
JJ
602 "lifetime of reference outlines \
603 lifetime of borrowed content...");
604 note_and_explain_region(
605 self.tcx,
606 "...the reference is valid for ",
607 sub,
608 "...");
609 note_and_explain_region(
610 self.tcx,
611 "...but the borrowed content is only valid for ",
612 sup,
613 "");
614 }
615 infer::ReborrowUpvar(span, ref upvar_id) => {
85aaf69f
SL
616 span_err!(self.tcx.sess, span, E0313,
617 "lifetime of borrowed pointer outlives \
1a4d82fc
JJ
618 lifetime of captured variable `{}`...",
619 ty::local_var_name_str(self.tcx,
620 upvar_id.var_id)
85aaf69f 621 .to_string());
1a4d82fc
JJ
622 note_and_explain_region(
623 self.tcx,
624 "...the borrowed pointer is valid for ",
625 sub,
626 "...");
627 note_and_explain_region(
628 self.tcx,
629 &format!("...but `{}` is only valid for ",
630 ty::local_var_name_str(self.tcx,
631 upvar_id.var_id)
c34b1796 632 .to_string()),
1a4d82fc
JJ
633 sup,
634 "");
635 }
636 infer::InfStackClosure(span) => {
85aaf69f 637 span_err!(self.tcx.sess, span, E0314,
1a4d82fc
JJ
638 "closure outlives stack frame");
639 note_and_explain_region(
640 self.tcx,
641 "...the closure must be valid for ",
642 sub,
643 "...");
644 note_and_explain_region(
645 self.tcx,
646 "...but the closure's stack frame is only valid for ",
647 sup,
648 "");
649 }
650 infer::InvokeClosure(span) => {
85aaf69f 651 span_err!(self.tcx.sess, span, E0315,
1a4d82fc
JJ
652 "cannot invoke closure outside of its lifetime");
653 note_and_explain_region(
654 self.tcx,
655 "the closure is only valid for ",
656 sup,
657 "");
658 }
659 infer::DerefPointer(span) => {
660 self.tcx.sess.span_err(
661 span,
662 "dereference of reference outside its lifetime");
663 note_and_explain_region(
664 self.tcx,
665 "the reference is only valid for ",
666 sup,
667 "");
668 }
669 infer::FreeVariable(span, id) => {
670 self.tcx.sess.span_err(
671 span,
672 &format!("captured variable `{}` does not \
673 outlive the enclosing closure",
674 ty::local_var_name_str(self.tcx,
c34b1796 675 id).to_string()));
1a4d82fc
JJ
676 note_and_explain_region(
677 self.tcx,
678 "captured variable is valid for ",
679 sup,
680 "");
681 note_and_explain_region(
682 self.tcx,
683 "closure is valid for ",
684 sub,
685 "");
686 }
687 infer::IndexSlice(span) => {
688 self.tcx.sess.span_err(span,
689 "index of slice outside its lifetime");
690 note_and_explain_region(
691 self.tcx,
692 "the slice is only valid for ",
693 sup,
694 "");
695 }
696 infer::RelateObjectBound(span) => {
697 self.tcx.sess.span_err(
698 span,
699 "lifetime of the source pointer does not outlive \
700 lifetime bound of the object type");
701 note_and_explain_region(
702 self.tcx,
703 "object type is valid for ",
704 sub,
705 "");
706 note_and_explain_region(
707 self.tcx,
708 "source pointer is only valid for ",
709 sup,
710 "");
711 }
712 infer::RelateParamBound(span, ty) => {
713 self.tcx.sess.span_err(
714 span,
715 &format!("the type `{}` does not fulfill the \
716 required lifetime",
c34b1796 717 self.ty_to_string(ty)));
1a4d82fc
JJ
718 note_and_explain_region(self.tcx,
719 "type must outlive ",
720 sub,
721 "");
722 }
723 infer::RelateRegionParamBound(span) => {
724 self.tcx.sess.span_err(
725 span,
85aaf69f 726 "lifetime bound not satisfied");
1a4d82fc
JJ
727 note_and_explain_region(
728 self.tcx,
729 "lifetime parameter instantiated with ",
730 sup,
731 "");
732 note_and_explain_region(
733 self.tcx,
734 "but lifetime parameter must outlive ",
735 sub,
736 "");
737 }
738 infer::RelateDefaultParamBound(span, ty) => {
739 self.tcx.sess.span_err(
740 span,
741 &format!("the type `{}` (provided as the value of \
742 a type parameter) is not valid at this point",
c34b1796 743 self.ty_to_string(ty)));
1a4d82fc
JJ
744 note_and_explain_region(self.tcx,
745 "type must outlive ",
746 sub,
747 "");
748 }
749 infer::CallRcvr(span) => {
750 self.tcx.sess.span_err(
751 span,
752 "lifetime of method receiver does not outlive \
753 the method call");
754 note_and_explain_region(
755 self.tcx,
756 "the receiver is only valid for ",
757 sup,
758 "");
759 }
760 infer::CallArg(span) => {
761 self.tcx.sess.span_err(
762 span,
763 "lifetime of function argument does not outlive \
764 the function call");
765 note_and_explain_region(
766 self.tcx,
767 "the function argument is only valid for ",
768 sup,
769 "");
770 }
771 infer::CallReturn(span) => {
772 self.tcx.sess.span_err(
773 span,
774 "lifetime of return value does not outlive \
775 the function call");
776 note_and_explain_region(
777 self.tcx,
778 "the return value is only valid for ",
779 sup,
780 "");
781 }
85aaf69f
SL
782 infer::Operand(span) => {
783 self.tcx.sess.span_err(
784 span,
785 "lifetime of operand does not outlive \
786 the operation");
787 note_and_explain_region(
788 self.tcx,
789 "the operand is only valid for ",
790 sup,
791 "");
792 }
1a4d82fc
JJ
793 infer::AddrOf(span) => {
794 self.tcx.sess.span_err(
795 span,
796 "reference is not valid \
797 at the time of borrow");
798 note_and_explain_region(
799 self.tcx,
800 "the borrow is only valid for ",
801 sup,
802 "");
803 }
804 infer::AutoBorrow(span) => {
805 self.tcx.sess.span_err(
806 span,
807 "automatically reference is not valid \
808 at the time of borrow");
809 note_and_explain_region(
810 self.tcx,
811 "the automatic borrow is only valid for ",
812 sup,
813 "");
814 }
815 infer::ExprTypeIsNotInScope(t, span) => {
816 self.tcx.sess.span_err(
817 span,
818 &format!("type of expression contains references \
819 that are not valid during the expression: `{}`",
c34b1796 820 self.ty_to_string(t)));
1a4d82fc
JJ
821 note_and_explain_region(
822 self.tcx,
823 "type is only valid for ",
824 sup,
825 "");
826 }
85aaf69f
SL
827 infer::SafeDestructor(span) => {
828 self.tcx.sess.span_err(
829 span,
830 "unsafe use of destructor: destructor might be called \
831 while references are dead");
832 // FIXME (22171): terms "super/subregion" are suboptimal
833 note_and_explain_region(
834 self.tcx,
835 "superregion: ",
836 sup,
837 "");
838 note_and_explain_region(
839 self.tcx,
840 "subregion: ",
841 sub,
842 "");
843 }
1a4d82fc
JJ
844 infer::BindingTypeIsNotValidAtDecl(span) => {
845 self.tcx.sess.span_err(
846 span,
847 "lifetime of variable does not enclose its declaration");
848 note_and_explain_region(
849 self.tcx,
850 "the variable is only valid for ",
851 sup,
852 "");
853 }
854 infer::ReferenceOutlivesReferent(ty, span) => {
855 self.tcx.sess.span_err(
856 span,
857 &format!("in type `{}`, reference has a longer lifetime \
858 than the data it references",
c34b1796 859 self.ty_to_string(ty)));
1a4d82fc
JJ
860 note_and_explain_region(
861 self.tcx,
862 "the pointer is valid for ",
863 sub,
864 "");
865 note_and_explain_region(
866 self.tcx,
867 "but the referenced data is only valid for ",
868 sup,
869 "");
870 }
871 }
872 }
873
874 fn report_sub_sup_conflict(&self,
875 var_origin: RegionVariableOrigin,
876 sub_origin: SubregionOrigin<'tcx>,
877 sub_region: Region,
878 sup_origin: SubregionOrigin<'tcx>,
879 sup_region: Region) {
880 self.report_inference_failure(var_origin);
881
882 note_and_explain_region(
883 self.tcx,
884 "first, the lifetime cannot outlive ",
885 sup_region,
886 "...");
887
888 self.note_region_origin(&sup_origin);
889
890 note_and_explain_region(
891 self.tcx,
892 "but, the lifetime must be valid for ",
893 sub_region,
894 "...");
895
896 self.note_region_origin(&sub_origin);
897 }
898
899 fn report_sup_sup_conflict(&self,
900 var_origin: RegionVariableOrigin,
901 origin1: SubregionOrigin<'tcx>,
902 region1: Region,
903 origin2: SubregionOrigin<'tcx>,
904 region2: Region) {
905 self.report_inference_failure(var_origin);
906
907 note_and_explain_region(
908 self.tcx,
909 "first, the lifetime must be contained by ",
910 region1,
911 "...");
912
913 self.note_region_origin(&origin1);
914
915 note_and_explain_region(
916 self.tcx,
917 "but, the lifetime must also be contained by ",
918 region2,
919 "...");
920
921 self.note_region_origin(&origin2);
922 }
923
924 fn report_processed_errors(&self,
925 var_origins: &[RegionVariableOrigin],
926 trace_origins: &[(TypeTrace<'tcx>, ty::type_err<'tcx>)],
927 same_regions: &[SameRegions]) {
85aaf69f 928 for vo in var_origins {
1a4d82fc
JJ
929 self.report_inference_failure(vo.clone());
930 }
931 self.give_suggestion(same_regions);
85aaf69f 932 for &(ref trace, terr) in trace_origins {
9346a6ac 933 self.report_and_explain_type_error(trace.clone(), &terr);
1a4d82fc
JJ
934 }
935 }
936
937 fn give_suggestion(&self, same_regions: &[SameRegions]) {
938 let scope_id = same_regions[0].scope_id;
939 let parent = self.tcx.map.get_parent(scope_id);
940 let parent_node = self.tcx.map.find(parent);
85aaf69f
SL
941 let taken = lifetimes_in_scope(self.tcx, scope_id);
942 let life_giver = LifeGiver::with_taken(&taken[..]);
1a4d82fc
JJ
943 let node_inner = match parent_node {
944 Some(ref node) => match *node {
945 ast_map::NodeItem(ref item) => {
946 match item.node {
62682a34
SL
947 ast::ItemFn(ref fn_decl, unsafety, constness, _, ref gen, _) => {
948 Some((fn_decl, gen, unsafety, constness,
949 item.ident, None, item.span))
1a4d82fc
JJ
950 },
951 _ => None
952 }
953 }
c34b1796
AL
954 ast_map::NodeImplItem(item) => {
955 match item.node {
956 ast::MethodImplItem(ref sig, _) => {
957 Some((&sig.decl,
958 &sig.generics,
959 sig.unsafety,
62682a34 960 sig.constness,
c34b1796
AL
961 item.ident,
962 Some(&sig.explicit_self.node),
963 item.span))
1a4d82fc 964 }
d9579d0f
AL
965 ast::MacImplItem(_) => self.tcx.sess.bug("unexpanded macro"),
966 _ => None,
1a4d82fc
JJ
967 }
968 },
c34b1796
AL
969 ast_map::NodeTraitItem(item) => {
970 match item.node {
971 ast::MethodTraitItem(ref sig, Some(_)) => {
972 Some((&sig.decl,
973 &sig.generics,
974 sig.unsafety,
62682a34 975 sig.constness,
c34b1796
AL
976 item.ident,
977 Some(&sig.explicit_self.node),
978 item.span))
1a4d82fc
JJ
979 }
980 _ => None
981 }
982 }
983 _ => None
984 },
985 None => None
986 };
62682a34 987 let (fn_decl, generics, unsafety, constness, ident, expl_self, span)
1a4d82fc 988 = node_inner.expect("expect item fn");
1a4d82fc
JJ
989 let rebuilder = Rebuilder::new(self.tcx, fn_decl, expl_self,
990 generics, same_regions, &life_giver);
991 let (fn_decl, expl_self, generics) = rebuilder.rebuild();
62682a34 992 self.give_expl_lifetime_param(&fn_decl, unsafety, constness, ident,
1a4d82fc
JJ
993 expl_self.as_ref(), &generics, span);
994 }
995}
996
997struct RebuildPathInfo<'a> {
998 path: &'a ast::Path,
999 // indexes to insert lifetime on path.lifetimes
1000 indexes: Vec<u32>,
1001 // number of lifetimes we expect to see on the type referred by `path`
1002 // (e.g., expected=1 for struct Foo<'a>)
1003 expected: u32,
1004 anon_nums: &'a HashSet<u32>,
1005 region_names: &'a HashSet<ast::Name>
1006}
1007
1008struct Rebuilder<'a, 'tcx: 'a> {
1009 tcx: &'a ty::ctxt<'tcx>,
1010 fn_decl: &'a ast::FnDecl,
1011 expl_self_opt: Option<&'a ast::ExplicitSelf_>,
1012 generics: &'a ast::Generics,
1013 same_regions: &'a [SameRegions],
1014 life_giver: &'a LifeGiver,
1015 cur_anon: Cell<u32>,
1016 inserted_anons: RefCell<HashSet<u32>>,
1017}
1018
1019enum FreshOrKept {
1020 Fresh,
1021 Kept
1022}
1023
1024impl<'a, 'tcx> Rebuilder<'a, 'tcx> {
1025 fn new(tcx: &'a ty::ctxt<'tcx>,
1026 fn_decl: &'a ast::FnDecl,
1027 expl_self_opt: Option<&'a ast::ExplicitSelf_>,
1028 generics: &'a ast::Generics,
1029 same_regions: &'a [SameRegions],
1030 life_giver: &'a LifeGiver)
1031 -> Rebuilder<'a, 'tcx> {
1032 Rebuilder {
1033 tcx: tcx,
1034 fn_decl: fn_decl,
1035 expl_self_opt: expl_self_opt,
1036 generics: generics,
1037 same_regions: same_regions,
1038 life_giver: life_giver,
1039 cur_anon: Cell::new(0),
1040 inserted_anons: RefCell::new(HashSet::new()),
1041 }
1042 }
1043
1044 fn rebuild(&self)
1045 -> (ast::FnDecl, Option<ast::ExplicitSelf_>, ast::Generics) {
85aaf69f 1046 let mut expl_self_opt = self.expl_self_opt.cloned();
1a4d82fc
JJ
1047 let mut inputs = self.fn_decl.inputs.clone();
1048 let mut output = self.fn_decl.output.clone();
1049 let mut ty_params = self.generics.ty_params.clone();
1050 let where_clause = self.generics.where_clause.clone();
1051 let mut kept_lifetimes = HashSet::new();
85aaf69f 1052 for sr in self.same_regions {
1a4d82fc
JJ
1053 self.cur_anon.set(0);
1054 self.offset_cur_anon();
1055 let (anon_nums, region_names) =
1056 self.extract_anon_nums_and_names(sr);
1057 let (lifetime, fresh_or_kept) = self.pick_lifetime(&region_names);
1058 match fresh_or_kept {
1059 Kept => { kept_lifetimes.insert(lifetime.name); }
1060 _ => ()
1061 }
1062 expl_self_opt = self.rebuild_expl_self(expl_self_opt, lifetime,
1063 &anon_nums, &region_names);
85aaf69f 1064 inputs = self.rebuild_args_ty(&inputs[..], lifetime,
1a4d82fc
JJ
1065 &anon_nums, &region_names);
1066 output = self.rebuild_output(&output, lifetime, &anon_nums, &region_names);
1067 ty_params = self.rebuild_ty_params(ty_params, lifetime,
1068 &region_names);
1069 }
1070 let fresh_lifetimes = self.life_giver.get_generated_lifetimes();
1071 let all_region_names = self.extract_all_region_names();
1072 let generics = self.rebuild_generics(self.generics,
1073 &fresh_lifetimes,
1074 &kept_lifetimes,
1075 &all_region_names,
1076 ty_params,
1077 where_clause);
1078 let new_fn_decl = ast::FnDecl {
1079 inputs: inputs,
1080 output: output,
1081 variadic: self.fn_decl.variadic
1082 };
1083 (new_fn_decl, expl_self_opt, generics)
1084 }
1085
1086 fn pick_lifetime(&self,
1087 region_names: &HashSet<ast::Name>)
1088 -> (ast::Lifetime, FreshOrKept) {
9346a6ac 1089 if !region_names.is_empty() {
1a4d82fc
JJ
1090 // It's not necessary to convert the set of region names to a
1091 // vector of string and then sort them. However, it makes the
1092 // choice of lifetime name deterministic and thus easier to test.
1093 let mut names = Vec::new();
85aaf69f
SL
1094 for rn in region_names {
1095 let lt_name = token::get_name(*rn).to_string();
1a4d82fc
JJ
1096 names.push(lt_name);
1097 }
1098 names.sort();
c34b1796 1099 let name = token::str_to_ident(&names[0]).name;
1a4d82fc
JJ
1100 return (name_to_dummy_lifetime(name), Kept);
1101 }
1102 return (self.life_giver.give_lifetime(), Fresh);
1103 }
1104
1105 fn extract_anon_nums_and_names(&self, same_regions: &SameRegions)
1106 -> (HashSet<u32>, HashSet<ast::Name>) {
1107 let mut anon_nums = HashSet::new();
1108 let mut region_names = HashSet::new();
85aaf69f 1109 for br in &same_regions.regions {
1a4d82fc
JJ
1110 match *br {
1111 ty::BrAnon(i) => {
1112 anon_nums.insert(i);
1113 }
1114 ty::BrNamed(_, name) => {
1115 region_names.insert(name);
1116 }
1117 _ => ()
1118 }
1119 }
1120 (anon_nums, region_names)
1121 }
1122
1123 fn extract_all_region_names(&self) -> HashSet<ast::Name> {
1124 let mut all_region_names = HashSet::new();
85aaf69f
SL
1125 for sr in self.same_regions {
1126 for br in &sr.regions {
1a4d82fc
JJ
1127 match *br {
1128 ty::BrNamed(_, name) => {
1129 all_region_names.insert(name);
1130 }
1131 _ => ()
1132 }
1133 }
1134 }
1135 all_region_names
1136 }
1137
1138 fn inc_cur_anon(&self, n: u32) {
1139 let anon = self.cur_anon.get();
1140 self.cur_anon.set(anon+n);
1141 }
1142
1143 fn offset_cur_anon(&self) {
1144 let mut anon = self.cur_anon.get();
1145 while self.inserted_anons.borrow().contains(&anon) {
1146 anon += 1;
1147 }
1148 self.cur_anon.set(anon);
1149 }
1150
1151 fn inc_and_offset_cur_anon(&self, n: u32) {
1152 self.inc_cur_anon(n);
1153 self.offset_cur_anon();
1154 }
1155
1156 fn track_anon(&self, anon: u32) {
1157 self.inserted_anons.borrow_mut().insert(anon);
1158 }
1159
1160 fn rebuild_ty_params(&self,
1161 ty_params: OwnedSlice<ast::TyParam>,
1162 lifetime: ast::Lifetime,
1163 region_names: &HashSet<ast::Name>)
1164 -> OwnedSlice<ast::TyParam> {
1165 ty_params.map(|ty_param| {
1166 let bounds = self.rebuild_ty_param_bounds(ty_param.bounds.clone(),
1167 lifetime,
1168 region_names);
1169 ast::TyParam {
1170 ident: ty_param.ident,
1171 id: ty_param.id,
1172 bounds: bounds,
1173 default: ty_param.default.clone(),
1174 span: ty_param.span,
1175 }
1176 })
1177 }
1178
1179 fn rebuild_ty_param_bounds(&self,
1180 ty_param_bounds: OwnedSlice<ast::TyParamBound>,
1181 lifetime: ast::Lifetime,
1182 region_names: &HashSet<ast::Name>)
1183 -> OwnedSlice<ast::TyParamBound> {
1184 ty_param_bounds.map(|tpb| {
1185 match tpb {
1186 &ast::RegionTyParamBound(lt) => {
1187 // FIXME -- it's unclear whether I'm supposed to
1188 // substitute lifetime here. I suspect we need to
1189 // be passing down a map.
1190 ast::RegionTyParamBound(lt)
1191 }
1192 &ast::TraitTyParamBound(ref poly_tr, modifier) => {
1193 let tr = &poly_tr.trait_ref;
1194 let last_seg = tr.path.segments.last().unwrap();
1195 let mut insert = Vec::new();
1196 let lifetimes = last_seg.parameters.lifetimes();
1197 for (i, lt) in lifetimes.iter().enumerate() {
1198 if region_names.contains(&lt.name) {
1199 insert.push(i as u32);
1200 }
1201 }
1202 let rebuild_info = RebuildPathInfo {
1203 path: &tr.path,
1204 indexes: insert,
1205 expected: lifetimes.len() as u32,
1206 anon_nums: &HashSet::new(),
1207 region_names: region_names
1208 };
1209 let new_path = self.rebuild_path(rebuild_info, lifetime);
1210 ast::TraitTyParamBound(ast::PolyTraitRef {
1211 bound_lifetimes: poly_tr.bound_lifetimes.clone(),
1212 trait_ref: ast::TraitRef {
1213 path: new_path,
1214 ref_id: tr.ref_id,
85aaf69f
SL
1215 },
1216 span: poly_tr.span,
1a4d82fc
JJ
1217 }, modifier)
1218 }
1219 }
1220 })
1221 }
1222
1223 fn rebuild_expl_self(&self,
1224 expl_self_opt: Option<ast::ExplicitSelf_>,
1225 lifetime: ast::Lifetime,
1226 anon_nums: &HashSet<u32>,
1227 region_names: &HashSet<ast::Name>)
1228 -> Option<ast::ExplicitSelf_> {
1229 match expl_self_opt {
1230 Some(ref expl_self) => match *expl_self {
1231 ast::SelfRegion(lt_opt, muta, id) => match lt_opt {
1232 Some(lt) => if region_names.contains(&lt.name) {
1233 return Some(ast::SelfRegion(Some(lifetime), muta, id));
1234 },
1235 None => {
1236 let anon = self.cur_anon.get();
1237 self.inc_and_offset_cur_anon(1);
1238 if anon_nums.contains(&anon) {
1239 self.track_anon(anon);
1240 return Some(ast::SelfRegion(Some(lifetime), muta, id));
1241 }
1242 }
1243 },
1244 _ => ()
1245 },
1246 None => ()
1247 }
1248 expl_self_opt
1249 }
1250
1251 fn rebuild_generics(&self,
1252 generics: &ast::Generics,
1253 add: &Vec<ast::Lifetime>,
1254 keep: &HashSet<ast::Name>,
1255 remove: &HashSet<ast::Name>,
1256 ty_params: OwnedSlice<ast::TyParam>,
1257 where_clause: ast::WhereClause)
1258 -> ast::Generics {
1259 let mut lifetimes = Vec::new();
85aaf69f 1260 for lt in add {
1a4d82fc
JJ
1261 lifetimes.push(ast::LifetimeDef { lifetime: *lt,
1262 bounds: Vec::new() });
1263 }
85aaf69f 1264 for lt in &generics.lifetimes {
1a4d82fc
JJ
1265 if keep.contains(&lt.lifetime.name) ||
1266 !remove.contains(&lt.lifetime.name) {
1267 lifetimes.push((*lt).clone());
1268 }
1269 }
1270 ast::Generics {
1271 lifetimes: lifetimes,
1272 ty_params: ty_params,
1273 where_clause: where_clause,
1274 }
1275 }
1276
1277 fn rebuild_args_ty(&self,
1278 inputs: &[ast::Arg],
1279 lifetime: ast::Lifetime,
1280 anon_nums: &HashSet<u32>,
1281 region_names: &HashSet<ast::Name>)
1282 -> Vec<ast::Arg> {
1283 let mut new_inputs = Vec::new();
85aaf69f 1284 for arg in inputs {
1a4d82fc
JJ
1285 let new_ty = self.rebuild_arg_ty_or_output(&*arg.ty, lifetime,
1286 anon_nums, region_names);
1287 let possibly_new_arg = ast::Arg {
1288 ty: new_ty,
1289 pat: arg.pat.clone(),
1290 id: arg.id
1291 };
1292 new_inputs.push(possibly_new_arg);
1293 }
1294 new_inputs
1295 }
1296
1297 fn rebuild_output(&self, ty: &ast::FunctionRetTy,
1298 lifetime: ast::Lifetime,
1299 anon_nums: &HashSet<u32>,
1300 region_names: &HashSet<ast::Name>) -> ast::FunctionRetTy {
1301 match *ty {
1302 ast::Return(ref ret_ty) => ast::Return(
1303 self.rebuild_arg_ty_or_output(&**ret_ty, lifetime, anon_nums, region_names)
1304 ),
85aaf69f 1305 ast::DefaultReturn(span) => ast::DefaultReturn(span),
1a4d82fc
JJ
1306 ast::NoReturn(span) => ast::NoReturn(span)
1307 }
1308 }
1309
1310 fn rebuild_arg_ty_or_output(&self,
1311 ty: &ast::Ty,
1312 lifetime: ast::Lifetime,
1313 anon_nums: &HashSet<u32>,
1314 region_names: &HashSet<ast::Name>)
1315 -> P<ast::Ty> {
1316 let mut new_ty = P(ty.clone());
1317 let mut ty_queue = vec!(ty);
1318 while !ty_queue.is_empty() {
1319 let cur_ty = ty_queue.remove(0);
1320 match cur_ty.node {
1321 ast::TyRptr(lt_opt, ref mut_ty) => {
1322 let rebuild = match lt_opt {
1323 Some(lt) => region_names.contains(&lt.name),
1324 None => {
1325 let anon = self.cur_anon.get();
1326 let rebuild = anon_nums.contains(&anon);
1327 if rebuild {
1328 self.track_anon(anon);
1329 }
1330 self.inc_and_offset_cur_anon(1);
1331 rebuild
1332 }
1333 };
1334 if rebuild {
1335 let to = ast::Ty {
1336 id: cur_ty.id,
1337 node: ast::TyRptr(Some(lifetime), mut_ty.clone()),
1338 span: cur_ty.span
1339 };
1340 new_ty = self.rebuild_ty(new_ty, P(to));
1341 }
1342 ty_queue.push(&*mut_ty.ty);
1343 }
c34b1796
AL
1344 ast::TyPath(ref maybe_qself, ref path) => {
1345 let a_def = match self.tcx.def_map.borrow().get(&cur_ty.id) {
1a4d82fc
JJ
1346 None => {
1347 self.tcx
1348 .sess
1349 .fatal(&format!(
1350 "unbound path {}",
c34b1796 1351 pprust::path_to_string(path)))
1a4d82fc 1352 }
c34b1796 1353 Some(d) => d.full_def()
1a4d82fc
JJ
1354 };
1355 match a_def {
1356 def::DefTy(did, _) | def::DefStruct(did) => {
1357 let generics = ty::lookup_item_type(self.tcx, did).generics;
1358
1359 let expected =
1360 generics.regions.len(subst::TypeSpace) as u32;
1361 let lifetimes =
1362 path.segments.last().unwrap().parameters.lifetimes();
1363 let mut insert = Vec::new();
9346a6ac 1364 if lifetimes.is_empty() {
1a4d82fc 1365 let anon = self.cur_anon.get();
85aaf69f 1366 for (i, a) in (anon..anon+expected).enumerate() {
1a4d82fc
JJ
1367 if anon_nums.contains(&a) {
1368 insert.push(i as u32);
1369 }
1370 self.track_anon(a);
1371 }
1372 self.inc_and_offset_cur_anon(expected);
1373 } else {
1374 for (i, lt) in lifetimes.iter().enumerate() {
1375 if region_names.contains(&lt.name) {
1376 insert.push(i as u32);
1377 }
1378 }
1379 }
1380 let rebuild_info = RebuildPathInfo {
1381 path: path,
1382 indexes: insert,
1383 expected: expected,
1384 anon_nums: anon_nums,
1385 region_names: region_names
1386 };
1387 let new_path = self.rebuild_path(rebuild_info, lifetime);
c34b1796
AL
1388 let qself = maybe_qself.as_ref().map(|qself| {
1389 ast::QSelf {
1390 ty: self.rebuild_arg_ty_or_output(&qself.ty, lifetime,
1391 anon_nums, region_names),
1392 position: qself.position
1393 }
1394 });
1a4d82fc
JJ
1395 let to = ast::Ty {
1396 id: cur_ty.id,
c34b1796 1397 node: ast::TyPath(qself, new_path),
1a4d82fc
JJ
1398 span: cur_ty.span
1399 };
1400 new_ty = self.rebuild_ty(new_ty, P(to));
1401 }
1402 _ => ()
1403 }
1404
1405 }
1406
1407 ast::TyPtr(ref mut_ty) => {
1408 ty_queue.push(&*mut_ty.ty);
1409 }
1410 ast::TyVec(ref ty) |
1411 ast::TyFixedLengthVec(ref ty, _) => {
1412 ty_queue.push(&**ty);
1413 }
1414 ast::TyTup(ref tys) => ty_queue.extend(tys.iter().map(|ty| &**ty)),
1415 _ => {}
1416 }
1417 }
1418 new_ty
1419 }
1420
1421 fn rebuild_ty(&self,
1422 from: P<ast::Ty>,
1423 to: P<ast::Ty>)
1424 -> P<ast::Ty> {
1425
1426 fn build_to(from: P<ast::Ty>,
1427 to: &mut Option<P<ast::Ty>>)
1428 -> P<ast::Ty> {
1429 if Some(from.id) == to.as_ref().map(|ty| ty.id) {
1430 return to.take().expect("`to` type found more than once during rebuild");
1431 }
1432 from.map(|ast::Ty {id, node, span}| {
1433 let new_node = match node {
1434 ast::TyRptr(lifetime, mut_ty) => {
1435 ast::TyRptr(lifetime, ast::MutTy {
1436 mutbl: mut_ty.mutbl,
1437 ty: build_to(mut_ty.ty, to),
1438 })
1439 }
1440 ast::TyPtr(mut_ty) => {
1441 ast::TyPtr(ast::MutTy {
1442 mutbl: mut_ty.mutbl,
1443 ty: build_to(mut_ty.ty, to),
1444 })
1445 }
1446 ast::TyVec(ty) => ast::TyVec(build_to(ty, to)),
1447 ast::TyFixedLengthVec(ty, e) => {
1448 ast::TyFixedLengthVec(build_to(ty, to), e)
1449 }
1450 ast::TyTup(tys) => {
1451 ast::TyTup(tys.into_iter().map(|ty| build_to(ty, to)).collect())
1452 }
1453 ast::TyParen(typ) => ast::TyParen(build_to(typ, to)),
1454 other => other
1455 };
1456 ast::Ty { id: id, node: new_node, span: span }
1457 })
1458 }
1459
1460 build_to(from, &mut Some(to))
1461 }
1462
1463 fn rebuild_path(&self,
1464 rebuild_info: RebuildPathInfo,
1465 lifetime: ast::Lifetime)
1466 -> ast::Path
1467 {
1468 let RebuildPathInfo {
1469 path,
1470 indexes,
1471 expected,
1472 anon_nums,
1473 region_names,
1474 } = rebuild_info;
1475
1476 let last_seg = path.segments.last().unwrap();
1477 let new_parameters = match last_seg.parameters {
1478 ast::ParenthesizedParameters(..) => {
1479 last_seg.parameters.clone()
1480 }
1481
1482 ast::AngleBracketedParameters(ref data) => {
1483 let mut new_lts = Vec::new();
9346a6ac 1484 if data.lifetimes.is_empty() {
1a4d82fc 1485 // traverse once to see if there's a need to insert lifetime
85aaf69f 1486 let need_insert = (0..expected).any(|i| {
1a4d82fc
JJ
1487 indexes.contains(&i)
1488 });
1489 if need_insert {
85aaf69f 1490 for i in 0..expected {
1a4d82fc
JJ
1491 if indexes.contains(&i) {
1492 new_lts.push(lifetime);
1493 } else {
1494 new_lts.push(self.life_giver.give_lifetime());
1495 }
1496 }
1497 }
1498 } else {
1499 for (i, lt) in data.lifetimes.iter().enumerate() {
1500 if indexes.contains(&(i as u32)) {
1501 new_lts.push(lifetime);
1502 } else {
1503 new_lts.push(*lt);
1504 }
1505 }
1506 }
1507 let new_types = data.types.map(|t| {
1508 self.rebuild_arg_ty_or_output(&**t, lifetime, anon_nums, region_names)
1509 });
1510 let new_bindings = data.bindings.map(|b| {
1511 P(ast::TypeBinding {
1512 id: b.id,
1513 ident: b.ident,
1514 ty: self.rebuild_arg_ty_or_output(&*b.ty,
1515 lifetime,
1516 anon_nums,
1517 region_names),
1518 span: b.span
1519 })
1520 });
1521 ast::AngleBracketedParameters(ast::AngleBracketedParameterData {
1522 lifetimes: new_lts,
1523 types: new_types,
1524 bindings: new_bindings,
1525 })
1526 }
1527 };
1528 let new_seg = ast::PathSegment {
1529 identifier: last_seg.identifier,
1530 parameters: new_parameters
1531 };
1532 let mut new_segs = Vec::new();
1533 new_segs.push_all(path.segments.init());
1534 new_segs.push(new_seg);
1535 ast::Path {
1536 span: path.span,
1537 global: path.global,
1538 segments: new_segs
1539 }
1540 }
1541}
1542
1543impl<'a, 'tcx> ErrorReportingHelpers<'tcx> for InferCtxt<'a, 'tcx> {
1544 fn give_expl_lifetime_param(&self,
1545 decl: &ast::FnDecl,
1546 unsafety: ast::Unsafety,
62682a34 1547 constness: ast::Constness,
1a4d82fc
JJ
1548 ident: ast::Ident,
1549 opt_explicit_self: Option<&ast::ExplicitSelf_>,
1550 generics: &ast::Generics,
62682a34
SL
1551 span: Span) {
1552 let suggested_fn = pprust::fun_to_string(decl, unsafety, constness, ident,
1553 opt_explicit_self, generics);
1a4d82fc
JJ
1554 let msg = format!("consider using an explicit lifetime \
1555 parameter as shown: {}", suggested_fn);
85aaf69f 1556 self.tcx.sess.span_help(span, &msg[..]);
1a4d82fc
JJ
1557 }
1558
1559 fn report_inference_failure(&self,
1560 var_origin: RegionVariableOrigin) {
62682a34
SL
1561 let br_string = |br: ty::BoundRegion| {
1562 let mut s = br.to_string();
1563 if !s.is_empty() {
1564 s.push_str(" ");
1565 }
1566 s
1567 };
1a4d82fc
JJ
1568 let var_description = match var_origin {
1569 infer::MiscVariable(_) => "".to_string(),
1570 infer::PatternRegion(_) => " for pattern".to_string(),
1571 infer::AddrOfRegion(_) => " for borrow expression".to_string(),
1a4d82fc
JJ
1572 infer::Autoref(_) => " for autoref".to_string(),
1573 infer::Coercion(_) => " for automatic coercion".to_string(),
1574 infer::LateBoundRegion(_, br, infer::FnCall) => {
62682a34
SL
1575 format!(" for lifetime parameter {}in function call",
1576 br_string(br))
1a4d82fc
JJ
1577 }
1578 infer::LateBoundRegion(_, br, infer::HigherRankedType) => {
62682a34 1579 format!(" for lifetime parameter {}in generic type", br_string(br))
1a4d82fc
JJ
1580 }
1581 infer::LateBoundRegion(_, br, infer::AssocTypeProjection(type_name)) => {
62682a34
SL
1582 format!(" for lifetime parameter {}in trait containing associated type `{}`",
1583 br_string(br), token::get_name(type_name))
1a4d82fc
JJ
1584 }
1585 infer::EarlyBoundRegion(_, name) => {
1586 format!(" for lifetime parameter `{}`",
85aaf69f 1587 &token::get_name(name))
1a4d82fc
JJ
1588 }
1589 infer::BoundRegionInCoherence(name) => {
1590 format!(" for lifetime parameter `{}` in coherence check",
85aaf69f 1591 &token::get_name(name))
1a4d82fc
JJ
1592 }
1593 infer::UpvarRegion(ref upvar_id, _) => {
1594 format!(" for capture of `{}` by closure",
85aaf69f 1595 ty::local_var_name_str(self.tcx, upvar_id.var_id).to_string())
1a4d82fc
JJ
1596 }
1597 };
1598
1599 self.tcx.sess.span_err(
1600 var_origin.span(),
1601 &format!("cannot infer an appropriate lifetime{} \
1602 due to conflicting requirements",
c34b1796 1603 var_description));
1a4d82fc
JJ
1604 }
1605
1606 fn note_region_origin(&self, origin: &SubregionOrigin<'tcx>) {
1607 match *origin {
62682a34
SL
1608 infer::Subtype(ref trace) |
1609 infer::DefaultExistentialBound(ref trace) => {
1a4d82fc
JJ
1610 let desc = match trace.origin {
1611 infer::Misc(_) => {
c34b1796 1612 "types are compatible"
1a4d82fc
JJ
1613 }
1614 infer::MethodCompatCheck(_) => {
c34b1796 1615 "method type is compatible with trait"
1a4d82fc
JJ
1616 }
1617 infer::ExprAssignable(_) => {
c34b1796 1618 "expression is assignable"
1a4d82fc
JJ
1619 }
1620 infer::RelateTraitRefs(_) => {
c34b1796 1621 "traits are compatible"
1a4d82fc
JJ
1622 }
1623 infer::RelateSelfType(_) => {
c34b1796 1624 "self type matches impl self type"
1a4d82fc
JJ
1625 }
1626 infer::RelateOutputImplTypes(_) => {
c34b1796
AL
1627 "trait type parameters matches those \
1628 specified on the impl"
1a4d82fc
JJ
1629 }
1630 infer::MatchExpressionArm(_, _) => {
c34b1796 1631 "match arms have compatible types"
1a4d82fc
JJ
1632 }
1633 infer::IfExpression(_) => {
c34b1796 1634 "if and else have compatible types"
1a4d82fc
JJ
1635 }
1636 infer::IfExpressionWithNoElse(_) => {
c34b1796 1637 "if may be missing an else clause"
1a4d82fc
JJ
1638 }
1639 infer::RangeExpression(_) => {
c34b1796 1640 "start and end of range have compatible types"
1a4d82fc
JJ
1641 }
1642 infer::EquatePredicate(_) => {
c34b1796 1643 "equality where clause is satisfied"
1a4d82fc
JJ
1644 }
1645 };
1646
1647 match self.values_str(&trace.values) {
1648 Some(values_str) => {
1649 self.tcx.sess.span_note(
1650 trace.origin.span(),
1651 &format!("...so that {} ({})",
c34b1796 1652 desc, values_str));
1a4d82fc
JJ
1653 }
1654 None => {
1655 // Really should avoid printing this error at
1656 // all, since it is derived, but that would
1657 // require more refactoring than I feel like
1658 // doing right now. - nmatsakis
1659 self.tcx.sess.span_note(
1660 trace.origin.span(),
c34b1796 1661 &format!("...so that {}", desc));
1a4d82fc
JJ
1662 }
1663 }
1664 }
1665 infer::Reborrow(span) => {
1666 self.tcx.sess.span_note(
1667 span,
1668 "...so that reference does not outlive \
1669 borrowed content");
1670 }
1671 infer::ReborrowUpvar(span, ref upvar_id) => {
1672 self.tcx.sess.span_note(
1673 span,
1674 &format!(
1675 "...so that closure can access `{}`",
1676 ty::local_var_name_str(self.tcx, upvar_id.var_id)
c34b1796 1677 .to_string()))
1a4d82fc
JJ
1678 }
1679 infer::InfStackClosure(span) => {
1680 self.tcx.sess.span_note(
1681 span,
1682 "...so that closure does not outlive its stack frame");
1683 }
1684 infer::InvokeClosure(span) => {
1685 self.tcx.sess.span_note(
1686 span,
1687 "...so that closure is not invoked outside its lifetime");
1688 }
1689 infer::DerefPointer(span) => {
1690 self.tcx.sess.span_note(
1691 span,
1692 "...so that pointer is not dereferenced \
1693 outside its lifetime");
1694 }
1695 infer::FreeVariable(span, id) => {
1696 self.tcx.sess.span_note(
1697 span,
1698 &format!("...so that captured variable `{}` \
1699 does not outlive the enclosing closure",
1700 ty::local_var_name_str(
1701 self.tcx,
c34b1796 1702 id).to_string()));
1a4d82fc
JJ
1703 }
1704 infer::IndexSlice(span) => {
1705 self.tcx.sess.span_note(
1706 span,
1707 "...so that slice is not indexed outside the lifetime");
1708 }
1709 infer::RelateObjectBound(span) => {
1710 self.tcx.sess.span_note(
1711 span,
1712 "...so that it can be closed over into an object");
1713 }
1714 infer::CallRcvr(span) => {
1715 self.tcx.sess.span_note(
1716 span,
1717 "...so that method receiver is valid for the method call");
1718 }
1719 infer::CallArg(span) => {
1720 self.tcx.sess.span_note(
1721 span,
1722 "...so that argument is valid for the call");
1723 }
1724 infer::CallReturn(span) => {
1725 self.tcx.sess.span_note(
1726 span,
1727 "...so that return value is valid for the call");
1728 }
85aaf69f
SL
1729 infer::Operand(span) => {
1730 self.tcx.sess.span_err(
1731 span,
1732 "...so that operand is valid for operation");
1733 }
1a4d82fc
JJ
1734 infer::AddrOf(span) => {
1735 self.tcx.sess.span_note(
1736 span,
1737 "...so that reference is valid \
1738 at the time of borrow");
1739 }
1740 infer::AutoBorrow(span) => {
1741 self.tcx.sess.span_note(
1742 span,
1743 "...so that auto-reference is valid \
1744 at the time of borrow");
1745 }
1746 infer::ExprTypeIsNotInScope(t, span) => {
1747 self.tcx.sess.span_note(
1748 span,
1749 &format!("...so type `{}` of expression is valid during the \
1750 expression",
c34b1796 1751 self.ty_to_string(t)));
1a4d82fc
JJ
1752 }
1753 infer::BindingTypeIsNotValidAtDecl(span) => {
1754 self.tcx.sess.span_note(
1755 span,
1756 "...so that variable is valid at time of its declaration");
1757 }
1758 infer::ReferenceOutlivesReferent(ty, span) => {
1759 self.tcx.sess.span_note(
1760 span,
1761 &format!("...so that the reference type `{}` \
1762 does not outlive the data it points at",
c34b1796 1763 self.ty_to_string(ty)));
1a4d82fc
JJ
1764 }
1765 infer::RelateParamBound(span, t) => {
1766 self.tcx.sess.span_note(
1767 span,
1768 &format!("...so that the type `{}` \
85aaf69f 1769 will meet its required lifetime bounds",
c34b1796 1770 self.ty_to_string(t)));
1a4d82fc
JJ
1771 }
1772 infer::RelateDefaultParamBound(span, t) => {
1773 self.tcx.sess.span_note(
1774 span,
1775 &format!("...so that type parameter \
1776 instantiated with `{}`, \
1777 will meet its declared lifetime bounds",
c34b1796 1778 self.ty_to_string(t)));
1a4d82fc
JJ
1779 }
1780 infer::RelateRegionParamBound(span) => {
1781 self.tcx.sess.span_note(
1782 span,
c34b1796
AL
1783 "...so that the declared lifetime parameter bounds \
1784 are satisfied");
1a4d82fc 1785 }
85aaf69f
SL
1786 infer::SafeDestructor(span) => {
1787 self.tcx.sess.span_note(
1788 span,
1789 "...so that references are valid when the destructor \
1790 runs")
1791 }
1a4d82fc
JJ
1792 }
1793 }
1794}
1795
1796pub trait Resolvable<'tcx> {
1797 fn resolve<'a>(&self, infcx: &InferCtxt<'a, 'tcx>) -> Self;
1798 fn contains_error(&self) -> bool;
1799}
1800
1801impl<'tcx> Resolvable<'tcx> for Ty<'tcx> {
1802 fn resolve<'a>(&self, infcx: &InferCtxt<'a, 'tcx>) -> Ty<'tcx> {
1803 infcx.resolve_type_vars_if_possible(self)
1804 }
1805 fn contains_error(&self) -> bool {
1806 ty::type_is_error(*self)
1807 }
1808}
1809
d9579d0f 1810impl<'tcx> Resolvable<'tcx> for ty::TraitRef<'tcx> {
1a4d82fc 1811 fn resolve<'a>(&self, infcx: &InferCtxt<'a, 'tcx>)
d9579d0f
AL
1812 -> ty::TraitRef<'tcx> {
1813 infcx.resolve_type_vars_if_possible(self)
1a4d82fc
JJ
1814 }
1815 fn contains_error(&self) -> bool {
d9579d0f 1816 ty::trait_ref_contains_error(self)
1a4d82fc
JJ
1817 }
1818}
1819
1820impl<'tcx> Resolvable<'tcx> for ty::PolyTraitRef<'tcx> {
1821 fn resolve<'a>(&self,
1822 infcx: &InferCtxt<'a, 'tcx>)
1823 -> ty::PolyTraitRef<'tcx>
1824 {
1825 infcx.resolve_type_vars_if_possible(self)
1826 }
1827
1828 fn contains_error(&self) -> bool {
d9579d0f 1829 ty::trait_ref_contains_error(&self.0)
1a4d82fc
JJ
1830 }
1831}
1832
1833fn lifetimes_in_scope(tcx: &ty::ctxt,
1834 scope_id: ast::NodeId)
1835 -> Vec<ast::LifetimeDef> {
1836 let mut taken = Vec::new();
1837 let parent = tcx.map.get_parent(scope_id);
1838 let method_id_opt = match tcx.map.find(parent) {
1839 Some(node) => match node {
1840 ast_map::NodeItem(item) => match item.node {
62682a34 1841 ast::ItemFn(_, _, _, _, ref gen, _) => {
c34b1796 1842 taken.push_all(&gen.lifetimes);
1a4d82fc
JJ
1843 None
1844 },
1845 _ => None
1846 },
1847 ast_map::NodeImplItem(ii) => {
c34b1796
AL
1848 match ii.node {
1849 ast::MethodImplItem(ref sig, _) => {
1850 taken.push_all(&sig.generics.lifetimes);
1851 Some(ii.id)
1a4d82fc 1852 }
d9579d0f
AL
1853 ast::MacImplItem(_) => tcx.sess.bug("unexpanded macro"),
1854 _ => None,
1a4d82fc
JJ
1855 }
1856 }
1857 _ => None
1858 },
1859 None => None
1860 };
1861 if method_id_opt.is_some() {
1862 let method_id = method_id_opt.unwrap();
1863 let parent = tcx.map.get_parent(method_id);
1864 match tcx.map.find(parent) {
1865 Some(node) => match node {
1866 ast_map::NodeItem(item) => match item.node {
1867 ast::ItemImpl(_, _, ref gen, _, _, _) => {
85aaf69f 1868 taken.push_all(&gen.lifetimes);
1a4d82fc
JJ
1869 }
1870 _ => ()
1871 },
1872 _ => ()
1873 },
1874 None => ()
1875 }
1876 }
1877 return taken;
1878}
1879
1880// LifeGiver is responsible for generating fresh lifetime names
1881struct LifeGiver {
1882 taken: HashSet<String>,
c34b1796 1883 counter: Cell<usize>,
1a4d82fc
JJ
1884 generated: RefCell<Vec<ast::Lifetime>>,
1885}
1886
1887impl LifeGiver {
1888 fn with_taken(taken: &[ast::LifetimeDef]) -> LifeGiver {
1889 let mut taken_ = HashSet::new();
85aaf69f
SL
1890 for lt in taken {
1891 let lt_name = token::get_name(lt.lifetime.name).to_string();
1a4d82fc
JJ
1892 taken_.insert(lt_name);
1893 }
1894 LifeGiver {
1895 taken: taken_,
1896 counter: Cell::new(0),
1897 generated: RefCell::new(Vec::new()),
1898 }
1899 }
1900
1901 fn inc_counter(&self) {
1902 let c = self.counter.get();
1903 self.counter.set(c+1);
1904 }
1905
1906 fn give_lifetime(&self) -> ast::Lifetime {
1907 let mut lifetime;
1908 loop {
62682a34 1909 let mut s = String::from("'");
c34b1796 1910 s.push_str(&num_to_string(self.counter.get()));
1a4d82fc
JJ
1911 if !self.taken.contains(&s) {
1912 lifetime = name_to_dummy_lifetime(
85aaf69f 1913 token::str_to_ident(&s[..]).name);
1a4d82fc
JJ
1914 self.generated.borrow_mut().push(lifetime);
1915 break;
1916 }
1917 self.inc_counter();
1918 }
1919 self.inc_counter();
1920 return lifetime;
1921
1922 // 0 .. 25 generates a .. z, 26 .. 51 generates aa .. zz, and so on
c34b1796 1923 fn num_to_string(counter: usize) -> String {
1a4d82fc
JJ
1924 let mut s = String::new();
1925 let (n, r) = (counter/26 + 1, counter % 26);
1926 let letter: char = from_u32((r+97) as u32).unwrap();
85aaf69f 1927 for _ in 0..n {
1a4d82fc
JJ
1928 s.push(letter);
1929 }
1930 s
1931 }
1932 }
1933
1934 fn get_generated_lifetimes(&self) -> Vec<ast::Lifetime> {
1935 self.generated.borrow().clone()
1936 }
1937}