快速枚舉協(xié)議：NSFastEnumeration

問題

下面的代碼輸出是什么凌净？會不會Crash寻狂？如果Crash解釋一下原因邓萨。

NSMutableArray *array = [NSMutableArray arrayWithObjects:@"1",@"2",@"3",@"4",@"5",@"6",@"7", nil];
for (NSString *obj in array) {
    if ([obj isEqualToString:@"3"]) {
        [array removeObject:obj];
    }
    NSLog(@"%@", array);
}

答案

控制臺的輸出給出了所有的答案：

2019-04-26 14:58:45.449992+0800 MyProject[8112:1804104] (
    1,
    2,
    3,
    4,
    5,
    6,
    7
)
2019-04-26 14:58:45.450151+0800 MyProject[8112:1804104] (
    1,
    2,
    3,
    4,
    5,
    6,
    7
)
2019-04-26 14:58:45.450281+0800 MyProject[8112:1804104] (
    1,
    2,
    4,
    5,
    6,
    7
)
2019-04-26 14:59:01.597547+0800 MyProject[8112:1804104] *** Terminating app due to uncaught exception 'NSGenericException', reason: '*** Collection <__NSArrayM: 0x600001491770> was mutated while being enumerated.'
*** First throw call stack:
(
    0   CoreFoundation                      0x000000010be3b1bb __exceptionPreprocess + 331
    1   libobjc.A.dylib                     0x000000010e469735 objc_exception_throw + 48
    2   CoreFoundation                      0x000000010be37e9c __NSFastEnumerationMutationHandler + 124
    ......
)
libc++abi.dylib: terminating with uncaught exception of type NSException

Crash信息中明確指出了原因：Collection was mutated while being enumerated.集合在枚舉其中的元素的時候被修改了蠕嫁。

探究

1. 什么是快速枚舉锨天？

蘋果的官方文檔中提到，快速枚舉是枚舉集合的首選方法剃毒，它有一下有點：

枚舉比直接使用NSEnumerator更有效病袄。
語法很簡潔。
如果在枚舉時修改集合赘阀，枚舉器將引發(fā)異常益缠。
可以同時執(zhí)行多個枚舉。

快速枚舉的行為根據(jù)集合的類型略有不同基公。數(shù)組和集合枚舉它們的內(nèi)容幅慌，字典枚舉它們的鍵。

2. 如何讓自定義的類支持快速枚舉轰豆？

讓自己定義的類遵守NSFastEnumeration協(xié)議胰伍，實現(xiàn)下面的方法即可：

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state 
                                  objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer 
                                    count:(NSUInteger)len;

哇！一切看起來似乎很簡單～

2.1 什么是NSFastEnumerationState酸休？有何作用骂租？

NSFastEnumerationState是一個結構體，和NSFastEnumeration協(xié)議一起在NSEnumerator.h中被定義斑司。

typedef struct {
    unsigned long state;
    id __unsafe_unretained _Nullable * _Nullable itemsPtr;
    unsigned long * _Nullable mutationsPtr;
    unsigned long extra[5];
} NSFastEnumerationState;

state：在forin的方法內(nèi)部并未使用渗饮，從蘋果的示例代碼中可以看出它是留給開發(fā)者在實現(xiàn)NSFastEnumeration協(xié)議方法的時候用的；
itemsPtr：C語言數(shù)組的指針宿刮，該數(shù)組存放了“此次”待枚舉的items互站。數(shù)組獲取指定位置的item的時間復雜度是O(1)，這也是快速枚舉效率高的原因之一糙置；
mutationsPtr：在集合中的元素被枚舉時，記錄該集合是否被改變是目，若改變則會拋出異常谤饭；
extra：和state一樣留給開發(fā)者使用；具體用途在兩個實例中有體現(xiàn)懊纳。

2.1 為什么需要一個緩沖區(qū)buffer揉抵？len又是什么？

len很好理解它表示buffer緩沖區(qū)的長度(length)嗤疯。

