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

  AdjustToClearance(clearance_offset, &adjusted_origin_point);

  NGLogicalSize float_size(inline_size + fragment_margins.InlineSum(),
                           LayoutUnit());
  return exclusion_space.FindLayoutOpportunity(
      adjusted_origin_point, unpositioned_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.
scoped_refptr<NGConstraintSpace> CreateConstraintSpaceForFloat(
    const NGUnpositionedFloat& unpositioned_float,
    const NGConstraintSpace& parent_space,
    base::Optional<LayoutUnit> origin_block_offset = base::nullopt) {
  const ComputedStyle& style = unpositioned_float.node.Style();
  NGConstraintSpaceBuilder builder(parent_space);

  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.SetPercentageResolutionSize(unpositioned_float.percentage_size)
      .SetAvailableSize(unpositioned_float.available_size)
      .SetIsNewFormattingContext(true)
      .SetIsShrinkToFit(true)
      .SetTextDirection(style.Direction())
      .ToConstraintSpace(style.GetWritingMode());
}

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

  // 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:
      shape_insets =
          ComputeBorders(
              *CreateConstraintSpaceForFloat(unpositioned_float, parent_space),
              style)
              .ConvertToPhysical(style.GetWritingMode(), style.Direction())
              .ConvertToLogical(parent_space.GetWritingMode(),
                                TextDirection::kLtr);
      break;
    case CSSBoxType::kContent:
      const scoped_refptr<NGConstraintSpace> space =
          CreateConstraintSpaceForFloat(unpositioned_float, parent_space);
      NGBoxStrut border_padding =
          ComputeBorders(*space, style) + ComputePadding(*space, style);
      shape_insets =
          border_padding
              .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 NGFragment& fragment,
    const NGBfcOffset& float_margin_bfc_offset,
    const NGBoxStrut& margins,
    const LayoutBox* layout_box,
    const NGUnpositionedFloat& unpositioned_float,
    const NGConstraintSpace& parent_space,
    TextDirection direction,
    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(margins, layout_box, unpositioned_float,
                                     parent_space, direction)
          : 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 NGConstraintSpace& parent_space,
                                     NGUnpositionedFloat* unpositioned_float) {
  if (unpositioned_float->layout_result)
    return;

  const scoped_refptr<NGConstraintSpace> space =
      CreateConstraintSpaceForFloat(*unpositioned_float, parent_space);

  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,
    NGUnpositionedFloat* unpositioned_float) {
  DCHECK(unpositioned_float);

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

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

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

NGPositionedFloat PositionFloat(LayoutUnit origin_block_offset,
                                LayoutUnit parent_bfc_block_offset,
                                NGUnpositionedFloat* unpositioned_float,
                                const NGConstraintSpace& parent_space,
                                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(parent_space, unpositioned_float);
    layout_result = unpositioned_float->layout_result;
    fragment_margins = unpositioned_float->margins;
  } else {
    scoped_refptr<NGConstraintSpace> space = CreateConstraintSpaceForFloat(
        *unpositioned_float, parent_space, origin_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 (!layout_result->PhysicalFragment()->BreakToken()->IsFinished())
      fragment_margins.block_end = LayoutUnit();
  }

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

  NGBfcOffset origin_offset = {unpositioned_float->origin_bfc_line_offset,
                               origin_block_offset};

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

  // Calculate the float's margin box BFC offset.
  NGBfcOffset float_margin_bfc_offset = opportunity.rect.start_offset;
  if (unpositioned_float->IsRight()) {
    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_fragment, float_margin_bfc_offset, fragment_margins,
      unpositioned_float->node.GetLayoutBox(), *unpositioned_float,
      parent_space, parent_space.Direction(),
      unpositioned_float->IsRight() ? 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);
}

const Vector<NGPositionedFloat> PositionFloats(
    LayoutUnit origin_block_offset,
    LayoutUnit parent_bfc_block_offset,
    NGUnpositionedFloatVector& unpositioned_floats,
    const NGConstraintSpace& space,
    NGExclusionSpace* exclusion_space) {
  Vector<NGPositionedFloat> positioned_floats;
  positioned_floats.ReserveCapacity(unpositioned_floats.size());

  for (NGUnpositionedFloat& unpositioned_float : unpositioned_floats) {
    positioned_floats.push_back(
        PositionFloat(origin_block_offset, parent_bfc_block_offset,
                      &unpositioned_float, space, exclusion_space));
  }

  return positioned_floats;
}

void AddUnpositionedFloat(NGUnpositionedFloatVector* unpositioned_floats,
                          NGContainerFragmentBuilder* fragment_builder,
                          NGUnpositionedFloat unpositioned_float) {
  // 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.IsLeft() ? 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