Typen aus mehrdeutiger Basisklasse holen

Kellerautomat

Hallo Leute!

Ich implementiere gerade ein Visitor-Pattern fuer den Syntaxbaum meines Compilers. Von der Grundidee her habe ich mich am Alexandrescu orientiert, allerdings ist mir der nicht flexibel genug. Und zwar moechte ich den Visitor so haben, dass ich jeden beliebigen Rueckgabetyp haben kann, ohne, dass ich die "visited" Klassen veraendern muss.

In meinem Syntaxbaum gibt es 3 verschiedene Klassenhierarchien: Expr, Stmt und Decl. Von jeder Hierarchie gibt es wiederum mehrere abgeleitete Klassen. Ein Visitor soll gleichzeitig Visitor aller 3 Hierarchien sein koennen und je Hierarchie einen unterschiedlichen Typ zurueckgeben koennen.

Diese Basisklassen sehen wie folgt aus:

struct Expr : IVisitable<Expr>
{
	...
};

struct Stmt : IVisitable<Stmt>
{
	...
};

struct Decl : IVisitable<Decl>
{
	...
};

IVisitable hat nur eine einzige Methode accept(), die rein virtuell ist und von den abgeleiteten Klassen ueberschrieben wird.

template <typename Hierarchy>
struct IVisitable : private IBase
{
	virtual void accept(IVisitorImpl<Hierarchy>& visitor, void* result) = 0;

protected:
	IVisitable() {}
	IVisitable(IVisitable&&) {}
};

Eine konkrete Klasse, z.B. StmtIf, sieht dann so aus:

struct StmtIf : Stmt
{
	VISITABLE(Stmt, StmtIf)

	...
};

VISITABLE ist ein Makro, das besagte Methode implementiert:

#define VISITABLE(Hierarchy, Self) \
	virtual void accept(IVisitorImpl<Hierarchy>& visitor, void* result) override \
	{ \
		if(auto concreteVisitor = dynamic_cast<VisitorImpl<Hierarchy, Self>*>(&visitor)) \
			concreteVisitor->visitImpl(*this, result); \
	}

Um den Rueckgabetyp von der Hierarchie unabhaengig zu bekommen, war meine Idee, anstatt einen richtigen Returnwert zu verwenden, einen void* durchzureichen, der quasi der Outputparameter fuer den Returnwert ist. Wenn das Visitable Objekt dann den Visitor aufruft, fuehrt der Visitor selbst einen Cast auf den richtigen Typen durch.

IVisitorImpl ist im wesentlichen eine leere Klasse und dient nur dazu, dass zur Compilezeit sichergestellt wird, Visitoren welcher Hierarchie das Objekt akzeptiert. Ein Visitor fuer Expr kann also z.B. keine Stmts besuchen.

template <typename Hierarchy>
struct IVisitorImpl : private IBase
{};

Jetzt gibt es in jeder dieser Hierarchien verschiedene Klassen, die der Visitor besuchen kann. Fuer jede dieser besuchten Klassen soll eine rein virtuelle Funktion generiert werden, die der User in seinem Visitor ueberschreiben muss. Das wird mit folgendem Template erledigt:

template <typename Hierarchy, typename Visited>
struct VisitorImpl : virtual IVisitorImpl<Hierarchy>
{
	virtual void visitImpl(Visited& visited, void* result) = 0;
};

visitImpl ist die vorhin angesprochene Funktion, die im Visitor die Konvertierung (void* <-> Returnwert des Users) vornimmt und wird nur intern verwendet, der User bekommt davon nichts mit. An dieser Stelle ist der Rueckgabetyp nicht bekannt, daher ist sie rein virtuell.

visitImpl wird dann von Instanzierungen von VisitorGen implementiert. VisitorGen implementiert alle visitImpl rekursiv und generiert gleichzeitig die vom User verwendeten, rein virtuellen funktionen. Zusaetzlich zu den gezeigten Templates gibt es noch jeweils eine Spezialisierung fuer void, die mit dem Outputparameter nichts macht, da es keinen Returnwert gibt.

template <typename Hierarchy, typename... Visited>
struct VisitorGen;

template <typename T, typename Hierarchy, typename Head1Visited>
struct VisitorGen<T, Hierarchy, Head1Visited>
	: VisitorImpl<Hierarchy, Head1Visited>
{
	virtual void visitImpl(Head1Visited& visited, void* result) override final
	{
		*static_cast<T*>(result) = visit(visited);
	}

	virtual T visit(Head1Visited&) = 0;
};

template <typename T, typename Hierarchy, typename Head1Visited, typename Head2Visited, typename... TailVisited>
struct VisitorGen<T, Hierarchy, Head1Visited, Head2Visited, TailVisited...>
	: VisitorImpl<Hierarchy, Head1Visited>
	, VisitorGen<T, Hierarchy, Head2Visited, TailVisited...>
{
	using VisitorGen<T, Hierarchy, Head2Visited, TailVisited...>::visitImpl;
	using VisitorGen<T, Hierarchy, Head2Visited, TailVisited...>::visit;

	virtual void visitImpl(Head1Visited& visited, void* result) override final
	{
		*static_cast<T*>(result) = visit(visited);
	}

	virtual T visit(Head1Visited&) = 0;
};

Sollte jemand eine Idee haben, wie ich hier doppelten Code vermeiden kann, nur zu. Das Problem dabei sind allerdings die using-Deklarationen, die ich benoetige, um Compilerwarnungen wegen verdeckens virtueller Funktionen loszuwerden.

Nun gibt es noch eine kleine Klasse, die nichts anderes macht, als von VisitorGen abzuleiten und ein nested Typedef zu definieren. Dies ist letzendlich die Klasse, von der der User seine Visitoren ableitet.

