yak_sitter/

lib.rs

use std::cmp::Ordering;
use std::collections::Bound;
use std::error::Error;
use std::fmt::{Debug, Display, Formatter};
use std::hash::{Hash, Hasher};
use std::iter::{once, FusedIterator, Once};
use std::ops::{BitAnd, BitOr, BitOrAssign, RangeBounds};
#[cfg(unix)]
use std::os::unix::io::AsRawFd;
#[cfg(windows)]
use std::os::windows::io::AsRawHandle;
use std::path::{Path, PathBuf};
use std::ptr::NonNull;
use std::str::Utf8Error;
use streaming_iterator::StreamingIterator;
use utf8_error_offset_by::Utf8ErrorOffsetBy;

mod utf8_error_offset_by;

/// A tree that represents the syntactic structure of a source code file.
///
/// It stores its text and filepath, and uses and is used by other [`yak_sitter`](crate) wrappers.
#[derive(Clone, Debug)]
pub struct Tree {
    tree: tree_sitter::Tree,
    byte_text: Vec<u8>,
    path: Option<PathBuf>,
}

/// A single node on a syntax [`Tree`].
///
/// It can access its text and filepath, and uses and is used by other [`yak_sitter`](crate)
/// wrappers.
#[derive(Clone, Copy)]
pub struct Node<'tree> {
    node: tree_sitter::Node<'tree>,
    tree: &'tree Tree,
}

/// Raw pointer equivalent of [`Node`]
#[derive(Clone, Copy)]
pub struct NodePtr {
    node_data: TsNodePtr,
    tree: NonNull<Tree>,
}

/// Taken straight from [`tree_sitter::ffi::TSNode`]. This must maintain the same layout
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[repr(C)]
struct TsNodePtr {
    context: [u32; 4usize],
    id: *const (),
    tree: *const (),
}

/// Wrapper around `usize` (aka node id)
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[repr(transparent)]
pub struct NodeId(usize);

/// A stateful object for walking a syntax tree efficiently.
///
/// Unlike tree-sitter's cursor, it go outside of its "local" node, albeit with degraded
/// performance.
#[derive(Clone)]
pub struct TreeCursor<'tree> {
    cursor: tree_sitter::TreeCursor<'tree>,
    tree: &'tree Tree,
    child_depth: usize,
}

/// Wrapper around [`tree_sitter::QueryCursor`]
pub struct QueryCursor {
    query_cursor: tree_sitter::QueryCursor,
}

/// Wrapper around [`tree_sitter::QueryMatches`].
///
/// [`tree_sitter::QueryMatches`] is NOT a real iterator, it's a [`StreamingIterator`] (see
///     <https://github.com/tree-sitter/tree-sitter/issues/608>). Therefore this doesn't implement
///     [`Iterator`].
pub struct QueryMatches<'query, 'tree> {
    query_matches: tree_sitter::QueryMatches<'query, 'tree, &'tree Tree, &'tree str>,
    current_match: Option<QueryMatch<'query, 'tree>>,
    query: &'query Query,
    tree: &'tree Tree,
}

/// Wrapper around [`tree_sitter::QueryMatch`]
pub struct QueryMatch<'query, 'tree> {
    query_match: *const tree_sitter::QueryMatch<'query, 'tree>,
    query: &'query Query,
    tree: &'tree Tree,
}

/// Wrapper around [`tree_sitter::QueryCaptures`]
pub struct QueryCaptures<'query, 'tree> {
    query_captures: tree_sitter::QueryCaptures<'query, 'tree, &'tree Tree, &'tree str>,
    query: &'query Query,
    tree: &'tree Tree,
}

/// Wrapper around [`tree_sitter::QueryCapture`]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct QueryCapture<'query, 'tree> {
    pub node: Node<'tree>,
    pub index: usize,
    pub name: &'query str,
}

/// Variant of [`std::ops::Range`] that can be copied and displays as `:line:column-:line:column`
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct PointRange {
    pub start: Point,
    pub end: Point,
}

/// Structurally identical to [`tree_sitter::Point`] but displays as `:line:column`
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Point {
    pub row: usize,
    pub column: usize,
}

/// Structurally identical to [`tree_sitter::Range`] (byte and point range) but displays as
/// `:line:column-:line:column`
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Range {
    pub start_byte: usize,
    pub end_byte: usize,
    pub start_point: Point,
    pub end_point: Point,
}

/// A stateful object that this is used to produce a Tree based on some source code
#[repr(transparent)]
pub struct Parser(tree_sitter::Parser);

/// An opaque object that defines how to parse a particular language.
///
/// The code for each Language is generated by the Tree-sitter CLI.
pub type Language = tree_sitter::Language;
/// Re-exports [`tree_sitter::LanguageRef`]
pub type LanguageRef<'a> = tree_sitter::LanguageRef<'a>;
/// An error that occurred when trying to assign an incompatible [`Language`] to a [`Parser`]
pub type LanguageError = tree_sitter::LanguageError;
/// A set of patterns that match nodes in a syntax tree
pub type Query = tree_sitter::Query;
/// A key-value pair associated with a particular pattern in a [`Query`]
pub type QueryProperty = tree_sitter::QueryProperty;
/// An error that occurred in [`Parser::set_included_ranges`]
pub type IncludedRangesError = tree_sitter::IncludedRangesError;
/// A summary of a change to a text document
pub type InputEdit = tree_sitter::InputEdit;

/// Error from parsing a tree
#[derive(Debug)]
pub enum TreeParseError {
    IO(std::io::Error),
    ParsingFailed,
    NotUtf8(Utf8Error),
}

/// Describes the previous traversal action in a pre-order traversal which iterates nodes with
/// children both up and down, so we can get the next node in the traversal
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum TraversalState {
    Start,
    Down,
    Right,
    Up,
    End,
}

/// Iterator over a tree in pre-order traversal which iterates nodes with children both up and down
#[derive(Clone)]
pub struct PreorderTraversal<'tree> {
    cursor: TreeCursor<'tree>,
    last_state: TraversalState,
}

/// Iterated node in a traversal (includes field name and last state)
#[derive(Clone, Copy, Debug)]
pub struct TraversalItem<'tree> {
    /// The node
    pub node: Node<'tree>,
    /// The node's field name
    pub field_name: Option<&'static str>,
    /// Last traversal state to reach this node
    pub last_state: TraversalState,
}

