BUG-7464: Improve Map contract compliance

Add explicit precondition guards against null keys and values
and fix iterators not currectly throwing exceptions. Also make
sure entrySet().contains() and remove() operations do not throw,
but return correct results.

Change-Id: I645686112ebb3675b73349d0c3096a3901243522
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java
index acb944ede48ef34cfe918d93573c1011b252fa69..feb95393388713ae13d7137324e74e31f5dfa47b 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/TrieMap.java
@@ -15,7 +15,10 @@
  */
 package org.opendaylight.yangtools.triemap;
 
-import com.google.common.base.Preconditions;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
+import com.google.common.collect.Iterators;
 import java.io.ObjectStreamException;
 import java.io.Serializable;
 import java.util.AbstractMap;
@@ -24,6 +27,7 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Iterator;
 import java.util.List;
+import java.util.NoSuchElementException;
 import java.util.Optional;
 import java.util.Set;
 import java.util.concurrent.ConcurrentMap;
@@ -79,7 +83,7 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
     }
 
     final boolean CAS_ROOT(final Object ov, final Object nv) {
-        Preconditions.checkState(!readOnly, "Attempted to modify a read-only snapshot");
+        checkState(!readOnly, "Attempted to modify a read-only snapshot");
         return ROOT_UPDATER.compareAndSet (this, ov, nv);
     }
 
@@ -100,55 +104,50 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
         final Object r = /* READ */root;
         if (r instanceof INode) {
             return (INode<K, V>) r;
-        } else if (r instanceof RDCSS_Descriptor) {
-            return RDCSS_Complete (abort);
-        } else {
-            throw new IllegalStateException("Unhandled root " + r);
         }
