// Copyright 2017 The Chromium Authors
// 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/floats_utils.h"

#include "third_party/blink/renderer/core/frame/local_frame_view.h"
#include "third_party/blink/renderer/core/layout/block_break_token.h"
#include "third_party/blink/renderer/core/layout/constraint_space.h"
#include "third_party/blink/renderer/core/layout/constraint_space_builder.h"
#include "third_party/blink/renderer/core/layout/fragment_builder.h"
#include "third_party/blink/renderer/core/layout/fragmentation_utils.h"
#include "third_party/blink/renderer/core/layout/layout_box.h"
#include "third_party/blink/renderer/core/layout/layout_result.h"
#include "third_party/blink/renderer/core/layout/length_utils.h"
#include "third_party/blink/renderer/core/layout/logical_fragment.h"
#include "third_party/blink/renderer/core/layout/min_max_sizes.h"
#include "third_party/blink/renderer/core/layout/physical_fragment.h"
#include "third_party/blink/renderer/core/layout/positioned_float.h"
#include "third_party/blink/renderer/core/layout/space_utils.h"
#include "third_party/blink/renderer/core/layout/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.
BfcOffset AdjustToTopEdgeAlignmentRule(const ExclusionSpace& exclusion_space,
                                       const BfcOffset& offset) {
  BfcOffset adjusted_offset = offset;
  adjusted_offset.block_offset = std::max(
      adjusted_offset.block_offset, exclusion_space.LastFloatBlockStart());

  return adjusted_offset;
}

LayoutOpportunity FindLayoutOpportunityForFloat(
    const UnpositionedFloat& unpositioned_float,
    const ExclusionSpace& exclusion_space,
    const BoxStrut& fragment_margins,
    LayoutUnit inline_size) {
  BfcOffset adjusted_origin_point = AdjustToTopEdgeAlignmentRule(
      exclusion_space, unpositioned_float.origin_bfc_offset);

  const TextDirection direction = unpositioned_float.parent_space.Direction();
  const EClear clear_type = unpositioned_float.ClearType(direction);
  const EFloat float_type = unpositioned_float.node.Style().Floating(direction);
  const LayoutUnit clearance_offset =
      std::max({exclusion_space.ClearanceOffset(clear_type),
                exclusion_space.InitialLetterClearanceOffset(float_type)});

  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.
ConstraintSpace CreateConstraintSpaceForFloat(
    const UnpositionedFloat& unpositioned_float,
    std::optional<LayoutUnit> origin_block_offset = std::nullopt,
    std::optional<BoxStrut> margins = std::nullopt) {
  const ComputedStyle& style = unpositioned_float.node.Style();
  const ConstraintSpace& parent_space = unpositioned_float.parent_space;
  ConstraintSpaceBuilder builder(parent_space, style.GetWritingDirection(),
                                 /* is_new_fc */ true);
  SetOrthogonalFallbackInlineSizeIfNeeded(unpositioned_float.parent_style,
                                          unpositioned_float.node, &builder);
  builder.SetIsPaintedAtomically(true);
  builder.SetIsHiddenForPaint(unpositioned_float.is_hidden_for_paint);

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

    SetupSpaceBuilderForFragmentation(
        parent_space, unpositioned_float.node,
        unpositioned_float.fragmentainer_block_offset + *origin_block_offset,
        unpositioned_float.fragmentainer_block_size,
        /*requires_content_before_breaking=*/false, &builder);

    // For other node types, what matters is whether the block-start border edge
    // is at the fragmentainer start, but for floats, it's the block start
    // *margin* edge, since float margins are unbreakable and are never
    // truncated.
    LayoutUnit margin_edge_offset =
        unpositioned_float.fragmentainer_block_offset + *origin_block_offset -
        margins->block_start;
    if (margin_edge_offset <= LayoutUnit())
      builder.SetIsAtFragmentainerStart();
  } else {
    builder.SetFragmentationType(FragmentationType::kFragmentNone);
  }

  builder.SetAvailableSize(unpositioned_float.available_size);
  builder.SetPercentageResolutionSize(unpositioned_float.percentage_size);
  return builder.ToConstraintSpace();
}

