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