Is there a way to traverse the AST?

[anurbol]

Some parsers have a way to traverse an AST down from the root node to the leaf nodes. Something like this:

traverse(ast, visit)
fn visit(node: impl Node) {
  // ... do stuff with node ...
  node.get_children().for_each(visit)
}

Is there something similar in SWC? I've searched and didn't find, so I think there's not, but I'd like to be sure.

Or maybe I am missing some nice idiomatic to Rust way to traverse SWC-generated AST?

[kdy1]

Traversal is implemented both for rust and javascript, but there's no untyped traversal yet.

In rust, you need to turn on specialization and implement swc_common::Fold<Expr> or swc_common::Visit<Expr> for example.

In javascript, you can use @swc/core/Visitor.
See https://swc-project.github.io/docs/usage-plugin for usage.
Note that javascript api will be changed slightly on v1.1.5

[kdy1]

@anurbol In rust, almost all of /ecmascript/transforms are example of type-based ast traversal

[anurbol]

Wow, great! I'll look there! Thanks for all the help! I'll do my best to make a universal (untyped) traversal and contribute, if I'll manage to do that.

[anurbol]

Until then closing this issue...

[anurbol]

I am back to this problem. Wow this was harder than I thought. I have spent hours reading the SWC source code, including Transforms, and I now have some (very basic) idea of how stuff works, but I don't know how to apply it to my use case (without writing mountains of code).

So as far as I understand, I need to write something like this:

struct CommentProcessor {
  fn process_comment(&self, comment: Comment) { /* process comment, doesn't matter */ }
}

impl Visit<Stmt> for CommentProcessor {
  fn visit(&self, stmt: Stmt) {
      let comment = /* get comment of Stmt*/;
      self.process_comment(comment);
      /* iterate body of Stmt and call visit() on it's every item  */
  }
}

Did I get the idea?

If yes, then, do I really have to implement Visit for every single AST Item, if I want to process all comments? Isn't there already some approach to simply iterate every node all the way from the root node to the leaf nodes? I suspect there isn't, because it's hard to do that with Rust's type system. If this is the case, then could we make (I could try) some additional trait like Traversible to the current ast_node set of traits. The trait could look perhaps something like this:

trait Traversible {
  pub fn get_children(&self) -> Vec<AstNode>
  pub fn traverse(&self, fn: |x| -> ()) /* I forgot correct syntax for callback param*/  {
    fn(self);
    self.get_children().for_each(|child| { match child {  c => c.traverse(fn) }  })
  }
}

/* ... implement Traversible (the `get_children` method) for every AstNode ... */

enum AstNode {
  ArrayLit(ArrayLit),
  ArrayPat(ArrayPat), 
  ArrowExpr(ArrowExpr),
  AssignExpr(AssignExpr),
  AssignPat(AssignPat),
/* all the remaining nodes */
}

What do you think? Will it work?

Disclaimer: the code may be horribly wrong, silly etc.

[kdy1]

@anurbol

If you only need to process comment of each node, you can easily handle this with generic.

impl<T> Fold<T> for CommentProcessor
where
    T: FoldWith<Self> + Spanned,
{
    fn fold(&mut self, n: T) -> T {
        let span = n.span();
        n.fold_children(self)
    }
}

If you need to specialize behavior of some type, you need to mark fold above as default impl and should add a implementation more special than T: FoldWith<Self> + Spanned.

[anurbol]

Hey @kdy1 can we discuss this in Gitter? I messaged you there. I am facing problems with importing stuff.

[kdy1]

@anurbol I sent a message.

[anurbol]

@kdy1 Wow, seems to work great! Thanks! When you have some time could you please explain how fold_children works? For me it's just plain magic. I can't find where that method is implemented, how does it find the children.

P.S. For those who needs this: in Gitter chat I was told to have my Cargo.toml like this:

[dependencies]
swc_ecma_ast = {version = "...", features = ["fold"] } // import feature

After that Fold, FoldWith can be imported just fine.

[kdy1]

@anurbol procedural macro implements it.
You can use cargo-expand to see the expanded code.

1. Install it with cargo install cargo-expand
2. cd swc/macros/ast_node
3. cargo expand --test fold_simple

output from cargo expand

