| // Copyright 2017 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 "third_party/blink/renderer/core/layout/ng/ng_column_layout_algorithm.h" |
| |
| #include <algorithm> |
| #include "third_party/blink/renderer/core/layout/ng/geometry/ng_logical_size.h" |
| #include "third_party/blink/renderer/core/layout/ng/inline/ng_baseline.h" |
| #include "third_party/blink/renderer/core/layout/ng/ng_block_layout_algorithm.h" |
| #include "third_party/blink/renderer/core/layout/ng/ng_box_fragment.h" |
| #include "third_party/blink/renderer/core/layout/ng/ng_constraint_space_builder.h" |
| #include "third_party/blink/renderer/core/layout/ng/ng_length_utils.h" |
| #include "third_party/blink/renderer/core/layout/ng/ng_out_of_flow_layout_part.h" |
| #include "third_party/blink/renderer/core/layout/ng/ng_physical_box_fragment.h" |
| #include "third_party/blink/renderer/core/style/computed_style.h" |
| |
| namespace blink { |
| |
| namespace { |
| |
| inline bool NeedsColumnBalancing(LayoutUnit block_size, |
| const ComputedStyle& style) { |
| return block_size == NGSizeIndefinite || |
| style.GetColumnFill() == EColumnFill::kBalance; |
| } |
| |
| // Constrain a balanced column block size to not overflow the multicol |
| // container. |
| LayoutUnit ConstrainColumnBlockSize(LayoutUnit size, |
| NGBlockNode node, |
| const NGConstraintSpace& space) { |
| // The {,max-}{height,width} properties are specified on the multicol |
| // container, but here we're calculating the column block sizes inside the |
| // multicol container, which isn't exactly the same. We may shrink the column |
| // block size here, but we'll never stretch it, because the value passed is |
| // the perfect balanced block size. Making it taller would only disrupt the |
| // balanced output, for no reason. The only thing we need to worry about here |
| // is to not overflow the multicol container. |
| |
| // First of all we need to convert the size to a value that can be compared |
| // against the resolved properties on the multicol container. That means that |
| // we have to convert the value from content-box to border-box. |
| NGBoxStrut border_scrollbar_padding = |
| CalculateBorderScrollbarPadding(space, node); |
| LayoutUnit extra = border_scrollbar_padding.BlockSum(); |
| size += extra; |
| |
| const ComputedStyle& style = node.Style(); |
| LayoutUnit max = ResolveBlockLength(space, style, style.LogicalMaxHeight(), |
| size, LengthResolveType::kMaxSize, |
| LengthResolvePhase::kLayout); |
| LayoutUnit extent = ResolveBlockLength(space, style, style.LogicalHeight(), |
| size, LengthResolveType::kContentSize, |
| LengthResolvePhase::kLayout); |
| if (extent != NGSizeIndefinite) { |
| // A specified height/width will just constrain the maximum length. |
| max = std::min(max, extent); |
| } |
| |
| // Constrain and convert the value back to content-box. |
| size = std::min(size, max); |
| return size - extra; |
| } |
| |
| } // namespace |
| |
| NGColumnLayoutAlgorithm::NGColumnLayoutAlgorithm( |
| NGBlockNode node, |
| const NGConstraintSpace& space, |
| const NGBreakToken* break_token) |
| : NGLayoutAlgorithm(node, space, ToNGBlockBreakToken(break_token)) { |
| container_builder_.SetIsNewFormattingContext(space.IsNewFormattingContext()); |
| } |
| |
| scoped_refptr<NGLayoutResult> NGColumnLayoutAlgorithm::Layout() { |
| NGBoxStrut borders = ComputeBorders(ConstraintSpace(), Node()); |
| NGBoxStrut scrollbars = Node().GetScrollbarSizes(); |
| NGBoxStrut padding = ComputePadding(ConstraintSpace(), Style()) + |
| ComputeIntrinsicPadding(ConstraintSpace(), Node()); |
| NGBoxStrut border_scrollbar_padding = borders + scrollbars + padding; |
| NGLogicalSize border_box_size = |
| CalculateBorderBoxSize(ConstraintSpace(), Node()); |
| NGLogicalSize content_box_size = |
| ShrinkAvailableSize(border_box_size, border_scrollbar_padding); |
| NGLogicalSize column_size = CalculateColumnSize(content_box_size); |
| |
| WritingMode writing_mode = ConstraintSpace().GetWritingMode(); |
| LayoutUnit column_block_offset(border_scrollbar_padding.block_start); |
| LayoutUnit column_inline_progression = |
| column_size.inline_size + |
| ResolveUsedColumnGap(content_box_size.inline_size, Style()); |
| int used_column_count = |
| ResolveUsedColumnCount(content_box_size.inline_size, Style()); |
| |
| do { |
| scoped_refptr<const NGBlockBreakToken> break_token = BreakToken(); |
| LayoutUnit intrinsic_block_size; |
| LayoutUnit column_inline_offset(border_scrollbar_padding.inline_start); |
| int actual_column_count = 0; |
| int forced_break_count = 0; |
| |
| // Each column should calculate their own minimal space shortage. Find the |
| // lowest value of those. This will serve as the column stretch amount, if |
| // we determine that stretching them is necessary and possible (column |
| // balancing). |
| LayoutUnit minimal_space_shortage(LayoutUnit::Max()); |
| |
| // Allow any block-start margins at the start of the first column. |
| bool separate_leading_margins = true; |
| |
| do { |
| // Lay out one column. Each column will become a fragment. |
| NGConstraintSpace child_space = CreateConstraintSpaceForColumns( |
| column_size, separate_leading_margins); |
| |
| NGBlockLayoutAlgorithm child_algorithm(Node(), child_space, |
| break_token.get()); |
| child_algorithm.SetBoxType(NGPhysicalFragment::kColumnBox); |
| scoped_refptr<NGLayoutResult> result = child_algorithm.Layout(); |
| const NGPhysicalBoxFragment* column = |
| ToNGPhysicalBoxFragment(result->PhysicalFragment()); |
| |
| NGLogicalOffset logical_offset(column_inline_offset, column_block_offset); |
| container_builder_.AddChild(*result, logical_offset); |
| |
| LayoutUnit space_shortage = result->MinimalSpaceShortage(); |
| if (space_shortage > LayoutUnit()) { |
| minimal_space_shortage = |
| std::min(minimal_space_shortage, space_shortage); |
| } |
| actual_column_count++; |
| if (result->HasForcedBreak()) { |
| forced_break_count++; |
| separate_leading_margins = true; |
| } else { |
| separate_leading_margins = false; |
| } |
| |
| LayoutUnit block_size = |
| NGBoxFragment(writing_mode, ConstraintSpace().Direction(), *column) |
| .BlockSize(); |
| intrinsic_block_size = |
| std::max(intrinsic_block_size, column_block_offset + block_size); |
| |
| column_inline_offset += column_inline_progression; |
| break_token = ToNGBlockBreakToken(column->BreakToken()); |
| } while (break_token && !break_token->IsFinished()); |
| |
| // If we overflowed (actual column count larger than what we have room for), |
| // and we're supposed to calculate the column lengths automatically (column |
| // balancing), see if we're able to stretch them. |
| // |
| // We can only stretch the columns if we have at least one column that could |
| // take more content, and we also need to know the stretch amount (minimal |
| // space shortage). We need at least one soft break opportunity to do |
| // this. If forced breaks cause too many breaks, there's no stretch amount |
| // that could prevent the actual column count from overflowing. |
| if (actual_column_count > used_column_count && |
| actual_column_count > forced_break_count + 1 && |
| minimal_space_shortage != LayoutUnit::Max()) { |
| LayoutUnit new_column_block_size = |
| StretchColumnBlockSize(minimal_space_shortage, column_size.block_size, |
| content_box_size.block_size); |
| |
| DCHECK_GE(new_column_block_size, column_size.block_size); |
| if (new_column_block_size > column_size.block_size) { |
| // Re-attempt layout with taller columns. |
| column_size.block_size = new_column_block_size; |
| container_builder_.RemoveChildren(); |
| continue; |
| } |
| } |
| container_builder_.SetIntrinsicBlockSize(intrinsic_block_size); |
| break; |
| } while (true); |
| |
| NGOutOfFlowLayoutPart(&container_builder_, Node().IsAbsoluteContainer(), |
| Node().IsFixedContainer(), borders + scrollbars, |
| ConstraintSpace(), Style()) |
| .Run(); |
| |
| // TODO(mstensho): Propagate baselines. |
| |
| if (border_box_size.block_size == NGSizeIndefinite) { |
| // Get the block size from the columns if it's auto. |
| border_box_size.block_size = |
| column_size.block_size + border_scrollbar_padding.BlockSum(); |
| } |
| container_builder_.SetInlineSize(border_box_size.inline_size); |
| container_builder_.SetBlockSize(border_box_size.block_size); |
| container_builder_.SetBorders(ComputeBorders(ConstraintSpace(), Style())); |
| container_builder_.SetPadding(ComputePadding(ConstraintSpace(), Style())); |
| |
| return container_builder_.ToBoxFragment(); |
| } |
| |
| base::Optional<MinMaxSize> NGColumnLayoutAlgorithm::ComputeMinMaxSize( |
| const MinMaxSizeInput& input) const { |
| // First calculate the min/max sizes of columns. |
| NGBlockLayoutAlgorithm algorithm(Node(), ConstraintSpace()); |
| MinMaxSizeInput child_input(input); |
| child_input.size_type = NGMinMaxSizeType::kContentBoxSize; |
| base::Optional<MinMaxSize> min_max_sizes = |
| algorithm.ComputeMinMaxSize(child_input); |
| DCHECK(min_max_sizes.has_value()); |
| MinMaxSize sizes = min_max_sizes.value(); |
| |
| // If column-width is non-auto, pick the larger of that and intrinsic column |
| // width. |
| if (!Style().HasAutoColumnWidth()) { |
| sizes.min_size = |
| std::max(sizes.min_size, LayoutUnit(Style().ColumnWidth())); |
| sizes.max_size = std::max(sizes.max_size, sizes.min_size); |
| } |
| |
| // Now convert those column min/max values to multicol container min/max |
| // values. We typically have multiple columns and also gaps between them. |
| int column_count = Style().ColumnCount(); |
| DCHECK_GE(column_count, 1); |
| sizes.min_size *= column_count; |
| sizes.max_size *= column_count; |
| LayoutUnit column_gap = ResolveUsedColumnGap(LayoutUnit(), Style()); |
| sizes += column_gap * (column_count - 1); |
| |
| if (input.size_type == NGMinMaxSizeType::kBorderBoxSize) { |
| LayoutUnit border_scrollbar_padding = |
| CalculateBorderScrollbarPadding(ConstraintSpace(), node_).InlineSum(); |
| sizes += border_scrollbar_padding; |
| } |
| |
| return sizes; |
| } |
| |
| NGLogicalSize NGColumnLayoutAlgorithm::CalculateColumnSize( |
| const NGLogicalSize& content_box_size) { |
| NGLogicalSize column_size = content_box_size; |
| DCHECK_GE(column_size.inline_size, LayoutUnit()); |
| column_size.inline_size = |
| ResolveUsedColumnInlineSize(column_size.inline_size, Style()); |
| |
| if (NeedsColumnBalancing(column_size.block_size, Style())) { |
| int used_count = |
| ResolveUsedColumnCount(content_box_size.inline_size, Style()); |
| column_size.block_size = |
| CalculateBalancedColumnBlockSize(column_size, used_count); |
| } |
| |
| return column_size; |
| } |
| |
| LayoutUnit NGColumnLayoutAlgorithm::CalculateBalancedColumnBlockSize( |
| const NGLogicalSize& column_size, |
| int column_count) { |
| // To calculate a balanced column size, we need to figure out how tall our |
| // content is. To do that we need to lay out. Create a special constraint |
| // space for column balancing, without splitting into fragmentainers. It will |
| // make us lay out all the multicol content as one single tall strip. When |
| // we're done with this layout pass, we can examine the result and calculate |
| // an ideal column block size. |
| NGConstraintSpace space = CreateConstaintSpaceForBalancing(column_size); |
| NGBlockLayoutAlgorithm balancing_algorithm(Node(), space); |
| scoped_refptr<NGLayoutResult> result = balancing_algorithm.Layout(); |
| |
| // TODO(mstensho): This is where the fun begins. We need to examine the entire |
| // fragment tree, not just the root. |
| NGFragment fragment(space.GetWritingMode(), *result->PhysicalFragment()); |
| LayoutUnit single_strip_block_size = fragment.BlockSize(); |
| |
| // Some extra care is required the division here. We want a the resulting |
| // LayoutUnit value to be large enough to prevent overflowing columns. Use |
| // floating point to get higher precision than LayoutUnit. Then convert it to |
| // a LayoutUnit, but round it up to the nearest value that LayoutUnit is able |
| // to represent. |
| LayoutUnit block_size = LayoutUnit::FromFloatCeil( |
| single_strip_block_size.ToFloat() / static_cast<float>(column_count)); |
| |
| // Finally, honor {,min-,max-}{height,width} properties. |
| return ConstrainColumnBlockSize(block_size, Node(), ConstraintSpace()); |
| } |
| |
| LayoutUnit NGColumnLayoutAlgorithm::StretchColumnBlockSize( |
| LayoutUnit minimal_space_shortage, |
| LayoutUnit current_column_size, |
| LayoutUnit container_content_box_block_size) const { |
| if (!NeedsColumnBalancing(container_content_box_block_size, Style())) |
| return current_column_size; |
| LayoutUnit length = current_column_size + minimal_space_shortage; |
| // Honor {,min-,max-}{height,width} properties. |
| return ConstrainColumnBlockSize(length, Node(), ConstraintSpace()); |
| } |
| |
| NGConstraintSpace NGColumnLayoutAlgorithm::CreateConstraintSpaceForColumns( |
| const NGLogicalSize& column_size, |
| bool separate_leading_margins) const { |
| NGConstraintSpaceBuilder space_builder( |
| ConstraintSpace(), Style().GetWritingMode(), /* is_new_fc */ true); |
| space_builder.SetAvailableSize(column_size); |
| space_builder.SetPercentageResolutionSize(column_size); |
| |
| if (NGBaseline::ShouldPropagateBaselines(Node())) |
| space_builder.AddBaselineRequests(ConstraintSpace().BaselineRequests()); |
| |
| // To ensure progression, we need something larger than 0 here. The spec |
| // actually says that fragmentainers have to accept at least 1px of content. |
| // See https://www.w3.org/TR/css-break-3/#breaking-rules |
| LayoutUnit column_block_size = |
| std::max(column_size.block_size, LayoutUnit(1)); |
| |
| space_builder.SetFragmentationType(kFragmentColumn); |
| space_builder.SetFragmentainerBlockSize(column_block_size); |
| space_builder.SetFragmentainerSpaceAtBfcStart(column_block_size); |
| space_builder.SetIsAnonymous(true); |
| space_builder.SetSeparateLeadingFragmentainerMargins( |
| separate_leading_margins); |
| |
| return space_builder.ToConstraintSpace(); |
| } |
| |
| NGConstraintSpace NGColumnLayoutAlgorithm::CreateConstaintSpaceForBalancing( |
| const NGLogicalSize& column_size) const { |
| NGConstraintSpaceBuilder space_builder( |
| ConstraintSpace(), Style().GetWritingMode(), /* is_new_fc */ true); |
| space_builder.SetAvailableSize({column_size.inline_size, NGSizeIndefinite}); |
| space_builder.SetPercentageResolutionSize(column_size); |
| space_builder.SetIsAnonymous(true); |
| space_builder.SetIsIntermediateLayout(true); |
| |
| return space_builder.ToConstraintSpace(); |
| } |
| |
| } // namespace Blink |