Migrate from ints to unsigneds when referring to indices into strings
[WebKit-https.git] / Source / WebCore / rendering / svg / SVGTextQuery.cpp
1 /*
2  * Copyright (C) Research In Motion Limited 2010-2012. All rights reserved.
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public License
15  * along with this library; see the file COPYING.LIB.  If not, write to
16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  * Boston, MA 02110-1301, USA.
18  */
19
20 #include "config.h"
21 #include "SVGTextQuery.h"
22
23 #include "FloatConversion.h"
24 #include "InlineFlowBox.h"
25 #include "RenderBlockFlow.h"
26 #include "RenderInline.h"
27 #include "RenderSVGText.h"
28 #include "SVGInlineTextBox.h"
29 #include "VisiblePosition.h"
30
31 #include <wtf/MathExtras.h>
32
33 namespace WebCore {
34
35 // Base structure for callback user data
36 struct SVGTextQuery::Data {
37     Data()
38         : isVerticalText(false)
39         , processedCharacters(0)
40         , textRenderer(0)
41         , textBox(0)
42     {
43     }
44
45     bool isVerticalText;
46     unsigned processedCharacters;
47     RenderSVGInlineText* textRenderer;
48     const SVGInlineTextBox* textBox;
49 };
50
51 static inline InlineFlowBox* flowBoxForRenderer(RenderObject* renderer)
52 {
53     if (!renderer)
54         return nullptr;
55
56     if (is<RenderBlockFlow>(*renderer)) {
57         // If we're given a block element, it has to be a RenderSVGText.
58         ASSERT(is<RenderSVGText>(*renderer));
59         RenderBlockFlow& renderBlock = downcast<RenderBlockFlow>(*renderer);
60
61         // RenderSVGText only ever contains a single line box.
62         auto flowBox = renderBlock.firstRootBox();
63         ASSERT(flowBox == renderBlock.lastRootBox());
64         return flowBox;
65     }
66
67     if (is<RenderInline>(*renderer)) {
68         // We're given a RenderSVGInline or objects that derive from it (RenderSVGTSpan / RenderSVGTextPath)
69         RenderInline& renderInline = downcast<RenderInline>(*renderer);
70
71         // RenderSVGInline only ever contains a single line box.
72         InlineFlowBox* flowBox = renderInline.firstLineBox();
73         ASSERT(flowBox == renderInline.lastLineBox());
74         return flowBox;
75     }
76
77     ASSERT_NOT_REACHED();
78     return nullptr;
79 }
80
81 SVGTextQuery::SVGTextQuery(RenderObject* renderer)
82 {
83     collectTextBoxesInFlowBox(flowBoxForRenderer(renderer));
84 }
85
86 void SVGTextQuery::collectTextBoxesInFlowBox(InlineFlowBox* flowBox)
87 {
88     if (!flowBox)
89         return;
90
91     for (InlineBox* child = flowBox->firstChild(); child; child = child->nextOnLine()) {
92         if (is<InlineFlowBox>(*child)) {
93             // Skip generated content.
94             if (!child->renderer().node())
95                 continue;
96
97             collectTextBoxesInFlowBox(downcast<InlineFlowBox>(child));
98             continue;
99         }
100
101         if (is<SVGInlineTextBox>(*child))
102             m_textBoxes.append(downcast<SVGInlineTextBox>(child));
103     }
104 }
105
106 bool SVGTextQuery::executeQuery(Data* queryData, ProcessTextFragmentCallback fragmentCallback) const
107 {
108     ASSERT(!m_textBoxes.isEmpty());
109
110     unsigned processedCharacters = 0;
111     unsigned textBoxCount = m_textBoxes.size();
112
113     // Loop over all text boxes
114     for (unsigned textBoxPosition = 0; textBoxPosition < textBoxCount; ++textBoxPosition) {
115         queryData->textBox = m_textBoxes.at(textBoxPosition);
116         queryData->textRenderer = &queryData->textBox->renderer();
117
118         queryData->isVerticalText = queryData->textRenderer->style().svgStyle().isVerticalWritingMode();
119         const Vector<SVGTextFragment>& fragments = queryData->textBox->textFragments();
120     
121         // Loop over all text fragments in this text box, firing a callback for each.
122         unsigned fragmentCount = fragments.size();
123         for (unsigned i = 0; i < fragmentCount; ++i) {
124             const SVGTextFragment& fragment = fragments.at(i);
125             if ((this->*fragmentCallback)(queryData, fragment))
126                 return true;
127
128             processedCharacters += fragment.length;
129         }
130
131         queryData->processedCharacters = processedCharacters;
132     }
133
134     return false;
135 }
136
137 bool SVGTextQuery::mapStartEndPositionsIntoFragmentCoordinates(Data* queryData, const SVGTextFragment& fragment, unsigned& startPosition, unsigned& endPosition) const
138 {
139     // Reuse the same logic used for text selection & painting, to map our query start/length into start/endPositions of the current text fragment.
140     ASSERT(startPosition >= queryData->processedCharacters);
141     ASSERT(endPosition >= queryData->processedCharacters);
142     startPosition -= queryData->processedCharacters;
143     endPosition -= queryData->processedCharacters;
144
145     if (startPosition >= endPosition)
146         return false;
147
148     modifyStartEndPositionsRespectingLigatures(queryData, startPosition, endPosition);
149     if (!queryData->textBox->mapStartEndPositionsIntoFragmentCoordinates(fragment, startPosition, endPosition))
150         return false;
151
152     ASSERT_WITH_SECURITY_IMPLICATION(startPosition < endPosition);
153     return true;
154 }
155
156 void SVGTextQuery::modifyStartEndPositionsRespectingLigatures(Data* queryData, unsigned& startPosition, unsigned& endPosition) const
157 {
158     SVGTextLayoutAttributes* layoutAttributes = queryData->textRenderer->layoutAttributes();
159     Vector<SVGTextMetrics>& textMetricsValues = layoutAttributes->textMetricsValues();
160     unsigned boxStart = queryData->textBox->start();
161     unsigned boxLength = queryData->textBox->len();
162
163     unsigned textMetricsOffset = 0;
164     unsigned textMetricsSize = textMetricsValues.size();
165
166     unsigned positionOffset = 0;
167     unsigned positionSize = layoutAttributes->context().textLength();
168
169     bool alterStartPosition = true;
170     bool alterEndPosition = true;
171
172     Optional<unsigned> lastPositionOffset;
173     for (; textMetricsOffset < textMetricsSize && positionOffset < positionSize; ++textMetricsOffset) {
174         SVGTextMetrics& metrics = textMetricsValues[textMetricsOffset];
175
176         // Advance to text box start location.
177         if (positionOffset < boxStart) {
178             positionOffset += metrics.length();
179             continue;
180         }
181
182         // Stop if we've finished processing this text box.
183         if (positionOffset >= boxStart + boxLength)
184             break;
185
186         // If the start position maps to a character in the metrics list, we don't need to modify it.
187         if (startPosition == positionOffset)
188             alterStartPosition = false;
189
190         // If the start position maps to a character in the metrics list, we don't need to modify it.
191         if (endPosition == positionOffset)
192             alterEndPosition = false;
193
194         // Detect ligatures.
195         if (lastPositionOffset && lastPositionOffset.value() - positionOffset > 1) {
196             if (alterStartPosition && startPosition > lastPositionOffset.value() && startPosition < positionOffset) {
197                 startPosition = lastPositionOffset.value();
198                 alterStartPosition = false;
199             }
200
201             if (alterEndPosition && endPosition > lastPositionOffset.value() && endPosition < positionOffset) {
202                 endPosition = positionOffset;
203                 alterEndPosition = false;
204             }
205         }
206
207         if (!alterStartPosition && !alterEndPosition)
208             break;
209
210         lastPositionOffset = positionOffset;
211         positionOffset += metrics.length();
212     }
213
214     if (!alterStartPosition && !alterEndPosition)
215         return;
216
217     if (lastPositionOffset && lastPositionOffset.value() - positionOffset > 1) {
218         if (alterStartPosition && startPosition > lastPositionOffset.value() && startPosition < positionOffset)
219             startPosition = lastPositionOffset.value();
220
221         if (alterEndPosition && endPosition > lastPositionOffset.value() && endPosition < positionOffset)
222             endPosition = positionOffset;
223     }
224 }
225
226 // numberOfCharacters() implementation
227 bool SVGTextQuery::numberOfCharactersCallback(Data*, const SVGTextFragment&) const
228 {
229     // no-op
230     return false;
231 }
232
233 unsigned SVGTextQuery::numberOfCharacters() const
234 {
235     if (m_textBoxes.isEmpty())
236         return 0;
237
238     Data data;
239     executeQuery(&data, &SVGTextQuery::numberOfCharactersCallback);
240     return data.processedCharacters;
241 }
242
243 // textLength() implementation
244 struct TextLengthData : SVGTextQuery::Data {
245     TextLengthData()
246         : textLength(0)
247     {
248     }
249
250     float textLength;
251 };
252
253 bool SVGTextQuery::textLengthCallback(Data* queryData, const SVGTextFragment& fragment) const
254 {
255     TextLengthData* data = static_cast<TextLengthData*>(queryData);
256     data->textLength += queryData->isVerticalText ? fragment.height : fragment.width;
257     return false;
258 }
259
260 float SVGTextQuery::textLength() const
261 {
262     if (m_textBoxes.isEmpty())
263         return 0;
264
265     TextLengthData data;
266     executeQuery(&data, &SVGTextQuery::textLengthCallback);
267     return data.textLength;
268 }
269
270 // subStringLength() implementation
271 struct SubStringLengthData : SVGTextQuery::Data {
272     SubStringLengthData(unsigned queryStartPosition, unsigned queryLength)
273         : startPosition(queryStartPosition)
274         , length(queryLength)
275         , subStringLength(0)
276     {
277     }
278
279     unsigned startPosition;
280     unsigned length;
281
282     float subStringLength;
283 };
284
285 bool SVGTextQuery::subStringLengthCallback(Data* queryData, const SVGTextFragment& fragment) const
286 {
287     SubStringLengthData* data = static_cast<SubStringLengthData*>(queryData);
288
289     unsigned startPosition = data->startPosition;
290     unsigned endPosition = startPosition + data->length;
291     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
292         return false;
293
294     SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(*queryData->textRenderer, fragment.characterOffset + startPosition, endPosition - startPosition);
295     data->subStringLength += queryData->isVerticalText ? metrics.height() : metrics.width();
296     return false;
297 }
298
299 float SVGTextQuery::subStringLength(unsigned startPosition, unsigned length) const
300 {
301     if (m_textBoxes.isEmpty())
302         return 0;
303
304     SubStringLengthData data(startPosition, length);
305     executeQuery(&data, &SVGTextQuery::subStringLengthCallback);
306     return data.subStringLength;
307 }
308
309 // startPositionOfCharacter() implementation
310 struct StartPositionOfCharacterData : SVGTextQuery::Data {
311     StartPositionOfCharacterData(unsigned queryPosition)
312         : position(queryPosition)
313     {
314     }
315
316     unsigned position;
317     FloatPoint startPosition;
318 };
319
320 bool SVGTextQuery::startPositionOfCharacterCallback(Data* queryData, const SVGTextFragment& fragment) const
321 {
322     StartPositionOfCharacterData* data = static_cast<StartPositionOfCharacterData*>(queryData);
323
324     unsigned startPosition = data->position;
325     unsigned endPosition = startPosition + 1;
326     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
327         return false;
328
329     data->startPosition = FloatPoint(fragment.x, fragment.y);
330
331     if (startPosition) {
332         SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(*queryData->textRenderer, fragment.characterOffset, startPosition);
333         if (queryData->isVerticalText)
334             data->startPosition.move(0, metrics.height());
335         else
336             data->startPosition.move(metrics.width(), 0);
337     }
338
339     AffineTransform fragmentTransform;
340     fragment.buildFragmentTransform(fragmentTransform, SVGTextFragment::TransformIgnoringTextLength);
341     if (fragmentTransform.isIdentity())
342         return true;
343
344     data->startPosition = fragmentTransform.mapPoint(data->startPosition);
345     return true;
346 }
347
348 SVGPoint SVGTextQuery::startPositionOfCharacter(unsigned position) const
349 {
350     if (m_textBoxes.isEmpty())
351         return SVGPoint();
352
353     StartPositionOfCharacterData data(position);
354     executeQuery(&data, &SVGTextQuery::startPositionOfCharacterCallback);
355     return data.startPosition;
356 }
357
358 // endPositionOfCharacter() implementation
359 struct EndPositionOfCharacterData : SVGTextQuery::Data {
360     EndPositionOfCharacterData(unsigned queryPosition)
361         : position(queryPosition)
362     {
363     }
364
365     unsigned position;
366     FloatPoint endPosition;
367 };
368
369 bool SVGTextQuery::endPositionOfCharacterCallback(Data* queryData, const SVGTextFragment& fragment) const
370 {
371     EndPositionOfCharacterData* data = static_cast<EndPositionOfCharacterData*>(queryData);
372
373     unsigned startPosition = data->position;
374     unsigned endPosition = startPosition + 1;
375     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
376         return false;
377
378     data->endPosition = FloatPoint(fragment.x, fragment.y);
379
380     SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(*queryData->textRenderer, fragment.characterOffset, startPosition + 1);
381     if (queryData->isVerticalText)
382         data->endPosition.move(0, metrics.height());
383     else
384         data->endPosition.move(metrics.width(), 0);
385
386     AffineTransform fragmentTransform;
387     fragment.buildFragmentTransform(fragmentTransform, SVGTextFragment::TransformIgnoringTextLength);
388     if (fragmentTransform.isIdentity())
389         return true;
390
391     data->endPosition = fragmentTransform.mapPoint(data->endPosition);
392     return true;
393 }
394
395 SVGPoint SVGTextQuery::endPositionOfCharacter(unsigned position) const
396 {
397     if (m_textBoxes.isEmpty())
398         return SVGPoint();
399
400     EndPositionOfCharacterData data(position);
401     executeQuery(&data, &SVGTextQuery::endPositionOfCharacterCallback);
402     return data.endPosition;
403 }
404
405 // rotationOfCharacter() implementation
406 struct RotationOfCharacterData : SVGTextQuery::Data {
407     RotationOfCharacterData(unsigned queryPosition)
408         : position(queryPosition)
409         , rotation(0)
410     {
411     }
412
413     unsigned position;
414     float rotation;
415 };
416
417 bool SVGTextQuery::rotationOfCharacterCallback(Data* queryData, const SVGTextFragment& fragment) const
418 {
419     RotationOfCharacterData* data = static_cast<RotationOfCharacterData*>(queryData);
420
421     unsigned startPosition = data->position;
422     unsigned endPosition = startPosition + 1;
423     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
424         return false;
425
426     AffineTransform fragmentTransform;
427     fragment.buildFragmentTransform(fragmentTransform, SVGTextFragment::TransformIgnoringTextLength);
428     if (fragmentTransform.isIdentity())
429         data->rotation = 0;
430     else {
431         fragmentTransform.scale(1 / fragmentTransform.xScale(), 1 / fragmentTransform.yScale());
432         data->rotation = narrowPrecisionToFloat(rad2deg(atan2(fragmentTransform.b(), fragmentTransform.a())));
433     }
434
435     return true;
436 }
437
438 float SVGTextQuery::rotationOfCharacter(unsigned position) const
439 {
440     if (m_textBoxes.isEmpty())
441         return 0;
442
443     RotationOfCharacterData data(position);
444     executeQuery(&data, &SVGTextQuery::rotationOfCharacterCallback);
445     return data.rotation;
446 }
447
448 // extentOfCharacter() implementation
449 struct ExtentOfCharacterData : SVGTextQuery::Data {
450     ExtentOfCharacterData(unsigned queryPosition)
451         : position(queryPosition)
452     {
453     }
454
455     unsigned position;
456     FloatRect extent;
457 };
458
459 static inline void calculateGlyphBoundaries(SVGTextQuery::Data* queryData, const SVGTextFragment& fragment, unsigned startPosition, FloatRect& extent)
460 {
461     float scalingFactor = queryData->textRenderer->scalingFactor();
462     ASSERT(scalingFactor);
463
464     extent.setLocation(FloatPoint(fragment.x, fragment.y - queryData->textRenderer->scaledFont().fontMetrics().floatAscent() / scalingFactor));
465
466     if (startPosition) {
467         SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(*queryData->textRenderer, fragment.characterOffset, startPosition);
468         if (queryData->isVerticalText)
469             extent.move(0, metrics.height());
470         else
471             extent.move(metrics.width(), 0);
472     }
473
474     SVGTextMetrics metrics = SVGTextMetrics::measureCharacterRange(*queryData->textRenderer, fragment.characterOffset + startPosition, 1);
475     extent.setSize(FloatSize(metrics.width(), metrics.height()));
476
477     AffineTransform fragmentTransform;
478     fragment.buildFragmentTransform(fragmentTransform, SVGTextFragment::TransformIgnoringTextLength);
479     if (fragmentTransform.isIdentity())
480         return;
481
482     extent = fragmentTransform.mapRect(extent);
483 }
484
485 bool SVGTextQuery::extentOfCharacterCallback(Data* queryData, const SVGTextFragment& fragment) const
486 {
487     ExtentOfCharacterData* data = static_cast<ExtentOfCharacterData*>(queryData);
488
489     unsigned startPosition = data->position;
490     unsigned endPosition = startPosition + 1;
491     if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
492         return false;
493
494     calculateGlyphBoundaries(queryData, fragment, startPosition, data->extent);
495     return true;
496 }
497
498 FloatRect SVGTextQuery::extentOfCharacter(unsigned position) const
499 {
500     if (m_textBoxes.isEmpty())
501         return FloatRect();
502
503     ExtentOfCharacterData data(position);
504     executeQuery(&data, &SVGTextQuery::extentOfCharacterCallback);
505     return data.extent;
506 }
507
508 // characterNumberAtPosition() implementation
509 struct CharacterNumberAtPositionData : SVGTextQuery::Data {
510     CharacterNumberAtPositionData(const FloatPoint& queryPosition)
511         : position(queryPosition)
512     {
513     }
514
515     FloatPoint position;
516 };
517
518 bool SVGTextQuery::characterNumberAtPositionCallback(Data* queryData, const SVGTextFragment& fragment) const
519 {
520     CharacterNumberAtPositionData* data = static_cast<CharacterNumberAtPositionData*>(queryData);
521
522     FloatRect extent;
523     for (unsigned i = 0; i < fragment.length; ++i) {
524         unsigned startPosition = data->processedCharacters + i;
525         unsigned endPosition = startPosition + 1;
526         if (!mapStartEndPositionsIntoFragmentCoordinates(queryData, fragment, startPosition, endPosition))
527             continue;
528
529         calculateGlyphBoundaries(queryData, fragment, startPosition, extent);
530         if (extent.contains(data->position)) {
531             data->processedCharacters += i;
532             return true;
533         }
534     }
535
536     return false;
537 }
538
539 int SVGTextQuery::characterNumberAtPosition(const SVGPoint& position) const
540 {
541     if (m_textBoxes.isEmpty())
542         return -1;
543
544     CharacterNumberAtPositionData data(position);
545     if (!executeQuery(&data, &SVGTextQuery::characterNumberAtPositionCallback))
546         return -1;
547
548     return data.processedCharacters;
549 }
550
551 }