Implementierung eines statischen Visitors

[Nexus]

Hallo zusammen,

Ich hab wieder mal ein Problem mit purem C++. Genauer gesagt handelt es sich um einen Versuch, statische und dynamische Polymorphie für das Visitor-Pattern mittels Type Erasure zu kombinieren. Im Prinzip versuche ich sowas:

// Basisklasse der zu besuchenden Klassen
struct Base { virtual ~Base() = 0; };

// Zwischenklasse, um Base-Derivate nicht zu verändern
struct BaseAcceptor
{
    template <class V>
    virtual void Accept(V visitor) = 0;

    Base* base;
};

template <class D>
struct Acceptor : BaseAcceptor
{
    template <class V>
    virtual void Accept(V visitor)
    {
        // Statischen Typ für Überladung bekannt machen
        visitor.Visit( static_cast<D&>(base) );
    }
};

Das soll so angewandt werden:

struct User
{
    template <class V>
    void VisitEach(V visitor)
    {
        BOOST_FOREACH(BaseAcceptor* fw, acceptors)
            fw->Accept(visitor); 
    }

    std::vector<BaseAcceptor*> acceptors;
};

Ist nun etwas schwierig, weil virtuelle Funktionen keine Templates sein können. Der übliche Workaround, V zum Templateparameter der Klasse zu machen, funktioniert nicht, weil V zum Instanziierungszeitpunkt der Klassen Acceptor<D> (also beim Einfüllen in den Container acceptors ) noch nicht bekannt ist. Alexandrescu implementiert in seinem Buch einen dynamischen Visitor, da muss die Visitor-Klasse für jeden besuchten Typen von einer Klasse erben. Ausserdem muss jede besuchte Klasse ein Makro definieren, und das Ganze ist über dynamic_cast implementiert.

Diese Nachteile möchte ich soweit möglich vermeiden, vor allem soll der Benutzer möglichst wenig Gerüst-Code schreiben, nur damit überhaupt was läuft. Dafür kann ich Zugeständnisse machen, was die Abhängigkeiten der einzelnen Typen betrifft (mein Visitor kennt alle besuchten Klassen vollständig). Mein Vorbild für User::VisitEach() ist boost::variant::apply_visitor() , die Anwendung ist dort sehr schön. Jedoch ist boost::variant im Vorteil, weil 1. nur eine vorgegebene Menge an Typen vorkommt und 2. alle statischen Typinformationen als Template-Parameter vorliegen. Ich denke, es läuft im Endeffekt auf einen Mittelweg hinaus.

Ich habe boost::variant ein wenig näher angeschaut. Nachdem ich wieder mal zum Schluss kam, dass das Debuggen und Nachvollziehen von Boost-Code der Wahnsinn persönlich ist, bin ich (in Präprozessor-Metaprogrammierung verpackt) auf sowas gestossen:

// Z.B. boost::variant<int, double>
switch (which) // which=Typ-Index (0 für int, 1 für double)
{
    case 0:  DoSomethingVeryAbstract<int>();    break;
    case 1:  DoSomethingVeryAbstract<double>(); break;
}

Boost spielt also seine Vorteile schön aus. Ich hingegen habe die Typinformationen über int bzw. double nicht direkt, sondern nur in der abgeleiteten Klasse Acceptor . Dort wiederum habe ich aber keine Möglichkeit, statische Typinformationen über den Visitor zu erhalten... Mir scheint, mein momentaner Ansatz führt ins Leere. Wahrscheinlich stosse ich gerade an einer prinzipiellen Unmöglichkeit an.

Habt ihr eine Idee? :xmas1:

[cgfdghhdfg]

Was soll das bringen? Wieso nicht einfach ohne die template Sachen?

[Nexus]

Der 08/15-Ansatz mit einer Visitor-Basisklasse à la

class BaseVisitor
{
    public:
        virtual void Visit(Derived1& d) = 0;
        virtual void Visit(Derived2& d) = 0;
        ...
        virtual ~BaseVisitor();
};

ist ungeeignet, weil hier alle besuchbaren Klassen ( Derived1 , Derived2 , ...) bekannt sein müssen. Das geht natürlich nicht, wenn BaseVisitor in der Bibliothek ist, aber der Benutzer auch andere Klassen als die vorgegebenen besuchen will.

