Segfault for remove_vertex with adjacency_list<boost::setS, ...>

[lmondada]

Bug description

Removing a vertex in an adjacency_list graph produces an invalid read when the following conditions are met

• the edge storage OutEdgeList is setS or hash_setS
• the vertex storage VertexList is vecS
• a source or target of an edge in the graph has index larger than the vertex index being deleted

Reproducing MWE

The following code:

#include <boost/graph/adjacency_list.hpp>

using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>;

int main() {
  while (true) {
    Graph g(3);
    boost::add_edge(2, 0, g);
    boost::remove_vertex(1, g);
  }
}

On MacOS Big Sur, this results in a segfault in roughly 1/1000 iterations. This could be reproduced both with AppleClang 12.0.5.12050022 and LLVM Clang 12.0.0. On Linux with gcc, no segfault was observed but the memory corruption can be observed in Valgrind (see output).

Proposed fix

Reverting commit 5dd748307cc35e8 seems to fix the issue. The issue seems to come from incrementing an invalid iterator after a change to the original container.

[avdg81]

Hello all, I am facing the exact same issue as the one reported here. Just curious to know what the current status is? It seems that the underlying problem is well understood, and a possible solution has been suggested. Is it expected that it will be solved any time soon, or are there other problems (that I am not aware of) that block its resolution? Any feedback is greatly appreciated. Thanks.

[jeremy-murphy]

This will be a priority to fix once the CI is fixed.

[jeremy-murphy]

The fix is now on develop; please test and re-open this bug report if the problem remains. Thanks everyone!