[LayoutNG] Refactor NGLineBreaker for ShapingLineBreaker

third_party/WebKit/Source/core/layout/ng/inline/ng_line_breaker.cc

Index: third_party/WebKit/Source/core/layout/ng/inline/ng_line_breaker.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/inline/ng_line_breaker.cc b/third_party/WebKit/Source/core/layout/ng/inline/ng_line_breaker.cc
index c922def3ee83bb50eab69d404af2a44f84af82a7..cf900ff9cd1f93577dae8409199f0e8a5519192e 100644
--- a/third_party/WebKit/Source/core/layout/ng/inline/ng_line_breaker.cc
+++ b/third_party/WebKit/Source/core/layout/ng/inline/ng_line_breaker.cc
@@ -4,6 +4,7 @@
 
 #include "core/layout/ng/inline/ng_line_breaker.h"
 
+#include "core/layout/ng/inline/ng_inline_break_token.h"
 #include "core/layout/ng/inline/ng_inline_layout_algorithm.h"
 #include "core/layout/ng/inline/ng_inline_node.h"
 #include "core/layout/ng/inline/ng_text_fragment.h"
@@ -13,85 +14,294 @@
 #include "core/layout/ng/ng_fragment_builder.h"
 #include "core/layout/ng/ng_layout_opportunity_iterator.h"
 #include "core/style/ComputedStyle.h"
