1 /* 2 * Copyright (C) 2024 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.binding; 18 19 import static com.google.common.base.Preconditions.checkState; 20 import static dagger.internal.codegen.extension.DaggerStreams.instancesOf; 21 import static dagger.internal.codegen.extension.DaggerStreams.toImmutableSet; 22 23 import com.google.common.collect.ImmutableList; 24 import com.google.common.collect.ImmutableMap; 25 import com.google.common.collect.ImmutableSet; 26 import com.google.common.collect.Maps; 27 import com.google.common.graph.EndpointPair; 28 import com.google.common.graph.MutableNetwork; 29 import com.google.common.graph.Network; 30 import com.google.common.graph.NetworkBuilder; 31 import dagger.internal.codegen.base.TarjanSCCs; 32 import dagger.internal.codegen.model.BindingGraph.Edge; 33 import dagger.internal.codegen.model.BindingGraph.Node; 34 import java.util.Map; 35 36 /** Transformations on the binding graph network. */ 37 final class BindingGraphTransformations { 38 /** Returns a network where {@link BindingType} is present for all binding nodes. */ withFixedBindingTypes(MutableNetwork<Node, Edge> network)39 static MutableNetwork<Node, Edge> withFixedBindingTypes(MutableNetwork<Node, Edge> network) { 40 ImmutableSet<BindingNode> bindingsToFix = bindingsWithMissingBindingTypes(network); 41 if (bindingsToFix.isEmpty()) { 42 return network; 43 } 44 45 MutableNetwork<Node, Edge> fixedNetwork = withFixedBindingTypes(network, bindingsToFix); 46 47 // Check that all bindings now have a BindingType in the fixed network. 48 checkState(bindingsWithMissingBindingTypes(fixedNetwork).isEmpty()); 49 return fixedNetwork; 50 } 51 withFixedBindingTypes( Network<Node, Edge> network, ImmutableSet<BindingNode> bindingsToFix)52 private static MutableNetwork<Node, Edge> withFixedBindingTypes( 53 Network<Node, Edge> network, ImmutableSet<BindingNode> bindingsToFix) { 54 // Topologically sort the bindings so that we're guaranteed all dependencies of a binding are 55 // fixed before the bindings itself is fixed. 56 ImmutableList<ImmutableSet<BindingNode>> topologicallySortedBindingsToFix = 57 TarjanSCCs.compute( 58 bindingsToFix, 59 binding -> 60 network.successors(binding).stream() 61 .flatMap(instancesOf(BindingNode.class)) 62 // Filter because we only care about direct dependencies on bindings that need 63 // to be fixed. There might be other cycles through nodes that already have a 64 // type, but those don't matter because it won't affect how we will fix the 65 // types for these bindings. 66 .filter(bindingsToFix::contains) 67 .collect(toImmutableSet())); 68 69 Map<BindingNode, BindingNode> replacements = 70 Maps.newHashMapWithExpectedSize(bindingsToFix.size()); 71 for (ImmutableSet<BindingNode> connectedBindings : topologicallySortedBindingsToFix) { 72 BindingType successorBindingType = 73 connectedBindings.stream() 74 .flatMap(binding -> network.successors(binding).stream()) 75 .flatMap(instancesOf(BindingNode.class)) 76 .filter(binding -> !connectedBindings.contains(binding)) 77 .map(binding -> replacements.getOrDefault(binding, binding)) 78 .anyMatch(BindingNode::isProduction) 79 ? BindingType.PRODUCTION 80 : BindingType.PROVISION; 81 for (BindingNode bindingNode : connectedBindings) { 82 replacements.put(bindingNode, bindingNode.withBindingType(successorBindingType)); 83 } 84 } 85 return withReplacedBindings(network, ImmutableMap.copyOf(replacements)); 86 } 87 bindingsWithMissingBindingTypes( Network<Node, Edge> network)88 private static ImmutableSet<BindingNode> bindingsWithMissingBindingTypes( 89 Network<Node, Edge> network) { 90 return network.nodes().stream() 91 .flatMap(instancesOf(BindingNode.class)) 92 .filter(binding -> binding.delegate().optionalBindingType().isEmpty()) 93 .collect(toImmutableSet()); 94 } 95 96 // Note: This method creates an entirely new network rather than replacing individual nodes and 97 // edges in the original network. We can reconsider this choice, e.g. if it turns out to be 98 // too inefficient, but my initial thought is that this approach is a bit nicer because it 99 // maintains the original node and edge iteration order, which could be nice for debugging. withReplacedBindings( Network<Node, Edge> network, ImmutableMap<? extends Node, ? extends Node> replacementNodes)100 private static MutableNetwork<Node, Edge> withReplacedBindings( 101 Network<Node, Edge> network, ImmutableMap<? extends Node, ? extends Node> replacementNodes) { 102 MutableNetwork<Node, Edge> newNetwork = NetworkBuilder.from(network).build(); 103 for (Node node : network.nodes()) { 104 newNetwork.addNode(replacementNodes.containsKey(node) ? replacementNodes.get(node) : node); 105 } 106 for (Edge edge : network.edges()) { 107 EndpointPair<Node> incidentNodes = network.incidentNodes(edge); 108 Node source = incidentNodes.source(); 109 Node target = incidentNodes.target(); 110 newNetwork.addEdge( 111 replacementNodes.containsKey(source) ? replacementNodes.get(source) : source, 112 replacementNodes.containsKey(target) ? replacementNodes.get(target) : target, 113 edge); 114 } 115 return newNetwork; 116 } 117 BindingGraphTransformations()118 private BindingGraphTransformations() {} 119 } 120