W3C home > Mailing lists > Public > whatwg@whatwg.org > November 2012

Re: [whatwg] Question on Limits in Adaption Agency Algorithm

From: Yasuhiko Minamide <minamide@cs.tsukuba.ac.jp>
Date: Mon, 05 Nov 2012 16:02:53 +0900 (JST)
Message-Id: <20121105.160253.163012433.minamide@cs.tsukuba.ac.jp>
To: whatwg@whatwg.org
Cc: minamide@cs.tsukuba.ac.jp, uezato@score.cs.tsukuba.ac.jp

> The DOM you get when you hit the limits in the adoption agency
> algorithm don't make a lot of intuitive sense.  Unfortunately, the
> limits are necessary so that implementations don't end up having to do
> quadratic work.  If this behavior is causing you trouble, you might

I'm wondering whether the adoption agency algorithm without the limits
really has a quadratic complexity (with respect to the size of the stack). 

Even if we do not impose a limit on the inner loop, each node in the
stack of open elements is processed at most once.

- The inner loop processes the nodes between the formatting element
  and the furthest block.
- Then, the formatting element is moved below the furthest block.

Then, the nodes above the furthest block will not be processed anymore.

If we do not impose the limit on the outer loop, the step 4 may cause
the quadratic behaviour. However, I think that it can be avoided by
slightly revising the algorithm.

I'm working on the automated test generation for the HTML5 parser 
specification and had the question when we try to understand the 
specification precisely.

Yasuhiko Minamide
Received on Monday, 5 November 2012 07:03:26 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 30 January 2013 18:48:11 GMT