1/*
2 * Copyright 2016 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 <hb-ot.h>
9#include <unicode/brkiter.h>
10#include <unicode/locid.h>
11#include <unicode/stringpiece.h>
12#include <unicode/ubidi.h>
13#include <unicode/uchriter.h>
14#include <unicode/unistr.h>
15#include <unicode/uscript.h>
16
17#include "SkFontMgr.h"
18#include "SkLoadICU.h"
19#include "SkOnce.h"
20#include "SkShaper.h"
21#include "SkStream.h"
22#include "SkTDPQueue.h"
23#include "SkTLazy.h"
24#include "SkTemplates.h"
25#include "SkTextBlob.h"
26#include "SkTypeface.h"
27#include "SkUtils.h"
28
29namespace {
30template <class T, void(*P)(T*)> using resource = std::unique_ptr<T, SkFunctionWrapper<void, T, P>>;
31using HBBlob   = resource<hb_blob_t  , hb_blob_destroy  >;
32using HBFace   = resource<hb_face_t  , hb_face_destroy  >;
33using HBFont   = resource<hb_font_t  , hb_font_destroy  >;
34using HBBuffer = resource<hb_buffer_t, hb_buffer_destroy>;
35using ICUBiDi  = resource<UBiDi      , ubidi_close      >;
36
37HBBlob stream_to_blob(std::unique_ptr<SkStreamAsset> asset) {
38    size_t size = asset->getLength();
39    HBBlob blob;
40    if (const void* base = asset->getMemoryBase()) {
41        blob.reset(hb_blob_create((char*)base, SkToUInt(size),
42                                  HB_MEMORY_MODE_READONLY, asset.release(),
43                                  [](void* p) { delete (SkStreamAsset*)p; }));
44    } else {
45        // SkDebugf("Extra SkStreamAsset copy\n");
46        void* ptr = size ? sk_malloc_throw(size) : nullptr;
47        asset->read(ptr, size);
48        blob.reset(hb_blob_create((char*)ptr, SkToUInt(size),
49                                  HB_MEMORY_MODE_READONLY, ptr, sk_free));
50    }
51    SkASSERT(blob);
52    hb_blob_make_immutable(blob.get());
53    return blob;
54}
55
56HBFont create_hb_font(SkTypeface* tf) {
57    int index;
58    HBBlob blob(stream_to_blob(std::unique_ptr<SkStreamAsset>(tf->openStream(&index))));
59    HBFace face(hb_face_create(blob.get(), (unsigned)index));
60    SkASSERT(face);
61    if (!face) {
62        return nullptr;
63    }
64    hb_face_set_index(face.get(), (unsigned)index);
65    hb_face_set_upem(face.get(), tf->getUnitsPerEm());
66
67    HBFont font(hb_font_create(face.get()));
68    SkASSERT(font);
69    if (!font) {
70        return nullptr;
71    }
72    hb_ot_font_set_funcs(font.get());
73    int axis_count = tf->getVariationDesignPosition(nullptr, 0);
74    if (axis_count > 0) {
75        SkAutoSTMalloc<4, SkFontArguments::VariationPosition::Coordinate> axis_values(axis_count);
76        if (tf->getVariationDesignPosition(axis_values, axis_count) == axis_count) {
77            hb_font_set_variations(font.get(),
78                                   reinterpret_cast<hb_variation_t*>(axis_values.get()),
79                                   axis_count);
80        }
81    }
82    return font;
83}
84
85class RunIterator {
86public:
87    virtual ~RunIterator() {}
88    virtual void consume() = 0;
89    // Pointer one past the last (utf8) element in the current run.
90    virtual const char* endOfCurrentRun() const = 0;
91    virtual bool atEnd() const = 0;
92    bool operator<(const RunIterator& that) const {
93        return this->endOfCurrentRun() < that.endOfCurrentRun();
94    }
95};
96
97class BiDiRunIterator : public RunIterator {
98public:
99    static SkTLazy<BiDiRunIterator> Make(const char* utf8, size_t utf8Bytes, UBiDiLevel level) {
100        SkTLazy<BiDiRunIterator> ret;
101
102        // ubidi only accepts utf16 (though internally it basically works on utf32 chars).
103        // We want an ubidi_setPara(UBiDi*, UText*, UBiDiLevel, UBiDiLevel*, UErrorCode*);
104        if (!SkTFitsIn<int32_t>(utf8Bytes)) {
105            SkDebugf("Bidi error: text too long");
106            return ret;
107        }
108        icu::UnicodeString utf16 = icu::UnicodeString::fromUTF8(icu::StringPiece(utf8, utf8Bytes));
109
110        UErrorCode status = U_ZERO_ERROR;
111        ICUBiDi bidi(ubidi_openSized(utf16.length(), 0, &status));
112        if (U_FAILURE(status)) {
113            SkDebugf("Bidi error: %s", u_errorName(status));
114            return ret;
115        }
116        SkASSERT(bidi);
117
118        // The required lifetime of utf16 isn't well documented.
119        // It appears it isn't used after ubidi_setPara except through ubidi_getText.
120        ubidi_setPara(bidi.get(), utf16.getBuffer(), utf16.length(), level, nullptr, &status);
121        if (U_FAILURE(status)) {
122            SkDebugf("Bidi error: %s", u_errorName(status));
123            return ret;
124        }
125
126        ret.init(utf8, std::move(bidi));
127        return ret;
128    }
129    BiDiRunIterator(const char* utf8, ICUBiDi bidi)
130        : fBidi(std::move(bidi))
131        , fEndOfCurrentRun(utf8)
132        , fUTF16LogicalPosition(0)
133        , fLevel(UBIDI_DEFAULT_LTR)
134    {}
135    void consume() override {
136        SkASSERT(fUTF16LogicalPosition < ubidi_getLength(fBidi.get()));
137        int32_t endPosition = ubidi_getLength(fBidi.get());
138        fLevel = ubidi_getLevelAt(fBidi.get(), fUTF16LogicalPosition);
139        SkUnichar u = SkUTF8_NextUnichar(&fEndOfCurrentRun);
140        fUTF16LogicalPosition += SkUTF16_FromUnichar(u);
141        UBiDiLevel level;
142        while (fUTF16LogicalPosition < endPosition) {
143            level = ubidi_getLevelAt(fBidi.get(), fUTF16LogicalPosition);
144            if (level != fLevel) {
145                break;
146            }
147            u = SkUTF8_NextUnichar(&fEndOfCurrentRun);
148            fUTF16LogicalPosition += SkUTF16_FromUnichar(u);
149        }
150    }
151    const char* endOfCurrentRun() const override {
152        return fEndOfCurrentRun;
153    }
154    bool atEnd() const override {
155        return fUTF16LogicalPosition == ubidi_getLength(fBidi.get());
156    }
157
158    UBiDiLevel currentLevel() const {
159        return fLevel;
160    }
161private:
162    ICUBiDi fBidi;
163    const char* fEndOfCurrentRun;
164    int32_t fUTF16LogicalPosition;
165    UBiDiLevel fLevel;
166};
167
168class ScriptRunIterator : public RunIterator {
169public:
170    static SkTLazy<ScriptRunIterator> Make(const char* utf8, size_t utf8Bytes,
171                                           hb_unicode_funcs_t* hbUnicode)
172    {
173        SkTLazy<ScriptRunIterator> ret;
174        ret.init(utf8, utf8Bytes, hbUnicode);
175        return ret;
176    }
177    ScriptRunIterator(const char* utf8, size_t utf8Bytes, hb_unicode_funcs_t* hbUnicode)
178        : fCurrent(utf8), fEnd(fCurrent + utf8Bytes)
179        , fHBUnicode(hbUnicode)
180        , fCurrentScript(HB_SCRIPT_UNKNOWN)
181    {}
182    void consume() override {
183        SkASSERT(fCurrent < fEnd);
184        SkUnichar u = SkUTF8_NextUnichar(&fCurrent);
185        fCurrentScript = hb_unicode_script(fHBUnicode, u);
186        while (fCurrent < fEnd) {
187            const char* prev = fCurrent;
188            u = SkUTF8_NextUnichar(&fCurrent);
189            const hb_script_t script = hb_unicode_script(fHBUnicode, u);
190            if (script != fCurrentScript) {
191                if (fCurrentScript == HB_SCRIPT_INHERITED || fCurrentScript == HB_SCRIPT_COMMON) {
192                    fCurrentScript = script;
193                } else if (script == HB_SCRIPT_INHERITED || script == HB_SCRIPT_COMMON) {
194                    continue;
195                } else {
196                    fCurrent = prev;
197                    break;
198                }
199            }
200        }
201        if (fCurrentScript == HB_SCRIPT_INHERITED) {
202            fCurrentScript = HB_SCRIPT_COMMON;
203        }
204    }
205    const char* endOfCurrentRun() const override {
206        return fCurrent;
207    }
208    bool atEnd() const override {
209        return fCurrent == fEnd;
210    }
211
212    hb_script_t currentScript() const {
213        return fCurrentScript;
214    }
215private:
216    const char* fCurrent;
217    const char* fEnd;
218    hb_unicode_funcs_t* fHBUnicode;
219    hb_script_t fCurrentScript;
220};
221
222class FontRunIterator : public RunIterator {
223public:
224    static SkTLazy<FontRunIterator> Make(const char* utf8, size_t utf8Bytes,
225                                         sk_sp<SkTypeface> typeface,
226                                         hb_font_t* hbFace,
227                                         sk_sp<SkFontMgr> fallbackMgr)
228    {
229        SkTLazy<FontRunIterator> ret;
230        ret.init(utf8, utf8Bytes, std::move(typeface), hbFace, std::move(fallbackMgr));
231        return ret;
232    }
233    FontRunIterator(const char* utf8, size_t utf8Bytes, sk_sp<SkTypeface> typeface,
234                    hb_font_t* hbFace, sk_sp<SkFontMgr> fallbackMgr)
235        : fCurrent(utf8), fEnd(fCurrent + utf8Bytes)
236        , fFallbackMgr(std::move(fallbackMgr))
237        , fHBFont(hbFace), fTypeface(std::move(typeface))
238        , fFallbackHBFont(nullptr), fFallbackTypeface(nullptr)
239        , fCurrentHBFont(fHBFont), fCurrentTypeface(fTypeface.get())
240    {}
241    void consume() override {
242        SkASSERT(fCurrent < fEnd);
243        SkUnichar u = SkUTF8_NextUnichar(&fCurrent);
244        // If the starting typeface can handle this character, use it.
245        if (fTypeface->charsToGlyphs(&u, SkTypeface::kUTF32_Encoding, nullptr, 1)) {
246            fFallbackTypeface.reset();
247        // If not, try to find a fallback typeface
248        } else {
249            fFallbackTypeface.reset(fFallbackMgr->matchFamilyStyleCharacter(
250                nullptr, fTypeface->fontStyle(), nullptr, 0, u));
251        }
252
253        if (fFallbackTypeface) {
254            fFallbackHBFont = create_hb_font(fFallbackTypeface.get());
255            fCurrentTypeface = fFallbackTypeface.get();
256            fCurrentHBFont = fFallbackHBFont.get();
257        } else {
258            fFallbackHBFont.reset();
259            fCurrentTypeface = fTypeface.get();
260            fCurrentHBFont = fHBFont;
261        }
262
263        while (fCurrent < fEnd) {
264            const char* prev = fCurrent;
265            u = SkUTF8_NextUnichar(&fCurrent);
266
267            // If using a fallback and the initial typeface has this character, stop fallback.
268            if (fFallbackTypeface &&
269                fTypeface->charsToGlyphs(&u, SkTypeface::kUTF32_Encoding, nullptr, 1))
270            {
271                fCurrent = prev;
272                return;
273            }
274            // If the current typeface cannot handle this character, stop using it.
275            if (!fCurrentTypeface->charsToGlyphs(&u, SkTypeface::kUTF32_Encoding, nullptr, 1)) {
276                fCurrent = prev;
277                return;
278            }
279        }
280    }
281    const char* endOfCurrentRun() const override {
282        return fCurrent;
283    }
284    bool atEnd() const override {
285        return fCurrent == fEnd;
286    }
287
288    SkTypeface* currentTypeface() const {
289        return fCurrentTypeface;
290    }
291    hb_font_t* currentHBFont() const {
292        return fCurrentHBFont;
293    }
294private:
295    const char* fCurrent;
296    const char* fEnd;
297    sk_sp<SkFontMgr> fFallbackMgr;
298    hb_font_t* fHBFont;
299    sk_sp<SkTypeface> fTypeface;
300    HBFont fFallbackHBFont;
301    sk_sp<SkTypeface> fFallbackTypeface;
302    hb_font_t* fCurrentHBFont;
303    SkTypeface* fCurrentTypeface;
304};
305
306class RunIteratorQueue {
307public:
308    void insert(RunIterator* runIterator) {
309        fRunIterators.insert(runIterator);
310    }
311
312    bool advanceRuns() {
313        const RunIterator* leastRun = fRunIterators.peek();
314        if (leastRun->atEnd()) {
315            SkASSERT(this->allRunsAreAtEnd());
316            return false;
317        }
318        const char* leastEnd = leastRun->endOfCurrentRun();
319        RunIterator* currentRun = nullptr;
320        SkDEBUGCODE(const char* previousEndOfCurrentRun);
321        while ((currentRun = fRunIterators.peek())->endOfCurrentRun() <= leastEnd) {
322            fRunIterators.pop();
323            SkDEBUGCODE(previousEndOfCurrentRun = currentRun->endOfCurrentRun());
324            currentRun->consume();
325            SkASSERT(previousEndOfCurrentRun < currentRun->endOfCurrentRun());
326            fRunIterators.insert(currentRun);
327        }
328        return true;
329    }
330
331    const char* endOfCurrentRun() const {
332        return fRunIterators.peek()->endOfCurrentRun();
333    }
334
335private:
336    bool allRunsAreAtEnd() const {
337        for (int i = 0; i < fRunIterators.count(); ++i) {
338            if (!fRunIterators.at(i)->atEnd()) {
339                return false;
340            }
341        }
342        return true;
343    }
344
345    static bool CompareRunIterator(RunIterator* const& a, RunIterator* const& b) {
346        return *a < *b;
347    }
348    SkTDPQueue<RunIterator*, CompareRunIterator> fRunIterators;
349};
350
351struct ShapedGlyph {
352    SkGlyphID fID;
353    uint32_t fCluster;
354    SkPoint fOffset;
355    SkVector fAdvance;
356    bool fMayLineBreakBefore;
357    bool fMustLineBreakBefore;
358    bool fHasVisual;
359};
360struct ShapedRun {
361    ShapedRun(const char* utf8Start, const char* utf8End, int numGlyphs, const SkPaint& paint,
362              UBiDiLevel level, std::unique_ptr<ShapedGlyph[]> glyphs)
363        : fUtf8Start(utf8Start), fUtf8End(utf8End), fNumGlyphs(numGlyphs), fPaint(paint)
364        , fLevel(level), fGlyphs(std::move(glyphs))
365    {}
366
367    const char* fUtf8Start;
368    const char* fUtf8End;
369    int fNumGlyphs;
370    SkPaint fPaint;
371    UBiDiLevel fLevel;
372    std::unique_ptr<ShapedGlyph[]> fGlyphs;
373};
374
375static constexpr bool is_LTR(UBiDiLevel level) {
376    return (level & 1) == 0;
377}
378
379static void append(SkTextBlobBuilder* b, const ShapedRun& run, int start, int end, SkPoint* p) {
380    unsigned len = end - start;
381    auto runBuffer = b->allocRunTextPos(run.fPaint, len, run.fUtf8End - run.fUtf8Start, SkString());
382    memcpy(runBuffer.utf8text, run.fUtf8Start, run.fUtf8End - run.fUtf8Start);
383
384    for (unsigned i = 0; i < len; i++) {
385        // Glyphs are in logical order, but output ltr since PDF readers seem to expect that.
386        const ShapedGlyph& glyph = run.fGlyphs[is_LTR(run.fLevel) ? start + i : end - 1 - i];
387        runBuffer.glyphs[i] = glyph.fID;
388        runBuffer.clusters[i] = glyph.fCluster;
389        reinterpret_cast<SkPoint*>(runBuffer.pos)[i] =
390                SkPoint::Make(p->fX + glyph.fOffset.fX, p->fY - glyph.fOffset.fY);
391        p->fX += glyph.fAdvance.fX;
392        p->fY += glyph.fAdvance.fY;
393    }
394}
395
396struct ShapedRunGlyphIterator {
397    ShapedRunGlyphIterator(const SkTArray<ShapedRun>& origRuns)
398        : fRuns(&origRuns), fRunIndex(0), fGlyphIndex(0)
399    { }
400
401    ShapedRunGlyphIterator(const ShapedRunGlyphIterator& that) = default;
402    ShapedRunGlyphIterator& operator=(const ShapedRunGlyphIterator& that) = default;
403    bool operator==(const ShapedRunGlyphIterator& that) const {
404        return fRuns == that.fRuns &&
405               fRunIndex == that.fRunIndex &&
406               fGlyphIndex == that.fGlyphIndex;
407    }
408    bool operator!=(const ShapedRunGlyphIterator& that) const {
409        return fRuns != that.fRuns ||
410               fRunIndex != that.fRunIndex ||
411               fGlyphIndex != that.fGlyphIndex;
412    }
413
414    ShapedGlyph* next() {
415        const SkTArray<ShapedRun>& runs = *fRuns;
416        SkASSERT(fRunIndex < runs.count());
417        SkASSERT(fGlyphIndex < runs[fRunIndex].fNumGlyphs);
418
419        ++fGlyphIndex;
420        if (fGlyphIndex == runs[fRunIndex].fNumGlyphs) {
421            fGlyphIndex = 0;
422            ++fRunIndex;
423            if (fRunIndex >= runs.count()) {
424                return nullptr;
425            }
426        }
427        return &runs[fRunIndex].fGlyphs[fGlyphIndex];
428    }
429
430    ShapedGlyph* current() {
431        const SkTArray<ShapedRun>& runs = *fRuns;
432        if (fRunIndex >= runs.count()) {
433            return nullptr;
434        }
435        return &runs[fRunIndex].fGlyphs[fGlyphIndex];
436    }
437
438    const SkTArray<ShapedRun>* fRuns;
439    int fRunIndex;
440    int fGlyphIndex;
441};
442
443}  // namespace
444
445struct SkShaper::Impl {
446    HBFont fHarfBuzzFont;
447    HBBuffer fBuffer;
448    sk_sp<SkTypeface> fTypeface;
449    std::unique_ptr<icu::BreakIterator> fBreakIterator;
450};
451
452SkShaper::SkShaper(sk_sp<SkTypeface> tf) : fImpl(new Impl) {
453    SkOnce once;
454    once([] { SkLoadICU(); });
455
456    fImpl->fTypeface = tf ? std::move(tf) : SkTypeface::MakeDefault();
457    fImpl->fHarfBuzzFont = create_hb_font(fImpl->fTypeface.get());
458    SkASSERT(fImpl->fHarfBuzzFont);
459    fImpl->fBuffer.reset(hb_buffer_create());
460    SkASSERT(fImpl->fBuffer);
461
462    icu::Locale thai("th");
463    UErrorCode status = U_ZERO_ERROR;
464    fImpl->fBreakIterator.reset(icu::BreakIterator::createLineInstance(thai, status));
465    if (U_FAILURE(status)) {
466        SkDebugf("Could not create break iterator: %s", u_errorName(status));
467        SK_ABORT("");
468    }
469}
470
471SkShaper::~SkShaper() {}
472
473bool SkShaper::good() const {
474    return fImpl->fHarfBuzzFont &&
475           fImpl->fBuffer &&
476           fImpl->fTypeface &&
477           fImpl->fBreakIterator;
478}
479
480SkPoint SkShaper::shape(SkTextBlobBuilder* builder,
481                        const SkPaint& srcPaint,
482                        const char* utf8,
483                        size_t utf8Bytes,
484                        bool leftToRight,
485                        SkPoint point,
486                        SkScalar width) const {
487    sk_sp<SkFontMgr> fontMgr = SkFontMgr::RefDefault();
488    SkASSERT(builder);
489    UBiDiLevel defaultLevel = leftToRight ? UBIDI_DEFAULT_LTR : UBIDI_DEFAULT_RTL;
490    //hb_script_t script = ...
491
492    SkTArray<ShapedRun> runs;
493{
494    RunIteratorQueue runSegmenter;
495
496    SkTLazy<BiDiRunIterator> maybeBidi(BiDiRunIterator::Make(utf8, utf8Bytes, defaultLevel));
497    BiDiRunIterator* bidi = maybeBidi.getMaybeNull();
498    if (!bidi) {
499        return point;
500    }
501    runSegmenter.insert(bidi);
502
503    hb_unicode_funcs_t* hbUnicode = hb_buffer_get_unicode_funcs(fImpl->fBuffer.get());
504    SkTLazy<ScriptRunIterator> maybeScript(ScriptRunIterator::Make(utf8, utf8Bytes, hbUnicode));
505    ScriptRunIterator* script = maybeScript.getMaybeNull();
506    if (!script) {
507        return point;
508    }
509    runSegmenter.insert(script);
510
511    SkTLazy<FontRunIterator> maybeFont(FontRunIterator::Make(utf8, utf8Bytes,
512                                                             fImpl->fTypeface,
513                                                             fImpl->fHarfBuzzFont.get(),
514                                                             std::move(fontMgr)));
515    FontRunIterator* font = maybeFont.getMaybeNull();
516    if (!font) {
517        return point;
518    }
519    runSegmenter.insert(font);
520
521    icu::BreakIterator& breakIterator = *fImpl->fBreakIterator;
522    {
523        UErrorCode status = U_ZERO_ERROR;
524        UText utf8UText = UTEXT_INITIALIZER;
525        utext_openUTF8(&utf8UText, utf8, utf8Bytes, &status);
526        std::unique_ptr<UText, SkFunctionWrapper<UText*, UText, utext_close>> autoClose(&utf8UText);
527        if (U_FAILURE(status)) {
528            SkDebugf("Could not create utf8UText: %s", u_errorName(status));
529            return point;
530        }
531        breakIterator.setText(&utf8UText, status);
532        //utext_close(&utf8UText);
533        if (U_FAILURE(status)) {
534            SkDebugf("Could not setText on break iterator: %s", u_errorName(status));
535            return point;
536        }
537    }
538
539    const char* utf8Start = nullptr;
540    const char* utf8End = utf8;
541    while (runSegmenter.advanceRuns()) {
542        utf8Start = utf8End;
543        utf8End = runSegmenter.endOfCurrentRun();
544
545        hb_buffer_t* buffer = fImpl->fBuffer.get();
546        SkAutoTCallVProc<hb_buffer_t, hb_buffer_clear_contents> autoClearBuffer(buffer);
547        hb_buffer_set_content_type(buffer, HB_BUFFER_CONTENT_TYPE_UNICODE);
548        hb_buffer_set_cluster_level(buffer, HB_BUFFER_CLUSTER_LEVEL_MONOTONE_CHARACTERS);
549
550        // Populate the hb_buffer directly with utf8 cluster indexes.
551        const char* utf8Current = utf8Start;
552        while (utf8Current < utf8End) {
553            unsigned int cluster = utf8Current - utf8Start;
554            hb_codepoint_t u = SkUTF8_NextUnichar(&utf8Current);
555            hb_buffer_add(buffer, u, cluster);
556        }
557
558        size_t utf8runLength = utf8End - utf8Start;
559        if (!SkTFitsIn<int>(utf8runLength)) {
560            SkDebugf("Shaping error: utf8 too long");
561            return point;
562        }
563        hb_buffer_set_script(buffer, script->currentScript());
564        hb_direction_t direction = is_LTR(bidi->currentLevel()) ? HB_DIRECTION_LTR:HB_DIRECTION_RTL;
565        hb_buffer_set_direction(buffer, direction);
566        // TODO: language
567        hb_buffer_guess_segment_properties(buffer);
568        // TODO: features
569        hb_shape(font->currentHBFont(), buffer, nullptr, 0);
570        unsigned len = hb_buffer_get_length(buffer);
571        if (len == 0) {
572            continue;
573        }
574
575        if (direction == HB_DIRECTION_RTL) {
576            // Put the clusters back in logical order.
577            // Note that the advances remain ltr.
578            hb_buffer_reverse(buffer);
579        }
580        hb_glyph_info_t* info = hb_buffer_get_glyph_infos(buffer, nullptr);
581        hb_glyph_position_t* pos = hb_buffer_get_glyph_positions(buffer, nullptr);
582
583        if (!SkTFitsIn<int>(len)) {
584            SkDebugf("Shaping error: too many glyphs");
585            return point;
586        }
587
588        SkPaint paint(srcPaint);
589        paint.setTextEncoding(SkPaint::kGlyphID_TextEncoding);
590        paint.setTypeface(sk_ref_sp(font->currentTypeface()));
591        ShapedRun& run = runs.emplace_back(utf8Start, utf8End, len, paint, bidi->currentLevel(),
592                                           std::unique_ptr<ShapedGlyph[]>(new ShapedGlyph[len]));
593        int scaleX, scaleY;
594        hb_font_get_scale(font->currentHBFont(), &scaleX, &scaleY);
595        double textSizeY = run.fPaint.getTextSize() / scaleY;
596        double textSizeX = run.fPaint.getTextSize() / scaleX * run.fPaint.getTextScaleX();
597        for (unsigned i = 0; i < len; i++) {
598            ShapedGlyph& glyph = run.fGlyphs[i];
599            glyph.fID = info[i].codepoint;
600            glyph.fCluster = info[i].cluster;
601            glyph.fOffset.fX = pos[i].x_offset * textSizeX;
602            glyph.fOffset.fY = pos[i].y_offset * textSizeY;
603            glyph.fAdvance.fX = pos[i].x_advance * textSizeX;
604            glyph.fAdvance.fY = pos[i].y_advance * textSizeY;
605            glyph.fHasVisual = true; //!font->currentTypeface()->glyphBoundsAreZero(glyph.fID);
606            //info->mask safe_to_break;
607            glyph.fMustLineBreakBefore = false;
608        }
609
610        int32_t clusterOffset = utf8Start - utf8;
611        uint32_t previousCluster = 0xFFFFFFFF;
612        for (unsigned i = 0; i < len; ++i) {
613            ShapedGlyph& glyph = run.fGlyphs[i];
614            int32_t glyphCluster = glyph.fCluster + clusterOffset;
615            int32_t breakIteratorCurrent = breakIterator.current();
616            while (breakIteratorCurrent != icu::BreakIterator::DONE &&
617                   breakIteratorCurrent < glyphCluster)
618            {
619                breakIteratorCurrent = breakIterator.next();
620            }
621            glyph.fMayLineBreakBefore = glyph.fCluster != previousCluster &&
622                                        breakIteratorCurrent == glyphCluster;
623            previousCluster = glyph.fCluster;
624        }
625    }
626}
627
628// Iterate over the glyphs in logical order to mark line endings.
629{
630    SkScalar widthSoFar = 0;
631    bool previousBreakValid = false; // Set when previousBreak is set to a valid candidate break.
632    bool canAddBreakNow = false; // Disallow line breaks before the first glyph of a run.
633    ShapedRunGlyphIterator previousBreak(runs);
634    ShapedRunGlyphIterator glyphIterator(runs);
635    while (ShapedGlyph* glyph = glyphIterator.current()) {
636        if (canAddBreakNow && glyph->fMayLineBreakBefore) {
637            previousBreakValid = true;
638            previousBreak = glyphIterator;
639        }
640        SkScalar glyphWidth = glyph->fAdvance.fX;
641        if (widthSoFar + glyphWidth < width) {
642            widthSoFar += glyphWidth;
643            glyphIterator.next();
644            canAddBreakNow = true;
645            continue;
646        }
647
648        if (widthSoFar == 0) {
649            // Adding just this glyph is too much, just break with this glyph
650            glyphIterator.next();
651            previousBreak = glyphIterator;
652        } else if (!previousBreakValid) {
653            // No break opprotunity found yet, just break without this glyph
654            previousBreak = glyphIterator;
655        }
656        glyphIterator = previousBreak;
657        glyph = glyphIterator.current();
658        if (glyph) {
659            glyph->fMustLineBreakBefore = true;
660        }
661        widthSoFar = 0;
662        previousBreakValid = false;
663        canAddBreakNow = false;
664    }
665}
666
667// Reorder the runs and glyphs per line and write them out.
668    SkPoint currentPoint = point;
669{
670    ShapedRunGlyphIterator previousBreak(runs);
671    ShapedRunGlyphIterator glyphIterator(runs);
672    SkScalar maxAscent = 0;
673    SkScalar maxDescent = 0;
674    SkScalar maxLeading = 0;
675    int previousRunIndex = -1;
676    while (glyphIterator.current()) {
677        int runIndex = glyphIterator.fRunIndex;
678        int glyphIndex = glyphIterator.fGlyphIndex;
679        ShapedGlyph* nextGlyph = glyphIterator.next();
680
681        if (previousRunIndex != runIndex) {
682            SkPaint::FontMetrics metrics;
683            runs[runIndex].fPaint.getFontMetrics(&metrics);
684            maxAscent = SkTMin(maxAscent, metrics.fAscent);
685            maxDescent = SkTMax(maxDescent, metrics.fDescent);
686            maxLeading = SkTMax(maxLeading, metrics.fLeading);
687            previousRunIndex = runIndex;
688        }
689
690        // Nothing can be written until the baseline is known.
691        if (!(nextGlyph == nullptr || nextGlyph->fMustLineBreakBefore)) {
692            continue;
693        }
694
695        currentPoint.fY -= maxAscent;
696
697        int numRuns = runIndex - previousBreak.fRunIndex + 1;
698        SkAutoSTMalloc<4, UBiDiLevel> runLevels(numRuns);
699        for (int i = 0; i < numRuns; ++i) {
700            runLevels[i] = runs[previousBreak.fRunIndex + i].fLevel;
701        }
702        SkAutoSTMalloc<4, int32_t> logicalFromVisual(numRuns);
703        ubidi_reorderVisual(runLevels, numRuns, logicalFromVisual);
704
705        for (int i = 0; i < numRuns; ++i) {
706            int logicalIndex = previousBreak.fRunIndex + logicalFromVisual[i];
707
708            int startGlyphIndex = (logicalIndex == previousBreak.fRunIndex)
709                                ? previousBreak.fGlyphIndex
710                                : 0;
711            int endGlyphIndex = (logicalIndex == runIndex)
712                              ? glyphIndex + 1
713                              : runs[logicalIndex].fNumGlyphs;
714            append(builder, runs[logicalIndex], startGlyphIndex, endGlyphIndex, &currentPoint);
715        }
716
717        currentPoint.fY += maxDescent + maxLeading;
718        currentPoint.fX = point.fX;
719        maxAscent = 0;
720        maxDescent = 0;
721        maxLeading = 0;
722        previousRunIndex = -1;
723        previousBreak = glyphIterator;
724    }
725}
726
727    return currentPoint;
728}
729