iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 28
0
自我挑戰組

花式PHP系列 第 29

PHP SPL:RecursiveIteratorIterator

read me senpai

這篇文章希望你至少有以下的知識:
2. 使用過多維陣列
3. 知道迭代器(Iterator)

如果你知道底下這些東西會更好:

  1. 遞迴
  2. 樹(資料結構)的基本概念
  3. ArrayIterator是用來迭代陣列的 Iterator

所以它能做什麼呢?

先講結論:(遞迴)迭代一個樹。

意思就是把一個多維陣列當成一個一維陣列在迭代,超猛。

<?php

// 產生多為陣列
// function create_deep_array(int $depth):array
// {
//     if ($depth > 1) {
//         return array($depth, create_deep_array($depth - 1));
//     } else {
//         return array('bottom');
//     }
// }
// 
// echo json_encode(create_deep_array(5));

$deepArray = json_decode('[5,[4,[3,[2,["bottom"]]]]]', TRUE);

// 變魔法!
$iterator = new RecursiveIteratorIterator(new RecursiveArrayIterator($deepArray));

// 當成一維陣列迭代!
foreach ($iterator as $element) {
    echo "$element" . PHP_EOL;
}

// 5
// 4
// 3
// 2
// bottom

什麼時候會用到它?

假如你現在有個多維陣列,而且每一層陣列底下元素的數量不固定,
那麼我要如何迭代到其中的每一個 element 呢?
或者說我打算 flatten 一個陣列,有沒有什麼簡單的作法呢?
是自己寫個遞迴,還是自己實作遞迴迭代器呢?

其實都不用,PHP 就已經內建遞迴迭代器了!就像上面那段程式碼用的那樣~

它的原理是什麼?

在上面那段程式碼中變魔法的那一行,
首先 new 出了一個 RecursiveArrayIterator,
再用它 new 出了一個 RecursiveIteratorIterator。

但名字這麼長,他們都是些什麼妖魔鬼怪?

底下章節會適度的使用簡稱:
class RecursiveArrayIterator 簡稱 RAI
class RecursiveIteratorIterator 簡稱 RII

先總結一下繼承關係

底下斜體字的是不會在文中提到的

  • RecursiveIteratorIterator

    • 實作 OuterIterator
      • 繼承 Iterator
  • RecursiveArrayIterator

    • 實作 RecursiveIterator
      • 繼承 Iterator
    • 繼承 ArrayIterator
      • 實作 SeekableIterator
        • 繼承 Iterator

RecursiveArrayIterator

它的本質就是一個 ArrayInterator,看看它在官網的繼承關係說明

<?php

class  RecursiveArrayIterator extends ArrayIterator implements RecursiveIterator
{
    /* 2 Methods */
    public RecursiveArrayIterator getChildren ( void )
    public bool hasChildren ( void )
    
    /**
     * 24 Inherited Methods
     */
}

首先「extends ArrayIterator」說明了它就是一個 ArrayIterator。
再來「implements RecursiveIterator」說明它必須實作該界面的 getChildren、hasChildren。

而且 ArrayIterator 的函式都被原封不動的繼承下來了,
由此可知,迭代時 ArrayIterator 的行為與 RAI 一致。

也就是說,即使它擁有 getChildren、hasChildren,
但在迭代 RAI 時是不會使用到它們兩個函式,也就是不會遞迴迭代的。

RecursiveIteratorIterator

它的讀法是「RecursiveIteratorIterator」。
意思就是「遞迴迭代器的迭代器」。

顧名思義,它可以用來迭代任何實作了 RecursiveIterator 界面的 Iterator。

繼承關係

<?php

class RecursiveIteratorIterator implements OuterIterator
{
    /* 4 Constants */
    /* 14 Methods */
    /* 1 Inherited methods */
}

