Source/WebCore/ChangeLog

 12015-02-01 Zalan Bujtas <zalan@apple.com>
 2
 3 Simple line layout: use std::upper_bound in splitFragmentToFitLine()
 4 https://bugs.webkit.org/show_bug.cgi?id=141146
 5
 6 Reviewed by NOBODY (OOPS!).
 7
 8 Replace the custom binary search implementation with std::upper_bound and
 9 move splitting functionality to TextFragment.
 10
 11 No change in functionality.
 12
 13 * rendering/SimpleLineLayout.cpp:
 14 (WebCore::SimpleLineLayout::FragmentWidthIterator::FragmentWidthIterator):
 15 (WebCore::SimpleLineLayout::FragmentWidthIterator::operator++):
 16 (WebCore::SimpleLineLayout::FragmentWidthIterator::operator--):
 17 (WebCore::SimpleLineLayout::FragmentWidthIterator::operator==):
 18 (WebCore::SimpleLineLayout::FragmentWidthIterator::operator!=):
 19 (WebCore::SimpleLineLayout::FragmentWidthIterator::operator*):
 20 (WebCore::SimpleLineLayout::begin):
 21 (WebCore::SimpleLineLayout::end):
 22 (WebCore::SimpleLineLayout::splitFragmentToFitLine):
 23 * rendering/SimpleLineLayoutFlowContentsIterator.cpp:
 24 (WebCore::SimpleLineLayout::FlowContentsIterator::runWidth):
 25 * rendering/SimpleLineLayoutFlowContentsIterator.h:
 26 (WebCore::SimpleLineLayout::FlowContentsIterator::TextFragment::split):
 27
1282015-02-02 Darin Adler <darin@apple.com>
229
330 Fix some leaks found by the leak bot

Source/WebCore/rendering/SimpleLineLayout.cpp

@@private:
297297 bool m_firstCharacterFits { false };
298298};
299299
 300class FragmentWidthIterator {
 301public:
 302 typedef std::pair<unsigned, unsigned> WidthRange;
 303 typedef ptrdiff_t difference_type;
 304 typedef WidthRange value_type;
 305 typedef WidthRange* pointer;
 306 typedef WidthRange& reference;
 307 typedef std::forward_iterator_tag iterator_category;
 308
 309 FragmentWidthIterator(const FlowContentsIterator::TextFragment& fragment, unsigned fragmentIndex)
 310 : m_fragment(fragment)
 311 , m_fragmentIndex(fragmentIndex)
 312 {
 313 }
 314
 315 FragmentWidthIterator& operator++()
 316 {
 317 ++m_fragmentIndex;
 318 return *this;
 319 }
 320
 321 FragmentWidthIterator operator++(int)
 322 {
 323 FragmentWidthIterator result(*this);
 324 this->operator++();
 325 return result;
 326 }
 327
 328 FragmentWidthIterator& operator--()
 329 {
 330 --m_fragmentIndex;
 331 return *this;
 332 }
 333
 334 FragmentWidthIterator operator--(int)
 335 {
 336 FragmentWidthIterator result(*this);
 337 this->operator--();
 338 return result;
 339 }
 340
 341 bool operator==(const FragmentWidthIterator& other) const { return m_fragmentIndex == other.m_fragmentIndex; }
 342 bool operator!=(const FragmentWidthIterator& other) const { return !(*this == other); }
 343 const WidthRange operator*() const { return std::make_pair(m_fragment.start(), m_fragmentIndex); }
 344
 345private:
 346 FlowContentsIterator::TextFragment m_fragment;
 347 unsigned m_fragmentIndex { 0 };
 348};
 349
 350static FragmentWidthIterator begin(const FlowContentsIterator::TextFragment& fragment) { return FragmentWidthIterator(fragment, fragment.start()); }
 351static FragmentWidthIterator end(const FlowContentsIterator::TextFragment& fragment) { return FragmentWidthIterator(fragment, fragment.end()); }
 352
