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