third_party/WebKit/Source/core/layout/svg/SVGTextQuery.cpp - chromium/src - Git at Google

 /*
  * 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/SVGTextQuery.h"

 #include "core/layout/LayoutBlockFlow.h"
 #include "core/layout/LayoutInline.h"
 #include "core/layout/api/LineLayoutSVGInlineText.h"
 #include "core/layout/line/InlineFlowBox.h"
 #include "core/layout/svg/LayoutSVGInlineText.h"
 #include "core/layout/svg/SVGTextFragment.h"
 #include "core/layout/svg/SVGTextMetrics.h"
 #include "core/layout/svg/line/SVGInlineTextBox.h"
 #include "wtf/MathExtras.h"
 #include "wtf/Vector.h"
 #include <algorithm>

 namespace blink {

 // Base structure for callback user data
 struct QueryData {
   QueryData()
       : isVerticalText(false),
         currentOffset(0),
         textLineLayout(nullptr),
         textBox(nullptr) {}

   bool isVerticalText;
   unsigned currentOffset;
   LineLayoutSVGInlineText textLineLayout;
   const SVGInlineTextBox* textBox;
 };

 static inline InlineFlowBox* flowBoxForLayoutObject(
     LayoutObject* layoutObject) {
   if (!layoutObject)
     return nullptr;

   if (layoutObject->isLayoutBlock()) {
     // If we're given a block element, it has to be a LayoutSVGText.
     ASSERT(layoutObject->isSVGText());
     LayoutBlockFlow* layoutBlockFlow = toLayoutBlockFlow(layoutObject);

     // LayoutSVGText only ever contains a single line box.
     InlineFlowBox* flowBox = layoutBlockFlow->firstLineBox();
     ASSERT(flowBox == layoutBlockFlow->lastLineBox());
     return flowBox;
   }

   if (layoutObject->isLayoutInline()) {
     // We're given a LayoutSVGInline or objects that derive from it
     // (LayoutSVGTSpan / LayoutSVGTextPath)
     LayoutInline* layoutInline = toLayoutInline(layoutObject);

     // LayoutSVGInline only ever contains a single line box.
     InlineFlowBox* flowBox = layoutInline->firstLineBox();
     ASSERT(flowBox == layoutInline->lastLineBox());
     return flowBox;
   }

   ASSERT_NOT_REACHED();
   return nullptr;
 }

 static void collectTextBoxesInFlowBox(InlineFlowBox* flowBox,
                                       Vector<SVGInlineTextBox*>& textBoxes) {
   if (!flowBox)
     return;

   for (InlineBox* child = flowBox->firstChild(); child;
        child = child->nextOnLine()) {
     if (child->isInlineFlowBox()) {
       // Skip generated content.
       if (!child->getLineLayoutItem().node())
         continue;

       collectTextBoxesInFlowBox(toInlineFlowBox(child), textBoxes);
       continue;
     }

     if (child->isSVGInlineTextBox())
       textBoxes.append(toSVGInlineTextBox(child));
   }
 }

 typedef bool ProcessTextFragmentCallback(QueryData*, const SVGTextFragment&);

 static bool queryTextBox(QueryData* queryData,
                          const SVGInlineTextBox* textBox,
                          ProcessTextFragmentCallback fragmentCallback) {
   queryData->textBox = textBox;
   queryData->textLineLayout =
       LineLayoutSVGInlineText(textBox->getLineLayoutItem());

   queryData->isVerticalText =
       !queryData->textLineLayout.style()->isHorizontalWritingMode();

   // 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);

   // Loop over all text boxes
   for (const SVGInlineTextBox* textBox : textBoxes) {
     if (queryTextBox(queryData, textBox, fragmentCallback))
       return;
   }
 }

 static void collectTextBoxesInLogicalOrder(
     LineLayoutSVGInlineText textLineLayout,
     Vector<SVGInlineTextBox*>& textBoxes) {
   textBoxes.shrink(0);
   for (InlineTextBox* textBox = textLineLayout.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;

     LineLayoutSVGInlineText textLineLayout =
         LineLayoutSVGInlineText(toLayoutSVGInlineText(layoutObject));
     ASSERT(textLineLayout.style());

     // TODO(fs): Allow filtering the search earlier, since we should be
     // able to trivially reject (prune) at least some of the queries.
     collectTextBoxesInLogicalOrder(textLineLayout, textBoxes);

     for (const SVGInlineTextBox* textBox : textBoxes) {
       if (queryTextBox(queryData, textBox, fragmentCallback))
         return;
       queryData->currentOffset += textBox->len();
     }
   }
 }

 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 -= 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.
   return queryData->textBox->mapStartEndPositionsIntoFragmentCoordinates(
       fragment, startPosition, endPosition);
 }

 // numberOfCharacters() implementation
 static bool numberOfCharactersCallback(QueryData*, const SVGTextFragment&) {
   // no-op
   return false;
 }

 unsigned SVGTextQuery::numberOfCharacters() const {
   QueryData data;
   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;
   logicalQuery(m_queryRootLayoutObject, &data, textLengthCallback);
   return data.textLength;
 }

 using MetricsList = Vector<SVGTextMetrics>;

 MetricsList::const_iterator findMetricsForCharacter(
     const MetricsList& metricsList,
     const SVGTextFragment& fragment,
     unsigned startInFragment) {
   // Find the text metrics cell that starts at or contains the character at
   // |startInFragment|.
   MetricsList::const_iterator metrics =
       metricsList.begin() + fragment.metricsListOffset;
   unsigned fragmentOffset = 0;
   while (fragmentOffset < fragment.length) {
     fragmentOffset += metrics->length();
     if (startInFragment < fragmentOffset)
       break;
     ++metrics;
   }
   ASSERT(metrics <= metricsList.end());
   return metrics;
 }

 static float calculateGlyphRange(const QueryData* queryData,
                                  const SVGTextFragment& fragment,
                                  unsigned start,
                                  unsigned end) {
   const MetricsList& metricsList = queryData->textLineLayout.metricsList();
   auto metrics = findMetricsForCharacter(metricsList, fragment, start);
   auto endMetrics = findMetricsForCharacter(metricsList, fragment, end);
   float glyphRange = 0;
   for (; metrics != endMetrics; ++metrics)
     glyphRange +=
         queryData->isVerticalText ? metrics->height() : metrics->width();
   return glyphRange;
 }

 // subStringLength() implementation
 struct SubStringLengthData : QueryData {
   SubStringLengthData(unsigned queryStartPosition, unsigned queryLength)
       : startPosition(queryStartPosition),
         length(queryLength),
         subStringLength(0) {}

   unsigned startPosition;
   unsigned length;

   float subStringLength;
 };

 static bool subStringLengthCallback(QueryData* queryData,
                                     const SVGTextFragment& fragment) {
   SubStringLengthData* data = static_cast<SubStringLengthData*>(queryData);

   int startPosition = data->startPosition;
   int endPosition = startPosition + data->length;
   if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
                                                    startPosition, endPosition))
     return false;

   data->subStringLength +=
       calculateGlyphRange(queryData, fragment, startPosition, endPosition);
   return false;
 }

 float SVGTextQuery::subStringLength(unsigned startPosition,
                                     unsigned length) const {
   SubStringLengthData data(startPosition, length);
   logicalQuery(m_queryRootLayoutObject, &data, subStringLengthCallback);
   return data.subStringLength;
 }

 // startPositionOfCharacter() implementation
 struct StartPositionOfCharacterData : QueryData {
   StartPositionOfCharacterData(unsigned queryPosition)
       : position(queryPosition) {}

   unsigned position;
   FloatPoint startPosition;
 };

 static FloatPoint logicalGlyphPositionToPhysical(
     const QueryData* queryData,
     const SVGTextFragment& fragment,
     float logicalGlyphOffset) {
   float physicalGlyphOffset = logicalGlyphOffset;
   if (!queryData->textBox->isLeftToRightDirection()) {
     float fragmentExtent =
         queryData->isVerticalText ? fragment.height : fragment.width;
     physicalGlyphOffset = fragmentExtent - logicalGlyphOffset;
   }

   FloatPoint glyphPosition(fragment.x, fragment.y);
   if (queryData->isVerticalText)
     glyphPosition.move(0, physicalGlyphOffset);
   else
     glyphPosition.move(physicalGlyphOffset, 0);

   return glyphPosition;
 }

 static FloatPoint calculateGlyphPosition(const QueryData* queryData,
                                          const SVGTextFragment& fragment,
                                          unsigned offsetInFragment) {
   float glyphOffsetInDirection =
       calculateGlyphRange(queryData, fragment, 0, offsetInFragment);
   FloatPoint glyphPosition = logicalGlyphPositionToPhysical(
       queryData, fragment, glyphOffsetInDirection);
   if (fragment.isTransformed()) {
     AffineTransform fragmentTransform = fragment.buildFragmentTransform(
         SVGTextFragment::TransformIgnoringTextLength);
     glyphPosition = fragmentTransform.mapPoint(glyphPosition);
   }
   return glyphPosition;
 }

 static bool startPositionOfCharacterCallback(QueryData* queryData,
                                              const SVGTextFragment& fragment) {
   StartPositionOfCharacterData* data =
       static_cast<StartPositionOfCharacterData*>(queryData);

   int startPosition = data->position;
   int endPosition = startPosition + 1;
   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);
   logicalQuery(m_queryRootLayoutObject, &data,
                startPositionOfCharacterCallback);
   return data.startPosition;
 }

 // endPositionOfCharacter() implementation
 struct EndPositionOfCharacterData : QueryData {
   EndPositionOfCharacterData(unsigned queryPosition)
       : position(queryPosition) {}

   unsigned position;
   FloatPoint endPosition;
 };

 static bool endPositionOfCharacterCallback(QueryData* queryData,
                                            const SVGTextFragment& fragment) {
   EndPositionOfCharacterData* data =
       static_cast<EndPositionOfCharacterData*>(queryData);

   int startPosition = data->position;
   int endPosition = startPosition + 1;
   if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
                                                    startPosition, endPosition))
     return false;

   data->endPosition = calculateGlyphPosition(queryData, fragment, endPosition);
   return true;
 }

 FloatPoint SVGTextQuery::endPositionOfCharacter(unsigned position) const {
   EndPositionOfCharacterData data(position);
   logicalQuery(m_queryRootLayoutObject, &data, endPositionOfCharacterCallback);
   return data.endPosition;
 }

 // rotationOfCharacter() implementation
 struct RotationOfCharacterData : QueryData {
   RotationOfCharacterData(unsigned queryPosition)
       : position(queryPosition), rotation(0) {}

   unsigned position;
   float rotation;
 };

 static bool rotationOfCharacterCallback(QueryData* queryData,
                                         const SVGTextFragment& fragment) {
   RotationOfCharacterData* data =
       static_cast<RotationOfCharacterData*>(queryData);

   int startPosition = data->position;
   int endPosition = startPosition + 1;
   if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
                                                    startPosition, endPosition))
     return false;

   if (!fragment.isTransformed()) {
     data->rotation = 0;
   } else {
     AffineTransform fragmentTransform = fragment.buildFragmentTransform(
         SVGTextFragment::TransformIgnoringTextLength);
     fragmentTransform.scale(1 / fragmentTransform.xScale(),
                             1 / fragmentTransform.yScale());
     data->rotation = clampTo<float>(
         rad2deg(atan2(fragmentTransform.b(), fragmentTransform.a())));
   }
   return true;
 }

 float SVGTextQuery::rotationOfCharacter(unsigned position) const {
   RotationOfCharacterData data(position);
   logicalQuery(m_queryRootLayoutObject, &data, rotationOfCharacterCallback);
   return data.rotation;
 }

 // extentOfCharacter() implementation
 struct ExtentOfCharacterData : QueryData {
   ExtentOfCharacterData(unsigned queryPosition) : position(queryPosition) {}

   unsigned position;
   FloatRect extent;
 };

 static FloatRect physicalGlyphExtents(const QueryData* queryData,
                                       const SVGTextMetrics& metrics,
                                       const FloatPoint& glyphPosition) {
   // TODO(fs): Negative glyph extents seems kind of weird to have, but
   // presently it can occur in some cases (like Arabic.)
   FloatRect glyphExtents(glyphPosition,
                          FloatSize(std::max<float>(metrics.width(), 0),
                                    std::max<float>(metrics.height(), 0)));

   // If RTL, adjust the starting point to align with the LHS of the glyph
   // bounding box.
   if (!queryData->textBox->isLeftToRightDirection()) {
     if (queryData->isVerticalText)
       glyphExtents.move(0, -glyphExtents.height());
     else
       glyphExtents.move(-glyphExtents.width(), 0);
   }
   return glyphExtents;
 }

 static inline FloatRect calculateGlyphBoundaries(
     const QueryData* queryData,
     const SVGTextFragment& fragment,
     int startPosition) {
   const float scalingFactor = queryData->textLineLayout.scalingFactor();
   ASSERT(scalingFactor);
   const float baseline =
       queryData->textLineLayout.scaledFont().getFontMetrics().floatAscent() /
       scalingFactor;

   float glyphOffsetInDirection =
       calculateGlyphRange(queryData, fragment, 0, startPosition);
   FloatPoint glyphPosition = logicalGlyphPositionToPhysical(
       queryData, fragment, glyphOffsetInDirection);
   glyphPosition.move(0, -baseline);

   // Use the SVGTextMetrics computed by SVGTextMetricsBuilder.
   const MetricsList& metricsList = queryData->textLineLayout.metricsList();
   auto metrics = findMetricsForCharacter(metricsList, fragment, startPosition);

   FloatRect extent = physicalGlyphExtents(queryData, *metrics, glyphPosition);
   if (fragment.isTransformed()) {
     AffineTransform fragmentTransform = fragment.buildFragmentTransform(
         SVGTextFragment::TransformIgnoringTextLength);
     extent = fragmentTransform.mapRect(extent);
   }
   return extent;
 }

 static bool extentOfCharacterCallback(QueryData* queryData,
                                       const SVGTextFragment& fragment) {
   ExtentOfCharacterData* data = static_cast<ExtentOfCharacterData*>(queryData);

   int startPosition = data->position;
   int endPosition = startPosition + 1;
   if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
                                                    startPosition, endPosition))
     return false;

   data->extent = calculateGlyphBoundaries(queryData, fragment, startPosition);
   return true;
 }

 FloatRect SVGTextQuery::extentOfCharacter(unsigned position) const {
   ExtentOfCharacterData data(position);
   logicalQuery(m_queryRootLayoutObject, &data, extentOfCharacterCallback);
   return data.extent;
 }

 // characterNumberAtPosition() implementation
 struct CharacterNumberAtPositionData : QueryData {
   CharacterNumberAtPositionData(const FloatPoint& queryPosition)
       : position(queryPosition), hitLayoutItem(nullptr), offsetInTextNode(0) {}

   int characterNumberWithin(const LayoutObject* queryRoot) const;

   FloatPoint position;
   LineLayoutItem hitLayoutItem;
   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 (!hitLayoutItem)
     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 (LineLayoutItem layoutItem = hitLayoutItem.previousInPreOrder(queryRoot);
        layoutItem; layoutItem = layoutItem.previousInPreOrder(queryRoot)) {
     if (!layoutItem.isSVGInlineText())
       continue;
     characterNumber += LineLayoutSVGInlineText(layoutItem).resolvedTextLength();
   }
   return characterNumber;
 }

 static unsigned logicalOffsetInTextNode(LineLayoutSVGInlineText textLineLayout,
                                         const SVGInlineTextBox* startTextBox,
                                         unsigned fragmentOffset) {
   Vector<SVGInlineTextBox*> textBoxes;
   collectTextBoxesInLogicalOrder(textLineLayout, 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);

   const float scalingFactor = data->textLineLayout.scalingFactor();
   ASSERT(scalingFactor);
   const float baseline =
       data->textLineLayout.scaledFont().getFontMetrics().floatAscent() /
       scalingFactor;

   // Test the query point against the bounds of the entire fragment first.
   if (!fragment.boundingBox(baseline).contains(data->position))
     return false;

   AffineTransform fragmentTransform = fragment.buildFragmentTransform(
       SVGTextFragment::TransformIgnoringTextLength);

   // Iterate through the glyphs in this fragment, and check if their extents
   // contain the query point.
   MetricsList::const_iterator metrics =
       data->textLineLayout.metricsList().begin() + fragment.metricsListOffset;
   unsigned fragmentOffset = 0;
   float glyphOffset = 0;
   while (fragmentOffset < fragment.length) {
     FloatPoint glyphPosition =
         logicalGlyphPositionToPhysical(data, fragment, glyphOffset);
     glyphPosition.move(0, -baseline);

     FloatRect extent = fragmentTransform.mapRect(
         physicalGlyphExtents(data, *metrics, glyphPosition));
     if (extent.contains(data->position)) {
       // Compute the character offset of the glyph within the text node.
       unsigned offsetInBox = fragment.characterOffset -
                              queryData->textBox->start() + fragmentOffset;
       data->offsetInTextNode = logicalOffsetInTextNode(
           queryData->textLineLayout, queryData->textBox, offsetInBox);
       data->hitLayoutItem = LineLayoutItem(data->textLineLayout);
       return true;
     }
     fragmentOffset += metrics->length();
     glyphOffset += data->isVerticalText ? metrics->height() : metrics->width();
     ++metrics;
   }
   return false;
 }

 int SVGTextQuery::characterNumberAtPosition(const FloatPoint& position) const {
   CharacterNumberAtPositionData data(position);
   spatialQuery(m_queryRootLayoutObject, &data,
                characterNumberAtPositionCallback);
   return data.characterNumberWithin(m_queryRootLayoutObject);
 }

 }  // namespace blink
	/*
	* 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/SVGTextQuery.h"

	#include "core/layout/LayoutBlockFlow.h"
	#include "core/layout/LayoutInline.h"
	#include "core/layout/api/LineLayoutSVGInlineText.h"
	#include "core/layout/line/InlineFlowBox.h"
	#include "core/layout/svg/LayoutSVGInlineText.h"
	#include "core/layout/svg/SVGTextFragment.h"
	#include "core/layout/svg/SVGTextMetrics.h"
	#include "core/layout/svg/line/SVGInlineTextBox.h"
	#include "wtf/MathExtras.h"
	#include "wtf/Vector.h"
	#include <algorithm>

	namespace blink {

	// Base structure for callback user data
	struct QueryData {
	QueryData()
	: isVerticalText(false),
	currentOffset(0),
	textLineLayout(nullptr),
	textBox(nullptr) {}

	bool isVerticalText;
	unsigned currentOffset;
	LineLayoutSVGInlineText textLineLayout;
	const SVGInlineTextBox* textBox;
	};

	static inline InlineFlowBox* flowBoxForLayoutObject(
	LayoutObject* layoutObject) {
	if (!layoutObject)
	return nullptr;

	if (layoutObject->isLayoutBlock()) {
	// If we're given a block element, it has to be a LayoutSVGText.
	ASSERT(layoutObject->isSVGText());
	LayoutBlockFlow* layoutBlockFlow = toLayoutBlockFlow(layoutObject);

	// LayoutSVGText only ever contains a single line box.
	InlineFlowBox* flowBox = layoutBlockFlow->firstLineBox();
	ASSERT(flowBox == layoutBlockFlow->lastLineBox());
	return flowBox;
	}

	if (layoutObject->isLayoutInline()) {
	// We're given a LayoutSVGInline or objects that derive from it
	// (LayoutSVGTSpan / LayoutSVGTextPath)
	LayoutInline* layoutInline = toLayoutInline(layoutObject);

	// LayoutSVGInline only ever contains a single line box.
	InlineFlowBox* flowBox = layoutInline->firstLineBox();
	ASSERT(flowBox == layoutInline->lastLineBox());
	return flowBox;
	}

	ASSERT_NOT_REACHED();
	return nullptr;
	}

	static void collectTextBoxesInFlowBox(InlineFlowBox* flowBox,
	Vector<SVGInlineTextBox*>& textBoxes) {
	if (!flowBox)
	return;

	for (InlineBox* child = flowBox->firstChild(); child;
	child = child->nextOnLine()) {
	if (child->isInlineFlowBox()) {
	// Skip generated content.
	if (!child->getLineLayoutItem().node())
	continue;

	collectTextBoxesInFlowBox(toInlineFlowBox(child), textBoxes);
	continue;
	}

	if (child->isSVGInlineTextBox())
	textBoxes.append(toSVGInlineTextBox(child));
	}
	}

	typedef bool ProcessTextFragmentCallback(QueryData*, const SVGTextFragment&);

	static bool queryTextBox(QueryData* queryData,
	const SVGInlineTextBox* textBox,
	ProcessTextFragmentCallback fragmentCallback) {
	queryData->textBox = textBox;
	queryData->textLineLayout =
	LineLayoutSVGInlineText(textBox->getLineLayoutItem());

	queryData->isVerticalText =
	!queryData->textLineLayout.style()->isHorizontalWritingMode();

	// 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);

	// Loop over all text boxes
	for (const SVGInlineTextBox* textBox : textBoxes) {
	if (queryTextBox(queryData, textBox, fragmentCallback))
	return;
	}
	}

	static void collectTextBoxesInLogicalOrder(
	LineLayoutSVGInlineText textLineLayout,
	Vector<SVGInlineTextBox*>& textBoxes) {
	textBoxes.shrink(0);
	for (InlineTextBox* textBox = textLineLayout.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;

	LineLayoutSVGInlineText textLineLayout =
	LineLayoutSVGInlineText(toLayoutSVGInlineText(layoutObject));
	ASSERT(textLineLayout.style());

	// TODO(fs): Allow filtering the search earlier, since we should be
	// able to trivially reject (prune) at least some of the queries.
	collectTextBoxesInLogicalOrder(textLineLayout, textBoxes);

	for (const SVGInlineTextBox* textBox : textBoxes) {
	if (queryTextBox(queryData, textBox, fragmentCallback))
	return;
	queryData->currentOffset += textBox->len();
	}
	}
	}

	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 -= 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.
	return queryData->textBox->mapStartEndPositionsIntoFragmentCoordinates(
	fragment, startPosition, endPosition);
	}

	// numberOfCharacters() implementation
	static bool numberOfCharactersCallback(QueryData*, const SVGTextFragment&) {
	// no-op
	return false;
	}

	unsigned SVGTextQuery::numberOfCharacters() const {
	QueryData data;
	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;
	logicalQuery(m_queryRootLayoutObject, &data, textLengthCallback);
	return data.textLength;
	}

	using MetricsList = Vector<SVGTextMetrics>;

	MetricsList::const_iterator findMetricsForCharacter(
	const MetricsList& metricsList,
	const SVGTextFragment& fragment,
	unsigned startInFragment) {
	// Find the text metrics cell that starts at or contains the character at
	// \|startInFragment\|.
	MetricsList::const_iterator metrics =
	metricsList.begin() + fragment.metricsListOffset;
	unsigned fragmentOffset = 0;
	while (fragmentOffset < fragment.length) {
	fragmentOffset += metrics->length();
	if (startInFragment < fragmentOffset)
	break;
	++metrics;
	}
	ASSERT(metrics <= metricsList.end());
	return metrics;
	}

	static float calculateGlyphRange(const QueryData* queryData,
	const SVGTextFragment& fragment,
	unsigned start,
	unsigned end) {
	const MetricsList& metricsList = queryData->textLineLayout.metricsList();
	auto metrics = findMetricsForCharacter(metricsList, fragment, start);
	auto endMetrics = findMetricsForCharacter(metricsList, fragment, end);
	float glyphRange = 0;
	for (; metrics != endMetrics; ++metrics)
	glyphRange +=
	queryData->isVerticalText ? metrics->height() : metrics->width();
	return glyphRange;
	}

	// subStringLength() implementation
	struct SubStringLengthData : QueryData {
	SubStringLengthData(unsigned queryStartPosition, unsigned queryLength)
	: startPosition(queryStartPosition),
	length(queryLength),
	subStringLength(0) {}

	unsigned startPosition;
	unsigned length;

	float subStringLength;
	};

	static bool subStringLengthCallback(QueryData* queryData,
	const SVGTextFragment& fragment) {
	SubStringLengthData* data = static_cast<SubStringLengthData*>(queryData);

	int startPosition = data->startPosition;
	int endPosition = startPosition + data->length;
	if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
	startPosition, endPosition))
	return false;

	data->subStringLength +=
	calculateGlyphRange(queryData, fragment, startPosition, endPosition);
	return false;
	}

	float SVGTextQuery::subStringLength(unsigned startPosition,
	unsigned length) const {
	SubStringLengthData data(startPosition, length);
	logicalQuery(m_queryRootLayoutObject, &data, subStringLengthCallback);
	return data.subStringLength;
	}

	// startPositionOfCharacter() implementation
	struct StartPositionOfCharacterData : QueryData {
	StartPositionOfCharacterData(unsigned queryPosition)
	: position(queryPosition) {}

	unsigned position;
	FloatPoint startPosition;
	};

	static FloatPoint logicalGlyphPositionToPhysical(
	const QueryData* queryData,
	const SVGTextFragment& fragment,
	float logicalGlyphOffset) {
	float physicalGlyphOffset = logicalGlyphOffset;
	if (!queryData->textBox->isLeftToRightDirection()) {
	float fragmentExtent =
	queryData->isVerticalText ? fragment.height : fragment.width;
	physicalGlyphOffset = fragmentExtent - logicalGlyphOffset;
	}

	FloatPoint glyphPosition(fragment.x, fragment.y);
	if (queryData->isVerticalText)
	glyphPosition.move(0, physicalGlyphOffset);
	else
	glyphPosition.move(physicalGlyphOffset, 0);

	return glyphPosition;
	}

	static FloatPoint calculateGlyphPosition(const QueryData* queryData,
	const SVGTextFragment& fragment,
	unsigned offsetInFragment) {
	float glyphOffsetInDirection =
	calculateGlyphRange(queryData, fragment, 0, offsetInFragment);
	FloatPoint glyphPosition = logicalGlyphPositionToPhysical(
	queryData, fragment, glyphOffsetInDirection);
	if (fragment.isTransformed()) {
	AffineTransform fragmentTransform = fragment.buildFragmentTransform(
	SVGTextFragment::TransformIgnoringTextLength);
	glyphPosition = fragmentTransform.mapPoint(glyphPosition);
	}
	return glyphPosition;
	}

	static bool startPositionOfCharacterCallback(QueryData* queryData,
	const SVGTextFragment& fragment) {
	StartPositionOfCharacterData* data =
	static_cast<StartPositionOfCharacterData*>(queryData);

	int startPosition = data->position;
	int endPosition = startPosition + 1;
	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);
	logicalQuery(m_queryRootLayoutObject, &data,
	startPositionOfCharacterCallback);
	return data.startPosition;
	}

	// endPositionOfCharacter() implementation
	struct EndPositionOfCharacterData : QueryData {
	EndPositionOfCharacterData(unsigned queryPosition)
	: position(queryPosition) {}

	unsigned position;
	FloatPoint endPosition;
	};

	static bool endPositionOfCharacterCallback(QueryData* queryData,
	const SVGTextFragment& fragment) {
	EndPositionOfCharacterData* data =
	static_cast<EndPositionOfCharacterData*>(queryData);

	int startPosition = data->position;
	int endPosition = startPosition + 1;
	if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
	startPosition, endPosition))
	return false;

	data->endPosition = calculateGlyphPosition(queryData, fragment, endPosition);
	return true;
	}

	FloatPoint SVGTextQuery::endPositionOfCharacter(unsigned position) const {
	EndPositionOfCharacterData data(position);
	logicalQuery(m_queryRootLayoutObject, &data, endPositionOfCharacterCallback);
	return data.endPosition;
	}

	// rotationOfCharacter() implementation
	struct RotationOfCharacterData : QueryData {
	RotationOfCharacterData(unsigned queryPosition)
	: position(queryPosition), rotation(0) {}

	unsigned position;
	float rotation;
	};

	static bool rotationOfCharacterCallback(QueryData* queryData,
	const SVGTextFragment& fragment) {
	RotationOfCharacterData* data =
	static_cast<RotationOfCharacterData*>(queryData);

	int startPosition = data->position;
	int endPosition = startPosition + 1;
	if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
	startPosition, endPosition))
	return false;

	if (!fragment.isTransformed()) {
	data->rotation = 0;
	} else {
	AffineTransform fragmentTransform = fragment.buildFragmentTransform(
	SVGTextFragment::TransformIgnoringTextLength);
	fragmentTransform.scale(1 / fragmentTransform.xScale(),
	1 / fragmentTransform.yScale());
	data->rotation = clampTo<float>(
	rad2deg(atan2(fragmentTransform.b(), fragmentTransform.a())));
	}
	return true;
	}

	float SVGTextQuery::rotationOfCharacter(unsigned position) const {
	RotationOfCharacterData data(position);
	logicalQuery(m_queryRootLayoutObject, &data, rotationOfCharacterCallback);
	return data.rotation;
	}

	// extentOfCharacter() implementation
	struct ExtentOfCharacterData : QueryData {
	ExtentOfCharacterData(unsigned queryPosition) : position(queryPosition) {}

	unsigned position;
	FloatRect extent;
	};

	static FloatRect physicalGlyphExtents(const QueryData* queryData,
	const SVGTextMetrics& metrics,
	const FloatPoint& glyphPosition) {
	// TODO(fs): Negative glyph extents seems kind of weird to have, but
	// presently it can occur in some cases (like Arabic.)
	FloatRect glyphExtents(glyphPosition,
	FloatSize(std::max<float>(metrics.width(), 0),
	std::max<float>(metrics.height(), 0)));

	// If RTL, adjust the starting point to align with the LHS of the glyph
	// bounding box.
	if (!queryData->textBox->isLeftToRightDirection()) {
	if (queryData->isVerticalText)
	glyphExtents.move(0, -glyphExtents.height());
	else
	glyphExtents.move(-glyphExtents.width(), 0);
	}
	return glyphExtents;
	}

	static inline FloatRect calculateGlyphBoundaries(
	const QueryData* queryData,
	const SVGTextFragment& fragment,
	int startPosition) {
	const float scalingFactor = queryData->textLineLayout.scalingFactor();
	ASSERT(scalingFactor);
	const float baseline =
	queryData->textLineLayout.scaledFont().getFontMetrics().floatAscent() /
	scalingFactor;

	float glyphOffsetInDirection =
	calculateGlyphRange(queryData, fragment, 0, startPosition);
	FloatPoint glyphPosition = logicalGlyphPositionToPhysical(
	queryData, fragment, glyphOffsetInDirection);
	glyphPosition.move(0, -baseline);

	// Use the SVGTextMetrics computed by SVGTextMetricsBuilder.
	const MetricsList& metricsList = queryData->textLineLayout.metricsList();
	auto metrics = findMetricsForCharacter(metricsList, fragment, startPosition);

	FloatRect extent = physicalGlyphExtents(queryData, *metrics, glyphPosition);
	if (fragment.isTransformed()) {
	AffineTransform fragmentTransform = fragment.buildFragmentTransform(
	SVGTextFragment::TransformIgnoringTextLength);
	extent = fragmentTransform.mapRect(extent);
	}
	return extent;
	}

	static bool extentOfCharacterCallback(QueryData* queryData,
	const SVGTextFragment& fragment) {
	ExtentOfCharacterData* data = static_cast<ExtentOfCharacterData*>(queryData);

	int startPosition = data->position;
	int endPosition = startPosition + 1;
	if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment,
	startPosition, endPosition))
	return false;

	data->extent = calculateGlyphBoundaries(queryData, fragment, startPosition);
	return true;
	}

	FloatRect SVGTextQuery::extentOfCharacter(unsigned position) const {
	ExtentOfCharacterData data(position);
	logicalQuery(m_queryRootLayoutObject, &data, extentOfCharacterCallback);
	return data.extent;
	}

	// characterNumberAtPosition() implementation
	struct CharacterNumberAtPositionData : QueryData {
	CharacterNumberAtPositionData(const FloatPoint& queryPosition)
	: position(queryPosition), hitLayoutItem(nullptr), offsetInTextNode(0) {}

	int characterNumberWithin(const LayoutObject* queryRoot) const;

	FloatPoint position;
	LineLayoutItem hitLayoutItem;
	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 (!hitLayoutItem)
	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 (LineLayoutItem layoutItem = hitLayoutItem.previousInPreOrder(queryRoot);
	layoutItem; layoutItem = layoutItem.previousInPreOrder(queryRoot)) {
	if (!layoutItem.isSVGInlineText())
	continue;
	characterNumber += LineLayoutSVGInlineText(layoutItem).resolvedTextLength();
	}
	return characterNumber;
	}

	static unsigned logicalOffsetInTextNode(LineLayoutSVGInlineText textLineLayout,
	const SVGInlineTextBox* startTextBox,
	unsigned fragmentOffset) {
	Vector<SVGInlineTextBox*> textBoxes;
	collectTextBoxesInLogicalOrder(textLineLayout, 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);

	const float scalingFactor = data->textLineLayout.scalingFactor();
	ASSERT(scalingFactor);
	const float baseline =
	data->textLineLayout.scaledFont().getFontMetrics().floatAscent() /
	scalingFactor;

	// Test the query point against the bounds of the entire fragment first.
	if (!fragment.boundingBox(baseline).contains(data->position))
	return false;

	AffineTransform fragmentTransform = fragment.buildFragmentTransform(
	SVGTextFragment::TransformIgnoringTextLength);

	// Iterate through the glyphs in this fragment, and check if their extents
	// contain the query point.
	MetricsList::const_iterator metrics =
	data->textLineLayout.metricsList().begin() + fragment.metricsListOffset;
	unsigned fragmentOffset = 0;
	float glyphOffset = 0;
	while (fragmentOffset < fragment.length) {
	FloatPoint glyphPosition =
	logicalGlyphPositionToPhysical(data, fragment, glyphOffset);
	glyphPosition.move(0, -baseline);

	FloatRect extent = fragmentTransform.mapRect(
	physicalGlyphExtents(data, *metrics, glyphPosition));
	if (extent.contains(data->position)) {
	// Compute the character offset of the glyph within the text node.
	unsigned offsetInBox = fragment.characterOffset -
	queryData->textBox->start() + fragmentOffset;
	data->offsetInTextNode = logicalOffsetInTextNode(
	queryData->textLineLayout, queryData->textBox, offsetInBox);
	data->hitLayoutItem = LineLayoutItem(data->textLineLayout);
	return true;
	}
	fragmentOffset += metrics->length();
	glyphOffset += data->isVerticalText ? metrics->height() : metrics->width();
	++metrics;
	}
	return false;
	}

	int SVGTextQuery::characterNumberAtPosition(const FloatPoint& position) const {
	CharacterNumberAtPositionData data(position);
	spatialQuery(m_queryRootLayoutObject, &data,
	characterNumberAtPositionCallback);
	return data.characterNumberWithin(m_queryRootLayoutObject);
	}

	} // namespace blink