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. These are objects, the contents of which are used in determining some variable aspects of the action. The variable aspects of an action are 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 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. Thus, each object is either certainly modifiable, certainly not modifiable, or unspecifiedly modifiable.
An object is a leaf (of the dependency DAG) if there is no way to derive it from other objects, or if it is certainly not modifiable.
There are two intertwined concepts of current and broken. An object is current if it's in as good shape as possible. A current object is broken if there's still something definitely wrong with it (determining this is somewhat problematical, because MakeDo is sometimes asked to operate without much guidance about what's to be expected).
Loosely speaking, an object is current if either it's A-OK, or there's nothing MakeDo can do about it. Here is a precise formulation:
A leaf is current;
a non-leaf N, with producing action A, is current iff
all of A's determiners are current and
either
some of A's determiners are broken,
or
A's variable parts are derived from the current contents of its determiners, and
all inputs to A are current, and
either
some of A's inputs are broken, or
some of A's mandatory inputs don't exist, or
A fails when executed on the current contents of its inputs, or
A claims N is consistent with the current contents of its inputs.
From the above, you can deduce that MakeDo will attempt to execute an action A iff:
all of A's determiners are current, and
none of A's determiners are broken, and
A's variable parts are derived from the current contents of its determiners, and
all of A's inputs are current, and
none of A's inputs are broken, and
all of A's mandatory inputs exist, and
A is not known to fail when executed on the current contents of its inputs, and
A claims some output N is inconsistent with the current contents of its inputs.
Loosely speaking, a current object is broken if it doesn't exist but is expected to, or if the action that derives it fails, or if it depends on broken objects. Precisely, a current object N is broken iff:
N is certainly modifiable and doesn't exist, or
N is produced by A and is not certainly not modifable and either:
some of A's inputs or determiners are broken, or
N is certainly modifiable and some of A's mandatory inputs don't exist, or
all of A's mandatory inputs exist and A fails when executed on the current contents of its inputs.
I am not confident that this definition of broken accurately captures what's desired. Comments and suggestions are welcome.
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 consistent with with the inputs, 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 consistent with inputs. 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 consistent with inputs. It also uses an optional extra determiner, file Foo.LupineSwitches (for the action "Lupine TranslateInterface[Foo]"), to get additional Lupine arguments.
1.4 Incrementality
Although conceptually at all times an object has well-defined currentness, brokenness, and producer, MakeDo does not try to know these things at all times. However, once it computes these things, it does not forget them. When computing new information, or determining what to do, MakeDo stops exploring the dependency graph where all the relevent values are known and nothing needs to be done.
1.4.1 The Modifiability Bug
One of the contributors to the currency computation is the modifiability. The modifiability is unique in having the unfortunate property of coming from the user who is asking for something to be done, instead of from the dependency graph itself. It is expected that, for any given object, the user is not really interested in changing its modifiability (very often), although the user may direct MakeDo at alternating tasks, with a different modifiability for each, but (probably, mostly) non-conflicting modifiability for the intersecting objects, if any. Comforted by this assumption, MakeDo stores modifiability on the objects. Now, strictly speaking, this means that every time modifiability is specified, MakeDo should explore the entire dependency graph and update the modifiability stored there --- and you've probably already guessed that it doesn't. What it does do is update the modifiability of any objects it happens to touch for other reasons. It is hoped that this comes close enough for most purposes --- please complain if it's not.
1.6 Parallelism
When bringing things up-to-date, MakeDo is willing to employ additional processes, up to some client-specified limit. 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 executing multiple actions at once (e.g., taking advantage of multiple compiler servers).
When MakeDo forks an auxilliary process, it is for the purpose of executing one action --- when that finishes, the process is de-allocated. Before forking, MakeDo prints a message in the command tool indicating that it is about to fork a process, and what action it will execute. Then, in a container viewer maintained for just this purpose, named "MakeDoAuxBox", a typescript viewer is created, and the action is executed in that typescript. When it is done, the typescript is deleted. The output from the auxilliary process is also gathered in a buffer, and printed all at once in the original command tool when the process finishes.