Add a "logical query mode" to SVGTextQuery

Source/core/layout/svg/SVGTextQuery.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
@@ skipping 19 matching lines @@
 #include "platform/FloatConversion.h"
 #include "wtf/MathExtras.h"
 #include "wtf/Vector.h"
 
 namespace blink {
 
 // Base structure for callback user data
 struct QueryData {
     QueryData()
         : isVerticalText(false)
-        , processedCharacters(0)
+        , currentOffset(0)
         , textLayoutObject(0)
         , textBox(0)
     {
     }
 
     bool isVerticalText;
-    unsigned processedCharacters;
+    unsigned currentOffset;
     LayoutSVGInlineText* textLayoutObject;
     const SVGInlineTextBox* textBox;
 };
 
 static inline InlineFlowBox* flowBoxForLayoutObject(LayoutObject* layoutObject)
 {
     if (!layoutObject)
         return 0;
 
     if (layoutObject->isLayoutBlock()) {
@@ skipping 36 matching lines @@
             continue;
         }
 
         if (child->isSVGInlineTextBox())
             textBoxes.append(toSVGInlineTextBox(child));
     }
 }
 
 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 (const SVGInlineTextBox* textBox : textBoxes) {
+        if (queryTextBox(queryData, textBox, fragmentCallback))
+            return;
+    }
+}
 
-    // 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());
+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);
+}
 
-        queryData->isVerticalText = queryData->textLayoutObject->style()->svgStyle().isVerticalWritingMode();
-        const Vector<SVGTextFragment>& fragments = queryData->textBox->textFragments();
+// 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;
 
-        // 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;
+    // 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;
 
-            processedCharacters += fragment.length;
+        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();
         }
-
-        queryData->processedCharacters = processedCharacters;
     }
