| /******************************************************************************* |
| * Copyright (c) 2015, 2018 Manumitting Technologies Inc 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: |
| * Brian de Alwis (MTI) - initial API and implementation |
| * Lars Vogel <Lars.Vogel@vogella.com> - Bug 472654 |
| ******************************************************************************/ |
| |
| package org.eclipse.e4.ui.internal.workbench; |
| |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.LinkedHashMap; |
| import java.util.LinkedHashSet; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.Map; |
| |
| /** |
| * This class implements a topological sort. The implementation distinguishes between the objects to |
| * be sorted from their corresponding dependency identifier, and properly tracks where multiple |
| * objects have the same identifier. This is required for sorting Eclipse Extension Registry |
| * extensions by their plug-in dependencies, as a plug-in may contribute multiple sets of |
| * extensions. |
| * |
| * <p> |
| * The implementation creates a dependency graph where the vertices represent the object identifiers |
| * and the edges represent the required-relation between them. Subclasses must implement of |
| * {@link #getRequirements(Object)} and {@link #getDependencies(Object)}. Although these are |
| * normally symmetric operations (i.e., if <em>B</em> is a requirement of <em>A</em>, then |
| * <em>A</em> is a dependent of <em>B</em>), one may be easier to compute than the other in some |
| * contexts and so this class combines the results. |
| * </p> |
| * |
| * <p> |
| * Description of the algorithm: |
| * </p> |
| * <ol> |
| * <li>Construct the dependency graph with {@link #getRequirements(Object)} and |
| * {@link #getDependencies(Object)}. The out edges represent requirements, and in edges represent |
| * dependencies. This graph may be disconnected if there are nodes with no dependencies amongst each |
| * other.</li> |
| * <li>Sort the list of identifiers by their out-degree, and then by in-degree. Ids with out-degree |
| * 0 are roots; if there is no id with out-degree 0 then we have a cycle. We sort nodes with the |
| * same out-degree by their in-degree to privilege nodes within the cycle from those that are |
| * dependencies (e.g., consider: A → B, B → C, C → A, D → A; all have out-degree |
| * 1, but A has in-degree 2, and A must be output before D).</li> |
| * <li>While there are ids left to consider, take the id with lowest out-degree and add its objects |
| * to the list. Remove the id from all of its dependents' required lists. This removal changes the |
| * out-degree and may require that the id list be resorted since some of the dependents may now be |
| * roots. Note that should we encounter a cycle (i.e., no nodes of degree 0), we process all the |
| * bundles within the cycle, since any dependencies to any single ndoe within the cycle effectively |
| * extends to all.</li> |
| * </ol> |
| * |
| * @param <T> |
| * the type of objects being sorted |
| * @param <ID> |
| * the type of the object identifiers; multiple objects of T may correspond to the same |
| * ID |
| */ |
| public abstract class TopologicalSort<T, ID> { |
| private final Map<ID, Collection<T>> mappedObjects = new LinkedHashMap<>(); |
| // Captures the bundles that are listed as requirements for a particular bundle. |
| private final Map<ID, Collection<ID>> requires = new LinkedHashMap<>(); |
| // Captures the bundles that list a particular bundle as a requirement |
| private final Map<ID, Collection<ID>> depends = new LinkedHashMap<>(); |
| |
| /** |
| * Return the identifier for the given object. The implementation properly tracks where multiple |
| * objects have the same identifier. |
| * |
| * @param object |
| * the object |
| * @return the identifier |
| */ |
| protected abstract ID getId(T object); |
| |
| /** |
| * Return the list of IDs required by {@code id}. Implementors may choose to return {@code null} |
| * or an empty collection if this information is more easily computed by |
| * {@link #getDependencies(Object)}. |
| * |
| * @param id |
| * the id |
| * @return the IDs required by {@code id}; may be {@code null} |
| */ |
| protected abstract Collection<ID> getRequirements(ID id); |
| |
| /** |
| * Return the list of IDs depended upon by {@code id}. Implementors may choose to return |
| * {@code null} or an empty collection if this information is more easily computed by |
| * {@link #getRequirements(Object)}. |
| * |
| * @param id |
| * the id |
| * @return the IDs depended upon by {@code id}; may be {@code null} |
| */ |
| protected abstract Collection<ID> getDependencies(ID id); |
| |
| /** |
| * Sort the provided extensions by the dependencies of their contributors. Note that sorting is |
| * done in-place. |
| * |
| * @param objects |
| * the objects to be sorted |
| * @return the objects in a topologically-sorted order |
| */ |
| public T[] sort(T[] objects) { |
| if (objects.length <= 1) { |
| return objects; |
| } |
| |
| addAll(objects); |
| return process(objects); |
| } |
| |
| /** Place results in results and return results */ |
| private T[] process(T[] results) { |
| buildDependencyGraph(); |
| |
| // Sort nodes by out-degree ({@code requires}) and then by in-degree. |
| // There are two situations: we have disconnected graphs |
| // In case of a cycle, one of the nodes involved in the cycle should have |
| // higher in-degree from some other non-cyclic node |
| int resultsIndex = 0; |
| List<ID> sortedByOutdegree = new ArrayList<>(requires.keySet()); |
| Comparator<ID> outdegreeSorter = (o1, o2) -> { |
| assert requires.containsKey(o1) && requires.containsKey(o2); |
| int comparison = requires.get(o1).size() - requires.get(o2).size(); |
| if (comparison == 0) { |
| // Select the node whose removal would have the greatest effect |
| return depends.get(o2).size() - depends.get(o1).size(); |
| } |
| return comparison; |
| }; |
| sortedByOutdegree.sort(outdegreeSorter); |
| |
| while (!sortedByOutdegree.isEmpty()) { |
| // don't sort unnecessarily: the current ordering is fine providing |
| // item #0 still has no dependencies |
| if (!requires.get(sortedByOutdegree.get(0)).isEmpty()) { |
| sortedByOutdegree.sort(outdegreeSorter); |
| } |
| LinkedList<ID> cycleToBeDone = new LinkedList<>(); |
| cycleToBeDone.add(sortedByOutdegree.remove(0)); |
| while (!cycleToBeDone.isEmpty()) { |
| ID bundleId = cycleToBeDone.removeFirst(); |
| assert depends.containsKey(bundleId) && requires.containsKey(bundleId); |
| for (T ext : mappedObjects.get(bundleId)) { |
| results[resultsIndex++] = ext; |
| } |
| // requires.get(bundleId) is empty unless there's a cycle; |
| // we process all nodes within the cycle now |
| for (ID reqId : requires.get(bundleId)) { |
| if (!cycleToBeDone.contains(reqId)) { |
| cycleToBeDone.add(reqId); |
| } |
| sortedByOutdegree.remove(reqId); |
| depends.get(reqId).remove(bundleId); |
| } |
| requires.remove(bundleId); |
| for (ID depId : depends.get(bundleId)) { |
| requires.get(depId).remove(bundleId); |
| } |
| depends.remove(bundleId); |
| } |
| } |
| return results; |
| } |
| |
| /** |
| * @param objects |
| */ |
| private void addAll(T[] objects) { |
| // first build up the list of object ids actually being considered |
| for (T o : objects) { |
| ID id = getId(o); |
| Collection<T> exts = mappedObjects.get(id); |
| if (exts == null) { |
| mappedObjects.put(id, exts = new LinkedHashSet<>()); |
| } |
| exts.add(o); |
| } |
| } |
| |
| private void buildDependencyGraph() { |
| // reset |
| requires.clear(); |
| depends.clear(); |
| for (ID id : mappedObjects.keySet()) { |
| requires.put(id, new LinkedHashSet<>()); |
| depends.put(id, new LinkedHashSet<>()); |
| } |
| |
| // now populate the dependency graph |
| for (ID subjectId : mappedObjects.keySet()) { |
| assert requires.containsKey(subjectId) && depends.containsKey(subjectId); |
| |
| Collection<ID> requirements = getRequirements(subjectId); |
| if (requirements != null) { |
| for (ID requiredId : requirements) { |
| assert !requiredId.equals(subjectId) : "self-cycles not supported"; //$NON-NLS-1$ |
| // ignore objects not being sorted |
| if (!mappedObjects.containsKey(requiredId)) { |
| continue; |
| } |
| // So requiredId is a requirement for subjectId |
| // and subjectId is a dependent of requiredId |
| depends.get(requiredId).add(subjectId); |
| requires.get(subjectId).add(requiredId); |
| } |
| } |
| |
| Collection<ID> dependencies = getDependencies(subjectId); |
| if (dependencies != null) { |
| for (ID dependentId : dependencies) { |
| assert !dependentId.equals(subjectId) : "self-cycles not supported"; //$NON-NLS-1$ |
| // ignore objects not being sorted |
| if (!mappedObjects.containsKey(dependentId)) { |
| continue; |
| } |
| // So dependentId is a dependency of subjectId |
| // and subjectId is a requirement of dependentId |
| requires.get(dependentId).add(subjectId); |
| depends.get(subjectId).add(dependentId); |
| } |
| } |
| } |
| } |
| } |