Streamline PODIntervalTree code and remove ValueToString
authordarin@apple.com <darin@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 9 Dec 2019 17:12:48 +0000 (17:12 +0000)
committerdarin@apple.com <darin@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 9 Dec 2019 17:12:48 +0000 (17:12 +0000)
https://bugs.webkit.org/show_bug.cgi?id=199782

Reviewed by Anders Carlsson.

Source/WebCore:

* dom/Element.cpp: Updated includes.

* html/HTMLMediaElement.cpp:
(WebCore::HTMLMediaElement::ignoreTrackDisplayUpdateRequests const): Moved this
function out of line so we don't have to include PODIntervalTree.h in the header.
But also, it's only used inside this file. Also updated for m_cueData.
(WebCore::HTMLMediaElement::updateActiveTextTrackCues): More of the same.
(WebCore::HTMLMediaElement::textTrackAddCue): Ditto.
(WebCore::HTMLMediaElement::textTrackRemoveCue): Ditto.
(WebCore::HTMLMediaElement::currentlyActiveCues const): Ditto.

* html/HTMLMediaElement.h: Changed to not include PODIntervalTree.h, which in turn
includes PODRedBlackTree.h, to significantly cut down how many times we have to
compile those headers. Moved some functions out of line. Made m_cueData to hold the
two cue-related objects so they don't have to be defined in the header. Also
removed ValueToString specializations.

* html/track/TextTrackCue.cpp:
(WebCore::operator<<): Added debug-only overload of TextStream operator.
(WebCore::TextTrackCue::debugString const): Deleted.
* html/track/TextTrackCue.h: Updated for the above.

* html/track/VTTCue.h: Added comments about the incorrect implementation of
isType for VTTCue. Tweaked formatting a bit as well.

* platform/LayoutUnit.h: Removed ValueToString specialization.

* platform/PODInterval.h: Use #pragma once. Removed inaccurate comments
saying this works only with POD. Use TextStream instead of ValueToString.
Added overloads to the constructor so we can do move semantics instead of
copy semantics, slightly better for WeakPtr. Removed the toString function
and added an overload of operator<< with TextStream. Use "{ }" instead of
"0" as the default value for user data.

* platform/PODIntervalTree.h: Removed unneeded includes and unusual default
argument types for the templates. Changed setNeedsFullOrderingComparisons
and node updating to use template arguments instead of virtual functions
and runtime setters. This allowed removal of the constructor and the init
function since the defaults take care of both. Removed the overload of
the allOverlaps function that uses an out argument. Removed unneeded use
of WTF_MAKE_NONCOPYABLE. Use "{ }" instead of 0 for the default value
for user data. Changed the createInterval function to use move semantics.
Changed the nextIntervalAfter function to just take a point, not require
and interval and use its high point. The PODIntervalTree::updateNode
function is replaced with the PODIntervalNodeUpdater::update function.
Removed the ValueToString use and the overriding as well and replaced
with TextStream use.

* platform/PODRedBlackTree.h: Updated comments to reflect the fact
that this is not specific to POD and uses TextStream. Also that the
needsFullOrderingComparisons technique is now a template argument.
Use pragma once. Added FIXME about a few major improvements we should
make.
(WebCore::PODRedBlackTree::~PODRedBlackTree): Made non-virtual since
we use template arguments for polymorphism and don't need virtual
functions too.
(WebCore::PODRedBlackTree::clear): Rewrote to use a non-recursive
algorithm to delete the tree nodes.
(WebCore::PODRedBlackTree::add): Added an overload that takes an
rvalue reference for move semantics.
(WebCore::PODRedBlackTree::visitInorder const): Deleted.
(WebCore::PODRedBlackTree::size const): Deleted.
(WebCore::PODRedBlackTree::isEmpty const): Replaced the inefficiently
implemented size function with this much faster function. Could have
also made a more efficient size function, but no client needs it.
(WebCore::PODRedBlackTree::setNeedsFullOrderingComparisons): Deleted.
(WebCore::PODRedBlackTree::checkInvariants const): Made non-virtual
since there is no need for polymorphism.
(WebCore::PODRedBlackTree::Node::Node): Use rvalue reference and
move semantics.
(WebCore::PODRedBlackTree::Node::copyFrom): Deleted.
(WebCore::PODRedBlackTree::Node::moveDataFrom): Use move instead of
copy. Also removed the gratuitous use of virtual.
(WebCore::PODRedBlackTree::updateNode): Made non-virtual and instead
call through the NodeUpdaterType (actually more like "traits").
(WebCore::PODRedBlackTree::treeSearch const): Use template argument
instead of data member.
(WebCore::PODRedBlackTree::treeSuccessor): Made a static member function.
(WebCore::PODRedBlackTree::treeMinimum): Ditto.
(WebCore::PODRedBlackTree::treeSuccessorInPostOrder): Added. Useful
when deleting the tree so we visit children before deleting the parent.
(WebCore::PODRedBlackTree::deleteNode): Use moveDataFrom when moving
the data from a node that we are about to delete.
(WebCore::PODRedBlackTree::visitInorderImpl const): Deleted.
(WebCore::PODRedBlackTree::markFree): Deleted.
(WebCore::PODRedBlackTree::Counter): Deleted.
(WebCore::PODRedBlackTree::dumpFromNode const): Use TextStream.

* platform/graphics/FloatPolygon.cpp:
(WebCore::FloatPolygon::FloatPolygon): Tweaked coding style a bit.
(WebCore::FloatPolygon::overlappingEdges const): Changed to use a return
value instead of an out argument. Also tweaked coding style a bit.
(WebCore::FloatPolygonEdge::debugString const): Deleted.
(WebCore::ooperator>>): Implemented TextStream overload.

* platform/graphics/FloatPolygon.h: Updated for above, removed
ValueToString specialization.

* rendering/FloatingObjects.cpp:
(WebCore::FloatingObject::debugString const): Deleted.
(WebCore::operator<<): Implemented TextStream overload.
* rendering/FloatingObjects.h: Ditto. Also removed include of
PODIntervalTree.h and used a forward declaration instead.

* rendering/RenderBlock.cpp: Updated includes.

* rendering/RenderFragmentContainer.cpp:
(WebCore::RenderFragmentContainer::debugString const): Deleted.
(WebCore::operator<<): Implemented TextStream overload.
* rendering/RenderFragmentContainer.h: Ditto.

* rendering/RenderFragmentedFlow.cpp:
(WebCore::RenderFragmentedFlow::FragmentSearchAdapter::FragmentSearchAdapter):
Moved this class here from the header, moving the one function body that was
already here up in the file.
(WebCore::RenderFragmentedFlow::fragmentAtBlockOffset const): Refactored and
tweaked code sequence a bit, did not change logic.
(WebCore::RenderFragmentedFlow::updateFragmentsFragmentedFlowPortionRect):
Tweaked code style a bit.

* rendering/RenderFragmentedFlow.h: Moved FragmentSearchAdapter out of the
header, and tweaked coding style a bit. Removed ValueToString specialization.

* rendering/shapes/PolygonShape.cpp:
(WebCore::PolygonShape::getExcludedInterval const): Updated to use the
return value from the overlappingEdges function rather than an out argument.

* rendering/updating/RenderTreeBuilder.cpp: Updated includes.
* rendering/updating/RenderTreeBuilderFirstLetter.h: Updated forward declarations.
* rendering/updating/RenderTreeBuilderMultiColumn.cpp: Updated includes.

* rendering/updating/RenderTreePosition.h: Removed includes of
RenderFragmentedFlow.h, RenderText.h, and RenderView.h, since none are
needed by this header.

* rendering/updating/RenderTreeUpdater.cpp: Updated includes.

Source/WTF:

* WTF.xcodeproj/project.pbxproj: Remove ValueToString.h.
* wtf/CMakeLists.txt: Ditto.

* wtf/MediaTime.cpp:
(WTF::operator<<): Implement debug-only TextStream serialization
based on toJSONString.
* wtf/MediaTime.h: Ditto.

* wtf/text/ValueToString.h: Removed.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@253290 268f45cc-cd09-0410-ab3c-d52691b4dbfc

32 files changed:
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/MediaTime.cpp
Source/WTF/wtf/MediaTime.h
Source/WTF/wtf/text/ValueToString.h [deleted file]
Source/WebCore/ChangeLog
Source/WebCore/dom/Element.cpp
Source/WebCore/html/HTMLMediaElement.cpp
Source/WebCore/html/HTMLMediaElement.h
Source/WebCore/html/track/TextTrackCue.cpp
Source/WebCore/html/track/TextTrackCue.h
Source/WebCore/html/track/VTTCue.h
Source/WebCore/platform/LayoutUnit.h
Source/WebCore/platform/PODInterval.h
Source/WebCore/platform/PODIntervalTree.h
Source/WebCore/platform/PODRedBlackTree.h
Source/WebCore/platform/graphics/FloatPolygon.cpp
Source/WebCore/platform/graphics/FloatPolygon.h
Source/WebCore/rendering/FloatingObjects.cpp
Source/WebCore/rendering/FloatingObjects.h
Source/WebCore/rendering/RenderBlock.cpp
Source/WebCore/rendering/RenderFragmentContainer.cpp
Source/WebCore/rendering/RenderFragmentContainer.h
Source/WebCore/rendering/RenderFragmentedFlow.cpp
Source/WebCore/rendering/RenderFragmentedFlow.h
Source/WebCore/rendering/shapes/PolygonShape.cpp
Source/WebCore/rendering/updating/RenderTreeBuilder.cpp
Source/WebCore/rendering/updating/RenderTreeBuilderFirstLetter.h
Source/WebCore/rendering/updating/RenderTreeBuilderMultiColumn.cpp
Source/WebCore/rendering/updating/RenderTreePosition.h
Source/WebCore/rendering/updating/RenderTreeUpdater.cpp

index 2b9cb97..7a3ee37 100644 (file)
@@ -1,3 +1,20 @@
+2019-07-13  Darin Adler  <darin@apple.com>
+
+        Streamline PODIntervalTree code and remove ValueToString
+        https://bugs.webkit.org/show_bug.cgi?id=199782
+
+        Reviewed by Anders Carlsson.
+
+        * WTF.xcodeproj/project.pbxproj: Remove ValueToString.h.
+        * wtf/CMakeLists.txt: Ditto.
+
+        * wtf/MediaTime.cpp:
+        (WTF::operator<<): Implement debug-only TextStream serialization
+        based on toJSONString.
+        * wtf/MediaTime.h: Ditto.
+
+        * wtf/text/ValueToString.h: Removed.
+
 2019-12-06  Zan Dobersek  <zdobersek@igalia.com>
 
         [GTK][WPE] Use bmalloc's memory footprint API for JSC heap growth management