impl Parser {
    /// Create a new parser for the given language. See [`tree_sitter::Parser::set_language`]
    #[inline]
    pub fn new(language: &Language) -> Result<Self, LanguageError> {
        let mut parser = tree_sitter::Parser::new();
        parser.set_language(language)?;
        Ok(Self(parser))
    }

    /// Set the language of the parser. See [`tree_sitter::Parser::set_language`]
    #[inline]
    pub fn set_language(&mut self, language: &Language) -> Result<(), LanguageError> {
        self.0.set_language(language)
    }

    /// Set the ranges of text the parser should include when parsing. See
    /// [`tree_sitter::Parser::set_included_ranges`]
    #[inline]
    pub fn set_included_ranges(&mut self, ranges: &[Range]) -> Result<(), IncludedRangesError> {
        let ranges = ranges
            .iter()
            .copied()
            .map(tree_sitter::Range::from)
            .collect::<Vec<_>>();
        self.0.set_included_ranges(&ranges)
    }

    /// Parse a file. See [`tree_sitter::Parser::parse`].
    ///
    /// Additionally, file must be valid utf-8 or this will return `Err`. The file's path is used
    /// for stable node comparison between trees.
    #[inline]
    pub fn parse_file(
        &mut self,
        path: &Path,
        old_tree: Option<&Tree>,
    ) -> Result<Tree, TreeParseError> {
        let byte_text = std::fs::read(path)?;
        self.parse_bytes(byte_text, Some(path), old_tree)
    }

    /// Parse a string. See [`tree_sitter::Parser::parse`].
    ///
    /// The path is stored as metadata that can be accessed from nodes. If you don't need this, pass
    /// `None`.
    #[inline]
    pub fn parse_string(
        &mut self,
        text: String,
        path: Option<&Path>,
        old_tree: Option<&Tree>,
    ) -> Result<Tree, TreeParseError> {
        self.parse_bytes(text.into_bytes(), path, old_tree)
    }

    /// Parse a byte string. See [`tree_sitter::Parser::parse`].
    ///
    /// Note that the wrappers expect and assume UTF-8, so this will fail if the text is not valid
    /// UTF-8.
    ///
    /// The path is stored as metadata that can be accessed from nodes. If you don't need this, pass
    /// `None`.
    #[inline]
    pub fn parse_bytes(
        &mut self,
        byte_text: Vec<u8>,
        path: Option<&Path>,
        old_tree: Option<&Tree>,
    ) -> Result<Tree, TreeParseError> {
        let tree = self
            .0
            .parse(&byte_text, old_tree.map(|t| &t.tree))
            .ok_or(TreeParseError::ParsingFailed)?;
        Ok(Tree::new(tree, byte_text, path.map(|p| p.to_path_buf()))?)
    }
}

impl Tree {
    /// Wrap the tree and its associated text.
    ///
    /// Note that the wrappers expect and assume UTF-8, so this returns `Err` if the text is not
    /// valid UTF-8.
    #[inline]
    fn new(
        tree: tree_sitter::Tree,
        byte_text: Vec<u8>,
        path: Option<PathBuf>,
    ) -> Result<Self, Utf8Error> {
        Self::validate_utf8(&tree, &byte_text)?;
        Ok(Self {
            tree,
            byte_text,
            path,
        })
    }

    fn validate_utf8(tree: &tree_sitter::Tree, byte_text: &[u8]) -> Result<(), Utf8Error> {
        let _ = std::str::from_utf8(byte_text)?;
        let mut cursor = tree.walk();
        let mut went_up = false;
        while (!went_up && cursor.goto_first_child()) || cursor.goto_next_sibling() || {
            went_up = true;
            cursor.goto_parent()
        } {
            let node = cursor.node();
            let range = node.byte_range();
            let _ = std::str::from_utf8(&byte_text[range])
                .map_err(|e| e.offset_by(node.start_byte()))?;
        }
        Ok(())
    }

    /// Get the underlying text. This includes text which isn't in the [`Self::included_ranges`]
    #[inline]
    pub fn text(&self) -> &str {
        // SAFETY: we ran validate_utf8 before constructing so the text is valid UTF-8
        unsafe { std::str::from_utf8_unchecked(&self.byte_text) }
    }

    /// Get the path the tree is associated with, if any.
    ///
    /// The path may be virtual, it's used for stable node comparison between trees.
    #[inline]
    pub fn path(&self) -> Option<&Path> {
        self.path.as_deref()
    }

    /// Get the root node.
    #[inline]
    pub fn root_node(&self) -> Node<'_> {
        // SAFETY: The node is from this tree
        unsafe { Node::new(self.tree.root_node(), self) }
    }

    /// Create a cursor starting at the root node
    #[inline]
    pub fn walk(&self) -> TreeCursor<'_> {
        TreeCursor::new(self.tree.walk(), self, true)
    }

    /// Get the included ranges used to parse the tree
    #[inline]
    pub fn included_ranges(&self) -> Vec<Range> {
        self.tree
            .included_ranges()
            .into_iter()
            .map(Range::from)
            .collect()
    }

    /// Get the changed ranges. See [`tree_sitter::Tree::changed_ranges`]
    #[inline]
    pub fn changed_ranges(&self, other: &Tree) -> impl ExactSizeIterator<Item = Range> {
        self.tree.changed_ranges(&other.tree).map(Range::from)
    }

    /// Get the language used to parse the tree.
    #[inline]
    pub fn language(&self) -> LanguageRef<'_> {
        self.tree.language()
    }

    //noinspection RsIncorrectFunctionArgumentCount - IntelliJ inspection bug.
    /// Print a dot graph of the tree to the given file. See [`tree_sitter::Tree::print_dot_graph`]
    #[inline]
    pub fn print_dot_graph(
        &self,
        #[cfg(unix)] file: &impl AsRawFd,
        #[cfg(windows)] file: &impl AsRawHandle,
    ) {
        self.tree.print_dot_graph(file)
    }

    /// Edit the tree. See [`tree_sitter::Tree::edit`]
    #[inline]
    pub fn edit(&mut self, edit: &InputEdit) {
        self.tree.edit(edit)
    }
}

