auto merge of #11982 : eddyb/rust/generic-default-type-params, r=pcwalton

Fixes #11964 and closes #8998.

7 files changed, 245 insertions, 80 deletions

diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index c4a30171687..7176b512c71 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -13,8 +13,10 @@
 use middle::ty;
 use middle::ty_fold;
 use middle::ty_fold::TypeFolder;
+use util::ppaux::Repr;
 
 use std::rc::Rc;
+use syntax::codemap::Span;
 use syntax::opt_vec::OptVec;
 
 ///////////////////////////////////////////////////////////////////////////
@@ -22,9 +24,16 @@ use syntax::opt_vec::OptVec;
 //
 // Just call `foo.subst(tcx, substs)` to perform a substitution across
 // `foo`.
+// Or use `foo.subst_spanned(tcx, substs, Some(span))` when there is more
+// information available (for better errors).
 
 pub trait Subst {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> Self;
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> Self {
+        self.subst_spanned(tcx, substs, None)
+    }
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> Self;
 }
 
 ///////////////////////////////////////////////////////////////////////////
@@ -36,11 +45,18 @@ pub trait Subst {
 // our current method/trait matching algorithm. - Niko
 
 impl Subst for ty::t {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::t {
-        if ty::substs_is_noop(substs) {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::t {
+        if ty::substs_is_noop(substs) && !ty::type_has_params(*self) {
             *self
         } else {
-            let mut folder = SubstFolder {tcx: tcx, substs: substs};
+            let mut folder = SubstFolder {
+                tcx: tcx,
+                substs: substs,
+                span: span,
+                root_ty: Some(*self)
+            };
             folder.fold_ty(*self)
         }
     }
@@ -48,7 +64,13 @@ impl Subst for ty::t {
 
 struct SubstFolder<'a> {
     tcx: ty::ctxt,
-    substs: &'a ty::substs
+    substs: &'a ty::substs,
+
+    // The location for which the substitution is performed, if available.
+    span: Option<Span>,
+
+    // The root type that is being substituted, if available.
+    root_ty: Option<ty::t>
 }
 
 impl<'a> TypeFolder for SubstFolder<'a> {
@@ -65,14 +87,42 @@ impl<'a> TypeFolder for SubstFolder<'a> {
 
         match ty::get(t).sty {
             ty::ty_param(p) => {
-                self.substs.tps[p.idx]
+                if p.idx < self.substs.tps.len() {
+                    self.substs.tps[p.idx]
+                } else {
+                    let root_msg = match self.root_ty {
+                        Some(root) => format!(" in the substitution of `{}`",
+                                              root.repr(self.tcx)),
+                        None => ~""
+                    };
+                    let m = format!("missing type param `{}`{}",
+                                    t.repr(self.tcx), root_msg);
+                    match self.span {
+                        Some(span) => self.tcx.sess.span_err(span, m),
+                        None => self.tcx.sess.err(m)
+                    }
+                    ty::mk_err()
+                }
             }
             ty::ty_self(_) => {
-                self.substs.self_ty.expect("ty_self not found in substs")
-            }
-            _ => {
-                ty_fold::super_fold_ty(self, t)
+                match self.substs.self_ty {
+                    Some(ty) => ty,
+                    None => {
+                        let root_msg = match self.root_ty {
+                            Some(root) => format!(" in the substitution of `{}`",
+                                                  root.repr(self.tcx)),
+                            None => ~""
+                        };
+                        let m = format!("missing `Self` type param{}", root_msg);
+                        match self.span {
+                            Some(span) => self.tcx.sess.span_err(span, m),
+                            None => self.tcx.sess.err(m)
+                        }
+                        ty::mk_err()
+                    }
+                }
             }
+            _ => ty_fold::super_fold_ty(self, t)
         }
     }
 }
@@ -81,112 +131,145 @@ impl<'a> TypeFolder for SubstFolder<'a> {
 // Other types
 
 impl<T:Subst> Subst for ~[T] {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ~[T] {
-        self.map(|t| t.subst(tcx, substs))
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ~[T] {
+        self.map(|t| t.subst_spanned(tcx, substs, span))
     }
 }
 impl<T:Subst> Subst for Rc<T> {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> Rc<T> {
-        Rc::new(self.borrow().subst(tcx, substs))
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> Rc<T> {
+        Rc::new(self.borrow().subst_spanned(tcx, substs, span))
     }
 }
 
 impl<T:Subst> Subst for OptVec<T> {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> OptVec<T> {
-        self.map(|t| t.subst(tcx, substs))
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> OptVec<T> {
+        self.map(|t| t.subst_spanned(tcx, substs, span))
     }
 }
 
 impl<T:Subst + 'static> Subst for @T {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> @T {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> @T {
         match self {
-            t => @(**t).subst(tcx, substs)
+            t => @(**t).subst_spanned(tcx, substs, span)
         }
     }
 }
 
 impl<T:Subst> Subst for Option<T> {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> Option<T> {
-        self.as_ref().map(|t| t.subst(tcx, substs))
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> Option<T> {
+        self.as_ref().map(|t| t.subst_spanned(tcx, substs, span))
     }
 }
 
 impl Subst for ty::TraitRef {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::TraitRef {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::TraitRef {
         ty::TraitRef {
             def_id: self.def_id,
-            substs: self.substs.subst(tcx, substs)
+            substs: self.substs.subst_spanned(tcx, substs, span)
         }
     }
 }
 
 impl Subst for ty::substs {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::substs {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::substs {
         ty::substs {
-            regions: self.regions.subst(tcx, substs),
-            self_ty: self.self_ty.map(|typ| typ.subst(tcx, substs)),
-            tps: self.tps.map(|typ| typ.subst(tcx, substs))
+            regions: self.regions.subst_spanned(tcx, substs, span),
+            self_ty: self.self_ty.map(|typ| typ.subst_spanned(tcx, substs, span)),
+            tps: self.tps.map(|typ| typ.subst_spanned(tcx, substs, span))
         }
     }
 }
 
 impl Subst for ty::RegionSubsts {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::RegionSubsts {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::RegionSubsts {
         match *self {
             ty::ErasedRegions => {
                 ty::ErasedRegions
             }
             ty::NonerasedRegions(ref regions) => {
-                ty::NonerasedRegions(regions.subst(tcx, substs))
+                ty::NonerasedRegions(regions.subst_spanned(tcx, substs, span))
             }
         }
     }
 }
 
 impl Subst for ty::BareFnTy {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::BareFnTy {
-        let mut folder = SubstFolder {tcx: tcx, substs: substs};
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::BareFnTy {
+        let mut folder = SubstFolder {
+            tcx: tcx,
+            substs: substs,
+            span: span,
+            root_ty: None
+        };
         folder.fold_bare_fn_ty(self)
     }
 }
 
 impl Subst for ty::ParamBounds {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::ParamBounds {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::ParamBounds {
         ty::ParamBounds {
             builtin_bounds: self.builtin_bounds,
-            trait_bounds: self.trait_bounds.subst(tcx, substs)
+            trait_bounds: self.trait_bounds.subst_spanned(tcx, substs, span)
         }
     }
 }
 
 impl Subst for ty::TypeParameterDef {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::TypeParameterDef {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::TypeParameterDef {
         ty::TypeParameterDef {
             ident: self.ident,
             def_id: self.def_id,
-            bounds: self.bounds.subst(tcx, substs),
-            default: self.default.map(|x| x.subst(tcx, substs))
+            bounds: self.bounds.subst_spanned(tcx, substs, span),
+            default: self.default.map(|x| x.subst_spanned(tcx, substs, span))
         }
     }
 }
 
 impl Subst for ty::Generics {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::Generics {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::Generics {
         ty::Generics {
-            type_param_defs: self.type_param_defs.subst(tcx, substs),
-            region_param_defs: self.region_param_defs.subst(tcx, substs),
+            type_param_defs: self.type_param_defs.subst_spanned(tcx, substs, span),
+            region_param_defs: self.region_param_defs.subst_spanned(tcx, substs, span),
         }
     }
 }
 
 impl Subst for ty::RegionParameterDef {
-    fn subst(&self, _: ty::ctxt, _: &ty::substs) -> ty::RegionParameterDef {
+    fn subst_spanned(&self, _: ty::ctxt,
+                     _: &ty::substs,
+                     _: Option<Span>) -> ty::RegionParameterDef {
         *self
     }
 }
 
 impl Subst for ty::Region {
-    fn subst(&self, _tcx: ty::ctxt, substs: &ty::substs) -> ty::Region {
+    fn subst_spanned(&self, _tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     _: Option<Span>) -> ty::Region {
         // Note: This routine only handles regions that are bound on
         // type declarationss and other outer declarations, not those
         // bound in *fn types*. Region substitution of the bound
@@ -206,10 +289,12 @@ impl Subst for ty::Region {
 }
 
 impl Subst for ty::ty_param_bounds_and_ty {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::ty_param_bounds_and_ty {
+    fn subst_spanned(&self, tcx: ty::ctxt,
+                     substs: &ty::substs,
+                     span: Option<Span>) -> ty::ty_param_bounds_and_ty {
         ty::ty_param_bounds_and_ty {
-            generics: self.generics.subst(tcx, substs),
-            ty: self.ty.subst(tcx, substs)
+            generics: self.generics.subst_spanned(tcx, substs, span),
+            ty: self.ty.subst_spanned(tcx, substs, span)
         }
     }
 }
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 90abdc5ac50..906bb504bb0 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -52,6 +52,7 @@
 
 use middle::const_eval;
 use middle::lint;
+use middle::subst::Subst;
 use middle::ty::{substs};
 use middle::ty::{ty_param_substs_and_ty};
 use middle::ty;
@@ -228,16 +229,23 @@ fn ast_path_substs<AC:AstConv,RS:RegionScope>(
                                  ~"provided type arguments with defaults");
     }
 
-    let defaults = decl_generics.type_param_defs().slice_from(supplied_ty_param_count)
-                                .iter().map(|&x| x.default.unwrap());
     let tps = path.segments.iter().flat_map(|s| s.types.iter())
                             .map(|&a_t| ast_ty_to_ty(this, rscope, a_t))
-                            .chain(defaults).collect();
-    substs {
+                            .collect();
+
+    let mut substs = substs {
         regions: ty::NonerasedRegions(regions),
         self_ty: self_ty,
         tps: tps
+    };
+
+    for param in decl_generics.type_param_defs()
+                              .slice_from(supplied_ty_param_count).iter() {
+        let ty = param.default.unwrap().subst_spanned(tcx, &substs, Some(path.span));
+        substs.tps.push(ty);
     }
+
+    substs
 }
 
 pub fn ast_path_to_substs_and_ty<AC:AstConv,
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 43179aa3c92..74655914a27 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -3744,6 +3744,7 @@ pub fn instantiate_path(fcx: @FnCtxt,
                 infer::BoundRegionInTypeOrImpl(span),
                 num_expected_regions))
     };
+    let regions = ty::NonerasedRegions(regions);
 
     // Special case: If there is a self parameter, omit it from the list of
     // type parameters.
@@ -3762,12 +3763,12 @@ pub fn instantiate_path(fcx: @FnCtxt,
 
     // determine values for type parameters, using the values given by
     // the user (if any) and otherwise using fresh type variables
-    let tps = if ty_substs_len == 0 {
-        fcx.infcx().next_ty_vars(ty_param_count)
+    let (tps, regions) = if ty_substs_len == 0 {
+        (fcx.infcx().next_ty_vars(ty_param_count), regions)
     } else if ty_param_count == 0 {
         fcx.ccx.tcx.sess.span_err
             (span, "this item does not take type parameters");
-        fcx.infcx().next_ty_vars(ty_param_count)
+        (fcx.infcx().next_ty_vars(ty_param_count), regions)
     } else if ty_substs_len > user_ty_param_count {
         let expected = if user_ty_param_req < user_ty_param_count {
             "expected at most"
@@ -3778,7 +3779,7 @@ pub fn instantiate_path(fcx: @FnCtxt,
             (span,
              format!("too many type parameters provided: {} {}, found {}",
                   expected, user_ty_param_count, ty_substs_len));
-        fcx.infcx().next_ty_vars(ty_param_count)
+        (fcx.infcx().next_ty_vars(ty_param_count), regions)
     } else if ty_substs_len < user_ty_param_req {
         let expected = if user_ty_param_req < user_ty_param_count {
             "expected at least"
@@ -3789,7 +3790,7 @@ pub fn instantiate_path(fcx: @FnCtxt,
             (span,
              format!("not enough type parameters provided: {} {}, found {}",
                   expected, user_ty_param_req, ty_substs_len));
-        fcx.infcx().next_ty_vars(ty_param_count)
+        (fcx.infcx().next_ty_vars(ty_param_count), regions)
     } else {
         if ty_substs_len > user_ty_param_req {
             fcx.tcx().sess.add_lint(lint::DefaultTypeParamUsage, node_id, pth.span,
@@ -3798,50 +3799,71 @@ pub fn instantiate_path(fcx: @FnCtxt,
 
         // Build up the list of type parameters, inserting the self parameter
         // at the appropriate position.
-        let mut result = ~[];
+        let mut tps = ~[];
         let mut pushed = false;
+        for (i, ty) in pth.segments.iter()
+                                   .flat_map(|segment| segment.types.iter())
+                                   .map(|&ast_type| fcx.to_ty(ast_type))
+                                   .enumerate() {
+            match self_parameter_index {
+                Some(index) if index == i => {
+                    tps.push(fcx.infcx().next_ty_vars(1)[0]);
+                    pushed = true;
+                }
+                _ => {}
+            }
+            tps.push(ty)
+        }
+
+        let mut substs = substs {
+            regions: regions,
+            self_ty: None,
+            tps: tps
+        };
+
         let defaults = tpt.generics.type_param_defs().iter()
                           .enumerate().filter_map(|(i, x)| {
             match self_parameter_index {
                 Some(index) if index == i => None,
                 _ => Some(x.default)
             }
-        }).skip(ty_substs_len).map(|x| match x {
-            Some(default) => default,
-            None => {
-                fcx.tcx().sess.span_bug(span,
-                    "missing default for a not explicitely provided type param")
-            }
         });
-        for (i, ty) in pth.segments.iter()
-                                   .flat_map(|segment| segment.types.iter())
-                                   .map(|&ast_type| fcx.to_ty(ast_type))
-                                   .chain(defaults).enumerate() {
+        for (i, default) in defaults.skip(ty_substs_len).enumerate() {
             match self_parameter_index {
-                Some(index) if index == i => {
-                    result.push(fcx.infcx().next_ty_vars(1)[0]);
+                Some(index) if index == i + ty_substs_len => {
+                    substs.tps.push(fcx.infcx().next_ty_vars(1)[0]);
                     pushed = true;
                 }
                 _ => {}
             }
-            result.push(ty)
+            match default {
+                Some(default) => {
+                    let ty = default.subst_spanned(fcx.tcx(), &substs, Some(span));
+                    substs.tps.push(ty);
+                }
+                None => {
+                    fcx.tcx().sess.span_bug(span,
+                        "missing default for a not explicitely provided type param")
+                }
+            }
         }
 
         // If the self parameter goes at the end, insert it there.
         if !pushed && self_parameter_index.is_some() {
-            result.push(fcx.infcx().next_ty_vars(1)[0])
+            substs.tps.push(fcx.infcx().next_ty_vars(1)[0])
         }
 
-        assert_eq!(result.len(), ty_param_count)
-        result
+        assert_eq!(substs.tps.len(), ty_param_count)
+
+        let substs {tps, regions, ..} = substs;
+        (tps, regions)
     };
 
-    let substs = substs {
-        regions: ty::NonerasedRegions(regions),
+    fcx.write_ty_substs(node_id, tpt.ty, substs {
+        regions: regions,
         self_ty: None,
         tps: tps
-    };
-    fcx.write_ty_substs(node_id, tpt.ty, substs);
+    });
 
     debug!("<<<");
 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index eba99c7fb5a..334407ff122 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -525,13 +525,25 @@ pub fn parameterized(cx: ctxt,
     } else {
         ty::lookup_item_type(cx, did).generics
     };
-    let ty_params = generics.type_param_defs().iter();
-    let num_defaults = ty_params.zip(tps.iter()).rev().take_while(|&(def, &actual)| {
-        match def.default {
-            Some(default) => default == actual,
-            None => false
-        }
-    }).len();
+    let ty_params = generics.type_param_defs();
+    let has_defaults = ty_params.last().map_or(false, |def| def.default.is_some());
+    let num_defaults = if has_defaults {
+        // We should have a borrowed version of substs instead of cloning.
+        let mut substs = ty::substs {
+            tps: tps.to_owned(),
+            regions: regions.clone(),
+            self_ty: None
+        };
+        ty_params.iter().zip(tps.iter()).rev().take_while(|&(def, &actual)| {
+            substs.tps.pop();
+            match def.default {
+                Some(default) => ty::subst(cx, &substs, default) == actual,
+                None => false
+            }
+        }).len()
+    } else {
+        0
+    };
 
     for t in tps.slice_to(tps.len() - num_defaults).iter() {
         strs.push(ty_to_str(cx, *t))
diff --git a/src/test/compile-fail/generic-type-params-forward-mention.rs b/src/test/compile-fail/generic-type-params-forward-mention.rs
new file mode 100644
index 00000000000..003ffdc8cc0
--- /dev/null
+++ b/src/test/compile-fail/generic-type-params-forward-mention.rs
@@ -0,0 +1,19 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#[feature(default_type_params)];
+
+// Ensure that we get an error and not an ICE for this problematic case.
+struct Foo<T = Option<U>, U = bool>;
+
+fn main() {
+    let x: Foo;
+    //~^ ERROR missing type param `U` in the substitution of `std::option::Option<U>`
+}
diff --git a/src/test/compile-fail/generic-type-params-name-repr.rs b/src/test/compile-fail/generic-type-params-name-repr.rs
index 59e6ba87ecb..066bbc38e1a 100644
--- a/src/test/compile-fail/generic-type-params-name-repr.rs
+++ b/src/test/compile-fail/generic-type-params-name-repr.rs
@@ -15,6 +15,9 @@ struct B;
 struct C;
 struct Foo<T = A, U = B, V = C>;
 
+struct Hash<T>;
+struct HashMap<K, V, H = Hash<K>>;
+
 fn main() {
     // Ensure that the printed type doesn't include the default type params...
     let _: Foo<int> = ();
@@ -24,6 +27,12 @@ fn main() {
     let _: Foo<int, B, C> = ();
     //~^ ERROR mismatched types: expected `Foo<int>` but found `()`
 
+    // Including cases where the default is using previous type params.
+    let _: HashMap<~str, int> = ();
+    //~^ ERROR mismatched types: expected `HashMap<~str,int>` but found `()`
+    let _: HashMap<~str, int, Hash<~str>> = ();
+    //~^ ERROR mismatched types: expected `HashMap<~str,int>` but found `()`
+
     // But not when there's a different type in between.
     let _: Foo<A, int, C> = ();
     //~^ ERROR mismatched types: expected `Foo<A,int>` but found `()`
diff --git a/src/test/run-pass/generic-default-type-params.rs b/src/test/run-pass/generic-default-type-params.rs
index bb5a923ce9e..1521710072d 100644
--- a/src/test/run-pass/generic-default-type-params.rs
+++ b/src/test/run-pass/generic-default-type-params.rs
@@ -52,6 +52,16 @@ fn default_foo(x: Foo) {
     assert_eq!(x.baz(), (1, 'a'));
 }
 
+#[deriving(Eq)]
+struct BazHelper<T>(T);
+
+#[deriving(Eq)]
+// Ensure that we can use previous type parameters in defaults.
+struct Baz<T, U = BazHelper<T>, V = Option<U>>(T, U, V);
+
 fn main() {
     default_foo(Foo { a: (1, 'a') });
+
+    let x: Baz<bool> = Baz(true, BazHelper(false), Some(BazHelper(true)));
+    assert_eq!(x, Baz(true, BazHelper(false), Some(BazHelper(true))));
 }