Re: [Boost-bugs] [Boost C++ Libraries] #11801: Recursive modify in multi_index sometimes does not update index correctly

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11801: Recursive modify in multi_index sometimes does not update index correctly
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-11-19 08:08:07

#11801: Recursive modify in multi_index sometimes does not update index correctly
-------------------------------------+-------------------------------------
  Reporter:  Valentyn Shtronda       |      Owner:  joaquin
  <valiko.ua@…>                      |     Status:  closed
      Type:  Bugs                    |  Component:  multi_index
 Milestone:  To Be Determined        |   Severity:  Problem
   Version:  Boost 1.59.0            |   Keywords:  multi_index
Resolution:  invalid                 |  multi_index_container recursive
                                     |  modify
-------------------------------------+-------------------------------------
Changes (by joaquin):

 * status:  new => closed
 * resolution:   => invalid

Comment:

 `modify` can be used recursively if you're careful. Consider the following
 pseudocode:

 {{{
 c.modify(it,[&](element& x){
   x.data=...; // c invariant broken
   c.find(...); // undefined behavior
 });
 }}}

 When `x.data` is modified, the invariants of `c` (i.e. the sortedness of
 their indices) are potentially broken (`modify` precisely restores them,
 i.e. reindexes, after the user-provided lambda returns) so it not legal to
 call `f.find` in the following line. In your example, you break the
 invariant of `deps_map` at lines

 {{{
 88:    node_info.layer = CALCULATION_IN_PROGRESS;
 94:    node_info.layer = UNINITIALIZED;
 100:   node_info.layer = UNINITIALIZED;
 103:   node_info.layer = std::max(node_info.layer, dep_it->layer + 1);
 }}}

 88 can be seemingly dispensed with since you don't really have circular
 references; 94 and 100 aren't problematic as you return immediately after
 modification; actually, it is 103 that poses the problem, because after
 changing `node_info.layer` you continue using the container in line 91.

 The solution is to defer element modification to the very end of the user-
 provided lambda:


 {{{
 bool succeeded = deps_map.modify(it,
     [=](node_info_t& node_info)
     {
         if (node_info.deps.size() == 0)
         {
             node_info.layer = 0;
         }
         else
         {
             index_by_name_t& index_by_name = deps_map.get<by_name>();
             // following statement not needed, in the asumption there are
 no circular refs
             // node_info.layer = CALCULATION_IN_PROGRESS;
             int layer=0;
             for (const std::string& dep_name : node_info.deps)
             {
                 index_by_name_t::iterator dep_it =
 index_by_name.find(dep_name);
                 if (dep_it == deps_map.end())
                 {
                     node_info.layer = UNINITIALIZED;
                     printf("Unknown dependency.\n");
                     return;
                 }
                 if (!calc_layer(dep_it))
                 {
                     node_info.layer = UNINITIALIZED;
                     return;
                 }
                 layer = std::max(layer, dep_it->layer + 1);
             }
             node_info.layer=layer;
         }
     });
 }}}

 I've tried this and it works. Closing the ticket as a non-bug, please re-
 open if you think otherwise.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11801#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.