index 9de84ec..8e8ec15 100644 (file)
                A331D96021F24A0A009F02AA /* FileSystemMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = FileSystemMac.mm; sourceTree = "<group>"; };
                A331D96621F24ABD009F02AA /* FileSystemPOSIX.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FileSystemPOSIX.cpp; sourceTree = "<group>"; };
                A36E16F7216FF828008DD87E /* WTFSemaphore.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WTFSemaphore.h; sourceTree = "<group>"; };
-               A3AB6E6A1F3E1AD6009C14B1 /* ValueToString.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ValueToString.h; sourceTree = "<group>"; };
                A3D273B921F2EE9100866971 /* MetadataSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MetadataSPI.h; sourceTree = "<group>"; };
                A3E4DD911F3A803400DED0B4 /* TextStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TextStream.cpp; sourceTree = "<group>"; };
                A3E4DD921F3A803400DED0B4 /* TextStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TextStream.h; sourceTree = "<group>"; };
                                A3E4DD921F3A803400DED0B4 /* TextStream.h */,
                                70ECA60C1B02426800449739 /* UniquedStringImpl.h */,
                                FEF295BF20B49DCB00CF283A /* UTF8ConversionError.h */,
-                               A3AB6E6A1F3E1AD6009C14B1 /* ValueToString.h */,
                                A8A4732D151A825B004123FF /* WTFString.cpp */,
                                A8A4732E151A825B004123FF /* WTFString.h */,
                        );
index ff5d272..afcc60e 100644 (file)
@@ -328,7 +328,6 @@ set(WTF_PUBLIC_HEADERS
     text/TextStream.h
     text/UTF8ConversionError.h
     text/UniquedStringImpl.h
-    text/ValueToString.h
     text/WTFString.h
 
     text/icu/TextBreakIteratorICU.h
index 414a9b4..2845d78 100644 (file)
@@ -37,6 +37,7 @@
 #include <wtf/MathExtras.h>
 #include <wtf/PrintStream.h>
 #include <wtf/text/StringBuilder.h>
+#include <wtf/text/TextStream.h>
 
 namespace WTF {
 
@@ -656,4 +657,13 @@ String MediaTimeRange::toJSONString() const
     return object->toJSONString();
 }
 
+#ifndef NDEBUG
+
+TextStream& operator<<(TextStream& stream, const MediaTime& time)
+{
+    return stream << time.toJSONString();
+}
+
+#endif
+
 }
index 6daf112..56f55b0 100644 (file)
@@ -176,25 +176,19 @@ bool MediaTime::decode(Decoder& decoder, MediaTime& time)
         && decoder.decode(time.m_timeFlags);
 }
 
-template<typename Type>
-struct LogArgument;
-
-template <>
-struct LogArgument<MediaTime> {
-    static String toString(const MediaTime& time)
-    {
-        return time.toJSONString();
-    }
-};
+template<typename> struct LogArgument;
 
-template <>
-struct LogArgument<MediaTimeRange> {
-    static String toString(const MediaTimeRange& range)
-    {
-        return range.toJSONString();
-    }
+template<> struct LogArgument<MediaTime> {
+    static String toString(const MediaTime& time) { return time.toJSONString(); }
+};
+template<> struct LogArgument<MediaTimeRange> {
+    static String toString(const MediaTimeRange& range) { return range.toJSONString(); }
 };
 
+#ifndef NDEBUG
+WTF_EXPORT_PRIVATE TextStream& operator<<(TextStream&, const MediaTime&);
+#endif
+
 }
 
 using WTF::MediaTime;
diff --git a/Source/WTF/wtf/text/ValueToString.h b/Source/WTF/wtf/text/ValueToString.h
deleted file mode 100644 (file)
index c1ef993..0000000
+++ /dev/null
@@ -1,56 +0,0 @@
-/*
- * Copyright (C) 2013 Adobe Systems Incorporated. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above
- *    copyright notice, this list of conditions and the following
- *    disclaimer.
- * 2. Redistributions in binary form must reproduce the above
- *    copyright notice, this list of conditions and the following
- *    disclaimer in the documentation and/or other materials
- *    provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER "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 HOLDER 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.
- */
-
-#pragma once
-
-#ifndef NDEBUG
-
-#include <wtf/text/WTFString.h>
-
-namespace WTF {
-
-template<typename> struct ValueToString;
-
-template<> struct ValueToString<int> {
-    static String string(int value) { return String::number(value); }
-};
-
-template<> struct ValueToString<float> {
-    static String string(float value) { return String::numberToStringFixedPrecision(value); }
-};
-
-template<> struct ValueToString<double> {
-    static String string(double value) { return String::numberToStringFixedPrecision(value); }
-};
-
-} // namespace WTF
-
-using WTF::ValueToString;
-
-#endif
index 2ee6049..9ccd031 100644 (file)
@@ -1,3 +1,147 @@
+2019-12-07  Darin Adler  <darin@apple.com>
+
+        Streamline PODIntervalTree code and remove ValueToString
+        https://bugs.webkit.org/show_bug.cgi?id=199782
+
+        Reviewed by Anders Carlsson.
+
+        * dom/Element.cpp: Updated includes.
+
+        * html/HTMLMediaElement.cpp:
+        (WebCore::HTMLMediaElement::ignoreTrackDisplayUpdateRequests const): Moved this
+        function out of line so we don't have to include PODIntervalTree.h in the header.
+        But also, it's only used inside this file. Also updated for m_cueData.
+        (WebCore::HTMLMediaElement::updateActiveTextTrackCues): More of the same.
+        (WebCore::HTMLMediaElement::textTrackAddCue): Ditto.
+        (WebCore::HTMLMediaElement::textTrackRemoveCue): Ditto.
+        (WebCore::HTMLMediaElement::currentlyActiveCues const): Ditto.
+
+        * html/HTMLMediaElement.h: Changed to not include PODIntervalTree.h, which in turn
+        includes PODRedBlackTree.h, to significantly cut down how many times we have to
+        compile those headers. Moved some functions out of line. Made m_cueData to hold the
+        two cue-related objects so they don't have to be defined in the header. Also
+        removed ValueToString specializations.
+
+        * html/track/TextTrackCue.cpp:
+        (WebCore::operator<<): Added debug-only overload of TextStream operator.
+        (WebCore::TextTrackCue::debugString const): Deleted.
+        * html/track/TextTrackCue.h: Updated for the above.
+
+        * html/track/VTTCue.h: Added comments about the incorrect implementation of
+        isType for VTTCue. Tweaked formatting a bit as well.
+
+        * platform/LayoutUnit.h: Removed ValueToString specialization.
+
+        * platform/PODInterval.h: Use #pragma once. Removed inaccurate comments
+        saying this works only with POD. Use TextStream instead of ValueToString.
+        Added overloads to the constructor so we can do move semantics instead of
+        copy semantics, slightly better for WeakPtr. Removed the toString function
+        and added an overload of operator<< with TextStream. Use "{ }" instead of
+        "0" as the default value for user data.
+
+        * platform/PODIntervalTree.h: Removed unneeded includes and unusual default
+        argument types for the templates. Changed setNeedsFullOrderingComparisons
+        and node updating to use template arguments instead of virtual functions
+        and runtime setters. This allowed removal of the constructor and the init
+        function since the defaults take care of both. Removed the overload of
+        the allOverlaps function that uses an out argument. Removed unneeded use
+        of WTF_MAKE_NONCOPYABLE. Use "{ }" instead of 0 for the default value
+        for user data. Changed the createInterval function to use move semantics.
+        Changed the nextIntervalAfter function to just take a point, not require
+        and interval and use its high point. The PODIntervalTree::updateNode
+        function is replaced with the PODIntervalNodeUpdater::update function.
+        Removed the ValueToString use and the overriding as well and replaced
+        with TextStream use.
+
+        * platform/PODRedBlackTree.h: Updated comments to reflect the fact
+        that this is not specific to POD and uses TextStream. Also that the
+        needsFullOrderingComparisons technique is now a template argument.
+        Use pragma once. Added FIXME about a few major improvements we should
+        make.
+        (WebCore::PODRedBlackTree::~PODRedBlackTree): Made non-virtual since
+        we use template arguments for polymorphism and don't need virtual
+        functions too.
+        (WebCore::PODRedBlackTree::clear): Rewrote to use a non-recursive
+        algorithm to delete the tree nodes.
+        (WebCore::PODRedBlackTree::add): Added an overload that takes an
+        rvalue reference for move semantics.
+        (WebCore::PODRedBlackTree::visitInorder const): Deleted.
+        (WebCore::PODRedBlackTree::size const): Deleted.
+        (WebCore::PODRedBlackTree::isEmpty const): Replaced the inefficiently
+        implemented size function with this much faster function. Could have
+        also made a more efficient size function, but no client needs it.
+        (WebCore::PODRedBlackTree::setNeedsFullOrderingComparisons): Deleted.
+        (WebCore::PODRedBlackTree::checkInvariants const): Made non-virtual
+        since there is no need for polymorphism.
+        (WebCore::PODRedBlackTree::Node::Node): Use rvalue reference and
+        move semantics.
+        (WebCore::PODRedBlackTree::Node::copyFrom): Deleted.
+        (WebCore::PODRedBlackTree::Node::moveDataFrom): Use move instead of
+        copy. Also removed the gratuitous use of virtual.
+        (WebCore::PODRedBlackTree::updateNode): Made non-virtual and instead
+        call through the NodeUpdaterType (actually more like "traits").
+        (WebCore::PODRedBlackTree::treeSearch const): Use template argument
+        instead of data member.
+        (WebCore::PODRedBlackTree::treeSuccessor): Made a static member function.
+        (WebCore::PODRedBlackTree::treeMinimum): Ditto.
+        (WebCore::PODRedBlackTree::treeSuccessorInPostOrder): Added. Useful
+        when deleting the tree so we visit children before deleting the parent.
+        (WebCore::PODRedBlackTree::deleteNode): Use moveDataFrom when moving
+        the data from a node that we are about to delete.
+        (WebCore::PODRedBlackTree::visitInorderImpl const): Deleted.
+        (WebCore::PODRedBlackTree::markFree): Deleted.
+        (WebCore::PODRedBlackTree::Counter): Deleted.
+        (WebCore::PODRedBlackTree::dumpFromNode const): Use TextStream.
+
+        * platform/graphics/FloatPolygon.cpp:
+        (WebCore::FloatPolygon::FloatPolygon): Tweaked coding style a bit.
+        (WebCore::FloatPolygon::overlappingEdges const): Changed to use a return
+        value instead of an out argument. Also tweaked coding style a bit.
+        (WebCore::FloatPolygonEdge::debugString const): Deleted.
+        (WebCore::ooperator>>): Implemented TextStream overload.
+
+        * platform/graphics/FloatPolygon.h: Updated for above, removed
+        ValueToString specialization.
+
+        * rendering/FloatingObjects.cpp:
+        (WebCore::FloatingObject::debugString const): Deleted.
+        (WebCore::operator<<): Implemented TextStream overload.
+        * rendering/FloatingObjects.h: Ditto. Also removed include of
+        PODIntervalTree.h and used a forward declaration instead.
+
+        * rendering/RenderBlock.cpp: Updated includes.
+
+        * rendering/RenderFragmentContainer.cpp:
+        (WebCore::RenderFragmentContainer::debugString const): Deleted.
+        (WebCore::operator<<): Implemented TextStream overload.
+        * rendering/RenderFragmentContainer.h: Ditto.
+
+        * rendering/RenderFragmentedFlow.cpp:
+        (WebCore::RenderFragmentedFlow::FragmentSearchAdapter::FragmentSearchAdapter):
+        Moved this class here from the header, moving the one function body that was
+        already here up in the file.
+        (WebCore::RenderFragmentedFlow::fragmentAtBlockOffset const): Refactored and
+        tweaked code sequence a bit, did not change logic.
+        (WebCore::RenderFragmentedFlow::updateFragmentsFragmentedFlowPortionRect):
+        Tweaked code style a bit.
+
+        * rendering/RenderFragmentedFlow.h: Moved FragmentSearchAdapter out of the
+        header, and tweaked coding style a bit. Removed ValueToString specialization.
+
+        * rendering/shapes/PolygonShape.cpp:
+        (WebCore::PolygonShape::getExcludedInterval const): Updated to use the
+        return value from the overlappingEdges function rather than an out argument.
+
+        * rendering/updating/RenderTreeBuilder.cpp: Updated includes.
+        * rendering/updating/RenderTreeBuilderFirstLetter.h: Updated forward declarations.
+        * rendering/updating/RenderTreeBuilderMultiColumn.cpp: Updated includes.
+
+        * rendering/updating/RenderTreePosition.h: Removed includes of
+        RenderFragmentedFlow.h, RenderText.h, and RenderView.h, since none are
+        needed by this header.
+
+        * rendering/updating/RenderTreeUpdater.cpp: Updated includes.
+
 2019-12-09  Zalan Bujtas  <zalan@apple.com>
 
         [LFC][IFC] Do not create PartialContent for a single character run when it does not fit.
