cairo_lang_syntax/node/

mod.rs

use core::hash::Hash;

use cairo_lang_filesystem::db::FilesGroup;
use cairo_lang_filesystem::ids::{FileId, SmolStrId};
use cairo_lang_filesystem::span::{TextOffset, TextPosition, TextSpan, TextWidth};
use cairo_lang_proc_macros::{DebugWithDb, HeapSize};
use cairo_lang_utils::require;
use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
use salsa::Database;
use salsa::plumbing::AsId;

use self::ast::TriviaGreen;
use self::green::GreenNode;
use self::ids::{GreenId, SyntaxStablePtrId};
use self::kind::SyntaxKind;
use crate::node::iter::{Preorder, WalkEvent};

pub mod ast;
pub mod db;
pub mod element_list;
pub mod green;
pub mod helpers;
pub mod ids;
pub mod iter;
pub mod key_fields;
pub mod kind;
pub mod stable_ptr;
pub mod with_db;

#[cfg(test)]
mod ast_test;
#[cfg(test)]
mod test_utils;

/// Private enum for syntax node id. This holds data used to identify the node.
#[derive(Debug, Clone, PartialEq, Eq, Hash, DebugWithDb, salsa::SalsaValue)]
#[debug_db(dyn Database)]
pub enum SyntaxNodeId<'db> {
    Root(FileId<'db>),
    Child {
        /// Parent of this node, either another node or if node is root, its file id.
        parent: SyntaxNode<'db>,
        /// The kind of this node. Part of the identity, as `index` below counts occurrences
        /// per `(parent, kind, key_fields)`.
        kind: SyntaxKind,
        /// Chronological index among all nodes with the same (parent, kind, key_fields).
        index: usize,
        /// Which fields are used is determined by each SyntaxKind.
        /// For example, a function item might use the name of the function.
        key_fields: Box<[GreenId<'db>]>,
    },
}

/// Private tracked struct containing the actual SyntaxNode data.
/// This is kept private so the public `new` function generated by salsa can't be called directly.
#[salsa::tracked]
#[derive(Debug, HeapSize)]
struct SyntaxNodeData<'a> {
    #[tracked]
    green: GreenId<'a>,
    /// This node's span start relative to its parent's (for a root, to the file start). Keeping
    /// it parent-relative makes `get_children` a pure function of the green tree, independent of
    /// the node's absolute position. Recover the absolute offset via [`SyntaxNode::offset`].
    #[tracked]
    #[returns(copy)]
    offset_in_parent: TextOffset,
    /// Unique identifier for this node.
    #[returns(ref)]
    id: SyntaxNodeId<'a>,
}

impl<'db> SyntaxNodeData<'db> {
    /// Gets the kind of the given node's parent if it exists.
    pub fn parent(&self, db: &'db dyn Database) -> Option<SyntaxNode<'db>> {
        match self.id(db) {
            SyntaxNodeId::Root(_) => None,
            SyntaxNodeId::Child { parent, .. } => Some(*parent),
        }
    }
}

/// The absolute offset of the node from the beginning of the file: its offset within its parent
/// plus the (recursively memoized) absolute offset of the parent. A tracked query rather than a
/// cache inside the node data, as a cache would go stale when a shifted-but-unchanged subtree is
/// backdated.
#[salsa::tracked(returns(copy))]
fn absolute_offset<'db>(db: &'db dyn Database, data: SyntaxNodeData<'db>) -> TextOffset {
    match data.parent(db) {
        Some(parent) => absolute_offset(db, parent.data)
            .add_width(data.offset_in_parent(db) - TextOffset::START),
        None => data.offset_in_parent(db),
    }
}

/// The eagerly-materialized children of all non-terminal nodes of one syntax tree, stored flat:
/// one contiguous nodes vector plus per-node (start, len) ranges, avoiding a heap allocation per
/// node.
#[derive(Debug, Default, PartialEq, Eq, salsa::SalsaValue)]
struct RedTree<'db> {
    nodes: Vec<SyntaxNode<'db>>,
    ranges: UnorderedHashMap<SyntaxNodeData<'db>, std::ops::Range<u32>>,
}

impl<'db> cairo_lang_debug::DebugWithDb<'db> for SyntaxNodeData<'db> {
    type Db = dyn Database;
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>, db: &'db Self::Db) -> std::fmt::Result {
        f.debug_struct("SyntaxNode")
            .field("green", &self.green(db).debug(db))
            .field("offset_in_parent", &self.offset_in_parent(db))
            .field("id", &self.id(db).debug(db))
            .finish()
    }
}

