AST format

[iliabylich]

I propose to take some in inspiration from this config. There are two things that are different from whitequark/parser and right now I think it was my mistake to introduce them: IfMod and IfTernary should go away, If node is enough to cover all cases.

Apart from this it makes a lot of sense to me. Thoughts on current config:

• Assignment - in static analysis from my experience people never look for "an abstract assignment", there's always a need to find a certain type of assignment, like lvar assignment (to track local variables) or ivar assignment. I think it makes sense to introduce separate nodes for all types of assignment like it's done in whitequark/parser, ruby_parser and all parsers derived from them.
• Binary - I think it's too generic and complex at the same time. 2 + 2 is a Binary, right? I think it should have the same type as foo.bar, because it is a method call. On the other side all types of "real" binary operators need their own node types because they have special behaviour.
• CharacterLiteral - it should be just a String, there's no different between them.
• FloatLiteral - let's keep it.
• Identifier - this node has no value on its own and it always requires tracking current context to understand the meaning.
• IfModifier - like I described above a single If node is enough. If there's a need to track a modifier version source maps can be used, but there's no different in how "normal if" works vs "if modifier". AST should represent meaning, not layout.
• ImaginaryLiteral - let's keep it
• IntegerLiteral - keep
• OperatorAssignment - keep, there's an equivalent in whitequark/parser
• Program - ehh, we can keep it, both whitequark/parser, ruby_parser (and IIRC all parsers except parser.y/Ripper) use begin node for it, because there's difference in how top-level block of code is treated comparing to let's say block body or begin..end.
• RationalLiteral - keep
• Range - I think it makes sense to split it to .. and ... ranges
• Redo / Retry - keep
• Statements - should be just begin I guess
• Ternary - redundant, can be replaced with If
• UnlessModifier - redundant, can be if with "inverted" branches
• UntilModifier - redundant, there can be a single Until node
• VariableReference - sounds a bit verbose, lvar or localvariable should be enough
• WhileModifier - redundant, there can be a single While node

@kddnewton PTAL at the document that I linked above and let me know what you think

[eregon]

This sounds good to me, agreed focusing on semantics is good and makes the number of nodes smaller.

What's Program? Is it just a sequence of statements? Then should it be Begin or Sequence or so?
If it's special maybe TopLevel or so?

Range - I think it makes sense to split it to .. and ... ranges

Why not a simple exclude_end boolean flag for that? I think the difference between them is minimal.
BTW maybe it should be named RangeLiteral?

UnlessModifier - redundant, can be if with "inverted" branches

Ah right, you'd swap the if_true/if_false fields then for converting an unless to If like parser does?
Sounds fine, although maybe a little bit confusing with the order of branches in the source.

VariableReference - sounds a bit verbose, lvar or localvariable should be enough

I think it'd be nice if the ReadXVariable and WriteXVariable have clearly corresponding names (I'm not a fan of InstVarNode/InstAsgnNode in JRuby or lvar/lvasgn in parser, it's not obvious they complement each other or that "var" reads a variable).
So e.g. ReadLocalVariable/WriteLocalVariable (or -LocalVar or -Local or -LVar), ReadInstanceVariable/WriteInstanceVariable (or -IVar), etc for Class, Global variables. For Global variables might want to have special nodes for some special globals like $1-$9.

[enebo]

Just adding in what JRuby does for its AST. It is very similar to MRI but a bit more along your suggestions with respect to Nodes. Seems like beyond clarity perhaps alignment should be considered here? If adding an extra boolean makes a particular node too wide to fit into, let's say, a clean arena allocation scheme then perhaps it makes sense to break some of these into distinct nodes.

* `Assignment` - in static analysis from my experience people never look for "an abstract assignment", there's always a need to find a certain type of assignment, like lvar assignment (to track local variables) or ivar assignment. I think it makes sense to introduce separate nodes for all types of assignment like it's done in whitequark/parser, ruby_parser and all parsers derived from them.

JRuby has these broken up by type (and so does MRI).

