make handling of prerequisites that interlock?

[Ben Pfaff]

I'm having some trouble with a set of dependencies that
indirectly depend on a common file.  Here's a minimal makefile
that demonstrates the problem:

----------------------------------------------------------------------
a: c b
        cat $^ > $@

b: c d
        cat $^ > $@

c: x
        cat $^ > $@

clean:
        rm -f a b c

# Turn off implicit rules to make `make -d' output easier to read.
.SUFFIXES:
%: %,v
%: RCS/%,v
%: RCS/%
%: s.%
%: SCCS/s.%
----------------------------------------------------------------------

When I run this in a tight loop, as with

    rm -f foo
    touch x d
    while ! grep newer foo; do 
        make clean > /dev/null
        make > /dev/null
        echo x > x
        make -d > foo
    done

it typically iterates for a few seconds (with most iterations not
seeing any change in file times, presumably because everything
happens too fast), and then stops with this output in foo:

----------------------------------------------------------------------
Considering target file `a'.
  Considering target file `c'.
    Considering target file `x'.
     Looking for an implicit rule for `x'.
     No implicit rule found for `x'.
     Finished prerequisites of target file `x'.
    No need to remake target `x'.
   Finished prerequisites of target file `c'.
   Prerequisite `x' is newer than target `c'.
  Must remake target `c'.
cat x > c
Putting child 0x08072260 (c) PID 5270 on the chain.
Live child 0x08072260 (c) PID 5270 
Reaping winning child 0x08072260 PID 5270 
Removing child 0x08072260 PID 5270 from chain.
  Successfully remade target file `c'.
  Considering target file `b'.
    Pruning file `c'.
    Considering target file `d'.
     Looking for an implicit rule for `d'.
     No implicit rule found for `d'.
     Finished prerequisites of target file `d'.
    No need to remake target `d'.
   Finished prerequisites of target file `b'.
   Prerequisite `c' is newer than target `b'.
   Prerequisite `d' is older than target `b'.
  Must remake target `b'.
cat c d > b
Putting child 0x08072350 (b) PID 5272 on the chain.
Live child 0x08072350 (b) PID 5272 
Reaping winning child 0x08072350 PID 5272 
Removing child 0x08072350 PID 5272 from chain.
  Successfully remade target file `b'.
 Finished prerequisites of target file `a'.
 Prerequisite `c' is newer than target `a'.       <---- 1
 Prerequisite `b' is newer than target `a'.       <---- 2
No need to remake target `a'.                     <---- 3
----------------------------------------------------------------------

So here's the part I don't understand.  make realizes that c
needs to be remade, so it remakes it, and similarly for b.  It
also realizes that `c' is newer than `a' (line 1 above) and `b'
is newer than `a' (line 2 above).  But then it concludes somehow
that `a' does not need to be remade (line 3 above).  I cannot
follow this logic.  What am I missing?

(Is this a bug in my Makefile?  If it is, how can I fix my
Makefile?)

This occurs with both my system's version of GNU make (Debian
3.80-9) and a copy of 3.81beta2 that I separately compiled.  My
system is Debian "unstable" running on a 1.8 GHz Pentium 4 M
laptop, using a Linux 2.6 kernel and an ext3 file system.

Thanks,

Ben.
-- 
Ben Pfaff 
email: address@hidden
web: http://benpfaff.org