MakeDoDoc.tioga
Spreitzer, September 3, 1985 10:26:38 pm PDT
MakeDO
CEDAR 6.0 — FOR INTERNAL XEROX USE ONLY
MakeDo
Mike Spreitzer
© Copyright 1985 Xerox Corporation. All rights reserved.
Abstract: MakeDo automatically determines dependencies between files, and can issue whatever commands are necessary to bring derived files up to date.
Created by: Mike Spreitzer
Maintained by: Mike Spreitzer <Spreitzer.pa>
Keywords: Make, Dependency, Consistency, Derive, File, DF File, Command, Compile, Bind, Order, Sequence
XEROX   Xerox Corporation
    Palo Alto Research Center
    3333 Coyote Hill Road
    Palo Alto, California 94304

For Internal Xerox Use Only
0. Introduction
MakeDo is a package for determining dependency relations between Cedar objects (usually files), and executing actions to bring these objects up-to-date. It is less amibitious than the System Modelling project, in that it has a lower-level understanding (e.g., source and binary files, instead of Cedar modules), and in that it derives the dependencies itself in a standard way from the environment, rather than reading a model.
1. Theory
1.1 The Dependency Graph
There are objects. An object is like a variable: it has some interesting contents, and they may vary over time. At any given time, an object has a create date, which is the most recent time at which the object's contents were set. A UNIX file is an example of this. A Cedar FS filename-without-version is another example (take the create date and contents of the current highest version to be the create date and contents of the object). An object may not exist, which means its contents can not be examined, and its create date is MakeDo.notExistTime. This is like a NIL pointer, or the name of a file that does not exist (have any versions).
There are actions. An action has something which can be executed, which so far must be a Command Tool command. An action also has some inputs (objects whose contents it reads), and some outputs (objects whose contents it sets). Some of the inputs may be optional, which means that if they don't exist, the action is happy to not read their contents. An action also has some determiners (some of which may also be optional). These are objects, the contents of which are used in determining some variable aspects of the action. The variable aspects of an action are (so far) its executable part and its set of inputs. An example action is [command: "Compile []<>P>Rope", inputs: {[]<>P>Basics.BCD, []<>P>PrincOps.BCD, []<>P>Rope.Mesa}, outputs: {[]<>P>Rope.BCD}, determiners: {[]<>P>Rope.Mesa, []<>P>Rope.BCD.Switches}].
There are some simplifying assumptions. Each object is an output of at most one action. None of an action's inputs or determiners depends (transitively) on any of its outputs (among other things, this implies that no object can be both an input and an output of the same action).
There are dependencies. An action depends on its determiners. Effectively, each of an action's outputs depends on all of its inputs, but in fact we think of this in two parts: an action depends on its inputs, and an output depends on the action (if any) that produces it.
There is a concept of up-to-date. An action's variable aspects are up-to-date if they were derived from the current contents of the action's determiners. An action's outputs are up-to-date if <rules that vary with action class>.
1.2 The Action-Class Registry
All Compile or Bind actions belong to the CompileAndBind action class. All Lupine actions belong to the Lupine action class. An action class specifies the rules for discovering dependencies, the rules for determining when an output is out-of-date, and the rules for how the variable parts of an action are computed from its determiners. MakeDo maintains a registry of action classes. It initially contains two (CompileAndBind and Lupine); clients may add more.
The CompileAndBind action class uses version stamps to determine when outputs are up-to-date. This is consistent with the way the Compiler and Binder work. This class uses an optional extra determiner, file Foo.BCD.Switches (for the action "Compile Foo"), to get the switches for the compile or bind command. The file should contain the switch string, including introductory character (currently a dash ('-)).
The Lupine action class uses create dates to determine when outputs are up-to-date. It also uses an optional extra determiner, file Foo.LupineSwitches (for the action "Lupine TranslateInterface[Foo]"), to get additional Lupine arguments.
1.3 Bringing Things Up-To-Date
The basic operation of MakeDo is to simultaneously derive the dependency graph, and ensure that the objects and actions are up-to-date. There are two more concepts beyond those presented above which enter into this.
One of them is need. To bring things up-to-date, a set of goals is specified. An object is needed if a goal (transitively) depends on it.
The other concept is modifiability. MakeDo is willing to accept a set of objects which it may modify, with the assumption that it is not allowed to modify any others. MakeDo is also willing to operate without such guidance, and will modify any objects it detects a need to.
Here are the rules for bringing things up-to-date (where C is an action variable, and A and B are object variables):
IF A is needed & C makes A & A doesn't exist THEN C needs to be done
IF A is needed & C makes A & A is out-of-date THEN C needs to be done
C makes A from (non-optional) B & B doesn't exist IS NOT SUFFICIENT REASON TO CONCLUDE A is out-of-date
IF C needs to be done & (ForAll B mustHad by C: B exists) THEN C can be done
IF C needs to be done & C can't be done THEN C fails
IF C succeeded & C makes A THEN A may have changed
IF C failed & C makes A THEN A doesn't exist
IF A is needed & A is certainly modifiable & C makes A from B & B doesn't exist THEN C fails; IF B not certainly modifiable THEN Complain
Complications arise from the fact that MakeDo operates on the dependency graph incrementally, from multiple processes.
1.4 Incrementality
MakeDo keeps, on each object and action, bits saying whether they are suspected of being out-of-date. The exploration of the dependency graph is clipped where the bits say there is certainly no need to explore further. Careful examination of the above definitions and rules will reveal that whether there is a need to explore further at each vertex depends on the modifiability specification; in fact the suspicion bits are not updated when the modifiability specification changes --- it is hoped that this bug will not actually take any painful bites.
Each object belongs to an object class. An object class is responsible for being able to report the current create date of any of its members. MakeDo remembers such reports, and only asks the object class again if there is reason to suspect the create date may have changed. There is a procedure in the MakeDo interface that an object class may call to make MakeDo suspect that an object's create date may have changed. An object class could monitor all of its members, and poke MakeDo whenever any of them changes. The file object class does this. Alternatively, one could suspect create date changes in all the relevent objects (supposing one could enumerate this set) just before calling MakeDo.Ensure.
1.5 Parallelism
When bringing things up-to-date, MakeDo is willing to employ additional processes, up to some client-specified limit (which is initially 0). The reason for this is that while doing the executable part of an action, that process does nothing else. With multiple processes, you could be doing multiple actions at once (e.g., taking advantage of multiple compiler servers).
Supposing that it is allowed, MakeDo will only spawn a new process when there is work for it to do. This spawning is accomplished by issuing a command that forks the command tool it is issued in. You can thus tell how many additional processes MakeDo has by counting the number of additional command tools on your screen. Of course, you don't want to delete one of these (until after MakeDo is thoroughly done with it) because that would give rise to ERRORs about close streams, and ABORTing these ERRORs will abort your entire MakeDo job. You can tell when MakeDo is thoroughly done with an auxilliary command tool, because the last thing it prints in it is "done helping MakeDo". When MakeDo finishes bringing things up-to-date, it is not yet thoroughly done with its auxilliary command tools. If you set the limit for additional processes to be less than the number currently in use, the appropriate number will become thoroughly done.
MakeDo is not so parallel that it can work on more than one top-level thing at a time. Don't even try it.
1.6 Interrupting
To stop MakeDo, click the "STOP!" button on any of the auxilliary command tools, or on the command tool (if any) from which you are invoking MakeDo. This raises the ERROR ABORTED in all processes currently in MakeDo. Note that the compiler catches this ERROR and does its own interpretation.
It is OK to stop MakeDo while it is working on some operations, but not on others --- see the documentation on the specific operations for details. If you STOP! one of the auxilliary command tools while MakeDo is not doing anything, the next time you try to bring things up-to-date, you will get an ABORT.
2. Programmer's Interface
See the interface module MakeDo.
3. Command Tool Commands
name MakeDo:
syntax
MakeDo  list of arg 
(where arg is one of: -gr DF file name, -gm DF file name, -dr DF file name, -dm DF file name, -md DF file name, -mn file name, -assumeAllInconsistent, -dontAssumeAllInconsistent, -do, -dontDo, -record, -dontRecord, or -p number)
description
MakeDo executes whatever commands are necessary to produce up-to-date versions of given files. For instance, it will run the compiler and binder, on the right files, in the right order. You have the option of delimiting what MakeDo is allowed to cause to be changed. Excercizing this option gives you added safety and error reporting.
Each argument to MakeDo is a bare name, or something with a switch. Bare names are taken to be goals. Here is what the switches mean:
-gr DF file name: Take the files in the DF file marked as verify-roots (i.e., preceeded by a "+") to be goals.
-gm DF file name: Take all the modifiable files in it (i.e., ones that might be stored if you did an SModel) to be goals.
-dr DF file name: Take the files in it marked as verify-roots to be goals. Add to the delimited set of what MakeDo may change all of the modifiable files in the DF-file.
-dm DF file name: Take all the modifiable files in it to be goals.
-md DF file name: Add to the delimited set of what MakeDo may change all of the modifiable files in the DF-file.
-mn file name: Add it to the delimited set of what MakeDo may change.
-assumeAllInconsistent: Assume that every derived file is inconsistent with its sources.
-dontAssumeAllInconsistent: Don't make that assumption --- check it out.
-do: MakeDo is allowed to execute commands to achieve consistency.
-dontDo: MakeDo is not allowed to execute commands to achieve consistency.
-record: MakeDo is to report the commands it did (or would) execute.
-dontRecord: That report is not to be given.
-p number: Reset the limit of auxilliary processes MakeDo may use to the given value --- if you don't use this switch, the limit won't change.
If one of the switches dr, dm, md, or mn is used, the set of things MakeDo may cause to be changed is delimited to what was explicitly asked for, plus, of course, the goals. Otherwise, what MakeDo may change is undelimited --- it may change anything.
examples
Suppose you have a package. It has a public interface (Foo), a private interface (FooPrivate, which references Foo), two implementation modules (FooImplA and FooImplB, both of which reference FooPrivate), and a configuration (FooPackage, which references FooImplA and FooImplB). After any sequence of compiling, binding, and editing, the command

% MakeDo FooPackage.BCD (the ".BCD" is optional, so far)
will do whatever compiles and binds are necessary to produce an up-to-date version of FooPackage.BCD. For instance, if everything was up-to-date, then you edited FooImplA, then issued the MakeDo command, MakeDo would compile FooImplA and then (if the compile was successful) bind FooPackage. If you were working in subdirectory Foo, with a FooPackage.BCD.Switches that contained
/c~s
it might look like this:

% Compile []<>Foo>FooImplA.Mesa
Compiling: FooImplA/-g . . . . . . no errors.
End of compilation
% Bind /c~s FooPackage
Binding: FooPackage
. . . . 0 errors
End of binding
If you have a Foo.DF that follows all the usual conventions, a good way to invoke MakeDo is

% MakeDo -dr Foo.DF
warnings
Beware!
stop/undo
Click the STOP! button in a participating commander.
name MakeCommandList:
syntax
MakeCommandList  list of arg 
description
Lists the commands that MakeDo would execute, under some vanilla assumptions about the results of those executions (execution of any one command may affect later decisions).
stop/undo
Click the STOP! button in a participating commander.
name MakeExcuses:
syntax
MakeExcuses [-verbose]  list of file name 
description
Explains what MakeDo thinks about the named files.
examples
Suppose your package has a module named MakeDoPrivate; you might do something like this:

% MakeExcuses MakeDoPrivate.BCD
[]<>Users>Spreitzer.pa>MD>MakeDoPrivate.BCD
 needed by: {
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoUpCmds.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoUpNodes.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoDownCmds.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoDownNodes.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoProcesses.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoFinders.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoAuxImpl.Mesa
  RCompile []<>Users>Spreitzer.pa>MD>MakeDoSimpleImpl.Mesa}
 determines: {}
 Does not need investigation
RCompile []<>Users>Spreitzer.pa>MD>MakeDoPrivate.Mesa:
 According to:
  ?[]<>Users>Spreitzer.pa>MD>MakeDoPrivate.BCD.Switches
  []<>Users>Spreitzer.pa>MD>MakeDoPrivate.Mesa
 Makes:
  []<>Users>Spreitzer.pa>MD>MakeDoPrivate.BCD
 From:
  []<>Users>Spreitzer.pa>MD>BasicTime.BCD
  []<>Users>Spreitzer.pa>MD>CedarProcess.BCD
  []<>Users>Spreitzer.pa>MD>Commander.BCD
  []<>Users>Spreitzer.pa>MD>IO.BCD
  []<>Users>Spreitzer.pa>MD>List.BCD
  []<>Users>Spreitzer.pa>MD>MakeDo.BCD
  []<>Users>Spreitzer.pa>MD>RedBlackTree.BCD
  []<>Users>Spreitzer.pa>MD>Rope.BCD
  []<>Users>Spreitzer.pa>MD>TimeStamp.BCD
  []<>Users>Spreitzer.pa>MD>MakeDoPrivate.Mesa
 Does not need to be rederived
 Does not need to be reexecuted
 does not need to be executed, because:
 []<>Users>Spreitzer.pa>MD>MakeDoPrivate.BCD of August 30, 1985 3:41:23 pm PDT
 references: used version: current version
 []<>Users>Spreitzer.pa>MD>MakeDoPrivate.Mesa 00008c069f3f (August 30, 1985 3:32:38 pm PDT) 00008c069f3f (August 30, 1985 3:32:38 pm PDT)
 []<>Users>Spreitzer.pa>MD>TimeStamp.BCD 0c108bf3ad31 0c108bf3ad31
 []<>Users>Spreitzer.pa>MD>Rope.BCD 84aaa8987127 84aaa8987127
 []<>Users>Spreitzer.pa>MD>RedBlackTree.BCD 3c4e5fda65d9 3c4e5fda65d9
 []<>Users>Spreitzer.pa>MD>MakeDo.BCD a1b4b653b164 a1b4b653b164
 []<>Users>Spreitzer.pa>MD>List.BCD 8dfb4ad95316 8dfb4ad95316
 []<>Users>Spreitzer.pa>MD>IO.BCD 870776697211 870776697211
 []<>Users>Spreitzer.pa>MD>Commander.BCD 1d35546e4963 1d35546e4963
 []<>Users>Spreitzer.pa>MD>CedarProcess.BCD 0c10c6afafc1 0c10c6afafc1
 []<>Users>Spreitzer.pa>MD>BasicTime.BCD 2430539b0797 2430539b0797
warnings
Beware the Ides of March!
stop/undo
Click the STOP! button in the commander.
name MakeSuspicion:
syntax
MakeSuspicion arg*
arg: [-p] fileName | -all
description
Suspects the named files of change. If prefixed by a -p, this suspects the producer of that file of need of rederivation and reexecution. If instead -all is given, this suspects all nodes and actions of everything.
examples

% MakeSuspicion -all
stop/undo
Don't!
name MakeEmpty:
syntax
MakeEmpty
description
Deletes the entire dependency graph.
examples

% MakeEmpty
stop/undo
Don't!
name MakeProducer:
syntax
MakeProducer  list of fileName 
description
Retries figuring out how to make named leaves.
examples

% MakeProducer FooPackage.BCD
stop/undo
Don't!