经过上一篇 消息快速发送之 objc_msgSend 的分析 对调用方法的时候，通过汇编查询 Cache 如果 缓存命中 就直接进行发送。

但是上一篇的结尾说到，如果没有命中缓存就需要走慢速流程，也就是来到 _class_lookupMethodAndLoadCache3 函数里面，接下来就是对慢速流程的探索。

1、进入慢速转发 _class_lookupMethodAndLoadCache

/***********************************************************************
* _class_lookupMethodAndLoadCache.
* Method lookup for dispatchers ONLY. OTHER CODE SHOULD USE lookUpImp().
* This lookup avoids optimistic cache scan because the dispatcher 
* already tried that.
**********************************************************************/
/*
译文：
* _class_lookupMethodAndLoadCache。
*只查找调度程序的方法。其他代码应该使用lookUpImp()。
*这种查找避免了乐观缓存扫描，因为调度程序已经尝试过了。
*/
IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{
    return lookUpImpOrForward(cls, sel, obj, 
                              YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}

复制代码

上方的翻译可以看到，调用 _class_lookupMethodAndLoadCache3 函数的时候， cache 传入的是NO，因为在快速流程中已经查找过了，也告诉了开发者，其他地方使用 lookUpImpOrForward 函数，这意味着 lookUpImpOrForward() 调用的地方将会很多。

2、lookUpImpOrForward()函数的探索

看函数名称就知道这里是查找方法的实现或者消息转发，一起进入这个函数看看吧，这个函数很长，我们慢慢分析。

/***********************************************************************
* lookUpImpOrForward.
* The standard IMP lookup. 
* initialize==NO tries to avoid +initialize (but sometimes fails)
* cache==NO skips optimistic unlocked lookup (but uses cache elsewhere)
* Most callers should use initialize==YES and cache==YES.
* inst is an instance of cls or a subclass thereof, or nil if none is known. 
*   If cls is an un-initialized metaclass then a non-nil inst is faster.
* May return _objc_msgForward_impcache. IMPs destined for external use 
*   must be converted to _objc_msgForward or _objc_msgForward_stret.
*   If you don't want forwarding at all, use lookUpImpOrNil() instead.
**********************************************************************/

/**
 * lookUpImpOrForward。
 * 标准IMP查找。
 * initialize==NO 尝试避免+初始化(但有时会失败)
 * cache==NO 跳过乐观解锁查找(但在其他地方使用缓存)
 * 大多数调用者应该使用initialize==YES和cache==YES。
 * inst是cls或其子类的一个实例，如果不知道，则为nil。
 * 如果cls是一个未初始化的元类，那么非空的inst会更快。
 * 可能返回_objc_msgForward_impcache。用于外部使用的imp必须转换为_objc_msgForward或_objc_msgForward_stret。
 * 如果根本不想转发，可以使用lookUpImpOrNil()。
 */


IMP lookUpImpOrForward(Class cls, SEL sel, id inst, 
                       bool initialize, bool cache, bool resolver)
{
    IMP imp = nil;
    bool triedResolver = NO;

    runtimeLock.assertUnlocked();

    // Optimistic cache lookup
    // 乐观的缓存查找
    // 这里如果传入的 cache 为 YES ，就查找一次 cache, 如果 imp 存在，就直接返回了。
    if (cache) {
        imp = cache_getImp(cls, sel);
        if (imp) return imp;
    }

    // runtimeLock is held during isRealized and isInitialized checking
    // to prevent races against concurrent realization.

    // runtimeLock is held during method search to make
    // method-lookup + cache-fill atomic with respect to method addition.
    // Otherwise, a category could be added but ignored indefinitely because
    // the cache was re-filled with the old value after the cache flush on
    // behalf of the category.
    
    // runtimeLock 在isrealize和isInitialized检查过程中被持有，以防止对并发实现的竞争。
    // runtimeLock 在方法搜索过程中保持，使方法查找+缓存填充原子相对于方法添加。
    // 否则，可以添加一个类别，但是无限期地忽略它，因为在代表类别的缓存刷新之后，缓存会用旧值重新填充。

    // 上方的说明就是对这里加锁的解释
    runtimeLock.lock();
    
    // 如果运行时知道这个类(位于共享缓存中，加载的图像的数据段中，或者已经用obj_allocateClassPair分配了)，
    // 则返回true，
    // 如果没有就崩溃了
    checkIsKnownClass(cls);

    //锁定:为了防止并发实现，持有runtimeLock。
    if (!cls->isRealized()) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        // runtimeLock may have been dropped but is now locked again
    }

    if (initialize && !cls->isInitialized()) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
        // runtimeLock may have been dropped but is now locked again

        // If sel == initialize, class_initialize will send +initialize and 
        // then the messenger will send +initialize again after this 
        // procedure finishes. Of course, if this is not being called 
        // from the messenger then it won't happen. 2778172
    }


 retry:    
    runtimeLock.assertLocked();

    // Try this class's cache.
    // 先查询一遍缓存
    imp = cache_getImp(cls, sel);
    
    // 如果imp 存在就跳转 done，done里面就2行代码，
    //（PS:实现在该方法最后两行，下方再次看到 goto done，就是 return imp 的意思，不再说明）
    
    if (imp) goto done;

    // Try this class's method lists.
    // 在该对象的所属的类的方法列表中查找
    
    //  { } 代表作用域，作用域中声明的变量出了作用域就会释放，所以可以进行多个同名的声明。
    {
        //使用二分查找法
        Method meth = getMethodNoSuper_nolock(cls, sel);
        if (meth) {
            // 如果找到了就填充到缓存中
            log_and_fill_cache(cls, meth->imp, sel, inst, cls);
            imp = meth->imp;
            goto done;
        }
    }

    // Try superclass caches and method lists.
    // 从父类中查找
    {
        unsigned attempts = unreasonableClassCount();
        for (Class curClass = cls->superclass;
             curClass != nil;
             curClass = curClass->superclass)
        {
            // Halt if there is a cycle in the superclass chain.
            if (--attempts == 0) {
                _objc_fatal("Memory corruption in class list.");
            }
            
            // Superclass cache.
            // 寻找父类的缓存中有没有
            imp = cache_getImp(curClass, sel);
            if (imp) {
                if (imp != (IMP)_objc_msgForward_impcache) {
                    // Found the method in a superclass. Cache it in this class.
                    log_and_fill_cache(cls, imp, sel, inst, curClass);
                    goto done;
                }
                else {
                    // Found a forward:: entry in a superclass.
                    // Stop searching, but don't cache yet; call method 
                    // resolver for this class first.
                    break;
                }
            }
            
            // Superclass method list.
            // 寻找父类的方法列表中有没有
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                log_and_fill_cache(cls, meth->imp, sel, inst, curClass);
                imp = meth->imp;
                goto done;
            }
        }
    }

    // No implementation found. Try method resolver once.
    // 没有找到就进行消息转发
    if (resolver  &&  !triedResolver) {
        runtimeLock.unlock();
        resolveMethod(cls, sel, inst);
        runtimeLock.lock();
        // Don't cache the result; we don't hold the lock so it may have 
        // changed already. Re-do the search from scratch instead.
        triedResolver = YES;
        goto retry;
    }

    // No implementation found, and method resolver didn't help. 
    // Use forwarding.

    //没有实现消息转发就进入 _objc_msgForward_impcache 的汇编了
    imp = (IMP)_objc_msgForward_impcache;
    cache_fill(cls, sel, imp, inst);

 done:
    runtimeLock.unlock();

    return imp;
}
复制代码