impl<'tree> tree_sitter::TextProvider<&'tree str> for &'tree Tree {
    type I = Once<&'tree str>;

    #[inline]
    fn text(&mut self, node: tree_sitter::Node<'_>) -> Self::I {
        // SAFETY: we ran validate_utf8 before constructing so every node's text is valid UTF-8
        once(unsafe { std::str::from_utf8_unchecked(&self.byte_text[node.byte_range()]) })
    }
}

impl<'tree> Node<'tree> {
    /// Wrap a [`tree_sitter::Node`]. Requires its associated [`Tree`] for convenience methods.
    ///
    /// # Safety
    /// The node must be from the given tree.
    #[inline]
    pub unsafe fn new(node: tree_sitter::Node<'tree>, tree: &'tree Tree) -> Self {
        Self { node, tree }
    }

    /// Gets the node id, which is represented by its address.
    ///
    /// Nodes from separate trees are guaranteed to have different ids iff both trees are alive, but
    /// a node which is no longer alive may have the same id as a different node which is. The
    /// tree-sitter docs specify that a if a tree is created from an older tree, nodes may be reused
    /// and from the old tree and these will have the same id.
    ///
    /// See [`tree_sitter::Node::id`].
    #[inline]
    pub fn id(&self) -> NodeId {
        NodeId::of_ts(self.node)
    }

    /// Get the node's kind. See [`tree_sitter::Node::kind`]
    #[inline]
    pub fn kind(&self) -> &'static str {
        self.node.kind()
    }

    /// Check if the node is named. See [`tree_sitter::Node::is_named`]
    #[inline]
    pub fn is_named(&self) -> bool {
        self.node.is_named()
    }

    /// Check if the node is missing. See [`tree_sitter::Node::is_missing`]
    #[inline]
    pub fn is_missing(&self) -> bool {
        self.node.is_missing()
    }

    /// Check if the node is extra. See [`tree_sitter::Node::is_extra`]
    #[inline]
    pub fn is_extra(&self) -> bool {
        self.node.is_extra()
    }

    /// Check if the node is an error. See [`tree_sitter::Node::is_error`]
    #[inline]
    pub fn is_error(&self) -> bool {
        self.node.is_error()
    }

    /// Check if the node has an error. See [`tree_sitter::Node::has_error`]
    #[inline]
    pub fn has_error(&self) -> bool {
        self.node.has_error()
    }

    /// Check if the node has changes. See [`tree_sitter::Node::has_changes`]
    #[inline]
    pub fn has_changes(&self) -> bool {
        self.node.has_changes()
    }

    /// Edit the node. See [`tree_sitter::Node::edit`]
    #[inline]
    pub fn edit(&mut self, edit: &InputEdit) {
        self.node.edit(edit)
    }

    /// Get the byte offsets where this node starts
    #[inline]
    pub fn start_byte(&self) -> usize {
        self.node.start_byte()
    }

    /// Get the byte offsets where this node ends
    #[inline]
    pub fn end_byte(&self) -> usize {
        self.node.end_byte()
    }

    /// Get the row and column where this node starts
    #[inline]
    pub fn start_position(&self) -> Point {
        Point::from(self.node.start_position())
    }

    /// Get the row and column where this node ends
    #[inline]
    pub fn end_position(&self) -> Point {
        Point::from(self.node.end_position())
    }

    /// Get the byte range where this node is located
    #[inline]
    pub fn byte_range(&self) -> std::ops::Range<usize> {
        self.node.byte_range()
    }

    /// Get the row and column range where this node is located
    #[inline]
    pub fn position_range(&self) -> PointRange {
        PointRange {
            start: self.start_position(),
            end: self.end_position(),
        }
    }

    /// Get the byte range and row and column range where this node is located
    #[inline]
    pub fn range(&self) -> Range {
        Range::from(self.node.range())
    }

    /// Get the node's text as a byte string.
    ///
    /// **Warning:** the return value is unspecified if the tree is edited.
    #[inline]
    fn byte_text(&self) -> &'tree [u8] {
        &self.tree.byte_text[self.byte_range()]
    }

    /// Get the node's text.
    ///
    /// **Warning:** the return value is unspecified if the tree is edited.
    #[inline]
    pub fn text(&self) -> &'tree str {
        // SAFETY: we ran validate_utf8 before constructing so every node's text is valid UTF-8
        unsafe { std::str::from_utf8_unchecked(self.byte_text()) }
    }

    /// Path of the node's tree.
    ///
    /// This is the virtual path set on the tree's creation, used primarily for consistent ordering.
    #[inline]
    pub fn path(&self) -> Option<&'tree Path> {
        self.tree.path()
    }

    /// Get the node's named and unnamed children. See [`tree_sitter::Node::children`]
    #[inline]
    pub fn all_children<'a>(
        &self,
        cursor: &'a mut TreeCursor<'tree>,
    ) -> impl ExactSizeIterator<Item = Node<'tree>> + 'a {
        let tree = self.tree;
        // SAFETY: Same tree
        self.node
            .children(&mut cursor.cursor)
            .map(move |node| unsafe { Node::new(node, tree) })
    }

    /// Get the node's named children. See [`tree_sitter::Node::named_children`]
    #[inline]
    pub fn named_children<'a>(
        &self,
        cursor: &'a mut TreeCursor<'tree>,
    ) -> impl ExactSizeIterator<Item = Node<'tree>> + 'a {
        let tree = self.tree;
        // SAFETY: Same tree
        self.node
            .named_children(&mut cursor.cursor)
            .map(move |node| unsafe { Node::new(node, tree) })
    }

    /// Get the number of (named and unnamed) children
    #[inline]
    pub fn child_count(&self) -> usize {
        self.node.child_count()
    }

    /// Get the number of named children
    #[inline]
    pub fn named_child_count(&self) -> usize {
        self.node.named_child_count()
    }

    /// Get the node's immediate parent
    #[inline]
    pub fn parent(&self) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .parent()
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's immediate next (named or unnamed) sibling
    #[inline]
    pub fn next_sibling(&self) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .next_sibling()
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's immediate next named sibling
    #[inline]
    pub fn next_named_sibling(&self) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .next_named_sibling()
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's immediate previous (named or unnamed) sibling
    #[inline]
    pub fn prev_sibling(&self) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .prev_sibling()
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's immediate previous named sibling
    #[inline]
    pub fn prev_named_sibling(&self) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .prev_named_sibling()
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's (named or unnamed) child at the given index. See [`tree_sitter::Node::child`]
    #[inline]
    pub fn child(&self, i: usize) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .child(u32::try_from(i).ok()?)
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's named child at the given index. See [`tree_sitter::Node::named_child`]
    #[inline]
    pub fn named_child(&self, i: usize) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .named_child(i.try_into().ok()?)
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's last (named or unnamed) child
    #[inline]
    pub fn last_child(&self) -> Option<Node<'tree>> {
        // .child is already bounds-checked so we use wrapping_sub for iff the count is 0
        self.child(self.child_count().wrapping_sub(1))
    }

    /// Get the node's last named child
    #[inline]
    pub fn last_named_child(&self) -> Option<Node<'tree>> {
        // .named_child is already bounds-checked so we use wrapping_sub for iff the count is 0
        self.named_child(self.named_child_count().wrapping_sub(1))
    }

    /// Get the node's first child of the given kind, named or unnamed.
    ///
    /// The cursor is used to iterate the node's immediate children in order to find said child.
    #[inline]
    pub fn child_of_kind(&self, kind: &str, cursor: &mut TreeCursor<'tree>) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .named_children(&mut cursor.cursor)
            .find(|node| node.kind() == kind)
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's children of the given kind, named or unnamed.
    ///
    /// The cursor is used to iterate the node's immediate children in order to find said child.
    #[inline]
    pub fn children_of_kind<'a>(
        &self,
        kind: &'a str,
        cursor: &'a mut TreeCursor<'tree>,
    ) -> impl Iterator<Item = Node<'tree>> + 'a {
        // SAFETY: Same tree
        self.node
            .named_children(&mut cursor.cursor)
            .filter(move |node| node.kind() == kind)
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the first child with the given field name
    #[inline]
    pub fn child_by_field_name(&self, field_name: &str) -> Option<Node<'tree>> {
        // SAFETY: Same tree
        self.node
            .child_by_field_name(field_name)
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the node's children with the given field name
    #[inline]
    pub fn children_by_field_name<'a>(
        &self,
        field_name: &str,
        c: &'a mut TreeCursor<'tree>,
    ) -> impl Iterator<Item = Node<'tree>> + 'a {
        // SAFETY: Same tree
        self.node
            .children_by_field_name(field_name, &mut c.cursor)
            .map(|node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the field name of the child at the given index
    #[inline]
    pub fn field_name_for_child(&self, i: usize) -> Option<&'static str> {
        self.node.field_name_for_child(i as u32)
    }

    /// Get the field name of the named child at the given index
    #[inline]
    pub fn field_name_for_named_child(&self, i: usize) -> Option<&'static str> {
        self.node.field_name_for_named_child(i as u32)
    }

    /// Get the node's field name.
    ///
    /// This is done by looking at the parent's children and finding the one that matches this node,
    /// then returning its field name, hence the need for a cursor.
    pub fn field_name(&self, cursor: &mut TreeCursor<'tree>) -> Option<&'static str> {
        self.parent().and_then(|parent| {
            let i = parent
                .all_children(cursor)
                .position(|x| x == *self)
                .expect("node not one of its parent's children");
            parent.field_name_for_child(i)
        })
    }

    /// Get a [`TreeCursor`] that points to this node.
    ///
    /// Unlike tree-sitter's cursors, this one can also reach its siblings and parents, albeit with
    /// degraded performance.
    #[inline]
    pub fn walk(&self) -> TreeCursor<'tree> {
        TreeCursor::new(self.node.walk(), self.tree, false)
    }

    /// Print the node as an s-expression
    #[inline]
    pub fn to_sexp(&self) -> String {
        self.node.to_sexp()
    }

    /// Get a raw pointer to this node (remove the `'tree` lifetime)
    #[inline]
    pub fn to_ptr(&self) -> NodePtr {
        NodePtr {
            node_data: TsNodePtr::from(self.node),
            tree: NonNull::from(self.tree),
        }
    }
}