[cgfdghhdfg]

Was hast du eigentlich vor?

[Nexus]

Eine Klasse speichert einen Container mit polymorphen Basisklassenzeigern. In Wirklichkeit stecken dahinter verschiedene abgeleitete Objekte.

Nun will ich in dieser Klasse eine Schnittstelle anbieten, um für alle Elemente etwas zu tun. Naheliegend scheint ein Iterator-Interface, doch dann muss der Benutzer jeweils downcasten und Typunterscheidungen durchführen. Daher scheint es mir eleganter, einen Visitor zu nehmen, der den dynamischen Typen des jeweiligen Elements automatisch erkennt und eine spezifische Aktion durchführt.

[cgfdghhdfg]

Warum muss man casten? Mach halt eine Funktion "doWhatEver" in die Basisklasse und ruf die dann auf. Ganz einfache Polymorphie.

[XSpille]

Hallo Nexus,

Nexus schrieb:

Der übliche Workaround, V zum Templateparameter der Klasse zu machen, funktioniert nicht, weil V zum Instanziierungszeitpunkt der Klassen Acceptor<D> (also beim Einfüllen in den Container acceptors) noch nicht bekannt ist.

Wie willst du sie dann ansprechen?

Verstehe ich richtig, dass der Typ beim Einfügen festgelegt wird?

Du kannst evtl. den Parameter in eine Template-Klasse mit virtuellen Funktionen
wrappen um so eine gemeinsame Schnittstelle zu adaptieren.
EDIT: Also ich meinte eine Basisklasse mit virtuellem Zuweisungsoperator und einem
virtuellen visit (und void-Zeiger). Die Template-Klasse castet dann den void-Zeiger.

Gruß,
XSpille

[Nexus]

cgfdghhdfg schrieb:

Warum muss man casten? Mach halt eine Funktion "doWhatEver" in die Basisklasse und ruf die dann auf. Ganz einfache Polymorphie.

Nein, die Klassenhierarchie steht fest und kann nicht verändert werden. Was man höchstens machen könnte, wäre ein Makro für eine automatische Implementierung einer Accept() -Funktion, wie bei Alexandrescu. Aber mir wäre lieber ohne.

XSpille schrieb:

Wie willst du sie dann ansprechen?
Verstehe ich richtig, dass der Typ beim Einfügen festgelegt wird?

Ja, der dynamische Typ D des Objekts ist beim Einfügen bekannt.

XSpille schrieb:

Du kannst evtl. den Parameter in eine Template-Klasse mit virtuellen Funktionen
wrappen um so eine gemeinsame Schnittstelle zu adaptieren.

Das Problem ist, ich brauche für den Besuch zwei Typinformationen. Zum einen muss V bekannt sein (statischer Typ des Visitors). Damit der Visitor weiss, was für ein Objekt er besucht, muss auch D bekannt sein (Typ des zu besuchenden abgeleiteten Objekts). Einer dieser Typen mit Type Erasure wegzuabstrahieren ist nicht schwierig, aber beide gleichzeitig geht nicht, weil sie an unterschiedlichen Orten bekannt sind ( D beim Einfüllen in den Container und V beim Aufruf von VisitEach() ).

Oder hast du was anderes gemeint und würdest das an einem kleinen Beispiel verdeutlichen?

[Nexus]

Nexus schrieb:

Nein, die Klassenhierarchie steht fest und kann nicht verändert werden.

Da fällt mir was ein... Wenn man virtuelle Funktionen ausserhalb der Klasse benötigt, ist Dynamic-Dispatch eine Möglichkeit. Allerdings müsste ich dann die einzelnen Visit() -Funktionen irgendwo registrieren.

Aber das ist wahrscheinlich das kleinste Übel...

[XSpille]

hmm... Ich überleg noch

Mal eine andere Frage:
Weswegen übergibst du den 'genauen' Typ (oder Basisklasse) von

Base* base;

nicht per Template-Parameter an?

Ein Visitor soll ja eh einen bestimmten base-Typ (oder dessen Basisklasse)
behandeln können, oder?

Welche Informationen bestehen über Base*?
Ansonsten wäre es ja als würde man einen void-Zeiger übergeben (abgesehen von
dem virtuellen Destruktor)

