[LayoutNG] Make floats push line boxes down if no break opportunities can fit

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 0c8776b066dfe64117a4a239477a50cb66857c44..bcc114c5831e193b6f06e5d1ef77255ad114b69a 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
@@ -66,14 +66,9 @@ NGLineBreaker::NGLineBreaker(
       constraint_space_(space),
       container_builder_(container_builder),
       unpositioned_floats_(unpositioned_floats),
-      item_index_(0),
-      offset_(0),
       break_iterator_(node.Text()),
       shaper_(node.Text().Characters16(), node.Text().length()),
-      spacing_(node.Text()),
-      auto_wrap_(false),
-      should_create_line_box_(false),
-      is_after_forced_break_(false) {
+      spacing_(node.Text()) {
   if (break_token) {
     item_index_ = break_token->ItemIndex();
     offset_ = break_token->TextOffset();
@@ -99,9 +94,34 @@ bool NGLineBreaker::IsFirstFormattedLine() const {
   return true;
 }
 
+// Initialize internal states for the next line.
+void NGLineBreaker::PrepareNextLine(NGLineInfo* line_info) {
+  NGInlineItemResults* item_results = &line_info->Results();
+  item_results->clear();
+  line_info->SetLineStyle(node_, *constraint_space_, IsFirstFormattedLine(),
+                          line_.is_after_forced_break);
+  SetCurrentStyle(line_info->LineStyle());
+  line_.is_after_forced_break = false;
+  line_.should_create_line_box = false;
+
+  // Use 'text-indent' as the initial position. This lets tab positions to align
+  // regardless of 'text-indent'.
+  line_.position = line_info->TextIndent();
+
+  // We are only able to calculate our available_width if our container has
+  // been positioned in the BFC coordinate space yet.
+  if (container_builder_->BfcOffset())
+    UpdateAvailableWidth();
+  else
+    line_.opportunity.reset();
+}
+
 bool NGLineBreaker::NextLine(NGLineInfo* line_info,
                              const NGLogicalOffset& content_offset) {
   content_offset_ = content_offset;
+
+  PrepareNextLine(line_info);
+
   BreakLine(line_info);
 
   // TODO(kojii): When editing, or caret is enabled, trailing spaces at wrap
@@ -115,7 +135,7 @@ bool NGLineBreaker::NextLine(NGLineInfo* line_info,
 
   // TODO(kojii): There are cases where we need to PlaceItems() without creating
   // line boxes. These cases need to be reviewed.
-  if (should_create_line_box_)
+  if (line_.should_create_line_box)
     ComputeLineLocation(line_info);
 
   return true;
@@ -123,26 +143,9 @@ bool NGLineBreaker::NextLine(NGLineInfo* line_info,
 
 void NGLineBreaker::BreakLine(NGLineInfo* line_info) {
   NGInlineItemResults* item_results = &line_info->Results();
-  item_results->clear();
   const Vector<NGInlineItem>& items = node_.Items();
-  line_info->SetLineStyle(node_, *constraint_space_, IsFirstFormattedLine(),
-                          is_after_forced_break_);
-  SetCurrentStyle(line_info->LineStyle());
-  is_after_forced_break_ = false;
-  should_create_line_box_ = false;
   LineBreakState state = LineBreakState::kNotBreakable;
 
-  // Use 'text-indent' as the initial position. This lets tab positions to align
-  // regardless of 'text-indent'.
-  position_ = line_info->TextIndent();
-
-  // We are only able to calculate our available_width if our container has
-  // been positioned in the BFC coordinate space yet.
-  if (container_builder_->BfcOffset())
-    UpdateAvailableWidth();
-  else
-    opportunity_.reset();
-
   while (item_index_ < items.size()) {
     // CloseTag prohibits to break before.
     const NGInlineItem& item = items[item_index_];
@@ -157,8 +160,8 @@ void NGLineBreaker::BreakLine(NGLineInfo* line_info) {
       line_info->SetIsLastLine(false);
       return;
     }
-    if (state == LineBreakState::kIsBreakable && HasAvailableWidth() &&
-        position_ > AvailableWidth())
+    if (state == LineBreakState::kIsBreakable && line_.HasAvailableWidth() &&
+        !line_.CanFit())
       return HandleOverflow(line_info);
 
     item_results->push_back(
@@ -171,7 +174,7 @@ void NGLineBreaker::BreakLine(NGLineInfo* line_info) {
     } else if (item.Type() == NGInlineItem::kControl) {
       state = HandleControlItem(item, item_result);
       if (state == LineBreakState::kForcedBreak) {
-        is_after_forced_break_ = true;
+        line_.is_after_forced_break = true;
         line_info->SetIsLastLine(true);
         return;
       }
@@ -184,8 +187,8 @@ void NGLineBreaker::BreakLine(NGLineInfo* line_info) {
       MoveToNextOf(item);
     }
   }
-  if (state == LineBreakState::kIsBreakable && HasAvailableWidth() &&
-      position_ > AvailableWidth())
+  if (state == LineBreakState::kIsBreakable && line_.HasAvailableWidth() &&
+      !line_.CanFit())
     return HandleOverflow(line_info);
   line_info->SetIsLastLine(true);
 }
@@ -193,21 +196,50 @@ void NGLineBreaker::BreakLine(NGLineInfo* line_info) {
 // Update the inline size of the first layout opportunity from the given
 // content_offset.
 void NGLineBreaker::UpdateAvailableWidth() {
-  NGLogicalOffset offset = container_builder_->BfcOffset().value();
-  offset += content_offset_;
+  const NGLogicalOffset& bfc_offset = container_builder_->BfcOffset().value();
+  NGLayoutOpportunityIterator iter(constraint_space_->Exclusions().get(),
+                                   constraint_space_->AvailableSize(),
+                                   bfc_offset + content_offset_);
+  line_.opportunity = iter.Next();
+  line_.has_floats_or_exclusions = !iter.IsAtEnd();

[ianjkilpatrick, 2017/07/21 18:18:43]

this variable name is a little misleading for me, its really - 

has_floats_that_are_larger_than_available_inline_size ?

[kojii, 2017/07/23 07:01:10]

No, this flag is about whether it has at least one float/exclusion or not. It
may be larger than available size or smaller.

+
+  // When floats/exclusions occupies the entire line (e.g., float: left; width:
+  // 100%), zero-inline-size opportunities are not included in the iterator.
+  // Instead, the block offset of the first opportunity is pushed down to avoid
+  // such floats/exclusions. Set the line box location to it.

[ianjkilpatrick, 2017/07/21 18:18:43]

so is this approaching it the wrong way? 

Wouldn't we want to create a linebox - just containing the single float, then
enter into the line breaker again for the second line?

Is that difficult to do?

This matches what the first-line selector would do, e.g.
<!DOCTYPE html>
<style>
::first-line { color: blue; }
body { width: 100px; }
#float { width: 100%; float: left; height: 10px; background: red;}
</style>
<p><div id=f></div>This isn't blue.</p>

[kojii, 2017/07/23 07:01:10]

I'm fine either way, I don't see much differences, but doing so runs a bit of
additional code. Any reasons to prefer that?
First-line is an interesting point, but it can probably be done independently
from whether we create an empty line box or not.

It looks like impls don't agree.
http://jsbin.com/bozuhec/edit?html,output
* Gecko doesn't consider the pushed line is first-line
* Edge/Blink/WebKit consider the pushed line is fist-line
I mildly prefer matching to Edge/Blink/WebKit since it's consistent with the
other case in the tests above, but ok to match to Gecko if it's more
preferrable.

Filed https://github.com/w3c/csswg-drafts/issues/1644

+  content_offset_.block_offset =
+      line_.opportunity.value().BlockStartOffset() - bfc_offset.block_offset;
+}
 
+// When no break opportunities can fit in a line that has floats, such a line
+// should be moved down below the floats.
+// Given the minimum required inline size, this function finds such an
+// opporunity and moves |content_offset_.block_offset| down.
+void NGLineBreaker::MoveDownBelowFloats(LayoutUnit min_inline_size) {
+  const NGLogicalOffset& bfc_offset = container_builder_->BfcOffset().value();
   NGLayoutOpportunityIterator iter(constraint_space_->Exclusions().get(),
-                                   constraint_space_->AvailableSize(), offset);
-  opportunity_ = iter.Next();
+                                   constraint_space_->AvailableSize(),
+                                   bfc_offset + content_offset_);
+  while (true) {
+    line_.opportunity = iter.Next();
+    if (iter.IsAtEnd() ||
+        line_.opportunity.value().InlineSize() >= min_inline_size) {
+      line_.has_floats_or_exclusions = !iter.IsAtEnd();
+      content_offset_.block_offset =
+          line_.opportunity.value().BlockStartOffset() -
+          bfc_offset.block_offset;
+      return;
+    }
+  }
 }
 
 void NGLineBreaker::ComputeLineLocation(NGLineInfo* line_info) const {
   // Both NGLayoutOpportunity and BfcOffset are in visual order that
   // "inline-start" are actually "line-left".
   // https://drafts.csswg.org/css-writing-modes-3/#line-left
-  LayoutUnit line_left = opportunity_.value().InlineStartOffset() -
+  LayoutUnit line_left = line_.opportunity.value().InlineStartOffset() -
                          constraint_space_->BfcOffset().inline_offset;
-  line_info->SetLineLocation(line_left, AvailableWidth(),
+  line_info->SetLineLocation(line_left, line_.AvailableWidth(),
                              content_offset_.block_offset);
 }
 
@@ -223,17 +255,17 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleText(
     const NGInlineItem& item,
     NGInlineItemResult* item_result) {
   DCHECK_EQ(item.Type(), NGInlineItem::kText);
-  should_create_line_box_ = true;
+  line_.should_create_line_box = true;
 
-  LayoutUnit available_width = AvailableWidth();
+  LayoutUnit available_width = line_.AvailableWidth();
 
   // If the start offset is at the item boundary, try to add the entire item.
   if (offset_ == item.StartOffset()) {
     item_result->inline_size = item.InlineSize();
-    LayoutUnit next_position = position_ + item_result->inline_size;
+    LayoutUnit next_position = line_.position + item_result->inline_size;
     if (!auto_wrap_ || next_position <= available_width) {
       item_result->shape_result = item.TextShapeResult();
-      position_ = next_position;
+      line_.position = next_position;
       MoveToNextOf(item);
       if (auto_wrap_ && break_iterator_.IsBreakable(item.EndOffset()))
         return LineBreakState::kIsBreakable;
@@ -244,8 +276,8 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleText(
 
   if (auto_wrap_) {
     // Try to break inside of this text item.
-    BreakText(item_result, item, available_width - position_);
-    LayoutUnit next_position = position_ + item_result->inline_size;
+    BreakText(item_result, item, available_width - line_.position);
+    LayoutUnit next_position = line_.position + item_result->inline_size;
     bool is_overflow = next_position > available_width;
 
     // If overflow and no break opportunities exist, and if 'break-word', try to
@@ -254,13 +286,13 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleText(
         IsFirstBreakOpportunity(item_result->end_offset, results)) {
       DCHECK_EQ(break_iterator_.BreakType(), LineBreakType::kNormal);
       break_iterator_.SetBreakType(LineBreakType::kBreakCharacter);
-      BreakText(item_result, item, available_width - position_);
+      BreakText(item_result, item, available_width - line_.position);
       break_iterator_.SetBreakType(LineBreakType::kNormal);
-      next_position = position_ + item_result->inline_size;
+      next_position = line_.position + item_result->inline_size;
       is_overflow = next_position > available_width;
     }
 
-    position_ = next_position;
+    line_.position = next_position;
     item_result->no_break_opportunities_inside = is_overflow;
     if (item_result->end_offset < item.EndOffset()) {
       offset_ = item_result->end_offset;
@@ -280,7 +312,7 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleText(
   DCHECK_EQ(item_result->end_offset, item.EndOffset());
   item_result->no_break_opportunities_inside = true;
   item_result->prohibit_break_after = true;
-  position_ += item_result->inline_size;
+  line_.position += item_result->inline_size;
   MoveToNextOf(item);
   return LineBreakState::kNotBreakable;
 }
@@ -333,7 +365,7 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleControlItem(
     const NGInlineItem& item,
     NGInlineItemResult* item_result) {
   DCHECK_EQ(item.Length(), 1u);
-  should_create_line_box_ = true;
+  line_.should_create_line_box = true;
 
   UChar character = node_.Text()[item.StartOffset()];
   if (character == kNewlineCharacter) {
@@ -344,8 +376,8 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleControlItem(
   DCHECK(item.Style());
   const ComputedStyle& style = *item.Style();
   const Font& font = style.GetFont();
-  item_result->inline_size = font.TabWidth(style.GetTabSize(), position_);
-  position_ += item_result->inline_size;
+  item_result->inline_size = font.TabWidth(style.GetTabSize(), line_.position);
+  line_.position += item_result->inline_size;
   MoveToNextOf(item);
   // TODO(kojii): Implement break around the tab character.
   return LineBreakState::kIsBreakable;
@@ -356,7 +388,7 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleAtomicInline(
     NGInlineItemResult* item_result,
     const NGLineInfo& line_info) {
   DCHECK_EQ(item.Type(), NGInlineItem::kAtomicInline);
-  should_create_line_box_ = true;
+  line_.should_create_line_box = true;
 
   LayoutBox* layout_box = ToLayoutBox(item.GetLayoutObject());
   NGBlockNode node = NGBlockNode(layout_box);
@@ -391,7 +423,7 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleAtomicInline(
                      constraint_space_->WritingMode(), style.Direction());
   item_result->inline_size += item_result->margins.InlineSum();
 
-  position_ += item_result->inline_size;
+  line_.position += item_result->inline_size;
   MoveToNextOf(item);
   if (auto_wrap_)
     return LineBreakState::kIsBreakable;
@@ -417,6 +449,18 @@ NGLineBreaker::LineBreakState NGLineBreaker::HandleAtomicInline(
 // TODO(glebl): Add the support of clearance for inline floats.
 void NGLineBreaker::HandleFloat(const NGInlineItem& item,
                                 NGInlineItemResults* item_results) {
+  // When rewind occurs, an item may be handled multiple times.

[ianjkilpatrick, 2017/07/21 18:18:43]

so, i don't think we want to be able to rewind past a float? I think the logic
we want is:

a) A float will only get placed on the current line if there is room on it.
    We should modify HandleFloat to position a float if it exceeds the inline
size, if its the only thing on that line.
    ^ Should fix this bug?
b) Therefore we should never enter into HandleOverflow after we've placed a
float.
    (There are always break opportunities between floats right?)
    ^ We should add a DCHECK inside of HandleOverflow that we never go back past
a float.
c) This means that we can have a linebox with a single float inside of it (which
seems ok, and matches first-line behaviour?)

[kojii, 2017/07/23 07:01:09]

I'm not following this...we already don't position floats if the float doesn't
fit, no?

The case this CL is trying to fix is when floats fit, but the next word doesn't.
Not common but logically it's still possible. Some tests:
http://jsbin.com/fipovos/edit?html,output

For the flexibility to improve the line breaker quality as we go, I'd like not
to have "unrewindable objects", but this is probably a bit academic wish we may
not appreciate in future, we can ignore this.
As above, I'm ok to have such a linebox, but it doesn't solve all cases (and
first-line behavior is questionable.)

+  // Since floats are put into a separate list, avoid handling same floats
+  // twice.
+  // Ideally rewind can take floats out of floats list, but the difference is
+  // sutble compared to the complexity.
+  if (item_index_ < handled_floats_end_item_index_) {
+    item_results->pop_back();
+    MoveToNextOf(item);
+    return;
+  }
+  handled_floats_end_item_index_ = item_index_ + 1;
+
   NGBlockNode node(ToLayoutBox(item.GetLayoutObject()));
 
   const ComputedStyle& float_style = node.Style();
@@ -439,11 +483,10 @@ void NGLineBreaker::HandleFloat(const NGInlineItem& item,
   // We can only determine if our float will fit if we have an available_width
   // I.e. we may not have come across any text yet, in order to be able to
   // resolve the BFC position.
-  bool float_does_not_fit =
-      (!constraint_space_->FloatsBfcOffset() ||
-       container_builder_->BfcOffset()) &&
-      (!HasAvailableWidth() ||
-       position_ + inline_size + margins.InlineSum() > AvailableWidth());
+  bool float_does_not_fit = (!constraint_space_->FloatsBfcOffset() ||
+                             container_builder_->BfcOffset()) &&
+                            (!line_.HasAvailableWidth() ||
+                             !line_.CanFit(inline_size + margins.InlineSum()));
 
   // Check if we already have a pending float. That's because a float cannot be
   // higher than any block or floated box generated before.
@@ -493,7 +536,7 @@ void NGLineBreaker::HandleOpenTag(const NGInlineItem& item,
                                             constraint_space_->Direction());
       item_result->inline_size = item_result->margins.inline_start +
                                  borders.inline_start + paddings.inline_start;
-      position_ += item_result->inline_size;
+      line_.position += item_result->inline_size;
 
       // While the spec defines "non-zero margins, padding, or borders" prevents
       // line boxes to be zero-height, tests indicate that only inline direction
@@ -501,7 +544,7 @@ void NGLineBreaker::HandleOpenTag(const NGInlineItem& item,
       // Force to create a box, because such inline boxes affect line heights.
       item_result->needs_box_when_empty =
           item_result->inline_size || item_result->margins.inline_start;
-      should_create_line_box_ |= item_result->needs_box_when_empty;
+      line_.should_create_line_box |= item_result->needs_box_when_empty;
     }
   }
   SetCurrentStyle(style);
@@ -521,11 +564,11 @@ void NGLineBreaker::HandleCloseTag(const NGInlineItem& item,
     NGBoxStrut paddings = ComputePadding(*constraint_space_, style);
     item_result->inline_size = item_result->margins.inline_end +
                                borders.inline_end + paddings.inline_end;
-    position_ += item_result->inline_size;
+    line_.position += item_result->inline_size;
 
     item_result->needs_box_when_empty =
         item_result->inline_size || item_result->margins.inline_end;
-    should_create_line_box_ |= item_result->needs_box_when_empty;
+    line_.should_create_line_box |= item_result->needs_box_when_empty;
   }
   DCHECK(item.GetLayoutObject() && item.GetLayoutObject()->Parent());
   SetCurrentStyle(item.GetLayoutObject()->Parent()->StyleRef());
@@ -538,8 +581,8 @@ void NGLineBreaker::HandleCloseTag(const NGInlineItem& item,
 void NGLineBreaker::HandleOverflow(NGLineInfo* line_info) {
   NGInlineItemResults* item_results = &line_info->Results();
   const Vector<NGInlineItem>& items = node_.Items();
-  LayoutUnit available_width = AvailableWidth();
-  LayoutUnit rewind_width = available_width - position_;
+  LayoutUnit available_width = line_.AvailableWidth();
+  LayoutUnit rewind_width = available_width - line_.position;
   DCHECK_LT(rewind_width, 0);
 
   // Search for a break opportunity that can fit.
@@ -595,7 +638,22 @@ void NGLineBreaker::HandleOverflow(NGLineInfo* line_info) {
     }
   }
 
-  // The rewind point did not found, let this line overflow.
+  // Reaching here means that the rewind point was not found.
+
+  // If the current line has floats or exclusions, push this line down below the
+  // floats/exclusions.
+  if (line_.has_floats_or_exclusions) {
+    MoveDownBelowFloats(line_.position);
+    // Moving the line down widened the available width. Need to rewind items
+    // that depend on old available width, but it's not trivial to rewind all
+    // the states. For the simplicity, rewind to the beginning of the line.
+    Rewind(line_info, 0);
+    line_.position = line_info->TextIndent();
+    BreakLine(line_info);
+    return;
+  }
+
+  // Let this line overflow.
   // If there was a break opporunity, the overflow should stop there.
   if (break_before)
     return Rewind(line_info, break_before);
@@ -605,14 +663,25 @@ void NGLineBreaker::HandleOverflow(NGLineInfo* line_info) {
 
 void NGLineBreaker::Rewind(NGLineInfo* line_info, unsigned new_end) {
   NGInlineItemResults* item_results = &line_info->Results();
+  DCHECK_LT(new_end, item_results->size());
+
+  if (new_end) {
+    // Use |results[new_end - 1].end_offset| because it may have been truncated
+    // and may not be equal to |results[new_end].start_offset|.
+    MoveToNextOf((*item_results)[new_end - 1]);
+  } else {
+    // When rewinding all items, use |results[0].start_offset|.
+    const NGInlineItemResult& first_remove = (*item_results)[new_end];
+    item_index_ = first_remove.item_index;
+    offset_ = first_remove.start_offset;
+  }
+
   // TODO(kojii): Should we keep results for the next line? We don't need to
   // re-layout atomic inlines.
   // TODO(kojii): Removing processed floats is likely a problematic. Keep
   // floats in this line, or keep it for the next line.
   item_results->Shrink(new_end);
 
-  MoveToNextOf(item_results->back());
-  DCHECK_LT(item_index_, node_.Items().size());
   line_info->SetIsLastLine(false);
 }