/// SyntaxNode. Untyped view of the syntax tree. Adds parent() and offset() capabilities.
///
/// This is a public wrapper around a private tracked struct. Construction only happens through
/// tracked functions to ensure uniqueness of SyntaxNodes.
/// The canonical tree of a file comes from `db.file_syntax(file_id)` (created via
/// [`SyntaxNode::new_canonical_root`]); standalone trees use [`SyntaxNode::new_detached_root`].
#[derive(Clone, Copy, salsa::SalsaValue, HeapSize)]
pub struct SyntaxNode<'a> {
    data: SyntaxNodeData<'a>,
    /// The data of the outermost enclosing expression block, if any - the root of the arena
    /// chunk this node belongs to. Expression code is consumed densely (body semantics visits
    /// every node), so it is materialized as one arena per body; everything else (module and item
    /// structure, which plugin expansion samples shallowly) stays lazily materialized per node.
    /// Fully derived from `data`, like the other caches below.
    arena_root: Option<SyntaxNodeData<'a>>,
    /// Cached parent data to avoid database lookups. None for root nodes.
    parent: Option<SyntaxNodeData<'a>>,
    /// Cached kind to avoid database lookups.
    kind: SyntaxKind,
    /// Cached parent kind to avoid database lookups. None for root nodes.
    parent_kind: Option<SyntaxKind>,
}

/// Equality and hashing consider only `data`: the other fields are caches fully derived from it
/// at every construction site, and `data` is embedded (via parents and stable pointers) in the
/// identity of practically every semantic object, so this is on very hot paths.
impl PartialEq for SyntaxNode<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data
    }
}
impl Eq for SyntaxNode<'_> {}
impl Hash for SyntaxNode<'_> {
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        self.data.hash(state);
    }
}

impl<'db> std::fmt::Debug for SyntaxNode<'db> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "SyntaxNode({:x})", self.data.as_id().index())
    }
}

impl<'db> cairo_lang_debug::DebugWithDb<'db> for SyntaxNode<'db> {
    type Db = dyn Database;
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>, db: &'db Self::Db) -> std::fmt::Result {
        self.data.fmt(f, db)
    }
}

impl<'db> SyntaxNode<'db> {
    /// Reconstructs the node view from its tracked data - every other field of [`SyntaxNode`] is
    /// a cache fully derived from it.
    fn from_data(db: &'db dyn Database, data: SyntaxNodeData<'db>) -> Self {
        let (parent, parent_kind, inherited_arena_root) = match data.id(db) {
            SyntaxNodeId::Child { parent, .. } => {
                (Some(parent.data), Some(parent.kind), parent.arena_root)
            }
            SyntaxNodeId::Root(_) => (None, None, None),
        };
        let kind = data.green(db).long(db).kind;
        let arena_root = inherited_arena_root.or((kind == SyntaxKind::ExprBlock).then_some(data));
        SyntaxNode { data, arena_root, parent, kind, parent_kind }
    }

    /// Gets the absolute offset of this syntax node from the beginning of the file.
    pub fn offset(self, db: &'db dyn Database) -> TextOffset {
        absolute_offset(db, self.data)
    }

