path: root/chromium/third_party/blink/renderer/core/layout/ng/ng_floats_utils.cc

// 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_floats_utils.h"

#include "third_party/blink/renderer/core/frame/local_frame_view.h"
#include "third_party/blink/renderer/core/layout/layout_box.h"
#include "third_party/blink/renderer/core/layout/min_max_sizes.h"
#include "third_party/blink/renderer/core/layout/ng/ng_block_break_token.h"
#include "third_party/blink/renderer/core/layout/ng/ng_constraint_space.h"
#include "third_party/blink/renderer/core/layout/ng/ng_constraint_space_builder.h"
#include "third_party/blink/renderer/core/layout/ng/ng_container_fragment_builder.h"
#include "third_party/blink/renderer/core/layout/ng/ng_fragment.h"
#include "third_party/blink/renderer/core/layout/ng/ng_fragmentation_utils.h"
#include "third_party/blink/renderer/core/layout/ng/ng_layout_result.h"
#include "third_party/blink/renderer/core/layout/ng/ng_length_utils.h"
#include "third_party/blink/renderer/core/layout/ng/ng_positioned_float.h"
#include "third_party/blink/renderer/core/layout/ng/ng_space_utils.h"
#include "third_party/blink/renderer/core/layout/ng/ng_unpositioned_float.h"
#include "third_party/blink/renderer/core/style/computed_style.h"

