examples crash when run

[jzmaddock]

The following two examples crash at runtime:

astar_maze.cpp
kevin-bacon2.cpp

Sorry but I don't see what the issue is off hand.

[jzmaddock]

Need to add last-mod-time.cpp to this list as well (msvc-12.0).

[deinst]

astar_maze works for me (osx)
last-mod-time has problems with the stat call on osx (non fatal, but incorrect results). This would be easiest to fix by using the c++17 filesystem header, is that permissible?

[jzmaddock]

astar_maze works for me (osx)

Works for me on Ubuntu - it's just msvc where it's crashing.

Here's what I've found:

• MSVC has an "uninitialised variable guard" in debug mode and this is causing the crash, because an uninitialised value is being passed to new[].
• The problem is the value of map::m_barrier_grid.m_g.m_num_vertices.
• Prior to the call of m.solve() in main() everything is fine, but during the function call initialization, msvc debug code overwrites the stack space with it's "special" value as a guard against subsequent uninitialized reads, this leads to the value of this->m_barrier_grid.m_g.m_num_vertices to change to the "uninitialized" special value and the subsequent crash.
• Nothing else inside *this seems to be touched.
• My assumption is that something during initialization of the maze was created on the stack so that this->m_barrier_grid.m_g.m_num_vertices goes out of scope. But I don't see how.

So at this point I'm stumped.

[jzmaddock]

last-mod-time has problems with the stat call on osx (non fatal, but incorrect results). This would be easiest to fix by using the c++17 filesystem header, is that permissible?

Ooops looks like I added that one to the wrong bug report: the example uses several unix-isms which will never compile on windows. So yes, either or <boost/filesystem.hpp> would be good choices IMO.

[deinst]

astar_maze works for me (osx)

Even valgrind is not complaining, so I cannot test anything. I think llvm has similar tools to msvc, and I'll try to figure out what they are.

In the mean time, one thing that smells funny to me is the constructors of the member of maze. The initialization of m_barrier_grid calls create_barrier_grid which uses m_barriers which is initialized after barrier_grid, and so is uinititialized during the call to create_barrier_grid.

If this is the problem, then swapping lines 123 and 125 (the definitions of m_barrier_grid and m_barrier) so that m_barrier is constructed first should fix things.

[jzmaddock]

OK, there is a bug somewhere, but it's masked by some very clever named-return-value optimisations with gcc and clang. Here's what I have so far:

• During:

maze random_maze(std::size_t x, std::size_t y) {
  maze m(x, y);

The member variable m.m_barrier_grid.m_g is of type const boost::grid_graph<2,unsigned int,unsigned int>& and "points to" the first member of m which is m.m_grid.

• When the function returns, then the reference m.m_barrier_grid.m_g is left still pointing to the variable that was created inside the subroutine, and not new the copy that was returned.
• When NVRO is in effect, then the address of the variable inside random_maze is the same as the one inside main and the issue is masked. GCC and Clang it appears do this all the time (and very cleverly so), while msvc only does it as an optimisation in release mode.
• This all tracks back to filtered_graph_base which stores actually stores the reference - IMO this type should be non-copyable to prevent this type of bug (it's already non-assignable of course). I might just change it locally and see what if anything breaks.
• I wonder if there are other issues like this lurking?

[jzmaddock]

Making filtered_graph_base non-copyable breaks a lot of code - there are a lot of factory functions that create filtered_graph's. filter_graph is actually documented to store a reference and mentions that care should be taken with it's use, but that still didn't stop the authors from falling into this trap.

In the mean time I have an easy fix for astar_maze.cpp which I'll push shortly...

[jzmaddock]

Pushed fixes for astar_maze.cpp: 32bc0e1

[Becheler]

Hi !
I will be closing this issue:

• The general API problem that leds to this kind of bug is too wide and open-ended for an issue.
• both examples now run cleanly CI
• including under -fsanitize=address -O0 -fno-elide-constructors -g (the flags that defeat NRVO and would have caught the original bug).
• Commit 32bc0e1 fixed astar_maze.cpp by passing maze& into random_maze instead of returning by value
• kevin-bacon2.cpp doesn't actually involve filtered_graph and runs fine against a valid .dat.

Notes:

• astar_maze.cpp still carries an old IMPORTANT: This example appears to be broken... comment block at the top that should be removed.
• I plan on reworking old examples for non-regression purpose conjointly to Doc migration #491

It's worth preserving the pattern this issue documented, since it's easy to fall into:

class my_thing {
    Graph                       m_graph;   // owns a graph
    filtered_graph<Graph, ...>  m_view;    // a view "over" m_graph
public:
    my_thing()
      : m_graph(...)
      , m_view(m_graph, ...)   // <-- m_view stores a reference to m_graph
    {}
};

And since a copy makes non rebound of the reference, this breaks:

my_thing a;        // a.m_view's stored reference points at a.m_graph
my_thing b = a;    // b is a copy but b.m_view reference is not rebound

"Return by value" is the same problem because a return-by-value is logically a copy: the local in the function gets copied to the caller, then the local is destroyed. The returned object's view now references the dead local's m_graph member.

So in short:

• a value-type that owns a Graph member and embeds a filtered_graph (or any reference-holding adapter) over it is unsafe to copy or return by value : the adapter's stored reference will dangle.
• NRVO masks this on modern GCC/Clang almost all the time.
• Building with -fsanitize=address -fno-elide-constructors exposes the whole family of bugs in one pass.
• Maybe modern CI should use those flags ?
• Also related to this current reddit comment about BGL not respecting core guidelines, specifically : https://www.reddit.com/r/cpp_questions/comments/1oj6mi6/boost_graph_library_example_seems_to_run_afoul_of/ that triggers https://clang.llvm.org/extra/clang-tidy/checks/cppcoreguidelines/avoid-const-or-ref-data-members.html