/*
 * Copyright (c) 2012 Google Inc. All rights reserved.
 * Copyright (C) 2013 BlackBerry Limited. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "third_party/blink/renderer/platform/fonts/shaping/harfbuzz_shaper.h"

#include <hb-ot.h>
#include <hb.h>
#include <unicode/uchar.h>
#include <unicode/uscript.h>

#include <algorithm>
#include <hb-cplusplus.hh>
#include <memory>
#include <utility>

#include "base/check_op.h"
#include "base/logging.h"
#include "base/memory/ptr_util.h"
#include "base/notreached.h"
#include "base/numerics/safe_conversions.h"
#include "build/build_config.h"
#include "third_party/blink/renderer/platform/fonts/font.h"
#include "third_party/blink/renderer/platform/fonts/font_description.h"
#include "third_party/blink/renderer/platform/fonts/font_fallback_iterator.h"
#include "third_party/blink/renderer/platform/fonts/font_fallback_priority.h"
#include "third_party/blink/renderer/platform/fonts/font_variant_emoji.h"
#include "third_party/blink/renderer/platform/fonts/opentype/open_type_caps_support.h"
#include "third_party/blink/renderer/platform/fonts/shaping/case_mapping_harfbuzz_buffer_filler.h"
#include "third_party/blink/renderer/platform/fonts/shaping/font_features.h"
#include "third_party/blink/renderer/platform/fonts/shaping/han_kerning.h"
#include "third_party/blink/renderer/platform/fonts/shaping/harfbuzz_face.h"
#include "third_party/blink/renderer/platform/fonts/shaping/shape_result_run.h"
#include "third_party/blink/renderer/platform/fonts/small_caps_iterator.h"
#include "third_party/blink/renderer/platform/fonts/utf16_text_iterator.h"
#include "third_party/blink/renderer/platform/runtime_enabled_features.h"
#include "third_party/blink/renderer/platform/text/text_break_iterator.h"
#include "third_party/blink/renderer/platform/wtf/deque.h"
#include "third_party/blink/renderer/platform/wtf/math_extras.h"
#include "third_party/blink/renderer/platform/wtf/text/format.h"
#include "third_party/blink/renderer/platform/wtf/text/string_builder.h"
#include "third_party/blink/renderer/platform/wtf/text/unicode.h"

namespace blink {

namespace {

const char* const harfrust_shaper_list[] = {"harfrust"};
const char* const ot_shaper_list[] = {"ot"};

inline const char* const* ShapingBackend() {
  return RuntimeEnabledFeatures::HarfRustShapingEnabled() ? harfrust_shaper_list
                                                          : ot_shaper_list;
}

//
// This class holds an `hb_buffer_t`.
//
// To reduce constructions and destructions of `hb_buffer_t`, it returns the
// `hb_buffer_t` instance to its internal pool on the destruction. The pooled
// instances will be `hb_buffer_reset`ed and reused on future constructions.
//
class PooledHarfBuzzBuffer {
 public:
  PooledHarfBuzzBuffer() {
    Pool& pool = GetPool();
    if (!pool.empty()) {
      buffer_ = std::move(pool.back());
#if EXPENSIVE_DCHECKS_ARE_ON()
      DCHECK(buffer_);
      DCHECK(!pool.back());
#endif  // EXPENSIVE_DCHECKS_ARE_ON()
      pool.pop_back();

      hb_buffer_reset(buffer_);
      return;
    }

    buffer_ = hb::unique_ptr<hb_buffer_t>{hb_buffer_create()};
  }

  ~PooledHarfBuzzBuffer() {
    Pool& pool = GetPool();
    pool.push_back(std::move(buffer_));
#if EXPENSIVE_DCHECKS_ARE_ON()
    DCHECK_LE(pool.size(), kInlineCapacity);
    DCHECK(!buffer_);
#endif  // EXPENSIVE_DCHECKS_ARE_ON()
  }

  hb_buffer_t* Get() const { return buffer_; }
  const hb_buffer_t* operator->() const { return Get(); }
  explicit operator hb_buffer_t*() const { return Get(); }
  explicit operator bool() const { return Get(); }

 private:
  static constexpr wtf_size_t kInlineCapacity = 2;
  using Pool = Vector<hb::unique_ptr<hb_buffer_t>, kInlineCapacity>;

  static Pool& GetPool() {
    DEFINE_THREAD_SAFE_STATIC_LOCAL(ThreadSpecific<Pool>, pool, ());
    return *pool;
  }

  hb::unique_ptr<hb_buffer_t> buffer_;
};

#if EXPENSIVE_DCHECKS_ARE_ON()
// Check if the ShapeResult has the specified range.
// |text| and |font| are only for logging.
void CheckShapeResultRange(const ShapeResult* result,
                           unsigned start,
                           unsigned end,
                           const String& text,
                           const Font* font) {
  if (!result) {
    return;
  }
  DCHECK_LE(start, end);
  unsigned length = end - start;
  if (length == result->NumCharacters() &&
      (!length ||
       (start == result->StartIndex() && end == result->EndIndex()))) {
    return;
  }

  // Log font-family/size as specified.
  StringBuilder log;
  log.Append("Font='");
  const FontDescription& font_description = font->GetFontDescription();
  log.Append(font_description.Family().ToString());
  FormatTo(log, "', {:f}", font_description.ComputedSize());

  // Log the primary font with its family name in the font file.
  const SimpleFontData* font_data = font->PrimaryFont();
  if (font_data) {
    const SkTypeface* typeface = font_data->PlatformData().Typeface();
    SkString family_name;
    typeface->getFamilyName(&family_name);
    log.Append(", primary=");
    log.Append(base::as_byte_span(family_name));
  }

  // Log the text to shape.
  FormatTo(log, ": {}-{} -> {}-{}:", start, end, result->StartIndex(),
           result->EndIndex());
  for (unsigned i = start; i < end; ++i) {
    FormatTo(log, " {:02X}", text[i]);
  }

  log.Append(", result=");
  result->ToString(&log);

  NOTREACHED() << log.ToString();
}
#endif

FontFallbackPriority ApplyFontVariantEmojiOnFallbackPriority(
    FontFallbackPriority curr_font_fallback_priority,
    FontVariantEmoji font_variant_emoji) {
  // font-variant-emoji property should not override emoji variation selectors,
  // see https://www.w3.org/TR/css-fonts-4/#font-variant-emoji-prop.
  if (!HasVSFallbackPriority(curr_font_fallback_priority)) {
    if (font_variant_emoji == kEmojiVariantEmoji) {
      return FontFallbackPriority::kEmojiEmoji;
    }
    if (font_variant_emoji == kTextVariantEmoji) {
      return FontFallbackPriority::kText;
    }
  }
  return curr_font_fallback_priority;
}

}  // namespace

enum ReshapeQueueItemAction {
  kReshapeQueueNextFont,
  kReshapeQueueRange,
  kReshapeQueueReset
};

struct ReshapeQueueItem {
  DISALLOW_NEW();
  ReshapeQueueItemAction action_;
  unsigned start_index_;
  unsigned num_characters_;
  ReshapeQueueItem(ReshapeQueueItemAction action, unsigned start, unsigned num)
      : action_(action), start_index_(start), num_characters_(num) {}
};

//
// Represents a context while shaping a range.
//
// Input-only data and objects whose pointers don't change are marked as
// `const`.
//
struct RangeContext {
  STACK_ALLOCATED();

 public:
  RangeContext(const Font* font,
               TextDirection direction,
               unsigned start,
               unsigned end,
               ShapeOptions options = ShapeOptions())
      : font(font),
        text_direction(direction),
        start(start),
        end(end),
        font_features(font->GetFontFeatures()),
        options(options) {
    DCHECK_GE(end, start);
  }

  const Font* const font;
  const TextDirection text_direction;
  const unsigned start;
  const unsigned end;
  const PooledHarfBuzzBuffer buffer;
  FontFeatureRanges font_features;
  Deque<ReshapeQueueItem> reshape_queue;
  const ShapeOptions options;

  hb_direction_t HarfBuzzDirection(CanvasRotationInVertical canvas_rotation) {
    FontOrientation orientation = font->GetFontDescription().Orientation();
    hb_direction_t direction =
        IsVerticalAnyUpright(orientation) &&
                IsCanvasRotationInVerticalUpright(canvas_rotation)
            ? HB_DIRECTION_TTB
            : HB_DIRECTION_LTR;
    return text_direction == TextDirection::kRtl
               ? HB_DIRECTION_REVERSE(direction)
               : direction;
  }
};

struct BufferSlice {
  unsigned start_character_index;
  unsigned num_characters;
  unsigned start_glyph_index;
  unsigned num_glyphs;
};

namespace {

// A port of hb_icu_script_to_script because harfbuzz on CrOS is built
// without hb-icu. See http://crbug.com/356929
static inline hb_script_t ICUScriptToHBScript(UScriptCode script) {
  if (script == USCRIPT_INVALID_CODE) [[unlikely]] {
    return HB_SCRIPT_INVALID;
  }

  return hb_script_from_string(uscript_getShortName(script), -1);
}

inline float HarfBuzzPositionToFloat(hb_position_t value) {
  return static_cast<float>(value) / (1 << 16);
}

void RoundHarfBuzzPosition(hb_position_t* value) {
  if ((*value) & 0xFFFF) {
    // There is a non-zero fractional part in the 16.16 value.
    *value = static_cast<hb_position_t>(
                 round(static_cast<float>(*value) / (1 << 16)))
             << 16;
  }
}

void RoundHarfBuzzBufferPositions(hb_buffer_t* buffer) {
  unsigned int len;
  hb_glyph_position_t* glyph_positions =
      hb_buffer_get_glyph_positions(buffer, &len);
  for (unsigned int i = 0; i < len; i++) {
    hb_glyph_position_t* pos = &UNSAFE_TODO(glyph_positions[i]);
    RoundHarfBuzzPosition(&pos->x_offset);
    RoundHarfBuzzPosition(&pos->y_offset);
    RoundHarfBuzzPosition(&pos->x_advance);
    RoundHarfBuzzPosition(&pos->y_advance);
  }
}

inline bool ShapeRange(hb_buffer_t* buffer,
                       const FontFeatureRanges& font_features,
                       const SimpleFontData* current_font,
                       const UnicodeRangeSet* current_font_range_set,
                       UScriptCode current_run_script,
                       hb_direction_t direction,
                       hb_language_t language,
                       float specified_size,
                       VariationSelectorMode variation_selector_mode) {
  const FontPlatformData& platform_data = current_font->PlatformData();
  HarfBuzzFace* face = platform_data.GetHarfBuzzFace();
  if (!face) {
    DLOG(ERROR) << "Could not create HarfBuzzFace from FontPlatformData.";
    return false;
  }

  std::optional<FontFeatureRanges> variant_features;
  if (const ResolvedFontFeatures& resolved_features =
          platform_data.ResolvedFeatures();
      !resolved_features.empty()) {
    // Insert `resolved_features` before `font_features`.
    variant_features.emplace();
    variant_features->reserve(resolved_features.size() + font_features.size());
    for (const FontFeatureValue& feature : resolved_features) {
      variant_features->push_back(FontFeatureRange{feature});
    }
    variant_features->append_range(font_features);
  }
  const FontFeatureRanges& argument_features =
      variant_features ? *variant_features : font_features;

  hb_buffer_set_language(buffer, language);
  hb_buffer_set_script(buffer, ICUScriptToHBScript(current_run_script));
  hb_buffer_set_direction(buffer, direction);

  hb_font_t* hb_font =
      face->GetScaledFont(current_font_range_set,
                          HB_DIRECTION_IS_VERTICAL(direction)
                              ? HarfBuzzFace::kPrepareForVerticalLayout
                              : HarfBuzzFace::kNoVerticalLayout,
                          specified_size);
  face->SetVariationSelectorMode(variation_selector_mode);
  hb_shape_full(hb_font, buffer,
                FontFeatureRange::ToHarfBuzzData(argument_features.data()),
                argument_features.size(), ShapingBackend());
  if (!face->ShouldSubpixelPosition()) {
    RoundHarfBuzzBufferPositions(buffer);
  }

  return true;
}

BufferSlice ComputeSlice(RangeContext* range_data,
                         const ReshapeQueueItem& current_queue_item,
                         const hb_glyph_info_t* glyph_info,
                         unsigned num_glyphs,
                         unsigned old_glyph_index,
                         unsigned new_glyph_index) {
  // Compute the range indices of consecutive shaped or .notdef glyphs.
  // Cluster information for RTL runs becomes reversed, e.g. glyph 0
  // has cluster index 5 in a run of 6 characters.
  BufferSlice result;
  result.start_glyph_index = old_glyph_index;
  result.num_glyphs = new_glyph_index - old_glyph_index;

  if (HB_DIRECTION_IS_FORWARD(
          hb_buffer_get_direction(range_data->buffer.Get()))) {
    result.start_character_index =
        UNSAFE_TODO(glyph_info[old_glyph_index].cluster);
    if (new_glyph_index == num_glyphs) {
      // Clamp the end offsets of the queue item to the offsets representing
      // the shaping window.
      unsigned shape_end =
          std::min(range_data->end, current_queue_item.start_index_ +
                                        current_queue_item.num_characters_);
      result.num_characters = shape_end - result.start_character_index;
    } else {
      result.num_characters = UNSAFE_TODO(glyph_info[new_glyph_index].cluster -
                                          result.start_character_index);
    }
  } else {
    // Direction Backwards
    result.start_character_index =
        UNSAFE_TODO(glyph_info[new_glyph_index - 1].cluster);
    if (old_glyph_index == 0) {
      // Clamp the end offsets of the queue item to the offsets representing
      // the shaping window.
      unsigned shape_end =
          std::min(range_data->end, current_queue_item.start_index_ +
                                        current_queue_item.num_characters_);
      result.num_characters = shape_end - result.start_character_index;
    } else {
      result.num_characters =
          UNSAFE_TODO(glyph_info[old_glyph_index - 1].cluster -
                      glyph_info[new_glyph_index - 1].cluster);
    }
  }

  return result;
}

inline bool IsLastFontToShape(
    HarfBuzzShaper::FallbackFontStage fallback_stage) {
  return fallback_stage == HarfBuzzShaper::kLast ||
         fallback_stage == HarfBuzzShaper::kLastIgnoreVS;
}

inline bool StageNeedsQueueReset(
    HarfBuzzShaper::FallbackFontStage fallback_stage) {
  return fallback_stage == HarfBuzzShaper::kLastWithVS;
}

HarfBuzzShaper::FallbackFontStage ChangeStageToLast(
    HarfBuzzShaper::FallbackFontStage fallback_stage) {
  switch (fallback_stage) {
    case HarfBuzzShaper::kIntermediate:
      return HarfBuzzShaper::kLast;
    case HarfBuzzShaper::kIntermediateWithVS:
      return HarfBuzzShaper::kLastWithVS;
    case HarfBuzzShaper::kIntermediateIgnoreVS:
      return HarfBuzzShaper::kLastIgnoreVS;
    default:
      return fallback_stage;
  }
}

HarfBuzzShaper::FallbackFontStage ChangeStageToVS(
    HarfBuzzShaper::FallbackFontStage fallback_stage) {
  switch (fallback_stage) {
    case HarfBuzzShaper::kIntermediate:
      return HarfBuzzShaper::kIntermediateWithVS;
    case HarfBuzzShaper::kLast:
      return HarfBuzzShaper::kLastWithVS;
    case HarfBuzzShaper::kIntermediateWithVS:
    case HarfBuzzShaper::kLastWithVS:
      return fallback_stage;
    default:
      // We should not call this function on the second fallback pass.
      NOTREACHED();
  }
}

void QueueCharacters(RangeContext* range_data,
                     const SimpleFontData* current_font,
                     bool& font_cycle_queued,
                     const BufferSlice& slice,
                     HarfBuzzShaper::FallbackFontStage font_stage) {
  if (!font_cycle_queued) {
    if (StageNeedsQueueReset(font_stage)) {
      range_data->reshape_queue.push_back(
          ReshapeQueueItem(kReshapeQueueReset, 0, 0));
    } else {
      range_data->reshape_queue.push_back(
          ReshapeQueueItem(kReshapeQueueNextFont, 0, 0));
    }
    font_cycle_queued = true;
  }

  DCHECK(slice.num_characters);
  range_data->reshape_queue.push_back(ReshapeQueueItem(
      kReshapeQueueRange, slice.start_character_index, slice.num_characters));
}

CanvasRotationInVertical CanvasRotationForRun(
    FontOrientation font_orientation,
    OrientationIterator::RenderOrientation render_orientation,
    const FontDescription& font_description) {
  if (font_orientation == FontOrientation::kVerticalUpright) {
    return font_description.IsSyntheticOblique()
               ? CanvasRotationInVertical::kRotateCanvasUprightOblique
               : CanvasRotationInVertical::kRotateCanvasUpright;
  }

  if (font_orientation == FontOrientation::kVerticalMixed) {
    if (render_orientation == OrientationIterator::kOrientationKeep) {
      return font_description.IsSyntheticOblique()
                 ? CanvasRotationInVertical::kRotateCanvasUprightOblique
                 : CanvasRotationInVertical::kRotateCanvasUpright;
    }
    return font_description.IsSyntheticOblique()
               ? CanvasRotationInVertical::kOblique
               : CanvasRotationInVertical::kRegular;
  }

  return CanvasRotationInVertical::kRegular;
}

}  // namespace

inline void HarfBuzzShaper::CheckTextLen(unsigned start,
                                         unsigned length) const {
  CHECK_LE(start, text_.length());
  CHECK_LE(length, text_.length() - start);
}

inline void HarfBuzzShaper::CheckTextEnd(unsigned start, unsigned end) const {
  CHECK_LE(start, end);
  CHECK_LE(start, text_.length());
  CHECK_LE(end, text_.length());
}

void HarfBuzzShaper::CommitGlyphs(RangeContext* range_data,
                                  const SimpleFontData* current_font,
                                  UScriptCode current_run_script,
                                  CanvasRotationInVertical canvas_rotation,
                                  FallbackFontStage fallback_stage,
                                  const BufferSlice& slice,
                                  ShapeResult* shape_result) const {
  hb_direction_t direction = range_data->HarfBuzzDirection(canvas_rotation);
  hb_script_t script = ICUScriptToHBScript(current_run_script);
  // Here we need to specify glyph positions.
  BufferSlice next_slice;
  unsigned run_start_index = slice.start_character_index;
  for (const BufferSlice* current_slice = &slice;;) {
    auto* run = MakeGarbageCollected<ShapeResultRun>(
        current_font, direction, canvas_rotation, script, run_start_index,
        current_slice->num_glyphs, current_slice->num_characters);
    unsigned next_start_glyph;
    shape_result->InsertRun(run, current_slice->start_glyph_index,
                            current_slice->num_glyphs, &next_start_glyph,
                            range_data->buffer.Get());
    DCHECK_GE(current_slice->start_glyph_index + current_slice->num_glyphs,
              next_start_glyph);
    unsigned next_num_glyphs =
        current_slice->num_glyphs -
        (next_start_glyph - current_slice->start_glyph_index);
    if (!next_num_glyphs) {
      break;
    }

    // If the slice exceeds the limit a RunInfo can store, create another
    // RunInfo for the rest of the slice.
    DCHECK_GT(current_slice->num_characters, run->num_characters_);
    next_slice = {current_slice->start_character_index + run->num_characters_,
                  current_slice->num_characters - run->num_characters_,
                  next_start_glyph, next_num_glyphs};
    current_slice = &next_slice;

    // The |InsertRun| has truncated the right end. In LTR, advance the
    // |run_start_index| because the end characters are truncated. In RTL, keep
    // the same |run_start_index| because the start characters are truncated.
    if (HB_DIRECTION_IS_FORWARD(direction)) {
      run_start_index = next_slice.start_character_index;
    }
  }
  if (IsLastFontToShape(fallback_stage)) {
    range_data->font->ReportNotDefGlyph();
  }
}

void HarfBuzzShaper::ExtractShapeResults(
    RangeContext* range_data,
    bool& font_cycle_queued,
    const ReshapeQueueItem& current_queue_item,
    const SimpleFontData* current_font,
    UScriptCode current_run_script,
    CanvasRotationInVertical canvas_rotation,
    FallbackFontStage& fallback_stage,
    ShapeResult* shape_result) const {
  enum ClusterResult { kShaped, kNotDef, kUnknown };
  ClusterResult current_cluster_result = kUnknown;
  ClusterResult previous_cluster_result = kUnknown;
  unsigned previous_cluster = 0;
  unsigned current_cluster = 0;

  // Find first notdef glyph in buffer.
  unsigned num_glyphs = hb_buffer_get_length(range_data->buffer.Get());
  hb_glyph_info_t* glyph_info =
      hb_buffer_get_glyph_infos(range_data->buffer.Get(), nullptr);

  unsigned last_change_glyph_index = 0;
  unsigned previous_cluster_start_glyph_index = 0;

  if (!num_glyphs) {
    return;
  }

  const Glyph space_glyph = current_font->SpaceGlyph();
  for (unsigned glyph_index = 0; glyph_index < num_glyphs; ++glyph_index) {
    // We proceed by full clusters and determine a shaping result - either
    // kShaped or kNotDef for each cluster.
    const hb_glyph_info_t& glyph = UNSAFE_TODO(glyph_info[glyph_index]);
    previous_cluster = current_cluster;
    current_cluster = glyph.cluster;
    const hb_codepoint_t glyph_id = glyph.codepoint;
    ClusterResult glyph_result;
    if (glyph_id == 0) {
      // Glyph 0 must be assigned to a .notdef glyph.
      // https://docs.microsoft.com/en-us/typography/opentype/spec/recom#glyph-0-the-notdef-glyph
      glyph_result = kNotDef;
    } else if (glyph_id == space_glyph && !IsLastFontToShape(fallback_stage) &&
               text_[current_cluster] == uchar::kIdeographicSpace) {
      // HarfBuzz synthesizes U+3000 IDEOGRAPHIC SPACE using the space glyph.
      // This is not desired for run-splitting, applying features, and for
      // computing `line-height`. crbug.com/1193282
      // We revisit when HarfBuzz decides how to solve this more generally.
      // https://github.com/harfbuzz/harfbuzz/issues/2889
      glyph_result = kNotDef;
    } else if (glyph_id == kUnmatchedVSGlyphId) {
      fallback_stage = ChangeStageToVS(fallback_stage);
      glyph_result = kNotDef;
    } else {
      glyph_result = kShaped;
    }

    if (current_cluster != previous_cluster) {
      // We are transitioning to a new cluster (whose shaping result state we
      // have not looked at yet). This means the cluster we just looked at is
      // completely analysed and we can determine whether it was fully shaped
      // and whether that means a state change to the cluster before that one.
      if ((previous_cluster_result != current_cluster_result) &&
          previous_cluster_result != kUnknown) {
        BufferSlice slice = ComputeSlice(
            range_data, current_queue_item, glyph_info, num_glyphs,
            last_change_glyph_index, previous_cluster_start_glyph_index);
        // If the most recent cluster is shaped and there is a state change,
        // it means the previous ones were unshaped, so we queue them, unless
        // we're using the last resort font.
        if (current_cluster_result == kShaped &&
            !IsLastFontToShape(fallback_stage)) {
          QueueCharacters(range_data, current_font, font_cycle_queued, slice,
                          fallback_stage);
        } else {
          // If the most recent cluster is unshaped and there is a state
          // change, it means the previous one(s) were shaped, so we commit
          // the glyphs. We also commit when we've reached the last resort
          // font.
          CommitGlyphs(range_data, current_font, current_run_script,
                       canvas_rotation, fallback_stage, slice, shape_result);
        }
        last_change_glyph_index = previous_cluster_start_glyph_index;
      }

      // No state change happened, continue.
      previous_cluster_result = current_cluster_result;
      previous_cluster_start_glyph_index = glyph_index;
      // Reset current cluster result.
      current_cluster_result = glyph_result;
    } else {
      // Update and merge current cluster result.
      current_cluster_result =
          glyph_result == kShaped && (current_cluster_result == kShaped ||
                                      current_cluster_result == kUnknown)
              ? kShaped
              : kNotDef;
    }
  }

  // End of the run.
  if (current_cluster_result != previous_cluster_result &&
      previous_cluster_result != kUnknown &&
      !IsLastFontToShape(fallback_stage)) {
    // The last cluster in the run still had shaping status different from
    // the cluster(s) before it, we need to submit one shaped and one
    // unshaped segment.
    if (current_cluster_result == kShaped) {
      BufferSlice slice = ComputeSlice(
          range_data, current_queue_item, glyph_info, num_glyphs,
          last_change_glyph_index, previous_cluster_start_glyph_index);
      QueueCharacters(range_data, current_font, font_cycle_queued, slice,
                      fallback_stage);
      slice =
          ComputeSlice(range_data, current_queue_item, glyph_info, num_glyphs,
                       previous_cluster_start_glyph_index, num_glyphs);
      CommitGlyphs(range_data, current_font, current_run_script,
                   canvas_rotation, fallback_stage, slice, shape_result);
    } else {
      BufferSlice slice = ComputeSlice(
          range_data, current_queue_item, glyph_info, num_glyphs,
          last_change_glyph_index, previous_cluster_start_glyph_index);
      CommitGlyphs(range_data, current_font, current_run_script,
                   canvas_rotation, fallback_stage, slice, shape_result);
      slice =
          ComputeSlice(range_data, current_queue_item, glyph_info, num_glyphs,
                       previous_cluster_start_glyph_index, num_glyphs);
      QueueCharacters(range_data, current_font, font_cycle_queued, slice,
                      fallback_stage);
    }
  } else {
    // There hasn't been a state change for the last cluster, so we can just
    // either commit or queue what we have up until here.
    BufferSlice slice =
        ComputeSlice(range_data, current_queue_item, glyph_info, num_glyphs,
                     last_change_glyph_index, num_glyphs);
    if (current_cluster_result == kNotDef &&
        !IsLastFontToShape(fallback_stage)) {
      QueueCharacters(range_data, current_font, font_cycle_queued, slice,
                      fallback_stage);
    } else {
      CommitGlyphs(range_data, current_font, current_run_script,
                   canvas_rotation, fallback_stage, slice, shape_result);
    }
  }
}

bool HarfBuzzShaper::CollectFallbackHintChars(
    const Deque<ReshapeQueueItem>& reshape_queue,
    bool needs_hint_list,
    HintCharList& hint) const {
  if (reshape_queue.empty()) {
    return false;
  }

  // Clear without releasing the capacity to avoid reallocations.
  hint.resize(0);

  size_t num_chars_added = 0;
  for (auto it = reshape_queue.begin(); it != reshape_queue.end(); ++it) {
    if (it->action_ == kReshapeQueueNextFont) {
      break;
    }

    CheckTextLen(it->start_index_, it->num_characters_);
    if (text_.Is8Bit()) {
      for (unsigned i = 0; i < it->num_characters_; i++) {
        const UChar hint_char = text_[it->start_index_ + i];
        hint.push_back(hint_char);
        num_chars_added++;
        // Determine if we can take a shortcut and not fill the hint list
        // further: We can do that if we do not need a hint list, and we have
        // managed to find a character with a definite script since
        // FontFallbackIterator needs a character with a determined script to
        // perform meaningful system fallback.
        if (!needs_hint_list &&
            !Character::IsCommonOrInheritedScript(hint_char)) {
          return true;
        }
      }
      continue;
    }

    // !text_.Is8Bit()...
    UChar32 hint_char;
    UTF16TextIterator iterator(
        text_.Span16().subspan(it->start_index_, it->num_characters_));
    while (iterator.Consume(hint_char)) {
      hint.push_back(hint_char);
      num_chars_added++;
      // Determine if we can take a shortcut and not fill the hint list
      // further: We can do that if we do not need a hint list, and we have
      // managed to find a character with a definite script since
      // FontFallbackIterator needs a character with a determined script to
      // perform meaningful system fallback.
      if (!needs_hint_list &&
          !Character::IsCommonOrInheritedScript(hint_char)) {
        return true;
      }
      iterator.Advance();
    }
  }
  return num_chars_added > 0;
}

namespace {

void SplitUntilNextCaseChange(
    const String& text,
    Deque<blink::ReshapeQueueItem>* queue,
    blink::ReshapeQueueItem& current_queue_item,
    SmallCapsIterator::SmallCapsBehavior& small_caps_behavior) {
  // TODO(layout-dev): Add support for latin-1 to SmallCapsIterator.
  base::span<const UChar> normalized_buffer;
  std::optional<String> utf16_text;
  if (text.Is8Bit()) {
    utf16_text.emplace(text);
    utf16_text->Ensure16Bit();
    normalized_buffer = utf16_text->Span16();
  } else {
    normalized_buffer = text.Span16();
  }

  unsigned num_characters_until_case_change = 0;
  SmallCapsIterator small_caps_iterator(normalized_buffer.subspan(
      current_queue_item.start_index_, current_queue_item.num_characters_));
  small_caps_iterator.Consume(&num_characters_until_case_change,
                              &small_caps_behavior);
  if (num_characters_until_case_change > 0 &&
      num_characters_until_case_change < current_queue_item.num_characters_) {
    queue->push_front(blink::ReshapeQueueItem(
        blink::ReshapeQueueItemAction::kReshapeQueueRange,
        current_queue_item.start_index_ + num_characters_until_case_change,
        current_queue_item.num_characters_ - num_characters_until_case_change));
    current_queue_item.num_characters_ = num_characters_until_case_change;
  }
}

class CapsFeatureSettingsScopedOverlay final {
  STACK_ALLOCATED();

 public:
  CapsFeatureSettingsScopedOverlay(FontFeatureRanges*,
                                   FontDescription::FontVariantCaps);
  CapsFeatureSettingsScopedOverlay() = delete;
  ~CapsFeatureSettingsScopedOverlay();

 private:
  void OverlayCapsFeatures(FontDescription::FontVariantCaps);
  void PrependCounting(const FontFeatureRange&);
  FontFeatureRanges* features_;
  wtf_size_t count_features_;
};

CapsFeatureSettingsScopedOverlay::CapsFeatureSettingsScopedOverlay(
    FontFeatureRanges* features,
    FontDescription::FontVariantCaps variant_caps)
    : features_(features), count_features_(0) {
  OverlayCapsFeatures(variant_caps);
}

void CapsFeatureSettingsScopedOverlay::OverlayCapsFeatures(
    FontDescription::FontVariantCaps variant_caps) {
  static constexpr FontFeatureRange smcp{{{'s', 'm', 'c', 'p'}, 1}};
  static constexpr FontFeatureRange pcap{{{'p', 'c', 'a', 'p'}, 1}};
  static constexpr FontFeatureRange c2sc{{{'c', '2', 's', 'c'}, 1}};
  static constexpr FontFeatureRange c2pc{{{'c', '2', 'p', 'c'}, 1}};
  static constexpr FontFeatureRange unic{{{'u', 'n', 'i', 'c'}, 1}};
  static constexpr FontFeatureRange titl{{{'t', 'i', 't', 'l'}, 1}};
  if (variant_caps == FontDescription::kSmallCaps ||
      variant_caps == FontDescription::kAllSmallCaps) {
    PrependCounting(smcp);
    if (variant_caps == FontDescription::kAllSmallCaps) {
      PrependCounting(c2sc);
    }
  }
  if (variant_caps == FontDescription::kPetiteCaps ||
      variant_caps == FontDescription::kAllPetiteCaps) {
    PrependCounting(pcap);
    if (variant_caps == FontDescription::kAllPetiteCaps) {
      PrependCounting(c2pc);
    }
  }
  if (variant_caps == FontDescription::kUnicase) {
    PrependCounting(unic);
  }
  if (variant_caps == FontDescription::kTitlingCaps) {
    PrependCounting(titl);
  }
}

void CapsFeatureSettingsScopedOverlay::PrependCounting(
    const FontFeatureRange& feature) {
  features_->push_front(feature);
  count_features_++;
}

CapsFeatureSettingsScopedOverlay::~CapsFeatureSettingsScopedOverlay() {
  features_->EraseAt(0, count_features_);
}

inline hb_language_t GetLanguageFromFontDescription(
    const FontDescription& font_description) {
  // Determines the HarfBuzz language used for shaping.
  // If the `font-language-override property` is present, its value (a
  // four-character OpenType language system tag) is converted to a HarfBuzz
  // language using hb_ot_tag_to_language. The tag is derived from the string
  // using hb_tag_from_string, with -1 indicating that the string is
  // null-terminated. If no override is specified, the locale-based HarfBuzz
  // language is used instead.
  if (font_description.HasLanguageOverride()) {
    const hb_language_t override_language =
        hb_ot_tag_to_language(hb_tag_from_string(
            font_description.FontLanguageOverride().Utf8().data(), -1));
    if (override_language) {
      return override_language;
    }
  }
  return font_description.LocaleOrDefault().HarfbuzzLanguage();
}

}  // namespace

void HarfBuzzShaper::ShapeSegment(
    RangeContext* range_data,
    const RunSegmenter::RunSegmenterRange& segment,
    ShapeResult* result) const {
  DCHECK(result);
  DCHECK(range_data->buffer);
  const Font* font = range_data->font;
  const FontDescription& font_description = font->GetFontDescription();
  const LayoutLocale& locale = font_description.LocaleOrDefault();
  const hb_language_t language =
      GetLanguageFromFontDescription(font_description);

  bool needs_caps_handling =
      font_description.VariantCaps() != FontDescription::kCapsNormal;
  OpenTypeCapsSupport caps_support;
  HanKerning han_kerning(text_, segment.start, segment.end, font_description);

  FontFallbackIterator fallback_iterator(
      font->CreateFontFallbackIterator(ApplyFontVariantEmojiOnFallbackPriority(
          segment.font_fallback_priority, font_description.VariantEmoji())));

  range_data->reshape_queue.push_back(
      ReshapeQueueItem(kReshapeQueueNextFont, 0, 0));
  range_data->reshape_queue.push_back(ReshapeQueueItem(
      kReshapeQueueRange, segment.start, segment.end - segment.start));

  bool font_cycle_queued = false;
  HintCharList fallback_chars_hint;
  // Reserve sufficient capacity to avoid multiple reallocations, only when a
  // full hint list is needed.
  if (fallback_iterator.NeedsHintList()) {
    fallback_chars_hint.ReserveInitialCapacity(range_data->end -
                                               range_data->start);
  }
  FontDataForRangeSet* current_font_data_for_range_set = nullptr;
  FallbackFontStage fallback_stage = kIntermediate;
  // Variation selector mode should be always set to default at the
  // beginning of the segment shaping run.
  VariationSelectorMode variation_selector_mode =
      GetVariationSelectorModeFromFontVariantEmoji(
          font_description.VariantEmoji());
  while (!range_data->reshape_queue.empty()) {
    ReshapeQueueItem current_queue_item = range_data->reshape_queue.TakeFirst();

    if (current_queue_item.action_ != kReshapeQueueRange) {
      if (current_queue_item.action_ == kReshapeQueueReset) {
        // We reached last font in the list, some of the variation sequences
        // are not shaped yet and there is a fonts in the list that has glyphs
        // for the base codepoint of unshaped variation sequences, so we need to
        // restart the fallback queue and set the variation selector mode to
        // `kIgnoreVariationSelector`.
        DCHECK_EQ(fallback_stage, kLastWithVS);
        fallback_iterator.Reset();
        fallback_stage = kIntermediateIgnoreVS;
        variation_selector_mode = kIgnoreVariationSelector;
      }

      if (!CollectFallbackHintChars(range_data->reshape_queue,
                                    fallback_iterator.NeedsHintList(),
                                    fallback_chars_hint)) {
        // Give up shaping since we cannot retrieve a font fallback
        // font without a hintlist.
        range_data->reshape_queue.clear();
        break;
      }

      current_font_data_for_range_set =
          fallback_iterator.Next(fallback_chars_hint);
      if (!current_font_data_for_range_set->FontData()) {
        DCHECK(range_data->reshape_queue.empty());
        break;
      }
      font_cycle_queued = false;
      continue;
    }

    if (!fallback_iterator.HasNext()) {
      fallback_stage = ChangeStageToLast(fallback_stage);
    }

    const SimpleFontData* font_data =
        current_font_data_for_range_set->FontData();
    SmallCapsIterator::SmallCapsBehavior small_caps_behavior =
        SmallCapsIterator::kSmallCapsSameCase;
    if (needs_caps_handling) {
      caps_support =
          OpenTypeCapsSupport(font_data->PlatformData().GetHarfBuzzFace(),
                              font_description.VariantCaps(),
                              font_description.GetFontSynthesisSmallCaps(),
                              ICUScriptToHBScript(segment.script));
      if (caps_support.NeedsRunCaseSplitting()) {
        SplitUntilNextCaseChange(text_, &range_data->reshape_queue,
                                 current_queue_item, small_caps_behavior);
        // Skip queue items generated by SplitUntilNextCaseChange that do not
        // contribute to the shape result if the range_data restricts shaping to
        // a substring.
        if (range_data->start >= current_queue_item.start_index_ +
                                     current_queue_item.num_characters_ ||
            range_data->end <= current_queue_item.start_index_) {
          continue;
        }
      }
    }

    DCHECK(current_queue_item.num_characters_);
    const SimpleFontData* adjusted_font = font_data;

    // Clamp the start and end offsets of the queue item to the offsets
    // representing the shaping window.
    const unsigned shape_start =
        std::max(range_data->start, current_queue_item.start_index_);
    const unsigned shape_end =
        std::min(range_data->end, current_queue_item.start_index_ +
                                      current_queue_item.num_characters_);
    DCHECK_GT(shape_end, shape_start);
    CheckTextEnd(shape_start, shape_end);

    CaseMapIntend case_map_intend = CaseMapIntend::kKeepSameCase;
    if (needs_caps_handling) {
      case_map_intend = caps_support.NeedsCaseChange(small_caps_behavior);
      if (caps_support.NeedsSyntheticFont(small_caps_behavior)) {
        adjusted_font = font_data->SmallCapsFontData(font_description);
      }
    }

    CaseMappingHarfBuzzBufferFiller(
        case_map_intend, font_description.LocaleOrDefault(),
        range_data->buffer.Get(), text_, shape_start, shape_end - shape_start);

    CanvasRotationInVertical canvas_rotation =
        CanvasRotationForRun(adjusted_font->PlatformData().Orientation(),
                             segment.render_orientation, font_description);

    FontFeatureRanges& font_features = range_data->font_features;
    CapsFeatureSettingsScopedOverlay caps_overlay(
        &font_features, caps_support.FontFeatureToUse(small_caps_behavior));
    hb_direction_t direction = range_data->HarfBuzzDirection(canvas_rotation);
    FontFeatureRangesSaver font_features_saver(&font_features);
    bool is_han_kerning_comptued = false;
    if (han_kerning.MayApply()) [[unlikely]] {
      is_han_kerning_comptued = han_kerning.AppendFontFeatures(
          text_, shape_start, shape_end, *adjusted_font, locale,
          {.is_horizontal = HB_DIRECTION_IS_HORIZONTAL(direction),
           .is_line_start = range_data->options.is_line_start &&
                            range_data->start == shape_start,
           .apply_start = range_data->options.han_kerning_start &&
                          range_data->start == shape_start,
           .apply_end = range_data->options.han_kerning_end &&
                        range_data->end == shape_end},
          font_features);
    }

    if (!ShapeRange(range_data->buffer.Get(), range_data->font_features,
                    adjusted_font, current_font_data_for_range_set->Ranges(),
                    segment.script, direction, language,
                    font_description.SpecifiedSize(),
                    variation_selector_mode)) {
      DLOG(ERROR) << "Shaping range failed.";
    }

    ExtractShapeResults(range_data, font_cycle_queued, current_queue_item,
                        adjusted_font, segment.script, canvas_rotation,
                        fallback_stage, result);

    if (is_han_kerning_comptued) [[unlikely]] {
      if (!han_kerning.UnsafeToBreakBefore().empty()) [[unlikely]] {
        result->AddUnsafeToBreak(han_kerning.UnsafeToBreakBefore());
        han_kerning.ClearUnsafeToBreakBefore();
      }
      if (!range_data->reshape_queue.empty() &&
          RuntimeEnabledFeatures::TextSpacingTrimFallbackEnabled()) {
        han_kerning.PrepareFallback(text_);
      }
    }

    hb_buffer_reset(range_data->buffer.Get());
  }

  han_kerning.DidShapeSegment(*result);
}

ShapeResult* HarfBuzzShaper::Shape(const Font* font,
                                   TextDirection direction,
                                   unsigned start,
                                   unsigned end) const {
  CHECK_GE(end, start);
  CHECK_LE(end, text_.length());

  const unsigned length = end - start;
  ShapeResult* result =
      MakeGarbageCollected<ShapeResult>(start, length, direction);
  RangeContext range_data(font, direction, start, end);
  if (text_.Is8Bit()) {
    // 8-bit text is guaranteed to be horizontal latin-1.
    RunSegmenter::RunSegmenterRange segment_range = {
        start, end, USCRIPT_LATIN, OrientationIterator::kOrientationKeep,
        FontFallbackPriority::kText};
    ShapeSegment(&range_data, segment_range, result);

  } else {
    // Run segmentation needs to operate on the entire string, regardless of the
    // shaping window (defined by the start and end parameters).
    DCHECK(!text_.Is8Bit());
    RunSegmenter run_segmenter(text_.Span16(),
                               font->GetFontDescription().Orientation());
    RunSegmenter::RunSegmenterRange segment_range;
    while (run_segmenter.Consume(&segment_range)) {
      // Only shape segments overlapping with the range indicated by start and
      // end. Not only those strictly within.
      if (start < segment_range.end && end > segment_range.start) {
        ShapeSegment(&range_data, segment_range, result);
      }

      // Break if beyond the requested range. Because RunSegmenter is
      // incremental, further ranges are not needed. This also allows reusing
      // the segmenter state for next incremental calls.
      if (segment_range.end >= end) {
        break;
      }
    }
  }

#if EXPENSIVE_DCHECKS_ARE_ON()
  CheckShapeResultRange(result, start, end, text_, font);
#endif
  return result;
}

ShapeResult* HarfBuzzShaper::Shape(
    const Font* font,
    TextDirection direction,
    unsigned start,
    unsigned end,
    const Vector<RunSegmenter::RunSegmenterRange>& ranges,
    ShapeOptions options) const {
  CHECK_GE(end, start);
  CHECK_LE(end, text_.length());
  DCHECK_GT(ranges.size(), 0u);
  DCHECK_EQ(start, ranges[0].start);
  DCHECK_EQ(end, ranges[ranges.size() - 1].end);

  const unsigned length = end - start;
  ShapeResult* result =
      MakeGarbageCollected<ShapeResult>(start, length, direction);
  RangeContext range_data(font, direction, start, end, options);
  for (const RunSegmenter::RunSegmenterRange& segmented_range : ranges) {
    DCHECK_GE(segmented_range.end, segmented_range.start);
    DCHECK_GE(segmented_range.start, start);
    DCHECK_LE(segmented_range.end, end);
    ShapeSegment(&range_data, segmented_range, result);
  }

#if EXPENSIVE_DCHECKS_ARE_ON()
  CheckShapeResultRange(result, start, end, text_, font);
#endif
  return result;
}

ShapeResult* HarfBuzzShaper::Shape(
    const Font* font,
    TextDirection direction,
    unsigned start,
    unsigned end,
    const RunSegmenter::RunSegmenterRange pre_segmented,
    ShapeOptions options) const {
  CHECK_GE(end, start);
  CHECK_LE(end, text_.length());
  DCHECK_GE(start, pre_segmented.start);
  DCHECK_LE(end, pre_segmented.end);

  const unsigned length = end - start;
  ShapeResult* result =
      MakeGarbageCollected<ShapeResult>(start, length, direction);
  RangeContext range_data(font, direction, start, end, options);
  ShapeSegment(&range_data, pre_segmented, result);

#if EXPENSIVE_DCHECKS_ARE_ON()
  CheckShapeResultRange(result, start, end, text_, font);
#endif
  return result;
}

ShapeResult* HarfBuzzShaper::Shape(const Font* font,
                                   TextDirection direction) const {
  return Shape(font, direction, 0, text_.length());
}

void HarfBuzzShaper::GetGlyphData(const SimpleFontData& font_data,
                                  const LayoutLocale& locale,
                                  UScriptCode script,
                                  bool is_horizontal,
                                  TextDirection direction,
                                  GlyphDataList& glyphs) {
  PooledHarfBuzzBuffer pooled_hb_buffer;
  hb_buffer_t* hb_buffer = pooled_hb_buffer.Get();
  hb_buffer_set_language(hb_buffer, locale.HarfbuzzLanguage());
  hb_buffer_set_script(hb_buffer, ICUScriptToHBScript(script));
  hb_buffer_set_direction(
      hb_buffer, is_horizontal ? (blink::IsLtr(direction) ? HB_DIRECTION_LTR
                                                          : HB_DIRECTION_RTL)
                               : HB_DIRECTION_TTB);
  if (text_.Is8Bit()) {
    auto span = text_.Span8();
    hb_buffer_add_latin1(hb_buffer, span.data(),
                         base::checked_cast<int>(span.size()), 0,
                         text_.length());
  } else {
    static_assert(sizeof(uint16_t) == sizeof(UChar));
    auto span = text_.SpanUint16();
    hb_buffer_add_utf16(hb_buffer, span.data(),
                        base::checked_cast<int>(span.size()), 0,
                        text_.length());
  }

  const FontPlatformData& platform_data = font_data.PlatformData();
  HarfBuzzFace* const hb_face = platform_data.GetHarfBuzzFace();
  DCHECK(hb_face);
  hb_font_t* const hb_font = hb_face->GetScaledFont(
      nullptr,
      is_horizontal ? HarfBuzzFace::kNoVerticalLayout
                    : HarfBuzzFace::kPrepareForVerticalLayout,
      platform_data.size());
  DCHECK(hb_font);
  hb_shape_full(hb_font, hb_buffer, nullptr, 0, ShapingBackend());

  // Create `GlyphDataList` from `hb_buffer`.
  unsigned num_glyphs;
  hb_glyph_info_t* glyph_info =
      hb_buffer_get_glyph_infos(hb_buffer, &num_glyphs);
  hb_glyph_position_t* glyph_position =
      hb_buffer_get_glyph_positions(hb_buffer, nullptr);
  glyphs.reserve(num_glyphs);
  for (; num_glyphs;
       --num_glyphs, UNSAFE_TODO(++glyph_info), UNSAFE_TODO(++glyph_position)) {
    glyphs.push_back(GlyphData{
        .cluster = glyph_info->cluster,
        .glyph = static_cast<Glyph>(glyph_info->codepoint),
        .advance = {HarfBuzzPositionToFloat(glyph_position->x_advance),
                    -HarfBuzzPositionToFloat(glyph_position->y_advance)},
        .offset = {HarfBuzzPositionToFloat(glyph_position->x_offset),
                   -HarfBuzzPositionToFloat(glyph_position->y_offset)}});
  }
}

}  // namespace blink