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