# OrderBy源码分析

**Repository Path**: hu-lizhe/order-by-source-code-analysis

## Basic Information

- **Project Name**: OrderBy源码分析
- **Description**: C#分析OrderBy源码理解使用OrderBy乱序数组的技巧。
配合文章https://zhuanlan.zhihu.com/p/624891558?食用风味最佳
- **Primary Language**: C#
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2023-04-26
- **Last Updated**: 2023-05-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 通过分析OrderBy源码理解使用OrderBy乱序数组的技巧

## 问题

有这样一段代码，用来实现数组乱序：  
![问题](./%E5%9B%BE%E7%89%871.png)

为什么这样写可以做到让数组乱序？  
我们把鼠标放到var身上，可以看到：
![var是什么](./%E5%9B%BE%E7%89%872.png)  
对IOrderedEnumerable< T >类型进行foreach遍历，foreach底层是怎么遍历的呢？其实foreach是语法糖，本质上，foreach会被编译成什么？

## 了解foreach

我们来看看官网对foreach语法的解释。  
首先来看这样一段代码：
```
foreach (var item in collection)
{
    Console.WriteLine(item?.ToString());
}
```
collection依赖于.net core中定义的2个泛型接口，才能生成循环访问集合所需的代码：IEnumerable< T > 和 IEnumerator< T >。这 2 种接口还具备相应的非泛型接口：IEnumerable 和 IEnumerator。  
编译器会将foreach 循环转换为类似于此构造的内容：  
```
IEnumerator<int> enumerator = collection.GetEnumerator();
while (enumerator.MoveNext())
{
    var item = enumerator.Current;
    Console.WriteLine(item.ToString());
}
```
然后我们看看IEnumerator的源码实现以及开发者对于内部字段和方法的解释：  
```
[System.Runtime.InteropServices.ComVisible(true)]
    public interface IEnumerator
    {
        // Interfaces are not serializable
        // Advances the enumerator to the next element of the enumeration and
        // returns a boolean indicating whether an element is available. Upon
        // creation, an enumerator is conceptually positioned before the first
        // element of the enumeration, and the first call to MoveNext 
        // brings the first element of the enumeration into view.
        // 
        bool MoveNext();
    
        // Returns the current element of the enumeration. The returned value is
        // undefined before the first call to MoveNext and following a
        // call to MoveNext that returned false. Multiple calls to
        // GetCurrent with no intervening calls to MoveNext 
        // will return the same object.
        // 
        Object Current {
            get; 
        }
    
        // Resets the enumerator to the beginning of the enumeration, starting over.
        // The preferred behavior for Reset is to return the exact same enumeration.
        // This means if you modify the underlying collection then call Reset, your
        // IEnumerator will be invalid, just as it would have been if you had called
        // MoveNext or Current.
        //
        void Reset();
    }
```

简单来说，调用MoveNext方法会让迭代器(enumerator)移动一步到枚举中的下一个元素，如果这个元素是有效的，返回true，否则返回false；注意，迭代器在创建时默认位置是在第一个枚举元素之前(概念上来说)。  
访问Current这个对象时会返回迭代器当前所在位置上的元素，但是如果在还没有调用过MoveNext方法和调用MoveNext方法后返回false这两种情况下会返回undefined。  
Reset方法会重置迭代器回到初始位置，即第一个枚举元素之前。后面那句话的意思我的理解大概是，如果你在改变当前集合后调用MoveNext或者Current，都会使迭代器无效。  
所以foreach本质上就是在不停调用moveNext移动迭代器，取出当前指向的元素然后每一轮循环中的操作，直至迭代器失效。foreach了解到这里差不多了。  

## 反编译代码并分析

既然我们有ILSpy，也了解了foreach的原理，接下来我们直接反编译最开始的那段代码，结果如下：  
```
private static void Main(string[] args)
{
    int[] ints = new int[10] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    Random random = new Random();
    IOrderedEnumerable<int> ordered = Enumerable.OrderBy(ints, (int n) => random.Next());
    using (IEnumerator<int> enumerator = ordered.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            Console.Write(enumerator.Current + " ");
        }
    }
    Console.WriteLine("");
    Console.ReadKey();
}
```

ordered是一个接口，该接口是这样定义的：
```
public interface IOrderedEnumerable<TElement> : IEnumerable<TElement>
{
    IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending);
}
```

可以看到，该接口继承自IEnumerable<TElement>，IEnumerable接口的定义是这样的：  
```
public interface IEnumerable<out T> : IEnumerable
{
    new IEnumerator<T> GetEnumerator();
}
```

