php

拥抱PHP之在crash中遇见generator

0. crash样本 缘起

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<?php
function p1(){
    yield 1;
    yield 2;
    yield 3;
}

$p1 = p1();

function gen(){
    global $p1;
    yield from $p1; 	
}

$gen = gen();
$gen->rewind();

function child(){
    global $gen;
    yield from $gen;
}

$child = child();
$child->rewind();

function new1() {
    global $p1;
    yield from $p1;
}

$new = new1();
$new->rewind();

$child->next();
$child->next();
$child->next();
echo 1;

在工作时, 偶然之下构造出了上面一个例子, 这个例子会导致PHP7.4和7.3 (全小版本, 后同) 崩掉 (null pointer dereference), 而PHP7.0, PHP7.1, PHP7.2没有崩掉是因为写了一行垃圾代码 (指的是完全没有任何作用且还会带来负面影响的代码) 阴差阳错地导致这个问题被带过了, 从PHP7.3开始这行垃圾代码被拿掉了, 问题就显示出来了. 最后在PHP8中彻底简化了delegated generator tree的构造, 这个问题也自然没有了. 从PHP历史来看, 这个问题一直都没有被发现, 我觉得这和generator内部实现的复杂度是有紧密关系的.

在这里，我必须要吐槽一下相关PHP开发者, delegated generator tree这个结构在PHP7中无比复杂, 文档和相关资料也少的可怜 (基本没有), 导致相关代码读起来会异常难受, 我花费了巨额地时间才彻底理顺逻辑. 借此, 有了这篇文章, 希望将PHP generator内部实现中最复杂的那部分内容, 以尽可能无痛地方式传递给读者或者后来者. 同时这篇文章中也有一些我的小心思, 全文只有一处完整地复制粘贴了PHP内部代码的地方 (一个结构定义), 其余地方我都使用伪代码来描述过程, 因为我不希望此篇文章成为一个类似"读代码的文章"的典范, 而希望是在婉婉道来一个有趣的故事. 另外在读这篇文章的时候, 你不需要对PHP内部有任何的了解, 我保证.

1. Delegated generator tree (委托构造器树)

这一节我们将介绍什么是delegated generator tree.

1.1. Generator 概念速成

首先简要介绍一下 generator (构造器)的概念. 这个feature在很多编程语言 (python 和 ECMAScript等) 中都有存在, 它的概念也并不复杂. 你可以将它理解为"一个特殊的iterator (迭代器), 但是长成了函数的模样". 它是一个iterator意味着它天然地支持一些操作, 比如将iterator指向第一个元素的 rewind操作, 获取iterator当前指向元素的current操作, 将iterator指向下一个元素的 move_forward操作等等, 不同语言上的实现可能有些许不同. 而它长成了函数的样子意味着你可以像函数调用一样去调用它, 但是它的并不会因此而直接执行, 你需要通过前面提到的iterator的相关操作去拨动它. 例如在PHP中一个最简单generator例子为

1
2
3
4
5
6
7
8
9
function gen () {
    yield 1;
    return 2;
}
$gen = gen();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->getReturn(); // output: 2

其中有一个关键字yield, 它的出现就决定了它所在的函数是一个generator. 当你第一次调用这个函数的时候, 你就会得到一个generator实例, 如这里的第5行. 之后你就可以将其视为一个iterator来操作, 如这里的第6-8行. 当你使用rewind()操作时, iterator就会指向它的第一个元素, 对generator而言, 这个操作会告诉它, 开始执行对应的函数, 并且在执行完第一个yield之后停下来, 并将这个yield产生的值视为一个元素. 如这里这个第二行yield执行会产生一个常量1. 值得注意是, 当在generator实例已经开始运行之后, 再使用rewind()操作, 将没有任何作用, 因为PHP不允许rewind一个正在运行的generator实例. 当你使用next()操作时, iterator就会指向它的下一个元素, 对于generatora而言, 这个操作会告诉它, 继续从当前位置执行, 直到下一个yield执行之后再停下来, 或者遇到return直接完成执行. 如这里并没有第二个yield, 使得当前generator实例在执行return之后就关闭了. generator 除了支持必要的iterator操作, 也支持一些其他特殊的操作, 如这里的getReturn()操作, 它可以获取对应generator实例的返回值. 甚至你也可以通过send()操作给generator实例内部传递值. 相关的操作均可以在PHP 官方文档 找到, 这里就不累述了.

