[whatwg] Recursion and loops of Microdata items

[Philip Jägenstedt]

On Wed, 08 Jun 2011 21:51:57 +0200, Ian Hickson <ian at hixie.ch> wrote:

> The goal of itemref="" was just to have a way to handle cases where you
> have an item's properties scattered around a document.
>
> It's caused us more difficulties than helped anything, as far as I can
> tell. Has anyone implemented it or used it and liked it? I'd be fine with
> removing it if it's not a lot of trouble...
>
> I haven't fixed the algorithm to be written more simply, nor fixed the
> loops in the JSON stuff, because if we remove itemref="" then those
> problems just go away. If we want to keep itemref="", though, I will fix
> them. Any opinions one way or the other?

Unfortunately Tomasz is home sick, so he's asked me to reply in his place.

I think that itemref, while certainly the most complicated part of the  
API, should remain. Not having it would be rather limiting in cases where  
you don't want to change the structure of your markup (and perhaps layout)  
to fit the nesting that the vocabulary requires.

The algorithm in the spec clearly has some bugs and is rather hard to  
digest, so instead of suggesting deltas to it, I'll describe what we think  
the overall behavior should be.

Tomasz has implemented loop elimination using the Cheriyan–Mehlhorn/Gabow  
algorithm [1] and this looks promising. The algorithm finds the strongly  
connected components [2] and then we remove all components that have more  
than one item. Another way of stating this (I think) is that any item  
which is part of a loop (not just leading into one) is removed.

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.)

Would you be willing to spec something along these lines?

[1] http://en.wikipedia.org/wiki/Cheriyan–Mehlhorn/Gabow_algorithm
[2] http://en.wikipedia.org/wiki/Strongly_connected_component

-- 
Philip Jägenstedt
Core Developer
Opera Software