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