Supporting the FL_NEWLINE flag on nodes

The current CRuby AST supports indicating which nodes will trigger the :line tracepoint event. It does this by setting the FL_NEWLINE flag on the node in the AST. Relevant places of parse.y include the newline_node function or anywhere that mentioned FL_NEWLINE.

For the most part, it's only the nodes that are children of top_stmts or stmts in the CRuby AST. That maps almost 1:1 with any nodes that are contained within the body array of a StatementsNode node.

To support this, we will need to store a flag on each node that could trigger the :line tracepoint event. I'd rather not increase the memory size of the AST, so I'd like to reserve the upper half of the bits of the node type enum for these kinds of flags. (I think on every platform that should be 16 bits, because of both the fact that enums are generally 32 bits and the fact that it will probably need to pad the location out to a certain alignment.) (I can think of 2 other things that would be nice to store there - the fact that a call is a vcall and the fact that a symbol is a label.)

To test that we're generating the right :line events, it will definitely take the whole compilation process, so this will be a long-standing ticket. In the meantime, we can check that we're generating the right number of nodes with line events by recursively walking the ISEQs generated by the same code and counting them. What I mean is:

source = <<~RUBY
a + 
  b

c do 
  d
end
RUBY

yarv_lines = 0
queue = [RubyVM::InstructionSequence.compile(source).to_a.last]

while (iseq = queue.shift)
  yarv_lines += iseq.count(:RUBY_EVENT_LINE)

  iseq.each do |insn|
    if insn in [*, ["YARVInstructionSequence/SimpleDataFormat", *, child], *]
      queue << child
    end
  end
end

yarp_lines = 0
queue = [YARP.parse(source).value]

while (node = queue.shift)
  yarp_lines += 1 if node.newline?

  queue.concat(node.child_nodes)
end

puts "YARV: #{yarv_lines}"
puts "YARP: #{yarp_lines}"

Note that this presumes a newline? method on YARP nodes which doesn't currently exist. The tree for the source above looks like:

ProgramNode(0...23)(
  [],
  StatementsNode(0...23)(
    [CallNode(0...8)(
       CallNode(0...1)(nil, nil, (0...1), nil, nil, nil, nil, 0, "a"),
       nil,
       (2...3),
       nil,
       ArgumentsNode(7...8)([CallNode(7...8)(nil, nil, (7...8), nil, nil, nil, nil, 0, "b")]),
       nil,
       nil,
       0,
       "+"
     ),
     CallNode(10...23)(
       nil,
       nil,
       (10...11),
       nil,
       nil,
       nil,
       BlockNode(12...23)([], nil, StatementsNode(18...19)([CallNode(18...19)(nil, nil, (18...19), nil, nil, nil, nil, 0, "d")]), (12...14), (20...23)),
       0,
       "c"
     )]
  )
)

Note that the nodes that should have the newline flags on them are all the children of StatementsNode nodes (the current working theory).

Sounds great.

I'd rather not increase the memory size of the AST, so I'd like to reserve the upper half of the bits of the node type enum for these kinds of flags. (I think on every platform that should be 16 bits, because of both the fact that enums are generally 32 bits and the fact that it will probably need to pad the location out to a certain alignment.)

Currently the type is a single byte, and there are 126 node types.
Increasing it to 16 bits would add a byte for every node serialized, unless you mean to encode the type as a varint so it only takes 2 bytes if >= 128? Then we should be careful to keep the number of node types < 128, otherwise it'll be rather inefficient for node types 128-255.

If we only need one bit for FL_NEWLINE we could use the 7th bit of the type, and that then would limit to 128 node types.

I think in any case avoiding too many node types is helpful for processing the AST more easily and for performance.

(I can think of 2 other things that would be nice to store there - the fact that a call is a vcall and the fact that a symbol is a label.)

For a vcall, I think it makes more sense to reuse CallNode flags. But maybe we could store the CallNode flags (and RegularExpressionFlags too?) "in the type" although I am not sure what that would gain, except one byte if all flags are 0 (but is that a likely case? if rare it seems extra complications).

Note that the nodes that should have the newline flags on them are all the children of StatementsNode nodes (the current working theory).