ExclusionShapeData* CreateExclusionShapeData(
    const BoxStrut& margins,
    const UnpositionedFloat& unpositioned_float) {
  const LayoutBox* layout_box = unpositioned_float.node.GetLayoutBox();
  DCHECK(layout_box->GetShapeOutsideInfo());
  const ConstraintSpace& 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.
  BoxStrut new_margins(margins.LineLeft(direction),
                       margins.LineRight(direction), margins.block_start,
                       margins.block_end);
  BoxStrut 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 ConstraintSpace space =
          CreateConstraintSpaceForFloat(unpositioned_float);
      BoxStrut 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 MakeGarbageCollected<ExclusionShapeData>(layout_box, new_margins,
                                                  shape_insets);
}

// Creates an exclusion from the fragment that will be placed in the provided
// layout opportunity.
const ExclusionArea* CreateExclusionArea(
    const LogicalFragment& fragment,
    const BfcOffset& float_margin_bfc_offset,
    const BoxStrut& margins,
    const UnpositionedFloat& unpositioned_float,
    EFloat type) {
  BfcOffset start_offset = float_margin_bfc_offset;
  BfcOffset end_offset(
      start_offset.line_offset +
          (fragment.InlineSize() + margins.InlineSum()).ClampNegativeToZero(),
      start_offset.block_offset +
          (fragment.BlockSize() + margins.BlockSum()).ClampNegativeToZero());

  ExclusionShapeData* shape_data =
      unpositioned_float.node.GetLayoutBox()->GetShapeOutsideInfo()
          ? CreateExclusionShapeData(margins, unpositioned_float)
          : nullptr;

  return ExclusionArea::Create(BfcRect(start_offset, end_offset), type,
                               unpositioned_float.is_hidden_for_paint,
                               std::move(shape_data));
}

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

  const ConstraintSpace space =
      CreateConstraintSpaceForFloat(*unpositioned_float);

  // Pass in the break token if one exists. This can happen when we relayout
  // without fragmentation to handle clipping. We still want to look at the
  // break token so that layout is resumed correctly. See
  // InvolvedInBlockFragmentation() in fragmentation_utils.h for more details.
  unpositioned_float->layout_result =
      unpositioned_float->node.Layout(space, unpositioned_float->token);
  unpositioned_float->margins =
      ComputeMarginsFor(space, unpositioned_float->node.Style(),
                        unpositioned_float->parent_space);
}

}  // namespace

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

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

  const auto& fragment =
      unpositioned_float->layout_result->GetPhysicalFragment();
  DCHECK(!fragment.GetBreakToken());

  const ConstraintSpace& parent_space = unpositioned_float->parent_space;

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

