ModuleLayer#layers() and Configuration#configurations() produces non-topological ordering

[Luke Hutchison]

(Sorry Alan for the dup -- I forgot to Reply-All to the list)

On Fri, Jun 15, 2018 at 8:50 AM Alan Bateman <Alan.Bateman at oracle.com>
wrote:

> > 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.
> Multi parent configurations is a somewhat niche area but it is specified
> to be DFS. If there someone in spec that has lead to you to assume the
> above is incorrect? I'm just wondering if there is wording that need to
> be improved or fixed somewhere.
>

The alternative algorithm I suggested is still DFS -- it is just
postorder+reversed in its output, rather than pretorder.

It is not in reference to the spec that I make this suggestion, it is due
to the logical argument that the existing code is written not just to
handle tree-structured multi-parenting, but fully DAG-structured ancestral
graphs -- and because the existing code appears to attempt to ensure that
(1) a node is listed before its parent in the output, and (2) if there are
multiple parents, those parents are listed in the same relative order in
the output. These two criteria together would turn the partial ordering of
the DAG into a total ordering without any ambiguity. However, criterion (1)
is violated by the current code in DAG-structured ancestral graphs, in all
but the first directed path to the most distant common ancestor node.

I'm assuming that since more than one module may define classes in the same
package, it is possible to have the same class defined multiple times in
different layers. Therefore, if the intent of specifying that DFS should be
used for module resolution is that class definitions in shallower layers
should mask definitions of the same class in deeper layers, then
topological ordering does in fact matter -- because otherwise, as shown in
the example I gave, it is possible for deeper layers to be reached before
shallower layers.

On Fri, Jun 15, 2018 at 8:26 AM David Lloyd <david.lloyd at redhat.com> wrote:

> > 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
>
> A small quibble: LinkedList should normally never be used.  You can
> push things on to the beginning of an ArrayDeque (it is a double-ended
> queue after all).
>

Thank you, I always assumed that ArrayDeque had O(size()) time for
insertion at the head -- but I just looked at the implementation and it's
O(1) -- very clever :-)


On Fri, Jun 15, 2018 at 8:50 AM Alan Bateman <Alan.Bateman at oracle.com>
wrote:

> On 15/06/2018 04:37, Luke Hutchison wrote:
> > :
> >
> > 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.
> Multi parent configurations is a somewhat niche area but it is specified
> to be DFS. If there someone in spec that has lead to you to assume the
> above is incorrect? I'm just wondering if there is wording that need to
> be improved or fixed somewhere.
>
> -Alan
>