Auto merge of #56481 - arielb1:dynamic-order, r=nikomatsakis

add coherence future-compat warnings for marker-only trait objects

The future-compat warnings break code that assumes that `dyn Send + Sync !=
dyn Sync + Send`, and are the first step in making them equal. cc #33140.

Note: this lint should be made to default-warn before we merge. It is deny only for the crater run.

r? @nikomatsakis / @scalexm . cc @Centril & @alexreg.
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index f124623..833da67 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -347,6 +347,10 @@
         self.infcx.tcx
     }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.infcx.trait_object_mode()
+    }
+
     fn tag(&self) -> &'static str {
         "Generalizer"
     }
diff --git a/src/librustc/infer/equate.rs b/src/librustc/infer/equate.rs
index 27faa45..caa120f 100644
--- a/src/librustc/infer/equate.rs
+++ b/src/librustc/infer/equate.rs
@@ -39,6 +39,10 @@
 
     fn tcx(&self) -> TyCtxt<'infcx, 'gcx, 'tcx> { self.fields.tcx() }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.fields.infcx.trait_object_mode()
+    }
+
     fn a_is_expected(&self) -> bool { self.a_is_expected }
 
     fn relate_item_substs(&mut self,
diff --git a/src/librustc/infer/glb.rs b/src/librustc/infer/glb.rs
index 8968c59..ba21ebb 100644
--- a/src/librustc/infer/glb.rs
+++ b/src/librustc/infer/glb.rs
@@ -15,7 +15,7 @@
 
 use traits::ObligationCause;
 use ty::{self, Ty, TyCtxt};
-use ty::relate::{Relate, RelateResult, TypeRelation};
+use ty::relate::{self, Relate, RelateResult, TypeRelation};
 
 /// "Greatest lower bound" (common subtype)
 pub struct Glb<'combine, 'infcx: 'combine, 'gcx: 'infcx+'tcx, 'tcx: 'infcx> {
@@ -36,6 +36,10 @@
 {
     fn tag(&self) -> &'static str { "Glb" }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.fields.infcx.trait_object_mode()
+    }
+
     fn tcx(&self) -> TyCtxt<'infcx, 'gcx, 'tcx> { self.fields.tcx() }
 
     fn a_is_expected(&self) -> bool { self.a_is_expected }
diff --git a/src/librustc/infer/lub.rs b/src/librustc/infer/lub.rs
index 8875b41..80fad44 100644
--- a/src/librustc/infer/lub.rs
+++ b/src/librustc/infer/lub.rs
@@ -15,7 +15,7 @@
 
 use traits::ObligationCause;
 use ty::{self, Ty, TyCtxt};
-use ty::relate::{Relate, RelateResult, TypeRelation};
+use ty::relate::{self, Relate, RelateResult, TypeRelation};
 
 /// "Least upper bound" (common supertype)
 pub struct Lub<'combine, 'infcx: 'combine, 'gcx: 'infcx+'tcx, 'tcx: 'infcx> {
@@ -36,6 +36,10 @@
 {
     fn tag(&self) -> &'static str { "Lub" }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.fields.infcx.trait_object_mode()
+    }
+
     fn tcx(&self) -> TyCtxt<'infcx, 'gcx, 'tcx> { self.fields.tcx() }
 
     fn a_is_expected(&self) -> bool { self.a_is_expected }
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index b1a1335..c961fd5 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -35,7 +35,7 @@
 use traits::{self, ObligationCause, PredicateObligations, TraitEngine};
 use ty::error::{ExpectedFound, TypeError, UnconstrainedNumeric};
 use ty::fold::TypeFoldable;
-use ty::relate::RelateResult;
+use ty::relate::{RelateResult, TraitObjectMode};
 use ty::subst::{Kind, Substs};
 use ty::{self, GenericParamDefKind, Ty, TyCtxt};
 use ty::{FloatVid, IntVid, TyVid};
@@ -182,6 +182,9 @@
     // This flag is true while there is an active snapshot.
     in_snapshot: Cell<bool>,
 
+    // The TraitObjectMode used here,
+    trait_object_mode: TraitObjectMode,
+
     // A set of constraints that regionck must validate. Each
     // constraint has the form `T:'a`, meaning "some type `T` must
     // outlive the lifetime 'a". These constraints derive from
@@ -472,6 +475,7 @@
     global_tcx: TyCtxt<'a, 'gcx, 'gcx>,
     arena: SyncDroplessArena,
     fresh_tables: Option<RefCell<ty::TypeckTables<'tcx>>>,
+    trait_object_mode: TraitObjectMode,
 }
 
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'gcx> {
@@ -480,6 +484,7 @@
             global_tcx: self,
             arena: SyncDroplessArena::default(),
             fresh_tables: None,
+            trait_object_mode: TraitObjectMode::NoSquash,
         }
     }
 }
