Coverage Report

 package org.kuali.rice.krms.framework.engine;
 
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.PriorityQueue;
 import java.util.Set;
 
 import org.apache.commons.lang.StringUtils;
 import org.kuali.rice.krms.api.Asset;
 import org.kuali.rice.krms.api.AssetResolutionEngine;
 import org.kuali.rice.krms.api.AssetResolutionException;
 import org.kuali.rice.krms.api.AssetResolver;
 
 public class AssetResolutionEngineImpl implements AssetResolutionEngine {
         private static final org.apache.log4j.Logger LOG = org.apache.log4j.Logger.getLogger(AssetResolutionEngineImpl.class);
         
         private final Map<Asset, List<AssetResolver<?>>> assetResolversByOutput = new HashMap<Asset, List<AssetResolver<?>>>();
         private final Map<AssetResolverKey, AssetResolver<?>> assetResolversByKey = new HashMap<AssetResolverKey, AssetResolver<?>>(); 
         
         // should this use soft refs?  Will require some refactoring to check if the referenced object is around;
         private final Map<Asset, Object> assetCache = new HashMap<Asset, Object>();
 
         @Override
         public void addAssetValue(Asset asset, Object value) {
                 assetCache.put(asset, value);
         }
         
         @Override
         public void addAssetResolver(AssetResolver<?> assetResolver) {
                 if (assetResolver == null) throw new IllegalArgumentException("assetResolver is reuqired");
                 if (assetResolver.getOutput() == null) throw new IllegalArgumentException("assetResolver.getOutput() must not be null");
 
                 List<AssetResolver<?>> assetResolvers = assetResolversByOutput.get(assetResolver.getOutput());
                 if (assetResolvers == null) {
                         assetResolvers = new LinkedList<AssetResolver<?>>();
                         assetResolversByOutput.put(assetResolver.getOutput(), assetResolvers);
                 }
                 assetResolversByKey.put(new AssetResolverKey(assetResolver), assetResolver);
                 assetResolvers.add(assetResolver);
         }
 
         @SuppressWarnings("unchecked")
         @Override
         public <T> T resolveAsset(final Asset asset) throws AssetResolutionException {
                 LOG.debug("+--> resolveAsset(" + asset + ")");
                 if (assetCache.containsKey(asset)) return (T)assetCache.get(asset);
                 
                 List<AssetResolverKey> resolutionPlan = buildAssetResolutionPlan(asset);
                 // TODO: could cache these plans somewhere, since future agendas will likely require the same plans
                 
                 LOG.debug("resolutionPlan: " + (resolutionPlan == null ? "null" : StringUtils.join(resolutionPlan.iterator(), ", ")));
                 
                 if (resolutionPlan != null) {
                         LOG.debug("executing plan");
                         for (AssetResolverKey resolverKey : resolutionPlan) {
                                 AssetResolver<?> resolver = assetResolversByKey.get(resolverKey);
                                 
                                 // build prereqs
                                 Map<Asset, Object> resolvedPrereqs = new HashMap<Asset, Object>();
                                 
                                 // Am I making unsafe assumptions?  
                                 // The plan order should guarantee these prereqs exist and are cached.
                                 for (Asset prereq : resolver.getPrerequisites()) {
                                         Object resolvedPrereq = assetCache.get(prereq);
                                         resolvedPrereqs.put(prereq, resolvedPrereq);
                                 }
                                 
                                 Object resolvedAsset = resolver.resolve(resolvedPrereqs);
                                 assetCache.put(resolver.getOutput(), resolvedAsset);
                         }                
                 } else {
                         throw new AssetResolutionException("Unable to plan the resolution of asset " + asset);
                 }
                 return (T)assetCache.get(asset);
         }
         
         // TODO: try to extract some methods out to shorten this beast
         protected List<AssetResolverKey> buildAssetResolutionPlan(Asset asset) {
                 // our result
                 List<AssetResolverKey> resolutionPlan = null;
                 
                 // Holds the resolvers we've visited, along with the needed metadata for generating our final plan
                 Map<AssetResolverKey, Visited> visitedByKey = new HashMap<AssetResolverKey, Visited>();
                 
                 // this holds a least cost first list of nodes remaining to be explored
                 PriorityQueue<ToVisit> toVisits = new PriorityQueue<ToVisit>(); // nice grammar there cowboy
                 
                 // dummy resolver to be the root of this tree
                 // Do I really need this?  Yes, because there may be more than one resolver that resolves to the desired asset,
                 // so this destination unifies the trees of those candidate resolvers
                 AssetResolver destination = createDestination(asset); // problem is we can't get this one out of the registry
                 AssetResolverKey destinationKey = new AssetResolverKey(destination);
                 
                 LOG.debug("Beginning resolution tree search for " + asset);
                 
                 // seed our queue of resolvers to visit
                 // need to be aware of null parent for root ToVisit
                 toVisits.add(new ToVisit(0, destination, null));
                 
                 // there may not be a viable plan
                 boolean plannedToDestination = false;
                 
                 // We'll do a modified Dijkstra's shortest path algorithm, where at each leaf we see if we've planned out
                 // asset resolution all the way up to the root, our destination.  If so, we just reconstruct our plan.
                 while (!plannedToDestination && toVisits.size() > 0) {
                         // visit least cost node remaining
                         ToVisit visiting = toVisits.poll();
 
                         LOG.debug("visiting " + visiting.getAssetResolverKey());
                         
                         // the resolver is the edge in our tree -- we don't get it directly from the assetResolversByKey Map, because it could be our destination
                         AssetResolver resolver = getResolver(visiting.getAssetResolverKey(), destination, destinationKey);
                         AssetResolver parent = getResolver(visiting.getParentKey(), destination, destinationKey);
                         
                         if (visitedByKey.containsKey(visiting.getAssetResolverKey())) {
                                 continue; // TODO: is this right?  will this make trouble?  We've already visited this one
                         }
                         
                         Visited parentVisited = visitedByKey.get(visiting.getParentKey());
                         
                         if (resolver == null) throw new RuntimeException("Unable to get AssetResolver by its key");
                         Set<Asset> prereqs = resolver.getPrerequisites();
                         // keep track of any prereqs that we already have handy
                         List<Asset> metPrereqs = new LinkedList<Asset>();
                         
                         // see what prereqs we have already, and which we'll need to visit
                         if (prereqs != null) for (Asset prereq : prereqs) {
                                 if (!assetCache.containsKey(prereq)) {
                                         // enqueue all resolvers in toVisits
                                         List<AssetResolver<?>> prereqResolvers = assetResolversByOutput.get(prereq);
                                         if (prereqResolvers != null) for (AssetResolver prereqResolver : prereqResolvers) {
                                                 toVisits.add(new ToVisit(visiting.getCost() /* cost to get to this resolver */, prereqResolver, resolver));
                                         }
                                 } else {
                                         metPrereqs.add(prereq);
                                 }
                         }
                         
                         // Build visited info
                         Visited visited = buildVisited(resolver, parentVisited, metPrereqs);
                         visitedByKey.put(visited.getResolverKey(), visited);
                         
                         plannedToDestination = isPlannedBackToDestination(visited, destinationKey, visitedByKey);
                 }
                 
                 if (plannedToDestination) {
                         // build result from Visited tree.
                         resolutionPlan = new LinkedList<AssetResolverKey>();
                         
                         assembleLinearResolutionPlan(visitedByKey.get(destinationKey), visitedByKey, resolutionPlan);
                 }
                 return resolutionPlan;
         }
         
         /**
          *  @return the Visited object for the resolver we just, er, well, visited.
          */
         private Visited buildVisited(AssetResolver resolver, Visited parentVisited, Collection<Asset> metPrereqs) {
                 Visited visited = null;
                 
                 List<AssetResolverKey> pathTo = new ArrayList<AssetResolverKey>(1 + (parentVisited == null ? 0 : parentVisited.pathTo.size()));
                 if (parentVisited != null && parentVisited.getPathTo() != null) pathTo.addAll(parentVisited.getPathTo());
                 if (parentVisited != null) pathTo.add(parentVisited.getResolverKey());
                 AssetResolverKey resolverKey = new AssetResolverKey(resolver);
                 
                 visited = new Visited(resolverKey, pathTo, resolver.getPrerequisites(), resolver.getCost() + (parentVisited == null ? 0 : parentVisited.getCost()));
                 for (Asset metPrereq : metPrereqs) { visited.addPlannedPrereq(metPrereq); }
         
                 return visited;
         }
 
         /**
          * our dummy destination isn't allowed to pollute assetResolversByKey, hence the ugly conditional encapsulated herein
          */
         private AssetResolver getResolver(AssetResolverKey resolverKey,
                         AssetResolver destination, AssetResolverKey destinationKey) {
                 AssetResolver resolver;
                 if (destinationKey.equals(resolverKey)) {
                         resolver = destination;
                 } else {
                         resolver = assetResolversByKey.get(resolverKey);
                 }
                 return resolver;
         }
 
         /**
          * @param visited
          * @param destinationKey
          * @param visitedByKey
          * @param plannedToDestination
          * @return
          */
         private boolean isPlannedBackToDestination(Visited visited,
                         AssetResolverKey destinationKey,
                         Map<AssetResolverKey, Visited> visitedByKey) {
                 boolean plannedToDestination = false;
                 if (visited.isFullyPlanned()) {
                         LOG.debug("Leaf! this resolver's prereqs are all avialable.");
                         // no traversing further yet, instead we need to check how far up the tree is fully planned out 
                         // step backwards toward the root of the tree and see if we're good all the way to our objective.
                         // if a node fully planned, move up the tree (towards the root) to see if its parent is fully planned, and so on.
                         
                         if (visited.getPathTo().size() > 0) {
                                 // reverse the path to
                                 List<AssetResolverKey> reversePathTo = new ArrayList<AssetResolverKey>(visited.getPathTo());
                                 Collections.reverse(reversePathTo);
                                 
                                 // we use this to propagate resolutions up the tree
                                 Visited previousAncestor = visited;
                                 
                                 for (AssetResolverKey ancestorKey : reversePathTo) {
                                         
                                         Visited ancestorVisited = visitedByKey.get(ancestorKey);
                                         ancestorVisited.addPlannedPrereq(previousAncestor.getResolverKey());
                                         
                                         LOG.debug("checking ancestor " + ancestorKey);
                                         
                                         if (ancestorVisited.isFullyPlanned() && ancestorKey.equals(destinationKey)) {
                                                 // Woot! Job's done!
                                                 plannedToDestination = true;
                                                 break;
                                         } else if (!ancestorVisited.isFullyPlanned()) { // if the ancestor isn't fully planned, we're done
                                                 LOG.debug("Still have planning to do.");
                                                 break;
                                         }
                                         // update previousAncestor reference for next iteration
                                         previousAncestor = ancestorVisited;
                                 }
                         } else {
                                 // we're done already! do a jig?
                                 LOG.debug("Trivial plan.");
                                 plannedToDestination = true;
                         }
                 }
                 return plannedToDestination;
         }
         
         private void assembleLinearResolutionPlan(Visited visited, Map<AssetResolverKey, Visited> visitedByKey, List<AssetResolverKey> plan) {
                 // DFS
                 for (AssetResolverKey prereqResolverKey : visited.getPrereqResolvers()) {
                         Visited prereqVisited = visitedByKey.get(prereqResolverKey);
                         assembleLinearResolutionPlan(prereqVisited, visitedByKey, plan);
                         plan.add(prereqResolverKey);
                 }
         }
 
         /**
          * Create our dummy destination resolver
          * @param asset
          */
         private AssetResolver<? extends Object> createDestination(final Asset asset) {
                 AssetResolver<?> destination = new AssetResolver<Object>() {
                         final Asset dest = new Asset("", "");
                         @Override
                         public int getCost() {
                                 return 0;
                         }
                         @Override
                         public Asset getOutput() {
                                 return dest;
                         }
                         @Override
                         public Set<Asset> getPrerequisites() {
                                 return Collections.<Asset>singleton(asset);
                         }
                         @Override
                         public Object resolve(Map<Asset, Object> resolvedPrereqs) throws AssetResolutionException {
                                 return null;
                         }
                 };
                 return destination;
         }
         
         
         private static class ToVisit implements Comparable<ToVisit> {
                 
                 private final int precost;
                 private final int addcost;
                 private final AssetResolverKey resolverKey;
                 
                 // the parent key is not being used for comparison purposes currently
                 private final AssetResolverKey parentKey;
                 
                 /**
                  * @param precost
                  * @param resolver
                  */
                 public ToVisit(int precost, AssetResolver resolver, AssetResolver parent) {
                         super();
                         this.precost = precost;
                         this.addcost = resolver.getCost();
                         this.resolverKey = new AssetResolverKey(resolver.getOutput(), resolver.getPrerequisites());
                         
                         if (parent != null) {
                                 this.parentKey = new AssetResolverKey(parent.getOutput(), parent.getPrerequisites());
                         } else {
                                 this.parentKey = null;
                         }
                 }
 
                 public int getCost() {
                         return precost + addcost;
                 }
                 
                 @Override
                 public boolean equals(Object obj) {
                         if (this == obj) return true;
                         if (obj == null) return false;
                         if (getClass() != obj.getClass())
                                 return false;                        
                         ToVisit other = (ToVisit)obj;
                         return this.compareTo(other) == 0;
                 }
                 
                 /* (non-Javadoc)
                  * @see java.lang.Object#hashCode()
                  */
                 @Override
                 public int hashCode() {
                         final int prime = 31;
                         int result = 1;
                         result = prime * result + getCost();
                         result = prime * result + ((resolverKey == null) ? 0 : resolverKey.hashCode());
                         return result;
                 }
                 
                 /**
                  * {@inheritDoc Comparable}
                  */
                 @Override
                 public int compareTo(ToVisit o) {
                         if (o == null) return 1;
                         if (getCost() > o.getCost()) return 1;
                         if (getCost() < o.getCost()) return -1;
                         return resolverKey.compareTo(o.resolverKey);
                 }
                 
                 public AssetResolverKey getAssetResolverKey() {
                         return resolverKey;
                 }
                 
                 public AssetResolverKey getParentKey() {
                         return parentKey;
                 }
                 
                 @Override
                 public String toString() {
                         return getClass().getSimpleName()+"("+getAssetResolverKey()+")";
                 }
         }
         
         protected static class AssetResolverKey implements Comparable<AssetResolverKey> {
                 private final List<Asset> data;
                 
                 // just used for toArray call
                 private static final Asset[] TYPER = new Asset[0];
                 
                 public AssetResolverKey(AssetResolver resolver) {
                         this(resolver.getOutput(), resolver.getPrerequisites());
                 }
                 
                 private AssetResolverKey(Asset dest, Set<Asset> prereqs) {
                         if (dest == null) throw new IllegalArgumentException("dest parameter must not be null");
                         data = new ArrayList<Asset>(1 + ((prereqs == null) ? 0 : prereqs.size())); // size ArrayList perfectly
                         data.add(dest);
                         if (prereqs != null) {
                                 // this is painful, but to be able to compare we need a defined order 
                                 Asset [] prereqsArray = prereqs.toArray(TYPER);
                                 Arrays.sort(prereqsArray);
                                 for (Asset prereq : prereqsArray) {
                                         data.add(prereq);
                                 }
                         }
                 }
                 
                 public Asset getOutput() {
                         return data.get(0);
                 }
                 
                 private String comparatorHelperMemo = null;
                 
                 private String getComparatorHelper() {
                         if (comparatorHelperMemo == null) {
                                 StringBuilder sb = new StringBuilder();
                                 for (int i=0; i<data.size(); i++) {
                                         Asset asset = data.get(i);
                                         if (i == 1) {
                                                 sb.append(" <- ");
                                         } else if (i > 1) {
                                                 sb.append(",");
                                         }
                                         if (asset != null) {
                                                 sb.append(asset.getComparatorHelper());
                                         }
                                 }
                                 comparatorHelperMemo = sb.toString();
                         }
                         return comparatorHelperMemo;
                 }
                         
                 @Override
                 public int compareTo(AssetResolverKey o) {
                         if (o == null) return 1;
                         return getComparatorHelper().compareTo(o.getComparatorHelper());
                 }
 
                 /* (non-Javadoc)
                  * @see java.lang.Object#hashCode()
                  */
                 @Override
                 public int hashCode() {
                         return data.hashCode();
                 }
 
                 /* (non-Javadoc)
                  * @see java.lang.Object#equals(java.lang.Object)
                  */
                 @Override
                 public boolean equals(Object obj) {
                         if (this == obj)
                                 return true;
                         if (obj == null)
                                 return false;
                         if (getClass() != obj.getClass())
                                 return false;
                         AssetResolverKey other = (AssetResolverKey) obj;
                         return this.compareTo(other) == 0;
                 }
                 
                 @Override
                 public String toString() {
                         return getClass().getSimpleName()+"("+getComparatorHelper()+")";
                 }
         }
         
         
         private static class Visited {
                 private AssetResolverKey resolverKey; 
                 private List<AssetResolverKey> pathTo;
                 private Set<Asset> remainingPrereqs;
                 private Map<Asset, AssetResolverKey> prereqResolvers;
                 private int cost;
                 
                 /**
                  * @param resolver
                  * @param pathTo
                  * @param fullyPlanned
                  * @param cost
                  */
                 public Visited(AssetResolverKey resolverKey, List<AssetResolverKey> pathTo, Set<Asset> prereqs, int cost) {
                         super();
                         this.resolverKey = resolverKey;
                         this.pathTo = pathTo;
                         this.remainingPrereqs = new HashSet<Asset>(prereqs);
                         this.prereqResolvers = new HashMap<Asset, AssetResolverKey>();
                         this.cost = cost;
                 }
 
                 /**
                  * @return the path from the goal node down to this resolver
                  */
                 public List<AssetResolverKey> getPathTo() {
                         return pathTo;
                 }
                 
                 public AssetResolverKey getResolverKey() {
                         return resolverKey;
                 }
                 
                 public Collection<AssetResolverKey> getPrereqResolvers() {
                         return prereqResolvers.values();
                 }
                 
                 /**
                  * @return true if resolution of all the prerequisites has been planned
                  */
                 public boolean isFullyPlanned() {
                         return remainingPrereqs.isEmpty();
                 }
                 
                 public int getCost() {
                         return cost;
                 }
                 
                 public void addPlannedPrereq(AssetResolverKey assetResolverKey) {
                         remainingPrereqs.remove(assetResolverKey.getOutput());
                         prereqResolvers.put(assetResolverKey.getOutput(), assetResolverKey);
                 }
                 
                 public void addPlannedPrereq(Asset asset) {
                         remainingPrereqs.remove(asset);
                 }
         }
         
         private static class InvalidResolutionPathException extends Exception {
                 private static final long serialVersionUID = 1L;
 
                 public InvalidResolutionPathException() {
                 }
         }        
 
 }
 
 

