Merge: Safe collection access

A proposition to solve an old API issue related to covariance in collections (and fix #1353)

This PR updates the signatures of access methods in collections: `has`, `[]` and anything related that takes an `E` or a `K` in read-collections.
This make these classes covariant-safe.

Previously, the signature was to strictly accepts the bound, thus making the code unsafe but has the advantage to provide static hints

~~~nit
assert [1,2,3].has("Hello") # static error, expected int got string
~~~

But this behavior had issues because:

* unsafe code, but it is not because Nit *can* be unsafe that Nit *should* be unsafe.
* a perfect semantic answer is possible, eq returning false in the previous example. thus the existing behavior is not POLA

Because the philosophy of Nit is that static types should help the programmer without being annoying, this PR lift the constraint on parameters of all read access methods.

The semantic is now more aligned with the one of dynamically typed language where the behavior is decided by messages and not by the types of things.

This especially allows to use collections of thing when `==` does not implies the equality of static types (ex subclasses of Sequence).

~~~nit
var a = [1,2,3]
var l = new List[Int].from(a)
assert a == l # by the law of Sequence

var aa = [a]
assert aa.has(l) # before the PR, error; with the PR, true

var ma = new Map[Array[Int],String]
ma[a] = "hello"
assert ma.has_key(l) # before the PR, error; with the PR, true
~~~

Pull-Request: #1355
Reviewed-by: Alexis Laferrière <alexis.laf@xymus.net>
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
Reviewed-by: Alexandre Terrasa <alexandre@moz-code.org>

diff --git a/lib/counter.nit b/lib/counter.nit
index 6d5729d..befce9c 100644 (file)
--- a/lib/counter.nit
+++ b/lib/counter.nit
@@ -53,14 +53,14 @@ class Counter[E]
        redef fun iterator do return map.iterator
 
        # The number of counted occurrences of `e`
-       redef fun [](e: E): Int
+       redef fun [](e)
        do
                var map = self.map
                if map.has_key(e) then return map[e]
                return 0
        end
 
-       redef fun []=(e: E, value: Int)
+       redef fun []=(e, value)
        do
                sum -= self[e]
                self.map[e] = value

diff --git a/lib/dummy_array.nit b/lib/dummy_array.nit
index 9061e53..85440b4 100644 (file)
--- a/lib/dummy_array.nit
+++ b/lib/dummy_array.nit
@@ -28,9 +28,10 @@ class DummyArray
                _length = l + 1
        end
 
-       redef fun remove(value: Int)
+       redef fun remove(value)
        do
                assert not is_empty
+               if not value isa Int then return
                var l = _length
                if l > 1 then
                        var last = _values[l - 1]
@@ -41,8 +42,9 @@ class DummyArray
                _length = l - 1
        end
 
-       redef fun has(value: Int): Bool
+       redef fun has(value)
        do
+               if not value isa Int then return false
                assert value < _capacity
                var pos = _keys[value]
                if pos < _length then

diff --git a/lib/neo4j/graph/graph.nit b/lib/neo4j/graph/graph.nit
index 39063f2..2ffa800 100644 (file)
--- a/lib/neo4j/graph/graph.nit
+++ b/lib/neo4j/graph/graph.nit
@@ -133,7 +133,7 @@ abstract class NeoNodeCollection
                for node in self do remove_node(node)
        end
 
-       redef fun remove(node: NeoNode) do
+       redef fun remove(node) do
                for n in self do
                        if node == n then
                                remove_node(n)
@@ -142,7 +142,7 @@ abstract class NeoNodeCollection
                end
        end
 
-       redef fun remove_all(node: NeoNode) do
+       redef fun remove_all(node) do
                for n in self do
                        if node == n then remove_node(n)
                end

diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit
index 2f7e454..0dec265 100644 (file)
--- a/lib/standard/collection/abstract_collection.nit
+++ b/lib/standard/collection/abstract_collection.nit
@@ -92,7 +92,7 @@ interface Collection[E]
        #     assert [1,2,3].has(9)    == false
        #     assert [1..5[.has(2)     == true
        #     assert [1..5[.has(9)     == false
-       fun has(item: E): Bool
+       fun has(item: nullable Object): Bool
        do
                for i in self do if i == item then return true
                return false
@@ -109,7 +109,7 @@ interface Collection[E]
        #     assert [3..3[.has_only(1)          == true # empty collection
        #
        # ENSURE `is_empty implies result == true`
-       fun has_only(item: E): Bool
+       fun has_only(item: nullable Object): Bool
        do
                for i in self do if i != item then return false
                return true
@@ -119,7 +119,7 @@ interface Collection[E]
        # Comparisons are done with ==
        #
        #     assert [10,20,10].count(10)         == 2
-       fun count(item: E): Int
+       fun count(item: nullable Object): Int
        do
                var nb = 0
                for i in self do if i == item then nb += 1
@@ -147,7 +147,7 @@ interface Collection[E]
        #
        # Note that the default implementation is general and correct for any lawful Collections.
        # It is memory-efficient but relies on `has` so may be CPU-inefficient for some kind of collections.
-       fun has_all(other: Collection[E]): Bool
+       fun has_all(other: Collection[nullable Object]): Bool
        do
                for x in other do if not has(x) then return false
                return true
@@ -171,7 +171,7 @@ interface Collection[E]
        #
        # Note that the default implementation is general and correct for any lawful Collections.
        # It is memory-efficient but relies on `count` so may be CPU-inefficient for some kind of collections.
-       fun has_exactly(other: Collection[E]): Bool
+       fun has_exactly(other: Collection[nullable Object]): Bool
        do
                if length != other.length then return false
                for e in self do if self.count(e) != other.count(e) then return false
@@ -267,19 +267,19 @@ interface RemovableCollection[E]
        # ENSURE `is_empty`
        fun clear is abstract
 
-       # Remove an occucence of `item`
+       # Remove an occurrence of `item`
        #
        #     var a = [1,2,3,1,2,3]
        #     a.remove 2
        #     assert a == [1,3,1,2,3]
-       fun remove(item: E) is abstract
+       fun remove(item: nullable Object) is abstract
 
-       # Remove all occurences of `item`
+       # Remove all occurrences of `item`
        #
        #     var a = [1,2,3,1,2,3]
        #     a.remove_all 2
        #     assert a == [1,3,1,3]
-       fun remove_all(item: E) do while has(item) do remove(item)
+       fun remove_all(item: nullable Object) do while has(item) do remove(item)
 end
 
 # Items can be added to these collections.
@@ -345,7 +345,7 @@ interface Set[E]
        # Equality is defined on set and means that each set contains the same elements
        redef fun ==(other)
        do
-               if not other isa Set[Object] then return false
+               if not other isa Set[nullable Object] then return false
                if other.length != length then return false
                return has_all(other)
        end
@@ -396,7 +396,7 @@ interface MapRead[K, V]
        #
        # If the key is not in the map, `provide_default_value` is called (that aborts by default)
        # See `get_or_null` and `get_or_default` for safe variations.
-       fun [](key: K): V is abstract
+       fun [](key: nullable Object): V is abstract
 
        # Get the item at `key` or null if `key` is not in the map.
        #
@@ -406,7 +406,7 @@ interface MapRead[K, V]
        #     assert x.get_or_null("five") == null
        #
        # Note: use `has_key` and `[]` if you need the distinction between a key associated with null, and no key.
-       fun get_or_null(key: K): nullable V
+       fun get_or_null(key: nullable Object): nullable V
        do
                if has_key(key) then return self[key]
                return null
@@ -419,7 +419,7 @@ interface MapRead[K, V]
        #     assert x.get_or_default("four", 40) == 4
        #     assert x.get_or_default("five", 50) == 50
        #
-       fun get_or_default(key: K, default: V): V
+       fun get_or_default(key: nullable Object, default: V): V
        do
                if has_key(key) then return self[key]
                return default
@@ -433,7 +433,7 @@ interface MapRead[K, V]
        #     assert x.has_key("five") == false
        #
        # By default it is a synonymous to `keys.has` but could be redefined with a direct implementation.
-       fun has_key(key: K): Bool do return self.keys.has(key)
+       fun has_key(key: nullable Object): Bool do return self.keys.has(key)
 
        # Get a new iterator on the map.
        fun iterator: MapIterator[K, V] is abstract
@@ -481,7 +481,7 @@ interface MapRead[K, V]
        #
        # Note: the value is returned *as is*, implementations may want to store the value in the map before returning it
        # @toimplement
-       protected fun provide_default_value(key: K): V do abort
+       protected fun provide_default_value(key: nullable Object): V do abort
 
        # Does `self` and `other` have the same keys associated with the same values?
        #
@@ -716,7 +716,7 @@ interface SequenceRead[E]
        #     var a = [10,20,30,10,20,30]
        #     assert a.index_of(20)   == 1
        #     assert a.index_of(40)   == -1
-       fun index_of(item: E): Int do return index_of_from(item, 0)
+       fun index_of(item: nullable Object): Int do return index_of_from(item, 0)
 
        # The index of the last occurrence of `item`.
        # Return -1 if `item` is not found.
@@ -725,7 +725,7 @@ interface SequenceRead[E]
        #     var a = [10,20,30,10,20,30]
        #     assert a.last_index_of(20)   == 4
        #     assert a.last_index_of(40)   == -1
-       fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
+       fun last_index_of(item: nullable Object): Int do return last_index_of_from(item, length-1)
 
        # The index of the first occurrence of `item`, starting from pos.
        # Return -1 if `item` is not found.
@@ -735,7 +735,7 @@ interface SequenceRead[E]
        #     assert a.index_of_from(20, 3)   == 4
        #     assert a.index_of_from(20, 4)   == 4
        #     assert a.index_of_from(20, 5)   == -1
-       fun index_of_from(item: E, pos: Int): Int
+       fun index_of_from(item: nullable Object, pos: Int): Int
        do
                var p = 0
                var i = iterator
@@ -755,7 +755,7 @@ interface SequenceRead[E]
        #     assert a.last_index_of_from(20, 2)   == 1
        #     assert a.last_index_of_from(20, 1)   == 1
        #     assert a.last_index_of_from(20, 0)   == -1
-       fun last_index_of_from(item: E, pos: Int): Int
+       fun last_index_of_from(item: nullable Object, pos: Int): Int
        do
                var res = -1
                var p = 0
@@ -1005,7 +1005,7 @@ interface CoupleMap[K, V]
 
        # Return the couple of the corresponding key
        # Return null if the key is no associated element
-       protected fun couple_at(key: K): nullable Couple[K, V] is abstract
+       protected fun couple_at(key: nullable Object): nullable Couple[K, V] is abstract
 
        # Return a new iteralot on all couples
        # Used to provide `iterator` and others

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index cdb5242..b3ec382 100644 (file)
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -63,9 +63,9 @@ abstract class AbstractArrayRead[E]
 
        redef fun index_of(item) do return index_of_from(item, 0)
 
-       redef fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
+       redef fun last_index_of(item) do return last_index_of_from(item, length-1)
 
-       redef fun index_of_from(item: E, pos: Int): Int
+       redef fun index_of_from(item, pos)
        do
                var i = pos
                var len = length
@@ -78,7 +78,7 @@ abstract class AbstractArrayRead[E]
                return -1
        end
 
-       redef fun last_index_of_from(item: E, pos: Int): Int
+       redef fun last_index_of_from(item, pos)
        do
                var i = pos
                while i >= 0 do

diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit
index e5ff507..961e560 100644 (file)
--- a/lib/standard/collection/hash_collection.nit
+++ b/lib/standard/collection/hash_collection.nit
@@ -32,13 +32,13 @@ private abstract class HashCollection[K]
        var last_item: nullable N = null # Last added item (same)
 
        # The last key accessed (used for cache)
-       var last_accessed_key: nullable K = null
+       var last_accessed_key: nullable Object = null
 
        # The last node accessed (used for cache)
        var last_accessed_node: nullable N = null
 
        # Return the index of the key k
-       fun index_at(k: K): Int
+       fun index_at(k: nullable Object): Int
        do
                if k == null then return 0
 
@@ -48,7 +48,7 @@ private abstract class HashCollection[K]
        end
 
        # Return the node associated with the key
-       fun node_at(k: K): nullable N
+       fun node_at(k: nullable Object): nullable N
        do
                # cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
                if k.is_same_instance(_last_accessed_key) then return _last_accessed_node
@@ -60,7 +60,7 @@ private abstract class HashCollection[K]
        end
 
        # Return the node associated with the key (but with the index already known)
-       fun node_at_idx(i: Int, k: K): nullable N
+       fun node_at_idx(i: Int, k: nullable Object): nullable N
        do
                var c = _array[i]
                while c != null do
@@ -109,7 +109,7 @@ private abstract class HashCollection[K]
        end
 
        # Remove the node assosiated with the key
-       fun remove_node(k: K)
+       fun remove_node(k: nullable Object)
        do
                var i = index_at(k)
                var node = node_at_idx(i, k)

diff --git a/lib/standard/collection/range.nit b/lib/standard/collection/range.nit
index 1ad0309..5ed0531 100644 (file)
--- a/lib/standard/collection/range.nit
+++ b/lib/standard/collection/range.nit
@@ -30,7 +30,7 @@ class Range[E: Discrete]
        #     assert [1..10].has(5)
        #     assert [1..10].has(10)
        #     assert not [1..10[.has(10)
-       redef fun has(item) do return item >= first and item <= last
+       redef fun has(item) do return item isa Comparable and item >= first and item <= last
 
        #     assert [1..1].has_only(1)
        #     assert not [1..10].has_only(1)

diff --git a/lib/standard/collection/union_find.nit b/lib/standard/collection/union_find.nit
index 12c9c86..f4c6baa 100644 (file)
--- a/lib/standard/collection/union_find.nit
+++ b/lib/standard/collection/union_find.nit
@@ -115,7 +115,7 @@ class DisjointSet[E]
        #     s.add(1)
        #     assert s.has(1)
        #     assert not s.has(2)
-       redef fun has(e: E): Bool
+       redef fun has(e)
        do
                return nodes.has_key(e)
        end

diff --git a/lib/trees/bintree.nit b/lib/trees/bintree.nit
index 6b6b91c..610ec2e 100644 (file)
--- a/lib/trees/bintree.nit
+++ b/lib/trees/bintree.nit
@@ -64,7 +64,7 @@ class BinTreeMap[K: Comparable, E]
        #     assert not tree.has_key(0)
        #     assert tree.has_key(2)
        #     assert not tree.has_key(6)
-       redef fun has_key(key: K): Bool do
+       redef fun has_key(key) do
                if is_empty then return false
                var res = search_down(root.as(not null), key)
                if res != null then
@@ -85,7 +85,7 @@ class BinTreeMap[K: Comparable, E]
        #     assert tree[1] == "n1"
        #     assert tree.has_key(1)
        #     assert tree[2] == "n2"
-       redef fun [](key: K): E do
+       redef fun [](key) do
                assert not_empty: not is_empty
                if cache_node != null and cache_node.key == key then return cache_node.value
                var res = search_down(root.as(not null), key)
@@ -94,7 +94,8 @@ class BinTreeMap[K: Comparable, E]
        end
 
        # Search `key` in `from` and its children nodes.
-       protected fun search_down(from: N, key: K): nullable N do
+       protected fun search_down(from: N, key: nullable Object): nullable N do
+               if not key isa Comparable then return null
                var cmp = key <=> from.key
                if cmp == 0 then return from
                if from.left != null and cmp < 0 then

diff --git a/src/doc/doc_phases/doc_indexing.nit b/src/doc/doc_phases/doc_indexing.nit
index 3e71df2..72df73c 100644 (file)
--- a/src/doc/doc_phases/doc_indexing.nit
+++ b/src/doc/doc_phases/doc_indexing.nit
@@ -80,6 +80,7 @@ private class QuickSearchTable
 
        redef fun provide_default_value(key) do
                var v = new QuickSearchResultList
+               assert key isa String
                self[key] = v
                return v
        end

diff --git a/tests/sav/test_coll_eq.res b/tests/sav/test_coll_eq.res
new file mode 100644 (file)
index 0000000..abe1e00
--- /dev/null
+++ b/tests/sav/test_coll_eq.res
@@ -0,0 +1,13 @@
+true
+true
+true
+true
+true
+true
+
+true
+true
+true
+
+true
+hello

diff --git a/tests/test_coll_eq.nit b/tests/test_coll_eq.nit
new file mode 100644 (file)
index 0000000..bf13bd9
--- /dev/null
+++ b/tests/test_coll_eq.nit
@@ -0,0 +1,38 @@
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+var a = [1,2,3]
+var l = new List[Int].from(a)
+var l2 = new List[Object].from(a)
+
+print a == l
+print a == l2
+print l == a
+print l == l2
+print l2 == a
+print l2 == l
+print ""
+
+var aa = [a]
+print aa.has(a)
+print aa.has(l)
+print aa.has(l2)
+print ""
+
+var map = new Map[List[Int], String]
+map[l] = "hello"
+
+var mapr: MapRead[Object, String] = map
+print mapr.has_key(a)
+print mapr[l2]