buffer是一個C語言的數(shù)組id []冤今。對于不同類型集合來說它們存儲元素的方式不同，比如向量vector(也可以簡單的等同于數(shù)組)中的元素是連續(xù)存儲的茂缚，元素的邏輯地址和存儲地址是一致的：v[i] = v[0] + i * sizeof(item)戏罢；而對于鏈表來說就不滿足這樣的特性屋谭，它獲取指定位置的元素的時間復雜度是O(n)。為了保持統(tǒng)一和提高效率龟糕，就需要一個buffer將這些邏輯地址連續(xù)的元素放在一起桐磁。

buffer.jpg

3. 實例一

自定義類ALFastEnumObject

3.1 `ALFastEnumObject.h`

/// 聲明該類遵守NSFastEnumeration協(xié)議
@interface ALFastEnumObject : NSObject <NSFastEnumeration>
@end

3.2 `ALFastEnumObject.mm`

#import "ALFastEnumObject.h"
#include <vector>

@interface ALFastEnumObject ()
{
    std::vector<NSNumber *> _list;
}
@end

使用C++中的向量作為實際要存儲的元素的數(shù)據(jù)結構。

@implementation ALFastEnumObject

- (instancetype)init {
    self = [super init];
    if (self) {
        for (NSInteger i = 0; i < 20; i ++) {
            _list.push_back(@(i));
        }
    }
    return self;
}
#define ItemPhysicalAddressisIsNotSuccessive 1
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state
                                  objects:(id  _Nullable __unsafe_unretained [])buffer
                                    count:(NSUInteger)len {
    NSUInteger count = 0;
    /// 當連續(xù)調(diào)用-countByEnumeratingWithState:objects:count:的時候讲岁，使用state->state記錄已經(jīng)枚舉過的item的數(shù)量
    unsigned long countOfItemsAlreadyEnumerated = state->state;
    if (countOfItemsAlreadyEnumerated == 0) {
        state->mutationsPtr = &state->extra[0];
    }
#ifdef ItemPhysicalAddressisIsNotSuccessive //#1: 物理地址不連續(xù)我擂，使用stackBuffer
    /// 提供待枚舉的item
    if (countOfItemsAlreadyEnumerated < _list.size()) {
        state->itemsPtr = buffer;/// 查找元素是從buffer中查找
        while ((countOfItemsAlreadyEnumerated < _list.size()) && (count < len)) {
            buffer[count] = _list[countOfItemsAlreadyEnumerated];/// 將元素放到buffer中
            countOfItemsAlreadyEnumerated ++;/// 記錄數(shù)量
            count ++;/// 返回此次待枚舉item的數(shù)量
        }
    } else { /// 已經(jīng)枚舉完成，我們已經(jīng)提供了所有的item缓艳。通過返回值為0告訴調(diào)用者校摩，調(diào)用者可以根據(jù)count==0判斷是否枚舉已經(jīng)完成
        count = 0;
    }
#else //#2: 物理地址連續(xù)，不使用stackBuffer直接使用_list作為“緩沖區(qū)”
    if (countOfItemsAlreadyEnumerated < _list.size()) {
        /// 一次返回所有要枚舉的item阶淘，可以理解為把_list.data()當作了緩沖區(qū)buffer
        __unsafe_unretained const id * const_array = _list.data();
        state->itemsPtr = (__typeof(state->itemsPtr))const_array;
        /// 我們必須返回在state->itemsPtr中有多少對象
        countOfItemsAlreadyEnumerated = _list.size();
        count = _list.size();
    } else {
        count = 0;
    }
#endif
    /// 放入緩沖區(qū)后衙吩，即可更新state->state為已枚舉的對象
    state->state = countOfItemsAlreadyEnumerated;
    return count;
}
@end

總結一下實現(xiàn)NSFastEnumeration協(xié)議方法的關鍵：

