Reason behind duplicated functions in standard library

I noticed that in the standard library there are multiple declarations of the function containsAll.

One declared as a member function of Collection (doc) (source);
Another one declared as an extension function of Collection (doc) (source).

What’s the reason behind this?


On a side note, I also have no clue why containsAll is on Collection but not its supertype Iterable.

Under the hood, Collection.containsAll invokes Iterable.all and Iterable.contains.

We can easily implement containsAll in Iterable:

fun <T> Iterable<T>._containsAll(other: Iterable<T>): Boolean = other.all { contains(it) }

Why is that the case?

I imagine that some Iterable implementations may be of only one-time traversal, so you wouldn’t be able to iterate over them multiple times using contains().

1 Like

oh right that makes sense, thanks

The source for the extension function has a comment: “Allows to overcome type-safety restriction of containsAll that requires to pass a collection of type Collection<E>.”


The comment is vague about what exact restriction it is trying to over come… is it related to declaration-site covariance of Collection’s type parameter?

Is this related?

I suppose they meant to allow checking against the collection of super types. See this example:

val nums = listOf<Number>()
val ints = listOf<Int>()
val floats = listOf<Float>()

nums.containsAll(ints) // expected to work
ints.containsAll(nums) // expected to work
ints.containsAll(floats) // expected to fail

If you ctrl-click on containsAll(), you will notice the first one points to the member function, but the second one to the extension. Second case would be impossible to do without an extension, because while calling a member function, we can’t implicitly upcast the receiver type. We can do this while using extensions. Alternatively, we could change the type of the parameter to simply: Collection<Any?>, but then the third case would be allowed.

I’m not convinced with this explanation. We have Iterator for single iteration only. Iterable is generally iterable multiple times and it may be sometimes restricted.

Also, I doubt we use such implementation of containsAll() in practice. It would be terrible for the performance, it would be quadratic (O(M * N)). This function can be easily implemented to be linear (O(M + N)) by using a hash set. Then, we iterate the receiver only once.

We need to remember kotlin.collections.Collection is not a “real” type. It is required to represent collections in the Kotlin source code, but then it is compiled using native types for the specific platform. In Java that means java.util.Collection. Compiler can’t add new methods to existing types, so we have to compile to whatever is available in the target stdlib. In Java containsAll() is defined for Collection, but not for Iterable.

Also, please remember adding more functions to an interface is maybe convenient for the user of the interface, but it makes implementing it harder. Imagine you need to implement a simple Iterable which only returns an iterator you already have, but then you have to implement containsAll() and other methods as well. It is usually better to use extensions for such cases (or alternatively: default methods).


This is wild :hushed:

I’ve created a custom class to play/test with, will come back to it later:

class Box<out T>(
    val item: T
    fun contains(t: @UnsafeVariance T) =  item == t

fun <T> Box<T>.contains(t: T) = item == t

val numBox: Box<Number> = Box(1L)
val intBox: Box<Int> = Box(2)
val floatBox: Box<Float> = Box(3f)

numBox.contains(1L)  //method
numBox.contains(2)   //method
numBox.contains(3f)  //method

intBox.contains(1L)  //extension function
intBox.contains(2)   //method
intBox.contains(3f)  //extension function

floatBox.contains(1L)//extension function
floatBox.contains(2) //extension function

Yes :slight_smile:

It works like this because if we use a generic class/interface, then T is provided by the type and can’t be changed. If we use a generic function (including extension), then T is inferred at the call-site - the compiler looks at arguments and return types and tries to find T which meets all requirements. It could choose a supertype of provided arguments.

Your sample is still a little different than the one for containsAll(). floatBox.contains(1L) case would not compile for containsAll(). This is expected behavior. We expect the argument collection to be either the super type or sub type, but not sibling or just any arbitrary type. This is accomplished for containsAll() by using an internal annotation: @kotlin.internal.OnlyInputTypes.

1 Like

Thanks agian broot!
I have collected my thought and I have written this as a note…
Would you please take a look (and nit-pick all mistakes) to see if my understanding is correct?

class Box<out T>(
    private var item: T
    fun getItem() = item

    //It generally makes sense to not use covariant type parameters at `in` positions;
    /*fun setItem(t: T){item = t}*/ //ERROR: Type parameter T is declared as 'out' but occurs in 'in' position in type T

    //However there are situations where it is conceptually fine, but the compiler prevents us from doing it anyway.
    /*fun contains(t: T) = item == t*/ //ERROR: Type parameter T is declared as 'out' but occurs in 'in' position in type T

    //To work around the limitation:
     * 1. we could suppress checking with annotation `@UnsafeVariance`;
    fun contains_annotated(t: @UnsafeVariance T) =  item == t

 * 2. or we could create an extension function for the same functionality.
 *  - This works because extension functions cannot access private members,
 *      this limitation essentially prevents us from breaking covariance.
 *  - The type parameter declared by the extension function (`U`) is used as type argument of `Box` (`T`),
 *      they are not the same type parameter.
 *      This makes the extension function behaviourally more flexible, where `U` can be a supertype of `T`.
 *  - Automatic type inferring that leads to `U` being a supertype of `T`, can be prevented:
 *      - at declaration-site, with the use of `@kotlin.internal.OnlyInputTypes`
 *        (it is [internal]( though 🤷‍️)
 *      - at use-site, by explicitly specifying the type of `U` as `T`
 *        (practically that would never happen, because we couldn't use the function in cases where we had to specify the type explicitly)
fun <U> Box<U>.contains_extfx(u: U) = getItem() == u

val numBox: Box<Number> = Box(1L)
val intBox: Box<Int> = Box(2)
val floatBox: Box<Float> = Box(3f)

/*intBox.contains_annotated(1L)*/   //ERROR: The integer literal does not conform to the expected type Int
/*intBox.contains_annotated(3f)*/   //ERROR: The floating-point literal does not conform to the expected type Int
/*floatBox.contains_annotated(1L)*/ //ERROR: The integer literal does not conform to the expected type Float
/*floatBox.contains_annotated(2)*/  //ERROR: The integer literal does not conform to the expected type Float

intBox.contains_extfx<Any>(1L)   //type argument is `Any`, not `Int`
intBox.contains_extfx<Any>(3f)   //type argument is `Any`, not `Int`
floatBox.contains_extfx<Any>(1L) //type argument is `Any`, not `Float`
floatBox.contains_extfx<Any>(2)  //type argument is `Any`, not `Float`

Again, I really appreciate all the replies :grinning:

Regarding Iterable how many times can it be iterated really?

Under Iterator, we only have the functions hasNext() and getNext() – clearly we are not guaranteed the ability to backtrack, and so the ability to iterate multiple times;

The kdoc on Iterable did not mention anything about iterating multiple times…

Iterable has a single function iterator(), which returns an Iterator instance.
The documentation above the iterator() function is:

Returns an iterator over the elements of this object.

There is no explicit instruction that it has to be a new Iterator instance every call, or that the Iterator instance has to point at the first element. Besides its not like the function is called newIterator or something… so there is no guarantee neither :thinking:

No, there are no strict rules on how many times Iterable could be iterated, nor it is not specified how Iterable should behave if it is a single-use only and it is asked multiple times for an iterator. It is left for the developer to get it right.

In Java this is straightforward because extension functions aren’t available;

However with Kotlin extension functions, we have to assume that all Iterable implementations can only be iterated through once, otherwise the extension function wouldn’t be reliable… Especially when the extension function is a part of the standard library :thinking: