Improve node subclassing

[ahornung]

Apparently subclassing octree data nodes is confusing, error-prone and can lead to confusing slicing bugs such as #95 and #93 .

In general, deriving custom nodes and octrees should be improved. Options could include better documentation in the code and / or a wiki page, or file templates.

Making ocree nodes virtual (polymorphism) as suggested in #97 is not an option, however, because of the additional memory requirement for the vtable pointers.

[ahornung]

Related issues:

#70 OcTreeDataNode's destructor is not virtual
#93 Subclassing OcTreeNode - memory bug
#95 OcTreeNode with 64 bits members crashes

[ahundt]

Perhaps consider crtp, a C++ technique for subclassing using templates? I believe that technique eliminates the performance issue and the subclassing issue in one fell swoop.

[ahornung]

Yes, that would definitely be the right way!

[lorenzoriano]

As it is subclassing OcTreeNode doesn't work. This is due to the static_cast happening in OcTreeNode (https://github.com/OctoMap/octomap/blob/devel/octomap/include/octomap/OcTreeNode.h#L65) and the fact that children in OcTreeDataNode is of non-polymorphic type OcTreeDataNode.

In several occasions the code seems to work fine (as for the coloured nodes), but a crash is always lurking (see the issues mentioned above). No better documentation could solve this problem, and a re-design of the OcTreeDataNode data type is necessary. CRTP might be the solution!

[ahornung]

@lorenzoriano Subclassing works as long as the functions mentioned in the header (https://github.com/OctoMap/octomap/blob/devel/octomap/include/octomap/OcTreeNode.h#L49) are implemented in the derived class as well (including adjusted casts), this avoids the memory issues as it is done in ColorOcTreeNode. Probably expandNode() has to be added to that list as well, but I haven't investigated it in detail yet.

But I agree that it's definitely too easy to miss, or to derive an incomplete class. Documentation or file templates could help with that.

If we're aiming for an API-breaking change, we could completely rid the nodes of all the tree logic (e.g. createChild, getChild, ...) and move that into the tree class. It already knows the correct node class (which is not allowed to change within a tree) from the template parameter, thus acting in a way similar to CRTP already!

[ahornung]

It took some time, but I now have a prototype ready in the branch node-subclassing-tree. All the casts and tree structure management are now the responsibility of the tree class, so it's sufficient to have it implemented only once in OcTreeBaseImpl. That means that nodes only care about their own stored data, not their children.

It's not yet 100% done but definitely ready to try out. The unit tests succeed and a valgrind memcheck (suppressing everything related to the StaticMemberInitializer) also shows nothing suspicious, although the only truly derived ColorOcTreeNode is not fully utilized yet (e.g. pruning and extending).

[lorenzoriano]

It's looking good! What else do you need to do?

[ahundt]

Is casting to void** correct? I seem to recall reading recently that it is best avoided in modern C++ and that there are good alternatives. However, I haven't been able to locate an exact reference to back up my recollection, perhaps in one of Scott Meyers' books...

[lorenzoriano]

Yeah that void** is really not recommended. I drafted an implementation of Curiously recurring template pattern, you can find it at https://github.com/bosch-ros-pkg/octomap/tree/node-subclassing-tree. It segfaults on test_io, so there's some casts that I'm missing, but at least we can see if the idea is sound

[ahornung]

That void* array was quick hack, I just changed it to AbstractOcTreeNode*. Although technically it's doing the same thing (tree class maintains the correct casts) it's more clear what's supposed to be stored in the "universal" child array.

What needs to be done: A bit more cleanup (a few children-related functions still remain in OcTreeDataNode) and remaining TODOs in OcTreeBaseImpl.

Finally: More testing with derived node classes (especially updated nodes, extending and pruning them). There should be no segfaults and valgrind memcheck (run as mentioned in https://github.com/OctoMap/octomap/blob/node-subclassing-tree/octomap/valgrind_memcheck.supp) should return no errors. There's one leak concerning KeyRay that I still need to trace down but it's unrelated to the changes in the node-subclassing-tree branch.

[ahornung]

Is there any reason not to merge node-subclassing-tree into devel, to get ready for a new release?

In my opinion there's no real need for CRTP anymore. All the casts and memory management is now hidden in OcTreeBaseImpl, which a user does not need to touch (or even know about) anymore. Custom derived node classes should be easily possible. With CRTP, anyone deriving a custom node needs to implement it properly and the structure may not be obvious to anyone.

[ahornung]

Update: PR merged into devel.

[ahornung]

Closing here, version 1.8.0 with all changes released. If you update to this version, remember to update your custom node classes accordingly. You should be fine by removing the following member functions from the nodes, if used at all:

• createChild(...)
• getChild(...)
• expandNode()
• pruneNode()
• hasChildren()
• childExists(...)
• collapsible()

[lorenzoriano]

Thanks for fixing this!