The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a

commit 6310c024c916f3f7ea89eb3ffabbc94e59a3c29a
Author: hayato <hayato@chromium.org>
Date: Fri May 27 11:59:39 2016

Rewrite Shadow DOM distribution engine to support partial synchronous distribution for v1

This is a huge engine rewrite to support slotchange [1] 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 [2] 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
  Time:
    Before: avg 3190.3 runs/s
    After:  avg 5885.6 runs/s

- PerformanceTests/ShadowDOM/v1-host-child-append.html => About 6.0x faster
  Time:
    Before: avg  51.6 runs/s
    After:  avg 306.4 runs/s

- PerformanceTests/ShadowDOM/v1-slot-append.html => About 3.4x faster
  Time:
    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.

- PerformanceTests/ShadowDOM/v1-distribution.html
  JS Heap:
    Before: avg 21357790.4 bytes
    After:  avg  3136606.4 bytes

- PerformanceTests/ShadowDOM/v1-host-child-append.html
  JS Heap:
    Before: avg 5860745.6 bytes
    After:  avg 4165614.4 bytes

- PerformanceTests/ShadowDOM/v1-slot-append.html
  JS Heap:
    Before: avg 13256016 bytes
    After:  avg  3540172.8 bytes

Notes:
- 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.
  -  crbug.com/610588 
  - imported/wpt/shadow-dom/HTMLSlotElement-interface.html

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
    structure.

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
    slot.

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.

Links:

[1] slotchange event: https://github.com/w3c/webcomponents/issues/288
[2] Relevant DOM Standard sections: https://dom.spec.whatwg.org/
    4.2.2 Shadow tree  4.2.2.1 Slots
      4.2.2.2 Slotables
      4.2.2.3 Finding slots and slotables
      4.2.2.4 Assigning slotables and slots
      4.2.2.5 Signaling slot changes
    4.2.3 Mutation algorithms

BUG= 531990 , 595287 , 610588 , 610961 , 579107 

Review-Url: https://codereview.chromium.org/1995203002
Cr-Commit-Position: refs/heads/master@{#396443}

[delete] https://crrev.com/42b137d8600104c1853de10626f6ef1e15e972ab/third_party/WebKit/LayoutTests/imported/wpt/shadow-dom/HTMLSlotElement-interface-expected.txt
[add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/LayoutTests/shadow-dom/slotchange-host-child-appended.html
[add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/LayoutTests/shadow-dom/slotchange-node-removed.html
[add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/LayoutTests/shadow-dom/slotchange-slotname-renamed.html
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/ShadowDOM/v1-distribution.html
[add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/ShadowDOM/v1-host-child-append.html
[add] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/ShadowDOM/v1-slot-append.html
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/PerformanceTests/Skipped
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/ContainerNode.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Document.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Document.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/DocumentOrderedMap.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Element.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Element.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Node.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/Node.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/ElementShadow.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/FlatTreeTraversal.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/ShadowRoot.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/ShadowRoot.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.h
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/html/HTMLSlotElement.cpp
[modify] https://crrev.com/6310c024c916f3f7ea89eb3ffabbc94e59a3c29a/third_party/WebKit/Source/core/html/HTMLSlotElement.h