"Fossies" - the Fresh Open Source Software Archive

Member "dune-typetree-2.8.0/dune/typetree/visitor.hh" (31 Aug 2021, 22121 Bytes) of package /linux/misc/dune/dune-typetree-2.8.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "visitor.hh" see the Fossies "Dox" file reference documentation.

    1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
    2 // vi: set et ts=4 sw=2 sts=2:
    3 
    4 #ifndef DUNE_TYPETREE_VISITOR_HH
    5 #define DUNE_TYPETREE_VISITOR_HH
    6 
    7 #include <dune/typetree/treepath.hh>
    8 #include <dune/typetree/utility.hh>
    9 
   10 namespace Dune {
   11   namespace TypeTree {
   12 
   13     /** \addtogroup Tree Traversal
   14      *  \ingroup TypeTree
   15      *  \{
   16      */
   17 
   18     //! Visitor interface and base class for TypeTree visitors.
   19     /**
   20      * DefaultVisitor defines the interface for visitors that can be applied to a TypeTree
   21      * using applyToTree(). Each method of the visitor is passed a node of the tree (either as
   22      * a mutable or a const reference, depending on the constness of the tree applyToTree() was
   23      * called with). The second argument is of type TreePath and denotes the exact position of the
   24      * node within the TypeTree, encoded as child indices starting at the root node.
   25      *
   26      * In order to create a functioning visitor, an implementation will - in addition to providing the methods
   27      * of this class - also have to contain the following template struct, which is used to determine
   28      * whether to visit a given node:
   29      *
   30      * \code
   31      * template<typename Node, typename Child, typename TreePath>
   32      * struct VisitChild
   33      * {
   34      *   static const bool value = ...; // decide whether to visit Child
   35      * };
   36      * \endcode
   37      *
   38      * For the two most common scenarios - visiting only direct children and visiting the whole tree - there
   39      * are mixin classes VisitDirectChildren and VisitTree and combined base classes TreeVisitor and
   40      * DirectChildrenVisitor. The latter two inherit from both DefaultVisitor and one of the two mixin classes
   41      * and can thus be used as convenient base classes.
   42      *
   43      * \note This class can also be used as a convenient base class if the implemented visitor
   44      *       only needs to act on some of the possible callback sites, avoiding a lot of boilerplate code.
   45      */
   46     struct DefaultVisitor
   47     {
   48 
   49       //! Method for prefix tree traversal.
   50       /**
   51        * This method gets called when first encountering a non-leaf node and
   52        * before visiting any of its children.
   53        *
   54        * \param t        The node to visit.
   55        * \param treePath The position of the node within the TypeTree.
   56        */
   57       template<typename T, typename TreePath>
   58       void pre(T&& t, TreePath treePath) const {}
   59 
   60       //! Method for infix tree traversal.
   61       /**
   62        * This method gets called BETWEEN visits of children of a non-leaf node.
   63        * That definition implies that this method will only be called for nodes
   64        * with at least two children.
   65        *
   66        * \param t        The node to visit.
   67        * \param treePath The position of the node within the TypeTree.
   68        */
   69       template<typename T, typename TreePath>
   70       void in(T&& t, TreePath treePath) const {}
   71 
   72       //! Method for postfix tree traversal.
   73       /**
   74        * This method gets called after all children of a non-leaf node have
   75        * been visited.
   76        *
   77        * \param t        The node to visit.
   78        * \param treePath The position of the node within the TypeTree.
   79        */
   80       template<typename T, typename TreePath>
   81       void post(T&& t, TreePath treePath) const {}
   82 
   83       //! Method for leaf traversal.
   84       /**
   85        * This method gets called when encountering a leaf node within the TypeTree.
   86        *
   87        * \param t        The node to visit.
   88        * \param treePath The position of the node within the TypeTree.
   89        */
   90       template<typename T, typename TreePath>
   91       void leaf(T&& t, TreePath treePath) const {}
   92 
   93       //! Method for parent-child traversal.
   94       /**
   95        * This method gets called before visiting a child node.
   96        *
   97        * \note This method gets called even if the visitor decides not to visit the child in question.
   98        *
   99        * \param t          The parent node.
  100        * \param child      The child node that will (potentially) be visited next.
  101        * \param treePath   The position of the parent node within the TypeTree.
  102        * \param childIndex The index of the child node in relation to the parent node.
  103        */
  104       template<typename T, typename Child, typename TreePath, typename ChildIndex>
  105       void beforeChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex) const {}
  106 
  107       //! Method for child-parent traversal.
  108       /**
  109        * This method gets called after visiting a child node.
  110        *
  111        * \note This method gets called even if the child node was not visited because the visitor
  112        *       chose not to do so.
  113        *
  114        * \param t          The parent node.
  115        * \param child      The child node that was visited last (if the visitor did not reject it).
  116        * \param treePath   The position of the parent node within the TypeTree.
  117        * \param childIndex The index of the child node in relation to the parent node.
  118        */
  119       template<typename T, typename Child, typename TreePath, typename ChildIndex>
  120       void afterChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex) const {}
  121 
  122     };
  123 
  124 
  125     //! Visitor interface and base class for visitors of pairs of TypeTrees.
  126     /**
  127      * DefaultPairVisitor defines the interface for visitors that can be applied to a pair of TypeTrees
  128      * using applyToTreePair(). Each method of the visitor is passed a node of both trees (either as
  129      * a mutable or a const reference, depending on the constness of the tree applyToTreePair() was
  130      * called with). The last argument is of type TreePath and denotes the exact position of the
  131      * nodes within the TypeTrees, encoded as child indices starting at the root node.
  132      *
  133      * In order to create a functioning visitor, an implementation will - in addition to providing the methods
  134      * of this class - also have to contain the following template struct, which is used to determine
  135      * whether to visit a given node:
  136      *
  137      * \code
  138      * template<typename Node1,
  139      *          typename Child1,
  140      *          typename Node2,
  141      *          typename Child2,
  142      *          typename TreePath>
  143      * struct VisitChild
  144      * {
  145      *   static const bool value = ...; // decide whether to visit Child
  146      * };
  147      * \endcode
  148      *
  149      * For the two most common scenarios - visiting only direct children and visiting the whole tree - there
  150      * are mixin classes VisitDirectChildren and VisitTree and combined base classes TreePairVisitor and
  151      * DirectChildrenPairVisitor. The latter two inherit from both DefaultVisitor and one of the two mixin classes
  152      * and can thus be used as convenient base classes.
  153      *
  154      * \note If your compiler does not support rvalue references, both trees must be either const or
  155      *       non-const. If you call applyToTreePair() with two trees of different constness, they will
  156      *       both be made const.
  157      *
  158      * \note This class can also be used as a convenient base class if the implemented visitor
  159      *       only needs to act on some of the possible callback sites, avoiding a lot of boilerplate code.
  160      */
  161     struct DefaultPairVisitor
  162     {
  163 
  164       //! Method for prefix tree traversal.
  165       /**
  166        * This method gets called when first encountering a non-leaf node and
  167        * before visiting any of its children.
  168        *
  169        * \param t1       The node of the first tree to visit.
  170        * \param t2       The node of the second tree to visit.
  171        * \param treePath The position of the node within the TypeTree.
  172        */
  173       template<typename T1, typename T2, typename TreePath>
  174       void pre(T1&& t1, T2&& t2, TreePath treePath) const {}
  175 
  176       //! Method for infix tree traversal.
  177       /**
  178        * This method gets called BETWEEN visits of children of a non-leaf node.
  179        * That definition implies that this method will only be called for nodes
  180        * with at least two children.
  181        *
  182        * \param t1       The node of the first tree to visit.
  183        * \param t2       The node of the second tree to visit.
  184        * \param treePath The position of the node within the TypeTree.
  185        */
  186       template<typename T1, typename T2, typename TreePath>
  187       void in(T1&& t1, T2&& t2, TreePath treePath) const {}
  188 
  189       //! Method for postfix traversal.
  190       /**
  191        * This method gets called after all children of a non-leaf node have
  192        * been visited.
  193        *
  194        * \param t1       The node of the first tree to visit.
  195        * \param t2       The node of the second tree to visit.
  196        * \param treePath The position of the node within the TypeTree.
  197        */
  198       template<typename T1, typename T2, typename TreePath>
  199       void post(T1&& t1, T2&& t2, TreePath treePath) const {}
  200 
  201       //! Method for leaf traversal.
  202       /**
  203        * This method gets called when encountering a leaf node within the pair of TypeTrees.
  204        *
  205        * \attention Since the two TypeTrees are not required to be exactly identical,
  206        *            it is only guaranteed that at least one of the nodes is a leaf node,
  207        *            not both.
  208        *
  209        * \param t1       The node of the first tree to visit.
  210        * \param t2       The node of the second tree to visit.
  211        * \param treePath The position of the node within the TypeTree.
  212        */
  213       template<typename T1, typename T2, typename TreePath>
  214       void leaf(T1&& t1, T2&& t2, TreePath treePath) const {}
  215 
  216       //! Method for parent-child traversal.
  217       /**
  218        * This method gets called before visiting a child node.
  219        *
  220        * \note This method gets called even if the visitor decides not to visit the child in question.
  221        *
  222        * \param t1         The node of the first tree to visit.
  223        * \param child1     The child of t1 to visit.
  224        * \param t2         The node of the second tree to visit.
  225        * \param child2     The child of t2 to visit.
  226        * \param treePath   The position of the parent nodes within the TypeTree.
  227        * \param childIndex The index of the child nodes in relation to the parent nodes.
  228        */
  229       template<typename T1, typename Child1, typename T2, typename Child2, typename TreePath, typename ChildIndex>
  230       void beforeChild(T1&& t1, Child1&& child1, T2&& t2, Child2&& child2, TreePath treePath, ChildIndex childIndex) const {}
  231 
  232       //! Method for child-parent traversal.
  233       /**
  234        * This method gets called after visiting a child node.
  235        *
  236        * \note This method gets called even if the visitor decides not to visit the child in question.
  237        *
  238        * \param t1         The node of the first tree to visit.
  239        * \param child1     The child of t1 to visit.
  240        * \param t2         The node of the second tree to visit.
  241        * \param child2     The child of t2 to visit.
  242        * \param treePath   The position of the parent nodes within the TypeTree.
  243        * \param childIndex The index of the child nodes in relation to the parent nodes.
  244        */
  245       template<typename T1, typename Child1, typename T2, typename Child2, typename TreePath, typename ChildIndex>
  246       void afterChild(T1&& t1, Child1&& child1, T2&& t2, Child2&& child2, TreePath treePath, ChildIndex childIndex) const {}
  247 
  248     };
  249 
  250 
  251     namespace Experimental {
  252 
  253       /**
  254        * @brief Hybrid visitor interface and base class for TypeTree hybrid visitors.
  255        *
  256        * DefaultHybridVisitor defines the interface for visitors that can be applied to a TypeTree
  257        * using hybridApplyToTree(). Each method of the visitor is passed a node of the tree (either as
  258        * a mutable or a const reference, depending on the constness of the tree hybridApplyToTree() was
  259        * called with). The second argument is of type TreePath and denotes the exact position of the
  260        * node within the TypeTree, encoded as child indices starting at the root node.
  261        *
  262        * An hybrid visitor is different from a plain visitor because each method receives a carried value
  263        * (last argument) on the node visit and is required to return a transformed value from it.
  264        * Transformations of the carried value type are allowed as long as they are expected on the
  265        * next visited node.
  266        *
  267        * In order to create a functioning visitor, an implementation will - in addition to providing the methods
  268        * of this class - also have to contain the following template struct, which is used to determine
  269        * whether to visit a given node:
  270        *
  271        * \code
  272        * template<typename Node, typename Child, typename TreePath>
  273        * struct VisitChild
  274        * {
  275        *   static const bool value = ...; // decide whether to visit Child
  276        * };
  277        * \endcode
  278        *
  279        *
  280        * \note This class can also be used as a convenient base class if the implemented visitor
  281        *       only needs to act on some of the possible callback sites, avoiding a lot of boilerplate code.
  282        */
  283       struct DefaultHybridVisitor
  284       {
  285 
  286         /**
  287          * \copybrief DefaultVisitor::pre
  288          * \copydetails DefaultVisitor::pre
  289          *
  290          * \param u        The carry value from previous visit.
  291          * \return         The result of applying this visitor to u.
  292          */
  293         template<typename T, typename TreePath, typename U>
  294         auto pre(T&& t, TreePath treePath, const U& u) const { return u;}
  295 
  296         /**
  297          * \copybrief DefaultVisitor::in
  298          * \copydetails DefaultVisitor::in
  299          *
  300          * \param u        The carry value from previous visit.
  301          * \return         The result of applying this visitor to u.
  302          */
  303         template<typename T, typename TreePath, typename U>
  304         auto in(T&& t, TreePath treePath, const U& u) const {return u;}
  305 
  306         /**
  307          * \copybrief DefaultVisitor::post
  308          * \copydetails DefaultVisitor::post
  309          *
  310          * \param u        The carry value from previous visit.
  311          * \return         The result of applying this visitor to u.
  312          */
  313         template<typename T, typename TreePath, typename U>
  314         auto post(T&& t, TreePath treePath, const U& u) const {return u;}
  315 
  316         /**
  317          * \copybrief DefaultVisitor::leaf
  318          * \copydetails DefaultVisitor::leaf
  319          *
  320          * \param u        The carry value from previous visit.
  321          * \return         The result of applying this visitor to u.
  322          */
  323         template<typename T, typename TreePath, typename U>
  324         auto leaf(T&& t, TreePath treePath, const U& u) const { return u;}
  325 
  326         /**
  327          * \copybrief DefaultVisitor::beforeChild
  328          * \copydetails DefaultVisitor::beforeChild
  329          *
  330          * \param u        The carry value from previous visit.
  331          * \return         The result of applying this visitor to u.
  332          */
  333         template<typename T, typename Child, typename TreePath, typename ChildIndex, typename U>
  334         auto beforeChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex, const U& u) const {return u;}
  335 
  336         /**
  337          * \copybrief DefaultVisitor::afterChild
  338          * \copydetails DefaultVisitor::afterChild
  339          *
  340          * \param u        The carry value from previous visit.
  341          * \return         The result of applying this visitor to u.
  342          */
  343         template<typename T, typename Child, typename TreePath, typename ChildIndex, typename U>
  344         auto afterChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex, const U& u) const {return u;}
  345 
  346       };
  347     } // namespace Experimental
  348 
  349     //! Mixin base class for visitors that only want to visit the direct children of a node.
  350     /**
  351      * This mixin class will reject all children presented to it, causing the algorithm to
  352      * only visit the root node and call DefaultVisitor::beforeChild() and DefaultVisitor::afterChild()
  353      * for its direct children.
  354      */
  355     struct VisitDirectChildren
  356     {
  357 
  358       // the little trick with the default template arguments
  359       // makes the class usable for both single-tree visitors
  360       // and visitors for pairs of trees
  361       //! Template struct for determining whether or not to visit a given child.
  362       template<typename Node1,
  363                typename Child1,
  364                typename Node2,
  365                typename Child2 = void,
  366                typename TreePath = void>
  367       struct VisitChild
  368       {
  369         //! Do not visit any child.
  370         static const bool value = false;
  371       };
  372 
  373     };
  374 
  375 
  376     //! Mixin base class for visitors that want to visit the complete tree.
  377     /**
  378      * This mixin class will accept all children presented to it and thus make the iterator
  379      * traverse the entire tree.
  380      */
  381     struct VisitTree
  382     {
  383 
  384       // the little trick with the default template arguments
  385       // makes the class usable for both single-tree visitors
  386       // and visitors for pairs of trees
  387       //! Template struct for determining whether or not to visit a given child.
  388       template<typename Node1,
  389                typename Child1,
  390                typename Node2,
  391                typename Child2 = void,
  392                typename TreePath = void>
  393       struct VisitChild
  394       {
  395         //! Visit any child.
  396         static const bool value = true;
  397       };
  398 
  399     };
  400 
  401     //! Mixin base class for visitors that require a static TreePath during traversal.
  402     /**
  403      * \warning Static traversal should only be used if absolutely necessary, as it tends
  404      *          to increase compilation times and object sizes (especially if compiling
  405      *          with debug information)!
  406      *
  407      * \sa DynamicTraversal
  408      */
  409     struct StaticTraversal
  410     {
  411       //! Use the static tree traversal algorithm.
  412       static const TreePathType::Type treePathType = TreePathType::fullyStatic;
  413     };
  414 
  415     //! Mixin base class for visitors that only need a dynamic TreePath during traversal.
  416     /**
  417      * \note Dynamic traversal is preferable to static traversal, as it causes fewer
  418      *       template instantiations, which improves compile time and reduces object
  419      *       size (especially if compiling with debug information).
  420      *
  421      * \sa StaticTraversal
  422      */
  423     struct DynamicTraversal
  424     {
  425       //! Use the dynamic tree traversal algorithm.
  426       static const TreePathType::Type treePathType = TreePathType::dynamic;
  427     };
  428 
  429     //! Convenience base class for visiting the entire tree.
  430     struct TreeVisitor
  431       : public DefaultVisitor
  432       , public VisitTree
  433     {};
  434 
  435     //! Convenience base class for visiting the direct children of a node.
  436     struct DirectChildrenVisitor
  437       : public DefaultVisitor
  438       , public VisitDirectChildren
  439     {};
  440 
  441     //! Convenience base class for visiting an entire tree pair.
  442     struct TreePairVisitor
  443       : public DefaultPairVisitor
  444       , public VisitTree
  445     {};
  446 
  447     //! Convenience base class for visiting the direct children of a node pair.
  448     struct DirectChildrenPairVisitor
  449       : public DefaultPairVisitor
  450       , public VisitDirectChildren
  451     {};
  452 
  453     namespace Experimental::Info {
  454 
  455       struct LeafCounterVisitor
  456         : public DefaultHybridVisitor
  457         , public StaticTraversal
  458         , public VisitTree
  459       {
  460         template<class Tree, class Child, class TreePath, class ChildIndex, class U>
  461         auto beforeChild(Tree&&, Child&&, TreePath, ChildIndex, U u) const {
  462           // in this case child index is an integral constant: forward u
  463           return u;
  464         }
  465 
  466         template<class Tree, class Child, class TreePath, class U>
  467         std::size_t beforeChild(Tree&&, Child&&, TreePath, std::size_t childIndex, U u) const {
  468           // in this case child index is a run-time index: cast accumulated u to std::size_t
  469           return std::size_t{u};
  470         }
  471 
  472         template<class Tree, class TreePath, class U>
  473         auto leaf(Tree&&, TreePath, U u) const
  474         {
  475           return Hybrid::plus(u,Dune::Indices::_1);
  476         }
  477 
  478       };
  479 
  480       struct NodeCounterVisitor
  481         : public LeafCounterVisitor
  482       {
  483         template<typename Tree, typename TreePath, typename U>
  484         auto pre(Tree&& tree, TreePath treePath, U u) const {
  485           return Hybrid::plus(u,Indices::_1);
  486         }
  487       };
  488 
  489       struct DepthVisitor
  490         : public DefaultHybridVisitor
  491         , public StaticTraversal
  492         , public VisitTree
  493       {
  494         template<class Tree, class TreePath, class U>
  495         auto leaf(Tree&&, TreePath, U u) const
  496         {
  497           auto path_size = index_constant<treePathSize(TreePath{})>{};
  498           auto depth = Hybrid::plus(path_size,Indices::_1);
  499           return Hybrid::max(depth,u);
  500         }
  501       };
  502 
  503     //! The depth of the TypeTree.
  504     // result is alwayas an integral constant
  505       template<typename Tree>
  506       auto depth(const Tree& tree)
  507       {
  508         return hybridApplyToTree(tree,DepthVisitor{},Indices::_0);
  509       }
  510 
  511       //! The depth of the Tree.
  512       // return types is std::integral_constant.
  513       template<typename Tree>
  514       constexpr auto depth()
  515       {
  516         return decltype(hybridApplyToTree(std::declval<Tree>(),DepthVisitor{},Indices::_0)){};
  517       }
  518 
  519       //! The total number of nodes in the Tree.
  520       // if Tree is dynamic, return type is std::size_t, otherwise std::integral_constant.
  521       template<typename Tree>
  522       auto nodeCount(const Tree& tree)
  523       {
  524         return hybridApplyToTree(tree,NodeCounterVisitor{},Indices::_0);
  525       }
  526 
  527       //! The number of leaf nodes in the Tree.
  528       // if Tree is dynamic, return type is std::size_t, otherwise std::integral_constant.
  529       template<typename Tree>
  530       auto leafCount(const Tree& tree)
  531       {
  532         return hybridApplyToTree(tree,LeafCounterVisitor{},Dune::Indices::_0);
  533       }
  534 
  535       //! true if any of the nodes in the tree only has dynamic degree.
  536       template<typename Tree>
  537       constexpr bool isDynamic = std::is_same<std::size_t, decltype(leafCount(std::declval<Tree>()))>{};
  538 
  539     } // namespace Experimental::Info
  540 
  541     //! \} group Tree Traversal
  542 
  543   } // namespace TypeTree
  544 } //namespace Dune
  545 
  546 #endif // DUNE_TYPETREE_VISITOR_HH