#![feature(prelude_import)]
#![feature(specialization)]
#[prelude_import]
use std::prelude::v1::*;
#[macro_use]
extern crate std;
use swc_common::{Fold, FoldWith};
pub trait AssertFold<T>: Fold<T> {}
pub struct LitFold;
impl Fold<Lit> for LitFold {
    fn fold(&mut self, _: Lit) -> Lit {
        Lit::A
    }
}
impl AssertFold<Expr> for LitFold {}
impl AssertFold<ExprKind> for LitFold {}
pub struct Expr {
    pub node: ExprKind,
    /// This field should be skipped.
    pub bool_field: bool,
    /// Ensure that #[fold(ignore)] works.
    #[fold(ignore)]
    pub ignored: PanicOnFold,
}
const IMPL_FOLD_FOR_Expr: () = {
    impl<__Fold> swc_common::FoldWith<__Fold> for Expr {
        #[inline]
        #[allow(clippy::needless_return)]
        fn fold_children(self, _f: &mut __Fold) -> Self {
            match self {
                Expr {
                    node: _node,
                    bool_field: _bool_field,
                    ignored: _ignored,
                } => {
                    return Expr {
                        node: swc_common::Fold::<ExprKind>::fold(_f, _node),
                        bool_field: _bool_field,
                        ignored: _ignored,
                    };
                }
            }
        }
    }
    impl<__V> swc_common::VisitWith<__V> for Expr {
        #[inline]
        fn visit_children(&self, _v: &mut __V) {
            match *self {
                Expr {
                    node: ref _node,
                    bool_field: ref _bool_field,
                    ignored: ref _ignored,
                } => {
                    swc_common::Visit::<ExprKind>::visit(_v, _node);
                }
            }
        }
    }
};
pub struct PanicOnFold;
impl<F> FoldWith<F> for PanicOnFold {
    fn fold_children(self, _: &mut F) -> Self {
        {
            {
                {
                    ::std::rt::begin_panic_fmt(
                        &::core::fmt::Arguments::new_v1(
                            &["internal error: entered unreachable code: "],
                            &match (&"this should not be called",) {
                                (arg0,) => [::core::fmt::ArgumentV1::new(
                                    arg0,
                                    ::core::fmt::Display::fmt,
                                )],
                            },
                        ),
                        &("macros/ast_node/tests/fold_simple.rs", 35u32, 9u32),
                    )
                }
            }
        }
    }
}
pub enum ExprKind {
    RecursiveBoud(Box<Expr>),
    Rec2(Vec<Option<Box<Expr>>>),
    Lit(Lit),
}
const IMPL_FOLD_FOR_ExprKind: () = {
    impl<__Fold> swc_common::FoldWith<__Fold> for ExprKind {
        #[inline]
        #[allow(clippy::needless_return)]
        fn fold_children(self, _f: &mut __Fold) -> Self {
            match self {
                ExprKind::RecursiveBoud(_0) => {
                    return ExprKind::RecursiveBoud {
                        0: swc_common::Fold::<Box<Expr>>::fold(_f, _0),
                    };
                }
                ExprKind::Rec2(_0) => {
                    return ExprKind::Rec2 {
                        0: swc_common::Fold::<Vec<Option<Box<Expr>>>>::fold(_f, _0),
                    };
                }
                ExprKind::Lit(_0) => {
                    return ExprKind::Lit {
                        0: swc_common::Fold::<Lit>::fold(_f, _0),
                    };
                }
            }
        }
    }
    impl<__V> swc_common::VisitWith<__V> for ExprKind {
        #[inline]
        fn visit_children(&self, _v: &mut __V) {
            match *self {
                ExprKind::RecursiveBoud(ref _0) => {
                    swc_common::Visit::<Box<Expr>>::visit(_v, _0);
                }
                ExprKind::Rec2(ref _0) => {
                    swc_common::Visit::<Vec<Option<Box<Expr>>>>::visit(_v, _0);
                }
                ExprKind::Lit(ref _0) => {
                    swc_common::Visit::<Lit>::visit(_v, _0);
                }
            }
        }
    }
};
pub enum Lit {
    A,
    B,
}
const IMPL_FOLD_FOR_Lit: () = {
    impl<__Fold> swc_common::FoldWith<__Fold> for Lit {
        #[inline]
        #[allow(clippy::needless_return)]
        fn fold_children(self, _f: &mut __Fold) -> Self {
            match self {
                Lit::A => {
                    return Lit::A;
                }
                Lit::B => {
                    return Lit::B;
                }
            }
        }
    }
    impl<__V> swc_common::VisitWith<__V> for Lit {
        #[inline]
        fn visit_children(&self, _v: &mut __V) {
            match *self {
                Lit::A => {}
                Lit::B => {}
            }
        }
    }
};
#[main]
pub fn main() -> () {
    extern crate test;
    test::test_main_static(&[])
}

As you can see, there's impl<F> swc_common::FoldWith<F> for Expr.
All ast nodes implement FoldWith<F> (for any F) when swc_ecma_ast/fold is enabled.

There's one more magic left.

swc/common/src/fold.rs

Lines 91 to 107 in 42ad8a9

	impl<T, F> Fold<T> for F
	where
	T: FoldWith<F>,
	{
	default fn fold(&mut self, t: T) -> T {
	t.fold_children(self)
	}
	}
	impl<T: ?Sized, F> Visit<T> for F
	where
	T: VisitWith<F>,
	{
	default fn visit(&mut self, t: &T) {
	t.visit_children(self)
	}
	}

With this default implementation, all types implements Fold<T> when T: FoldWith<Self>. It means, when #[derive(Fold)] is applied to T, all types can fold T.

Note that this magic is based on specialization, so you need nightly rust.

[anurbol]

Well this is a bit hard to understand, but thanks for posting! It's a great reference for future me (when I need this again) or others when someone is interested. Specialization is easy (and I have utilized it as you said) if compared to this macro madness :')

[swc-bot]

This closed issue has been automatically locked because it had no new activity for a month. If you are running into a similar issue, please create a new issue with the steps to reproduce. Thank you.