Hi! Yep, I'm still around, though I don't post much these days :-(
To get a build graph that isn't a tree, you just need a diamond:
- A depends on B and C
- B depends on D
- C depends on D
- a.out depends on foo.o and bar.o
- foo.o depends on common.h
- bar.o depends on common.h
Note that this is a diamond whether we consider build graphs top-down (starting from the ultimate target to be built) or bottom-up (starting from the dirty files).
I can't, off the top of my head, think of a build tool that makes this error (recursive Make, possibly?), but I've certainly seen it among people writing about build tools
. The downside of making this error would be unnecessary rebuilds of clean targets, and possibly race conditions.
Cycles are rarer, but as so often with build-system weirdness, LaTeX has us covered. Suppose `paper.tex` contains cross-references ("see Equation 3.2.4 on p123"). You want to generate a compiled document, `paper.pdf`. The command to do that is `pdflatex paper.tex`, which reads `paper.tex` and `paper.aux`, and updates `paper.pdf`; but if the target of a cross-reference has changed, it will also update `paper.aux`. So you have to repeatedly run `pdflatex` until `paper.pdf` and `paper.aux` stop changing. But this is not guaranteed to happen! I believe that it is possible to construct a pathological document in which the new width of a cross-reference pushes the target to a different page, which updates the .aux file again, which causes a non-convergent build cycle; however, I can't find a reference for this right now :-(
Build cycles that provably reach a fixed point if run enough times are merely infuriating; build cycles that are not guaranteed to terminate are worse; build cycles where you couldn't even get started (which I think is what you're asking about?) would be worst of all, but fortunately I'm not aware of any examples of that - since software does ultimately get built, I think
we can rule it out as a case we need to handle. My point was really that if you assume or enforce acyclicity (which seems
like a harmless safety measure), then your tool will be unable to correctly handle builds that rely on rerunning a compiler until a fixpoint is reached, like LaTeX.
[How do existing build tools handle this? I think they either handle the fixpoint calculation properly, and accept the possibility of infinite loops, or run the compiler a bounded (or worse, fixed) number of times.]