[whatwg] Recursion and loops of Microdata items

[Ian Hickson]

On Thu, 9 Jun 2011, Philip Jägenstedt wrote:
> 
> As for the spec, I don't think it can or needs to define the algorithm on a
> form suitable form implementation. Something along these lines would be much
> clearer for reference:
> 
> 1. create a (possibly disconnected) graph of all the items in the document (or
> subtree)
> 2. find the strongly connected components
> 3. create a list of "loopy" items: those that are in the same component as any
> other item
> 
> The traversal would remain mostly as before, but whenever an item is
> encountered, one checks if it is in the list of "loopy" items and if so
> ignores it. Since "loopy" is a global property, you'll see the same properties
> regardless of the path taken to reach it, which may or may not be the case
> with the current spec. (In any case, it's a nice feature.)

The main reason I didn't do something like this with the current spec was 
that I was trying to minimise the work needed when implementing the API in 
a dynamic situation. The above would imply that any time anything in the 
document changed in a way that could affect microdata, you'd have to redo 
the whole document before the next time the API was invoked. That seems 
expensive. (Consider the WHATWG spec, which has microdata in it and is 
about 5MB. Do you really want to crawl the whole document looking for 
microdata each time the API is invoked?)

What I had tried to do when implementing the spec is start at whatever 
point in the DOM the API call was related to, and then search for loops 
from that point, and drop anything loopy. That's still expensive, but it 
at least minimises the total amount of work.

Does that make sense?

If the expense isn't a big deal then I don't mind doing it the other way 
too, but this seems like an API that we're going to have enough trouble 
getting implemented in the first place without giving implementors a 
reason to avoid doing it at all.

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