CST Upward Navigation

[xunilrj]

Today we don't have a very nice way to navigate the CST upwards. Of course, we have SyntaxNode::parent but then I need to work on the untyped tree.

tools/crates/rome_rowan/src/cursor/node.rs

Line 160 in 3d5b0f0

pub fn parent(&self) -> Option<SyntaxNode> {

All the examples below are navigating from a binding identifier to its declaration statement and checking if the var keyword was used:

My first option is to navigate the untyped tree and ignore checking anything along the way.

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .parent()
        .and_then(|declarator| declarator.parent())
        .and_then(|list| list.parent())
        .and_then(|declaration| declaration.cast::<JsVariableDeclaration>())
        .map(|x| x.is_var())
        .unwrap_or(false)
}

But if we don't wanna check anything, we may as well do:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .ancestors()
        .nth(3)
        .and_then(JsVariableDeclaration::cast)
        .map(|declaration| declaration.is_var())
        .unwrap_or(false)
}

If I do need to check anything along the way the chain gets much bigger and with a lot of boring repetitive code. One of the reasons is that AstNodedoes not have a parent method. So I need to jump into the untyped tree again.

tools/crates/rome_rowan/src/ast/mod.rs

Line 25 in 3d5b0f0

pub trait AstNode {

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    JsIdentifierBinding::cast(binding)
        .and_then(|binding| binding.syntax().parent())
        .and_then(JsVariableDeclarator::cast)
        .and_then(|declarator| declarator.syntax().parent())
        .and_then(JsVariableDeclaratorList::cast)
        .and_then(|list| list.syntax().parent())
        .and_then(JsVariableDeclaration::cast)
        .map(|x| x.is_var())
        .unwrap_or(false)
}

Any functional programmer at this point is laughing at me for not using "do notations" or any other monadic comprehension. So we can use the "try" operator:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    JsIdentifierBinding::cast(binding)
        .and_then(|binding| {
            let declarator = JsVariableDeclarator::cast(binding.syntax().parent()?)?;
            let list = JsVariableDeclaratorList::cast(declarator.syntax().parent()?)?;
            let declaration = JsVariableDeclaration::cast(list.syntax().parent()?)?;
            Some(declaration.is_var())
        })
        .unwrap_or(false)
}

One annoying thing here is that we can't have one chain because cast is an associated function. Another very annoying thing is the almost double "?" operator. This we can alleviate with:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    JsIdentifierBinding::cast(binding)
        .and_then(|binding| {
            let declarator = binding
                .syntax()
                .parent()
                .and_then(JsVariableDeclarator::cast)?;
            let list = declarator
                .syntax()
                .parent()
                .and_then(JsVariableDeclaratorList::cast)?;
            let declaration = list
                .syntax()
                .parent()
                .and_then(JsVariableDeclaration::cast)?;
            Some(declaration.is_var())
        })
        .unwrap_or(false)
}

Any other variations were cosmetic changes from these possibilities.
Now, below are my suggestions on how to improve this navigation, split into four different threads, so it becomes easy to discuss each specific point.

1 - SyntaxNode cast extension method;
2 - AstNode needs a parent function;
3 - Lifting parent to Option<> world;
4 - using the extension-trait crate.

I am a strong advocate for implementing the first three, whereas the fourth is more like just sugar on top of it.

[xunilrj]

1 - SyntaxNode cast extension method

The .await proved that "postfixed operators" normally generate easier to read chains. In this case, having to call JsVariableDeclarator:::cast as a "prefixed operator" breaks the flow and forces me to have temporary variables.

My first proposal is to create a method to cast from SyntaxNode to AstNode; and we can do this keeping the dependency order correct by creating extensions methods in the AstNode module.

In the end I will use this crate: https://github.com/danielhenrymantilla/ext-trait.rs. But for now I will implement everything manually.

pub trait AstNodeFromSyntaxNode<L>
where
    L: Language,
{
    fn cast<T>(self) -> Option<T>
    where
        T: AstNode<Language = L>;
}

impl<L> AstNodeFromSyntaxNode<L> for SyntaxNode<L>
where
    L: Language,
{
    fn cast<T>(self) -> Option<T>
    where
        T: AstNode<Language = L>,
    {
        T::cast(self)
    }
}

This allows me to write:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .cast::<JsIdentifierBinding>()
        .and_then(|binding| {
            let declarator: JsVariableDeclarator = binding.syntax().parent()?.cast()?;
            let list: JsVariableDeclaratorList = declarator.syntax().parent()?.cast()?;
            let declaration: JsVariableDeclaration = list.syntax().parent()?.cast()?;
            Some(declaration.is_var())
        })
        .unwrap_or(false)
}

Not quite there yet. But already something.
In this case the "double try operator" is less annoying because it is more clear what they are doing.

And I can finally have one long chain.

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .cast::<JsIdentifierBinding>()
        .and_then(|binding| {
            let is_var = binding
                .syntax()
                .parent()?
                .cast::<JsVariableDeclarator>()?
                .syntax()
                .parent()?
                .cast::<JsVariableDeclaratorList>()?
                .syntax()
                .parent()?
                .cast::<JsVariableDeclaration>()?
                .is_var();
            Some(is_var)
        })
        .unwrap_or(false)
}

Which I, personally, think it is much easier to read.

