Synchronize MathML WPT tests against upstream
[WebKit-https.git] / Source / WebCore / editing / VisibleUnits.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "VisibleUnits.h"
28
29 #include "Document.h"
30 #include "Editing.h"
31 #include "HTMLBRElement.h"
32 #include "HTMLElement.h"
33 #include "HTMLNames.h"
34 #include "InlineTextBox.h"
35 #include "NodeTraversal.h"
36 #include "RenderBlockFlow.h"
37 #include "RenderObject.h"
38 #include "RenderedPosition.h"
39 #include "Text.h"
40 #include "TextBoundaries.h"
41 #include "TextIterator.h"
42 #include "VisibleSelection.h"
43 #include <unicode/ubrk.h>
44 #include <wtf/text/TextBreakIterator.h>
45
46 namespace WebCore {
47
48 using namespace HTMLNames;
49 using namespace WTF::Unicode;
50
51 static Node* previousLeafWithSameEditability(Node* node, EditableType editableType)
52 {
53     bool editable = hasEditableStyle(*node, editableType);
54     node = previousLeafNode(node);
55     while (node) {
56         if (editable == hasEditableStyle(*node, editableType))
57             return node;
58         node = previousLeafNode(node);
59     }
60     return nullptr;
61 }
62
63 static Node* nextLeafWithSameEditability(Node* node, EditableType editableType)
64 {
65     if (!node)
66         return nullptr;
67     
68     bool editable = hasEditableStyle(*node, editableType);
69     node = nextLeafNode(node);
70     while (node) {
71         if (editable == hasEditableStyle(*node, editableType))
72             return node;
73         node = nextLeafNode(node);
74     }
75     return nullptr;
76 }
77
78 // FIXME: consolidate with code in previousLinePosition.
79 static Position previousRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
80 {
81     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
82     Node* previousNode = previousLeafWithSameEditability(node, editableType);
83
84     while (previousNode && (!previousNode->renderer() || inSameLine(firstPositionInOrBeforeNode(previousNode), visiblePosition)))
85         previousNode = previousLeafWithSameEditability(previousNode, editableType);
86
87     while (previousNode && !previousNode->isShadowRoot()) {
88         if (highestEditableRoot(firstPositionInOrBeforeNode(previousNode), editableType) != highestRoot)
89             break;
90
91         Position pos = previousNode->hasTagName(brTag) ? positionBeforeNode(previousNode) :
92             createLegacyEditingPosition(previousNode, caretMaxOffset(*previousNode));
93         
94         if (pos.isCandidate())
95             return pos;
96
97         previousNode = previousLeafWithSameEditability(previousNode, editableType);
98     }
99     return Position();
100 }
101
102 static Position nextRootInlineBoxCandidatePosition(Node* node, const VisiblePosition& visiblePosition, EditableType editableType)
103 {
104     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent(), editableType);
105     Node* nextNode = nextLeafWithSameEditability(node, editableType);
106     while (nextNode && (!nextNode->renderer() || inSameLine(firstPositionInOrBeforeNode(nextNode), visiblePosition)))
107         nextNode = nextLeafWithSameEditability(nextNode, ContentIsEditable);
108
109     while (nextNode && !nextNode->isShadowRoot()) {
110         if (highestEditableRoot(firstPositionInOrBeforeNode(nextNode), editableType) != highestRoot)
111             break;
112
113         Position pos;
114         pos = createLegacyEditingPosition(nextNode, caretMinOffset(*nextNode));
115         
116         if (pos.isCandidate())
117             return pos;
118
119         nextNode = nextLeafWithSameEditability(nextNode, editableType);
120     }
121     return Position();
122 }
123
124 class CachedLogicallyOrderedLeafBoxes {
125 public:
126     CachedLogicallyOrderedLeafBoxes();
127
128     const InlineBox* previousTextOrLineBreakBox(const RootInlineBox*, const InlineBox*);
129     const InlineBox* nextTextOrLineBreakBox(const RootInlineBox*, const InlineBox*);
130
131     size_t size() const { return m_leafBoxes.size(); }
132     const InlineBox* firstBox() const { return m_leafBoxes[0]; }
133
134 private:
135     const Vector<InlineBox*>& collectBoxes(const RootInlineBox*);
136     int boxIndexInLeaves(const InlineBox*) const;
137
138     const RootInlineBox* m_rootInlineBox { nullptr };
139     Vector<InlineBox*> m_leafBoxes;
140 };
141
142 CachedLogicallyOrderedLeafBoxes::CachedLogicallyOrderedLeafBoxes()
143 {
144 }
145
146 const InlineBox* CachedLogicallyOrderedLeafBoxes::previousTextOrLineBreakBox(const RootInlineBox* root, const InlineBox* box)
147 {
148     if (!root)
149         return nullptr;
150
151     collectBoxes(root);
152
153     // If box is null, root is box's previous RootInlineBox, and previousBox is the last logical box in root.
154     int boxIndex = m_leafBoxes.size() - 1;
155     if (box)
156         boxIndex = boxIndexInLeaves(box) - 1;
157
158     for (int i = boxIndex; i >= 0; --i) {
159         InlineBox* box = m_leafBoxes[i];
160         if (box->isInlineTextBox() || box->renderer().isBR())
161             return box;
162     }
163
164     return nullptr;
165 }
166
167 const InlineBox* CachedLogicallyOrderedLeafBoxes::nextTextOrLineBreakBox(const RootInlineBox* root, const InlineBox* box)
168 {
169     if (!root)
170         return nullptr;
171
172     collectBoxes(root);
173
174     // If box is null, root is box's next RootInlineBox, and nextBox is the first logical box in root.
175     // Otherwise, root is box's RootInlineBox, and nextBox is the next logical box in the same line.
176     size_t nextBoxIndex = 0;
177     if (box)
178         nextBoxIndex = boxIndexInLeaves(box) + 1;
179
180     for (size_t i = nextBoxIndex; i < m_leafBoxes.size(); ++i) {
181         InlineBox* box = m_leafBoxes[i];
182         if (box->isInlineTextBox() || box->renderer().isBR())
183             return box;
184     }
185
186     return nullptr;
187 }
188
189 const Vector<InlineBox*>& CachedLogicallyOrderedLeafBoxes::collectBoxes(const RootInlineBox* root)
190 {
191     if (m_rootInlineBox != root) {
192         m_rootInlineBox = root;
193         m_leafBoxes.clear();
194         root->collectLeafBoxesInLogicalOrder(m_leafBoxes);
195     }
196     return m_leafBoxes;
197 }
198
199 int CachedLogicallyOrderedLeafBoxes::boxIndexInLeaves(const InlineBox* box) const
200 {
201     for (size_t i = 0; i < m_leafBoxes.size(); ++i) {
202         if (box == m_leafBoxes[i])
203             return i;
204     }
205     return 0;
206 }
207
208 static const InlineBox* logicallyPreviousBox(const VisiblePosition& visiblePosition, const InlineBox* textBox,
209     bool& previousBoxInDifferentLine, CachedLogicallyOrderedLeafBoxes& leafBoxes)
210 {
211     const InlineBox* startBox = textBox;
212
213     const InlineBox* previousBox = leafBoxes.previousTextOrLineBreakBox(&startBox->root(), textBox);
214     if (previousBox)
215         return previousBox;
216
217     previousBox = leafBoxes.previousTextOrLineBreakBox(startBox->root().prevRootBox(), 0);
218     if (previousBox)
219         return previousBox;
220
221     while (1) {
222         Node* startNode = startBox->renderer().nonPseudoNode();
223         if (!startNode)
224             break;
225
226         Position position = previousRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
227         if (position.isNull())
228             break;
229
230         RenderedPosition renderedPosition(position, DOWNSTREAM);
231         RootInlineBox* previousRoot = renderedPosition.rootBox();
232         if (!previousRoot)
233             break;
234
235         previousBox = leafBoxes.previousTextOrLineBreakBox(previousRoot, &startBox->root() == previousRoot ? startBox : nullptr);
236         if (previousBox) {
237             previousBoxInDifferentLine = true;
238             return previousBox;
239         }
240
241         if (!leafBoxes.size())
242             break;
243         startBox = leafBoxes.firstBox();
244     }
245     return 0;
246 }
247
248
249 static const InlineBox* logicallyNextBox(const VisiblePosition& visiblePosition, const InlineBox* textBox,
250     bool& nextBoxInDifferentLine, CachedLogicallyOrderedLeafBoxes& leafBoxes)
251 {
252     const InlineBox* startBox = textBox;
253
254     const InlineBox* nextBox = leafBoxes.nextTextOrLineBreakBox(&startBox->root(), textBox);
255     if (nextBox)
256         return nextBox;
257
258     nextBox = leafBoxes.nextTextOrLineBreakBox(startBox->root().nextRootBox(), 0);
259     if (nextBox)
260         return nextBox;
261
262     while (1) {
263         Node* startNode = startBox->renderer().nonPseudoNode();
264         if (!startNode)
265             break;
266
267         Position position = nextRootInlineBoxCandidatePosition(startNode, visiblePosition, ContentIsEditable);
268         if (position.isNull())
269             break;
270
271         RenderedPosition renderedPosition(position, DOWNSTREAM);
272         RootInlineBox* nextRoot = renderedPosition.rootBox();
273         if (!nextRoot)
274             break;
275
276         nextBox = leafBoxes.nextTextOrLineBreakBox(nextRoot, &startBox->root() == nextRoot ? startBox : nullptr);
277         if (nextBox) {
278             nextBoxInDifferentLine = true;
279             return nextBox;
280         }
281
282         if (!leafBoxes.size())
283             break;
284         startBox = leafBoxes.firstBox();
285     }
286     return 0;
287 }
288
289 static UBreakIterator* wordBreakIteratorForMinOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
290     int& previousBoxLength, bool& previousBoxInDifferentLine, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
291 {
292     previousBoxInDifferentLine = false;
293
294     const InlineBox* previousBox = logicallyPreviousBox(visiblePosition, textBox, previousBoxInDifferentLine, leafBoxes);
295     while (previousBox && !is<InlineTextBox>(previousBox)) {
296         ASSERT(previousBox->renderer().isBR());
297         previousBoxInDifferentLine = true;
298         previousBox = logicallyPreviousBox(visiblePosition, previousBox, previousBoxInDifferentLine, leafBoxes);
299     }
300
301     string.clear();
302
303     if (is<InlineTextBox>(previousBox)) {
304         const auto& previousTextBox = downcast<InlineTextBox>(*previousBox);
305         previousBoxLength = previousTextBox.len();
306         append(string, StringView(previousTextBox.renderer().text()).substring(previousTextBox.start(), previousBoxLength));
307     }
308     append(string, StringView(textBox->renderer().text()).substring(textBox->start(), textBox->len()));
309
310     return wordBreakIterator(StringView(string.data(), string.size()));
311 }
312
313 static UBreakIterator* wordBreakIteratorForMaxOffsetBoundary(const VisiblePosition& visiblePosition, const InlineTextBox* textBox,
314     bool& nextBoxInDifferentLine, Vector<UChar, 1024>& string, CachedLogicallyOrderedLeafBoxes& leafBoxes)
315 {
316     nextBoxInDifferentLine = false;
317
318     const InlineBox* nextBox = logicallyNextBox(visiblePosition, textBox, nextBoxInDifferentLine, leafBoxes);
319     while (nextBox && !is<InlineTextBox>(nextBox)) {
320         ASSERT(nextBox->renderer().isBR());
321         nextBoxInDifferentLine = true;
322         nextBox = logicallyNextBox(visiblePosition, nextBox, nextBoxInDifferentLine, leafBoxes);
323     }
324
325     string.clear();
326     append(string, StringView(textBox->renderer().text()).substring(textBox->start(), textBox->len()));
327     if (is<InlineTextBox>(nextBox)) {
328         const auto& nextTextBox = downcast<InlineTextBox>(*nextBox);
329         append(string, StringView(nextTextBox.renderer().text()).substring(nextTextBox.start(), nextTextBox.len()));
330     }
331
332     return wordBreakIterator(StringView(string.data(), string.size()));
333 }
334
335 static bool isLogicalStartOfWord(UBreakIterator* iter, int position, bool hardLineBreak)
336 {
337     bool boundary = hardLineBreak ? true : ubrk_isBoundary(iter, position);
338     if (!boundary)
339         return false;
340
341     ubrk_following(iter, position);
342     // isWordTextBreak returns true after moving across a word and false after moving across a punctuation/space.
343     return isWordTextBreak(iter);
344 }
345
346 static bool islogicalEndOfWord(UBreakIterator* iter, int position, bool hardLineBreak)
347 {
348     bool boundary = ubrk_isBoundary(iter, position);
349     return (hardLineBreak || boundary) && isWordTextBreak(iter);
350 }
351
352 enum CursorMovementDirection { MoveLeft, MoveRight };
353
354 static VisiblePosition visualWordPosition(const VisiblePosition& visiblePosition, CursorMovementDirection direction, 
355     bool skipsSpaceWhenMovingRight)
356 {
357     if (visiblePosition.isNull())
358         return VisiblePosition();
359
360     TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
361     InlineBox* previouslyVisitedBox = nullptr;
362     VisiblePosition current = visiblePosition;
363     Optional<VisiblePosition> previousPosition;
364     UBreakIterator* iter = nullptr;
365
366     CachedLogicallyOrderedLeafBoxes leafBoxes;
367     Vector<UChar, 1024> string;
368
369     while (1) {
370         VisiblePosition adjacentCharacterPosition = direction == MoveRight ? current.right(true) : current.left(true); 
371         if (adjacentCharacterPosition == current || adjacentCharacterPosition.isNull())
372             return VisiblePosition();
373         // FIXME: This is a workaround for webkit.org/b/167138.
374         if (previousPosition && adjacentCharacterPosition == previousPosition.value())
375             return VisiblePosition();
376     
377         InlineBox* box;
378         int offsetInBox;
379         adjacentCharacterPosition.deepEquivalent().getInlineBoxAndOffset(UPSTREAM, box, offsetInBox);
380     
381         if (!box)
382             break;
383         if (!is<InlineTextBox>(*box)) {
384             current = adjacentCharacterPosition;
385             continue;
386         }
387
388         InlineTextBox& textBox = downcast<InlineTextBox>(*box);
389         int previousBoxLength = 0;
390         bool previousBoxInDifferentLine = false;
391         bool nextBoxInDifferentLine = false;
392         bool movingIntoNewBox = previouslyVisitedBox != box;
393
394         if (offsetInBox == box->caretMinOffset())
395             iter = wordBreakIteratorForMinOffsetBoundary(adjacentCharacterPosition, &textBox, previousBoxLength, previousBoxInDifferentLine, string, leafBoxes);
396         else if (offsetInBox == box->caretMaxOffset())
397             iter = wordBreakIteratorForMaxOffsetBoundary(adjacentCharacterPosition, &textBox, nextBoxInDifferentLine, string, leafBoxes);
398         else if (movingIntoNewBox) {
399             iter = wordBreakIterator(StringView(textBox.renderer().text()).substring(textBox.start(), textBox.len()));
400             previouslyVisitedBox = box;
401         }
402
403         if (!iter)
404             break;
405
406         ubrk_first(iter);
407         int offsetInIterator = offsetInBox - textBox.start() + previousBoxLength;
408
409         bool isWordBreak;
410         bool boxHasSameDirectionalityAsBlock = box->direction() == blockDirection;
411         bool movingBackward = (direction == MoveLeft && box->direction() == TextDirection::LTR) || (direction == MoveRight && box->direction() == TextDirection::RTL);
412         if ((skipsSpaceWhenMovingRight && boxHasSameDirectionalityAsBlock)
413             || (!skipsSpaceWhenMovingRight && movingBackward)) {
414             bool logicalStartInRenderer = offsetInBox == static_cast<int>(textBox.start()) && previousBoxInDifferentLine;
415             isWordBreak = isLogicalStartOfWord(iter, offsetInIterator, logicalStartInRenderer);
416             if (isWordBreak && offsetInBox == box->caretMaxOffset() && nextBoxInDifferentLine)
417                 isWordBreak = false;
418         } else {
419             bool logicalEndInRenderer = offsetInBox == static_cast<int>(textBox.start() + textBox.len()) && nextBoxInDifferentLine;
420             isWordBreak = islogicalEndOfWord(iter, offsetInIterator, logicalEndInRenderer);
421             if (isWordBreak && offsetInBox == box->caretMinOffset() && previousBoxInDifferentLine)
422                 isWordBreak = false;
423         }      
424
425         if (isWordBreak)
426             return adjacentCharacterPosition;
427     
428         previousPosition = current;
429         current = adjacentCharacterPosition;
430     }
431     return VisiblePosition();
432 }
433
434 VisiblePosition leftWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
435 {
436     VisiblePosition leftWordBreak = visualWordPosition(visiblePosition, MoveLeft, skipsSpaceWhenMovingRight);
437     leftWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(leftWordBreak);
438     
439     // FIXME: How should we handle a non-editable position?
440     if (leftWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
441         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
442         leftWordBreak = blockDirection == TextDirection::LTR ? startOfEditableContent(visiblePosition) : endOfEditableContent(visiblePosition);
443     }
444     return leftWordBreak;
445 }
446
447 VisiblePosition rightWordPosition(const VisiblePosition& visiblePosition, bool skipsSpaceWhenMovingRight)
448 {
449     VisiblePosition rightWordBreak = visualWordPosition(visiblePosition, MoveRight, skipsSpaceWhenMovingRight);
450     rightWordBreak = visiblePosition.honorEditingBoundaryAtOrBefore(rightWordBreak);
451
452     // FIXME: How should we handle a non-editable position?
453     if (rightWordBreak.isNull() && isEditablePosition(visiblePosition.deepEquivalent())) {
454         TextDirection blockDirection = directionOfEnclosingBlock(visiblePosition.deepEquivalent());
455         rightWordBreak = blockDirection == TextDirection::LTR ? endOfEditableContent(visiblePosition) : startOfEditableContent(visiblePosition);
456     }
457     return rightWordBreak;
458 }
459
460
461 static void prepend(Vector<UChar, 1024>& buffer, StringView string)
462 {
463     unsigned oldSize = buffer.size();
464     unsigned length = string.length();
465     buffer.grow(oldSize + length);
466     memmove(buffer.data() + length, buffer.data(), oldSize * sizeof(UChar));
467     for (unsigned i = 0; i < length; ++i)
468         buffer[i] = string[i];
469 }
470
471 static void prependRepeatedCharacter(Vector<UChar, 1024>& buffer, UChar character, unsigned count)
472 {
473     unsigned oldSize = buffer.size();
474     buffer.grow(oldSize + count);
475     memmove(buffer.data() + count, buffer.data(), oldSize * sizeof(UChar));
476     for (unsigned i = 0; i < count; ++i)
477         buffer[i] = character;
478 }
479
480 static void appendRepeatedCharacter(Vector<UChar, 1024>& buffer, UChar character, unsigned count)
481 {
482     unsigned oldSize = buffer.size();
483     buffer.grow(oldSize + count);
484     for (unsigned i = 0; i < count; ++i)
485         buffer[oldSize + i] = character;
486 }
487
488 unsigned suffixLengthForRange(const Range& forwardsScanRange, Vector<UChar, 1024>& string)
489 {
490     unsigned suffixLength = 0;
491     TextIterator forwardsIterator(&forwardsScanRange);
492     while (!forwardsIterator.atEnd()) {
493         StringView text = forwardsIterator.text();
494         unsigned i = endOfFirstWordBoundaryContext(text);
495         append(string, text.substring(0, i));
496         suffixLength += i;
497         if (i < text.length())
498             break;
499         forwardsIterator.advance();
500     }
501     return suffixLength;
502 }
503
504 unsigned prefixLengthForRange(const Range& backwardsScanRange, Vector<UChar, 1024>& string)
505 {
506     unsigned prefixLength = 0;
507     SimplifiedBackwardsTextIterator backwardsIterator(backwardsScanRange);
508     while (!backwardsIterator.atEnd()) {
509         StringView text = backwardsIterator.text();
510         int i = startOfLastWordBoundaryContext(text);
511         prepend(string, text.substring(i));
512         prefixLength += text.length() - i;
513         if (i > 0)
514             break;
515         backwardsIterator.advance();
516     }
517     return prefixLength;
518 }
519
520 unsigned backwardSearchForBoundaryWithTextIterator(SimplifiedBackwardsTextIterator& it, Vector<UChar, 1024>& string, unsigned suffixLength, BoundarySearchFunction searchFunction)
521 {
522     unsigned next = 0;
523     bool needMoreContext = false;
524     while (!it.atEnd()) {
525         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style().textSecurity() != TextSecurity::None;
526         // iterate to get chunks until the searchFunction returns a non-zero value.
527         if (!inTextSecurityMode)
528             prepend(string, it.text());
529         else {
530             // Treat bullets used in the text security mode as regular characters when looking for boundaries
531             prependRepeatedCharacter(string, 'x', it.text().length());
532         }
533         if (string.size() > suffixLength) {
534             next = searchFunction(StringView(string.data(), string.size()), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
535             if (next > 1) // FIXME: This is a work around for https://webkit.org/b/115070. We need to provide more contexts in general case.
536                 break;
537         }
538         it.advance();
539     }
540     if (needMoreContext && string.size() > suffixLength) {
541         // The last search returned the beginning of the buffer and asked for more context,
542         // but there is no earlier text. Force a search with what's available.
543         next = searchFunction(StringView(string.data(), string.size()), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
544         ASSERT(!needMoreContext);
545     }
546     
547     return next;
548 }
549
550 unsigned forwardSearchForBoundaryWithTextIterator(TextIterator& it, Vector<UChar, 1024>& string, unsigned prefixLength, BoundarySearchFunction searchFunction)
551 {
552     unsigned next = 0;
553     bool needMoreContext = false;
554     while (!it.atEnd()) {
555         bool inTextSecurityMode = it.node() && it.node()->renderer() && it.node()->renderer()->style().textSecurity() != TextSecurity::None;
556         // Keep asking the iterator for chunks until the search function
557         // returns an end value not equal to the length of the string passed to it.
558         if (!inTextSecurityMode)
559             append(string, it.text());
560         else {
561             // Treat bullets used in the text security mode as regular characters when looking for boundaries
562             appendRepeatedCharacter(string, 'x', it.text().length());
563         }
564         if (string.size() > prefixLength) {
565             next = searchFunction(StringView(string.data(), string.size()), prefixLength, MayHaveMoreContext, needMoreContext);
566             if (next != string.size())
567                 break;
568         }
569         it.advance();
570     }
571     if (needMoreContext && string.size() > prefixLength) {
572         // The last search returned the end of the buffer and asked for more context,
573         // but there is no further text. Force a search with what's available.
574         next = searchFunction(StringView(string.data(), string.size()), prefixLength, DontHaveMoreContext, needMoreContext);
575         ASSERT(!needMoreContext);
576     }
577     
578     return next;
579 }
580
581 enum class NeedsContextAtParagraphStart { Yes, No };
582 static VisiblePosition previousBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction,
583     NeedsContextAtParagraphStart needsContextAtParagraphStart = NeedsContextAtParagraphStart::No)
584 {
585     Position pos = c.deepEquivalent();
586     Node* boundary = pos.parentEditingBoundary();
587     if (!boundary)
588         return VisiblePosition();
589
590     Document& boundaryDocument = boundary->document();
591     Position start = createLegacyEditingPosition(boundary, 0).parentAnchoredEquivalent();
592     Position end = pos.parentAnchoredEquivalent();
593
594     if (start.isNull() || end.isNull())
595         return VisiblePosition();
596
597     Ref<Range> searchRange = Range::create(boundaryDocument);
598     
599     Vector<UChar, 1024> string;
600     unsigned suffixLength = 0;
601
602     if (needsContextAtParagraphStart == NeedsContextAtParagraphStart::Yes && isStartOfParagraph(c)) {
603         auto forwardsScanRange = boundaryDocument.createRange();
604         auto endOfCurrentParagraph = endOfParagraph(c);
605         auto result = forwardsScanRange->setEnd(endOfCurrentParagraph.deepEquivalent());
606         if (result.hasException())
607             return { };
608         result = forwardsScanRange->setStart(start);
609         if (result.hasException())
610             return { };
611         for (TextIterator forwardsIterator(forwardsScanRange.ptr()); !forwardsIterator.atEnd(); forwardsIterator.advance())
612             append(string, forwardsIterator.text());
613         suffixLength = string.size();
614     } else if (requiresContextForWordBoundary(c.characterBefore())) {
615         auto forwardsScanRange = boundaryDocument.createRange();
616         auto result = forwardsScanRange->setEndAfter(*boundary);
617         if (result.hasException())
618             return { };
619         result = forwardsScanRange->setStart(*end.deprecatedNode(), end.deprecatedEditingOffset());
620         if (result.hasException())
621             return { };
622         suffixLength = suffixLengthForRange(forwardsScanRange, string);
623     }
624
625     auto result = searchRange->setStart(*start.deprecatedNode(), start.deprecatedEditingOffset());
626     if (result.hasException())
627         return { };
628     result = searchRange->setEnd(*end.deprecatedNode(), end.deprecatedEditingOffset());
629     if (result.hasException())
630         return { };
631
632     SimplifiedBackwardsTextIterator it(searchRange);
633     unsigned next = backwardSearchForBoundaryWithTextIterator(it, string, suffixLength, searchFunction);
634
635     if (!next)
636         return VisiblePosition(it.atEnd() ? searchRange->startPosition() : pos, DOWNSTREAM);
637
638     Node& node = it.atEnd() ? searchRange->startContainer() : it.range()->startContainer();
639     if ((!suffixLength && node.isTextNode() && static_cast<int>(next) <= node.maxCharacterOffset()) || (node.renderer() && node.renderer()->isBR() && !next)) {
640         // The next variable contains a usable index into a text node
641         return VisiblePosition(createLegacyEditingPosition(&node, next), DOWNSTREAM);
642     }
643
644     // Use the character iterator to translate the next value into a DOM position.
645     BackwardsCharacterIterator charIt(searchRange);
646     if (next < string.size() - suffixLength)
647         charIt.advance(string.size() - suffixLength - next);
648     // FIXME: charIt can get out of shadow host.
649     return VisiblePosition(charIt.range()->endPosition(), DOWNSTREAM);
650 }
651
652 static VisiblePosition nextBoundary(const VisiblePosition& c, BoundarySearchFunction searchFunction)
653 {
654     Position pos = c.deepEquivalent();
655     Node* boundary = pos.parentEditingBoundary();
656     if (!boundary)
657         return VisiblePosition();
658
659     Document& boundaryDocument = boundary->document();
660     Ref<Range> searchRange = boundaryDocument.createRange();
661     Position start(pos.parentAnchoredEquivalent());
662
663     Vector<UChar, 1024> string;
664     unsigned prefixLength = 0;
665
666     if (requiresContextForWordBoundary(c.characterAfter())) {
667         auto backwardsScanRange = boundaryDocument.createRange();
668         if (start.deprecatedNode())
669             backwardsScanRange->setEnd(*start.deprecatedNode(), start.deprecatedEditingOffset());
670         prefixLength = prefixLengthForRange(backwardsScanRange, string);
671     }
672
673     searchRange->selectNodeContents(*boundary);
674     if (start.deprecatedNode())
675         searchRange->setStart(*start.deprecatedNode(), start.deprecatedEditingOffset());
676     TextIterator it(searchRange.ptr(), TextIteratorEmitsCharactersBetweenAllVisiblePositions);
677     unsigned next = forwardSearchForBoundaryWithTextIterator(it, string, prefixLength, searchFunction);
678     
679     if (it.atEnd() && next == string.size())
680         pos = searchRange->endPosition();
681     else if (next > prefixLength) {
682         // Use the character iterator to translate the next value into a DOM position.
683         CharacterIterator charIt(searchRange, TextIteratorEmitsCharactersBetweenAllVisiblePositions);
684         charIt.advance(next - prefixLength - 1);
685         RefPtr<Range> characterRange = charIt.range();
686         pos = characterRange->endPosition();
687         
688         if (charIt.text()[0] == '\n') {
689             // FIXME: workaround for collapsed range (where only start position is correct) emitted for some emitted newlines (see rdar://5192593)
690             VisiblePosition visPos = VisiblePosition(pos);
691             if (visPos == VisiblePosition(characterRange->startPosition())) {
692                 charIt.advance(1);
693                 pos = charIt.range()->startPosition();
694             }
695         }
696     }
697
698     // generate VisiblePosition, use UPSTREAM affinity if possible
699     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
700 }
701
702 // ---------
703
704 unsigned startWordBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
705 {
706     ASSERT(offset);
707     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(text.substring(0, offset))) {
708         needMoreContext = true;
709         return 0;
710     }
711     needMoreContext = false;
712     int start, end;
713     U16_BACK_1(text, 0, offset);
714     findWordBoundary(text, offset, &start, &end);
715     return start;
716 }
717
718 VisiblePosition startOfWord(const VisiblePosition& c, EWordSide side)
719 {
720     // FIXME: This returns a null VP for c at the start of the document
721     // and side == LeftWordIfOnBoundary
722     VisiblePosition p = c;
723     if (side == RightWordIfOnBoundary) {
724         // at paragraph end, the startofWord is the current position
725         if (isEndOfParagraph(c))
726             return c;
727         
728         p = c.next();
729         if (p.isNull())
730             return c;
731     }
732     return previousBoundary(p, startWordBoundary);
733 }
734
735 unsigned endWordBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
736 {
737     ASSERT(offset <= text.length());
738     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(text.substring(offset)) == text.length() - offset) {
739         needMoreContext = true;
740         return text.length();
741     }
742     needMoreContext = false;
743     int end;
744     findEndWordBoundary(text, offset, &end);
745     return end;
746 }
747
748 VisiblePosition endOfWord(const VisiblePosition& c, EWordSide side)
749 {
750     VisiblePosition p = c;
751     if (side == LeftWordIfOnBoundary) {
752         if (isStartOfParagraph(c))
753             return c;
754             
755         p = c.previous();
756         if (p.isNull())
757             return c;
758     } else if (isEndOfParagraph(c))
759         return c;
760     
761     return nextBoundary(p, endWordBoundary);
762 }
763
764 static unsigned previousWordPositionBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
765 {
766     if (mayHaveMoreContext && !startOfLastWordBoundaryContext(text.substring(0, offset))) {
767         needMoreContext = true;
768         return 0;
769     }
770     needMoreContext = false;
771     return findNextWordFromIndex(text, offset, false);
772 }
773
774 VisiblePosition previousWordPosition(const VisiblePosition& position)
775 {
776     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousWordPositionBoundary));
777 }
778
779 static unsigned nextWordPositionBoundary(StringView text, unsigned offset, BoundarySearchContextAvailability mayHaveMoreContext, bool& needMoreContext)
780 {
781     if (mayHaveMoreContext && endOfFirstWordBoundaryContext(text.substring(offset)) == text.length() - offset) {
782         needMoreContext = true;
783         return text.length();
784     }
785     needMoreContext = false;
786     return findNextWordFromIndex(text, offset, true);
787 }
788
789 VisiblePosition nextWordPosition(const VisiblePosition& position)
790 {
791     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextWordPositionBoundary));
792 }
793
794 bool isStartOfWord(const VisiblePosition& p)
795 {
796     return p.isNotNull() && p == startOfWord(p, RightWordIfOnBoundary);
797 }
798
799 // ---------
800
801 enum LineEndpointComputationMode { UseLogicalOrdering, UseInlineBoxOrdering };
802 static VisiblePosition startPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
803 {
804     if (c.isNull())
805         return VisiblePosition();
806
807     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
808     if (!rootBox) {
809         // There are VisiblePositions at offset 0 in blocks without
810         // RootInlineBoxes, like empty editable blocks and bordered blocks.
811         Position p = c.deepEquivalent();
812         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
813             return c;
814
815         return VisiblePosition();
816     }
817
818     Node* startNode;
819     InlineBox* startBox;
820     if (mode == UseLogicalOrdering) {
821         startNode = rootBox->getLogicalStartBoxWithNode(startBox);
822         if (!startNode)
823             return VisiblePosition();
824     } else {
825         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
826         // and so cannot be represented by a VisiblePosition. Use whatever follows instead.
827         startBox = rootBox->firstLeafChild();
828         while (true) {
829             if (!startBox)
830                 return VisiblePosition();
831
832             startNode = startBox->renderer().nonPseudoNode();
833             if (startNode)
834                 break;
835
836             startBox = startBox->nextLeafChild();
837         }
838     }
839
840     return is<Text>(*startNode) ? Position(downcast<Text>(startNode), downcast<InlineTextBox>(*startBox).start())
841         : positionBeforeNode(startNode);
842 }
843
844 static VisiblePosition startOfLine(const VisiblePosition& c, LineEndpointComputationMode mode, bool* reachedBoundary)
845 {
846     if (reachedBoundary)
847         *reachedBoundary = false;
848     // TODO: this is the current behavior that might need to be fixed.
849     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
850     VisiblePosition visPos = startPositionForLine(c, mode);
851
852     if (mode == UseLogicalOrdering) {
853         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
854             if (!editableRoot->contains(visPos.deepEquivalent().containerNode())) {
855                 VisiblePosition newPosition = firstPositionInNode(editableRoot);
856                 if (reachedBoundary)
857                     *reachedBoundary = c == newPosition;
858                 return newPosition;
859             }
860         }
861     }
862
863     return c.honorEditingBoundaryAtOrBefore(visPos, reachedBoundary);
864 }
865
866 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
867 VisiblePosition startOfLine(const VisiblePosition& currentPosition)
868 {
869     return startOfLine(currentPosition, UseInlineBoxOrdering, nullptr);
870 }
871
872 VisiblePosition logicalStartOfLine(const VisiblePosition& currentPosition, bool* reachedBoundary)
873 {
874     return startOfLine(currentPosition, UseLogicalOrdering, reachedBoundary);
875 }
876
877 static VisiblePosition endPositionForLine(const VisiblePosition& c, LineEndpointComputationMode mode)
878 {
879     if (c.isNull())
880         return VisiblePosition();
881
882     RootInlineBox* rootBox = RenderedPosition(c).rootBox();
883     if (!rootBox) {
884         // There are VisiblePositions at offset 0 in blocks without
885         // RootInlineBoxes, like empty editable blocks and bordered blocks.
886         Position p = c.deepEquivalent();
887         if (p.deprecatedNode()->renderer() && p.deprecatedNode()->renderer()->isRenderBlock() && !p.deprecatedEditingOffset())
888             return c;
889         return VisiblePosition();
890     }
891
892     Node* endNode;
893     InlineBox* endBox;
894     if (mode == UseLogicalOrdering) {
895         endNode = rootBox->getLogicalEndBoxWithNode(endBox);
896         if (!endNode)
897             return VisiblePosition();
898     } else {
899         // Generated content (e.g. list markers and CSS :before and :after pseudoelements) have no corresponding DOM element,
900         // and so cannot be represented by a VisiblePosition. Use whatever precedes instead.
901         endBox = rootBox->lastLeafChild();
902         while (true) {
903             if (!endBox)
904                 return VisiblePosition();
905
906             endNode = endBox->renderer().nonPseudoNode();
907             if (endNode)
908                 break;
909             
910             endBox = endBox->prevLeafChild();
911         }
912     }
913
914     Position pos;
915     if (is<HTMLBRElement>(*endNode))
916         pos = positionBeforeNode(endNode);
917     else if (is<InlineTextBox>(*endBox) && is<Text>(*endNode)) {
918         auto& endTextBox = downcast<InlineTextBox>(*endBox);
919         int endOffset = endTextBox.start();
920         if (!endTextBox.isLineBreak())
921             endOffset += endTextBox.len();
922         pos = Position(downcast<Text>(endNode), endOffset);
923     } else
924         pos = positionAfterNode(endNode);
925     
926     return VisiblePosition(pos, VP_UPSTREAM_IF_POSSIBLE);
927 }
928
929 static bool inSameLogicalLine(const VisiblePosition& a, const VisiblePosition& b)
930 {
931     return a.isNotNull() && logicalStartOfLine(a) == logicalStartOfLine(b);
932 }
933
934 static VisiblePosition endOfLine(const VisiblePosition& c, LineEndpointComputationMode mode, bool* reachedBoundary)
935 {
936     if (reachedBoundary)
937         *reachedBoundary = false;
938     // TODO: this is the current behavior that might need to be fixed.
939     // Please refer to https://bugs.webkit.org/show_bug.cgi?id=49107 for detail.
940     VisiblePosition visPos = endPositionForLine(c, mode);
941
942     if (mode == UseLogicalOrdering) {
943         // Make sure the end of line is at the same line as the given input position. For a wrapping line, the logical end
944         // position for the not-last-2-lines might incorrectly hand back the logical beginning of the next line. 
945         // For example, <div contenteditable dir="rtl" style="line-break:before-white-space">abcdefg abcdefg abcdefg
946         // a abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg abcdefg </div>
947         // In this case, use the previous position of the computed logical end position.
948         if (!inSameLogicalLine(c, visPos))
949             visPos = visPos.previous();
950
951         if (Node* editableRoot = highestEditableRoot(c.deepEquivalent())) {
952             if (!editableRoot->contains(visPos.deepEquivalent().containerNode())) {
953                 VisiblePosition newPosition = lastPositionInNode(editableRoot);
954                 if (reachedBoundary)
955                     *reachedBoundary = c == newPosition;
956                 return newPosition;
957             }
958         }
959
960         return c.honorEditingBoundaryAtOrAfter(visPos, reachedBoundary);
961     }
962
963     // Make sure the end of line is at the same line as the given input position. Else use the previous position to 
964     // obtain end of line. This condition happens when the input position is before the space character at the end 
965     // of a soft-wrapped non-editable line. In this scenario, endPositionForLine would incorrectly hand back a position
966     // in the next line instead. This fix is to account for the discrepancy between lines with webkit-line-break:after-white-space style
967     // versus lines without that style, which would break before a space by default. 
968     if (!inSameLine(c, visPos)) {
969         visPos = c.previous();
970         if (visPos.isNull())
971             return VisiblePosition();
972         visPos = endPositionForLine(visPos, UseInlineBoxOrdering);
973     }
974     
975     return c.honorEditingBoundaryAtOrAfter(visPos, reachedBoundary);
976 }
977
978 // FIXME: Rename this function to reflect the fact it ignores bidi levels.
979 VisiblePosition endOfLine(const VisiblePosition& currentPosition)
980 {
981     return endOfLine(currentPosition, UseInlineBoxOrdering, nullptr);
982 }
983
984 VisiblePosition logicalEndOfLine(const VisiblePosition& currentPosition, bool* reachedBoundary)
985 {
986     return endOfLine(currentPosition, UseLogicalOrdering, reachedBoundary);
987 }
988
989 bool inSameLine(const VisiblePosition& a, const VisiblePosition& b)
990 {
991     return a.isNotNull() && startOfLine(a) == startOfLine(b);
992 }
993
994 bool isStartOfLine(const VisiblePosition& p)
995 {
996     return p.isNotNull() && p == startOfLine(p);
997 }
998
999 bool isEndOfLine(const VisiblePosition& p)
1000 {
1001     return p.isNotNull() && p == endOfLine(p);
1002 }
1003
1004 bool isLogicalEndOfLine(const VisiblePosition &p)
1005 {
1006     return p.isNotNull() && p == logicalEndOfLine(p);
1007 }
1008
1009 static inline IntPoint absoluteLineDirectionPointToLocalPointInBlock(RootInlineBox& root, int lineDirectionPoint)
1010 {
1011     RenderBlockFlow& containingBlock = root.blockFlow();
1012     FloatPoint absoluteBlockPoint = containingBlock.localToAbsolute(FloatPoint()) - toFloatSize(containingBlock.scrollPosition());
1013
1014     if (containingBlock.isHorizontalWritingMode())
1015         return IntPoint(lineDirectionPoint - absoluteBlockPoint.x(), root.blockDirectionPointInLine());
1016
1017     return IntPoint(root.blockDirectionPointInLine(), lineDirectionPoint - absoluteBlockPoint.y());
1018 }
1019
1020 static Element* rootEditableOrDocumentElement(Node& node, EditableType editableType)
1021 {
1022     if (hasEditableStyle(node, editableType))
1023         return editableRootForPosition(firstPositionInOrBeforeNode(&node), editableType);
1024     return node.document().documentElement();
1025 }
1026
1027 VisiblePosition previousLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
1028 {
1029     Position p = visiblePosition.deepEquivalent();
1030     Node* node = p.deprecatedNode();
1031
1032     if (!node)
1033         return VisiblePosition();
1034     
1035     node->document().updateLayoutIgnorePendingStylesheets();
1036     
1037     RenderObject* renderer = node->renderer();
1038     if (!renderer)
1039         return VisiblePosition();
1040
1041     RootInlineBox* root = nullptr;
1042     InlineBox* box;
1043     int ignoredCaretOffset;
1044     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
1045     if (box) {
1046         root = box->root().prevRootBox();
1047         // We want to skip zero height boxes.
1048         // This could happen in case it is a TrailingFloatsRootInlineBox.
1049         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1050             root = nullptr;
1051     }
1052
1053     if (!root) {
1054         Position position = previousRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1055         if (position.isNotNull()) {
1056             RenderedPosition renderedPosition(position);
1057             root = renderedPosition.rootBox();
1058             if (!root)
1059                 return position;
1060         }
1061     }
1062     
1063     if (root) {
1064         // FIXME: Can be wrong for multi-column layout and with transforms.
1065         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
1066         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1067         Node* node = renderer.node();
1068         if (node && editingIgnoresContent(*node))
1069             return positionInParentBeforeNode(node);
1070         return renderer.positionForPoint(pointInLine, nullptr);
1071     }
1072     
1073     // Could not find a previous line. This means we must already be on the first line.
1074     // Move to the start of the content in this block, which effectively moves us
1075     // to the start of the line we're on.
1076     Element* rootElement = rootEditableOrDocumentElement(*node, editableType);
1077     if (!rootElement)
1078         return VisiblePosition();
1079     return VisiblePosition(firstPositionInNode(rootElement), DOWNSTREAM);
1080 }
1081
1082 VisiblePosition nextLinePosition(const VisiblePosition& visiblePosition, int lineDirectionPoint, EditableType editableType)
1083 {
1084     Position p = visiblePosition.deepEquivalent();
1085     Node* node = p.deprecatedNode();
1086
1087     if (!node)
1088         return VisiblePosition();
1089     
1090     node->document().updateLayoutIgnorePendingStylesheets();
1091
1092     RenderObject* renderer = node->renderer();
1093     if (!renderer)
1094         return VisiblePosition();
1095
1096     RootInlineBox* root = nullptr;
1097     InlineBox* box;
1098     int ignoredCaretOffset;
1099     visiblePosition.getInlineBoxAndOffset(box, ignoredCaretOffset);
1100     if (box) {
1101         root = box->root().nextRootBox();
1102         // We want to skip zero height boxes.
1103         // This could happen in case it is a TrailingFloatsRootInlineBox.
1104         if (!root || !root->logicalHeight() || !root->firstLeafChild())
1105             root = nullptr;
1106     }
1107
1108     if (!root) {
1109         // FIXME: We need do the same in previousLinePosition.
1110         Node* child = node->traverseToChildAt(p.deprecatedEditingOffset());
1111         node = child ? child : node->lastDescendant();
1112         Position position = nextRootInlineBoxCandidatePosition(node, visiblePosition, editableType);
1113         if (position.isNotNull()) {
1114             RenderedPosition renderedPosition(position);
1115             root = renderedPosition.rootBox();
1116             if (!root)
1117                 return position;
1118         }
1119     }
1120     
1121     if (root) {
1122         // FIXME: Can be wrong for multi-column layout and with transforms.
1123         IntPoint pointInLine = absoluteLineDirectionPointToLocalPointInBlock(*root, lineDirectionPoint);
1124         RenderObject& renderer = root->closestLeafChildForPoint(pointInLine, isEditablePosition(p))->renderer();
1125         Node* node = renderer.node();
1126         if (node && editingIgnoresContent(*node))
1127             return positionInParentBeforeNode(node);
1128         return renderer.positionForPoint(pointInLine, nullptr);
1129     }
1130
1131     // Could not find a next line. This means we must already be on the last line.
1132     // Move to the end of the content in this block, which effectively moves us
1133     // to the end of the line we're on.
1134     Element* rootElement = rootEditableOrDocumentElement(*node, editableType);
1135     if (!rootElement)
1136         return VisiblePosition();
1137     return VisiblePosition(lastPositionInNode(rootElement), DOWNSTREAM);
1138 }
1139
1140 // ---------
1141
1142 unsigned startSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1143 {
1144     // FIXME: The following function can return -1; we don't handle that.
1145     return ubrk_preceding(sentenceBreakIterator(text), text.length());
1146 }
1147
1148 VisiblePosition startOfSentence(const VisiblePosition& position)
1149 {
1150     return previousBoundary(position, startSentenceBoundary, NeedsContextAtParagraphStart::Yes);
1151 }
1152
1153 unsigned endSentenceBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1154 {
1155     return ubrk_next(sentenceBreakIterator(text));
1156 }
1157
1158 VisiblePosition endOfSentence(const VisiblePosition& position)
1159 {
1160     // FIXME: This includes the space after the punctuation that marks the end of the sentence.
1161     return nextBoundary(position, endSentenceBoundary);
1162 }
1163
1164 static unsigned previousSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1165 {
1166     // FIXME: This is identical to startSentenceBoundary. I'm pretty sure that's not right.
1167     // FIXME: The following function can return -1; we don't handle that.
1168     return ubrk_preceding(sentenceBreakIterator(text), text.length());
1169 }
1170
1171 VisiblePosition previousSentencePosition(const VisiblePosition& position)
1172 {
1173     return position.honorEditingBoundaryAtOrBefore(previousBoundary(position, previousSentencePositionBoundary));
1174 }
1175
1176 static unsigned nextSentencePositionBoundary(StringView text, unsigned, BoundarySearchContextAvailability, bool&)
1177 {
1178     // FIXME: This is identical to endSentenceBoundary.
1179     // That isn't right. This function needs to move to the equivalent position in the following sentence.
1180     return ubrk_following(sentenceBreakIterator(text), 0);
1181 }
1182
1183 VisiblePosition nextSentencePosition(const VisiblePosition& position)
1184 {
1185     return position.honorEditingBoundaryAtOrAfter(nextBoundary(position, nextSentencePositionBoundary));
1186 }
1187
1188 Node* findStartOfParagraph(Node* startNode, Node* highestRoot, Node* startBlock, int& offset, Position::AnchorType& type, EditingBoundaryCrossingRule boundaryCrossingRule)
1189 {
1190     Node* node = startNode;
1191     Node* n = startNode;
1192     while (n) {
1193 #if ENABLE(USERSELECT_ALL)
1194         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1195 #else
1196         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1197 #endif
1198             break;
1199         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1200             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1201                 n = NodeTraversal::previousPostOrder(*n, startBlock);
1202             if (!n || !n->isDescendantOf(highestRoot))
1203                 break;
1204         }
1205         RenderObject* r = n->renderer();
1206         if (!r) {
1207             n = NodeTraversal::previousPostOrder(*n, startBlock);
1208             continue;
1209         }
1210         const RenderStyle& style = r->style();
1211         if (style.visibility() != Visibility::Visible) {
1212             n = NodeTraversal::previousPostOrder(*n, startBlock);
1213             continue;
1214         }
1215         
1216         if (r->isBR() || isBlock(n))
1217             break;
1218
1219         if (is<RenderText>(*r) && downcast<RenderText>(*r).hasRenderedText()) {
1220             ASSERT_WITH_SECURITY_IMPLICATION(is<Text>(*n));
1221             type = Position::PositionIsOffsetInAnchor;
1222             if (style.preserveNewline()) {
1223                 StringImpl& text = downcast<RenderText>(*r).text();
1224                 int i = text.length();
1225                 int o = offset;
1226                 if (n == startNode && o < i)
1227                     i = std::max(0, o);
1228                 while (--i >= 0) {
1229                     if (text[i] == '\n') {
1230                         offset = i + 1;
1231                         return n;
1232                     }
1233                 }
1234             }
1235             node = n;
1236             offset = 0;
1237             n = NodeTraversal::previousPostOrder(*n, startBlock);
1238         } else if (editingIgnoresContent(*n) || isRenderedTable(n)) {
1239             node = n;
1240             type = Position::PositionIsBeforeAnchor;
1241             n = n->previousSibling() ? n->previousSibling() : NodeTraversal::previousPostOrder(*n, startBlock);
1242         } else
1243             n = NodeTraversal::previousPostOrder(*n, startBlock);
1244     }
1245
1246     return node;
1247 }
1248
1249 Node* findEndOfParagraph(Node* startNode, Node* highestRoot, Node* stayInsideBlock, int& offset, Position::AnchorType& type, EditingBoundaryCrossingRule boundaryCrossingRule)
1250 {
1251     Node* node = startNode;
1252     Node* n = startNode;
1253     while (n) {
1254 #if ENABLE(USERSELECT_ALL)
1255         if (boundaryCrossingRule == CannotCrossEditingBoundary && !Position::nodeIsUserSelectAll(n) && n->hasEditableStyle() != startNode->hasEditableStyle())
1256 #else
1257         if (boundaryCrossingRule == CannotCrossEditingBoundary && n->hasEditableStyle() != startNode->hasEditableStyle())
1258 #endif
1259             break;
1260         if (boundaryCrossingRule == CanSkipOverEditingBoundary) {
1261             while (n && n->hasEditableStyle() != startNode->hasEditableStyle())
1262                 n = NodeTraversal::next(*n, stayInsideBlock);
1263             if (!n || !n->isDescendantOf(highestRoot))
1264                 break;
1265         }
1266
1267         RenderObject* r = n->renderer();
1268         if (!r) {
1269             n = NodeTraversal::next(*n, stayInsideBlock);
1270             continue;
1271         }
1272         const RenderStyle& style = r->style();
1273         if (style.visibility() != Visibility::Visible) {
1274             n = NodeTraversal::next(*n, stayInsideBlock);
1275             continue;
1276         }
1277         
1278         // FIXME: This is wrong when startNode is a block. We should return a position after the block.
1279         if (r->isBR() || isBlock(n))
1280             break;
1281
1282         // FIXME: We avoid returning a position where the renderer can't accept the caret.
1283         if (is<RenderText>(*r) && downcast<RenderText>(*r).hasRenderedText()) {
1284             ASSERT_WITH_SECURITY_IMPLICATION(is<Text>(*n));
1285             type = Position::PositionIsOffsetInAnchor;
1286             if (style.preserveNewline()) {
1287                 StringImpl& text = downcast<RenderText>(*r).text();
1288                 int o = n == startNode ? offset : 0;
1289                 int length = text.length();
1290                 for (int i = o; i < length; ++i) {
1291                     if (text[i] == '\n') {
1292                         offset = i;
1293                         return n;
1294                     }
1295                 }
1296             }
1297             node = n;
1298             offset = r->caretMaxOffset();
1299             n = NodeTraversal::next(*n, stayInsideBlock);
1300         } else if (editingIgnoresContent(*n) || isRenderedTable(n)) {
1301             node = n;
1302             type = Position::PositionIsAfterAnchor;
1303             n = NodeTraversal::nextSkippingChildren(*n, stayInsideBlock);
1304         } else
1305             n = NodeTraversal::next(*n, stayInsideBlock);
1306     }
1307     return node;
1308 }
1309
1310 VisiblePosition startOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1311 {
1312     Position p = c.deepEquivalent();
1313     auto* startNode = p.deprecatedNode();
1314     
1315     if (!startNode)
1316         return VisiblePosition();
1317     
1318     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1319         return positionBeforeNode(startNode);
1320     
1321     Node* startBlock = enclosingBlock(startNode);
1322     
1323     auto* highestRoot = highestEditableRoot(p);
1324     int offset = p.deprecatedEditingOffset();
1325     Position::AnchorType type = p.anchorType();
1326     
1327     auto* node = findStartOfParagraph(startNode, highestRoot, startBlock, offset, type, boundaryCrossingRule);
1328     
1329     if (is<Text>(node))
1330         return VisiblePosition(Position(downcast<Text>(node), offset), DOWNSTREAM);
1331     
1332     if (type == Position::PositionIsOffsetInAnchor) {
1333         ASSERT(type == Position::PositionIsOffsetInAnchor || !offset);
1334         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1335     }
1336     
1337     return VisiblePosition(Position(node, type), DOWNSTREAM);
1338 }
1339
1340 VisiblePosition endOfParagraph(const VisiblePosition& c, EditingBoundaryCrossingRule boundaryCrossingRule)
1341 {    
1342     if (c.isNull())
1343         return VisiblePosition();
1344     
1345     Position p = c.deepEquivalent();
1346     auto* startNode = p.deprecatedNode();
1347     
1348     if (isRenderedAsNonInlineTableImageOrHR(startNode))
1349         return positionAfterNode(startNode);
1350     
1351     auto* startBlock = enclosingBlock(startNode);
1352     auto* stayInsideBlock = startBlock;
1353     
1354     auto* highestRoot = highestEditableRoot(p);
1355     int offset = p.deprecatedEditingOffset();
1356     Position::AnchorType type = p.anchorType();
1357     
1358     auto* node = findEndOfParagraph(startNode, highestRoot, stayInsideBlock, offset, type, boundaryCrossingRule);
1359     
1360     if (is<Text>(node))
1361         return VisiblePosition(Position(downcast<Text>(node), offset), DOWNSTREAM);
1362     
1363     if (type == Position::PositionIsOffsetInAnchor)
1364         return VisiblePosition(Position(node, offset, type), DOWNSTREAM);
1365
1366     return VisiblePosition(Position(node, type), DOWNSTREAM);
1367 }
1368
1369 // FIXME: isStartOfParagraph(startOfNextParagraph(pos)) is not always true
1370 VisiblePosition startOfNextParagraph(const VisiblePosition& visiblePosition)
1371 {
1372     VisiblePosition paragraphEnd(endOfParagraph(visiblePosition, CanSkipOverEditingBoundary));
1373     VisiblePosition afterParagraphEnd(paragraphEnd.next(CannotCrossEditingBoundary));
1374     // The position after the last position in the last cell of a table
1375     // is not the start of the next paragraph.
1376     if (isFirstPositionAfterTable(afterParagraphEnd))
1377         return afterParagraphEnd.next(CannotCrossEditingBoundary);
1378     return afterParagraphEnd;
1379 }
1380
1381 bool inSameParagraph(const VisiblePosition& a, const VisiblePosition& b, EditingBoundaryCrossingRule boundaryCrossingRule)
1382 {
1383     return a.isNotNull() && startOfParagraph(a, boundaryCrossingRule) == startOfParagraph(b, boundaryCrossingRule);
1384 }
1385
1386 bool isStartOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1387 {
1388     return pos.isNotNull() && pos == startOfParagraph(pos, boundaryCrossingRule);
1389 }
1390
1391 bool isEndOfParagraph(const VisiblePosition& pos, EditingBoundaryCrossingRule boundaryCrossingRule)
1392 {
1393     return pos.isNotNull() && pos == endOfParagraph(pos, boundaryCrossingRule);
1394 }
1395     
1396 bool isBlankParagraph(const VisiblePosition& position)
1397 {
1398     return isStartOfParagraph(position) && startOfParagraph(position.next()) != startOfParagraph(position);
1399 }
1400
1401 VisiblePosition previousParagraphPosition(const VisiblePosition& p, int x)
1402 {
1403     VisiblePosition pos = p;
1404     do {
1405         VisiblePosition n = previousLinePosition(pos, x);
1406         if (n.isNull() || n == pos)
1407             break;
1408         pos = n;
1409     } while (inSameParagraph(p, pos));
1410     return pos;
1411 }
1412
1413 VisiblePosition nextParagraphPosition(const VisiblePosition& p, int x)
1414 {
1415     VisiblePosition pos = p;
1416     do {
1417         VisiblePosition n = nextLinePosition(pos, x);
1418         if (n.isNull() || n == pos)
1419             break;
1420         pos = n;
1421     } while (inSameParagraph(p, pos));
1422     return pos;
1423 }
1424
1425 // ---------
1426
1427 VisiblePosition startOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1428 {
1429     Position position = visiblePosition.deepEquivalent();
1430     Node* startBlock;
1431     if (!position.containerNode() || !(startBlock = enclosingBlock(position.containerNode(), rule)))
1432         return VisiblePosition();
1433     return firstPositionInNode(startBlock);
1434 }
1435
1436 VisiblePosition endOfBlock(const VisiblePosition& visiblePosition, EditingBoundaryCrossingRule rule)
1437 {
1438     Position position = visiblePosition.deepEquivalent();
1439     Node* endBlock;
1440     if (!position.containerNode() || !(endBlock = enclosingBlock(position.containerNode(), rule)))
1441         return VisiblePosition();
1442     return lastPositionInNode(endBlock);
1443 }
1444
1445 bool inSameBlock(const VisiblePosition& a, const VisiblePosition& b)
1446 {
1447     return !a.isNull() && enclosingBlock(a.deepEquivalent().containerNode()) == enclosingBlock(b.deepEquivalent().containerNode());
1448 }
1449
1450 bool isStartOfBlock(const VisiblePosition& pos)
1451 {
1452     return pos.isNotNull() && pos == startOfBlock(pos, CanCrossEditingBoundary);
1453 }
1454
1455 bool isEndOfBlock(const VisiblePosition& pos)
1456 {
1457     return pos.isNotNull() && pos == endOfBlock(pos, CanCrossEditingBoundary);
1458 }
1459
1460 // ---------
1461
1462 VisiblePosition startOfDocument(const Node* node)
1463 {
1464     if (!node || !node->document().documentElement())
1465         return VisiblePosition();
1466     
1467     // The canonicalization of the position at (documentElement, 0) can turn the visible
1468     // position to null, even when there's a valid candidate to be had, because the root HTML element
1469     // is not content editable.  So we construct directly from the valid candidate.
1470     Position firstCandidate = nextCandidate(createLegacyEditingPosition(node->document().documentElement(), 0));
1471     if (firstCandidate.isNull())
1472         return VisiblePosition();
1473     return VisiblePosition(firstCandidate);
1474 }
1475
1476 VisiblePosition startOfDocument(const VisiblePosition& c)
1477 {
1478     return startOfDocument(c.deepEquivalent().deprecatedNode());
1479 }
1480
1481 VisiblePosition endOfDocument(const Node* node)
1482 {
1483     if (!node || !node->document().documentElement())
1484         return VisiblePosition();
1485     
1486     // (As above, in startOfDocument.)  The canonicalization can reject valid visible positions
1487     // when descending from the root element, so we construct the visible position directly from a
1488     // valid candidate.
1489     Position lastPosition = createLegacyEditingPosition(node->document().documentElement(), node->document().documentElement()->countChildNodes());
1490     Position lastCandidate = previousCandidate(lastPosition);
1491     if (lastCandidate.isNull())
1492         return VisiblePosition();
1493     return VisiblePosition(lastCandidate);
1494 }
1495
1496 VisiblePosition endOfDocument(const VisiblePosition& c)
1497 {
1498     return endOfDocument(c.deepEquivalent().deprecatedNode());
1499 }
1500
1501 bool inSameDocument(const VisiblePosition& a, const VisiblePosition& b)
1502 {
1503     Position ap = a.deepEquivalent();
1504     Node* an = ap.deprecatedNode();
1505     if (!an)
1506         return false;
1507     Position bp = b.deepEquivalent();
1508     Node* bn = bp.deprecatedNode();
1509     if (an == bn)
1510         return true;
1511
1512     return &an->document() == &bn->document();
1513 }
1514
1515 bool isStartOfDocument(const VisiblePosition& p)
1516 {
1517     return p.isNotNull() && p.previous(CanCrossEditingBoundary).isNull();
1518 }
1519
1520 bool isEndOfDocument(const VisiblePosition& p)
1521 {
1522     return p.isNotNull() && p.next(CanCrossEditingBoundary).isNull();
1523 }
1524
1525 // ---------
1526
1527 VisiblePosition startOfEditableContent(const VisiblePosition& visiblePosition)
1528 {
1529     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1530     if (!highestRoot)
1531         return { };
1532
1533     return firstPositionInNode(highestRoot);
1534 }
1535
1536 VisiblePosition endOfEditableContent(const VisiblePosition& visiblePosition)
1537 {
1538     auto* highestRoot = highestEditableRoot(visiblePosition.deepEquivalent());
1539     if (!highestRoot)
1540         return { };
1541
1542     return lastPositionInNode(highestRoot);
1543 }
1544
1545 bool isEndOfEditableOrNonEditableContent(const VisiblePosition& p)
1546 {
1547     return p.isNotNull() && p.next().isNull();
1548 }
1549
1550 VisiblePosition leftBoundaryOfLine(const VisiblePosition& c, TextDirection direction, bool* reachedBoundary)
1551 {
1552     return direction == TextDirection::LTR ? logicalStartOfLine(c, reachedBoundary) : logicalEndOfLine(c, reachedBoundary);
1553 }
1554
1555 VisiblePosition rightBoundaryOfLine(const VisiblePosition& c, TextDirection direction, bool* reachedBoundary)
1556 {
1557     return direction == TextDirection::LTR ? logicalEndOfLine(c, reachedBoundary) : logicalStartOfLine(c, reachedBoundary);
1558 }
1559
1560 static bool directionIsDownstream(SelectionDirection direction)
1561 {
1562     if (direction == DirectionBackward)
1563         return false;
1564     else if (direction == DirectionForward)
1565         return true;
1566
1567     // FIXME: this code doesn't take into account the original direction of the element.
1568     // I'm not fixing this now because I'm afraid there is some code in UIKit relying on
1569     // this wrong behavior.
1570     return direction == DirectionRight;
1571 }
1572
1573 bool atBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1574 {
1575     if (granularity == CharacterGranularity)
1576         return true;
1577
1578     VisiblePosition boundary;
1579
1580     bool useDownstream = directionIsDownstream(direction);
1581
1582     switch (granularity) {
1583     case WordGranularity:
1584         // visible_units claims erroneously that the start and the end
1585         // of a paragraph are the end and start of a word, respectively.
1586         if ((useDownstream && isStartOfParagraph(vp)) || (!useDownstream && isEndOfParagraph(vp)))
1587             return false;
1588
1589         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1590         boundary = useDownstream ? endOfWord(vp, LeftWordIfOnBoundary) : startOfWord(vp, RightWordIfOnBoundary);
1591         break;
1592
1593     case SentenceGranularity:
1594         boundary = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1595         break;
1596
1597     case LineGranularity:
1598         // Affinity has to be set to get right boundary of the line.
1599         boundary = vp;
1600         boundary.setAffinity(useDownstream ? VP_UPSTREAM_IF_POSSIBLE : DOWNSTREAM);
1601         boundary = useDownstream ? endOfLine(boundary) : startOfLine(boundary);
1602         break;
1603
1604     case ParagraphGranularity:
1605         boundary = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1606         break;
1607
1608     case DocumentGranularity:
1609         boundary = useDownstream ? endOfDocument(vp) : startOfDocument(vp);
1610         break;
1611
1612     default:
1613         ASSERT_NOT_REACHED();
1614         break;
1615     }
1616
1617     return vp == boundary;
1618 }
1619
1620 bool withinTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1621 {
1622     if (granularity == CharacterGranularity || granularity == DocumentGranularity)
1623         return true;
1624
1625     bool useDownstream = directionIsDownstream(direction);
1626
1627     VisiblePosition prevBoundary;
1628     VisiblePosition nextBoundary;
1629     
1630     switch (granularity) {
1631     case WordGranularity:
1632         // Note that "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1633         prevBoundary = startOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1634         nextBoundary = endOfWord(vp, (useDownstream ? RightWordIfOnBoundary : LeftWordIfOnBoundary));
1635     
1636         // Workaround for <rdar://problem/7259611> Word boundary code on iPhone gives different results than desktop
1637         if (endOfWord(prevBoundary, RightWordIfOnBoundary) != nextBoundary)
1638             return false;
1639
1640         break;
1641
1642     case SentenceGranularity:
1643         prevBoundary = startOfSentence(vp);
1644         nextBoundary = endOfSentence(vp);
1645         break;
1646
1647     case LineGranularity:
1648         prevBoundary = startOfLine(vp);
1649         nextBoundary = endOfLine(vp);
1650
1651         if (prevBoundary == nextBoundary) {
1652             nextBoundary = nextLinePosition(nextBoundary, 0);
1653             nextBoundary.setAffinity(UPSTREAM);
1654             if (!inSameLine(prevBoundary, nextBoundary))
1655                 nextBoundary = vp.next();
1656         }
1657         break;
1658
1659     case ParagraphGranularity:
1660         prevBoundary = startOfParagraph(vp);
1661         nextBoundary = endOfParagraph(vp);
1662         break;
1663
1664     default:
1665         ASSERT_NOT_REACHED();
1666         break;
1667     }
1668
1669     if (prevBoundary == nextBoundary)
1670         return false;
1671
1672     if (vp == prevBoundary)
1673         return useDownstream;
1674
1675     if (vp == nextBoundary)
1676         return !useDownstream;
1677
1678     return (prevBoundary < vp && vp < nextBoundary);
1679 }
1680
1681 static VisiblePosition nextCharacterBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction, EditingBoundaryCrossingRule rule)
1682 {
1683     return directionIsDownstream(direction) ? vp.next(rule) : vp.previous(rule);
1684 }
1685
1686 static VisiblePosition nextWordBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1687 {
1688     bool useDownstream = directionIsDownstream(direction);
1689     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, WordGranularity, direction);
1690     VisiblePosition result;
1691     
1692     if (useDownstream) {
1693         if (withinUnitOfGranularity)
1694             result = endOfWord(vp, RightWordIfOnBoundary);
1695         else {
1696             VisiblePosition start = startOfWord(vp, RightWordIfOnBoundary);
1697             if (start > vp && start != endOfWord(start))
1698                 result = start;
1699             else {
1700                 // Do same thing as backwards traveling below.
1701                 start = vp;
1702                 while (true) {
1703                     result = startOfWord(nextWordPosition(start), RightWordIfOnBoundary);
1704
1705                     if (result == start)
1706                         break;
1707
1708                     // We failed to find a word boundary.
1709                     if (result.isNull() || result < start)
1710                         return VisiblePosition();
1711
1712                     // We consider successs also the case where start is before element and result is after.
1713                     // This covers moving past images like words.
1714                     if (result != endOfWord(result)
1715                         || (result.deepEquivalent().anchorNode() == start.deepEquivalent().anchorNode()
1716                             && result.deepEquivalent().anchorType() == Position::PositionIsAfterAnchor
1717                             && start.deepEquivalent().anchorType() == Position::PositionIsBeforeAnchor))
1718                         break;
1719
1720                     start = result;
1721                 }
1722             }
1723         }
1724     } else {
1725         if (withinUnitOfGranularity)
1726             result = startOfWord(vp, LeftWordIfOnBoundary);
1727         else {
1728             // This is complicated because:
1729             //   When given "Blah blah.|", endOfWord is "Blah blah|.", and previousWordPosition is "Blah| blah."
1730             //   When given "Blah blah. |", endOfWord is "Blah blah.| ", and previousWordPosition is "Blah |blah. ".
1731             VisiblePosition end = endOfWord(vp, LeftWordIfOnBoundary);
1732             if (end < vp && end != startOfWord(end))
1733                 result = end;
1734             else {
1735                 end = vp;
1736                 while (true) {
1737                     result = endOfWord(previousWordPosition(end), RightWordIfOnBoundary);
1738
1739                     if (result == end)
1740                         break;
1741
1742                     if (result.isNull() || result > end)
1743                         return VisiblePosition();
1744
1745                     if (result != startOfWord(result))
1746                         break;
1747
1748                     end = result;
1749                 }
1750             }
1751         }
1752     }
1753     
1754     if (result == vp)
1755         return VisiblePosition();
1756     
1757     return result;
1758 }
1759
1760 static VisiblePosition nextSentenceBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1761 {
1762     bool useDownstream = directionIsDownstream(direction);
1763     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, SentenceGranularity, direction);
1764     VisiblePosition result;
1765
1766     if (withinUnitOfGranularity)
1767         result = useDownstream ? endOfSentence(vp) : startOfSentence(vp);
1768     else {
1769         result = useDownstream ? nextSentencePosition(vp) : previousSentencePosition(vp);
1770         if (result.isNull() || result == vp)
1771             return VisiblePosition();
1772
1773         result = useDownstream ? startOfSentence(vp) : endOfSentence(vp);
1774     }
1775
1776     if (result == vp)
1777         return VisiblePosition();
1778
1779     ASSERT(useDownstream ? (result > vp) : (result < vp));
1780
1781     return result;
1782 }
1783
1784 static VisiblePosition nextLineBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1785 {
1786     bool useDownstream = directionIsDownstream(direction);
1787     VisiblePosition result = vp;
1788
1789     if (useDownstream) {
1790         result.setAffinity(DOWNSTREAM);
1791         result = isEndOfLine(result) ? startOfLine(nextLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : endOfLine(result);
1792     } else {
1793         result.setAffinity(VP_UPSTREAM_IF_POSSIBLE);
1794         result = isStartOfLine(result) ? endOfLine(previousLinePosition(result, result.lineDirectionPointForBlockDirectionNavigation())) : startOfLine(result);
1795     }
1796
1797     return result;
1798 }
1799
1800 static VisiblePosition nextParagraphBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1801 {
1802     bool useDownstream = directionIsDownstream(direction);
1803     bool withinUnitOfGranularity = withinTextUnitOfGranularity(vp, ParagraphGranularity, direction);
1804     VisiblePosition result;
1805
1806     if (!withinUnitOfGranularity)
1807         result =  useDownstream ? startOfParagraph(nextParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation())) : endOfParagraph(previousParagraphPosition(vp, vp.lineDirectionPointForBlockDirectionNavigation()));
1808     else
1809         result = useDownstream ? endOfParagraph(vp) : startOfParagraph(vp);
1810
1811     return result;
1812 }
1813
1814 static VisiblePosition nextDocumentBoundaryInDirection(const VisiblePosition& vp, SelectionDirection direction)
1815 {
1816     return directionIsDownstream(direction) ? endOfDocument(vp) : startOfDocument(vp);
1817 }
1818
1819 VisiblePosition positionOfNextBoundaryOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1820 {
1821     switch (granularity) {
1822     case CharacterGranularity:
1823         return nextCharacterBoundaryInDirection(vp, direction, CanCrossEditingBoundary);
1824     case WordGranularity:
1825         return nextWordBoundaryInDirection(vp, direction);
1826     case SentenceGranularity:
1827         return nextSentenceBoundaryInDirection(vp, direction);
1828     case LineGranularity:
1829         return nextLineBoundaryInDirection(vp, direction);
1830     case ParagraphGranularity:
1831         return nextParagraphBoundaryInDirection(vp, direction);
1832     case DocumentGranularity:
1833         return nextDocumentBoundaryInDirection(vp, direction);
1834     default:
1835         ASSERT_NOT_REACHED();
1836         return VisiblePosition();
1837     }
1838 }
1839
1840 RefPtr<Range> enclosingTextUnitOfGranularity(const VisiblePosition& vp, TextGranularity granularity, SelectionDirection direction)
1841 {
1842     // This is particularly inefficient.  We could easily obtain the answer with the boundaries computed below.
1843     if (!withinTextUnitOfGranularity(vp, granularity, direction))
1844         return nullptr;
1845
1846     VisiblePosition prevBoundary;
1847     VisiblePosition nextBoundary;
1848     bool useDownstream = directionIsDownstream(direction);
1849
1850     switch (granularity) {
1851         case CharacterGranularity:
1852             prevBoundary = vp;
1853             nextBoundary = prevBoundary.next();
1854             break;
1855
1856         case WordGranularity:
1857             // NB: "Left" and "Right" in this context apparently mean "upstream/previous" and "downstream/next".
1858             if (useDownstream) {
1859                 prevBoundary = startOfWord(vp, RightWordIfOnBoundary);
1860                 nextBoundary = endOfWord(vp, RightWordIfOnBoundary);
1861             } else {
1862                 prevBoundary = startOfWord(vp, LeftWordIfOnBoundary);
1863                 nextBoundary = endOfWord(vp, LeftWordIfOnBoundary);
1864             }
1865             break;
1866
1867         case SentenceGranularity:
1868             prevBoundary = startOfSentence(vp);
1869             nextBoundary = endOfSentence(vp);
1870             break;
1871
1872         case LineGranularity:
1873             prevBoundary = startOfLine(vp);
1874             nextBoundary = endOfLine(vp);
1875
1876             if (prevBoundary == nextBoundary) {
1877                 nextBoundary = nextLinePosition(nextBoundary, 0);
1878                 nextBoundary.setAffinity(UPSTREAM);
1879                 if (!inSameLine(prevBoundary, nextBoundary))
1880                     nextBoundary = vp.next();
1881             }
1882             break;
1883
1884         case ParagraphGranularity:
1885             prevBoundary = startOfParagraph(vp);
1886             nextBoundary = endOfParagraph(vp);
1887             break;
1888
1889         case DocumentGranularity:
1890             prevBoundary = startOfDocument(vp);
1891             nextBoundary = endOfDocument(vp);
1892             break;
1893
1894         default:
1895             ASSERT_NOT_REACHED();
1896             return nullptr;
1897     }
1898
1899     if (prevBoundary.isNull() || nextBoundary.isNull())
1900         return nullptr;
1901
1902     if (vp < prevBoundary || vp > nextBoundary)
1903         return nullptr;
1904
1905     return Range::create(prevBoundary.deepEquivalent().deprecatedNode()->document(), prevBoundary, nextBoundary);
1906 }
1907
1908 int distanceBetweenPositions(const VisiblePosition& vp, const VisiblePosition& other)
1909 {
1910     if (vp.isNull() || other.isNull())
1911         return 0;
1912
1913     bool thisIsStart = (vp < other);
1914
1915     // Start must come first in the Range constructor.
1916     auto range = Range::create(vp.deepEquivalent().deprecatedNode()->document(),
1917                                         (thisIsStart ? vp : other),
1918                                         (thisIsStart ? other : vp));
1919     int distance = TextIterator::rangeLength(range.ptr());
1920
1921     return (thisIsStart ? -distance : distance);
1922 }
1923
1924 void charactersAroundPosition(const VisiblePosition& position, UChar32& oneAfter, UChar32& oneBefore, UChar32& twoBefore)
1925 {
1926     const int maxCharacters = 3;
1927     UChar32 characters[maxCharacters] = { 0 };
1928
1929     if (position.isNull() || isStartOfDocument(position))
1930         return;
1931
1932     VisiblePosition startPosition = position;
1933     VisiblePosition endPosition = position;
1934
1935     VisiblePosition nextPosition = nextCharacterBoundaryInDirection(position, DirectionForward, CannotCrossEditingBoundary);
1936     if (nextPosition.isNotNull())
1937         endPosition = nextPosition;
1938
1939     VisiblePosition previousPosition = nextCharacterBoundaryInDirection(position, DirectionBackward, CannotCrossEditingBoundary);
1940     if (previousPosition.isNotNull()) {
1941         startPosition = previousPosition;
1942         previousPosition = nextCharacterBoundaryInDirection(previousPosition, DirectionBackward, CannotCrossEditingBoundary);
1943         if (previousPosition.isNotNull())
1944             startPosition = previousPosition;
1945     }
1946
1947     if (startPosition != endPosition) {
1948         String characterString = plainText(Range::create(position.deepEquivalent().anchorNode()->document(), startPosition, endPosition).ptr()).replace(noBreakSpace, ' ');
1949         for (int i = characterString.length() - 1, index = 0; i >= 0 && index < maxCharacters; --i) {
1950             if (!index && nextPosition.isNull())
1951                 index++;
1952             characters[index++] = characterString[i];
1953         }
1954     }
1955     oneAfter = characters[0];
1956     oneBefore = characters[1];
1957     twoBefore = characters[2];
1958 }
1959
1960 RefPtr<Range> wordRangeFromPosition(const VisiblePosition& position)
1961 {
1962     // The selection could be in a non visible element and we don't have a VisiblePosition.
1963     if (position.isNull())
1964         return nullptr;
1965
1966     RefPtr<Range> range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionBackward);
1967
1968     if (!range) {
1969         // We could be at the start of a word, try forward.
1970         range = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
1971     }
1972
1973     if (range)
1974         return range;
1975
1976     VisiblePosition currentPosition = position;
1977     do {
1978         currentPosition = positionOfNextBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward);
1979     } while (currentPosition.isNotNull() && !atBoundaryOfGranularity(currentPosition, WordGranularity, DirectionBackward));
1980
1981     if (currentPosition.isNull())
1982         currentPosition = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
1983
1984     if (currentPosition.isNotNull()) {
1985         range = Range::create(position.deepEquivalent().deprecatedNode()->document(), currentPosition, position);
1986         ASSERT(range);
1987     }
1988
1989     return range;
1990 }
1991
1992 VisiblePosition closestWordBoundaryForPosition(const VisiblePosition& position)
1993 {
1994     VisiblePosition result;
1995
1996     // move the position at the end of the word
1997     if (atBoundaryOfGranularity(position, LineGranularity, DirectionForward)) {
1998         // Don't cross line boundaries.
1999         result = position;
2000     } else if (withinTextUnitOfGranularity(position, WordGranularity, DirectionForward)) {
2001         // The position lies within a word.
2002         RefPtr<Range> wordRange = enclosingTextUnitOfGranularity(position, WordGranularity, DirectionForward);
2003
2004         result = wordRange->startPosition();
2005         if (distanceBetweenPositions(position, result) > 1)
2006             result = wordRange->endPosition();
2007     } else if (atBoundaryOfGranularity(position, WordGranularity, DirectionBackward)) {
2008         // The position is at the end of a word.
2009         result = position;
2010     } else {
2011         // The position is not within a word.
2012         // Go to the next boundary.
2013         result = positionOfNextBoundaryOfGranularity(position, WordGranularity, DirectionForward);
2014
2015         // If there is no such boundary we go to the end of the element.
2016         if (result.isNull())
2017             result = endOfEditableContent(position);
2018     }
2019     return result;
2020 }
2021
2022 RefPtr<Range> rangeExpandedByCharactersInDirectionAtWordBoundary(const VisiblePosition& position, int numberOfCharactersToExpand, SelectionDirection direction)
2023 {
2024     Position start = position.deepEquivalent();
2025     Position end = position.deepEquivalent();
2026     for (int i = 0; i < numberOfCharactersToExpand; ++i) {
2027         if (direction == DirectionBackward)
2028             start = start.previous(Character);
2029         else
2030             end = end.next(Character);
2031     }
2032     
2033     if (direction == DirectionBackward && !atBoundaryOfGranularity(start, WordGranularity, DirectionBackward))
2034         start = startOfWord(start).deepEquivalent();
2035     if (direction == DirectionForward && !atBoundaryOfGranularity(end, WordGranularity, DirectionForward))
2036         end = endOfWord(end).deepEquivalent();
2037
2038     return makeRange(start, end);
2039 }    
2040
2041 RefPtr<Range> rangeExpandedAroundPositionByCharacters(const VisiblePosition& position, int numberOfCharactersToExpand)
2042 {
2043     Position start = position.deepEquivalent();
2044     Position end = position.deepEquivalent();
2045     for (int i = 0; i < numberOfCharactersToExpand; ++i) {
2046         start = start.previous(Character);
2047         end = end.next(Character);
2048     }
2049     
2050     return makeRange(start, end);
2051 }    
2052
2053 }