[Nexus]

XSpille schrieb:

Mal eine andere Frage:
Weswegen übergibst du den 'genauen' Typ (oder Basisklasse) von

Base* base;

nicht per Template-Parameter an?

Das tue ich in Wirklichkeit, ist hier der Einfachheit weggelassen. Zum Beispiel sind in meinem Code auch durchgehend ungekapselte struct s zu sehen.

XSpille schrieb:

Welche Informationen bestehen über Base*?
Ansonsten wäre es ja als würde man einen void-Zeiger übergeben (abgesehen von
dem virtuellen Destruktor)

Naja, Base ist halt die polymorphe Basisklasse, die als Abstraktion der konkreten abgeleiteten Klassen dient. Eventuell muss sie später auch RTTI unterstützen.

[XSpille]

Eigentlich scheint mir die 'Lösung' zu einfach, aber ich poste
trotzdem mal, was ich mir gedacht habe:

template<class T>
struct IVisitorWrapper {

	virtual void Visit(T& t);
};

template<class TVisitor, class T>
struct VisitorWrapper {

	VisitorWrapper(TVisitor* visitor) : visitor(visitor) {
	}

	virtual void Visit(T& t){
		this->visitor->Visit(t);
	}

	TVisitor* visitor;
};

// Basisklasse der zu besuchenden Klassen 
struct Base { virtual ~Base() = 0; }; 

// Zwischenklasse, um Base-Derivate nicht zu verändern 
template <class TBase>
struct BaseAcceptor 
{ 
    virtual void Accept(IVisitorWrapper<TBase>& visitor) = 0; 

    TBase* base;
}; 

template <class TBase>
struct Acceptor : BaseAcceptor<TBase>
{ 
    virtual void Accept(IVisitorWrapper<TBase>& visitor) 
    { 
        // Statischen Typ für Überladung bekannt machen 
        visitor.Visit(base); 
    } 
};

[headmyshoulder]

Ich bin mir nicht ganz sicher was Du genau meinst, aber wenn es genau das ist

Nexus schrieb:

Eine Klasse speichert einen Container mit polymorphen Basisklassenzeigern. In Wirklichkeit stecken dahinter verschiedene abgeleitete Objekte.

Nun will ich in dieser Klasse eine Schnittstelle anbieten, um für alle Elemente etwas zu tun. Naheliegend scheint ein Iterator-Interface, doch dann muss der Benutzer jeweils downcasten und Typunterscheidungen durchführen. Daher scheint es mir eleganter, einen Visitor zu nehmen, der den dynamischen Typen des jeweiligen Elements automatisch erkennt und eine spezifische Aktion durchführt.

könntest Du vielleicht boost::fusion::map benutzen, vielleicht auch in Kombination mit boost::function.

Vielleicht so

struct base { ... };
struct derived1 : base { ... };
struct derived2 : base { ... }:
...
void visit_derived1( derived1 *d ) { ... }
void visit_derived2( derived2 *d ) { ... }

typedef fusion::map<
    fusion::pair< derived1 , boost::function1< void , derived1* > ,
    fusion::pair< derived2 , boost::function2< void , derived2* > 
> default_switch_type( fusion::make_pair< derived1 >( visit_derived1 ) , fusion::make_pair< derived2 >( visit_derived2 ) );

template< class SwitchType = default_switch_type >
struct visitor
{
    SwitchType m_switch;
    visitor( const SwitchType &switch_ = SwitchType() )
    : m_switch( switch_ )

    template< class ToVisit >
    void operator()( ToVisit *t )
    {
        visit( t , fusion::has_key< ToVisit )( m_switch ) );
    }

    // visit this function if Key exist
    template< class ToVisit >
    void visit( ToVisit *t , boost::true_type )
    {
        fusion::at_key< ToVisit >( m_switch )( t );
    }

    template< class ToVisit >
    void visit( ToVisit *t , boost::false_type )
    {
         // default ...
    }
};

Das ganze ist dann "konfigurierbar", der User kann eine eigene Sequenz angeben, welche dann besucht wird.

Die Frage ist jetzt wie der Container aussieht. Wenn er statisch ist ( boost::fusion, std::tr1::tuple ) kannst Du einfach fusion::for_each benutzen und es wird richtig gecastet.

