[whatwg] Question on Limits in Adaption Agency Algorithm

[Ian Hickson]

On Fri, 2 Aug 2013, Yasuhiko Minamide wrote:
> On Mon, 1 Jul 2013, Ian Hickson wrote:
> > 
> > One option would be to remove from the stack of open elements any 
> > elements that we are skipping when we bail out of the AAA.
> > 
> > Can anyone see a problem with doing that?
> 
> I think that this solves the issue and clarifies the behaviour of the 
> parser.
> 
> > The limits are really intended to reduce the memory consumption of the 
> > algorithm, not its running time. Elements are expensive, and this 
> > algorithm can create exponentially more elements than tags in the 
> > markup, when it's not limited.
> 
> Although I agree with the revision above, I would like to clarify the 
> behaviour of the AAA algorithm.
> 
> I don't think that the AAA algorithm can create exponentially more 
> elements even if it's not limited.
> 
> Let D be the depth of the stack of open elements and S the size of the 
> DOM tree that has been constructed so far.
> 
> Then after application of the algorithm:
> 
> * The size of the DOM tree is at most S + D. 
> * The depth of the stack of open elements is at most D.
> 
> Even if the algorithm is applied n times, the size of the DOM tree is 
> bounded by S + nD. (not S * 2^n)
> 
> In total, I think that the number of elements in the DOM tree is in 
> O(m^2) where m is the number of tags in the source HTML.

Yeah, that's more accurate. I should have said quadratically, not 
exponentially.

-- 
Ian Hickson               U+1047E                )\._.,--....,'``.    fL
http://ln.hixie.ch/       U+263A                /,   _.. \   _\  ;`._ ,.
Things that are impossible just take longer.   `._.-(,_..'--(,_..'`-.;.'