impl<'tree> PartialEq for Node<'tree> {
    #[inline]
    fn eq(&self, other: &Node<'tree>) -> bool {
        self.id() == other.id()
    }
}

impl<'tree> Eq for Node<'tree> {}

impl<'tree> PartialOrd for Node<'tree> {
    /// If not equal, compares based on source position, then filepath, then address.
    #[inline]
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<'tree> Ord for Node<'tree> {
    /// If not equal, compares based on source position, then filepath, then address.
    fn cmp(&self, other: &Self) -> Ordering {
        if self.id() == other.id() {
            Ordering::Equal
        } else if std::ptr::eq(self.tree as *const _, other.tree as *const _) {
            self.start_byte()
                .cmp(&other.start_byte())
                .then(self.end_byte().cmp(&other.end_byte()))
        } else {
            self.path()
                .cmp(&other.path())
                .then(self.id().0.cmp(&other.id().0))
        }
    }
}

impl<'tree> Hash for Node<'tree> {
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id().hash(state)
    }
}

impl NodePtr {
    /// Converts this node pointer back into a "node", i.e., node reference.
    ///
    /// # Safety
    /// You must ensure that the tree the node came from is alive.
    #[inline]
    pub unsafe fn to_node<'a>(self) -> Node<'a> {
        Node {
            node: self.node_data.to_node(),
            tree: self.tree.as_ref(),
        }
    }
}

impl PartialEq for NodePtr {
    #[inline]
    fn eq(&self, other: &NodePtr) -> bool {
        self.node_data == other.node_data
    }
}

impl Eq for NodePtr {}

impl Hash for NodePtr {
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.node_data.hash(state)
    }
}

impl TsNodePtr {
    /// Converts this tree-sitter node pointer back into a tree-sitter "node", i.e., node reference.
    ///
    /// # Safety
    /// You must ensure that the tree the node came from is alive
    #[inline]
    pub unsafe fn to_node<'tree>(self) -> tree_sitter::Node<'tree> {
        // SAFETY: tree_sitter::Node is POD (no Drop, Copy),
        // and sizes are compile_time checked to be the same
        std::mem::transmute(self)
    }
}