@@ -492,6 +497,12 @@
         self
     }
 
+    pub fn with_trait_object_mode(mut self, mode: TraitObjectMode) -> Self {
+        debug!("with_trait_object_mode: setting mode to {:?}", mode);
+        self.trait_object_mode = mode;
+        self
+    }
+
     /// Given a canonical value `C` as a starting point, create an
     /// inference context that contains each of the bound values
     /// within instantiated as a fresh variable. The `f` closure is
@@ -518,6 +529,7 @@
     pub fn enter<R>(&'tcx mut self, f: impl for<'b> FnOnce(InferCtxt<'b, 'gcx, 'tcx>) -> R) -> R {
         let InferCtxtBuilder {
             global_tcx,
+            trait_object_mode,
             ref arena,
             ref fresh_tables,
         } = *self;
@@ -526,6 +538,7 @@
             f(InferCtxt {
                 tcx,
                 in_progress_tables,
+                trait_object_mode,
                 projection_cache: Default::default(),
                 type_variables: RefCell::new(type_variable::TypeVariableTable::new()),
                 int_unification_table: RefCell::new(ut::UnificationTable::new()),
@@ -607,6 +620,10 @@
         self.in_snapshot.get()
     }
 
+    pub fn trait_object_mode(&self) -> TraitObjectMode {
+        self.trait_object_mode
+    }
+
     pub fn freshen<T: TypeFoldable<'tcx>>(&self, t: T) -> T {
         t.fold_with(&mut self.freshener())
     }
diff --git a/src/librustc/infer/nll_relate/mod.rs b/src/librustc/infer/nll_relate/mod.rs
index 773c712..0ce0eb9 100644
--- a/src/librustc/infer/nll_relate/mod.rs
+++ b/src/librustc/infer/nll_relate/mod.rs
@@ -382,6 +382,13 @@
         self.infcx.tcx
     }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        // squashing should only be done in coherence, not NLL
+        assert_eq!(self.infcx.trait_object_mode(),
+                   relate::TraitObjectMode::NoSquash);
+        relate::TraitObjectMode::NoSquash
+    }
+
     fn tag(&self) -> &'static str {
         "nll::subtype"
     }
@@ -696,6 +703,13 @@
         self.infcx.tcx
     }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        // squashing should only be done in coherence, not NLL
+        assert_eq!(self.infcx.trait_object_mode(),
+                   relate::TraitObjectMode::NoSquash);
+        relate::TraitObjectMode::NoSquash
+    }
+
     fn tag(&self) -> &'static str {
         "nll::generalizer"
     }
diff --git a/src/librustc/infer/sub.rs b/src/librustc/infer/sub.rs
index 3b0f9a5..ef2ef3f 100644
--- a/src/librustc/infer/sub.rs
+++ b/src/librustc/infer/sub.rs
@@ -15,7 +15,7 @@
 use ty::{self, Ty, TyCtxt};
 use ty::TyVar;
 use ty::fold::TypeFoldable;
-use ty::relate::{Cause, Relate, RelateResult, TypeRelation};
+use ty::relate::{self, Cause, Relate, RelateResult, TypeRelation};
 use std::mem;
 
 /// Ensures `a` is made a subtype of `b`. Returns `a` on success.
@@ -43,6 +43,10 @@
     for Sub<'combine, 'infcx, 'gcx, 'tcx>
 {
     fn tag(&self) -> &'static str { "Sub" }
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.fields.infcx.trait_object_mode()
+    }
+
     fn tcx(&self) -> TyCtxt<'infcx, 'gcx, 'tcx> { self.fields.infcx.tcx }
     fn a_is_expected(&self) -> bool { self.a_is_expected }
 
diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 82145f6..cf43710 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -209,6 +209,12 @@
 }
 
 declare_lint! {
+    pub ORDER_DEPENDENT_TRAIT_OBJECTS,
+    Deny,
+    "trait-object types were treated as different depending on marker-trait order"
+}
+
+declare_lint! {
     pub BAD_REPR,
     Warn,
     "detects incorrect use of `repr` attribute"
@@ -412,6 +418,7 @@
             PARENTHESIZED_PARAMS_IN_TYPES_AND_MODULES,
             LATE_BOUND_LIFETIME_ARGUMENTS,
             INCOHERENT_FUNDAMENTAL_IMPLS,
+            ORDER_DEPENDENT_TRAIT_OBJECTS,
             DEPRECATED,
             UNUSED_UNSAFE,
             UNUSED_MUT,
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index f10f523..af338cd 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -20,6 +20,7 @@
 use traits::IntercrateMode;
 use traits::select::IntercrateAmbiguityCause;
 use ty::{self, Ty, TyCtxt};
+use ty::relate::TraitObjectMode;
 use ty::fold::TypeFoldable;
 use ty::subst::Subst;
 
@@ -52,6 +53,7 @@
     impl1_def_id: DefId,
     impl2_def_id: DefId,
     intercrate_mode: IntercrateMode,
+    trait_object_mode: TraitObjectMode,
     on_overlap: F1,
     no_overlap: F2,
 ) -> R