index c9463b1..70d9e1b 100644 (file)
@@ -83,7 +83,7 @@
 #include "PointerCaptureController.h"
 #include "PointerEvent.h"
 #include "PointerLockController.h"
-#include "RenderFragmentContainer.h"
+#include "RenderFragmentedFlow.h"
 #include "RenderLayer.h"
 #include "RenderLayerBacking.h"
 #include "RenderLayerCompositor.h"
index 37dfcd7..c483e1c 100644 (file)
@@ -72,6 +72,7 @@
 #include "MediaQueryEvaluator.h"
 #include "MediaResourceLoader.h"
 #include "NetworkingContext.h"
+#include "PODIntervalTree.h"
 #include "Page.h"
 #include "PageGroup.h"
 #include "PictureInPictureSupport.h"
@@ -1627,6 +1628,12 @@ void HTMLMediaElement::loadResource(const URL& initialURL, ContentType& contentT
 
 #if ENABLE(VIDEO_TRACK)
 
+struct HTMLMediaElement::CueData {
+    WTF_MAKE_STRUCT_FAST_ALLOCATED;
+    PODIntervalTree<MediaTime, TextTrackCue*> cueTree;
+    CueList currentlyActiveCues;
+};
+
 static bool trackIndexCompare(TextTrack* a, TextTrack* b)
 {
     return a->trackIndex() - b->trackIndex() < 0;
@@ -1661,6 +1668,11 @@ static bool compareCueIntervalEndTime(const CueInterval& one, const CueInterval&
     return one.data()->endMediaTime() > two.data()->endMediaTime();
 }
 
+bool HTMLMediaElement::ignoreTrackDisplayUpdateRequests() const
+{
+    return m_ignoreTrackDisplayUpdate > 0 || !m_textTracks || !m_cueData || m_cueData->cueTree.isEmpty();
+}
+
 void HTMLMediaElement::updateActiveTextTrackCues(const MediaTime& movieTime)
 {
     // 4.8.10.8 Playing the media resource
@@ -1680,9 +1692,9 @@ void HTMLMediaElement::updateActiveTextTrackCues(const MediaTime& movieTime)
 
     // The user agent must synchronously unset [the text track cue active] flag
     // whenever ... the media element's readyState is changed back to HAVE_NOTHING.
-    auto movieTimeInterval = m_cueTree.createInterval(movieTime, movieTime);
+    auto movieTimeInterval = m_cueData->cueTree.createInterval(movieTime, movieTime);
     if (m_readyState != HAVE_NOTHING && m_player) {
-        currentCues = m_cueTree.allOverlaps(movieTimeInterval);
+        currentCues = m_cueData->cueTree.allOverlaps(movieTimeInterval);
         if (currentCues.size() > 1)
             std::sort(currentCues.begin(), currentCues.end(), &compareCueInterval);
     }
@@ -1693,7 +1705,7 @@ void HTMLMediaElement::updateActiveTextTrackCues(const MediaTime& movieTime)
     // 2 - Let other cues be a list of cues, initialized to contain all the cues
     // of hidden, showing, and showing by default text tracks of the media
     // element that are not present in current cues.
-    previousCues = m_currentlyActiveCues;
+    previousCues = m_cueData->currentlyActiveCues;
 
     // 3 - Let last time be the current playback position at the time this
     // algorithm was last run for this media element, if this is not the first
@@ -1707,7 +1719,7 @@ void HTMLMediaElement::updateActiveTextTrackCues(const MediaTime& movieTime)
     // end times are less than or equal to the current playback position.
     // Otherwise, let missed cues be an empty list.
     if (lastTime >= MediaTime::zeroTime() && m_lastSeekTime < movieTime) {
-        for (auto& cue : m_cueTree.allOverlaps(m_cueTree.createInterval(lastTime, movieTime))) {
+        for (auto& cue : m_cueData->cueTree.allOverlaps({ lastTime, movieTime })) {
             // Consider cues that may have been missed since the last seek time.
             if (cue.low() > std::max(m_lastSeekTime, lastTime) && cue.high() < movieTime)
                 missedCues.append(cue);
@@ -1752,7 +1764,7 @@ void HTMLMediaElement::updateActiveTextTrackCues(const MediaTime& movieTime)
     if (auto nearestEndingCue = std::min_element(currentCues.begin(), currentCues.end(), compareCueIntervalEndTime))
         nextInterestingTime = nearestEndingCue->data()->endMediaTime();
 
-    Optional<CueInterval> nextCue = m_cueTree.nextIntervalAfter(movieTimeInterval);
+    Optional<CueInterval> nextCue = m_cueData->cueTree.nextIntervalAfter(movieTimeInterval.high());
     if (nextCue)
         nextInterestingTime = std::min(nextInterestingTime, nextCue->low());
 
@@ -1897,7 +1909,7 @@ void HTMLMediaElement::updateActiveTextTrackCues(const MediaTime& movieTime)
             previousCues[i].data()->setIsActive(false);
 
     // Update the current active cues.
-    m_currentlyActiveCues = currentCues;
+    m_cueData->currentlyActiveCues = currentCues;
 
     if (activeSetChanged)
         updateTextTrackDisplay();
@@ -2034,24 +2046,30 @@ void HTMLMediaElement::textTrackAddCue(TextTrack& track, TextTrackCue& cue)
     if (track.mode() == TextTrack::Mode::Disabled)
         return;
 
+    if (!m_cueData)
+        m_cueData = makeUnique<CueData>();
+
     // Negative duration cues need be treated in the interval tree as
     // zero-length cues.
     MediaTime endTime = std::max(cue.startMediaTime(), cue.endMediaTime());
 
-    CueInterval interval = m_cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
-    if (!m_cueTree.contains(interval))
-        m_cueTree.add(interval);
+    CueInterval interval = m_cueData->cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
+    if (!m_cueData->cueTree.contains(interval))
+        m_cueData->cueTree.add(interval);
     updateActiveTextTrackCues(currentMediaTime());
 }
 
 void HTMLMediaElement::textTrackRemoveCue(TextTrack&, TextTrackCue& cue)
 {
+    if (!m_cueData)
+        m_cueData = makeUnique<CueData>();
+
     // Negative duration cues need to be treated in the interval tree as
     // zero-length cues.
     MediaTime endTime = std::max(cue.startMediaTime(), cue.endMediaTime());
 
-    CueInterval interval = m_cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
-    m_cueTree.remove(interval);
+    CueInterval interval = m_cueData->cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
+    m_cueData->cueTree.remove(interval);
 
     // Since the cue will be removed from the media element and likely the
     // TextTrack might also be destructed, notifying the region of the cue
@@ -2060,10 +2078,10 @@ void HTMLMediaElement::textTrackRemoveCue(TextTrack&, TextTrackCue& cue)
     if (isVTT)
         toVTTCue(&cue)->notifyRegionWhenRemovingDisplayTree(false);
 
-    size_t index = m_currentlyActiveCues.find(interval);
+    size_t index = m_cueData->currentlyActiveCues.find(interval);
     if (index != notFound) {
         cue.setIsActive(false);
-        m_currentlyActiveCues.remove(index);
+        m_cueData->currentlyActiveCues.remove(index);
     }
 
     cue.removeDisplayTree();
@@ -2073,6 +2091,13 @@ void HTMLMediaElement::textTrackRemoveCue(TextTrack&, TextTrackCue& cue)
         toVTTCue(&cue)->notifyRegionWhenRemovingDisplayTree(true);
 }
 
+CueList HTMLMediaElement::currentlyActiveCues() const
+{
+    if (!m_cueData)
+        return { };
+    return m_cueData->currentlyActiveCues;
+}
+
 #endif
 
 static inline bool isAllowedToLoadMediaURL(HTMLMediaElement& element, const URL& url, bool isInUserAgentShadowTree)
index 12d107f..c0bd6b2 100644 (file)
@@ -47,7 +47,7 @@
 #if ENABLE(VIDEO_TRACK)
 #include "AudioTrack.h"
 #include "CaptionUserPreferences.h"
-#include "PODIntervalTree.h"
+#include "PODInterval.h"
 #include "TextTrack.h"
 #include "TextTrackCue.h"
 #include "VTTCue.h"
@@ -112,8 +112,7 @@ class RemotePlayback;
 #endif
 
 #if ENABLE(VIDEO_TRACK)
-using CueIntervalTree = PODIntervalTree<MediaTime, TextTrackCue*>;
-using CueInterval = CueIntervalTree::IntervalType;
+using CueInterval = PODInterval<MediaTime, TextTrackCue*>;
 using CueList = Vector<CueInterval>;
 #endif
 
@@ -347,7 +346,7 @@ public:
     TextTrackList* textTracks() const { return m_textTracks.get(); }
     VideoTrackList* videoTracks() const { return m_videoTracks.get(); }
 
-    CueList currentlyActiveCues() const { return m_currentlyActiveCues; }
+    CueList currentlyActiveCues() const;
 
     void addAudioTrack(Ref<AudioTrack>&&);
     void addTextTrack(Ref<TextTrack>&&);
@@ -611,12 +610,6 @@ protected:
     
     bool isMediaElement() const final { return true; }
 
-#if ENABLE(VIDEO_TRACK)
-    bool ignoreTrackDisplayUpdateRequests() const { return m_ignoreTrackDisplayUpdate > 0 || !m_textTracks || !m_cueTree.size(); }
-    void beginIgnoringTrackDisplayUpdateRequests();
-    void endIgnoringTrackDisplayUpdateRequests();
-#endif
-
     RenderPtr<RenderElement> createElementRenderer(RenderStyle&&, const RenderTreePosition&) override;
 
 #if ENABLE(MEDIA_CONTROLS_SCRIPT)
@@ -803,13 +796,14 @@ private:
     URL selectNextSourceChild(ContentType*, String* keySystem, InvalidURLAction);
 
 #if ENABLE(VIDEO_TRACK)
+    bool ignoreTrackDisplayUpdateRequests() const;
+    void beginIgnoringTrackDisplayUpdateRequests();
+    void endIgnoringTrackDisplayUpdateRequests();
+
     void updateActiveTextTrackCues(const MediaTime&);
     HTMLTrackElement* showingTrackWithSameKind(HTMLTrackElement*) const;
 
-    enum ReconfigureMode {
-        Immediately,
-        AfterDelay,
-    };
+    enum ReconfigureMode { Immediately, AfterDelay };
     void markCaptionAndSubtitleTracksAsUnconfigured(ReconfigureMode);
     void captionPreferencesChanged() override;
     CaptionUserPreferences::CaptionDisplayMode captionDisplayMode();
@@ -874,11 +868,7 @@ private:
     bool isLiveStream() const override { return movieLoadType() == MediaPlayerEnums::LiveStream; }
 
     void updateSleepDisabling();
-    enum class SleepType {
-        None,
-        Display,
-        System,
-    };
+    enum class SleepType { None, Display, System };
     SleepType shouldDisableSleep() const;
 
 #if ENABLE(MEDIA_CONTROLS_SCRIPT)
@@ -1152,9 +1142,9 @@ private:
     RefPtr<VideoTrackList> m_videoTracks;
     Vector<RefPtr<TextTrack>> m_textTracksWhenResourceSelectionBegan;
 
-    CueIntervalTree m_cueTree;
+    struct CueData;
+    std::unique_ptr<CueData> m_cueData;
 
-    CueList m_currentlyActiveCues;
     int m_ignoreTrackDisplayUpdate { 0 };
 
     bool m_requireCaptionPreferencesChangedCallbacks { false };
@@ -1183,6 +1173,7 @@ private:
 #if ENABLE(LEGACY_ENCRYPTED_MEDIA)
     RefPtr<WebKitMediaKeys> m_webKitMediaKeys;
 #endif
+
 #if ENABLE(ENCRYPTED_MEDIA)
     RefPtr<MediaKeys> m_mediaKeys;
     bool m_attachingMediaKeys { false };
@@ -1234,23 +1225,6 @@ template<> struct LogArgument<WebCore::HTMLMediaElement::AutoplayEventPlaybackSt
     static String toString(WebCore::HTMLMediaElement::AutoplayEventPlaybackState reason) { return convertEnumerationToString(reason); }
 };
 
-#if ENABLE(VIDEO_TRACK) && !defined(NDEBUG)
-
-// Template specialization required by PodIntervalTree in debug mode.
-template<> struct ValueToString<WebCore::TextTrackCue*> {
-    static String string(const WebCore::TextTrackCue* cue) { return cue->debugString(); }
-};
-
-#endif
-
-#ifndef NDEBUG
-
-template<> struct ValueToString<MediaTime> {
-    static String string(const MediaTime& time) { return toString(time); }
-};
-
-#endif
-
 } // namespace WTF
 
 SPECIALIZE_TYPE_TRAITS_BEGIN(WebCore::HTMLMediaElement)
index fac06bd..c6ffc3f 100644 (file)
@@ -423,14 +423,18 @@ String TextTrackCue::toJSONString() const
     return object->toJSONString();
 }
 
-String TextTrackCue::debugString() const
+#ifndef NDEBUG
+
+TextStream& operator<<(TextStream& stream, const TextTrackCue& cue)
 {
     String text;
-    if (is<VTTCue>(this))
-        text = toVTTCue(this)->text();
-    return makeString("0x", hex(reinterpret_cast<uintptr_t>(this)), " id=", id(), " interval=", startTime(), "-->", endTime(), " cue=", text, ')');
+    if (is<VTTCue>(cue))
+        text = toVTTCue(&cue)->text();
+    return stream << &cue << " id=" << cue.id() << " interval=" << cue.startTime() << "-->" << cue.endTime() << " cue=" << text << ')';
 }
 
+#endif
+
 RefPtr<DocumentFragment> TextTrackCue::getCueAsHTML()
 {
     if (!m_cueNode)
index ebb4597..c7bd75e 100644 (file)
@@ -119,7 +119,6 @@ public:
     virtual RefPtr<DocumentFragment> getCueAsHTML();
 
     String toJSONString() const;
-    String debugString() const;
 
     using RefCounted::ref;
     using RefCounted::deref;
@@ -170,6 +169,10 @@ private:
     bool m_displayTreeNeedsUpdate { true };
 };
 
+#ifndef NDEBUG
+TextStream& operator<<(TextStream&, const TextTrackCue&);
+#endif
+
 } // namespace WebCore
 
 namespace WTF {
index 4515142..e3ce992 100644 (file)
@@ -252,19 +252,18 @@ const VTTCue* toVTTCue(const TextTrackCue*);
 
 namespace WTF {
 
-template<typename Type>
-struct LogArgument;
+template<typename> struct LogArgument;
 
-template <>
-struct LogArgument<WebCore::VTTCue> {
-    static String toString(const WebCore::VTTCue& cue)
-    {
-        return cue.toJSONString();
-    }
+template<> struct LogArgument<WebCore::VTTCue> {
+    static String toString(const WebCore::VTTCue& cue) { return cue.toJSONString(); }
 };
 
 } // namespace WTF
 
+// FIXME: The following isType function is incorrect, since it returns true for TextTrackCueGeneric.
+// Should fix this so that is<VTTCue> and downcast<VTTCue> will work correctly and eliminate toVTTCue
+// since it's just another name for downcast<VTTCue>.
+
 SPECIALIZE_TYPE_TRAITS_BEGIN(WebCore::VTTCue)
 static bool isType(const WebCore::TextTrackCue& cue) { return cue.cueType() == WebCore::TextTrackCue::WebVTT; }
 SPECIALIZE_TYPE_TRAITS_END()
index 46a9634..156a01b 100644 (file)
@@ -36,7 +36,6 @@
 #include <stdlib.h>
 #include <wtf/MathExtras.h>
 #include <wtf/SaturatedArithmetic.h>
-#include <wtf/text/ValueToString.h>
 
 namespace WTF {
 class TextStream;
@@ -839,16 +838,3 @@ inline LayoutUnit operator"" _lu(unsigned long long value)
 }
 
 } // namespace WebCore
-
-#ifndef NDEBUG
-
-namespace WTF {
-
-// This structure is used by PODIntervalTree for debugging.
-template<> struct ValueToString<WebCore::LayoutUnit> {
-    static String string(WebCore::LayoutUnit value) { return String::numberToStringFixedPrecision(value.toFloat()); }
-};
-
-} // namespace WTF
-
-#endif
index 048da98..96e047b 100644 (file)
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#ifndef PODInterval_h
-#define PODInterval_h
+#pragma once
 
 #ifndef NDEBUG
-#include <wtf/text/StringBuilder.h>
-#include <wtf/text/ValueToString.h>
+#include <wtf/text/TextStream.h>
 #endif
 
 namespace WebCore {
 
-// Class representing a closed interval which can hold an arbitrary
-// Plain Old Datatype (POD) as its endpoints and a piece of user
+// Class representing a closed interval which can hold arbitrary
+// endpoints and a piece of user
 // data. An important characteristic for the algorithms we use is that
 // if two intervals have identical endpoints but different user data,
 // they are not considered to be equal. This situation can arise when
@@ -49,44 +47,33 @@ namespace WebCore {
 // The following constructors and operators must be implemented on
 // type T:
 //
-//   - Copy constructor (if user data is desired)
+//   - Copy constructor
 //   - operator<
 //   - operator==
 //   - operator=
 //
-// If the UserData type is specified, it must support a copy
-// constructor and assignment operator.
+// The UserData type must support a copy constructor and assignment
+// operator.
 //
 // In debug mode, printing of intervals and the data they contain is
-// enabled. This requires the following template specializations to be
-// available:
-//
-//   template<> struct WebCore::ValueToString<T> {
-//       static String string(const T& t);
-//   };
-//   template<> struct WebCore::ValueToString<UserData> {
-//       static String string(const UserData& t);
-//   };
+// enabled. This uses WTF::TextStream.
 //
 // Note that this class requires a copy constructor and assignment
 // operator in order to be stored in the red-black tree.
 
-template<class T, class UserData = void*>
+// FIXME: The prefix "POD" here isn't correct; this works with non-POD types.
+
+template<class T, class UserData>
 class PODInterval {
 public:
-    // Constructor from endpoints. This constructor only works when the
-    // UserData type is a pointer or other type which can be initialized
-    // with 0.
     PODInterval(const T& low, const T& high)
         : m_low(low)
         , m_high(high)
-        , m_data(0)
         , m_maxHigh(high)
     {
     }
 
-    // Constructor from two endpoints plus explicit user data.
-    PODInterval(const T& low, const T& high, const UserData data)
+    PODInterval(const T& low, const T& high, const UserData& data)
         : m_low(low)
         , m_high(high)
         , m_data(data)
@@ -94,6 +81,14 @@ public:
     {
     }
 
+    PODInterval(const T& low, const T& high, UserData&& data)
+        : m_low(low)
+        , m_high(high)
+        , m_data(WTFMove(data))
+        , m_maxHigh(high)
+    {
+    }
+
     const T& low() const { return m_low; }
     const T& high() const { return m_high; }
     const UserData& data() const { return m_data; }
@@ -131,31 +126,21 @@ public:
     const T& maxHigh() const { return m_maxHigh; }
     void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
 
-#ifndef NDEBUG
-    // Support for printing PODIntervals.
-    String toString() const
-    {
-        StringBuilder builder;
-        builder.appendLiteral("[PODInterval (");
-        builder.append(ValueToString<T>::string(low()));
-        builder.appendLiteral(", ");
-        builder.append(ValueToString<T>::string(high()));
-        builder.appendLiteral("), data=");
-        builder.append(ValueToString<UserData>::string(data()));
-        builder.appendLiteral(", maxHigh=");
-        builder.append(ValueToString<T>::string(maxHigh()));
-        builder.append(']');
-        return builder.toString();
-    }
-#endif
-
 private:
     T m_low;
     T m_high;
-    UserData m_data;
+    UserData m_data { };
     T m_maxHigh;
 };
 
-} // namespace WebCore
+#ifndef NDEBUG
 
-#endif // PODInterval_h
+template<class T, class UserData>
+TextStream& operator<<(TextStream& stream, const PODInterval<T, UserData>& interval)
+{
+    return stream << "[PODInterval (" << interval.low() << ", " << interval.high() << "), data=" << *interval.data() << ", maxHigh=" << interval.maxHigh() << ']';
+}
+
+#endif
+
+} // namespace WebCore
index 7a0c8b9..be4b88f 100644 (file)
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2010 Google Inc. All rights reserved.
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#ifndef PODIntervalTree_h
-#define PODIntervalTree_h
+#pragma once
 
 #include "PODInterval.h"
 #include "PODRedBlackTree.h"
-#include <wtf/Assertions.h>
-#include <wtf/Noncopyable.h>
 #include <wtf/Optional.h>
 #include <wtf/Vector.h>
-#include <wtf/text/ValueToString.h>
+
+// FIXME: The prefix "POD" here isn't correct; this tree works with non-POD types.
 
 namespace WebCore {
 
-template <class T, class UserData = void*>
+template <class T, class UserData>
 class PODIntervalSearchAdapter {
 public:
     typedef PODInterval<T, UserData> IntervalType;
@@ -62,46 +61,31 @@ private:
     T m_highValue;
 };
 
+struct PODIntervalNodeUpdater;
+
 // An interval tree, which is a form of augmented red-black tree. It
 // supports efficient (O(lg n)) insertion, removal and querying of
 // intervals in the tree.
-template<class T, class UserData = void*>
-class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData>> {
+template<class T, class UserData>
+class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true> {
     WTF_MAKE_FAST_ALLOCATED;
-    WTF_MAKE_NONCOPYABLE(PODIntervalTree);
 public:
     // Typedef to reduce typing when declaring intervals to be stored in
     // this tree.
     typedef PODInterval<T, UserData> IntervalType;
     typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
 
-    PODIntervalTree()
-        : PODRedBlackTree<IntervalType>()
-    {
-        init();
-    }
-
     // Returns all intervals in the tree which overlap the given query
     // interval. The returned intervals are sorted by increasing low
     // endpoint.
     Vector<IntervalType> allOverlaps(const IntervalType& interval) const
     {
         Vector<IntervalType> result;
-        allOverlaps(interval, result);
+        IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
+        allOverlapsWithAdapter<IntervalSearchAdapterType>(adapter);
         return result;
     }
 
-    // Returns all intervals in the tree which overlap the given query
-    // interval. The returned intervals are sorted by increasing low
-    // endpoint.
-    void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const
-    {
-        // Explicit dereference of "this" required because of
-        // inheritance rules in template classes.
-        IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
-        searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter);
-    }
-    
     template <class AdapterType>
     void allOverlapsWithAdapter(AdapterType& adapter) const
     {
@@ -111,39 +95,35 @@ public:
     }
 
     // Helper to create interval objects.
-    static IntervalType createInterval(const T& low, const T& high, const UserData data = 0)
+    static IntervalType createInterval(const T& low, const T& high, UserData&& data = { })
     {
-        return IntervalType(low, high, data);
+        return IntervalType(low, high, WTFMove(data));
     }
 
-    Optional<IntervalType> nextIntervalAfter(const IntervalType& interval)
+    Optional<IntervalType> nextIntervalAfter(const T& point)
     {
-        auto next = smallestNodeGreaterThanFrom(interval, this->root());
+        auto next = smallestNodeGreaterThanFrom(point, this->root());
         if (!next)
             return WTF::nullopt;
-
         return next->data();
     }
 
-    bool checkInvariants() const override
+#ifndef NDEBUG
+
+    bool checkInvariants() const
     {
-        if (!PODRedBlackTree<IntervalType>::checkInvariants())
+        if (!Base::checkInvariants())
             return false;
         if (!this->root())
             return true;
         return checkInvariantsFromNode(this->root(), 0);
     }
 
-private:
-    typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode;
+#endif
 
-    // Initializes the tree.
-    void init()
-    {
-        // Explicit dereference of "this" required because of
-        // inheritance rules in template classes.
-        this->setNeedsFullOrderingComparisons(true);
-    }
+private:
+    using Base = PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true>;
+    typedef typename Base::Node IntervalNode;
 
     // Starting from the given node, adds all overlaps with the given
     // interval to the result vector. The intervals are sorted by
@@ -175,43 +155,22 @@ private:
             searchForOverlapsFrom<AdapterType>(node->right(), adapter);
     }
 
-    IntervalNode* smallestNodeGreaterThanFrom(const IntervalType& interval, IntervalNode* node) const
+    IntervalNode* smallestNodeGreaterThanFrom(const T& point, IntervalNode* node) const
     {
         if (!node)
             return nullptr;
 
-        if (!(interval.high() < node->data().low()))
-            return smallestNodeGreaterThanFrom(interval, node->right());
+        if (!(point < node->data().low()))
+            return smallestNodeGreaterThanFrom(point, node->right());
 
-        if (auto left = smallestNodeGreaterThanFrom(interval, node->right()))
+        if (auto left = smallestNodeGreaterThanFrom(point, node->right()))
             return left;
 
         return node;
-}
-
-    bool updateNode(IntervalNode* node) override
-    {
-        // Would use const T&, but need to reassign this reference in this
-        // function.
-        const T* curMax = &node->data().high();
-        IntervalNode* left = node->left();
-        if (left) {
-            if (*curMax < left->data().maxHigh())
-                curMax = &left->data().maxHigh();
-        }
-        IntervalNode* right = node->right();
-        if (right) {
-            if (*curMax < right->data().maxHigh())
-                curMax = &right->data().maxHigh();
-        }
-        // This is phrased like this to avoid needing operator!= on type T.
-        if (!(*curMax == node->data().maxHigh())) {
-            node->data().setMaxHigh(*curMax);
-            return true;
-        }
-        return false;
     }
 
+#ifndef NDEBUG
+
     bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const
     {
         // These assignments are only done in order to avoid requiring
@@ -245,34 +204,42 @@ private:
         if (localMaxValue < node->data().high())
             localMaxValue = node->data().high();
         if (!(localMaxValue == node->data().maxHigh())) {
-#ifndef NDEBUG
-            String localMaxValueString = ValueToString<T>::string(localMaxValue);
-            LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s",
-                      node, localMaxValueString.utf8().data(), node->data().toString().utf8().data());
-#endif
+            TextStream stream;
+            stream << "localMaxValue=" << localMaxValue << "and data =" << node->data();
+            LOG_ERROR("PODIntervalTree verification failed at node 0x%p: %s",
+                node, stream.release().utf8().data());
             return false;
         }
         if (currentMaxValue)
             *currentMaxValue = localMaxValue;
         return true;
     }
-};
 
-} // namespace WebCore
+#endif
 
