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