impl<'tree> From<tree_sitter::Node<'tree>> for TsNodePtr {
    #[inline]
    fn from(node: tree_sitter::Node) -> Self {
        // SAFETY: We are storing this as opaquely, tree_sitter::Node is POD (no Drop, Copy),
        // and sizes are compile_time checked to be the same
        unsafe { std::mem::transmute::<tree_sitter::Node<'_>, TsNodePtr>(node) }
    }
}

impl<'tree> TreeCursor<'tree> {
    /// Wrap a [`tree-sitter::TreeCursor`].
    ///
    /// You must also provide the tree and whether the cursor is at the root node, which are used to
    /// access parent and siblings on cursors that are not rooted.
    #[inline]
    fn new(cursor: tree_sitter::TreeCursor<'tree>, tree: &'tree Tree, is_rooted: bool) -> Self {
        Self {
            cursor,
            tree,
            child_depth: match is_rooted {
                false => 0,
                true => 1,
            },
        }
    }

    /// Gets the cursor's current node
    #[inline]
    pub fn node(&self) -> Node<'tree> {
        // SAFETY: Same tree
        unsafe { Node::new(self.cursor.node(), self.tree) }
    }

    /// Gets the field name of the cursor's current node
    pub fn field_name(&mut self) -> Option<&'static str> {
        self.cursor.field_name().or_else(|| {
            if self.child_depth > 0 {
                None
            } else {
                match self.node().parent() {
                    None => None,
                    Some(parent) => {
                        let original_node = self.node();
                        self.reset(parent);
                        self.goto_first_child();
                        while self.node() != original_node {
                            self.goto_next_sibling();
                        }
                        self.cursor.field_name()
                    }
                }
            }
        })
    }

    /// Re-initialize the cursor to point to the given node
    #[inline]
    pub fn reset(&mut self, node: Node<'tree>) {
        if self.cursor.node() != node.node {
            self.cursor.reset(node.node);
            self.child_depth = if node.tree.root_node() == node { 1 } else { 0 };
        }
    }

    /// Move the cursor to the first child of the current node and return `true`, or return `false`
    /// if the current node has no children
    #[inline]
    pub fn goto_first_child(&mut self) -> bool {
        if self.cursor.goto_first_child() {
            self.child_depth += 1;
            true
        } else {
            false
        }
    }

    /// Move the cursor to the first child of the current node that extends beyond the given byte
    /// offset, and return its index.
    ///
    /// Returns `None` if the current node has no children past that offset.
    #[inline]
    pub fn goto_first_child_for_byte(&mut self, index: usize) -> Option<usize> {
        self.cursor.goto_first_child_for_byte(index).map(|index| {
            self.child_depth += 1;
            index
        })
    }

    /// Move the cursor to the first child of the current node that extends beyond the given row
    /// and column, and return its index.
    ///
    /// Returns `None` if the current node has no children past that row and column.
    #[inline]
    pub fn goto_first_child_for_point(&mut self, point: Point) -> Option<usize> {
        self.cursor
            .goto_first_child_for_point(point.into())
            .map(|index| {
                self.child_depth += 1;
                index
            })
    }

    /// Move the cursor to the next sibling of the current node and return `true`, or return `false`
    /// if the current node has no next sibling.
    ///
    /// Unlike [`tree_sitter::TreeCursor.goto_next_sibling`], this will try (isn't guaranteed to
    /// return `false`) if the cursor is rooted (e.g. reset) to its current node.
    pub fn goto_next_sibling(&mut self) -> bool {
        self.cursor.goto_next_sibling()
            || if self.child_depth > 0 {
                false
            } else {
                match self.node().parent() {
                    None => false,
                    Some(parent) => {
                        let original_node = self.node();
                        self.reset(parent);
                        self.goto_first_child();
                        while self.node() != original_node {
                            self.goto_next_sibling();
                        }
                        self.goto_next_sibling()
                    }
                }
            }
    }

    /// Move the cursor to the parent of the current node and return `true`, or return `false`
    /// if the current node is a tree root.
    ///
    /// Unlike [`tree_sitter::TreeCursor.goto_parent`], this will try (isn't guaranteed to return
    /// `false`) if the cursor is rooted (e.g. reset) to its current node.
    pub fn goto_parent(&mut self) -> bool {
        if self.cursor.goto_parent() {
            debug_assert!(self.child_depth != 0);
            self.child_depth -= 1;
            true
        } else {
            if self.child_depth > 0 {
                false
            } else {
                match self.node().parent() {
                    None => false,
                    Some(parent) => {
                        self.reset(parent);
                        true
                    }
                }
            }
        }
    }

    /// Move the cursor to the next node in pre-order traversal order, where nodes with children are
    /// traversed on both the up and down.
    ///
    /// This uses `last_state` to determine where to go next (i.e. up or right/down on a node with
    /// children), and returns the next state which you would pass to the next `goto_preorder` call
    /// and so on.
    pub fn goto_preorder(&mut self, last_state: TraversalState) -> TraversalState {
        if !last_state.is_up() && self.goto_first_child() {
            TraversalState::Down
        } else if self.goto_next_sibling() {
            TraversalState::Right
        } else if self.goto_parent() {
            TraversalState::Up
        } else {
            TraversalState::End
        }
    }
}

impl QueryCursor {
    /// Creates a new cursor. See [`tree_sitter::QueryCursor::new`]
    #[inline]
    pub fn new() -> Self {
        Self {
            query_cursor: tree_sitter::QueryCursor::new(),
        }
    }

    /// Iterate over all matches in the order they were found. See
    /// [`tree_sitter::QueryCursor::matches`]
    #[inline]
    pub fn matches<'query, 'cursor: 'query, 'tree>(
        &'cursor mut self,
        query: &'query Query,
        node: Node<'tree>,
    ) -> QueryMatches<'query, 'tree> {
        QueryMatches {
            query_matches: self.query_cursor.matches(&query, node.node, node.tree),
            current_match: None,
            tree: node.tree,
            query,
        }
    }

