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}