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