Attachment #134725 for bug #82009

View Details Raw Unified Return to Bug 82009

| Differences between



2012-03-26  Hayato Ito  <hayato@chromium.org>

        [Shadow DOM] Add a Walker class which can traverse a Composed Shadow Tree.
        https://bugs.webkit.org/show_bug.cgi?id=82009

        Reviewed by NOBODY (OOPS!).

        ComposedShadowTreeWalker is intended to be a successor of current ReifiedTreeTraversal APIs.
        ComposedShadowTreeWalker uses a cursor pattern and takes a starting node in its constructor.

        The typical usage is:

          for (ComposedShadowTreeWalker walker(node); walker.get(); walker.nextNode()) {
                ...
          }

        Follow-up patches will update clients which use current ReifiedTreeTraversal APIs so that they use the Walker.
        More tests will come along with these actual use cases in follow-up patches.
        After that, I'll get rid of ReifiedTreeTraversal APIs in favor of the Walker.

        Note that 'ComposedShadowTree' and 'ReifiedTree' has the same meaning.
        Because ReifiedTree is not intuitive name, we are starting to use 'ComposedShadowTree' from now.

        Test: fast/dom/shadow/composed-shadow-tree-walker.html

        * CMakeLists.txt:
        * GNUmakefile.list.am:
        * Target.pri:
        * WebCore.exp.in:
        * WebCore.gypi:
        * WebCore.vcproj/WebCore.vcproj:
        * WebCore.xcodeproj/project.pbxproj:
        * dom/ComposedShadowTreeWalker.cpp: Added.
        (WebCore):
        (WebCore::isShadowHost):
        (WebCore::shadowTreeFor):
        (WebCore::shadowTreeOfParent):
        (WebCore::ComposedShadowTreeWalker::ComposedShadowTreeWalker):
        (WebCore::ComposedShadowTreeWalker::startedWithFirstChild):
        (WebCore::ComposedShadowTreeWalker::assertPrecondition):
        (WebCore::ComposedShadowTreeWalker::assertPostcondition):
        (WebCore::ComposedShadowTreeWalker::firstChild):
        (WebCore::ComposedShadowTreeWalker::traverseFirstChild):
        (WebCore::ComposedShadowTreeWalker::lastChild):
        (WebCore::ComposedShadowTreeWalker::traverseLastChild):
        (WebCore::ComposedShadowTreeWalker::traverseChild):
        (WebCore::ComposedShadowTreeWalker::traverseLightChildren):
        (WebCore::ComposedShadowTreeWalker::traverseNode):
        (WebCore::ComposedShadowTreeWalker::nextSibling):
        (WebCore::ComposedShadowTreeWalker::previousSibling):
        (WebCore::ComposedShadowTreeWalker::traverseSiblingOrBackToInsertionPoint):
        (WebCore::ComposedShadowTreeWalker::traverseSiblingInCurrentTree):
        (WebCore::ComposedShadowTreeWalker::traverseSiblingOrBackToYoungerShadowRoot):
        (WebCore::ComposedShadowTreeWalker::escapeFallbackContentElement):
        (WebCore::ComposedShadowTreeWalker::traverseNodeEscapingFallbackContents):
        (WebCore::ComposedShadowTreeWalker::parentNode):
        (WebCore::ComposedShadowTreeWalker::traverseParentNode):
        (WebCore::ComposedShadowTreeWalker::traverseParentNodeInCurrentTree):
        (WebCore::ComposedShadowTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost):
        (WebCore::ComposedShadowTreeWalker::adjustedParentNode):
        (WebCore::ComposedShadowTreeWalker::traverseNextSibling):
        (WebCore::ComposedShadowTreeWalker::traversePreviousSibling):
        (WebCore::ComposedShadowTreeWalker::nextNode):
        (WebCore::ComposedShadowTreeWalker::previousNode):
        * dom/ComposedShadowTreeWalker.h: Added.
        (WebCore):
        (ComposedShadowTreeWalker):
        (WebCore::ComposedShadowTreeWalker::get):
        (WebCore::ComposedShadowTreeWalker::canCrossUpperBoundary):
        * testing/Internals.cpp:
        (WebCore::Internals::nextSiblingByWalker):
        (WebCore):
        (WebCore::Internals::firstChildByWalker):
        (WebCore::Internals::lastChildByWalker):
        (WebCore::Internals::nextNodeByWalker):
        (WebCore::Internals::previousNodeByWalker):
        * testing/Internals.h:
        (Internals):
        * testing/Internals.idl:

2012-03-28  Antti Koivisto  <antti@apple.com>

        Split WebKitCSSKeyframeRule into internal and CSSOM types 

        * rendering/RenderLayerBacking.cpp:
        (WebCore::RenderLayerBacking::RenderLayerBacking):

2012-03-22  Hayato Ito  <hayato@chromium.org>

        Benchmark for Reified Teee Traversal APIs.
        https://bugs.webkit.org/show_bug.cgi?id=81495

        Reviewed by NOBODY (OOPS!).

        No intention to commit this patch as of now. Just for benchmarking.

        Test: fast/dom/shadow/benchmark.html

        * testing/Internals.cpp:
        (WebCore):
        (WebCore::Internals::doTraverseNextNode):
        (WebCore::Internals::doTraverseNextNodeInReifiedTree):
        * testing/Internals.h:
        (Internals):
        * testing/Internals.idl:

2012-03-23  Hayato Ito  <hayato@chromium.org>

        WIP. Walker version.
        https://bugs.webkit.org/show_bug.cgi?id=82009

        Reviewed by NOBODY (OOPS!).

        Test: fast/dom/shadow/reified-tree-walker.html

        * WebCore.gypi:
        * dom/ReifiedTreeWalker.cpp: Added.
        (WebCore):
        (WebCore::isShadowHost):
        (WebCore::shadowTreeFor):
        (WebCore::shadowTreeOfParent):
        (WebCore::ReifiedTreeWalker::firstChild):
        (WebCore::ReifiedTreeWalker::traverseFirstChild):
        (WebCore::ReifiedTreeWalker::lastChild):
        (WebCore::ReifiedTreeWalker::traverseLastChild):
        (WebCore::ReifiedTreeWalker::traverseChild):
        (WebCore::ReifiedTreeWalker::traverseLightChildren):
        (WebCore::ReifiedTreeWalker::traverseNode):
        (WebCore::ReifiedTreeWalker::nextSibling):
        (WebCore::ReifiedTreeWalker::previousSibling):
        (WebCore::ReifiedTreeWalker::traverseSiblingOrBackToInsertionPoint):
        (WebCore::ReifiedTreeWalker::traverseSiblingInCurrentTree):
        (WebCore::ReifiedTreeWalker::traverseSiblingOrBackToYoungerShadowRoot):
        (WebCore::ReifiedTreeWalker::escapeFallbackContentElement):
        (WebCore::ReifiedTreeWalker::traverseNodeEscapingFallbackContents):
        (WebCore::ReifiedTreeWalker::parentNode):
        (WebCore::ReifiedTreeWalker::traverseParentNode):
        (WebCore::ReifiedTreeWalker::traverseParentNodeInCurrentTree):
        (WebCore::ReifiedTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost):
        (WebCore::ReifiedTreeWalker::adjustedParentNode):
        (WebCore::ReifiedTreeWalker::traverseNextSibling):
        (WebCore::ReifiedTreeWalker::traversePreviousSibling):
        (WebCore::ReifiedTreeWalker::nextNode):
        (WebCore::ReifiedTreeWalker::previousNode):
        * dom/ReifiedTreeWalker.h: Added.
        (WebCore):
        (ReifiedTreeWalker):
        (WebCore::ReifiedTreeWalker::get):
        (WebCore::ReifiedTreeWalker::allowCrossingUpperBoundary):
        (WebCore::ReifiedTreeWalker::ReifiedTreeWalker):
        (WebCore::ReifiedTreeWalker::startedWithFirstChild):
        * testing/Internals.cpp:
        (WebCore::Internals::nextSiblingByWalker):
        (WebCore):
        (WebCore::Internals::firstChildByWalker):
        (WebCore::Internals::lastChildByWalker):
        (WebCore::Internals::nextNodeByWalker):
        (WebCore::Internals::previousNodeByWalker):
        * testing/Internals.h:
        (Internals):
        * testing/Internals.idl:

2012-03-21  Xingnan Wang  <xingnan.wang@intel.com>

        Web audio layout test failed in debug with an ASSERT error in ReverbConvolverStage.cpp