[MichaReiser]

I considered adding this method multiple times but was worried about adding it to SyntaxNode because of the cyclic dependency it introduces. That's why I like your proposal of introducing it as part of an extension trait.

We may want to consider introducing a rome_rowan::prelude that imports many of the commonly used traits.

[ematipico]

I like it!

[xunilrj]

2 - AstNode needs a parent function

Another simpler improvement is avoiding all the .syntax().parent() calls and implement a parent() function directly in the AstNode. This can be very easily done as:

trait AstNode {
    ...
    fn parent(&self) -> Option<SyntaxNode<Self::Language>> {
        self.syntax().parent()
    }
}

This allows me to write:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .cast::<JsIdentifierBinding>()
        .and_then(|binding| {
            let is_var = binding
                .parent()?
                .cast::<JsVariableDeclarator>()?
                .parent()?
                .cast::<JsVariableDeclaratorList>()?
                .parent()?
                .cast::<JsVariableDeclaration>()?
                .is_var();
            Some(is_var)
        })
        .unwrap_or(false)
}

A little bit better. But this brings to the attention that the typed tree is returning an untyped parent. If we instead return a typed parent, we can avoid all these cast.

trait AstNode {
    ...
    fn parent<T: AstNode<Language = Self::Language> + Sized>(&self) -> Option<T> {
        self.syntax().parent().and_then(T::cast)
    }
}

with this we arrived at:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .cast::<JsIdentifierBinding>()
        .and_then(|binding| {
            let is_var = binding
                .parent::<JsVariableDeclarator>()?
                .parent::<JsVariableDeclaratorList>()?
                .parent::<JsVariableDeclaration>()?
                .is_var();
            Some(is_var)
        })
        .unwrap_or(false)
}

Which is much clearer.

The next section is a little bit more polemic, but I think makes the whole solution much more easier to understand.

[MichaReiser]

Babel has a findParent method that can help when traversing upwards.

Roslyn offers a similar method (which is also similar to the parent method you suggested). It returns the first node in the ancestor list (starting with the current node) that is of the given type (and fulfils a potential optional predicate)

Traversing along all ancestors might provide more flexible and avoid the need to have multiple helper methods. The downside is that it can be dangerous in case nested expressions are possible.

[ematipico]

What if we called it parent_as::<T>? Simply because passing the generic type is not enough to tell me that parent:: actually does a cast on the type. Regardless the naming, I like the idea.

[xunilrj]

Normally as is infallible free operation: https://rust-lang.github.io/api-guidelines/naming.html
In this case, we can fail.

We could have a parent_to but I do not see any gain, especially because we can't have a plain vanilla parent in the typed tree.

[ematipico]

No problem :) it doesn't create much friction! The documentation will help!

[xunilrj]

3 - Lifting parent to Option world

Rust unfortunately is not a complete functional language, so we have no easy way to lift the parent function to Option. And even if we could, there is no easy way to turn lifted function into "postfixed operators", because Rust do not have a pipeline operator.

In this case my proposal is to create a extension method to Option<T> where T: AstNode that contains the lifted implementation of parent.

pub trait AstNodeParent {
    type Language: Language;
    fn parent<T: AstNode<Language = Self::Language> + Sized>(&self) -> Option<T>;
}

impl<TAstNode, TLanguage> AstNodeParent for Option<TAstNode>
where
    TAstNode: AstNode<Language = TLanguage>,
    TLanguage: Language,
{
    type Language = TLanguage;
    fn parent<T: AstNode<Language = Self::Language> + Sized>(&self) -> Option<T> {
        self.as_ref()?.syntax().parent().and_then(T::cast)
    }
}

This brings the solution to:

fn is_identifier_declared_with_var(binding: JsSyntaxNode) -> bool {
    binding
        .cast::<JsIdentifierBinding>()
        .parent::<JsVariableDeclarator>()
        .parent::<JsVariableDeclaratorList>()
        .parent::<JsVariableDeclaration>()
        .map(|declaration| declaration.is_var())
        .unwrap_or(false)
}

[MichaReiser]

I personally don't mind the additional ? operator but implementing the trait for Option seems fine too.

[ematipico]

I think the only downside of this implementation is that you don't know where you get the None. With Result, you actually get the error and we know which parent is missing. Here we don't. What's a use case where we want Option and don't mind about missing parents? And how do we differentiate the parent call that returns Result from the one that returns Option?

[xunilrj]

4 - using the extension-trait crate

If we use the extension-trait crate, the whole implementation becomes:

use extension_trait::*;

#[extension_trait]
pub impl<L: Language> SyntaxNodeCast<L> for SyntaxNode<L> {
    fn cast<T: AstNode<Language = L>>(self) -> Option<T> {
        T::cast(self)
    }
}

trait AstNode {
    ...
    fn parent<TParent: AstNode<Language = L> + Sized>(&self) -> Option<TParent> {
        self.syntax().parent().and_then(TParent::cast)
    }
}

#[extension_trait]
pub impl<L: Language, T: AstNode<Language = L>> OptionAstNodeParent<L> for Option<T> {
    fn parent<TParent: AstNode<Language = L> + Sized>(&self) -> Option<TParent> {
        self.as_ref()?.syntax().parent().and_then(TParent::cast)
    }
}

[xunilrj]

PR for this discussion: #2601