ordered_out_edges.cpp dereferences a null iterator

[jzmaddock]

Title says it all, msvc runtime checks catch this.

[Becheler]

Hi !

It's a bit post-mortem, but here is what I understand of this issue.

The bug is a contract mismatch: BGL hands std::multiset::find a partially constructed element, and the user-provided comparator (that was defined under the standard's normal assumption that both arguments are fully-formed) dereferences a member that was never initialized.

Reproducer

I could reproduce a minimal example: See on Compiler Explorer

Compiled with -std=c++14 -O0 -fsanitize=address,undefined -g

#include <iostream>
#include <set>
#include <string>
#include <boost/graph/adjacency_list.hpp>

template <class StoredEdge>
struct order_by_name {
    bool operator()(const StoredEdge& e1, const StoredEdge& e2) const {
        return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
             < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
    }
};

struct ordered_set_by_nameS {};

namespace boost {
    template <class ValueType>
    struct container_gen<ordered_set_by_nameS, ValueType> {
        using type = std::multiset<ValueType, order_by_name<ValueType>>;
    };

    template <>
    struct parallel_edge_traits<ordered_set_by_nameS> {
        using type = allow_parallel_edge_tag;
    };
}

int main() {
    using namespace boost;
    using EdgeProperty = property<edge_name_t, std::string>;
    using Graph = adjacency_list<ordered_set_by_nameS, vecS, undirectedS,
                                 no_property, EdgeProperty>;

    Graph g;
    add_edge(0, 1, EdgeProperty("joe"),      g);
    add_edge(0, 1, EdgeProperty("chandler"), g);

    bool found;
    graph_traits<Graph>::edge_descriptor e;

    boost::tie(e, found) = edge(0, 1, g);   // <-- crash here

    std::cout << "found = " << std::boolalpha << found << "\n";
    return 0;
}

Output

Program returned: 1
Program stderr
/cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_list.h:604:55: runtime error: member call on null pointer of type 'struct _Node'
/cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_list.h:557:45: runtime error: member access within null pointer of type 'struct _List_node'
AddressSanitizer:DEADLYSIGNAL
=================================================================
==1==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000028 (pc 0x000000405631 bp 0x7ffdd6440be0 sp 0x7ffdd6440bc0 T0)
==1==The signal is caused by a READ memory access.
==1==Hint: address points to the zero page.
    #0 0x000000405631 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::size() const /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/basic_string.h:1165
    #1 0x000000407064 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::length() const /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/basic_string.h:1176
    #2 0x00000040834b in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/basic_string.h:617
    #3 0x00000041b575 in std::pair<unsigned long, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::pair<unsigned long&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, true>(unsigned long&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_pair.h:902
    #4 0x00000041966b in std::pair<std::__strip_reference_wrapper<std::decay<unsigned long&>::type>::__type, std::__strip_reference_wrapper<std::decay<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>::type>::__type> std::make_pair<unsigned long&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>(unsigned long&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_pair.h:1169
    #5 0x0000004177af in order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >::operator()(boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&) const /app/example.cpp:10
    #6 0x00000041749c in std::_Rb_tree<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, std::_Identity<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >::_M_lower_bound(std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&) const /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_tree.h:2604
    #7 0x000000415bdb in std::_Rb_tree<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, std::_Identity<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >::find(boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&) const /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_tree.h:3165
    #8 0x0000004144c6 in std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >::find(boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&) const /cefs/22/22e6cdc013c8541ce3d1548e_consolidated/compilers_c++_x86_gcc_15.1.0/include/c++/15.1.0/bits/stl_multiset.h:823
    #9 0x000000411738 in std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >::const_iterator boost::graph_detail::find_dispatch<std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >(std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > > const&, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&, boost::graph_detail::associative_container_tag) /app/boost/include/boost/pending/container_traits.hpp:644
    #10 0x00000040a5d9 in std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >::const_iterator boost::graph_detail::find<std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > >, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >(std::multiset<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> >, order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, std::allocator<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > > > const&, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&) /app/boost/include/boost/pending/container_traits.hpp:651
    #11 0x000000406411 in std::pair<boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config::edge_descriptor, bool> boost::edge<boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config, boost::undirected_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config> >(boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config::vertex_descriptor, boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config::vertex_descriptor, boost::adj_list_helper<boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config, boost::undirected_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<ordered_set_by_nameS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>, boost::vecS, ordered_set_by_nameS, boost::undirectedS, boost::no_property, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::no_property, boost::listS>::config> > const&) /app/boost/include/boost/graph/detail/adjacency_list.hpp:1650
    #12 0x0000004038a9 in main /app/example.cpp:41
    #13 0x70fcb3229d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 095c7ba148aeca81668091f718047078d57efddb)
    #14 0x70fcb3229e3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 095c7ba148aeca81668091f718047078d57efddb)
    #15 0x000000403314 in _start (/app/output.s+0x403314) (BuildId: 8e2f11bd5528004cc1f90b11a33fff88d3d178c5)

==1==Register values:
rax = 0x0000000000000020  rbx = 0x00006cfcb1100ec0  rcx = 0x00006cfcb1300a88  rdx = 0x0000000000000000  
rdi = 0x0000000000000020  rsi = 0x00006cfcb1300a88  rbp = 0x00007ffdd6440be0  rsp = 0x00007ffdd6440bc0  
 r8 = 0x0000000000000000   r9 = 0x00006cfcb10f803b  r10 = 0x00000000ffffffff  r11 = 0x0000000000000206  
r12 = 0x00000d9f962201d8  r13 = 0x00006cfcb1100f00  r14 = 0x00006cfcb1300a78  r15 = 0x00006cfcb1100ee0  
AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /app/example.cpp:10 in order_by_name<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >::operator()(boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&, boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > >, boost::property<boost::edge_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property> > const&) const
==1==ABORTING

Underlying issue

The three culprits are:

The stored_edge_iter class which get_property() member blindly dereferences m_iter without checking that the one-argument constructor actually initialized it:

graph/include/boost/graph/detail/adjacency_list.hpp

Lines 1640 to 1654 in c1f4786

	template < class Config, class Base >
	inline std::pair< typename Config::edge_descriptor, bool > edge(
	typename Config::vertex_descriptor u, typename Config::vertex_descriptor v,
	const adj_list_helper< Config, Base >& g_)
	{
	typedef typename Config::graph_type Graph;
	typedef typename Config::StoredEdge StoredEdge;
	const Graph& cg = static_cast< const Graph& >(g_);
	const typename Config::OutEdgeList& el = cg.out_edge_list(u);
	typename Config::OutEdgeList::const_iterator it
	= graph_detail::find(el, StoredEdge(v));
	return std::make_pair(typename Config::edge_descriptor(u, v,
	(it == el.end() ? 0 : &(*it).get_property())),
	(it != el.end()));
	}

The user-provided comparator reads edge properties from both arguments, which is fine under std::multiset normal contract but unsafe given how BGL constructs its lookup:

graph/example/ordered_out_edges.cpp

Lines 43 to 56 in c1f4786

	template < class StoredEdge > struct order_by_name
	{
	using first_argument_type = StoredEdge;
	using second_argument_type = StoredEdge;
	using result_type = bool;
	bool operator()(const StoredEdge& e1, const StoredEdge& e2) const
	{
	// Order by target vertex, then by name.
	// std::pair's operator< does a nice job of implementing
	// lexicographical compare on tuples.
	return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
	< std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
	}
	};

And the adjacency_list class that passes the contract breach without minding:

graph/include/boost/graph/detail/adjacency_list.hpp

Lines 344 to 364 in c1f4786

	template < class Vertex, class Iter, class Property >
	class stored_edge_iter : public stored_edge< Vertex >
	{
	public:
	typedef Property property_type;
	inline stored_edge_iter() {}
	inline stored_edge_iter(Vertex v) : stored_edge< Vertex >(v) {}
	inline stored_edge_iter(Vertex v, Iter i, void* = 0)
	: stored_edge< Vertex >(v), m_iter(i)
	{
	}
	inline Property& get_property() { return m_iter->get_property(); }
	inline const Property& get_property() const
	{
	return m_iter->get_property();
	}
	inline Iter get_iter() const { return m_iter; }
	protected:
	Iter m_iter;
	};

Going step by step:

1. BGL constructs StoredEdge(v) (alias to stored_edge_iter) singular iterator probe.StoredEdge is constructed from a vertex descriptor only, and the property is left default-constructed. The probe is well-formed structurally (target is set), but its m_iter member is singular: default-constructed and not pointing at any list node. Nothing's been dereferenced yet, so this is fine in isolation:
   

   graph/include/boost/graph/detail/adjacency_list.hpp

   Lines 1649 to 1650 in c1f4786

   	typename Config::OutEdgeList::const_iterator it
   	= graph_detail::find(el, StoredEdge(v));

2. Then graph_detail::find(el, StoredEdge(v)) is called and dispatch the find to the multiset using the comparator:

   graph/include/boost/pending/container_traits.hpp

   Lines 639 to 645 in c1f4786

   	template < class AssociativeContainer, class Value >
   	typename AssociativeContainer::const_iterator find_dispatch(
   	const AssociativeContainer& c, const Value& value,
   	associative_container_tag)
   	{
   	return c.find(value);
   	}

3. The user-provided comparator is used.

   graph/example/ordered_out_edges.cpp

   Lines 53 to 54 in c1f4786

   	return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
   	< std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));

   • Building one side is fine: A.get_target() returns 1, and get(edge_name, A) follows A.m_iter (valid) into the property list and reads the string "joe", so it results in make_pair(1, "joe"), which is fine.
   • Building the other side is where it breaks: probe.get_target() returns 1 (valid),
     • then get(edge_name, probe) is called.
       

       graph/include/boost/graph/detail/adjacency_list.hpp

       Lines 416 to 421 in c1f4786

       	template < class Tag, class Vertex, class Iter, class Property >
       	const typename property_value< Property, Tag >::type& get(Tag property_tag,
       	const detail::stored_edge_iter< Vertex, Iter, Property >& e)
       	{
       	return get_property_value(e.get_property(), property_tag);
       	}

     • then the get_property() blindly dereferences m_iter when it had been left singular by the one-arg constructor at step 1.
       

       graph/include/boost/graph/detail/adjacency_list.hpp

       Lines 356 to 359 in c1f4786

       	inline const Property& get_property() const
       	{
       	return m_iter->get_property();
       	}

     • The copy constructor of std::string is invoked on the dangling reference and leads to runtime error: reference binding to null pointer of type 'const struct basic_string'
     • get_property() returns a reference to memory through the singular m_iter. UBSan reports this immediately as reference binding to null pointer of type 'const struct basic_string'. The subsequent std::string copy constructor then attempts to actually read through that reference, which is the SEGV ASan catches.

