toolchain/49086: make(1): many problems with dependency handling

[Jarmo Jaakkola <jarmo.jaakkola%roskakori.fi@localhost>]

>Number:         49086
>Category:       toolchain
>Synopsis:       suffix rules broken in many ways, also other problems.
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    toolchain-manager
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Aug 07 16:15:00 +0000 2014
>Originator:     Jarmo Jaakkola <jarmo.jaakkola%roskakori.fi@localhost>
>Release:        NetBSD 6.1.2_PATCH
>Organization:
>Environment:
System: NetBSD kotoisa.roskakori.fi 6.1.2_PATCH NetBSD 6.1.2_PATCH (KOTOISA) 
#5: Mon Jan 20 17:01:44 EET 2014 
jammuli%kotoisa.roskakori.fi@localhost:/usr/src/sys/arch/amd64/compile/KOTOISA 
amd64
Architecture: x86_64
Machine: amd64
>Description:

I have found multiple bugs in make(1) related to handling of dependency
information, especially in relation to suffix transformation rules.
I list all of the issues here instead of making multiple PRs as I have
prepared an extensive patch to fix them all in one go.  Here is a quick
rundown of issues:

Issue 1: explicit rules for lib(member) targets do not work properly
Issue 2: POSIX .s1.a transformations do not work
Issue 3: single suffix rules remain active after .SUFFIXES is cleared
Issue 4: suffix rules do not become regular rules when .SUFFIXES is cleared
Issue 5: adding more suffixes does not make existing rules into suffix rules
Issue 6: transformation search can end up in an infinite loop
Issue 7: using the .NULL special target breaks single suffix rules
Issue 8: implicit/explicit sources from suffix rules are added to all targets
Issue 9: the value of $(*) sometimes does not contain the directory part
Issue 10: explicit dependencies affect transformation rule selection
Issue 11: sources from transformation rules are expanded incorrectly
Issue 12: if a rule is defined multiple times, the first one is used

At least issues 1, 2, 3, 4, 8 and 10 affect POSIX specified features.

I will submit a patch as a follow-up.



Issue 1: explicit rules for lib(member) targets do not work properly
========

Dependency on 'member' is always added, even if not specified
in the makefile.  The value of $(@) (.TARGET) is incorrect, as
according to POSIX it should be 'lib', not 'member'.

From POSIX:
    For the lib(member.o) expression lib refers to the name of the
    archive library and member.o to the member name. The application
    shall ensure that the member is an object file with the .o suffix.

And:
    For the target lib(member.o) and the s2.a rule, the internal macros
    shall be defined as:
    [...]
    $@
        lib

--<Start>---------------------------------------------------------------
$ cat >Makefile1 <<EOF
lib: lib(foo.o)
        ar -s \$(@)

#          This prevents triggering another bug, see PR 49085 issue 4.
#             v
lib(foo.o) happynow: foo.c
        cc -c -o \$(%) foo.c
        ar -rc \$(@) \$(%)
        rm -f \$(%)

foo.c:
        echo 'int foo = 1;' >\$(@)

#foo.o: foo.c
#       @echo Incorrect!
#       cc -c -o \$(@) \$(?)

# Expected:
# echo 'int foo = 1;' >foo.c
# cc -c -o foo.o foo.c
# ar -rc lib foo.o
# rm -f foo.o
# ar -s lib
EOF
$ make -rf Makefile1
echo 'int foo = 1;' >foo.c
make: don't know how to make foo.o. Stop

make: stopped in /some/dir
--<End>-----------------------------------------------------------------

Note that there's nothing in the makefile that should cause make to try
to build foo.o.  Let's placate make and activate the commented out rule
for foo.o and then try again.

--<Start>---------------------------------------------------------------
$ $EDITOR Makefile1 # Uncomment the foo.o rule.
$ rm -f lib* foo*; make -rf Makefile1
echo 'int foo = 1;' >\$(@)
Incorrect!
cc -c -o foo.o foo.c
cc -c -o foo.o foo.c
ar -rc foo.o foo.o
ar: foo.o: File format not recognized
*** Error code 1

