快速枚举协议：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更有效。
语法很简洁。
如果在枚举时修改集合，枚举器将引发异常。
可以同时执行多个枚举。

快速枚举的行为根据集合的类型略有不同。数组和集合枚举它们的内容，字典枚举它们的键。

2. 如何让自定义的类支持快速枚举？

让自己定义的类遵守NSFastEnumeration协议，实现下面的方法即可：

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

哇！一切看起来似乎很简单～

2.1 什么是NSFastEnumerationState？有何作用？

NSFastEnumerationState是一个结构体，和NSFastEnumeration协议一起在NSEnumerator.h中被定义。

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

state：在forin的方法内部并未使用，从苹果的示例代码中可以看出它是留给开发者在实现NSFastEnumeration协议方法的时候用的；
itemsPtr：C语言数组的指针，该数组存放了“此次”待枚举的items。数组获取指定位置的item的时间复杂度是O(1)，这也是快速枚举效率高的原因之一；
mutationsPtr：在集合中的元素被枚举时，记录该集合是否被改变，若改变则会抛出异常；
extra：和state一样留给开发者使用；具体用途在两个实例中有体现。

2.1 为什么需要一个缓冲区buffer？len又是什么？

len很好理解它表示buffer缓冲区的长度(length)。

buffer是一个C语言的数组id []。对于不同类型集合来说它们存储元素的方式不同，比如向量vector(也可以简单的等同于数组)中的元素是连续存储的，元素的逻辑地址和存储地址是一致的：v[i] = v[0] + i * sizeof(item)；而对于链表来说就不满足这样的特性，它获取指定位置的元素的时间复杂度是O(n)。为了保持统一和提高效率，就需要一个buffer将这些逻辑地址连续的元素放在一起。

buffer.jpg

3. 实例一

自定义类ALFastEnumObject

3.1 `ALFastEnumObject.h`

/// 声明该类遵守NSFastEnumeration协议
@interface ALFastEnumObject : NSObject <NSFastEnumeration>
@end

3.2 `ALFastEnumObject.mm`

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

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

使用C++中的向量作为实际要存储的元素的数据结构。

@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;
    /// 当连续调用-countByEnumeratingWithState:objects:count:的时候，使用state->state记录已经枚举过的item的数量
    unsigned long countOfItemsAlreadyEnumerated = state->state;
    if (countOfItemsAlreadyEnumerated == 0) {
        state->mutationsPtr = &state->extra[0];
    }
#ifdef ItemPhysicalAddressisIsNotSuccessive //#1: 物理地址不连续，使用stackBuffer
    /// 提供待枚举的item
    if (countOfItemsAlreadyEnumerated < _list.size()) {
        state->itemsPtr = buffer;/// 查找元素是从buffer中查找
        while ((countOfItemsAlreadyEnumerated < _list.size()) && (count < len)) {
            buffer[count] = _list[countOfItemsAlreadyEnumerated];/// 将元素放到buffer中
            countOfItemsAlreadyEnumerated ++;/// 记录数量
            count ++;/// 返回此次待枚举item的数量
        }
    } else { /// 已经枚举完成，我们已经提供了所有的item。通过返回值为0告诉调用者，调用者可以根据count==0判断是否枚举已经完成
        count = 0;
    }
#else //#2: 物理地址连续，不使用stackBuffer直接使用_list作为“缓冲区”
    if (countOfItemsAlreadyEnumerated < _list.size()) {
        /// 一次返回所有要枚举的item，可以理解为把_list.data()当作了缓冲区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
    /// 放入缓冲区后，即可更新state->state为已枚举的对象
    state->state = countOfItemsAlreadyEnumerated;
    return count;
}
@end

总结一下实现NSFastEnumeration协议方法的关键：

使用NSFastEnumerationState->state记录已经枚举过的元素的个数，当枚举元素多的集合时协议方法会多次调用，(NSFastEnumerationState *)state会在调用之间传递；
根据缓冲区的长度和剩余待枚举的元素的个数填充buffer；
方法的返回值为填充到buffer中的元素的个数；
state->extra[0]作为记录集合是否被修改的标识：state->mutationsPtr = &state->extra[0];，开始第一次枚举元素时countOfItemsAlreadyEnumerated == 0初始化它。

4. 实例二：使用链表作为实例存储元素的数据结构

4.1 定义链表的节点类

创建一个C++文件ALLinkedList.cpp(不创建头文件)，然后将文件名改为ALLinkedList.mm，这样就简单的构建了一个C++的编码环境。

template <typename T>
class ALNode {
public:
// 成员
    T data;
    ALNode<T>* next; /// 指向下一个同类型的节点
// 构造函数
    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;        // 规模
    ALNode<T>* header;// 头节点
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;
    }
};

这里定义了一个只带有头节点的链表。

从公有的append的方法可以看出往尾部插入一个元素的时间复杂度为O(n)，时间主要消耗在查找最后一个节点上。当然了，若链表定义尾节点的话时间复杂度会变为O(1)。

append_one_item.jpg
clear清空实在链表被销毁析构函数被调用时执行，时间复杂度O(n)，需要对每个节点调用delete操作。

clear_one_item.jpg

4.3 重新定义`NSFastEnumeration`协议方法

#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()); /// 存储最后一个已经枚举的节点，头节点无需枚举正好作为最后一个已经枚举的节点
    }
    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中的节点，也就是最后一个已经枚举的节点
    } else {
        count = 0;
    }
    state->state = countOfItemsAlreadyEnumerated;
    return count;
}
- (void)dealloc {
    delete _list; /// 不要忘记销毁在init方法中new出来的对象。
}
@end

此方法与之间的不同点有：

必须使用协议方法中buffer
NSFastEnumerationState->extra的第二个字段state->extra[1]用来存储最后一个已经枚举的节点，当再次调用协议方法时从该字段取值并在链表中往后查找节点直至末尾或buffer填满。
buffer中直接填充节点数据部分buffer[count] = insertToBuffer->data;

4.4 验证

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

测试中的buffer的大小为16，当集合中的元素个数大于16时NSFastEnumeration协议方法会调用多次。

5. 为什么会抛出 `Collection was mutated while being enumerated.`的异常？

简单的来说就是多次调用协议方法时，方法的state参数为同一个，但state的mutationsPtr指针所指向的值发生的变化。

对实例二中的协议方法稍做修改：

state->extra[0] = arc4random(); /// *** 新增：修改state->extra[1]的同时也修改[0]
state->extra[1] = (unsigned long)(insertToBuffer); /// 最后一个放入buffer中的节点，也就是最后一个已经枚举的节点

其它地方都一样，再次运行就会抛出Collection was mutated while being enumerated.的异常，然而我们并没有对集合进行修改。

6. forin循环的源码分析

简单的命令行应用：

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

在命令行中进入main.m所在的文件夹，执行命令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);/// 获取当前片中元素个数
    if (limit) { /// 大于0时开始两层循环
    unsigned long startMutations = *enumState.mutationsPtr;
    do { /// 外层是能分多少片
        unsigned long counter = 0;
        do { /// 内层是每片有多少元素
            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解决

源码中抛出异常的调用就是objc_enumerationMutation(l_collection);查看objc4-646的源码中可以看到具体实现：

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时调用该Handler。所以只要系统提供为我们设置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);/// 规避异常
    }
    return self;
}

需要说明的是这种规避异常的方法就有全局效应，以后无论是否是使用ALListedListFastEnumerator集合类还是系统其它的集合类都不会Crash～