[LayoutNG] Allow block-flow layout to be fragmented using new approach.

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_block_child_iterator.h"
 #include "core/layout/ng/ng_box_fragment.h"
 #include "core/layout/ng/ng_column_mapper.h"
 #include "core/layout/ng/ng_constraint_space.h"
 #include "core/layout/ng/ng_constraint_space_builder.h"
 #include "core/layout/ng/ng_fragment.h"
 #include "core/layout/ng/ng_fragment_builder.h"
 #include "core/layout/ng/ng_inline_node.h"
 #include "core/layout/ng/ng_layout_opportunity_iterator.h"
 #include "core/layout/ng/ng_length_utils.h"
 #include "core/layout/ng/ng_line_builder.h"
@@ skipping 274 matching lines @@
   if (display == EDisplay::Grid || display == EDisplay::Flex ||
       display == EDisplay::WebkitBox)
     return true;
 
   if (space.WritingMode() != FromPlatformWritingMode(style.getWritingMode()))
     return true;
 
   return false;
 }
 
+// Returns the borders and padding box for the current layout.
+NGBoxStrut ComputeBordersAndPadding(const NGConstraintSpace& space,
+                                    const ComputedStyle& style) {
+  // If we are producing an anonymous fragment (e.g. a column) we shouldn't
+  // have any borders or padding.
+  return space.IsAnonymous()
+             ? NGBoxStrut()
+             : ComputeBorders(style) + ComputePadding(space, style);
+}
+
+// Whether we've run out of space in this flow, if so there will be no work

[mstensho (USE GERRIT), 2017/02/27 13:44:36]

Suggest changing punctuation and capitalization a little, for easier reading:

-> "... in this flow. If so, there will be..."

[ikilpatrick, 2017/02/27 18:50:09]

Done.

