bugmake - Bugs: bug #30381, Don't avoid implicit rule...


bug #30381: Don't avoid implicit rule recursion quite so soon.

Submitted by:  Reinier Post <r_p>
Submitted on:  Wed 07 Jul 2010 03:26:17 PM UTC  
Severity: 3 - NormalItem Group: Enhancement
Status: NonePrivacy: Public
Assigned to: NoneOpen/Closed: Open
Component Version: 3.81Operating System: None
Fixed Release: NoneTriage Status: None

Add a New Comment (Rich MarkupRich Markup):

You are not logged in

Please log in, so followups can be emailed to you.


(Jump to the original submission Jump to the original submission)

Sat 06 Apr 2013 01:37:57 PM UTC, comment #14:

I don't think it's correct to implement this feature using a command-line option. Makefiles need to be written in a certain way to use this feature and if they are written that way, then you must have the feature enabled or the build will fail. And vice versa.

For situations like that we don't want to force the user to have to specify options on the command line: these options need to be set within the makefile so the makefile author controls them. Also it's not clear that having the flag on the command line, where it will be passed recursively to sub-makes, won't break those sub-makes in some situations.

Paul D. Smith <psmith>
Project Administrator
Tue 02 Nov 2010 11:34:22 AM UTC, comment #13:

Here is version two of the patch. It fixes an essential off-by-one error, adds the feature to .FEATURES, improves the tests, and adds documentation (generated info files not included). The reported version is still 3.82.

(file #21902)

Reinier Post <r_p>
Mon 01 Nov 2010 10:28:36 AM UTC, comment #12:

Another idea is to make the "Avoiding implicit rule recursion" message report which rule is being avoided.

For this it seems necessary to either add a floc field to struct rule or give even commandless rules a cmds field so as to allow the use of rule->cmds->floc.

Would this be acceptable?

Reinier Post <r_p>
Mon 01 Nov 2010 09:53:45 AM UTC, comment #11:

Strike my last comment: invoking a rule multiple times in a chain appears to work just fine.

To prove this, here is a patch against the make 3.82 source that adds a -M option, which allows this; a test script is included, but string translations and documentation updates are missing.

The idea is really simple: it replaces rule->in_use with rule->nr_reuses and compare that number against the value of -M. Note that -M without an argument means 'infinite' (same as for -j), so it allows rule chaining to go into an infinite loop.

I will use this as a workaround for myself. I didn't use the idea discussed below (to allow recursion only when the dependency is shorter than the target) only because it was slightly harder to implement.

(file #21887)

Reinier Post <r_p>
Wed 27 Oct 2010 10:05:46 AM UTC, comment #10:

I really need this feature with my present set of makefiles, so I've looked at the code (implicit.c) to see how easy it would be to make the change. The main issue is the mixing in struct rule of definition-time information and inference-time information which makes it difficult to allow the same rule to be used multiple times in the same inference chain. This would need to be split up. Due to the length of pattern_search() and the number of variables it uses, I won't attempt a patch at this time.

Reinier Post <r_p>
Mon 19 Jul 2010 02:11:14 PM UTC, comment #9:

Maybe we can use something like

%(1).foo%(2) : %(1)a%(2)

So your example will look like

%(1).foo : %(1)a%(1)

I agree with Reiner. make can be better and has more features, then current implementation.

At least all functions from


can be very good to have in standard make. Basically I see in source some EXPERIMENTAL blocks already. :-)

Olexiy Buyanskyy <olexiyb>
Mon 19 Jul 2010 11:28:52 AM UTC, comment #8:

Somehow the verbatim tags ate most of my descriptions (a preview facility would be really nice), retry:

(imagine verbatim on)

(6) d. For each prerequisite that does not exist, follow this algorithm recursively to see if the prerequisite can be made by an implicit rule, excluding the present rule from the list of rules to consider.

(imagine verbatim off)

A variant on my proposal:

(imagine verbatim on)

(6) d. For each prerequisite that does not exist, follow this algorithm recursively to see if the prerequisite can be made by an implicit rule, excluding the present rule from the list of rules to consider if and only if the present target is not shorter than the prerequisite.

(imagine verbatim off)

Reinier Post <r_p>
Mon 19 Jul 2010 11:24:30 AM UTC, comment #7:


I don't think it's complicated to describe. %: %.o and %.o: %.c don't shorten the search target so they can't be used twice, while %.made: % does. All the cases in my own makefiles are of the second type anyway. This is only considered after variable expansion, so variables in rules won't complicate it. Things will only become complicated if less restrictive criteria are chosen instead; this can be done using techniques from formal language theory. Even that wouldn't necessarily bother the users of make, just the implementers, but there is something to be said for keeping things simple. Performance will only be lost for cases in which a second application of a rule during a search matches, and a dependency in that rule is shorter than the target, and that dependency doesn't eventually produce a viable chain; the overhead resulting from comparing against the targets in the chain thus far should be negligible. So it would be relevant to find existing makefiles in which such second applications already occur. (This can be done with a modified make.)

The existing description at http://www.gnu.org/software/make/manual/make.html#Implicit-Rule-Search doesn't even mention the restriction that no chain may contain the same rule twice. To document it, 6d can be changed as follows:

A variant on my proposal:

Here, comparing the lengths happens on the rule's first application instead of on later applications. This can only make a difference if targets and dependencies may contain different numbers of masks, which is not possible at present:

(The second % is not interpreted as a mask.)


I know I can hack around the issue in this way, but it makes my makefiles unmaintainable. As I said, I have lost time writing makefiles in the past because I wasn't aware of this restriction, and I'm sure others have, too. I also lose time because I have to work around it with such techniques. It's unclear how often such recursion would be used if it were possible.

Reinier Post <r_p>
Sat 17 Jul 2010 03:04:50 PM UTC, comment #6:


I agree with Paul. Performance is very important. And we should not add very rare used feature.

What about submakes. Did you try

%.rev : %
sort $? > $@
$(MAKE) $@.rev

Olexiy Buyanskyy <olexiyb>
Fri 09 Jul 2010 09:56:45 PM UTC, comment #5:

But it isn't just a matter of infinite recursion; there's a very serious issue of performance as well, even without infinite recursion. Computing pattern rule matches can already take quite a while: if we add more ways in which patterns can recurse that's potentially orders of magnitude more possible paths make has to examine and discard before it can move forward (or give up).

There are many rules in the default database of the form "% : %.o" for example; if we can't avoid recursing on them then they're essentially infinite already: the idea that we can just debug these issues because they're really rare anyway is not really true.

Yes, saying that we'd only allow recursion that resulted in a smaller file length would help... but it seems complicated to describe. Coming up with the changes needed to the "Implicit Rule Search Algorithm" chapter in the manual might be a good way forward.

Paul D. Smith <psmith>
Project Administrator
Fri 09 Jul 2010 08:25:20 PM UTC, comment #4:

PS the second rule in the example should also have a > of course.

Reinier Post <r_p>
Fri 09 Jul 2010 08:24:10 PM UTC, comment #3:

Sorry to have been so cryptic, but I really wanted to express the need and various ideas for how to approach a solution, rather than present a detailed proposal - for that, I would need more input from other users and more knowledge about the details of GNU make's operation.

Safeguarding against infinite recursion is clearly useful - although GNU make has other ways of getting into infinite loops - but the rules can be relaxed in many different ways. A straightforward way to address your concern is to allow multiple iterations only when the newly considered targets are shorter than the ones considered in previous iterations of the rule in question. Personally, I'd be happy to see the check dropped completely, I know how to use make -d.

The use cases I have for it arise when I use utilities that produce files of the same type as their input files; for instance, text processing utilities such as grep, sort, rev, uniq, join, cut, or image processing utilities like those of netpbm or ImageMagick. Complex processing chains can be built up with such utilities, and in such chains, it is sometimes useful to call the same rule multiple times. I'd rather just write rules that make sense and debug cases of infinite regress with make -d than use make -d to discover cases of make's built-in prevention and hack around it in my Makefile by artificially duplicating the rules and renaming some of the dependencies in question, as I'm doing now:

I'm not saying that this use is typical (although I've personally run into this limitation a few times in the past and only now realize what is going on), I'm just saying that it would be a lot easier to write such rule systems if GNU make didn't make it difficult.

