CMappedList create() incorrectly handles insert_at_start

[Hayk Martirosyan]

You're right, I couldn't leave it alone :). I found the bug, nothing to do with STL. Recreated with the file below.

#include <iostream>
#include "CMappedList.hpp"

class A {
public:
  sutil::CMappedList<std::string, std::string> data_;
};

class B {
public:

  B() { std::cout << "B constructor" << std::endl; }
  ~B() { std::cout << "B destructor" << std::endl; }

  sutil::CMappedList<std::string, A> data_;
};

int main(int argc, char* argv[]) {

  std::cout << "Allocating b" << std::endl;
  B* b = new B();

  std::cout << "Populating b" << std::endl;
  A* one = b->data_.create("one", true);
  one->data_.create("fruit", "apple", true);
  A* two = b->data_.create("two", true);
  two->data_.create("candy", "twix", true);

  std::cout << "Copying b to b2" << std::endl;
  B* b2 = new B(*b);

  std::cout << "Querying for b2 data" << std::endl;
  std::cout << "b one: " << *b->data_.at("one")->data_.at(0) << std::endl;
  std::cout << "b two: " << *b->data_.at("two")->data_.at(0) << std::endl;
  std::cout << "b2 one: " << *b2->data_.at("one")->data_.at(0) << std::endl;
  std::cout << "b2 two: " << *b2->data_.at("two")->data_.at(0) << std::endl;

  return 0;
}

Compile with: $ g++ -std=c++11 -ggdb -o test main.cpp

Result:

$ ./test 
Allocating b
B constructor
Populating b
CMappedList Copy Constructor
CMappedList Copy Constructor
Copying b to b2
CMappedList Copy Constructor
CMappedList Copy Constructor
CMappedList Copy Constructor
Querying for b2 data
b one: apple
b two: twix
b2 one: twix
b2 two: twix

The error is that the last two lines both print twix, meaning b was incorrectly copied to b2. If we look inside CMappedList, at create(), we see it has the bool insert_at_start parameter, with an if-else if-else statement to insert the tmp pointer at the front_ or back_. However, regardless of this, the code following creates and adds front_ to map_ and returns front_->data_:

map_.insert( std::pair<Idx, SMLNode<Idx,T> *>(arg_idx, front_) );
flag_is_sorted_ = false;

return front_->data_;

This is incorrect behavior when create is called with insert_at_start = false, as is done from deepCopy. The fix is to use back_ instead of front_ when needed, with something like the following as the end of create():

    size_++;
    flag_is_sorted_ = false;

    if((0 == size_) || insert_at_start) {
      map_.insert( std::pair<Idx, SMLNode<Idx,T> *>(arg_idx, front_) );
      return front_->data_;
    } else {
      map_.insert( std::pair<Idx, SMLNode<Idx,T> *>(arg_idx, back_) );
      return back_->data_;
    }

Result:

$ ./test 
Allocating b
B constructor
Populating b
CMappedList Copy Constructor
CMappedList Copy Constructor
Copying b to b2
CMappedList Copy Constructor
CMappedList Copy Constructor
CMappedList Copy Constructor
Querying for b2 data
b one: apple
b two: twix
b2 one: apple
b2 two: twix

qed

[Samir Menon]

Nice catch! Thanks for the simple test. Turns out you helped catch another bug.. ;-)

Fixed as of: https://github.com/samirmenon/sUtil/commit/77ca30ef13fd16c61442b9de2692ecbbfe74b65c

Please check and close the bug. Thx!

There is also a test case here: https://github.com/samirmenon/sUtil/commit/7a44ab41611d1d9e3e1e001e17ec313a3748c46c

(Compile and run test suite 2 in sutil applications-linux/sutil_test)..

[Samir Menon]

Running your code:

$ sUtil.git/src/sutil$ g++ -std=c++11 -ggdb -o test tmp.cpp
$ sUtil.git/src/sutil$ ./test 
Allocating b
B constructor
Populating b
Copying b to b2
Querying for b2 data
b one: apple
b two: twix
b2 one: apple
b2 two: twix

[Samir Menon]

Please close this when you are satisfied that the fix works...

[Hayk Martirosyan]

Confirmed that the test case now works. However, my robot still can't copy properly in my original use case. After some more investigation, I found an issue with CMappedTree's copy behavior. CMappedTree::deepCopy calls CMappedList::deepCopy, but line 211 is incorrect:

this->root_node_ = CMappedList<TIdx,TNode>::at(arg_mt->getRootNodeConst()->name_);

It should set the root node pointer to its own newly allocated root node, not the argument's. In general, any pointers in a class to its own members need to be pointed at the newly allocated versions for copying to work properly. Not sure if there are more cases of this in the CMapped suite or the SCL data structures.

Example snippet:

  Robot* r = new Robot(SPEC_DIR, config_fileA, robot_nameA);
  r->initDataStructures();
  robots_.push_back(*r);
  delete r;

In this case, robots_[0].rgcm_.rbdyn_tree_.root_node_ now points to deallocated memory, what used to be (*r).rgcm_.rbdyn_tree_.root_node_.

[Hayk Martirosyan]

Taking a quick look at the data structures, several of them SRigidBody, SRigidBodyDyn, SForce, etc. have member variables which are pointers to other data structures to denote parents, children, etc. This inherently means that they won't copy correctly. Let's say a class has two SRigidBodies, which are referencing each other - I can't think of a good way to copy both and update the pointers in between them (except manually) to have that class copy correctly.

I see two options:

1. Make sure all data structures copy properly by setting the pointers correctly (probably very hard).
2. Change the pointers to something that does a lookup (probably a lot of time?).
3. Explicitly forbid copying so people don't get confusing segfaults:

