- From: Yasuhiko Minamide <minamide@cs.tsukuba.ac.jp>
- Date: Tue, 18 Dec 2012 10:55:23 +0900 (JST)
- To: ian@hixie.ch
- Cc: whatwg@whatwg.org, minamide@cs.tsukuba.ac.jp, uezato@score.cs.tsukuba.ac.jp
>>
>> "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
Received on Tuesday, 18 December 2012 01:55:49 UTC