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-20 07:21:12

#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
-------------------------------------+-------------------------------------

Comment (by joaquin):

 ''Please confirm that my understanding is correct: the problem occurs
 because during reindexing modify() assumes that only *it element is
 changed, so it does not perform full sort (for performance reasons). If
 I'm correct, I would mention this in the documentation of modify().''

 Exactly, `modify(it,mod)` does only (possibly) relocate the element
 pointed to by `it`. In fact this is stated
 [http://www.boost.org/libs/multi_index/doc/reference/ord_indices.html#modify

 in the docs]:

 '''''Effects:''' Calls `mod(e)` where `e` is the element pointed to by
 `position` and rearranges `*position` into all the indices of the
 `multi_index_container` [...]''

 As for how to document permissibly operations within `mod(e)`, the
 (unstated) assumption is that the container is not messed with in any
 manner, and I'm very reluctant to provide extra guarantees beyond this. A
 safe compromise would be to add something like this in the '''Requires'''
 clause:

 ''`mod(e)` does not invoke any operation of the `multi_index_container`
 except possibly only before `e` is directly modified, and only as long as
 `position` is not rendered invalid.''

 Does this sound sufficiently clear and unscary? By the way this makes the
 `reindex` trick legally invalid, but your code could be very easily
 rewritten to conform:

 {{{
 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>();
             index_by_name.modify(it,[](node_info_t& node_info_alias){
                 node_info_alias.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;
         }
     });
 }}}

 The key here is the qualifier ''directly'' in "before `e` is directly
 modified": you can change `e` indirectly through a recursive call to
 `modify`, as done in

 {{{
 index_by_name.modify(it,[](node_info_t& node_info_alias){
     node_info_alias.layer = CALCULATION_IN_PROGRESS;
 });
 }}}

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