Ticket #11801: DirectedGraph.cpp

// Please use attached simplified file to reproduce the problem.
// I used boost 1.59 with VS2015.
// Reproduced in all 4 configurations (debug/release, x86/x64).
// I'm not sure if it's a bug or limitation of multi_index, but commenting any line in fill_test_date() fixes the problem, so seems like a bug in some specific conditions.
// If it's multi_index limitation, please mention this in description of modify/modify_key.
//
// The problem:
// multi_index container has two keys ordered_unique and ordered_non_unique.
// In calc_layer() I call modify() on first index and change the key of second index.
// During calculation of new key for second index, other recursive calls to modify() may be performed.
// All calls to modify() return true but in some cases second index is not correctly ordered in we see message "WRONG SORT ORDER BY LAYER".

#include <set>
#include <string>
#include <boost/algorithm/string.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>

namespace mi = ::boost::multi_index;

#define UNINITIALIZED           -1
#define CALCULATION_IN_PROGRESS -2

struct node_info_t
{
    node_info_t(const std::string& name)
    : name(name)
    , layer(UNINITIALIZED)
    {
    }

    std::string name;
    std::set<std::string> deps;
    int layer;
};

struct by_name {};
struct by_layer {};

typedef mi::multi_index_container<
    node_info_t,
    mi::indexed_by<
        mi::ordered_unique    <mi::tag<by_name >, mi::member<node_info_t, std::string, &node_info_t::name> >,
        mi::ordered_non_unique<mi::tag<by_layer>, mi::member<node_info_t, int,         &node_info_t::layer> >
    >
> node_deps_map_t;

typedef node_deps_map_t::index<by_name >::type index_by_name_t;
typedef node_deps_map_t::index<by_layer>::type index_by_layer_t;

node_deps_map_t deps_map;

void add_node(const char* node_name, const char* node_deps_string)
{
    auto res = deps_map.emplace(node_name);
    if (!res.second)
    {
        printf("Already inserted.\n");
    }
    else if (*node_deps_string)
    {
        deps_map.modify(res.first,
            [=](node_info_t& node_info)
            {
                boost::split(node_info.deps, node_deps_string, boost::is_any_of(" "), boost::algorithm::token_compress_on);
            });
    }
}

bool calc_layer(index_by_name_t::iterator it)
{
    if (it->layer == CALCULATION_IN_PROGRESS)
        return printf("Circular reference.\n"), false;
    if (it->layer != UNINITIALIZED)
        return true;

    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>();
                node_info.layer = CALCULATION_IN_PROGRESS;
                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;
                    }
                    node_info.layer = std::max(node_info.layer, dep_it->layer + 1);
                }
            }
        });

    if (!succeeded)
        return printf("modify() failed.\n"), false;

    return it->layer >= 0;
}

void fill_test_data()
{
    add_node("m1", "");
    add_node("b1", "");
    add_node("o1", "");
    add_node("a3", "");
    add_node("t1", "");
    add_node("m2", "");
    add_node("c1", "b1");
    add_node("r1", "b1");
    add_node("t2", "b1");
    add_node("o2", "b1");
    add_node("h1", "b1");
    add_node("h2", "b1");
    add_node("d1", "b1");
    add_node("x1", "b1");
    add_node("h3", "b1");
    add_node("m3", "b1");
    add_node("l1", "b1 c1");
    add_node("w1", "b1 c1");
    add_node("g1", "b1 t2");
    add_node("s1", "b1 r1");
    add_node("s2", "b1 r1 t2 l1 d1 o2 m1");
    add_node("a6", "b1 s2");
    add_node("m4", "b1 s2 o2");
    add_node("a4", "b1 s2 o2 l1");
    add_node("w2", "b1 s2 c1 w1");
    add_node("s3", "b1 s2 o2 h2");
    add_node("s4", "b1 s2 o2 h2 t2");
    add_node("a5", "b1 s2 d1 r1 w1");
    add_node("g2", "b1 s2 r1 c1 l1");
    add_node("b2", "b1 s2 r1 d1 a5");
    add_node("s5", "b1 s2 r1");
    add_node("w3", "b1 x1");
    add_node("m5", "b1 s2");
    add_node("m6", "b1 s2 o2 m4");
    add_node("m7", "b1 s2");
    add_node("n1", "b1 s2 l1");
    add_node("p1", "b1 s2 l1 x1");
    add_node("s6", "b1 s2 l1 g1 t2");
    add_node("c2", "b1 s2 o2 m4");
    add_node("c3", "b1 s2 l1 o2 w1 m5");
    add_node("c4", "b1 s2 l1 g1 t2");
    add_node("d2", "b1 s2 l1 o2");
    add_node("a1", "b1 s2 t2 g1 a4 a6 t1 m2 a3 d1 s1 o1 a5 b2 w1 l1");
    add_node("a2", "b1 s2 t2 g1 a4 a6 t1 m2 r1 a3 d1 b2 s3 s4 o2 s1 o1 a5 w1 l1 c1");
}

int main(int, char*[])
{
    fill_test_data();

    for (auto it = deps_map.begin(); it != deps_map.end(); ++it)
    {
        calc_layer(it);
    }

    index_by_layer_t& index_by_layer = deps_map.get<by_layer>();
    if (!std::is_sorted(index_by_layer.begin(), index_by_layer.end(),
            [](const node_info_t& l, const node_info_t& r) { return l.layer < r.layer; }))
        printf("\nWRONG SORT ORDER BY LAYER\n");

    return 0;
}