span/

ast_id.rs

//! `AstIdMap` allows to create stable IDs for "large" syntax nodes like items
//! and macro calls.
//!
//! Specifically, it enumerates all items in a file and uses position of a an
//! item as an ID. That way, id's don't change unless the set of items itself
//! changes.
//!
//! These IDs are tricky. If one of them invalidates, its interned ID invalidates,
//! and this can cause *a lot* to be recomputed. For example, if you invalidate the ID
//! of a struct, and that struct has an impl (any impl!) this will cause the `Self`
//! type of the impl to invalidate, which will cause the all impls queries to be
//! invalidated, which will cause every trait solve query in this crate *and* all
//! transitive reverse dependencies to be invalidated, which is pretty much the worst
//! thing that can happen incrementality wise.
//!
//! So we want these IDs to stay as stable as possible. For top-level items, we store
//! their kind and name, which should be unique, but since they can still not be, we
//! also store an index disambiguator. For nested items, we also store the ID of their
//! parent. For macro calls, we store the macro name and an index. There aren't usually
//! a lot of macro calls in item position, and invalidation in bodies is not much of
//! a problem, so this should be enough.

use std::{
    any::type_name,
    fmt,
    hash::{BuildHasher, Hash, Hasher},
    marker::PhantomData,
};

use la_arena::{Arena, Idx, RawIdx};
use rustc_hash::{FxBuildHasher, FxHashMap};
use syntax::{
    AstNode, AstPtr, SyntaxKind, SyntaxNode, SyntaxNodePtr,
    ast::{self, HasName},
    match_ast,
};

// The first index is always the root node's AstId
/// The root ast id always points to the encompassing file, using this in spans is discouraged as
/// any range relative to it will be effectively absolute, ruining the entire point of anchored
/// relative text ranges.
pub const ROOT_ERASED_FILE_AST_ID: ErasedFileAstId =
    ErasedFileAstId(pack_hash_index_and_kind(0, 0, ErasedFileAstIdKind::Root as u32));

/// ErasedFileAstId used as the span for syntax node fixups. Any Span containing this file id is to be
/// considered fake.
/// Do not modify this, it is used by the proc-macro server.
pub const FIXUP_ERASED_FILE_AST_ID_MARKER: ErasedFileAstId =
    ErasedFileAstId(pack_hash_index_and_kind(0, 0, ErasedFileAstIdKind::Fixup as u32));

/// [`ErasedFileAstId`] used as the span for syntax nodes that should not be mapped down to
/// macro expansion. Any `Span` containing this file id is to be considered fake.
pub const NO_DOWNMAP_ERASED_FILE_AST_ID_MARKER: ErasedFileAstId =
    ErasedFileAstId(pack_hash_index_and_kind(0, 0, ErasedFileAstIdKind::NoDownmap as u32));

/// This is a type erased FileAstId.
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct ErasedFileAstId(u32);

impl fmt::Debug for ErasedFileAstId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let kind = self.kind();
        macro_rules! kind {
            ($($kind:ident),* $(,)?) => {
                if false {
                    // Ensure we covered all variants.
                    match ErasedFileAstIdKind::Root {
                        $( ErasedFileAstIdKind::$kind => {} )*
                    }
                    unreachable!()
                }
                $( else if kind == ErasedFileAstIdKind::$kind as u32 {
                    stringify!($kind)
                } )*
                else {
                    "Unknown"
                }
            };
        }
        let kind = kind!(
            Root,
            Enum,
            Struct,
            Union,
            ExternCrate,
            MacroDef,
            MacroRules,
            Module,
            Static,
            Trait,
            TraitAlias,
            Variant,
            Const,
            Fn,
            MacroCall,
            TypeAlias,
            ExternBlock,
            Use,
            Impl,
            BlockExpr,
            AsmExpr,
            Fixup,
            NoDownmap,
        );
        if f.alternate() {
            write!(f, "{kind}[{:04X}, {}]", self.hash_value(), self.index())
        } else {
            f.debug_struct("ErasedFileAstId")
                .field("kind", &format_args!("{kind}"))
                .field("index", &self.index())
                .field("hash", &format_args!("{:04X}", self.hash_value()))
                .finish()
        }
    }
}

