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

 
 

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

Submitter:  Reinier Post <r_p>
Submitted:  Wed 07 Jul 2010 03:26:17 PM UTC
Votes: 50
 
Severity:  3 - Normal Item Group:  Enhancement
Status:  None Privacy:  Public
Assigned to:  None Open/Closed:  Open
Component Version:  3.81 Operating System:  None
Fixed Release:  None Triage Status:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 12 May 2015 09:05:46 PM UTC, comment #19: 

Regarding the earlier suggestion of using recursive calls to Make:

The problem with this is concurrency.  I want to do multi-threaded make, and I don't want different recipes building the same shared prereq simultaneously, stepping on each others' output files, etc.  I am going to do recursive make for now, because I can see no other option, but the slowdown is going to be large.

Anonymous
Tue 12 May 2015 08:58:42 PM UTC, comment #18: 

Ack, my code got mangled, because I'm new at Rich Markup.  Here it is again:

I could really use this feature.  I'm implementing a sort of branching revision control of databases, in which the history is stored as SQL diffs in files named things like "<new version #>.from.<old version #>.sql".

So, for example, there's an explicit rule in the makefile to generate the "root" database "0.db", and then there are a bunch of SQL files in the folder, with names like "5.from.3.sql" and "3.from.0.sql".

I have an implicit rule that would, if not for the limitation discussed in this thread, walk up the dependency chain when the user calls e.g. "make 5.db":


.SECONDEXPANSION:
%.db : %.from.*.sql $(SQL_EXE) $$(subst sql,db,$$(subst $$*.from.,$$(blank),$$(wildcard $$*.from.*.sql)))
        $(CP) $(subst sql,db,$(subst $*.from,$(blank),$*.from.*.sql)) $*.prev.db
        $(SQL_EXE) $*.prev.db < $*.from.*.sql
        $(MV) $*.prev.db $*.db


Make looks for 5.db, finds it missing, then tries the above rule, and succeeds in finding 5.from.3.sql and thus expanding the expression in the prereq list of 5.db to include 3.db.  But then it refuses to follow the same rule for 3.db.

Anonymous
Tue 12 May 2015 08:54:32 PM UTC, comment #17: 

I could really use this feature.  I'm implementing a sort of branching revision control of databases, in which the history is stored as SQL diffs in files named things like \<new version #\>.from.\<old version #\>.sql .

So, for example, there's an explicit rule in the makefile to generate the "root" database "0.db", and then there are a bunch of SQL files in the folder, with names like "5.from.3.sql" and "3.from.0.sql".

I have an implicit rule that would, if not for the limitation discussed in this thread, walk up the dependency chain when the user calls e.g. "make 5.db":

<verbatim>
.SECONDEXPANSION:
%.db : %.from.*.sql $(SQL_EXE) $$(subst sql,db,$$(subst $$*.from.,$$(blank),$$(wildcard $$*.from.*.sql)))
$(CP) $(subst sql,db,$(subst $*.from,$(blank),$*.from.*.sql)) $*.prev.db
$(SQL_EXE) $*.prev.db < $*.from.*.sql
$(MV) $*.prev.db $*.db
</verbatim>

Make looks for 5.db, finds it missing, then tries the above rule, and succeeds in finding 5.from.3.sql and thus expanding the expression in the prereq list of 5.db to include 3.db.  But then it refuses to follow the same rule for 3.db.

Anonymous
Mon 02 Jun 2014 01:18:37 PM UTC, comment #16: 

Brent, I don't think your problem can be helped by this patch.

For details, see my reply to the list.

Reinier Post <r_p>
Fri 30 May 2014 02:58:17 AM UTC, comment #15: 

I support this feature.

I just tried to write a makefile that implicitly generates output files from XML control files, that contain references to other files in the XML.  What I wanted was this:


define futurebases
   $(shell xmllint --xpath "print(//futurebase/@filename)" $(1))
endef

.SECONDEXPANSION:

%.htb: %.xml $$(call futurebases, %.xml)
        $(HOFFMAN) -g $<


It doesn't work.

Brent Baccala <baccala>
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>
Group 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

http://gmsl.sourceforge.net/

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: 

  Paul,

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:


(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.


A variant on my proposal:


(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.


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:


sh>  touch bab ba% ; echo '%.foo: %a%; @echo making $@ from $?' | make -f - b.foo
making b.foo from ba%


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

  Olexiy,

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: 

Reiner,

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>
Group 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:



%.sorted: %
  @sort $? > $@

%.sorted2: %
  @sort $?  $@


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:

%.x : %.x.x ; cat $< > $@


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>
Group administrator
Wed 07 Jul 2010 05:02:06 PM UTC, comment #1: 

This is the documented behavior, however:

   No single implicit rule can appear more than once in a chain.  This
means that `make' will not even consider such a ridiculous thing as
making `foo' from `foo.o.o' by running the linker twice.  This
constraint has the added benefit of preventing any infinite loop in the
search for an implicit rule chain.


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:

%.x : %.y ; cat > $@
%.y : %.x ; cat > $@


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>
Group administrator
Wed 07 Jul 2010 03:26:17 PM UTC, original submission:  

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



sh> echo foo > foo
sh> echo '%.rev : %; rev $? > $@' > Makefile
sh> make foo.rev.rev
make: *** No rule to make target `foo.rev.rev'.  Stop.
sh> make foo.rev foo.rev.rev
rev foo > foo.rev
rev foo.rev > foo.rev.rev


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 Files:
   
   
Comment:
   

Attached Files
file #21902:  make-3.82-M.diff-Nurd added by r_p (11KiB - application/octet-stream)
file #21887:  make-3.82-M.diff-Nurd added by r_p (6KiB - 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
  • -email is unavailable- added by free_keith (Voted in favor of this item)
  • -email is unavailable- added by baccala (Posted a comment)
  • -email is unavailable- added by olexiyb (Posted a comment)
  • -email is unavailable- added by psmith (Posted a comment)
  • -email is unavailable- added by r_p (Submitted the item)
  • -email is unavailable- added by r_p
  •  

    There are 50 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-06-29 free_keith Carbon-Copy- Added free_keith
    2010-11-02 r_p Attached File- Added make-3.82-M.diff-Nurd, #21902
    2010-11-01 r_p Attached File- Added make-3.82-M.diff-Nurd, #21887
    2010-07-07 psmith Item GroupNone Enhancement
        Component VersionNone 3.81
    2010-07-07 r_p Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code