Proposal for implementing type-aware visitor for c++ target

[AmatanHead]

Hello!

I have an idea on how to improve visitors in c++. I'd like to discuss it before attempting to make a pull request.

Motivation

There are three reasons that brought me to this proposal.

The first one is that in current visitors, all type checks happen at runtime. This is bad because we loose the ability of the compiler to ensure that the program is type-correct. This also leads to excessive use of dynamic_casts which may result in performance issues.

The second one is that there is no way to implement an efficient Any class in c++. For some cases, the Small Object Optimization technique can be used to avoid unnecessary memory allocations, however, it is not a general solution.

The third one is that the default aggregateResult implementation is generally unpredictable. That is, one cannot be sure that visiting a rule will result in something useful unless there exists an explicit overload for that rule.

To address these issues, I propose implementing an alternative visitor which is capable of handling types in compile time. This visitor is not a replacement for the standard one.

The idea

The idea is to make a visitor with a single non-virtual method template

template <typename T> void visit(T);

and enable users to provide overloads for this method in subclasses. For example:

class BaseVisitor {
public:
    template <typename T> void visit(T) { ... }
}

class DerivedVisitor: public BaseVisitor {
public:
    int visit(IntLiteralContext* ctx) { ... }
}

With this setup, we can use CRTP to resolve the correct overload of the visit function.

The advantage of this method is that the compiler have full type info and therefore is able to perform type checks and optimizations.

The drawback is complicated inheritance schema.

Implementation sketch

C++ runtime changes:

The new-type visitors should derive from the base class with a single non-virtual method visitChildren:

class ANTLR4CPP_PUBLIC LiteParseTreeVisitor {
public:
    void visitChildren(ParseTree* node) {
        for (auto child: node->children) {
            child->accept(this);
        }
    }
}

The accept method should be able to handle both ParseTreeVisitor* and LiteParseTreeVisitor*.

What's going to be generated:

Consider the following grammar:

root
    : (element (';' element)*)? EOF
    ;

element
    : 'foo' value=literal # fooElement
    | 'bar' value=literal # barElement
    ;

literal
    : value=STRING # stringLiteral
    | value=NUMBER # numberLiteral
    ;

For this grammar, I propose generating the next visitor template:

// This common base can be passed to 'context.accept'.
class AbstractTypedVisitor: public LiteParseTreeVisitor {
public:
    // For every rule there is a virtual method with a corresponding name.
    // These methods serve for handling signals from 'context.accept'.
    // User does not override these methods directly.
    virtual void visitRoot(RootContext*) = 0;
    virtual void visitElement(ElementContext*) = 0;
    virtual void visitLiteral(LiteralContext*) = 0;
}

template <typename TBase>
class TypedVisitor: public AbstractTypedVisitor {
public:
    // The default implementation is to perform runtime dispatch.
    // The 'context.accept' will call the appropriate 'visitX' method.
    // The 'visitX' methods delegate to the appropriate 'visit' overload.
    template <typename T>
    void visit(T* context) {
        context->accept(this);
    }

    // For each context class there is a default 'visit' overload which simply
    // goes recursive.
    void visit(RootContext* context) {
        visitChildren(context);
    }

    // We perform dynamic type resolution for rules with named alternatives.
    auto visit(ElementContext* context) {
        // We'll need to think of an efficient type identification.
        // I propose generating enum with alternative names
        // and than doing a switch-case here.
        // For now we just use dynamic cast.
        if (auto cast = dynamic_cast<FooElementContext*>(context))
            return static_cast<TBase*>(this)->visit(cast);
        if (auto cast = dynamic_cast<BarElementContext*>(context))
            return static_cast<TBase*>(this)->visit(cast);
        __builtin_unreachable();  // This should never happen.
    }

    void visit(FooElementContext* context) {
        visitChildren(context);
    }

    void visit(BarElementContext* context) {
        visitChildren(context);
    }

    void visit(StringLiteralContext* context) {
        visitChildren(context);
    }

    void visit(NumberLiteralContext* context) {
        visitChildren(context);
    }

    auto visit(LiteralContext* context) {
        if (auto cast = dynamic_cast<StringLiteralContext*>(context))
            return static_cast<TBase*>(this)->visit(cast);
        if (auto cast = dynamic_cast<NumberLiteralContext*>(context))
            return static_cast<TBase*>(this)->visit(cast);
        __builtin_unreachable();
    }

    // All 'visitX' methods are final. User should not override them.
    void visitRootContext(RootContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }

    void visitElementContext(ElementContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }

    void visitFooElementContext(FooElementContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }

    void visitBarElementContext(BarElementContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }

    void visitStringLiteralContext(StringLiteralContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }

    void visitNumberLiteralContext(NumberLiteralContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }

    void visitLiteralContext(LiteralContext* context) final {
        static_cast<TBase*>(this)->visit(context);
    }
}