#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
#[repr(u8)]
enum ErasedFileAstIdKind {
    /// This needs to not change because it's depended upon by the proc macro server.
    Fixup = 0,
    // The following are associated with `ErasedHasNameFileAstId`.
    Enum,
    Struct,
    Union,
    ExternCrate,
    MacroDef,
    MacroRules,
    Module,
    Static,
    Trait,
    TraitAlias,
    // Until here associated with `ErasedHasNameFileAstId`.
    // The following are associated with `ErasedAssocItemFileAstId`.
    Variant,
    Const,
    Fn,
    MacroCall,
    TypeAlias,
    // Until here associated with `ErasedAssocItemFileAstId`.
    // Extern blocks don't really have any identifying property unfortunately.
    ExternBlock,
    // FIXME: If we store the final `UseTree` instead of the top-level `Use`, we can store its name,
    // and be way more granular for incrementality, at the expense of increased memory usage.
    // Use IDs aren't used a lot. The main thing that stores them is the def map. So everything that
    // uses the def map will be invalidated. That includes infers, and so is pretty bad, but our
    // def map incrementality story is pretty bad anyway and needs to be improved (see
    // https://rust-lang.zulipchat.com/#narrow/channel/185405-t-compiler.2Frust-analyzer/topic/.60infer.60.20queries.20and.20splitting.20.60DefMap.60).
    // So I left this as-is for now, as the def map improvement should also mitigate this.
    Use,
    /// Associated with [`ImplFileAstId`].
    Impl,
    /// Associated with [`BlockExprFileAstId`].
    BlockExpr,
    // `global_asm!()` is an item, so we need to give it an `AstId`. So we give to all inline asm
    // because incrementality is not a problem, they will always be the only item in the macro file,
    // and memory usage also not because they're rare.
    AsmExpr,
    /// Represents a fake [`ErasedFileAstId`] that should not be mapped down to macro expansion
    /// result.
    NoDownmap,
    /// Keep this last.
    Root,
}

// First hash, then index, then kind.
const HASH_BITS: u32 = 16;
const INDEX_BITS: u32 = 11;
const KIND_BITS: u32 = 5;
const _: () = assert!(ErasedFileAstIdKind::Root as u32 <= ((1 << KIND_BITS) - 1));
const _: () = assert!(HASH_BITS + INDEX_BITS + KIND_BITS == u32::BITS);

#[inline]
const fn u16_hash(hash: u64) -> u16 {
    // We do basically the same as `FxHasher`. We don't use rustc-hash and truncate because the
    // higher bits have more entropy, but unlike rustc-hash we don't rotate because it rotates
    // for hashmaps that just use the low bits, but we compare all bits.
    const K: u16 = 0xecc5;
    let (part1, part2, part3, part4) =
        (hash as u16, (hash >> 16) as u16, (hash >> 32) as u16, (hash >> 48) as u16);
    part1
        .wrapping_add(part2)
        .wrapping_mul(K)
        .wrapping_add(part3)
        .wrapping_mul(K)
        .wrapping_add(part4)
        .wrapping_mul(K)
}

#[inline]
const fn pack_hash_index_and_kind(hash: u16, index: u32, kind: u32) -> u32 {
    (hash as u32) | (index << HASH_BITS) | (kind << (HASH_BITS + INDEX_BITS))
}

impl ErasedFileAstId {
    #[inline]
    fn hash_value(self) -> u16 {
        self.0 as u16
    }

    #[inline]
    fn index(self) -> u32 {
        (self.0 << KIND_BITS) >> (HASH_BITS + KIND_BITS)
    }

    #[inline]
    fn kind(self) -> u32 {
        self.0 >> (HASH_BITS + INDEX_BITS)
    }