因为ordered具有接口 IEnumerable，所以在后续的using语句中它可以调用GetEnumerator()方法。然后我们要看这个ordered具体的对象(class)是谁，从而找到对GetEnumerator()的具体实现。  
`IOrderedEnumerable<int> ordered = Enumerable.OrderBy(ints, (int n) => random.Next());`

从这句语句可以看出，OrderBy的返回值赋给了ordered，OrderBy的源码如下：
```
public static IOrderedEnumerable<TSource>
 OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
 {
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}
```

看起来是new了一个OrderedEnumerable对象并返回，我们来看一下这个对象的源码：
```
internal class OrderedEnumerable<TElement, TKey> : OrderedEnumerable<TElement>
    {
        internal OrderedEnumerable<TElement> parent;
        internal Func<TElement, TKey> keySelector;
        internal IComparer<TKey> comparer;
        internal bool descending;
 
        internal OrderedEnumerable(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending) {
            if (source == null) throw Error.ArgumentNull("source");
            if (keySelector == null) throw Error.ArgumentNull("keySelector");
            this.source = source;
            this.parent = null;
            this.keySelector = keySelector;
            this.comparer = comparer != null ? comparer : Comparer<TKey>.Default;
            this.descending = descending;
        }
 
        internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next) {
            EnumerableSorter<TElement> sorter = new EnumerableSorter<TElement, TKey>(keySelector, comparer, descending, next);
            if (parent != null) sorter = parent.GetEnumerableSorter(sorter);
            return sorter;
        }
}
```

我们确实找到了ordered具体的对象(class)是OrderedEnumerable< TElement, TKey>，可是在该类中没有对于GetEnumerator()的具体实现，于是我们进入它的父类OrderedEnumerable TElement>进行查找，终于，功夫不负有心人，我们找到了：
```
public IEnumerator<TElement> GetEnumerator() {
        Buffer<TElement> buffer = new Buffer<TElement>(source);
        if (buffer.count > 0) {
            EnumerableSorter<TElement> sorter = GetEnumerableSorter(null);
            int[] map = sorter.Sort(buffer.items, buffer.count);
            sorter = null;
            for (int i = 0; i < buffer.count; i++) yield return buffer.items[map[i]];
        }
    }
```

在这段代码里，可以看到是做了排序的，这是合理的，排完序后返回迭代器，然后在外层代码中不停调用movenext方法取出current对象并操作，终于，我们可以开始问最初的问题了：给OrderBy传入的匿名方法返回一个随机值，为什么能让集合中的元素乱序？带着这个问题，我们来分析这段代码。
首先，我们要搞清楚**TElement是谁，source又是谁**  

现在就像递归到底了要出调用栈了一样， OrderedEnumerable< TElement>的子类是 OrderedEnumerable< TElement, TKey>，OrderedEnumerable< TElement, TKey>是我们在OrderBy源码里看到的：
```
public static IOrderedEnumerable<TSource>
 OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
 {
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}
```

TSource传给了TElement，这里的 IEnumerable< TSource>里的TSource为int,因为我们传入的是int[]会被转化为IEnumerable< int>，因此得出结论：
TElement是int
继续查找另外一个叫做source的身份，在OrderedEnumerable< TElement>类定义中定义了source:
internal IEnumerable< TElement> source;
因为已知TElement是int，那么迎刃而解，source是IEnumerable< int>变量，同时，要注意子类 OrderedEnumerable的构造函数，它会传入第一个参数并赋给父类中的source，这个source就是我们程序中定义的int[]。

为了更加直观，把TElemnet全部替换为int，并加上注释，我们得到如下代码：
```
 public IEnumerator<int> GetEnumerator() {
//拷贝一份source至buffer中
    Buffer<int> buffer = new Buffer<int>(source);
if (buffer.count > 0) {
//GetEnumerableSorter方法会调用子类中的具体实现
        EnumerableSorter<int> sorter = GetEnumerableSorter(null);
        int[] map = sorter.Sort(buffer.items, buffer.count);
        sorter = null;
        for (int i = 0; i < buffer.count; i++) 
		yield return buffer.items[map[i]];
    }
}
```

这个buffer，是与OrderedEnumerable定义在同一文件中的。
```
struct Buffer<TElement>
    {
        internal TElement[] items;
        internal int count;
 
        internal Buffer(IEnumerable<TElement> source) {
            TElement[] items = null;
            int count = 0;
            ICollection<TElement> collection = source as ICollection<TElement>;
            if (collection != null) {
                count = collection.Count;
                if (count > 0) {
                    items = new TElement[count];
                    collection.CopyTo(items, 0);
                }
            }
            else {
                foreach (TElement item in source) {
                    if (items == null) {
                        items = new TElement[4];
                    }
                    else if (items.Length == count) {
                        TElement[] newItems = new TElement[checked(count * 2)];
                        Array.Copy(items, 0, newItems, 0, count);
                        items = newItems;
                    }
                    items[count] = item;
                    count++;
                }
            }
            this.items = items;
            this.count = count;
        }
 
        internal TElement[] ToArray() {
            if (count == 0) return new TElement[0];
            if (items.Length == count) return items;
            TElement[] result = new TElement[count];
            Array.Copy(items, 0, result, 0, count);
            return result;
        }
    }
```
Buffer的作用就是拷贝一份source到一块内存buffer中。

