OC底层-慢速查找

• OC底层-objc_msgSend我们探索了cache_t的方法缓存插入。
• OC底层-runtime我们大概看了下cache缓存的查找流程

方法的查找分为快速查找和慢速查找，今天我们先来探索下方法的慢速查找，看看苹果工程师的设计思路，以及这种设计的优点。

慢速查找流程

1、之前我们探索的时候看到方法调用实际就是调用objc_msgSend进行消息发送，然后我们通过汇编代码看到objc_msgSend先机械能判断消息发送对象是否合法，发送的消息是否合法等等。

2、通过以上汇编代码跟流程走，大概能够得到如下的一个流程图：

3、之前探索的时候，没有注意一个细节，那就是在objc-cache.m文件中有这样一段注释：

4、苹果明确给出解释当触发objc_msgSend的时候，缓存查找以及添加缓存的主流程。那么我们按照这个主流程，去看下慢速查找的过程，因为上面我们分析了大概的缓存查找流程，我们只看到了查找不到的时候返回空值，并没有看到找到后赋值的过程，所以经过再次阅读，发现忽略了又一个细节__objc_msgSend_uncached，在调用CacheLookup的时候传入了四个参数，但是没有详细去看第四个参数，而正是忽略的第四个参数，才是查找过程的重点，所以回过头重新看下这个函数。

5、我们可以看到这个__objc_msgLookup_uncached中只调用了一个MethodTableLookup函数，然后就直接返回了，那么我们就去看下这个函数的具体实现：

6、在这个函数中首先将获取到的class也就是消息发送者保存到x2寄存器，然后将x3寄存器赋值为3，然后跳转到_lookUpImpOrForward函数，函数执行完成后，从x0寄存器读取IMP然后保存到x17寄存器。那么我们再去看下_lookUpImpOrForward函数的实现，我们之前分析的时候就看到这个是个C函数，所以直接在objc源码搜索lookUpImpOrForward，找到后进入函数实现如下：

7、在这块就牵扯出来我们iOS中isa最重要的一张图：

8、慢速查找的流程再结合isa的走位图，我们最终可以得到如下一个流程图：

isInitialized

我们之前探索类的底层的时候介绍过类的底层结构，主要包含以下几点：

1、我们看下isInitialized函数，这个函数就是通过isa然后读取bits然后通过bits读取flags，然后将得到的flags进行一步与运算，具体代码如下：

2、我们能够看到这时候的flags是33320，我们放在计算器看下这个十六进制数据和#define RW_INITIALIZED (1<<29)的结果是1左移19位：

3、通过计算器转16进制后，结果是1000 0010 0010 1000，1左移19位结果是0010 0000 0000 0000 0000 0000 0000两个数据进行且运算，结果是0000 0000 0000 0000 0000 0000 0000，最终结果是0，也就是返回false。

4、然后我们通过断点调式查看结果，如果是alloc或者new的时候都是走未初始化的结果，打印如下：

checkIsKnownClass

1、这个函数是为了检测是否是系统在编译时期，通过objc_duplicateClass、objc_initializeClassPair、objc_allocateClassPair合法注册的类，具体实现如下：

2、然后在调用了isKnownClass，系统也有相应的注释，就是在isa->bits->witness保存了类是否是系统在编译时期通过objc_duplicateClass、objc_initializeClassPair、objc_allocateClassPair合法注册的类。

realizeAndInitializeIfNeeded_locked

1、首先按照惯例先看下这个函数的具体实现如下：

2、这个函数就做了两件事情：第一、检测是否实现给定的类，如果没有实现，进行实现；第二、给定的类是否初始化，如果没有进行初始化。

3、我们首先看下第一个判定是否实现类的判定，这块调用了isa->bits->flags然后进行与运算，将获取到的flags与1<<31，通过断点可以看到这块获取到的值如下：

main.m中的代码如下：

然后运算结果如下：

3580144： 0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0110 1010 0000 1111 0000
1 << 31： 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
结   果：  0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
复制代码

经过以上运算后结果是false，也就是类没有实现，然后if (slowpath(!cls->isRealized())) {...}取的是非，所以会走if判断的分支，然后对类进行实现。

4、然后我们看下第二个判定是否对类进行了初始化操作，这块调用了isa->bits->flags然后进行与运算，将获取到的flags与1<<29，通过断点可以看到这块获取到的值如下：

然后运算结果如下：

3580144： 0000 0000 0000 0000 0000 0011 0110 1010 0000 1111 0000
1 << 29： 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
结   果：  0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
复制代码

经过上面的运算，得到的最终结果是false，然后取非，外部传入的initialize是true，所以这块最终结果是true也会走对类的初始化操作。

getMethodNoSuper_nolock

1、这个函数是获取当前类的方法列表，然后遍历查找IMP，我们继续看下具体代码：

2、然后我们继续往下看search_method_list_inline函数的实现：

3、外面处理逻辑只是按照method的长度进行位移读取method，我们重点看下search_method_list_inline函数的实现：

4、上面函数主要是进行搜索读取排序好的方法列表或者未排序的方法列表，重点我们继续看findMethodInSortedMethodList函数的实现：

5、以上就是方法查找的最后节点了，如果在这里查不到，那么久返回nil开始走转发流程了。

findMethodInSortedMethodList

1、在这个方法中，苹果把二分查找可以说用到了极致啊，我们看下具体做法以及代码：

2、首先在外层定义了一个方法列表的最大值计算，这块用个图，我感觉更加直观一些：

3、我们解读下这块的算法，假设这个得到的count是14，所以运算过程如下：

count = 14;base = 0; probe = 0;
第一次循环：
probe = base + (count>>1);
probe =   0  +   14>>1
probe =   0  +   1110>>1
probe =   0  +   0110
probe =   0  +   6
probe =   6
base  =   6 + 1 = 7
第二次循环
probe = base + (count>>1);
probe =   7  +   14>>1>>1
probe =   7  +   1110>>1>>1
probe =   7  +   0110>>1
probe =   7  +   0010
probe =   7  +   2
probe =   9
base  =   10
第三次循环
probe = base + (count>>1);
probe =   10 +   14>>1>>1>>1
probe =   10 +   1110>>1>>1>>1
probe =   10 +   0110>>1>>1
probe =   10 +   0010>>1
probe =   10 +   0001>>1
probe =   10 +   1
probe =   11
base  =   12
复制代码

4、然后苹果工程师，还有一个细微的操作，那就是获取父类的时候(curClass = curClass->getSuperclass()) == nil)先取父类，然后再去判断是否nil，这样就能够让方法查找按照isa的走位图去向上查询。

总结

方法调用到消息发送，再到方法查找是一个整体流程，只是这个流程中苹果做了很多细节的优化以及容错判断，所以我们读源码的时候看起来比较乱，但是当你走完一遍流程，然后总结出来主线后，你会发现很简单，除了主线流程其他都是容错处理以及细节优化。