[Bug 25489] [Imports]: Script execution order is non-deterministic in cyclic cases

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

--- Comment #2 from Morrita Hajime <morrita@google.com> ---
This is super interesting and seems like you're right. 
Thank you for pointing this out!

Cycles always make thing complex :-/

Instead of marking cycles, it might be better to distinguish 
"owning" link and "sharing" link (naming TBD). That is what Blink is kinda
doing.
In this model, first link in the traversal order wins the "ownership"
regardless
of the loading order.

Using your example, first let's consider

- I1 comes before I2 and
- I2 comes before I3 in the master M.
- and so on.

Based on this definition, the DFS traversal order of the tree (graph) is 

-  M->I1
- I1->I4
- I4->I2
- I3->I4 . This is marked as "shared" because I1->I4 already visited there.
-  M->I2 . This marked as "shared" as well.
-  M->I4 . Marked as shared.

This DFS traversal defines the spanning tree, that forms the import tree.

The point is that this ownership thing is "recomputed" each time new
import is added to the graph. For example, M->I2 first owns the I2, 
but once I4->I2 is found, the ownership is moved to I4->I2 from M->I2.

This might sound complicated, but thanks for the blocking of script execution,
we don't have to worry about undeterminisity of the script execution order.
It is (I believe) guaranteed to be executed by DFS order.

Thinking about I2 for example.
Imagine it is loaded by M2 at first. At that time, the graph would look like:

 M -> I1
   -> I2

The system cannot execute I2 because it is blocked by I1 which isn't yet
loaded.

Then time passed, I4 was loaded by I1 and I4 found I2.
Here, I4 grabbed the ownership of I2 from M becaus I4->I2 wins M->I2 based on
the DFS order.
Scripts in I2 (before link I2->I3) can be executed at this time 
because noting blocks I2 so far.

 M -> I1 -> I4
   .> I2 <-
   -> I3

Note that this diagram shows that I3 is also loaded by M.
It cannot be executed either because I1 blocks I3.

Then I2 found I3. I2 grabbed the ownership of I3 from M.

 M -> I1 -> I4
   .> I2 <-
       |
       v
   .> I3

Then I3 found I4, but it didn't own it.

 M -> I1 -> I4
   .> I2 <-
       |
       v
   .> I3  .>

And so on...

Hmm, apparently this explanation isn't clear enough :-/
I'll update the spec to give clearer picture.

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

Received on Monday, 28 April 2014 21:27:16 UTC