3、 二分查找法的分析 getMethodNoSuper_nolock ()

苹果在查找方法列表的时候使用了 二分查找法，二分查找法有一个前提条件就是 有序数组，我们经常能看到苹果将方法的 SEL sel 强转成整形，这里整形就是有序的~。

有了这个前提，我们看看 getMethodNoSuper_nolock 的代码：

1、getMethodNoSuper_nolock()

getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();

    assert(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    // 二分查找
    // 在 objc_object 的 class_rw_t *data() 的 methods 。
    // beginLists : 第一个方法的指针地址。
    // endLists : 最后一个方法的指针地址。
    
    for (auto mlists = cls->data()->methods.beginLists(), 
              end = cls->data()->methods.endLists(); 
         mlists != end;
         ++mlists)
    {
        method_t *m = search_method_list(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

复制代码

2、findMethodInSortedMethodList ()

static method_t *findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    assert(list);

    const method_t * const first = &list->first;
    const method_t *base = first;
    const method_t *probe;
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
  
  
    for (count = list->count; count != 0; count >>= 1) {
        probe = base + (count >> 1); //从一半开始找起
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        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)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}
复制代码

分析一下上述逻辑：

 /**
  * count ： 初始值为方法列表的个数 假设 48
  * 1、如果 count != 0; 循环条件每次 右移一位  也就是说 除以 2;
  * 2、 第一次进入 从一半开始找起，如果 keyValue > probeValue 那么在右边，否则在左边;
  * 3、 第二次是从 12 开始找起，也不满足 keyValue > probeValue 的条件;
  * 4、 第二次从 6 开始找起，满足条件 keyValue > probeValue，将初始值移动到当前 6 的后一位
        也就是从 7 开始查找，然后count--, 
        可以看到当前 count = 5 ，然后在对 > 6 且 < 12 进行查找，
        也就是 7 - 11 ，count >> 1 为 2， 7+2 = 9，刚好是 7 - 11 的中心。
  * 5、这就是 2分查找法，但是前提是有序数组。
  */
复制代码

4、没有实现的方法 Xcode 是怎么崩溃的？

IMP lookUpImpOrForward(Class cls, SEL sel, id inst, 
                       bool initialize, bool cache, bool resolver)
{
    //...
    
    // No implementation found. Try method resolver once.
    // 没有找到就进行消息转发
    if (resolver  &&  !triedResolver) {
        runtimeLock.unlock();
        resolveMethod(cls, sel, inst);
        runtimeLock.lock();
        // Don't cache the result; we don't hold the lock so it may have 
        // changed already. Re-do the search from scratch instead.
        triedResolver = YES;
        goto retry;
    }

    // No implementation found, and method resolver didn't help. 
    // Use forwarding.

    //没有实现消息转发就进入 _objc_msgForward_impcache 的汇编了
    imp = (IMP)_objc_msgForward_impcache;
    cache_fill(cls, sel, imp, inst);

 done:
    runtimeLock.unlock();

    return imp;
}
复制代码

上方方法列表的查找就不需要多说了，在最后看到了两段代码，一段是消息转发，我们下一篇说明，还有一段就是 imp = (IMP)_objc_msgForward_impcache; ，这是一段汇编。搜索 _objc_msgForward_impcache，看到如下代码：

    STATIC_ENTRY __objc_msgForward_impcache

    // No stret specialization.
    b	__objc_msgForward

    END_ENTRY __objc_msgForward_impcache

	
    ENTRY __objc_msgForward

    adrp	x17, __objc_forward_handler@PAGE
    ldr	p17, [x17, __objc_forward_handler@PAGEOFF]
    TailCallFunctionPointer x17
	
    END_ENTRY __objc_msgForward

复制代码

上述代码发现调用了 _objc_forward_handler 函数，继续搜索，得到如下结果：

void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

// Default forward handler halts the process.
__attribute__((noreturn)) void 
objc_defaultForwardHandler(id self, SEL sel)
{
    _objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
                "(no message forward handler is installed)", 
                class_isMetaClass(object_getClass(self)) ? '+' : '-', 
                object_getClassName(self), sel_getName(sel), self);
}
复制代码

呵~，这不就是我们经常看到的 Xcode 找不到方法的崩溃信息吗？

到这里，消息查找流程就全部完成了，下一篇会探索 如果方法没有实现，OC 是怎么消息的转发的。

PS: 消息查找流程（上）- 消息快速发送 之 objc_msgSend 分析

PS:可以运行的并且不断进行注释的objc_756.2 源码地址。