// Copyright 2015 The Cobalt Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "cobalt/layout/paragraph.h"

#include "base/i18n/char_iterator.h"
#include "cobalt/base/unicode/character_values.h"

#include "third_party/icu/source/common/unicode/ubidi.h"

namespace cobalt {
namespace layout {

namespace {

int ConvertBaseDirectionToBidiLevel(BaseDirection base_direction) {
  return base_direction == kRightToLeftBaseDirection ? 1 : 0;
}

}  // namespace

Paragraph::Paragraph(
    const icu::Locale& locale, BaseDirection base_direction,
    const DirectionalEmbeddingStack& directional_embedding_stack,
    icu::BreakIterator* line_break_iterator,
    icu::BreakIterator* character_break_iterator)
    : locale_(locale),
      base_direction_(base_direction),
      directional_embedding_stack_(directional_embedding_stack),
      line_break_iterator_(line_break_iterator),
      character_break_iterator_(character_break_iterator),
      is_closed_(false),
      last_retrieved_run_index_(0) {
  DCHECK(line_break_iterator_);
  DCHECK(character_break_iterator_);

  level_runs_.push_back(
      BidiLevelRun(0, ConvertBaseDirectionToBidiLevel(base_direction)));

  // Walk through the passed in directional embedding stack and add each
  // embedding to the text. This allows a paragraph to continue the directional
  // state of a prior paragraph.
  DCHECK(unicode_text_.isEmpty());
  for (size_t i = 0; i < directional_embedding_stack_.size(); ++i) {
    if (directional_embedding_stack_[i] == kRightToLeftDirectionalEmbedding) {
      unicode_text_ += base::unicode::kRightToLeftEmbeddingCharacter;
    } else {
      unicode_text_ += base::unicode::kLeftToRightEmbeddingCharacter;
    }
  }
}

int32 Paragraph::AppendUtf8String(const std::string& utf8_string) {
  return AppendUtf8String(utf8_string, kNoTextTransform);
}

int32 Paragraph::AppendUtf8String(const std::string& utf8_string,
                                  TextTransform transform) {
  int32 start_position = GetTextEndPosition();
  DCHECK(!is_closed_);
  if (!is_closed_) {
    icu::UnicodeString unicode_string =
        icu::UnicodeString::fromUTF8(utf8_string);
    if (transform == kUppercaseTextTransform) {
      unicode_string.toUpper(locale_);
    }

    unicode_text_ += unicode_string;
  }

  return start_position;
}

int32 Paragraph::AppendCodePoint(CodePoint code_point) {
  // TODO: Switch from appending directional embedding characters to
  // using directional isolate characters as soon as we upgrade to the latest
  // version of ICU. Our current version doesn't support them.
  int32 start_position = GetTextEndPosition();
  DCHECK(!is_closed_);
  if (!is_closed_) {
    switch (code_point) {
      case kLeftToRightEmbedCodePoint:
        // If this is a directional embedding that is being added, then add it
        // to the directional embedding stack. This guarantees that a
        // corresponding pop directional formatting will later be added to the
        // text and allows later paragraphs to copy the directional state.
        // http://unicode.org/reports/tr9/#Explicit_Directional_Embeddings
        directional_embedding_stack_.push_back(
            kLeftToRightDirectionalEmbedding);
        unicode_text_ += base::unicode::kLeftToRightEmbeddingCharacter;
        break;
      case kLineFeedCodePoint:
        unicode_text_ += base::unicode::kNewLineCharacter;
        break;
      case kNoBreakSpaceCodePoint:
        unicode_text_ += base::unicode::kNoBreakSpaceCharacter;
        break;
      case kObjectReplacementCharacterCodePoint:
        unicode_text_ += base::unicode::kObjectReplacementCharacter;
        break;
      case kPopDirectionalFormattingCharacterCodePoint:
        directional_embedding_stack_.pop_back();
        unicode_text_ += base::unicode::kPopDirectionalFormattingCharacter;
        break;
      case kRightToLeftEmbedCodePoint:
        // If this is a directional embedding that is being added, then add it
        // to the directional embedding stack. This guarantees that a
        // corresponding pop directional formatting will later be added to the
        // text and allows later paragraphs to to copy the directional state.
        // http://unicode.org/reports/tr9/#Explicit_Directional_Embeddings
        directional_embedding_stack_.push_back(
            kRightToLeftDirectionalEmbedding);
        unicode_text_ += base::unicode::kRightToLeftEmbeddingCharacter;
        break;
    }
  }
  return start_position;
}

bool Paragraph::FindBreakPosition(const scoped_refptr<dom::FontList>& used_font,
                                  int32 start_position, int32 end_position,
                                  LayoutUnit available_width,
                                  bool should_collapse_trailing_white_space,
                                  bool allow_overflow,
                                  Paragraph::BreakPolicy break_policy,
                                  int32* break_position,
                                  LayoutUnit* break_width) {
  DCHECK(is_closed_);

  *break_position = start_position;
  *break_width = LayoutUnit();

  // If overflow isn't allowed and there is no available width, then there is
  // nothing to do. No break position can be found.
  if (!allow_overflow && available_width <= LayoutUnit()) {
    return false;
  }

  // Normal overflow is not allowed when the break policy is break-word, so
  // only attempt to find normal break positions if the break policy is normal
  // or there is width still available.
  // https://www.w3.org/TR/css-text-3/#overflow-wrap
  // NOTE: Normal break positions are still found when the break policy is
  // break-word and overflow has not yet occurred because width calculations are
  // more accurate between word intervals, as these properly take into complex
  // shaping. Due to this, calculating the width using word intervals until
  // reaching the final word that must be broken between grapheme clusters
  // results in less accumulated width calculation error.
  if (break_policy == kBreakPolicyNormal || available_width > LayoutUnit()) {
    // Only allow normal overflow if the policy is |kBreakPolicyNormal|;
    // otherwise, overflowing via normal breaking would be too greedy in what it
    // included and overflow wrapping will be attempted via word breaking.
    bool allow_normal_overflow =
        allow_overflow && break_policy == kBreakPolicyNormal;

    // Find the last available normal break position. |break_position| and
    // |break_width| will be updated with the position of the last available
    // break position.
    FindIteratorBreakPosition(
        used_font, line_break_iterator_, start_position, end_position,
        available_width, should_collapse_trailing_white_space,
        allow_normal_overflow, break_position, break_width);
  }

  // If break word is the break policy, attempt to break unbreakable "words" at
  // an arbitrary point, while still maintaining grapheme clusters as
  // indivisible units.
  // https://www.w3.org/TR/css3-text/#overflow-wrap
  if (break_policy == kBreakPolicyBreakWord) {
    // Only continue allowing overflow if the break position has not moved from
    // start, meaning that no normal break positions were found.
    allow_overflow = allow_overflow && (*break_position == start_position);

    // Find the last available break-word break position. |break_position| and
    // |break_width| will be updated with the position of the last available
    // break position. The search begins at the location of the last normal
    // break position that fit within the available width.
    FindIteratorBreakPosition(
        used_font, character_break_iterator_, *break_position, end_position,
        available_width, false, allow_overflow, break_position, break_width);
  }

  // No usable break position was found if the break position has not moved
  // from the start position.
  return *break_position > start_position;
}

int32 Paragraph::GetNextBreakPosition(int32 position,
                                      BreakPolicy break_policy) {
  icu::BreakIterator* break_iterator = GetBreakIterator(break_policy);
  break_iterator->setText(unicode_text_);
  return break_iterator->following(position);
}

int32 Paragraph::GetPreviousBreakPosition(int32 position,
                                          BreakPolicy break_policy) {
  icu::BreakIterator* break_iterator = GetBreakIterator(break_policy);
  break_iterator->setText(unicode_text_);
  return break_iterator->preceding(position);
}

bool Paragraph::IsBreakPosition(int32 position, BreakPolicy break_policy) {
  icu::BreakIterator* break_iterator = GetBreakIterator(break_policy);
  break_iterator->setText(unicode_text_);
  return break_iterator->isBoundary(position) == TRUE;
}

std::string Paragraph::RetrieveUtf8SubString(int32 start_position,
                                             int32 end_position) const {
  return RetrieveUtf8SubString(start_position, end_position, kLogicalTextOrder);
}

std::string Paragraph::RetrieveUtf8SubString(int32 start_position,
                                             int32 end_position,
                                             TextOrder text_order) const {
  std::string utf8_sub_string;

  if (start_position < end_position) {
    icu::UnicodeString unicode_sub_string =
        unicode_text_.tempSubStringBetween(start_position, end_position);

    // Odd bidi levels signify RTL directionality. If the text is being
    // retrieved in visual order and has RTL directionality, then reverse the
    // text.
    if (text_order == kVisualTextOrder && IsRTL(start_position)) {
      unicode_sub_string.reverse();
    }

    unicode_sub_string.toUTF8String(utf8_sub_string);
  }

  return utf8_sub_string;
}

const char16* Paragraph::GetTextBuffer() const {
  return unicode_text_.getBuffer();
}

const icu::Locale& Paragraph::GetLocale() const { return locale_; }

BaseDirection Paragraph::GetBaseDirection() const { return base_direction_; }

BaseDirection Paragraph::GetDirectionalEmbeddingStackDirection() const {
  size_t stack_size = directional_embedding_stack_.size();
  if (stack_size > 0) {
    if (directional_embedding_stack_[stack_size - 1] ==
        kRightToLeftDirectionalEmbedding) {
      return kRightToLeftBaseDirection;
    } else {
      return kLeftToRightBaseDirection;
    }
  } else {
    return base_direction_;
  }
}

int Paragraph::GetBidiLevel(int32 position) const {
  return level_runs_[GetRunIndex(position)].level_;
}

bool Paragraph::IsRTL(int32 position) const {
  return (GetBidiLevel(position) % 2) == 1;
}

bool Paragraph::IsCollapsibleWhiteSpace(int32 position) const {
  // Only check for the space character. Other collapsible white space
  // characters will have already been converted into the space characters and
  // do not need to be checked against.
  return unicode_text_[position] == base::unicode::kSpaceCharacter;
}

bool Paragraph::GetNextRunPosition(int32 position,
                                   int32* next_run_position) const {
  size_t next_run_index = GetRunIndex(position) + 1;
  if (next_run_index >= level_runs_.size()) {
    return false;
  } else {
    *next_run_position = level_runs_[next_run_index].start_position_;
    return true;
  }
}

int32 Paragraph::GetTextEndPosition() const { return unicode_text_.length(); }

const Paragraph::DirectionalEmbeddingStack&
Paragraph::GetDirectionalEmbeddingStack() const {
  return directional_embedding_stack_;
}

void Paragraph::Close() {
  DCHECK(!is_closed_);
  if (!is_closed_) {
    // Terminate all of the explicit directional embeddings that were previously
    // added. However, do not clear the stack. A subsequent paragraph may need
    // to copy it.
    // http://unicode.org/reports/tr9/#Terminating_Explicit_Directional_Embeddings_and_Overrides
    for (size_t count = directional_embedding_stack_.size(); count > 0;
         --count) {
      unicode_text_ += base::unicode::kPopDirectionalFormattingCharacter;
    }

    is_closed_ = true;
    GenerateBidiLevelRuns();
  }
}

bool Paragraph::IsClosed() const { return is_closed_; }

Paragraph::BreakPolicy Paragraph::GetBreakPolicyFromWrapOpportunityPolicy(
    WrapOpportunityPolicy wrap_opportunity_policy,
    bool does_style_allow_break_word) {
  // Initialize here to prevent a potential compiler warning.
  BreakPolicy break_policy = kBreakPolicyNormal;
  switch (wrap_opportunity_policy) {
    case kWrapOpportunityPolicyNormal:
      break_policy = kBreakPolicyNormal;
      break;
    case kWrapOpportunityPolicyBreakWord:
      break_policy = kBreakPolicyBreakWord;
      break;
    case kWrapOpportunityPolicyBreakWordOrNormal:
      break_policy = does_style_allow_break_word ? kBreakPolicyBreakWord
                                                 : kBreakPolicyNormal;
      break;
  }
  return break_policy;
}

icu::BreakIterator* Paragraph::GetBreakIterator(BreakPolicy break_policy) {
  return break_policy == kBreakPolicyNormal ? line_break_iterator_
                                            : character_break_iterator_;
}

void Paragraph::FindIteratorBreakPosition(
    const scoped_refptr<dom::FontList>& used_font,
    icu::BreakIterator* const break_iterator, int32 start_position,
    int32 end_position, LayoutUnit available_width,
    bool should_collapse_trailing_white_space, bool allow_overflow,
    int32* break_position, LayoutUnit* break_width) {
  // Iterate through break segments, beginning from the passed in start
  // position. Continue until TryIncludeSegmentWithinAvailableWidth() returns
  // false, indicating that no more segments can be included.
  break_iterator->setText(unicode_text_);
  for (int32 segment_end = break_iterator->following(start_position);
       segment_end != icu::BreakIterator::DONE && segment_end < end_position;
       segment_end = break_iterator->next()) {
    if (!TryIncludeSegmentWithinAvailableWidth(
            used_font, *break_position, segment_end, available_width,
            should_collapse_trailing_white_space, &allow_overflow,
            break_position, break_width)) {
      break;
    }
  }
}

bool Paragraph::TryIncludeSegmentWithinAvailableWidth(
    const scoped_refptr<dom::FontList>& used_font, int32 segment_start,
    int32 segment_end, LayoutUnit available_width,
    bool should_collapse_trailing_white_space, bool* allow_overflow,
    int32* break_position, LayoutUnit* break_width) {
  // Add the width of the segment encountered to the total, until reaching one
  // that causes the available width to be exceeded. The previous break position
  // is the last usable one. However, if overflow is allowed and no segment has
  // been found, then the first overflowing segment is accepted.
  LayoutUnit segment_width = LayoutUnit(used_font->GetTextWidth(
      unicode_text_.getBuffer() + segment_start, segment_end - segment_start,
      IsRTL(segment_start), NULL));

  // If trailing white space is being collapsed, then it will not be included
  // when determining if the segment can fit within the available width.
  // However, it is still added to |break_width|, as it will impact the
  // width available to additional segments.
  LayoutUnit collapsible_trailing_white_space_width =
      LayoutUnit(should_collapse_trailing_white_space &&
                         IsCollapsibleWhiteSpace(segment_end - 1)
                     ? used_font->GetSpaceWidth()
                     : 0);

  if (!*allow_overflow &&
      *break_width + segment_width - collapsible_trailing_white_space_width >
          available_width) {
    return false;
  }

  *break_position = segment_end;
  *break_width += segment_width;

  if (*allow_overflow) {
    *allow_overflow = false;
    if (*break_width >= available_width) {
      return false;
    }
  }

  return true;
}

namespace {

// This class guarantees that a UBiDi object is closed when it goes out of
// scope.
class ScopedUBiDiPtr {
 public:
  explicit ScopedUBiDiPtr(UBiDi* ubidi) : ubidi_(ubidi) {}

