Some Balancer improvements for performance and compatibility
authorTim Starling <tstarling@wikimedia.org>
Mon, 4 Jul 2016 05:15:18 +0000 (15:15 +1000)
committerTim Starling <tstarling@wikimedia.org>
Tue, 12 Jul 2016 04:18:04 +0000 (14:18 +1000)
commit5726c9ceb0644af360d37b86351b97ddfcbee20c
treebd343d6b5a53c451cbd01e789afce3163bdabc28
parentce081a3d7b5b24f39beb9955ccd5a9d5e79cfa86
Some Balancer improvements for performance and compatibility

* Use a doubly-linked list for the AFE list, instead of an array,
  allowing efficient insertion and removal from the middle, and trivial
  O(1) lookup of existing elements.
* Use a hashtable of singly-linked lists for storing Noah's Ark buckets,
  instead of iterating through the entire AFE list on every push.
* Store attributes in an array instead of serializing them in the
  tokenizer. This allows us to avoid sorting them in the output. For the
  Noah's Ark clause, the array is copied and then sorted on demand.
* XHTML-style serialization with self-closing tags.
* Clear the AFE list in stopParsing(), otherwise all the BalanceElement
  objects are kept alive until after serialization, thus using O(N^2)
  memory (in stack depth N) since the full serialization is stored at
  each stack level.

Change-Id: I517129c0658f03eb2ddee61fdf33ffe6fbd48509
autoload.php
includes/tidy/Balancer.php
tests/phpunit/includes/tidy/BalancerTest.php