1/*
2 * Copyright (C) 2014 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 "SimpleLineLayoutResolver.h"
28
29#include "InlineTextBoxStyle.h"
30#include "RenderBlockFlow.h"
31#include "RenderObject.h"
32#include "SimpleLineLayoutFunctions.h"
33
34namespace WebCore {
35namespace SimpleLineLayout {
36
37static FloatPoint linePosition(float logicalLeft, float logicalTop)
38{
39 return FloatPoint(logicalLeft, roundf(logicalTop));
40}
41
42static FloatSize lineSize(float logicalLeft, float logicalRight, float height)
43{
44 return FloatSize(logicalRight - logicalLeft, height);
45}
46
47RunResolver::Run::Run(const Iterator& iterator)
48 : m_iterator(iterator)
49{
50}
51
52String RunResolver::Run::textWithHyphen() const
53{
54 auto& run = m_iterator.simpleRun();
55 ASSERT(run.hasHyphen);
56 // Empty runs should not have hyphen.
57 ASSERT(run.start < run.end);
58 auto& segment = m_iterator.resolver().m_flowContents.segmentForRun(run.start, run.end);
59 auto text = StringView(segment.text).substring(segment.toSegmentPosition(run.start), run.end - run.start);
60 return makeString(text, m_iterator.resolver().flow().style().hyphenString());
61}
62
63FloatRect RunResolver::Run::rect() const
64{
65 auto& run = m_iterator.simpleRun();
66 auto& resolver = m_iterator.resolver();
67 float baseline = computeBaselinePosition();
68 FloatPoint position = linePosition(run.logicalLeft, baseline - resolver.m_ascent);
69 FloatSize size = lineSize(run.logicalLeft, run.logicalRight, resolver.m_ascent + resolver.m_descent + resolver.m_visualOverflowOffset);
70 bool moveLineBreakToBaseline = false;
71 if (run.start == run.end && m_iterator != resolver.begin() && m_iterator.inQuirksMode()) {
72 auto previousRun = m_iterator;
73 --previousRun;
74 moveLineBreakToBaseline = !previousRun.simpleRun().isEndOfLine;
75 }
76 if (moveLineBreakToBaseline)
77 return FloatRect(FloatPoint(position.x(), baseline), FloatSize(size.width(), std::max<float>(0, resolver.m_ascent - resolver.m_baseline.toFloat())));
78 return FloatRect(position, size);
79}
80
81StringView RunResolver::Run::text() const
82{
83 auto& run = m_iterator.simpleRun();
84 ASSERT(run.start < run.end);
85 auto& segment = m_iterator.resolver().m_flowContents.segmentForRun(run.start, run.end);
86 // We currently split runs on segment boundaries (different RenderObject).
87 ASSERT(run.end <= segment.end);
88 return StringView(segment.text).substring(segment.toSegmentPosition(run.start), run.end - run.start);
89}
90
91const RenderObject& RunResolver::Run::renderer() const
92{
93 auto& run = m_iterator.simpleRun();
94 // FlowContents cannot differentiate empty runs.
95 ASSERT(run.start != run.end);
96 return m_iterator.resolver().m_flowContents.segmentForRun(run.start, run.end).renderer;
97}
98
99unsigned RunResolver::Run::localStart() const
100{
101 auto& run = m_iterator.simpleRun();
102 // FlowContents cannot differentiate empty runs.
103 ASSERT(run.start != run.end);
104 return m_iterator.resolver().m_flowContents.segmentForRun(run.start, run.end).toSegmentPosition(run.start);
105}
106
107unsigned RunResolver::Run::localEnd() const
108{
109 auto& run = m_iterator.simpleRun();
110 // FlowContents cannot differentiate empty runs.
111 ASSERT(run.start != run.end);
112 return m_iterator.resolver().m_flowContents.segmentForRun(run.start, run.end).toSegmentPosition(run.end);
113}
114
115RunResolver::Iterator::Iterator(const RunResolver& resolver, unsigned runIndex, unsigned lineIndex)
116 : m_resolver(resolver)
117 , m_runIndex(runIndex)
118 , m_lineIndex(lineIndex)
119{
120}
121
122RunResolver::Iterator& RunResolver::Iterator::advance()
123{
124 if (simpleRun().isEndOfLine)
125 ++m_lineIndex;
126 ++m_runIndex;
127 return *this;
128}
129
130RunResolver::Iterator& RunResolver::Iterator::advanceLines(unsigned lineCount)
131{
132 unsigned runCount = m_resolver.m_layout.runCount();
133 if (runCount == m_resolver.m_layout.lineCount()) {
134 m_runIndex = std::min(runCount, m_runIndex + lineCount);
135 m_lineIndex = m_runIndex;
136 return *this;
137 }
138 unsigned target = m_lineIndex + lineCount;
139 while (m_lineIndex < target && m_runIndex < runCount)
140 advance();
141
142 return *this;
143}
144
145RunResolver::RunResolver(const RenderBlockFlow& flow, const Layout& layout)
146 : m_flowRenderer(flow)
147 , m_layout(layout)
148 , m_flowContents(flow)
149 , m_lineHeight(lineHeightFromFlow(flow))
150 , m_baseline(baselineFromFlow(flow))
151 , m_borderAndPaddingBefore(flow.borderAndPaddingBefore())
152 , m_ascent(flow.style().fontCascade().fontMetrics().ascent())
153 , m_descent(flow.style().fontCascade().fontMetrics().descent())
154 , m_visualOverflowOffset(visualOverflowForDecorations(flow.style(), nullptr).bottom)
155 , m_inQuirksMode(flow.document().inQuirksMode())
156{
157}
158
159unsigned RunResolver::adjustLineIndexForStruts(LayoutUnit y, IndexType type, unsigned lineIndexCandidate) const
160{
161 auto& struts = m_layout.struts();
162 // We need to offset the lineIndex with line struts when there's an actual strut before the candidate.
163 auto& strut = struts.first();
164 if (strut.lineBreak >= lineIndexCandidate)
165 return lineIndexCandidate;
166 unsigned strutIndex = 0;
167 Optional<unsigned> lastIndexCandidate;
168 auto top = strut.lineBreak * m_lineHeight;
169 auto lineHeightWithOverflow = m_lineHeight;
170 // If font is larger than the line height (glyphs overflow), use the font size when checking line boundaries.
171 if (m_ascent + m_descent > m_lineHeight) {
172 lineHeightWithOverflow = m_ascent + m_descent;
173 top += m_baseline - m_ascent;
174 }
175 auto bottom = top + lineHeightWithOverflow;
176 for (auto lineIndex = strut.lineBreak; lineIndex < m_layout.lineCount(); ++lineIndex) {
177 float strutOffset = 0;
178 if (strutIndex < struts.size() && struts.at(strutIndex).lineBreak == lineIndex)
179 strutOffset = struts.at(strutIndex++).offset;
180 bottom = top + strutOffset + lineHeightWithOverflow;
181 if (y >= top && y < bottom) {
182 if (type == IndexType::First)
183 return lineIndex;
184 lastIndexCandidate = lineIndex;
185 } else if (lastIndexCandidate)
186 return *lastIndexCandidate;
187 top += m_lineHeight + strutOffset;
188 }
189 if (lastIndexCandidate || y >= bottom)
190 return m_layout.lineCount() - 1;
191 // We missed the line.
192 ASSERT_NOT_REACHED();
193 return lineIndexCandidate;
194}
195
196unsigned RunResolver::lineIndexForHeight(LayoutUnit height, IndexType type) const
197{
198 ASSERT(m_lineHeight);
199 float y = height - m_borderAndPaddingBefore;
200 // Lines may overlap, adjust to get the first or last line at this height.
201 auto adjustedY = y;
202 if (type == IndexType::First)
203 adjustedY += m_lineHeight - (m_baseline + m_descent);
204 else
205 adjustedY -= m_baseline - m_ascent;
206 adjustedY = std::max<float>(adjustedY, 0);
207 auto lineIndexCandidate = std::min<unsigned>(adjustedY / m_lineHeight, m_layout.lineCount() - 1);
208 if (m_layout.hasLineStruts())
209 return adjustLineIndexForStruts(y, type, lineIndexCandidate);
210 return lineIndexCandidate;
211}
212
213WTF::IteratorRange<RunResolver::Iterator> RunResolver::rangeForRect(const LayoutRect& rect) const
214{
215 if (!m_lineHeight)
216 return { begin(), end() };
217
218 unsigned firstLine = lineIndexForHeight(rect.y(), IndexType::First);
219 unsigned lastLine = std::max(firstLine, lineIndexForHeight(rect.maxY(), IndexType::Last));
220 auto rangeBegin = begin().advanceLines(firstLine);
221 if (rangeBegin == end())
222 return { end(), end() };
223 auto rangeEnd = rangeBegin;
224 ASSERT(lastLine >= firstLine);
225 rangeEnd.advanceLines(lastLine - firstLine + 1);
226 return { rangeBegin, rangeEnd };
227}
228
229WTF::IteratorRange<RunResolver::Iterator> RunResolver::rangeForLine(unsigned lineIndex) const
230{
231 auto rangeBegin = begin().advanceLines(lineIndex);
232 if (rangeBegin == end())
233 return { end(), end() };
234 auto rangeEnd = rangeBegin;
235 rangeEnd.advanceLines(1);
236 return { rangeBegin, rangeEnd };
237}
238
239WTF::IteratorRange<RunResolver::Iterator> RunResolver::rangeForRenderer(const RenderObject& renderer) const
240{
241 if (begin() == end())
242 return { end(), end() };
243 FlowContents::Iterator segment = m_flowContents.begin();
244 auto run = begin();
245 ASSERT(segment->start <= (*run).start());
246 // Move run to the beginning of the segment.
247 while (&segment->renderer != &renderer && run != end()) {
248 if ((*run).start() == segment->start && (*run).end() == segment->end) {
249 ++run;
250 ++segment;
251 } else if ((*run).start() < segment->end)
252 ++run;
253 else
254 ++segment;
255 ASSERT(segment != m_flowContents.end());
256 }
257 // Do we actually have a run for this renderer?
258 // Collapsed whitespace with dedicated renderer could end up with no run at all.
259 if (run == end() || (segment->start != segment->end && segment->end <= (*run).start()))
260 return { end(), end() };
261
262 auto rangeBegin = run;
263 // Move beyond the end of the segment.
264 while (run != end() && (*run).start() < segment->end)
265 ++run;
266 // Special case when segment == run.
267 if (run == rangeBegin)
268 ++run;
269 return { rangeBegin, run };
270}
271
272RunResolver::Iterator RunResolver::runForPoint(const LayoutPoint& point) const
273{
274 if (!m_lineHeight)
275 return end();
276 if (begin() == end())
277 return end();
278 unsigned lineIndex = lineIndexForHeight(point.y(), IndexType::Last);
279 auto x = point.x() - m_borderAndPaddingBefore;
280 auto it = begin();
281 it.advanceLines(lineIndex);
282 // Point is at the left side of the first run on this line.
283 if ((*it).logicalLeft() > x)
284 return it;
285 // Advance to the first candidate run on this line.
286 while (it != end() && (*it).logicalRight() < x && lineIndex == it.lineIndex())
287 ++it;
288 // We jumped to the next line so the point is at the right side of the previous line.
289 if (it.lineIndex() > lineIndex)
290 return --it;
291 // Now we have a candidate run.
292 // Find the last run that still contains this point (taking overlapping runs with odd word spacing values into account).
293 while (it != end() && (*it).logicalLeft() <= x && lineIndex == it.lineIndex())
294 ++it;
295 return --it;
296}
297
298WTF::IteratorRange<RunResolver::Iterator> RunResolver::rangeForRendererWithOffsets(const RenderObject& renderer, unsigned startOffset, unsigned endOffset) const
299{
300 ASSERT(startOffset <= endOffset);
301 auto range = rangeForRenderer(renderer);
302 auto it = range.begin();
303 // Advance to the firt run with the start offset inside.
304 while (it != range.end() && (*it).end() <= startOffset)
305 ++it;
306 if (it == range.end())
307 return { end(), end() };
308 auto rangeBegin = it;
309 // Special case empty ranges that start at the edge of the run. Apparently normal line layout include those.
310 if (endOffset == startOffset && (*it).start() == endOffset)
311 return { rangeBegin, ++it };
312 // Advance beyond the last run with the end offset.
313 while (it != range.end() && (*it).start() < endOffset)
314 ++it;
315 return { rangeBegin, it };
316}
317
318LineResolver::Iterator::Iterator(RunResolver::Iterator runIterator)
319 : m_runIterator(runIterator)
320{
321}
322
323FloatRect LineResolver::Iterator::operator*() const
324{
325 unsigned currentLine = m_runIterator.lineIndex();
326 auto it = m_runIterator;
327 FloatRect rect = (*it).rect();
328 while (it.advance().lineIndex() == currentLine)
329 rect.unite((*it).rect());
330 return rect;
331}
332
333const RenderObject& LineResolver::Iterator::renderer() const
334{
335 // FIXME: This works as long as we've got only one renderer per line.
336 auto run = *m_runIterator;
337 return m_runIterator.resolver().flowContents().segmentForRun(run.start(), run.end()).renderer;
338}
339
340LineResolver::LineResolver(const RunResolver& runResolver)
341 : m_runResolver(runResolver)
342{
343}
344
345}
346}
347