-#ifndef NDEBUG
-namespace WTF {
+};
 
-// Support for printing PODIntervals at the PODRedBlackTree level.
-template<class T, class UserData>
-struct ValueToString<WebCore::PODInterval<T, UserData>> {
-    static String string(const WebCore::PODInterval<T, UserData>& interval)
+struct PODIntervalNodeUpdater {
+    template<typename Node> static bool update(Node& node)
     {
-        return interval.toString();
+        auto* curMax = &node.data().high();
+        auto* left = node.left();
+        if (left) {
+            if (*curMax < left->data().maxHigh())
+                curMax = &left->data().maxHigh();
+        }
+        auto* right = node.right();
+        if (right) {
+            if (*curMax < right->data().maxHigh())
+                curMax = &right->data().maxHigh();
+        }
+        // This is phrased like this to avoid needing operator!= on type T.
+        if (!(*curMax == node.data().maxHigh())) {
+            node.data().setMaxHigh(*curMax);
+            return true;
+        }
+        return false;
     }
 };
 
-} // namespace WTF
-#endif
-
-#endif // PODIntervalTree_h
+} // namespace WebCore
index 131f31a..d48f498 100644 (file)
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2010 Google Inc. All rights reserved.
+ * Copyright (C) 2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 //   Deletion:  O(lg(n))
 //   Querying:  O(lg(n))
 //