1.2. Delegated generator tree的由来

从上面对generator介绍看来, 它并不复杂, 但是引入yield from之后, generator的世界就开始变的复杂了. PHP官方文档对yield from的介绍如下:

Generator delegation allows you to yield values from another generator, Traversable object, or array by using the yield from keyword.

所以yield from对应的机制应该称之为"Generator delegation" (构造器委托), 可以看到它支持3种delegated values, 我们的关注重点delegated value为generator的情况, 后面的两种我们在这里简单介绍一下. 例如

1
2
3
4
5
6
7
8
9
10
function gen () {
    yield from [1,2,3];
}
$gen = gen();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->current(); // output: 2
$gen->next();
echo $gen->current(); // output: 3

当执行yield from之后, 此时iterator会委托给它后面的对象, 因此当我们拨动next方法的时候, 实际在拨动另外一个iterator, 当这个新的iterator被使用完毕之后, 就会返回调用yield from的地方继续执行.

可以想象一下yield from后面的表达式是一个generator实例的时候会发生什么? 为方便描述, 我们将调用yield from的generator称为outer generator, 而被调用的那个generator称为inner generator. 例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function gen1 () {
    yield 1;
    yield 2;
}

function gen2 () {
    yield from gen1();
    yield 3;
}

$gen = gen2();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->current(); // output: 2
$gen->next();
echo $gen->current(); // output: 3

可以看到在使用rewind()操作之后, 指向的第一个元素是由gen1产生的, 这是因为在gen2的一开始, 我们通过yield from 引入了gen1作为delegated value, 在这些值被使用完之前, 原generator不会向下执行. 难道你不觉得这里非常奇妙吗 ? 我们拨动outer generator向前, 却是inner generator在向前, 并且我们对outer generator取值也总是能取到正确的值.

PHP内部究竟是如何实现它的呢？ 不着急, 我们再来看一些更加复杂的例子, 让你对它有一些更深层次的思考, 以便于对后文有更好的理解. 假如我们在gen1也增加一个yield from呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function gen0 () {
    yield 4;	 
}

function gen1 () {
    yield 1;
    yield 2;
    yield from gen0();
}

function gen2 () {
    yield from gen1();
    yield 3;
}

$gen = gen2();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->current(); // output: 2
$gen->next();
echo $gen->current(); // output: 4
$gen->next();
echo $gen->current(); // output: 3

对照函数调用时的call chain, 这里每次调用yield from的时候也会构造一条类似的chain, 我们可以将其称之为delegated generator chain, 比如在第12行这里就会形成gen2 -> gen1, 而在第8行这里就会形成gen2 -> gen1 -> gen0, 其中一个箭头就表示一次yield from执行, 而箭头方向对应outermost到innermost的方向.

这里会给我们一种感觉, 当我们拨动一条delegated generator chain上的某个generator时, 总是会先拨动这条chain上innermost generator. 我们把简单地修改一下上面的例子, 让我们的感觉更加明显:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function gen0 () {
    yield 4;
    yield 5;
    yield 6;
}

function gen1 () {
    yield 1;
    yield 2;
    yield from gen0();
}

function gen2 () {
    global $gen1;
    yield from $gen1;
    yield 3;
}

$gen1 = gen1();
$gen2 = gen2();
$gen2->rewind();
echo $gen2->current(); // output: 1
$gen2->next();
echo $gen2->current(); // output: 2
$gen2->next();
echo $gen2->current(); // output: 4

$gen1->next();
echo $gen1->current(); // output: 5

$gen2->next();
echo $gen2->current(); // output: 6

这里我们单独拿到了gen1的引用, 首先我们三次连续拨动gen2, 在最后一次拨动gen2时, 在gen1中yield from下形成了delegated generator chain为gen2 -> gen1 -> gen0 . 此时gen0作为innermost generator, 所以我们拿到了gen0中第一个yield产生的值. 而后我们换gen1来拨动, gen1也是这条chain上的一个delegated generator, 因此我们拿到了gen0中第二个yield产生的值. 最后我们再切回gen2来拨动, 依然也是预期的值.

所以这里我们给出第一个重要的原则:

Principle1. 假设某个generator处于由yield from生成的delegated generator chain上, 当我们使用next()拨动它时, 会首先拨动它所在chain的innermost generator. 同理使用current()获取当前元素时, 也会去获取该innermost generator指向的元素.