Adjacent issues

The same probe-construction pattern appears at three other sites in adjacency_list.hpp.

• edge_range: Bug reproduced with edge_range: https://godbolt.org/z/EsTqxeTcc
  

  graph/include/boost/graph/detail/adjacency_list.hpp

  Lines 1656 to 1674 in c1f4786

  	template < class Config, class Base >
  	inline std::pair< typename Config::out_edge_iterator,
  	typename Config::out_edge_iterator >
  	edge_range(typename Config::vertex_descriptor u,
  	typename Config::vertex_descriptor v,
  	const adj_list_helper< Config, Base >& g_)
  	{
  	typedef typename Config::graph_type Graph;
  	typedef typename Config::StoredEdge StoredEdge;
  	const Graph& cg = static_cast< const Graph& >(g_);
  	Graph& g = const_cast< Graph& >(cg);
  	typedef typename Config::out_edge_iterator out_edge_iterator;
  	typename Config::OutEdgeList& el = g.out_edge_list(u);
  	typename Config::OutEdgeList::iterator first, last;
  	typename Config::EdgeContainer fake_edge_container;
  	boost::tie(first, last) = graph_detail::equal_range(el, StoredEdge(v));
  	return std::make_pair(
  	out_edge_iterator(first, u), out_edge_iterator(last, u));
  	}