-// The data type T that is stored in this red-black tree must be only
-// Plain Old Data (POD), or bottom out into POD. It must _not_ rely on
-// having its destructor called. This implementation internally
-// allocates storage in large chunks and does not call the destructor
-// on each object.
-//
 // Type T must supply a default constructor, a copy constructor, and
 // the "<" and "==" operators.
 //
 // In debug mode, printing of the data contained in the tree is
-// enabled. This requires the template specialization to be available:
-//
-//   template<> struct WebCore::ValueToString<T> {
-//       static String string(const T& t);
-//   };
+// enabled. This makes use of WTF::TextStream.
 //
 // Note that when complex types are stored in this red/black tree, it
 // is possible that single invocations of the "<" and "==" operators
@@ -57,8 +48,7 @@
 // the "==" operator takes into account the high endpoint as well.
 // This makes the necessary logic for querying and deletion somewhat
 // more complex. In order to properly handle such situations, the
-// property "needsFullOrderingComparisons" must be set to true on
-// the tree.
+// template argument "needsFullOrderingComparisons" must be true.
 //
 // This red-black tree is designed to be _augmented_; subclasses can
 // add additional and summary information to each node to efficiently
 // The design of this red-black tree comes from Cormen, Leiserson,
 // and Rivest, _Introduction to Algorithms_, MIT Press, 1990.
 
