WebCore:
authormjs@apple.com <mjs@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 26 Mar 2008 19:22:01 +0000 (19:22 +0000)
committermjs@apple.com <mjs@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 26 Mar 2008 19:22:01 +0000 (19:22 +0000)
2008-03-26  Maciej Stachowiak  <mjs@apple.com>

        Reviewed by Darin.

        - fixed "SVG multichar glyph matching matches longest instead of first (affects Acid3 test 79)"
        http://bugs.webkit.org/show_bug.cgi?id=18118

        * svg/SVGFont.cpp:
        (WebCore::SVGTextRunWalker::walk):
        * svg/SVGFontElement.cpp:
        (WebCore::SVGFontElement::SVGFontElement):
        (WebCore::SVGFontElement::addGlyphToCache):
        (WebCore::SVGFontElement::removeGlyphFromCache):
        (WebCore::SVGFontElement::ensureGlyphCache):
        (WebCore::SVGFontElement::getGlyphIdentifiersForString):
        * svg/SVGFontElement.h:
        * svg/SVGGlyphElement.h:
        (WebCore::SVGGlyphIdentifier::SVGGlyphIdentifier):
        * svg/SVGGlyphMap.h: Added. New radix tree based glyph map.
        (WebCore::GlyphMapNode::GlyphMapNode):
        (WebCore::SVGGlyphMap::SVGGlyphMap):
        (WebCore::SVGGlyphMap::add):
        (WebCore::SVGGlyphMap::compareGlyphPriority):
        (WebCore::SVGGlyphMap::get):
        (WebCore::SVGGlyphMap::clear):

LayoutTests:

2008-03-26  Maciej Stachowiak  <mjs@apple.com>

        Reviewed by Darin.

        - test updates for "SVG multichar glyph matching matches longest instead of first (affects Acid3 test 79)"
        http://bugs.webkit.org/show_bug.cgi?id=18118

        These test cases were already checking for this exact bug and now
        render correctly.

        * platform/mac/svg/W3C-SVG-1.1/fonts-glyph-02-t-expected.txt:
        * platform/mac/svg/W3C-SVG-1.1/fonts-glyph-04-t-expected.txt:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@31324 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/platform/mac/svg/W3C-SVG-1.1/fonts-glyph-02-t-expected.txt
LayoutTests/platform/mac/svg/W3C-SVG-1.1/fonts-glyph-04-t-expected.txt
WebCore/ChangeLog
WebCore/svg/SVGFont.cpp
WebCore/svg/SVGFontElement.cpp
WebCore/svg/SVGFontElement.h
WebCore/svg/SVGGlyphElement.h
WebCore/svg/SVGGlyphMap.h [new file with mode: 0644]

index 73a909b4eb3e749e37e32bff94ffec31f1d34283..20f8c95baae31c2ac335e6d6b5f6cff61ace4d59 100644 (file)
@@ -1,4 +1,17 @@
-2008-03-26  Eric Seidel  <eric@webkit.org>
+2008-03-26  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Darin.
+
+        - test updates for "SVG multichar glyph matching matches longest instead of first (affects Acid3 test 79)"
+        http://bugs.webkit.org/show_bug.cgi?id=18118
+
+        These test cases were already checking for this exact bug and now
+        render correctly.
+        
+        * platform/mac/svg/W3C-SVG-1.1/fonts-glyph-02-t-expected.txt:
+        * platform/mac/svg/W3C-SVG-1.1/fonts-glyph-04-t-expected.txt:
+
+o2008-03-26  Eric Seidel  <eric@webkit.org>
 
         Reviewed by darin.
 
index d7bc56ec2b0bb4f8c5cb55e76af624468c1327f1..bf04ca5e8ed2dd46d4e3e1d2c600b11b389cdc04 100644 (file)
@@ -2,16 +2,16 @@ layer at (0,0) size 480x360
   RenderView at (0,0) size 480x360
 layer at (0,0) size 480x360
   RenderSVGRoot {svg} at (0.50,0.50) size 479x359
