Simple line layout: Re-adjust paginated lines when block height changes.
authorzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 25 Feb 2017 02:14:40 +0000 (02:14 +0000)
committerzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 25 Feb 2017 02:14:40 +0000 (02:14 +0000)
https://bugs.webkit.org/show_bug.cgi?id=168838
<rdar://problem/30701233>

Reviewed by Antti Koivisto.

When the estimated block height is wrong, we issue an additional layout on the inline children
so that we get the pagination right (this layout is setChildNeedsLayout(MarkOnlyThis) only).
Since the height change only affects the struts and page breaks (and again, the relayoutChildren flag is false)
we don't need to re-layout the content, but instead we just need to re-adjust the pagination for the simple lines.
This patch also moves the pagination logic to SimpleLineLayoutPagination.cpp.

Not enabled yet.

* CMakeLists.txt:
* WebCore.xcodeproj/project.pbxproj:
* rendering/RenderBlockFlow.cpp:
(WebCore::RenderBlockFlow::layoutSimpleLines):
* rendering/RenderingAllInOne.cpp:
* rendering/SimpleLineLayout.cpp:
(WebCore::SimpleLineLayout::canUseForWithReason):
(WebCore::SimpleLineLayout::create):
(WebCore::SimpleLineLayout::Layout::create):
(WebCore::SimpleLineLayout::Layout::Layout):
(WebCore::SimpleLineLayout::computeLineTopAndBottomWithOverflow): Deleted.
(WebCore::SimpleLineLayout::computeLineBreakIndex): Deleted.
(WebCore::SimpleLineLayout::computeOffsetAfterLineBreak): Deleted.
(WebCore::SimpleLineLayout::setPageBreakForLine): Deleted.
(WebCore::SimpleLineLayout::updateMinimumPageHeight): Deleted.
(WebCore::SimpleLineLayout::adjustLinePositionsForPagination): Deleted.
* rendering/SimpleLineLayout.h:
(WebCore::SimpleLineLayout::Layout::setIsPaginated):
(WebCore::SimpleLineLayout::Layout::setLineStruts):
* rendering/SimpleLineLayoutPagination.cpp: Added.
(WebCore::SimpleLineLayout::computeLineTopAndBottomWithOverflow):
(WebCore::SimpleLineLayout::computeLineBreakIndex):
(WebCore::SimpleLineLayout::computeOffsetAfterLineBreak):
(WebCore::SimpleLineLayout::setPageBreakForLine):
(WebCore::SimpleLineLayout::updateMinimumPageHeight):
(WebCore::SimpleLineLayout::adjustLinePositionsForPagination):
* rendering/SimpleLineLayoutPagination.h: Added.

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

Source/WebCore/CMakeLists.txt
Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/rendering/RenderBlockFlow.cpp
Source/WebCore/rendering/RenderingAllInOne.cpp
Source/WebCore/rendering/SimpleLineLayout.cpp
Source/WebCore/rendering/SimpleLineLayout.h
Source/WebCore/rendering/SimpleLineLayoutPagination.cpp [new file with mode: 0644]
Source/WebCore/rendering/SimpleLineLayoutPagination.h [new file with mode: 0644]

