[LayoutNG] A different approach to multi-col.

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

Index: third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc b/third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
index 0d92903cecd8964f77c6475e0d1b1b696c4b49fb..181a529cd99deb47fc1e85b3e968b5271a925f99 100644
--- a/third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
+++ b/third_party/WebKit/Source/core/layout/ng/ng_block_layout_algorithm.cc
@@ -300,18 +300,17 @@ bool IsNewFormattingContextForInFlowBlockLevelChild(
 }  // namespace
 
 NGBlockLayoutAlgorithm::NGBlockLayoutAlgorithm(
-    LayoutObject* layout_object,
-    PassRefPtr<const ComputedStyle> style,
-    NGLayoutInputNode* first_child,
+    NGBlockNode* node,
     NGConstraintSpace* constraint_space,
-    NGBreakToken* break_token)
-    : style_(style),
-      first_child_(first_child),
+    NGBlockBreakToken* break_token)
+    : style_(node->Style()),
+      first_child_(node->FirstChild()),
       constraint_space_(constraint_space),
       break_token_(break_token),
       builder_(WTF::wrapUnique(
-          new NGFragmentBuilder(NGPhysicalFragment::kFragmentBox,
-                                layout_object))) {
+          new NGFragmentBuilder(NGPhysicalFragment::kFragmentBox, node))),
+      child_iterator_(WTF::wrapUnique(
+          new NGBlockLayoutChildIterator(first_child_, break_token))) {
   DCHECK(style_);
 }
 
@@ -364,6 +363,7 @@ RefPtr<NGPhysicalFragment> NGBlockLayoutAlgorithm::Layout() {
   if (NeedMinAndMaxContentSizes(ConstraintSpace(), Style()))
     sizes = ComputeMinAndMaxContentSizes();
 
+  // TODO(ikilpatrick): should be no borders or padding if anon.
   border_and_padding_ =
       ComputeBorders(Style()) + ComputePadding(ConstraintSpace(), Style());
 
@@ -383,34 +383,21 @@ RefPtr<NGPhysicalFragment> NGBlockLayoutAlgorithm::Layout() {
     adjusted_block_size -= border_and_padding_.BlockSum();
 
   space_builder_ = new NGConstraintSpaceBuilder(constraint_space_);
-  if (Style().specifiesColumns()) {
-    space_builder_->SetFragmentationType(kFragmentColumn);
-    adjusted_inline_size =
-        ResolveUsedColumnInlineSize(adjusted_inline_size, Style());
-    LayoutUnit inline_progression =
-        adjusted_inline_size + ResolveUsedColumnGap(Style());
-    fragmentainer_mapper_ =
-        new NGColumnMapper(inline_progression, adjusted_block_size);
-  }
-  space_builder_->SetAvailableSize(
-      NGLogicalSize(adjusted_inline_size, adjusted_block_size));
-  space_builder_->SetPercentageResolutionSize(
-      NGLogicalSize(adjusted_inline_size, adjusted_block_size));
+  space_builder_
+      ->SetAvailableSize(
+          NGLogicalSize(adjusted_inline_size, adjusted_block_size))
+      .SetPercentageResolutionSize(
+          NGLogicalSize(adjusted_inline_size, adjusted_block_size));
 
   builder_->SetDirection(constraint_space_->Direction());
   builder_->SetWritingMode(constraint_space_->WritingMode());
   builder_->SetInlineSize(inline_size).SetBlockSize(block_size);
 
-  // TODO(glebl): fix multicol after the new margin collapsing/floats algorithm
-  // based on BFCOffset is checked in.
-  if (NGBlockBreakToken* token = CurrentBlockBreakToken()) {
-    // Resume after a previous break.
-    content_size_ = token->BreakOffset();
-    current_child_ = token->InputNode();
-  } else {
-    content_size_ = border_and_padding_.block_start;
-    current_child_ = first_child_;
-  }
+  std::tie(current_child_, current_child_break_token_) =
+      child_iterator_->NextChild();
+
+  content_size_ =
+      break_token_ ? LayoutUnit(0) : border_and_padding_.block_start;

[mstensho (USE GERRIT), 2017/02/15 21:12:22]

Should use LayoutUnit() instead of LayoutUnit(0), or you end up performing
checks for saturated arithmetics.

 
   curr_margin_strut_ = ConstraintSpace().MarginStrut();
   curr_bfc_offset_ = ConstraintSpace().BfcOffset();
@@ -438,8 +425,6 @@ RefPtr<NGPhysicalFragment> NGBlockLayoutAlgorithm::Layout() {
       }
     }
 
-    DCHECK(!ConstraintSpace().HasBlockFragmentation() ||
-           SpaceAvailableForCurrentChild() > LayoutUnit());
     space_for_current_child_ = CreateConstraintSpaceForCurrentChild();
 
     if (current_child_->Type() == NGLayoutInputNode::kLegacyInline) {
@@ -508,7 +493,7 @@ void NGBlockLayoutAlgorithm::LayoutInlineChildren(NGInlineNode* current_child) {
   current_child->LayoutInline(space_for_current_child_, &line_builder);
   // TODO(kojii): The wrapper fragment should not be needed.
   NGFragmentBuilder wrapper_fragment_builder(NGPhysicalFragment::kFragmentBox,
-                                             current_child->GetLayoutObject());
+                                             current_child);
   line_builder.CreateFragments(&wrapper_fragment_builder);
   RefPtr<NGPhysicalBoxFragment> child_fragment =
       wrapper_fragment_builder.ToBoxFragment();
@@ -568,11 +553,6 @@ void NGBlockLayoutAlgorithm::FinishCurrentChildLayout(
   }
   NGLogicalOffset logical_offset = CalculateLogicalOffset(bfc_offset);
 
-  if (fragmentainer_mapper_)
-    fragmentainer_mapper_->ToVisualOffset(logical_offset);

[mstensho (USE GERRIT), 2017/02/15 21:12:22]

Is the plan to replace the fragmentainer mapper with something else? It might be
viable to cram all its logic into the column layout algorithm, now that we do
have a dedicated algorithm for multicol.

[ikilpatrick, 2017/02/16 16:48:31]

Yeah i think most of the logic inside the fragmentainer mapper could just live
inside the column layout algorithm now... the NGColumnLayoutAlgorithm should
just deal with:
1) Performing the initial layout pass & determining fragmentation lines.
2) Performing layout and placement of each column.
3) Performing layout and placement of each spanner. (which bubble up to their
parent NGColumnLayoutAlgorithm).

