[LayoutNG] A different approach to multi-col.

third_party/WebKit/Source/core/layout/ng/ng_block_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_block_layout_algorithm.h"
 
 #include "core/layout/ng/ng_absolute_utils.h"
 #include "core/layout/ng/ng_block_break_token.h"
 #include "core/layout/ng/ng_box_fragment.h"
 #include "core/layout/ng/ng_column_mapper.h"
@@ skipping 282 matching lines @@
 
   if (space.WritingMode() != FromPlatformWritingMode(style.getWritingMode()))
     return true;
 
   return false;
 }
 
 }  // 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_);
 }
 
 Optional<MinAndMaxContentSizes>
 NGBlockLayoutAlgorithm::ComputeMinAndMaxContentSizes() const {
   MinAndMaxContentSizes sizes;
 
   // Size-contained elements don't consider their contents for intrinsic sizing.
   if (Style().containsSize())
     return sizes;
@@ skipping 32 matching lines @@
                    builder_->BfcOffset().value().block_offset;
   }
   return {inline_offset, block_offset};
 }
 
 RefPtr<NGPhysicalFragment> NGBlockLayoutAlgorithm::Layout() {
   WTF::Optional<MinAndMaxContentSizes> sizes;
   if (NeedMinAndMaxContentSizes(ConstraintSpace(), Style()))
     sizes = ComputeMinAndMaxContentSizes();
 
+  // TODO(ikilpatrick): should be no borders or padding if anon.
   border_and_padding_ =
       ComputeBorders(Style()) + ComputePadding(ConstraintSpace(), Style());
 
   LayoutUnit inline_size =
       ComputeInlineSizeForFragment(ConstraintSpace(), Style(), sizes);
   LayoutUnit adjusted_inline_size =
       inline_size - border_and_padding_.InlineSum();
   // TODO(layout-ng): For quirks mode, should we pass blockSize instead of
   // -1?
   LayoutUnit block_size =
       ComputeBlockSizeForFragment(ConstraintSpace(), Style(), NGSizeIndefinite);
   LayoutUnit adjusted_block_size(block_size);
   // Our calculated block-axis size may be indefinite at this point.
   // If so, just leave the size as NGSizeIndefinite instead of subtracting
   // borders and padding.
   if (adjusted_block_size != NGSizeIndefinite)
     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();
 
   // Margins collapsing:
   //   Do not collapse margins between parent and its child if there is
   //   border/padding between them.
   if (border_and_padding_.block_start ||
       ConstraintSpace().IsNewFormattingContext()) {
     curr_bfc_offset_.block_offset += curr_margin_strut_.Sum();
     builder_->SetBfcOffset(curr_bfc_offset_);
     curr_margin_strut_ = NGMarginStrut();
   }
   curr_bfc_offset_.block_offset += content_size_;
 
   while (current_child_) {
     if (current_child_->Type() == NGLayoutInputNode::kLegacyBlock) {
       NGBlockNode* current_block_child = toNGBlockNode(current_child_);
       EPosition position = current_block_child->Style().position();
       if (position == AbsolutePosition || position == FixedPosition) {
         builder_->AddOutOfFlowChildCandidate(current_block_child,
                                              GetChildSpaceOffset());
         current_child_ = current_block_child->NextSibling();
         continue;
       }
     }
 
-    DCHECK(!ConstraintSpace().HasBlockFragmentation() ||
-           SpaceAvailableForCurrentChild() > LayoutUnit());
     space_for_current_child_ = CreateConstraintSpaceForCurrentChild();
 
     if (current_child_->Type() == NGLayoutInputNode::kLegacyInline) {
       LayoutInlineChildren(toNGInlineNode(current_child_));
       continue;
     }
 
     RefPtr<NGPhysicalFragment> physical_fragment =
         current_child_->Layout(space_for_current_child_);
 
@@ skipping 48 matching lines @@
 }
 
 void NGBlockLayoutAlgorithm::LayoutInlineChildren(NGInlineNode* current_child) {
   // TODO(kojii): This logic does not handle when children are mix of
   // inline/block. We need to detect the case and setup appropriately; e.g.,
   // constraint space, margin collapsing, next siblings, etc.
   NGLineBuilder line_builder(current_child, space_for_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();
   line_builder.CopyFragmentDataToLayoutBlockFlow();
   FinishCurrentChildLayout(child_fragment.get());
   current_child_ = nullptr;
 }
 
 void NGBlockLayoutAlgorithm::FinishCurrentChildLayout(
     RefPtr<NGPhysicalBoxFragment> physical_fragment) {
@@ skipping 39 matching lines @@
     curr_bfc_offset_.block_offset = fragment.BfcOffset().value().block_offset;
     bfc_offset = curr_bfc_offset_;
   }
   if (bfc_offset) {
     UpdateFragmentBfcOffset(curr_bfc_offset_, builder_.get());
     PositionPendingFloats(curr_bfc_offset_.block_offset, ConstraintSpace(),
                           builder_.get());
   }
   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);
 
   content_size_ = fragment.BlockSize() + logical_offset.block_offset;
   max_inline_size_ =
       std::max(max_inline_size_, fragment.InlineSize() +
                                      curr_child_margins_.InlineSum() +
                                      border_and_padding_.InlineSum());
 
   builder_->AddChild(std::move(physical_fragment), logical_offset);
 }
 
 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);
