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

Index: third_party/WebKit/Source/core/layout/svg/SVGTextMetricsBuilder.cpp
diff --git a/third_party/WebKit/Source/core/layout/svg/SVGTextMetricsBuilder.cpp b/third_party/WebKit/Source/core/layout/svg/SVGTextMetricsBuilder.cpp
index 70d014dc02e049924f22a7c7bea94715a1f0f413..bef4f03291d7b9b234d3885eaff9978d6b1e28a7 100644
--- a/third_party/WebKit/Source/core/layout/svg/SVGTextMetricsBuilder.cpp
+++ b/third_party/WebKit/Source/core/layout/svg/SVGTextMetricsBuilder.cpp
@@ -24,8 +24,7 @@
 #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"
@@ -41,34 +40,52 @@ 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[m_currentPosition]) && m_currentPosition + 1 < characterCount() && U16_IS_TRAIL(m_run[m_currentPosition + 1]);
+    }
+    bool currentCharacterIsWhiteSpace() const
     {
-        return U16_IS_LEAD(m_run[textPosition]) && textPosition + 1 < textLength() && U16_IS_TRAIL(m_run[textPosition + 1]);
+        return m_run[m_currentPosition] == ' ';
     }
-    bool characterIsWhiteSpace(unsigned textPosition) const
+    unsigned characterCount() const
     {
-        return m_run[textPosition] == ' ';
+        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;
-    BidiCharacterRun* m_bidiRun;
     TextRun m_run;
+
+    BidiCharacterRun* m_bidiRun;
     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_bidiRun(nullptr)
+    : m_currentPosition(0)
+    , m_text(LineLayoutSVGInlineText(text))
     , m_run(SVGTextMetrics::constructTextRun(m_text, 0, m_text.textLength(), m_text.styleRef().direction()))
-    , m_totalWidth(0)
+    , m_bidiRun(nullptr)
 {
     setupBidiRuns();
 }
@@ -81,11 +98,8 @@ SVGTextMetricsCalculator::~SVGTextMetricsCalculator()
 
 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);
@@ -97,36 +111,57 @@ void SVGTextMetricsCalculator::setupBidiRuns()
     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 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);
+
+        // 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;
+            }
+        }
     }
 
-    unsigned metricsLength = characterStartsSurrogatePair(textPosition) ? 2 : 1;
-    SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(m_text, textPosition, metricsLength, m_textDirection);
-    ASSERT(metrics.length() == metricsLength);
-
-    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);
-
-    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 {
@@ -155,47 +190,46 @@ static void measureTextLayoutObject(LayoutSVGInlineText* text, MeasureTextData*
             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)