/*
 * Copyright 2022 Rive
 */

#include "rive/text_engine.hpp"
#include <limits>
#include <algorithm>
using namespace rive;

static bool autowidth(float width) { return width < 0.0f; }

float GlyphLine::ComputeMaxWidth(
    Span<GlyphLine> lines,
    Span<const GlyphRun> runs)
{
  float maxLineWidth = 0.0f;
  for (auto& line : lines)
  {
    maxLineWidth = std::max(
        maxLineWidth,
        runs[line.endRunIndex].xpos[line.endGlyphIndex] -
            runs[line.startRunIndex].xpos[line.startGlyphIndex]);
  }
  return maxLineWidth;
}

static const rive::Font::LineMetrics computeLineMetrics(
    const rive::Font::LineMetrics& metrics,
    float customLineHeight,
    float fontSize)
{
  if (customLineHeight < 0.0f)
  {
    return {metrics.ascent * fontSize, metrics.descent * fontSize};
  }
  float baseline = -metrics.ascent;
  float height = baseline + metrics.descent;
  float baselineFactor = baseline / height;

  float actualAscent = -baselineFactor * customLineHeight;

  return {actualAscent, customLineHeight + actualAscent};
}

void GlyphLine::ComputeLineSpacing(
    bool isFirstLine,
    Span<GlyphLine> lines,
    Span<const GlyphRun> runs,
    float width,
    TextAlign align)
{
  bool first = isFirstLine;
  float Y = 0; // top of our frame
  for (auto& line : lines)
  {
    float asc = 0;
    float realAscent = 0;
    float des = 0;
    float lh = 0;
    for (uint32_t i = line.startRunIndex; i <= line.endRunIndex; ++i)
    {
      const auto& run = runs[i];
      const auto& metrics = computeLineMetrics(
          run.font->lineMetrics(),
          run.lineHeight,
          run.size);
      realAscent = std::min(
          realAscent,
          run.font->lineMetrics().ascent * run.size);
      asc = std::min(asc, metrics.ascent);
      des = std::max(des, metrics.descent);
      if (run.lineHeight >= 0.0f)
      {
        lh = std::max(lh, run.lineHeight);
      }
      else
      {
        lh = std::max(lh, -asc + des);
      }
    }
    line.top = Y;
    if (first)
    {
      Y = -realAscent;
      first = false;
    }
    else
    {
      Y -= asc;
    }
    line.baseline = Y;
    Y += des;
    line.bottom = Y;

    auto lineWidth = runs[line.endRunIndex].xpos[line.endGlyphIndex] -
                     runs[line.startRunIndex].xpos[line.startGlyphIndex];
    switch (align)
    {
      case TextAlign::right:
        line.startX = width - lineWidth;
        break;
      case TextAlign::left:
        line.startX = 0;
        break;
      case TextAlign::center:
        line.startX = width / 2.0f - lineWidth / 2.0f;
        break;
    }
  }
}

struct WordMarker
{
  const GlyphRun* run;
  uint32_t index;

  bool next(Span<const GlyphRun> runs)
  {
    index += 2;
    while (index >= run->breaks.size())
    {
      index -= run->breaks.size();
      run++;
      if (run == runs.end())
      {
        return false;
      }
    }
    return true;
  }
};

class RunIterator
{
  Span<const GlyphRun> m_runs;
  const GlyphRun* m_run;
  uint32_t m_index;

public:
  RunIterator(Span<const GlyphRun> runs, const GlyphRun* run, uint32_t index)
      : m_runs(runs)
      , m_run(run)
      , m_index(index)
  {}

  bool back()
  {
    if (m_index == 0)
    {
      if (m_run == m_runs.begin())
      {
        return false;
      }
      m_run--;
      if (m_run->glyphs.size() == 0)
      {
        m_index = 0;
        return back();
      }
      else
      {
        m_index = m_run->glyphs.size() == 0
                      ? 0
                      : (uint32_t)m_run->glyphs.size() - 1;
      }
    }
    else
    {
      m_index--;
    }
    // Never stop inside a glyph cluster.
    while (m_index > 0 &&
           m_run->textIndices[m_index] == m_run->textIndices[m_index - 1])
    {
      m_index--;
    }
    // If there are any word-joiners, do not break on them and find the
    // closest index that does not wrap a WJ
    if (m_run->joiners.size() > 0 && m_run->textIndices[m_index] > 0)
    {
      auto joiners = m_run->joiners;
      auto wordJoinerIndex = m_run->textIndices[m_index] - 1;
      size_t mid = 0;
      size_t start = 0;
      size_t end = joiners.size();
      // If this condition is not met, skip to avoid binary search
      if (wordJoinerIndex >= joiners[start] &&
          wordJoinerIndex < joiners[end - 1])
      {
        while (start < end)
        {
          mid = (start + end) >> 1;
          auto joinerCandidate = joiners[mid];
          if (joinerCandidate == wordJoinerIndex)
          {
            // we found that the previous text index is a joiner
            // now let's clean all indexes that are pointing to word
            // joiners
            bool isJoiner = true;
            auto currentJoinerIndex = mid;
            while (isJoiner)
            {
              if (m_index == 0)
              {
                return back();
              }
              // If the text index of the previous glyph is a
              // joiner, we need to skip it
              if (m_run->textIndices[m_index - 1] ==
                  joiners[currentJoinerIndex])
              {
                m_index--;
                if (currentJoinerIndex > 0)
                {
                  // we keep moving up the joiners list in
                  // case there are consecutive word joiners
                  currentJoinerIndex--;
                }
                else
                {
                  isJoiner = false;
                }
              }
              else
              {
                isJoiner = false;
              }
            }
            return back();
          }
          if (joinerCandidate < wordJoinerIndex)
          {
            start = mid + 1;
          }
          else
          {
            end = mid;
          }
        }
      }
    }
    return true;
  }