Usage example

Here is an example of a visitor that builds an AST for the grammar described above:

// -- AST nodes ------------------------------------

class FooValue {
public:
    FooValue(std::variant<int, std::string>);
public:
    std::variant<int, std::string> value;
}

class BarValue {
public:
    BarValue(std::variant<int, std::string>);
public:
    std::variant<int, std::string> value;
}

class Model {
public:
    std::vector<FooValue> foos;
    std::vector<BarValue> bars;
}

// -- Loader ---------------------------------------

class ModelLoader final: public TypedVisitor<ModelLoader> {
public:
    Model release() {
        return std::move(model);
    }

public:
    using TypedVisitor<ModelLoader>::visit;

    void visit(FooElementContext* ctx) {
        std::variant<int, std::string> value = visit(ctx.value);
        Model.foos.push_back(FooValue(value))
    }

    void visit(BarElementContext* ctx) {
        std::variant<int, std::string> value = visit(ctx.value);
        Model.bars.push_back(BarValue(value))
    }

    std::variant<int, std::string> visit(StringLiteralContext* ctx) {
        return parseNumber(ctx.value.getText());
    }

    std::variant<int, std::string> visit(NumberLiteralContext* ctx) {
        return parseString(ctx.value.getText());
    }

private:
    Model model;
}

// -- Main -----------------------------------------

int main() {
    ...
    auto tree = parser.root()
    auto loader = ModelLoader();
    loader.visit(tree);
    auto model = loader.release();
    ...
}

[garzon]

It seems that I have the same dynamic_cast performance problem mentioned, I just simply replace it with static_cast as a quick fix since there is no need to check the type all the time(though it is not perfect, but safe and enough for me), like this:

antlr4-master/tool/resources/org/antlr/v4/tool/templates/codegen/Cpp/Cpp.stg 
@@ -613,7 +613,7 @@ AltLabelStructDecl(struct, attrs, getters, dispatchMethods) ::= <<
 CodeBlockForOuterMostAltHeader(currentOuterMostAltCodeBlock, locals, preamble, ops) ::= "<! Required to exist, but unused. !>"
 CodeBlockForOuterMostAlt(currentOuterMostAltCodeBlock, locals, preamble, ops) ::= <<
 <if (currentOuterMostAltCodeBlock.altLabel)>
-_localctx = dynamic_cast\<<currentRule.ctxType> *>(_tracker.createInstance\<<parser.name>::<currentOuterMostAltCodeBlock.altLabel; format = "cap">Context>(_localctx));
+_localctx = static_cast\<<currentRule.ctxType> *>(_tracker.createInstance\<<parser.name>::<currentOuterMostAltCodeBlock.altLabel; format = "cap">Context>(_localctx));
 <endif>
 enterOuterAlt(_localctx, <currentOuterMostAltCodeBlock.alt.altNum>);
 <CodeBlockForAlt(currentAltCodeBlock = currentOuterMostAltCodeBlock, ...)>
@@ -1072,10 +1072,10 @@ AttributeDeclHeader(d) ::= "<d.type> <d.name><if(d.initValue)> = <d.initValue><e
 AttributeDecl(d) ::= "<d.type> <d.name>"

 /** If we don't know location of label def x, use this template */
-labelref(x) ::= "<if (!x.isLocal)>dynamic_cast\<<x.ctx.name> *>(_localctx)-><endif><x.name>"
+labelref(x) ::= "<if (!x.isLocal)>static_cast\<<x.ctx.name> *>(_localctx)-><endif><x.name>"

 /** For any action chunk, what is correctly-typed context struct ptr? */
-ctx(actionChunk) ::= "dynamic_cast\<<actionChunk.ctx.name> *>(_localctx)"
+ctx(actionChunk) ::= "static_cast\<<actionChunk.ctx.name> *>(_localctx)"

 // used for left-recursive rules
 recRuleAltPredicate(ruleName,opPrec) ::= "precpred(_ctx, <opPrec>)"