Stop.
make: stopped in /some/dir
--<End>-----------------------------------------------------------------

Sure enough, an unspecified dependency is definitely added on the archive
member and this results in the execution of a rule that should not run.
The file format error occurs because $(@) is 'foo.o' instead of 'lib'
in the archive member rule.

The problem is that the SuffFindArchiveDeps() function in suff.c does
not try to find an explicit rule for lib(member) but immediately creates
a dependency node for member and then tries to build that one with
the assumption that there will then be a transformation rule from
member's suffix to the library's suffix.  The $(@) variable is wrong,
because it is copied from the node that shouldn't have been created in
the first place.



Issue 2: POSIX .s1.a transformations do not work
========

According to POSIX:
    The application shall ensure that the member is an object file with
    the .o suffix.  [...]  The .a suffix shall refer to an archive
    library. The .s2.a rule shall be used to update a member in the
    library from a file with a suffix .s2.

--<Start>---------------------------------------------------------------
$ cat >Makefile2 <<EOF
.SUFFIXES: .c .a
.c.a:
        cc -c -o \$(%) \$(<)
        ar -rc \$(@) \$(%)
        rm -f \$(%)

#.SUFFIXES: .o
#.o.a:
#       @echo Even more incorrect! \$(@)
#       ar -rc \$(@) \$(%)

#lib.a: lib.a(foo.o)
lib: lib(foo.o)
        ar -s \$(@)

#foo.o: foo.c
#       @echo Incorrect!
#       cc -c -o \$(@) \$(@:.o=.c)

foo.c:
        echo 'int foo = 1;' >\$(@)

# Expected: see Makefile1
EOF
$ make -rf Makefile2
make: don't know how to make foo.o. Stop

make: stopped in /some/dir
--<End>-----------------------------------------------------------------

Not too surprising.  We've already established the obsession with
'member.o'.  Let's try again with the rule for 'foo.o' uncommented.

--<Start>---------------------------------------------------------------
$ $EDITOR Makefile2 # Uncomment the foo.o rule.
$ rm -f lib* foo*; make -rf Makefile2
echo 'int foo = 1;' >foo.c
Incorrect!
cc -c -o foo.o foo.c
ar -s lib
ar: 'lib': No such file
*** Error code 1

Stop.
make: stopped in /some/dir
--<End>-----------------------------------------------------------------

Yet again providing a rule for foo.o results in the wrong commands being
run.  Interestingly, the only rule (.c.a) that could actually make the
lib(foo.o) target up-to-date is /not/ run, yet lib(foo.o) becomes
up-to-date as is evidenced by the rule for lib being executed.

One more time.  This time we'll have .o.a transformation too, and add
the .a suffix to lib.

--<Start>---------------------------------------------------------------
$ $EDITOR Makefile2 # Uncomment .o.a, use lib.a instead of lib
$ rm -f lib* foo*; make -rf Makefile2
echo 'int foo = 1;' >foo.c
Incorrect!
cc -c -o foo.o foo.c
ar -s lib.a
ar: 'lib.a': No such file
*** Error code 1

Stop.
make: stopped in /some/dir
$ make -rf Makefile2
Even more incorrect! foo.o
ar -rc foo.o foo.o
ar: foo.o: File format not recognized
*** Error code 1

Stop.
make: stopped in /some/dir
--<End>-----------------------------------------------------------------

The first run is identical to second example.  The surprise comes from
the second run, because it executes the .o.a transformation that it
did not execute on the first run because now foo.o exists.  The value of
$(@) is also incorrect in the .o.a rule.

This issue is caused by suff.c:SuffFindArchiveDeps() too.  It does not try
the POSIX inference semantics at all.  To be exact, it actually can't get
anything inferred, if the lib does not have a known suffix.
(Oddly enough, POSIX does not require a suffix on lib)



Issue 3: single suffix rules remain active after .SUFFIXES is cleared
========