+// left to do for this block in this fragmentainer.
+bool IsOutOfSpace(const NGConstraintSpace& space, LayoutUnit content_size) {
+  return space.HasBlockFragmentation() &&
+         content_size >= space.FragmentainerSpaceAvailable();
+}
+
 }  // namespace
 
 NGBlockLayoutAlgorithm::NGBlockLayoutAlgorithm(
     NGBlockNode* node,
     NGConstraintSpace* constraint_space,
-    NGBreakToken* break_token)
+    NGBlockBreakToken* break_token)
     : node_(node),
       constraint_space_(constraint_space),
       break_token_(break_token),
       builder_(WTF::wrapUnique(
           new NGFragmentBuilder(NGPhysicalFragment::kFragmentBox, node))) {}
 
 Optional<MinAndMaxContentSizes>
 NGBlockLayoutAlgorithm::ComputeMinAndMaxContentSizes() const {
   MinAndMaxContentSizes sizes;
 
@@ skipping 35 matching lines @@
                    builder_->BfcOffset().value().block_offset;
   }
   return {inline_offset, block_offset};
 }
 
 RefPtr<NGLayoutResult> NGBlockLayoutAlgorithm::Layout() {
   WTF::Optional<MinAndMaxContentSizes> sizes;
   if (NeedMinAndMaxContentSizes(ConstraintSpace(), Style()))
     sizes = ComputeMinAndMaxContentSizes();
 
-  border_and_padding_ =
-      ComputeBorders(Style()) + ComputePadding(ConstraintSpace(), Style());
+  border_and_padding_ = ComputeBordersAndPadding(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_ = node_->FirstChild();
-  }
+  NGBlockChildIterator child_iterator(node_->FirstChild(), break_token_);
+  NGBlockChildIterator::Entry entry = child_iterator.NextChild();
+  current_child_ = entry.node;
+  NGBreakToken* child_break_token = entry.token;
+
+  // If we are resuming from a break token our start border and padding is
+  // within a previous fragment.
+  content_size_ = break_token_ ? LayoutUnit() : border_and_padding_.block_start;
 
   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) {
     curr_bfc_offset_.block_offset += curr_margin_strut_.Sum();
     UpdateFragmentBfcOffset(curr_bfc_offset_, builder_.get());
@@ skipping 16 matching lines @@
       NGBlockNode* current_block_child = toNGBlockNode(current_child_);
       EPosition position = current_block_child->Style().position();
       if (position == EPosition::kAbsolute || position == EPosition::kFixed) {
         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<NGLayoutResult> layout_result =
-        current_child_->Layout(space_for_current_child_);
+        current_child_->Layout(space_for_current_child_, child_break_token);
 
     FinishCurrentChildLayout(layout_result);
 
-    if (!ProceedToNextUnfinishedSibling(
-            layout_result->PhysicalFragment().get()))
+    entry = child_iterator.NextChild();
+    current_child_ = entry.node;
+    child_break_token = entry.token;
+
+    if (IsOutOfSpace(ConstraintSpace(), content_size_))
       break;
   }
 
   // Margins collapsing:
   //   Bottom margins of an in-flow block box doesn't collapse with its last
   //   in-flow block-level child's bottom margin if the box has bottom
   //   border/padding.
   content_size_ += border_and_padding_.block_end;
   if (border_and_padding_.block_end ||
       ConstraintSpace().IsNewFormattingContext()) {
@@ skipping 80 matching lines @@
       PositionPendingFloats(origin_point.block_offset, ConstraintSpace(),
                             builder_.get());
     }
     return;
   }
 
   // Determine the fragment's position in the parent space either by using
   // content_size_ or known fragment's BFC offset.
   WTF::Optional<NGLogicalOffset> bfc_offset;
   if (CurrentChildConstraintSpace().IsNewFormattingContext()) {
+    // DO NOT SUBMIT - Do we need to move this inside

[Gleb Lanbin, 2017/02/25 01:12:19]

do not forger to remove this before submit

[ikilpatrick, 2017/02/27 18:50:09]

Added TODO

+    // CreateConstraintSpaceForCurrentChild?
     curr_bfc_offset_.block_offset += curr_margin_strut_.Sum();
     bfc_offset = curr_bfc_offset_;
   } else if (fragment.BfcOffset()) {
     // Fragment that knows its offset can be used to set parent's BFC position.
     curr_bfc_offset_.block_offset = fragment.BfcOffset().value().block_offset;
     bfc_offset = curr_bfc_offset_;
   } else if (builder_->BfcOffset()) {
     // Fragment doesn't know its offset but we can still calculate its BFC
     // position because the parent fragment's BFC is known.
     // Example:
     // BFC Offset is known here because of the padding.
     // <div style="padding: 1px">
     //   <div id="empty-div" style="margins: 1px"></div>
     bfc_offset = curr_bfc_offset_;
     bfc_offset.value().block_offset += curr_margin_strut_.Sum();
   }
   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);
-  else
-    logical_offset.block_offset -= PreviousBreakOffset();
-
   // Update margin strut.
   curr_margin_strut_ = fragment.EndMarginStrut();
   curr_margin_strut_.Append(curr_child_margins_.block_end);
 
   // Only modify content_size if BlockSize is not empty. It's needed to prevent
   // the situation when logical_offset is included in content_size for empty
   // blocks. Example:
   //   <div style="overflow:hidden">
   //     <div style="margin-top: 8px"></div>
   //     <div style="margin-top: 10px"></div>
   //   </div>
   if (fragment.BlockSize())
     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(layout_result, 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);
-  }
+void NGBlockLayoutAlgorithm::FinalizeForFragmentation() {
+  LayoutUnit used_block_size =
+      break_token_ ? break_token_->UsedBlockSize() : LayoutUnit();
+  LayoutUnit block_size = ComputeBlockSizeForFragment(
+      ConstraintSpace(), Style(), used_block_size + content_size_);
 
-  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).
-    return false;
-  }
+  block_size -= used_block_size;
+  DCHECK_GE(block_size, LayoutUnit())
+      << "Adding and subtracting the used_block_size shouldn't leave the "

[mstensho (USE GERRIT), 2017/02/27 13:44:36]

Isn't this going to fail when you have a block with fixed height that you
overflow (at least if the current fragmentainer only consists of an overflow
portion of the block)?

Like in the second fragmentainer here:

<div style="columns:2; column-fill:auto; height:100px;">
    <div id="overflowing" style="height:50px;">
        <div style="height:150px;"></div>
    </div>
</div>

Hmm.. but then there's the InnerChildrenFragmentationSmallHeight, which should
also fail then. So I guess there's something I don't understand.

