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; 026import java.util.List; 027 028import org.eclipse.aether.RepositoryException; 029import org.eclipse.aether.collection.UnsolvableVersionConflictException; 030import org.eclipse.aether.graph.DependencyFilter; 031import org.eclipse.aether.graph.DependencyNode; 032import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext; 033import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem; 034import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector; 035import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor; 036import org.eclipse.aether.version.Version; 037import org.eclipse.aether.version.VersionConstraint; 038 039/** 040 * A version selector for use with {@link ConflictResolver} that resolves version conflicts using a nearest-wins 041 * strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail. 042 */ 043public final class NearestVersionSelector 044 extends VersionSelector 045{ 046 047 /** 048 * Creates a new instance of this version selector. 049 */ 050 public NearestVersionSelector() 051 { 052 } 053 054 @Override 055 public void selectVersion( ConflictContext context ) 056 throws RepositoryException 057 { 058 ConflictGroup group = new ConflictGroup(); 059 for ( ConflictItem item : context.getItems() ) 060 { 061 DependencyNode node = item.getNode(); 062 VersionConstraint constraint = node.getVersionConstraint(); 063 064 boolean backtrack = false; 065 boolean hardConstraint = constraint.getRange() != null; 066 067 if ( hardConstraint ) 068 { 069 if ( group.constraints.add( constraint ) ) 070 { 071 if ( group.winner != null && !constraint.containsVersion( group.winner.getNode().getVersion() ) ) 072 { 073 backtrack = true; 074 } 075 } 076 } 077 078 if ( isAcceptable( group, node.getVersion() ) ) 079 { 080 group.candidates.add( item ); 081 082 if ( backtrack ) 083 { 084 backtrack( group, context ); 085 } 086 else if ( group.winner == null || isNearer( item, group.winner ) ) 087 { 088 group.winner = item; 089 } 090 } 091 else if ( backtrack ) 092 { 093 backtrack( group, context ); 094 } 095 } 096 context.setWinner( group.winner ); 097 } 098 099 private void backtrack( ConflictGroup group, ConflictContext context ) 100 throws UnsolvableVersionConflictException 101 { 102 group.winner = null; 103 104 for ( Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); ) 105 { 106 ConflictItem candidate = it.next(); 107 108 if ( !isAcceptable( group, candidate.getNode().getVersion() ) ) 109 { 110 it.remove(); 111 } 112 else if ( group.winner == null || isNearer( candidate, group.winner ) ) 113 { 114 group.winner = candidate; 115 } 116 } 117 118 if ( group.winner == null ) 119 { 120 throw newFailure( context ); 121 } 122 } 123 124 private boolean isAcceptable( ConflictGroup group, Version version ) 125 { 126 for ( VersionConstraint constraint : group.constraints ) 127 { 128 if ( !constraint.containsVersion( version ) ) 129 { 130 return false; 131 } 132 } 133 return true; 134 } 135 136 private boolean isNearer( ConflictItem item1, ConflictItem item2 ) 137 { 138 if ( item1.isSibling( item2 ) ) 139 { 140 return item1.getNode().getVersion().compareTo( item2.getNode().getVersion() ) > 0; 141 } 142 else 143 { 144 return item1.getDepth() < item2.getDepth(); 145 } 146 } 147 148 private UnsolvableVersionConflictException newFailure( final ConflictContext context ) 149 { 150 DependencyFilter filter = new DependencyFilter() 151 { 152 public boolean accept( DependencyNode node, List<DependencyNode> parents ) 153 { 154 return context.isIncluded( node ); 155 } 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<VersionConstraint>(); 174 candidates = new ArrayList<ConflictItem>( 64 ); 175 } 176 177 @Override 178 public String toString() 179 { 180 return String.valueOf( winner ); 181 } 182 183 } 184 185}