-    RenderSVGContainer {g} at (100,36) size 209x180
+    RenderSVGContainer {g} at (100,36) size 210x180
       RenderSVGHiddenContainer {defs} at (0,0) size 0x0
-      RenderSVGContainer {g} at (100,36) size 184x80
-        RenderSVGText {text} at (100,100) size 184x80 contains 1 chunk(s)
-          RenderSVGInlineText {#text} at (0,-64) size 184x80
-            chunk 1 text run 1 at (100.00,100.00) startOffset 0 endOffset 5 width 184.00 RTL: "\x{69A} \x{69A}\x{69A}\x{69A}"
-      RenderSVGContainer {g} at (100,136) size 209x80
-        RenderSVGText {text} at (100,200) size 209x80 contains 1 chunk(s)
-          RenderSVGInlineText {#text} at (0,-64) size 209x80
-            chunk 1 text run 1 at (100.00,200.00) startOffset 0 endOffset 5 width 223.92 RTL: "\x{62E} \x{62E}\x{62E}\x{62E}"
+      RenderSVGContainer {g} at (100,36) size 200x80
+        RenderSVGText {text} at (100,100) size 200x80 contains 1 chunk(s)
+          RenderSVGInlineText {#text} at (0,-64) size 200x80
+            chunk 1 text run 1 at (100.00,100.00) startOffset 0 endOffset 5 width 200.00 RTL: "\x{69A} \x{69A}\x{69A}\x{69A}"
+      RenderSVGContainer {g} at (100,136) size 210x80
+        RenderSVGText {text} at (100,200) size 210x80 contains 1 chunk(s)
+          RenderSVGInlineText {#text} at (0,-64) size 210x80
+            chunk 1 text run 1 at (100.00,200.00) startOffset 0 endOffset 5 width 209.92 RTL: "\x{62E} \x{62E}\x{62E}\x{62E}"
     RenderSVGText {text} at (10,340) size 264x46 contains 1 chunk(s)
       RenderSVGInlineText {#text} at (0,-36) size 264x46
         chunk 1 text run 1 at (10.00,340.00) startOffset 0 endOffset 16 width 264.00: "$Revision: 1.7 $"
index 6baaf4fc42688c6bc395733c45dcad8a55a5113c..55eeef375fc0c9349f255d441c16fbbc32907926 100644 (file)
@@ -2,11 +2,11 @@ layer at (0,0) size 480x360
   RenderView at (0,0) size 480x360
 layer at (0,0) size 480x360
   RenderSVGRoot {svg} at (0.50,0.50) size 479x359
-    RenderSVGContainer {g} at (100,60) size 25x150
+    RenderSVGContainer {g} at (100,60) size 64x150
       RenderSVGHiddenContainer {defs} at (0,0) size 0x0
-      RenderSVGText {text} at (100,100) size 25x50 contains 1 chunk(s)
-        RenderSVGInlineText {#text} at (0,-40) size 25x50
-          chunk 1 text run 1 at (100.00,100.00) startOffset 0 endOffset 3 width 25.00: "ffl"
+      RenderSVGText {text} at (100,100) size 64x50 contains 1 chunk(s)
+        RenderSVGInlineText {#text} at (0,-40) size 64x50
+          chunk 1 text run 1 at (100.00,100.00) startOffset 0 endOffset 3 width 64.00: "ffl"
       RenderSVGText {text} at (100,200) size 25x50 contains 1 chunk(s)
         RenderSVGInlineText {#text} at (0,-40) size 25x50
           chunk 1 text run 1 at (100.00,200.00) startOffset 0 endOffset 3 width 25.00: "ffl"
index 8bcd5dbb92a652b53d9941aca9178e56ac72c991..bdf7f14785cfd79624ae2e9fc2e705d362407ea8 100644 (file)
@@ -1,3 +1,29 @@
+2008-03-26  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Darin.
+
+        - fixed "SVG multichar glyph matching matches longest instead of first (affects Acid3 test 79)"
+        http://bugs.webkit.org/show_bug.cgi?id=18118
+
+        * svg/SVGFont.cpp:
+        (WebCore::SVGTextRunWalker::walk):
+        * svg/SVGFontElement.cpp:
+        (WebCore::SVGFontElement::SVGFontElement):
+        (WebCore::SVGFontElement::addGlyphToCache):
+        (WebCore::SVGFontElement::removeGlyphFromCache):
+        (WebCore::SVGFontElement::ensureGlyphCache):
+        (WebCore::SVGFontElement::getGlyphIdentifiersForString):
+        * svg/SVGFontElement.h:
+        * svg/SVGGlyphElement.h:
+        (WebCore::SVGGlyphIdentifier::SVGGlyphIdentifier):
+        * svg/SVGGlyphMap.h: Added. New radix tree based glyph map.
+        (WebCore::GlyphMapNode::GlyphMapNode):
+        (WebCore::SVGGlyphMap::SVGGlyphMap):
+        (WebCore::SVGGlyphMap::add):
+        (WebCore::SVGGlyphMap::compareGlyphPriority):
+        (WebCore::SVGGlyphMap::get):
+        (WebCore::SVGGlyphMap::clear):
+
 2008-03-26  David Hyatt  <hyatt@apple.com>
 
         Fix build bustage on Tiger.  Tiger will not have the bug fix.
index e1974b09f35f3fc9a978c3f3f4e2360432b90dd4..1ed806aae1fcdad19b0fedbab8ed504284e00b1b 100644 (file)
@@ -29,6 +29,7 @@
 #include "SimpleFontData.h"
 #include "SVGFontData.h"
 #include "SVGGlyphElement.h"
+#include "SVGGlyphMap.h"
 #include "SVGFontElement.h"
 #include "SVGFontFaceElement.h"
 #include "SVGMissingGlyphElement.h"
@@ -241,9 +242,6 @@ struct SVGTextRunWalker {
         // Should hold true for SVG text, otherwhise sth. is wrong
         ASSERT(to - from == run.length());
 
-        int maximumHashKeyLength = m_fontElement->maximumHashKeyLength();
-        ASSERT(maximumHashKeyLength >= 0);
-
         Vector<SVGGlyphIdentifier::ArabicForm> chars(charactersWithArabicForm(String(run.data(from), run.length()), run.rtl()));
 
         SVGGlyphIdentifier identifier;
@@ -255,37 +253,33 @@ struct SVGTextRunWalker {
             // If characterLookupRange is > 0, then the font defined ligatures (length of unicode property value > 1).
             // We have to check wheter the current character & the next character define a ligature. This needs to be
             // extended to the n-th next character (where n is 'characterLookupRange'), to check for any possible ligature.
-            characterLookupRange = maximumHashKeyLength + i >= endOfScanRange ? endOfScanRange - i : maximumHashKeyLength;
-
-            // FIXME: instead of checking from longest string to shortest, this should really scan in order
-            // of the glyphs and pick the first match
-            while (characterLookupRange > 0 && !foundGlyph) {
-                String lookupString(run.data(run.rtl() ? run.length() - (i + characterLookupRange) : i), characterLookupRange);
-
-                Vector<SVGGlyphIdentifier> glyphs = m_fontElement->glyphIdentifiersForString(lookupString);
-                Vector<SVGGlyphIdentifier>::iterator it = glyphs.begin();
-                Vector<SVGGlyphIdentifier>::iterator end = glyphs.end();
-
-                for (; it != end; ++it) {
-                    identifier = *it;
-
-                    unsigned int startPosition = run.rtl() ? run.length() - (i + lookupString.length()) : i;
-                    unsigned int endPosition = startPosition + lookupString.length();
-
-                    if (identifier.isValid && isCompatibleGlyph(identifier, isVerticalText, language, chars, startPosition, endPosition)) {
-                        ASSERT(characterLookupRange > 0);
-                        i += characterLookupRange - 1;
-                        m_walkerData.charsConsumed += characterLookupRange;
-
-                        foundGlyph = true;
-                        SVGGlyphElement::inheritUnspecifiedAttributes(identifier, m_fontData);
-                        break;
-                    }
+            characterLookupRange = endOfScanRange - i;
+
+            String lookupString(run.data(run.rtl() ? run.length() - (i + characterLookupRange) : i), characterLookupRange);
+
+            Vector<SVGGlyphIdentifier> glyphs;
+            m_fontElement->getGlyphIdentifiersForString(lookupString, glyphs);
+            Vector<SVGGlyphIdentifier>::iterator it = glyphs.begin();
+            Vector<SVGGlyphIdentifier>::iterator end = glyphs.end();
+            
+            for (; it != end; ++it) {
+                identifier = *it;
+                
+                unsigned int startPosition = run.rtl() ? run.length() - (i + lookupString.length()) : i;
+                unsigned int endPosition = startPosition + lookupString.length();
+                
+                if (identifier.isValid && isCompatibleGlyph(identifier, isVerticalText, language, chars, startPosition, endPosition)) {
+                    ASSERT(characterLookupRange > 0);
+                    i += identifier.nameLength - 1;
+                    m_walkerData.charsConsumed += identifier.nameLength;
+                    
+                    foundGlyph = true;
+                    SVGGlyphElement::inheritUnspecifiedAttributes(identifier, m_fontData);
+                    break;
                 }
-
-                characterLookupRange--;
             }
 
+            
             if (!foundGlyph) {
                 ++m_walkerData.charsConsumed;
                 if (SVGMissingGlyphElement* element = m_fontElement->firstMissingGlyphElement()) {
index a21450926713d291514a4ce9848c526f6720d220..b76b5897cf60a9dc6770fd41055c9c1381bbfa58 100644 (file)
@@ -36,7 +36,7 @@ using namespace SVGNames;
 
 SVGFontElement::SVGFontElement(const QualifiedName& tagName, Document* doc)
     : SVGStyledElement(tagName, doc)
-    , m_maximumHashKeyLength(0)
+    , m_isGlyphCacheValid(false)
 {
 }
 
@@ -46,78 +46,16 @@ SVGFontElement::~SVGFontElement()
 
 void SVGFontElement::addGlyphToCache(SVGGlyphElement* glyphElement)
 {
-    ASSERT(glyphElement);
-
-    String glyphString = glyphElement->getAttribute(unicodeAttr);
-    if (glyphString.isEmpty()) // No unicode property, means that glyph will be used in <altGlyph> situations!
-        return;
-
-    SVGGlyphIdentifier identifier = glyphElement->buildGlyphIdentifier();
-    identifier.isValid = true;
-
-    if (glyphString.length() > m_maximumHashKeyLength)
-        m_maximumHashKeyLength = glyphString.length();
-
-    GlyphHashMap::iterator glyphsIt = m_glyphMap.find(glyphString);
-    if (glyphsIt == m_glyphMap.end()) {
-        Vector<SVGGlyphIdentifier> glyphs;
-        glyphs.append(identifier);
-
-        m_glyphMap.add(glyphString, glyphs);
-    } else {
-        Vector<SVGGlyphIdentifier>& glyphs = (*glyphsIt).second;
-        glyphs.append(identifier);
-    }
+    if (m_isGlyphCacheValid)
+        m_glyphMap.clear();
+    m_isGlyphCacheValid = false;
 }
 
 void SVGFontElement::removeGlyphFromCache(SVGGlyphElement* glyphElement)
 {
-    ASSERT(glyphElement);
-
-    String glyphString = glyphElement->getAttribute(unicodeAttr);
-    if (glyphString.isEmpty()) // No unicode property, means that glyph will be used in <altGlyph> situations!
-        return;
-
-    GlyphHashMap::iterator glyphsIt = m_glyphMap.find(glyphString);
-    ASSERT(glyphsIt != m_glyphMap.end());
-
-    Vector<SVGGlyphIdentifier>& glyphs = (*glyphsIt).second;
-
-    if (glyphs.size() == 1)
-        m_glyphMap.remove(glyphString);
-    else {
-        SVGGlyphIdentifier identifier = glyphElement->buildGlyphIdentifier();
-        identifier.isValid = true;
-
-        Vector<SVGGlyphIdentifier>::iterator it = glyphs.begin();
-        Vector<SVGGlyphIdentifier>::iterator end = glyphs.end();
-
-        unsigned int position = 0;
-        for (; it != end; ++it) {
-            if ((*it) == identifier)
-                break;
-
-            position++;
-        }
-
-        ASSERT(position < glyphs.size());
-        glyphs.remove(position);
-    }
-
-    // If we remove a glyph from cache, whose unicode property length is equal to
-    // m_maximumHashKeyLength then we need to recalculate the hash key length, because there
-    // is either no more glyph with that length, or there are still more glyphs with the maximum length.
-    if (glyphString.length() == m_maximumHashKeyLength) {
-        m_maximumHashKeyLength = 0;
-
-        GlyphHashMap::iterator it = m_glyphMap.begin();
-        GlyphHashMap::iterator end = m_glyphMap.end();
-
-        for (; it != end; ++it) {
-            if ((*it).first.length() > m_maximumHashKeyLength)
-                m_maximumHashKeyLength = (*it).first.length();
-        }
-    }
+    if (m_isGlyphCacheValid)
+        m_glyphMap.clear();
+    m_isGlyphCacheValid = false;
 }
 
 SVGMissingGlyphElement* SVGFontElement::firstMissingGlyphElement() const
@@ -130,15 +68,27 @@ SVGMissingGlyphElement* SVGFontElement::firstMissingGlyphElement() const
     return 0;
 }
 
-const Vector<SVGGlyphIdentifier>& SVGFontElement::glyphIdentifiersForString(const String& string) const
+void SVGFontElement::ensureGlyphCache() const
 {
-    GlyphHashMap::const_iterator it = m_glyphMap.find(string);
-    if (it == m_glyphMap.end()) {
-        static Vector<SVGGlyphIdentifier> s_emptyGlyphList;
-        return s_emptyGlyphList;
+    if (m_isGlyphCacheValid)
+        return;
+
+    for (Node* child = firstChild(); child; child = child->nextSibling()) {
+        if (child->hasTagName(glyphTag)) {
+            SVGGlyphElement* glyph = static_cast<SVGGlyphElement*>(child);
+            String unicode = glyph->getAttribute(unicodeAttr);
+            if (unicode.length())
+                m_glyphMap.add(unicode, glyph->buildGlyphIdentifier());
+        }
     }
+        
+    m_isGlyphCacheValid = true;
+}
 
-    return (*it).second;
+void SVGFontElement::getGlyphIdentifiersForString(const String& string, Vector<SVGGlyphIdentifier>& glyphs) const
+{
+    ensureGlyphCache();
+    m_glyphMap.get(string, glyphs);
 }
 
 }
index 1005654a3b5c5022e3506420c3a032feff988165..8223ada7a5d10eb739093f77ea88af134a55aab8 100644 (file)
@@ -24,6 +24,7 @@
 #if ENABLE(SVG_FONTS)
 #include "SVGExternalResourcesRequired.h"
 #include "SVGGlyphElement.h"
+#include "SVGGlyphMap.h"
 #include "SVGStyledElement.h"
 
 namespace WebCore {
@@ -41,19 +42,15 @@ namespace WebCore {
         void addGlyphToCache(SVGGlyphElement*);
         void removeGlyphFromCache(SVGGlyphElement*);
 
-        const Vector<SVGGlyphIdentifier>& glyphIdentifiersForString(const String&) const;
-
-        // Returns the longest hash key length (the 'unicode' property value with the
-        // highest amount of characters) - ie. for <glyph unicode="ffl"/> it will return 3.
-        unsigned int maximumHashKeyLength() const { return m_maximumHashKeyLength; }
+        void getGlyphIdentifiersForString(const String&, Vector<SVGGlyphIdentifier>&) const;
 
         SVGMissingGlyphElement* firstMissingGlyphElement() const;
 
     private:
-        typedef HashMap<String, Vector<SVGGlyphIdentifier> > GlyphHashMap;
-        GlyphHashMap m_glyphMap;
+        void ensureGlyphCache() const;
 
-        unsigned int m_maximumHashKeyLength;
+        mutable SVGGlyphMap m_glyphMap;
+        mutable bool m_isGlyphCacheValid;
     };
 
 } // namespace WebCore
index e05f2845de9b42edb451f96b6da755ade0c6fd21..bd6b3cde6274c7f79f5ba7617dcb6237b01ac4e2 100644 (file)
@@ -51,9 +51,10 @@ namespace WebCore {
 
         SVGGlyphIdentifier()
             : isValid(false)
-            , priority(0)
             , orientation(Both)
             , arabicForm(None)
+            , priority(0)
+            , nameLength(0)
             , horizontalAdvanceX(0.0f)
             , verticalOriginX(0.0f)
             , verticalOriginY(0.0f)
@@ -83,10 +84,11 @@ namespace WebCore {
         }
 
         bool isValid : 1;
-        int priority;
 
         Orientation orientation : 2;
         ArabicForm arabicForm : 3;
+        int priority;
+        size_t nameLength;
         String glyphName;
 
         float horizontalAdvanceX;
diff --git a/WebCore/svg/SVGGlyphMap.h b/WebCore/svg/SVGGlyphMap.h
new file mode 100644 (file)
index 0000000..97f2e18
--- /dev/null
@@ -0,0 +1,105 @@
+/*
+   Copyright (C) 2008 Apple, Inc
+
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public License
+   along with this library; see the file COPYING.LIB.  If not, write to
+   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+   Boston, MA 02110-1301, USA.
+ */
+
+#ifndef SVGGlyphMap_h
+#define SVGGlyphMap_h
+
+#if ENABLE(SVG_FONTS)
+#include "SVGGlyphElement.h"
+
+
+namespace WebCore {
+
+    struct GlyphMapNode;
+
+    typedef HashMap<UChar, RefPtr<GlyphMapNode> > GlyphMapLayer;
+
+    struct GlyphMapNode : public RefCounted<GlyphMapNode> {
+        GlyphMapNode() { }
+
+        Vector<SVGGlyphIdentifier> glyphs;
+
+        GlyphMapLayer children;
+    };
+
+    class SVGGlyphMap {
+    public:
+        SVGGlyphMap() : m_currentPriority(0) { }
+
+        void add(const String& string, const SVGGlyphIdentifier& glyph) 
+        {
+            size_t len = string.length();
+            GlyphMapLayer* currentLayer = &m_rootLayer;
+
+            RefPtr<GlyphMapNode> node;
+            for (size_t i = 0; i < len; i++) {
+                UChar curChar = string[i];
+                node = currentLayer->get(curChar);
+                if (!node) {
+                    node = new GlyphMapNode;
+                    currentLayer->set(curChar, node);
+                }
+                currentLayer = &node->children;
+            }
+
+            if (node) {
+                node->glyphs.append(glyph);
+                node->glyphs.last().priority = m_currentPriority++;
+                node->glyphs.last().nameLength = len;
+                node->glyphs.last().isValid = true;
+            }
+        }
+
+        static inline bool compareGlyphPriority(const SVGGlyphIdentifier& first, const SVGGlyphIdentifier& second)
+        {
+            return first.priority < second.priority;
+        }
+
+        void get(const String& string, Vector<SVGGlyphIdentifier>& glyphs)
+        {
+            GlyphMapLayer* currentLayer = &m_rootLayer;
+
+            for (size_t i = 0; i < string.length(); i++) {
+                UChar curChar = string[i];
+                RefPtr<GlyphMapNode> node = currentLayer->get(curChar);
+                if (!node)
+                    break;
+                glyphs.append(node->glyphs);
+                currentLayer = &node->children;
+            }
+            std::sort(glyphs.begin(), glyphs.end(), compareGlyphPriority);
+        }
+
+        void clear() 
+        { 
+            m_rootLayer.clear(); 
+            m_currentPriority = 0;
+        }
+
+    private:
+        GlyphMapLayer m_rootLayer;
+        int m_currentPriority;
+    };
+
+}
+
+#endif // ENABLE(SVG_FONTS)
+
+
+#endif //SVGGlyphMap_h