f1ec9ef31c5546d02c2736b2df1fc0b7e13b3609
[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 "GlyphPageTreeNode.h"
38 #include <wtf/HashMap.h>
39 #include <wtf/ListHashSet.h>
40 #include <wtf/StdLibExtras.h>
41 #include <wtf/text/StringHash.h>
42
43 using namespace WTF;
44
45 namespace WebCore {
46
47 FontCache* fontCache()
48 {
49     DEFINE_STATIC_LOCAL(FontCache, globalFontCache, ());
50     return &globalFontCache;
51 }
52
53 FontCache::FontCache()
54     : m_purgePreventCount(0)
55 {
56 }
57
58 struct FontPlatformDataCacheKey {
59     WTF_MAKE_FAST_ALLOCATED;
60 public:
61     FontPlatformDataCacheKey(const AtomicString& family = AtomicString(), unsigned size = 0, unsigned weight = 0, bool italic = false,
62                              bool isPrinterFont = false, FontRenderingMode renderingMode = NormalRenderingMode, FontOrientation orientation = Horizontal,
63                              TextOrientation textOrientation = TextOrientationVerticalRight, FontWidthVariant widthVariant = RegularWidth)
64         : m_size(size)
65         , m_weight(weight)
66         , m_family(family)
67         , m_italic(italic)
68         , m_printerFont(isPrinterFont)
69         , m_renderingMode(renderingMode)
70         , m_orientation(orientation)
71         , m_textOrientation(textOrientation)
72         , m_widthVariant(widthVariant)
73     {
74     }
75
76     FontPlatformDataCacheKey(HashTableDeletedValueType) : m_size(hashTableDeletedSize()) { }
77     bool isHashTableDeletedValue() const { return m_size == hashTableDeletedSize(); }
78
79     bool operator==(const FontPlatformDataCacheKey& other) const
80     {
81         return equalIgnoringCase(m_family, other.m_family) && m_size == other.m_size && 
82                m_weight == other.m_weight && m_italic == other.m_italic && m_printerFont == other.m_printerFont &&
83                m_renderingMode == other.m_renderingMode && m_orientation == other.m_orientation && m_textOrientation == other.m_textOrientation && m_widthVariant == other.m_widthVariant;
84     }
85
86     unsigned m_size;
87     unsigned m_weight;
88     AtomicString m_family;
89     bool m_italic;
90     bool m_printerFont;
91     FontRenderingMode m_renderingMode;
92     FontOrientation m_orientation;
93     TextOrientation m_textOrientation;
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_textOrientation) << 4 | 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, 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"));
136     DEFINE_STATIC_LOCAL(AtomicString, courierNew, ("Courier New"));
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"));
149     DEFINE_STATIC_LOCAL(AtomicString, timesNewRoman, ("Times New Roman"));
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"));
157     DEFINE_STATIC_LOCAL(AtomicString, helvetica, ("Helvetica"));
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"));
167     DEFINE_STATIC_LOCAL(AtomicString, microsoftSans, ("Microsoft Sans Serif"));
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     static AtomicString msSerif("MS Serif");
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& familyName,
183                                                        bool checkingAlternateName)
184 {
185     if (!gFontPlatformDataCache) {
186         gFontPlatformDataCache = new FontPlatformDataCache;
187         platformInit();
188     }
189
190     FontPlatformDataCacheKey key(familyName, fontDescription.computedPixelSize(), fontDescription.weight(), fontDescription.italic(),
191                                  fontDescription.usePrinterFont(), fontDescription.renderingMode(), fontDescription.orientation(),
192                                  fontDescription.textOrientation(), fontDescription.widthVariant());
193     FontPlatformData* result = 0;
194     bool foundResult;
195     FontPlatformDataCache::iterator it = gFontPlatformDataCache->find(key);
196     if (it == gFontPlatformDataCache->end()) {
197         result = createFontPlatformData(fontDescription, familyName);
198         gFontPlatformDataCache->set(key, result);
199         foundResult = result;
200     } else {
201         result = it->second;
202         foundResult = true;
203     }
204
205     if (!foundResult && !checkingAlternateName) {
206         // We were unable to find a font.  We have a small set of fonts that we alias to other names, 
207         // e.g., Arial/Helvetica, Courier/Courier New, etc.  Try looking up the font under the aliased name.
208         const AtomicString& alternateName = alternateFamilyName(familyName);
209         if (!alternateName.isEmpty())
210             result = getCachedFontPlatformData(fontDescription, alternateName, true);
211         if (result)
212             gFontPlatformDataCache->set(key, new FontPlatformData(*result)); // Cache the result under the old name.
213     }
214
215     return result;
216 }
217
218 struct FontDataCacheKeyHash {
219     static unsigned hash(const FontPlatformData& platformData)
220     {
221         return platformData.hash();
222     }
223          
224     static bool equal(const FontPlatformData& a, const FontPlatformData& b)
225     {
226         return a == b;
227     }
228
229     static const bool safeToCompareToEmptyOrDeleted = true;
230 };
231
232 struct FontDataCacheKeyTraits : WTF::GenericHashTraits<FontPlatformData> {
233     static const bool emptyValueIsZero = true;
234     static const bool needsDestruction = true;
235     static const FontPlatformData& emptyValue()
236     {
237         DEFINE_STATIC_LOCAL(FontPlatformData, key, (0.f, false, false));
238         return key;
239     }
240     static void constructDeletedValue(FontPlatformData& slot)
241     {
242         new (&slot) FontPlatformData(HashTableDeletedValue);
243     }
244     static bool isDeletedValue(const FontPlatformData& value)
245     {
246         return value.isHashTableDeletedValue();
247     }
248 };
249
250 typedef HashMap<FontPlatformData, pair<SimpleFontData*, unsigned>, FontDataCacheKeyHash, FontDataCacheKeyTraits> FontDataCache;
251
252 static FontDataCache* gFontDataCache = 0;
253
254 #if PLATFORM(CHROMIUM)
255 const int cMaxInactiveFontData = 250;
256 const int cTargetInactiveFontData = 200;
257 #else
258 const int cMaxInactiveFontData = 50; // Pretty Low Threshold
259 const int cTargetInactiveFontData = 30;
260 #endif
261 static ListHashSet<const SimpleFontData*>* gInactiveFontData = 0;
262
263 SimpleFontData* FontCache::getCachedFontData(const FontDescription& fontDescription, const AtomicString& family, bool checkingAlternateName, ShouldRetain shouldRetain)
264 {
265     FontPlatformData* platformData = getCachedFontPlatformData(fontDescription, family, checkingAlternateName);
266     if (!platformData)
267         return 0;
268
269     return getCachedFontData(platformData, shouldRetain);
270 }
271
272 SimpleFontData* FontCache::getCachedFontData(const FontPlatformData* platformData, ShouldRetain shouldRetain)
273 {
274     if (!platformData)
275         return 0;
276
277 #if !ASSERT_DISABLED
278     if (shouldRetain == DoNotRetain)
279         ASSERT(m_purgePreventCount);
280 #endif
281
282     if (!gFontDataCache) {
283         gFontDataCache = new FontDataCache;
284         gInactiveFontData = new ListHashSet<const SimpleFontData*>;
285     }
286
287     FontDataCache::iterator result = gFontDataCache->find(*platformData);
288     if (result == gFontDataCache->end()) {
289         pair<SimpleFontData*, unsigned> newValue(new SimpleFontData(*platformData), shouldRetain == Retain ? 1 : 0);
290         gFontDataCache->set(*platformData, newValue);
291         if (shouldRetain == DoNotRetain)
292             gInactiveFontData->add(newValue.first);
293         return newValue.first;
294     }
295
296     if (!result.get()->second.second) {
297         ASSERT(gInactiveFontData->contains(result.get()->second.first));
298         gInactiveFontData->remove(result.get()->second.first);
299     }
300
301     if (shouldRetain == Retain)
302         result.get()->second.second++;
303     else if (!result.get()->second.second) {
304         // If shouldRetain is DoNotRetain and count is 0, we want to remove the fontData from 
305         // gInactiveFontData (above) and re-add here to update LRU position.
306         gInactiveFontData->add(result.get()->second.first);
307     }
308
309     return result.get()->second.first;
310 }
311
312 void FontCache::releaseFontData(const SimpleFontData* fontData)
313 {
314     ASSERT(gFontDataCache);
315     ASSERT(!fontData->isCustomFont());
316
317     FontDataCache::iterator it = gFontDataCache->find(fontData->platformData());
318     ASSERT(it != gFontDataCache->end());
319
320     ASSERT(it->second.second);
321     if (!--it->second.second)
322         gInactiveFontData->add(fontData);
323 }
324
325 void FontCache::purgeInactiveFontDataIfNeeded()
326 {
327     if (gInactiveFontData && !m_purgePreventCount && gInactiveFontData->size() > cMaxInactiveFontData)
328         purgeInactiveFontData(gInactiveFontData->size() - cTargetInactiveFontData);
329 }
330
331 void FontCache::purgeInactiveFontData(int count)
332 {
333     if (!gInactiveFontData || m_purgePreventCount)
334         return;
335
336     static bool isPurging;  // Guard against reentry when e.g. a deleted FontData releases its small caps FontData.
337     if (isPurging)
338         return;
339
340     isPurging = true;
341
342     Vector<const SimpleFontData*, 20> fontDataToDelete;
343     ListHashSet<const SimpleFontData*>::iterator end = gInactiveFontData->end();
344     ListHashSet<const SimpleFontData*>::iterator it = gInactiveFontData->begin();
345     for (int i = 0; i < count && it != end; ++it, ++i) {
346         const SimpleFontData* fontData = *it.get();
347         gFontDataCache->remove(fontData->platformData());
348         // We should not delete SimpleFontData here because deletion can modify gInactiveFontData. See http://trac.webkit.org/changeset/44011
349         fontDataToDelete.append(fontData);
350     }
351
352     if (it == end) {
353         // Removed everything
354         gInactiveFontData->clear();
355     } else {
356         for (int i = 0; i < count; ++i)
357             gInactiveFontData->remove(gInactiveFontData->begin());
358     }
359
360     size_t fontDataToDeleteCount = fontDataToDelete.size();
361     for (size_t i = 0; i < fontDataToDeleteCount; ++i)
362         delete fontDataToDelete[i];
363
364     if (gFontPlatformDataCache) {
365         Vector<FontPlatformDataCacheKey> keysToRemove;
366         keysToRemove.reserveInitialCapacity(gFontPlatformDataCache->size());
367         FontPlatformDataCache::iterator platformDataEnd = gFontPlatformDataCache->end();
368         for (FontPlatformDataCache::iterator platformData = gFontPlatformDataCache->begin(); platformData != platformDataEnd; ++platformData) {
369             if (platformData->second && !gFontDataCache->contains(*platformData->second))
370                 keysToRemove.append(platformData->first);
371         }
372         
373         size_t keysToRemoveCount = keysToRemove.size();
374         for (size_t i = 0; i < keysToRemoveCount; ++i)
375             delete gFontPlatformDataCache->take(keysToRemove[i]);
376     }
377
378     isPurging = false;
379 }
380
381 size_t FontCache::fontDataCount()
382 {
383     if (gFontDataCache)
384         return gFontDataCache->size();
385     return 0;
386 }
387
388 size_t FontCache::inactiveFontDataCount()
389 {
390     if (gInactiveFontData)
391         return gInactiveFontData->size();
392     return 0;
393 }
394
395 const FontData* FontCache::getFontData(const Font& font, int& familyIndex, FontSelector* fontSelector)
396 {
397     SimpleFontData* result = 0;
398
399     int startIndex = familyIndex;
400     const FontFamily* startFamily = &font.fontDescription().family();
401     for (int i = 0; startFamily && i < startIndex; i++)
402         startFamily = startFamily->next();
403     const FontFamily* currFamily = startFamily;
404     while (currFamily && !result) {
405         familyIndex++;
406         if (currFamily->family().length()) {
407             if (fontSelector) {
408                 FontData* data = fontSelector->getFontData(font.fontDescription(), currFamily->family());
409                 if (data)
410                     return data;
411             }
412             result = getCachedFontData(font.fontDescription(), currFamily->family());
413         }
414         currFamily = currFamily->next();
415     }
416
417     if (!currFamily)
418         familyIndex = cAllFamiliesScanned;
419
420     if (!result)
421         // We didn't find a font. Try to find a similar font using our own specific knowledge about our platform.
422         // For example on OS X, we know to map any families containing the words Arabic, Pashto, or Urdu to the
423         // Geeza Pro font.
424         result = getSimilarFontPlatformData(font);
425
426     if (!result && startIndex == 0) {
427         // If it's the primary font that we couldn't find, we try the following. In all other cases, we will
428         // just use per-character system fallback.
429
430         if (fontSelector) {
431             // Try the user's preferred standard font.
432             if (FontData* data = fontSelector->getFontData(font.fontDescription(), "-webkit-standard"))
433                 return data;
434         }
435
436         // Still no result.  Hand back our last resort fallback font.
437         result = getLastResortFallbackFont(font.fontDescription());
438     }
439     return result;
440 }
441
442 static HashSet<FontSelector*>* gClients;
443
444 void FontCache::addClient(FontSelector* client)
445 {
446     if (!gClients)
447         gClients = new HashSet<FontSelector*>;
448
449     ASSERT(!gClients->contains(client));
450     gClients->add(client);
451 }
452
453 void FontCache::removeClient(FontSelector* client)
454 {
455     ASSERT(gClients);
456     ASSERT(gClients->contains(client));
457
458     gClients->remove(client);
459 }
460
461 static unsigned gGeneration = 0;
462
463 unsigned FontCache::generation()
464 {
465     return gGeneration;
466 }
467
468 void FontCache::invalidate()
469 {
470     if (!gClients) {
471         ASSERT(!gFontPlatformDataCache);
472         return;
473     }
474
475     if (gFontPlatformDataCache) {
476         deleteAllValues(*gFontPlatformDataCache);
477         delete gFontPlatformDataCache;
478         gFontPlatformDataCache = new FontPlatformDataCache;
479     }
480
481     gGeneration++;
482
483     Vector<RefPtr<FontSelector> > clients;
484     size_t numClients = gClients->size();
485     clients.reserveInitialCapacity(numClients);
486     HashSet<FontSelector*>::iterator end = gClients->end();
487     for (HashSet<FontSelector*>::iterator it = gClients->begin(); it != end; ++it)
488         clients.append(*it);
489
490     ASSERT(numClients == clients.size());
491     for (size_t i = 0; i < numClients; ++i)
492         clients[i]->fontCacheInvalidated();
493
494     purgeInactiveFontData();
495 }
496
497 } // namespace WebCore