I think this should be pretty small to live in one class, but happy to split out
if that isn't the case.

-  else
-    logical_offset.block_offset -= PreviousBreakOffset();
-
   // Update margin strut.
   curr_margin_strut_ = fragment.EndMarginStrut();
   curr_margin_strut_.Append(curr_child_margins_.block_end);
@@ -589,146 +569,63 @@ void NGBlockLayoutAlgorithm::FinishCurrentChildLayout(
 bool NGBlockLayoutAlgorithm::ProceedToNextUnfinishedSibling(
     NGPhysicalFragment* child_fragment) {
   DCHECK(current_child_);
-  NGBlockNode* finished_child = toNGBlockNode(current_child_);
-  current_child_ = current_child_->NextSibling();
-  if (!ConstraintSpace().HasBlockFragmentation() && !fragmentainer_mapper_)
-    return true;
-  // If we're resuming layout after a fragmentainer break, we need to skip
-  // siblings that we're done with. We may have been able to fully lay out some
-  // node(s) preceding a node that we had to break inside (and therefore were
-  // not able to fully lay out). This happens when we have parallel flows [1],
-  // which are caused by floats, overflow, etc.
-  //
-  // [1] https://drafts.csswg.org/css-break/#parallel-flows
-  if (CurrentBlockBreakToken()) {
-    // TODO(layout-ng): Figure out if we need a better way to determine if the
-    // node is finished. Maybe something to encode in a break token?
-    // TODO(kojii): Handle inline children.
-    while (current_child_ &&
-           current_child_->Type() == NGLayoutInputNode::kLegacyBlock &&
-           toNGBlockNode(current_child_)->IsLayoutFinished()) {
-      current_child_ = current_child_->NextSibling();
-    }
-  }
-  LayoutUnit break_offset = NextBreakOffset();
-  bool is_out_of_space = content_size_ - PreviousBreakOffset() >= break_offset;
-  if (!HasPendingBreakToken()) {
-    bool child_broke = child_fragment->BreakToken();
-    // This block needs to break if the child broke, or if we're out of space
-    // and there's more content waiting to be laid out. Otherwise, just bail
-    // now.
-    if (!child_broke && (!is_out_of_space || !current_child_))
-      return true;
-    // Prepare a break token for this block, so that we know where to resume
-    // when the time comes for that. We may not be able to abort layout of this
-    // block right away, due to the posibility of parallel flows. We can only
-    // abort when we're out of space, or when there are no siblings left to
-    // process.
-    NGBlockBreakToken* token;
-    if (child_broke) {
-      // The child we just laid out was the first one to break. So that is
-      // where we need to resume.
-      token = new NGBlockBreakToken(finished_child, break_offset);
-    } else {
-      // Resume layout at the next sibling that needs layout.
-      DCHECK(current_child_);
-      token =
-          new NGBlockBreakToken(toNGBlockNode(current_child_), break_offset);
-    }
-    SetPendingBreakToken(token);
-  }
-
-  if (!fragmentainer_mapper_) {
-    if (!is_out_of_space)
-      return true;
-    // We have run out of space in this flow, so there's no work left to do for
-    // this block in this fragmentainer. We should finalize the fragment and get
-    // back to the remaining content when laying out the next fragmentainer(s).
+  std::tie(current_child_, current_child_break_token_) =
+      child_iterator_->NextChild();
+
+  bool is_out_of_space =
+      constraint_space_->HasBlockFragmentation()
+          ? content_size_ >= constraint_space_->FragmentainerSpaceAvailable()

[mstensho (USE GERRIT), 2017/02/15 21:12:22]

All you need is: constraint_space_->HasBlockFragmentation() && content_size_ >=
constraint_space_->FragmentainerSpaceAvailable()

+          : false;
+
+  // We have run out of space in this flow, so there's no work left to do for
+  // this block in this fragmentainer. We should finalize the fragment and get
+  // back to the remaining content when laying out the next fragmentainer(s).
+  if (is_out_of_space)
     return false;
-  }
 
-  if (is_out_of_space || !current_child_) {
-    NGBlockBreakToken* token = fragmentainer_mapper_->Advance();
-    DCHECK(token || !is_out_of_space);
-    if (token) {
-      break_token_ = token;
-      content_size_ = token->BreakOffset();
-      current_child_ = token->InputNode();
-    }
-  }
-  return true;
+  return current_child_;
 }
 
-void NGBlockLayoutAlgorithm::SetPendingBreakToken(NGBlockBreakToken* token) {
-  if (fragmentainer_mapper_)
-    fragmentainer_mapper_->SetBreakToken(token);
-  else
-    builder_->SetBreakToken(token);
-}
+void NGBlockLayoutAlgorithm::FinalizeForFragmentation() {
+  LayoutUnit used_block_size =
+      break_token_ ? break_token_->UsedBlockSize() : LayoutUnit();
+  LayoutUnit block_size = ComputeBlockSizeForFragment(
+      ConstraintSpace(), Style(), used_block_size + content_size_);
 
-bool NGBlockLayoutAlgorithm::HasPendingBreakToken() const {
-  if (fragmentainer_mapper_)
-    return fragmentainer_mapper_->HasBreakToken();
-  return builder_->HasBreakToken();
-}
+  if (!block_size)
+    return;
 
-void NGBlockLayoutAlgorithm::FinalizeForFragmentation() {
-  LayoutUnit block_size =
-      ComputeBlockSizeForFragment(ConstraintSpace(), Style(), content_size_);
-  LayoutUnit previous_break_offset = PreviousBreakOffset();
-  block_size -= previous_break_offset;
-  block_size = std::max(LayoutUnit(), block_size);
-  LayoutUnit space_left = ConstraintSpace().FragmentainerSpaceAvailable();
+  block_size -= used_block_size;
+  DCHECK_GE(block_size, LayoutUnit());
+
+  // This is relative to the bfc offset, we should have this if non-zero block
+  // size.
+  DCHECK(builder_->BfcOffset());
+  LayoutUnit space_left = ConstraintSpace().FragmentainerSpaceAvailable() -
+                          builder_->BfcOffset().value().block_offset;
   DCHECK_GE(space_left, LayoutUnit());
-  if (builder_->HasBreakToken()) {
+
+  if (builder_->DidBreak()) {
     // A break token is ready, which means that we're going to break
     // before or inside a block-level child.
+    builder_->SetUsedBlockSize(std::min(space_left, block_size) +
+                               used_block_size);
     builder_->SetBlockSize(std::min(space_left, block_size));
     builder_->SetBlockOverflow(space_left);
     return;
   }
+
   if (block_size > space_left) {
     // Need a break inside this block.
-    builder_->SetBreakToken(new NGBlockBreakToken(nullptr, NextBreakOffset()));
+    builder_->SetUsedBlockSize(space_left + used_block_size);
     builder_->SetBlockSize(space_left);
     builder_->SetBlockOverflow(space_left);
     return;
   }
+
   // The end of the block fits in the current fragmentainer.
   builder_->SetBlockSize(block_size);
-  builder_->SetBlockOverflow(content_size_ - previous_break_offset);
-}
-
-NGBlockBreakToken* NGBlockLayoutAlgorithm::CurrentBlockBreakToken() const {
-  NGBreakToken* token = break_token_;
-  if (!token || token->Type() != NGBreakToken::kBlockBreakToken)
-    return nullptr;
-  return toNGBlockBreakToken(token);
-}
-
-LayoutUnit NGBlockLayoutAlgorithm::PreviousBreakOffset() const {
-  const NGBlockBreakToken* token = CurrentBlockBreakToken();
-  return token ? token->BreakOffset() : LayoutUnit();
-}
-
-LayoutUnit NGBlockLayoutAlgorithm::NextBreakOffset() const {
-  if (fragmentainer_mapper_)
-    return fragmentainer_mapper_->NextBreakOffset();
-  DCHECK(ConstraintSpace().HasBlockFragmentation());
-  return PreviousBreakOffset() +
-         ConstraintSpace().FragmentainerSpaceAvailable();
-}
-
-LayoutUnit NGBlockLayoutAlgorithm::SpaceAvailableForCurrentChild() const {
-  LayoutUnit space_left;
-  if (fragmentainer_mapper_)
-    space_left = fragmentainer_mapper_->BlockSize();
-  else if (ConstraintSpace().HasBlockFragmentation())
-    space_left = ConstraintSpace().FragmentainerSpaceAvailable();
-  else
-    return NGSizeIndefinite;
-  space_left -= BorderEdgeForCurrentChild() - PreviousBreakOffset();
-  return space_left;
+  builder_->SetBlockOverflow(content_size_);
 }
 
 NGBoxStrut NGBlockLayoutAlgorithm::CalculateMargins(
@@ -770,8 +667,6 @@ NGBlockLayoutAlgorithm::CreateConstraintSpaceForCurrentChild() {
       .SetWritingMode(
           FromPlatformWritingMode(current_child_style.getWritingMode()))
       .SetTextDirection(current_child_style.direction());
-  LayoutUnit space_available = SpaceAvailableForCurrentChild();
-  space_builder_->SetFragmentainerSpaceAvailable(space_available);
 
   // Clearance :
   // - Collapse margins
@@ -813,6 +708,18 @@ NGBlockLayoutAlgorithm::CreateConstraintSpaceForCurrentChild() {
 
   space_builder_->SetBfcOffset(curr_bfc_offset_);
 
+  if (constraint_space_->HasBlockFragmentation()) {
+    LayoutUnit space_available =
+        ConstraintSpace().FragmentainerSpaceAvailable();
+    if (builder_->BfcOffset()) {
+      // TODO(ikilpatrick): this should be true for new FC's.
+      space_available -= builder_->BfcOffset().value().block_offset;

[mstensho (USE GERRIT), 2017/02/15 21:12:22]

I don't understand how this is supposed to work. We want to subtract the
distance from the top of the current column to the top of the fragment to
create, but what does BFC offset have to do with it?

[ikilpatrick, 2017/02/16 16:48:31]

Ah yeah this is wrong, we need a IsNewFormattingContext check here as well;
basically it will cover this case:

So each column will establish a new (anonymous) block formatting context.
<div id=multicol> <!-- the multi-col element, anon column is new FC -->
  <div id=in-flow-no-new-fc> <!-- "this" - the current layout -->
    <div id=zero-height></div>
    <div id=in-flow-new-fc></div>
  </div>
</div>

"in-flow-no-new-fc" currently doesn't currently know where it is inside its
formatting context; the fragmentation line is with respect to the formatting
context.

When it comes to performing layout upon "in-flow-new-fc" it has to determine the
BFC offset for that child (before that child's layout call) so that it can give
the child the correct fragmentation line with respect to *its* formatting
context.

[mstensho (USE GERRIT), 2017/02/16 21:14:47]

Not sure if I misunderstand what you mean here, but column boxes don't establish
new block formatting contexts. The container does, but each column doesn't.

+    }
+    space_builder_->SetFragmentainerSpaceAvailable(space_available);
+  } else {
+    space_builder_->SetFragmentainerSpaceAvailable(LayoutUnit(0));

[mstensho (USE GERRIT), 2017/02/15 21:12:22]

Just LayoutUnit().

+  }
+
   return space_builder_->ToConstraintSpace();
 }