Track constness while lowering bounds
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index 4b2e90e..a914537 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -1237,7 +1237,7 @@
             // The traits' privacy in bodies is already checked as a part of trait object types.
             let bounds = rustc_typeck::hir_trait_to_predicates(self.tcx, trait_ref);
 
-            for (trait_predicate, _) in bounds.trait_bounds {
+            for (trait_predicate, _, _) in bounds.trait_bounds {
                 if self.visit_trait(*trait_predicate.skip_binder()) {
                     return;
                 }
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 9253c00..6726a14 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -31,7 +31,7 @@
 use rustc_span::{MultiSpan, Span, DUMMY_SP};
 use rustc_target::spec::abi;
 use smallvec::SmallVec;
-use syntax::ast;
+use syntax::ast::{self, Constness};
 use syntax::util::lev_distance::find_best_match_for_name;
 
 use std::collections::BTreeSet;
@@ -49,6 +49,8 @@
 
     fn item_def_id(&self) -> Option<DefId>;
 
+    fn default_constness_for_trait_bounds(&self) -> Constness;
+
     /// Returns predicates in scope of the form `X: Foo`, where `X` is
     /// a type parameter `X` with the given id `def_id`. This is a
     /// subset of the full set of predicates.
@@ -919,6 +921,7 @@
         &self,
         trait_ref: &hir::TraitRef<'_>,
         span: Span,
+        constness: Constness,
         self_ty: Ty<'tcx>,
         bounds: &mut Bounds<'tcx>,
         speculative: bool,
@@ -947,7 +950,7 @@
         );
         let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs));
 
