src/third_party/WebKit/Source/platform/fonts/GlyphPageTreeNode.cpp

   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 blink {
  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 #if ENABLE(ASSERT)
  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[newlineCharacter] = space;
 174                     buffer[characterTabulation] = space;
 175                     buffer[noBreakSpace] = space;
 176                 } else if (start == (arabicLetterMark & ~(GlyphPage::size - 1))) {
 177                     buffer[arabicLetterMark - start] = zeroWidthSpace;
 178                 } else if (start == (leftToRightMark & ~(GlyphPage::size - 1))) {
 179                     // LRM, RLM, LRE, RLE, ZWNJ, ZWJ, and PDF must not render at all.
 180                     buffer[leftToRightMark - start] = zeroWidthSpace;
 181                     buffer[rightToLeftMark - start] = zeroWidthSpace;
 182                     buffer[leftToRightEmbed - start] = zeroWidthSpace;
 183                     buffer[rightToLeftEmbed - start] = zeroWidthSpace;
 184                     buffer[leftToRightOverride - start] = zeroWidthSpace;
 185                     buffer[rightToLeftOverride - start] = zeroWidthSpace;
 186                     buffer[zeroWidthNonJoiner - start] = zeroWidthSpace;
 187                     buffer[zeroWidthJoiner - start] = zeroWidthSpace;
 188                     buffer[popDirectionalFormatting - start] = zeroWidthSpace;
 189                     buffer[activateArabicFormShaping - start] = zeroWidthSpace;
 190                     buffer[activateSymmetricSwapping - start] = zeroWidthSpace;
 191                     buffer[firstStrongIsolate - start] = zeroWidthSpace;
 192                     buffer[inhibitArabicFormShaping - start] = zeroWidthSpace;
 193                     buffer[inhibitSymmetricSwapping - start] = zeroWidthSpace;
 194                     buffer[leftToRightIsolate - start] = zeroWidthSpace;
 195                     buffer[nationalDigitShapes - start] = zeroWidthSpace;
 196                     buffer[nominalDigitShapes - start] = zeroWidthSpace;
 197                     buffer[popDirectionalIsolate - start] = zeroWidthSpace;
 198                     buffer[rightToLeftIsolate - start] = zeroWidthSpace;
 199                 } else if (start == (objectReplacementCharacter & ~(GlyphPage::size - 1))) {
 200                     // Object replacement character must not render at all.
 201                     buffer[objectReplacementCharacter - start] = zeroWidthSpace;
 202                 } else if (start == (zeroWidthNoBreakSpace & ~(GlyphPage::size - 1))) {
 203                     // ZWNBS/BOM must not render at all.
 204                     buffer[zeroWidthNoBreakSpace - start] = zeroWidthSpace;
 205                 }
 206             } else {
 207                 bufferLength = GlyphPage::size * 2;
 208                 for (i = 0; i < GlyphPage::size; i++) {
 209                     int c = i + start;
 210                     buffer[i * 2] = U16_LEAD(c);
 211                     buffer[i * 2 + 1] = U16_TRAIL(c);
 212                 }
 213             }
 214
 215             // Now that we have a buffer full of characters, we want to get back an array
 216             // of glyph indices.  This part involves calling into the platform-specific
 217             // routine of our glyph map for actually filling in the page with the glyphs.
 218             // Success is not guaranteed. For example, Times fails to fill page 260, giving glyph data
 219             // for only 128 out of 256 characters.
 220             bool haveGlyphs;
 221             if (!fontData->isSegmented()) {
 222                 m_page = GlyphPage::createForSingleFontData(this, toSimpleFontData(fontData));
 223                 haveGlyphs = fill(m_page.get(), 0, GlyphPage::size, buffer, bufferLength, toSimpleFontData(fontData));
 224             } else {
 225                 m_page = GlyphPage::createForMixedFontData(this);
 226                 haveGlyphs = false;
 227
 228                 const SegmentedFontData* segmentedFontData = toSegmentedFontData(fontData);
 229                 for (int i = segmentedFontData->numRanges() - 1; i >= 0; i--) {
 230                     const FontDataRange& range = segmentedFontData->rangeAt(i);
 231                     // all this casting is to ensure all the parameters to min and max have the same type,
 232                     // to avoid ambiguous template parameter errors on Windows
 233                     int from = max(0, static_cast<int>(range.from()) - static_cast<int>(start));
 234                     int to = 1 + min(static_cast<int>(range.to()) - static_cast<int>(start), static_cast<int>(GlyphPage::size) - 1);
 235                     if (from >= static_cast<int>(GlyphPage::size) || to <= 0)
 236                         continue;
 237
 238                     // If this is a custom font needs to be loaded, do not fill
 239                     // the page so that font fallback is used while loading.
 240                     RefPtr<CustomFontData> customData = range.fontData()->customFontData();
 241                     if (customData && customData->isLoadingFallback()) {
 242                         for (int j = from; j < to; j++) {
 243                             m_page->setCustomFontToLoad(j, customData.get());
 244                             haveGlyphs = true;
 245                         }
 246                         continue;
 247                     }
 248
 249                     haveGlyphs |= fill(m_page.get(), from, to - from, buffer + from * (start < 0x10000 ? 1 : 2), (to - from) * (start < 0x10000 ? 1 : 2), range.fontData().get());
 250                 }
 251             }
 252
 253             if (!haveGlyphs)
 254                 m_page = nullptr;
 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                     }
 295
 296                     if (parentPage->customFontToLoadAt(i)) {
 297                         m_page->setCustomFontToLoad(i, parentPage->customFontToLoadAt(i));
 298                     } else if (fallbackPage->customFontToLoadAt(i) && !parentPage->glyphAt(i)) {
 299                         m_page->setCustomFontToLoad(i, fallbackPage->customFontToLoadAt(i));
 300                         newGlyphs = true;
 301                     }
 302                 }
 303
 304                 if (!newGlyphs)
 305                     // We didn't override anything, so our override is just the parent page.
 306                     m_page = parentPage;
 307             }
 308         }
 309     } else {
 310         // System fallback. Initialized with the parent's page here, as individual
 311         // entries may use different fonts depending on character. If the Font
 312         // ever finds it needs a glyph out of the system fallback page, it will
 313         // ask the system for the best font to use and fill that glyph in for us.
 314         if (parentPage)
 315             m_page = parentPage->createCopiedSystemFallbackPage(this);
 316         else
 317             m_page = GlyphPage::createForMixedFontData(this);
 318     }
 319 }
 320
 321 GlyphPageTreeNode* GlyphPageTreeNode::getChild(const FontData* fontData, unsigned pageNumber)
 322 {
 323     ASSERT(fontData || !m_isSystemFallback);
 324     ASSERT(pageNumber == m_pageNumber);
 325
 326     if (GlyphPageTreeNode* foundChild = fontData ? m_children.get(fontData) : m_systemFallbackChild.get())
 327         return foundChild;
 328
 329     GlyphPageTreeNode* child = new GlyphPageTreeNode;
 330     child->m_parent = this;
 331     child->m_level = m_level + 1;
 332     if (fontData && fontData->isCustomFont()) {
 333         for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
 334             curr->m_customFontCount++;
 335     }
 336
 337 #if ENABLE(ASSERT)
 338     child->m_pageNumber = m_pageNumber;
 339 #endif
 340     if (fontData) {
 341         m_children.set(fontData, adoptPtr(child));
 342         fontData->setMaxGlyphPageTreeLevel(max(fontData->maxGlyphPageTreeLevel(), child->m_level));
 343     } else {
 344         m_systemFallbackChild = adoptPtr(child);
 345         child->m_isSystemFallback = true;
 346     }
 347     child->initializePage(fontData, pageNumber);
 348     return child;
 349 }
 350
 351 void GlyphPageTreeNode::pruneCustomFontData(const FontData* fontData)
 352 {
 353     if (!fontData || !m_customFontCount)
 354         return;
 355
 356     // Prune any branch that contains this FontData.
 357     if (OwnPtr<GlyphPageTreeNode> node = m_children.take(fontData)) {
 358         if (unsigned customFontCount = node->m_customFontCount + 1) {
 359             for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
 360                 curr->m_customFontCount -= customFontCount;
 361         }
 362     }
 363
 364     // Check any branches that remain that still have custom fonts underneath them.
 365     if (!m_customFontCount)
 366         return;
 367
 368     GlyphPageTreeNodeMap::iterator end = m_children.end();
 369     for (GlyphPageTreeNodeMap::iterator it = m_children.begin(); it != end; ++it)
 370         it->value->pruneCustomFontData(fontData);
 371 }
 372
 373 void GlyphPageTreeNode::pruneFontData(const SimpleFontData* fontData, unsigned level)
 374 {
 375     ASSERT(fontData);
 376
 377     // Prune fall back child (if any) of this font.
 378     if (m_systemFallbackChild && m_systemFallbackChild->m_page)
 379         m_systemFallbackChild->m_page->removeFontDataFromSystemFallbackPage(fontData);
 380
 381     // Prune any branch that contains this FontData.
 382     if (OwnPtr<GlyphPageTreeNode> node = m_children.take(fontData)) {
 383         if (unsigned customFontCount = node->m_customFontCount) {
 384             for (GlyphPageTreeNode* curr = this; curr; curr = curr->m_parent)
 385                 curr->m_customFontCount -= customFontCount;
 386         }
 387     }
 388
 389     level++;
 390     if (level > fontData->maxGlyphPageTreeLevel())
 391         return;
 392
 393     GlyphPageTreeNodeMap::iterator end = m_children.end();
 394     for (GlyphPageTreeNodeMap::iterator it = m_children.begin(); it != end; ++it)
 395         it->value->pruneFontData(fontData, level);
 396 }
 397
 398 } // namespace blink
 399