一、前言，

在iOS消息机制过程中存在两种查找imp 的方式，另外一种就是慢速查找，我们都知道快速就是走汇编流程，因为汇编本身就计算机能识别的语言。所以并且上一篇文章已经着重介绍了快速查找流程，本文我们着重介绍一下慢速查找流程。

我们在项目中创建一个类LGPerson 继承自NSObject然后创建改类对象的示例方法；

@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayNB;
- (void)sayMaster;
- (void)say666;
- (void)sayHello;

@end

在main.m 文件中生成相应的对象实现

         LGPerson *person = [LGPerson alloc];
        [person say666];

我们用断点调试相关的say666 方法，然后进入相应的方法查找流程；

二，慢速查找

1，断定定位

首先我们跟着断点调试进入编译流程，进入XCode的 Debug > 下的 Debug WorkFlow 下的 Always show Disamessbly 界面如下

图片.png

在此信息中我们能看你的的是我们创建的当前对象 LGPerson 以及我们调用的方法 say666,我们再次 control + step into 进入

图片.png

此时我们能看到相应的调试信息已经跳转的相应位置是_objc_msgSend_uncached,我们顺着再次进入调试信息到：

图片.png

通过调试方法我们最终定位到，慢速查找流程最终执行的是lookUpImpOrForward 在objc-runtime-new.mm:的弟 6099行；
当然我们用快速查找流程的 CheckMiss 也可以进入同样的位置信息。定义如下；

.macro CheckMiss
    // miss if bucket->sel == 0
.if $0 == GETIMP
    cbz p9, LGetImpMiss
.elseif $0 == NORMAL
    cbz p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
    cbz p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

我们使用的是NORMAL,所以执行的是 __objc_msgSend_uncached 和上边的查找流程一模一样；

2，源码分析

顺着代码我们定位到相应的方法里；

lookUpImpOrForward(nil, sel, cls, LOOKUP_RESOLVER);

进入后代码的实现如下：

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();

........................................

此处代码很多，我们逐一的分析；

代码段1

 const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    // Optimistic cache lookup
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }

首先定义了一个forward_imp 类型为 _objc_msgForward_impcache,吧imp 设置为nil; 然后开始共缓存本类的缓存中取imp;因为我们在做某些操作的时候很有可能内存已经进行缓存；所以优先取自己的缓存列表；

代码段2 checkIsKnownClass(cls); 判断当前类是否是我们已知的类，因为只有系统熟悉，也就是我们创建的类对象，才能进行相应的属性、列表，协议以及分类等方法的写入，从而才能进行查找流程。
代码段3

 if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        // runtimeLock may have been dropped but is now locked again
    }

进入到最终的实现代码定义如下

 class_rw_t *rw;
    Class supercls;
    Class metacls;

    if (!cls) return nil;
    if (cls->isRealized()) return cls;
    ASSERT(cls == remapClass(cls));

    // fixme verify class is not in an un-dlopened part of the shared cache?

    auto ro = (const class_ro_t *)cls->data();
    auto isMeta = ro->flags & RO_META;
    if (ro->flags & RO_FUTURE) {
        // This was a future class. rw data is already allocated.
        rw = cls->data();
        ro = cls->data()->ro();
        ASSERT(!isMeta);
        cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE);
    } else {
        // Normal class. Allocate writeable class data.
        rw = objc::zalloc<class_rw_t>();
        rw->set_ro(ro);
        rw->flags = RW_REALIZED|RW_REALIZING|isMeta;
        cls->setData(rw);
    }
   supercls = realizeClassWithoutSwift(remapClass(cls->superclass), nil);
    metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);

代码只摘取了片段，次片段的主要作用是取出当前类对象的data()数据，和我们之前读取的类的bits_t一样，取出过后对相应的ro,rw等赋值，确保类对象所有的数据结构都存在并且不为空；

最后两句代码也是非常的重要，起作用大致就是把相关的继承链都实现，从而确保了isa走位图的流通，
以及元类都存在；

isa走位图.png

也就是进行相应的初始化操作，确保我们所需与查找的流程以及环境的初始化

代码段4

if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);

    }

也就是系统调用的一些初始化方法，包括load 和initialize,这些方法都不需要我们自己手动的调用，系统在创建的时候就已经为我们调用了；

3，imp的查找

所有的方法查找都是先从自己的缓存方法列表中查询，因为自己有实现了就没必要查找父类方法了，这样会节省时间和性能，从而节约资源

Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }

从当前类方法列表查找代码如下

ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp();
    int methodListHasExpectedSize = mlist->entsize() == sizeof(method_t);
    
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        for (auto& meth : *mlist) {
            if (meth.name == sel) return &meth;
        }
    }

