Review requested: Fixing the ordering problem in Data-E

diff --git a/src/esrc/org/erights/e/elib/serial/deSubgraphKit.emaker b/src/esrc/org/erights/e/elib/serial/deSubgraphKit.emaker
index c45b040..1531804 100644
--- a/src/esrc/org/erights/e/elib/serial/deSubgraphKit.emaker
+++ b/src/esrc/org/erights/e/elib/serial/deSubgraphKit.emaker
@@ -12,6 +12,7 @@ def DEBuilderOf := <elib:serial.DEBuilderOf>
 def deSrcKit := <elib:serial.deSrcKit>
 def makeCycleBreaker := <elib:tables.makeCycleBreaker>
 def makeAnUncaller := <elib:serial.makeAnUncaller>
+def makeAssembler := <elib:serial.makeAssembler>
 
 def defaultUncallers := makeAnUncaller.getDefaultUncallers()
 
@@ -251,6 +252,10 @@ def deSubgraphKit {
      */
     to makeBuilder(scope, caller) :near {
 
+        # The assembler, which makes sure calls happen in a valid order
+        # XXX allow caller to provide the dependency hook.
+        def assembler := makeAssembler(fn _, _ {}, caller)
+
         # The index of the next temp variable
         var nextTemp := 0
 
@@ -264,13 +269,17 @@ def deSubgraphKit {
             to getNodeType() :near { Node }
             to getRootType() :near { Root }
 
-            to buildRoot(root :Node)        :Root { root }
             to buildLiteral(value)          :Node { value }
             to buildImport(varName :String) :Node { scope[varName] }
             to buildIbid(tempIndex :int)    :Node { temps[tempIndex] }
 
+            to buildRoot(root :Node) :Root { 
+                assembler.finish()
+                root
+            }
+
             to buildCall(rec :Node, verb :String, args :List[Node]) :Node {
-                caller.call(rec, verb, args)
+                assembler.call(rec, verb, args)
             }
 
             to buildDefine(rValue :Node) :Tuple[Node, int] {
diff --git a/src/esrc/org/erights/e/elib/serial/makeAssembler.emaker b/src/esrc/org/erights/e/elib/serial/makeAssembler.emaker
new file mode 100644
index 0000000..b59a3fa
--- /dev/null
+++ b/src/esrc/org/erights/e/elib/serial/makeAssembler.emaker
@@ -0,0 +1,141 @@
+# Copyright 2007 Kevin Reid, under the terms of the MIT X license
+# found at http://www.opensource.org/licenses/mit-license.html ................
+
+pragma.syntax("0.9")
+pragma.enable("accumulator")
+
+def ESet := <type:org.erights.e.elib.tables.ESet>
+def makeQueue := <elib:vat.makeQueue>
+def makeTraversalKey := <elib:tables.makeTraversalKey>
+def Really := <elib:slot.Really>
+
+def makeImplicitCreationFlexMap(makeValue) {
+    def storage := [].asMap().diverge()
+    return def icfm extends storage {
+        to get(key) { return storage.fetch(key,
+                               fn { storage[key] := makeValue() }) }
+    }
+}
+
+/** Generalization of a standard topological sort, in that edges may be added
+  * to any node not already output. 'initialEdger' is called first, with a
+  * function of two arguments which is used to add edges at that time or later;
+  * 'output' is then called once with each node in the computed order.
+  *
+  * Throws if no progress can be made and there are nodes remaining; i.e. when
+  * there is a cycle in the graph.
+  *
+  * Implementation limitation: null may not be a node. */
+def topologicalSort(nodes :ESet, initialEdger, output) {
+    
+    # Tables of edges
+    def forwardEdges := makeImplicitCreationFlexMap(
+                          fn { [].asSet().diverge() })
+    def reverseCount := makeImplicitCreationFlexMap(fn { 0 })
+    
+    # Queue containing all elements that might have no remaining predecessors
+    def ready := makeQueue()
+    for node in nodes { ready.enqueue(node) }
+
+    def undoneNodes := nodes.diverge()
+    
+    def addEdge(from, ::"to") {
+        require(undoneNodes.contains(from))
+        require(undoneNodes.contains(::"to"))
+        forwardEdges[from].addElement(::"to")
+        reverseCount[::"to"] += 1
+    }
+    initialEdger(addEdge)
+    
+    while (ready.optDequeue() =~ node :notNull) {
+        # Output if the node is actually ready and not already done
+        if (reverseCount[node].isZero() && undoneNodes.contains(node)) {
+            output(node)
+            undoneNodes.remove(node)
+
+            for next in forwardEdges[node] {
+                # Enqueue if there now remain no predecessors
+                def remaining := reverseCount[next] -= 1
+                if (remaining.isZero()) {
+                    ready.enqueue(next)
+                }
+            }
+            forwardEdges.removeKey(node)
+        }
+    }
+    
+    if (forwardEdges.size().aboveZero()) {
+        throw(`Topological sort failed: $forwardEdges remains`)
+    }
+    require(undoneNodes.size().isZero(), 
+      "Shouldn't happen: undoneNodes has things left")
+}
+
+def check {}
+def call {}
+
+def makeAssembler(extraDependencyBuilder, subcaller) {
+    def calls := [].asMap().diverge()
+
+    def assembler {
+        to call(recipient, verb, args) {
+            def record := [def resolution, recipient, verb, args]
+            calls[makeTraversalKey(resolution)] := record
+            return resolution
+        }
+        to run(recipient) {
+            return def callBuilder match [verb, args] {
+                assembler.call(recipient, verb, args)
+            }
+        }
+        to finish() {
+            def addEdge
+            
+            def addDependency(earlier, laterKey, kind) {
+                def earlierKey := makeTraversalKey(earlier)
+                if (calls.maps(earlierKey)) {
+                    addEdge([earlierKey, call], [laterKey, kind])
+                }
+            }
+            
+            #traceln(`${calls.domain()}`)
+            topologicalSort(
+                { # set of node names used in the topo sort
+                    def nodesFlex := [].asSet().diverge()
+                    for key in calls.getKeys() {
+                         nodesFlex.addElement([key, check])
+                         nodesFlex.addElement([key, call])
+                    }
+                  nodesFlex.snapshot()
+                },
+                fn bind addEdge {
+                    # add initial edges
+                    for key => [_, recipient, _, _] in calls {
+                        addEdge([key, check], [key, call])
+                        addDependency(recipient, key, check)
+                    }
+                },
+                fn node {
+                    # process a given node
+                    switch (node) {
+                        match [key, ==check] {
+                            #traceln(`checking ${calls[key]}`)
+                            def [_, recipient, verb, args] := calls[key]
+                            
+                            extraDependencyBuilder(
+                                [recipient, verb, args],
+                                fn what { addDependency(what, key, call) })
+                        }
+                        match [key, ==call] {
+                            #traceln(`doing ${calls[key]}`)
+                            def [resolver, recipient, verb, args] := calls[key]
+                            resolver.resolve(
+                                subcaller.call(recipient, verb, args))
+                            calls.removeKey(key)
+                        }
+                    }
+                })
+        }
+    }
+    return assembler
+}
\ No newline at end of file
diff --git a/src/esrc/org/erights/e/elib/slot/Really.emaker b/src/esrc/org/erights/e/elib/slot/Really.emaker
new file mode 100644
index 0000000..4b046fa
--- /dev/null
+++ b/src/esrc/org/erights/e/elib/slot/Really.emaker
@@ -0,0 +1,22 @@
+/** Given a guard, produces a guard which accepts only those values which the
+  * wrapped guard passes through without coercing.
+  *
+  * Note that for an arbitrary guard, this cannot be done other than by
+  * invoking the wrapped guard and checking sameness of the result. */
+def Really {
+    # XXX add optimization for known cases, e.g. any Java class.
+    to get(coercingGuard) {
+        return def reallyGuard {
+            to coerce(specimen, optEjector) {
+                def coerced := coercingGuard.coerce(specimen, optEjector)
+                if (coerced != specimen) {
+                    # XXX unnecessary-printing efficiency problem
+                    throw.eject(optEjector, E.toQuote(coerced) +
+                      " must be same as original specimen " +
+                      E.toQuote(specimen))
+                }
+                return coerced
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/esrc/scripts/test/updoc/datae-ordering.updoc b/src/esrc/scripts/test/updoc/datae-ordering.updoc
new file mode 100644
index 0000000..a0e82da
--- /dev/null
+++ b/src/esrc/scripts/test/updoc/datae-ordering.updoc
@@ -0,0 +1,103 @@
+# Copyright 2010 Kevin Reid, under the terms of the MIT X license
+# found at http://www.opensource.org/licenses/mit-license.html ................
+
+XXX TODO: Dig up the mailing list discussion for this topic.
+
+XXX linewraps
+The problem is that, depending on the order of serialization, Data-E unserialization may proceed in an order which fails to unserialize, because some reference must be near; in particular, when the recipient of a given call is an object whose creation was deferred.
+
+For example, suppose A and B refer to each other, and A is encountered first:
+
+     /-------\
+     V       |
+   +---+   +---+ 
+-->| A |-->| B |
+   +---+   +---+   
+
+Furthermore, object C is a facet of A, and B refers to A:
+
+     /-------\
+     V       |
+   +---+   +---+ 
+-->| A |-->| B |
+   +---+   +---+   
+    *^*      |
+   +---+     |
+   | C |<----/
+   +---/
+
+Then the deSubgraphKit algorithm:
+  * meets A, descends into its components
+    * meets B, descends into its components
+      * meets A again, produces a promise for A
+      * meets C, descends into its components
+        * meets A again as the receiver for C's uncall
+
+This last step is the problem. We find we have the Data-E code:
+  def t_A := makeA(makeB(t_A, t_A.makeC()))
+which will fail with not-synchronously-callable at makeC. (Note that this problem can only occur if the *recipient* of an object's uncall is another object in the subgraph, which participates in cycles, rather than being an exit or non-cyclic subgraph.)
+
+Another case is when C is not a facet of A, but is the product of makeC(_ :near); this will also fail since t_A is not near when makeC(t_A) is done. Note that unlike the previous case, this cannot be fixed 'statically' (based only on the Data-E graph structure) since it depends on the requirements for makeC's parameters.
+
+The general solution to both of these problems is to recognize that the 'order of execution' in unserialization is not part of the meaningful content of a Data-E graph; therefore, we use the *caller* hook of deSubgraphKit.makeBuilder to include a module which defers calls until they may succeed.
+
+The algorithm used is an incremental topological sort. Before each call is performed, it is examined for dependencies (such as the recipient being near). If it has any, it is deferred until those dependencies have also executed.
+
+The component which replaces E.call in unserialization is called an 'assembler', because its job is to perform the steps of assembling the subgraph from the disorganized parts (calls) in the proper order until it is complete.
+
+Testing the assembler by itself
+-------------------------------
+
+XXX review: The assembler has more general use, as speculated in the April 18 2007 mail; what should the FQN really be?
+  
+  ? def Really := <elib:slot.Really>
+  
+  ? def makeAssembler := <import:org.erights.e.elib.serial.makeAssembler>
+  # value: <makeAssembler>
+  
+  ? def setDependencyBuilder(portrayal, addDependency) {
+  >     if (portrayal =~ [list :Really[List], =="asSet", []]) {
+  >         for x in list { addDependency(x) }
+  >     }
+  > }
+
+The parameters to makeAssembler are a callback which may inspect calls and add additional dependencies on specific references (which is not invoked until the call constructing the recipient has been performed), and the caller which should be used for the underlying real calls (that this is wrapping).
+  
+  ? def a := makeAssembler(setDependencyBuilder, E)
+  # value: <assembler>
+  
+  ? def [y, s, l, x] := [a(1).next(),
+  >                      a(l).asSet(),
+  >                      a(__makeList).run(x, y),
+  >                      a(0).next()]
+  > a.finish()
+  > [y,s,l,x]
+  # value: [2, [1, 2].asSet(), [1, 2], 1]
+
+XXX test the call() based interface.
+
+  ? def l := a(["hello world", a(l).readOnly()]).diverge()
+  > a.finish()
+  > l
+  # value: ["hello world", <***CYCLE***>.readOnly()].diverge()
+
+Data-E ordering
+---------------
+
+To test Data-E, we use the problem case described at the beginning of this document.
+
+  ? def b
+  > def a := ["this is A", b]
+  > bind b := ["this is B", a, a.diverge()]
+  > a
+  # value: ["this is A", ["this is B", <***CYCLE***>, ["this is A", <***CYCLE***>].diverge()]]
+
+  ? def surgeon := <elib:serial.makeSurgeon>.withSrcKit(""); null
+  ? print(def ser := surgeon.serialize(a))
+  # stdout: def t__0 := ["this is A", ["this is B", t__0, t__0.diverge()]]
+
+  ? surgeon.unserialize(ser)
+  # value: ["this is A", ["this is B", <***CYCLE***>, ["this is A", <***CYCLE***>].diverge()]]
+
+
+XXX possibly add the default feature of using rangeSubsetOf to check if the guards of the parameters in the the recipient's alleged type are known to reject promises.