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