先看一个sort.Slice重写比较函数的例子
sort.Slice(intervals, func(i, j int) bool {
// 闭包
return intervals[i][0] < intervals[j][0]
})
注意到上面的Slice的第二个比较函数就用到了闭包,引用了intervals,要注意这里的intervals会通过后面的less函数间接操作。我们再来看一下Slice的源码部分,any是type any = interface{} 空接口eface
func Slice(x any, less func(i, j int) bool) {
rv := reflectValueOf(x)
swap := reflectSwapper(x)
length := rv.Len()
quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
reflectValueOf和reflectSwapper是两个位于internal/reflectlite包中的两个函数类型,这里简单提一下reflectlite包,其实就是reflect包的一种轻量级实现方式,省去了大量的方法
先看ValueOf,函数的目的就是返回空接口对应的Value类型,如果是空指针就直接返回0值。
// ValueOf returns a new Value initialized to the concrete value
// stored in the interface i. ValueOf(nil) returns the zero Value.
func ValueOf(i any) Value { // type any interface{}
if i == nil {
return Value{}
}
// TODO: Maybe allow contents of a Value to live on the stack.
// For now we make the contents always escape to the heap. It
// makes life easier in a few places (see chanrecv/mapassign
// comment below).
escapes(i)
return unpackEface(i)
}
escapes(i)这里非常有意思,乍一看感觉什么都没有做,因为dummy结构体在初始化的时候b会初始为false,所以escapes里的if语句是根本不会执行的。golang的逃逸分析是在编译期Escape Analysis完成的,所以这个操作的目的就是为了让编译器对变量x百分百执行逃逸操作,也不会因为内联等发生改变。
func escapes(x any) {
if dummy.b {
dummy.x = x
}
}
var dummy struct {
b bool
x any
}
unpackEface就如同其字面意思,将一个EmptyInterface转换为Value类型。Value就是一个结构体如下,其中typ是大多数value类型的共有部分,rtype定义在reflectlite/type.go文件中,Type ptr 指向的是value所对应的实际类型所存储的数据。Value把flag作为了匿名成员,类似于在flag基础上派生,将flag的方法都作为己用。
type Value struct {
// typ holds the type of the value represented by a Value.
typ *rtype
// Pointer-valued data or, if flagIndir is set, pointer to data.
// Valid when either flagIndir is set or typ.pointers() is true.
ptr unsafe.Pointer
flag
Swapper函数省略大部分common情况判断的代码,先通过Kind()接口判断类型是否为Slice,这里的判断底层要依靠Value结构体中的flag。
func Swapper(slice any) func(i, j int) {
v := ValueOf(slice)
if v.Kind() != Slice {
panic(&ValueError{Method: "Swapper", Kind: v.Kind()})
}
// Fast path for slices of size 0 and 1. Nothing to swap.
switch v.Len() {
...
}
typ := v.Type().Elem().(*rtype)
size := typ.Size()
hasPtr := typ.ptrdata != 0
// Some common & small cases, without using memmove:
if hasPtr {
...
} else {
...
}
s := (*unsafeheader.Slice)(v.ptr)
tmp := unsafe_New(typ) // swap scratch space
return func(i, j int) {
if uint(i) >= uint(s.Len) || uint(j) >= uint(s.Len) {
panic("reflect: slice index out of range")
}
val1 := arrayAt(s.Data, i, size, "i < s.Len")
val2 := arrayAt(s.Data, j, size, "j < s.Len")
// typedmemmove copies a value of type t to dst from src.
typedmemmove(typ, tmp, val1)
typedmemmove(typ, val1, val2)
typedmemmove(typ, val2, tmp)
}
}
注意到arrayAt最后一个传参为string类型,读者可能会好奇怎么通过一个string来进行条件判断呢?答案是代码根本无法照此进行判断,所以这个whySafe string更多的是让调用者能够在coding的过程中注意到该需求,否则会有越界风险,这个风格实属首次见到。
总之一个小小的sort.Slice重写比较函数涉及到了go的栈逃逸,reflect等等。后面有机会再把reflect和逃逸分析好好整理一下。