    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/*
    016 * Licensed to the Apache Software Foundation (ASF) under one
    017 * or more contributor license agreements.  See the NOTICE file
    018 * distributed with this work for additional information
    019 * regarding copyright ownership.  The ASF licenses this file
    020 * to you under the Apache License, Version 2.0 (the
    021 * "License"); you may not use this file except in compliance
    022 * with the License.  You may obtain a copy of the License at
    023 *
    024 *  http://www.apache.org/licenses/LICENSE-2.0
    025 *
    026 * Unless required by applicable law or agreed to in writing,
    027 * software distributed under the License is distributed on an
    028 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    029 * KIND, either express or implied.  See the License for the
    030 * specific language governing permissions and limitations
    031 * under the License.
    032 */
    033
    034import java.math.BigInteger;
    035import java.util.ArrayList;
    036import java.util.Arrays;
    037import java.util.Iterator;
    038import java.util.List;
    039import java.util.ListIterator;
    040import java.util.Locale;
    041import java.util.Properties;
    042import java.util.Stack;
    043
    044/**
    045 * Generic implementation of version comparison.
    046 *
    047 * <p>Features:
    048 * <ul>
    049 * <li>mixing of '<code>-</code>' (dash) and '<code>.</code>' (dot) separators,</li>
    050 * <li>transition between characters and digits also constitutes a separator:
    051 *     <code>1.0alpha1 =&gt; [1, 0, alpha, 1]</code></li>
    052 * <li>unlimited number of version components,</li>
    053 * <li>version components in the text can be digits or strings,</li>
    054 * <li>strings are checked for well-known qualifiers and the qualifier ordering is used for version ordering.
    055 *     Well-known qualifiers (case insensitive) are:<ul>
    056 *     <li><code>snapshot</code></li>
    057 *     <li><code>alpha</code> or <code>a</code></li>
    058 *     <li><code>beta</code> or <code>b</code></li>
    059 *     <li><code>milestone</code> or <code>m</code></li>
    060 *     <li><code>rc</code> or <code>cr</code></li>
    061 *     <li><code>(the empty string)</code> or <code>ga</code> or <code>final</code></li>
    062 *     <li><code>sp</code></li>
    063 *     </ul>
    064 *     Unknown qualifiers are considered after known qualifiers, with lexical order (always case insensitive),
    065 *   </li>
    066 * <li>a dash usually precedes a qualifier, and is always less important than something preceded with a dot.</li>
    067 * </ul></p>
    068 *
    069 * @see <a href="https://cwiki.apache.org/confluence/display/MAVENOLD/Versioning">"Versioning" on Maven Wiki</a>
    070 * @author <a href="mailto:kenney@apache.org">Kenney Westerhof</a>
    071 * @author <a href="mailto:hboutemy@apache.org">Hervé Boutemy</a>
    072 */
    073public class ComparableVersion
    074    implements Comparable<ComparableVersion>
    075{
    076    private String value;
    077
    078    private String canonical;
    079
    080    private ListItem items;
    081
    082    private interface Item
    083    {
    084        final int INTEGER_ITEM = 0;
    085        final int STRING_ITEM = 1;
    086        final int LIST_ITEM = 2;
    087
    088        int compareTo( Item item );
    089
    090        int getType();
    091
    092        boolean isNull();
    093    }
    094
    095    /**
    096     * Represents a numeric item in the version item list.
    097     */
    098    private static class IntegerItem
    099        implements Item
    100    {
    101        private static final BigInteger BigInteger_ZERO = new BigInteger( "0" );
    102
    103        private final BigInteger value;
    104
    105        public static final IntegerItem ZERO = new IntegerItem();
    106
    107        private IntegerItem()
    108        {
    109            this.value = BigInteger_ZERO;
    110        }
    111
    112        public IntegerItem( String str )
    113        {
    114            this.value = new BigInteger( str );
    115        }
    116
    117        public int getType()
    118        {
    119            return INTEGER_ITEM;
    120        }
    121
    122        public boolean isNull()
    123        {
    124            return BigInteger_ZERO.equals( value );
    125        }
    126
    127        public int compareTo( Item item )
    128        {
    129            if ( item == null )
    130            {
    131                return BigInteger_ZERO.equals( value ) ? 0 : 1; // 1.0 == 1, 1.1 > 1
    132            }
    133
    134            switch ( item.getType() )
    135            {
    136                case INTEGER_ITEM:
    137                    return value.compareTo( ( (IntegerItem) item ).value );
    138
    139                case STRING_ITEM:
    140                    return 1; // 1.1 > 1-sp
    141
    142                case LIST_ITEM:
    143                    return 1; // 1.1 > 1-1
    144
    145                default:
    146                    throw new RuntimeException( "invalid item: " + item.getClass() );
    147            }
    148        }
    149
    150        public String toString()
    151        {
    152            return value.toString();
    153        }
    154    }
    155
    156    /**
    157     * Represents a string in the version item list, usually a qualifier.
    158     */
    159    private static class StringItem
    160        implements Item
    161    {
    162        private static final String[] QUALIFIERS = { "alpha", "beta", "milestone", "rc", "snapshot", "", "sp" };
    163
    164        private static final List<String> _QUALIFIERS = Arrays.asList( QUALIFIERS );
    165
    166        private static final Properties ALIASES = new Properties();
    167        static
    168        {
    169            ALIASES.put( "ga", "" );
    170            ALIASES.put( "final", "" );
    171            ALIASES.put( "cr", "rc" );
    172        }
    173
    174        /**
    175         * A comparable value for the empty-string qualifier. This one is used to determine if a given qualifier makes
    176         * the version older than one without a qualifier, or more recent.
    177         */
    178        private static final String RELEASE_VERSION_INDEX = String.valueOf( _QUALIFIERS.indexOf( "" ) );
    179
    180        private String value;
    181
    182        public StringItem( String value, boolean followedByDigit )
    183        {
    184            if ( followedByDigit && value.length() == 1 )
    185            {
    186                // a1 = alpha-1, b1 = beta-1, m1 = milestone-1
    187                switch ( value.charAt( 0 ) )
    188                {
    189                    case 'a':
    190                        value = "alpha";
    191                        break;
    192                    case 'b':
    193                        value = "beta";
    194                        break;
    195                    case 'm':
    196                        value = "milestone";
    197                        break;
    198                }
    199            }
    200            this.value = ALIASES.getProperty( value , value );
    201        }
    202
    203        public int getType()
    204        {
    205            return STRING_ITEM;
    206        }
    207
    208        public boolean isNull()
    209        {
    210            return ( comparableQualifier( value ).compareTo( RELEASE_VERSION_INDEX ) == 0 );
    211        }
    212
    213        /**
    214         * Returns a comparable value for a qualifier.
    215         *
    216         * This method takes into account the ordering of known qualifiers then unknown qualifiers with lexical ordering.
    217         *
    218         * just returning an Integer with the index here is faster, but requires a lot of if/then/else to check for -1
    219         * or QUALIFIERS.size and then resort to lexical ordering. Most comparisons are decided by the first character,
    220         * so this is still fast. If more characters are needed then it requires a lexical sort anyway.
    221         *
    222         * @param qualifier
    223         * @return an equivalent value that can be used with lexical comparison
    224         */
    225        public static String comparableQualifier( String qualifier )
    226        {
    227            int i = _QUALIFIERS.indexOf( qualifier );
    228
    229            return i == -1 ? ( _QUALIFIERS.size() + "-" + qualifier ) : String.valueOf( i );
    230        }
    231
    232        public int compareTo( Item item )
    233        {
    234            if ( item == null )
    235            {
    236                // 1-rc < 1, 1-ga > 1
    237                return comparableQualifier( value ).compareTo( RELEASE_VERSION_INDEX );
    238            }
    239            switch ( item.getType() )
    240            {
    241                case INTEGER_ITEM:
    242                    return -1; // 1.any < 1.1 ?
    243
    244                case STRING_ITEM:
    245                    return comparableQualifier( value ).compareTo( comparableQualifier( ( (StringItem) item ).value ) );
    246
    247                case LIST_ITEM:
    248                    return -1; // 1.any < 1-1
    249
    250                default:
    251                    throw new RuntimeException( "invalid item: " + item.getClass() );
    252            }
    253        }
    254
    255        public String toString()
    256        {
    257            return value;
    258        }
    259    }
    260
    261    /**
    262     * Represents a version list item. This class is used both for the global item list and for sub-lists (which start
    263     * with '-(number)' in the version specification).
    264     */
    265    private static class ListItem
    266        extends ArrayList<Item>
    267        implements Item
    268    {
    269        public int getType()
    270        {
    271            return LIST_ITEM;
    272        }
    273
    274        public boolean isNull()
    275        {
    276            return ( size() == 0 );
    277        }
    278
    279        void normalize()
    280        {
    281            for( ListIterator<Item> iterator = listIterator( size() ); iterator.hasPrevious(); )
    282            {
    283                Item item = iterator.previous();
    284                if ( item.isNull() )
    285                {
    286                    iterator.remove(); // remove null trailing items: 0, "", empty list
    287                }
    288                else
    289                {
    290                    break;
    291                }
    292            }
    293        }
    294
    295        public int compareTo( Item item )
    296        {
    297            if ( item == null )
    298            {
    299                if ( size() == 0 )
    300                {
    301                    return 0; // 1-0 = 1- (normalize) = 1
    302                }
    303                Item first = get( 0 );
    304                return first.compareTo( null );
    305            }
    306            switch ( item.getType() )
    307            {
    308                case INTEGER_ITEM:
    309                    return -1; // 1-1 < 1.0.x
    310
    311                case STRING_ITEM:
    312                    return 1; // 1-1 > 1-sp
    313
    314                case LIST_ITEM:
    315                    Iterator<Item> left = iterator();
    316                    Iterator<Item> right = ( (ListItem) item ).iterator();
    317
    318                    while ( left.hasNext() || right.hasNext() )
    319                    {
    320                        Item l = left.hasNext() ? left.next() : null;
    321                        Item r = right.hasNext() ? right.next() : null;
    322
    323                        // if this is shorter, then invert the compare and mul with -1
    324                        int result = l == null ? -1 * r.compareTo( l ) : l.compareTo( r );
    325
    326                        if ( result != 0 )
    327                        {
    328                            return result;
    329                        }
    330                    }
    331
    332                    return 0;
    333
    334                default:
    335                    throw new RuntimeException( "invalid item: " + item.getClass() );
    336            }
    337        }
    338
    339        public String toString()
    340        {
    341            StringBuilder buffer = new StringBuilder( "(" );
    342            for( Iterator<Item> iter = iterator(); iter.hasNext(); )
    343            {
    344                buffer.append( iter.next() );
    345                if ( iter.hasNext() )
    346                {
    347                    buffer.append( ',' );
    348                }
    349            }
    350            buffer.append( ')' );
    351            return buffer.toString();
    352        }
    353    }
    354
    355    public ComparableVersion( String version )
    356    {
    357        parseVersion( version );
    358    }
    359
    360    public final void parseVersion( String version )
    361    {
    362        this.value = version;
    363
    364        items = new ListItem();
    365
    366        version = version.toLowerCase( Locale.ENGLISH );
    367
    368        ListItem list = items;
    369
    370        Stack<Item> stack = new Stack<Item>();
    371        stack.push( list );
    372
    373        boolean isDigit = false;
    374
    375        int startIndex = 0;
    376
    377        for ( int i = 0; i < version.length(); i++ )
    378        {
    379            char c = version.charAt( i );
    380
    381            if ( c == '.' )
    382            {
    383                if ( i == startIndex )
    384                {
    385                    list.add( IntegerItem.ZERO );
    386                }
    387                else
    388                {
    389                    list.add( parseItem( isDigit, version.substring( startIndex, i ) ) );
    390                }
    391                startIndex = i + 1;
    392            }
    393            else if ( c == '-' )
    394            {
    395                if ( i == startIndex )
    396                {
    397                    list.add( IntegerItem.ZERO );
    398                }
    399                else
    400                {
    401                    list.add( parseItem( isDigit, version.substring( startIndex, i ) ) );
    402                }
    403                startIndex = i + 1;
    404
    405                if ( isDigit )
    406                {
    407                    list.normalize(); // 1.0-* = 1-*
    408
    409                    if ( ( i + 1 < version.length() ) && Character.isDigit( version.charAt( i + 1 ) ) )
    410                    {
    411                        // new ListItem only if previous were digits and new char is a digit,
    412                        // ie need to differentiate only 1.1 from 1-1
    413                        list.add( list = new ListItem() );
    414
    415                        stack.push( list );
    416                    }
    417                }
    418            }
    419            else if ( Character.isDigit( c ) )
    420            {
    421                if ( !isDigit && i > startIndex )
    422                {
    423                    list.add( new StringItem( version.substring( startIndex, i ), true ) );
    424                    startIndex = i;
    425                }
    426
    427                isDigit = true;
    428            }
    429            else
    430            {
    431                if ( isDigit && i > startIndex )
    432                {
    433                    list.add( parseItem( true, version.substring( startIndex, i ) ) );
    434                    startIndex = i;
    435                }
    436
    437                isDigit = false;
    438            }
    439        }
    440
    441        if ( version.length() > startIndex )
    442        {
    443            list.add( parseItem( isDigit, version.substring( startIndex ) ) );
    444        }
    445
    446        while ( !stack.isEmpty() )
    447        {
    448            list = (ListItem) stack.pop();
    449            list.normalize();
    450        }
    451
    452        canonical = items.toString();
    453    }
    454
    455    private static Item parseItem( boolean isDigit, String buf )
    456    {
    457        return isDigit ? new IntegerItem( buf ) : new StringItem( buf, false );
    458    }
    459
    460    public int compareTo( ComparableVersion o )
    461    {
    462        return items.compareTo( o.items );
    463    }
    464
    465    public String toString()
    466    {
    467        return value;
    468    }
    469
    470    public boolean equals( Object o )
    471    {
    472        return ( o instanceof ComparableVersion ) && canonical.equals( ( (ComparableVersion) o ).canonical );
    473    }
    474
    475    public int hashCode()
    476    {
    477        return canonical.hashCode();
    478    }
    479}