  ~ScopedUBiDiPtr() { ubidi_close(ubidi_); }

  UBiDi* get() const { return ubidi_; }

 private:
  UBiDi* ubidi_;
};

}  // namespace

// Should only be called by Close().
void Paragraph::GenerateBidiLevelRuns() {
  DCHECK(is_closed_);

  UErrorCode error = U_ZERO_ERROR;

  // Create a scoped ubidi ptr when opening the text. It guarantees that the
  // UBiDi object will be closed when it goes out of scope.
  ScopedUBiDiPtr ubidi(ubidi_openSized(unicode_text_.length(), 0, &error));
  if (U_FAILURE(error)) {
    return;
  }

  ubidi_setPara(ubidi.get(), unicode_text_.getBuffer(), unicode_text_.length(),
                UBiDiLevel(ConvertBaseDirectionToBidiLevel(base_direction_)),
                NULL, &error);
  if (U_FAILURE(error)) {
    return;
  }

  const int runs = ubidi_countRuns(ubidi.get(), &error);
  if (U_FAILURE(error)) {
    return;
  }

  level_runs_.clear();
  level_runs_.reserve(size_t(runs));

  int run_start_position = 0;
  int run_end_position;
  UBiDiLevel run_ubidi_level;

  int32 text_end_position = GetTextEndPosition();
  while (run_start_position < text_end_position) {
    ubidi_getLogicalRun(ubidi.get(), run_start_position, &run_end_position,
                        &run_ubidi_level);
    level_runs_.push_back(
        BidiLevelRun(run_start_position, static_cast<int>(run_ubidi_level)));
    run_start_position = run_end_position;
  }
}

size_t Paragraph::GetRunIndex(int32 position) const {
  DCHECK(is_closed_);

  // Start the search from the last retrieved index. This is tracked because
  // the next retrieved run index is almost always either the same as the last
  // retrieved one or a neighbor of it, so this reduces nearly all calls to only
  // requiring a couple comparisons.

  // First iterate up the level run vector, finding the first element that has
  // a start position larger than the passed in position. The upward iteration
  // is stopped if the last element is reached.
  while (last_retrieved_run_index_ < level_runs_.size() - 1 &&
         level_runs_[last_retrieved_run_index_].start_position_ < position) {
    ++last_retrieved_run_index_;
  }
  // Iterate down the level run vector until a start position smaller than or
  // equal to the passed in position is reached. This run contains the passed in
  // position. The start position of the first run has a value of 0 and serves
  // as a sentinel for the loop.
  while (level_runs_[last_retrieved_run_index_].start_position_ > position) {
    --last_retrieved_run_index_;
  }

  return last_retrieved_run_index_;
}

}  // namespace layout
}  // namespace cobalt