[ruby-core:33687] Towards a standardized AST for Ruby code
Magnus Holm
When it comes to working with Ruby files in Ruby (parsing, analyzing
etc), we definitely have a non-optimal solution right now. There's
plenty of parsers, but almost none work across implementations or are
compatible with each other:
* ParseTree. 1.8. Only parses 1.8 code (including internal). UnifiedRuby AST.
* RubyParser. Everywhere. Only parses 1.8 code. UnifiedRuby AST.
* Ripper. 1.9 / MacRuby. Only parses 1.9 code. Event based.
* Melbourne. C-extension. Only parses 1.8 code. Rubinius AST.
* JRuby's parser. JRuby. Parses both 1.8 and most 1.9 code. JRuby AST.
* RedParse. Everywhere. Parses both 1.8 and some 1.9 code. RedParse
AST. Not used as much as the other tools.
I'm proposing that we design and standardize a single AST which is
intended to be used by tools that works with Ruby syntax (Flog, Flay,
Roodi, Reek etc). Parsers can then produce this AST either directly
from the parser itself, or through a converter from the internal AST
to the standardized AST. Please be aware that this AST does not
mandate how the parsers/implementations should structure their
internal Ruby code; it's only a convention for how to work with Ruby
within Ruby in order to make it easier for all parts.
A long term goal is that every implementation should implement a
Ruby::Parser class which will parse the code with the internal parser,
and yet produce the same AST everywhere.
## Suggested plan
1. Design and standardize an AST together with a test suite (based on
current parsers' test suites)
2. Write converters for all the parsers above
3. Provide a gem with all of the converters which automatically
chooses the best internal parser on each implementation.
4. Make sure everyone targets this meta-parser instead of custom AST
provided by other parsers.
5. *If* this gets traction, each implementation can *then* provide
their own Ruby::Parser class and we can slowly deprecate the gem.
## How should we proceed with this?
First a few questions:
Everyone, do you also see the value of this, or is it only me?
Ruby core team, is there a way to make this an "official" AST?
matz, what are your thoughts on a Ruby::Parser class?
Where should we continue discussing this AST? ruby-core? A new mailing
list? Somewhere else?
Also, if you know about someone who has either written a parser or a
tool that depends on a parser, could you please point them to this
discussion?
Thanks for your consideration,
Magnus Holm
Charles Oliver Nutter
> Hey folks,
>
> When it comes to working with Ruby files in Ruby (parsing, analyzing
> etc), we definitely have a non-optimal solution right now. There's
> plenty of parsers, but almost none work across implementations or are
> compatible with each other:
>
> * ParseTree. 1.8. Only parses 1.8 code (including internal). UnifiedRuby AST.
> * RubyParser. Everywhere. Only parses 1.8 code. UnifiedRuby AST.
> * Ripper. 1.9 / MacRuby. Only parses 1.9 code. Event based.
> * Melbourne. C-extension. Only parses 1.8 code. Rubinius AST.
> * JRuby's parser. JRuby. Parses both 1.8 and most 1.9 code. JRuby AST.
> * RedParse. Everywhere. Parses both 1.8 and some 1.9 code. RedParse
> AST. Not used as much as the other tools.
For the record, JRuby will never freeze its AST. We have made changes
to it (for various reasons) at roughly the same rate since I started
working on the project in 2005. It's likely changes will continue to
happen. So any "standard" AST should be produced by a separate offline
parser.
> ## Suggested plan
>
> 1. Design and standardize an AST together with a test suite (based on
> current parsers' test suites)
> 2. Write converters for all the parsers above
> 3. Provide a gem with all of the converters which automatically
> chooses the best internal parser on each implementation.
> 4. Make sure everyone targets this meta-parser instead of custom AST
> provided by other parsers.
> 5. *If* this gets traction, each implementation can *then* provide
> their own Ruby::Parser class and we can slowly deprecate the gem.
>
> ## How should we proceed with this?
>
> First a few questions:
>
> Everyone, do you also see the value of this, or is it only me?
> Ruby core team, is there a way to make this an "official" AST?
> matz, what are your thoughts on a Ruby::Parser class?
I will cast my vote, whatever it's worth, for just enhancing and
improving Ryan's RubyParser. It already parses 1.8 code very well, and
being racc-based it's closest in structure to the canonical C Ruby
parser, which will make enhancing and improving it far easier than
one-offs. It also has an extensive test suite, backward-compatibility
with ParseTree, and reasonable performance.
Converters will always suffer from changes that happen to each impl's
AST, and will need constant maintenance. RubyParser needs no such
maintenance beyond adding new syntax features as they are added to
Ruby proper.
Native parsers will be faster; but re-walking the native ASTs and
converting them to a standard format could be nearly as "slow" as a
pure-Ruby parser.
A pure-Ruby parser will work across all implementations that
sufficiently support standard Ruby.
The only down side at the moment is that RubyParser does not support
1.9 syntax. Ryan has a bounty on adding such support (or at least
adding tests, which may encourage him to add such support) and I'll
toss in a few bucks as well.
http://blog.zenspider.com/2010/12/bounty-ruby-parser-needs-19-lo.html
I'd also love to see someone implement a native racc backend for
JRuby...but that's a separate discussion :)
At any rate, I'd find incorporating a pure-Ruby parser into stdlib the
most acceptable option, and I think RubyParser is currently the best
candidate.
- Charlie
Haase, Konstantin
> The only down side at the moment is that RubyParser does not support
> 1.9 syntax.
Also, such a parser cannot be used to inspect a live system (accessing the AST for a method or closure, for instance) unless it would be possible to access the source code of those (as in JavaScript). Therefore it cannot be used for say partial evaluation in a live system (pypy does this for generating extremely fast code).
Konstantin
Urabe Shyouhei
> Also, such a parser cannot be used to inspect a live system (accessing the AST for a method or closure, for instance) unless it would be possible to access the source code of those (as in JavaScript). Therefore it cannot be used for say partial evaluation in a live system (pypy does this for generating extremely fast code).
I doubt MRI people (namely Matz) allow you to access a live system AST. They
believe ASTs are not standard part of Ruby. These days any small part of MRI
tend to be regarded as a Ruby standard (like refinements) and that would bind
core people not to change it. Language designers tend to hesitate the
situation they cannot touch their own language internals. So, as far as this
proposal is aiming to make a standard, to inspect a live system is fairly
undesirable for them.
Ryan Davis
ParseTree had no (ok... few) problems converting from actual MRI AST to "Unified" AST (a cleaned up AST that had less implementation details in it). Providing a standard AST definition for consumers != defining the internals. It is very easy to manipulate the internal definition into an external definition.
Ryan Davis
I have asked until I was blue in the face for 1.9 to be extended w/ optional live AST access. It would make really powerful tools available to all rubyists across 1.8 and 1.9. Despite this desirable fact, it has been rejected time and time again.
I've gotten rather lame responses on why it is undesirable (usually memory--which seems moot if the AST is only available given a cmdline flag or other opt-in only option).
I've since given up asking and left it to others to ask. (Like at rubyconf 2010's "ask matz" session--thank you!)
Ryan Davis
On Dec 12, 2010, at 08:46 , Charles Oliver Nutter wrote:
> For the record, JRuby will never freeze its AST. We have made changes
> to it (for various reasons) at roughly the same rate since I started
> working on the project in 2005. It's likely changes will continue to
> happen. So any "standard" AST should be produced by a separate offline
> parser.
It certainly doesn't have to be an offline parser. It just needs a translation layer like UnifiedRuby for ParseTree.
> I will cast my vote, whatever it's worth, for just enhancing and
> improving Ryan's RubyParser. It already parses 1.8 code very well, and
> being racc-based it's closest in structure to the canonical C Ruby
> parser, which will make enhancing and improving it far easier than
> one-offs. It also has an extensive test suite, backward-compatibility
> with ParseTree, and reasonable performance.
>
> Converters will always suffer from changes that happen to each impl's
> AST, and will need constant maintenance. RubyParser needs no such
> maintenance beyond adding new syntax features as they are added to
> Ruby proper.
But if that converter ships with the impl, it is easy to keep in sync. It only took me an hour or so everytime MRI changed something and my test suite failed. Since the person implementing the change knows it best, it'd be trivial for them to change the converter at the same time (most of that hour was me figuring out what the change was and why... the code part is the easy part).
> Native parsers will be faster; but re-walking the native ASTs and
> converting them to a standard format could be nearly as "slow" as a
> pure-Ruby parser.
Totally disagree. "could" is speculative and I have plenty of proof that it is false. Manipulating an AST is nearly free compared to tracking all the BS involved with lexing and parsing ruby.
> The only down side at the moment is that RubyParser does not support
> 1.9 syntax. Ryan has a bounty on adding such support (or at least
> adding tests, which may encourage him to add such support) and I'll
> toss in a few bucks as well.
> http://blog.zenspider.com/2010/12/bounty-ruby-parser-needs-19-lo.html
And that bounty still stands... but I haven't gotten any nibbles yet. :(
> I'd also love to see someone implement a native racc backend for
> JRuby...but that's a separate discussion :)
I assume you're running the pure ruby racc runtime in jruby? How's the performance? I was talking to Alan at gemstone about optimizations to it that could speed it up a fair amount but I never got time to implement them before I left EY.
Ryan Davis
On Dec 12, 2010, at 07:55 , Magnus Holm wrote:
> ## Suggested plan
>
> 1. Design and standardize an AST together with a test suite (based on
> current parsers' test suites)
> 2. Write converters for all the parsers above
> 3. Provide a gem with all of the converters which automatically
> chooses the best internal parser on each implementation.
> 4. Make sure everyone targets this meta-parser instead of custom AST
> provided by other parsers.
> 5. *If* this gets traction, each implementation can *then* provide
> their own Ruby::Parser class and we can slowly deprecate the gem.
I think that's a good plan. I've been considering namespacing RP into Ruby::. Then it could be easy to adopt that for most implementations.
Urabe Shyouhei
> Providing a standard AST definition for consumers != defining the internals.
Definitely. I'm not against a standardised AST itself; just in doubt for that
standard to touch MRI internals. To make a live AST access possible more or
less new API is mandatory. The sadness is almost every new feature added to
MRI are seen as Ruby standard these days; we do not want that.
Ryan Davis
That's fair... tho in this case I know that rubinius and jruby would throw in support fairly quickly and would probably welcome it as a standard feature.
Rocky Bernstein
On Dec 12, 2010, at 08:54 , Haase, Konstantin wrote:
> On Dec 12, 2010, at 17:46 , Charles Oliver Nutter wrote:
>
>> The only down side at the moment is that RubyParser does not support
>> 1.9 syntax.
>I have asked until I was blue in the face for 1.9 to be extended w/ optional live AST access. It would make really powerful tools available to all rubyists across 1.8 and 1.9. Despite this desirable fact, it has been rejected time and time again.
> Also, such a parser cannot be used to inspect a live system (accessing the AST for a method or closure, for instance) unless it would be possible to access the source code of those (as in JavaScript). Therefore it cannot be used for say partial evaluation in a live system (pypy does this for generating extremely fast code).
Charles Oliver Nutter
> It certainly doesn't have to be an offline parser. It just needs a translation layer like UnifiedRuby for ParseTree.
It is not possible to translate from other formats into Unified's AST.
For example, Rubinius's current bytecode form, YARV's bytecode form,
and JRuby's upcoming IR form.
But an offline parser could do the same work as a live AST if the
source code were kept around. That's far easier to do than mapping AST
and keeping that mapping in sync.
> But if that converter ships with the impl, it is easy to keep in sync. It only took me an hour or so everytime MRI changed something and my test suite failed. Since the person implementing the change knows it best, it'd be trivial for them to change the converter at the same time (most of that hour was me figuring out what the change was and why... the code part is the easy part).
See above. JRuby's AST isn't too far removed from MRI's, but other
in-memory representations are.
>> Native parsers will be faster; but re-walking the native ASTs and
>> converting them to a standard format could be nearly as "slow" as a
>> pure-Ruby parser.
>
> Totally disagree. "could" is speculative and I have plenty of proof that it is false. Manipulating an AST is nearly free compared to tracking all the BS involved with lexing and parsing ruby.
"Could" is not speculative. It should be mathematically obvious that
it depends on the complexity of the mapping required. More mapping =
more complexity, and could easily exceed parsing overhead at some
point if ASTs diverge enough (or if AST is thrown away completely in
favor of a different format that takes a lot more massaging back into
standard form). Unified was based off MRI's AST (right?), so your
evidence is based on mapping from a slightly divergent AST to a
standard one that used to match more closely.
>> I'd also love to see someone implement a native racc backend for
>> JRuby...but that's a separate discussion :)
>
> I assume you're running the pure ruby racc runtime in jruby? How's the performance? I was talking to Alan at gemstone about optimizations to it that could speed it up a fair amount but I never got time to implement them before I left EY.
Pure Ruby, yes. Performance settles in around 50% slower than 1.9
*using the C extension*. I'm not sure if that says something about the
performance of racc (it's slow no matter what) or the performance of
JRuby (ZOMG only 50% slower than C).
- Charlie
Charles Oliver Nutter
I see a reason it couldn't/shouldn't remain in a gem and remain
offline. I think the feature to add would be getting source out of
various constructs, so we could simulate live ASTs. If it made people
feel better, it could be an official "core" gem maintained by core
devs (and other impls would probably help too.)
- Charlie
Haase, Konstantin
> I think the feature to add would be getting source out of
> various constructs, so we could simulate live ASTs.
That would be a great feature and would ease unified behavior amongst different implementations a lot. Also, it would be more stable that trying to parse sourced from files on your own (you could never be sure you actually got the right code, it's not possible for generated code, etc), and would allow other fancy features, like displaying the correct code in the backtrace on the rack error page. Also, I guess this feature is probably not to hard to implement. AFAIK it has been discussed a few times in the Rubinius IRC channel.
Konstantin
Charles Oliver Nutter
> On the other hand, I do believe that in the rubinius implementation it is
> possible to have one interpreter/system which suits both competing needs of
> performance and live introspection. I believe this because in a sense
> rubinius *is* already two implementations: a Ruby interpreter plus a JIT for
> it.
JRuby has also been a mixed-mode implementation since early 2008.
Depending on what information you want available for debugging, it's
possible to provide it in interpreted mode; but as we discussed at
RubyKaigi, all optimizing compilers will eventually want to throw away
information about code that isn't necessary for execution, and then
you have to do debugging only with the interpreter (or with a compiler
that doesn't do those optimizations, which may be fine). I don't think
you currently want/need anything we throw away, but we need to be
mindful of that possibility.
- Charlie
Charles Oliver Nutter
<Konstant...@student.hpi.uni-potsdam.de> wrote:
> That would be a great feature and would ease unified behavior amongst different implementations a lot. Also, it would be more stable that trying to parse sourced from files on your own (you could never be sure you actually got the right code, it's not possible for generated code, etc), and would allow other fancy features, like displaying the correct code in the backtrace on the rack error page. Also, I guess this feature is probably not to hard to implement. AFAIK it has been discussed a few times in the Rubinius IRC channel.
We have discussed it as well. It's not especially hard, but it does
eat up memory. Also, for implementations that support ahead-of-time
compilation (like JRuby), you'd ideally not want to ship embedded
source. That could probably be a compiler flag, though.
- Charlie
Haase, Konstantin
Being able toe turn it on and off during runtime would be a great feature and would reduce memory overhead.
Konstantin
Charles Oliver Nutter
<Konstant...@student.hpi.uni-potsdam.de> wrote:
> Being able toe turn it on and off during runtime would be a great feature and would reduce memory overhead.
If you haven't loaded code with the source saved, you can't really get
it back. On and off at runtime would only make sense for code
yet-to-be-parsed.
- Charlie
Haase, Konstantin
Yeah, but that's what I'm getting at. Say, I load the system, maybe even gems I need and don't care for their code. Then I activate the source tracking, load my app code, parse the AST with RubyParser, do some transformations, disable the source tracking again, redefine some methods and run the app. Doing it as a flag that will affect the complete life cycle of my app will have such a performance/memory impact that say partial evaluation wouldn't be feasible.
Konstantin
Rocky Bernstein
James M. Lawrence
> * ParseTree. 1.8. Only parses 1.8 code (including
> internal). UnifiedRuby AST.
> * RubyParser. Everywhere. Only parses 1.8 code. UnifiedRuby AST.
> * Ripper. 1.9 / MacRuby. Only parses 1.9 code. Event based.
> * Melbourne. C-extension. Only parses 1.8 code. Rubinius AST.
> * JRuby's parser. JRuby. Parses both 1.8 and most 1.9 code. JRuby
> AST.
> * RedParse. Everywhere. Parses both 1.8 and some 1.9 code. RedParse
> AST. Not used as much as the other tools.
Yes, this is vexing. I worked around it by creating parser
plug-ins. In retrospect it was an over-orchestrated solution to a
problem that should be fixed elsewhere.
> ## Suggested plan
>
> 1. Design and standardize an AST together with a test suite (based
> on current parsers' test suites)
> 2. Write converters for all the parsers above
> 3. Provide a gem with all of the converters which automatically
> chooses the best internal parser on each implementation.
> 4. Make sure everyone targets this meta-parser instead of custom AST
> provided by other parsers.
> 5. *If* this gets traction, each implementation can *then* provide
> their own Ruby::Parser class and we can slowly deprecate the gem.
>
> ## How should we proceed with this?
Converters seem somewhat impractical and a long way off, whereas
RubyParser is close--it just needs some 1.9 syntax.
A converter does make sense as an optimization. If a Ruby
implementation stores the internal AST of a method (presumably some
internal AST data exists before it gets converted into bytecode), it
would certainly be faster to translate a single method's AST than to
re-parse the file whence it came with RubyParser. Also remember the
load time for RubyParser is significant.
A converter makes the most sense when it is working on stored internal
AST data, preventing a needless re-parsing of the same code by an
external tool. But a converter would not be especially useful if no
internal AST is present--it's faster but it's still stupidly
unoptimized: code is parsed twice, and parsing is expensive. Might as
well use RubyParser.
It seems clear that RubyParser should come first. When it is fairly
complete, and when an implementation supports storing AST data, that
implementation can provide an optimized RubyParser (a converter).
Whether to rename RubyParser or where to put its hypothetical
optimized implementations are relatively small technical issues which
can be handled when the time comes, after RubyParser is working.
Regarding live ASTs, can't this be prototyped with RubyParser?
require 'live_ast'
require 'pp'
class Greet
def hello
puts "hello, world"
end
end
pp Greet.instance_method(:hello).ast
output:
s(:defn,
:hello,
s(:args),
s(:scope,
s(:block, s(:call, nil, :puts, s(:arglist, s(:str, "hello, world"))))))
http://github.com/quix/live_ast
It also works with define_method and with definitions inside eval.
109 lines of code, comments and whitespace included.
Charles Oliver Nutter
<quixotic...@gmail.com> wrote:
> A converter does make sense as an optimization. If a Ruby
> implementation stores the internal AST of a method (presumably some
> internal AST data exists before it gets converted into bytecode), it
> would certainly be faster to translate a single method's AST than to
> re-parse the file whence it came with RubyParser. Also remember the
> load time for RubyParser is significant.
What's the use case that requires this optimization? I'm not opposed,
but it seems like most runtime uses of parse tree are one-shot
deals...and even with an optimized form you wouldn't want to construct
a full sexp tree in hot-path code.
> It seems clear that RubyParser should come first. When it is fairly
> complete, and when an implementation supports storing AST data, that
> implementation can provide an optimized RubyParser (a converter).
Or simply make RubyParser faster...
> Regarding live ASTs, can't this be prototyped with RubyParser?
...
> http://github.com/quix/live_ast
I like the trick of using the original file source, reparsed, to get
the live AST. But the method_added hook would obviously not fly in a
real-world situation. I recognize this is just a prototype too :)
Adding .source to a few Ruby constructs would probably not be hard (I
think...I'm not the parser guy), and would enable even more than just
runtime ASTs.
- Charlie
James M. Lawrence
<hea...@headius.com> wrote:
> On Thu, Jan 27, 2011 at 7:54 PM, James M. Lawrence
> <quixotic...@gmail.com> wrote:
>> A converter does make sense as an optimization. If a Ruby
>> implementation stores the internal AST of a method (presumably some
>> internal AST data exists before it gets converted into bytecode), it
>> would certainly be faster to translate a single method's AST than to
>> re-parse the file whence it came with RubyParser. Also remember the
>> load time for RubyParser is significant.
>
> What's the use case that requires this optimization? I'm not opposed,
> but it seems like most runtime uses of parse tree are one-shot
> deals...and even with an optimized form you wouldn't want to construct
> a full sexp tree in hot-path code.
I was making the gentlemanly gesture of considering the best possible
argument for the opposing view. The best argument I see for converters
is optimization. I'm not aware of a need for it, though Magnus may
know. I expect that interest in converters will fall away once
RubyParser is finished.
>> Regarding live ASTs, can't this be prototyped with RubyParser?
> ...
>> http://github.com/quix/live_ast
>
> I like the trick of using the original file source, reparsed, to get
> the live AST. But the method_added hook would obviously not fly in a
> real-world situation. I recognize this is just a prototype too :)
Yes, not for the real world, but good enough for writing runnable
tests, if live ASTs are ever considered for official inclusion. (I
recently added functionality for live proc ASTs as well.)
> Adding .source to a few Ruby constructs would probably not be hard (I
> think...I'm not the parser guy), and would enable even more than just
> runtime ASTs.
I think a full-fledged RubyParser together with an optional flag that
enables .source is the best solution for live ASTs, if .source is
feasible enough for implementations.