| /* |
| * Copyright 2000-2014 JetBrains s.r.o. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package com.intellij.openapi.extensions; |
| |
| import com.intellij.openapi.util.Couple; |
| import com.intellij.openapi.util.text.StringUtil; |
| import com.intellij.util.containers.ContainerUtil; |
| import com.intellij.util.graph.CachingSemiGraph; |
| import com.intellij.util.graph.DFSTBuilder; |
| import com.intellij.util.graph.GraphGenerator; |
| import org.jdom.Element; |
| import org.jetbrains.annotations.NonNls; |
| import org.jetbrains.annotations.NotNull; |
| import org.jetbrains.annotations.Nullable; |
| |
| import java.util.*; |
| |
| /** |
| * All extensions can have an "order" attribute in their XML element that will affect the place where this extension will appear in the |
| * {@link ExtensionPoint#getExtensions()}. Possible values are "first", "last", "before ID" and "after ID" where ID |
| * is another same-type extension ID. Values can be combined in a comma-separated way. E.g. if you wish to plug before some extension XXX |
| * that has "first" as its order, you must be "first, before XXX". The same with "last".<p> |
| * |
| * Extension ID can be specified in the "id" attribute of corresponding XML element. When you specify order, it's usually a good practice |
| * to specify also id, to allow other plugin-writers to plug relatively to your extension.<p> |
| * |
| * If some anchor id can't be resolved, the constraint is ignored. |
| * |
| * @author Alexander Kireyev |
| */ |
| public class LoadingOrder { |
| @NonNls private static final String FIRST_STR = "FIRST"; |
| @NonNls private static final String LAST_STR = "LAST"; |
| @NonNls private static final String BEFORE_STR = "BEFORE "; |
| @NonNls private static final String BEFORE_STR_OLD = "BEFORE:"; |
| @NonNls private static final String AFTER_STR = "AFTER "; |
| @NonNls private static final String AFTER_STR_OLD = "AFTER:"; |
| |
| public static final LoadingOrder ANY = new LoadingOrder(); |
| public static final LoadingOrder FIRST = new LoadingOrder(FIRST_STR); |
| public static final LoadingOrder LAST = new LoadingOrder(LAST_STR); |
| |
| @NonNls private final String myName; // for debug only |
| private final boolean myFirst; |
| private final boolean myLast; |
| private final Set<String> myBefore = new HashSet<String>(2); |
| private final Set<String> myAfter = new HashSet<String>(2); |
| |
| private LoadingOrder() { |
| myName = "ANY"; |
| myFirst = false; |
| myLast = false; |
| } |
| |
| private LoadingOrder(@NonNls @NotNull String text) { |
| myName = text; |
| boolean last = false; |
| boolean first = false; |
| for (final String string : StringUtil.split(text, ",")) { |
| String trimmed = string.trim(); |
| if (trimmed.equalsIgnoreCase(FIRST_STR)) first = true; |
| else if (trimmed.equalsIgnoreCase(LAST_STR)) last = true; |
| else if (StringUtil.startsWithIgnoreCase(trimmed, BEFORE_STR)) myBefore.add(trimmed.substring(BEFORE_STR.length()).trim()); |
| else if (StringUtil.startsWithIgnoreCase(trimmed, BEFORE_STR_OLD)) myBefore.add(trimmed.substring(BEFORE_STR_OLD.length()).trim()); |
| else if (StringUtil.startsWithIgnoreCase(trimmed, AFTER_STR)) myAfter.add(trimmed.substring(AFTER_STR.length()).trim()); |
| else if (StringUtil.startsWithIgnoreCase(trimmed, AFTER_STR_OLD)) myAfter.add(trimmed.substring(AFTER_STR_OLD.length()).trim()); |
| else throw new AssertionError("Invalid specification: " + trimmed + "; should be one of FIRST, LAST, BEFORE <id> or AFTER <id>"); |
| } |
| myFirst = first; |
| myLast = last; |
| } |
| |
| public String toString() { |
| return myName; |
| } |
| |
| public boolean equals(final Object o) { |
| if (this == o) return true; |
| if (!(o instanceof LoadingOrder)) return false; |
| |
| final LoadingOrder that = (LoadingOrder)o; |
| |
| if (myFirst != that.myFirst) return false; |
| if (myLast != that.myLast) return false; |
| if (!myAfter.equals(that.myAfter)) return false; |
| if (!myBefore.equals(that.myBefore)) return false; |
| |
| return true; |
| } |
| |
| public int hashCode() { |
| int result = myFirst ? 1 : 0; |
| result = 31 * result + (myLast ? 1 : 0); |
| result = 31 * result + myBefore.hashCode(); |
| result = 31 * result + myAfter.hashCode(); |
| return result; |
| } |
| |
| public static LoadingOrder before(@NonNls final String id) { |
| return new LoadingOrder(BEFORE_STR + id); |
| } |
| |
| public static LoadingOrder after(@NonNls final String id) { |
| return new LoadingOrder(AFTER_STR + id); |
| } |
| |
| public static void sort(@NotNull Orderable... orderable) { |
| sort(Arrays.asList(orderable)); |
| } |
| |
| public static void sort(@NotNull final List<? extends Orderable> orderable) { |
| // our graph is pretty sparse so do benefit from the fact |
| final Map<String, Orderable> map = ContainerUtil.newHashMap(); |
| final Map<Orderable, LoadingOrder> cachedMap = ContainerUtil.newHashMap(); |
| final Set<Orderable> first = ContainerUtil.newHashSet(1); |
| final Set<Orderable> hasBefore = ContainerUtil.newHashSet(orderable.size()); |
| |
| for (Orderable o : orderable) { |
| String id = o.getOrderId(); |
| if (StringUtil.isNotEmpty(id)) map.put(id, o); |
| LoadingOrder order = o.getOrder(); |
| cachedMap.put(o, order); |
| if (order.myFirst) first.add(o); |
| if (order.myBefore.size() != 0) hasBefore.add(o); |
| } |
| |
| GraphGenerator.SemiGraph<Orderable> graph = new GraphGenerator.SemiGraph<Orderable>() { |
| @Override |
| public Collection<Orderable> getNodes() { |
| List<Orderable> list = ContainerUtil.newArrayList(orderable); |
| Collections.reverse(list); |
| return list; |
| } |
| |
| @Override |
| public Iterator<Orderable> getIn(Orderable n) { |
| LoadingOrder order = cachedMap.get(n); |
| |
| Set<Orderable> predecessors = new LinkedHashSet<Orderable>(); |
| for (String id : order.myAfter) { |
| Orderable o = map.get(id); |
| if (o != null) { |
| predecessors.add(o); |
| } |
| } |
| |
| String id = n.getOrderId(); |
| if (StringUtil.isNotEmpty(id)) { |
| for (Orderable o : hasBefore) { |
| LoadingOrder hisOrder = cachedMap.get(o); |
| if (hisOrder.myBefore.contains(id)) { |
| predecessors.add(o); |
| } |
| } |
| } |
| |
| if (order.myLast) { |
| for (Orderable o : orderable) { |
| LoadingOrder hisOrder = cachedMap.get(o); |
| if (!hisOrder.myLast) { |
| predecessors.add(o); |
| } |
| } |
| } |
| |
| if (!order.myFirst) { |
| predecessors.addAll(first); |
| } |
| |
| return predecessors.iterator(); |
| } |
| }; |
| |
| DFSTBuilder<Orderable> builder = new DFSTBuilder<Orderable>(new GraphGenerator<Orderable>(new CachingSemiGraph<Orderable>(graph))); |
| |
| if (!builder.isAcyclic()) { |
| Couple<Orderable> p = builder.getCircularDependency(); |
| throw new SortingException("Could not satisfy sorting requirements", p.first.getDescribingElement(), p.second.getDescribingElement()); |
| } |
| |
| Collections.sort(orderable, builder.comparator()); |
| } |
| |
| public static LoadingOrder readOrder(@NonNls String orderAttr) { |
| return orderAttr != null ? new LoadingOrder(orderAttr) : ANY; |
| } |
| |
| public interface Orderable { |
| @Nullable |
| String getOrderId(); |
| LoadingOrder getOrder(); |
| Element getDescribingElement(); |
| } |
| } |