-        bounds.trait_bounds.push((poly_trait_ref, span));
+        bounds.trait_bounds.push((poly_trait_ref, span, constness));
 
         let mut dup_bindings = FxHashMap::default();
         for binding in &assoc_bindings {
@@ -993,12 +996,14 @@
     pub fn instantiate_poly_trait_ref(
         &self,
         poly_trait_ref: &hir::PolyTraitRef<'_>,
+        constness: Constness,
         self_ty: Ty<'tcx>,
         bounds: &mut Bounds<'tcx>,
     ) -> Option<Vec<Span>> {
         self.instantiate_poly_trait_ref_inner(
             &poly_trait_ref.trait_ref,
             poly_trait_ref.span,
+            constness,
             self_ty,
             bounds,
             false,
@@ -1181,18 +1186,22 @@
         let mut trait_bounds = Vec::new();
         let mut region_bounds = Vec::new();
 
+        let constness = self.default_constness_for_trait_bounds();
         for ast_bound in ast_bounds {
             match *ast_bound {
                 hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) => {
-                    trait_bounds.push(b)
+                    trait_bounds.push((b, constness))
+                }
+                hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::MaybeConst) => {
+                    trait_bounds.push((b, Constness::NotConst))
                 }
                 hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
                 hir::GenericBound::Outlives(ref l) => region_bounds.push(l),
             }
         }
 
-        for bound in trait_bounds {
-            let _ = self.instantiate_poly_trait_ref(bound, param_ty, bounds);
+        for (bound, constness) in trait_bounds {
+            let _ = self.instantiate_poly_trait_ref(bound, constness, param_ty, bounds);
         }
 
         bounds.region_bounds.extend(
@@ -1226,7 +1235,7 @@
         let mut bounds = Bounds::default();
 
         self.add_bounds(param_ty, ast_bounds, &mut bounds);
-        bounds.trait_bounds.sort_by_key(|(t, _)| t.def_id());
+        bounds.trait_bounds.sort_by_key(|(t, _, _)| t.def_id());
 
         bounds.implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
             if !self.is_unsized(ast_bounds, span) { Some(span) } else { None }
@@ -1417,15 +1426,21 @@
         let mut potential_assoc_types = Vec::new();
         let dummy_self = self.tcx().types.trait_object_dummy_self;
         for trait_bound in trait_bounds.iter().rev() {
-            let cur_potential_assoc_types =
-                self.instantiate_poly_trait_ref(trait_bound, dummy_self, &mut bounds);
+            let cur_potential_assoc_types = self.instantiate_poly_trait_ref(
+                trait_bound,
+                Constness::NotConst,
+                dummy_self,
+                &mut bounds,
+            );
             potential_assoc_types.extend(cur_potential_assoc_types.into_iter().flatten());
         }
 
         // Expand trait aliases recursively and check that only one regular (non-auto) trait
         // is used and no 'maybe' bounds are used.
-        let expanded_traits =
-            traits::expand_trait_aliases(tcx, bounds.trait_bounds.iter().cloned());
+        let expanded_traits = traits::expand_trait_aliases(
+            tcx,
+            bounds.trait_bounds.iter().map(|&(a, b, _)| (a.clone(), b)),
+        );
         let (mut auto_traits, regular_traits): (Vec<_>, Vec<_>) =
             expanded_traits.partition(|i| tcx.trait_is_auto(i.trait_ref().def_id()));
         if regular_traits.len() > 1 {
@@ -1481,16 +1496,18 @@
         let regular_traits_refs_spans = bounds
             .trait_bounds
             .into_iter()
-            .filter(|(trait_ref, _)| !tcx.trait_is_auto(trait_ref.def_id()));
+            .filter(|(trait_ref, _, _)| !tcx.trait_is_auto(trait_ref.def_id()));
 
-        for (base_trait_ref, span) in regular_traits_refs_spans {
+        for (base_trait_ref, span, constness) in regular_traits_refs_spans {
+            assert_eq!(constness, ast::Constness::NotConst);
+
             for trait_ref in traits::elaborate_trait_ref(tcx, base_trait_ref) {
                 debug!(
                     "conv_object_ty_poly_trait_ref: observing object predicate `{:?}`",
                     trait_ref
                 );
                 match trait_ref {
-                    ty::Predicate::Trait(pred, constness) => {
+                    ty::Predicate::Trait(pred, _) => {
                         associated_types.entry(span).or_default().extend(
                             tcx.associated_items(pred.def_id())
                                 .filter(|item| item.kind == ty::AssocKind::Type)
@@ -2949,7 +2966,7 @@
 
     /// A list of trait bounds. So if you had `T: Debug` this would be
     /// `T: Debug`. Note that the self-type is explicit here.
-    pub trait_bounds: Vec<(ty::PolyTraitRef<'tcx>, Span)>,
+    pub trait_bounds: Vec<(ty::PolyTraitRef<'tcx>, Span, Constness)>,
 
     /// A list of projection equality bounds. So if you had `T:
     /// Iterator<Item = u32>` this would include `<T as
@@ -2997,11 +3014,10 @@
                         let outlives = ty::OutlivesPredicate(param_ty, region_bound);
                         (ty::Binder::bind(outlives).to_predicate(), span)
                     })
-                    .chain(
-                        self.trait_bounds
-                            .iter()
-                            .map(|&(bound_trait_ref, span)| (bound_trait_ref.to_predicate(), span)),
-                    )
+                    .chain(self.trait_bounds.iter().map(|&(bound_trait_ref, span, constness)| {
+                        let predicate = bound_trait_ref.with_constness(constness).to_predicate();
+                        (predicate, span)
+                    }))
                     .chain(
                         self.projection_bounds
                             .iter()
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 1e3927f..5e1b3a7 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -90,6 +90,7 @@
 use crate::astconv::{AstConv, PathSeg};
 use crate::middle::lang_items;
 use crate::namespace::Namespace;
+use rustc::hir::map::blocks::FnLikeNode;
 use rustc::hir::map::Map;
 use rustc::infer::canonical::{Canonical, OriginalQueryValues, QueryResponse};
 use rustc::infer::error_reporting::TypeAnnotationNeeded::E0282;
@@ -2612,6 +2613,16 @@
         None
     }
 
+    fn default_constness_for_trait_bounds(&self) -> ast::Constness {
+        // FIXME: refactor this into a method
+        let node = self.tcx.hir().get(self.body_id);
+        if let Some(fn_like) = FnLikeNode::from_node(node) {
+            fn_like.constness()
+        } else {
+            ast::Constness::NotConst
+        }
+    }
+
     fn get_type_parameter_bounds(&self, _: Span, def_id: DefId) -> ty::GenericPredicates<'tcx> {
         let tcx = self.tcx;
         let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 1211075..45d969a 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -20,6 +20,7 @@
 use crate::lint;
 use crate::middle::resolve_lifetime as rl;
 use crate::middle::weak_lang_items;
+use rustc::hir::map::blocks::FnLikeNode;
 use rustc::hir::map::Map;
 use rustc::middle::codegen_fn_attrs::{CodegenFnAttrFlags, CodegenFnAttrs};
 use rustc::mir::mono::Linkage;
@@ -288,6 +289,22 @@
         Some(self.item_def_id)
     }
 
+    fn default_constness_for_trait_bounds(&self) -> ast::Constness {
+        // FIXME: refactor this into a method
+        let hir_id = self
+            .tcx
+            .hir()
+            .as_local_hir_id(self.item_def_id)
+            .expect("Non-local call to local provider is_const_fn");
+
+        let node = self.tcx.hir().get(hir_id);
+        if let Some(fn_like) = FnLikeNode::from_node(node) {
+            fn_like.constness()
+        } else {
+            ast::Constness::NotConst
+        }
+    }
+
     fn get_type_parameter_bounds(&self, span: Span, def_id: DefId) -> ty::GenericPredicates<'tcx> {
         self.tcx.at(span).type_param_predicates((self.item_def_id, def_id))
     }
@@ -454,6 +471,7 @@
         ty: Ty<'tcx>,
         only_self_bounds: OnlySelfBounds,
     ) -> Vec<(ty::Predicate<'tcx>, Span)> {
+        let constness = self.default_constness_for_trait_bounds();
         let from_ty_params = ast_generics
             .params
             .iter()
@@ -462,7 +480,7 @@
                 _ => None,
             })
             .flat_map(|bounds| bounds.iter())
-            .flat_map(|b| predicates_from_bound(self, ty, b));
+            .flat_map(|b| predicates_from_bound(self, ty, b, constness));
 
         let from_where_clauses = ast_generics
             .where_clause
@@ -482,7 +500,7 @@
                 };
                 bp.bounds.iter().filter_map(move |b| bt.map(|bt| (bt, b)))
             })
-            .flat_map(|(bt, b)| predicates_from_bound(self, bt, b));
+            .flat_map(|(bt, b)| predicates_from_bound(self, bt, b, constness));
 
         from_ty_params.chain(from_where_clauses).collect()
     }
@@ -2107,6 +2125,7 @@
     let mut is_default_impl_trait = None;
 
     let icx = ItemCtxt::new(tcx, def_id);
+    let constness = icx.default_constness_for_trait_bounds();
 
     const NO_GENERICS: &hir::Generics<'_> = &hir::Generics::empty();
 
@@ -2308,11 +2327,18 @@
 
                 for bound in bound_pred.bounds.iter() {
                     match bound {
-                        &hir::GenericBound::Trait(ref poly_trait_ref, _) => {
+                        &hir::GenericBound::Trait(ref poly_trait_ref, modifier) => {
+                            let constness = match modifier {
+                                hir::TraitBoundModifier::MaybeConst => ast::Constness::NotConst,
+                                hir::TraitBoundModifier::None => constness,
+                                hir::TraitBoundModifier::Maybe => bug!("this wasn't handled"),
+                            };
+
                             let mut bounds = Bounds::default();
                             let _ = AstConv::instantiate_poly_trait_ref(
                                 &icx,
                                 poly_trait_ref,
+                                constness,
                                 ty,
                                 &mut bounds,
                             );
@@ -2488,11 +2514,18 @@
     astconv: &dyn AstConv<'tcx>,
     param_ty: Ty<'tcx>,
     bound: &'tcx hir::GenericBound<'tcx>,
+    constness: ast::Constness,
 ) -> Vec<(ty::Predicate<'tcx>, Span)> {
     match *bound {
-        hir::GenericBound::Trait(ref tr, hir::TraitBoundModifier::None) => {
+        hir::GenericBound::Trait(ref tr, modifier) => {
+            let constness = match modifier {
+                hir::TraitBoundModifier::Maybe => return vec![],
+                hir::TraitBoundModifier::MaybeConst => ast::Constness::NotConst,
+                hir::TraitBoundModifier::None => constness,
+            };
+
             let mut bounds = Bounds::default();
-            let _ = astconv.instantiate_poly_trait_ref(tr, param_ty, &mut bounds);
+            let _ = astconv.instantiate_poly_trait_ref(tr, constness, param_ty, &mut bounds);
             bounds.predicates(astconv.tcx(), param_ty)
         }
         hir::GenericBound::Outlives(ref lifetime) => {
@@ -2500,7 +2533,6 @@
             let pred = ty::Binder::bind(ty::OutlivesPredicate(param_ty, region));
             vec![(ty::Predicate::TypeOutlives(pred), lifetime.span)]
         }
-        hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => vec![],
     }
 }
 
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 95cd3c6..b3cf5f2 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -382,6 +382,7 @@
         &item_cx,
         hir_trait,
         DUMMY_SP,
+        syntax::ast::Constness::NotConst,
         tcx.types.err,
         &mut bounds,
         true,