方法慢速查找流程分析

慢速查找前提

obj_msgsend消息发送在完成汇编缓存快速查找流程后，如果没有找到，说明缓存没有，那么就需要进入到C/C++层进入慢速查找lookUpImpOrForward流程。

消息查找过程与isa走位联系

消息在查找过程中如果在自己类中没有找到，那么就会去父类找，如果父类还是没有找到就会找到其根源类，如同isa的走位图一般。
我们可以通过下面案例演示，首先我们新建一个继承自NSObject 的类SYPerson，再建一个继承自SYPerson类的SYMan类，然后再建一个NSObject分类，如图

类名

我们在SYMan中声明两个方法,同时在SYPerson和NSObject+SY中添加同样的方法

- (void)sayHello;
+ (void)say666;

//实现

- (void)sayHello{
    NSLog(@"%s",__func__);
}

+ (void)say666{
    NSLog(@"%s",__func__);
}

//调用
SYMan *man = [SYMan alloc];

[man sayHello];

[SYMan say666];

首先，我们在SYMan中实现两个方法，然后调用打印，毫无疑问直接打印如下

2020-09-22 21:22:41.968785+0800 KCObjc[28236:428912] -[SYMan sayHello]
2020-09-22 21:22:41.969886+0800 KCObjc[28236:428912] +[SYMan say666]

现在，我们将SYMan中方法的实现注释，在其父类SYPerson中实现这两个方法，那么我们执行会打印什么呢？会不会崩溃呢？结果如下:

2020-09-22 21:25:35.352163+0800 KCObjc[28366:431785] -[SYPerson sayHello]
2020-09-22 21:25:35.352965+0800 KCObjc[28366:431785] +[SYPerson say666]

从上诉打印我们发现，在SYMan类中虽然没有实现方法，但是我们在调用的时候并没有崩溃，而是执行了其父类SYPerson的方法实现，说明方法在自身没有实现的时候如果其父类实现了，会找到父类进行执行。
最后我们将SYPerson的方法实现也注释掉，，而是由分类NSObject+SY实现，那么会怎么样了？我们执行打印如下：

2020-09-22 21:29:27.085123+0800 KCObjc[28493:433778] -[NSObject(SY) sayHello]
2020-09-22 21:29:27.085790+0800 KCObjc[28493:433778] +[NSObject(SY) say666]

结果显示虽然自身和父类都没对方法进行实现，但是其根源类NSObject中却实现了调用的时候直接走了分类中的方法实现。

以上我们的主要目的就是为了验证方法消息在查找过程中会存在一个继承链的关系，这在慢速查找
lookUpImpOrForward中是适用的。

通过源码分析消息慢速查找

首先还是找到lookUpImpOrForward的实现源码进行分析

//传入sel方法名，cls调用类名
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    // 再次判断缓存中是否存在，之所以这里要再次判断是因为可能因为多线程等原因，之前缓存没找到，但是后面缓存中又存在了，那么就直接通过缓存快速查找了，不需要进入慢速查找。
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }


    runtimeLock.lock();
    //判断当前类是否已经认可，是已知类
    checkIsKnownClass(cls);

    if (slowpath(!cls->isRealized())) {
    // 递归找到类继承链,做好去父类查找准备
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        
    }

    if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {        
    //递归初始所有类initialize
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

    runtimeLock.assertLocked();
    curClass = cls;
    //这是一个死循环，只有找到了就break
    for (unsigned attempts = unreasonableClassCount();;) {
        // 查找当前类自己是否能找到方法，如果找到就不用去父类找了
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }
        //这里将curClass赋值为其父类
        if (slowpath((curClass = curClass->superclass) == nil)) {
            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);// 这里实现了真正的lookUpImpOrForward递归
     
        if (slowpath(imp == forward_imp)) {
    
            break;
        }
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }
    //如果上诉都没找到方法，那么进入动态方法决议
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

    
 done:
//找到了之后就加入到缓存，方便下次进行快速查找
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
// 不管什么方式都没有找到，那么只有返回nil
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
//返回查找到的imp
    return imp;
}

二分法查找方法

二分查找过程：
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

在系统底层是通过二分法查找方法名对应的IMP，在类初始化的时候method_list是以递增方式存在，二分法查找源码如下：

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) {
        //通过右移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;
}