maven-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hbout...@apache.org
Subject [maven] 01/02: [MNG-6572] use int or long instead of BigIntegers for little numbers in ComparableVersion
Date Sun, 17 Mar 2019 10:02:33 GMT
This is an automated email from the ASF dual-hosted git repository.

hboutemy pushed a commit to branch MNG-6572
in repository https://gitbox.apache.org/repos/asf/maven.git

commit f5a13746e13e6225b28ef8ba6e16fc8f02946dd6
Author: Gabriel Belingueres <belingueres@gmail.com>
AuthorDate: Sat Jan 26 05:23:54 2019 -0300

    [MNG-6572] use int or long instead of BigIntegers for little numbers in
    ComparableVersion
    
    - Added class IntItem and LongItem for handling numbers lower than 2^31
    and 2^63.
    - Renamed IntegerItem to BigIntegerItem for handling larger numbers.
    - Changed old Stack implementation to LinkedList.
    - Changed LinkedList to ArrayDeque.
    - Changed thrown RuntimeException by IllegalStateException.
    - Ensure numeric values don't have leading zeroes, therefore ensuring
    that IntItem, LongItem and BigIntItem represent bigger numeric values,
    respectively.
    - Only compare item value when the other Item is of the same type.
    Otherwise infer comparison result from the quantity of digits of the
    numerical value representing the other Item.
    - Added tests.
---
 .../artifact/versioning/ComparableVersion.java     | 227 ++++++++++++++++++---
 .../artifact/versioning/ComparableVersionTest.java |  90 ++++++++
 2 files changed, 292 insertions(+), 25 deletions(-)

diff --git a/maven-artifact/src/main/java/org/apache/maven/artifact/versioning/ComparableVersion.java
b/maven-artifact/src/main/java/org/apache/maven/artifact/versioning/ComparableVersion.java
index 4c64d2b..c0ad57d 100644
--- a/maven-artifact/src/main/java/org/apache/maven/artifact/versioning/ComparableVersion.java
+++ b/maven-artifact/src/main/java/org/apache/maven/artifact/versioning/ComparableVersion.java
@@ -20,13 +20,16 @@ package org.apache.maven.artifact.versioning;
  */
 
 import java.math.BigInteger;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Deque;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Locale;
 import java.util.Properties;
-import java.util.Stack;
+
+import org.apache.commons.lang3.StringUtils;
 
 /**
  * <p>
@@ -62,6 +65,10 @@ import java.util.Stack;
 public class ComparableVersion
     implements Comparable<ComparableVersion>
 {
+    private static final int MAX_INTITEM_LENGTH = 9;
+
+    private static final int MAX_LONGITEM_LENGTH = 18;
+
     private String value;
 
     private String canonical;
@@ -70,7 +77,9 @@ public class ComparableVersion
 
     private interface Item
     {
-        int INTEGER_ITEM = 0;
+        int INT_ITEM = 3;
+        int LONG_ITEM = 4;
+        int BIGINTEGER_ITEM = 0;
         int STRING_ITEM = 1;
         int LIST_ITEM = 2;
 
@@ -82,48 +91,174 @@ public class ComparableVersion
     }
 
     /**
-     * Represents a numeric item in the version item list.
+     * Represents a numeric item in the version item list that can be represented with an
int.
      */
