search

antlr / antlr4

ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.
http://antlr.org
BSD 3-Clause "New" or "Revised" License
17.11k stars 3.28k forks source link

Go Generics #3457

Open dragonfax opened 2 years ago

dragonfax commented 2 years ago

Re: a recent PR that started a discussion on using Go Generics (which will be available in the language stable releases starting in February).

I've been toying with this.

Here is my solution.

But its built on top of my existing visitor fix for Go. (thats why no PR yet)

And here is an example of what a generics Go visitor looks like.

Comments

For the most part, Go generics work fine. Just like other languages. But with one glaring exception.

In Go, just like other languages, a method inherits the Type Parameters of its class (struct). But, unlike other languages, a method in Go cannot add its own personal Type Parameters. Its limited only to the Type Parameters declared its class. I.e. no generic methods on a non-generic class.

This gets in the way of Antlr's Accept() method on its nodes. So I had to move those out of the tree nodes, and replace it with a method in the visitor base class itself, using a huge (auto-generated) switch statement.

func (v *BaseJavaParserVisitor[T]) Accept(tree antlr.ParseTree) T {

    switch ttree := tree.(type) {
    case *antlr.TerminalNodeImpl:
        return v.RootVisitor.VisitTerminal(ttree)
    case *antlr.ErrorNodeImpl:
        return v.RootVisitor.VisitErrorNode(ttree)

    case *CompilationUnitContext:
        return v.BaseParseTreeVisitor.RootVisitor.(JavaParserVisitor[T]).VisitCompilationUnit(ttree)

    case *PackageDeclarationContext:
        return v.BaseParseTreeVisitor.RootVisitor.(JavaParserVisitor[T]).VisitPackageDeclaration(ttree)
...

This is a "type switch" in Go, and it means that in each case clause, the value of tree will be typed according to the Context. So VisitCompilationUnit is given an argument of type *CompilationUnitContext argument, and VisitPackageDeclaration is given and argument of type *PackageDeclarationContext and so on. Very handy.

Unfortunately the addition of generics to Go does not solve the original visitor implementation problem that Antlr has. The use of virtual methods. Addressed by my original PR. https://github.com/antlr/antlr4/pull/3456

parrt commented 2 years ago

Thanks for the detailed explanation! I'm trying to learn go and just got my first go-based parser running yesterday. I will try to catch up over the next couple of months. my first task is to come up with a benchmark for parsing in Go so we can evaluate updates to the code generation.

jimidle commented 2 years ago

I will start to take a look at this. It looks like #3456 was merged in? So let's take a look at the use of generics. Not being OOP, Go is always going to be a little different, but I agree with the idea that implementing a visitor in Go should not be too far away from the other targets, or it will need completely different documentation.

B1Z0N commented 1 year ago

@parrt what is the current state of this feature? I've quickly skimmed through all the history with this issue in place.

  1. There were two older PRs aimed at fixing this:

    • 1807

    • 1841

  2. But later on, @jcking suggested waiting till generics land in go.
  3. And after that, we ended up in this issue with @jimidle saying he'll start looking into this.
  4. While #3456 HUGE PR with generics and proper visitor support hasn't been merged in.

So right now, assuming it's the current end of the discussion, generics are landed but we are left with partially working go implementation. I'm talking about Visit and VisitChildren methods not working as expected(here's the quick fix on the user's side). I'm willing to make a contribution or participate to fix this as soon as possible.

But I'll need context from one of you on this stuff: @parrt @jimidle @dragonfax.

jimidle commented 1 year ago

To cycle back to this.

So, with the next release, the Go target is now solid and the algorithm aligns correctly with the Java reference. It has taken quite some time to get to this state and there is still a ton of things for me to fix that will reward good grammars.

Up until this point, I have not really spent much time on the visitor, other than I know it isn't quite right. The listener is "OK", but interface embedding isn't quite right and there are no generics. I did bring in a contribution that makes the tree walker a bit better, but it needs re-inventing I think.

Here's the thing though. I can't just throw everything away and do it again, because it is likely that people are depending on how it is right now. I suppose I could do that, and the release after next everyone has to change the way they use it. I think some of this isn't very useable at all as it stands. So, maybe that is the right way.

Here is my rough plan for the Go target:

Anyway, I just wanted to say that I have not forgotten about this. But the PRs and so on that were submitted so far are a bit of a patch-up, and not quite what is needed. Now that the fundamentals of the runtime are working, I will come back to this. BTW - Generics can just end up making everything slower - as well as a lookup for interface methods, now you add another one for generic type. Perhaps worrying about that is too much micro-optimization and perhaps functionally correct is more important here - but I am about to cycle in to this area now. Sorry for the time it takes @B1Z0N , but I am only one bloke ;)

B1Z0N commented 1 year ago

I am so thankful for your work (at virtually any pace). That's one thing I wanted to say.

The other thing is that. Do you accept help with this or is it solely your job here with Go target? Because as I put it here, I want to help with the implementation.

jimidle commented 1 year ago

A runtime is sort of best done by one person. At least, that’s my feeling. But what a really mean by that is that specific chunks such as walker generation need one mind. If you wanted to start from the next release as a base and give it a craic then have a go.

The reason I say the next release is that I am first going to lose all the unnecessary interface abstraction that’s a fairly big task. But then we’ll have a clean point to start from. It’s possible that the existing stuff could be preserved, but I have not properly looked at that. The walker is almost completely code gen.

On Sat, Apr 22, 2023 at 15:41 Mykola Fedurko @.***> wrote:

I am so thankful for your work. That's one thing I wanted to say.

The other thing is that. Do you accept help with this or is it solely your job here with Go target? Because as I put it here https://github.com/antlr/antlr4/issues/3457#issuecomment-1467947584, I want to help with the implementation.

— Reply to this email directly, view it on GitHub https://github.com/antlr/antlr4/issues/3457#issuecomment-1518549239, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAJ7TMFW2OGUUKMRUWNDVILXCODS3ANCNFSM5LEOOL5A . You are receiving this because you were mentioned.Message ID: @.***>

B1Z0N commented 1 year ago

Ok. I understood. The principle of conceptual integrity from the Mythical Man-Month. So yeah, I'll return to the repo after some time to check for the next release. Thanks.

jimidle commented 1 year ago

So, I did quite a bit of work on removing interfaces in generated code where possible and using the actual struct types. It all works great until we get to left recursive rules. I can use the accept interface/return struct pattern up to a point, but if $variables are used in the grammar, then there is currently no way to both accept an interface and implement context variable access. I will come back to that. If removing interfaces does not happen in this release, I will at least still be on this. When/if interfaces can go, then I can look in to how to make the visitor easier to use.