为了节省篇幅, 后面将使用chain来指代delegated generator chian. 聪明的你, 可能要问一个问题了, 有没有可能一个generator位于两条不同的chain中呢 ? 非常好的问题, 答案是肯定存在, 比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function gen0 () {
    yield 0;
    yield 1;
}

function gen1 () {
    global $gen0;
    yield from $gen0;
}

function gen2 () {
    global $gen0;
    yield from $gen0;
}

$gen0 = gen0();
$gen1 = gen1();
$gen2 = gen2();
$gen1->rewind();
$gen2->rewind();
echo $gen1->current();  // output: 0
echo $gen2->current(); // output: 0

在拨动gen1和gen2之后, 就生成了两条具有相同innermost generator的chains, 如下: (我们去掉了chain连线上的箭头, 因为画起来会很乱, 我们约定inner genearator总是在outer generator的上面)

1
2
3
    gen0
   /    \
gen1    gen2

此时gen0位于两条不同的chains中. 咋一看, 这里的结构看起来就是一棵tree, 而一条delegated generator chain实际就是一条root-to-leaf path. 我们需要仔细验证一下, 这里是不是真的符合tree结构, 需要考虑所有delegrated generator chain可能长成的样子出发. 我们默认大家都熟悉基本数据结构Tree中的一些关键词, 比如root结点 (根结点), parent结点 (父节点), child结点 (孩子结点), ancestor结点 (祖先结点), descendant结点 (后继结点).

#1 任意时刻一generator实例只能执行一个yield from.

因此不可能出现以下情况, 这就意味确实可能只存在一个root结点.

1
2
3
gen1    gen2
   \    /
    gen0

#2 PHP不允许环的出现

以下例子会抛出一个异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function gen0 () {
	global $gen1;
	yield 1;
	yield from $gen1;
}

function gen1() {
	yield from gen0();
}

$gen1 = gen1();
$gen1->rewind();
echo $gen1->current();
$gen1->next();

因此我们不用考虑环出现的情况.

综合#1和#2, 我们完全可以用tree结构代替delegated generator chains. 并且我们可以确保 "任一generator在某一时刻只能处于唯一的一颗delegated generator tree上", 换句话说每个generator都有唯一的root结点, 这是因为#1可以保证tree不会分叉. 由此delegated generator tree正式进入我们的视野, 而delegated generator chain只不过是一条root-to-leaf path. 之后我可能会频繁地给出各种形式的delegrated generated trees, 但是为了节省篇幅, 我不会同时给出对应它们的PHP代码了, 默认它们都是可以以某种方式被构造出来的. 在继续往下之前, 我们首先明确(或者强调)几个概念:

  1. 对于一特定的yield from, 它对应的inner generator和outer generator对应delegated generator tree上一对parent-child结点.
  2. 对于一特定的delegated generator tree, 它的每一条root-to-leaf path都对应着一条delegated generator chain, 这些chains拥有相同的innermost genearator, 即为该delegated generator tree的root结点.
  3. 对于一特定的generator, 只能处于唯一确定的delegated generator tree上.

那么这里我们可以给出第二个重要的principle:

Principle2. 给定一个generator, 当我们使用next()拨动它时, 会首先拨动它所在delegated generator tree的root结点. 同理使用current()获取当前元素时, 也会去获取该root结点指向的元素.

注意我们使用 "结点" 指特定的generator. 我们可以将内部没有yield from语句, 且也不是其他generator的delegated generator的generator视为一个tree of single node, 即只有一个结点的tree, 其root结点就是它自己. 为了进一步节省篇幅, 我将直接使用tree来指代delegated generator tree.

PHP内部使用如下结构连接tree上的结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct _zend_generator_node {
	zend_generator *parent; /* NULL for root */
	uint32_t children;
	union {
		HashTable *ht; /* if multiple children */
		struct { /* if one child */
			zend_generator *leaf;
			zend_generator *child;
		} single;
	} child;
	union {
		zend_generator *leaf; /* if > 0 children */
		zend_generator *root; /* if 0 children */
	} ptr;
};

后文我将使用node来指代这个结构, 其中有4个字段:

  1. node.parent用来存储parent结点.
  2. node.single用来存储child结点的个数.
  3. node.child用来存储child结点.
  4. node.ptr用来存储一些信息.