    /// Iterate over all captures in the order they appear. See
    /// [`tree_sitter::QueryCursor::captures`]
    #[inline]
    pub fn captures<'query, 'cursor: 'query, 'tree>(
        &'cursor mut self,
        query: &'query Query,
        node: Node<'tree>,
    ) -> QueryCaptures<'query, 'tree> {
        QueryCaptures {
            query_captures: self.query_cursor.captures(query, node.node, node.tree),
            tree: node.tree,
            query,
        }
    }

    /// Set the maximum number of in-progress matches for this cursor
    #[inline]
    pub fn set_match_limit(&mut self, limit: u16) {
        self.query_cursor.set_match_limit(limit as u32);
    }

    /// Get the maximum number of in-progress matches for this cursor
    #[inline]
    pub fn match_limit(&self) -> u16 {
        self.query_cursor.match_limit() as u16
    }

    /// Check if, on its last execution, this cursor exceeded its maximum number of in-progress
    /// matches
    #[inline]
    pub fn did_exceed_match_limit(&self) -> bool {
        self.query_cursor.did_exceed_match_limit()
    }

    /// Set the range in which to search for matches, in terms of byte offsets.
    ///
    /// Like [`tree_sitter::QueryCursor::set_byte_range`], returns `self` for convenience (builder
    /// pattern).
    #[inline]
    pub fn set_byte_range(&mut self, range: std::ops::Range<usize>) -> &mut Self {
        self.query_cursor.set_byte_range(range);
        self
    }

    /// Set the range in which to search for matches, in terms of rows and columns.
    ///
    /// Like [`tree_sitter::QueryCursor::set_point_range`], returns `self` for convenience (builder
    /// pattern).
    #[inline]
    pub fn set_point_range(&mut self, range: PointRange) -> &mut Self {
        self.query_cursor.set_point_range(range.to_ts_point_range());
        self
    }
}

impl<'query, 'tree> QueryMatches<'query, 'tree> {
    /// Get the query that the matches are from
    #[inline]
    pub fn query(&self) -> &'query Query {
        self.query
    }

    /// Get the tree that the matches are from
    #[inline]
    pub fn tree(&self) -> &'tree Tree {
        self.tree
    }

    /// Limit captures to a byte range
    #[inline]
    pub fn set_byte_range(&mut self, range: std::ops::Range<usize>) {
        self.query_matches.set_byte_range(range);
    }

    /// Limit captures to a point range
    #[inline]
    pub fn set_point_range(&mut self, range: PointRange) {
        self.query_matches
            .set_point_range(range.to_ts_point_range());
    }

    /// Get the underlying [`tree_sitter::QueryMatches`]
    #[inline]
    pub fn as_inner(&self) -> &tree_sitter::QueryMatches<'query, 'tree, &'tree Tree, &'tree str> {
        &self.query_matches
    }

    /// Get the underlying [`tree_sitter::QueryMatches`] (mutable)
    #[inline]
    pub fn as_inner_mut(
        &mut self,
    ) -> &mut tree_sitter::QueryMatches<'query, 'tree, &'tree Tree, &'tree str> {
        &mut self.query_matches
    }

    /// Destruct into the underlying [`tree_sitter::QueryMatches`], as well as the query and tree
    #[inline]
    pub fn into_inner(
        self,
    ) -> (
        tree_sitter::QueryMatches<'query, 'tree, &'tree Tree, &'tree str>,
        &'query Query,
        &'tree Tree,
    ) {
        (self.query_matches, self.query, self.tree)
    }
}

impl<'query, 'tree: 'query> StreamingIterator for QueryMatches<'query, 'tree> {
    type Item = QueryMatch<'query, 'tree>;

    #[inline]
    fn advance(&mut self) {
        self.query_matches.advance();
        self.current_match = self.query_matches.get().map(|query_match| QueryMatch {
            query_match: query_match as *const _,
            query: self.query,
            tree: self.tree,
        });
    }

    #[inline]
    fn get(&self) -> Option<&Self::Item> {
        self.current_match.as_ref()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.query_matches.size_hint()
    }
}

impl<'query, 'tree> QueryCaptures<'query, 'tree> {
    /// Get the query that the captures are from
    #[inline]
    pub fn query(&self) -> &'query Query {
        self.query
    }

    /// Get the tree that the captures are from
    #[inline]
    pub fn tree(&self) -> &'tree Tree {
        self.tree
    }

    /// Limit captures to a byte range
    #[inline]
    pub fn set_byte_range(&mut self, range: std::ops::Range<usize>) {
        self.query_captures.set_byte_range(range);
    }

    /// Limit captures to a point range
    #[inline]
    pub fn set_point_range(&mut self, range: PointRange) {
        self.query_captures
            .set_point_range(range.to_ts_point_range());
    }

    /// Get the underlying [`tree_sitter::QueryCaptures`]
    #[inline]
    pub fn as_inner(&self) -> &tree_sitter::QueryCaptures<'query, 'tree, &'tree Tree, &'tree str> {
        &self.query_captures
    }

    /// Get the underlying [`tree_sitter::QueryCaptures`] (mutable)
    #[inline]
    pub fn as_inner_mut(
        &mut self,
    ) -> &mut tree_sitter::QueryCaptures<'query, 'tree, &'tree Tree, &'tree str> {
        &mut self.query_captures
    }

    /// Destruct into the underlying [`tree_sitter::QueryCaptures`], as well as query and tree
    #[inline]
    pub fn into_inner(
        self,
    ) -> (
        tree_sitter::QueryCaptures<'query, 'tree, &'tree Tree, &'tree str>,
        &'query Query,
        &'tree Tree,
    ) {
        (self.query_captures, self.query, self.tree)
    }
}

impl<'query, 'tree: 'query> Iterator for QueryCaptures<'query, 'tree> {
    type Item = QueryCapture<'query, 'tree>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.query_captures.next().map(|(query_match, index)| {
            QueryCapture::new(query_match.captures[*index], self.query, self.tree)
        })
    }
}

impl<'query, 'tree> QueryMatch<'query, 'tree> {
    /// Wrap a tree-sitter query match.
    ///
    /// # Safety
    /// The query match must be from the given tree and query. Additionally, *`query_match`'s
    /// lifetime must be longer than the "lifetime" where any methods may be called on this
    /// structure, despite not being captured in the signature* (the structure can outlive
    /// `query_match` because it stores a raw pointer, but most of its methods dereference, so when
    /// `query_match` is no longer live they cause UB).
    #[inline]
    pub unsafe fn new(
        query_match: &tree_sitter::QueryMatch<'query, 'tree>,
        query: &'query Query,
        tree: &'tree Tree,
    ) -> Self {
        Self {
            query_match: query_match as *const _,
            query,
            tree,
        }
    }

