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 "core/platform/graphics/GlyphPageTreeNode.h" 31 32 #include <stdio.h> 33 #include "core/platform/graphics/SegmentedFontData.h" 34 #include "core/platform/graphics/SimpleFontData.h" 35 #include "core/platform/graphics/opentype/OpenTypeVerticalData.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 // Now that we have a buffer full of characters, we want to get back an array 205 // of glyph indices. This part involves calling into the platform-specific 206 // routine of our glyph map for actually filling in the page with the glyphs. 207 // Success is not guaranteed. For example, Times fails to fill page 260, giving glyph data 208 // for only 128 out of 256 characters. 209 bool haveGlyphs; 210 if (!fontData->isSegmented()) { 211 m_page = GlyphPage::createForSingleFontData(this, static_cast<const SimpleFontData*>(fontData)); 212 haveGlyphs = fill(m_page.get(), 0, GlyphPage::size, buffer, bufferLength, static_cast<const SimpleFontData*>(fontData)); 213 } else { 214 m_page = GlyphPage::createForMixedFontData(this); 215 haveGlyphs = false; 216 217 const SegmentedFontData* segmentedFontData = static_cast<const SegmentedFontData*>(fontData); 218 unsigned numRanges = segmentedFontData->numRanges(); 219 bool zeroFilled = false; 220 RefPtr<GlyphPage> scratchPage; 221 GlyphPage* pageToFill = m_page.get(); 222 for (unsigned i = 0; i < numRanges; i++) { 223 const FontDataRange& range = segmentedFontData->rangeAt(i); 224 // all this casting is to ensure all the parameters to min and max have the same type, 225 // to avoid ambiguous template parameter errors on Windows 226 int from = max(0, static_cast<int>(range.from()) - static_cast<int>(start)); 227 int to = 1 + min(static_cast<int>(range.to()) - static_cast<int>(start), static_cast<int>(GlyphPage::size) - 1); 228 if (from < static_cast<int>(GlyphPage::size) && to > 0) { 229 if (haveGlyphs && !scratchPage) { 230 scratchPage = GlyphPage::createForMixedFontData(this); 231 pageToFill = scratchPage.get(); 232 } 233 234 if (!zeroFilled) { 235 if (from > 0 || to < static_cast<int>(GlyphPage::size)) { 236 for (unsigned i = 0; i < GlyphPage::size; i++) 237 pageToFill->setGlyphDataForIndex(i, 0, 0); 238 } 239 zeroFilled = true; 240 } 241 haveGlyphs |= fill(pageToFill, from, to - from, buffer + from * (start < 0x10000 ? 1 : 2), (to - from) * (start < 0x10000 ? 1 : 2), range.fontData().get()); 242 if (scratchPage) { 243 ASSERT_WITH_SECURITY_IMPLICATION(to <= static_cast<int>(GlyphPage::size)); 244 for (int j = from; j < to; j++) { 245 if (!m_page->glyphAt(j) && pageToFill->glyphAt(j)) 246 m_page->setGlyphDataForIndex(j, pageToFill->glyphDataForIndex(j)); 247 } 248 } 249 } 250 } 251 } 252 253 if (!haveGlyphs) 254 m_page = 0; 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 } else 295 m_page->setGlyphDataForIndex(i, 0, 0); 296 } 297 298 if (!newGlyphs) 299 // We didn't override anything, so our override is just the parent page. 300 m_page = parentPage; 301 } 302 } 303 } else { 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 = parentPage->createCopiedSystemFallbackPage(this); 310 else 311 m_page = GlyphPage::createForMixedFontData(this); 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->removeFontDataFromSystemFallbackPage(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 430
