Generic Visitor Builder

Recently, I’ve been implementing an internal scene graph data structure and I want to show my solution for building generic scene graph visitors.

Lets consider a basis type for our tree.

class base_node {
public:
  base_node() : m_name{"default"} {}
  base_node(std::string name) : m_name{std::move(name)} {}

  [[nodiscard]] auto& name() { return m_name; }
  [[nodiscard]] auto& name() const { return m_name; }
  [[nodiscard]] auto& children() { return m_children; }
  [[nodiscard]] auto& children() const { return m_children; }

private:
  std::string m_name;
  std::vector<base_node> m_children;
};

We can create a new scene graph like this:

  auto layer_1 = base_node{"parent"};
  
  auto& layer_2 = layer_1.children();
  layer_2 = {{"child_1"},{"child_2"},{"child_3"},{"child_4"},{"child_5"}};

  auto& layer_3 = layer_2[1].children();
  layer_3 = {{"child_6"},{"child_7"},{"child_8"},{"child_9"},{"child_10"}};

It has a name and a vector of base_nodes to hold its children.

So now lets say you want to apply some function to the whole scene graph; lets say you want to print the hierarchy.

We could write a visitor functor which takes a base_node and recursively calls itself with all of its children printing the name of each node. For this example, we will visit in a preorder fashion.

We will also add some state to make it look pretty.

struct print_hierarchy {
  void operator()(base_node& parent) {
    auto put_indent = [count = m_level] (const char indent_char) mutable {
      while(count--) std::cout << indent_char;
    };
    auto increase_indent = [&] () {
      m_level += 2;
    };
    auto decrease_indent = [&] () {
      m_level -= 2;
    };

    put_indent('-');

    std::cout << parent.name() << '\n';

    increase_indent();
    for(auto& node: parent.children()) {
      (*this)(node);
    }
    decrease_indent();
  }
  
private:
  size_t m_level{0};
};

If we call this on our hierarchy, we get:

parent
--child_1
--child_2
----child_6
----child_7
----child_8
----child_9
----child_10
--child_3
--child_4
--child_5

We can make this more generic by replacing the cout with a call to some callable.

We need to pass a Callable template argument to our visitor. We will also rename it to hierarchy_visitor

struct hierarchy_visitor {
  template<class TCallable>
  void operator()(base_node& parent, TCallable callable) {
    auto put_indent = [count = m_level] (const char indent_char) mutable {
      while(count--) std::cout << indent_char;
    };
    auto increase_indent = [&] () {
      m_level += 2;
    };
    auto decrease_indent = [&] () {
      m_level -= 2;
    };

    put_indent('-');

    callable(parent);

    increase_indent();
    for(auto& node: parent.children()) {
      (*this)(node, callable);
    }
    decrease_indent();
  }
private:
  size_t m_level{0};
};

We can now do this:

auto print_node = [](base_node& parent) {
  std::cout << parent.name() << '\n';
};

auto visitor = hierarchy_visitor();
visitor(layer_1, print_node);

But now we have a new problem. We have formatting hard coded into our visitor. It isn’t as generic as it could be.

We want to refactor out the formatting code. We can move put_indent to the callable and make the callable accept a layer parameter that tells the current level in the hierarchy visitor. It makes since for a hierarchy visitor to know its current level so level will remain inside the visitor. We will also rename the lambdas to something that sounds more generic.

struct hierarchy_visitor {
  template <class TCallable>
  void operator()(base_node& parent, TCallable callable) {
    auto increase_level = [&]() { m_level += 1; };
    auto decrease_level = [&]() { m_level -= 1; };

    callable(parent, m_level);

    increase_level();
    for (auto& node : parent.children()) {
      (*this)(node, callable);
    }
    decrease_level();
  }

 private:
  size_t m_level{0};
};

auto print_node = [indent_char = '-', indent_width = 2](base_node& parent, auto level) {
  auto put_indent = [&indent_width, level](auto indent_char) mutable {
    level *= indent_width;
    while (level--) std::cout << indent_char;
  };

  put_indent(indent_char);
  std::cout << parent.name() << '\n';
};

What if we don’t want to pass our callable in every recursive call? We can allow our hierarchy visitor to store it as a private member.

template<class TCallable>
struct hierarchy_visitor {
  void operator()(base_node& parent) {
    auto increase_level = [&]() { m_level += 1; };
    auto decrease_level = [&]() { m_level -= 1; };

    m_callable(parent, m_level);

    increase_level();
    for (auto& node : parent.children()) {
      (*this)(node, callable);
    }
    decrease_level();
  }

 private:
  TCallable m_callable;
  size_t m_level{0};
};

But now we have an issue where we cant determine the type of a lambda to instantiate an instance of hierarchy_visitor. We will have to give hierarchy_visitor a constructor which takes a TCallable.

But even this is not enough. Since
We will have to create a builder.

template <typename Callable>
hierarchy_visitor<Callable> build_hierarchy_visitor(Callable callable) {
  return {callable};
}

Now we can build a hierarchy_visitor but what about other types of visitors?

We can use some lambda magic with variable templates to accept a generic TCallable and TVisitor.

template <template <class> class TVisitor>
auto build_visitor =
    [](auto callable) -> TVisitor<std::decay_t<decltype(callable)>> {
  return {callable};
};

Unfortunately this doesn’t work in MSVC without -std:c++latest so we’ll have to try something else for the most portable code.

template <template <class> class TVisitor, class TCallable>
TVisitor<TCallable> build_visitor(TCallable callable) {
  return {callable};
}

We can then create new visitors and call them like this:

  auto visitor = build_visitor<hierarchy_visitor>(print_node);
  visitor(layer_1);

I tested this one on Clang 9, GCC 9.2, and MSVC 19.24 and it works fine.

Here is an alternative which may be more flexible and also works on all platforms:

template <template <class> class TVisitor>
struct build_visitor_impl {
  template <typename TCallable>
  constexpr auto operator()(TCallable callable) const
      -> TVisitor<decltype(callable)> {
    return {callable};
  }
};

template <template <class> class TVisitor>
inline constexpr auto build_visitor = build_visitor_impl<TVisitor>{};

View the full code on Compiler Explorer.

Thanks for reading!