    /// Get the query that the match is from
    #[inline]
    pub fn query(&self) -> &'query Query {
        self.query
    }

    /// Get the tree that the match is from
    #[inline]
    pub fn tree(&self) -> &'tree Tree {
        self.tree
    }

    /// Iterate all captures in the order they appear.
    #[inline]
    pub fn iter_captures(&self) -> impl Iterator<Item = QueryCapture<'query, 'tree>> {
        self.as_inner()
            .captures
            .iter()
            .map(|&query_capture| QueryCapture::new(query_capture, self.query, self.tree))
    }

    /// Get the capture at the given index (order it appears).
    #[inline]
    pub fn capture(&self, index: usize) -> Option<QueryCapture<'query, 'tree>> {
        self.as_inner()
            .captures
            .get(index)
            .map(|&query_capture| QueryCapture::new(query_capture, self.query, self.tree))
    }

    /// Get the first occurrence of the capture with the given name.
    #[inline]
    pub fn capture_named(&self, name: &str) -> Option<QueryCapture<'query, 'tree>> {
        self.iter_captures().find(|capture| capture.name == name)
    }

    /// Get every occurrence of the captures with the given name.
    #[inline]
    pub fn captures_named<'a>(
        &'a self,
        name: &'a str,
    ) -> impl Iterator<Item = QueryCapture<'query, 'tree>> + 'a {
        self.iter_captures()
            .filter(move |capture| capture.name == name)
    }

    /// Get the number of captures in this match.
    #[inline]
    pub fn capture_count(&self) -> usize {
        self.as_inner().captures.len()
    }

    /// Get the pattern index of this match.
    #[inline]
    pub fn pattern_index(&self) -> usize {
        self.as_inner().pattern_index
    }

    /// Get the id of this match  (honestly I don't know what this does because it's not documented)
    #[inline]
    pub fn id(&self) -> u32 {
        self.as_inner().id()
    }

    /// Remove the match (honestly I don't know what this does because it's not documented)
    #[inline]
    pub fn remove(&self) {
        self.as_inner().remove()
    }

    /// Get the nodes that were captures by the capture at the given index.
    #[inline]
    pub fn nodes_for_capture_index(
        &self,
        capture_index: u32,
    ) -> impl Iterator<Item = Node<'tree>> + '_ {
        // SAFETY: Same tree
        self.as_inner()
            .nodes_for_capture_index(capture_index)
            .map(move |node| unsafe { Node::new(node, self.tree) })
    }

    /// Get the underlying [`tree_sitter::QueryMatch`]
    #[inline]
    pub fn as_inner(&self) -> &tree_sitter::QueryMatch<'query, 'tree> {
        // SAFETY: The `unsafe` constructor requires that the pointer is live.
        unsafe { &*self.query_match }
    }

    /// Destruct into the underlying [`tree_sitter::QueryMatch`] raw pointer, as well as the query and
    /// tree
    #[inline]
    pub fn into_inner(
        self,
    ) -> (
        *const tree_sitter::QueryMatch<'query, 'tree>,
        &'query Query,
        &'tree Tree,
    ) {
        (self.query_match, self.query, self.tree)
    }
}

impl<'query, 'tree> QueryCapture<'query, 'tree> {
    /// Wrap a [`tree_sitter::QueryCapture`]. This also needs the tree and query for helper methods
    #[inline]
    fn new(
        query_capture: tree_sitter::QueryCapture<'tree>,
        query: &'query Query,
        tree: &'tree Tree,
    ) -> Self {
        // SAFETY: fn is internal so the provided tree is always the same as the node's tree
        unsafe {
            Self {
                node: Node::new(query_capture.node, tree),
                index: query_capture.index as usize,
                name: &query.capture_names()[query_capture.index as usize],
            }
        }
    }
}

impl From<tree_sitter::Point> for Point {
    #[inline]
    fn from(value: tree_sitter::Point) -> Self {
        Self {
            row: value.row,
            column: value.column,
        }
    }
}

impl From<Point> for tree_sitter::Point {
    #[inline]
    fn from(value: Point) -> Self {
        Self {
            row: value.row,
            column: value.column,
        }
    }
}

impl Display for Point {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}:{}", self.row + 1, self.column + 1)
    }
}

impl PointRange {
    /// Convert this into an [`std::ops::Range`]
    #[inline]
    pub fn to_ops_range(self) -> std::ops::Range<Point> {
        self.start..self.end
    }

    /// Convert this into an [`std::ops::Range`] of [`tree_sitter::Point`]s
    #[inline]
    pub fn to_ts_point_range(self) -> std::ops::Range<tree_sitter::Point> {
        self.start.into()..self.end.into()
    }
}

impl From<std::ops::Range<Point>> for PointRange {
    #[inline]
    fn from(value: std::ops::Range<Point>) -> Self {
        Self {
            start: value.start,
            end: value.end,
        }
    }
}

impl RangeBounds<Point> for PointRange {
    fn start_bound(&self) -> Bound<&Point> {
        Bound::Excluded(&self.start)
    }

    fn end_bound(&self) -> Bound<&Point> {
        Bound::Excluded(&self.end)
    }
}

impl Display for PointRange {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        if self.start == self.end {
            write!(f, "{}", self.start)
        } else if self.start.row == self.end.row {
            write!(f, "{}-{}", self.start, self.end.column + 1)
        } else {
            write!(f, "{}-{}", self.start, self.end)
        }
    }
}

impl From<tree_sitter::Range> for Range {
    #[inline]
    fn from(value: tree_sitter::Range) -> Self {
        Self {
            start_byte: value.start_byte,
            end_byte: value.end_byte,
            start_point: Point::from(value.start_point),
            end_point: Point::from(value.end_point),
        }
    }
}

impl From<Range> for tree_sitter::Range {
    #[inline]
    fn from(value: Range) -> Self {
        Self {
            start_byte: value.start_byte,
            end_byte: value.end_byte,
            start_point: value.start_point.into(),
            end_point: value.end_point.into(),
        }
    }
}

