iT邦幫忙

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

花式PHP系列 第 29 篇

PHP SPL：RecursiveIteratorIterator

2018鐵人賽 php spl iterator
4030 瀏覽

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
下一篇
推薦一些好用的工具
系列文
花式PHP 共 31 篇
  1. 27
    PHP SPL：SplFixedArray
  2. 28
    PHP SPL：SplObjectStorage
  3. 29
    PHP SPL：RecursiveIteratorIterator
  4. 30
    推薦一些好用的工具
  5. 31
    Firefox：Quantum 57 for developers
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1123 組
團體組數
52 組
累計文章數
23096 篇
完賽人數
656 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 2018鐵人賽 javascript 2017鐵人賽 python windows php c# windows server linux css react 程式設計 vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