@@ -62,12 +64,14 @@
     debug!("overlapping_impls(\
            impl1_def_id={:?}, \
            impl2_def_id={:?},
-           intercrate_mode={:?})",
+           intercrate_mode={:?},
+           trait_object_mode={:?})",
            impl1_def_id,
            impl2_def_id,
-           intercrate_mode);
+           intercrate_mode,
+           trait_object_mode);
 
-    let overlaps = tcx.infer_ctxt().enter(|infcx| {
+    let overlaps = tcx.infer_ctxt().with_trait_object_mode(trait_object_mode).enter(|infcx| {
         let selcx = &mut SelectionContext::intercrate(&infcx, intercrate_mode);
         overlap(selcx, impl1_def_id, impl2_def_id).is_some()
     });
@@ -79,7 +83,7 @@
     // In the case where we detect an error, run the check again, but
     // this time tracking intercrate ambuiguity causes for better
     // diagnostics. (These take time and can lead to false errors.)
-    tcx.infer_ctxt().enter(|infcx| {
+    tcx.infer_ctxt().with_trait_object_mode(trait_object_mode).enter(|infcx| {
         let selcx = &mut SelectionContext::intercrate(&infcx, intercrate_mode);
         selcx.enable_tracking_intercrate_ambiguity_causes();
         on_overlap(overlap(selcx, impl1_def_id, impl2_def_id).unwrap())
diff --git a/src/librustc/traits/error_reporting.rs b/src/librustc/traits/error_reporting.rs
index 4ef4f45..373d665 100644
--- a/src/librustc/traits/error_reporting.rs
+++ b/src/librustc/traits/error_reporting.rs
@@ -459,7 +459,7 @@
     {
         let simp = fast_reject::simplify_type(self.tcx,
                                               trait_ref.skip_binder().self_ty(),
-                                              true);
+                                              true,);
         let all_impls = self.tcx.all_impls(trait_ref.def_id());
 
         match simp {
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 8d91132..cf37c3f 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -64,6 +64,8 @@
 pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError};
 pub use self::specialize::{OverlapError, specialization_graph, translate_substs};
 pub use self::specialize::find_associated_item;
+pub use self::specialize::specialization_graph::FutureCompatOverlapError;
+pub use self::specialize::specialization_graph::FutureCompatOverlapErrorKind;
 pub use self::engine::{TraitEngine, TraitEngineExt};
 pub use self::util::{elaborate_predicates, elaborate_trait_ref, elaborate_trait_refs};
 pub use self::util::{supertraits, supertrait_def_ids, transitive_bounds,
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index c438542..d46389b 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -44,7 +44,7 @@
 use middle::lang_items;
 use mir::interpret::GlobalId;
 use ty::fast_reject;
-use ty::relate::TypeRelation;
+use ty::relate::{TypeRelation, TraitObjectMode};
 use ty::subst::{Subst, Substs};
 use ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable};
 
@@ -1501,6 +1501,13 @@
             return false;
         }
 
+        // Same idea as the above, but for alt trait object modes. These
+        // should only be used in intercrate mode - better safe than sorry.
+        if self.infcx.trait_object_mode() != TraitObjectMode::NoSquash {
+            bug!("using squashing TraitObjectMode outside of intercrate mode? param_env={:?}",
+                 param_env);
+        }
+
         // Otherwise, we can use the global cache.
         true
     }
@@ -3699,7 +3706,8 @@
         previous: &ty::PolyTraitRef<'tcx>,
         current: &ty::PolyTraitRef<'tcx>,
     ) -> bool {
-        let mut matcher = ty::_match::Match::new(self.tcx());
+        let mut matcher = ty::_match::Match::new(
+            self.tcx(), self.infcx.trait_object_mode());
         matcher.relate(previous, current).is_ok()
     }
 
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index 96bb545..70d36e9 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -24,10 +24,10 @@
 use hir::def_id::DefId;
 use infer::{InferCtxt, InferOk};
 use lint;
+use traits::{self, FutureCompatOverlapErrorKind, ObligationCause, TraitEngine};
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::sync::Lrc;
 use syntax_pos::DUMMY_SP;
-use traits::{self, ObligationCause, TraitEngine};
 use traits::select::IntercrateAmbiguityCause;
 use ty::{self, TyCtxt, TypeFoldable};
 use ty::subst::{Subst, Substs};
@@ -36,6 +36,7 @@
 use super::util::impl_trait_ref_and_oblig;
 
 /// Information pertinent to an overlapping impl error.
+#[derive(Debug)]
 pub struct OverlapError {
     pub with_impl: DefId,
     pub trait_desc: String,
@@ -318,8 +319,9 @@
             let insert_result = sg.insert(tcx, impl_def_id);
             // Report error if there was one.
             let (overlap, used_to_be_allowed) = match insert_result {
-                Err(overlap) => (Some(overlap), false),
-                Ok(opt_overlap) => (opt_overlap, true)
+                Err(overlap) => (Some(overlap), None),
+                Ok(Some(overlap)) => (Some(overlap.error), Some(overlap.kind)),
+                Ok(None) => (None, None)
             };
 
             if let Some(overlap) = overlap {
@@ -329,14 +331,20 @@
                         String::new(), |ty| {
                             format!(" for type `{}`", ty)
                         }),
-                    if used_to_be_allowed { " (E0119)" } else { "" }
+                    if used_to_be_allowed.is_some() { " (E0119)" } else { "" }
                 );
                 let impl_span = tcx.sess.source_map().def_span(
                     tcx.span_of_impl(impl_def_id).unwrap()
                 );
-                let mut err = if used_to_be_allowed {
+                let mut err = if let Some(kind) = used_to_be_allowed {
+                    let lint = match kind {
+                        FutureCompatOverlapErrorKind::Issue43355 =>
+                            lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
+                        FutureCompatOverlapErrorKind::Issue33140 =>
+                            lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS,
+                    };
                     tcx.struct_span_lint_node(
-                        lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
+                        lint,
                         tcx.hir().as_local_node_id(impl_def_id).unwrap(),
                         impl_span,
                         &msg)
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index b0ca2f6..1a22866 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -17,6 +17,7 @@
 use traits;
 use ty::{self, TyCtxt, TypeFoldable};
 use ty::fast_reject::{self, SimplifiedType};
+use ty::relate::TraitObjectMode;
 use rustc_data_structures::sync::Lrc;
 use syntax::ast::Ident;
 use util::captures::Captures;
@@ -68,10 +69,22 @@
     blanket_impls: Vec<DefId>,
 }
 
+#[derive(Copy, Clone, Debug)]
+pub enum FutureCompatOverlapErrorKind {
+    Issue43355,
+    Issue33140,
+}
+
+#[derive(Debug)]
+pub struct FutureCompatOverlapError {
+    pub error: OverlapError,
+    pub kind: FutureCompatOverlapErrorKind
+}
+
 /// The result of attempting to insert an impl into a group of children.
 enum Inserted {
     /// The impl was inserted as a new child in this group of children.
-    BecameNewSibling(Option<OverlapError>),
+    BecameNewSibling(Option<FutureCompatOverlapError>),
 
     /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc.
     ReplaceChildren(Vec<DefId>),
@@ -170,6 +183,7 @@
                 possible_sibling,
                 impl_def_id,
                 traits::IntercrateMode::Issue43355,
+                TraitObjectMode::NoSquash,
                 |overlap| {
                     if tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
                         return Ok((false, false));
@@ -200,12 +214,36 @@
                 replace_children.push(possible_sibling);
             } else {
                 if !tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
+                    // do future-compat checks for overlap. Have issue #43355
+                    // errors overwrite issue #33140 errors when both are present.
+
                     traits::overlapping_impls(
                         tcx,
                         possible_sibling,
                         impl_def_id,
                         traits::IntercrateMode::Fixed,
-                        |overlap| last_lint = Some(overlap_error(overlap)),
+                        TraitObjectMode::SquashAutoTraitsIssue33140,
+                        |overlap| {
+                            last_lint = Some(FutureCompatOverlapError {
+                                error: overlap_error(overlap),
+                                kind: FutureCompatOverlapErrorKind::Issue33140
+                            });
+                        },
+                        || (),
+                    );
+
+                    traits::overlapping_impls(
+                        tcx,
+                        possible_sibling,
+                        impl_def_id,
+                        traits::IntercrateMode::Fixed,
+                        TraitObjectMode::NoSquash,
+                        |overlap| {
+                            last_lint = Some(FutureCompatOverlapError {
+                                error: overlap_error(overlap),
+                                kind: FutureCompatOverlapErrorKind::Issue43355
+                            });
+                        },
                         || (),
                     );
                 }
@@ -272,7 +310,7 @@
     pub fn insert(&mut self,
                   tcx: TyCtxt<'a, 'gcx, 'tcx>,
                   impl_def_id: DefId)
-                  -> Result<Option<OverlapError>, OverlapError> {
+                  -> Result<Option<FutureCompatOverlapError>, OverlapError> {
         assert!(impl_def_id.is_local());
 
         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
diff --git a/src/librustc/ty/_match.rs b/src/librustc/ty/_match.rs
index d20b6d3..29067bf 100644
--- a/src/librustc/ty/_match.rs
+++ b/src/librustc/ty/_match.rs
@@ -29,17 +29,24 @@
 /// important thing about the result is Ok/Err. Also, matching never
 /// affects any type variables or unification state.
 pub struct Match<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
-    tcx: TyCtxt<'a, 'gcx, 'tcx>
+    tcx: TyCtxt<'a, 'gcx, 'tcx>,
+    trait_object_mode: relate::TraitObjectMode
 }
 
 impl<'a, 'gcx, 'tcx> Match<'a, 'gcx, 'tcx> {
-    pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Match<'a, 'gcx, 'tcx> {
-        Match { tcx }
+    pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+               trait_object_mode: relate::TraitObjectMode)
+               -> Match<'a, 'gcx, 'tcx> {
+        Match { tcx, trait_object_mode }
     }
 }
 
 impl<'a, 'gcx, 'tcx> TypeRelation<'a, 'gcx, 'tcx> for Match<'a, 'gcx, 'tcx> {
     fn tag(&self) -> &'static str { "Match" }
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.trait_object_mode
+    }
+
     fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> { self.tcx }
     fn a_is_expected(&self) -> bool { true } // irrelevant
 
diff --git a/src/librustc/ty/fast_reject.rs b/src/librustc/ty/fast_reject.rs
index 7005e14..bd01dd8 100644
--- a/src/librustc/ty/fast_reject.rs
+++ b/src/librustc/ty/fast_reject.rs
@@ -43,6 +43,9 @@
     PtrSimplifiedType,
     NeverSimplifiedType,
     TupleSimplifiedType(usize),
+    /// A trait object, all of whose components are markers
+    /// (e.g., `dyn Send + Sync`).
+    MarkerTraitObjectSimplifiedType,
     TraitSimplifiedType(D),
     ClosureSimplifiedType(D),
     GeneratorSimplifiedType(D),
@@ -78,7 +81,12 @@
         ty::Array(..) | ty::Slice(_) => Some(ArraySimplifiedType),
         ty::RawPtr(_) => Some(PtrSimplifiedType),
         ty::Dynamic(ref trait_info, ..) => {
-            Some(TraitSimplifiedType(trait_info.principal().def_id()))
+            let principal_def_id = trait_info.principal().def_id();
+            if tcx.trait_is_auto(principal_def_id) {
+                Some(MarkerTraitObjectSimplifiedType)
+            } else {
+                Some(TraitSimplifiedType(principal_def_id))
+            }
         }
         ty::Ref(_, ty, _) => {
             // since we introduce auto-refs during method lookup, we
@@ -144,6 +152,7 @@
             NeverSimplifiedType => NeverSimplifiedType,
             TupleSimplifiedType(n) => TupleSimplifiedType(n),
             TraitSimplifiedType(d) => TraitSimplifiedType(map(d)),
+            MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType,
             ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)),
             GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)),
             GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n),
