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