    fn ast_id_for(
        node: &SyntaxNode,
        index_map: &mut ErasedAstIdNextIndexMap,
        parent: Option<&ErasedFileAstId>,
    ) -> Option<ErasedFileAstId> {
        // Blocks are deliberately not here - we only want to allocate a block if it contains items.
        has_name_ast_id(node, index_map)
            .or_else(|| assoc_item_ast_id(node, index_map, parent))
            .or_else(|| extern_block_ast_id(node, index_map))
            .or_else(|| use_ast_id(node, index_map))
            .or_else(|| impl_ast_id(node, index_map))
            .or_else(|| asm_expr_ast_id(node, index_map))
    }

    fn should_alloc(node: &SyntaxNode) -> bool {
        let kind = node.kind();
        should_alloc_has_name(kind)
            || should_alloc_assoc_item(kind)
            || ast::ExternBlock::can_cast(kind)
            || ast::Use::can_cast(kind)
            || ast::Impl::can_cast(kind)
            || ast::AsmExpr::can_cast(kind)
    }

    #[inline]
    pub fn into_raw(self) -> u32 {
        self.0
    }

    #[inline]
    pub const fn from_raw(v: u32) -> Self {
        Self(v)
    }
}

pub trait AstIdNode: AstNode {}

/// `AstId` points to an AST node in a specific file.
pub struct FileAstId<N> {
    raw: ErasedFileAstId,
    _marker: PhantomData<fn() -> N>,
}

/// Traits are manually implemented because `derive` adds redundant bounds.
impl<N> Clone for FileAstId<N> {
    #[inline]
    fn clone(&self) -> FileAstId<N> {
        *self
    }
}
impl<N> Copy for FileAstId<N> {}

impl<N> PartialEq for FileAstId<N> {
    fn eq(&self, other: &Self) -> bool {
        self.raw == other.raw
    }
}
impl<N> Eq for FileAstId<N> {}
impl<N> Hash for FileAstId<N> {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.raw.hash(hasher);
    }
}

impl<N> fmt::Debug for FileAstId<N> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "FileAstId::<{}>({:?})", type_name::<N>(), self.raw)
    }
}

impl<N> FileAstId<N> {
    // Can't make this a From implementation because of coherence
    #[inline]
    pub fn upcast<M: AstIdNode>(self) -> FileAstId<M>
    where
        N: Into<M>,
    {
        FileAstId { raw: self.raw, _marker: PhantomData }
    }

    #[inline]
    pub fn erase(self) -> ErasedFileAstId {
        self.raw
    }
}

#[derive(Hash)]
struct ErasedHasNameFileAstId<'a> {
    name: &'a str,
}

/// This holds the ast ID for variants too (they're a kind of assoc item).
#[derive(Hash)]
struct ErasedAssocItemFileAstId<'a> {
    /// Subtle: items in `extern` blocks **do not** store the ID of the extern block here.
    /// Instead this is left empty. The reason is that `ExternBlockFileAstId` is pretty unstable
    /// (it contains only an index), and extern blocks don't introduce a new scope, so storing
    /// the extern block ID will do more harm to incrementality than help.
    parent: Option<ErasedFileAstId>,
    properties: ErasedHasNameFileAstId<'a>,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct ImplFileAstId<'a> {
    /// This can be `None` if the `Self` type is not a named type, or if it is inside a macro call.
    self_ty_name: Option<&'a str>,
    /// This can be `None` if this is an inherent impl, or if the trait name is inside a macro call.
    trait_name: Option<&'a str>,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct BlockExprFileAstId {
    parent: Option<ErasedFileAstId>,
}

impl AstIdNode for ast::ExternBlock {}

fn extern_block_ast_id(
    node: &SyntaxNode,
    index_map: &mut ErasedAstIdNextIndexMap,
) -> Option<ErasedFileAstId> {
    if ast::ExternBlock::can_cast(node.kind()) {
        Some(index_map.new_id(ErasedFileAstIdKind::ExternBlock, ()))
    } else {
        None
    }
}

impl AstIdNode for ast::Use {}

fn use_ast_id(
    node: &SyntaxNode,
    index_map: &mut ErasedAstIdNextIndexMap,
) -> Option<ErasedFileAstId> {
    if ast::Use::can_cast(node.kind()) {
        Some(index_map.new_id(ErasedFileAstIdKind::Use, ()))
    } else {
        None
    }
}

