// Copyright 2015 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 "core/layout/ColumnBalancer.h"

#include "core/layout/LayoutMultiColumnFlowThread.h"
#include "core/layout/LayoutMultiColumnSet.h"
#include "core/layout/api/LineLayoutBlockFlow.h"

namespace blink {

ColumnBalancer::ColumnBalancer(const LayoutMultiColumnSet& columnSet,
                               LayoutUnit logicalTopInFlowThread,
                               LayoutUnit logicalBottomInFlowThread)
    : m_columnSet(columnSet),
      m_logicalTopInFlowThread(logicalTopInFlowThread),
      m_logicalBottomInFlowThread(logicalBottomInFlowThread) {
  DCHECK_GE(columnSet.usedColumnCount(), 1U);
}

void ColumnBalancer::traverse() {
  traverseSubtree(*columnSet().flowThread());
  ASSERT(!flowThreadOffset());
}

void ColumnBalancer::traverseSubtree(const LayoutBox& box) {
  if (box.childrenInline() && box.isLayoutBlockFlow()) {
    // Look for breaks between lines.
    traverseLines(toLayoutBlockFlow(box));
  }

  // Look for breaks between and inside block-level children. Even if this is a
  // block flow with inline children, there may be interesting floats to examine
  // here.
  traverseChildren(box);
}

void ColumnBalancer::traverseLines(const LayoutBlockFlow& blockFlow) {
  for (const RootInlineBox* line = blockFlow.firstRootBox(); line;
       line = line->nextRootBox()) {
    LayoutUnit lineTopInFlowThread =
        m_flowThreadOffset + line->lineTopWithLeading();
    if (lineTopInFlowThread < logicalTopInFlowThread())
      continue;
    if (lineTopInFlowThread >= logicalBottomInFlowThread())
      break;
    examineLine(*line);
  }
}

void ColumnBalancer::traverseChildren(const LayoutObject& object) {
  // The break-after value from the previous in-flow block-level object to be
  // joined with the break-before value of the next in-flow block-level sibling.
  EBreakBetween previousBreakAfterValue = EBreakBetween::kAuto;

  for (const LayoutObject* child = object.slowFirstChild(); child;
       child = child->nextSibling()) {
    if (!child->isBox()) {
      // Keep traversing inside inlines. There may be floats there.
      if (child->isLayoutInline())
        traverseChildren(*child);
      continue;
    }

    const LayoutBox& childBox = toLayoutBox(*child);

    LayoutUnit borderEdgeOffset;
    LayoutUnit logicalTop = childBox.logicalTop();
    LayoutUnit logicalHeight = childBox.logicalHeightWithVisibleOverflow();
    // Floats' margins don't collapse with column boundaries, and we don't want
    // to break inside them, or separate them from the float's border box. Set
    // the offset to the margin-before edge (rather than border-before edge),
    // and include the block direction margins in the child height.
    if (childBox.isFloating()) {
      LayoutUnit marginBefore = childBox.marginBefore(object.style());
      LayoutUnit marginAfter = childBox.marginAfter(object.style());
      logicalHeight =
          std::max(logicalHeight, childBox.logicalHeight() + marginAfter);
      logicalTop -= marginBefore;
      logicalHeight += marginBefore;

      // As soon as we want to process content inside this child, though, we
      // need to get to its border-before edge.
      borderEdgeOffset = marginBefore;
    }

    if (m_flowThreadOffset + logicalTop + logicalHeight <=
        logicalTopInFlowThread()) {
      // This child is fully above the flow thread portion we're examining.
      continue;
    }
    if (m_flowThreadOffset + logicalTop >= logicalBottomInFlowThread()) {
      // This child is fully below the flow thread portion we're examining. We
      // cannot just stop here, though, thanks to negative margins.
      // So keep looking.
      continue;
    }
    if (childBox.isOutOfFlowPositioned() || childBox.isColumnSpanAll())
      continue;

    // Tables are wicked. Both table rows and table cells are relative to their
    // table section.
    LayoutUnit offsetForThisChild =
        childBox.isTableRow() ? LayoutUnit() : logicalTop;

    m_flowThreadOffset += offsetForThisChild;

    examineBoxAfterEntering(childBox, logicalHeight, previousBreakAfterValue);
    // Unless the child is unsplittable, or if the child establishes an inner
    // multicol container, we descend into its subtree for further examination.
    if (childBox.getPaginationBreakability() != LayoutBox::ForbidBreaks &&
        (!childBox.isLayoutBlockFlow() ||
         !toLayoutBlockFlow(childBox).multiColumnFlowThread())) {
      // We need to get to the border edge before processing content inside
      // this child. If the child is floated, we're currently at the margin
      // edge.
      m_flowThreadOffset += borderEdgeOffset;
      traverseSubtree(childBox);
      m_flowThreadOffset -= borderEdgeOffset;
    }
    previousBreakAfterValue = childBox.breakAfter();
    examineBoxBeforeLeaving(childBox, logicalHeight);

    m_flowThreadOffset -= offsetForThisChild;
  }
}

InitialColumnHeightFinder::InitialColumnHeightFinder(
    const LayoutMultiColumnSet& columnSet,
    LayoutUnit logicalTopInFlowThread,
    LayoutUnit logicalBottomInFlowThread)
    : ColumnBalancer(columnSet,
                     logicalTopInFlowThread,
                     logicalBottomInFlowThread) {
  m_shortestStruts.resize(columnSet.usedColumnCount());
  for (auto& strut : m_shortestStruts)
    strut = LayoutUnit::max();
  traverse();
  // We have now found each explicit / forced break, and their location. Now we
  // need to figure out how many additional implicit / soft breaks we need and
  // guess where they will occur, in order
  // to provide an initial column height.
  distributeImplicitBreaks();
}

LayoutUnit InitialColumnHeightFinder::initialMinimalBalancedHeight() const {
  LayoutUnit rowLogicalTop;
  if (m_contentRuns.size() > columnSet().usedColumnCount()) {
    // We have not inserted additional fragmentainer groups yet (because we
    // aren't able to calculate their constraints yet), but we already know for
    // sure that there'll be more than one of them, due to the number of forced
    // breaks in a nested multicol container. We will now attempt to take all
    // the imaginary rows into account and calculate a minimal balanced logical
    // height for everything.
    unsigned stride = columnSet().usedColumnCount();
    LayoutUnit rowStartOffset = logicalTopInFlowThread();
    for (unsigned i = 0; i < firstContentRunIndexInLastRow(); i += stride) {
      LayoutUnit rowEndOffset = m_contentRuns[i + stride - 1].breakOffset();
      float rowHeight = float(rowEndOffset - rowStartOffset) / float(stride);
      rowLogicalTop += LayoutUnit::fromFloatCeil(rowHeight);
      rowStartOffset = rowEndOffset;
    }
  }
  unsigned index = contentRunIndexWithTallestColumns();
  LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset()
                                     : logicalTopInFlowThread();
  LayoutUnit height = m_contentRuns[index].columnLogicalHeight(startOffset);
  return rowLogicalTop + std::max(height, m_tallestUnbreakableLogicalHeight);
}

void InitialColumnHeightFinder::examineBoxAfterEntering(
    const LayoutBox& box,
    LayoutUnit childLogicalHeight,
    EBreakBetween previousBreakAfterValue) {
  if (m_lastBreakSeen > flowThreadOffset()) {
    // We have moved backwards. We're probably in a parallel flow, caused by
    // floats, sibling table cells, etc.
    m_lastBreakSeen = LayoutUnit();
  }
  if (isLogicalTopWithinBounds(flowThreadOffset() - box.paginationStrut())) {
    if (box.needsForcedBreakBefore(previousBreakAfterValue)) {
      addContentRun(flowThreadOffset());
    } else if (isFirstAfterBreak(flowThreadOffset()) &&
               m_lastBreakSeen != flowThreadOffset()) {
      // This box is first after a soft break.
      m_lastBreakSeen = flowThreadOffset();
      recordStrutBeforeOffset(flowThreadOffset(), box.paginationStrut());
    }
  }

  if (box.getPaginationBreakability() != LayoutBox::AllowAnyBreaks) {
    m_tallestUnbreakableLogicalHeight =
        std::max(m_tallestUnbreakableLogicalHeight, childLogicalHeight);
    return;
  }
  // Need to examine inner multicol containers to find their tallest unbreakable
  // piece of content.
  if (!box.isLayoutBlockFlow())
    return;
  LayoutMultiColumnFlowThread* innerFlowThread =
      toLayoutBlockFlow(box).multiColumnFlowThread();
  if (!innerFlowThread || innerFlowThread->isLayoutPagedFlowThread())
    return;
  LayoutUnit offsetInInnerFlowThread =
      flowThreadOffset() -
      innerFlowThread->blockOffsetInEnclosingFragmentationContext();
  LayoutUnit innerUnbreakableHeight =
      innerFlowThread->tallestUnbreakableLogicalHeight(offsetInInnerFlowThread);
  m_tallestUnbreakableLogicalHeight =
      std::max(m_tallestUnbreakableLogicalHeight, innerUnbreakableHeight);
}

void InitialColumnHeightFinder::examineBoxBeforeLeaving(
    const LayoutBox& box,
    LayoutUnit childLogicalHeight) {}

static inline LayoutUnit columnLogicalHeightRequirementForLine(
    const ComputedStyle& style,
    const RootInlineBox& lastLine) {
  // We may require a certain minimum number of lines per page in order to
  // satisfy orphans and widows, and that may affect the minimum page height.
  unsigned minimumLineCount =
      std::max<unsigned>(style.orphans(), style.widows());
  const RootInlineBox* firstLine = &lastLine;
  for (unsigned i = 1; i < minimumLineCount && firstLine->prevRootBox(); i++)
    firstLine = firstLine->prevRootBox();
  return lastLine.lineBottomWithLeading() - firstLine->lineTopWithLeading();
}

void InitialColumnHeightFinder::examineLine(const RootInlineBox& line) {
  LayoutUnit lineTop = line.lineTopWithLeading();
  LayoutUnit lineTopInFlowThread = flowThreadOffset() + lineTop;
  LayoutUnit minimumLogialHeight =
      columnLogicalHeightRequirementForLine(line.block().styleRef(), line);
  m_tallestUnbreakableLogicalHeight =
      std::max(m_tallestUnbreakableLogicalHeight, minimumLogialHeight);
  ASSERT(
      isFirstAfterBreak(lineTopInFlowThread) || !line.paginationStrut() ||
      !isLogicalTopWithinBounds(lineTopInFlowThread - line.paginationStrut()));
  if (isFirstAfterBreak(lineTopInFlowThread) &&
      m_lastBreakSeen != lineTopInFlowThread) {
    m_lastBreakSeen = lineTopInFlowThread;
    recordStrutBeforeOffset(lineTopInFlowThread, line.paginationStrut());
  }
}

void InitialColumnHeightFinder::recordStrutBeforeOffset(
    LayoutUnit offsetInFlowThread,
    LayoutUnit strut) {
  unsigned columnCount = columnSet().usedColumnCount();
  ASSERT(m_shortestStruts.size() == columnCount);
  unsigned index = groupAtOffset(offsetInFlowThread)
                       .columnIndexAtOffset(offsetInFlowThread - strut,
                                            LayoutBox::AssociateWithFormerPage);
  if (index >= columnCount)
    return;
  m_shortestStruts[index] = std::min(m_shortestStruts[index], strut);
}

LayoutUnit InitialColumnHeightFinder::spaceUsedByStrutsAt(
    LayoutUnit offsetInFlowThread) const {
  unsigned stopBeforeColumn =
      groupAtOffset(offsetInFlowThread)
          .columnIndexAtOffset(offsetInFlowThread,
                               LayoutBox::AssociateWithLatterPage) +
      1;
  stopBeforeColumn = std::min(stopBeforeColumn, columnSet().usedColumnCount());
  ASSERT(stopBeforeColumn <= m_shortestStruts.size());
  LayoutUnit totalStrutSpace;
  for (unsigned i = 0; i < stopBeforeColumn; i++) {
    if (m_shortestStruts[i] != LayoutUnit::max())
      totalStrutSpace += m_shortestStruts[i];
  }
  return totalStrutSpace;
}

void InitialColumnHeightFinder::addContentRun(
    LayoutUnit endOffsetInFlowThread) {
  endOffsetInFlowThread -= spaceUsedByStrutsAt(endOffsetInFlowThread);
  if (!m_contentRuns.isEmpty() &&
      endOffsetInFlowThread <= m_contentRuns.back().breakOffset())
    return;
  // Append another item as long as we haven't exceeded used column count. What
  // ends up in the overflow area shouldn't affect column balancing. However, if
  // we're in a nested fragmentation context, we may still need to record all
  // runs, since there'll be no overflow area in the inline direction then, but
  // rather additional rows of columns in multiple outer fragmentainers.
  if (m_contentRuns.size() >= columnSet().usedColumnCount()) {
    const auto* flowThread = columnSet().multiColumnFlowThread();
    if (!flowThread->enclosingFragmentationContext() ||
        columnSet().newFragmentainerGroupsAllowed())
      return;
  }
  m_contentRuns.push_back(ContentRun(endOffsetInFlowThread));
}

unsigned InitialColumnHeightFinder::contentRunIndexWithTallestColumns() const {
  unsigned indexWithLargestHeight = 0;
  LayoutUnit largestHeight;
  LayoutUnit previousOffset = logicalTopInFlowThread();
  size_t runCount = m_contentRuns.size();
  ASSERT(runCount);
  for (size_t i = firstContentRunIndexInLastRow(); i < runCount; i++) {
    const ContentRun& run = m_contentRuns[i];
    LayoutUnit height = run.columnLogicalHeight(previousOffset);
    if (largestHeight < height) {
      largestHeight = height;
      indexWithLargestHeight = i;
    }
    previousOffset = run.breakOffset();
  }
  return indexWithLargestHeight;
}

void InitialColumnHeightFinder::distributeImplicitBreaks() {
  // Insert a final content run to encompass all content. This will include
  // overflow if we're at the end of the multicol container.
  addContentRun(logicalBottomInFlowThread());
  unsigned columnCount = m_contentRuns.size();

  // If there is room for more breaks (to reach the used value of column-count),
  // imagine that we insert implicit breaks at suitable locations. At any given
  // time, the content run with the currently tallest columns will get another
  // implicit break "inserted", which will increase its column count by one and
  // shrink its columns' height. Repeat until we have the desired total number
  // of breaks. The largest column height among the runs will then be the
  // initial column height for the balancer to use.
  if (columnCount > columnSet().usedColumnCount()) {
    // If we exceed used column-count (which we are allowed to do if we're at
    // the initial balancing pass for a multicol that lives inside another
    // to-be-balanced outer multicol container), we only care about content that
    // could end up in the last row. We need to pad up the number of columns, so
    // that all rows will contain as many columns as used column-count dictates.
    columnCount %= columnSet().usedColumnCount();
    // If there are just enough explicit breaks to fill all rows with the right
    // amount of columns, we won't be needing any implicit breaks.
    if (!columnCount)
      return;
  }
  while (columnCount < columnSet().usedColumnCount()) {
    unsigned index = contentRunIndexWithTallestColumns();
    m_contentRuns[index].assumeAnotherImplicitBreak();
    columnCount++;
  }
}

MinimumSpaceShortageFinder::MinimumSpaceShortageFinder(
    const LayoutMultiColumnSet& columnSet,
    LayoutUnit logicalTopInFlowThread,
    LayoutUnit logicalBottomInFlowThread)
    : ColumnBalancer(columnSet,
                     logicalTopInFlowThread,
                     logicalBottomInFlowThread),
      m_minimumSpaceShortage(LayoutUnit::max()),
      m_pendingStrut(LayoutUnit::min()),
      m_forcedBreaksCount(0) {
  traverse();
}

void MinimumSpaceShortageFinder::examineBoxAfterEntering(
    const LayoutBox& box,
    LayoutUnit childLogicalHeight,
    EBreakBetween previousBreakAfterValue) {
  LayoutBox::PaginationBreakability breakability =
      box.getPaginationBreakability();

  // Look for breaks before the child box.
  if (isLogicalTopWithinBounds(flowThreadOffset() - box.paginationStrut())) {
    if (box.needsForcedBreakBefore(previousBreakAfterValue)) {
      m_forcedBreaksCount++;
    } else {
      if (isFirstAfterBreak(flowThreadOffset())) {
        // This box is first after a soft break.
        LayoutUnit strut = box.paginationStrut();
        // Figure out how much more space we would need to prevent it from being
        // pushed to the next column.
        recordSpaceShortage(childLogicalHeight - strut);
        if (breakability != LayoutBox::ForbidBreaks &&
            m_pendingStrut == LayoutUnit::min()) {
          // We now want to look for the first piece of unbreakable content
          // (e.g. a line or a block-displayed image) inside this block. That
          // ought to be a good candidate for minimum space shortage; a much
          // better one than reporting space shortage for the entire block
          // (which we'll also do (further down), in case we couldn't find
          // anything more suitable).
          m_pendingStrut = strut;
        }
      }
    }
  }

  if (breakability != LayoutBox::ForbidBreaks) {
    // See if this breakable box crosses column boundaries.
    LayoutUnit bottomInFlowThread = flowThreadOffset() + childLogicalHeight;
    const MultiColumnFragmentainerGroup& group =
        groupAtOffset(flowThreadOffset());
    if (isFirstAfterBreak(flowThreadOffset()) ||
        group.columnLogicalTopForOffset(flowThreadOffset()) !=
            group.columnLogicalTopForOffset(bottomInFlowThread)) {
      // If the child crosses a column boundary, record space shortage, in case
      // nothing inside it has already done so. The column balancer needs to
      // know by how much it has to stretch the columns to make more content
      // fit. If no breaks are reported (but do occur), the balancer will have
      // no clue. Only measure the space after the last column boundary, in case
      // it crosses more than one.
      LayoutUnit spaceUsedInLastColumn =
          bottomInFlowThread -
          group.columnLogicalTopForOffset(bottomInFlowThread);
      recordSpaceShortage(spaceUsedInLastColumn);
    }
  }

  // If this is an inner multicol container, look for space shortage inside it.
  if (!box.isLayoutBlockFlow())
    return;
  LayoutMultiColumnFlowThread* flowThread =
      toLayoutBlockFlow(box).multiColumnFlowThread();
  if (!flowThread || flowThread->isLayoutPagedFlowThread())
    return;
  for (const LayoutMultiColumnSet* columnSet =
           flowThread->firstMultiColumnSet();
       columnSet; columnSet = columnSet->nextSiblingMultiColumnSet()) {
    // Establish an inner shortage finder for this column set in the inner
    // multicol container. We need to let it walk through all fragmentainer
    // groups in one go, or we'd miss the column boundaries between each
    // fragmentainer group. We need to record space shortage there too.
    MinimumSpaceShortageFinder innerFinder(
        *columnSet, columnSet->logicalTopInFlowThread(),
        columnSet->logicalBottomInFlowThread());
    recordSpaceShortage(innerFinder.minimumSpaceShortage());
  }
}

void MinimumSpaceShortageFinder::examineBoxBeforeLeaving(
    const LayoutBox& box,
    LayoutUnit childLogicalHeight) {
  if (m_pendingStrut == LayoutUnit::min() ||
      box.getPaginationBreakability() != LayoutBox::ForbidBreaks)
    return;

  // The previous break was before a breakable block. Here's the first piece of
  // unbreakable content after / inside that block. We want to record the
  // distance from the top of the column to the bottom of this box as space
  // shortage.
  LayoutUnit logicalOffsetFromCurrentColumn =
      offsetFromColumnLogicalTop(flowThreadOffset());
  recordSpaceShortage(logicalOffsetFromCurrentColumn + childLogicalHeight -
                      m_pendingStrut);
  m_pendingStrut = LayoutUnit::min();
}

void MinimumSpaceShortageFinder::examineLine(const RootInlineBox& line) {
  LayoutUnit lineTop = line.lineTopWithLeading();
  LayoutUnit lineTopInFlowThread = flowThreadOffset() + lineTop;
  LayoutUnit lineHeight = line.lineBottomWithLeading() - lineTop;
  if (m_pendingStrut != LayoutUnit::min()) {
    // The previous break was before a breakable block. Here's the first line
    // after / inside that block. We want to record the distance from the top of
    // the column to the bottom of this box as space shortage.
    LayoutUnit logicalOffsetFromCurrentColumn =
        offsetFromColumnLogicalTop(lineTopInFlowThread);
    recordSpaceShortage(logicalOffsetFromCurrentColumn + lineHeight -
                        m_pendingStrut);
    m_pendingStrut = LayoutUnit::min();
    return;
  }
  ASSERT(
      isFirstAfterBreak(lineTopInFlowThread) || !line.paginationStrut() ||
      !isLogicalTopWithinBounds(lineTopInFlowThread - line.paginationStrut()));
  if (isFirstAfterBreak(lineTopInFlowThread))
    recordSpaceShortage(lineHeight - line.paginationStrut());

  // Even if the line box itself fits fine inside a column, some content may
  // overflow the line box bottom (due to restrictive line-height, for
  // instance). We should check if some portion of said overflow ends up in the
  // next column. That counts as space shortage.
  const MultiColumnFragmentainerGroup& group =
      groupAtOffset(lineTopInFlowThread);
  LayoutUnit lineBottomWithOverflow =
      lineTopInFlowThread + line.lineBottom() - lineTop;
  if (group.columnLogicalTopForOffset(lineTopInFlowThread) !=
      group.columnLogicalTopForOffset(lineBottomWithOverflow)) {
    LayoutUnit shortage =
        lineBottomWithOverflow -
        group.columnLogicalTopForOffset(lineBottomWithOverflow);
    recordSpaceShortage(shortage);
  }
}

}  // namespace blink