depfiles should be handled more intelligently during dependency cycle computation

[nico]

On IRC, someone reported that they had a cycle that was caused by an edge from a .d file. They fixed their code, but since deps are loaded before .d files are rebuilt, the cycle was still there. Here's a repro:

hummer:tmp thakis$ cat build.ninja 
rule cc
  command = clang -c $in -o $out -MMD -MF $out.d
  depfile = $out.d

rule ld
  command = clang $in -o $out

rule run_codegen
  command = ./codegen

build codegen: ld codegen.o

build codegen.o: cc codegen.cc

build header.h: run_codegen | codegen
hummer:tmp thakis$ cat codegen.cc 
#include <stdio.h>
#include "header.h"

int main() {
  FILE* f = fopen("header.h", "w");
  fclose(f);
}
hummer:tmp thakis$ cat header.h 
hummer:tmp thakis$ 
hummer:tmp thakis$ 
hummer:tmp thakis$ 
hummer:tmp thakis$ ninja
[3/3] ./codegen
hummer:tmp thakis$ ninja
ninja: no work to do.
hummer:tmp thakis$ touch codegen.cc
hummer:tmp thakis$ ninja
ninja: error: dependency cycle: header.h -> codegen -> codegen.o -> header.h
hummer:tmp thakis$ # oh shiiiiiiii
hummer:tmp thakis$ # better remove it
hummer:tmp thakis$ cat codegen.cc
#include <stdio.h>
//#include "header.h"

int main() {
  FILE* f = fopen("header.h", "w");
  fclose(f);
}
hummer:tmp thakis$ ninja
ninja: error: dependency cycle: header.h -> codegen -> codegen.o -> header.h
hummer:tmp thakis$ # d'oh! need to manually remove .d file. harder in deps mode.
hummer:tmp thakis$ rm codegen.o.d 
hummer:tmp thakis$ ninja
[3/3] ./codegen
hummer:tmp thakis$ touch codegen.cc
hummer:tmp thakis$ ninja
[3/3] ./codegen

[nico]

Maybe for edges with .d files, the .d file shouldn't be loaded if the node is already dirty due to its timestamp?

[maximuska]

This behavior will be tough to explain the manual. :)
And this won't help if the loop is more complex:

auto.h -> codegen -> codegen.c -> codegen.h -> auto.h

After removing include to auto.h from codegen.h you would wish the build to
proceed, but:

• ninja have to load deps to discover that 'codegen' should be rebuilt
  following changes in 'codegen.h'.
• if the (now dated) deps are loaded, the build fails due to the detected
  loop.

On Fri, Oct 11, 2013 at 7:04 PM, Nico Weber [email protected]:

Maybe for edges with .d files, the .d file shouldn't be loaded if the node
is already dirty due to its timestamp?

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/664#issuecomment-26149234
.

Maxim

[nico]

Oh, that's a good point!

[nico]

Another idea would be to detect this right after the .d file is written and abort the build at that point (".d file would cause dependency cycle").

[nico]

One issue with that idea might be that it could maybe lead to false positives if the dependency order between cc files flips, and the old .d file information still points the other way, and the new upstream target is built first, which adds a cycle that'd be cleaned up once the now-downstream cc is rebuilt which would remove the .d edge. Hmm, I suppose that build order can't happen since the old .d edge prevents that. Maybe it'll work if it can be made fast enough.

Another idea would be to only warn on cycles that contain edges from .d files, and remove these edges before starting the build.

[maximuska]

I think the "only warn on cycles that contain edges from .d files, and
remove these edges before starting the build" could be a good solution.
I've interpreted your idea as:

On cycle detection when building the graph ninja may:

• Try recovering by removing edges created from .d files or loaded from
  deps logs for all files involved in the cycle (we'll just need to remember
  an extra offset per node in graph to allow that) and mark all targets
  involved in cycle as dirty.
• Check if we still have the cycle then fail, else issue the warning and
  continue in hope the cycle was fixed.

That would be equivalent to user deleting stale .d files manually, except
that user could do that more intelligently, removing only the relevant .d
file(s).

P.S> I must admit that handling dependency cycles when depslog is used
becomes painful, it could be nice to have this logic in.

On Thu, Aug 28, 2014 at 6:48 PM, Nico Weber [email protected]
wrote:

One issue with that idea might be that it could maybe lead to false
positives if the dependency order between cc files flips, and the old .d
file information still points the other way, and the new upstream target is
built first, which adds a cycle that'd be cleaned up once the
now-downstream cc is rebuilt which would remove the .d edge. Hmm, I suppose
that build order can't happen since the old .d edge prevents that. Maybe
it'll work if it can be made fast enough.

Another idea would be to only warn on cycles that contain edges from .d
files, and remove these edges before starting the build.

—
Reply to this email directly or view it on GitHub
#664 (comment).

Maxim

[nico]

(looks like you replied by email, and github's email parser got confused. Here's what I think the dots should expand to, copy-pasted from "view source"

"""
On cycle detection when building the graph ninja may:

• Try recovering by removing edges created from .d files or loaded from deps logs for all files involved in the cycle (we'll just need to remember an extra offset per node in graph to allow that) and mark all targets involved in cycle as dirty.
• Check if we still have the cycle then fail, else issue the warning and continue in hope the cycle was fixed. That would be equivalent to user deleting stale .d files manually, except that user could do that more intelligently, removing only the relevant .d file(s).

P.S I must admit that handling dependency cycles when depslog is used becomes painful, it could be nice to have this logic in.
""")

[nico]

I think a similar issue happens when the outputs of depfiles isn't right:

rule cg
   depfile = d.d
   command = touch c; echo "a: b" > d.d

build c: cg b

$ ninja && ninja
ninja: error: expected depfile 'd.d' to mention 'c', got 'a'

In this case, there's no other way to recover other than removing that dep file (or, harder, that dep entry) either.