* `Binary` - I think it's too generic and complex at the same time. `2 + 2` is a `Binary`, right? I think it should have the same type as `foo.bar`, because it is a method call. On the other side all types of "real" binary operators need their own node types because they have special behaviour.

we have an OperatorCallNode used for both uni and bin ops. It just extends CallNode. Not really sure from a semantic standpoint why these are all just not CallNode?

* `CharacterLiteral` - it should be just a `String`, there's no different between them.

This is what we do.

* `FloatLiteral` - let's keep it.

ditto (FloatNode)

* `Identifier` - this node has no value on its own and it always requires tracking current context to understand the meaning.

We mix runtime with parser for this and it is a RubySymbol (yeah eager symbols)

* `IfModifier` - like I described above a single `If` node is enough. If there's a need to track a modifier version source maps can be used, but there's no different in how "normal if" works vs "if modifier". AST should represent meaning, not layout.

This is just IfNode (all conditionals are just IfNode).

* `ImaginaryLiteral` - let's keep it

same

* `IntegerLiteral` - keep

same

* `OperatorAssignment` - keep, there's an equivalent in whitequark/parser

we have OpElementAsgnNode but we create additional types for OpAsgnAndNode and OpAsgnOrNode. Seems this could all just be a single node. JRuby is old and our AST also used to be our interpreter so we still have some specialization not needed.

* `Program` - ehh, we can keep it, both whitequark/parser, ruby_parser (and IIRC all parsers except parser.y/Ripper) use `begin` node for it, because there's difference in how top-level block of code is treated comparing to let's say block body or `begin..end`.

same as MRI

* `RationalLiteral` - keep

same

* `Range` - I think it makes sense to split it to `..` and `...` ranges

We only use a single DotNode with an exclusive field (Range is a better name and what we use for the operand in our IR).

* `Redo` / `Retry` - keep

We have RedoNode,RetryNode, NextNode, and ReturnNode

* `Statements` - should be just `begin` I guess

??? From AST perspective I guess this is ListNode.

* `Ternary` - redundant, can be replaced with `If`

This is just IfNode (all conditionals are just IfNode).

* `UnlessModifier` - redundant, can be `if` with "inverted" branches

This is just IfNode (all conditionals are just IfNode).

* `UntilModifier` - redundant, there can be a single `Until` node

We have a single UntilNode

* `VariableReference` - sounds a bit verbose, `lvar` or `localvariable` should be enough

We differentiate variable types with their own nodes (e.g. LocalVariableNode)

* `WhileModifier` - redundant, there can be a single `While` node

We have a single WhileNode

[eregon]

we have OpElementAsgnNode but we create additional types for OpAsgnAndNode and OpAsgnOrNode. Seems this could all just be a single node. JRuby is old and our AST also used to be our interpreter so we still have some specialization not needed.

I guess that goes back to "real" binary operators mentioned by @iliabylich above, which I guess means only &&= and ||=?
i.e. we need to differentiate a.foo = b and a.foo ||= b/a.foo &&= b.
Things like a.foo &= b could be desugared eagerly to a.foo = a.foo & b, that seems nice.

But a.foo ||= b cannot be desugared or at least not the same way, since it means (defined?(a.foo) && a.foo) || (a.foo = b) (the defined? check can be skipped in some cases) and not a.foo = a.foo || b.
I'm not sure about &&= but in any case it's different because it's a control flow operator vs a method call.

[enebo]

@eregon yeah you're right. I forgot about how those worked.

[iliabylich]

@eregon I think we shouldn't do desugaring by default or otherwise all linters will complain by default with suggestions to replace a = a && b to a &&= b

[eregon]

@iliabylich That's a good point.

Maybe we can do desugaring as an option in the future then (not needed for the first version). It seems quite convenient for Ruby interpreters and potentially for semantic analysis/other usages too (potentially we could even desugar pattern matching which could be a pretty cool feature for Ruby interpreters).
One issue with desugaring is we'd need a concept of hidden local variables or so, because a.foo.bar += b shouldn't execute a.foo twice and also not add local vars visible to Binding. Could be as simple as local vars with an invalid prefix, e.g. starting with some meta char like % or so.

