|
A Make Abstract Machine
Glenn Fowler <gsf@research.att.com>
AT&T Labs Research - Florham Park NJ
Many programming languages rely on abstractions to assist implementations
or to share common components with other languages.
For example, some C++ compilers produce
C as an intermediate step [ATT89],
some PROLOG compilers produce
WAM (Warren Abstract Machine) code [Warr83],
and some C, C++, and FORTRAN compilers generate intermediate code
for common back ends that do optimization and
machine code generation.
Abstractions allow complex language constructs to be implemented once
and well.
So why an abstraction for
make?
The concept behind
make
is simple, but the abundance of incompatible implementations
(make [Feld79],
augmented make [SV84],
build [EP84],
nmake [Fowl85][Fowl90],
mk [Hume87],
SunPro make [Palk87],
GNU make [SM89],
parallel make [Baal88],
POSIX make [POSI93],
Microsoft NMAKE [MICR90],
imake [DuBo93],
4.4 bsdmake [BSD93])
makes it difficult to determine the exact semantics for a given makefile.
Although makefiles specify the files under
make's
control, it is only the
make
execution that reveals the actions to be taken.
Traditionally this is where
make
programming support has been weak.
The usual dynamic output, a shell command trace, reveals little about
the relationships that triggered them.
The
make abstract machine
encompasses the static and dynamic nature of
make.
It has a simple instruction set that has been used
to abstract both
oldmake
(System V, BSD, GNU) and
nmake.
make
abstractions form the basis for makefile conversion tools, makefile porting,
regression testing, and makefile analysis.
MAM (make abstract machine) was born of necessity.
I use
nmake
to control all my software.
This poses no problem for personal work on my home platform,
but makes porting and shipping to incompatible platforms a headache.
Originally I maintained two sets of makefiles:
nmake
for local use and
oldmake
for porting.
This duplication was particularly annoying during the early
stages of software development when makefiles would change many times
in a single day.
To make matters worse, no amount of care could keep the
makefiles from diverging.
The only acceptable solution was to single source the makefile information
and generate the makefiles as needed.
Makefile generation has been done in the past
(makedepend [Leff83], [Wald84])
and is still popular
(imake [DuBo93], autoconf [ME04], automake [MT04], [VETT00]),
but separating make information from the make engine introduces yet another
divergence point between source and generated files.
Makefile generation is also expensive enough that it is rarely part of the
make
process (e.g., the makefiles are usually generated at the user's
discretion, not
make's).
To avoid inventing yet another makefile generation language,
I decided to use
nmake
makefiles as the generator input (influenced by a heavy investment in
nmake).
The temptation at this point was to code the entire generator within
nmake;
after all, it already had the machinery to convert makefiles into an
internal tree-based data structure.
A pass over this data structure could produce makefiles in any format.
But rather than weigh down
nmake
with the moral equivalent of
cb
(C program beautifier), the internal data structure was instead dumped
for a separate conversion program to consume.
At the same time there was considerable pressure from new
nmake
users to produce a program that converted
oldmake
makefiles to
nmake.
So a version of GNU
make
was modified in a similar manner to
nmake
and a separate generator was coded:
The prospect of adding more formats and converters to handle
mk,
GNU
make,
etc., made clear the need for a common abstraction.
Unlike
COMMON LISP,
there probably won't ever be a
common make;
there are just too many variants.
The differences are especially evident in
makefile syntax and dynamic execution.
Conditional makefiles, variable expansion syntax,
dependency graph generation and traversal,
shell interface, and concurrent target updates are typical divergence points.
But the static semantics are a different story.
Strip away the bells and whistles and syntactic goo and all
makes
become strikingly similar:
execute a minimal
(minimal
is the ultimate goal)
set of shell actions,
in the correct order,
to bring files up to date.
From a static viewpoint
make
manipulates two entities: rules and variables.
Rules are the nodes in the dependency graph and their names
usually associate one-to-one with file names.
A dependency arc from rule A to rule B is asserted as:
A : B
and reads: if B is newer than A then A is out of date.
An
action
may label a dependency arc:
A : B
action
and reads: if A is out of date then execute
action
to bring A up to date.
Variables are used to parameterize actions
and to avoid duplication in rule assertions.
They can be assigned:
variable = value
and expanded:
$(variable)
make
also supports
pattern metarules.
These are special rules that allow some assertions to be omitted.
For example, the assertion:
main.o : main.c
cc -c main.c
is not usually necessary because of the predefined %.o : %.c
(or the obsolete .c.o) metarule.
Metarules are a notational convenience; for any metarule based makefile
there exists an equivalent metarule-free makefile.
Conceptually, for all implementations,
make
expands makefile variables and metarules to generate a virtual makefile
that contains only rule assertions and actions.
This virtual makefile describes the complete dependency graph on which
make
operates.
MAM provides a simple, concise notation for describing
make
entities (variables, rules, actions) and relationships (dependencies).
The language has both a static and dynamic nature.
Static MAM specifies the complete
make
dependency graph; this can be used by makefile display and conversion programs.
Dynamic MAM traces
make
as it executes; this can be used for
make
regression testing or for communicating
make
actions to other tools, either in real time or as a logging technique.
At this point it may seem that MAM is shaping up to be just another
make,
but there is an important difference:
MAM does not define the
make
algorithm.
Although it specifies the dependency graph, it does not specify
``out of date'' or under what circumstances the actions are executed.
The intent is not to replace
make
but rather to provide a common language that communicates ``make'' to
other programs.
MAM syntax is akin to assembly: a sequence of instructions,
one per line, read from top to bottom.
The complete instruction set is listed in Figure 1.
The rule and variable definition instructions support static
makefile descriptions whereas
the runtime instructions provide dynamic information as
make
executes.
rule definition
make rule [ attribute ... ]
done rule [ attribute ... ]
prev rule [ attribute ... ]
exec rule [ action-line ]
variable definition
setv variable [ value ]
runtime
info type [ value ... ]
bind rule time [ binding ]
meta rule patterns source [ stem ]
init rule start
code rule exit-code time end [ attribute ... ]
miscellaneous
note [ comment ]
Figure 1: MAM instruction set
A detailed description follows.
- make rule [ attribute ... ]
-
- done rule [ attribute ... ]
-
A make/done pair defines the target rule named rule.
Nested make/done pairs define the dependencies: the enclosing
rule
is the parent and the enclosed
rules
are the prerequisites.
The optional
attributes
classify the rule or dependency relationship
(older
makes
may not emit any attributes):
- archive
-
An
archive
rule binds to a file that contains information on other files.
archive
usually marks libraries controlled by the
ar
command.
- dontcare
-
Marks files that need not exist.
If the file exists then its time is checked and propagated, otherwise
it is silently ignored.
- generated
-
Marks rules that are generated by a shell action.
- implicit
-
Marks the current rule as an implicit prerequisite of the enclosing
parent rule.
An implicit prerequisite can make the parent rule out of date
without triggering the parent action.
Implicit prerequisites usually correspond to #include prerequisites.
For example, if x.o is generated from x.c,
x.c is generated from x.y, and x.c
includes x.h, then x.h is an implicit prerequisite of x.c.
Touching x.h does not make x.c out of date but it does
make x.o out of date.
Implicit prerequisites are currently generated only by
nmake.
- joint
-
Marks one of a group of rules that are built by a single shell action.
- metarule
-
A
metarule
rule provides predefined
make
information; its action and prerequisite actions are not executed, but are
instead used to hold additional information.
- state
-
Marks state variable rules.
- virtual
-
A
virtual
rule is not associated with any file.
Some
makes
may optimize file system operations based on this.
- prev rule [ attribute ... ]
-
Used to reference rules that have already been defined by
make/done.
- exec rule [ action-line ]
-
Appends
action-line
to the shell action for
rule.
The
rule
name - names the rule in the current make/done nesting.
exec is not emitted until all prerequisite rules for
rule
have been defined.
- setv variable [ value ]
-
Assigns
value
to
variable.
A setv is required for each variable referenced in the mamfile,
even if its value is null, and it must occur before the first reference
of the variable.
This allows an analysis program to determine all variables
used in the makefile and the proper assignment order.
value
must be in
sh(1)
compatible syntax (all
make
variable references
expanded or eliminated).
- info type [ value ]
-
The info instruction is a catch-all for
make
execution environment information:
- info mam type parent YYYY-MM-DD [ generator ]
-
This is always the first instruction for each
make
instantiation.
It identifies the MAM
type
(static, dynamic, regress),
parent
id (00000 if this is the top level make),
version
(YYYY-MM-DD),
and optional version information on the program that generated
the mamfile
(generator).
This document describes the initial
1994-07-17
MAM version.
- info start time
-
Shows the
make
start time in seconds since the epoch.
- info pwd path
-
Shows the current working directory path.
- info view view
-
Shows the current view information if either viewpathing or union directories
are present.
- info finish time code
-
Shows the
make
finish time and exit code.
- info error|warning|debug|panic|info message
-
make
messages of varying severity.
- bind rule time [ binding ]
-
The bind instruction is emitted when
make
binds a rule to a file.
time
is the file modification time in seconds since the epoch.
If
binding
is omitted then the file name is
rule,
otherwise
binding
is the path name of the corresponding file.
Any of the
make
path search algorithms (VPATH, CPATH, .PATH* .SOURCE*) may cause
binding
to differ from
rule.
- init rule start
-
This instruction reports the wall time
start
just before the action for
rule
executes.
- meta rule patterns source stem
-
The meta instruction is emitted when a pattern metarule is used
to generate a target.
rule
is the target name,
patterns
is the pattern metarule name in the form
source-pattern>target-pattern,
source
is the main source prerequisite name, and
stem
is the % pattern stem.
Old style suffix rules are treated as if they were asserted as
pattern metarules.
- code rule exit-code time end [ attribute ... ]
-
This instruction reports, just as the
rule
action completes, the exit status
exit-code,
the (possibly updated)
rule
time
and the wall time
end.
The optional
attributes
classify the action status
(older
makes
may not emit any attributes):
- ignore
-
The action exited with an error exit status that was ignored.
- same
-
The action completed successfully but the
rule
was not updated.
- note [ comment ]
-
This is the comment instruction and is otherwise ignored.
To support multiple
make
processes in a dynamic MAM trace,
an optional process id number may prefix each instruction:
12345 info start 6789
54321 info finish 6790 0
...
The makefile in Figure 2 will be used to illustrate MAM.
The corresponding mamfile is listed in Figure 3,
annotated with line numbers for easy reference.
The first column contains mamfile line numbers and the second column contains
line numbers from the makefile in Figure 2.
1 DEBUG = -g -DDEBUG=1
2 CFLAGS = $(DEBUG)
3 cmd : cmd.o lib.o
4 $(CC) $(CFLAGS) -o cmd cmd.o lib.o
5 cmd.o : cmd.h lib.h
6 lib.o : lib.h
Figure 2: example makefile
01 - info mam static 00000 1994-07-17 GNU make version 3.81beta1
02 - make Makefile
03 - done Makefile
04 3 make cmd
05 3 make cmd.o
06 - meta cmd.o %.c>%.o cmd.c cmd
07 - make cmd.c
08 - done cmd.c
09 5 make cmd.h
10 5 done cmd.h
11 5 make lib.h
12 5 done lib.h
13 - setv CC cc
14 1 setv DEBUG -g -DDEBUG=1
15 2 setv CFLAGS ${DEBUG}
16 - setv OUTPUT_OPTION -o cmd.o
17 - exec cmd.o ${CC} ${CFLAGS} -c ${OUTPUT_OPTION} cmd.c
18 3 done cmd.o
19 3 make lib.o
20 - meta lib.o %.c>%.o lib.c lib
21 - make lib.c
22 - done lib.c
23 6 prev lib.h
24 - setv OUTPUT_OPTION -o lib.o
25 - exec lib.o ${CC} ${CFLAGS} -c ${OUTPUT_OPTION} lib.c
26 6 done lib.o
27 4 exec cmd ${CC} ${CFLAGS} -o cmd cmd.o lib.o
28 2 done cmd
Figure 3: example mamfile
The info mam instruction (line 01) identifies the file as a mamfile,
lists the MAM
version, and also identifies the program that generated the mamfile.
Variables are defined using setv (lines 14,15,16,24).
Lines 02 and 03 show that this
make
implementation allows the input makefile to be generated from rules
within the makefile itself.
Lines 04 and 05 come directly from the makefile, and line 07 is inferred
from the a metarule (line 06) in the predefined rules.
exec defines the rule actions (lines 17,25,27),
but is not emitted until after all
prerequisite rules have been defined.
Makefile variable references are converted to
shell syntax in the mamfile (lines 14,15,16,24).
This provides a common target language for actions
and also makes it possible to analyze makefiles using the shell.
Variable references may occur in all instructions, and are commonly
used to parameterize
rule
names:
setv INSTALLROOT ${HOME}
....
make ${INSTALLROOT}/include/std.h
From a human standpoint MAM is too verbose,
but this is exactly what makes it an attractive input language
for program analysis.
The close connection between MAM and
shell
is also intentional; it allows most MAM
analyzers to be written directly in
shell.
Also, the analysis scripts are short enough
that a few are included in this paper.
Rather than get bogged down in shell compatibility issues (and for brevity)
the example scripts use
ksh93
[BK94], which provides builtin arithmetic and associative arrays.
For portability the scripts have also been written in V7 shell [Bour78],
but the V7 scripts are much larger (up to 10 times) and noticeably
slower, mainly because external commands must be used as a substitute for
ksh93
features.
The first program generates a shell script that contains the
variable definitions and actions that bring all mamfile targets up to date.
Such a script could be used to bootstrap software on systems that
have no
make.
This is how
nmake
source was ported from 1985 to 1989.
Given a mamfile,
generating a bootstrap script is trivial:
simply grab the setv and
exec instructions and convert to shell syntax:
setv variable [ value ]
converts to
variable="value"
and
exec rule [ action-line ]
converts to
action-line
The variable assignments and commands are in the correct order because,
by definition,
setv instructions are emitted before the first variable reference and
exec instructions are not emitted until all prerequisite
rules have been defined.
The script,
mamsh,
is listed in Figure 4.
sed -n -e 's/^setv \([^ ]*\) \(.*\)/\1="${\1-\2}"/p' -e 's/^exec [^ ]* //p'
Figure 4: mamsh: convert MAM to shell script
The resulting
mamsh
bootstrap script for the makefile in Figure 2 is:
CC="${CC-cc}"
DEBUG="${DEBUG--g -DDEBUG=1}"
CFLAGS="${CFLAGS-${DEBUG}}"
OUTPUT_OPTION="${OUTPUT_OPTION--o cmd.o}"
${CC} ${CFLAGS} -c ${OUTPUT_OPTION} cmd.c
OUTPUT_OPTION="${OUTPUT_OPTION--o lib.o}"
${CC} ${CFLAGS} -c ${OUTPUT_OPTION} lib.c
${CC} ${CFLAGS} -o cmd cmd.o lib.o
Generating a graphical representation of makefile dependencies is
slightly more complicated.
Figure 5 lists
mamdot,
a script that converts mamfile input into a
dot
[GV99] specification.
dot
input consists attributes and nested edge constructs of the form
"A" -> { "B" "C" ... }
that reads: an edge connects node A to node B,
node A to C, etc.
mamdot
uses the make and prev instructions to build the prerequisite
lists (lines 21,25) and the done instruction to print
the non-empty lists (line 27).
It follows typical MAM script form:
-
initialize (lines 01-07)
-
check options and arguments (none in this example)
-
read each mamfile line and case on each instruction (lines 08-36),
where make and done correspond to push and pop operations
(lines 21,27)
-
clean up (line 37)
The
dot
specification generated from the example mamfile is:
digraph mam {
rankdir = LR
node [ shape = box ]
"cmd.o" -> {
"cmd.c"
"cmd.h"
"lib.h" }
"lib.o" -> {
"lib.c"
"lib.h" }
"cmd" -> {
"cmd.o"
"lib.o" }
}
01 integer level=0
02 typeset -A pwd top
03 list[0]=all
04 top[0]=1
05 print "digraph mam {"
06 print "rankdir = LR"
07 print "node [ shape = box ]"
08 while read -r label op arg arg2 arg3 args
09 do [[ $label == [[:digit:]]* ]] || {
10 arg3=$args
11 arg2=$arg
12 arg=$op
13 op=$label
14 label=0
15 }
16 [[ ${top[$label]} || $arg == */* || $op != @(make|prev|done) ]] || {
17 [[ $op == make ]] && print "\"$label::$arg\" [ label = \"$arg\" ]"
18 arg=$label::$arg
19 }
20 case $op in
21 make) list[level]=${list[level]}$'\n'\"$arg\"
22 level=level+1
23 list[level]=
24 ;;
25 prev) list[level]=${list[level]}$'\n'\"$arg\"
26 ;;
27 done) [[ ${list[level]} ]] &&
28 print "\"$arg\" -> {${list[level]} }"
29 level=level-1
30 ;;
31 info) case $arg in
32 pwd) [[ $arg3 == "." ]] && top[$label]=1 ;;
33 esac
34 ;;
35 esac
36 done
37 print "}"
Figure 5: mamdot: convert MAM to dot input
The resulting
dot
layout is:
For graphs of actual makefiles see the AST
nmake
makefile graph (generated by nmake -nFMstatic)
for the GNU make-3.81beta1 at
http://www.research.att.com/~gsf/mam/gmake-nmake.ps.gz
and the corresponding GNU
make
makefile (generated by gmake -nFMstatic) at
http://www.research.att.com/~gsf/mam/gmake-gmake.ps.gz
.
Figure 6 lists
mamexec,
a script that implements
make
with state using mamfiles rather than makefiles as input.
A script similar to this (except written in ~300 lines of V7 shell)
is a major component of a software distribution
system that has been used to ship
ksh
and
nmake
to a wide variety of systems and requires only a V7
sh,
a C compiler,
ls,
comm,
sort
and
sed.
01 typeset beg="(set -ex;" end=") </dev/null" exec=eval mamfile=Mamfile
02 typeset -i accept=0 force=0 level=0
03 typeset -A list same
04 while getopts "AFf:[mamfile]n" opt
05 do case ${opt#${opt%?}} in
06 A) accept=1 ;;
07 F) force=1 ;;
08 f) mamfile=$OPTARG ;;
09 n) exec=print beg= end= ;;
10 esac
11 done
12 [[ $opt == "?" ]] && exit 1
13 ml=$mamfile.ml ms=$mamfile.ms
14 [[ $force == 0 && -f $ml && -f $ms ]] &&
15 for i in $(ls -ld $(<$ml) 2>/dev/null|sort|comm -12 $ms -|sed 's/.* //')
16 do same[$i]=1; done
17 while read -r op arg data
18 do case $op in
19 setv) eval val='$'$arg
20 [[ $level != 0 || $val ]] && eval $arg='$data </dev/null'
21 ;;
22 make) level=level+1
23 eval arg=$arg
24 [[ " $data " == *" metarule "* ]] && same[$arg]=1 && continue
25 name[level]=$arg cmds[level]= list[$arg]=1
26 ;;
27 prev) eval arg=$arg
28 [[ ! ${same[$arg]} ]] && same[${name[level]}]=
29 ;;
30 exec) [[ ! ${cmds[level]} ]] && cmds[level]=$data ||
31 cmds[level]=${cmds[level]}$'\n'$data
32 ;;
33 done) eval arg=$arg
34 [[ ! ${same[$arg]} ]] &&
35 { [[ ${cmds[level]} ]] &&
36 { $exec "$beg${cmds[level]}$end" || exit; }
37 same[${name[level-1]}]=; }
38 level=level-1
39 ;;
40 esac
41 done <$mamfile
42 [[ $accept == 1 || $exec == eval ]] &&
43 { print ${!list[@]} > $ml; ls -ld ${!list[@]} 2>/dev/null|sort > $ms; }
Figure 6: mamexec: make with state
A common reaction to
mamexec
(especially to its V7 counterpart) is:
Why would anyone want
make
in shell?
The answer is bootstrap portability:
-
The V7
mamexec
works the same on all UNIX® system variants that support the shell.
It has even been used to bootstrap
ksh
and
nmake
on Microsoft Windows NT§
[ 
Microsoft Windows and Microsoft Windows NT are trademarks
of the Microsoft Corporation.
] 
(Microsoft
NMAKE
is completely different from
oldmake
and AT&T
nmake).
-
mamexec
is small enough that it can be shipped along with the source
to be built.
-
mamexec
avoids
make
implementation differences on recipient systems.
Such differences are often difficult to debug, especially when no
login is available.
-
By operating from mamfiles,
mamexec
also avoids
make
implementation differences on the sending system.
These are difficult to debug because features in the home environment
are easy to take for granted.
MAM inherently freezes
make
features into a common language.
-
Unlike
oldmake,
mamexec
handles actions with embedded shell
here documents
and multi-line case statements.
To be fair,
mamexec
does not implement full
make
semantics.
It only has four options:
- -A
-
Accept current files as up to date.
- -F
-
Force all files to be out of date.
- -f mamfile
-
The input mamfile is mamfile instead of the default Mamfile.
- -n
-
Show actions but do not execute.
mamexec
does not have target selection: all targets that are out of date are built
(i.e., it cannot just make main.o;
adding this would cost about 10 lines).
To its advantage, however,
mamexec
implements a state algorithm for testing ``out of date.''
In
oldmake
a target is out of date if its modification time is older than the modification
time of any of its prerequisites.
In the state algorithm the modification time
for each target is saved in a
statefile
just before
make
exits.
A target is out of date if its current modification time is different
from its state time (saved in the statefile)
or
if any of its prerequisites are out of date.
The state algorithm detects changes that occur when old files are restored,
a situation that
oldmake
cannot handle.
This may happen when
cpio
or
tar
archives are read into the current source tree,
but also happens more frequently under viewpathing
(using VPATH in
oldmake,
GNU
make,
and
nmake,
or
vpath
in
nDFS
[KK90] or
union mounts
in Plan 9 and 4.4 BSD)
when top layer files are removed to expose older lower layer files.
More importantly, the state algorithm allows an action to chose
not
to update its target file(s).
Unlike
oldmake,
the state algorithm will not trigger such actions the next time.
This supports smart actions that may determine ``out of date''
by mechanisms more complex than modification time.
The
mamexec
source is straightforward.
Lines 01-13 initialize the local variables (lines 01-02),
associative arrays (line 03),
and options (lines 04-13).
Lines 15-16 compare the current state with the previous state (if it exists).
same[rule] is 1 if
rule's
current modification time is the same as the statefile modification time
(ls determines the time, comm and sort determine entries that
have not changed).
A rule is out of date if same[rule] is null.
The main loop (lines 17-38) collects prerequisites and actions and executes
actions for out of date rules (line 33).
Only builtin commands are executed in the main loop.
setv assigns variable that have no previous value
unless the setv occurs inside a make/done nesting (line 20).
Lines 39-40 update the statefile before the script exits.
The state consists of 2 files; mamfile.ml contains the list of all
rules and mamfile.ms contains the state time and name for all rules.
user sys user+sys
GNU make 0.35 0.30 0.65
oldmake 0.43 1.08 1.51
mamexec 1.23 0.40 1.65
nmake 0.85 0.95 1.80
Figure 7: comparative make -n times
Figure 7 is a table of user+sys times on an unloaded SPARC 2
for various
make -n
commands running on a makefile (or mamfile) with 97 up to date rules and
223 action lines.
Since
mamexec
is a shell script and the other
makes
are compiled programs one would assume that
mamexec
would perform poorly, but this is not the case.
There are a few reasons for this:
the mamfile parse is simple compared to makefiles, and all rule
bindings are precomputed in the mamfile
(i.e., metarules and file path searches have already been
applied by the mamfile generator).
nmake
is slightly slower in this example because it computes the implicit
prerequisites that have already been asserted in the mamfile and
oldmake
makefiles, and the startup cost for this outweighs the small makefile size.
Makefile conversion, last mentioned in the introduction, hasn't been forgotten.
Original plans were to describe an 800 line, 5 year old C program that
converts MAM to
oldmake
makefiles, but after cleaning up the
mamdot
and
mamexec
scripts for publication a
mamold
script precipitated out.
Figure 8 lists
mamold,
a MAM to
oldmake
makefile converter.
01 : convert MAM to oldmake makefile
02
03 # generate implicit+explicit in list
04
05 function closure {
06 typeset i j
07 for i
08 do [[ " $list " == *" $i "* ]] && continue
09 list="$list $i"
10 for j in ${implicit[$i]}
11 do closure $j; done
12 done
13 }
14
15 typeset -A prereqs implicit action
16 typeset -i level=0
17 typeset rule list order target
18 format="op arg val"
19 read -r $format
20 case $op in
21 +([0-9])) format="label $format" ;;
22 esac
23 print "# # makefile generated by mamold.sh # #"
24 while read -r $format
25 do case $op in
26 setv) [[ $val == *'${mam_'* ]] && val=${val//'${mam_'/'$${mam_'}
27 print -r -- $arg = $val
28 ;;
29 make|prev) rule=${target[level]}
30 [[ " $val " == *" implicit "* ]] &&
31 implicit[$rule]="${implicit[$rule]} $arg" ||
32 prereqs[$rule]="${prereqs[$rule]} $arg"
33 [[ $op == prev ]] && continue
34 target[++level]=$arg
35 [[ " $order " != *" $arg "* ]] && order="$order $arg"
36 ;;
37 exec) [[ $arg == - ]] && arg=${target[level]}
38 [[ ${action[$arg]} ]] &&
39 action[$arg]=${action[$arg]}'$(newline)\'$'\n'$'\t'$val ||
40 action[$arg]=$'\t'$val
41 ;;
42 done) level=level-1
43 ;;
44 esac
45 done
46
47 # dump the assertions
48
49 for rule in $order
50 do [[ ! ${prereqs[$rule]} && ! ${action[$rule]} ]] && continue
51 list=
52 closure ${prereqs[$rule]} && print && print -r -- "$rule :$list"
53 [[ ${action[$rule]} ]] && print -r -- "${action[$rule]}"
54 done
Figure 8: mamold: MAM to oldmake makefile converter
Since it generates
oldmake
makefiles,
mamold
must differentiate between explicit (prereqs[rule])
and implicit (implicit[rule]) prerequisites
for a given
rule
(lines 27-29).
setv collects the variable names (line 23) so that the shell style
variable references can be converted to
make
style by the convert function (lines 01-07).
The assertions are emitted in mamfile order (lines 32,43-48), and the
closure function emits the transitive closure of the
explicit and implicit prerequisites.
Embedded newlines in actions have always been a problem for
oldmake
because it traditionally executes action lines one at a time, each in
a separate shell.
Some shell constructs, such as
here documents
and multi-line
case statements, cannot appear in
oldmake
actions.
So
mamold
does not play as an important a role as
mamexec
in the software porting process.
MAM deliberately mimics the
make
algorithm, so adding MAM to
make
is a simple task.
The make and done instructions bracket the
make
inner loop, called
doname()
in the original and
update_file_1()
in GNU
make.
Often MAM instructions correspond to portions of the debug trace output,
as happens with GNU
make
and System V
oldmake.
The exec instruction is just an intercept of action execution.
Actions may be parameterized by first emitting setv for each
parameter variable:
setv CC cc
setv CCFLAGS
...
and then initializing the
make
variable values to expand to their shell counterparts:
CC = $${CC}
CFLAGS = $${CCFLAGS}
...
A MAM-instrumented
make
has these options or their equivalent:
- -F, --force
-
Force all targets to be out of date.
- -M, --mam=type[,subtype][:file[:parent[:directory]]]
-
Write make abstract machine output to
file
if specified or to the standard output otherwise.
If
parent
!=0 then it is the process id of a parent MAM process.
directory
is the working directory of the current MAM process relative
to the root MAM process,
type
must be one of:
- dynamic
-
Generate a MAM trace of an actual build.
Dynamic MAM output is flushed as each event occurs to support real time tracing.
- regress
-
Generate MAM for regression testing; labels, path names and time stamps are
canonicalized for easy comparison.
- static
-
Generate a MAM representation of the makefile assertions.
- -N, --never|really-just-print
-
Don't execute any shell actions, including commands prefixed by
+
and commands containing
$(MAKE)
or
${MAKE}.
All other
make
options and arguments apply as usual: if you want a static mamfile of
the install target then
run make -nFMstatic install;
if you want a static mamfile of the default target then
run make -nFMstatic.
There is no MAM analogue for makefile conditionals:
# generic makefile conditional syntax
if this is release x of system y with hardware z
command : x_y_z.c
endif
Basically MAM describes makefiles relative to the current environment,
just as the C preprocessing phase freezes #if and #ifdef
conditionals and macro expansions for C programs.
This is a drawback
if
MAM is viewed as a replacement makefile language.
Although MAM started out to support makefile conversion,
it has inspired the development
of several different programs that aid makefile analysis, generate
shell scripts for software porting,
report software updates as
make
executes,
and even replace a generous subset of
make
itself.
MAM is stable and has been used to port and analyze software within AT&T
since 1989.
This paper retains its 1994 form, including some motivating factors that
may be moot in the 21st century.
Minor adjustments have been made to keep the details up to date with the
current implementation.
The web posting at
http://www.research.att.com/~gsf/mam/
is its only official publication.
A MAM patch for GNU
make
is available at
http://www.research.att.com/~gsf/mam/make-3.81beta1-mam.patch
.
ksh93
and
perl
versions of
mamdot(1)
are included in the patch.
dot(1)
and
gvpr(1)
are available at
http://www.research.att.com/sw/tools/graphviz/
.
The
AST
(AT&T Software Technology) software originally used a convoluted
mamexec(1)
to bootstrap
nmake(1)
and
ksh(1);
the current bootstrap build is handled by the standalone,
configure-free
mamake(1)
program.
mamake(1)
transparently handles viewpathing
(via
VPATH)
and recursive Makefile (Mamfile) ordering,
fundamental parts of the
AST
configuration management scheme.
To generate a postscript dependency graph for a any GNU
make
setup:
gmake -nFMstatic | mamdot | dot -Tps > out.ps
If you only want the graph of the top level makefile in
a recursive make setup then use -N instead of -n,
or if you want the graph of a specific target, then add it
to the GNU
make
command line.
To generate a postscript dependency graph for a any AST
nmake
setup:
nmake -nFMstatic | mamdot | dot -Tps > out.ps
Recursive make configurations may generate duplicate edges.
These can be merged by inserting the following graphviz command
between mamdot and dot:
gvpr '
BEG_G {
graph_t g = graph ("merged", "DS");
graph_t sg = copy (g,$);
edge_t e;
}
E {
e = clone(g,$);
subedge(sg,e);
}
END_G {
fwriteG(sg,1);
}'
- [ATT89]
-
UNIX System V AT&T C++ Language System: Release 2.1 Release Notes,
AT&T, Select Code 307-160, 1989.
- [Ball88]
-
Erik Ballbergen,
Design and Implementation of Parallel Make,
USENIX Computing Systems, 135-158, Spring 1988.
- [BK89]
-
Morris Bolsky and David G. Korn,
The KornShell Command and Programming Language,
Prentice Hall, 1989.
- [BK94]
-
Morris Bolsky and David G. Korn,
a revised edition of [BK89],
to be published.
- [Bour78]
-
S. R. Bourne,
The UNIX Shell,
AT&T Bell Laboratories Technical Journal,
Vol. 57 No. 6 Part 2, pp. 1971-1990, July-August 1978.
- [BSD93]
-
4.4 BSD make,
4.4 BSD UNIX distribution.
- [DuBo93]
-
Paul DuBois,
Software Portability with imake,
O'Reilly and Associates, 1993.
- [EP84]
-
B. Erickson and J. F. Pellegrin,
Build - A Software Construction Tool,
AT&T Bell Laboratories Technical Journal Vol. 63 No. 6 Part 2,
pp. 1049-1059, July-August 1984.
- [Feld79]
-
S. I. Feldman,
Make - A Program for Maintaining Computer Programs,
Software - Practice and Experience, Vol. 9 No. 4, pp. 256-265, April 1979.
- [Fowl85]
-
G. S. Fowler,
The Fourth Generation Make,
USENIX Portland 1985 Summer Conference Proceedings, pp. 159-174, 1985.
- [Fowl90]
-
G. S. Fowler,
A Case for make,
Software - Practice and Experience,
Vol. 20 No. S1, pp. 35-46, June 1990.
- [GN99]
-
E. R. Gansner and S. C. North,
An open graph visualization system and its application to software engineering,
Software - Practice and Experience, 00(S1), 1-5 (1999),
http://www.research.att.com/sw/tools/graphviz/
.
- [Hume87]
-
A. G. Hume,
Mk: a successor to make,
USENIX Phoenix 1987 Summer Conference Proceedings, pp. 445-457, 1987.
- [KK90]
-
D. G. Korn and E. Krell,
A New Dimension for the Unix File System,
Software - Practice and Experience,
Vol. 20 No. S1, pp. 19-33, June 1990.
- [Leff84]
-
Samuel J. Leffler,
Building 4.2BSD UNIX Systems with Config,
UNIX System Manager's Manual,
University of California, Berkeley, July 1984.
- [ME04]
-
GNU Autoconf,
David MacKenzie and Ben Elliston,
http://www.gnu.org/software/autoconf/
.
- [MICR90]
-
Microsoft C: Advanced Programming Techniques,
Microsoft Corporation, pp. 103-132, 1990.
- [MT04]
-
GNU Automake,
David MacKenzie and Tom Tromey,
http://www.gnu.org/software/automake/
.
- [Palk87]
-
R. Palkovic,
SunPro: The Sun Programming Environment,
M. Hall (ed.),
A Sun Technical Report, Sun Microsystems, Inc., pp. 67-86, 1987.
- [POSI93]
-
IEEE Standard for Information Technology -
Portable Operating System Interface (POSIX) -
Part 2: Shell and Utilities (Volume 1), pp. 666-679, IEEE, 1993.
- [SM89]
-
R. M. Stallman and R. McGrath,
GNU Make - A Program for Directing Recompilation,
Edition 0.1 Beta, March 1989.
- [SV84]
-
Augmented Version of Make,
UNIX System V - Release 2.0 Support Tools Guide, pp. 3.1-19, April 1984.
- [Wald84]
-
Kim Walden,
Automatic Generation of Make Dependencies,
Software - Practice and Experience,
Vol. 14 No. 6, pp. 575-585, June 1984.
- [Warr83]
-
David H. D. Warren,
An abstract Prolog instruction set,
Technical note 309, SRI Project 4776,
Stanford Research Institute International, Menlo Park, CA, October 1983.
- [VETT00]
-
GNU Autoconf, Automake, and Libtool,
Gary V. Vaughan, Ben Elliston, Tom Tromey, and Ian Lance Taylor,
1st edition, New Riders Publishing, ISBN 1578701902, October 2000.
|
|
Glenn Fowler |
|
|
Information and Software Systems Research |
|
|
AT&T Labs Research |
|
|
Florham Park NJ |
|
|
February 14, 1994 |
|