-#ifndef PODRedBlackTree_h
-#define PODRedBlackTree_h
+#pragma once
 
 #include <wtf/Assertions.h>
 #include <wtf/Noncopyable.h>
-#include <wtf/text/ValueToString.h>
+
 #ifndef NDEBUG
 #include <wtf/text/StringBuilder.h>
-#include <wtf/text/WTFString.h>
+#include <wtf/text/TextStream.h>
 #endif
 
+// FIXME: The prefix "POD" here isn't correct; this tree works with non-POD types too.
+// FIXME: Remove the unusual needsFullOrderingComparisons feature by changing the interval tree to use full ordering, sorting based on low, high, and data.
+// FIXME: Would be worthwhile to implement this on top of WTF::RedBlackTree rather than keeping two separate class templates around.
+
 namespace WebCore {
 
-template<class T>
+template<typename T, typename NodeUpdaterType, bool needsFullOrderingComparisons>
 class PODRedBlackTree {
-    WTF_MAKE_FAST_ALLOCATED;
+    WTF_MAKE_NONCOPYABLE(PODRedBlackTree);
 public:
-    class Node;
-
-    // Visitor interface for walking all of the tree's elements.
-    class Visitor {
-    public:
-        virtual void visit(const T& data) = 0;
-    protected:
-        virtual ~Visitor() = default;
-    };
-
-    PODRedBlackTree()
-        : m_root(0)
-        , m_needsFullOrderingComparisons(false)
-#ifndef NDEBUG
-        , m_verboseDebugging(false)
-#endif
-    {
-    }
+    PODRedBlackTree() = default;
 
-    virtual ~PODRedBlackTree()
+    ~PODRedBlackTree()
     {
         clear();
     }
 
-    // Clearing will delete the contents of the tree. After this call
-    // isInitialized will return false.
+    // Clearing will delete the contents of the tree.
     void clear()
     {
-        markFree(m_root);
-        m_root = 0;
+        if (!m_root)
+            return;
+        Node* next;
+        for (Node* node = treeMinimum(m_root); node; node = next) {
+            next = treeSuccessorInPostOrder(node);
+            delete node;
+        }
+        m_root = nullptr;
     }
-    
+
     void add(const T& data)
     {
-        Node* node = new Node(data);
-        insertNode(node);
+        insertNode(new Node(T { data }));
+    }
+
+    void add(T&& data)
+    {
+        insertNode(new Node(WTFMove(data)));
     }
 
     // Returns true if the datum was found in the tree.
@@ -140,33 +125,19 @@ public:
         return treeSearch(data);
     }
 
-    void visitInorder(Visitor* visitor) const
-    {
-        if (!m_root)
-            return;
-        visitInorderImpl(m_root, visitor);
-    }
-
-    int size() const
+    bool isEmpty() const
     {
-        Counter counter;
-        visitInorder(&counter);
-        return counter.count();
+        return !m_root;
     }
 
-    // See the class documentation for an explanation of this property.
-    void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)
-    {
-        m_needsFullOrderingComparisons = needsFullOrderingComparisons;
-    }
+#ifndef NDEBUG
 
-    virtual bool checkInvariants() const
+    bool checkInvariants() const
     {
         int blackCount;
         return checkInvariantsFromNode(m_root, &blackCount);
     }
 
-#ifndef NDEBUG
     // Dumps the tree's contents to the logging info stream for
     // debugging purposes.
     void dump() const
@@ -181,12 +152,11 @@ public:
     {
         m_verboseDebugging = verboseDebugging;
     }
+
 #endif
 
-    enum Color {
-        Red = 1,
-        Black
-    };
+protected:
+    enum Color { Red, Black };
 
     // The base Node class which is stored in the tree. Nodes are only
     // an internal concept; users of the tree deal only with the data
@@ -196,30 +166,17 @@ public:
         WTF_MAKE_NONCOPYABLE(Node);
     public:
         // Constructor. Newly-created nodes are colored red.
-        explicit Node(const T& data)
-            : m_left(0)
-            , m_right(0)
-            , m_parent(0)
-            , m_color(Red)
-            , m_data(data)
+        explicit Node(T&& data)
+            : m_data(WTFMove(data))
         {
         }
 
-        virtual ~Node() = default;
-
         Color color() const { return m_color; }
         void setColor(Color color) { m_color = color; }
 
-        // Fetches the user data.
         T& data() { return m_data; }
 
-        // Copies all user-level fields from the source node, but not
-        // internal fields. For example, the base implementation of this
-        // method copies the "m_data" field, but not the child or parent
-        // fields. Any augmentation information also does not need to be
-        // copied, as it will be recomputed. Subclasses must call the
-        // superclass implementation.
-        virtual void copyFrom(Node* src) { m_data = src->data(); }
+        void moveDataFrom(Node* src) { m_data = WTFMove(src->m_data); }
 
         Node* left() const { return m_left; }
         void setLeft(Node* node) { m_left = node; }
@@ -231,19 +188,18 @@ public:
         void setParent(Node* node) { m_parent = node; }
 
     private:
-        Node* m_left;
-        Node* m_right;
-        Node* m_parent;
-        Color m_color;
+        Node* m_left { nullptr };
+        Node* m_right { nullptr };
+        Node* m_parent { nullptr };
+        Color m_color { Red };
         T m_data;
     };
 
-protected:
     // Returns the root of the tree, which is needed by some subclasses.
     Node* root() const { return m_root; }
 
 private:
-    // This virtual method is the hook that subclasses should use when
+    // This is the hook that subclasses should use when
     // augmenting the red-black tree with additional per-node summary
     // information. For example, in the case of an interval tree, this
     // is used to compute the maximum endpoint of the subtree below the
@@ -252,7 +208,10 @@ private:
     // properly update such summary information based only on the values
     // in the left and right children. This method should return true if
     // the node's summary information changed.
-    virtual bool updateNode(Node*) { return false; }
+    bool updateNode(Node* node)
+    {
+        return NodeUpdaterType::update(*node);
+    }
 
     //----------------------------------------------------------------------
     // Generic binary search tree operations
@@ -261,7 +220,7 @@ private:
     // Searches the tree for the given datum.
     Node* treeSearch(const T& data) const
     {
-        if (m_needsFullOrderingComparisons)
+        if (needsFullOrderingComparisons)
             return treeSearchFullComparisons(m_root, data);
 
         return treeSearchNormal(m_root, data);
@@ -326,7 +285,7 @@ private:
 
     // Finds the node following the given one in sequential ordering of
     // their data, or null if none exists.
-    Node* treeSuccessor(Node* x)
+    static Node* treeSuccessor(Node* x)
     {
         if (x->right())
             return treeMinimum(x->right());
@@ -340,13 +299,21 @@ private:
 
     // Finds the minimum element in the sub-tree rooted at the given
     // node.
-    Node* treeMinimum(Node* x)
+    static Node* treeMinimum(Node* x)
     {
         while (x->left())
             x = x->left();
         return x;
     }
 
+    static Node* treeSuccessorInPostOrder(Node* x)
+    {
+        Node* y = x->parent();
+        if (y && x == y->left() && y->right())
+            return treeMinimum(y->right());
+        return y;
+    }
+
     // Helper for maintaining the augmented red-black tree.
     void propagateUpdates(Node* start)
     {
@@ -627,7 +594,7 @@ private:
                 y->parent()->setRight(x);
         }
         if (y != z) {
-            z->copyFrom(y);
+            z->moveDataFrom(y);
             // This node has changed location in the tree and must be updated.
             updateNode(z);
             // The parent and its parents may now be out of date.
@@ -643,49 +610,12 @@ private:
         delete y;
     }
 
-    // Visits the subtree rooted at the given node in order.
-    void visitInorderImpl(Node* node, Visitor* visitor) const
-    {
-        if (node->left())
-            visitInorderImpl(node->left(), visitor);
-        visitor->visit(node->data());
-        if (node->right())
-            visitInorderImpl(node->right(), visitor);
-    }
-
-    void markFree(Node *node)
-    {
-        if (!node)
-            return;
-
-        if (node->left())
-            markFree(node->left());
-        if (node->right())
-            markFree(node->right());
-        delete node;
-    }
-
-    //----------------------------------------------------------------------
-    // Helper class for size()
-
-    // A Visitor which simply counts the number of visited elements.
-    class Counter : public Visitor {
-        WTF_MAKE_NONCOPYABLE(Counter);
-    public:
-        Counter()
-            : m_count(0) { }
-
-        void visit(const T&) override { ++m_count; }
-        int count() const { return m_count; }
-
-    private:
-        int m_count;
-    };
-
     //----------------------------------------------------------------------
     // Verification and debugging routines
     //
 
+#ifndef NDEBUG
+
     // Returns in the "blackCount" parameter the number of black
     // children along all paths to all leaves of the given node.
     bool checkInvariantsFromNode(Node* node, int* blackCount) const
@@ -721,6 +651,8 @@ private:
         return leftCount == rightCount;
     }
 
+#endif
+
 #ifdef NDEBUG
     void logIfVerbose(const char*) const { }
 #else
@@ -732,6 +664,7 @@ private:
 #endif
 
 #ifndef NDEBUG
+
     // Dumps the subtree rooted at the given node.
     void dumpFromNode(Node* node, int indentation) const
     {
@@ -741,27 +674,27 @@ private:
         builder.append('-');
         if (node) {
             builder.append(' ');
-            builder.append(ValueToString<T>::string(node->data()));
+            TextStream stream;
+            stream << node->data();
+            builder.append(stream.release());
             builder.append((node->color() == Black) ? " (black)" : " (red)");
         }
-        LOG_ERROR("%s", builder.toString().ascii().data());
+        LOG_ERROR("%s", builder.toString().utf8().data());
         if (node) {
             dumpFromNode(node->left(), indentation + 2);
             dumpFromNode(node->right(), indentation + 2);
         }
     }
+
 #endif
 
     //----------------------------------------------------------------------
     // Data members
 
-    Node* m_root;
-    bool m_needsFullOrderingComparisons;
+    Node* m_root { nullptr };
 #ifndef NDEBUG
-    bool m_verboseDebugging;
+    bool m_verboseDebugging { false };
 #endif
 };
 
 } // namespace WebCore