index abff164..89853c4 100644 (file)
@@ -2481,6 +2481,7 @@ set(WebCore_SOURCES
     rendering/SimpleLineLayout.cpp
     rendering/SimpleLineLayoutFlowContents.cpp
     rendering/SimpleLineLayoutFunctions.cpp
+    rendering/SimpleLineLayoutPagination.cpp
     rendering/SimpleLineLayoutResolver.cpp
     rendering/SimpleLineLayoutTextFragmentIterator.cpp
     rendering/TextDecorationPainter.cpp
index 816c013..15a3c42 100644 (file)
@@ -1,3 +1,47 @@
+2017-02-24  Zalan Bujtas  <zalan@apple.com>
+
+        Simple line layout: Re-adjust paginated lines when block height changes.
+        https://bugs.webkit.org/show_bug.cgi?id=168838
+        <rdar://problem/30701233>
+
+        Reviewed by Antti Koivisto.
+
+        When the estimated block height is wrong, we issue an additional layout on the inline children
+        so that we get the pagination right (this layout is setChildNeedsLayout(MarkOnlyThis) only).
+        Since the height change only affects the struts and page breaks (and again, the relayoutChildren flag is false)
+        we don't need to re-layout the content, but instead we just need to re-adjust the pagination for the simple lines. 
+        This patch also moves the pagination logic to SimpleLineLayoutPagination.cpp.
+
+        Not enabled yet.
+
+        * CMakeLists.txt:
+        * WebCore.xcodeproj/project.pbxproj:
+        * rendering/RenderBlockFlow.cpp:
+        (WebCore::RenderBlockFlow::layoutSimpleLines):
+        * rendering/RenderingAllInOne.cpp:
+        * rendering/SimpleLineLayout.cpp:
+        (WebCore::SimpleLineLayout::canUseForWithReason):
+        (WebCore::SimpleLineLayout::create):
+        (WebCore::SimpleLineLayout::Layout::create):
+        (WebCore::SimpleLineLayout::Layout::Layout):
+        (WebCore::SimpleLineLayout::computeLineTopAndBottomWithOverflow): Deleted.
+        (WebCore::SimpleLineLayout::computeLineBreakIndex): Deleted.
+        (WebCore::SimpleLineLayout::computeOffsetAfterLineBreak): Deleted.
+        (WebCore::SimpleLineLayout::setPageBreakForLine): Deleted.
+        (WebCore::SimpleLineLayout::updateMinimumPageHeight): Deleted.
+        (WebCore::SimpleLineLayout::adjustLinePositionsForPagination): Deleted.
+        * rendering/SimpleLineLayout.h:
+        (WebCore::SimpleLineLayout::Layout::setIsPaginated):
+        (WebCore::SimpleLineLayout::Layout::setLineStruts):
+        * rendering/SimpleLineLayoutPagination.cpp: Added.
+        (WebCore::SimpleLineLayout::computeLineTopAndBottomWithOverflow):
+        (WebCore::SimpleLineLayout::computeLineBreakIndex):
+        (WebCore::SimpleLineLayout::computeOffsetAfterLineBreak):
+        (WebCore::SimpleLineLayout::setPageBreakForLine):
+        (WebCore::SimpleLineLayout::updateMinimumPageHeight):
+        (WebCore::SimpleLineLayout::adjustLinePositionsForPagination):
+        * rendering/SimpleLineLayoutPagination.h: Added.
+
 2017-02-24  Jon Lee  <jonlee@apple.com>
 
         Alias "system-ui" for the System font name
index af56363..ad19985 100644 (file)
                0FFD4D6018651FA300512F6E /* AsyncScrollingCoordinator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFD4D5E18651FA300512F6E /* AsyncScrollingCoordinator.cpp */; };
                0FFD4D6118651FA300512F6E /* AsyncScrollingCoordinator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FFD4D5F18651FA300512F6E /* AsyncScrollingCoordinator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                10FB084B14E15C7E00A3DB98 /* PublicURLManager.h in Headers */ = {isa = PBXBuildFile; fileRef = 10FB084A14E15C7E00A3DB98 /* PublicURLManager.h */; };
+               112B34D21E60B8A700BB310A /* SimpleLineLayoutPagination.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 112B34D01E60B8A700BB310A /* SimpleLineLayoutPagination.cpp */; };
+               112B34D51E60B98300BB310A /* SimpleLineLayoutPagination.h in Headers */ = {isa = PBXBuildFile; fileRef = 112B34D41E60B98300BB310A /* SimpleLineLayoutPagination.h */; };
                120DE3ED1C86CA3E00B6D4DD /* WebAnimation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 120DE3EA1C80161C00B6D4DD /* WebAnimation.cpp */; };
                120DE3F11C86CCC600B6D4DD /* AnimationEffect.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 120DE3EE1C86CCBD00B6D4DD /* AnimationEffect.cpp */; };
                120DE3F81C87C5A800B6D4DD /* JSWebAnimation.h in Headers */ = {isa = PBXBuildFile; fileRef = 120DE3F51C87C58E00B6D4DD /* JSWebAnimation.h */; };
                0FFD4D5E18651FA300512F6E /* AsyncScrollingCoordinator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AsyncScrollingCoordinator.cpp; sourceTree = "<group>"; };
                0FFD4D5F18651FA300512F6E /* AsyncScrollingCoordinator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AsyncScrollingCoordinator.h; sourceTree = "<group>"; };
                10FB084A14E15C7E00A3DB98 /* PublicURLManager.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PublicURLManager.h; sourceTree = "<group>"; };
+               112B34D01E60B8A700BB310A /* SimpleLineLayoutPagination.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SimpleLineLayoutPagination.cpp; sourceTree = "<group>"; };
+               112B34D41E60B98300BB310A /* SimpleLineLayoutPagination.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SimpleLineLayoutPagination.h; sourceTree = "<group>"; };
                120DE3EA1C80161C00B6D4DD /* WebAnimation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WebAnimation.cpp; sourceTree = "<group>"; };
                120DE3EB1C80161C00B6D4DD /* WebAnimation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebAnimation.h; sourceTree = "<group>"; };
                120DE3EC1C80161C00B6D4DD /* WebAnimation.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = WebAnimation.idl; sourceTree = "<group>"; };
                                585D6E021A1A792E00FA4F12 /* SimpleLineLayoutFlowContents.h */,
                                E4E9B11A18145692003ACCDF /* SimpleLineLayoutFunctions.cpp */,
                                E4E9B11C1814569C003ACCDF /* SimpleLineLayoutFunctions.h */,
