You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2023/08/28 14:16:47 UTC
[sis] 02/02: Use deterministic dimension order for user-specified units. This commit fixes a random test failure where the order depended on which tests were executed first, because the dimension order of the first cached unit was the order used for other compatible units.
This is an automated email from the ASF dual-hosted git repository.
desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git
commit dd3ddafcb2200935158aa3d217b704df93d32ace
Author: Martin Desruisseaux <ma...@geomatys.com>
AuthorDate: Mon Aug 28 16:06:11 2023 +0200
Use deterministic dimension order for user-specified units.
This commit fixes a random test failure where the order depended on which tests were executed first,
because the dimension order of the first cached unit was the order used for other compatible units.
---
.../main/org/apache/sis/measure/UnitDimension.java | 73 +++++++++--
.../main/org/apache/sis/measure/UnitRegistry.java | 55 +++++++-
.../org/apache/sis/util/collection/WeakEntry.java | 14 +-
.../sis/util/collection/WeakValueHashMap.java | 145 ++++++++++++---------
.../org/apache/sis/measure/UnitFormatTest.java | 4 +-
5 files changed, 215 insertions(+), 76 deletions(-)
diff --git a/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitDimension.java b/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitDimension.java
index 49e03937a9..93e339f1f5 100644
--- a/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitDimension.java
+++ b/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitDimension.java
@@ -242,7 +242,7 @@ final class UnitDimension implements Dimension, Serializable {
* is safe if we use the `components` map as a read-only map (no put operation allowed).
*/
@SuppressWarnings("unchecked")
- Map<Dimension,Integer> components = (Map<Dimension,Integer>) dimension.getBaseDimensions();
+ final var components = (Map<Dimension,Integer>) dimension.getBaseDimensions();
if (components == null) {
return Map.of(dimension, new Fraction(1,1));
}
@@ -273,6 +273,7 @@ final class UnitDimension implements Dimension, Serializable {
/**
* Returns the product or the quotient of this dimension with the specified one.
+ * This method may return a cached instance.
*
* @param other the dimension by which to multiply or divide this dimension.
* @param divide {@code false} for a multiplication, {@code true} for a division.
@@ -350,17 +351,49 @@ final class UnitDimension implements Dimension, Serializable {
}
if (other instanceof UnitDimension) {
final UnitDimension that = (UnitDimension) other;
- if (symbol == that.symbol) {
- /*
- * Do not compare `components` if `symbols` is non-zero because in such case
- * the components map contains `this`, which would cause an infinite loop.
- */
- return (symbol != 0) || components.equals(that.components);
+ if ((symbol | that.symbol) != 0) {
+ return symbol == that.symbol;
}
+ /*
+ * Do not compare `components` if `symbols` is non-zero because in such case
+ * the components map contains `this`, which would cause an infinite loop.
+ */
+ return components.equals(that.components);
}
return false;
}
+ /**
+ * Compares this dimension with the given object for equality, taking element order in account.
+ *
+ * @param that the other object to compare with.
+ * @return whether the two objects are equal with elements in the same order.
+ */
+ final boolean equalsOrdered(final UnitDimension that) {
+ if ((symbol | that.symbol) != 0) {
+ return symbol == that.symbol;
+ }
+ return equalsOrdered(components, that.components);
+ }
+
+ /**
+ * Compares the given map in a way that take order in account.
+ *
+ * @param m1 the first map to compare.
+ * @param m2 the second map to compare.
+ * @return whether the two maps contain the same element in the same order.
+ */
+ static boolean equalsOrdered(final Map<?,?> m1, final Map<?,?> m2) {
+ final var i1 = m1.entrySet().iterator();
+ final var i2 = m2.entrySet().iterator();
+ while (i1.hasNext()) {
+ if (!(i2.hasNext() && i1.next().equals(i2.next()))) {
+ return false;
+ }
+ }
+ return !i2.hasNext();
+ }
+
/**
* Returns a hash code value for this dimension.
*/
@@ -370,7 +403,31 @@ final class UnitDimension implements Dimension, Serializable {
* Do not use `components` in hash code calculation if `symbols` is non-zero
* beause in such case the map contains `this`, which would cause an infinite loop.
*/
- return (symbol != 0) ? symbol ^ (int) serialVersionUID : components.hashCode();
+ return (symbol != 0 ? symbol : components.hashCode()) ^ (int) serialVersionUID;
+ }
+
+ /**
+ * {@return returns a hash code value which takes element order in account}.
+ * If the map is empty or contains only one element, then the returned value
+ * is the same as {@link #hashCode()}.
+ */
+ final int hashCodeOrdered() {
+ int code = symbol;
+ if (code == 0) code = hashCodeOrdered(components);
+ return code ^ (int) serialVersionUID;
+ }
+
+ /**
+ * {@return an hash code value of the given map computed in an order-sensitive was}.
+ *
+ * @param components the map for which to compute hash code.
+ */
+ static int hashCodeOrdered(final Map<?,?> components) {
+ int code = 0;
+ for (final Map.Entry<?,?> entry : components.entrySet()) {
+ code = code * 31 + entry.hashCode();
+ }
+ return code;
}
/**
diff --git a/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitRegistry.java b/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitRegistry.java
index f410a6ba00..0d1dc55919 100644
--- a/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitRegistry.java
+++ b/endorsed/src/org.apache.sis.util/main/org/apache/sis/measure/UnitRegistry.java
@@ -98,6 +98,11 @@ final class UnitRegistry implements SystemOfUnits, Serializable {
* <tr><td>{@link String}</td> <td>{@link AbstractUnit}</td> <td>Key is the unit symbol.</td></tr>
* <tr><td>{@link Short}</td> <td>{@link AbstractUnit}</td> <td>Key is the EPSG code.</td></tr>
* </table>
+ *
+ * <h4>Dimension order</h4>
+ * The search for an existing unit in this map is <strong>not</strong> sensitive to dimension order.
+ * N⋅m is considered equivalent to m⋅N, and both of them are associated to the symbol "J" (Joule).
+ * We ignore dimension order because it has no incidence on the unit symbol shown to user.
*/
private static final Map<Object,Object> HARD_CODED = new HashMap<>(256);
@@ -106,12 +111,56 @@ final class UnitRegistry implements SystemOfUnits, Serializable {
* Values are stored by weak references and garbage collected when no longer used.
* Key and value types are the same than the one described in {@link #HARD_CODED}.
*
+ * <h4>Dimension order</h4>
+ * Contrarily to {@link #HARD_CODED}, the user-specified map of units is sensitive to dimension order.
+ * kg∕(m⋅s³) is not considered the same as kg∕(s³⋅m) for formatting purpose (but still considered the
+ * same for unit conversions purpose). This distinction is applied because the unit may have no label
+ * associated to it. The only label may be the list of dimensions, so we try to show them in the same
+ * order as specified by the users when they constructed their units.
+ *
* <h4>Implementation note</h4>
* We separate hard-coded values from user-defined values because the amount of hard-coded values is relatively
- * large, using weak references for them is useless, and most applications will not define any custom values.
- * This map will typically stay empty.
+ * large, using weak references for them is useless, and most applications will not define any custom values so
+ * the user-defined map will typically stay empty. This separation avoids synchronization of hard-coded values.
+ * Furthermore the two maps have a different policy on whether to consider dimension order as significant.
+ */
+ private static final WeakValueHashMap<Object,Object> USER_DEFINED = new WeakValueHashMap<>(Object.class,
+ UnitRegistry::hashCodeOrdered,
+ UnitRegistry::equalsOrdered);
+
+ /**
+ * Returns a hash code value for the specified key, taking dimension order in account.
+ * This is used for the policy of keys in the {@link #USER_DEFINED} map.
+ *
+ * @param key a key of one of the types defined in {@link #HARD_CODED}.
+ * @return hash code value for the given key. Never null.
*/
- private static final WeakValueHashMap<Object,Object> USER_DEFINED = new WeakValueHashMap<>(Object.class);
+ private static int hashCodeOrdered(final Object key) {
+ if (key instanceof UnitDimension) return ((UnitDimension) key).hashCodeOrdered();
+ if (key instanceof Map<?,?>) return UnitDimension.hashCodeOrdered((Map<?,?>) key);
+ return key.hashCode();
+ }
+
+ /**
+ * Compares the given keys, taking dimension order in account.
+ * Shall be consistent with {@link #hashCode(Object)}.
+ *
+ * @param key a key of one of the types defined in {@link #HARD_CODED}.
+ * @param object an object to compare with the key. Never null.
+ * @return whether the given object are equal.
+ */
+ private static boolean equalsOrdered(final Object key, final Object other) {
+ if (key instanceof UnitDimension) {
+ if (other instanceof UnitDimension) {
+ return ((UnitDimension) key).equalsOrdered((UnitDimension) other);
+ }
+ } else if (key instanceof Map<?,?>) {
+ if (other instanceof Map<?,?>) {
+ return UnitDimension.equalsOrdered((Map<?,?>) key, (Map<?,?>) other);
+ }
+ }
+ return key.equals(other);
+ }
/**
* Adds the given {@code components}, {@code dim} pair in the map of hard-coded values.
diff --git a/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakEntry.java b/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakEntry.java
index a58665f063..fde9942372 100644
--- a/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakEntry.java
+++ b/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakEntry.java
@@ -34,7 +34,7 @@ import org.apache.sis.math.MathFunctions;
* from the enclosing collection.
*
* @author Martin Desruisseaux (MPO, IRD, Geomatys)
- * @version 0.3
+ * @version 1.4
*
* @param <E> the type of elements in the collection.
*
@@ -204,4 +204,16 @@ abstract class WeakEntry<E> extends WeakReference<E> implements Disposable {
static int upperCapacityThreshold(final int capacity) {
return capacity - (capacity >>> 2);
}
+
+ /**
+ * Compares the given objects using the {@code ==} operator.
+ * This is a convenience method for use as lambda function.
+ *
+ * @param o1 the first object to compare.
+ * @param o2 the second object to compare.
+ * @return whether the two objects are the same instance.
+ */
+ static boolean identityEqual(final Object o1, final Object o2) {
+ return o1 == o2;
+ }
}
diff --git a/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakValueHashMap.java b/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakValueHashMap.java
index 463b93639b..5ffff63ca2 100644
--- a/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakValueHashMap.java
+++ b/endorsed/src/org.apache.sis.util/main/org/apache/sis/util/collection/WeakValueHashMap.java
@@ -24,7 +24,9 @@ import java.util.Iterator;
import java.util.Objects;
import java.util.Arrays;
import java.util.function.Function;
+import java.util.function.ToIntFunction;
import java.lang.ref.WeakReference;
+import java.util.function.BiPredicate;
import org.apache.sis.util.Debug;
import org.apache.sis.util.ArraysExt;
import org.apache.sis.util.Utilities;
@@ -86,21 +88,25 @@ import static org.apache.sis.util.collection.WeakEntry.*;
*/
public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
/**
- * Comparison mode for key objects. The standard mode is {@code EQUALS}, which means that keys are compared
- * using their {@link Object#equals(Object)} method. But {@code WeakValueHashMap} will automatically select
- * {@code DEEP_EQUALS} if there is a chance that some keys are arrays. In the latter case, comparisons will
- * be done by the more costly {@link Objects#deepEquals(Object, Object)} method instead.
+ * The function to invoke for computing hash codes.
+ * This is usually one of the following:
*
- * <p>The {@code IDENTITY} mode is rarely used, and is selected only if the user explicitly asks for this mode
- * at construction time. This mode is provided because reference-equality semantic is sometimes required, and
- * hard to simulate if not supported natively by the hash map. See {@link java.util.IdentityHashMap} javadoc
- * for some examples of cases where reference-equality semantic is useful.</p>
+ * <ul>
+ * <li>{@link Objects#hashCode(Object)} for the {@link java.util.HashMap} behavior.</li>
+ * <li>{@link System#identityHashCode(Object)} for the {@link java.util.IdentityHashMap} behavior.</li>
+ * <li>{@link Utilities#deepHashCode(Object)} for a map working with arrays.</li>
+ * </ul>
*
- * @see #comparisonMode
- * @see #keyEquals(Object, Object)
- * @see #keyHashCode(Object)
+ * The argument given in calls to {@code applyAsInt(Object)} will never be null.
*/
- private static final byte IDENTITY = 0, EQUALS = 1, DEEP_EQUALS = 2;
+ private final ToIntFunction<Object> hashFunction;
+
+ /**
+ * The function to invoke for comparing two objects.
+ * Shall be consistent with {@link #hashFunction}.
+ * The arguments given in calls to {@code test(Object, Object)} will never be null.
+ */
+ private final BiPredicate<Object,Object> comparator;
/**
* An entry in the {@link WeakValueHashMap}. This is a weak reference
@@ -108,7 +114,7 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
*/
private final class Entry extends WeakEntry<V> implements Map.Entry<K,V> {
/**
- * The key.
+ * The key. Shall never be null.
*/
final K key;
@@ -168,7 +174,7 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
public boolean equals(final Object other) {
if (other instanceof Map.Entry<?,?>) {
final Map.Entry<?,?> that = (Map.Entry<?,?>) other;
- return keyEquals(key, that.getKey()) && Objects.equals(get(), that.getValue());
+ return comparator.test(key, that.getKey()) && Objects.equals(get(), that.getValue());
}
return false;
}
@@ -179,7 +185,7 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
*/
@Override
public int hashCode() {
- int code = keyHashCode(key);
+ int code = hashFunction.applyAsInt(key);
final V val = get();
if (val != null) {
code ^= val.hashCode();
@@ -204,17 +210,6 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
*/
private final Class<K> keyType;
- /**
- * Whether keys shall be compared by reference-equality ({@link #IDENTITY}), by shallow object-equality
- * ({@link #EQUALS}) or by deep object-equality ({@link #DEEP_EQUALS}). The {@code DEEP_EQUALS} mode is
- * selected only if the keys in this map may be arrays. If the keys cannot be arrays, then we select the
- * {@code EQUALS} mode for avoiding calls to the costly {@link Objects#deepEquals(Object, Object)} method.
- *
- * @see #keyEquals(Object, Object)
- * @see #keyHashCode(Object)
- */
- private final byte comparisonMode;
-
/**
* The set of entries, created only when first needed.
*/
@@ -253,9 +248,64 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
*/
@SuppressWarnings({"rawtypes", "unchecked"}) // Generic array creation.
public WeakValueHashMap(final Class<K> keyType, final boolean identity) {
- this.keyType = keyType;
- comparisonMode = identity ? IDENTITY :
- (keyType.isArray() || keyType.equals(Object.class)) ? DEEP_EQUALS : EQUALS;
+ this.keyType = Objects.requireNonNull(keyType);
+ if (identity) {
+ hashFunction = System::identityHashCode;
+ comparator = WeakEntry::identityEqual;
+ } else if (keyType.isArray()) {
+ hashFunction = Utilities::deepHashCode;
+ comparator = Objects::deepEquals;
+ } else {
+ hashFunction = Object::hashCode;
+ comparator = Object::equals;
+ }
+ lastTimeNormalCapacity = System.nanoTime();
+ table = new WeakValueHashMap.Entry[MIN_CAPACITY];
+ }
+
+ /**
+ * Creates a new {@code WeakValueHashMap} using the given functions for computing hash code and equality.
+ * Commonly used functions are:
+ *
+ * <table class="sis">
+ * <caption>Frequently used hash and comparison functions</caption>
+ * <tr>
+ * <th>Desired behavior</th>
+ * <th>Hash function</th>
+ * <th>Comparator</th>
+ * </tr><tr>
+ * <td>Standard (like {@link java.util.HashMap})</td>
+ * <td>{@link Object#hashCode()}</td>
+ * <td>{@link Object#equals(Object)}</td>
+ * </tr><tr>
+ * <td>Robust to arrays</td>
+ * <td>{@link Utilities#deepHashCode(Object)}</td>
+ * <td>{@link Objects#deepEquals(Object, Object)}</td>
+ * </tr><tr>
+ * <td>Identity (like {@link java.util.IdentityHashMap})</td>
+ * <td>{@link System#identityHashCode()}</td>
+ * <td>{@code (o1,o2) -> o1 == o2}</td>
+ * </tr>
+ * </table>
+ *
+ * The functions do not need to be null-safe. {@code WeakValueHashMap} will never invoke
+ * {@link ToIntFunction#applyAsInt(Object)} or {@link BiPredicate#test(Object, Object)}
+ * with null arguments.
+ *
+ * @param keyType the type of keys in the map.
+ * @param hashFunction the function to invoke for computing hash codes.
+ * @param comparator the function to invoke for comparing two objects.
+ *
+ * @since 1.4
+ */
+ @SuppressWarnings({"rawtypes", "unchecked"}) // Generic array creation.
+ public WeakValueHashMap(final Class<K> keyType,
+ final ToIntFunction<Object> hashFunction,
+ final BiPredicate<Object,Object> comparator)
+ {
+ this.keyType = Objects.requireNonNull(keyType);
+ this.hashFunction = Objects.requireNonNull(hashFunction);
+ this.comparator = Objects.requireNonNull(comparator);
lastTimeNormalCapacity = System.nanoTime();
table = new WeakValueHashMap.Entry[MIN_CAPACITY];
}
@@ -312,35 +362,6 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
return count;
}
- /**
- * Returns the hash code value for the given key.
- *
- * @param key the key (cannot be null).
- */
- private int keyHashCode(final Object key) {
- switch (comparisonMode) {
- case IDENTITY: return System.identityHashCode(key);
- case EQUALS: return key.hashCode();
- case DEEP_EQUALS: return Utilities.deepHashCode(key);
- default: throw new AssertionError(comparisonMode);
- }
- }
-
- /**
- * Returns {@code true} if the two given keys are equal.
- *
- * @param k1 the first key (cannot be null).
- * @paral k2 the second key.
- */
- private boolean keyEquals(final Object k1, final Object k2) {
- switch (comparisonMode) {
- case IDENTITY: return k1 == k2;
- case EQUALS: return k1.equals(k2);
- case DEEP_EQUALS: return Objects.deepEquals(k1, k2);
- default: throw new AssertionError(comparisonMode);
- }
- }
-
/**
* Locates the entry for the given key and, if present, invokes the given getter method.
*
@@ -355,9 +376,9 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
assert isValid();
if (key != null) {
final Entry[] table = this.table;
- final int index = (keyHashCode(key) & HASH_MASK) % table.length;
+ final int index = (hashFunction.applyAsInt(key) & HASH_MASK) % table.length;
for (Entry e = table[index]; e != null; e = (Entry) e.next) {
- if (keyEquals(key, e.key)) {
+ if (comparator.test(key, e.key)) {
return getter.apply(e);
}
}
@@ -478,10 +499,10 @@ public class WeakValueHashMap<K,V> extends AbstractMap<K,V> {
*/
V oldValue = null;
Entry[] table = this.table;
- final int hash = keyHashCode(key) & HASH_MASK;
+ final int hash = hashFunction.applyAsInt(key) & HASH_MASK;
int index = hash % table.length;
for (Entry e = table[index]; e != null; e = (Entry) e.next) {
- if (keyEquals(key, e.key)) {
+ if (comparator.test(key, e.key)) {
oldValue = e.get();
if (condition != null && !condition.equals(oldValue)) {
return oldValue;
diff --git a/endorsed/src/org.apache.sis.util/test/org/apache/sis/measure/UnitFormatTest.java b/endorsed/src/org.apache.sis.util/test/org/apache/sis/measure/UnitFormatTest.java
index db7fa86b24..c2a42f2552 100644
--- a/endorsed/src/org.apache.sis.util/test/org/apache/sis/measure/UnitFormatTest.java
+++ b/endorsed/src/org.apache.sis.util/test/org/apache/sis/measure/UnitFormatTest.java
@@ -720,7 +720,7 @@ public final class UnitFormatTest extends TestCase {
roundtrip(f, "(m2.s.sr)-1", "1∕(m²⋅s)"); // Too aggressive simplification bug (SIS-378)
roundtrip(f, "(kg.m-3).(m.s-1)", "kg∕(m²⋅s)"); // Too aggressive simplification bug (SIS-378)
roundtrip(f, "cm/day", "cm∕d");
- roundtrip(f, "W.m-2.nm-1", "10⁹⋅kg∕(m⋅s³)"); // Too aggressive simplification bug (SIS-378)
+ roundtrip(f, "W.m-2.nm-1", "10⁹⋅kg∕(s³⋅m)"); // Too aggressive simplification bug (SIS-378)
}
/**
@@ -763,7 +763,7 @@ public final class UnitFormatTest extends TestCase {
roundtrip(f, "W.m-3.sr-1", "W∕m³");
roundtrip(f, "m3.s-1.m-1", "m²∕s");
roundtrip(f, "(kg.m-3)*(m.s-1)", "kg∕(m²⋅s)");
- roundtrip(f, "W.m-2.nm-1", "10⁹⋅kg∕(m⋅s³)");
+ roundtrip(f, "W.m-2.nm-1", "10⁹⋅kg∕(s³⋅m)");
}
/**