View Javadoc

1   /*
2    * Grapht, an open source dependency injector.
3    * Copyright 2014-2015 various contributors (see CONTRIBUTORS.txt)
4    * Copyright 2010-2014 Regents of the University of Minnesota
5    *
6    * This program is free software; you can redistribute it and/or modify
7    * it under the terms of the GNU Lesser General Public License as
8    * published by the Free Software Foundation; either version 2.1 of the
9    * License, or (at your option) any later version.
10   *
11   * This program is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13   * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14   * details.
15   *
16   * You should have received a copy of the GNU General Public License along with
17   * this program; if not, write to the Free Software Foundation, Inc., 51
18   * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19   */
20  package org.grouplens.grapht.solver;
21  
22  import com.google.common.base.Predicate;
23  import com.google.common.base.Predicates;
24  import com.google.common.collect.*;
25  import org.grouplens.grapht.CachePolicy;
26  import org.grouplens.grapht.Component;
27  import org.grouplens.grapht.Dependency;
28  import org.grouplens.grapht.annotation.AnnotationBuilder;
29  import org.grouplens.grapht.context.ContextElements;
30  import org.grouplens.grapht.context.ContextMatcher;
31  import org.grouplens.grapht.context.ContextPattern;
32  import org.grouplens.grapht.graph.DAGEdge;
33  import org.grouplens.grapht.graph.DAGNode;
34  import org.grouplens.grapht.reflect.*;
35  import org.junit.Assert;
36  import org.junit.Test;
37  
38  import javax.inject.Qualifier;
39  import java.lang.annotation.Retention;
40  import java.lang.annotation.RetentionPolicy;
41  import java.util.ArrayList;
42  import java.util.Arrays;
43  import java.util.HashSet;
44  import java.util.Set;
45  
46  import static org.hamcrest.Matchers.equalTo;
47  import static org.hamcrest.Matchers.hasSize;
48  import static org.junit.Assert.assertThat;
49  
50  public class DependencySolverTest {
51      private DependencySolver createSolver(ListMultimap<ContextMatcher, BindRule> rules) {
52          return DependencySolver.newBuilder()
53                  .addBindingFunction(new RuleBasedBindingFunction(rules))
54                  .setDefaultPolicy(CachePolicy.NO_PREFERENCE)
55                  .setMaxDepth(100)
56                  .build();
57      }
58      
59      // bypass synthetic root and return node that resolves the desire 
60      private DAGNode<Component, Dependency> getRoot(DependencySolver r, Desire d) {
61          return r.getGraph().getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d)).getTail();
62      }
63      
64      @Test
65      public void testCachePolicySuccess() throws Exception {
66          // Test that satisfactions formed with different cache policies 
67          // correctly restrict merging of nodes
68          Satisfaction sa = new MockSatisfaction(A.class, new ArrayList<Desire>());
69          Desire da = new MockDesire();
70          Satisfaction sb = new MockSatisfaction(B.class, Arrays.asList(da));
71          
72          Desire ra = new MockDesire(sa);
73          Desire rb = new MockDesire(sb);
74          
75          ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
76          final Class<?> type = B.class;
77          final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
78          bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
79                       new MockBindRule(da, ra).setCachePolicy(CachePolicy.MEMOIZE));
80          bindings.put(ContextPattern.any(),
81                       new MockBindRule(da, ra).setCachePolicy(CachePolicy.NEW_INSTANCE));
82          
83          DependencySolver r = createSolver(bindings.build());
84          r.resolve(rb);
85          r.resolve(da); // should create a single extra sa node with different cache policy
86  
87          assertThat(r.getGraph().getReachableNodes(),
88                     hasSize(3 + 1));
89  
90          DAGNode<Component, Dependency> bnode = getRoot(r, rb);
91          Assert.assertEquals(CachePolicy.NO_PREFERENCE, bnode.getLabel().getCachePolicy());
92          
93          DAGNode<Component, Dependency> adepnode = getNode(bnode, sa, da);
94          Assert.assertNotNull(adepnode);
95          Assert.assertEquals(CachePolicy.MEMOIZE, adepnode.getLabel().getCachePolicy());
96          
97          DAGNode<Component, Dependency> anode = getRoot(r, da);
98          Assert.assertNotSame(adepnode, anode);
99          Assert.assertEquals(CachePolicy.NEW_INSTANCE, anode.getLabel().getCachePolicy());
100     }
101     
102     @Test
103     public void testNoDependenciesSuccess() throws Exception {
104         // Test resolving a satisfaction that has no dependencies and is already satisfiable
105         Satisfaction sat = new MockSatisfaction(A.class, new ArrayList<Desire>());
106         Desire desire = new MockDesire(sat);
107 
108         DependencySolver r = createSolver(ArrayListMultimap.<ContextMatcher, BindRule>create());
109         r.resolve(desire);
110         assertThat(r.getGraph().getReachableNodes(), hasSize(2));
111 
112         DAGNode<Component, Dependency> node = getRoot(r, desire);
113         Assert.assertEquals(sat, node.getLabel().getSatisfaction());
114         Assert.assertTrue(node.getOutgoingEdges().isEmpty());
115         Assert.assertTrue(r.getGraph().getReachableNodes().contains(node));
116     }
117 
118     @Test
119     public void testSingleDependencySuccess() throws Exception {
120         // Test resolving a satisfaction with a single dependency that is already satisfiable
121         Satisfaction dep = new MockSatisfaction(B.class);
122         Desire depDesire = new MockDesire(dep);
123         Satisfaction rootSat = new MockSatisfaction(A.class, Arrays.asList(depDesire));
124         Desire rootDesire = new MockDesire(rootSat);
125         
126         DependencySolver r = createSolver(ArrayListMultimap.<ContextMatcher, BindRule>create());
127         r.resolve(rootDesire);
128         
129         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
130         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
131         Assert.assertEquals(rootSat, rootNode.getLabel().getSatisfaction());
132         Assert.assertEquals(1, rootNode.getOutgoingEdges().size());
133         Assert.assertEquals(dep, rootNode.getOutgoingEdges().iterator().next().getTail().getLabel().getSatisfaction());
134     }
135 
136     @Test
137     public void testSingleDependencyChainedDesiresSuccess() throws Exception {
138         // Test resolving a satisfaction with a single dependency through multiple desires/bind rules
139         Satisfaction dep = new MockSatisfaction(B.class);
140         Desire d1 = new MockDesire();
141         Desire d2 = new MockDesire();
142         Desire d3 = new MockDesire(dep);
143         Satisfaction root = new MockSatisfaction(A.class, Arrays.asList(d1));
144         Desire rootDesire = new MockDesire(root);
145         
146         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
147         bindings.putAll(ContextPattern.any(),
148                         new MockBindRule(d1, d2),
149                         new MockBindRule(d2, d3));
150         DependencySolver r = createSolver(bindings.build());
151         r.resolve(rootDesire);
152         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
153         
154         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
155         Assert.assertEquals(root, rootNode.getLabel().getSatisfaction());
156         Assert.assertEquals(1, rootNode.getOutgoingEdges().size());
157         Assert.assertEquals(dep, rootNode.getOutgoingEdges().iterator().next().getTail().getLabel().getSatisfaction());
158     }
159 
160     @Test
161     public void testMultipleSatisfiableDesiresSuccess() throws Exception {
162         // Test resolving a single satisfaction, where the chain of bind rules
163         // contains multiple satisfiable desires, and the deepest is selected
164         Satisfaction dep = new MockSatisfaction(B.class);
165         Satisfaction s1 = new MockSatisfaction(C.class);
166         Satisfaction s2 = new MockSatisfaction(Ap.class);
167         Desire d1 = new MockDesire(s1);
168         Desire d2 = new MockDesire(s2);
169         Desire d3 = new MockDesire(dep);
170         Satisfaction root = new MockSatisfaction(A.class, Arrays.asList(d1));
171         
172         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
173         bindings.putAll(ContextPattern.any(),
174                         new MockBindRule(d1, d2),
175                         new MockBindRule(d2, d3));
176 
177         Desire rootDesire = new MockDesire(root);
178         DependencySolver r = createSolver(bindings.build());
179         r.resolve(rootDesire);
180         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
181 
182         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
183         Assert.assertEquals(root, rootNode.getLabel().getSatisfaction());
184         Assert.assertEquals(1, rootNode.getOutgoingEdges().size());
185         Assert.assertEquals(dep, rootNode.getOutgoingEdges().iterator().next().getTail().getLabel().getSatisfaction());
186     }
187     
188     @Test
189     public void testParentReferencesGrandChildSuccess() throws Exception {
190         // Test that when a desire references a child that child's desire (2 desires total),
191         // the parent desire is resolved properly (note that a solution by walking
192         // up leaf nodes doesn't work in this case since it will encounter the parent
193         // and child at the same time).
194         Desire d1 = new MockDesire();
195         Desire d2 = new MockDesire();
196         
197         Satisfaction s3 = new MockSatisfaction(C.class); // leaf/grandchild
198         Satisfaction s2 = new MockSatisfaction(B.class, Arrays.asList(d2)); // child
199         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1, d2));
200         
201         Desire b1 = new MockDesire(s2);
202         Desire b2 = new MockDesire(s3);
203         
204         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
205         bindings.putAll(ContextPattern.any(),
206                         new MockBindRule(d1, b1),
207                         new MockBindRule(d2, b2));
208         
209         Desire rootDesire = new MockDesire(s1);
210         DependencySolver r = createSolver(bindings.build());
211         r.resolve(rootDesire);
212         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
213         
214         Assert.assertEquals(3 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
215         Assert.assertEquals(s1, rootNode.getLabel().getSatisfaction());
216         
217         DAGNode<Component, Dependency> n1 =
218                 getNode(r.getGraph(), Component.create(s1, CachePolicy.NO_PREFERENCE));
219         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(s2, CachePolicy.NO_PREFERENCE));
220         DAGNode<Component, Dependency> n3 = getNode(r.getGraph(), Component.create(s3, CachePolicy.NO_PREFERENCE));
221 
222         assertThat(Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))),
223                    hasSize(1));
224         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
225         
226         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
227         Assert.assertEquals(d2, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
228         
229         Assert.assertEquals(1, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
230         Assert.assertEquals(d2, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
231     }
232     
233     @Test
234     public void testContextRoleMatchSuccess() throws Exception {
235         // Test that qualifiers are properly remembered in the context
236         // - note that this is different than having a qualifier-binding, that is
237         //   part of the bind rule's match implementation
238         Qual qualifier1 = AnnotationBuilder.of(Qual.class).setValue(0).build();
239         Qual qualifier2 = AnnotationBuilder.of(Qual.class).setValue(1).build();
240         
241         Desire dr1 = new MockDesire(null, qualifier1);
242         Desire dr2 = new MockDesire(null, qualifier2);
243         Desire d3 = new MockDesire();
244         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(dr1, dr2));
245         Satisfaction r2 = new MockSatisfaction(B.class, Arrays.asList(d3));
246         Satisfaction r3 = new MockSatisfaction(C.class, Arrays.asList(d3));
247         
248         Satisfaction r4 = new MockSatisfaction(Cp.class);
249         Satisfaction or4 = new MockSatisfaction(Bp.class);
250         
251         Desire br1 = new MockDesire(r2);
252         Desire br2 = new MockDesire(r3);
253         Desire b3 = new MockDesire(r4);
254         Desire ob3 = new MockDesire(or4);
255         
256         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
257         bindings.putAll(ContextPattern.any(),
258                         new MockBindRule(dr1, br1),
259                         new MockBindRule(dr2, br2));
260         final Class<?> type = Object.class;
261         final MockQualifierMatcher qualifier = MockQualifierMatcher.match(qualifier1);
262         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
263                      new MockBindRule(d3, b3));
264         final Class<?> type1 = Object.class;
265         final MockQualifierMatcher qualifier3 = MockQualifierMatcher.match(qualifier2);
266         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type1, qualifier3)),
267                      new MockBindRule(d3, ob3));
268         
269         Desire rootDesire = new MockDesire(r1);
270         DependencySolver r = createSolver(bindings.build());
271         r.resolve(rootDesire);
272         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
273         
274         Assert.assertEquals(5 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
275         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(r1, CachePolicy.NO_PREFERENCE));
276         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(r2, CachePolicy.NO_PREFERENCE));
277         DAGNode<Component, Dependency> n3 = getNode(r.getGraph(), Component.create(r3, CachePolicy.NO_PREFERENCE));
278         DAGNode<Component, Dependency> n4 = getNode(r.getGraph(), Component.create(r4, CachePolicy.NO_PREFERENCE));
279         DAGNode<Component, Dependency> on4 = getNode(r.getGraph(), Component.create(or4, CachePolicy.NO_PREFERENCE));
280 
281         Assert.assertEquals(n1, rootNode);
282         Assert.assertEquals(2, n1.getOutgoingEdges().size());
283         
284         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
285         Assert.assertEquals(dr1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
286         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
287         Assert.assertEquals(dr2, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
288 
289         Assert.assertEquals(1, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n4))).size());
290         Assert.assertEquals(d3, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n4))).iterator().next().getLabel().getInitialDesire());
291         Assert.assertEquals(1, Sets.filter(n3.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(on4))).size());
292         Assert.assertEquals(d3, Sets.filter(n3.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(on4))).iterator().next().getLabel().getInitialDesire());
293     }
294     
295     @Test
296     public void testSimpleContextMatchSuccess() throws Exception {
297         // Test that a context-specific bind rule is included and selected
298         Desire d1 = new MockDesire();
299         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(d1));
300         Satisfaction r2 = new MockSatisfaction(B.class);
301         Satisfaction or2 = new MockSatisfaction(Bp.class);
302         
303         Desire b1 = new MockDesire(r2);
304         Desire ob1 = new MockDesire(or2);
305 
306         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
307         bindings.put(ContextPattern.any(),
308                      new MockBindRule(d1, b1));
309         final Class<?> type = A.class;
310         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
311         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
312                      new MockBindRule(d1, ob1));
313 
314         Desire rootDesire = new MockDesire(r1);
315         DependencySolver r = createSolver(bindings.build());
316         r.resolve(rootDesire);
317         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
318 
319         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
320         Assert.assertEquals(r1, rootNode.getLabel().getSatisfaction());
321         Assert.assertEquals(1, rootNode.getOutgoingEdges().size());
322         Assert.assertEquals(or2, rootNode.getOutgoingEdges().iterator().next().getTail().getLabel().getSatisfaction());
323     }
324     
325     @Test
326     public void testContextClosenessMatchSuccess() throws Exception {
327         // Test that between two context bind rules, the closest is chosen
328         Desire d1 = new MockDesire();
329         Desire d2 = new MockDesire();
330         
331         Satisfaction or3 = new MockSatisfaction(Cp.class);
332         Satisfaction r3 = new MockSatisfaction(C.class);
333         Satisfaction r2 = new MockSatisfaction(B.class, Arrays.asList(d2));
334         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(d1));
335         
336         Desire b1 = new MockDesire(r2);
337         Desire b2 = new MockDesire(r3);
338         Desire ob2 = new MockDesire(or3);
339         
340         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
341         bindings.put(ContextPattern.any(),
342                      new MockBindRule(d1, b1));
343         // for this test, CycleA is farther than B so b2 should be selected over ob2
344         final Class<?> type = A.class;
345         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
346         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
347                      new MockBindRule(d2, ob2));
348         final Class<?> type1 = B.class;
349         final MockQualifierMatcher qualifier1 = MockQualifierMatcher.any();
350         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type1, qualifier1)),
351                      new MockBindRule(d2, b2));
352         
353         Desire rootDesire = new MockDesire(r1);
354         DependencySolver r = createSolver(bindings.build());
355         r.resolve(rootDesire);
356         
357         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(r1, CachePolicy.NO_PREFERENCE));
358         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(r2, CachePolicy.NO_PREFERENCE));
359         DAGNode<Component, Dependency> n3 = getNode(r.getGraph(), Component.create(r3, CachePolicy.NO_PREFERENCE));
360         DAGNode<Component, Dependency> on3 = getNode(r.getGraph(), Component.create(or3, CachePolicy.NO_PREFERENCE));
361 
362         Assert.assertEquals(3 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
363         Assert.assertNotNull(n1);
364         Assert.assertNotNull(n2);
365         Assert.assertNotNull(n3);
366         Assert.assertNull(on3);
367         
368         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
369         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
370 
371         Assert.assertEquals(1, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
372         Assert.assertEquals(d2, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
373     }
374 
375     @Test
376     public void testContextLengthMatchSuccess() throws Exception {
377         // Test that between two context bind rules, the longest is chosen
378         // if their closeness is equal
379         Desire d1 = new MockDesire();
380         Desire d2 = new MockDesire();
381         
382         Satisfaction or3 = new MockSatisfaction(Cp.class);
383         Satisfaction r3 = new MockSatisfaction(C.class);
384         Satisfaction r2 = new MockSatisfaction(B.class, Arrays.asList(d2));
385         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(d1));
386         
387         Desire b1 = new MockDesire(r2);
388         Desire b2 = new MockDesire(r3);
389         Desire ob2 = new MockDesire(or3);
390         
391         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
392         bindings.put(ContextPattern.any(),
393                      new MockBindRule(d1, b1));
394         // for this test, AB is longer than CycleA so b2 is selected over ob2
395         final Class<?> type = A.class;
396         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
397         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
398                      new MockBindRule(d2, ob2));
399         final Class<?> type1 = A.class;
400         final MockQualifierMatcher qualifier1 = MockQualifierMatcher.any();
401         final Class<?> type2 = B.class;
402         final MockQualifierMatcher qualifier2 = MockQualifierMatcher.any();
403         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type1, qualifier1), ContextElements.matchType(type2, qualifier2)
404         ),
405                      new MockBindRule(d2, b2));
406         
407         Desire rootDesire = new MockDesire(r1);
408         DependencySolver r = createSolver(bindings.build());
409         r.resolve(rootDesire);
410         
411         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(r1, CachePolicy.NO_PREFERENCE));
412         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(r2, CachePolicy.NO_PREFERENCE));
413         DAGNode<Component, Dependency> n3 = getNode(r.getGraph(), Component.create(r3, CachePolicy.NO_PREFERENCE));
414         DAGNode<Component, Dependency> on3 = getNode(r.getGraph(), Component.create(or3, CachePolicy.NO_PREFERENCE));
415 
416         Assert.assertEquals(3 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
417         Assert.assertNotNull(n1);
418         Assert.assertNotNull(n2);
419         Assert.assertNotNull(n3);
420         Assert.assertNull(on3);
421         
422         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
423         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
424 
425         Assert.assertEquals(1, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
426         Assert.assertEquals(d2, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
427     }
428     
429     @Test
430     public void testIgnoreDefaultContextBindingSuccess() throws Exception {
431         // Test that a specific context binding is preferred over a valid default
432         // context binding for the same type. This can be inferred from the above
433         // tests but it is nice to ensure it works as expected
434         Desire d1 = new MockDesire();
435         
436         Satisfaction or2 = new MockSatisfaction(Bp.class);
437         Satisfaction r2 = new MockSatisfaction(B.class);
438         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(d1));
439         
440         Desire b1 = new MockDesire(r2);
441         Desire ob1 = new MockDesire(or2);
442         
443         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
444         // for this test, CycleA is more specific than default, so b2 is selected
445         bindings.put(ContextPattern.any(),
446                      new MockBindRule(d1, ob1));
447         final Class<?> type = A.class;
448         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
449         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
450                      new MockBindRule(d1, b1));
451         
452         Desire rootDesire = new MockDesire(r1);
453         DependencySolver r = createSolver(bindings.build());
454         r.resolve(rootDesire);
455         
456         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(r1, CachePolicy.NO_PREFERENCE));
457         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(r2, CachePolicy.NO_PREFERENCE));
458         DAGNode<Component, Dependency> on2 = getNode(r.getGraph(), Component.create(or2, CachePolicy.NO_PREFERENCE));
459 
460         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
461         Assert.assertNotNull(n1);
462         Assert.assertNotNull(n2);
463         Assert.assertNull(on2);
464         
465         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
466         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
467     }
468 
469     @Test
470     public void testMultipleDependenciesSuccess() throws Exception {
471         // Test that a satisfaction with multiple dependencies is correctly resolved
472         Desire d1 = new MockDesire();
473         Desire d2 = new MockDesire();
474         Desire d3 = new MockDesire();
475         
476         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(d1, d2, d3));
477         Satisfaction sd1 = new MockSatisfaction(B.class);
478         Satisfaction sd2 = new MockSatisfaction(C.class);
479         Satisfaction sd3 = new MockSatisfaction(Cp.class);
480         
481         Desire b1 = new MockDesire(sd1);
482         Desire b2 = new MockDesire(sd2);
483         Desire b3 = new MockDesire(sd3);
484         
485         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
486         bindings.putAll(ContextPattern.any(),
487                         new MockBindRule(d1, b1),
488                         new MockBindRule(d2, b2),
489                         new MockBindRule(d3, b3));
490         
491         Desire rootDesire = new MockDesire(r1);
492         DependencySolver r = createSolver(bindings.build());
493         r.resolve(rootDesire);
494         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
495         
496         Assert.assertEquals(4 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
497         Assert.assertEquals(r1, rootNode.getLabel().getSatisfaction());
498         Assert.assertEquals(3, rootNode.getOutgoingEdges().size());
499         
500         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(sd1, CachePolicy.NO_PREFERENCE));
501         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(sd2, CachePolicy.NO_PREFERENCE));
502         DAGNode<Component, Dependency> n3 = getNode(r.getGraph(), Component.create(sd3, CachePolicy.NO_PREFERENCE));
503         
504         Assert.assertEquals(1, Sets.filter(rootNode.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n1))).size());
505         Assert.assertEquals(d1, Sets.filter(rootNode.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n1))).iterator().next().getLabel().getInitialDesire());
506         
507         Assert.assertEquals(1, Sets.filter(rootNode.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
508         Assert.assertEquals(d2, Sets.filter(rootNode.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
509         
510         Assert.assertEquals(1, Sets.filter(rootNode.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
511         Assert.assertEquals(d3, Sets.filter(rootNode.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
512     }
513 
514     @Test
515     public void testMultipleRootsSharedDependencySuccess() throws Exception {
516         // Test multiple root desires that resolve to nodes that share
517         // a dependency, and verify that the resolved dependency is the same DAGNode<Component, DesireChain>
518         Desire d1 = new MockDesire();
519         Desire d2 = new MockDesire();
520         Desire d3 = new MockDesire();
521         
522         Satisfaction r1 = new MockSatisfaction(A.class, Arrays.asList(d1, d2, d3));
523         Satisfaction sd1 = new MockSatisfaction(B.class);
524         
525         Desire b1 = new MockDesire(sd1);
526         Desire b2 = new MockDesire(sd1);
527         Desire b3 = new MockDesire(sd1);
528 
529         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
530         bindings.putAll(ContextPattern.any(),
531                         new MockBindRule(d1, b1),
532                         new MockBindRule(d2, b2),
533                         new MockBindRule(d3, b3));
534         
535         Desire rootDesire = new MockDesire(r1);
536         DependencySolver r = createSolver(bindings.build());
537         r.resolve(rootDesire);
538         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
539         
540         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
541         Assert.assertEquals(r1, rootNode.getLabel().getSatisfaction());
542         Assert.assertEquals(3, rootNode.getOutgoingEdges().size());
543         
544         Set<Desire> edges = new HashSet<Desire>();
545         for (DAGEdge<Component, Dependency> e: rootNode.getOutgoingEdges()) {
546             Assert.assertEquals(sd1, e.getTail().getLabel().getSatisfaction());
547             edges.add(e.getLabel().getInitialDesire());
548         }
549         
550         Assert.assertTrue(edges.contains(d1));
551         Assert.assertTrue(edges.contains(d2));
552         Assert.assertTrue(edges.contains(d3));
553     }
554 
555     @Test
556     public void testChainedDependenciesSuccess() throws Exception {
557         // Test multiple levels of dependencies
558         Desire d1 = new MockDesire();
559         Desire d2 = new MockDesire();
560         
561         Satisfaction s3 = new MockSatisfaction(C.class);
562         Satisfaction s2 = new MockSatisfaction(B.class, Arrays.asList(d2));
563         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
564         
565         Desire b1 = new MockDesire(s2);
566         Desire b2 = new MockDesire(s3);
567         
568         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
569         bindings.putAll(ContextPattern.any(),
570                         new MockBindRule(d1, b1),
571                         new MockBindRule(d2, b2));
572         
573         Desire rootDesire = new MockDesire(s1);
574         DependencySolver r = createSolver(bindings.build());
575         r.resolve(rootDesire);
576         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
577         
578         Assert.assertEquals(3 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
579         Assert.assertEquals(s1, rootNode.getLabel().getSatisfaction());
580         
581         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(s1, CachePolicy.NO_PREFERENCE));
582         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(s2, CachePolicy.NO_PREFERENCE));
583         DAGNode<Component, Dependency> n3 = getNode(r.getGraph(), Component.create(s3, CachePolicy.NO_PREFERENCE));
584         
585         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
586         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
587         
588         Assert.assertEquals(1, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).size());
589         Assert.assertEquals(d2, Sets.filter(n2.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n3))).iterator().next().getLabel().getInitialDesire());
590     }
591 
592     @Test
593     public void testComplexDependenciesSuccess() throws Exception {
594         // Test a contrived example of a reasonably complex dependency scenario
595         // that tests contexts, qualifiers, shared, and split nodes
596         Qual r1 = AnnotationBuilder.of(Qual.class).setValue(0).build();
597         Qual r2 = AnnotationBuilder.of(Qual.class).setValue(1).build();
598         Qual r3 = AnnotationBuilder.of(Qual.class).setValue(2).build();
599         Qual r4 = AnnotationBuilder.of(Qual.class).setValue(3).build();
600         
601         Desire d1 = new MockDesire(null, r1);
602         Desire d2 = new MockDesire(null, r2);
603         Desire d3 = new MockDesire(null, r3);
604         Desire d4 = new MockDesire(null, r4);
605         Desire d5 = new MockDesire();
606         Desire d6 = new MockDesire();
607         Desire d7 = new MockDesire();
608         
609         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1, d2));
610         Satisfaction s2 = new MockSatisfaction(B.class, Arrays.asList(d3, d4));
611         Satisfaction s3 = new MockSatisfaction(C.class, Arrays.asList(d5));
612         Satisfaction s4 = new MockSatisfaction(D.class, Arrays.asList(d6));
613         Satisfaction s5 = new MockSatisfaction(E.class, Arrays.asList(d7));
614         Satisfaction s6 = new MockSatisfaction(F.class);
615         Satisfaction s7 = new MockSatisfaction(G.class);
616         
617         Desire b1 = new MockDesire(s2);
618         Desire b2 = new MockDesire(s3);
619         Desire b3 = new MockDesire(s4);
620         Desire b4 = new MockDesire(s5);
621         Desire b5 = new MockDesire(s6);
622         Desire b6 = new MockDesire(s7);
623         
624         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
625         bindings.putAll(ContextPattern.any(),
626                         new MockBindRule(d1, b1), // d1 -> s2
627                         new MockBindRule(d2, b1), // d2 -> s2
628                         new MockBindRule(d3, b3), // d3 -> s4
629                         new MockBindRule(d4, b3), // d4 -> s4
630                         new MockBindRule(d5, b4), // d5 -> s5
631                         new MockBindRule(d6, b4), // d6 -> s5
632                         new MockBindRule(d7, b5)); // d7 -> s6
633         final Class<?> type = B.class;
634         final MockQualifierMatcher qualifier = MockQualifierMatcher.match(r1);
635         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
636                      new MockBindRule(d3, b2)); // r1s1:d3 -> s3
637         final Class<?> type1 = B.class;
638         final MockQualifierMatcher qualifier1 = MockQualifierMatcher.match(r2);
639         final Class<?> type2 = D.class;
640         final MockQualifierMatcher qualifier2 = MockQualifierMatcher.match(r4);
641         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type1, qualifier1),
642                                                 ContextElements.matchType(type2, qualifier2)
643         ),
644                      new MockBindRule(d7, b6)); // r2s1,r4s2:d7 -> s7
645         
646         Desire rootDesire = new MockDesire(s1);
647         DependencySolver r = createSolver(bindings.build());
648         r.resolve(rootDesire);
649         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
650         
651         // there are 10 nodes, s2, s4 and s5 are duplicated
652         Assert.assertEquals(10 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
653         
654         // grab all of the nodes in the graph
655         DAGNode<Component, Dependency> n1 = rootNode;
656         DAGNode<Component, Dependency> n2 = getNode(n1, s2, d1);
657         DAGNode<Component, Dependency> on2 = getNode(n1, s2, d2);
658         DAGNode<Component, Dependency> n3 = getNode(n2, s3, d3);
659         DAGNode<Component, Dependency> n4 = getNode(n2, s4, d4);
660         DAGNode<Component, Dependency> on4 = getNode(on2, s4, d3); // should equal n4
661         DAGNode<Component, Dependency> oon4 = getNode(on2, s4, d4); // should not equal n4 and on4
662         DAGNode<Component, Dependency> n5 = getNode(n3, s5, d5);
663         DAGNode<Component, Dependency> on5 = getNode(on4, s5, d6); // should equal n5
664         DAGNode<Component, Dependency> oon5 = getNode(oon4, s5, d6); // should not equal n5 and on5
665         DAGNode<Component, Dependency> n6 = getNode(n5, s6, d7);
666         DAGNode<Component, Dependency> n7 = getNode(oon5, s7, d7);
667         
668         // make sure that node states are as expected, if they're not null then
669         // they match the satisfaction and desire in the query
670         Assert.assertTrue(n1 != null && n2 != null && n3 != null && n4 != null
671                           && n5 != null && n6 != null && n7 != null && on2 != null 
672                           && on4 != null && on5 != null && oon4 != null && oon5 != null);
673         Assert.assertNotSame(n2, on2);
674         Assert.assertSame(n4, on4);
675         Assert.assertSame(n5, on5);
676         Assert.assertNotSame(n4, oon4);
677         Assert.assertNotSame(n5, oon5);
678         
679         // make sure there aren't any extra edges
680         Assert.assertEquals(2, n1.getOutgoingEdges().size());
681         Assert.assertEquals(2, n2.getOutgoingEdges().size());
682         Assert.assertEquals(2, on2.getOutgoingEdges().size());
683         Assert.assertEquals(1, n3.getOutgoingEdges().size());
684         Assert.assertEquals(1, n4.getOutgoingEdges().size());
685         Assert.assertEquals(1, oon4.getOutgoingEdges().size());
686         Assert.assertEquals(1, n5.getOutgoingEdges().size());
687         Assert.assertEquals(1, oon5.getOutgoingEdges().size());
688         Assert.assertEquals(0, n6.getOutgoingEdges().size());
689         Assert.assertEquals(0, n7.getOutgoingEdges().size());
690         
691         // special case for root (since the graph adds a synthetic root)
692         Assert.assertEquals(1, r.getGraph().getIncomingEdges(n1).size());
693         assertThat(r.getGraph().getIncomingEdges(n1).iterator().next().getHead().getLabel(),
694                    equalTo(DependencySolver.ROOT_SATISFACTION));
695 
696         Assert.assertEquals(1, r.getGraph().getIncomingEdges(n2).size());
697         Assert.assertEquals(1, r.getGraph().getIncomingEdges(on2).size());
698         Assert.assertEquals(1, r.getGraph().getIncomingEdges(n3).size());
699         Assert.assertEquals(2, r.getGraph().getIncomingEdges(n4).size());
700         Assert.assertEquals(1, r.getGraph().getIncomingEdges(oon4).size());
701         Assert.assertEquals(2, r.getGraph().getIncomingEdges(n5).size());
702         Assert.assertEquals(1, r.getGraph().getIncomingEdges(oon5).size());
703         Assert.assertEquals(1, r.getGraph().getIncomingEdges(n6).size());
704         Assert.assertEquals(1, r.getGraph().getIncomingEdges(n7).size());
705     }
706     
707     @Test
708     public void testContextBreakingCycleSuccess() throws Exception {
709         // Test that a context that is activated after a certain number of
710         // cycles within a dependency can break out of the cycle and finish resolving
711         Desire d1 = new MockDesire();
712         Desire d2 = new MockDesire();
713         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
714         Satisfaction s2 = new MockSatisfaction(B.class, Arrays.asList(d2));
715         Satisfaction os2 = new MockSatisfaction(Bp.class);
716         
717         Desire b1 = new MockDesire(s2);
718         Desire ob1 = new MockDesire(os2);
719         Desire b2 = new MockDesire(s1);
720         
721         // configure bindings so that s1 and s2 cycle for a couple of iterations
722         // until the context s2/s2 is reached, then switches to os2
723         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
724         bindings.putAll(ContextPattern.any(),
725                         new MockBindRule(d1, b1),
726                         new MockBindRule(d2, b2));
727         final Class<?> type = B.class;
728         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
729         final Class<?> type1 = B.class;
730         final MockQualifierMatcher qualifier1 = MockQualifierMatcher.any();
731         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier),
732                                                 ContextElements.matchType(type1, qualifier1)
733         ),
734                      new MockBindRule(d1, ob1));
735         
736         Desire rootDesire = new MockDesire(s1);
737         DependencySolver r = createSolver(bindings.build());
738         r.resolve(rootDesire);
739         DAGNode<Component, Dependency> rootNode = getRoot(r, rootDesire);
740         
741         // the resulting graph should be s1->s2->s1->s2->s1->os2 = 6 nodes
742         Assert.assertEquals(6 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
743         Assert.assertEquals(s1, rootNode.getLabel().getSatisfaction());
744         
745         // edge s1->s2 by d1
746         Set<DAGEdge<Component, Dependency>> edges = rootNode.getOutgoingEdges();
747         Assert.assertEquals(1, edges.size());
748         DAGEdge<Component, Dependency> e1 = edges.iterator().next();
749         Assert.assertEquals(s2, e1.getTail().getLabel().getSatisfaction());
750         Assert.assertEquals(d1, e1.getLabel().getInitialDesire());
751         
752         // edge s2->s1 by d2
753         edges = e1.getTail().getOutgoingEdges();
754         Assert.assertEquals(1, edges.size());
755         DAGEdge<Component, Dependency> e2 = edges.iterator().next();
756         Assert.assertEquals(s1, e2.getTail().getLabel().getSatisfaction());
757         Assert.assertEquals(d2, e2.getLabel().getInitialDesire());
758         
759         // edge s1->s2 by d1
760         edges = e2.getTail().getOutgoingEdges();
761         Assert.assertEquals(1, edges.size());
762         DAGEdge<Component, Dependency> e3 = edges.iterator().next();
763         Assert.assertEquals(s2, e3.getTail().getLabel().getSatisfaction());
764         Assert.assertEquals(d1, e3.getLabel().getInitialDesire());
765         
766         // edge s2->s1 by d2
767         edges = e3.getTail().getOutgoingEdges();
768         Assert.assertEquals(1, edges.size());
769         DAGEdge<Component, Dependency> e4 = edges.iterator().next();
770         Assert.assertEquals(s1, e4.getTail().getLabel().getSatisfaction());
771         Assert.assertEquals(d2, e4.getLabel().getInitialDesire());
772         
773         // edge s1->os2 by d1
774         edges = e4.getTail().getOutgoingEdges();
775         Assert.assertEquals(1, edges.size());
776         DAGEdge<Component, Dependency> e5 = edges.iterator().next();
777         Assert.assertEquals(os2, e5.getTail().getLabel().getSatisfaction());
778         Assert.assertEquals(d1, e5.getLabel().getInitialDesire());
779         
780         Assert.assertTrue(e5.getTail().getOutgoingEdges().isEmpty());
781     }
782     
783     @Test
784     public void testTooManyChoicesFilteredByContextSuccess() throws Exception {
785         // Test when too many choices exist, but are limited in scope by contexts
786         // that do not apply, the resolving will succeed
787         Desire d1 = new MockDesire();
788         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
789         Satisfaction s2 = new MockSatisfaction(B.class);
790         Satisfaction os2 = new MockSatisfaction(Bp.class);
791         
792         Desire b1 = new MockDesire(s2);
793         Desire ob1 = new MockDesire(os2);
794         
795         // configure bindings so that d1 has two solutions, but 1 is only active
796         // within a Bp context (which is not possible in this case)
797         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
798         bindings.put(ContextPattern.any(),
799                      new MockBindRule(d1, b1));
800         final Class<?> type = Bp.class;
801         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
802         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
803                      new MockBindRule(d1, ob1));
804         
805         Desire rootDesire = new MockDesire(s1);
806         DependencySolver r = createSolver(bindings.build());
807         r.resolve(rootDesire);
808         
809         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
810         
811         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(s1, CachePolicy.NO_PREFERENCE));
812         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(s2, CachePolicy.NO_PREFERENCE));
813         
814         Assert.assertNotNull(n1);
815         Assert.assertNotNull(n2);
816         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
817         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
818     }
819 
820     @Test
821     public void testLimitedBindRuleApplicationsSuccess() throws Exception {
822         // Test that a bind-rule is properly excluded from subsequent desires
823         // when resolving a desire chain, but a final desire can still be found
824         Desire d1 = new MockDesire();
825         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
826         Satisfaction s2 = new MockSatisfaction(B.class);
827         
828         Desire b1 = new MockDesire(s2);
829         
830         // configure bindings so that s1:d1->d1, d1->b1
831         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
832         bindings.put(ContextPattern.any(),
833                      new MockBindRule(d1, b1));
834         final Class<?> type = A.class;
835         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
836         bindings.put(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
837                      new MockBindRule(d1, d1));
838         
839         Desire rootDesire = new MockDesire(s1);
840         DependencySolver r = createSolver(bindings.build());
841         r.resolve(rootDesire);
842         
843         Assert.assertEquals(2 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
844         
845         DAGNode<Component, Dependency> n1 = getNode(r.getGraph(), Component.create(s1, CachePolicy.NO_PREFERENCE));
846         DAGNode<Component, Dependency> n2 = getNode(r.getGraph(), Component.create(s2, CachePolicy.NO_PREFERENCE));
847         
848         Assert.assertNotNull(n1);
849         Assert.assertNotNull(n2);
850         Assert.assertEquals(1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).size());
851         Assert.assertEquals(d1, Sets.filter(n1.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(n2))).iterator().next().getLabel().getInitialDesire());
852     }
853     
854     @Test
855     public void testMultipleRequestsMergeSuccess() throws Exception {
856         // Test that multiple requests to resolve() will update the graph
857         // and share dependency nodes as expected
858         Desire a1 = new MockDesire(); // a's dependency
859         Desire d1 = new MockDesire(); // d's first dependency
860         Desire d2 = new MockDesire(); // d's second dependency
861         Satisfaction sa = new MockSatisfaction(A.class, Arrays.asList(a1));
862         Satisfaction sap = new MockSatisfaction(Ap.class, Arrays.asList(a1)); // variant of CycleA
863         Satisfaction sd = new MockSatisfaction(D.class, Arrays.asList(d1, d2));
864         Satisfaction sb = new MockSatisfaction(B.class);
865         Satisfaction sc = new MockSatisfaction(C.class);
866         
867         Desire da = new MockDesire(sa);
868         Desire dap = new MockDesire(sap);
869         
870         // configure bindings so that a1 -> sd, b1 -> sb, b2 -> sc
871         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
872         bindings.putAll(ContextPattern.any(),
873                         new MockBindRule(a1, new MockDesire(sd)),
874                         new MockBindRule(d1, new MockDesire(sb)),
875                         new MockBindRule(d2, new MockDesire(sc)));
876         
877         DependencySolver r = createSolver(bindings.build());
878         r.resolve(da);
879         r.resolve(dap);
880         
881         DAGNode<Component, Dependency> root = r.getGraph();
882         Assert.assertEquals(5 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
883         Assert.assertEquals(2, root.getOutgoingEdges().size()); // da and dap
884         
885         DAGNode<Component, Dependency> na =
886                 root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(da)).getTail();
887         DAGNode<Component, Dependency> nap = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(dap)).getTail();
888         
889         // sa and sap were different satisfactions, so they should be separate nodes
890         Assert.assertNotSame(na, nap);
891         
892         // the resolved desire for a1, from da
893         DAGNode<Component, Dependency> ra1 = na.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(a1)).getTail();
894         DAGNode<Component, Dependency> ra1p = nap.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(a1)).getTail();
895         
896         // verify that both a and ap point to the sb satisfaction, and verify
897         // that sb (and also its children) are properly shared
898         Assert.assertSame(sd, ra1.getLabel().getSatisfaction());
899         Assert.assertSame(sd, ra1p.getLabel().getSatisfaction());
900         Assert.assertSame(ra1, ra1p);
901 
902         Predicate<DAGNode<Component, ?>> tgt = DAGNode.labelMatches(Predicates.equalTo(Component.create(sd, CachePolicy.NO_PREFERENCE)));
903         DAGNode<Component, Dependency> node =
904                 Iterables.find(r.getGraph().getReachableNodes(),
905                                tgt);
906         assertThat(r.getGraph().getIncomingEdges(node),
907                    hasSize(2));
908     }
909     
910     @Test
911     public void testMultipleRequestsNoMergeSuccess() throws Exception {
912         // Test that multiple requests will keep nodes separate as required
913         // by dependency configuration
914         Desire a1 = new MockDesire(); // a's dependency
915         Desire d1 = new MockDesire(); // d's first dependency
916         Desire d2 = new MockDesire(); // d's second dependency
917         Satisfaction sa = new MockSatisfaction(A.class, Arrays.asList(a1));
918         Satisfaction sap = new MockSatisfaction(Ap.class, Arrays.asList(a1)); // variant of CycleA
919         Satisfaction sd = new MockSatisfaction(D.class, Arrays.asList(d1, d2));
920         Satisfaction sb = new MockSatisfaction(B.class);
921         Satisfaction sbp = new MockSatisfaction(Bp.class); // variant of B
922         Satisfaction sc = new MockSatisfaction(C.class);
923         Satisfaction scp = new MockSatisfaction(Cp.class); // variant of C
924         
925         Desire da = new MockDesire(sa);
926         Desire dap = new MockDesire(sap);
927         
928         // configure bindings so that a1 -> sd, b1 -> sb, b2 -> sc
929         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
930         bindings.putAll(ContextPattern.any(),
931                         new MockBindRule(a1, new MockDesire(sd)),
932                         new MockBindRule(d1, new MockDesire(sb)),
933                         new MockBindRule(d2, new MockDesire(sc)));
934         final Class<?> type = Ap.class;
935         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
936         bindings.putAll(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
937                         new MockBindRule(d1, new MockDesire(sbp)),
938                         new MockBindRule(d2, new MockDesire(scp)));
939         
940         DependencySolver r = createSolver(bindings.build());
941         r.resolve(da);
942         r.resolve(dap);
943         
944         DAGNode<Component, Dependency> root = r.getGraph();
945         Assert.assertEquals(8 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
946         Assert.assertEquals(2, root.getOutgoingEdges().size()); // da and dap
947         
948         DAGNode<Component, Dependency> na = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(da)).getTail();
949         DAGNode<Component, Dependency> nap = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(dap)).getTail();
950         
951         // sa and sap were different satisfactions, so they should be separate nodes
952         Assert.assertNotSame(na, nap);
953         
954         // the resolved desire for a1, from da
955         DAGNode<Component, Dependency> ra1 = na.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(a1)).getTail();
956         DAGNode<Component, Dependency> ra1p = nap.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(a1)).getTail();
957         
958         // verify that both ra1 and ra1p are different nodes that both use the
959         // sd satisfaction because sd's dependencies are configured differently
960         Assert.assertNotSame(ra1, ra1p);
961         Assert.assertSame(sd, ra1.getLabel().getSatisfaction());
962         Assert.assertSame(sd, ra1p.getLabel().getSatisfaction());
963         
964         Assert.assertSame(sb, ra1.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d1)).getTail().getLabel().getSatisfaction());
965         Assert.assertSame(sc, ra1.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d2)).getTail().getLabel().getSatisfaction());
966         Assert.assertSame(sbp, ra1p.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d1)).getTail().getLabel().getSatisfaction());
967         Assert.assertSame(scp, ra1p.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d2)).getTail().getLabel().getSatisfaction());
968     }
969     
970     @Test
971     public void testRequestDependencyMergeSuccess() throws Exception {
972         // Test that a request for a desire already in the graph as a dependency
973         // will have a new edge from the root to that dependency added.
974         Desire a1 = new MockDesire(); // a's dependency
975         Desire d1 = new MockDesire(); // d's first dependency
976         Desire d2 = new MockDesire(); // d's second dependency
977         Satisfaction sa = new MockSatisfaction(A.class, Arrays.asList(a1));
978         Satisfaction sd = new MockSatisfaction(D.class, Arrays.asList(d1, d2));
979         Satisfaction sb = new MockSatisfaction(B.class);
980         Satisfaction sc = new MockSatisfaction(C.class);
981         
982         Desire da = new MockDesire(sa);
983         Desire dd = new MockDesire(sd);
984         // configure bindings so that a1 -> sd, b1 -> sb, b2 -> sc
985         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
986         bindings.putAll(ContextPattern.any(),
987                         new MockBindRule(a1, new MockDesire(sd)),
988                         new MockBindRule(d1, new MockDesire(sb)),
989                         new MockBindRule(d2, new MockDesire(sc)));
990         
991         DependencySolver r = createSolver(bindings.build());
992         r.resolve(da);
993         r.resolve(dd);
994         
995         DAGNode<Component, Dependency> root = r.getGraph();
996         Assert.assertEquals(4 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
997         Assert.assertEquals(2, root.getOutgoingEdges().size()); // da and dd
998         
999         DAGNode<Component, Dependency> na = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(da)).getTail();
1000         DAGNode<Component, Dependency> nd = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(dd)).getTail();
1001         
1002         // additionally verify that there is an edge going from na to nd
1003         Assert.assertEquals(1, Sets.filter(na.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(nd))).size());
1004         Assert.assertSame(nd, na.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(a1)).getTail());
1005     }
1006     
1007     @Test
1008     public void testRequestDependencyNoMergeSuccess() throws Exception {
1009         // Test that a request for a desire already in the graph as a dependency,
1010         // will create a new node if the dependency has a different configuration
1011         // because of context-specific bind rules
1012         Desire a1 = new MockDesire(); // a's dependency
1013         Desire d1 = new MockDesire(); // d's first dependency
1014         Desire d2 = new MockDesire(); // d's second dependency
1015         Satisfaction sa = new MockSatisfaction(A.class, Arrays.asList(a1));
1016         Satisfaction sd = new MockSatisfaction(D.class, Arrays.asList(d1, d2));
1017         Satisfaction sb = new MockSatisfaction(B.class);
1018         Satisfaction sbp = new MockSatisfaction(Bp.class); // variant of B
1019         Satisfaction sc = new MockSatisfaction(C.class);
1020         Satisfaction scp = new MockSatisfaction(Cp.class); // variant of C
1021         
1022         Desire da = new MockDesire(sa);
1023         Desire dd = new MockDesire(sd);
1024         
1025         // configure bindings so that a1 -> sd, b1 -> sb, b2 -> sc
1026         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1027         bindings.putAll(ContextPattern.any(),
1028                         new MockBindRule(a1, new MockDesire(sd)),
1029                         new MockBindRule(d1, new MockDesire(sbp)),
1030                         new MockBindRule(d2, new MockDesire(scp)));
1031         final Class<?> type = A.class;
1032         final MockQualifierMatcher qualifier = MockQualifierMatcher.any();
1033         bindings.putAll(ContextPattern.subsequence(ContextElements.matchType(type, qualifier)),
1034                         new MockBindRule(d1, new MockDesire(sb)),
1035                         new MockBindRule(d2, new MockDesire(sc)));
1036         
1037         DependencySolver r = createSolver(bindings.build());
1038         r.resolve(da);
1039         r.resolve(dd);
1040         
1041         DAGNode<Component, Dependency> root = r.getGraph();
1042         Assert.assertEquals(7 + 1, r.getGraph().getReachableNodes().size()); // add one for synthetic root
1043         Assert.assertEquals(2, root.getOutgoingEdges().size()); // da and dd
1044         
1045         // resolved root desire nodes
1046         DAGNode<Component, Dependency> na = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(da)).getTail();
1047         DAGNode<Component, Dependency> nd = root.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(dd)).getTail();
1048         
1049         // make sure that there is no edge between na and nd
1050         Assert.assertTrue(Sets.filter(na.getOutgoingEdges(), DAGEdge.tailMatches(Predicates.equalTo(nd))).isEmpty());
1051         
1052         // look up dependency for na (which is also the sd satisfaction)
1053         DAGNode<Component, Dependency> nad = na.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(a1)).getTail();
1054         
1055         // verify that the two sd nodes are different and have different edge
1056         // configurations
1057         Assert.assertNotSame(nd, nad); 
1058         Assert.assertSame(sd, nd.getLabel().getSatisfaction());
1059         Assert.assertSame(sd, nad.getLabel().getSatisfaction());
1060         
1061         Assert.assertSame(sb, nad.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d1)).getTail().getLabel().getSatisfaction());
1062         Assert.assertSame(sc, nad.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d2)).getTail().getLabel().getSatisfaction());
1063         Assert.assertSame(sbp, nd.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d1)).getTail().getLabel().getSatisfaction());
1064         Assert.assertSame(scp, nd.getOutgoingEdgeWithLabel(Dependency.hasInitialDesire(d2)).getTail().getLabel().getSatisfaction());
1065     }
1066 
1067     @Test(expected=UnresolvableDependencyException.class)
1068     public void testLimitedBindRuleApplicationsFail() throws Exception {
1069         // Test that a bind-rule is properly excluded form subsequent desires
1070         // but that leaves no applicable bindings so resolving fails
1071         Desire d1 = new MockDesire();
1072         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
1073         
1074         // configure bindings so that d1->d1 so binding fails
1075         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1076         bindings.put(ContextPattern.any(),
1077                      new MockBindRule(d1, d1));
1078         
1079         Desire rootDesire = new MockDesire(s1);
1080         DependencySolver r = createSolver(bindings.build());
1081         r.resolve(rootDesire);
1082     }
1083     
1084     @Test(expected=CyclicDependencyException.class)
1085     public void testCyclicDependenciesFail() throws Exception {
1086         // Test that a cyclic dependency is properly caught and resolving
1087         // fails before a stack overflow
1088         Desire d1 = new MockDesire();
1089         Desire d2 = new MockDesire();
1090         
1091         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
1092         Satisfaction s2 = new MockSatisfaction(B.class, Arrays.asList(d2));
1093         
1094         Desire b1 = new MockDesire(s2);
1095         Desire b2 = new MockDesire(s1);
1096         
1097         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1098         bindings.putAll(ContextPattern.any(),
1099                         new MockBindRule(d1, b1),
1100                         new MockBindRule(d2, b2));
1101         
1102         Desire rootDesire = new MockDesire(s1);
1103         DependencySolver r = createSolver(bindings.build());
1104         r.resolve(rootDesire);
1105     }
1106     
1107     @Test(expected=MultipleBindingsException.class)
1108     public void testTooManyBindRulesFail() throws Exception {
1109         // Test that providing too many choices for bind rules throws an exception
1110         Desire d1 = new MockDesire();
1111         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
1112         Satisfaction s2 = new MockSatisfaction(B.class);
1113         Satisfaction s3 = new MockSatisfaction(C.class);
1114         
1115         Desire b1 = new MockDesire(s2);
1116         Desire ob1 = new MockDesire(s3);
1117         
1118         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1119         bindings.putAll(ContextPattern.any(),
1120                         new MockBindRule(d1, b1),
1121                         new MockBindRule(d1, ob1));
1122         
1123         Desire rootDesire = new MockDesire(s1);
1124         DependencySolver r = createSolver(bindings.build());
1125         r.resolve(rootDesire);
1126     }
1127 
1128     @Test(expected=UnresolvableDependencyException.class)
1129     public void testUnsatisfiableDesireFail() throws Exception {
1130         // Test that a chain of desires that cannot be satisfied throws an exception
1131         Desire d1 = new MockDesire();
1132         Desire d2 = new MockDesire();
1133         Desire d3 = new MockDesire();
1134         
1135         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
1136         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1137         bindings.putAll(ContextPattern.any(),
1138                         new MockBindRule(d1, d2),
1139                         new MockBindRule(d2, d3));
1140         
1141         Desire rootDesire = new MockDesire(s1);
1142         DependencySolver r = createSolver(bindings.build());
1143         r.resolve(rootDesire);
1144     }
1145     
1146     @Test(expected=UnresolvableDependencyException.class)
1147     public void testNoBindRulesFail() throws Exception {
1148         // Test that not providing applicable bind rules will throw an exception,
1149         // even if other bind rules are given
1150         Desire d1 = new MockDesire();
1151         Desire d2 = new MockDesire();
1152         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
1153         
1154         Desire b2 = new MockDesire();
1155         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1156         bindings.put(ContextPattern.any(),
1157                      new MockBindRule(d2, b2));
1158 
1159         Desire rootDesire = new MockDesire(s1);
1160         DependencySolver r = createSolver(bindings.build());
1161         r.resolve(rootDesire);
1162     }
1163 
1164     @Test(expected=UnresolvableDependencyException.class)
1165     public void testNonLeafSatisfiableDesireFail() throws Exception {
1166         // Test that a chain of desires, where an intermediate desire is
1167         // satisfiable but the leaf node is not, still throws an exception
1168         Desire d1 = new MockDesire();
1169         Satisfaction s1 = new MockSatisfaction(A.class, Arrays.asList(d1));
1170         Satisfaction s2 = new MockSatisfaction(B.class);
1171         
1172         Desire b1 = new MockDesire(s2);
1173         Desire b2 = new MockDesire();
1174         
1175         ImmutableListMultimap.Builder<ContextMatcher, BindRule> bindings = ImmutableListMultimap.builder();
1176         bindings.putAll(ContextPattern.any(),
1177                         new MockBindRule(d1, b1),
1178                         new MockBindRule(b1, b2));
1179 
1180         Desire rootDesire = new MockDesire(s1);
1181         DependencySolver r = createSolver(bindings.build());
1182         r.resolve(rootDesire);
1183     }
1184     
1185     // Find the node for s connected to p by the given desire, d
1186     private DAGNode<Component, Dependency> getNode(DAGNode<Component, Dependency> graph, Satisfaction s, Desire d) {
1187         for (DAGEdge<Component, Dependency> e: graph.getOutgoingEdges()) {
1188             if (e.getLabel().getInitialDesire().equals(d) && e.getTail().getLabel().getSatisfaction().equals(s)) {
1189                 return e.getTail();
1190             }
1191         }
1192         return null;
1193     }
1194     
1195     private DAGNode<Component, Dependency> getNode(DAGNode<Component, Dependency> g, Component s) {
1196         Predicate<DAGNode<Component, ?>> pred = DAGNode.labelMatches(Predicates.equalTo(s));
1197         return Iterables.find(g.getReachableNodes(), pred, null);
1198     }
1199     
1200     @Qualifier
1201     @Retention(RetentionPolicy.RUNTIME)
1202     public static @interface Qual {
1203         int value();
1204     }
1205 
1206     private static class A {}
1207     private static class B {}
1208     private static class C {}
1209     private static class D {}
1210     private static class E {}
1211     private static class F {}
1212     private static class G {}
1213 
1214     private static class Ap extends A {}
1215     private static class Bp extends B {}
1216     private static class Cp extends C {}
1217 }