| /******************************************************************************* |
| * Copyright (c) 2004, 2016 IBM Corporation and others. |
| * |
| * This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License 2.0 |
| * which accompanies this distribution, and is available at |
| * https://www.eclipse.org/legal/epl-2.0/ |
| * |
| * SPDX-License-Identifier: EPL-2.0 |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| |
| package org.eclipse.osgi.internal.container; |
| |
| import java.util.*; |
| |
| /** |
| * Borrowed from org.eclipse.core.internal.resources.ComputeProjectOrder |
| * to be used when computing the stop order. |
| * Implementation of a sort algorithm for computing the node order. This |
| * algorithm handles cycles in the node reference graph in a reasonable way. |
| * |
| * @since 3.0 |
| */ |
| public class ComputeNodeOrder { |
| |
| /* |
| * Prevent class from being instantiated. |
| */ |
| private ComputeNodeOrder() { |
| // not allowed |
| } |
| |
| /** |
| * A directed graph. Once the vertexes and edges of the graph have been |
| * defined, the graph can be queried for the depth-first finish time of each |
| * vertex. |
| * <p> |
| * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>, |
| * McGraw-Hill, 1990. The depth-first search algorithm is in section 23.3. |
| * </p> |
| */ |
| private static class Digraph { |
| /** |
| * struct-like object for representing a vertex along with various |
| * values computed during depth-first search (DFS). |
| */ |
| public static class Vertex { |
| /** |
| * White is for marking vertexes as unvisited. |
| */ |
| public static final String WHITE = "white"; //$NON-NLS-1$ |
| |
| /** |
| * Grey is for marking vertexes as discovered but visit not yet |
| * finished. |
| */ |
| public static final String GREY = "grey"; //$NON-NLS-1$ |
| |
| /** |
| * Black is for marking vertexes as visited. |
| */ |
| public static final String BLACK = "black"; //$NON-NLS-1$ |
| |
| /** |
| * Color of the vertex. One of <code>WHITE</code> (unvisited), |
| * <code>GREY</code> (visit in progress), or <code>BLACK</code> |
| * (visit finished). <code>WHITE</code> initially. |
| */ |
| public String color = WHITE; |
| |
| /** |
| * The DFS predecessor vertex, or <code>null</code> if there is no |
| * predecessor. <code>null</code> initially. |
| */ |
| public Vertex predecessor = null; |
| |
| /** |
| * Timestamp indicating when the vertex was finished (became BLACK) |
| * in the DFS. Finish times are between 1 and the number of |
| * vertexes. |
| */ |
| public int finishTime; |
| |
| /** |
| * The id of this vertex. |
| */ |
| public Object id; |
| |
| /** |
| * Ordered list of adjacent vertexes. In other words, "this" is the |
| * "from" vertex and the elements of this list are all "to" |
| * vertexes. |
| * |
| * Element type: <code>Vertex</code> |
| */ |
| public List<Vertex> adjacent = new ArrayList<>(3); |
| |
| /** |
| * Creates a new vertex with the given id. |
| * |
| * @param id the vertex id |
| */ |
| public Vertex(Object id) { |
| this.id = id; |
| } |
| } |
| |
| /** |
| * Ordered list of all vertexes in this graph. |
| * |
| * Element type: <code>Vertex</code> |
| */ |
| private List<Vertex> vertexList = new ArrayList<>(100); |
| |
| /** |
| * Map from id to vertex. |
| * |
| * Key type: <code>Object</code>; value type: <code>Vertex</code> |
| */ |
| private Map<Object, Vertex> vertexMap = new HashMap<>(100); |
| |
| /** |
| * DFS visit time. Non-negative. |
| */ |
| private int time; |
| |
| /** |
| * Indicates whether the graph has been initialized. Initially |
| * <code>false</code>. |
| */ |
| private boolean initialized = false; |
| |
| /** |
| * Indicates whether the graph contains cycles. Initially |
| * <code>false</code>. |
| */ |
| private boolean cycles = false; |
| |
| /** |
| * Creates a new empty directed graph object. |
| * <p> |
| * After this graph's vertexes and edges are defined with |
| * <code>addVertex</code> and <code>addEdge</code>, call |
| * <code>freeze</code> to indicate that the graph is all there, and then |
| * call <code>idsByDFSFinishTime</code> to read off the vertexes ordered |
| * by DFS finish time. |
| * </p> |
| */ |
| public Digraph() { |
| super(); |
| } |
| |
| /** |
| * Freezes this graph. No more vertexes or edges can be added to this |
| * graph after this method is called. Has no effect if the graph is |
| * already frozen. |
| */ |
| public void freeze() { |
| if (!initialized) { |
| initialized = true; |
| // only perform depth-first-search once |
| DFS(); |
| } |
| } |
| |
| /** |
| * Defines a new vertex with the given id. The depth-first search is |
| * performed in the relative order in which vertexes were added to the |
| * graph. |
| * |
| * @param id the id of the vertex |
| * @exception IllegalArgumentException if the vertex id is |
| * already defined or if the graph is frozen |
| */ |
| public void addVertex(Object id) throws IllegalArgumentException { |
| if (initialized) { |
| throw new IllegalArgumentException(); |
| } |
| Vertex vertex = new Vertex(id); |
| Object existing = vertexMap.put(id, vertex); |
| // nip problems with duplicate vertexes in the bud |
| if (existing != null) { |
| throw new IllegalArgumentException(); |
| } |
| vertexList.add(vertex); |
| } |
| |
| /** |
| * Adds a new directed edge between the vertexes with the given ids. |
| * Vertexes for the given ids must be defined beforehand with |
| * <code>addVertex</code>. The depth-first search is performed in the |
| * relative order in which adjacent "to" vertexes were added to a given |
| * "from" index. |
| * |
| * @param fromId the id of the "from" vertex |
| * @param toId the id of the "to" vertex |
| * @exception IllegalArgumentException if either vertex is undefined or |
| * if the graph is frozen |
| */ |
| public void addEdge(Object fromId, Object toId) throws IllegalArgumentException { |
| if (initialized) { |
| throw new IllegalArgumentException(); |
| } |
| Vertex fromVertex = vertexMap.get(fromId); |
| Vertex toVertex = vertexMap.get(toId); |
| // ignore edges when one of the vertices is unknown |
| if (fromVertex == null || toVertex == null) |
| return; |
| fromVertex.adjacent.add(toVertex); |
| } |
| |
| /** |
| * Returns the ids of the vertexes in this graph ordered by depth-first |
| * search finish time. The graph must be frozen. |
| * |
| * @param increasing <code>true</code> if objects are to be arranged |
| * into increasing order of depth-first search finish time, and |
| * <code>false</code> if objects are to be arranged into decreasing |
| * order of depth-first search finish time |
| * @return the list of ids ordered by depth-first search finish time |
| * (element type: <code>Object</code>) |
| * @exception IllegalArgumentException if the graph is not frozen |
| */ |
| public List<Object> idsByDFSFinishTime(boolean increasing) { |
| if (!initialized) { |
| throw new IllegalArgumentException(); |
| } |
| int len = vertexList.size(); |
| Object[] r = new Object[len]; |
| for (Vertex vertex : vertexList) { |
| int f = vertex.finishTime; |
| // note that finish times start at 1, not 0 |
| if (increasing) { |
| r[f - 1] = vertex.id; |
| } else { |
| r[len - f] = vertex.id; |
| } |
| } |
| return Arrays.asList(r); |
| } |
| |
| /** |
| * Returns whether the graph contains cycles. The graph must be frozen. |
| * |
| * @return <code>true</code> if this graph contains at least one cycle, |
| * and <code>false</code> if this graph is cycle free |
| * @exception IllegalArgumentException if the graph is not frozen |
| */ |
| public boolean containsCycles() { |
| if (!initialized) { |
| throw new IllegalArgumentException(); |
| } |
| return cycles; |
| } |
| |
| /** |
| * Returns the non-trivial components of this graph. A non-trivial |
| * component is a set of 2 or more vertexes that were traversed |
| * together. The graph must be frozen. |
| * |
| * @return the possibly empty list of non-trivial components, where |
| * each component is an array of ids (element type: |
| * <code>Object[]</code>) |
| * @exception IllegalArgumentException if the graph is not frozen |
| */ |
| public List<Object[]> nonTrivialComponents() { |
| if (!initialized) { |
| throw new IllegalArgumentException(); |
| } |
| // find the roots of each component |
| // Map<Vertex,List<Object>> components |
| Map<Vertex, List<Object>> components = new HashMap<>(); |
| for (Vertex vertex : vertexList) { |
| if (vertex.predecessor == null) { |
| // this vertex is the root of a component |
| // if component is non-trivial we will hit a child |
| } else { |
| // find the root ancestor of this vertex |
| Vertex root = vertex; |
| while (root.predecessor != null) { |
| root = root.predecessor; |
| } |
| List<Object> component = components.get(root); |
| if (component == null) { |
| component = new ArrayList<>(2); |
| component.add(root.id); |
| components.put(root, component); |
| } |
| component.add(vertex.id); |
| } |
| } |
| List<Object[]> result = new ArrayList<>(components.size()); |
| for (List<Object> component : components.values()) { |
| if (component.size() > 1) { |
| result.add(component.toArray()); |
| } |
| } |
| return result; |
| } |
| |
| // /** |
| // * Performs a depth-first search of this graph and records interesting |
| // * info with each vertex, including DFS finish time. Employs a recursive |
| // * helper method <code>DFSVisit</code>. |
| // * <p> |
| // * Although this method is not used, it is the basis of the |
| // * non-recursive <code>DFS</code> method. |
| // * </p> |
| // */ |
| // private void recursiveDFS() { |
| // // initialize |
| // // all vertex.color initially Vertex.WHITE; |
| // // all vertex.predecessor initially null; |
| // time = 0; |
| // for (Iterator allV = vertexList.iterator(); allV.hasNext();) { |
| // Vertex nextVertex = (Vertex) allV.next(); |
| // if (nextVertex.color == Vertex.WHITE) { |
| // DFSVisit(nextVertex); |
| // } |
| // } |
| // } |
| // |
| // /** |
| // * Helper method. Performs a depth first search of this graph. |
| // * |
| // * @param vertex the vertex to visit |
| // */ |
| // private void DFSVisit(Vertex vertex) { |
| // // mark vertex as discovered |
| // vertex.color = Vertex.GREY; |
| // List adj = vertex.adjacent; |
| // for (Iterator allAdjacent=adj.iterator(); allAdjacent.hasNext();) { |
| // Vertex adjVertex = (Vertex) allAdjacent.next(); |
| // if (adjVertex.color == Vertex.WHITE) { |
| // // explore edge from vertex to adjVertex |
| // adjVertex.predecessor = vertex; |
| // DFSVisit(adjVertex); |
| // } else if (adjVertex.color == Vertex.GREY) { |
| // // back edge (grey vertex means visit in progress) |
| // cycles = true; |
| // } |
| // } |
| // // done exploring vertex |
| // vertex.color = Vertex.BLACK; |
| // time++; |
| // vertex.finishTime = time; |
| // } |
| |
| /** |
| * Performs a depth-first search of this graph and records interesting |
| * info with each vertex, including DFS finish time. Does not employ |
| * recursion. |
| */ |
| private void DFS() { |
| // state machine rendition of the standard recursive DFS algorithm |
| int state; |
| final int NEXT_VERTEX = 1; |
| final int START_DFS_VISIT = 2; |
| final int NEXT_ADJACENT = 3; |
| final int AFTER_NEXTED_DFS_VISIT = 4; |
| // use precomputed objects to avoid garbage |
| final Integer NEXT_VERTEX_OBJECT = Integer.valueOf(NEXT_VERTEX); |
| final Integer AFTER_NEXTED_DFS_VISIT_OBJECT = Integer.valueOf(AFTER_NEXTED_DFS_VISIT); |
| // initialize |
| // all vertex.color initially Vertex.WHITE; |
| // all vertex.predecessor initially null; |
| time = 0; |
| // for a stack, append to the end of an array-based list |
| List<Object> stack = new ArrayList<>(Math.max(1, vertexList.size())); |
| Iterator<Vertex> allAdjacent = null; |
| Vertex vertex = null; |
| Iterator<Vertex> allV = vertexList.iterator(); |
| state = NEXT_VERTEX; |
| nextStateLoop: while (true) { |
| switch (state) { |
| case NEXT_VERTEX : |
| // on entry, "allV" contains vertexes yet to be visited |
| if (!allV.hasNext()) { |
| // all done |
| break nextStateLoop; |
| } |
| Vertex nextVertex = allV.next(); |
| if (nextVertex.color == Vertex.WHITE) { |
| stack.add(NEXT_VERTEX_OBJECT); |
| vertex = nextVertex; |
| state = START_DFS_VISIT; |
| continue nextStateLoop; |
| } |
| state = NEXT_VERTEX; |
| continue nextStateLoop; |
| case START_DFS_VISIT : |
| // on entry, "vertex" contains the vertex to be visited |
| // top of stack is return code |
| // mark the vertex as discovered |
| vertex.color = Vertex.GREY; |
| allAdjacent = vertex.adjacent.iterator(); |
| state = NEXT_ADJACENT; |
| continue nextStateLoop; |
| case NEXT_ADJACENT : |
| // on entry, "allAdjacent" contains adjacent vertexes to |
| // be visited; "vertex" contains vertex being visited |
| if (allAdjacent.hasNext()) { |
| Vertex adjVertex = allAdjacent.next(); |
| if (adjVertex.color == Vertex.WHITE) { |
| // explore edge from vertex to adjVertex |
| adjVertex.predecessor = vertex; |
| stack.add(allAdjacent); |
| stack.add(vertex); |
| stack.add(AFTER_NEXTED_DFS_VISIT_OBJECT); |
| vertex = adjVertex; |
| state = START_DFS_VISIT; |
| continue nextStateLoop; |
| } |
| if (adjVertex.color == Vertex.GREY) { |
| // back edge (grey means visit in progress) |
| cycles = true; |
| } |
| state = NEXT_ADJACENT; |
| continue nextStateLoop; |
| } |
| // done exploring vertex |
| vertex.color = Vertex.BLACK; |
| time++; |
| vertex.finishTime = time; |
| state = ((Integer) stack.remove(stack.size() - 1)).intValue(); |
| continue nextStateLoop; |
| case AFTER_NEXTED_DFS_VISIT : |
| // on entry, stack contains "vertex" and "allAjacent" |
| vertex = (Vertex) stack.remove(stack.size() - 1); |
| @SuppressWarnings("unchecked") |
| Iterator<Vertex> unchecked = (Iterator<Vertex>) stack.remove(stack.size() - 1); |
| allAdjacent = unchecked; |
| state = NEXT_ADJACENT; |
| continue nextStateLoop; |
| } |
| } |
| } |
| |
| } |
| |
| /** |
| * Sorts the given list of projects in a manner that honors the given |
| * project reference relationships. That is, if project A references project |
| * B, then the resulting order will list B before A if possible. For graphs |
| * that do not contain cycles, the result is the same as a conventional |
| * topological sort. For graphs containing cycles, the order is based on |
| * ordering the strongly connected components of the graph. This has the |
| * effect of keeping each knot of projects together without otherwise |
| * affecting the order of projects not involved in a cycle. For a graph G, |
| * the algorithm performs in O(|G|) space and time. |
| * <p> |
| * When there is an arbitrary choice, vertexes are ordered as supplied. |
| * Arranged projects in descending alphabetical order generally results in |
| * an order that builds "A" before "Z" when there are no other constraints. |
| * </p> |
| * <p> Ref: Cormen, Leiserson, and Rivest <it>Introduction to |
| * Algorithms</it>, McGraw-Hill, 1990. The strongly-connected-components |
| * algorithm is in section 23.5. |
| * </p> |
| * |
| * @param objects a list of projects (element type: |
| * <code>IProject</code>) |
| * @param references a list of project references [A,B] meaning that A |
| * references B (element type: <code>IProject[]</code>) |
| * @return an object describing the resulting project order |
| */ |
| public static Object[][] computeNodeOrder(Object[] objects, Object[][] references) { |
| |
| // Step 1: Create the graph object. |
| final Digraph g1 = new Digraph(); |
| // add vertexes |
| for (Object object : objects) { |
| g1.addVertex(object); |
| } |
| // add edges |
| for (Object[] reference : references) { |
| // create an edge from q to p |
| // to cause q to come before p in eventual result |
| g1.addEdge(reference[1], reference[0]); |
| } |
| g1.freeze(); |
| |
| // Step 2: Create the transposed graph. This time, define the vertexes |
| // in decreasing order of depth-first finish time in g1 |
| // interchange "to" and "from" to reverse edges from g1 |
| final Digraph g2 = new Digraph(); |
| // add vertexes |
| List<Object> resortedVertexes = g1.idsByDFSFinishTime(false); |
| for (Iterator<Object> it = resortedVertexes.iterator(); it.hasNext();) |
| g2.addVertex(it.next()); |
| // add edges |
| for (Object[] reference : references) { |
| g2.addEdge(reference[0], reference[1]); |
| } |
| g2.freeze(); |
| |
| // Step 3: Return the vertexes in increasing order of depth-first finish |
| // time in g2 |
| List<Object> sortedProjectList = g2.idsByDFSFinishTime(true); |
| Object[] orderedNodes = new Object[sortedProjectList.size()]; |
| sortedProjectList.toArray(orderedNodes); |
| Object[][] knots; |
| boolean hasCycles = g2.containsCycles(); |
| if (hasCycles) { |
| List<Object[]> knotList = g2.nonTrivialComponents(); |
| knots = knotList.toArray(new Object[knotList.size()][]); |
| } else { |
| knots = new Object[0][]; |
| } |
| for (int i = 0; i < orderedNodes.length; i++) |
| objects[i] = orderedNodes[i]; |
| return knots; |
| } |
| } |