Lines 539-544 SET(WebCore_SOURCES a/Source/WebCore/CMakeLists.txt_sec1
- a/Source/WebCore/CMakeLists.txt +1 lines
539	dom/Clipboard.cpp	539	dom/Clipboard.cpp
540	dom/ClipboardEvent.cpp	540	dom/ClipboardEvent.cpp
541	dom/Comment.cpp	541	dom/Comment.cpp
		542	dom/ComposedShadowTreeWalker.cpp
542	dom/CompositionEvent.cpp	543	dom/CompositionEvent.cpp
543	dom/ContainerNode.cpp	544	dom/ContainerNode.cpp
544	dom/ContextDestructionObserver.cpp	545	dom/ContextDestructionObserver.cpp

Lines 1748-1753 webcore_sources += \ a/Source/WebCore/GNUmakefile.list.am_sec1
- a/Source/WebCore/GNUmakefile.list.am +2 lines
1748	Source/WebCore/dom/Clipboard.h \	1748	Source/WebCore/dom/Clipboard.h \
1749	Source/WebCore/dom/Comment.cpp \	1749	Source/WebCore/dom/Comment.cpp \
1750	Source/WebCore/dom/Comment.h \	1750	Source/WebCore/dom/Comment.h \
		1751	Source/WebCore/dom/ComposedShadowTreeWalker.cpp \
		1752	Source/WebCore/dom/ComposedShadowTreeWalker.h \
1751	Source/WebCore/dom/CompositionEvent.cpp \	1753	Source/WebCore/dom/CompositionEvent.cpp \
1752	Source/WebCore/dom/CompositionEvent.h \	1754	Source/WebCore/dom/CompositionEvent.h \
1753	Source/WebCore/dom/ContainerNodeAlgorithms.h \	1755	Source/WebCore/dom/ContainerNodeAlgorithms.h \



    dom/Clipboard.cpp \
    dom/ClipboardEvent.cpp \
    dom/Comment.cpp \
    dom/ComposedShadowTreeWalker.cpp \
    dom/CompositionEvent.cpp \
    dom/ContainerNode.cpp \
    dom/ContextDestructionObserver.cpp \

    dom/ClipboardEvent.h \
    dom/Clipboard.h \
    dom/Comment.h \
    dom/ComposedShadowTreeWalker.h \
    dom/ContainerNode.h \
    dom/CustomEvent.h \
    dom/default/PlatformMessagePortChannel.h \

Lines 665-670 __ZN7WebCore23encodeHostNameWithRangeEP8NSString8_NSRange a/Source/WebCore/WebCore.exp.in_sec1
- a/Source/WebCore/WebCore.exp.in +6 lines
665	__ZN7WebCore23getHostnamesWithCookiesERN3WTF7HashSetINS0_6StringENS0_10StringHashENS0_10HashTraitsIS2_EEEE	665	__ZN7WebCore23getHostnamesWithCookiesERN3WTF7HashSetINS0_6StringENS0_10StringHashENS0_10HashTraitsIS2_EEEE
666	__ZN7WebCore24BinaryPropertyListWriter17writePropertyListEv	666	__ZN7WebCore24BinaryPropertyListWriter17writePropertyListEv
667	__ZN7WebCore24CachedResourceHandleBase11setResourceEPNS_14CachedResourceE	667	__ZN7WebCore24CachedResourceHandleBase11setResourceEPNS_14CachedResourceE
		668	__ZN7WebCore24ComposedShadowTreeWalker10firstChildEv
		669	__ZN7WebCore24ComposedShadowTreeWalker11nextSiblingEv
		670	__ZN7WebCore24ComposedShadowTreeWalker12previousNodeEv
		671	__ZN7WebCore24ComposedShadowTreeWalker8nextNodeEv
		672	__ZN7WebCore24ComposedShadowTreeWalker9lastChildEv
		673	__ZN7WebCore24ComposedShadowTreeWalkerC1EPKNS_4NodeENS0_6PolicyE
668	__ZN7WebCore24DocumentMarkerController10markersForEPNS_4NodeENS_14DocumentMarker11MarkerTypesE	674	__ZN7WebCore24DocumentMarkerController10markersForEPNS_4NodeENS_14DocumentMarker11MarkerTypesE
669	__ZN7WebCore24DocumentMarkerController13removeMarkersENS_14DocumentMarker11MarkerTypesE	675	__ZN7WebCore24DocumentMarkerController13removeMarkersENS_14DocumentMarker11MarkerTypesE
670	__ZN7WebCore24DocumentMarkerController23renderedRectsForMarkersENS_14DocumentMarker10MarkerTypeE	676	__ZN7WebCore24DocumentMarkerController23renderedRectsForMarkersENS_14DocumentMarker10MarkerTypeE

Lines 589-594 a/Source/WebCore/WebCore.gypi_sec1
- a/Source/WebCore/WebCore.gypi +3 lines
589	'dom/CheckedRadioButtons.h',	589	'dom/CheckedRadioButtons.h',
590	'dom/Clipboard.h',	590	'dom/Clipboard.h',
591	'dom/ClipboardAccessPolicy.h',	591	'dom/ClipboardAccessPolicy.h',
		592	'dom/ComposedShadowTreeWalker.h',
592	'dom/ContainerNode.h',	593	'dom/ContainerNode.h',
593	'dom/ContextDestructionObserver.h',	594	'dom/ContextDestructionObserver.h',
594	'dom/DOMImplementation.h',	595	'dom/DOMImplementation.h',
Lines 5082-5087 a/Source/WebCore/WebCore.gypi_sec2
5082	'dom/ClipboardEvent.h',	5083	'dom/ClipboardEvent.h',
5083	'dom/Comment.cpp',	5084	'dom/Comment.cpp',
5084	'dom/Comment.h',	5085	'dom/Comment.h',
		5086	'dom/ComposedShadowTreeWalker.cpp',
		5087	'dom/ComposedShadowTreeWalker.h',
5085	'dom/CompositionEvent.cpp',	5088	'dom/CompositionEvent.cpp',
5086	'dom/CompositionEvent.h',	5089	'dom/CompositionEvent.h',
5087	'dom/ContainerNode.cpp',	5090	'dom/ContainerNode.cpp',

Lines 47926-47931 a/Source/WebCore/WebCore.vcproj/WebCore.vcproj_sec1
- a/Source/WebCore/WebCore.vcproj/WebCore.vcproj +8 lines
47926	>	47926	>
47927	</File>	47927	</File>
47928	<File	47928	<File
		47929	RelativePath="..\dom\ComposedShadowTreeWalker.cpp"
		47930	>
		47931	</File>
		47932	<File
		47933	RelativePath="..\dom\ComposedShadowTreeWalker.h"
		47934	>
		47935	</File>
		47936	<File
47929	RelativePath="..\dom\CompositionEvent.cpp"	47937	RelativePath="..\dom\CompositionEvent.cpp"
47930	>	47938	>
47931	<FileConfiguration	47939	<FileConfiguration



/*
 * Copyright (C) 2012 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "ComposedShadowTreeWalker.h"

#include "Element.h"
#include "HTMLContentSelector.h"
#include "InsertionPoint.h"
#include "ShadowTree.h"

#ifndef NDEBUG
#define ASSERT_PRECONDITION() assertPrecondition()
#else
#define ASSERT_PRECONDITION()
#endif

#ifndef NDEBUG
#define ASSERT_POSTCONDITION() assertPostcondition()
#else
#define ASSERT_POSTCONDITION()
#endif

namespace WebCore {

static inline bool isShadowHost(const Node* node)
{
    return node && node->isElementNode() && toElement(node)->hasShadowRoot();
}

static inline ShadowTree* shadowTreeFor(const Node* node)
{
    if (node && node->isElementNode())
        return toElement(node)->shadowTree();
    return 0;
}

static inline ShadowTree* shadowTreeOfParent(const Node* node)
{
    if (node && node->parentNode())
        return shadowTreeFor(node->parentNode());
    return 0;
}

ComposedShadowTreeWalker::ComposedShadowTreeWalker(const Node* node, Policy policy)
    : m_node(node)
    , m_policy(policy)
{
#ifndef NDEBUG
    assertPrecondition();
#endif
}

ComposedShadowTreeWalker ComposedShadowTreeWalker::startedWithFirstChild(const Node* node, Policy policy)
{
    ComposedShadowTreeWalker walker(node, policy);
    walker.firstChild();
    return walker;
}

#ifndef NDEBUG
void ComposedShadowTreeWalker::assertPrecondition() const
{
    ASSERT(m_node);
    if (canCrossUpperBoundary())
        ASSERT(!m_node->isShadowRoot());
    else
        ASSERT(!m_node->isShadowRoot() || toShadowRoot(m_node)->isYoungest());
    // FIXME: Add an assertion once InsertionPoint have isActive() function.
    // https://bugs.webkit.org/show_bug.cgi?id=82010
    // ASSERT(!isInsertionPoint(m_node) || !toInsertionPoint(node)->isActive());
}

void ComposedShadowTreeWalker::assertPostcondition() const
{
    if (m_node)
        assertPrecondition();
}
#endif

void ComposedShadowTreeWalker::firstChild()
{
    ASSERT_PRECONDITION();
    m_node = traverseChild(m_node, TraversalDirectionForward);
    ASSERT_POSTCONDITION();
}

Node* ComposedShadowTreeWalker::traverseFirstChild(const Node* node) const
{
    ASSERT(node);
    return traverseChild(node, TraversalDirectionForward);
}

void ComposedShadowTreeWalker::lastChild()
{
    ASSERT_PRECONDITION();
    m_node = traverseLastChild(m_node);
    ASSERT_POSTCONDITION();
}

Node* ComposedShadowTreeWalker::traverseLastChild(const Node* node) const
{
    ASSERT(node);
    return traverseChild(node, TraversalDirectionBackward);
}

Node* ComposedShadowTreeWalker::traverseChild(const Node* node, TraversalDirection direction) const
{
    ASSERT(node);
    if (canCrossUpperBoundary()) {
        ShadowTree* shadowTree = shadowTreeFor(node);
        return (shadowTree && shadowTree->hasShadowRoot()) ? traverseLightChildren(shadowTree->youngestShadowRoot(), direction)
            : traverseLightChildren(node, direction);
    }
    if (isShadowHost(node))
        return 0;
    return traverseLightChildren(node, direction);
}

Node* ComposedShadowTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction)
{
    ASSERT(node);
    if (Node* child = (direction == TraversalDirectionForward ? node->firstChild() : node->lastChild()))
        return traverseNode(child, direction);
    return 0;
}

Node* ComposedShadowTreeWalker::traverseNode(const Node* node, TraversalDirection direction)
{
    ASSERT(node);
    if (isInsertionPoint(node)) {
        const HTMLContentSelectionList* selectionList = toInsertionPoint(node)->selections();
        if (HTMLContentSelection* selection = (direction == TraversalDirectionForward ? selectionList->first() : selectionList->last()))
            return traverseNode(selection->node(), direction);
        return traverseLightChildren(node, direction);
    }
    return const_cast<Node*>(node);
}

void ComposedShadowTreeWalker::nextSibling()
{
    ASSERT_PRECONDITION();
    m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionForward);
    ASSERT_POSTCONDITION();
}

void ComposedShadowTreeWalker::previousSibling()
{
    ASSERT_PRECONDITION();
    m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionBackward);
    ASSERT_POSTCONDITION();
}

Node* ComposedShadowTreeWalker::traverseSiblingOrBackToInsertionPoint(const Node* node, TraversalDirection direction)
{
    ASSERT(node);
    ShadowTree* shadowTree = shadowTreeOfParent(node);
    if (!shadowTree)
        return traverseSiblingInCurrentTree(node, direction);
    HTMLContentSelection* selection = shadowTree->selectionFor(node);
    if (!selection)
        return traverseSiblingInCurrentTree(node, direction);
    if (HTMLContentSelection* nextSelection = (direction == TraversalDirectionForward ? selection->next() : selection->previous()))
        return traverseNode(nextSelection->node(), direction);
    return traverseSiblingOrBackToInsertionPoint(selection->insertionPoint(), direction);
}

Node* ComposedShadowTreeWalker::traverseSiblingInCurrentTree(const Node* node, TraversalDirection direction)
{
    ASSERT(node);
    if (Node* next = (direction == TraversalDirectionForward ? node->nextSibling() : node->previousSibling()))
        return traverseNode(next, direction);
    if (Node* next = traverseSiblingOrBackToYoungerShadowRoot(node, direction))
        return next;
    return escapeFallbackContentElement(node, direction);
}

Node* ComposedShadowTreeWalker::traverseSiblingOrBackToYoungerShadowRoot(const Node* node, TraversalDirection direction)
{
    ASSERT(node);
    if (node->parentNode() && node->parentNode()->isShadowRoot()) {
        ShadowRoot* parentShadowRoot = toShadowRoot(node->parentNode());
        if (!parentShadowRoot->isYoungest()) {
            InsertionPoint* assignedInsertionPoint = parentShadowRoot->assignedTo();
            ASSERT(assignedInsertionPoint);
            return traverseSiblingInCurrentTree(assignedInsertionPoint, direction);
        }
    }
    return 0;
}

Node* ComposedShadowTreeWalker::escapeFallbackContentElement(const Node* node, TraversalDirection direction)
{
    ASSERT(node);
    if (node->parentNode() && isInsertionPoint(node->parentNode()))
        return traverseSiblingOrBackToInsertionPoint(node->parentNode(), direction);
    return 0;
}

Node* ComposedShadowTreeWalker::traverseNodeEscapingFallbackContents(const Node* node) const
{
    ASSERT(node);
    if (isInsertionPoint(node))
        return traverseParentNode(node);
    return const_cast<Node*>(node);
}

void ComposedShadowTreeWalker::parentNode()
{
    ASSERT_PRECONDITION();
    m_node = traverseParentNode(m_node);
    ASSERT_POSTCONDITION();
}

Node* ComposedShadowTreeWalker::traverseParentNode(const Node* node) const
{
    if (!canCrossUpperBoundary() && node->isShadowRoot()) {
        ASSERT(toShadowRoot(node)->isYoungest());
        return 0;
    }
    if (ShadowTree* shadowTree = shadowTreeOfParent(node)) {
        if (HTMLContentSelection* selection = shadowTree->selectionFor(node))
            return traverseParentNode(selection->insertionPoint());
    }
    return traverseParentNodeInCurrentTree(node);
}

Node* ComposedShadowTreeWalker::traverseParentNodeInCurrentTree(const Node* node) const
{
    if (Node* parent = node->parentNode())
        return parent->isShadowRoot() ? traverseParentNodeBackToYoungerShadowRootOrHost(toShadowRoot(parent)) : traverseNodeEscapingFallbackContents(parent);
    return 0;
}

Node* ComposedShadowTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost(const ShadowRoot* shadowRoot) const
{
    ASSERT(shadowRoot);
    if (shadowRoot->isYoungest()) {
        if (canCrossUpperBoundary())
            return shadowRoot->host();
        return const_cast<ShadowRoot*>(shadowRoot);
    }
    InsertionPoint* assignedInsertionPoint = shadowRoot->assignedTo();
    ASSERT(assignedInsertionPoint);
    return traverseParentNode(assignedInsertionPoint);
}

// FIXME: Remove from the first version.
void ComposedShadowTreeWalker::adjustedParentNode()
{
    ASSERT(m_node);
    if (ShadowTree* shadowTree = shadowTreeOfParent(m_node)) {
        if (HTMLContentSelection* selection = shadowTree->selectionFor(m_node)) {
            m_node = selection->insertionPoint();
            return;
        }
    }
    if (!m_node->isShadowRoot()) {
        m_node = m_node->parentNode();
        return;
    }
    const ShadowRoot* shadowRoot = toShadowRoot(m_node);
    if (!shadowRoot->isYoungest()) {
        ASSERT(shadowRoot->assignedTo());
        m_node = shadowRoot->assignedTo();
        return;
    }
    if (canCrossUpperBoundary())
        m_node = shadowRoot->host();
    else
        m_node = 0;
}

Node* ComposedShadowTreeWalker::traverseNextSibling(const Node* node)
{
    ASSERT(node);
    return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
}

Node* ComposedShadowTreeWalker::traversePreviousSibling(const Node* node)
{
    ASSERT(node);
    return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
}

void ComposedShadowTreeWalker::nextNode()
{
    ASSERT_PRECONDITION();
    if (Node* next = traverseFirstChild(m_node))
        m_node = next;
    else if (Node* next = traverseNextSibling(m_node))
        m_node = next;
    else {
        const Node* n = m_node;
        while (n && !traverseNextSibling(n))
            n = traverseParentNode(n);
        m_node = n ? traverseNextSibling(n) : 0;
    }
    ASSERT_POSTCONDITION();
}

void ComposedShadowTreeWalker::previousNode()
{
    ASSERT_PRECONDITION();
    if (Node* n = traversePreviousSibling(m_node)) {
        while (Node* child = traverseLastChild(n))
            n = child;
        m_node = n;
    } else
        parentNode();
    ASSERT_POSTCONDITION();
}

} // namespace



/*
 * Copyright (C) 2012 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef ComposedShadowTreeWalker_h
#define ComposedShadowTreeWalker_h

namespace WebCore {

class Node;
class ShadowRoot;

class ComposedShadowTreeWalker {
public:
    enum Policy {
        CrossUpperBoundary,
        DoNotCrossUpperBoundary,
    };

    ComposedShadowTreeWalker(const Node*, Policy = CrossUpperBoundary);

    // For a common use case such as:
    // for (ComposedShadowTreeWalker walker = ComposedShadowTreeWalker::startedWithFirstChild(node); walker.get(); walker.nextSibling())
    static inline ComposedShadowTreeWalker startedWithFirstChild(const Node*, Policy = CrossUpperBoundary);

    Node* get() const { return const_cast<Node*>(m_node); }

    void firstChild();
    void lastChild();

    void nextSibling();
    void previousSibling();

    void parentNode();

    void nextNode();
    void previousNode();

    // FIXME: An 'adjusted' is not good name for general use case. Rename this.
    // https://bugs.webkit.org/show_bug.cgi?id=82022
    // This may return ShadowRoot or InsertionPoint.
    void adjustedParentNode();

private:
    enum TraversalDirection {
        TraversalDirectionForward,
        TraversalDirectionBackward
    };

    bool canCrossUpperBoundary() const { return m_policy == CrossUpperBoundary; }

#ifndef NDEBUG
    void assertPrecondition() const;
    void assertPostcondition() const;
#endif

    static Node* traverseNode(const Node*, TraversalDirection);
    static Node* traverseLightChildren(const Node*, TraversalDirection);

    Node* traverseFirstChild(const Node*) const;
    Node* traverseLastChild(const Node*) const;
    Node* traverseChild(const Node*, TraversalDirection) const;
    Node* traverseParentNode(const Node*) const;

    static Node* traverseNextSibling(const Node*);
    static Node* traversePreviousSibling(const Node*);

    static Node* traverseSiblingOrBackToInsertionPoint(const Node*, TraversalDirection);
    static Node* traverseSiblingInCurrentTree(const Node*, TraversalDirection);

    static Node* traverseSiblingOrBackToYoungerShadowRoot(const Node*, TraversalDirection);
    static Node* escapeFallbackContentElement(const Node*, TraversalDirection);

    Node* traverseNodeEscapingFallbackContents(const Node*) const;
    Node* traverseParentNodeInCurrentTree(const Node*) const;
    Node* traverseParentNodeBackToYoungerShadowRootOrHost(const ShadowRoot*) const;

    const Node* m_node;
    Policy m_policy;
};

} // namespace

#endif



#include "CachedResourceLoader.h"
#include "ClientRect.h"
#include "ClientRectList.h"
#include "ComposedShadowTreeWalker.h"
#include "DOMNodeHighlighter.h"
#include "Document.h"
#include "DocumentMarker.h"

    return node->attached();
}

Node* Internals::nextSiblingByWalker(Node* node, ExceptionCode& ec)
{
    if (!node) {
        ec = INVALID_ACCESS_ERR;
        return 0;
    }
    ComposedShadowTreeWalker walker(node);
    walker.nextSibling();
    return walker.get();
}

Node* Internals::firstChildByWalker(Node* node, ExceptionCode& ec)
{
    if (!node) {
        ec = INVALID_ACCESS_ERR;
        return 0;
    }
    ComposedShadowTreeWalker walker(node);
    walker.firstChild();
    return walker.get();
}

Node* Internals::lastChildByWalker(Node* node, ExceptionCode& ec)
{
    if (!node) {
        ec = INVALID_ACCESS_ERR;
        return 0;
    }
    ComposedShadowTreeWalker walker(node);
    walker.lastChild();
    return walker.get();
}

Node* Internals::nextNodeByWalker(Node* node, ExceptionCode& ec)
{
    if (!node) {
        ec = INVALID_ACCESS_ERR;
        return 0;
    }
    ComposedShadowTreeWalker walker(node);
    walker.nextNode();
    return walker.get();
}

Node* Internals::previousNodeByWalker(Node* node, ExceptionCode& ec)
{
    if (!node) {
        ec = INVALID_ACCESS_ERR;
        return 0;
    }
    ComposedShadowTreeWalker walker(node);
    walker.previousNode();
    return walker.get();
}

Node* Internals::nextSiblingInReifiedTree(Node* node, ExceptionCode& ec)
{
    if (!node) {

Lines 84-89 public: a/Source/WebCore/testing/Internals.h_sec1
- a/Source/WebCore/testing/Internals.h +7 lines
84		84
85	bool attached(Node*, ExceptionCode&);	85	bool attached(Node*, ExceptionCode&);
86		86
		87	// FIXME: Rename these functions if walker is prefered.
		88	Node* nextSiblingByWalker(Node*, ExceptionCode&);
		89	Node* firstChildByWalker(Node*, ExceptionCode&);
		90	Node* lastChildByWalker(Node*, ExceptionCode&);
		91	Node* nextNodeByWalker(Node*, ExceptionCode&);
		92	Node* previousNodeByWalker(Node*, ExceptionCode&);
		93
87	Node* nextSiblingInReifiedTree(Node*, ExceptionCode&);	94	Node* nextSiblingInReifiedTree(Node*, ExceptionCode&);
88	Node* firstChildInReifiedTree(Node*, ExceptionCode&);	95	Node* firstChildInReifiedTree(Node*, ExceptionCode&);
89	Node* lastChildInReifiedTree(Node*, ExceptionCode&);	96	Node* lastChildInReifiedTree(Node*, ExceptionCode&);

Lines 55-60 module window { a/Source/WebCore/testing/Internals.idl_sec1
- a/Source/WebCore/testing/Internals.idl -1 / +7 lines
55	Element getElementByIdInShadowRoot(in Node shadowRoot, in DOMString id) raises(DOMException);	55	Element getElementByIdInShadowRoot(in Node shadowRoot, in DOMString id) raises(DOMException);
56	boolean isValidContentSelect(in Element contentElement) raises(DOMException);	56	boolean isValidContentSelect(in Element contentElement) raises(DOMException);
57		57
		58	Node nextSiblingByWalker(in Node node) raises(DOMException);
		59	Node firstChildByWalker(in Node node) raises(DOMException);
		60	Node lastChildByWalker(in Node node) raises(DOMException);
		61	Node nextNodeByWalker(in Node node) raises(DOMException);
		62	Node previousNodeByWalker(in Node node) raises(DOMException);
		63
58	Node nextSiblingInReifiedTree(in Node node) raises(DOMException);	64	Node nextSiblingInReifiedTree(in Node node) raises(DOMException);
59	Node firstChildInReifiedTree(in Node node) raises(DOMException);	65	Node firstChildInReifiedTree(in Node node) raises(DOMException);
60	Node lastChildInReifiedTree(in Node node) raises(DOMException);	66	Node lastChildInReifiedTree(in Node node) raises(DOMException);
Lines 126-132 module window { a/Source/WebCore/testing/Internals.idl_sec2
126		132
127	#if defined(ENABLE_BATTERY_STATUS) && ENABLE_BATTERY_STATUS	133	#if defined(ENABLE_BATTERY_STATUS) && ENABLE_BATTERY_STATUS
128	void setBatteryStatus(in Document document, in DOMString eventType, in boolean charging, in double chargingTime, in double dischargingTime, in double level) raises (DOMException);	134	void setBatteryStatus(in Document document, in DOMString eventType, in boolean charging, in double chargingTime, in double dischargingTime, in double level) raises (DOMException);
129	#endif	135	#endif
130		136
131	[Conditional=INSPECTOR] unsigned long numberOfLiveNodes();	137	[Conditional=INSPECTOR] unsigned long numberOfLiveNodes();
132	[Conditional=INSPECTOR] unsigned long numberOfLiveDocuments();	138	[Conditional=INSPECTOR] unsigned long numberOfLiveDocuments();



2012-03-26  Hayato Ito  <hayato@chromium.org>

        [Shadow DOM] Add a Walker class which can traverse a Composed Shadow Tree.
        https://bugs.webkit.org/show_bug.cgi?id=82009

        Reviewed by NOBODY (OOPS!).

        * fast/dom/shadow/composed-shadow-tree-walker-expected.txt: Added.
        * fast/dom/shadow/composed-shadow-tree-walker.html: Added.

2012-03-29  Zeno Albisser  <zeno@webkit.org>

        Fieldset disabled attribute does not work.



Tests for Composed Shadow DOM Tree Traversal APIs. Can only run within DRT

On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".


ShadowRoot should be used.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b

Traverse in forward.
DIV	 id=a
DIV	 id=b
Traverse in backward.
DIV	 id=b
DIV	 id=a

A content element should select light children
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b
	DIV	 id=c
	DIV	 id=d

Traverse in forward.
DIV	 id=a
DIV	 id=b
DIV	 id=c
DIV	 id=d
Traverse in backward.
DIV	 id=d
DIV	 id=c
DIV	 id=b
DIV	 id=a

Test for content element selector.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b

Traverse in forward.
DIV	 id=a
Traverse in backward.
DIV	 id=a

Light children should be selected only at once.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b

Traverse in forward.
DIV	 id=a
DIV	 id=b
Traverse in backward.
DIV	 id=e
DIV	 id=d
DIV	 id=c
DIV	 id=a

A content element can have fallback elements.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b
	DIV	 id=f1
	DIV	 id=f2

Traverse in forward.
DIV	 id=a
DIV	 id=b
DIV	 id=f1
DIV	 id=f2
Traverse in backward.
DIV	 id=f2
DIV	 id=f1
DIV	 id=b
DIV	 id=a

Fallback elements should not be used if  element selects any elements.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b
	DIV	 id=f1
	DIV	 id=f2

Traverse in forward.
DIV	 id=a
DIV	 id=b
DIV	 id=f1
DIV	 id=f2
Traverse in backward.
DIV	 id=f2
DIV	 id=f1
DIV	 id=b
DIV	 id=a

Test for Nested ShadowRoots.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=b
		DIV	 id=c
		DIV	 id=e
		DIV	 id=d
	DIV	 id=f
	DIV	 id=h
	DIV	 id=i
	DIV	 id=g

Traverse in forward.
DIV	 id=a
DIV	 id=b
DIV	 id=c
DIV	 id=e
DIV	 id=d
DIV	 id=f
DIV	 id=h
DIV	 id=i
DIV	 id=g
Traverse in backward.
DIV	 id=g
DIV	 id=i
DIV	 id=h
DIV	 id=f
DIV	 id=d
DIV	 id=e
DIV	 id=c
DIV	 id=b
DIV	 id=a

Test for Multiple ShadowRoots.
Composed Shadow Tree:
DIV	 id=a
	DIV	 id=d
	DIV	 id=b
	DIV	 id=f
	DIV	 id=c
	DIV	 id=e

Traverse in forward.
DIV	 id=a
DIV	 id=d
DIV	 id=b
DIV	 id=f
DIV	 id=c
DIV	 id=e
Traverse in backward.
DIV	 id=e
DIV	 id=c
DIV	 id=f
DIV	 id=b
DIV	 id=d
DIV	 id=a

PASS successfullyParsed is true

TEST COMPLETE




<!DOCTYPE html>
<html>
<head>
<script src="../../js/resources/js-test-pre.js"></script>
<script src="resources/shadow-dom.js"></script>
</head>
<body>
<div id="console"></div>
<script>
description("Tests for Composed Shadow DOM Tree Traversal APIs. Can only run within DRT");

if (window.layoutTestController)
    layoutTestController.dumpAsText();

function dumpNode(node)
{
    var output = node.nodeName + "\t";
    if (node.id)
        output += ' id=' + node.id;
    if (node.className)
        output += ' class=' + node.className;
    return output;
}

function dumpComposedShadowTree(node, indent)
{
    indent = indent || "";
    var output = indent + dumpNode(node) + "\n";
    var child;
    for (child = internals.firstChildByWalker(node); child; child = internals.nextSiblingByWalker(child))
         output += dumpComposedShadowTree(child, indent + "\t");
    return output;
}

function lastNodeByWalker(root)
{
    var lastNode = root;
    while (internals.lastChildByWalker(lastNode))
        lastNode = internals.lastChildByWalker(lastNode);
    return lastNode;
}

function showComposedShadowTreeByTraversingInForward(root)
{
    var node = root;
    var last = lastNodeByWalker(root);
    while (node) {
        debug(dumpNode(node));
        if (node == last)
            break;
        node = internals.nextNodeByWalker(node);
    }
}

function showComposedShadowTreeByTraversingInBackward(root)
{
    var node = lastNodeByWalker(root);
    while (node) {
        debug(dumpNode(node));
        if (node == root)
            break;
        node = internals.previousNodeByWalker(node);
    }
}

function showComposedShadowTree(node)
{
    document.body.appendChild(node);
    document.body.offsetLeft;

    debug('Composed Shadow Tree:');
    debug(dumpComposedShadowTree(node));

    debug('Traverse in forward.');
    showComposedShadowTreeByTraversingInForward(node);

    debug('Traverse in backward.');
    showComposedShadowTreeByTraversingInBackward(node);

    debug('');
}

debug('ShadowRoot should be used.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'})),
              createDOM('div', {'id': 'c'})));

debug('A content element should select light children');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'}),
                               createDOM('content')),
              createDOM('div', {'id': 'c'}),
              createDOM('div', {'id': 'd'})));

debug('Test for content element selector.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'}),
                               createDOM('content', {'select': '.d'})),
              createDOM('div', {'id': 'c'}),
              createDOM('div', {'id': 'd'}),
              createDOM('div', {'id': 'e'})));

debug('Light children should be selected only at once.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'}),
                               createDOM('content', {'select': '.d'}),
                               createDOM('content')),
              createDOM('div', {'id': 'c'}),
              createDOM('div', {'id': 'd'}),
              createDOM('div', {'id': 'e'})));

debug('A content element can have fallback elements.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'}),
                               createDOM('content', {'select': '.z'},
                                         createDOM('div', {'id': 'f1'}),
                                         createDOM('div', {'id': 'f2'}))),
              createDOM('div', {'id': 'c'})));

debug('Fallback elements should not be used if <content> element selects any elements.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'}),
                               createDOM('content', {'select': '.c'},
                                         createDOM('div', {'id': 'f1'}),
                                         createDOM('div', {'id': 'f2'}))),
              createDOM('div', {'id': 'c'})));

debug('Test for Nested ShadowRoots.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'},
                                         createShadowRoot(createDOM('div', {'id': 'c'}),
                                                          createDOM('content'),
                                                          createDOM('div', {'id': 'd'})),
                                         createDOM('div', {'id': 'e'})),
                               createDOM('div', {'id': 'f'}),
                               createDOM('content'),
                               createDOM('div', {'id': 'g'})),
              createDOM('div', {'id': 'h'}),
              createDOM('div', {'id': 'i'})));

debug('Test for Multiple ShadowRoots.');
showComposedShadowTree(
    createDOM('div', {'id': 'a'},
              createShadowRoot(createDOM('div', {'id': 'b'}),
                               createDOM('content'),
                               createDOM('div', {'id': 'c'})),
              createShadowRoot(createDOM('div', {'id': 'd'}),
                               createDOM('shadow'),
                               createDOM('div', {'id': 'e'})),
              createDOM('div', {'id': 'f'})));

</script>
<script src="../../js/resources/js-test-post.js"></script>
</body>
</html>

Return to Bug 82009

Lines 1-3 a/Source/WebCore/ChangeLog_sec1
- a/Source/WebCore/ChangeLog +155 lines
		1	2012-03-26 Hayato Ito <hayato@chromium.org>
		2
		3	[Shadow DOM] Add a Walker class which can traverse a Composed Shadow Tree.
		4	https://bugs.webkit.org/show_bug.cgi?id=82009
		5
		6	Reviewed by NOBODY (OOPS!).
		7
		8	ComposedShadowTreeWalker is intended to be a successor of current ReifiedTreeTraversal APIs.
		9	ComposedShadowTreeWalker uses a cursor pattern and takes a starting node in its constructor.
		10
		11	The typical usage is:
		12
		13	for (ComposedShadowTreeWalker walker(node); walker.get(); walker.nextNode()) {
		14	...
		15	}
		16
		17	Follow-up patches will update clients which use current ReifiedTreeTraversal APIs so that they use the Walker.
		18	More tests will come along with these actual use cases in follow-up patches.
		19	After that, I'll get rid of ReifiedTreeTraversal APIs in favor of the Walker.
		20
		21	Note that 'ComposedShadowTree' and 'ReifiedTree' has the same meaning.
		22	Because ReifiedTree is not intuitive name, we are starting to use 'ComposedShadowTree' from now.
		23
		24	Test: fast/dom/shadow/composed-shadow-tree-walker.html
		25
		26	* CMakeLists.txt:
		27	* GNUmakefile.list.am:
		28	* Target.pri:
		29	* WebCore.exp.in:
		30	* WebCore.gypi:
		31	* WebCore.vcproj/WebCore.vcproj:
		32	* WebCore.xcodeproj/project.pbxproj:
		33	* dom/ComposedShadowTreeWalker.cpp: Added.
		34	(WebCore):
		35	(WebCore::isShadowHost):
		36	(WebCore::shadowTreeFor):
		37	(WebCore::shadowTreeOfParent):
		38	(WebCore::ComposedShadowTreeWalker::ComposedShadowTreeWalker):
		39	(WebCore::ComposedShadowTreeWalker::startedWithFirstChild):
		40	(WebCore::ComposedShadowTreeWalker::assertPrecondition):
		41	(WebCore::ComposedShadowTreeWalker::assertPostcondition):
		42	(WebCore::ComposedShadowTreeWalker::firstChild):
		43	(WebCore::ComposedShadowTreeWalker::traverseFirstChild):
		44	(WebCore::ComposedShadowTreeWalker::lastChild):
		45	(WebCore::ComposedShadowTreeWalker::traverseLastChild):
		46	(WebCore::ComposedShadowTreeWalker::traverseChild):
		47	(WebCore::ComposedShadowTreeWalker::traverseLightChildren):
		48	(WebCore::ComposedShadowTreeWalker::traverseNode):
		49	(WebCore::ComposedShadowTreeWalker::nextSibling):
		50	(WebCore::ComposedShadowTreeWalker::previousSibling):
		51	(WebCore::ComposedShadowTreeWalker::traverseSiblingOrBackToInsertionPoint):
		52	(WebCore::ComposedShadowTreeWalker::traverseSiblingInCurrentTree):
		53	(WebCore::ComposedShadowTreeWalker::traverseSiblingOrBackToYoungerShadowRoot):
		54	(WebCore::ComposedShadowTreeWalker::escapeFallbackContentElement):
		55	(WebCore::ComposedShadowTreeWalker::traverseNodeEscapingFallbackContents):
		56	(WebCore::ComposedShadowTreeWalker::parentNode):
		57	(WebCore::ComposedShadowTreeWalker::traverseParentNode):
		58	(WebCore::ComposedShadowTreeWalker::traverseParentNodeInCurrentTree):
		59	(WebCore::ComposedShadowTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost):
		60	(WebCore::ComposedShadowTreeWalker::adjustedParentNode):
		61	(WebCore::ComposedShadowTreeWalker::traverseNextSibling):
		62	(WebCore::ComposedShadowTreeWalker::traversePreviousSibling):
		63	(WebCore::ComposedShadowTreeWalker::nextNode):
		64	(WebCore::ComposedShadowTreeWalker::previousNode):
65	* dom/ComposedShadowTreeWalker.h: Added.
66	(WebCore):
67	(ComposedShadowTreeWalker):
68	(WebCore::ComposedShadowTreeWalker::get):
69	(WebCore::ComposedShadowTreeWalker::canCrossUpperBoundary):
70	* testing/Internals.cpp:
71	(WebCore::Internals::nextSiblingByWalker):
72	(WebCore):
73	(WebCore::Internals::firstChildByWalker):
74	(WebCore::Internals::lastChildByWalker):
75	(WebCore::Internals::nextNodeByWalker):
76	(WebCore::Internals::previousNodeByWalker):
77	* testing/Internals.h:
78	(Internals):
79	* testing/Internals.idl:
80
1	2012-03-28 Antti Koivisto <antti@apple.com>	81	2012-03-28 Antti Koivisto <antti@apple.com>
2		82
3	Split WebKitCSSKeyframeRule into internal and CSSOM types	83	Split WebKitCSSKeyframeRule into internal and CSSOM types
Lines 10573-10578 a/Source/WebCore/ChangeLog_sec2
10573	* rendering/RenderLayerBacking.cpp:	10653	* rendering/RenderLayerBacking.cpp:
10574	(WebCore::RenderLayerBacking::RenderLayerBacking):	10654	(WebCore::RenderLayerBacking::RenderLayerBacking):
10575		10655
		10656	2012-03-22 Hayato Ito <hayato@chromium.org>
		10657
		10658	Benchmark for Reified Teee Traversal APIs.
		10659	https://bugs.webkit.org/show_bug.cgi?id=81495
		10660
		10661	Reviewed by NOBODY (OOPS!).
		10662
		10663	No intention to commit this patch as of now. Just for benchmarking.
		10664
		10665	Test: fast/dom/shadow/benchmark.html
		10666
		10667	* testing/Internals.cpp:
		10668	(WebCore):
		10669	(WebCore::Internals::doTraverseNextNode):
		10670	(WebCore::Internals::doTraverseNextNodeInReifiedTree):
		10671	* testing/Internals.h:
		10672	(Internals):
		10673	* testing/Internals.idl:
		10674
		10675	2012-03-23 Hayato Ito <hayato@chromium.org>
		10676
		10677	WIP. Walker version.
		10678	https://bugs.webkit.org/show_bug.cgi?id=82009
		10679
		10680	Reviewed by NOBODY (OOPS!).
		10681
		10682	Test: fast/dom/shadow/reified-tree-walker.html
		10683
		10684	* WebCore.gypi:
		10685	* dom/ReifiedTreeWalker.cpp: Added.
		10686	(WebCore):
		10687	(WebCore::isShadowHost):
		10688	(WebCore::shadowTreeFor):
		10689	(WebCore::shadowTreeOfParent):
		10690	(WebCore::ReifiedTreeWalker::firstChild):
		10691	(WebCore::ReifiedTreeWalker::traverseFirstChild):
		10692	(WebCore::ReifiedTreeWalker::lastChild):
		10693	(WebCore::ReifiedTreeWalker::traverseLastChild):
		10694	(WebCore::ReifiedTreeWalker::traverseChild):
		10695	(WebCore::ReifiedTreeWalker::traverseLightChildren):
		10696	(WebCore::ReifiedTreeWalker::traverseNode):
		10697	(WebCore::ReifiedTreeWalker::nextSibling):
		10698	(WebCore::ReifiedTreeWalker::previousSibling):
		10699	(WebCore::ReifiedTreeWalker::traverseSiblingOrBackToInsertionPoint):
		10700	(WebCore::ReifiedTreeWalker::traverseSiblingInCurrentTree):
		10701	(WebCore::ReifiedTreeWalker::traverseSiblingOrBackToYoungerShadowRoot):
		10702	(WebCore::ReifiedTreeWalker::escapeFallbackContentElement):
		10703	(WebCore::ReifiedTreeWalker::traverseNodeEscapingFallbackContents):
		10704	(WebCore::ReifiedTreeWalker::parentNode):
		10705	(WebCore::ReifiedTreeWalker::traverseParentNode):
		10706	(WebCore::ReifiedTreeWalker::traverseParentNodeInCurrentTree):
		10707	(WebCore::ReifiedTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost):
		10708	(WebCore::ReifiedTreeWalker::adjustedParentNode):
		10709	(WebCore::ReifiedTreeWalker::traverseNextSibling):
		10710	(WebCore::ReifiedTreeWalker::traversePreviousSibling):
		10711	(WebCore::ReifiedTreeWalker::nextNode):
		10712	(WebCore::ReifiedTreeWalker::previousNode):
		10713	* dom/ReifiedTreeWalker.h: Added.
		10714	(WebCore):
		10715	(ReifiedTreeWalker):
		10716	(WebCore::ReifiedTreeWalker::get):
		10717	(WebCore::ReifiedTreeWalker::allowCrossingUpperBoundary):
		10718	(WebCore::ReifiedTreeWalker::ReifiedTreeWalker):
		10719	(WebCore::ReifiedTreeWalker::startedWithFirstChild):
10720	* testing/Internals.cpp:
10721	(WebCore::Internals::nextSiblingByWalker):
10722	(WebCore):
10723	(WebCore::Internals::firstChildByWalker):
10724	(WebCore::Internals::lastChildByWalker):
10725	(WebCore::Internals::nextNodeByWalker):
10726	(WebCore::Internals::previousNodeByWalker):
10727	* testing/Internals.h:
10728	(Internals):
10729	* testing/Internals.idl:
10730
10576	2012-03-21 Xingnan Wang <xingnan.wang@intel.com>	10731	2012-03-21 Xingnan Wang <xingnan.wang@intel.com>
10577		10732
10578	Web audio layout test failed in debug with an ASSERT error in ReverbConvolverStage.cpp	10733	Web audio layout test failed in debug with an ASSERT error in ReverbConvolverStage.cpp

Lines 514-519 SOURCES += \ a/Source/WebCore/Target.pri_sec1
- a/Source/WebCore/Target.pri +2 lines
514	dom/Clipboard.cpp \	514	dom/Clipboard.cpp \
515	dom/ClipboardEvent.cpp \	515	dom/ClipboardEvent.cpp \
516	dom/Comment.cpp \	516	dom/Comment.cpp \
		517	dom/ComposedShadowTreeWalker.cpp \
517	dom/CompositionEvent.cpp \	518	dom/CompositionEvent.cpp \
518	dom/ContainerNode.cpp \	519	dom/ContainerNode.cpp \
519	dom/ContextDestructionObserver.cpp \	520	dom/ContextDestructionObserver.cpp \
Lines 1655-1660 HEADERS += \ a/Source/WebCore/Target.pri_sec2
1655	dom/ClipboardEvent.h \	1656	dom/ClipboardEvent.h \
1656	dom/Clipboard.h \	1657	dom/Clipboard.h \
1657	dom/Comment.h \	1658	dom/Comment.h \
		1659	dom/ComposedShadowTreeWalker.h \
1658	dom/ContainerNode.h \	1660	dom/ContainerNode.h \
1659	dom/CustomEvent.h \	1661	dom/CustomEvent.h \
1660	dom/default/PlatformMessagePortChannel.h \	1662	dom/default/PlatformMessagePortChannel.h \

Lines 1368-1373 a/Source/WebCore/WebCore.xcodeproj/project.pbxproj_sec1
- a/Source/WebCore/WebCore.xcodeproj/project.pbxproj +8 lines
1368	4A1E71A614E106AC00626F9D /* JSShadowRoot.h in Headers / = {isa = PBXBuildFile; fileRef = 4A1E71A414E106AC00626F9D / JSShadowRoot.h */; };	1368	4A1E71A614E106AC00626F9D /* JSShadowRoot.h in Headers / = {isa = PBXBuildFile; fileRef = 4A1E71A414E106AC00626F9D / JSShadowRoot.h */; };
1369	4A38BF5014FE1C0900612512 /* WebSocketDeflateFramer.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A38BF4E14FE1C0900612512 / WebSocketDeflateFramer.cpp */; };	1369	4A38BF5014FE1C0900612512 /* WebSocketDeflateFramer.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A38BF4E14FE1C0900612512 / WebSocketDeflateFramer.cpp */; };
1370	4A38BF5114FE1C0900612512 /* WebSocketDeflateFramer.h in Headers / = {isa = PBXBuildFile; fileRef = 4A38BF4F14FE1C0900612512 / WebSocketDeflateFramer.h */; };	1370	4A38BF5114FE1C0900612512 /* WebSocketDeflateFramer.h in Headers / = {isa = PBXBuildFile; fileRef = 4A38BF4F14FE1C0900612512 / WebSocketDeflateFramer.h */; };
		1371	4A6A0C5B15232F2400B09C6E /* ComposedShadowTreeWalker.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A6A0C5915232F2400B09C6E / ComposedShadowTreeWalker.cpp */; };
		1372	4A6A0C5C15232F2400B09C6E /* ComposedShadowTreeWalker.h in Headers / = {isa = PBXBuildFile; fileRef = 4A6A0C5A15232F2400B09C6E / ComposedShadowTreeWalker.h */; };
