src/tools/rust-analyzer/crates/hir-def/src/item_tree.rs

   1 //! A simplified AST that only contains items.
   2 //!
   3 //! This is the primary IR used throughout `hir_def`. It is the input to the name resolution
   4 //! algorithm, as well as to the queries defined in `adt.rs`, `data.rs`, and most things in
   5 //! `attr.rs`.
   6 //!
   7 //! `ItemTree`s are built per `HirFileId`, from the syntax tree of the parsed file. This means that
   8 //! they are crate-independent: they don't know which `#[cfg]`s are active or which module they
   9 //! belong to, since those concepts don't exist at this level (a single `ItemTree` might be part of
  10 //! multiple crates, or might be included into the same crate twice via `#[path]`).
  11 //!
  12 //! One important purpose of this layer is to provide an "invalidation barrier" for incremental
  13 //! computations: when typing inside an item body, the `ItemTree` of the modified file is typically
  14 //! unaffected, so we don't have to recompute name resolution results or item data (see `data.rs`).
  15 //!
  16 //! The `ItemTree` for the currently open file can be displayed by using the VS Code command
  17 //! "rust-analyzer: Debug ItemTree".
  18 //!
  19 //! Compared to rustc's architecture, `ItemTree` has properties from both rustc's AST and HIR: many
  20 //! syntax-level Rust features are already desugared to simpler forms in the `ItemTree`, but name
  21 //! resolution has not yet been performed. `ItemTree`s are per-file, while rustc's AST and HIR are
  22 //! per-crate, because we are interested in incrementally computing it.
  23 //!
  24 //! The representation of items in the `ItemTree` should generally mirror the surface syntax: it is
  25 //! usually a bad idea to desugar a syntax-level construct to something that is structurally
  26 //! different here. Name resolution needs to be able to process attributes and expand macros
  27 //! (including attribute macros), and having a 1-to-1 mapping between syntax and the `ItemTree`
  28 //! avoids introducing subtle bugs.
  29 //!
  30 //! In general, any item in the `ItemTree` stores its `AstId`, which allows mapping it back to its
  31 //! surface syntax.
  32
  33 mod lower;
  34 mod pretty;
  35 #[cfg(test)]
  36 mod tests;
  37
  38 use std::{
  39     fmt::{self, Debug},
  40     hash::{Hash, Hasher},
  41     marker::PhantomData,
  42     ops::Index,
  43     sync::Arc,
  44 };
  45
  46 use ast::{AstNode, HasName, StructKind};
  47 use base_db::CrateId;
  48 use either::Either;
  49 use hir_expand::{
  50     ast_id_map::FileAstId,
  51     attrs::RawAttrs,
  52     hygiene::Hygiene,
  53     name::{name, AsName, Name},
  54     ExpandTo, HirFileId, InFile,
  55 };
  56 use intern::Interned;
  57 use la_arena::{Arena, Idx, IdxRange, RawIdx};
  58 use profile::Count;
  59 use rustc_hash::FxHashMap;
  60 use smallvec::SmallVec;
  61 use stdx::never;
  62 use syntax::{ast, match_ast, SyntaxKind};
  63
  64 use crate::{
  65     attr::Attrs,
  66     db::DefDatabase,
  67     generics::GenericParams,
  68     path::{path, AssociatedTypeBinding, GenericArgs, ImportAlias, ModPath, Path, PathKind},
  69     type_ref::{Mutability, TraitRef, TypeBound, TypeRef},
  70     visibility::RawVisibility,
  71     BlockId,
  72 };
  73
  74 #[derive(Copy, Clone, Eq, PartialEq)]
  75 pub struct RawVisibilityId(u32);
  76
  77 impl RawVisibilityId {
  78     pub const PUB: Self = RawVisibilityId(u32::max_value());
  79     pub const PRIV: Self = RawVisibilityId(u32::max_value() - 1);
  80     pub const PUB_CRATE: Self = RawVisibilityId(u32::max_value() - 2);
  81 }
  82
  83 impl fmt::Debug for RawVisibilityId {
  84     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  85         let mut f = f.debug_tuple("RawVisibilityId");
  86         match *self {
  87             Self::PUB => f.field(&"pub"),
  88             Self::PRIV => f.field(&"pub(self)"),
  89             Self::PUB_CRATE => f.field(&"pub(crate)"),
  90             _ => f.field(&self.0),
  91         };
  92         f.finish()
  93     }
  94 }
  95
  96 /// The item tree of a source file.
  97 #[derive(Debug, Default, Eq, PartialEq)]
  98 pub struct ItemTree {
  99     _c: Count<Self>,
 100
 101     top_level: SmallVec<[ModItem; 1]>,
 102     attrs: FxHashMap<AttrOwner, RawAttrs>,
 103
 104     data: Option<Box<ItemTreeData>>,
 105 }
 106
 107 impl ItemTree {
 108     pub(crate) fn file_item_tree_query(db: &dyn DefDatabase, file_id: HirFileId) -> Arc<ItemTree> {
 109         let _p = profile::span("file_item_tree_query").detail(|| format!("{file_id:?}"));
 110         let syntax = match db.parse_or_expand(file_id) {
 111             Some(node) => node,
 112             None => return Default::default(),
 113         };
 114         if never!(syntax.kind() == SyntaxKind::ERROR, "{:?} from {:?} {}", file_id, syntax, syntax)
 115         {
 116             // FIXME: not 100% sure why these crop up, but return an empty tree to avoid a panic
 117             return Default::default();
 118         }
 119
 120         let ctx = lower::Ctx::new(db, file_id);
 121         let mut top_attrs = None;
 122         let mut item_tree = match_ast! {
 123             match syntax {
 124                 ast::SourceFile(file) => {
 125                     top_attrs = Some(RawAttrs::new(db.upcast(), &file, ctx.hygiene()));
 126                     ctx.lower_module_items(&file)
 127                 },
 128                 ast::MacroItems(items) => {
 129                     ctx.lower_module_items(&items)
 130                 },
 131                 ast::MacroStmts(stmts) => {
 132                     // The produced statements can include items, which should be added as top-level
 133                     // items.
 134                     ctx.lower_macro_stmts(stmts)
 135                 },
 136                 _ => {
 137                     panic!("cannot create item tree for file {file_id:?} from {syntax:?} {syntax}");
 138                 },
 139             }
 140         };
 141
 142         if let Some(attrs) = top_attrs {
 143             item_tree.attrs.insert(AttrOwner::TopLevel, attrs);
 144         }
 145         item_tree.shrink_to_fit();
 146         Arc::new(item_tree)
 147     }
 148
 149     /// Returns an iterator over all items located at the top level of the `HirFileId` this
 150     /// `ItemTree` was created from.
 151     pub fn top_level_items(&self) -> &[ModItem] {
 152         &self.top_level
 153     }
 154
 155     /// Returns the inner attributes of the source file.
 156     pub fn top_level_attrs(&self, db: &dyn DefDatabase, krate: CrateId) -> Attrs {
 157         Attrs::filter(
 158             db,
 159             krate,
 160             self.attrs.get(&AttrOwner::TopLevel).unwrap_or(&RawAttrs::EMPTY).clone(),
 161         )
 162     }
 163
 164     pub(crate) fn raw_attrs(&self, of: AttrOwner) -> &RawAttrs {
 165         self.attrs.get(&of).unwrap_or(&RawAttrs::EMPTY)
 166     }
 167
 168     pub(crate) fn attrs(&self, db: &dyn DefDatabase, krate: CrateId, of: AttrOwner) -> Attrs {
 169         Attrs::filter(db, krate, self.raw_attrs(of).clone())
 170     }
 171
 172     pub fn pretty_print(&self) -> String {
 173         pretty::print_item_tree(self)
 174     }
 175
 176     fn data(&self) -> &ItemTreeData {
 177         self.data.as_ref().expect("attempted to access data of empty ItemTree")
 178     }
 179
 180     fn data_mut(&mut self) -> &mut ItemTreeData {
 181         self.data.get_or_insert_with(Box::default)
 182     }
 183
 184     fn block_item_tree(db: &dyn DefDatabase, block: BlockId) -> Arc<ItemTree> {
 185         let loc = db.lookup_intern_block(block);
 186         let block = loc.ast_id.to_node(db.upcast());
 187         let ctx = lower::Ctx::new(db, loc.ast_id.file_id);
 188         Arc::new(ctx.lower_block(&block))
 189     }
 190
 191     fn shrink_to_fit(&mut self) {
 192         if let Some(data) = &mut self.data {
 193             let ItemTreeData {
 194                 imports,
 195                 extern_crates,
 196                 extern_blocks,
 197                 functions,
 198                 params,
 199                 structs,
 200                 fields,
 201                 unions,
 202                 enums,
 203                 variants,
 204                 consts,
 205                 statics,
 206                 traits,
 207                 trait_aliases,
 208                 impls,
 209                 type_aliases,
 210                 mods,
 211                 macro_calls,
 212                 macro_rules,
 213                 macro_defs,
 214                 vis,
 215             } = &mut **data;
 216
 217             imports.shrink_to_fit();
 218             extern_crates.shrink_to_fit();
 219             extern_blocks.shrink_to_fit();
 220             functions.shrink_to_fit();
 221             params.shrink_to_fit();
 222             structs.shrink_to_fit();
 223             fields.shrink_to_fit();
 224             unions.shrink_to_fit();
 225             enums.shrink_to_fit();
 226             variants.shrink_to_fit();
 227             consts.shrink_to_fit();
 228             statics.shrink_to_fit();
 229             traits.shrink_to_fit();
 230             trait_aliases.shrink_to_fit();
 231             impls.shrink_to_fit();
 232             type_aliases.shrink_to_fit();
 233             mods.shrink_to_fit();
 234             macro_calls.shrink_to_fit();
 235             macro_rules.shrink_to_fit();
 236             macro_defs.shrink_to_fit();
 237
 238             vis.arena.shrink_to_fit();
 239         }
 240     }
 241 }
 242
 243 #[derive(Default, Debug, Eq, PartialEq)]
 244 struct ItemVisibilities {
 245     arena: Arena<RawVisibility>,
 246 }
 247
 248 impl ItemVisibilities {
 249     fn alloc(&mut self, vis: RawVisibility) -> RawVisibilityId {
 250         match &vis {
 251             RawVisibility::Public => RawVisibilityId::PUB,
 252             RawVisibility::Module(path) if path.segments().is_empty() => match &path.kind {
 253                 PathKind::Super(0) => RawVisibilityId::PRIV,
 254                 PathKind::Crate => RawVisibilityId::PUB_CRATE,
 255                 _ => RawVisibilityId(self.arena.alloc(vis).into_raw().into()),
 256             },
 257             _ => RawVisibilityId(self.arena.alloc(vis).into_raw().into()),
 258         }
 259     }
 260 }
 261
 262 static VIS_PUB: RawVisibility = RawVisibility::Public;
 263 static VIS_PRIV: RawVisibility = RawVisibility::Module(ModPath::from_kind(PathKind::Super(0)));
 264 static VIS_PUB_CRATE: RawVisibility = RawVisibility::Module(ModPath::from_kind(PathKind::Crate));
 265
 266 #[derive(Default, Debug, Eq, PartialEq)]
 267 struct ItemTreeData {
 268     imports: Arena<Import>,
 269     extern_crates: Arena<ExternCrate>,
 270     extern_blocks: Arena<ExternBlock>,
 271     functions: Arena<Function>,
 272     params: Arena<Param>,
 273     structs: Arena<Struct>,
 274     fields: Arena<Field>,
 275     unions: Arena<Union>,
 276     enums: Arena<Enum>,
 277     variants: Arena<Variant>,
 278     consts: Arena<Const>,
 279     statics: Arena<Static>,
 280     traits: Arena<Trait>,
 281     trait_aliases: Arena<TraitAlias>,
 282     impls: Arena<Impl>,
 283     type_aliases: Arena<TypeAlias>,
 284     mods: Arena<Mod>,
 285     macro_calls: Arena<MacroCall>,
 286     macro_rules: Arena<MacroRules>,
 287     macro_defs: Arena<MacroDef>,
 288
 289     vis: ItemVisibilities,
 290 }
 291
 292 #[derive(Debug, Eq, PartialEq, Hash)]
 293 pub enum AttrOwner {
 294     /// Attributes on an item.
 295     ModItem(ModItem),
 296     /// Inner attributes of the source file.
 297     TopLevel,
 298
 299     Variant(Idx<Variant>),
 300     Field(Idx<Field>),
 301     Param(Idx<Param>),
 302 }
 303
 304 macro_rules! from_attrs {
 305     ( $( $var:ident($t:ty) ),+ ) => {
 306         $(
 307             impl From<$t> for AttrOwner {
 308                 fn from(t: $t) -> AttrOwner {
 309                     AttrOwner::$var(t)
 310                 }
 311             }
 312         )+
 313     };
 314 }
 315
 316 from_attrs!(ModItem(ModItem), Variant(Idx<Variant>), Field(Idx<Field>), Param(Idx<Param>));
 317
 318 /// Trait implemented by all item nodes in the item tree.
 319 pub trait ItemTreeNode: Clone {
 320     type Source: AstNode + Into<ast::Item>;
 321
 322     fn ast_id(&self) -> FileAstId<Self::Source>;
 323
 324     /// Looks up an instance of `Self` in an item tree.
 325     fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self;
 326
 327     /// Downcasts a `ModItem` to a `FileItemTreeId` specific to this type.
 328     fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>>;
 329
 330     /// Upcasts a `FileItemTreeId` to a generic `ModItem`.
 331     fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem;
 332 }
 333
 334 pub struct FileItemTreeId<N: ItemTreeNode> {
 335     index: Idx<N>,
 336     _p: PhantomData<N>,
 337 }
 338
 339 impl<N: ItemTreeNode> Clone for FileItemTreeId<N> {
 340     fn clone(&self) -> Self {
 341         Self { index: self.index, _p: PhantomData }
 342     }
 343 }
 344 impl<N: ItemTreeNode> Copy for FileItemTreeId<N> {}
 345
 346 impl<N: ItemTreeNode> PartialEq for FileItemTreeId<N> {
 347     fn eq(&self, other: &FileItemTreeId<N>) -> bool {
 348         self.index == other.index
 349     }
 350 }
 351 impl<N: ItemTreeNode> Eq for FileItemTreeId<N> {}
 352
 353 impl<N: ItemTreeNode> Hash for FileItemTreeId<N> {
 354     fn hash<H: Hasher>(&self, state: &mut H) {
 355         self.index.hash(state)
 356     }
 357 }
 358
 359 impl<N: ItemTreeNode> fmt::Debug for FileItemTreeId<N> {
 360     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 361         self.index.fmt(f)
 362     }
 363 }
 364
 365 /// Identifies a particular [`ItemTree`].
 366 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
 367 pub struct TreeId {
 368     file: HirFileId,
 369     block: Option<BlockId>,
 370 }
 371
 372 impl TreeId {
 373     pub(crate) fn new(file: HirFileId, block: Option<BlockId>) -> Self {
 374         Self { file, block }
 375     }
 376
 377     pub(crate) fn item_tree(&self, db: &dyn DefDatabase) -> Arc<ItemTree> {
 378         match self.block {
 379             Some(block) => ItemTree::block_item_tree(db, block),
 380             None => db.file_item_tree(self.file),
 381         }
 382     }
 383
 384     pub(crate) fn file_id(self) -> HirFileId {
 385         self.file
 386     }
 387
 388     pub(crate) fn is_block(self) -> bool {
 389         self.block.is_some()
 390     }
 391 }
 392
 393 #[derive(Debug)]
 394 pub struct ItemTreeId<N: ItemTreeNode> {
 395     tree: TreeId,
 396     pub value: FileItemTreeId<N>,
 397 }
 398
 399 impl<N: ItemTreeNode> ItemTreeId<N> {
 400     pub fn new(tree: TreeId, idx: FileItemTreeId<N>) -> Self {
 401         Self { tree, value: idx }
 402     }
 403
 404     pub fn file_id(self) -> HirFileId {
 405         self.tree.file
 406     }
 407
 408     pub fn tree_id(self) -> TreeId {
 409         self.tree
 410     }
 411
 412     pub fn item_tree(self, db: &dyn DefDatabase) -> Arc<ItemTree> {
 413         self.tree.item_tree(db)
 414     }
 415 }
 416
 417 impl<N: ItemTreeNode> Copy for ItemTreeId<N> {}
 418 impl<N: ItemTreeNode> Clone for ItemTreeId<N> {
 419     fn clone(&self) -> Self {
 420         *self
 421     }
 422 }
 423
 424 impl<N: ItemTreeNode> PartialEq for ItemTreeId<N> {
 425     fn eq(&self, other: &Self) -> bool {
 426         self.tree == other.tree && self.value == other.value
 427     }
 428 }
 429
 430 impl<N: ItemTreeNode> Eq for ItemTreeId<N> {}
 431
 432 impl<N: ItemTreeNode> Hash for ItemTreeId<N> {
 433     fn hash<H: Hasher>(&self, state: &mut H) {
 434         self.tree.hash(state);
 435         self.value.hash(state);
 436     }
 437 }
 438
 439 macro_rules! mod_items {
 440     ( $( $typ:ident in $fld:ident -> $ast:ty ),+ $(,)? ) => {
 441         #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 442         pub enum ModItem {
 443             $(
 444                 $typ(FileItemTreeId<$typ>),
 445             )+
 446         }
 447
 448         $(
 449             impl From<FileItemTreeId<$typ>> for ModItem {
 450                 fn from(id: FileItemTreeId<$typ>) -> ModItem {
 451                     ModItem::$typ(id)
 452                 }
 453             }
 454         )+
 455
 456         $(
 457             impl ItemTreeNode for $typ {
 458                 type Source = $ast;
 459
 460                 fn ast_id(&self) -> FileAstId<Self::Source> {
 461                     self.ast_id
 462                 }
 463
 464                 fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self {
 465                     &tree.data().$fld[index]
 466                 }
 467
 468                 fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>> {
 469                     match mod_item {
 470                         ModItem::$typ(id) => Some(id),
 471                         _ => None,
 472                     }
 473                 }
 474
 475                 fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem {
 476                     ModItem::$typ(id)
 477                 }
 478             }
 479
 480             impl Index<Idx<$typ>> for ItemTree {
 481                 type Output = $typ;
 482
 483                 fn index(&self, index: Idx<$typ>) -> &Self::Output {
 484                     &self.data().$fld[index]
 485                 }
 486             }
 487         )+
 488     };
 489 }
 490
 491 mod_items! {
 492     Import in imports -> ast::Use,
 493     ExternCrate in extern_crates -> ast::ExternCrate,
 494     ExternBlock in extern_blocks -> ast::ExternBlock,
 495     Function in functions -> ast::Fn,
 496     Struct in structs -> ast::Struct,
 497     Union in unions -> ast::Union,
 498     Enum in enums -> ast::Enum,
 499     Const in consts -> ast::Const,
 500     Static in statics -> ast::Static,
 501     Trait in traits -> ast::Trait,
 502     TraitAlias in trait_aliases -> ast::TraitAlias,
 503     Impl in impls -> ast::Impl,
 504     TypeAlias in type_aliases -> ast::TypeAlias,
 505     Mod in mods -> ast::Module,
 506     MacroCall in macro_calls -> ast::MacroCall,
 507     MacroRules in macro_rules -> ast::MacroRules,
 508     MacroDef in macro_defs -> ast::MacroDef,
 509 }
 510
 511 macro_rules! impl_index {
 512     ( $($fld:ident: $t:ty),+ $(,)? ) => {
 513         $(
 514             impl Index<Idx<$t>> for ItemTree {
 515                 type Output = $t;
 516
 517                 fn index(&self, index: Idx<$t>) -> &Self::Output {
 518                     &self.data().$fld[index]
 519                 }
 520             }
 521         )+
 522     };
 523 }
 524
 525 impl_index!(fields: Field, variants: Variant, params: Param);
 526
 527 impl Index<RawVisibilityId> for ItemTree {
 528     type Output = RawVisibility;
 529     fn index(&self, index: RawVisibilityId) -> &Self::Output {
 530         match index {
 531             RawVisibilityId::PRIV => &VIS_PRIV,
 532             RawVisibilityId::PUB => &VIS_PUB,
 533             RawVisibilityId::PUB_CRATE => &VIS_PUB_CRATE,
 534             _ => &self.data().vis.arena[Idx::from_raw(index.0.into())],
 535         }
 536     }
 537 }
 538
 539 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
 540     type Output = N;
 541     fn index(&self, id: FileItemTreeId<N>) -> &N {
 542         N::lookup(self, id.index)
 543     }
 544 }
 545
 546 #[derive(Debug, Clone, Eq, PartialEq)]
 547 pub struct Import {
 548     pub visibility: RawVisibilityId,
 549     pub ast_id: FileAstId<ast::Use>,
 550     pub use_tree: UseTree,
 551 }
 552
 553 #[derive(Debug, Clone, Eq, PartialEq)]
 554 pub struct UseTree {
 555     pub index: Idx<ast::UseTree>,
 556     kind: UseTreeKind,
 557 }
 558
 559 #[derive(Debug, Clone, Eq, PartialEq)]
 560 pub enum UseTreeKind {
 561     /// ```
 562     /// use path::to::Item;
 563     /// use path::to::Item as Renamed;
 564     /// use path::to::Trait as _;
 565     /// ```
 566     Single { path: Interned<ModPath>, alias: Option<ImportAlias> },
 567
 568     /// ```
 569     /// use *;  // (invalid, but can occur in nested tree)
 570     /// use path::*;
 571     /// ```
 572     Glob { path: Option<Interned<ModPath>> },
 573
 574     /// ```
 575     /// use prefix::{self, Item, ...};
 576     /// ```
 577     Prefixed { prefix: Option<Interned<ModPath>>, list: Box<[UseTree]> },
 578 }
 579
 580 #[derive(Debug, Clone, Eq, PartialEq)]
 581 pub struct ExternCrate {
 582     pub name: Name,
 583     pub alias: Option<ImportAlias>,
 584     pub visibility: RawVisibilityId,
 585     pub ast_id: FileAstId<ast::ExternCrate>,
 586 }
 587
 588 #[derive(Debug, Clone, Eq, PartialEq)]
 589 pub struct ExternBlock {
 590     pub abi: Option<Interned<str>>,
 591     pub ast_id: FileAstId<ast::ExternBlock>,
 592     pub children: Box<[ModItem]>,
 593 }
 594
 595 #[derive(Debug, Clone, Eq, PartialEq)]
 596 pub struct Function {
 597     pub name: Name,
 598     pub visibility: RawVisibilityId,
 599     pub explicit_generic_params: Interned<GenericParams>,
 600     pub abi: Option<Interned<str>>,
 601     pub params: IdxRange<Param>,
 602     pub ret_type: Interned<TypeRef>,
 603     pub async_ret_type: Option<Interned<TypeRef>>,
 604     pub ast_id: FileAstId<ast::Fn>,
 605     pub(crate) flags: FnFlags,
 606 }
 607
 608 #[derive(Debug, Clone, Eq, PartialEq)]
 609 pub enum Param {
 610     Normal(Option<Name>, Interned<TypeRef>),
 611     Varargs,
 612 }
 613
 614 bitflags::bitflags! {
 615     #[derive(Default)]
 616     pub(crate) struct FnFlags: u8 {
 617         const HAS_SELF_PARAM = 1 << 0;
 618         const HAS_BODY = 1 << 1;
 619         const HAS_DEFAULT_KW = 1 << 2;
 620         const HAS_CONST_KW = 1 << 3;
 621         const HAS_ASYNC_KW = 1 << 4;
 622         const HAS_UNSAFE_KW = 1 << 5;
 623         const IS_VARARGS = 1 << 6;
 624     }
 625 }
 626
 627 #[derive(Debug, Clone, Eq, PartialEq)]
 628 pub struct Struct {
 629     pub name: Name,
 630     pub visibility: RawVisibilityId,
 631     pub generic_params: Interned<GenericParams>,
 632     pub fields: Fields,
 633     pub ast_id: FileAstId<ast::Struct>,
 634 }
 635
 636 #[derive(Debug, Clone, Eq, PartialEq)]
 637 pub struct Union {
 638     pub name: Name,
 639     pub visibility: RawVisibilityId,
 640     pub generic_params: Interned<GenericParams>,
 641     pub fields: Fields,
 642     pub ast_id: FileAstId<ast::Union>,
 643 }
 644
 645 #[derive(Debug, Clone, Eq, PartialEq)]
 646 pub struct Enum {
 647     pub name: Name,
 648     pub visibility: RawVisibilityId,
 649     pub generic_params: Interned<GenericParams>,
 650     pub variants: IdxRange<Variant>,
 651     pub ast_id: FileAstId<ast::Enum>,
 652 }
 653
 654 #[derive(Debug, Clone, Eq, PartialEq)]
 655 pub struct Const {
 656     /// `None` for `const _: () = ();`
 657     pub name: Option<Name>,
 658     pub visibility: RawVisibilityId,
 659     pub type_ref: Interned<TypeRef>,
 660     pub ast_id: FileAstId<ast::Const>,
 661 }
 662
 663 #[derive(Debug, Clone, Eq, PartialEq)]
 664 pub struct Static {
 665     pub name: Name,
 666     pub visibility: RawVisibilityId,
 667     pub mutable: bool,
 668     pub type_ref: Interned<TypeRef>,
 669     pub ast_id: FileAstId<ast::Static>,
 670 }
 671
 672 #[derive(Debug, Clone, Eq, PartialEq)]
 673 pub struct Trait {
 674     pub name: Name,
 675     pub visibility: RawVisibilityId,
 676     pub generic_params: Interned<GenericParams>,
 677     pub is_auto: bool,
 678     pub is_unsafe: bool,
 679     pub items: Box<[AssocItem]>,
 680     pub ast_id: FileAstId<ast::Trait>,
 681 }
 682
 683 #[derive(Debug, Clone, Eq, PartialEq)]
 684 pub struct TraitAlias {
 685     pub name: Name,
 686     pub visibility: RawVisibilityId,
 687     pub generic_params: Interned<GenericParams>,
 688     pub ast_id: FileAstId<ast::TraitAlias>,
 689 }
 690
 691 #[derive(Debug, Clone, Eq, PartialEq)]
 692 pub struct Impl {
 693     pub generic_params: Interned<GenericParams>,
 694     pub target_trait: Option<Interned<TraitRef>>,
 695     pub self_ty: Interned<TypeRef>,
 696     pub is_negative: bool,
 697     pub items: Box<[AssocItem]>,
 698     pub ast_id: FileAstId<ast::Impl>,
 699 }
 700
 701 #[derive(Debug, Clone, PartialEq, Eq)]
 702 pub struct TypeAlias {
 703     pub name: Name,
 704     pub visibility: RawVisibilityId,
 705     /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
 706     pub bounds: Box<[Interned<TypeBound>]>,
 707     pub generic_params: Interned<GenericParams>,
 708     pub type_ref: Option<Interned<TypeRef>>,
 709     pub ast_id: FileAstId<ast::TypeAlias>,
 710 }
 711
 712 #[derive(Debug, Clone, Eq, PartialEq)]
 713 pub struct Mod {
 714     pub name: Name,
 715     pub visibility: RawVisibilityId,
 716     pub kind: ModKind,
 717     pub ast_id: FileAstId<ast::Module>,
 718 }
 719
 720 #[derive(Debug, Clone, Eq, PartialEq)]
 721 pub enum ModKind {
 722     /// `mod m { ... }`
 723     Inline { items: Box<[ModItem]> },
 724
 725     /// `mod m;`
 726     Outline,
 727 }
 728
 729 #[derive(Debug, Clone, Eq, PartialEq)]
 730 pub struct MacroCall {
 731     /// Path to the called macro.
 732     pub path: Interned<ModPath>,
 733     pub ast_id: FileAstId<ast::MacroCall>,
 734     pub expand_to: ExpandTo,
 735 }
 736
 737 #[derive(Debug, Clone, Eq, PartialEq)]
 738 pub struct MacroRules {
 739     /// The name of the declared macro.
 740     pub name: Name,
 741     pub ast_id: FileAstId<ast::MacroRules>,
 742 }
 743
 744 /// "Macros 2.0" macro definition.
 745 #[derive(Debug, Clone, Eq, PartialEq)]
 746 pub struct MacroDef {
 747     pub name: Name,
 748     pub visibility: RawVisibilityId,
 749     pub ast_id: FileAstId<ast::MacroDef>,
 750 }
 751
 752 impl Import {
 753     /// Maps a `UseTree` contained in this import back to its AST node.
 754     pub fn use_tree_to_ast(
 755         &self,
 756         db: &dyn DefDatabase,
 757         file_id: HirFileId,
 758         index: Idx<ast::UseTree>,
 759     ) -> ast::UseTree {
 760         // Re-lower the AST item and get the source map.
 761         // Note: The AST unwraps are fine, since if they fail we should have never obtained `index`.
 762         let ast = InFile::new(file_id, self.ast_id).to_node(db.upcast());
 763         let ast_use_tree = ast.use_tree().expect("missing `use_tree`");
 764         let hygiene = Hygiene::new(db.upcast(), file_id);
 765         let (_, source_map) =
 766             lower::lower_use_tree(db, &hygiene, ast_use_tree).expect("failed to lower use tree");
 767         source_map[index].clone()
 768     }
 769 }
 770
 771 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
 772 pub enum ImportKind {
 773     /// The `ModPath` is imported normally.
 774     Plain,
 775     /// This is a glob-import of all names in the `ModPath`.
 776     Glob,
 777     /// This is a `some::path::self` import, which imports `some::path` only in type namespace.
 778     TypeOnly,
 779 }
 780
 781 impl UseTree {
 782     /// Expands the `UseTree` into individually imported `ModPath`s.
 783     pub fn expand(
 784         &self,
 785         mut cb: impl FnMut(Idx<ast::UseTree>, ModPath, ImportKind, Option<ImportAlias>),
 786     ) {
 787         self.expand_impl(None, &mut cb)
 788     }
 789
 790     fn expand_impl(
 791         &self,
 792         prefix: Option<ModPath>,
 793         cb: &mut dyn FnMut(Idx<ast::UseTree>, ModPath, ImportKind, Option<ImportAlias>),
 794     ) {
 795         fn concat_mod_paths(
 796             prefix: Option<ModPath>,
 797             path: &ModPath,
 798         ) -> Option<(ModPath, ImportKind)> {
 799             match (prefix, &path.kind) {
 800                 (None, _) => Some((path.clone(), ImportKind::Plain)),
 801                 (Some(mut prefix), PathKind::Plain) => {
 802                     for segment in path.segments() {
 803                         prefix.push_segment(segment.clone());
 804                     }
 805                     Some((prefix, ImportKind::Plain))
 806                 }
 807                 (Some(mut prefix), PathKind::Super(n))
 808                     if *n > 0 && prefix.segments().is_empty() =>
 809                 {
 810                     // `super::super` + `super::rest`
 811                     match &mut prefix.kind {
 812                         PathKind::Super(m) => {
 813                             cov_mark::hit!(concat_super_mod_paths);
 814                             *m += *n;
 815                             for segment in path.segments() {
 816                                 prefix.push_segment(segment.clone());
 817                             }
 818                             Some((prefix, ImportKind::Plain))
 819                         }
 820                         _ => None,
 821                     }
 822                 }
 823                 (Some(prefix), PathKind::Super(0)) if path.segments().is_empty() => {
 824                     // `some::path::self` == `some::path`
 825                     Some((prefix, ImportKind::TypeOnly))
 826                 }
 827                 (Some(_), _) => None,
 828             }
 829         }
 830
 831         match &self.kind {
 832             UseTreeKind::Single { path, alias } => {
 833                 if let Some((path, kind)) = concat_mod_paths(prefix, path) {
 834                     cb(self.index, path, kind, alias.clone());
 835                 }
 836             }
 837             UseTreeKind::Glob { path: Some(path) } => {
 838                 if let Some((path, _)) = concat_mod_paths(prefix, path) {
 839                     cb(self.index, path, ImportKind::Glob, None);
 840                 }
 841             }
 842             UseTreeKind::Glob { path: None } => {
 843                 if let Some(prefix) = prefix {
 844                     cb(self.index, prefix, ImportKind::Glob, None);
 845                 }
 846             }
 847             UseTreeKind::Prefixed { prefix: additional_prefix, list } => {
 848                 let prefix = match additional_prefix {
 849                     Some(path) => match concat_mod_paths(prefix, path) {
 850                         Some((path, ImportKind::Plain)) => Some(path),
 851                         _ => return,
 852                     },
 853                     None => prefix,
 854                 };
 855                 for tree in &**list {
 856                     tree.expand_impl(prefix.clone(), cb);
 857                 }
 858             }
 859         }
 860     }
 861 }
 862
 863 macro_rules! impl_froms {
 864     ($e:ident { $($v:ident ($t:ty)),* $(,)? }) => {
 865         $(
 866             impl From<$t> for $e {
 867                 fn from(it: $t) -> $e {
 868                     $e::$v(it)
 869                 }
 870             }
 871         )*
 872     }
 873 }
 874
 875 impl ModItem {
 876     pub fn as_assoc_item(&self) -> Option<AssocItem> {
 877         match self {
 878             ModItem::Import(_)
 879             | ModItem::ExternCrate(_)
 880             | ModItem::ExternBlock(_)
 881             | ModItem::Struct(_)
 882             | ModItem::Union(_)
 883             | ModItem::Enum(_)
 884             | ModItem::Static(_)
 885             | ModItem::Trait(_)
 886             | ModItem::TraitAlias(_)
 887             | ModItem::Impl(_)
 888             | ModItem::Mod(_)
 889             | ModItem::MacroRules(_)
 890             | ModItem::MacroDef(_) => None,
 891             ModItem::MacroCall(call) => Some(AssocItem::MacroCall(*call)),
 892             ModItem::Const(konst) => Some(AssocItem::Const(*konst)),
 893             ModItem::TypeAlias(alias) => Some(AssocItem::TypeAlias(*alias)),
 894             ModItem::Function(func) => Some(AssocItem::Function(*func)),
 895         }
 896     }
 897
 898     pub fn downcast<N: ItemTreeNode>(self) -> Option<FileItemTreeId<N>> {
 899         N::id_from_mod_item(self)
 900     }
 901
 902     pub fn ast_id(&self, tree: &ItemTree) -> FileAstId<ast::Item> {
 903         match self {
 904             ModItem::Import(it) => tree[it.index].ast_id().upcast(),
 905             ModItem::ExternCrate(it) => tree[it.index].ast_id().upcast(),
 906             ModItem::ExternBlock(it) => tree[it.index].ast_id().upcast(),
 907             ModItem::Function(it) => tree[it.index].ast_id().upcast(),
 908             ModItem::Struct(it) => tree[it.index].ast_id().upcast(),
 909             ModItem::Union(it) => tree[it.index].ast_id().upcast(),
 910             ModItem::Enum(it) => tree[it.index].ast_id().upcast(),
 911             ModItem::Const(it) => tree[it.index].ast_id().upcast(),
 912             ModItem::Static(it) => tree[it.index].ast_id().upcast(),
 913             ModItem::Trait(it) => tree[it.index].ast_id().upcast(),
 914             ModItem::TraitAlias(it) => tree[it.index].ast_id().upcast(),
 915             ModItem::Impl(it) => tree[it.index].ast_id().upcast(),
 916             ModItem::TypeAlias(it) => tree[it.index].ast_id().upcast(),
 917             ModItem::Mod(it) => tree[it.index].ast_id().upcast(),
 918             ModItem::MacroCall(it) => tree[it.index].ast_id().upcast(),
 919             ModItem::MacroRules(it) => tree[it.index].ast_id().upcast(),
 920             ModItem::MacroDef(it) => tree[it.index].ast_id().upcast(),
 921         }
 922     }
 923 }
 924
 925 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 926 pub enum AssocItem {
 927     Function(FileItemTreeId<Function>),
 928     TypeAlias(FileItemTreeId<TypeAlias>),
 929     Const(FileItemTreeId<Const>),
 930     MacroCall(FileItemTreeId<MacroCall>),
 931 }
 932
 933 impl_froms!(AssocItem {
 934     Function(FileItemTreeId<Function>),
 935     TypeAlias(FileItemTreeId<TypeAlias>),
 936     Const(FileItemTreeId<Const>),
 937     MacroCall(FileItemTreeId<MacroCall>),
 938 });
 939
 940 impl From<AssocItem> for ModItem {
 941     fn from(item: AssocItem) -> Self {
 942         match item {
 943             AssocItem::Function(it) => it.into(),
 944             AssocItem::TypeAlias(it) => it.into(),
 945             AssocItem::Const(it) => it.into(),
 946             AssocItem::MacroCall(it) => it.into(),
 947         }
 948     }
 949 }
 950
 951 impl AssocItem {
 952     pub fn ast_id(self, tree: &ItemTree) -> FileAstId<ast::AssocItem> {
 953         match self {
 954             AssocItem::Function(id) => tree[id].ast_id.upcast(),
 955             AssocItem::TypeAlias(id) => tree[id].ast_id.upcast(),
 956             AssocItem::Const(id) => tree[id].ast_id.upcast(),
 957             AssocItem::MacroCall(id) => tree[id].ast_id.upcast(),
 958         }
 959     }
 960 }
 961
 962 #[derive(Debug, Eq, PartialEq)]
 963 pub struct Variant {
 964     pub name: Name,
 965     pub fields: Fields,
 966     pub ast_id: FileAstId<ast::Variant>,
 967 }
 968
 969 #[derive(Debug, Clone, PartialEq, Eq)]
 970 pub enum Fields {
 971     Record(IdxRange<Field>),
 972     Tuple(IdxRange<Field>),
 973     Unit,
 974 }
 975
 976 #[derive(Debug, Clone, PartialEq, Eq)]
 977 pub enum FieldAstId {
 978     Record(FileAstId<ast::RecordField>),
 979     Tuple(FileAstId<ast::TupleField>),
 980 }
 981
 982 /// A single field of an enum variant or struct
 983 #[derive(Debug, Clone, PartialEq, Eq)]
 984 pub struct Field {
 985     pub name: Name,
 986     pub type_ref: Interned<TypeRef>,
 987     pub visibility: RawVisibilityId,
 988     pub ast_id: FieldAstId,
 989 }