1 /* 2 * Copyright (C) 2018 The Dagger Authors. 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 17 package dagger.internal.codegen.validation; 18 19 import static com.google.common.base.Predicates.equalTo; 20 import static com.google.common.base.Verify.verify; 21 import static com.google.common.collect.Iterables.filter; 22 import static com.google.common.collect.Iterables.getLast; 23 import static com.google.common.collect.Iterables.indexOf; 24 import static com.google.common.collect.Iterables.transform; 25 import static dagger.internal.codegen.base.ElementFormatter.elementToString; 26 import static dagger.internal.codegen.extension.DaggerGraphs.shortestPath; 27 import static dagger.internal.codegen.extension.DaggerStreams.instancesOf; 28 import static dagger.internal.codegen.extension.DaggerStreams.presentValues; 29 import static dagger.internal.codegen.extension.DaggerStreams.toImmutableList; 30 import static dagger.internal.codegen.extension.DaggerStreams.toImmutableSet; 31 import static dagger.internal.codegen.langmodel.DaggerElements.DECLARATION_ORDER; 32 import static dagger.internal.codegen.langmodel.DaggerElements.closestEnclosingTypeElement; 33 import static java.util.Collections.min; 34 import static java.util.Comparator.comparing; 35 import static java.util.Comparator.comparingInt; 36 37 import com.google.auto.common.MoreElements; 38 import com.google.auto.common.MoreTypes; 39 import com.google.common.cache.CacheBuilder; 40 import com.google.common.cache.CacheLoader; 41 import com.google.common.cache.LoadingCache; 42 import com.google.common.collect.HashBasedTable; 43 import com.google.common.collect.ImmutableList; 44 import com.google.common.collect.ImmutableSet; 45 import com.google.common.collect.Iterables; 46 import com.google.common.collect.Table; 47 import dagger.internal.codegen.base.ElementFormatter; 48 import dagger.internal.codegen.base.Formatter; 49 import dagger.internal.codegen.binding.DependencyRequestFormatter; 50 import dagger.internal.codegen.langmodel.DaggerTypes; 51 import dagger.model.BindingGraph; 52 import dagger.model.BindingGraph.DependencyEdge; 53 import dagger.model.BindingGraph.Edge; 54 import dagger.model.BindingGraph.MaybeBinding; 55 import dagger.model.BindingGraph.Node; 56 import dagger.model.ComponentPath; 57 import java.util.Comparator; 58 import java.util.Set; 59 import java.util.function.Function; 60 import javax.inject.Inject; 61 import javax.lang.model.element.Element; 62 import javax.lang.model.element.TypeElement; 63 64 /** Helper class for generating diagnostic messages. */ 65 public final class DiagnosticMessageGenerator { 66 67 /** Injectable factory for {@code DiagnosticMessageGenerator}. */ 68 public static final class Factory { 69 private final DaggerTypes types; 70 private final DependencyRequestFormatter dependencyRequestFormatter; 71 private final ElementFormatter elementFormatter; 72 73 @Inject Factory( DaggerTypes types, DependencyRequestFormatter dependencyRequestFormatter, ElementFormatter elementFormatter)74 Factory( 75 DaggerTypes types, 76 DependencyRequestFormatter dependencyRequestFormatter, 77 ElementFormatter elementFormatter) { 78 this.types = types; 79 this.dependencyRequestFormatter = dependencyRequestFormatter; 80 this.elementFormatter = elementFormatter; 81 } 82 83 /** Creates a {@code DiagnosticMessageGenerator} for the given binding graph. */ create(BindingGraph graph)84 public DiagnosticMessageGenerator create(BindingGraph graph) { 85 return new DiagnosticMessageGenerator( 86 graph, types, dependencyRequestFormatter, elementFormatter); 87 } 88 } 89 90 private final BindingGraph graph; 91 private final DependencyRequestFormatter dependencyRequestFormatter; 92 private final ElementFormatter elementFormatter; 93 94 /** A cached function from type to all of its supertypes in breadth-first order. */ 95 private final Function<TypeElement, Iterable<TypeElement>> supertypes; 96 97 /** The shortest path (value) from an entry point (column) to a binding (row). */ 98 private final Table<MaybeBinding, DependencyEdge, ImmutableList<Node>> shortestPaths = 99 HashBasedTable.create(); 100 memoize(Function<K, V> uncached)101 private static <K, V> Function<K, V> memoize(Function<K, V> uncached) { 102 // If Android Guava is on the processor path, then c.g.c.b.Function (which LoadingCache 103 // implements) does not extend j.u.f.Function. 104 // TODO(erichang): Fix current breakages and try to remove this to enforce not having this on 105 // processor path. 106 107 // First, explicitly convert uncached to c.g.c.b.Function because CacheLoader.from() expects 108 // one. 109 com.google.common.base.Function<K, V> uncachedAsBaseFunction = uncached::apply; 110 111 LoadingCache<K, V> cache = 112 CacheBuilder.newBuilder().build(CacheLoader.from(uncachedAsBaseFunction)); 113 114 // Second, explicitly convert LoadingCache to j.u.f.Function. 115 @SuppressWarnings("deprecation") // uncachedAsBaseFunction throws only unchecked exceptions 116 Function<K, V> memoized = cache::apply; 117 118 return memoized; 119 } 120 DiagnosticMessageGenerator( BindingGraph graph, DaggerTypes types, DependencyRequestFormatter dependencyRequestFormatter, ElementFormatter elementFormatter)121 private DiagnosticMessageGenerator( 122 BindingGraph graph, 123 DaggerTypes types, 124 DependencyRequestFormatter dependencyRequestFormatter, 125 ElementFormatter elementFormatter) { 126 this.graph = graph; 127 this.dependencyRequestFormatter = dependencyRequestFormatter; 128 this.elementFormatter = elementFormatter; 129 supertypes = 130 memoize( 131 component -> transform(types.supertypes(component.asType()), MoreTypes::asTypeElement)); 132 } 133 getMessage(MaybeBinding binding)134 public String getMessage(MaybeBinding binding) { 135 ImmutableSet<DependencyEdge> entryPoints = graph.entryPointEdgesDependingOnBinding(binding); 136 ImmutableSet<DependencyEdge> requests = requests(binding); 137 ImmutableList<DependencyEdge> dependencyTrace = dependencyTrace(binding, entryPoints); 138 139 return getMessageInternal(dependencyTrace, requests, entryPoints); 140 } 141 getMessage(DependencyEdge dependencyEdge)142 public String getMessage(DependencyEdge dependencyEdge) { 143 ImmutableSet<DependencyEdge> requests = ImmutableSet.of(dependencyEdge); 144 145 ImmutableSet<DependencyEdge> entryPoints; 146 ImmutableList<DependencyEdge> dependencyTrace; 147 if (dependencyEdge.isEntryPoint()) { 148 entryPoints = ImmutableSet.of(dependencyEdge); 149 dependencyTrace = ImmutableList.of(dependencyEdge); 150 } else { 151 // It's not an entry point, so it's part of a binding 152 dagger.model.Binding binding = (dagger.model.Binding) source(dependencyEdge); 153 entryPoints = graph.entryPointEdgesDependingOnBinding(binding); 154 dependencyTrace = 155 ImmutableList.<DependencyEdge>builder() 156 .add(dependencyEdge) 157 .addAll(dependencyTrace(binding, entryPoints)) 158 .build(); 159 } 160 161 return getMessageInternal(dependencyTrace, requests, entryPoints); 162 } 163 getMessageInternal( ImmutableList<DependencyEdge> dependencyTrace, ImmutableSet<DependencyEdge> requests, ImmutableSet<DependencyEdge> entryPoints)164 private String getMessageInternal( 165 ImmutableList<DependencyEdge> dependencyTrace, 166 ImmutableSet<DependencyEdge> requests, 167 ImmutableSet<DependencyEdge> entryPoints) { 168 StringBuilder message = 169 graph.isFullBindingGraph() 170 ? new StringBuilder() 171 : new StringBuilder(dependencyTrace.size() * 100 /* a guess heuristic */); 172 173 // Print the dependency trace unless it's a full binding graph 174 if (!graph.isFullBindingGraph()) { 175 dependencyTrace.forEach( 176 edge -> dependencyRequestFormatter.appendFormatLine(message, edge.dependencyRequest())); 177 if (!dependencyTrace.isEmpty()) { 178 appendComponentPathUnlessAtRoot(message, source(getLast(dependencyTrace))); 179 } 180 } 181 182 // Print any dependency requests that aren't shown as part of the dependency trace. 183 ImmutableSet<Element> requestsToPrint = 184 requests.stream() 185 // if printing entry points, skip entry points and the traced request 186 .filter( 187 request -> 188 graph.isFullBindingGraph() 189 || (!request.isEntryPoint() && !isTracedRequest(dependencyTrace, request))) 190 .map(request -> request.dependencyRequest().requestElement()) 191 .flatMap(presentValues()) 192 .collect(toImmutableSet()); 193 if (!requestsToPrint.isEmpty()) { 194 message 195 .append("\nIt is") 196 .append(graph.isFullBindingGraph() ? " " : " also ") 197 .append("requested at:"); 198 elementFormatter.formatIndentedList(message, requestsToPrint, 1); 199 } 200 201 // Print the remaining entry points, showing which component they're in, unless it's a full 202 // binding graph 203 if (!graph.isFullBindingGraph() && entryPoints.size() > 1) { 204 message.append("\nThe following other entry points also depend on it:"); 205 entryPointFormatter.formatIndentedList( 206 message, 207 entryPoints.stream() 208 .filter(entryPoint -> !entryPoint.equals(getLast(dependencyTrace))) 209 .sorted( 210 // 1. List entry points in components closest to the root first. 211 // 2. List entry points declared in a component before those in a supertype. 212 // 3. List entry points in declaration order in their declaring type. 213 rootComponentFirst() 214 .thenComparing(nearestComponentSupertypeFirst()) 215 .thenComparing(requestElementDeclarationOrder())) 216 .collect(toImmutableList()), 217 1); 218 } 219 return message.toString(); 220 } 221 appendComponentPathUnlessAtRoot(StringBuilder message, Node node)222 public void appendComponentPathUnlessAtRoot(StringBuilder message, Node node) { 223 if (!node.componentPath().equals(graph.rootComponentNode().componentPath())) { 224 message.append(String.format(" [%s]", node.componentPath())); 225 } 226 } 227 228 private final Formatter<DependencyEdge> entryPointFormatter = 229 new Formatter<DependencyEdge>() { 230 @Override 231 public String format(DependencyEdge object) { 232 Element requestElement = object.dependencyRequest().requestElement().get(); 233 StringBuilder element = new StringBuilder(elementToString(requestElement)); 234 235 // For entry points declared in subcomponents or supertypes of the root component, 236 // append the component path to make clear to the user which component it's in. 237 ComponentPath componentPath = source(object).componentPath(); 238 if (!componentPath.atRoot() 239 || !requestElement.getEnclosingElement().equals(componentPath.rootComponent())) { 240 element.append(String.format(" [%s]", componentPath)); 241 } 242 return element.toString(); 243 } 244 }; 245 isTracedRequest( ImmutableList<DependencyEdge> dependencyTrace, DependencyEdge request)246 private static boolean isTracedRequest( 247 ImmutableList<DependencyEdge> dependencyTrace, DependencyEdge request) { 248 return !dependencyTrace.isEmpty() && request.equals(dependencyTrace.get(0)); 249 } 250 251 /** 252 * Returns the dependency trace from one of the {@code entryPoints} to {@code binding} to {@code 253 * message} as a list <i>ending with</i> the entry point. 254 */ 255 // TODO(ronshapiro): Adding a DependencyPath type to dagger.model could be useful, i.e. 256 // bindingGraph.shortestPathFromEntryPoint(DependencyEdge, MaybeBindingNode) dependencyTrace( MaybeBinding binding, ImmutableSet<DependencyEdge> entryPoints)257 ImmutableList<DependencyEdge> dependencyTrace( 258 MaybeBinding binding, ImmutableSet<DependencyEdge> entryPoints) { 259 // Module binding graphs may have bindings unreachable from any entry points. If there are 260 // no entry points for this DiagnosticInfo, don't try to print a dependency trace. 261 if (entryPoints.isEmpty()) { 262 return ImmutableList.of(); 263 } 264 // Show the full dependency trace for one entry point. 265 DependencyEdge entryPointForTrace = 266 min( 267 entryPoints, 268 // prefer entry points in components closest to the root 269 rootComponentFirst() 270 // then prefer entry points with a short dependency path to the error 271 .thenComparing(shortestDependencyPathFirst(binding)) 272 // then prefer entry points declared in the component to those declared in a 273 // supertype 274 .thenComparing(nearestComponentSupertypeFirst()) 275 // finally prefer entry points declared first in their enclosing type 276 .thenComparing(requestElementDeclarationOrder())); 277 278 ImmutableList<Node> shortestBindingPath = 279 shortestPathFromEntryPoint(entryPointForTrace, binding); 280 verify( 281 !shortestBindingPath.isEmpty(), 282 "no dependency path from %s to %s in %s", 283 entryPointForTrace, 284 binding, 285 graph); 286 287 ImmutableList.Builder<DependencyEdge> dependencyTrace = ImmutableList.builder(); 288 dependencyTrace.add(entryPointForTrace); 289 for (int i = 0; i < shortestBindingPath.size() - 1; i++) { 290 Set<Edge> dependenciesBetween = 291 graph 292 .network() 293 .edgesConnecting(shortestBindingPath.get(i), shortestBindingPath.get(i + 1)); 294 // If a binding requests a key more than once, any of them should be fine to get to the 295 // shortest path 296 dependencyTrace.add((DependencyEdge) Iterables.get(dependenciesBetween, 0)); 297 } 298 return dependencyTrace.build().reverse(); 299 } 300 301 /** Returns all the nonsynthetic dependency requests for a binding. */ requests(MaybeBinding binding)302 ImmutableSet<DependencyEdge> requests(MaybeBinding binding) { 303 return graph.network().inEdges(binding).stream() 304 .flatMap(instancesOf(DependencyEdge.class)) 305 .filter(edge -> edge.dependencyRequest().requestElement().isPresent()) 306 .sorted(requestEnclosingTypeName().thenComparing(requestElementDeclarationOrder())) 307 .collect(toImmutableSet()); 308 } 309 310 /** 311 * Returns a comparator that sorts entry points in components whose paths from the root are 312 * shorter first. 313 */ rootComponentFirst()314 Comparator<DependencyEdge> rootComponentFirst() { 315 return comparingInt(entryPoint -> source(entryPoint).componentPath().components().size()); 316 } 317 318 /** 319 * Returns a comparator that puts entry points whose shortest dependency path to {@code binding} 320 * is shortest first. 321 */ shortestDependencyPathFirst(MaybeBinding binding)322 Comparator<DependencyEdge> shortestDependencyPathFirst(MaybeBinding binding) { 323 return comparing(entryPoint -> shortestPathFromEntryPoint(entryPoint, binding).size()); 324 } 325 shortestPathFromEntryPoint(DependencyEdge entryPoint, MaybeBinding binding)326 ImmutableList<Node> shortestPathFromEntryPoint(DependencyEdge entryPoint, MaybeBinding binding) { 327 return shortestPaths 328 .row(binding) 329 .computeIfAbsent( 330 entryPoint, 331 ep -> 332 shortestPath( 333 node -> 334 filter(graph.network().successors(node), MaybeBinding.class::isInstance), 335 graph.network().incidentNodes(ep).target(), 336 binding)); 337 } 338 339 /** 340 * Returns a comparator that sorts entry points in by the distance of the type that declares them 341 * from the type of the component that contains them. 342 * 343 * <p>For instance, an entry point declared directly in the component type would sort before one 344 * declared in a direct supertype, which would sort before one declared in a supertype of a 345 * supertype. 346 */ nearestComponentSupertypeFirst()347 Comparator<DependencyEdge> nearestComponentSupertypeFirst() { 348 return comparingInt( 349 entryPoint -> 350 indexOf( 351 supertypes.apply(componentContainingEntryPoint(entryPoint)), 352 equalTo(typeDeclaringEntryPoint(entryPoint)))); 353 } 354 componentContainingEntryPoint(DependencyEdge entryPoint)355 TypeElement componentContainingEntryPoint(DependencyEdge entryPoint) { 356 return source(entryPoint).componentPath().currentComponent(); 357 } 358 typeDeclaringEntryPoint(DependencyEdge entryPoint)359 TypeElement typeDeclaringEntryPoint(DependencyEdge entryPoint) { 360 return MoreElements.asType( 361 entryPoint.dependencyRequest().requestElement().get().getEnclosingElement()); 362 } 363 364 /** 365 * Returns a comparator that sorts dependency edges lexicographically by the qualified name of the 366 * type that contains them. Only appropriate for edges with request elements. 367 */ requestEnclosingTypeName()368 Comparator<DependencyEdge> requestEnclosingTypeName() { 369 return comparing( 370 edge -> 371 closestEnclosingTypeElement(edge.dependencyRequest().requestElement().get()) 372 .getQualifiedName() 373 .toString()); 374 } 375 376 /** 377 * Returns a comparator that sorts edges in the order in which their request elements were 378 * declared in their declaring type. 379 * 380 * <p>Only useful to compare edges whose request elements were declared in the same type. 381 */ requestElementDeclarationOrder()382 Comparator<DependencyEdge> requestElementDeclarationOrder() { 383 return comparing(edge -> edge.dependencyRequest().requestElement().get(), DECLARATION_ORDER); 384 } 385 source(Edge edge)386 private Node source(Edge edge) { 387 return graph.network().incidentNodes(edge).source(); 388 } 389 } 390