使用NSFastEnumerationState->state記錄已經(jīng)枚舉過的元素的個數(shù)，當枚舉元素多的集合時協(xié)議方法會多次調(diào)用舶治，(NSFastEnumerationState *)state會在調(diào)用之間傳遞分井；
根據(jù)緩沖區(qū)的長度和剩余待枚舉的元素的個數(shù)填充buffer；
方法的返回值為填充到buffer中的元素的個數(shù)霉猛；
state->extra[0]作為記錄集合是否被修改的標識：state->mutationsPtr = &state->extra[0];尺锚，開始第一次枚舉元素時countOfItemsAlreadyEnumerated == 0初始化它。

4. 實例二：使用鏈表作為實例存儲元素的數(shù)據(jù)結構

4.1 定義鏈表的節(jié)點類

創(chuàng)建一個C++文件ALLinkedList.cpp(不創(chuàng)建頭文件)惜浅，然后將文件名改為ALLinkedList.mm瘫辩，這樣就簡單的構建了一個C++的編碼環(huán)境。

template <typename T>
class ALNode {
public:
// 成員
    T data;
    ALNode<T>* next; /// 指向下一個同類型的節(jié)點
// 構造函數(shù)
    ALNode(T e, ALNode<T>* next = NULL) {
        this->data = e;
        this->next = next;
    }
};

4.2 定義鏈表

也是在ALLinkedList.mm中：

template <typename T>
class ALLinkedList {
private:
    int _size;        // 規(guī)模
    ALNode<T>* header;// 頭節(jié)點
protected:
    void init() {
        this->header = new ALNode<T>;
        this->header->next = NULL;
        this->_size = 0;
    }
    void clear() {
        ALNode<T>* deleteNodePtr = header->next;
        while (deleteNodePtr != NULL) {
            header->next = deleteNodePtr->next;
            delete deleteNodePtr;
            _size --;
            
            deleteNodePtr = header->next;
        }
    }
public:
    ALLinkedList() {
        init();
    }
    ~ALLinkedList() {
        clear();
        delete header;
    }
    
    void append(T const&  data) {
        ALNode<T> *readyToInsert = new ALNode<T>(data);
        
        ALNode<T> *lastNode = header;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }
        lastNode->next = readyToInsert;
        _size ++;
    }
    int size() {
        return _size;
    }
    ALNode<T>* headerNode() {
        return header;
    }
};

這里定義了一個只帶有頭節(jié)點的鏈表坛悉。

從公有的append的方法可以看出往尾部插入一個元素的時間復雜度為O(n)伐厌，時間主要消耗在查找最后一個節(jié)點上。當然了裸影，若鏈表定義尾節(jié)點的話時間復雜度會變?yōu)镺(1)挣轨。

append_one_item.jpg
clear清空實在鏈表被銷毀析構函數(shù)被調(diào)用時執(zhí)行，時間復雜度O(n)轩猩，需要對每個節(jié)點調(diào)用delete操作卷扮。

clear_one_item.jpg

4.3 重新定義`NSFastEnumeration`協(xié)議方法

