Skip to main content
aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorPascal Rapicault2011-10-25 14:04:56 -0400
committerPascal Rapicault2011-10-25 14:04:56 -0400
commitb5721d073827007f961cb0e5adb26ef38116ef29 (patch)
tree7f2cb226bfa6fdde82f1718db826360a870afd5a
parentad226d17b124a02d73266d29b68618551b82cc45 (diff)
downloadrt.equinox.p2-sortingOperands.tar.gz
rt.equinox.p2-sortingOperands.tar.xz
rt.equinox.p2-sortingOperands.zip
progress on sorting operandssortingOperands
-rw-r--r--bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ComputeNodeOrder.java503
-rw-r--r--bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/Engine.java2
-rw-r--r--bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/OperandSorter.java137
-rw-r--r--bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/PhaseSet.java4
-rw-r--r--bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ProvisioningPlan.java10
-rw-r--r--bundles/org.eclipse.equinox.p2.tests/src/org/eclipse/equinox/p2/tests/engine/OperandSorterTest.java46
6 files changed, 696 insertions, 6 deletions
diff --git a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ComputeNodeOrder.java b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ComputeNodeOrder.java
new file mode 100644
index 000000000..68be27702
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ComputeNodeOrder.java
@@ -0,0 +1,503 @@
+package org.eclipse.equinox.internal.p2.engine;
+
+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<Vertex>(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<Vertex>(100);
+
+ /**
+ * Map from id to vertex.
+ *
+ * Key type: <code>Object</code>; value type: <code>Vertex</code>
+ */
+ private Map<Object, Vertex> vertexMap = new HashMap<Object, Vertex>(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 (Iterator<Vertex> allV = vertexList.iterator(); allV.hasNext();) {
+ Vertex vertex = allV.next();
+ 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<Vertex, List<Object>>();
+ for (Iterator<Vertex> it = vertexList.iterator(); it.hasNext();) {
+ Vertex vertex = it.next();
+ 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<Object>(2);
+ component.add(root.id);
+ components.put(root, component);
+ }
+ component.add(vertex.id);
+ }
+ }
+ List<Object[]> result = new ArrayList<Object[]>(components.size());
+ for (Iterator<List<Object>> it = components.values().iterator(); it.hasNext();) {
+ List<Object> component = it.next();
+ 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 = new Integer(NEXT_VERTEX);
+ final Integer AFTER_NEXTED_DFS_VISIT_OBJECT = new Integer(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<Object>(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 (int i = 0; i < objects.length; i++)
+ g1.addVertex(objects[i]);
+ // add edges
+ for (int i = 0; i < references.length; i++)
+ // create an edge from q to p
+ // to cause q to come before p in eventual result
+ g1.addEdge(references[i][1], references[i][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 (int i = 0; i < references.length; i++)
+ g2.addEdge(references[i][0], references[i][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;
+ }
+}
diff --git a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/Engine.java b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/Engine.java
index abe5c56d1..1d833f34b 100644
--- a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/Engine.java
+++ b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/Engine.java
@@ -62,7 +62,7 @@ public class Engine implements IEngine {
= ((ProvisioningPlan) plan).getOperands();
// = ((ProvisioningPlan) plan).getOperands();
// new OperandSorter(plan.getAdditions(), true).sortBundles(installOrder);
- Operand[] operandsSortedForInstall, Operand[] operandsSortedForUninstall, ProvisioningContext context,
+// Operand[] operandsSortedForInstall, Operand[] operandsSortedForUninstall, ProvisioningContext context,
PhaseSet phaseSet = (PhaseSet) phases;
checkArguments(iprofile, phaseSet, operandsSortedForUninstall, operandsSortedForUninstall, context, monitor);
diff --git a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/OperandSorter.java b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/OperandSorter.java
new file mode 100644
index 000000000..fc1bdc372
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/OperandSorter.java
@@ -0,0 +1,137 @@
+package org.eclipse.equinox.internal.p2.engine;
+
+import java.util.*;
+import org.eclipse.equinox.p2.metadata.IInstallableUnit;
+import org.eclipse.equinox.p2.metadata.IRequirement;
+import org.eclipse.equinox.p2.query.*;
+
+public class OperandSorter {
+ IQueryable<IInstallableUnit> allIUs;
+ IInstallableUnit[] sortedIUs;
+ boolean doingInstall = true;
+ Operand[] operandsToSort = null;
+
+ Map<IInstallableUnit, Operand> iuToIUOperand = new HashMap<IInstallableUnit, Operand>();
+ Map<IInstallableUnit, Operand> iuToIUPropertyOperand = new HashMap<IInstallableUnit, Operand>();
+
+ public OperandSorter(IQueryable<IInstallableUnit> allIUs, boolean installOrUninstall) {
+ this.allIUs = allIUs;
+ doingInstall = installOrUninstall;
+ }
+
+ private void indexOperands() {
+ for (int i = 0; i < operandsToSort.length; i++) {
+ if (operandsToSort[i] instanceof InstallableUnitOperand) {
+ InstallableUnitOperand iuo = (InstallableUnitOperand) operandsToSort[i];
+ if (iuo.first() != null)
+ iuToIUOperand.put(iuo.first(), iuo);
+ if (iuo.second() != null)
+ iuToIUOperand.put(iuo.second(), iuo);
+ }
+
+ if (operandsToSort[i] instanceof InstallableUnitPropertyOperand) {
+ InstallableUnitPropertyOperand iupo = (InstallableUnitPropertyOperand) operandsToSort[i];
+ iuToIUPropertyOperand.put(iupo.getInstallableUnit(), iupo);
+ }
+ }
+ }
+
+ public void sortOperands(Operand[] operands) {
+ operandsToSort = operands;
+ sortedIUs = allIUs.query(QueryUtil.ALL_UNITS, null).toUnmodifiableSet().toArray(new IInstallableUnit[0]);
+ sortIUs();
+ indexOperands();
+ computeInstallOrder();
+ computeUninstallOrder();
+ }
+
+ private ArrayList<Operand> installOrder;
+ private ArrayList<Operand> uninstallOrder;
+
+ private void computeInstallOrder() {
+ installOrder = new ArrayList<Operand>(); //TODO size
+ for (int i = 0; i < sortedIUs.length; i++) {
+ IInstallableUnit iInstallableUnit = sortedIUs[i];
+
+ Operand candidate = iuToIUPropertyOperand.get(iInstallableUnit);
+ if (candidate != null)
+ installOrder.add(iuToIUPropertyOperand.get(iInstallableUnit));
+
+ candidate = iuToIUOperand.get(iInstallableUnit);
+ if (candidate != null)
+ installOrder.add(iuToIUOperand.get(iInstallableUnit));
+ }
+ }
+
+ private void computeUninstallOrder() {
+ uninstallOrder = new ArrayList<Operand>(); //TODO size
+ for (int i = (sortedIUs.length - 1); i != 0; i--) {
+ IInstallableUnit iInstallableUnit = sortedIUs[i];
+
+ Operand candidate = iuToIUPropertyOperand.get(iInstallableUnit);
+ if (candidate != null)
+ uninstallOrder.add(iuToIUPropertyOperand.get(iInstallableUnit));
+
+ candidate = iuToIUOperand.get(iInstallableUnit);
+ if (candidate != null)
+ uninstallOrder.add(iuToIUOperand.get(iInstallableUnit));
+ }
+ }
+
+ public ArrayList<Operand> getUninstallOrder() {
+ assert (operandsToSort.length == uninstallOrder.size());
+ return uninstallOrder;
+ }
+
+ public ArrayList<Operand> getInstallOrder() {
+ assert (operandsToSort.length == installOrder.size());
+ return installOrder;
+ }
+
+ private Object[][] sortIUs() {
+ List<Object[]> references = new ArrayList<Object[]>(sortedIUs.length);
+ for (int i = 0; i < sortedIUs.length; i++) {
+ buildReferences(sortedIUs[i], references);
+ }
+ Object[][] cycles = ComputeNodeOrder.computeNodeOrder(sortedIUs, references.toArray(new Object[references.size()][]));
+ if (cycles.length == 0)
+ return cycles;
+ // // fix up host/fragment orders (bug 184127)
+ // for (int i = 0; i < cycles.length; i++) {
+ // for (int j = 0; j < cycles[i].length; j++) {
+ // BundleDescription fragment = (BundleDescription) cycles[i][j];
+ // if (fragment.getHost() == null)
+ // continue;
+ // BundleDescription host = (BundleDescription) fragment.getHost().getSupplier();
+ // if (host == null)
+ // continue;
+ // fixFragmentOrder(host, fragment, toSort);
+ // }
+ // }
+ return cycles;
+ }
+
+ private void buildReferences(IInstallableUnit description, List<Object[]> references) {
+ //TODO Do we need to deal with patches in a special way?
+ //TODO Do we need to deal with fragmnets?
+ //TODO Do we need to deal with
+
+ buildReferences(description, description.getRequirements(), references);
+ }
+
+ private void buildReferences(IInstallableUnit description, Collection<IRequirement> dependencies, List<Object[]> references) {
+ for (IRequirement req : dependencies) {
+ IQueryResult<IInstallableUnit> matches = allIUs.query(QueryUtil.createMatchQuery(req.getMatches()), null);
+ for (Iterator<IInstallableUnit> iterator = matches.iterator(); iterator.hasNext();) {
+ addReference(description, iterator.next(), references);
+ }
+ }
+ }
+
+ private void addReference(IInstallableUnit description, IInstallableUnit reference, List<Object[]> references) {
+ // build the reference from the description
+ if (description == reference || reference == null)
+ return;
+ references.add(new Object[] {description, reference});
+ }
+}
diff --git a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/PhaseSet.java b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/PhaseSet.java
index b02cc3814..3f7d6d7e3 100644
--- a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/PhaseSet.java
+++ b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/PhaseSet.java
@@ -29,7 +29,7 @@ public class PhaseSet implements IPhaseSet {
public final MultiStatus perform(EngineSession session, Operand[] operandsSortedForInstall, Operand[] operandsSortedForUninstall, IProgressMonitor monitor) {
MultiStatus status = new MultiStatus(EngineActivator.ID, IStatus.OK, null, null);
- int[] weights = getProgressWeights(operands);
+ int[] weights = getProgressWeights(operandsSortedForInstall);
int totalWork = getTotalWork(weights);
SubMonitor pm = SubMonitor.convert(monitor, totalWork);
try {
@@ -41,7 +41,7 @@ public class PhaseSet implements IPhaseSet {
Phase phase = phases[i];
phase.actionManager = (ActionManager) session.getAgent().getService(ActionManager.SERVICE_NAME);
try {
- phase.perform(status, session, phase.getProcessingOrder() == Phase.INSTALL_ORDER ? operandsSortedForInstall : operandsSortedForUninstall, pm.newChild(weights[i]));
+ phase.perform(status, session, phase.getProcessingOrder() == Phase.ORDER_INSTALL ? operandsSortedForInstall : operandsSortedForUninstall, pm.newChild(weights[i]));
} catch (OperationCanceledException e) {
// propagate operation cancellation
status.add(new Status(IStatus.CANCEL, EngineActivator.ID, e.getMessage(), e));
diff --git a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ProvisioningPlan.java b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ProvisioningPlan.java
index 22c19a5ab..88e4196a5 100644
--- a/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ProvisioningPlan.java
+++ b/bundles/org.eclipse.equinox.p2.engine/src/org/eclipse/equinox/internal/p2/engine/ProvisioningPlan.java
@@ -10,8 +10,6 @@
*******************************************************************************/
package org.eclipse.equinox.internal.p2.engine;
-import org.eclipse.equinox.internal.p2.director.OperandSorter;
-
import java.util.*;
import org.eclipse.core.runtime.*;
import org.eclipse.equinox.internal.p2.metadata.InstallableUnit;
@@ -198,12 +196,18 @@ public class ProvisioningPlan implements IProvisioningPlan {
Operand[] getOrderedPlanForInstall() {
Operand[] sortedPlan = getOperands();
- new OperandSorter(new CompoundQueryable<IInstallableUnit>(new IQueryable[] { profile }new QueryablePlan(true), true).sortBundles(sortedPlan);
+ if (!sortOperands)
+ return sortedPlan;
+
+ //TODO To change for futureState
+ new OperandSorter(new CompoundQueryable<IInstallableUnit>(new IQueryable[] {profile}), true).sortBundles(sortedPlan);
return sortedPlan;
}
Operand[] getOrderedPlanForUninstall() {
Operand[] sortedPlan = getOperands();
+ if (!sortOperands)
+ return sortedPlan;
new OperandSorter(new QueryablePlan(false), false).sortBundles(sortedPlan);
return sortedPlan;
}
diff --git a/bundles/org.eclipse.equinox.p2.tests/src/org/eclipse/equinox/p2/tests/engine/OperandSorterTest.java b/bundles/org.eclipse.equinox.p2.tests/src/org/eclipse/equinox/p2/tests/engine/OperandSorterTest.java
new file mode 100644
index 000000000..9784da17d
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.tests/src/org/eclipse/equinox/p2/tests/engine/OperandSorterTest.java
@@ -0,0 +1,46 @@
+package org.eclipse.equinox.p2.tests.engine;
+
+import org.eclipse.equinox.internal.p2.engine.*;
+import org.eclipse.equinox.p2.metadata.*;
+import org.eclipse.equinox.p2.query.QueryUtil;
+import org.eclipse.equinox.p2.tests.AbstractProvisioningTest;
+
+public class OperandSorterTest extends AbstractProvisioningTest {
+
+ public void testSort() {
+ IRequirement[] req = new IRequirement[1];
+ req[0] = MetadataFactory.createRequirement(IInstallableUnit.NAMESPACE_IU_ID, "B", VersionRange.emptyRange, null, false, false, true);
+ IInstallableUnit a = createIU("A", req);
+ IInstallableUnit b = createIU("B");
+ IInstallableUnit c = createIU("C");
+
+ {
+ InstallableUnitOperand op = new InstallableUnitOperand(createResolvedIU(a), null);
+ InstallableUnitOperand op2 = new InstallableUnitOperand(createResolvedIU(b), null);
+ InstallableUnitOperand[] operands = new InstallableUnitOperand[] {op, op2};
+
+ OperandSorter sorter = new OperandSorter(createTestMetdataRepository(new IInstallableUnit[] {a, b, c}).query(QueryUtil.ALL_UNITS, null), true);
+ sorter.sortOperands(operands);
+ System.out.println(sorter.getInstallOrder());
+ System.out.println(sorter.getUninstallOrder());
+ }
+
+ {
+ InstallableUnitOperand op = new InstallableUnitOperand(createResolvedIU(a), null);
+ // InstallableUnitOperand op2 = new InstallableUnitOperand(createResolvedIU(b), null);
+ // InstallableUnitPropertyOperand op3 = new InstallableUnitPropertyOperand(b, "key", null, "val2");
+ InstallableUnitPropertyOperand op4 = new InstallableUnitPropertyOperand(a, "key", "addVal", null);
+ Operand[] operands = new Operand[] {op, op4};
+
+ OperandSorter sorter = new OperandSorter(createTestMetdataRepository(new IInstallableUnit[] {a, b, c}).query(QueryUtil.ALL_UNITS, null), true);
+ sorter.sortOperands(operands);
+ System.out.println(sorter.getInstallOrder());
+ System.out.println(sorter.getUninstallOrder());
+ }
+ }
+
+ //Nothing to do
+ //Try sorting with property related operands
+
+ //Try sorting with dep order different between the pre and the post
+}

Back to the top