// 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_size.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 NGLogicalSize& float_available_size,
    const NGBfcOffset& origin_bfc_offset,
    const NGExclusionSpace& exclusion_space,
    const NGUnpositionedFloat& unpositioned_float,
    const NGBoxStrut& fragment_margins,
    const NGConstraintSpace& parent_space,
    LayoutUnit inline_size) {
  NGBfcOffset adjusted_origin_point =
      AdjustToTopEdgeAlignmentRule(exclusion_space, origin_bfc_offset);
  LayoutUnit clearance_offset = exclusion_space.ClearanceOffset(
      unpositioned_float.ClearType(parent_space.Direction()));

  AdjustToClearance(clearance_offset, &adjusted_origin_point);

  NGLogicalSize float_size(inline_size + fragment_margins.InlineSum(),
                           LayoutUnit());
  return exclusion_space.FindLayoutOpportunity(
      adjusted_origin_point, float_available_size.inline_size, float_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 NGLogicalSize& float_available_size,
    const NGLogicalSize& float_percentage_size,
    const NGLogicalSize& float_replaced_percentage_size,
    const NGUnpositionedFloat& unpositioned_float,
    const NGConstraintSpace& parent_space,
    const ComputedStyle& parent_style,
    base::Optional<LayoutUnit> origin_block_offset = base::nullopt) {
  const ComputedStyle& style = unpositioned_float.node.Style();
  NGConstraintSpaceBuilder builder(parent_space, style.GetWritingMode(),
                                   /* is_new_fc */ true);
  SetOrthogonalFallbackInlineSizeIfNeeded(parent_style, unpositioned_float.node,
                                          &builder);

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

    LayoutUnit fragmentation_offset =
        parent_space.FragmentainerSpaceAtBfcStart() -
        origin_block_offset.value();
    builder.SetFragmentainerBlockSize(parent_space.FragmentainerBlockSize());
    builder.SetFragmentainerSpaceAtBfcStart(fragmentation_offset);
    builder.SetFragmentationType(parent_space.BlockFragmentationType());
  } else {
    builder.SetFragmentationType(NGFragmentationType::kFragmentNone);
  }

  return builder.SetAvailableSize(float_available_size)
      .SetPercentageResolutionSize(float_percentage_size)
      .SetReplacedPercentageResolutionSize(float_replaced_percentage_size)
      .SetIsShrinkToFit(style.LogicalWidth().IsAuto())
      .SetTextDirection(style.Direction())
      .ToConstraintSpace();
}