If that holds we could serialize (and maybe store too while parsing) FL_NEWLINE as a bit vector in StatementsNode, i.e., a uint32[].
When deserialized, if we want Node#newline?, the flag would need to be stored on a node though, e.g., as a boolean field.
If we don't need that, and accept to e.g. only have StatementsNode#newline_nodes or so, then we could also store it as a bit vector in deserialized StatementsNode. That seems quite nice from TruffleRuby's POV and memory usage (the extra boolean/byte field would cost as much as 4 or 8 bytes due to Java alignment).

In the serialized form it's one byte, I was talking about the C structs where the enum is typically 4 (depending on architecture). Yeah I'm hoping a bit vector is possible, I'm not sure if it holds or not.

I think for the serialization API I'd be fine reserving the top bit for newline. If we end up with more node types somehow, we can always move it to another byte after the type if necessary.

I'm looking at working around this and trying to understand what is marked as newline.
I noticed for a IfNode, it seems the condition gets flagged, not the if itself.
This can be seen via:

$ ruby -e 'TracePoint.new(:line) { |tp| p tp }.enable { eval "recv = 42;\nif\nrecv; else; end" }'
#<TracePoint:line -e:1>
#<TracePoint:line (eval):1>
#<TracePoint:line (eval):3>

Line 1 is for recv = 42, line 3 is for recv, the condition of the if.

With more newlines:

$ ruby -e 'TracePoint.new(:line) { |tp| p tp }.enable { eval "recv =\n42;\nif\nrecv;\nelse;\nend" }' 
#<TracePoint:line -e:1>
#<TracePoint:line (eval):2>
#<TracePoint:line (eval):4>

so the value of of the assignment (42) seems marked, as well as the if's condition.

$ ruby --dump=insns -e '"ab#{ 123.to_f }cd"'
== disasm: #<ISeq:<main>@-e:1 (1,0)-(1,19)> (catch: false)
0000 putobject                              "ab"                      (   1)[Li]
0002 putobject                              123
0004 opt_send_without_block                 <calldata!mid:to_f, argc:0, ARGS_SIMPLE>
0006 dup
0007 objtostring                            <calldata!mid:to_s, argc:0, FCALL|ARGS_SIMPLE>
0009 anytostring
0010 putobject                              "cd"
0012 concatstrings                          3
0014 leave

So there CRuby marks "ab" if I read correctly.

I guess one reason to have the line event for a if on the condition rather than the if keyword is it makes more sense for coverage to show/highlight the condition as executed/not instead of the if keyword.

@mame

I have a working prototype at #1123 + TruffleRuby changes.
This walks the AST after it's built and calls setNewLineFlag() at the top, and some nodes override that method to place the flag on their children instead.