Falls der Container dynamisch ist, kannst Du in visitor::operator() noch einen Meta-Loop über all (statischen) Keys in SwitchType einbauen. In jedem dieser Aufrufe machst Du einen check ob Du casten kannst und wenn ja wird die Funktion aufgerufen:

struct call_visitor
{
	const base* m_b;
	call_visitor( const base *b ) : m_b( b ) { };

	template< class Key , class Value >
	void operator()( fusion::pair< Key , Value > p ) const
	{
		typedef typename boost::is_base_of< base , Key >::type base_dispatch_type;
		cout << "operator " << typeid( Key ).name() << " " << base_dispatch_type::value << endl;
		dispatch( p , base_dispatch_type() );
	}

	template< class Key , class Value >
	void dispatch( fusion::pair< Key , Value > p , boost::true_type ) const
	{
		Value f = p.second;
		f( dynamic_cast< const Key* >( m_b ) );
	}

	template< class Key , class Value >
	void dispatch( fusion::pair< Key , Value > p , boost::false_type ) const
	{
		cout << "Not good types!" << endl;
	}
};

void visit( base* b )
{
	fusion::for_each( default_switch , call_visitor( b ) );
}

[Nexus]

XSpille schrieb:

Eigentlich scheint mir die 'Lösung' zu einfach, aber ich poste
trotzdem mal, was ich mir gedacht habe:

Naja, das Problem ist jetzt, dass hier

visitor.Visit(base);

base nur ein Basisklassenzeiger ist, wodurch man keine Funktionsüberladung in der Visitor-Klasse nutzen kann.

headmyshoulder schrieb:

Ich bin mir nicht ganz sicher was Du genau meinst, aber wenn es genau das ist könntest Du vielleicht boost::fusion::map benutzen, vielleicht auch in Kombination mit boost::function.

Vielen Dank für den Hinweis und den Code! Leider kann ich in der Bibliothek kein Boost benutzen, aber dein Vorschlag hat mich dazu gebracht, die Boost.Fusion-Bibliothek mal anzuschauen. Scheint wirklich noch ein paar interessante Konzepte zu haben...

Doch gleich eine Frage zu deinem Code: Müssen die einzelnen abgeleiteten Typen in der Sequenz nicht bekannt sein? Boost.Fusion basiert ja stark auf auf statischer Polymorphie (vom dynamischen Teil der Fusion habe ich bisher noch nicht viel entdeckt). Und ehlich gesagt schreckt mich die boost-typische Templateschlacht ein bisschen ab...

[headmyshoulder]

Nexus schrieb:

Vielen Dank für den Hinweis und den Code! Leider kann ich in der Bibliothek kein Boost benutzen, aber dein Vorschlag hat mich dazu gebracht, die Boost.Fusion-Bibliothek mal anzuschauen. Scheint wirklich noch ein paar interessante Konzepte zu haben...

Ok, dass per Hand zu entwickeln ist recht aufwendig. Sollte aber möglich sein, falls es nur um diese Funktionalität geht. Man könnte auch std::tr1::tuple dazu aufbohren und eine dazugehöriges for_each implementieren.

Nexus schrieb:

Doch gleich eine Frage zu deinem Code: Müssen die einzelnen abgeleiteten Typen in der Sequenz nicht bekannt sein? Boost.Fusion basiert ja stark auf auf statischer Polymorphie (vom dynamischen Teil der Fusion habe ich bisher noch nicht viel entdeckt). Und ehlich gesagt schreckt mich die boost-typische Templateschlacht ein bisschen ab...

Ja, müssen sie. Allerdings bekommt die Klasse Visitor die Sequenz als Template-Parameter mit übergeben. Der User kann also die Sequenz, und damit auch das Verhalten und Weiterleiten, selbst festlegen. Man könnte auch eine Default-Sequenz festlegen.

Ein weitere Möglichkeit wäre es, die Sequenz in einem Member zu verstecken, ähnlich wie Boost.Any. Dann kann die Sequenz auch dynamisch gesetzt und verändert werden.

[Nexus]

headmyshoulder schrieb:

Ja, müssen sie. Allerdings bekommt die Klasse Visitor die Sequenz als Template-Parameter mit übergeben.