此时你需要对这个结构有一些大致的了解即可. 这是本文唯一一处直接使用PHP内部代码的地方, 因为我们需要用它来描述delegated generator tree的设计. 注意当我们提到结点的时候, 依然指得是某一个特定的generator, 而不是某个node结构. 对于node结构, 我们会使用类似gen.node来指代generator gen中的node结构.

1.3 维护 delegated generator tree 概览

首先要明确我们引入delegated generator tree的核心目的是"为了更好的维护 delegated generator chains", 而delegated generator chain是PHP准确处理任何一个generator的基础. 这里面存在两个难点问题:

  1. 不同层次上的generator如何快速地找到对应的currently executing geneartor? 简而言之如何让delegated generator tree上的各个结点能够快速地找到root结点.
  2. 不同层次上的generator对应的currently executing generator完成执行时, 如何切换到下一个generator继续执行 ?

对于第一个问题, 我们可以有非常直接的方法, 即从指定的结点开始往上遍历node.parent直到root结点. 但是你如果考虑一个非常高的tree和它的一个leaf结点, 每次地拨动这个leaf结点都需要查找一次, 如果这个过程非常频繁, 那么代价并不小. 所以我们是否可以考虑引入类似cache的东西 ? 比如在第一次查找之后就保存这个root结点, 这个方法显然是奏效的, 但是你需要额外维护这个cache. 如果这个root结点已经完成执行了, 你可能需要考虑更新所有引用它的地方, 以免二次误用. 进一步思考, 这个cache可能有多种形式:

  • multiple cache: 允许多个结点保存同一个root结点.

那么必须在root结点处维护一张表, 存储所有引用它的地方, 保证在它被改变之后, 能够及时地更新到引用它的结点.

  • single cache: 一个root结点只允许一个结点引用.

那么我们只需要在root结点上引用这个结点即可.

为什么我们提到这两种cache形式呢 ? 考虑下面的tree

1
2
3
4
5
    gen0
   /
  gen1
 /
gen2

其中gen1和gen2的root结点都是gen0. 在multiple cache下, 无论怎样拨动gen1还是gen2都可以使用cache机制. 而在single cache下, 当我们从拨动gen1切换到gen2或者从gen2切换到gen1时, cache就会失效, 但是连续拨动时依然可以享受到cache带来的好处.

PHP7和PHP8均使用的第二种cache方式, 我将其称之为核心设计1. 但是PHP7还往前走了一步, 这里我们注意到gen1和gen2对应同一个root结点, 那么有没有办法让它们共享这个root结点呢? 并且在root结点上不用同时引用它们两个结点. 答案是,

  1. 在gen1中存一个关于gen2的引用, 而不是直接存root结点.
  2. 在gen2中存root结点.
  3. 在拨动gen1时, 直接从gen2中取root结点.

可以这样做的原因是, 对于一个结点而言, 它和它的所有descendant结点都拥有着相同的root结点. 换言之, 如果它的某个descendant结点已经拥有了关于root结点的引用, 那么我们可以直接去问这个descendant结点要root结点即可. 另外对于这个descendant结点的选择, 应当最好是一个leaf结点, 因为它可以成为更多其他结点的descendant结点. 这就是PHP7中delegated generator tree的独有的核心设计2.

对于第二个问题, 简而言之就是当前root结点完成执行之后, 我们应当如何选择child结点作为新的root结点. 我们考虑两种情况下的tree

1
2
3
4
5
  gen0            gen2
 /                /   \
gen1            gen3   gen4
                /
              gen5

对于左边这颗树, 当gen0完成执行之后, 我们再拨动gen1, 此时gen0只有一个child结点, 所以选择只有一个. 而对于右边这棵树, 同样当gen2完成执行之后, 我们再拨动gen5, 此时gen2有两个child结点, 正确的选择应该是gen3, 那么这里应该如何准确地确定它呢 ? 同样我们可以直接从gen5开始向上遍历, 直到碰到gen2的某个child结点, 这是PHP8中的做法.

而PHP7中的做法则是对每个结点的child结点建立一张索引表, 在返回选择child结点的过程中，我们可以根据当前正在拨动的generator信息查表得到对应的child结点. 这一做法中延续了之前我们刚刚提到的核心设计1. 为理解这一建表过程, 我们从最直觉的方法出发, 再回归PHP7中的方法.