@@ -170,7 +179,8 @@
             ArraySimplifiedType |
             PtrSimplifiedType |
             NeverSimplifiedType |
-            ParameterSimplifiedType => {
+            ParameterSimplifiedType |
+            MarkerTraitObjectSimplifiedType => {
                 // nothing to do
             }
             IntSimplifiedType(t) => t.hash_stable(hcx, hasher),
diff --git a/src/librustc/ty/relate.rs b/src/librustc/ty/relate.rs
index 7ad4fd5..88c3e5c 100644
--- a/src/librustc/ty/relate.rs
+++ b/src/librustc/ty/relate.rs
@@ -35,9 +35,20 @@
     ExistentialRegionBound, // relating an existential region bound
 }
 
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum TraitObjectMode {
+    NoSquash,
+    /// A temporary mode to treat `Send + Sync = Sync + Send`, should be
+    /// used only in coherence.
+    SquashAutoTraitsIssue33140
+}
+
 pub trait TypeRelation<'a, 'gcx: 'a+'tcx, 'tcx: 'a> : Sized {
     fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx>;
 
+    /// Return the trait object mode to be used.
+    fn trait_object_mode(&self) -> TraitObjectMode;
+
     /// Returns a static string we can use for printouts.
     fn tag(&self) -> &'static str;
 
@@ -596,14 +607,44 @@
                            a: &Self,
                            b: &Self)
         -> RelateResult<'tcx, Self>
