Add a "logical query mode" to SVGTextQuery

Source/core/layout/svg/SVGTextQuery.cpp

Index: Source/core/layout/svg/SVGTextQuery.cpp
diff --git a/Source/core/layout/svg/SVGTextQuery.cpp b/Source/core/layout/svg/SVGTextQuery.cpp
index 490237a0386c0c4defe10d7ee1c2c110497d6082..8b63773d742ea3ef6d0a9a56f102c56c207deefe 100644
--- a/Source/core/layout/svg/SVGTextQuery.cpp
+++ b/Source/core/layout/svg/SVGTextQuery.cpp
@@ -37,14 +37,14 @@ namespace blink {
 struct QueryData {
     QueryData()
         : isVerticalText(false)
-        , processedCharacters(0)
+        , currentOffset(0)
         , textLayoutObject(0)
         , textBox(0)
     {
     }
 
     bool isVerticalText;
-    unsigned processedCharacters;
+    unsigned currentOffset;
     LayoutSVGInlineText* textLayoutObject;
     const SVGInlineTextBox* textBox;
 };
@@ -101,36 +101,70 @@ static void collectTextBoxesInFlowBox(InlineFlowBox* flowBox, Vector<SVGInlineTe
 
 typedef bool ProcessTextFragmentCallback(QueryData*, const SVGTextFragment&);
 
-static bool executeQuery(LayoutObject* queryRoot, QueryData* queryData, ProcessTextFragmentCallback fragmentCallback)
+static bool queryTextBox(QueryData* queryData, const SVGInlineTextBox* textBox, ProcessTextFragmentCallback fragmentCallback)
+{
+    queryData->textBox = textBox;
+    queryData->textLayoutObject = &toLayoutSVGInlineText(textBox->layoutObject());
+
+    queryData->isVerticalText = textBox->layoutObject().style()->svgStyle().isVerticalWritingMode();
+
+    // Loop over all text fragments in this text box, firing a callback for each.
+    for (const SVGTextFragment& fragment : textBox->textFragments()) {
+        if (fragmentCallback(queryData, fragment))
+            return true;
+    }
+    return false;
+}
+
+// Execute a query in "spatial" order starting at |queryRoot|. This means
+// walking the lines boxes in the order they would get painted.
+static void spatialQuery(LayoutObject* queryRoot, QueryData* queryData, ProcessTextFragmentCallback fragmentCallback)
 {
     Vector<SVGInlineTextBox*> textBoxes;
     collectTextBoxesInFlowBox(flowBoxForLayoutObject(queryRoot), textBoxes);
 
-    unsigned processedCharacters = 0;
-    unsigned textBoxCount = textBoxes.size();
-
     // Loop over all text boxes
-    for (unsigned textBoxPosition = 0; textBoxPosition < textBoxCount; ++textBoxPosition) {
-        queryData->textBox = textBoxes[textBoxPosition];
-        queryData->textLayoutObject = &toLayoutSVGInlineText(queryData->textBox->layoutObject());
-        ASSERT(queryData->textLayoutObject->style());
-
-        queryData->isVerticalText = queryData->textLayoutObject->style()->svgStyle().isVerticalWritingMode();
-        const Vector<SVGTextFragment>& fragments = queryData->textBox->textFragments();
-
-        // Loop over all text fragments in this text box, firing a callback for each.
-        unsigned fragmentCount = fragments.size();
-        for (unsigned i = 0; i < fragmentCount; ++i) {
-            const SVGTextFragment& fragment = fragments.at(i);
-            if (fragmentCallback(queryData, fragment))
-                return true;
-
-            processedCharacters += fragment.length;
-        }
+    for (const SVGInlineTextBox* textBox : textBoxes) {
+        if (queryTextBox(queryData, textBox, fragmentCallback))
+            return;
+    }
+}
+
+static void collectTextBoxesInLogicalOrder(const LayoutSVGInlineText& textLayoutObject, Vector<SVGInlineTextBox*>& textBoxes)
+{
+    textBoxes.shrink(0);
+    for (InlineTextBox* textBox = textLayoutObject.firstTextBox(); textBox; textBox = textBox->nextTextBox())
+        textBoxes.append(toSVGInlineTextBox(textBox));
+    std::sort(textBoxes.begin(), textBoxes.end(), InlineTextBox::compareByStart);
+}
+
+// Execute a query in "logical" order starting at |queryRoot|. This means
+// walking the lines boxes for each layout object in layout tree (pre)order.
+static void logicalQuery(LayoutObject* queryRoot, QueryData* queryData, ProcessTextFragmentCallback fragmentCallback)
+{
+    if (!queryRoot)
+        return;
+
+    // Walk the layout tree in pre-order, starting at the specified root, and
+    // run the query for each text node.
+    Vector<SVGInlineTextBox*> textBoxes;
+    for (LayoutObject* layoutObject = queryRoot->slowFirstChild(); layoutObject; layoutObject = layoutObject->nextInPreOrder(queryRoot)) {
+        if (!layoutObject->isSVGInlineText())
+            continue;
 
-        queryData->processedCharacters = processedCharacters;
+        LayoutSVGInlineText& textLayoutObject = toLayoutSVGInlineText(*layoutObject);
+        ASSERT(textLayoutObject.style());
+
+        // TODO(fs): Allow filtering the search earlier, since we should be
+        // able to trivially reject (prune) at least some of the queries.
+        collectTextBoxesInLogicalOrder(textLayoutObject, textBoxes);
+
+        for (const SVGInlineTextBox* textBox : textBoxes) {
+            if (queryTextBox(queryData, textBox, fragmentCallback))
+                return;
+            queryData->currentOffset += textBox->len();
+        }
     }
-    return false;
 }
 
 static void modifyStartEndPositionsRespectingLigatures(const QueryData* queryData, const SVGTextFragment& fragment, int& startPosition, int& endPosition)
@@ -167,9 +201,11 @@ static void modifyStartEndPositionsRespectingLigatures(const QueryData* queryDat
 
 static bool mapStartEndPositionsIntoFragmentCoordinates(const QueryData* queryData, const SVGTextFragment& fragment, int& startPosition, int& endPosition)
 {
+    unsigned boxStart = queryData->currentOffset;
+
     // Make <startPosition, endPosition> offsets relative to the current text box.
-    startPosition -= queryData->processedCharacters;
-    endPosition -= queryData->processedCharacters;
+    startPosition -= boxStart;
+    endPosition -= boxStart;
 
     // Reuse the same logic used for text selection & painting, to map our
     // query start/length into start/endPositions of the current text fragment.
@@ -191,8 +227,8 @@ static bool numberOfCharactersCallback(QueryData*, const SVGTextFragment&)
 unsigned SVGTextQuery::numberOfCharacters() const
 {
     QueryData data;
-    executeQuery(m_queryRootLayoutObject, &data, numberOfCharactersCallback);
-    return data.processedCharacters;
+    logicalQuery(m_queryRootLayoutObject, &data, numberOfCharactersCallback);
+    return data.currentOffset;
 }
 
 // textLength() implementation
@@ -215,7 +251,7 @@ static bool textLengthCallback(QueryData* queryData, const SVGTextFragment& frag
 float SVGTextQuery::textLength() const
 {
     TextLengthData data;
-    executeQuery(m_queryRootLayoutObject, &data, textLengthCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, textLengthCallback);
     return data.textLength;
 }
 
@@ -251,7 +287,7 @@ static bool subStringLengthCallback(QueryData* queryData, const SVGTextFragment&
 float SVGTextQuery::subStringLength(unsigned startPosition, unsigned length) const
 {
     SubStringLengthData data(startPosition, length);
-    executeQuery(m_queryRootLayoutObject, &data, subStringLengthCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, subStringLengthCallback);
     return data.subStringLength;
 }
 
@@ -318,7 +354,7 @@ static bool startPositionOfCharacterCallback(QueryData* queryData, const SVGText
 FloatPoint SVGTextQuery::startPositionOfCharacter(unsigned position) const
 {
     StartPositionOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, startPositionOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, startPositionOfCharacterCallback);
     return data.startPosition;
 }
 
@@ -352,7 +388,7 @@ static bool endPositionOfCharacterCallback(QueryData* queryData, const SVGTextFr
 FloatPoint SVGTextQuery::endPositionOfCharacter(unsigned position) const
 {
     EndPositionOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, endPositionOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, endPositionOfCharacterCallback);
     return data.endPosition;
 }
 
@@ -392,7 +428,7 @@ static bool rotationOfCharacterCallback(QueryData* queryData, const SVGTextFragm
 float SVGTextQuery::rotationOfCharacter(unsigned position) const
 {
     RotationOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, rotationOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, rotationOfCharacterCallback);
     return data.rotation;
 }
 
@@ -484,7 +520,7 @@ static bool extentOfCharacterCallback(QueryData* queryData, const SVGTextFragmen
 FloatRect SVGTextQuery::extentOfCharacter(unsigned position) const
 {
     ExtentOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, extentOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, extentOfCharacterCallback);
     return data.extent;
 }
 
@@ -492,12 +528,55 @@ FloatRect SVGTextQuery::extentOfCharacter(unsigned position) const
 struct CharacterNumberAtPositionData : QueryData {
     CharacterNumberAtPositionData(const FloatPoint& queryPosition)
         : position(queryPosition)
+        , hitLayoutObject(nullptr)
+        , offsetInTextNode(0)
     {
     }
 
+    int characterNumberWithin(const LayoutObject* queryRoot) const;
+
     FloatPoint position;
+    LayoutObject* hitLayoutObject;
+    int offsetInTextNode;
 };
 
+int CharacterNumberAtPositionData::characterNumberWithin(const LayoutObject* queryRoot) const
+{
+    // http://www.w3.org/TR/SVG/single-page.html#text-__svg__SVGTextContentElement__getCharNumAtPosition
+    // "If no such character exists, a value of -1 is returned."
+    if (!hitLayoutObject)
+        return -1;
+    ASSERT(queryRoot);
+    int characterNumber = offsetInTextNode;
+
+    // Accumulate the lengths of all the text nodes preceding the target layout
+    // object within the queried root, to get the complete character number.
+    for (const LayoutObject* layoutObject = hitLayoutObject->previousInPreOrder(queryRoot);
+        layoutObject; layoutObject = layoutObject->previousInPreOrder(queryRoot)) {
+        if (!layoutObject->isSVGInlineText())
+            continue;
+        characterNumber += toLayoutSVGInlineText(layoutObject)->renderedTextLength();
+    }
+    return characterNumber;
+}
+
+static unsigned logicalOffsetInTextNode(const LayoutSVGInlineText& textLayoutObject, const SVGInlineTextBox* startTextBox, unsigned fragmentOffset)
+{
+    Vector<SVGInlineTextBox*> textBoxes;
+    collectTextBoxesInLogicalOrder(textLayoutObject, textBoxes);
+
+    ASSERT(startTextBox);
+    size_t index = textBoxes.find(startTextBox);
+    ASSERT(index != kNotFound);
+
+    unsigned offset = fragmentOffset;
+    while (index) {
+        --index;
+        offset += textBoxes[index]->len();
+    }
+    return offset;
+}
+
 static bool characterNumberAtPositionCallback(QueryData* queryData, const SVGTextFragment& fragment)
 {
     CharacterNumberAtPositionData* data = static_cast<CharacterNumberAtPositionData*>(queryData);
@@ -516,10 +595,10 @@ static bool characterNumberAtPositionCallback(QueryData* queryData, const SVGTex
     while (fragmentOffset < fragment.length) {
         calculateGlyphBoundaries(queryData, fragment, fragmentOffset, extent);
         if (extent.contains(data->position)) {
-            // Compute the character offset of the glyph within the text box
-            // and add to processedCharacters.
-            unsigned characterOffset = fragment.characterOffset + fragmentOffset;
-            data->processedCharacters += characterOffset - data->textBox->start();
+            // Compute the character offset of the glyph within the text node.
+            unsigned offsetInBox = fragment.characterOffset - queryData->textBox->start() + fragmentOffset;
+            data->offsetInTextNode = logicalOffsetInTextNode(*queryData->textLayoutObject, queryData->textBox, offsetInBox);
+            data->hitLayoutObject = data->textLayoutObject;
             return true;
         }
         fragmentOffset += textMetrics[textMetricsOffset].length();
@@ -531,10 +610,8 @@ static bool characterNumberAtPositionCallback(QueryData* queryData, const SVGTex
 int SVGTextQuery::characterNumberAtPosition(const FloatPoint& position) const
 {
     CharacterNumberAtPositionData data(position);
-    if (!executeQuery(m_queryRootLayoutObject, &data, characterNumberAtPositionCallback))
-        return -1;
-
-    return data.processedCharacters;
+    spatialQuery(m_queryRootLayoutObject, &data, characterNumberAtPositionCallback);
+    return data.characterNumberWithin(m_queryRootLayoutObject);
 }
 
 }