-  }
+  std::tie(current_child_, current_child_break_token_) =
+      child_iterator_->NextChild();
 
-  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).
+  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;
-}
-
-void NGBlockLayoutAlgorithm::SetPendingBreakToken(NGBlockBreakToken* token) {
-  if (fragmentainer_mapper_)
-    fragmentainer_mapper_->SetBreakToken(token);
-  else
-    builder_->SetBreakToken(token);
-}
-
-bool NGBlockLayoutAlgorithm::HasPendingBreakToken() const {
-  if (fragmentainer_mapper_)
-    return fragmentainer_mapper_->HasBreakToken();
-  return builder_->HasBreakToken();
+  return current_child_;
 }
 
 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();
+  LayoutUnit used_block_size =
+      break_token_ ? break_token_->UsedBlockSize() : LayoutUnit();
+  LayoutUnit block_size = ComputeBlockSizeForFragment(
+      ConstraintSpace(), Style(), used_block_size + content_size_);
+
+  if (!block_size)
+    return;
+
+  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(
     const NGConstraintSpace& space,
     const ComputedStyle& style) {
   WTF::Optional<MinAndMaxContentSizes> sizes;
   if (NeedMinAndMaxContentSizes(space, style)) {
     // TODO(ikilpatrick): Change ComputeMinAndMaxContentSizes to return
     // MinAndMaxContentSizes.
     sizes = toNGBlockNode(current_child_)->ComputeMinAndMaxContentSizes();
@@ skipping 21 matching lines @@
 
   const ComputedStyle& current_child_style = CurrentChildStyle();
   bool is_new_bfc = IsNewFormattingContextForInFlowBlockLevelChild(
       ConstraintSpace(), current_child_style);
   space_builder_->SetIsNewFormattingContext(is_new_bfc)
       .SetIsShrinkToFit(
           ShouldShrinkToFit(ConstraintSpace(), CurrentChildStyle()))
       .SetWritingMode(
           FromPlatformWritingMode(current_child_style.getWritingMode()))
       .SetTextDirection(current_child_style.direction());
-  LayoutUnit space_available = SpaceAvailableForCurrentChild();
-  space_builder_->SetFragmentainerSpaceAvailable(space_available);
 
   // Clearance :
   // - Collapse margins
   // - Update curr_bfc_offset and parent BFC offset if needed.
   // - Position all pending floats as position is known now.
   // TODO(glebl): Fix the use case with clear: left and an intruding right.
   // https://software.hixie.ch/utilities/js/live-dom-viewer/saved/4847
   if (current_child_style.clear() != EClear::kNone) {
     curr_bfc_offset_.block_offset += curr_margin_strut_.Sum();
     UpdateFragmentBfcOffset(curr_bfc_offset_, builder_.get());
@@ skipping 21 matching lines @@
   curr_bfc_offset_.inline_offset += border_and_padding_.inline_start;
 
   // Floats margins are not included in child's CS because they are used to
   // calculate floating exclusions.
   if (!CurrentChildStyle().isFloating()) {
     curr_bfc_offset_.inline_offset += curr_child_margins_.inline_start;
   }
 
   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();
 }
 
 }  // namespace blink