Node pattern and AST

[marcandre]

From #14

The Elixir AST is a really simple data structure, I have an article that you can use for reference, and I also wrote an article that describes Sourceror's approach. In essence(and specially in Sourceror's case) an AST node is a tuple with 3 elements like {:def, metadata, arguments} for a function definition, {:%{}, metadata, elements} for a map, and so on. Elixir also has pattern matching, so walking the AST looking for a specific node is trivial once you get used to it.

It's true that the builtin pattern matching makes this easier to do in elixir (Ruby got pattern matching too though), but in my experience matching on different levels or for things that are not supported (e.g. keyword matching foo, or map/keyword with key matching foo) that it shines ("any child" / "last child", etc.).

My first impression of the elixir AST is that of sore disappointment though. The metadata is missing the equivalent of parser's SourceMap nor access to their source at all.

$ ruby-parse -L -e "2+2"
(send
  (int 2) :+
  (int 2))
2+2
 ~ selector
~~~ expression

(int 2)
2+2
~ expression

(int 2)
2+2
  ~ expression

Compared to:

quote do: 2+2
# => {:+, _ , [2, 2]}

This shows also that literals are unwrapped (e.g. 42 vs {:int, _, 42}), which seems (to my newbie eyes) as a dire mistake, which compounds with the previous point.

Also, I didn't test much, but the fact that 42 |> IO.inspect and IO.inspect(42) do not produce the same AST structure (meta data excluded) seems to also be a grave error (again, in my newbie's eyes). I fail to see how these could possible behave differently.

Finally, macros complicate things, as it makes ~w[a b] and ["a", "b"] theoretically different even though they should be for most practical purposes considered equivalent.

Now, I see that RuboCop's NodePath has some operators like ^ to move up in the tree, which is not possible by using this kind of traversal functions. I believe a port of NodePath should be achievable using that Zipper API.

That's correct, I'd use Zipper.

I've been entertaining similar ideas while looking at projects such as grasp

I wanted to do something like graspjs for Ruby, but never managed to do it and now I'm doing more elixir

[doorgan]

This shows also that literals are unwrapped (e.g. 42 vs {:int, _, 42}), which seems (to my newbie eyes) as a dire mistake, which compounds with the previous point.

There have been discussions in the past regarding this. In this mailing list discussion, José mentions some of the reasons why literals are unwrapped. To summarize, they optimized the AST for macro creation, not for reconstruction or for other kind of use cases.

For example, if you were to write a macro that used the following syntax:

schema "some_table" do
  field :foo, :string
end

You write the macro clause like so:

defmacro schema(table, do: block) do
  # ...
end

But if every node were wrapped, you'd have to write something like this:

defmacro  foo({:"[]", _, [{{{:__atom__, :do}, _, _}, block}]}) do
  # ...
end

More complex scenarios would require much more verbose pattern matching. The truth is that pattern matching shines on identifying relatively simple patterns, and not so much when the structure is quite nested, due to the lack of composability of patterns out of the box.

Also, I didn't test much, but the fact that 42 |> IO.inspect and IO.inspect(42) do not produce the same AST structure (meta data excluded) seems to also be a grave error (again, in my newbie's eyes). I fail to see how these could possible behave differently.

This happens because in Elixir, most of the constructs are implemented as macros, which can be overrided in some contexts, and the pipe operator is no exception. The Elixir AST is a bit "lispy" in this regard, and something like an "Expression node" doesn't make that much sense. Syntax can mean completely different things depending on the context. It's cumbersome in many cases, yes, but it's what we have. This caused me troubles too when writing a function that converts usage of Enum.join after Enum.map into a single Enum.map_join: https://github.com/doorgan/credo_fixes/blob/main/lib/fixes/refactor/map_join.ex and the pattern matching is still quite ugly. Which is what turned my attention to grasp and now NodePath.

So while I agree that the situation is not ideal for tools like RuboCop or Sourceror, this design is used to great extent to extend the language. There are other issues like comments being discarded in the AST, so I had to also send some PRs to Elixir so we can preserve them.