#import "ALLinkedList.mm"
@interface ALListedListFastEnumerator ()
{
    ALLinkedList<NSString *> *_list;
}
@end
@implementation ALListedListFastEnumerator
- (instancetype)init {
    self = [super init];
    if (self) {
        _list = new ALLinkedList<NSString *>;
        for (NSInteger i = 0; i < 18; i ++) { /// 測試code
            _list->append([NSString stringWithFormat:@"%ld", i]);
        }
    }
    return self;
}

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state
                                  objects:(id  _Nullable __unsafe_unretained [])buffer
                                    count:(NSUInteger)len {
    NSUInteger count = 0;
    unsigned long countOfItemsAlreadyEnumerated = state->state;
    if (countOfItemsAlreadyEnumerated == 0) {
        state->mutationsPtr = &state->extra[0];
        state->extra[1] = (unsigned long)(_list->headerNode()); /// 存儲最后一個已經(jīng)枚舉的節(jié)點，頭節(jié)點無需枚舉正好作為最后一個已經(jīng)枚舉的節(jié)點
    }
    if (countOfItemsAlreadyEnumerated < _list->size()) {
        state->itemsPtr = buffer;
        ALNode<NSString *>* lastEnumeratedItem = (ALNode<NSString *>*)(state->extra[1]);
        ALNode<NSString *>* insertToBuffer = lastEnumeratedItem->next;
        while (insertToBuffer != NULL) {
            buffer[count] = insertToBuffer->data;
            countOfItemsAlreadyEnumerated ++;
            count ++ ;
            
            if (count < len) {
                insertToBuffer = insertToBuffer->next;
            } else {
                break;
            }
        }
        state->extra[1] = (unsigned long)(insertToBuffer); /// 最后一個放入buffer中的節(jié)點均践，也就是最后一個已經(jīng)枚舉的節(jié)點
    } else {
        count = 0;
    }
    state->state = countOfItemsAlreadyEnumerated;
    return count;
}
- (void)dealloc {
    delete _list; /// 不要忘記銷毀在init方法中new出來的對象晤锹。
}
@end

此方法與之間的不同點有：

必須使用協(xié)議方法中buffer
NSFastEnumerationState->extra的第二個字段state->extra[1]用來存儲最后一個已經(jīng)枚舉的節(jié)點，當再次調(diào)用協(xié)議方法時從該字段取值并在鏈表中往后查找節(jié)點直至末尾或buffer填滿彤委。
buffer中直接填充節(jié)點數(shù)據(jù)部分buffer[count] = insertToBuffer->data;

4.4 驗證

ALListedListFastEnumerator *list = [[ALListedListFastEnumerator alloc] init];
for (NSString *obj in list) {
    NSLog(@"%@", obj);
}

測試中的buffer的大小為16鞭铆，當集合中的元素個數(shù)大于16時NSFastEnumeration協(xié)議方法會調(diào)用多次。

5. 為什么會拋出 `Collection was mutated while being enumerated.`的異常焦影？

簡單的來說就是多次調(diào)用協(xié)議方法時车遂，方法的state參數(shù)為同一個封断，但state的mutationsPtr指針所指向的值發(fā)生的變化。

對實例二中的協(xié)議方法稍做修改：

state->extra[0] = arc4random(); /// *** 新增：修改state->extra[1]的同時也修改[0]
state->extra[1] = (unsigned long)(insertToBuffer); /// 最后一個放入buffer中的節(jié)點艰额，也就是最后一個已經(jīng)枚舉的節(jié)點

其它地方都一樣澄港，再次運行就會拋出Collection was mutated while being enumerated.的異常，然而我們并沒有對集合進行修改柄沮。

6. forin循環(huán)的源碼分析

簡單的命令行應用：

int main(int argc, char * argv[]) {
    @autoreleasepool {   
        for (id obj in @[@"1", @"2", @"3"]) {
            NSLog(@"%@", obj);
        }
        return 0;
    }    
}

在命令行中進入main.m所在的文件夾回梧，執(zhí)行命令clang -rewrite-objc main.m可以得到編譯后的文件main.cpp：