[kddnewton]

Thanks friends. This is really good discussion, and very helpful for me to understand all of your various use cases. I'll try to summarize what has been discussed so far so that we can come to the same understanding.

Design goals

First of all, I think we need to have a discussion around the overarching goal of the design of the tree. Currently, I'm seeing 3 different applications being discussed, and we need to agree on which one we're pushing for first before pushing for all of them at the same time.

• The first one I see is an accurate representation of the syntax being used (as opposed to the semantics that they imply). For example, with a CharacterLiteral node (e.g., ?a) the syntax that's being used is the ? literal. However the semantics are just a string literal. A formatter would be interested in knowing that the user used the ? syntax. A linter may be interested, or may not. A language implementation doesn't care at all, since it's all going to be compiled into the same thing. Technically I believe this representation is more commonly known as a concrete syntax tree.

• The second is a representation of the semantics of the program. This would replace CharacterLiteral with StringLiteral, collapse all of the modifier forms into nodes just based on their keyword, consolidate with a single Call node, etc. I believe this is more commonly known as the abstract syntax tree.

• The third is the desugared representation that @eregon mentioned, which is much closer to how the code actually gets compiled. I don't know if there's a term for this; I think it would just be called an abstract syntax tree that is a higher level of abstraction.

All of these trees have their purposes and their tradeoffs. CSTs are going to be necessary for formatters but come at the cost of a larger number of nodes and may require more effort to compile. ASTs are going to be useful for most folks, but risk dropping information that a formatter or linter might be interested in and require them to go back to the source. The higher-level AST risks dropping even more information, but is likely the easiest to compile for language implementers.

The direction I'd like to go in is to build as abstract of a tree as possible while retaining all of the necessary information from the source such that consumers of this library don't need to go back into the source to gather more information. (As just an example of that, currently in the Binary node that ripper gives back the operator comes back as a symbol, and thus no location information is provided for that operator. This has led to consternation for syntax_tree for formatting but also error_highlight for alignment.) I think we can accomplish this with minimal changes to what we already have, while continuing to push in this direction going forward.

Ideally, I'd like to provide APIs that also provide the desugaring that has been mentioned. I think that the more logic we can move into here and out of the various implementations and tools, the easier it's going to be moving forward for all of the tooling. I know @eregon even mentioned at one point desugaring pattern matching like ruby-next does, which could be very interesting. But for the first pass, I honestly don't even want to touch this until we get it completely functional and compatible.

Current nodes

Nodes we're not changing

With all of that in mind, here are the nodes that I believe we're all agreed on should stay as they are:

• FloatLiteral
• ImaginaryLiteral
• IntegerLiteral
• RationalLiteral
• Redo
• Retry

Nodes we're considering collapsing

Next, here are the nodes that you are suggesting we collapse into other nodes:

• CharacterLiteral - My issue with collapsing this into a StringLiteral node is that the shape of the node is pretty different. At the moment a CharacterLiteral contains a single token, whereas a StringLiteral node would contain a beginning (quote or %), an ending, and an array of child nodes (plain string content, interpolated expressions, interpolated variables).

  We could try to collapse this by making StringLiteral's beginning and ending be optional, and the array of child nodes have length one containing only the token with the content. That would accomplish the goal of lowering the number of nodes, while still maintaining all of the necessary information for all tools. I'd be okay with this change once we get to that point.

