1 /*
2 * Copyright (c) 2012 Google Inc. All rights reserved.
3 * Copyright (C) 2013 BlackBerry Limited. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following disclaimer
13 * in the documentation and/or other materials provided with the
14 * distribution.
15 * * Neither the name of Google Inc. nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include "third_party/blink/renderer/platform/fonts/shaping/shape_result.h"
33
34 #include <hb.h>
35 #include <algorithm>
36 #include <limits>
37 #include <memory>
38 #include <utility>
39
40 #include "base/containers/adapters.h"
41 #include "base/memory/ptr_util.h"
42 #include "base/numerics/safe_conversions.h"
43 #include "build/build_config.h"
44 #include "third_party/blink/renderer/platform/fonts/character_range.h"
45 #include "third_party/blink/renderer/platform/fonts/font.h"
46 #include "third_party/blink/renderer/platform/fonts/shaping/glyph_bounds_accumulator.h"
47 #include "third_party/blink/renderer/platform/fonts/shaping/shape_result_inline_headers.h"
48 #include "third_party/blink/renderer/platform/fonts/shaping/shape_result_spacing.h"
49 #include "third_party/blink/renderer/platform/text/text_break_iterator.h"
50 #include "third_party/blink/renderer/platform/wtf/size_assertions.h"
51 #include "third_party/blink/renderer/platform/wtf/text/string_builder.h"
52
53 namespace blink {
54
55 constexpr unsigned HarfBuzzRunGlyphData::kMaxCharacterIndex;
56 constexpr unsigned HarfBuzzRunGlyphData::kMaxGlyphs;
57
58 struct SameSizeAsHarfBuzzRunGlyphData {
59 unsigned glyph : 16;
60 unsigned char_index_and_bit_field : 16;
61 float advance;
62 };
63
64 ASSERT_SIZE(HarfBuzzRunGlyphData, SameSizeAsHarfBuzzRunGlyphData);
65
66 struct SameSizeAsShapeResult : public RefCounted<SameSizeAsShapeResult> {
67 float floats[5];
68 Vector<int> vector;
69 void* pointers[2];
70 unsigned integers[2];
71 unsigned bitfields : 32;
72 };
73
74 ASSERT_SIZE(ShapeResult, SameSizeAsShapeResult);
75
NextSafeToBreakOffset(unsigned offset) const76 unsigned ShapeResult::RunInfo::NextSafeToBreakOffset(unsigned offset) const {
77 DCHECK_LE(offset, num_characters_);
78 if (!Rtl()) {
79 for (const auto& glyph_data : glyph_data_) {
80 if (glyph_data.safe_to_break_before &&
81 glyph_data.character_index >= offset)
82 return glyph_data.character_index;
83 }
84 } else {
85 for (const auto& glyph_data : base::Reversed(glyph_data_)) {
86 if (glyph_data.safe_to_break_before &&
87 glyph_data.character_index >= offset)
88 return glyph_data.character_index;
89 }
90 }
91
92 // Next safe break is at the end of the run.
93 return num_characters_;
94 }
95
PreviousSafeToBreakOffset(unsigned offset) const96 unsigned ShapeResult::RunInfo::PreviousSafeToBreakOffset(
97 unsigned offset) const {
98 if (offset >= num_characters_)
99 return num_characters_;
100 if (!Rtl()) {
101 for (const auto& glyph_data : base::Reversed(glyph_data_)) {
102 if (glyph_data.safe_to_break_before &&
103 glyph_data.character_index <= offset)
104 return glyph_data.character_index;
105 }
106 } else {
107 for (const auto& glyph_data : glyph_data_) {
108 if (glyph_data.safe_to_break_before &&
109 glyph_data.character_index <= offset)
110 return glyph_data.character_index;
111 }
112 }
113
114 // Next safe break is at the start of the run.
115 return 0;
116 }
117
XPositionForVisualOffset(unsigned offset,AdjustMidCluster adjust_mid_cluster) const118 float ShapeResult::RunInfo::XPositionForVisualOffset(
119 unsigned offset,
120 AdjustMidCluster adjust_mid_cluster) const {
121 DCHECK_LT(offset, num_characters_);
122 if (Rtl())
123 offset = num_characters_ - offset - 1;
124 return XPositionForOffset(offset, adjust_mid_cluster);
125 }
126
NumGraphemes(unsigned start,unsigned end) const127 unsigned ShapeResult::RunInfo::NumGraphemes(unsigned start,
128 unsigned end) const {
129 if (graphemes_.size() == 0 || start >= num_characters_)
130 return 0;
131 CHECK_LT(start, end);
132 CHECK_LE(end, num_characters_);
133 CHECK_EQ(num_characters_, graphemes_.size());
134 return graphemes_[end - 1] - graphemes_[start] + 1;
135 }
136
EnsureGraphemes(const StringView & text) const137 void ShapeResult::EnsureGraphemes(const StringView& text) const {
138 CHECK_EQ(NumCharacters(), text.length());
139
140 // Hit-testing, canvas, etc. may still call this function for 0-length text,
141 // or glyphs may be missing at all.
142 if (runs_.IsEmpty())
143 return;
144
145 bool is_computed = !runs_.front()->graphemes_.IsEmpty();
146 #if DCHECK_IS_ON()
147 for (const auto& run : runs_)
148 DCHECK_EQ(is_computed, !run->graphemes_.IsEmpty());
149 #endif
150 if (is_computed)
151 return;
152
153 unsigned result_start_index = StartIndex();
154 for (const scoped_refptr<RunInfo>& run : runs_) {
155 if (!run)
156 continue;
157 DCHECK_GE(run->start_index_, result_start_index);
158 GraphemesClusterList(
159 StringView(text, run->start_index_ - result_start_index,
160 run->num_characters_),
161 &run->graphemes_);
162 }
163 }
164
165 // XPositionForOffset returns the X position (in layout space) from the
166 // beginning of the run to the beginning of the cluster of glyphs for X
167 // character.
168 // For RTL, beginning means the right most side of the cluster.
169 // Characters may spawn multiple glyphs.
170 // In the case that multiple characters form a Unicode grapheme cluster, we
171 // distribute the width of the grapheme cluster among the number of cursor
172 // positions returned by cursor-based TextBreakIterator.
XPositionForOffset(unsigned offset,AdjustMidCluster adjust_mid_cluster) const173 float ShapeResult::RunInfo::XPositionForOffset(
174 unsigned offset,
175 AdjustMidCluster adjust_mid_cluster) const {
176 DCHECK_LE(offset, num_characters_);
177 const unsigned num_glyphs = glyph_data_.size();
178
179 // In this context, a glyph sequence is a sequence of glyphs that shares the
180 // same character_index and therefore represent the same interval of source
181 // characters. glyph_sequence_start marks the character index at the beginning
182 // of the interval of characters for which this glyph sequence was formed as
183 // the result of shaping; glyph_sequence_end marks the end of the interval of
184 // characters for which this glyph sequence was formed. [glyph_sequence_start,
185 // glyph_sequence_end) is inclusive on the start for the range of characters
186 // of the current sequence we are visiting.
187 unsigned glyph_sequence_start = 0;
188 unsigned glyph_sequence_end = num_characters_;
189 // the advance of the current glyph sequence.
190 float glyph_sequence_advance = 0.0;
191 // the accumulated advance up to the current glyph sequence.
192 float accumulated_position = 0;
193
194 if (!Rtl()) {
195 for (unsigned i = 0; i < num_glyphs; ++i) {
196 unsigned current_glyph_char_index = glyph_data_[i].character_index;
197 // If this glyph is still part of the same glyph sequence for the grapheme
198 // cluster at character index glyph_sequence_start, add its advance to the
199 // glyph_sequence's advance.
200 if (glyph_sequence_start == current_glyph_char_index) {
201 glyph_sequence_advance += glyph_data_[i].advance;
202 continue;
203 }
204
205 // We are about to move out of a glyph sequence that contains offset, so
206 // the current glyph sequence is the one we are looking for.
207 if (glyph_sequence_start <= offset && offset < current_glyph_char_index) {
208 glyph_sequence_end = current_glyph_char_index;
209 break;
210 }
211
212 glyph_sequence_start = current_glyph_char_index;
213 // Since we always update glyph_sequence_end when we break, set this to
214 // last_character in case this is the final iteration of the loop.
215 glyph_sequence_end = num_characters_;
216 accumulated_position += glyph_sequence_advance;
217 glyph_sequence_advance = glyph_data_[i].advance;
218 }
219
220 } else {
221 glyph_sequence_start = glyph_sequence_end = num_characters_;
222
223 for (unsigned i = 0; i < num_glyphs; ++i) {
224 unsigned current_glyph_char_index = glyph_data_[i].character_index;
225 // If this glyph is still part of the same glyph sequence for the grapheme
226 // cluster at character index glyph_sequence_start, add its advance to the
227 // glyph_sequence's advance.
228 if (glyph_sequence_start == current_glyph_char_index) {
229 glyph_sequence_advance += glyph_data_[i].advance;
230 continue;
231 }
232
233 // We are about to move out of a glyph sequence that contains offset, so
234 // the current glyph sequence is the one we are looking for.
235 if (glyph_sequence_start <= offset && offset < glyph_sequence_end) {
236 break;
237 }
238
239 glyph_sequence_end = glyph_sequence_start;
240 glyph_sequence_start = current_glyph_char_index;
241 accumulated_position += glyph_sequence_advance;
242 glyph_sequence_advance = glyph_data_[i].advance;
243 }
244 }
245
246 // This is the character position inside the glyph sequence.
247 unsigned pos = offset - glyph_sequence_start;
248
249 // We calculate the number of Unicode grapheme clusters (actually cursor
250 // position stops) on the subset of characters. We use this to divide
251 // glyph_sequence_advance by the number of unicode grapheme clusters this
252 // glyph sequence was shaped for, and thus linearly interpolate the cursor
253 // position based on accumulated position and a fraction of
254 // glyph_sequence_advance.
255 unsigned graphemes = NumGraphemes(glyph_sequence_start, glyph_sequence_end);
256 if (graphemes > 1) {
257 DCHECK_GE(glyph_sequence_end, glyph_sequence_start);
258 unsigned size = glyph_sequence_end - glyph_sequence_start;
259 unsigned place = graphemes * pos / size;
260 pos -= place;
261 glyph_sequence_advance = glyph_sequence_advance / graphemes;
262 if (Rtl()) {
263 accumulated_position += glyph_sequence_advance * (graphemes - place - 1);
264 } else {
265 accumulated_position += glyph_sequence_advance * place;
266 }
267 }
268
269 // Re-adapt based on adjust_mid_cluster. On LTR, if we want AdjustToEnd and
270 // offset is not at the beginning, we need to jump to the right side of the
271 // grapheme. On RTL, if we want AdjustToStart and offset is not at the end, we
272 // need to jump to the left side of the grapheme.
273 if (!Rtl() && adjust_mid_cluster == AdjustMidCluster::kToEnd && pos != 0) {
274 accumulated_position += glyph_sequence_advance;
275 } else if (Rtl() && adjust_mid_cluster == AdjustMidCluster::kToEnd &&
276 pos != 0) {
277 accumulated_position -= glyph_sequence_advance;
278 }
279
280 if (Rtl()) {
281 // For RTL, we return the right side.
282 accumulated_position += glyph_sequence_advance;
283 }
284
285 return accumulated_position;
286 }
287
288 // In some ways, CharacterIndexForXPosition is the reverse of
289 // XPositionForOffset. Given a target pixel distance on screen space, returns a
290 // character index for the end of the interval that would be included within
291 // that space. @break_glyphs_option controls wether we use grapheme information
292 // to break glyphs into grapheme clusters and return character that are a part
293 // of a glyph.
CharacterIndexForXPosition(float target_x,BreakGlyphsOption break_glyphs_option,GlyphIndexResult * result) const294 void ShapeResult::RunInfo::CharacterIndexForXPosition(
295 float target_x,
296 BreakGlyphsOption break_glyphs_option,
297 GlyphIndexResult* result) const {
298 DCHECK(target_x >= 0 && target_x <= width_);
299
300 result->origin_x = 0;
301 unsigned glyph_sequence_start = 0;
302 unsigned glyph_sequence_end = num_characters_;
303 result->advance = 0.0;
304
305 // on RTL, we start on the last index.
306 if (Rtl()) {
307 glyph_sequence_start = glyph_sequence_end = num_characters_;
308 }
309
310 for (const HarfBuzzRunGlyphData& glyph_data : glyph_data_) {
311 unsigned current_glyph_char_index = glyph_data.character_index;
312 // If the glyph is part of the same sequence, we just accumulate the
313 // advance.
314 if (glyph_sequence_start == current_glyph_char_index) {
315 result->advance += glyph_data.advance;
316 continue;
317 }
318
319 // Since we are about to move to the next sequence of glyphs, check if
320 // the target falls inside it, if it does, we found our sequence.
321 if (result->origin_x + result->advance > target_x) {
322 if (!Rtl()) {
323 glyph_sequence_end = current_glyph_char_index;
324 }
325 break;
326 }
327
328 // Move to the next sequence, update accumulated_x.
329 if (Rtl()) {
330 // Notice that on RTL, as we move to our next sequence, we already know
331 // both bounds. Nonetheless, we still need to move forward so we can
332 // capture all glyphs of this sequence.
333 glyph_sequence_end = glyph_sequence_start;
334 }
335 glyph_sequence_start = current_glyph_char_index;
336 result->origin_x += result->advance;
337 result->advance = glyph_data.advance;
338 }
339
340 // At this point, we have [glyph_sequence_start, glyph_sequence_end)
341 // representing a sequence of glyphs, of size glyph_sequence_advance. We
342 // linearly interpolate how much space each character takes, and reduce the
343 // sequence to only match the character size.
344 if (break_glyphs_option == BreakGlyphs &&
345 glyph_sequence_end > glyph_sequence_start) {
346 int graphemes = NumGraphemes(glyph_sequence_start, glyph_sequence_end);
347 if (graphemes > 1) {
348 float unit_size = result->advance / graphemes;
349 unsigned step = floor((target_x - result->origin_x) / unit_size);
350 unsigned glyph_length = glyph_sequence_end - glyph_sequence_start;
351 unsigned final_size = floor(glyph_length / graphemes);
352 result->origin_x += unit_size * step;
353 if (!Rtl()) {
354 glyph_sequence_start += step;
355 glyph_sequence_end = glyph_sequence_start + final_size;
356 } else {
357 glyph_sequence_end -= step;
358 glyph_sequence_start = glyph_sequence_end - final_size;
359 }
360 result->advance = unit_size;
361 }
362 }
363
364 if (!Rtl()) {
365 result->left_character_index = glyph_sequence_start;
366 result->right_character_index = glyph_sequence_end;
367 } else {
368 result->left_character_index = glyph_sequence_end;
369 result->right_character_index = glyph_sequence_start;
370 }
371 }
372
ShapeResult(scoped_refptr<const SimpleFontData> font_data,unsigned start_index,unsigned num_characters,TextDirection direction)373 ShapeResult::ShapeResult(scoped_refptr<const SimpleFontData> font_data,
374 unsigned start_index,
375 unsigned num_characters,
376 TextDirection direction)
377 : width_(0),
378 primary_font_(font_data),
379 start_index_(start_index),
380 num_characters_(num_characters),
381 num_glyphs_(0),
382 direction_(static_cast<unsigned>(direction)),
383 has_vertical_offsets_(false),
384 is_applied_spacing_(false) {}
385
ShapeResult(const Font * font,unsigned start_index,unsigned num_characters,TextDirection direction)386 ShapeResult::ShapeResult(const Font* font,
387 unsigned start_index,
388 unsigned num_characters,
389 TextDirection direction)
390 : ShapeResult(font->PrimaryFont(), start_index, num_characters, direction) {
391 }
392
ShapeResult(const ShapeResult & other)393 ShapeResult::ShapeResult(const ShapeResult& other)
394 : width_(other.width_),
395 primary_font_(other.primary_font_),
396 start_index_(other.start_index_),
397 num_characters_(other.num_characters_),
398 num_glyphs_(other.num_glyphs_),
399 direction_(other.direction_),
400 has_vertical_offsets_(other.has_vertical_offsets_),
401 is_applied_spacing_(other.is_applied_spacing_) {
402 runs_.ReserveCapacity(other.runs_.size());
403 for (const auto& run : other.runs_)
404 runs_.push_back(run->Create(*run.get()));
405 }
406
407 ShapeResult::~ShapeResult() = default;
408
ByteSize() const409 size_t ShapeResult::ByteSize() const {
410 size_t self_byte_size = sizeof(*this);
411 for (unsigned i = 0; i < runs_.size(); ++i) {
412 self_byte_size += runs_[i]->ByteSize();
413 }
414 return self_byte_size;
415 }
416
NextSafeToBreakOffset(unsigned index) const417 unsigned ShapeResult::NextSafeToBreakOffset(unsigned index) const {
418 for (auto* it = runs_.begin(); it != runs_.end(); ++it) {
419 const auto& run = *it;
420 if (!run)
421 continue;
422
423 unsigned run_start = run->start_index_;
424 if (index >= run_start) {
425 unsigned offset = index - run_start;
426 if (offset <= run->num_characters_) {
427 return run->NextSafeToBreakOffset(offset) + run_start;
428 }
429 if (Rtl()) {
430 if (it == runs_.begin())
431 return run_start + run->num_characters_;
432 const auto& previous_run = *--it;
433 return previous_run->start_index_;
434 }
435 } else if (!Rtl()) {
436 return run_start;
437 }
438 }
439
440 return EndIndex();
441 }
442
PreviousSafeToBreakOffset(unsigned index) const443 unsigned ShapeResult::PreviousSafeToBreakOffset(unsigned index) const {
444 for (auto it = runs_.rbegin(); it != runs_.rend(); ++it) {
445 const auto& run = *it;
446 if (!run)
447 continue;
448
449 unsigned run_start = run->start_index_;
450 if (index >= run_start) {
451 unsigned offset = index - run_start;
452 if (offset <= run->num_characters_) {
453 return run->PreviousSafeToBreakOffset(offset) + run_start;
454 }
455 if (!Rtl()) {
456 return run_start + run->num_characters_;
457 }
458 } else if (Rtl()) {
459 if (it == runs_.rbegin())
460 return run->start_index_;
461 const auto& previous_run = *--it;
462 return previous_run->start_index_ + previous_run->num_characters_;
463 }
464 }
465
466 return StartIndex();
467 }
468
469 // If the position is outside of the result, returns the start or the end offset
470 // depends on the position.
OffsetForPosition(float target_x,BreakGlyphsOption break_glyphs_option,GlyphIndexResult * result) const471 void ShapeResult::OffsetForPosition(float target_x,
472 BreakGlyphsOption break_glyphs_option,
473 GlyphIndexResult* result) const {
474 if (target_x <= 0) {
475 if (Rtl()) {
476 result->left_character_index = result->right_character_index =
477 NumCharacters();
478 }
479 return;
480 }
481
482 unsigned characters_so_far = Rtl() ? NumCharacters() : 0;
483 float current_x = 0;
484
485 for (const scoped_refptr<RunInfo>& run_ptr : runs_) {
486 const RunInfo* run = run_ptr.get();
487 if (!run)
488 continue;
489 if (Rtl())
490 characters_so_far -= run->num_characters_;
491 float next_x = current_x + run->width_;
492 float offset_for_run = target_x - current_x;
493 if (offset_for_run >= 0 && offset_for_run < run->width_) {
494 // The x value in question is within this script run.
495 run->CharacterIndexForXPosition(offset_for_run, break_glyphs_option,
496 result);
497 result->characters_on_left_runs = characters_so_far;
498 if (Rtl()) {
499 result->left_character_index =
500 characters_so_far + result->left_character_index;
501 result->right_character_index =
502 characters_so_far + result->right_character_index;
503 DCHECK_LE(result->left_character_index, NumCharacters() + 1);
504 DCHECK_LE(result->right_character_index, NumCharacters());
505 } else {
506 result->left_character_index += characters_so_far;
507 result->right_character_index += characters_so_far;
508 DCHECK_LE(result->left_character_index, NumCharacters());
509 DCHECK_LE(result->right_character_index, NumCharacters() + 1);
510 }
511 result->origin_x += current_x;
512 return;
513 }
514 if (!Rtl())
515 characters_so_far += run->num_characters_;
516 current_x = next_x;
517 }
518
519 if (Rtl()) {
520 result->left_character_index = 0;
521 result->right_character_index = 0;
522 } else {
523 result->left_character_index += characters_so_far;
524 result->right_character_index += characters_so_far;
525 }
526
527 result->characters_on_left_runs = characters_so_far;
528
529 DCHECK_LE(result->left_character_index, NumCharacters());
530 DCHECK_LE(result->right_character_index, NumCharacters() + 1);
531 }
532
OffsetForPosition(float x,BreakGlyphsOption break_glyphs_option) const533 unsigned ShapeResult::OffsetForPosition(
534 float x,
535 BreakGlyphsOption break_glyphs_option) const {
536 GlyphIndexResult result;
537 OffsetForPosition(x, break_glyphs_option, &result);
538
539 // For LTR, the offset is always the left one.
540 if (!Rtl())
541 return result.left_character_index;
542
543 // For RTL the offset is the right one, except that the interval is open
544 // on other side. So in case we are exactly at the boundary, we return the
545 // left index.
546 if (x == result.origin_x)
547 return result.left_character_index;
548 return result.right_character_index;
549 }
550
CaretOffsetForHitTest(float x,const StringView & text,BreakGlyphsOption break_glyphs_option) const551 unsigned ShapeResult::CaretOffsetForHitTest(
552 float x,
553 const StringView& text,
554 BreakGlyphsOption break_glyphs_option) const {
555 if (break_glyphs_option == BreakGlyphs)
556 EnsureGraphemes(text);
557
558 GlyphIndexResult result;
559 OffsetForPosition(x, break_glyphs_option, &result);
560
561 if (x - result.origin_x <= result.advance / 2)
562 return result.left_character_index;
563 return result.right_character_index;
564 }
565
OffsetToFit(float x,TextDirection line_direction) const566 unsigned ShapeResult::OffsetToFit(float x, TextDirection line_direction) const {
567 GlyphIndexResult result;
568 OffsetForPosition(x, DontBreakGlyphs, &result);
569
570 if (IsLtr(line_direction))
571 return result.left_character_index;
572
573 if (x == result.origin_x)
574 return result.left_character_index;
575 return result.right_character_index;
576 }
577
PositionForOffset(unsigned absolute_offset,AdjustMidCluster adjust_mid_cluster) const578 float ShapeResult::PositionForOffset(
579 unsigned absolute_offset,
580 AdjustMidCluster adjust_mid_cluster) const {
581 float x = 0;
582 float offset_x = 0;
583
584 // The absolute_offset argument represents the offset for the entire
585 // ShapeResult while offset is continuously updated to be relative to the
586 // current run.
587 unsigned offset = absolute_offset;
588
589 if (Rtl()) {
590 // Convert logical offsets to visual offsets, because results are in
591 // logical order while runs are in visual order.
592 x = width_;
593 if (offset < NumCharacters())
594 offset = NumCharacters() - offset - 1;
595 x -= Width();
596 }
597
598 for (unsigned i = 0; i < runs_.size(); i++) {
599 if (!runs_[i])
600 continue;
601 DCHECK_EQ(Rtl(), runs_[i]->Rtl());
602 unsigned num_characters = runs_[i]->num_characters_;
603
604 if (!offset_x && offset < num_characters) {
605 offset_x =
606 runs_[i]->XPositionForVisualOffset(offset, adjust_mid_cluster) + x;
607 break;
608 }
609
610 offset -= num_characters;
611 x += runs_[i]->width_;
612 }
613
614 // The position in question might be just after the text.
615 if (!offset_x && absolute_offset == NumCharacters())
616 return Rtl() ? 0 : width_;
617
618 return offset_x;
619 }
620
CaretPositionForOffset(unsigned offset,const StringView & text,AdjustMidCluster adjust_mid_cluster) const621 float ShapeResult::CaretPositionForOffset(
622 unsigned offset,
623 const StringView& text,
624 AdjustMidCluster adjust_mid_cluster) const {
625 EnsureGraphemes(text);
626 return PositionForOffset(offset, adjust_mid_cluster);
627 }
628
FallbackFonts(HashSet<const SimpleFontData * > * fallback) const629 void ShapeResult::FallbackFonts(
630 HashSet<const SimpleFontData*>* fallback) const {
631 DCHECK(fallback);
632 DCHECK(primary_font_);
633 for (unsigned i = 0; i < runs_.size(); ++i) {
634 if (runs_[i] && runs_[i]->font_data_ &&
635 runs_[i]->font_data_ != primary_font_) {
636 fallback->insert(runs_[i]->font_data_.get());
637 }
638 }
639 }
640
GetRunFontData(Vector<RunFontData> * font_data) const641 void ShapeResult::GetRunFontData(Vector<RunFontData>* font_data) const {
642 for (const auto& run : runs_) {
643 font_data->push_back(
644 RunFontData({run->font_data_.get(), run->glyph_data_.size()}));
645 }
646 }
647
648 template <bool has_non_zero_glyph_offsets>
ForEachGlyphImpl(float initial_advance,GlyphCallback glyph_callback,void * context,const RunInfo & run) const649 float ShapeResult::ForEachGlyphImpl(float initial_advance,
650 GlyphCallback glyph_callback,
651 void* context,
652 const RunInfo& run) const {
653 auto glyph_offsets = run.glyph_data_.GetOffsets<has_non_zero_glyph_offsets>();
654 auto total_advance = initial_advance;
655 bool is_horizontal = HB_DIRECTION_IS_HORIZONTAL(run.direction_);
656 for (const auto& glyph_data : run.glyph_data_) {
657 glyph_callback(context, run.start_index_ + glyph_data.character_index,
658 glyph_data.glyph, *glyph_offsets, total_advance,
659 is_horizontal, run.canvas_rotation_, run.font_data_.get());
660 total_advance += glyph_data.advance;
661 ++glyph_offsets;
662 }
663 return total_advance;
664 }
665
ForEachGlyph(float initial_advance,GlyphCallback glyph_callback,void * context) const666 float ShapeResult::ForEachGlyph(float initial_advance,
667 GlyphCallback glyph_callback,
668 void* context) const {
669 auto total_advance = initial_advance;
670 for (const auto& run : runs_) {
671 if (run->glyph_data_.HasNonZeroOffsets()) {
672 total_advance =
673 ForEachGlyphImpl<true>(total_advance, glyph_callback, context, *run);
674 } else {
675 total_advance =
676 ForEachGlyphImpl<false>(total_advance, glyph_callback, context, *run);
677 }
678 }
679 return total_advance;
680 }
681
682 template <bool has_non_zero_glyph_offsets>
ForEachGlyphImpl(float initial_advance,unsigned from,unsigned to,unsigned index_offset,GlyphCallback glyph_callback,void * context,const RunInfo & run) const683 float ShapeResult::ForEachGlyphImpl(float initial_advance,
684 unsigned from,
685 unsigned to,
686 unsigned index_offset,
687 GlyphCallback glyph_callback,
688 void* context,
689 const RunInfo& run) const {
690 auto glyph_offsets = run.glyph_data_.GetOffsets<has_non_zero_glyph_offsets>();
691 auto total_advance = initial_advance;
692 unsigned run_start = run.start_index_ + index_offset;
693 bool is_horizontal = HB_DIRECTION_IS_HORIZONTAL(run.direction_);
694 const SimpleFontData* font_data = run.font_data_.get();
695
696 if (!run.Rtl()) { // Left-to-right
697 for (const auto& glyph_data : run.glyph_data_) {
698 const unsigned character_index = run_start + glyph_data.character_index;
699 if (character_index >= to)
700 break;
701 if (character_index >= from) {
702 glyph_callback(context, character_index, glyph_data.glyph,
703 *glyph_offsets, total_advance, is_horizontal,
704 run.canvas_rotation_, font_data);
705 }
706 total_advance += glyph_data.advance;
707 ++glyph_offsets;
708 }
709 } else { // Right-to-left
710 for (const auto& glyph_data : run.glyph_data_) {
711 const unsigned character_index = run_start + glyph_data.character_index;
712 if (character_index < from)
713 break;
714 if (character_index < to) {
715 glyph_callback(context, character_index, glyph_data.glyph,
716 *glyph_offsets, total_advance, is_horizontal,
717 run.canvas_rotation_, font_data);
718 }
719 total_advance += glyph_data.advance;
720 ++glyph_offsets;
721 }
722 }
723 return total_advance;
724 }
725
ForEachGlyph(float initial_advance,unsigned from,unsigned to,unsigned index_offset,GlyphCallback glyph_callback,void * context) const726 float ShapeResult::ForEachGlyph(float initial_advance,
727 unsigned from,
728 unsigned to,
729 unsigned index_offset,
730 GlyphCallback glyph_callback,
731 void* context) const {
732 auto total_advance = initial_advance;
733 for (const auto& run : runs_) {
734 if (run->glyph_data_.HasNonZeroOffsets()) {
735 total_advance = ForEachGlyphImpl<true>(
736 total_advance, from, to, index_offset, glyph_callback, context, *run);
737 } else {
738 total_advance = ForEachGlyphImpl<false>(
739 total_advance, from, to, index_offset, glyph_callback, context, *run);
740 }
741 }
742 return total_advance;
743 }
744
CountGraphemesInCluster(base::span<const UChar> str,uint16_t start_index,uint16_t end_index)745 unsigned ShapeResult::CountGraphemesInCluster(base::span<const UChar> str,
746 uint16_t start_index,
747 uint16_t end_index) {
748 if (start_index > end_index)
749 std::swap(start_index, end_index);
750 uint16_t length = end_index - start_index;
751 TextBreakIterator* cursor_pos_iterator =
752 CursorMovementIterator(str.subspan(start_index, length));
753 if (!cursor_pos_iterator)
754 return 0;
755
756 int cursor_pos = cursor_pos_iterator->current();
757 int num_graphemes = -1;
758 while (0 <= cursor_pos) {
759 cursor_pos = cursor_pos_iterator->next();
760 num_graphemes++;
761 }
762 return std::max(0, num_graphemes);
763 }
764
ForEachGraphemeClusters(const StringView & text,float initial_advance,unsigned from,unsigned to,unsigned index_offset,GraphemeClusterCallback callback,void * context) const765 float ShapeResult::ForEachGraphemeClusters(const StringView& text,
766 float initial_advance,
767 unsigned from,
768 unsigned to,
769 unsigned index_offset,
770 GraphemeClusterCallback callback,
771 void* context) const {
772 unsigned run_offset = index_offset;
773 float advance_so_far = initial_advance;
774 for (const auto& run : runs_) {
775 unsigned graphemes_in_cluster = 1;
776 float cluster_advance = 0;
777
778 // FIXME: should this be run->direction_?
779 bool rtl = Direction() == TextDirection::kRtl;
780
781 // A "cluster" in this context means a cluster as it is used by HarfBuzz:
782 // The minimal group of characters and corresponding glyphs, that cannot be
783 // broken down further from a text shaping point of view. A cluster can
784 // contain multiple glyphs and grapheme clusters, with mutually overlapping
785 // boundaries.
786 uint16_t cluster_start = static_cast<uint16_t>(
787 rtl ? run->start_index_ + run->num_characters_ + run_offset
788 : run->GlyphToCharacterIndex(0) + run_offset);
789
790 const unsigned num_glyphs = run->glyph_data_.size();
791 for (unsigned i = 0; i < num_glyphs; ++i) {
792 const HarfBuzzRunGlyphData& glyph_data = run->glyph_data_[i];
793 uint16_t current_character_index =
794 run->start_index_ + glyph_data.character_index + run_offset;
795 bool is_run_end = (i + 1 == num_glyphs);
796 bool is_cluster_end =
797 is_run_end || (run->GlyphToCharacterIndex(i + 1) + run_offset !=
798 current_character_index);
799
800 if ((rtl && current_character_index >= to) ||
801 (!rtl && current_character_index < from)) {
802 advance_so_far += glyph_data.advance;
803 rtl ? --cluster_start : ++cluster_start;
804 continue;
805 }
806
807 cluster_advance += glyph_data.advance;
808
809 if (text.Is8Bit()) {
810 callback(context, current_character_index, advance_so_far, 1,
811 glyph_data.advance, run->canvas_rotation_);
812
813 advance_so_far += glyph_data.advance;
814 } else if (is_cluster_end) {
815 uint16_t cluster_end;
816 if (rtl) {
817 cluster_end = current_character_index;
818 } else {
819 cluster_end = static_cast<uint16_t>(
820 is_run_end ? run->start_index_ + run->num_characters_ + run_offset
821 : run->GlyphToCharacterIndex(i + 1) + run_offset);
822 }
823 graphemes_in_cluster =
824 CountGraphemesInCluster(text.Span16(), cluster_start, cluster_end);
825 if (!graphemes_in_cluster || !cluster_advance)
826 continue;
827
828 callback(context, current_character_index, advance_so_far,
829 graphemes_in_cluster, cluster_advance, run->canvas_rotation_);
830 advance_so_far += cluster_advance;
831
832 cluster_start = cluster_end;
833 cluster_advance = 0;
834 }
835 }
836 }
837 return advance_so_far;
838 }
839
840 // TODO(kojii): VC2015 fails to explicit instantiation of a member function.
841 // Typed functions + this private function are to instantiate instances.
842 template <typename TextContainerType>
ApplySpacingImpl(ShapeResultSpacing<TextContainerType> & spacing,int text_start_offset)843 void ShapeResult::ApplySpacingImpl(
844 ShapeResultSpacing<TextContainerType>& spacing,
845 int text_start_offset) {
846 float offset = 0;
847 float total_space = 0;
848 float space = 0;
849 for (auto& run : runs_) {
850 if (!run)
851 continue;
852 unsigned run_start_index = run->start_index_ + text_start_offset;
853 float total_space_for_run = 0;
854 for (wtf_size_t i = 0; i < run->glyph_data_.size(); i++) {
855 HarfBuzzRunGlyphData& glyph_data = run->glyph_data_[i];
856
857 // Skip if it's not a grapheme cluster boundary.
858 if (i + 1 < run->glyph_data_.size() &&
859 glyph_data.character_index ==
860 run->glyph_data_[i + 1].character_index) {
861 continue;
862 }
863
864 typename ShapeResultSpacing<TextContainerType>::ComputeSpacingParameters
865 parameters{.index = run_start_index + glyph_data.character_index,
866 .advance_override = run->font_data_->GetAdvanceOverride(),
867 .original_advance = glyph_data.advance,
868 .advance_proportional_override =
869 run->font_data_->GetAdvanceProportionalOverride()};
870 space = spacing.ComputeSpacing(parameters, offset);
871 glyph_data.advance += space;
872 total_space_for_run += space;
873
874 // |offset| is non-zero only when justifying CJK characters that follow
875 // non-CJK characters.
876 if (UNLIKELY(offset)) {
877 if (run->IsHorizontal()) {
878 run->glyph_data_.AddOffsetWidthAt(i, offset);
879 } else {
880 run->glyph_data_.AddOffsetHeightAt(i, offset);
881 has_vertical_offsets_ = true;
882 }
883 offset = 0;
884 }
885 }
886 run->width_ += total_space_for_run;
887 total_space += total_space_for_run;
888 }
889 width_ += total_space;
890
891 // The spacing on the right of the last glyph does not affect the glyph
892 // bounding box. Thus, the glyph bounding box becomes smaller than the advance
893 // if the letter spacing is positve, or larger if negative.
894 if (space) {
895 total_space -= space;
896
897 // TODO(kojii): crbug.com/768284: There are cases where
898 // InlineTextBox::LogicalWidth() is round down of ShapeResult::Width() in
899 // LayoutUnit. Ceiling the width did not help. Add 1px to avoid cut-off.
900 if (space < 0)
901 total_space += 1;
902 }
903 }
904
ApplySpacing(ShapeResultSpacing<String> & spacing,int text_start_offset)905 void ShapeResult::ApplySpacing(ShapeResultSpacing<String>& spacing,
906 int text_start_offset) {
907 // For simplicity, we apply spacing once only. If you want to do multiple
908 // time, please get rid of below |DCHECK()|.
909 DCHECK(!is_applied_spacing_) << this;
910 is_applied_spacing_ = true;
911 ApplySpacingImpl(spacing, text_start_offset);
912 }
913
ApplySpacingToCopy(ShapeResultSpacing<TextRun> & spacing,const TextRun & run) const914 scoped_refptr<ShapeResult> ShapeResult::ApplySpacingToCopy(
915 ShapeResultSpacing<TextRun>& spacing,
916 const TextRun& run) const {
917 unsigned index_of_sub_run = spacing.Text().IndexOfSubRun(run);
918 DCHECK_NE(std::numeric_limits<unsigned>::max(), index_of_sub_run);
919 scoped_refptr<ShapeResult> result = ShapeResult::Create(*this);
920 if (index_of_sub_run != std::numeric_limits<unsigned>::max())
921 result->ApplySpacingImpl(spacing, index_of_sub_run);
922 return result;
923 }
924
925 namespace {
926
HarfBuzzPositionToFloat(hb_position_t value)927 float HarfBuzzPositionToFloat(hb_position_t value) {
928 return static_cast<float>(value) / (1 << 16);
929 }
930
931 // Checks whether it's safe to break without reshaping before the given glyph.
IsSafeToBreakBefore(const hb_glyph_info_t * glyph_infos,unsigned i,unsigned num_glyph,TextDirection direction)932 bool IsSafeToBreakBefore(const hb_glyph_info_t* glyph_infos,
933 unsigned i,
934 unsigned num_glyph,
935 TextDirection direction) {
936 if (direction == TextDirection::kLtr) {
937 // Before the first glyph is safe to break.
938 if (!i)
939 return true;
940
941 // Not at a cluster boundary.
942 if (glyph_infos[i].cluster == glyph_infos[i - 1].cluster)
943 return false;
944 } else {
945 DCHECK_EQ(direction, TextDirection::kRtl);
946 // Before the first glyph is safe to break.
947 if (i == num_glyph - 1)
948 return true;
949
950 // Not at a cluster boundary.
951 if (glyph_infos[i].cluster == glyph_infos[i + 1].cluster)
952 return false;
953 }
954
955 // The HB_GLYPH_FLAG_UNSAFE_TO_BREAK flag is set for all glyphs in a
956 // given cluster so we only need to check the last one.
957 hb_glyph_flags_t flags = hb_glyph_info_get_glyph_flags(glyph_infos + i);
958 return (flags & HB_GLYPH_FLAG_UNSAFE_TO_BREAK) == 0;
959 }
960
961 } // anonymous namespace
962
963 // This function computes the number of glyphs and characters that can fit into
964 // this RunInfo.
965 //
966 // HarfBuzzRunGlyphData has a limit kMaxCharacterIndex for the character index
967 // in order to packsave memory. Also, RunInfo has kMaxGlyphs to make the number
968 // of glyphs predictable and to minimize the buffer reallocations.
LimitNumGlyphs(unsigned start_glyph,unsigned * num_glyphs_in_out,const bool is_ltr,const hb_glyph_info_t * glyph_infos)969 unsigned ShapeResult::RunInfo::LimitNumGlyphs(
970 unsigned start_glyph,
971 unsigned* num_glyphs_in_out,
972 const bool is_ltr,
973 const hb_glyph_info_t* glyph_infos) {
974 unsigned num_glyphs = *num_glyphs_in_out;
975 CHECK_GT(num_glyphs, 0u);
976
977 // If there were larger character indexes than kMaxCharacterIndex, reduce
978 // num_glyphs so that all character indexes can fit to kMaxCharacterIndex.
979 // Because code points and glyphs are not always 1:1, we need to check the
980 // first and the last cluster.
981 const hb_glyph_info_t* left_glyph_info = &glyph_infos[start_glyph];
982 const hb_glyph_info_t* right_glyph_info = &left_glyph_info[num_glyphs - 1];
983 unsigned start_cluster;
984 if (is_ltr) {
985 start_cluster = left_glyph_info->cluster;
986 unsigned last_cluster = right_glyph_info->cluster;
987 unsigned max_cluster =
988 start_cluster + HarfBuzzRunGlyphData::kMaxCharacterIndex;
989 if (UNLIKELY(last_cluster > max_cluster)) {
990 // Limit at |max_cluster| in LTR. If |max_cluster| is 100:
991 // 0 1 2 ... 98 99 99 101 101 103 ...
992 // ^ limit here.
993 // Find |glyph_info| where |cluster| <= |max_cluster|.
994 const hb_glyph_info_t* limit_glyph_info = std::upper_bound(
995 left_glyph_info, right_glyph_info + 1, max_cluster,
996 [](unsigned cluster, const hb_glyph_info_t& glyph_info) {
997 return cluster < glyph_info.cluster;
998 });
999 --limit_glyph_info;
1000 CHECK_GT(limit_glyph_info, left_glyph_info);
1001 CHECK_LT(limit_glyph_info, right_glyph_info);
1002 DCHECK_LE(limit_glyph_info->cluster, max_cluster);
1003 // Adjust |right_glyph_info| and recompute dependent variables.
1004 right_glyph_info = limit_glyph_info;
1005 num_glyphs = right_glyph_info - left_glyph_info + 1;
1006 num_characters_ = right_glyph_info[1].cluster - start_cluster;
1007 }
1008 } else {
1009 start_cluster = right_glyph_info->cluster;
1010 unsigned last_cluster = left_glyph_info->cluster;
1011 unsigned max_cluster =
1012 start_cluster + HarfBuzzRunGlyphData::kMaxCharacterIndex;
1013 if (UNLIKELY(last_cluster > max_cluster)) {
1014 // Limit the right edge, which is in the reverse order in RTL.
1015 // If |min_cluster| is 3:
1016 // 103 102 ... 4 4 2 2 ...
1017 // ^ limit here.
1018 // Find |glyph_info| where |cluster| >= |min_cluster|.
1019 unsigned min_cluster =
1020 last_cluster - HarfBuzzRunGlyphData::kMaxCharacterIndex;
1021 DCHECK_LT(start_cluster, min_cluster);
1022 const hb_glyph_info_t* limit_glyph_info = std::upper_bound(
1023 left_glyph_info, right_glyph_info + 1, min_cluster,
1024 [](unsigned cluster, const hb_glyph_info_t& glyph_info) {
1025 return cluster > glyph_info.cluster;
1026 });
1027 --limit_glyph_info;
1028 CHECK_GT(limit_glyph_info, left_glyph_info);
1029 CHECK_LT(limit_glyph_info, right_glyph_info);
1030 DCHECK_GE(limit_glyph_info->cluster, min_cluster);
1031 // Adjust |right_glyph_info| and recompute dependent variables.
1032 right_glyph_info = limit_glyph_info;
1033 start_cluster = right_glyph_info->cluster;
1034 num_glyphs = right_glyph_info - left_glyph_info + 1;
1035 num_characters_ = last_cluster - right_glyph_info[1].cluster;
1036 }
1037 }
1038
1039 // num_glyphs maybe still larger than kMaxGlyphs after it was reduced to fit
1040 // to kMaxCharacterIndex. Reduce to kMaxGlyphs if so.
1041 if (UNLIKELY(num_glyphs > HarfBuzzRunGlyphData::kMaxGlyphs)) {
1042 num_glyphs = HarfBuzzRunGlyphData::kMaxGlyphs;
1043
1044 // If kMaxGlyphs is not a cluster boundary, reduce further until the last
1045 // boundary.
1046 const unsigned end_cluster = glyph_infos[start_glyph + num_glyphs].cluster;
1047 for (;; num_glyphs--) {
1048 if (!num_glyphs) {
1049 // Extreme edge case when kMaxGlyphs is one grapheme cluster. We don't
1050 // have much choices, just cut at kMaxGlyphs.
1051 num_glyphs = HarfBuzzRunGlyphData::kMaxGlyphs;
1052 break;
1053 }
1054 if (glyph_infos[start_glyph + num_glyphs - 1].cluster != end_cluster)
1055 break;
1056 }
1057 num_characters_ = is_ltr ? end_cluster - start_cluster
1058 : glyph_infos[start_glyph].cluster - end_cluster;
1059 }
1060
1061 if (num_glyphs == *num_glyphs_in_out)
1062 return start_cluster;
1063 glyph_data_.Shrink(num_glyphs);
1064 *num_glyphs_in_out = num_glyphs;
1065 return start_cluster;
1066 }
1067
1068 // Computes glyph positions, sets advance and offset of each glyph to RunInfo.
1069 template <bool is_horizontal_run>
ComputeGlyphPositions(ShapeResult::RunInfo * run,unsigned start_glyph,unsigned num_glyphs,hb_buffer_t * harfbuzz_buffer)1070 void ShapeResult::ComputeGlyphPositions(ShapeResult::RunInfo* run,
1071 unsigned start_glyph,
1072 unsigned num_glyphs,
1073 hb_buffer_t* harfbuzz_buffer) {
1074 DCHECK_EQ(is_horizontal_run, run->IsHorizontal());
1075 const hb_glyph_info_t* glyph_infos =
1076 hb_buffer_get_glyph_infos(harfbuzz_buffer, nullptr);
1077 const hb_glyph_position_t* glyph_positions =
1078 hb_buffer_get_glyph_positions(harfbuzz_buffer, nullptr);
1079
1080 const bool is_ltr =
1081 HB_DIRECTION_IS_FORWARD(hb_buffer_get_direction(harfbuzz_buffer));
1082 unsigned start_cluster =
1083 run->LimitNumGlyphs(start_glyph, &num_glyphs, is_ltr, glyph_infos);
1084 DCHECK_LE(num_glyphs, HarfBuzzRunGlyphData::kMaxGlyphs);
1085
1086 // Compute glyph_origin in physical, since offsets of glyphs are in physical.
1087 // It's the caller's responsibility to convert to logical.
1088 float total_advance = 0.0f;
1089 bool has_vertical_offsets = !is_horizontal_run;
1090
1091 // HarfBuzz returns result in visual order, no need to flip for RTL.
1092 for (unsigned i = 0; i < num_glyphs; ++i) {
1093 const hb_glyph_info_t glyph = glyph_infos[start_glyph + i];
1094 const hb_glyph_position_t& pos = glyph_positions[start_glyph + i];
1095
1096 // Offset is primarily used when painting glyphs. Keep it in physical.
1097 GlyphOffset offset(HarfBuzzPositionToFloat(pos.x_offset),
1098 -HarfBuzzPositionToFloat(pos.y_offset));
1099
1100 // One out of x_advance and y_advance is zero, depending on
1101 // whether the buffer direction is horizontal or vertical.
1102 // Convert to float and negate to avoid integer-overflow for ULONG_MAX.
1103 float advance = is_horizontal_run ? HarfBuzzPositionToFloat(pos.x_advance)
1104 : -HarfBuzzPositionToFloat(pos.y_advance);
1105
1106 uint16_t character_index = glyph.cluster - start_cluster;
1107 DCHECK_LE(character_index, HarfBuzzRunGlyphData::kMaxCharacterIndex);
1108 run->glyph_data_[i] = {glyph.codepoint, character_index,
1109 IsSafeToBreakBefore(glyph_infos + start_glyph, i,
1110 num_glyphs, Direction()),
1111 advance};
1112 run->glyph_data_.SetOffsetAt(i, offset);
1113
1114 total_advance += advance;
1115 has_vertical_offsets |= (offset.Height() != 0);
1116 }
1117
1118 run->width_ = std::max(0.0f, total_advance);
1119 has_vertical_offsets_ |= has_vertical_offsets;
1120 }
1121
InsertRun(scoped_refptr<ShapeResult::RunInfo> run_to_insert,unsigned start_glyph,unsigned num_glyphs,hb_buffer_t * harfbuzz_buffer)1122 void ShapeResult::InsertRun(scoped_refptr<ShapeResult::RunInfo> run_to_insert,
1123 unsigned start_glyph,
1124 unsigned num_glyphs,
1125 hb_buffer_t* harfbuzz_buffer) {
1126 DCHECK_GT(num_glyphs, 0u);
1127 scoped_refptr<ShapeResult::RunInfo> run(std::move(run_to_insert));
1128
1129 if (run->IsHorizontal()) {
1130 // Inserting a horizontal run into a horizontal or vertical result.
1131 ComputeGlyphPositions<true>(run.get(), start_glyph, num_glyphs,
1132 harfbuzz_buffer);
1133 } else {
1134 // Inserting a vertical run to a vertical result.
1135 ComputeGlyphPositions<false>(run.get(), start_glyph, num_glyphs,
1136 harfbuzz_buffer);
1137 }
1138 width_ += run->width_;
1139 num_glyphs_ += run->NumGlyphs();
1140 DCHECK_GE(num_glyphs_, run->NumGlyphs());
1141
1142 InsertRun(std::move(run));
1143 }
1144
InsertRun(scoped_refptr<ShapeResult::RunInfo> run)1145 void ShapeResult::InsertRun(scoped_refptr<ShapeResult::RunInfo> run) {
1146 // The runs are stored in result->m_runs in visual order. For LTR, we place
1147 // the run to be inserted before the next run with a bigger character start
1148 // index.
1149 const auto ltr_comparer = [](scoped_refptr<RunInfo>& run,
1150 unsigned start_index) {
1151 return run->start_index_ < start_index;
1152 };
1153
1154 // For RTL, we place the run before the next run with a lower character
1155 // index. Otherwise, for both directions, at the end.
1156 const auto rtl_comparer = [](scoped_refptr<RunInfo>& run,
1157 unsigned start_index) {
1158 return run->start_index_ > start_index;
1159 };
1160
1161 Vector<scoped_refptr<RunInfo>>::iterator iterator = std::lower_bound(
1162 runs_.begin(), runs_.end(), run->start_index_,
1163 HB_DIRECTION_IS_FORWARD(run->direction_) ? ltr_comparer : rtl_comparer);
1164 if (iterator != runs_.end())
1165 runs_.insert(iterator - runs_.begin(), std::move(run));
1166
1167 // If we didn't find an existing slot to place it, append.
1168 if (run)
1169 runs_.push_back(std::move(run));
1170 }
1171
InsertRunForTesting(unsigned start_index,unsigned num_characters,TextDirection direction,Vector<uint16_t> safe_break_offsets)1172 ShapeResult::RunInfo* ShapeResult::InsertRunForTesting(
1173 unsigned start_index,
1174 unsigned num_characters,
1175 TextDirection direction,
1176 Vector<uint16_t> safe_break_offsets) {
1177 auto run = RunInfo::Create(
1178 nullptr, IsLtr(direction) ? HB_DIRECTION_LTR : HB_DIRECTION_RTL,
1179 CanvasRotationInVertical::kRegular, HB_SCRIPT_COMMON, start_index,
1180 num_characters, num_characters);
1181 for (unsigned i = 0; i < run->glyph_data_.size(); i++) {
1182 run->glyph_data_[i] = {0, i, false, 0};
1183 }
1184 for (uint16_t offset : safe_break_offsets)
1185 run->glyph_data_[offset].safe_to_break_before = true;
1186 // RTL runs have glyphs in the descending order of character_index.
1187 if (Rtl())
1188 run->glyph_data_.Reverse();
1189 num_glyphs_ += run->NumGlyphs();
1190 RunInfo* run_ptr = run.get();
1191 InsertRun(std::move(run));
1192 return run_ptr;
1193 }
1194
1195 // Moves runs at (run_size_before, end) to the front of |runs_|.
1196 //
1197 // Runs in RTL result are in visual order, and that new runs should be
1198 // prepended. This function adjusts the run order after runs were appended.
ReorderRtlRuns(unsigned run_size_before)1199 void ShapeResult::ReorderRtlRuns(unsigned run_size_before) {
1200 DCHECK(Rtl());
1201 DCHECK_GT(runs_.size(), run_size_before);
1202 if (runs_.size() == run_size_before + 1) {
1203 if (!run_size_before)
1204 return;
1205 scoped_refptr<RunInfo> new_run(std::move(runs_.back()));
1206 runs_.Shrink(runs_.size() - 1);
1207 runs_.push_front(std::move(new_run));
1208 return;
1209 }
1210
1211 // |push_front| is O(n) that we should not call it multiple times.
1212 // Create a new list in the correct order and swap it.
1213 Vector<scoped_refptr<RunInfo>> new_runs;
1214 new_runs.ReserveInitialCapacity(runs_.size());
1215 for (unsigned i = run_size_before; i < runs_.size(); i++)
1216 new_runs.push_back(std::move(runs_[i]));
1217
1218 // Then append existing runs.
1219 for (unsigned i = 0; i < run_size_before; i++)
1220 new_runs.push_back(std::move(runs_[i]));
1221 runs_.swap(new_runs);
1222 }
1223
CopyRange(unsigned start_offset,unsigned end_offset,ShapeResult * target) const1224 void ShapeResult::CopyRange(unsigned start_offset,
1225 unsigned end_offset,
1226 ShapeResult* target) const {
1227 unsigned run_index = 0;
1228 CopyRangeInternal(run_index, start_offset, end_offset, target);
1229 }
1230
CopyRanges(const ShapeRange * ranges,unsigned num_ranges) const1231 void ShapeResult::CopyRanges(const ShapeRange* ranges,
1232 unsigned num_ranges) const {
1233 DCHECK_GT(num_ranges, 0u);
1234
1235 // Ranges are in logical order so for RTL the ranges are proccessed back to
1236 // front to ensure that they're in a sequential visual order with regards to
1237 // the runs.
1238 if (Rtl()) {
1239 unsigned run_index = 0;
1240 unsigned last_range = num_ranges - 1;
1241 for (unsigned i = 0; i < num_ranges; i++) {
1242 const ShapeRange& range = ranges[last_range - i];
1243 #if DCHECK_IS_ON()
1244 DCHECK_GE(range.end, range.start);
1245 if (i != last_range)
1246 DCHECK_GE(range.start, ranges[last_range - (i + 1)].end);
1247 #endif
1248 run_index =
1249 CopyRangeInternal(run_index, range.start, range.end, range.target);
1250 }
1251 return;
1252 }
1253
1254 unsigned run_index = 0;
1255 for (unsigned i = 0; i < num_ranges; i++) {
1256 const ShapeRange& range = ranges[i];
1257 #if DCHECK_IS_ON()
1258 DCHECK_GE(range.end, range.start);
1259 if (i)
1260 DCHECK_GE(range.start, ranges[i - 1].end);
1261 #endif
1262 run_index =
1263 CopyRangeInternal(run_index, range.start, range.end, range.target);
1264 }
1265 }
1266
CopyRangeInternal(unsigned run_index,unsigned start_offset,unsigned end_offset,ShapeResult * target) const1267 unsigned ShapeResult::CopyRangeInternal(unsigned run_index,
1268 unsigned start_offset,
1269 unsigned end_offset,
1270 ShapeResult* target) const {
1271 #if DCHECK_IS_ON()
1272 unsigned target_num_characters_before = target->num_characters_;
1273 #endif
1274
1275 target->is_applied_spacing_ |= is_applied_spacing_;
1276
1277 // When |target| is empty, its character indexes are the specified sub range
1278 // of |this|. Otherwise the character indexes are renumbered to be continuous.
1279 //
1280 // Compute the diff of index and the number of characters from the source
1281 // ShapeResult and given offsets, because computing them from runs/parts can
1282 // be inaccurate when all characters in a run/part are missing.
1283 int index_diff;
1284 if (!target->num_characters_) {
1285 index_diff = 0;
1286 target->start_index_ = start_offset;
1287 } else {
1288 index_diff = target->EndIndex() - std::max(start_offset, StartIndex());
1289 }
1290 target->num_characters_ +=
1291 std::min(end_offset, EndIndex()) - std::max(start_offset, StartIndex());
1292
1293 unsigned target_run_size_before = target->runs_.size();
1294 bool should_merge = !target->runs_.IsEmpty();
1295 for (; run_index < runs_.size(); run_index++) {
1296 const auto& run = runs_[run_index];
1297 unsigned run_start = run->start_index_;
1298 unsigned run_end = run_start + run->num_characters_;
1299
1300 if (start_offset < run_end && end_offset > run_start) {
1301 unsigned start = start_offset > run_start ? start_offset - run_start : 0;
1302 unsigned end = std::min(end_offset, run_end) - run_start;
1303 DCHECK(end > start);
1304
1305 auto sub_run = run->CreateSubRun(start, end);
1306 sub_run->start_index_ += index_diff;
1307 target->width_ += sub_run->width_;
1308 target->num_glyphs_ += sub_run->glyph_data_.size();
1309 if (auto merged_run =
1310 should_merge ? target->runs_.back()->MergeIfPossible(*sub_run)
1311 : scoped_refptr<RunInfo>()) {
1312 target->runs_.back() = std::move(merged_run);
1313 } else {
1314 target->runs_.push_back(std::move(sub_run));
1315 }
1316 should_merge = false;
1317
1318 // No need to process runs after the end of the range.
1319 if ((!Rtl() && end_offset <= run_end) ||
1320 (Rtl() && start_offset >= run_start)) {
1321 break;
1322 }
1323 }
1324 }
1325
1326 if (!target->num_glyphs_) {
1327 return run_index;
1328 }
1329
1330 // Runs in RTL result are in visual order, and that new runs should be
1331 // prepended. Reorder appended runs.
1332 DCHECK_EQ(Rtl(), target->Rtl());
1333 if (UNLIKELY(Rtl() && target->runs_.size() != target_run_size_before))
1334 target->ReorderRtlRuns(target_run_size_before);
1335
1336 target->has_vertical_offsets_ |= has_vertical_offsets_;
1337
1338 #if DCHECK_IS_ON()
1339 DCHECK_EQ(
1340 target->num_characters_ - target_num_characters_before,
1341 std::min(end_offset, EndIndex()) - std::max(start_offset, StartIndex()));
1342 target->CheckConsistency();
1343 #endif
1344
1345 return run_index;
1346 }
1347
SubRange(unsigned start_offset,unsigned end_offset) const1348 scoped_refptr<ShapeResult> ShapeResult::SubRange(unsigned start_offset,
1349 unsigned end_offset) const {
1350 scoped_refptr<ShapeResult> sub_range =
1351 Create(primary_font_.get(), 0, 0, Direction());
1352 CopyRange(start_offset, end_offset, sub_range.get());
1353 return sub_range;
1354 }
1355
CopyAdjustedOffset(unsigned start_index) const1356 scoped_refptr<ShapeResult> ShapeResult::CopyAdjustedOffset(
1357 unsigned start_index) const {
1358 scoped_refptr<ShapeResult> result = base::AdoptRef(new ShapeResult(*this));
1359
1360 if (start_index > result->StartIndex()) {
1361 unsigned delta = start_index - result->StartIndex();
1362 for (auto& run : result->runs_)
1363 run->start_index_ += delta;
1364 } else {
1365 unsigned delta = result->StartIndex() - start_index;
1366 for (auto& run : result->runs_) {
1367 DCHECK(run->start_index_ >= delta);
1368 run->start_index_ -= delta;
1369 }
1370 }
1371
1372 result->start_index_ = start_index;
1373 return result;
1374 }
1375
1376 #if DCHECK_IS_ON()
CheckConsistency() const1377 void ShapeResult::CheckConsistency() const {
1378 if (runs_.IsEmpty()) {
1379 DCHECK_EQ(0u, num_characters_);
1380 DCHECK_EQ(0u, num_glyphs_);
1381 return;
1382 }
1383
1384 const unsigned start_index = StartIndex();
1385 unsigned index = start_index;
1386 unsigned num_glyphs = 0;
1387 if (!Rtl()) {
1388 for (const auto& run : runs_) {
1389 // Characters maybe missing, but must be in increasing order.
1390 DCHECK_GE(run->start_index_, index);
1391 index = run->start_index_ + run->num_characters_;
1392 num_glyphs += run->glyph_data_.size();
1393 }
1394 } else {
1395 // RTL on Mac may not have runs for the all characters. crbug.com/774034
1396 index = runs_.back()->start_index_;
1397 for (const auto& run : base::Reversed(runs_)) {
1398 DCHECK_GE(run->start_index_, index);
1399 index = run->start_index_ + run->num_characters_;
1400 num_glyphs += run->glyph_data_.size();
1401 }
1402 }
1403 const unsigned end_index = EndIndex();
1404 DCHECK_LE(index, end_index);
1405 DCHECK_EQ(end_index - start_index, num_characters_);
1406 DCHECK_EQ(num_glyphs, num_glyphs_);
1407 }
1408 #endif
1409
CreateForTabulationCharacters(const Font * font,const TextRun & text_run,float position_offset,unsigned length)1410 scoped_refptr<ShapeResult> ShapeResult::CreateForTabulationCharacters(
1411 const Font* font,
1412 const TextRun& text_run,
1413 float position_offset,
1414 unsigned length) {
1415 return CreateForTabulationCharacters(
1416 font, text_run.Direction(), text_run.GetTabSize(),
1417 text_run.XPos() + position_offset, 0, length);
1418 }
1419
CreateForTabulationCharacters(const Font * font,TextDirection direction,const TabSize & tab_size,float position,unsigned start_index,unsigned length)1420 scoped_refptr<ShapeResult> ShapeResult::CreateForTabulationCharacters(
1421 const Font* font,
1422 TextDirection direction,
1423 const TabSize& tab_size,
1424 float position,
1425 unsigned start_index,
1426 unsigned length) {
1427 DCHECK_GT(length, 0u);
1428 const SimpleFontData* font_data = font->PrimaryFont();
1429 DCHECK(font_data);
1430 scoped_refptr<ShapeResult> result =
1431 ShapeResult::Create(font, start_index, length, direction);
1432 result->num_glyphs_ = length;
1433 DCHECK_EQ(result->num_glyphs_, length); // no overflow
1434 result->has_vertical_offsets_ =
1435 font_data->PlatformData().IsVerticalAnyUpright();
1436 // Tab characters are always LTR or RTL, not TTB, even when
1437 // isVerticalAnyUpright().
1438 hb_direction_t hb_direction =
1439 IsLtr(direction) ? HB_DIRECTION_LTR : HB_DIRECTION_RTL;
1440 // Only the advance of the first tab is affected by |position|.
1441 float advance = font->TabWidth(font_data, tab_size, position);
1442 do {
1443 unsigned run_length = std::min(length, HarfBuzzRunGlyphData::kMaxGlyphs);
1444 scoped_refptr<ShapeResult::RunInfo> run = RunInfo::Create(
1445 font_data, hb_direction, CanvasRotationInVertical::kRegular,
1446 HB_SCRIPT_COMMON, start_index, run_length, run_length);
1447 float start_position = position;
1448 for (unsigned i = 0; i < run_length; i++) {
1449 // 2nd and following tabs have the base width, without using |position|.
1450 if (i == 1)
1451 advance = font->TabWidth(font_data, tab_size);
1452 run->glyph_data_[i] = {font_data->SpaceGlyph(), i, true, advance};
1453 position += advance;
1454 }
1455 run->width_ = position - start_position;
1456 result->width_ += run->width_;
1457 result->runs_.push_back(std::move(run));
1458 DCHECK_GE(length, run_length);
1459 length -= run_length;
1460 start_index += run_length;
1461 } while (length);
1462 return result;
1463 }
1464
CreateForSpaces(const Font * font,TextDirection direction,unsigned start_index,unsigned length,float width)1465 scoped_refptr<ShapeResult> ShapeResult::CreateForSpaces(const Font* font,
1466 TextDirection direction,
1467 unsigned start_index,
1468 unsigned length,
1469 float width) {
1470 DCHECK_GT(length, 0u);
1471 const SimpleFontData* font_data = font->PrimaryFont();
1472 DCHECK(font_data);
1473 scoped_refptr<ShapeResult> result =
1474 ShapeResult::Create(font, start_index, length, direction);
1475 result->num_glyphs_ = length;
1476 DCHECK_EQ(result->num_glyphs_, length); // no overflow
1477 result->has_vertical_offsets_ =
1478 font_data->PlatformData().IsVerticalAnyUpright();
1479 hb_direction_t hb_direction =
1480 IsLtr(direction) ? HB_DIRECTION_LTR : HB_DIRECTION_RTL;
1481 scoped_refptr<ShapeResult::RunInfo> run = RunInfo::Create(
1482 font_data, hb_direction, CanvasRotationInVertical::kRegular,
1483 HB_SCRIPT_COMMON, start_index, length, length);
1484 result->width_ = run->width_ = width;
1485 for (unsigned i = 0; i < length; i++) {
1486 run->glyph_data_[i] = {font_data->SpaceGlyph(), i, true, width};
1487 width = 0;
1488 }
1489 result->runs_.push_back(std::move(run));
1490 return result;
1491 }
1492
CreateForStretchyMathOperator(const Font * font,TextDirection direction,Glyph glyph_variant,float stretch_size)1493 scoped_refptr<ShapeResult> ShapeResult::CreateForStretchyMathOperator(
1494 const Font* font,
1495 TextDirection direction,
1496 Glyph glyph_variant,
1497 float stretch_size) {
1498 unsigned start_index = 0;
1499 unsigned num_characters = 1;
1500 scoped_refptr<ShapeResult> result =
1501 ShapeResult::Create(font, start_index, num_characters, direction);
1502
1503 hb_direction_t hb_direction = HB_DIRECTION_LTR;
1504 unsigned glyph_index = 0;
1505 scoped_refptr<ShapeResult::RunInfo> run = RunInfo::Create(
1506 font->PrimaryFont(), hb_direction, CanvasRotationInVertical::kRegular,
1507 HB_SCRIPT_COMMON, start_index, 1 /* num_glyph */, num_characters);
1508 run->glyph_data_[glyph_index] = {glyph_variant, 0 /* character index */,
1509 true /* IsSafeToBreakBefore */,
1510 stretch_size};
1511 run->width_ = std::max(0.0f, stretch_size);
1512
1513 result->width_ = run->width_;
1514 result->num_glyphs_ = run->NumGlyphs();
1515 result->runs_.push_back(std::move(run));
1516
1517 return result;
1518 }
1519
CreateForStretchyMathOperator(const Font * font,TextDirection direction,OpenTypeMathStretchData::StretchAxis stretch_axis,const OpenTypeMathStretchData::AssemblyParameters & assembly_parameters)1520 scoped_refptr<ShapeResult> ShapeResult::CreateForStretchyMathOperator(
1521 const Font* font,
1522 TextDirection direction,
1523 OpenTypeMathStretchData::StretchAxis stretch_axis,
1524 const OpenTypeMathStretchData::AssemblyParameters& assembly_parameters) {
1525 DCHECK(!assembly_parameters.parts.IsEmpty());
1526 DCHECK_LE(assembly_parameters.glyph_count, HarfBuzzRunGlyphData::kMaxGlyphs);
1527
1528 bool is_horizontal_assembly =
1529 stretch_axis == OpenTypeMathStretchData::StretchAxis::Horizontal;
1530 unsigned start_index = 0;
1531 unsigned num_characters = 1;
1532 scoped_refptr<ShapeResult> result =
1533 ShapeResult::Create(font, start_index, num_characters, direction);
1534
1535 hb_direction_t hb_direction =
1536 is_horizontal_assembly ? HB_DIRECTION_LTR : HB_DIRECTION_TTB;
1537 scoped_refptr<ShapeResult::RunInfo> run = RunInfo::Create(
1538 font->PrimaryFont(), hb_direction, CanvasRotationInVertical::kRegular,
1539 HB_SCRIPT_COMMON, start_index, assembly_parameters.glyph_count,
1540 num_characters);
1541
1542 float overlap = assembly_parameters.connector_overlap;
1543 unsigned part_index = 0;
1544 for (const auto& part : assembly_parameters.parts) {
1545 unsigned repetition_count =
1546 part.is_extender ? assembly_parameters.repetition_count : 1;
1547 if (!repetition_count)
1548 continue;
1549 DCHECK(part_index < assembly_parameters.glyph_count);
1550 for (unsigned repetition_index = 0; repetition_index < repetition_count;
1551 repetition_index++) {
1552 unsigned glyph_index =
1553 is_horizontal_assembly
1554 ? part_index
1555 : assembly_parameters.glyph_count - 1 - part_index;
1556 float full_advance = glyph_index == assembly_parameters.glyph_count - 1
1557 ? part.full_advance
1558 : part.full_advance - overlap;
1559 run->glyph_data_[glyph_index] = {part.glyph, 0 /* character index */,
1560 !glyph_index /* IsSafeToBreakBefore */,
1561 full_advance};
1562 if (!is_horizontal_assembly) {
1563 GlyphOffset glyph_offset(
1564 0, -assembly_parameters.stretch_size + part.full_advance);
1565 run->glyph_data_.SetOffsetAt(glyph_index, glyph_offset);
1566 result->has_vertical_offsets_ |= (glyph_offset.Height() != 0);
1567 }
1568 part_index++;
1569 }
1570 }
1571 run->width_ = std::max(0.0f, assembly_parameters.stretch_size);
1572
1573 result->width_ = run->width_;
1574 result->num_glyphs_ = run->NumGlyphs();
1575 result->runs_.push_back(std::move(run));
1576 return result;
1577 }
1578
ToString(StringBuilder * output) const1579 void ShapeResult::ToString(StringBuilder* output) const {
1580 output->Append("#chars=");
1581 output->AppendNumber(num_characters_);
1582 output->Append(", #glyphs=");
1583 output->AppendNumber(num_glyphs_);
1584 output->Append(", dir=");
1585 output->AppendNumber(direction_);
1586 output->Append(", runs[");
1587 output->AppendNumber(runs_.size());
1588 output->Append("]{");
1589 for (unsigned run_index = 0; run_index < runs_.size(); run_index++) {
1590 output->AppendNumber(run_index);
1591 const auto& run = *runs_[run_index];
1592 output->Append(":{start=");
1593 output->AppendNumber(run.start_index_);
1594 output->Append(", #chars=");
1595 output->AppendNumber(run.num_characters_);
1596 output->Append(", dir=");
1597 output->AppendNumber(static_cast<uint32_t>(run.direction_));
1598 output->Append(", glyphs[");
1599 output->AppendNumber(run.glyph_data_.size());
1600 output->Append("]{");
1601 for (unsigned glyph_index = 0; glyph_index < run.glyph_data_.size();
1602 glyph_index++) {
1603 output->AppendNumber(glyph_index);
1604 const auto& glyph_data = run.glyph_data_[glyph_index];
1605 output->Append(":{char=");
1606 output->AppendNumber(glyph_data.character_index);
1607 output->Append(", glyph=");
1608 output->AppendNumber(glyph_data.glyph);
1609 output->Append("}");
1610 }
1611 output->Append("}}");
1612 }
1613 output->Append("}");
1614 }
1615
ToString() const1616 String ShapeResult::ToString() const {
1617 StringBuilder output;
1618 ToString(&output);
1619 return output.ToString();
1620 }
1621
operator <<(std::ostream & ostream,const ShapeResult & shape_result)1622 std::ostream& operator<<(std::ostream& ostream,
1623 const ShapeResult& shape_result) {
1624 return ostream << shape_result.ToString();
1625 }
1626
1627 template <bool rtl>
ComputePositionData() const1628 void ShapeResult::ComputePositionData() const {
1629 auto& data = character_position_->data_;
1630 unsigned start_offset = StartIndex();
1631 unsigned next_character_index = 0;
1632 float run_advance = 0;
1633 float last_x_position = 0;
1634
1635 // Iterate runs/glyphs in the visual order; i.e., from the left edge
1636 // regardless of the directionality, so that |x_position| is always in
1637 // ascending order.
1638 // TODO(kojii): It does not work when large negative letter-/word-
1639 // spacing is applied.
1640 for (const auto& run : runs_) {
1641 if (!run)
1642 continue;
1643
1644 // Assumes all runs have the same directionality as the ShapeResult so that
1645 // |x_position| is in ascending order.
1646 DCHECK_EQ(Rtl(), run->Rtl());
1647
1648 float total_advance = run_advance;
1649 for (const auto& glyph_data : run->glyph_data_) {
1650 DCHECK_GE(run->start_index_, start_offset);
1651 unsigned character_index =
1652 run->start_index_ + glyph_data.character_index - start_offset;
1653
1654 // Make |character_index| to the visual offset.
1655 DCHECK_LT(character_index, num_characters_);
1656 if (rtl)
1657 character_index = num_characters_ - character_index - 1;
1658
1659 // If this glyph is the first glyph of a new cluster, set the data.
1660 // Otherwise, |data[character_index]| is already set. Do not overwrite.
1661 DCHECK_LT(character_index, num_characters_);
1662 if (next_character_index <= character_index) {
1663 if (next_character_index < character_index) {
1664 // Multiple glyphs may have the same character index and not all
1665 // character indices may have glyphs. For character indices without
1666 // glyphs set the x-position to that of the nearest preceding glyph in
1667 // the logical order; i.e., the last position for LTR or this position
1668 // for RTL.
1669 float x_position = !rtl ? last_x_position : total_advance;
1670 for (unsigned i = next_character_index; i < character_index; i++) {
1671 DCHECK_LT(i, num_characters_);
1672 data[i] = {x_position, false, false};
1673 }
1674 }
1675
1676 data[character_index] = {total_advance, true,
1677 glyph_data.safe_to_break_before};
1678 last_x_position = total_advance;
1679 }
1680
1681 total_advance += glyph_data.advance;
1682 next_character_index = character_index + 1;
1683 }
1684 run_advance += run->width_;
1685 }
1686
1687 // Fill |x_position| for the rest of characters, when they don't have
1688 // corresponding glyphs.
1689 if (next_character_index < num_characters_) {
1690 float x_position = !rtl ? last_x_position : run_advance;
1691 for (unsigned i = next_character_index; i < num_characters_; i++) {
1692 data[i] = {x_position, false, false};
1693 }
1694 }
1695
1696 character_position_->start_offset_ = start_offset;
1697 }
1698
EnsurePositionData() const1699 void ShapeResult::EnsurePositionData() const {
1700 if (character_position_)
1701 return;
1702
1703 character_position_ =
1704 std::make_unique<CharacterPositionData>(num_characters_, width_);
1705 if (Direction() == TextDirection::kLtr)
1706 ComputePositionData<false>();
1707 else
1708 ComputePositionData<true>();
1709 }
1710
DiscardPositionData() const1711 void ShapeResult::DiscardPositionData() const {
1712 character_position_ = nullptr;
1713 }
1714
CachedOffsetForPosition(float x) const1715 unsigned ShapeResult::CachedOffsetForPosition(float x) const {
1716 DCHECK(character_position_);
1717 unsigned offset = character_position_->OffsetForPosition(x, Rtl());
1718 #if 0
1719 // TODO(kojii): This DCHECK fails in ~10 tests. Needs investigations.
1720 DCHECK_EQ(OffsetForPosition(x, BreakGlyphsOption::DontBreakGlyphs), offset) << x;
1721 #endif
1722 return offset;
1723 }
1724
CachedPositionForOffset(unsigned offset) const1725 float ShapeResult::CachedPositionForOffset(unsigned offset) const {
1726 DCHECK_GE(offset, 0u);
1727 DCHECK_LE(offset, num_characters_);
1728 DCHECK(character_position_);
1729 float position = character_position_->PositionForOffset(offset, Rtl());
1730 #if 0
1731 // TODO(kojii): This DCHECK fails in several tests. Needs investigations.
1732 DCHECK_EQ(PositionForOffset(offset), position) << offset;
1733 #endif
1734 return position;
1735 }
1736
CachedNextSafeToBreakOffset(unsigned offset) const1737 unsigned ShapeResult::CachedNextSafeToBreakOffset(unsigned offset) const {
1738 if (Rtl())
1739 return NextSafeToBreakOffset(offset);
1740
1741 DCHECK(character_position_);
1742 return character_position_->NextSafeToBreakOffset(offset);
1743 }
1744
CachedPreviousSafeToBreakOffset(unsigned offset) const1745 unsigned ShapeResult::CachedPreviousSafeToBreakOffset(unsigned offset) const {
1746 if (Rtl())
1747 return PreviousSafeToBreakOffset(offset);
1748
1749 DCHECK(character_position_);
1750 return character_position_->PreviousSafeToBreakOffset(offset);
1751 }
1752
1753 // TODO(eae): Might be worth trying to set midpoint to ~50% more than the number
1754 // of characters in the previous line for the first try. Would cut the number
1755 // of tries in the majority of cases for long strings.
OffsetForPosition(float x,bool rtl) const1756 unsigned ShapeResult::CharacterPositionData::OffsetForPosition(float x,
1757 bool rtl) const {
1758 // At or before start, return offset *of* the first character.
1759 // At or beyond the end, return offset *after* the last character.
1760 if (x <= 0)
1761 return !rtl ? 0 : data_.size();
1762 if (x >= width_)
1763 return !rtl ? data_.size() : 0;
1764
1765 // Do a binary search to find the largest x-position that is less than or
1766 // equal to the supplied x value.
1767 unsigned length = data_.size();
1768 unsigned low = 0;
1769 unsigned high = length - 1;
1770 while (low <= high) {
1771 unsigned midpoint = low + (high - low) / 2;
1772 if (data_[midpoint].x_position <= x &&
1773 (midpoint + 1 == length || data_[midpoint + 1].x_position > x)) {
1774 if (!rtl)
1775 return midpoint;
1776 // The border belongs to the logical next character.
1777 return data_[midpoint].x_position == x ? data_.size() - midpoint
1778 : data_.size() - midpoint - 1;
1779 }
1780 if (x < data_[midpoint].x_position)
1781 high = midpoint - 1;
1782 else
1783 low = midpoint + 1;
1784 }
1785
1786 return 0;
1787 }
1788
PositionForOffset(unsigned offset,bool rtl) const1789 float ShapeResult::CharacterPositionData::PositionForOffset(unsigned offset,
1790 bool rtl) const {
1791 DCHECK_GT(data_.size(), 0u);
1792 if (!rtl) {
1793 if (offset < data_.size())
1794 return data_[offset].x_position;
1795 } else {
1796 if (offset >= data_.size())
1797 return 0;
1798 // Return the left edge of the next character because in RTL, the position
1799 // is the right edge of the character.
1800 for (unsigned visual_offset = data_.size() - offset - 1;
1801 visual_offset < data_.size(); visual_offset++) {
1802 if (data_[visual_offset].is_cluster_base) {
1803 return visual_offset + 1 < data_.size()
1804 ? data_[visual_offset + 1].x_position
1805 : width_;
1806 }
1807 }
1808 }
1809 return width_;
1810 }
1811
NextSafeToBreakOffset(unsigned offset) const1812 unsigned ShapeResult::CharacterPositionData::NextSafeToBreakOffset(
1813 unsigned offset) const {
1814 DCHECK_LE(start_offset_, offset);
1815 unsigned adjusted_offset = offset - start_offset_;
1816 DCHECK_LT(adjusted_offset, data_.size());
1817
1818 // Assume it is always safe to break at the start. While not strictly correct
1819 // the text has already been segmented at that offset. This also matches the
1820 // non-CharacterPositionData implementation.
1821 if (adjusted_offset == 0)
1822 return start_offset_;
1823
1824 unsigned length = data_.size();
1825 for (unsigned i = adjusted_offset; i < length; i++) {
1826 if (data_[i].safe_to_break_before)
1827 return start_offset_ + i;
1828 }
1829
1830 // Next safe break is at the end of the run.
1831 return start_offset_ + length;
1832 }
1833
PreviousSafeToBreakOffset(unsigned offset) const1834 unsigned ShapeResult::CharacterPositionData::PreviousSafeToBreakOffset(
1835 unsigned offset) const {
1836 DCHECK_LE(start_offset_, offset);
1837 unsigned adjusted_offset = offset - start_offset_;
1838 DCHECK_LT(adjusted_offset, data_.size());
1839
1840 // Assume it is always safe to break at the end of the run.
1841 if (adjusted_offset >= data_.size())
1842 return start_offset_ + data_.size();
1843
1844 for (unsigned i = adjusted_offset + 1; i > 0; i--) {
1845 if (data_[i - 1].safe_to_break_before)
1846 return start_offset_ + (i - 1);
1847 }
1848
1849 // Previous safe break is at the start of the run.
1850 return 0;
1851 }
1852
1853 namespace {
1854
AddRunInfoRanges(const ShapeResult::RunInfo & run_info,float offset,Vector<CharacterRange> * ranges)1855 void AddRunInfoRanges(const ShapeResult::RunInfo& run_info,
1856 float offset,
1857 Vector<CharacterRange>* ranges) {
1858 Vector<float> character_widths(run_info.num_characters_);
1859 for (const auto& glyph : run_info.glyph_data_)
1860 character_widths[glyph.character_index] += glyph.advance;
1861
1862 if (run_info.Rtl())
1863 offset += run_info.width_;
1864
1865 for (unsigned character_index = 0; character_index < run_info.num_characters_;
1866 character_index++) {
1867 float start = offset;
1868 offset += character_widths[character_index] * (run_info.Rtl() ? -1 : 1);
1869 float end = offset;
1870
1871 // To match getCharacterRange we flip ranges to ensure start <= end.
1872 if (end < start)
1873 ranges->push_back(CharacterRange(end, start, 0, 0));
1874 else
1875 ranges->push_back(CharacterRange(start, end, 0, 0));
1876 }
1877 }
1878
1879 } // anonymous namespace
1880
IndividualCharacterRanges(Vector<CharacterRange> * ranges,float start_x) const1881 float ShapeResult::IndividualCharacterRanges(Vector<CharacterRange>* ranges,
1882 float start_x) const {
1883 DCHECK(ranges);
1884 float current_x = start_x;
1885
1886 if (Rtl()) {
1887 unsigned run_count = runs_.size();
1888 for (int index = run_count - 1; index >= 0; index--) {
1889 current_x -= runs_[index]->width_;
1890 AddRunInfoRanges(*runs_[index], current_x, ranges);
1891 }
1892 } else {
1893 for (const auto& run : runs_) {
1894 AddRunInfoRanges(*run, current_x, ranges);
1895 current_x += run->width_;
1896 }
1897 }
1898
1899 return current_x;
1900 }
1901
1902 template <bool is_horizontal_run, bool has_non_zero_glyph_offsets>
ComputeRunInkBounds(const ShapeResult::RunInfo & run,float run_advance,FloatRect * ink_bounds) const1903 void ShapeResult::ComputeRunInkBounds(const ShapeResult::RunInfo& run,
1904 float run_advance,
1905 FloatRect* ink_bounds) const {
1906 // Get glyph bounds from Skia. It's a lot faster if we give it list of glyph
1907 // IDs rather than calling it for each glyph.
1908 // TODO(kojii): MacOS does not benefit from batching the Skia request due to
1909 // https://bugs.chromium.org/p/skia/issues/detail?id=5328, and the cost to
1910 // prepare batching, which is normally much less than the benefit of
1911 // batching, is not ignorable unfortunately.
1912 auto glyph_offsets = run.glyph_data_.GetOffsets<has_non_zero_glyph_offsets>();
1913 const SimpleFontData& current_font_data = *run.font_data_;
1914 unsigned num_glyphs = run.glyph_data_.size();
1915 #if !defined(OS_MAC)
1916 Vector<Glyph, 256> glyphs(num_glyphs);
1917 unsigned i = 0;
1918 for (const auto& glyph_data : run.glyph_data_)
1919 glyphs[i++] = glyph_data.glyph;
1920 Vector<SkRect, 256> bounds_list(num_glyphs);
1921 current_font_data.BoundsForGlyphs(glyphs, &bounds_list);
1922 #endif
1923
1924 GlyphBoundsAccumulator bounds(run_advance);
1925 for (unsigned j = 0; j < num_glyphs; ++j) {
1926 const HarfBuzzRunGlyphData& glyph_data = run.glyph_data_[j];
1927 #if defined(OS_MAC)
1928 FloatRect glyph_bounds = current_font_data.BoundsForGlyph(glyph_data.glyph);
1929 #else
1930 FloatRect glyph_bounds(bounds_list[j]);
1931 #endif
1932 bounds.Unite<is_horizontal_run>(glyph_bounds, *glyph_offsets);
1933 ++glyph_offsets;
1934 bounds.origin += glyph_data.advance;
1935 }
1936
1937 if (!is_horizontal_run)
1938 bounds.ConvertVerticalRunToLogical(current_font_data.GetFontMetrics());
1939 ink_bounds->Unite(bounds.bounds);
1940 }
1941
ComputeInkBounds() const1942 FloatRect ShapeResult::ComputeInkBounds() const {
1943 FloatRect ink_bounds;
1944 float run_advance = 0.0f;
1945 for (const auto& run : runs_) {
1946 if (run->glyph_data_.HasNonZeroOffsets()) {
1947 if (run->IsHorizontal())
1948 ComputeRunInkBounds<true, true>(*run.get(), run_advance, &ink_bounds);
1949 else
1950 ComputeRunInkBounds<false, true>(*run.get(), run_advance, &ink_bounds);
1951 } else {
1952 if (run->IsHorizontal())
1953 ComputeRunInkBounds<true, false>(*run.get(), run_advance, &ink_bounds);
1954 else
1955 ComputeRunInkBounds<false, false>(*run.get(), run_advance, &ink_bounds);
1956 }
1957 run_advance += run->width_;
1958 }
1959
1960 return ink_bounds;
1961 }
1962
1963 } // namespace blink
1964