Type erasures: réconcilier polymorphisme et programmation générique

Hide polymorphic implementation inside objects that can be copied, assigned, compared for equality, stored in STL containers and used with STL algorithms.

— Sean Parent, Beyound Objects

A class is correct if it works correctly with all algorithms which make sense for it.

— Alexander A. Stepanov, Science of C++ Programming

Dans un précédent texte, la technique des type erasures a été présentée. Aussi, bien qu'il ait été possible, même dans sa forme la plus simple, de trouver des usages intéressants à la technique, sa véritable utilité se révèle lorsque l'on considère un vieux problème affectant le C++, soit la tension existant entre le polymorphisme propre à la programmation orientée objet et la programmation générique.

Contrairement aux langages, comme Java et Python, dans lesquels les objets sont par définition des références, le C++ est explicitement confronté à un problème connu sous le nom d'object slicing.

Comme bien souvent en programmation, l'indirection est la solution retenue afin de mitiger ce problème. Dans ce cas particulier, celle-ci prend la forme de pointeurs.

Malheureusement, cette solution impose une sémantique de référence explicite. Or, cette dernière présente des faiblesses autant au plan de la gestion de la mémoire qu'au plan de l'interaction avec les algorithmes génériques de la STL.

Pour illustrer la situation, considérons l'exemple suivant dans lequel nous désirons stocker et manipuler une séquence d'objets polymorphes à l'aide d'un algorithme générique de la STL.

int main() {
    std::vector<Base> v;
    v.push_back(Derived(1)); // Compile error !
    v.push_back(Derived(2));
    v.push_back(Derived(3));
    std::find(v.begin(), v.end(), Derived(2))->doit();
    return 0;
}

S'il est désirable d'écrire le code ci-dessus, le problème de l'object slicing nous en empêche. Une erreur de compilation est effectivement générée. Dès lors, on recourt à une sémantique de référence pour traiter de manière uniforme la séquence d'objets polymorphes. Le code est donc réécrit de la manière suivante[1].

int main() {
    std::vector<Base*> v;
    v.push_back(new Derived(1));
    v.push_back(new Derived(2));
    v.push_back(new Derived(3));
    (*std::find(v.begin(), v.end(),
                new Derived(2)))->doit(); // Runtime error !
    return 0;
}

Or, dans ce cas particulier, l'algorithme de la STL ne pourra trouver l'objet recherché dans le vecteur puisque l'on compare des pointeurs, ce qui équivaut à comparer des identités, alors que l'on désire comparer des objets, c'est-à-dire des valeurs.

C'est justement afin de passer outre cette dichotomie apparente que Sean Parent, de chez Adobe, a introduit en 2008 une méthode basée sur la technique des type erasures permettant réconcilier le polymorphisme et la sémantique de valeur requise par la programmation générique: le runtime concept idiom. Avec cette méthode, le polymorphisme est relégué au rang de détail d'implantation. Les exemples précédents peuvent alors être réécrits de la manière suivante.

int main() {
    std::vector<Base> v;
    v.push_back(Base(Derived(1)));
    v.push_back(Base(Derived(2)));
    v.push_back(Base(Derived(3)));
    std::find(v.begin(), v.end(), Derived(2))->doit();
    return 0;
}

Sous forme graphique, cela pourrait ressembler à la figure suivante.

Implantation

Une fois le principe des type erasures maîtrisé, implanter le runtime concept idiom est une tâche relativement simple. Essentiellement, il s'agit de rendre les classes Concept, Model et TypeErasure paramétrables par l'utilisateur. Les templates constituent bien sûr le véhicule privilégié pour y arriver.

Ainsi, la classe Concept se trouve découpée en deux parties. Le UserConcept est une interface purement virtuelle dans laquelle l'utilisateur définit son concept alors que le DefaultConcept contient les méthodes formant l'interface de base de tous les concepts. Le DefaultConcept intègre l'interface définie par l'utilisateur en héritant de cette dernière.

template<typename UserConcept>
struct DefaultConcept: UserConcept {
    typedef DefaultConcept ConceptType;
    virtual bool equals(const DefaultConcept&) const = 0;
    virtual DefaultConcept* copy() const = 0;
    virtual const std::type_info& type() const = 0;
    virtual ~DefaultConcept() {}
};

Tout comme la classe Concept, la classe Model est découpée en deux morceaux. Le UserModel correspond à l'implantation de l'interface définie dans le UserConcept alors que le DefaultModel contient l'implantation des méthodes définies dans la classe DefaultConcept. Le DefaultModel intègre les méthodes du UserModel en héritant de ce dernier.

template<typename UserModel>
struct DefaultModel: UserModel {
    typedef typename UserModel::ValueType       ValueType;
    typedef typename UserModel::ConceptType 	ConceptType;

