- From: <bugzilla@jessica.w3.org>
- Date: Mon, 17 Feb 2014 01:12:11 +0000
- To: public-webapps-bugzilla@w3.org
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