Regression(r147639) Causes assertion hit in HashTable
[WebKit-https.git] / Source / WebCore / platform / graphics / FontCache.cpp
1 /*
2  * Copyright (C) 2006, 2008 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 Computer, 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 "Font.h"
34 #include "FontFallbackList.h"
35 #include "FontPlatformData.h"
36 #include "FontSelector.h"
37 #include "OpenTypeVerticalData.h"
38 #include "WebKitFontFamilyNames.h"
39 #include <wtf/HashMap.h>
40 #include <wtf/ListHashSet.h>
41 #include <wtf/StdLibExtras.h>
42 #include <wtf/text/AtomicStringHash.h>
43 #include <wtf/text/StringHash.h>
44
45 using namespace WTF;
46
47 namespace WebCore {
48
49 FontCache* fontCache()
50 {
51     DEFINE_STATIC_LOCAL(FontCache, globalFontCache, ());
52     return &globalFontCache;
53 }
54
55 FontCache::FontCache()
56     : m_purgePreventCount(0)
57 {
58 }
59
60 struct FontPlatformDataCacheKey {
61     WTF_MAKE_FAST_ALLOCATED;
62 public:
63     FontPlatformDataCacheKey(const AtomicString& family = AtomicString(), unsigned size = 0, unsigned weight = 0, bool italic = false,
64                              bool isPrinterFont = false, FontRenderingMode renderingMode = NormalRenderingMode, FontOrientation orientation = Horizontal,
65                              FontWidthVariant widthVariant = RegularWidth)
66         : m_size(size)
67         , m_weight(weight)
68         , m_family(family)
69         , m_italic(italic)
70         , m_printerFont(isPrinterFont)
71         , m_renderingMode(renderingMode)
72         , m_orientation(orientation)
73         , m_widthVariant(widthVariant)
74     {
75     }
76
77     FontPlatformDataCacheKey(HashTableDeletedValueType) : m_size(hashTableDeletedSize()) { }
78     bool isHashTableDeletedValue() const { return m_size == hashTableDeletedSize(); }
79
80     bool operator==(const FontPlatformDataCacheKey& other) const
81     {
82         return equalIgnoringCase(m_family, other.m_family) && m_size == other.m_size && 
83                m_weight == other.m_weight && m_italic == other.m_italic && m_printerFont == other.m_printerFont &&
84                m_renderingMode == other.m_renderingMode && m_orientation == other.m_orientation && m_widthVariant == other.m_widthVariant;
85     }
86
87     unsigned m_size;
88     unsigned m_weight;
89     AtomicString m_family;
90     bool m_italic;
91     bool m_printerFont;
92     FontRenderingMode m_renderingMode;
93     FontOrientation m_orientation;
94     FontWidthVariant m_widthVariant;
95
96 private:
97     static unsigned hashTableDeletedSize() { return 0xFFFFFFFFU; }
98 };
99
100 inline unsigned computeHash(const FontPlatformDataCacheKey& fontKey)
101 {
102     unsigned hashCodes[5] = {
103         CaseFoldingHash::hash(fontKey.m_family),
104         fontKey.m_size,
105         fontKey.m_weight,
106         fontKey.m_widthVariant,
107         static_cast<unsigned>(fontKey.m_orientation) << 3 | static_cast<unsigned>(fontKey.m_italic) << 2 | static_cast<unsigned>(fontKey.m_printerFont) << 1 | static_cast<unsigned>(fontKey.m_renderingMode)
108     };
109     return StringHasher::hashMemory<sizeof(hashCodes)>(hashCodes);
110 }
111
112 struct FontPlatformDataCacheKeyHash {
113     static unsigned hash(const FontPlatformDataCacheKey& font)
114     {
115         return computeHash(font);
116     }
117          
118     static bool equal(const FontPlatformDataCacheKey& a, const FontPlatformDataCacheKey& b)
119     {
120         return a == b;
121     }
122
123     static const bool safeToCompareToEmptyOrDeleted = true;
124 };
125
126 struct FontPlatformDataCacheKeyTraits : WTF::SimpleClassHashTraits<FontPlatformDataCacheKey> { };
127
128 typedef HashMap<FontPlatformDataCacheKey, OwnPtr<FontPlatformData>, FontPlatformDataCacheKeyHash, FontPlatformDataCacheKeyTraits> FontPlatformDataCache;
129
130 static FontPlatformDataCache* gFontPlatformDataCache = 0;
131
132 static const AtomicString& alternateFamilyName(const AtomicString& familyName)
133 {
134     // Alias Courier <-> Courier New
135     DEFINE_STATIC_LOCAL(AtomicString, courier, ("Courier", AtomicString::ConstructFromLiteral));
136     DEFINE_STATIC_LOCAL(AtomicString, courierNew, ("Courier New", AtomicString::ConstructFromLiteral));
137     if (equalIgnoringCase(familyName, courier))
138         return courierNew;
139 #if !OS(WINDOWS)
140     // On Windows, Courier New (truetype font) is always present and
141     // Courier is a bitmap font. So, we don't want to map Courier New to
142     // Courier.
143     if (equalIgnoringCase(familyName, courierNew))
144         return courier;
145 #endif
146
147     // Alias Times and Times New Roman.
148     DEFINE_STATIC_LOCAL(AtomicString, times, ("Times", AtomicString::ConstructFromLiteral));
149     DEFINE_STATIC_LOCAL(AtomicString, timesNewRoman, ("Times New Roman", AtomicString::ConstructFromLiteral));
150     if (equalIgnoringCase(familyName, times))
151         return timesNewRoman;
152     if (equalIgnoringCase(familyName, timesNewRoman))
153         return times;
154     
155     // Alias Arial and Helvetica
156     DEFINE_STATIC_LOCAL(AtomicString, arial, ("Arial", AtomicString::ConstructFromLiteral));
157     DEFINE_STATIC_LOCAL(AtomicString, helvetica, ("Helvetica", AtomicString::ConstructFromLiteral));
158     if (equalIgnoringCase(familyName, arial))
159         return helvetica;
160     if (equalIgnoringCase(familyName, helvetica))
161         return arial;
162
163 #if OS(WINDOWS)
164     // On Windows, bitmap fonts are blocked altogether so that we have to 
165     // alias MS Sans Serif (bitmap font) -> Microsoft Sans Serif (truetype font)
166     DEFINE_STATIC_LOCAL(AtomicString, msSans, ("MS Sans Serif", AtomicString::ConstructFromLiteral));
167     DEFINE_STATIC_LOCAL(AtomicString, microsoftSans, ("Microsoft Sans Serif", AtomicString::ConstructFromLiteral));
168     if (equalIgnoringCase(familyName, msSans))
169         return microsoftSans;
170
171     // Alias MS Serif (bitmap) -> Times New Roman (truetype font). There's no 
172     // 'Microsoft Sans Serif-equivalent' for Serif.
173     DEFINE_STATIC_LOCAL(AtomicString, msSerif, ("MS Serif", AtomicString::ConstructFromLiteral));
174     if (equalIgnoringCase(familyName, msSerif))
175         return timesNewRoman;
176 #endif
177
178     return emptyAtom;
179 }
180
181 FontPlatformData* FontCache::getCachedFontPlatformData(const FontDescription& fontDescription,
182                                                        const AtomicString& passedFamilyName,
183                                                        bool checkingAlternateName)
184 {
185 #if OS(WINDOWS) && ENABLE(OPENTYPE_VERTICAL)
186     // Leading "@" in the font name enables Windows vertical flow flag for the font.
187     // Because we do vertical flow by ourselves, we don't want to use the Windows feature.
188     // IE disregards "@" regardless of the orientatoin, so we follow the behavior.
189     const AtomicString& familyName = (passedFamilyName.isEmpty() || passedFamilyName[0] != '@') ?
190         passedFamilyName : AtomicString(passedFamilyName.impl()->substring(1));
191 #else
192     const AtomicString& familyName = passedFamilyName;
193 #endif
194
195     if (!gFontPlatformDataCache) {
196         gFontPlatformDataCache = new FontPlatformDataCache;
197         platformInit();
198     }
199
200     FontPlatformDataCacheKey key(familyName, fontDescription.computedPixelSize(), fontDescription.weight(), fontDescription.italic(),
201                                  fontDescription.usePrinterFont(), fontDescription.renderingMode(), fontDescription.orientation(),
202                                  fontDescription.widthVariant());
203
204     FontPlatformDataCache::AddResult result = gFontPlatformDataCache->add(key, nullptr);
205     FontPlatformDataCache::iterator it = result.iterator;
206     if (result.isNewEntry) {
207         it->value = createFontPlatformData(fontDescription, familyName);
208
209         if (!it->value && !checkingAlternateName) {
210             // We were unable to find a font.  We have a small set of fonts that we alias to other names,
211             // e.g., Arial/Helvetica, Courier/Courier New, etc.  Try looking up the font under the aliased name.
212             const AtomicString& alternateName = alternateFamilyName(familyName);
213             if (!alternateName.isEmpty()) {
214                 FontPlatformData* fontPlatformDataForAlternateName = getCachedFontPlatformData(fontDescription, alternateName, true);
215                 // Lookup the key in the hash table again as the previous iterator may have
216                 // been invalidated by the recursive call to getCachedFontPlatformData().
217                 it = gFontPlatformDataCache->find(key);
218                 ASSERT(it != gFontPlatformDataCache->end());
219                 if (fontPlatformDataForAlternateName)
220                     it->value = adoptPtr(new FontPlatformData(*fontPlatformDataForAlternateName));
221             }
222         }
223     }
224
225     return it->value.get();
226 }
227
228 #if ENABLE(OPENTYPE_VERTICAL)
229 typedef HashMap<FontCache::FontFileKey, RefPtr<OpenTypeVerticalData>, WTF::IntHash<FontCache::FontFileKey>, WTF::UnsignedWithZeroKeyHashTraits<FontCache::FontFileKey> > FontVerticalDataCache;
230
231 FontVerticalDataCache& fontVerticalDataCacheInstance()
232 {
233     DEFINE_STATIC_LOCAL(FontVerticalDataCache, fontVerticalDataCache, ());
234     return fontVerticalDataCache;
235 }
236
237 PassRefPtr<OpenTypeVerticalData> FontCache::getVerticalData(const FontFileKey& key, const FontPlatformData& platformData)
238 {
239     FontVerticalDataCache& fontVerticalDataCache = fontVerticalDataCacheInstance();
240     FontVerticalDataCache::iterator result = fontVerticalDataCache.find(key);
241     if (result != fontVerticalDataCache.end())
242         return result.get()->value;
243
244     RefPtr<OpenTypeVerticalData> verticalData = OpenTypeVerticalData::create(platformData);
245     if (!verticalData->isOpenType())
246         verticalData.clear();
247     fontVerticalDataCache.set(key, verticalData);
248     return verticalData;
249 }
250 #endif
251
252 struct FontDataCacheKeyHash {
253     static unsigned hash(const FontPlatformData& platformData)
254     {
255         return platformData.hash();
256     }
257          
258     static bool equal(const FontPlatformData& a, const FontPlatformData& b)
259     {
260         return a == b;
261     }
262
263     static const bool safeToCompareToEmptyOrDeleted = true;
264 };
265
266 struct FontDataCacheKeyTraits : WTF::GenericHashTraits<FontPlatformData> {
267     static const bool emptyValueIsZero = true;
268     static const bool needsDestruction = true;
269     static const FontPlatformData& emptyValue()
270     {
271         DEFINE_STATIC_LOCAL(FontPlatformData, key, (0.f, false, false));
272         return key;
273     }
274     static void constructDeletedValue(FontPlatformData& slot)
275     {
276         new (NotNull, &slot) FontPlatformData(HashTableDeletedValue);
277     }
278     static bool isDeletedValue(const FontPlatformData& value)
279     {
280         return value.isHashTableDeletedValue();
281     }
282 };
283
284 typedef HashMap<FontPlatformData, pair<RefPtr<SimpleFontData>, unsigned>, FontDataCacheKeyHash, FontDataCacheKeyTraits> FontDataCache;
285
286 static FontDataCache* gFontDataCache = 0;
287
288 #if PLATFORM(CHROMIUM) && !OS(ANDROID)
289 const int cMaxInactiveFontData = 250;
290 const int cTargetInactiveFontData = 200;
291 #else
292 const int cMaxInactiveFontData = 225;
293 const int cTargetInactiveFontData = 200;
294 #endif
295 static ListHashSet<RefPtr<SimpleFontData> >* gInactiveFontData = 0;
296
297 PassRefPtr<SimpleFontData> FontCache::getCachedFontData(const FontDescription& fontDescription, const AtomicString& family, bool checkingAlternateName, ShouldRetain shouldRetain)
298 {
299     FontPlatformData* platformData = getCachedFontPlatformData(fontDescription, family, checkingAlternateName);
300     if (!platformData)
301         return 0;
302
303     return getCachedFontData(platformData, shouldRetain);
304 }
305
306 PassRefPtr<SimpleFontData> FontCache::getCachedFontData(const FontPlatformData* platformData, ShouldRetain shouldRetain)
307 {
308     if (!platformData)
309         return 0;
310
311 #if !ASSERT_DISABLED
312     if (shouldRetain == DoNotRetain)
313         ASSERT(m_purgePreventCount);
314 #endif
315
316     if (!gFontDataCache) {
317         gFontDataCache = new FontDataCache;
318         gInactiveFontData = new ListHashSet<RefPtr<SimpleFontData> >;
319     }
320
321     FontDataCache::iterator result = gFontDataCache->find(*platformData);
322     if (result == gFontDataCache->end()) {
323         pair<RefPtr<SimpleFontData>, unsigned> newValue(SimpleFontData::create(*platformData), shouldRetain == Retain ? 1 : 0);
324         gFontDataCache->set(*platformData, newValue);
325         if (shouldRetain == DoNotRetain)
326             gInactiveFontData->add(newValue.first);
327         return newValue.first.release();
328     }
329
330     if (!result.get()->value.second) {
331         ASSERT(gInactiveFontData->contains(result.get()->value.first));
332         gInactiveFontData->remove(result.get()->value.first);
333     }
334
335     if (shouldRetain == Retain)
336         result.get()->value.second++;
337     else if (!result.get()->value.second) {
338         // If shouldRetain is DoNotRetain and count is 0, we want to remove the fontData from 
339         // gInactiveFontData (above) and re-add here to update LRU position.
340         gInactiveFontData->add(result.get()->value.first);
341     }
342
343     return result.get()->value.first;
344 }
345
346 SimpleFontData* FontCache::getNonRetainedLastResortFallbackFont(const FontDescription& fontDescription)
347 {
348     return getLastResortFallbackFont(fontDescription, DoNotRetain).leakRef();
349 }
350
351 void FontCache::releaseFontData(const SimpleFontData* fontData)
352 {
353     ASSERT(gFontDataCache);
354     ASSERT(!fontData->isCustomFont());
355
356     FontDataCache::iterator it = gFontDataCache->find(fontData->platformData());
357     ASSERT(it != gFontDataCache->end());
358     if (it == gFontDataCache->end())
359         return;
360
361     ASSERT(it->value.second);
362     if (!--it->value.second)
363         gInactiveFontData->add(it->value.first);
364 }
365
366 void FontCache::purgeInactiveFontDataIfNeeded()
367 {
368     if (gInactiveFontData && !m_purgePreventCount && gInactiveFontData->size() > cMaxInactiveFontData)
369         purgeInactiveFontData(gInactiveFontData->size() - cTargetInactiveFontData);
370 }
371
372 void FontCache::purgeInactiveFontData(int count)
373 {
374     if (!gInactiveFontData || m_purgePreventCount)
375         return;
376
377     static bool isPurging;  // Guard against reentry when e.g. a deleted FontData releases its small caps FontData.
378     if (isPurging)
379         return;
380
381     isPurging = true;
382
383     Vector<RefPtr<SimpleFontData>, 20> fontDataToDelete;
384     ListHashSet<RefPtr<SimpleFontData> >::iterator end = gInactiveFontData->end();
385     ListHashSet<RefPtr<SimpleFontData> >::iterator it = gInactiveFontData->begin();
386     for (int i = 0; i < count && it != end; ++it, ++i) {
387         RefPtr<SimpleFontData>& fontData = *it.get();
388         gFontDataCache->remove(fontData->platformData());
389         // We should not delete SimpleFontData here because deletion can modify gInactiveFontData. See http://trac.webkit.org/changeset/44011
390         fontDataToDelete.append(fontData);
391     }
392
393     if (it == end) {
394         // Removed everything
395         gInactiveFontData->clear();
396     } else {
397         for (int i = 0; i < count; ++i)
398             gInactiveFontData->remove(gInactiveFontData->begin());
399     }
400
401     fontDataToDelete.clear();
402
403     if (gFontPlatformDataCache) {
404         Vector<FontPlatformDataCacheKey> keysToRemove;
405         keysToRemove.reserveInitialCapacity(gFontPlatformDataCache->size());
406         FontPlatformDataCache::iterator platformDataEnd = gFontPlatformDataCache->end();
407         for (FontPlatformDataCache::iterator platformData = gFontPlatformDataCache->begin(); platformData != platformDataEnd; ++platformData) {
408             if (platformData->value && !gFontDataCache->contains(*platformData->value))
409                 keysToRemove.append(platformData->key);
410         }
411         
412         size_t keysToRemoveCount = keysToRemove.size();
413         for (size_t i = 0; i < keysToRemoveCount; ++i)
414             gFontPlatformDataCache->remove(keysToRemove[i]);
415     }
416
417 #if ENABLE(OPENTYPE_VERTICAL)
418     FontVerticalDataCache& fontVerticalDataCache = fontVerticalDataCacheInstance();
419     if (!fontVerticalDataCache.isEmpty()) {
420         // Mark & sweep unused verticalData
421         FontVerticalDataCache::iterator verticalDataEnd = fontVerticalDataCache.end();
422         for (FontVerticalDataCache::iterator verticalData = fontVerticalDataCache.begin(); verticalData != verticalDataEnd; ++verticalData) {
423             if (verticalData->value)
424                 verticalData->value->m_inFontCache = false;
425         }
426         FontDataCache::iterator fontDataEnd = gFontDataCache->end();
427         for (FontDataCache::iterator fontData = gFontDataCache->begin(); fontData != fontDataEnd; ++fontData) {
428             OpenTypeVerticalData* verticalData = const_cast<OpenTypeVerticalData*>(fontData->value.first->verticalData());
429             if (verticalData)
430                 verticalData->m_inFontCache = true;
431         }
432         Vector<FontFileKey> keysToRemove;
433         keysToRemove.reserveInitialCapacity(fontVerticalDataCache.size());
434         for (FontVerticalDataCache::iterator verticalData = fontVerticalDataCache.begin(); verticalData != verticalDataEnd; ++verticalData) {
435             if (!verticalData->value || !verticalData->value->m_inFontCache)
436                 keysToRemove.append(verticalData->key);
437         }
438         for (size_t i = 0, count = keysToRemove.size(); i < count; ++i)
439             fontVerticalDataCache.take(keysToRemove[i]);
440     }
441 #endif
442
443     isPurging = false;
444 }
445
446 size_t FontCache::fontDataCount()
447 {
448     if (gFontDataCache)
449         return gFontDataCache->size();
450     return 0;
451 }
452
453 size_t FontCache::inactiveFontDataCount()
454 {
455     if (gInactiveFontData)
456         return gInactiveFontData->size();
457     return 0;
458 }
459
460 PassRefPtr<FontData> FontCache::getFontData(const Font& font, int& familyIndex, FontSelector* fontSelector)
461 {
462     RefPtr<FontData> result;
463
464     int startIndex = familyIndex;
465     const FontFamily* startFamily = &font.fontDescription().family();
466     for (int i = 0; startFamily && i < startIndex; i++)
467         startFamily = startFamily->next();
468     const FontFamily* currFamily = startFamily;
469     while (currFamily && !result) {
470         familyIndex++;
471         if (currFamily->family().length()) {
472             if (fontSelector)
473                 result = fontSelector->getFontData(font.fontDescription(), currFamily->family());
474
475             if (!result)
476                 result = getCachedFontData(font.fontDescription(), currFamily->family());
477         }
478         currFamily = currFamily->next();
479     }
480
481     if (!currFamily)
482         familyIndex = cAllFamiliesScanned;
483
484     if (!result)
485         // We didn't find a font. Try to find a similar font using our own specific knowledge about our platform.
486         // For example on OS X, we know to map any families containing the words Arabic, Pashto, or Urdu to the
487         // Geeza Pro font.
488         result = getSimilarFontPlatformData(font);
489
490     if (!result && startIndex == 0) {
491         // If it's the primary font that we couldn't find, we try the following. In all other cases, we will
492         // just use per-character system fallback.
493
494         if (fontSelector) {
495             // Try the user's preferred standard font.
496             if (RefPtr<FontData> data = fontSelector->getFontData(font.fontDescription(), standardFamily))
497                 return data.release();
498         }
499
500         // Still no result.  Hand back our last resort fallback font.
501         result = getLastResortFallbackFont(font.fontDescription());
502     }
503     return result.release();
504 }
505
506 static HashSet<FontSelector*>* gClients;
507
508 void FontCache::addClient(FontSelector* client)
509 {
510     if (!gClients)
511         gClients = new HashSet<FontSelector*>;
512
513     ASSERT(!gClients->contains(client));
514     gClients->add(client);
515 }
516
517 void FontCache::removeClient(FontSelector* client)
518 {
519     ASSERT(gClients);
520     ASSERT(gClients->contains(client));
521
522     gClients->remove(client);
523 }
524
525 static unsigned short gGeneration = 0;
526
527 unsigned short FontCache::generation()
528 {
529     return gGeneration;
530 }
531
532 void FontCache::invalidate()
533 {
534     if (!gClients) {
535         ASSERT(!gFontPlatformDataCache);
536         return;
537     }
538
539     if (gFontPlatformDataCache)
540         gFontPlatformDataCache->clear();
541
542     gGeneration++;
543
544     Vector<RefPtr<FontSelector> > clients;
545     size_t numClients = gClients->size();
546     clients.reserveInitialCapacity(numClients);
547     HashSet<FontSelector*>::iterator end = gClients->end();
548     for (HashSet<FontSelector*>::iterator it = gClients->begin(); it != end; ++it)
549         clients.append(*it);
550
551     ASSERT(numClients == clients.size());
552     for (size_t i = 0; i < numClients; ++i)
553         clients[i]->fontCacheInvalidated();
554
555     purgeInactiveFontData();
556 }
557
558 } // namespace WebCore