• rease_from_incidence_list:

  graph/include/boost/graph/detail/adjacency_list.hpp

  Lines 116 to 122 in c1f4786

  	template < class EdgeList, class vertex_descriptor >
  	void erase_from_incidence_list(
  	EdgeList& el, vertex_descriptor v, disallow_parallel_edge_tag)
  	{
  	typedef typename EdgeList::value_type StoredEdge;
  	el.erase(StoredEdge(v));
  	}

• remove_edge_and_property:

  graph/include/boost/graph/detail/adjacency_list.hpp

  Lines 866 to 880 in c1f4786

  	template < class Graph, class EdgeList, class Vertex >
  	inline void remove_edge_and_property(
  	Graph& g, EdgeList& el, Vertex v, boost::disallow_parallel_edge_tag)
  	{
  	typedef typename Graph::global_edgelist_selector EdgeListS;
  	BOOST_STATIC_ASSERT((!is_same< EdgeListS, vecS >::value));
  	typedef typename EdgeList::value_type StoredEdge;
  	typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
  	if (i != end)
  	{
  	g.m_edges.erase((*i).get_iter());
  	el.erase(i);
  	}
  	}

The two remove_edge sites are only instantiated when parallel_edge_traits is disallow_parallel_edge_tag,

Proposed solution

