Update SVG text layout to use shaped glyph data & go fast (O(n^2)->O(n))

third_party/WebKit/Source/core/layout/svg/SVGTextMetricsBuilder.cpp

 /*
  * Copyright (C) Research In Motion Limited 2010-2012. All rights reserved.
  *
  * 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.
  */
 
 #include "core/layout/svg/SVGTextMetricsBuilder.h"
 
 #include "core/layout/api/LineLayoutSVGInlineText.h"
 #include "core/layout/svg/LayoutSVGInline.h"
 #include "core/layout/svg/LayoutSVGInlineText.h"
 #include "core/layout/svg/LayoutSVGText.h"
 #include "core/layout/svg/SVGTextMetrics.h"
-#include "platform/fonts/GlyphBuffer.h"
-#include "platform/fonts/shaping/SimpleShaper.h"
+#include "platform/fonts/CharacterRange.h"
 #include "platform/text/BidiCharacterRun.h"
 #include "platform/text/BidiResolver.h"
 #include "platform/text/TextDirection.h"
 #include "platform/text/TextPath.h"
 #include "platform/text/TextRun.h"
 #include "platform/text/TextRunIterator.h"
 #include "wtf/Vector.h"
 
 namespace blink {
 
 class SVGTextMetricsCalculator {
 public:
     SVGTextMetricsCalculator(LayoutSVGInlineText*);
     ~SVGTextMetricsCalculator();
 
-    SVGTextMetrics computeMetricsForCharacter(unsigned textPosition);
-    unsigned textLength() const { return static_cast<unsigned>(m_run.charactersLength()); }
+    bool advancePosition();
+    unsigned currentPosition() const { return m_currentPosition; }
 
-    bool characterStartsSurrogatePair(unsigned textPosition) const
+    SVGTextMetrics currentCharacterMetrics();
+
+    // TODO(pdr): The surrogate pair concept should be refactored to a single

[fs, 2016/03/09 11:31:44]

I think we should rather strive to move in the direction of using something more
resembling a "typographic character unit"
(https://drafts.csswg.org/css-text-3/#typographic-character-unit), and hopefully
not need to care about surrogates or not. (Currently the only reason for this is
because of the x/y/dx/dy indexing using "glyphs" - and using TCUs would be even
better and more correct.)

[pdr., 2016/03/10 04:55:15]

Nice! I didn't know the name for this. I've rewritten this comment and filed a
separate bug (https://crbug.com/593570) because this is a pretty large project.

+    // place to hide this complexity.
+    bool currentCharacterStartsSurrogatePair() const
     {
-        return U16_IS_LEAD(m_run[textPosition]) && textPosition + 1 < textLength() && U16_IS_TRAIL(m_run[textPosition + 1]);
+        return U16_IS_LEAD(m_run[m_currentPosition]) && m_currentPosition + 1 < characterCount() && U16_IS_TRAIL(m_run[m_currentPosition + 1]);
     }
-    bool characterIsWhiteSpace(unsigned textPosition) const
+    bool currentCharacterIsWhiteSpace() const
     {
-        return m_run[textPosition] == ' ';
+        return m_run[m_currentPosition] == ' ';
+    }
+    unsigned characterCount() const
+    {
+        return static_cast<unsigned>(m_run.charactersLength());
     }
 
 private:
     void setupBidiRuns();
 
+    // Ensure |m_subrunRanges| is updated for the current bidi run, or the
+    // complete m_run if no bidi runs are present. Returns the current position
+    // in the subrun which can be used to index into |m_subrunRanges|.
+    unsigned updateSubrunRangesForCurrentPosition();
+
+    // Current character position in m_text.
+    unsigned m_currentPosition;
+
     LineLayoutSVGInlineText m_text;
+    TextRun m_run;
+
     BidiCharacterRun* m_bidiRun;
-    TextRun m_run;
     BidiResolver<TextRunIterator, BidiCharacterRun> m_bidiResolver;
-    float m_totalWidth;
-    TextDirection m_textDirection;
+
+    // Ranges for the current bidi run if present, or the entire run otherwise.
+    Vector<CharacterRange> m_subrunRanges;
 };
 
 SVGTextMetricsCalculator::SVGTextMetricsCalculator(LayoutSVGInlineText* text)
-    : m_text(LineLayoutSVGInlineText(text))
+    : m_currentPosition(0)
+    , m_text(LineLayoutSVGInlineText(text))
+    , m_run(SVGTextMetrics::constructTextRun(m_text, 0, m_text.textLength(), m_text.styleRef().direction()))
     , m_bidiRun(nullptr)
-    , m_run(SVGTextMetrics::constructTextRun(m_text, 0, m_text.textLength(), m_text.styleRef().direction()))
-    , m_totalWidth(0)
 {
     setupBidiRuns();
 }
 
 SVGTextMetricsCalculator::~SVGTextMetricsCalculator()
 {
     if (m_bidiRun)
         m_bidiResolver.runs().deleteRuns();
 }
 
 void SVGTextMetricsCalculator::setupBidiRuns()
 {
-    const ComputedStyle& style = m_text.styleRef();
-    m_textDirection = style.direction();
-    if (isOverride(style.unicodeBidi()))
+    if (isOverride(m_text.styleRef().unicodeBidi()))
         return;
-
     BidiStatus status(LTR, false);
     status.last = status.lastStrong = WTF::Unicode::OtherNeutral;
     m_bidiResolver.setStatus(status);
     m_bidiResolver.setPositionIgnoringNestedIsolates(TextRunIterator(&m_run, 0));
     const bool hardLineBreak = false;
     const bool reorderRuns = false;
     m_bidiResolver.createBidiRunsForLine(TextRunIterator(&m_run, m_run.length()), NoVisualOverride, hardLineBreak, reorderRuns);
     BidiRunList<BidiCharacterRun>& bidiRuns = m_bidiResolver.runs();
     m_bidiRun = bidiRuns.firstRun();
 }
 
-SVGTextMetrics SVGTextMetricsCalculator::computeMetricsForCharacter(unsigned textPosition)
+bool SVGTextMetricsCalculator::advancePosition()
+{
+    m_currentPosition += currentCharacterStartsSurrogatePair() ? 2 : 1;
+    return m_currentPosition < characterCount();
+}
+
+unsigned SVGTextMetricsCalculator::updateSubrunRangesForCurrentPosition()
 {
     if (m_bidiRun) {
-        if (textPosition >= static_cast<unsigned>(m_bidiRun->stop())) {
+        if (m_currentPosition >= static_cast<unsigned>(m_bidiRun->stop())) {
             m_bidiRun = m_bidiRun->next();
-            // New BiDi run means new reference position for measurements, so reset |m_totalWidth|.
-            m_totalWidth = 0;
+            // Ensure new subrange ranges are computed below.
+            m_subrunRanges.clear();
         }
         ASSERT(m_bidiRun);
-        ASSERT(static_cast<int>(textPosition) < m_bidiRun->stop());
-        m_textDirection = m_bidiRun->direction();
+        ASSERT(static_cast<int>(m_currentPosition) < m_bidiRun->stop());
     }
 
-    unsigned metricsLength = characterStartsSurrogatePair(textPosition) ? 2 : 1;
-    SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(m_text, textPosition, metricsLength, m_textDirection);
-    ASSERT(metrics.length() == metricsLength);
+    unsigned positionInRun = m_bidiRun ? m_currentPosition - m_bidiRun->start() : m_currentPosition;
+    if (positionInRun >= m_subrunRanges.size()) {
+        unsigned subrunStart = m_bidiRun ? m_bidiRun->start() : 0;
+        unsigned subrunEnd = m_bidiRun ? m_bidiRun->stop() : m_run.charactersLength();
+        TextDirection subrunDirection = m_bidiRun ? m_bidiRun->direction() : m_text.styleRef().direction();
+        TextRun subRun = SVGTextMetrics::constructTextRun(m_text, subrunStart, subrunEnd - subrunStart, subrunDirection);
+        m_subrunRanges = m_text.scaledFont().individualCharacterRanges(subRun, 0, subRun.length() - 1);
 
-    unsigned startPosition = m_bidiRun ? m_bidiRun->start() : 0;
-    ASSERT(startPosition <= textPosition);
-    SVGTextMetrics complexStartToCurrentMetrics = SVGTextMetrics::measureCharacterRange(m_text, startPosition, textPosition - startPosition + metricsLength, m_textDirection);
-    // Frequent case for Arabic text: when measuring a single character the arabic isolated form is taken
-    // when laying out the glyph "in context" (with it's surrounding characters) it changes due to shaping.
-    // So whenever currentWidth != currentMetrics.width(), we are processing a text run whose length is
-    // not equal to the sum of the individual lengths of the glyphs, when measuring them isolated.
-    float currentWidth = complexStartToCurrentMetrics.width() - m_totalWidth;
-    if (currentWidth != metrics.width())
-        metrics.setWidth(currentWidth);
+        // TODO(pdr): Our font APIs currently only have per-glyph data so we
+        // need to synthesize per-grapheme data. For example, if 'fi' is shaped
+        // into a single glyph, we do not have access to the 'i' position. The
+        // code below synthesizes a position when two characters share the same

[fs, 2016/03/09 11:31:44]

Well technically "two or more" (i.e ligatures like 'ffi' and 'ffl'). The code
below doesn't deal with that though. I don't know what result you'll get for
diacritics, but hopefullly they won't have width == 0.

[pdr., 2016/03/10 04:55:15]

+1, good catch. I've ffixed this loop and added a test
(svg/text/ligature-queries.html).

The loop will still incorrectly split combining diacritic markers though. I
think this is better than not splitting fi and ffi since combining diacritic
markers seem more rare (english-centrism... :/). This is only for combining
diacritics so Söderquist with a single-character ö is safe. FWIW, Firefox takes
the opposite approach and shows overlapping glyphs for ffi. With a little extra
glyph data out of HarfBuzz, I think we'll be able to fix this with
https://crbug.com/473476.

[pdr., 2016/03/10 07:21:48]

I looked at this some more and we're violating the spec by not using combined
glyphs like Firefox. I'll request clarification from the SVGWG but I'd like to
continue with the approach here for now.

[fs, 2016/03/10 09:55:57]

Yes, it more common for us weird people with diacritics to write the composed
form - we could as well use the decomposed form though =).
Yeah, I think even the early revisions of the spec somehow spelled out cases
like ligatures wrt 'x'/'y' position et.c (and there are tests for it in the
official testsuite - text-text-<somenumber> - one of those with lots of blue
boxes, short red lines and other weird stuff.)

The new ("under construction" *insert GIF with digging person here*) text layout
algorithm, some parts of a TCU would be marked "middle":

https://svgwg.org/svg2-draft/text.html#TextLayoutAlgorithm

And for the record - I'm ok with a "small progressive steps" approach here, so
no need to get rid of all the old bagage at once.

+        // position. See: https://crbug.com/473476.
+        for (unsigned rangeIndex = m_subrunRanges.size() - 1; rangeIndex > 0; --rangeIndex) {
+            CharacterRange& currentRange = m_subrunRanges[rangeIndex];
+            CharacterRange& previousRange = m_subrunRanges[rangeIndex - 1];
+            if (currentRange.width() == 0 && previousRange.end == currentRange.start) {
+                float midpoint = (previousRange.end - previousRange.start) / 2;
+                previousRange.end = previousRange.start + midpoint;

[fs, 2016/03/09 11:31:44]

(previousRange.start + previousRange.end) / 2

for a slightly shorter version (with less FOPS; and * 0.5f even better =))

[pdr., 2016/03/10 04:55:15]

The new loop now requires a divide 😭

+                currentRange.start = previousRange.end;
+            }
+        }
+    }
 
-    m_totalWidth = complexStartToCurrentMetrics.width();
-    return metrics;
+    return positionInRun;
+}
+
+SVGTextMetrics SVGTextMetricsCalculator::currentCharacterMetrics()
+{
+    unsigned currentSubrunPosition = updateSubrunRangesForCurrentPosition();
+    unsigned length = currentCharacterStartsSurrogatePair() ? 2 : 1;
+    float width = m_subrunRanges[currentSubrunPosition].width();
+    return SVGTextMetrics(m_text, length, width);
 }
 
 struct MeasureTextData {
     MeasureTextData(SVGCharacterDataMap* characterDataMap)
         : allCharactersMap(characterDataMap)
         , lastCharacterWasWhiteSpace(true)
         , valueListPosition(0)
     {
     }
 
     SVGCharacterDataMap* allCharactersMap;
     bool lastCharacterWasWhiteSpace;
     unsigned valueListPosition;
 };
 
 static void measureTextLayoutObject(LayoutSVGInlineText* text, MeasureTextData* data, bool processLayoutObject)
 {
     ASSERT(text);
 
     SVGTextLayoutAttributes* attributes = text->layoutAttributes();
     Vector<SVGTextMetrics>* textMetricsValues = &attributes->textMetricsValues();
     if (processLayoutObject) {
         if (data->allCharactersMap)
             attributes->clear();
         else
             textMetricsValues->clear();
     }
 
+    // TODO(pdr): This loop is too tightly coupled to SVGTextMetricsCalculator.

[fs, 2016/03/09 11:31:44]

Should we file a (separate) bug for this, or will it be handled in the one
referenced here? (It does sound like a good plan - should probably also create a
"dummy" BidiCharacterRun for the case where none are created currently.)

[pdr., 2016/03/10 04:55:15]

Yeah, I plan to do this one in a followup but wanted to keep this patch simple.

[fs, 2016/03/10 09:55:57]

Roger that.

+    // We should refactor SVGTextMetricsCalculator to be a simple bidi run
+    // iterator and move all subrun logic to a single function.
     SVGTextMetricsCalculator calculator(text);
     bool preserveWhiteSpace = text->style()->whiteSpace() == PRE;
     unsigned surrogatePairCharacters = 0;
     unsigned skippedCharacters = 0;
-    unsigned textPosition = 0;
-    unsigned textLength = calculator.textLength();
-
-    SVGTextMetrics currentMetrics;
-    for (; textPosition < textLength; textPosition += currentMetrics.length()) {
-        currentMetrics = calculator.computeMetricsForCharacter(textPosition);
-        if (!currentMetrics.length())
+    do {
+        SVGTextMetrics metrics = calculator.currentCharacterMetrics();
+        if (!metrics.length())
             break;
 
-        bool characterIsWhiteSpace = calculator.characterIsWhiteSpace(textPosition);
+        bool characterIsWhiteSpace = calculator.currentCharacterIsWhiteSpace();
         if (characterIsWhiteSpace && !preserveWhiteSpace && data->lastCharacterWasWhiteSpace) {
             if (processLayoutObject)
                 textMetricsValues->append(SVGTextMetrics(SVGTextMetrics::SkippedSpaceMetrics));
             if (data->allCharactersMap)
-                skippedCharacters += currentMetrics.length();
+                skippedCharacters += metrics.length();
             continue;
         }
 
         if (processLayoutObject) {
             if (data->allCharactersMap) {
-                const SVGCharacterDataMap::const_iterator it = data->allCharactersMap->find(data->valueListPosition + textPosition - skippedCharacters - surrogatePairCharacters + 1);
+                const SVGCharacterDataMap::const_iterator it = data->allCharactersMap->find(data->valueListPosition + calculator.currentPosition() - skippedCharacters - surrogatePairCharacters + 1);
                 if (it != data->allCharactersMap->end())
-                    attributes->characterDataMap().set(textPosition + 1, it->value);
+                    attributes->characterDataMap().set(calculator.currentPosition() + 1, it->value);
             }
-            textMetricsValues->append(currentMetrics);
+            textMetricsValues->append(metrics);
         }
 
-        if (data->allCharactersMap && calculator.characterStartsSurrogatePair(textPosition))
+        if (data->allCharactersMap && calculator.currentCharacterStartsSurrogatePair())
             surrogatePairCharacters++;
 
         data->lastCharacterWasWhiteSpace = characterIsWhiteSpace;
-    }
+    } while (calculator.advancePosition());
 
     if (!data->allCharactersMap)
         return;
 
-    data->valueListPosition += textPosition - skippedCharacters;
+    data->valueListPosition += calculator.currentPosition() - skippedCharacters;
 }
 
 static void walkTree(LayoutSVGText* start, LayoutSVGInlineText* stopAtLeaf, MeasureTextData* data)
 {
     LayoutObject* child = start->firstChild();
     while (child) {
         if (child->isSVGInlineText()) {
             LayoutSVGInlineText* text = toLayoutSVGInlineText(child);
             measureTextLayoutObject(text, data, !stopAtLeaf || stopAtLeaf == text);
             if (stopAtLeaf && stopAtLeaf == text)
@@ skipping 22 matching lines @@
 }
 
 void SVGTextMetricsBuilder::buildMetricsAndLayoutAttributes(LayoutSVGText* textRoot, LayoutSVGInlineText* stopAtLeaf, SVGCharacterDataMap& allCharactersMap)
 {
     ASSERT(textRoot);
     MeasureTextData data(&allCharactersMap);
     walkTree(textRoot, stopAtLeaf, &data);
 }
 
 } // namespace blink