I'm studying kotlin in official site. I understand that the sequence has two type operation(intermediate, terminal). And the intermediate operation is triggered when the terminal operation is called. What I want to know is that the trigger point when the terminal operation is called. I deep dive into the code but couldn't find the source code. Where is the trigger source code?

public fun <T> Sequence<T>.toList(): List<T> {
    return this.toMutableList().optimizeReadOnlyList()
}

public fun <T> Sequence<T>.toMutableList(): MutableList<T> {
    return toCollection(ArrayList<T>())
}

public fun <T, C : MutableCollection<in T>> Sequence<T>.toCollection(destination: C): C {
    for (item in this) {
        destination.add(item)
    }
    return destination
}

updated

fun testSequence(){
    val words = "The quick brown fox jumps over the lazy dog".split(" ")
//convert the List to a Sequence
    val wordsSequence = words.asSequence()

    val lengthsSequence = wordsSequence.filter { println("filter: $it"); it.length > 3 }
        .map { println("length: ${it.length}"); it.length }
        .take(4)

    println("Lengths of first 4 words longer than 3 chars")
    
// terminal operation: obtaining the result as a List
    Thread.sleep(2000)
    println(lengthsSequence.toList())
}

CodePudding user response：

It might help to see that the for loop in toCollection is translated to:

when(val $iterator = this.iterator()) {
    else -> while ($iterator.hasNext()) {
                val item = __iterator.next()
                destination.add(item)
            }

(See the spec for more details on how for loops work)

The key thing here is that this includes a call to iterator, and a call to next on that iterator. What these calls actually does will depend on what intermediate operations you have called.

For example, let's consider the sequence listOf(1,2,3).asSequence(). Looking at the source code for asSequence, we can see that the iterator for this sequence is just the same iterator as listOf(1,2,3).iterator(). (Verifying this has been left as an exercise for the reader)

Therefore, calling toList() on this sequence will give you the list [1,2,3].

Now consider listOf(1,2,3).asSequence().filter { it == 2 }. filter returns a FilteringSequence, with its own implementation of iterator:

public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    return FilteringSequence(this, true, predicate)
}

...

internal class FilteringSequence<T>(
    private val sequence: Sequence<T>,
    private val sendWhen: Boolean = true,
    private val predicate: (T) -> Boolean
) : Sequence<T> {

    override fun iterator(): Iterator<T> = object : Iterator<T> {
        val iterator = sequence.iterator()
        var nextState: Int = -1 // -1 for unknown, 0 for done, 1 for continue
        var nextItem: T? = null

        private fun calcNext() {
            while (iterator.hasNext()) {
                val item = iterator.next()
                ...
            }
            ...
        }
        ...
    }
}

The important thing here is that in filter, this is passed to FilteringSequence, which becomes sequence, and in its implementation of iterator, it uses sequence.iterator(), calling next on it, in addition to performing the filtering logic specific to filter, of course.

This means that when you do toList on listOf(1,2,3).asSequence().filter { it == 2 }, and it calls next on the filtering sequence's iterator, it will eventually call next on the iterator of listOf(1,2,3).

All the intermediate operations are like this. They are all defined in terms of an "upstream" sequence, and they will use the iterator of the "upstream" sequence in their implementation of iterator. Therefore, if you have a chain of

listOf(1,2,3).asSequence()
    .map { it   1 }
    .filter { it > 0 }
    .take(5)
    .flatMap { listOf(it, it) }
    .count()

You create

1. a TransformingSequence with listOf(1,2,3).asSequence() being the upstream,
2. a FilteringSequence with 1. being the upstream
3. a TakeSequence with 2. being the upstream
4. a FlatteningSequence with 3. being the upstream

and when count() is called, the next method of the iterator of the FlatteningSequence is called, which in turn calls that of the TakeSequence, which in turn calls that of the FilteringSequence, and so on... Hence performing the logic of each operation, as those are implemented in the next method.