impl From<Range> for PointRange {
    #[inline]
    fn from(value: Range) -> Self {
        Self {
            start: value.start_point,
            end: value.end_point,
        }
    }
}

impl BitOr for Range {
    type Output = Range;

    /// Smallest range which contains both ranges
    #[inline]
    fn bitor(self, rhs: Self) -> Self::Output {
        Range {
            start_byte: self.start_byte.min(rhs.start_byte),
            end_byte: self.end_byte.max(rhs.end_byte),
            start_point: self.start_point.min(rhs.start_point),
            end_point: self.end_point.max(rhs.end_point),
        }
    }
}

impl BitOrAssign for Range {
    /// Smallest range which contains both ranges
    #[inline]
    fn bitor_assign(&mut self, rhs: Self) {
        *self = *self | rhs;
    }
}

impl BitAnd for Range {
    type Output = Option<Range>;

    /// Largest range which both ranges contain if not disjoint, or `None` if they are
    #[inline]
    fn bitand(self, rhs: Self) -> Self::Output {
        let start_byte = self.start_byte.max(rhs.start_byte);
        let end_byte = self.end_byte.min(rhs.end_byte);
        let start_point = self.start_point.max(rhs.start_point);
        let end_point = self.end_point.min(rhs.end_point);

        if start_byte <= end_byte && start_point <= end_point {
            Some(Range {
                start_byte,
                end_byte,
                start_point,
                end_point,
            })
        } else {
            None
        }
    }
}

impl Display for Range {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", PointRange::from(*self))
    }
}

impl NodeId {
    /// "Magic" node id for an invalid node
    pub const INVALID: Self = Self(usize::MAX);

    /// Get the id of the given [`tree_sitter::Node`]. See [`tree_sitter::Node::id`]
    #[inline]
    fn of_ts(node: tree_sitter::Node<'_>) -> Self {
        NodeId(node.id())
    }
}

impl From<u64> for NodeId {
    #[inline]
    fn from(value: u64) -> Self {
        NodeId(value as usize)
    }
}

impl Into<u64> for NodeId {
    #[inline]
    fn into(self) -> u64 {
        self.0 as u64
    }
}

impl Display for NodeId {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "#{}", self.0)
    }
}

impl Clone for TreeParseError {
    #[inline]
    fn clone(&self) -> Self {
        match self {
            TreeParseError::IO(e) => TreeParseError::IO(std::io::Error::from(e.kind())),
            TreeParseError::ParsingFailed => TreeParseError::ParsingFailed,
            TreeParseError::NotUtf8(e) => TreeParseError::NotUtf8(*e),
        }
    }
}

impl From<std::io::Error> for TreeParseError {
    fn from(e: std::io::Error) -> Self {
        TreeParseError::IO(e)
    }
}

impl From<Utf8Error> for TreeParseError {
    fn from(e: Utf8Error) -> Self {
        TreeParseError::NotUtf8(e)
    }
}

impl Display for TreeParseError {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            TreeParseError::IO(e) => write!(f, "IO error: {}", e),
            TreeParseError::ParsingFailed => write!(f, "Parsing failed"),
            TreeParseError::NotUtf8(e) => write!(f, "Not UTF-8: {}", e),
        }
    }
}

impl Error for TreeParseError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            TreeParseError::IO(e) => Some(e),
            TreeParseError::ParsingFailed => None,
            TreeParseError::NotUtf8(e) => Some(e),
        }
    }
}

impl TraversalState {
    /// Is this the up state?
    #[inline]
    pub fn is_up(&self) -> bool {
        match self {
            TraversalState::Up => true,
            _ => false,
        }
    }

    /// Is this the final state (done traversing?)
    #[inline]
    pub fn is_end(&self) -> bool {
        match self {
            TraversalState::End => true,
            _ => false,
        }
    }
}

impl<'tree> PreorderTraversal<'tree> {
    /// Create a new preorder traversal which will use the given tree-cursor
    #[inline]
    pub fn with_cursor(cursor: TreeCursor<'tree>) -> Self {
        Self {
            cursor,
            last_state: TraversalState::Start,
        }
    }

    /// Create a new preorder traversal which will traverse the given tree
    #[inline]
    pub fn of_tree(tree: &'tree Tree) -> Self {
        Self::with_cursor(tree.walk())
    }

    /// Create a new preorder traversal which will traverse the given node
    #[inline]
    pub fn of_node(node: Node<'tree>) -> Self {
        Self::with_cursor(node.walk())
    }

    /// Get the current item without advancing the traversal
    #[inline]
    pub fn peek(&mut self) -> TraversalItem<'tree> {
        TraversalItem {
            node: self.cursor.node(),
            field_name: self.cursor.field_name(),
            last_state: self.last_state,
        }
    }

    /// Advance the traversal to the next item and return `true`, or return `false` if it's done
    #[inline]
    pub fn goto_next(&mut self) -> bool {
        if self.last_state.is_end() {
            false
        } else {
            self.last_state = self.cursor.goto_preorder(self.last_state);
            true
        }
    }
}

impl<'tree> Iterator for PreorderTraversal<'tree> {
    type Item = TraversalItem<'tree>;

    #[inline]
    fn next(&mut self) -> Option<TraversalItem<'tree>> {
        if self.last_state.is_end() {
            return None;
        }
        let item = self.peek();
        self.last_state = self.cursor.goto_preorder(self.last_state);
        Some(item)
    }
}

impl<'tree> FusedIterator for PreorderTraversal<'tree> {}

// region special "boilerplate" impls
impl<'tree> Debug for Node<'tree> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self.node)
    }
}

impl Debug for NodePtr {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self.node_data)
    }
}

impl<'query, 'tree> Debug for QueryMatch<'query, 'tree> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self.query_match)
    }
}
// endregion

impl<'tree> PartialEq for TraversalItem<'tree> {
    fn eq(&self, other: &Self) -> bool {
        if self.node == other.node {
            debug_assert_eq!(
                self.field_name, other.field_name,
                "field_name must be the same if node is the same"
            );
        }
        self.node == other.node && self.last_state == other.last_state
    }
}

impl<'tree> Eq for TraversalItem<'tree> {}
// endregion