NonCopyable & operator=(const NonCopyable&) = delete;
NonCopyable(const NonCopyable&) = delete;

[Samir Menon]

this->root_node_ = CMappedList<TIdx,TNode>::at(arg_mt->getRootNodeConst()->name_);

Line 211 uses the newly allocated root node. The CMappedList<TIdx,TNode>::at() function is a member function for the object. It just uses the root node's name from the passed arg_mt object.

Moreover, arg_mt is a const pointer while this->root_node_ is not. Just print the pointers and you'll see that they are different.

There does seem to be something else wrong with the deep copy, however... Lemme check..

[Samir Menon]

Overall, it's a good point. I think forbidding copying is a bad solution.

Probably best to make sure that all data structures copy properly. Let me think about this.

[Samir Menon]

Here's the test:

// *************************
      //9. Test deep copy code
      sutil::CMappedTree<std::string,_testSMTNode> mtree2(mtree);

      //Some iterator "itcp" (iterator copied mtree) to be used below...
      sutil::CMappedTree<std::string,_testSMTNode>::const_iterator itcp,itcpe;

      std::cout<<"\nTest Result ("<<test_id++<<") : \nOriginal mapped tree's nodes : ";
      // Print all links
      itcp = mtree.begin(); itcpe = mtree.end();
      for(; itcp!=itcpe;++itcp)
      { std::cout<<" "<<(!itcp);  }
      std::cout<<std::flush;

      std::cout<<"\n  Copied static alloc mapped tree's nodes : ";
      // Print all links
      itcp = mtree2.begin(); itcpe = mtree2.end();
      for(; itcp!=itcpe;++itcp)
      { std::cout<<" "<<(!itcp);  }
      std::cout<<std::flush;

      const _testSMTNode* org_root = mtree.getRootNodeConst();
      std::cout<<"\nTest Result ("<<test_id++<<") : Original mapped tree's root node pointer : "<<org_root<<std::flush;

      const _testSMTNode* mtree2_root = mtree2.getRootNodeConst();
      std::cout<<"\nTest Result ("<<test_id++<<") : Static alloc copied mapped tree's root node pointer : "<<mtree2_root<<std::flush;

      std::cout<<"\nTest Result ("<<test_id++<<") : Original mapped tree's root node's children : ";
      // Print all links
      for(auto && it : mtree.getRootNodeConst()->child_addrs_)
      { std::cout<<" "<<it->name_;  }

      std::cout<<"\nTest Result ("<<test_id++<<") : Static alloc copied mapped tree's root node's children : ";
      // Print all links
      for(auto && it : mtree2.getRootNodeConst()->child_addrs_)
      { std::cout<<" "<<it->name_;  }

      std::cout<<"\nTest #"<<arg_id<<" (Mapped Tree Test) Succeeded.";

https://github.com/samirmenon/sUtil/blob/master/applications-linux/sutil_test/test-mapped-tree.cpp

Prints out:

Test Result (24) : 
            Original mapped tree's nodes :  r2 r1 l3 l2 root l1
 Copied static alloc mapped tree's nodes :  r2 r1 l3 l2 root l1
Test Result (25) : Original mapped tree's root node pointer : 0x233e230
Test Result (26) : Static alloc copied mapped tree's root node pointer : 0x233eb80
Test Result (27) : Original mapped tree's root node's children :  r1 l1
Test Result (28) : Static alloc copied mapped tree's root node's children :  r1 l1

[Hayk Martirosyan]

Hmm, you're right that line CMappedList<TIdx,TNode>::at(arg_mt->getRootNodeConst()->name_) seems to be a lookup on itself based on the string name.

However, in the debugger I specifically found that the rdyn_tree_ links were copied over and all had new addresses, but the root_node_ pointer of the copied tree still held the address of the original, and not the new, ground link.

[Samir Menon]

Not sure what you were doing. The above test results say otherwise:

Test Result (25) : Original mapped tree's root node pointer : 0x233e230
Test Result (26) : Static alloc copied mapped tree's root node pointer : 0x233eb80

(Btw, the plain sutil source is here: [e-mail]:samirmenon/sUtil.git)

The weird problem here is that somehow, when I alloc a CMappedTree<> on the heap with new, it doesn't work.. Ack!

[Hayk Martirosyan]

I was examining in the debugger the states of the rbdyn tree inside of the rgcm inside of the robot class with the following code, in (*r) vs robots_[0]:

 Robot* r = new Robot(SPEC_DIR, config_fileA, robot_nameA);
  r->initDataStructures();
  robots_.push_back(*r);

I can check again tomorrow, but 90% sure. Note that this is on the heap, and also copied onto the heap inside the vector.

[Samir Menon]

Ok the latest commit should work for sure: 94be3d4

Try again after a git submodule update...

The issue was that I was using the destructor to reset the object to a newly constructed state but that doesn't work in general. Also cleaned up a few related things.

Thx for catching the bugs!

[Samir Menon]

Please check and close!

[Hayk Martirosyan]

You seem to have fixed the previous issue. The image capture below from the debugger now shows that the root_node_ entries are different addresses, as well as the list entries.

However, I still can't copy my Robot because of the larger issue of pointers in the data structures. In the screenshot, we can see an example of this where the root nodes have been copied, but the link_ds_ inside the root nodes still point to the same entry. This becomes a seg fault when the SRigidBody it points to is destructed.

I'm going to name this issue solved and open up a new one about the pointers.

[Hayk Martirosyan]

Original issue and related bugs fixed.

[Hayk Martirosyan]

Follow up #168.