001/*
002 * Forge Mod Loader
003 * Copyright (c) 2012-2013 cpw.
004 * All rights reserved. This program and the accompanying materials
005 * are made available under the terms of the GNU Lesser Public License v2.1
006 * which accompanies this distribution, and is available at
007 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
008 * 
009 * Contributors:
010 *     cpw - implementation
011 */
012
013package cpw.mods.fml.common.versioning;
014/*
015 * Modifications by cpw under LGPL 2.1 or later
016 */
017
018/*
019 * Licensed to the Apache Software Foundation (ASF) under one
020 * or more contributor license agreements.  See the NOTICE file
021 * distributed with this work for additional information
022 * regarding copyright ownership.  The ASF licenses this file
023 * to you under the Apache License, Version 2.0 (the
024 * "License"); you may not use this file except in compliance
025 * with the License.  You may obtain a copy of the License at
026 *
027 *  http://www.apache.org/licenses/LICENSE-2.0
028 *
029 * Unless required by applicable law or agreed to in writing,
030 * software distributed under the License is distributed on an
031 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
032 * KIND, either express or implied.  See the License for the
033 * specific language governing permissions and limitations
034 * under the License.
035 */
036
037import java.util.ArrayList;
038import java.util.Collections;
039import java.util.Iterator;
040import java.util.List;
041
042import com.google.common.base.Joiner;
043
044/**
045 * Construct a version range from a specification.
046 *
047 * @author <a href="mailto:brett@apache.org">Brett Porter</a>
048 */
049public class VersionRange
050{
051    private final ArtifactVersion recommendedVersion;
052
053    private final List<Restriction> restrictions;
054
055    private VersionRange( ArtifactVersion recommendedVersion,
056                          List<Restriction> restrictions )
057    {
058        this.recommendedVersion = recommendedVersion;
059        this.restrictions = restrictions;
060    }
061
062    public ArtifactVersion getRecommendedVersion()
063    {
064        return recommendedVersion;
065    }
066
067    public List<Restriction> getRestrictions()
068    {
069        return restrictions;
070    }
071
072    public VersionRange cloneOf()
073    {
074        List<Restriction> copiedRestrictions = null;
075
076        if ( restrictions != null )
077        {
078            copiedRestrictions = new ArrayList<Restriction>();
079
080            if ( !restrictions.isEmpty() )
081            {
082                copiedRestrictions.addAll( restrictions );
083            }
084        }
085
086        return new VersionRange( recommendedVersion, copiedRestrictions );
087    }
088
089    /**
090     * Create a version range from a string representation
091     * <p/>
092     * Some spec examples are
093     * <ul>
094     * <li><code>1.0</code> Version 1.0</li>
095     * <li><code>[1.0,2.0)</code> Versions 1.0 (included) to 2.0 (not included)</li>
096     * <li><code>[1.0,2.0]</code> Versions 1.0 to 2.0 (both included)</li>
097     * <li><code>[1.5,)</code> Versions 1.5 and higher</li>
098     * <li><code>(,1.0],[1.2,)</code> Versions up to 1.0 (included) and 1.2 or higher</li>
099     * </ul>
100     *
101     * @param spec string representation of a version or version range
102     * @return a new {@link VersionRange} object that represents the spec
103     * @throws InvalidVersionSpecificationException
104     *
105     */
106    public static VersionRange createFromVersionSpec( String spec )
107        throws InvalidVersionSpecificationException
108    {
109        if ( spec == null )
110        {
111            return null;
112        }
113
114        List<Restriction> restrictions = new ArrayList<Restriction>();
115        String process = spec;
116        ArtifactVersion version = null;
117        ArtifactVersion upperBound = null;
118        ArtifactVersion lowerBound = null;
119
120        while ( process.startsWith( "[" ) || process.startsWith( "(" ) )
121        {
122            int index1 = process.indexOf( ")" );
123            int index2 = process.indexOf( "]" );
124
125            int index = index2;
126            if ( index2 < 0 || index1 < index2 )
127            {
128                if ( index1 >= 0 )
129                {
130                    index = index1;
131                }
132            }
133
134            if ( index < 0 )
135            {
136                throw new InvalidVersionSpecificationException( "Unbounded range: " + spec );
137            }
138
139            Restriction restriction = parseRestriction( process.substring( 0, index + 1 ) );
140            if ( lowerBound == null )
141            {
142                lowerBound = restriction.getLowerBound();
143            }
144            if ( upperBound != null )
145            {
146                if ( restriction.getLowerBound() == null || restriction.getLowerBound().compareTo( upperBound ) < 0 )
147                {
148                    throw new InvalidVersionSpecificationException( "Ranges overlap: " + spec );
149                }
150            }
151            restrictions.add( restriction );
152            upperBound = restriction.getUpperBound();
153
154            process = process.substring( index + 1 ).trim();
155
156            if ( process.length() > 0 && process.startsWith( "," ) )
157            {
158                process = process.substring( 1 ).trim();
159            }
160        }
161
162        if ( process.length() > 0 )
163        {
164            if ( restrictions.size() > 0 )
165            {
166                throw new InvalidVersionSpecificationException(
167                    "Only fully-qualified sets allowed in multiple set scenario: " + spec );
168            }
169            else
170            {
171                version = new DefaultArtifactVersion( process );
172                restrictions.add( Restriction.EVERYTHING );
173            }
174        }
175
176        return new VersionRange( version, restrictions );
177    }
178
179    private static Restriction parseRestriction( String spec )
180        throws InvalidVersionSpecificationException
181    {
182        boolean lowerBoundInclusive = spec.startsWith( "[" );
183        boolean upperBoundInclusive = spec.endsWith( "]" );
184
185        String process = spec.substring( 1, spec.length() - 1 ).trim();
186
187        Restriction restriction;
188
189        int index = process.indexOf( "," );
190
191        if ( index < 0 )
192        {
193            if ( !lowerBoundInclusive || !upperBoundInclusive )
194            {
195                throw new InvalidVersionSpecificationException( "Single version must be surrounded by []: " + spec );
196            }
197
198            ArtifactVersion version = new DefaultArtifactVersion( process );
199
200            restriction = new Restriction( version, lowerBoundInclusive, version, upperBoundInclusive );
201        }
202        else
203        {
204            String lowerBound = process.substring( 0, index ).trim();
205            String upperBound = process.substring( index + 1 ).trim();
206            if ( lowerBound.equals( upperBound ) )
207            {
208                throw new InvalidVersionSpecificationException( "Range cannot have identical boundaries: " + spec );
209            }
210
211            ArtifactVersion lowerVersion = null;
212            if ( lowerBound.length() > 0 )
213            {
214                lowerVersion = new DefaultArtifactVersion( lowerBound );
215            }
216            ArtifactVersion upperVersion = null;
217            if ( upperBound.length() > 0 )
218            {
219                upperVersion = new DefaultArtifactVersion( upperBound );
220            }
221
222            if ( upperVersion != null && lowerVersion != null && upperVersion.compareTo( lowerVersion ) < 0 )
223            {
224                throw new InvalidVersionSpecificationException( "Range defies version ordering: " + spec );
225            }
226
227            restriction = new Restriction( lowerVersion, lowerBoundInclusive, upperVersion, upperBoundInclusive );
228        }
229
230        return restriction;
231    }
232
233    public static VersionRange createFromVersion( String version , ArtifactVersion existing)
234    {
235        List<Restriction> restrictions = Collections.emptyList();
236        if (existing == null)
237        {
238            existing = new DefaultArtifactVersion( version );
239        }
240        return new VersionRange(existing , restrictions );
241    }
242
243    /**
244     * Creates and returns a new <code>VersionRange</code> that is a restriction of this
245     * version range and the specified version range.
246     * <p>
247     * Note: Precedence is given to the recommended version from this version range over the
248     * recommended version from the specified version range.
249     * </p>
250     *
251     * @param restriction the <code>VersionRange</code> that will be used to restrict this version
252     *                    range.
253     * @return the <code>VersionRange</code> that is a restriction of this version range and the
254     *         specified version range.
255     *         <p>
256     *         The restrictions of the returned version range will be an intersection of the restrictions
257     *         of this version range and the specified version range if both version ranges have
258     *         restrictions. Otherwise, the restrictions on the returned range will be empty.
259     *         </p>
260     *         <p>
261     *         The recommended version of the returned version range will be the recommended version of
262     *         this version range, provided that ranges falls within the intersected restrictions. If
263     *         the restrictions are empty, this version range's recommended version is used if it is not
264     *         <code>null</code>. If it is <code>null</code>, the specified version range's recommended
265     *         version is used (provided it is non-<code>null</code>). If no recommended version can be
266     *         obtained, the returned version range's recommended version is set to <code>null</code>.
267     *         </p>
268     * @throws NullPointerException if the specified <code>VersionRange</code> is
269     *                              <code>null</code>.
270     */
271    public VersionRange restrict( VersionRange restriction )
272    {
273        List<Restriction> r1 = this.restrictions;
274        List<Restriction> r2 = restriction.restrictions;
275        List<Restriction> restrictions;
276
277        if ( r1.isEmpty() || r2.isEmpty() )
278        {
279            restrictions = Collections.emptyList();
280        }
281        else
282        {
283            restrictions = intersection( r1, r2 );
284        }
285
286        ArtifactVersion version = null;
287        if ( restrictions.size() > 0 )
288        {
289            for ( Restriction r : restrictions )
290            {
291                if ( recommendedVersion != null && r.containsVersion( recommendedVersion ) )
292                {
293                    // if we find the original, use that
294                    version = recommendedVersion;
295                    break;
296                }
297                else if ( version == null && restriction.getRecommendedVersion() != null
298                    && r.containsVersion( restriction.getRecommendedVersion() ) )
299                {
300                    // use this if we can, but prefer the original if possible
301                    version = restriction.getRecommendedVersion();
302                }
303            }
304        }
305        // Either the original or the specified version ranges have no restrictions
306        else if ( recommendedVersion != null )
307        {
308            // Use the original recommended version since it exists
309            version = recommendedVersion;
310        }
311        else if ( restriction.recommendedVersion != null )
312        {
313            // Use the recommended version from the specified VersionRange since there is no
314            // original recommended version
315            version = restriction.recommendedVersion;
316        }
317/* TODO: should throw this immediately, but need artifact
318        else
319        {
320            throw new OverConstrainedVersionException( "Restricting incompatible version ranges" );
321        }
322*/
323
324        return new VersionRange( version, restrictions );
325    }
326
327    private List<Restriction> intersection( List<Restriction> r1, List<Restriction> r2 )
328    {
329        List<Restriction> restrictions = new ArrayList<Restriction>( r1.size() + r2.size() );
330        Iterator<Restriction> i1 = r1.iterator();
331        Iterator<Restriction> i2 = r2.iterator();
332        Restriction res1 = i1.next();
333        Restriction res2 = i2.next();
334
335        boolean done = false;
336        while ( !done )
337        {
338            if ( res1.getLowerBound() == null || res2.getUpperBound() == null
339                || res1.getLowerBound().compareTo( res2.getUpperBound() ) <= 0 )
340            {
341                if ( res1.getUpperBound() == null || res2.getLowerBound() == null
342                    || res1.getUpperBound().compareTo( res2.getLowerBound() ) >= 0 )
343                {
344                    ArtifactVersion lower;
345                    ArtifactVersion upper;
346                    boolean lowerInclusive;
347                    boolean upperInclusive;
348
349                    // overlaps
350                    if ( res1.getLowerBound() == null )
351                    {
352                        lower = res2.getLowerBound();
353                        lowerInclusive = res2.isLowerBoundInclusive();
354                    }
355                    else if ( res2.getLowerBound() == null )
356                    {
357                        lower = res1.getLowerBound();
358                        lowerInclusive = res1.isLowerBoundInclusive();
359                    }
360                    else
361                    {
362                        int comparison = res1.getLowerBound().compareTo( res2.getLowerBound() );
363                        if ( comparison < 0 )
364                        {
365                            lower = res2.getLowerBound();
366                            lowerInclusive = res2.isLowerBoundInclusive();
367                        }
368                        else if ( comparison == 0 )
369                        {
370                            lower = res1.getLowerBound();
371                            lowerInclusive = res1.isLowerBoundInclusive() && res2.isLowerBoundInclusive();
372                        }
373                        else
374                        {
375                            lower = res1.getLowerBound();
376                            lowerInclusive = res1.isLowerBoundInclusive();
377                        }
378                    }
379
380                    if ( res1.getUpperBound() == null )
381                    {
382                        upper = res2.getUpperBound();
383                        upperInclusive = res2.isUpperBoundInclusive();
384                    }
385                    else if ( res2.getUpperBound() == null )
386                    {
387                        upper = res1.getUpperBound();
388                        upperInclusive = res1.isUpperBoundInclusive();
389                    }
390                    else
391                    {
392                        int comparison = res1.getUpperBound().compareTo( res2.getUpperBound() );
393                        if ( comparison < 0 )
394                        {
395                            upper = res1.getUpperBound();
396                            upperInclusive = res1.isUpperBoundInclusive();
397                        }
398                        else if ( comparison == 0 )
399                        {
400                            upper = res1.getUpperBound();
401                            upperInclusive = res1.isUpperBoundInclusive() && res2.isUpperBoundInclusive();
402                        }
403                        else
404                        {
405                            upper = res2.getUpperBound();
406                            upperInclusive = res2.isUpperBoundInclusive();
407                        }
408                    }
409
410                    // don't add if they are equal and one is not inclusive
411                    if ( lower == null || upper == null || lower.compareTo( upper ) != 0 )
412                    {
413                        restrictions.add( new Restriction( lower, lowerInclusive, upper, upperInclusive ) );
414                    }
415                    else if ( lowerInclusive && upperInclusive )
416                    {
417                        restrictions.add( new Restriction( lower, lowerInclusive, upper, upperInclusive ) );
418                    }
419
420                    //noinspection ObjectEquality
421                    if ( upper == res2.getUpperBound() )
422                    {
423                        // advance res2
424                        if ( i2.hasNext() )
425                        {
426                            res2 = i2.next();
427                        }
428                        else
429                        {
430                            done = true;
431                        }
432                    }
433                    else
434                    {
435                        // advance res1
436                        if ( i1.hasNext() )
437                        {
438                            res1 = i1.next();
439                        }
440                        else
441                        {
442                            done = true;
443                        }
444                    }
445                }
446                else
447                {
448                    // move on to next in r1
449                    if ( i1.hasNext() )
450                    {
451                        res1 = i1.next();
452                    }
453                    else
454                    {
455                        done = true;
456                    }
457                }
458            }
459            else
460            {
461                // move on to next in r2
462                if ( i2.hasNext() )
463                {
464                    res2 = i2.next();
465                }
466                else
467                {
468                    done = true;
469                }
470            }
471        }
472
473        return restrictions;
474    }
475
476    public String toString()
477    {
478        if ( recommendedVersion != null )
479        {
480            return recommendedVersion.toString();
481        }
482        else
483        {
484            return Joiner.on(',').join(restrictions);
485        }
486    }
487
488    public ArtifactVersion matchVersion( List<ArtifactVersion> versions )
489    {
490        // TODO: could be more efficient by sorting the list and then moving along the restrictions in order?
491
492        ArtifactVersion matched = null;
493        for ( ArtifactVersion version : versions )
494        {
495            if ( containsVersion( version ) )
496            {
497                // valid - check if it is greater than the currently matched version
498                if ( matched == null || version.compareTo( matched ) > 0 )
499                {
500                    matched = version;
501                }
502            }
503        }
504        return matched;
505    }
506
507    public boolean containsVersion( ArtifactVersion version )
508    {
509        for ( Restriction restriction : restrictions )
510        {
511            if ( restriction.containsVersion( version ) )
512            {
513                return true;
514            }
515        }
516        return false;
517    }
518
519    public boolean hasRestrictions()
520    {
521        return !restrictions.isEmpty() && recommendedVersion == null;
522    }
523
524    public boolean equals( Object obj )
525    {
526        if ( this == obj )
527        {
528            return true;
529        }
530        if ( !( obj instanceof VersionRange ) )
531        {
532            return false;
533        }
534        VersionRange other = (VersionRange) obj;
535
536        boolean equals =
537            recommendedVersion == other.recommendedVersion
538                || ( ( recommendedVersion != null ) && recommendedVersion.equals( other.recommendedVersion ) );
539        equals &=
540            restrictions == other.restrictions
541                || ( ( restrictions != null ) && restrictions.equals( other.restrictions ) );
542        return equals;
543    }
544
545    public int hashCode()
546    {
547        int hash = 7;
548        hash = 31 * hash + ( recommendedVersion == null ? 0 : recommendedVersion.hashCode() );
549        hash = 31 * hash + ( restrictions == null ? 0 : restrictions.hashCode() );
550        return hash;
551    }
552}