12 files changed, 103 insertions, 51 deletions

diff --git a/crates/hir_def/src/attr.rs b/crates/hir_def/src/attr.rs
index 89a1ea770..385ba8c80 100644
--- a/crates/hir_def/src/attr.rs
+++ b/crates/hir_def/src/attr.rs
@@ -105,7 +105,7 @@ impl RawAttrs {
                 Either::Left(attr) => Attr::from_src(db, attr, hygiene, id),
                 Either::Right(comment) => comment.doc_comment().map(|doc| Attr {
                     id,
-                    input: Some(AttrInput::Literal(SmolStr::new(doc))),
+                    input: Some(Interned::new(AttrInput::Literal(SmolStr::new(doc)))),
                     path: Interned::new(ModPath::from(hir_expand::name!(doc))),
                 }),
             })
@@ -151,7 +151,7 @@ impl RawAttrs {
                     return smallvec![attr.clone()];
                 }
 
-                let subtree = match &attr.input {
+                let subtree = match attr.input.as_deref() {
                     Some(AttrInput::TokenTree(it)) => it,
                     _ => return smallvec![attr.clone()],
                 };
@@ -251,7 +251,7 @@ impl Attrs {
     }
 
     pub fn docs(&self) -> Option<Documentation> {
-        let docs = self.by_key("doc").attrs().flat_map(|attr| match attr.input.as_ref()? {
+        let docs = self.by_key("doc").attrs().flat_map(|attr| match attr.input.as_deref()? {
             AttrInput::Literal(s) => Some(s),
             AttrInput::TokenTree(_) => None,
         });
@@ -454,7 +454,7 @@ impl AttrsWithOwner {
         db: &dyn DefDatabase,
     ) -> Option<(Documentation, DocsRangeMap)> {
         // FIXME: code duplication in `docs` above
-        let docs = self.by_key("doc").attrs().flat_map(|attr| match attr.input.as_ref()? {
+        let docs = self.by_key("doc").attrs().flat_map(|attr| match attr.input.as_deref()? {
             AttrInput::Literal(s) => Some((s, attr.id)),
             AttrInput::TokenTree(_) => None,
         });
@@ -637,10 +637,10 @@ pub(crate) struct AttrId {
 pub struct Attr {
     pub(crate) id: AttrId,
     pub(crate) path: Interned<ModPath>,
-    pub(crate) input: Option<AttrInput>,
+    pub(crate) input: Option<Interned<AttrInput>>,
 }
 
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum AttrInput {
     /// `#[attr = "string"]`
     Literal(SmolStr),
@@ -670,9 +670,9 @@ impl Attr {
                 ast::LiteralKind::String(string) => string.value()?.into(),
                 _ => lit.syntax().first_token()?.text().trim_matches('"').into(),
             };
-            Some(AttrInput::Literal(value))
+            Some(Interned::new(AttrInput::Literal(value)))
         } else if let Some(tt) = ast.token_tree() {
-            Some(AttrInput::TokenTree(ast_to_token_tree(&tt).0))
+            Some(Interned::new(AttrInput::TokenTree(ast_to_token_tree(&tt).0)))
         } else {
             None
         };
@@ -688,7 +688,7 @@ impl Attr {
             return None;
         }
 
-        match &self.input {
+        match self.input.as_deref() {
             Some(AttrInput::TokenTree(args)) => {
                 let mut counter = 0;
                 let paths = args
@@ -720,7 +720,7 @@ impl Attr {
     }
 
     pub fn string_value(&self) -> Option<&SmolStr> {
-        match self.input.as_ref()? {
+        match self.input.as_deref()? {
             AttrInput::Literal(it) => Some(it),
             _ => None,
         }
@@ -735,14 +735,14 @@ pub struct AttrQuery<'a> {
 
 impl<'a> AttrQuery<'a> {
     pub fn tt_values(self) -> impl Iterator<Item = &'a Subtree> {
-        self.attrs().filter_map(|attr| match attr.input.as_ref()? {
+        self.attrs().filter_map(|attr| match attr.input.as_deref()? {
             AttrInput::TokenTree(it) => Some(it),
             _ => None,
         })
     }
 
     pub fn string_value(self) -> Option<&'a SmolStr> {
-        self.attrs().find_map(|attr| match attr.input.as_ref()? {
+        self.attrs().find_map(|attr| match attr.input.as_deref()? {
             AttrInput::Literal(it) => Some(it),
             _ => None,
         })
diff --git a/crates/hir_def/src/data.rs b/crates/hir_def/src/data.rs
index 135a6698e..8bcac60ef 100644
--- a/crates/hir_def/src/data.rs
+++ b/crates/hir_def/src/data.rs
@@ -112,7 +112,7 @@ pub struct TypeAliasData {
     pub visibility: RawVisibility,
     pub is_extern: bool,
     /// Bounds restricting the type alias itself (eg. `type Ty: Bound;` in a trait or impl).
-    pub bounds: Vec<TypeBound>,
+    pub bounds: Vec<Interned<TypeBound>>,
 }
 
 impl TypeAliasData {
@@ -141,7 +141,7 @@ pub struct TraitData {
     pub is_auto: bool,
     pub is_unsafe: bool,
     pub visibility: RawVisibility,
-    pub bounds: Box<[TypeBound]>,
+    pub bounds: Box<[Interned<TypeBound>]>,
 }
 
 impl TraitData {
diff --git a/crates/hir_def/src/generics.rs b/crates/hir_def/src/generics.rs
index de5acced8..44d22b918 100644
--- a/crates/hir_def/src/generics.rs
+++ b/crates/hir_def/src/generics.rs
@@ -68,9 +68,19 @@ pub struct GenericParams {
 /// associated type bindings like `Iterator<Item = u32>`.
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub enum WherePredicate {
-    TypeBound { target: WherePredicateTypeTarget, bound: TypeBound },
-    Lifetime { target: LifetimeRef, bound: LifetimeRef },
-    ForLifetime { lifetimes: Box<[Name]>, target: WherePredicateTypeTarget, bound: TypeBound },
+    TypeBound {
+        target: WherePredicateTypeTarget,
+        bound: Interned<TypeBound>,
+    },
+    Lifetime {
+        target: LifetimeRef,
+        bound: LifetimeRef,
+    },
+    ForLifetime {
+        lifetimes: Box<[Name]>,
+        target: WherePredicateTypeTarget,
+        bound: Interned<TypeBound>,
+    },
 }
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -339,11 +349,11 @@ impl GenericParams {
                 Some(hrtb_lifetimes) => WherePredicate::ForLifetime {
                     lifetimes: hrtb_lifetimes.clone(),
                     target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
-                    bound,
+                    bound: Interned::new(bound),
                 },
                 None => WherePredicate::TypeBound {
                     target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
-                    bound,
+                    bound: Interned::new(bound),
                 },
             },
             (Either::Right(lifetime), TypeBound::Lifetime(bound)) => {
diff --git a/crates/hir_def/src/intern.rs b/crates/hir_def/src/intern.rs
index 5cc7f2df6..79ba970e7 100644
--- a/crates/hir_def/src/intern.rs
+++ b/crates/hir_def/src/intern.rs
@@ -216,7 +216,10 @@ pub use crate::_impl_internable as impl_internable;
 impl_internable!(
     crate::type_ref::TypeRef,
     crate::type_ref::TraitRef,
+    crate::type_ref::TypeBound,
     crate::path::ModPath,
+    crate::path::GenericArgs,
+    crate::attr::AttrInput,
     GenericParams,
     str,
 );
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index 528270d49..11767d100 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -1,4 +1,34 @@
 //! A simplified AST that only contains items.
+//!
+//! This is the primary IR used throughout `hir_def`. It is the input to the name resolution
+//! algorithm, as well as to the queries defined in `adt.rs`, `data.rs`, and most things in
+//! `attr.rs`.
+//!
+//! `ItemTree`s are built per `HirFileId`, from the syntax tree of the parsed file. This means that
+//! they are crate-independent: they don't know which `#[cfg]`s are active or which module they
+//! belong to, since those concepts don't exist at this level (a single `ItemTree` might be part of
+//! multiple crates, or might be included into the same crate twice via `#[path]`).
+//!
+//! One important purpose of this layer is to provide an "invalidation barrier" for incremental
+//! computations: when typing inside an item body, the `ItemTree` of the modified file is typically
+//! unaffected, so we don't have to recompute name resolution results or item data (see `data.rs`).
+//!
+//! The `ItemTree` for the currently open file can be displayed by using the VS Code command
+//! "Rust Analyzer: Debug ItemTree".
+//!
+//! Compared to rustc's architecture, `ItemTree` has properties from both rustc's AST and HIR: many
+//! syntax-level Rust features are already desugared to simpler forms in the `ItemTree`, but name
+//! resolution has not yet been performed. `ItemTree`s are per-file, while rustc's AST and HIR are
+//! per-crate, because we are interested in incrementally computing it.
+//!
+//! The representation of items in the `ItemTree` should generally mirror the surface syntax: it is
+//! usually a bad idea to desugar a syntax-level construct to something that is structurally
+//! different here. Name resolution needs to be able to process attributes and expand macros
+//! (including attribute macros), and having a 1-to-1 mapping between syntax and the `ItemTree`
+//! avoids introducing subtle bugs.
+//!
+//! In general, any item in the `ItemTree` stores its `AstId`, which allows mapping it back to its
+//! surface syntax.
 
 mod lower;
 mod pretty;
@@ -500,8 +530,8 @@ pub struct Import {
     pub alias: Option<ImportAlias>,
     pub visibility: RawVisibilityId,
     pub is_glob: bool,
-    /// AST ID of the `use` or `extern crate` item this import was derived from. Note that many
-    /// `Import`s can map to the same `use` item.
+    /// AST ID of the `use` item this import was derived from. Note that many `Import`s can map to
+    /// the same `use` item.
     pub ast_id: FileAstId<ast::Use>,
     /// Index of this `Import` when the containing `Use` is visited via `ModPath::expand_use_item`.
     ///
@@ -614,7 +644,7 @@ pub struct Trait {
     pub generic_params: Interned<GenericParams>,
     pub is_auto: bool,
     pub is_unsafe: bool,
-    pub bounds: Box<[TypeBound]>,
+    pub bounds: Box<[Interned<TypeBound>]>,
     pub items: Box<[AssocItem]>,
     pub ast_id: FileAstId<ast::Trait>,
 }
@@ -634,7 +664,7 @@ pub struct TypeAlias {
     pub name: Name,
     pub visibility: RawVisibilityId,
     /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
-    pub bounds: Box<[TypeBound]>,
+    pub bounds: Box<[Interned<TypeBound>]>,
     pub generic_params: Interned<GenericParams>,
     pub type_ref: Option<Interned<TypeRef>>,
     pub is_extern: bool,
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index 91cf75371..b4389371f 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -384,7 +384,7 @@ impl<'a> Ctx<'a> {
 
         let ret_type = if func.async_token().is_some() {
             let future_impl = desugar_future_path(ret_type);
-            let ty_bound = TypeBound::Path(future_impl);
+            let ty_bound = Interned::new(TypeBound::Path(future_impl));
             TypeRef::ImplTrait(vec![ty_bound])
         } else {
             ret_type
@@ -738,11 +738,12 @@ impl<'a> Ctx<'a> {
         Interned::new(generics)
     }
 
-    fn lower_type_bounds(&mut self, node: &impl ast::TypeBoundsOwner) -> Vec<TypeBound> {
+    fn lower_type_bounds(&mut self, node: &impl ast::TypeBoundsOwner) -> Vec<Interned<TypeBound>> {
         match node.type_bound_list() {
-            Some(bound_list) => {
-                bound_list.bounds().map(|it| TypeBound::from_ast(&self.body_ctx, it)).collect()
-            }
+            Some(bound_list) => bound_list
+                .bounds()
+                .map(|it| Interned::new(TypeBound::from_ast(&self.body_ctx, it)))
+                .collect(),
             None => Vec::new(),
         }
     }
@@ -810,7 +811,7 @@ fn desugar_future_path(orig: TypeRef) -> Path {
     let binding =
         AssociatedTypeBinding { name: name![Output], type_ref: Some(orig), bounds: Vec::new() };
     last.bindings.push(binding);
-    generic_args.push(Some(Arc::new(last)));
+    generic_args.push(Some(Interned::new(last)));
 
     Path::from_known_path(path, generic_args)
 }
diff --git a/crates/hir_def/src/item_tree/pretty.rs b/crates/hir_def/src/item_tree/pretty.rs
index 4bc87a0e2..9394a5de6 100644
--- a/crates/hir_def/src/item_tree/pretty.rs
+++ b/crates/hir_def/src/item_tree/pretty.rs
@@ -513,13 +513,13 @@ impl<'a> Printer<'a> {
         }
     }
 
-    fn print_type_bounds(&mut self, bounds: &[TypeBound]) {
+    fn print_type_bounds(&mut self, bounds: &[Interned<TypeBound>]) {
         for (i, bound) in bounds.iter().enumerate() {
             if i != 0 {
                 w!(self, " + ");
             }
 
-            match bound {
+            match bound.as_ref() {
                 TypeBound::Path(path) => self.print_path(path),
                 TypeBound::Lifetime(lt) => w!(self, "{}", lt.name),
                 TypeBound::Error => w!(self, "{{unknown}}"),
diff --git a/crates/hir_def/src/lib.rs b/crates/hir_def/src/lib.rs
index a82ea5957..70001cac8 100644
--- a/crates/hir_def/src/lib.rs
+++ b/crates/hir_def/src/lib.rs
@@ -485,6 +485,14 @@ impl VariantId {
             VariantId::UnionId(it) => it.lookup(db).id.file_id(),
         }
     }
+
+    pub fn adt_id(self) -> AdtId {
+        match self {
+            VariantId::EnumVariantId(it) => it.parent.into(),
+            VariantId::StructId(it) => it.into(),
+            VariantId::UnionId(it) => it.into(),
+        }
+    }
 }
 
 trait Intern {
diff --git a/crates/hir_def/src/nameres/collector.rs b/crates/hir_def/src/nameres/collector.rs
index 014ea4de4..2ae740d0e 100644
--- a/crates/hir_def/src/nameres/collector.rs
+++ b/crates/hir_def/src/nameres/collector.rs
@@ -285,7 +285,7 @@ impl DefCollector<'_> {
                 let registered_name = if *attr_name == hir_expand::name![register_attr]
                     || *attr_name == hir_expand::name![register_tool]
                 {
-                    match &attr.input {
+                    match attr.input.as_deref() {
                         Some(AttrInput::TokenTree(subtree)) => match &*subtree.token_trees {
                             [tt::TokenTree::Leaf(tt::Leaf::Ident(name))] => name.as_name(),
                             _ => continue,
diff --git a/crates/hir_def/src/path.rs b/crates/hir_def/src/path.rs
index 9b8873fd2..45ab9d0ff 100644
--- a/crates/hir_def/src/path.rs
+++ b/crates/hir_def/src/path.rs
@@ -4,7 +4,6 @@ mod lower;
 use std::{
     fmt::{self, Display},
     iter,
-    sync::Arc,
 };
 
 use crate::{body::LowerCtx, db::DefDatabase, intern::Interned, type_ref::LifetimeRef};
@@ -136,7 +135,7 @@ pub struct Path {
     type_anchor: Option<Interned<TypeRef>>,
     mod_path: Interned<ModPath>,
     /// Invariant: the same len as `self.mod_path.segments`
-    generic_args: Vec<Option<Arc<GenericArgs>>>,
+    generic_args: Vec<Option<Interned<GenericArgs>>>,
 }
 
 /// Generic arguments to a path segment (e.g. the `i32` in `Option<i32>`). This
@@ -165,7 +164,7 @@ pub struct AssociatedTypeBinding {
     /// Bounds for the associated type, like in `Iterator<Item:
     /// SomeOtherTrait>`. (This is the unstable `associated_type_bounds`
     /// feature.)
-    pub bounds: Vec<TypeBound>,
+    pub bounds: Vec<Interned<TypeBound>>,
 }
 
 /// A single generic argument.
@@ -185,7 +184,7 @@ impl Path {
     /// Converts a known mod path to `Path`.
     pub(crate) fn from_known_path(
         path: ModPath,
-        generic_args: Vec<Option<Arc<GenericArgs>>>,
+        generic_args: Vec<Option<Interned<GenericArgs>>>,
     ) -> Path {
         Path { type_anchor: None, mod_path: Interned::new(path), generic_args }
     }
@@ -239,7 +238,7 @@ pub struct PathSegment<'a> {
 
 pub struct PathSegments<'a> {
     segments: &'a [Name],
-    generic_args: &'a [Option<Arc<GenericArgs>>],
+    generic_args: &'a [Option<Interned<GenericArgs>>],
 }
 
 impl<'a> PathSegments<'a> {
diff --git a/crates/hir_def/src/path/lower.rs b/crates/hir_def/src/path/lower.rs
index a873325b2..5d5dd9c8f 100644
--- a/crates/hir_def/src/path/lower.rs
+++ b/crates/hir_def/src/path/lower.rs
@@ -3,7 +3,6 @@
 mod lower_use;
 
 use crate::intern::Interned;
-use std::sync::Arc;
 
 use either::Either;
 use hir_expand::name::{name, AsName};
@@ -48,7 +47,7 @@ pub(super) fn lower_path(mut path: ast::Path, ctx: &LowerCtx) -> Option<Path> {
                                     segment.ret_type(),
                                 )
                             })
-                            .map(Arc::new);
+                            .map(Interned::new);
                         segments.push(name);
                         generic_args.push(args)
                     }
@@ -87,13 +86,13 @@ pub(super) fn lower_path(mut path: ast::Path, ctx: &LowerCtx) -> Option<Path> {
                         // Insert the type reference (T in the above example) as Self parameter for the trait
                         let last_segment =
                             generic_args.iter_mut().rev().nth(num_segments.saturating_sub(1))?;
-                        if last_segment.is_none() {
-                            *last_segment = Some(Arc::new(GenericArgs::empty()));
+                        let mut args_inner = match last_segment {
+                            Some(it) => it.as_ref().clone(),
+                            None => GenericArgs::empty(),
                         };
-                        let args = last_segment.as_mut().unwrap();
-                        let mut args_inner = Arc::make_mut(args);
                         args_inner.has_self_type = true;
                         args_inner.args.insert(0, GenericArg::Type(self_type));
+                        *last_segment = Some(Interned::new(args_inner));
                     }
                 }
             }
@@ -171,7 +170,9 @@ pub(super) fn lower_generic_args(
                     let name = name_ref.as_name();
                     let type_ref = assoc_type_arg.ty().map(|it| TypeRef::from_ast(lower_ctx, it));
                     let bounds = if let Some(l) = assoc_type_arg.type_bound_list() {
-                        l.bounds().map(|it| TypeBound::from_ast(lower_ctx, it)).collect()
+                        l.bounds()
+                            .map(|it| Interned::new(TypeBound::from_ast(lower_ctx, it)))
+                            .collect()
                     } else {
                         Vec::new()
                     };
diff --git a/crates/hir_def/src/type_ref.rs b/crates/hir_def/src/type_ref.rs
index cdcab7110..cbde6b940 100644
--- a/crates/hir_def/src/type_ref.rs
+++ b/crates/hir_def/src/type_ref.rs
@@ -5,7 +5,7 @@ use hir_expand::{name::Name, AstId, InFile};
 use std::convert::TryInto;
 use syntax::ast;
 
-use crate::{body::LowerCtx, path::Path};
+use crate::{body::LowerCtx, intern::Interned, path::Path};
 
 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 pub enum Mutability {
@@ -91,8 +91,8 @@ pub enum TypeRef {
     /// A fn pointer. Last element of the vector is the return type.
     Fn(Vec<TypeRef>, bool /*varargs*/),
     // For
-    ImplTrait(Vec<TypeBound>),
-    DynTrait(Vec<TypeBound>),
+    ImplTrait(Vec<Interned<TypeBound>>),
+    DynTrait(Vec<Interned<TypeBound>>),
     Macro(AstId<ast::MacroCall>),
     Error,
 }
@@ -232,7 +232,7 @@ impl TypeRef {
                 | TypeRef::Slice(type_ref) => go(&type_ref, f),
                 TypeRef::ImplTrait(bounds) | TypeRef::DynTrait(bounds) => {
                     for bound in bounds {
-                        match bound {
+                        match bound.as_ref() {
                             TypeBound::Path(path) => go_path(path, f),
                             TypeBound::Lifetime(_) | TypeBound::Error => (),
                         }
@@ -262,7 +262,7 @@ impl TypeRef {
                             go(type_ref, f);
                         }
                         for bound in &binding.bounds {
-                            match bound {
+                            match bound.as_ref() {
                                 TypeBound::Path(path) => go_path(path, f),
                                 TypeBound::Lifetime(_) | TypeBound::Error => (),
                             }
@@ -277,9 +277,9 @@ impl TypeRef {
 pub(crate) fn type_bounds_from_ast(
     lower_ctx: &LowerCtx,
     type_bounds_opt: Option<ast::TypeBoundList>,
-) -> Vec<TypeBound> {
+) -> Vec<Interned<TypeBound>> {
     if let Some(type_bounds) = type_bounds_opt {
-        type_bounds.bounds().map(|it| TypeBound::from_ast(lower_ctx, it)).collect()
+        type_bounds.bounds().map(|it| Interned::new(TypeBound::from_ast(lower_ctx, it))).collect()
     } else {
         vec![]
     }