-
-#endif // PODRedBlackTree_h
index 0f2423c..c1d3294 100644 (file)
@@ -135,24 +135,18 @@ FloatPolygon::FloatPolygon(std::unique_ptr<Vector<FloatPoint>> vertices, WindRul
     if (m_empty)
         return;
 
-    for (unsigned i = 0; i < m_edges.size(); ++i) {
-        FloatPolygonEdge* edge = &m_edges[i];
-        m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
-    }
+    for (auto& edge : m_edges)
+        m_edgeTree.add({ edge.minY(), edge.maxY(), &edge });
 }
 
-bool FloatPolygon::overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const
+Vector<std::reference_wrapper<const FloatPolygonEdge>> FloatPolygon::overlappingEdges(float minY, float maxY) const
 {
-    Vector<FloatPolygon::EdgeInterval> overlappingEdgeIntervals;
-    m_edgeTree.allOverlaps(FloatPolygon::EdgeInterval(minY, maxY, 0), overlappingEdgeIntervals);
-    unsigned overlappingEdgeIntervalsSize = overlappingEdgeIntervals.size();
-    result.resize(overlappingEdgeIntervalsSize);
-    for (unsigned i = 0; i < overlappingEdgeIntervalsSize; ++i) {
-        const FloatPolygonEdge* edge = static_cast<const FloatPolygonEdge*>(overlappingEdgeIntervals[i].data());
-        ASSERT(edge);
-        result[i] = edge;
-    }
-    return overlappingEdgeIntervalsSize > 0;
+    auto overlappingEdgeIntervals = m_edgeTree.allOverlaps({ minY, maxY });
+    Vector<std::reference_wrapper<const FloatPolygonEdge>> result;
+    result.reserveInitialCapacity(overlappingEdgeIntervals.size());
+    for (auto& interval : overlappingEdgeIntervals)
+        result.uncheckedAppend(*interval.data());
+    return result;
 }
 
 static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
@@ -257,9 +251,9 @@ bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
 
 #ifndef NDEBUG
 
-String FloatPolygonEdge::debugString() const
+TextStream& operator<<(TextStream& stream, const FloatPolygonEdge& edge)
 {
-    return makeString("0x", hex(reinterpret_cast<uintptr_t>(this)), " (", vertex1().x(), ',', vertex1().y(), ' ', vertex2().x(), ',', vertex2().y(), ')');
+    return stream << &edge << " (" << edge.vertex1().x() << ',' << edge.vertex1().y() << ' ' << edge.vertex2().x() << ',' << edge.vertex2().y() << ')';
 }
 
 #endif
index 9461fe1..f64dd60 100644 (file)
@@ -53,12 +53,11 @@ public:
     unsigned numberOfEdges() const { return m_edges.size(); }
 
     FloatRect boundingBox() const { return m_boundingBox; }
-    bool overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const;
+    Vector<std::reference_wrapper<const FloatPolygonEdge>> overlappingEdges(float minY, float maxY) const;
     bool contains(const FloatPoint&) const;
     bool isEmpty() const { return m_empty; }
 
 private:
-    typedef PODInterval<float, FloatPolygonEdge*> EdgeInterval;
     typedef PODIntervalTree<float, FloatPolygonEdge*> EdgeIntervalTree;
 
     bool containsNonZero(const FloatPoint&) const;
@@ -121,8 +120,6 @@ public:
     unsigned vertexIndex2() const { return m_vertexIndex2; }
     unsigned edgeIndex() const { return m_edgeIndex; }
 
-    String debugString() const;
-
 private:
     // Edge vertex index1 is less than index2, except the last edge, where index2 is 0. When a polygon edge
     // is defined by 3 or more colinear vertices, index2 can be the index of the last colinear vertex.
@@ -132,17 +129,8 @@ private:
     const FloatPolygon* m_polygon;
 };
 
-} // namespace WebCore
-
 #ifndef NDEBUG
-
-namespace WTF {
-
-// This structure is used by PODIntervalTree for debugging.
-template<> struct ValueToString<WebCore::FloatPolygonEdge*> {
-    static String string(const WebCore::FloatPolygonEdge* edge) { return edge->debugString(); }
-};
-
-}
-
+TextStream& operator<<(TextStream&, const FloatPolygonEdge&);
 #endif
+
+} // namespace WebCore
index a6c6481..696d471 100644 (file)
@@ -24,6 +24,7 @@
 #include "config.h"
 #include "FloatingObjects.h"
 
+#include "PODIntervalTree.h"
 #include "RenderBlockFlow.h"
 #include "RenderBox.h"
 #include "RenderView.h"
@@ -101,9 +102,9 @@ LayoutSize FloatingObject::translationOffsetToAncestor() const
 
 #ifndef NDEBUG
 
-String FloatingObject::debugString() const
+TextStream& operator<<(TextStream& stream, const FloatingObject& object)
 {
-    return makeString("0x", hex(reinterpret_cast<uintptr_t>(this)), " (", frameRect().x().toInt(), 'x', frameRect().y().toInt(), ' ', frameRect().maxX().toInt(), 'x', frameRect().maxY().toInt(), ')');
+    return stream << &object << " (" << object.frameRect().x().toInt() << 'x' << object.frameRect().y().toInt() << ' ' << object.frameRect().maxX().toInt() << 'x' << object.frameRect().maxY().toInt() << ')';
 }
 
 #endif
index 250b33d..cfb2273 100644 (file)
@@ -23,7 +23,7 @@
 
 #pragma once
 
-#include "PODIntervalTree.h"
+#include "PODInterval.h"
 #include "RootInlineBox.h"
 #include <wtf/ListHashSet.h>
 #include <wtf/WeakPtr.h>
@@ -33,6 +33,8 @@ namespace WebCore {
 class RenderBlockFlow;
 class RenderBox;
 
+template<typename, typename> class PODIntervalTree;
+
 class FloatingObject {
     WTF_MAKE_NONCOPYABLE(FloatingObject); WTF_MAKE_FAST_ALLOCATED;
 public:
@@ -95,8 +97,6 @@ public:
     LayoutSize marginOffset() const { ASSERT(isPlaced()); return m_marginOffset; }
     LayoutSize translationOffsetToAncestor() const;
 
-    String debugString() const;
-
 private:
     WeakPtr<RenderBox> m_renderer;
     WeakPtr<RootInlineBox> m_originatingLine;
@@ -187,17 +187,8 @@ private:
     WeakPtr<const RenderBlockFlow> m_renderer;
 };
 
-} // namespace WebCore
-
 #ifndef NDEBUG
-
-namespace WTF {
-
-// This helper is used by PODIntervalTree for debugging purposes.
-template<> struct ValueToString<WebCore::FloatingObject*> {
-    static String string(const WebCore::FloatingObject* floatingObject) { return floatingObject->debugString(); }
-};
-
-} // namespace WTF
-
+TextStream& operator<<(TextStream&, const FloatingObject&);
 #endif
+
+} // namespace WebCore
index f8a9d83..a98f70e 100644 (file)
@@ -52,7 +52,7 @@
 #include "RenderCombineText.h"
 #include "RenderDeprecatedFlexibleBox.h"
 #include "RenderFlexibleBox.h"
-#include "RenderFragmentContainer.h"
+#include "RenderFragmentedFlow.h"
 #include "RenderInline.h"
 #include "RenderIterator.h"
 #include "RenderLayer.h"
index 7f6cabc..a1067c0 100644 (file)
@@ -563,9 +563,9 @@ CurrentRenderFragmentContainerMaintainer::~CurrentRenderFragmentContainerMaintai
 
 #ifndef NDEBUG
 
-String RenderFragmentContainer::debugString() const
+TextStream& operator<<(TextStream& stream, const RenderFragmentContainer& container)
 {
-    return makeString("0x", hex(reinterpret_cast<uintptr_t>(this), Lowercase));
+    return stream << &container;
 }
 
 #endif
index 8d98969..a27bbbe 100644 (file)
@@ -121,8 +121,6 @@ public:
 
     virtual void absoluteQuadsForBoxInFragment(Vector<FloatQuad>&, bool*, const RenderBox*, float, float) { }
 
-    String debugString() const;
-
 protected:
     RenderFragmentContainer(Element&, RenderStyle&&, RenderFragmentedFlow*);
     RenderFragmentContainer(Document&, RenderStyle&&, RenderFragmentedFlow*);
@@ -180,6 +178,10 @@ private:
     RenderFragmentContainer& m_fragment;
 };
 
+#ifndef NDEBUG
+TextStream& operator<<(TextStream&, const RenderFragmentContainer&);
+#endif
+
 } // namespace WebCore
 
 SPECIALIZE_TYPE_TRAITS_RENDER_OBJECT(RenderFragmentContainer, isRenderFragmentContainer())
index 846dd3a..2da61c0 100644 (file)
@@ -34,7 +34,6 @@
 #include "HitTestResult.h"
 #include "InlineElementBox.h"
 #include "Node.h"
-#include "PODIntervalTree.h"
 #include "RenderBoxFragmentInfo.h"
 #include "RenderFragmentContainer.h"
 #include "RenderInline.h"
@@ -219,6 +218,31 @@ void RenderFragmentedFlow::repaintRectangleInFragments(const LayoutRect& repaint
         fragment->repaintFragmentedFlowContent(repaintRect);
 }
 