template <typename T, typename Hierarchy, typename... Visited>
struct Visitor : VisitorGen<T, Hierarchy, Visited...>
{
	typedef T ReturnType;
};

Was jetzt noch fehlt, ist eine Wrapper-Funktion, die einen Visitor auf ein Visitable anwendet, ich habe sie applyVisitor genannt. Meine Idee war, dass applyVisitor nun das Objekt fuer den Rueckgabewert erstellt, den void* an accept() der Hierarchie weitergibt, die wiederum den korrekten Overload von visit() im Visitor aufruft, und dass der Visitor dann letztendlich den Rueckgabewert setzt. applyVisitor kann diesen dann zurueckgeben.

template <typename Visitor, typename Visitable>
void applyVisitorImpl(Visitor& visitor, Visitable& visitable, std::integral_constant<bool, true>)
{
	visitable.accept(visitor, nullptr);
}

template <typename Visitor, typename Visitable>
auto applyVisitorImpl(Visitor& visitor, Visitable& visitable, std::integral_constant<bool, false>)
{
	typename VisitorTraits<Visitor, Visitable>::ReturnType result;
	visitable.accept(visitor, &result);
	return result;
}

template <typename Visitor, typename Visitable>
auto applyVisitor(Visitor& visitor, Visitable& visitable)
{
	return applyVisitorImpl(visitor, visitable, std::integral_constant<bool, std::is_same<typename VisitorTraits<Visitor, Visitable>::ReturnType, void>::value>());
}

Wiederum gibt es einen Overload fuer void, fuer den Fall, dass der Visitor nichts zurueckgibt, sowie etwas TMP, um zu entscheiden, welcher Overload aufgerufen werden soll. applyVisitor verwendet VisitorTraits, um sich den Rueckggabetypen des Visitors zu holen.

Allerdings ist genau VisitorTraits hier das Problem:

template <typename Visitor, typename Hierarchy>
struct VisitorTraits
{
	typedef ??? ReturnType;
};

Gegeben sei ein User-definierter typ Visitor und eine Hierarchie-Basisklasse, wie kommt VisitorTraits an den korrekten Rueckgabetyp?

Ich erklaere das Problem am besten anhand eines Beispiels. In meinem Compiler gibt es folgenden Visitor, der eine formatierte Version des Syntaxbaumes ausgibt:

struct FormatVisitor
	: Visitor<void, Expr, ExprConst, ExprVar, ExprCall, ExprBinOp>
	, Visitor<void, Stmt, StmtComp, StmtIf, StmtWhile, StmtRet, StmtDef, StmtExpr>
	, Visitor<void, Decl, DefVar, DefFnParam, DefFnInt, DeclFnExt>
{
	...
};

Wie man sieht, leitet FormatVisitor von Visitor fuer alle 3 Hierarchien ab und implementiert visit() fuer alle moeglichen Klassen des Syntaxbaumes. Damit ist das Typedef ReturnType aus Visitor innerhalb von FormatVisitor mehrdeutig. Ich kenne zwar innerhalb von applyVisitor bzw. applyVisitorImpl die Hierarchie der Visitor Basisklasse, allerdings nicht die Instanzierung von Visitor selbst.

Gibt es irgendeine Moeglichkeit, wie VisitorTraits dennoch an den ReturnType herankommen koennte?

Ich hoffe, mein Post war verstaendlich, das Ganze ist nicht so einfach zu erklaeren. Sollten irgendwo Unklarheiten bestehen, bitte nachfragen.

Vielen Dank schonmal im Voraus,
Der Kellerautomat

Also im VisitorGen<T, Hierarchy, Visited...> template hast Du sowohl den Rückgabetyp als auch den Hierarchie-Typ stecken. Das scheint doch ein guter Ansatzpunkt zu sein.

template< typename Hierarchy, typename Ret, typename... Visited >
Ret deduce_ret_type( VisitorGen<Ret, Hierarchy, Visitied...>* );

template< typename Visitor, typename Hierarchy >
using return_type = decltype(deduce_ret_type<Hierarchy>((Visitor*)0));

Oh, das steht ja genau so auch schon im Visitor in der Reihenfolge, dann kannst Du dort statt VisitorGen auch besser Visitor verwenden. Hatte mir den Text nicht so genau angeschaut, sorry

Kellerautomat

Seltsam, ich dachte, ich haette schon alles in die Richtung durchprobiert. Scheint aber zu funktionieren. Vielen Dank!

Gibst sonst vielleicht noch Vorschlaege, wie ich den Code verbessern koennte? Besonders schoen ist das ja nicht alles.

Oder vielleicht besser:

template< typename Hierarchy, typename Ret, typename... Visited >
Visitor< Ret, Hierarchy, Visited... > deduce_hierarchy_visitor( Visitor<Ret,Hierarchy,Visited...>* );

template< typename Visitor, typename Hierarchy >
using hierarchy_visitor = decltype(deduce_hierarchy_visitor<Hierarchy>((Visitor*)nullptr));

Dann hast Du gleich den kompletten Typ des Hierarchie-spezifischen Visitors...

std::is_same hat einen type-member, der integral_constant<bool> ist... also std::true_type oder std::false type. Die kannst Du auch gleich als Tag-Argument-Typen verwenden, statt dem langen integral_constant.

Und vor dem Rest kapituliere ich... wenn das void* da sein muss und das gecaste sicher und gut versteckt ist, soll mich das auch nicht stören.
Habe immer interessiert über das Visitor-Pattern gelesen, es aber irgendwie nie in's Herz geschlossen. Mag vielleicht auch daran liegen, dass ich selten mit statischen Typ-Mengen zu tun hatte. Ansonsten natürlich sehr viel Text und es ist spät