#if DEBUG
    // sanity-check negative results
    if (mlist->isFixedUp()) {
        for (auto& meth : *mlist) {
            if (meth.name == sel) {
                _objc_fatal("linear search worked when binary search did not");
            }
        }
    }
#endif

    return nil;
}

从代码的源码中我们就知道相关的查找算法是二分查找，
二分法原理

在用二分法进行查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的大小顺序存储的。其基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。具体做法是：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。

时间复杂度

1.最坏情况查找最后一个元素（或者第一个元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情况查找中间元素O(1)查找的元素即为中间元素（奇数长度数列的正中间，偶数长度数列的中间靠左的元素）

空间复杂度

S(n)=logn

有若干个数按由小到大的顺序存放在一个一维数组中，输入一个数x，用二分查找法找出x是数组中第几个数组元素的值。如果x不在数组中，则输出“无此数！”。
（1）编程思路。
设有一数组a[n]，数组中的元素按值从小到大排列有序。用变量low、high和mid分别指示待查元素所在区间的下界、上界和中间位置。初始时，low=0，high=n-1。
1）令 mid = (low+ high) /2 。
2）比较给定值x与a[mid]值的大小
若a[mid] == x ，则查找成功，结束查找；
若a[mid]> x ，则表明给定值x只可能在区间low ~ mid-1内，修改检索范围。令high=mid-1，low值保持不变；
若a[mid]< x ，则表明给定值x只可能在区间mid+1~high内，修改检索范围。令low=mid+1，high值保持不变。
3）比较当前变量low和high的值，若low≤high，重复执行第1）、2）两步，若low>high，表明数组中不存在待查找的元素，查找失败。
例如，设一有序的数组中有11个数据元素，它们的值依次为{3，8，15，21，35，54，63，79，82，92，97}，用二分查找在该数组中查找值为82和87的元素的过程如图1所示。

image

这样我们就能快速查找到我们相应的方法了，通过方法编号去查找，快速有效；

1 如果查找成功就进行相应的 log_and_fill_cache操作，即 cache_fill(cls, sel, imp, receiver); 到cache->insert(cls, sel, imp, receiver); 也就是我上一篇文章所提到的cache_t流程，写入自己的缓存，方便以后方法调用的时候查找，从而达到快速的目的；
2 如果查找失败，则进入父类的方法列表中查询；

if (slowpath((curClass = curClass->superclass) == nil)) {
            // No implementation found, and method resolver didn't help.
            // Use forwarding.
            imp = forward_imp;
            break;
        }

此时我们能知道所有类对象和父类之间是一个双向列表的关系；

curClass = cls;
curClass = curClass->superclass

如果查找成功就进行相应的 log_and_fill_cache操作，即 cache_fill(cls, sel, imp, receiver); 到cache->insert(cls, sel, imp, receiver); 如果查找失败，跳出循环；

4，递归查找

当从我们创建的类对象的method_list 和父类method_list都没找到相应的方法实现是；我们就会进入

  imp = cache_getImp(curClass, sel);

cache_getImp(curClass, sel);;
全局搜索能发现我们的方法进入

STATIC_ENTRY _cache_getImp

    mov r9, r0
    CacheLookup NORMAL, _cache_getImp
    // cache hit, IMP in r12
    mov r0, r12
    bx  lr          // return imp
    
    CacheLookup2 GETIMP, _cache_getImp
    // cache miss, return nil
    mov r0, #0
    bx  lr

    END_ENTRY _cache_getImp

所有我们进入了CacheLookup 然后又会进入到 lookUpImpOrForward,所以此方法会来回的递归，知道找到nil为止，

5、动态方法解析；

以上4个步骤就是所有的查找流程，从创建的对象LGPerson 自身开始，一直带父类，再到根类一直到NSObject如果都没找到相应的方法实现，那么就会进入一下代码，然后进行一次动态拯救的机会

if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
   }

我们断点调试进入会发现程序在执行到这里之前是不会报错的

图片.png

所以即使所有的类中都查找了没找到我们调用的方法实现，但是只要我们在这之前进行了次动态方法解析，告诉系统我们会执行相应的操作，那么系统是不会存在报错问题的。

进行动态解析后系统又会继续调用lookUpImpOrForward 从而检测到该方法的实现

三，总结；

上一篇文章我们已经详细的介绍了快速的查找流程，此次是着重介绍方法机制的慢速查找，这样就完整的介绍了在消息调用机制中的方法查找流程，此次学习是个人的一个记录和成长，还请各位大神多多指教。

iOS消息机制的慢速查找流程

iOS消息机制的慢速查找流程

一、前言，

二，慢速查找

1，断定定位

2，源码分析

3，imp的查找

时间复杂度

空间复杂度

4，递归查找

5、动态方法解析；

三，总结；