namespace blink {
namespace {

// Adjusts the provided offset to the top edge alignment rule.
// Top edge alignment rule: the outer top of a floating box may not be higher
// than the outer top of any block or floated box generated by an element
// earlier in the source document.
NGBfcOffset AdjustToTopEdgeAlignmentRule(
    const NGExclusionSpace& exclusion_space,
    const NGBfcOffset& offset) {
  NGBfcOffset adjusted_offset = offset;
  adjusted_offset.block_offset = std::max(
      adjusted_offset.block_offset, exclusion_space.LastFloatBlockStart());

  return adjusted_offset;
}

NGLayoutOpportunity FindLayoutOpportunityForFloat(
    const NGUnpositionedFloat& unpositioned_float,
    const NGExclusionSpace& exclusion_space,
    const NGBoxStrut& fragment_margins,
    LayoutUnit inline_size) {
  NGBfcOffset adjusted_origin_point = AdjustToTopEdgeAlignmentRule(
      exclusion_space, unpositioned_float.origin_bfc_offset);
  LayoutUnit clearance_offset =
      exclusion_space.ClearanceOffset(unpositioned_float.ClearType(
          unpositioned_float.parent_space.Direction()));

  AdjustToClearance(clearance_offset, &adjusted_origin_point);

  return exclusion_space.FindLayoutOpportunity(
      adjusted_origin_point, unpositioned_float.available_size.inline_size,
      inline_size + fragment_margins.InlineSum() /* minimum_inline_size */);
}

// Creates a constraint space for an unpositioned float. origin_block_offset
// should only be set when we want to fragmentation to occur.
NGConstraintSpace CreateConstraintSpaceForFloat(
    const NGUnpositionedFloat& unpositioned_float,
    base::Optional<LayoutUnit> origin_block_offset = base::nullopt) {
  const ComputedStyle& style = unpositioned_float.node.Style();
  const NGConstraintSpace& parent_space = unpositioned_float.parent_space;
  NGConstraintSpaceBuilder builder(parent_space, style.GetWritingDirection(),
                                   /* is_new_fc */ true);
  SetOrthogonalFallbackInlineSizeIfNeeded(unpositioned_float.parent_style,
                                          unpositioned_float.node, &builder);
  builder.SetIsPaintedAtomically(true);

  if (origin_block_offset) {
    DCHECK(parent_space.HasBlockFragmentation());
    DCHECK_EQ(style.GetWritingMode(), parent_space.GetWritingMode());

    SetupSpaceBuilderForFragmentation(parent_space, unpositioned_float.node,
                                      *origin_block_offset, &builder,
                                      /* is_new_fc */ true);
  } else {
    builder.SetFragmentationType(NGFragmentationType::kFragmentNone);
  }

  // If we're resuming layout of this float after a fragmentainer break, the
  // margins of its children may be adjoining with the fragmentainer
  // block-start, in which case they may get truncated.
  if (IsResumingLayout(unpositioned_float.token.get()))
    builder.SetDiscardingMarginStrut();

  builder.SetAvailableSize(unpositioned_float.available_size);
  builder.SetPercentageResolutionSize(unpositioned_float.percentage_size);
  builder.SetReplacedPercentageResolutionSize(
      unpositioned_float.replaced_percentage_size);
  builder.SetIsShrinkToFit(style.LogicalWidth().IsAuto());
  return builder.ToConstraintSpace();
}

std::unique_ptr<NGExclusionShapeData> CreateExclusionShapeData(
    const NGBoxStrut& margins,
    const NGUnpositionedFloat& unpositioned_float) {
  const LayoutBox* layout_box = unpositioned_float.node.GetLayoutBox();
  DCHECK(layout_box->GetShapeOutsideInfo());
  const NGConstraintSpace& parent_space = unpositioned_float.parent_space;
  TextDirection direction = parent_space.Direction();

  // We make the margins on the shape-data relative to line-left/line-right.
  NGBoxStrut new_margins(margins.LineLeft(direction),
                         margins.LineRight(direction), margins.block_start,
                         margins.block_end);
  NGBoxStrut shape_insets;

  const ComputedStyle& style = unpositioned_float.node.Style();
  switch (style.ShapeOutside()->CssBox()) {
    case CSSBoxType::kMissing:
    case CSSBoxType::kMargin:
      shape_insets -= new_margins;
      break;
    case CSSBoxType::kBorder:
      break;
    case CSSBoxType::kPadding:
    case CSSBoxType::kContent:
      const NGConstraintSpace space =
          CreateConstraintSpaceForFloat(unpositioned_float);
      NGBoxStrut strut = ComputeBorders(space, unpositioned_float.node);
      if (style.ShapeOutside()->CssBox() == CSSBoxType::kContent)
        strut += ComputePadding(space, style);
      // |TextDirection::kLtr| is used as this is line relative.
      shape_insets = strut.ConvertToPhysical(style.GetWritingDirection())
                         .ConvertToLogical({parent_space.GetWritingMode(),
                                            TextDirection::kLtr});
      break;
  }

  return std::make_unique<NGExclusionShapeData>(layout_box, new_margins,
                                                shape_insets);
}

// Creates an exclusion from the fragment that will be placed in the provided
// layout opportunity.
scoped_refptr<const NGExclusion> CreateExclusion(
    const NGFragment& fragment,
    const NGBfcOffset& float_margin_bfc_offset,
    const NGBoxStrut& margins,
    const NGUnpositionedFloat& unpositioned_float,
    EFloat type) {
  NGBfcOffset start_offset = float_margin_bfc_offset;
  NGBfcOffset end_offset(
      start_offset.line_offset +
          (fragment.InlineSize() + margins.InlineSum()).ClampNegativeToZero(),
      start_offset.block_offset +
          (fragment.BlockSize() + margins.BlockSum()).ClampNegativeToZero());

  std::unique_ptr<NGExclusionShapeData> shape_data =
      unpositioned_float.node.GetLayoutBox()->GetShapeOutsideInfo()
          ? CreateExclusionShapeData(margins, unpositioned_float)
          : nullptr;

  return NGExclusion::Create(NGBfcRect(start_offset, end_offset), type,
                             std::move(shape_data));
}

// Performs layout on a float, without fragmentation, and stores the result on
// the NGUnpositionedFloat data-structure.
void LayoutFloatWithoutFragmentation(NGUnpositionedFloat* unpositioned_float) {
  if (unpositioned_float->layout_result)
    return;

  const NGConstraintSpace space =
      CreateConstraintSpaceForFloat(*unpositioned_float);

  unpositioned_float->layout_result = unpositioned_float->node.Layout(space);
  unpositioned_float->margins =
      ComputeMarginsFor(space, unpositioned_float->node.Style(),
                        unpositioned_float->parent_space);
}

}  // namespace

LayoutUnit ComputeMarginBoxInlineSizeForUnpositionedFloat(
    NGUnpositionedFloat* unpositioned_float) {
  DCHECK(unpositioned_float);

  LayoutFloatWithoutFragmentation(unpositioned_float);
  DCHECK(unpositioned_float->layout_result);

  const auto& fragment = unpositioned_float->layout_result->PhysicalFragment();
  DCHECK(!fragment.BreakToken());

  const NGConstraintSpace& parent_space = unpositioned_float->parent_space;

  return (NGFragment(parent_space.GetWritingDirection(), fragment)
              .InlineSize() +
          unpositioned_float->margins.InlineSum())
      .ClampNegativeToZero();
}

NGPositionedFloat PositionFloat(NGUnpositionedFloat* unpositioned_float,
                                NGExclusionSpace* exclusion_space) {
  DCHECK(unpositioned_float);
  const NGConstraintSpace& parent_space = unpositioned_float->parent_space;
  NGBlockNode node = unpositioned_float->node;
  bool is_same_writing_mode =
      node.Style().GetWritingMode() == parent_space.GetWritingMode();

  bool is_fragmentable =
      is_same_writing_mode && parent_space.HasBlockFragmentation();

  scoped_refptr<const NGLayoutResult> layout_result;
  NGBoxStrut fragment_margins;
  NGLayoutOpportunity opportunity;
  bool need_break_before = false;

  if (!is_fragmentable) {
    // We may be able to re-use the fragment from when we calculated the
    // inline-size, if there is no block fragmentation.
    LayoutFloatWithoutFragmentation(unpositioned_float);
    layout_result = unpositioned_float->layout_result;
    fragment_margins = unpositioned_float->margins;

    NGFragment float_fragment(parent_space.GetWritingDirection(),
                              layout_result->PhysicalFragment());

    // Find a layout opportunity that will fit our float.
    opportunity = FindLayoutOpportunityForFloat(
        *unpositioned_float, *exclusion_space, fragment_margins,
        float_fragment.InlineSize());
  } else {
    fragment_margins = ComputeMarginsFor(
        node.Style(), unpositioned_float->percentage_size.inline_size,
        parent_space.GetWritingDirection());
    AdjustMarginsForFragmentation(unpositioned_float->token.get(),
                                  &fragment_margins);

    // When fragmenting, we need to set the block-offset of the node before
    // laying it out. This is a float, and in order to calculate its offset, we
    // first need to know its inline-size.

    LayoutUnit fragmentainer_delta;
    bool optimistically_placed = false;
    if (unpositioned_float->layout_result) {
      // We have already laid out the float to find its inline-size.
      NGFragment float_fragment(
          parent_space.GetWritingDirection(),
          unpositioned_float->layout_result->PhysicalFragment());
      // We can find a layout opportunity and set the fragmentainer offset right
      // away.
      opportunity = FindLayoutOpportunityForFloat(
          *unpositioned_float, *exclusion_space, fragment_margins,
          float_fragment.InlineSize());
      fragmentainer_delta = opportunity.rect.start_offset.block_offset +
                            fragment_margins.block_start;
    } else {
      // If we don't know the inline-size yet, we'll estimate the offset to be
      // the one we'd get if the float isn't affected by any other floats in the
      // block formatting context. If this turns out to be wrong, we'll need to
      // lay out again.
      fragmentainer_delta = unpositioned_float->origin_bfc_offset.block_offset +
                            fragment_margins.block_start;
      optimistically_placed = true;
    }

    do {
      NGConstraintSpace space = CreateConstraintSpaceForFloat(
          *unpositioned_float, fragmentainer_delta);

      layout_result = node.Layout(space, unpositioned_float->token.get());

      // If we knew the right block-offset up front, we're done.
      if (!optimistically_placed)
        break;

      NGFragment float_fragment(parent_space.GetWritingDirection(),
                                layout_result->PhysicalFragment());

      // Find a layout opportunity that will fit our float, and see if our
      // initial estimate was correct.
      opportunity = FindLayoutOpportunityForFloat(
          *unpositioned_float, *exclusion_space, fragment_margins,
          float_fragment.InlineSize());

      LayoutUnit new_fragmentainer_delta =
          opportunity.rect.start_offset.block_offset +
          fragment_margins.block_start;

      // We can only stay where we are, or go down.
      DCHECK_LE(fragmentainer_delta, new_fragmentainer_delta);

      if (fragmentainer_delta < new_fragmentainer_delta) {
        // The float got pushed down. We need to lay out again.
        fragmentainer_delta = new_fragmentainer_delta;
        optimistically_placed = false;
        continue;
      }
      break;
    } while (true);

    LayoutUnit fragmentainer_margin_edge_block_offset =
        parent_space.FragmentainerOffsetAtBfc() +
        opportunity.rect.start_offset.block_offset;

    // Note that we don't check if we're at a valid class A, B or C breakpoint
    // (we only check that we're not at the start of the fragmentainer (in which
    // case breaking typically wouldn't eliminate the unappealing break inside
    // the float)). While no other browsers do this either, we should consider
    // doing this in the future. But for now, don't let the float affect the
    // appeal of breaking inside this container.
    //
    // If we're past the fragmentainer start, we can consider breaking before
    // this float. Otherwise we cannot, or there'd be no content
    // progression. The common fragmentation machinery assumes that margins can
    // collapse with fragmentainer boundaries, but this isn't the case for
    // floats. We don't allow float margins to collapse with anything, nor be
    // split into multiple fragmentainers. Hence this additional check. Note
    // that we might want to reconsider this behavior, since browsers disagree
    // (what we do now is relatively similar to legacy Blink, though). Should we
    // split a margin in cases where it helps prevent fragmentainer overflow?
    // Should we always split them if they occur at fragmentainer boundaries? Or
    // even allow them to collapse with the fragmentainer boundary? Exact
    // behavior is currently unspecified.
    if (fragmentainer_margin_edge_block_offset > LayoutUnit()) {
      LayoutUnit fragmentainer_block_offset =
          fragmentainer_margin_edge_block_offset + fragment_margins.block_start;
      if (!MovePastBreakpoint(parent_space, node, *layout_result,
                              fragmentainer_block_offset, kBreakAppealPerfect,
                              /* builder */ nullptr)) {
        need_break_before = true;
      } else if (layout_result->PhysicalFragment().BreakToken()) {
        // We need to resume in the next fragmentainer, which means that
        // there'll be no block-end margin here.
        fragment_margins.block_end = LayoutUnit();
      }
    }
  }

  NGFragment float_fragment(parent_space.GetWritingDirection(),
                            layout_result->PhysicalFragment());

  // Calculate the float's margin box BFC offset.
  NGBfcOffset float_margin_bfc_offset = opportunity.rect.start_offset;
  if (unpositioned_float->IsLineRight(parent_space.Direction())) {
    LayoutUnit float_margin_box_inline_size =
        float_fragment.InlineSize() + fragment_margins.InlineSum();
    float_margin_bfc_offset.line_offset +=
        (opportunity.rect.InlineSize() - float_margin_box_inline_size);
  }

  // Add the float as an exclusion.
  if (need_break_before) {
    // Create a special exclusion past everything. This will prevent us from
    // adding any more floats in this formatting context to the current
    // fragmentainer, and also make clearance behave correctly (e.g. an in-flow
    // block with clear:left after a float:left that got pushed to the next
    // fragmentainer means that the in-flow block also needs to be pushed, while
    // if the in-flow block has clear:right, it may still be allowed in the
    // current fragmentainer).
    NGBfcOffset past_everything(LayoutUnit(),
                                FragmentainerSpaceAtBfcStart(parent_space));
    scoped_refptr<const NGExclusion> exclusion =
        NGExclusion::Create(NGBfcRect(past_everything, past_everything),
                            node.Style().Floating(parent_space.Direction()));
    exclusion_space->Add(std::move(exclusion));
  } else {
    scoped_refptr<const NGExclusion> exclusion = CreateExclusion(
        float_fragment, float_margin_bfc_offset, fragment_margins,
        *unpositioned_float, node.Style().Floating(parent_space.Direction()));
    exclusion_space->Add(std::move(exclusion));
  }

  // Adjust the float's bfc_offset to its border-box (instead of margin-box).
  NGBfcOffset float_bfc_offset(
      float_margin_bfc_offset.line_offset +
          fragment_margins.LineLeft(parent_space.Direction()),
      float_margin_bfc_offset.block_offset + fragment_margins.block_start);

  return NGPositionedFloat(std::move(layout_result), float_bfc_offset,
                           need_break_before);
}

}  // namespace blink