Reviewed by Anders Carlsson.
[WebKit-https.git] / WebCore / platform / graphics / GlyphPageTreeNode.cpp
1 /*
2  * Copyright (C) 2006, 2007 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer. 
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution. 
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission. 
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30 #include "GlyphPageTreeNode.h"
31
32 #include "CharacterNames.h"
33 #include "FontData.h"
34 #include <wtf/unicode/Unicode.h>
35
36 namespace WebCore {
37
38 HashMap<int, GlyphPageTreeNode*>* GlyphPageTreeNode::roots = 0;
39 GlyphPageTreeNode* GlyphPageTreeNode::pageZeroRoot = 0;
40
41 GlyphPageTreeNode* GlyphPageTreeNode::getRoot(unsigned pageNumber)
42 {
43     static bool initialized;
44     if (!initialized) {
45         initialized = true;
46         roots = new HashMap<int, GlyphPageTreeNode*>;
47         pageZeroRoot = new GlyphPageTreeNode;
48     }
49
50     GlyphPageTreeNode* node = pageNumber ? roots->get(pageNumber) : pageZeroRoot;
51     if (!node) {
52         node = new GlyphPageTreeNode;
53 #ifndef NDEBUG
54         node->m_pageNumber = pageNumber;
55 #endif
56         if (pageNumber)
57             roots->set(pageNumber, node);
58         else
59             pageZeroRoot = node;
60     }
61     return node;
62 }
63
64 void GlyphPageTreeNode::pruneTreeCustomFontData(const FontData* fontData)
65 {
66     // Enumerate all the roots and prune any tree that contains our custom font data.
67     if (roots) {
68         HashMap<int, GlyphPageTreeNode*>::iterator end = roots->end();
69         for (HashMap<int, GlyphPageTreeNode*>::iterator it = roots->begin(); it != end; ++it)
70             it->second->pruneCustomFontData(fontData);
71     }
72     
73     if (pageZeroRoot)
74         pageZeroRoot->pruneCustomFontData(fontData);
75 }
76
77 GlyphPageTreeNode::~GlyphPageTreeNode()
78 {
79     deleteAllValues(m_children);
80     delete m_systemFallbackChild;
81 }
82
83 void GlyphPageTreeNode::initializePage(const FontData* fontData, unsigned pageNumber)
84 {
85     ASSERT(!m_page);
86
87     // This function must not be called for the root of the tree, because that
88     // level does not contain any glyphs.
89     ASSERT(m_level > 0 && m_parent);
90
91     // The parent's page will be 0 if we are level one or the parent's font data
92     // did not contain any glyphs for that page.
93     GlyphPage* parentPage = m_parent->page();
94
95     // NULL FontData means we're being asked for the system fallback font.
96     if (fontData) {
97         if (m_level == 1) {
98             // Children of the root hold pure pages. These will cover only one
99             // font data's glyphs, and will have glyph index 0 if the font data does not
100             // contain the glyph.
101             unsigned start = pageNumber * GlyphPage::size;
102             UChar buffer[GlyphPage::size * 2 + 2];
103             unsigned bufferLength;
104             unsigned i;
105
106             // Fill in a buffer with the entire "page" of characters that we want to look up glyphs for.
107             if (start < 0x10000) {
108                 bufferLength = GlyphPage::size;
109                 for (i = 0; i < GlyphPage::size; i++)
110                     buffer[i] = start + i;
111
112                 if (start == 0) {
113                     // Control characters must not render at all.
114                     for (i = 0; i < 0x20; ++i)
115                         buffer[i] = zeroWidthSpace;
116                     for (i = 0x7F; i < 0xA0; i++)
117                         buffer[i] = zeroWidthSpace;
118
119                     // \n, \t, and nonbreaking space must render as a space.
120                     buffer[(int)'\n'] = ' ';
121                     buffer[(int)'\t'] = ' ';
122                     buffer[noBreakSpace] = ' ';
123                 } else if (start == (leftToRightMark & ~(GlyphPage::size - 1))) {
124                     // LRM, RLM, LRE, RLE and PDF must not render at all.
125                     buffer[leftToRightMark - start] = zeroWidthSpace;
126                     buffer[rightToLeftMark - start] = zeroWidthSpace;
127                     buffer[leftToRightEmbed - start] = zeroWidthSpace;
128                     buffer[rightToLeftEmbed - start] = zeroWidthSpace;
129                     buffer[leftToRightOverride - start] = zeroWidthSpace;
130                     buffer[rightToLeftOverride - start] = zeroWidthSpace;
131                     buffer[popDirectionalFormatting - start] = zeroWidthSpace;
132                 } else if (start == (objectReplacementCharacter & ~(GlyphPage::size - 1))) {
133                     // Object replacement character must not render at all.
134                     buffer[objectReplacementCharacter - start] = zeroWidthSpace;
135                 }
136             } else {
137                 bufferLength = GlyphPage::size * 2;
138                 for (i = 0; i < GlyphPage::size; i++) {
139                     int c = i + start;
140                     buffer[i * 2] = U16_LEAD(c);
141                     buffer[i * 2 + 1] = U16_TRAIL(c);
142                 }
143             }
144             
145             m_page = new GlyphPage(this);
146
147             // Now that we have a buffer full of characters, we want to get back an array
148             // of glyph indices.  This part involves calling into the platform-specific 
149             // routine of our glyph map for actually filling in the page with the glyphs.
150             // Success is not guaranteed. For example, Times fails to fill page 260, giving glyph data
151             // for only 128 out of 256 characters.
152             bool haveGlyphs = m_page->fill(buffer, bufferLength, fontData);
153
154             if (!haveGlyphs)
155                 m_page = 0;
156         } else if (parentPage && parentPage->owner() != m_parent) {
157             // The page we're overriding may not be owned by our parent node.
158             // This happens when our parent node provides no useful overrides
159             // and just copies the pointer to an already-existing page (see
160             // below).
161             //
162             // We want our override to be shared by all nodes that reference
163             // that page to avoid duplication, and so standardize on having the
164             // page's owner collect all the overrides.  Call getChild on the
165             // page owner with the desired font data (this will populate
166             // the page) and then reference it.
167             m_page = parentPage->owner()->getChild(fontData, pageNumber)->page();
168         } else {
169             // Get the pure page for the fallback font (at level 1 with no
170             // overrides). getRootChild will always create a page if one
171             // doesn't exist, but the page doesn't necessarily have glyphs
172             // (this pointer may be 0).
173             GlyphPage* fallbackPage = getRootChild(fontData, pageNumber)->page();
174             if (!parentPage) {
175                 // When the parent has no glyphs for this page, we can easily
176                 // override it just by supplying the glyphs from our font.
177                 m_page = fallbackPage;
178             } else if (!fallbackPage) {
179                 // When our font has no glyphs for this page, we can just reference the
180                 // parent page.
181                 m_page = parentPage;
182             } else {
183                 // Combine the parent's glyphs and ours to form a new more complete page.
184                 m_page = new GlyphPage(this);
185
186                 // Overlay the parent page on the fallback page. Check if the fallback font
187                 // has added anything.
188                 bool newGlyphs = false;
189                 for (unsigned i = 0; i < GlyphPage::size; i++) {
190                     if (parentPage->m_glyphs[i].glyph)
191                         m_page->m_glyphs[i] = parentPage->m_glyphs[i];
192                     else  if (fallbackPage->m_glyphs[i].glyph) {
193                         m_page->m_glyphs[i] = fallbackPage->m_glyphs[i];
194                         newGlyphs = true;
195                     } else {
196                         const GlyphData data = { 0, 0 };
197                         m_page->m_glyphs[i] = data;
198                     }
199                 }
200
201                 if (!newGlyphs)
202                     // We didn't override anything, so our override is just the parent page.
203                     m_page = parentPage;
204             }
205         }
206     } else {
207         m_page = new GlyphPage(this);
208         // System fallback. Initialized with the parent's page here, as individual
209         // entries may use different fonts depending on character. If the Font
210         // ever finds it needs a glyph out of the system fallback page, it will
211         // ask the system for the best font to use and fill that glyph in for us.
212         if (parentPage)
213             memcpy(m_page->m_glyphs, parentPage->m_glyphs, GlyphPage::size * sizeof(m_page->m_glyphs[0]));
214         else {
215             const GlyphData data = { 0, 0 };
216             for (unsigned i = 0; i < GlyphPage::size; i++)
217                 m_page->m_glyphs[i] = data;
218         }
219     }
220 }
221
222 GlyphPageTreeNode* GlyphPageTreeNode::getChild(const FontData* fontData, unsigned pageNumber)
223 {
224     ASSERT(fontData || !m_isSystemFallback);
225     ASSERT(pageNumber == m_pageNumber);
226
227     GlyphPageTreeNode* child = fontData ? m_children.get(fontData) : m_systemFallbackChild;
228     if (!child) {
229         child = new GlyphPageTreeNode;
230         child->m_parent = this;
231         child->m_level = m_level + 1;
232         if (fontData && fontData->isCustomFont()) {
233             for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
234                 curr->m_customFontCount++;
235         }
236
237 #ifndef NDEBUG
238         child->m_pageNumber = m_pageNumber;
239 #endif
240         if (fontData)
241             m_children.set(fontData, child);
242         else {
243             m_systemFallbackChild = child;
244             child->m_isSystemFallback = true;
245         }
246         child->initializePage(fontData, pageNumber);
247     }
248     return child;
249 }
250
251 void GlyphPageTreeNode::pruneCustomFontData(const FontData* fontData)
252 {
253     if (!fontData || !m_customFontCount)
254         return;
255         
256     // Prune any branch that contains this FontData.
257     GlyphPageTreeNode* node = m_children.get(fontData);
258     if (node) {
259         m_children.remove(fontData);
260         unsigned fontCount = node->m_customFontCount + 1;
261         delete node;
262         for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
263             curr->m_customFontCount -= fontCount;
264     }
265     
266     // Check any branches that remain that still have custom fonts underneath them.
267     if (!m_customFontCount)
268         return;
269     HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end();
270     for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it)
271         it->second->pruneCustomFontData(fontData);
272 }
273
274 }