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 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 if (!pageNumber) 58 return pageZeroRoot; 59 60 if (GlyphPageTreeNode* foundNode = roots->get(pageNumber)) 61 return foundNode; 62 63 GlyphPageTreeNode* node = new GlyphPageTreeNode; 64 #ifndef NDEBUG 65 node->m_pageNumber = pageNumber; 66 #endif 67 roots->set(pageNumber, node); 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->value->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 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 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 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 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 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[(int)'\n'] = ' '; 174 buffer[(int)'\t'] = ' '; 175 buffer[noBreakSpace] = ' '; 176 } else if (start == (leftToRightMark & ~(GlyphPage::size - 1))) { 177 // LRM, RLM, LRE, RLE, ZWNJ, ZWJ, and PDF must not render at all. 178 buffer[leftToRightMark - start] = zeroWidthSpace; 179 buffer[rightToLeftMark - start] = zeroWidthSpace; 180 buffer[leftToRightEmbed - start] = zeroWidthSpace; 181 buffer[rightToLeftEmbed - start] = zeroWidthSpace; 182 buffer[leftToRightOverride - start] = zeroWidthSpace; 183 buffer[rightToLeftOverride - start] = zeroWidthSpace; 184 buffer[zeroWidthNonJoiner - start] = zeroWidthSpace; 185 buffer[zeroWidthJoiner - start] = zeroWidthSpace; 186 buffer[popDirectionalFormatting - start] = zeroWidthSpace; 187 } else if (start == (objectReplacementCharacter & ~(GlyphPage::size - 1))) { 188 // Object replacement character must not render at all. 189 buffer[objectReplacementCharacter - start] = zeroWidthSpace; 190 } else if (start == (zeroWidthNoBreakSpace & ~(GlyphPage::size - 1))) { 191 // ZWNBS/BOM must not render at all. 192 buffer[zeroWidthNoBreakSpace - start] = zeroWidthSpace; 193 } 194 } else { 195 bufferLength = GlyphPage::size * 2; 196 for (i = 0; i < GlyphPage::size; i++) { 197 int c = i + start; 198 buffer[i * 2] = U16_LEAD(c); 199 buffer[i * 2 + 1] = U16_TRAIL(c); 200 } 201 } 202 203 // Now that we have a buffer full of characters, we want to get back an array 204 // of glyph indices. This part involves calling into the platform-specific 205 // routine of our glyph map for actually filling in the page with the glyphs. 206 // Success is not guaranteed. For example, Times fails to fill page 260, giving glyph data 207 // for only 128 out of 256 characters. 208 bool haveGlyphs; 209 if (!fontData->isSegmented()) { 210 m_page = GlyphPage::createForSingleFontData(this, static_cast<const SimpleFontData*>(fontData)); 211 haveGlyphs = fill(m_page.get(), 0, GlyphPage::size, buffer, bufferLength, static_cast<const SimpleFontData*>(fontData)); 212 } else { 213 m_page = GlyphPage::createForMixedFontData(this); 214 haveGlyphs = false; 215 216 const SegmentedFontData* segmentedFontData = static_cast<const SegmentedFontData*>(fontData); 217 for (int i = segmentedFontData->numRanges() - 1; i >= 0; i--) { 218 const FontDataRange& range = segmentedFontData->rangeAt(i); 219 // all this casting is to ensure all the parameters to min and max have the same type, 220 // to avoid ambiguous template parameter errors on Windows 221 int from = max(0, static_cast<int>(range.from()) - static_cast<int>(start)); 222 int to = 1 + min(static_cast<int>(range.to()) - static_cast<int>(start), static_cast<int>(GlyphPage::size) - 1); 223 if (from >= static_cast<int>(GlyphPage::size) || to <= 0) 224 continue; 225 226 // If this is a custom font needs to be loaded, do not fill 227 // the page so that font fallback is used while loading. 228 RefPtr<CustomFontData> customData = range.fontData()->customFontData(); 229 if (customData && customData->isLoadingFallback()) { 230 for (int j = from; j < to; j++) { 231 m_page->setCustomFontToLoad(j, customData.get()); 232 haveGlyphs = true; 233 } 234 continue; 235 } 236 237 haveGlyphs |= fill(m_page.get(), from, to - from, buffer + from * (start < 0x10000 ? 1 : 2), (to - from) * (start < 0x10000 ? 1 : 2), range.fontData().get()); 238 } 239 } 240 241 if (!haveGlyphs) 242 m_page = nullptr; 243 } else if (parentPage && parentPage->owner() != m_parent) { 244 // The page we're overriding may not be owned by our parent node. 245 // This happens when our parent node provides no useful overrides 246 // and just copies the pointer to an already-existing page (see 247 // below). 248 // 249 // We want our override to be shared by all nodes that reference 250 // that page to avoid duplication, and so standardize on having the 251 // page's owner collect all the overrides. Call getChild on the 252 // page owner with the desired font data (this will populate 253 // the page) and then reference it. 254 m_page = parentPage->owner()->getChild(fontData, pageNumber)->page(); 255 } else { 256 // Get the pure page for the fallback font (at level 1 with no 257 // overrides). getRootChild will always create a page if one 258 // doesn't exist, but the page doesn't necessarily have glyphs 259 // (this pointer may be 0). 260 GlyphPage* fallbackPage = getRootChild(fontData, pageNumber)->page(); 261 if (!parentPage) { 262 // When the parent has no glyphs for this page, we can easily 263 // override it just by supplying the glyphs from our font. 264 m_page = fallbackPage; 265 } else if (!fallbackPage) { 266 // When our font has no glyphs for this page, we can just reference the 267 // parent page. 268 m_page = parentPage; 269 } else { 270 // Combine the parent's glyphs and ours to form a new more complete page. 271 m_page = GlyphPage::createForMixedFontData(this); 272 273 // Overlay the parent page on the fallback page. Check if the fallback font 274 // has added anything. 275 bool newGlyphs = false; 276 for (unsigned i = 0; i < GlyphPage::size; i++) { 277 if (parentPage->glyphAt(i)) { 278 m_page->setGlyphDataForIndex(i, parentPage->glyphDataForIndex(i)); 279 } else if (fallbackPage->glyphAt(i)) { 280 m_page->setGlyphDataForIndex(i, fallbackPage->glyphDataForIndex(i)); 281 newGlyphs = true; 282 } 283 284 if (parentPage->customFontToLoadAt(i)) { 285 m_page->setCustomFontToLoad(i, parentPage->customFontToLoadAt(i)); 286 } else if (fallbackPage->customFontToLoadAt(i) && !parentPage->glyphAt(i)) { 287 m_page->setCustomFontToLoad(i, fallbackPage->customFontToLoadAt(i)); 288 newGlyphs = true; 289 } 290 } 291 292 if (!newGlyphs) 293 // We didn't override anything, so our override is just the parent page. 294 m_page = parentPage; 295 } 296 } 297 } else { 298 // System fallback. Initialized with the parent's page here, as individual 299 // entries may use different fonts depending on character. If the Font 300 // ever finds it needs a glyph out of the system fallback page, it will 301 // ask the system for the best font to use and fill that glyph in for us. 302 if (parentPage) 303 m_page = parentPage->createCopiedSystemFallbackPage(this); 304 else 305 m_page = GlyphPage::createForMixedFontData(this); 306 } 307 } 308 309 GlyphPageTreeNode* GlyphPageTreeNode::getChild(const FontData* fontData, unsigned pageNumber) 310 { 311 ASSERT(fontData || !m_isSystemFallback); 312 ASSERT(pageNumber == m_pageNumber); 313 314 if (GlyphPageTreeNode* foundChild = fontData ? m_children.get(fontData) : m_systemFallbackChild.get()) 315 return foundChild; 316 317 GlyphPageTreeNode* child = new GlyphPageTreeNode; 318 child->m_parent = this; 319 child->m_level = m_level + 1; 320 if (fontData && fontData->isCustomFont()) { 321 for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent) 322 curr->m_customFontCount++; 323 } 324 325 #ifndef NDEBUG 326 child->m_pageNumber = m_pageNumber; 327 #endif 328 if (fontData) { 329 m_children.set(fontData, adoptPtr(child)); 330 fontData->setMaxGlyphPageTreeLevel(max(fontData->maxGlyphPageTreeLevel(), child->m_level)); 331 } else { 332 m_systemFallbackChild = adoptPtr(child); 333 child->m_isSystemFallback = true; 334 } 335 child->initializePage(fontData, pageNumber); 336 return child; 337 } 338 339 void GlyphPageTreeNode::pruneCustomFontData(const FontData* fontData) 340 { 341 if (!fontData || !m_customFontCount) 342 return; 343 344 // Prune any branch that contains this FontData. 345 if (OwnPtr<GlyphPageTreeNode> node = m_children.take(fontData)) { 346 if (unsigned customFontCount = node->m_customFontCount + 1) { 347 for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent) 348 curr->m_customFontCount -= customFontCount; 349 } 350 } 351 352 // Check any branches that remain that still have custom fonts underneath them. 353 if (!m_customFontCount) 354 return; 355 356 GlyphPageTreeNodeMap::iterator end = m_children.end(); 357 for (GlyphPageTreeNodeMap::iterator it = m_children.begin(); it != end; ++it) 358 it->value->pruneCustomFontData(fontData); 359 } 360 361 void GlyphPageTreeNode::pruneFontData(const SimpleFontData* fontData, unsigned level) 362 { 363 ASSERT(fontData); 364 365 // Prune fall back child (if any) of this font. 366 if (m_systemFallbackChild && m_systemFallbackChild->m_page) 367 m_systemFallbackChild->m_page->removeFontDataFromSystemFallbackPage(fontData); 368 369 // Prune any branch that contains this FontData. 370 if (OwnPtr<GlyphPageTreeNode> node = m_children.take(fontData)) { 371 if (unsigned customFontCount = node->m_customFontCount) { 372 for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent) 373 curr->m_customFontCount -= customFontCount; 374 } 375 } 376 377 level++; 378 if (level > fontData->maxGlyphPageTreeLevel()) 379 return; 380 381 GlyphPageTreeNodeMap::iterator end = m_children.end(); 382 for (GlyphPageTreeNodeMap::iterator it = m_children.begin(); it != end; ++it) 383 it->value->pruneFontData(fontData, level); 384 } 385 386 #ifndef NDEBUG 387 void GlyphPageTreeNode::showSubtree() 388 { 389 Vector<char> indent(level()); 390 indent.fill('\t', level()); 391 indent.append(0); 392 393 GlyphPageTreeNodeMap::iterator end = m_children.end(); 394 for (GlyphPageTreeNodeMap::iterator it = m_children.begin(); it != end; ++it) { 395 printf("%s\t%p %s\n", indent.data(), it->key, it->key->description().utf8().data()); 396 it->value->showSubtree(); 397 } 398 if (m_systemFallbackChild) { 399 printf("%s\t* fallback\n", indent.data()); 400 m_systemFallbackChild->showSubtree(); 401 } 402 } 403 #endif 404 405 } 406 407 #ifndef NDEBUG 408 void showGlyphPageTrees() 409 { 410 printf("Page 0:\n"); 411 showGlyphPageTree(0); 412 HashMap<int, WebCore::GlyphPageTreeNode*>::iterator end = WebCore::GlyphPageTreeNode::roots->end(); 413 for (HashMap<int, WebCore::GlyphPageTreeNode*>::iterator it = WebCore::GlyphPageTreeNode::roots->begin(); it != end; ++it) { 414 printf("\nPage %d:\n", it->key); 415 showGlyphPageTree(it->key); 416 } 417 } 418 419 void showGlyphPageTree(unsigned pageNumber) 420 { 421 WebCore::GlyphPageTreeNode::getRoot(pageNumber)->showSubtree(); 422 } 423 #endif 424