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}