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