想象我们正在结点gen上存储一个child结点 c, 并且假定这个child结点有一些descendant结点, d1, d2, ..., dn等等. 那么我们在gen上存储一些ordered pairs, (c,c), (c, d1), (c, d2), ... (c, dn). 未来当gen完成执行，我们再次拨动d1, d2, ..., dn中的某个结点di时, 我们可以根据di查询gen中的ordered pairs马上知道我们选择的child结点是c. 这一ordered pair结构显然可以用哈希表来完成 (让di作为index), 这就是PHP7中独有的核心设计3. 如果我们继续深度思考的话, 这里实际可能并不需要存储这么多ordered pairs, 考虑拥有下面结构的c

1
2
3
4
5
6
7
     c
   /   \
  d1   d4
  /
  d2
 / 
d3

类似于前面提到的核心设计, 当c完成执行是, 这里拨动d2 选择的c的child结点, 和拨动任意一个d2的descendant结点选择的c的child结点是一样的. 因此这里我们也可以让d2保存一个d3的引用, 然后我们在c上只需要保存两个ordered pair (d1, d3), (d1, d4) , 并且在查询d2时, 我们转而使用d3来作为查询index, 这就是PHP7中独有的核心设计4. 在实际建表的过程中, 还要更复杂一些, 我们会详细提到.

最后我们小小地总结一下, generator delegated tree有两个需维护重点:

  1. 快速找到一个结点对应的root结点.
  2. 更新已经完成执行的root结点时, 需要快速地找到退回的child结点.

在这两个查找操作中都用到了相同的思想, 即一些结点是可以共用查询的结果, 通过这个fact, 我们希望减少复用结果所带来的空间复杂度, 于是乎诞生了核心设计2和核心设计4. 而核心设计1和核心设计3的思想就比较朴素, 即为了减少遍历tree带来的时间复杂度. 下面几个小节，我们将完整的介绍整个维护过程.

1.4. 维护 Delegated generator tree 之结点初始化

当一个generator实例gen产生的时候, 我可以将它看做只有一个结点的tree, 相关初始化操作如下:

1
2
3
4
5
6
7
function init_gen_node (gen) {
    gen.node.parent = null;
    gen.node.children = 0;
    gen.node.single.child = null;
    gen.node.single.leaf = null;
    gen.node.ptr.root = gen
}

这样一个结点自然是没有parent结点和child结点. 值得注意是我们用到node.ptr, 这里我们有一个约定:

  1. 若给定结点gen是一个leaf结点, 则使用gen.node.ptr.root记录它所在tree的root结点.
  2. 反之, 则使用gen.node.ptr.leaf记录以它为root结点所在子树的某个leaf结点.

我们可以用一个简单的例子来说明:

1
2
3
4
5
    gen0
   /
  gen1
 /    \
gen2   gen3

图中结点node.ptr使用情况为:

  1. gen2.node.ptr.root == gen0
  2. gen3.node.ptr.root == gen0
  3. gen1.node.ptr.leaf == gen2
  4. gen0.node.ptr.leaf == gen2

你可能会问如果有多个leaf结点, 我们应该记录哪一个呢? 例如这里就有两个leaf结点, 答案是没有区别, 记录任意一个leaf结点都行, 在后文中你将看到原因. 另外可以看到在初始化过程中, 我们使用是node.ptr.root, 这是因为此时的gen结点既是一个root结点也是一个leaf结点, 无论使用node.ptr另一种方式均可. 同时我们可以称呼这样的结点为root-leaf结点.

1.5. 维护 delegated generator tree 之新增child结点

这一节我们将描述如何两个结点在yield form调用过程中, 其中一个结点是如何被连接为另一个结点的child结点. 调用yield from的generator将作为这个过程中的child结点. 给定两个generators分别记为gen 和 child, 其中child将作为child结点连接到gen上. 我们将根据gen和child本身的结构来分类讨论他们的连接过程. 注意每一个case的连接操作可能并不是完整的, 我们主要关注是在不同case, 可能需要引入的新操作是哪些. 把每个case补全会导致，case与case之前出现重复, 并且讲解臃肿.

#1 gen为一个leaf结点.

这个case下新增过程相对来说比较好理解, 图式新增过程如下:

1
2
3
                      gen
gen +  child   -->    /
                    child

那么这里的连接过程如下:3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function add_child_to_leaf_node (gen, child) {
	// assert(gen1.node.parent == null && gen1.node.children == 0)
    
    leaf = child.node.children ? child.node.ptr.leaf : child;
    
    leaf.node.ptr.root = gen.node.ptr.root; 
    gen.node.ptr.leaf = leaf;
    
    
    gen.node.child.single.leaf = leaf; 
    gen.node.child.single.child = child;

    child.node.parent = gen;
}