300353static bool preWrap(const FlowContentsIterator::Style& style)
301354{
302355 return style.wrapLines && !style.collapseWhitespace;

@@static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line)
330383
331384static FlowContentsIterator::TextFragment splitFragmentToFitLine(FlowContentsIterator::TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const FlowContentsIterator& flowContentsIterator)
332385{
333  // Fast path for single char fragments.
334  if (fragmentToSplit.start() + 1 == fragmentToSplit.end()) {
335  if (keepAtLeastOneCharacter)
336  return FlowContentsIterator::TextFragment();
337 
338  FlowContentsIterator::TextFragment fragmentForNextLine(fragmentToSplit);
339  // Make it empty fragment.
340  fragmentToSplit = FlowContentsIterator::TextFragment(fragmentToSplit.start(), fragmentToSplit.start(), 0, fragmentToSplit.type());
341  return fragmentForNextLine;
342  }
343  // Simple binary search to find out what fits the current line.
344386 // FIXME: add surrogate pair support.
345  unsigned left = fragmentToSplit.start();
346  unsigned right = fragmentToSplit.end() - 1; // We can ignore the last character. It surely does not fit.
347  float width = 0;
348  while (left < right) {
349  unsigned middle = (left + right) / 2;
350  width = flowContentsIterator.textWidth(fragmentToSplit.start(), middle + 1, 0);
351  if (availableWidth > width)
352  left = middle + 1;
353  else if (availableWidth < width)
354  right = middle;
355  else {
356  right = middle + 1;
357  break;
358  }
359  }
360 
361  if (keepAtLeastOneCharacter && right == fragmentToSplit.start())
362  ++right;
363 
364  // Fragment for next line.
365  unsigned nextLineStart = right;
366  unsigned nextLineEnd = fragmentToSplit.end();
367  float nextLineWidth = flowContentsIterator.textWidth(nextLineStart, nextLineEnd, 0);
368 
369  unsigned thisLineStart = fragmentToSplit.start();
370  unsigned thisLineEnd = right;
371  ASSERT(thisLineStart <= thisLineEnd);
372  float thisLineWidth = thisLineStart < thisLineEnd ? flowContentsIterator.textWidth(thisLineStart, thisLineEnd, 0) : 0;
373  fragmentToSplit = FlowContentsIterator::TextFragment(thisLineStart, thisLineEnd, thisLineWidth, fragmentToSplit.type(), fragmentToSplit.isCollapsed(), fragmentToSplit.isBreakable());
374  return FlowContentsIterator::TextFragment(nextLineStart, nextLineEnd, nextLineWidth, fragmentToSplit.type(), fragmentToSplit.isCollapsed(), fragmentToSplit.isBreakable());
 387 auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&](float availableWidth, const FragmentWidthIterator::WidthRange& range) {
 388 // FIXME: use x position instead of 0.
 389 return availableWidth < flowContentsIterator.textWidth(range.first, range.second + 1, 0);
 390 });
 391 unsigned splitPosition = (*it).second;
 392 if (keepAtLeastOneCharacter && splitPosition == fragmentToSplit.start())
 393 ++splitPosition;
 394 return fragmentToSplit.split(splitPosition, flowContentsIterator);
375395}
376396
377397static FlowContentsIterator::TextFragment firstFragment(FlowContentsIterator& flowContentsIterator, const LineState& previousLine)

Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.cpp

@@unsigned FlowContentsIterator::findNextNonWhitespacePosition(unsigned position,
171171template <typename CharacterType>
172172float FlowContentsIterator::runWidth(const String& text, unsigned from, unsigned to, float xPosition) const
173173{
174  ASSERT(from < to);
 174 ASSERT(from <= to);
 175 if (from == to)
 176 return 0;
175177 bool measureWithEndSpace = m_style.collapseWhitespace && to < text.length() && text[to] == ' ';
176178 if (measureWithEndSpace)
177179 ++to;

Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h

@@public:
5959 Type type() const { return m_type; }
6060 bool isCollapsed() const { return m_isCollapsed; }
6161 bool isBreakable() const { return m_isBreakable; }
 62
6263 bool isEmpty() const { return start() == end(); }
 64 TextFragment split(unsigned splitPosition, const FlowContentsIterator&);
6365
6466 private:
6567 unsigned m_start { 0 };

@@private:
103105 unsigned m_position { 0 };
104106};
105107
 108inline FlowContentsIterator::TextFragment FlowContentsIterator::TextFragment::split(unsigned splitPosition, const FlowContentsIterator& flowContentsIterator)
 109{
 110 TextFragment newFragment(*this);
 111
 112 if (splitPosition == end()) {
 113 newFragment.m_start = end();
 114 newFragment.m_width = 0;
 115 newFragment.m_isCollapsed = false;
 116 newFragment.m_isBreakable = false;
 117 return newFragment;
 118 }
 119
 120 if (splitPosition == start()) {
 121 m_end = start();
 122 m_width = 0;
 123 m_isCollapsed = false;
 124 m_isBreakable = false;
 125 return newFragment;
 126 }
 127
 128 m_end = splitPosition;
 129 m_width = flowContentsIterator.textWidth(start(), end(), 0);
 130 bool single = start() + 1 == end();
 131 m_isBreakable = single ? false : m_isBreakable;
 132 m_isCollapsed = single ? false : m_isCollapsed;
 133
 134 newFragment.m_start = splitPosition;
 135 newFragment.m_width = flowContentsIterator.textWidth(newFragment.start(), newFragment.end(), 0);
 136 single = newFragment.start() + 1 == newFragment.end();
 137 newFragment.m_isBreakable = single ? false : newFragment.m_isBreakable;
 138 newFragment.m_isCollapsed = single ? false : newFragment.m_isCollapsed;
 139 return newFragment;
 140}
 141
106142inline UChar FlowContentsIterator::characterAt(unsigned position) const
107143{
108144 auto& segment = m_flowContents.segmentForPosition(position);