Replace CaseFoldingHash with ASCIICaseInsensitiveHash
[WebKit-https.git] / Source / WebCore / platform / graphics / FontCache.cpp
1 /*
2  * Copyright (C) 2006, 2008, 2013 Apple Inc. All rights reserved.
3  * Copyright (C) 2007 Nicholas Shanks <webkit@nickshanks.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer. 
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution. 
14  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission. 
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #include "config.h"
31 #include "FontCache.h"
32
33 #include "FontCascade.h"
34 #include "FontPlatformData.h"
35 #include "FontSelector.h"
36 #include "MemoryPressureHandler.h"
37 #include "WebKitFontFamilyNames.h"
38 #include <wtf/HashMap.h>
39 #include <wtf/ListHashSet.h>
40 #include <wtf/NeverDestroyed.h>
41 #include <wtf/StdLibExtras.h>
42 #include <wtf/TemporaryChange.h>
43 #include <wtf/text/AtomicStringHash.h>
44 #include <wtf/text/StringHash.h>
45
46 #if ENABLE(OPENTYPE_VERTICAL)
47 #include "OpenTypeVerticalData.h"
48 #endif
49
50 #if PLATFORM(IOS)
51 #include <wtf/Noncopyable.h>
52
53 // FIXME: We may be able to simplify this code using C++11 threading primitives, including std::call_once().
54 static pthread_mutex_t fontLock;
55
56 static void initFontCacheLockOnce()
57 {
58     pthread_mutexattr_t mutexAttribute;
59     pthread_mutexattr_init(&mutexAttribute);
60     pthread_mutexattr_settype(&mutexAttribute, PTHREAD_MUTEX_RECURSIVE);
61     pthread_mutex_init(&fontLock, &mutexAttribute);
62     pthread_mutexattr_destroy(&mutexAttribute);
63 }
64
65 static pthread_once_t initFontLockControl = PTHREAD_ONCE_INIT;
66
67 class FontLocker {
68     WTF_MAKE_NONCOPYABLE(FontLocker);
69 public:
70     FontLocker()
71     {
72         pthread_once(&initFontLockControl, initFontCacheLockOnce);
73         int lockcode = pthread_mutex_lock(&fontLock);
74         ASSERT_WITH_MESSAGE_UNUSED(lockcode, !lockcode, "fontLock lock failed with code:%d", lockcode);    
75     }
76     ~FontLocker()
77     {
78         int lockcode = pthread_mutex_unlock(&fontLock);
79         ASSERT_WITH_MESSAGE_UNUSED(lockcode, !lockcode, "fontLock unlock failed with code:%d", lockcode);
80     }
81 };
82 #endif // PLATFORM(IOS)
83
84 using namespace WTF;
85
86 namespace WebCore {
87
88 FontCache& FontCache::singleton()
89 {
90     static NeverDestroyed<FontCache> globalFontCache;
91     return globalFontCache;
92 }
93
94 FontCache::FontCache()
95     : m_purgeTimer(*this, &FontCache::purgeInactiveFontDataIfNeeded)
96 {
97 }
98
99 struct FontPlatformDataCacheKey {
100     AtomicString family;
101     FontDescriptionKey description;
102
103     FontPlatformDataCacheKey() = default;
104     FontPlatformDataCacheKey(const AtomicString& family, const FontDescription& description)
105         : family(family), description(description)
106     {
107     }
108
109     explicit FontPlatformDataCacheKey(HashTableDeletedValueType)
110         : description(HashTableDeletedValue)
111     {
112     }
113     bool isHashTableDeletedValue() const
114     {
115         return description.isHashTableDeletedValue();
116     }
117 };
118
119 struct FontPlatformDataCacheKeyHash {
120     static unsigned hash(const FontPlatformDataCacheKey& key)
121     {
122         return pairIntHash(ASCIICaseInsensitiveHash::hash(key.family), key.description.computeHash());
123     }
124     static bool equal(const FontPlatformDataCacheKey& a, const FontPlatformDataCacheKey& b)
125     {
126         return a.description == b.description && equalIgnoringASCIICase(a.family, b.family);
127     }
128     static const bool safeToCompareToEmptyOrDeleted = true;
129 };
130
131 struct FontPlatformDataCacheKeyTraits : SimpleClassHashTraits<FontPlatformDataCacheKey> {
132     static const bool hasIsEmptyValueFunction = true;
133     static bool isEmptyValue(const FontPlatformDataCacheKey& key)
134     {
135         return key.family.isNull();
136     }
137 };
138
139 typedef HashMap<FontPlatformDataCacheKey, std::unique_ptr<FontPlatformData>, FontPlatformDataCacheKeyHash, FontPlatformDataCacheKeyTraits> FontPlatformDataCache;
140
141 static FontPlatformDataCache& fontPlatformDataCache()
142 {
143     static NeverDestroyed<FontPlatformDataCache> cache;
144     return cache;
145 }
146
147 static AtomicString alternateFamilyName(const AtomicString& familyName)
148 {
149     switch (familyName.length()) {
150     case 5:
151         if (equalLettersIgnoringASCIICase(familyName, "arial"))
152             return AtomicString("Helvetica", AtomicString::ConstructFromLiteral);
153         if (equalLettersIgnoringASCIICase(familyName, "times"))
154             return AtomicString("Times New Roman", AtomicString::ConstructFromLiteral);
155         break;
156     case 7:
157         if (equalLettersIgnoringASCIICase(familyName, "courier"))
158             return AtomicString("Courier New", AtomicString::ConstructFromLiteral);
159         break;
160 #if OS(WINDOWS)
161     // On Windows, we don't support bitmap fonts, but legacy content expects support.
162     // Thus we allow Times New Roman as an alternative for the bitmap font MS Serif,
163     // even if the webpage does not specify fallback.
164     // FIXME: Seems unlikely this is still needed. If it was really needed, I think we
165     // would need it on other platforms too.
166     case 8:
167         if (equalLettersIgnoringASCIICase(familyName, "ms serif"))
168             return AtomicString("Times New Roman", AtomicString::ConstructFromLiteral);
169         break;
170 #endif
171     case 9:
172         if (equalLettersIgnoringASCIICase(familyName, "helvetica"))
173             return AtomicString("Arial", AtomicString::ConstructFromLiteral);
174         break;
175 #if !OS(WINDOWS)
176     // On Windows, Courier New is a TrueType font that is always present and
177     // Courier is a bitmap font that we do not support. So, we don't want to map
178     // Courier New to Courier.
179     // FIXME: Not sure why this is harmful on Windows, since the alternative will
180     // only be tried if Courier New is not found.
181     case 11:
182         if (equalLettersIgnoringASCIICase(familyName, "courier new"))
183             return AtomicString("Courier", AtomicString::ConstructFromLiteral);
184         break;
185 #endif
186 #if OS(WINDOWS)
187     // On Windows, we don't support bitmap fonts, but legacy content expects support.
188     // Thus we allow Microsoft Sans Serif as an alternative for the bitmap font MS Sans Serif,
189     // even if the webpage does not specify fallback.
190     // FIXME: Seems unlikely this is still needed. If it was really needed, I think we
191     // would need it on other platforms too.
192     case 13:
193         if (equalLettersIgnoringASCIICase(familyName, "ms sans serif"))
194             return AtomicString("Microsoft Sans Serif", AtomicString::ConstructFromLiteral);
195         break;
196 #endif
197     case 15:
198         if (equalLettersIgnoringASCIICase(familyName, "times new roman"))
199             return AtomicString("Times", AtomicString::ConstructFromLiteral);
200         break;
201     }
202
203     return nullAtom;
204 }
205
206 // FIXME: This function name should not have the word "get" in it for WebKit coding style.
207 // FIXME: The boolean here is poor coding style. Easy to factor this into two functions so we don't need it.
208 FontPlatformData* FontCache::getCachedFontPlatformData(const FontDescription& fontDescription, const AtomicString& passedFamilyName, bool checkingAlternateName)
209 {
210 #if PLATFORM(IOS)
211     FontLocker fontLocker;
212 #endif
213     
214 #if OS(WINDOWS) && ENABLE(OPENTYPE_VERTICAL)
215     // Leading "@" in the font name enables Windows vertical flow flag for the font.
216     // Because we do vertical flow by ourselves, we don't want to use the Windows feature.
217     // IE disregards "@" regardless of the orientation, so we follow the behavior.
218     const AtomicString& familyName = passedFamilyName[0] != '@'
219         ? passedFamilyName : AtomicString(passedFamilyName.impl()->substring(1));
220 #else
221     const AtomicString& familyName = passedFamilyName;
222 #endif
223
224     static bool initialized;
225     if (!initialized) {
226         platformInit();
227         initialized = true;
228     }
229
230     FontPlatformDataCacheKey key(familyName, fontDescription);
231
232     auto addResult = fontPlatformDataCache().add(key, nullptr);
233     FontPlatformDataCache::iterator it = addResult.iterator;
234     if (addResult.isNewEntry) {
235         it->value = createFontPlatformData(fontDescription, familyName);
236         if (!it->value && !checkingAlternateName) {
237             // We were unable to find a font. We have a small set of fonts that we alias to other names,
238             // e.g., Arial/Helvetica, Courier/Courier New, etc. Try looking up the font under the aliased name.
239             auto alternateName = alternateFamilyName(familyName);
240             if (!alternateName.isNull()) {
241                 FontPlatformData* fontPlatformDataForAlternateName = getCachedFontPlatformData(fontDescription, alternateName, true);
242                 // Look up the key in the hash table again as the previous iterator may have
243                 // been invalidated by the recursive call to getCachedFontPlatformData().
244                 it = fontPlatformDataCache().find(key);
245                 ASSERT(it != fontPlatformDataCache().end());
246                 if (fontPlatformDataForAlternateName)
247                     it->value = std::make_unique<FontPlatformData>(*fontPlatformDataForAlternateName);
248             }
249         }
250     }
251
252     return it->value.get();
253 }
254
255 #if ENABLE(OPENTYPE_VERTICAL)
256 struct FontVerticalDataCacheKeyHash {
257     static unsigned hash(const FontCache::FontFileKey& fontFileKey)
258     {
259         return PtrHash<const FontCache::FontFileKey*>::hash(&fontFileKey);
260     }
261
262     static bool equal(const FontCache::FontFileKey& a, const FontCache::FontFileKey& b)
263     {
264         return a == b;
265     }
266
267     static const bool safeToCompareToEmptyOrDeleted = true;
268 };
269
270 struct FontVerticalDataCacheKeyTraits : WTF::GenericHashTraits<FontCache::FontFileKey> {
271     static const bool emptyValueIsZero = true;
272     static const bool needsDestruction = true;
273     static const FontCache::FontFileKey& emptyValue()
274     {
275         static NeverDestroyed<FontCache::FontFileKey> key = nullAtom;
276         return key;
277     }
278     static void constructDeletedValue(FontCache::FontFileKey& slot)
279     {
280         new (NotNull, &slot) FontCache::FontFileKey(HashTableDeletedValue);
281     }
282     static bool isDeletedValue(const FontCache::FontFileKey& value)
283     {
284         return value.isHashTableDeletedValue();
285     }
286 };
287
288 typedef HashMap<FontCache::FontFileKey, RefPtr<OpenTypeVerticalData>, FontVerticalDataCacheKeyHash, FontVerticalDataCacheKeyTraits> FontVerticalDataCache;
289
290 FontVerticalDataCache& fontVerticalDataCacheInstance()
291 {
292     static NeverDestroyed<FontVerticalDataCache> fontVerticalDataCache;
293     return fontVerticalDataCache;
294 }
295
296 PassRefPtr<OpenTypeVerticalData> FontCache::getVerticalData(const FontFileKey& key, const FontPlatformData& platformData)
297 {
298     FontVerticalDataCache& fontVerticalDataCache = fontVerticalDataCacheInstance();
299     FontVerticalDataCache::iterator result = fontVerticalDataCache.find(key);
300     if (result != fontVerticalDataCache.end())
301         return result.get()->value;
302
303     RefPtr<OpenTypeVerticalData> verticalData = OpenTypeVerticalData::create(platformData);
304     if (!verticalData->isOpenType())
305         verticalData = nullptr;
306     fontVerticalDataCache.set(key, verticalData);
307     return verticalData;
308 }
309 #endif
310
311 struct FontDataCacheKeyHash {
312     static unsigned hash(const FontPlatformData& platformData)
313     {
314         return platformData.hash();
315     }
316          
317     static bool equal(const FontPlatformData& a, const FontPlatformData& b)
318     {
319         return a == b;
320     }
321
322     static const bool safeToCompareToEmptyOrDeleted = true;
323 };
324
325 struct FontDataCacheKeyTraits : WTF::GenericHashTraits<FontPlatformData> {
326     static const bool emptyValueIsZero = true;
327     static const FontPlatformData& emptyValue()
328     {
329         static NeverDestroyed<FontPlatformData> key(0.f, false, false);
330         return key;
331     }
332     static void constructDeletedValue(FontPlatformData& slot)
333     {
334         new (NotNull, &slot) FontPlatformData(HashTableDeletedValue);
335     }
336     static bool isDeletedValue(const FontPlatformData& value)
337     {
338         return value.isHashTableDeletedValue();
339     }
340 };
341
342 typedef HashMap<FontPlatformData, RefPtr<Font>, FontDataCacheKeyHash, FontDataCacheKeyTraits> FontDataCache;
343
344 static FontDataCache& cachedFonts()
345 {
346     static NeverDestroyed<FontDataCache> cache;
347     return cache;
348 }
349
350
351 #if PLATFORM(IOS)
352 const unsigned cMaxInactiveFontData = 120;
353 const unsigned cTargetInactiveFontData = 100;
354 #else
355 const unsigned cMaxInactiveFontData = 225;
356 const unsigned cTargetInactiveFontData = 200;
357 #endif
358
359 const unsigned cMaxUnderMemoryPressureInactiveFontData = 50;
360 const unsigned cTargetUnderMemoryPressureInactiveFontData = 30;
361
362 RefPtr<Font> FontCache::fontForFamily(const FontDescription& fontDescription, const AtomicString& family, bool checkingAlternateName)
363 {
364     if (!m_purgeTimer.isActive())
365         m_purgeTimer.startOneShot(std::chrono::milliseconds::zero());
366
367     FontPlatformData* platformData = getCachedFontPlatformData(fontDescription, family, checkingAlternateName);
368     if (!platformData)
369         return nullptr;
370
371     return fontForPlatformData(*platformData);
372 }
373
374 Ref<Font> FontCache::fontForPlatformData(const FontPlatformData& platformData)
375 {
376 #if PLATFORM(IOS)
377     FontLocker fontLocker;
378 #endif
379     
380     auto addResult = cachedFonts().add(platformData, nullptr);
381     if (addResult.isNewEntry)
382         addResult.iterator->value = Font::create(platformData);
383
384     return *addResult.iterator->value;
385 }
386
387 void FontCache::purgeInactiveFontDataIfNeeded()
388 {
389     bool underMemoryPressure = MemoryPressureHandler::singleton().isUnderMemoryPressure();
390     unsigned inactiveFontDataLimit = underMemoryPressure ? cMaxUnderMemoryPressureInactiveFontData : cMaxInactiveFontData;
391
392     if (cachedFonts().size() < inactiveFontDataLimit)
393         return;
394     unsigned inactiveCount = inactiveFontCount();
395     if (inactiveCount <= inactiveFontDataLimit)
396         return;
397
398     unsigned targetFontDataLimit = underMemoryPressure ? cTargetUnderMemoryPressureInactiveFontData : cTargetInactiveFontData;
399     purgeInactiveFontData(inactiveCount - targetFontDataLimit);
400 }
401
402 void FontCache::purgeInactiveFontData(unsigned purgeCount)
403 {
404     pruneUnreferencedEntriesFromFontCascadeCache();
405     pruneSystemFallbackFonts();
406
407 #if PLATFORM(IOS)
408     FontLocker fontLocker;
409 #endif
410
411     while (purgeCount) {
412         Vector<RefPtr<Font>, 20> fontsToDelete;
413         for (auto& font : cachedFonts().values()) {
414             if (!font->hasOneRef())
415                 continue;
416             fontsToDelete.append(WTFMove(font));
417             if (!--purgeCount)
418                 break;
419         }
420         // Fonts may ref other fonts so we loop until there are no changes.
421         if (fontsToDelete.isEmpty())
422             break;
423         for (auto& font : fontsToDelete)
424             cachedFonts().remove(font->platformData());
425     };
426
427     Vector<FontPlatformDataCacheKey> keysToRemove;
428     keysToRemove.reserveInitialCapacity(fontPlatformDataCache().size());
429     for (auto& entry : fontPlatformDataCache()) {
430         if (entry.value && !cachedFonts().contains(*entry.value))
431             keysToRemove.append(entry.key);
432     }
433     for (auto& key : keysToRemove)
434         fontPlatformDataCache().remove(key);
435
436 #if ENABLE(OPENTYPE_VERTICAL)
437     FontVerticalDataCache& fontVerticalDataCache = fontVerticalDataCacheInstance();
438     if (!fontVerticalDataCache.isEmpty()) {
439         // Mark & sweep unused verticalData
440         for (auto& verticalData : fontVerticalDataCache.values()) {
441             if (verticalData)
442                 verticalData->m_inFontCache = false;
443         }
444         for (auto& font : cachedFonts().values()) {
445             auto* verticalData = const_cast<OpenTypeVerticalData*>(font->verticalData());
446             if (verticalData)
447                 verticalData->m_inFontCache = true;
448         }
449         Vector<FontFileKey> keysToRemove;
450         keysToRemove.reserveInitialCapacity(fontVerticalDataCache.size());
451         for (auto& it : fontVerticalDataCache) {
452             if (!it.value || !it.value->m_inFontCache)
453                 keysToRemove.append(it.key);
454         }
455         for (auto& key : keysToRemove)
456             fontVerticalDataCache.remove(key);
457     }
458 #endif
459
460     platformPurgeInactiveFontData();
461 }
462
463 size_t FontCache::fontCount()
464 {
465     return cachedFonts().size();
466 }
467
468 size_t FontCache::inactiveFontCount()
469 {
470 #if PLATFORM(IOS)
471     FontLocker fontLocker;
472 #endif
473     unsigned count = 0;
474     for (auto& font : cachedFonts().values()) {
475         if (font->hasOneRef())
476             ++count;
477     }
478     return count;
479 }
480
481 static HashSet<FontSelector*>* gClients;
482
483 void FontCache::addClient(FontSelector* client)
484 {
485     if (!gClients)
486         gClients = new HashSet<FontSelector*>;
487
488     ASSERT(!gClients->contains(client));
489     gClients->add(client);
490 }
491
492 void FontCache::removeClient(FontSelector* client)
493 {
494     ASSERT(gClients);
495     ASSERT(gClients->contains(client));
496
497     gClients->remove(client);
498 }
499
500 static unsigned short gGeneration = 0;
501
502 unsigned short FontCache::generation()
503 {
504     return gGeneration;
505 }
506
507 void FontCache::invalidate()
508 {
509     if (!gClients) {
510         ASSERT(fontPlatformDataCache().isEmpty());
511         return;
512     }
513
514     fontPlatformDataCache().clear();
515     invalidateFontCascadeCache();
516
517     gGeneration++;
518
519     Vector<Ref<FontSelector>> clients;
520     clients.reserveInitialCapacity(gClients->size());
521     for (auto it = gClients->begin(), end = gClients->end(); it != end; ++it)
522         clients.uncheckedAppend(**it);
523
524     for (unsigned i = 0; i < clients.size(); ++i)
525         clients[i]->fontCacheInvalidated();
526
527     purgeInactiveFontData();
528 }
529
530 #if !PLATFORM(COCOA)
531 RefPtr<Font> FontCache::similarFont(const FontDescription&, const AtomicString&)
532 {
533     return nullptr;
534 }
535 #endif
536
537 } // namespace WebCore