[LayoutNG] Add NGInlineBreakToken and back of NGInlineLayoutAlgorithm

third_party/WebKit/Source/core/layout/ng/ng_inline_layout_algorithm.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "core/layout/ng/ng_line_builder.h"
+#include "core/layout/ng/ng_inline_layout_algorithm.h"
 
 #include "core/layout/BidiRun.h"
 #include "core/layout/LayoutBlockFlow.h"
 #include "core/layout/line/LineInfo.h"
 #include "core/layout/line/RootInlineBox.h"
 #include "core/layout/ng/layout_ng_block_flow.h"
 #include "core/layout/ng/ng_bidi_paragraph.h"
 #include "core/layout/ng/ng_block_layout_algorithm.h"
 #include "core/layout/ng/ng_box_fragment.h"
 #include "core/layout/ng/ng_constraint_space.h"
 #include "core/layout/ng/ng_constraint_space_builder.h"
 #include "core/layout/ng/ng_floating_object.h"
 #include "core/layout/ng/ng_floats_utils.h"
 #include "core/layout/ng/ng_fragment_builder.h"
+#include "core/layout/ng/ng_inline_break_token.h"
 #include "core/layout/ng/ng_inline_node.h"
 #include "core/layout/ng/ng_length_utils.h"
 #include "core/layout/ng/ng_line_box_fragment.h"
 #include "core/layout/ng/ng_line_box_fragment_builder.h"