• IfModifier/UnlessModifier/UntilModifier/WhileModifier - Currently the shape of the If node is going to contain the starting if keyword, the predicate node, the body node (a Statements node since it's a list of expressions, not just a single one), an optional consequent node, and an optional end token. Note that there is always the consequent node or the end token. The IfModifier node contains the predicate node (which cannot have any comments attached), the if keyword, and the body node (not a Statements node).

  We could try to collapse this by removing the limitation that there is always a consequent or an end token, making the child node the first in the array of the Statements's body, and maybe keep a flag around that says that the keyword was used in the modifier position.

• Ternary - Current shape contains 3 nodes (predicate, truthy, falsy) and 2 tokens (? and :). If is obviously pretty different.

  I'm most resistant to collapsing this one. The shape is really different and this falls much closer to desugaring than consolidating nodes. To make it so that you know where the tokens are you're going to end up making a lot of things optional or overloading the meaning of the various tokens (like token1 and token2 or similar). I get what you all are saying about them being semantically equivalent, but since they're so syntactically different I don't think we can collapse it easily and maintain all of the necessary information.

Other nodes

Finally, here are the various other nodes:

• Assignment - We've talked about splitting these up into different assignment types. I like @eregon's suggestion to name them clearly with read and write, I think that makes it much more obvious what is going on. Personally, I really want the noun first so that alphabetizing the nodes keeps them logically together. Taking all of that into account, I propose:

  • ClassVariableRead/ClassVariableWrite - @@foo
  • ConstantRead/ConstantWrite - Foo, ::Foo, Foo::Bar, ::Foo::Bar
  • FieldRead/FieldWrite - Foo.bar and foo.bar
  • GlobalVariableRead/GlobalVariableWrite - $foo
  • InstanceVariableRead/InstanceVariableWrite - @foo
  • LocalVariableRead/LocalVariableWrite - foo

  These are a lot of nodes, but I know that at least in MRI it'll probably make it quite a bit easier to compile since these all result in different instructions. I'm just not sure about the FieldRead one? I'm taking that naming convention from ripper but maybe there's a better one for use here?

• Binary - this is any infix operator. I have a hunch (though this is completely unverified) that this is split out in ripper because most of the time it's replaced by an optimized instruction in YARV (like opt_plus, opt_minus, etc). I'm fine with replacing this with a generic call node though. Also because foo.+(bar) should really be the same node as foo + bar, but it's not going to be at the moment. So action = replace with Call. I think we'll need to handle &&, ||, and, and or separately though since they impact control flow.

• Identifier - agreed that this doesn't really provide a lot of value. It should be removed once we have more of the parser built.

• OperatorAssignment - keep, but maybe provide a different node for &&= and ||= since those change control flow.

• Program - technically this is different from a regular set of statements because BEGIN and END can be used within this context only, but it's really not all that different. I'd be fine replacing this. But I'd like to rename it to Scope to match RubyVM::AST. We're going to have to end up tracking local variables anyway, so we may as well do it with the same named node.

• Range - there's been some discussion on whether this should be split into RangeInclusive/RangeExclusive, to just have an exclusive flag on it, or just to keep it as it is. Personally I'd like to go the flag direction, to keep the number of nodes small but also keep all of the necessary information.

• Statements - as mentioned in the Program section, I think this can also just be a Scope node.

• VariableReference - @iliabylich this one is much more than just an lvar though, it's also self, true, false, nil, any local, or any non local variable. It looks like the parser gem and RubyVM::AST have nodes for self, true, false, and nil which is kind of the equivalent here. I'm fine splitting this out into those kinds of nodes as well here.

@iliabylich I love the layout of that file, it makes a lot of sense. Overall I'm very happy to take inspiration from it. Thanks for the detailed issue. Let me know what you think of the points I've made above.

[iliabylich]

Wow, that's a thorough and huge review of everything we wrote above, thank you.

1. On the first list of nodes that we agreed with - yes, I fully support it.
2. CharacterLiteral - not super opinionated, but I think in most contexts it's interchangeable with StringLiteral (except for one when a formatter needs to convert it to a string or other way around) and it doesn't matter how it's written. Do you see any use-case for this node except for linter/formatter?
3. IfModifier/UnlessModifier/UntilModifier/WhileModifier - the fact that it's an if/unless modifier can also be easily takes from source maps, and I think it makes sense to "move" responsibility to calculate layout-specific information to layout data holders (locations). Sorry, not sure if it's a good metaphor, but it's somewhat similar to doing CSS animations in JS while it's possible to write them in CSS that was designed for it.
4. Ternary - whitequark/parser treats ? as then, and : as else, and so it perfectly fits the structure of the If node. Once again, I think information about how the code looks should be in the metadata.
5. Assignment - agree on splitting. How about using Get/Set suffixes? Read and Write sounds a bit IO-oriented to me 😄
6. Binary - agree on turning most of them into Call/Send, and that control-flow operators need their own nodes.
7. Identifier - agree.
8. OperatorAssignment - agree
9. Program - the reason why I think it's redundant is because visitors that operate on AST usually have their constructors that can handle top-level node in a special way. Maybe we can keep it to enforce users of the parser to indicate it in a more explicit way. Also, there will be nodes for class/module/def, right? They could be responsible for opening and closing scopes, WDYT?
10. Range - I have a bad feeling about introducing boolean flags, but in this case I think it's worth it.
11. Statements - I think a generic Begin makes more sense, it could be used in other contexts too, not only as a begin..end multi-statement of condition or loop: it can be in interpolation to store location of #{ and }, or in code like a = (1; 2). I have no strong opinion actually, both Statements and Scope sounds good to me too.
12. VariableReference - good question on wether it makes sense to have a separate node for false, true, self and others. How do you feel about having a Literal node that has an enum? Or is it too much?

[eregon]

Thanks for the summary!

The direction I'd like to go in is to build as abstract of a tree as possible while retaining all of the necessary information from the source such that consumers of this library don't need to go back into the source to gather more information.

👍 Agreed this seems a good first target. Maybe it's even good enough to not need the concrete syntax tree?

• whereas a StringLiteral node would contain a beginning (quote or %), an ending, and an array of child nodes (plain string content, interpolated expressions, interpolated variables).

I'm a bit surprised about a StringLiteral node having multiple children, and potentially being interpolated which I would say it's then not really a literal (arguable I know :)). I think interpolated Strings should use a different node class.
Is it also multiple children for "abc" \ (on next line) "def"? That seems like this level of details should be removed for the AST, or at least there should be a way to get the single string literal value (for not interpolated).
Re CharacterLiteral could it be represented as like only the beginning and no ending or so, or as a flag?

