Home | History | Annotate | Download | only in graphics
      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