+#include "core/layout/ng/ng_line_breaker.h"
 #include "core/layout/ng/ng_space_utils.h"
 #include "core/layout/ng/ng_text_fragment.h"
 #include "core/layout/ng/ng_text_fragment_builder.h"
 #include "core/style/ComputedStyle.h"
 #include "platform/text/BidiRunList.h"
 
 namespace blink {
 namespace {
 
 RefPtr<NGConstraintSpace> CreateConstraintSpaceForFloat(
@@ skipping 24 matching lines @@
   for (auto& floating_object : builder->UnpositionedFloats()) {
     NGLogicalOffset offset = PositionFloat(origin_point, space->BfcOffset(),
                                            floating_object.get(), space);
     builder->AddFloatingObject(floating_object, offset);
   }
   builder->MutableUnpositionedFloats().clear();
 }
 
 }  // namespace
 
-NGLineBuilder::NGLineBuilder(NGInlineNode* inline_box,
-                             NGConstraintSpace* constraint_space)
+NGInlineLayoutAlgorithm::NGInlineLayoutAlgorithm(
+    NGInlineNode* inline_box,
+    NGConstraintSpace* constraint_space,
+    NGInlineBreakToken* break_token)
     : inline_box_(inline_box),
       constraint_space_(constraint_space),
       container_builder_(NGPhysicalFragment::kFragmentBox, inline_box_),
-      container_layout_result_(nullptr),
       is_horizontal_writing_mode_(
           blink::IsHorizontalWritingMode(constraint_space->WritingMode())),
       space_builder_(constraint_space)
 #if DCHECK_IS_ON()
       ,
       is_bidi_reordered_(false)
 #endif
 {
   if (!is_horizontal_writing_mode_)
     baseline_type_ = FontBaseline::IdeographicBaseline;
+  if (break_token)
+    Initialize(break_token->ItemIndex(), break_token->TextOffset());
+  else
+    Initialize(0, 0);
 }
 
-bool NGLineBuilder::CanFitOnLine() const {
+bool NGInlineLayoutAlgorithm::CanFitOnLine() const {
   LayoutUnit available_size = current_opportunity_.InlineSize();
   if (available_size == NGSizeIndefinite)
     return true;
   return end_position_ <= available_size;
 }
 
-bool NGLineBuilder::HasItems() const {
+bool NGInlineLayoutAlgorithm::HasItems() const {
   return start_offset_ != end_offset_;
 }
 
-bool NGLineBuilder::HasBreakOpportunity() const {
+bool NGInlineLayoutAlgorithm::HasBreakOpportunity() const {
   return start_offset_ != last_break_opportunity_offset_;
 }
 
-bool NGLineBuilder::HasItemsAfterLastBreakOpportunity() const {
+bool NGInlineLayoutAlgorithm::HasItemsAfterLastBreakOpportunity() const {
   return last_break_opportunity_offset_ != end_offset_;
 }
 
-void NGLineBuilder::SetStart(unsigned index, unsigned offset) {
-  inline_box_->AssertOffset(index, offset);
+void NGInlineLayoutAlgorithm::Initialize(unsigned index, unsigned offset) {
+  if (index || offset)
+    inline_box_->AssertOffset(index, offset);
 
   start_index_ = last_index_ = last_break_opportunity_index_ = index;
   start_offset_ = end_offset_ = last_break_opportunity_offset_ = offset;
   end_position_ = last_break_opportunity_position_ = LayoutUnit();
 
   FindNextLayoutOpportunity();
 }
 
-void NGLineBuilder::SetEnd(unsigned new_end_offset) {
+void NGInlineLayoutAlgorithm::SetEnd(unsigned new_end_offset) {
   DCHECK_GT(new_end_offset, end_offset_);
   const Vector<NGLayoutInlineItem>& items = inline_box_->Items();
   DCHECK_LE(new_end_offset, items.back().EndOffset());
 
   // SetEnd() while |new_end_offset| is beyond the current last item.
   unsigned index = last_index_;
   const NGLayoutInlineItem* item = &items[index];
   if (new_end_offset > item->EndOffset()) {
     if (end_offset_ < item->EndOffset()) {
       SetEnd(index, item->EndOffset(),
@@ skipping 11 matching lines @@
 
   // Include closing elements.
   while (new_end_offset == item->EndOffset() && index < items.size() - 1) {
     item = &items[++index];
     if (item->Type() != NGLayoutInlineItem::kCloseTag)
       break;
     SetEnd(index, new_end_offset, InlineSize(*item));
   }
 }
 
-void NGLineBuilder::SetEnd(unsigned index,
-                           unsigned new_end_offset,
-                           LayoutUnit inline_size_since_current_end) {
+void NGInlineLayoutAlgorithm::SetEnd(unsigned index,
+                                     unsigned new_end_offset,
+                                     LayoutUnit inline_size_since_current_end) {
   const Vector<NGLayoutInlineItem>& items = inline_box_->Items();
   DCHECK_LE(new_end_offset, items.back().EndOffset());
 
   // |new_end_offset| should be in the current item or next.
   // TODO(kojii): Reconsider this restriction if needed.
   DCHECK((index == last_index_ && new_end_offset > end_offset_) ||
          (index == last_index_ + 1 && new_end_offset >= end_offset_ &&
           end_offset_ == items[last_index_].EndOffset()));
   const NGLayoutInlineItem& item = items[index];
   item.AssertEndOffset(new_end_offset);
 
   if (item.Type() == NGLayoutInlineItem::kFloating) {
     LayoutAndPositionFloat(
         LayoutUnit(end_position_) + inline_size_since_current_end,
         item.GetLayoutObject());
   }
 
   last_index_ = index;
   end_offset_ = new_end_offset;
   end_position_ += inline_size_since_current_end;
 }
 
-void NGLineBuilder::SetBreakOpportunity() {
+void NGInlineLayoutAlgorithm::SetBreakOpportunity() {
   last_break_opportunity_index_ = last_index_;
   last_break_opportunity_offset_ = end_offset_;
   last_break_opportunity_position_ = end_position_;
 }
 
-void NGLineBuilder::SetStartOfHangables(unsigned offset) {
+void NGInlineLayoutAlgorithm::SetStartOfHangables(unsigned offset) {
   // TODO(kojii): Implement.
 }
 
-LayoutUnit NGLineBuilder::InlineSize(const NGLayoutInlineItem& item) {
+LayoutUnit NGInlineLayoutAlgorithm::InlineSize(const NGLayoutInlineItem& item) {
   if (item.Type() == NGLayoutInlineItem::kAtomicInline)
     return InlineSizeFromLayout(item);
   return item.InlineSize();
 }
 
-LayoutUnit NGLineBuilder::InlineSize(const NGLayoutInlineItem& item,
-                                     unsigned start_offset,
-                                     unsigned end_offset) {
+LayoutUnit NGInlineLayoutAlgorithm::InlineSize(const NGLayoutInlineItem& item,
+                                               unsigned start_offset,
+                                               unsigned end_offset) {
   if (item.StartOffset() == start_offset && item.EndOffset() == end_offset)
     return InlineSize(item);
   return item.InlineSize(start_offset, end_offset);
 }
 
-LayoutUnit NGLineBuilder::InlineSizeFromLayout(const NGLayoutInlineItem& item) {
+LayoutUnit NGInlineLayoutAlgorithm::InlineSizeFromLayout(
+    const NGLayoutInlineItem& item) {
   return NGBoxFragment(ConstraintSpace().WritingMode(),
                        toNGPhysicalBoxFragment(
                            LayoutItem(item)->PhysicalFragment().get()))
       .InlineSize();
 }
 
-const NGLayoutResult* NGLineBuilder::LayoutItem(
+const NGLayoutResult* NGInlineLayoutAlgorithm::LayoutItem(
     const NGLayoutInlineItem& item) {
   // Returns the cached NGLayoutResult if available.
   const Vector<NGLayoutInlineItem>& items = inline_box_->Items();
   if (layout_results_.isEmpty())
     layout_results_.resize(items.size());
   unsigned index = std::distance(items.begin(), &item);
   RefPtr<NGLayoutResult>* layout_result = &layout_results_[index];
   if (*layout_result)
     return layout_result->get();
 
   DCHECK(item.Type() == NGLayoutInlineItem::kAtomicInline);
   NGBlockNode* node = new NGBlockNode(item.GetLayoutObject());
   // TODO(kojii): Keep node in NGLayoutInlineItem.
   const ComputedStyle& style = node->Style();
   NGConstraintSpaceBuilder constraint_space_builder(&ConstraintSpace());
   RefPtr<NGConstraintSpace> constraint_space =
       constraint_space_builder.SetIsNewFormattingContext(true)
           .SetIsShrinkToFit(true)
           .SetTextDirection(style.direction())
           .ToConstraintSpace(FromPlatformWritingMode(style.getWritingMode()));
   *layout_result = node->Layout(constraint_space.get());
   return layout_result->get();
 }
 
-void NGLineBuilder::CreateLine() {
+bool NGInlineLayoutAlgorithm::CreateLine() {
   if (HasItemsAfterLastBreakOpportunity())
     SetBreakOpportunity();
-  CreateLineUpToLastBreakOpportunity();
+  return CreateLineUpToLastBreakOpportunity();
 }
 
-void NGLineBuilder::CreateLineUpToLastBreakOpportunity() {
+bool NGInlineLayoutAlgorithm::CreateLineUpToLastBreakOpportunity() {
   const Vector<NGLayoutInlineItem>& items = inline_box_->Items();
 
   // Create a list of LineItemChunk from |start| and |last_break_opportunity|.
   // TODO(kojii): Consider refactoring LineItemChunk once NGLineBuilder's public
   // API is more finalized. It does not fit well with the current API.
   Vector<LineItemChunk, 32> line_item_chunks;
   unsigned start_offset = start_offset_;
   for (unsigned i = start_index_; i <= last_break_opportunity_index_; i++) {
     const NGLayoutInlineItem& item = items[i];
     unsigned end_offset =
         std::min(item.EndOffset(), last_break_opportunity_offset_);
     line_item_chunks.push_back(
         LineItemChunk{i, start_offset, end_offset,
                       InlineSize(item, start_offset, end_offset)});
     start_offset = end_offset;
   }
 
   if (inline_box_->IsBidiEnabled())
     BidiReorder(&line_item_chunks);
 
-  PlaceItems(line_item_chunks);
+  if (!PlaceItems(line_item_chunks))
+    return false;
 
   // Prepare for the next line.
   // Move |start| to |last_break_opportunity|, keeping items after
   // |last_break_opportunity|.
   start_index_ = last_break_opportunity_index_;
   start_offset_ = last_break_opportunity_offset_;
   DCHECK_GE(end_position_, last_break_opportunity_position_);
   end_position_ -= last_break_opportunity_position_;
   last_break_opportunity_position_ = LayoutUnit();
 #if DCHECK_IS_ON()
   is_bidi_reordered_ = false;
 #endif
 
   NGLogicalOffset origin_point =
       GetOriginPointForFloats(ConstraintSpace(), content_size_);
   PositionPendingFloats(origin_point, constraint_space_, &container_builder_);
   FindNextLayoutOpportunity();
+  return true;
 }
 
-void NGLineBuilder::BidiReorder(Vector<LineItemChunk, 32>* line_item_chunks) {
+void NGInlineLayoutAlgorithm::BidiReorder(
+    Vector<LineItemChunk, 32>* line_item_chunks) {
 #if DCHECK_IS_ON()
   DCHECK(!is_bidi_reordered_);
   is_bidi_reordered_ = true;
 #endif
 
   // TODO(kojii): UAX#9 L1 is not supported yet. Supporting L1 may change
   // embedding levels of parts of runs, which requires to split items.
   // http://unicode.org/reports/tr9/#L1
   // BidiResolver does not support L1 crbug.com/316409.
 
@@ skipping 14 matching lines @@
   for (unsigned visual_index = 0; visual_index < indices_in_visual_order.size();
        visual_index++) {
     unsigned logical_index = indices_in_visual_order[visual_index];
     line_item_chunks_in_visual_order[visual_index] =
         (*line_item_chunks)[logical_index];
   }
   line_item_chunks->swap(line_item_chunks_in_visual_order);
 }
 
 // TODO(glebl): Add the support of clearance for inline floats.
-void NGLineBuilder::LayoutAndPositionFloat(LayoutUnit end_position,
-                                           LayoutObject* layout_object) {
+void NGInlineLayoutAlgorithm::LayoutAndPositionFloat(
+    LayoutUnit end_position,
+    LayoutObject* layout_object) {
   NGBlockNode* node = new NGBlockNode(layout_object);
+
   RefPtr<NGConstraintSpace> float_space = CreateConstraintSpaceForFloat(
       node->Style(), ConstraintSpace(), &space_builder_);
 
   // TODO(glebl): add the fragmentation support:
   // same writing mode - get the inline size ComputeInlineSizeForFragment to
   // determine if it fits on this line, then perform layout with the correct
   // fragmentation line.
   // diff writing mode - get the inline size from performing layout.
   RefPtr<NGLayoutResult> layout_result = node->Layout(float_space.get());
 
@@ skipping 16 matching lines @@
     NGLogicalOffset origin_point =
         GetOriginPointForFloats(ConstraintSpace(), content_size_);
     NGLogicalOffset offset =
         PositionFloat(origin_point, constraint_space_->BfcOffset(),
                       floating_object.get(), constraint_space_);
     container_builder_.AddFloatingObject(floating_object, offset);
     FindNextLayoutOpportunity();
   }
 }
 
-void NGLineBuilder::PlaceItems(
+bool NGInlineLayoutAlgorithm::PlaceItems(
     const Vector<LineItemChunk, 32>& line_item_chunks) {
   const Vector<NGLayoutInlineItem>& items = inline_box_->Items();
 
   NGLineBoxFragmentBuilder line_box(inline_box_);
   NGTextFragmentBuilder text_builder(inline_box_);
 
   // Accumulate a "strut"; a zero-width inline box with the element's font and
   // line height properties. https://drafts.csswg.org/css2/visudet.html#strut
   NGLineHeightMetrics block_metrics(inline_box_->Style(), baseline_type_);
   line_box.UniteMetrics(block_metrics);
@@ skipping 56 matching lines @@
 
     NGLogicalOffset logical_offset(
         inline_size + current_opportunity_.InlineStartOffset() -
             ConstraintSpace().BfcOffset().inline_offset,
         block_start);
     line_box.AddChild(std::move(text_fragment), logical_offset);
     inline_size += line_item_chunk.inline_size;
   }
 
   if (line_box.Children().isEmpty()) {
-    // The line was empty.
-    return;
+    return true;  // The line was empty.
+  }
+
+  // Check if the line fits into the constraint space in block direction.
+  LayoutUnit block_end = content_size_ + line_box.Metrics().LineHeight();
+  if (!container_builder_.Children().isEmpty() &&
+      ConstraintSpace().AvailableSize().block_size != NGSizeIndefinite &&
+      block_end > ConstraintSpace().AvailableSize().block_size) {
+    return false;
   }
 
   // If the estimated baseline position was not the actual position, move all
   // fragments in the block direction.
   LayoutUnit adjust_baseline(line_box.Metrics().ascent_and_leading -
                              block_metrics.ascent_and_leading);
   if (adjust_baseline)
     line_box.MoveChildrenInBlockDirection(adjust_baseline);
 
+  // If there are more content to consume, create an unfinished break token.
+  if (last_break_opportunity_index_ != items.size() - 1 ||
+      last_break_opportunity_offset_ != inline_box_->Text().length()) {
+    line_box.SetBreakToken(
+        NGInlineBreakToken::create(inline_box_, last_break_opportunity_index_,
+                                   last_break_opportunity_offset_));
+  }
+
   line_box.SetInlineSize(inline_size);
-  NGLogicalOffset offset(LayoutUnit(), content_size_);
-  container_builder_.AddChild(line_box.ToLineBoxFragment(), offset);
+  container_builder_.AddChild(line_box.ToLineBoxFragment(),
+                              {LayoutUnit(), content_size_});
+
   max_inline_size_ = std::max(max_inline_size_, inline_size);
-  content_size_ += line_box.Metrics().LineHeight();
+  content_size_ = block_end;
+  return true;
 }
 
-void NGLineBuilder::AccumulateUsedFonts(const NGLayoutInlineItem& item,
-                                        const LineItemChunk& line_item_chunk,
-                                        NGLineBoxFragmentBuilder* line_box) {
+void NGInlineLayoutAlgorithm::AccumulateUsedFonts(
+    const NGLayoutInlineItem& item,
+    const LineItemChunk& line_item_chunk,
+    NGLineBoxFragmentBuilder* line_box) {
   HashSet<const SimpleFontData*> fallback_fonts;
   item.GetFallbackFonts(&fallback_fonts, line_item_chunk.start_offset,
                         line_item_chunk.end_offset);
   for (const auto& fallback_font : fallback_fonts) {
     NGLineHeightMetrics metrics(fallback_font->getFontMetrics(),
                                 baseline_type_);
     line_box->UniteMetrics(metrics);
   }
 }
 
-LayoutUnit NGLineBuilder::PlaceAtomicInline(
+LayoutUnit NGInlineLayoutAlgorithm::PlaceAtomicInline(
     const NGLayoutInlineItem& item,
     LayoutUnit estimated_baseline,
     NGLineBoxFragmentBuilder* line_box,
     NGTextFragmentBuilder* text_builder) {
   NGBoxFragment fragment(
       ConstraintSpace().WritingMode(),
       toNGPhysicalBoxFragment(LayoutItem(item)->PhysicalFragment().get()));
   // TODO(kojii): Margin and border in block progression not implemented yet.
   LayoutUnit block_size = fragment.BlockSize();
 
@@ skipping 16 matching lines @@
   metrics.ascent_and_leading = baseline_offset;
   metrics.descent_and_leading = block_size - baseline_offset;
   line_box->UniteMetrics(metrics);
 
   // TODO(kojii): Figure out what to do with OOF in NGLayoutResult.
   // Floats are ok because atomic inlines are BFC?
 
   return block_start;
 }
 
-void NGLineBuilder::FindNextLayoutOpportunity() {
+void NGInlineLayoutAlgorithm::FindNextLayoutOpportunity() {
   NGLogicalOffset iter_offset = constraint_space_->BfcOffset();
   iter_offset.block_offset += content_size_;
   auto* iter = constraint_space_->LayoutOpportunityIterator(iter_offset);
   NGLayoutOpportunity opportunity = iter->Next();
   if (!opportunity.IsEmpty())
     current_opportunity_ = opportunity;
 }
 
-RefPtr<NGLayoutResult> NGLineBuilder::CreateFragments() {
-  DCHECK(!HasItems()) << "Must call CreateLine()";
+RefPtr<NGLayoutResult> NGInlineLayoutAlgorithm::Layout() {
+  if (!inline_box_->Text().isEmpty())
+    NGLineBreaker().BreakLines(this, inline_box_->Text(), start_offset_);
 
   // TODO(kojii): Check if the line box width should be content or available.
-  // TODO(kojii): Need to take constraint_space into account.
   container_builder_.SetInlineSize(max_inline_size_)
       .SetInlineOverflow(max_inline_size_)
       .SetBlockSize(content_size_)
       .SetBlockOverflow(content_size_);
 
-  container_layout_result_ = container_builder_.ToBoxFragment();
-  return container_layout_result_;
+  return container_builder_.ToBoxFragment();
 }
 
-void NGLineBuilder::CopyFragmentDataToLayoutBlockFlow() {
+MinMaxContentSize NGInlineLayoutAlgorithm::ComputeMinMaxContentSizeByLayout() {
+  DCHECK(ConstraintSpace().AvailableSize().inline_size == LayoutUnit() &&
+         ConstraintSpace().AvailableSize().block_size == NGSizeIndefinite);
+  if (!inline_box_->Text().isEmpty())
+    NGLineBreaker().BreakLines(this, inline_box_->Text(), start_offset_);
+  MinMaxContentSize sizes;
+  sizes.min_content = MaxInlineSize();
+
+  // max-content is the width without any line wrapping.
+  // TODO(kojii): Implement hard breaks (<br> etc.) to break.
+  for (const auto& item : inline_box_->Items())
+    sizes.max_content += InlineSize(item);
+
+  return sizes;
+}
+
+void NGInlineLayoutAlgorithm::CopyFragmentDataToLayoutBlockFlow(
+    NGLayoutResult* layout_result) {
   LayoutBlockFlow* block = inline_box_->GetLayoutBlockFlow();
   block->deleteLineBoxTree();
 
   Vector<NGLayoutInlineItem>& items = inline_box_->Items();
   Vector<unsigned, 32> text_offsets(items.size());
   inline_box_->GetLayoutTextOffsets(&text_offsets);
 
   Vector<const NGPhysicalFragment*, 32> fragments_for_bidi_runs;
   fragments_for_bidi_runs.reserveInitialCapacity(items.size());
   BidiRunList<BidiRun> bidi_runs;
   LineInfo line_info;
-  NGPhysicalBoxFragment* box_fragment = toNGPhysicalBoxFragment(
-      container_layout_result_->PhysicalFragment().get());
+  NGPhysicalBoxFragment* box_fragment =
+      toNGPhysicalBoxFragment(layout_result->PhysicalFragment().get());
   for (const auto& container_child : box_fragment->Children()) {
     NGPhysicalLineBoxFragment* physical_line_box =
         toNGPhysicalLineBoxFragment(container_child.get());
     // Create a BidiRunList for this line.
     for (const auto& line_child : physical_line_box->Children()) {
       const auto* text_fragment = toNGPhysicalTextFragment(line_child.get());
       const NGLayoutInlineItem& item = items[text_fragment->ItemIndex()];
       BidiRun* run;
       if (item.Type() == NGLayoutInlineItem::kText) {
         LayoutObject* layout_object = item.GetLayoutObject();
@@ skipping 54 matching lines @@
     root_line_box->setLineTopBottomPositions(
         baseline - LayoutUnit(metrics.ascent),
         baseline + LayoutUnit(metrics.descent), line_top_with_leading,
         baseline + LayoutUnit(metrics.descent_and_leading));
 
     bidi_runs.deleteRuns();
     fragments_for_bidi_runs.clear();
   }
 }
 }  // namespace blink