crates/ra_hir_def/src/item_tree.rs

   1 //! A simplified AST that only contains items.
   2
   3 mod lower;
   4 #[cfg(test)]
   5 mod tests;
   6
   7 use std::{
   8     fmt::{self, Debug},
   9     hash::{Hash, Hasher},
  10     marker::PhantomData,
  11     ops::{Index, Range},
  12     sync::Arc,
  13 };
  14
  15 use ast::{AstNode, AttrsOwner, NameOwner, StructKind, TypeAscriptionOwner};
  16 use either::Either;
  17 use hir_expand::{
  18     ast_id_map::FileAstId,
  19     hygiene::Hygiene,
  20     name::{name, AsName, Name},
  21     HirFileId, InFile,
  22 };
  23 use ra_arena::{Arena, Idx, RawId};
  24 use ra_syntax::{ast, match_ast};
  25 use rustc_hash::FxHashMap;
  26 use test_utils::mark;
  27
  28 use crate::{
  29     attr::Attrs,
  30     db::DefDatabase,
  31     generics::GenericParams,
  32     path::{path, AssociatedTypeBinding, GenericArgs, ImportAlias, ModPath, Path},
  33     type_ref::{Mutability, TypeBound, TypeRef},
  34     visibility::RawVisibility,
  35 };
  36 use smallvec::SmallVec;
  37
  38 /// The item tree of a source file.
  39 #[derive(Debug, Eq, PartialEq)]
  40 pub struct ItemTree {
  41     file_id: HirFileId,
  42     top_level: Vec<ModItem>,
  43     top_attrs: Attrs,
  44     attrs: FxHashMap<ModItem, Attrs>,
  45     empty_attrs: Attrs,
  46     inner_items: FxHashMap<FileAstId<ast::ModuleItem>, SmallVec<[ModItem; 1]>>,
  47
  48     imports: Arena<Import>,
  49     extern_crates: Arena<ExternCrate>,
  50     functions: Arena<Function>,
  51     structs: Arena<Struct>,
  52     fields: Arena<Field>,
  53     unions: Arena<Union>,
  54     enums: Arena<Enum>,
  55     variants: Arena<Variant>,
  56     consts: Arena<Const>,
  57     statics: Arena<Static>,
  58     traits: Arena<Trait>,
  59     impls: Arena<Impl>,
  60     type_aliases: Arena<TypeAlias>,
  61     mods: Arena<Mod>,
  62     macro_calls: Arena<MacroCall>,
  63     exprs: Arena<Expr>,
  64 }
  65
  66 impl ItemTree {
  67     pub fn item_tree_query(db: &dyn DefDatabase, file_id: HirFileId) -> Arc<ItemTree> {
  68         let _p = ra_prof::profile("item_tree_query").detail(|| format!("{:?}", file_id));
  69         let syntax = if let Some(node) = db.parse_or_expand(file_id) {
  70             node
  71         } else {
  72             return Arc::new(Self::empty(file_id));
  73         };
  74
  75         let hygiene = Hygiene::new(db.upcast(), file_id);
  76         let ctx = lower::Ctx::new(db, hygiene.clone(), file_id);
  77         let mut top_attrs = None;
  78         let mut item_tree = match_ast! {
  79             match syntax {
  80                 ast::SourceFile(file) => {
  81                     top_attrs = Some(Attrs::new(&file, &hygiene));
  82                     ctx.lower_module_items(&file)
  83                 },
  84                 ast::MacroItems(items) => {
  85                     ctx.lower_module_items(&items)
  86                 },
  87                 // Macros can expand to expressions. We return an empty item tree in this case, but
  88                 // still need to collect inner items.
  89                 ast::Expr(e) => {
  90                     ctx.lower_inner_items(e.syntax())
  91                 },
  92                 _ => {
  93                     panic!("cannot create item tree from {:?}", syntax);
  94                 },
  95             }
  96         };
  97
  98         item_tree.top_attrs = top_attrs.unwrap_or_default();
  99         Arc::new(item_tree)
 100     }
 101
 102     fn empty(file_id: HirFileId) -> Self {
 103         Self {
 104             file_id,
 105             top_level: Default::default(),
 106             top_attrs: Default::default(),
 107             attrs: Default::default(),
 108             empty_attrs: Default::default(),
 109             inner_items: Default::default(),
 110             imports: Default::default(),
 111             extern_crates: Default::default(),
 112             functions: Default::default(),
 113             structs: Default::default(),
 114             fields: Default::default(),
 115             unions: Default::default(),
 116             enums: Default::default(),
 117             variants: Default::default(),
 118             consts: Default::default(),
 119             statics: Default::default(),
 120             traits: Default::default(),
 121             impls: Default::default(),
 122             type_aliases: Default::default(),
 123             mods: Default::default(),
 124             macro_calls: Default::default(),
 125             exprs: Default::default(),
 126         }
 127     }
 128
 129     /// Returns an iterator over all items located at the top level of the `HirFileId` this
 130     /// `ItemTree` was created from.
 131     pub fn top_level_items(&self) -> &[ModItem] {
 132         &self.top_level
 133     }
 134
 135     /// Returns the inner attributes of the source file.
 136     pub fn top_level_attrs(&self) -> &Attrs {
 137         &self.top_attrs
 138     }
 139
 140     pub fn attrs(&self, of: ModItem) -> &Attrs {
 141         self.attrs.get(&of).unwrap_or(&self.empty_attrs)
 142     }
 143
 144     /// Returns the lowered inner items that `ast` corresponds to.
 145     ///
 146     /// Most AST items are lowered to a single `ModItem`, but some (eg. `use` items) may be lowered
 147     /// to multiple items in the `ItemTree`.
 148     pub fn inner_items(&self, ast: FileAstId<ast::ModuleItem>) -> &[ModItem] {
 149         &self.inner_items[&ast]
 150     }
 151
 152     pub fn all_inner_items(&self) -> impl Iterator<Item = ModItem> + '_ {
 153         self.inner_items.values().flatten().copied()
 154     }
 155
 156     pub fn source<S: ItemTreeSource>(
 157         &self,
 158         db: &dyn DefDatabase,
 159         of: FileItemTreeId<S>,
 160     ) -> S::Source {
 161         // This unwrap cannot fail, since it has either succeeded above, or resulted in an empty
 162         // ItemTree (in which case there is no valid `FileItemTreeId` to call this method with).
 163         let root = db
 164             .parse_or_expand(self.file_id)
 165             .expect("parse_or_expand failed on constructed ItemTree");
 166
 167         let id = self[of].ast_id();
 168         let map = db.ast_id_map(self.file_id);
 169         let ptr = map.get(id);
 170         ptr.to_node(&root)
 171     }
 172 }
 173
 174 /// Trait implemented by all nodes in the item tree.
 175 pub trait ItemTreeNode: Clone {
 176     /// Looks up an instance of `Self` in an item tree.
 177     fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self;
 178
 179     /// Downcasts a `ModItem` to a `FileItemTreeId` specific to this type.
 180     fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>>;
 181
 182     /// Upcasts a `FileItemTreeId` to a generic `ModItem`.
 183     fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem;
 184 }
 185
 186 /// Trait for item tree nodes that allow accessing the original AST node.
 187 pub trait ItemTreeSource: ItemTreeNode {
 188     type Source: AstNode + Into<ast::ModuleItem>;
 189
 190     fn ast_id(&self) -> FileAstId<Self::Source>;
 191 }
 192
 193 pub struct FileItemTreeId<N: ItemTreeNode> {
 194     index: Idx<N>,
 195     _p: PhantomData<N>,
 196 }
 197
 198 impl<N: ItemTreeNode> Clone for FileItemTreeId<N> {
 199     fn clone(&self) -> Self {
 200         Self { index: self.index, _p: PhantomData }
 201     }
 202 }
 203 impl<N: ItemTreeNode> Copy for FileItemTreeId<N> {}
 204
 205 impl<N: ItemTreeNode> PartialEq for FileItemTreeId<N> {
 206     fn eq(&self, other: &FileItemTreeId<N>) -> bool {
 207         self.index == other.index
 208     }
 209 }
 210 impl<N: ItemTreeNode> Eq for FileItemTreeId<N> {}
 211
 212 impl<N: ItemTreeNode> Hash for FileItemTreeId<N> {
 213     fn hash<H: Hasher>(&self, state: &mut H) {
 214         self.index.hash(state)
 215     }
 216 }
 217
 218 impl<N: ItemTreeNode> fmt::Debug for FileItemTreeId<N> {
 219     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 220         self.index.fmt(f)
 221     }
 222 }
 223
 224 pub type ItemTreeId<N> = InFile<FileItemTreeId<N>>;
 225
 226 macro_rules! nodes {
 227     ( $($node:ident in $fld:ident),+ $(,)? ) => { $(
 228         impl ItemTreeNode for $node {
 229             fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self {
 230                 &tree.$fld[index]
 231             }
 232
 233
 234             fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>> {
 235                 if let ModItem::$node(id) = mod_item {
 236                     Some(id)
 237                 } else {
 238                     None
 239                 }
 240             }
 241
 242             fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem {
 243                 ModItem::$node(id)
 244             }
 245         }
 246     )+ };
 247 }
 248
 249 nodes!(
 250     Import in imports,
 251     ExternCrate in extern_crates,
 252     Function in functions,
 253     Struct in structs,
 254     Union in unions,
 255     Enum in enums,
 256     Const in consts,
 257     Static in statics,
 258     Trait in traits,
 259     Impl in impls,
 260     TypeAlias in type_aliases,
 261     Mod in mods,
 262     MacroCall in macro_calls,
 263 );
 264
 265 macro_rules! source {
 266     ( $($node:ident -> $ast:path),+ $(,)? ) => { $(
 267         impl ItemTreeSource for $node {
 268             type Source = $ast;
 269
 270             fn ast_id(&self) -> FileAstId<Self::Source> {
 271                 self.ast_id
 272             }
 273         }
 274     )+ };
 275 }
 276
 277 source! {
 278     Import -> ast::UseItem,
 279     ExternCrate -> ast::ExternCrateItem,
 280     Function -> ast::FnDef,
 281     Struct -> ast::StructDef,
 282     Union -> ast::UnionDef,
 283     Enum -> ast::EnumDef,
 284     Const -> ast::ConstDef,
 285     Static -> ast::StaticDef,
 286     Trait -> ast::TraitDef,
 287     Impl -> ast::ImplDef,
 288     TypeAlias -> ast::TypeAliasDef,
 289     Mod -> ast::Module,
 290     MacroCall -> ast::MacroCall,
 291 }
 292
 293 macro_rules! impl_index {
 294     ( $($fld:ident: $t:ty),+ $(,)? ) => {
 295         $(
 296             impl Index<Idx<$t>> for ItemTree {
 297                 type Output = $t;
 298
 299                 fn index(&self, index: Idx<$t>) -> &Self::Output {
 300                     &self.$fld[index]
 301                 }
 302             }
 303         )+
 304     };
 305 }
 306
 307 impl_index!(
 308     imports: Import,
 309     functions: Function,
 310     structs: Struct,
 311     fields: Field,
 312     unions: Union,
 313     enums: Enum,
 314     variants: Variant,
 315     consts: Const,
 316     statics: Static,
 317     traits: Trait,
 318     impls: Impl,
 319     type_aliases: TypeAlias,
 320     mods: Mod,
 321     macro_calls: MacroCall,
 322     exprs: Expr,
 323 );
 324
 325 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
 326     type Output = N;
 327     fn index(&self, id: FileItemTreeId<N>) -> &N {
 328         N::lookup(self, id.index)
 329     }
 330 }
 331
 332 /// A desugared `use` import.
 333 #[derive(Debug, Clone, Eq, PartialEq)]
 334 pub struct Import {
 335     pub path: ModPath,
 336     pub alias: Option<ImportAlias>,
 337     pub visibility: RawVisibility,
 338     pub is_glob: bool,
 339     pub is_prelude: bool,
 340     /// AST ID of the `use` or `extern crate` item this import was derived from. Note that many
 341     /// `Import`s can map to the same `use` item.
 342     pub ast_id: FileAstId<ast::UseItem>,
 343 }
 344
 345 #[derive(Debug, Clone, Eq, PartialEq)]
 346 pub struct ExternCrate {
 347     pub path: ModPath,
 348     pub alias: Option<ImportAlias>,
 349     pub visibility: RawVisibility,
 350     /// Whether this is a `#[macro_use] extern crate ...`.
 351     pub is_macro_use: bool,
 352     pub ast_id: FileAstId<ast::ExternCrateItem>,
 353 }
 354
 355 #[derive(Debug, Clone, Eq, PartialEq)]
 356 pub struct Function {
 357     pub name: Name,
 358     pub visibility: RawVisibility,
 359     pub generic_params: GenericParams,
 360     pub has_self_param: bool,
 361     pub is_unsafe: bool,
 362     pub params: Vec<TypeRef>,
 363     pub ret_type: TypeRef,
 364     pub ast_id: FileAstId<ast::FnDef>,
 365 }
 366
 367 #[derive(Debug, Clone, Eq, PartialEq)]
 368 pub struct Struct {
 369     pub name: Name,
 370     pub visibility: RawVisibility,
 371     pub generic_params: GenericParams,
 372     pub fields: Fields,
 373     pub ast_id: FileAstId<ast::StructDef>,
 374     pub kind: StructDefKind,
 375 }
 376
 377 #[derive(Debug, Clone, Eq, PartialEq)]
 378 pub enum StructDefKind {
 379     /// `struct S { ... }` - type namespace only.
 380     Record,
 381     /// `struct S(...);`
 382     Tuple,
 383     /// `struct S;`
 384     Unit,
 385 }
 386
 387 #[derive(Debug, Clone, Eq, PartialEq)]
 388 pub struct Union {
 389     pub name: Name,
 390     pub visibility: RawVisibility,
 391     pub generic_params: GenericParams,
 392     pub fields: Fields,
 393     pub ast_id: FileAstId<ast::UnionDef>,
 394 }
 395
 396 #[derive(Debug, Clone, Eq, PartialEq)]
 397 pub struct Enum {
 398     pub name: Name,
 399     pub visibility: RawVisibility,
 400     pub generic_params: GenericParams,
 401     pub variants: Range<Idx<Variant>>,
 402     pub ast_id: FileAstId<ast::EnumDef>,
 403 }
 404
 405 #[derive(Debug, Clone, Eq, PartialEq)]
 406 pub struct Const {
 407     /// const _: () = ();
 408     pub name: Option<Name>,
 409     pub visibility: RawVisibility,
 410     pub type_ref: TypeRef,
 411     pub ast_id: FileAstId<ast::ConstDef>,
 412 }
 413
 414 #[derive(Debug, Clone, Eq, PartialEq)]
 415 pub struct Static {
 416     pub name: Name,
 417     pub visibility: RawVisibility,
 418     pub mutable: bool,
 419     pub type_ref: TypeRef,
 420     pub ast_id: FileAstId<ast::StaticDef>,
 421 }
 422
 423 #[derive(Debug, Clone, Eq, PartialEq)]
 424 pub struct Trait {
 425     pub name: Name,
 426     pub visibility: RawVisibility,
 427     pub generic_params: GenericParams,
 428     pub auto: bool,
 429     pub items: Vec<AssocItem>,
 430     pub ast_id: FileAstId<ast::TraitDef>,
 431 }
 432
 433 #[derive(Debug, Clone, Eq, PartialEq)]
 434 pub struct Impl {
 435     pub generic_params: GenericParams,
 436     pub target_trait: Option<TypeRef>,
 437     pub target_type: TypeRef,
 438     pub is_negative: bool,
 439     pub items: Vec<AssocItem>,
 440     pub ast_id: FileAstId<ast::ImplDef>,
 441 }
 442
 443 #[derive(Debug, Clone, PartialEq, Eq)]
 444 pub struct TypeAlias {
 445     pub name: Name,
 446     pub visibility: RawVisibility,
 447     /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
 448     pub bounds: Vec<TypeBound>,
 449     pub generic_params: GenericParams,
 450     pub type_ref: Option<TypeRef>,
 451     pub ast_id: FileAstId<ast::TypeAliasDef>,
 452 }
 453
 454 #[derive(Debug, Clone, Eq, PartialEq)]
 455 pub struct Mod {
 456     pub name: Name,
 457     pub visibility: RawVisibility,
 458     pub kind: ModKind,
 459     pub ast_id: FileAstId<ast::Module>,
 460 }
 461
 462 #[derive(Debug, Clone, Eq, PartialEq)]
 463 pub enum ModKind {
 464     /// `mod m { ... }`
 465     Inline { items: Vec<ModItem> },
 466
 467     /// `mod m;`
 468     Outline {},
 469 }
 470
 471 #[derive(Debug, Clone, Eq, PartialEq)]
 472 pub struct MacroCall {
 473     /// For `macro_rules!` declarations, this is the name of the declared macro.
 474     pub name: Option<Name>,
 475     /// Path to the called macro.
 476     pub path: ModPath,
 477     /// Has `#[macro_export]`.
 478     pub is_export: bool,
 479     /// Has `#[macro_export(local_inner_macros)]`.
 480     pub is_local_inner: bool,
 481     /// Has `#[rustc_builtin_macro]`.
 482     pub is_builtin: bool,
 483     pub ast_id: FileAstId<ast::MacroCall>,
 484 }
 485
 486 // NB: There's no `FileAstId` for `Expr`. The only case where this would be useful is for array
 487 // lengths, but we don't do much with them yet.
 488 #[derive(Debug, Clone, Eq, PartialEq)]
 489 pub struct Expr;
 490
 491 macro_rules! impl_froms {
 492     ($e:ident { $($v:ident ($t:ty)),* $(,)? }) => {
 493         $(
 494             impl From<$t> for $e {
 495                 fn from(it: $t) -> $e {
 496                     $e::$v(it)
 497                 }
 498             }
 499         )*
 500     }
 501 }
 502
 503 #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 504 pub enum ModItem {
 505     Import(FileItemTreeId<Import>),
 506     ExternCrate(FileItemTreeId<ExternCrate>),
 507     Function(FileItemTreeId<Function>),
 508     Struct(FileItemTreeId<Struct>),
 509     Union(FileItemTreeId<Union>),
 510     Enum(FileItemTreeId<Enum>),
 511     Const(FileItemTreeId<Const>),
 512     Static(FileItemTreeId<Static>),
 513     Trait(FileItemTreeId<Trait>),
 514     Impl(FileItemTreeId<Impl>),
 515     TypeAlias(FileItemTreeId<TypeAlias>),
 516     Mod(FileItemTreeId<Mod>),
 517     MacroCall(FileItemTreeId<MacroCall>),
 518 }
 519
 520 impl ModItem {
 521     pub fn as_assoc_item(&self) -> Option<AssocItem> {
 522         match self {
 523             ModItem::Import(_)
 524             | ModItem::ExternCrate(_)
 525             | ModItem::Struct(_)
 526             | ModItem::Union(_)
 527             | ModItem::Enum(_)
 528             | ModItem::Static(_)
 529             | ModItem::Trait(_)
 530             | ModItem::Impl(_)
 531             | ModItem::Mod(_) => None,
 532             ModItem::MacroCall(call) => Some(AssocItem::MacroCall(*call)),
 533             ModItem::Const(konst) => Some(AssocItem::Const(*konst)),
 534             ModItem::TypeAlias(alias) => Some(AssocItem::TypeAlias(*alias)),
 535             ModItem::Function(func) => Some(AssocItem::Function(*func)),
 536         }
 537     }
 538
 539     pub fn downcast<N: ItemTreeNode>(self) -> Option<FileItemTreeId<N>> {
 540         N::id_from_mod_item(self)
 541     }
 542 }
 543
 544 impl_froms!(ModItem {
 545     Import(FileItemTreeId<Import>),
 546     ExternCrate(FileItemTreeId<ExternCrate>),
 547     Function(FileItemTreeId<Function>),
 548     Struct(FileItemTreeId<Struct>),
 549     Union(FileItemTreeId<Union>),
 550     Enum(FileItemTreeId<Enum>),
 551     Const(FileItemTreeId<Const>),
 552     Static(FileItemTreeId<Static>),
 553     Trait(FileItemTreeId<Trait>),
 554     Impl(FileItemTreeId<Impl>),
 555     TypeAlias(FileItemTreeId<TypeAlias>),
 556     Mod(FileItemTreeId<Mod>),
 557     MacroCall(FileItemTreeId<MacroCall>),
 558 });
 559
 560 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 561 pub enum AssocItem {
 562     Function(FileItemTreeId<Function>),
 563     TypeAlias(FileItemTreeId<TypeAlias>),
 564     Const(FileItemTreeId<Const>),
 565     MacroCall(FileItemTreeId<MacroCall>),
 566 }
 567
 568 impl_froms!(AssocItem {
 569     Function(FileItemTreeId<Function>),
 570     TypeAlias(FileItemTreeId<TypeAlias>),
 571     Const(FileItemTreeId<Const>),
 572     MacroCall(FileItemTreeId<MacroCall>),
 573 });
 574
 575 impl From<AssocItem> for ModItem {
 576     fn from(item: AssocItem) -> Self {
 577         match item {
 578             AssocItem::Function(it) => it.into(),
 579             AssocItem::TypeAlias(it) => it.into(),
 580             AssocItem::Const(it) => it.into(),
 581             AssocItem::MacroCall(it) => it.into(),
 582         }
 583     }
 584 }
 585
 586 #[derive(Debug, Eq, PartialEq)]
 587 pub struct Variant {
 588     pub name: Name,
 589     pub fields: Fields,
 590 }
 591
 592 #[derive(Debug, Clone, PartialEq, Eq)]
 593 pub enum Fields {
 594     Record(Range<Idx<Field>>),
 595     Tuple(Range<Idx<Field>>),
 596     Unit,
 597 }
 598
 599 /// A single field of an enum variant or struct
 600 #[derive(Debug, Clone, PartialEq, Eq)]
 601 pub struct Field {
 602     pub name: Name,
 603     pub type_ref: TypeRef,
 604     pub visibility: RawVisibility,
 605 }