Recursive Behavior Trees

[Rockjack00]

Describe the bug
Behavior trees can be provided their own ID as a Subtree leading to a stack overflow during parsing (this also works for cycles).

Example simple recursive behavior tree (slightly modified from btcpp_sample):

 <root BTCPP_format="4" >
     <BehaviorTree ID="MainTree">
        <Sequence name="root">
            <AlwaysSuccess/>
            <SaySomething   message="this works too" />
            <ThinkWhatToSay text="{the_answer}"/>
            <SaySomething   message="{the_answer}" />
            <SubTree ID="MainTree" />
        </Sequence>
     </BehaviorTree>

 </root>

Resulted in this backtrace:

#0  0x00007ffff78a3e57 in _int_malloc (av=av@entry=0x7ffff7a1ac80 <main_arena>, bytes=bytes@entry=936) at ./malloc/malloc.c:3982
#1  0x00007ffff78a5262 in __GI___libc_malloc (bytes=936) at ./malloc/malloc.c:3321
#2  0x00007ffff7cae98c in operator new(unsigned long) () from /lib/x86_64-linux-gnu/libstdc++.so.6
#3  0x00007ffff7f1454d in BT::TreeNode::TreeNode(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, BT::NodeConfig) ()
   from /opt/ros/humble/lib/libbehaviortree_cpp.so
#4  0x00007ffff7f14d66 in BT::ControlNode::ControlNode(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::NodeConfig const&)
    () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#5  0x00007ffff7f46b3c in BT::SequenceNode::SequenceNode(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool) ()
   from /opt/ros/humble/lib/libbehaviortree_cpp.so
#6  0x00007ffff7f06f33 in std::_Function_handler<std::unique_ptr<BT::TreeNode, std::default_delete<BT::TreeNode> > (std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::NodeConfig const&), BT::CreateBuilder<BT::SequenceNode>()::{lambda(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::NodeConfig const&)#1}>::_M_invoke(std::_Any_data const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::NodeConfig const&) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#7  0x00007ffff7eeb8cc in BT::BehaviorTreeFactory::instantiateTreeNode(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::NodeConfig const&) const () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#8  0x00007ffff7f3af22 in BT::XMLParser::PImpl::createNodeFromXML(tinyxml2::XMLElement const*, std::shared_ptr<BT::Blackboard> const&, std::shared_ptr<BT::TreeNode> const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::Tree&) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#9  0x00007ffff7f3b89a in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#10 0x00007ffff7f3c70d in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#11 0x00007ffff7f35677 in BT::XMLParser::PImpl::recursivelyCreateSubtree(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::Tree&, std::shared_ptr<BT::Blackboard>, std::shared_ptr<BT::TreeNode> const&) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#12 0x00007ffff7f3bd67 in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#13 0x00007ffff7f3c70d in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#14 0x00007ffff7f3c1e5 in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#15 0x00007ffff7f3c70d in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#16 0x00007ffff7f35677 in BT::XMLParser::PImpl::recursivelyCreateSubtree(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::Tree&, std::shared_ptr<BT::Blackboard>, std::shared_ptr<BT::TreeNode> const&) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#17 0x00007ffff7f3bd67 in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#18 0x00007ffff7f3c70d in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#19 0x00007ffff7f3c1e5 in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#20 0x00007ffff7f3c70d in ?? () from /opt/ros/humble/lib/libbehaviortree_cpp.so

...

#25681 0x00007ffff7f35677 in BT::XMLParser::PImpl::recursivelyCreateSubtree(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, BT::Tree&, std::shared_ptr<BT::Blackboard>, std::shared_ptr<BT::TreeNode> const&) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#25682 0x00007ffff7f39b3f in BT::XMLParser::instantiateTree(std::shared_ptr<BT::Blackboard> const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#25683 0x00007ffff7eebb54 in BT::BehaviorTreeFactory::createTreeFromText(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::shared_ptr<BT::Blackboard>) () from /opt/ros/humble/lib/libbehaviortree_cpp.so
#25684 0x000055555555c011 in main () at /home/{obfuscated}/bt_ws/src/btcpp_sample/main.cpp:72

More complex example of a cyclical recursive behavior tree (again, slightly modified from btcpp_sample):

 <root BTCPP_format="4" main_tree_to_execute="MainTree">

     <BehaviorTree ID="MainTree">
        <Sequence name="root">
            <AlwaysSuccess/>
            <SaySomething   message="this works too" />
            <ThinkWhatToSay text="{the_answer}"/>
            <SaySomething   message="{the_answer}" />
            <SubTree ID="TreeA" />
        </Sequence>
     </BehaviorTree>

     <BehaviorTree ID="TreeA">
        <Sequence name="root">
            <AlwaysSuccess/>
            <SaySomething   message="this works too" />
            <ThinkWhatToSay text="{the_answer}"/>
            <SaySomething   message="{the_answer}" />
            <SubTree ID="TreeB" />
        </Sequence>
     </BehaviorTree>

     <BehaviorTree ID="TreeB">
        <Sequence name="root">
            <AlwaysSuccess/>
            <SaySomething   message="this works too" />
            <ThinkWhatToSay text="{the_answer}"/>
            <SaySomething   message="{the_answer}" />
            <SubTree ID="MainTree" />
        </Sequence>
     </BehaviorTree>
 </root>

How to Reproduce
This can be easily reproduced by building the Sample BehaviorTree.CPP Project. I did so using colcon and modifying the static const char* xml_text on line 6 with the behavior trees shown above.

[facontidavide]

recursive behavior tree are not supported and will never be. This should not be accepted in the first place, therefore the "bug" is allowing you to try doing it, without giving a proper error message

[Rockjack00]

Wow, fast response! I was in the process of writing this suggestion:

Suggestions
I am assuming that recursive behavior trees should not be encouraged by design, so these are related to preventing their creation:
In XMLParser::PImpl::recursivelyCreateSubtree when subtrees nodes are created, check that the subtree ID does not already exist in its prefix.

[facontidavide]

it is not about "not encouraging". They are plain impossible to implement, in the current version of the software.