+#include "platform/fonts/shaping/HarfBuzzShaper.h"
+#include "platform/fonts/shaping/ShapingLineBreaker.h"
 #include "platform/text/TextBreakIterator.h"
 
 namespace blink {
 
-static bool IsHangable(UChar ch) {
-  return ch == ' ';
-}
+namespace {
 
-void NGLineBreaker::BreakLines(NGInlineLayoutAlgorithm* algorithm,
-                               const String& text_content,
-                               unsigned current_offset) {
-  DCHECK(!text_content.IsEmpty());
-  LazyLineBreakIterator line_break_iterator(text_content, locale_);
-  const unsigned end_offset = text_content.length();
-  while (current_offset < end_offset) {
-    // Find the next break opportunity.
-    int tmp_next_breakable_offset = -1;
-    line_break_iterator.IsBreakable(current_offset + 1,
-                                    tmp_next_breakable_offset);
-    current_offset =
-        tmp_next_breakable_offset >= 0 ? tmp_next_breakable_offset : end_offset;
-    DCHECK_LE(current_offset, end_offset);
-
-    // Advance the break opportunity to the end of hangable characters; e.g.,
-    // spaces.
-    // Unlike the ICU line breaker, LazyLineBreakIterator breaks before
-    // breakable spaces, and expect the line breaker to handle spaces
-    // differently. This logic computes in the ICU way; break after spaces, and
-    // handle spaces as hangable characters.
-    unsigned start_of_hangables = current_offset;
-    while (current_offset < end_offset &&
-           IsHangable(text_content[current_offset]))
-      current_offset++;
-
-    // Set the end to the next break opportunity.
-    algorithm->SetEnd(current_offset);
-
-    // If there are more available spaces, mark the break opportunity and fetch
-    // more text.
-    // TODO(layout-ng): check if the height of the linebox can fit within
-    // the current opportunity.
-    if (algorithm->CanFitOnLine()) {
-      algorithm->SetBreakOpportunity();
-      continue;
+// Use a mock of ShapingLineBreaker for test/debug purposes.
+#define MOCK_SHAPE_LINE
+
+#if defined(MOCK_SHAPE_LINE)
+// The mock for ShapingLineBreaker::ShapeLine().
+// The returned offset > item.StartOffset().
+// - If offset < item.EndOffset() and width <= available_width, the break
+//   opportunity to fit to the available_width is found.
+// - If offset < item.EndOffset() and width > available_width, the first break
+//   opportunity did not fit.
+// - If offset == item.EndOffset() and width <= available_width, the break
+//   opportunity at the end of the item fits.
+// - If offset == item.EndOffset() and width > available_width, the first
+//   break opportunity is at the end of the item but it does not fit.
+// - If offset > item.EndOffset(), the first break opportunity is beyond the
+//   end of item and thus cannot measure. In this case, inline_size shows the
+//   width until the end of the item. It may fit or may not.
+std::pair<unsigned, LayoutUnit> ShapeLineMock(
+    const NGInlineItem& item,
+    unsigned offset,
+    LayoutUnit available_width,
+    const LazyLineBreakIterator& break_iterator) {
+  bool has_break_opportunities = false;
+  LayoutUnit inline_size;
+  while (true) {
+    unsigned next_break = break_iterator.NextBreakOpportunity(offset + 1);
+    LayoutUnit next_inline_size =
+        inline_size +
+        item.InlineSize(offset, std::min(next_break, item.EndOffset()));
+    if (next_inline_size > available_width || next_break >= item.EndOffset()) {
+      if (!has_break_opportunities)
+        return std::make_pair(next_break, next_inline_size);
+      return std::make_pair(offset, inline_size);
     }
+    offset = next_break;
+    inline_size = next_inline_size;
+    has_break_opportunities = true;
+  }
+}
+#endif
+
+LineBreakType GetLineBreakType(const ComputedStyle& style) {
+  if (style.AutoWrap()) {
+    if (style.WordBreak() == kBreakAllWordBreak ||
+        style.WordBreak() == kBreakWordBreak)
+      return LineBreakType::kBreakAll;
+    if (style.WordBreak() == kKeepAllWordBreak)
+      return LineBreakType::kKeepAll;
+  }
+  return LineBreakType::kNormal;
+}
+
+}  // namespace
+
+NGLineBreaker::NGLineBreaker(NGInlineNode* node,
+                             const NGConstraintSpace* space,
+                             NGInlineBreakToken* break_token)
+    : node_(node), constraint_space_(space), item_index_(0), offset_(0) {
+  if (break_token) {
+    item_index_ = break_token->ItemIndex();
+    offset_ = break_token->TextOffset();
+    node->AssertOffset(item_index_, offset_);
+  }
+}
+
+void NGLineBreaker::NextLine(NGInlineItemResults* item_results,
+                             NGInlineLayoutAlgorithm* algorithm) {
+  DCHECK(item_results->IsEmpty());
+  const Vector<NGInlineItem>& items = node_->Items();
+  const String& text = node_->Text();
+  const ComputedStyle& style = node_->Style();
+  LazyLineBreakIterator break_iterator(text, style.LocaleForLineBreakIterator(),
+                                       GetLineBreakType(style));
+#if !defined(MOCK_SHAPE_LINE)
+  HarfBuzzShaper shaper(text.Characters16(), text.length());
+#endif
+  LayoutUnit available_width = algorithm->AvailableWidth();
+  LayoutUnit position;
+  unsigned offset = offset_;
+  unsigned item_index = item_index_;
+  while (item_index < items.size()) {

[ikilpatrick, 2017/05/11 15:55:55]

... move this for loop into NGInlineLayoutAlgorithm::Layout...

this function would just take:

NGLineBreaker::NextLine(const NGLayoutOpportunity&, NGInlineItemResults*
item_results)

the code which does the kAtomicInline, kFloating etc, would move out... and this
would soley just deal with text if that makes sense.

I can also have a shot at doing this next week if this doesn't make sense :)

[kojii, 2017/05/11 16:18:29]

I don't like NGLineBreaker taking NGInlineLayoutAlgorithm as an argument either,
have a TODO comment in local to consider further refactoring.

If possible, I'd like classes for different pipeline stages than for different
target objects. Text and atomic inlines are really the same abstraction for the
line breaking purposes, and line breaker needs to traverse back and forth over a
mix of them in overflow and some other cases. Separating these two makes the
line breaker more complicated. Objects should be abstracted and handled in the
same way as much as possible.

Different pipeline stages I meant, this patch makes NGLineBreaker to own
measuring, so that we can make a single directional pipeline; measure, break,
and build a line. If NGInlineLayoutAlgorithm owns measuring, the flow goes
NGInlineLayoutAlgorithm -> NGLineBreaker -> NGInlineLayoutAlgorithm. This makes
the two classes more tightly coupled.

I'm fine to make yet another class to measure all kind of objects if desired,
but I'm not positive for NGInlineLayoutAlgorithm to own all measuring except for
text.

Currently, floats is preventing the single directional pipeline, because it
requires container builder (build) but affects available width (measure). I need
to study a bit more on floats how to cut this bi-directional dependency.

+    const NGInlineItem& item = items[item_index];
+    item_results->push_back(
+        NGInlineItemResult(item_index, offset, item.EndOffset()));
+    NGInlineItemResult* item_result = &item_results->back();
+
+    // If the start offset is at the item boundary, try to add the entire item.
+    if (offset == item.StartOffset()) {
+      if (item.Type() == NGInlineItem::kText) {
+        item_result->inline_size = item.InlineSize();
+      } else if (item.Type() == NGInlineItem::kAtomicInline) {
+        LayoutAtomicInline(item, item_result);
+      } else if (item.Type() == NGInlineItem::kFloating) {
+        // Floats may change the available width if they fit.
+        algorithm->LayoutAndPositionFloat(position, item.GetLayoutObject());
+        available_width = algorithm->AvailableWidth();
+        DCHECK_LE(position, available_width);
+      } else {
+        offset = item.EndOffset();
+        item_index++;
+        continue;
+      }
+      LayoutUnit next_position = position + item_result->inline_size;
+      if (next_position <= available_width) {
+        offset = item.EndOffset();
+        item_index++;
+        position = next_position;
+        continue;
+      }
 
-    // Compute hangable characters if exists.
-    if (current_offset != start_of_hangables) {
-      algorithm->SetStartOfHangables(start_of_hangables);
-      // If text before hangables can fit, include it in the current line.
-      if (algorithm->CanFitOnLine())
-        algorithm->SetBreakOpportunity();
+      // The entire item does not fit. Handle non-text items as overflow,
+      // since only text item is breakable.
+      if (item.Type() != NGInlineItem::kText) {
+        offset_ = item.EndOffset();
+        item_index_ = item_index + 1;
+        return HandleOverflow(item_results, break_iterator);
+      }
     }
 
-    if (!algorithm->HasBreakOpportunity()) {
-      // The first word (break opportunity) did not fit on the line.
-      // Create a line including items that don't fit, allowing them to
-      // overflow.
-      if (!algorithm->CreateLine())
-        return;
+    // Either the start or the break is in the mid of a text item.
+    DCHECK_EQ(item.Type(), NGInlineItem::kText);
+    DCHECK_LT(offset, item.EndOffset());
+    break_iterator.SetLocale(item.Style()->LocaleForLineBreakIterator());
+    break_iterator.SetBreakType(GetLineBreakType(*item.Style()));
+#if defined(MOCK_SHAPE_LINE)
+    unsigned break_offset;
+    std::tie(break_offset, item_result->inline_size) =
+        ShapeLineMock(item, offset, available_width - position, break_iterator);
+#else
+    // TODO(kojii): Change constructor to take LazyLineBreakIterator.
+    // TODO(kojii): We need to instantiate ShapingLineBreaker here because it
+    // has item-specific info as context. Should they be part of ShapeLine() to
+    // instantiate once, or is this just fine since instatiation is not
+    // expensive?
+    ShapingLineBreaker breaker(&shaper, &item.Style()->GetFont(),
+                               item.TextShapeResult(), item.Style()->Locale(),
+                               LineBreakType::kNormal);
+    // TODO(kojii): Set item.StartOffset/EndOffset() to ShapingLineBreaker, or
+    // change ShapingLineBreaker to take the range from ShapeResult.
+    // item.TextShapeResult() does not have results for outside the item offset
+    // range.
+    unsigned break_offset;
+    item_result->shape_result =
+        breaker.ShapeLine(offset, available_width - position, &break_offset);
+    item_result->inline_size = item_result->shape_result->SnappedWidth();
+#endif
+    DCHECK_GT(break_offset, offset);
+    position += item_result->inline_size;
+
+    // If the break found within the item, break here.
+    if (break_offset < item.EndOffset()) {
+      offset = item_result->end_offset = break_offset;
+      if (position <= available_width)
+        break;
+      // The first break opportunity of the item does not fit.
     } else {
-      if (!algorithm->CreateLineUpToLastBreakOpportunity())
-        return;
-
-      // Items after the last break opportunity were sent to the next line.
-      // Set the break opportunity, or create a line if the word doesn't fit.
-      if (algorithm->HasItems()) {
-        if (algorithm->CanFitOnLine())
-          algorithm->SetBreakOpportunity();
-        else if (!algorithm->CreateLine())
-          return;
-      }
+      // No break opporunity in the item, or the first break opportunity is at
+      // the end of the item. If it fits, continue to the next item.
+      offset = item_result->end_offset = item.EndOffset();
+      item_index++;
+      if (position <= available_width)
+        continue;
     }
+
+    offset_ = offset;
+    item_index_ = item_index;
+    // We need to look at next item if we're overflowing, and the break
+    // opportunity is beyond this item.
+    if (break_offset > item.EndOffset())
+      continue;
+    return HandleOverflow(item_results, break_iterator);
   }
+  offset_ = offset;
+  item_index_ = item_index;
+
+  SkipCollapsibleWhitespaces();
+}
+
+void NGLineBreaker::LayoutAtomicInline(const NGInlineItem& item,
+                                       NGInlineItemResult* item_result) {
+  DCHECK_EQ(item.Type(), NGInlineItem::kAtomicInline);
+  NGBlockNode* node = new NGBlockNode(item.GetLayoutObject());
+  const ComputedStyle& style = node->Style();
+  NGConstraintSpaceBuilder constraint_space_builder(constraint_space_);
+  RefPtr<NGConstraintSpace> constraint_space =
+      constraint_space_builder.SetIsNewFormattingContext(true)
+          .SetIsShrinkToFit(true)
+          .SetTextDirection(style.Direction())
+          .ToConstraintSpace(FromPlatformWritingMode(style.GetWritingMode()));
+  item_result->layout_result = node->Layout(constraint_space.Get());
+
+  item_result->inline_size =
+      NGBoxFragment(constraint_space_->WritingMode(),
+                    ToNGPhysicalBoxFragment(
+                        item_result->layout_result->PhysicalFragment().Get()))
+          .InlineSize();
+}
+
+void NGLineBreaker::HandleOverflow(
+    NGInlineItemResults* item_results,
+    const LazyLineBreakIterator& break_iterator) {
+  // At this point, item_results does not fit into the current line, and
+  // there're no break opportunities in item_results.back().
+
+  // Overflow if there were no break opprtunities to back.
+  unsigned line_start_offset = item_results->front().start_offset;
+  DCHECK_GT(offset_, 0u);
+  unsigned break_offset =
+      break_iterator.PreviousBreakOpportunity(offset_ - 1, line_start_offset);
+  if (!break_offset || break_offset <= line_start_offset)
+    return SkipCollapsibleWhitespaces();
+
+  // Truncate the end of the line to the previous break opportunity.
+  const Vector<NGInlineItem>& items = node_->Items();
+  unsigned new_end = item_results->size();
+  while (true) {
+    NGInlineItemResult* item_result = &(*item_results)[--new_end];
+    if (item_result->start_offset < break_offset) {
+      // The break is at the mid of the item. Adjust the end_offset to the new
+      // break offset.
+      const NGInlineItem& item = items[item_result->item_index];
+      item.AssertEndOffset(break_offset);
+      DCHECK_EQ(item.Type(), NGInlineItem::kText);
+      DCHECK_NE(item_result->end_offset, break_offset);
+      item_result->end_offset = break_offset;
+      item_result->inline_size =
+          item.InlineSize(item_result->start_offset, item_result->end_offset);
+      // TODO(kojii): May need to reshape. Add to ShapingLineBreaker?
+      new_end++;
+      break;
+    }
+    if (item_result->start_offset == break_offset) {
+      // The new break offset is at the item boundary. Remove items up to the
+      // new break offset.
+      // TODO(kojii): Remove open tags as well.
+      break;
+    }
+  }
+  DCHECK_GT(new_end, 0u);
+
+  // TODO(kojii): Should we keep results for the next line? We don't need to
+  // re-layout atomic inlines. Also, processing floats twice is likely a
+  // problematic. Keep floats in this line, or keep it for the next line.
+  item_results->Shrink(new_end);
+
+  // Update the current item index and offset to the new break point.
+  const NGInlineItemResult& last_item_result = item_results->back();
+  offset_ = last_item_result.end_offset;
+  item_index_ = last_item_result.item_index;
+  if (items[item_index_].EndOffset() == offset_)
+    item_index_++;
+}
+
+void NGLineBreaker::SkipCollapsibleWhitespaces() {
+  const Vector<NGInlineItem>& items = node_->Items();
+  if (item_index_ >= items.size())
+    return;
+  const NGInlineItem& item = items[item_index_];
+  if (item.Type() != NGInlineItem::kText || !item.Style()->CollapseWhiteSpace())
+    return;
+  DCHECK_LT(offset_, item.EndOffset());
+
+  // TODO(kojii): When editing, or caret is enabled, trailing spaces at wrap
+  // point should not be removed. For other cases, we can a) remove, b) leave
+  // characters without glyphs, or c) leave both characters and glyphs without
+  // measuring. Need to decide which one works the best.
+  if (node_->Text()[offset_] == kSpaceCharacter) {
+    // Skip one whitespace. Collapsible spaces are collapsed to single space in
+    // NGInlineItemBuilder, so this removes all collapsible spaces.
+    offset_++;
+    if (offset_ == item.EndOffset())
+      item_index_++;
+  }
+}
 
-  // If inline children ended with items left in the line builder, create a line
-  // for them.
-  if (algorithm->HasItems())
-    algorithm->CreateLine();
+RefPtr<NGInlineBreakToken> NGLineBreaker::CreateBreakToken() const {
+  const Vector<NGInlineItem>& items = node_->Items();
+  if (item_index_ >= items.size())
+    return nullptr;
+  return NGInlineBreakToken::Create(node_, item_index_, offset_);
 }
 
 }  // namespace blink