-    private static class IntegerItem
+    private static class IntItem
         implements Item
     {
-        private static final BigInteger BIG_INTEGER_ZERO = new BigInteger( "0" );
+        private final int value;
 
-        private final BigInteger value;
+        public static final IntItem ZERO = new IntItem();
+
+        private IntItem()
+        {
+            this.value = 0;
+        }
+
+        IntItem( String str )
+        {
+            this.value = Integer.parseInt( str );
+        }
+
+        @Override
+        public int getType()
+        {
+            return INT_ITEM;
+        }
+
+        @Override
+        public boolean isNull()
+        {
+            return value == 0;
+        }
+
+        @Override
+        public int compareTo( Item item )
+        {
+            if ( item == null )
+            {
+                return ( value == 0 ) ? 0 : 1; // 1.0 == 1, 1.1 > 1
+            }
+
+            switch ( item.getType() )
+            {
+                case INT_ITEM:
+                    int itemValue = ( (IntItem) item ).value;
+                    return ( value < itemValue ) ? -1 : ( ( value == itemValue ) ? 0 :
1 );
+                case LONG_ITEM:
+                case BIGINTEGER_ITEM:
+                    return -1;
+
+                case STRING_ITEM:
+                    return 1; // 1.1 > 1-sp
+
+                case LIST_ITEM:
+                    return 1; // 1.1 > 1-1
+
+                default:
+                    throw new IllegalStateException( "invalid item: " + item.getClass() );
+            }
+        }
+
+        @Override
+        public String toString()
+        {
+            return Integer.toString( value );
+        }
+    }
+
+    /**
+     * Represents a numeric item in the version item list that can be represented with a
long.
+     */
+    private static class LongItem
+        implements Item
+    {
+        private final long value;
+
+        LongItem( String str )
+        {
+            this.value = Long.parseLong( str );
+        }
 
-        public static final IntegerItem ZERO = new IntegerItem();
+        @Override
+        public int getType()
+        {
+            return LONG_ITEM;
+        }
 
-        private IntegerItem()
+        @Override
+        public boolean isNull()
         {
-            this.value = BIG_INTEGER_ZERO;
+            return value == 0;
         }
 
-        IntegerItem( String str )
+        @Override
+        public int compareTo( Item item )
+        {
+            if ( item == null )
+            {
+                return ( value == 0 ) ? 0 : 1; // 1.0 == 1, 1.1 > 1
+            }
+
+            switch ( item.getType() )
+            {
+                case INT_ITEM:
+                    return 1;
+                case LONG_ITEM:
+                    long itemValue = ( (LongItem) item ).value;
+                    return ( value < itemValue ) ? -1 : ( ( value == itemValue ) ? 0 :
1 );
+                case BIGINTEGER_ITEM:
+                    return -1;
+
+                case STRING_ITEM:
+                    return 1; // 1.1 > 1-sp
+
+                case LIST_ITEM:
+                    return 1; // 1.1 > 1-1
+
+                default:
+                    throw new IllegalStateException( "invalid item: " + item.getClass() );
+            }
+        }
+
+        @Override
+        public String toString()
+        {
+            return Long.toString( value );
+        }
+    }
+
+    /**
+     * Represents a numeric item in the version item list.
+     */
+    private static class BigIntegerItem
+        implements Item
+    {
+        private final BigInteger value;
+
+        BigIntegerItem( String str )
         {
             this.value = new BigInteger( str );
         }
 
+        @Override
         public int getType()
         {
-            return INTEGER_ITEM;
+            return BIGINTEGER_ITEM;
         }
 
+        @Override
         public boolean isNull()
         {
-            return BIG_INTEGER_ZERO.equals( value );
+            return BigInteger.ZERO.equals( value );
         }
 
+        @Override
         public int compareTo( Item item )
         {
             if ( item == null )
             {
-                return BIG_INTEGER_ZERO.equals( value ) ? 0 : 1; // 1.0 == 1, 1.1 > 1
+                return BigInteger.ZERO.equals( value ) ? 0 : 1; // 1.0 == 1, 1.1 > 1
             }
 
             switch ( item.getType() )
             {
-                case INTEGER_ITEM:
-                    return value.compareTo( ( (IntegerItem) item ).value );
+                case INT_ITEM:
+                case LONG_ITEM:
+                    return 1;
+
+                case BIGINTEGER_ITEM:
+                    return value.compareTo( ( (BigIntegerItem) item ).value );
 
                 case STRING_ITEM:
                     return 1; // 1.1 > 1-sp
@@ -132,10 +267,11 @@ public class ComparableVersion
                     return 1; // 1.1 > 1-1
 
                 default:
-                    throw new RuntimeException( "invalid item: " + item.getClass() );
+                    throw new IllegalStateException( "invalid item: " + item.getClass() );
             }
         }
 
+        @Override
         public String toString()
         {
             return value.toString();
@@ -165,7 +301,7 @@ public class ComparableVersion
          */
         private static final String RELEASE_VERSION_INDEX = String.valueOf( QUALIFIERS.indexOf(
"" ) );
 
-        private String value;
+        private final String value;
 
         StringItem( String value, boolean followedByDigit )
         {
@@ -189,11 +325,13 @@ public class ComparableVersion
             this.value = ALIASES.getProperty( value , value );
         }
 
+        @Override
         public int getType()
         {
             return STRING_ITEM;
         }
 
+        @Override
         public boolean isNull()
         {
             return ( comparableQualifier( value ).compareTo( RELEASE_VERSION_INDEX ) == 0
);
@@ -219,6 +357,7 @@ public class ComparableVersion
             return i == -1 ? ( QUALIFIERS.size() + "-" + qualifier ) : String.valueOf( i
);
         }
 
+        @Override
         public int compareTo( Item item )
         {
             if ( item == null )
@@ -228,7 +367,9 @@ public class ComparableVersion
             }
             switch ( item.getType() )
             {
-                case INTEGER_ITEM:
+                case INT_ITEM:
+                case LONG_ITEM:
+                case BIGINTEGER_ITEM:
                     return -1; // 1.any < 1.1 ?
 
                 case STRING_ITEM:
@@ -238,10 +379,11 @@ public class ComparableVersion
                     return -1; // 1.any < 1-1
 
                 default:
-                    throw new RuntimeException( "invalid item: " + item.getClass() );
+                    throw new IllegalStateException( "invalid item: " + item.getClass() );
             }
         }
 
+        @Override
         public String toString()
         {
             return value;
@@ -256,11 +398,13 @@ public class ComparableVersion
         extends ArrayList<Item>
         implements Item
     {
+        @Override
         public int getType()
         {
             return LIST_ITEM;
         }
 
+        @Override
         public boolean isNull()
         {
             return ( size() == 0 );
@@ -284,6 +428,7 @@ public class ComparableVersion
             }
         }
 
+        @Override
         public int compareTo( Item item )
         {
             if ( item == null )
@@ -297,7 +442,9 @@ public class ComparableVersion
             }
             switch ( item.getType() )
             {
-                case INTEGER_ITEM:
+                case INT_ITEM:
+                case LONG_ITEM:
+                case BIGINTEGER_ITEM:
                     return -1; // 1-1 < 1.0.x
 
                 case STRING_ITEM:
@@ -324,10 +471,11 @@ public class ComparableVersion
                     return 0;
 
                 default:
-                    throw new RuntimeException( "invalid item: " + item.getClass() );
+                    throw new IllegalStateException( "invalid item: " + item.getClass() );
             }
         }
 
+        @Override
         public String toString()
         {
             StringBuilder buffer = new StringBuilder();
@@ -359,7 +507,7 @@ public class ComparableVersion
 
         ListItem list = items;
 
-        Stack<Item> stack = new Stack<>();
+        Deque<Item> stack = new ArrayDeque<>();
         stack.push( list );
 
         boolean isDigit = false;
@@ -374,7 +522,7 @@ public class ComparableVersion
             {
                 if ( i == startIndex )
                 {
-                    list.add( IntegerItem.ZERO );
+                    list.add( IntItem.ZERO );
                 }
                 else
                 {
@@ -386,7 +534,7 @@ public class ComparableVersion
             {
                 if ( i == startIndex )
                 {
-                    list.add( IntegerItem.ZERO );
+                    list.add( IntItem.ZERO );
                 }
                 else
                 {
@@ -441,14 +589,41 @@ public class ComparableVersion
 
     private static Item parseItem( boolean isDigit, String buf )
     {
-        return isDigit ? new IntegerItem( buf ) : new StringItem( buf, false );
+        if ( isDigit )
+        {
+            buf = stripLeadingZeroes( buf );
+            if ( buf.length() <= MAX_INTITEM_LENGTH )
+            {
+                // lower than 2^31
+                return new IntItem( buf );
+            }
+            else if ( buf.length() <= MAX_LONGITEM_LENGTH )
+            {
+                // lower than 2^63
+                return new LongItem( buf );
+            }
+            return new BigIntegerItem( buf );
+        }
+        return new StringItem( buf, false );
+    }
+
+    private static String stripLeadingZeroes( String buf )
+    {
+        String strippedBuf = StringUtils.stripStart( buf, "0" );
+        if ( strippedBuf.isEmpty() )
+        {
+            return "0";
+        }
+        return strippedBuf;
     }
 
+    @Override
     public int compareTo( ComparableVersion o )
     {
         return items.compareTo( o.items );
     }
 
+    @Override
     public String toString()
     {
         return value;
@@ -459,11 +634,13 @@ public class ComparableVersion
         return canonical;
     }
 
+    @Override
     public boolean equals( Object o )
     {
         return ( o instanceof ComparableVersion ) && canonical.equals( ( (ComparableVersion)
o ).canonical );
     }
 
+    @Override
     public int hashCode()
     {
         return canonical.hashCode();
diff --git a/maven-artifact/src/test/java/org/apache/maven/artifact/versioning/ComparableVersionTest.java
b/maven-artifact/src/test/java/org/apache/maven/artifact/versioning/ComparableVersionTest.java
index 875b43e..ce7df2d 100644
--- a/maven-artifact/src/test/java/org/apache/maven/artifact/versioning/ComparableVersionTest.java
+++ b/maven-artifact/src/test/java/org/apache/maven/artifact/versioning/ComparableVersionTest.java
@@ -85,6 +85,14 @@ public class ComparableVersionTest
         assertTrue( "expected " + v2 + ".equals( " + v1 + " )", c2.equals( c1 ) );
     }
 
+    private void checkVersionsArrayEqual( String[] array )
+    {
+        // compare against each other (including itself)
+        for ( int i = 0; i < array.length; ++i )
+            for ( int j = i; j < array.length; ++j )
+                checkVersionsEqual( array[i], array[j] );
+    }
+
     private void checkVersionsOrder( String v1, String v2 )
     {
         Comparable c1 = newComparable( v1 );
@@ -201,6 +209,88 @@ public class ComparableVersionTest
         checkVersionsOrder( a, c );
     }
 
+    /**
+     * Test <a href="https://jira.apache.org/jira/browse/MNG-6572">MNG-6572</a>
optimization.
+     */
+    public void testMng6572()
+    {
+        String a = "20190126.230843"; // resembles a SNAPSHOT
+        String b = "1234567890.12345"; // 10 digit number
+        String c = "123456789012345.1H.5-beta"; // 15 digit number
+        String d = "12345678901234567890.1H.5-beta"; // 20 digit number
+
+        checkVersionsOrder( a, b );
+        checkVersionsOrder( b, c );
+        checkVersionsOrder( a, c );
+        checkVersionsOrder( c, d );
+        checkVersionsOrder( b, d );
+        checkVersionsOrder( a, d );
+    }
+
+    /**
+     * Test all versions are equal when starting with many leading zeroes regardless of string
length
+     * (related to MNG-6572 optimization) 
+     */
+    public void testVersionEqualWithLeadingZeroes()
+    {
+        // versions with string lengths from 1 to 19
+        String[] arr = new String[] {
+            "0000000000000000001",
+            "000000000000000001",
+            "00000000000000001",
+            "0000000000000001",
+            "000000000000001",
+            "00000000000001",
+            "0000000000001",
+            "000000000001",
+            "00000000001",
+            "0000000001",
+            "000000001",
+            "00000001",
+            "0000001",
+            "000001",
+            "00001",
+            "0001",
+            "001",
+            "01",
+            "1"
+        };
+        
+        checkVersionsArrayEqual( arr );
+    }
+
+    /**
+     * Test all "0" versions are equal when starting with many leading zeroes regardless
of string length
+     * (related to MNG-6572 optimization) 
+     */
+    public void testVersionZeroEqualWithLeadingZeroes()
+    {
+        // versions with string lengths from 1 to 19
+        String[] arr = new String[] {
+            "0000000000000000000",
+            "000000000000000000",
+            "00000000000000000",
+            "0000000000000000",
+            "000000000000000",
+            "00000000000000",
+            "0000000000000",
+            "000000000000",
+            "00000000000",
+            "0000000000",
+            "000000000",
+            "00000000",
+            "0000000",
+            "000000",
+            "00000",
+            "0000",
+            "000",
+            "00",
+            "0"
+        };
+        
+        checkVersionsArrayEqual( arr );
+    }
+
     public void testLocaleIndependent()
     {
         Locale orig = Locale.getDefault();


Mime
View raw message