1371	4A6E9FC313C17D1D0046A7F8 /* FontFeatureValue.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A6E9FC113C17D1D0046A7F8 / FontFeatureValue.cpp */; };	1373	4A6E9FC313C17D1D0046A7F8 /* FontFeatureValue.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A6E9FC113C17D1D0046A7F8 / FontFeatureValue.cpp */; };
1372	4A6E9FC413C17D1D0046A7F8 /* FontFeatureValue.h in Headers / = {isa = PBXBuildFile; fileRef = 4A6E9FC213C17D1D0046A7F8 / FontFeatureValue.h */; settings = {ATTRIBUTES = (Private, ); }; };	1374	4A6E9FC413C17D1D0046A7F8 /* FontFeatureValue.h in Headers / = {isa = PBXBuildFile; fileRef = 4A6E9FC213C17D1D0046A7F8 / FontFeatureValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
1373	4A6E9FC713C17D570046A7F8 /* FontFeatureSettings.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A6E9FC513C17D570046A7F8 / FontFeatureSettings.cpp */; };	1375	4A6E9FC713C17D570046A7F8 /* FontFeatureSettings.cpp in Sources / = {isa = PBXBuildFile; fileRef = 4A6E9FC513C17D570046A7F8 / FontFeatureSettings.cpp */; };
Lines 8310-8315 a/Source/WebCore/WebCore.xcodeproj/project.pbxproj_sec2
8310	4A1E71A414E106AC00626F9D /* JSShadowRoot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSShadowRoot.h; sourceTree = "<group>"; };	8312	4A1E71A414E106AC00626F9D /* JSShadowRoot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSShadowRoot.h; sourceTree = "<group>"; };
8311	4A38BF4E14FE1C0900612512 /* WebSocketDeflateFramer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = WebSocketDeflateFramer.cpp; path = Modules/websockets/WebSocketDeflateFramer.cpp; sourceTree = "<group>"; };	8313	4A38BF4E14FE1C0900612512 /* WebSocketDeflateFramer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = WebSocketDeflateFramer.cpp; path = Modules/websockets/WebSocketDeflateFramer.cpp; sourceTree = "<group>"; };
8312	4A38BF4F14FE1C0900612512 /* WebSocketDeflateFramer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = WebSocketDeflateFramer.h; path = Modules/websockets/WebSocketDeflateFramer.h; sourceTree = "<group>"; };	8314	4A38BF4F14FE1C0900612512 /* WebSocketDeflateFramer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = WebSocketDeflateFramer.h; path = Modules/websockets/WebSocketDeflateFramer.h; sourceTree = "<group>"; };
		8315	4A6A0C5915232F2400B09C6E /* ComposedShadowTreeWalker.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ComposedShadowTreeWalker.cpp; sourceTree = "<group>"; };
		8316	4A6A0C5A15232F2400B09C6E /* ComposedShadowTreeWalker.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ComposedShadowTreeWalker.h; sourceTree = "<group>"; };
8313	4A6E9FC113C17D1D0046A7F8 /* FontFeatureValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FontFeatureValue.cpp; sourceTree = "<group>"; };	8317	4A6E9FC113C17D1D0046A7F8 /* FontFeatureValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FontFeatureValue.cpp; sourceTree = "<group>"; };
8314	4A6E9FC213C17D1D0046A7F8 /* FontFeatureValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FontFeatureValue.h; sourceTree = "<group>"; };	8318	4A6E9FC213C17D1D0046A7F8 /* FontFeatureValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FontFeatureValue.h; sourceTree = "<group>"; };
8315	4A6E9FC513C17D570046A7F8 /* FontFeatureSettings.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FontFeatureSettings.cpp; sourceTree = "<group>"; };	8319	4A6E9FC513C17D570046A7F8 /* FontFeatureSettings.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FontFeatureSettings.cpp; sourceTree = "<group>"; };
Lines 20863-20868 a/Source/WebCore/WebCore.xcodeproj/project.pbxproj_sec3
20863	6550B697099DF0270090D781 /* Comment.cpp */,	20867	6550B697099DF0270090D781 /* Comment.cpp */,
20864	6550B698099DF0270090D781 /* Comment.h */,	20868	6550B698099DF0270090D781 /* Comment.h */,
20865	85089CC70A98C22600A275AA /* Comment.idl */,	20869	85089CC70A98C22600A275AA /* Comment.idl */,
		20870	4A6A0C5915232F2400B09C6E /* ComposedShadowTreeWalker.cpp */,
		20871	4A6A0C5A15232F2400B09C6E /* ComposedShadowTreeWalker.h */,