  bool forward()
  {
    if (m_index == m_run->glyphs.size())
    {
      if (m_run == m_runs.end())
      {
        return false;
      }
      m_run++;
      m_index = 0;
      if (m_index == m_run->glyphs.size())
      {
        return forward();
      }
    }
    else
    {
      m_index++;
    }
    while (m_index > 0 && m_index < m_run->glyphs.size() &&
           m_run->textIndices[m_index] == m_run->textIndices[m_index - 1])
    {
      m_index++;
    }
    if (m_run->joiners.size() > 0 && m_index < m_run->textIndices.size())
    {
      auto joiners = m_run->joiners;
      auto wordJoinerIndex = m_run->textIndices[m_index];
      size_t mid = 0;
      size_t start = 0;
      size_t end = joiners.size();
      // If this condition is not met, skip to avoid binary search
      if (wordJoinerIndex >= joiners[start] &&
          wordJoinerIndex < joiners[end - 1])
      {

        while (start < end)
        {
          mid = (start + end) >> 1;
          auto joinerCandidate = joiners[mid];
          if (joinerCandidate == wordJoinerIndex)
          {
            // we found that the next text index is a joiner
            // now let's clean all indexes that are pointing to word
            // joiners
            bool isJoiner = true;
            auto currentJoinerIndex = mid;
            while (isJoiner)
            {
              if (m_index == m_run->glyphs.size())
              {
                return forward();
              }
              // If the text index of the current glyph is a
              // joiner, we need to skip it
              if (currentJoinerIndex < joiners.size() &&
                  m_run->textIndices[m_index] == joiners[currentJoinerIndex])
              {
                m_index++;
                if (currentJoinerIndex < joiners.size())
                {
                  // we keep moving down the joiners list in
                  // case there are consecutive word joiners
                  currentJoinerIndex++;
                }
                else
                {
                  isJoiner = false;
                }
              }
              else
              {
                isJoiner = false;
              }
            }
            return forward();
          }
          if (joinerCandidate < wordJoinerIndex)
          {
            start = mid + 1;
          }
          else
          {
            end = mid;
          }
        }
      }
    }
    return true;
  }

  float x() const { return m_run->xpos[m_index]; }

  const GlyphRun* run() const { return m_run; }
  uint32_t index() const { return m_index; }

  bool operator==(const RunIterator& o) const
  {
    return m_run == o.m_run && m_index == o.m_index;
  }
};

