Simple line layout: Add support for pagination.
authorzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 16 Feb 2017 23:02:56 +0000 (23:02 +0000)
committerzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 16 Feb 2017 23:02:56 +0000 (23:02 +0000)
https://bugs.webkit.org/show_bug.cgi?id=168355
<rdar://problem/30119769>

Reviewed by David Hyatt.

This patch adds basic support for paginated content including widows and orphans.

This is based on the normal line layout pagination logic. However there are 2 major
advantages here (and they allow us to have a much simpler logic):
1. all the lines are positioned by the time we start paginating them and
2. lines always have uniform heights.

This is not enabled yet.

* rendering/RenderBlockFlow.h:
* rendering/SimpleLineLayout.cpp:
(WebCore::SimpleLineLayout::computeLineTopAndBottomWithOverflow):
(WebCore::SimpleLineLayout::computeLineBreakIndex):
(WebCore::SimpleLineLayout::setPageBreakForLine):
(WebCore::SimpleLineLayout::computeOffsetAfterLineBreak):
(WebCore::SimpleLineLayout::updateMinimumPageHeight):
(WebCore::SimpleLineLayout::adjustLinePositionsForPagination):
(WebCore::SimpleLineLayout::create):
(WebCore::SimpleLineLayout::Layout::create):
(WebCore::SimpleLineLayout::Layout::Layout):
* rendering/SimpleLineLayout.h:
(WebCore::SimpleLineLayout::Layout::isPaginated):
(WebCore::SimpleLineLayout::Layout::struts):
* rendering/SimpleLineLayoutFunctions.h:
(WebCore::SimpleLineLayout::computeFlowHeight):
* rendering/SimpleLineLayoutResolver.h:
(WebCore::SimpleLineLayout::RunResolver::Run::computeBaselinePosition):

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

Source/WebCore/ChangeLog
Source/WebCore/rendering/RenderBlockFlow.h
Source/WebCore/rendering/SimpleLineLayout.cpp
Source/WebCore/rendering/SimpleLineLayout.h
Source/WebCore/rendering/SimpleLineLayoutFunctions.h
Source/WebCore/rendering/SimpleLineLayoutResolver.h

index aaa6a3a..7cae593 100644 (file)
@@ -1,3 +1,39 @@
+2017-02-16  Zalan Bujtas  <zalan@apple.com>
+
+        Simple line layout: Add support for pagination.
+        https://bugs.webkit.org/show_bug.cgi?id=168355
+        <rdar://problem/30119769>
+
+        Reviewed by David Hyatt.
+
+        This patch adds basic support for paginated content including widows and orphans.
+
+        This is based on the normal line layout pagination logic. However there are 2 major
+        advantages here (and they allow us to have a much simpler logic):
+        1. all the lines are positioned by the time we start paginating them and
+        2. lines always have uniform heights. 
+
+        This is not enabled yet.
+
+        * rendering/RenderBlockFlow.h:
+        * rendering/SimpleLineLayout.cpp:
+        (WebCore::SimpleLineLayout::computeLineTopAndBottomWithOverflow):
+        (WebCore::SimpleLineLayout::computeLineBreakIndex):
+        (WebCore::SimpleLineLayout::setPageBreakForLine):
+        (WebCore::SimpleLineLayout::computeOffsetAfterLineBreak):
+        (WebCore::SimpleLineLayout::updateMinimumPageHeight):
+        (WebCore::SimpleLineLayout::adjustLinePositionsForPagination):
+        (WebCore::SimpleLineLayout::create):
+        (WebCore::SimpleLineLayout::Layout::create):
+        (WebCore::SimpleLineLayout::Layout::Layout):
+        * rendering/SimpleLineLayout.h:
+        (WebCore::SimpleLineLayout::Layout::isPaginated):
+        (WebCore::SimpleLineLayout::Layout::struts):
+        * rendering/SimpleLineLayoutFunctions.h:
+        (WebCore::SimpleLineLayout::computeFlowHeight):
+        * rendering/SimpleLineLayoutResolver.h:
+        (WebCore::SimpleLineLayout::RunResolver::Run::computeBaselinePosition):
+
 2017-02-11  Filip Pizlo  <fpizlo@apple.com>
 
         The collector thread should only start when the mutator doesn't have heap access
index 41b8591..4bedb55 100644 (file)
@@ -395,16 +395,16 @@ public:
     bool needsLayoutAfterRegionRangeChange() const override;
     WEBCORE_EXPORT RenderText* findClosestTextAtAbsolutePoint(const FloatPoint&);
 
-protected:
-    void computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const override;
-    
     // A page break is required at some offset due to space shortage in the current fragmentainer.
     void setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage);
-
     // Update minimum page height required to avoid fragmentation where it shouldn't occur (inside
     // unbreakable content, between orphans and widows, etc.). This will be used as a hint to the
     // column balancer to help set a good minimum column height.
     void updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight);
+
+protected:
+    void computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const override;
+    
     bool pushToNextPageWithMinimumLogicalHeight(LayoutUnit& adjustment, LayoutUnit logicalOffset, LayoutUnit minimumLogicalHeight) const;
 
     // If the child is unsplittable and can't fit on the current page, return the top of the next page/column.