20866	79F2F59E1091939A000D87CB /* CompositionEvent.cpp */,	20872	79F2F59E1091939A000D87CB /* CompositionEvent.cpp */,
20867	79F2F59F1091939A000D87CB /* CompositionEvent.h */,	20873	79F2F59F1091939A000D87CB /* CompositionEvent.h */,
20868	79F2F5A01091939A000D87CB /* CompositionEvent.idl */,	20874	79F2F5A01091939A000D87CB /* CompositionEvent.idl */,
Lines 21684-21689 a/Source/WebCore/WebCore.xcodeproj/project.pbxproj_sec4
21684	BCDD454E1236C95C009A7985 /* ColumnInfo.h in Headers */,	21690	BCDD454E1236C95C009A7985 /* ColumnInfo.h in Headers */,
21685	6550B6A2099DF0270090D781 /* Comment.h in Headers */,	21691	6550B6A2099DF0270090D781 /* Comment.h in Headers */,
21686	37C236111097EE7700EF9F72 /* ComplexTextController.h in Headers */,	21692	37C236111097EE7700EF9F72 /* ComplexTextController.h in Headers */,
		21693	4A6A0C5C15232F2400B09C6E /* ComposedShadowTreeWalker.h in Headers */,
21687	316FE1160E6E1DA700BF6088 /* CompositeAnimation.h in Headers */,	21694	316FE1160E6E1DA700BF6088 /* CompositeAnimation.h in Headers */,
21688	93309DDD099E64920056E581 /* CompositeEditCommand.h in Headers */,	21695	93309DDD099E64920056E581 /* CompositeEditCommand.h in Headers */,
21689	79F2F5A21091939A000D87CB /* CompositionEvent.h in Headers */,	21696	79F2F5A21091939A000D87CB /* CompositionEvent.h in Headers */,
Lines 25162-25167 a/Source/WebCore/WebCore.xcodeproj/project.pbxproj_sec5
25162	37C236101097EE7700EF9F72 /* ComplexTextController.cpp in Sources */,	25169	37C236101097EE7700EF9F72 /* ComplexTextController.cpp in Sources */,
25163	37C238211098C84200EF9F72 /* ComplexTextControllerATSUI.cpp in Sources */,	25170	37C238211098C84200EF9F72 /* ComplexTextControllerATSUI.cpp in Sources */,
25164	37C238221098C84200EF9F72 /* ComplexTextControllerCoreText.mm in Sources */,	25171	37C238221098C84200EF9F72 /* ComplexTextControllerCoreText.mm in Sources */,
		25172	4A6A0C5B15232F2400B09C6E /* ComposedShadowTreeWalker.cpp in Sources */,
