1 //! A simplified AST that only contains items.
14 use ast::{AstNode, NameOwner, StructKind};
18 ast_id_map::FileAstId,
20 name::{name, AsName, Name},
21 FragmentKind, HirFileId, InFile,
23 use la_arena::{Arena, Idx, RawIdx};
25 use rustc_hash::FxHashMap;
26 use smallvec::SmallVec;
27 use syntax::{ast, match_ast, SyntaxKind};
30 attr::{Attrs, RawAttrs},
32 generics::GenericParams,
34 path::{path, AssociatedTypeBinding, GenericArgs, ImportAlias, ModPath, Path, PathKind},
35 type_ref::{Mutability, TraitRef, 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 /// The item tree of a source file.
62 #[derive(Debug, Default, Eq, PartialEq)]
66 top_level: SmallVec<[ModItem; 1]>,
67 attrs: FxHashMap<AttrOwner, RawAttrs>,
69 data: Option<Box<ItemTreeData>>,
73 pub(crate) fn file_item_tree_query(db: &dyn DefDatabase, file_id: HirFileId) -> Arc<ItemTree> {
74 let _p = profile::span("item_tree_query").detail(|| format!("{:?}", file_id));
75 let syntax = if let Some(node) = db.parse_or_expand(file_id) {
76 if node.kind() == SyntaxKind::ERROR {
77 // FIXME: not 100% sure why these crop up, but return an empty tree to avoid a panic
78 return Default::default();
82 return Default::default();
85 let hygiene = Hygiene::new(db.upcast(), file_id);
86 let ctx = lower::Ctx::new(db, hygiene.clone(), file_id);
87 let mut top_attrs = None;
88 let mut item_tree = match_ast! {
90 ast::SourceFile(file) => {
91 top_attrs = Some(RawAttrs::new(db, &file, &hygiene));
92 ctx.lower_module_items(&file)
94 ast::MacroItems(items) => {
95 ctx.lower_module_items(&items)
97 ast::MacroStmts(stmts) => {
98 // The produced statements can include items, which should be added as top-level
100 ctx.lower_macro_stmts(stmts)
103 // FIXME: This occurs because macros in pattern position are treated as inner
104 // items and expanded during block DefMap computation
105 return Default::default();
108 // Types can contain inner items. We return an empty item tree in this case, but
109 // still need to collect inner items.
110 ctx.lower_inner_items(ty.syntax())
113 // Macros can expand to expressions. We return an empty item tree in this case, but
114 // still need to collect inner items.
115 ctx.lower_inner_items(e.syntax())
118 panic!("cannot create item tree from {:?} {}", syntax, syntax);
123 if let Some(attrs) = top_attrs {
124 item_tree.attrs.insert(AttrOwner::TopLevel, attrs);
126 item_tree.shrink_to_fit();
130 fn shrink_to_fit(&mut self) {
131 if let Some(data) = &mut self.data {
155 imports.shrink_to_fit();
156 extern_crates.shrink_to_fit();
157 functions.shrink_to_fit();
158 params.shrink_to_fit();
159 structs.shrink_to_fit();
160 fields.shrink_to_fit();
161 unions.shrink_to_fit();
162 enums.shrink_to_fit();
163 variants.shrink_to_fit();
164 consts.shrink_to_fit();
165 statics.shrink_to_fit();
166 traits.shrink_to_fit();
167 impls.shrink_to_fit();
168 type_aliases.shrink_to_fit();
169 mods.shrink_to_fit();
170 macro_calls.shrink_to_fit();
171 macro_rules.shrink_to_fit();
172 macro_defs.shrink_to_fit();
174 vis.arena.shrink_to_fit();
176 inner_items.shrink_to_fit();
180 /// Returns an iterator over all items located at the top level of the `HirFileId` this
181 /// `ItemTree` was created from.
182 pub fn top_level_items(&self) -> &[ModItem] {
186 /// Returns the inner attributes of the source file.
187 pub fn top_level_attrs(&self, db: &dyn DefDatabase, krate: CrateId) -> Attrs {
188 self.attrs.get(&AttrOwner::TopLevel).unwrap_or(&RawAttrs::EMPTY).clone().filter(db, krate)
191 pub(crate) fn raw_attrs(&self, of: AttrOwner) -> &RawAttrs {
192 self.attrs.get(&of).unwrap_or(&RawAttrs::EMPTY)
195 pub fn attrs(&self, db: &dyn DefDatabase, krate: CrateId, of: AttrOwner) -> Attrs {
196 self.raw_attrs(of).clone().filter(db, krate)
199 pub fn inner_items_of_block(&self, block: FileAstId<ast::BlockExpr>) -> &[ModItem] {
201 Some(data) => data.inner_items.get(&block).map(|it| &**it).unwrap_or(&[]),
206 fn data(&self) -> &ItemTreeData {
207 self.data.as_ref().expect("attempted to access data of empty ItemTree")
210 fn data_mut(&mut self) -> &mut ItemTreeData {
211 self.data.get_or_insert_with(Box::default)
215 #[derive(Default, Debug, Eq, PartialEq)]
216 struct ItemVisibilities {
217 arena: Arena<RawVisibility>,
220 impl ItemVisibilities {
221 fn alloc(&mut self, vis: RawVisibility) -> RawVisibilityId {
223 RawVisibility::Public => RawVisibilityId::PUB,
224 RawVisibility::Module(path) if path.segments().is_empty() => match &path.kind {
225 PathKind::Super(0) => RawVisibilityId::PRIV,
226 PathKind::Crate => RawVisibilityId::PUB_CRATE,
227 _ => RawVisibilityId(self.arena.alloc(vis).into_raw().into()),
229 _ => RawVisibilityId(self.arena.alloc(vis).into_raw().into()),
234 static VIS_PUB: RawVisibility = RawVisibility::Public;
235 static VIS_PRIV: RawVisibility = RawVisibility::Module(ModPath::from_kind(PathKind::Super(0)));
236 static VIS_PUB_CRATE: RawVisibility = RawVisibility::Module(ModPath::from_kind(PathKind::Crate));
238 #[derive(Default, Debug, Eq, PartialEq)]
239 struct ItemTreeData {
240 imports: Arena<Import>,
241 extern_crates: Arena<ExternCrate>,
242 functions: Arena<Function>,
243 params: Arena<Param>,
244 structs: Arena<Struct>,
245 fields: Arena<Field>,
246 unions: Arena<Union>,
248 variants: Arena<Variant>,
249 consts: Arena<Const>,
250 statics: Arena<Static>,
251 traits: Arena<Trait>,
253 type_aliases: Arena<TypeAlias>,
255 macro_calls: Arena<MacroCall>,
256 macro_rules: Arena<MacroRules>,
257 macro_defs: Arena<MacroDef>,
259 vis: ItemVisibilities,
261 inner_items: FxHashMap<FileAstId<ast::BlockExpr>, SmallVec<[ModItem; 1]>>,
264 #[derive(Debug, Eq, PartialEq, Hash)]
266 /// Attributes on an item.
268 /// Inner attributes of the source file.
271 Variant(Idx<Variant>),
276 macro_rules! from_attrs {
277 ( $( $var:ident($t:ty) ),+ ) => {
279 impl From<$t> for AttrOwner {
280 fn from(t: $t) -> AttrOwner {
288 from_attrs!(ModItem(ModItem), Variant(Idx<Variant>), Field(Idx<Field>), Param(Idx<Param>));
290 /// Trait implemented by all item nodes in the item tree.
291 pub trait ItemTreeNode: Clone {
292 type Source: AstNode + Into<ast::Item>;
294 fn ast_id(&self) -> FileAstId<Self::Source>;
296 /// Looks up an instance of `Self` in an item tree.
297 fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self;
299 /// Downcasts a `ModItem` to a `FileItemTreeId` specific to this type.
300 fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>>;
302 /// Upcasts a `FileItemTreeId` to a generic `ModItem`.
303 fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem;
306 pub struct FileItemTreeId<N: ItemTreeNode> {
311 impl<N: ItemTreeNode> Clone for FileItemTreeId<N> {
312 fn clone(&self) -> Self {
313 Self { index: self.index, _p: PhantomData }
316 impl<N: ItemTreeNode> Copy for FileItemTreeId<N> {}
318 impl<N: ItemTreeNode> PartialEq for FileItemTreeId<N> {
319 fn eq(&self, other: &FileItemTreeId<N>) -> bool {
320 self.index == other.index
323 impl<N: ItemTreeNode> Eq for FileItemTreeId<N> {}
325 impl<N: ItemTreeNode> Hash for FileItemTreeId<N> {
326 fn hash<H: Hasher>(&self, state: &mut H) {
327 self.index.hash(state)
331 impl<N: ItemTreeNode> fmt::Debug for FileItemTreeId<N> {
332 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
338 pub struct ItemTreeId<N: ItemTreeNode> {
340 pub value: FileItemTreeId<N>,
343 impl<N: ItemTreeNode> ItemTreeId<N> {
344 pub fn new(file: HirFileId, idx: FileItemTreeId<N>) -> Self {
345 Self { file, value: idx }
348 pub fn file_id(self) -> HirFileId {
352 pub fn item_tree(self, db: &dyn DefDatabase) -> Arc<ItemTree> {
353 db.file_item_tree(self.file)
357 impl<N: ItemTreeNode> Copy for ItemTreeId<N> {}
358 impl<N: ItemTreeNode> Clone for ItemTreeId<N> {
359 fn clone(&self) -> Self {
364 impl<N: ItemTreeNode> PartialEq for ItemTreeId<N> {
365 fn eq(&self, other: &Self) -> bool {
366 self.file == other.file && self.value == other.value
370 impl<N: ItemTreeNode> Eq for ItemTreeId<N> {}
372 impl<N: ItemTreeNode> Hash for ItemTreeId<N> {
373 fn hash<H: Hasher>(&self, state: &mut H) {
374 self.file.hash(state);
375 self.value.hash(state);
379 macro_rules! mod_items {
380 ( $( $typ:ident in $fld:ident -> $ast:ty ),+ $(,)? ) => {
381 #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
384 $typ(FileItemTreeId<$typ>),
389 impl From<FileItemTreeId<$typ>> for ModItem {
390 fn from(id: FileItemTreeId<$typ>) -> ModItem {
397 impl ItemTreeNode for $typ {
400 fn ast_id(&self) -> FileAstId<Self::Source> {
404 fn lookup(tree: &ItemTree, index: Idx<Self>) -> &Self {
405 &tree.data().$fld[index]
408 fn id_from_mod_item(mod_item: ModItem) -> Option<FileItemTreeId<Self>> {
409 if let ModItem::$typ(id) = mod_item {
416 fn id_to_mod_item(id: FileItemTreeId<Self>) -> ModItem {
421 impl Index<Idx<$typ>> for ItemTree {
424 fn index(&self, index: Idx<$typ>) -> &Self::Output {
425 &self.data().$fld[index]
433 Import in imports -> ast::Use,
434 ExternCrate in extern_crates -> ast::ExternCrate,
435 Function in functions -> ast::Fn,
436 Struct in structs -> ast::Struct,
437 Union in unions -> ast::Union,
438 Enum in enums -> ast::Enum,
439 Const in consts -> ast::Const,
440 Static in statics -> ast::Static,
441 Trait in traits -> ast::Trait,
442 Impl in impls -> ast::Impl,
443 TypeAlias in type_aliases -> ast::TypeAlias,
444 Mod in mods -> ast::Module,
445 MacroCall in macro_calls -> ast::MacroCall,
446 MacroRules in macro_rules -> ast::MacroRules,
447 MacroDef in macro_defs -> ast::MacroDef,
450 macro_rules! impl_index {
451 ( $($fld:ident: $t:ty),+ $(,)? ) => {
453 impl Index<Idx<$t>> for ItemTree {
456 fn index(&self, index: Idx<$t>) -> &Self::Output {
457 &self.data().$fld[index]
464 impl_index!(fields: Field, variants: Variant, params: Param);
466 impl Index<RawVisibilityId> for ItemTree {
467 type Output = RawVisibility;
468 fn index(&self, index: RawVisibilityId) -> &Self::Output {
470 RawVisibilityId::PRIV => &VIS_PRIV,
471 RawVisibilityId::PUB => &VIS_PUB,
472 RawVisibilityId::PUB_CRATE => &VIS_PUB_CRATE,
473 _ => &self.data().vis.arena[Idx::from_raw(index.0.into())],
478 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
480 fn index(&self, id: FileItemTreeId<N>) -> &N {
481 N::lookup(self, id.index)
485 /// A desugared `use` import.
486 #[derive(Debug, Clone, Eq, PartialEq)]
488 pub path: Interned<ModPath>,
489 pub alias: Option<ImportAlias>,
490 pub visibility: RawVisibilityId,
492 /// AST ID of the `use` or `extern crate` item this import was derived from. Note that many
493 /// `Import`s can map to the same `use` item.
494 pub ast_id: FileAstId<ast::Use>,
495 /// Index of this `Import` when the containing `Use` is visited via `ModPath::expand_use_item`.
497 /// This can be used to get the `UseTree` this `Import` corresponds to and allows emitting
498 /// precise diagnostics.
502 #[derive(Debug, Clone, Eq, PartialEq)]
503 pub struct ExternCrate {
505 pub alias: Option<ImportAlias>,
506 pub visibility: RawVisibilityId,
507 pub ast_id: FileAstId<ast::ExternCrate>,
510 #[derive(Debug, Clone, Eq, PartialEq)]
511 pub struct Function {
513 pub visibility: RawVisibilityId,
514 pub generic_params: Interned<GenericParams>,
515 pub abi: Option<Interned<str>>,
516 pub params: IdRange<Param>,
517 pub ret_type: Interned<TypeRef>,
518 pub ast_id: FileAstId<ast::Fn>,
519 pub(crate) flags: FnFlags,
522 #[derive(Debug, Clone, Eq, PartialEq)]
524 Normal(Interned<TypeRef>),
528 #[derive(Debug, Clone, Copy, Eq, PartialEq, Default)]
529 pub(crate) struct FnFlags {
533 pub(crate) const HAS_SELF_PARAM: u8 = 1 << 0;
534 pub(crate) const HAS_BODY: u8 = 1 << 1;
535 pub(crate) const IS_DEFAULT: u8 = 1 << 2;
536 pub(crate) const IS_CONST: u8 = 1 << 3;
537 pub(crate) const IS_ASYNC: u8 = 1 << 4;
538 pub(crate) const IS_UNSAFE: u8 = 1 << 5;
539 /// Whether the function is located in an `extern` block (*not* whether it is an
540 /// `extern "abi" fn`).
541 pub(crate) const IS_IN_EXTERN_BLOCK: u8 = 1 << 6;
542 pub(crate) const IS_VARARGS: u8 = 1 << 7;
545 #[derive(Debug, Clone, Eq, PartialEq)]
548 pub visibility: RawVisibilityId,
549 pub generic_params: Interned<GenericParams>,
551 pub ast_id: FileAstId<ast::Struct>,
552 pub kind: StructDefKind,
555 #[derive(Debug, Clone, Eq, PartialEq)]
556 pub enum StructDefKind {
557 /// `struct S { ... }` - type namespace only.
565 #[derive(Debug, Clone, Eq, PartialEq)]
568 pub visibility: RawVisibilityId,
569 pub generic_params: Interned<GenericParams>,
571 pub ast_id: FileAstId<ast::Union>,
574 #[derive(Debug, Clone, Eq, PartialEq)]
577 pub visibility: RawVisibilityId,
578 pub generic_params: Interned<GenericParams>,
579 pub variants: IdRange<Variant>,
580 pub ast_id: FileAstId<ast::Enum>,
583 #[derive(Debug, Clone, Eq, PartialEq)]
585 /// const _: () = ();
586 pub name: Option<Name>,
587 pub visibility: RawVisibilityId,
588 pub type_ref: Interned<TypeRef>,
589 pub ast_id: FileAstId<ast::Const>,
592 #[derive(Debug, Clone, Eq, PartialEq)]
595 pub visibility: RawVisibilityId,
597 /// Whether the static is in an `extern` block.
599 pub type_ref: Interned<TypeRef>,
600 pub ast_id: FileAstId<ast::Static>,
603 #[derive(Debug, Clone, Eq, PartialEq)]
606 pub visibility: RawVisibilityId,
607 pub generic_params: Interned<GenericParams>,
610 pub bounds: Box<[TypeBound]>,
611 pub items: Box<[AssocItem]>,
612 pub ast_id: FileAstId<ast::Trait>,
615 #[derive(Debug, Clone, Eq, PartialEq)]
617 pub generic_params: Interned<GenericParams>,
618 pub target_trait: Option<Interned<TraitRef>>,
619 pub self_ty: Interned<TypeRef>,
620 pub is_negative: bool,
621 pub items: Box<[AssocItem]>,
622 pub ast_id: FileAstId<ast::Impl>,
625 #[derive(Debug, Clone, PartialEq, Eq)]
626 pub struct TypeAlias {
628 pub visibility: RawVisibilityId,
629 /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
630 pub bounds: Box<[TypeBound]>,
631 pub generic_params: Interned<GenericParams>,
632 pub type_ref: Option<Interned<TypeRef>>,
634 pub ast_id: FileAstId<ast::TypeAlias>,
637 #[derive(Debug, Clone, Eq, PartialEq)]
640 pub visibility: RawVisibilityId,
642 pub ast_id: FileAstId<ast::Module>,
645 #[derive(Debug, Clone, Eq, PartialEq)]
648 Inline { items: Box<[ModItem]> },
654 #[derive(Debug, Clone, Eq, PartialEq)]
655 pub struct MacroCall {
656 /// Path to the called macro.
657 pub path: Interned<ModPath>,
658 pub ast_id: FileAstId<ast::MacroCall>,
659 pub fragment: FragmentKind,
662 #[derive(Debug, Clone, Eq, PartialEq)]
663 pub struct MacroRules {
664 /// The name of the declared macro.
666 pub ast_id: FileAstId<ast::MacroRules>,
669 /// "Macros 2.0" macro definition.
670 #[derive(Debug, Clone, Eq, PartialEq)]
671 pub struct MacroDef {
673 pub visibility: RawVisibilityId,
674 pub ast_id: FileAstId<ast::MacroDef>,
677 macro_rules! impl_froms {
678 ($e:ident { $($v:ident ($t:ty)),* $(,)? }) => {
680 impl From<$t> for $e {
681 fn from(it: $t) -> $e {
690 pub fn as_assoc_item(&self) -> Option<AssocItem> {
693 | ModItem::ExternCrate(_)
701 | ModItem::MacroRules(_)
702 | ModItem::MacroDef(_) => None,
703 ModItem::MacroCall(call) => Some(AssocItem::MacroCall(*call)),
704 ModItem::Const(konst) => Some(AssocItem::Const(*konst)),
705 ModItem::TypeAlias(alias) => Some(AssocItem::TypeAlias(*alias)),
706 ModItem::Function(func) => Some(AssocItem::Function(*func)),
710 pub fn downcast<N: ItemTreeNode>(self) -> Option<FileItemTreeId<N>> {
711 N::id_from_mod_item(self)
714 pub fn ast_id(&self, tree: &ItemTree) -> FileAstId<ast::Item> {
716 ModItem::Import(it) => tree[it.index].ast_id().upcast(),
717 ModItem::ExternCrate(it) => tree[it.index].ast_id().upcast(),
718 ModItem::Function(it) => tree[it.index].ast_id().upcast(),
719 ModItem::Struct(it) => tree[it.index].ast_id().upcast(),
720 ModItem::Union(it) => tree[it.index].ast_id().upcast(),
721 ModItem::Enum(it) => tree[it.index].ast_id().upcast(),
722 ModItem::Const(it) => tree[it.index].ast_id().upcast(),
723 ModItem::Static(it) => tree[it.index].ast_id().upcast(),
724 ModItem::Trait(it) => tree[it.index].ast_id().upcast(),
725 ModItem::Impl(it) => tree[it.index].ast_id().upcast(),
726 ModItem::TypeAlias(it) => tree[it.index].ast_id().upcast(),
727 ModItem::Mod(it) => tree[it.index].ast_id().upcast(),
728 ModItem::MacroCall(it) => tree[it.index].ast_id().upcast(),
729 ModItem::MacroRules(it) => tree[it.index].ast_id().upcast(),
730 ModItem::MacroDef(it) => tree[it.index].ast_id().upcast(),
735 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
737 Function(FileItemTreeId<Function>),
738 TypeAlias(FileItemTreeId<TypeAlias>),
739 Const(FileItemTreeId<Const>),
740 MacroCall(FileItemTreeId<MacroCall>),
743 impl_froms!(AssocItem {
744 Function(FileItemTreeId<Function>),
745 TypeAlias(FileItemTreeId<TypeAlias>),
746 Const(FileItemTreeId<Const>),
747 MacroCall(FileItemTreeId<MacroCall>),
750 impl From<AssocItem> for ModItem {
751 fn from(item: AssocItem) -> Self {
753 AssocItem::Function(it) => it.into(),
754 AssocItem::TypeAlias(it) => it.into(),
755 AssocItem::Const(it) => it.into(),
756 AssocItem::MacroCall(it) => it.into(),
761 #[derive(Debug, Eq, PartialEq)]
767 /// A range of densely allocated ItemTree IDs.
768 pub struct IdRange<T> {
774 fn new(range: Range<Idx<T>>) -> Self {
775 Self { range: range.start.into_raw().into()..range.end.into_raw().into(), _p: PhantomData }
779 impl<T> Iterator for IdRange<T> {
781 fn next(&mut self) -> Option<Self::Item> {
782 self.range.next().map(|raw| Idx::from_raw(raw.into()))
786 impl<T> DoubleEndedIterator for IdRange<T> {
787 fn next_back(&mut self) -> Option<Self::Item> {
788 self.range.next_back().map(|raw| Idx::from_raw(raw.into()))
792 impl<T> fmt::Debug for IdRange<T> {
793 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
794 f.debug_tuple(&format!("IdRange::<{}>", type_name::<T>())).field(&self.range).finish()
798 impl<T> Clone for IdRange<T> {
799 fn clone(&self) -> Self {
800 Self { range: self.range.clone(), _p: PhantomData }
804 impl<T> PartialEq for IdRange<T> {
805 fn eq(&self, other: &Self) -> bool {
806 self.range == other.range
810 impl<T> Eq for IdRange<T> {}
812 #[derive(Debug, Clone, PartialEq, Eq)]
814 Record(IdRange<Field>),
815 Tuple(IdRange<Field>),
819 /// A single field of an enum variant or struct
820 #[derive(Debug, Clone, PartialEq, Eq)]
823 pub type_ref: Interned<TypeRef>,
824 pub visibility: RawVisibilityId,