// Copyright 2018 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_flex_layout_algorithm.h"

#include <memory>
#include "third_party/blink/renderer/core/layout/flexible_box_algorithm.h"
#include "third_party/blink/renderer/core/layout/layout_box.h"
#include "third_party/blink/renderer/core/layout/layout_flexible_box.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_fragment.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_space_utils.h"
#include "third_party/blink/renderer/platform/wtf/vector.h"

namespace blink {

NGFlexLayoutAlgorithm::NGFlexLayoutAlgorithm(NGBlockNode node,
                                             const NGConstraintSpace& space,
                                             const NGBreakToken* break_token)
    : NGLayoutAlgorithm(node, space, ToNGBlockBreakToken(break_token)),
      border_scrollbar_padding_(
          CalculateBorderScrollbarPadding(ConstraintSpace(), Node())),
      borders_(ComputeBorders(ConstraintSpace(), Style())),
      padding_(ComputePadding(ConstraintSpace(), Style())),
      is_column_(Style().IsColumnFlexDirection()) {
  container_builder_.SetIsNewFormattingContext(space.IsNewFormattingContext());
}

bool NGFlexLayoutAlgorithm::MainAxisIsInlineAxis(NGBlockNode child) {
  return child.Style().IsHorizontalWritingMode() ==
         FlexLayoutAlgorithm::IsHorizontalFlow(Style());
}

LayoutUnit NGFlexLayoutAlgorithm::MainAxisContentExtent(
    LayoutUnit sum_hypothetical_main_size) {
  if (Style().IsColumnFlexDirection()) {
    return ComputeBlockSizeForFragment(
               ConstraintSpace(), Style(),
               sum_hypothetical_main_size + (borders_ + padding_).BlockSum()) -
           border_scrollbar_padding_.BlockSum();
  }
  return content_box_size_.inline_size;
}

void NGFlexLayoutAlgorithm::HandleOutOfFlowPositioned(NGBlockNode child) {
  // TODO(dgrogan): There's stuff from
  // https://www.w3.org/TR/css-flexbox-1/#abspos-items that isn't done here.
  // Specifically, neither rtl nor alignment is handled here, at least.
  // Look at LayoutFlexibleBox::PrepareChildForPositionedLayout and
  // SetStaticPositionForPositionedLayout to see how to statically position
  // this.
  container_builder_.AddOutOfFlowChildCandidate(
      child, {border_scrollbar_padding_.inline_start,
              border_scrollbar_padding_.block_start});
}

scoped_refptr<NGLayoutResult> NGFlexLayoutAlgorithm::Layout() {
  // TODO(dgrogan): Pass padding+borders as optimization.
  border_box_size_ = CalculateBorderBoxSize(ConstraintSpace(), Node());
  content_box_size_ =
      ShrinkAvailableSize(border_box_size_, border_scrollbar_padding_);

  const LayoutUnit line_break_length = MainAxisContentExtent(LayoutUnit::Max());
  FlexLayoutAlgorithm algorithm(&Style(), line_break_length);
  const bool is_horizontal_flow = algorithm.IsHorizontalFlow();

  for (NGLayoutInputNode generic_child = Node().FirstChild(); generic_child;
       generic_child = generic_child.NextSibling()) {
    NGBlockNode child = ToNGBlockNode(generic_child);
    if (child.IsOutOfFlowPositioned()) {
      HandleOutOfFlowPositioned(child);
      continue;
    }

    const ComputedStyle& child_style = child.Style();
    NGConstraintSpaceBuilder space_builder(ConstraintSpace(),
                                           child_style.GetWritingMode(),
                                           /* is_new_fc */ true);
    SetOrthogonalFallbackInlineSizeIfNeeded(Style(), child, &space_builder);

    // TODO(dgrogan): Set IsShrinkToFit here when cross axis size is auto, at
    // least for correctness. For perf, don't set it if the item will later be
    // stretched or we won't hit the cache later.
    NGConstraintSpace child_space =
        space_builder.SetAvailableSize(content_box_size_)
            .SetPercentageResolutionSize(content_box_size_)
            .ToConstraintSpace();

    NGBoxStrut border_padding_in_child_writing_mode =
        ComputeBorders(child_space, child_style) +
        ComputePadding(child_space, child_style);
    NGPhysicalBoxStrut physical_border_padding(
        border_padding_in_child_writing_mode.ConvertToPhysical(
            child_style.GetWritingMode(), child_style.Direction()));
    LayoutUnit main_axis_border_and_padding =
        is_horizontal_flow ? physical_border_padding.HorizontalSum()
                           : physical_border_padding.VerticalSum();

    // We want the child's min/max size in its writing mode, not ours. We'll
    // only ever use it if the child's inline axis is our main axis.
    MinMaxSizeInput zero_input;
    MinMaxSize min_max_sizes_border_box = child.ComputeMinMaxSize(
        child_style.GetWritingMode(), zero_input, &child_space);
    // TODO(dgrogan): Don't layout every time, just when you need to.
    scoped_refptr<NGLayoutResult> layout_result =
        child.Layout(child_space, nullptr /*break token*/);
    NGFragment fragment_in_child_writing_mode(
        child_style.GetWritingMode(), *layout_result->PhysicalFragment());

    LayoutUnit flex_base_border_box;
    Length length_in_main_axis =
        is_horizontal_flow ? child_style.Width() : child_style.Height();
    if (child_style.FlexBasis().IsAuto() && length_in_main_axis.IsAuto()) {
      if (MainAxisIsInlineAxis(child))
        flex_base_border_box = min_max_sizes_border_box.max_size;
      else
        flex_base_border_box = fragment_in_child_writing_mode.BlockSize();
    } else {
      Length length_to_resolve = child_style.FlexBasis();
      if (length_to_resolve.IsAuto())
        length_to_resolve = length_in_main_axis;
      DCHECK(!length_to_resolve.IsAuto());

      if (MainAxisIsInlineAxis(child)) {
        flex_base_border_box = ResolveInlineLength(
            child_space, child_style, min_max_sizes_border_box,
            length_to_resolve, LengthResolveType::kContentSize,
            LengthResolvePhase::kLayout);
      } else {
        // Flex container's main axis is in child's block direction. Child's
        // flex basis is in child's block direction.
        flex_base_border_box = ResolveBlockLength(
            child_space, child_style, length_to_resolve,
            fragment_in_child_writing_mode.BlockSize(),
            LengthResolveType::kContentSize, LengthResolvePhase::kLayout);
      }
    }

    // Spec calls this "flex base size"
    // https://www.w3.org/TR/css-flexbox-1/#algo-main-item
    // Blink's FlexibleBoxAlgorithm expects it to be content + scrollbar widths,
    // but no padding or border.
    LayoutUnit flex_base_content_size =
        flex_base_border_box - main_axis_border_and_padding;

    NGPhysicalBoxStrut physical_child_margins =
        ComputePhysicalMargins(child_space, child_style);
    LayoutUnit main_axis_margin = is_horizontal_flow
                                      ? physical_child_margins.HorizontalSum()
                                      : physical_child_margins.VerticalSum();

    MinMaxSize min_max_sizes_in_main_axis_direction{LayoutUnit(),
                                                    LayoutUnit::Max()};
    Length max = is_horizontal_flow ? child.Style().MaxWidth()
                                    : child.Style().MaxHeight();
    if (MainAxisIsInlineAxis(child)) {
      min_max_sizes_in_main_axis_direction.max_size = ResolveInlineLength(
          child_space, child_style, min_max_sizes_border_box, max,
          LengthResolveType::kMaxSize, LengthResolvePhase::kLayout);
    } else {
      min_max_sizes_in_main_axis_direction.max_size = ResolveBlockLength(
          child_space, child_style, max,
          fragment_in_child_writing_mode.BlockSize(),
          LengthResolveType::kMaxSize, LengthResolvePhase::kLayout);
    }

    Length min = is_horizontal_flow ? child.Style().MinWidth()
                                    : child.Style().MinHeight();
    if (min.IsAuto()) {
      if (algorithm.ShouldApplyMinSizeAutoForChild(*child.GetLayoutBox())) {
        // TODO(dgrogan): Port logic from
        // https://www.w3.org/TR/css-flexbox-1/#min-size-auto and
        // LayoutFlexibleBox::ComputeMinAndMaxSizesForChild
      }
    } else if (MainAxisIsInlineAxis(child)) {
      min_max_sizes_in_main_axis_direction.min_size = ResolveInlineLength(
          child_space, child_style, min_max_sizes_border_box, min,
          LengthResolveType::kMinSize, LengthResolvePhase::kLayout);
    } else {
      min_max_sizes_in_main_axis_direction.min_size = ResolveBlockLength(
          child_space, child_style, min,
          fragment_in_child_writing_mode.BlockSize(),
          LengthResolveType::kMinSize, LengthResolvePhase::kLayout);
    }

    algorithm
        .emplace_back(child.GetLayoutBox(), flex_base_content_size,
                      min_max_sizes_in_main_axis_direction,
                      main_axis_border_and_padding, main_axis_margin)
        .ng_input_node = child;
  }

  LayoutUnit main_axis_offset = border_scrollbar_padding_.inline_start;
  LayoutUnit cross_axis_offset = border_scrollbar_padding_.block_start;
  if (is_column_) {
    main_axis_offset = border_scrollbar_padding_.block_start;
    cross_axis_offset = border_scrollbar_padding_.inline_start;
  }
  FlexLine* line;
  LayoutUnit max_main_axis_extent;
  while ((line = algorithm.ComputeNextFlexLine(border_box_size_.inline_size))) {
    line->SetContainerMainInnerSize(
        MainAxisContentExtent(line->sum_hypothetical_main_size));
    line->FreezeInflexibleItems();
    while (!line->ResolveFlexibleLengths()) {
      continue;
    }
    for (wtf_size_t i = 0; i < line->line_items.size(); ++i) {
      FlexItem& flex_item = line->line_items[i];

      WritingMode child_writing_mode =
          flex_item.ng_input_node.Style().GetWritingMode();
      NGConstraintSpaceBuilder space_builder(ConstraintSpace(),
                                             child_writing_mode,
                                             /* is_new_fc */ true);
      SetOrthogonalFallbackInlineSizeIfNeeded(Style(), flex_item.ng_input_node,
                                              &space_builder);

      NGLogicalSize available_size;
      if (is_column_) {
        available_size.inline_size = content_box_size_.inline_size;
        available_size.block_size = flex_item.flexed_content_size +
                                    flex_item.main_axis_border_and_padding;
        space_builder.SetIsFixedSizeBlock(true);
      } else {
        available_size.inline_size = flex_item.flexed_content_size +
                                     flex_item.main_axis_border_and_padding;
        available_size.block_size = content_box_size_.block_size;
        space_builder.SetIsFixedSizeInline(true);
      }
      space_builder.SetAvailableSize(available_size);
      space_builder.SetPercentageResolutionSize(content_box_size_);
      NGConstraintSpace child_space = space_builder.ToConstraintSpace();
      flex_item.layout_result =
          flex_item.ng_input_node.Layout(child_space, nullptr /*break token*/);
      flex_item.cross_axis_size =
          is_horizontal_flow
              ? flex_item.layout_result->PhysicalFragment()->Size().height
              : flex_item.layout_result->PhysicalFragment()->Size().width;
      // TODO(dgrogan): Port logic from
      // LayoutFlexibleBox::CrossAxisIntrinsicExtentForChild?
      flex_item.cross_axis_intrinsic_size = flex_item.cross_axis_size;
    }
    // cross_axis_offset is updated in each iteration of the loop, for passing
    // in to the next iteration.
    line->ComputeLineItemsPosition(main_axis_offset, cross_axis_offset);
    max_main_axis_extent =
        std::max(max_main_axis_extent, line->main_axis_extent);
  }
  LayoutUnit intrinsic_block_content_size =
      is_column_ ? max_main_axis_extent
                 : cross_axis_offset - border_scrollbar_padding_.block_start;
  LayoutUnit intrinsic_block_size =
      intrinsic_block_content_size + border_scrollbar_padding_.BlockSum();
  LayoutUnit block_size = ComputeBlockSizeForFragment(
      ConstraintSpace(), Style(), intrinsic_block_size);

  // Apply stretch alignment.
  // TODO(dgrogan): Move this to its own method, which means making some of the
  // container-specific local variables into data members.
  LayoutUnit final_content_cross_size =
      block_size - border_scrollbar_padding_.BlockSum();
  if (is_column_) {
    final_content_cross_size =
        border_box_size_.inline_size - border_scrollbar_padding_.InlineSum();
  }
  if (!algorithm.IsMultiline() && !algorithm.FlexLines().IsEmpty())
    algorithm.FlexLines()[0].cross_axis_extent = final_content_cross_size;

  for (FlexLine& line_context : algorithm.FlexLines()) {
    for (wtf_size_t child_number = 0;
         child_number < line_context.line_items.size(); ++child_number) {
      FlexItem& flex_item = line_context.line_items[child_number];
      if (flex_item.Alignment() == ItemPosition::kStretch) {
        flex_item.ComputeStretchedSize();

        WritingMode child_writing_mode =
            flex_item.ng_input_node.Style().GetWritingMode();
        NGConstraintSpaceBuilder space_builder(ConstraintSpace(),
                                               child_writing_mode,
                                               /* is_new_fc */ true);
        SetOrthogonalFallbackInlineSizeIfNeeded(
            Style(), flex_item.ng_input_node, &space_builder);

        NGLogicalSize available_size(flex_item.flexed_content_size +
                                         flex_item.main_axis_border_and_padding,
                                     flex_item.cross_axis_size);
        if (is_column_)
          available_size.Flip();
        space_builder.SetAvailableSize(available_size);
        space_builder.SetPercentageResolutionSize(content_box_size_);
        space_builder.SetIsFixedSizeInline(true);
        space_builder.SetIsFixedSizeBlock(true);
        NGConstraintSpace child_space = space_builder.ToConstraintSpace();
        flex_item.layout_result = flex_item.ng_input_node.Layout(
            child_space, /* break_token */ nullptr);
      }
      container_builder_.AddChild(
          *flex_item.layout_result,
          {flex_item.desired_location.X(), flex_item.desired_location.Y()});
    }
  }

  container_builder_.SetBlockSize(block_size);
  container_builder_.SetInlineSize(border_box_size_.inline_size);
  container_builder_.SetBorders(ComputeBorders(ConstraintSpace(), Style()));
  container_builder_.SetPadding(ComputePadding(ConstraintSpace(), Style()));

  NGOutOfFlowLayoutPart(&container_builder_, Node().IsAbsoluteContainer(),
                        Node().IsFixedContainer(),
                        borders_ + Node().GetScrollbarSizes(),
                        ConstraintSpace(), Style())
      .Run();

  return container_builder_.ToBoxFragment();
}

base::Optional<MinMaxSize> NGFlexLayoutAlgorithm::ComputeMinMaxSize(
    const MinMaxSizeInput& input) const {
  MinMaxSize sizes;
  if (Node().ShouldApplySizeContainment()) {
    // TODO(dgrogan): When this code was written it didn't make any more tests
    // pass, so it may be wrong or untested.
    if (input.size_type == NGMinMaxSizeType::kBorderBoxSize)
      sizes = border_scrollbar_padding_.InlineSum();
    return sizes;
  }

  for (NGLayoutInputNode generic_child = Node().FirstChild(); generic_child;
       generic_child = generic_child.NextSibling()) {
    NGBlockNode child = ToNGBlockNode(generic_child);
    if (child.IsOutOfFlowPositioned())
      continue;
    // Use default MinMaxSizeInput:
    //   - Children of flexbox ignore any specified float properties, so
    //     children never have to take floated siblings into account, and
    //     external floats don't make it through the new formatting context that
    //     flexbox establishes.
    //   - We want the child's border box MinMaxSize, which is the default.
    MinMaxSize child_min_max_sizes =
        ComputeMinAndMaxContentContribution(Style(), child, MinMaxSizeInput());
    NGBoxStrut child_margins = ComputeMinMaxMargins(Style(), child);
    child_min_max_sizes += child_margins.InlineSum();
    if (is_column_) {
      sizes.min_size = std::max(sizes.min_size, child_min_max_sizes.min_size);
      sizes.max_size = std::max(sizes.max_size, child_min_max_sizes.max_size);
    } else {
      sizes.max_size += child_min_max_sizes.max_size;
      if (IsMultiline())
        sizes.min_size = std::max(sizes.min_size, child_min_max_sizes.min_size);
      else
        sizes.min_size += child_min_max_sizes.min_size;
    }
  }
  sizes.max_size = std::max(sizes.max_size, sizes.min_size);

  // Due to negative margins, it is possible that we calculated a negative
  // intrinsic width. Make sure that we never return a negative width.
  sizes.Encompass(LayoutUnit());

  if (input.size_type == NGMinMaxSizeType::kBorderBoxSize)
    sizes += border_scrollbar_padding_.InlineSum();

  return sizes;
}

bool NGFlexLayoutAlgorithm::IsMultiline() const {
  return Style().FlexWrap() != EFlexWrap::kNowrap;
}

}  // namespace blink