Auf Visitor-Seite ist es sogar erwünscht, dass die zu besuchenden Klassen als statische Typinformationen vorliegen. Auf der Seite der Klasse mit Container aus polymorphen Zeigern hingegen haben wir die Typen nicht (oder nur durch Type Erasure abstrahiert). Ich sehe daher eine grundsätzliche Schwierigkeit... Oder ich hab einfach noch nicht ganz verstanden, wie dynamisch Boost.Fusion sein kann.

boost::any wäre hingegen auch nur eine Wegkapselung des dynamischen Typen mittels Type Erasure, dann komm ich wieder nicht an die statischen Typen.

[headmyshoulder]

Nexus schrieb:

headmyshoulder schrieb:

Ja, müssen sie. Allerdings bekommt die Klasse Visitor die Sequenz als Template-Parameter mit übergeben.

Auf Visitor-Seite ist es sogar erwünscht, dass die zu besuchenden Klassen als statische Typinformationen vorliegen. Auf der Seite der Klasse mit Container aus polymorphen Zeigern hingegen haben wir die Typen nicht (oder nur durch Type Erasure abstrahiert). Ich sehe daher eine grundsätzliche Schwierigkeit... Oder ich hab einfach noch nicht ganz verstanden, wie dynamisch Boost.Fusion sein kann.

Wenn dynamisch für Dich bedeutet zur Laufzeit mit Code aus beliebigen Dlls/SO geht das natürlich nicht. Wenn dynamisch bedeutet dass der User das Verhalten festlegen kann schon.

In dem Beispiel bildet Fusion.Map einen Typ auf einen Funktor ab.

// Achtung kein C++
derived1 -> visit_derived1
derived2 -> visit_derived2
...

Diese Map kann der User selbst festlegen und verändern, aber nur während des Kompilierens. Wird jetzt der Container von base* durchlaufen und der Visitor aufgerufen wird anhand dieser Abbildung der entsprechende Funktor mit dem gerade zu besuchenden Element aufgerufen. Ich glaub der folgende Code veranschaulicht das Recht gut:

struct call_visitor
{
    const base* m_b;
    call_visitor( const base *b ) : m_b( b ) { };

    template< class Key , class Value >
    void operator()( fusion::pair< Key , Value > p ) const
    {
        const Key* k = dynamic_cast< const Key * >( m_b );
        if( k != 0 )
        {
            Value f = p.second;
            f( k );
        }
    }
};

void visit( base* b )
{
    fusion::for_each( switch , call_visitor( b ) );
}

switch ist hier die Fusion Map aus dem obigen Beispiel.

Würde das Dein Problem lösen?

[Nexus]

Mein Dynamic-Dispatcher ist inzwischen lauffähig, ich muss hauptsächlich noch ein paar Feineinstellungen vornehmen. Wenn ich das richtig sehe, habe ich sogar was Ähnliches wie dein Code nachgebaut, nur halt mehr auf die Laufzeit konzentriert.

// Klasse mit Container von polymorphen Zeigern
struct User
{
	void VisitEach(DynamicDispatcher<Base>& dispatcher)
	{
		for (/* Iterator itr über b */)
			dispatcher.Call(**itr);
	}

	std::vector<Base*> b;
};

// Funktionen für den Besuch
void Visit(Derived1&);
void Visit(Derived2&);

// Anwendung
int main()
{
    DynamicDispatcher<Base> dispatcher;
    dispatcher.Register<Derived1>(&Visit);
    dispatcher.Register<Derived2>(&Visit);

	User u;	// fülle u.b mit Objekten
	u.VisitEach(dispatcher);
}

Ist nun halt kein Funktor mit überladenen operator() -Funktionen mehr, aber das scheint eh nicht zu gehen. Zumindest nicht ohne Template-Gehacke und Ableiten von etlichen Klassen. Oder kann man mit Boost.Fusion das Ganze so hinkriegen, dass ein Visitor des Benutzers so aussieht (von mir aus kann er von einer Basisklasse erben)?

struct Visitor
{
    void operator() (Derived1&);
    void operator() (Derived2&);
    ...
};