int main(int argc, const char * argv[]) {
    /* @autoreleasepool */ { __AtAutoreleasePool __autoreleasepool; 
        {
    id obj;
    struct __objcFastEnumerationState enumState = { 0 }; /// 分片枚舉時傳遞的state
    id __rw_items[16]; /// 每片能容納16個元素
    id l_collection = (id) ((NSArray *(*)(Class, SEL, ObjectType  _Nonnull const * _Nonnull, NSUInteger))(void *)objc_msgSend)(objc_getClass("NSArray"), sel_registerName("arrayWithObjects:count:"), (const id *)__NSContainer_literal(3U, (NSString *)&__NSConstantStringImpl__var_folders_8f_c7chq5p16z54819ns4hxvgwm0000gp_T_main_8d9ab2_mi_0, (NSString *)&__NSConstantStringImpl__var_folders_8f_c7chq5p16z54819ns4hxvgwm0000gp_T_main_8d9ab2_mi_1, (NSString *)&__NSConstantStringImpl__var_folders_8f_c7chq5p16z54819ns4hxvgwm0000gp_T_main_8d9ab2_mi_2).arr, 3U);
    _WIN_NSUInteger limit =
        ((_WIN_NSUInteger (*) (id, SEL, struct __objcFastEnumerationState *, id *, _WIN_NSUInteger))(void *)objc_msgSend)
        ((id)l_collection,
        sel_registerName("countByEnumeratingWithState:objects:count:"),
        &enumState, (id *)__rw_items, (_WIN_NSUInteger)16);/// 獲取當前片中元素個數(shù)
    if (limit) { /// 大于0時開始兩層循環(huán)
    unsigned long startMutations = *enumState.mutationsPtr;
    do { /// 外層是能分多少片
        unsigned long counter = 0;
        do { /// 內(nèi)層是每片有多少元素
            if (startMutations != *enumState.mutationsPtr) /// 比較每次mutationsPtr指向的值
                objc_enumerationMutation(l_collection);
            obj = (id)enumState.itemsPtr[counter++]; { /// 直接從buffer中獲取元素
            NSLog((NSString *)&__NSConstantStringImpl__var_folders_8f_c7chq5p16z54819ns4hxvgwm0000gp_T_main_8d9ab2_mi_3, obj);
        };
    __continue_label_1: ;
        } while (counter < limit);
    } while ((limit = ((_WIN_NSUInteger (*) (id, SEL, struct __objcFastEnumerationState *, id *, _WIN_NSUInteger))(void *)objc_msgSend)
        ((id)l_collection,
        sel_registerName("countByEnumeratingWithState:objects:count:"),
        &enumState, (id *)__rw_items, (_WIN_NSUInteger)16)));
    obj = ((id)0);
    __break_label_1: ;
    }
    else
        obj = ((id)0);
    }

    }
    return 0;
}

7. Crash解決

源碼中拋出異常的調(diào)用就是objc_enumerationMutation(l_collection);查看objc4-646的源碼中可以看到具體實現(xiàn)：

static void (*enumerationMutationHandler)(id);
void objc_enumerationMutation(id object) {
    if (enumerationMutationHandler == nil) {
        _objc_fatal("mutation detected during 'for(... in ...)'  enumeration of object %p.", (void*)object);
    }
    (*enumerationMutationHandler)(object);
}
void objc_setEnumerationMutationHandler(void (*handler)(id)) {
    enumerationMutationHandler = handler;
}

可以看出當enumerationMutationHandler為nil時拋出異常，不為nil時調(diào)用該Handler祖搓。所以只要系統(tǒng)提供為我們設置enumerationMutationHandler的接口方法即可避免拋出異常狱意。

在<objc/message.h>有方法：

/** 
 * Sets the current mutation handler. 
 * 
 * @param handler Function pointer to the new mutation handler.
 */
OBJC_EXPORT void
objc_setEnumerationMutationHandler(void (*_Nullable handler)(id _Nonnull )) 
    OBJC_AVAILABLE(10.5, 2.0, 9.0, 1.0, 2.0);

所以在# 5.拋出異常的測試代碼上修改ALListedListFastEnumerator的-init方法：

#import <objc/message.h>
void defaultHandler(id objt) {
    NSLog(@"在%@的快速枚舉過程中集合被修改了～",objt);
}
- (instancetype)init {
    self = [super init];
    if (self) {
        _list = new ALLinkedList<NSString *>;
        for (NSInteger i = 0; i < 18; i ++) {
            _list->append([NSString stringWithFormat:@"%ld", i]);
        }
        objc_setEnumerationMutationHandler(defaultHandler);/// 規(guī)避異常
    }
    return self;
}

需要說明的是這種規(guī)避異常的方法就有全局效應，以后無論是否是使用ALListedListFastEnumerator集合類還是系統(tǒng)其它的集合類都不會Crash～