25165	316FE1150E6E1DA700BF6088 /* CompositeAnimation.cpp in Sources */,	25173	316FE1150E6E1DA700BF6088 /* CompositeAnimation.cpp in Sources */,
25166	93309DDC099E64920056E581 /* CompositeEditCommand.cpp in Sources */,	25174	93309DDC099E64920056E581 /* CompositeEditCommand.cpp in Sources */,
25167	79F2F5A11091939A000D87CB /* CompositionEvent.cpp in Sources */,	25175	79F2F5A11091939A000D87CB /* CompositionEvent.cpp in Sources */,

Line 0 a/Source/WebCore/dom/ComposedShadowTreeWalker.cpp_sec1
- a/Source/WebCore/dom/ComposedShadowTreeWalker.cpp +337 lines
		1	/*
		2	* Copyright (C) 2012 Google Inc. All rights reserved.
		3	*
		4	* Redistribution and use in source and binary forms, with or without
		5	* modification, are permitted provided that the following conditions are
		6	* met:
		7	*
		8	* * Redistributions of source code must retain the above copyright
		9	* notice, this list of conditions and the following disclaimer.
		10	* * Neither the name of Google Inc. nor the names of its
		11	* contributors may be used to endorse or promote products derived from
		12	* this software without specific prior written permission.
		13	*
		14	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
		15	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
		16	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
		17	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
		18	* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
		19	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
		20	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		21	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		22	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		23	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
		24	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		25	*/
		26
		27	#include "config.h"
		28	#include "ComposedShadowTreeWalker.h"
		29
		30	#include "Element.h"
		31	#include "HTMLContentSelector.h"
		32	#include "InsertionPoint.h"
		33	#include "ShadowTree.h"
		34
		35	#ifndef NDEBUG
		36	#define ASSERT_PRECONDITION() assertPrecondition()
		37	#else
		38	#define ASSERT_PRECONDITION()
		39	#endif
		40
		41	#ifndef NDEBUG
		42	#define ASSERT_POSTCONDITION() assertPostcondition()
		43	#else
		44	#define ASSERT_POSTCONDITION()
		45	#endif
		46
		47	namespace WebCore {
		48
		49	static inline bool isShadowHost(const Node* node)
		50	{
		51	return node && node->isElementNode() && toElement(node)->hasShadowRoot();
		52	}
		53
		54	static inline ShadowTree* shadowTreeFor(const Node* node)
		55	{
		56	if (node && node->isElementNode())
		57	return toElement(node)->shadowTree();
		58	return 0;
		59	}
		60
		61	static inline ShadowTree* shadowTreeOfParent(const Node* node)
		62	{
		63	if (node && node->parentNode())
		64	return shadowTreeFor(node->parentNode());
65	return 0;
66	}
67
68	ComposedShadowTreeWalker::ComposedShadowTreeWalker(const Node* node, Policy policy)
69	: m_node(node)
70	, m_policy(policy)
71	{
72	#ifndef NDEBUG
73	assertPrecondition();
74	#endif
75	}
76
77	ComposedShadowTreeWalker ComposedShadowTreeWalker::startedWithFirstChild(const Node* node, Policy policy)
78	{
79	ComposedShadowTreeWalker walker(node, policy);
80	walker.firstChild();
81	return walker;
82	}
83
84	#ifndef NDEBUG
85	void ComposedShadowTreeWalker::assertPrecondition() const
86	{
87	ASSERT(m_node);
88	if (canCrossUpperBoundary())
89	ASSERT(!m_node->isShadowRoot());
90	else
91	ASSERT(!m_node->isShadowRoot() \|\| toShadowRoot(m_node)->isYoungest());
92	// FIXME: Add an assertion once InsertionPoint have isActive() function.
93	// https://bugs.webkit.org/show_bug.cgi?id=82010
94	// ASSERT(!isInsertionPoint(m_node) \|\| !toInsertionPoint(node)->isActive());
95	}
96
97	void ComposedShadowTreeWalker::assertPostcondition() const
98	{
99	if (m_node)
100	assertPrecondition();
101	}
102	#endif
103
104	void ComposedShadowTreeWalker::firstChild()
105	{
106	ASSERT_PRECONDITION();
107	m_node = traverseChild(m_node, TraversalDirectionForward);
108	ASSERT_POSTCONDITION();
109	}
110
111	Node* ComposedShadowTreeWalker::traverseFirstChild(const Node* node) const
112	{
113	ASSERT(node);
114	return traverseChild(node, TraversalDirectionForward);
115	}
116
117	void ComposedShadowTreeWalker::lastChild()
118	{
119	ASSERT_PRECONDITION();
120	m_node = traverseLastChild(m_node);
121	ASSERT_POSTCONDITION();
122	}
123
124	Node* ComposedShadowTreeWalker::traverseLastChild(const Node* node) const
125	{
126	ASSERT(node);
127	return traverseChild(node, TraversalDirectionBackward);
128	}
129
130	Node* ComposedShadowTreeWalker::traverseChild(const Node* node, TraversalDirection direction) const
131	{
132	ASSERT(node);
133	if (canCrossUpperBoundary()) {
134	ShadowTree* shadowTree = shadowTreeFor(node);
135	return (shadowTree && shadowTree->hasShadowRoot()) ? traverseLightChildren(shadowTree->youngestShadowRoot(), direction)
136	: traverseLightChildren(node, direction);
137	}
138	if (isShadowHost(node))
139	return 0;
140	return traverseLightChildren(node, direction);
141	}
142
143	Node* ComposedShadowTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction)
144	{
145	ASSERT(node);
146	if (Node* child = (direction == TraversalDirectionForward ? node->firstChild() : node->lastChild()))
147	return traverseNode(child, direction);
148	return 0;
149	}
150
151	Node* ComposedShadowTreeWalker::traverseNode(const Node* node, TraversalDirection direction)
152	{
153	ASSERT(node);
154	if (isInsertionPoint(node)) {
155	const HTMLContentSelectionList* selectionList = toInsertionPoint(node)->selections();
156	if (HTMLContentSelection* selection = (direction == TraversalDirectionForward ? selectionList->first() : selectionList->last()))
157	return traverseNode(selection->node(), direction);
158	return traverseLightChildren(node, direction);
159	}
160	return const_cast<Node*>(node);
161	}
162
163	void ComposedShadowTreeWalker::nextSibling()
164	{
165	ASSERT_PRECONDITION();
166	m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionForward);
167	ASSERT_POSTCONDITION();
168	}
169
170	void ComposedShadowTreeWalker::previousSibling()
171	{
172	ASSERT_PRECONDITION();
173	m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionBackward);
174	ASSERT_POSTCONDITION();
175	}
176
177	Node* ComposedShadowTreeWalker::traverseSiblingOrBackToInsertionPoint(const Node* node, TraversalDirection direction)
178	{
179	ASSERT(node);
180	ShadowTree* shadowTree = shadowTreeOfParent(node);
181	if (!shadowTree)
182	return traverseSiblingInCurrentTree(node, direction);
183	HTMLContentSelection* selection = shadowTree->selectionFor(node);
184	if (!selection)
185	return traverseSiblingInCurrentTree(node, direction);
186	if (HTMLContentSelection* nextSelection = (direction == TraversalDirectionForward ? selection->next() : selection->previous()))
187	return traverseNode(nextSelection->node(), direction);
188	return traverseSiblingOrBackToInsertionPoint(selection->insertionPoint(), direction);
189	}
190
191	Node* ComposedShadowTreeWalker::traverseSiblingInCurrentTree(const Node* node, TraversalDirection direction)
192	{
193	ASSERT(node);
194	if (Node* next = (direction == TraversalDirectionForward ? node->nextSibling() : node->previousSibling()))
195	return traverseNode(next, direction);
196	if (Node* next = traverseSiblingOrBackToYoungerShadowRoot(node, direction))
197	return next;
198	return escapeFallbackContentElement(node, direction);
199	}
200
201	Node* ComposedShadowTreeWalker::traverseSiblingOrBackToYoungerShadowRoot(const Node* node, TraversalDirection direction)
202	{
203	ASSERT(node);
204	if (node->parentNode() && node->parentNode()->isShadowRoot()) {
205	ShadowRoot* parentShadowRoot = toShadowRoot(node->parentNode());
206	if (!parentShadowRoot->isYoungest()) {
207	InsertionPoint* assignedInsertionPoint = parentShadowRoot->assignedTo();
208	ASSERT(assignedInsertionPoint);
209	return traverseSiblingInCurrentTree(assignedInsertionPoint, direction);
210	}
211	}
212	return 0;
213	}
214
215	Node* ComposedShadowTreeWalker::escapeFallbackContentElement(const Node* node, TraversalDirection direction)
216	{
217	ASSERT(node);
218	if (node->parentNode() && isInsertionPoint(node->parentNode()))
219	return traverseSiblingOrBackToInsertionPoint(node->parentNode(), direction);
220	return 0;
221	}
222
223	Node* ComposedShadowTreeWalker::traverseNodeEscapingFallbackContents(const Node* node) const
224	{
225	ASSERT(node);
226	if (isInsertionPoint(node))
227	return traverseParentNode(node);
228	return const_cast<Node*>(node);
229	}
230
231	void ComposedShadowTreeWalker::parentNode()
232	{
233	ASSERT_PRECONDITION();
234	m_node = traverseParentNode(m_node);
235	ASSERT_POSTCONDITION();
236	}
237
238	Node* ComposedShadowTreeWalker::traverseParentNode(const Node* node) const
239	{
240	if (!canCrossUpperBoundary() && node->isShadowRoot()) {
241	ASSERT(toShadowRoot(node)->isYoungest());
242	return 0;
243	}
244	if (ShadowTree* shadowTree = shadowTreeOfParent(node)) {
245	if (HTMLContentSelection* selection = shadowTree->selectionFor(node))
246	return traverseParentNode(selection->insertionPoint());
247	}
248	return traverseParentNodeInCurrentTree(node);
249	}
250
251	Node* ComposedShadowTreeWalker::traverseParentNodeInCurrentTree(const Node* node) const
252	{
253	if (Node* parent = node->parentNode())
254	return parent->isShadowRoot() ? traverseParentNodeBackToYoungerShadowRootOrHost(toShadowRoot(parent)) : traverseNodeEscapingFallbackContents(parent);
255	return 0;
256	}
257
258	Node* ComposedShadowTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost(const ShadowRoot* shadowRoot) const
259	{
260	ASSERT(shadowRoot);
261	if (shadowRoot->isYoungest()) {
262	if (canCrossUpperBoundary())
263	return shadowRoot->host();
264	return const_cast<ShadowRoot*>(shadowRoot);
265	}
266	InsertionPoint* assignedInsertionPoint = shadowRoot->assignedTo();
267	ASSERT(assignedInsertionPoint);
268	return traverseParentNode(assignedInsertionPoint);
269	}
270
271	// FIXME: Remove from the first version.
272	void ComposedShadowTreeWalker::adjustedParentNode()
273	{
274	ASSERT(m_node);
275	if (ShadowTree* shadowTree = shadowTreeOfParent(m_node)) {
276	if (HTMLContentSelection* selection = shadowTree->selectionFor(m_node)) {
277	m_node = selection->insertionPoint();
278	return;
279	}
280	}
281	if (!m_node->isShadowRoot()) {
282	m_node = m_node->parentNode();
283	return;
284	}
285	const ShadowRoot* shadowRoot = toShadowRoot(m_node);
286	if (!shadowRoot->isYoungest()) {
287	ASSERT(shadowRoot->assignedTo());
288	m_node = shadowRoot->assignedTo();
289	return;
290	}
291	if (canCrossUpperBoundary())
292	m_node = shadowRoot->host();
293	else
294	m_node = 0;
295	}
296
297	Node* ComposedShadowTreeWalker::traverseNextSibling(const Node* node)
298	{
299	ASSERT(node);
300	return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
301	}
302
303	Node* ComposedShadowTreeWalker::traversePreviousSibling(const Node* node)
304	{
305	ASSERT(node);
306	return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
307	}
308
309	void ComposedShadowTreeWalker::nextNode()
310	{
311	ASSERT_PRECONDITION();
312	if (Node* next = traverseFirstChild(m_node))
313	m_node = next;
314	else if (Node* next = traverseNextSibling(m_node))
315	m_node = next;
316	else {
317	const Node* n = m_node;
318	while (n && !traverseNextSibling(n))
319	n = traverseParentNode(n);
320	m_node = n ? traverseNextSibling(n) : 0;
321	}
322	ASSERT_POSTCONDITION();
323	}
324
325	void ComposedShadowTreeWalker::previousNode()
326	{
327	ASSERT_PRECONDITION();
328	if (Node* n = traversePreviousSibling(m_node)) {
329	while (Node* child = traverseLastChild(n))
330	n = child;
331	m_node = n;
332	} else
333	parentNode();
334	ASSERT_POSTCONDITION();
335	}
336
337	} // namespace

