Rewrite Shadow DOM distribution engine to support partial synchronous distribution for v1
This is a huge engine rewrite to support slotchange  events more strictly
and more efficiently.
The summary of the changes is:
1. Make Blink be more spec compliant, regarding slotchange event.
2. Get significant performance improvements.
Now SlotAssignment has |slotname|-to-|slot| HashMap, via DocumentOrderedMap.
This HashMap is updated in each insertion/removal/renaming of slots.
Though DOM Standard  requires synchronous calculation of slot assignments
in each DOM mutation to fire a slotchagne event at the end of microtask,
this CL does not calculate it synchronously, as an important optimization,
if we can be sure to delay it. Instead, we do a minimum necessary check to
detect a slotchange, using the characteristics of slot assignments.
Especially, appending a child to a shadow host, which happens a lot in
Polymer, becomes much faster.
3. Make HTMLSlotElement a much smaller footprint element.
The following member variables are removed:
m_oldAssignedNodes, m_oldDistributedNodes, m_fallbackNodes, m_oldFallbackNodes,
m_distributionState and m_assignmentState.
4. Make SlotAssignment::resolveDistribution much simpler because slotchange is
already detected at early stage.
See the bug 610961 for details to know the basic ideas behind the scene.
The results of micro benchmarks are:
- PerformanceTests/ShadowDOM/v1-distribution.html => About 1.8x faster
Before: avg 3190.3 runs/s
After: avg 5885.6 runs/s
- PerformanceTests/ShadowDOM/v1-host-child-append.html => About 6.0x faster
Before: avg 51.6 runs/s
After: avg 306.4 runs/s
- PerformanceTests/ShadowDOM/v1-slot-append.html => About 3.4x faster
Before: avg 1647.4 runs/s
After: avg 5645.0 runs/s
This CL also reduced the memory usage in micro benchmarks because a slot element
becomes a smaller footprint element.
Before: avg 21357790.4 bytes
After: avg 3136606.4 bytes
Before: avg 5860745.6 bytes
After: avg 4165614.4 bytes
Before: avg 13256016 bytes
After: avg 3540172.8 bytes
- Reducing the memory usage is not the primary motivation of this CL.
- These performance tests are being marked skipped. See crbug.com/579107
- This CL also fixes the following bugs. These tests no longer fail.
The future works are:
1. There is a still false-positive case for slotchange event.
e.g. A preceding slot is inserted together with a following slot. This would
not be a significant issue, but should be fixed. As of now, we must pay a
performance penalty to remove this kind of false-positive.
2. Add more layout tests and add W3C Web Platform tests to be upstreamed.
3. Optimize the performance more and more.
e.g. It might be possible to optimize
HTMLSlotElement::hasAssignedNodesSynchronously by using yet another data
4. Support SlotAssignment for non shadow trees. e.g. a document tree.
This is a low-priority task because a document tree is unlikely to have a
5. Isolate NeedsRecalDistribution flag for v0 and v1.
Currently, the same flag is used in both kinds of shadow trees, v0 and v1,
to support both together in one page.
6. DocumentOrderedMap might not be optimized for our purpose.
e.g. DocumentOrderedMap has to travers DOM Tree if conflicts happen.
Just using Document::compareDocumentPosition() might be better, given that
conflicts is unlikely to happen.
 slotchange event: https://github.com/w3c/webcomponents/issues/288
 Relevant DOM Standard sections: https://dom.spec.whatwg.org/
4.2.2 Shadow tree 188.8.131.52 Slots
184.108.40.206 Finding slots and slotables
220.127.116.11 Assigning slotables and slots
18.104.22.168 Signaling slot changes
4.2.3 Mutation algorithms
25 files changed