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