Home | History | Annotate | Download | only in codegen
      1 /*
      2  * Copyright (C) 2015 Google, Inc.
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  * http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 package dagger.internal.codegen;
     17 
     18 import com.google.auto.common.MoreElements;
     19 import com.google.auto.common.MoreTypes;
     20 import com.google.auto.value.AutoValue;
     21 import com.google.common.base.Equivalence;
     22 import com.google.common.base.Function;
     23 import com.google.common.base.Joiner;
     24 import com.google.common.base.Optional;
     25 import com.google.common.base.Predicate;
     26 import com.google.common.base.Predicates;
     27 import com.google.common.collect.FluentIterable;
     28 import com.google.common.collect.ImmutableList;
     29 import com.google.common.collect.ImmutableListMultimap;
     30 import com.google.common.collect.ImmutableMap;
     31 import com.google.common.collect.ImmutableSet;
     32 import com.google.common.collect.ImmutableSetMultimap;
     33 import com.google.common.collect.Iterables;
     34 import com.google.common.collect.Maps;
     35 import com.google.common.collect.Multimap;
     36 import com.google.common.collect.Ordering;
     37 import com.google.common.collect.Sets;
     38 import dagger.Component;
     39 import dagger.Lazy;
     40 import dagger.MapKey;
     41 import dagger.internal.codegen.ComponentDescriptor.BuilderSpec;
     42 import dagger.internal.codegen.ComponentDescriptor.ComponentMethodDescriptor;
     43 import dagger.internal.codegen.ContributionBinding.ContributionType;
     44 import dagger.internal.codegen.writer.TypeNames;
     45 import java.util.ArrayDeque;
     46 import java.util.Arrays;
     47 import java.util.Collection;
     48 import java.util.Deque;
     49 import java.util.Formatter;
     50 import java.util.HashSet;
     51 import java.util.Iterator;
     52 import java.util.LinkedHashSet;
     53 import java.util.Map;
     54 import java.util.Set;
     55 import javax.inject.Provider;
     56 import javax.lang.model.element.AnnotationMirror;
     57 import javax.lang.model.element.Element;
     58 import javax.lang.model.element.ExecutableElement;
     59 import javax.lang.model.element.TypeElement;
     60 import javax.lang.model.type.ArrayType;
     61 import javax.lang.model.type.DeclaredType;
     62 import javax.lang.model.type.ExecutableType;
     63 import javax.lang.model.type.PrimitiveType;
     64 import javax.lang.model.type.TypeMirror;
     65 import javax.lang.model.util.SimpleTypeVisitor6;
     66 import javax.lang.model.util.Types;
     67 import javax.tools.Diagnostic;
     68 
     69 import static com.google.auto.common.MoreElements.getAnnotationMirror;
     70 import static com.google.auto.common.MoreTypes.asDeclared;
     71 import static com.google.auto.common.MoreTypes.asExecutable;
     72 import static com.google.auto.common.MoreTypes.asTypeElements;
     73 import static com.google.common.base.Predicates.equalTo;
     74 import static com.google.common.base.Predicates.in;
     75 import static com.google.common.base.Predicates.not;
     76 import static com.google.common.base.Verify.verify;
     77 import static com.google.common.collect.Iterables.all;
     78 import static com.google.common.collect.Iterables.any;
     79 import static com.google.common.collect.Iterables.getOnlyElement;
     80 import static com.google.common.collect.Iterables.indexOf;
     81 import static com.google.common.collect.Iterables.skip;
     82 import static com.google.common.collect.Maps.filterKeys;
     83 import static dagger.internal.codegen.ComponentDescriptor.ComponentMethodDescriptor.isOfKind;
     84 import static dagger.internal.codegen.ComponentDescriptor.ComponentMethodKind.SUBCOMPONENT;
     85 import static dagger.internal.codegen.ConfigurationAnnotations.getComponentDependencies;
     86 import static dagger.internal.codegen.ContributionBinding.indexMapBindingsByAnnotationType;
     87 import static dagger.internal.codegen.ContributionBinding.indexMapBindingsByMapKey;
     88 import static dagger.internal.codegen.ErrorMessages.DUPLICATE_SIZE_LIMIT;
     89 import static dagger.internal.codegen.ErrorMessages.INDENT;
     90 import static dagger.internal.codegen.ErrorMessages.MEMBERS_INJECTION_WITH_UNBOUNDED_TYPE;
     91 import static dagger.internal.codegen.ErrorMessages.REQUIRES_AT_INJECT_CONSTRUCTOR_OR_PROVIDER_FORMAT;
     92 import static dagger.internal.codegen.ErrorMessages.REQUIRES_AT_INJECT_CONSTRUCTOR_OR_PROVIDER_OR_PRODUCER_FORMAT;
     93 import static dagger.internal.codegen.ErrorMessages.REQUIRES_PROVIDER_FORMAT;
     94 import static dagger.internal.codegen.ErrorMessages.REQUIRES_PROVIDER_OR_PRODUCER_FORMAT;
     95 import static dagger.internal.codegen.ErrorMessages.duplicateMapKeysError;
     96 import static dagger.internal.codegen.ErrorMessages.inconsistentMapKeyAnnotationsError;
     97 import static dagger.internal.codegen.ErrorMessages.nullableToNonNullable;
     98 import static dagger.internal.codegen.ErrorMessages.stripCommonTypePrefixes;
     99 import static dagger.internal.codegen.Util.componentCanMakeNewInstances;
    100 import static dagger.internal.codegen.Util.getKeyTypeOfMap;
    101 import static dagger.internal.codegen.Util.getProvidedValueTypeOfMap;
    102 import static dagger.internal.codegen.Util.getValueTypeOfMap;
    103 import static dagger.internal.codegen.Util.isMapWithNonProvidedValues;
    104 import static dagger.internal.codegen.Util.isMapWithProvidedValues;
    105 import static javax.tools.Diagnostic.Kind.ERROR;
    106 import static javax.tools.Diagnostic.Kind.WARNING;
    107 
    108 public class BindingGraphValidator {
    109 
    110   private final Types types;
    111   private final InjectBindingRegistry injectBindingRegistry;
    112   private final ValidationType scopeCycleValidationType;
    113   private final Diagnostic.Kind nullableValidationType;
    114   private final ContributionBindingFormatter contributionBindingFormatter;
    115   private final MethodSignatureFormatter methodSignatureFormatter;
    116   private final DependencyRequestFormatter dependencyRequestFormatter;
    117   private final KeyFormatter keyFormatter;
    118 
    119   BindingGraphValidator(
    120       Types types,
    121       InjectBindingRegistry injectBindingRegistry,
    122       ValidationType scopeCycleValidationType,
    123       Diagnostic.Kind nullableValidationType,
    124       ContributionBindingFormatter contributionBindingFormatter,
    125       MethodSignatureFormatter methodSignatureFormatter,
    126       DependencyRequestFormatter dependencyRequestFormatter,
    127       KeyFormatter keyFormatter) {
    128     this.types = types;
    129     this.injectBindingRegistry = injectBindingRegistry;
    130     this.scopeCycleValidationType = scopeCycleValidationType;
    131     this.nullableValidationType = nullableValidationType;
    132     this.contributionBindingFormatter = contributionBindingFormatter;
    133     this.methodSignatureFormatter = methodSignatureFormatter;
    134     this.dependencyRequestFormatter = dependencyRequestFormatter;
    135     this.keyFormatter = keyFormatter;
    136   }
    137 
    138   private class Validation {
    139     final BindingGraph topLevelGraph;
    140     final BindingGraph subject;
    141     final ValidationReport.Builder<TypeElement> reportBuilder;
    142 
    143     Validation(BindingGraph topLevelGraph, BindingGraph subject) {
    144       this.topLevelGraph = topLevelGraph;
    145       this.subject = subject;
    146       this.reportBuilder =
    147           ValidationReport.about(subject.componentDescriptor().componentDefinitionType());
    148     }
    149 
    150     Validation(BindingGraph topLevelGraph) {
    151       this(topLevelGraph, topLevelGraph);
    152     }
    153 
    154     ValidationReport<TypeElement> buildReport() {
    155       return reportBuilder.build();
    156     }
    157 
    158     void validateSubgraph() {
    159       validateComponentScope();
    160       validateDependencyScopes();
    161       validateComponentHierarchy();
    162       validateBuilders();
    163 
    164       for (ComponentMethodDescriptor componentMethod :
    165            subject.componentDescriptor().componentMethods()) {
    166         Optional<DependencyRequest> entryPoint = componentMethod.dependencyRequest();
    167         if (entryPoint.isPresent()) {
    168           traverseRequest(
    169               entryPoint.get(),
    170               new ArrayDeque<ResolvedRequest>(),
    171               new LinkedHashSet<BindingKey>(),
    172               subject,
    173               new HashSet<DependencyRequest>());
    174         }
    175       }
    176 
    177       for (Map.Entry<ComponentMethodDescriptor, ComponentDescriptor> entry :
    178           filterKeys(subject.componentDescriptor().subcomponents(), isOfKind(SUBCOMPONENT))
    179               .entrySet()) {
    180         validateSubcomponentFactoryMethod(
    181             entry.getKey().methodElement(), entry.getValue().componentDefinitionType());
    182       }
    183 
    184       for (BindingGraph subgraph : subject.subgraphs().values()) {
    185         Validation subgraphValidation =
    186             new Validation(topLevelGraph, subgraph);
    187         subgraphValidation.validateSubgraph();
    188         reportBuilder.addSubreport(subgraphValidation.buildReport());
    189       }
    190     }
    191 
    192     private void validateSubcomponentFactoryMethod(
    193         ExecutableElement factoryMethod, TypeElement subcomponentType) {
    194       BindingGraph subgraph = subject.subgraphs().get(factoryMethod);
    195       FluentIterable<TypeElement> missingModules =
    196           FluentIterable.from(subgraph.componentRequirements())
    197               .filter(not(in(subgraphFactoryMethodParameters(factoryMethod))))
    198               .filter(
    199                   new Predicate<TypeElement>() {
    200                     @Override
    201                     public boolean apply(TypeElement moduleType) {
    202                       return !componentCanMakeNewInstances(moduleType);
    203                     }
    204                   });
    205       if (!missingModules.isEmpty()) {
    206         reportBuilder.addError(
    207             String.format(
    208                 "%s requires modules which have no visible default constructors. "
    209                     + "Add the following modules as parameters to this method: %s",
    210                 subcomponentType.getQualifiedName(),
    211                 Joiner.on(", ").join(missingModules.toSet())),
    212             factoryMethod);
    213       }
    214     }
    215 
    216     private ImmutableSet<TypeElement> subgraphFactoryMethodParameters(
    217         ExecutableElement factoryMethod) {
    218       DeclaredType componentType =
    219           asDeclared(subject.componentDescriptor().componentDefinitionType().asType());
    220       ExecutableType factoryMethodType =
    221           asExecutable(types.asMemberOf(componentType, factoryMethod));
    222       return asTypeElements(factoryMethodType.getParameterTypes());
    223     }
    224 
    225     /**
    226      * Traverse the resolved dependency requests, validating resolved bindings, and reporting any
    227      * cycles found.
    228      *
    229      * @param request the current dependency request
    230      * @param bindingPath the dependency request path from the parent of {@code request} at the head
    231      *     up to the root dependency request from the component method at the tail
    232      * @param keysInPath the binding keys corresponding to the dependency requests in
    233      *     {@code bindingPath}, but in reverse order: the first element is the binding key from the
    234      *     component method
    235      * @param resolvedRequests the requests that have already been resolved, so we can avoid
    236      *     traversing that part of the graph again
    237      */
    238     // TODO(dpb): It might be simpler to invert bindingPath's order.
    239     private void traverseRequest(
    240         DependencyRequest request,
    241         Deque<ResolvedRequest> bindingPath,
    242         LinkedHashSet<BindingKey> keysInPath,
    243         BindingGraph graph,
    244         Set<DependencyRequest> resolvedRequests) {
    245       verify(bindingPath.size() == keysInPath.size(),
    246           "mismatched path vs keys -- (%s vs %s)", bindingPath, keysInPath);
    247       BindingKey requestKey = request.bindingKey();
    248       if (keysInPath.contains(requestKey)) {
    249         reportCycle(
    250             // Invert bindingPath to match keysInPath's order
    251             ImmutableList.copyOf(bindingPath).reverse(),
    252             request,
    253             indexOf(keysInPath, equalTo(requestKey)));
    254         return;
    255       }
    256 
    257       // If request has already been resolved, avoid re-traversing the binding path.
    258       if (resolvedRequests.add(request)) {
    259         ResolvedRequest resolvedRequest = ResolvedRequest.create(request, graph);
    260         bindingPath.push(resolvedRequest);
    261         keysInPath.add(requestKey);
    262         validateResolvedBinding(bindingPath, resolvedRequest.binding());
    263 
    264         for (Binding binding : resolvedRequest.binding().bindings()) {
    265           for (DependencyRequest nextRequest : binding.implicitDependencies()) {
    266             traverseRequest(nextRequest, bindingPath, keysInPath, graph, resolvedRequests);
    267           }
    268         }
    269         bindingPath.poll();
    270         keysInPath.remove(requestKey);
    271       }
    272     }
    273 
    274     /**
    275      * Validates that the set of bindings resolved is consistent with the type of the binding, and
    276      * returns true if the bindings are valid.
    277      */
    278     private boolean validateResolvedBinding(
    279         Deque<ResolvedRequest> path, ResolvedBindings resolvedBinding) {
    280       if (resolvedBinding.bindings().isEmpty()) {
    281         reportMissingBinding(path);
    282         return false;
    283       }
    284 
    285       switch (resolvedBinding.bindingKey().kind()) {
    286         case CONTRIBUTION:
    287           ImmutableSet<ContributionBinding> contributionBindings =
    288               resolvedBinding.contributionBindings();
    289           if (any(contributionBindings, Binding.Type.MEMBERS_INJECTION)) {
    290             throw new IllegalArgumentException(
    291                 "contribution binding keys should never have members injection bindings");
    292           }
    293           if (!validateNullability(path.peek().request(), contributionBindings)) {
    294             return false;
    295           }
    296           if (any(contributionBindings, Binding.Type.PRODUCTION)
    297               && doesPathRequireProvisionOnly(path)) {
    298             reportProviderMayNotDependOnProducer(path);
    299             return false;
    300           }
    301           if (contributionBindings.size() <= 1) {
    302             return true;
    303           }
    304           ImmutableListMultimap<ContributionType, ContributionBinding> contributionsByType =
    305               ContributionBinding.contributionTypesFor(contributionBindings);
    306           if (contributionsByType.keySet().size() > 1) {
    307             reportMultipleBindingTypes(path);
    308             return false;
    309           }
    310           switch (getOnlyElement(contributionsByType.keySet())) {
    311             case UNIQUE:
    312               reportDuplicateBindings(path);
    313               return false;
    314             case MAP:
    315               boolean duplicateMapKeys = hasDuplicateMapKeys(path, contributionBindings);
    316               boolean inconsistentMapKeyAnnotationTypes =
    317                   hasInconsistentMapKeyAnnotationTypes(path, contributionBindings);
    318               return !duplicateMapKeys && !inconsistentMapKeyAnnotationTypes;
    319             case SET:
    320               break;
    321             default:
    322               throw new AssertionError();
    323           }
    324           break;
    325         case MEMBERS_INJECTION:
    326           if (!all(resolvedBinding.bindings(), Binding.Type.MEMBERS_INJECTION)) {
    327             throw new IllegalArgumentException(
    328                 "members injection binding keys should never have contribution bindings");
    329           }
    330           if (resolvedBinding.bindings().size() > 1) {
    331             reportDuplicateBindings(path);
    332             return false;
    333           }
    334           return validateMembersInjectionBinding(getOnlyElement(resolvedBinding.bindings()), path);
    335         default:
    336           throw new AssertionError();
    337       }
    338       return true;
    339     }
    340 
    341     /** Ensures that if the request isn't nullable, then each contribution is also not nullable. */
    342     private boolean validateNullability(
    343         DependencyRequest request, Set<ContributionBinding> bindings) {
    344       if (request.isNullable()) {
    345         return true;
    346       }
    347 
    348       // Note: the method signature will include the @Nullable in it!
    349       /* TODO(sameb): Sometimes javac doesn't include the Element in its output.
    350        * (Maybe this happens if the code was already compiled before this point?)
    351        * ... we manually print out the request in that case, otherwise the error
    352        * message is kind of useless. */
    353       String typeName = TypeNames.forTypeMirror(request.key().type()).toString();
    354 
    355       boolean valid = true;
    356       for (ContributionBinding binding : bindings) {
    357         if (binding.nullableType().isPresent()) {
    358           reportBuilder.addItem(
    359               nullableToNonNullable(typeName, contributionBindingFormatter.format(binding))
    360                   + "\n at: "
    361                   + dependencyRequestFormatter.format(request),
    362               nullableValidationType,
    363               request.requestElement());
    364           valid = false;
    365         }
    366       }
    367       return valid;
    368     }
    369 
    370     /**
    371      * Returns {@code true} (and reports errors) if {@code mapBindings} has more than one binding
    372      * for the same map key.
    373      */
    374     private boolean hasDuplicateMapKeys(
    375         Deque<ResolvedRequest> path, Set<ContributionBinding> mapBindings) {
    376       boolean hasDuplicateMapKeys = false;
    377       for (Collection<ContributionBinding> mapBindingsForMapKey :
    378           indexMapBindingsByMapKey(mapBindings).asMap().values()) {
    379         if (mapBindingsForMapKey.size() > 1) {
    380           hasDuplicateMapKeys = true;
    381           reportDuplicateMapKeys(path, mapBindingsForMapKey);
    382         }
    383       }
    384       return hasDuplicateMapKeys;
    385     }
    386 
    387     /**
    388      * Returns {@code true} (and reports errors) if {@code mapBindings} uses more than one
    389      * {@link MapKey} annotation type.
    390      */
    391     private boolean hasInconsistentMapKeyAnnotationTypes(
    392         Deque<ResolvedRequest> path, Set<ContributionBinding> contributionBindings) {
    393       ImmutableSetMultimap<Equivalence.Wrapper<DeclaredType>, ContributionBinding>
    394           mapBindingsByAnnotationType = indexMapBindingsByAnnotationType(contributionBindings);
    395       if (mapBindingsByAnnotationType.keySet().size() > 1) {
    396         reportInconsistentMapKeyAnnotations(path, mapBindingsByAnnotationType);
    397         return true;
    398       }
    399       return false;
    400     }
    401 
    402     /**
    403      * Validates a members injection binding, returning false (and reporting the error) if it wasn't
    404      * valid.
    405      */
    406     private boolean validateMembersInjectionBinding(
    407         Binding binding, final Deque<ResolvedRequest> path) {
    408       return binding
    409           .key()
    410           .type()
    411           .accept(
    412               new SimpleTypeVisitor6<Boolean, Void>() {
    413                 @Override
    414                 protected Boolean defaultAction(TypeMirror e, Void p) {
    415                   reportBuilder.addError(
    416                       "Invalid members injection request.", path.peek().request().requestElement());
    417                   return false;
    418                 }
    419 
    420                 @Override
    421                 public Boolean visitDeclared(DeclaredType type, Void ignored) {
    422                   // If the key has type arguments, validate that each type argument is declared.
    423                   // Otherwise the type argument may be a wildcard (or other type), and we can't
    424                   // resolve that to actual types.  If the arg was an array, validate the type
    425                   // of the array.
    426                   for (TypeMirror arg : type.getTypeArguments()) {
    427                     boolean declared;
    428                     switch (arg.getKind()) {
    429                       case ARRAY:
    430                         declared =
    431                             MoreTypes.asArray(arg)
    432                                 .getComponentType()
    433                                 .accept(
    434                                     new SimpleTypeVisitor6<Boolean, Void>() {
    435                                       @Override
    436                                       protected Boolean defaultAction(TypeMirror e, Void p) {
    437                                         return false;
    438                                       }
    439 
    440                                       @Override
    441                                       public Boolean visitDeclared(DeclaredType t, Void p) {
    442                                         for (TypeMirror arg : t.getTypeArguments()) {
    443                                           if (!arg.accept(this, null)) {
    444                                             return false;
    445                                           }
    446                                         }
    447                                         return true;
    448                                       }
    449 
    450                                       @Override
    451                                       public Boolean visitArray(ArrayType t, Void p) {
    452                                         return t.getComponentType().accept(this, null);
    453                                       }
    454 
    455                                       @Override
    456                                       public Boolean visitPrimitive(PrimitiveType t, Void p) {
    457                                         return true;
    458                                       }
    459                                     },
    460                                     null);
    461                         break;
    462                       case DECLARED:
    463                         declared = true;
    464                         break;
    465                       default:
    466                         declared = false;
    467                     }
    468                     if (!declared) {
    469                       ImmutableList<String> printableDependencyPath =
    470                           FluentIterable.from(path)
    471                               .transform(REQUEST_FROM_RESOLVED_REQUEST)
    472                               .transform(dependencyRequestFormatter)
    473                               .filter(Predicates.not(Predicates.equalTo("")))
    474                               .toList()
    475                               .reverse();
    476                       reportBuilder.addError(
    477                           String.format(
    478                               MEMBERS_INJECTION_WITH_UNBOUNDED_TYPE,
    479                               arg.toString(),
    480                               type.toString(),
    481                               Joiner.on('\n').join(printableDependencyPath)),
    482                           path.peek().request().requestElement());
    483                       return false;
    484                     }
    485                   }
    486 
    487                   TypeElement element = MoreElements.asType(type.asElement());
    488                   // Also validate that the key is not the erasure of a generic type.
    489                   // If it is, that means the user referred to Foo<T> as just 'Foo',
    490                   // which we don't allow.  (This is a judgement call -- we *could*
    491                   // allow it and instantiate the type bounds... but we don't.)
    492                   if (!MoreTypes.asDeclared(element.asType()).getTypeArguments().isEmpty()
    493                       && types.isSameType(types.erasure(element.asType()), type)) {
    494                     ImmutableList<String> printableDependencyPath =
    495                         FluentIterable.from(path)
    496                             .transform(REQUEST_FROM_RESOLVED_REQUEST)
    497                             .transform(dependencyRequestFormatter)
    498                             .filter(Predicates.not(Predicates.equalTo("")))
    499                             .toList()
    500                             .reverse();
    501                     reportBuilder.addError(
    502                         String.format(
    503                             ErrorMessages.MEMBERS_INJECTION_WITH_RAW_TYPE,
    504                             type.toString(),
    505                             Joiner.on('\n').join(printableDependencyPath)),
    506                         path.peek().request().requestElement());
    507                     return false;
    508                   }
    509 
    510                   return true; // valid
    511                 }
    512               },
    513               null);
    514     }
    515 
    516     /**
    517      * Validates that component dependencies do not form a cycle.
    518      */
    519     private void validateComponentHierarchy() {
    520       ComponentDescriptor descriptor = subject.componentDescriptor();
    521       TypeElement componentType = descriptor.componentDefinitionType();
    522       validateComponentHierarchy(componentType, componentType, new ArrayDeque<TypeElement>());
    523     }
    524 
    525     /**
    526      * Recursive method to validate that component dependencies do not form a cycle.
    527      */
    528     private void validateComponentHierarchy(
    529         TypeElement rootComponent,
    530         TypeElement componentType,
    531         Deque<TypeElement> componentStack) {
    532 
    533       if (componentStack.contains(componentType)) {
    534         // Current component has already appeared in the component chain.
    535         StringBuilder message = new StringBuilder();
    536         message.append(rootComponent.getQualifiedName());
    537         message.append(" contains a cycle in its component dependencies:\n");
    538         componentStack.push(componentType);
    539         appendIndentedComponentsList(message, componentStack);
    540         componentStack.pop();
    541         reportBuilder.addItem(message.toString(),
    542             scopeCycleValidationType.diagnosticKind().get(),
    543             rootComponent, getAnnotationMirror(rootComponent, Component.class).get());
    544       } else {
    545         Optional<AnnotationMirror> componentAnnotation =
    546             getAnnotationMirror(componentType, Component.class);
    547         if (componentAnnotation.isPresent()) {
    548           componentStack.push(componentType);
    549 
    550           ImmutableSet<TypeElement> dependencies =
    551               MoreTypes.asTypeElements(getComponentDependencies(componentAnnotation.get()));
    552           for (TypeElement dependency : dependencies) {
    553             validateComponentHierarchy(rootComponent, dependency, componentStack);
    554           }
    555 
    556           componentStack.pop();
    557         }
    558       }
    559     }
    560 
    561     /**
    562      * Validates that among the dependencies are at most one scoped dependency,
    563      * that there are no cycles within the scoping chain, and that singleton
    564      * components have no scoped dependencies.
    565      */
    566     private void validateDependencyScopes() {
    567       ComponentDescriptor descriptor = subject.componentDescriptor();
    568       Scope scope = descriptor.scope();
    569       ImmutableSet<TypeElement> scopedDependencies = scopedTypesIn(descriptor.dependencies());
    570       if (scope.isPresent()) {
    571         // Dagger 1.x scope compatibility requires this be suppress-able.
    572         if (scopeCycleValidationType.diagnosticKind().isPresent()
    573             && scope.isSingleton()) {
    574           // Singleton is a special-case representing the longest lifetime, and therefore
    575           // @Singleton components may not depend on scoped components
    576           if (!scopedDependencies.isEmpty()) {
    577             StringBuilder message = new StringBuilder(
    578                 "This @Singleton component cannot depend on scoped components:\n");
    579             appendIndentedComponentsList(message, scopedDependencies);
    580             reportBuilder.addItem(message.toString(),
    581                 scopeCycleValidationType.diagnosticKind().get(),
    582                 descriptor.componentDefinitionType(),
    583                 descriptor.componentAnnotation());
    584           }
    585         } else if (scopedDependencies.size() > 1) {
    586           // Scoped components may depend on at most one scoped component.
    587           StringBuilder message = new StringBuilder(scope.getReadableSource())
    588               .append(' ')
    589               .append(descriptor.componentDefinitionType().getQualifiedName())
    590               .append(" depends on more than one scoped component:\n");
    591           appendIndentedComponentsList(message, scopedDependencies);
    592           reportBuilder.addError(
    593               message.toString(),
    594               descriptor.componentDefinitionType(),
    595               descriptor.componentAnnotation());
    596         } else {
    597           // Dagger 1.x scope compatibility requires this be suppress-able.
    598           if (!scopeCycleValidationType.equals(ValidationType.NONE)) {
    599             validateScopeHierarchy(descriptor.componentDefinitionType(),
    600                 descriptor.componentDefinitionType(),
    601                 new ArrayDeque<Scope>(),
    602                 new ArrayDeque<TypeElement>());
    603           }
    604         }
    605       } else {
    606         // Scopeless components may not depend on scoped components.
    607         if (!scopedDependencies.isEmpty()) {
    608           StringBuilder message =
    609               new StringBuilder(descriptor.componentDefinitionType().getQualifiedName())
    610                   .append(" (unscoped) cannot depend on scoped components:\n");
    611           appendIndentedComponentsList(message, scopedDependencies);
    612           reportBuilder.addError(
    613               message.toString(),
    614               descriptor.componentDefinitionType(),
    615               descriptor.componentAnnotation());
    616         }
    617       }
    618     }
    619 
    620     private void validateBuilders() {
    621       ComponentDescriptor componentDesc = subject.componentDescriptor();
    622       if (!componentDesc.builderSpec().isPresent()) {
    623         // If no builder, nothing to validate.
    624         return;
    625       }
    626 
    627       Set<TypeElement> availableDependencies = subject.availableDependencies();
    628       Set<TypeElement> requiredDependencies =
    629           Sets.filter(
    630               availableDependencies,
    631               new Predicate<TypeElement>() {
    632                 @Override
    633                 public boolean apply(TypeElement input) {
    634                   return !Util.componentCanMakeNewInstances(input);
    635                 }
    636               });
    637       final BuilderSpec spec = componentDesc.builderSpec().get();
    638       Map<TypeElement, ExecutableElement> allSetters = spec.methodMap();
    639 
    640       ErrorMessages.ComponentBuilderMessages msgs =
    641           ErrorMessages.builderMsgsFor(subject.componentDescriptor().kind());
    642       Set<TypeElement> extraSetters = Sets.difference(allSetters.keySet(), availableDependencies);
    643       if (!extraSetters.isEmpty()) {
    644         Collection<ExecutableElement> excessMethods =
    645             Maps.filterKeys(allSetters, Predicates.in(extraSetters)).values();
    646         Iterable<String> formatted = FluentIterable.from(excessMethods).transform(
    647             new Function<ExecutableElement, String>() {
    648               @Override public String apply(ExecutableElement input) {
    649                 return methodSignatureFormatter.format(input,
    650                     Optional.of(MoreTypes.asDeclared(spec.builderDefinitionType().asType())));
    651               }});
    652         reportBuilder.addError(
    653             String.format(msgs.extraSetters(), formatted), spec.builderDefinitionType());
    654       }
    655 
    656       Set<TypeElement> missingSetters = Sets.difference(requiredDependencies, allSetters.keySet());
    657       if (!missingSetters.isEmpty()) {
    658         reportBuilder.addError(
    659             String.format(msgs.missingSetters(), missingSetters), spec.builderDefinitionType());
    660       }
    661     }
    662 
    663     /**
    664      * Validates that scopes do not participate in a scoping cycle - that is to say, scoped
    665      * components are in a hierarchical relationship terminating with Singleton.
    666      *
    667      * <p>As a side-effect, this means scoped components cannot have a dependency cycle between
    668      * themselves, since a component's presence within its own dependency path implies a cyclical
    669      * relationship between scopes. However, cycles in component dependencies are explicitly
    670      * checked in {@link #validateComponentHierarchy()}.
    671      */
    672     private void validateScopeHierarchy(TypeElement rootComponent,
    673         TypeElement componentType,
    674         Deque<Scope> scopeStack,
    675         Deque<TypeElement> scopedDependencyStack) {
    676       Scope scope = Scope.scopeOf(componentType);
    677       if (scope.isPresent()) {
    678         if (scopeStack.contains(scope)) {
    679           scopedDependencyStack.push(componentType);
    680           // Current scope has already appeared in the component chain.
    681           StringBuilder message = new StringBuilder();
    682           message.append(rootComponent.getQualifiedName());
    683           message.append(" depends on scoped components in a non-hierarchical scope ordering:\n");
    684           appendIndentedComponentsList(message, scopedDependencyStack);
    685           if (scopeCycleValidationType.diagnosticKind().isPresent()) {
    686             reportBuilder.addItem(message.toString(),
    687                 scopeCycleValidationType.diagnosticKind().get(),
    688                 rootComponent, getAnnotationMirror(rootComponent, Component.class).get());
    689           }
    690           scopedDependencyStack.pop();
    691         } else {
    692           Optional<AnnotationMirror> componentAnnotation =
    693               getAnnotationMirror(componentType, Component.class);
    694           if (componentAnnotation.isPresent()) {
    695             ImmutableSet<TypeElement> scopedDependencies = scopedTypesIn(
    696                 MoreTypes.asTypeElements(getComponentDependencies(componentAnnotation.get())));
    697             if (scopedDependencies.size() == 1) {
    698               // empty can be ignored (base-case), and > 1 is a different error reported separately.
    699               scopeStack.push(scope);
    700               scopedDependencyStack.push(componentType);
    701               validateScopeHierarchy(rootComponent, getOnlyElement(scopedDependencies),
    702                   scopeStack, scopedDependencyStack);
    703               scopedDependencyStack.pop();
    704               scopeStack.pop();
    705             }
    706           } // else: we skip component dependencies which are not components
    707         }
    708       }
    709     }
    710 
    711     /**
    712      * Validates that the scope (if any) of this component are compatible with the scopes of the
    713      * bindings available in this component
    714      */
    715     void validateComponentScope() {
    716       ImmutableMap<BindingKey, ResolvedBindings> resolvedBindings = subject.resolvedBindings();
    717       Scope componentScope = subject.componentDescriptor().scope();
    718       ImmutableSet.Builder<String> incompatiblyScopedMethodsBuilder = ImmutableSet.builder();
    719       for (ResolvedBindings bindings : resolvedBindings.values()) {
    720         if (bindings.bindingKey().kind().equals(BindingKey.Kind.CONTRIBUTION)) {
    721           for (ContributionBinding contributionBinding : bindings.ownedContributionBindings()) {
    722             Scope bindingScope = contributionBinding.scope();
    723             if (bindingScope.isPresent() && !bindingScope.equals(componentScope)) {
    724               // Scoped components cannot reference bindings to @Provides methods or @Inject
    725               // types decorated by a different scope annotation. Unscoped components cannot
    726               // reference to scoped @Provides methods or @Inject types decorated by any
    727               // scope annotation.
    728               switch (contributionBinding.bindingKind()) {
    729                 case PROVISION:
    730                   ExecutableElement provisionMethod =
    731                       MoreElements.asExecutable(contributionBinding.bindingElement());
    732                   incompatiblyScopedMethodsBuilder.add(
    733                       methodSignatureFormatter.format(provisionMethod));
    734                   break;
    735                 case INJECTION:
    736                   incompatiblyScopedMethodsBuilder.add(
    737                       bindingScope.getReadableSource()
    738                           + " class "
    739                           + contributionBinding.bindingTypeElement().getQualifiedName());
    740                   break;
    741                 default:
    742                   throw new IllegalStateException();
    743               }
    744             }
    745           }
    746         }
    747       }
    748       ImmutableSet<String> incompatiblyScopedMethods = incompatiblyScopedMethodsBuilder.build();
    749       if (!incompatiblyScopedMethods.isEmpty()) {
    750         TypeElement componentType = subject.componentDescriptor().componentDefinitionType();
    751         StringBuilder message = new StringBuilder(componentType.getQualifiedName());
    752         if (componentScope.isPresent()) {
    753           message.append(" scoped with ");
    754           message.append(componentScope.getReadableSource());
    755           message.append(" may not reference bindings with different scopes:\n");
    756         } else {
    757           message.append(" (unscoped) may not reference scoped bindings:\n");
    758         }
    759         for (String method : incompatiblyScopedMethods) {
    760           message.append(ErrorMessages.INDENT).append(method).append("\n");
    761         }
    762         reportBuilder.addError(
    763             message.toString(), componentType, subject.componentDescriptor().componentAnnotation());
    764       }
    765     }
    766 
    767     @SuppressWarnings("resource") // Appendable is a StringBuilder.
    768     private void reportProviderMayNotDependOnProducer(Deque<ResolvedRequest> path) {
    769       StringBuilder errorMessage = new StringBuilder();
    770       if (path.size() == 1) {
    771         new Formatter(errorMessage)
    772             .format(
    773                 ErrorMessages.PROVIDER_ENTRY_POINT_MAY_NOT_DEPEND_ON_PRODUCER_FORMAT,
    774                 formatRootRequestKey(path));
    775       } else {
    776         ImmutableSet<? extends Binding> dependentProvisions =
    777             provisionsDependingOnLatestRequest(path);
    778         // TODO(beder): Consider displaying all dependent provisions in the error message. If we do
    779         // that, should we display all productions that depend on them also?
    780         new Formatter(errorMessage).format(ErrorMessages.PROVIDER_MAY_NOT_DEPEND_ON_PRODUCER_FORMAT,
    781             keyFormatter.format(dependentProvisions.iterator().next().key()));
    782       }
    783       reportBuilder.addError(errorMessage.toString(), path.getLast().request().requestElement());
    784     }
    785 
    786     private void reportMissingBinding(Deque<ResolvedRequest> path) {
    787       Key key = path.peek().request().key();
    788       BindingKey bindingKey = path.peek().request().bindingKey();
    789       boolean requiresContributionMethod = !key.isValidImplicitProvisionKey(types);
    790       boolean requiresProvision = doesPathRequireProvisionOnly(path);
    791       StringBuilder errorMessage = new StringBuilder();
    792       String requiresErrorMessageFormat = requiresContributionMethod
    793           ? requiresProvision
    794               ? REQUIRES_PROVIDER_FORMAT
    795               : REQUIRES_PROVIDER_OR_PRODUCER_FORMAT
    796           : requiresProvision
    797               ? REQUIRES_AT_INJECT_CONSTRUCTOR_OR_PROVIDER_FORMAT
    798               : REQUIRES_AT_INJECT_CONSTRUCTOR_OR_PROVIDER_OR_PRODUCER_FORMAT;
    799       errorMessage.append(String.format(requiresErrorMessageFormat, keyFormatter.format(key)));
    800       if (key.isValidMembersInjectionKey()
    801           && !injectBindingRegistry.getOrFindMembersInjectionBinding(key).injectionSites()
    802               .isEmpty()) {
    803         errorMessage.append(" ").append(ErrorMessages.MEMBERS_INJECTION_DOES_NOT_IMPLY_PROVISION);
    804       }
    805       ImmutableList<String> printableDependencyPath =
    806           FluentIterable.from(path)
    807               .transform(REQUEST_FROM_RESOLVED_REQUEST)
    808               .transform(dependencyRequestFormatter)
    809               .filter(Predicates.not(Predicates.equalTo("")))
    810               .toList()
    811               .reverse();
    812       for (String dependency :
    813           printableDependencyPath.subList(1, printableDependencyPath.size())) {
    814         errorMessage.append('\n').append(dependency);
    815       }
    816       for (String suggestion : MissingBindingSuggestions.forKey(topLevelGraph, bindingKey)) {
    817         errorMessage.append('\n').append(suggestion);
    818       }
    819       reportBuilder.addError(errorMessage.toString(), path.getLast().request().requestElement());
    820     }
    821 
    822     @SuppressWarnings("resource") // Appendable is a StringBuilder.
    823     private void reportDuplicateBindings(Deque<ResolvedRequest> path) {
    824       ResolvedBindings resolvedBinding = path.peek().binding();
    825       StringBuilder builder = new StringBuilder();
    826       new Formatter(builder)
    827           .format(ErrorMessages.DUPLICATE_BINDINGS_FOR_KEY_FORMAT, formatRootRequestKey(path));
    828       for (ContributionBinding binding :
    829           Iterables.limit(resolvedBinding.contributionBindings(), DUPLICATE_SIZE_LIMIT)) {
    830         builder.append('\n').append(INDENT).append(contributionBindingFormatter.format(binding));
    831       }
    832       int numberOfOtherBindings =
    833           resolvedBinding.contributionBindings().size() - DUPLICATE_SIZE_LIMIT;
    834       if (numberOfOtherBindings > 0) {
    835         builder.append('\n').append(INDENT)
    836             .append("and ").append(numberOfOtherBindings).append(" other");
    837       }
    838       if (numberOfOtherBindings > 1) {
    839         builder.append('s');
    840       }
    841       reportBuilder.addError(builder.toString(), path.getLast().request().requestElement());
    842     }
    843 
    844     @SuppressWarnings("resource") // Appendable is a StringBuilder.
    845     private void reportMultipleBindingTypes(Deque<ResolvedRequest> path) {
    846       ResolvedBindings resolvedBinding = path.peek().binding();
    847       StringBuilder builder = new StringBuilder();
    848       new Formatter(builder)
    849           .format(ErrorMessages.MULTIPLE_BINDING_TYPES_FOR_KEY_FORMAT, formatRootRequestKey(path));
    850       ImmutableListMultimap<ContributionType, ContributionBinding> bindingsByType =
    851           ContributionBinding.contributionTypesFor(resolvedBinding.contributionBindings());
    852       for (ContributionType type :
    853           Ordering.natural().immutableSortedCopy(bindingsByType.keySet())) {
    854         builder.append(INDENT);
    855         builder.append(formatBindingType(type));
    856         builder.append(" bindings:\n");
    857         for (ContributionBinding binding : bindingsByType.get(type)) {
    858           builder
    859               .append(INDENT)
    860               .append(INDENT)
    861               .append(contributionBindingFormatter.format(binding))
    862               .append('\n');
    863         }
    864       }
    865       reportBuilder.addError(builder.toString(), path.getLast().request().requestElement());
    866     }
    867 
    868     private void reportDuplicateMapKeys(
    869         Deque<ResolvedRequest> path, Collection<ContributionBinding> mapBindings) {
    870       StringBuilder builder = new StringBuilder();
    871       builder.append(duplicateMapKeysError(formatRootRequestKey(path)));
    872       appendBindings(builder, mapBindings, 1);
    873       reportBuilder.addError(builder.toString(), path.getLast().request().requestElement());
    874     }
    875 
    876     private void reportInconsistentMapKeyAnnotations(
    877         Deque<ResolvedRequest> path,
    878         Multimap<Equivalence.Wrapper<DeclaredType>, ContributionBinding>
    879             mapBindingsByAnnotationType) {
    880       StringBuilder builder =
    881           new StringBuilder(inconsistentMapKeyAnnotationsError(formatRootRequestKey(path)));
    882       for (Map.Entry<Equivalence.Wrapper<DeclaredType>, Collection<ContributionBinding>> entry :
    883           mapBindingsByAnnotationType.asMap().entrySet()) {
    884         DeclaredType annotationType = entry.getKey().get();
    885         Collection<ContributionBinding> bindings = entry.getValue();
    886 
    887         builder
    888             .append('\n')
    889             .append(INDENT)
    890             .append(annotationType)
    891             .append(':');
    892 
    893         appendBindings(builder, bindings, 2);
    894       }
    895       reportBuilder.addError(builder.toString(), path.getLast().request().requestElement());
    896     }
    897 
    898     /**
    899      * Reports a cycle in the binding path.
    900      *
    901      * @param bindingPath the binding path, starting with the component provision dependency, and
    902      *     ending with the binding that depends on {@code request}
    903      * @param request the request that would have been added to the binding path if its
    904      *     {@linkplain DependencyRequest#bindingKey() binding key} wasn't already in it
    905      * @param indexOfDuplicatedKey the index of the dependency request in {@code bindingPath} whose
    906      *     {@linkplain DependencyRequest#bindingKey() binding key} matches {@code request}'s
    907      */
    908     private void reportCycle(
    909         Iterable<ResolvedRequest> bindingPath,
    910         DependencyRequest request,
    911         int indexOfDuplicatedKey) {
    912       ImmutableList<DependencyRequest> requestPath =
    913           FluentIterable.from(bindingPath)
    914               .transform(REQUEST_FROM_RESOLVED_REQUEST)
    915               .append(request)
    916               .toList();
    917       Element rootRequestElement = requestPath.get(0).requestElement();
    918       ImmutableList<DependencyRequest> cycle =
    919           requestPath.subList(indexOfDuplicatedKey, requestPath.size());
    920       Diagnostic.Kind kind = cycleHasProviderOrLazy(cycle) ? WARNING : ERROR;
    921       if (kind == WARNING
    922           && (suppressCycleWarnings(rootRequestElement)
    923               || suppressCycleWarnings(rootRequestElement.getEnclosingElement())
    924               || suppressCycleWarnings(cycle))) {
    925         return;
    926       }
    927       // TODO(cgruber): Provide a hint for the start and end of the cycle.
    928       TypeElement componentType = MoreElements.asType(rootRequestElement.getEnclosingElement());
    929       reportBuilder.addItem(
    930           String.format(
    931               ErrorMessages.CONTAINS_DEPENDENCY_CYCLE_FORMAT,
    932               componentType.getQualifiedName(),
    933               rootRequestElement.getSimpleName(),
    934               Joiner.on("\n")
    935                   .join(
    936                       FluentIterable.from(requestPath)
    937                           .transform(dependencyRequestFormatter)
    938                           .filter(not(equalTo("")))
    939                           .skip(1))),
    940           kind,
    941           rootRequestElement);
    942     }
    943 
    944     /**
    945      * Returns {@code true} if any step of a dependency cycle after the first is a {@link Provider}
    946      * or {@link Lazy} or a {@code Map<K, Provider<V>>}.
    947      *
    948      * <p>If an implicit {@link Provider} dependency on {@code Map<K, Provider<V>>} is immediately
    949      * preceded by a dependency on {@code Map<K, V>}, which means that the map's {@link Provider}s'
    950      * {@link Provider#get() get()} methods are called during provision and so the cycle is not
    951      * really broken.
    952      */
    953     private boolean cycleHasProviderOrLazy(ImmutableList<DependencyRequest> cycle) {
    954       DependencyRequest lastDependencyRequest = cycle.get(0);
    955       for (DependencyRequest dependencyRequest : skip(cycle, 1)) {
    956         switch (dependencyRequest.kind()) {
    957           case PROVIDER:
    958             if (!isImplicitProviderMapForValueMap(dependencyRequest, lastDependencyRequest)) {
    959               return true;
    960             }
    961             break;
    962 
    963           case LAZY:
    964             return true;
    965 
    966           case INSTANCE:
    967             if (isMapWithProvidedValues(dependencyRequest.key().type())) {
    968               return true;
    969             } else {
    970               break;
    971             }
    972 
    973           default:
    974             break;
    975         }
    976         lastDependencyRequest = dependencyRequest;
    977       }
    978       return false;
    979     }
    980 
    981     /**
    982      * Returns {@code true} if {@code maybeValueMapRequest}'s key type is {@code Map<K, V>} and
    983      * {@code maybeProviderMapRequest}'s key type is {@code Map<K, Provider<V>>}, and both keys have
    984      * the same qualifier.
    985      */
    986     private boolean isImplicitProviderMapForValueMap(
    987         DependencyRequest maybeProviderMapRequest, DependencyRequest maybeValueMapRequest) {
    988       TypeMirror maybeProviderMapRequestType = maybeProviderMapRequest.key().type();
    989       TypeMirror maybeValueMapRequestType = maybeValueMapRequest.key().type();
    990       return maybeProviderMapRequest
    991               .key()
    992               .wrappedQualifier()
    993               .equals(maybeValueMapRequest.key().wrappedQualifier())
    994           && isMapWithProvidedValues(maybeProviderMapRequestType)
    995           && isMapWithNonProvidedValues(maybeValueMapRequestType)
    996           && types.isSameType(
    997               getKeyTypeOfMap(asDeclared(maybeProviderMapRequestType)),
    998               getKeyTypeOfMap(asDeclared(maybeValueMapRequestType)))
    999           && types.isSameType(
   1000               getProvidedValueTypeOfMap(asDeclared(maybeProviderMapRequestType)),
   1001               getValueTypeOfMap(asDeclared(maybeValueMapRequestType)));
   1002     }
   1003   }
   1004 
   1005   private boolean suppressCycleWarnings(Element requestElement) {
   1006     SuppressWarnings suppressions = requestElement.getAnnotation(SuppressWarnings.class);
   1007     return suppressions != null && Arrays.asList(suppressions.value()).contains("dependency-cycle");
   1008   }
   1009 
   1010   private boolean suppressCycleWarnings(ImmutableList<DependencyRequest> pathElements) {
   1011     for (DependencyRequest dependencyRequest : pathElements) {
   1012       if (suppressCycleWarnings(dependencyRequest.requestElement())) {
   1013         return true;
   1014       }
   1015     }
   1016     return false;
   1017   }
   1018 
   1019   ValidationReport<TypeElement> validate(BindingGraph subject) {
   1020     Validation validation = new Validation(subject);
   1021     validation.validateSubgraph();
   1022     return validation.buildReport();
   1023   }
   1024 
   1025   /**
   1026    * Append and format a list of indented component types (with their scope annotations)
   1027    */
   1028   private void appendIndentedComponentsList(StringBuilder message, Iterable<TypeElement> types) {
   1029     for (TypeElement scopedComponent : types) {
   1030       message.append(INDENT);
   1031       Scope scope = Scope.scopeOf(scopedComponent);
   1032       if (scope.isPresent()) {
   1033         message.append(scope.getReadableSource()).append(' ');
   1034       }
   1035       message.append(stripCommonTypePrefixes(scopedComponent.getQualifiedName().toString()))
   1036           .append('\n');
   1037     }
   1038   }
   1039 
   1040   /**
   1041    * Returns a set of type elements containing only those found in the input set that have
   1042    * a scoping annotation.
   1043    */
   1044   private ImmutableSet<TypeElement> scopedTypesIn(Set<TypeElement> types) {
   1045     return FluentIterable.from(types).filter(new Predicate<TypeElement>() {
   1046       @Override public boolean apply(TypeElement input) {
   1047         return Scope.scopeOf(input).isPresent();
   1048       }
   1049     }).toSet();
   1050   }
   1051 
   1052   /**
   1053    * Returns whether the given dependency path would require the most recent request to be resolved
   1054    * by only provision bindings.
   1055    */
   1056   private boolean doesPathRequireProvisionOnly(Deque<ResolvedRequest> path) {
   1057     if (path.size() == 1) {
   1058       // if this is an entry-point, then we check the request
   1059       switch (path.peek().request().kind()) {
   1060         case INSTANCE:
   1061         case PROVIDER:
   1062         case LAZY:
   1063         case MEMBERS_INJECTOR:
   1064           return true;
   1065         case PRODUCER:
   1066         case PRODUCED:
   1067         case FUTURE:
   1068           return false;
   1069         default:
   1070           throw new AssertionError();
   1071       }
   1072     }
   1073     // otherwise, the second-most-recent bindings determine whether the most recent one must be a
   1074     // provision
   1075     return !provisionsDependingOnLatestRequest(path).isEmpty();
   1076   }
   1077 
   1078   /**
   1079    * Returns any provision bindings resolved for the second-most-recent request in the given path;
   1080    * that is, returns those provision bindings that depend on the latest request in the path.
   1081    */
   1082   private ImmutableSet<? extends Binding> provisionsDependingOnLatestRequest(
   1083       Deque<ResolvedRequest> path) {
   1084     Iterator<ResolvedRequest> iterator = path.iterator();
   1085     final DependencyRequest request = iterator.next().request();
   1086     ResolvedRequest previousResolvedRequest = iterator.next();
   1087     return FluentIterable.from(previousResolvedRequest.binding().bindings())
   1088         .filter(Binding.Type.PROVISION)
   1089         .filter(
   1090             new Predicate<Binding>() {
   1091               @Override
   1092               public boolean apply(Binding binding) {
   1093                 return binding.implicitDependencies().contains(request);
   1094               }
   1095             })
   1096         .toSet();
   1097   }
   1098 
   1099   private String formatBindingType(ContributionType type) {
   1100     switch (type) {
   1101       case MAP:
   1102         return "Map";
   1103       case SET:
   1104         return "Set";
   1105       case UNIQUE:
   1106         return "Unique";
   1107       default:
   1108         throw new IllegalStateException("Unknown binding type: " + type);
   1109     }
   1110   }
   1111 
   1112   private String formatRootRequestKey(Deque<ResolvedRequest> path) {
   1113     return keyFormatter.format(path.peek().request().key());
   1114   }
   1115 
   1116   private void appendBindings(
   1117       StringBuilder builder, Collection<ContributionBinding> bindings, int indentLevel) {
   1118     for (ContributionBinding binding : Iterables.limit(bindings, DUPLICATE_SIZE_LIMIT)) {
   1119       builder.append('\n');
   1120       for (int i = 0; i < indentLevel; i++) {
   1121         builder.append(INDENT);
   1122       }
   1123       builder.append(contributionBindingFormatter.format(binding));
   1124     }
   1125     int numberOfOtherBindings = bindings.size() - DUPLICATE_SIZE_LIMIT;
   1126     if (numberOfOtherBindings > 0) {
   1127       builder.append('\n');
   1128       for (int i = 0; i < indentLevel; i++) {
   1129         builder.append(INDENT);
   1130       }
   1131       builder.append("and ").append(numberOfOtherBindings).append(" other");
   1132     }
   1133     if (numberOfOtherBindings > 1) {
   1134       builder.append('s');
   1135     }
   1136   }
   1137 
   1138   @AutoValue
   1139   abstract static class ResolvedRequest {
   1140     abstract DependencyRequest request();
   1141     abstract ResolvedBindings binding();
   1142 
   1143     static ResolvedRequest create(DependencyRequest request, BindingGraph graph) {
   1144       BindingKey bindingKey = request.bindingKey();
   1145       ResolvedBindings resolvedBindings = graph.resolvedBindings().get(bindingKey);
   1146       return new AutoValue_BindingGraphValidator_ResolvedRequest(
   1147           request,
   1148           resolvedBindings == null
   1149               ? ResolvedBindings.noBindings(bindingKey, graph.componentDescriptor())
   1150               : resolvedBindings);
   1151     }
   1152   }
   1153 
   1154   private static final Function<ResolvedRequest, DependencyRequest> REQUEST_FROM_RESOLVED_REQUEST =
   1155       new Function<ResolvedRequest, DependencyRequest>() {
   1156         @Override public DependencyRequest apply(ResolvedRequest resolvedRequest) {
   1157           return resolvedRequest.request();
   1158         }
   1159       };
   1160 }
   1161