Skip的原碼探索

本章會說明及分析Skip、SkipLast、SkipWhile三個方法的原始碼實作及測試案例欣賞。

原始碼分析

Source Code: Skip.cs、Partition.cs

Skip

Skip有一個公開方法的實作如下:

public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (count <= 0)
    {
        // Return source if not actually skipping, but only if it's a type from here, to avoid
        // issues if collections are used as keys or otherwise must not be aliased.
        if (source is Iterator<TSource> || source is IPartition<TSource>)
        {
            return source;
        }

        count = 0;
    }

    else if (source is IPartition<TSource> partition)
    {
        return partition.Skip(count);
    }

    if (source is IList<TSource> sourceList)
    {
        return new ListPartition<TSource>(sourceList, count, int.MaxValue);
    }

    return new EnumerablePartition<TSource>(source, count, -1);
}

此公開方法做了下面幾件事情:

判斷source是否為空，空的話拋出ArgumentNull的例外
判斷count是否小於0，小於0的話將count設成0
前面已經是IPartition型別，也就是已經有執行過LINQ了，直接call之前method實作的Skip
如果是IList就用ListPartition實作
其餘的叫用EnumerablePartition實作

看到Enumerable就會想到MoveNext()，所以接下來會介紹ListPartition跟EnumerablePartition的定義及MoveNext()。

ListPartition

public ListPartition(IList<TSource> source, int minIndexInclusive, int maxIndexInclusive);

傳入一個List，設好第一個元素及最後個元素的index，他會把這區間內的元素集合輸出。

這裡要注意的是如果只要忽略前面的元素的話只需要設定minIndexInclusive，maxIndexInclusive設為int.MaxValue就好。

下面是MoveNext()的實作:

public override bool MoveNext()
{
    // _state - 1 represents the zero-based index into the list.
    // Having a separate field for the index would be more readable. However, we save it
    // into _state with a bias to minimize field size of the iterator.
    int index = _state - 1;
    if (unchecked((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive))
    {
        _current = _source[_minIndexInclusive + index];
        ++_state;
        return true;
    }

    Dispose();
    return false;
}

上面的程式有幾個重點:

_state當作索引，初始值是1，所以index = _state - 1
這裡要輸出的元素是由_minIndexInclusive起算，可以想成_minIndexInclusive是個起點，而index則是由這個起點數來第幾個的變數
判斷index有沒有超出最大索引值及集合數量
如果超出則return false，結束迭代
如果沒有超出，則把目前的元素附給_current，然後_state加1，回傳true

這裡我們注意到一件事，因為_maxIndexInclusive的用法是index <= _maxIndexInclusive - _minIndexInclusive，所以只要把_maxIndexInclusive設為int.MaxValue，_maxIndexInclusive就不會影響判斷，因此Skip才會將其設為int.MaxValue。

EnumerablePartition

internal EnumerablePartition(IEnumerable<TSource> source, int minIndexInclusive, int maxIndexInclusive);

傳入一個IEnumerable，設好第一個元素及最後個元素的index，他會把這區間內的元素集合輸出。

如果只要忽略由第一個數來第N個元素的話只需要設定minIndexInclusive，maxIndexInclusive設為-1就好。

這裡有一個地方跟ListPartition不同，只要忽略前面的元素時maxIndexInclusive的設定一個是int.MaxValue，一個是-1，我們等下從實作上看為什麼會不同。

下面是MoveNext()的實作:

public override bool MoveNext()
{
    // Cases where GetEnumerator has not been called or Dispose has already
    // been called need to be handled explicitly, due to the default: clause.
    int taken = _state - 3;
    if (taken < -2)
    {
        Dispose();
        return false;
    }

    switch (_state)
    {
        case 1:
            _enumerator = _source.GetEnumerator();
            _state = 2;
            goto case 2;
        case 2:
            if (!SkipBeforeFirst(_enumerator))
            {
                // Reached the end before we finished skipping.
                break;
            }

            _state = 3;
            goto default;
        default:
            if ((!HasLimit || taken < Limit) && _enumerator.MoveNext())
            {
                if (HasLimit)
                {
                    // If we are taking an unknown number of elements, it's important not to increment _state.
                    // _state - 3 may eventually end up overflowing & we'll hit the Dispose branch even though
                    // we haven't finished enumerating.
                    _state++;
                }
                _current = _enumerator.Current;
                return true;
            }

            break;
    }

    Dispose();
    return false;
}

這段程式碼有下面幾個重點:

這裡的_state回歸原本的用法: 狀態的設置
_state=1: 初始_source，轉為Enumerator
_state=2: 判斷設置的minIndexInclusive是否超過集合總長度並且將_enumerator的_current推至minIndexInclusive的位置
_state=3: 判斷是否超過最大長度，沒有的話將_current往後再推一個至目標位置然後傳回true

我們可以在HasLimit找到為什麼maxIndexInclusive要設-1:

private bool HasLimit => _maxIndexInclusive != -1;

EnumerablePartition是用_maxIndexInclusive != -1判斷是否有設定最大值，所以如果沒有設定最大值的話要設為-1。

SkipLast

SkipLast有一個公開方法，其實作為:

判斷參數是否為空，如果為空則拋出ArgumentNull例外
參數判斷合法後叫用SkipLastIterator

下面為SkipLastIterator的實作:

private static IEnumerable<TSource> SkipLastIterator<TSource>(IEnumerable<TSource> source, int count)
{
    Debug.Assert(source != null);
    Debug.Assert(count > 0);

    var queue = new Queue<TSource>();

    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        while (e.MoveNext())
        {
            if (queue.Count == count)
            {
                do
                {
                    yield return queue.Dequeue();
                    queue.Enqueue(e.Current);
                }
                while (e.MoveNext());
                break;
            }
            else
            {
                queue.Enqueue(e.Current);
            }
        }
    }
}

