前言
之前有讲到过，OC当中几乎所有的方法调用到底层都是消息的发送 objc_msgSend ，也探讨了如何从cache 中通过 cmd 获取 imp 这些流程。但是当我们从缓存当找不到 imp 的时候又该怎么办呢？
前面我们在class 的探讨中提到过 bits 当中存储量很多的属性、方法等。
前面我们在 objc_msgSend() 的查找过程中提到 objc_msgSend_uncached 这个方法，这个方法表示缓存查找不到，那么我们就从 objc_msgSend_uncached 这个方法入手。
汇编缓存找不到
通过搜索 __objc_msgSend_uncached 我们可以找到 MethodTableLookup 才是关键
MethodTableLookup
于是我们去找 MethodTableLookup 这个方法，在这个方法里面我们最终找到了由 C++ 实现的 lookUpImpOrForward 方法。
.macro MethodTableLookup
SAVE_REGS MSGSEND
// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
// receiver and selector already in x0 and x1
mov x2, x16 //赋值，把x16（ cls ） 赋值给 x2
mov x3, #3 // x3 = 3
bl _lookUpImpOrForward
// IMP in x0
mov x17, x0
// 由于这里吧 imp 放在了x0里面，所以x0 应该就是上一个 跳转的事件的返回值。所以我们的直接就去寻找 _lookUpImpOrForward，
// 但是全局搜索 _lookUpImpOrForward 过程中发现没有，于是乎我们就搜索 lookUpImpOrForward
// 发现在 objc-runtime-new 里面定义了 lookUpImpOrForward 这个方法。
RESTORE_REGS MSGSEND
.endmacro
这里也说明了，我们 objc_msgSend 发送消息通过 cmd 获取 imp 的过程是先用汇编在 cache 里面查找，如果找不到了又会采用 C++ 继续查找。
接下来我们去看 lookUpImpOrForward 这个过程。
通过整个方法结果看到最后是一个 return imp; 的过程，所以我们的整个流程就是去查找 imp 什么时候赋值的。于是有了下面这段代码
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
......
/// 这里是个死循环 for (<#initialization#>; <#condition#>; <#increment#>) 通过这个定义可以知道， condition 没有，也就是没有终止条件。
for (unsigned attempts = unreasonableClassCount();;) {
/// isConstantOptimizedCache 这个方法从其具体的定义和实现的判断（objc_cache.mm 里面）只有在真机的环境下才会有可能存在。
if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
/// 这里也印证了只有真机的环境才需要这样做。有可能在查找的过程中有了缓存，那么直接返回。
imp = cache_getImp(curClass, sel);
if (imp) goto done_unlock;
curClass = curClass->cache.preoptFallbackClass();
#endif
} else {
// curClass method list.
Method meth = getMethodNoSuper_nolock(curClass, sel);
/// 这里才是真正的去获取 imp的流程
if (meth) {
imp = meth->imp(false);
goto done; /// 获取到了imp 直接 goto done
}
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break;
}
}
// Halt if there is a cycle in the superclass chain.
if (slowpath(--attempts == 0)) {
_objc_fatal("Memory corruption in class list.");
}
// Superclass cache.
imp = cache_getImp(curClass, sel);
/// 如果还是获取不到那么就去从父类厘米获取，然后又走cache 那套流程这样形成一个递归像上的流程。
/// 如果一旦获取到了，那么应该走上面的 goto done， 下面的 goto done 判断应该只是一个放置意外吧。
if (slowpath(imp == forward_imp)) {
// Found a forward:: entry in a superclass.
// Stop searching, but don't cache yet; call method
// resolver for this class first.
break;
}
if (fastpath(imp)) {
// Found the method in a superclass. Cache it in this class.
goto done;
}
}
......
return imp;
}
通过上面的分析，我们最终找打了 getMethodNoSuper_nolock -> search_method_list_inline 这个方法， 最后找到了 findMethodInSortedMethodList 这个方法。findMethodInSortedMethodList 这个方法就是我们的查找流程，由于是排好序的，所以按照最优解就是二分查找法。于是就到了我们二分查找法去查找 imp 的过程了。
慢速查找流程
是应该去找父类还是去找方法列表。
在整个查找的主线中有点小问题
二分查找
上面最终找到了 findMethodInSortedMethodList 这个方法，那么我们去看看 findMethodInSortedMethodList 的实现。
template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
ASSERT(list);
auto first = list->begin(); /// 获取第一个
auto base = first;
decltype(first) probe; /// 这个是我们想要返回的结果。
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
/**
假如我们一共有 8 个方法，即 count = 8 , 那么 probe 就应该是从 0 ～7 当中，假定结果为7，key = 7，最后一个
即：base = 0， probe = 0，key = 7， count = 8
那么第一次for 循环相当于
for (count = 8, count !=0, count = 4) count >>= 1 -> count = count >> 1 -> 1000 >> 1 = 0100 = 4
count = 8, base = 0;
probe = 0 + 4 = 4;
4 != 7 所以查找失败
由于 7 > 4 ,所以 base = 5 ， count = 3
进入第二次循环
coun = 3, base = 5
probe = base + count >> 1 = 5 + 1 = 6;
由于 6 != 7
所以没查找失败
由于 7 > 6 , 所以 count = 2-1 = 1, base = probe + 1 = 6 + 1 = 7
第三次循环
count = 1, base = 7
probe = base + count >> 1 = 7+0 = 7
由于7 == 7 ，所以查找成功
*/
for (count = list->count; count != 0; count >>= 1) {
probe = base + (count >> 1);
/// 获取probe 的name ，其实就是 SEL
uintptr_t probeValue = (uintptr_t)getName(probe);
if (keyValue == probeValue) {
// `probe` is a match.
// Rewind looking for the *first* occurrence of this value.
// This is required for correct category overrides.
while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
/// 这里就是 category 的同名方法是怎么存的就怎么取。也就是最后编译的同名方法在前面，这个就是循环取最前面的一个。
probe--;
}
/// 从结果看，这里是有这个才是有用的返回，那么结果必然会到这里。
return &*probe;
}
//如果没有找到， 并且value 大于当前查找的 key，说明在后面，那么下次的循环就变成
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
同理，比如我们要找小端位置的结果呢？如下所示。
如果我们查找小的呢，比如0号位置。
base = 0， probe = 0，key = 0， list.count = 8
那么第一次为
for (8, 8 != 0, 8 >>= 1)
probe = base + count >> 1 = 0 + 4
因为 4 != 0 ，所以查找失败
由于 0 > 4 不成立，所以 base 和 count 不变
第二次循环
count = 4, base = 0
probr = base + count >> 1 = 0 + 2 = 2
因为 2 != 0 所以查找失败
由于 0 > 2 不成立， 所以 base 和 count 不变
第三次
count = 2, base = 0
probr = base + count >> 1 = 0 + 1 = 1
因为 1 != 0 所以查找失败
由于 0 > 1 不成立， 所以 base 和 count 不变
第四次
count = 1, base = 0
probr = base + count >> 1 = 0 + 0 = 0
因为 0 == 0 ，所以查找成功，返回
通过上面的结果，我们找到了有可能找到了imp， 但是如果没有找到呢？
看看几个判断.
- 1、判断 getSuperclass 是否为空，如果为空，那么就执行 forward_imp。
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break;
}
- 2、imp = cache_getImp(curClass, sel); 递归像父类查找
到此处，如果imp 存在，那么我们一定可以找到，然后执行 goto done;
done:
if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
cls = cls->cache.preoptFallbackClass();
}
#endif
log_and_fill_cache(cls, imp, sel, inst, curClass);
}
log_and_fill_cache 这个最后又会执行 cache.insert
总结：
这里需要一张流程图
