试验 ruby迭代器奇怪的漏洞bug

qbjxiaolei

ruby当中，数组和hash数据结构都可以使用迭代器。假设一个数组，遍历每一个元素，其中每访问一个元素，调用这个元素的一个方法update，使在遍历过程中又删除该数组中的某些元素，这个遍历结果会怎么样。

在Game_Map当中设置usr_events并初始化为[]，update_events方法中迭代usr_events。
[pre lang="ruby" line="1"]def update_events
    @events.each_value {|event| event.update }
    @common_events.each {|event| event.update }
  
    @usr_events.each {|event| event.update}
  end[/pre]

然后写一个如下的测试类：


然后我们初始化3个Test类的实例id,i各为0,1,2。然后在一开始的时候加入game_map.usr_events。


然后我们预测一下结果，理想情况下是0，1，2，1，2，2 这样的，一轮删除一个元素。0，1，2第一轮；1，2第二轮；2第三轮的。
实际结果却是如下：

0，2，1，2，1，2这种。

分析原因：
我们可以假设这种迭代器是没有考虑在遍历过程中还会删除某些元素的。那么我估计它会是这样实现的。
[pre lang="ruby" line="1"]i=0;
while i<usr_events.size
usr_events.update
i+=1;
end[/pre]
那么就会出此类问题。一开始数组是[0,1,2]这样一个结构。i=0的时候遍历0号元素，结果0号元素在执行delete的时候删除了自身导致整个数组结构成了[1,2]。但是代码并没有理会这层结构变化依然将i++;i=1的时候遍历的元素是2号元素，这样就导致了在这次遍历过程中忽略了1号元素。所以在上面那个例子显示0过后不是1而是跳过了1显示2了。

总结：
在遍历数组的时候最好不要删除元素和往数组当中插入元素，这会导致数组遍历混乱，绝对不是你想要的结果。如果向我上面那种在事件中动态添加删除事件，假设总事件是n，那么最坏情况下可能有一个事件会遍历了(1/4)n^2才会得到一次遍历机会。在巨量添加事件的情况下可能会导致巨大的延迟。

qbjxiaolei

不晓得有没有好的解决方案啊

qbjxiaolei

晴兰 发表于 2012-10-10 07:46
上一楼在审核，简而言之就是迭代器如果允许数组是可变的，怎么都会导出矛盾，所以只能是不变的，但代码逻辑 ...

为什么只有晴兰大神回复我的帖子，其实实际情况可以灵活看待就不一定一定是逻辑错误了。就比如说动态添加和删除事件的这个例子，如果我们把Game_Map看作是操作系统代码的话，每一个event就可以看作是一个独立的线程，event中的update函数就是线程函数，而Game_Map迭代events其实就相当于不停地在给每个线程分配时间片，逻辑上来说每个event能正常执行的话我们只要保证event当中的update是线程安全的函数或者update是解决了竞争关系的函数就可以了，一个event偶尔点背被系统不公平得剥夺了一两个Cpu时间片在逻辑上是无关紧要的。

qbjxiaolei

晴兰 发表于 2012-10-10 08:39
这个实际上不能类比OS，因为你删除了任务之后并不能自己去维护任务链表，所以并不是一个OS的功能。

总 ...

额，我这么想的。不把它当os，就把游戏当作一个进程，而event就可以看作是用户态的线程(不是内核上的)，而那个迭代器就算是简单的线程调度吧。我们可以默认认为多个event谁先迭代到谁后迭代到，或谁迭代次数多，谁次数少都是不定的话。我们要解决同步问题的话就落在了update本身里面了，比如在里面加入互斥量之类的。这样的话至少在event层面是不会出问题的。

6rp

从后面删除吧。
a.reverse.each{|e| ...}

qbjxiaolei

的确，删除后面的元素不会出问题应该，但是删除的元素位置大多都是不确定的可是。虽然性能会降低，我还是这样修改吧，遍历中要删除的元素放在一个其他的数组中，等遍历结束后再来删除。