The purpose of Sourceror is to have an AST more aligned with your idea of "every node is wrapped". So in Sourceror 42 is actually {:__block__, [line: 1, column: 1, token: "42"], [42]}. Blocks are generic groupings in the AST, which is why I used them(and also the Elixir Formatter, built into Elixir, also does this). Of course, the wrapping could be {{:int, "42"}, [line: 1, column: 1], 42} for instance to simplify pattern matching(we can't use {:int, _, 42} because then we need {:atom, _, :foo} which is ambiguous with the variable nodes like {:foo, _, nil}), but then an additional step would be needed before passing it to the formatter(which sourceror uses to convert AST back to strings) while stringifying it. It should be trivial to do, though, and it would be nice to do it before v1.0.

As far as I know, we're the first to do this kind of stuff for Elixir, so there's a lot of work to do. My focus so far was in providing all the necessary primitives so we can start building more complex tools. For example, the Zipper is technically capable of navigating the AST and find a keyword list that contains a given key, but there's not a set of predicates or DSL to make it easier yet:

alias Sourceror.Zipper, as: Z

def go_to_kw_element(ast, key) when is_atom(key) do
  ast
  # Create the zipper from the AST
  |> Z.zip()
  # Find a list node
  |> Z.find(&match?({:__block__, _, [items]} when is_list(items), &1))
  # Find an element that has the given `key`
  |> Z.find(&match?({{:__block__, _, [^key]}, _}, &1))
end

The code is still a bit verbose, and Z.find performs a global search, and there's not a version that only looks at the children yet. But still, the primitives are there.

[marcandre]

As a macro author, you need to call Macro.expand to get around those issues, which Ecto doesn't seem to be doing. I don't know the reason.

👍 I'll investigate. I wonder if there are cases where one would need to escape just the Kernel's macros and not others.

I imagine that the goal is to get the location of 42, but this does not feel descriptive nor easy to match.

I agree. I might also add that I released Sourceror after I made the core Elixir formatter able to print AST, and the Sourceror AST inherits the AST used by the formatter. There's no reason to not provide a better one.

We could adopt this, for example:
foo -> {:var, [], :foo}
400_000 -> {:int, [token: "400_000"], 400000}
42.0 -> {:float, [token: "42.0"], 42.0
:foo -> {:atom, [], :foo}
[1, 2] -> {:"[]", [], [...]} or {:list, [], [...]}
{1, 2} -> {:{}, [], [...]}

👍 Looks good. Did you mean the [] literally? I was expecting location information, maybe something like expression: 42..48, source: "full source code here". That would make token redundant.

~w[a b c] -> {:sigil, [name: "w"], [...]}

At first I thought ~w[...] was purely syntactic sugar, but there doesn't seem to be an equivalent way to call sigil_w, right?

Sigils are a complex case with different arguments. First idea would be like

~w[a b c]a -> {:sigil, [...], [:w, {:string, _, "a b c"}, 'a'}}

I wouldn't have the name information as above, just the mapping information. I really like parser's source maps, the equivalent would be something like: expression: 0..10, tilde: 0..1, name: 1..2, begin: 3..4, end: 8..9, flags: 9..10.

Actually, parser would probably wrap the sigil options and/or the sigil name, but I'm not sure why tbh:

$ ruby-parse -e "/asdasd/i"
(regexp
  (str "asdasd")
  (regopt :i))

That's quite trivial to do by changing the literal encoder. We need to also do the inverse in Sourceror.to_string so the formatter understands what we're giving it, but again it should be trivial.

[doorgan]

Did you mean the [] literally?

No, I meant it as the metadata keyword list. Nodes that are not literals or variables have the shape {type, metadata, values}, so I was just reflecting that. The metadata holds location information, at least the line and column of the start position, some other nodes also provide location for the ending parenthesis(:closing), or the do and end positions. For the full range I wrote Sourceror.get_range/1, which also takes into consideration the comments associated with the node(this could be made configurable).

At first I thought ~w[...] was purely syntactic sugar, but there doesn't seem to be an equivalent way to call sigil_w, right?

No, there isn't. My idea of making the sigil a different kind of node is because it's extremely annoying having to convert the node type to string and check that it starts with sigil_ and is followed by a single letter.

Sigils are a complex case with different arguments. First idea would be like
~w[a b c]a -> {:sigil, [...], [:w, {:string, _, "a b c"}, 'a'}}

Sigils also accept interpolations, so the arguments could be more convoluted:

iex> quote do ~w[a #{:b} c]a end
{:sigil_w, [delimiter: "[", line: 1],
 [
   {:<<>>, [line: 1],
    [
      "a ",
      {:"::", [line: 1],
       [
         {{:., [line: 1],
           [Kernel, :to_string]},
          [line: 1], [:b]},
         {:binary, [line: 1], nil}
       ]},
      " c"
    ]},
   'a'
 ]}

Something similar applies to string and atom interpolations. But the [sigil_type, contents, modifiers] idea looks good to me 👍

I really like parser's source maps, the equivalent would be something like: expression: 0..10, tilde: 0..1, name: 1..2, begin: 3..4, end: 8..9, flags: 9..10.

We could add a step to Sourceror.parse_string to enrich the tree with such data. There is one case I wasn't able to 100% map the node to source ranges:

A
.
B
.
C

This is valid Elixir for A.B.C and produces {:__aliases__, [line: 1, column: 1, last: [line: 5, column: 1]], [:A, :B, :C}, so I don't have data about where the dots and the intermediate segments are. Adding more detailed information to our AST would in some way involve reparsing some segments of the source code and we could solve this issue too.

I need to dig more into parser because it looks really cool and its approach could help us transform the code without needing to implement another printer like they did in recast, unfortunately I didn't have too much time the last couple days, I'm hoping to get back to this soon. I want to understand better how the patch scheduling and application works there first, but regarding these changes to the AST, I'll try to implement them soon(PRs welcome too :) )

[marcandre]

I need to dig more into elixir's AST 😄 I'm just starting to realize how far the core AST is from what I expected.
When I first saw {:if, ...} I thought this made a lot of sense, but now I'm realizing that this could actually be a completely different function that has been imported than a normal if. I'll have to somehow reconcile macros and AST 🤔.

It looks like the AST for aliases should have been more structured. The fact that alias Foo.Bar and alias Foo.{Bar} produce different ASTs (forgetting about meta) doesn't seem ideal either. In my mind, the AST captures what the code means, not how it is written (that is captured in the meta).

[doorgan]

Yes, it can be weird in a couple cases, the Foo.{Bar} definitely caught me by surprise. I believe @OvermindDL1(I hope you don't mind the ping :P) did a "normalized" AST years ago, maybe he can shed some light on us about the pains of the core Elixir AST.

[OvermindDL1]

@doorgan Pings are all good, I'm just mostly not in browsers, I live in the shell and haven't found a good git 'interface' there to get pings from. ^.^;

But yeah, the AST was designed to be easier for macro writing, but honestly I don't think they should have done that, just like we have a way to quote macro's to generate the nasty AST, we could have quoted a macro 'matcher' for function heads and cases and so forth, and that's really what they should have done in my opinion. I really miss the meta contextual information that it is missing...

[andyl]

Another comparable for consideration: the Query Language used by Treesitter.

[hissssst]

We can create collaboration to use Pathex for AST traversal. I already have an example, but I am unable to test it properly, since sourceror wraps everything in {:__block__, _, _} which is hard to work with

[doorgan]

Do you have any ideas on how would that work? I'm not familiar with Pathex, I'm familiar with lenses in general though I'm not sure how it would work in the context of an AST

The current AST sourceror uses is "designed" to reduce intermediate representations between the parser -> sourceror -> elixir formatter. I recognize it's still not the best representation and I've been thinking on using structs for AST nodes to make it easier to pattern match(and not forget about keeping the node metadata), would that help in any way for Pathex?

[hissssst]

If we've implemented this, you could create a lens for specific definition in module like this

import Pathex.Sourceror 
lens_to_post = module(_) ~> definition(:def, :post, 2)
lens_to_map_get = prewalk_lens() ~> call_lens(Map, :get, [_, _])

ast =
  "some_file.ex"
  |> File.read!()
  |> Sourceror.parse_string()
  
# This call changes all Map.get to Map.fetch! in AST
Pathex.over(ast, lens_to_map_get, fn {_caller, meta, [map, key]} -> {{:".", meta, [Map, :fetch!]}, meta, [map, key]} end)

# This call changes Map.get to Map.fetch! only in `post/2` function
Pathex.over(ast, lens_to_post ~> lens_to_map_get, fn {_caller, meta, [map, key]} -> {{:".", meta, [Map, :fetch!]}, meta, [map, key]} end)

Plus, it is possible to implement a macro which can generate patterns to match on AST like this:

iex> super_quote(x + y) = quote(do: 1 + 2)
iex> x
1
iex> y
2

[doorgan]

I see. So what would be missing from Sourceror to help you implement that?
I don't have the mental bandwidth right now to help you implement it on Pathex, but the idea of Sourceror is to help provide the building blocks for other tools. So if you can point me into how the AST should look like for you, ideally, we can work towards a PR to improve on that front.

As an aside but tangentially related, I'm still unhappy that you have to keep the metadata on every single pattern match and not forget to pass it around, so maybe for the purposes of source code manipulation the regular elixir AST is not enough and we need to look into something else(hence my thoughts on using different structs for different node types), though my only concern with that is that it should add relatively low overhead so it doesn't make sourceror slower than it already is.