+class RenderFragmentedFlow::FragmentSearchAdapter {
+public:
+    explicit FragmentSearchAdapter(LayoutUnit offset)
+        : m_offset(offset)
+    {
+    }
+
+    const LayoutUnit& lowValue() const { return m_offset; }
+    const LayoutUnit& highValue() const { return m_offset; }
+
+    void collectIfNeeded(const PODInterval<LayoutUnit, WeakPtr<RenderFragmentContainer>>& interval)
+    {
+        if (m_result)
+            return;
+        if (interval.low() <= m_offset && interval.high() > m_offset)
+            m_result = interval.data();
+    }
+
+    RenderFragmentContainer* result() const { return m_result.get(); }
+
+private:
+    LayoutUnit m_offset;
+    WeakPtr<RenderFragmentContainer> m_result;
+};
+
 RenderFragmentContainer* RenderFragmentedFlow::fragmentAtBlockOffset(const RenderBox* clampBox, LayoutUnit offset, bool extendLastFragment) const
 {
     ASSERT(!m_fragmentsInvalidated);
@@ -229,21 +253,24 @@ RenderFragmentContainer* RenderFragmentedFlow::fragmentAtBlockOffset(const Rende
     if (m_fragmentList.size() == 1 && extendLastFragment)
         return m_fragmentList.first();
 
+    auto clamp = [clampBox](RenderFragmentContainer* fragment)  {
+        return clampBox ? clampBox->clampToStartAndEndFragments(fragment) : fragment;
+    };
+
     if (offset <= 0)
-        return clampBox ? clampBox->clampToStartAndEndFragments(m_fragmentList.first()) : m_fragmentList.first();
+        return clamp(m_fragmentList.first());
 
     FragmentSearchAdapter adapter(offset);
-    m_fragmentIntervalTree.allOverlapsWithAdapter<FragmentSearchAdapter>(adapter);
+    m_fragmentIntervalTree.allOverlapsWithAdapter(adapter);
+    if (auto* fragment = adapter.result())
+        return clamp(fragment);
 
     // If no fragment was found, the offset is in the flow thread overflow.
     // The last fragment will contain the offset if extendLastFragment is set or if the last fragment is a set.
-    if (!adapter.result() && (extendLastFragment || m_fragmentList.last()->isRenderFragmentContainerSet()))
-        return clampBox ? clampBox->clampToStartAndEndFragments(m_fragmentList.last()) : m_fragmentList.last();
+    if (extendLastFragment || m_fragmentList.last()->isRenderFragmentContainerSet())
+        return clamp(m_fragmentList.last());
 
-    RenderFragmentContainer* fragment = adapter.result();
-    if (!clampBox)
-        return fragment;
-    return fragment ? clampBox->clampToStartAndEndFragments(fragment) : nullptr;
+    return nullptr;
 }
 
 LayoutPoint RenderFragmentedFlow::adjustedPositionRelativeToOffsetParent(const RenderBoxModelObject& boxModelObject, const LayoutPoint& startPoint) const
@@ -781,7 +808,7 @@ void RenderFragmentedFlow::markFragmentsForOverflowLayoutIfNeeded()
 void RenderFragmentedFlow::updateFragmentsFragmentedFlowPortionRect()
 {
     LayoutUnit logicalHeight;
-    // FIXME: Optimize not to clear the interval all the time. This implies manually managing the tree nodes lifecycle.
+    // FIXME: Optimize not to clear the interval tree all the time. This would involve manually managing the tree nodes' lifecycle.
     m_fragmentIntervalTree.clear();
     for (auto& fragment : m_fragmentList) {
         LayoutUnit fragmentLogicalWidth = fragment->pageLogicalWidth();
@@ -791,7 +818,7 @@ void RenderFragmentedFlow::updateFragmentsFragmentedFlowPortionRect()
 
         fragment->setFragmentedFlowPortionRect(isHorizontalWritingMode() ? fragmentRect : fragmentRect.transposedRect());
 
-        m_fragmentIntervalTree.add(FragmentIntervalTree::createInterval(logicalHeight, logicalHeight + fragmentLogicalHeight, makeWeakPtr(fragment)));
+        m_fragmentIntervalTree.add({ logicalHeight, logicalHeight + fragmentLogicalHeight, makeWeakPtr(fragment) });
 
         logicalHeight += fragmentLogicalHeight;
     }
@@ -882,14 +909,6 @@ LayoutUnit RenderFragmentedFlow::offsetFromLogicalTopOfFirstFragment(const Rende
     return currentBlock->isHorizontalWritingMode() ? blockRect.y() : blockRect.x();
 }
 
-void RenderFragmentedFlow::FragmentSearchAdapter::collectIfNeeded(const FragmentInterval& interval)
-{
-    if (m_result)
-        return;
-    if (interval.low() <= m_offset && interval.high() > m_offset)
-        m_result = interval.data();
-}
-
 void RenderFragmentedFlow::mapLocalToContainer(const RenderLayerModelObject* repaintContainer, TransformState& transformState, MapCoordinatesFlags mode, bool* wasFixed) const
 {
     if (this == repaintContainer)
index 4c3977e..59cbe2d 100644 (file)
@@ -30,6 +30,7 @@
 #pragma once
 
 #include "LayerFragment.h"
+#include "PODIntervalTree.h"
 #include "RenderBlockFlow.h"
 #include "RenderFragmentContainer.h"
 #include <wtf/ListHashSet.h>
@@ -202,8 +203,6 @@ protected:
     void removeRenderBoxFragmentInfo(RenderBox&);
     void removeLineFragmentInfo(const RenderBlockFlow&);
 
-    RenderFragmentContainerList m_fragmentList;
-
     class RenderFragmentContainerRange {
     public:
         RenderFragmentContainerRange() = default;
@@ -230,39 +229,23 @@ protected:
         bool m_rangeInvalidated;
     };
 
-    typedef PODInterval<LayoutUnit, WeakPtr<RenderFragmentContainer>> FragmentInterval;
-    typedef PODIntervalTree<LayoutUnit, WeakPtr<RenderFragmentContainer>> FragmentIntervalTree;
-
-    class FragmentSearchAdapter {
-    public:
-        FragmentSearchAdapter(LayoutUnit offset)
-            : m_offset(offset)
-        {
-        }
-        
-        const LayoutUnit& lowValue() const { return m_offset; }
-        const LayoutUnit& highValue() const { return m_offset; }
-        void collectIfNeeded(const FragmentInterval&);
-
-        RenderFragmentContainer* result() const { return m_result.get(); }
+    class FragmentSearchAdapter;
 
-    private:
-        LayoutUnit m_offset;
-        WeakPtr<RenderFragmentContainer> m_result;
-    };
+    RenderFragmentContainerList m_fragmentList;
 
     // Map a line to its containing fragment.
     std::unique_ptr<ContainingFragmentMap> m_lineToFragmentMap;
 
     // Map a box to the list of fragments in which the box is rendered.
-    typedef HashMap<const RenderBox*, RenderFragmentContainerRange> RenderFragmentContainerRangeMap;
+    using RenderFragmentContainerRangeMap = HashMap<const RenderBox*, RenderFragmentContainerRange>;
     RenderFragmentContainerRangeMap m_fragmentRangeMap;
 
     // Map a box with a fragment break to the auto height fragment affected by that break. 
-    typedef HashMap<RenderBox*, RenderFragmentContainer*> RenderBoxToFragmentMap;
+    using RenderBoxToFragmentMap = HashMap<RenderBox*, RenderFragmentContainer*>;
     RenderBoxToFragmentMap m_breakBeforeToFragmentMap;
     RenderBoxToFragmentMap m_breakAfterToFragmentMap;
 
+    using FragmentIntervalTree = PODIntervalTree<LayoutUnit, WeakPtr<RenderFragmentContainer>>;
     FragmentIntervalTree m_fragmentIntervalTree;
 
     CurrentRenderFragmentContainerMaintainer* m_currentFragmentMaintainer;
@@ -275,20 +258,4 @@ protected:
 
 } // namespace WebCore
 
-#ifndef NDEBUG
-
-namespace WTF {
-
-// This structure is used by PODIntervalTree for debugging.
-template <> struct ValueToString<WebCore::RenderFragmentContainer*> {
-    static String string(const WebCore::RenderFragmentContainer* value) { return value->debugString(); }
-};
-template <> struct ValueToString<WeakPtr<WebCore::RenderFragmentContainer>> {
-    static String string(const WeakPtr<WebCore::RenderFragmentContainer>& value) { return value ? value->debugString() : String { }; }
-};
-
-} // namespace WTF
-
-#endif
-
 SPECIALIZE_TYPE_TRAITS_RENDER_OBJECT(RenderFragmentedFlow, isRenderFragmentedFlow())
index 65a5af9..9ec085b 100644 (file)
@@ -125,13 +125,8 @@ LineSegment PolygonShape::getExcludedInterval(LayoutUnit logicalTop, LayoutUnit
     if (m_polygon.isEmpty() || !m_polygon.boundingBox().overlapsYRange(y1 - shapeMargin(), y2 + shapeMargin()))
         return LineSegment();
 
-    Vector<const FloatPolygonEdge*> overlappingEdges;
-    if (!m_polygon.overlappingEdges(y1 - shapeMargin(), y2 + shapeMargin(), overlappingEdges))
-        return LineSegment();
-
     FloatShapeInterval excludedInterval;
-    for (unsigned i = 0; i < overlappingEdges.size(); i++) {
-        const FloatPolygonEdge& edge = *(overlappingEdges[i]);
+    for (const FloatPolygonEdge& edge : m_polygon.overlappingEdges(y1 - shapeMargin(), y2 + shapeMargin())) {
         if (edge.maxY() == edge.minY())
             continue;
         if (!shapeMargin())
index 14702d2..1871808 100644 (file)
@@ -63,6 +63,8 @@
 #include "RenderTreeBuilderRuby.h"
 #include "RenderTreeBuilderSVG.h"
 #include "RenderTreeBuilderTable.h"
+#include "RenderView.h"
+
 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
 #include "FrameView.h"
 #include "FrameViewLayoutContext.h"
index 576ffa6..9b2e87d 100644 (file)
 
 namespace WebCore {
 
-class RenderElement;
+class RenderText;
+class RenderTextFragment;
 
 class RenderTreeBuilder::FirstLetter {
     WTF_MAKE_FAST_ALLOCATED;
 public:
-    FirstLetter(RenderTreeBuilder&);
+    explicit FirstLetter(RenderTreeBuilder&);
 
     void updateAfterDescendants(RenderBlock&);
     void cleanupOnDestroy(RenderTextFragment&);
index c9d289a..4187893 100644 (file)
@@ -31,6 +31,7 @@
 #include "RenderMultiColumnSpannerPlaceholder.h"
 #include "RenderTreeBuilder.h"
 #include "RenderTreeBuilderBlock.h"
+#include "RenderView.h"
 
 namespace WebCore {
 
index 23a9268..01bf16e 100644 (file)
@@ -26,9 +26,6 @@
 #pragma once
 
 #include "RenderElement.h"
-#include "RenderFragmentedFlow.h"
-#include "RenderText.h"
-#include "RenderView.h"
 
 namespace WebCore {
 
index 82a5802..3656f3b 100644 (file)
@@ -45,6 +45,7 @@
 #include "RenderMultiColumnFlow.h"
 #include "RenderMultiColumnSet.h"
 #include "RenderTreeUpdaterGeneratedContent.h"
+#include "RenderView.h"
 #include "RuntimeEnabledFeatures.h"
 #include "StyleResolver.h"
 #include "StyleTreeResolver.h"