crates/hir_def/src/item_tree.rs

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