4 files changed, 68 insertions, 6 deletions

diff --git a/crates/hir_def/src/data.rs b/crates/hir_def/src/data.rs
index 0be868ba2..7d35d7083 100644
--- a/crates/hir_def/src/data.rs
+++ b/crates/hir_def/src/data.rs
@@ -10,7 +10,7 @@ use crate::{
     body::Expander,
     db::DefDatabase,
     item_tree::{AssocItem, FunctionQualifier, ItemTreeId, ModItem, Param},
-    type_ref::{TypeBound, TypeRef},
+    type_ref::{TraitRef, TypeBound, TypeRef},
     visibility::RawVisibility,
     AssocContainerId, AssocItemId, ConstId, ConstLoc, FunctionId, FunctionLoc, HasModule, ImplId,
     Intern, Lookup, ModuleId, StaticId, TraitId, TypeAliasId, TypeAliasLoc,
@@ -156,7 +156,7 @@ impl TraitData {
 
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct ImplData {
-    pub target_trait: Option<TypeRef>,
+    pub target_trait: Option<TraitRef>,
     pub target_type: TypeRef,
     pub items: Vec<AssocItemId>,
     pub is_negative: bool,
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index ca0048b16..db94bb1ef 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -31,7 +31,7 @@ use crate::{
     db::DefDatabase,
     generics::GenericParams,
     path::{path, AssociatedTypeBinding, GenericArgs, ImportAlias, ModPath, Path, PathKind},
-    type_ref::{Mutability, TypeBound, TypeRef},
+    type_ref::{Mutability, TraitRef, TypeBound, TypeRef},
     visibility::RawVisibility,
 };
 
@@ -147,6 +147,7 @@ impl ItemTree {
                 vis,
                 generics,
                 type_refs,
+                trait_refs,
                 inner_items,
             } = &mut **data;
 
@@ -173,6 +174,7 @@ impl ItemTree {
             generics.arena.shrink_to_fit();
             type_refs.arena.shrink_to_fit();
             type_refs.map.shrink_to_fit();
+            trait_refs.map.shrink_to_fit();
 
             inner_items.shrink_to_fit();
         }
@@ -295,6 +297,32 @@ impl TypeRefStorage {
     }
 }
 
+/// `TraitRef` interner.
+#[derive(Default, Debug, Eq, PartialEq)]
+struct TraitRefStorage {
+    arena: Arena<Arc<TraitRef>>,
+    map: FxHashMap<Arc<TraitRef>, Idx<Arc<TraitRef>>>,
+}
+
+impl TraitRefStorage {
+    // Note: We lie about the `Idx<TraitRef>` to hide the interner details.
+
+    fn intern(&mut self, ty: TraitRef) -> Idx<TraitRef> {
+        if let Some(id) = self.map.get(&ty) {
+            return Idx::from_raw(id.into_raw());
+        }
+
+        let ty = Arc::new(ty);
+        let idx = self.arena.alloc(ty.clone());
+        self.map.insert(ty, idx);
+        Idx::from_raw(idx.into_raw())
+    }
+
+    fn lookup(&self, id: Idx<TraitRef>) -> &TraitRef {
+        &self.arena[Idx::from_raw(id.into_raw())]
+    }
+}
+
 #[derive(Default, Debug, Eq, PartialEq)]
 struct ItemTreeData {
     imports: Arena<Import>,
@@ -319,6 +347,7 @@ struct ItemTreeData {
     vis: ItemVisibilities,
     generics: GenericParamsStorage,
     type_refs: TypeRefStorage,
+    trait_refs: TraitRefStorage,
 
     inner_items: FxHashMap<FileAstId<ast::BlockExpr>, SmallVec<[ModItem; 1]>>,
 }
@@ -556,6 +585,14 @@ impl Index<Idx<TypeRef>> for ItemTree {
     }
 }
 
+impl Index<Idx<TraitRef>> for ItemTree {
+    type Output = TraitRef;
+
+    fn index(&self, id: Idx<TraitRef>) -> &Self::Output {
+        self.data().trait_refs.lookup(id)
+    }
+}
+
 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
     type Output = N;
     fn index(&self, id: FileItemTreeId<N>) -> &N {
@@ -692,7 +729,7 @@ pub struct Trait {
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Impl {
     pub generic_params: GenericParamsId,
-    pub target_trait: Option<Idx<TypeRef>>,
+    pub target_trait: Option<Idx<TraitRef>>,
     pub target_type: Idx<TypeRef>,
     pub is_negative: bool,
     pub items: Box<[AssocItem]>,
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index 3f558edd8..34af5c8d4 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -11,7 +11,7 @@ use syntax::{
 
 use crate::{
     generics::{GenericParams, TypeParamData, TypeParamProvenance},
-    type_ref::LifetimeRef,
+    type_ref::{LifetimeRef, TraitRef},
 };
 
 use super::*;
@@ -536,7 +536,7 @@ impl Ctx {
     fn lower_impl(&mut self, impl_def: &ast::Impl) -> Option<FileItemTreeId<Impl>> {
         let generic_params =
             self.lower_generic_params_and_inner_items(GenericsOwner::Impl, impl_def);
-        let target_trait = impl_def.trait_().map(|tr| self.lower_type_ref(&tr));
+        let target_trait = impl_def.trait_().map(|tr| self.lower_trait_ref(&tr));
         let target_type = self.lower_type_ref(&impl_def.self_ty()?);
         let is_negative = impl_def.excl_token().is_some();
 
@@ -740,10 +740,16 @@ impl Ctx {
         self.data().vis.alloc(vis)
     }
 
+    fn lower_trait_ref(&mut self, trait_ref: &ast::Type) -> Idx<TraitRef> {
+        let trait_ref = TraitRef::from_ast(&self.body_ctx, trait_ref.clone());
+        self.data().trait_refs.intern(trait_ref)
+    }
+
     fn lower_type_ref(&mut self, type_ref: &ast::Type) -> Idx<TypeRef> {
         let tyref = TypeRef::from_ast(&self.body_ctx, type_ref.clone());
         self.data().type_refs.intern(tyref)
     }
+
     fn lower_type_ref_opt(&mut self, type_ref: Option<ast::Type>) -> Idx<TypeRef> {
         match type_ref.map(|ty| self.lower_type_ref(&ty)) {
             Some(it) => it,
diff --git a/crates/hir_def/src/type_ref.rs b/crates/hir_def/src/type_ref.rs
index 049b2e462..b7484ed0d 100644
--- a/crates/hir_def/src/type_ref.rs
+++ b/crates/hir_def/src/type_ref.rs
@@ -51,6 +51,25 @@ impl Rawness {
     }
 }
 
+#[derive(Clone, PartialEq, Eq, Hash, Debug)]
+pub enum TraitRef {
+    Path(Path),
+    Error,
+}
+
+impl TraitRef {
+    /// Converts an `ast::PathType` to a `hir::TraitRef`.
+    pub(crate) fn from_ast(ctx: &LowerCtx, node: ast::Type) -> Self {
+        // FIXME: Use `Path::from_src`
+        match node {
+            ast::Type::PathType(path) => path
+                .path()
+                .and_then(|it| ctx.lower_path(it))
+                .map_or(TraitRef::Error, TraitRef::Path),
+            _ => TraitRef::Error,
+        }
+    }
+}
 /// Compare ty::Ty
 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
 pub enum TypeRef {