dc80607a12d287c56639c475441355ad148afa52
[WebKit-https.git] / Source / WebCore / platform / graphics / ComplexTextController.cpp
1 /*
2  * Copyright (C) 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
16  * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
17  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
20  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23  */
24
25 #include "config.h"
26 #include "ComplexTextController.h"
27
28 #include "CharacterProperties.h"
29 #include "FloatSize.h"
30 #include "FontCascade.h"
31 #include "RenderBlock.h"
32 #include "RenderText.h"
33 #include "TextRun.h"
34 #include <unicode/ubrk.h>
35 #include <wtf/Optional.h>
36 #include <wtf/StdLibExtras.h>
37 #include <wtf/text/TextBreakIterator.h>
38 #include <wtf/unicode/CharacterNames.h>
39
40 #if PLATFORM(IOS)
41 #include <CoreText/CoreText.h>
42 #endif
43
44 #if PLATFORM(MAC)
45 #include <ApplicationServices/ApplicationServices.h>
46 #endif
47
48 namespace WebCore {
49
50 class TextLayout {
51     WTF_MAKE_FAST_ALLOCATED;
52 public:
53     static bool isNeeded(RenderText& text, const FontCascade& font)
54     {
55         TextRun run = RenderBlock::constructTextRun(text, text.style());
56         return font.codePath(run) == FontCascade::Complex;
57     }
58
59     TextLayout(RenderText& text, const FontCascade& font, float xPos)
60         : m_font(font)
61         , m_run(constructTextRun(text, xPos))
62         , m_controller(std::make_unique<ComplexTextController>(m_font, m_run, true))
63     {
64     }
65
66     float width(unsigned from, unsigned len, HashSet<const Font*>* fallbackFonts)
67     {
68         m_controller->advance(from, 0, ByWholeGlyphs, fallbackFonts);
69         float beforeWidth = m_controller->runWidthSoFar();
70         if (m_font.wordSpacing() && from && FontCascade::treatAsSpace(m_run[from]))
71             beforeWidth += m_font.wordSpacing();
72         m_controller->advance(from + len, 0, ByWholeGlyphs, fallbackFonts);
73         float afterWidth = m_controller->runWidthSoFar();
74         return afterWidth - beforeWidth;
75     }
76
77 private:
78     static TextRun constructTextRun(RenderText& text, float xPos)
79     {
80         TextRun run = RenderBlock::constructTextRun(text, text.style());
81         run.setCharactersLength(text.textLength());
82         ASSERT(run.charactersLength() >= run.length());
83         run.setXPos(xPos);
84         return run;
85     }
86
87     // ComplexTextController has only references to its FontCascade and TextRun so they must be kept alive here.
88     FontCascade m_font;
89     TextRun m_run;
90     std::unique_ptr<ComplexTextController> m_controller;
91 };
92
93 void TextLayoutDeleter::operator()(TextLayout* layout) const
94 {
95 #if PLATFORM(COCOA)
96     delete layout;
97 #else
98     ASSERT_UNUSED(layout, !layout);
99 #endif
100 }
101
102 std::unique_ptr<TextLayout, TextLayoutDeleter> FontCascade::createLayout(RenderText& text, float xPos, bool collapseWhiteSpace) const
103 {
104 #if PLATFORM(COCOA)
105     if (!collapseWhiteSpace || !TextLayout::isNeeded(text, *this))
106         return nullptr;
107     return std::unique_ptr<TextLayout, TextLayoutDeleter>(new TextLayout(text, *this, xPos));
108 #else
109     UNUSED_PARAM(text);
110     UNUSED_PARAM(xPos);
111     UNUSED_PARAM(collapseWhiteSpace);
112     return nullptr;
113 #endif
114 }
115
116 float FontCascade::width(TextLayout& layout, unsigned from, unsigned len, HashSet<const Font*>* fallbackFonts)
117 {
118 #if PLATFORM(COCOA)
119     return layout.width(from, len, fallbackFonts);
120 #else
121     UNUSED_PARAM(layout);
122     UNUSED_PARAM(from);
123     UNUSED_PARAM(len);
124     UNUSED_PARAM(fallbackFonts);
125     ASSERT_NOT_REACHED();
126     return 0;
127 #endif
128 }
129
130 void ComplexTextController::computeExpansionOpportunity()
131 {
132     if (!m_expansion)
133         m_expansionPerOpportunity = 0;
134     else {
135         unsigned expansionOpportunityCount = FontCascade::expansionOpportunityCount(m_run.text(), m_run.ltr() ? LTR : RTL, m_run.expansionBehavior()).first;
136
137         if (!expansionOpportunityCount)
138             m_expansionPerOpportunity = 0;
139         else
140             m_expansionPerOpportunity = m_expansion / expansionOpportunityCount;
141     }
142 }
143
144 ComplexTextController::ComplexTextController(const FontCascade& font, const TextRun& run, bool mayUseNaturalWritingDirection, HashSet<const Font*>* fallbackFonts, bool forTextEmphasis)
145     : m_fallbackFonts(fallbackFonts)
146     , m_font(font)
147     , m_run(run)
148     , m_end(run.length())
149     , m_expansion(run.expansion())
150     , m_mayUseNaturalWritingDirection(mayUseNaturalWritingDirection)
151     , m_forTextEmphasis(forTextEmphasis)
152 {
153     computeExpansionOpportunity();
154
155     collectComplexTextRuns();
156
157     finishConstruction();
158 }
159
160 ComplexTextController::ComplexTextController(const FontCascade& font, const TextRun& run, Vector<Ref<ComplexTextRun>>& runs)
161     : m_font(font)
162     , m_run(run)
163     , m_end(run.length())
164     , m_expansion(run.expansion())
165 {
166     computeExpansionOpportunity();
167
168     for (auto& run : runs)
169         m_complexTextRuns.append(run.ptr());
170
171     finishConstruction();
172 }
173
174 void ComplexTextController::finishConstruction()
175 {
176     adjustGlyphsAndAdvances();
177
178     if (!m_isLTROnly) {
179         m_runIndices.reserveInitialCapacity(m_complexTextRuns.size());
180
181         m_glyphCountFromStartToIndex.reserveInitialCapacity(m_complexTextRuns.size());
182         unsigned glyphCountSoFar = 0;
183         for (unsigned i = 0; i < m_complexTextRuns.size(); ++i) {
184             m_glyphCountFromStartToIndex.uncheckedAppend(glyphCountSoFar);
185             glyphCountSoFar += m_complexTextRuns[i]->glyphCount();
186         }
187     }
188 }
189
190 unsigned ComplexTextController::offsetForPosition(float h, bool includePartialGlyphs)
191 {
192     if (h >= m_totalWidth)
193         return m_run.ltr() ? m_end : 0;
194
195     if (h < 0)
196         return m_run.ltr() ? 0 : m_end;
197
198     float x = h;
199
200     size_t runCount = m_complexTextRuns.size();
201     unsigned offsetIntoAdjustedGlyphs = 0;
202
203     for (size_t r = 0; r < runCount; ++r) {
204         const ComplexTextRun& complexTextRun = *m_complexTextRuns[r];
205         for (unsigned j = 0; j < complexTextRun.glyphCount(); ++j) {
206             unsigned index = offsetIntoAdjustedGlyphs + j;
207             float adjustedAdvance = m_adjustedBaseAdvances[index].width();
208             if (x < adjustedAdvance) {
209                 unsigned hitGlyphStart = complexTextRun.indexAt(j);
210                 unsigned hitGlyphEnd;
211                 if (m_run.ltr())
212                     hitGlyphEnd = std::max(hitGlyphStart, j + 1 < complexTextRun.glyphCount() ? complexTextRun.indexAt(j + 1) : complexTextRun.indexEnd());
213                 else
214                     hitGlyphEnd = std::max(hitGlyphStart, j > 0 ? complexTextRun.indexAt(j - 1) : complexTextRun.indexEnd());
215
216                 // FIXME: Instead of dividing the glyph's advance equally between the characters, this
217                 // could use the glyph's "ligature carets". This is available in CoreText via CTFontGetLigatureCaretPositions().
218                 unsigned hitIndex = hitGlyphStart + (hitGlyphEnd - hitGlyphStart) * (m_run.ltr() ? x / adjustedAdvance : 1 - x / adjustedAdvance);
219                 unsigned stringLength = complexTextRun.stringLength();
220                 CachedTextBreakIterator cursorPositionIterator(StringView(complexTextRun.characters(), stringLength), TextBreakIterator::Mode::Cursor, nullAtom);
221                 unsigned clusterStart;
222                 if (cursorPositionIterator.isBoundary(hitIndex))
223                     clusterStart = hitIndex;
224                 else
225                     clusterStart = cursorPositionIterator.preceding(hitIndex).value_or(0);
226
227                 if (!includePartialGlyphs)
228                     return complexTextRun.stringLocation() + clusterStart;
229
230                 unsigned clusterEnd = cursorPositionIterator.following(hitIndex).value_or(stringLength);
231
232                 float clusterWidth;
233                 // FIXME: The search stops at the boundaries of complexTextRun. In theory, it should go on into neighboring ComplexTextRuns
234                 // derived from the same CTLine. In practice, we do not expect there to be more than one CTRun in a CTLine, as no
235                 // reordering and no font fallback should occur within a CTLine.
236                 if (clusterEnd - clusterStart > 1) {
237                     clusterWidth = adjustedAdvance;
238                     if (j) {
239                         unsigned firstGlyphBeforeCluster = j - 1;
240                         while (complexTextRun.indexAt(firstGlyphBeforeCluster) >= clusterStart && complexTextRun.indexAt(firstGlyphBeforeCluster) < clusterEnd) {
241                             float width = m_adjustedBaseAdvances[offsetIntoAdjustedGlyphs + firstGlyphBeforeCluster].width();
242                             clusterWidth += width;
243                             x += width;
244                             if (!firstGlyphBeforeCluster)
245                                 break;
246                             firstGlyphBeforeCluster--;
247                         }
248                     }
249                     unsigned firstGlyphAfterCluster = j + 1;
250                     while (firstGlyphAfterCluster < complexTextRun.glyphCount() && complexTextRun.indexAt(firstGlyphAfterCluster) >= clusterStart && complexTextRun.indexAt(firstGlyphAfterCluster) < clusterEnd) {
251                         clusterWidth += m_adjustedBaseAdvances[offsetIntoAdjustedGlyphs + firstGlyphAfterCluster].width();
252                         firstGlyphAfterCluster++;
253                     }
254                 } else {
255                     clusterWidth = adjustedAdvance / (hitGlyphEnd - hitGlyphStart);
256                     x -=  clusterWidth * (m_run.ltr() ? hitIndex - hitGlyphStart : hitGlyphEnd - hitIndex - 1);
257                 }
258                 if (x <= clusterWidth / 2)
259                     return complexTextRun.stringLocation() + (m_run.ltr() ? clusterStart : clusterEnd);
260                 return complexTextRun.stringLocation() + (m_run.ltr() ? clusterEnd : clusterStart);
261             }
262             x -= adjustedAdvance;
263         }
264         offsetIntoAdjustedGlyphs += complexTextRun.glyphCount();
265     }
266
267     ASSERT_NOT_REACHED();
268     return 0;
269 }
270
271 // FIXME: We should consider reimplementing this function using ICU to advance by grapheme.
272 // The current implementation only considers explicitly emoji sequences and emoji variations.
273 static bool advanceByCombiningCharacterSequence(const UChar*& iterator, const UChar* end, UChar32& baseCharacter, unsigned& markCount)
274 {
275     ASSERT(iterator < end);
276
277     markCount = 0;
278
279     unsigned i = 0;
280     unsigned remainingCharacters = end - iterator;
281     U16_NEXT(iterator, i, remainingCharacters, baseCharacter);
282     iterator = iterator + i;
283     if (U_IS_SURROGATE(baseCharacter))
284         return false;
285
286     // Consume marks.
287     bool sawEmojiGroupCandidate = isEmojiGroupCandidate(baseCharacter);
288     bool sawJoiner = false;
289     while (iterator < end) {
290         UChar32 nextCharacter;
291         unsigned markLength = 0;
292         bool shouldContinue = false;
293         ASSERT(end >= iterator);
294         U16_NEXT(iterator, markLength, static_cast<unsigned>(end - iterator), nextCharacter);
295
296         if (isVariationSelector(nextCharacter) || isEmojiFitzpatrickModifier(nextCharacter))
297             shouldContinue = true;
298
299         if (sawJoiner && isEmojiGroupCandidate(nextCharacter))
300             shouldContinue = true;
301
302         sawJoiner = false;
303         if (sawEmojiGroupCandidate && nextCharacter == zeroWidthJoiner) {
304             sawJoiner = true;
305             shouldContinue = true;
306         }
307         
308         if (!shouldContinue && !(U_GET_GC_MASK(nextCharacter) & U_GC_M_MASK))
309             break;
310
311         markCount += markLength;
312         iterator += markLength;
313     }
314
315     return true;
316 }
317
318 // FIXME: Capitalization is language-dependent and context-dependent and should operate on grapheme clusters instead of codepoints.
319 static inline std::optional<UChar32> capitalized(UChar32 baseCharacter)
320 {
321     if (U_GET_GC_MASK(baseCharacter) & U_GC_M_MASK)
322         return std::nullopt;
323
324     UChar32 uppercaseCharacter = u_toupper(baseCharacter);
325     ASSERT(uppercaseCharacter == baseCharacter || (U_IS_BMP(baseCharacter) == U_IS_BMP(uppercaseCharacter)));
326     if (uppercaseCharacter != baseCharacter)
327         return uppercaseCharacter;
328     return std::nullopt;
329 }
330
331 static bool shouldSynthesize(bool dontSynthesizeSmallCaps, const Font* nextFont, UChar32 baseCharacter, std::optional<UChar32> capitalizedBase, FontVariantCaps fontVariantCaps, bool engageAllSmallCapsProcessing)
332 {
333     if (dontSynthesizeSmallCaps)
334         return false;
335     if (!nextFont || nextFont == Font::systemFallback())
336         return false;
337     if (engageAllSmallCapsProcessing && isASCIISpace(baseCharacter))
338         return false;
339     if (!engageAllSmallCapsProcessing && !capitalizedBase)
340         return false;
341     return !nextFont->variantCapsSupportsCharacterForSynthesis(fontVariantCaps, baseCharacter);
342 }
343
344 void ComplexTextController::collectComplexTextRuns()
345 {
346     if (!m_end)
347         return;
348
349     // We break up glyph run generation for the string by Font.
350     const UChar* cp;
351
352     if (m_run.is8Bit()) {
353         String stringFor8BitRun = String::make16BitFrom8BitSource(m_run.characters8(), m_run.length());
354         m_stringsFor8BitRuns.append(WTFMove(stringFor8BitRun));
355         cp = m_stringsFor8BitRuns.last().characters16();
356     } else
357         cp = m_run.characters16();
358
359     auto fontVariantCaps = m_font.fontDescription().variantCaps();
360     bool dontSynthesizeSmallCaps = !static_cast<bool>(m_font.fontDescription().fontSynthesis() & FontSynthesisSmallCaps);
361     bool engageAllSmallCapsProcessing = fontVariantCaps == FontVariantCaps::AllSmall || fontVariantCaps == FontVariantCaps::AllPetite;
362     bool engageSmallCapsProcessing = engageAllSmallCapsProcessing || fontVariantCaps == FontVariantCaps::Small || fontVariantCaps == FontVariantCaps::Petite;
363
364     if (engageAllSmallCapsProcessing || engageSmallCapsProcessing)
365         m_smallCapsBuffer.resize(m_end);
366
367     unsigned indexOfFontTransition = 0;
368     const UChar* curr = cp;
369     const UChar* end = cp + m_end;
370
371     const Font* font;
372     const Font* nextFont;
373     const Font* synthesizedFont = nullptr;
374     const Font* smallSynthesizedFont = nullptr;
375
376     unsigned markCount;
377     UChar32 baseCharacter;
378     if (!advanceByCombiningCharacterSequence(curr, end, baseCharacter, markCount))
379         return;
380
381     nextFont = m_font.fontForCombiningCharacterSequence(cp, curr - cp);
382
383     bool isSmallCaps = false;
384     bool nextIsSmallCaps = false;
385
386     auto capitalizedBase = capitalized(baseCharacter);
387     if (shouldSynthesize(dontSynthesizeSmallCaps, nextFont, baseCharacter, capitalizedBase, fontVariantCaps, engageAllSmallCapsProcessing)) {
388         synthesizedFont = &nextFont->noSynthesizableFeaturesFont();
389         smallSynthesizedFont = synthesizedFont->smallCapsFont(m_font.fontDescription());
390         UChar32 characterToWrite = capitalizedBase ? capitalizedBase.value() : cp[0];
391         unsigned characterIndex = 0;
392         U16_APPEND_UNSAFE(m_smallCapsBuffer, characterIndex, characterToWrite);
393         for (unsigned i = characterIndex; cp + i < curr; ++i)
394             m_smallCapsBuffer[i] = cp[i];
395         nextIsSmallCaps = true;
396     }
397
398     while (curr < end) {
399         font = nextFont;
400         isSmallCaps = nextIsSmallCaps;
401         unsigned index = curr - cp;
402
403         if (!advanceByCombiningCharacterSequence(curr, end, baseCharacter, markCount))
404             return;
405
406         if (synthesizedFont) {
407             if (auto capitalizedBase = capitalized(baseCharacter)) {
408                 unsigned characterIndex = index;
409                 U16_APPEND_UNSAFE(m_smallCapsBuffer, characterIndex, capitalizedBase.value());
410                 for (unsigned i = 0; i < markCount; ++i)
411                     m_smallCapsBuffer[i + characterIndex] = cp[i + characterIndex];
412                 nextIsSmallCaps = true;
413             } else {
414                 if (engageAllSmallCapsProcessing) {
415                     for (unsigned i = 0; i < curr - cp - index; ++i)
416                         m_smallCapsBuffer[index + i] = cp[index + i];
417                 }
418                 nextIsSmallCaps = engageAllSmallCapsProcessing;
419             }
420         }
421
422         if (baseCharacter == zeroWidthJoiner)
423             nextFont = font;
424         else
425             nextFont = m_font.fontForCombiningCharacterSequence(cp + index, curr - cp - index);
426
427         capitalizedBase = capitalized(baseCharacter);
428         if (!synthesizedFont && shouldSynthesize(dontSynthesizeSmallCaps, nextFont, baseCharacter, capitalizedBase, fontVariantCaps, engageAllSmallCapsProcessing)) {
429             // Rather than synthesize each character individually, we should synthesize the entire "run" if any character requires synthesis.
430             synthesizedFont = &nextFont->noSynthesizableFeaturesFont();
431             smallSynthesizedFont = synthesizedFont->smallCapsFont(m_font.fontDescription());
432             nextIsSmallCaps = true;
433             curr = cp + indexOfFontTransition;
434             continue;
435         }
436
437         if (nextFont != font || nextIsSmallCaps != isSmallCaps) {
438             unsigned itemLength = index - indexOfFontTransition;
439             if (itemLength) {
440                 unsigned itemStart = indexOfFontTransition;
441                 if (synthesizedFont) {
442                     if (isSmallCaps)
443                         collectComplexTextRunsForCharacters(m_smallCapsBuffer.data() + itemStart, itemLength, itemStart, smallSynthesizedFont);
444                     else
445                         collectComplexTextRunsForCharacters(cp + itemStart, itemLength, itemStart, synthesizedFont);
446                 } else
447                     collectComplexTextRunsForCharacters(cp + itemStart, itemLength, itemStart, font);
448                 if (nextFont != font) {
449                     synthesizedFont = nullptr;
450                     smallSynthesizedFont = nullptr;
451                     nextIsSmallCaps = false;
452                 }
453             }
454             indexOfFontTransition = index;
455         }
456     }
457
458     ASSERT(m_end >= indexOfFontTransition);
459     unsigned itemLength = m_end - indexOfFontTransition;
460     if (itemLength) {
461         unsigned itemStart = indexOfFontTransition;
462         if (synthesizedFont) {
463             if (nextIsSmallCaps)
464                 collectComplexTextRunsForCharacters(m_smallCapsBuffer.data() + itemStart, itemLength, itemStart, smallSynthesizedFont);
465             else
466                 collectComplexTextRunsForCharacters(cp + itemStart, itemLength, itemStart, synthesizedFont);
467         } else
468             collectComplexTextRunsForCharacters(cp + itemStart, itemLength, itemStart, nextFont);
469     }
470
471     if (!m_run.ltr())
472         m_complexTextRuns.reverse();
473 }
474
475 unsigned ComplexTextController::ComplexTextRun::indexAt(unsigned i) const
476 {
477     ASSERT(i < m_glyphCount);
478
479     return m_coreTextIndices[i];
480 }
481
482 void ComplexTextController::ComplexTextRun::setIsNonMonotonic()
483 {
484     ASSERT(m_isMonotonic);
485     m_isMonotonic = false;
486
487     Vector<bool, 64> mappedIndices(m_stringLength, false);
488     for (unsigned i = 0; i < m_glyphCount; ++i) {
489         ASSERT(indexAt(i) < m_stringLength);
490         mappedIndices[indexAt(i)] = true;
491     }
492
493     m_glyphEndOffsets.grow(m_glyphCount);
494     for (unsigned i = 0; i < m_glyphCount; ++i) {
495         unsigned nextMappedIndex = m_indexEnd;
496         for (unsigned j = indexAt(i) + 1; j < m_stringLength; ++j) {
497             if (mappedIndices[j]) {
498                 nextMappedIndex = j;
499                 break;
500             }
501         }
502         m_glyphEndOffsets[i] = nextMappedIndex;
503     }
504 }
505
506 unsigned ComplexTextController::indexOfCurrentRun(unsigned& leftmostGlyph)
507 {
508     leftmostGlyph = 0;
509     
510     size_t runCount = m_complexTextRuns.size();
511     if (m_currentRun >= runCount)
512         return runCount;
513
514     if (m_isLTROnly) {
515         for (unsigned i = 0; i < m_currentRun; ++i)
516             leftmostGlyph += m_complexTextRuns[i]->glyphCount();
517         return m_currentRun;
518     }
519
520     if (m_runIndices.isEmpty()) {
521         unsigned firstRun = 0;
522         unsigned firstRunOffset = stringBegin(*m_complexTextRuns[0]);
523         for (unsigned i = 1; i < runCount; ++i) {
524             unsigned offset = stringBegin(*m_complexTextRuns[i]);
525             if (offset < firstRunOffset) {
526                 firstRun = i;
527                 firstRunOffset = offset;
528             }
529         }
530         m_runIndices.uncheckedAppend(firstRun);
531     }
532
533     while (m_runIndices.size() <= m_currentRun) {
534         unsigned offset = stringEnd(*m_complexTextRuns[m_runIndices.last()]);
535
536         for (unsigned i = 0; i < runCount; ++i) {
537             if (offset == stringBegin(*m_complexTextRuns[i])) {
538                 m_runIndices.uncheckedAppend(i);
539                 break;
540             }
541         }
542     }
543
544     unsigned currentRunIndex = m_runIndices[m_currentRun];
545     leftmostGlyph = m_glyphCountFromStartToIndex[currentRunIndex];
546     return currentRunIndex;
547 }
548
549 unsigned ComplexTextController::incrementCurrentRun(unsigned& leftmostGlyph)
550 {
551     if (m_isLTROnly) {
552         leftmostGlyph += m_complexTextRuns[m_currentRun++]->glyphCount();
553         return m_currentRun;
554     }
555
556     m_currentRun++;
557     leftmostGlyph = 0;
558     return indexOfCurrentRun(leftmostGlyph);
559 }
560
561 float ComplexTextController::runWidthSoFarFraction(unsigned glyphStartOffset, unsigned glyphEndOffset, unsigned oldCharacterInCurrentGlyph, GlyphIterationStyle iterationStyle) const
562 {
563     // FIXME: Instead of dividing the glyph's advance equally between the characters, this
564     // could use the glyph's "ligature carets". This is available in CoreText via CTFontGetLigatureCaretPositions().
565     if (glyphStartOffset == glyphEndOffset) {
566         // When there are multiple glyphs per character we need to advance by the full width of the glyph.
567         ASSERT(m_characterInCurrentGlyph == oldCharacterInCurrentGlyph);
568         return 1;
569     }
570
571     if (iterationStyle == ByWholeGlyphs) {
572         if (!oldCharacterInCurrentGlyph)
573             return 1;
574         return 0;
575     }
576
577     return static_cast<float>(m_characterInCurrentGlyph - oldCharacterInCurrentGlyph) / (glyphEndOffset - glyphStartOffset);
578 }
579
580 void ComplexTextController::advance(unsigned offset, GlyphBuffer* glyphBuffer, GlyphIterationStyle iterationStyle, HashSet<const Font*>* fallbackFonts)
581 {
582     if (offset > m_end)
583         offset = m_end;
584
585     if (offset <= m_currentCharacter) {
586         m_runWidthSoFar = 0;
587         m_numGlyphsSoFar = 0;
588         m_currentRun = 0;
589         m_glyphInCurrentRun = 0;
590         m_characterInCurrentGlyph = 0;
591     }
592
593     m_currentCharacter = offset;
594
595     size_t runCount = m_complexTextRuns.size();
596
597     unsigned indexOfLeftmostGlyphInCurrentRun = 0; // Relative to the beginning of ComplexTextController.
598     unsigned currentRunIndex = indexOfCurrentRun(indexOfLeftmostGlyphInCurrentRun);
599     while (m_currentRun < runCount) {
600         const ComplexTextRun& complexTextRun = *m_complexTextRuns[currentRunIndex];
601         bool ltr = complexTextRun.isLTR();
602         unsigned glyphCount = complexTextRun.glyphCount();
603         unsigned glyphIndexIntoCurrentRun = ltr ? m_glyphInCurrentRun : glyphCount - 1 - m_glyphInCurrentRun;
604         unsigned glyphIndexIntoComplexTextController = indexOfLeftmostGlyphInCurrentRun + glyphIndexIntoCurrentRun;
605         if (fallbackFonts && &complexTextRun.font() != &m_font.primaryFont())
606             fallbackFonts->add(&complexTextRun.font());
607
608         // We must store the initial advance for the first glyph we are going to draw.
609         // When leftmostGlyph is 0, it represents the first glyph to draw, taking into
610         // account the text direction.
611         if (!indexOfLeftmostGlyphInCurrentRun && glyphBuffer)
612             glyphBuffer->setInitialAdvance(GlyphBufferAdvance(complexTextRun.initialAdvance().width(), complexTextRun.initialAdvance().height()));
613
614         while (m_glyphInCurrentRun < glyphCount) {
615             unsigned glyphStartOffset = complexTextRun.indexAt(glyphIndexIntoCurrentRun);
616             unsigned glyphEndOffset;
617             if (complexTextRun.isMonotonic()) {
618                 if (ltr)
619                     glyphEndOffset = std::max(glyphStartOffset, glyphIndexIntoCurrentRun + 1 < glyphCount ? complexTextRun.indexAt(glyphIndexIntoCurrentRun + 1) : complexTextRun.indexEnd());
620                 else
621                     glyphEndOffset = std::max(glyphStartOffset, glyphIndexIntoCurrentRun > 0 ? complexTextRun.indexAt(glyphIndexIntoCurrentRun - 1) : complexTextRun.indexEnd());
622             } else
623                 glyphEndOffset = complexTextRun.endOffsetAt(glyphIndexIntoCurrentRun);
624
625             FloatSize adjustedBaseAdvance = m_adjustedBaseAdvances[glyphIndexIntoComplexTextController];
626
627             if (glyphStartOffset + complexTextRun.stringLocation() >= m_currentCharacter)
628                 return;
629
630             if (glyphBuffer && !m_characterInCurrentGlyph) {
631                 auto currentGlyphOrigin = glyphOrigin(glyphIndexIntoComplexTextController);
632                 GlyphBufferAdvance paintAdvance(adjustedBaseAdvance);
633                 if (!glyphIndexIntoCurrentRun) {
634                     // The first layout advance of every run includes the "initial layout advance." However, here, we need
635                     // paint advances, so subtract it out before transforming the layout advance into a paint advance.
636                     paintAdvance.setWidth(paintAdvance.width() - (complexTextRun.initialAdvance().width() - currentGlyphOrigin.x()));
637                     paintAdvance.setHeight(paintAdvance.height() - (complexTextRun.initialAdvance().height() - currentGlyphOrigin.y()));
638                 }
639                 paintAdvance.setWidth(paintAdvance.width() + glyphOrigin(glyphIndexIntoComplexTextController + 1).x() - currentGlyphOrigin.x());
640                 paintAdvance.setHeight(paintAdvance.height() + glyphOrigin(glyphIndexIntoComplexTextController + 1).y() - currentGlyphOrigin.y());
641                 if (glyphIndexIntoCurrentRun == glyphCount - 1 && currentRunIndex + 1 < runCount) {
642                     // Our paint advance points to the end of the run. However, the next run may have an
643                     // initial advance, and our paint advance needs to point to the location of the next
644                     // glyph. So, we need to add in the next run's initial advance.
645                     paintAdvance.setWidth(paintAdvance.width() - glyphOrigin(glyphIndexIntoComplexTextController + 1).x() + m_complexTextRuns[currentRunIndex + 1]->initialAdvance().width());
646                     paintAdvance.setHeight(paintAdvance.height() - glyphOrigin(glyphIndexIntoComplexTextController + 1).y() + m_complexTextRuns[currentRunIndex + 1]->initialAdvance().height());
647                 }
648                 paintAdvance.setHeight(-paintAdvance.height()); // Increasing y points down
649                 glyphBuffer->add(m_adjustedGlyphs[glyphIndexIntoComplexTextController], &complexTextRun.font(), paintAdvance, complexTextRun.indexAt(m_glyphInCurrentRun));
650             }
651
652             unsigned oldCharacterInCurrentGlyph = m_characterInCurrentGlyph;
653             m_characterInCurrentGlyph = std::min(m_currentCharacter - complexTextRun.stringLocation(), glyphEndOffset) - glyphStartOffset;
654             m_runWidthSoFar += adjustedBaseAdvance.width() * runWidthSoFarFraction(glyphStartOffset, glyphEndOffset, oldCharacterInCurrentGlyph, iterationStyle);
655
656             if (glyphEndOffset + complexTextRun.stringLocation() > m_currentCharacter)
657                 return;
658
659             m_numGlyphsSoFar++;
660             m_glyphInCurrentRun++;
661             m_characterInCurrentGlyph = 0;
662             if (ltr) {
663                 glyphIndexIntoCurrentRun++;
664                 glyphIndexIntoComplexTextController++;
665             } else {
666                 glyphIndexIntoCurrentRun--;
667                 glyphIndexIntoComplexTextController--;
668             }
669         }
670         currentRunIndex = incrementCurrentRun(indexOfLeftmostGlyphInCurrentRun);
671         m_glyphInCurrentRun = 0;
672     }
673 }
674
675 static inline std::pair<bool, bool> expansionLocation(bool ideograph, bool treatAsSpace, bool ltr, bool isAfterExpansion, bool forbidLeadingExpansion, bool forbidTrailingExpansion, bool forceLeadingExpansion, bool forceTrailingExpansion)
676 {
677     bool expandLeft = ideograph;
678     bool expandRight = ideograph;
679     if (treatAsSpace) {
680         if (ltr)
681             expandRight = true;
682         else
683             expandLeft = true;
684     }
685     if (isAfterExpansion)
686         expandLeft = false;
687     ASSERT(!forbidLeadingExpansion || !forceLeadingExpansion);
688     ASSERT(!forbidTrailingExpansion || !forceTrailingExpansion);
689     if (forbidLeadingExpansion)
690         expandLeft = false;
691     if (forbidTrailingExpansion)
692         expandRight = false;
693     if (forceLeadingExpansion)
694         expandLeft = true;
695     if (forceTrailingExpansion)
696         expandRight = true;
697     return std::make_pair(expandLeft, expandRight);
698 }
699
700 void ComplexTextController::adjustGlyphsAndAdvances()
701 {
702     bool afterExpansion = (m_run.expansionBehavior() & LeadingExpansionMask) == ForbidLeadingExpansion;
703     float widthSinceLastCommit = 0;
704     size_t runCount = m_complexTextRuns.size();
705     bool hasExtraSpacing = (m_font.letterSpacing() || m_font.wordSpacing() || m_expansion) && !m_run.spacingDisabled();
706     bool runForcesLeadingExpansion = (m_run.expansionBehavior() & LeadingExpansionMask) == ForceLeadingExpansion;
707     bool runForcesTrailingExpansion = (m_run.expansionBehavior() & TrailingExpansionMask) == ForceTrailingExpansion;
708     bool runForbidsLeadingExpansion = (m_run.expansionBehavior() & LeadingExpansionMask) == ForbidLeadingExpansion;
709     bool runForbidsTrailingExpansion = (m_run.expansionBehavior() & TrailingExpansionMask) == ForbidTrailingExpansion;
710
711     // We are iterating in glyph order, not string order. Compare this to WidthIterator::advanceInternal()
712     for (size_t runIndex = 0; runIndex < runCount; ++runIndex) {
713         ComplexTextRun& complexTextRun = *m_complexTextRuns[runIndex];
714         unsigned glyphCount = complexTextRun.glyphCount();
715         const Font& font = complexTextRun.font();
716
717         if (!complexTextRun.isLTR())
718             m_isLTROnly = false;
719
720         const CGGlyph* glyphs = complexTextRun.glyphs();
721         const FloatSize* advances = complexTextRun.baseAdvances();
722
723         float spaceWidth = font.spaceWidth() - font.syntheticBoldOffset();
724         const UChar* cp = complexTextRun.characters();
725         FloatPoint glyphOrigin;
726         unsigned lastCharacterIndex = m_run.ltr() ? std::numeric_limits<unsigned>::min() : std::numeric_limits<unsigned>::max();
727         bool isMonotonic = true;
728
729         for (unsigned i = 0; i < glyphCount; i++) {
730             unsigned characterIndex = complexTextRun.indexAt(i);
731             if (m_run.ltr()) {
732                 if (characterIndex < lastCharacterIndex)
733                     isMonotonic = false;
734             } else {
735                 if (characterIndex > lastCharacterIndex)
736                     isMonotonic = false;
737             }
738             UChar ch = *(cp + characterIndex);
739
740             bool treatAsSpace = FontCascade::treatAsSpace(ch);
741             CGGlyph glyph = treatAsSpace ? font.spaceGlyph() : glyphs[i];
742             FloatSize advance = treatAsSpace ? FloatSize(spaceWidth, advances[i].height()) : advances[i];
743
744             if (ch == '\t' && m_run.allowTabs())
745                 advance.setWidth(m_font.tabWidth(font, m_run.tabSize(), m_run.xPos() + m_totalWidth + widthSinceLastCommit));
746             else if (FontCascade::treatAsZeroWidthSpace(ch) && !treatAsSpace) {
747                 advance.setWidth(0);
748                 glyph = font.spaceGlyph();
749             }
750
751             if (!i) {
752                 advance.expand(complexTextRun.initialAdvance().width(), complexTextRun.initialAdvance().height());
753                 if (auto* origins = complexTextRun.glyphOrigins())
754                     advance.expand(-origins[0].x(), -origins[0].y());
755             }
756
757             advance.expand(font.syntheticBoldOffset(), 0);
758
759             if (hasExtraSpacing) {
760                 // If we're a glyph with an advance, add in letter-spacing.
761                 // That way we weed out zero width lurkers. This behavior matches the fast text code path.
762                 if (advance.width())
763                     advance.expand(m_font.letterSpacing(), 0);
764
765                 unsigned characterIndexInRun = characterIndex + complexTextRun.stringLocation();
766                 bool isFirstCharacter = !(characterIndex + complexTextRun.stringLocation());
767                 bool isLastCharacter = characterIndexInRun + 1 == m_run.length() || (U16_IS_LEAD(ch) && characterIndexInRun + 2 == m_run.length() && U16_IS_TRAIL(*(cp + characterIndex + 1)));
768
769                 bool forceLeadingExpansion = false; // On the left, regardless of m_run.ltr()
770                 bool forceTrailingExpansion = false; // On the right, regardless of m_run.ltr()
771                 bool forbidLeadingExpansion = false;
772                 bool forbidTrailingExpansion = false;
773                 if (runForcesLeadingExpansion)
774                     forceLeadingExpansion = m_run.ltr() ? isFirstCharacter : isLastCharacter;
775                 if (runForcesTrailingExpansion)
776                     forceTrailingExpansion = m_run.ltr() ? isLastCharacter : isFirstCharacter;
777                 if (runForbidsLeadingExpansion)
778                     forbidLeadingExpansion = m_run.ltr() ? isFirstCharacter : isLastCharacter;
779                 if (runForbidsTrailingExpansion)
780                     forbidTrailingExpansion = m_run.ltr() ? isLastCharacter : isFirstCharacter;
781                 // Handle justification and word-spacing.
782                 bool ideograph = FontCascade::isCJKIdeographOrSymbol(ch);
783                 if (treatAsSpace || ideograph || forceLeadingExpansion || forceTrailingExpansion) {
784                     // Distribute the run's total expansion evenly over all expansion opportunities in the run.
785                     if (m_expansion) {
786                         bool expandLeft, expandRight;
787                         std::tie(expandLeft, expandRight) = expansionLocation(ideograph, treatAsSpace, m_run.ltr(), afterExpansion, forbidLeadingExpansion, forbidTrailingExpansion, forceLeadingExpansion, forceTrailingExpansion);
788                         m_expansion -= m_expansionPerOpportunity;
789                         advance.expand(m_expansionPerOpportunity, 0);
790                         if (expandLeft) {
791                             // Increase previous width
792                             if (m_adjustedBaseAdvances.isEmpty())
793                                 complexTextRun.growInitialAdvanceHorizontally(m_expansionPerOpportunity);
794                             else
795                                 m_adjustedBaseAdvances.last().expand(m_expansionPerOpportunity, 0);
796                         }
797                         if (expandRight)
798                             afterExpansion = true;
799                     } else
800                         afterExpansion = false;
801
802                     // Account for word-spacing.
803                     if (treatAsSpace && (ch != '\t' || !m_run.allowTabs()) && (characterIndex > 0 || runIndex > 0) && m_font.wordSpacing())
804                         advance.expand(m_font.wordSpacing(), 0);
805                 } else
806                     afterExpansion = false;
807             }
808
809             widthSinceLastCommit += advance.width();
810
811             // FIXME: Combining marks should receive a text emphasis mark if they are combine with a space.
812             if (m_forTextEmphasis && (!FontCascade::canReceiveTextEmphasis(ch) || (U_GET_GC_MASK(ch) & U_GC_M_MASK)))
813                 glyph = 0;
814
815             m_adjustedBaseAdvances.append(advance);
816             if (auto* origins = complexTextRun.glyphOrigins()) {
817                 ASSERT(m_glyphOrigins.size() < m_adjustedBaseAdvances.size());
818                 m_glyphOrigins.grow(m_adjustedBaseAdvances.size());
819                 m_glyphOrigins[m_glyphOrigins.size() - 1] = origins[i];
820                 ASSERT(m_glyphOrigins.size() == m_adjustedBaseAdvances.size());
821             }
822             m_adjustedGlyphs.append(glyph);
823             
824             FloatRect glyphBounds = font.boundsForGlyph(glyph);
825             glyphBounds.move(glyphOrigin.x(), glyphOrigin.y());
826             m_minGlyphBoundingBoxX = std::min(m_minGlyphBoundingBoxX, glyphBounds.x());
827             m_maxGlyphBoundingBoxX = std::max(m_maxGlyphBoundingBoxX, glyphBounds.maxX());
828             m_minGlyphBoundingBoxY = std::min(m_minGlyphBoundingBoxY, glyphBounds.y());
829             m_maxGlyphBoundingBoxY = std::max(m_maxGlyphBoundingBoxY, glyphBounds.maxY());
830             glyphOrigin.move(advance);
831             
832             lastCharacterIndex = characterIndex;
833         }
834         if (!isMonotonic)
835             complexTextRun.setIsNonMonotonic();
836     }
837
838     m_totalWidth += widthSinceLastCommit;
839 }
840
841 // Missing glyphs run constructor. Core Text will not generate a run of missing glyphs, instead falling back on
842 // glyphs from LastResort. We want to use the primary font's missing glyph in order to match the fast text code path.
843 ComplexTextController::ComplexTextRun::ComplexTextRun(const Font& font, const UChar* characters, unsigned stringLocation, unsigned stringLength, unsigned indexBegin, unsigned indexEnd, bool ltr)
844     : m_font(font)
845     , m_characters(characters)
846     , m_stringLength(stringLength)
847     , m_indexBegin(indexBegin)
848     , m_indexEnd(indexEnd)
849     , m_stringLocation(stringLocation)
850     , m_isLTR(ltr)
851 {
852     auto runLengthInCodeUnits = m_indexEnd - m_indexBegin;
853     m_coreTextIndices.reserveInitialCapacity(runLengthInCodeUnits);
854     unsigned r = m_indexBegin;
855     while (r < m_indexEnd) {
856         m_coreTextIndices.uncheckedAppend(r);
857         UChar32 character;
858         U16_NEXT(m_characters, r, m_stringLength, character);
859     }
860     m_glyphCount = m_coreTextIndices.size();
861     if (!ltr) {
862         for (unsigned r = 0, end = m_glyphCount - 1; r < m_glyphCount / 2; ++r, --end)
863             std::swap(m_coreTextIndices[r], m_coreTextIndices[end]);
864     }
865
866     // Synthesize a run of missing glyphs.
867     m_glyphs.fill(0, m_glyphCount);
868     m_baseAdvances.fill(FloatSize(m_font.widthForGlyph(0), 0), m_glyphCount);
869 }
870
871 ComplexTextController::ComplexTextRun::ComplexTextRun(const Vector<FloatSize>& advances, const Vector<FloatPoint>& origins, const Vector<Glyph>& glyphs, const Vector<unsigned>& stringIndices, FloatSize initialAdvance, const Font& font, const UChar* characters, unsigned stringLocation, unsigned stringLength, unsigned indexBegin, unsigned indexEnd, bool ltr)
872     : m_baseAdvances(advances)
873     , m_glyphOrigins(origins)
874     , m_glyphs(glyphs)
875     , m_coreTextIndices(stringIndices)
876     , m_initialAdvance(initialAdvance)
877     , m_font(font)
878     , m_characters(characters)
879     , m_stringLength(stringLength)
880     , m_indexBegin(indexBegin)
881     , m_indexEnd(indexEnd)
882     , m_glyphCount(glyphs.size())
883     , m_stringLocation(stringLocation)
884     , m_isLTR(ltr)
885 {
886 }
887
888 } // namespace WebCore