• the body node (a Statements node since it's a list of expressions, not just a single one),

Wouldn't it make sense if it's a single statement/expression to just be that node? And so only a Statements if multiple statements?
Also we probably want either to make the field "optional" or give it a special value which is not just a regular Nil literal to know if there is anything in one of the two branches/bodies (useful for tooling and to save memory footprint). JRuby has NilImplicitNode vs NilNode for this.

Re Ternary, agreed with @iliabylich, structurally they are very similar and even syntactically (e.g. same order of condition, ifTrueBody, ifFalseBody). Of course we need to retain the position of the ?/: for the formatters/linters.

Re FieldRead/FieldWrite those are method calls with 0 arguments (vcalls), I don't think they are related to variables, syntactically and semantically.
Other node names sound great to me.

I have a hunch (though this is completely unverified) that this is split out in ripper because most of the time it's replaced by an optimized instruction in YARV

There are some opt_* instructions also for non-operators like size, min, max, etc.

Scope nodes with a list of local variables seems nice.

• Statements - as mentioned in the Program section, I think this can also just be a Scope node.

I think these need to be separate nodes, because there are many Statements without their own local var scope. Scope are only one for top-level, one per method defintion, one per block definition and oen per module/class-end I think that's all of them.

@iliabylich

5. Assignment - agree on splitting. How about using Get/Set suffixes? Read and Write sounds a bit IO-oriented to me smile

Mmh, but one does read or write a variable not "get a variable" (AFAIK), and it ends up reading/writing memory. Also I find it's a feature that it's not a single letter difference between them since they typically have very different logic (the Write part being much more complex often).

Begin sounds unclear to me, I think having both Scope and Statements is much clearer.

I think separate nodes for true/false/nil and self are good to have. They typically are handled differently at least for interpretation (they end up as BooleanLiteralNode/NilLiteralNode/SelfNode in TruffleRuby). Especially self is very different and not really a literal or at least not a constant value. A common superclass seems nice for true/false/nil for other usages. Maybe even a common superclass for all "true literals"/"actually constants at parse time" like integer/float/string/symbol literals, etc. That's e.g. useful to know they have no side-effects, do not depend on the execution, etc. It's harder to decide for a Range literal though, but maybe we can consider Range to never be "constant at parse time" because that's kind of implementation-dependent (e.g. 1..3 is but 1..nil isn't on TruffleRuby, not sure this is the same on CRuby).
I think we don't initially need such superclasses though, so it's more of a "what could be nice for some applications".