Lines 29-34 a/Source/WebCore/testing/Internals.cpp_sec1
- a/Source/WebCore/testing/Internals.cpp +56 lines
29	#include "CachedResourceLoader.h"	29	#include "CachedResourceLoader.h"
30	#include "ClientRect.h"	30	#include "ClientRect.h"
31	#include "ClientRectList.h"	31	#include "ClientRectList.h"
		32	#include "ComposedShadowTreeWalker.h"
32	#include "DOMNodeHighlighter.h"	33	#include "DOMNodeHighlighter.h"
33	#include "Document.h"	34	#include "Document.h"
34	#include "DocumentMarker.h"	35	#include "DocumentMarker.h"
Lines 182-187 bool Internals::attached(Node* node, ExceptionCode& ec) a/Source/WebCore/testing/Internals.cpp_sec2
182	return node->attached();	183	return node->attached();
183	}	184	}
184		185
		186	Node* Internals::nextSiblingByWalker(Node* node, ExceptionCode& ec)
		187	{
		188	if (!node) {
		189	ec = INVALID_ACCESS_ERR;
		190	return 0;
		191	}
		192	ComposedShadowTreeWalker walker(node);
		193	walker.nextSibling();
		194	return walker.get();
		195	}
		196
		197	Node* Internals::firstChildByWalker(Node* node, ExceptionCode& ec)
		198	{
		199	if (!node) {
		200	ec = INVALID_ACCESS_ERR;
		201	return 0;
		202	}
		203	ComposedShadowTreeWalker walker(node);
		204	walker.firstChild();
		205	return walker.get();
		206	}
		207
		208	Node* Internals::lastChildByWalker(Node* node, ExceptionCode& ec)
		209	{
		210	if (!node) {
		211	ec = INVALID_ACCESS_ERR;
		212	return 0;
		213	}
		214	ComposedShadowTreeWalker walker(node);
		215	walker.lastChild();
		216	return walker.get();
		217	}
		218
		219	Node* Internals::nextNodeByWalker(Node* node, ExceptionCode& ec)
		220	{
		221	if (!node) {
		222	ec = INVALID_ACCESS_ERR;
		223	return 0;
		224	}
		225	ComposedShadowTreeWalker walker(node);
		226	walker.nextNode();
		227	return walker.get();
		228	}
		229
		230	Node* Internals::previousNodeByWalker(Node* node, ExceptionCode& ec)
		231	{
		232	if (!node) {
		233	ec = INVALID_ACCESS_ERR;
		234	return 0;
		235	}
		236	ComposedShadowTreeWalker walker(node);
		237	walker.previousNode();
		238	return walker.get();
		239	}
		240