// add_root_leaf_node_to_root_leaf_node (gen1, gen2)

用自然语言来描述如下:

  1. 第5行, 第7-8行: gen和child构成了父子, 它们应当具有相同的root结点. 根据核心设计2, 此时我们应当去选择一个gen的descendent结点, 让gen保存这个结点的引用. 这个descendent结点最好是一个leaf节点, 当child是不是一个leaf结点的时候, 这里的最好选择应当是它上面存放的某个leaf结点, 反之leaf只能是child. 第7-8行直接对应核心设计2的操作, 注意这里我们可以直接使用gen.node.ptr.root来获取root结点，是因为在假设条件中gen是一个leaf结点.
  2. 第10-11行: 存储child作为gen的child结点时, 根据核心设计3, 我们应当存储一个order pair, 这里只能是(child, leaf).
  3. 第13行: 维护正常的父子结点关系.

#2 gen有一个child结点.

图式新增过程如下:

1
2
3
             gen        gen
            /          /   \
gen  -->   c1   -->   c1   child

引入这个case, 是想指明使用node.child.single到node.child.ht转变. 只有一个order pair的时候, 我们直接使用node.child.single即可, 而需要存储多个ordered pairs就只能用哈希表了. 相关转变过程如下

1
2
3
4
5
6
7
function one_child_to_multiple_children(gen, child) {
    child_leaf = child.node.children ? child.node.ptr.leaf : child
    c1_leaf = gen.node.single.leaf;
    gen.node.ht = new_ht();
    ht_add(gen.node.ht, c1_leaf, c1); // 将c1对应的pair加入ht
    ht_add(gen.node, child_leaf, chi就只能变成ld); // 将child对应的pair加入ht
}

#3 gen是一个leaf结点且有parent结点.

情况开始变的复杂, 图式新增过程如下:

1
2
3
4
5
6
7
8
9
10
11
                                  ...
    ...                           /
     /                           p2
    p2                          /
   /                           p1
  p1    +    child             /
 /            \       -->    gen
gen           ...              \
                               child
                                 \
                                 ...

它对应的连接过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function add_child_to_leaf_node_has_parent(gen, child)
{
    // assert(gen.node.childen == 0 && gen.node.parent != null)
    
    leaf = child.node.children ? child.node.ptr.leaf : child;
    
    leaf.node.ptr.root = gen.node.ptr.root; 
    gen.node.ptr.leaf = leaf;

    // 依次向上遍历gen的祖先结点. 
    next = gen.node.parent;
    while (next) {
        if (next.node.children > 1) { 
            child2 = ht_find(next.child.ht, gen);
            ht_del(next.child.ht, gen);  // 从ht中删除以gen为index的元素
            ht_add(next.child.ht, leaf, child2); // 在ht中添加以leaf为index元素
        }
        next.node.ptr.leaf = leaf
        next = next.node.parent;
    }
}

第11-20行: gen原本是一个leaf结点, 那么它有可能被其他结点引用, 可能引用的地方为它的ancestor结点的node.child.single.leaf 或者 node.child.ht或者 node.ptr.leaf处. 此时gen不再是一个leaf结点，因此我们需要对这三个地方做一个必要的更新. 对于第一个和第三个地方, 我们之间将gen更新为leaf即可, 而第二个地方, 我们需要把包含gen的ordered pair取出来, 把gen换成leaf.

显然这里的代码忽略了更新node.child.single.leaf这个地方, 即ancestor结点只有一个child结点的时候, 会使得这个ancestor结点保存错误的ordered pair, 最后在它完成执行之后，我们可能无法正确地找到退回child结点. 我们在最初给出的crash例子对应了下面的构造过程:

1
2
3
4
5
 p1              p1                    p1
/    --->        /      --->         /    \
gen             gen	             gen    new1
                 \                   \
                child               child

注意中间这个图, 对应了这里case所代表的连接过程, 连接child之后, p1.child.single.leaf依然保存了gen, 而不是真正所需要的child. 那么在下一步构造中, 我们把new也连接到p1下, 使得p1会使用node.ptr.ht来保存两个child结点对应的两个ordered pair, 显然(gen, gen)是其中一个pair. 最后我们尝试拨动child->next()使得p1完成执行, 这个时候p1被关闭, 需要使用child来查询 p1.child.ht来更新root结点, 结果就是查询失败最终导致crash. 因此这里需要打个patch:

1
2
3
4
5
6
7
    if (next.node.children > 1) { 
        child2 = ht_find(next.child.ht, gen);
        ht_del(next.child.ht, gen);
        ht_add(next.child.ht, leaf, child);
+   } else {
+       next.node.child.single.leaf = leaf;    
+   }

那为什么PHP7.0, 7.1, 7.2没崩呢? 因为有一行垃圾代码使得gen在完成与child连接之后拥有了两个child结点, 即重复存储了child, 原本只有一个child结点, 使得在最后连接new1的时候根本不会用到未更新的p1.child.single.leaf, 参考下面的case#4.

#4 gen有一个child结点, 且存在一个有多个孩子的descendent结点.

图示新增过程如下:

1
2
3
4
5
    gen                       gen
   /                         /   \
  c1    +  child   -->     c1    child
 /  \                      /  \
c2  c3                    c2  c3

对应的部分连接过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function search_multi_children_node(gen) {
    while (gen.node.children == 1) {
        gen = gen.node.child.single.child;
    }
    return gen.node.children > 1 ? gen : null;
}

function merge_child_nodes_to_ht (gen, mutil_children_node, gen_single_child_node) {
    foreach (mutil_children_node.node.child.ht as leaf => child) {
        ht_add(gen.node.child.ht, leaf, gen_single_child_node);
    } 
}

function add_child_to_node_has_one_child (gen, child) {
	// assert (gen.node.children == 1)
    multi_children_node = search_multi_children_node(gen);
    if (multi_children_node != null) {
        merge_child_nodes_to_ht(gen, multi_children_node, gen.node.single.child);
    }
}

这里的操作是围绕核心设计3在进行. 注意观察最左边gen本身的结构, 它只有一个child结点, 那么当我们拨动c2或者c3使得gen完成执行后, 新root结点只能是它唯一的child结点. 但是当child也连接为成为gen的一个child之后, 我们就需要在gen完成执行时, 做出选择了. 那么gen中至少需要存储3个ordered pair, 即 (c1, c2), (c1, c3), (child, child). 所以这里有一个细微的merge操作, 将gen所有的后继leaf结点和gen的本身那个child结点构成的ordered pairs都放到gen.node.child.ht中.

那么我们要怎样完成这个工作呢? 我们不需要遍历gen所在tree的所有leaf结点, 我们只需要找到gen下第一个拥有多个孩子的descendent结点, 然后遍历它的ordered pairs中的leaf结点即可. 因为我们一直在维护上述操作, 可以保证从该结点中拿到所有的leaf结点.

#5 child不存在多个孩子的descendent结点

图示连接过程

1
2
3
4
5
6
7
8
9
 ...                       ...
  \                         \
   p1     +  child   -->     p1
  / \           \           /  \
...  gen        c1         ...  gen
    /                          /  \
   ...                        ...  child
                                     \
                                      c1

上述连接过程完成之后, gen会多出一个leaf结点 c1, 如果gen拥有多个child结点, 考虑核心设计3, 那么我们需要把(child, c1)放到gen中. 同理我们需要向上考虑gen所有拥有多个孩子的ancestor结点. 其过程为如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function add_child_to_node_has_one_child (gen, child) {
    if (gen.node.children != 0) {
        multi_children_node = search_multi_children_node(child);
        if (multi_children_node == null) { // `child`不存在多个孩子的descendent结点
            leaf = child.node.ptr.leaf;
            ht_add(gen, leaf, child);

            parent = gen.node.parent;
            cur = generator;
            while (parent) {
                if (parent.node.children > 1) {
                    ht_add(parent, leaf, cur);
                }
                cur = parent;
                parent = parent->node.parent;
            }
        }
    }
}

#6 child存在一个有多个孩子的descendent结点.

图示连接过程

1
2
3
4
5
6
7
8
9
...                             ...
 \                                \
  p1                               p1
 /  \                             /  \
...   gen   +    child    --> ...    gen
     /          /     \             /   \
    ...         c1     c2          ...  child
                                         /    \
                                        c1    c2

