Repository navigation
Lets store line column information on Nodes #775
Description
Up until now YARP has avoided storing line column information on nodes to keep memory usage low, but it seems clear that this information is worth the additional memory. In addition in the future we can work to reduce this memory with some careful bitpacking if it ends up being a problem.
There are a number of places where column and newline information is important to have and we don't have today,
- at lex time we do not know the current line or column number.
- when emitting parse errors we do not yet know the line number.
- We can construct the line numbers after parsing, but likely have to construct them in each place that we emit code to be consumed by another library (serialize.c needs to construct its line information, compile.c needs to construct its line information)
Here is a potential plan for adding this information to the AST:
- Use the existing line/col calculation which happens after parse to convert the serialize & Ruby AST output to use line/col instead of byte offset. Now consumers have the API that we plan to switch to and the rest of the changes are internal.
- Change the lexer to consume newlines in only one place so lex state can keep track of line number before tokens are emitted. (Also build the newline array the same as how we build it with a second pass to prove we successfully captured all newline information)
- Attach the new line/col information to nodes and remove all post-processing line column information tracking. While doing this make sure that setting and retrieving newline information is done through a method to allow us to change the internal storage of the line/col information in the future if memory is adversely effected.
Follow up work:
Once this is done, adding a new line flag to nodes similar to CRuby's NL flag should be easier to do, but I consider this a different task that should eventually grow its own issue.
Reacted by Jemma Issroff and Aaron Patterson
Activity
HParker commentedon Apr 6, 2023
cc: @eregon and @enebo Did I capture the main issues we identified? I am thinking we should reverse our "we only store byte offsets" decision and I think we have good reasons to do it.
enebo commentedon Apr 6, 2023
@HParker I also redid the description of #667 which covers nearly all of this yesterday. Your description I think does cover the considerations of what we can do.
Additionally, I do not believe anyone will need column information who uses serialize for execution. It still is used after that point for some uncommon parse errors during compile/build but only to raise a syntax error. We can walk source to derive if you assume the node which errors has a line number.
In #667, I also mention end lines which will be needed for a small collection of nodes (but not most of them).
eregon commentedon Apr 9, 2023
We can't store line & column instead of offset, because of #757 (comment). I.e., it would be terribly inefficient to actually get the relevant section in the source as a substring then.
Although maybe that could be avoided for execution purposes by ensuring there is no need to read from the source and all the relevant information is stored in node fields or so.
I think YARP needs to track directly OR be able to find out line and column during lexing and parsing, so that it can emit proper parse errors of the format
line:column: some parse error. I don't think we currently have a need to serialize line or column information.enebo commentedon Apr 10, 2023
@eregon you mention in #757 that we can derive line only if coverage is enabled but we need line numbers for any live thrown errors during execution so we 100% need to emit line info whether coverage is on or not. This was part of my original request having every single node derive line but only emit if the line changed (e.g. no newline node flag) and having to bin search a newline table when parser already had to do line calcs during parse for error checking (feels a bit inefficient).
I think the only concerns with maintaining line (and/or column) is just memory it takes to store it and where (parse structs or only in serialize).
Your performance of column determination I don't understand. Are you saying we need to calculate uncommon parse errors during build/parse quickly? Or is there some more common use of columns I am missing?
enebo commentedon Apr 11, 2023
After meeting the direction is specified in #808. This can be closed.
eregon commentedon Apr 12, 2023
To write down what we said during the call
That's something JRuby needs I wasn't aware of. TruffleRuby doesn't set the current line anywhere, for stacktraces it uses the offset+length stored in every AST/Truffle node.
Re column, yeah I think nothing needs it on a fast path currently. It can be computed from the offset when needed (e.g. for the debugger).
enebo commentedon Apr 12, 2023
@eregon could you show me where column is used after parse in MRI or JRuby? I don't see it.
I think it would very easy for TR to just pass offsets and JRuby to pass line + offsets. The original push back seemed to be specifying extra things in config.yml. I plan on short term just making my own branch since I do not feel I am past a discovery phase. Once I finish WIP of a running YARP in JRuby I will figure out if there are general changes which benefit us all AND whether deviation has a substantial pay off over one format. Having said that I thought we all agreed for now line would be in serialized blob.
eregon commentedon Apr 13, 2023
I don't know, besides RubyVM::AbstractSyntaxTree.
In TruffleRuby every node knows its offset+length and so indirectly its start and end line and column. And this is notably used for the GraalVM/Truffle DAP Debugger.
(Currently because we use the JRuby parser we don't have column info, so columns are always 1 or last column of that line, but that's something we always wanted to fix).
eregon commentedon Apr 13, 2023
Yes it is what we agreed in the call and let's do that. Once that lands I'll likely propose a way to not serialize the line on TruffleRuby because I think it's just overhead for TruffleRuby to serialize the line.
enebo commentedon Apr 13, 2023
I wonder if YARP landing will necessitate this going away? The trees do not match and even if they did it contains internal state which reflects a different approach. Not specific to column but just a realization that this is a coarse edge in migrating to YARP.
eregon commentedon Apr 15, 2023
Yes, I think we've mentioned it in the past. Anything under RubyVM is anyway unstable experimental stuff, and RubyVM::AbstractSyntaxTree particularly because it doesn't even have a way to access a child node by name and the child indices are not guaranteed (they can change over time). Hence, it'll be good to get rid of that and have a proper parser API.
enebo commentedon Apr 18, 2023
@eregon agreed. I only am adding this comment because Kevin pointed out that ripper is still marked experimental (I did not verify). If so then that is funny and should get changed.
kddnewton commentedon Jun 20, 2023
So we're now storing the line offsets and can use that to calculate the line/column as necessary. Fundamentally this is an implementation detail, effectively we now have this information.
So at this point we need to figure out how to get it into the serialized form, and what that information should look like. Should we include the table of newline offsets and then provide functions to get the start line/end line as necessary? Should we include all of the information on every node? I'm not clear on the answers to these @enebo, @eregon
eregon commentedon Jun 21, 2023
@kddnewton JRuby needs them, and it would be rather costly for them to compute them when deserializing (it would be Java code that needs warmup + the cost to deserialize the table, and so delays general startup/warmup).
TruffleRuby (at least currently) doesn't need lines, it only needs
start + length.I think we should do this via an env var or some kind of configuration or so, to decide whether to serialize
start + lengthor both (start + lengthandline). It would then be dealt with at templating time (needed e.g. to have only the corresponding fields inNode).Like:
class Node { <%= 'public final int line;' if ENV["SERIALIZE_LINE"] == "true" %> }(and likely move
ENV["SERIALIZE_LINE"] == "true"to aserialize_line?predicate for convenience inbin/template.rb)To be clear, I think
serialize_line?should only be used in Java templates and in serialize.c.erb, NOT in Ruby templates or other files, where I think it's fine to just assume SERIALIZE_LINE to be false (for simplicity and readability).So like #808 (comment) but I think it's good to avoid serializing line when not needed, currently I think only JRuby wants it in serialization (e.g. for Ruby nodes and for TruffleRuby it would be memory overhead)
eregon commentedon Jun 21, 2023
@enebo Maybe JRuby would only need line and not
start + length? That means no column information then and no way to find where a node is in the source. I think that's probably better for later, when we are sure there is no need forstart + lengthfor compilation in JRuby.It's also connected to not serializing locations at all.
eregon commentedon Jul 5, 2023
See #1099 (comment)
I think we don't need to store line numbers in nodes, if we have O(1) offset->line conversion (#1087).
So I will optimistically close this, and I think instead we should serialize the line offsets/bit vectors.