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