Subversion Repositories planix.SVN

.HTML "Maintaining Files on Plan 9 with Mk

.TL

Maintaining Files on Plan 9 with Mk

.AU

Andrew G. Hume

andrew@research.att.com

Bob Flandrena

bobf@plan9.bell-labs.com

.AB

.PP

.CW Mk

is a tool

for describing and maintaining dependencies between

files.

It is similar to the

UNIX program

.CW make ,

but provides several extensions.

.CW Mk\fR'\fPs

flexible rule specifications, implied

dependency derivation, and parallel

execution of maintenance actions are

well-suited to the Plan 9 environment.

Almost all Plan 9 maintenance procedures

are automated using

.CW mk .

.AE

.NH 1

Introduction

.PP

This document describes how

.CW mk ,

a program functionally similar to

.CW make

[Feld79],

is used to maintain dependencies between

files in Plan 9.

.CW Mk

provides several extensions to the

capabilities of its predecessor that work

well in Plan 9's distributed, multi-architecture

environment.  It

exploits the power of multiprocessors by executing

maintenance actions in parallel and interacts with

the Plan 9 command interpreter

.CW rc

to provide a powerful set of maintenance tools.

It accepts pattern-based dependency specifications

that are not limited to describing

rules for program construction.

The result is a tool that is flexible enough to

perform many maintenance tasks including

database maintenance,

hardware design, and document production.

.PP

This document begins by discussing 

the syntax of the control file,

the pattern matching capabilities, and

the special rules for maintaining archives.

A brief description of

.CW mk\fR'\fPs

algorithm for deriving dependencies

is followed by a discussion

of the conventions used to resolve ambiguous

specifications.  The final sections

describe parallel execution

and special features.

.PP

An earlier paper [Hume87]

provides a detailed discussion of

.CW mk\fR'\fPs

design and an appendix summarizes

the differences between

.CW mk

and

.CW make .

.NH 1

The \f(CWMkfile\fP

.PP

.CW Mk

reads a file describing relationships among files

and executes commands to bring the files up to date.

The specification file, called a

.CW mkfile ,

contains three types of statements:

assignments, includes, and rules.

Assignment and include statements are similar

to those in C.

Rules specify dependencies between a

.I target

and its

.I prerequisites .

When the target and prerequisites are files, their

modification times determine if they

are out of date.  Rules often contain a

.I recipe ,

an

.I rc (1)

script that produces the target from

the prerequisites.

.PP

This simple

.CW mkfile

produces an executable

from a C source file:

.P1

CC=pcc

f1:	f1.c

	$CC -o f1 f1.c

.P2

The first line assigns the name of the portable ANSI/POSIX compiler

to the

.CW mk

variable

.CW CC ;

subsequent references of the form

.CW $CC

select this compiler.

The only rule specifies a dependence between the target file

.CW f1

and the prerequisite file

.CW f1.c .

If the target does not exist or if the

prerequisite has been modified more recently than

the target,

.CW mk

passes the recipe to

.CW rc

for execution.  Here,

.CW f1.c

is compiled and loaded to produce

.CW f1 .

.PP

The native Plan 9 environment

requires executables for

all architectures, not only the current one.

The Plan 9 version of the same

.CW mkfile

looks like:

.P1

</$objtype/mkfile

f1:	f1.$O

	$LD $LDFLAGS -o f1 f1.$O

f1.$O:	f1.c

	$CC $CFLAGS f1.c

.P2

The first line is an include statement

that replaces itself with the contents of the file

.CW /$objtype/mkfile .

The variable

.CW $objtype

is inherited from the environment and

contains the name of the target architecture.

The prototype

.CW mkfile

for that architecture defines architecture-specific variables:

.CW CC

and

.CW LD

are the names of the compiler and loader,

.CW O 

is the code character of the architecture.

The rules compile the source file into an object

file and invoke the loader to produce

.CW f1 .

Invoking

.CW mk

from the command line as follows

.P1

% objtype=mips mk

vc -w f1.c

vl $LDFLAGS -o f1 f1.k

%

.P2

produces the

.CW mips

executable of program

.CW f1

regardless of the current architecture type.

.PP

We can extend the

.CW mkfile

to build two programs:

.P1

</$objtype/mkfile

ALL=f1 f2

all:V:	$ALL

f1:	f1.$O

	$LD $LDFLAGS -o f1 f1.$O

f1.$O:	f1.c

	$CC $CFLAGS f1.c

f2:	f2.$O

	$LD $LDFLAGS -o f2 f2.$O

f2.$O:	f2.c

	$CC $CFLAGS f2.c

.P2

The target

.CW all ,

modified by the

.I attribute

.CW V ,

builds both programs.

The attribute identifies 

.CW all

as a dummy target that is

not related to a file of the same name;

its precise effect is explained later.

This example describes cascading dependencies:

the first target depends on another which depends on a third and

so on.

Here, individual rules build each

program; later we'll see how to do this with a

general rule.

.NH 1

Variables and the environment

.PP

.CW Mk

does not distinguish between its

internal variables and

.CW rc

variables in the environment.

When

.CW mk

starts, it imports each environment variable into a

.CW mk

variable of the same name.  Before executing a recipe,

.CW mk

exports all variables, including those

inherited from the environment,

to the environment in which

.CW rc

executes the recipe.

.PP

There are several ways for a

variable to take a value.

It can be set with an assignment statement,

inherited from the environment, or specified

on the command line.

.CW Mk

also maintains several special internal variables

that are described in

.I mk (1).

Assignments have the following decreasing order of precedence:

.LP

.in .7i

1)  Command line assignment

