[whatwg] Question on Limits in Adaption Agency Algorithm

[Yasuhiko Minamide]

>> 
>> "xyz" is inserted as a child of <i> and the order between "abc" and 
>> "xyz" is reversed in the tree. We would like to know whether this is an 
>> intended behaviour of the specification.
> 
> Yeah that's definitely not intentional.
> 
> Does anyone have any preference for how this is fixed?
> 

The easiest fix will be just to remove the limit of the inner loop.
Unfortunately, this makes the complexity of current implementations of the
adoption agency algorithm in O(n^2). This is because "remove node from 
the stack of open elements" is in O(n) on implementations as far as I 
have checked.

 9.5 If node is not in the list of active formatting elements, then remove 
     node from the stack of open elements and then go back to the step labeled 
     inner loop.

* WebKit : stack of open elements is implemented as a singly-linked list.
* Firefox : stack of open elements is implemented as an array.
            (need to move elements in the array to remove)

I'm not sure whether this is ok or not. 
(I thought the operation remove node was implemented in O(1). 
 For example, by using doubly linked list.)

Yasuhiko