Luke Hutchison

2018-06-15 03:37:48 UTC

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?

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?