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