SkipLast是用yield return實作，有下面幾個重點:

維護一個Queue，用來存放集合的元素
叫用MoveNext()將Queue的元素數量塞到跟要Skip的元素數量一樣為止
當Queue的元素數量跟要Skip的數量相同時，做以下動作
1. 從Queue裡抓出第一個元素做yield return
2. 將目前的元素在塞到Queue裡
3. 叫用MoveNext()做下一輪的判斷

第三點的處理會讓Queue裡一直保持最後count數的元素，代表到巡覽結束時在Queue中的元素就不會被輸出，所以就可以做到最後count數的元素Skip的處理。

SkipWhile

SkipWhlie有兩個公開方法，差別在predicate參數上:

SkipWhile<TSource>(...Func<TSource, bool> predicate);

SkipWhile<TSource>(...Func<TSource, int, bool> predicate);

一個有傳入index的參數，另一個沒有傳入。

兩個方法都做了以下的處理:

判斷參數是否為空，如果為空則拋出ArgumentNull例外
參數判斷合法後叫用SkipWhileIterator

我們兩種Iterator一起看，直接看有index參數的predicate的SkipWhileIterator:

private static IEnumerable<TSource> SkipWhileIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
{
    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        int index = -1;
        while (e.MoveNext())
        {
            checked
            {
                index++;
            }

            TSource element = e.Current;
            if (!predicate(element, index))
            {
                yield return element;
                while (e.MoveNext())
                {
                    yield return e.Current;
                }

                yield break;
            }
        }
    }
}

這段有下列的重點:

每次MoveNext()時index就加1
判斷predicate的結果，如果是true代表要繼續Skip
如果是false的話代表要輸出這個元素之後的所有元素

測試案例賞析

Source Code: SkipTests.cs、SkipLastTests.cs、SkipWhileTests.cs

SkipTests.cs

SkipExcessive

[Fact]
public void SkipExcessive()
{
    Assert.Equal(Enumerable.Empty<int>(), NumberRangeGuaranteedNotCollectionType(0, 20).Skip(42));
}

count超過元素數量的話會傳回Empty。

SkipOnEmpty

[Fact]
public void SkipOnEmpty()
{
    Assert.Equal(Enumerable.Empty<int>(), GuaranteeNotIList(Enumerable.Empty<int>()).Skip(0));
    Assert.Equal(Enumerable.Empty<string>(), GuaranteeNotIList(Enumerable.Empty<string>()).Skip(-1));
    Assert.Equal(Enumerable.Empty<double>(), GuaranteeNotIList(Enumerable.Empty<double>()).Skip(1));
}

source是Empty並不會拋出ArgumentNull的例外，而是回傳Empty的集合。

SkipNegative

[Fact]
public void SkipNegative()
{
    Assert.Equal(Enumerable.Range(0, 20), NumberRangeGuaranteedNotCollectionType(0, 20).Skip(-42));
}

count為負數時不會Skip任何元素。

結語

在Skip的原始碼中，我們可以觀察到Skip是用什麼方式達成目標的，其中最特別的是SkipLast，用了一個Queue存入跟要Skip數量相同的元素，在巡覽到想同數量時開始把Queue中的第一個元素吐出，最後Queue中只會剩下要Skip的元素，剩餘的都已經巡覽了。

參考

dotnet/corefx

# Skip的原碼探索

# 原始碼分析

# Skip

# ListPartition

# EnumerablePartition

# SkipLast

# SkipWhile

# 測試案例賞析

# SkipTests.cs

# SkipExcessive

# SkipOnEmpty

# SkipNegative

# 結語

# 參考