[Bug 24658] [imports]: The fetch readiness shouldn't block fetching.

https://www.w3.org/Bugs/Public/show_bug.cgi?id=24658

--- Comment #6 from Gabor Krizsanits <gkrizsanits@mozilla.com> ---
(In reply to Morrita Hajime from comment #5)
> It's almost tree, except we have import sharing (dedup). de-dup makes
> everything complicated. Once we allow import sharing (by having <link>s with
> same URL), it is no longer a tree. It becoems DAG, or even could have
> cycles. That's why I gave up the tree and use list intead.
> 
> But yes, having a list globally makes explanation cryptic
> and it kills parallelism easily if misstated.
> 
> My current thinking here is that we could prevent cycles explicitly and
> accept the notion of DAG somehow.

Ah yeah, I keep saying tree when it's not... But it does not matter much
really, the tree we are looking for is well defined and part of the directed
graph of imports. Only extension to my algorithm that while we are looking for
the left most child we build up a list form the parent chain (that we have to
anyway because of the multiple parents) and check if the next first child is in
this list already. If so, we found a circle, we just ignore that link and check
for the next child or if there is no more child we're done, we found the leaf
node we were looking for in the sub-tree. This way the alg. will traverse the
graph as if it were a tree, ignoring exactly the edges that make circles. For
de-dup we have to add one more thing to it: step to the next one when the
referred import is already started/unblocked.

-- 
You are receiving this mail because:
You are the QA Contact for the bug.

Received on Monday, 17 February 2014 01:12:13 UTC