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