-    return false;
 }
 
 static void modifyStartEndPositionsRespectingLigatures(const QueryData* queryData, const SVGTextFragment& fragment, int& startPosition, int& endPosition)
 {
     const Vector<SVGTextMetrics>& textMetricsValues = queryData->textLayoutObject->layoutAttributes()->textMetricsValues();
 
     unsigned textMetricsOffset = fragment.metricsListOffset;
     int fragmentOffset = 0;
     int fragmentEnd = static_cast<int>(fragment.length);
 
@@ skipping 16 matching lines @@
         if (fragmentOffset >= endPosition)
             break;
         textMetricsOffset++;
     }
 
     endPosition = fragmentOffset;
 }
 
 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.
     if (!queryData->textBox->mapStartEndPositionsIntoFragmentCoordinates(fragment, startPosition, endPosition))
         return false;
 
     modifyStartEndPositionsRespectingLigatures(queryData, fragment, startPosition, endPosition);
     ASSERT(startPosition < endPosition);
     return true;
 }
 
 // numberOfCharacters() implementation
 static bool numberOfCharactersCallback(QueryData*, const SVGTextFragment&)
 {
     // no-op
     return false;
 }
 
 unsigned SVGTextQuery::numberOfCharacters() const
 {
     QueryData data;
-    executeQuery(m_queryRootLayoutObject, &data, numberOfCharactersCallback);
-    return data.processedCharacters;
+    logicalQuery(m_queryRootLayoutObject, &data, numberOfCharactersCallback);
+    return data.currentOffset;
 }
 
 // textLength() implementation
 struct TextLengthData : QueryData {
     TextLengthData()
         : textLength(0)
     {
     }
 
     float textLength;
 };
 
 static bool textLengthCallback(QueryData* queryData, const SVGTextFragment& fragment)
 {
     TextLengthData* data = static_cast<TextLengthData*>(queryData);
     data->textLength += queryData->isVerticalText ? fragment.height : fragment.width;
     return false;
 }
 
 float SVGTextQuery::textLength() const
 {
     TextLengthData data;
-    executeQuery(m_queryRootLayoutObject, &data, textLengthCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, textLengthCallback);
     return data.textLength;
 }
 
 // subStringLength() implementation
 struct SubStringLengthData : QueryData {
     SubStringLengthData(unsigned queryStartPosition, unsigned queryLength)
         : startPosition(queryStartPosition)
         , length(queryLength)
         , subStringLength(0)
     {
@@ skipping 15 matching lines @@
         return false;
 
     SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(queryData->textLayoutObject, fragment.characterOffset + startPosition, endPosition - startPosition, queryData->textBox->direction());
     data->subStringLength += queryData->isVerticalText ? metrics.height() : metrics.width();
     return false;
 }
 
 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;
 }
 
 // startPositionOfCharacter() implementation
 struct StartPositionOfCharacterData : QueryData {
     StartPositionOfCharacterData(unsigned queryPosition)
         : position(queryPosition)
     {
     }
 
@@ skipping 46 matching lines @@
     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
         return false;
 
     data->startPosition = calculateGlyphPosition(queryData, fragment, startPosition);
     return true;
 }
 
 FloatPoint SVGTextQuery::startPositionOfCharacter(unsigned position) const
 {
     StartPositionOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, startPositionOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, startPositionOfCharacterCallback);
     return data.startPosition;
 }
 
 // endPositionOfCharacter() implementation
 struct EndPositionOfCharacterData : QueryData {
     EndPositionOfCharacterData(unsigned queryPosition)
         : position(queryPosition)
     {
     }
 
@@ skipping 13 matching lines @@
     // TODO(fs): mapStartEndPositionsIntoFragmentCoordinates(...) above applies
     // some heuristics for ligatures, so why not just use endPosition here?
     // (rather than startPosition+1)
     data->endPosition = calculateGlyphPosition(queryData, fragment, startPosition + 1);
     return true;
 }
 
 FloatPoint SVGTextQuery::endPositionOfCharacter(unsigned position) const
 {
     EndPositionOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, endPositionOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, endPositionOfCharacterCallback);
     return data.endPosition;
 }
 
 // rotationOfCharacter() implementation
 struct RotationOfCharacterData : QueryData {
     RotationOfCharacterData(unsigned queryPosition)
         : position(queryPosition)
         , rotation(0)
     {
     }
@@ skipping 19 matching lines @@
         fragmentTransform.scale(1 / fragmentTransform.xScale(), 1 / fragmentTransform.yScale());
         data->rotation = narrowPrecisionToFloat(rad2deg(atan2(fragmentTransform.b(), fragmentTransform.a())));
     }
 
     return true;
 }
 
 float SVGTextQuery::rotationOfCharacter(unsigned position) const
 {
     RotationOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, rotationOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, rotationOfCharacterCallback);
     return data.rotation;
 }
 
 // extentOfCharacter() implementation
 struct ExtentOfCharacterData : QueryData {
     ExtentOfCharacterData(unsigned queryPosition)
         : position(queryPosition)
     {
     }
 
@@ skipping 71 matching lines @@
     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
         return false;
 
     calculateGlyphBoundaries(queryData, fragment, startPosition, data->extent);
     return true;
 }
 
 FloatRect SVGTextQuery::extentOfCharacter(unsigned position) const
 {
     ExtentOfCharacterData data(position);
-    executeQuery(m_queryRootLayoutObject, &data, extentOfCharacterCallback);
+    logicalQuery(m_queryRootLayoutObject, &data, extentOfCharacterCallback);
     return data.extent;
 }
 
 // characterNumberAtPosition() implementation
 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
+{
+    // https://svgwg.org/svg2-draft/single-page.html#text-__svg__SVGTextContentElement__getCharNumAtPosition

[pdr., 2015/04/16 21:13:25]

Sorry for the churn. I use the svg2 draft for everything but we should link to
the real deal if possible. Can you change this to be:
http://www.w3.org/TR/SVG/single-page.html#text-__svg__SVGTextContentElement__...

[fs, 2015/04/17 11:05:40]

Done.

+    // "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);
 
     // Test the query point against the bounds of the entire fragment first.
     FloatRect fragmentExtents = calculateFragmentBoundaries(*queryData->textLayoutObject, fragment);
     if (!fragmentExtents.contains(data->position))
         return false;
 
     // Iterate through the glyphs in this fragment, and check if their extents
     // contain the query point.
     FloatRect extent;
     const Vector<SVGTextMetrics>& textMetrics = queryData->textLayoutObject->layoutAttributes()->textMetricsValues();
     unsigned textMetricsOffset = fragment.metricsListOffset;
     unsigned fragmentOffset = 0;
     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();
         textMetricsOffset++;
     }
     return false;
 }
 
 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);
 }
 
 }