submodule/skia/modules/skparagraph/src/TextLine.cpp

   1 // Copyright 2019 Google LLC.
   2 #include "include/core/SkBlurTypes.h"
   3 #include "include/core/SkCanvas.h"
   4 #include "include/core/SkFont.h"
   5 #include "include/core/SkFontMetrics.h"
   6 #include "include/core/SkMaskFilter.h"
   7 #include "include/core/SkPaint.h"
   8 #include "include/core/SkSpan.h"
   9 #include "include/core/SkString.h"
  10 #include "include/core/SkTextBlob.h"
  11 #include "include/core/SkTypes.h"
  12 #include "include/private/SkTemplates.h"
  13 #include "include/private/SkTo.h"
  14 #include "modules/skparagraph/include/DartTypes.h"
  15 #include "modules/skparagraph/include/Metrics.h"
  16 #include "modules/skparagraph/include/ParagraphStyle.h"
  17 #include "modules/skparagraph/include/TextShadow.h"
  18 #include "modules/skparagraph/include/TextStyle.h"
  19 #include "modules/skparagraph/src/Decorations.h"
  20 #include "modules/skparagraph/src/ParagraphImpl.h"
  21 #include "modules/skparagraph/src/TextLine.h"
  22 #include "modules/skshaper/include/SkShaper.h"
  23
  24 #include <algorithm>
  25 #include <iterator>
  26 #include <limits>
  27 #include <map>
  28 #include <memory>
  29 #include <tuple>
  30 #include <type_traits>
  31 #include <utility>
  32
  33 namespace skia {
  34 namespace textlayout {
  35
  36 namespace {
  37
  38 // TODO: deal with all the intersection functionality
  39 TextRange intersected(const TextRange& a, const TextRange& b) {
  40     if (a.start == b.start && a.end == b.end) return a;
  41     auto begin = std::max(a.start, b.start);
  42     auto end = std::min(a.end, b.end);
  43     return end >= begin ? TextRange(begin, end) : EMPTY_TEXT;
  44 }
  45
  46 SkScalar littleRound(SkScalar a) {
  47     // This rounding is done to match Flutter tests. Must be removed..
  48   return SkScalarRoundToScalar(a * 100.0)/100.0;
  49 }
  50
  51 TextRange operator*(const TextRange& a, const TextRange& b) {
  52     if (a.start == b.start && a.end == b.end) return a;
  53     auto begin = std::max(a.start, b.start);
  54     auto end = std::min(a.end, b.end);
  55     return end > begin ? TextRange(begin, end) : EMPTY_TEXT;
  56 }
  57
  58 int compareRound(SkScalar a, SkScalar b) {
  59     // There is a rounding error that gets bigger when maxWidth gets bigger
  60     // VERY long zalgo text (> 100000) on a VERY long line (> 10000)
  61     // Canvas scaling affects it
  62     // Letter spacing affects it
  63     // It has to be relative to be useful
  64     auto base = std::max(SkScalarAbs(a), SkScalarAbs(b));
  65     auto diff = SkScalarAbs(a - b);
  66     if (nearlyZero(base) || diff / base < 0.001f) {
  67         return 0;
  68     }
  69
  70     auto ra = littleRound(a);
  71     auto rb = littleRound(b);
  72     if (ra < rb) {
  73         return -1;
  74     } else {
  75         return 1;
  76     }
  77 }
  78
  79 }  // namespace
  80
  81 TextLine::TextLine(ParagraphImpl* owner,
  82                    SkVector offset,
  83                    SkVector advance,
  84                    BlockRange blocks,
  85                    TextRange textExcludingSpaces,
  86                    TextRange text,
  87                    TextRange textIncludingNewlines,
  88                    ClusterRange clusters,
  89                    ClusterRange clustersWithGhosts,
  90                    SkScalar widthWithSpaces,
  91                    InternalLineMetrics sizes)
  92         : fOwner(owner)
  93         , fBlockRange(blocks)
  94         , fTextExcludingSpaces(textExcludingSpaces)
  95         , fText(text)
  96         , fTextIncludingNewlines(textIncludingNewlines)
  97         , fClusterRange(clusters)
  98         , fGhostClusterRange(clustersWithGhosts)
  99         , fRunsInVisualOrder()
 100         , fAdvance(advance)
 101         , fOffset(offset)
 102         , fShift(0.0)
 103         , fWidthWithSpaces(widthWithSpaces)
 104         , fEllipsis(nullptr)
 105         , fSizes(sizes)
 106         , fHasBackground(false)
 107         , fHasShadows(false)
 108         , fHasDecorations(false)
 109         , fAscentStyle(LineMetricStyle::CSS)
 110         , fDescentStyle(LineMetricStyle::CSS)
 111         , fTextBlobCachePopulated(false) {
 112     // Reorder visual runs
 113     auto& start = owner->cluster(fGhostClusterRange.start);
 114     auto& end = owner->cluster(fGhostClusterRange.end - 1);
 115     size_t numRuns = end.runIndex() - start.runIndex() + 1;
 116
 117     for (BlockIndex index = fBlockRange.start; index < fBlockRange.end; ++index) {
 118         auto b = fOwner->styles().begin() + index;
 119         if (b->fStyle.hasBackground()) {
 120             fHasBackground = true;
 121         }
 122         if (b->fStyle.getDecorationType() != TextDecoration::kNoDecoration) {
 123             fHasDecorations = true;
 124         }
 125         if (b->fStyle.getShadowNumber() > 0) {
 126             fHasShadows = true;
 127         }
 128     }
 129
 130     // Get the logical order
 131
 132     // This is just chosen to catch the common/fast cases. Feel free to tweak.
 133     constexpr int kPreallocCount = 4;
 134     SkAutoSTArray<kPreallocCount, SkUnicode::BidiLevel> runLevels(numRuns);
 135     size_t runLevelsIndex = 0;
 136     for (auto runIndex = start.runIndex(); runIndex <= end.runIndex(); ++runIndex) {
 137         auto& run = fOwner->run(runIndex);
 138         runLevels[runLevelsIndex++] = run.fBidiLevel;
 139         fMaxRunMetrics.add(
 140             InternalLineMetrics(run.fFontMetrics.fAscent, run.fFontMetrics.fDescent, run.fFontMetrics.fLeading));
 141     }
 142     SkASSERT(runLevelsIndex == numRuns);
 143
 144     SkAutoSTArray<kPreallocCount, int32_t> logicalOrder(numRuns);
 145
 146     // TODO: hide all these logic in SkUnicode?
 147   fOwner->getUnicode()->reorderVisual(runLevels.data(), numRuns, logicalOrder.data());
 148     auto firstRunIndex = start.runIndex();
 149     for (auto index : logicalOrder) {
 150         fRunsInVisualOrder.push_back(firstRunIndex + index);
 151     }
 152
 153     // TODO: This is the fix for flutter. Must be removed...
 154     for (auto cluster = &start; cluster <= &end; ++cluster) {
 155         if (!cluster->run().isPlaceholder()) {
 156             fShift += cluster->getHalfLetterSpacing();
 157             break;
 158         }
 159     }
 160 }
 161
 162 void TextLine::paint(SkCanvas* textCanvas, SkScalar x, SkScalar y) {
 163     if (fHasBackground) {
 164         this->iterateThroughVisualRuns(false,
 165             [textCanvas, x, y, this]
 166             (const Run* run, SkScalar runOffsetInLine, TextRange textRange, SkScalar* runWidthInLine) {
 167                 *runWidthInLine = this->iterateThroughSingleRunByStyles(
 168                 run, runOffsetInLine, textRange, StyleType::kBackground,
 169                 [textCanvas, x, y, this](TextRange textRange, const TextStyle& style, const ClipContext& context) {
 170                     this->paintBackground(textCanvas, x, y, textRange, style, context);
 171                 });
 172             return true;
 173             });
 174     }
 175
 176     if (fHasShadows) {
 177         this->iterateThroughVisualRuns(false,
 178             [textCanvas, x, y, this]
 179             (const Run* run, SkScalar runOffsetInLine, TextRange textRange, SkScalar* runWidthInLine) {
 180             *runWidthInLine = this->iterateThroughSingleRunByStyles(
 181                 run, runOffsetInLine, textRange, StyleType::kShadow,
 182                 [textCanvas, x, y, this]
 183                 (TextRange textRange, const TextStyle& style, const ClipContext& context) {
 184                     this->paintShadow(textCanvas, x, y, textRange, style, context);
 185                 });
 186             return true;
 187             });
 188     }
 189
 190     ensureTextBlobCachePopulated();
 191
 192     for (auto& record : fTextBlobCache) {
 193         record.paint(textCanvas, x, y);
 194     }
 195
 196     if (fHasDecorations) {
 197         this->iterateThroughVisualRuns(false,
 198             [textCanvas, x, y, this]
 199             (const Run* run, SkScalar runOffsetInLine, TextRange textRange, SkScalar* runWidthInLine) {
 200                 *runWidthInLine = this->iterateThroughSingleRunByStyles(
 201                 run, runOffsetInLine, textRange, StyleType::kDecorations,
 202                 [textCanvas, x, y, this]
 203                 (TextRange textRange, const TextStyle& style, const ClipContext& context) {
 204                     this->paintDecorations(textCanvas, x, y, textRange, style, context);
 205                 });
 206                 return true;
 207         });
 208     }
 209 }
 210
 211 void TextLine::ensureTextBlobCachePopulated() {
 212     if (fTextBlobCachePopulated) {
 213         return;
 214     }
 215     if (fBlockRange.width() == 1 &&
 216         fRunsInVisualOrder.size() == 1 &&
 217         fEllipsis == nullptr &&
 218         fOwner->run(fRunsInVisualOrder[0]).placeholderStyle() == nullptr) {
 219         if (fClusterRange.width() == 0) {
 220             return;
 221         }
 222         // Most common and most simple case
 223         const auto& style = fOwner->block(fBlockRange.start).fStyle;
 224         const auto& run = fOwner->run(fRunsInVisualOrder[0]);
 225         auto clip = SkRect::MakeXYWH(0.0f, this->sizes().runTop(&run, this->fAscentStyle),
 226                                      fAdvance.fX,
 227                                      run.calculateHeight(this->fAscentStyle, this->fDescentStyle));
 228
 229         auto& start = fOwner->cluster(fClusterRange.start);
 230         auto& end = fOwner->cluster(fClusterRange.end - 1);
 231         SkASSERT(start.runIndex() == end.runIndex());
 232         GlyphRange glyphs;
 233         if (run.leftToRight()) {
 234             glyphs = GlyphRange(start.startPos(),
 235                                 end.isHardBreak() ? end.startPos() : end.endPos());
 236         } else {
 237             glyphs = GlyphRange(end.startPos(),
 238                                 start.isHardBreak() ? start.startPos() : start.endPos());
 239         }
 240         ClipContext context = {/*run=*/&run,
 241                                /*pos=*/glyphs.start,
 242                                /*size=*/glyphs.width(),
 243                                /*fTextShift=*/-run.positionX(glyphs.start), // starting position
 244                                /*clip=*/clip,                               // entire line
 245                                /*fExcludedTrailingSpaces=*/0.0f,            // no need for that
 246                                /*clippingNeeded=*/false};                   // no need for that
 247         this->buildTextBlob(fTextExcludingSpaces, style, context);
 248     } else {
 249         this->iterateThroughVisualRuns(false,
 250            [this](const Run* run,
 251                   SkScalar runOffsetInLine,
 252                   TextRange textRange,
 253                   SkScalar* runWidthInLine) {
 254                if (run->placeholderStyle() != nullptr) {
 255                    *runWidthInLine = run->advance().fX;
 256                    return true;
 257                }
 258                *runWidthInLine = this->iterateThroughSingleRunByStyles(
 259                    run,
 260                    runOffsetInLine,
 261                    textRange,
 262                    StyleType::kForeground,
 263                    [this](TextRange textRange, const TextStyle& style, const ClipContext& context) {
 264                        this->buildTextBlob(textRange, style, context);
 265                    });
 266                return true;
 267            });
 268     }
 269     fTextBlobCachePopulated = true;
 270 }
 271
 272 void TextLine::format(TextAlign align, SkScalar maxWidth) {
 273     SkScalar delta = maxWidth - this->width();
 274     if (delta <= 0) {
 275         return;
 276     }
 277
 278     // We do nothing for left align
 279     if (align == TextAlign::kJustify) {
 280         if (!this->endsWithHardLineBreak()) {
 281             this->justify(maxWidth);
 282         } else if (fOwner->paragraphStyle().getTextDirection() == TextDirection::kRtl) {
 283             // Justify -> Right align
 284             fShift = delta;
 285         }
 286     } else if (align == TextAlign::kRight) {
 287         fShift = delta;
 288     } else if (align == TextAlign::kCenter) {
 289         fShift = delta / 2;
 290     }
 291 }
 292
 293 void TextLine::scanStyles(StyleType styleType, const RunStyleVisitor& visitor) {
 294     if (this->empty()) {
 295         return;
 296     }
 297
 298     this->iterateThroughVisualRuns(false,
 299         [this, visitor, styleType](const Run* run, SkScalar runOffset, TextRange textRange, SkScalar* width) {
 300             *width = this->iterateThroughSingleRunByStyles(
 301                 run, runOffset, textRange, styleType,
 302                 [visitor](TextRange textRange, const TextStyle& style, const ClipContext& context) {
 303                     visitor(textRange, style, context);
 304                 });
 305             return true;
 306         });
 307 }
 308
 309 SkRect TextLine::extendHeight(const ClipContext& context) const {
 310     SkRect result = context.clip;
 311     result.fBottom += std::max(this->fMaxRunMetrics.height() - this->height(), 0.0f);
 312     return result;
 313 }
 314
 315 SkScalar TextLine::metricsWithoutMultiplier(TextHeightBehavior correction) {
 316
 317     if (this->fSizes.getForceStrut()) {
 318         return 0;
 319     }
 320
 321     InternalLineMetrics result;
 322     this->iterateThroughVisualRuns(true,
 323         [&result](const Run* run, SkScalar runOffset, TextRange textRange, SkScalar* width) {
 324         InternalLineMetrics runMetrics(run->ascent(), run->descent(), run->leading());
 325         result.add(runMetrics);
 326         return true;
 327     });
 328     SkScalar delta = 0;
 329     if (correction  == TextHeightBehavior::kDisableFirstAscent) {
 330         delta += (this->fSizes.fAscent - result.fAscent);
 331         this->fSizes.fAscent = result.fAscent;
 332         this->fAscentStyle = LineMetricStyle::Typographic;
 333     } else if (correction  == TextHeightBehavior::kDisableLastDescent) {
 334         delta -= (this->fSizes.fDescent - result.fDescent);
 335         this->fSizes.fDescent = result.fDescent;
 336         this->fDescentStyle = LineMetricStyle::Typographic;
 337     }
 338     fAdvance.fY += delta;
 339     return delta;
 340 }
 341
 342 void TextLine::buildTextBlob(TextRange textRange, const TextStyle& style, const ClipContext& context) {
 343     if (context.run->placeholderStyle() != nullptr) {
 344         return;
 345     }
 346
 347     fTextBlobCache.emplace_back();
 348     TextBlobRecord& record = fTextBlobCache.back();
 349
 350     if (style.hasForeground()) {
 351         record.fPaint = style.getForeground();
 352     } else {
 353         record.fPaint.setColor(style.getColor());
 354     }
 355     record.fVisitor_Run = context.run;
 356     record.fVisitor_Pos = context.pos;
 357
 358     // TODO: This is the change for flutter, must be removed later
 359     SkTextBlobBuilder builder;
 360     context.run->copyTo(builder, SkToU32(context.pos), context.size);
 361     record.fClippingNeeded = context.clippingNeeded;
 362     if (context.clippingNeeded) {
 363         record.fClipRect = extendHeight(context).makeOffset(this->offset());
 364     } else {
 365         record.fClipRect = context.clip.makeOffset(this->offset());
 366     }
 367
 368     SkASSERT(nearlyEqual(context.run->baselineShift(), style.getBaselineShift()));
 369     SkScalar correctedBaseline = SkScalarFloorToScalar(this->baseline() + style.getBaselineShift() +  0.5);
 370     record.fBlob = builder.make();
 371     if (record.fBlob != nullptr) {
 372         record.fBounds.joinPossiblyEmptyRect(record.fBlob->bounds());
 373     }
 374
 375     record.fOffset = SkPoint::Make(this->offset().fX + context.fTextShift,
 376                                    this->offset().fY + correctedBaseline);
 377 }
 378
 379 void TextLine::TextBlobRecord::paint(SkCanvas* canvas, SkScalar x, SkScalar y) {
 380     if (fClippingNeeded) {
 381         canvas->save();
 382         canvas->clipRect(fClipRect.makeOffset(x, y));
 383     }
 384     canvas->drawTextBlob(fBlob, x + fOffset.x(), y + fOffset.y(), fPaint);
 385     if (fClippingNeeded) {
 386         canvas->restore();
 387     }
 388 }
 389
 390 void TextLine::paintBackground(SkCanvas* canvas,
 391                                SkScalar x,
 392                                SkScalar y,
 393                                TextRange textRange,
 394                                const TextStyle& style,
 395                                const ClipContext& context) const {
 396     if (style.hasBackground()) {
 397         canvas->drawRect(context.clip.makeOffset(this->offset() + SkPoint::Make(x, y)),
 398                          style.getBackground());
 399     }
 400 }
 401
 402 void TextLine::paintShadow(SkCanvas* canvas,
 403                            SkScalar x,
 404                            SkScalar y,
 405                            TextRange textRange,
 406                            const TextStyle& style,
 407                            const ClipContext& context) const {
 408     SkScalar correctedBaseline = SkScalarFloorToScalar(this->baseline() + style.getBaselineShift() + 0.5);
 409
 410     for (TextShadow shadow : style.getShadows()) {
 411         if (!shadow.hasShadow()) continue;
 412
 413         SkPaint paint;
 414         paint.setColor(shadow.fColor);
 415         if (shadow.fBlurSigma != 0.0) {
 416             auto filter = SkMaskFilter::MakeBlur(kNormal_SkBlurStyle,
 417                                                  SkDoubleToScalar(shadow.fBlurSigma), false);
 418             paint.setMaskFilter(filter);
 419         }
 420
 421         SkTextBlobBuilder builder;
 422         context.run->copyTo(builder, context.pos, context.size);
 423
 424         if (context.clippingNeeded) {
 425             canvas->save();
 426             SkRect clip = extendHeight(context);
 427             clip.offset(this->offset());
 428             canvas->clipRect(clip);
 429         }
 430         auto blob = builder.make();
 431         canvas->drawTextBlob(blob,
 432             x + this->offset().fX + shadow.fOffset.x() + context.fTextShift,
 433             y + this->offset().fY + shadow.fOffset.y() + correctedBaseline,
 434             paint);
 435         if (context.clippingNeeded) {
 436             canvas->restore();
 437         }
 438     }
 439 }
 440
 441 void TextLine::paintDecorations(SkCanvas* canvas, SkScalar x, SkScalar y, TextRange textRange, const TextStyle& style, const ClipContext& context) const {
 442
 443     SkAutoCanvasRestore acr(canvas, true);
 444     canvas->translate(x + this->offset().fX, y + this->offset().fY + style.getBaselineShift());
 445     Decorations decorations;
 446     SkScalar correctedBaseline = SkScalarFloorToScalar(this->baseline() + style.getBaselineShift() + 0.5);
 447     decorations.paint(canvas, style, context, correctedBaseline);
 448 }
 449
 450 void TextLine::justify(SkScalar maxWidth) {
 451     // Count words and the extra spaces to spread across the line
 452     // TODO: do it at the line breaking?..
 453     size_t whitespacePatches = 0;
 454     SkScalar textLen = 0;
 455     bool whitespacePatch = false;
 456     this->iterateThroughClustersInGlyphsOrder(false, false,
 457         [&whitespacePatches, &textLen, &whitespacePatch](const Cluster* cluster, bool ghost) {
 458             if (cluster->isWhitespaceBreak()) {
 459                 if (!whitespacePatch) {
 460                     whitespacePatch = true;
 461                     ++whitespacePatches;
 462                 }
 463             } else {
 464                 whitespacePatch = false;
 465             }
 466             textLen += cluster->width();
 467             return true;
 468         });
 469
 470     if (whitespacePatches == 0) {
 471         return;
 472     }
 473
 474     SkScalar step = (maxWidth - textLen) / whitespacePatches;
 475     SkScalar shift = 0;
 476
 477     // Deal with the ghost spaces
 478     auto ghostShift = maxWidth - this->fAdvance.fX;
 479     // Spread the extra whitespaces
 480     whitespacePatch = false;
 481     this->iterateThroughClustersInGlyphsOrder(false, true, [&](const Cluster* cluster, bool ghost) {
 482
 483         if (ghost) {
 484             if (cluster->run().leftToRight()) {
 485                 shiftCluster(cluster, ghostShift, ghostShift);
 486             }
 487             return true;
 488         }
 489
 490         auto prevShift = shift;
 491         if (cluster->isWhitespaceBreak()) {
 492             if (!whitespacePatch) {
 493                 shift += step;
 494                 whitespacePatch = true;
 495                 --whitespacePatches;
 496             }
 497         } else {
 498             whitespacePatch = false;
 499         }
 500         shiftCluster(cluster, shift, prevShift);
 501         return true;
 502     });
 503
 504     SkAssertResult(nearlyEqual(shift, maxWidth - textLen));
 505     SkASSERT(whitespacePatches == 0);
 506
 507     this->fWidthWithSpaces += ghostShift;
 508     this->fAdvance.fX = maxWidth;
 509 }
 510
 511 void TextLine::shiftCluster(const Cluster* cluster, SkScalar shift, SkScalar prevShift) {
 512
 513     auto& run = cluster->run();
 514     auto start = cluster->startPos();
 515     auto end = cluster->endPos();
 516
 517     if (end == run.size()) {
 518         // Set the same shift for the fake last glyph (to avoid all extra checks)
 519         ++end;
 520     }
 521
 522     if (run.fJustificationShifts.empty()) {
 523         // Do not fill this array until needed
 524         run.fJustificationShifts.push_back_n(run.size() + 1, { 0, 0 });
 525     }
 526
 527     for (size_t pos = start; pos < end; ++pos) {
 528         run.fJustificationShifts[pos] = { shift, prevShift };
 529     }
 530 }
 531
 532 void TextLine::createEllipsis(SkScalar maxWidth, const SkString& ellipsis, bool) {
 533     // Replace some clusters with the ellipsis
 534     // Go through the clusters in the reverse logical order
 535     // taking off cluster by cluster until the ellipsis fits
 536     SkScalar width = fAdvance.fX;
 537     // There is one case when we need to attach the ellipsis on the left:
 538     // when the first few runs together wider than the ellipsis run are RTL
 539     // In all the other cases we attach the ellipsis on the right
 540     RunIndex leftRun = EMPTY_RUN;
 541     std::unique_ptr<Run> ellipsisRun;
 542     iterateThroughClustersInGlyphsOrder(
 543         false, false, [&](const Cluster* cluster, bool ghost) {
 544             if (cluster->run().leftToRight()) {
 545                 return false;
 546             }
 547             // Shape the ellipsis if the run has changed
 548             if (leftRun != cluster->runIndex()) {
 549                 ellipsisRun = shapeEllipsis(ellipsis, cluster->run());
 550                 if (ellipsisRun->advance().fX > maxWidth) {
 551                     // Ellipsis is bigger than the entire line
 552                     return false;
 553                 }
 554                 ellipsisRun->fClusterStart = cluster->textRange().start;
 555                 ellipsisRun->setOwner(fOwner);
 556                 leftRun = cluster->runIndex();
 557             }
 558             // See if it fits
 559             if (width + ellipsisRun->advance().fX > maxWidth) {
 560                 width -= cluster->width();
 561                 // Continue if it's not
 562                 return true;
 563             }
 564             fEllipsis = std::move(ellipsisRun);
 565             fEllipsis->fBidiLevel = 1;
 566             fClusterRange.end = cluster - fOwner->clusters().data() + 1;
 567             fGhostClusterRange.end = cluster - fOwner->clusters().data() + 1;
 568             fText.end = cluster->textRange().end;
 569             fTextIncludingNewlines.end = cluster->textRange().end;
 570             fTextExcludingSpaces.end = cluster->textRange().end;
 571             fAdvance.fX = width;
 572             return false;
 573         });
 574
 575     if (fEllipsis) return;
 576
 577     RunIndex rightRun = EMPTY_RUN;
 578     iterateThroughClustersInGlyphsOrder(
 579         true, false, [&](const Cluster* cluster, bool ghost) {
 580             // Shape the ellipsis if the run has changed
 581             if (rightRun != cluster->runIndex()) {
 582                 // Shape the ellipsis
 583                 ellipsisRun = shapeEllipsis(ellipsis, cluster->run());
 584                 if (ellipsisRun->advance().fX > maxWidth) {
 585                     // Ellipsis is bigger than the entire line
 586                     return false;
 587                 }
 588                 ellipsisRun->fClusterStart = cluster->textRange().start;
 589                 ellipsisRun->setOwner(fOwner);
 590                 rightRun = cluster->runIndex();
 591             }
 592             // See if it fits
 593             if (width + ellipsisRun->advance().fX > maxWidth) {
 594                 width -= cluster->width();
 595                 // Continue if it's not
 596                 return true;
 597             }
 598             fEllipsis = std::move(ellipsisRun);
 599             fEllipsis->fBidiLevel = 0;
 600             fClusterRange.end = cluster - fOwner->clusters().data() + 1;
 601             fGhostClusterRange.end = fClusterRange.end;
 602             fText.end = cluster->textRange().end;
 603             fTextIncludingNewlines.end = cluster->textRange().end;
 604             fTextExcludingSpaces.end = cluster->textRange().end;
 605             fAdvance.fX = width;
 606             return false;
 607         });
 608     if (fEllipsis) return;
 609
 610     // Weird situation: ellipsis does not fit; no ellipsis then
 611     fClusterRange.end = fClusterRange.start;
 612     fGhostClusterRange.end = fClusterRange.start;
 613     fText.end = fText.start;
 614     fTextIncludingNewlines.end = fTextIncludingNewlines.start;
 615     fTextExcludingSpaces.end = fTextExcludingSpaces.start;
 616     fAdvance.fX = 0;
 617 }
 618
 619 std::unique_ptr<Run> TextLine::shapeEllipsis(const SkString& ellipsis, const Run& run) {
 620
 621     class ShapeHandler final : public SkShaper::RunHandler {
 622     public:
 623         ShapeHandler(SkScalar lineHeight, bool useHalfLeading, SkScalar baselineShift, const SkString& ellipsis)
 624             : fRun(nullptr), fLineHeight(lineHeight), fUseHalfLeading(useHalfLeading), fBaselineShift(baselineShift), fEllipsis(ellipsis) {}
 625         Run* run() & { return fRun.get(); }
 626         std::unique_ptr<Run> run() && { return std::move(fRun); }
 627
 628     private:
 629         void beginLine() override {}
 630
 631         void runInfo(const RunInfo&) override {}
 632
 633         void commitRunInfo() override {}
 634
 635         Buffer runBuffer(const RunInfo& info) override {
 636             SkASSERT(!fRun);
 637             fRun = std::make_unique<Run>(nullptr, info, 0, fLineHeight, fUseHalfLeading, fBaselineShift, 0, 0);
 638             return fRun->newRunBuffer();
 639         }
 640
 641         void commitRunBuffer(const RunInfo& info) override {
 642             fRun->fAdvance.fX = info.fAdvance.fX;
 643             fRun->fAdvance.fY = fRun->advance().fY;
 644             fRun->fPlaceholderIndex = std::numeric_limits<size_t>::max();
 645             fRun->fEllipsis = true;
 646         }
 647
 648         void commitLine() override {}
 649
 650         std::unique_ptr<Run> fRun;
 651         SkScalar fLineHeight;
 652         bool fUseHalfLeading;
 653         SkScalar fBaselineShift;
 654         SkString fEllipsis;
 655     };
 656
 657     ShapeHandler handler(run.heightMultiplier(), run.useHalfLeading(), run.baselineShift(), ellipsis);
 658     std::unique_ptr<SkShaper> shaper = SkShaper::MakeShapeDontWrapOrReorder();
 659     SkASSERT_RELEASE(shaper != nullptr);
 660     shaper->shape(ellipsis.c_str(), ellipsis.size(), run.font(), true,
 661                   std::numeric_limits<SkScalar>::max(), &handler);
 662     handler.run()->fTextRange = TextRange(0, ellipsis.size());
 663     handler.run()->fOwner = fOwner;
 664     return std::move(handler).run();
 665 }
 666
 667 TextLine::ClipContext TextLine::measureTextInsideOneRun(TextRange textRange,
 668                                                         const Run* run,
 669                                                         SkScalar runOffsetInLine,
 670                                                         SkScalar textOffsetInRunInLine,
 671                                                         bool includeGhostSpaces,
 672                                                         bool limitToGraphemes) const {
 673     ClipContext result = { run, 0, run->size(), 0, SkRect::MakeEmpty(), 0, false };
 674
 675     if (run->fEllipsis) {
 676         // Both ellipsis and placeholders can only be measured as one glyph
 677         result.fTextShift = runOffsetInLine;
 678         result.clip = SkRect::MakeXYWH(runOffsetInLine,
 679                                        sizes().runTop(run, this->fAscentStyle),
 680                                        run->advance().fX,
 681                                        run->calculateHeight(this->fAscentStyle,this->fDescentStyle));
 682         return result;
 683     } else if (run->isPlaceholder()) {
 684         result.fTextShift = runOffsetInLine;
 685         if (SkScalarIsFinite(run->fFontMetrics.fAscent)) {
 686           result.clip = SkRect::MakeXYWH(runOffsetInLine,
 687                                          sizes().runTop(run, this->fAscentStyle),
 688                                          run->advance().fX,
 689                                          run->calculateHeight(this->fAscentStyle,this->fDescentStyle));
 690         } else {
 691             result.clip = SkRect::MakeXYWH(runOffsetInLine, run->fFontMetrics.fAscent, run->advance().fX, 0);
 692         }
 693         return result;
 694     }
 695     // Find [start:end] clusters for the text
 696     Cluster* start = nullptr;
 697     Cluster* end = nullptr;
 698     do {
 699         bool found;
 700         ClusterIndex startIndex;
 701         ClusterIndex endIndex;
 702         std::tie(found, startIndex, endIndex) = run->findLimitingClusters(textRange);
 703         if (!found) {
 704             return result;
 705         }
 706         start = &fOwner->cluster(startIndex);
 707         end = &fOwner->cluster(endIndex);
 708
 709         if (!limitToGraphemes) {
 710             break;
 711         }
 712
 713         // Update textRange by cluster edges
 714         if (run->leftToRight()) {
 715             if (textRange.start != start->textRange().start) {
 716                 textRange.start = start->textRange().end;
 717             }
 718             textRange.end = end->textRange().end;
 719         } else {
 720             if (textRange.start != end->textRange().start) {
 721                 textRange.start = end->textRange().end;
 722             }
 723             textRange.end = start->textRange().end;
 724         }
 725
 726         std::tie(found, startIndex, endIndex) = run->findLimitingGraphemes(textRange);
 727         if (startIndex == textRange.start && endIndex == textRange.end) {
 728             break;
 729         }
 730
 731         // Some clusters are inside graphemes and we need to adjust them
 732         //SkDebugf("Correct range: [%d:%d) -> [%d:%d)\n", textRange.start, textRange.end, startIndex, endIndex);
 733         textRange.start = startIndex;
 734         textRange.end = endIndex;
 735
 736         // Move the start until it's on the grapheme edge (and glypheme, too)
 737     } while (true);
 738
 739     result.pos = start->startPos();
 740     result.size = (end->isHardBreak() ? end->startPos() : end->endPos()) - start->startPos();
 741
 742     auto textStartInRun = run->positionX(start->startPos());
 743     auto textStartInLine = runOffsetInLine + textOffsetInRunInLine;
 744 /*
 745     if (!run->fJustificationShifts.empty()) {
 746         SkDebugf("Justification for [%d:%d)\n", textRange.start, textRange.end);
 747         for (auto i = result.pos; i < result.pos + result.size; ++i) {
 748             auto j = run->fJustificationShifts[i];
 749             SkDebugf("[%d] = %f %f\n", i, j.fX, j.fY);
 750         }
 751     }
 752 */
 753     // Calculate the clipping rectangle for the text with cluster edges
 754     // There are 2 cases:
 755     // EOL (when we expect the last cluster clipped without any spaces)
 756     // Anything else (when we want the cluster width contain all the spaces -
 757     // coming from letter spacing or word spacing or justification)
 758     result.clip =
 759             SkRect::MakeXYWH(0,
 760                              sizes().runTop(run, this->fAscentStyle),
 761                              run->calculateWidth(result.pos, result.pos + result.size, false),
 762                              run->calculateHeight(this->fAscentStyle,this->fDescentStyle));
 763
 764     // Correct the width in case the text edges don't match clusters
 765     // TODO: This is where we get smart about selecting a part of a cluster
 766     //  by shaping each grapheme separately and then use the result sizes
 767     //  to calculate the proportions
 768     auto leftCorrection = start->sizeToChar(textRange.start);
 769     auto rightCorrection = end->sizeFromChar(textRange.end - 1);
 770     result.clip.fLeft += leftCorrection;
 771     result.clip.fRight -= rightCorrection;
 772     result.clippingNeeded = leftCorrection != 0 || rightCorrection != 0;
 773
 774     textStartInLine -= leftCorrection;
 775     result.clip.offset(textStartInLine, 0);
 776
 777     if (compareRound(result.clip.fRight, fAdvance.fX) > 0 && !includeGhostSpaces) {
 778         // There are few cases when we need it.
 779         // The most important one: we measure the text with spaces at the end (or at the beginning in RTL)
 780         // and we should ignore these spaces
 781         if (run->leftToRight()) {
 782             // We only use this member for LTR
 783             result.fExcludedTrailingSpaces = std::max(result.clip.fRight - fAdvance.fX, 0.0f);
 784             result.clippingNeeded = true;
 785             result.clip.fRight = fAdvance.fX;
 786         }
 787     }
 788
 789     if (result.clip.width() < 0) {
 790         // Weird situation when glyph offsets move the glyph to the left
 791         // (happens with zalgo texts, for instance)
 792         result.clip.fRight = result.clip.fLeft;
 793     }
 794
 795     // The text must be aligned with the lineOffset
 796     result.fTextShift = textStartInLine - textStartInRun;
 797
 798     return result;
 799 }
 800
 801 void TextLine::iterateThroughClustersInGlyphsOrder(bool reversed,
 802                                                    bool includeGhosts,
 803                                                    const ClustersVisitor& visitor) const {
 804     // Walk through the clusters in the logical order (or reverse)
 805     SkSpan<const size_t> runs(fRunsInVisualOrder.data(), fRunsInVisualOrder.size());
 806     bool ignore = false;
 807     directional_for_each(runs, !reversed, [&](decltype(runs[0]) r) {
 808         if (ignore) return;
 809         auto run = this->fOwner->run(r);
 810         auto trimmedRange = fClusterRange.intersection(run.clusterRange());
 811         auto trailedRange = fGhostClusterRange.intersection(run.clusterRange());
 812         SkASSERT(trimmedRange.start == trailedRange.start);
 813
 814         auto trailed = fOwner->clusters(trailedRange);
 815         auto trimmed = fOwner->clusters(trimmedRange);
 816         directional_for_each(trailed, reversed != run.leftToRight(), [&](Cluster& cluster) {
 817             if (ignore) return;
 818             bool ghost =  &cluster >= trimmed.end();
 819             if (!includeGhosts && ghost) {
 820                 return;
 821             }
 822             if (!visitor(&cluster, ghost)) {
 823                 ignore = true;
 824                 return;
 825             }
 826         });
 827     });
 828 }
 829
 830 SkScalar TextLine::iterateThroughSingleRunByStyles(const Run* run,
 831                                                    SkScalar runOffset,
 832                                                    TextRange textRange,
 833                                                    StyleType styleType,
 834                                                    const RunStyleVisitor& visitor) const {
 835
 836     if (run->fEllipsis) {
 837         // Extra efforts to get the ellipsis text style
 838         ClipContext clipContext = this->measureTextInsideOneRun(run->textRange(), run, runOffset,
 839                                                                 0, false, true);
 840         TextRange testRange(run->fClusterStart, run->fClusterStart + run->textRange().width());
 841         for (BlockIndex index = fBlockRange.start; index < fBlockRange.end; ++index) {
 842            auto block = fOwner->styles().begin() + index;
 843            auto intersect = intersected(block->fRange, testRange);
 844            if (intersect.width() > 0) {
 845                visitor(testRange, block->fStyle, clipContext);
 846                return run->advance().fX;
 847            }
 848         }
 849         SkASSERT(false);
 850     }
 851
 852     if (styleType == StyleType::kNone) {
 853         ClipContext clipContext = this->measureTextInsideOneRun(textRange, run, runOffset,
 854                                                                 0, false, true);
 855         if (clipContext.clip.height() > 0) {
 856             visitor(textRange, TextStyle(), clipContext);
 857             return clipContext.clip.width();
 858         } else {
 859             return 0;
 860         }
 861     }
 862
 863     TextIndex start = EMPTY_INDEX;
 864     size_t size = 0;
 865     const TextStyle* prevStyle = nullptr;
 866     SkScalar textOffsetInRun = 0;
 867
 868     const BlockIndex blockRangeSize = fBlockRange.end - fBlockRange.start;
 869     for (BlockIndex index = 0; index <= blockRangeSize; ++index) {
 870
 871         TextRange intersect;
 872         TextStyle* style = nullptr;
 873         if (index < blockRangeSize) {
 874             auto block = fOwner->styles().begin() +
 875                  (run->leftToRight() ? fBlockRange.start + index : fBlockRange.end - index - 1);
 876
 877             // Get the text
 878             intersect = intersected(block->fRange, textRange);
 879             if (intersect.width() == 0) {
 880                 if (start == EMPTY_INDEX) {
 881                     // This style is not applicable to the text yet
 882                     continue;
 883                 } else {
 884                     // We have found all the good styles already
 885                     // but we need to process the last one of them
 886                     intersect = TextRange(start, start + size);
 887                     index = fBlockRange.end;
 888                 }
 889             } else {
 890                 // Get the style
 891                 style = &block->fStyle;
 892                 if (start != EMPTY_INDEX && style->matchOneAttribute(styleType, *prevStyle)) {
 893                     size += intersect.width();
 894                     // RTL text intervals move backward
 895                     start = std::min(intersect.start, start);
 896                     continue;
 897                 } else if (start == EMPTY_INDEX ) {
 898                     // First time only
 899                     prevStyle = style;
 900                     size = intersect.width();
 901                     start = intersect.start;
 902                     continue;
 903                 }
 904             }
 905         } else if (prevStyle != nullptr) {
 906             // This is the last style
 907         } else {
 908             break;
 909         }
 910
 911         // We have the style and the text
 912         auto runStyleTextRange = TextRange(start, start + size);
 913         // Measure the text
 914         ClipContext clipContext = this->measureTextInsideOneRun(runStyleTextRange, run, runOffset,
 915                                                                 textOffsetInRun, false, true);
 916         textOffsetInRun += clipContext.clip.width();
 917         if (clipContext.clip.height() == 0) {
 918             continue;
 919         }
 920         visitor(runStyleTextRange, *prevStyle, clipContext);
 921
 922         // Start all over again
 923         prevStyle = style;
 924         start = intersect.start;
 925         size = intersect.width();
 926     }
 927     return textOffsetInRun;
 928 }
 929
 930 void TextLine::iterateThroughVisualRuns(bool includingGhostSpaces, const RunVisitor& visitor) const {
 931
 932     // Walk through all the runs that intersect with the line in visual order
 933     SkScalar width = 0;
 934     SkScalar runOffset = 0;
 935     SkScalar totalWidth = 0;
 936     auto textRange = includingGhostSpaces ? this->textWithNewlines() : this->trimmedText();
 937
 938     if (this->ellipsis() != nullptr && !this->ellipsis()->leftToRight()) {
 939         runOffset = this->ellipsis()->offset().fX;
 940         if (visitor(ellipsis(), runOffset, ellipsis()->textRange(), &width)) {
 941         }
 942     }
 943
 944     for (auto& runIndex : fRunsInVisualOrder) {
 945
 946         const auto run = &this->fOwner->run(runIndex);
 947         auto lineIntersection = intersected(run->textRange(), textRange);
 948         if (lineIntersection.width() == 0 && this->width() != 0) {
 949             // TODO: deal with empty runs in a better way
 950             continue;
 951         }
 952         if (!run->leftToRight() && runOffset == 0 && includingGhostSpaces) {
 953             // runOffset does not take in account a possibility
 954             // that RTL run could start before the line (trailing spaces)
 955             // so we need to do runOffset -= "trailing whitespaces length"
 956             TextRange whitespaces = intersected(
 957                     TextRange(fTextExcludingSpaces.end, fTextIncludingNewlines.end), run->fTextRange);
 958             if (whitespaces.width() > 0) {
 959                 auto whitespacesLen = measureTextInsideOneRun(whitespaces, run, runOffset, 0, true, false).clip.width();
 960                 runOffset -= whitespacesLen;
 961             }
 962         }
 963         runOffset += width;
 964         totalWidth += width;
 965         if (!visitor(run, runOffset, lineIntersection, &width)) {
 966             return;
 967         }
 968     }
 969
 970     runOffset += width;
 971     totalWidth += width;
 972
 973     if (this->ellipsis() != nullptr && this->ellipsis()->leftToRight()) {
 974         if (visitor(ellipsis(), runOffset, ellipsis()->textRange(), &width)) {
 975             totalWidth += width;
 976         }
 977     }
 978
 979     // This is a very important assert!
 980     // It asserts that 2 different ways of calculation come with the same results
 981     if (!includingGhostSpaces && compareRound(totalWidth, this->width()) != 0) {
 982         SkDebugf("ASSERT: %f != %f\n", totalWidth, this->width());
 983         SkASSERT(false);
 984     }
 985 }
 986
 987 SkVector TextLine::offset() const {
 988     return fOffset + SkVector::Make(fShift, 0);
 989 }
 990
 991 LineMetrics TextLine::getMetrics() const {
 992     LineMetrics result;
 993
 994     // Fill out the metrics
 995     fOwner->ensureUTF16Mapping();
 996     result.fStartIndex = fOwner->getUTF16Index(fTextExcludingSpaces.start);
 997     result.fEndExcludingWhitespaces = fOwner->getUTF16Index(fTextExcludingSpaces.end);
 998     result.fEndIndex = fOwner->getUTF16Index(fText.end);
 999     result.fEndIncludingNewline = fOwner->getUTF16Index(fTextIncludingNewlines.end);
1000     result.fHardBreak = endsWithHardLineBreak();
1001     result.fAscent = - fMaxRunMetrics.ascent();
1002     result.fDescent = fMaxRunMetrics.descent();
1003     result.fUnscaledAscent = - fMaxRunMetrics.ascent(); // TODO: implement
1004     result.fHeight = littleRound(fAdvance.fY);
1005     result.fWidth = littleRound(fAdvance.fX);
1006     result.fLeft = this->offset().fX;
1007     // This is Flutter definition of a baseline
1008     result.fBaseline = this->offset().fY + this->height() - this->sizes().descent();
1009     result.fLineNumber = this - fOwner->lines().begin();
1010
1011     // Fill out the style parts
1012     this->iterateThroughVisualRuns(false,
1013         [this, &result]
1014         (const Run* run, SkScalar runOffsetInLine, TextRange textRange, SkScalar* runWidthInLine) {
1015         if (run->placeholderStyle() != nullptr) {
1016             *runWidthInLine = run->advance().fX;
1017             return true;
1018         }
1019         *runWidthInLine = this->iterateThroughSingleRunByStyles(
1020         run, runOffsetInLine, textRange, StyleType::kForeground,
1021         [&result, &run](TextRange textRange, const TextStyle& style, const ClipContext& context) {
1022             SkFontMetrics fontMetrics;
1023             run->fFont.getMetrics(&fontMetrics);
1024             StyleMetrics styleMetrics(&style, fontMetrics);
1025             result.fLineMetrics.emplace(textRange.start, styleMetrics);
1026         });
1027         return true;
1028     });
1029
1030     return result;
1031 }
1032
1033 bool TextLine::isFirstLine() {
1034     return this == &fOwner->lines().front();
1035 }
1036
1037 bool TextLine::isLastLine() {
1038     return this == &fOwner->lines().back();
1039 }
1040
1041 bool TextLine::endsWithHardLineBreak() const {
1042     // TODO: For some reason Flutter imagines a hard line break at the end of the last line.
1043     //  To be removed...
1044     return fOwner->cluster(fGhostClusterRange.end - 1).isHardBreak() ||
1045            fEllipsis != nullptr ||
1046            fGhostClusterRange.end == fOwner->clusters().size() - 1;
1047 }
1048
1049 void TextLine::getRectsForRange(TextRange textRange0,
1050                                 RectHeightStyle rectHeightStyle,
1051                                 RectWidthStyle rectWidthStyle,
1052                                 std::vector<TextBox>& boxes)
1053 {
1054     const Run* lastRun = nullptr;
1055     auto startBox = boxes.size();
1056     this->iterateThroughVisualRuns(true,
1057         [textRange0, rectHeightStyle, rectWidthStyle, &boxes, &lastRun, startBox, this]
1058         (const Run* run, SkScalar runOffsetInLine, TextRange textRange, SkScalar* runWidthInLine) {
1059         *runWidthInLine = this->iterateThroughSingleRunByStyles(
1060         run, runOffsetInLine, textRange, StyleType::kNone,
1061         [run, runOffsetInLine, textRange0, rectHeightStyle, rectWidthStyle, &boxes, &lastRun, startBox, this]
1062         (TextRange textRange, const TextStyle& style, const TextLine::ClipContext& lineContext) {
1063
1064             auto intersect = textRange * textRange0;
1065             if (intersect.empty()) {
1066                 return true;
1067             }
1068
1069             auto paragraphStyle = fOwner->paragraphStyle();
1070
1071             // Found a run that intersects with the text
1072             auto context = this->measureTextInsideOneRun(intersect, run, runOffsetInLine, 0, true, true);
1073             SkRect clip = context.clip;
1074             clip.offset(lineContext.fTextShift - context.fTextShift, 0);
1075
1076             switch (rectHeightStyle) {
1077                 case RectHeightStyle::kMax:
1078                     // TODO: Change it once flutter rolls into google3
1079                     //  (probably will break things if changed before)
1080                     clip.fBottom = this->height();
1081                     clip.fTop = this->sizes().delta();
1082                     break;
1083                 case RectHeightStyle::kIncludeLineSpacingTop: {
1084                     clip.fBottom = this->height();
1085                     clip.fTop = this->sizes().delta();
1086                     auto verticalShift = this->sizes().rawAscent() - this->sizes().ascent();
1087                     if (isFirstLine()) {
1088                         clip.fTop += verticalShift;
1089                     }
1090                     break;
1091                 }
1092                 case RectHeightStyle::kIncludeLineSpacingMiddle: {
1093                     clip.fBottom = this->height();
1094                     clip.fTop = this->sizes().delta();
1095                     auto verticalShift = this->sizes().rawAscent() - this->sizes().ascent();
1096                     clip.offset(0, verticalShift / 2.0);
1097                     if (isFirstLine()) {
1098                         clip.fTop += verticalShift / 2.0;
1099                     }
1100                     if (isLastLine()) {
1101                         clip.fBottom -= verticalShift / 2.0;
1102                     }
1103                     break;
1104                  }
1105                 case RectHeightStyle::kIncludeLineSpacingBottom: {
1106                     clip.fBottom = this->height();
1107                     clip.fTop = this->sizes().delta();
1108                     auto verticalShift = this->sizes().rawAscent() - this->sizes().ascent();
1109                     clip.offset(0, verticalShift);
1110                     if (isLastLine()) {
1111                         clip.fBottom -= verticalShift;
1112                     }
1113                     break;
1114                 }
1115                 case RectHeightStyle::kStrut: {
1116                     const auto& strutStyle = paragraphStyle.getStrutStyle();
1117                     if (strutStyle.getStrutEnabled()
1118                         && strutStyle.getFontSize() > 0) {
1119                         auto strutMetrics = fOwner->strutMetrics();
1120                         auto top = this->baseline();
1121                         clip.fTop = top + strutMetrics.ascent();
1122                         clip.fBottom = top + strutMetrics.descent();
1123                     }
1124                 }
1125                 break;
1126                 case RectHeightStyle::kTight: {
1127                     if (run->fHeightMultiplier <= 0) {
1128                         break;
1129                     }
1130                     const auto effectiveBaseline = this->baseline() + this->sizes().delta();
1131                     clip.fTop = effectiveBaseline + run->ascent();
1132                     clip.fBottom = effectiveBaseline + run->descent();
1133                 }
1134                 break;
1135                 default:
1136                     SkASSERT(false);
1137                 break;
1138             }
1139
1140             // Separate trailing spaces and move them in the default order of the paragraph
1141             // in case the run order and the paragraph order don't match
1142             SkRect trailingSpaces = SkRect::MakeEmpty();
1143             if (this->trimmedText().end <this->textWithNewlines().end && // Line has trailing space
1144                 this->textWithNewlines().end == intersect.end &&         // Range is at the end of the line
1145                 this->trimmedText().end > intersect.start)               // Range has more than just spaces
1146             {
1147                 auto delta = this->spacesWidth();
1148                 trailingSpaces = SkRect::MakeXYWH(0, 0, 0, 0);
1149                 // There are trailing spaces in this run
1150                 if (paragraphStyle.getTextAlign() == TextAlign::kJustify && isLastLine())
1151                 {
1152                     // TODO: this is just a patch. Make it right later (when it's clear what and how)
1153                     trailingSpaces = clip;
1154                     if(run->leftToRight()) {
1155                         trailingSpaces.fLeft = this->width();
1156                         clip.fRight = this->width();
1157                     } else {
1158                         trailingSpaces.fRight = 0;
1159                         clip.fLeft = 0;
1160                     }
1161                 } else if (paragraphStyle.getTextDirection() == TextDirection::kRtl &&
1162                     !run->leftToRight())
1163                 {
1164                     // Split
1165                     trailingSpaces = clip;
1166                     trailingSpaces.fLeft = - delta;
1167                     trailingSpaces.fRight = 0;
1168                     clip.fLeft += delta;
1169                 } else if (paragraphStyle.getTextDirection() == TextDirection::kLtr &&
1170                     run->leftToRight())
1171                 {
1172                     // Split
1173                     trailingSpaces = clip;
1174                     trailingSpaces.fLeft = this->width();
1175                     trailingSpaces.fRight = trailingSpaces.fLeft + delta;
1176                     clip.fRight -= delta;
1177                 }
1178             }
1179
1180             clip.offset(this->offset());
1181             if (trailingSpaces.width() > 0) {
1182                 trailingSpaces.offset(this->offset());
1183             }
1184
1185             // Check if we can merge two boxes instead of adding a new one
1186             auto merge = [&lastRun, &context, &boxes](SkRect clip) {
1187                 bool mergedBoxes = false;
1188                 if (!boxes.empty() &&
1189                     lastRun != nullptr &&
1190                     context.run->leftToRight() == lastRun->leftToRight() &&
1191                     lastRun->placeholderStyle() == nullptr &&
1192                     context.run->placeholderStyle() == nullptr &&
1193                     nearlyEqual(lastRun->heightMultiplier(),
1194                                 context.run->heightMultiplier()) &&
1195                     lastRun->font() == context.run->font())
1196                 {
1197                     auto& lastBox = boxes.back();
1198                     if (nearlyEqual(lastBox.rect.fTop, clip.fTop) &&
1199                         nearlyEqual(lastBox.rect.fBottom, clip.fBottom) &&
1200                             (nearlyEqual(lastBox.rect.fLeft, clip.fRight) ||
1201                              nearlyEqual(lastBox.rect.fRight, clip.fLeft)))
1202                     {
1203                         lastBox.rect.fLeft = std::min(lastBox.rect.fLeft, clip.fLeft);
1204                         lastBox.rect.fRight = std::max(lastBox.rect.fRight, clip.fRight);
1205                         mergedBoxes = true;
1206                     }
1207                 }
1208                 lastRun = context.run;
1209                 return mergedBoxes;
1210             };
1211
1212             if (!merge(clip)) {
1213                 boxes.emplace_back(clip, context.run->getTextDirection());
1214             }
1215             if (!nearlyZero(trailingSpaces.width()) && !merge(trailingSpaces)) {
1216                 boxes.emplace_back(trailingSpaces, paragraphStyle.getTextDirection());
1217             }
1218
1219             if (rectWidthStyle == RectWidthStyle::kMax && !isLastLine()) {
1220                 // Align the very left/right box horizontally
1221                 auto lineStart = this->offset().fX;
1222                 auto lineEnd = this->offset().fX + this->width();
1223                 auto left = boxes[startBox];
1224                 auto right = boxes.back();
1225                 if (left.rect.fLeft > lineStart && left.direction == TextDirection::kRtl) {
1226                     left.rect.fRight = left.rect.fLeft;
1227                     left.rect.fLeft = 0;
1228                     boxes.insert(boxes.begin() + startBox + 1, left);
1229                 }
1230                 if (right.direction == TextDirection::kLtr &&
1231                     right.rect.fRight >= lineEnd &&
1232                     right.rect.fRight < fOwner->widthWithTrailingSpaces()) {
1233                     right.rect.fLeft = right.rect.fRight;
1234                     right.rect.fRight = fOwner->widthWithTrailingSpaces();
1235                     boxes.emplace_back(right);
1236                 }
1237             }
1238
1239             return true;
1240         });
1241         return true;
1242     });
1243     for (auto& r : boxes) {
1244         r.rect.fLeft = littleRound(r.rect.fLeft);
1245         r.rect.fRight = littleRound(r.rect.fRight);
1246         r.rect.fTop = littleRound(r.rect.fTop);
1247         r.rect.fBottom = littleRound(r.rect.fBottom);
1248     }
1249 }
1250
1251 PositionWithAffinity TextLine::getGlyphPositionAtCoordinate(SkScalar dx) {
1252
1253     if (SkScalarNearlyZero(this->width()) && SkScalarNearlyZero(this->spacesWidth())) {
1254         // TODO: this is one of the flutter changes that have to go away eventually
1255         //  Empty line is a special case in txtlib (but only when there are no spaces, too)
1256         auto utf16Index = fOwner->getUTF16Index(this->fTextExcludingSpaces.end);
1257         return { SkToS32(utf16Index) , kDownstream };
1258     }
1259
1260     PositionWithAffinity result(0, Affinity::kDownstream);
1261     this->iterateThroughVisualRuns(true,
1262         [this, dx, &result]
1263         (const Run* run, SkScalar runOffsetInLine, TextRange textRange, SkScalar* runWidthInLine) {
1264             bool keepLooking = true;
1265             *runWidthInLine = this->iterateThroughSingleRunByStyles(
1266             run, runOffsetInLine, textRange, StyleType::kNone,
1267             [this, run, dx, &result, &keepLooking]
1268             (TextRange textRange, const TextStyle& style, const TextLine::ClipContext& context0) {
1269
1270                 SkScalar offsetX = this->offset().fX;
1271                 ClipContext context = context0;
1272
1273                 // Correct the clip size because libtxt counts trailing spaces
1274                 if (run->leftToRight()) {
1275                     context.clip.fRight += context.fExcludedTrailingSpaces; // extending clip to the right
1276                 } else {
1277                     // Clip starts from 0; we cannot extend it to the left from that
1278                 }
1279                 // This patch will help us to avoid a floating point error
1280                 if (SkScalarNearlyEqual(context.clip.fRight, dx - offsetX, 0.01f)) {
1281                     context.clip.fRight = dx - offsetX;
1282                 }
1283
1284                 if (dx <= context.clip.fLeft + offsetX) {
1285                     // All the other runs are placed right of this one
1286                     auto utf16Index = fOwner->getUTF16Index(context.run->globalClusterIndex(context.pos));
1287                     if (run->leftToRight()) {
1288                         result = { SkToS32(utf16Index), kDownstream};
1289                         keepLooking = false;
1290                     } else {
1291                         result = { SkToS32(utf16Index), kDownstream};
1292                         // If we haven't reached the end of the run we need to keep looking
1293                         keepLooking = context.pos != 0;
1294                     }
1295                     // For RTL we go another way
1296                     return !run->leftToRight();
1297                 }
1298
1299                 if (dx >= context.clip.fRight + offsetX) {
1300                     // We have to keep looking ; just in case keep the last one as the closest
1301                     auto utf16Index = fOwner->getUTF16Index(context.run->globalClusterIndex(context.pos + context.size));
1302                     if (run->leftToRight()) {
1303                         result = {SkToS32(utf16Index), kUpstream};
1304                     } else {
1305                         result = {SkToS32(utf16Index), kDownstream};
1306                     }
1307                     // For RTL we go another way
1308                     return run->leftToRight();
1309                 }
1310
1311                 // So we found the run that contains our coordinates
1312                 // Find the glyph position in the run that is the closest left of our point
1313                 // TODO: binary search
1314                 size_t found = context.pos;
1315                 for (size_t index = context.pos; index < context.pos + context.size; ++index) {
1316                     // TODO: this rounding is done to match Flutter tests. Must be removed..
1317                     auto end = littleRound(context.run->positionX(index) + context.fTextShift + offsetX);
1318                     if (end > dx) {
1319                         break;
1320                     } else if (end == dx && !context.run->leftToRight()) {
1321                         // When we move RTL variable end points to the beginning of the code point which is included
1322                         found = index;
1323                         break;
1324                     }
1325                     found = index;
1326                 }
1327
1328                 SkScalar glyphemePosLeft = context.run->positionX(found) + context.fTextShift + offsetX;
1329                 SkScalar glyphemePosWidth = context.run->positionX(found + 1) - context.run->positionX(found);
1330
1331                 // Find the grapheme range that contains the point
1332                 auto clusterIndex8 = context.run->globalClusterIndex(found);
1333                 auto clusterEnd8 = context.run->globalClusterIndex(found + 1);
1334
1335                 SkScalar center = glyphemePosLeft + glyphemePosWidth / 2;
1336                 if ((dx < center) == context.run->leftToRight()) {
1337                     size_t utf16Index = context.run->leftToRight()
1338                                                 ? fOwner->getUTF16Index(clusterIndex8)
1339                                                 : fOwner->getUTF16Index(clusterEnd8) + 1;
1340                     result = { SkToS32(utf16Index), kDownstream };
1341                 } else {
1342                     size_t utf16Index = context.run->leftToRight()
1343                                                 ? fOwner->getUTF16Index(clusterEnd8)
1344                                                 : fOwner->getUTF16Index(clusterIndex8) + 1;
1345                     result = { SkToS32(utf16Index), kUpstream };
1346                 }
1347
1348                 return keepLooking = false;
1349
1350             });
1351             return keepLooking;
1352         }
1353     );
1354     return result;
1355 }
1356
1357 void TextLine::getRectsForPlaceholders(std::vector<TextBox>& boxes) {
1358     this->iterateThroughVisualRuns(
1359         true,
1360         [&boxes, this](const Run* run, SkScalar runOffset, TextRange textRange,
1361                         SkScalar* width) {
1362             auto context = this->measureTextInsideOneRun(textRange, run, runOffset, 0, true, false);
1363             *width = context.clip.width();
1364
1365             if (textRange.width() == 0) {
1366                 return true;
1367             }
1368             if (!run->isPlaceholder()) {
1369                 return true;
1370             }
1371
1372             SkRect clip = context.clip;
1373             clip.offset(this->offset());
1374
1375             clip.fLeft = littleRound(clip.fLeft);
1376             clip.fRight = littleRound(clip.fRight);
1377             clip.fTop = littleRound(clip.fTop);
1378             clip.fBottom = littleRound(clip.fBottom);
1379             boxes.emplace_back(clip, run->getTextDirection());
1380             return true;
1381         });
1382 }
1383 }  // namespace textlayout
1384 }  // namespace skia