这里面临和#3中一样的问题, 当gen不是leaf结点时, 我们需要把ordered pair (child, c1)和(child, c2)也放到gen上. 同时, 也需要考虑gen的所有拥有多个孩子的ancestor结点, 将child中的所有leaf结点对应的ordered pairs加到其上. 其过程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function merge_leaf_node_to_node (gen, child) {
    if (gen.node.children != 0) {
        multi_children_node = search_multi_children_node(child);
        if (multi_children_node) {
            merge_child_nodes_to_ht(gen, multi_children_node, child);

            parent = generator->node.parent;
            cur = generator;
            while (parent) {
                if (parent.node.children > 1) {
                    merge_child_nodes_to_ht(parent, multi_children_node, cur);
                }
                cur = parent;
                parent = parent->node.parent;
            }
        }
    }
}

1.6. 维护 Delegated generator tree 之快速查找root结点

结合核心设计1-2, 我们可以很快的写出root结点的查找过程,

1
2
3
4
5
6
7
8
9
10
function get_current_geneartor(gen) {
    if (gen.node.parent == null) {
        return gen;
    }

    leaf = gen.node.children ? gen.node.ptr.leaf : gen; // 确定gen的leaf结点
    root = leaf.node.ptr.root;

    return root;
}

对应任意的结点, 我们首先找到它上存着的某个leaf结点的引用, 再从这个leaf结点上获取真正的root结点. 但是上面这个版本的查找过程并不正确. 在下面一节中将给出完全正确的版本.

1.7. 维护 Delegated generator tree 之更新结点

这里维护操作关注, 当root结点完成执行之后, 如何退回正确的child结点继续执行, 对应核心设计3-4. 首先我们将上面的get_current_generator()修改正确, 考虑下面的例子

1
2
3
        gen0
    /           \
gen1			gen2

当我们拨动gen1, 使得gen0完成执行后, gen2依然在使用gen0, i.e., 获取gen0的返回值. 这里告诉我们当root结点有多个孩子的时候, 我们不能直接将它从tree上移除. 但是为了避免, 我们下次拨动gen1或者gen1获取错误的root结点. 我们需要将gen_current_generator修改一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function get_current_generator(gen) {
    if (gen.node.parent == null) {
        return gen;
    }

    leaf = gen.node.children ? gen.node.ptr.leaf : gen;
    root = leaf.node.ptr.root;

    if (root is not finished && root.node.parent == null) {
        return root;
    }

    return update_tree(gen, leaf);
}

可以看到, 我们在返回root结点之前, 多了一个check, 确保其并没有完成执行, 同时依然是一个root结点 (可能leaf.node.ptr.leaf还没有被更新). 如果这个check失败了, 我们就需要更新gen对应的root结点, 这就是update_tree()中在做的操作, 其过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function get_child(gen, leaf) {
    // assert (gen.node.children >= 1)
    if (gen.node.children == 1) {
        return gen.node.child.single.child;
    } else {
        return ht_find(gen.node.child.ht, leaf);
    }
}

function update_tree(gen, leaf) {
    root = leaf.node.ptr.root
    root = get_child(root, leaf);

    while (root is finished && root != gen) {
        root = get_child(root, leaf);
    }
    
    if (root.parent != null && parent is not finished) {
        do {
            root = root.node.parent
        } while (root.node.parent)
    }

    leaf.node.ptr.root = root;
    return root;
}

第11-12行对应了核心设计3-4, 根据leaf 结点找到应该退回的child结点. 这里我们并不能直接把找到child结点视为新的root结点, 有可能它也已经完成执行了, 那么我们则需要继续寻找它的child结点, 对应这里第一个循环过程.

第18-22行这里在干什么 ? 注意在1.5节新增child结点中, 只有一个地方会更新leaf结点中关于root结点的引用, 即case#1中, 而其余任何地方都是不会更新node.ptr.root的. 这是因为在其他情况下, 我们就需要使用类似于get_current_generator()中的操作, 定位leaf结点, 再check对应的root结点. 因此我们将在新增孩子结点过程中的更新root结点操作延迟到了update_tree()当中, 当没有更新node.ptr.root就有可能出现找到的root结点其实并不是真正的root结点, 这一点我们可以通过它是否存在parent结点来确定.

最后在24行处完成leaf结点上关于新root结点的引用更新.

2. 最后

拥抱PHP系列又开始更新了, 这个系列的初衷是希望大家多多关注PHP里面的东西, 距离上一次更新，已经大概已经3年过去了. 接下来也许还会继续更新, 但是不知道在多久之后... 文章错误我会不定时勘误. 谢谢最后读到这里的陌生人, 下次再见.