    /// Gets the parent syntax node, if any.
    pub fn parent(self, db: &'db dyn Database) -> Option<SyntaxNode<'db>> {
        match self.data.id(db) {
            SyntaxNodeId::Child { parent, .. } => Some(*parent),
            SyntaxNodeId::Root(_) => None,
        }
    }

    /// Gets the grandparent syntax node, if any.
    /// This uses a cached parent when available, avoiding some database lookups.
    pub fn grandparent(self, db: &'db dyn Database) -> Option<SyntaxNode<'db>> {
        self.parent?.parent(db)
    }

    /// Checks if this syntax node is the root of the syntax tree.
    pub fn is_root(self) -> bool {
        self.parent.is_none()
    }

    /// Gets the stable pointer for this syntax node.
    pub fn stable_ptr(self, _db: &'db dyn Database) -> SyntaxStablePtrId<'db> {
        SyntaxStablePtrId(self)
    }

    pub fn raw_id(&self, db: &'db dyn Database) -> &'db SyntaxNodeId<'db> {
        self.data.id(db)
    }

    /// Gets the key fields of this syntax node. These define the unique identifier of the node.
    pub fn key_fields(self, db: &'db dyn Database) -> &'db [GreenId<'db>] {
        match self.data.id(db) {
            SyntaxNodeId::Child { key_fields, .. } => key_fields,
            SyntaxNodeId::Root(_) => &[],
        }
    }

    /// Returns the file id of the file containing this node.
    pub fn file_id(&self, db: &'db dyn Database) -> FileId<'db> {
        // Use cached parent if available to avoid database lookup
        if let Some(parent_data) = self.parent {
            return match parent_data.id(db) {
                SyntaxNodeId::Child { parent, .. } => parent.file_id(db),
                SyntaxNodeId::Root(file_id) => *file_id,
            };
        }
        match self.data.id(db) {
            SyntaxNodeId::Root(file_id) => *file_id,
            SyntaxNodeId::Child { .. } => {
                unreachable!("Parent already checked and found to not exist.")
            }
        }
    }

    /// Returns the `n`th parent of this syntax node.
    /// n = 0: returns itself.
    /// n = 1: return the parent.
    /// n = 2: return the grand parent.
    /// And so on...
    /// Assumes that the `n`th parent exists. Panics otherwise.
    pub fn nth_parent<'r: 'db>(&self, db: &'r dyn Database, mut n: usize) -> SyntaxNode<'db> {
        let mut result = Some(*self);
        while let Some(p) = result
            && n > 1
        {
            result = p.grandparent(db);
            n -= 2;
        }
        if let Some(p) = result
            && n == 1
        {
            result = p.parent(db);
        }
        result.unwrap_or_else(|| {
            panic!(
                "N'th parent did not exist. File {} Offset {:?}",
                self.file_id(db).long(db).full_path(db),
                self.offset(db)
            )
        })
    }
}

/// Creates a new syntax node. `offset_in_parent` must be relative to the parent (absolute for a
/// root) — see `SyntaxNodeData::offset_in_parent`.
pub fn new_syntax_node<'db>(
    db: &'db dyn Database,
    green: GreenId<'db>,
    offset_in_parent: TextOffset,
    id: SyntaxNodeId<'db>,
    kind: SyntaxKind,
) -> SyntaxNode<'db> {
    let parent = match &id {
        SyntaxNodeId::Child { parent, .. } => Some(*parent),
        SyntaxNodeId::Root(_) => None,
    };
    let data = SyntaxNodeData::new(db, green, offset_in_parent, id);
    let arena_root = parent
        .and_then(|parent| parent.arena_root)
        .or((kind == SyntaxKind::ExprBlock).then_some(data));
    SyntaxNode {
        data,
        arena_root,
        parent: parent.map(|parent| parent.data),
        kind,
        parent_kind: parent.map(|parent| parent.kind),
    }
}

/// Green-keyed query backing the *detached* root constructors. Keyed by `(file_id, green,
/// offset)`, it deduplicates roots built from the same green tree (so repeated detached
/// construction returns one node) and provides the tracked-function context salsa needs to mint a
/// root's tracked struct. Because the key includes `green`, a detached root's id changes whenever
/// the content does — fine for transient trees, but never use it for the canonical file tree
/// (see [`SyntaxNode::new_canonical_root`]).
#[salsa::tracked(returns(copy))]
fn new_detached_root_node<'db>(
    db: &'db dyn Database,
    file_id: FileId<'db>,
    green: GreenId<'db>,
    offset: TextOffset,
) -> SyntaxNode<'db> {
    let kind = green.long(db).kind;
    new_syntax_node(db, green, offset, SyntaxNodeId::Root(file_id), kind)
}

// Construction methods
impl<'a> SyntaxNode<'a> {
    /// Creates **the canonical root** for a file's syntax tree. Must be called only from the
    /// per-file parse query (`file_syntax_data`): the root's tracked struct is then seeded by that
    /// *file-keyed* query, so reparsing changed content reuses the same node ids instead of
    /// minting fresh ones. That id stability is what lets downstream early cutoff fire across
    /// edits. Every other consumer must obtain this tree via `db.file_syntax(file_id)`, not by
    /// constructing a root directly.
    pub fn new_canonical_root(
        db: &'a dyn Database,
        file_id: FileId<'a>,
        green: GreenId<'a>,
    ) -> Self {
        let kind = green.long(db).kind;
        new_syntax_node(db, green, TextOffset::START, SyntaxNodeId::Root(file_id), kind)
    }

    /// Creates a **detached** root: a standalone tree built directly from `green`, not unified with
    /// the file's canonical tree. For transient/standalone parses (proc-macro token streams,
    /// snippet formatting, tests) that have no per-file parse query to seed from. Its node ids are
    /// green-keyed, so they are *not* stable across content changes — do not use it to back a file
    /// that an editor mutates; use `db.file_syntax(file_id)` for that.
    pub fn new_detached_root(
        db: &'a dyn Database,
        file_id: FileId<'a>,
        green: GreenId<'a>,
    ) -> Self {
        new_detached_root_node(db, file_id, green, TextOffset::START)
    }

    /// A [`Self::new_detached_root`] with a custom initial offset, for embedding a standalone
    /// subtree (e.g. a macro expansion) at its position in the parent file.
    pub fn new_detached_root_with_offset(
        db: &'a dyn Database,
        file_id: FileId<'a>,
        green: GreenId<'a>,
        initial_offset: Option<TextOffset>,
    ) -> Self {
        new_detached_root_node(db, file_id, green, initial_offset.unwrap_or_default())
    }

    // Basic accessors

    /// Gets the width of this syntax node.
    pub fn width(&self, db: &dyn Database) -> TextWidth {
        self.green_node(db).width(db)
    }

    /// Gets the syntax kind of this node.
    pub fn kind(&self, _db: &dyn Database) -> SyntaxKind {
        self.kind
    }

    /// Gets the span of this syntax node.
    pub fn span(&self, db: &dyn Database) -> TextSpan {
        TextSpan::new_with_width(self.offset(db), self.width(db))
    }

    /// Returns the text of the token if this node is a token.
    pub fn text(&self, db: &'a dyn Database) -> Option<SmolStrId<'a>> {
        match &self.green_node(db).details {
            green::GreenNodeDetails::Token(text) => Some(*text),
            green::GreenNodeDetails::Node { .. } => None,
        }
    }

    /// Returns the green node of the syntax node.
    pub fn green_node(&self, db: &'a dyn Database) -> &'a GreenNode<'a> {
        self.data.green(db).long(db)
    }

    /// Returns whether the subtree rooted at this node contains a node of a missing kind, i.e.
    /// whether it had a parser error.
    pub fn contains_missing(&self, db: &'a dyn Database) -> bool {
        /// Whether the green subtree rooted at `green_id` contains a node of a missing kind.
        /// Walks the green tree directly - materializing the red tree just for this check would
        /// create (and memoize) a `SyntaxNode` per descendant. Memoized per green id, so shared
        /// subtrees are walked once.
        #[salsa::tracked(returns(copy))]
        fn query<'db>(db: &'db dyn Database, green_id: GreenId<'db>) -> bool {
            let node = green_id.long(db);
            node.kind.is_missing() || node.children().iter().any(|child| query(db, *child))
        }
        query(db, *self.data.green(db))
    }

    /// Returns the span of the syntax node without trivia.
    pub fn span_without_trivia(&self, db: &dyn Database) -> TextSpan {
        let green_node = self.green_node(db);
        let (leading, trailing) = both_trivia_width(db, green_node);
        let offset = self.offset(db);
        let start = offset.add_width(leading);
        let end = offset.add_width(green_node.width(db)).sub_width(trailing);
        TextSpan::new(start, end)
    }

    /// Gets the inner token from a terminal SyntaxNode. If the given node is not a terminal,
    /// returns None.
    pub fn get_terminal_token(&'a self, db: &'a dyn Database) -> Option<SyntaxNode<'a>> {
        let green_node = self.green_node(db);
        require(green_node.kind.is_terminal())?;
        // At this point we know we should have a second child which is the token.
        self.get_children(db).get(1).copied()
    }

    // Children and tree navigation

    /// Gets the children syntax nodes of the current node.
    pub fn get_children(&self, db: &'a dyn Database) -> &'a [SyntaxNode<'a>] {
        /// The children of every non-terminal node in the expression subtree rooted at `root`
        /// (an outermost expression block), materialized eagerly in one query. A single memo per
        /// body replaces a full salsa query (key lookup, sync-table claim, memo insert,
        /// dependency edge) per node, which dominated compilation profiles. Terminal subtrees
        /// (token + trivia, ~4/5 of all nodes) are rarely visited, so they stay lazy - served by
        /// the per-node [`node_children`] fallback.
        #[salsa::tracked(returns(ref))]
        fn red_tree<'db>(db: &'db dyn Database, root: SyntaxNodeData<'db>) -> RedTree<'db> {
            let root_node = SyntaxNode::from_data(db, root);
            let mut res = RedTree::default();
            // DFS is done so subtrees would occupy contiguous regions and tree-shaped consumers
            // stay local.
            let mut stack = vec![root_node];
            while let Some(node) = stack.pop() {
                if node.kind.is_terminal() {
                    continue;
                }
                let start = res.nodes.len();
                node.collect_children_into(db, &mut res.nodes);
                let end = res.nodes.len();
                res.ranges.insert(node.data, start as u32..end as u32);
                stack.extend(res.nodes[start..end].iter().rev().copied());
            }
            res
        }
        /// Lazy per-node fallback for nodes the arena does not cover (terminals and their
        /// descendants). Keyed on the tracked [`SyntaxNodeData`] struct, so the memo is attached
        /// to it; the wrapper's other fields are caches derived from `data`.
        #[salsa::tracked(returns(ref))]
        fn node_children<'db>(
            db: &'db dyn Database,
            data: SyntaxNodeData<'db>,
        ) -> Vec<SyntaxNode<'db>> {
            let node = SyntaxNode::from_data(db, data);
            let mut res = Vec::with_capacity(node.green_node(db).children().len());
            node.collect_children_into(db, &mut res);
            res
        }
        match self.arena_root {
            Some(arena_root) => {
                let tree = red_tree(db, arena_root);
                match tree.ranges.get(&self.data) {
                    Some(range) => &tree.nodes[range.start as usize..range.end as usize],
                    None => node_children(db, self.data).as_slice(),
                }
            }
            None => node_children(db, self.data).as_slice(),
        }
    }

