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