1		package org.kuali.rice.krms.framework.engine;
2
3		import java.util.ArrayList;
4		import java.util.Arrays;
5		import java.util.Collection;
6		import java.util.Collections;
7		import java.util.HashMap;
8		import java.util.HashSet;
9		import java.util.LinkedList;
10		import java.util.List;
11		import java.util.Map;
12		import java.util.PriorityQueue;
13		import java.util.Set;
14
15		import org.apache.commons.lang.StringUtils;
16		import org.kuali.rice.krms.api.Asset;
17		import org.kuali.rice.krms.api.AssetResolutionEngine;
18		import org.kuali.rice.krms.api.AssetResolutionException;
19		import org.kuali.rice.krms.api.AssetResolver;
20
21	0	public class AssetResolutionEngineImpl implements AssetResolutionEngine {
22	0	private static final org.apache.log4j.Logger LOG = org.apache.log4j.Logger.getLogger(AssetResolutionEngineImpl.class);
23
24	0	private final Map<Asset, List<AssetResolver<?>>> assetResolversByOutput = new HashMap<Asset, List<AssetResolver<?>>>();
25	0	private final Map<AssetResolverKey, AssetResolver<?>> assetResolversByKey = new HashMap<AssetResolverKey, AssetResolver<?>>();
26
27		// should this use soft refs? Will require some refactoring to check if the referenced object is around;
28	0	private final Map<Asset, Object> assetCache = new HashMap<Asset, Object>();
29
30		@Override
31		public void addAssetValue(Asset asset, Object value) {
32	0	assetCache.put(asset, value);
33	0	}
34
35		@Override
36		public void addAssetResolver(AssetResolver<?> assetResolver) {
37	0	if (assetResolver == null) throw new IllegalArgumentException("assetResolver is reuqired");
38	0	if (assetResolver.getOutput() == null) throw new IllegalArgumentException("assetResolver.getOutput() must not be null");
39
40	0	List<AssetResolver<?>> assetResolvers = assetResolversByOutput.get(assetResolver.getOutput());
41	0	if (assetResolvers == null) {
42	0	assetResolvers = new LinkedList<AssetResolver<?>>();
43	0	assetResolversByOutput.put(assetResolver.getOutput(), assetResolvers);
44		}
45	0	assetResolversByKey.put(new AssetResolverKey(assetResolver), assetResolver);
46	0	assetResolvers.add(assetResolver);
47	0	}
48
49		@SuppressWarnings("unchecked")
50		@Override
51		public <T> T resolveAsset(final Asset asset) throws AssetResolutionException {
52	0	LOG.debug("+--> resolveAsset(" + asset + ")");
53	0	if (assetCache.containsKey(asset)) return (T)assetCache.get(asset);
54
55	0	List<AssetResolverKey> resolutionPlan = buildAssetResolutionPlan(asset);
56		// TODO: could cache these plans somewhere, since future agendas will likely require the same plans
57
58	0	LOG.debug("resolutionPlan: " + (resolutionPlan == null ? "null" : StringUtils.join(resolutionPlan.iterator(), ", ")));
59
60	0	if (resolutionPlan != null) {
61	0	LOG.debug("executing plan");
62	0	for (AssetResolverKey resolverKey : resolutionPlan) {
63	0	AssetResolver<?> resolver = assetResolversByKey.get(resolverKey);
64
65		// build prereqs
66	0	Map<Asset, Object> resolvedPrereqs = new HashMap<Asset, Object>();
67
68		// Am I making unsafe assumptions?
69		// The plan order should guarantee these prereqs exist and are cached.
70	0	for (Asset prereq : resolver.getPrerequisites()) {
71	0	Object resolvedPrereq = assetCache.get(prereq);
72	0	resolvedPrereqs.put(prereq, resolvedPrereq);
73	0	}
74
75	0	Object resolvedAsset = resolver.resolve(resolvedPrereqs);
76	0	assetCache.put(resolver.getOutput(), resolvedAsset);
77	0	}
78		} else {
79	0	throw new AssetResolutionException("Unable to plan the resolution of asset " + asset);
80		}
81	0	return (T)assetCache.get(asset);
82		}
83
84		// TODO: try to extract some methods out to shorten this beast
85		protected List<AssetResolverKey> buildAssetResolutionPlan(Asset asset) {
86		// our result
87	0	List<AssetResolverKey> resolutionPlan = null;
88
89		// Holds the resolvers we've visited, along with the needed metadata for generating our final plan
90	0	Map<AssetResolverKey, Visited> visitedByKey = new HashMap<AssetResolverKey, Visited>();
91
92		// this holds a least cost first list of nodes remaining to be explored
93	0	PriorityQueue<ToVisit> toVisits = new PriorityQueue<ToVisit>(); // nice grammar there cowboy
94
95		// dummy resolver to be the root of this tree
96		// Do I really need this? Yes, because there may be more than one resolver that resolves to the desired asset,
97		// so this destination unifies the trees of those candidate resolvers
98	0	AssetResolver destination = createDestination(asset); // problem is we can't get this one out of the registry
99	0	AssetResolverKey destinationKey = new AssetResolverKey(destination);
100
101	0	LOG.debug("Beginning resolution tree search for " + asset);
102
103		// seed our queue of resolvers to visit
104		// need to be aware of null parent for root ToVisit
105	0	toVisits.add(new ToVisit(0, destination, null));
106
107		// there may not be a viable plan
108	0	boolean plannedToDestination = false;
109
110		// We'll do a modified Dijkstra's shortest path algorithm, where at each leaf we see if we've planned out
111		// asset resolution all the way up to the root, our destination. If so, we just reconstruct our plan.
112	0	while (!plannedToDestination && toVisits.size() > 0) {
113		// visit least cost node remaining
114	0	ToVisit visiting = toVisits.poll();
115
116	0	LOG.debug("visiting " + visiting.getAssetResolverKey());
117
118		// the resolver is the edge in our tree -- we don't get it directly from the assetResolversByKey Map, because it could be our destination
119	0	AssetResolver resolver = getResolver(visiting.getAssetResolverKey(), destination, destinationKey);
120	0	AssetResolver parent = getResolver(visiting.getParentKey(), destination, destinationKey);
121
122	0	if (visitedByKey.containsKey(visiting.getAssetResolverKey())) {
123	0	continue; // TODO: is this right? will this make trouble? We've already visited this one
124		}
125
126	0	Visited parentVisited = visitedByKey.get(visiting.getParentKey());
127
128	0	if (resolver == null) throw new RuntimeException("Unable to get AssetResolver by its key");
129	0	Set<Asset> prereqs = resolver.getPrerequisites();
130		// keep track of any prereqs that we already have handy
131	0	List<Asset> metPrereqs = new LinkedList<Asset>();
132
133		// see what prereqs we have already, and which we'll need to visit
134	0	if (prereqs != null) for (Asset prereq : prereqs) {
135	0	if (!assetCache.containsKey(prereq)) {
136		// enqueue all resolvers in toVisits
137	0	List<AssetResolver<?>> prereqResolvers = assetResolversByOutput.get(prereq);
138	0	if (prereqResolvers != null) for (AssetResolver prereqResolver : prereqResolvers) {
139	0	toVisits.add(new ToVisit(visiting.getCost() /* cost to get to this resolver */, prereqResolver, resolver));
140		}
141	0	} else {
142	0	metPrereqs.add(prereq);
143		}
144		}
145
146		// Build visited info
147	0	Visited visited = buildVisited(resolver, parentVisited, metPrereqs);
148	0	visitedByKey.put(visited.getResolverKey(), visited);
149
150	0	plannedToDestination = isPlannedBackToDestination(visited, destinationKey, visitedByKey);
151	0	}
152
153	0	if (plannedToDestination) {
154		// build result from Visited tree.
155	0	resolutionPlan = new LinkedList<AssetResolverKey>();
156
157	0	assembleLinearResolutionPlan(visitedByKey.get(destinationKey), visitedByKey, resolutionPlan);
158		}
159	0	return resolutionPlan;
160		}
161
162		/**
163		* @return the Visited object for the resolver we just, er, well, visited.
164		*/
165		private Visited buildVisited(AssetResolver resolver, Visited parentVisited, Collection<Asset> metPrereqs) {
166	0	Visited visited = null;
167
168	0	List<AssetResolverKey> pathTo = new ArrayList<AssetResolverKey>(1 + (parentVisited == null ? 0 : parentVisited.pathTo.size()));
169	0	if (parentVisited != null && parentVisited.getPathTo() != null) pathTo.addAll(parentVisited.getPathTo());
170	0	if (parentVisited != null) pathTo.add(parentVisited.getResolverKey());
171	0	AssetResolverKey resolverKey = new AssetResolverKey(resolver);
172
173	0	visited = new Visited(resolverKey, pathTo, resolver.getPrerequisites(), resolver.getCost() + (parentVisited == null ? 0 : parentVisited.getCost()));
174	0	for (Asset metPrereq : metPrereqs) { visited.addPlannedPrereq(metPrereq); }
175
176	0	return visited;
177		}
178
179		/**
180		* our dummy destination isn't allowed to pollute assetResolversByKey, hence the ugly conditional encapsulated herein
181		*/
182		private AssetResolver getResolver(AssetResolverKey resolverKey,
183		AssetResolver destination, AssetResolverKey destinationKey) {
184		AssetResolver resolver;
185	0	if (destinationKey.equals(resolverKey)) {
186	0	resolver = destination;
187		} else {
188	0	resolver = assetResolversByKey.get(resolverKey);
189		}
190	0	return resolver;
191		}
192
193		/**
194		* @param visited
195		* @param destinationKey
196		* @param visitedByKey
197		* @param plannedToDestination
198		* @return
199		*/
200		private boolean isPlannedBackToDestination(Visited visited,
201		AssetResolverKey destinationKey,
202		Map<AssetResolverKey, Visited> visitedByKey) {
203	0	boolean plannedToDestination = false;
204	0	if (visited.isFullyPlanned()) {
205	0	LOG.debug("Leaf! this resolver's prereqs are all avialable.");
206		// no traversing further yet, instead we need to check how far up the tree is fully planned out
207		// step backwards toward the root of the tree and see if we're good all the way to our objective.
208		// if a node fully planned, move up the tree (towards the root) to see if its parent is fully planned, and so on.
209
210	0	if (visited.getPathTo().size() > 0) {
211		// reverse the path to
212	0	List<AssetResolverKey> reversePathTo = new ArrayList<AssetResolverKey>(visited.getPathTo());
213	0	Collections.reverse(reversePathTo);
214
215		// we use this to propagate resolutions up the tree
216	0	Visited previousAncestor = visited;
217
218	0	for (AssetResolverKey ancestorKey : reversePathTo) {
219
220	0	Visited ancestorVisited = visitedByKey.get(ancestorKey);
221	0	ancestorVisited.addPlannedPrereq(previousAncestor.getResolverKey());
222
223	0	LOG.debug("checking ancestor " + ancestorKey);
224
225	0	if (ancestorVisited.isFullyPlanned() && ancestorKey.equals(destinationKey)) {
226		// Woot! Job's done!
227	0	plannedToDestination = true;
228	0	break;
229	0	} else if (!ancestorVisited.isFullyPlanned()) { // if the ancestor isn't fully planned, we're done
230	0	LOG.debug("Still have planning to do.");
231	0	break;
232		}
233		// update previousAncestor reference for next iteration
234	0	previousAncestor = ancestorVisited;
235	0	}
236	0	} else {
237		// we're done already! do a jig?
238	0	LOG.debug("Trivial plan.");
239	0	plannedToDestination = true;
240		}
241		}
242	0	return plannedToDestination;
243		}
244
245		private void assembleLinearResolutionPlan(Visited visited, Map<AssetResolverKey, Visited> visitedByKey, List<AssetResolverKey> plan) {
246		// DFS
247	0	for (AssetResolverKey prereqResolverKey : visited.getPrereqResolvers()) {
248	0	Visited prereqVisited = visitedByKey.get(prereqResolverKey);
249	0	assembleLinearResolutionPlan(prereqVisited, visitedByKey, plan);
250	0	plan.add(prereqResolverKey);
251	0	}
252	0	}
253
254		/**
255		* Create our dummy destination resolver
256		* @param asset
257		*/
258		private AssetResolver<? extends Object> createDestination(final Asset asset) {
259	0	AssetResolver<?> destination = new AssetResolver<Object>() {
260	0	final Asset dest = new Asset("", "");
261		@Override
262		public int getCost() {
263	0	return 0;
264		}
265		@Override
266		public Asset getOutput() {
267	0	return dest;
268		}
269		@Override
270		public Set<Asset> getPrerequisites() {
271	0	return Collections.<Asset>singleton(asset);
272		}
273		@Override
274		public Object resolve(Map<Asset, Object> resolvedPrereqs) throws AssetResolutionException {
275	0	return null;
276		}
277		};
278	0	return destination;
279		}
280
281
282	0	private static class ToVisit implements Comparable<ToVisit> {
283
284		private final int precost;
285		private final int addcost;
286		private final AssetResolverKey resolverKey;
287
288		// the parent key is not being used for comparison purposes currently
289		private final AssetResolverKey parentKey;
290
291		/**
292		* @param precost
293		* @param resolver
294		*/
295		public ToVisit(int precost, AssetResolver resolver, AssetResolver parent) {
296	0	super();
297	0	this.precost = precost;
298	0	this.addcost = resolver.getCost();
299	0	this.resolverKey = new AssetResolverKey(resolver.getOutput(), resolver.getPrerequisites());
300
301	0	if (parent != null) {
302	0	this.parentKey = new AssetResolverKey(parent.getOutput(), parent.getPrerequisites());
303		} else {
304	0	this.parentKey = null;
305		}
306	0	}
307
308		public int getCost() {
309	0	return precost + addcost;
310		}
311
312		@Override
313		public boolean equals(Object obj) {
314	0	if (this == obj) return true;
315	0	if (obj == null) return false;
316	0	if (getClass() != obj.getClass())
317	0	return false;
318	0	ToVisit other = (ToVisit)obj;
319	0	return this.compareTo(other) == 0;
320		}
321
322		/* (non-Javadoc)
323		* @see java.lang.Object#hashCode()
324		*/
325		@Override
326		public int hashCode() {
327	0	final int prime = 31;
328	0	int result = 1;
329	0	result = prime * result + getCost();
330	0	result = prime * result + ((resolverKey == null) ? 0 : resolverKey.hashCode());
331	0	return result;
332		}
333
334		/**
335		* {@inheritDoc Comparable}
336		*/
337		@Override
338		public int compareTo(ToVisit o) {
339	0	if (o == null) return 1;
340	0	if (getCost() > o.getCost()) return 1;
341	0	if (getCost() < o.getCost()) return -1;
342	0	return resolverKey.compareTo(o.resolverKey);
343		}
344
345		public AssetResolverKey getAssetResolverKey() {
346	0	return resolverKey;
347		}
348
349		public AssetResolverKey getParentKey() {
350	0	return parentKey;
351		}
352
353		@Override
354		public String toString() {
355	0	return getClass().getSimpleName()+"("+getAssetResolverKey()+")";
356		}
357		}
358
359	0	protected static class AssetResolverKey implements Comparable<AssetResolverKey> {
360		private final List<Asset> data;
361
362		// just used for toArray call
363	0	private static final Asset[] TYPER = new Asset[0];
364
365		public AssetResolverKey(AssetResolver resolver) {
366	0	this(resolver.getOutput(), resolver.getPrerequisites());
367	0	}
368
369	0	private AssetResolverKey(Asset dest, Set<Asset> prereqs) {
370	0	if (dest == null) throw new IllegalArgumentException("dest parameter must not be null");
371	0	data = new ArrayList<Asset>(1 + ((prereqs == null) ? 0 : prereqs.size())); // size ArrayList perfectly
372	0	data.add(dest);
373	0	if (prereqs != null) {
374		// this is painful, but to be able to compare we need a defined order
375	0	Asset [] prereqsArray = prereqs.toArray(TYPER);
376	0	Arrays.sort(prereqsArray);
377	0	for (Asset prereq : prereqsArray) {
378	0	data.add(prereq);
379		}
380		}
381	0	}
382
383		public Asset getOutput() {
384	0	return data.get(0);
385		}
386
387	0	private String comparatorHelperMemo = null;
388
389		private String getComparatorHelper() {
390	0	if (comparatorHelperMemo == null) {
391	0	StringBuilder sb = new StringBuilder();
392	0	for (int i=0; i<data.size(); i++) {
393	0	Asset asset = data.get(i);
394	0	if (i == 1) {
395	0	sb.append(" <- ");
396	0	} else if (i > 1) {
397	0	sb.append(",");
398		}
399	0	if (asset != null) {
400	0	sb.append(asset.getComparatorHelper());
401		}
402		}
403	0	comparatorHelperMemo = sb.toString();
404		}
405	0	return comparatorHelperMemo;
406		}
407
408		@Override
409		public int compareTo(AssetResolverKey o) {
410	0	if (o == null) return 1;
411	0	return getComparatorHelper().compareTo(o.getComparatorHelper());
412		}
413
414		/* (non-Javadoc)
415		* @see java.lang.Object#hashCode()
416		*/
417		@Override
418		public int hashCode() {
419	0	return data.hashCode();
420		}
421
422		/* (non-Javadoc)
423		* @see java.lang.Object#equals(java.lang.Object)
424		*/
425		@Override
426		public boolean equals(Object obj) {
427	0	if (this == obj)
428	0	return true;
429	0	if (obj == null)
430	0	return false;
431	0	if (getClass() != obj.getClass())
432	0	return false;
433	0	AssetResolverKey other = (AssetResolverKey) obj;
434	0	return this.compareTo(other) == 0;
435		}
436
437		@Override
438		public String toString() {
439	0	return getClass().getSimpleName()+"("+getComparatorHelper()+")";
440		}
441		}
442
443
444	0	private static class Visited {
445		private AssetResolverKey resolverKey;
446		private List<AssetResolverKey> pathTo;
447		private Set<Asset> remainingPrereqs;
448		private Map<Asset, AssetResolverKey> prereqResolvers;
449		private int cost;
450
451		/**
452		* @param resolver
453		* @param pathTo
454		* @param fullyPlanned
455		* @param cost
456		*/
457		public Visited(AssetResolverKey resolverKey, List<AssetResolverKey> pathTo, Set<Asset> prereqs, int cost) {
458	0	super();
459	0	this.resolverKey = resolverKey;
460	0	this.pathTo = pathTo;
461	0	this.remainingPrereqs = new HashSet<Asset>(prereqs);
462	0	this.prereqResolvers = new HashMap<Asset, AssetResolverKey>();
463	0	this.cost = cost;
464	0	}
465
466		/**
467		* @return the path from the goal node down to this resolver
468		*/
469		public List<AssetResolverKey> getPathTo() {
470	0	return pathTo;
471		}
472
473		public AssetResolverKey getResolverKey() {
474	0	return resolverKey;
475		}
476
477		public Collection<AssetResolverKey> getPrereqResolvers() {
478	0	return prereqResolvers.values();
479		}
480
481		/**
482		* @return true if resolution of all the prerequisites has been planned
483		*/
484		public boolean isFullyPlanned() {
485	0	return remainingPrereqs.isEmpty();
486		}
487
488		public int getCost() {
489	0	return cost;
490		}
491
492		public void addPlannedPrereq(AssetResolverKey assetResolverKey) {
493	0	remainingPrereqs.remove(assetResolverKey.getOutput());
494	0	prereqResolvers.put(assetResolverKey.getOutput(), assetResolverKey);
495	0	}
496
497		public void addPlannedPrereq(Asset asset) {
498	0	remainingPrereqs.remove(asset);
499	0	}
500		}
501
502	0	private static class InvalidResolutionPathException extends Exception {
503		private static final long serialVersionUID = 1L;
504
505	0	public InvalidResolutionPathException() {
506	0	}
507		}
508
509		}
510
511