001 /**
002 * Copyright 2005-2013 The Kuali Foundation
003 *
004 * Licensed under the Educational Community License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/ecl2.php
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016 package org.kuali.rice.krms.framework.engine;
017
018 import java.util.ArrayList;
019 import java.util.Arrays;
020 import java.util.Collection;
021 import java.util.Collections;
022 import java.util.HashMap;
023 import java.util.HashSet;
024 import java.util.Iterator;
025 import java.util.LinkedList;
026 import java.util.List;
027 import java.util.Map;
028 import java.util.Map.Entry;
029 import java.util.PriorityQueue;
030 import java.util.Set;
031
032 import org.apache.commons.collections.CollectionUtils;
033 import org.apache.commons.lang.ArrayUtils;
034 import org.apache.commons.lang.StringUtils;
035 import org.kuali.rice.krms.api.engine.Term;
036 import org.kuali.rice.krms.api.engine.TermResolutionEngine;
037 import org.kuali.rice.krms.api.engine.TermResolutionException;
038 import org.kuali.rice.krms.api.engine.TermResolver;
039
040 /**
041 * An implementation of {@link TermResolutionEngine}
042 * @author Kuali Rice Team (rice.collab@kuali.org)
043 */
044 public class TermResolutionEngineImpl implements TermResolutionEngine {
045 private static final org.apache.log4j.Logger LOG = org.apache.log4j.Logger.getLogger(TermResolutionEngineImpl.class);
046
047 private final Map<String, List<TermResolver<?>>> termResolversByOutput = new HashMap<String, List<TermResolver<?>>>();
048 private final Map<TermResolverKey, TermResolver<?>> termResolversByKey = new HashMap<TermResolverKey, TermResolver<?>>();
049
050 // should this use soft refs? Will require some refactoring to check if the referenced object is around;
051 private final Map<Term, Object> termCache = new HashMap<Term, Object>();
052
053 @Override
054 public void addTermValue(Term term, Object value) {
055 termCache.put(term, value);
056 }
057
058 @Override
059 public void addTermResolver(TermResolver<?> termResolver) {
060 if (termResolver == null) throw new IllegalArgumentException("termResolver is reuqired");
061 if (termResolver.getOutput() == null) throw new IllegalArgumentException("termResolver.getOutput() must not be null");
062
063 List<TermResolver<?>> termResolvers = termResolversByOutput.get(termResolver.getOutput());
064 if (termResolvers == null) {
065 termResolvers = new LinkedList<TermResolver<?>>();
066 termResolversByOutput.put(termResolver.getOutput(), termResolvers);
067 }
068 termResolversByKey.put(new TermResolverKey(termResolver), termResolver);
069 termResolvers.add(termResolver);
070 }
071
072 @SuppressWarnings("unchecked")
073 @Override
074 public <T> T resolveTerm(Term term) throws TermResolutionException {
075 LOG.debug("+--> resolveTerm(" + term + ")");
076 if (termCache.containsKey(term)) return (T)termCache.get(term);
077
078 String termName = term.getName();
079
080 // build plan w/ termName spec for correct TermResolver selection
081 List<TermResolverKey> resolutionPlan = buildTermResolutionPlan(termName);
082 // TODO: could cache these plans somewhere, since future agendas will likely require the same plans
083
084 LOG.debug("resolutionPlan: " + (resolutionPlan == null ? "null" : StringUtils.join(resolutionPlan.iterator(), ", ")));
085
086 if (resolutionPlan != null) {
087 LOG.debug("executing plan");
088 for (TermResolverKey resolverKey : resolutionPlan) {
089 TermResolver<?> resolver = termResolversByKey.get(resolverKey);
090
091 // build prereqs
092 Map<String, Object> resolvedPrereqs = new HashMap<String, Object>();
093
094 // The plan order should guarantee these prereqs exist and are cached.
095 for (String prereq : resolver.getPrerequisites()) {
096 Object resolvedPrereq = termCache.get(new Term(prereq, null));
097 resolvedPrereqs.put(prereq, resolvedPrereq);
098 }
099
100 Map<String, String> providedParameters = Collections.emptyMap();
101 // The destination Term (and only the dest Term) can be parameterized
102 if (termName.equals(resolver.getOutput())) {
103 providedParameters = term.getParameters();
104
105 // throw a TermResolutionException if the params doen't match up
106 validateTermParameters(resolver, providedParameters);
107 }
108
109 Object resolvedTerm = resolver.resolve(resolvedPrereqs, providedParameters);
110 if (termName.equals(resolver.getOutput())) {
111 termCache.put(term, resolvedTerm);
112 } else {
113 if (!CollectionUtils.isEmpty(resolver.getParameterNames())) {
114 // Shouldn't happen due to checks in buildResolutionPlan
115 throw new TermResolutionException("TermResolvers requiring parameters cannot be intermediates in the Term resolution plan", resolver, providedParameters);
116 }
117 termCache.put(new Term(resolver.getOutput(), null), resolvedTerm);
118 }
119 }
120 } else {
121 throw new TermResolutionException("Unable to plan the resolution of " + term, null, null);
122 }
123 return (T)termCache.get(term);
124 }
125
126 /**
127 * This method checks that the required parameters (as returned by the {@link TermResolver} via
128 * {@link TermResolver#getParameterNames()}) are met in the {@link Map} of provided parameters.
129 *
130 * @param resolver {@link TermResolver}
131 * @param providedParameters
132 * @throws TermResolutionException if provided parameters do not match requirements
133 */
134 private void validateTermParameters(TermResolver<?> resolver,
135 Map<String, String> providedParameters)
136 throws TermResolutionException {
137 // validate that params match what the TermResolver requires
138 if (!providedParameters.keySet().equals(resolver.getParameterNames())) {
139 StringBuilder sb = new StringBuilder();
140
141 boolean first = true;
142 for (Entry<String,String> param : providedParameters.entrySet()) {
143 if (first) {
144 first = false;
145 } else {
146 sb.append(",");
147 }
148 sb.append(param.getKey());
149 sb.append("=");
150 sb.append(param.getValue());
151 }
152
153 throw new TermResolutionException("provided parameters ("+ sb
154 +") do not match requirements ("
155 + StringUtils.join(resolver.getParameterNames(), ",") +")", resolver, providedParameters);
156 }
157 }
158
159 /**
160 *
161 * @param termName
162 * @return List<{@link TermResolverKey}>
163 */
164 protected List<TermResolverKey> buildTermResolutionPlan(String termName) {
165 // our result
166 List<TermResolverKey> resolutionPlan = null;
167
168 // Holds the resolvers we've visited, along with the needed metadata for generating our final plan
169 Map<TermResolverKey, Visited> visitedByKey = new HashMap<TermResolverKey, Visited>();
170
171 // this holds a least cost first list of nodes remaining to be explored
172 PriorityQueue<ToVisit> toVisits = new PriorityQueue<ToVisit>(); // nice grammar there cowboy
173
174 // dummy resolver to be the root of this tree
175 // Do I really need this? Yes, because there may be more than one resolver that resolves to the desired termName,
176 // so this destination unifies the trees of those candidate resolvers
177 TermResolver destination = createDestination(termName); // problem is we can't get this one out of the registry
178 TermResolverKey destinationKey = new TermResolverKey(destination);
179
180 LOG.debug("Beginning resolution tree search for " + termName);
181
182 // seed our queue of resolvers to visit
183 // need to be aware of null parent for root ToVisit
184 toVisits.add(new ToVisit(0, destination, null));
185
186 // there may not be a viable plan
187 boolean plannedToDestination = false;
188
189 // We'll do a modified Dijkstra's shortest path algorithm, where at each leaf we see if we've planned out
190 // termName resolution all the way up to the root, our destination. If so, we just reconstruct our plan.
191 while (!plannedToDestination && toVisits.size() > 0) {
192 // visit least cost node remaining
193 ToVisit visiting = toVisits.poll();
194
195 LOG.debug("visiting " + visiting.getTermResolverKey());
196
197 // the resolver is the edge in our tree -- we don't get it directly from the termResolversByKey Map, because it could be our destination
198 TermResolver resolver = getResolver(visiting.getTermResolverKey(), destination, destinationKey);
199 TermResolver parent = getResolver(visiting.getParentKey(), destination, destinationKey);
200
201 if (visitedByKey.containsKey(visiting.getTermResolverKey())) {
202 continue; // We've already visited this one
203 }
204
205 Visited parentVisited = visitedByKey.get(visiting.getParentKey());
206
207 if (resolver == null) throw new RuntimeException("Unable to get TermResolver by its key");
208 Set<String> prereqs = resolver.getPrerequisites();
209 // keep track of any prereqs that we already have handy
210 List<String> metPrereqs = new LinkedList<String>();
211
212 // see what prereqs we have already, and which we'll need to visit
213 if (prereqs != null) for (String prereq : prereqs) {
214 if (!termCache.containsKey(new Term(prereq, null))) {
215 // enqueue all resolvers in toVisits
216 List<TermResolver<?>> prereqResolvers = termResolversByOutput.get(prereq);
217 if (prereqResolvers != null) for (TermResolver prereqResolver : prereqResolvers) {
218 // Only TermResolvers that don't take paramaterized terms can be chained, so:
219 // if the TermResolver doesn't take parameters, or it resolves the output termName
220 if (CollectionUtils.isEmpty(prereqResolver.getParameterNames()) ||
221 termName.equals(prereqResolver.getOutput()))
222 {
223 // queue it up for visiting
224 toVisits.add(new ToVisit(visiting.getCost() /* cost to get to this resolver */, prereqResolver, resolver));
225 }
226 }
227 } else {
228 metPrereqs.add(prereq);
229 }
230 }
231
232 // Build visited info
233 Visited visited = buildVisited(resolver, parentVisited, metPrereqs);
234 visitedByKey.put(visited.getResolverKey(), visited);
235
236 plannedToDestination = isPlannedBackToDestination(visited, destinationKey, visitedByKey);
237 }
238
239 if (plannedToDestination) {
240 // build result from Visited tree.
241 resolutionPlan = new LinkedList<TermResolverKey>();
242
243 assembleLinearResolutionPlan(visitedByKey.get(destinationKey), visitedByKey, resolutionPlan);
244 }
245 return resolutionPlan;
246 }
247
248 /**
249 * @return the Visited object for the resolver we just, er, well, visited.
250 */
251 private Visited buildVisited(TermResolver resolver, Visited parentVisited, Collection<String> metPrereqs) {
252 Visited visited = null;
253
254 List<TermResolverKey> pathTo = new ArrayList<TermResolverKey>(1 + (parentVisited == null ? 0 : parentVisited.pathTo.size()));
255 if (parentVisited != null && parentVisited.getPathTo() != null) pathTo.addAll(parentVisited.getPathTo());
256 if (parentVisited != null) pathTo.add(parentVisited.getResolverKey());
257 TermResolverKey resolverKey = new TermResolverKey(resolver);
258
259 visited = new Visited(resolverKey, pathTo, resolver.getPrerequisites(), resolver.getCost() + (parentVisited == null ? 0 : parentVisited.getCost()));
260 for (String metPrereq : metPrereqs) { visited.addPlannedPrereq(metPrereq); }
261
262 return visited;
263 }
264
265 /**
266 * our dummy destination isn't allowed to pollute termResolversByKey, hence the ugly conditional encapsulated herein
267 */
268 private TermResolver getResolver(TermResolverKey resolverKey,
269 TermResolver destination, TermResolverKey destinationKey) {
270 TermResolver resolver;
271 if (destinationKey.equals(resolverKey)) {
272 resolver = destination;
273 } else {
274 resolver = termResolversByKey.get(resolverKey);
275 }
276 return resolver;
277 }
278
279 /**
280 * @param visited
281 * @param destinationKey
282 * @param visitedByKey
283 * @return
284 */
285 private boolean isPlannedBackToDestination(Visited visited,
286 TermResolverKey destinationKey,
287 Map<TermResolverKey, Visited> visitedByKey) {
288 boolean plannedToDestination = false;
289 if (visited.isFullyPlanned()) {
290 LOG.debug("Leaf! this resolver's prereqs are all avialable.");
291 // no traversing further yet, instead we need to check how far up the tree is fully planned out
292 // step backwards toward the root of the tree and see if we're good all the way to our objective.
293 // if a node fully planned, move up the tree (towards the root) to see if its parent is fully planned, and so on.
294
295 if (visited.getPathTo().size() > 0) {
296 // reverse the path to
297 List<TermResolverKey> reversePathTo = new ArrayList<TermResolverKey>(visited.getPathTo());
298 Collections.reverse(reversePathTo);
299
300 // we use this to propagate resolutions up the tree
301 Visited previousAncestor = visited;
302
303 for (TermResolverKey ancestorKey : reversePathTo) {
304
305 Visited ancestorVisited = visitedByKey.get(ancestorKey);
306 ancestorVisited.addPlannedPrereq(previousAncestor.getResolverKey());
307
308 LOG.debug("checking ancestor " + ancestorKey);
309
310 if (ancestorVisited.isFullyPlanned() && ancestorKey.equals(destinationKey)) {
311 // Woot! Job's done!
312 plannedToDestination = true;
313 break;
314 } else if (!ancestorVisited.isFullyPlanned()) { // if the ancestor isn't fully planned, we're done
315 LOG.debug("Still have planning to do.");
316 break;
317 }
318 // update previousAncestor reference for next iteration
319 previousAncestor = ancestorVisited;
320 }
321 } else {
322 // we're done already! do a jig?
323 LOG.debug("Trivial plan.");
324 plannedToDestination = true;
325 }
326 }
327 return plannedToDestination;
328 }
329
330 /**
331 *
332 * @param visited
333 * @param visitedByKey
334 * @param plan
335 */
336 private void assembleLinearResolutionPlan(Visited visited, Map<TermResolverKey, Visited> visitedByKey, List<TermResolverKey> plan) {
337 // DFS
338 for (TermResolverKey prereqResolverKey : visited.getPrereqResolvers()) {
339 Visited prereqVisited = visitedByKey.get(prereqResolverKey);
340 assembleLinearResolutionPlan(prereqVisited, visitedByKey, plan);
341 plan.add(prereqResolverKey);
342 }
343 }
344
345 /**
346 * Create our dummy destination resolver
347 * @param termName
348 */
349 private TermResolver<? extends Object> createDestination(final String termName) {
350 TermResolver<?> destination = new TermResolver<Object>() {
351 final String dest = "termResolutionEngineDestination";
352 @Override
353 public int getCost() {
354 return 0;
355 }
356 @Override
357 public String getOutput() {
358 return dest;
359 }
360 @Override
361 public Set<String> getPrerequisites() {
362 return Collections.<String>singleton(termName);
363 }
364 @Override
365 public Set<String> getParameterNames() {
366 return Collections.emptySet();
367 }
368 @Override
369 public Object resolve(Map<String, Object> resolvedPrereqs, Map<String, String> parameters) throws TermResolutionException {
370 return null;
371 }
372 };
373 return destination;
374 }
375
376 private static class ToVisit implements Comparable<ToVisit> {
377
378 private final int precost;
379 private final int addcost;
380 private final TermResolverKey resolverKey;
381
382 // the parent key is not being used for comparison purposes currently
383 private final TermResolverKey parentKey;
384
385 /**
386 * @param precost
387 * @param resolver
388 */
389 public ToVisit(int precost, TermResolver resolver, TermResolver parent) {
390 super();
391 this.precost = precost;
392 this.addcost = resolver.getCost();
393 this.resolverKey = new TermResolverKey(resolver);
394
395 if (parent != null) {
396 this.parentKey = new TermResolverKey(parent);
397 } else {
398 this.parentKey = null;
399 }
400 }
401
402 /**
403 * Get the precost plus the addcost
404 * @return in precost plus addcost
405 */
406 public int getCost() {
407 return precost + addcost;
408 }
409
410 @Override
411 public boolean equals(Object obj) {
412 if (this == obj) return true;
413 if (obj == null) return false;
414 if (getClass() != obj.getClass())
415 return false;
416 ToVisit other = (ToVisit)obj;
417 return this.compareTo(other) == 0;
418 }
419
420 /* (non-Javadoc)
421 * @see java.lang.Object#hashCode()
422 */
423 @Override
424 public int hashCode() {
425 final int prime = 31;
426 int result = 1;
427 result = prime * result + getCost();
428 result = prime * result + ((resolverKey == null) ? 0 : resolverKey.hashCode());
429 return result;
430 }
431
432 /**
433 * {@inheritDoc Comparable}
434 */
435 @Override
436 public int compareTo(ToVisit o) {
437 if (o == null) return 1;
438 if (getCost() > o.getCost()) return 1;
439 if (getCost() < o.getCost()) return -1;
440 return resolverKey.compareTo(o.resolverKey);
441 }
442
443 /**
444 * Return the {@link TermResolverKey}
445 * @return {@link TermResolverKey}
446 */
447 public TermResolverKey getTermResolverKey() {
448 return resolverKey;
449 }
450
451 /**
452 * Return the Parent {@link TermResolverKey}
453 * @return the Parent {@link TermResolverKey}
454 */
455 public TermResolverKey getParentKey() {
456 return parentKey;
457 }
458
459 @Override
460 public String toString() {
461 return getClass().getSimpleName()+"("+getTermResolverKey()+")";
462 }
463 }
464
465 protected static class TermResolverKey implements Comparable<TermResolverKey> {
466 private final List<String> data;
467 private final String [] params;
468
469 // just used for toArray call
470 private static final String[] TERM_SPEC_TYPER = new String[0];
471 private static final String[] STRING_TYPER = new String[0];
472
473 public TermResolverKey(TermResolver resolver) {
474 this(resolver.getOutput(), resolver.getParameterNames(), resolver.getPrerequisites());
475 }
476
477 private TermResolverKey(String dest, Set<String> paramSet, Set<String> prereqs) {
478 if (dest == null) throw new IllegalArgumentException("dest parameter must not be null");
479 data = new ArrayList<String>(1 + ((prereqs == null) ? 0 : prereqs.size())); // size ArrayList perfectly
480 data.add(dest);
481 if (!CollectionUtils.isEmpty(paramSet)) {
482 params = paramSet.toArray(STRING_TYPER);
483 Arrays.sort(params);
484 } else {
485 params = STRING_TYPER; // just assigning a handy zero length String array
486 }
487 if (prereqs != null) {
488 // this is painful, but to be able to compare we need a defined order
489 String [] prereqsArray = prereqs.toArray(TERM_SPEC_TYPER);
490 Arrays.sort(prereqsArray);
491 for (String prereq : prereqsArray) {
492 data.add(prereq);
493 }
494 }
495 }
496
497 public String getOutput() {
498 return data.get(0);
499 }
500
501 @Override
502 public int compareTo(TermResolverKey o) {
503 if (o == null) return 1;
504
505 Iterator<String> mDataIter = data.iterator();
506 Iterator<String> oDataIter = o.data.iterator();
507
508 while (mDataIter.hasNext() && oDataIter.hasNext()) {
509 int itemCompareResult = mDataIter.next().compareTo(oDataIter.next());
510 if (itemCompareResult != 0) return itemCompareResult;
511 }
512
513 if (mDataIter.hasNext()) return 1;
514 if (oDataIter.hasNext()) return -1;
515
516 return 0;
517 }
518
519 /* (non-Javadoc)
520 * @see java.lang.Object#hashCode()
521 */
522 @Override
523 public int hashCode() {
524 return data.hashCode();
525 }
526
527 /* (non-Javadoc)
528 * @see java.lang.Object#equals(java.lang.Object)
529 */
530 @Override
531 public boolean equals(Object obj) {
532 if (this == obj)
533 return true;
534 if (obj == null)
535 return false;
536 if (getClass() != obj.getClass())
537 return false;
538 TermResolverKey other = (TermResolverKey) obj;
539 return this.compareTo(other) == 0;
540 }
541
542 @Override
543 public String toString() {
544 StringBuilder sb = new StringBuilder();
545 sb.append(getClass().getSimpleName());
546 sb.append("(");
547 Iterator<String> iter = data.iterator();
548 sb.append(iter.next().toString());
549 if (params.length != 0) {
550 sb.append("+");
551 ArrayUtils.toString(params);
552 }
553
554 if (iter.hasNext()) sb.append(" <- ");
555 boolean first = true;
556 while (iter.hasNext()) {
557 if (first) first = false;
558 else sb.append(", ");
559 sb.append(iter.next().toString());
560 }
561
562
563 return sb.toString();
564 }
565 }
566
567
568 private static class Visited {
569 private TermResolverKey resolverKey;
570 private List<TermResolverKey> pathTo;
571 private Set<String> remainingPrereqs;
572 private Map<String, TermResolverKey> prereqResolvers;
573 private int cost;
574
575 /**
576 * @param resolverKey
577 * @param pathTo
578 * @param prereqs
579 * @param cost
580 */
581 public Visited(TermResolverKey resolverKey, List<TermResolverKey> pathTo, Set<String> prereqs, int cost) {
582 super();
583 this.resolverKey = resolverKey;
584 this.pathTo = pathTo;
585 this.remainingPrereqs = new HashSet<String>(prereqs);
586 this.prereqResolvers = new HashMap<String, TermResolverKey>();
587 this.cost = cost;
588 }
589
590 /**
591 * @return the path from the goal node down to this resolver
592 */
593 public List<TermResolverKey> getPathTo() {
594 return pathTo;
595 }
596
597 public TermResolverKey getResolverKey() {
598 return resolverKey;
599 }
600
601 public Collection<TermResolverKey> getPrereqResolvers() {
602 return prereqResolvers.values();
603 }
604
605 /**
606 * @return true if resolution of all the prerequisites has been planned
607 */
608 public boolean isFullyPlanned() {
609 return remainingPrereqs.isEmpty();
610 }
611
612 public int getCost() {
613 return cost;
614 }
615
616 public void addPlannedPrereq(TermResolverKey termResolverKey) {
617 remainingPrereqs.remove(termResolverKey.getOutput());
618 prereqResolvers.put(termResolverKey.getOutput(), termResolverKey);
619 }
620
621 public void addPlannedPrereq(String termName) {
622 remainingPrereqs.remove(termName);
623 }
624 }
625
626 private static class InvalidResolutionPathException extends Exception {
627 private static final long serialVersionUID = 1L;
628
629 public InvalidResolutionPathException() {
630 }
631 }
632
633 }
634
635