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 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 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 84 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 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 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 119 GlyphPageTreeNode::~GlyphPageTreeNode() 120 { 121 deleteAllValues(m_children); 122 delete m_systemFallbackChild; 123 } 124 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 // all this casting is to ensure all the parameters to min and max have the same type, 206 // to avoid ambiguous template parameter errors on Windows 207 int from = max(0, static_cast<int>(range.from()) - static_cast<int>(start)); 208 int to = 1 + min(static_cast<int>(range.to()) - static_cast<int>(start), static_cast<int>(GlyphPage::size) - 1); 209 if (from < static_cast<int>(GlyphPage::size) && to > 0) { 210 if (haveGlyphs && !scratchPage) { 211 scratchPage = GlyphPage::create(this); 212 pageToFill = scratchPage.get(); 213 } 214 215 if (!zeroFilled) { 216 if (from > 0 || to < static_cast<int>(GlyphPage::size)) { 217 for (unsigned i = 0; i < GlyphPage::size; i++) 218 pageToFill->setGlyphDataForIndex(i, 0, 0); 219 } 220 zeroFilled = true; 221 } 222 haveGlyphs |= pageToFill->fill(from, to - from, buffer + from * (start < 0x10000 ? 1 : 2), (to - from) * (start < 0x10000 ? 1 : 2), range.fontData()); 223 if (scratchPage) { 224 ASSERT(to <= static_cast<int>(GlyphPage::size)); 225 for (int j = from; j < to; j++) { 226 if (!m_page->glyphAt(j) && pageToFill->glyphAt(j)) 227 m_page->setGlyphDataForIndex(j, pageToFill->glyphDataForIndex(j)); 228 } 229 } 230 } 231 } 232 } else 233 haveGlyphs = m_page->fill(0, GlyphPage::size, buffer, bufferLength, static_cast<const SimpleFontData*>(fontData)); 234 235 if (!haveGlyphs) 236 m_page = 0; 237 } else if (parentPage && parentPage->owner() != m_parent) { 238 // The page we're overriding may not be owned by our parent node. 239 // This happens when our parent node provides no useful overrides 240 // and just copies the pointer to an already-existing page (see 241 // below). 242 // 243 // We want our override to be shared by all nodes that reference 244 // that page to avoid duplication, and so standardize on having the 245 // page's owner collect all the overrides. Call getChild on the 246 // page owner with the desired font data (this will populate 247 // the page) and then reference it. 248 m_page = parentPage->owner()->getChild(fontData, pageNumber)->page(); 249 } else { 250 // Get the pure page for the fallback font (at level 1 with no 251 // overrides). getRootChild will always create a page if one 252 // doesn't exist, but the page doesn't necessarily have glyphs 253 // (this pointer may be 0). 254 GlyphPage* fallbackPage = getRootChild(fontData, pageNumber)->page(); 255 if (!parentPage) { 256 // When the parent has no glyphs for this page, we can easily 257 // override it just by supplying the glyphs from our font. 258 m_page = fallbackPage; 259 } else if (!fallbackPage) { 260 // When our font has no glyphs for this page, we can just reference the 261 // parent page. 262 m_page = parentPage; 263 } else { 264 // Combine the parent's glyphs and ours to form a new more complete page. 265 m_page = GlyphPage::create(this); 266 267 // Overlay the parent page on the fallback page. Check if the fallback font 268 // has added anything. 269 bool newGlyphs = false; 270 for (unsigned i = 0; i < GlyphPage::size; i++) { 271 if (parentPage->glyphAt(i)) 272 m_page->setGlyphDataForIndex(i, parentPage->glyphDataForIndex(i)); 273 else if (fallbackPage->glyphAt(i)) { 274 m_page->setGlyphDataForIndex(i, fallbackPage->glyphDataForIndex(i)); 275 newGlyphs = true; 276 } else 277 m_page->setGlyphDataForIndex(i, 0, 0); 278 } 279 280 if (!newGlyphs) 281 // We didn't override anything, so our override is just the parent page. 282 m_page = parentPage; 283 } 284 } 285 } else { 286 m_page = GlyphPage::create(this); 287 // System fallback. Initialized with the parent's page here, as individual 288 // entries may use different fonts depending on character. If the Font 289 // ever finds it needs a glyph out of the system fallback page, it will 290 // ask the system for the best font to use and fill that glyph in for us. 291 if (parentPage) 292 m_page->copyFrom(*parentPage); 293 else 294 m_page->clear(); 295 } 296 } 297 298 GlyphPageTreeNode* GlyphPageTreeNode::getChild(const FontData* fontData, unsigned pageNumber) 299 { 300 ASSERT(fontData || !m_isSystemFallback); 301 ASSERT(pageNumber == m_pageNumber); 302 303 GlyphPageTreeNode* child = fontData ? m_children.get(fontData) : m_systemFallbackChild; 304 if (!child) { 305 child = new GlyphPageTreeNode; 306 child->m_parent = this; 307 child->m_level = m_level + 1; 308 if (fontData && fontData->isCustomFont()) { 309 for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent) 310 curr->m_customFontCount++; 311 } 312 313 #ifndef NDEBUG 314 child->m_pageNumber = m_pageNumber; 315 #endif 316 if (fontData) { 317 m_children.set(fontData, child); 318 fontData->setMaxGlyphPageTreeLevel(max(fontData->maxGlyphPageTreeLevel(), child->m_level)); 319 } else { 320 m_systemFallbackChild = child; 321 child->m_isSystemFallback = true; 322 } 323 child->initializePage(fontData, pageNumber); 324 } 325 return child; 326 } 327 328 void GlyphPageTreeNode::pruneCustomFontData(const FontData* fontData) 329 { 330 if (!fontData || !m_customFontCount) 331 return; 332 333 // Prune any branch that contains this FontData. 334 GlyphPageTreeNode* node = m_children.get(fontData); 335 if (node) { 336 m_children.remove(fontData); 337 unsigned fontCount = node->m_customFontCount + 1; 338 delete node; 339 for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent) 340 curr->m_customFontCount -= fontCount; 341 } 342 343 // Check any branches that remain that still have custom fonts underneath them. 344 if (!m_customFontCount) 345 return; 346 HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end(); 347 for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it) 348 it->second->pruneCustomFontData(fontData); 349 } 350 351 void GlyphPageTreeNode::pruneFontData(const SimpleFontData* fontData, unsigned level) 352 { 353 ASSERT(fontData); 354 if (!fontData) 355 return; 356 357 // Prune any branch that contains this FontData. 358 HashMap<const FontData*, GlyphPageTreeNode*>::iterator child = m_children.find(fontData); 359 if (child == m_children.end()) { 360 // If there is no level-1 node for fontData, then there is no deeper node for it in this tree. 361 if (!level) 362 return; 363 } else { 364 GlyphPageTreeNode* node = child->second; 365 m_children.remove(fontData); 366 unsigned customFontCount = node->m_customFontCount; 367 delete node; 368 if (customFontCount) { 369 for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent) 370 curr->m_customFontCount -= customFontCount; 371 } 372 } 373 374 level++; 375 if (level > fontData->maxGlyphPageTreeLevel()) 376 return; 377 378 HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end(); 379 for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it) 380 it->second->pruneFontData(fontData, level); 381 } 382 383 #ifndef NDEBUG 384 void GlyphPageTreeNode::showSubtree() 385 { 386 Vector<char> indent(level()); 387 indent.fill('\t', level()); 388 indent.append(0); 389 390 HashMap<const FontData*, GlyphPageTreeNode*>::iterator end = m_children.end(); 391 for (HashMap<const FontData*, GlyphPageTreeNode*>::iterator it = m_children.begin(); it != end; ++it) { 392 printf("%s\t%p %s\n", indent.data(), it->first, it->first->description().utf8().data()); 393 it->second->showSubtree(); 394 } 395 if (m_systemFallbackChild) { 396 printf("%s\t* fallback\n", indent.data()); 397 m_systemFallbackChild->showSubtree(); 398 } 399 } 400 #endif 401 402 } 403 404 #ifndef NDEBUG 405 void showGlyphPageTrees() 406 { 407 printf("Page 0:\n"); 408 showGlyphPageTree(0); 409 HashMap<int, WebCore::GlyphPageTreeNode*>::iterator end = WebCore::GlyphPageTreeNode::roots->end(); 410 for (HashMap<int, WebCore::GlyphPageTreeNode*>::iterator it = WebCore::GlyphPageTreeNode::roots->begin(); it != end; ++it) { 411 printf("\nPage %d:\n", it->first); 412 showGlyphPageTree(it->first); 413 } 414 } 415 416 void showGlyphPageTree(unsigned pageNumber) 417 { 418 WebCore::GlyphPageTreeNode::getRoot(pageNumber)->showSubtree(); 419 } 420 #endif 421