185	Node* Internals::nextSiblingInReifiedTree(Node* node, ExceptionCode& ec)	241	Node* Internals::nextSiblingInReifiedTree(Node* node, ExceptionCode& ec)
186	{	242	{
187	if (!node) {	243	if (!node) {

Lines 1-3 a/LayoutTests/ChangeLog_sec1
- a/LayoutTests/ChangeLog +10 lines
		1	2012-03-26 Hayato Ito <hayato@chromium.org>
		2
		3	[Shadow DOM] Add a Walker class which can traverse a Composed Shadow Tree.
		4	https://bugs.webkit.org/show_bug.cgi?id=82009
		5
		6	Reviewed by NOBODY (OOPS!).
		7
		8	* fast/dom/shadow/composed-shadow-tree-walker-expected.txt: Added.
		9	* fast/dom/shadow/composed-shadow-tree-walker.html: Added.
		10
1	2012-03-29 Zeno Albisser <zeno@webkit.org>	11	2012-03-29 Zeno Albisser <zeno@webkit.org>
2		12
3	Fieldset disabled attribute does not work.	13	Fieldset disabled attribute does not work.

Line 0 a/LayoutTests/fast/dom/shadow/composed-shadow-tree-walker-expected.txt_sec1
- a/LayoutTests/fast/dom/shadow/composed-shadow-tree-walker-expected.txt +156 lines
		1	Tests for Composed Shadow DOM Tree Traversal APIs. Can only run within DRT
		2
		3	On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
		4
		5
		6	ShadowRoot should be used.
		7	Composed Shadow Tree:
		8	DIV id=a
		9	DIV id=b
		10
		11	Traverse in forward.
		12	DIV id=a
		13	DIV id=b
		14	Traverse in backward.
		15	DIV id=b
		16	DIV id=a
		17
		18	A content element should select light children
		19	Composed Shadow Tree:
		20	DIV id=a
		21	DIV id=b
		22	DIV id=c
		23	DIV id=d
		24
		25	Traverse in forward.
		26	DIV id=a
		27	DIV id=b
		28	DIV id=c
		29	DIV id=d
		30	Traverse in backward.
		31	DIV id=d
		32	DIV id=c
		33	DIV id=b
		34	DIV id=a
		35
		36	Test for content element selector.
		37	Composed Shadow Tree:
		38	DIV id=a
		39	DIV id=b
		40
		41	Traverse in forward.
		42	DIV id=a
		43	Traverse in backward.
		44	DIV id=a
		45
		46	Light children should be selected only at once.
		47	Composed Shadow Tree:
		48	DIV id=a
		49	DIV id=b
		50
		51	Traverse in forward.
		52	DIV id=a
		53	DIV id=b
		54	Traverse in backward.
		55	DIV id=e
		56	DIV id=d
		57	DIV id=c
		58	DIV id=a
		59
		60	A content element can have fallback elements.
		61	Composed Shadow Tree:
		62	DIV id=a
		63	DIV id=b
		64	DIV id=f1
65	DIV id=f2
66
67	Traverse in forward.
68	DIV id=a
69	DIV id=b
70	DIV id=f1
71	DIV id=f2
72	Traverse in backward.
73	DIV id=f2
74	DIV id=f1
75	DIV id=b
76	DIV id=a
77
78	Fallback elements should not be used if element selects any elements.
79	Composed Shadow Tree:
80	DIV id=a
81	DIV id=b
82	DIV id=f1
83	DIV id=f2
84
85	Traverse in forward.
86	DIV id=a
87	DIV id=b
88	DIV id=f1
89	DIV id=f2
90	Traverse in backward.
91	DIV id=f2
92	DIV id=f1
93	DIV id=b
94	DIV id=a
95
96	Test for Nested ShadowRoots.
97	Composed Shadow Tree:
98	DIV id=a
99	DIV id=b
100	DIV id=c
101	DIV id=e
102	DIV id=d
103	DIV id=f
104	DIV id=h
105	DIV id=i
106	DIV id=g
107
108	Traverse in forward.
109	DIV id=a
110	DIV id=b
111	DIV id=c
112	DIV id=e
113	DIV id=d
114	DIV id=f
115	DIV id=h
116	DIV id=i
117	DIV id=g
118	Traverse in backward.
119	DIV id=g
120	DIV id=i
121	DIV id=h
122	DIV id=f
123	DIV id=d
124	DIV id=e
125	DIV id=c
126	DIV id=b
127	DIV id=a
128
129	Test for Multiple ShadowRoots.
130	Composed Shadow Tree:
131	DIV id=a
132	DIV id=d
133	DIV id=b
134	DIV id=f
135	DIV id=c
136	DIV id=e
137
138	Traverse in forward.
139	DIV id=a
140	DIV id=d
141	DIV id=b
142	DIV id=f
143	DIV id=c
144	DIV id=e
145	Traverse in backward.
146	DIV id=e
147	DIV id=c
148	DIV id=f
149	DIV id=b
150	DIV id=d
151	DIV id=a
152
153	PASS successfullyParsed is true
154
155	TEST COMPLETE
156

Line 0 a/LayoutTests/fast/dom/shadow/composed-shadow-tree-walker.html_sec1
- a/LayoutTests/fast/dom/shadow/composed-shadow-tree-walker.html +162 lines
		1	<!DOCTYPE html>
		2	<html>
		3	<head>
		4	<script src="../../js/resources/js-test-pre.js"></script>
		5	<script src="resources/shadow-dom.js"></script>
		6	</head>
		7	<body>
		8	<div id="console"></div>
		9	<script>
		10	description("Tests for Composed Shadow DOM Tree Traversal APIs. Can only run within DRT");
		11
		12	if (window.layoutTestController)
		13	layoutTestController.dumpAsText();
		14
		15	function dumpNode(node)
		16	{
		17	var output = node.nodeName + "\t";
		18	if (node.id)
		19	output += ' id=' + node.id;
		20	if (node.className)
		21	output += ' class=' + node.className;
		22	return output;
		23	}
		24
		25	function dumpComposedShadowTree(node, indent)
		26	{
		27	indent = indent \|\| "";
		28	var output = indent + dumpNode(node) + "\n";
		29	var child;
		30	for (child = internals.firstChildByWalker(node); child; child = internals.nextSiblingByWalker(child))
		31	output += dumpComposedShadowTree(child, indent + "\t");
		32	return output;
		33	}
		34
		35	function lastNodeByWalker(root)
		36	{
		37	var lastNode = root;
		38	while (internals.lastChildByWalker(lastNode))
		39	lastNode = internals.lastChildByWalker(lastNode);
		40	return lastNode;
		41	}
		42
		43	function showComposedShadowTreeByTraversingInForward(root)
		44	{
		45	var node = root;
		46	var last = lastNodeByWalker(root);
		47	while (node) {
		48	debug(dumpNode(node));
		49	if (node == last)
		50	break;
		51	node = internals.nextNodeByWalker(node);
		52	}
		53	}
		54
		55	function showComposedShadowTreeByTraversingInBackward(root)
		56	{
		57	var node = lastNodeByWalker(root);
		58	while (node) {
		59	debug(dumpNode(node));
		60	if (node == root)
		61	break;
		62	node = internals.previousNodeByWalker(node);
		63	}
		64	}
65
66	function showComposedShadowTree(node)
67	{
68	document.body.appendChild(node);
69	document.body.offsetLeft;
70
71	debug('Composed Shadow Tree:');
72	debug(dumpComposedShadowTree(node));
73
74	debug('Traverse in forward.');
75	showComposedShadowTreeByTraversingInForward(node);
76
77	debug('Traverse in backward.');
78	showComposedShadowTreeByTraversingInBackward(node);
79
80	debug('');
81	}
82
83	debug('ShadowRoot should be used.');
84	showComposedShadowTree(
85	createDOM('div', {'id': 'a'},
86	createShadowRoot(createDOM('div', {'id': 'b'})),
87	createDOM('div', {'id': 'c'})));
88
89	debug('A content element should select light children');
90	showComposedShadowTree(
91	createDOM('div', {'id': 'a'},
92	createShadowRoot(createDOM('div', {'id': 'b'}),
93	createDOM('content')),
94	createDOM('div', {'id': 'c'}),
95	createDOM('div', {'id': 'd'})));
96
97	debug('Test for content element selector.');
98	showComposedShadowTree(
99	createDOM('div', {'id': 'a'},
100	createShadowRoot(createDOM('div', {'id': 'b'}),
101	createDOM('content', {'select': '.d'})),
102	createDOM('div', {'id': 'c'}),
103	createDOM('div', {'id': 'd'}),
104	createDOM('div', {'id': 'e'})));
105
106	debug('Light children should be selected only at once.');
107	showComposedShadowTree(
108	createDOM('div', {'id': 'a'},
109	createShadowRoot(createDOM('div', {'id': 'b'}),
110	createDOM('content', {'select': '.d'}),
111	createDOM('content')),
112	createDOM('div', {'id': 'c'}),
113	createDOM('div', {'id': 'd'}),
114	createDOM('div', {'id': 'e'})));
115
116	debug('A content element can have fallback elements.');
117	showComposedShadowTree(
118	createDOM('div', {'id': 'a'},
119	createShadowRoot(createDOM('div', {'id': 'b'}),
120	createDOM('content', {'select': '.z'},
121	createDOM('div', {'id': 'f1'}),
122	createDOM('div', {'id': 'f2'}))),
123	createDOM('div', {'id': 'c'})));
124
125	debug('Fallback elements should not be used if <content> element selects any elements.');
126	showComposedShadowTree(
127	createDOM('div', {'id': 'a'},
128	createShadowRoot(createDOM('div', {'id': 'b'}),
129	createDOM('content', {'select': '.c'},
130	createDOM('div', {'id': 'f1'}),
131	createDOM('div', {'id': 'f2'}))),
132	createDOM('div', {'id': 'c'})));
133
134	debug('Test for Nested ShadowRoots.');
135	showComposedShadowTree(
136	createDOM('div', {'id': 'a'},
137	createShadowRoot(createDOM('div', {'id': 'b'},
138	createShadowRoot(createDOM('div', {'id': 'c'}),
139	createDOM('content'),
140	createDOM('div', {'id': 'd'})),
141	createDOM('div', {'id': 'e'})),
142	createDOM('div', {'id': 'f'}),
143	createDOM('content'),
144	createDOM('div', {'id': 'g'})),
145	createDOM('div', {'id': 'h'}),
146	createDOM('div', {'id': 'i'})));
147
148	debug('Test for Multiple ShadowRoots.');
149	showComposedShadowTree(
150	createDOM('div', {'id': 'a'},
151	createShadowRoot(createDOM('div', {'id': 'b'}),
152	createDOM('content'),
153	createDOM('div', {'id': 'c'})),
154	createShadowRoot(createDOM('div', {'id': 'd'}),
155	createDOM('shadow'),
156	createDOM('div', {'id': 'e'})),
157	createDOM('div', {'id': 'f'})));
158
159	</script>
160	<script src="../../js/resources/js-test-post.js"></script>
161	</body>
162	</html>