std::unique_ptr<NGExclusionShapeData> CreateExclusionShapeData(
    const NGLogicalSize& float_available_size,
    const NGLogicalSize& float_percentage_size,
    const NGLogicalSize& float_replaced_percentage_size,
    const NGBoxStrut& margins,
    const LayoutBox* layout_box,
    const NGUnpositionedFloat& unpositioned_float,
    const NGConstraintSpace& parent_space,
    const ComputedStyle& parent_style) {
  DCHECK(layout_box->GetShapeOutsideInfo());
  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 = layout_box->StyleRef();
  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(
          float_available_size, float_percentage_size,
          float_replaced_percentage_size, unpositioned_float, parent_space,
          parent_style);
      NGBoxStrut strut = ComputeBorders(space, style);
      if (style.ShapeOutside()->CssBox() == CSSBoxType::kContent)
        strut += ComputePadding(space, style);
      shape_insets =
          strut.ConvertToPhysical(style.GetWritingMode(), style.Direction())
              .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<NGExclusion> CreateExclusion(
    const NGLogicalSize& float_available_size,
    const NGLogicalSize& float_percentage_size,
    const NGLogicalSize& float_replaced_percentage_size,
    const NGFragment& fragment,
    const NGBfcOffset& float_margin_bfc_offset,
    const NGBoxStrut& margins,
    const LayoutBox* layout_box,
    const NGUnpositionedFloat& unpositioned_float,
    const NGConstraintSpace& parent_space,
    const ComputedStyle& parent_style,
    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 =
      layout_box->GetShapeOutsideInfo()
          ? CreateExclusionShapeData(
                float_available_size, float_percentage_size,
                float_replaced_percentage_size, margins, layout_box,
                unpositioned_float, parent_space, parent_style)
          : 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(
    const NGLogicalSize& float_available_size,
    const NGLogicalSize& float_percentage_size,
    const NGLogicalSize& float_replaced_percentage_size,
    const NGConstraintSpace& parent_space,
    const ComputedStyle& parent_style,
    NGUnpositionedFloat* unpositioned_float) {
  if (unpositioned_float->layout_result)
    return;

  const NGConstraintSpace space = CreateConstraintSpaceForFloat(
      float_available_size, float_percentage_size,
      float_replaced_percentage_size, *unpositioned_float, parent_space,
      parent_style);

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

}  // namespace

LayoutUnit ComputeMarginBoxInlineSizeForUnpositionedFloat(
    const NGConstraintSpace& parent_space,
    const ComputedStyle& parent_style,
    NGUnpositionedFloat* unpositioned_float) {
  DCHECK(unpositioned_float);

  // NOTE: We can safely use the parent space's available and percentage size
  // as this function should only be called within an inline context.
  LayoutFloatWithoutFragmentation(
      parent_space.AvailableSize(), parent_space.PercentageResolutionSize(),
      parent_space.ReplacedPercentageResolutionSize(), parent_space,
      parent_style, unpositioned_float);
  DCHECK(unpositioned_float->layout_result);

  const auto* fragment = unpositioned_float->layout_result->PhysicalFragment();
  DCHECK(fragment);
  DCHECK(!fragment->BreakToken() || fragment->BreakToken()->IsFinished());

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

NGPositionedFloat PositionFloat(
    const NGLogicalSize& float_available_size,
    const NGLogicalSize& float_percentage_size,
    const NGLogicalSize& float_replaced_percentage_size,
    const NGBfcOffset& origin_bfc_offset,
    LayoutUnit parent_bfc_block_offset,
    NGUnpositionedFloat* unpositioned_float,
    const NGConstraintSpace& parent_space,
    const ComputedStyle& parent_style,
    NGExclusionSpace* exclusion_space) {
  DCHECK(unpositioned_float);

  bool is_same_writing_mode =
      unpositioned_float->node.Style().GetWritingMode() ==
      parent_space.GetWritingMode();

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

  scoped_refptr<NGLayoutResult> layout_result;
  NGBoxStrut fragment_margins;

  // We may be able to re-use the fragment from when we calculated the
  // inline-size, if there is no block fragmentation.
  if (!is_fragmentable) {
    LayoutFloatWithoutFragmentation(float_available_size, float_percentage_size,
                                    float_replaced_percentage_size,
                                    parent_space, parent_style,
                                    unpositioned_float);
    layout_result = unpositioned_float->layout_result;
    fragment_margins = unpositioned_float->margins;
  } else {
    NGConstraintSpace space = CreateConstraintSpaceForFloat(
        float_available_size, float_percentage_size,
        float_replaced_percentage_size, *unpositioned_float, parent_space,
        parent_style, origin_bfc_offset.block_offset);
    layout_result =
        unpositioned_float->node.Layout(space, unpositioned_float->token.get());
    fragment_margins = ComputeMarginsFor(
        space, unpositioned_float->node.Style(), parent_space);

    // Make the margins fragmentation aware.
    if (ShouldIgnoreBlockStartMargin(parent_space, unpositioned_float->node,
                                     unpositioned_float->token.get()))
      fragment_margins.block_start = LayoutUnit();
    if (const NGBreakToken* break_token =
            layout_result->PhysicalFragment()->BreakToken()) {
      if (!break_token->IsFinished())
        fragment_margins.block_end = LayoutUnit();
    }
  }

  DCHECK(layout_result->PhysicalFragment());
  NGFragment float_fragment(parent_space.GetWritingMode(),
                            *layout_result->PhysicalFragment());

  // Find a layout opportunity that will fit our float.
  NGLayoutOpportunity opportunity = FindLayoutOpportunityForFloat(
      float_available_size, origin_bfc_offset, *exclusion_space,
      *unpositioned_float, fragment_margins, parent_space,
      float_fragment.InlineSize());

  // 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.
  scoped_refptr<NGExclusion> exclusion = CreateExclusion(
      float_available_size, float_percentage_size,
      float_replaced_percentage_size, float_fragment, float_margin_bfc_offset,
      fragment_margins, unpositioned_float->node.GetLayoutBox(),
      *unpositioned_float, parent_space, parent_style,
      unpositioned_float->IsLineRight(parent_space.Direction())
          ? EFloat::kRight
          : EFloat::kLeft);
  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);
}

void PositionFloats(const NGLogicalSize& float_available_size,
                    const NGLogicalSize& float_percentage_size,
                    const NGLogicalSize& float_replaced_percentage_size,
                    const NGBfcOffset& origin_bfc_offset,
                    LayoutUnit parent_bfc_block_offset,
                    NGUnpositionedFloatVector& unpositioned_floats,
                    const NGConstraintSpace& parent_space,
                    const ComputedStyle& parent_style,
                    NGExclusionSpace* exclusion_space,
                    NGPositionedFloatVector* positioned_floats) {
  positioned_floats->ReserveCapacity(positioned_floats->size() +
                                     unpositioned_floats.size());

  for (NGUnpositionedFloat& unpositioned_float : unpositioned_floats) {
    positioned_floats->push_back(
        PositionFloat(float_available_size, float_percentage_size,
                      float_replaced_percentage_size, origin_bfc_offset,
                      parent_bfc_block_offset, &unpositioned_float,
                      parent_space, parent_style, exclusion_space));
  }
}

void AddUnpositionedFloat(NGUnpositionedFloatVector* unpositioned_floats,
                          NGContainerFragmentBuilder* fragment_builder,
                          NGUnpositionedFloat unpositioned_float,
                          const NGConstraintSpace& parent_space) {
  // The same float node should not be added more than once.
  DCHECK(
      !RemoveUnpositionedFloat(unpositioned_floats, unpositioned_float.node));

  if (fragment_builder && !fragment_builder->BfcBlockOffset()) {
    fragment_builder->AddAdjoiningFloatTypes(
        unpositioned_float.IsLineLeft(parent_space.Direction())
            ? kFloatTypeLeft
            : kFloatTypeRight);
  }
  unpositioned_floats->push_back(std::move(unpositioned_float));
}

bool RemoveUnpositionedFloat(NGUnpositionedFloatVector* unpositioned_floats,
                             NGBlockNode float_node) {
  for (NGUnpositionedFloat& unpositioned_float : *unpositioned_floats) {
    if (unpositioned_float.node == float_node) {
      unpositioned_floats->erase(&unpositioned_float);
      return true;
    }
  }
  return false;
}

NGFloatTypes ToFloatTypes(EClear clear) {
  switch (clear) {
    default:
      NOTREACHED();
      FALLTHROUGH;
    case EClear::kNone:
      return kFloatTypeNone;
    case EClear::kLeft:
      return kFloatTypeLeft;
    case EClear::kRight:
      return kFloatTypeRight;
    case EClear::kBoth:
      return kFloatTypeBoth;
  };
}

}  // namespace blink