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