Laying out a TextRun using an SVG font is O(n^2)
[WebKit-https.git] / Source / WebCore / svg / SVGFontData.cpp
1 /*
2  * Copyright (C) 2008 Nikolas Zimmermann <zimmermann@kde.org>
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public License
15  * along with this library; see the file COPYING.LIB.  If not, write to
16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  * Boston, MA 02110-1301, USA.
18  */
19
20 #include "config.h"
21
22 #if ENABLE(SVG_FONTS)
23 #include "SVGFontData.h"
24
25 #include "RenderElement.h"
26 #include "SVGAltGlyphElement.h"
27 #include "SVGFontElement.h"
28 #include "SVGFontFaceElement.h"
29 #include "SVGGlyph.h"
30 #include "SVGGlyphElement.h"
31 #include "SVGNames.h"
32 #include "SVGTextRunRenderingContext.h"
33 #include "TextRun.h"
34 #include "WidthIterator.h"
35 #include "XMLNames.h"
36 #include <wtf/text/StringBuilder.h>
37 #include <wtf/unicode/CharacterNames.h>
38
39 using namespace WTF;
40 using namespace Unicode;
41
42 namespace WebCore {
43
44 static String createStringWithMirroredCharacters(StringView);
45 static void computeNormalizedSpaces(const TextRun&, bool mirror, String& normalizedSpacesStringCache);
46
47 SVGFontData::SVGFontData(SVGFontFaceElement* fontFaceElement)
48     : m_svgFontFaceElement(fontFaceElement)
49     , m_horizontalOriginX(fontFaceElement->horizontalOriginX())
50     , m_horizontalOriginY(fontFaceElement->horizontalOriginY())
51     , m_horizontalAdvanceX(fontFaceElement->horizontalAdvanceX())
52     , m_verticalOriginX(fontFaceElement->verticalOriginX())
53     , m_verticalOriginY(fontFaceElement->verticalOriginY())
54     , m_verticalAdvanceY(fontFaceElement->verticalAdvanceY())
55 {
56     ASSERT_ARG(fontFaceElement, fontFaceElement);
57 }
58
59 void SVGFontData::initializeFontData(SimpleFontData* fontData, float fontSize)
60 {
61     ASSERT(fontData);
62
63     SVGFontFaceElement* svgFontFaceElement = this->svgFontFaceElement();
64     ASSERT(svgFontFaceElement);
65
66     SVGFontElement* svgFontElement = svgFontFaceElement->associatedFontElement();
67     ASSERT(svgFontElement);
68     GlyphData missingGlyphData;
69     missingGlyphData.fontData = fontData;
70     missingGlyphData.glyph = svgFontElement->missingGlyph();
71     fontData->setMissingGlyphData(missingGlyphData);
72
73     fontData->setZeroWidthSpaceGlyph(0);
74     fontData->determinePitch();
75
76     unsigned unitsPerEm = svgFontFaceElement->unitsPerEm();
77     float scale = scaleEmToUnits(fontSize, unitsPerEm);
78     float xHeight = svgFontFaceElement->xHeight() * scale;
79     float ascent = svgFontFaceElement->ascent() * scale;
80     float descent = svgFontFaceElement->descent() * scale;
81     float lineGap = 0.1f * fontSize;
82
83     GlyphPage* glyphPageZero = GlyphPageTreeNode::getRootChild(fontData, 0)->page();
84
85     if (!xHeight && glyphPageZero) {
86         // Fallback if x_heightAttr is not specified for the font element.
87         Glyph letterXGlyph = glyphPageZero->glyphDataForCharacter('x').glyph;
88         xHeight = letterXGlyph ? fontData->widthForGlyph(letterXGlyph) : 2 * ascent / 3;
89     }
90
91     FontMetrics& fontMetrics = fontData->fontMetrics();
92     fontMetrics.setUnitsPerEm(unitsPerEm);
93     fontMetrics.setAscent(ascent);
94     fontMetrics.setDescent(descent);
95     fontMetrics.setLineGap(lineGap);
96     fontMetrics.setLineSpacing(roundf(ascent) + roundf(descent) + roundf(lineGap));
97     fontMetrics.setXHeight(xHeight);
98
99     if (!glyphPageZero) {
100         fontData->setSpaceGlyph(0);
101         fontData->setSpaceWidth(0);
102         fontData->setAvgCharWidth(0);
103         fontData->setMaxCharWidth(ascent);
104         return;
105     }
106
107     // Calculate space width.
108     Glyph spaceGlyph = glyphPageZero->glyphDataForCharacter(' ').glyph;
109     fontData->setSpaceGlyph(spaceGlyph);
110     fontData->setSpaceWidth(fontData->widthForGlyph(spaceGlyph));
111
112     // Estimate average character width.
113     Glyph numeralZeroGlyph = glyphPageZero->glyphDataForCharacter('0').glyph;
114     fontData->setAvgCharWidth(numeralZeroGlyph ? fontData->widthForGlyph(numeralZeroGlyph) : fontData->spaceWidth());
115
116     // Estimate maximum character width.
117     Glyph letterWGlyph = glyphPageZero->glyphDataForCharacter('W').glyph;
118     fontData->setMaxCharWidth(letterWGlyph ? fontData->widthForGlyph(letterWGlyph) : ascent);
119 }
120
121 float SVGFontData::widthForSVGGlyph(Glyph glyph, float fontSize) const
122 {
123     SVGFontFaceElement* svgFontFaceElement = this->svgFontFaceElement();
124     ASSERT(svgFontFaceElement);
125
126     SVGFontElement* associatedFontElement = svgFontFaceElement->associatedFontElement();
127     ASSERT(associatedFontElement);
128
129     SVGGlyph svgGlyph = associatedFontElement->svgGlyphForGlyph(glyph);
130     SVGGlyphElement::inheritUnspecifiedAttributes(svgGlyph, this);
131     return svgGlyph.horizontalAdvanceX * scaleEmToUnits(fontSize, svgFontFaceElement->unitsPerEm());
132 }
133
134 bool SVGFontData::applySVGGlyphSelection(WidthIterator& iterator, GlyphData& glyphData, bool mirror, int currentCharacter, unsigned& advanceLength, String& normalizedSpacesStringCache) const
135 {
136     const TextRun& run = iterator.run();
137     Vector<SVGGlyph::ArabicForm>& arabicForms = iterator.arabicForms();
138     ASSERT(run.charactersLength() >= currentCharacter);
139
140     SVGFontFaceElement* svgFontFaceElement = this->svgFontFaceElement();
141     ASSERT(svgFontFaceElement);
142
143     SVGFontElement* associatedFontElement = svgFontFaceElement->associatedFontElement();
144     ASSERT(associatedFontElement);
145
146     RenderObject* renderObject = 0;
147     if (TextRun::RenderingContext* renderingContext = run.renderingContext())
148         renderObject = &static_cast<SVGTextRunRenderingContext*>(renderingContext)->renderer();
149
150     String language;
151     bool isVerticalText = false;
152     Vector<String> altGlyphNames;
153
154     if (renderObject) {
155         RenderElement* parentRenderer = renderObject->isRenderElement() ? toRenderElement(renderObject) : renderObject->parent();
156         ASSERT(parentRenderer);
157
158         isVerticalText = parentRenderer->style().svgStyle().isVerticalWritingMode();
159         if (Element* parentRendererElement = parentRenderer->element()) {
160             language = parentRendererElement->getAttribute(XMLNames::langAttr);
161
162             if (isSVGAltGlyphElement(parentRendererElement)) {
163                 SVGAltGlyphElement* altGlyph = toSVGAltGlyphElement(parentRendererElement);
164                 if (!altGlyph->hasValidGlyphElements(altGlyphNames))
165                     altGlyphNames.clear();
166             }
167         }
168     }
169
170     Vector<SVGGlyph> glyphs;
171     size_t altGlyphNamesSize = altGlyphNames.size();
172     if (altGlyphNamesSize) {
173         for (size_t index = 0; index < altGlyphNamesSize; ++index)
174             associatedFontElement->collectGlyphsForGlyphName(altGlyphNames[index], glyphs);
175
176         // Assign the unicodeStringLength now that its known.
177         size_t glyphsSize = glyphs.size();
178         for (size_t i = 0; i < glyphsSize; ++i)
179             glyphs[i].unicodeStringLength = run.length();
180
181         // Do not check alt glyphs for compatibility. Just return the first one.
182         // Later code will fail if we do not do this and the glyph is incompatible.
183         if (glyphsSize) {
184             SVGGlyph& svgGlyph = glyphs[0];
185             iterator.setLastGlyphName(svgGlyph.glyphName);
186             glyphData.glyph = svgGlyph.tableEntry;
187             advanceLength = svgGlyph.unicodeStringLength;
188             return true;
189         }
190     } else {
191         // Associate text with arabic forms, if needed.
192         computeNormalizedSpaces(run, mirror, normalizedSpacesStringCache);
193         auto remainingTextInRun = normalizedSpacesStringCache.substring(currentCharacter);
194
195         if (!currentCharacter && arabicForms.isEmpty())
196             arabicForms = charactersWithArabicForm(remainingTextInRun, mirror);
197
198         associatedFontElement->collectGlyphsForString(remainingTextInRun, glyphs);
199     }
200
201     size_t glyphsSize = glyphs.size();
202     for (size_t i = 0; i < glyphsSize; ++i) {
203         SVGGlyph& svgGlyph = glyphs[i];
204         if (svgGlyph.isPartOfLigature)
205             continue;
206         if (!isCompatibleGlyph(svgGlyph, isVerticalText, language, arabicForms, currentCharacter, currentCharacter + svgGlyph.unicodeStringLength))
207             continue;
208         iterator.setLastGlyphName(svgGlyph.glyphName);
209         glyphData.glyph = svgGlyph.tableEntry;
210         advanceLength = svgGlyph.unicodeStringLength;
211         return true;
212     }
213
214     iterator.setLastGlyphName(String());
215     return false;
216 }
217
218 bool SVGFontData::fillSVGGlyphPage(GlyphPage* pageToFill, unsigned offset, unsigned length, UChar* buffer, unsigned bufferLength, const SimpleFontData* fontData) const
219 {
220     ASSERT(fontData->isCustomFont());
221     ASSERT(fontData->isSVGFont());
222
223     SVGFontFaceElement* fontFaceElement = this->svgFontFaceElement();
224     ASSERT(fontFaceElement);
225
226     SVGFontElement* fontElement = fontFaceElement->associatedFontElement();
227     ASSERT(fontElement);
228
229     if (bufferLength == length)
230         return fillBMPGlyphs(fontElement, pageToFill, offset, length, buffer, fontData);
231
232     ASSERT(bufferLength == 2 * length);
233     return fillNonBMPGlyphs(fontElement, pageToFill, offset, length, buffer, fontData);
234 }
235
236 bool SVGFontData::fillBMPGlyphs(SVGFontElement* fontElement, GlyphPage* pageToFill, unsigned offset, unsigned length, UChar* buffer, const SimpleFontData* fontData) const
237 {
238     bool haveGlyphs = false;
239     Vector<SVGGlyph> glyphs;
240     for (unsigned i = 0; i < length; ++i) {
241         String lookupString(buffer + i, 1);
242         fontElement->collectGlyphsForString(lookupString, glyphs);
243         if (glyphs.isEmpty()) {
244             pageToFill->setGlyphDataForIndex(offset + i, 0, 0);
245             continue;
246         }
247
248         // Associate entry in glyph page with first valid SVGGlyph.
249         // If there are multiple valid ones, just take the first one. WidthIterator will take
250         // care of matching to the correct glyph, if multiple ones are available, as that's
251         // only possible within the context of a string (eg. arabic form matching).
252         haveGlyphs = true;
253         pageToFill->setGlyphDataForIndex(offset + i, glyphs.first().tableEntry, fontData);
254         glyphs.clear();
255     }
256
257     return haveGlyphs;
258 }
259
260 bool SVGFontData::fillNonBMPGlyphs(SVGFontElement* fontElement, GlyphPage* pageToFill, unsigned offset, unsigned length, UChar* buffer, const SimpleFontData* fontData) const
261 {
262     bool haveGlyphs = false;
263     Vector<SVGGlyph> glyphs;
264     for (unsigned i = 0; i < length; ++i) {
265         // Each character here consists of a surrogate pair
266         String lookupString(buffer + i * 2, 2);
267         fontElement->collectGlyphsForString(lookupString, glyphs);
268         if (glyphs.isEmpty()) {
269             pageToFill->setGlyphDataForIndex(offset + i, 0, 0);
270             continue;
271         }
272
273         // Associate entry in glyph page with first valid SVGGlyph.
274         // If there are multiple valid ones, just take the first one. WidthIterator will take
275         // care of matching to the correct glyph, if multiple ones are available, as that's
276         // only possible within the context of a string (eg. arabic form matching).
277         haveGlyphs = true;
278         pageToFill->setGlyphDataForIndex(offset + i, glyphs.first().tableEntry, fontData);
279         glyphs.clear();
280     }
281
282     return haveGlyphs;
283 }
284
285 void computeNormalizedSpaces(const TextRun& run, bool mirror, String& normalizedSpacesStringCache)
286 {
287     if (normalizedSpacesStringCache.length() == static_cast<unsigned>(run.charactersLength()))
288         return;
289     if (run.is8Bit()) {
290         normalizedSpacesStringCache = String(run.data8(0), run.charactersLength());
291         normalizedSpacesStringCache = Font::normalizeSpaces(normalizedSpacesStringCache.characters8(), normalizedSpacesStringCache.length());
292     } else {
293         normalizedSpacesStringCache = String(run.data16(0), run.charactersLength());
294         normalizedSpacesStringCache = Font::normalizeSpaces(normalizedSpacesStringCache.characters16(), normalizedSpacesStringCache.length());
295     }
296     if (mirror)
297         normalizedSpacesStringCache = createStringWithMirroredCharacters(normalizedSpacesStringCache);
298 }
299
300 String createStringWithMirroredCharacters(StringView string)
301 {
302     unsigned length = string.length();
303     StringBuilder mirroredCharacters;
304     mirroredCharacters.reserveCapacity(length);
305     for (unsigned i = 0; i < length; ) {
306         UChar32 character;
307         U16_NEXT(string, i, length, character);
308         mirroredCharacters.append(u_charMirror(character));
309     }
310     return mirroredCharacters.toString();
311 }
312
313 } // namespace WebCore
314
315 #endif