From c768146e4ded54ee1b2a5a9771d9f99cc12dac1d Mon Sep 17 00:00:00 2001 From: "Edward Z. Yang" Date: Sat, 12 Oct 2013 21:24:38 -0700 Subject: [PATCH] Gusev's proposed patch Signed-off-by: Edward Z. Yang --- library/HTMLPurifier.includes.php | 3 + library/HTMLPurifier.safe-includes.php | 3 + library/HTMLPurifier/Array.php | 184 ++++++++++++++++++++ library/HTMLPurifier/ArrayNode.php | 24 +++ library/HTMLPurifier/Strategy/MakeWellFormed.php | 9 +- tests/HTMLPurifier/ArrayTest.php | 207 +++++++++++++++++++++++ 6 files changed, 426 insertions(+), 4 deletions(-) create mode 100644 library/HTMLPurifier/Array.php create mode 100644 library/HTMLPurifier/ArrayNode.php create mode 100644 tests/HTMLPurifier/ArrayTest.php diff --git a/library/HTMLPurifier.includes.php b/library/HTMLPurifier.includes.php index 18cb0013..5f8c137a 100644 --- a/library/HTMLPurifier.includes.php +++ b/library/HTMLPurifier.includes.php @@ -19,6 +19,8 @@ */ require 'HTMLPurifier.php'; +require 'HTMLPurifier/Array.php'; +require 'HTMLPurifier/ArrayNode.php'; require 'HTMLPurifier/AttrCollections.php'; require 'HTMLPurifier/AttrDef.php'; require 'HTMLPurifier/AttrTransform.php'; @@ -36,6 +38,7 @@ require 'HTMLPurifier/DefinitionCache.php'; require 'HTMLPurifier/DefinitionCacheFactory.php'; require 'HTMLPurifier/Doctype.php'; require 'HTMLPurifier/DoctypeRegistry.php'; +require 'HTMLPurifier/DoublyLinkedList.php'; require 'HTMLPurifier/ElementDef.php'; require 'HTMLPurifier/Encoder.php'; require 'HTMLPurifier/EntityLookup.php'; diff --git a/library/HTMLPurifier.safe-includes.php b/library/HTMLPurifier.safe-includes.php index e23a81a7..090a0e59 100644 --- a/library/HTMLPurifier.safe-includes.php +++ b/library/HTMLPurifier.safe-includes.php @@ -13,6 +13,8 @@ $__dir = dirname(__FILE__); require_once $__dir . '/HTMLPurifier.php'; +require_once $__dir . '/HTMLPurifier/Array.php'; +require_once $__dir . '/HTMLPurifier/ArrayNode.php'; require_once $__dir . '/HTMLPurifier/AttrCollections.php'; require_once $__dir . '/HTMLPurifier/AttrDef.php'; require_once $__dir . '/HTMLPurifier/AttrTransform.php'; @@ -30,6 +32,7 @@ require_once $__dir . '/HTMLPurifier/DefinitionCache.php'; require_once $__dir . '/HTMLPurifier/DefinitionCacheFactory.php'; require_once $__dir . '/HTMLPurifier/Doctype.php'; require_once $__dir . '/HTMLPurifier/DoctypeRegistry.php'; +require_once $__dir . '/HTMLPurifier/DoublyLinkedList.php'; require_once $__dir . '/HTMLPurifier/ElementDef.php'; require_once $__dir . '/HTMLPurifier/Encoder.php'; require_once $__dir . '/HTMLPurifier/EntityLookup.php'; diff --git a/library/HTMLPurifier/Array.php b/library/HTMLPurifier/Array.php new file mode 100644 index 00000000..4a40fa52 --- /dev/null +++ b/library/HTMLPurifier/Array.php @@ -0,0 +1,184 @@ +head == null) { + $this->head = &$item; + } + if ($temp instanceof HTMLPurifier_ArrayNode) { + $item->prev = &$temp; + $temp->next = &$item; + } + unset($temp); + $temp = &$item; + + $i ++; + + unset($item, $v); + } + $this->count = $i; + $this->offset = 0; + $this->offsetItem = &$this->head; + } + + protected function findIndex($offset) + { + if ($this->head == null) { + return array( + 'correct' => false, + 'value' => null + ); + } + + $current = &$this->head; + $index = 0; + + if ($this->offset <= $offset && $this->offsetItem instanceof HTMLPurifier_ArrayNode) { + $current = &$this->offsetItem; + $index = $this->offset; + } + + while ($current->next instanceof HTMLPurifier_ArrayNode && $index != $offset) { + $current = &$current->next; + $index ++; + } + + if ($index == $offset) { + $this->offset = $offset; + $this->offsetItem = &$current; + return array( + 'correct' => true, + 'value' => &$current + ); + } + + return array( + 'correct' => false, + 'value' => &$current + ); + } + + public function insertBefore($offset, $value) + { + $result = $this->findIndex($offset); + + $this->count ++; + $item = new HTMLPurifier_ArrayNode($value); + if ($result['correct'] == false) { + if ($result['value'] instanceof HTMLPurifier_ArrayNode) { + $result['value']->next = &$item; + $item->prev = &$result['value']; + } + } else { + if ($result['value'] instanceof HTMLPurifier_ArrayNode) { + $item->prev = &$result['value']->prev; + $item->next = &$result['value']; + } + if ($item->prev instanceof HTMLPurifier_ArrayNode) { + $item->prev->next = &$item; + } + if ($result['value'] instanceof HTMLPurifier_ArrayNode) { + $result['value']->prev = &$item; + } + } + if ($offset == 0) { + $this->head = &$item; + } + if ($offset <= $this->offset && $this->offsetItem instanceof HTMLPurifier_ArrayNode) { + $this->offsetItem = &$this->offsetItem->prev; + } + } + + public function remove($offset) + { + $result = $this->findIndex($offset); + + if ($result['correct']) { + $this->count --; + $item = $result['value']; + $item->prev->next = &$result['value']->next; + $item->next->prev = &$result['value']->prev; + if ($offset == 0) { + $this->head = &$item->next; + } + if ($offset < $this->offset) { + $this->offset --; + } elseif ($offset == $this->offset) { + $this->offsetItem = &$item->next; + } + } + } + + public function getArray() + { + $return = array(); + $head = $this->head; + + while ($head instanceof HTMLPurifier_ArrayNode) { + $return[] = $head->value; + $head = &$head->next; + } + + return $return; + } + + public function offsetExists($offset) + { + return $offset >= 0 && $offset < $this->count; + } + + public function offsetGet($offset) + { + $result = $this->findIndex($offset); + if ($result['correct']) { + return $result['value']->value; + } + + return null; + } + + public function offsetSet($offset, $value) + { + $result = $this->findIndex($offset); + if ($result['correct']) { + $result['value']->value = &$value; + } + } + + public function offsetUnset($offset) + { + $this->remove($offset); + } +} diff --git a/library/HTMLPurifier/ArrayNode.php b/library/HTMLPurifier/ArrayNode.php new file mode 100644 index 00000000..1871059b --- /dev/null +++ b/library/HTMLPurifier/ArrayNode.php @@ -0,0 +1,24 @@ +value = &$value; + } + + /** + * @var HTMLPurifier_ArrayNode + */ + public $prev = null; + + /** + * @var HTMLPurifier_ArrayNode + */ + public $next = null; + + /** + * @var mixed + */ + public $value = null; +} diff --git a/library/HTMLPurifier/Strategy/MakeWellFormed.php b/library/HTMLPurifier/Strategy/MakeWellFormed.php index c7aa1bb8..0e755b04 100644 --- a/library/HTMLPurifier/Strategy/MakeWellFormed.php +++ b/library/HTMLPurifier/Strategy/MakeWellFormed.php @@ -45,7 +45,7 @@ class HTMLPurifier_Strategy_MakeWellFormed extends HTMLPurifier_Strategy protected $context; public function execute($tokens, $config, $context) { - + $tokens = new HTMLPurifier_Array($tokens); $definition = $config->getHTMLDefinition(); // local variables @@ -453,7 +453,7 @@ class HTMLPurifier_Strategy_MakeWellFormed extends HTMLPurifier_Strategy $context->destroy('CurrentToken'); unset($this->injectors, $this->stack, $this->tokens, $this->t); - return $tokens; + return $tokens->getArray(); } /** @@ -490,6 +490,7 @@ class HTMLPurifier_Strategy_MakeWellFormed extends HTMLPurifier_Strategy // array(number nodes to delete, new node 1, new node 2, ...) $delete = array_shift($token); + throw new Exception("unsupported"); $old = array_splice($this->tokens, $this->t, $delete, $token); if ($injector > -1) { @@ -508,7 +509,7 @@ class HTMLPurifier_Strategy_MakeWellFormed extends HTMLPurifier_Strategy * this token. You must reprocess after this. */ private function insertBefore($token) { - array_splice($this->tokens, $this->t, 0, array($token)); + $this->tokens->insertBefore($this->t, $token); } /** @@ -516,7 +517,7 @@ class HTMLPurifier_Strategy_MakeWellFormed extends HTMLPurifier_Strategy * occupied space. You must reprocess after this. */ private function remove() { - array_splice($this->tokens, $this->t, 1); + $this->tokens->remove($this->t); } /** diff --git a/tests/HTMLPurifier/ArrayTest.php b/tests/HTMLPurifier/ArrayTest.php new file mode 100644 index 00000000..7e51d474 --- /dev/null +++ b/tests/HTMLPurifier/ArrayTest.php @@ -0,0 +1,207 @@ +getData(); + $object = new HTMLPurifier_ArrayMock($array); + + $this->assertEqual(0, $object->getOffset()); + $this->assertEqual($object->getHead(), $object->getOffsetItem()); + $this->assertEqual(count($array), $object->getCount()); + $this->assertEqual($array, $object->getArray()); + } + + /** + * Testing of offset & offsetItem properties while seeking/removing/inserting + */ + public function testFindIndex() + { + $array = array(1, 2, 3, 4, 5); + $object = new HTMLPurifier_ArrayMock($array); + for ($i = 0; $i < $object->getCount(); $i ++) { + $object[$i]; + $this->assertEqual($i, $object->getOffset()); + $this->assertEqual($array[$i], $object->getOffsetItem()->value); + } + + $object[2]; + $this->assertEqual(2, $object->getOffset()); + $this->assertEqual(3, $object->getOffsetItem()->value); + $object->remove(2); + $this->assertEqual(2, $object->getOffset()); + $this->assertEqual(4, $object->getOffsetItem()->value); + + $object[1]; + $this->assertEqual(1, $object->getOffset()); + $this->assertEqual(2, $object->getOffsetItem()->value); + $object->insertBefore(1, 'a'); + $this->assertEqual(1, $object->getOffset()); + $this->assertEqual('a', $object->getOffsetItem()->value); + } + + /** + * Testing that behavior of insertBefore the same as array_splice + */ + public function testInsertBefore() + { + $array = $this->getData(); + $object = new HTMLPurifier_ArrayMock($array); + + $index = 0; + array_splice($array, $index, 0, array('a')); + $object->insertBefore($index, 'a'); + $this->assertEqual($array, $object->getArray()); + + $index = 2; + array_splice($array, $index, 0, array('a')); + $object->insertBefore($index, 'a'); + $this->assertEqual($array, $object->getArray()); + + $index = count($array) * 2; + array_splice($array, $index, 0, array('a')); + $object->insertBefore($index, 'a'); + $this->assertEqual($array, $object->getArray()); + } + + /** + * Testing that behavior of remove the same as array_splice + */ + public function testRemove() + { + $array = $this->getData(); + $object = new HTMLPurifier_ArrayMock($array); + + $index = 0; + array_splice($array, $index, 1); + $object->remove($index); + $this->assertEqual($array, $object->getArray()); + + $index = 2; + array_splice($array, $index, 1); + $object->remove($index); + $this->assertEqual($array, $object->getArray()); + + $index = count($array) * 2; + array_splice($array, $index, 1); + $object->remove($index); + $this->assertEqual($array, $object->getArray()); + } + + /** + * Testing that object returns original array + */ + public function testGetArray() + { + $array = $this->getData(); + $object = new HTMLPurifier_ArrayMock($array); + $this->assertEqual($array, $object->getArray()); + } + + /** + * Testing ArrayAccess interface + */ + public function testOffsetExists() + { + $array = $this->getData(); + $object = new HTMLPurifier_ArrayMock($array); + $this->assertEqual(isset($array[0]), isset($object[0])); + } + + /** + * Testing ArrayAccess interface + */ + public function testOffsetGet() + { + $array = array(1, 2, 3); + $object = new HTMLPurifier_ArrayMock($array); + foreach ($array as $k => $v) { + $this->assertEqual($v, $object[$k]); + } + } + + /** + * Testing ArrayAccess interface + */ + public function testOffsetSet() + { + $array = array(1, 2, 3); + $object = new HTMLPurifier_ArrayMock($array); + foreach ($array as $k => $v) { + $v = $v * 2; + $object[$k] = $v; + $this->assertEqual($v, $object[$k]); + } + } + + /** + * Testing ArrayAccess interface + * There is one difference: keys are updated as well, they are started from 0 + */ + public function testOffsetUnset() + { + $object = new HTMLPurifier_ArrayMock(array(1, 2, 3, 4)); + unset($object[1]); + $this->assertEqual(array(1, 3, 4), $object->getArray()); + unset($object[0]); + $this->assertEqual(array(3, 4), $object->getArray()); + unset($object[1]); + $this->assertEqual(array(3), $object->getArray()); + unset($object[0]); + $this->assertEqual(array(), $object->getArray()); + } +} + +/** + * Mock for some protected properties of HTMLPurifier_Array + */ +class HTMLPurifier_ArrayMock extends HTMLPurifier_Array +{ + /** + * @return HTMLPurifier_ArrayNode|null + */ + public function getHead() + { + return $this->head; + } + + /** + * @return int + */ + public function getOffset() + { + return $this->offset; + } + + /** + * @return int + */ + public function getCount() + { + return $this->count; + } + + /** + * @return HTMLPurifier_ArrayNode|null + */ + public function getOffsetItem() + { + return $this->offsetItem; + } +} -- 2.11.4.GIT