+                               112B34D41E60B98300BB310A /* SimpleLineLayoutPagination.h */,
+                               112B34D01E60B8A700BB310A /* SimpleLineLayoutPagination.cpp */,
                                585D6DFB1A15355600FA4F12 /* SimpleLineLayoutResolver.cpp */,
                                E4E9B1181810916F003ACCDF /* SimpleLineLayoutResolver.h */,
                                582CB0541A78A2B200AFFCC4 /* SimpleLineLayoutTextFragmentIterator.cpp */,
                                931CBD11161A44E900E4C874 /* ScrollingStateTree.h in Headers */,
                                1AF62F2614DAFEA10041556C /* ScrollingThread.h in Headers */,
                                1AAADDA414DB409F00AF64B3 /* ScrollingTree.h in Headers */,
+                               112B34D51E60B98300BB310A /* SimpleLineLayoutPagination.h in Headers */,
                                93C38C03164473DD00091EB2 /* ScrollingTreeFixedNode.h in Headers */,
                                0FEA3E88191B3BD7000F1B55 /* ScrollingTreeFrameScrollingNode.h in Headers */,
                                0FC4E411187F82E10045882C /* ScrollingTreeFrameScrollingNodeIOS.h in Headers */,
                                975CA28A130365F800E99AD9 /* Crypto.cpp in Sources */,
                                E172AF6D180F24C600FBADB9 /* CryptoAlgorithm.cpp in Sources */,
                                E125F8411824253A00D84CD9 /* CryptoAlgorithmAES_CBC.cpp in Sources */,
+                               112B34D21E60B8A700BB310A /* SimpleLineLayoutPagination.cpp in Sources */,
                                E125F845182425C900D84CD9 /* CryptoAlgorithmAES_CBCMac.cpp in Sources */,
                                E1FE137A184D21BB00892F13 /* CryptoAlgorithmAES_KW.cpp in Sources */,
                                E1FE137E184D270200892F13 /* CryptoAlgorithmAES_KWMac.cpp in Sources */,
index 514a579..5ac7a54 100644 (file)
@@ -51,6 +51,7 @@
 #include "RenderView.h"
 #include "Settings.h"
 #include "SimpleLineLayoutFunctions.h"
+#include "SimpleLineLayoutPagination.h"
 #include "VerticalPositionCache.h"
 #include "VisiblePosition.h"
 
@@ -3671,6 +3672,10 @@ void RenderBlockFlow::layoutSimpleLines(bool relayoutChildren, LayoutUnit& repai
         deleteLineBoxesBeforeSimpleLineLayout();
         m_simpleLineLayout = SimpleLineLayout::create(*this);
     }
+    if (view().layoutState() && view().layoutState()->isPaginated()) {
+        m_simpleLineLayout->setIsPaginated();
+        SimpleLineLayout::adjustLinePositionsForPagination(*m_simpleLineLayout, *this);
+    }
     for (auto& renderer : childrenOfType<RenderObject>(*this))
         renderer.clearNeedsLayout();
     ASSERT(!m_lineBoxes.firstLineBox());
index 06a2635..26fde5e 100644 (file)
 #include "SimpleLineLayout.cpp"
 #include "SimpleLineLayoutFlowContents.cpp"
 #include "SimpleLineLayoutFunctions.cpp"