-            where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a {
+        where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a {
+        use ty::ExistentialPredicate::*;
 
-        if a.len() != b.len() {
+        let tcx = relation.tcx();
+        let (a_buf, b_buf);
+        let (a_norm, b_norm): (&[_], &[_]) = match relation.trait_object_mode() {
+            TraitObjectMode::NoSquash => {
+                (a, b)
+            }
+            TraitObjectMode::SquashAutoTraitsIssue33140 => {
+                // Treat auto-trait "principal" components as equal
+                // to the non-principal components, to make
+                // `dyn Send+Sync = dyn Sync+Send`.
+                let normalize = |d: &[ty::ExistentialPredicate<'tcx>]| {
+                    let mut result: Vec<_> = d.iter().map(|pi| match pi {
+                        Trait(ref a) if tcx.trait_is_auto(a.def_id) => {
+                            AutoTrait(a.def_id)
+                        },
+                        other => *other
+                    }).collect();
+
+                    result.sort_by(|a, b| a.stable_cmp(tcx, b));
+                    result.dedup();
+                    result
+                };
+
+                a_buf = normalize(a);
+                b_buf = normalize(b);
+
+                (&a_buf, &b_buf)
+            }
+        };
+
+        if a_norm.len() != b_norm.len() {
             return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
         }
 
-        let tcx = relation.tcx();
-        let v = a.iter().zip(b.iter()).map(|(ep_a, ep_b)| {
+        let v = a_norm.iter().zip(b_norm.iter()).map(|(ep_a, ep_b)| {
             use ty::ExistentialPredicate::*;
             match (*ep_a, *ep_b) {
                 (Trait(ref a), Trait(ref b)) => Ok(Trait(relation.relate(a, b)?)),
diff --git a/src/librustc_lint/lib.rs b/src/librustc_lint/lib.rs
index 66364ff..3471218 100644
--- a/src/librustc_lint/lib.rs
+++ b/src/librustc_lint/lib.rs
@@ -294,6 +294,11 @@
             edition: None,
         },
         FutureIncompatibleInfo {
+            id: LintId::of(ORDER_DEPENDENT_TRAIT_OBJECTS),
+            reference: "issue #56484 <https://github.com/rust-lang/rust/issues/56484>",
+            edition: None,
+        },
+        FutureIncompatibleInfo {
             id: LintId::of(TYVAR_BEHIND_RAW_POINTER),
             reference: "issue #46906 <https://github.com/rust-lang/rust/issues/46906>",
             edition: Some(Edition::Edition2018),
diff --git a/src/librustc_traits/chalk_context/resolvent_ops.rs b/src/librustc_traits/chalk_context/resolvent_ops.rs
index df6458a..73aa8a1 100644
--- a/src/librustc_traits/chalk_context/resolvent_ops.rs
+++ b/src/librustc_traits/chalk_context/resolvent_ops.rs
@@ -17,7 +17,7 @@
 };
 use rustc::ty::{self, Ty};
 use rustc::ty::subst::Kind;
-use rustc::ty::relate::{Relate, RelateResult, TypeRelation};
+use rustc::ty::relate::{self, Relate, RelateResult, TypeRelation};
 use syntax_pos::DUMMY_SP;
 
 use super::{ChalkInferenceContext, ChalkArenas, ChalkExClause, ConstrainedSubst};
@@ -137,6 +137,10 @@
         self.infcx.tcx
     }
 
+    fn trait_object_mode(&self) -> relate::TraitObjectMode {
+        self.infcx.trait_object_mode()
+    }
+
     fn tag(&self) -> &'static str {
         "chalk_context::answer_substitutor"
     }
diff --git a/src/librustc_typeck/coherence/inherent_impls_overlap.rs b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
index ec1a439..c273c8f 100644
--- a/src/librustc_typeck/coherence/inherent_impls_overlap.rs
+++ b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
@@ -12,8 +12,9 @@
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use rustc::hir;
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
-use rustc::traits::{self, IntercrateMode};
+use rustc::traits::{self, IntercrateMode, FutureCompatOverlapErrorKind};
 use rustc::ty::TyCtxt;
+use rustc::ty::relate::TraitObjectMode;
 
 use lint;
 
@@ -29,9 +30,11 @@
 }
 
 impl<'a, 'tcx> InherentOverlapChecker<'a, 'tcx> {
-    fn check_for_common_items_in_impls(&self, impl1: DefId, impl2: DefId,
-                                       overlap: traits::OverlapResult,
-                                       used_to_be_allowed: bool) {
+    fn check_for_common_items_in_impls(
+        &self, impl1: DefId, impl2: DefId,
+        overlap: traits::OverlapResult,
+        used_to_be_allowed: Option<FutureCompatOverlapErrorKind>)
+    {
 
         let name_and_namespace = |def_id| {
             let item = self.tcx.associated_item(def_id);
@@ -47,19 +50,28 @@
             for &item2 in &impl_items2[..] {
                 if (name, namespace) == name_and_namespace(item2) {
                     let node_id = self.tcx.hir().as_local_node_id(impl1);
-                    let mut err = if used_to_be_allowed && node_id.is_some() {
-                        self.tcx.struct_span_lint_node(
-                            lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
-                            node_id.unwrap(),
-                            self.tcx.span_of_impl(item1).unwrap(),
-                            &format!("duplicate definitions with name `{}` (E0592)", name)
-                        )
-                    } else {
-                        struct_span_err!(self.tcx.sess,
-                                         self.tcx.span_of_impl(item1).unwrap(),
-                                         E0592,
-                                         "duplicate definitions with name `{}`",
-                                         name)
+                    let mut err = match used_to_be_allowed {
+                        Some(kind) if node_id.is_some() => {
+                            let lint = match kind {
+                                FutureCompatOverlapErrorKind::Issue43355 =>
+                                    lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
+                                FutureCompatOverlapErrorKind::Issue33140 =>
+                                    lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS,
+                            };
+                            self.tcx.struct_span_lint_node(
+                                lint,
+                                node_id.unwrap(),
+                                self.tcx.span_of_impl(item1).unwrap(),
+                                &format!("duplicate definitions with name `{}` (E0592)", name)
+                            )
+                        }
+                        _ => {
+                            struct_span_err!(self.tcx.sess,
+                                             self.tcx.span_of_impl(item1).unwrap(),
+                                             E0592,
+                                             "duplicate definitions with name `{}`",
+                                             name)
+                        }
                     };
 
                     err.span_label(self.tcx.span_of_impl(item1).unwrap(),
@@ -82,38 +94,73 @@
 
         for (i, &impl1_def_id) in impls.iter().enumerate() {
             for &impl2_def_id in &impls[(i + 1)..] {
+                // First, check if the impl was forbidden under the
+                // old rules. In that case, just have an error.
                 let used_to_be_allowed = traits::overlapping_impls(
                     self.tcx,
                     impl1_def_id,
                     impl2_def_id,
                     IntercrateMode::Issue43355,
+                    TraitObjectMode::NoSquash,
                     |overlap| {
                         self.check_for_common_items_in_impls(
                             impl1_def_id,
                             impl2_def_id,
                             overlap,
-                            false,
+                            None,
                         );
                         false
                     },
                     || true,
                 );
 
-                if used_to_be_allowed {
-                    traits::overlapping_impls(
-                        self.tcx,
-                        impl1_def_id,
-                        impl2_def_id,
-                        IntercrateMode::Fixed,
-                        |overlap| self.check_for_common_items_in_impls(
+                if !used_to_be_allowed {
+                    continue;
+                }
+
+                // Then, check if the impl was forbidden under only
+                // #43355. In that case, emit an #43355 error.
+                let used_to_be_allowed = traits::overlapping_impls(
+                    self.tcx,
+                    impl1_def_id,
+                    impl2_def_id,
+                    IntercrateMode::Fixed,
+                    TraitObjectMode::NoSquash,
+                    |overlap| {
+                        self.check_for_common_items_in_impls(
                             impl1_def_id,
                             impl2_def_id,
                             overlap,
-                            true,
-                        ),
-                        || (),
-                    );
+                            Some(FutureCompatOverlapErrorKind::Issue43355),
+                        );
+                        false
+                    },
+                    || true,
+                );
+
+                if !used_to_be_allowed {
+                    continue;
                 }
+
+                // Then, check if the impl was forbidden under
+                // #33140. In that case, emit a #33140 error.
+                traits::overlapping_impls(
+                    self.tcx,
+                    impl1_def_id,
+                    impl2_def_id,
+                    IntercrateMode::Fixed,
+                    TraitObjectMode::SquashAutoTraitsIssue33140,
+                    |overlap| {
+                        self.check_for_common_items_in_impls(
+                            impl1_def_id,
+                            impl2_def_id,
+                            overlap,
+                            Some(FutureCompatOverlapErrorKind::Issue33140),
+                        );
+                        false
+                    },
+                    || true,
+                );
             }
         }
     }
diff --git a/src/test/run-pass/issues/issue-33140.rs b/src/test/run-pass/issues/issue-33140.rs
new file mode 100644
index 0000000..08c6945
--- /dev/null
+++ b/src/test/run-pass/issues/issue-33140.rs
@@ -0,0 +1,57 @@
+// Copyright 2018 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.
+
+#![allow(order_dependent_trait_objects)]
+
+trait Trait {
+    fn xyz() -> bool;
+}
+
+impl Trait for dyn Send + Sync {
+    fn xyz() -> bool { false }
+}
+
+impl Trait for dyn Sync + Send {
+    fn xyz() -> bool { true }
+}
+
+trait Trait2 {
+    fn uvw() -> bool;
+}
+
+impl Trait2 for dyn Send + Sync {
+    fn uvw() -> bool { false }
+}
+
+impl Trait2 for dyn Sync + Send + Sync {
+    fn uvw() -> bool { true }
+}
+
+struct Foo<T: ?Sized>(T);
+impl Foo<dyn Send + Sync> {
+    fn abc() -> bool {
+        false
+    }
+}
+
+impl Foo<dyn Sync + Send> {
+    fn abc() -> bool {
+        true
+    }
+}
+
+fn main() {
+    assert_eq!(<dyn Send+Sync>::xyz(), false);
+    assert_eq!(<dyn Sync+Send>::xyz(), true);
+    assert_eq!(<dyn Send+Sync>::uvw(), false);
+    assert_eq!(<dyn Sync+Send+Sync>::uvw(), true);
+    assert_eq!(<Foo<dyn Send+Sync>>::abc(), false);
+    assert_eq!(<Foo<dyn Sync+Send>>::abc(), true);
+}
diff --git a/src/test/ui/issues/issue-33140.rs b/src/test/ui/issues/issue-33140.rs
new file mode 100644
index 0000000..fef5a82
--- /dev/null
+++ b/src/test/ui/issues/issue-33140.rs
@@ -0,0 +1,62 @@
+// Copyright 2018 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.
+
+#![deny(order_dependent_trait_objects)]
+
+trait Trait {
+    fn xyz() -> bool;
+}
+
+impl Trait for dyn Send + Sync {
+    fn xyz() -> bool { false }
+}
+
+impl Trait for dyn Sync + Send {
+//~^ ERROR conflicting implementations
+//~| hard error
+    fn xyz() -> bool { true }
+}
+
+trait Trait2 {
+    fn uvw() -> bool;
+}
+
+impl Trait2 for dyn Send + Sync {
+    fn uvw() -> bool { false }
+}
+
+impl Trait2 for dyn Sync + Send + Sync {
+//~^ ERROR conflicting implementations
+//~| hard error
+    fn uvw() -> bool { true }
+}
+
+struct Foo<T: ?Sized>(T);
+impl Foo<dyn Send + Sync> {
+    fn abc() -> bool { //~ ERROR duplicate definitions with name `abc`
+                       //~| hard error
+        false
+    }
+}
+
+impl Foo<dyn Sync + Send> {
+    fn abc() -> bool {
+        true
+    }
+}
+
+fn main() {
+    assert_eq!(<Send+Sync>::xyz(), false);
+    assert_eq!(<Sync+Send>::xyz(), true);
+    assert_eq!(<Send+Sync>::uvw(), false);
+    assert_eq!(<Sync+Send+Sync>::uvw(), true);
+    assert_eq!(<Foo<Send+Sync>>::abc(), false);
+    assert_eq!(<Foo<Sync+Send>>::abc(), true);
+}
diff --git a/src/test/ui/issues/issue-33140.stderr b/src/test/ui/issues/issue-33140.stderr
new file mode 100644
index 0000000..240137f
--- /dev/null
+++ b/src/test/ui/issues/issue-33140.stderr
@@ -0,0 +1,48 @@
+error: conflicting implementations of trait `Trait` for type `(dyn std::marker::Send + std::marker::Sync + 'static)`: (E0119)
+  --> $DIR/issue-33140.rs:21:1
+   |
+LL | impl Trait for dyn Send + Sync {
+   | ------------------------------ first implementation here
+...
+LL | impl Trait for dyn Sync + Send {
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `(dyn std::marker::Send + std::marker::Sync + 'static)`
+   |
+note: lint level defined here
+  --> $DIR/issue-33140.rs:11:9
+   |
+LL | #![deny(order_dependent_trait_objects)]
+   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
+   = note: for more information, see issue #56484 <https://github.com/rust-lang/rust/issues/56484>
+
+error: conflicting implementations of trait `Trait2` for type `(dyn std::marker::Send + std::marker::Sync + 'static)`: (E0119)
+  --> $DIR/issue-33140.rs:35:1
+   |
+LL | impl Trait2 for dyn Send + Sync {
+   | ------------------------------- first implementation here
+...
+LL | impl Trait2 for dyn Sync + Send + Sync {
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `(dyn std::marker::Send + std::marker::Sync + 'static)`
+   |
+   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
+   = note: for more information, see issue #56484 <https://github.com/rust-lang/rust/issues/56484>
+
+error: duplicate definitions with name `abc` (E0592)
+  --> $DIR/issue-33140.rs:43:5
+   |
+LL | /     fn abc() -> bool { //~ ERROR duplicate definitions with name `abc`
+LL | |                        //~| hard error
+LL | |         false
+LL | |     }
+   | |_____^ duplicate definitions for `abc`
+...
+LL | /     fn abc() -> bool {
+LL | |         true
+LL | |     }
+   | |_____- other definition for `abc`
+   |
+   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
+   = note: for more information, see issue #56484 <https://github.com/rust-lang/rust/issues/56484>
+
+error: aborting due to 3 previous errors
+