impl AstIdNode for ast::AsmExpr {}

fn asm_expr_ast_id(
    node: &SyntaxNode,
    index_map: &mut ErasedAstIdNextIndexMap,
) -> Option<ErasedFileAstId> {
    if ast::AsmExpr::can_cast(node.kind()) {
        Some(index_map.new_id(ErasedFileAstIdKind::AsmExpr, ()))
    } else {
        None
    }
}

impl AstIdNode for ast::Impl {}

fn impl_ast_id(
    node: &SyntaxNode,
    index_map: &mut ErasedAstIdNextIndexMap,
) -> Option<ErasedFileAstId> {
    if let Some(node) = ast::Impl::cast(node.clone()) {
        let type_as_name = |ty: Option<ast::Type>| match ty? {
            ast::Type::PathType(it) => Some(it.path()?.segment()?.name_ref()?),
            _ => None,
        };
        let self_ty_name = type_as_name(node.self_ty());
        let trait_name = type_as_name(node.trait_());
        let data = ImplFileAstId {
            self_ty_name: self_ty_name.as_ref().map(|it| it.text_non_mutable()),
            trait_name: trait_name.as_ref().map(|it| it.text_non_mutable()),
        };
        Some(index_map.new_id(ErasedFileAstIdKind::Impl, data))
    } else {
        None
    }
}

// Blocks aren't `AstIdNode`s deliberately, because unlike other nodes, not all blocks get their own
// ast id, only if they have items. To account for that we have a different, fallible, API for blocks.
// impl !AstIdNode for ast::BlockExpr {}

fn block_expr_ast_id(
    node: &SyntaxNode,
    index_map: &mut ErasedAstIdNextIndexMap,
    parent: Option<&ErasedFileAstId>,
) -> Option<ErasedFileAstId> {
    if ast::BlockExpr::can_cast(node.kind()) {
        Some(
            index_map.new_id(
                ErasedFileAstIdKind::BlockExpr,
                BlockExprFileAstId { parent: parent.copied() },
            ),
        )
    } else {
        None
    }
}

#[derive(Default)]
struct ErasedAstIdNextIndexMap(FxHashMap<(ErasedFileAstIdKind, u16), u32>);

impl ErasedAstIdNextIndexMap {
    #[inline]
    fn new_id(&mut self, kind: ErasedFileAstIdKind, data: impl Hash) -> ErasedFileAstId {
        let hash = FxBuildHasher.hash_one(&data);
        let initial_hash = u16_hash(hash);
        // Even though 2^INDEX_BITS=2048 items with the same hash seems like a lot,
        // it could happen with macro calls or `use`s in macro-generated files. So we want
        // to handle it gracefully. We just increment the hash.
        let mut hash = initial_hash;
        let index = loop {
            match self.0.entry((kind, hash)) {
                std::collections::hash_map::Entry::Occupied(mut entry) => {
                    let i = entry.get_mut();
                    if *i < ((1 << INDEX_BITS) - 1) {
                        *i += 1;
                        break *i;
                    }
                }
                std::collections::hash_map::Entry::Vacant(entry) => {
                    entry.insert(0);
                    break 0;
                }
            }
            hash = hash.wrapping_add(1);
            if hash == initial_hash {
                // That's 2^27=134,217,728 items!
                panic!("you have way too many items in the same file!");
            }
        };
        let kind = kind as u32;
        ErasedFileAstId(pack_hash_index_and_kind(hash, index, kind))
    }
}

macro_rules! register_enum_ast_id {
    (impl $AstIdNode:ident for $($ident:ident),+ ) => {
        $(
            impl $AstIdNode for ast::$ident {}
        )+
    };
}
register_enum_ast_id! {
    impl AstIdNode for
    Item, AnyHasGenericParams, Adt, Macro,
    AssocItem
}

