| /** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You 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 org.apache.aries.blueprint.container; |
| |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Iterator; |
| import java.util.LinkedHashMap; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.Map; |
| |
| import org.apache.aries.blueprint.di.CircularDependencyException; |
| import org.apache.aries.blueprint.di.Recipe; |
| import org.apache.aries.blueprint.di.RefRecipe; |
| import org.osgi.service.blueprint.container.NoSuchComponentException; |
| import org.slf4j.Logger; |
| import org.slf4j.LoggerFactory; |
| |
| public class DependencyGraph { |
| |
| private static final Logger LOGGER = LoggerFactory.getLogger(DependencyGraph.class); |
| |
| private BlueprintRepository repository; |
| |
| public DependencyGraph(BlueprintRepository repository) { |
| this.repository = repository; |
| } |
| |
| public LinkedHashMap<String, Recipe> getSortedRecipes(Collection<String> names) { |
| // construct the graph |
| Map<String, Node> nodes = new LinkedHashMap<String, Node>(); |
| for (String name : names) { |
| Object object = repository.getObject(name); |
| if (object == null) { |
| throw new NoSuchComponentException(name); |
| } |
| if (object instanceof Recipe) { |
| Recipe recipe = (Recipe) object; |
| if (!recipe.getName().equals(name)) { |
| throw new RuntimeException("Recipe '" + name + "' returned from the repository has name '" + name + "'"); |
| } |
| createNode(name, recipe, nodes); |
| } |
| } |
| |
| // find all initial leaf nodes (and islands) |
| List<Node> sortedNodes = new ArrayList<Node>(nodes.size()); |
| LinkedList<Node> leafNodes = new LinkedList<Node>(); |
| for (Node n : nodes.values()) { |
| if (n.referenceCount == 0) { |
| // if the node is totally isolated (no in or out refs), |
| // move it directly to the finished list, so they are first |
| if (n.references.size() == 0) { |
| sortedNodes.add(n); |
| } else { |
| leafNodes.add(n); |
| } |
| } |
| } |
| |
| // pluck the leaves until there are no leaves remaining |
| while (!leafNodes.isEmpty()) { |
| Node node = leafNodes.removeFirst(); |
| sortedNodes.add(node); |
| for (Node ref : node.references) { |
| ref.referenceCount--; |
| if (ref.referenceCount == 0) { |
| leafNodes.add(ref); |
| } |
| } |
| } |
| |
| // There are no more leaves so if there are there still |
| // unprocessed nodes in the graph, we have one or more curcuits |
| if (sortedNodes.size() != nodes.size()) { |
| findCircuit(nodes.values().iterator().next(), new ArrayList<Recipe>(nodes.size())); |
| // find circuit should never fail, if it does there is a programming error |
| throw new RuntimeException("Internal Error: expected a CircularDependencyException"); |
| } |
| |
| // return the recipes |
| LinkedHashMap<String, Recipe> sortedRecipes = new LinkedHashMap<String, Recipe>(); |
| for (Node node : sortedNodes) { |
| sortedRecipes.put(node.name, node.recipe); |
| } |
| |
| return sortedRecipes; |
| } |
| |
| private void findCircuit(Node node, ArrayList<Recipe> stack) { |
| if (stack.contains(node.recipe)) { |
| ArrayList<Recipe> circularity = new ArrayList<Recipe>(stack.subList(stack.indexOf(node.recipe), stack.size())); |
| |
| // remove anonymous nodes from circularity list |
| for (Iterator<Recipe> iterator = circularity.iterator(); iterator.hasNext();) { |
| Recipe recipe = iterator.next(); |
| if (recipe != node.recipe && recipe.getName() == null) { |
| iterator.remove(); |
| } |
| } |
| |
| // add ending node to list so a full circuit is shown |
| circularity.add(node.recipe); |
| |
| throw new CircularDependencyException(circularity); |
| } |
| |
| stack.add(node.recipe); |
| for (Node reference : node.references) { |
| findCircuit(reference, stack); |
| } |
| } |
| |
| private Node createNode(String name, Recipe recipe, Map<String, Node> nodes) { |
| // if node already exists, verify that the exact same recipe instnace is used for both |
| if (nodes.containsKey(name)) { |
| Node node = nodes.get(name); |
| if (node.recipe != recipe) { |
| throw new RuntimeException("The name '" + name +"' is assigned to multiple recipies"); |
| } |
| return node; |
| } |
| |
| // create the node |
| Node node = new Node(); |
| node.name = name; |
| node.recipe = recipe; |
| nodes.put(name, node); |
| |
| // link in the references |
| LinkedList<Recipe> constructorRecipes = new LinkedList<Recipe>(recipe.getConstructorDependencies()); |
| while (!constructorRecipes.isEmpty()) { |
| Recipe nestedRecipe = constructorRecipes.removeFirst(); |
| if (nestedRecipe instanceof RefRecipe) { |
| nestedRecipe = nestedRecipe.getDependencies().get(0); |
| String nestedName = nestedRecipe.getName(); |
| Node nestedNode = createNode(nestedName, nestedRecipe, nodes); |
| node.referenceCount++; |
| nestedNode.references.add(node); |
| } else { |
| constructorRecipes.addAll(nestedRecipe.getDependencies()); |
| } |
| } |
| |
| return node; |
| } |
| |
| private class Node { |
| String name; |
| Recipe recipe; |
| final List<Node> references = new ArrayList<Node>(); |
| int referenceCount; |
| |
| public String toString() { |
| StringBuffer buf = new StringBuffer(); |
| buf.append("Node[").append(name); |
| if (references.size() > 0) { |
| buf.append(" <- "); |
| Iterator<Node> iter = references.iterator(); |
| while(iter.hasNext()) { |
| buf.append(iter.next().name); |
| if (iter.hasNext()) { |
| buf.append(", "); |
| } |
| } |
| } |
| buf.append("]"); |
| return buf.toString(); |
| } |
| |
| } |
| } |