001package org.apache.maven.artifact.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>alpha</code> or <code>a</code></li>
045 *     <li><code>beta</code> or <code>b</code></li>
046 *     <li><code>milestone</code> or <code>m</code></li>
047 *     <li><code>rc</code> or <code>cr</code></li>
048 *     <li><code>snapshot</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        int INTEGER_ITEM = 0;
073        int STRING_ITEM = 1;
074        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 BIG_INTEGER_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 = BIG_INTEGER_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 BIG_INTEGER_ZERO.equals( value );
113        }
114
115        public int compareTo( Item item )
116        {
117            if ( item == null )
118            {
119                return BIG_INTEGER_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}