.br

2)  Assignment statement

.br

3)  Imported from the environment

.br

4)  Implicitly set by \f(CWmk\fP

.in 0

.LP

For example, a command line assignment overrides

a value imported from the environment.

.PP

All variable values are strings.  They can be

used for pattern matching and

comparison but not for arithmetic.

A

.I list

is a string containing several values separated by

white space.  Each member is

handled individually during pattern matching,

target selection, and prerequisite evaluation.

.PP

A

.I namelist

is a list produced by

transforming the members of an existing list.

The transform applies a pattern to each member,

replacing each matched string with a new string,

much as in the substitute command in

.I sam (1)

or

.I ed (1).

The syntax is

.P1

${\fIvar\fP:A%B=C%D}

.P2

where

.I var

is a variable.

The pattern

.CW A%B

matches a member beginning with the string

.I A

and ending with the string

.I B

with any string in between;

it behaves like the regular expression

.CW A.*B .

When a member of the

.I var

list

matches this pattern,

the string

.I C

replaces

.I A ,

.I D

replaces

.I B ,

and the matched string replaces itself.

Any of

.I A ,

.I B ,

.I C ,

or

.I D

may be the empty string.  In effect, a namelist is

generated by applying the

.I ed (1)

substitute command

.P1

	s/\fIA\fP(.*)\fIB\fP/\fIC\fP\e1\fID\fP/

.P2

to each member of a variable list.

.PP

Namelists are useful for generating

a list based on a predictable transformation.

For example,

.P1

	SRC=a.c b.c c.c

	OBJ=${SRC:%.c=%.v}

.P2

assigns the list \f(CW(a.v b.v c.v)\fP to

.CW OBJ .

A namelist may be used anywhere a variable is allowed

except in a recipe.

.PP

Command output is assigned to a variable

using the normal

.CW rc

syntax:

.P1

	var=`{rc command}

.P2

The command executes in an environment populated

with previously assigned variables, including those

inherited from

.CW mk\fR'\fPs

execution environment.

The command may

be arbitrarily complex; for example,

.P1

	TARG=`{ls -d *.[cy] | sed 's/..$//'}

.P2

assigns a list of the C and yacc source files in the current

directory, stripped of their suffix, to the variable

.CW TARG .

.NH 1

The include statement

.PP

The include statement

replaces itself with the contents of a file.

It is functionally similar to the C

.CW #include

statement but uses a different syntax:

.P1

	<\fIfilename\fP

.P2

The contents of the file are evaluated

as they are read.

An include statement may be used anywhere except

in a recipe.

.PP

Unlike

.CW make ,

.CW mk

has no built-in rules.  Instead,

the include statement allows generic rules

to be imported from a prototype

.CW mkfile ;

most Plan 9

.CW mkfiles

use this approach [Flan95].

.NH 1

Rules

.PP

A rule has four elements: targets,

prerequisites, attributes, and a recipe.

It has the form:

.P1

\fItargets\fP:\fIattributes\fP:\fIprerequisites\fP

	\fIrecipe\fP

.P2

The first line, containing the

targets, attributes, and prerequisites is

the

.I "rule header" ;

it

must begin at the left margin.

The recipe contains zero or more lines,

each of which begins with white space.

One or more targets must be specified but the

attributes, prerequisites, and recipe are optional.

A rule specifies

a dependency between the target(s) and its prerequisite(s),

the recipe brings the target(s)

up to date with the prerequisite(s) and

attributes modify

.CW mk\fR'\fPs

evaluation of the dependency.

.PP

Normally the target is a file that depends

on one or more prerequisite files.

.CW Mk

compares the modification times of each target

and each prerequisite; a target is considered out of date

when it does not exist or when a prerequisite has been modified

more recently.

When a target is out of date,

.CW mk

executes the

recipe to bring it up to date.

When the recipe completes,

the modification time of the target is checked and

used in later dependency evaluations.

If the recipe does not update the target,

evaluation continues with the out of date target.

.PP

A prerequisite of one rule

may be the target of another.  When

this happens, the rules cascade

to define a multi-step procedure.

For example,

an executable target depends on prerequisite

object files, each of which is a target

in a rule with a C source file as the prerequisite.

.CW Mk

follows a chain of dependencies until it encounters

a prerequisite that is not a target of another rule

or it finds a target that

is up to date.  It then

executes the recipes in reverse order to produce

the desired target.

.PP

The rule header is evaluated when the rule is read.

Variables are replaced by their values, namelists are

generated, and

commands are replaced by their

output at this time.

.PP

Most attributes modify

.CW mk\fR'\fPs

evaluation of a rule.

An attribute is usually a single letter but some

are more complicated.

This paper only discusses commonly used attributes;

see

.I mk (1)

for a complete list.

.PP

The

.CW V

attribute identifies a

.I virtual 

target;

that is, a target that is not a file.

For example,

.P1

clean:V:

	rm *.$O $O.out

.P2

removes executables and compiler intermediate files.

The target is virtual because it does not refer to a file named

.CW clean .

Without the attribute, the recipe would not be

executed if a file named

.CW clean 

existed.

The

.CW Q

attribute

silences the printing of a recipe before

execution.

It is useful when the output of a recipe is

similar to the recipe:

.P1

default:QV:

	echo 'No default target; use mk all or mk install'

.P2

.PP

The recipe is an

.CW rc

script.  It is optional but when it is

missing, the rule is handled specially, as described later.

Unlike

.CW make ,

.CW mk

executes recipes without interpretation.

After

stripping the first white space character from each line

it passes the entire recipe to

.CW rc 

on standard input.

Since

.CW mk

does not interpret a recipe,

escape conventions are exactly those of

.CW rc .

Scripts for

.CW awk

and

.CW sed

commands can be embedded exactly as they would

be entered from the command line.

.CW Mk

invokes

.CW rc

with the

.CW -e

flag, which causes

.CW rc

to stop if any command

in the recipe exits with a non-zero status; the

.CW E

attribute overrides this behavior and allows

.CW rc

to continue executing in the face of errors.

Before a recipe is executed, variables are exported

to the environment where they are available to

.CW rc .

Commands in the recipe may not read from

standard input because

.CW mk

uses it internally.

.PP

References to a variable can yield different

values depending on the location of the

reference in the

.CW mkfile .

.CW Mk

resolves variable references

in assignment statements and rule headers

when the statement is read.  Variable references

in recipes are evaluated by

.CW rc

when the recipe is executed; this

happens after the entire

.CW mkfile

has been read.  The value of a variable in a recipe

is the last value assigned in the file.  For example,

.P1

STRING=all

all:VQ:

	echo $STRING

STRING=none

.P2

produces the message

.CW none .

A variable assignment in a recipe

does not affect the value of the variable in the

.CW mkfile 

for two reasons.

First,

.CW mk

does not import values from

the environment when a recipe completes;

one recipe cannot pass a value through

the environment to another recipe.

Second, no recipe is executed until 

.CW mk

has completed its evaluation, so even if a variable

were changed,

it would not affect the dependency evaluation.

.NH 1

Metarules

.PP

A

.I metarule

is a rule based on a pattern.

The pattern selects a class of target(s) and 

identifies related prerequisites.

.CW Mk

metarules may select targets and prerequisites

based on any criterion that can be described by a pattern, not just

the suffix transformations associated with program

construction.

.PP

Metarule patterns are either

.I intrinsic

or regular expressions conforming to the

syntax of

.I regexp (6).

The intrinsic patterns are shorthand

for common regular expressions.

The intrinsic pattern

.CW %

matches one or more of anything; it is equivalent to

the regular expression

.CW `.+' .

The other intrinsic pattern,

.CW & ,

matches one or more of any characters except \f(CW`/'\fP

and \f(CW`.'\fP.

It matches a portion of a path and is

equivalent to the regular expression

.CW `[^./]+' .

An intrinsic pattern in a prerequisite references

the string matched by the same intrinsic pattern in the target.

For example, the rule

.P1

	%.v:	%.c

.P2

says that a file ending in

.CW .v

depends on a file of the same name with a

.CW .c

suffix:

.CW foo.v

depends on

.CW foo.c ,

.CW bar.v

depends on

.CW bar.c , 

and so on.

The string matched by an intrinsic pattern in the target

is supplied to the recipe in the variable

.CW $stem .

Thus the rule

.P1

%.$O:	%.c

	$CC $CFLAGS $stem.c

.P2

creates an object file for the target architecture from

a similarly named C source file.  If several object

files are out of date, the rule is applied repeatedly and

.CW $stem

refers to each file in turn.

Since there is only one

.CW stem

variable, there can only be one

.CW %

or

.CW &

pattern in a target;

the pattern

.CW %-%.c

is illegal.

.PP

Metarules simplify the

.CW mkfile

for building programs

.CW f1

and

.CW f2 :

.P1

</$objtype/mkfile

ALL=f1 f2

all:V:	$ALL

%:	%.$O

	$LD -o $target $prereq

%.$O:	%.c

	$CC $CFLAGS $stem.c

clean:V:

	rm -f $ALL *.[$OS]

.P2

(The variable

.CW $OS

is a list of code characters for all architectures.)

Here, metarules specify

compile and load steps for all C source files.

The loader rule relies on two internal variables

set by

.CW mk

during evaluation of the rule:

.CW $target

is the name of the target(s) and

.CW $prereq

the name of all prerequisite(s).

Metarules allow this

.CW mkfile

to be easily extended; a new program

is supported by adding its name to the third line.

.PP

A regular expression metarule must have an

.CW R

attribute.

Prerequisites may reference matching substrings in

the target using the form

.CW \e\fIn\fP

where

.I n

is a digit from 1 to 9 specifying the

.I n th

parenthesized sub-expression.  In a recipe,

.CW $stem\fIn\fP

is the equivalent reference.

For example, a compile rule could be

specified using regular expressions:

.P1

(.+)\e.$O:R:	\e1.c

	$CC $CFLAGS $stem1.c

.P2

Here,

.CW \e1

and

.CW $stem1

refer to the name of the target object file without the

suffix.  The variable

.CW $stem

associated with an intrinsic pattern is undefined

in a regular expression metarule.

.NH 1

Archives

.PP

.CW Mk

provides a special mechanism for maintaining an archive.

An archive member is referenced using the form

.CW \fIlib\fP(\fIfile\fP)

where

.I lib

is the name of the archive and 

.I file

is the name of the member.  Two rules define the

dependency between an object file and its membership

in an archive:

.P1

$LIB(foo.8):N:	foo.8

$LIB:	$LIB(foo.8)

	ar rv $LIB foo.8

.P2

The first rule establishes a dependency between the

archive member and the object file.

Normally,

.CW mk

detects an error when a target does not exist and the rule

contains no recipe; the

.CW N

attribute overrides this behavior because the subsequent rule

updates the member.

The second

rule establishes the dependency between the member and

the archive; its recipe inserts the member

into the archive.

This two-step specification allows the modification time

of the archive

to represent the state of its members.  Other rules

can then specify the archive as a prerequisite instead of

listing each member.

.PP

A metarule generalizes library maintenance:

.P1

LIB=lib.a

OBJS=etoa.$O atoe.$O ebcdic.$O

$LIB(%):N:	%

$LIB:	${OBJS:%=$LIB(%)}

	ar rv $LIB $OBJS

.P2

The namelist prerequisite of the

.CW $LIB

target generates archive member names for each object file name;

for example, 

.CW etoa.$O

becomes

.CW lib.a(etoa.$O) .

This formulation always updates all members.

This is acceptable for a small archive, but may 

be slow for a big one.

The rule

.P1

$LIB:	${OBJS:%=$LIB(%)}

	ar rv $LIB `{membername $newprereq}

.P2

only updates out of date object files.

The internal variable

.CW $newprereq

contains the names of the out of

date prerequisites.  The

.CW rc

script

.CW membername

transforms an archive member specification into a file name:

it translates

.CW lib.a(etoa.$O)

into

.CW etoa.$O .

.PP

The

.CW mkfile

.P1

</$objtype/mkfile

LIB=lib.a

OBJS=etoa.$O atoe.$O ebcdic.$O

prog:	main.$O $LIB

	$LD -o $target $prereq

$LIB(%):N:	%

$LIB:	${OBJS:%=$LIB(%)}

	ar rv $LIB $OBJS

.P2

builds a program by loading it with a library.

.NH 1

Evaluation algorithm

.PP

For each target of interest,

.CW mk

uses the rules in a

.CW mkfile

to build a data

structure called a dependency graph.  The nodes of

the graph represent targets and prerequisites;

a directed arc

from one node to another indicates that

the file associated with the first node depends

on the file associated with the second.

When the

.CW mkfile

has been completely read, the graph is analyzed.

In the first step, implied dependencies are resolved by

computing the

.I "transitive closure"

of the graph.

This calculation extends the graph to include all

targets that are potentially

derivable from the rules in the

.CW mkfile .

Next the graph is checked for cycles;

.CW make

accepts cyclic dependencies, but

.CW mk

does not allow them.

Subsequent steps

prune subgraphs that are irrelevant for producing the

desired target and verify that there is only one way

to build it.

The recipes associated with the

nodes on the longest path between the

target and an out of date prerequisite

are then executed in reverse order.

.PP

The transitive closure calculation is sensitive to

metarules; the patterns often select many potential targets

and cause the graph to grow rapidly.

Fortunately,

dependencies associated with the desired target

usually form a small part of the graph, so, after

pruning, analysis is tractable.

For example, the rules

.P1

%:	x.%

	recipe1

x.%:	%.k

	recipe2

%.k:	%.f

	recipe3

.P2

produce a graph with four nodes for each file in the

current directory.

If the desired target is

.CW foo ,

.CW mk

detects the dependency between it

and the original file

.CW foo.f

through intermediate dependencies on

.CW foo.k

and

.CW x.foo .

Nodes associated with other files are deleted during pruning because

they are irrelevant to the production of

.CW foo .

.PP

.CW Mk

avoids infinite cycles by evaluating

each metarule once.

Thus, the rule

.P1

%:	%.z

	cp $prereq $prereq.z

.P2

copies the prerequisite file once.

.NH 1

Conventions for evaluating rules

.PP

There must be only one

way to build each target.  However, during evaluation

metarule patterns often select potential targets that

conflict with the

targets of other rules.

.CW Mk

uses several conventions to resolve ambiguities

and to select the proper dependencies.

.PP

When a target selects more than one rule,

.CW mk

chooses a regular rule

over a metarule.

For example, the

.CW mkfile

.P1

</$objtype/mkfile

FILES=f1.$O f2.$O f3.$O

prog:	$FILES

	$LD -o $target $prereq

%.$O:	%.c

	$CC $CFLAGS $stem.c

f2.$O:	f2.c

	$CC f2.c

.P2

contains two rules that could build

.CW f2.$O .

.CW Mk

selects the last rule because its target,

.CW f2.$O ,

is explicitly specified, while the 

.CW %.$O

rule is a metarule.  In effect,

the explicit rule for

.CW f2.$O

overrides the general rule for building object files from

C source files.

.PP

When a rule has a target and prerequisites but no recipe,

those prerequisites are added to all other rules with

recipes that have the same target.

All prerequisites, regardless of where they were specified, are

exported to the recipe in variable

.CW $prereq .

For example, in

.P1

</$objtype/mkfile

FILES=f1.$O f2.$O f3.$O

prog:	$FILES

	$LD -o $target $prereq

%.$O:	hdr.h

%.$O:	%.c

	$CC $CFLAGS $stem.c

.P2

the second rule adds

.CW hdr.h

as a prerequisite of the compile metarule;

an object file produced from a C source file

depends on

.CW hdr.h

as well as the source file.  Notice that the recipe of 

the compile rule uses

.CW $stem.c

instead of

.CW $prereq

because the latter specification would attempt to compile

.CW hdr.h .

.PP

When a target is virtual and there is no other rule with

the same target,

.CW mk

evaluates each prerequisite.

For example, adding the rule

.P1

all:V:	prog

.P2

to the preceding example builds the executable

when either

.CW prog

or

.CW all

is the specified target.  In effect, the

.CW all

target is an alias for

.CW prog .

.PP

When two rules have identical rule headers and both have

recipes, the later rule replaces the former one.

For example,

if a file named

.CW mkrules

contains

.P1

$O.out:	$OFILES

	$LD $LFLAGS $OFILES