因為 RII 僅僅只有實作 OuterIterator 這個界面,(界面不會有任何實作細節
所以我們可以預期 RII 的行為一定是有別於所有其他 Iterator 的。

它不一樣在哪呢?

如果你只對如何達成「遞迴迭代」有興趣,那其實看到這邊就可以了。

如果你對 RII 具體是如何達成遞迴迭代的,
可以繼續往下看,我會試著去追蹤、解釋 PHP 直譯器中跟 RII 有關的原始碼。
/images/emoticon/emoticon18.gif

RII是一款真正支援遞迴的迭代器

之所以用 RII 包 RAI 的原因是:
因為 RAI 提供了 getChildren 及 hasChildren,卻不會真的使用它來作「遞迴迭代」。
反而 RII 才會去用它們做迭代。

三種改變其迭代行為的FLAG

FLAG 意義
LEAVES_ONLY 預設。僅迭代 leaf node(沒有children的元素)。
SELF_FIRST leaf node 及 internal node(parent) 都迭代到。
CHILD_FIRST 同上,但 leaf node 優先

它迭代時具體發生了什麼?

根據 PHP 直譯器這段程式碼
大概可以知道 RII 是如何作到迭代的。

但因為我並不會 C ,
所以底下這段程式碼+註解只是我個人為了找出這個問題的答案做的努力,
如果有註解錯的地方請前輩留言指教~

static void spl_recursive_it_move_forward_ex(spl_recursive_it_object *object, zval *zthis)
{
	zend_object_iterator      *iterator;
	zval                      *zobject;
	zend_class_entry          *ce;
	zval                      retval, child;
	zend_object_iterator      *sub_iter;
	int                       has_children;

	SPL_FETCH_SUB_ITERATOR(iterator, object);

    // 透過 while 來不斷推進單次迭代要作的事情
    // 一次 while 不等於一次 php 對 RII 做的迭代,每執行一次這個 function 才是。
	while (!EG(exception)) {
next_step:
		iterator = object->iterators[object->level].iterator;
		switch (object->iterators[object->level].state) {
			case RS_NEXT:
				// 移動指針
				iterator->funcs->move_forward(iterator);
				if (EG(exception)) {
					if (!(object->flags & RIT_CATCH_GET_CHILD)) {
						return;
					} else {
						zend_clear_exception();
					}
				}
				/* fall through */
			case RS_START:
				// 查目前指針是不是指向正確的位置
				if (iterator->funcs->valid(iterator) == FAILURE) {
					break; //否則中斷
				}
				object->iterators[object->level].state = RS_TEST;
				/* break; */
			case RS_TEST:
				ce = object->iterators[object->level].ce;
				zobject = &object->iterators[object->level].zobject;
				// 檢查目前元素有沒有 hasChildren 可以呼叫以確定有沒有子元素
				if (object->callHasChildren) {
					zend_call_method_with_0_params(zthis, object->ce, &object->callHasChildren, "callHasChildren", &retval);
				} else {
					zend_call_method_with_0_params(zobject, ce, NULL, "haschildren", &retval);
				}
				if (EG(exception)) {
					if (!(object->flags & RIT_CATCH_GET_CHILD)) {
						object->iterators[object->level].state = RS_NEXT;
						return;
					} else {
						zend_clear_exception();
					}
				}
				// 有 hasChildren,而且執行了
				if (Z_TYPE(retval) != IS_UNDEF) {
					has_children = zend_is_true(&retval);
					zval_ptr_dtor(&retval);
					// 有子元素
					if (has_children) {
						if (object->max_depth == -1 || object->max_depth > object->level) {
							// 則根據在建構子設定的 FLAG 決定迭代器的行為
							switch (object->mode) {
							case RIT_LEAVES_ONLY:
							case RIT_CHILD_FIRST:
								// 執行 RS_CHILD
								object->iterators[object->level].state = RS_CHILD;
								goto next_step;
							case RIT_SELF_FIRST:
								// 執行 RS_SELF
								object->iterators[object->level].state = RS_SELF;
								goto next_step;
							}
						} else {
							/* do not recurse into */
							if (object->mode == RIT_LEAVES_ONLY) {
								/* this is not a leave, so skip it */
								object->iterators[object->level].state = RS_NEXT;
								goto next_step;
							}
						}
					}
				}
				if (object->nextElement) {
					zend_call_method_with_0_params(zthis, object->ce, &object->nextElement, "nextelement", NULL);
				}
				object->iterators[object->level].state = RS_NEXT;
				if (EG(exception)) {
					if (!(object->flags & RIT_CATCH_GET_CHILD)) {
						return;
					} else {
						zend_clear_exception();
					}
				}
				return /* self */;
			case RS_SELF:
				// FLAG 為 SELF_FIRST 或 CHILD_FIRST 時
				if (object->nextElement && (object->mode == RIT_SELF_FIRST || object->mode == RIT_CHILD_FIRST)) {
					//(好像是執行 nextElement 的樣子)
					zend_call_method_with_0_params(zthis, object->ce, &object->nextElement, "nextelement", NULL);
				}
				//FLAG 為 SELF_FIRST 時
				if (object->mode == RIT_SELF_FIRST) {
					// 執行 RS_CHILD
					object->iterators[object->level].state = RS_CHILD;
				} else {
					// 執行 RS_NEXT
					object->iterators[object->level].state = RS_NEXT;
				}
				// 中斷迭代
				return /* self */;
			case RS_CHILD:
				ce = object->iterators[object->level].ce;
				zobject = &object->iterators[object->level].zobject;
				// 嘗試對目前元素執行 getchildren
				if (object->callGetChildren) {
					zend_call_method_with_0_params(zthis, object->ce, &object->callGetChildren, "callGetChildren", &child);
				} else {
					zend_call_method_with_0_params(zobject, ce, NULL, "getchildren", &child);
				}

				if (EG(exception)) {
					if (!(object->flags & RIT_CATCH_GET_CHILD)) {
						return;
					} else {
						zend_clear_exception();
						zval_ptr_dtor(&child);
						object->iterators[object->level].state = RS_NEXT;
						goto next_step;
					}
				}

				//如果 children「是Undefined」或「不是Object」或「不是RecursiveIterator」
				if (Z_TYPE(child) == IS_UNDEF || Z_TYPE(child) != IS_OBJECT ||
						!((ce = Z_OBJCE(child)) && instanceof_function(ce, spl_ce_RecursiveIterator))) {
					zval_ptr_dtor(&child);
					//throw Exception
					zend_throw_exception(spl_ce_UnexpectedValueException, "Objects returned by RecursiveIterator::getChildren() must implement RecursiveIterator", 0);
					return;
				}

				//FLAG 為 CHILD_FIRST 時
				if (object->mode == RIT_CHILD_FIRST) {
					//執行 RS_SELF
					object->iterators[object->level].state = RS_SELF;
				} else {
					//執行 RS_NEXT
					object->iterators[object->level].state = RS_NEXT;
				}
				// 為從 children 取出的迭代器[分配記憶體]
				// @link http://php.net/manual/en/internals2.memory.management.php
				object->iterators = erealloc(object->iterators, sizeof(spl_sub_iterator) * (++object->level+1));
				sub_iter = ce->get_iterator(ce, &child, 0);
				// 複製資料
				ZVAL_COPY_VALUE(&object->iterators[object->level].zobject, &child);
				object->iterators[object->level].iterator = sub_iter;
				object->iterators[object->level].ce = ce;
				object->iterators[object->level].state = RS_START;
				if (sub_iter->funcs->rewind) {
					//子迭代器內部指針重設
					sub_iter->funcs->rewind(sub_iter);
				}
				//如果子迭代器有 beginChildren 則執行它
				if (object->beginChildren) {
					zend_call_method_with_0_params(zthis, object->ce, &object->beginChildren, "beginchildren", NULL);
					if (EG(exception)) {
						if (!(object->flags & RIT_CATCH_GET_CHILD)) {
							return;
						} else {
							zend_clear_exception();
						}
					}
				}
				goto next_step;
		}
		/* no more elements */
		if (object->level > 0) {
			if (object->endChildren) {
				zend_call_method_with_0_params(zthis, object->ce, &object->endChildren, "endchildren", NULL);
				if (EG(exception)) {
					if (!(object->flags & RIT_CATCH_GET_CHILD)) {
						return;
					} else {
						zend_clear_exception();
					}
				}
			}
			if (object->level > 0) {
				zval garbage;
				ZVAL_COPY_VALUE(&garbage, &object->iterators[object->level].zobject);
				ZVAL_UNDEF(&object->iterators[object->level].zobject);
				zval_ptr_dtor(&garbage);
				zend_iterator_dtor(iterator);
				object->level--;
			}
		} else {
			return; /* done completeley */
		}
	}
}

C好難

/images/emoticon/emoticon06.gif
收工~


上一篇
PHP SPL:SplObjectStorage
下一篇
推薦一些好用的工具
系列文
花式PHP31

尚未有邦友留言

立即登入留言