@@ -1047,9 +1047,10 @@ virtual void <if (method.isEnter)>enter<else>exit<endif>Rule(antlr4::tree::Parse
 >>
 ListenerDispatchMethod(method) ::= <<
 void <parser.name>::<struct.name>::<if (method.isEnter)>enter<else>exit<endif>Rule(tree::ParseTreeListener *listener) {
-  auto parserListener = dynamic_cast\<<parser.grammarName>Listener *>(listener);
-  if (parserListener != nullptr)
+  if (listener != nullptr) {
+    auto parserListener = static_cast\<<parser.grammarName>Listener *>(listener);
     parserListener-><if(method.isEnter)>enter<else>exit<endif><struct.derivedFromName; format="cap">(this);
+  }
 }
 >>

and replace the corresponding template file in the .jar

I have also modified is<>() and make some classes final:

-- antlr4-master/runtime/Cpp/runtime/src/support/CPPUtils.h --
@@ -38,12 +38,16 @@ namespace antlrcpp {
   // Convenience functions to avoid lengthy dynamic_cast() != nullptr checks in many places.
   template <typename T1, typename T2>
   inline bool is(T2 *obj) { // For pointer types.
+   typedef typename std::remove_pointer<typename std::add_const<T1>::type>::type MyType;
+    if (typeid(*obj) == typeid(MyType)) return true;
+   if (std::is_final<MyType>::value) return false;
     return dynamic_cast<typename std::add_const<T1>::type>(obj) != nullptr;
   }

   template <typename T1, typename T2>
   inline bool is(Ref<T2> const& obj) { // For shared pointers.
-    return dynamic_cast<T1 *>(obj.get()) != nullptr;
+    return is<T1 *>(obj.get());
+    //return dynamic_cast<T1 *>(obj.get()) != nullptr;
   }

- thirdparty/antlr/antlr4-master/runtime/Cpp/runtime/src/atn/RuleTransition.h -
@@ -10,7 +10,7 @@
 namespace antlr4 {
 namespace atn {

-  class ANTLR4CPP_PUBLIC RuleTransition : public Transition {
+  class ANTLR4CPP_PUBLIC RuleTransition final : public Transition {

[AmatanHead]

@garzon does it help a lot?

[garzon]

@AmatanHead well, it does help I think, especially the enter/exitRule part for listener if you use it(I haven't checked the visitor part yet), and modifying is<>() and making RuleTransition final for is<RuleTransition*> in ParserATNSimulator::closure_ which takes a lot CPU time. Maybe you should check it out by profiling

P.S.: Maybe you'll also be interested in https://github.com/antlr/antlr4/issues/2366

[thosakwe]

Would be interested in helping you create this PR.

[mike-lischke]

@AmatanHead Sorry for not participating here until now. I missed the creation of this issue and hence never got notified. I find your approach very interesting. Much of the structure in the C++ runtime is only done so because the Java runtime does it this way. This doesn't mean we cannot change that and in fact I hoped over time people like you would propose better implementations. So if you are still interested please file a PR and I will review and test that.

@garzon Also your changes look interesting and I'd like to ask you to make a PR for them. However, I'd like to see a prove that switching from dynamic_cast to static_cast has a significant advantage.

[markww]

I just came across this thread through my own work with ANTLR. I'd like to make a different argument for this proposal, from a correctness perspective rather than a performance one.

The current state of the art at the time of this writing is that ANTLR's C++ visitor returns std::any. As long as you have RTTI on (many shops do not), that makes for a very convenient generic return type that can be safely cast to the actual expected type. The problem, unfortunately, is that std::any can only contain copyable types.

In modern C++, objects can be copied (in which their contents are straightforwardly duplicated) or moved (in which the contents of the first object are taken and left with some unspecified placeholder to make the second object). You can opt to have objects be copyable, movable, or neither. There are many reasons why you might want a type to be movable but not copyable, but the most common one is probably to use std::unique_ptr.

C++'s manual management of dynamically-allocated memory is a constant source of headaches for its users, and the general way that it is tamed is to introduce lightweight memory management schemes. The simplest is to say that an object has only one long-lived pointer pointing to it and when that pointer is destroyed, the pointed-to object is destroyed as well. This is the purpose for which std::unique_ptr was introduced and one at which it excels. It is also very widespread and popular: the Google style guide pushes its users strongly towards using std::unique_ptr for ownership.

The problem, of course, is that std::unique_ptr must be unique. It cannot be copied, as that would destroy its guarantee; it can only be moved. That means that an ANTLR visitor which builds a more tailored to purpose AST from the ANTLR parse tree cannot return std::unique_ptrs to construct the links in that AST. You can work around this by returning regular old pointers through the std::any return types, only putting std::unique_ptrs around them when putting them into the AST structure, but this introduces an unnecessary hole in the proof of correctness that std::unique_ptr's semantics provide. This is exactly the problem I'm running into in my own code.

If, instead, the return type were specifiable via a template parameter as this proposal suggests, or if it were fixed but configurable at visitor generation time, then I could have my std::unique_ptr return types on visitor methods and not have to work around the copy mandate imposed by std::any.

[mike-lischke]

Thanks @markww, I think we all understand the advantages of a typed visitor implementation. We only need someone to provide an implementation as a PR here.

[olowo726]

@AmatanHead @thosakwe

I know that this thread is old but I just found it today researching how one could control the return type of the visit functions. I'm probably not be technically skilled enough to make a good PR so I won't try straight away. But perhaps the knowledge that someone else out there would appreciate a solution could inspire one of you to write a PR? Otherwise I might try myself when I've solved my immediate problem.