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! mod_items {
 227     ( $( $typ:ident in $fld:ident -> $ast:ty ),+ $(,)? ) => {
 228         #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 229         pub enum ModItem {
 230             $(
 231                 $typ(FileItemTreeId<$typ>),
 232             )+
 233         }
 234
 235         $(
 236             impl From<FileItemTreeId<$typ>> for ModItem {
 237                 fn from(id: FileItemTreeId<$typ>) -> ModItem {
 238                     ModItem::$typ(id)
 239                 }
 240             }
 241         )+
 242
 243         $(
 244             impl ItemTreeNode for $typ {
 245                 fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self {
 246                     &tree.$fld[index]
 247                 }
 248
 249                 fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>> {
 250                     if let ModItem::$typ(id) = mod_item {
 251                         Some(id)
 252                     } else {
 253                         None
 254                     }
 255                 }
 256
 257                 fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem {
 258                     ModItem::$typ(id)
 259                 }
 260             }
 261
 262             impl ItemTreeSource for $typ {
 263                 type Source = $ast;
 264
 265                 fn ast_id(&self) -> FileAstId<Self::Source> {
 266                     self.ast_id
 267                 }
 268             }
 269
 270             impl Index<Idx<$typ>> for ItemTree {
 271                 type Output = $typ;
 272
 273                 fn index(&self, index: Idx<$typ>) -> &Self::Output {
 274                     &self.$fld[index]
 275                 }
 276             }
 277         )+
 278     };
 279 }
 280
 281 mod_items! {
 282     Import in imports -> ast::UseItem,
 283     ExternCrate in extern_crates -> ast::ExternCrateItem,
 284     Function in functions -> ast::FnDef,
 285     Struct in structs -> ast::StructDef,
 286     Union in unions -> ast::UnionDef,
 287     Enum in enums -> ast::EnumDef,
 288     Const in consts -> ast::ConstDef,
 289     Static in statics -> ast::StaticDef,
 290     Trait in traits -> ast::TraitDef,
 291     Impl in impls -> ast::ImplDef,
 292     TypeAlias in type_aliases -> ast::TypeAliasDef,
 293     Mod in mods -> ast::Module,
 294     MacroCall in macro_calls -> ast::MacroCall,
 295 }
 296
 297 macro_rules! impl_index {
 298     ( $($fld:ident: $t:ty),+ $(,)? ) => {
 299         $(
 300             impl Index<Idx<$t>> for ItemTree {
 301                 type Output = $t;
 302
 303                 fn index(&self, index: Idx<$t>) -> &Self::Output {
 304                     &self.$fld[index]
 305                 }
 306             }
 307         )+
 308     };
 309 }
 310
 311 impl_index!(fields: Field, variants: Variant, exprs: Expr);
 312
 313 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
 314     type Output = N;
 315     fn index(&self, id: FileItemTreeId<N>) -> &N {
 316         N::lookup(self, id.index)
 317     }
 318 }
 319
 320 /// A desugared `use` import.
 321 #[derive(Debug, Clone, Eq, PartialEq)]
 322 pub struct Import {
 323     pub path: ModPath,
 324     pub alias: Option<ImportAlias>,
 325     pub visibility: RawVisibility,
 326     pub is_glob: bool,
 327     pub is_prelude: bool,
 328     /// AST ID of the `use` or `extern crate` item this import was derived from. Note that many
 329     /// `Import`s can map to the same `use` item.
 330     pub ast_id: FileAstId<ast::UseItem>,
 331 }
 332
 333 #[derive(Debug, Clone, Eq, PartialEq)]
 334 pub struct ExternCrate {
 335     pub path: ModPath,
 336     pub alias: Option<ImportAlias>,
 337     pub visibility: RawVisibility,
 338     /// Whether this is a `#[macro_use] extern crate ...`.
 339     pub is_macro_use: bool,
 340     pub ast_id: FileAstId<ast::ExternCrateItem>,
 341 }
 342
 343 #[derive(Debug, Clone, Eq, PartialEq)]
 344 pub struct Function {
 345     pub name: Name,
 346     pub visibility: RawVisibility,
 347     pub generic_params: GenericParams,
 348     pub has_self_param: bool,
 349     pub is_unsafe: bool,
 350     pub params: Vec<TypeRef>,
 351     pub ret_type: TypeRef,
 352     pub ast_id: FileAstId<ast::FnDef>,
 353 }
 354
 355 #[derive(Debug, Clone, Eq, PartialEq)]
 356 pub struct Struct {
 357     pub name: Name,
 358     pub visibility: RawVisibility,
 359     pub generic_params: GenericParams,
 360     pub fields: Fields,
 361     pub ast_id: FileAstId<ast::StructDef>,
 362     pub kind: StructDefKind,
 363 }
 364
 365 #[derive(Debug, Clone, Eq, PartialEq)]
 366 pub enum StructDefKind {
 367     /// `struct S { ... }` - type namespace only.
 368     Record,
 369     /// `struct S(...);`
 370     Tuple,
 371     /// `struct S;`
 372     Unit,
 373 }
 374
 375 #[derive(Debug, Clone, Eq, PartialEq)]
 376 pub struct Union {
 377     pub name: Name,
 378     pub visibility: RawVisibility,
 379     pub generic_params: GenericParams,
 380     pub fields: Fields,
 381     pub ast_id: FileAstId<ast::UnionDef>,
 382 }
 383
 384 #[derive(Debug, Clone, Eq, PartialEq)]
 385 pub struct Enum {
 386     pub name: Name,
 387     pub visibility: RawVisibility,
 388     pub generic_params: GenericParams,
 389     pub variants: Range<Idx<Variant>>,
 390     pub ast_id: FileAstId<ast::EnumDef>,
 391 }
 392
 393 #[derive(Debug, Clone, Eq, PartialEq)]
 394 pub struct Const {
 395     /// const _: () = ();
 396     pub name: Option<Name>,
 397     pub visibility: RawVisibility,
 398     pub type_ref: TypeRef,
 399     pub ast_id: FileAstId<ast::ConstDef>,
 400 }
 401
 402 #[derive(Debug, Clone, Eq, PartialEq)]
 403 pub struct Static {
 404     pub name: Name,
 405     pub visibility: RawVisibility,
 406     pub mutable: bool,
 407     pub type_ref: TypeRef,
 408     pub ast_id: FileAstId<ast::StaticDef>,
 409 }
 410
 411 #[derive(Debug, Clone, Eq, PartialEq)]
 412 pub struct Trait {
 413     pub name: Name,
 414     pub visibility: RawVisibility,
 415     pub generic_params: GenericParams,
 416     pub auto: bool,
 417     pub items: Vec<AssocItem>,
 418     pub ast_id: FileAstId<ast::TraitDef>,
 419 }
 420
 421 #[derive(Debug, Clone, Eq, PartialEq)]
 422 pub struct Impl {
 423     pub generic_params: GenericParams,
 424     pub target_trait: Option<TypeRef>,
 425     pub target_type: TypeRef,
 426     pub is_negative: bool,
 427     pub items: Vec<AssocItem>,
 428     pub ast_id: FileAstId<ast::ImplDef>,
 429 }
 430
 431 #[derive(Debug, Clone, PartialEq, Eq)]
 432 pub struct TypeAlias {
 433     pub name: Name,
 434     pub visibility: RawVisibility,
 435     /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
 436     pub bounds: Vec<TypeBound>,
 437     pub generic_params: GenericParams,
 438     pub type_ref: Option<TypeRef>,
 439     pub ast_id: FileAstId<ast::TypeAliasDef>,
 440 }
 441
 442 #[derive(Debug, Clone, Eq, PartialEq)]
 443 pub struct Mod {
 444     pub name: Name,
 445     pub visibility: RawVisibility,
 446     pub kind: ModKind,
 447     pub ast_id: FileAstId<ast::Module>,
 448 }
 449
 450 #[derive(Debug, Clone, Eq, PartialEq)]
 451 pub enum ModKind {
 452     /// `mod m { ... }`
 453     Inline { items: Vec<ModItem> },
 454
 455     /// `mod m;`
 456     Outline {},
 457 }
 458
 459 #[derive(Debug, Clone, Eq, PartialEq)]
 460 pub struct MacroCall {
 461     /// For `macro_rules!` declarations, this is the name of the declared macro.
 462     pub name: Option<Name>,
 463     /// Path to the called macro.
 464     pub path: ModPath,
 465     /// Has `#[macro_export]`.
 466     pub is_export: bool,
 467     /// Has `#[macro_export(local_inner_macros)]`.
 468     pub is_local_inner: bool,
 469     /// Has `#[rustc_builtin_macro]`.
 470     pub is_builtin: bool,
 471     pub ast_id: FileAstId<ast::MacroCall>,
 472 }
 473
 474 // NB: There's no `FileAstId` for `Expr`. The only case where this would be useful is for array
 475 // lengths, but we don't do much with them yet.
 476 #[derive(Debug, Clone, Eq, PartialEq)]
 477 pub struct Expr;
 478
 479 macro_rules! impl_froms {
 480     ($e:ident { $($v:ident ($t:ty)),* $(,)? }) => {
 481         $(
 482             impl From<$t> for $e {
 483                 fn from(it: $t) -> $e {
 484                     $e::$v(it)
 485                 }
 486             }
 487         )*
 488     }
 489 }
 490
 491 impl ModItem {
 492     pub fn as_assoc_item(&self) -> Option<AssocItem> {
 493         match self {
 494             ModItem::Import(_)
 495             | ModItem::ExternCrate(_)
 496             | ModItem::Struct(_)
 497             | ModItem::Union(_)
 498             | ModItem::Enum(_)
 499             | ModItem::Static(_)
 500             | ModItem::Trait(_)
 501             | ModItem::Impl(_)
 502             | ModItem::Mod(_) => None,
 503             ModItem::MacroCall(call) => Some(AssocItem::MacroCall(*call)),
 504             ModItem::Const(konst) => Some(AssocItem::Const(*konst)),
 505             ModItem::TypeAlias(alias) => Some(AssocItem::TypeAlias(*alias)),
 506             ModItem::Function(func) => Some(AssocItem::Function(*func)),
 507         }
 508     }
 509
 510     pub fn downcast<N: ItemTreeNode>(self) -> Option<FileItemTreeId<N>> {
 511         N::id_from_mod_item(self)
 512     }
 513 }
 514
 515 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 516 pub enum AssocItem {
 517     Function(FileItemTreeId<Function>),
 518     TypeAlias(FileItemTreeId<TypeAlias>),
 519     Const(FileItemTreeId<Const>),
 520     MacroCall(FileItemTreeId<MacroCall>),
 521 }
 522
 523 impl_froms!(AssocItem {
 524     Function(FileItemTreeId<Function>),
 525     TypeAlias(FileItemTreeId<TypeAlias>),
 526     Const(FileItemTreeId<Const>),
 527     MacroCall(FileItemTreeId<MacroCall>),
 528 });
 529
 530 impl From<AssocItem> for ModItem {
 531     fn from(item: AssocItem) -> Self {
 532         match item {
 533             AssocItem::Function(it) => it.into(),
 534             AssocItem::TypeAlias(it) => it.into(),
 535             AssocItem::Const(it) => it.into(),
 536             AssocItem::MacroCall(it) => it.into(),
 537         }
 538     }
 539 }
 540
 541 #[derive(Debug, Eq, PartialEq)]
 542 pub struct Variant {
 543     pub name: Name,
 544     pub fields: Fields,
 545 }
 546
 547 #[derive(Debug, Clone, PartialEq, Eq)]
 548 pub enum Fields {
 549     Record(Range<Idx<Field>>),
 550     Tuple(Range<Idx<Field>>),
 551     Unit,
 552 }
 553
 554 /// A single field of an enum variant or struct
 555 #[derive(Debug, Clone, PartialEq, Eq)]
 556 pub struct Field {
 557     pub name: Name,
 558     pub type_ref: TypeRef,
 559     pub visibility: RawVisibility,
 560 }