This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 15296 - [Shadow]: Tree composition algorithm/rendering does not prevent multiple output of trees
Summary: [Shadow]: Tree composition algorithm/rendering does not prevent multiple outp...
Status: RESOLVED FIXED
Alias: None
Product: WebAppsWG
Classification: Unclassified
Component: HISTORICAL - Component Model (show other bugs)
Version: unspecified
Hardware: PC All
: P2 normal
Target Milestone: ---
Assignee: Dimitri Glazkov
QA Contact: public-webapps-bugzilla
URL:
Whiteboard:
Keywords:
Depends on:
Blocks: 14978
  Show dependency treegraph
 
Reported: 2011-12-21 09:31 UTC by Dominic Cooney
Modified: 2011-12-21 19:20 UTC (History)
0 users

See Also:


Attachments

Description Dominic Cooney 2011-12-21 09:31:56 UTC
There is a problem with the tree composition algorithm; it lacks the similar concept to "distribute" in the distribution algorithm for relating older shadow trees to shadow insertion points. As a result the algorithm contains redundant steps and the result is undesirable.

Consider this shadow DOM stack:

(younger)

Shadow Jr:
<shadow id="a"></shadow>
<shadow id="b"></shadow>

Shadow Papa:
<div>Hello, world</div>

(older) 

Since there are no insertion points, the operation of the distribution algorithm is trivial. The tree composition algorithm operates this way:

1. TREE = Jr
2. POOL = []
3. POOL = […]
4. POINT = #a
5. TREE exists, so:
5.1 (trivial distribution on TREE supplying POOL; no POOL is consumed; etc.)
5.2 POINT exists, so:
5.2.1 find the next older tree relative to Jr, so find Sr
5.2.1.1 Sr exists, so don’t stop
5.2.1.2 do:
5.2.1.2.1 TREE = Sr
5.2.1.2.2 "Assign Sr to #a" or POINT = Sr… what does this step mean?
5.2.1.2.3 Continue to REPEAT
5. TREE exists, so:
5.1 (trivial distribution on TREE supplying POOL; no POOL is consumed; etc.)
*** 5.2 POINT exists, so
5.2.1 Find the next older tree relative to Sr, so find nothing
5.2.1.1 Didn’t find anything so stop.

*** Aside: It seems POINT should be updated like in step 4 relative to Sr here; POINT is either still #a or Sr, depending on the meaning of 5.2.1.2.2.

When it comes to Rendering Shadow DOM Subtrees, the algorithm 2.(third bullet) says "in place of each shadow insertion point" which for Jr is #a and #b, 2.(third bullet).1 is true for both #a and #b—Sr is the older tree in the shadow host’s tree stack, and hence the rendering is:

<div>Hello, world</div>
<div>Hello, world</div>

ie Sr is output twice. I am pretty sure that this is not the intention, though.

The spec should clarify the algorithm with regard to older trees being distributed to shadow insertion points so as to avoid multiple renderings of a given node.

Basically the meaning of tree composition algorithm step 5.2.1.2.2 is unclear and probably wrong; and the rendering algorithm step 2.(third bullet).1 commits the sin of using tree composition language "If there is an older tree in shadow host’s tree stack …" when it could limit itself to the concept of nodes having been distributed or not.
Comment 1 Dimitri Glazkov 2011-12-21 19:19:35 UTC
(In reply to comment #0)
> There is a problem with the tree composition algorithm; it lacks the similar
> concept to "distribute" in the distribution algorithm for relating older shadow
> trees to shadow insertion points. As a result the algorithm contains redundant
> steps and the result is undesirable.
> 
> Consider this shadow DOM stack:
> 
> (younger)
> 
> Shadow Jr:
> <shadow id="a"></shadow>
> <shadow id="b"></shadow>
> 
> Shadow Papa:
> <div>Hello, world</div>
> 
> (older) 
> 
> Since there are no insertion points, the operation of the distribution
> algorithm is trivial. The tree composition algorithm operates this way:
> 
> 1. TREE = Jr
> 2. POOL = []
> 3. POOL = […]
> 4. POINT = #a
> 5. TREE exists, so:
> 5.1 (trivial distribution on TREE supplying POOL; no POOL is consumed; etc.)
> 5.2 POINT exists, so:
> 5.2.1 find the next older tree relative to Jr, so find Sr
> 5.2.1.1 Sr exists, so don’t stop
> 5.2.1.2 do:
> 5.2.1.2.1 TREE = Sr
> 5.2.1.2.2 "Assign Sr to #a" or POINT = Sr… what does this step mean?

I use the word "distribute" for insertion point, and the word "assign" for shadow insertion point. For insertion point, there could be more than one node to distribute, but for shadow insertion point, you can only distribute one, so I used the word "assign".

> 5.2.1.2.3 Continue to REPEAT
> 5. TREE exists, so:
> 5.1 (trivial distribution on TREE supplying POOL; no POOL is consumed; etc.)
> *** 5.2 POINT exists, so
> 5.2.1 Find the next older tree relative to Sr, so find nothing
> 5.2.1.1 Didn’t find anything so stop.
> 
> *** Aside: It seems POINT should be updated like in step 4 relative to Sr here;
> POINT is either still #a or Sr, depending on the meaning of 5.2.1.2.2.

Yes!!

> 
> When it comes to Rendering Shadow DOM Subtrees, the algorithm 2.(third bullet)
> says "in place of each shadow insertion point" which for Jr is #a and #b,
> 2.(third bullet).1 is true for both #a and #b—Sr is the older tree in the
> shadow host’s tree stack, and hence the rendering is:
> 
> <div>Hello, world</div>
> <div>Hello, world</div>
> 
> ie Sr is output twice. I am pretty sure that this is not the intention, though.
> 
> The spec should clarify the algorithm with regard to older trees being
> distributed to shadow insertion points so as to avoid multiple renderings of a
> given node.
> 
> Basically the meaning of tree composition algorithm step 5.2.1.2.2 is unclear
> and probably wrong; and the rendering algorithm step 2.(third bullet).1 commits
> the sin of using tree composition language "If there is an older tree in shadow
> host’s tree stack …" when it could limit itself to the concept of nodes having
> been distributed or not.

You're right! I fixed the wording in rendering algo, and tweaked the composition algo to denote "Assign" as a special term.
Comment 2 Dimitri Glazkov 2011-12-21 19:20:28 UTC
http://dvcs.w3.org/hg/webcomponents/rev/2c3c3971a9f5