2010-04-21 David Yonge-Mallo <davinci@chromium.org>
[WebKit-https.git] / WebCore / platform / graphics / GlyphPageTreeNode.cpp
1 /*
2  * Copyright (C) 2006, 2007, 2008 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 "PlatformString.h"
34 #include "SegmentedFontData.h"
35 #include "SimpleFontData.h"
36 #include <stdio.h>
37 #include <wtf/text/CString.h>
38 #include <wtf/unicode/Unicode.h>
39
40 namespace WebCore {
41
42 using std::max;
43 using std::min;
44
45 HashMap<int, GlyphPageTreeNode*>* GlyphPageTreeNode::roots = 0;
46 GlyphPageTreeNode* GlyphPageTreeNode::pageZeroRoot = 0;
47
48 GlyphPageTreeNode* GlyphPageTreeNode::getRoot(unsigned pageNumber)
49 {
50     static bool initialized;
51     if (!initialized) {
52         initialized = true;
53         roots = new HashMap<int, GlyphPageTreeNode*>;
54         pageZeroRoot = new GlyphPageTreeNode;
55     }
56
57     GlyphPageTreeNode* node = pageNumber ? roots->get(pageNumber) : pageZeroRoot;
58     if (!node) {
59         node = new GlyphPageTreeNode;
60 #ifndef NDEBUG
61         node->m_pageNumber = pageNumber;
62 #endif
63         if (pageNumber)
64             roots->set(pageNumber, node);
65         else
66             pageZeroRoot = node;
67     }
68     return node;
69 }
70
71 size_t GlyphPageTreeNode::treeGlyphPageCount()
72 {
73     size_t count = 0;
74     if (roots) {
75         HashMap<int, GlyphPageTreeNode*>::iterator end = roots->end();
76         for (HashMap<int, GlyphPageTreeNode*>::iterator it = roots->begin(); it != end; ++it)
77             count += it->second->pageCount();
78     }
79     
80     if (pageZeroRoot)
81         count += pageZeroRoot->pageCount();
82
83     return count;
84 }
85
86 size_t GlyphPageTreeNode::pageCount() const
87 {
88     size_t count = m_page && m_page->owner() == this ? 1 : 0;
89     HashMap<const FontData*, GlyphPageTreeNode*>::const_iterator end = m_children.end();
90     for (HashMap<const FontData*, GlyphPageTreeNode*>::const_iterator it = m_children.begin(); it != end; ++it)
91         count += it->second->pageCount();
92
93     return count;
94 }
95
96 void GlyphPageTreeNode::pruneTreeCustomFontData(const FontData* fontData)
97 {
98     // Enumerate all the roots and prune any tree that contains our custom font data.
99     if (roots) {
100         HashMap<int, GlyphPageTreeNode*>::iterator end = roots->end();
101         for (HashMap<int, GlyphPageTreeNode*>::iterator it = roots->begin(); it != end; ++it)
102             it->second->pruneCustomFontData(fontData);
103     }
104     
105     if (pageZeroRoot)
106         pageZeroRoot->pruneCustomFontData(fontData);
107 }
108
109 void GlyphPageTreeNode::pruneTreeFontData(const SimpleFontData* fontData)
110 {
111     if (roots) {
112         HashMap<int, GlyphPageTreeNode*>::iterator end = roots->end();
113         for (HashMap<int, GlyphPageTreeNode*>::iterator it = roots->begin(); it != end; ++it)
114             it->second->pruneFontData(fontData);
115     }
116     
117     if (pageZeroRoot)
118         pageZeroRoot->pruneFontData(fontData);
119 }
120
121 GlyphPageTreeNode::~GlyphPageTreeNode()
122 {
123     deleteAllValues(m_children);
124     delete m_systemFallbackChild;
125 }
126
127 void GlyphPageTreeNode::initializePage(const FontData* fontData, unsigned pageNumber)
128 {
129     ASSERT(!m_page);
130
131     // This function must not be called for the root of the tree, because that
132     // level does not contain any glyphs.
133     ASSERT(m_level > 0 && m_parent);
134
135     // The parent's page will be 0 if we are level one or the parent's font data
136     // did not contain any glyphs for that page.
137     GlyphPage* parentPage = m_parent->page();
138
139     // NULL FontData means we're being asked for the system fallback font.
140     if (fontData) {
141         if (m_level == 1) {
142             // Children of the root hold pure pages. These will cover only one
143             // font data's glyphs, and will have glyph index 0 if the font data does not
144             // contain the glyph.
145             unsigned start = pageNumber * GlyphPage::size;
146             UChar buffer[GlyphPage::size * 2 + 2];
147             unsigned bufferLength;
148             unsigned i;
149
150             // Fill in a buffer with the entire "page" of characters that we want to look up glyphs for.
151             if (start < 0x10000) {
152                 bufferLength = GlyphPage::size;
153                 for (i = 0; i < GlyphPage::size; i++)
154                     buffer[i] = start + i;
155
156                 if (start == 0) {
157                     // Control characters must not render at all.
158                     for (i = 0; i < 0x20; ++i)
159                         buffer[i] = zeroWidthSpace;
160                     for (i = 0x7F; i < 0xA0; i++)
161                         buffer[i] = zeroWidthSpace;
162
163                     // \n, \t, and nonbreaking space must render as a space.
164                     buffer[(int)'\n'] = ' ';
165                     buffer[(int)'\t'] = ' ';
166                     buffer[noBreakSpace] = ' ';
167                 } else if (start == (leftToRightMark & ~(GlyphPage::size - 1))) {
168                     // LRM, RLM, LRE, RLE, ZWNJ, ZWJ, and PDF must not render at all.
169                     buffer[leftToRightMark - start] = zeroWidthSpace;
170                     buffer[rightToLeftMark - start] = zeroWidthSpace;
171                     buffer[leftToRightEmbed - start] = zeroWidthSpace;
172                     buffer[rightToLeftEmbed - start] = zeroWidthSpace;
173                     buffer[leftToRightOverride - start] = zeroWidthSpace;
174                     buffer[rightToLeftOverride - start] = zeroWidthSpace;
175                     buffer[zeroWidthNonJoiner - start] = zeroWidthSpace;
176                     buffer[zeroWidthJoiner - start] = zeroWidthSpace;
177                     buffer[popDirectionalFormatting - start] = zeroWidthSpace;
178                 } else if (start == (objectReplacementCharacter & ~(GlyphPage::size - 1))) {
179                     // Object replacement character must not render at all.
180                     buffer[objectReplacementCharacter - start] = zeroWidthSpace;
181                 }
182             } else {
183                 bufferLength = GlyphPage::size * 2;
184                 for (i = 0; i < GlyphPage::size; i++) {
185                     int c = i + start;
186                     buffer[i * 2] = U16_LEAD(c);
187                     buffer[i * 2 + 1] = U16_TRAIL(c);
188                 }
189             }
190             
191             m_page = GlyphPage::create(this);
192
193             // Now that we have a buffer full of characters, we want to get back an array
194             // of glyph indices.  This part involves calling into the platform-specific 
195             // routine of our glyph map for actually filling in the page with the glyphs.
196             // Success is not guaranteed. For example, Times fails to fill page 260, giving glyph data
197             // for only 128 out of 256 characters.
198             bool haveGlyphs;
199             if (fontData->isSegmented()) {
200                 haveGlyphs = false;
201
202                 const SegmentedFontData* segmentedFontData = static_cast<const SegmentedFontData*>(fontData);
203                 unsigned numRanges = segmentedFontData->numRanges();
204                 bool zeroFilled = false;
205                 RefPtr<GlyphPage> scratchPage;
206                 GlyphPage* pageToFill = m_page.get();
207                 for (unsigned i = 0; i < numRanges; i++) {
208                     const FontDataRange& range = segmentedFontData->rangeAt(i);
209                     // all this casting is to ensure all the parameters to min and max have the same type,
210                     // to avoid ambiguous template parameter errors on Windows
211                     int from = max(0, static_cast<int>(range.from()) - static_cast<int>(start));
212                     int to = 1 + min(static_cast<int>(range.to()) - static_cast<int>(start), static_cast<int>(GlyphPage::size) - 1);
213                     if (from < static_cast<int>(GlyphPage::size) && to > 0) {
214                         if (haveGlyphs && !scratchPage) {
215                             scratchPage = GlyphPage::create(this);
216                             pageToFill = scratchPage.get();
217                         }
218
219                         if (!zeroFilled) {
220                             if (from > 0 || to < static_cast<int>(GlyphPage::size)) {
221                                 for (unsigned i = 0; i < GlyphPage::size; i++)
222                                     pageToFill->setGlyphDataForIndex(i, 0, 0);
223                             }
224                             zeroFilled = true;
225                         }
226                         haveGlyphs |= pageToFill->fill(from, to - from, buffer + from * (start < 0x10000 ? 1 : 2), (to - from) * (start < 0x10000 ? 1 : 2), range.fontData());
227                         if (scratchPage) {
228                             ASSERT(to <=  static_cast<int>(GlyphPage::size));
229                             for (int j = from; j < to; j++) {
230                                 if (!m_page->glyphAt(j) && pageToFill->glyphAt(j))
231                                     m_page->setGlyphDataForIndex(j, pageToFill->glyphDataForIndex(j));
232                             }
233                         }
234                     }
235                 }
236             } else
237                 haveGlyphs = m_page->fill(0, GlyphPage::size, buffer, bufferLength, static_cast<const SimpleFontData*>(fontData));
238
239             if (!haveGlyphs)
240                 m_page = 0;
241         } else if (parentPage && parentPage->owner() != m_parent) {
242             // The page we're overriding may not be owned by our parent node.
243             // This happens when our parent node provides no useful overrides
244             // and just copies the pointer to an already-existing page (see
245             // below).
246             //
247             // We want our override to be shared by all nodes that reference
248             // that page to avoid duplication, and so standardize on having the
249             // page's owner collect all the overrides.  Call getChild on the
250             // page owner with the desired font data (this will populate
251             // the page) and then reference it.
252             m_page = parentPage->owner()->getChild(fontData, pageNumber)->page();
253         } else {
254             // Get the pure page for the fallback font (at level 1 with no
255             // overrides). getRootChild will always create a page if one
256             // doesn't exist, but the page doesn't necessarily have glyphs
257             // (this pointer may be 0).
258             GlyphPage* fallbackPage = getRootChild(fontData, pageNumber)->page();
259             if (!parentPage) {
260                 // When the parent has no glyphs for this page, we can easily
261                 // override it just by supplying the glyphs from our font.
262                 m_page = fallbackPage;
263             } else if (!fallbackPage) {
264                 // When our font has no glyphs for this page, we can just reference the
265                 // parent page.
266                 m_page = parentPage;
267             } else {
268                 // Combine the parent's glyphs and ours to form a new more complete page.
269                 m_page = GlyphPage::create(this);
270
271                 // Overlay the parent page on the fallback page. Check if the fallback font
272                 // has added anything.
273                 bool newGlyphs = false;
274                 for (unsigned i = 0; i < GlyphPage::size; i++) {
275                     if (parentPage->glyphAt(i))
276                         m_page->setGlyphDataForIndex(i, parentPage->glyphDataForIndex(i));
277                     else  if (fallbackPage->glyphAt(i)) {
278                         m_page->setGlyphDataForIndex(i, fallbackPage->glyphDataForIndex(i));
279                         newGlyphs = true;
280                     } else
281                         m_page->setGlyphDataForIndex(i, 0, 0);
282                 }
283
284                 if (!newGlyphs)
285                     // We didn't override anything, so our override is just the parent page.
286                     m_page = parentPage;
287             }
288         }
289     } else {
290         m_page = GlyphPage::create(this);
291         // System fallback. Initialized with the parent's page here, as individual
292         // entries may use different fonts depending on character. If the Font
293         // ever finds it needs a glyph out of the system fallback page, it will
294         // ask the system for the best font to use and fill that glyph in for us.
295         if (parentPage)
296             m_page->copyFrom(*parentPage);
297         else
298             m_page->clear();
299     }
300 }
301
302 GlyphPageTreeNode* GlyphPageTreeNode::getChild(const FontData* fontData, unsigned pageNumber)
303 {
304     ASSERT(fontData || !m_isSystemFallback);
305     ASSERT(pageNumber == m_pageNumber);
306
307     GlyphPageTreeNode* child = fontData ? m_children.get(fontData) : m_systemFallbackChild;
308     if (!child) {
309         child = new GlyphPageTreeNode;
310         child->m_parent = this;
311         child->m_level = m_level + 1;
312         if (fontData && fontData->isCustomFont()) {
313             for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
314                 curr->m_customFontCount++;
315         }
316
317 #ifndef NDEBUG
318         child->m_pageNumber = m_pageNumber;
319 #endif
320         if (fontData) {
321             m_children.set(fontData, child);
322             fontData->setMaxGlyphPageTreeLevel(max(fontData->maxGlyphPageTreeLevel(), child->m_level));
323         } else {
324             m_systemFallbackChild = child;
325             child->m_isSystemFallback = true;
326         }
327         child->initializePage(fontData, pageNumber);
328     }
329     return child;
330 }
331
332 void GlyphPageTreeNode::pruneCustomFontData(const FontData* fontData)
333 {
334     if (!fontData || !m_customFontCount)
335         return;
336         
337     // Prune any branch that contains this FontData.
338     GlyphPageTreeNode* node = m_children.get(fontData);
339     if (node) {
340         m_children.remove(fontData);
341         unsigned fontCount = node->m_customFontCount + 1;
342         delete node;
343         for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
344             curr->m_customFontCount -= fontCount;
345     }
346     
347     // Check any branches that remain that still have custom fonts underneath them.
348     if (!m_customFontCount)
349         return;
350     HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end();
351     for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it)
352         it->second->pruneCustomFontData(fontData);
353 }
354
355 void GlyphPageTreeNode::pruneFontData(const SimpleFontData* fontData, unsigned level)
356 {
357     ASSERT(fontData);
358     if (!fontData)
359         return;
360
361     // Prune any branch that contains this FontData.
362     HashMap<const FontData*, GlyphPageTreeNode*>::iterator child = m_children.find(fontData);
363     if (child == m_children.end()) {
364         // If there is no level-1 node for fontData, then there is no deeper node for it in this tree.
365         if (!level)
366             return;
367     } else {
368         GlyphPageTreeNode* node = child->second;
369         m_children.remove(fontData);
370         unsigned customFontCount = node->m_customFontCount;
371         delete node;
372         if (customFontCount) {
373             for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
374                 curr->m_customFontCount -= customFontCount;
375         }
376     }
377
378     level++;
379     if (level > fontData->maxGlyphPageTreeLevel())
380         return;
381
382     HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end();
383     for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it)
384         it->second->pruneFontData(fontData, level);
385 }
386
387 #ifndef NDEBUG
388     void GlyphPageTreeNode::showSubtree()
389     {
390         Vector<char> indent(level());
391         indent.fill('\t', level());
392         indent.append(0);
393
394         HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end();
395         for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it) {
396             printf("%s\t%p %s\n", indent.data(), it->first, it->first->description().utf8().data());
397             it->second->showSubtree();
398         }
399         if (m_systemFallbackChild) {
400             printf("%s\t* fallback\n", indent.data());
401             m_systemFallbackChild->showSubtree();
402         }
403     }
404 #endif
405
406 }
407
408 #ifndef NDEBUG
409 void showGlyphPageTrees()
410 {
411     printf("Page 0:\n");
412     showGlyphPageTree(0);
413     HashMap<int, WebCore::GlyphPageTreeNode*>::iterator end = WebCore::GlyphPageTreeNode::roots->end();
414     for (HashMap<int, WebCore::GlyphPageTreeNode*>::iterator it = WebCore::GlyphPageTreeNode::roots->begin(); it != end; ++it) {
415         printf("\nPage %d:\n", it->first);
416         showGlyphPageTree(it->first);
417     }
418 }
419
420 void showGlyphPageTree(unsigned pageNumber)
421 {
422     WebCore::GlyphPageTreeNode::getRoot(pageNumber)->showSubtree();
423 }
424 #endif