isEditablePosition and related functions shouldn't move position out of table
[WebKit-https.git] / Source / WebCore / editing / htmlediting.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007 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 "htmlediting.h"
28
29 #include "AXObjectCache.h"
30 #include "Document.h"
31 #include "Editor.h"
32 #include "ExceptionCodePlaceholder.h"
33 #include "Frame.h"
34 #include "HTMLBRElement.h"
35 #include "HTMLDivElement.h"
36 #include "HTMLElementFactory.h"
37 #include "HTMLInterchange.h"
38 #include "HTMLLIElement.h"
39 #include "HTMLNames.h"
40 #include "HTMLOListElement.h"
41 #include "HTMLObjectElement.h"
42 #include "HTMLParagraphElement.h"
43 #include "HTMLTableElement.h"
44 #include "HTMLTextFormControlElement.h"
45 #include "HTMLUListElement.h"
46 #include "NodeTraversal.h"
47 #include "PositionIterator.h"
48 #include "RenderBlock.h"
49 #include "RenderElement.h"
50 #include "RenderTableCell.h"
51 #include "ShadowRoot.h"
52 #include "Text.h"
53 #include "TextIterator.h"
54 #include "VisibleUnits.h"
55 #include <wtf/Assertions.h>
56 #include <wtf/StdLibExtras.h>
57 #include <wtf/unicode/CharacterNames.h>
58
59 namespace WebCore {
60
61 using namespace HTMLNames;
62
63 // Atomic means that the node has no children, or has children which are ignored for the
64 // purposes of editing.
65 bool isAtomicNode(const Node *node)
66 {
67     return node && (!node->hasChildNodes() || editingIgnoresContent(node));
68 }
69
70 // Compare two positions, taking into account the possibility that one or both
71 // could be inside a shadow tree. Only works for non-null values.
72 int comparePositions(const Position& a, const Position& b)
73 {
74     TreeScope* commonScope = commonTreeScope(a.containerNode(), b.containerNode());
75
76     if (!commonScope)
77         return 0;
78
79     Node* nodeA = commonScope->ancestorInThisScope(a.containerNode());
80     ASSERT(nodeA);
81     bool hasDescendentA = nodeA != a.containerNode();
82     int offsetA = hasDescendentA ? 0 : a.computeOffsetInContainerNode();
83
84     Node* nodeB = commonScope->ancestorInThisScope(b.containerNode());
85     ASSERT(nodeB);
86     bool hasDescendentB = nodeB != b.containerNode();
87     int offsetB = hasDescendentB ? 0 : b.computeOffsetInContainerNode();
88
89     int bias = 0;
90     if (nodeA == nodeB) {
91         if (hasDescendentA)
92             bias = -1;
93         else if (hasDescendentB)
94             bias = 1;
95     }
96
97     int result = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB, IGNORE_EXCEPTION);
98     return result ? result : bias;
99 }
100
101 int comparePositions(const VisiblePosition& a, const VisiblePosition& b)
102 {
103     return comparePositions(a.deepEquivalent(), b.deepEquivalent());
104 }
105
106 Node* highestEditableRoot(const Position& position, EditableType editableType)
107 {
108     Node* node = position.deprecatedNode();
109     if (!node)
110         return 0;
111
112     Node* highestEditableRoot = editableRootForPosition(position, editableType);
113     if (!highestEditableRoot)
114         return 0;
115
116     node = highestEditableRoot;
117     while (!node->hasTagName(bodyTag)) {
118         node = node->parentNode();
119         if (!node)
120             break;
121         if (node->hasEditableStyle(editableType))
122             highestEditableRoot = node;
123     }
124
125     return highestEditableRoot;
126 }
127
128 Node* lowestEditableAncestor(Node* node)
129 {
130     if (!node)
131         return 0;
132     
133     while (node) {
134         if (node->hasEditableStyle())
135             return node->rootEditableElement();
136         if (node->hasTagName(bodyTag))
137             break;
138         node = node->parentNode();
139     }
140     
141     return 0;
142 }
143
144 bool isEditablePosition(const Position& p, EditableType editableType, EUpdateStyle updateStyle)
145 {
146     Node* node = p.containerNode();
147     if (!node)
148         return false;
149     if (updateStyle == UpdateStyle)
150         node->document().updateStyleIfNeeded();
151     else
152         ASSERT(updateStyle == DoNotUpdateStyle);
153
154     return node->hasEditableStyle(editableType);
155 }
156
157 bool isAtUnsplittableElement(const Position& pos)
158 {
159     Node* node = pos.containerNode();
160     return (node == editableRootForPosition(pos) || node == enclosingNodeOfType(pos, &isTableCell));
161 }
162     
163     
164 bool isRichlyEditablePosition(const Position& p, EditableType editableType)
165 {
166     Node* node = p.containerNode();
167     if (!node)
168         return false;
169
170     return node->hasRichlyEditableStyle(editableType);
171 }
172
173 Element* editableRootForPosition(const Position& p, EditableType editableType)
174 {
175     Node* node = p.containerNode();
176     if (!node)
177         return 0;
178
179     return node->rootEditableElement(editableType);
180 }
181
182 // Finds the enclosing element until which the tree can be split.
183 // When a user hits ENTER, he/she won't expect this element to be split into two.
184 // You may pass it as the second argument of splitTreeToNode.
185 Element* unsplittableElementForPosition(const Position& p)
186 {
187     // Since enclosingNodeOfType won't search beyond the highest root editable node,
188     // this code works even if the closest table cell was outside of the root editable node.
189     Element* enclosingCell = downcast<Element>(enclosingNodeOfType(p, &isTableCell));
190     if (enclosingCell)
191         return enclosingCell;
192
193     return editableRootForPosition(p);
194 }
195
196 Position nextCandidate(const Position& position)
197 {
198     PositionIterator p = position;
199     while (!p.atEnd()) {
200         p.increment();
201         if (p.isCandidate())
202             return p;
203     }
204     return Position();
205 }
206
207 Position nextVisuallyDistinctCandidate(const Position& position)
208 {
209     Position p = position;
210     Position downstreamStart = p.downstream();
211     while (!p.atEndOfTree()) {
212         p = p.next(Character);
213         if (p.isCandidate() && p.downstream() != downstreamStart)
214             return p;
215     }
216     return Position();
217 }
218
219 Position previousCandidate(const Position& position)
220 {
221     PositionIterator p = position;
222     while (!p.atStart()) {
223         p.decrement();
224         if (p.isCandidate())
225             return p;
226     }
227     return Position();
228 }
229
230 Position previousVisuallyDistinctCandidate(const Position& position)
231 {
232     Position p = position;
233     Position downstreamStart = p.downstream();
234     while (!p.atStartOfTree()) {
235         p = p.previous(Character);
236         if (p.isCandidate() && p.downstream() != downstreamStart)
237             return p;
238     }
239     return Position();
240 }
241
242 VisiblePosition firstEditablePositionAfterPositionInRoot(const Position& position, Node* highestRoot)
243 {
244     // position falls before highestRoot.
245     if (comparePositions(position, firstPositionInNode(highestRoot)) == -1 && highestRoot->hasEditableStyle())
246         return firstPositionInNode(highestRoot);
247
248     Position p = position;
249
250     if (&position.deprecatedNode()->treeScope() != &highestRoot->treeScope()) {
251         Node* shadowAncestor = highestRoot->treeScope().ancestorInThisScope(p.deprecatedNode());
252         if (!shadowAncestor)
253             return VisiblePosition();
254
255         p = positionAfterNode(shadowAncestor);
256     }
257
258     while (p.deprecatedNode() && !isEditablePosition(p) && p.deprecatedNode()->isDescendantOf(highestRoot))
259         p = isAtomicNode(p.deprecatedNode()) ? positionInParentAfterNode(p.deprecatedNode()) : nextVisuallyDistinctCandidate(p);
260     
261     if (p.deprecatedNode() && p.deprecatedNode() != highestRoot && !p.deprecatedNode()->isDescendantOf(highestRoot))
262         return VisiblePosition();
263     
264     return VisiblePosition(p);
265 }
266
267 VisiblePosition lastEditablePositionBeforePositionInRoot(const Position& position, Node* highestRoot)
268 {
269     // When position falls after highestRoot, the result is easy to compute.
270     if (comparePositions(position, lastPositionInNode(highestRoot)) == 1)
271         return lastPositionInNode(highestRoot);
272
273     Position p = position;
274
275     if (&position.deprecatedNode()->treeScope() != &highestRoot->treeScope()) {
276         Node* shadowAncestor = highestRoot->treeScope().ancestorInThisScope(p.deprecatedNode());
277         if (!shadowAncestor)
278             return VisiblePosition();
279
280         p = firstPositionInOrBeforeNode(shadowAncestor);
281     }
282     
283     while (p.deprecatedNode() && !isEditablePosition(p) && p.deprecatedNode()->isDescendantOf(highestRoot))
284         p = isAtomicNode(p.deprecatedNode()) ? positionInParentBeforeNode(p.deprecatedNode()) : previousVisuallyDistinctCandidate(p);
285     
286     if (p.deprecatedNode() && p.deprecatedNode() != highestRoot && !p.deprecatedNode()->isDescendantOf(highestRoot))
287         return VisiblePosition();
288     
289     return VisiblePosition(p);
290 }
291
292 // FIXME: The method name, comment, and code say three different things here!
293 // Whether or not content before and after this node will collapse onto the same line as it.
294 bool isBlock(const Node* node)
295 {
296     return node && node->renderer() && !node->renderer()->isInline() && !node->renderer()->isRubyText();
297 }
298
299 bool isInline(const Node* node)
300 {
301     return node && node->renderer() && node->renderer()->isInline();
302 }
303
304 // FIXME: Deploy this in all of the places where enclosingBlockFlow/enclosingBlockFlowOrTableElement are used.
305 // FIXME: Pass a position to this function. The enclosing block of [table, x] for example, should be the 
306 // block that contains the table and not the table, and this function should be the only one responsible for 
307 // knowing about these kinds of special cases.
308 Element* enclosingBlock(Node* node, EditingBoundaryCrossingRule rule)
309 {
310     Node* enclosingNode = enclosingNodeOfType(firstPositionInOrBeforeNode(node), isBlock, rule);
311     return is<Element>(enclosingNode) ? downcast<Element>(enclosingNode) : nullptr;
312 }
313
314 TextDirection directionOfEnclosingBlock(const Position& position)
315 {
316     auto block = enclosingBlock(position.containerNode());
317     if (!block)
318         return LTR;
319     auto renderer = block->renderer();
320     if (!renderer)
321         return LTR;
322     return renderer->style().direction();
323 }
324
325 // This method is used to create positions in the DOM. It returns the maximum valid offset
326 // in a node. It returns 1 for some elements even though they do not have children, which
327 // creates technically invalid DOM Positions. Be sure to call parentAnchoredEquivalent
328 // on a Position before using it to create a DOM Range, or an exception will be thrown.
329 int lastOffsetForEditing(const Node* node)
330 {
331     ASSERT(node);
332     if (!node)
333         return 0;
334     if (node->offsetInCharacters())
335         return node->maxCharacterOffset();
336
337     if (node->hasChildNodes())
338         return node->countChildNodes();
339
340     // NOTE: This should preempt the countChildNodes() for, e.g., select nodes (what does this mean)?
341     if (editingIgnoresContent(node))
342         return 1;
343
344     return 0;
345 }
346
347 String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)
348 {
349     Vector<UChar> rebalancedString(string.length());
350     StringView(string).getCharactersWithUpconvert(rebalancedString.data());
351
352     bool previousCharacterWasSpace = false;
353     for (size_t i = 0; i < rebalancedString.size(); i++) {
354         if (!isWhitespace(rebalancedString[i])) {
355             previousCharacterWasSpace = false;
356             continue;
357         }
358
359         if (previousCharacterWasSpace || (!i && startIsStartOfParagraph) || (i + 1 == rebalancedString.size() && endIsEndOfParagraph)) {
360             rebalancedString[i] = noBreakSpace;
361             previousCharacterWasSpace = false;
362         } else {
363             rebalancedString[i] = ' ';
364             previousCharacterWasSpace = true;
365         }
366     }
367
368     return String::adopt(rebalancedString);
369 }
370
371 bool isTableStructureNode(const Node *node)
372 {
373     RenderObject* renderer = node->renderer();
374     return (renderer && (renderer->isTableCell() || renderer->isTableRow() || renderer->isTableSection() || renderer->isRenderTableCol()));
375 }
376
377 const String& nonBreakingSpaceString()
378 {
379     DEPRECATED_DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));
380     return nonBreakingSpaceString;
381 }
382
383 // FIXME: need to dump this
384 bool isSpecialElement(const Node *n)
385 {
386     if (!n)
387         return false;
388         
389     if (!n->isHTMLElement())
390         return false;
391
392     if (n->isLink())
393         return true;
394
395     RenderObject* renderer = n->renderer();
396     if (!renderer)
397         return false;
398         
399     if (renderer->style().display() == TABLE || renderer->style().display() == INLINE_TABLE)
400         return true;
401
402     if (renderer->style().isFloating())
403         return true;
404
405     if (renderer->style().position() != StaticPosition)
406         return true;
407         
408     return false;
409 }
410
411 static Node* firstInSpecialElement(const Position& pos)
412 {
413     Node* rootEditableElement = pos.containerNode()->rootEditableElement();
414     for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
415         if (isSpecialElement(n)) {
416             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
417             VisiblePosition firstInElement = VisiblePosition(firstPositionInOrBeforeNode(n), DOWNSTREAM);
418             if (isRenderedTable(n) && vPos == firstInElement.next())
419                 return n;
420             if (vPos == firstInElement)
421                 return n;
422         }
423     return 0;
424 }
425
426 static Node* lastInSpecialElement(const Position& pos)
427 {
428     Node* rootEditableElement = pos.containerNode()->rootEditableElement();
429     for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
430         if (isSpecialElement(n)) {
431             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
432             VisiblePosition lastInElement = VisiblePosition(lastPositionInOrAfterNode(n), DOWNSTREAM);
433             if (isRenderedTable(n) && vPos == lastInElement.previous())
434                 return n;
435             if (vPos == lastInElement)
436                 return n;
437         }
438     return 0;
439 }
440
441 bool isFirstVisiblePositionInSpecialElement(const Position& pos)
442 {
443     return firstInSpecialElement(pos);
444 }
445
446 Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)
447 {
448     Node* n = firstInSpecialElement(pos);
449     if (!n)
450         return pos;
451     Position result = positionInParentBeforeNode(n);
452     if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
453         return pos;
454     if (containingSpecialElement)
455         *containingSpecialElement = n;
456     return result;
457 }
458
459 bool isLastVisiblePositionInSpecialElement(const Position& pos)
460 {
461     return lastInSpecialElement(pos);
462 }
463
464 Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)
465 {
466     Node* n = lastInSpecialElement(pos);
467     if (!n)
468         return pos;
469     Position result = positionInParentAfterNode(n);
470     if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
471         return pos;
472     if (containingSpecialElement)
473         *containingSpecialElement = n;
474     return result;
475 }
476
477 Position positionOutsideContainingSpecialElement(const Position &pos, Node **containingSpecialElement)
478 {
479     if (isFirstVisiblePositionInSpecialElement(pos))
480         return positionBeforeContainingSpecialElement(pos, containingSpecialElement);
481     if (isLastVisiblePositionInSpecialElement(pos))
482         return positionAfterContainingSpecialElement(pos, containingSpecialElement);
483     return pos;
484 }
485
486 Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)
487 {
488     Position upstream(visiblePosition.deepEquivalent().upstream());
489     if (upstream.deprecatedNode() && upstream.deprecatedNode()->renderer() && upstream.deprecatedNode()->renderer()->isTable() && upstream.atLastEditingPositionForNode())
490         return upstream.deprecatedNode();
491     
492     return 0;
493 }
494
495 Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)
496 {
497     Position downstream(visiblePosition.deepEquivalent().downstream());
498     if (downstream.deprecatedNode() && downstream.deprecatedNode()->renderer() && downstream.deprecatedNode()->renderer()->isTable() && downstream.atFirstEditingPositionForNode())
499         return downstream.deprecatedNode();
500     
501     return 0;
502 }
503
504 // Returns the visible position at the beginning of a node
505 VisiblePosition visiblePositionBeforeNode(Node* node)
506 {
507     ASSERT(node);
508     if (node->hasChildNodes())
509         return VisiblePosition(firstPositionInOrBeforeNode(node), DOWNSTREAM);
510     ASSERT(node->parentNode());
511     ASSERT(!node->parentNode()->isShadowRoot());
512     return positionInParentBeforeNode(node);
513 }
514
515 // Returns the visible position at the ending of a node
516 VisiblePosition visiblePositionAfterNode(Node* node)
517 {
518     ASSERT(node);
519     if (node->hasChildNodes())
520         return VisiblePosition(lastPositionInOrAfterNode(node), DOWNSTREAM);
521     ASSERT(node->parentNode());
522     ASSERT(!node->parentNode()->isShadowRoot());
523     return positionInParentAfterNode(node);
524 }
525
526 bool isListElement(Node *n)
527 {
528     return (n && (n->hasTagName(ulTag) || n->hasTagName(olTag) || n->hasTagName(dlTag)));
529 }
530
531 bool isListItem(const Node *n)
532 {
533     return n && (isListElement(n->parentNode()) || (n->renderer() && n->renderer()->isListItem()));
534 }
535
536 Element* enclosingElementWithTag(const Position& position, const QualifiedName& tagName)
537 {
538     if (position.isNull())
539         return nullptr;
540
541     Node* root = highestEditableRoot(position);
542     for (Node* node = position.deprecatedNode(); node; node = node->parentNode()) {
543         if (root && !node->hasEditableStyle())
544             continue;
545         if (!is<Element>(*node))
546             continue;
547         if (downcast<Element>(*node).hasTagName(tagName))
548             return downcast<Element>(node);
549         if (node == root)
550             return nullptr;
551     }
552
553     return nullptr;
554 }
555
556 Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule)
557 {
558     // FIXME: support CanSkipCrossEditingBoundary
559     ASSERT(rule == CanCrossEditingBoundary || rule == CannotCrossEditingBoundary);
560     if (p.isNull())
561         return 0;
562         
563     Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
564     for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
565         // Don't return a non-editable node if the input position was editable, since
566         // the callers from editing will no doubt want to perform editing inside the returned node.
567         if (root && !n->hasEditableStyle())
568             continue;
569         if (nodeIsOfType(n))
570             return n;
571         if (n == root)
572             return 0;
573     }
574     
575     return 0;
576 }
577
578 Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule, Node* stayWithin)
579 {
580     Node* highest = 0;
581     Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
582     for (Node* n = p.containerNode(); n && n != stayWithin; n = n->parentNode()) {
583         if (root && !n->hasEditableStyle())
584             continue;
585         if (nodeIsOfType(n))
586             highest = n;
587         if (n == root)
588             break;
589     }
590     
591     return highest;
592 }
593
594 static bool hasARenderedDescendant(Node* node, Node* excludedNode)
595 {
596     for (Node* n = node->firstChild(); n;) {
597         if (n == excludedNode) {
598             n = NodeTraversal::nextSkippingChildren(*n, node);
599             continue;
600         }
601         if (n->renderer())
602             return true;
603         n = NodeTraversal::next(*n, node);
604     }
605     return false;
606 }
607
608 Node* highestNodeToRemoveInPruning(Node* node)
609 {
610     Node* previousNode = 0;
611     Node* rootEditableElement = node ? node->rootEditableElement() : 0;
612     for (; node; node = node->parentNode()) {
613         if (RenderObject* renderer = node->renderer()) {
614             if (!renderer->canHaveChildren() || hasARenderedDescendant(node, previousNode) || rootEditableElement == node)
615                 return previousNode;
616         }
617         previousNode = node;
618     }
619     return 0;
620 }
621
622 Node* enclosingTableCell(const Position& p)
623 {
624     return downcast<Element>(enclosingNodeOfType(p, isTableCell));
625 }
626
627 Element* enclosingAnchorElement(const Position& p)
628 {
629     if (p.isNull())
630         return nullptr;
631
632     for (Node* node = p.deprecatedNode(); node; node = node->parentNode()) {
633         if (is<Element>(*node) && node->isLink())
634             return downcast<Element>(node);
635     }
636     return nullptr;
637 }
638
639 HTMLElement* enclosingList(Node* node)
640 {
641     if (!node)
642         return nullptr;
643         
644     Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
645     
646     for (ContainerNode* ancestor = node->parentNode(); ancestor; ancestor = ancestor->parentNode()) {
647         if (is<HTMLUListElement>(*ancestor) || is<HTMLOListElement>(*ancestor))
648             return downcast<HTMLElement>(ancestor);
649         if (ancestor == root)
650             return nullptr;
651     }
652     
653     return nullptr;
654 }
655
656 Node* enclosingListChild(Node *node)
657 {
658     if (!node)
659         return nullptr;
660     // Check for a list item element, or for a node whose parent is a list element. Such a node
661     // will appear visually as a list item (but without a list marker)
662     Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
663     
664     // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()
665     for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
666         if (n->hasTagName(liTag) || (isListElement(n->parentNode()) && n != root))
667             return n;
668         if (n == root || isTableCell(n))
669             return nullptr;
670     }
671     
672     return nullptr;
673 }
674
675 static HTMLElement* embeddedSublist(Node* listItem)
676 {
677     // Check the DOM so that we'll find collapsed sublists without renderers.
678     for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {
679         if (isListElement(n))
680             return downcast<HTMLElement>(n);
681     }
682     
683     return nullptr;
684 }
685
686 static Node* appendedSublist(Node* listItem)
687 {
688     // Check the DOM so that we'll find collapsed sublists without renderers.
689     for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {
690         if (isListElement(n))
691             return downcast<HTMLElement>(n);
692         if (isListItem(listItem))
693             return nullptr;
694     }
695     
696     return nullptr;
697 }
698
699 // FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph
700 Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)
701 {
702     // Check that position is on a line by itself inside a list item
703     Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().deprecatedNode());
704     if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))
705         return 0;
706
707     VisiblePosition firstInListChild(firstPositionInOrBeforeNode(listChildNode));
708     VisiblePosition lastInListChild(lastPositionInOrAfterNode(listChildNode));
709
710     if (firstInListChild != visiblePos || lastInListChild != visiblePos)
711         return 0;
712     
713     if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))
714         return 0;
715         
716     return listChildNode;
717 }
718
719 HTMLElement* outermostEnclosingList(Node* node, Node* rootList)
720 {
721     HTMLElement* list = enclosingList(node);
722     if (!list)
723         return 0;
724
725     while (HTMLElement* nextList = enclosingList(list)) {
726         if (nextList == rootList)
727             break;
728         list = nextList;
729     }
730
731     return list;
732 }
733
734 bool canMergeLists(Element* firstList, Element* secondList)
735 {
736     if (!firstList || !secondList || !firstList->isHTMLElement() || !secondList->isHTMLElement())
737         return false;
738
739     return firstList->hasTagName(secondList->tagQName()) // make sure the list types match (ol vs. ul)
740     && firstList->hasEditableStyle() && secondList->hasEditableStyle() // both lists are editable
741     && firstList->rootEditableElement() == secondList->rootEditableElement() // don't cross editing boundaries
742     && isVisiblyAdjacent(positionInParentAfterNode(firstList), positionInParentBeforeNode(secondList));
743     // Make sure there is no visible content between this li and the previous list
744 }
745
746 Node* highestAncestor(Node* node)
747 {
748     ASSERT(node);
749     Node* parent = node;
750     while ((node = node->parentNode()))
751         parent = node;
752     return parent;
753 }
754
755 static Node* previousNodeConsideringAtomicNodes(const Node* node)
756 {
757     if (node->previousSibling()) {
758         Node* n = node->previousSibling();
759         while (!isAtomicNode(n) && n->lastChild())
760             n = n->lastChild();
761         return n;
762     }
763     if (node->parentNode())
764         return node->parentNode();
765     return 0;
766 }
767
768 static Node* nextNodeConsideringAtomicNodes(const Node* node)
769 {
770     if (!isAtomicNode(node) && node->firstChild())
771         return node->firstChild();
772     if (node->nextSibling())
773         return node->nextSibling();
774     const Node* n = node;
775     while (n && !n->nextSibling())
776         n = n->parentNode();
777     if (n)
778         return n->nextSibling();
779     return 0;
780 }
781
782 Node* previousLeafNode(const Node* node)
783 {
784     Node* n = previousNodeConsideringAtomicNodes(node);
785     while (n) {
786         if (isAtomicNode(n))
787             return n;
788         n = previousNodeConsideringAtomicNodes(n);
789     }
790     return 0;
791 }
792
793 Node* nextLeafNode(const Node* node)
794 {
795     Node* n = nextNodeConsideringAtomicNodes(node);
796     while (n) {
797         if (isAtomicNode(n))
798             return n;
799         n = nextNodeConsideringAtomicNodes(n);
800     }
801     return 0;
802 }
803
804 // FIXME: do not require renderer, so that this can be used within fragments
805 bool isRenderedTable(const Node* n)
806 {
807     if (!n || !n->isElementNode())
808         return false;
809
810     RenderObject* renderer = n->renderer();
811     return (renderer && renderer->isTable());
812 }
813
814 bool isTableCell(const Node* node)
815 {
816     RenderObject* r = node->renderer();
817     if (!r)
818         return node->hasTagName(tdTag) || node->hasTagName(thTag);
819     
820     return r->isTableCell();
821 }
822
823 bool isEmptyTableCell(const Node* node)
824 {
825     // Returns true IFF the passed in node is one of:
826     //   .) a table cell with no children,
827     //   .) a table cell with a single BR child, and which has no other child renderers, including :before and :after renderers
828     //   .) the BR child of such a table cell
829
830     // Find rendered node
831     while (node && !node->renderer())
832         node = node->parentNode();
833     if (!node)
834         return false;
835
836     // Make sure the rendered node is a table cell or <br>.
837     // If it's a <br>, then the parent node has to be a table cell.
838     RenderObject* renderer = node->renderer();
839     if (renderer->isBR()) {
840         renderer = renderer->parent();
841         if (!renderer)
842             return false;
843     }
844     if (!is<RenderTableCell>(*renderer))
845         return false;
846
847     // Check that the table cell contains no child renderers except for perhaps a single <br>.
848     RenderObject* childRenderer = downcast<RenderTableCell>(*renderer).firstChild();
849     if (!childRenderer)
850         return true;
851     if (!childRenderer->isBR())
852         return false;
853     return !childRenderer->nextSibling();
854 }
855
856 PassRefPtr<HTMLElement> createDefaultParagraphElement(Document& document)
857 {
858     switch (document.frame()->editor().defaultParagraphSeparator()) {
859     case EditorParagraphSeparatorIsDiv:
860         return HTMLDivElement::create(document);
861     case EditorParagraphSeparatorIsP:
862         return HTMLParagraphElement::create(document);
863     }
864
865     ASSERT_NOT_REACHED();
866     return 0;
867 }
868
869 PassRefPtr<HTMLElement> createBreakElement(Document& document)
870 {
871     return HTMLBRElement::create(document);
872 }
873
874 PassRefPtr<HTMLElement> createOrderedListElement(Document& document)
875 {
876     return HTMLOListElement::create(document);
877 }
878
879 PassRefPtr<HTMLElement> createUnorderedListElement(Document& document)
880 {
881     return HTMLUListElement::create(document);
882 }
883
884 PassRefPtr<HTMLElement> createListItemElement(Document& document)
885 {
886     return HTMLLIElement::create(document);
887 }
888
889 Ref<HTMLElement> createHTMLElement(Document& document, const QualifiedName& name)
890 {
891     return HTMLElementFactory::createElement(name, document);
892 }
893
894 Ref<HTMLElement> createHTMLElement(Document& document, const AtomicString& tagName)
895 {
896     return createHTMLElement(document, QualifiedName(nullAtom, tagName, xhtmlNamespaceURI));
897 }
898
899 bool isTabSpanNode(const Node *node)
900 {
901     return node && node->hasTagName(spanTag) && node->isElementNode() && static_cast<const Element *>(node)->getAttribute(classAttr) == AppleTabSpanClass;
902 }
903
904 bool isTabSpanTextNode(const Node *node)
905 {
906     return node && node->isTextNode() && node->parentNode() && isTabSpanNode(node->parentNode());
907 }
908
909 Node* tabSpanNode(const Node *node)
910 {
911     return isTabSpanTextNode(node) ? node->parentNode() : 0;
912 }
913     
914 Position positionOutsideTabSpan(const Position& pos)
915 {
916     Node* node = pos.containerNode();
917     if (isTabSpanTextNode(node))
918         node = tabSpanNode(node);
919     else if (!isTabSpanNode(node))
920         return pos;
921
922     if (node && VisiblePosition(pos) == lastPositionInNode(node))
923         return positionInParentAfterNode(node);
924
925     return positionInParentBeforeNode(node);
926 }
927
928 PassRefPtr<Element> createTabSpanElement(Document& document, PassRefPtr<Node> prpTabTextNode)
929 {
930     RefPtr<Node> tabTextNode = prpTabTextNode;
931
932     // Make the span to hold the tab.
933     RefPtr<Element> spanElement = document.createElement(spanTag, false);
934     spanElement->setAttribute(classAttr, AppleTabSpanClass);
935     spanElement->setAttribute(styleAttr, "white-space:pre");
936
937     // Add tab text to that span.
938     if (!tabTextNode)
939         tabTextNode = document.createEditingTextNode("\t");
940
941     spanElement->appendChild(tabTextNode.release(), ASSERT_NO_EXCEPTION);
942
943     return spanElement.release();
944 }
945
946 PassRefPtr<Element> createTabSpanElement(Document& document, const String& tabText)
947 {
948     return createTabSpanElement(document, document.createTextNode(tabText));
949 }
950
951 PassRefPtr<Element> createTabSpanElement(Document& document)
952 {
953     return createTabSpanElement(document, PassRefPtr<Node>());
954 }
955
956 bool isNodeRendered(const Node* node)
957 {
958     if (!node)
959         return false;
960
961     RenderObject* renderer = node->renderer();
962     if (!renderer)
963         return false;
964
965     return renderer->style().visibility() == VISIBLE;
966 }
967
968 unsigned numEnclosingMailBlockquotes(const Position& p)
969 {
970     unsigned num = 0;
971     for (Node* n = p.deprecatedNode(); n; n = n->parentNode())
972         if (isMailBlockquote(n))
973             num++;
974     
975     return num;
976 }
977
978 void updatePositionForNodeRemoval(Position& position, Node& node)
979 {
980     if (position.isNull())
981         return;
982     switch (position.anchorType()) {
983     case Position::PositionIsBeforeChildren:
984         if (node.containsIncludingShadowDOM(position.containerNode()))
985             position = positionInParentBeforeNode(&node);
986         break;
987     case Position::PositionIsAfterChildren:
988         if (node.containsIncludingShadowDOM(position.containerNode()))
989             position = positionInParentBeforeNode(&node);
990         break;
991     case Position::PositionIsOffsetInAnchor:
992         if (position.containerNode() == node.parentNode() && static_cast<unsigned>(position.offsetInContainerNode()) > node.computeNodeIndex())
993             position.moveToOffset(position.offsetInContainerNode() - 1);
994         else if (node.containsIncludingShadowDOM(position.containerNode()))
995             position = positionInParentBeforeNode(&node);
996         break;
997     case Position::PositionIsAfterAnchor:
998         if (node.containsIncludingShadowDOM(position.anchorNode()))
999             position = positionInParentAfterNode(&node);
1000         break;
1001     case Position::PositionIsBeforeAnchor:
1002         if (node.containsIncludingShadowDOM(position.anchorNode()))
1003             position = positionInParentBeforeNode(&node);
1004         break;
1005     }
1006 }
1007
1008 bool isMailBlockquote(const Node *node)
1009 {
1010     if (!node || !node->hasTagName(blockquoteTag))
1011         return false;
1012         
1013     return static_cast<const Element *>(node)->getAttribute("type") == "cite";
1014 }
1015
1016 int caretMinOffset(const Node* n)
1017 {
1018     RenderObject* r = n->renderer();
1019     ASSERT(!n->isCharacterDataNode() || !r || r->isText()); // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
1020     return r ? r->caretMinOffset() : 0;
1021 }
1022
1023 // If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise 
1024 // return the number of children for container nodes and the length for unrendered text nodes.
1025 int caretMaxOffset(const Node* n)
1026 {
1027     // For rendered text nodes, return the last position that a caret could occupy.
1028     if (n->isTextNode() && n->renderer())
1029         return n->renderer()->caretMaxOffset();
1030     // For containers return the number of children. For others do the same as above.
1031     return lastOffsetForEditing(n);
1032 }
1033
1034 bool lineBreakExistsAtVisiblePosition(const VisiblePosition& visiblePosition)
1035 {
1036     return lineBreakExistsAtPosition(visiblePosition.deepEquivalent().downstream());
1037 }
1038
1039 bool lineBreakExistsAtPosition(const Position& position)
1040 {
1041     if (position.isNull())
1042         return false;
1043     
1044     if (position.anchorNode()->hasTagName(brTag) && position.atFirstEditingPositionForNode())
1045         return true;
1046     
1047     if (!position.anchorNode()->renderer())
1048         return false;
1049     
1050     if (!is<Text>(*position.anchorNode()) || !position.anchorNode()->renderer()->style().preserveNewline())
1051         return false;
1052     
1053     Text& textNode = downcast<Text>(*position.anchorNode());
1054     unsigned offset = position.offsetInContainerNode();
1055     return offset < textNode.length() && textNode.data()[offset] == '\n';
1056 }
1057
1058 // Modifies selections that have an end point at the edge of a table
1059 // that contains the other endpoint so that they don't confuse
1060 // code that iterates over selected paragraphs.
1061 VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)
1062 {
1063     VisibleSelection newSelection(original);
1064     VisiblePosition startOfSelection(newSelection.visibleStart());
1065     VisiblePosition endOfSelection(newSelection.visibleEnd());
1066     
1067     // If the end of the selection to modify is just after a table, and
1068     // if the start of the selection is inside that table, then the last paragraph
1069     // that we'll want modify is the last one inside the table, not the table itself
1070     // (a table is itself a paragraph).
1071     if (Node* table = isFirstPositionAfterTable(endOfSelection))
1072         if (startOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(table))
1073             newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(CannotCrossEditingBoundary));
1074     
1075     // If the start of the selection to modify is just before a table,
1076     // and if the end of the selection is inside that table, then the first paragraph
1077     // we'll want to modify is the first one inside the table, not the paragraph
1078     // containing the table itself.
1079     if (Node* table = isLastPositionBeforeTable(startOfSelection))
1080         if (endOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(table))
1081             newSelection = VisibleSelection(startOfSelection.next(CannotCrossEditingBoundary), endOfSelection);
1082     
1083     return newSelection;
1084 }
1085
1086 // FIXME: indexForVisiblePosition and visiblePositionForIndex use TextIterators to convert between 
1087 // VisiblePositions and indices. But TextIterator iteration using TextIteratorEmitsCharactersBetweenAllVisiblePositions 
1088 // does not exactly match VisiblePosition iteration, so using them to preserve a selection during an editing 
1089 // opertion is unreliable. TextIterator's TextIteratorEmitsCharactersBetweenAllVisiblePositions mode needs to be fixed, 
1090 // or these functions need to be changed to iterate using actual VisiblePositions.
1091 // FIXME: Deploy these functions everywhere that TextIterators are used to convert between VisiblePositions and indices.
1092 int indexForVisiblePosition(const VisiblePosition& visiblePosition, RefPtr<ContainerNode>& scope)
1093 {
1094     if (visiblePosition.isNull())
1095         return 0;
1096
1097     Position p(visiblePosition.deepEquivalent());
1098     Document& document = p.anchorNode()->document();
1099     ShadowRoot* shadowRoot = p.anchorNode()->containingShadowRoot();
1100
1101     if (shadowRoot)
1102         scope = shadowRoot;
1103     else
1104         scope = document.documentElement();
1105
1106     RefPtr<Range> range = Range::create(document, firstPositionInNode(scope.get()), p.parentAnchoredEquivalent());
1107     return TextIterator::rangeLength(range.get(), true);
1108 }
1109
1110 // FIXME: Merge these two functions.
1111 int indexForVisiblePosition(Node* node, const VisiblePosition& visiblePosition, bool forSelectionPreservation)
1112 {
1113     ASSERT(node);
1114     RefPtr<Range> range = Range::create(node->document(), firstPositionInNode(node), visiblePosition.deepEquivalent().parentAnchoredEquivalent());
1115     return TextIterator::rangeLength(range.get(), forSelectionPreservation);
1116 }
1117
1118 VisiblePosition visiblePositionForIndex(int index, ContainerNode* scope)
1119 {
1120     RefPtr<Range> range = TextIterator::rangeFromLocationAndLength(scope, index, 0, true);
1121     // Check for an invalid index. Certain editing operations invalidate indices because 
1122     // of problems with TextIteratorEmitsCharactersBetweenAllVisiblePositions.
1123     if (!range)
1124         return VisiblePosition();
1125     return VisiblePosition(range->startPosition());
1126 }
1127
1128 VisiblePosition visiblePositionForIndexUsingCharacterIterator(Node* node, int index)
1129 {
1130     ASSERT(node);
1131     if (index <= 0)
1132         return VisiblePosition(firstPositionInOrBeforeNode(node), DOWNSTREAM);
1133
1134     RefPtr<Range> range = Range::create(node->document());
1135     range->selectNodeContents(node, IGNORE_EXCEPTION);
1136     CharacterIterator it(*range);
1137     it.advance(index - 1);
1138     return VisiblePosition(it.atEnd() ? range->endPosition() : it.range()->endPosition(), UPSTREAM);
1139 }
1140
1141 // Determines whether two positions are visibly next to each other (first then second)
1142 // while ignoring whitespaces and unrendered nodes
1143 bool isVisiblyAdjacent(const Position& first, const Position& second)
1144 {
1145     return VisiblePosition(first) == VisiblePosition(second.upstream());
1146 }
1147
1148 // Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1149 // Call this function to determine whether a node is visibly fit inside selectedRange
1150 bool isNodeVisiblyContainedWithin(Node* node, const Range* selectedRange)
1151 {
1152     ASSERT(node);
1153     ASSERT(selectedRange);
1154     // If the node is inside the range, then it surely is contained within
1155     if (selectedRange->compareNode(node, IGNORE_EXCEPTION) == Range::NODE_INSIDE)
1156         return true;
1157
1158     bool startIsVisuallySame = visiblePositionBeforeNode(node) == selectedRange->startPosition();
1159     if (startIsVisuallySame && comparePositions(positionInParentAfterNode(node), selectedRange->endPosition()) < 0)
1160         return true;
1161
1162     bool endIsVisuallySame = visiblePositionAfterNode(node) == selectedRange->endPosition();
1163     if (endIsVisuallySame && comparePositions(selectedRange->startPosition(), positionInParentBeforeNode(node)) < 0)
1164         return true;
1165
1166     return startIsVisuallySame && endIsVisuallySame;
1167 }
1168
1169 bool isRenderedAsNonInlineTableImageOrHR(const Node* node)
1170 {
1171     if (!node)
1172         return false;
1173     RenderObject* renderer = node->renderer();
1174     return renderer && ((renderer->isTable() && !renderer->isInline()) || (renderer->isImage() && !renderer->isInline()) || renderer->isHR());
1175 }
1176
1177 bool areIdenticalElements(const Node* first, const Node* second)
1178 {
1179     if (!is<Element>(*first) || !is<Element>(*second))
1180         return false;
1181
1182     const Element& firstElement = downcast<Element>(*first);
1183     const Element& secondElement = downcast<Element>(*second);
1184     if (!firstElement.hasTagName(secondElement.tagQName()))
1185         return false;
1186
1187     return firstElement.hasEquivalentAttributes(&secondElement);
1188 }
1189
1190 bool isNonTableCellHTMLBlockElement(const Node* node)
1191 {
1192     return node->hasTagName(listingTag)
1193         || node->hasTagName(olTag)
1194         || node->hasTagName(preTag)
1195         || is<HTMLTableElement>(*node)
1196         || node->hasTagName(ulTag)
1197         || node->hasTagName(xmpTag)
1198         || node->hasTagName(h1Tag)
1199         || node->hasTagName(h2Tag)
1200         || node->hasTagName(h3Tag)
1201         || node->hasTagName(h4Tag)
1202         || node->hasTagName(h5Tag);
1203 }
1204
1205 Position adjustedSelectionStartForStyleComputation(const VisibleSelection& selection)
1206 {
1207     // This function is used by range style computations to avoid bugs like:
1208     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1209     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up 
1210     // with a spurious "mixed" style.
1211
1212     VisiblePosition visiblePosition = selection.start();
1213     if (visiblePosition.isNull())
1214         return Position();
1215
1216     // if the selection is a caret, just return the position, since the style
1217     // behind us is relevant
1218     if (selection.isCaret())
1219         return visiblePosition.deepEquivalent();
1220
1221     // if the selection starts just before a paragraph break, skip over it
1222     if (isEndOfParagraph(visiblePosition))
1223         return visiblePosition.next().deepEquivalent().downstream();
1224
1225     // otherwise, make sure to be at the start of the first selected node,
1226     // instead of possibly at the end of the last node before the selection
1227     return visiblePosition.deepEquivalent().downstream();
1228 }
1229
1230 // FIXME: Should this be deprecated like deprecatedEnclosingBlockFlowElement is?
1231 bool isBlockFlowElement(const Node* node)
1232 {
1233     if (!node->isElementNode())
1234         return false;
1235     RenderObject* renderer = node->renderer();
1236     return renderer && renderer->isRenderBlockFlow();
1237 }
1238
1239 Element* deprecatedEnclosingBlockFlowElement(Node* node)
1240 {
1241     if (!node)
1242         return nullptr;
1243     if (isBlockFlowElement(node))
1244         return downcast<Element>(node);
1245     while ((node = node->parentNode())) {
1246         if (isBlockFlowElement(node) || is<HTMLBodyElement>(*node))
1247             return downcast<Element>(node);
1248     }
1249     return nullptr;
1250 }
1251
1252 static inline bool caretRendersInsideNode(Node* node)
1253 {
1254     return node && !isRenderedTable(node) && !editingIgnoresContent(node);
1255 }
1256
1257 RenderBlock* rendererForCaretPainting(Node* node)
1258 {
1259     if (!node)
1260         return nullptr;
1261
1262     RenderObject* renderer = node->renderer();
1263     if (!renderer)
1264         return nullptr;
1265
1266     // If caretNode is a block and caret is inside it, then caret should be painted by that block.
1267     bool paintedByBlock = is<RenderBlockFlow>(*renderer) && caretRendersInsideNode(node);
1268     return paintedByBlock ? downcast<RenderBlock>(renderer) : renderer->containingBlock();
1269 }
1270
1271 LayoutRect localCaretRectInRendererForCaretPainting(const VisiblePosition& caretPosition, RenderBlock*& caretPainter)
1272 {
1273     if (caretPosition.isNull())
1274         return LayoutRect();
1275
1276     ASSERT(caretPosition.deepEquivalent().deprecatedNode()->renderer());
1277
1278     // First compute a rect local to the renderer at the selection start.
1279     RenderObject* renderer;
1280     LayoutRect localRect = caretPosition.localCaretRect(renderer);
1281
1282     // Get the renderer that will be responsible for painting the caret
1283     // (which is either the renderer we just found, or one of its containers).
1284     caretPainter = rendererForCaretPainting(caretPosition.deepEquivalent().deprecatedNode());
1285
1286     // Compute an offset between the renderer and the caretPainter.
1287     while (renderer != caretPainter) {
1288         RenderElement* containerObject = renderer->container();
1289         if (!containerObject)
1290             return LayoutRect();
1291         localRect.move(renderer->offsetFromContainer(*containerObject, localRect.location()));
1292         renderer = containerObject;
1293     }
1294
1295     return localRect;
1296 }
1297
1298 IntRect absoluteBoundsForLocalCaretRect(RenderBlock* rendererForCaretPainting, const LayoutRect& rect)
1299 {
1300     if (!rendererForCaretPainting || rect.isEmpty())
1301         return IntRect();
1302
1303     LayoutRect localRect(rect);
1304     rendererForCaretPainting->flipForWritingMode(localRect);
1305     return rendererForCaretPainting->localToAbsoluteQuad(FloatRect(localRect)).enclosingBoundingBox();
1306 }
1307
1308 } // namespace WebCore