PHP源码阅读笔记二十九：接口的继承

PHP源码阅读笔记二十九：接口的继承
在之前有看过PHP源码中类的继承，今天我们看下PHP中的接口继承是如何实现的。
同样我们从CachingIterator类开始查找接口的继承实现。
CachingIterator extends IteratorIterator implements OuterIterator , Traversable , Iterator , ArrayAccess , Countable

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/* ArrayAccess接口的继承实现 */
REGISTER_SPL_IMPLEMENTS(CachingIterator, ArrayAccess);
 
//    ext/spl/spl_functions.h 41行
#define REGISTER_SPL_IMPLEMENTS(class_name, interface_name) \
	zend_class_implements(spl_ce_ ## class_name TSRMLS_CC, 1, spl_ce_ ## interface_name);
 
//	zend/zend_API.c 2218行
ZEND_API void zend_class_implements(zend_class_entry *class_entry TSRMLS_DC, int num_interfaces, ...) /* {{{ */
{
	zend_class_entry *interface_entry;
	va_list interface_list;
	va_start(interface_list, num_interfaces);
 
	while (num_interfaces--) {
		interface_entry = va_arg(interface_list, zend_class_entry *);
		zend_do_implement_interface(class_entry, interface_entry TSRMLS_CC);
	}
 
	va_end(interface_list);
}
/* }}} */
 
 
 
//	zend/zend_complie.c 2887行
ZEND_API void zend_do_implement_interface(zend_class_entry *ce, zend_class_entry *iface TSRMLS_DC) /* {{{ */
{
	zend_uint i, ignore = 0;
	zend_uint current_iface_num = ce->num_interfaces;
	zend_uint parent_iface_num  = ce->parent ? ce->parent->num_interfaces : 0;
 
	for (i = 0; i < ce->num_interfaces; i++) {
		if (ce->interfaces[i] == NULL) {
			memmove(ce->interfaces + i, ce->interfaces + i + 1, sizeof(zend_class_entry*) * (--ce->num_interfaces - i));
			i--;
		} else if (ce->interfaces[i] == iface) {	/* 已存在此接口 */
			if (i < parent_iface_num) {
				ignore = 1;
			} else {
				zend_error(E_COMPILE_ERROR, "Class %s cannot implement previously implemented interface %s", ce->name, iface->name);
			}
		}
	}
	if (!ignore) {
		if (ce->num_interfaces >= current_iface_num) {
			if (ce->type == ZEND_INTERNAL_CLASS) {
				ce->interfaces = (zend_class_entry **) realloc(ce->interfaces, sizeof(zend_class_entry *) * (++current_iface_num));
			} else {
				ce->interfaces = (zend_class_entry **) erealloc(ce->interfaces, sizeof(zend_class_entry *) * (++current_iface_num));
			}
		}
		ce->interfaces[ce->num_interfaces++] = iface;	//	接口数加1，将接口加入接口列表中
 
		/* 合并接口中的常量列表和方法列表 */
		zend_hash_merge_ex(&ce->constants_table, &iface->constants_table, (copy_ctor_func_t) zval_add_ref, sizeof(zval *), (merge_checker_func_t) do_inherit_constant_check, iface);
		zend_hash_merge_ex(&ce->function_table, &iface->function_table, (copy_ctor_func_t) do_inherit_method, sizeof(zend_function), (merge_checker_func_t) do_inherit_method_check, ce);
 
		do_implement_interface(ce, iface TSRMLS_CC);
		zend_do_inherit_interfaces(ce, iface TSRMLS_CC);
	}
}

从zend_do_implement_interface函数的合并接口中的常量列表和方法列表操作，我们可以猜想这也许是接口中不能有变量可以有常量的原因之一吧
在接口继承的过程中有对当前类的接口中是否存在同样接口的判断操作，如果已经存在了同样的接口，则此接口将不会继承。
如下所示php代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

<?php
interface FooInterface {
	public function method1();
}
 
class Base implements FooInterface {
	public function method1() {
		echo 'ss';
	}
}
 
class Foo extends Base implements FooInterface {
 
}
 
$foo = new Foo();
$foo->method1();

使用PHP实现堆排序

使用PHP实现堆排序
堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

“堆”定义
　　n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
　　(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) //ki相当于二叉树的非叶结点，K2i则是左孩子，k2i+1是右孩子
　　若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
　　树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

“筛选法”调整堆
　　R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆[性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为”筛选法”。
以上来自百度百科


以下为PHP的堆排序实现。
siftup函数是在x[1..n-1]为堆，在x[n]中放置一个任意的元素时，重新获得堆的操作。
它尽可能的将新元素向上筛选，向上筛选是通过交换该结点与其父结点来实现的。

siftdown函数是在x[1..n]是一个堆，在x[1]中放置一个任意的元素时，重新获得堆的操作。
它是一个向下筛选的过程，将顺序不对的元素和比它小的子结点交换。

通过siftup函数，加入n个元素，构造堆
通过siftdown函数，每次取堆顶端的数，然后重新构造堆，如此迭代，直到所有的数据都取出，因为堆顶一定是这个堆中最小的值，所以最后一定可以得到一个有序的序列。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

<?php
/**
 * 堆排序
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
/**
 * 向上筛选元素
 * 将元素$n添加到堆中，调整构建新的堆
 */
function siftup(&$seq, $n) {
	$i = $n;
 
	while($i > 1) {
		$p = floor($i / 2);
		if($seq[$p] <= $seq[$i]) {
			break;
		}
		list($seq[$p], $seq[$i]) = array($seq[$i], $seq[$p]);
 
		$i = $p;
	}
}
 
/**
 * 向下筛选元素
 */
function siftdown(&$seq, $n) {
	$i = 1;
 
	while(1) {
		$c = $i * 2;
 
		if($c > $n) {
			break;
		}
 
		/* $c 为左结点 $c + 1 为右结点*/
		if($c + 1 <= $n) {
			if($seq[$c + 1] < $seq[$c]) {
				$c++;
			}
		}
 
		if($seq[$i] <= $seq[$c]) {
			break;
		}
 
		/* 将$seq[$i]和它的两个孩子结点中关键字较大者进行交换 */
		list($seq[$c], $seq[$i]) = array($seq[$i], $seq[$c]);
 
		$i = $c;
	}
}
 
 
 
/**
 * 堆排序
 * @param	array	$seq	待排序的序列
 */
function heapSort(&$seq) {
	$n = count($seq);
 
	for($i = 2; $i <= $n; $i++) {
		siftup($seq, $i);
	}
 
	for($i = $n; $i >= 2; $i--) {
		list($seq[1], $seq[$i]) = array($seq[$i], $seq[1]);
		siftdown($seq, $i - 1);
	}
}
 
/* 测试 */
$seq = array(1 => 9, 7, 2, 3, 1, 6);
heapSort($seq);
print_r($seq);
 
die();

heapSort使用了n-1次siftup和n-1次siftdown操作，其时间复杂度为O(nlogn)

PHP源码阅读笔记二十八：类结构和继承

PHP源码阅读笔记二十八：类结构和继承
作为面向对象中一个非常关键也非常纠结的特性，我们需要了解一些
在PHP5中，从一开始就有了继承的概念，今天我们从PHP源码出发，了解他是怎么实现的。
在了解类的继承之前，我们需要知道类在PHP源码中是以哪种方式存储的。
找到zend/zend.h 418行：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

 
struct _zend_class_entry {
	char type;
	char *name;	/* 类名 */
	zend_uint name_length;	/* 类名字符串长度 */
	struct _zend_class_entry *parent; /* 父类 */
	int refcount; /* 引用计数 */
	zend_bool constants_updated;
	zend_uint ce_flags;	/* 类的访问控制 */
 
	HashTable function_table;	/*	类的成员函数 */
	HashTable default_properties;	/*	类的默认属性 */
	HashTable properties_info;	/*	类的属性信息 如访问控制等 */
	HashTable default_static_members;/*	静态成员列表 */
	HashTable *static_members;
	HashTable constants_table;	/* 常量列表 */
	const struct _zend_function_entry *builtin_functions;
 
	union _zend_function *constructor;	/*	构造函数*/
	union _zend_function *destructor;	/*	析构函数*/
	union _zend_function *clone;		/*	克隆方法*/
 
	/*	魔术方法 */
	union _zend_function *__get;
	union _zend_function *__set;
	union _zend_function *__unset;
	union _zend_function *__isset;
	union _zend_function *__call;
	union _zend_function *__callstatic;
	union _zend_function *__tostring;
	union _zend_function *serialize_func;
	union _zend_function *unserialize_func;
 
	zend_class_iterator_funcs iterator_funcs;
 
	/* handlers */
	zend_object_value (*create_object)(zend_class_entry *class_type TSRMLS_DC);
	zend_object_iterator *(*get_iterator)(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC);
	int (*interface_gets_implemented)(zend_class_entry *iface, zend_class_entry *class_type TSRMLS_DC); /* a class implements this interface */
	union _zend_function *(*get_static_method)(zend_class_entry *ce, char* method, int method_len TSRMLS_DC);
 
	/* serializer callbacks */
	int (*serialize)(zval *object, unsigned char **buffer, zend_uint *buf_len, zend_serialize_data *data TSRMLS_DC);
	int (*unserialize)(zval **object, zend_class_entry *ce, const unsigned char *buf, zend_uint buf_len, zend_unserialize_data *data TSRMLS_DC);
 
	zend_class_entry **interfaces;	/*	类实现的接口 */
	zend_uint num_interfaces;	/*	类实现的接口数 */
 
	/*	类所在文件信息 */
	char *filename;
	zend_uint line_start;
	zend_uint line_end;
	char *doc_comment;
	zend_uint doc_comment_len;
 
	struct _zend_module_entry *module;
};

从PHP自带的SPL中，我们可以看到有类的继承，从这里出发，可以找到我们所需要的实现过程
从手册中选择CachingIterator类作为切入点。
CachingIterator extends IteratorIterator implements OuterIterator , Traversable , Iterator , ArrayAccess , Countable
跟踪过程如下：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

//在ext/spl/spl_iterators.c 3246行，
REGISTER_SPL_SUB_CLASS_EX(CachingIterator, IteratorIterator, spl_dual_it_new, spl_funcs_CachingIterator);
 
//    ext/spl/spl_functions.h 34行
#define REGISTER_SPL_SUB_CLASS_EX(class_name, parent_class_name, obj_ctor, funcs) \
    spl_register_sub_class(&spl_ce_ ## class_name, spl_ce_ ## parent_class_name, # class_name, obj_ctor, funcs TSRMLS_CC);
 
//    ext/spl/spl_functions.c 56行
PHPAPI void spl_register_sub_class(zend_class_entry ** ppce, zend_class_entry * parent_ce, char * class_name, void *obj_ctor, const zend_function_entry * function_list TSRMLS_DC)
*ppce = zend_register_internal_class_ex(&ce, parent_ce, NULL TSRMLS_CC);
 
//    zend/zend_API.c  2196行
ZEND_API zend_class_entry *zend_register_internal_class_ex(zend_class_entry *class_entry, zend_class_entry *parent_ce, char *parent_name TSRMLS_DC)
zend_do_inheritance(register_class, parent_ce TSRMLS_CC);
 
//    zend/zend_compile.c 2784行
 
ZEND_API void zend_do_inheritance(zend_class_entry *ce, zend_class_entry *parent_ce TSRMLS_DC)
{
    /* 接口不能继承类 */
    if ((ce->ce_flags & ZEND_ACC_INTERFACE)
   	 && !(parent_ce->ce_flags & ZEND_ACC_INTERFACE)) {
   	 zend_error(E_COMPILE_ERROR, "Interface %s may not inherit from class (%s)", ce->name, parent_ce->name);
    }
 
    /* final类不能继承 */
    if (parent_ce->ce_flags & ZEND_ACC_FINAL_CLASS) {
   	 zend_error(E_COMPILE_ERROR, "Class %s may not inherit from final class (%s)", ce->name, parent_ce->name);
    }
 
    ce->parent = parent_ce;
    /* 拷贝序列化和反序列化回调函数 */
    if (!ce->serialize) {
   	 ce->serialize   = parent_ce->serialize;
    }
    if (!ce->unserialize) {
   	 ce->unserialize = parent_ce->unserialize;
    }
 
    /* 继承父类的接口 在此处有停下来思考，为何要这么做 */
    zend_do_inherit_interfaces(ce, parent_ce TSRMLS_CC);
 
    /* 继承父类的属性  */
    zend_hash_merge(&ce->default_properties, &parent_ce->default_properties, (void (*)(void *)) zval_add_ref, NULL, sizeof(zval *), 0);
    if (parent_ce->type != ce->type) {
   	 /* 用户自定义的类从内部类继承 */
   	 zend_update_class_constants(parent_ce  TSRMLS_CC);
   	 zend_hash_apply_with_arguments(CE_STATIC_MEMBERS(parent_ce) TSRMLS_CC, (apply_func_args_t)inherit_static_prop, 1, &ce->default_static_members);
    } else {
   	 zend_hash_apply_with_arguments(&parent_ce->default_static_members TSRMLS_CC, (apply_func_args_t)inherit_static_prop, 1, &ce->default_static_members);
    }
    zend_hash_merge_ex(&ce->properties_info, &parent_ce->properties_info, (copy_ctor_func_t) (ce->type & ZEND_INTERNAL_CLASS ? zend_duplicate_property_info_internal : zend_duplicate_property_info), sizeof(zend_property_info), (merge_checker_func_t) do_inherit_property_access_check, ce);
 
    /* 合并常量和成员函数 */
    zend_hash_merge(&ce->constants_table, &parent_ce->constants_table, (void (*)(void *)) zval_add_ref, NULL, sizeof(zval *), 0);
    zend_hash_merge_ex(&ce->function_table, &parent_ce->function_table, (copy_ctor_func_t) do_inherit_method, sizeof(zend_function), (merge_checker_func_t) do_inherit_method_check, ce);
 
    do_inherit_parent_constructor(ce);
 
    if (ce->ce_flags & ZEND_ACC_IMPLICIT_ABSTRACT_CLASS && ce->type == ZEND_INTERNAL_CLASS) {
   	 ce->ce_flags |= ZEND_ACC_EXPLICIT_ABSTRACT_CLASS;
    } else if (!(ce->ce_flags & ZEND_ACC_IMPLEMENT_INTERFACES)) {
   	 /* The verification will be done in runtime by ZEND_VERIFY_ABSTRACT_CLASS */
   	 zend_verify_abstract_class(ce TSRMLS_CC);
    }
}

关于上面do_inherit_parent_constructor(ce)
此方法实现魔术方法继承，如果子类中没有相关的魔术方法，则继承父类的对应方法。如下所示的PHP代码为子类没构造函数的情况

1
2
3
4
5
6
7
8
9
10
11

class Base {
	public function __construct() {
    	echo 'Base __construct<br />';
	}
}
 
class Foo extends Base {
 
}
 
$foo = new Foo();

如上，会输出：Base __construct
显然继承了父类的构造方法，如果子类有自己的构造方法，并且需要调用父类的构造方法时，需要在子类的构造方法中调用父类的构造方法，PHP不会自动调用。