Auto merge of #86118 - spastorino:tait-soundness-bug, r=nikomatsakis

Create different inference variables for different defining uses of TAITs

Fixes #73481

r? `@nikomatsakis`
cc `@oli-obk`

21 files changed, 439 insertions, 132 deletions

diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index a8b9f479f1e..bbfe225e23e 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -96,6 +96,7 @@ pub mod thin_vec;
 pub mod tiny_list;
 pub mod transitive_relation;
 pub mod vec_linked_list;
+pub mod vec_map;
 pub mod work_queue;
 pub use atomic_ref::AtomicRef;
 pub mod frozen;
diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs
new file mode 100644
index 00000000000..73b04d3329c
--- /dev/null
+++ b/compiler/rustc_data_structures/src/vec_map.rs
@@ -0,0 +1,155 @@
+use std::borrow::Borrow;
+use std::iter::FromIterator;
+use std::slice::{Iter, IterMut};
+use std::vec::IntoIter;
+
+use crate::stable_hasher::{HashStable, StableHasher};
+
+/// A map type implemented as a vector of pairs `K` (key) and `V` (value).
+/// It currently provides a subset of all the map operations, the rest could be added as needed.
+#[derive(Clone, Encodable, Decodable, Debug)]
+pub struct VecMap<K, V>(Vec<(K, V)>);
+
+impl<K, V> VecMap<K, V>
+where
+    K: PartialEq,
+{
+    pub fn new() -> Self {
+        VecMap(Default::default())
+    }
+
+    /// Sets the value of the entry, and returns the entry's old value.
+    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
+        if let Some(elem) = self.0.iter_mut().find(|(key, _)| *key == k) {
+            Some(std::mem::replace(&mut elem.1, v))
+        } else {
+            self.0.push((k, v));
+            None
+        }
+    }
+
+    /// Gets a reference to the value in the entry.
+    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: Eq,
+    {
+        self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1)
+    }
+
+    /// Returns the value corresponding to the supplied predicate filter.
+    ///
+    /// The supplied predicate will be applied to each (key, value) pair and it will return a
+    /// reference to the values where the predicate returns `true`.
+    pub fn get_by(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> {
+        self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1)
+    }
+
+    /// Returns `true` if the map contains a value for the specified key.
+    ///
+    /// The key may be any borrowed form of the map's key type,
+    /// [`Eq`] on the borrowed form *must* match those for
+    /// the key type.
+    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: Eq,
+    {
+        self.get(k).is_some()
+    }
+
+    /// Returns `true` if the map contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    pub fn iter(&self) -> Iter<'_, (K, V)> {
+        self.into_iter()
+    }
+
+    pub fn iter_mut(&mut self) -> IterMut<'_, (K, V)> {
+        self.into_iter()
+    }
+}
+
+impl<K, V> Default for VecMap<K, V> {
+    #[inline]
+    fn default() -> Self {
+        Self(Default::default())
+    }
+}
+
+impl<K, V> From<Vec<(K, V)>> for VecMap<K, V> {
+    fn from(vec: Vec<(K, V)>) -> Self {
+        Self(vec)
+    }
+}
+
+impl<K, V> Into<Vec<(K, V)>> for VecMap<K, V> {
+    fn into(self) -> Vec<(K, V)> {
+        self.0
+    }
+}
+
+impl<K, V> FromIterator<(K, V)> for VecMap<K, V> {
+    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
+        Self(iter.into_iter().collect())
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a VecMap<K, V> {
+    type Item = &'a (K, V);
+    type IntoIter = Iter<'a, (K, V)>;
+
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.iter()
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a mut VecMap<K, V> {
+    type Item = &'a mut (K, V);
+    type IntoIter = IterMut<'a, (K, V)>;
+
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.iter_mut()
+    }
+}
+
+impl<K, V> IntoIterator for VecMap<K, V> {
+    type Item = (K, V);
+    type IntoIter = IntoIter<(K, V)>;
+
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
+    }
+}
+
+impl<K, V> Extend<(K, V)> for VecMap<K, V> {
+    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
+        self.0.extend(iter);
+    }
+
+    fn extend_one(&mut self, item: (K, V)) {
+        self.0.extend_one(item);
+    }
+
+    fn extend_reserve(&mut self, additional: usize) {
+        self.0.extend_reserve(additional);
+    }
+}
+
+impl<K, V, CTX> HashStable<CTX> for VecMap<K, V>
+where
+    K: HashStable<CTX> + Eq,
+    V: HashStable<CTX>,
+{
+    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
+        self.0.hash_stable(hcx, hasher)
+    }
+}
+
+#[cfg(test)]
+mod tests;
diff --git a/compiler/rustc_data_structures/src/vec_map/tests.rs b/compiler/rustc_data_structures/src/vec_map/tests.rs
new file mode 100644
index 00000000000..9083de85982
--- /dev/null
+++ b/compiler/rustc_data_structures/src/vec_map/tests.rs
@@ -0,0 +1,48 @@
+use super::*;
+
+impl<K, V> VecMap<K, V> {
+    fn into_vec(self) -> Vec<(K, V)> {
+        self.0.into()
+    }
+}
+
+#[test]
+fn test_from_iterator() {
+    assert_eq!(
+        std::iter::empty().collect::<VecMap<i32, bool>>().into_vec(),
+        Vec::<(i32, bool)>::new()
+    );
+    assert_eq!(std::iter::once((42, true)).collect::<VecMap<_, _>>().into_vec(), vec![(42, true)]);
+    assert_eq!(
+        vec![(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>().into_vec(),
+        vec![(1, true), (2, false)]
+    );
+}
+
+#[test]
+fn test_into_iterator_owned() {
+    assert_eq!(VecMap::new().into_iter().collect::<Vec<(i32, bool)>>(), Vec::<(i32, bool)>::new());
+    assert_eq!(VecMap::from(vec![(1, true)]).into_iter().collect::<Vec<_>>(), vec![(1, true)]);
+    assert_eq!(
+        VecMap::from(vec![(1, true), (2, false)]).into_iter().collect::<Vec<_>>(),
+        vec![(1, true), (2, false)]
+    );
+}
+
+#[test]
+fn test_insert() {
+    let mut v = VecMap::new();
+    assert_eq!(v.insert(1, true), None);
+    assert_eq!(v.insert(2, false), None);
+    assert_eq!(v.clone().into_vec(), vec![(1, true), (2, false)]);
+    assert_eq!(v.insert(1, false), Some(true));
+    assert_eq!(v.into_vec(), vec![(1, false), (2, false)]);
+}
+
+#[test]
+fn test_get() {
+    let v = vec![(1, true), (2, false)].into_iter().collect::<VecMap<_, _>>();
+    assert_eq!(v.get(&1), Some(&true));
+    assert_eq!(v.get(&2), Some(&false));
+    assert_eq!(v.get(&3), None);
+}
diff --git a/compiler/rustc_middle/src/mir/query.rs b/compiler/rustc_middle/src/mir/query.rs
index 0edb79fdbc8..4fb737f463a 100644
--- a/compiler/rustc_middle/src/mir/query.rs
+++ b/compiler/rustc_middle/src/mir/query.rs
@@ -2,13 +2,14 @@
 
 use crate::mir::{abstract_const, Body, Promoted};
 use crate::ty::{self, Ty, TyCtxt};
-use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::sync::Lrc;
+use rustc_data_structures::vec_map::VecMap;
 use rustc_errors::ErrorReported;
 use rustc_hir as hir;
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_index::bit_set::BitMatrix;
 use rustc_index::vec::IndexVec;
+use rustc_middle::ty::OpaqueTypeKey;
 use rustc_span::Span;
 use rustc_target::abi::VariantIdx;
 use smallvec::SmallVec;
@@ -210,7 +211,7 @@ pub struct BorrowCheckResult<'tcx> {
     /// All the opaque types that are restricted to concrete types
     /// by this function. Unlike the value in `TypeckResults`, this has
     /// unerased regions.
-    pub concrete_opaque_types: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
+    pub concrete_opaque_types: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
     pub closure_requirements: Option<ClosureRegionRequirements<'tcx>>,
     pub used_mut_upvars: SmallVec<[Field; 8]>,
 }
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 047b95f116e..62d1bc7eb6d 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -34,6 +34,7 @@ use rustc_data_structures::sharded::{IntoPointer, ShardedHashMap};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::steal::Steal;
 use rustc_data_structures::sync::{self, Lock, Lrc, WorkerLocal};
+use rustc_data_structures::vec_map::VecMap;
 use rustc_errors::ErrorReported;
 use rustc_hir as hir;
 use rustc_hir::def::{DefKind, Res};
@@ -47,6 +48,7 @@ use rustc_hir::{
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_macros::HashStable;
 use rustc_middle::mir::FakeReadCause;
+use rustc_middle::ty::OpaqueTypeKey;
 use rustc_serialize::opaque::{FileEncodeResult, FileEncoder};
 use rustc_session::config::{BorrowckMode, CrateType, OutputFilenames};
 use rustc_session::lint::{Level, Lint};
@@ -286,17 +288,6 @@ impl<'a, V> LocalTableInContextMut<'a, V> {
     }
 }
 
-/// All information necessary to validate and reveal an `impl Trait`.
-#[derive(TyEncodable, TyDecodable, Debug, HashStable)]
-pub struct ResolvedOpaqueTy<'tcx> {
-    /// The revealed type as seen by this function.
-    pub concrete_type: Ty<'tcx>,
-    /// Generic parameters on the opaque type as passed by this function.
-    /// For `type Foo<A, B> = impl Bar<A, B>; fn foo<T, U>() -> Foo<T, U> { .. }`
-    /// this is `[T, U]`, not `[A, B]`.
-    pub substs: SubstsRef<'tcx>,
-}
-
 /// Whenever a value may be live across a generator yield, the type of that value winds up in the
 /// `GeneratorInteriorTypeCause` struct. This struct adds additional information about such
 /// captured types that can be useful for diagnostics. In particular, it stores the span that
