auto merge of #6336 : nikomatsakis/rust/issue-6308-closure-bounds, r=nikomatsakis

Use a bitset to represent built-in bounds. There are several places in the language where only builtin bounds (aka kinds) will be accepted, e.g. on closures, destructor type parameters perhaps, and on trait types.

r? @brson

14 files changed, 515 insertions, 213 deletions

diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 02acafbd980..c220ae45b1a 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -555,18 +555,34 @@ fn parse_type_param_def(st: @mut PState, conv: conv_did) -> ty::TypeParameterDef
                           bounds: parse_bounds(st, conv)}
 }
 
-fn parse_bounds(st: @mut PState, conv: conv_did) -> @~[ty::param_bound] {
-    let mut bounds = ~[];
+fn parse_bounds(st: @mut PState, conv: conv_did) -> @ty::ParamBounds {
+    let mut param_bounds = ty::ParamBounds {
+        builtin_bounds: ty::EmptyBuiltinBounds(),
+        trait_bounds: ~[]
+    };
     loop {
-        bounds.push(match next(st) {
-          'S' => ty::bound_owned,
-          'C' => ty::bound_copy,
-          'K' => ty::bound_const,
-          'O' => ty::bound_durable,
-          'I' => ty::bound_trait(@parse_trait_ref(st, conv)),
-          '.' => break,
-          _ => fail!(~"parse_bounds: bad bounds")
-        });
+        match next(st) {
+            'S' => {
+                param_bounds.builtin_bounds.add(ty::BoundOwned);
+            }
+            'C' => {
+                param_bounds.builtin_bounds.add(ty::BoundCopy);
+            }
+            'K' => {
+                param_bounds.builtin_bounds.add(ty::BoundConst);
+            }
+            'O' => {
+                param_bounds.builtin_bounds.add(ty::BoundStatic);
+            }
+            'I' => {
+                param_bounds.trait_bounds.push(@parse_trait_ref(st, conv));
+            }
+            '.' => {
+                return @param_bounds;
+            }
+            _ => {
+                fail!(~"parse_bounds: bad bounds")
+            }
+        }
     }
-    @bounds
 }
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 3abe5b22e1a..86088646bca 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -396,19 +396,21 @@ fn enc_fn_sig(w: @io::Writer, cx: @ctxt, fsig: &ty::FnSig) {
     enc_ty(w, cx, fsig.output);
 }
 
-fn enc_bounds(w: @io::Writer, cx: @ctxt, bs: @~[ty::param_bound]) {
-    for (*bs).each |bound| {
-        match *bound {
-          ty::bound_owned => w.write_char('S'),
-          ty::bound_copy => w.write_char('C'),
-          ty::bound_const => w.write_char('K'),
-          ty::bound_durable => w.write_char('O'),
-          ty::bound_trait(tp) => {
-              w.write_char('I');
-              enc_trait_ref(w, cx, tp);
-          }
+fn enc_bounds(w: @io::Writer, cx: @ctxt, bs: @ty::ParamBounds) {
+    for bs.builtin_bounds.each |bound| {
+        match bound {
+            ty::BoundOwned => w.write_char('S'),
+            ty::BoundCopy => w.write_char('C'),
+            ty::BoundConst => w.write_char('K'),
+            ty::BoundStatic => w.write_char('O'),
         }
     }
+
+    for bs.trait_bounds.each |&tp| {
+        w.write_char('I');
+        enc_trait_ref(w, cx, tp);
+    }
+
     w.write_char('.');
 }
 
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
index 0050e0f81c7..f8f6dbd8259 100644
--- a/src/librustc/middle/kind.rs
+++ b/src/librustc/middle/kind.rs
@@ -14,6 +14,7 @@ use middle::pat_util;
 use middle::ty;
 use middle::typeck;
 use util::ppaux::{Repr, ty_to_str};
+use util::ppaux::UserString;
 
 use syntax::ast::*;
 use syntax::attr::attrs_contains_name;
@@ -338,46 +339,19 @@ pub fn check_bounds(cx: Context,
                     type_param_def: &ty::TypeParameterDef)
 {
     let kind = ty::type_contents(cx.tcx, ty);
-    let mut missing = ~[];
-    for type_param_def.bounds.each |bound| {
-        match *bound {
-            ty::bound_trait(_) => {
-                /* Not our job, checking in typeck */
-            }
-
-            ty::bound_copy => {
-                if !kind.is_copy(cx.tcx) {
-                    missing.push("Copy");
-                }
-            }
-
-            ty::bound_durable => {
-                if !kind.is_durable(cx.tcx) {
-                    missing.push("'static");
-                }
-            }
-
-            ty::bound_owned => {
-                if !kind.is_owned(cx.tcx) {
-                    missing.push("Owned");
-                }
-            }
-
-            ty::bound_const => {
-                if !kind.is_const(cx.tcx) {
-                    missing.push("Const");
-                }
-            }
+    let mut missing = ty::EmptyBuiltinBounds();
+    for type_param_def.bounds.builtin_bounds.each |bound| {
+        if !kind.meets_bound(cx.tcx, bound) {
+            missing.add(bound);
         }
     }
-
     if !missing.is_empty() {
         cx.tcx.sess.span_err(
             sp,
             fmt!("instantiating a type parameter with an incompatible type \
                   `%s`, which does not fulfill `%s`",
                  ty_to_str(cx.tcx, ty),
-                 str::connect_slices(missing, " ")));
+                 missing.user_string(cx.tcx)));
     }
 }
 
@@ -440,7 +414,7 @@ pub fn check_owned(cx: Context, ty: ty::t, sp: span) -> bool {
 
 // note: also used from middle::typeck::regionck!
 pub fn check_durable(tcx: ty::ctxt, ty: ty::t, sp: span) -> bool {
-    if !ty::type_is_durable(tcx, ty) {
+    if !ty::type_is_static(tcx, ty) {
         match ty::get(ty).sty {
           ty::ty_param(*) => {
             tcx.sess.span_err(sp, "value may contain borrowed \
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index bf64134704a..5c7c33d35b2 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -78,9 +78,11 @@ impl<T:Subst> Subst for ~[T] {
     }
 }
 
-impl<T:Subst> Subst for @~[T] {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> @~[T] {
-        @(**self).subst(tcx, substs)
+impl<T:Subst> Subst for @T {
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> @T {
+        match self {
+            &@ref t => @t.subst(tcx, substs)
+        }
     }
 }
 
@@ -115,19 +117,11 @@ impl Subst for ty::BareFnTy {
     }
 }
 
-impl Subst for ty::param_bound {
-    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::param_bound {
-        match self {
-            &ty::bound_copy |
-            &ty::bound_durable |
-            &ty::bound_owned |
-            &ty::bound_const => {
-                *self
-            }
-
-            &ty::bound_trait(tref) => {
-                ty::bound_trait(@tref.subst(tcx, substs))
-            }
+impl Subst for ty::ParamBounds {
+    fn subst(&self, tcx: ty::ctxt, substs: &ty::substs) -> ty::ParamBounds {
+        ty::ParamBounds {
+            builtin_bounds: self.builtin_bounds,
+            trait_bounds: self.trait_bounds.subst(tcx, substs)
         }
     }
 }
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index 6e250641869..905e5ed912c 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -348,14 +348,9 @@ pub fn make_mono_id(ccx: @CrateContext,
         let mut i = 0;
         vec::map_zip(*item_ty.generics.type_param_defs, substs, |type_param_def, subst| {
             let mut v = ~[];
-            for type_param_def.bounds.each |bound| {
-                match *bound {
-                  ty::bound_trait(_) => {
-                    v.push(meth::vtable_id(ccx, /*bad*/copy vts[i]));
-                    i += 1;
-                  }
-                  _ => ()
-                }
+            for type_param_def.bounds.trait_bounds.each |_bound| {
+                v.push(meth::vtable_id(ccx, /*bad*/copy vts[i]));
+                i += 1;
             }
             (*subst, if !v.is_empty() { Some(v) } else { None })
         })
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 2daba3212e1..c31843870e8 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -26,6 +26,7 @@ use util::ppaux::{note_and_explain_region, bound_region_to_str};
 use util::ppaux::{trait_store_to_str, ty_to_str, vstore_to_str};
 use util::ppaux::Repr;
 use util::common::{indenter};
+use util::enum_set::{EnumSet, CLike};
 
 use core;
 use core::ptr::to_unsafe_ptr;
@@ -58,8 +59,6 @@ pub struct field {
     mt: mt
 }
 
-pub type param_bounds = @~[param_bound];
-
 pub struct method {
     ident: ast::ident,
     generics: ty::Generics,
@@ -655,12 +654,32 @@ pub enum type_err {
 }
 
 #[deriving(Eq, IterBytes)]
-pub enum param_bound {
-    bound_copy,
-    bound_durable,
-    bound_owned,
-    bound_const,
-    bound_trait(@TraitRef),
+pub struct ParamBounds {
+    builtin_bounds: BuiltinBounds,
+    trait_bounds: ~[@TraitRef]
+}
+
+pub type BuiltinBounds = EnumSet<BuiltinBound>;
+
+#[deriving(Eq, IterBytes)]
+pub enum BuiltinBound {
+    BoundCopy,
+    BoundStatic,
+    BoundOwned,
+    BoundConst,
+}
+
+pub fn EmptyBuiltinBounds() -> BuiltinBounds {
+    EnumSet::empty()
+}
+
+impl CLike for BuiltinBound {
+    pub fn to_uint(&self) -> uint {
+        *self as uint
+    }
+    pub fn from_uint(v: uint) -> BuiltinBound {
+        unsafe { cast::transmute(v) }
+    }
 }
 
 #[deriving(Eq)]
@@ -817,7 +836,7 @@ impl to_bytes::IterBytes for RegionVid {
 
 pub struct TypeParameterDef {
     def_id: ast::def_id,
-    bounds: param_bounds
+    bounds: @ParamBounds
 }
 
 /// Information about the type/lifetime parametesr associated with an item.
@@ -1497,14 +1516,6 @@ pub fn substs_to_str(cx: ctxt, substs: &substs) -> ~str {
     substs.repr(cx)
 }
 
-pub fn param_bound_to_str(cx: ctxt, pb: &param_bound) -> ~str {
-    pb.repr(cx)
-}
-
-pub fn param_bounds_to_str(cx: ctxt, pbs: param_bounds) -> ~str {
-    pbs.repr(cx)
-}
-
 pub fn subst(cx: ctxt,
              substs: &substs,
              typ: t)
@@ -1795,6 +1806,19 @@ pub struct TypeContents {
 }
 
 pub impl TypeContents {
+    fn meets_bounds(&self, cx: ctxt, bbs: BuiltinBounds) -> bool {
+        iter::all(|bb| self.meets_bound(cx, bb), |f| bbs.each(f))
+    }
+
+    fn meets_bound(&self, cx: ctxt, bb: BuiltinBound) -> bool {
+        match bb {
+            BoundCopy => self.is_copy(cx),
+            BoundStatic => self.is_static(cx),
+            BoundConst => self.is_const(cx),
+            BoundOwned => self.is_owned(cx)
+        }
+    }
+
     fn intersects(&self, tc: TypeContents) -> bool {
         (self.bits & tc.bits) != 0
     }
@@ -1808,11 +1832,11 @@ pub impl TypeContents {
             TC_EMPTY_ENUM
     }
 
-    fn is_durable(&self, cx: ctxt) -> bool {
-        !self.intersects(TypeContents::nondurable(cx))
+    fn is_static(&self, cx: ctxt) -> bool {
+        !self.intersects(TypeContents::nonstatic(cx))
     }
 
-    fn nondurable(_cx: ctxt) -> TypeContents {
+    fn nonstatic(_cx: ctxt) -> TypeContents {
         TC_BORROWED_POINTER
     }
 
@@ -1917,8 +1941,8 @@ pub fn type_is_copyable(cx: ctxt, t: ty::t) -> bool {
     type_contents(cx, t).is_copy(cx)
 }
 
-pub fn type_is_durable(cx: ctxt, t: ty::t) -> bool {
-    type_contents(cx, t).is_durable(cx)
+pub fn type_is_static(cx: ctxt, t: ty::t) -> bool {
+    type_contents(cx, t).is_static(cx)
 }
 
 pub fn type_is_owned(cx: ctxt, t: ty::t) -> bool {
@@ -2198,19 +2222,19 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
         debug!("type_param_def_to_contents(%s)", type_param_def.repr(cx));
         let _i = indenter();
 
-        let r = type_param_def.bounds.foldl(TC_ALL, |tc, bound| {
+        let mut tc = TC_ALL;
+        for type_param_def.bounds.builtin_bounds.each |bound| {
             debug!("tc = %s, bound = %?", tc.to_str(), bound);
-            match *bound {
-                bound_copy => tc - TypeContents::nonimplicitly_copyable(cx),
-                bound_durable => tc - TypeContents::nondurable(cx),
-                bound_owned => tc - TypeContents::nonowned(cx),
-                bound_const => tc - TypeContents::nonconst(cx),
-                bound_trait(_) => *tc
-            }
-        });
+            tc = tc - match bound {
+                BoundCopy => TypeContents::nonimplicitly_copyable(cx),
+                BoundStatic => TypeContents::nonstatic(cx),
+                BoundOwned => TypeContents::nonowned(cx),
+                BoundConst => TypeContents::nonconst(cx),
+            };
+        }
 
-        debug!("result = %s", r.to_str());
-        return r;
+        debug!("result = %s", tc.to_str());
+        return tc;
     }
 }
 
@@ -3577,7 +3601,7 @@ pub fn trait_supertraits(cx: ctxt,
 pub fn trait_ref_supertraits(cx: ctxt, trait_ref: &ty::TraitRef) -> ~[@TraitRef] {
     let supertrait_refs = trait_supertraits(cx, trait_ref.def_id);
     supertrait_refs.map(
-        |supertrait_ref| @supertrait_ref.subst(cx, &trait_ref.substs))
+        |supertrait_ref| supertrait_ref.subst(cx, &trait_ref.substs))
 }
 
 fn lookup_locally_or_in_crate_store<V:Copy>(
@@ -4261,18 +4285,9 @@ pub fn determine_inherited_purity(parent: (ast::purity, ast::node_id),
 // relation on the supertraits from each bounded trait's constraint
 // list.
 pub fn each_bound_trait_and_supertraits(tcx: ctxt,
-                                         bounds: param_bounds,
-                                         f: &fn(&TraitRef) -> bool) {
-    for bounds.each |bound| {
-        let bound_trait_ref = match *bound {
-            ty::bound_trait(bound_t) => bound_t,
-
-            ty::bound_copy | ty::bound_owned |
-            ty::bound_const | ty::bound_durable => {
-                loop; // skip non-trait bounds
-            }
-        };
-
+                                        bounds: &ParamBounds,
+                                        f: &fn(@TraitRef) -> bool) {
+    for bounds.trait_bounds.each |&bound_trait_ref| {
         let mut supertrait_set = HashMap::new();
         let mut trait_refs = ~[];
         let mut i = 0;
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index a744751ea91..12777159821 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -67,8 +67,7 @@ pub impl VtableContext {
 
 fn has_trait_bounds(type_param_defs: &[ty::TypeParameterDef]) -> bool {
     type_param_defs.any(
-        |type_param_def| type_param_def.bounds.any(
-            |bound| match bound { &ty::bound_trait(*) => true, _ => false }))
+        |type_param_def| !type_param_def.bounds.trait_bounds.is_empty())
 }
 
 fn lookup_vtables(vcx: &VtableContext,
@@ -99,7 +98,7 @@ fn lookup_vtables(vcx: &VtableContext,
 
             // Substitute the values of the type parameters that may
             // appear in the bound.
-            let trait_ref = trait_ref.subst(tcx, substs);
+            let trait_ref = (*trait_ref).subst(tcx, substs);
 
             debug!("after subst: %s", trait_ref.repr(tcx));
 
@@ -339,7 +338,8 @@ fn lookup_vtable(vcx: &VtableContext,
                                    vcx.infcx.trait_ref_to_str(trait_ref),
                                    vcx.infcx.trait_ref_to_str(of_trait_ref));
 
-                            let of_trait_ref = of_trait_ref.subst(tcx, &substs);
+                            let of_trait_ref =
+                                (*of_trait_ref).subst(tcx, &substs);
                             relate_trait_refs(
                                 vcx, location_info,
                                 &of_trait_ref, trait_ref);
@@ -458,7 +458,7 @@ fn connect_trait_tps(vcx: &VtableContext,
 
     // XXX: This should work for multiple traits.
     let impl_trait_ref = ty::impl_trait_refs(tcx, impl_did)[0];
-    let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
+    let impl_trait_ref = (*impl_trait_ref).subst(tcx, impl_substs);
     relate_trait_refs(vcx, location_info, &impl_trait_ref, trait_ref);
 }
 
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 82ef09a83be..6a83db6baee 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -22,7 +22,7 @@ use metadata::csearch;
 use metadata::cstore::{CStore, iter_crate_data};
 use metadata::decoder::{dl_def, dl_field, dl_impl};
 use middle::resolve::{Impl, MethodInfo};
-use middle::ty::{ProvidedMethodSource, ProvidedMethodInfo, bound_copy, get};
+use middle::ty::{ProvidedMethodSource, ProvidedMethodInfo, get};
 use middle::ty::{lookup_item_type, subst};
 use middle::ty::{substs, t, ty_bool, ty_bot, ty_box, ty_enum, ty_err};
 use middle::ty::{ty_estr, ty_evec, ty_float, ty_infer, ty_int, ty_nil};
@@ -603,34 +603,28 @@ pub impl CoherenceChecker {
                 // Check to ensure that each parameter binding respected its
                 // kind bounds.
                 for [ a, b ].each |result| {
-                    for vec::each2(result.type_variables, *result.type_param_defs)
-                            |ty_var, type_param_def| {
-                        match resolve_type(self.inference_context,
-                                           *ty_var,
-                                           resolve_nested_tvar) {
-                            Ok(resolved_ty) => {
-                                for type_param_def.bounds.each |bound| {
-                                    match *bound {
-                                        bound_copy => {
-                                            if !ty::type_is_copyable(
-                                                self.inference_context.tcx,
-                                                resolved_ty)
-                                            {
-                                                might_unify = false;
-                                                break;
-                                            }
-                                        }
-
-                                        // XXX: We could be smarter here.
-                                        // Check to see whether owned, send,
-                                        // const, trait param bounds could
-                                        // possibly unify.
-                                        _ => {}
+                    for vec::each2(result.type_variables,
+                                   *result.type_param_defs)
+                        |ty_var, type_param_def|
+                    {
+                        if type_param_def.bounds.builtin_bounds.contains_elem(
+                            ty::BoundCopy)
+                        {
+                            match resolve_type(self.inference_context,
+                                               *ty_var,
+                                               resolve_nested_tvar) {
+                                Ok(resolved_ty) => {
+                                    if !ty::type_is_copyable(
+                                        self.inference_context.tcx,
+                                        resolved_ty)
+                                    {
+                                        might_unify = false;
+                                        break;
                                     }
                                 }
-                            }
-                            Err(*) => {
-                                // Conservatively assume it might unify.
+                                Err(*) => {
+                                    // Conservatively assume it might unify.
+                                }
                             }
                         }
                     }
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index 33153bde5ac..6de87762031 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -41,8 +41,9 @@ use middle::typeck::infer;
 use middle::typeck::rscope::*;
 use middle::typeck::rscope;
 use middle::typeck::{CrateCtxt, lookup_def_tcx, no_params, write_ty_to_tcx};
-use util::common::{indenter, pluralize};
+use util::common::pluralize;
 use util::ppaux;
+use util::ppaux::UserString;
 
 use syntax::abi::AbiSet;
 use syntax::ast::{RegionTyParamBound, TraitTyParamBound};
@@ -341,10 +342,13 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
 
         // add in the "self" type parameter
         let self_trait_def = get_trait_def(ccx, local_def(trait_id));
-        let self_trait_ref = @self_trait_def.trait_ref.subst(tcx, &substs);
+        let self_trait_ref = self_trait_def.trait_ref.subst(tcx, &substs);
         new_type_param_defs.push(ty::TypeParameterDef {
             def_id: dummy_defid,
-            bounds: @~[ty::bound_trait(self_trait_ref)]
+            bounds: @ty::ParamBounds {
+                builtin_bounds: ty::EmptyBuiltinBounds(),
+                trait_bounds: ~[self_trait_ref]
+            }
         });
 
         // add in the type parameters from the method
@@ -444,7 +448,7 @@ pub fn compare_impl_method(tcx: ty::ctxt,
                            trait_substs: &ty::substs,
                            self_ty: ty::t) {
     debug!("compare_impl_method()");
-    let _indenter = indenter();
+    let infcx = infer::new_infer_ctxt(tcx);
 
     let impl_m = &cm.mty;
 
@@ -507,28 +511,50 @@ pub fn compare_impl_method(tcx: ty::ctxt,
         return;
     }
 
-    // FIXME(#2687)---we should be checking that the bounds of the
-    // trait imply the bounds of the subtype, but it appears
-    // we are...not checking this.
     for trait_m.generics.type_param_defs.eachi |i, trait_param_def| {
         // For each of the corresponding impl ty param's bounds...
         let impl_param_def = &impl_m.generics.type_param_defs[i];
-        // Make sure the bounds lists have the same length
-        // Would be nice to use the ty param names in the error message,
-        // but we don't have easy access to them here
-        if impl_param_def.bounds.len() != trait_param_def.bounds.len() {
+
+        // Check that the impl does not require any builtin-bounds
+        // that the trait does not guarantee:
+        let extra_bounds =
+            impl_param_def.bounds.builtin_bounds -
+            trait_param_def.bounds.builtin_bounds;
+        if !extra_bounds.is_empty() {
            tcx.sess.span_err(
                cm.span,
                fmt!("in method `%s`, \
-                     type parameter %u has %u %s, but the same type \
-                     parameter in its trait declaration has %u %s",
+                     type parameter %u requires `%s`, \
+                     which is not required by \
+                     the corresponding type parameter \
+                     in the trait declaration",
                     *tcx.sess.str_of(trait_m.ident),
-                    i, impl_param_def.bounds.len(),
-                    pluralize(impl_param_def.bounds.len(), ~"bound"),
-                    trait_param_def.bounds.len(),
-                    pluralize(trait_param_def.bounds.len(), ~"bound")));
+                    i,
+                    extra_bounds.user_string(tcx)));
            return;
         }
+
+        // FIXME(#2687)---we should be checking that the bounds of the
+        // trait imply the bounds of the subtype, but it appears we
+        // are...not checking this.
+        if impl_param_def.bounds.trait_bounds.len() !=
+            trait_param_def.bounds.trait_bounds.len()
+        {
+            tcx.sess.span_err(
+                cm.span,
+                fmt!("in method `%s`, \
+                      type parameter %u has %u trait %s, but the \
+                      corresponding type parameter in \
+                      the trait declaration has %u trait %s",
+                     *tcx.sess.str_of(trait_m.ident),
+                     i, impl_param_def.bounds.trait_bounds.len(),
+                     pluralize(impl_param_def.bounds.trait_bounds.len(),
+                               ~"bound"),
+                     trait_param_def.bounds.trait_bounds.len(),
+                     pluralize(trait_param_def.bounds.trait_bounds.len(),
+                               ~"bound")));
+            return;
+        }
     }
 
     // Replace any references to the self region in the self type with
@@ -619,7 +645,6 @@ pub fn compare_impl_method(tcx: ty::ctxt,
     };
     debug!("trait_fty (post-subst): %s", trait_fty.repr(tcx));
 
-    let infcx = infer::new_infer_ctxt(tcx);
     match infer::mk_subty(infcx, false, cm.span, impl_fty, trait_fty) {
         result::Ok(()) => {}
         result::Err(ref terr) => {
@@ -1152,8 +1177,8 @@ pub fn ty_generics(ccx: &CrateCtxt,
                 None => {
                     let param_ty = ty::param_ty {idx: base_index + offset,
                                                  def_id: local_def(param.id)};
-                    let bounds = compute_bounds(ccx, rp, generics,
-                                                param_ty, param.bounds);
+                    let bounds = @compute_bounds(ccx, rp, generics,
+                                                 param_ty, param.bounds);
                     let def = ty::TypeParameterDef {
                         def_id: local_def(param.id),
                         bounds: bounds
@@ -1171,7 +1196,7 @@ pub fn ty_generics(ccx: &CrateCtxt,
         rp: Option<ty::region_variance>,
         generics: &ast::Generics,
         param_ty: ty::param_ty,
-        ast_bounds: @OptVec<ast::TyParamBound>) -> ty::param_bounds
+        ast_bounds: @OptVec<ast::TyParamBound>) -> ty::ParamBounds
     {
         /*!
          *
@@ -1182,29 +1207,35 @@ pub fn ty_generics(ccx: &CrateCtxt,
          * as kinds): Const, Copy, and Send.
          */
 
-        @ast_bounds.flat_map_to_vec(|b| {
+        let mut param_bounds = ty::ParamBounds {
+            builtin_bounds: ty::EmptyBuiltinBounds(),
+            trait_bounds: ~[]
+        };
+        for ast_bounds.each |b| {
             match b {
                 &TraitTyParamBound(b) => {
                     let li = &ccx.tcx.lang_items;
                     let ty = ty::mk_param(ccx.tcx, param_ty.idx, param_ty.def_id);
                     let trait_ref = instantiate_trait_ref(ccx, b, rp, generics, ty);
                     if trait_ref.def_id == li.owned_trait() {
-                        ~[ty::bound_owned]
+                        param_bounds.builtin_bounds.add(ty::BoundOwned);
                     } else if trait_ref.def_id == li.copy_trait() {
-                        ~[ty::bound_copy]
+                        param_bounds.builtin_bounds.add(ty::BoundCopy);
                     } else if trait_ref.def_id == li.const_trait() {
-                        ~[ty::bound_const]
+                        param_bounds.builtin_bounds.add(ty::BoundConst);
                     } else {
                         // Must be a user-defined trait
-                        ~[ty::bound_trait(trait_ref)]
+                        param_bounds.trait_bounds.push(trait_ref);
                     }
                 }
 
                 &RegionTyParamBound => {
-                    ~[ty::bound_durable]
+                    param_bounds.builtin_bounds.add(ty::BoundStatic);
                 }
             }
-        })
+        }
+
+        param_bounds
     }
 }
 
diff --git a/src/librustc/rustc.rc b/src/librustc/rustc.rc
index f69a38c96dc..6027a044541 100644
--- a/src/librustc/rustc.rc
+++ b/src/librustc/rustc.rc
@@ -131,6 +131,7 @@ pub mod driver;
 pub mod util {
     pub mod common;
     pub mod ppaux;
+    pub mod enum_set;
 }
 
 pub mod lib {
diff --git a/src/librustc/util/enum_set.rs b/src/librustc/util/enum_set.rs
new file mode 100644
index 00000000000..859e743b43b
--- /dev/null
+++ b/src/librustc/util/enum_set.rs
@@ -0,0 +1,233 @@
+// Copyright 2012 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.
+
+use core;
+
+#[deriving(Eq, IterBytes)]
+pub struct EnumSet<E> {
+    bits: uint
+}
+
+pub trait CLike {
+    pub fn to_uint(&self) -> uint;
+    pub fn from_uint(uint) -> Self;
+}
+
+fn bit<E:CLike>(e: E) -> uint {
+    1 << e.to_uint()
+}
+
+pub impl<E:CLike> EnumSet<E> {
+    fn empty() -> EnumSet<E> {
+        EnumSet {bits: 0}
+    }
+
+    fn is_empty(&self) -> bool {
+        self.bits == 0
+    }
+
+    fn intersects(&self, e: EnumSet<E>) -> bool {
+        (self.bits & e.bits) != 0
+    }
+
+    fn contains(&self, e: EnumSet<E>) -> bool {
+        (self.bits & e.bits) == e.bits
+    }
+
+    fn add(&mut self, e: E) {
+        self.bits |= bit(e);
+    }
+
+    fn contains_elem(&self, e: E) -> bool {
+        (self.bits & bit(e)) != 0
+    }
+
+    fn each(&self, f: &fn(E) -> bool) {
+        let mut bits = self.bits;
+        let mut index = 0;
+        while bits != 0 {
+            if (bits & 1) != 0 {
+                let e = CLike::from_uint(index);
+                if !f(e) {
+                    return;
+                }
+            }
+            index += 1;
+            bits >>= 1;
+        }
+    }
+}
+
+impl<E:CLike> core::Sub<EnumSet<E>, EnumSet<E>> for EnumSet<E> {
+    fn sub(&self, e: &EnumSet<E>) -> EnumSet<E> {
+        EnumSet {bits: self.bits & !e.bits}
+    }
+}
+
+impl<E:CLike> core::BitOr<EnumSet<E>, EnumSet<E>> for EnumSet<E> {
+    fn bitor(&self, e: &EnumSet<E>) -> EnumSet<E> {
+        EnumSet {bits: self.bits | e.bits}
+    }
+}
+
+impl<E:CLike> core::BitAnd<EnumSet<E>, EnumSet<E>> for EnumSet<E> {
+    fn bitand(&self, e: &EnumSet<E>) -> EnumSet<E> {
+        EnumSet {bits: self.bits & e.bits}
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use core;
+    use core::iter;
+    use util::enum_set::*;
+
+    #[deriving(Eq)]
+    enum Foo {
+        A, B, C
+    }
+
+    impl CLike for Foo {
+        pub fn to_uint(&self) -> uint {
+            *self as uint
+        }
+
+        pub fn from_uint(v: uint) -> Foo {
+            unsafe { cast::transmute(v) }
+        }
+    }
+
+    #[test]
+    fn test_empty() {
+        let e: EnumSet<Foo> = EnumSet::empty();
+        assert!(e.is_empty());
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // intersect
+
+    #[test]
+    fn test_two_empties_do_not_intersect() {
+        let e1: EnumSet<Foo> = EnumSet::empty();
+        let e2: EnumSet<Foo> = EnumSet::empty();
+        assert!(!e1.intersects(e2));
+    }
+
+    #[test]
+    fn test_empty_does_not_intersect_with_full() {
+        let e1: EnumSet<Foo> = EnumSet::empty();
+
+        let mut e2: EnumSet<Foo> = EnumSet::empty();
+        e2.add(A);
+        e2.add(B);
+        e2.add(C);
+
+        assert!(!e1.intersects(e2));
+    }
+
+    #[test]
+    fn test_disjoint_intersects() {
+        let mut e1: EnumSet<Foo> = EnumSet::empty();
+        e1.add(A);
+
+        let mut e2: EnumSet<Foo> = EnumSet::empty();
+        e2.add(B);
+
+        assert!(!e1.intersects(e2));
+    }
+
+    #[test]
+    fn test_overlapping_intersects() {
+        let mut e1: EnumSet<Foo> = EnumSet::empty();
+        e1.add(A);
+
+        let mut e2: EnumSet<Foo> = EnumSet::empty();
+        e2.add(A);
+        e2.add(B);
+
+        assert!(e1.intersects(e2));
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // contains and contains_elem
+
+    #[test]
+    fn test_contains() {
+        let mut e1: EnumSet<Foo> = EnumSet::empty();
+        e1.add(A);
+
+        let mut e2: EnumSet<Foo> = EnumSet::empty();
+        e2.add(A);
+        e2.add(B);
+
+        assert!(!e1.contains(e2));
+        assert!(e2.contains(e1));
+    }
+
+    #[test]
+    fn test_contains_elem() {
+        let mut e1: EnumSet<Foo> = EnumSet::empty();
+        e1.add(A);
+        assert!(e1.contains_elem(A));
+        assert!(!e1.contains_elem(B));
+        assert!(!e1.contains_elem(C));
+
+        e1.add(A);
+        e1.add(B);
+        assert!(e1.contains_elem(A));
+        assert!(e1.contains_elem(B));
+        assert!(!e1.contains_elem(C));
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // each
+
+    #[test]
+    fn test_each() {
+        let mut e1: EnumSet<Foo> = EnumSet::empty();
+
+        assert_eq!(~[], iter::to_vec(|f| e1.each(f)))
+
+        e1.add(A);
+        assert_eq!(~[A], iter::to_vec(|f| e1.each(f)))
+
+        e1.add(C);
+        assert_eq!(~[A,C], iter::to_vec(|f| e1.each(f)))
+
+        e1.add(C);
+        assert_eq!(~[A,C], iter::to_vec(|f| e1.each(f)))
+
+        e1.add(B);
+        assert_eq!(~[A,B,C], iter::to_vec(|f| e1.each(f)))
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // operators
+
+    #[test]
+    fn test_operators() {
+        let mut e1: EnumSet<Foo> = EnumSet::empty();
+        e1.add(A);
+        e1.add(C);
+
+        let mut e2: EnumSet<Foo> = EnumSet::empty();
+        e2.add(B);
+        e2.add(C);
+
+        let e_union = e1 | e2;
+        assert_eq!(~[A,B,C], iter::to_vec(|f| e_union.each(f)))
+
+        let e_intersection = e1 & e2;
+        assert_eq!(~[C], iter::to_vec(|f| e_intersection.each(f)))
+
+        let e_subtract = e1 - e2;
+        assert_eq!(~[A], iter::to_vec(|f| e_subtract.each(f)))
+    }
+}
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 59a0a1ba3d6..804b23025f0 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -12,7 +12,7 @@ use metadata::encoder;
 use middle::ty::{ReSkolemized, ReVar};
 use middle::ty::{bound_region, br_anon, br_named, br_self, br_cap_avoid};
 use middle::ty::{br_fresh, ctxt, field, method};
-use middle::ty::{mt, t, param_bound, param_ty};
+use middle::ty::{mt, t, param_ty};
 use middle::ty::{re_bound, re_free, re_scope, re_infer, re_static, Region,
                  re_empty};
 use middle::ty::{ty_bool, ty_bot, ty_box, ty_struct, ty_enum};
@@ -29,10 +29,16 @@ use syntax::codemap::span;
 use syntax::print::pprust;
 use syntax::{ast, ast_util};
 
+/// Produces a string suitable for debugging output.
 pub trait Repr {
     fn repr(&self, tcx: ctxt) -> ~str;
 }
 
+/// Produces a string suitable for showing to the user.
+pub trait UserString {
+    fn user_string(&self, tcx: ctxt) -> ~str;
+}
+
 pub fn note_and_explain_region(cx: ctxt,
                                prefix: &str,
                                region: ty::Region,
@@ -273,10 +279,6 @@ pub fn tys_to_str(cx: ctxt, ts: &[t]) -> ~str {
     fmt!("(%s)", str::connect(tstrs, ", "))
 }
 
-pub fn bound_to_str(cx: ctxt, b: param_bound) -> ~str {
-    ty::param_bound_to_str(cx, &b)
-}
-
 pub fn fn_sig_to_str(cx: ctxt, typ: &ty::FnSig) -> ~str {
     fmt!("fn%s -> %s",
          tys_to_str(cx, typ.inputs.map(|a| a.ty)),
@@ -284,15 +286,7 @@ pub fn fn_sig_to_str(cx: ctxt, typ: &ty::FnSig) -> ~str {
 }
 
 pub fn trait_ref_to_str(cx: ctxt, trait_ref: &ty::TraitRef) -> ~str {
-    let path = ty::item_path(cx, trait_ref.def_id);
-    let base = ast_map::path_to_str(path, cx.sess.intr());
-    if cx.sess.verbose() && trait_ref.substs.self_ty.is_some() {
-        let mut all_tps = copy trait_ref.substs.tps;
-        for trait_ref.substs.self_ty.each |&t| { all_tps.push(t); }
-        parameterized(cx, base, trait_ref.substs.self_r, all_tps)
-    } else {
-        parameterized(cx, base, trait_ref.substs.self_r, trait_ref.substs.tps)
-    }
+    trait_ref.user_string(cx)
 }
 
 pub fn ty_to_str(cx: ctxt, typ: t) -> ~str {
@@ -555,15 +549,21 @@ impl Repr for ty::substs {
     }
 }
 
-impl Repr for ty::param_bound {
+impl Repr for ty::ParamBounds {
     fn repr(&self, tcx: ctxt) -> ~str {
-        match *self {
-            ty::bound_copy => ~"copy",
-            ty::bound_durable => ~"'static",
-            ty::bound_owned => ~"owned",
-            ty::bound_const => ~"const",
-            ty::bound_trait(ref t) => t.repr(tcx)
+        let mut res = ~[];
+        for self.builtin_bounds.each |b| {
+            res.push(match b {
+                ty::BoundCopy => ~"Copy",
+                ty::BoundStatic => ~"'static",
+                ty::BoundOwned => ~"Owned",
+                ty::BoundConst => ~"Const",
+            });
+        }
+        for self.trait_bounds.each |t| {
+            res.push(t.repr(tcx));
         }
+        str::connect(res, "+")
     }
 }
 
@@ -755,3 +755,53 @@ impl Repr for ast_map::path_elt {
         }
     }
 }
+
+impl Repr for ty::BuiltinBound {
+    fn repr(&self, _tcx: ctxt) -> ~str {
+        fmt!("%?", *self)
+    }
+}
+
+impl UserString for ty::BuiltinBound {
+    fn user_string(&self, _tcx: ctxt) -> ~str {
+        match *self {
+            ty::BoundCopy => ~"Copy",
+            ty::BoundStatic => ~"'static",
+            ty::BoundOwned => ~"Owned",
+            ty::BoundConst => ~"Const"
+        }
+    }
+}
+
+impl Repr for ty::BuiltinBounds {
+    fn repr(&self, tcx: ctxt) -> ~str {
+        self.user_string(tcx)
+    }
+}
+
+impl UserString for ty::BuiltinBounds {
+    fn user_string(&self, tcx: ctxt) -> ~str {
+        if self.is_empty() { ~"<no-bounds>" } else {
+            let mut result = ~[];
+            for self.each |bb| {
+                result.push(bb.user_string(tcx));
+            }
+            str::connect(result, "+")
+        }
+    }
+}
+
+impl UserString for ty::TraitRef {
+    fn user_string(&self, tcx: ctxt) -> ~str {
+        let path = ty::item_path(tcx, self.def_id);
+        let base = ast_map::path_to_str(path, tcx.sess.intr());
+        if tcx.sess.verbose() && self.substs.self_ty.is_some() {
+            let mut all_tps = copy self.substs.tps;
+            for self.substs.self_ty.each |&t| { all_tps.push(t); }
+            parameterized(tcx, base, self.substs.self_r, all_tps)
+        } else {
+            parameterized(tcx, base, self.substs.self_r,
+                          self.substs.tps)
+        }
+    }
+}
diff --git a/src/test/compile-fail/issue-2611-4.rs b/src/test/compile-fail/issue-2611-4.rs
index cf644fc198c..2385be5723e 100644
--- a/src/test/compile-fail/issue-2611-4.rs
+++ b/src/test/compile-fail/issue-2611-4.rs
@@ -20,7 +20,7 @@ struct E {
 }
 
 impl A for E {
-  fn b<F:Copy + Const,G>(_x: F) -> F { fail!() } //~ ERROR in method `b`, type parameter 0 has 2 bounds, but
+  fn b<F:Copy + Const,G>(_x: F) -> F { fail!() } //~ ERROR type parameter 0 requires `Const`
 }
 
 fn main() {}
diff --git a/src/test/compile-fail/issue-2611-3.rs b/src/test/run-pass/issue-2611-3.rs
index 248bea2d9b5..acc6ffd0dd1 100644
--- a/src/test/compile-fail/issue-2611-3.rs
+++ b/src/test/run-pass/issue-2611-3.rs
@@ -8,11 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// Tests that impl methods are matched to traits exactly:
-// we might be tempted to think matching is contravariant, but if
-// we let an impl method can have more permissive bounds than the trait
-// method it's implementing, the return type might be less specific than
-// needed. Just punt and make it invariant.
+// Tests that impls are allowed to have looser, more permissive bounds
+// than the traits require.
 
 trait A {
   fn b<C:Copy + Const,D>(x: C) -> C;