macro_rules! register_has_name_ast_id {
    (impl $AstIdNode:ident for $($ident:ident = $name_method:ident),+ ) => {
        $(
            impl $AstIdNode for ast::$ident {}
        )+

        fn has_name_ast_id(node: &SyntaxNode, index_map: &mut ErasedAstIdNextIndexMap) -> Option<ErasedFileAstId> {
            match_ast! {
                match node {
                    $(
                        ast::$ident(node) => {
                            let name = node.$name_method();
                            let name = name.as_ref().map_or("", |it| it.text_non_mutable());
                            let result = ErasedHasNameFileAstId {
                                name,
                            };
                            Some(index_map.new_id(ErasedFileAstIdKind::$ident, result))
                        },
                    )*
                    _ => None,
                }
            }
        }

        fn should_alloc_has_name(kind: SyntaxKind) -> bool {
            false $( || ast::$ident::can_cast(kind) )*
        }
    };
}
register_has_name_ast_id! {
    impl AstIdNode for
        Enum = name,
        Struct = name,
        Union = name,
        ExternCrate = name_ref,
        MacroDef = name,
        MacroRules = name,
        Module = name,
        Static = name,
        Trait = name
}

macro_rules! register_assoc_item_ast_id {
    (impl $AstIdNode:ident for $($ident:ident = $name_callback:expr),+ ) => {
        $(
            impl $AstIdNode for ast::$ident {}
        )+

        fn assoc_item_ast_id(
            node: &SyntaxNode,
            index_map: &mut ErasedAstIdNextIndexMap,
            parent: Option<&ErasedFileAstId>,
        ) -> Option<ErasedFileAstId> {
            match_ast! {
                match node {
                    $(
                        ast::$ident(node) => {
                            let name = $name_callback(node);
                            let name = name.as_ref().map_or("", |it| it.text_non_mutable());
                            let properties = ErasedHasNameFileAstId {
                                name,
                            };
                            let result = ErasedAssocItemFileAstId {
                                parent: parent.copied(),
                                properties,
                            };
                            Some(index_map.new_id(ErasedFileAstIdKind::$ident, result))
                        },
                    )*
                    _ => None,
                }
            }
        }

        fn should_alloc_assoc_item(kind: SyntaxKind) -> bool {
            false $( || ast::$ident::can_cast(kind) )*
        }
    };
}
register_assoc_item_ast_id! {
    impl AstIdNode for
    Variant = |it: ast::Variant| it.name(),
    Const = |it: ast::Const| it.name(),
    Fn = |it: ast::Fn| it.name(),
    MacroCall = |it: ast::MacroCall| it.path().and_then(|path| path.segment()?.name_ref()),
    TypeAlias = |it: ast::TypeAlias| it.name()
}

/// Maps items' `SyntaxNode`s to `ErasedFileAstId`s and back.
#[derive(Default)]
pub struct AstIdMap {
    /// An arena of the ptrs and their associated ID.
    arena: Arena<(SyntaxNodePtr, ErasedFileAstId)>,
    /// Map ptr to id.
    ptr_map: hashbrown::HashTable<ArenaId>,
    /// Map id to ptr.
    id_map: hashbrown::HashTable<ArenaId>,
}

type ArenaId = Idx<(SyntaxNodePtr, ErasedFileAstId)>;

impl fmt::Debug for AstIdMap {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("AstIdMap").field("arena", &self.arena).finish()
    }
}

impl PartialEq for AstIdMap {
    fn eq(&self, other: &Self) -> bool {
        self.arena == other.arena
    }
}
impl Eq for AstIdMap {}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ContainsItems {
    Yes,
    No,
}

