submodule/skia/modules/skottie/src/text/SkottieShaper.cpp

   1 /*
   2  * Copyright 2019 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #include "modules/skottie/src/text/SkottieShaper.h"
   9
  10 #include "include/core/SkFontMetrics.h"
  11 #include "include/core/SkFontMgr.h"
  12 #include "include/core/SkTextBlob.h"
  13 #include "include/private/SkTPin.h"
  14 #include "include/private/SkTemplates.h"
  15 #include "modules/skshaper/include/SkShaper.h"
  16 #include "modules/skunicode/include/SkUnicode.h"
  17 #include "src/core/SkTLazy.h"
  18 #include "src/core/SkTextBlobPriv.h"
  19 #include "src/utils/SkUTF.h"
  20
  21 #include <algorithm>
  22 #include <limits.h>
  23 #include <numeric>
  24
  25 namespace skottie {
  26 namespace {
  27
  28 SkRect ComputeBlobBounds(const sk_sp<SkTextBlob>& blob) {
  29     auto bounds = SkRect::MakeEmpty();
  30
  31     if (!blob) {
  32         return bounds;
  33     }
  34
  35     SkAutoSTArray<16, SkRect> glyphBounds;
  36
  37     for (SkTextBlobRunIterator it(blob.get()); !it.done(); it.next()) {
  38         glyphBounds.reset(SkToInt(it.glyphCount()));
  39         it.font().getBounds(it.glyphs(), it.glyphCount(), glyphBounds.get(), nullptr);
  40
  41         SkASSERT(it.positioning() == SkTextBlobRunIterator::kFull_Positioning);
  42         for (uint32_t i = 0; i < it.glyphCount(); ++i) {
  43             bounds.join(glyphBounds[i].makeOffset(it.pos()[i * 2    ],
  44                                                   it.pos()[i * 2 + 1]));
  45         }
  46     }
  47
  48     return bounds;
  49 }
  50
  51 static bool is_whitespace(char c) {
  52     // TODO: we've been getting away with this simple heuristic,
  53     // but ideally we should use SkUicode::isWhiteSpace().
  54     return c == ' ' || c == '\t' || c == '\r' || c == '\n';
  55 };
  56
  57 // Helper for interfacing with SkShaper: buffers shaper-fed runs and performs
  58 // per-line position adjustments (for external line breaking, horizontal alignment, etc).
  59 class BlobMaker final : public SkShaper::RunHandler {
  60 public:
  61     BlobMaker(const Shaper::TextDesc& desc, const SkRect& box, const sk_sp<SkFontMgr>& fontmgr)
  62         : fDesc(desc)
  63         , fBox(box)
  64         , fHAlignFactor(HAlignFactor(fDesc.fHAlign))
  65         , fFont(fDesc.fTypeface, fDesc.fTextSize)
  66         , fShaper(SkShaper::Make(fontmgr)) {
  67         fFont.setHinting(SkFontHinting::kNone);
  68         fFont.setSubpixel(true);
  69         fFont.setLinearMetrics(true);
  70         fFont.setBaselineSnap(false);
  71         fFont.setEdging(SkFont::Edging::kAntiAlias);
  72     }
  73
  74     void beginLine() override {
  75         fLineGlyphs.reset(0);
  76         fLinePos.reset(0);
  77         fLineClusters.reset(0);
  78         fLineRuns.reset();
  79         fLineGlyphCount = 0;
  80
  81         fCurrentPosition = fOffset;
  82         fPendingLineAdvance  = { 0, 0 };
  83
  84         fLastLineDescent = 0;
  85     }
  86
  87     void runInfo(const RunInfo& info) override {
  88         fPendingLineAdvance += info.fAdvance;
  89
  90         SkFontMetrics metrics;
  91         info.fFont.getMetrics(&metrics);
  92         if (!fLineCount) {
  93             fFirstLineAscent = std::min(fFirstLineAscent, metrics.fAscent);
  94         }
  95         fLastLineDescent = std::max(fLastLineDescent, metrics.fDescent);
  96     }
  97
  98     void commitRunInfo() override {}
  99
 100     Buffer runBuffer(const RunInfo& info) override {
 101         const auto run_start_index = fLineGlyphCount;
 102         fLineGlyphCount += info.glyphCount;
 103
 104         fLineGlyphs.realloc(fLineGlyphCount);
 105         fLinePos.realloc(fLineGlyphCount);
 106         fLineClusters.realloc(fLineGlyphCount);
 107         fLineRuns.push_back({info.fFont, info.glyphCount});
 108
 109         SkVector alignmentOffset { fHAlignFactor * (fPendingLineAdvance.x() - fBox.width()), 0 };
 110
 111         return {
 112             fLineGlyphs.get()   + run_start_index,
 113             fLinePos.get()      + run_start_index,
 114             nullptr,
 115             fLineClusters.get() + run_start_index,
 116             fCurrentPosition + alignmentOffset
 117         };
 118     }
 119
 120     void commitRunBuffer(const RunInfo& info) override {
 121         fCurrentPosition += info.fAdvance;
 122     }
 123
 124     void commitLine() override {
 125         fOffset.fY += fDesc.fLineHeight;
 126
 127         // Observed AE handling of whitespace, for alignment purposes:
 128         //
 129         //   - leading whitespace contributes to alignment
 130         //   - trailing whitespace is ignored
 131         //   - auto line breaking retains all separating whitespace on the first line (no artificial
 132         //     leading WS is created).
 133         auto adjust_trailing_whitespace = [this]() {
 134             // For left-alignment, trailing WS doesn't make any difference.
 135             if (fLineRuns.empty() || fDesc.fHAlign == SkTextUtils::Align::kLeft_Align) {
 136                 return;
 137             }
 138
 139             // Technically, trailing whitespace could span multiple runs, but realistically,
 140             // SkShaper has no reason to split it.  Hence we're only checking the last run.
 141             size_t ws_count = 0;
 142             for (size_t i = 0; i < fLineRuns.back().fGlyphCount; ++i) {
 143                 if (is_whitespace(fUTF8[fLineClusters[SkToInt(fLineGlyphCount - i - 1)]])) {
 144                     ++ws_count;
 145                 } else {
 146                     break;
 147                 }
 148             }
 149
 150             // No trailing whitespace.
 151             if (!ws_count) {
 152                 return;
 153             }
 154
 155             // Compute the cumulative whitespace advance.
 156             fAdvanceBuffer.resize(ws_count);
 157             fLineRuns.back().fFont.getWidths(fLineGlyphs.data() + fLineGlyphCount - ws_count,
 158                                              SkToInt(ws_count), fAdvanceBuffer.data(), nullptr);
 159
 160             const auto ws_advance = std::accumulate(fAdvanceBuffer.begin(),
 161                                                     fAdvanceBuffer.end(),
 162                                                     0.0f);
 163
 164             // Offset needed to compensate for whitespace.
 165             const auto offset = ws_advance*-fHAlignFactor;
 166
 167             // Shift the whole line horizontally by the computed offset.
 168             std::transform(fLinePos.data(),
 169                            fLinePos.data() + fLineGlyphCount,
 170                            fLinePos.data(),
 171                            [&offset](SkPoint pos) { return SkPoint{pos.fX + offset, pos.fY}; });
 172         };
 173
 174         adjust_trailing_whitespace();
 175
 176         const auto commit_proc = (fDesc.fFlags & Shaper::Flags::kFragmentGlyphs)
 177             ? &BlobMaker::commitFragementedRun
 178             : &BlobMaker::commitConsolidatedRun;
 179
 180         size_t run_offset = 0;
 181         for (const auto& rec : fLineRuns) {
 182             SkASSERT(run_offset < fLineGlyphCount);
 183             (this->*commit_proc)(rec,
 184                         fLineGlyphs.get()   + run_offset,
 185                         fLinePos.get()      + run_offset,
 186                         fLineClusters.get() + run_offset,
 187                         fLineCount);
 188             run_offset += rec.fGlyphCount;
 189         }
 190
 191         fLineCount++;
 192     }
 193
 194     Shaper::Result finalize(SkSize* shaped_size) {
 195         if (!(fDesc.fFlags & Shaper::Flags::kFragmentGlyphs)) {
 196             // All glyphs are pending in a single blob.
 197             SkASSERT(fResult.fFragments.empty());
 198             fResult.fFragments.reserve(1);
 199             fResult.fFragments.push_back({fBuilder.make(), {fBox.x(), fBox.y()}, 0, 0, 0, false});
 200         }
 201
 202         const auto ascent = this->ascent();
 203
 204         // For visual VAlign modes, we use a hybrid extent box computed as the union of
 205         // actual visual bounds and the vertical typographical extent.
 206         //
 207         // This ensures that
 208         //
 209         //   a) text doesn't visually overflow the alignment boundaries
 210         //
 211         //   b) leading/trailing empty lines are still taken into account for alignment purposes
 212
 213         auto extent_box = [&]() {
 214             auto box = fResult.computeVisualBounds();
 215
 216             // By default, first line is vertically-aligned on a baseline of 0.
 217             // The typographical height considered for vertical alignment is the distance between
 218             // the first line top (ascent) to the last line bottom (descent).
 219             const auto typographical_top    = fBox.fTop + ascent,
 220                        typographical_bottom = fBox.fTop + fLastLineDescent + fDesc.fLineHeight *
 221                                                            (fLineCount > 0 ? fLineCount - 1 : 0ul);
 222
 223             box.fTop    = std::min(box.fTop,    typographical_top);
 224             box.fBottom = std::max(box.fBottom, typographical_bottom);
 225
 226             return box;
 227         };
 228
 229         // Only compute the extent box when needed.
 230         SkTLazy<SkRect> ebox;
 231
 232         // Vertical adjustments.
 233         float v_offset = -fDesc.fLineShift;
 234
 235         switch (fDesc.fVAlign) {
 236         case Shaper::VAlign::kTop:
 237             v_offset -= ascent;
 238             break;
 239         case Shaper::VAlign::kTopBaseline:
 240             // Default behavior.
 241             break;
 242         case Shaper::VAlign::kVisualTop:
 243             ebox.init(extent_box());
 244             v_offset += fBox.fTop - ebox->fTop;
 245             break;
 246         case Shaper::VAlign::kVisualCenter:
 247             ebox.init(extent_box());
 248             v_offset += fBox.centerY() - ebox->centerY();
 249             break;
 250         case Shaper::VAlign::kVisualBottom:
 251             ebox.init(extent_box());
 252             v_offset += fBox.fBottom - ebox->fBottom;
 253             break;
 254         }
 255
 256         if (shaped_size) {
 257             if (!ebox.isValid()) {
 258                 ebox.init(extent_box());
 259             }
 260             *shaped_size = SkSize::Make(ebox->width(), ebox->height());
 261         }
 262
 263         if (v_offset) {
 264             for (auto& fragment : fResult.fFragments) {
 265                 fragment.fPos.fY += v_offset;
 266             }
 267         }
 268
 269         return std::move(fResult);
 270     }
 271
 272     void shapeLine(const char* start, const char* end) {
 273         if (!fShaper) {
 274             return;
 275         }
 276
 277         SkASSERT(start <= end);
 278         if (start == end) {
 279             // SkShaper doesn't care for empty lines.
 280             this->beginLine();
 281             this->commitLine();
 282             return;
 283         }
 284
 285         // In default paragraph mode (VAlign::kTop), AE clips out lines when the baseline
 286         // goes below the box lower edge.
 287         if (fDesc.fVAlign == Shaper::VAlign::kTop) {
 288             // fOffset is relative to the first line baseline.
 289             const auto max_offset = fBox.height() + this->ascent(); // NB: ascent is negative
 290             if (fOffset.y() > max_offset) {
 291                 return;
 292             }
 293         }
 294
 295         const auto shape_width = fDesc.fLinebreak == Shaper::LinebreakPolicy::kExplicit
 296                                     ? SK_ScalarMax
 297                                     : fBox.width();
 298         const auto shape_ltr   = fDesc.fDirection == Shaper::Direction::kLTR;
 299
 300         fUTF8 = start;
 301         fShaper->shape(start, SkToSizeT(end - start), fFont, shape_ltr, shape_width, this);
 302         fUTF8 = nullptr;
 303     }
 304
 305 private:
 306     struct RunRec {
 307         SkFont fFont;
 308         size_t fGlyphCount;
 309     };
 310
 311     void commitFragementedRun(const RunRec& rec,
 312                               const SkGlyphID* glyphs,
 313                               const SkPoint* pos,
 314                               const uint32_t* clusters,
 315                               uint32_t line_index) {
 316         float ascent = 0;
 317
 318         if (fDesc.fFlags & Shaper::Flags::kTrackFragmentAdvanceAscent) {
 319             SkFontMetrics metrics;
 320             rec.fFont.getMetrics(&metrics);
 321             ascent = metrics.fAscent;
 322
 323             // Note: we use per-glyph advances for anchoring, but it's unclear whether this
 324             // is exactly the same as AE.  E.g. are 'acute' glyphs anchored separately for fonts
 325             // in which they're distinct?
 326             fAdvanceBuffer.resize(rec.fGlyphCount);
 327             fFont.getWidths(glyphs, SkToInt(rec.fGlyphCount), fAdvanceBuffer.data());
 328         }
 329
 330         // In fragmented mode we immediately push the glyphs to fResult,
 331         // one fragment (blob) per glyph.  Glyph positioning is externalized
 332         // (positions returned in Fragment::fPos).
 333         for (size_t i = 0; i < rec.fGlyphCount; ++i) {
 334             const auto& blob_buffer = fBuilder.allocRunPos(rec.fFont, 1);
 335             blob_buffer.glyphs[0] = glyphs[i];
 336             blob_buffer.pos[0] = blob_buffer.pos[1] = 0;
 337
 338             const auto advance = (fDesc.fFlags & Shaper::Flags::kTrackFragmentAdvanceAscent)
 339                     ? fAdvanceBuffer[SkToInt(i)]
 340                     : 0.0f;
 341
 342             // Note: we only check the first code point in the cluster for whitespace.
 343             // It's unclear whether thers's a saner approach.
 344             fResult.fFragments.push_back({fBuilder.make(),
 345                                           { fBox.x() + pos[i].fX, fBox.y() + pos[i].fY },
 346                                           advance, ascent,
 347                                           line_index, is_whitespace(fUTF8[clusters[i]])
 348                                          });
 349             fResult.fMissingGlyphCount += (glyphs[i] == kMissingGlyphID);
 350         }
 351     }
 352
 353     void commitConsolidatedRun(const RunRec& rec,
 354                                const SkGlyphID* glyphs,
 355                                const SkPoint* pos,
 356                                const uint32_t*,
 357                                uint32_t) {
 358         // In consolidated mode we just accumulate glyphs to the blob builder, then push
 359         // to fResult as a single blob in finalize().  Glyph positions are baked in the
 360         // blob (Fragment::fPos only reflects the box origin).
 361         const auto& blob_buffer = fBuilder.allocRunPos(rec.fFont, rec.fGlyphCount);
 362         for (size_t i = 0; i < rec.fGlyphCount; ++i) {
 363             blob_buffer.glyphs[i] = glyphs[i];
 364             fResult.fMissingGlyphCount += (glyphs[i] == kMissingGlyphID);
 365         }
 366         sk_careful_memcpy(blob_buffer.pos, pos, rec.fGlyphCount * sizeof(SkPoint));
 367     }
 368
 369     static float HAlignFactor(SkTextUtils::Align align) {
 370         switch (align) {
 371         case SkTextUtils::kLeft_Align:   return  0.0f;
 372         case SkTextUtils::kCenter_Align: return -0.5f;
 373         case SkTextUtils::kRight_Align:  return -1.0f;
 374         }
 375         return 0.0f; // go home, msvc...
 376     }
 377
 378     SkScalar ascent() const {
 379         // Use the explicit ascent, when specified.
 380         // Note: ascent values are negative (relative to the baseline).
 381         return fDesc.fAscent ? fDesc.fAscent : fFirstLineAscent;
 382     }
 383
 384     inline static constexpr SkGlyphID kMissingGlyphID = 0;
 385
 386     const Shaper::TextDesc&   fDesc;
 387     const SkRect&             fBox;
 388     const float               fHAlignFactor;
 389
 390     SkFont                    fFont;
 391     SkTextBlobBuilder         fBuilder;
 392     std::unique_ptr<SkShaper> fShaper;
 393
 394     SkAutoSTMalloc<64, SkGlyphID> fLineGlyphs;
 395     SkAutoSTMalloc<64, SkPoint>   fLinePos;
 396     SkAutoSTMalloc<64, uint32_t>  fLineClusters;
 397     SkSTArray<16, RunRec>         fLineRuns;
 398     size_t                        fLineGlyphCount = 0;
 399
 400     SkSTArray<64, float, true>    fAdvanceBuffer;
 401
 402     SkPoint  fCurrentPosition{ 0, 0 };
 403     SkPoint  fOffset{ 0, 0 };
 404     SkVector fPendingLineAdvance{ 0, 0 };
 405     uint32_t fLineCount = 0;
 406     float    fFirstLineAscent = 0,
 407              fLastLineDescent = 0;
 408
 409     const char* fUTF8 = nullptr; // only valid during shapeLine() calls
 410
 411     Shaper::Result fResult;
 412 };
 413
 414 Shaper::Result ShapeImpl(const SkString& txt, const Shaper::TextDesc& desc,
 415                          const SkRect& box, const sk_sp<SkFontMgr>& fontmgr,
 416                          SkSize* shaped_size = nullptr) {
 417     const auto& is_line_break = [](SkUnichar uch) {
 418         // TODO: other explicit breaks?
 419         return uch == '\r';
 420     };
 421
 422     const char* ptr        = txt.c_str();
 423     const char* line_start = ptr;
 424     const char* end        = ptr + txt.size();
 425
 426     BlobMaker blobMaker(desc, box, fontmgr);
 427     while (ptr < end) {
 428         if (is_line_break(SkUTF::NextUTF8(&ptr, end))) {
 429             blobMaker.shapeLine(line_start, ptr - 1);
 430             line_start = ptr;
 431         }
 432     }
 433     blobMaker.shapeLine(line_start, ptr);
 434
 435     return blobMaker.finalize(shaped_size);
 436 }
 437
 438 bool result_fits(const Shaper::Result& res, const SkSize& res_size,
 439                  const SkRect& box, const Shaper::TextDesc& desc) {
 440     // optional max line count constraint
 441     if (desc.fMaxLines) {
 442         const auto line_count = res.fFragments.empty()
 443                 ? 0
 444                 : res.fFragments.back().fLineIndex + 1;
 445         if (line_count > desc.fMaxLines) {
 446             return false;
 447         }
 448     }
 449
 450     // geometric constraint
 451     return res_size.width() <= box.width() && res_size.height() <= box.height();
 452 }
 453
 454 Shaper::Result ShapeToFit(const SkString& txt, const Shaper::TextDesc& orig_desc,
 455                           const SkRect& box, const sk_sp<SkFontMgr>& fontmgr) {
 456     Shaper::Result best_result;
 457
 458     if (box.isEmpty() || orig_desc.fTextSize <= 0) {
 459         return best_result;
 460     }
 461
 462     auto desc = orig_desc;
 463
 464     const auto min_scale = std::max(desc.fMinTextSize / desc.fTextSize, 0.0f),
 465                max_scale = std::max(desc.fMaxTextSize / desc.fTextSize, min_scale);
 466
 467     float in_scale = min_scale,                          // maximum scale that fits inside
 468          out_scale = max_scale,                          // minimum scale that doesn't fit
 469          try_scale = SkTPin(1.0f, min_scale, max_scale); // current probe
 470
 471     // Perform a binary search for the best vertical fit (SkShaper already handles
 472     // horizontal fitting), starting with the specified text size.
 473     //
 474     // This hybrid loop handles both the binary search (when in/out extremes are known), and an
 475     // exponential search for the extremes.
 476     static constexpr size_t kMaxIter = 16;
 477     for (size_t i = 0; i < kMaxIter; ++i) {
 478         SkASSERT(try_scale >= in_scale && try_scale <= out_scale);
 479         desc.fTextSize   = try_scale * orig_desc.fTextSize;
 480         desc.fLineHeight = try_scale * orig_desc.fLineHeight;
 481         desc.fLineShift  = try_scale * orig_desc.fLineShift;
 482         desc.fAscent     = try_scale * orig_desc.fAscent;
 483
 484         SkSize res_size = {0, 0};
 485         auto res = ShapeImpl(txt, desc, box, fontmgr, &res_size);
 486
 487         const auto prev_scale = try_scale;
 488         if (!result_fits(res, res_size, box, desc)) {
 489             out_scale = try_scale;
 490             try_scale = (in_scale == min_scale)
 491                     // initial in_scale not found yet - search exponentially
 492                     ? std::max(min_scale, try_scale * 0.5f)
 493                     // in_scale found - binary search
 494                     : (in_scale + out_scale) * 0.5f;
 495         } else {
 496             // It fits - so it's a candidate.
 497             best_result = std::move(res);
 498             best_result.fScale = try_scale;
 499
 500             in_scale = try_scale;
 501             try_scale = (out_scale == max_scale)
 502                     // initial out_scale not found yet - search exponentially
 503                     ? std::min(max_scale, try_scale * 2)
 504                     // out_scale found - binary search
 505                     : (in_scale + out_scale) * 0.5f;
 506         }
 507
 508         if (try_scale == prev_scale) {
 509             // no more progress
 510             break;
 511         }
 512     }
 513
 514     return best_result;
 515 }
 516
 517
 518 // Applies capitalization rules.
 519 class AdjustedText {
 520 public:
 521     AdjustedText(const SkString& txt, const Shaper::TextDesc& desc)
 522         : fText(txt) {
 523         switch (desc.fCapitalization) {
 524         case Shaper::Capitalization::kNone:
 525             break;
 526         case Shaper::Capitalization::kUpperCase:
 527 #ifdef SK_UNICODE_AVAILABLE
 528             if (auto skuni = SkUnicode::Make()) {
 529                 *fText.writable() = skuni->toUpper(*fText);
 530             }
 531 #endif
 532             break;
 533         }
 534     }
 535
 536     operator const SkString&() const { return *fText; }
 537
 538 private:
 539     SkTCopyOnFirstWrite<SkString> fText;
 540 };
 541
 542 } // namespace
 543
 544 Shaper::Result Shaper::Shape(const SkString& orig_txt, const TextDesc& desc, const SkPoint& point,
 545                              const sk_sp<SkFontMgr>& fontmgr) {
 546     const AdjustedText txt(orig_txt, desc);
 547
 548     return (desc.fResize == ResizePolicy::kScaleToFit ||
 549             desc.fResize == ResizePolicy::kDownscaleToFit) // makes no sense in point mode
 550             ? Result()
 551             : ShapeImpl(txt, desc, SkRect::MakeEmpty().makeOffset(point.x(), point.y()), fontmgr);
 552 }
 553
 554 Shaper::Result Shaper::Shape(const SkString& orig_txt, const TextDesc& desc, const SkRect& box,
 555                              const sk_sp<SkFontMgr>& fontmgr) {
 556     const AdjustedText txt(orig_txt, desc);
 557
 558     switch(desc.fResize) {
 559     case ResizePolicy::kNone:
 560         return ShapeImpl(txt, desc, box, fontmgr);
 561     case ResizePolicy::kScaleToFit:
 562         return ShapeToFit(txt, desc, box, fontmgr);
 563     case ResizePolicy::kDownscaleToFit: {
 564         SkSize size;
 565         auto result = ShapeImpl(txt, desc, box, fontmgr, &size);
 566
 567         return result_fits(result, size, box, desc)
 568                 ? result
 569                 : ShapeToFit(txt, desc, box, fontmgr);
 570     }
 571     }
 572
 573     SkUNREACHABLE;
 574 }
 575
 576 SkRect Shaper::Result::computeVisualBounds() const {
 577     auto bounds = SkRect::MakeEmpty();
 578
 579     for (const auto& fragment : fFragments) {
 580         bounds.join(ComputeBlobBounds(fragment.fBlob).makeOffset(fragment.fPos.x(),
 581                                                                  fragment.fPos.y()));
 582     }
 583
 584     return bounds;
 585 }
 586
 587 } // namespace skottie