index e7f1640..08570ee 100644 (file)
@@ -907,6 +907,118 @@ 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::SimplePaginationStruts& 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::SimplePaginationStruts& 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 void setPageBreakForLine(unsigned lineBreak, PaginatedLines& lines, RenderBlockFlow& flow)
+{
+    if (!lineBreak) {
+        // When the line does not fit the current page, just add a page break in front.
+        auto line = lines.first();
+        flow.setPageBreak(line.top, flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary));
+        return;
+    }
+    auto beforeLineBreak = lines.at(lineBreak - 1);
+    auto spaceShortage = flow.pageRemainingLogicalHeightForOffset(beforeLineBreak.top, RenderBlockFlow::ExcludePageBoundary) - beforeLineBreak.height;
+    flow.setPageBreak(beforeLineBreak.bottom, spaceShortage);
+}
+
+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 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::SimplePaginationStruts& 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.append({ lineBreakIndex, computeOffsetAfterLineBreak(lines[lineBreakIndex].top, !lineBreakIndex, atTheTopOfColumnOrPage, flow) });
+            // 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();
@@ -931,20 +1043,23 @@ std::unique_ptr<Layout> create(RenderBlockFlow& flow)
 {
     unsigned lineCount = 0;
     Layout::RunVector runs;
-
     createTextRuns(runs, flow, lineCount);
-    return Layout::create(runs, lineCount);
+    Layout::SimplePaginationStruts struts;
+    if (flow.view().layoutState() && flow.view().layoutState()->isPaginated())
+        adjustLinePositionsForPagination(runs, struts, flow, lineCount);
+    return Layout::create(runs, struts, lineCount);
 }
 
-std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
+std::unique_ptr<Layout> Layout::create(const RunVector& runVector, SimplePaginationStruts& struts, unsigned lineCount)
 {
     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
-    return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
+    return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, struts, lineCount));
 }
 
-Layout::Layout(const RunVector& runVector, unsigned lineCount)
+Layout::Layout(const RunVector& runVector, SimplePaginationStruts& struts, unsigned lineCount)
     : m_lineCount(lineCount)
     , m_runCount(runVector.size())
+    , m_paginationStruts(WTFMove(struts))
 {
     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
 }
index b288e04..4d3ab24 100644 (file)
@@ -66,22 +66,31 @@ struct Run {
     ExpansionBehavior expansionBehavior { ForbidLeadingExpansion | ForbidTrailingExpansion };
 };
 
+struct SimplePaginationStrut {
+    unsigned lineBreak;
+    float offset;
+};
+
 class Layout {
     WTF_MAKE_FAST_ALLOCATED;
 public:
-    typedef Vector<Run, 10> RunVector;
-    static std::unique_ptr<Layout> create(const RunVector&, unsigned lineCount);
+    using RunVector = Vector<Run, 10>;
+    using SimplePaginationStruts = Vector<SimplePaginationStrut, 4>;
+    static std::unique_ptr<Layout> create(const RunVector&, SimplePaginationStruts&, unsigned lineCount);
 
     unsigned lineCount() const { return m_lineCount; }
 
     unsigned runCount() const { return m_runCount; }
     const Run& runAt(unsigned i) const { return m_runs[i]; }
 
+    bool isPaginated() const { return !m_paginationStruts.isEmpty(); }
+    const SimplePaginationStruts& struts() const { return m_paginationStruts; }
 private:
-    Layout(const RunVector&, unsigned lineCount);
+    Layout(const RunVector&, SimplePaginationStruts&, unsigned lineCount);
 
     unsigned m_lineCount;
     unsigned m_runCount;
+    SimplePaginationStruts m_paginationStruts;
     Run m_runs[0];
 };
 
index ff2ec6f..b5fdf68 100644 (file)
@@ -71,7 +71,12 @@ namespace SimpleLineLayout {
 
 inline LayoutUnit computeFlowHeight(const RenderBlockFlow& flow, const Layout& layout)
 {
-    return lineHeightFromFlow(flow) * layout.lineCount();
+    auto flowHeight = lineHeightFromFlow(flow) * layout.lineCount();
+    if (!layout.isPaginated())
+        return flowHeight;
+    for (auto& strutEntry : layout.struts())
+        flowHeight += strutEntry.offset;
+    return flowHeight;
 }
 
 inline LayoutUnit computeFlowFirstLineBaseline(const RenderBlockFlow& flow, const Layout& layout)
index 3cc3fb9..73345b6 100644 (file)
@@ -206,7 +206,15 @@ inline RunResolver::Iterator& RunResolver::Iterator::operator++()
 inline float RunResolver::Run::computeBaselinePosition() const
 {
     auto& resolver = m_iterator.resolver();
-    return resolver.m_lineHeight * lineIndex() + resolver.m_baseline + resolver.m_borderAndPaddingBefore;
+    auto offset = resolver.m_borderAndPaddingBefore + resolver.m_lineHeight * lineIndex();
+    if (!resolver.m_layout.isPaginated())
+        return offset + resolver.m_baseline;
+    for (auto& strutEntry : resolver.m_layout.struts()) {
+        if (strutEntry.lineBreak > lineIndex())
+            break;
+        offset += strutEntry.offset;
+    }
+    return offset + resolver.m_baseline;
 }
 
 inline RunResolver::Iterator& RunResolver::Iterator::operator--()