+
+        checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
+        return RDCSS_Complete(abort);
     }
 
     private INode<K, V> RDCSS_Complete(final boolean abort) {
         while (true) {
-            final Object v = /* READ */root;
-            if (v instanceof INode) {
-                return (INode<K, V>) v;
+            final Object r = /* READ */root;
+            if (r instanceof INode) {
+                return (INode<K, V>) r;
             }
 
-            if (v instanceof RDCSS_Descriptor) {
-                final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
-                final INode<K, V> ov = desc.old;
-                final MainNode<K, V> exp = desc.expectedmain;
-                final INode<K, V> nv = desc.nv;
-
-                if (abort) {
-                    if (CAS_ROOT(desc, ov)) {
-                        return ov;
-                    }
+            checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
+            final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
+            final INode<K, V> ov = desc.old;
+            final MainNode<K, V> exp = desc.expectedmain;
+            final INode<K, V> nv = desc.nv;
 
-                    // Tail recursion: return RDCSS_Complete(abort);
-                    continue;
+            if (abort) {
+                if (CAS_ROOT(desc, ov)) {
+                    return ov;
                 }
 
-                final MainNode<K, V> oldmain = ov.gcasRead(this);
-                if (oldmain == exp) {
-                    if (CAS_ROOT(desc, nv)) {
-                        desc.committed = true;
-                        return nv;
-                    }
-
-                    // Tail recursion: return RDCSS_Complete(abort);
-                    continue;
-                }
+                // Tail recursion: return RDCSS_Complete(abort);
+                continue;
+            }
 
-                if (CAS_ROOT(desc, ov)) {
-                    return ov;
+            final MainNode<K, V> oldmain = ov.gcasRead(this);
+            if (oldmain == exp) {
+                if (CAS_ROOT(desc, nv)) {
+                    desc.committed = true;
+                    return nv;
                 }
 
                 // Tail recursion: return RDCSS_Complete(abort);
                 continue;
             }
 
-            throw new IllegalStateException("Unexpected root " + v);
+            if (CAS_ROOT(desc, ov)) {
+                return ov;
+            }
+
+            // Tail recursion: return RDCSS_Complete(abort);
         }
     }
 
@@ -296,59 +295,57 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
         return equiv.equivalent(k1, k2);
     }
 
-    V lookup(final K k) {
-        return (V) lookuphc(k, computeHash(k));
-    }
-
     @Override
-    public V get(final Object k) {
-        return lookup((K)k);
+    public V get(final Object key) {
+        final K k = (K) checkNotNull(key);
+        return (V) lookuphc(k, computeHash(k));
     }
 
     @Override
     public V put(final K key, final V value) {
         ensureReadWrite();
-        final int hc = computeHash(key);
-        return insertifhc (key, hc, value, null).orElse(null);
+        final K k = checkNotNull(key);
+        return insertifhc(k, computeHash(k), checkNotNull(value), null).orElse(null);
     }
 
-    void add(final K k, final V v) {
-        inserthc(k, computeHash(k), v);
+    void add(final K key, final V value) {
+        final K k = checkNotNull(key);
+        inserthc(k, computeHash(k), checkNotNull(value));
     }
 
     @Override
-    public V remove(final Object k) {
+    public V remove(final Object key) {
         ensureReadWrite();
-        final int hc = computeHash ((K)k);
-        return removehc ((K)k, (V) null, hc).orElse(null);
+        final K k = (K) checkNotNull(key);
+        return removehc(k, (V) null, computeHash(k)).orElse(null);
     }
 
     @Override
-    public V putIfAbsent(final K k, final V v) {
+    public V putIfAbsent(final K key, final V value) {
         ensureReadWrite();
-        final int hc = computeHash (k);
-        return insertifhc (k, hc, v, INode.KEY_ABSENT).orElse(null);
+        final K k = checkNotNull(key);
+        return insertifhc(k, computeHash(k), checkNotNull(value), INode.KEY_ABSENT).orElse(null);
     }
 
     @Override
-    public boolean remove(final Object k, final Object v) {
+    public boolean remove(final Object key, final Object v) {
         ensureReadWrite();
-        final int hc = computeHash ((K)k);
-        return removehc((K)k, (V)v, hc).isPresent();
+        final K k = (K) checkNotNull(key);
+        return removehc(k, (V) checkNotNull(v), computeHash(k)).isPresent();
     }
 
     @Override
-    public boolean replace(final K k, final V oldvalue, final V newvalue) {
+    public boolean replace(final K key, final V oldValue, final V newValue) {
         ensureReadWrite();
-        final int hc = computeHash (k);
-        return insertifhc (k, hc, newvalue, oldvalue).isPresent();
+        final K k = checkNotNull(key);
+        return insertifhc(k, computeHash(k), checkNotNull(newValue), checkNotNull(oldValue)).isPresent();
     }
 
     @Override
-    public V replace(final K k, final V v) {
+    public V replace(final K key, final V value) {
         ensureReadWrite();
-        final int hc = computeHash (k);
-        return insertifhc (k, hc, v, INode.KEY_PRESENT).orElse(null);
+        final K k = checkNotNull(key);
+        return insertifhc (k, computeHash(k), checkNotNull(value), INode.KEY_PRESENT).orElse(null);
     }
 
     /***
@@ -387,7 +384,7 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
 
     @Override
     public boolean containsKey(final Object key) {
-        return lookup((K) key) != null;
+        return get(key) != null;
     }
 
     @Override
@@ -471,32 +468,31 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
 
 
         @Override
-        public boolean hasNext () {
+        public boolean hasNext() {
             return (current != null) || (subiter != null);
         }
 
         @Override
-        public Entry<K, V> next () {
-            if (hasNext ()) {
-                Entry<K, V> r = null;
-                if (subiter != null) {
-                    r = subiter.next ();
-                    checkSubiter ();
-                } else {
-                    r = current.kvPair ();
-                    advance ();
-                }
+        public Entry<K, V> next() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
 
-                lastReturned = r;
-                if (r != null) {
-                    final Entry<K, V> rr = r;
-                    return nextEntry(rr);
-                }
-                return r;
+            Entry<K, V> r = null;
+            if (subiter != null) {
+                r = subiter.next ();
+                checkSubiter ();
             } else {
-                // return Iterator.empty ().next ();
-                return null;
+                r = current.kvPair ();
+                advance ();
             }
+
+            lastReturned = r;
+            if (r != null) {
+                final Entry<K, V> rr = r;
+                return nextEntry(rr);
+            }
+            return r;
         }
 
         Entry<K, V> nextEntry(final Entry<K, V> rr) {
@@ -510,7 +506,7 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
 
                 @Override
                 public V getValue () {
-                    return (updated == null)?rr.getValue (): updated;
+                    return (updated == null) ? rr.getValue (): updated;
                 }
 
                 @Override
@@ -638,7 +634,7 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
         private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
             ArrayList<Entry<K, V>> list = new ArrayList<> ();
             while (it.hasNext ()) {
-                list.add (it.next ());
+                list.add (it.next());
             }
             return list;
         }
@@ -652,55 +648,57 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
         }
 
         @Override
-        public void remove () {
-            if (lastReturned != null) {
-                ct.remove (lastReturned.getKey ());
-                lastReturned = null;
-            } else {
-                throw new IllegalStateException();
-            }
+        public void remove() {
+            checkState(lastReturned != null);
+            ct.remove(lastReturned.getKey());
+            lastReturned = null;
         }
-
     }
 
     /***
      * Support for EntrySet operations required by the Map interface
      */
     private final class EntrySet extends AbstractSet<Entry<K, V>> {
-
         @Override
-        public Iterator<Entry<K, V>> iterator () {
+        public Iterator<Entry<K, V>> iterator() {
             return TrieMap.this.iterator ();
         }
 
         @Override
-        public final boolean contains (final Object o) {
+        public final boolean contains(final Object o) {
             if (!(o instanceof Entry)) {
                 return false;
             }
-            final Entry<K, V> e = (Entry<K, V>) o;
-            final K k = e.getKey ();
-            final V v = lookup (k);
-            return v != null;
+
+            final Entry<?, ?> e = (Entry<?, ?>) o;
+            if (e.getKey() == null) {
+                return false;
+            }
+            final V v = get(e.getKey());
+            return v != null && v.equals(e.getValue());
         }
 
         @Override
-        public final boolean remove (final Object o) {
+        public final boolean remove(final Object o) {
             if (!(o instanceof Entry)) {
                 return false;
             }
-            final Entry<K, V> e = (Entry<K, V>) o;
-            final K k = e.getKey();
-            return null != TrieMap.this.remove(k);
+            final Entry<?, ?> e = (Entry<K, V>) o;
+            final Object key = e.getKey();
+            if (key == null) {
+                return false;
+            }
+            final Object value = e.getValue();
+            if (value == null) {
+                return false;
+            }
+
+            return TrieMap.this.remove(key, value);
         }
 
         @Override
         public final int size () {
-            int size = 0;
-            for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
-                size++;
-            }
-            return size;
+            return Iterators.size(iterator());
         }
 
         @Override
@@ -708,5 +706,4 @@ public final class TrieMap<K, V> extends AbstractMap<K, V> implements Concurrent
             TrieMap.this.clear ();
         }
     }
-
 }

diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java
index 4f3cda74fb6d63ca143a6f27124488f27d25a5a8..98e7e27fef1af155ff359b52946908b3e839783d 100644 (file)
--- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java
+++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestDelete.java
@@ -22,6 +22,35 @@ import static org.junit.Assert.assertTrue;
 import org.junit.Test;
 
 public class TestDelete {
+    @Test(expected = NullPointerException.class)
+    public void testNullSimple() {
+        new TrieMap<>().remove(null);
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void testNullKey() {
+        new TrieMap<>().remove(null, "");
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void testNullValue() {
+        new TrieMap<>().remove("", null);
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void testNullBoth() {
+        new TrieMap<>().remove(null, null);
+    }
+
+    @Test
+    public void testClear() {
+        final TrieMap<Integer, Integer> bt = new TrieMap<>();
+        bt.put(1, 1);
+        bt.clear();
+        assertTrue(bt.isEmpty());
+        assertEquals(0, bt.size());
+    }
+
     @Test
     public void testDelete () {
         final TrieMap<Integer, Integer> bt = new TrieMap<> ();

diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java
index 81f66e869dd6b319421d31efd9890575515f8d5f..bf3813b7f7a20ad034050f6c50f3b990dda31435 100644 (file)
--- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java
+++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestInsert.java
@@ -38,4 +38,19 @@ public class TestInsert {
 
         bt.toString();
     }
+
+    @Test(expected = NullPointerException.class)
+    public void testNullKey() {
+        new TrieMap<>().put(null, "");
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void testNullValue() {
+        new TrieMap<>().put("", null);
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void testNullBoth() {
+        new TrieMap<>().put(null, null);
+    }
 }

diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java
index f697b1d1cc142a7f06b6e73312a7d06e1126ce6b..7d8e54901440068f6f66944a40efd756795f3076 100644 (file)
--- a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java
+++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestMapIterator.java
@@ -25,6 +25,7 @@ import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Map.Entry;
+import java.util.NoSuchElementException;
 import java.util.Random;
 import java.util.Set;
 import org.junit.Test;
@@ -75,4 +76,24 @@ public class TestMapIterator {
             assertTrue(bt.isEmpty ());
         }
     }
+
+    private static void failAdvance(final Iterator<?> it) {
+        assertFalse(it.hasNext());
+        it.next();
+    }
+
+    @Test(expected = NoSuchElementException.class)
+    public void testEmptyIterator() {
+        failAdvance(new TrieMap<>().iterator());
+    }
+
+    @Test(expected = NoSuchElementException.class)
+    public void testEmptyReadOnlyIterator() {
+        failAdvance(new TrieMap<>().readOnlyIterator());
+    }
+
+    @Test(expected = NoSuchElementException.class)
+    public void testEmptyReadOnlySnapshotIterator() {
+        failAdvance(new TrieMap<>().readOnlySnapshot().iterator());
+    }
 }