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