1 //! A simplified AST that only contains items.
16 use arena::{Arena, Idx, RawId};
17 use ast::{AstNode, AttrsOwner, NameOwner, StructKind};
20 ast_id_map::FileAstId,
22 name::{name, AsName, Name},
25 use rustc_hash::FxHashMap;
26 use smallvec::SmallVec;
27 use syntax::{ast, match_ast};
33 generics::GenericParams,
34 path::{path, AssociatedTypeBinding, GenericArgs, ImportAlias, ModPath, Path, PathKind},
35 type_ref::{Mutability, TypeBound, TypeRef},
36 visibility::RawVisibility,
39 #[derive(Copy, Clone, Eq, PartialEq)]
40 pub struct RawVisibilityId(u32);
42 impl RawVisibilityId {
43 pub const PUB: Self = RawVisibilityId(u32::max_value());
44 pub const PRIV: Self = RawVisibilityId(u32::max_value() - 1);
45 pub const PUB_CRATE: Self = RawVisibilityId(u32::max_value() - 2);
48 impl fmt::Debug for RawVisibilityId {
49 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50 let mut f = f.debug_tuple("RawVisibilityId");
52 Self::PUB => f.field(&"pub"),
53 Self::PRIV => f.field(&"pub(self)"),
54 Self::PUB_CRATE => f.field(&"pub(crate)"),
55 _ => f.field(&self.0),
61 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
62 pub struct GenericParamsId(u32);
64 impl GenericParamsId {
65 pub const EMPTY: Self = GenericParamsId(u32::max_value());
68 /// The item tree of a source file.
69 #[derive(Debug, Eq, PartialEq)]
71 top_level: SmallVec<[ModItem; 1]>,
72 attrs: FxHashMap<AttrOwner, Attrs>,
73 inner_items: FxHashMap<FileAstId<ast::Item>, SmallVec<[ModItem; 1]>>,
75 data: Option<Box<ItemTreeData>>,
79 pub fn 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) {
84 return Arc::new(Self::empty());
87 let hygiene = Hygiene::new(db.upcast(), file_id);
88 let ctx = lower::Ctx::new(db, hygiene.clone(), file_id);
89 let mut top_attrs = None;
90 let mut item_tree = match_ast! {
92 ast::SourceFile(file) => {
93 top_attrs = Some(Attrs::new(&file, &hygiene));
94 ctx.lower_module_items(&file)
96 ast::MacroItems(items) => {
97 ctx.lower_module_items(&items)
99 // Macros can expand to expressions. We return an empty item tree in this case, but
100 // still need to collect inner items.
102 ctx.lower_inner_items(e.syntax())
105 panic!("cannot create item tree from {:?}", syntax);
110 if let Some(attrs) = top_attrs {
111 item_tree.attrs.insert(AttrOwner::TopLevel, attrs);
113 item_tree.shrink_to_fit();
119 top_level: Default::default(),
120 attrs: Default::default(),
121 inner_items: Default::default(),
122 data: Default::default(),
126 fn shrink_to_fit(&mut self) {
127 if let Some(data) = &mut self.data {
149 imports.shrink_to_fit();
150 extern_crates.shrink_to_fit();
151 functions.shrink_to_fit();
152 structs.shrink_to_fit();
153 fields.shrink_to_fit();
154 unions.shrink_to_fit();
155 enums.shrink_to_fit();
156 variants.shrink_to_fit();
157 consts.shrink_to_fit();
158 statics.shrink_to_fit();
159 traits.shrink_to_fit();
160 impls.shrink_to_fit();
161 type_aliases.shrink_to_fit();
162 mods.shrink_to_fit();
163 macro_calls.shrink_to_fit();
164 exprs.shrink_to_fit();
166 vis.arena.shrink_to_fit();
167 generics.arena.shrink_to_fit();
171 /// Returns an iterator over all items located at the top level of the `HirFileId` this
172 /// `ItemTree` was created from.
173 pub fn top_level_items(&self) -> &[ModItem] {
177 /// Returns the inner attributes of the source file.
178 pub fn top_level_attrs(&self) -> &Attrs {
179 self.attrs.get(&AttrOwner::TopLevel).unwrap_or(&Attrs::EMPTY)
182 pub fn attrs(&self, of: AttrOwner) -> &Attrs {
183 self.attrs.get(&of).unwrap_or(&Attrs::EMPTY)
186 /// Returns the lowered inner items that `ast` corresponds to.
188 /// Most AST items are lowered to a single `ModItem`, but some (eg. `use` items) may be lowered
189 /// to multiple items in the `ItemTree`.
190 pub fn inner_items(&self, ast: FileAstId<ast::Item>) -> &[ModItem] {
191 &self.inner_items[&ast]
194 pub fn all_inner_items(&self) -> impl Iterator<Item = ModItem> + '_ {
195 self.inner_items.values().flatten().copied()
198 pub fn source<S: ItemTreeNode>(&self, db: &dyn DefDatabase, of: ItemTreeId<S>) -> S::Source {
199 // This unwrap cannot fail, since it has either succeeded above, or resulted in an empty
200 // ItemTree (in which case there is no valid `FileItemTreeId` to call this method with).
202 db.parse_or_expand(of.file_id).expect("parse_or_expand failed on constructed ItemTree");
204 let id = self[of.value].ast_id();
205 let map = db.ast_id_map(of.file_id);
206 let ptr = map.get(id);
210 fn data(&self) -> &ItemTreeData {
211 self.data.as_ref().expect("attempted to access data of empty ItemTree")
214 fn data_mut(&mut self) -> &mut ItemTreeData {
215 self.data.get_or_insert_with(Box::default)
219 #[derive(Default, Debug, Eq, PartialEq)]
220 struct ItemVisibilities {
221 arena: Arena<RawVisibility>,
224 impl ItemVisibilities {
225 fn alloc(&mut self, vis: RawVisibility) -> RawVisibilityId {
227 RawVisibility::Public => RawVisibilityId::PUB,
228 RawVisibility::Module(path) if path.segments.is_empty() => match &path.kind {
229 PathKind::Super(0) => RawVisibilityId::PRIV,
230 PathKind::Crate => RawVisibilityId::PUB_CRATE,
231 _ => RawVisibilityId(self.arena.alloc(vis).into_raw().into()),
233 _ => RawVisibilityId(self.arena.alloc(vis).into_raw().into()),
238 static VIS_PUB: RawVisibility = RawVisibility::Public;
239 static VIS_PRIV: RawVisibility =
240 RawVisibility::Module(ModPath { kind: PathKind::Super(0), segments: Vec::new() });
241 static VIS_PUB_CRATE: RawVisibility =
242 RawVisibility::Module(ModPath { kind: PathKind::Crate, segments: Vec::new() });
244 #[derive(Default, Debug, Eq, PartialEq)]
245 struct GenericParamsStorage {
246 arena: Arena<GenericParams>,
249 impl GenericParamsStorage {
250 fn alloc(&mut self, params: GenericParams) -> GenericParamsId {
251 if params.types.is_empty() && params.where_predicates.is_empty() {
252 return GenericParamsId::EMPTY;
255 GenericParamsId(self.arena.alloc(params).into_raw().into())
259 static EMPTY_GENERICS: GenericParams =
260 GenericParams { types: Arena::new(), where_predicates: Vec::new() };
262 #[derive(Default, Debug, Eq, PartialEq)]
263 struct ItemTreeData {
264 imports: Arena<Import>,
265 extern_crates: Arena<ExternCrate>,
266 functions: Arena<Function>,
267 structs: Arena<Struct>,
268 fields: Arena<Field>,
269 unions: Arena<Union>,
271 variants: Arena<Variant>,
272 consts: Arena<Const>,
273 statics: Arena<Static>,
274 traits: Arena<Trait>,
276 type_aliases: Arena<TypeAlias>,
278 macro_calls: Arena<MacroCall>,
281 vis: ItemVisibilities,
282 generics: GenericParamsStorage,
285 #[derive(Debug, Eq, PartialEq, Hash)]
287 /// Attributes on an item.
289 /// Inner attributes of the source file.
292 Variant(Idx<Variant>),
296 macro_rules! from_attrs {
297 ( $( $var:ident($t:ty) ),+ ) => {
299 impl From<$t> for AttrOwner {
300 fn from(t: $t) -> AttrOwner {
308 from_attrs!(ModItem(ModItem), Variant(Idx<Variant>), Field(Idx<Field>));
310 /// Trait implemented by all item nodes in the item tree.
311 pub trait ItemTreeNode: Clone {
312 type Source: AstNode + Into<ast::Item>;
314 fn ast_id(&self) -> FileAstId<Self::Source>;
316 /// Looks up an instance of `Self` in an item tree.
317 fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self;
319 /// Downcasts a `ModItem` to a `FileItemTreeId` specific to this type.
320 fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>>;
322 /// Upcasts a `FileItemTreeId` to a generic `ModItem`.
323 fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem;
326 pub struct FileItemTreeId<N: ItemTreeNode> {
331 impl<N: ItemTreeNode> Clone for FileItemTreeId<N> {
332 fn clone(&self) -> Self {
333 Self { index: self.index, _p: PhantomData }
336 impl<N: ItemTreeNode> Copy for FileItemTreeId<N> {}
338 impl<N: ItemTreeNode> PartialEq for FileItemTreeId<N> {
339 fn eq(&self, other: &FileItemTreeId<N>) -> bool {
340 self.index == other.index
343 impl<N: ItemTreeNode> Eq for FileItemTreeId<N> {}
345 impl<N: ItemTreeNode> Hash for FileItemTreeId<N> {
346 fn hash<H: Hasher>(&self, state: &mut H) {
347 self.index.hash(state)
351 impl<N: ItemTreeNode> fmt::Debug for FileItemTreeId<N> {
352 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
357 pub type ItemTreeId<N> = InFile<FileItemTreeId<N>>;
359 macro_rules! mod_items {
360 ( $( $typ:ident in $fld:ident -> $ast:ty ),+ $(,)? ) => {
361 #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
364 $typ(FileItemTreeId<$typ>),
369 impl From<FileItemTreeId<$typ>> for ModItem {
370 fn from(id: FileItemTreeId<$typ>) -> ModItem {
377 impl ItemTreeNode for $typ {
380 fn ast_id(&self) -> FileAstId<Self::Source> {
384 fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self {
385 &tree.data().$fld[index]
388 fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>> {
389 if let ModItem::$typ(id) = mod_item {
396 fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem {
401 impl Index<Idx<$typ>> for ItemTree {
404 fn index(&self, index: Idx<$typ>) -> &Self::Output {
405 &self.data().$fld[index]
413 Import in imports -> ast::Use,
414 ExternCrate in extern_crates -> ast::ExternCrate,
415 Function in functions -> ast::Fn,
416 Struct in structs -> ast::Struct,
417 Union in unions -> ast::Union,
418 Enum in enums -> ast::Enum,
419 Const in consts -> ast::Const,
420 Static in statics -> ast::Static,
421 Trait in traits -> ast::Trait,
422 Impl in impls -> ast::Impl,
423 TypeAlias in type_aliases -> ast::TypeAlias,
424 Mod in mods -> ast::Module,
425 MacroCall in macro_calls -> ast::MacroCall,
428 macro_rules! impl_index {
429 ( $($fld:ident: $t:ty),+ $(,)? ) => {
431 impl Index<Idx<$t>> for ItemTree {
434 fn index(&self, index: Idx<$t>) -> &Self::Output {
435 &self.data().$fld[index]
442 impl_index!(fields: Field, variants: Variant, exprs: Expr);
444 impl Index<RawVisibilityId> for ItemTree {
445 type Output = RawVisibility;
446 fn index(&self, index: RawVisibilityId) -> &Self::Output {
448 RawVisibilityId::PRIV => &VIS_PRIV,
449 RawVisibilityId::PUB => &VIS_PUB,
450 RawVisibilityId::PUB_CRATE => &VIS_PUB_CRATE,
451 _ => &self.data().vis.arena[Idx::from_raw(index.0.into())],
456 impl Index<GenericParamsId> for ItemTree {
457 type Output = GenericParams;
459 fn index(&self, index: GenericParamsId) -> &Self::Output {
461 GenericParamsId::EMPTY => &EMPTY_GENERICS,
462 _ => &self.data().generics.arena[Idx::from_raw(index.0.into())],
467 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
469 fn index(&self, id: FileItemTreeId<N>) -> &N {
470 N::lookup(self, id.index)
474 /// A desugared `use` import.
475 #[derive(Debug, Clone, Eq, PartialEq)]
478 pub alias: Option<ImportAlias>,
479 pub visibility: RawVisibilityId,
481 pub is_prelude: bool,
482 /// AST ID of the `use` or `extern crate` item this import was derived from. Note that many
483 /// `Import`s can map to the same `use` item.
484 pub ast_id: FileAstId<ast::Use>,
485 /// Index of this `Import` when the containing `Use` is visited via `ModPath::expand_use_item`.
487 /// This can be used to get the `UseTree` this `Import` corresponds to and allows emitting
488 /// precise diagnostics.
492 #[derive(Debug, Clone, Eq, PartialEq)]
493 pub struct ExternCrate {
495 pub alias: Option<ImportAlias>,
496 pub visibility: RawVisibilityId,
497 /// Whether this is a `#[macro_use] extern crate ...`.
498 pub is_macro_use: bool,
499 pub ast_id: FileAstId<ast::ExternCrate>,
502 #[derive(Debug, Clone, Eq, PartialEq)]
503 pub struct Function {
505 pub visibility: RawVisibilityId,
506 pub generic_params: GenericParamsId,
507 pub has_self_param: bool,
510 pub params: Box<[TypeRef]>,
511 pub is_varargs: bool,
512 pub ret_type: TypeRef,
513 pub ast_id: FileAstId<ast::Fn>,
516 #[derive(Debug, Clone, Eq, PartialEq)]
519 pub visibility: RawVisibilityId,
520 pub generic_params: GenericParamsId,
522 pub ast_id: FileAstId<ast::Struct>,
523 pub kind: StructDefKind,
526 #[derive(Debug, Clone, Eq, PartialEq)]
527 pub enum StructDefKind {
528 /// `struct S { ... }` - type namespace only.
536 #[derive(Debug, Clone, Eq, PartialEq)]
539 pub visibility: RawVisibilityId,
540 pub generic_params: GenericParamsId,
542 pub ast_id: FileAstId<ast::Union>,
545 #[derive(Debug, Clone, Eq, PartialEq)]
548 pub visibility: RawVisibilityId,
549 pub generic_params: GenericParamsId,
550 pub variants: IdRange<Variant>,
551 pub ast_id: FileAstId<ast::Enum>,
554 #[derive(Debug, Clone, Eq, PartialEq)]
556 /// const _: () = ();
557 pub name: Option<Name>,
558 pub visibility: RawVisibilityId,
559 pub type_ref: TypeRef,
560 pub ast_id: FileAstId<ast::Const>,
563 #[derive(Debug, Clone, Eq, PartialEq)]
566 pub visibility: RawVisibilityId,
568 pub type_ref: TypeRef,
569 pub ast_id: FileAstId<ast::Static>,
572 #[derive(Debug, Clone, Eq, PartialEq)]
575 pub visibility: RawVisibilityId,
576 pub generic_params: GenericParamsId,
578 pub items: Box<[AssocItem]>,
579 pub ast_id: FileAstId<ast::Trait>,
582 #[derive(Debug, Clone, Eq, PartialEq)]
584 pub generic_params: GenericParamsId,
585 pub target_trait: Option<TypeRef>,
586 pub target_type: TypeRef,
587 pub is_negative: bool,
588 pub items: Box<[AssocItem]>,
589 pub ast_id: FileAstId<ast::Impl>,
592 #[derive(Debug, Clone, PartialEq, Eq)]
593 pub struct TypeAlias {
595 pub visibility: RawVisibilityId,
596 /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
597 pub bounds: Box<[TypeBound]>,
598 pub generic_params: GenericParamsId,
599 pub type_ref: Option<TypeRef>,
601 pub ast_id: FileAstId<ast::TypeAlias>,
604 #[derive(Debug, Clone, Eq, PartialEq)]
607 pub visibility: RawVisibilityId,
609 pub ast_id: FileAstId<ast::Module>,
612 #[derive(Debug, Clone, Eq, PartialEq)]
615 Inline { items: Box<[ModItem]> },
621 #[derive(Debug, Clone, Eq, PartialEq)]
622 pub struct MacroCall {
623 /// For `macro_rules!` declarations, this is the name of the declared macro.
624 pub name: Option<Name>,
625 /// Path to the called macro.
627 /// Has `#[macro_export]`.
629 /// Has `#[macro_export(local_inner_macros)]`.
630 pub is_local_inner: bool,
631 /// Has `#[rustc_builtin_macro]`.
632 pub is_builtin: bool,
633 pub ast_id: FileAstId<ast::MacroCall>,
636 // NB: There's no `FileAstId` for `Expr`. The only case where this would be useful is for array
637 // lengths, but we don't do much with them yet.
638 #[derive(Debug, Clone, Eq, PartialEq)]
641 macro_rules! impl_froms {
642 ($e:ident { $($v:ident ($t:ty)),* $(,)? }) => {
644 impl From<$t> for $e {
645 fn from(it: $t) -> $e {
654 pub fn as_assoc_item(&self) -> Option<AssocItem> {
657 | ModItem::ExternCrate(_)
664 | ModItem::Mod(_) => None,
665 ModItem::MacroCall(call) => Some(AssocItem::MacroCall(*call)),
666 ModItem::Const(konst) => Some(AssocItem::Const(*konst)),
667 ModItem::TypeAlias(alias) => Some(AssocItem::TypeAlias(*alias)),
668 ModItem::Function(func) => Some(AssocItem::Function(*func)),
672 pub fn downcast<N: ItemTreeNode>(self) -> Option<FileItemTreeId<N>> {
673 N::id_from_mod_item(self)
677 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
679 Function(FileItemTreeId<Function>),
680 TypeAlias(FileItemTreeId<TypeAlias>),
681 Const(FileItemTreeId<Const>),
682 MacroCall(FileItemTreeId<MacroCall>),
685 impl_froms!(AssocItem {
686 Function(FileItemTreeId<Function>),
687 TypeAlias(FileItemTreeId<TypeAlias>),
688 Const(FileItemTreeId<Const>),
689 MacroCall(FileItemTreeId<MacroCall>),
692 impl From<AssocItem> for ModItem {
693 fn from(item: AssocItem) -> Self {
695 AssocItem::Function(it) => it.into(),
696 AssocItem::TypeAlias(it) => it.into(),
697 AssocItem::Const(it) => it.into(),
698 AssocItem::MacroCall(it) => it.into(),
703 #[derive(Debug, Eq, PartialEq)]
709 pub struct IdRange<T> {
715 fn new(range: Range<Idx<T>>) -> Self {
716 Self { range: range.start.into_raw().into()..range.end.into_raw().into(), _p: PhantomData }
720 impl<T> Iterator for IdRange<T> {
722 fn next(&mut self) -> Option<Self::Item> {
723 self.range.next().map(|raw| Idx::from_raw(raw.into()))
727 impl<T> fmt::Debug for IdRange<T> {
728 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
729 f.debug_tuple(&format!("IdRange::<{}>", type_name::<T>())).field(&self.range).finish()
733 impl<T> Clone for IdRange<T> {
734 fn clone(&self) -> Self {
735 Self { range: self.range.clone(), _p: PhantomData }
739 impl<T> PartialEq for IdRange<T> {
740 fn eq(&self, other: &Self) -> bool {
741 self.range == other.range
745 impl<T> Eq for IdRange<T> {}
747 #[derive(Debug, Clone, PartialEq, Eq)]
749 Record(IdRange<Field>),
750 Tuple(IdRange<Field>),
754 /// A single field of an enum variant or struct
755 #[derive(Debug, Clone, PartialEq, Eq)]
758 pub type_ref: TypeRef,
759 pub visibility: RawVisibilityId,