    /// Appends this node's children to `res`.
    fn collect_children_into(&self, db: &'a dyn Database, res: &mut Vec<SyntaxNode<'a>>) {
        // Children offsets are relative to this node, so seeding from `TextOffset::START` (rather
        // than `self.offset(db)`) keeps `get_children` a pure function of the green tree.
        let mut offset = TextOffset::START;
        let self_green = self.green_node(db);
        let children = self_green.children();
        let mut key_map = Vec::<(_, usize)>::with_capacity(children.len());
        for green_id in children {
            let green = green_id.long(db);
            let width = green.width(db);
            let kind = green.kind;
            let rng = key_fields::key_fields_range(kind);
            let key_fields: &'a [GreenId<'a>] = &green.children()[rng];
            let index = key_map
                .iter_mut()
                .find(|(k, _v)| *k == (kind, key_fields))
                .map(|(_k, v)| {
                    let index = *v;
                    *v += 1;
                    index
                })
                .unwrap_or_else(|| {
                    key_map.push(((kind, key_fields), 1));
                    0
                });
            // Create the SyntaxNode view for the child.
            res.push(new_syntax_node(
                db,
                *green_id,
                offset,
                SyntaxNodeId::Child {
                    parent: *self,
                    kind,
                    index,
                    key_fields: Box::from(key_fields),
                },
                kind,
            ));

            offset = offset.add_width(width);
        }
    }

    // Text and span utilities

    /// Returns the start of the span of the syntax node without trivia.
    pub fn span_start_without_trivia(&self, db: &dyn Database) -> TextOffset {
        let green_node = self.green_node(db);
        let leading = leading_trivia_width(db, green_node);
        self.offset(db).add_width(leading)
    }

    /// Returns the end of the span of the syntax node without trivia.
    pub fn span_end_without_trivia(&self, db: &dyn Database) -> TextOffset {
        let green_node = self.green_node(db);
        let trailing = trailing_trivia_width(db, green_node);
        self.offset(db).add_width(green_node.width(db)).sub_width(trailing)
    }

    /// Looks up a syntax node using an offset.
    pub fn lookup_offset(&self, db: &'a dyn Database, offset: TextOffset) -> SyntaxNode<'a> {
        for child in self.get_children(db).iter() {
            if child.offset(db).add_width(child.width(db)) > offset {
                return child.lookup_offset(db, offset);
            }
        }
        *self
    }

    /// Looks up a syntax node using a position.
    pub fn lookup_position(&self, db: &'a dyn Database, position: TextPosition) -> SyntaxNode<'a> {
        match position.offset_in_file(db, self.stable_ptr(db).file_id(db)) {
            Some(offset) => self.lookup_offset(db, offset),
            None => *self,
        }
    }

    /// Returns all the text under the syntax node.
    pub fn get_text(&self, db: &'a dyn Database) -> &'a str {
        // A `None` return from reading the file content is only expected in the case of an IO
        // error. Since a SyntaxNode exists and is being processed, we should have already
        // successfully accessed this file earlier, therefore it should never fail.
        let file_content =
            db.file_content(self.stable_ptr(db).file_id(db)).expect("Failed to read file content");

        self.span(db).take(file_content)
    }

    /// Returns all the text under the syntax node.
    /// It traverses all the syntax tree of the node, but ignores functions and modules.
    /// We ignore those, because if there's some inner functions or modules, we don't want to get
    /// raw text of them. Comments inside them refer themselves directly, not this SyntaxNode.
    pub fn get_text_without_inner_commentable_children(&self, db: &dyn Database) -> String {
        let mut buffer = String::new();

        match &self.green_node(db).details {
            green::GreenNodeDetails::Token(text) => buffer.push_str(text.long(db)),
            green::GreenNodeDetails::Node { .. } => {
                for child in self.get_children(db).iter() {
                    let kind = child.kind(db);

                    // Checks all the items that the inner comment can be bubbled to (implementation
                    // function is also a FunctionWithBody).
                    if !matches!(
                        kind,
                        SyntaxKind::FunctionWithBody
                            | SyntaxKind::ItemModule
                            | SyntaxKind::TraitItemFunction
                    ) {
                        buffer.push_str(&SyntaxNode::get_text_without_inner_commentable_children(
                            child, db,
                        ));
                    }
                }
            }
        }
        buffer
    }

    /// Returns all the text of the item without comments trivia.
    /// It traverses all the syntax tree of the node.
    pub fn get_text_without_all_comment_trivia(&self, db: &dyn Database) -> String {
        let mut buffer = String::new();

        match &self.green_node(db).details {
            green::GreenNodeDetails::Token(text) => buffer.push_str(text.long(db)),
            green::GreenNodeDetails::Node { .. } => {
                for child in self.get_children(db).iter() {
                    if let Some(trivia) = ast::Trivia::cast(db, *child) {
                        trivia.elements(db).for_each(|element| {
                            if !matches!(
                                element,
                                ast::Trivium::SingleLineComment(_)
                                    | ast::Trivium::SingleLineDocComment(_)
                                    | ast::Trivium::SingleLineInnerComment(_)
                            ) {
                                buffer.push_str(
                                    &element
                                        .as_syntax_node()
                                        .get_text_without_all_comment_trivia(db),
                                );
                            }
                        });
                    } else {
                        buffer
                            .push_str(&SyntaxNode::get_text_without_all_comment_trivia(child, db));
                    }
                }
            }
        }
        buffer
    }

    /// Returns all the text under the syntax node, without the outmost trivia (the leading trivia
    /// of the first token and the trailing trivia of the last token).
    ///
    /// Note that this traverses the syntax tree, and generates a new string, so use responsibly.
    pub fn get_text_without_trivia(self, db: &'a dyn Database) -> SmolStrId<'a> {
        let file_content =
            db.file_content(self.stable_ptr(db).file_id(db)).expect("Failed to read file content");
        SmolStrId::from(db, self.span_without_trivia(db).take(file_content))
    }

    /// Returns the text under the syntax node, according to the given span.
    ///
    /// `span` is assumed to be contained within the span of self.
    ///
    /// Note that this traverses the syntax tree, and generates a new string, so use responsibly.
    pub fn get_text_of_span(self, db: &'a dyn Database, span: TextSpan) -> &'a str {
        assert!(self.span(db).contains(span));
        let file_content =
            db.file_content(self.stable_ptr(db).file_id(db)).expect("Failed to read file content");
        span.take(file_content)
    }

    // Tree traversal iterators

    /// Traverse the subtree rooted at the current node (including the current node) in preorder.
    ///
    /// This is a shortcut for [`Self::preorder`] paired with filtering for [`WalkEvent::Enter`]
    /// events only.
    pub fn descendants(&self, db: &'a dyn Database) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
        self.preorder(db).filter_map(|event| match event {
            WalkEvent::Enter(node) => Some(node),
            WalkEvent::Leave(_) => None,
        })
    }

    /// Traverse the subtree rooted at the current node (including the current node) in preorder,
    /// excluding tokens.
    pub fn preorder(&self, db: &'a dyn Database) -> Preorder<'a> {
        Preorder::new(*self, db)
    }

    /// Gets all the leaves of the SyntaxTree, where the self node is the root of a tree.
    pub fn tokens(&self, db: &'a dyn Database) -> impl Iterator<Item = Self> + 'a {
        self.preorder(db).filter_map(|event| match event {
            WalkEvent::Enter(node) if node.kind(db).is_terminal() => Some(node),
            _ => None,
        })
    }

    /// Mirror of [`TypedSyntaxNode::cast`].
    pub fn cast<T: TypedSyntaxNode<'a>>(self, db: &'a dyn Database) -> Option<T> {
        T::cast(db, self)
    }

    // Ancestor queries

    /// Creates an iterator that yields ancestors of this syntax node.
    pub fn ancestors(&self, db: &'a dyn Database) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
        // We aren't reusing `ancestors_with_self` here to avoid cloning this node.
        std::iter::successors(self.parent(db), |n| n.parent(db))
    }

    /// Creates an iterator that yields this syntax node and walks up its ancestors.
    pub fn ancestors_with_self(
        &self,
        db: &'a dyn Database,
    ) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
        std::iter::successors(Some(*self), |n| n.parent(db))
    }

    /// Checks whether this syntax node is strictly above the given syntax node in the syntax tree.
    pub fn is_ancestor(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
        node.ancestors(db).any(|n| n == *self)
    }

    /// Checks whether this syntax node is strictly under the given syntax node in the syntax tree.
    pub fn is_descendant(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
        node.is_ancestor(db, self)
    }

    /// Checks whether this syntax node is or is above the given syntax node in the syntax tree.
    pub fn is_ancestor_or_self(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
        node.ancestors_with_self(db).any(|n| n == *self)
    }

    /// Checks whether this syntax node is or is under the given syntax node in the syntax tree.
    pub fn is_descendant_or_self(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
        node.is_ancestor_or_self(db, self)
    }

    // Specific ancestor/parent queries

    /// Finds the first ancestor of a given kind.
    pub fn ancestor_of_kind(
        &self,
        db: &'a dyn Database,
        kind: SyntaxKind,
    ) -> Option<SyntaxNode<'a>> {
        self.ancestors(db).find(|node| node.kind(db) == kind)
    }

    /// Finds the first ancestor of a given kind and returns it in typed form.
    pub fn ancestor_of_type<T: TypedSyntaxNode<'a>>(&self, db: &'a dyn Database) -> Option<T> {
        self.ancestors(db).find_map(|node| T::cast(db, node))
    }

    /// Finds the parent of a given kind.
    pub fn parent_of_kind(&self, db: &'a dyn Database, kind: SyntaxKind) -> Option<SyntaxNode<'a>> {
        self.parent(db).filter(|node| node.kind(db) == kind)
    }

    /// Finds the parent of a given kind and returns it in typed form.
    pub fn parent_of_type<T: TypedSyntaxNode<'a>>(&self, db: &'a dyn Database) -> Option<T> {
        self.parent(db).and_then(|node| T::cast(db, node))
    }

    /// Finds the first parent of one of the kinds.
    pub fn ancestor_of_kinds(
        &self,
        db: &'a dyn Database,
        kinds: &[SyntaxKind],
    ) -> Option<SyntaxNode<'a>> {
        self.ancestors(db).find(|node| kinds.contains(&node.kind(db)))
    }

    /// Gets the kind of the given node's parent if it exists.
    pub fn parent_kind(&self, _db: &dyn Database) -> Option<SyntaxKind> {
        self.parent_kind
    }

    /// Gets the kind of the given node's grandparent if it exists.
    pub fn grandparent_kind(&self, db: &dyn Database) -> Option<SyntaxKind> {
        self.parent(db)?.parent_kind(db)
    }

    /// Gets the kind of the given node's grandgrandparent if it exists.
    pub fn grandgrandparent_kind(&self, db: &dyn Database) -> Option<SyntaxKind> {
        self.grandparent(db)?.parent_kind(db)
    }
}

/// Trait for the typed view of the syntax tree. All the internal node implementations are under
/// the ast module.
pub trait TypedSyntaxNode<'a>: Sized {
    /// The relevant SyntaxKind. None for enums.
    const OPTIONAL_KIND: Option<SyntaxKind>;
    type StablePtr: TypedStablePtr<'a>;
    type Green;
    fn missing(db: &'a dyn Database) -> Self::Green;
    fn from_syntax_node(db: &'a dyn Database, node: SyntaxNode<'a>) -> Self;
    fn cast(db: &'a dyn Database, node: SyntaxNode<'a>) -> Option<Self>;
    fn as_syntax_node(&self) -> SyntaxNode<'a>;
    fn stable_ptr(&self, db: &'a dyn Database) -> Self::StablePtr;
}

pub trait Token<'a>: TypedSyntaxNode<'a> {
    fn new_green(db: &'a dyn Database, text: SmolStrId<'a>) -> Self::Green;
    fn text(&self, db: &'a dyn Database) -> SmolStrId<'a>;
}

pub trait Terminal<'a>: TypedSyntaxNode<'a> {
    const KIND: SyntaxKind;
    type TokenType: Token<'a>;
    fn new_green(
        db: &'a dyn Database,
        leading_trivia: TriviaGreen<'a>,
        token: <<Self as Terminal<'a>>::TokenType as TypedSyntaxNode<'a>>::Green,
        trailing_trivia: TriviaGreen<'a>,
    ) -> <Self as TypedSyntaxNode<'a>>::Green;
    /// Returns the text of the token of this terminal (excluding the trivia).
    fn text(&self, db: &'a dyn Database) -> SmolStrId<'a>;
    /// Casts a syntax node to this terminal type's token and then walks up to return the terminal.
    fn cast_token(db: &'a dyn Database, node: SyntaxNode<'a>) -> Option<Self> {
        if node.kind(db) == Self::TokenType::OPTIONAL_KIND? {
            Some(Self::from_syntax_node(db, node.parent(db)?))
        } else {
            None
        }
    }
}

/// Trait for stable pointers to syntax nodes.
pub trait TypedStablePtr<'a> {
    type SyntaxNode: TypedSyntaxNode<'a>;
    /// Returns the syntax node pointed to by this stable pointer.
    fn lookup(&self, db: &'a dyn Database) -> Self::SyntaxNode;
    /// Returns the untyped stable pointer.
    fn untyped(self) -> SyntaxStablePtrId<'a>;
}

/// Returns the width of the leading trivia of the given green node.
fn leading_trivia_width<'a>(db: &'a dyn Database, green: &GreenNode<'a>) -> TextWidth {
    match &green.details {
        green::GreenNodeDetails::Token(_) => TextWidth::default(),
        green::GreenNodeDetails::Node { children, width } => {
            if *width == TextWidth::default() {
                return TextWidth::default();
            }
            if green.kind.is_terminal() {
                return children[0].long(db).width(db);
            }
            let non_empty = find_non_empty_child(db, &mut children.iter())
                .expect("Parent width non-empty - one of the children should be non-empty");
            leading_trivia_width(db, non_empty)
        }
    }
}

/// Returns the width of the trailing trivia of the given green node.
fn trailing_trivia_width<'a>(db: &'a dyn Database, green: &GreenNode<'a>) -> TextWidth {
    match &green.details {
        green::GreenNodeDetails::Token(_) => TextWidth::default(),
        green::GreenNodeDetails::Node { children, width } => {
            if *width == TextWidth::default() {
                return TextWidth::default();
            }
            if green.kind.is_terminal() {
                return children[2].long(db).width(db);
            }
            let non_empty = find_non_empty_child(db, &mut children.iter().rev())
                .expect("Parent width non-empty - one of the children should be non-empty");
            trailing_trivia_width(db, non_empty)
        }
    }
}

/// Returns the width of the leading and trailing trivia of the given green node.
fn both_trivia_width<'a>(db: &'a dyn Database, green: &GreenNode<'a>) -> (TextWidth, TextWidth) {
    match &green.details {
        green::GreenNodeDetails::Token(_) => (TextWidth::default(), TextWidth::default()),
        green::GreenNodeDetails::Node { children, width } => {
            if *width == TextWidth::default() {
                return (TextWidth::default(), TextWidth::default());
            }
            if green.kind.is_terminal() {
                return (children[0].long(db).width(db), children[2].long(db).width(db));
            }
            let mut iter = children.iter();
            let first_non_empty = find_non_empty_child(db, &mut iter)
                .expect("Parent width non-empty - one of the children should be non-empty");
            if let Some(last_non_empty) = find_non_empty_child(db, &mut iter.rev()) {
                (
                    leading_trivia_width(db, first_non_empty),
                    trailing_trivia_width(db, last_non_empty),
                )
            } else {
                both_trivia_width(db, first_non_empty)
            }
        }
    }
}

/// Finds the first non-empty child in the given iterator.
fn find_non_empty_child<'a>(
    db: &'a dyn Database,
    child_iter: &mut impl Iterator<Item = &'a GreenId<'a>>,
) -> Option<&'a GreenNode<'a>> {
    child_iter.find_map(|child| {
        let child = child.long(db);
        (child.width(db) != TextWidth::default()).then_some(child)
    })
}