Présentation
L'article décrit l'implémentation paresseuse de la traversée d'arbre en C ++ à l'aide de coroutines et de plages à l'aide de l'exemple d'amélioration de l'interface pour travailler avec les enfants de la classe QObject partir du framework Qt. La création d'une vue personnalisée pour travailler avec des éléments enfants est considérée en détail et des implémentations paresseuses et classiques sont données. À la fin de l'article, il y a un lien vers le référentiel avec le code source complet.
À propos de l'auteur
Je travaille en tant que développeur senior au bureau norvégien de The Qt Company. J'ai développé des widgets et des éléments QtQuick, récemment Qt Core. J'utilise C ++ et je m'intéresse un peu à la programmation fonctionnelle. Parfois, je fais des rapports et j'écris des articles.
Qu'est-ce que Qt
Qt est un framework multiplateforme pour créer des interfaces utilisateur graphiques (GUI). En plus des modules pour créer une interface graphique, Qt contient de nombreux modules pour développer des logiciels d'application. Le cadre est principalement conçu dans le langage de programmation C ++, certains composants utilisent QML et JavaScript .
Classe QObject
QObject est la classe autour de laquelle le modèle d'objet Qt est construit. Les classes héritées de QObject peuvent être utilisées dans le modèle de signal de slot et la boucle d'événement. De plus, QObject vous permet d'accéder aux informations sur les classes de méta-objets et d'organiser les objets en arborescences.
Structure arborescente de QObject
L'utilisation d'une structure arborescente signifie que chaque objet QObject peut avoir un parent et zéro ou plusieurs enfants. L'objet parent contrôle la durée de vie des objets enfants. Dans l'exemple suivant, deux enfants seront supprimés automatiquement:
auto parent = std::make_unique<QObject>(); auto onDestroyed = [](auto obj){ qDebug("Object %p destroyed.", obj); }; QObject::connect(new QObject(parent.get()), &QObject::destroyed, onDestroyed); QObject::connect(new QObject(parent.get()), &QObject::destroyed, onDestroyed);
Malheureusement, jusqu'à présent, la plupart de l'API Qt ne fonctionne qu'avec des pointeurs bruts. Nous y travaillons, et peut-être que bientôt la situation changera pour le mieux au moins partiellement.
L'interface de classe QObject vous permet d'obtenir une liste de tous les objets enfants et d'effectuer une recherche selon certains critères. Prenons l'exemple de l'obtention d'une liste de tous les objets enfants:
auto parent = std::make_unique<QObject>();
La méthode QObject::children renvoie une liste de tous les enfants de l'objet donné. Cependant, une recherche est souvent requise parmi l'ensemble du sous-arbre des objets selon certains critères:
auto children = parent->findChildren<QObject>(QRegularExpression("0$")); qDebug() << children.count();
L'exemple ci-dessus montre comment obtenir une liste de tous les éléments enfants du type QObject dont le nom se termine par 0. Contrairement à la méthode children , la méthode findChildren parcourt récursivement l'arborescence, c'est-à-dire qu'elle recherche dans toute la hiérarchie des objets. Ce comportement peut être modifié en passant l' Qt::FindDirectChildrenOnly .
Inconvénients de l'interface pour travailler avec des éléments enfants
À première vue, il peut sembler que l'interface de travail avec les enfants est bien pensée et flexible. Cependant, il n'est pas sans défauts. Examinons certains d'entre eux:
- Interface redondante
Il existe deux méthodes findChildren différentes (il y en avait trois il n'y a pas si longtemps): la méthode findChild pour rechercher un élément et la méthode children. Tous se chevauchent partiellement. - L'interface est difficile à changer
Qt garantit la compatibilité binaire et la compatibilité au niveau du code source dans une seule version majeure. Par conséquent, vous ne pouvez pas simplement modifier la signature d'une méthode ou ajouter de nouvelles méthodes. - L'interface est difficile à étendre
En plus de la violation de compatibilité, il est impossible, par exemple, d'obtenir une liste d'éléments enfants selon un critère spécifié. Pour ajouter cette fonctionnalité, vous devez attendre la prochaine version ou créer une autre méthode. - Plus de copier tous les éléments
Souvent, il vous suffit de parcourir la liste de tous les éléments enfants filtrés par un critère donné. Pour ce faire, il n'est pas nécessaire de renvoyer un conteneur de pointeurs vers tous ces éléments. - Possible violation de SRP
C'est une question plutôt controversée, cependant, la nécessité de changer l'interface de classe pour changer, disons, une méthode pour traverser les enfants semble étrange.
Utilisation de range-v3 pour corriger certains défauts
range-v3 est une bibliothèque qui fournit des composants pour travailler avec des plages d'éléments. En fait, il s'agit d'une couche d'abstraction supplémentaire par rapport aux itérateurs classiques, qui vous permet de composer des opérations et de profiter de calculs paresseux.
Une bibliothèque tierce est utilisée car au moment de la rédaction, aucun compilateur connu de l'auteur ne prend en charge cette fonctionnalité. Peut-être que la situation va bientôt changer.
Pour QObject utilisation de cette approche nous permettra de séparer les opérations de traversée de l'arbre des éléments enfants de la classe et de créer une interface flexible pour rechercher des objets selon un critère donné, qui peut être facilement modifié.
Exemple Ranges-v3
Pour commencer, considérez un exemple simple d'utilisation de la bibliothèque. Avant de passer à l'exemple, nous introduisons une notation raccourcie pour les espaces de noms:
namespace r = ranges; namespace v = r::views; namespace a = r::actions;
Considérons maintenant un exemple de programme qui imprime des cubes de tous les nombres impairs dans l'intervalle [1, 10) dans l'ordre inverse:
auto is_odd = [](int n) { return n % 2 != 0; }; auto pow3 = [](int n) { return std::pow(n, 3); };
Il convient de noter que tous les calculs se produisent paresseusement, c'est-à-dire les ensembles de données temporaires ne sont ni créés ni copiés. Le programme ci-dessus est équivalent à cela, à l'exception du formatage de la sortie:
Comme vous pouvez le voir dans l'exemple ci-dessus, la bibliothèque vous permet de composer gracieusement diverses opérations. Vous trouverez plus d'exemples d'utilisation dans les répertoires de tests et d' examples du référentiel range-v3 .
Classe pour représenter une séquence d'enfants
La bibliothèque range-v3 fournit des classes auxiliaires pour créer diverses classes d'encapsuleurs personnalisées; parmi eux se trouvent des classes de la catégorie view . Ces classes sont conçues pour représenter une séquence d'éléments d'une certaine manière sans transformer et copier la séquence elle-même. Dans l'exemple précédent, la classe de filter été utilisée pour ne considérer que les éléments de la séquence qui correspondent aux critères spécifiés.
Pour créer une telle classe pour travailler avec des éléments enfants QObject, elle doit être héritée des ranges::view_facade classes auxiliaires ranges::view_facade :
namespace qt::detail { template <class T = QObject> class children_view : public r::view_facade<children_view<T>> {
Il convient de noter que la classe définit automatiquement la méthode end_cursor , qui renvoie le signe de la fin de la séquence. Si nécessaire, cette méthode peut être remplacée.
Ensuite, nous définissons la classe de curseur elle-même. Cela peut être fait à la fois dans la classe children_view et au-delà:
struct cursor {
Le curseur défini ci-dessus est en un seul passage. Cela signifie que la séquence ne peut se déplacer que dans une direction et une seule fois. Pour cette implémentation, cela n'est pas nécessaire, car nous stockons une séquence de tous les objets enfants et pouvons les parcourir dans toutes les directions autant de fois que vous le souhaitez. Pour indiquer que vous pouvez parcourir une séquence plusieurs fois, vous devez implémenter la méthode suivante dans la classe de curseur:
auto equal(const cursor &that) const { return current_index == that.current_index; }
Vous devez maintenant ajouter pour vous assurer que la vue créée peut être incluse dans la composition. Pour ce faire, utilisez les ranges::make_pipeable fonctions auxiliaires ranges::make_pipeable :
namespace qt { constexpr auto children = r::make_pipeable([](auto &&o) { return detail::children_view(o); }); constexpr auto find_children(Qt::FindChildOptions opts = Qt::FindChildrenRecursively) { return r::make_pipeable([opts](auto &&o) { return detail::children_view(o, opts); }); } }
Vous pouvez maintenant écrire ce code:
for (auto &&c : root | qt::children) {
Implémentation de la fonctionnalité de classe QObject existante
Après avoir implémenté la classe de présentation, vous pouvez facilement implémenter toutes les fonctionnalités pour travailler avec des enfants. Pour ce faire, vous devez implémenter trois fonctions:
namespace qt { template <class T> const auto with_type = v::filter([](auto &&o) { using ObjType = std::remove_cv_t<std::remove_pointer_t<T>>; return ObjType::staticMetaObject.cast(o); }) | v::transform([](auto &&o){ return static_cast<T>(o); }); auto by_name(const QString &name) { return v::filter([name](auto &&obj) { return obj->objectName() == name; }); } auto by_re(const QRegularExpression &re) { return v::filter([re](auto &&obj) { return re.match(obj->objectName()).hasMatch(); }); } }
À titre d'exemple d'utilisation, considérons le code suivant:
for (auto &&c : root | qt::children | qt::with_type<Foo*>) {
Conclusions intermédiaires
Comme le montre le code, il est désormais assez simple d'étendre les fonctionnalités sans changer l'interface de classe. De plus, toutes les opérations sont représentées par des fonctions distinctes et peuvent être organisées dans l'ordre souhaité. Ceci, entre autres, améliore la lisibilité du code et évite l'utilisation de fonctions avec plusieurs paramètres dans l'interface de classe. Il convient également de noter le déchargement de l'interface de classe et la réduction du nombre de raisons pour la modifier.
En fait, cette implémentation élimine déjà presque tous les inconvénients répertoriés de l'interface, sauf que nous devons encore copier tous les enfants dans le conteneur. Une façon de résoudre ce problème consiste à utiliser des coroutines.
Implémentation paresseuse de la traversée de l'arborescence d'objets à l'aide de coroutines
Les coroutines (coroutines) vous permettent de suspendre la fonction et de la reprendre plus tard. Vous pouvez considérer cette technologie comme une sorte de machine à états finis.
Au moment de l'écriture, la bibliothèque standard manque de nombreux éléments importants nécessaires pour une utilisation confortable des coroutines. Par conséquent, il est proposé d'utiliser une bibliothèque cppcoro tierce, qui est susceptible d'entrer dans la norme sous une forme ou une autre.
Pour commencer, nous allons écrire des fonctions qui retourneront le prochain enfant sur demande:
namespace qt::detail { cppcoro::recursive_generator<QObject*> takeChildRecursivelyImpl( const QObjectList &children, Qt::FindChildOptions opts) { for (QObject *c : children) { if (opts == Qt::FindChildrenRecursively) { co_yield takeChildRecursivelyImpl(c->children(), opts); } co_yield c; } } cppcoro::recursive_generator<QObject*> takeChildRecursively( QObject *root, Qt::FindChildOptions opts = Qt::FindChildrenRecursively) { if (root) { co_yield takeChildRecursivelyImpl(root->children(), opts); } } }
L'instruction co_yield renvoie la valeur au code appelant et interrompt la coroutine.
Intégrez maintenant ce code dans la classe children_view . Le code suivant affiche uniquement les éléments qui ont changé:
Le curseur doit également être modifié:
template <class T> struct children_view<T>::cursor { cppcoro::recursive_generator<QObject*>::iterator it; decltype(auto) read() const { return *it; } void next() { ++it; } auto equal(ranges::default_sentinel_t) const { return it == cppcoro::recursive_generator<QObject*>::iterator(nullptr); } explicit cursor(cppcoro::recursive_generator<QObject*>::iterator it): it(it) {} cursor() = default; };
Ici, le curseur agit simplement comme un wrapper autour d'un itérateur régulier. Le reste du code peut être utilisé tel quel, sans modifications supplémentaires.
Les dangers des promenades paresseuses dans les arbres
Il convient de noter que la traversée paresseuse de l'arbre des enfants n'est pas toujours sûre. Cela concerne principalement le contournement de hiérarchies complexes d'éléments graphiques, par exemple des widgets. Le fait est que dans le processus de traversée, la hiérarchie peut être reconstruite et certains éléments sont complètement supprimés. Si vous utilisez une solution de contournement paresseuse dans ce cas, vous pouvez obtenir des résultats très intéressants et imprévisibles du programme.
Cela signifie que dans certains cas, il est utile de copier tous les éléments dans un conteneur. Pour ce faire, vous pouvez utiliser la fonction d'assistance suivante:
auto children = ranges::to<std::vector>(root | qt::children);
À strictement parler, dans ce cas, il n'est pas nécessaire d'utiliser des coroutines et vous pouvez utiliser la vue dès la première itération.
Sera-ce en Qt
Peut-être, mais pas dans la prochaine version. Il y a plusieurs raisons à cela:
- La prochaine version majeure, Qt 6, exigera et supportera officiellement C ++ 17, mais pas plus.
- Il n'y a aucun moyen de l'implémenter sans bibliothèques tierces.
- Il sera relativement difficile d'adapter la base de code existante.
Très probablement, ils reviendront sur ce problème dans le cadre de la version Qt 7.
Conclusion
L'implémentation proposée de la traversée de l'arbre des éléments enfants facilite l'ajout de nouvelles fonctionnalités. En raison de la séparation des opérations, l'écriture d'un code plus propre et la suppression d'éléments inutiles de l'interface de classe sont obtenues.
Il convient de noter que les deux bibliothèques utilisées (range-v3 et cpp-coro) sont fournies sous forme de fichiers d'en-tête, ce qui simplifie le processus de génération. À l'avenir, il sera possible de se passer de bibliothèques tierces.
Cependant, l'approche décrite présente certains inconvénients. Parmi eux, on peut noter la syntaxe inhabituelle pour de nombreux développeurs, la relative complexité de l'implémentation et la paresse, qui peuvent être dangereuses dans certains cas.
En option
Code source
Remerciements particuliers à Misha Svetkin ( Trilla ) pour sa contribution à la mise en œuvre et à la discussion du projet.