看下子类中对于GetEnumerableSorter的具体实现：
```
Internal override 
EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next) 
{
   EnumerableSorter<TElement> sorter = new 
EnumerableSorter<TElement, TKey>(keySelector, comparer, descending, next);
            if (parent != null) sorter = parent.GetEnumerableSorter(sorter);
            return sorter;
}
```

我们假设parent就是空的，取的就是new出来的EnumerableSorter，这种总算是牵扯到了keyselector也就是我们传入的lambda表达式，那么，我们来看下EnumerableSorter的构造函数源码实现：
```
internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement> next) {
            this.keySelector = keySelector;
            this.comparer = comparer;
            this.descending = descending;
            this.next = next;
        }
```

这个构造函数看起来没什么东西，重点应该不在这儿。那我们接续看，接着EnumerableSorter实例调用了sort方法，在EnumerableSorter类定义中是没有这个方法实现的，所以，应该是在其父类上有这个方法的定义：
```
internal int[] Sort(TElement[] elements, int count) {
    ComputeKeys(elements, count);
    int[] map = new int[count];
    for (int i = 0; i < count; i++) map[i] = i;
    QuickSort(map, 0, count - 1);
    return map;
}
```

这个ComputeKeys是一个抽象方法，所以我们需要去找子类上实现的ComputeKeys：
```
internal override void ComputeKeys(TElement[] elements, int count) {
        keys = new TKey[count];
        for (int i = 0; i < count; i++) keys[i] = keySelector(elements[i]);
        if (next != null) next.ComputeKeys(elements, count);
    }
```

首先要注意，在调用GetEnumerableSorter时传入的参数为Null，所以next为null,不会走最后一行。
然后，TKey是什么？
传入的lambda表达式的返回值类型即为TKey，对本例子来说就是Int。
TElement是什么？
传入的lambda表达式的参数类型即为TElement，对本例子来说也是Int。
count参数自然就是TElement数组的长度
代码分析：
Keys为新创建的int数组，
根据数组长度遍历，每一轮中：
Keys[i] = keySelector(elements[i]);
即：
Keys[i] = ((n) => random.next())();
Keys[i]的值为0到2147483647中的任意一个整数

回到Sort方法继续执行，创建了一个名为map的Int数组，该数组大小与source数组大小一致，并且将下标与值一一对应，即map[0]=0,map[1]=1...
接着调用快排，传入这个Map数组，最后返回map。
有个问题是，map里的元素是顺序的，为什么要再快排呢？

我们来看下这里的快排源码：
```
void QuickSort(int[] map, int left, int right) {
        do {
            int i = left;
            int j = right;
            int x = map[i + ((j - i) >> 1)];
            do {
                while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
                while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
                if (i > j) break;
                if (i < j) {
                    int temp = map[i];
                    map[i] = map[j];
                    map[j] = temp;
                }
                i++;
                j--;
            } while (i <= j);
            if (j - left <= right - i) {
                if (left < j) QuickSort(map, left, j);
                left = i;
            }
            else {
                if (i < right) QuickSort(map, i, right);
                right = j;
            }
        } while (left < right);
    
}
```

可以看到它在比较两个数值大小时调用的是CompareKeys方法，而Comparekeys方法源码：
```
 internal override int CompareKeys(int index1, int index2) {
    int c = comparer.Compare(keys[index1], keys[index2]);
    if (c == 0) {
        if (next == null) return index1 - index2;
        return next.CompareKeys(index1, index2);
    }
    return descending ? -c : c;
}
```

keys就是我们的那个随机数数组，采用的是默认比较器也就是int类型的比较，
所以这个快排，会根据key值大小来改变map下标上对应的i,而这个i就是我们传入的数组的每个元素所在的数组下标，所以在sort之后，他的代码：
for (int i = 0; i < buffer.count; i++) 
		yield return buffer.items[map[i]];
返回数组下标为map[i]的元素，所以OrderBy的意义在于，根据key值排序传入的数组，但并不会真的对新数组做排序操作，map数组本质上表示一个映射关系，输入为原数组的顺序索引，输出为经过keys数组排序后新数组的索引。这样说比较难理解，画张图也许能对你有帮助。
![示意图](./Snipaste_2023-04-26_23-17-30.jpg)