@@ -424,7 +415,7 @@ pub struct TypeckResults<'tcx> {
 
     /// All the opaque types that are restricted to concrete types
     /// by this function.
-    pub concrete_opaque_types: FxHashMap<DefId, ResolvedOpaqueTy<'tcx>>,
+    pub concrete_opaque_types: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
 
     /// Tracks the minimum captures required for a closure;
     /// see `MinCaptureInformationMap` for more details.
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index b58c92b8415..227aa8dc284 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -58,7 +58,7 @@ pub use self::consts::{Const, ConstInt, ConstKind, InferConst, ScalarInt, Uneval
 pub use self::context::{
     tls, CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
     CtxtInterners, DelaySpanBugEmitted, FreeRegionInfo, GeneratorInteriorTypeCause, GlobalCtxt,
-    Lift, ResolvedOpaqueTy, TyCtxt, TypeckResults, UserType, UserTypeAnnotationIndex,
+    Lift, TyCtxt, TypeckResults, UserType, UserTypeAnnotationIndex,
 };
 pub use self::instance::{Instance, InstanceDef};
 pub use self::list::List;
@@ -835,6 +835,12 @@ impl<'tcx> InstantiatedPredicates<'tcx> {
     }
 }
 
+#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
+pub struct OpaqueTypeKey<'tcx> {
+    pub def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+}
+
 rustc_index::newtype_index! {
     /// "Universes" are used during type- and trait-checking in the
     /// presence of `for<..>` binders to control what sets of names are
diff --git a/compiler/rustc_mir/src/borrow_check/nll.rs b/compiler/rustc_mir/src/borrow_check/nll.rs
index a0265b20d12..bfeafa33a91 100644
--- a/compiler/rustc_mir/src/borrow_check/nll.rs
+++ b/compiler/rustc_mir/src/borrow_check/nll.rs
@@ -1,15 +1,14 @@
 //! The entry point of the NLL borrow checker.
 
-use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::vec_map::VecMap;
 use rustc_errors::Diagnostic;
-use rustc_hir::def_id::DefId;
 use rustc_index::vec::IndexVec;
 use rustc_infer::infer::InferCtxt;
 use rustc_middle::mir::{
     BasicBlock, Body, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind, Location,
     Promoted,
 };
-use rustc_middle::ty::{self, RegionKind, RegionVid};
+use rustc_middle::ty::{self, OpaqueTypeKey, RegionKind, RegionVid, Ty};
 use rustc_span::symbol::sym;
 use std::env;
 use std::fmt::Debug;
@@ -47,7 +46,7 @@ crate type PoloniusOutput = Output<RustcFacts>;
 /// closure requirements to propagate, and any generated errors.
 crate struct NllOutput<'tcx> {
     pub regioncx: RegionInferenceContext<'tcx>,
-    pub opaque_type_values: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
+    pub opaque_type_values: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
     pub polonius_output: Option<Rc<PoloniusOutput>>,
     pub opt_closure_req: Option<ClosureRegionRequirements<'tcx>>,
     pub nll_errors: RegionErrors<'tcx>,
@@ -367,7 +366,7 @@ pub(super) fn dump_annotation<'a, 'tcx>(
     body: &Body<'tcx>,
     regioncx: &RegionInferenceContext<'tcx>,
     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
-    opaque_type_values: &FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
+    opaque_type_values: &VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
     errors_buffer: &mut Vec<Diagnostic>,
 ) {
     let tcx = infcx.tcx;
diff --git a/compiler/rustc_mir/src/borrow_check/region_infer/opaque_types.rs b/compiler/rustc_mir/src/borrow_check/region_infer/opaque_types.rs
index 0d1d2551042..3ec24156f22 100644
--- a/compiler/rustc_mir/src/borrow_check/region_infer/opaque_types.rs
+++ b/compiler/rustc_mir/src/borrow_check/region_infer/opaque_types.rs
@@ -1,7 +1,6 @@
-use rustc_data_structures::fx::FxHashMap;
-use rustc_hir::def_id::DefId;
+use rustc_data_structures::vec_map::VecMap;
 use rustc_infer::infer::InferCtxt;
-use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
+use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable};
 use rustc_span::Span;
 use rustc_trait_selection::opaque_types::InferCtxtExt;
 
@@ -51,12 +50,13 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     pub(in crate::borrow_check) fn infer_opaque_types(
         &self,
         infcx: &InferCtxt<'_, 'tcx>,
-        opaque_ty_decls: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
+        opaque_ty_decls: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
         span: Span,
-    ) -> FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>> {
+    ) -> VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>> {
         opaque_ty_decls
             .into_iter()
-            .map(|(opaque_def_id, ty::ResolvedOpaqueTy { concrete_type, substs })| {
+            .map(|(opaque_type_key, concrete_type)| {
+                let substs = opaque_type_key.substs;
                 debug!(?concrete_type, ?substs);
 
                 let mut subst_regions = vec![self.universal_regions.fr_static];
@@ -110,16 +110,14 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
                 debug!(?universal_concrete_type, ?universal_substs);
 
+                let opaque_type_key =
+                    OpaqueTypeKey { def_id: opaque_type_key.def_id, substs: universal_substs };
                 let remapped_type = infcx.infer_opaque_definition_from_instantiation(
-                    opaque_def_id,
-                    universal_substs,
+                    opaque_type_key,
                     universal_concrete_type,
                     span,
                 );
-                (
-                    opaque_def_id,
-                    ty::ResolvedOpaqueTy { concrete_type: remapped_type, substs: universal_substs },
-                )
+                (opaque_type_key, remapped_type)
             })
             .collect()
     }
diff --git a/compiler/rustc_mir/src/borrow_check/type_check/mod.rs b/compiler/rustc_mir/src/borrow_check/type_check/mod.rs
index e294f128f2e..09cafddeeff 100644
--- a/compiler/rustc_mir/src/borrow_check/type_check/mod.rs
+++ b/compiler/rustc_mir/src/borrow_check/type_check/mod.rs
@@ -7,9 +7,10 @@ use either::Either;
 
 use rustc_data_structures::frozen::Frozen;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::vec_map::VecMap;
 use rustc_errors::struct_span_err;
 use rustc_hir as hir;
-use rustc_hir::def_id::{DefId, LocalDefId};
+use rustc_hir::def_id::LocalDefId;
 use rustc_hir::lang_items::LangItem;
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_infer::infer::canonical::QueryRegionConstraints;
@@ -27,8 +28,8 @@ use rustc_middle::ty::cast::CastTy;
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::subst::{GenericArgKind, Subst, SubstsRef, UserSubsts};
 use rustc_middle::ty::{
-    self, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, RegionVid, ToPredicate, Ty,
-    TyCtxt, UserType, UserTypeAnnotationIndex, WithConstness,
+    self, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, OpaqueTypeKey, RegionVid,
+    ToPredicate, Ty, TyCtxt, UserType, UserTypeAnnotationIndex, WithConstness,
 };
 use rustc_span::{Span, DUMMY_SP};
 use rustc_target::abi::VariantIdx;
@@ -818,7 +819,7 @@ struct TypeChecker<'a, 'tcx> {
     reported_errors: FxHashSet<(Ty<'tcx>, Span)>,
     borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>,
     universal_region_relations: &'a UniversalRegionRelations<'tcx>,
-    opaque_type_values: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
+    opaque_type_values: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
 }
 
 struct BorrowCheckContext<'a, 'tcx> {
@@ -833,7 +834,7 @@ struct BorrowCheckContext<'a, 'tcx> {
 crate struct MirTypeckResults<'tcx> {
     crate constraints: MirTypeckRegionConstraints<'tcx>,
     pub(in crate::borrow_check) universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>,
-    crate opaque_type_values: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
+    crate opaque_type_values: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
 }
 
 /// A collection of region constraints that must be satisfied for the
@@ -978,7 +979,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
             borrowck_context,
             reported_errors: Default::default(),
             universal_region_relations,
-            opaque_type_values: FxHashMap::default(),
+            opaque_type_values: VecMap::default(),
         };
         checker.check_user_type_annotations();
         checker
@@ -1240,7 +1241,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         let param_env = self.param_env;
         let body = self.body;
         let concrete_opaque_types = &tcx.typeck(anon_owner_def_id).concrete_opaque_types;
-        let mut opaque_type_values = Vec::new();
+        let mut opaque_type_values = VecMap::new();
 
         debug!("eq_opaque_type_and_type: mir_def_id={:?}", body.source.def_id());
         let opaque_type_map = self.fully_perform_op(
@@ -1281,37 +1282,39 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                             .eq(output_ty, revealed_ty)?,
                     );
 
-                    for (&opaque_def_id, opaque_decl) in &opaque_type_map {
+                    for &(opaque_type_key, opaque_decl) in &opaque_type_map {
                         let resolved_ty = infcx.resolve_vars_if_possible(opaque_decl.concrete_ty);
                         let concrete_is_opaque = if let ty::Opaque(def_id, _) = resolved_ty.kind() {
-                            *def_id == opaque_def_id
+                            *def_id == opaque_type_key.def_id
                         } else {
                             false
                         };
-                        let opaque_defn_ty = match concrete_opaque_types.get(&opaque_def_id) {
+
+                        let concrete_ty = match concrete_opaque_types
+                            .get_by(|(key, _)| key.def_id == opaque_type_key.def_id)
+                        {
                             None => {
                                 if !concrete_is_opaque {
                                     tcx.sess.delay_span_bug(
                                         body.span,
                                         &format!(
                                             "Non-defining use of {:?} with revealed type",
-                                            opaque_def_id,
+                                            opaque_type_key.def_id,
                                         ),
                                     );
                                 }
                                 continue;
                             }
-                            Some(opaque_defn_ty) => opaque_defn_ty,
+                            Some(concrete_ty) => concrete_ty,
                         };
-                        debug!("opaque_defn_ty = {:?}", opaque_defn_ty);
-                        let subst_opaque_defn_ty =
-                            opaque_defn_ty.concrete_type.subst(tcx, opaque_decl.substs);
+                        debug!("concrete_ty = {:?}", concrete_ty);
+                        let subst_opaque_defn_ty = concrete_ty.subst(tcx, opaque_type_key.substs);
                         let renumbered_opaque_defn_ty =
                             renumber::renumber_regions(infcx, subst_opaque_defn_ty);
 
                         debug!(
                             "eq_opaque_type_and_type: concrete_ty={:?}={:?} opaque_defn_ty={:?}",
-                            opaque_decl.concrete_ty, resolved_ty, renumbered_opaque_defn_ty,
+                            concrete_ty, resolved_ty, renumbered_opaque_defn_ty,
                         );
 
                         if !concrete_is_opaque {
@@ -1322,13 +1325,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                                     .at(&ObligationCause::dummy(), param_env)
                                     .eq(opaque_decl.concrete_ty, renumbered_opaque_defn_ty)?,
                             );
-                            opaque_type_values.push((
-                                opaque_def_id,
-                                ty::ResolvedOpaqueTy {
-                                    concrete_type: renumbered_opaque_defn_ty,
-                                    substs: opaque_decl.substs,
-                                },
-                            ));
+                            opaque_type_values.insert(opaque_type_key, renumbered_opaque_defn_ty);
                         } else {
                             // We're using an opaque `impl Trait` type without
                             // 'revealing' it. For example, code like this:
@@ -1351,7 +1348,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                             // gets 'revealed' into
                             debug!(
                                 "eq_opaque_type_and_type: non-defining use of {:?}",
-                                opaque_def_id,
+                                opaque_type_key.def_id,
                             );
                         }
                     }
@@ -1376,14 +1373,14 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         // prove that `T: Iterator` where `T` is the type we
         // instantiated it with).
         if let Some(opaque_type_map) = opaque_type_map {
-            for (opaque_def_id, opaque_decl) in opaque_type_map {
+            for (opaque_type_key, opaque_decl) in opaque_type_map {
                 self.fully_perform_op(
                     locations,
                     ConstraintCategory::OpaqueType,
                     CustomTypeOp::new(
                         |_cx| {
                             infcx.constrain_opaque_type(
-                                opaque_def_id,
+                                opaque_type_key,
                                 &opaque_decl,
                                 GenerateMemberConstraints::IfNoStaticBound,
                                 universal_region_relations,
diff --git a/compiler/rustc_trait_selection/src/opaque_types.rs b/compiler/rustc_trait_selection/src/opaque_types.rs
index 163df26e9ff..89ec211f262 100644
--- a/compiler/rustc_trait_selection/src/opaque_types.rs
+++ b/compiler/rustc_trait_selection/src/opaque_types.rs
@@ -2,21 +2,22 @@ use crate::infer::InferCtxtExt as _;
 use crate::traits::{self, PredicateObligation};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::sync::Lrc;
+use rustc_data_structures::vec_map::VecMap;
 use rustc_hir as hir;
-use rustc_hir::def_id::{DefId, DefIdMap, LocalDefId};
+use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_hir::Node;
 use rustc_infer::infer::error_reporting::unexpected_hidden_region_diagnostic;
 use rustc_infer::infer::free_regions::FreeRegionRelations;
 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
 use rustc_infer::infer::{self, InferCtxt, InferOk};
 use rustc_middle::ty::fold::{BottomUpFolder, TypeFoldable, TypeFolder, TypeVisitor};
-use rustc_middle::ty::subst::{GenericArg, GenericArgKind, InternalSubsts, Subst, SubstsRef};
-use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::subst::{GenericArg, GenericArgKind, InternalSubsts, Subst};
+use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt};
 use rustc_span::Span;
 
 use std::ops::ControlFlow;
 
-pub type OpaqueTypeMap<'tcx> = DefIdMap<OpaqueTypeDecl<'tcx>>;
+pub type OpaqueTypeMap<'tcx> = VecMap<OpaqueTypeKey<'tcx>, OpaqueTypeDecl<'tcx>>;
 
 /// Information about the opaque types whose values we
 /// are inferring in this function (these are the `impl Trait` that
@@ -26,19 +27,6 @@ pub struct OpaqueTypeDecl<'tcx> {
     /// The opaque type (`ty::Opaque`) for this declaration.
     pub opaque_type: Ty<'tcx>,
 
-    /// The substitutions that we apply to the opaque type that this
-    /// `impl Trait` desugars to. e.g., if:
-    ///
-    ///     fn foo<'a, 'b, T>() -> impl Trait<'a>
-    ///
-    /// winds up desugared to:
-    ///
-    ///     type Foo<'x, X> = impl Trait<'x>
-    ///     fn foo<'a, 'b, T>() -> Foo<'a, T>
-    ///
-    /// then `substs` would be `['a, T]`.
-    pub substs: SubstsRef<'tcx>,
-
     /// The span of this particular definition of the opaque type. So
     /// for example:
     ///
@@ -125,7 +113,7 @@ pub trait InferCtxtExt<'tcx> {
 
     fn constrain_opaque_type<FRR: FreeRegionRelations<'tcx>>(
         &self,
-        def_id: DefId,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         opaque_defn: &OpaqueTypeDecl<'tcx>,
         mode: GenerateMemberConstraints,
         free_region_relations: &FRR,
@@ -136,14 +124,13 @@ pub trait InferCtxtExt<'tcx> {
         &self,
         concrete_ty: Ty<'tcx>,
         opaque_defn: &OpaqueTypeDecl<'tcx>,
-        opaque_type_def_id: DefId,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         first_own_region_index: usize,
     );
 
     fn infer_opaque_definition_from_instantiation(
         &self,
-        def_id: DefId,
-        substs: SubstsRef<'tcx>,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         instantiated_ty: Ty<'tcx>,
         span: Span,
     ) -> Ty<'tcx>;
@@ -370,10 +357,10 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
     ) {
         debug!("constrain_opaque_types()");
 
-        for (&def_id, opaque_defn) in opaque_types {
+        for &(opaque_type_key, opaque_defn) in opaque_types {
             self.constrain_opaque_type(
-                def_id,
-                opaque_defn,
+                opaque_type_key,
+                &opaque_defn,
                 GenerateMemberConstraints::WhenRequired,
                 free_region_relations,
             );
@@ -383,11 +370,13 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
     /// See `constrain_opaque_types` for documentation.
     fn constrain_opaque_type<FRR: FreeRegionRelations<'tcx>>(
         &self,
-        def_id: DefId,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         opaque_defn: &OpaqueTypeDecl<'tcx>,
         mode: GenerateMemberConstraints,
         free_region_relations: &FRR,
     ) {
+        let def_id = opaque_type_key.def_id;
+
         debug!("constrain_opaque_type()");
         debug!("constrain_opaque_type: def_id={:?}", def_id);
         debug!("constrain_opaque_type: opaque_defn={:#?}", opaque_defn);
@@ -426,9 +415,9 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             let bounds = tcx.explicit_item_bounds(def_id);
             debug!("constrain_opaque_type: predicates: {:#?}", bounds);
             let bounds: Vec<_> =
-                bounds.iter().map(|(bound, _)| bound.subst(tcx, opaque_defn.substs)).collect();
+                bounds.iter().map(|(bound, _)| bound.subst(tcx, opaque_type_key.substs)).collect();
             debug!("constrain_opaque_type: bounds={:#?}", bounds);
-            let opaque_type = tcx.mk_opaque(def_id, opaque_defn.substs);
+            let opaque_type = tcx.mk_opaque(def_id, opaque_type_key.substs);
 
             let required_region_bounds =
                 required_region_bounds(tcx, opaque_type, bounds.into_iter());
@@ -440,7 +429,12 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                 });
             }
             if let GenerateMemberConstraints::IfNoStaticBound = mode {
-                self.generate_member_constraint(concrete_ty, opaque_defn, def_id, first_own_region);
+                self.generate_member_constraint(
+                    concrete_ty,
+                    opaque_defn,
+                    opaque_type_key,
+                    first_own_region,
+                );
             }
             return;
         }
@@ -454,7 +448,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         // second.
         let mut least_region = None;
 
-        for subst_arg in &opaque_defn.substs[first_own_region..] {
+        for subst_arg in &opaque_type_key.substs[first_own_region..] {
             let subst_region = match subst_arg.unpack() {
                 GenericArgKind::Lifetime(r) => r,
                 GenericArgKind::Type(_) | GenericArgKind::Const(_) => continue,
@@ -484,7 +478,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                         return self.generate_member_constraint(
                             concrete_ty,
                             opaque_defn,
-                            def_id,
+                            opaque_type_key,
                             first_own_region,
                         );
                     }
@@ -497,7 +491,12 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
 
         if let GenerateMemberConstraints::IfNoStaticBound = mode {
             if least_region != tcx.lifetimes.re_static {
-                self.generate_member_constraint(concrete_ty, opaque_defn, def_id, first_own_region);
+                self.generate_member_constraint(
+                    concrete_ty,
+                    opaque_defn,
+                    opaque_type_key,
+                    first_own_region,
+                );
             }
         }
         concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
@@ -517,14 +516,14 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         &self,
         concrete_ty: Ty<'tcx>,
         opaque_defn: &OpaqueTypeDecl<'tcx>,
-        opaque_type_def_id: DefId,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         first_own_region: usize,
     ) {
         // Create the set of choice regions: each region in the hidden
         // type can be equal to any of the region parameters of the
         // opaque type definition.
         let choice_regions: Lrc<Vec<ty::Region<'tcx>>> = Lrc::new(
-            opaque_defn.substs[first_own_region..]
+            opaque_type_key.substs[first_own_region..]
                 .iter()
                 .filter_map(|arg| match arg.unpack() {
                     GenericArgKind::Lifetime(r) => Some(r),
@@ -537,7 +536,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
             op: |r| {
                 self.member_constraint(
-                    opaque_type_def_id,
+                    opaque_type_key.def_id,
                     opaque_defn.definition_span,
                     concrete_ty,
                     r,
@@ -572,11 +571,12 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
     ///   `opaque_defn.concrete_ty`
     fn infer_opaque_definition_from_instantiation(
         &self,
-        def_id: DefId,
-        substs: SubstsRef<'tcx>,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         instantiated_ty: Ty<'tcx>,
         span: Span,
     ) -> Ty<'tcx> {
+        let OpaqueTypeKey { def_id, substs } = opaque_type_key;
+
         debug!(
             "infer_opaque_definition_from_instantiation(def_id={:?}, instantiated_ty={:?})",
             def_id, instantiated_ty
@@ -1007,7 +1007,9 @@ impl<'a, 'tcx> Instantiator<'a, 'tcx> {
                             ),
                         };
                         if in_definition_scope {
-                            return self.fold_opaque_ty(ty, def_id.to_def_id(), substs, origin);
+                            let opaque_type_key =
+                                OpaqueTypeKey { def_id: def_id.to_def_id(), substs };
+                            return self.fold_opaque_ty(ty, opaque_type_key, origin);
                         }
 
                         debug!(
@@ -1029,18 +1031,18 @@ impl<'a, 'tcx> Instantiator<'a, 'tcx> {
     fn fold_opaque_ty(
         &mut self,
         ty: Ty<'tcx>,
-        def_id: DefId,
-        substs: SubstsRef<'tcx>,
+        opaque_type_key: OpaqueTypeKey<'tcx>,
         origin: hir::OpaqueTyOrigin,
     ) -> Ty<'tcx> {
         let infcx = self.infcx;
         let tcx = infcx.tcx;
+        let OpaqueTypeKey { def_id, substs } = opaque_type_key;
 
         debug!("instantiate_opaque_types: Opaque(def_id={:?}, substs={:?})", def_id, substs);
 
         // Use the same type variable if the exact same opaque type appears more
         // than once in the return type (e.g., if it's passed to a type alias).
-        if let Some(opaque_defn) = self.opaque_types.get(&def_id) {
+        if let Some(opaque_defn) = self.opaque_types.get(&opaque_type_key) {
             debug!("instantiate_opaque_types: returning concrete ty {:?}", opaque_defn.concrete_ty);
             return opaque_defn.concrete_ty;
         }
@@ -1078,10 +1080,9 @@ impl<'a, 'tcx> Instantiator<'a, 'tcx> {
         let definition_span = self.value_span;
 
         self.opaque_types.insert(
-            def_id,
+            OpaqueTypeKey { def_id, substs },
             OpaqueTypeDecl {
                 opaque_type: ty,
-                substs,
                 definition_span,
                 concrete_ty: ty_var,
                 has_required_region_bounds: !required_region_bounds.is_empty(),
diff --git a/compiler/rustc_typeck/src/check/check.rs b/compiler/rustc_typeck/src/check/check.rs
index 166410731d2..70d85796d00 100644
--- a/compiler/rustc_typeck/src/check/check.rs
+++ b/compiler/rustc_typeck/src/check/check.rs
@@ -16,7 +16,7 @@ use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::layout::MAX_SIMD_LANES;
 use rustc_middle::ty::subst::GenericArgKind;
 use rustc_middle::ty::util::{Discr, IntTypeExt};
-use rustc_middle::ty::{self, ParamEnv, RegionKind, Ty, TyCtxt};
+use rustc_middle::ty::{self, OpaqueTypeKey, ParamEnv, RegionKind, Ty, TyCtxt};
 use rustc_session::lint::builtin::UNINHABITED_STATIC;
 use rustc_span::symbol::sym;
 use rustc_span::{self, MultiSpan, Span};
@@ -716,10 +716,10 @@ fn check_opaque_meets_bounds<'tcx>(
             infcx.instantiate_opaque_types(def_id, hir_id, param_env, opaque_ty, span),
         );
 
-        for (def_id, opaque_defn) in opaque_type_map {
+        for (OpaqueTypeKey { def_id, substs }, opaque_defn) in opaque_type_map {
             match infcx
                 .at(&misc_cause, param_env)
-                .eq(opaque_defn.concrete_ty, tcx.type_of(def_id).subst(tcx, opaque_defn.substs))
+                .eq(opaque_defn.concrete_ty, tcx.type_of(def_id).subst(tcx, substs))
             {
                 Ok(infer_ok) => inh.register_infer_ok_obligations(infer_ok),
                 Err(ty_err) => tcx.sess.delay_span_bug(
diff --git a/compiler/rustc_typeck/src/check/inherited.rs b/compiler/rustc_typeck/src/check/inherited.rs
index 1dacbade1bd..2e9bef15f90 100644
--- a/compiler/rustc_typeck/src/check/inherited.rs
+++ b/compiler/rustc_typeck/src/check/inherited.rs
@@ -2,13 +2,14 @@ use super::callee::DeferredCallResolution;
 use super::MaybeInProgressTables;
 
 use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::vec_map::VecMap;
 use rustc_hir as hir;
 use rustc_hir::def_id::{DefIdMap, LocalDefId};
 use rustc_hir::HirIdMap;
 use rustc_infer::infer;
 use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt};
 use rustc_middle::ty::fold::TypeFoldable;
-use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt};
 use rustc_span::{self, Span};
 use rustc_trait_selection::infer::InferCtxtExt as _;
 use rustc_trait_selection::opaque_types::OpaqueTypeDecl;
@@ -58,7 +59,7 @@ pub struct Inherited<'a, 'tcx> {
     // associated fresh inference variable. Writeback resolves these
     // variables to get the concrete type, which can be used to
     // 'de-opaque' OpaqueTypeDecl, after typeck is done with all functions.
-    pub(super) opaque_types: RefCell<DefIdMap<OpaqueTypeDecl<'tcx>>>,
+    pub(super) opaque_types: RefCell<VecMap<OpaqueTypeKey<'tcx>, OpaqueTypeDecl<'tcx>>>,
 
     /// A map from inference variables created from opaque
     /// type instantiations (`ty::Infer`) to the actual opaque
diff --git a/compiler/rustc_typeck/src/check/writeback.rs b/compiler/rustc_typeck/src/check/writeback.rs
index e472add6e80..032cc7ee233 100644
--- a/compiler/rustc_typeck/src/check/writeback.rs
+++ b/compiler/rustc_typeck/src/check/writeback.rs
@@ -475,8 +475,9 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
     }
 
     fn visit_opaque_types(&mut self, span: Span) {
-        for (&def_id, opaque_defn) in self.fcx.opaque_types.borrow().iter() {
-            let hir_id = self.tcx().hir().local_def_id_to_hir_id(def_id.expect_local());
+        for &(opaque_type_key, opaque_defn) in self.fcx.opaque_types.borrow().iter() {
+            let hir_id =
+                self.tcx().hir().local_def_id_to_hir_id(opaque_type_key.def_id.expect_local());
             let instantiated_ty = self.resolve(opaque_defn.concrete_ty, &hir_id);
 
             debug_assert!(!instantiated_ty.has_escaping_bound_vars());
@@ -494,50 +495,47 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
             // ```
             // figures out the concrete type with `U`, but the stored type is with `T`.
             let definition_ty = self.fcx.infer_opaque_definition_from_instantiation(
-                def_id,
-                opaque_defn.substs,
+                opaque_type_key,
                 instantiated_ty,
                 span,
             );
 
             let mut skip_add = false;
 
-            if let ty::Opaque(defin_ty_def_id, _substs) = *definition_ty.kind() {
+            if let ty::Opaque(definition_ty_def_id, _substs) = *definition_ty.kind() {
                 if let hir::OpaqueTyOrigin::Misc | hir::OpaqueTyOrigin::TyAlias = opaque_defn.origin
                 {
-                    if def_id == defin_ty_def_id {
+                    if opaque_type_key.def_id == definition_ty_def_id {
                         debug!(
                             "skipping adding concrete definition for opaque type {:?} {:?}",
-                            opaque_defn, defin_ty_def_id
+                            opaque_defn, opaque_type_key.def_id
                         );
                         skip_add = true;
                     }
                 }
             }
 
-            if !opaque_defn.substs.needs_infer() {
+            if !opaque_type_key.substs.needs_infer() {
                 // We only want to add an entry into `concrete_opaque_types`
                 // if we actually found a defining usage of this opaque type.
                 // Otherwise, we do nothing - we'll either find a defining usage
                 // in some other location, or we'll end up emitting an error due
                 // to the lack of defining usage
                 if !skip_add {
-                    let new = ty::ResolvedOpaqueTy {
-                        concrete_type: definition_ty,
-                        substs: opaque_defn.substs,
-                    };
-
-                    let old = self.typeck_results.concrete_opaque_types.insert(def_id, new);
-                    if let Some(old) = old {
-                        if old.concrete_type != definition_ty || old.substs != opaque_defn.substs {
+                    let old_concrete_ty = self
+                        .typeck_results
+                        .concrete_opaque_types
+                        .insert(opaque_type_key, definition_ty);
+                    if let Some(old_concrete_ty) = old_concrete_ty {
+                        if old_concrete_ty != definition_ty {
                             span_bug!(
                                 span,
                                 "`visit_opaque_types` tried to write different types for the same \
                                  opaque type: {:?}, {:?}, {:?}, {:?}",
-                                def_id,
+                                opaque_type_key.def_id,
                                 definition_ty,
                                 opaque_defn,
-                                old,
+                                old_concrete_ty,
                             );
                         }
                     }
diff --git a/compiler/rustc_typeck/src/collect/type_of.rs b/compiler/rustc_typeck/src/collect/type_of.rs
index 19c35ebd011..29a87b18a9e 100644
--- a/compiler/rustc_typeck/src/collect/type_of.rs
+++ b/compiler/rustc_typeck/src/collect/type_of.rs
@@ -349,8 +349,8 @@ pub(super) fn type_of(tcx: TyCtxt<'_>, def_id: DefId) -> Ty<'_> {
                     let concrete_ty = tcx
                         .mir_borrowck(owner.expect_local())
                         .concrete_opaque_types
-                        .get(&def_id.to_def_id())
-                        .map(|opaque| opaque.concrete_type)
+                        .get_by(|(key, _)| key.def_id == def_id.to_def_id())
+                        .map(|concrete_ty| *concrete_ty)
                         .unwrap_or_else(|| {
                             tcx.sess.delay_span_bug(
                                 DUMMY_SP,
@@ -515,7 +515,13 @@ fn find_opaque_ty_constraints(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Ty<'_> {
             }
             // Calling `mir_borrowck` can lead to cycle errors through
             // const-checking, avoid calling it if we don't have to.
-            if !self.tcx.typeck(def_id).concrete_opaque_types.contains_key(&self.def_id) {
+            if self
+                .tcx
+                .typeck(def_id)
+                .concrete_opaque_types
+                .get_by(|(key, _)| key.def_id == self.def_id)
+                .is_none()
+            {
                 debug!(
                     "find_opaque_ty_constraints: no constraint for `{:?}` at `{:?}`",
                     self.def_id, def_id,
@@ -523,11 +529,13 @@ fn find_opaque_ty_constraints(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Ty<'_> {
                 return;
             }
             // Use borrowck to get the type with unerased regions.
-            let ty = self.tcx.mir_borrowck(def_id).concrete_opaque_types.get(&self.def_id);
-            if let Some(ty::ResolvedOpaqueTy { concrete_type, substs }) = ty {
+            let concrete_opaque_types = &self.tcx.mir_borrowck(def_id).concrete_opaque_types;
+            if let Some((opaque_type_key, concrete_type)) =
+                concrete_opaque_types.iter().find(|(key, _)| key.def_id == self.def_id)
+            {
                 debug!(
                     "find_opaque_ty_constraints: found constraint for `{:?}` at `{:?}`: {:?}",
-                    self.def_id, def_id, ty,
+                    self.def_id, def_id, concrete_type,
                 );
 
                 // FIXME(oli-obk): trace the actual span from inference to improve errors.
@@ -538,7 +546,7 @@ fn find_opaque_ty_constraints(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Ty<'_> {
                 // using `delay_span_bug`, just in case `wfcheck` slips up.
                 let opaque_generics = self.tcx.generics_of(self.def_id);
                 let mut used_params: FxHashSet<_> = FxHashSet::default();
-                for (i, arg) in substs.iter().enumerate() {
+                for (i, arg) in opaque_type_key.substs.iter().enumerate() {
                     let arg_is_param = match arg.unpack() {
                         GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)),
                         GenericArgKind::Lifetime(lt) => {
@@ -699,8 +707,8 @@ fn let_position_impl_trait_type(tcx: TyCtxt<'_>, opaque_ty_id: LocalDefId) -> Ty
     let owner_typeck_results = tcx.typeck(scope_def_id);
     let concrete_ty = owner_typeck_results
         .concrete_opaque_types
-        .get(&opaque_ty_def_id)
-        .map(|opaque| opaque.concrete_type)
+        .get_by(|(key, _)| key.def_id == opaque_ty_def_id)
+        .map(|concrete_ty| *concrete_ty)
         .unwrap_or_else(|| {
             tcx.sess.delay_span_bug(
                 DUMMY_SP,
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn-pass.rs b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn-pass.rs
new file mode 100644
index 00000000000..ecad910f7d5
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn-pass.rs
@@ -0,0 +1,12 @@
+// check-pass
+#![feature(min_type_alias_impl_trait)]
+
+type X<A: ToString + Clone, B: ToString + Clone> = impl ToString;
+
+fn f<A: ToString + Clone, B: ToString + Clone>(a: A, b: B) -> (X<A, B>, X<A, B>) {
+    (a.clone(), a)
+}
+
+fn main() {
+    println!("{}", <X<_, _> as ToString>::to_string(&f(42_i32, String::new()).1));
+}
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn.rs b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn.rs
new file mode 100644
index 00000000000..67351e20159
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn.rs
@@ -0,0 +1,16 @@
+// https://github.com/rust-lang/rust/issues/73481
+// This test used to cause unsoundness, since one of the two possible
+// resolutions was chosen at random instead of erroring due to conflicts.
+
+#![feature(min_type_alias_impl_trait)]
+
+type X<A, B> = impl Into<&'static A>;
+//~^ ERROR the trait bound `&'static B: From<&A>` is not satisfied
+
+fn f<A, B: 'static>(a: &'static A, b: B) -> (X<A, B>, X<B, A>) {
+    (a, a)
+}
+
+fn main() {
+    println!("{}", <X<_, _> as Into<&String>>::into(f(&[1isize, 2, 3], String::new()).1));
+}
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn.stderr b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn.stderr
new file mode 100644
index 00000000000..731c6e2788d
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn.stderr
@@ -0,0 +1,15 @@
+error[E0277]: the trait bound `&'static B: From<&A>` is not satisfied
+  --> $DIR/multiple-def-uses-in-one-fn.rs:7:16
+   |
+LL | type X<A, B> = impl Into<&'static A>;
+   |                ^^^^^^^^^^^^^^^^^^^^^ the trait `From<&A>` is not implemented for `&'static B`
+   |
+   = note: required because of the requirements on the impl of `Into<&'static B>` for `&A`
+help: consider introducing a `where` bound, but there might be an alternative better way to express this requirement
+   |
+LL | fn f<A, B: 'static>(a: &'static A, b: B) -> (X<A, B>, X<B, A>) where &'static B: From<&A> {
+   |                                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn2.rs b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn2.rs
new file mode 100644
index 00000000000..38aa18fe40e
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn2.rs
@@ -0,0 +1,16 @@
+// https://github.com/rust-lang/rust/issues/73481
+// This test used to cause unsoundness, since one of the two possible
+// resolutions was chosen at random instead of erroring due to conflicts.
+
+#![feature(min_type_alias_impl_trait)]
+
+type X<A: ToString + Clone, B: ToString + Clone> = impl ToString;
+//~^ ERROR could not find defining uses
+
+fn f<A: ToString + Clone, B: ToString + Clone>(a: A, b: B) -> (X<A, B>, X<B, A>) {
+    (a.clone(), a)
+}
+
+fn main() {
+    println!("{}", <X<_, _> as ToString>::to_string(&f(42_i32, String::new()).1));
+}
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn2.stderr b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn2.stderr
new file mode 100644
index 00000000000..c00973c0761
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn2.stderr
@@ -0,0 +1,8 @@
+error: could not find defining uses
+  --> $DIR/multiple-def-uses-in-one-fn2.rs:7:52
+   |
+LL | type X<A: ToString + Clone, B: ToString + Clone> = impl ToString;
+   |                                                    ^^^^^^^^^^^^^
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn3.rs b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn3.rs
new file mode 100644
index 00000000000..17e90005811
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn3.rs
@@ -0,0 +1,18 @@
+// https://github.com/rust-lang/rust/issues/73481
+// This test used to cause unsoundness, since one of the two possible
+// resolutions was chosen at random instead of erroring due to conflicts.
+
+#![feature(min_type_alias_impl_trait)]
+
+type X<A: ToString + Clone, B: ToString + Clone> = impl ToString;
+
+fn f<A: ToString + Clone, B: ToString + Clone>(a: A, b: B) -> (X<A, B>, X<B, A>) {
+    (a, b)
+}
+
+fn g<A: ToString + Clone, B: ToString + Clone>(a: A, b: B) -> (X<A, B>, X<A, B>) {
+    (a, b)
+    //~^ ERROR mismatched types
+}
+
+fn main() {}
diff --git a/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn3.stderr b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn3.stderr
new file mode 100644
index 00000000000..bbe709dccab
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/multiple-def-uses-in-one-fn3.stderr
@@ -0,0 +1,18 @@
+error[E0308]: mismatched types
+  --> $DIR/multiple-def-uses-in-one-fn3.rs:14:9
+   |
+LL | fn g<A: ToString + Clone, B: ToString + Clone>(a: A, b: B) -> (X<A, B>, X<A, B>) {
+   |      -                    - found type parameter
+   |      |
+   |      expected type parameter
+LL |     (a, b)
+   |         ^ expected type parameter `A`, found type parameter `B`
+   |
+   = note: expected type parameter `A`
+              found type parameter `B`
+   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
+   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0308`.