Ansonsten bin ich mit meiner Methode recht zufrieden. Man muss die abgeleiteten Klassen nicht verändern und kommt als Benutzer fast ohne Templates aus. Was noch schön wäre, wenn man die Registrierung irgendwie automatisieren könnte, aber sonst kann ich damit leben.

[Nexus]

Ein möglicher Ansatz zur Automatisierung:

// ----------------------------------------------------------------
// Bibliothek (virtuelle Destruktoren weggelassen)
struct BaseVisitor { ... };

template <class D>
struct Visitor
{
    Visitor(); // Registriert Visit() dieser Klasse
    virtual void Visit(D&) = 0; // muss überschrieben werden
};

// ----------------------------------------------------------------
// Anwendung
struct MyVisitor : BaseVisitor, Visitor<Derived1>, Visitor<Derived2>
{
    virtual void Visit(Derived1&);
    virtual void Visit(Derived2&);
};

Der Rest bliebe ungefähr gleich.

Fändet ihr das benutzerfreundlicher? Ich sehe eigentlich nicht viele Vorteile, abgesehen davon, dass man DynamicDispatcher nicht direkt anfassen muss.

• Nur Methoden einer einzelnen Klasse zu verwenden ist auch mit DynamicDispatcher möglich.
• Man dupliziert auch hier Informationen: Abgeleitete Typen kommen als Template-Argumente von Visitor sowie als Funktionsparameter von Visit() vor.
• Der Ansatz hier hat recht viel Overhead, da neben den VTables wahrscheinlich auch ein dynamic_cast pro Visitor nötig ist. Zusätzlich zum Dispatch-Mechanismus, der ja auch nicht ganz gratis ist.
• Man ist grundsätzlich weniger flexibel, weil bereits bestehende Funktionen nicht zum Besuch verwendet werden können. Man muss eine Überladung in MyVisitor schreiben. Hingegen kann DynamicDispatch mit freien Funktionen, Memberfunktionen und Funktoren umgehen.

Aber seid ehrlich, was würdet ihr als Benutzer lieber verwenden?

[headmyshoulder]

Nexus schrieb:

Mein Dynamic-Dispatcher ist inzwischen lauffähig, ich muss hauptsächlich noch ein paar Feineinstellungen vornehmen. Wenn ich das richtig sehe, habe ich sogar was Ähnliches wie dein Code nachgebaut, nur halt mehr auf die Laufzeit konzentriert.

Jepp, ich denke dass das unter der Haube recht ähnlich zu meinem Ansatz ist. Kannst Du den Code von Deinem Dispatcher posten, insbesondere von Call und Register?

Nexus schrieb:

Ist nun halt kein Funktor mit überladenen operator() -Funktionen mehr, aber das scheint eh nicht zu gehen. Zumindest nicht ohne Template-Gehacke und Ableiten von etlichen Klassen. Oder kann man mit Boost.Fusion das Ganze so hinkriegen, dass ein Visitor des Benutzers so aussieht (von mir aus kann er von einer Basisklasse erben)?

Ich glaub prinzipiell kannst Du in fusion::map jeden beliebigen Typ reinpacken. Funktoren hab ich nur gewählt weil die ziemlich allgemein sind.

[headmyshoulder]

Nexus schrieb:

Ein möglicher Ansatz zur Automatisierung:

// ----------------------------------------------------------------
// Bibliothek (virtuelle Destruktoren weggelassen)
struct BaseVisitor { ... };

template <class D>
struct Visitor
{
    Visitor(); // Registriert Visit() dieser Klasse
    virtual void Visit(D&) = 0; // muss überschrieben werden
};

// ----------------------------------------------------------------
// Anwendung
struct MyVisitor : BaseVisitor, Visitor<Derived1>, Visitor<Derived2>
{
    virtual void Visit(Derived1&);
    virtual void Visit(Derived2&);
};

Der Rest bliebe ungefähr gleich.

Fändet ihr das benutzerfreundlicher?

Vielleicht müssen sich ja beiden Methoden gar nicht ausschliessen. Wenn Du das hinbekommst kann der User entscheiden was er lieber benutzt, entweder einen grossen Visitor oder viele kleine. Ich persönlich finde den ersten Ansatz ein bisschen besser. Die Mehrfachvererbung ist mir ein kleines bisschen suspekt.