+#include "SimpleLineLayoutPagination.cpp"
 #include "SimpleLineLayoutResolver.cpp"
 #include "SimpleLineLayoutTextFragmentIterator.cpp"
 #include "TextDecorationPainter.cpp"
index f390b37..ea42262 100644 (file)
@@ -907,121 +907,6 @@ static void closeLineEndingAndAdjustRuns(LineState& line, Layout::RunVector& run
     ++lineCount;
 }
 
-struct PaginatedLine {
-    LayoutUnit top;
-    LayoutUnit bottom;
-    LayoutUnit height; // Same value for each lines atm.
-};
-using PaginatedLines = Vector<PaginatedLine, 20>;
-
-static PaginatedLine computeLineTopAndBottomWithOverflow(const RenderBlockFlow& flow, unsigned lineIndex, Layout::SimpleLineStruts& struts)
-{
-    // FIXME: Add visualOverflowForDecorations.
-    auto& fontMetrics = flow.style().fontCascade().fontMetrics();
-    auto ascent = fontMetrics.floatAscent();
-    auto descent = fontMetrics.floatDescent();
-    auto lineHeight = lineHeightFromFlow(flow);
-    LayoutUnit offset = flow.borderAndPaddingBefore();
-    for (auto& strut : struts) {
-        if (strut.lineBreak > lineIndex)
-            break;
-        offset += strut.offset;
-    }
-    if (ascent + descent <= lineHeight) {
-        auto topPosition = lineIndex * lineHeight + offset;
-        return { topPosition, topPosition + lineHeight, lineHeight };
-    }
-    auto baseline = baselineFromFlow(flow);
-    auto topPosition = lineIndex * lineHeight + offset + baseline - ascent;
-    auto bottomPosition = topPosition + ascent + descent;
-    return { topPosition, bottomPosition, bottomPosition - topPosition };
-}
-
-static unsigned computeLineBreakIndex(unsigned breakCandidate, unsigned lineCount, unsigned widows, const Layout::SimpleLineStruts& struts)
-{
-    // First line does not fit the current page.
-    if (!breakCandidate)
-        return breakCandidate;
-    
-    auto remainingLineCount = lineCount - breakCandidate;
-    if (widows <= remainingLineCount)
-        return breakCandidate;
-    
-    // Only break after the first line with widows.
-    auto lineBreak = std::max<int>(lineCount - widows, 1);
-    // Break on current page only.
-    if (struts.isEmpty())
-        return lineBreak;
-    ASSERT(struts.last().lineBreak + 1 < lineCount);
-    return std::max<unsigned>(struts.last().lineBreak + 1, lineBreak);
-}
-
-static LayoutUnit computeOffsetAfterLineBreak(LayoutUnit lineBreakPosition, bool isFirstLine, bool atTheTopOfColumnOrPage, const RenderBlockFlow& flow)
-{
-    // No offset for top of the page lines unless widows pushed the line break.
-    LayoutUnit offset = isFirstLine ? flow.borderAndPaddingBefore() : LayoutUnit();
-    if (atTheTopOfColumnOrPage)
-        return offset;
-    return offset + flow.pageRemainingLogicalHeightForOffset(lineBreakPosition, RenderBlockFlow::ExcludePageBoundary);
-}
-
-static void setPageBreakForLine(unsigned lineBreakIndex, PaginatedLines& lines, RenderBlockFlow& flow, Layout::SimpleLineStruts& struts,
-    bool atTheTopOfColumnOrPage)
-{
-    if (!lineBreakIndex) {
-        // When the first line does not fit the current page, just add a page break in front and set the strut on the block.
-        auto line = lines.first();
-        auto remainingLogicalHeight = flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary);
-        flow.setPageBreak(line.top, line.height - remainingLogicalHeight);
-        flow.setPaginationStrut(remainingLogicalHeight);
-        return;
-    }
-    auto beforeLineBreak = lines.at(lineBreakIndex - 1);
-    auto spaceShortage = flow.pageRemainingLogicalHeightForOffset(beforeLineBreak.top, RenderBlockFlow::ExcludePageBoundary) - beforeLineBreak.height;
-    flow.setPageBreak(beforeLineBreak.bottom, spaceShortage);
-    struts.append({ lineBreakIndex, computeOffsetAfterLineBreak(lines[lineBreakIndex].top, !lineBreakIndex, atTheTopOfColumnOrPage, flow) });
-}
-
-static void updateMinimumPageHeight(RenderBlockFlow& flow, unsigned lineCount)
-{
-    auto& style = flow.style();
-    auto widows = style.hasAutoWidows() ? 1 : std::max<int>(style.widows(), 1);
-    auto orphans = style.hasAutoOrphans() ? 1 : std::max<int>(style.orphans(), 1);
-    auto minimumLineCount = std::min<unsigned>(std::max(widows, orphans), lineCount);
-    flow.updateMinimumPageHeight(0, minimumLineCount * lineHeightFromFlow(flow));
-}
-
-static void adjustLinePositionsForPagination(Layout::RunVector& runs, Layout::SimpleLineStruts& struts,
-    RenderBlockFlow& flow, unsigned lineCount)
-{
-    updateMinimumPageHeight(flow, lineCount);
-    // First pass with no pagination offset?
-    if (!flow.pageLogicalHeightForOffset(0))
-        return;
-    unsigned lineIndex = 0;
-    auto widows = flow.style().hasAutoWidows() ? 1 : std::max<int>(flow.style().widows(), 1);
-    PaginatedLines lines;
-    for (auto& run : runs) {
-        if (!run.isEndOfLine)
-            continue;
-
-        auto line = computeLineTopAndBottomWithOverflow(flow, lineIndex, struts);
-        lines.append(line);
-        auto remainingHeight = flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary);
-        auto atTheTopOfColumnOrPage = flow.pageLogicalHeightForOffset(line.top) == remainingHeight;
-        if (line.height > remainingHeight || (atTheTopOfColumnOrPage && lineIndex)) {
-            auto lineBreakIndex = computeLineBreakIndex(lineIndex, lineCount, widows, struts);
-            // Are we still at the top of the column/page?
-            atTheTopOfColumnOrPage = atTheTopOfColumnOrPage ? lineIndex == lineBreakIndex : false;
-            setPageBreakForLine(lineBreakIndex, lines, flow, struts, atTheTopOfColumnOrPage);
-            // Recompute line positions that we already visited but window break pushed them to a new page.
-            for (auto i = lineBreakIndex; i < lines.size(); ++i)
-                lines.at(i) = computeLineTopAndBottomWithOverflow(flow, i, struts);
-        }
-        ++lineIndex;
-    }
-}
-
 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
 {
     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
@@ -1047,24 +932,18 @@ std::unique_ptr<Layout> create(RenderBlockFlow& flow)
     unsigned lineCount = 0;
     Layout::RunVector runs;
     createTextRuns(runs, flow, lineCount);
-    Layout::SimpleLineStruts struts;
-    auto isPaginated = flow.view().layoutState() && flow.view().layoutState()->isPaginated();
-    if (isPaginated)
-        adjustLinePositionsForPagination(runs, struts, flow, lineCount);
-    return Layout::create(runs, struts, lineCount, isPaginated);
+    return Layout::create(runs, lineCount);
 }
 
