From 01dcb3bdf0fd779208c915d704ae634beb5c4448 Mon Sep 17 00:00:00 2001 From: Jared Roesch Date: Sun, 12 Jul 2015 20:33:17 -0700 Subject: [PATCH] Refactor the default type parameter algorithm The algorithm was not correctly detecting conflicts after moving defaults into TypeVariableValue. The updated algorithm correctly detects and reports conflicts with information about where the conflict occured and which items the defaults were introduced by. The span's for said items are not being correctly attached and still need to be patched. --- src/librustc/middle/infer/error_reporting.rs | 4 +- src/librustc/middle/infer/mod.rs | 41 +++-- src/librustc/middle/infer/type_variable.rs | 11 +- src/librustc/middle/ty.rs | 28 +++- src/librustc_typeck/astconv.rs | 4 +- src/librustc_typeck/check/method/confirm.rs | 4 +- src/librustc_typeck/check/method/mod.rs | 2 +- src/librustc_typeck/check/method/probe.rs | 2 +- src/librustc_typeck/check/mod.rs | 151 ++++++++++++++++--- src/librustc_typeck/collect.rs | 2 +- src/rust-installer | 2 +- 11 files changed, 198 insertions(+), 53 deletions(-) diff --git a/src/librustc/middle/infer/error_reporting.rs b/src/librustc/middle/infer/error_reporting.rs index 8d66ffac5d1..fbf19a10d93 100644 --- a/src/librustc/middle/infer/error_reporting.rs +++ b/src/librustc/middle/infer/error_reporting.rs @@ -893,8 +893,8 @@ fn report_processed_errors(&self, self.report_inference_failure(vo.clone()); } self.give_suggestion(same_regions); - for &(ref trace, terr) in trace_origins { - self.report_and_explain_type_error(trace.clone(), &terr); + for &(ref trace, ref terr) in trace_origins { + self.report_and_explain_type_error(trace.clone(), terr); } } diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs index db6e0ad1d4a..d38417143ce 100644 --- a/src/librustc/middle/infer/mod.rs +++ b/src/librustc/middle/infer/mod.rs @@ -40,6 +40,7 @@ use syntax::codemap::{Span, DUMMY_SP}; use util::nodemap::{FnvHashMap, NodeMap}; +use ast_map; use self::combine::CombineFields; use self::region_inference::{RegionVarBindings, RegionSnapshot}; use self::error_reporting::ErrorReporting; @@ -72,7 +73,7 @@ pub struct InferCtxt<'a, 'tcx: 'a> { // We instantiate UnificationTable with bounds because the // types that might instantiate a general type variable have an // order, represented by its upper and lower bounds. - type_variables: RefCell>, + pub type_variables: RefCell>, // Map from integral variable to the kind of integer it represents int_unification_table: RefCell>, @@ -690,7 +691,7 @@ pub fn unsolved_variables(&self) -> Vec> { variables.extend(unbound_ty_vars); variables.extend(unbound_int_vars); variables.extend(unbound_float_vars); - + return variables; } @@ -1047,15 +1048,36 @@ pub fn region_vars_for_defs(&self, } pub fn type_vars_for_defs(&self, + span: Span, + // substs: Substs, defs: &[ty::TypeParameterDef<'tcx>]) -> Vec> { + + fn definition_span<'tcx>(tcx: &ty::ctxt<'tcx>, def_id: ast::DefId) -> Span { + let parent = tcx.map.get_parent(def_id.node); + debug!("definition_span def_id={:?} parent={:?} node={:?} parent_node={:?}", + def_id, parent, tcx.map.find(def_id.node), tcx.map.find(parent)); + match tcx.map.find(parent) { + None => DUMMY_SP, + Some(ref node) => match *node { + ast_map::NodeItem(ref item) => item.span, + ast_map::NodeForeignItem(ref item) => item.span, + ast_map::NodeTraitItem(ref item) => item.span, + ast_map::NodeImplItem(ref item) => item.span, + _ => DUMMY_SP + } + } + } + let mut substs = Substs::empty(); let mut vars = Vec::with_capacity(defs.len()); for def in defs.iter() { let default = def.default.map(|default| { type_variable::Default { - ty: default + ty: default, + origin_span: span, + definition_span: definition_span(self.tcx, def.def_id) } }); //.subst(self.tcx, &substs) @@ -1077,7 +1099,8 @@ pub fn fresh_substs_for_generics(&self, let mut type_params = subst::VecPerParamSpace::empty(); for space in subst::ParamSpace::all().iter() { - type_params.replace(*space, self.type_vars_for_defs(generics.types.get_slice(*space))) + type_params.replace(*space, + self.type_vars_for_defs(span, generics.types.get_slice(*space))) } let region_params = @@ -1102,7 +1125,7 @@ pub fn fresh_substs_for_trait(&self, assert!(generics.regions.len(subst::FnSpace) == 0); let type_parameter_defs = generics.types.get_slice(subst::TypeSpace); - let type_parameters = self.type_vars_for_defs(type_parameter_defs); + let type_parameters = self.type_vars_for_defs(span, type_parameter_defs); let region_param_defs = generics.regions.get_slice(subst::TypeSpace); let regions = self.region_vars_for_defs(span, region_param_defs); @@ -1344,13 +1367,13 @@ pub fn report_mismatched_types(&self, pub fn report_conflicting_default_types(&self, span: Span, - expected: Ty<'tcx>, - actual: Ty<'tcx>) { + expected: type_variable::Default<'tcx>, + actual: type_variable::Default<'tcx>) { let trace = TypeTrace { origin: Misc(span), values: Types(ty::expected_found { - expected: expected, - found: actual + expected: expected.ty, + found: actual.ty }) }; diff --git a/src/librustc/middle/infer/type_variable.rs b/src/librustc/middle/infer/type_variable.rs index fa7cd143e3b..8707306a149 100644 --- a/src/librustc/middle/infer/type_variable.rs +++ b/src/librustc/middle/infer/type_variable.rs @@ -11,8 +11,9 @@ pub use self::RelationDir::*; use self::TypeVariableValue::*; use self::UndoEntry::*; - use middle::ty::{self, Ty}; +use syntax::codemap::Span; + use std::cmp::min; use std::marker::PhantomData; use std::mem; @@ -38,9 +39,13 @@ enum TypeVariableValue<'tcx> { // We will use this to store the required information to recapitulate what happened when // an error occurs. -#[derive(Clone)] +#[derive(Clone, Debug, PartialEq, Eq, Hash)] pub struct Default<'tcx> { - pub ty: Ty<'tcx> + pub ty: Ty<'tcx>, + /// The span where the default was incurred + pub origin_span: Span, + /// The definition that the default originates from + pub definition_span: Span } pub struct Snapshot { diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index a08c5e1f73f..19add679bbf 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -54,6 +54,7 @@ use middle::region; use middle::resolve_lifetime; use middle::infer; +use middle::infer::type_variable; use middle::pat_util; use middle::region::RegionMaps; use middle::stability; @@ -2068,7 +2069,7 @@ pub enum TypeError<'tcx> { ConvergenceMismatch(ExpectedFound), ProjectionNameMismatched(ExpectedFound), ProjectionBoundsLength(ExpectedFound), - terr_ty_param_default_mismatch(expected_found>) + TyParamDefaultMismatch(ExpectedFound>) } /// Bounds suitable for an existentially quantified type parameter @@ -5083,9 +5084,9 @@ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { values.found) }, terr_ty_param_default_mismatch(ref values) => { - write!(f, "conflicting type parameter defaults {} {}", - values.expected, - values.found) + write!(f, "conflicting type parameter defaults {} and {}", + values.expected.ty, + values.found.ty) } } } @@ -5405,7 +5406,7 @@ pub fn field_idx_strict(&self, name: ast::Name, fields: &[Field<'tcx>]) pub fn note_and_explain_type_err(&self, err: &TypeError<'tcx>, sp: Span) { use self::TypeError::*; - match *err { + match err.clone() { RegionsDoesNotOutlive(subregion, superregion) => { self.note_and_explain_region("", subregion, "..."); self.note_and_explain_region("...does not necessarily outlive ", @@ -5444,10 +5445,21 @@ pub fn note_and_explain_type_err(&self, err: &TypeError<'tcx>, sp: Span) { using it as a trait object")); } }, - terr_ty_param_default_mismatch(expected) => { + terr_ty_param_default_mismatch(values) => { + let expected = values.expected; + let found = values.found; self.sess.span_note(sp, - &format!("found conflicting defaults {:?} {:?}", - expected.expected, expected.found)) + &format!("conflicting type parameter defaults {} and {}", + expected.ty, + found.ty)); + self.sess.span_note(expected.definition_span, + &format!("...a default was defined")); + self.sess.span_note(expected.origin_span, + &format!("...that was applied to an unconstrained type variable here")); + self.sess.span_note(found.definition_span, + &format!("...a second default was defined")); + self.sess.span_note(found.origin_span, + &format!("...that also applies to the same type variable here")); } _ => {} } diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs index 5ed1da2fede..3925f4e751c 100644 --- a/src/librustc_typeck/astconv.rs +++ b/src/librustc_typeck/astconv.rs @@ -111,7 +111,7 @@ fn get_free_substs(&self) -> Option<&Substs<'tcx>> { } /// What type should we use when a type is omitted? - fn ty_infer(&self, default: Option>, span: Span) -> Ty<'tcx>; + fn ty_infer(&self, default: Option>, span: Span) -> Ty<'tcx>; /// Projecting an associated type from a (potentially) /// higher-ranked trait reference is more complicated, because of @@ -403,7 +403,7 @@ fn create_substs_for_ast_path<'tcx>( // they were optional (e.g. paths inside expressions). let mut type_substs = if param_mode == PathParamMode::Optional && types_provided.is_empty() { - ty_param_defs.iter().map(|p| this.ty_infer(p.default, span)).collect() + ty_param_defs.iter().map(|p| this.ty_infer(Some(p.clone()), span)).collect() } else { types_provided }; diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs index e3b9b990cb9..488428833ac 100644 --- a/src/librustc_typeck/check/method/confirm.rs +++ b/src/librustc_typeck/check/method/confirm.rs @@ -315,11 +315,11 @@ fn instantiate_method_substs(&mut self, let method_types = { if num_supplied_types == 0 { - self.fcx.infcx().type_vars_for_defs(method_types) + self.fcx.infcx().type_vars_for_defs(self.span, method_types) } else if num_method_types == 0 { span_err!(self.tcx().sess, self.span, E0035, "does not take type parameters"); - self.fcx.infcx().type_vars_for_defs(method_types) + self.fcx.infcx().type_vars_for_defs(self.span, method_types) } else if num_supplied_types != num_method_types { span_err!(self.tcx().sess, self.span, E0036, "incorrect number of type parameters given for this method"); diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs index 2ca5a88fb06..767797e843c 100644 --- a/src/librustc_typeck/check/method/mod.rs +++ b/src/librustc_typeck/check/method/mod.rs @@ -176,7 +176,7 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, } None => { - fcx.inh.infcx.type_vars_for_defs(type_parameter_defs) + fcx.inh.infcx.type_vars_for_defs(span, type_parameter_defs) } }; diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs index 88bd000cfdd..b190e7a7a48 100644 --- a/src/librustc_typeck/check/method/probe.rs +++ b/src/librustc_typeck/check/method/probe.rs @@ -1207,7 +1207,7 @@ fn xform_method_self_ty(&self, !method.generics.regions.is_empty_in(subst::FnSpace) { let method_types = - self.infcx().type_vars_for_defs( + self.infcx().type_vars_for_defs(self.span, method.generics.types.get_slice(subst::FnSpace)); // In general, during probe we erase regions. See diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs index f6a4dbca291..3a93c7ed916 100644 --- a/src/librustc_typeck/check/mod.rs +++ b/src/librustc_typeck/check/mod.rs @@ -1139,8 +1139,9 @@ fn trait_defines_associated_type_named(&self, trait_def.associated_type_names.contains(&assoc_name) } - fn ty_infer(&self, default: Option>, _span: Span) -> Ty<'tcx> { - let default = default.map(|t| type_variable::Default { ty: t }); + fn ty_infer(&self, ty_param_def: Option>, span: Span) -> Ty<'tcx> { + let default = ty_param_def.and_then(|t| + t.default.map(|ty| type_variable::Default { ty: ty, origin_span: span, definition_span: span })); self.infcx().next_ty_var_with_default(default) } @@ -1694,39 +1695,61 @@ fn check_casts(&self) { fn select_all_obligations_and_apply_defaults(&self) { use middle::ty::UnconstrainedNumeric::{UnconstrainedInt, UnconstrainedFloat, Neither}; - // debug!("select_all_obligations_and_apply_defaults: defaults={:?}", self.infcx().defaults); + // For the time being this errs on the side of being memory wasteful but provides better + // error reporting. + // let type_variables = self.infcx().type_variables.clone(); + // There is a possibility that this algorithm will have to run an arbitrary number of times + // to terminate so we bound it by the compiler's recursion limit. for _ in (0..self.tcx().sess.recursion_limit.get()) { + // First we try to solve all obligations, it is possible that the last iteration + // has made it possible to make more progress. self.select_obligations_where_possible(); + let mut conflicts = Vec::new(); + + // Collect all unsolved type, integral and floating point variables. let unsolved_variables = self.inh.infcx.unsolved_variables(); + + // We must collect the defaults *before* we do any unification. Because we have + // directly attached defaults to the type variables any unification that occurs + // will erase defaults causing conflicting defaults to be completely ignored. + let default_map: FnvHashMap<_, _> = + unsolved_variables + .iter() + .filter_map(|t| self.infcx().default(t).map(|d| (t, d))) + .collect(); + let mut unbound_tyvars = HashSet::new(); - // Gather all unconstrainted integer and float variables + debug!("select_all_obligations_and_apply_defaults: defaults={:?}", default_map); + + // We loop over the unsolved variables, resolving them and if they are + // and unconstrainted numberic type we add them to the set of unbound + // variables. We do this so we only apply literal fallback to type + // variables without defaults. for ty in &unsolved_variables { let resolved = self.infcx().resolve_type_vars_if_possible(ty); if self.infcx().type_var_diverges(resolved) { demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().mk_nil()); } else { match self.infcx().type_is_unconstrained_numeric(resolved) { - UnconstrainedInt => { + UnconstrainedInt | UnconstrainedFloat => { unbound_tyvars.insert(resolved); }, - UnconstrainedFloat => { - unbound_tyvars.insert(resolved); - } Neither => {} } } } - // Collect the set of variables that need fallback applied + // We now remove any numeric types that also have defaults, and instead insert + // the type variable with a defined fallback. for ty in &unsolved_variables { - if let Some(_) = self.inh.infcx.default(ty) { + if let Some(_default) = default_map.get(ty) { let resolved = self.infcx().resolve_type_vars_if_possible(ty); - // debug!("select_all_obligations_and_apply_defaults: ty: {:?} with default: {:?}", - // ty, self.inh.infcx.defaults.borrow().get(ty)); + debug!("select_all_obligations_and_apply_defaults: ty: {:?} with default: {:?}", + ty, _default); match resolved.sty { ty::TyInfer(ty::TyVar(_)) => { @@ -1745,11 +1768,21 @@ fn select_all_obligations_and_apply_defaults(&self) { } } + // If there are no more fallbacks to apply at this point we have applied all possible + // defaults and type inference will procede as normal. if unbound_tyvars.is_empty() { break; } - // Go through the unbound variables and unify them with the proper fallbacks + // Finally we go through each of the unbound type variables and unify them with + // the proper fallback, reporting a conflicting default error if any of the + // unifications fail. We know it must be a conflicting default because the + // variable would only be in `unbound_tyvars` and have a concrete value if + // it had been solved by previously applying a default. + + // We take a snapshot for use in error reporting. + let snapshot = self.infcx().type_variables.borrow_mut().snapshot(); + for ty in &unbound_tyvars { if self.infcx().type_var_diverges(ty) { demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().mk_nil()); @@ -1762,16 +1795,14 @@ fn select_all_obligations_and_apply_defaults(&self) { demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.f64) } Neither => { - if let Some(default) = self.inh.infcx.default(ty) { + if let Some(default) = default_map.get(ty) { + let default = default.clone(); match infer::mk_eqty(self.infcx(), false, - infer::Misc(codemap::DUMMY_SP), + infer::Misc(default.origin_span), ty, default.ty) { - Ok(()) => { /* ok */ } + Ok(()) => {} Err(_) => { - self.infcx().report_conflicting_default_types( - codemap::DUMMY_SP, - ty, - default.ty) + conflicts.push((*ty, default)); } } } @@ -1780,8 +1811,82 @@ fn select_all_obligations_and_apply_defaults(&self) { } } - self.select_obligations_where_possible(); + // There were some errors to report + if conflicts.len() > 0 { + self.infcx().type_variables.borrow_mut().rollback_to(snapshot); + + for (conflict, default) in conflicts { + let conflicting_default = + self.find_conflicting_default( + &unbound_tyvars, + &default_map, + conflict).unwrap_or(type_variable::Default { + ty: self.infcx().next_ty_var(), + origin_span: codemap::DUMMY_SP, + definition_span: codemap::DUMMY_SP + }); + + self.infcx().report_conflicting_default_types( + conflicting_default.origin_span, + conflicting_default, + default) + } + } else { + self.infcx().type_variables.borrow_mut().commit(snapshot) + } } + + self.select_obligations_where_possible(); + } + + // For use in error handling related to default type parameter fallback. We explicitly + // apply the default that caused conflict first to a local version of the type variable + // table then apply defaults until we find a conflict. That default must be the one + // that caused conflict earlier. + fn find_conflicting_default(&self, + unbound_vars: &HashSet>, + default_map: &FnvHashMap<&Ty<'tcx>, type_variable::Default<'tcx>>, + conflict: Ty<'tcx>) + -> Option> { + use middle::ty::UnconstrainedNumeric::{UnconstrainedInt, UnconstrainedFloat, Neither}; + + // Ensure that the conflicting default is applied first + let mut unbound_tyvars = Vec::with_capacity(unbound_vars.len() + 1); + unbound_tyvars.push(conflict); + unbound_tyvars.extend(unbound_vars.iter()); + + let mut result = None; + // We run the same code as above applying defaults in order, this time when + // we find the conflict we just return it for error reporting above. + for ty in &unbound_tyvars { + if self.infcx().type_var_diverges(ty) { + demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().mk_nil()); + } else { + match self.infcx().type_is_unconstrained_numeric(ty) { + UnconstrainedInt => { + demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.i32) + }, + UnconstrainedFloat => { + demand::eqtype(self, codemap::DUMMY_SP, *ty, self.tcx().types.f64) + }, + Neither => { + if let Some(default) = default_map.get(ty) { + let default = default.clone(); + match infer::mk_eqty(self.infcx(), false, + infer::Misc(default.origin_span), + ty, default.ty) { + Ok(()) => {} + Err(_) => { + result = Some(default); + } + } + } + } + } + } + } + + return result; } fn select_all_obligations_or_error(&self) { @@ -2495,7 +2600,7 @@ pub fn impl_self_ty<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, debug!("impl_self_ty: tps={:?} rps={:?} raw_ty={:?}", tps, rps, raw_ty); let rps = fcx.inh.infcx.region_vars_for_defs(span, rps); - let tps = fcx.inh.infcx.type_vars_for_defs(tps); + let tps = fcx.inh.infcx.type_vars_for_defs(span, tps); let substs = subst::Substs::new_type(tps, rps); let substd_ty = fcx.instantiate_type_scheme(span, &substs, &raw_ty); @@ -4715,7 +4820,7 @@ fn adjust_type_parameters<'a, 'tcx>( // Nothing specified at all: supply inference variables for // everything. if provided_len == 0 && !(require_type_space && space == subst::TypeSpace) { - substs.types.replace(space, fcx.infcx().type_vars_for_defs(&desired[..])); + substs.types.replace(space, fcx.infcx().type_vars_for_defs(span, &desired[..])); return; } diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs index 695991a97f0..8b38c58ce7a 100644 --- a/src/librustc_typeck/collect.rs +++ b/src/librustc_typeck/collect.rs @@ -404,7 +404,7 @@ fn trait_defines_associated_type_named(&self, } } - fn ty_infer(&self, _default: Option>, span: Span) -> Ty<'tcx> { + fn ty_infer(&self, _default: Option>, span: Span) -> Ty<'tcx> { span_err!(self.tcx().sess, span, E0121, "the type placeholder `_` is not allowed within types on item signatures"); self.tcx().types.err diff --git a/src/rust-installer b/src/rust-installer index c37d3747da7..8e4f8ea5815 160000 --- a/src/rust-installer +++ b/src/rust-installer @@ -1 +1 @@ -Subproject commit c37d3747da75c280237dc2d6b925078e69555499 +Subproject commit 8e4f8ea581502a2edc8177a040300e05ff7f91e3 -- 2.44.0