[enebo]

"The direction I'd like to go in is to build as abstract of a tree as possible while retaining all of the necessary information from the source such that consumers of this library don't need to go back into the source to gather more information."

Just as a show of support...

fwiw more nodes for runtimes will mean more code but not really more complexity. Processing binary in addition to a call will have an extra case stmt which just calls the same compilation that we would do for a 2 argument call. So to support other use cases I do not think this is a big burden (to JRuby at least). If we are literally talking about using switches for this processing even a ternary/if will just be two labels referencing the same code (assuming they have the same field layout).

As another dimension of discussion in formulation of nodes...

Also when the actual data stored is looked at more I am interested in less allocations to build the tree so I also think that is a orthogonal aspect to what nodes may be present. More nodes but same-sized nodes is a virtue (tree navigation of array). I know the goal is to be approximately the same speed as MRI but I suspect that can be improved upon. Analysis of nodes per source and a heuristic to arena alloc the right amount up front likely will be a win.

[kddnewton]

Okay cool, this definitely feels like we're getting somewhere. In terms of direction, it sounds like we're onboard with an AST that maintains just enough information to map back to source but not so much that we explode the number of nodes. With the additional feedback here, I'm going to re-summarize with less detail now.

• Assignment split - let's go with Read/Write for now, I agree with the points @eregon made
  • Call - foo.bar =
  • ClassVariableRead/ClassVariableWrite - @@foo =
  • ConstantRead/ConstantWrite - Foo =, ::Foo =, Foo::Bar =, ::Foo::Bar =
  • GlobalVariableRead/GlobalVariableWrite - $foo =
  • InstanceVariableRead/InstanceVariableWrite - @foo =
  • LocalVariableRead/LocalVariableWrite - foo =
• Binary split
  • Call - a + b
  • And - a && b, a and b
  • Or - a || b, a or b
• Call new
• CharacterLiteral collapse - yeah, you're right. There's not real use case for this outside of linters/formatters where it needs to exist where it's not just a string literal. I'm convinced.
• FalseLiteral new
• FloatLiteral keep
• IfModifier/UnlessModifier/UntilModifier/WhileModifier collapse - okay, I am convinced to collapse these into If, Unless, Until, and While. However I do not want to collapse Unless into If with reversed predicates. It feels way too much like desugaring to me, which we can deal with at a later date.
• ImaginaryLiteral keep
• IntegerLiteral keep
• NilLiteral new
• OperatorAssignment split
  • OperatorAssignment - +=, -=, etc.
  • AndAssignment - &&=
  • OrAssignment - ||=
• Range keep - but introduce a boolean flag for exclusivity
• RationalLiteral keep
• Redo keep
• Retry keep
• Scope new
• SelfLiteral new
• Statements rename - I really like the name List that @enebo mentioned. I'd like to go with that as it's more obvious that it's just a list of statements separated by terminators.
• Ternary collapse - oh man the then keyword! I completely forgot that that will map so well. In this case I am convinced, this can be replaced by just an If node and the location information stored on it will be enough to know if it was a ternary to begin with.
• TrueLiteral new

On the various other questions that folks asked:

• @iliabylich yes, there will definitely be nodes for class, module, and def. However I'd rather keep all scope-related logic in a single node and not make it common to a bunch of other nodes. I have a feeling the scope node is going to be particularly complex/important since it's going to track the local table and parameters.
• @eregon I was thinking "a" \ "b" would be a StringConcat node, since you'd want to track the position of the \ as well as the left and right. I know that can be desugared to a single string literal as well, we can talk about that in the future.

With all of this in mind, I'll get cracking on these changes.

[kddnewton]

Also, I'm going to convert this into a discussion, since I have a feeling this is going to stay around for a while.