impl AstIdMap {
    pub fn from_source(node: &SyntaxNode) -> AstIdMap {
        assert!(node.parent().is_none());
        let mut res = AstIdMap::default();
        let mut index_map = ErasedAstIdNextIndexMap::default();

        // Ensure we allocate the root.
        res.arena.alloc((SyntaxNodePtr::new(node), ROOT_ERASED_FILE_AST_ID));

        // By walking the tree in breadth-first order we make sure that parents
        // get lower ids then children. That is, adding a new child does not
        // change parent's id. This means that, say, adding a new function to a
        // trait does not change ids of top-level items, which helps caching.

        // This contains the stack of the `BlockExpr`s we are under. We do this
        // so we only allocate `BlockExpr`s if they contain items.
        // The general idea is: when we enter a block we push `(block, false)` here.
        // Items inside the block are attributed to the block's container, not the block.
        // For the first item we find inside a block, we make this `(block, true)`
        // and create an ast id for the block. When exiting the block we pop it,
        // whether or not we created an ast id for it.
        // It may seem that with this setup we will generate an ID for blocks that
        // have no items directly but have items inside other items inside them.
        // This is true, but it doesn't matter, because such blocks can't exist.
        // After all, the block will then contain the *outer* item, so we allocate
        // an ID for it anyway.
        let mut blocks = Vec::new();
        let mut curr_layer = vec![(node.clone(), None)];
        let mut next_layer = vec![];
        while !curr_layer.is_empty() {
            curr_layer.drain(..).for_each(|(node, parent_idx)| {
                let mut preorder = node.preorder();
                while let Some(event) = preorder.next() {
                    match event {
                        syntax::WalkEvent::Enter(node) => {
                            if ast::BlockExpr::can_cast(node.kind()) {
                                blocks.push((node, ContainsItems::No));
                            } else if ErasedFileAstId::should_alloc(&node) {
                                // Allocate blocks on-demand, only if they have items.
                                // We don't associate items with blocks, only with items, since block IDs can be quite unstable.
                                // FIXME: Is this the correct thing to do? Macro calls might actually be more incremental if
                                // associated with blocks (not sure). Either way it's not a big deal.
                                if let Some((
                                    last_block_node,
                                    already_allocated @ ContainsItems::No,
                                )) = blocks.last_mut()
                                {
                                    let block_ast_id = block_expr_ast_id(
                                        last_block_node,
                                        &mut index_map,
                                        parent_of(parent_idx, &res),
                                    )
                                    .expect("not a BlockExpr");
                                    res.arena
                                        .alloc((SyntaxNodePtr::new(last_block_node), block_ast_id));
                                    *already_allocated = ContainsItems::Yes;
                                }

                                let parent = parent_of(parent_idx, &res);
                                let ast_id =
                                    ErasedFileAstId::ast_id_for(&node, &mut index_map, parent)
                                        .expect("this node should have an ast id");
                                let idx = res.arena.alloc((SyntaxNodePtr::new(&node), ast_id));

                                next_layer.extend(node.children().map(|child| (child, Some(idx))));
                                preorder.skip_subtree();
                            }
                        }
                        syntax::WalkEvent::Leave(node) => {
                            if ast::BlockExpr::can_cast(node.kind()) {
                                assert_eq!(
                                    blocks.pop().map(|it| it.0),
                                    Some(node),
                                    "left a BlockExpr we never entered"
                                );
                            }
                        }
                    }
                }
            });
            std::mem::swap(&mut curr_layer, &mut next_layer);
            assert!(blocks.is_empty(), "didn't leave all BlockExprs");
        }

        res.ptr_map = hashbrown::HashTable::with_capacity(res.arena.len());
        res.id_map = hashbrown::HashTable::with_capacity(res.arena.len());
        for (idx, (ptr, ast_id)) in res.arena.iter() {
            let ptr_hash = hash_ptr(ptr);
            let ast_id_hash = hash_ast_id(ast_id);
            match res.ptr_map.entry(
                ptr_hash,
                |idx2| *idx2 == idx,
                |&idx| hash_ptr(&res.arena[idx].0),
            ) {
                hashbrown::hash_table::Entry::Occupied(_) => unreachable!(),
                hashbrown::hash_table::Entry::Vacant(entry) => {
                    entry.insert(idx);
                }
            }
            match res.id_map.entry(
                ast_id_hash,
                |idx2| *idx2 == idx,
                |&idx| hash_ast_id(&res.arena[idx].1),
            ) {
                hashbrown::hash_table::Entry::Occupied(_) => unreachable!(),
                hashbrown::hash_table::Entry::Vacant(entry) => {
                    entry.insert(idx);
                }
            }
        }
        res.arena.shrink_to_fit();
        return res;

        fn parent_of(parent_idx: Option<ArenaId>, res: &AstIdMap) -> Option<&ErasedFileAstId> {
            let mut parent = parent_idx.map(|parent_idx| &res.arena[parent_idx].1);
            if parent.is_some_and(|parent| parent.kind() == ErasedFileAstIdKind::ExternBlock as u32)
            {
                // See the comment on `ErasedAssocItemFileAstId` for why is this.
                // FIXME: Technically there could be an extern block inside another item, e.g.:
                // ```
                // fn foo() {
                //     extern "C" {
                //         fn bar();
                //     }
                // }
                // ```
                // Here we want to make `foo()` the parent of `bar()`, but we make it `None`.
                // Shouldn't be a big deal though.
                parent = None;
            }
            parent
        }
    }