SimpleArray<GlyphLine> GlyphLine::BreakLines(
    Span<const GlyphRun> runs,
    float width,
    TextWordBreak wordBreak)
{
  float maxLineWidth = autowidth(width) ? std::numeric_limits<float>::max()
                                        : width;

  SimpleArrayBuilder<GlyphLine> lines;

  if (runs.empty())
  {
    return lines;
  }

  auto limit = maxLineWidth;

  bool advanceWord = false;

  // We iterate the breaks list with a WordMarker helper which is
  // basically an iterator. The breaks lists contains tightly packed
  // start/end indices per run. So the first valid word is at break index
  // 0,1 (per run). Because a run can be created with no valid breaks, we
  // start the word iterator at a negative index and attempt to move it to
  // the first valid index (which could be in the Nth run in the
  // paragraph). If that fails, we know we have no words to break in the
  // entire paragraph and can early out. See how WordMarker::next works
  // and notice how we also use it below in this same method.
  WordMarker start = {runs.begin(), (uint32_t)-2};
  WordMarker end = {runs.begin(), (uint32_t)-1};
  if (!start.next(runs) || !end.next(runs))
  {
    return lines;
  }

  GlyphLine line = GlyphLine();

  uint32_t breakIndex = end.run->breaks[end.index];
  const GlyphRun* breakRun = end.run;
  uint32_t lastEndGlyphIndex = end.index;
  uint32_t startBreakIndex = start.run->breaks[start.index];
  const GlyphRun* startBreakRun = start.run;

  float x = end.run->xpos[breakIndex];
  while (true)
  {
    if (advanceWord)
    {
      lastEndGlyphIndex = end.index;

      if (!start.next(runs))
      {
        break;
      }
      if (!end.next(runs))
      {
        break;
      }

      advanceWord = false;

      breakIndex = end.run->breaks[end.index];
      breakRun = end.run;
      startBreakIndex = start.run->breaks[start.index];
      startBreakRun = start.run;
      x = end.run->xpos[breakIndex];
    }

    bool isForcedBreak = breakRun == startBreakRun &&
                         breakIndex == startBreakIndex;

    uint32_t startRunIndex = (uint32_t)(start.run - runs.begin());
    // Nothing has been placed on this line yet and it begins exactly at
    // this word, so the word is alone on its line and can't be knocked
    // any further down.
    bool wordStartsLine = line.startGlyphIndex == startBreakIndex &&
                          line.startRunIndex == startRunIndex;

    // TextWordBreak::normal never cuts a word: one that doesn't fit even
    // when alone on its line overflows the box instead, so treat it as if
    // it fit. Falling into the knock-to-a-new-line branch below would
    // spin forever -- it would rebuild an identical (empty) line and
    // never set advanceWord.
    bool overflows = !isForcedBreak && x > limit &&
                     !(wordBreak == TextWordBreak::normal && wordStartsLine);

    if (overflows)
    {
      // A whole word overflowed, break until we can no longer break
      // (or it fits). breakAll also cuts inside a word that isn't
      // alone on its line, but only once at least one cluster of it
      // still fits here. Without that bound the walk-back below -- which
      // has no lower bound, since the lineStart == lineEnd test is an
      // exact match -- could land in the whitespace *before* the word,
      // leaving the space on the end of this line (inflating the width
      // ComputeMaxWidth/ComputeLineSpacing derive from it) or at the
      // start of the next one. When not even one cluster fits we fall
      // through to knocking the whole word down, where wordStartsLine
      // becomes true and it gets cut normally.
      bool splitInsideWord = wordStartsLine;
      if (!splitInsideWord && wordBreak == TextWordBreak::breakAll)
      {
        RunIterator firstCluster(runs, start.run, startBreakIndex);
        splitInsideWord = firstCluster.forward() && firstCluster.x() <= limit;
      }
      if (splitInsideWord)
      {
        bool canBreakMore = true;
        while (canBreakMore && x > limit)
        {

          RunIterator lineStart = RunIterator(
              runs,
              runs.begin() + line.startRunIndex,
              line.startGlyphIndex);
          RunIterator lineEnd = RunIterator(
              runs,
              end.run,
              end.run->breaks[end.index]);
          // Look for the next character that doesn't overflow.
          while (true)
          {
            if (!lineEnd.back())
            {
              // Hit the start of the text, can't go back.
              canBreakMore = false;
              break;
            }
            else if (lineEnd.x() <= limit)
            {
              if (lineStart == lineEnd && !lineEnd.forward())
              {
                // Hit the start of the line and could not
                // go forward to consume a single character.
                // We can't break any further.
                canBreakMore = false;
              }
              else
              {
                line.endRunIndex = (uint32_t)(lineEnd.run() - runs.begin());
                line.endGlyphIndex = lineEnd.index();
              }
              break;
            }
          }
          if (canBreakMore)
          {
            // Add the line and push the limit out.
            limit = lineEnd.x() + maxLineWidth;
            if (!line.empty())
            {
              lines.add(line);
            }
            // Setup the next line.
            line = GlyphLine(
                (uint32_t)(lineEnd.run() - runs.begin()),
                lineEnd.index());
          }
        }
      }
      else
      {
        // word overflowed, knock it to a new line
        auto startX = start.run->xpos[start.run->breaks[start.index]];
        limit = startX + maxLineWidth;

        if (!line.empty() || start.index - lastEndGlyphIndex > 1)
        {
          lines.add(line);
        }

        line = GlyphLine(startRunIndex, startBreakIndex);
      }
    }
    else
    {
      line.endRunIndex = (uint32_t)(end.run - runs.begin());
      line.endGlyphIndex = end.run->breaks[end.index];
      advanceWord = true;
      // Forced BR.
      if (isForcedBreak)
      {
        lines.add(line);
        auto startX = start.run->xpos[start.run->breaks[start.index] + 1];
        limit = startX + maxLineWidth;
        line = GlyphLine(
            (uint32_t)(start.run - runs.begin()),
            startBreakIndex + 1);
      }
    }
  }

  // Add the last line.
  if (!line.empty())
  {
    lines.add(line);
  }

  return lines;
}