001    package 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    
022    import java.math.BigInteger;
023    import java.util.ArrayList;
024    import java.util.Arrays;
025    import java.util.Iterator;
026    import java.util.List;
027    import java.util.ListIterator;
028    import java.util.Locale;
029    import java.util.Properties;
030    import 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     */
061    public 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    }