-std::unique_ptr<Layout> Layout::create(const RunVector& runVector, SimpleLineStruts& struts, unsigned lineCount, bool isPaginated)
+std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
 {
     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
-    return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, struts, lineCount, isPaginated));
+    return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
 }
 
-Layout::Layout(const RunVector& runVector, SimpleLineStruts& struts, unsigned lineCount, bool isPaginated)
+Layout::Layout(const RunVector& runVector, unsigned lineCount)
     : m_lineCount(lineCount)
     , m_runCount(runVector.size())
-    , m_isPaginated(isPaginated)
-    , m_lineStruts(WTFMove(struts))
 {
     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
 }
index 5bd4102..3eb041b 100644 (file)
@@ -76,22 +76,24 @@ class Layout {
 public:
     using RunVector = Vector<Run, 10>;
     using SimpleLineStruts = Vector<SimpleLineStrut, 4>;
-    static std::unique_ptr<Layout> create(const RunVector&, SimpleLineStruts&, unsigned lineCount, bool isPaginated);
+    static std::unique_ptr<Layout> create(const RunVector&, unsigned lineCount);
 
     unsigned lineCount() const { return m_lineCount; }
 
     unsigned runCount() const { return m_runCount; }
     const Run& runAt(unsigned i) const { return m_runs[i]; }
 
+    void setIsPaginated() { m_isPaginated = true; }
     bool isPaginated() const { return m_isPaginated; }
     bool hasLineStruts() const { return !m_lineStruts.isEmpty(); }
+    void setLineStruts(SimpleLineStruts&& lineStruts) { m_lineStruts = lineStruts; }
     const SimpleLineStruts& struts() const { return m_lineStruts; }
 private:
-    Layout(const RunVector&, SimpleLineStruts&, unsigned lineCount, bool isPaginated);
+    Layout(const RunVector&, unsigned lineCount);
 
     unsigned m_lineCount;
     unsigned m_runCount;
-    bool m_isPaginated;
+    bool m_isPaginated { false };
     SimpleLineStruts m_lineStruts;
     Run m_runs[0];
 };
