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