001package org.eclipse.aether.util.graph.transformer; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import java.util.ArrayList; 023import java.util.Collection; 024import java.util.HashSet; 025import java.util.Iterator; 026 027import org.eclipse.aether.RepositoryException; 028import org.eclipse.aether.collection.UnsolvableVersionConflictException; 029import org.eclipse.aether.graph.DependencyFilter; 030import org.eclipse.aether.graph.DependencyNode; 031import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext; 032import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem; 033import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector; 034import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor; 035import org.eclipse.aether.version.Version; 036import org.eclipse.aether.version.VersionConstraint; 037 038import static java.util.Objects.requireNonNull; 039 040/** 041 * A version selector for use with {@link ConflictResolver} that resolves version conflicts using a nearest-wins 042 * strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail. 043 */ 044public final class NearestVersionSelector 045 extends VersionSelector 046{ 047 048 /** 049 * Creates a new instance of this version selector. 050 */ 051 public NearestVersionSelector() 052 { 053 } 054 055 @Override 056 public void selectVersion( ConflictContext context ) 057 throws RepositoryException 058 { 059 ConflictGroup group = new ConflictGroup(); 060 for ( ConflictItem item : context.getItems() ) 061 { 062 DependencyNode node = item.getNode(); 063 VersionConstraint constraint = node.getVersionConstraint(); 064 065 boolean backtrack = false; 066 boolean hardConstraint = constraint.getRange() != null; 067 068 if ( hardConstraint ) 069 { 070 if ( group.constraints.add( constraint ) ) 071 { 072 if ( group.winner != null && !constraint.containsVersion( group.winner.getNode().getVersion() ) ) 073 { 074 backtrack = true; 075 } 076 } 077 } 078 079 if ( isAcceptable( group, node.getVersion() ) ) 080 { 081 group.candidates.add( item ); 082 083 if ( backtrack ) 084 { 085 backtrack( group, context ); 086 } 087 else if ( group.winner == null || isNearer( item, group.winner ) ) 088 { 089 group.winner = item; 090 } 091 } 092 else if ( backtrack ) 093 { 094 backtrack( group, context ); 095 } 096 } 097 context.setWinner( group.winner ); 098 } 099 100 private void backtrack( ConflictGroup group, ConflictContext context ) 101 throws UnsolvableVersionConflictException 102 { 103 group.winner = null; 104 105 for ( Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); ) 106 { 107 ConflictItem candidate = it.next(); 108 109 if ( !isAcceptable( group, candidate.getNode().getVersion() ) ) 110 { 111 it.remove(); 112 } 113 else if ( group.winner == null || isNearer( candidate, group.winner ) ) 114 { 115 group.winner = candidate; 116 } 117 } 118 119 if ( group.winner == null ) 120 { 121 throw newFailure( context ); 122 } 123 } 124 125 private boolean isAcceptable( ConflictGroup group, Version version ) 126 { 127 for ( VersionConstraint constraint : group.constraints ) 128 { 129 if ( !constraint.containsVersion( version ) ) 130 { 131 return false; 132 } 133 } 134 return true; 135 } 136 137 private boolean isNearer( ConflictItem item1, ConflictItem item2 ) 138 { 139 if ( item1.isSibling( item2 ) ) 140 { 141 return item1.getNode().getVersion().compareTo( item2.getNode().getVersion() ) > 0; 142 } 143 else 144 { 145 return item1.getDepth() < item2.getDepth(); 146 } 147 } 148 149 private UnsolvableVersionConflictException newFailure( final ConflictContext context ) 150 { 151 DependencyFilter filter = ( node, parents ) -> 152 { 153 requireNonNull( node, "node cannot be null" ); 154 requireNonNull( parents, "parents cannot be null" ); 155 return context.isIncluded( node ); 156 }; 157 PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor( filter ); 158 context.getRoot().accept( visitor ); 159 return new UnsolvableVersionConflictException( visitor.getPaths() ); 160 } 161 162 static final class ConflictGroup 163 { 164 165 final Collection<VersionConstraint> constraints; 166 167 final Collection<ConflictItem> candidates; 168 169 ConflictItem winner; 170 171 ConflictGroup() 172 { 173 constraints = new HashSet<>(); 174 candidates = new ArrayList<>( 64 ); 175 } 176 177 @Override 178 public String toString() 179 { 180 return String.valueOf( winner ); 181 } 182 183 } 184 185}