Skip to content

Modernized tree traversal using c++17 constexpr_if

This MR tries to use modern c++ features from c++17 to improve the code of tree traversal. One goal is to shorten the error messages in case there is something wrong in the inner traversal loop. Another goal is to reduce compile times.

The main strategies are:

  • reduce instantiation depth (by not chaining simple forward functions)
  • replace simple lambdas with class
  • replace Hybrid::ifElse with if constexpr(_)

In order to test the modified traversal, I have used a minimal code with a simple basis tree from dune-functions:

int main()
{
  Dune::YaspGrid<2> grid({1.0,1.0}, {1,1});
  auto gridView = grid.leafGridView();

  using namespace Dune::Functions::BasisFactory;
  auto basis1 = makeBasis(gridView,
    composite(power<2>(lagrange<2>(), flatInterleaved()), lagrange<1>(), flatLexicographic()));

  auto localView = basis1.localView();
  Dune::TypeTree::forEachLeafNode(localView.tree(), [](auto const& node, auto const& tp)
  {
    std::cout << node.tp() << std::endl; // ERROR: node has no member .tp()
  });
}

Short summary: compiler: g++-8.1, size of error message in Bytes and number of lines

dune-2.6 dune-2.7 branch treepath-tuple
Bytes 46686 76851 11857 8311
Lines 33 61 29 26

I thought about other strategies to reduce compiler error messages. One could be to flatten the tree before traversal and then use a regular forEach loop to traverse the leaf elements. Another (similar) strategy would be to just create a (flat) tuple of treepath's that are traversed and the node is extracted from the root node using the current treepath-tuple element.

NOTE: if someone finds the reference implementation of expansion statements in clang, it would be nice to test it. The clang-expansion fork by Sam Goodrick seems not be work correctly still for slightly complicated expansion statements.

Edited by Simon Praetorius

Merge request reports