diff --git a/Source/WebCore/rendering/SimpleLineLayoutPagination.cpp b/Source/WebCore/rendering/SimpleLineLayoutPagination.cpp
new file mode 100644 (file)
index 0000000..cf5b684
--- /dev/null
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2017 Apple 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:
+ * 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 APPLE INC. AND ITS 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 APPLE INC. OR ITS 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 "SimpleLineLayoutPagination.h"
+
+#include "RenderBlockFlow.h"
+#include "SimpleLineLayout.h"
+#include "SimpleLineLayoutFunctions.h"
+
+namespace WebCore {
+namespace SimpleLineLayout {
+
+struct PaginatedLine {
+    LayoutUnit top;
+    LayoutUnit bottom;
+    LayoutUnit height; // Same value for each lines atm.
+};
+using PaginatedLines = Vector<PaginatedLine, 20>;
+
+static PaginatedLine computeLineTopAndBottomWithOverflow(const RenderBlockFlow& flow, unsigned lineIndex, Layout::SimpleLineStruts& struts)
+{
+    // FIXME: Add visualOverflowForDecorations.
+    auto& fontMetrics = flow.style().fontCascade().fontMetrics();
+    auto ascent = fontMetrics.floatAscent();
+    auto descent = fontMetrics.floatDescent();
+    auto lineHeight = lineHeightFromFlow(flow);
+    LayoutUnit offset = flow.borderAndPaddingBefore();
+    for (auto& strut : struts) {
+        if (strut.lineBreak > lineIndex)
+            break;
+        offset += strut.offset;
+    }
+    if (ascent + descent <= lineHeight) {
+        auto topPosition = lineIndex * lineHeight + offset;
+        return { topPosition, topPosition + lineHeight, lineHeight };
+    }
+    auto baseline = baselineFromFlow(flow);
+    auto topPosition = lineIndex * lineHeight + offset + baseline - ascent;
+    auto bottomPosition = topPosition + ascent + descent;
+    return { topPosition, bottomPosition, bottomPosition - topPosition };
+}
+
+static unsigned computeLineBreakIndex(unsigned breakCandidate, unsigned lineCount, unsigned widows, const Layout::SimpleLineStruts& struts)
+{
+    // First line does not fit the current page.
+    if (!breakCandidate)
+        return breakCandidate;
+    
+    auto remainingLineCount = lineCount - breakCandidate;
+    if (widows <= remainingLineCount)
+        return breakCandidate;
+    
+    // Only break after the first line with widows.
+    auto lineBreak = std::max<int>(lineCount - widows, 1);
+    // Break on current page only.
+    if (struts.isEmpty())
+        return lineBreak;
+    ASSERT(struts.last().lineBreak + 1 < lineCount);
+    return std::max<unsigned>(struts.last().lineBreak + 1, lineBreak);
+}
+
+static LayoutUnit computeOffsetAfterLineBreak(LayoutUnit lineBreakPosition, bool isFirstLine, bool atTheTopOfColumnOrPage, const RenderBlockFlow& flow)
+{
+    // No offset for top of the page lines unless widows pushed the line break.
+    LayoutUnit offset = isFirstLine ? flow.borderAndPaddingBefore() : LayoutUnit();
+    if (atTheTopOfColumnOrPage)
+        return offset;
+    return offset + flow.pageRemainingLogicalHeightForOffset(lineBreakPosition, RenderBlockFlow::ExcludePageBoundary);
+}
+
+static void setPageBreakForLine(unsigned lineBreakIndex, PaginatedLines& lines, RenderBlockFlow& flow, Layout::SimpleLineStruts& struts,
+    bool atTheTopOfColumnOrPage)
+{
+    if (!lineBreakIndex) {
+        // When the first line does not fit the current page, just add a page break in front and set the strut on the block.
+        auto line = lines.first();
+        auto remainingLogicalHeight = flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary);
+        flow.setPageBreak(line.top, line.height - remainingLogicalHeight);
+        flow.setPaginationStrut(remainingLogicalHeight);
+        return;
+    }
+    auto beforeLineBreak = lines.at(lineBreakIndex - 1);
+    auto spaceShortage = flow.pageRemainingLogicalHeightForOffset(beforeLineBreak.top, RenderBlockFlow::ExcludePageBoundary) - beforeLineBreak.height;
+    flow.setPageBreak(beforeLineBreak.bottom, spaceShortage);
+    struts.append({ lineBreakIndex, computeOffsetAfterLineBreak(lines[lineBreakIndex].top, !lineBreakIndex, atTheTopOfColumnOrPage, flow) });
+}
+
+static void updateMinimumPageHeight(RenderBlockFlow& flow, unsigned lineCount)
+{
+    auto& style = flow.style();
+    auto widows = style.hasAutoWidows() ? 1 : std::max<int>(style.widows(), 1);
+    auto orphans = style.hasAutoOrphans() ? 1 : std::max<int>(style.orphans(), 1);
+    auto minimumLineCount = std::min<unsigned>(std::max(widows, orphans), lineCount);
+    flow.updateMinimumPageHeight(0, minimumLineCount * lineHeightFromFlow(flow));
+}
+
+void adjustLinePositionsForPagination(SimpleLineLayout::Layout& simpleLines, RenderBlockFlow& flow)
+{
+    Layout::SimpleLineStruts struts;
+    auto lineCount = simpleLines.lineCount();
+    updateMinimumPageHeight(flow, lineCount);
+    // First pass with no pagination offset?
+    if (!flow.pageLogicalHeightForOffset(0))
+        return;
+    unsigned lineIndex = 0;
+    auto widows = flow.style().hasAutoWidows() ? 1 : std::max<int>(flow.style().widows(), 1);
+    PaginatedLines lines;
+    for (unsigned runIndex = 0; runIndex < simpleLines.runCount(); ++runIndex) {
+        auto& run = simpleLines.runAt(runIndex);
+        if (!run.isEndOfLine)
+            continue;
+
+        auto line = computeLineTopAndBottomWithOverflow(flow, lineIndex, struts);
+        lines.append(line);
+        auto remainingHeight = flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary);
+        auto atTheTopOfColumnOrPage = flow.pageLogicalHeightForOffset(line.top) == remainingHeight;
+        if (line.height > remainingHeight || (atTheTopOfColumnOrPage && lineIndex)) {
+            auto lineBreakIndex = computeLineBreakIndex(lineIndex, lineCount, widows, struts);
+            // Are we still at the top of the column/page?
+            atTheTopOfColumnOrPage = atTheTopOfColumnOrPage ? lineIndex == lineBreakIndex : false;
+            setPageBreakForLine(lineBreakIndex, lines, flow, struts, atTheTopOfColumnOrPage);
+            // Recompute line positions that we already visited but window break pushed them to a new page.
+            for (auto i = lineBreakIndex; i < lines.size(); ++i)
+                lines.at(i) = computeLineTopAndBottomWithOverflow(flow, i, struts);
+        }
+        ++lineIndex;
+    }
+    simpleLines.setLineStruts(WTFMove(struts));
+}
+
+}
+}
diff --git a/Source/WebCore/rendering/SimpleLineLayoutPagination.h b/Source/WebCore/rendering/SimpleLineLayoutPagination.h
new file mode 100644 (file)
index 0000000..dd6a17c
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+ * Copyright (C) 2017 Apple 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:
+ * 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 APPLE INC. AND ITS 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 APPLE INC. OR ITS 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.
+ */
+
+#pragma once
+
+namespace WebCore {
+
+class RenderBlockFlow;
+
+namespace SimpleLineLayout {
+
+class Layout;
+    
+void adjustLinePositionsForPagination(Layout&, RenderBlockFlow&);
+
+}
+}