[ikilpatrick, 2017/02/27 18:50:09]

It doesn't fail is it's DCHECK_GE not DCHECK_GT.

[mstensho (USE GERRIT), 2017/02/27 20:28:20]

Yeah, that wasn't my problem. I was thinking that used_block_space also included
space used in the overflow area, but it doesn't, so I understand why this works
now.

Ack.

+         "block_size for this fragment smaller than zero.";
 
-  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;
-}
+  DCHECK(builder_->BfcOffset()) << "We must have our BfcOffset by this point "
+                                   "to determine the space left in the flow.";
+  LayoutUnit space_left = ConstraintSpace().FragmentainerSpaceAvailable() -
+                          builder_->BfcOffset().value().block_offset;

[mstensho (USE GERRIT), 2017/02/27 13:44:36]

What does the block formatting context offset have to do with space left
calculation? Block formatting contexts should be independent of fragmentation.

[ikilpatrick, 2017/02/27 18:50:09]

We need a bunch more documentation around this BfcOffset concept. Basically:

1) Some children (in-flow, non-formatting-context, blocks) don't know their
position relative to parent until they've laid out their children, e.g.
zero-block-size elements can effect their position.

2) We need this position for calculating a few things, e.g. where the intruding
floats will be, where the fragmentation line will end up hitting us.

3) This is what the builder_->BfcOffset is used for,  this says our position
relative to our parent block formatting context. All geometry information is
relative to the formatting context on the constraint space.

[mstensho (USE GERRIT), 2017/02/27 20:28:20]

Acknowledged.

+  DCHECK_GE(space_left, LayoutUnit());
 
-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();
-}
-
-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();
-  DCHECK_GE(space_left, LayoutUnit());
-  if (builder_->HasBreakToken()) {
+  if (builder_->DidBreak()) {
     // A break token is ready, which means that we're going to break

[mstensho (USE GERRIT), 2017/02/27 13:44:36]

Looks like this comment now needs to be updated. There's no "break token [...]
ready" anymore, is there?

[ikilpatrick, 2017/02/27 18:50:09]

Done.

     // before or inside a block-level child.
+    builder_->SetUsedBlockSize(std::min(space_left, block_size) +

[mstensho (USE GERRIT), 2017/02/27 20:28:20]

std::min(space_left, block_size) called twice in a row now. Maybe store the
result somewhere instead. Hijack block_size or introduce a new variable?

+                               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 23 matching lines @@
                        CurrentChildStyle());
 
   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()))
       .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 += curr_child_margins_.inline_start;
     // Append the current margin strut with child's block start margin.
     // Non empty border/padding use cases are handled inside of the child's
     // layout.
     curr_margin_strut_.Append(curr_child_margins_.block_start);
     space_builder_->SetMarginStrut(curr_margin_strut_);
   }
 
   space_builder_->SetBfcOffset(curr_bfc_offset_);
 
+  LayoutUnit space_available;
+  if (constraint_space_->HasBlockFragmentation()) {
+    space_available = ConstraintSpace().FragmentainerSpaceAvailable();
+    // If a block establishes a new formatting context we must know our
+    // position in the formatting context, and are able to adjust the
+    // fragmentation line.
+    if (is_new_bfc) {
+      DCHECK(builder_->BfcOffset());
+      space_available -= curr_bfc_offset_.block_offset;

[mstensho (USE GERRIT), 2017/02/27 13:44:36]

Again, I don't understand the link between block formatting context and
fragmentation. It seems to me that you need to make this adjustment for any
block, regardless of it establishing a new block formatting context or not.

[ikilpatrick, 2017/02/27 18:50:09]

See above, basically the fragmentation line is always relative the parent
formatting context, hence if a child establishes a new formatting context we
need to adjust. This might be clearer inside ng_constraint_space_builder.cc ?

E.g.
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/layout/ng...

[mstensho (USE GERRIT), 2017/02/27 20:28:20]

Acknowledged.

+    }
+  }
+  space_builder_->SetFragmentainerSpaceAvailable(space_available);
+
   return space_builder_->ToConstraintSpace(
       FromPlatformWritingMode(current_child_style.getWritingMode()));
 }
 
 }  // namespace blink