Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!uunet!rsalz From: rsalz@uunet.UU.NET (Rich Salz) Newsgroups: comp.sources.unix Subject: v12i014: Cake, a make replacement, Part08/09 Message-ID: <2360@uunet.UU.NET> Date: Fri, 16-Oct-87 19:20:21 EDT Article-I.D.: uunet.2360 Posted: Fri Oct 16 19:20:21 1987 Date-Received: Sun, 18-Oct-87 00:39:14 EDT Organization: UUNET Communications Services, Arlington, VA Lines: 1395 Approved: rs@uunet.UU.NET Submitted-by: Zoltan Somogyi Posting-number: Volume 12, Issue 14 Archive-name: cake/part08 [ There are some missing font-change commands, I believe, but it's still quite readable. --r$ ] #! /bin/sh # This is a shell archive, meaning: # 1. Remove everything above the #! /bin/sh line. # 2. Save the resulting text in a file. # 3. Execute the file with /bin/sh (not csh) to create: # paper.bib # This archive created: Wed Oct 14 20:28:43 1987 export PATH; PATH=/bin:/usr/bin:$PATH echo mkdir Man mkdir Man echo cd Man cd Man echo shar: "extracting 'paper.bib'" '(40457 characters)' if test -f 'paper.bib' then echo shar: "will not over-write existing file 'paper.bib'" else sed 's/^X//' << \SHAR_EOF > 'paper.bib' X.\" Nroff macros for papers X.\" X.\" General setup X.nr ii 5n X.nr pi 5n X.nr fi 0 X.nh X.\" Simulated thesis mode X.de si X.po 1i X.he ''- % -'' X.. X.\" Title begin X.de tb X.(l C X.. X.\" Title end X.de te X.)l X.. X.\" Abstract begin X.de ab X.ll -16n X.po +8n X.(l C X\fBAbstract\fP X.)l X.. X.\" Abstract end X.de ae X X.ll +16n X.po -8n X.. X.\" Title spacing X.de ts X\& X.sp 1.45i X.. X.\" Melbourne University address X.de mu XDepartment of Computer Science XUniversity of Melbourne XParkville, 3052 Victoria, Australia X.. X.\" Zoltan Somogyi's address X.de zs X.po +8m X.(l M XUUCP: {uunet,mcvax,ukc}!munnari.oz!zs XARPA: zs%munnari.oz@uunet.uu.net XCSNET: zs%munnari.oz@australia X.)l X.po -8m X.. X.\" Computing Reviews categories X.de cr X.lp X\fBCR Categories and Subject Descriptors:\fP X.br X.. X.\" Keywords X.de kw X.lp X\fBAdditional Keywords and Phrases:\fP X.br X.. X.\" Tech report offsets etc X.de to X.br X.he ''- % -'' X.pn 1 X.po 1.2i X.bp X.. X.\" Acknowledge the ACrb X.de rb X.(f XThis research was supported by the Australian Computer Research Board. X.)f X.. X.\" Setup for theorem numbering X.de $1 X.nr tn 0 1 X.. X.\" Theorem X.de tr X.lp X.b "Theorem \\n($1.\\n+(tn" X.. X.\" Lemma X.de le X.lp X.b "Lemma \\n($1.\\n+(tn" X.. X.\" Corollary X.de co X.lp X.b "Corollary \\n($1.\\n+(tn" X.. X.\" Proof X.de pr X.lp X.b "Proof" X.br X.. X.\" Proof end X.de pe X.b "[]" X.br X.. X.\" Definition of terms X.de dt X.lp X.b "Definition" X.. X.\" Example X.de ea X.lp X.b "Example" X.. X.\" Program begin X.de (p X.sp .05i X.ft as X.nf X.. X.\" Program end X.de )p X.fi X.ft R X.sp .05i X.. X.\" Print contents page X.de ct X.he '''' X.bp X.ls 1 X.sp 4 X.ce 1 X\fIContents\fP X.ce 0 X.sp X.xp X.. X.\" Generate index X.de $0 X.(x X.if "\\$3"1" .sp X'in \\$3m*5u-5u X\fI\\$2. \\$1\fR X'in X.)x X.. X.\" Begin quote X.de (Q X.br X.nr po +\\n(iiu X.xl -\\n(iiu X.nr Gr \\n($r X.vs \\n(.vu+12p/2u X.nr $r \\n(.vu/\\n(.su X.lp X.. X.\" End quote X.de )Q X.nr po 0 X.xl X.nr $r \\n(Gr X.. X.ds l] /usr/bib/bmac X.\" Zoltan's bib macros X.ds [[ [ X.ds ]] ] X.ds ], ,\| X.ds ]- - X.ds [. " \& X.ds .] . X.ds [, " \& X.ds ,] , X.ds [? " \& X.ds ?] ? X.ds [: " \& X.ds :] : X.ds [; " \& X.ds ;] ; X.ds [! " \& X.ds !] ! X.ds [" " \& X.ds "] \&" X.ds [' " \& X.ds '] ' X.ds [< " \& X.ds >] X.\" reference formmating strings X.ds a] " \& X.ds b] , \& X.ds c] , \& X.ds n] "\&, and \& X.ds m] "\&, and \& X.ds p] . X.\" reference formmating macros X.de s[ \" start reference X.nh X.IP [\\*([F] 5m X.. X.de e[ \" end reference X.[- X.. X.de [] \" start to display collected references X.LP X.. X.de ][ \" choose format X.ie "\\*([T"" .nr t[ 9 \" notitle X.el \{\ X. ie !"\\*([J"" \{\ X. ie !"\\*([V"" .nr t[ 1 \" journal X. el .nr t[ 5 \" conference paper X. \} X. el \{\ X. ie !"\\*([R"" .nr t[ 4 \" technical report X. el \{\ X. ie "\\*([I"" .nr t[ 0 \" other (inverted test) X. el \{\ X. ie !"\\*([B"" .nr t[ 3 \" article in book X. el .nr t[ 2 \" book X. \} X. \} X. \} X.\} X.\\n(t[[ X.. X.de 0[ \" other X.s[ X.tm bmac.zs: using other for \\*([T X.if !"\\*([A"" \\*([A\c X.if !"\\*([T"" , \\*([T\c X.if !"\\*([I"" , \\*([I\c X.if !"\\*([C"" , \\*([C\c X.if !"\\*([V"" , vol. \\*([V\c X.if !"\\*([D"" , \\*([D\c X.if !"\\*([O"" , \\*([O\c X\&. X.e[ X.. X.de 1[ \" journal article X.s[ X.ie !"\\*([A"" \\*([A, X.el \{\ X. ie !"\\*([E"" \{\ X. ie \\n([E-1 \\*([E\\0(eds.), X. el \\*([E\\0(ed.), X. \} X. el .tm bmac.zs: no author/editor for journal article "\\*([T" X.\} X\\*([T\c X, \\fI\\*([J\\fP, \\*([V\c X.if !"\\*([N"" :\\*([N\c X.ie !"\\*([D"" \\ \\|(\\*([D)\c X.el .tm bmac.zs: no date for journal article "\\*([T" X.ie !"\\*([P"" \{\ X. ie \\n([P , pp. \\*([P\c X. el , p. \\*([P\c X.\} X.el .tm bmac.zs: no page numbers for journal article \\*([T X.if !"\\*([O"" , \\*([O\c X\\&. X.e[ X.. X.de 2[ \" book X.s[ X.ie !"\\*([A"" \\*([A, X.el \{\ X. ie !"\\*([E"" \{\ X. ie \\n([E-1 \\*([E\\0(eds.), X. el \\*([E\\0(ed.), X. \} X. el .tm bmac.zs: no author/editor for book "\\*([T" X.\} X\\*([T\c X.if !"\\*([S"" , \\*([S\c X.if !"\\*([S"" \{\ X. ie !"\\*([V"" volume \\& \\*([V\c X. el .if !"\\*([N"" \\& \\*([N\c X.\} X.ie !"\\*([I"" , \\*([I\c X.el .tm bmac.zs: no publisher for book "\\*([T" X.ie !"\\*([C"" , \\*([C\c X.el .tm bmac.zs: no city for book "\\*([T" X.ie !"\\*([D"" , \\*([D\c X.el .tm bmac.zs: no date for book "\\*([T" X.if !"\\*([O"" , \\*([O\c X\\&. X.e[ X.. X.de 3[ \" article in book X.s[ X.ie !"\\*([A"" \\*([A, X.el .tm bmac.zs: no author for article in book "\\*([T" X\\*([T,\\0in:\\0\c X.ie !"\\*([E"" \{\ X. ie \\n([E-1 \\*([E\\0(eds.), X. el \\*([E\\0(ed.), X.\} X.el .tm bmac.zs: no editor for article in book "\\*([T" X\\fI\\*([B\\fP\c X.if !"\\*([S"" , \\*([S\c X.if !"\\*([S"" \{\ X. ie !"\\*([V"" \\& volume \\*([V\c X. el .if !"\\*([N"" \\& \\*([N\c X.\} X.ie !"\\*([I"" , \\*([I\c X.el .tm bmac.zs: no publisher for article in book "\\*([T" X.ie !"\\*([C"" , \\*([C\c X.el .tm bmac.zs: no city for article in book "\\*([T" X.ie !"\\*([D"" , \\*([D\c X.el .tm bmac.zs: no date for article in book "\\*([T" X.if !"\\*([P"" \{\ X. ie \\n([P , pp. \\*([P\c X. el , p. \\*([P\c X.\} X.if !"\\*([O"" , \\*([O\c X\\&. X.e[ X.. X.de 4[ \" report X.s[ X.ie !"\\*([A"" \\*([A, X.el \{\ X. ie !"\\*([E"" \{\ X. ie \\n([E-1 \\*([E\\0(eds.), X. el \\*([E\\0(ed.), X. \} X. el .tm bmac.zs: no author/editor for report "\\*([T" X.\} X\\*([T, \\*([R\c X.ie !"\\*([I"" , \\*([I\c X.el .tm bmac.zs: no publisher for report "\\*([T" X.ie !"\\*([C"" , \\*([C\c X.el .tm bmac.zs: no city for report "\\*([T" X.ie !"\\*([D"" , \\*([D\c X.el .tm bmac.zs: no date for report "\\*([T" X.if !"\\*([O"" , \\*([O\c X\\&. X.e[ X.. X.de 5[ \" conference paper X.s[ X.ie !"\\*([A"" \\*([A, X.el \{\ X. ie !"\\*([E"" \{\ X. ie \\n([E-1 \\*([E\\0(eds.), X. el \\*([E\\0(ed.), X. \} X. el .tm bmac.zs: no author/editor for conference paper "\\*([T" X.\} X\\*([T, \\fI\\*([J\\fP\c X.ie !"\\*([C"" , \\*([C\c X.el .tm bmac.zs: no city for conference paper "\\*([T" X.if !"\\*([I"" , \\*([I\c X.ie !"\\*([D"" , \\*([D\c X.el .tm bmac.zs: no date for conference paper "\\*([T" X.ie !"\\*([P"" \{\ X. ie \\n([P , pp. \\*([P\c X. el , p. \\*([P\c X.\} X.el .tm bmac.zs: no page numbers for conference paper \\*([T X.if !"\\*([O"" , \\*([O\c X\\&. X.e[ X.. X.de 9[ \" notitle X.s[ X.tm bmac.zs: reference with no title X.if !"\\*([A"" \\*([A\c X.if !"\\*([E"" , ed. \\*([E\c X.if !"\\*([I"" , \\*([I\c X.if !"\\*([C"" , \\*([C\c X.if !"\\*([V"" , vol. \\*([V\c X.if !"\\*([D"" , \\*([D\c X.if !"\\*([O"" , \\*([O\c X\&. X.e[ X.. X.de [- \" clean up after yourself X.rm [A [B [C [D X.rm [E [F [G [H X.rm [I [J [K X.rm [N [O [P X.rm [R [T X.rm [V [W X.. X.ds [[ ( X.ds ]] ) X.ds ], ; X.\" Start references section X.de [] X.ls 1 X.ne 4 X.sh 1 "References" X.sp 1 X.nr ii 16 X.. X.\" Start reference X.de s[ X.nh X.ip (\\*([F) X.. X.\" End reference X.de e[ X.[- X.. X.\" NEED bib tbl eqn X.tb X\f(CBCake\fP:\fB a fifth generation version of \f(CBmake\fP\fR X.sp XZoltan Somogyi XDepartment of Computer Science XUniversity of Melbourne Xzs@mulga.OZ X.sp 2 X.ab X.lp X\f(asMake\fP is a standard Unix\** utility Xfor maintaining computer programs. X\f(asCake\fP is a rewrite of \f(asmake\fP from the ground up. XThe main difference is one of attitude: X\f(ascake\fP is considerably more general and flexible, Xand can be extended and customized to a much greater extent. XIt is applicable to a wide range of domains, Xnot just program development. X.(f X\** Unix is a trademark of AT&T Bell Laboratories. X.)f X.ae X.fo ''- % -'' X.ta 0.4i 0.8i 1.2i 1.6i 2.0i 2.4i 2.8i 3.2 3.6i 4.0i 4.4i 4.8i 5.2i 5.6i X.EQ Xdelim off X.EN X.sp 2 X.\" X.sh 1 "Introduction" X.\" X.lp XThe Unix utility \f(asmake\fP\*([<\*([[Feldman,\ 79\*(]]\*(>] Xwas written to automate the compilation and recompilation of C programs. XPeople have found \f(asmake\fP so successful in this domain Xthat they do not wish to be without its services Xeven when they are working in other domains. XSince \f(asmake\fP was not designed with these domains in mind X(some of which, e.g. VLSI design, Xdid not even exist when \f(asmake\fP was written), Xthis causes problems and complaints. XNevertheless, implied in these complaints Xis an enormous compliment to the designers of \f(asmake\fP; Xone does not hear many grumbles Xabout programs with only a few users. X.pp XThe version of \f(asmake\fP described in\*([<\*([[Feldman,\ 79\*(]]\*(>] Xis the standard utility. XAT&T modified it in several respects for distribution with System V Xunder the name \f(asaugmented make\fP\*([<\*([[AT&T,\ 84\*(]]\*(>]. XWe know of two complete rewrites: X\f(asenhanced make\fP\*([<\*([[Hirgelt,\ 83\*(]]\*(>] Xand \f(asfourth generation make\fP\*([<\*([[Fowler,\ 85\*(]]\*(>]. XAll these versions remain oriented towards program maintenance. X.pp XHere at Melbourne we wanted something we could use for text processing. XWe had access only to standard \f(asmake\fP Xand spent a lot of time wrestling with \f(asmakefiles\fP Xthat kept on getting bigger and bigger. XFor a while we thought about modifying the \f(asmake\fP source, Xbut then decided to write something completely new. XThe basic problem was Xthe inflexibility of \f(asmake's\fP search algorithm, Xand this algorithm is too embedded in the \f(asmake\fP source Xto be changed easily. X.pp XThe name \f(ascake\fP is a historical accident. X\f(asCake\fP follows two other programs Xwhose names were also puns on \f(asmake\fP. XOne was \f(asbake\fP, a variant of \f(asmake\fP Xwith built-in rules for VLSI designs instead of C programs X\*([[Gedye,\ 84\*(]]. XThe other was David Morley's shell script \f(asfake\fP. XWritten at a time when disc space on our machine was extremely scarce, Xand full file systems frequently caused write failures, Xit copied the contents of a directory to \f(as/tmp\fP Xand invoked \f(asmake\fP there. X.pp XThe structure of the paper is as follows. XSection 2 shows how \f(ascake\fP solves Xthe main problems with \f(asmake\fP, Xwhile section 3 describes Xthe most important new features of \f(ascake\fP. XThe topics of section 4 are portability and efficiency. X.lp XThe paper assumes that you have some knowledge of \f(asmake\fP. X.\" X.sh 1 "The problems with \f(CBmake\fP" X.\" X.lp X\f(asMake\fP has three principal problems. XThese are: X.np XIt supports only suffix-based rules. X.np XIts search algorithm is not flexible enough. X.np XIt has no provisions for the sharing of new \f(asmake\fP rules. X.pp XThese problems are built deep into \f(asmake\fP. XTo solve them we had to start again from scratch. XWe had to abandon backward compatibility because Xthe \f(asmake\fP syntax is not rich enough to represent Xthe complex relationships among the components of large systems. XNevertheless, the \f(ascake\fP user interface Xis deliberately based on \f(asmake's\fP; Xthis helps users to transfer their skills Xfrom \f(asmake\fP to \f(ascake\fP. XThe \fIfunctionalities\fP of the two systems Xare sufficiently different that the risk of confusion is minimal\**. X.(f X\** XThis problem, called cognitive dissonance, is discussed in XWeinberg's delightful book\*([<\*([[Weinberg,\ 71\*(]]\*(>]. X.)f X.pp XProbably the biggest single difference Xbetween \f(asmake\fP and \f(ascake\fP lies in their general attitudes. X\f(asMake\fP is focused on one domain: Xthe maintenance of compiled programs. XIt has a lot of code specific to this domain X(especially the later versions). XAnd it crams all its functionality into some tight syntax Xthat treats all sorts of special things (e.g. \f(as.SUFFIXES\fP) Xas if they were files. X.pp X\f(asCake\fP, on the other hand, Xuses different syntax for different things, Xand keeps the number of its mechanisms to the minimum Xconsistent with generality and flexibility. XThis attitude throws a lot of the functionality of \f(asmake\fP Xover the fence into the provinces of other programs. XFor example, where \f(asmake\fP has its own macro processor, X\f(ascake\fP uses the C preprocessor; Xand where \f(asmake\fP has special code to handle archives, X\f(ascake\fP has a general mechanism Xthat \fIjust happens\fP to be able to do the same job. X.\" X.sh 2 "Only suffix-based rules" X.\" X.lp XAll entries in a \f(asmakefile\fP have the same syntax. XThey do not, however, have the same semantics. XThe main division is between Xentries which describe simple dependencies X(how to make file \f(asa\fP from file \f(asb\fP), Xand those which describe rules X(how to make files with suffix \f(as.x\fP Xfrom files with suffix \f(as.y\fP)\**. X\f(asMake\fP distinguishes the two cases by treating as a rule Xany dependency whose target is a concatenation of two suffixes. X.(f X\** XFor the moment we ignore entries whose targets are special entities Xlike .IGNORE .PRECIOUS etc. X.)f X.pp XFor this scheme to work, \f(asmake\fP must assume three things. XThe first is that all interesting files have suffixes; Xthe second is that suffixes always begin with a period; Xthe third is that prefixes are not important. XAll three assumptions are violated in fairly common situations. XStandard \f(asmake\fP cannot express the relationship Xbetween \f(asfile\fP and \f(asfile.c\fP (executable and source) Xbecause of assumption 1, Xbetween \f(asfile\fP and \f(asfile,v\fP (working file and RCS file) Xbecause of assumption 2, Xand between \f(asfile.o\fP and \f(as../src/file.c\fP (object and source) Xbecause of assumption 3. X\f(asEnhanced make\fP and \f(asfourth generation make\fP Xhave special forms for some of these cases, Xbut these cannot be considered solutions Xbecause special forms will always lag behind demand for them X(they are embedded in the \f(asmake\fP source, Xand are therefore harder to change than even the built-in rules). X.pp X\f(asCake's\fP solution is Xto do away with \f(asmake\fP-style rules altogether Xand instead to allow ordinary dependencies to function as rules Xby permitting them to contain variables. XFor example, a possible rule for compiling C programs is X.(b M X.(p X%.o: %.c X cc -c %.c X.)p X.)b Xwhere the \f(as%\fP is the variable symbol. XThis rule is actually a \fItemplate\fP Xfor an infinite number of dependencies, Xeach of which is obtained Xby consistently substituting a string for the variable \f(as%\fP. X.pp XThe way this works is as follows. XFirst, as \f(ascake\fP seeks to update a file, Xit matches the name of that file Xagainst all the targets in the description file. XThis matching process gives values to the variables in the target. XThese values are then substituted in the rest of the rule\**. X(The matching operation is a form of \fIunification\fP, Xthe process at the heart of logic programming; Xthis is the reason for the \fIfifth generation\fP bit in the title.) X.(f X\** XAfter this the rule should have no unexpanded variables in it. XIf it does, \f(ascake\fP reports an error, Xas it has no way of finding out Xwhat the values of those variables should be. X.)f X.pp X\f(asCake\fP actually supports 11 variables: X\f(as%\fP and \f(as%0\fP to \f(as%9\fP. XA majority of rules in practice have only one variable X(canonically called \f(as%\fP), and most of the other rules have two X(canonically called \f(as%1\fP and \f(as%2\fP). XThese variables are local to their rules. XNamed variables are therefore not needed, Xthough it would be easy to modify the \f(ascake\fP source to allow them. X.ea XIf \f(ascake\fP wanted to update \f(asprog.o\fP, Xit would match \f(asprog.o\fP against \f(as%.o\fP, Xsubstitute \f(asprog\fP for \f(as%\fP throughout the entry, Xand then proceed as if the \f(ascakefile\fP contained the entry X.(b M X.(p Xprog.o: prog.c X cc -c prog.c X.)p X.)b X.lp XThis arrangement has a number of advantages. XOne can write X.(b M X.(p X%.o: RCS/%.c,v X co -u %.c X cc -c %.c X.)p X.)b Xwithout worrying about the fact that one of the files in the rule Xwas in a different directory and that Xits suffix started with a nonstandard character. XAnother advantage is that rules are not restricted to Xhaving one source and one target file. XThis is useful in VLSI, Xwhere one frequently needs rules like X.(b M X.(p X%.out: %.in %.circuit X simulator %.circuit < %.in > %.out X.)p X.)b Xand it can also be useful to describe Xthe full consequences of running \f(asyacc\fP X.(b M X.(p X%.c %.h: %.y X yacc -d %.y X mv y.tab.c %.c X mv y.tab.h %.h X.)p X.)b X.\" X.sh 2 "Inflexible search algorithm" X.\" X.lp XIn trying to write a \f(asmakefile\fP Xfor a domain other than program development, Xthe biggest problem one faces Xis usually \f(asmake's\fP search algorithm. XThe basis of this algorithm is a special list of suffixes. XWhen looking for ways to update a target \f(asfile.x\fP, X\f(asmake\fP searches along this list from left to right. XIt uses the first suffix \f(as.y\fP Xfor which it has a rule \f(as.y.x\fP Xand for which \f(asfile.y\fP exists. X.pp XThe problem with this algorithm manifests itself Xwhen a problem divides naturally into a number of stages. XSuppose that you have two rules \f(as.c.b\fP and \f(as.b.a\fP, Xthat \f(asfile.c\fP exists Xand you want to issue the command \f(asmake file.a\fP. X\f(asMake\fP will tell you Xthat it doesn't know how to make \f(asfile.a\fP. XThe problem is that for the suffix \f(as.b\fP X\f(asmake\fP has a rule but no file, Xwhile for \f(as.c\fP it has a file but no rule. X\f(asMake\fP needs a \fItransitive rule\fP \f(as.c.a\fP Xto go direct from \f(asfile.c\fP to \f(asfile.a\fP. X.pp XThe number of transitive rules increases Xas the square of the number of processing stages. XIt therefore becomes significant for program development Xonly when one adds processing stages on either side of compilers. XUnder Unix, these stages are typically the link editor \f(asld\fP Xand program generators like \f(asyacc\fP and \f(aslex\fP. XHalf of standard \f(asmake's\fP builtin rules are transitive ones, Xthere to take care of these three programs. XEven so, the builtin rules do not form a closure: Xsome rare combinations of suffixes are missing X(e.g. there is no rule for going from \f(asyacc\fP source to assembler). X.pp XFor builtin rules a slop factor of two may be acceptable. XFor rules supplied by the user it is not. XA general-purpose \f(asmakefile\fP for text processing under Unix Xneeds at least six processing stages to handle X\f(asnroff/troff\fP and their preprocessors X\f(aslbl\fP, \f(asbib\fP, \f(aspic\fP, \f(astbl\fP, and \f(aseqn\fP, Xto mention only the ones in common use at Melbourne University. X.pp X\f(asCake's\fP solution is simple: Xif \f(asfile1\fP can be made from \f(asfile2\fP Xbut \f(asfile2\fP does not exist, X\f(ascake\fP will try to \fIcreate\fP \f(asfile2\fP. XPerhaps \f(asfile2\fP can be made from \f(asfile3\fP, Xwhich can be made from \f(asfile4\fP, Xand so on, until we come to a file which does exist. X\f(asCake\fP will give up only when there is \fIabsolutely no way\fP Xfor it to generate a feasible update path. X.pp XBoth the standard and later versions of \f(asmake\fP Xconsider missing files to be out of date. XSo if \f(asfile1\fP depends on \f(asfile2\fP Xwhich depends on \f(asfile3\fP, Xand \f(asfile2\fP is missing, then \f(asmake\fP will remake Xfirst \f(asfile2\fP and then \f(asfile1\fP, Xeven if \f(asfile1\fP is more recent than \f(asfile3\fP. X.pp XWhen using \f(asyacc\fP, I frequently remove generated sources Xto prevent duplicate matches when I run \f(asegrep ... *.[chyl]\fP. XIf \f(ascake\fP adopted \f(asmake's\fP approach to missing files, Xit would do a lot of unnecessary work, Xrunning \f(asyacc\fP and \f(ascc\fP to generate Xthe same parser object again and again\**. X.(f X\** XIn this case \f(asmake\fP is rescued from this unnecessary work Xby its built-in transitive rules, Xbut as shown above this should not be considered Xa \fIgeneral\fP solution. X.)f X.pp X\f(asCake\fP solves this problem Xby associating dates even with missing files. XThe \fItheoretical update time\fP of an existing file Xis its modify time (as given by stat(2)); Xthe theoretical update time of a missing file Xis the theoretical update time of its youngest ancestor. XSuppose the \f(asyacc\fP source \f(asparser.y\fP Xis older than the parser object \f(asparser.o\fP, Xand \f(asparser.c\fP is missing. X\f(asCake\fP will figure that if it recreated \f(asparser.c\fP Xit would get a \f(asparser.c\fP which \fItheoretically\fP Xwas last modified at the same time as \f(asparser.y\fP was, Xand since \f(asparser.o\fP is younger than \f(asparser.y\fP, Xtheoretically it is younger than \f(asparser.c\fP as well, Xand therefore up-to-date. X.\" X.sh 2 "No provisions for sharing rules" X.\" X.lp XImagine that you have just written a program Xthat would normally be invoked from a \f(asmake\fP rule, Xsuch as a compiler for a new language. XYou want to make both the program and the \f(asmake\fP rule Xwidely available. XWith standard \f(asmake\fP, you have two choices. XYou can hand out copies of the rules Xand get users to include it in their individual \f(asmakefiles\fP; Xor you can modify the \f(asmake\fP source, Xspecifically, the file containing the built-in rules. XThe first way is error-prone and quite inconvenient X(all those rules cluttering up your \f(asmakefile\fP Xwhen you should never need to even look at them). XThe second way can be impractical; Xin the development stage because the rules can change frequently Xand after that because you want to distribute your program Xto sites that may lack the \f(asmake\fP source. XAnd of course two such modifications may conflict with one another. X.pp XLogically, your rules belong in a place Xthat is less permanent than the \f(asmake\fP source Xbut not as transitory as individual \f(asmakefiles\fP. XA library file is such a place. XThe obvious way to access the contents of library files Xis with \f(as#include\fP, so \f(ascake\fP filters Xevery \f(ascakefile\fP through the C preprocessor. X.pp X\f(asCake\fP relies on this mechanism Xto the extent of not having \fIany\fP built-in rules at all. XThe standard \f(ascake\fP rules live in files Xin a library directory (usually /usr/lib/cake). XEach of these files contains rules about one tool or group of tools. XMost user \f(ascakefiles\fP \f(as#define\fP some macros Xand then include some of these files. XGiven that the source for program \f(asprog\fP Xis distributed among \f(asprog.c\fP, X\f(asaux1.c\fP, \f(asaux2.c\fP, and \f(asparser.y\fP, Xall of which depend on \f(asdef.h\fP, Xthe following would be a suitable \f(ascakefile\fP: X.(b M X.(p X#define MAIN prog X#define FILES prog aux1 aux2 parser X#define HDR def.h X X#include X#include X#include
X.)p X.)b XThe standard \f(ascakefiles\fP X\f(asYacc\fP and \f(asC\fP, as might be expected, Xcontain rules that invoke \f(asyacc\fP and \f(ascc\fP respectively. XThey also provide some definitions Xfor the standard \f(ascakefile\fP \f(asMain\fP. XThis file contains rules about programs in general, Xand is adaptable to all compiled languages X(e.g. it can handle NU-Prolog programs). XOne entry in \f(asMain\fP links the object files together, Xanother prints out all the sources, Xa third creates a \f(astags\fP file Xif the language has a command equivalent to \f(asctags\fP, Xand so on. X.pp X\f(asMake\fP needs a specialized macro processor; Xwithout one it cannot substitute the proper filenames in rule bodies. X\f(asFourth generation make\fP has not solved this problem Xbut it still wants the extra functionality of the C preprocessor, Xso it grinds its \f(asmakefiles\fP through both macro processors ! X\f(asCake\fP solves the problem in another way, Xand can thus rely on the C preprocessor exclusively. X.pp XThe original \f(asmake\fP mechanisms are quite rudimentary, Xas admitted by\*([<\*([[Feldman,\ 79\*(]]\*(>]. XUnfortunately, the C preprocessor is not without flaws either. XThe most annoying is that Xthe bodies of macro definitions may begin with blanks, Xand will if the body is separated from the macro name and any parameters Xby more than one blank (whether space or tab). X\f(asCake\fP is distributed with a fix to this problem Xin the form of a one-line change to the preprocessor source, Xbut this change probably will not work on all versions of Unix Xand definitely will not work for binary-only sites. X.\" X.sh 1 "The new features of \f(CBcake\fP" X.\" X.lp XThe above solutions to \f(asmake's\fP problems are useful, Xbut they do not by themselves enable \f(ascake\fP to handle new domains. XFor this \f(ascake\fP employs two important new mechanisms: Xdynamic dependencies and conditional rules. X.\" X.sh 2 "Dynamic dependencies" X.\" X.lp XIn some situations it is not convenient to list in advance Xthe names of the files a target depends on. XFor example, an object file depends Xnot only on the corresponding source file Xbut also on the header files referenced in the source. X.pp XStandard \f(asmake\fP requires all these dependencies Xto be declared explicitly in the \f(asmakefile\fP. XSince there can be rather a lot of these, most people either Xdeclare that all objects depend on all headers, which is wasteful, Xor declare a subset of the true dependencies, which is error-prone. XA third alternative is to use a program (probably an \f(asawk\fP script) Xto derive the dependencies and edit them into the \f(asmakefile\fP. X\*([[Walden,\ 84\*(]] describes one program that does both these things; Xthere are others. XThese systems are usually called \f(asmake\%depend\fP Xor some variation of this name. X.pp XThe problems with this approach are that Xit is easy to alter the automatically-derived dependencies by mistake, Xand that if a new header dependency is added Xthe programmer must remember to run \f(asmakedepend\fP again. XThe C preprocessor solves the first problem; Xthe second, however, is the more important one. XIts solution must involve scanning though the source file, Xchecking if the programmer omitted to declare a header dependency. XSo why not use this scan Xto \fIfind\fP the header dependencies in the first place ? X.pp X\f(asCake\fP attacks this point directly Xby allowing parts of rules to be specified at run-time. XA command enclosed in double square brackets\** may appear in a rule Xanywhere a filename or a list of filenames may appear. X.(f X\** XSingle square brackets (like most special characters) Xare meaningful to \f(ascsh\fP: they denote character classes. XHowever, we are not aware of any legitimate contexts where Xtwo square brackets \fImust\fP appear together. XThe order of members in such classes is irrelevant, Xso if a bracket must be a member of such a class Xit can be positioned away from the offending boundary X(unless the class is a singleton, Xin which case there is no need for the class in the first place). X.)f XFor the example of the C header files, the rule would be X.(b M X.(p X%.o: %.c [[ccincl %.c]] X cc -c %.c X.)p X.)b X.lp Xsignifying that \f(asx.o\fP depends on the files Xwhose names are listed in the output of the command X\f(asccincl x.c\fP\**, as well as on \f(asx.c\fP. X.(f X\** X\f(asCcincl\fP prints out the names of the files Xthat are \f(as#included\fP in the file named by its argument. X.)f XThe matching process would convert this rule to X.(b M X.(p Xx.o: x.c [[ccincl x.c]] X cc -c x.c X.)p X.)b Xwhich in turn would be \fIcommand expanded\fP to X.(b M X.(p Xx.o: x.c hdr.h X cc -c x.c X.)p X.)b Xif \f(ashdr.h\fP were the only header included in \f(asx.c\fP. X.pp XCommand patterns provide replacements Xfor \f(asfourth generation make's\fP Xdirectory searches and special macros. X\f(as[[find\ \ -name\ \ -print]]\fP Xdoes as good a job as the special-purpose \f(asmake\fP code Xin looking up source files scattered among a number of directories. X\f(as[[basename\ \ ]]\fP can do an even better job: X\f(asmake\fP cannot extract the base from the name of an RCS file. X.pp XA number of tools intended to be used in just such contexts Xare distributed together with \f(ascake\fP. X\f(asCcincl\fP is one. X\f(asSub\fP is another: its purpose is to perform substitutions. XIts arguments are two patterns and some strings: Xit matches each string against the first pattern, Xgiving values to its variables; Xthen it applies those values to the second pattern Xand prints out the result of this substitution. XFor example, in the example of section 2.3 Xthe \f(ascakefile\fP \f(asMain\fP would invoke Xthe command \f(as[[sub\ X\ X.o\ FILES]]\fP\**, Xthe value of \f(asFILES\fP being \f(asprog aux1 aux2 parser\fP, Xto find that the object files it must link together Xto create the executable \f(asprog\fP are X\f(asprog.o aux1.o aux2.o parser.o\fP. X.(f X\** X\f(asSub\fP uses \f(asX\fP as the character denoting variables. XIt cannot use \f(as%\fP, Xas all \f(as%\fP's in the command will have been substituted for Xby \f(ascake\fP by the time \f(assub\fP is invoked. X.)f X.pp X\f(asCake\fP allows commands to be nested inside one another. XFor example, the command \f(as[[sub\ X.h\ X\ [[ccincl\ file.c]]]]\fP Xwould strip the suffix \f(as.h\fP Xfrom the names of the header files included in \f(asfile.c\fP\**. X.(f X\** XAs the outputs of commands are substituted Xfor the commands themselves, X\f(ascake\fP takes care not to scan the new text, Xlest it find new double square brackets Xand go into an infinite loop. X.)f X.\" X.sh 2 "Conditional rules" X.\" X.lp XSometimes it is natural to say that X\f(asfile1\fP depends on \f(asfile2\fP X\fIif\fP some condition holds. XNone of the \f(asmake\fP variants provide for this, Xbut it was not too hard Xto incorporate conditional rules into \f(ascake\fP. X.pp XA \f(ascake\fP entry may have a condition associated with it. XThis condition, which is introduced by the reserved word \f(asif\fP, Xis a boolean expression built up with the operators X\f(asand\fP, \f(asor\fP and \f(asnot\fP from primitive conditions. X.pp XThe most important primitive Xis a command enclosed in double curly braces. XWhenever \f(ascake\fP considers applying this rule, Xit will execute this command Xafter matching, substitution and command expansion. XThe condition will return true if the command's exit status is zero. XThis runs counter to the intuition of C programmers, Xbut it conforms to the Unix convention Xof commands returning zero status when no abnormal conditions arise. XFor example, \f(as{{grep\ xyzzy\ file}}\fP returns Xzero (i.e. true) if xyzzy occurs in \f(asfile\fP Xand nonzero (false) otherwise. X.pp XConceptually, this one primitive is all one needs. XHowever, it has considerable overhead, Xso \f(ascake\fP includes other primitives to handle some special cases. XThese test whether a filename occurs in a list of filenames, Xwhether a pattern matches another, Xand whether a file with a given name exists. XThree others forms test the internal \f(ascake\fP status of targets. XThis status is \f(asok\fP Xif the file was up-to-date when \f(ascake\fP was invoked, X\f(ascando\fP if it wasn't but \f(ascake\fP knows how to update it, Xand \f(asnoway\fP if \f(ascake\fP does not know how to update it. X.pp XAs an example, consider the rule for RCS. X.(b M X.(p X%: RCS/%,v if exist RCS/%,v X co -u % X.)p X.)b XWithout the condition Xthe rule would apply to all files, Xeven ones which were not controlled by RCS, Xand even the RCS files themselves: Xthere would be no way to stop the infinite recursion X(\f(as%\fP depends on \f(asRCS/%,v\fP Xwhich depends on \f(asRCS/RCS/%,v,v\fP ...). X.pp XNote that conditions are command expanded Xjust like other parts of entries, Xso it is possible to write X.(b M X.(p X%: archive if % in [[ar t archive]] X ar x archive % X.)p X.)b X.\" .\" X.\" .sh 1 "Details" X.\" .\" X.\" .\" X.\" .sh 2 "Flags" X.\" .\" X.\" .lp X.\" Flags after patterns and actions X.\" \f(asCake\fP actions are very similar to \f(asmake\fP actions. X.\" .\" X.\" .sh 2 "Error handling" X.\" .\" X.\" .lp X.\" After error discovered the nodes involved arenot touched again ... X.\" Propagation of errors. X.\" Detect circular dependencies. X.\" .\" X.\" .sh 2 "Options" X.\" .\" X.\" .lp X.\" \f(asCake\fP has even more options than \f(asmake\fP\** does. X.\" .(f X.\" \** X.\" I refer to standard \f(asmake\fP; X.\" I do not have sufficient documentation on the other versions X.\" to say whether this point holds for them or not X.\" (but I expect that it would). X.\" .)f X.\" The ones that the two have in common generally do the same things. X.\" .\" -D ... X.\" .lp X.\" \f(asCake\fP looks for options in environment (in the envariable CAKE), X.\" on the command line (the usual place), and in the \f(ascakefile\fP, X.\" consulted in that order, with later definitions overriding earlier ones. X.\" The fact that options in the \f(ascakefile\fP X.\" can override those on the command line is somewhat unusual. X.\" Certainly some options (such as -n, print actions but do not execute) X.\" should not be placed in the \f(ascakefile\fP. X.\" On the other hand, X.\" the \f(ascakefile\fP cannot be consulted before the command line, X.\" as the command line may specify the name of the \f(ascakefile\fP ! X.\" So instead of adding code to check that such conflicts do not occur X.\" we trust the programmer not to do such silly things in the first place. X.\" .\" X.\" .sh 1 "Standard \f(ascakefile\fPs" X.\" .\" X.\" .lp X.\" Main and System do everything (really?) that 4g make do X.\" X.sh 1 "The implementation" X.\" X.sh 2 "Portability" X.\" X.lp X\f(asCake\fP was developed on a Pyramid 90x under 4.2bsd. XIt now runs on a VAX under 4.3bsd, Xa Perkin-Elmer 3240 and an ELXSI 6400 under 4.2bsd, Xand on the same ELXSI under System V. XIt has not been tested on either System III or version 7. X.pp X\f(asCake\fP is written in standard C, Xwith (hopefully) all machine dependencies Xisolated in the makefile and a header file. XIn a number of places it uses \f(as#ifdef\fP Xto choose between pieces of code Xappropriate to the AT&T and Berkeley variants of Unix X(e.g. to choose between \f(astime()\fP and \f(asgettimeofday()\fP). XIn fact, the biggest hassle we have encountered in porting \f(ascake\fP Xwas caused by the standard header files. XSome files had different locations on different machines X(\f(as/usr/include\fP vs. \f(as/usr/include/sys\fP), Xand the some versions included other header files X(typically \f(astypes.h\fP) while others did not. X.pp XAs distributed \f(ascake\fP is set up to work with \f(ascsh\fP, Xbut it is a simple matter to specify another shell at installation time. X(In any case, users may substitute their preferred shell Xby specifying a few options.) XSome of the auxiliary commands are implemented as \f(ascsh\fP scripts, Xbut these are small and it should be trivial Xto convert them to another shell if necessary. X.\" X.sh 2 "Efficiency" X.\" X.lp X\f(asFourth generation make\fP Xhas a very effective optimization system. XFirst, it forks and execs only once. XIt creates one shell, and thereafter, Xit pipes commands to be executed to this shell Xand gets back status information via another pipe. XSecond, it compiles its \f(asmakefiles\fP into internal form, Xavoiding parsing except when the compiled version Xis out of date with respect to the master. X.pp XThe first of these optimizations is an absolute winner. X\f(asCake\fP does not have it Xfor the simple reason that it requires a shell Xwhich can transmit status information back to its parent process, Xand we don't have access to one X(this feature is provided by neither of the standard shells, X\f(assh\fP and \f(ascsh\fP). X.pp X\f(asCake\fP could possibly make use of the second optimization. XIt would involve keeping track Xof the files the C preprocessor includes, Xso that the \f(asmakefile\fP can be recompiled if one of them changes; Xthis must be done by fourth generation make as well Xthough\*([<\*([[Fowler,\ 85\*(]]\*(>] does not mention it. XHowever, the idea is not as big a win for \f(ascake\fP Xas it is for \f(asmake\fP. XThe reason is as follows. X.pp XThe basic motivations for using \f(ascake\fP rather than \f(asmake\fP Xis that it allows one to express more complex dependencies. XThis implies a bigger system, Xwith more and slower commands Xthan the ones \f(asmake\fP usually deals with. XThe times taken by \f(ascake\fP and the preprocessor Xare insignificant when compared to the time taken Xby the programs it most often invokes at Melbourne. XThese programs, \f(asditroff\fP and \f(asnc\fP X(the NU-Prolog compiler that is itself written in NU-Prolog), Xare notorious CPU hogs. X.pp XHere are some statistics to back up this argument. XThe \fIoverhead ratio\fP is given by the formula X.EQ X{ "cake process system time" X~ + ~ "children user time" X~ + ~ "children system time" } Xover "cake process user time" X.EN XThis is justifiable given that the \f(ascake\fP implementor Xhas direct control only over the denominator; Xthe kernel and the user's commands Ximpose a lower limit on the numerator. X.\" .(b L X.\" .TS X.\" center allbox; X.\" c s s X.\" c c c X.\" n n n X.\" n n n X.\" n n n X.\" n n n X.\" n n n X.\" c n n. X.\" overhead ratio X.\" quantile munmurra mulga X.\" 10 1.65 1.63 X.\" 25 22.92 2.69 X.\" 50 67.55 4.87 X.\" 75 105.07 22.93 X.\" 90 164.91 178.60 X.\" average 81.75 69.75 X.\" .TE X.\" .(l C X.\" Table 1. X.\" .)l X.\" .)b X.\" .lp X.\" Table 1. displays statistics X.\" collected on every \f(ascake\fP run on two machines at Melbourne\**. X.pp XWe have collected statistics Xon every \f(ascake\fP run on two machines at Melbourne\**. X.(f X\** XOn munmurra (an EXLSI 6400), Xthe main application is Prolog compilation; Xon mulga (a Perkin-Elmer 3240), Xthe main applications are text processing Xand the maintenance of a big bibliography (over 36000 references). X.)f XThese statistics show Xthat the processes and system calls invoked by \f(ascake\fP Xtake on average about 70-80 times as much CPU time Xas the \f(ascake\fP process itself. XThis suggests that the best way to lower total CPU time Xis not to tune \f(ascake\fP itself Xbut to reduce the number of child processes. XTo this end, \f(ascake\fP caches Xthe status returned by all condition commands \f(as{{command}}\fP Xand the output of all command patterns \f(as[[command]]\fP. XThe first cache has a hit ratio of about 50 percent, Xcorresponding to the typical practice Xin which a condition and its negation Xselect one out of a pair of rules. XThe second cache has a hit ratio of about 75 percent; Xthese hits are usually the second and later occurrences Xof macros whose values contain commands. X.pp X\f(asCake\fP also uses a second optimization. XThis one is borrowed from standard \f(asmake\fP: Xwhen an action contains no constructs requiring a shell, X\f(ascake\fP itself will parse the action and invoke it through exec. XWe have no statistics to show Xwhat percentage of actions benefit from this, Xbut a quick examination of the standard \f(ascakefiles\fP Xleads us to believe that it is over 50 percent. X.\" .lp X.\" The overhead ratio average is fairly misleading. X.\" It is dominated by big jobs X.\" slow startup caused by planning phase X.pp XOverall, \f(ascake\fP can do a lot more than \f(asmake\fP, Xbut on things which \fIcan\fP be handled by \f(asmake\fP, X\f(ascake\fP is slightly slower than standard \f(asmake\fP Xand a lot slower than fourth generation make. XSince the main goal of \f(ascake\fP is generality, not efficiency, Xthis is understandable. XIf efficiency is important, X\f(asmake\fP is always available as a fallback. X.\" X.sh 2 "Availability" X.\" X.lp X\f(asCake\fP has been fairly stable for about six months now. XDuring this time it has been used without major problems Xby about twenty people here at Melbourne. XIt will be posted to the net in the near future, Xcomplete with auxiliary programs and manual entries. X.\" X.sh 1 "Acknowledgements" X.\" X.lp XJohn Shepherd, Paul Maisano, David Morley and Jeff Schultz Xhelped me to locate bugs Xby being brave enough to use early versions of \f(ascake\fP. XI would like to thank John Xfor his comments on drafts of this paper. X.lp XThis research was supported by Xa Commonwealth Postgraduate Research Award, Xthe Australian Computer Research Board, Xand Pyramid Australia. X.\" X.[] X.[- X.ds [F AT&T,\ 84 X.ds [Q AT&T X.ds [T Augmented version of make X.ds [B Unix System V - release 2.0 support tools guide X.ds [I AT&T X.ds [D April 1984 X.][ X.[- X.ds [F Feldman,\ 79 X.ds [A Stuart I. Feldman X.ds [T Make - a program for maintaining computer programs X.ds [J Software - Practice and Experience X.ds [V 9 X.ds [N 4 X.ds [D April 1979 X.nr [P 1 X.ds [P 255-265 X.][ X.[- X.ds [F Fowler,\ 85 X.ds [A Glenn S. Fowler X.ds [T A fourth generation make X.ds [J Proceedings of the USENIX Summer Conference X.ds [C Portland, Oregon X.ds [D June 1985 X.nr [P 1 X.ds [P 159-174 X.][ X.[- X.ds [F Gedye,\ 84 X.ds [A David Gedye X.ds [T Cooking with CAD at UNSW X.ds [I Joint Microelectronics Research Center, University of New South Wales X.ds [C Sydney, Australia X.ds [D 1984 X.][ X.[- X.ds [F Hirgelt,\ 83 X.ds [A Edward Hirgelt X.ds [T Enhancing make or re-inventing a rounder wheel X.ds [J Proceedings of the USENIX Summer Conference X.ds [C Toronto, Ontario, Canada X.ds [D June 1983 X.nr [P 1 X.ds [P 45-58 X.][ X.[- X.ds [F Walden,\ 84 X.ds [A Kim Walden X.ds [T Automatic generation of make dependencies X.ds [J Software - Practice and Experience X.ds [V 14 X.ds [N 6 X.ds [D June 1984 X.nr [P 1 X.ds [P 575-585 X.][ X.[- X.ds [F Weinberg,\ 71 X.ds [A Gerald M. Weinberg X.ds [T The psychology of computer programming X.ds [I Van Nostrand Reinhold X.ds [C New York X.ds [D 1971 X.nr [P 0 X.ds [P 288 X.][ SHAR_EOF if test 40457 -ne "`wc -c < 'paper.bib'`" then echo shar: "error transmitting 'paper.bib'" '(should have been 40457 characters)' fi fi exit 0 # End of shell archivas