Let DependencyScan::RecomputeDirty() work correclty with cyclic graphs.

RecomputDirty(edge) currently works roughly like this:

      RecomputeDirty(edge):
        LoadDeps(edge)
        for in in edge.inputs:
          if in.StatIfNecessary():
            RecomputeDirty(in.in_edge)  # recurse into inputs
        for out in edge.outputs:
          out.StatIfNecessary()  # mark outputs as visited

It uses the stat state of each node to mark nodes as visited and doesn't
traverse across nodes that have been visited already.  For cyclic graphs
with an edge with multiple outputs on the cycle, nothing prevents an
edge to be visited more than once if the cycle is entered through an
output that isn't on the cycle.  In other words, RecomputeDirty() for
the same edge can be on the call stack more than once.  This is bad for
at least two reasons:

  1. Deps are added multiple times, making the graph confusing to reason
     about.

  2.  LoadDeps() will insert into the inputs_ of an edge that's iterated
      over in a callframe higher up. This can invalidate the iterator,
      which causes a crash when the callframe with the loop over the
      now-invalidated iterator resumes.

To fix this, let RecomputeDirty() mark all outputs of an edge as visited
as the first thing it does.  This way, even if the edge is on a cycle
with several outputs, each output is already marked and no edge will
have its deps loaded more than once.

Fixes the crashes in #875.  (In practice, it turns the crashes into
"stuck [this is a bug]" messages for now, due to the example without
duplicate rules in #867)

0 files changed, 0 insertions, 0 deletions