Use Optional::valueOr() instead of Optional::value_or()
[WebKit-https.git] / Source / WebCore / platform / graphics / FontCascade.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2000 Dirk Mueller (mueller@kde.org)
5  * Copyright (C) 2003-2017 Apple Inc. All rights reserved.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25 #include "FontCascade.h"
26
27 #include "CharacterProperties.h"
28 #include "ComplexTextController.h"
29 #include "DisplayListRecorder.h"
30 #include "FloatRect.h"
31 #include "FontCache.h"
32 #include "GlyphBuffer.h"
33 #include "GraphicsContext.h"
34 #include "LayoutRect.h"
35 #include "SurrogatePairAwareTextIterator.h"
36 #include "TextRun.h"
37 #include "WidthIterator.h"
38 #include <wtf/MainThread.h>
39 #include <wtf/MathExtras.h>
40 #include <wtf/NeverDestroyed.h>
41 #include <wtf/text/AtomicStringHash.h>
42 #include <wtf/text/StringBuilder.h>
43
44 #if PLATFORM(WIN)
45 #include "UniscribeController.h"
46 #endif
47
48 namespace WebCore {
49 using namespace WTF;
50 using namespace Unicode;
51
52 static bool useBackslashAsYenSignForFamily(const AtomicString& family)
53 {
54     if (family.isEmpty())
55         return false;
56     static const auto set = makeNeverDestroyed([] {
57         HashSet<AtomicString> set;
58         auto add = [&set] (const char* name, std::initializer_list<UChar> unicodeName) {
59             unsigned nameLength = strlen(name);
60             set.add(AtomicString { name, nameLength, AtomicString::ConstructFromLiteral });
61             unsigned unicodeNameLength = unicodeName.size();
62             set.add(AtomicString { unicodeName.begin(), unicodeNameLength });
63         };
64         add("MS PGothic", { 0xFF2D, 0xFF33, 0x0020, 0xFF30, 0x30B4, 0x30B7, 0x30C3, 0x30AF });
65         add("MS PMincho", { 0xFF2D, 0xFF33, 0x0020, 0xFF30, 0x660E, 0x671D });
66         add("MS Gothic", { 0xFF2D, 0xFF33, 0x0020, 0x30B4, 0x30B7, 0x30C3, 0x30AF });
67         add("MS Mincho", { 0xFF2D, 0xFF33, 0x0020, 0x660E, 0x671D });
68         add("Meiryo", { 0x30E1, 0x30A4, 0x30EA, 0x30AA });
69         return set;
70     }());
71     return set.get().contains(family);
72 }
73
74 FontCascade::CodePath FontCascade::s_codePath = Auto;
75
76 // ============================================================================================
77 // FontCascade Implementation (Cross-Platform Portion)
78 // ============================================================================================
79
80 FontCascade::FontCascade()
81 {
82 }
83
84 FontCascade::FontCascade(FontCascadeDescription&& fd, float letterSpacing, float wordSpacing)
85     : m_fontDescription(WTFMove(fd))
86     , m_letterSpacing(letterSpacing)
87     , m_wordSpacing(wordSpacing)
88     , m_useBackslashAsYenSymbol(useBackslashAsYenSignForFamily(m_fontDescription.firstFamily()))
89     , m_enableKerning(computeEnableKerning())
90     , m_requiresShaping(computeRequiresShaping())
91 {
92 }
93
94 // FIXME: We should make this constructor platform-independent.
95 FontCascade::FontCascade(const FontPlatformData& fontData, FontSmoothingMode fontSmoothingMode)
96     : m_fonts(FontCascadeFonts::createForPlatformFont(fontData))
97     , m_enableKerning(computeEnableKerning())
98     , m_requiresShaping(computeRequiresShaping())
99 {
100     m_fontDescription.setFontSmoothing(fontSmoothingMode);
101 #if PLATFORM(IOS_FAMILY)
102     m_fontDescription.setSpecifiedSize(CTFontGetSize(fontData.font()));
103     m_fontDescription.setComputedSize(CTFontGetSize(fontData.font()));
104     m_fontDescription.setIsItalic(CTFontGetSymbolicTraits(fontData.font()) & kCTFontTraitItalic);
105     m_fontDescription.setWeight((CTFontGetSymbolicTraits(fontData.font()) & kCTFontTraitBold) ? boldWeightValue() : normalWeightValue());
106 #endif
107 }
108
109 FontCascade::FontCascade(const FontCascade& other)
110     : m_fontDescription(other.m_fontDescription)
111     , m_fonts(other.m_fonts)
112     , m_letterSpacing(other.m_letterSpacing)
113     , m_wordSpacing(other.m_wordSpacing)
114     , m_useBackslashAsYenSymbol(other.m_useBackslashAsYenSymbol)
115     , m_enableKerning(computeEnableKerning())
116     , m_requiresShaping(computeRequiresShaping())
117 {
118 }
119
120 FontCascade& FontCascade::operator=(const FontCascade& other)
121 {
122     m_fontDescription = other.m_fontDescription;
123     m_fonts = other.m_fonts;
124     m_letterSpacing = other.m_letterSpacing;
125     m_wordSpacing = other.m_wordSpacing;
126     m_useBackslashAsYenSymbol = other.m_useBackslashAsYenSymbol;
127     m_enableKerning = other.m_enableKerning;
128     m_requiresShaping = other.m_requiresShaping;
129     return *this;
130 }
131
132 bool FontCascade::operator==(const FontCascade& other) const
133 {
134     if (isLoadingCustomFonts() || other.isLoadingCustomFonts())
135         return false;
136
137     if (m_fontDescription != other.m_fontDescription || m_letterSpacing != other.m_letterSpacing || m_wordSpacing != other.m_wordSpacing)
138         return false;
139     if (m_fonts == other.m_fonts)
140         return true;
141     if (!m_fonts || !other.m_fonts)
142         return false;
143     if (m_fonts->fontSelector() != other.m_fonts->fontSelector())
144         return false;
145     // Can these cases actually somehow occur? All fonts should get wiped out by full style recalc.
146     if (m_fonts->fontSelectorVersion() != other.m_fonts->fontSelectorVersion())
147         return false;
148     if (m_fonts->generation() != other.m_fonts->generation())
149         return false;
150     return true;
151 }
152
153 struct FontCascadeCacheKey {
154     FontDescriptionKey fontDescriptionKey; // Shared with the lower level FontCache (caching Font objects)
155     Vector<AtomicString, 3> families;
156     unsigned fontSelectorId;
157     unsigned fontSelectorVersion;
158 };
159
160 struct FontCascadeCacheEntry {
161     WTF_MAKE_FAST_ALLOCATED;
162 public:
163     FontCascadeCacheEntry(FontCascadeCacheKey&& key, Ref<FontCascadeFonts>&& fonts)
164         : key(WTFMove(key))
165         , fonts(WTFMove(fonts))
166     { }
167     FontCascadeCacheKey key;
168     Ref<FontCascadeFonts> fonts;
169 };
170
171 // FIXME: Should make hash traits for FontCascadeCacheKey instead of using a hash as the key (so we hash a hash).
172 typedef HashMap<unsigned, std::unique_ptr<FontCascadeCacheEntry>, AlreadyHashed> FontCascadeCache;
173
174 static bool keysMatch(const FontCascadeCacheKey& a, const FontCascadeCacheKey& b)
175 {
176     if (a.fontDescriptionKey != b.fontDescriptionKey)
177         return false;
178     if (a.fontSelectorId != b.fontSelectorId || a.fontSelectorVersion != b.fontSelectorVersion)
179         return false;
180     unsigned size = a.families.size();
181     if (size != b.families.size())
182         return false;
183     for (unsigned i = 0; i < size; ++i) {
184         if (!FontCascadeDescription::familyNamesAreEqual(a.families[i], b.families[i]))
185             return false;
186     }
187     return true;
188 }
189
190 static FontCascadeCache& fontCascadeCache()
191 {
192     static NeverDestroyed<FontCascadeCache> cache;
193     return cache.get();
194 }
195
196 void invalidateFontCascadeCache()
197 {
198     fontCascadeCache().clear();
199 }
200
201 void clearWidthCaches()
202 {
203     for (auto& value : fontCascadeCache().values())
204         value->fonts.get().widthCache().clear();
205 }
206
207 static FontCascadeCacheKey makeFontCascadeCacheKey(const FontCascadeDescription& description, FontSelector* fontSelector)
208 {
209     FontCascadeCacheKey key;
210     key.fontDescriptionKey = FontDescriptionKey(description);
211     unsigned familyCount = description.familyCount();
212     key.families.reserveInitialCapacity(familyCount);
213     for (unsigned i = 0; i < familyCount; ++i)
214         key.families.uncheckedAppend(description.familyAt(i));
215     key.fontSelectorId = fontSelector ? fontSelector->uniqueId() : 0;
216     key.fontSelectorVersion = fontSelector ? fontSelector->version() : 0;
217     return key;
218 }
219
220 static unsigned computeFontCascadeCacheHash(const FontCascadeCacheKey& key)
221 {
222     // FIXME: Should hash the key and the family name characters rather than making a hash out of other hashes.
223     IntegerHasher hasher;
224     hasher.add(key.fontDescriptionKey.computeHash());
225     hasher.add(key.fontSelectorId);
226     hasher.add(key.fontSelectorVersion);
227     for (unsigned i = 0; i < key.families.size(); ++i) {
228         auto& family = key.families[i];
229         hasher.add(family.isNull() ? 0 : FontCascadeDescription::familyNameHash(family));
230     }
231     return hasher.hash();
232 }
233
234 void pruneUnreferencedEntriesFromFontCascadeCache()
235 {
236     fontCascadeCache().removeIf([](auto& entry) {
237         return entry.value->fonts.get().hasOneRef();
238     });
239 }
240
241 void pruneSystemFallbackFonts()
242 {
243     for (auto& entry : fontCascadeCache().values())
244         entry->fonts->pruneSystemFallbacks();
245 }
246
247 static Ref<FontCascadeFonts> retrieveOrAddCachedFonts(const FontCascadeDescription& fontDescription, RefPtr<FontSelector>&& fontSelector)
248 {
249     auto key = makeFontCascadeCacheKey(fontDescription, fontSelector.get());
250
251     unsigned hash = computeFontCascadeCacheHash(key);
252     auto addResult = fontCascadeCache().add(hash, nullptr);
253     if (!addResult.isNewEntry && keysMatch(addResult.iterator->value->key, key))
254         return addResult.iterator->value->fonts.get();
255
256     auto& newEntry = addResult.iterator->value;
257     newEntry = std::make_unique<FontCascadeCacheEntry>(WTFMove(key), FontCascadeFonts::create(WTFMove(fontSelector)));
258     Ref<FontCascadeFonts> glyphs = newEntry->fonts.get();
259
260     static const unsigned unreferencedPruneInterval = 50;
261     static const int maximumEntries = 400;
262     static unsigned pruneCounter;
263     // Referenced FontCascadeFonts would exist anyway so pruning them saves little memory.
264     if (!(++pruneCounter % unreferencedPruneInterval))
265         pruneUnreferencedEntriesFromFontCascadeCache();
266     // Prevent pathological growth.
267     if (fontCascadeCache().size() > maximumEntries)
268         fontCascadeCache().remove(fontCascadeCache().random());
269     return glyphs;
270 }
271
272 void FontCascade::update(RefPtr<FontSelector>&& fontSelector) const
273 {
274     m_fonts = retrieveOrAddCachedFonts(m_fontDescription, WTFMove(fontSelector));
275     m_useBackslashAsYenSymbol = useBackslashAsYenSignForFamily(firstFamily());
276     m_enableKerning = computeEnableKerning();
277     m_requiresShaping = computeRequiresShaping();
278 }
279
280 float FontCascade::glyphBufferForTextRun(CodePath codePathToUse, const TextRun& run, unsigned from, unsigned to, GlyphBuffer& glyphBuffer) const
281 {
282     if (codePathToUse != Complex)
283         return getGlyphsAndAdvancesForSimpleText(run, from, to, glyphBuffer);
284     return getGlyphsAndAdvancesForComplexText(run, from, to, glyphBuffer);
285 }
286
287 float FontCascade::drawText(GraphicsContext& context, const TextRun& run, const FloatPoint& point, unsigned from, Optional<unsigned> to, CustomFontNotReadyAction customFontNotReadyAction) const
288 {
289     unsigned destination = to.valueOr(run.length());
290     GlyphBuffer glyphBuffer;
291     float startX = point.x() + glyphBufferForTextRun(codePath(run, from, to), run, from, destination, glyphBuffer);
292     // We couldn't generate any glyphs for the run. Give up.
293     if (glyphBuffer.isEmpty())
294         return 0;
295     // Draw the glyph buffer now at the starting point returned in startX.
296     FloatPoint startPoint(startX, point.y());
297     drawGlyphBuffer(context, glyphBuffer, startPoint, customFontNotReadyAction);
298     return startPoint.x() - startX;
299 }
300
301 void FontCascade::drawEmphasisMarks(GraphicsContext& context, const TextRun& run, const AtomicString& mark, const FloatPoint& point, unsigned from, Optional<unsigned> to) const
302 {
303     if (isLoadingCustomFonts())
304         return;
305
306     unsigned destination = to.valueOr(run.length());
307     if (codePath(run, from, to) != Complex)
308         drawEmphasisMarksForSimpleText(context, run, mark, point, from, destination);
309     else
310         drawEmphasisMarksForComplexText(context, run, mark, point, from, destination);
311 }
312
313 std::unique_ptr<DisplayList::DisplayList> FontCascade::displayListForTextRun(GraphicsContext& context, const TextRun& run, unsigned from, Optional<unsigned> to, CustomFontNotReadyAction customFontNotReadyAction) const
314 {
315     ASSERT(!context.paintingDisabled());
316     unsigned destination = to.valueOr(run.length());
317     
318     // FIXME: Use the fast code path once it handles partial runs with kerning and ligatures. See http://webkit.org/b/100050
319     CodePath codePathToUse = codePath(run);
320     if (codePathToUse != Complex && (enableKerning() || requiresShaping()) && (from || destination != run.length()))
321         codePathToUse = Complex;
322     
323     GlyphBuffer glyphBuffer;
324     float startX = glyphBufferForTextRun(codePathToUse, run, from, destination, glyphBuffer);
325     // We couldn't generate any glyphs for the run. Give up.
326     if (glyphBuffer.isEmpty())
327         return nullptr;
328     
329     std::unique_ptr<DisplayList::DisplayList> displayList = std::make_unique<DisplayList::DisplayList>();
330     GraphicsContext recordingContext([&](GraphicsContext& displayListContext) {
331         return std::make_unique<DisplayList::Recorder>(displayListContext, *displayList, context.state(), FloatRect(), AffineTransform());
332     });
333     
334     FloatPoint startPoint(startX, 0);
335     drawGlyphBuffer(recordingContext, glyphBuffer, startPoint, customFontNotReadyAction);
336     return displayList;
337 }
338     
339 float FontCascade::widthOfTextRange(const TextRun& run, unsigned from, unsigned to, HashSet<const Font*>* fallbackFonts, float* outWidthBeforeRange, float* outWidthAfterRange) const
340 {
341     ASSERT(from <= to);
342     ASSERT(to <= run.length());
343
344     if (!run.length())
345         return 0;
346
347     float offsetBeforeRange = 0;
348     float offsetAfterRange = 0;
349     float totalWidth = 0;
350
351     auto codePathToUse = codePath(run);
352     if (codePathToUse == Complex) {
353 #if PLATFORM(WIN)
354         UniscribeController it(this, run);
355         it.advance(from);
356         offsetBeforeRange = it.runWidthSoFar();
357         it.advance(to);
358         offsetAfterRange = it.runWidthSoFar();
359         it.advance(to);
360         totalWidth = it.runWidthSoFar();
361 #else
362         ComplexTextController complexIterator(*this, run, false, fallbackFonts);
363         complexIterator.advance(from, nullptr, IncludePartialGlyphs, fallbackFonts);
364         offsetBeforeRange = complexIterator.runWidthSoFar();
365         complexIterator.advance(to, nullptr, IncludePartialGlyphs, fallbackFonts);
366         offsetAfterRange = complexIterator.runWidthSoFar();
367         complexIterator.advance(run.length(), nullptr, IncludePartialGlyphs, fallbackFonts);
368         totalWidth = complexIterator.runWidthSoFar();
369 #endif
370     } else {
371         WidthIterator simpleIterator(this, run, fallbackFonts);
372         simpleIterator.advance(from, nullptr);
373         offsetBeforeRange = simpleIterator.runWidthSoFar();
374         simpleIterator.advance(to, nullptr);
375         offsetAfterRange = simpleIterator.runWidthSoFar();
376         simpleIterator.advance(run.length(), nullptr);
377         totalWidth = simpleIterator.runWidthSoFar();
378     }
379
380     if (outWidthBeforeRange)
381         *outWidthBeforeRange = offsetBeforeRange;
382
383     if (outWidthAfterRange)
384         *outWidthAfterRange = totalWidth - offsetAfterRange;
385
386     return offsetAfterRange - offsetBeforeRange;
387 }
388
389 float FontCascade::width(const TextRun& run, HashSet<const Font*>* fallbackFonts, GlyphOverflow* glyphOverflow) const
390 {
391     if (!run.length())
392         return 0;
393
394     CodePath codePathToUse = codePath(run);
395     if (codePathToUse != Complex) {
396         // The complex path is more restrictive about returning fallback fonts than the simple path, so we need an explicit test to make their behaviors match.
397         if (!canReturnFallbackFontsForComplexText())
398             fallbackFonts = nullptr;
399         // The simple path can optimize the case where glyph overflow is not observable.
400         if (codePathToUse != SimpleWithGlyphOverflow && (glyphOverflow && !glyphOverflow->computeBounds))
401             glyphOverflow = nullptr;
402     }
403
404     bool hasWordSpacingOrLetterSpacing = wordSpacing() || letterSpacing();
405     float* cacheEntry = m_fonts->widthCache().add(run, std::numeric_limits<float>::quiet_NaN(), enableKerning() || requiresShaping(), hasWordSpacingOrLetterSpacing, glyphOverflow);
406     if (cacheEntry && !std::isnan(*cacheEntry))
407         return *cacheEntry;
408
409     HashSet<const Font*> localFallbackFonts;
410     if (!fallbackFonts)
411         fallbackFonts = &localFallbackFonts;
412
413     float result;
414     if (codePathToUse == Complex)
415         result = floatWidthForComplexText(run, fallbackFonts, glyphOverflow);
416     else
417         result = floatWidthForSimpleText(run, fallbackFonts, glyphOverflow);
418
419     if (cacheEntry && fallbackFonts->isEmpty())
420         *cacheEntry = result;
421     return result;
422 }
423
424 float FontCascade::widthForSimpleText(StringView text) const
425 {
426     if (text.isNull() || text.isEmpty())
427         return 0;
428     ASSERT(codePath(TextRun(text)) != FontCascade::Complex);
429     float* cacheEntry = m_fonts->widthCache().add(text, std::numeric_limits<float>::quiet_NaN());
430     if (cacheEntry && !std::isnan(*cacheEntry))
431         return *cacheEntry;
432
433     Vector<GlyphBufferGlyph, 16> glyphs;
434     Vector<GlyphBufferAdvance, 16> advances;
435     bool hasKerningOrLigatures = enableKerning() || requiresShaping();
436     float runWidth = 0;
437     auto& font = primaryFont();
438     for (unsigned i = 0; i < text.length(); ++i) {
439         auto glyph = glyphDataForCharacter(text[i], false).glyph;
440         auto glyphWidth = font.widthForGlyph(glyph);
441         runWidth += glyphWidth;
442         if (!hasKerningOrLigatures)
443             continue;
444         glyphs.append(glyph);
445         advances.append(FloatSize(glyphWidth, 0));
446     }
447     if (hasKerningOrLigatures) {
448         font.applyTransforms(&glyphs[0], &advances[0], glyphs.size(), enableKerning(), requiresShaping());
449         // This is needed only to match the result of the slow path. Same glyph widths but different floating point arithmentics can
450         // produce different run width.
451         float runWidthDifferenceWithTransformApplied = -runWidth;
452         for (auto& advance : advances)
453             runWidthDifferenceWithTransformApplied += advance.width();
454         runWidth += runWidthDifferenceWithTransformApplied;
455     }
456
457     if (cacheEntry)
458         *cacheEntry = runWidth;
459     return runWidth;
460 }
461
462 GlyphData FontCascade::glyphDataForCharacter(UChar32 c, bool mirror, FontVariant variant) const
463 {
464     if (variant == AutoVariant) {
465         if (m_fontDescription.variantCaps() == FontVariantCaps::Small) {
466             UChar32 upperC = u_toupper(c);
467             if (upperC != c) {
468                 c = upperC;
469                 variant = SmallCapsVariant;
470             } else
471                 variant = NormalVariant;
472         } else
473             variant = NormalVariant;
474     }
475
476     if (mirror)
477         c = u_charMirror(c);
478
479     return m_fonts->glyphDataForCharacter(c, m_fontDescription, variant);
480 }
481
482 // For font families where any of the fonts don't have a valid entry in the OS/2 table
483 // for avgCharWidth, fallback to the legacy webkit behavior of getting the avgCharWidth
484 // from the width of a '0'. This only seems to apply to a fixed number of Mac fonts,
485 // but, in order to get similar rendering across platforms, we do this check for
486 // all platforms.
487 bool FontCascade::hasValidAverageCharWidth() const
488 {
489     const AtomicString& family = firstFamily();
490     if (family.isEmpty())
491         return false;
492
493 #if PLATFORM(COCOA)
494     // Internal fonts on macOS and iOS also have an invalid entry in the table for avgCharWidth.
495     if (primaryFontIsSystemFont())
496         return false;
497 #endif
498
499     static const auto map = makeNeverDestroyed(HashSet<AtomicString> {
500         "American Typewriter",
501         "Arial Hebrew",
502         "Chalkboard",
503         "Cochin",
504         "Corsiva Hebrew",
505         "Courier",
506         "Euphemia UCAS",
507         "Geneva",
508         "Gill Sans",
509         "Hei",
510         "Helvetica",
511         "Hoefler Text",
512         "InaiMathi",
513         "Kai",
514         "Lucida Grande",
515         "Marker Felt",
516         "Monaco",
517         "Mshtakan",
518         "New Peninim MT",
519         "Osaka",
520         "Raanana",
521         "STHeiti",
522         "Symbol",
523         "Times",
524         "Apple Braille",
525         "Apple LiGothic",
526         "Apple LiSung",
527         "Apple Symbols",
528         "AppleGothic",
529         "AppleMyungjo",
530         "#GungSeo",
531         "#HeadLineA",
532         "#PCMyungjo",
533         "#PilGi",
534     });
535     return !map.get().contains(family);
536 }
537
538 bool FontCascade::fastAverageCharWidthIfAvailable(float& width) const
539 {
540     bool success = hasValidAverageCharWidth();
541     if (success)
542         width = roundf(primaryFont().avgCharWidth()); // FIXME: primaryFont() might not correspond to firstFamily().
543     return success;
544 }
545
546 void FontCascade::adjustSelectionRectForText(const TextRun& run, LayoutRect& selectionRect, unsigned from, Optional<unsigned> to) const
547 {
548     unsigned destination = to.valueOr(run.length());
549     if (codePath(run, from, to) != Complex)
550         return adjustSelectionRectForSimpleText(run, selectionRect, from, destination);
551
552     return adjustSelectionRectForComplexText(run, selectionRect, from, destination);
553 }
554
555 int FontCascade::offsetForPosition(const TextRun& run, float x, bool includePartialGlyphs) const
556 {
557     if (codePath(run, x) != Complex)
558         return offsetForPositionForSimpleText(run, x, includePartialGlyphs);
559
560     return offsetForPositionForComplexText(run, x, includePartialGlyphs);
561 }
562
563 template <typename CharacterType>
564 static inline String normalizeSpacesInternal(const CharacterType* characters, unsigned length)
565 {
566     StringBuilder normalized;
567     normalized.reserveCapacity(length);
568
569     for (unsigned i = 0; i < length; ++i)
570         normalized.append(FontCascade::normalizeSpaces(characters[i]));
571
572     return normalized.toString();
573 }
574
575 String FontCascade::normalizeSpaces(const LChar* characters, unsigned length)
576 {
577     return normalizeSpacesInternal(characters, length);
578 }
579
580 String FontCascade::normalizeSpaces(const UChar* characters, unsigned length)
581 {
582     return normalizeSpacesInternal(characters, length);
583 }
584
585 static bool shouldUseFontSmoothing = true;
586
587 void FontCascade::setShouldUseSmoothing(bool shouldUseSmoothing)
588 {
589     ASSERT(isMainThread());
590     shouldUseFontSmoothing = shouldUseSmoothing;
591 }
592
593 bool FontCascade::shouldUseSmoothing()
594 {
595     return shouldUseFontSmoothing;
596 }
597
598 #if !PLATFORM(COCOA)
599 bool FontCascade::isSubpixelAntialiasingAvailable()
600 {
601     return false;
602 }
603 #endif
604
605 void FontCascade::setCodePath(CodePath p)
606 {
607     s_codePath = p;
608 }
609
610 FontCascade::CodePath FontCascade::codePath()
611 {
612     return s_codePath;
613 }
614
615 FontCascade::CodePath FontCascade::codePath(const TextRun& run, Optional<unsigned> from, Optional<unsigned> to) const
616 {
617     if (s_codePath != Auto)
618         return s_codePath;
619
620 #if !USE(FREETYPE)
621     // FIXME: Use the fast code path once it handles partial runs with kerning and ligatures. See http://webkit.org/b/100050
622     if ((enableKerning() || requiresShaping()) && (from.valueOr(0) || to.valueOr(run.length()) != run.length()))
623         return Complex;
624 #else
625     UNUSED_PARAM(from);
626     UNUSED_PARAM(to);
627 #endif
628
629 #if PLATFORM(COCOA) || USE(FREETYPE)
630     // Because Font::applyTransforms() doesn't know which features to enable/disable in the simple code path, it can't properly handle feature or variant settings.
631     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150791: @font-face features should also cause this to be complex.
632     if (m_fontDescription.featureSettings().size() > 0 || !m_fontDescription.variantSettings().isAllNormal())
633         return Complex;
634
635 #else
636
637     if (run.length() > 1 && (enableKerning() || requiresShaping()))
638         return Complex;
639 #endif
640
641     if (!run.characterScanForCodePath())
642         return Simple;
643
644     if (run.is8Bit())
645         return Simple;
646
647     // Start from 0 since drawing and highlighting also measure the characters before run->from.
648     return characterRangeCodePath(run.characters16(), run.length());
649 }
650
651 FontCascade::CodePath FontCascade::characterRangeCodePath(const UChar* characters, unsigned len)
652 {
653     // FIXME: Should use a UnicodeSet in ports where ICU is used. Note that we 
654     // can't simply use UnicodeCharacter Property/class because some characters
655     // are not 'combining', but still need to go to the complex path.
656     // Alternatively, we may as well consider binary search over a sorted
657     // list of ranges.
658     CodePath result = Simple;
659     bool previousCharacterIsEmojiGroupCandidate = false;
660     for (unsigned i = 0; i < len; i++) {
661         const UChar c = characters[i];
662         if (c == zeroWidthJoiner && previousCharacterIsEmojiGroupCandidate)
663             return Complex;
664         
665         previousCharacterIsEmojiGroupCandidate = false;
666         if (c < 0x2E5) // U+02E5 through U+02E9 (Modifier Letters : Tone letters)  
667             continue;
668         if (c <= 0x2E9) 
669             return Complex;
670
671         if (c < 0x300) // U+0300 through U+036F Combining diacritical marks
672             continue;
673         if (c <= 0x36F)
674             return Complex;
675
676         if (c < 0x0591 || c == 0x05BE) // U+0591 through U+05CF excluding U+05BE Hebrew combining marks, Hebrew punctuation Paseq, Sof Pasuq and Nun Hafukha
677             continue;
678         if (c <= 0x05CF)
679             return Complex;
680
681         // U+0600 through U+109F Arabic, Syriac, Thaana, NKo, Samaritan, Mandaic,
682         // Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, 
683         // Malayalam, Sinhala, Thai, Lao, Tibetan, Myanmar
684         if (c < 0x0600) 
685             continue;
686         if (c <= 0x109F)
687             return Complex;
688
689         // U+1100 through U+11FF Hangul Jamo (only Ancient Korean should be left here if you precompose;
690         // Modern Korean will be precomposed as a result of step A)
691         if (c < 0x1100)
692             continue;
693         if (c <= 0x11FF)
694             return Complex;
695
696         if (c < 0x135D) // U+135D through U+135F Ethiopic combining marks
697             continue;
698         if (c <= 0x135F)
699             return Complex;
700
701         if (c < 0x1700) // U+1780 through U+18AF Tagalog, Hanunoo, Buhid, Taghanwa,Khmer, Mongolian
702             continue;
703         if (c <= 0x18AF)
704             return Complex;
705
706         if (c < 0x1900) // U+1900 through U+194F Limbu (Unicode 4.0)
707             continue;
708         if (c <= 0x194F)
709             return Complex;
710
711         if (c < 0x1980) // U+1980 through U+19DF New Tai Lue
712             continue;
713         if (c <= 0x19DF)
714             return Complex;
715
716         if (c < 0x1A00) // U+1A00 through U+1CFF Buginese, Tai Tham, Balinese, Batak, Lepcha, Vedic
717             continue;
718         if (c <= 0x1CFF)
719             return Complex;
720
721         if (c < 0x1DC0) // U+1DC0 through U+1DFF Comining diacritical mark supplement
722             continue;
723         if (c <= 0x1DFF)
724             return Complex;
725
726         // U+1E00 through U+2000 characters with diacritics and stacked diacritics
727         if (c <= 0x2000) {
728             result = SimpleWithGlyphOverflow;
729             continue;
730         }
731
732         if (c < 0x20D0) // U+20D0 through U+20FF Combining marks for symbols
733             continue;
734         if (c <= 0x20FF)
735             return Complex;
736
737         if (c < 0x26F9)
738             continue;
739         if (c < 0x26FA)
740             return Complex;
741
742         if (c < 0x2CEF) // U+2CEF through U+2CF1 Combining marks for Coptic
743             continue;
744         if (c <= 0x2CF1)
745             return Complex;
746
747         if (c < 0x302A) // U+302A through U+302F Ideographic and Hangul Tone marks
748             continue;
749         if (c <= 0x302F)
750             return Complex;
751
752         if (c < 0xA67C) // U+A67C through U+A67D Combining marks for old Cyrillic
753             continue;
754         if (c <= 0xA67D)
755             return Complex;
756
757         if (c < 0xA6F0) // U+A6F0 through U+A6F1 Combining mark for Bamum
758             continue;
759         if (c <= 0xA6F1)
760             return Complex;
761
762         // U+A800 through U+ABFF Nagri, Phags-pa, Saurashtra, Devanagari Extended,
763         // Hangul Jamo Ext. A, Javanese, Myanmar Extended A, Tai Viet, Meetei Mayek,
764         if (c < 0xA800) 
765             continue;
766         if (c <= 0xABFF)
767             return Complex;
768
769         if (c < 0xD7B0) // U+D7B0 through U+D7FF Hangul Jamo Ext. B
770             continue;
771         if (c <= 0xD7FF)
772             return Complex;
773
774         if (c <= 0xDBFF) {
775             // High surrogate
776
777             if (i == len - 1)
778                 continue;
779
780             UChar next = characters[++i];
781             if (!U16_IS_TRAIL(next))
782                 continue;
783
784             UChar32 supplementaryCharacter = U16_GET_SUPPLEMENTARY(c, next);
785
786             if (supplementaryCharacter < 0x10A00)
787                 continue;
788             if (supplementaryCharacter < 0x10A60) // Kharoshthi
789                 return Complex;
790             if (supplementaryCharacter < 0x11000)
791                 continue;
792             if (supplementaryCharacter < 0x11080) // Brahmi
793                 return Complex;
794             if (supplementaryCharacter < 0x110D0) // Kaithi
795                 return Complex;
796             if (supplementaryCharacter < 0x11100)
797                 continue;
798             if (supplementaryCharacter < 0x11150) // Chakma
799                 return Complex;
800             if (supplementaryCharacter < 0x11180) // Mahajani
801                 return Complex;
802             if (supplementaryCharacter < 0x111E0) // Sharada
803                 return Complex;
804             if (supplementaryCharacter < 0x11200)
805                 continue;
806             if (supplementaryCharacter < 0x11250) // Khojki
807                 return Complex;
808             if (supplementaryCharacter < 0x112B0)
809                 continue;
810             if (supplementaryCharacter < 0x11300) // Khudawadi
811                 return Complex;
812             if (supplementaryCharacter < 0x11380) // Grantha
813                 return Complex;
814             if (supplementaryCharacter < 0x11400)
815                 continue;
816             if (supplementaryCharacter < 0x11480) // Newa
817                 return Complex;
818             if (supplementaryCharacter < 0x114E0) // Tirhuta
819                 return Complex;
820             if (supplementaryCharacter < 0x11580)
821                 continue;
822             if (supplementaryCharacter < 0x11600) // Siddham
823                 return Complex;
824             if (supplementaryCharacter < 0x11660) // Modi
825                 return Complex;
826             if (supplementaryCharacter < 0x11680)
827                 continue;
828             if (supplementaryCharacter < 0x116D0) // Takri
829                 return Complex;
830             if (supplementaryCharacter < 0x11C00)
831                 continue;
832             if (supplementaryCharacter < 0x11C70) // Bhaiksuki
833                 return Complex;
834             if (supplementaryCharacter < 0x11CC0) // Marchen
835                 return Complex;
836             if (supplementaryCharacter < 0x1E900)
837                 continue;
838             if (supplementaryCharacter < 0x1E960) // Adlam
839                 return Complex;
840             if (supplementaryCharacter < 0x1F1E6) // U+1F1E6 through U+1F1FF Regional Indicator Symbols
841                 continue;
842             if (supplementaryCharacter <= 0x1F1FF)
843                 return Complex;
844
845             if (isEmojiFitzpatrickModifier(supplementaryCharacter))
846                 return Complex;
847             if (isEmojiGroupCandidate(supplementaryCharacter)) {
848                 previousCharacterIsEmojiGroupCandidate = true;
849                 continue;
850             }
851
852             if (supplementaryCharacter < 0xE0000)
853                 continue;
854             if (supplementaryCharacter < 0xE0080) // Tags
855                 return Complex;
856             if (supplementaryCharacter < 0xE0100) // U+E0100 through U+E01EF Unicode variation selectors.
857                 continue;
858             if (supplementaryCharacter <= 0xE01EF)
859                 return Complex;
860
861             // FIXME: Check for Brahmi (U+11000 block), Kaithi (U+11080 block) and other complex scripts
862             // in plane 1 or higher.
863
864             continue;
865         }
866
867         if (c < 0xFE00) // U+FE00 through U+FE0F Unicode variation selectors
868             continue;
869         if (c <= 0xFE0F)
870             return Complex;
871
872         if (c < 0xFE20) // U+FE20 through U+FE2F Combining half marks
873             continue;
874         if (c <= 0xFE2F)
875             return Complex;
876     }
877     return result;
878 }
879
880 bool FontCascade::isCJKIdeograph(UChar32 c)
881 {
882     // The basic CJK Unified Ideographs block.
883     if (c >= 0x4E00 && c <= 0x9FFF)
884         return true;
885     
886     // CJK Unified Ideographs Extension A.
887     if (c >= 0x3400 && c <= 0x4DBF)
888         return true;
889     
890     // CJK Radicals Supplement.
891     if (c >= 0x2E80 && c <= 0x2EFF)
892         return true;
893     
894     // Kangxi Radicals.
895     if (c >= 0x2F00 && c <= 0x2FDF)
896         return true;
897     
898     // CJK Strokes.
899     if (c >= 0x31C0 && c <= 0x31EF)
900         return true;
901     
902     // CJK Compatibility Ideographs.
903     if (c >= 0xF900 && c <= 0xFAFF)
904         return true;
905
906     // CJK Unified Ideographs Extension B.
907     if (c >= 0x20000 && c <= 0x2A6DF)
908         return true;
909
910     // CJK Unified Ideographs Extension C.
911     if (c >= 0x2A700 && c <= 0x2B73F)
912         return true;
913     
914     // CJK Unified Ideographs Extension D.
915     if (c >= 0x2B740 && c <= 0x2B81F)
916         return true;
917     
918     // CJK Compatibility Ideographs Supplement.
919     if (c >= 0x2F800 && c <= 0x2FA1F)
920         return true;
921
922     return false;
923 }
924
925 bool FontCascade::isCJKIdeographOrSymbol(UChar32 c)
926 {
927     // 0x2C7 Caron, Mandarin Chinese 3rd Tone
928     // 0x2CA Modifier Letter Acute Accent, Mandarin Chinese 2nd Tone
929     // 0x2CB Modifier Letter Grave Access, Mandarin Chinese 4th Tone 
930     // 0x2D9 Dot Above, Mandarin Chinese 5th Tone 
931     if ((c == 0x2C7) || (c == 0x2CA) || (c == 0x2CB) || (c == 0x2D9))
932         return true;
933
934     if ((c == 0x2020) || (c == 0x2021) || (c == 0x2030) || (c == 0x203B) || (c == 0x203C)
935         || (c == 0x2042) || (c == 0x2047) || (c == 0x2048) || (c == 0x2049) || (c == 0x2051)
936         || (c == 0x20DD) || (c == 0x20DE) || (c == 0x2100) || (c == 0x2103) || (c == 0x2105)
937         || (c == 0x2109) || (c == 0x210A) || (c == 0x2113) || (c == 0x2116) || (c == 0x2121)
938         || (c == 0x212B) || (c == 0x213B) || (c == 0x2150) || (c == 0x2151) || (c == 0x2152))
939         return true;
940
941     if (c >= 0x2156 && c <= 0x215A)
942         return true;
943
944     if (c >= 0x2160 && c <= 0x216B)
945         return true;
946
947     if (c >= 0x2170 && c <= 0x217B)
948         return true;
949
950     if ((c == 0x217F) || (c == 0x2189) || (c == 0x2307) || (c == 0x2312) || (c == 0x23BE) || (c == 0x23BF))
951         return true;
952
953     if (c >= 0x23C0 && c <= 0x23CC)
954         return true;
955
956     if ((c == 0x23CE) || (c == 0x2423))
957         return true;
958
959     if (c >= 0x2460 && c <= 0x2492)
960         return true;
961
962     if (c >= 0x249C && c <= 0x24FF)
963         return true;
964
965     if ((c == 0x25A0) || (c == 0x25A1) || (c == 0x25A2) || (c == 0x25AA) || (c == 0x25AB))
966         return true;
967
968     if ((c == 0x25B1) || (c == 0x25B2) || (c == 0x25B3) || (c == 0x25B6) || (c == 0x25B7) || (c == 0x25BC) || (c == 0x25BD))
969         return true;
970     
971     if ((c == 0x25C0) || (c == 0x25C1) || (c == 0x25C6) || (c == 0x25C7) || (c == 0x25C9) || (c == 0x25CB) || (c == 0x25CC))
972         return true;
973
974     if (c >= 0x25CE && c <= 0x25D3)
975         return true;
976
977     if (c >= 0x25E2 && c <= 0x25E6)
978         return true;
979
980     if (c == 0x25EF)
981         return true;
982
983     if (c >= 0x2600 && c <= 0x2603)
984         return true;
985
986     if ((c == 0x2605) || (c == 0x2606) || (c == 0x260E) || (c == 0x2616) || (c == 0x2617) || (c == 0x2640) || (c == 0x2642))
987         return true;
988
989     if (c >= 0x2660 && c <= 0x266F)
990         return true;
991
992     if (c >= 0x2672 && c <= 0x267D)
993         return true;
994
995     if ((c == 0x26A0) || (c == 0x26BD) || (c == 0x26BE) || (c == 0x2713) || (c == 0x271A) || (c == 0x273F) || (c == 0x2740) || (c == 0x2756))
996         return true;
997
998     if (c >= 0x2776 && c <= 0x277F)
999         return true;
1000
1001     if (c == 0x2B1A)
1002         return true;
1003
1004     // Ideographic Description Characters.
1005     if (c >= 0x2FF0 && c <= 0x2FFF)
1006         return true;
1007
1008     // CJK Symbols and Punctuation, excluding 0x3030.
1009     if (c >= 0x3000 && c < 0x3030)
1010         return true;
1011
1012     if (c > 0x3030 && c <= 0x303F)
1013         return true;
1014
1015     // Hiragana
1016     if (c >= 0x3040 && c <= 0x309F)
1017         return true;
1018
1019     // Katakana 
1020     if (c >= 0x30A0 && c <= 0x30FF)
1021         return true;
1022
1023     // Bopomofo
1024     if (c >= 0x3100 && c <= 0x312F)
1025         return true;
1026
1027     if (c >= 0x3190 && c <= 0x319F)
1028         return true;
1029
1030     // Bopomofo Extended
1031     if (c >= 0x31A0 && c <= 0x31BF)
1032         return true;
1033
1034     // Enclosed CJK Letters and Months.
1035     if (c >= 0x3200 && c <= 0x32FF)
1036         return true;
1037     
1038     // CJK Compatibility.
1039     if (c >= 0x3300 && c <= 0x33FF)
1040         return true;
1041
1042     if (c >= 0xF860 && c <= 0xF862)
1043         return true;
1044
1045     // CJK Compatibility Forms.
1046     if (c >= 0xFE30 && c <= 0xFE4F)
1047         return true;
1048
1049     if ((c == 0xFE10) || (c == 0xFE11) || (c == 0xFE12) || (c == 0xFE19))
1050         return true;
1051
1052     if ((c == 0xFF0D) || (c == 0xFF1B) || (c == 0xFF1C) || (c == 0xFF1E))
1053         return false;
1054
1055     // Halfwidth and Fullwidth Forms
1056     // Usually only used in CJK
1057     if (c >= 0xFF00 && c <= 0xFFEF)
1058         return true;
1059
1060     // Emoji.
1061     if (c == 0x1F100)
1062         return true;
1063
1064     if (c >= 0x1F110 && c <= 0x1F129)
1065         return true;
1066
1067     if (c >= 0x1F130 && c <= 0x1F149)
1068         return true;
1069
1070     if (c >= 0x1F150 && c <= 0x1F169)
1071         return true;
1072
1073     if (c >= 0x1F170 && c <= 0x1F189)
1074         return true;
1075
1076     if (c >= 0x1F200 && c <= 0x1F6C5)
1077         return true;
1078
1079     return isCJKIdeograph(c);
1080 }
1081
1082 std::pair<unsigned, bool> FontCascade::expansionOpportunityCountInternal(const LChar* characters, unsigned length, TextDirection direction, ExpansionBehavior expansionBehavior)
1083 {
1084     unsigned count = 0;
1085     bool isAfterExpansion = (expansionBehavior & LeadingExpansionMask) == ForbidLeadingExpansion;
1086     if ((expansionBehavior & LeadingExpansionMask) == ForceLeadingExpansion) {
1087         ++count;
1088         isAfterExpansion = true;
1089     }
1090     if (direction == TextDirection::LTR) {
1091         for (unsigned i = 0; i < length; ++i) {
1092             if (treatAsSpace(characters[i])) {
1093                 count++;
1094                 isAfterExpansion = true;
1095             } else
1096                 isAfterExpansion = false;
1097         }
1098     } else {
1099         for (unsigned i = length; i > 0; --i) {
1100             if (treatAsSpace(characters[i - 1])) {
1101                 count++;
1102                 isAfterExpansion = true;
1103             } else
1104                 isAfterExpansion = false;
1105         }
1106     }
1107     if (!isAfterExpansion && (expansionBehavior & TrailingExpansionMask) == ForceTrailingExpansion) {
1108         ++count;
1109         isAfterExpansion = true;
1110     } else if (isAfterExpansion && (expansionBehavior & TrailingExpansionMask) == ForbidTrailingExpansion) {
1111         ASSERT(count);
1112         --count;
1113         isAfterExpansion = false;
1114     }
1115     return std::make_pair(count, isAfterExpansion);
1116 }
1117
1118 std::pair<unsigned, bool> FontCascade::expansionOpportunityCountInternal(const UChar* characters, unsigned length, TextDirection direction, ExpansionBehavior expansionBehavior)
1119 {
1120     static bool expandAroundIdeographs = canExpandAroundIdeographsInComplexText();
1121     unsigned count = 0;
1122     bool isAfterExpansion = (expansionBehavior & LeadingExpansionMask) == ForbidLeadingExpansion;
1123     if ((expansionBehavior & LeadingExpansionMask) == ForceLeadingExpansion) {
1124         ++count;
1125         isAfterExpansion = true;
1126     }
1127     if (direction == TextDirection::LTR) {
1128         for (unsigned i = 0; i < length; ++i) {
1129             UChar32 character = characters[i];
1130             if (treatAsSpace(character)) {
1131                 count++;
1132                 isAfterExpansion = true;
1133                 continue;
1134             }
1135             if (U16_IS_LEAD(character) && i + 1 < length && U16_IS_TRAIL(characters[i + 1])) {
1136                 character = U16_GET_SUPPLEMENTARY(character, characters[i + 1]);
1137                 i++;
1138             }
1139             if (expandAroundIdeographs && isCJKIdeographOrSymbol(character)) {
1140                 if (!isAfterExpansion)
1141                     count++;
1142                 count++;
1143                 isAfterExpansion = true;
1144                 continue;
1145             }
1146             isAfterExpansion = false;
1147         }
1148     } else {
1149         for (unsigned i = length; i > 0; --i) {
1150             UChar32 character = characters[i - 1];
1151             if (treatAsSpace(character)) {
1152                 count++;
1153                 isAfterExpansion = true;
1154                 continue;
1155             }
1156             if (U16_IS_TRAIL(character) && i > 1 && U16_IS_LEAD(characters[i - 2])) {
1157                 character = U16_GET_SUPPLEMENTARY(characters[i - 2], character);
1158                 i--;
1159             }
1160             if (expandAroundIdeographs && isCJKIdeographOrSymbol(character)) {
1161                 if (!isAfterExpansion)
1162                     count++;
1163                 count++;
1164                 isAfterExpansion = true;
1165                 continue;
1166             }
1167             isAfterExpansion = false;
1168         }
1169     }
1170     if (!isAfterExpansion && (expansionBehavior & TrailingExpansionMask) == ForceTrailingExpansion) {
1171         ++count;
1172         isAfterExpansion = true;
1173     } else if (isAfterExpansion && (expansionBehavior & TrailingExpansionMask) == ForbidTrailingExpansion) {
1174         ASSERT(count);
1175         --count;
1176         isAfterExpansion = false;
1177     }
1178     return std::make_pair(count, isAfterExpansion);
1179 }
1180
1181 std::pair<unsigned, bool> FontCascade::expansionOpportunityCount(const StringView& stringView, TextDirection direction, ExpansionBehavior expansionBehavior)
1182 {
1183     // For each character, iterating from left to right:
1184     //   If it is recognized as a space, insert an opportunity after it
1185     //   If it is an ideograph, insert one opportunity before it and one opportunity after it
1186     // Do this such a way so that there are not two opportunities next to each other.
1187     if (stringView.is8Bit())
1188         return expansionOpportunityCountInternal(stringView.characters8(), stringView.length(), direction, expansionBehavior);
1189     return expansionOpportunityCountInternal(stringView.characters16(), stringView.length(), direction, expansionBehavior);
1190 }
1191
1192 bool FontCascade::leadingExpansionOpportunity(const StringView& stringView, TextDirection direction)
1193 {
1194     if (!stringView.length())
1195         return false;
1196
1197     UChar32 initialCharacter;
1198     if (direction == TextDirection::LTR) {
1199         initialCharacter = stringView[0];
1200         if (U16_IS_LEAD(initialCharacter) && stringView.length() > 1 && U16_IS_TRAIL(stringView[1]))
1201             initialCharacter = U16_GET_SUPPLEMENTARY(initialCharacter, stringView[1]);
1202     } else {
1203         initialCharacter = stringView[stringView.length() - 1];
1204         if (U16_IS_TRAIL(initialCharacter) && stringView.length() > 1 && U16_IS_LEAD(stringView[stringView.length() - 2]))
1205             initialCharacter = U16_GET_SUPPLEMENTARY(stringView[stringView.length() - 2], initialCharacter);
1206     }
1207
1208     return canExpandAroundIdeographsInComplexText() && isCJKIdeographOrSymbol(initialCharacter);
1209 }
1210
1211 bool FontCascade::trailingExpansionOpportunity(const StringView& stringView, TextDirection direction)
1212 {
1213     if (!stringView.length())
1214         return false;
1215
1216     UChar32 finalCharacter;
1217     if (direction == TextDirection::LTR) {
1218         finalCharacter = stringView[stringView.length() - 1];
1219         if (U16_IS_TRAIL(finalCharacter) && stringView.length() > 1 && U16_IS_LEAD(stringView[stringView.length() - 2]))
1220             finalCharacter = U16_GET_SUPPLEMENTARY(stringView[stringView.length() - 2], finalCharacter);
1221     } else {
1222         finalCharacter = stringView[0];
1223         if (U16_IS_LEAD(finalCharacter) && stringView.length() > 1 && U16_IS_TRAIL(stringView[1]))
1224             finalCharacter = U16_GET_SUPPLEMENTARY(finalCharacter, stringView[1]);
1225     }
1226
1227     return treatAsSpace(finalCharacter) || (canExpandAroundIdeographsInComplexText() && isCJKIdeographOrSymbol(finalCharacter));
1228 }
1229
1230 bool FontCascade::canReceiveTextEmphasis(UChar32 c)
1231 {
1232     if (U_GET_GC_MASK(c) & (U_GC_Z_MASK | U_GC_CN_MASK | U_GC_CC_MASK | U_GC_CF_MASK))
1233         return false;
1234
1235     // Additional word-separator characters listed in CSS Text Level 3 Editor's Draft 3 November 2010.
1236     if (c == ethiopicWordspace || c == aegeanWordSeparatorLine || c == aegeanWordSeparatorDot
1237         || c == ugariticWordDivider || c == tibetanMarkIntersyllabicTsheg || c == tibetanMarkDelimiterTshegBstar)
1238         return false;
1239
1240     return true;
1241 }
1242
1243 bool FontCascade::isLoadingCustomFonts() const
1244 {
1245     return m_fonts && m_fonts->isLoadingCustomFonts();
1246 }
1247
1248 enum class GlyphUnderlineType : uint8_t {
1249     SkipDescenders,
1250     SkipGlyph,
1251     DrawOverGlyph
1252 };
1253     
1254 static GlyphUnderlineType computeUnderlineType(const TextRun& textRun, const GlyphBuffer& glyphBuffer, unsigned index)
1255 {
1256     // In general, we want to skip descenders. However, skipping descenders on CJK characters leads to undesirable renderings,
1257     // so we want to draw through CJK characters (on a character-by-character basis).
1258     // FIXME: The CSS spec says this should instead be done by the user-agent stylesheet using the lang= attribute.
1259     UChar32 baseCharacter;
1260     unsigned offsetInString = glyphBuffer.offsetInString(index);
1261
1262     if (offsetInString == GlyphBuffer::noOffset || offsetInString >= textRun.length()) {
1263         // We have no idea which character spawned this glyph. Bail.
1264         ASSERT_WITH_SECURITY_IMPLICATION(offsetInString < textRun.length());
1265         return GlyphUnderlineType::DrawOverGlyph;
1266     }
1267     
1268     if (textRun.is8Bit())
1269         baseCharacter = textRun.characters8()[offsetInString];
1270     else
1271         U16_NEXT(textRun.characters16(), offsetInString, textRun.length(), baseCharacter);
1272     
1273     // u_getIntPropertyValue with UCHAR_IDEOGRAPHIC doesn't return true for Japanese or Korean codepoints.
1274     // Instead, we can use the "Unicode allocation block" for the character.
1275     UBlockCode blockCode = ublock_getCode(baseCharacter);
1276     switch (blockCode) {
1277     case UBLOCK_CJK_RADICALS_SUPPLEMENT:
1278     case UBLOCK_CJK_SYMBOLS_AND_PUNCTUATION:
1279     case UBLOCK_ENCLOSED_CJK_LETTERS_AND_MONTHS:
1280     case UBLOCK_CJK_COMPATIBILITY:
1281     case UBLOCK_CJK_UNIFIED_IDEOGRAPHS_EXTENSION_A:
1282     case UBLOCK_CJK_UNIFIED_IDEOGRAPHS:
1283     case UBLOCK_CJK_COMPATIBILITY_IDEOGRAPHS:
1284     case UBLOCK_CJK_COMPATIBILITY_FORMS:
1285     case UBLOCK_CJK_UNIFIED_IDEOGRAPHS_EXTENSION_B:
1286     case UBLOCK_CJK_COMPATIBILITY_IDEOGRAPHS_SUPPLEMENT:
1287     case UBLOCK_CJK_STROKES:
1288     case UBLOCK_CJK_UNIFIED_IDEOGRAPHS_EXTENSION_C:
1289     case UBLOCK_CJK_UNIFIED_IDEOGRAPHS_EXTENSION_D:
1290     case UBLOCK_IDEOGRAPHIC_DESCRIPTION_CHARACTERS:
1291     case UBLOCK_LINEAR_B_IDEOGRAMS:
1292     case UBLOCK_ENCLOSED_IDEOGRAPHIC_SUPPLEMENT:
1293     case UBLOCK_HIRAGANA:
1294     case UBLOCK_KATAKANA:
1295     case UBLOCK_BOPOMOFO:
1296     case UBLOCK_BOPOMOFO_EXTENDED:
1297     case UBLOCK_HANGUL_JAMO:
1298     case UBLOCK_HANGUL_COMPATIBILITY_JAMO:
1299     case UBLOCK_HANGUL_SYLLABLES:
1300     case UBLOCK_HANGUL_JAMO_EXTENDED_A:
1301     case UBLOCK_HANGUL_JAMO_EXTENDED_B:
1302         return GlyphUnderlineType::DrawOverGlyph;
1303     default:
1304         return GlyphUnderlineType::SkipDescenders;
1305     }
1306 }
1307
1308 // FIXME: This function may not work if the emphasis mark uses a complex script, but none of the
1309 // standard emphasis marks do so.
1310 Optional<GlyphData> FontCascade::getEmphasisMarkGlyphData(const AtomicString& mark) const
1311 {
1312     if (mark.isEmpty())
1313         return WTF::nullopt;
1314
1315     UChar32 character;
1316     if (!mark.is8Bit()) {
1317         SurrogatePairAwareTextIterator iterator(mark.characters16(), 0, mark.length(), mark.length());
1318         unsigned clusterLength;
1319         if (!iterator.consume(character, clusterLength))
1320             return WTF::nullopt;
1321     } else
1322         character = mark[0];
1323
1324     Optional<GlyphData> glyphData(glyphDataForCharacter(character, false, EmphasisMarkVariant));
1325     return glyphData.value().isValid() ? glyphData : WTF::nullopt;
1326 }
1327
1328 int FontCascade::emphasisMarkAscent(const AtomicString& mark) const
1329 {
1330     Optional<GlyphData> markGlyphData = getEmphasisMarkGlyphData(mark);
1331     if (!markGlyphData)
1332         return 0;
1333
1334     const Font* markFontData = markGlyphData.value().font;
1335     ASSERT(markFontData);
1336     if (!markFontData)
1337         return 0;
1338
1339     return markFontData->fontMetrics().ascent();
1340 }
1341
1342 int FontCascade::emphasisMarkDescent(const AtomicString& mark) const
1343 {
1344     Optional<GlyphData> markGlyphData = getEmphasisMarkGlyphData(mark);
1345     if (!markGlyphData)
1346         return 0;
1347
1348     const Font* markFontData = markGlyphData.value().font;
1349     ASSERT(markFontData);
1350     if (!markFontData)
1351         return 0;
1352
1353     return markFontData->fontMetrics().descent();
1354 }
1355
1356 int FontCascade::emphasisMarkHeight(const AtomicString& mark) const
1357 {
1358     Optional<GlyphData> markGlyphData = getEmphasisMarkGlyphData(mark);
1359     if (!markGlyphData)
1360         return 0;
1361
1362     const Font* markFontData = markGlyphData.value().font;
1363     ASSERT(markFontData);
1364     if (!markFontData)
1365         return 0;
1366
1367     return markFontData->fontMetrics().height();
1368 }
1369
1370 float FontCascade::getGlyphsAndAdvancesForSimpleText(const TextRun& run, unsigned from, unsigned to, GlyphBuffer& glyphBuffer, ForTextEmphasisOrNot forTextEmphasis) const
1371 {
1372     float initialAdvance;
1373
1374     WidthIterator it(this, run, 0, false, forTextEmphasis);
1375     // FIXME: Using separate glyph buffers for the prefix and the suffix is incorrect when kerning or
1376     // ligatures are enabled.
1377     GlyphBuffer localGlyphBuffer;
1378     it.advance(from, &localGlyphBuffer);
1379     float beforeWidth = it.m_runWidthSoFar;
1380     it.advance(to, &glyphBuffer);
1381
1382     if (glyphBuffer.isEmpty())
1383         return 0;
1384
1385     float afterWidth = it.m_runWidthSoFar;
1386
1387     if (run.rtl()) {
1388         float finalRoundingWidth = it.m_finalRoundingWidth;
1389         it.advance(run.length(), &localGlyphBuffer);
1390         initialAdvance = finalRoundingWidth + it.m_runWidthSoFar - afterWidth;
1391     } else
1392         initialAdvance = beforeWidth;
1393
1394     if (run.rtl())
1395         glyphBuffer.reverse(0, glyphBuffer.size());
1396
1397     return initialAdvance;
1398 }
1399
1400 #if !PLATFORM(WIN)
1401 float FontCascade::getGlyphsAndAdvancesForComplexText(const TextRun& run, unsigned from, unsigned to, GlyphBuffer& glyphBuffer, ForTextEmphasisOrNot forTextEmphasis) const
1402 {
1403     float initialAdvance;
1404
1405     ComplexTextController controller(*this, run, false, 0, forTextEmphasis);
1406     GlyphBuffer dummyGlyphBuffer;
1407     controller.advance(from, &dummyGlyphBuffer);
1408     controller.advance(to, &glyphBuffer);
1409
1410     if (glyphBuffer.isEmpty())
1411         return 0;
1412
1413     if (run.rtl()) {
1414         // Exploit the fact that the sum of the paint advances is equal to
1415         // the sum of the layout advances.
1416         initialAdvance = controller.totalWidth();
1417         for (unsigned i = 0; i < dummyGlyphBuffer.size(); ++i)
1418             initialAdvance -= dummyGlyphBuffer.advanceAt(i).width();
1419         for (unsigned i = 0; i < glyphBuffer.size(); ++i)
1420             initialAdvance -= glyphBuffer.advanceAt(i).width();
1421         glyphBuffer.reverse(0, glyphBuffer.size());
1422     } else {
1423         initialAdvance = dummyGlyphBuffer.initialAdvance().width();
1424         for (unsigned i = 0; i < dummyGlyphBuffer.size(); ++i)
1425             initialAdvance += dummyGlyphBuffer.advanceAt(i).width();
1426     }
1427
1428     return initialAdvance;
1429 }
1430 #endif
1431
1432 void FontCascade::drawEmphasisMarksForSimpleText(GraphicsContext& context, const TextRun& run, const AtomicString& mark, const FloatPoint& point, unsigned from, unsigned to) const
1433 {
1434     GlyphBuffer glyphBuffer;
1435     float initialAdvance = getGlyphsAndAdvancesForSimpleText(run, from, to, glyphBuffer, ForTextEmphasis);
1436
1437     if (glyphBuffer.isEmpty())
1438         return;
1439
1440     drawEmphasisMarks(context, glyphBuffer, mark, FloatPoint(point.x() + initialAdvance, point.y()));
1441 }
1442
1443 inline bool shouldDrawIfLoading(const Font& font, FontCascade::CustomFontNotReadyAction customFontNotReadyAction)
1444 {
1445     // Don't draw anything while we are using custom fonts that are in the process of loading,
1446     // except if the 'customFontNotReadyAction' argument is set to UseFallbackIfFontNotReady
1447     // (in which case "font" will be a fallback font).
1448     return !font.isInterstitial() || font.visibility() == Font::Visibility::Visible || customFontNotReadyAction == FontCascade::CustomFontNotReadyAction::UseFallbackIfFontNotReady;
1449 }
1450
1451 void FontCascade::drawGlyphBuffer(GraphicsContext& context, const GlyphBuffer& glyphBuffer, FloatPoint& point, CustomFontNotReadyAction customFontNotReadyAction) const
1452 {
1453     // Draw each contiguous run of glyphs that use the same font data.
1454     const Font* fontData = glyphBuffer.fontAt(0);
1455 #if PLATFORM(WIN)
1456     FloatPoint startPoint(point.x() + glyphBuffer.initialAdvance().width(), point.y() + glyphBuffer.initialAdvance().height());
1457 #else
1458     // FIXME: Why do we subtract the initial advance's height but not its width???
1459     // We should use the line above from Windows instead.
1460     FloatPoint startPoint(point.x(), point.y() - glyphBuffer.initialAdvance().height());
1461 #endif
1462     float nextX = startPoint.x() + glyphBuffer.advanceAt(0).width();
1463     float nextY = startPoint.y() + glyphBuffer.advanceAt(0).height();
1464     unsigned lastFrom = 0;
1465     unsigned nextGlyph = 1;
1466     while (nextGlyph < glyphBuffer.size()) {
1467         const Font* nextFontData = glyphBuffer.fontAt(nextGlyph);
1468
1469         if (nextFontData != fontData) {
1470             if (shouldDrawIfLoading(*fontData, customFontNotReadyAction))
1471                 context.drawGlyphs(*fontData, glyphBuffer, lastFrom, nextGlyph - lastFrom, startPoint, m_fontDescription.fontSmoothing());
1472
1473             lastFrom = nextGlyph;
1474             fontData = nextFontData;
1475             startPoint.setX(nextX);
1476             startPoint.setY(nextY);
1477         }
1478         nextX += glyphBuffer.advanceAt(nextGlyph).width();
1479         nextY += glyphBuffer.advanceAt(nextGlyph).height();
1480         nextGlyph++;
1481     }
1482
1483     if (shouldDrawIfLoading(*fontData, customFontNotReadyAction))
1484         context.drawGlyphs(*fontData, glyphBuffer, lastFrom, nextGlyph - lastFrom, startPoint, m_fontDescription.fontSmoothing());
1485     point.setX(nextX);
1486 }
1487
1488 inline static float offsetToMiddleOfGlyph(const Font* fontData, Glyph glyph)
1489 {
1490     if (fontData->platformData().orientation() == FontOrientation::Horizontal) {
1491         FloatRect bounds = fontData->boundsForGlyph(glyph);
1492         return bounds.x() + bounds.width() / 2;
1493     }
1494     // FIXME: Use glyph bounds once they make sense for vertical fonts.
1495     return fontData->widthForGlyph(glyph) / 2;
1496 }
1497
1498 inline static float offsetToMiddleOfGlyphAtIndex(const GlyphBuffer& glyphBuffer, unsigned i)
1499 {
1500     return offsetToMiddleOfGlyph(glyphBuffer.fontAt(i), glyphBuffer.glyphAt(i));
1501 }
1502
1503 void FontCascade::drawEmphasisMarks(GraphicsContext& context, const GlyphBuffer& glyphBuffer, const AtomicString& mark, const FloatPoint& point) const
1504 {
1505     Optional<GlyphData> markGlyphData = getEmphasisMarkGlyphData(mark);
1506     if (!markGlyphData)
1507         return;
1508
1509     const Font* markFontData = markGlyphData.value().font;
1510     ASSERT(markFontData);
1511     if (!markFontData)
1512         return;
1513
1514     Glyph markGlyph = markGlyphData.value().glyph;
1515     Glyph spaceGlyph = markFontData->spaceGlyph();
1516
1517     float middleOfLastGlyph = offsetToMiddleOfGlyphAtIndex(glyphBuffer, 0);
1518     FloatPoint startPoint(point.x() + middleOfLastGlyph - offsetToMiddleOfGlyph(markFontData, markGlyph), point.y());
1519
1520     GlyphBuffer markBuffer;
1521     for (unsigned i = 0; i + 1 < glyphBuffer.size(); ++i) {
1522         float middleOfNextGlyph = offsetToMiddleOfGlyphAtIndex(glyphBuffer, i + 1);
1523         float advance = glyphBuffer.advanceAt(i).width() - middleOfLastGlyph + middleOfNextGlyph;
1524         markBuffer.add(glyphBuffer.glyphAt(i) ? markGlyph : spaceGlyph, markFontData, advance);
1525         middleOfLastGlyph = middleOfNextGlyph;
1526     }
1527     markBuffer.add(glyphBuffer.glyphAt(glyphBuffer.size() - 1) ? markGlyph : spaceGlyph, markFontData, 0);
1528
1529     drawGlyphBuffer(context, markBuffer, startPoint, CustomFontNotReadyAction::DoNotPaintIfFontNotReady);
1530 }
1531
1532 float FontCascade::floatWidthForSimpleText(const TextRun& run, HashSet<const Font*>* fallbackFonts, GlyphOverflow* glyphOverflow) const
1533 {
1534     WidthIterator it(this, run, fallbackFonts, glyphOverflow);
1535     GlyphBuffer glyphBuffer;
1536     it.advance(run.length(), (enableKerning() || requiresShaping()) ? &glyphBuffer : nullptr);
1537
1538     if (glyphOverflow) {
1539         glyphOverflow->top = std::max<int>(glyphOverflow->top, ceilf(-it.minGlyphBoundingBoxY()) - (glyphOverflow->computeBounds ? 0 : fontMetrics().ascent()));
1540         glyphOverflow->bottom = std::max<int>(glyphOverflow->bottom, ceilf(it.maxGlyphBoundingBoxY()) - (glyphOverflow->computeBounds ? 0 : fontMetrics().descent()));
1541         glyphOverflow->left = ceilf(it.firstGlyphOverflow());
1542         glyphOverflow->right = ceilf(it.lastGlyphOverflow());
1543     }
1544
1545     return it.m_runWidthSoFar;
1546 }
1547
1548 #if !PLATFORM(WIN)
1549 float FontCascade::floatWidthForComplexText(const TextRun& run, HashSet<const Font*>* fallbackFonts, GlyphOverflow* glyphOverflow) const
1550 {
1551     ComplexTextController controller(*this, run, true, fallbackFonts);
1552     if (glyphOverflow) {
1553         glyphOverflow->top = std::max<int>(glyphOverflow->top, ceilf(-controller.minGlyphBoundingBoxY()) - (glyphOverflow->computeBounds ? 0 : fontMetrics().ascent()));
1554         glyphOverflow->bottom = std::max<int>(glyphOverflow->bottom, ceilf(controller.maxGlyphBoundingBoxY()) - (glyphOverflow->computeBounds ? 0 : fontMetrics().descent()));
1555         glyphOverflow->left = std::max<int>(0, ceilf(-controller.minGlyphBoundingBoxX()));
1556         glyphOverflow->right = std::max<int>(0, ceilf(controller.maxGlyphBoundingBoxX() - controller.totalWidth()));
1557     }
1558     return controller.totalWidth();
1559 }
1560 #endif
1561
1562 void FontCascade::adjustSelectionRectForSimpleText(const TextRun& run, LayoutRect& selectionRect, unsigned from, unsigned to) const
1563 {
1564     GlyphBuffer glyphBuffer;
1565     WidthIterator it(this, run);
1566     it.advance(from, &glyphBuffer);
1567     float beforeWidth = it.m_runWidthSoFar;
1568     it.advance(to, &glyphBuffer);
1569     float afterWidth = it.m_runWidthSoFar;
1570     float totalWidth = -1;
1571
1572     if (run.rtl()) {
1573         it.advance(run.length(), &glyphBuffer);
1574         totalWidth = it.m_runWidthSoFar;
1575         selectionRect.move(totalWidth - afterWidth, 0);
1576     } else
1577         selectionRect.move(beforeWidth, 0);
1578     selectionRect.setWidth(LayoutUnit::fromFloatCeil(afterWidth - beforeWidth));
1579 }
1580
1581 #if !PLATFORM(WIN)
1582 void FontCascade::adjustSelectionRectForComplexText(const TextRun& run, LayoutRect& selectionRect, unsigned from, unsigned to) const
1583 {
1584     ComplexTextController controller(*this, run);
1585     controller.advance(from);
1586     float beforeWidth = controller.runWidthSoFar();
1587     controller.advance(to);
1588     float afterWidth = controller.runWidthSoFar();
1589
1590     if (run.rtl())
1591         selectionRect.move(controller.totalWidth() - afterWidth, 0);
1592     else
1593         selectionRect.move(beforeWidth, 0);
1594     selectionRect.setWidth(LayoutUnit::fromFloatCeil(afterWidth - beforeWidth));
1595 }
1596 #endif
1597
1598 int FontCascade::offsetForPositionForSimpleText(const TextRun& run, float x, bool includePartialGlyphs) const
1599 {
1600     float delta = x;
1601
1602     WidthIterator it(this, run);
1603     GlyphBuffer localGlyphBuffer;
1604     unsigned offset;
1605     if (run.rtl()) {
1606         delta -= floatWidthForSimpleText(run);
1607         while (1) {
1608             offset = it.m_currentCharacter;
1609             float w;
1610             if (!it.advanceOneCharacter(w, localGlyphBuffer))
1611                 break;
1612             delta += w;
1613             if (includePartialGlyphs) {
1614                 if (delta - w / 2 >= 0)
1615                     break;
1616             } else {
1617                 if (delta >= 0)
1618                     break;
1619             }
1620         }
1621     } else {
1622         while (1) {
1623             offset = it.m_currentCharacter;
1624             float w;
1625             if (!it.advanceOneCharacter(w, localGlyphBuffer))
1626                 break;
1627             delta -= w;
1628             if (includePartialGlyphs) {
1629                 if (delta + w / 2 <= 0)
1630                     break;
1631             } else {
1632                 if (delta <= 0)
1633                     break;
1634             }
1635         }
1636     }
1637
1638     return offset;
1639 }
1640
1641 #if !PLATFORM(WIN)
1642 int FontCascade::offsetForPositionForComplexText(const TextRun& run, float x, bool includePartialGlyphs) const
1643 {
1644     ComplexTextController controller(*this, run);
1645     return controller.offsetForPosition(x, includePartialGlyphs);
1646 }
1647 #endif
1648
1649 #if !PLATFORM(COCOA) && !USE(HARFBUZZ)
1650 // FIXME: Unify this with the macOS and iOS implementation.
1651 const Font* FontCascade::fontForCombiningCharacterSequence(const UChar* characters, size_t length) const
1652 {
1653     UChar32 baseCharacter;
1654     size_t baseCharacterLength = 0;
1655     U16_NEXT(characters, baseCharacterLength, length, baseCharacter);
1656     GlyphData baseCharacterGlyphData = glyphDataForCharacter(baseCharacter, false, NormalVariant);
1657
1658     if (!baseCharacterGlyphData.glyph)
1659         return nullptr;
1660     return baseCharacterGlyphData.font;
1661 }
1662 #endif
1663
1664 void FontCascade::drawEmphasisMarksForComplexText(GraphicsContext& context, const TextRun& run, const AtomicString& mark, const FloatPoint& point, unsigned from, unsigned to) const
1665 {
1666     GlyphBuffer glyphBuffer;
1667     float initialAdvance = getGlyphsAndAdvancesForComplexText(run, from, to, glyphBuffer, ForTextEmphasis);
1668
1669     if (glyphBuffer.isEmpty())
1670         return;
1671
1672     drawEmphasisMarks(context, glyphBuffer, mark, FloatPoint(point.x() + initialAdvance, point.y()));
1673 }
1674
1675 struct GlyphIterationState {
1676     FloatPoint startingPoint;
1677     FloatPoint currentPoint;
1678     float y1;
1679     float y2;
1680     float minX;
1681     float maxX;
1682 };
1683
1684 static Optional<float> findIntersectionPoint(float y, FloatPoint p1, FloatPoint p2)
1685 {
1686     if ((p1.y() < y && p2.y() > y) || (p1.y() > y && p2.y() < y))
1687         return p1.x() + (y - p1.y()) * (p2.x() - p1.x()) / (p2.y() - p1.y());
1688     return WTF::nullopt;
1689 }
1690
1691 static void updateX(GlyphIterationState& state, float x)
1692 {
1693     state.minX = std::min(state.minX, x);
1694     state.maxX = std::max(state.maxX, x);
1695 }
1696
1697 // This function is called by CGPathApply and is therefore invoked for each
1698 // contour in a glyph. This function models each contours as a straight line
1699 // and calculates the intersections between each pseudo-contour and
1700 // two horizontal lines (the upper and lower bounds of an underline) found in
1701 // GlyphIterationState::y1 and GlyphIterationState::y2. It keeps track of the
1702 // leftmost and rightmost intersection in GlyphIterationState::minX and
1703 // GlyphIterationState::maxX.
1704 static void findPathIntersections(GlyphIterationState& state, const PathElement& element)
1705 {
1706     bool doIntersection = false;
1707     FloatPoint point = FloatPoint();
1708     switch (element.type) {
1709     case PathElementMoveToPoint:
1710         state.startingPoint = element.points[0];
1711         state.currentPoint = element.points[0];
1712         break;
1713     case PathElementAddLineToPoint:
1714         doIntersection = true;
1715         point = element.points[0];
1716         break;
1717     case PathElementAddQuadCurveToPoint:
1718         doIntersection = true;
1719         point = element.points[1];
1720         break;
1721     case PathElementAddCurveToPoint:
1722         doIntersection = true;
1723         point = element.points[2];
1724         break;
1725     case PathElementCloseSubpath:
1726         doIntersection = true;
1727         point = state.startingPoint;
1728         break;
1729     }
1730     if (!doIntersection)
1731         return;
1732     if (auto intersectionPoint = findIntersectionPoint(state.y1, state.currentPoint, point))
1733         updateX(state, *intersectionPoint);
1734     if (auto intersectionPoint = findIntersectionPoint(state.y2, state.currentPoint, point))
1735         updateX(state, *intersectionPoint);
1736     if ((state.currentPoint.y() >= state.y1 && state.currentPoint.y() <= state.y2)
1737         || (state.currentPoint.y() <= state.y1 && state.currentPoint.y() >= state.y2))
1738         updateX(state, state.currentPoint.x());
1739     state.currentPoint = point;
1740 }
1741
1742 class GlyphToPathTranslator {
1743 public:
1744     GlyphToPathTranslator(const TextRun& textRun, const GlyphBuffer& glyphBuffer, const FloatPoint& textOrigin)
1745         : m_index(0)
1746         , m_textRun(textRun)
1747         , m_glyphBuffer(glyphBuffer)
1748         , m_fontData(glyphBuffer.fontAt(m_index))
1749         , m_translation(AffineTransform::translation(textOrigin.x(), textOrigin.y()))
1750     {
1751 #if USE(CG)
1752         m_translation.flipY();
1753 #endif
1754     }
1755
1756     bool containsMorePaths() { return m_index != m_glyphBuffer.size(); }
1757     Path path();
1758     std::pair<float, float> extents();
1759     GlyphUnderlineType underlineType();
1760     void advance();
1761
1762 private:
1763     unsigned m_index;
1764     const TextRun& m_textRun;
1765     const GlyphBuffer& m_glyphBuffer;
1766     const Font* m_fontData;
1767     AffineTransform m_translation;
1768 };
1769
1770 Path GlyphToPathTranslator::path()
1771 {
1772     Path path = m_fontData->pathForGlyph(m_glyphBuffer.glyphAt(m_index));
1773     path.transform(m_translation);
1774     return path;
1775 }
1776
1777 std::pair<float, float> GlyphToPathTranslator::extents()
1778 {
1779     auto beginning = m_translation.mapPoint(FloatPoint(0, 0));
1780     auto advance = m_glyphBuffer.advanceAt(m_index);
1781     auto end = m_translation.mapSize(FloatSize(advance.width(), advance.height()));
1782     return std::make_pair(beginning.x(), beginning.x() + end.width());
1783 }
1784
1785 auto GlyphToPathTranslator::underlineType() -> GlyphUnderlineType
1786 {
1787     return computeUnderlineType(m_textRun, m_glyphBuffer, m_index);
1788 }
1789
1790 void GlyphToPathTranslator::advance()
1791 {
1792     GlyphBufferAdvance advance = m_glyphBuffer.advanceAt(m_index);
1793     m_translation.translate(FloatSize(advance.width(), advance.height()));
1794     ++m_index;
1795     if (m_index < m_glyphBuffer.size())
1796         m_fontData = m_glyphBuffer.fontAt(m_index);
1797 }
1798
1799 DashArray FontCascade::dashesForIntersectionsWithRect(const TextRun& run, const FloatPoint& textOrigin, const FloatRect& lineExtents) const
1800 {
1801     if (isLoadingCustomFonts())
1802         return DashArray();
1803
1804     GlyphBuffer glyphBuffer;
1805     glyphBuffer.saveOffsetsInString();
1806     float deltaX;
1807     if (codePath(run) != FontCascade::Complex)
1808         deltaX = getGlyphsAndAdvancesForSimpleText(run, 0, run.length(), glyphBuffer);
1809     else
1810         deltaX = getGlyphsAndAdvancesForComplexText(run, 0, run.length(), glyphBuffer);
1811
1812     if (!glyphBuffer.size())
1813         return DashArray();
1814
1815     FloatPoint origin = FloatPoint(textOrigin.x() + deltaX, textOrigin.y());
1816     GlyphToPathTranslator translator(run, glyphBuffer, origin);
1817     DashArray result;
1818     for (unsigned index = 0; translator.containsMorePaths(); ++index, translator.advance()) {
1819         GlyphIterationState info = { FloatPoint(0, 0), FloatPoint(0, 0), lineExtents.y(), lineExtents.y() + lineExtents.height(), lineExtents.x() + lineExtents.width(), lineExtents.x() };
1820         const Font* localFont = glyphBuffer.fontAt(index);
1821         if (!localFont) {
1822             // The advances will get all messed up if we do anything other than bail here.
1823             result.clear();
1824             break;
1825         }
1826         switch (translator.underlineType()) {
1827         case GlyphUnderlineType::SkipDescenders: {
1828             Path path = translator.path();
1829             path.apply([&](const PathElement& element) {
1830                 findPathIntersections(info, element);
1831             });
1832             if (info.minX < info.maxX) {
1833                 result.append(info.minX - lineExtents.x());
1834                 result.append(info.maxX - lineExtents.x());
1835             }
1836             break;
1837         }
1838         case GlyphUnderlineType::SkipGlyph: {
1839             std::pair<float, float> extents = translator.extents();
1840             result.append(extents.first - lineExtents.x());
1841             result.append(extents.second - lineExtents.x());
1842             break;
1843         }
1844         case GlyphUnderlineType::DrawOverGlyph:
1845             // Nothing to do
1846             break;
1847         }
1848     }
1849     return result;
1850 }
1851
1852 }