After the list of known suffixes is cleared, old single suffix rules still
work.  Even when no suffixes are re-added.

--<Start>---------------------------------------------------------------
$ cat >Makefile3 <<EOF
.SUFFIXES: .a
.a:
        @echo '"\$(@)" "\$(<)"'
test.a:
.SUFFIXES:
# Expected:
# make: don't know how to make test. Stop
#
# make: stopped in /some/dir
EOF
$ make -rf Makefile3 test
"test" "test.a"
--<End>-----------------------------------------------------------------

This issue exists because suff.c:Suff_ClearSuffixes() does not clear
the children list of emptySuff.



Issue 4: suffix rules do not become regular rules when .SUFFIXES is cleared
========

It could be debated if a currently active suffix rule ".x.y" should
simultaneously work as a rule for a regular file named ".x.y" (I say: why
not, there's no harm in it).  There is however no question if the rule
should work as a regular when either or both of ".x" and ".y" are not
currently known suffixes.

--<Start>---------------------------------------------------------------
$ cat >Makefile4 <<EOF
.SUFFIXES: .x .y
.x.y:
        @echo .x.y
.SUFFIXES:
# Expected:
# .x.y
EOF
$ make -rf Makefile4
make: no target to make.

make: stopped in /some/dir
$ make -rf Makefile4 .x.y
make: don't know how to make .x.y. Stop

make: stopped in /some/dir
--<End>-----------------------------------------------------------------

This happens because the node for a suffix rule is not inserted into
the target graph when it is created, it is only stored in suff.c:transforms.
When the suffixes are cleared, they're not moved into the target graph.
Because .x.y is the first rule in the makefile, it should also become
the default target, when either of both of .x or .y is no longer known.



Issue 5: adding more suffixes does not make existing rules into suffix rules
========

When adding new known suffixes, scanning the list of currently defined
rules for any that could be made into suffix rules is a nice feature
to have.  And by the existance of suff.c:SuffScanTargets(), this has been
tought of before.  Too bad the function does not work at all.

--<Start>---------------------------------------------------------------
$ cat >Makefile5 <<EOF
.SUFFIXES: .x
.x.y:
        @echo '\$(<) -> \$(@)'
.z.x:
        @echo '\$(<) -> \$(@)'
.y:
        @echo '\$(<) -> \$(@)'
test1.x:
test2.z:
test3.y:
.SUFFIXES: .y .z
# Expected:
# test1.x -> test1.y
# test2.z -> test2.x
# test3.y -> test3
EOF
$ make -krf Makefile5 test1.y test2.x test3
make: don't know how to make test1.y (continuing)
make: don't know how to make test2.x (continuing)
make: don't know how to make test3 (continuing)


Stop.
make: stopped in /some/dir
--<End>-----------------------------------------------------------------

There's actually two problems in the function related to this issue.
They both come nicely apparent when parsing and suffix rule debugging
is used.  The following is printed:

    ParseReadLine (11): '.SUFFIXES: .y .z'
    ParseDoDependency(.SUFFIXES: .y .z)
    defining transformation from `.x' to `.y'
    inserting .x(1)...at end of list
    inserting .y(2)...at end of list
    Wildcard expanding "test1.y"...suffix is ".y"...SuffFindDeps (test1.y)
            trying test1.x...got it
    Wildcard expanding "test2.x"...suffix is ".x"...SuffFindDeps (test2.x)
    Wildcard expanding "test3"...SuffFindDeps (test3)
            No known suffix on test3. Using .NULL suffix
    adding suffix rules

While this would be expected (missing lines pointed out):

    ParseReadLine (11): '.SUFFIXES: .y .z'
    ParseDoDependency(.SUFFIXES: .y .z)
    defining transformation from `.x' to `.y'
    inserting .x(1)...at end of list
    inserting .y(2)...at end of list
->  defining transformation from `.z' to `.x'
->  inserting .z(3)...at end of list
->  inserting .x(1)...at end of list
->  defining transformation from `.y' to `'
->  inserting .y(2)...at end of list
->  inserting (0)...at end of list
    Wildcard expanding "test1.y"...suffix is ".y"...SuffFindDeps (test1.y)
            trying test1.x...got it
=>          applying .x -> .y to "test1.y"
    Wildcard expanding "test2.x"...suffix is ".x"...SuffFindDeps (test2.x)
->          trying test2.z...got it
->          applying .z -> .x to "test2.x"
    Wildcard expanding "test3"...SuffFindDeps (test3)
            No known suffix on test3. Using .NULL suffix
    adding suffix rules
->          trying test3.y...got it
->          applying .y ->  to "test3"


Lines marked by "->" are missing because SuffScanTargets() explicitly
exits if the new suffix matches at the start of the target name, thus
ignoring all rules where the new suffix is the source.  The line marked
by "=>" is missing because the two suffixes are only linked together in
SuffScanTargets() and the related target node in the graph is marked as
being a transformation node, but the transformation is not recorded in
suff.c:transforms!  Another problem caused by transformation nodes being
segregated from the general target population (see Issue 4).



Issue 6: transformation search can end up in an infinite loop
========

If there are rules to make two types of files from each other, neither
of which exists, and a third rule for making another file from one or
another of those types of file, the transformation lookup will end up
in an infinite loop.

--<Start>---------------------------------------------------------------
$ cat >Makefile6 <<EOF
.SUFFIXES: .x .y .z
.x.y:
        irrelevant
.y.x:
        irrelevant
.x.z:
        irrelevant
# Expected:
# make don't know how to make test.z. Stop
#
# make: stopped in /some/dir
EOF
$ make -rf Makefile6 test.z  # You'll need to kill this stuck process
--<End>-----------------------------------------------------------------

This happens because suff.c:SuffFindThem() does not check whether
the transformation it's going to add already exists in the chain it's
creating.



Issue 7: using the .NULL special target breaks single suffix rules
========

The make implementation includes an undocumented (in the man page) .NULL
special target, whose exact purpose escapes me.  This I found from
"PMake - A tutorial":

    One final question remains: what does PMake do with targets that
    have no known suffix? PMake simply pretends it actually has a known
    suffix and searches for transformations accordingly.  The suffix it
    chooses is the source for the .NULL target mentioned later.

So the feature looks like a weirdly limited version of single suffix
transformation rules.

--<Start>---------------------------------------------------------------
$ cat >Makefile7 <<EOF
.SUFFIXES: .x .y .z
.x.y:
        @echo '\$(<) -> \$(@)'
.z:
        @echo '\$(<) -> \$(@)'
test1.x:
test1.z:
test2.z:
.NULL: .y
# Expected:
# test1.z -> test1
# test2.z -> test2
EOF
$ make -rf Makefile7 test1 test2
test1.x -> test1
make: don't know how to make test2. Stop

make: stopped in /some/dir
--<End>-----------------------------------------------------------------

This issue occurs because suff.c:SuffParseTransform() uses suffNull
instead of emptySuff.

Also, I think that the whole feature is obsolete because of the POSIX
standardized single suffix rules.  Perhaps in the past this feature had
a use, but I cannot see what purpose it now serves.



Issue 8: implicit/explicit sources from suffix rules are added to all targets
========

This version of make allows the makefile to specify dependencies for
transformation rule.  These dependencies should then be applied to all
targets that use the transformation rule.  Instead they get applied
along with the implied source also on targets which could use
the transformation rule but actually don't.  This is against POSIX:

    When no target rule is found to update a target, the inference
    rules shall be checked.

This implies that an explicit rule should always take precedence over
any inferred ones.

(Duplicate of PR toolchain/5370)

--<Start>---------------------------------------------------------------
$ cat >Makefile8 <<EOF
.SUFFIXES: .a .b .x .y
.a.b:
        irrelevant
.x.y: foo
        irrelevant
test1.b: test1.c
        @echo '"\$(?)"'
test2.y: test2.z
        @echo '"\$(?)"'
test1.a test1.c test2.x test2.z foo:
# Expected:
# "test1.c"
# "test2.z"
EOF
$ make -rf Makefile8 test1.b test2.y
"test1.c test1.a"
"test2.z test2.x foo"
--<End>-----------------------------------------------------------------

Strictly speaking suffix rules with dependencies are not POSIX
conformant so standard-wise the behavior for those rules is OK even if
it is extremely counter-intuitive.  The output however shows that
the problem exists with standard rules also and a dependency can get
added on the implied source even when the inference rule is not used.

This issue is caused by suff.c:SuffFindNormalDeps() /not/ skipping
transformation rule search if the target has an explicit rule.
The search is always done and the inferred dependencies added.  Only if
it is later discovered that the target already has commands,
the inferred commands are not used, but the dependencies are left
in place.



Issue 9: the value of $(*) sometimes does not contain the directory part
========

The value of $(*) (.PREFIX) loses the directory part of the target name
when the target file exists and no transformation rule is applied.
Otherwise the directory part is retained.

--<Start>---------------------------------------------------------------
$ cat >Makefile9 <<EOF
.SUFFIXES: .a .c .d
abc/foo.a: abc/foo.b abc/foo.d
        @echo 'foo.a: "\$(*)"'
abc/foo.b: FORCE
        @echo 'foo.b: "\$(*)"'
abc/foo.c: FORCE
        @echo 'foo.c: "\$(*)"'
.c.d: FORCE
        @echo '.d.c: "\$(*)"'
FORCE:
# Expected:
# foo.b: "abc/foo.b"
# foo.c: "abc/foo"
# .d.c: "abc/foo"
# foo.a: "abc/foo"
EOF
$ mkdir abc; touch abc/foo.{b,c}
$ make -rf Makefile9
foo.b: "foo.b"
foo.c: "foo"
.c.d: "abc/foo"
foo.a: "abc/foo"
--<End>-----------------------------------------------------------------

This issue is caused by suff.c:SuffFindNormalDeps() stripping
the directory part from the target if it is found by Dir_FindFile().



Issue 10: explicit dependencies affect transformation rule selection
=========

The dependencies specified on a target may change the transformation
rule that was selected based on the order of suffixes in .SUFFIXES.
This is against POSIX:

    The suffix of the target (.s1) to be built is compared to the list
    of suffixes specified by the .SUFFIXES special targets. If the .s1
    suffix is found in .SUFFIXES, the inference rules shall be searched
    in the order defined for the first .s2.s1 rule whose prerequisite
    file ($*.s2) exists.

The dependencies of the target should not enter into the equation at any
point.

--<Start>---------------------------------------------------------------
$ cat >Makefile10 <<EOF
.SUFFIXES: .x .y .z
.x.z:
        @echo .x.z '"\$(?)"'
.y.z:
        @echo .y.z '"\$(?)"'
test1.z: test1.y
test2.z: foo/bar/test2.y
#test1.x:
#test1.y:
#test2.x:
#foo/bar/test2.y:
# Expected:
# .x.z "test1.y test1.x"
# .x.z "foo/bar/test2.y test2.x"
EOF
$ mkdir -p foo/bar; touch test1.{x,y} test2.x foo/bar/test2.y
$ make -rf Makefile10 test1.z test2.z
.y.z "test1.y"
.y.z "foo/bar/test2.y"
$ $EDITOR Makefile10 # Uncomment the rules for test{1,2}.{x,y}
$ rm -r test?.? foo; make -rf Makefile10 test1.z test2.z
.y.z "test1.y"
.y.z "foo/bar/test2.y"
$ mkdir -p foo/bar; touch foo/bar/test3.y
$ make -rf Makefile10 test3.z
make: don't know how to make test3.z. Stop

make: stopped in /some/dir
--<End>-----------------------------------------------------------------

While the standard only talks about an existing file, a sane
interpretation is that it actually means "prerequisite file or target
rule", so the second example is for that one.

Notice that the .x suffix is before the .y suffix in the suffix list
and thus should be the selected rule for both test1 and test2.
The test2 case is also a big surprise: inferring accross directories
is certainly not POSIX compliant and foo/bar isn't mentioned in any
.PATH either.  This is also inconsistent, as is evidenced by make's
inability to create test3.z.

This issue happens because there is a deliberate piece of code in
suff.c:SuffFindNormalDeps() for invoking suff.c:SuffFindCmds() for doing
exactly this override.



Issue 11: sources from transformation rules are expanded incorrectly
=========

If the transformation rule chain contains multiple steps, dynamic
sources only work in the last step of the chain.  Sources from
a transformation rule are expanded three times instead of the expected
two.  The second expansion is the extra one and causes expanded values
to /not/ be split on white space.

Why is two expansions expected?  Variables are expanded the first time
when a line is read, so the sources would get expanded once there in
the global context.  When a transformation is applied, children added
from the transformation need to be expanded a second time in
the target's context in case the transformation had dynamic sources, so
that's the second one.

--<Start>---------------------------------------------------------------
$ cat >Makefile11 <<EOF
.SUFFIXES: .x .y .z
.x.y: \$(.PREFIX).first
        @echo .x.y '"\$(?)"'
.y.z: \$(.PREFIX).second
        @echo .y.z '"\$(?)"'
test.x:
test.first:
test.second:

#VAR = foo bar
#.x.y: \$\$\$\$(VAR)
#       irrelevant
#.y.z: \$\$(VAR)
#       irrelevant
#test2.y:

# Expected 1:
# .x.y "test.x test.first"
# .y.z "test.y test.second"

# Expected 3:
# make: don't know how to make \$(VAR). Stop
#
# make: stopped in /some/dir

# Expected 4:
# make: don't know how to make foo. Stop
#
# make: stopped in /some/dir
EOF
$ make -rf Makefile11 test.z
$ make -rf Makefile11 test.y test.z  # works when everything is explicit
.x.y "test.x test.first"
.y.z "test.y test.second"
$ $EDITOR Makefile11  # Uncomment VAR, 2nd transformation rules, test2.y
$ make -rf Makefile11 test.y
make: don't know how to make bar. Stop

make: stopped in /some/dir
$ make -rf Makefile11 test2.z
make: don't know how to make foo bar. Stop

make: stopped in /some/dir
--<End>-----------------------------------------------------------------

Dynamic sources are not properly expanded because
suff.c:SuffExpandChildren() is called for all stages except the last one
/before/ values for the .PREFIX and .TARGET variables have been set in
suff.c:SuffFindNormalDeps().

The sources get expanded thrice because make.c:Make_HandleUse() also
expands the added children but suff.c:SuffFindNormalDeps() expects
to be the one to expand them.  Make_HandleUse() does not do whitespace
splitting and SuffFindNormalDeps() does splitting only if it expanded
anything.  Because of the extra expansion, there usually is nothing
to expand for SuffFindNormalDeps().



Issue 12: if a rule is defined multiple times, the first one is used
=========

From POSIX:

    If a rule is defined more than once, the value of the rule shall be
    that of the last one specified.

This only applies to rules with commands.  A rule without commands is
used to add extra dependencies for a target.

--<Start>---------------------------------------------------------------
$ cat >Makefile12 <<EOF
test:
        @echo first
test:
        @echo second
# Expected:
# second
EOF
$ make -rf Makefile12
make: "/some/dir/Makefile12" line 4: warning: duplicate script for target 
"test" ignored
make: "/some/dir/Makefile12" line 2: warning: using previous script for "test" 
defined here
first
--<End>-----------------------------------------------------------------

This issue is caused by parse.c:ParseAddCmd() having the proper way
#ifdef'd away and instead the incorrect one is used.


>How-To-Repeat:

Inlined into the description.

>Fix:

I will post a patch as a follow-up.