    /// The root node.
    pub fn root(&self) -> SyntaxNodePtr {
        self.arena[Idx::from_raw(RawIdx::from_u32(0))].0
    }

    pub fn ast_id<N: AstIdNode>(&self, item: &N) -> FileAstId<N> {
        self.ast_id_for_ptr(AstPtr::new(item))
    }

    /// Blocks may not be allocated (if they have no items), so they have a different API.
    pub fn ast_id_for_block(&self, block: &ast::BlockExpr) -> Option<FileAstId<ast::BlockExpr>> {
        self.ast_id_for_ptr_for_block(AstPtr::new(block))
    }

    pub fn ast_id_for_ptr<N: AstIdNode>(&self, ptr: AstPtr<N>) -> FileAstId<N> {
        let ptr = ptr.syntax_node_ptr();
        FileAstId { raw: self.erased_ast_id(ptr), _marker: PhantomData }
    }

    /// Blocks may not be allocated (if they have no items), so they have a different API.
    pub fn ast_id_for_ptr_for_block(
        &self,
        ptr: AstPtr<ast::BlockExpr>,
    ) -> Option<FileAstId<ast::BlockExpr>> {
        let ptr = ptr.syntax_node_ptr();
        self.try_erased_ast_id(ptr).map(|raw| FileAstId { raw, _marker: PhantomData })
    }

    fn erased_ast_id(&self, ptr: SyntaxNodePtr) -> ErasedFileAstId {
        self.try_erased_ast_id(ptr).unwrap_or_else(|| {
            panic!(
                "Can't find SyntaxNodePtr {:?} in AstIdMap:\n{:?}",
                ptr,
                self.arena.iter().map(|(_id, i)| i).collect::<Vec<_>>(),
            )
        })
    }

    fn try_erased_ast_id(&self, ptr: SyntaxNodePtr) -> Option<ErasedFileAstId> {
        let hash = hash_ptr(&ptr);
        let idx = *self.ptr_map.find(hash, |&idx| self.arena[idx].0 == ptr)?;
        Some(self.arena[idx].1)
    }

    // Don't bound on `AstIdNode` here, because `BlockExpr`s are also valid here (`ast::BlockExpr`
    // doesn't always have a matching `FileAstId`, but a `FileAstId<ast::BlockExpr>` always has
    // a matching node).
    pub fn get<N: AstNode>(&self, id: FileAstId<N>) -> AstPtr<N> {
        let ptr = self.get_erased(id.raw);
        AstPtr::try_from_raw(ptr)
            .unwrap_or_else(|| panic!("AstIdMap node mismatch with node `{ptr:?}`"))
    }

    pub fn get_erased(&self, id: ErasedFileAstId) -> SyntaxNodePtr {
        let hash = hash_ast_id(&id);
        match self.id_map.find(hash, |&idx| self.arena[idx].1 == id) {
            Some(&idx) => self.arena[idx].0,
            None => panic!(
                "Can't find ast id {:?} in AstIdMap:\n{:?}",
                id,
                self.arena.iter().map(|(_id, i)| i).collect::<Vec<_>>(),
            ),
        }
    }
}

#[inline]
fn hash_ptr(ptr: &SyntaxNodePtr) -> u64 {
    FxBuildHasher.hash_one(ptr)
}

#[inline]
fn hash_ast_id(ptr: &ErasedFileAstId) -> u64 {
    FxBuildHasher.hash_one(ptr)
}

