Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

third_party/WebKit/Source/core/layout/LayoutBlockFlowLine.cpp

 /*
  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
  * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All right reserved.
  * Copyright (C) 2010 Google Inc. 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.
  *
@@ skipping 409 matching lines @@
         if (!runWithNextObject->m_lineLayoutItem.isOutOfFlowPositioned() && !runWithNextObject->m_box->isLineBreak()) {
             nextObject = runWithNextObject->m_lineLayoutItem.layoutObject();
             break;
         }
     }
     layoutRubyRun->getOverhang(lineInfo.isFirstLine(), layoutRubyRun->style()->isLeftToRightDirection() ? previousObject : nextObject, layoutRubyRun->style()->isLeftToRightDirection() ? nextObject : previousObject, startOverhang, endOverhang);
     setMarginStartForChild(*layoutRubyRun, LayoutUnit(-startOverhang));
     setMarginEndForChild(*layoutRubyRun, LayoutUnit(-endOverhang));
 }
 
+static inline size_t findWordMeasurement(LineLayoutText layoutText, int offset,
+    WordMeasurements& wordMeasurements, size_t lastIndex)
+{
+    // In LTR, lastIndex should match since the order of BidiRun (visual) and
+    // WordMeasurement (logical) are the same.
+    size_t size = wordMeasurements.size();
+    if (lastIndex < size) {
+        const WordMeasurement& wordMeasurement = wordMeasurements[lastIndex];
+        if (wordMeasurement.layoutText == layoutText && wordMeasurement.startOffset == offset)
+            return lastIndex;
+    }
+
+    // In RTL, scan the whole array because they are not the same.
+    for (size_t i = 0; i < size; ++i) {
+        const WordMeasurement& wordMeasurement = wordMeasurements[i];
+        if (wordMeasurement.layoutText != layoutText)
+            continue;
+        if (wordMeasurement.startOffset == offset)
+            return i;
+        if (wordMeasurement.startOffset > offset)
+            break;
+    }
+
+    // In RTL with space collpasing or in LTR/RTL mixed lines, there can be no
+    // matches because spaces are handled differently in BidiRun and
+    // WordMeasurement. This can cause slight performance hit and slight
+    // differences in glyph positions since we re-measure the whole run.
+    return size;
+}
+
 static inline void setLogicalWidthForTextRun(RootInlineBox* lineBox, BidiRun* run, LineLayoutText layoutText, LayoutUnit xPos, const LineInfo& lineInfo,
-    GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
+    GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements,
+    size_t& wordMeasurementsIndex)
 {
     HashSet<const SimpleFontData*> fallbackFonts;
     GlyphOverflow glyphOverflow;
 
     const Font& font = layoutText.style(lineInfo.isFirstLine())->font();
 
     LayoutUnit hyphenWidth;
     if (toInlineTextBox(run->m_box)->hasHyphen())
         hyphenWidth = LayoutUnit(layoutText.hyphenWidth(font, run->direction()));
 
     float measuredWidth = 0;
     FloatRect glyphBounds;
 
     bool kerningIsEnabled = font.getFontDescription().getTypesettingFeatures() & Kerning;
 
 #if OS(MACOSX)
     // FIXME: Having any font feature settings enabled can lead to selection gaps on
     // Chromium-mac. https://bugs.webkit.org/show_bug.cgi?id=113418
     bool canUseCachedWordMeasurements = font.canShapeWordByWord() && !font.getFontDescription().featureSettings();
 #else
     bool canUseCachedWordMeasurements = font.canShapeWordByWord();
 #endif
 
     if (canUseCachedWordMeasurements) {
         int lastEndOffset = run->m_start;
-        for (size_t i = 0, size = wordMeasurements.size(); i < size && lastEndOffset < run->m_stop; ++i) {
+        size_t i = findWordMeasurement(layoutText, lastEndOffset, wordMeasurements, wordMeasurementsIndex);
+        for (size_t size = wordMeasurements.size(); i < size && lastEndOffset < run->m_stop; ++i) {
             const WordMeasurement& wordMeasurement = wordMeasurements[i];
             if (wordMeasurement.startOffset == wordMeasurement.endOffset)
                 continue;
             if (wordMeasurement.layoutText != layoutText || wordMeasurement.startOffset != lastEndOffset || wordMeasurement.endOffset > run->m_stop)
-                continue;
+                break;
 
             lastEndOffset = wordMeasurement.endOffset;
             if (kerningIsEnabled && lastEndOffset == run->m_stop) {
                 int wordLength = lastEndOffset - wordMeasurement.startOffset;
                 measuredWidth += layoutText.width(wordMeasurement.startOffset, wordLength, xPos, run->direction(), lineInfo.isFirstLine());
                 if (i > 0 && wordLength == 1 && layoutText.characterAt(wordMeasurement.startOffset) == ' ')
                     measuredWidth += layoutText.style()->wordSpacing();
             } else {
                 FloatRect wordGlyphBounds = wordMeasurement.glyphBounds;
                 wordGlyphBounds.move(measuredWidth, 0);
                 glyphBounds.unite(wordGlyphBounds);
                 measuredWidth += wordMeasurement.width;
             }
             if (!wordMeasurement.fallbackFonts.isEmpty()) {
                 HashSet<const SimpleFontData*>::const_iterator end = wordMeasurement.fallbackFonts.end();
                 for (HashSet<const SimpleFontData*>::const_iterator it = wordMeasurement.fallbackFonts.begin(); it != end; ++it)
                     fallbackFonts.add(*it);
             }
         }
+        wordMeasurementsIndex = i;
         if (lastEndOffset != run->m_stop) {
             // If we don't have enough cached data, we'll measure the run again.
             canUseCachedWordMeasurements = false;
             fallbackFonts.clear();
         }
     }
 
     // Don't put this into 'else' part of the above 'if' because canUseCachedWordMeasurements may be modified in the 'if' block.
     if (!canUseCachedWordMeasurements)
         measuredWidth = layoutText.width(run->m_start, run->m_stop - run->m_start, xPos, run->direction(), lineInfo.isFirstLine(), &fallbackFonts, &glyphBounds);
@@ skipping 121 matching lines @@
     WordMeasurements& wordMeasurements)
 {
     bool needsWordSpacing = true;
     LayoutUnit totalLogicalWidth = lineBox->getFlowSpacingLogicalWidth();
     bool isAfterExpansion = true;
     ExpansionOpportunities expansions;
     LayoutObject* previousObject = nullptr;
     TextJustify textJustify = style()->getTextJustify();
 
     BidiRun* r = firstRun;
+    size_t wordMeasurementsIndex = 0;
     for (; r; r = r->next()) {
         if (!r->m_box || r->m_lineLayoutItem.isOutOfFlowPositioned() || r->m_box->isLineBreak()) {
             continue; // Positioned objects are only participating to figure out their
                 // correct static x position.  They have no effect on the width.
                 // Similarly, line break boxes have no effect on the width.
         }
         if (r->m_lineLayoutItem.isText()) {
             LineLayoutText rt(r->m_lineLayoutItem);
             if (textAlign == JUSTIFY && r != trailingSpaceRun && textJustify != TextJustifyNone) {
                 if (!isAfterExpansion)
                     toInlineTextBox(r->m_box)->setCanHaveLeadingExpansion(true);
                 expansions.addRunWithExpansions(*r, isAfterExpansion, textJustify);
             }
 
             if (rt.textLength()) {
                 if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt.characterAt(r->m_start)))
                     totalLogicalWidth += rt.style(lineInfo.isFirstLine())->font().getFontDescription().wordSpacing();
                 needsWordSpacing = !isSpaceOrNewline(rt.characterAt(r->m_stop - 1));
             }
 
-            setLogicalWidthForTextRun(lineBox, r, rt, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache, wordMeasurements);
+            setLogicalWidthForTextRun(lineBox, r, rt, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache, wordMeasurements, wordMeasurementsIndex);
         } else {
             isAfterExpansion = false;
             if (!r->m_lineLayoutItem.isLayoutInline()) {
                 LayoutBox* layoutBox = toLayoutBox(r->m_lineLayoutItem.layoutObject());
                 if (layoutBox->isRubyRun())
                     setMarginsForRubyRun(r, toLayoutRubyRun(layoutBox), previousObject, lineInfo);
                 r->m_box->setLogicalWidth(logicalWidthForChild(*layoutBox));
                 totalLogicalWidth += marginStartForChild(*layoutBox) + marginEndForChild(*layoutBox);
                 needsWordSpacing = true;
             }
@@ skipping 1427 matching lines @@
 bool LayoutBlockFlow::paintedOutputOfObjectHasNoEffectRegardlessOfSize() const
 {
     // LayoutBlockFlow is in charge of paint invalidation of the first line.
     if (firstLineBox())
         return false;
 
     return LayoutBlock::paintedOutputOfObjectHasNoEffectRegardlessOfSize();
 }
 
 } // namespace blink