It's a pain to build the line offsets in Java, so for now I'll rely on the caller providing that and Truffle Source class to compute it (e.g. an ArrayList<Integer> feels so inefficient for this, and converting List -> int[] too, and Java doesn't have Arrays.indexOf(int[], int) :/).

I think it'd be good to serialize the line offsets, C is great for that (e.g. memchr()).
And with the technique mentioned by @mame (#1087) that would provide O(1) offset -> line lookup and that probably means not so needed to serialize the line number, could just compute it efficiently whenever needed (related: #775).

Another idea re serialization of the newline flag: we could have it as a "special node type" which isn't an existing node type (e.g., 255), i.e., we'd emit that 255 byte in front of the node type if there is a newline flag, and the deserializer would then understand that.

I'm trying to understand what CRuby does.
So I printed the NODE_FL_NEWLINE for RubyVM::AbstractSyntaxTree::Node:
ruby/ruby@master...eregon:ruby:rubyvm-ast-show-FL_NEWLINE

if
  rand
then
  2
else
  3
end

$ ruby -e 'pp RubyVM::AbstractSyntaxTree.parse_file("../yarp/test.rb").children.last'
(IF@1:0-7:3[Li] (VCALL@2:2-2:6 :rand) (LIT@4:2-4:3[Li] 2) (LIT@6:2-6:3[Li] 3))

Surprisingly this actually has a flag on the if, not on the rand, and (expected) on 2 and 3).
But then once compiled to bytecode the line flag is on rand, 2 and 3:

$ bin/insns test.rb
== disasm: #<ISeq:<main>@test.rb:1 (1,0)-(7,3)> (catch: FALSE)
0000 putself                                                          (   2)[Li]
0001 opt_send_without_block                 <calldata!mid:rand, argc:0, FCALL|VCALL|ARGS_SIMPLE>
0003 branchunless                           8
0005 putobject                              2                         (   4)[Li]
0007 leave                                                            (   6)
0008 putobject                              3[Li]
0010 leave

I found this in compile.c: https://github.com/ruby/ruby/blob/5f915108da7fac276875e04f3d73eac0771ca170/compile.c#L9495-L9507
So that seems to work like the first bytecode on a given line, corresponding to a NODE_FL_NEWLINE-flagged NODE gets the flag.

#1123 is merged. It marks newline nodes by walking the AST after it's deserialized. It's not only children of StatementsNode that have the flag. It's more like a small set of nodes never get the flag, and then it's their children getting it instead.

We could do the same for Ruby and C I suppose. Or we could already do this just after parsing (or during parsing if possible?). If it's done as part of normal parsing then we wouldn't need the logic for every language (C/Java/Ruby).

For compile.c I suspect it might be best to just reuse the existing logic there to add newline flags after it's been transformed to bytecode.
So unless we want this flag for Ruby nodes (i guess not), we can probably close this issue.
For Java nodes we have the flag now and I think it's reasonably fast.

Reopening this, it's not fully correct yet and we should have some testing for it.

irb(main):009:0> RubyVM::InstructionSequence.compile("a\n\nb\nc").to_a.last
=> 
[1,
 :RUBY_EVENT_LINE,
 [:putself],
 [:opt_send_without_block, {:mid=>:a, :flag=>28, :orig_argc=>0}],
 [:pop],
 3,
 :RUBY_EVENT_LINE,
 [:putself],
 [:opt_send_without_block, {:mid=>:b, :flag=>28, :orig_argc=>0}],
 [:pop],
 4,
 :RUBY_EVENT_LINE,
 [:putself],
 [:opt_send_without_block, {:mid=>:c, :flag=>28, :orig_argc=>0}],
 [:leave]]

So it seems the Integer before RUBY_EVENT_LINE is the line number, and so could know which lines should have exactly 1 node newline with a newline flag.

Another way which might be easier is to use Coverage, which shows which line should have an event and which not:

while rand
  break 42
  if rand > 2.0
    never
  end
end

$ ruby -rcoverage -e 'Coverage.start; require "./location.rb"; p Coverage.result'
{"/home/eregon/code/truffleruby-ws/truffleruby/location.rb"=>[1, 1, 0, 0, nil, nil]}

UPDATE: that is unfortunately way too slow if using a subprocess for each, and without a subprocess there seems to be a problem about "coverage already started".

I have found RubyVM::InstructionSequence#trace_points, that's very convenient to find which lines CRuby marked.
I wrote an approach based on a visitor: #1156
This manages to find almost the same lines as CRuby with a small list of exceptions and is quite simple.
For instance it marks IfNode and LocalVariableWriteNode, which CRuby does too, but after bytecode compilation the flag ends up respectively on the condition of the if and on the value of the variable write, and those can be on different lines.

I'm pondering whether we could do the logic in the parser directly, so we don't have to duplicate the logic for Ruby and Java.
It's trivial for the parser to find StatementsNode, IfNode and UnlessNode and mark them if there is no flagged node on that line yet, but I'm not sure about the order of visiting nodes and whether we can do the trick of having a new array of lines to mark when entering a block/lambda.

After learning much more about this, I don't think we can do this in the parser. The flag that we expose for the newline works, and allows the compiler to determine which nodes to consider, but the reality is the nodes that should be considered for newlines are entirely based on the order in which the compiler visits them, not any kind of relation to the parser itself. I'm going to close this for now.

Navigation Menu

Repository navigation

Supporting the FL_NEWLINE flag on nodes #1099

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Supporting the FL_NEWLINE flag on nodes #1099

Description

Activity

eregon commented on Jun 30, 2023

kddnewton commented on Jun 30, 2023

eregon commented on Jul 5, 2023

eregon commented on Jul 5, 2023

eregon commented on Jul 5, 2023

eregon commented on Jul 5, 2023

eregon commented on Jul 7, 2023

eregon commented on Jul 8, 2023

eregon commented on Jul 12, 2023

eregon commented on Jul 12, 2023

eregon commented on Jul 19, 2023

eregon commented on Jul 19, 2023

eregon commented on Jul 19, 2023

eregon commented on Jul 20, 2023

kddnewton commented on Feb 14, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions