Laying out a TextRun using an SVG font is O(n^2)
[WebKit-https.git] / Source / WebCore / platform / graphics / WidthIterator.cpp
1 /*
2  * Copyright (C) 2003, 2006, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
3  * Copyright (C) 2008 Holger Hans Peter Freyther
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB.  If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  *
20  */
21
22 #include "config.h"
23 #include "WidthIterator.h"
24
25 #include "Font.h"
26 #include "GlyphBuffer.h"
27 #include "Latin1TextIterator.h"
28 #include "SimpleFontData.h"
29 #include "SurrogatePairAwareTextIterator.h"
30 #include <wtf/MathExtras.h>
31
32 using namespace WTF;
33 using namespace Unicode;
34
35 namespace WebCore {
36
37 WidthIterator::WidthIterator(const Font* font, const TextRun& run, HashSet<const SimpleFontData*>* fallbackFonts, bool accountForGlyphBounds, bool forTextEmphasis)
38     : m_font(font)
39     , m_run(run)
40     , m_currentCharacter(0)
41     , m_runWidthSoFar(0)
42     , m_isAfterExpansion(!run.allowsLeadingExpansion())
43     , m_finalRoundingWidth(0)
44     , m_typesettingFeatures(font->typesettingFeatures())
45     , m_fallbackFonts(fallbackFonts)
46     , m_accountForGlyphBounds(accountForGlyphBounds)
47     , m_maxGlyphBoundingBoxY(std::numeric_limits<float>::min())
48     , m_minGlyphBoundingBoxY(std::numeric_limits<float>::max())
49     , m_firstGlyphOverflow(0)
50     , m_lastGlyphOverflow(0)
51     , m_forTextEmphasis(forTextEmphasis)
52 {
53     // If the padding is non-zero, count the number of spaces in the run
54     // and divide that by the padding for per space addition.
55     m_expansion = m_run.expansion();
56     if (!m_expansion)
57         m_expansionPerOpportunity = 0;
58     else {
59         bool isAfterExpansion = m_isAfterExpansion;
60         unsigned expansionOpportunityCount = m_run.is8Bit() ? Font::expansionOpportunityCount(m_run.characters8(), m_run.length(), m_run.ltr() ? LTR : RTL, isAfterExpansion) : Font::expansionOpportunityCount(m_run.characters16(), m_run.length(), m_run.ltr() ? LTR : RTL, isAfterExpansion);
61         if (isAfterExpansion && !m_run.allowsTrailingExpansion())
62             expansionOpportunityCount--;
63
64         if (!expansionOpportunityCount)
65             m_expansionPerOpportunity = 0;
66         else
67             m_expansionPerOpportunity = m_expansion / expansionOpportunityCount;
68     }
69 }
70
71 GlyphData WidthIterator::glyphDataForCharacter(UChar32 character, bool mirror, int currentCharacter, unsigned& advanceLength, String& normalizedSpacesStringCache)
72 {
73     ASSERT(m_font);
74
75 #if ENABLE(SVG_FONTS)
76     if (TextRun::RenderingContext* renderingContext = m_run.renderingContext())
77         return renderingContext->glyphDataForCharacter(*m_font, *this, character, mirror, currentCharacter, advanceLength, normalizedSpacesStringCache);
78 #else
79     UNUSED_PARAM(currentCharacter);
80     UNUSED_PARAM(advanceLength);
81 #endif
82
83     return m_font->glyphDataForCharacter(character, mirror);
84 }
85
86 struct OriginalAdvancesForCharacterTreatedAsSpace {
87 public:
88     OriginalAdvancesForCharacterTreatedAsSpace(bool isSpace, float advanceBefore, float advanceAt)
89         : characterIsSpace(isSpace)
90         , advanceBeforeCharacter(advanceBefore)
91         , advanceAtCharacter(advanceAt)
92     {
93     }
94
95     bool characterIsSpace;
96     float advanceBeforeCharacter;
97     float advanceAtCharacter;
98 };
99
100 typedef Vector<std::pair<int, OriginalAdvancesForCharacterTreatedAsSpace>, 64> CharactersTreatedAsSpace;
101
102 static inline float applyFontTransforms(GlyphBuffer* glyphBuffer, bool ltr, int& lastGlyphCount, const SimpleFontData* fontData, WidthIterator& iterator, TypesettingFeatures typesettingFeatures, CharactersTreatedAsSpace& charactersTreatedAsSpace)
103 {
104     ASSERT(typesettingFeatures & (Kerning | Ligatures));
105
106     if (!glyphBuffer)
107         return 0;
108
109     int glyphBufferSize = glyphBuffer->size();
110     if (glyphBuffer->size() <= lastGlyphCount + 1)
111         return 0;
112
113     GlyphBufferAdvance* advances = glyphBuffer->advances(0);
114     float widthDifference = 0;
115     for (int i = lastGlyphCount; i < glyphBufferSize; ++i)
116         widthDifference -= advances[i].width();
117
118     if (!ltr)
119         glyphBuffer->reverse(lastGlyphCount, glyphBufferSize - lastGlyphCount);
120
121 #if !ENABLE(SVG_FONTS)
122     UNUSED_PARAM(iterator);
123 #else
124     // We need to handle transforms on SVG fonts internally, since they are rendered internally.
125     if (fontData->isSVGFont()) {
126         // SVG font ligatures are handled during glyph selection, only kerning remaining.
127         if (iterator.run().renderingContext() && (typesettingFeatures & Kerning)) {
128             // FIXME: We could pass the necessary context down to this level so we can lazily create rendering contexts at this point.
129             // However, a larger refactoring of SVG fonts might necessary to sidestep this problem completely.
130             iterator.run().renderingContext()->applySVGKerning(fontData, iterator, glyphBuffer, lastGlyphCount);
131         }
132     } else
133 #endif
134         fontData->applyTransforms(glyphBuffer->glyphs(lastGlyphCount), advances + lastGlyphCount, glyphBufferSize - lastGlyphCount, typesettingFeatures);
135
136     if (!ltr)
137         glyphBuffer->reverse(lastGlyphCount, glyphBufferSize - lastGlyphCount);
138
139     for (size_t i = 0; i < charactersTreatedAsSpace.size(); ++i) {
140         int spaceOffset = charactersTreatedAsSpace[i].first;
141         const OriginalAdvancesForCharacterTreatedAsSpace& originalAdvances = charactersTreatedAsSpace[i].second;
142         if (spaceOffset && !originalAdvances.characterIsSpace)
143             glyphBuffer->advances(spaceOffset - 1)->setWidth(originalAdvances.advanceBeforeCharacter);
144         glyphBuffer->advances(spaceOffset)->setWidth(originalAdvances.advanceAtCharacter);
145     }
146     charactersTreatedAsSpace.clear();
147
148     for (int i = lastGlyphCount; i < glyphBufferSize; ++i)
149         widthDifference += advances[i].width();
150
151     lastGlyphCount = glyphBufferSize;
152     return widthDifference;
153 }
154
155 template <typename TextIterator>
156 inline unsigned WidthIterator::advanceInternal(TextIterator& textIterator, GlyphBuffer* glyphBuffer)
157 {
158     bool rtl = m_run.rtl();
159     bool hasExtraSpacing = (m_font->letterSpacing() || m_font->wordSpacing() || m_expansion) && !m_run.spacingDisabled();
160
161     float widthSinceLastRounding = m_runWidthSoFar;
162     m_runWidthSoFar = floorf(m_runWidthSoFar);
163     widthSinceLastRounding -= m_runWidthSoFar;
164
165     float lastRoundingWidth = m_finalRoundingWidth;
166     FloatRect bounds;
167
168     const SimpleFontData* primaryFont = m_font->primaryFont();
169     const SimpleFontData* lastFontData = primaryFont;
170     int lastGlyphCount = glyphBuffer ? glyphBuffer->size() : 0;
171
172     UChar32 character = 0;
173     unsigned clusterLength = 0;
174     CharactersTreatedAsSpace charactersTreatedAsSpace;
175     String normalizedSpacesStringCache;
176     while (textIterator.consume(character, clusterLength)) {
177         unsigned advanceLength = clusterLength;
178         int currentCharacter = textIterator.currentCharacter();
179         const GlyphData& glyphData = glyphDataForCharacter(character, rtl, currentCharacter, advanceLength, normalizedSpacesStringCache);
180         Glyph glyph = glyphData.glyph;
181         const SimpleFontData* fontData = glyphData.fontData;
182
183         ASSERT(fontData);
184
185         // Now that we have a glyph and font data, get its width.
186         float width;
187         if (character == '\t' && m_run.allowTabs())
188             width = m_font->tabWidth(*fontData, m_run.tabSize(), m_run.xPos() + m_runWidthSoFar + widthSinceLastRounding);
189         else {
190             width = fontData->widthForGlyph(glyph);
191
192             // SVG uses horizontalGlyphStretch(), when textLength is used to stretch/squeeze text.
193             width *= m_run.horizontalGlyphStretch();
194
195             // We special case spaces in two ways when applying word rounding.
196             // First, we round spaces to an adjusted width in all fonts.
197             // Second, in fixed-pitch fonts we ensure that all characters that
198             // match the width of the space character have the same width as the space character.
199             if (m_run.applyWordRounding() && width == fontData->spaceWidth() && (fontData->pitch() == FixedPitch || glyph == fontData->spaceGlyph()))
200                 width = fontData->adjustedSpaceWidth();
201         }
202
203         if (fontData != lastFontData && width) {
204             if (shouldApplyFontTransforms()) {
205                 m_runWidthSoFar += applyFontTransforms(glyphBuffer, m_run.ltr(), lastGlyphCount, lastFontData, *this, m_typesettingFeatures, charactersTreatedAsSpace);
206                 lastGlyphCount = glyphBuffer->size(); // applyFontTransforms doesn't update when there had been only one glyph.
207             }
208
209             lastFontData = fontData;
210             if (m_fallbackFonts && fontData != primaryFont) {
211                 // FIXME: This does a little extra work that could be avoided if
212                 // glyphDataForCharacter() returned whether it chose to use a small caps font.
213                 if (!m_font->isSmallCaps() || character == u_toupper(character))
214                     m_fallbackFonts->add(fontData);
215                 else {
216                     const GlyphData& uppercaseGlyphData = m_font->glyphDataForCharacter(u_toupper(character), rtl);
217                     if (uppercaseGlyphData.fontData != primaryFont)
218                         m_fallbackFonts->add(uppercaseGlyphData.fontData);
219                 }
220             }
221         }
222
223         if (hasExtraSpacing) {
224             // Account for letter-spacing.
225             if (width && m_font->letterSpacing())
226                 width += m_font->letterSpacing();
227
228             static bool expandAroundIdeographs = Font::canExpandAroundIdeographsInComplexText();
229             bool treatAsSpace = Font::treatAsSpace(character);
230             if (treatAsSpace || (expandAroundIdeographs && Font::isCJKIdeographOrSymbol(character))) {
231                 // Distribute the run's total expansion evenly over all expansion opportunities in the run.
232                 if (m_expansion) {
233                     float previousExpansion = m_expansion;
234                     if (!treatAsSpace && !m_isAfterExpansion) {
235                         // Take the expansion opportunity before this ideograph.
236                         m_expansion -= m_expansionPerOpportunity;
237                         float expansionAtThisOpportunity = !m_run.applyWordRounding() ? m_expansionPerOpportunity : roundf(previousExpansion) - roundf(m_expansion);
238                         m_runWidthSoFar += expansionAtThisOpportunity;
239                         if (glyphBuffer) {
240                             if (glyphBuffer->isEmpty()) {
241                                 if (m_forTextEmphasis)
242                                     glyphBuffer->add(fontData->zeroWidthSpaceGlyph(), fontData, m_expansionPerOpportunity, currentCharacter);
243                                 else
244                                     glyphBuffer->add(fontData->spaceGlyph(), fontData, expansionAtThisOpportunity, currentCharacter);
245                             } else
246                                 glyphBuffer->expandLastAdvance(expansionAtThisOpportunity);
247                         }
248                         previousExpansion = m_expansion;
249                     }
250                     if (m_run.allowsTrailingExpansion() || (m_run.ltr() && currentCharacter + advanceLength < static_cast<size_t>(m_run.length()))
251                         || (m_run.rtl() && currentCharacter)) {
252                         m_expansion -= m_expansionPerOpportunity;
253                         width += !m_run.applyWordRounding() ? m_expansionPerOpportunity : roundf(previousExpansion) - roundf(m_expansion);
254                         m_isAfterExpansion = true;
255                     }
256                 } else
257                     m_isAfterExpansion = false;
258
259                 // Account for word spacing.
260                 // We apply additional space between "words" by adding width to the space character.
261                 if (treatAsSpace && (character != '\t' || !m_run.allowTabs()) && (currentCharacter || character == noBreakSpace) && m_font->wordSpacing())
262                     width += m_font->wordSpacing();
263             } else
264                 m_isAfterExpansion = false;
265         }
266
267         if (shouldApplyFontTransforms() && glyphBuffer && Font::treatAsSpace(character))
268             charactersTreatedAsSpace.append(std::make_pair(glyphBuffer->size(),
269                 OriginalAdvancesForCharacterTreatedAsSpace(character == ' ', glyphBuffer->size() ? glyphBuffer->advanceAt(glyphBuffer->size() - 1).width() : 0, width)));
270
271         if (m_accountForGlyphBounds) {
272             bounds = fontData->boundsForGlyph(glyph);
273             if (!currentCharacter)
274                 m_firstGlyphOverflow = std::max<float>(0, -bounds.x());
275         }
276
277         if (m_forTextEmphasis && !Font::canReceiveTextEmphasis(character))
278             glyph = 0;
279
280         // Advance past the character we just dealt with.
281         textIterator.advance(advanceLength);
282
283         float oldWidth = width;
284
285         // Force characters that are used to determine word boundaries for the rounding hack
286         // to be integer width, so following words will start on an integer boundary.
287         if (m_run.applyWordRounding() && Font::isRoundingHackCharacter(character)) {
288             width = ceilf(width);
289
290             // Since widthSinceLastRounding can lose precision if we include measurements for
291             // preceding whitespace, we bypass it here.
292             m_runWidthSoFar += width;
293
294             // Since this is a rounding hack character, we should have reset this sum on the previous
295             // iteration.
296             ASSERT(!widthSinceLastRounding);
297         } else {
298             // Check to see if the next character is a "rounding hack character", if so, adjust
299             // width so that the total run width will be on an integer boundary.
300             if ((m_run.applyWordRounding() && textIterator.currentCharacter() < m_run.length() && Font::isRoundingHackCharacter(*(textIterator.characters())))
301                 || (m_run.applyRunRounding() && textIterator.currentCharacter() >= m_run.length())) {
302                 float totalWidth = widthSinceLastRounding + width;
303                 widthSinceLastRounding = ceilf(totalWidth);
304                 width += widthSinceLastRounding - totalWidth;
305                 m_runWidthSoFar += widthSinceLastRounding;
306                 widthSinceLastRounding = 0;
307             } else
308                 widthSinceLastRounding += width;
309         }
310
311         if (glyphBuffer)
312             glyphBuffer->add(glyph, fontData, (rtl ? oldWidth + lastRoundingWidth : width), currentCharacter);
313
314         lastRoundingWidth = width - oldWidth;
315
316         if (m_accountForGlyphBounds) {
317             m_maxGlyphBoundingBoxY = std::max(m_maxGlyphBoundingBoxY, bounds.maxY());
318             m_minGlyphBoundingBoxY = std::min(m_minGlyphBoundingBoxY, bounds.y());
319             m_lastGlyphOverflow = std::max<float>(0, bounds.maxX() - width);
320         }
321     }
322
323     if (shouldApplyFontTransforms())
324         m_runWidthSoFar += applyFontTransforms(glyphBuffer, m_run.ltr(), lastGlyphCount, lastFontData, *this, m_typesettingFeatures, charactersTreatedAsSpace);
325
326     unsigned consumedCharacters = textIterator.currentCharacter() - m_currentCharacter;
327     m_currentCharacter = textIterator.currentCharacter();
328     m_runWidthSoFar += widthSinceLastRounding;
329     m_finalRoundingWidth = lastRoundingWidth;
330     return consumedCharacters;
331 }
332
333 unsigned WidthIterator::advance(int offset, GlyphBuffer* glyphBuffer)
334 {
335     int length = m_run.length();
336
337     if (offset > length)
338         offset = length;
339
340     if (m_currentCharacter >= static_cast<unsigned>(offset))
341         return 0;
342
343     if (m_run.is8Bit()) {
344         Latin1TextIterator textIterator(m_run.data8(m_currentCharacter), m_currentCharacter, offset, length);
345         return advanceInternal(textIterator, glyphBuffer);
346     }
347
348     SurrogatePairAwareTextIterator textIterator(m_run.data16(m_currentCharacter), m_currentCharacter, offset, length);
349     return advanceInternal(textIterator, glyphBuffer);
350 }
351
352 bool WidthIterator::advanceOneCharacter(float& width, GlyphBuffer& glyphBuffer)
353 {
354     int oldSize = glyphBuffer.size();
355     advance(m_currentCharacter + 1, &glyphBuffer);
356     float w = 0;
357     for (int i = oldSize; i < glyphBuffer.size(); ++i)
358         w += glyphBuffer.advanceAt(i).width();
359     width = w;
360     return glyphBuffer.size() > oldSize;
361 }
362
363 }