    DefaultModel(const ValueType& value) :
        UserModel(value) /* Call UserModel's constructor. */ {
    }
    bool equals(const ConceptType& other) const {
        return (other.type() == typeid(ValueType))
                && (static_cast<const DefaultModel&>(other).value == this->value);
    }
    DefaultModel* copy() const {
        return new DefaultModel(this->value);
    }
    const std::type_info& type() const {
        return typeid(ValueType);
    }
};

La classe TypeErasure, réimplantée comme un template prenant en argument un UserConcept et un UserModel, se nomme maintenant RegularObject. L'accès au concept est rendu possible à travers des surcharges de l'opérateur de pointeur.

template<typename UserConcept,
         template<class > class UserModel>
class RegularObject {
private:
    typedef DefaultConcept<UserConcept>   Concept;
    Concept* object;

public:
    template<typename T> explicit RegularObject(const T& x) :
        object(new DefaultModel<UserModel<T> >(x)) {
    }
    RegularObject(const RegularObject& src) :
        object(src.object->copy()) {
    }
    ~RegularObject() {
        delete object;
    }
    RegularObject& operator=(RegularObject rhs) {
        swap(rhs);
        return *this;
    }
    void swap(RegularObject& x) {
        using std::swap;
        swap(object, x.object);
    }
    const Concept* operator->() const {
        return object;
    }
    Concept* operator->() {
        return object;
    }
    friend inline bool operator==(const RegularObject& x,
                                  const RegularObject& y) {
        return x.object->equals(*y.object);
    }
};

Pour comprendre comment cette machinerie peut être utilisée en pratique, le plus simple est de considérer une application manipulant des formes de manière polymorphe.

class Shape {
private:
    // Drawable interface definition. This is our concept.
    struct DrawableConcept {
        virtual void draw(const Point&) const = 0;
    };

    // Drawable interface implementation. This is our model.
    template<typename T>
    struct DrawableModel: DefaultConcept<DrawableConcept> {
        typedef T ValueType;

        DrawableModel(const ValueType& x) :
            value(x) {
        }
        void draw(const Point& where) const {
            value.draw(where);
        }

        ValueType value;
    };

    Point origine;
    RegularObject<DrawableConcept, DrawableModel> object;

public:
    template<typename Drawable>
    Shape(const Point& origine, const Drawable& drawable) :
        origine(origine), object(drawable) {
    }
    void draw() const {
        object->draw(origine);
    }
    Point where() const {
        return origine;
    }
    void move(const Point& to) {
        origine = to;
    }
    inline friend bool operator==(const Shape& x,
                                  const Shape& y) {
        return (x.origine == y.origine)
            && (x.object == y.object);
    }
};

Les deux classes DrawableConcept et DrawableModel sont assemblées de telle sorte que la hiérarchie suivante est formée lors de l'instanciation des templates.

Définir des formes additionnelles est alors très simple. Il suffit de s'assurer que l'interface de ces dernières est bien compatible avec le concept défini dans la classe Shape.

struct Text {
    Text(const std::string& text) :
        text(text) {
    }
    void draw(const Point& p) const {
        std::cout << "Shape(Point(" << p.first << ", "
                  << p.second << "), Text(\"" << text
                  << "\")); " << std::endl;
    }
    friend inline bool operator==(const Text& x, const Text& y) {
        return x.text == y.text;
    }

    std::string text;
};

Avec cette machinerie en place, il devient effectivement possible d'obtenir un comportement polymorphe tout en conservant une sémantique de valeur. On retrouve donc le meilleur des deux mondes.

int main() {
    vector<Shape> canvas1;
    canvas1.push_back(Shape(Point(1, 2), Circle(3)));
    canvas1.push_back(Shape(Point(3, 4), Circle(6)));
    canvas1.push_back(Shape(Point(5, 6), Rectangle(9, 10)));
    canvas1.push_back(Shape(Point(7, 8), Text(string("Test!"))));

    vector<Shape> canvas2(canvas1);

    reverse(canvas1.begin(), canvas1.end());

    find(canvas1.begin(), canvas1.end(),
         Shape(Point(3, 4), Circle(6)))->move(Point(10, 20));

    for_each(canvas1.begin(), canvas1.end(), mem_fun_ref(&Shape::draw));
    for_each(canvas2.begin(), canvas2.end(), mem_fun_ref(&Shape::draw));

    return 0;
}

Le code source complet de cet exemple peut être consulté en ligne.

Références

Le code présenté dans ce texte est une version légèrement modifiée de l'exemple utilisé par Sean Parent dans une présentation datée de 2008 intitulée Beyond Objects. La présentation est disponible sur le wiki du Software Technology Lab d'Adobe. Tout le crédit lui est évidemment attribuable et les erreurs sont miennes.

Sean Parent a également développé la technique dans un article coécrit avec Mat Marcus et Peter Pirkelbauer intitulé Runtime Concepts for the C++ Standard Template Library.

  1. Faisons abstraction de la fuite de mémoire…