1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "SimpleLineLayoutPagination.h"
28
29#include "FontCascade.h"
30#include "RenderBlockFlow.h"
31#include "SimpleLineLayout.h"
32#include "SimpleLineLayoutFunctions.h"
33
34namespace WebCore {
35namespace SimpleLineLayout {
36
37struct PaginatedLine {
38 LayoutUnit top;
39 LayoutUnit bottom;
40 LayoutUnit height; // Same value for each lines atm.
41};
42using PaginatedLines = Vector<PaginatedLine, 20>;
43
44static PaginatedLine computeLineTopAndBottomWithOverflow(const RenderBlockFlow& flow, unsigned lineIndex, Layout::SimpleLineStruts& struts)
45{
46 // FIXME: Add visualOverflowForDecorations.
47 auto& fontMetrics = flow.style().fontCascade().fontMetrics();
48 auto ascent = fontMetrics.ascent();
49 auto descent = fontMetrics.descent();
50 auto lineHeight = lineHeightFromFlow(flow);
51 LayoutUnit offset = flow.borderAndPaddingBefore();
52 for (auto& strut : struts) {
53 if (strut.lineBreak > lineIndex)
54 break;
55 offset += strut.offset;
56 }
57 if (ascent + descent <= lineHeight) {
58 auto topPosition = lineIndex * lineHeight + offset;
59 return { topPosition, topPosition + lineHeight, lineHeight };
60 }
61 auto baseline = baselineFromFlow(flow);
62 auto topPosition = lineIndex * lineHeight + offset + baseline - ascent;
63 auto bottomPosition = topPosition + ascent + descent;
64 return { topPosition, bottomPosition, bottomPosition - topPosition };
65}
66
67static unsigned computeLineBreakIndex(unsigned breakCandidate, unsigned lineCount, int orphansNeeded, int widowsNeeded,
68 const Layout::SimpleLineStruts& struts)
69{
70 // First line does not fit the current page.
71 if (!breakCandidate)
72 return breakCandidate;
73
74 int widowsOnTheNextPage = lineCount - breakCandidate;
75 if (widowsNeeded <= widowsOnTheNextPage)
76 return breakCandidate;
77 // Only break after the first line with widows.
78 auto lineBreak = std::max<int>(lineCount - widowsNeeded, 1);
79 if (orphansNeeded > lineBreak)
80 return breakCandidate;
81 // Break on current page only.
82 if (struts.isEmpty())
83 return lineBreak;
84 ASSERT(struts.last().lineBreak + 1 < lineCount);
85 return std::max<unsigned>(struts.last().lineBreak + 1, lineBreak);
86}
87
88static LayoutUnit computeOffsetAfterLineBreak(LayoutUnit lineBreakPosition, bool isFirstLine, bool atTheTopOfColumnOrPage, const RenderBlockFlow& flow)
89{
90 // No offset for top of the page lines unless widows pushed the line break.
91 LayoutUnit offset = isFirstLine ? flow.borderAndPaddingBefore() : 0_lu;
92 if (atTheTopOfColumnOrPage)
93 return offset;
94 return offset + flow.pageRemainingLogicalHeightForOffset(lineBreakPosition, RenderBlockFlow::ExcludePageBoundary);
95}
96
97static void setPageBreakForLine(unsigned lineBreakIndex, PaginatedLines& lines, RenderBlockFlow& flow, Layout::SimpleLineStruts& struts,
98 bool atTheTopOfColumnOrPage)
99{
100 auto line = lines.at(lineBreakIndex);
101 auto remainingLogicalHeight = flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary);
102 auto& style = flow.style();
103 auto firstLineDoesNotFit = !lineBreakIndex && line.height < flow.pageLogicalHeightForOffset(line.top);
104 auto orphanDoesNotFit = !style.hasAutoOrphans() && style.orphans() > (short)lineBreakIndex;
105 if (firstLineDoesNotFit || orphanDoesNotFit) {
106 auto firstLine = lines.first();
107 auto firstLineOverflowRect = computeOverflow(flow, LayoutRect(0_lu, firstLine.top, 0_lu, firstLine.height));
108 auto firstLineUpperOverhang = std::max<LayoutUnit>(-firstLineOverflowRect.y(), 0_lu);
109 flow.setPaginationStrut(line.top + remainingLogicalHeight + firstLineUpperOverhang);
110 return;
111 }
112 if (atTheTopOfColumnOrPage)
113 flow.setPageBreak(line.top, line.height);
114 else
115 flow.setPageBreak(line.top, line.height - remainingLogicalHeight);
116 struts.append({ lineBreakIndex, computeOffsetAfterLineBreak(lines[lineBreakIndex].top, !lineBreakIndex, atTheTopOfColumnOrPage, flow) });
117}
118
119static void updateMinimumPageHeight(RenderBlockFlow& flow, unsigned lineCount)
120{
121 auto& style = flow.style();
122 auto widows = style.hasAutoWidows() ? 1 : std::max<int>(style.widows(), 1);
123 auto orphans = style.hasAutoOrphans() ? 1 : std::max<int>(style.orphans(), 1);
124 auto minimumLineCount = std::min<unsigned>(std::max(widows, orphans), lineCount);
125 flow.updateMinimumPageHeight(0, minimumLineCount * lineHeightFromFlow(flow));
126}
127
128void adjustLinePositionsForPagination(SimpleLineLayout::Layout& simpleLines, RenderBlockFlow& flow)
129{
130 Layout::SimpleLineStruts struts;
131 auto lineCount = simpleLines.lineCount();
132 updateMinimumPageHeight(flow, lineCount);
133 // First pass with no pagination offset?
134 if (!flow.pageLogicalHeightForOffset(0))
135 return;
136 unsigned lineIndex = 0;
137 auto widows = flow.style().hasAutoWidows() ? 1 : std::max<int>(flow.style().widows(), 1);
138 auto orphans = flow.style().hasAutoOrphans() ? 1 : std::max<int>(flow.style().orphans(), 1);
139 PaginatedLines lines;
140 for (unsigned runIndex = 0; runIndex < simpleLines.runCount(); ++runIndex) {
141 auto& run = simpleLines.runAt(runIndex);
142 if (!run.isEndOfLine)
143 continue;
144
145 auto line = computeLineTopAndBottomWithOverflow(flow, lineIndex, struts);
146 lines.append(line);
147 auto remainingHeight = flow.pageRemainingLogicalHeightForOffset(line.top, RenderBlockFlow::ExcludePageBoundary);
148 auto atTheTopOfColumnOrPage = flow.pageLogicalHeightForOffset(line.top) == remainingHeight;
149 if (line.height > remainingHeight || (atTheTopOfColumnOrPage && lineIndex)) {
150 auto lineBreakIndex = computeLineBreakIndex(lineIndex, lineCount, orphans, widows, struts);
151 // Are we still at the top of the column/page?
152 atTheTopOfColumnOrPage = atTheTopOfColumnOrPage ? lineIndex == lineBreakIndex : false;
153 setPageBreakForLine(lineBreakIndex, lines, flow, struts, atTheTopOfColumnOrPage);
154 // Recompute line positions that we already visited but widow break pushed them to a new page.
155 for (auto i = lineBreakIndex; i < lines.size(); ++i)
156 lines.at(i) = computeLineTopAndBottomWithOverflow(flow, i, struts);
157 }
158 ++lineIndex;
159 }
160 simpleLines.setLineStruts(WTFMove(struts));
161}
162
163}
164}
165