On Mon, 13 Nov 2006, David Laight wrote:
> make(1) was recently 'updated' to implement a recursive check in the .WAIT
> code [...]
> The problem is that this was implemented by scanning the tree to
> add normal dependencies for all the child nodes (eg c1) against
> all the nodes to the left of the .WAIT.  For certain makefiles (eg
> src/tools/Makefile) this generates a considerable number of dependency
> checks - over 1000000.

I plead guilty.  My excuse is that the previous code already marked all
nodes to the right of the .WAIT as successors of all nodes to the left
of the .WAIT.

> I've modified make and completly reworked the way that jobs are scheduled
> so that both .WAIT and .ORDER recursively apply, but without requiring
> more than a simple 'visit each node once' scan of the tree to set it up.

This all looks much the same as I would have redesigned it, which
is not necessarily a good thing.

> I've implemented .ORDER by checking the order predecessors at the
> time a node is removed from the work list, if any are unmade (and
> need to be made) then the node isn't build, and its children aren't
> added.  When one of the predecessor nodes gets build, the dropped (now
> successor) node is rechecked.
> 
> This has the side effect that:
>     a: b
>     .ORDER b a
> is a deadlock - which might not, at first glance, be invalid syntax.

It would be nice it this worked.  Does your version still give each node
a list of ancestors?  If so, then when 'a' gets to the front of the work
list, and we notice that it has 'b' as an un-made .ORDER predecessor,
we could immediately check whether 'a' is an ancestor of 'b', and if so
then don't let the presence of the .ORDER cause a deadlock.

--apb (Alan Barrett)