There are different levels of fix.

1. Do nothing: we are already here:
   • the example is commented in the Jamfile
     

     graph/example/Jamfile.v2

     Lines 230 to 232 in c1f4786

     	# This one dereferences a null-iterator:
     	#
     	# run ordered_out_edges.cpp ;

   • there is a warning comment in it:
     

     graph/example/ordered_out_edges.cpp

     Lines 10 to 17 in c1f4786

     	/*
     	IMPORTANT:
     	~~~~~~~~~~
     	This example appears to be broken and crashes at runtime, see
     	https://github.com/boostorg/graph/issues/149
     	*/

2. Fix the documentation: the faulty example file should not appear, the design pattern should not be advertised (it currently is). This is concretely what Doc migration #491 doc migration PR is doing, and merging it would close this issue.
3. Remove the dangerous constructor stored_edge_iter(Vertex v) so BGL can no longer manufacture a singular probe. Use std::is_transparent instead. That could be done with:

namespace boost::graph_detail {

// for BGL internals
template <class Vertex> struct target_lookup { Vertex target;  };

// for users
template <class Vertex, class PropertyKey>
struct target_property_lookup {
    Vertex      target;
    PropertyKey property_key;
};

}  // namespace boost::graph_detail

And then

template <class StoredEdge>
struct order_by_name {
    using is_transparent = void;

    // Stored-vs-stored (maintains tree order)
    bool operator()(const StoredEdge& a, const StoredEdge& b) const {
        return std::make_pair(a.get_target(), boost::get(boost::edge_name, a))
             < std::make_pair(b.get_target(), boost::get(boost::edge_name, b));
    }

    // Target-only key used by BGL internals: edge(), edge_range(), ...
    template <class Vertex>
    bool operator()(const boost::graph_detail::target_lookup<Vertex>& k, const StoredEdge& e) const {
        return k.target < e.get_target();
    }
    template <class Vertex>
    bool operator()(const StoredEdge& e, const boost::graph_detail::target_lookup<Vertex>& k) const {
        return e.get_target() < k.target;
    }

    // (target, name) key (used by the user).
    template <class Vertex>
    bool operator()(const boost::graph_detail::target_property_lookup<Vertex, std::string>& k, const StoredEdge& e) const {
        return std::make_pair(k.target, k.property_key) < std::make_pair(e.get_target(), boost::get(boost::edge_name, e));
    }
    template <class Vertex>
    bool operator()(const StoredEdge& e, const boost::graph_detail::target_property_lookup<Vertex, std::string>& k) const {
        return std::make_pair(e.get_target(), boost::get(boost::edge_name, e)) < std::make_pair(k.target, k.property_key);
    }
};

We could figure out how to reduce the boilerplate. We could avoid breaking existing comparators with stuff like:

if constexpr (is_transparent_comparator_v<typename OutEdgeList::key_compare>) {
    it = graph_detail::find(el, edge_lookup_key<vertex_descriptor>{v});
} else {
    it = graph_detail::find(el, StoredEdge(v));   // legacy path
}