PositionedFloat PositionFloat(UnpositionedFloat* unpositioned_float,
                              ExclusionSpace* exclusion_space) {
  DCHECK(unpositioned_float);
  const ConstraintSpace& parent_space = unpositioned_float->parent_space;
  BlockNode 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();

  const LayoutResult* layout_result = nullptr;
  BoxStrut fragment_margins;
  LayoutOpportunity opportunity;
  LayoutUnit fragmentainer_block_size =
      unpositioned_float->fragmentainer_block_size;
  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;

    LogicalFragment float_fragment(parent_space.GetWritingDirection(),
                                   layout_result->GetPhysicalFragment());

    // 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, &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.
      LogicalFragment float_fragment(
          parent_space.GetWritingDirection(),
          unpositioned_float->layout_result->GetPhysicalFragment());
      // 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;
    }

    bool is_at_fragmentainer_start;
    do {
      ConstraintSpace space = CreateConstraintSpaceForFloat(
          *unpositioned_float,
          fragmentainer_delta - parent_space.ExpectedBfcBlockOffset(),
          fragment_margins);

      is_at_fragmentainer_start = space.IsAtFragmentainerStart();

      layout_result = node.Layout(space, unpositioned_float->token);
      DCHECK_EQ(layout_result->Status(), LayoutResult::kSuccess);

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

      LogicalFragment float_fragment(parent_space.GetWritingDirection(),
                                     layout_result->GetPhysicalFragment());

      // 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);

    // 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 (!is_at_fragmentainer_start) {
      LayoutUnit fragmentainer_block_offset =
          unpositioned_float->FragmentainerOffsetAtBfc() +
          opportunity.rect.start_offset.block_offset +
          fragment_margins.block_start;
      const auto* break_token = To<BlockBreakToken>(
          layout_result->GetPhysicalFragment().GetBreakToken());
      bool is_at_block_end = !break_token || break_token->IsAtBlockEnd();
      if (!is_at_block_end) {
        // We need to resume in the next fragmentainer (or even push the whole
        // thing there), which means that there'll be no block-end margin here.
        fragment_margins.block_end = LayoutUnit();
      }

      if (!MovePastBreakpoint(parent_space, node, *layout_result,
                              fragmentainer_block_offset,
                              fragmentainer_block_size, kBreakAppealPerfect,
                              /*builder=*/nullptr)) {
        need_break_before = true;
      } else if (is_at_block_end &&
                 parent_space.HasKnownFragmentainerBlockSize()) {
        LogicalFragment float_fragment(parent_space.GetWritingDirection(),
                                       layout_result->GetPhysicalFragment());
        LayoutUnit outer_block_end = fragmentainer_block_offset +
                                     float_fragment.BlockSize() +
                                     fragment_margins.block_end;
        if (outer_block_end > fragmentainer_block_size &&
            !IsBreakInside(unpositioned_float->token)) {
          // Avoid breaking inside the block-end margin of a float. They are not
          // to collapse with the fragmentainer boundary, unlike margins on
          // regular boxes.
          need_break_before = true;
        }
      }
    }
  }

  const auto& physical_fragment =
      To<PhysicalBoxFragment>(layout_result->GetPhysicalFragment());
  LogicalFragment float_fragment(parent_space.GetWritingDirection(),
                                 physical_fragment);

  // Calculate the float's margin box BFC offset.
  BfcOffset 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);
  }

  if (parent_space.HasBlockFragmentation() && !need_break_before &&
      !IsBreakInside(unpositioned_float->token) &&
      exclusion_space->NeedsBreakBeforeFloat(
          unpositioned_float->ClearType(parent_space.Direction())))
    need_break_before = true;

  // Add the float as an exclusion.
  const auto float_type = node.Style().Floating(parent_space.Direction());
  if (need_break_before) {
    // Create a special exclusion past everything, so that the container(s) may
    // grow to encompass the floats, if appropriate.
    BfcOffset past_everything(LayoutUnit(),
                              unpositioned_float->FragmentainerSpaceLeft() +
                                  parent_space.ExpectedBfcBlockOffset());
    const ExclusionArea* exclusion = ExclusionArea::Create(
        BfcRect(past_everything, past_everything), float_type,
        unpositioned_float->is_hidden_for_paint);
    exclusion_space->Add(std::move(exclusion));

    // Also specify that there will be a fragmentainer break before this
    // float. This means that we cannot add any more floats to the current
    // fragmentainer (a float cannot start above any preceding float), and it
    // may also affect clearance.
    exclusion_space->SetHasBreakBeforeFloat(float_type);
  } else {
    const ExclusionArea* exclusion =
        CreateExclusionArea(float_fragment, float_margin_bfc_offset,
                            fragment_margins, *unpositioned_float, float_type);
    exclusion_space->Add(std::move(exclusion));

    // If the float broke inside and will continue to take up layout space in
    // the next fragmentainer, it means that we cannot fit any subsequent
    // content that wants clearance past this float.
    if (const BlockBreakToken* break_token =
            physical_fragment.GetBreakToken()) {
      if (!break_token->IsAtBlockEnd())
        exclusion_space->SetHasBreakInsideFloat(float_type);
    }
  }

  // Adjust the float's bfc_offset to its border-box (instead of margin-box).
  BfcOffset 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);

  const BlockBreakToken* break_before_token = nullptr;
  if (need_break_before) {
    break_before_token =
        BlockBreakToken::CreateBreakBefore(node, /* is_forced_break */ false);
  }

  LayoutUnit minimum_space_shortage;
  if (break_before_token || physical_fragment.GetBreakToken()) {
    // Broke before or inside the float.
    if (parent_space.HasKnownFragmentainerBlockSize() &&
        parent_space.BlockFragmentationType() == kFragmentColumn) {
      LayoutUnit fragmentainer_block_offset =
          unpositioned_float->FragmentainerOffsetAtBfc() +
          float_bfc_offset.block_offset;
      minimum_space_shortage = CalculateSpaceShortage(
          parent_space, layout_result, fragmentainer_block_offset,
          fragmentainer_block_size);
    }
  }

  return PositionedFloat(layout_result, break_before_token, float_bfc_offset,
                         minimum_space_shortage);
}

}  // namespace blink