#[cfg(test)]
mod tests {
    use syntax::{AstNode, Edition, SourceFile, SyntaxKind, SyntaxNodePtr, WalkEvent, ast};

    use crate::AstIdMap;

    #[test]
    fn check_all_nodes() {
        let syntax = SourceFile::parse(
            r#"
extern crate foo;
fn foo() {
    union U {}
}
struct S;
macro_rules! m {}
macro m2() {}
trait Trait {}
impl Trait for S {}
impl S {}
impl m!() {}
impl m2!() for m!() {}
type T = i32;
enum E {
    V1(),
    V2 {},
    V3,
}
struct S; // duplicate
extern "C" {
    static S: i32;
}
static mut S: i32 = 0;
const FOO: i32 = 0;
        "#,
            Edition::CURRENT,
        )
        .syntax_node();
        let ast_id_map = AstIdMap::from_source(&syntax);
        for node in syntax.preorder() {
            let WalkEvent::Enter(node) = node else { continue };
            if !matches!(
                node.kind(),
                SyntaxKind::EXTERN_CRATE
                    | SyntaxKind::FN
                    | SyntaxKind::UNION
                    | SyntaxKind::STRUCT
                    | SyntaxKind::MACRO_RULES
                    | SyntaxKind::MACRO_DEF
                    | SyntaxKind::MACRO_CALL
                    | SyntaxKind::TRAIT
                    | SyntaxKind::IMPL
                    | SyntaxKind::TYPE_ALIAS
                    | SyntaxKind::ENUM
                    | SyntaxKind::VARIANT
                    | SyntaxKind::EXTERN_BLOCK
                    | SyntaxKind::STATIC
                    | SyntaxKind::CONST
            ) {
                continue;
            }
            let ptr = SyntaxNodePtr::new(&node);
            let ast_id = ast_id_map.erased_ast_id(ptr);
            let turn_back = ast_id_map.get_erased(ast_id);
            assert_eq!(ptr, turn_back);
        }
    }

    #[test]
    fn different_names_get_different_hashes() {
        let syntax = SourceFile::parse(
            r#"
fn foo() {}
fn bar() {}
        "#,
            Edition::CURRENT,
        )
        .syntax_node();
        let ast_id_map = AstIdMap::from_source(&syntax);
        let fns = syntax.descendants().filter_map(ast::Fn::cast).collect::<Vec<_>>();
        let [foo_fn, bar_fn] = fns.as_slice() else {
            panic!("not exactly 2 functions");
        };
        let foo_fn_id = ast_id_map.ast_id(foo_fn);
        let bar_fn_id = ast_id_map.ast_id(bar_fn);
        assert_ne!(foo_fn_id.raw.hash_value(), bar_fn_id.raw.hash_value(), "hashes are equal");
    }

    #[test]
    fn different_parents_get_different_hashes() {
        let syntax = SourceFile::parse(
            r#"
fn foo() {
    m!();
}
fn bar() {
    m!();
}
        "#,
            Edition::CURRENT,
        )
        .syntax_node();
        let ast_id_map = AstIdMap::from_source(&syntax);
        let macro_calls = syntax.descendants().filter_map(ast::MacroCall::cast).collect::<Vec<_>>();
        let [macro_call_foo, macro_call_bar] = macro_calls.as_slice() else {
            panic!("not exactly 2 macro calls");
        };
        let macro_call_foo_id = ast_id_map.ast_id(macro_call_foo);
        let macro_call_bar_id = ast_id_map.ast_id(macro_call_bar);
        assert_ne!(
            macro_call_foo_id.raw.hash_value(),
            macro_call_bar_id.raw.hash_value(),
            "hashes are equal"
        );
    }

    #[test]
    fn blocks_with_no_items_have_no_id() {
        let syntax = SourceFile::parse(
            r#"
fn foo() {
    let foo = 1;
    bar(foo);
}
        "#,
            Edition::CURRENT,
        )
        .syntax_node();
        let ast_id_map = AstIdMap::from_source(&syntax);
        let block = syntax.descendants().find_map(ast::BlockExpr::cast).expect("no block");
        assert!(ast_id_map.ast_id_for_block(&block).is_none());
    }
}