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