| // Copyright 2018 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "third_party/blink/renderer/platform/fonts/shaping/shape_result_view.h" |
| |
| #include <iterator> |
| #include "base/containers/adapters.h" |
| #include "build/build_config.h" |
| #include "third_party/blink/renderer/platform/fonts/font.h" |
| #include "third_party/blink/renderer/platform/fonts/shaping/glyph_bounds_accumulator.h" |
| #include "third_party/blink/renderer/platform/fonts/shaping/shape_result_inline_headers.h" |
| |
| namespace blink { |
| |
| struct ShapeResultView::RunInfoPart { |
| USING_FAST_MALLOC(RunInfoPart); |
| |
| public: |
| RunInfoPart(scoped_refptr<const ShapeResult::RunInfo> run, |
| ShapeResult::RunInfo::GlyphDataRange range, |
| unsigned start_index, |
| unsigned offset, |
| unsigned num_characters, |
| float width) |
| : run_(run), |
| range_(range), |
| start_index_(start_index), |
| offset_(offset), |
| num_characters_(num_characters), |
| width_(width) {} |
| |
| using const_iterator = const HarfBuzzRunGlyphData*; |
| const_iterator begin() const { return range_.begin; } |
| const_iterator end() const { return range_.end; } |
| using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
| const_reverse_iterator rbegin() const { |
| return const_reverse_iterator(end()); |
| } |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(begin()); |
| } |
| const HarfBuzzRunGlyphData& GlyphAt(unsigned index) const { |
| return *(range_.begin + index); |
| } |
| // The end character index of |this| without considering offsets in |
| // |ShapeResultView|. This is analogous to: |
| // GlyphAt(Rtl() ? -1 : NumGlyphs()).character_index |
| // if such |HarfBuzzRunGlyphData| is available. |
| unsigned CharacterIndexOfEndGlyph() const { |
| return num_characters_ + offset_; |
| } |
| |
| bool Rtl() const { return run_->Rtl(); } |
| bool IsHorizontal() const { return run_->IsHorizontal(); } |
| unsigned NumCharacters() const { return num_characters_; } |
| unsigned NumGlyphs() const { return range_.end - range_.begin; } |
| float Width() const { return width_; } |
| |
| unsigned PreviousSafeToBreakOffset(unsigned offset) const; |
| |
| // Common signatures with RunInfo, to templatize algorithms. |
| const ShapeResult::RunInfo* GetRunInfo() const { return run_.get(); } |
| const ShapeResult::RunInfo::GlyphDataRange& GetGlyphDataRange() const { |
| return range_; |
| } |
| ShapeResult::RunInfo::GlyphDataRange FindGlyphDataRange( |
| unsigned start_character_index, |
| unsigned end_character_index) const { |
| return GetGlyphDataRange().FindGlyphDataRange(Rtl(), start_character_index, |
| end_character_index); |
| } |
| unsigned OffsetToRunStartIndex() const { return offset_; } |
| |
| scoped_refptr<const ShapeResult::RunInfo> run_; |
| ShapeResult::RunInfo::GlyphDataRange range_; |
| |
| // Start index for partial run, adjusted to ensure that runs are continuous. |
| unsigned start_index_; |
| |
| // Offset relative to start index for the original run. |
| unsigned offset_; |
| |
| unsigned num_characters_; |
| float width_; |
| }; |
| |
| unsigned ShapeResultView::RunInfoPart::PreviousSafeToBreakOffset( |
| unsigned offset) const { |
| if (offset >= NumCharacters()) |
| return NumCharacters(); |
| if (!Rtl()) { |
| for (const auto& glyph : base::Reversed(*this)) { |
| if (glyph.safe_to_break_before && glyph.character_index <= offset) |
| return glyph.character_index; |
| } |
| } else { |
| for (const auto& glyph : *this) { |
| if (glyph.safe_to_break_before && glyph.character_index <= offset) |
| return glyph.character_index; |
| } |
| } |
| |
| // Next safe break is at the start of the run. |
| return 0; |
| } |
| |
| // The offset to add to |HarfBuzzRunGlyphData.character_index| to compute the |
| // character index of the source string. |
| unsigned ShapeResultView::CharacterIndexOffsetForGlyphData( |
| const RunInfoPart& part) const { |
| return part.start_index_ + char_index_offset_ - part.offset_; |
| } |
| |
| template <class ShapeResultType> |
| ShapeResultView::ShapeResultView(const ShapeResultType* other) |
| : primary_font_(other->primary_font_), |
| start_index_(0), |
| num_characters_(0), |
| num_glyphs_(0), |
| direction_(other->direction_), |
| has_vertical_offsets_(other->has_vertical_offsets_), |
| width_(0) {} |
| |
| ShapeResultView::~ShapeResultView() = default; |
| |
| scoped_refptr<ShapeResult> ShapeResultView::CreateShapeResult() const { |
| ShapeResult* new_result = |
| new ShapeResult(primary_font_, num_characters_, Direction()); |
| new_result->runs_.ReserveCapacity(parts_.size()); |
| for (const auto& part : parts_) { |
| auto new_run = ShapeResult::RunInfo::Create( |
| part->run_->font_data_.get(), part->run_->direction_, |
| part->run_->canvas_rotation_, part->run_->script_, part->start_index_, |
| part->NumGlyphs(), part->num_characters_); |
| std::copy(part->range_.begin, part->range_.end, |
| new_run->glyph_data_.begin()); |
| for (HarfBuzzRunGlyphData& glyph_data : new_run->glyph_data_) { |
| glyph_data.character_index -= part->offset_; |
| } |
| |
| new_run->start_index_ += char_index_offset_; |
| new_run->width_ = part->width_; |
| new_run->num_characters_ = part->num_characters_; |
| new_result->runs_.push_back(std::move(new_run)); |
| } |
| |
| new_result->start_index_ = start_index_ + char_index_offset_; |
| new_result->num_glyphs_ = num_glyphs_; |
| new_result->has_vertical_offsets_ = has_vertical_offsets_; |
| new_result->width_ = width_; |
| |
| return base::AdoptRef(new_result); |
| } |
| |
| template <class ShapeResultType> |
| void ShapeResultView::CreateViewsForResult(const ShapeResultType* other, |
| unsigned start_index, |
| unsigned end_index) { |
| bool first_result = num_characters_ == 0; |
| for (const auto& run : other->RunsOrParts()) { |
| if (!run->GetRunInfo()) |
| continue; |
| // Compute start/end of the run, or of the part if ShapeResultView. |
| unsigned part_start = run->start_index_ + other->StartIndexOffsetForRun(); |
| unsigned run_end = part_start + run->num_characters_; |
| if (start_index < run_end && end_index > part_start) { |
| ShapeResult::RunInfo::GlyphDataRange range; |
| |
| // Adjust start/end to the character index of |RunInfo|. The start index |
| // of |RunInfo| could be different from |part_start| for ShapeResultView. |
| DCHECK_GE(part_start, run->OffsetToRunStartIndex()); |
| unsigned run_start = part_start - run->OffsetToRunStartIndex(); |
| unsigned adjusted_start = |
| start_index > run_start ? start_index - run_start : 0; |
| unsigned adjusted_end = std::min(end_index, run_end) - run_start; |
| DCHECK(adjusted_end > adjusted_start); |
| unsigned part_characters = adjusted_end - adjusted_start; |
| float part_width; |
| |
| // Avoid O(log n) find operation if the entire run is in range. |
| if (part_start >= start_index && run_end <= end_index) { |
| range = run->GetGlyphDataRange(); |
| part_width = run->width_; |
| } else { |
| range = run->FindGlyphDataRange(adjusted_start, adjusted_end); |
| part_width = 0; |
| for (auto* glyph = range.begin; glyph != range.end; glyph++) |
| part_width += glyph->advance; |
| } |
| |
| // Adjust start_index for runs to be continuous. |
| unsigned part_start_index; |
| unsigned part_offset; |
| if (!run->Rtl()) { // Left-to-right |
| part_start_index = start_index_ + num_characters_; |
| part_offset = adjusted_start; |
| } else { // Right-to-left |
| part_start_index = run->start_index_ + adjusted_start; |
| part_offset = adjusted_start; |
| } |
| |
| parts_.push_back(std::make_unique<RunInfoPart>( |
| run->GetRunInfo(), range, part_start_index, part_offset, |
| part_characters, part_width)); |
| |
| num_characters_ += part_characters; |
| num_glyphs_ += range.end - range.begin; |
| width_ += part_width; |
| } |
| } |
| |
| if (first_result || Rtl()) |
| start_index_ = ComputeStartIndex(); |
| } |
| |
| scoped_refptr<ShapeResultView> ShapeResultView::Create(const Segment* segments, |
| size_t segment_count) { |
| DCHECK_GT(segment_count, 0u); |
| #if DCHECK_IS_ON() |
| for (unsigned i = 0; i < segment_count; ++i) { |
| DCHECK((segments[i].result || segments[i].view) && |
| (!segments[i].result || !segments[i].view)); |
| } |
| #endif |
| ShapeResultView* out = segments[0].result |
| ? new ShapeResultView(segments[0].result) |
| : new ShapeResultView(segments[0].view); |
| out->AddSegments(segments, segment_count); |
| return base::AdoptRef(out); |
| } |
| |
| scoped_refptr<ShapeResultView> ShapeResultView::Create( |
| const ShapeResult* result, |
| unsigned start_index, |
| unsigned end_index) { |
| Segment segment = {result, start_index, end_index}; |
| return Create(&segment, 1); |
| } |
| |
| scoped_refptr<ShapeResultView> ShapeResultView::Create( |
| const ShapeResultView* result, |
| unsigned start_index, |
| unsigned end_index) { |
| Segment segment = {result, start_index, end_index}; |
| return Create(&segment, 1); |
| } |
| |
| scoped_refptr<ShapeResultView> ShapeResultView::Create( |
| const ShapeResult* result) { |
| // This specialization is an optimization to allow the bounding box to be |
| // re-used. |
| ShapeResultView* out = new ShapeResultView(result); |
| out->char_index_offset_ = out->Rtl() ? 0 : result->StartIndex(); |
| out->CreateViewsForResult(result, 0, std::numeric_limits<unsigned>::max()); |
| out->has_vertical_offsets_ = result->has_vertical_offsets_; |
| return base::AdoptRef(out); |
| } |
| |
| void ShapeResultView::AddSegments(const Segment* segments, |
| size_t segment_count) { |
| // This method assumes that no parts have been added yet. |
| DCHECK_EQ(parts_.size(), 0u); |
| |
| // Segments are in logical order, runs and parts are in visual order. Iterate |
| // over segments back-to-front for RTL. |
| DCHECK_GT(segment_count, 0u); |
| unsigned last_segment_index = segment_count - 1; |
| |
| // Compute start index offset for the overall run. This is added to the start |
| // index of each glyph to ensure consistency with ShapeResult::SubRange |
| if (!Rtl()) { // Left-to-right |
| char_index_offset_ = segments[0].result ? segments[0].result->StartIndex() |
| : segments[0].view->StartIndex(); |
| char_index_offset_ = std::max(char_index_offset_, segments[0].start_index); |
| } else { // Right to left |
| char_index_offset_ = 0; |
| } |
| |
| for (unsigned i = 0; i < segment_count; i++) { |
| const Segment& segment = segments[Rtl() ? last_segment_index - i : i]; |
| if (segment.result) { |
| DCHECK_EQ(segment.result->Direction(), Direction()); |
| CreateViewsForResult(segment.result, segment.start_index, |
| segment.end_index); |
| has_vertical_offsets_ |= segment.result->has_vertical_offsets_; |
| } else if (segment.view) { |
| DCHECK_EQ(segment.view->Direction(), Direction()); |
| CreateViewsForResult(segment.view, segment.start_index, |
| segment.end_index); |
| has_vertical_offsets_ |= segment.view->has_vertical_offsets_; |
| } else { |
| NOTREACHED(); |
| } |
| } |
| } |
| |
| unsigned ShapeResultView::ComputeStartIndex() const { |
| if (UNLIKELY(parts_.IsEmpty())) |
| return 0; |
| const RunInfoPart& first_part = *parts_.front(); |
| if (!Rtl()) // Left-to-right. |
| return first_part.start_index_; |
| // Right-to-left. |
| unsigned end_index = first_part.start_index_ + first_part.num_characters_; |
| return end_index - num_characters_; |
| } |
| |
| unsigned ShapeResultView::PreviousSafeToBreakOffset(unsigned index) const { |
| for (auto it = parts_.rbegin(); it != parts_.rend(); ++it) { |
| const auto& part = *it; |
| if (!part) |
| continue; |
| |
| unsigned run_start = part->start_index_; |
| if (index >= run_start) { |
| unsigned offset = index - run_start; |
| if (offset <= part->num_characters_) { |
| return part->PreviousSafeToBreakOffset(offset) + run_start; |
| } |
| if (!Rtl()) { |
| return run_start + part->num_characters_; |
| } |
| } else if (Rtl()) { |
| if (it == parts_.rbegin()) |
| return part->start_index_; |
| const auto& previous_run = *--it; |
| return previous_run->start_index_ + previous_run->num_characters_; |
| } |
| } |
| |
| return StartIndex(); |
| } |
| |
| void ShapeResultView::GetRunFontData( |
| Vector<ShapeResult::RunFontData>* font_data) const { |
| for (const auto& part : parts_) { |
| font_data->push_back(ShapeResult::RunFontData( |
| {part->run_->font_data_.get(), part->end() - part->begin()})); |
| } |
| } |
| |
| void ShapeResultView::FallbackFonts( |
| HashSet<const SimpleFontData*>* fallback) const { |
| DCHECK(fallback); |
| DCHECK(primary_font_); |
| for (const auto& part : parts_) { |
| if (part->run_->font_data_ && part->run_->font_data_ != primary_font_) { |
| fallback->insert(part->run_->font_data_.get()); |
| } |
| } |
| } |
| |
| float ShapeResultView::ForEachGlyph(float initial_advance, |
| GlyphCallback glyph_callback, |
| void* context) const { |
| auto total_advance = initial_advance; |
| for (const auto& part : parts_) { |
| const auto& run = part->run_; |
| bool is_horizontal = HB_DIRECTION_IS_HORIZONTAL(run->direction_); |
| const SimpleFontData* font_data = run->font_data_.get(); |
| const unsigned character_index_offset_for_glyph_data = |
| CharacterIndexOffsetForGlyphData(*part); |
| for (const auto& glyph_data : *part) { |
| unsigned character_index = |
| glyph_data.character_index + character_index_offset_for_glyph_data; |
| glyph_callback(context, character_index, glyph_data.glyph, |
| glyph_data.offset, total_advance, is_horizontal, |
| run->canvas_rotation_, font_data); |
| total_advance += glyph_data.advance; |
| } |
| } |
| |
| return total_advance; |
| } |
| |
| float ShapeResultView::ForEachGlyph(float initial_advance, |
| unsigned from, |
| unsigned to, |
| unsigned index_offset, |
| GlyphCallback glyph_callback, |
| void* context) const { |
| auto total_advance = initial_advance; |
| |
| for (const auto& part : parts_) { |
| const auto& run = part->run_; |
| bool is_horizontal = HB_DIRECTION_IS_HORIZONTAL(run->direction_); |
| const SimpleFontData* font_data = run->font_data_.get(); |
| const unsigned character_index_offset_for_glyph_data = |
| CharacterIndexOffsetForGlyphData(*part); |
| |
| if (!run->Rtl()) { // Left-to-right |
| for (const auto& glyph_data : *part) { |
| unsigned character_index = |
| glyph_data.character_index + character_index_offset_for_glyph_data; |
| if (character_index >= to) |
| break; |
| if (character_index >= from) { |
| glyph_callback(context, character_index, glyph_data.glyph, |
| glyph_data.offset, total_advance, is_horizontal, |
| run->canvas_rotation_, font_data); |
| } |
| total_advance += glyph_data.advance; |
| } |
| |
| } else { // Right-to-left |
| for (const auto& glyph_data : *part) { |
| unsigned character_index = |
| glyph_data.character_index + character_index_offset_for_glyph_data; |
| if (character_index < from) |
| break; |
| if (character_index < to) { |
| glyph_callback(context, character_index, glyph_data.glyph, |
| glyph_data.offset, total_advance, is_horizontal, |
| run->canvas_rotation_, font_data); |
| } |
| total_advance += glyph_data.advance; |
| } |
| } |
| } |
| return total_advance; |
| } |
| |
| float ShapeResultView::ForEachGraphemeClusters(const StringView& text, |
| float initial_advance, |
| unsigned from, |
| unsigned to, |
| unsigned index_offset, |
| GraphemeClusterCallback callback, |
| void* context) const { |
| unsigned run_offset = index_offset; |
| float advance_so_far = initial_advance; |
| |
| for (const auto& part : parts_) { |
| const auto& run = part->run_; |
| unsigned graphemes_in_cluster = 1; |
| float cluster_advance = 0; |
| bool rtl = Direction() == TextDirection::kRtl; |
| |
| // A "cluster" in this context means a cluster as it is used by HarfBuzz: |
| // The minimal group of characters and corresponding glyphs, that cannot be |
| // broken down further from a text shaping point of view. A cluster can |
| // contain multiple glyphs and grapheme clusters, with mutually overlapping |
| // boundaries. |
| const unsigned character_index_offset_for_glyph_data = |
| CharacterIndexOffsetForGlyphData(*part) + run_offset; |
| uint16_t cluster_start = |
| static_cast<uint16_t>(rtl ? part->CharacterIndexOfEndGlyph() + |
| character_index_offset_for_glyph_data |
| : part->GlyphAt(0).character_index + |
| character_index_offset_for_glyph_data); |
| |
| const unsigned num_glyphs = part->NumGlyphs(); |
| for (unsigned i = 0; i < num_glyphs; ++i) { |
| const HarfBuzzRunGlyphData& glyph_data = part->GlyphAt(i); |
| uint16_t current_character_index = |
| glyph_data.character_index + character_index_offset_for_glyph_data; |
| |
| bool is_run_end = (i + 1 == num_glyphs); |
| bool is_cluster_end = |
| is_run_end || (part->GlyphAt(i + 1).character_index + |
| character_index_offset_for_glyph_data != |
| current_character_index); |
| |
| if ((rtl && current_character_index >= to) || |
| (!rtl && current_character_index < from)) { |
| advance_so_far += glyph_data.advance; |
| rtl ? --cluster_start : ++cluster_start; |
| continue; |
| } |
| |
| cluster_advance += glyph_data.advance; |
| |
| if (text.Is8Bit()) { |
| callback(context, current_character_index, advance_so_far, 1, |
| glyph_data.advance, run->canvas_rotation_); |
| |
| advance_so_far += glyph_data.advance; |
| } else if (is_cluster_end) { |
| uint16_t cluster_end; |
| if (rtl) { |
| cluster_end = current_character_index; |
| } else { |
| cluster_end = static_cast<uint16_t>( |
| is_run_end ? part->CharacterIndexOfEndGlyph() + |
| character_index_offset_for_glyph_data |
| : part->GlyphAt(i + 1).character_index + |
| character_index_offset_for_glyph_data); |
| } |
| graphemes_in_cluster = ShapeResult::CountGraphemesInCluster( |
| text.Span16(), cluster_start, cluster_end); |
| if (!graphemes_in_cluster || !cluster_advance) |
| continue; |
| |
| callback(context, current_character_index, advance_so_far, |
| graphemes_in_cluster, cluster_advance, run->canvas_rotation_); |
| advance_so_far += cluster_advance; |
| |
| cluster_start = cluster_end; |
| cluster_advance = 0; |
| } |
| } |
| } |
| return advance_so_far; |
| } |
| |
| template <bool is_horizontal_run> |
| void ShapeResultView::ComputePartInkBounds( |
| const ShapeResultView::RunInfoPart& part, |
| float run_advance, |
| FloatRect* ink_bounds) const { |
| // Get glyph bounds from Skia. It's a lot faster if we give it list of glyph |
| // IDs rather than calling it for each glyph. |
| // TODO(kojii): MacOS does not benefit from batching the Skia request due to |
| // https://bugs.chromium.org/p/skia/issues/detail?id=5328, and the cost to |
| // prepare batching, which is normally much less than the benefit of |
| // batching, is not ignorable unfortunately. |
| const SimpleFontData& current_font_data = *part.run_->font_data_; |
| unsigned num_glyphs = part.NumGlyphs(); |
| #if !defined(OS_MACOSX) |
| Vector<Glyph, 256> glyphs(num_glyphs); |
| unsigned i = 0; |
| for (const auto& glyph_data : part) |
| glyphs[i++] = glyph_data.glyph; |
| Vector<SkRect, 256> bounds_list(num_glyphs); |
| current_font_data.BoundsForGlyphs(glyphs, &bounds_list); |
| #endif |
| |
| GlyphBoundsAccumulator bounds(run_advance); |
| for (unsigned i = 0; i < num_glyphs; ++i) { |
| const HarfBuzzRunGlyphData& glyph_data = part.GlyphAt(i); |
| #if defined(OS_MACOSX) |
| FloatRect glyph_bounds = current_font_data.BoundsForGlyph(glyph_data.glyph); |
| #else |
| FloatRect glyph_bounds(bounds_list[i]); |
| #endif |
| bounds.Unite<is_horizontal_run>(glyph_data, glyph_bounds); |
| bounds.origin += glyph_data.advance; |
| } |
| |
| if (!is_horizontal_run) |
| bounds.ConvertVerticalRunToLogical(current_font_data.GetFontMetrics()); |
| ink_bounds->Unite(bounds.bounds); |
| } |
| |
| FloatRect ShapeResultView::ComputeInkBounds() const { |
| FloatRect ink_bounds; |
| |
| float run_advance = 0.0f; |
| for (const auto& part : parts_) { |
| if (part->IsHorizontal()) |
| ComputePartInkBounds<true>(*part.get(), run_advance, &ink_bounds); |
| else |
| ComputePartInkBounds<false>(*part.get(), run_advance, &ink_bounds); |
| run_advance += part->Width(); |
| } |
| |
| return ink_bounds; |
| } |
| |
| } // namespace blink |