Hi, I noticed that the method ModuleLayer#layers() uses the following code
to get the module layers in resolution order:
/**
* Returns an ordered stream of layers. The first element is this layer,
* the remaining elements are the parent layers in DFS order.
*
* @implNote For now, the assumption is that the number of elements will
* be very low and so this method does not use a specialized
spliterator.
*/
Stream<ModuleLayer> layers() {
List<ModuleLayer> allLayers = this.allLayers;
if (allLayers != null)
return allLayers.stream();
allLayers = new ArrayList<>();
Set<ModuleLayer> visited = new HashSet<>();
Deque<ModuleLayer> stack = new ArrayDeque<>();
visited.add(this);
stack.push(this);
while (!stack.isEmpty()) {
ModuleLayer layer = stack.pop();
allLayers.add(layer);
// push in reverse order
for (int i = layer.parents.size() - 1; i >= 0; i--) {
ModuleLayer parent = layer.parents.get(i);
if (!visited.contains(parent)) {
visited.add(parent);
stack.push(parent);
}
}
}
this.allLayers = allLayers =
Collections.unmodifiableList(allLayers);
return allLayers.stream();
}
This code represents a preorder DFS. The resulting order is *not* a
topological sort ordering. This can lead to an ancestral layer being listed
in the final ordering before a descendant layer. For example, consider
these four layer -> parent relationships:
A -> [ B, C ]
B -> [ D ]
C -> [ D ]
D -> [ ]
The ordering code as given in ModuleLayer will produce the order [ A, B, D,
C ], causing the layers D and C to be out of order. The order is not a
toplological sort ordering, which guarantees that all descendants of a node
are listed before the node, and all parents of the node are listed after it.
To fix this, the search order should be changed to a *reversed postorder
DFS*. The current code uses a stack to implement iterative DFS. However,
the recursive postorder DFS algorithm needs to do some work after the
recursive call returns (specifically adding the current node to the
beginning of the output ordering), so in effect, the current iterative code
cannot be directly modified to yield a postorder traversal, without having
two different types of nodes pushed onto the stack ("recurse to parent"
nodes and "return from child" nodes), effectively mimicking Continuation
Passing Style. It is simpler therefore to change the code to make it
recursive.
The list allLayers should be changed to a LinkedList, allowing nodes to be
pushed onto the beginning of the list, so that the ordering doesn't have to
be reversed at the end (as required by topological sorting). The
allLayers.add(layer) line should be moved after the iteration returns (to
give postorder traversal), and should be changed to allLayers.push(layer) (to
reverse the output ordering). Also, the loop through parent nodes should no
longer be inverted, since we're not using a FIFO stack to process parents
anymore.
The fixed algorithm is as follows:
/** Recursively find the topological sort order of ancestral layers. */
private void findLayerOrder(Set<ModuleLayer> visited,
LinkedList<ModuleLayer> allLayersOut) {
if (visited.add(this)) {
for (int i = 0; i < parents.size(); i++) {
ModuleLayer parent = parents.get(i);
parent.findLayerOrder(visited, allLayersOut);
}
allLayersOut.push(this);
}
}
/**
* Returns an ordered stream of layers. The first element is this layer,
* the remaining elements are the parent layers in topological sort
order.
*
* @implNote For now, the assumption is that the number of elements will
* be very low and so this method does not use a specialized
spliterator.
*/
Stream<ModuleLayer> layers() {
if (this.allLayers == null) {
LinkedList<ModuleLayer> allLayers = new LinkedList<>();
findLayerOrder(new HashSet<ModuleLayer>(), allLayers);
this.allLayers = Collections.unmodifiableList(allLayers);
}
return this.allLayers.stream();
}
The same changes should also be made to Configuration#configurations() ,
since it uses the same broken DFS algorithm.
Is there anywhere else in the java.lang.module code that needs to be fixed
to properly perform topological sort?