Reinier Post <r_p>
Wed 07 Jul 2010 05:13:27 PM UTC, comment #2:

Actually my example is solved by your suggestion to use a stack of targets. However, if you imagine a pattern rule where every iteration of the rule grows, instead of shrinks, then a stack of targets wouldn't help. What about:

In this case every time we iterate we have a new target.

A maximum recursion would solve it. I'm not sure how difficult it would be to implement though, and I'm not sure we have a strong use-case for it. If you can define the number of iterations then it should be possible to define targets in your makefile to "fix" the problem... no?

Paul D. Smith <psmith>
Project Administrator
Wed 07 Jul 2010 05:02:06 PM UTC, comment #1:

This is the documented behavior, however:

Also, your example is too simple. How does make know that if it just went "one step further" it would find a way to build that target? Suppose you had a chain that worked like this:

Now, without the above rule, this would be an infinite loop.

If you really want a feature like this then you'll need to come up with a much more precise definition of exactly how the system should behave. I'll leave this open as an enhancement.

Until then you'll have to define a target for the intermediate files (e.g., foo.rev: here) in order to get the behavior you want.

Paul D. Smith <psmith>
Project Administrator
Wed 07 Jul 2010 03:26:17 PM UTC, original submission:

This caught me by surprise (sh> is my shell prompt here):

Come on, make(1)! Yes I'm asking you to apply a rule twice, but with a different target!

This keeps biting me in the make file I'm writing at the moment.
My proposal is to keep a stack of the targets, and only stop recursion if a target already occurs on the stack.
Or least let me set a limit to how often you're willing to try this.

Reinier Post <r_p>


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):

Attached Files
file #21902:  make-3.82-M.diff-Nurd added by r_p (11kB - application/octet-stream)
file #21887:  make-3.82-M.diff-Nurd added by r_p (6kB - application/octet-stream - a clean fix for my problem)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -unavailable- added by olexiyb (Posted a comment)
  • -unavailable- added by psmith (Posted a comment)
  • -unavailable- added by r_p (Submitted the item)
  • -unavailable- added by r_p

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.


    Please enter the title of George Orwell's famous dystopian book (it's a date):



    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 02 Nov 2010 11:34:22 AM UTCr_pAttached File-=>Added make-3.82-M.diff-Nurd, #21902
    Mon 01 Nov 2010 09:53:45 AM UTCr_pAttached File-=>Added make-3.82-M.diff-Nurd, #21887
    Wed 07 Jul 2010 05:02:06 PM UTCpsmithItem GroupNone=>Enhancement
      Component VersionNone=>3.81
    Wed 07 Jul 2010 03:26:17 PM UTCr_pCarbon-Copy-=>Added -unavailable-

    Back to the top

    Powered by Savane 3.1-cleanup