You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@maven.apache.org by hb...@apache.org on 2019/03/17 10:02:33 UTC
[maven] 01/02: [MNG-6572] use int or long instead of BigIntegers
for little numbers in ComparableVersion
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 <be...@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();