This page is very preliminary.

The idea is that there are four operation that occur to a node when a DAG is being run. The operations are Setup(), Visit(), Build(), and Scan(). The first three happen exactly once; the last one occurs once for each distinct scan context applied to the node.

Unlike the typical DAG bush, this tree grows downward, so the children must be evaluated before the parents.

For the purposes of this discussion, these are the contents of the node; items marked with a "*" are not manipulated (but are used) by this algorithm: (TODO: correct the names to the ones actually used)

• status. A flag indicating whether the node has been visited or worked already. It's given as a string, but in an actual implementation, the value would be an integer so that inequalities would work as expected.
• ref_count. The number of dependencies on which this node is waiting. Initialized to one, when it counts down to zero, the node's prerequisits are completed and the node can be evaluated.
• pending. A list of parents waiting for this node to complete.
• names*. Identifier(s) of the object(s) generated by this node.
• children*. A list of nodes that this node explicitly depends on. Created by the Depends() function.
• sources*. A list of nodes that are used in the production of this node. A subset of children.
• parents*. A list of nodes that explicitly depend on this node. The other end of the Depends() function.
• targets*. A list of nodes that consume this node. A subset of parents.
• scan context. A set of values (including the scanner) to use for scanning a node.
• implicit_sources. A list of nodes that are implicitly used in the production of this node.
• implicit_targets. A list of nodes that implicitly consume this node.
• cache of scan results. Each result of a scan, indexed by the context.

There are four stages in a node's evaluation (along with the essential steps in each stage):

1. Initialize(). The node is initialized for use by the DAG runner. This is done when the node is instantiated.
   1. status = 'unvisited'
   2. pending is set to empty list
   3. implicits set to empty list
   4. implicit_sources is set to empty list
   5. implicit_targets is set to empty list
2. Visit(). The first time a node is visited, it performs a series of actions. This includes attaching parent dependencies (which visits the parent nodes). Note that a hook in this stage is effectively done when going "up" the DAG, the reverse direction of the usual dependency direction. If we have no parents (or if all parents are already resolved), this node is placed on the work queue.
   1. if status != 'unvisited': return
   2. set ref count to one
   3. run any pre-visit hooks
   4. for parent in parents: self.Pending(parent)
   5. run any post-visit hooks
   6. set status to 'visited'
   7. try to add ourself to the work queue
3. Build(). All ancestors have been evaluated; evaluate this node, running the action if there is one and running the scanner if there is one. This includes attaching implicit dependencies on children.
   1. if node is up-to-date: return
   2. run any pre-action hooks
   3. execute action, if any
   4. run any post-action hooks
   5. calculate signature
   6. set status to 'built'
   7. for child in targets+implicit_targets: child.Implicit(self)
   8. for child in pending: try to add child to the work queue
4. Scan(context). The node has been built; run a scanner (which is part of the context) to get any implicit dependencies.
   1. if there is a scan result for this context, return it
   2. run any pre-scanner hooks
   3. run scanner, producing a scan result
   4. run any post-scanner hooks
   5. return the new scan result There are two functions that provide glue so that nodes are evaluated correctly.

• One is node.Pending(dep) which delays the evaluation of the current node until the dependency has been worked. If the dependency has already been worked, it has nothing to do; otherwise, it sets up the delay as a topological sort. It has these steps:

  1. if dep.status == 'worked': return
  2. increment node.ref_count
  3. add node to dep.pending
  4. dep.Visit()

• The other is node.Implicit(src)which attaches implicit dependencies. The source is the node that is to be scanned for dependencies. For unworked dependencies, it adds the topological sort information; for worked dependencies, it recursively picks up the dependencies. It has these steps:

  1. if the node has no scan context, just return
  2. for dep in src.Scan(node.context)
     1. add node to dep.implicit_targets
     2. add dep to node.implicit_sources
     3. if dep.status != 'worked': node.Pending(dep)
     4. else: node.Implicit(dep)
  3. return The DAG runner needs these functions to run the DAG:

• Run

  1. item

• TryQueue

  1. decrement ref count; if ref count > zero: return

• XXX

  1. item Then a (single-threaded) implementation of the DAG runner has these steps:

1. for node in targets: node.Visit()
2. while work_queue: remove first node in work_queue; node.Work() (The multi-threaded implementation is more complex, but every time a node is added to the work queue or when a worker thread reports back the results of an action, an attempt is made to run the head of the queue.)

Each node executes the Visit() logic exactly once, is moved into the work queue exactly once, and executes the Work() logic exactly once. (Well, modulo loops in the DAG, in which case the nodes never get into the work queue.)