Turn avoidIntersectionWithNode into Editor member functions to encapsulate delete...
[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 COMPUTER, 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 COMPUTER, 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 "HTMLTextFormControlElement.h"
38 #include "HTMLInterchange.h"
39 #include "HTMLLIElement.h"
40 #include "HTMLNames.h"
41 #include "HTMLObjectElement.h"
42 #include "HTMLOListElement.h"
43 #include "HTMLParagraphElement.h"
44 #include "HTMLUListElement.h"
45 #include "NodeTraversal.h"
46 #include "PositionIterator.h"
47 #include "RenderObject.h"
48 #include "Range.h"
49 #include "ShadowRoot.h"
50 #include "Text.h"
51 #include "TextIterator.h"
52 #include "VisiblePosition.h"
53 #include "VisibleSelection.h"
54 #include "visible_units.h"
55 #include <wtf/Assertions.h>
56 #include <wtf/StdLibExtras.h>
57 #include <wtf/unicode/CharacterNames.h>
58
59 using namespace std;
60
61 namespace WebCore {
62
63 using namespace HTMLNames;
64
65 // Atomic means that the node has no children, or has children which are ignored for the
66 // purposes of editing.
67 bool isAtomicNode(const Node *node)
68 {
69     return node && (!node->hasChildNodes() || editingIgnoresContent(node));
70 }
71
72 // Compare two positions, taking into account the possibility that one or both
73 // could be inside a shadow tree. Only works for non-null values.
74 int comparePositions(const Position& a, const Position& b)
75 {
76     TreeScope* commonScope = commonTreeScope(a.containerNode(), b.containerNode());
77
78     ASSERT(commonScope);
79     if (!commonScope)
80         return 0;
81
82     Node* nodeA = commonScope->ancestorInThisScope(a.containerNode());
83     ASSERT(nodeA);
84     bool hasDescendentA = nodeA != a.containerNode();
85     int offsetA = hasDescendentA ? 0 : a.computeOffsetInContainerNode();
86
87     Node* nodeB = commonScope->ancestorInThisScope(b.containerNode());
88     ASSERT(nodeB);
89     bool hasDescendentB = nodeB != b.containerNode();
90     int offsetB = hasDescendentB ? 0 : b.computeOffsetInContainerNode();
91
92     int bias = 0;
93     if (nodeA == nodeB) {
94         if (hasDescendentA)
95             bias = -1;
96         else if (hasDescendentB)
97             bias = 1;
98     }
99
100     int result = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB, IGNORE_EXCEPTION);
101     return result ? result : bias;
102 }
103
104 int comparePositions(const VisiblePosition& a, const VisiblePosition& b)
105 {
106     return comparePositions(a.deepEquivalent(), b.deepEquivalent());
107 }
108
109 Node* highestEditableRoot(const Position& position, EditableType editableType)
110 {
111     Node* node = position.deprecatedNode();
112     if (!node)
113         return 0;
114         
115     Node* highestRoot = editableRootForPosition(position, editableType);
116     if (!highestRoot)
117         return 0;
118     
119     node = highestRoot;
120     while (node) {
121         if (node->rendererIsEditable(editableType))
122             highestRoot = node;
123         if (node->hasTagName(bodyTag))
124             break;
125         node = node->parentNode();
126     }
127     
128     return highestRoot;
129 }
130
131 Node* lowestEditableAncestor(Node* node)
132 {
133     if (!node)
134         return 0;
135     
136     Node *lowestRoot = 0;
137     while (node) {
138         if (node->rendererIsEditable())
139             return node->rootEditableElement();
140         if (node->hasTagName(bodyTag))
141             break;
142         node = node->parentNode();
143     }
144     
145     return lowestRoot;
146 }
147
148 bool isEditablePosition(const Position& p, EditableType editableType, EUpdateStyle updateStyle)
149 {
150     Node* node = p.deprecatedNode();
151     if (!node)
152         return false;
153     if (updateStyle == UpdateStyle)
154         node->document()->updateLayoutIgnorePendingStylesheets();
155     else
156         ASSERT(updateStyle == DoNotUpdateStyle);
157
158     if (node->renderer() && node->renderer()->isTable())
159         node = node->parentNode();
160     
161     return node->rendererIsEditable(editableType);
162 }
163
164 bool isAtUnsplittableElement(const Position& pos)
165 {
166     Node* node = pos.deprecatedNode();
167     return (node == editableRootForPosition(pos) || node == enclosingNodeOfType(pos, &isTableCell));
168 }
169     
170     
171 bool isRichlyEditablePosition(const Position& p, EditableType editableType)
172 {
173     Node* node = p.deprecatedNode();
174     if (!node)
175         return false;
176         
177     if (node->renderer() && node->renderer()->isTable())
178         node = node->parentNode();
179     
180     return node->rendererIsRichlyEditable(editableType);
181 }
182
183 Element* editableRootForPosition(const Position& p, EditableType editableType)
184 {
185     Node* node = p.containerNode();
186     if (!node)
187         return 0;
188         
189     if (node->renderer() && node->renderer()->isTable())
190         node = node->parentNode();
191     
192     return node->rootEditableElement(editableType);
193 }
194
195 // Finds the enclosing element until which the tree can be split.
196 // When a user hits ENTER, he/she won't expect this element to be split into two.
197 // You may pass it as the second argument of splitTreeToNode.
198 Element* unsplittableElementForPosition(const Position& p)
199 {
200     // Since enclosingNodeOfType won't search beyond the highest root editable node,
201     // this code works even if the closest table cell was outside of the root editable node.
202     Element* enclosingCell = static_cast<Element*>(enclosingNodeOfType(p, &isTableCell));
203     if (enclosingCell)
204         return enclosingCell;
205
206     return editableRootForPosition(p);
207 }
208
209 Position nextCandidate(const Position& position)
210 {
211     PositionIterator p = position;
212     while (!p.atEnd()) {
213         p.increment();
214         if (p.isCandidate())
215             return p;
216     }
217     return Position();
218 }
219
220 Position nextVisuallyDistinctCandidate(const Position& position)
221 {
222     Position p = position;
223     Position downstreamStart = p.downstream();
224     while (!p.atEndOfTree()) {
225         p = p.next(Character);
226         if (p.isCandidate() && p.downstream() != downstreamStart)
227             return p;
228     }
229     return Position();
230 }
231
232 Position previousCandidate(const Position& position)
233 {
234     PositionIterator p = position;
235     while (!p.atStart()) {
236         p.decrement();
237         if (p.isCandidate())
238             return p;
239     }
240     return Position();
241 }
242
243 Position previousVisuallyDistinctCandidate(const Position& position)
244 {
245     Position p = position;
246     Position downstreamStart = p.downstream();
247     while (!p.atStartOfTree()) {
248         p = p.previous(Character);
249         if (p.isCandidate() && p.downstream() != downstreamStart)
250             return p;
251     }
252     return Position();
253 }
254
255 VisiblePosition firstEditablePositionAfterPositionInRoot(const Position& position, Node* highestRoot)
256 {
257     // position falls before highestRoot.
258     if (comparePositions(position, firstPositionInNode(highestRoot)) == -1 && highestRoot->rendererIsEditable())
259         return firstPositionInNode(highestRoot);
260
261     Position p = position;
262
263     if (position.deprecatedNode()->treeScope() != highestRoot->treeScope()) {
264         Node* shadowAncestor = highestRoot->treeScope()->ancestorInThisScope(p.deprecatedNode());
265         if (!shadowAncestor)
266             return VisiblePosition();
267
268         p = positionAfterNode(shadowAncestor);
269     }
270
271     while (p.deprecatedNode() && !isEditablePosition(p) && p.deprecatedNode()->isDescendantOf(highestRoot))
272         p = isAtomicNode(p.deprecatedNode()) ? positionInParentAfterNode(p.deprecatedNode()) : nextVisuallyDistinctCandidate(p);
273     
274     if (p.deprecatedNode() && p.deprecatedNode() != highestRoot && !p.deprecatedNode()->isDescendantOf(highestRoot))
275         return VisiblePosition();
276     
277     return VisiblePosition(p);
278 }
279
280 VisiblePosition lastEditablePositionBeforePositionInRoot(const Position& position, Node* highestRoot)
281 {
282     // When position falls after highestRoot, the result is easy to compute.
283     if (comparePositions(position, lastPositionInNode(highestRoot)) == 1)
284         return lastPositionInNode(highestRoot);
285
286     Position p = position;
287
288     if (position.deprecatedNode()->treeScope() != highestRoot->treeScope()) {
289         Node* shadowAncestor = highestRoot->treeScope()->ancestorInThisScope(p.deprecatedNode());
290         if (!shadowAncestor)
291             return VisiblePosition();
292
293         p = firstPositionInOrBeforeNode(shadowAncestor);
294     }
295     
296     while (p.deprecatedNode() && !isEditablePosition(p) && p.deprecatedNode()->isDescendantOf(highestRoot))
297         p = isAtomicNode(p.deprecatedNode()) ? positionInParentBeforeNode(p.deprecatedNode()) : previousVisuallyDistinctCandidate(p);
298     
299     if (p.deprecatedNode() && p.deprecatedNode() != highestRoot && !p.deprecatedNode()->isDescendantOf(highestRoot))
300         return VisiblePosition();
301     
302     return VisiblePosition(p);
303 }
304
305 // FIXME: The method name, comment, and code say three different things here!
306 // Whether or not content before and after this node will collapse onto the same line as it.
307 bool isBlock(const Node* node)
308 {
309     return node && node->renderer() && !node->renderer()->isInline() && !node->renderer()->isRubyText();
310 }
311
312 bool isInline(const Node* node)
313 {
314     return node && node->renderer() && node->renderer()->isInline();
315 }
316
317 // FIXME: Deploy this in all of the places where enclosingBlockFlow/enclosingBlockFlowOrTableElement are used.
318 // FIXME: Pass a position to this function.  The enclosing block of [table, x] for example, should be the 
319 // block that contains the table and not the table, and this function should be the only one responsible for 
320 // knowing about these kinds of special cases.
321 Element* enclosingBlock(Node* node, EditingBoundaryCrossingRule rule)
322 {
323     Node* enclosingNode = enclosingNodeOfType(firstPositionInOrBeforeNode(node), isBlock, rule);
324     return enclosingNode && enclosingNode->isElementNode() ? toElement(enclosingNode) : 0;
325 }
326
327 TextDirection directionOfEnclosingBlock(const Position& position)
328 {
329     Node* enclosingBlockNode = enclosingBlock(position.containerNode());
330     if (!enclosingBlockNode)
331         return LTR;
332     RenderObject* renderer = enclosingBlockNode->renderer();
333     return renderer ? renderer->style()->direction() : LTR;
334 }
335
336 // This method is used to create positions in the DOM. It returns the maximum valid offset
337 // in a node.  It returns 1 for some elements even though they do not have children, which
338 // creates technically invalid DOM Positions.  Be sure to call parentAnchoredEquivalent
339 // on a Position before using it to create a DOM Range, or an exception will be thrown.
340 int lastOffsetForEditing(const Node* node)
341 {
342     ASSERT(node);
343     if (!node)
344         return 0;
345     if (node->offsetInCharacters())
346         return node->maxCharacterOffset();
347
348     if (node->hasChildNodes())
349         return node->childNodeCount();
350
351     // NOTE: This should preempt the childNodeCount for, e.g., select nodes
352     if (editingIgnoresContent(node))
353         return 1;
354
355     return 0;
356 }
357
358 String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)
359 {
360     Vector<UChar> rebalancedString;
361     append(rebalancedString, string);
362
363     bool previousCharacterWasSpace = false;
364     for (size_t i = 0; i < rebalancedString.size(); i++) {
365         if (!isWhitespace(rebalancedString[i])) {
366             previousCharacterWasSpace = false;
367             continue;
368         }
369
370         if (previousCharacterWasSpace || (!i && startIsStartOfParagraph) || (i + 1 == rebalancedString.size() && endIsEndOfParagraph)) {
371             rebalancedString[i] = noBreakSpace;
372             previousCharacterWasSpace = false;
373         } else {
374             rebalancedString[i] = ' ';
375             previousCharacterWasSpace = true;
376         }
377             
378     }
379
380     return String::adopt(rebalancedString);
381 }
382
383 bool isTableStructureNode(const Node *node)
384 {
385     RenderObject* renderer = node->renderer();
386     return (renderer && (renderer->isTableCell() || renderer->isTableRow() || renderer->isTableSection() || renderer->isRenderTableCol()));
387 }
388
389 const String& nonBreakingSpaceString()
390 {
391     DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));
392     return nonBreakingSpaceString;
393 }
394
395 // FIXME: need to dump this
396 bool isSpecialElement(const Node *n)
397 {
398     if (!n)
399         return false;
400         
401     if (!n->isHTMLElement())
402         return false;
403
404     if (n->isLink())
405         return true;
406
407     RenderObject *renderer = n->renderer();
408     if (!renderer)
409         return false;
410         
411     if (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE)
412         return true;
413
414     if (renderer->style()->isFloating())
415         return true;
416
417     if (renderer->style()->position() != StaticPosition)
418         return true;
419         
420     return false;
421 }
422
423 static Node* firstInSpecialElement(const Position& pos)
424 {
425     Node* rootEditableElement = pos.containerNode()->rootEditableElement();
426     for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
427         if (isSpecialElement(n)) {
428             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
429             VisiblePosition firstInElement = VisiblePosition(firstPositionInOrBeforeNode(n), DOWNSTREAM);
430             if (isTableElement(n) && vPos == firstInElement.next())
431                 return n;
432             if (vPos == firstInElement)
433                 return n;
434         }
435     return 0;
436 }
437
438 static Node* lastInSpecialElement(const Position& pos)
439 {
440     Node* rootEditableElement = pos.containerNode()->rootEditableElement();
441     for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
442         if (isSpecialElement(n)) {
443             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
444             VisiblePosition lastInElement = VisiblePosition(lastPositionInOrAfterNode(n), DOWNSTREAM);
445             if (isTableElement(n) && vPos == lastInElement.previous())
446                 return n;
447             if (vPos == lastInElement)
448                 return n;
449         }
450     return 0;
451 }
452
453 bool isFirstVisiblePositionInSpecialElement(const Position& pos)
454 {
455     return firstInSpecialElement(pos);
456 }
457
458 Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)
459 {
460     Node* n = firstInSpecialElement(pos);
461     if (!n)
462         return pos;
463     Position result = positionInParentBeforeNode(n);
464     if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
465         return pos;
466     if (containingSpecialElement)
467         *containingSpecialElement = n;
468     return result;
469 }
470
471 bool isLastVisiblePositionInSpecialElement(const Position& pos)
472 {
473     return lastInSpecialElement(pos);
474 }
475
476 Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)
477 {
478     Node* n = lastInSpecialElement(pos);
479     if (!n)
480         return pos;
481     Position result = positionInParentAfterNode(n);
482     if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
483         return pos;
484     if (containingSpecialElement)
485         *containingSpecialElement = n;
486     return result;
487 }
488
489 Position positionOutsideContainingSpecialElement(const Position &pos, Node **containingSpecialElement)
490 {
491     if (isFirstVisiblePositionInSpecialElement(pos))
492         return positionBeforeContainingSpecialElement(pos, containingSpecialElement);
493     if (isLastVisiblePositionInSpecialElement(pos))
494         return positionAfterContainingSpecialElement(pos, containingSpecialElement);
495     return pos;
496 }
497
498 Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)
499 {
500     Position upstream(visiblePosition.deepEquivalent().upstream());
501     if (upstream.deprecatedNode() && upstream.deprecatedNode()->renderer() && upstream.deprecatedNode()->renderer()->isTable() && upstream.atLastEditingPositionForNode())
502         return upstream.deprecatedNode();
503     
504     return 0;
505 }
506
507 Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)
508 {
509     Position downstream(visiblePosition.deepEquivalent().downstream());
510     if (downstream.deprecatedNode() && downstream.deprecatedNode()->renderer() && downstream.deprecatedNode()->renderer()->isTable() && downstream.atFirstEditingPositionForNode())
511         return downstream.deprecatedNode();
512     
513     return 0;
514 }
515
516 // Returns the visible position at the beginning of a node
517 VisiblePosition visiblePositionBeforeNode(Node* node)
518 {
519     ASSERT(node);
520     if (node->childNodeCount())
521         return VisiblePosition(firstPositionInOrBeforeNode(node), DOWNSTREAM);
522     ASSERT(node->parentNode());
523     ASSERT(!node->parentNode()->isShadowRoot());
524     return positionInParentBeforeNode(node);
525 }
526
527 // Returns the visible position at the ending of a node
528 VisiblePosition visiblePositionAfterNode(Node* node)
529 {
530     ASSERT(node);
531     if (node->childNodeCount())
532         return VisiblePosition(lastPositionInOrAfterNode(node), DOWNSTREAM);
533     ASSERT(node->parentNode());
534     ASSERT(!node->parentNode()->isShadowRoot());
535     return positionInParentAfterNode(node);
536 }
537
538 // Create a range object with two visible positions, start and end.
539 // create(PassRefPtr<Document>, const Position&, const Position&); will use deprecatedEditingOffset
540 // Use this function instead of create a regular range object (avoiding editing offset).
541 PassRefPtr<Range> createRange(PassRefPtr<Document> document, const VisiblePosition& start, const VisiblePosition& end, ExceptionCode& ec)
542 {
543     ec = 0;
544     RefPtr<Range> selectedRange = Range::create(document);
545     selectedRange->setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
546     if (!ec)
547         selectedRange->setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
548     return selectedRange.release();
549 }
550
551 // Extend rangeToExtend to include nodes that wraps range and visibly starts and ends inside or at the boudnaries of maximumRange
552 // e.g. if the original range spaned "hello" in <div>hello</div>, then this function extends the range to contain div's around it.
553 // Call this function before copying / moving paragraphs to contain all wrapping nodes.
554 // This function stops extending the range immediately below rootNode; i.e. the extended range can contain a child node of rootNode
555 // but it can never contain rootNode itself.
556 PassRefPtr<Range> extendRangeToWrappingNodes(PassRefPtr<Range> range, const Range* maximumRange, const Node* rootNode)
557 {
558     ASSERT(range);
559     ASSERT(maximumRange);
560
561     Node* ancestor = range->commonAncestorContainer(IGNORE_EXCEPTION); // Find the closest common ancestor.
562     Node* highestNode = 0;
563     // traverse through ancestors as long as they are contained within the range, content-editable, and below rootNode (could be =0).
564     while (ancestor && ancestor->rendererIsEditable() && isNodeVisiblyContainedWithin(ancestor, maximumRange) && ancestor != rootNode) {
565         highestNode = ancestor;
566         ancestor = ancestor->parentNode();
567     }
568
569     if (!highestNode)
570         return range;
571
572     // Create new range with the highest editable node contained within the range
573     RefPtr<Range> extendedRange = Range::create(range->ownerDocument());
574     extendedRange->selectNode(highestNode, IGNORE_EXCEPTION);
575     return extendedRange.release();
576 }
577
578 bool isListElement(Node *n)
579 {
580     return (n && (n->hasTagName(ulTag) || n->hasTagName(olTag) || n->hasTagName(dlTag)));
581 }
582
583 bool isListItem(Node *n)
584 {
585     return n && n->renderer() && n->renderer()->isListItem();
586 }
587
588 Node* enclosingNodeWithTag(const Position& p, const QualifiedName& tagName)
589 {
590     if (p.isNull())
591         return 0;
592         
593     Node* root = highestEditableRoot(p);
594     for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
595         if (root && !n->rendererIsEditable())
596             continue;
597         if (n->hasTagName(tagName))
598             return n;
599         if (n == root)
600             return 0;
601     }
602     
603     return 0;
604 }
605
606 Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule)
607 {
608     // FIXME: support CanSkipCrossEditingBoundary
609     ASSERT(rule == CanCrossEditingBoundary || rule == CannotCrossEditingBoundary);
610     if (p.isNull())
611         return 0;
612         
613     Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
614     for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
615         // Don't return a non-editable node if the input position was editable, since
616         // the callers from editing will no doubt want to perform editing inside the returned node.
617         if (root && !n->rendererIsEditable())
618             continue;
619         if (nodeIsOfType(n))
620             return n;
621         if (n == root)
622             return 0;
623     }
624     
625     return 0;
626 }
627
628 Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule, Node* stayWithin)
629 {
630     Node* highest = 0;
631     Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
632     for (Node* n = p.containerNode(); n && n != stayWithin; n = n->parentNode()) {
633         if (root && !n->rendererIsEditable())
634             continue;
635         if (nodeIsOfType(n))
636             highest = n;
637         if (n == root)
638             break;
639     }
640     
641     return highest;
642 }
643
644 static bool hasARenderedDescendant(Node* node, Node* excludedNode)
645 {
646     for (Node* n = node->firstChild(); n;) {
647         if (n == excludedNode) {
648             n = NodeTraversal::nextSkippingChildren(n, node);
649             continue;
650         }
651         if (n->renderer())
652             return true;
653         n = NodeTraversal::next(n, node);
654     }
655     return false;
656 }
657
658 Node* highestNodeToRemoveInPruning(Node* node)
659 {
660     Node* previousNode = 0;
661     Node* rootEditableElement = node ? node->rootEditableElement() : 0;
662     for (; node; node = node->parentNode()) {
663         if (RenderObject* renderer = node->renderer()) {
664             if (!renderer->canHaveChildren() || hasARenderedDescendant(node, previousNode) || rootEditableElement == node)
665                 return previousNode;
666         }
667         previousNode = node;
668     }
669     return 0;
670 }
671
672 Node* enclosingTableCell(const Position& p)
673 {
674     return static_cast<Element*>(enclosingNodeOfType(p, isTableCell));
675 }
676
677 Node* enclosingAnchorElement(const Position& p)
678 {
679     if (p.isNull())
680         return 0;
681     
682     Node* node = p.deprecatedNode();
683     while (node && !(node->isElementNode() && node->isLink()))
684         node = node->parentNode();
685     return node;
686 }
687
688 HTMLElement* enclosingList(Node* node)
689 {
690     if (!node)
691         return 0;
692         
693     Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
694     
695     for (ContainerNode* n = node->parentNode(); n; n = n->parentNode()) {
696         if (n->hasTagName(ulTag) || n->hasTagName(olTag))
697             return toHTMLElement(n);
698         if (n == root)
699             return 0;
700     }
701     
702     return 0;
703 }
704
705 Node* enclosingListChild(Node *node)
706 {
707     if (!node)
708         return 0;
709     // Check for a list item element, or for a node whose parent is a list element.  Such a node
710     // will appear visually as a list item (but without a list marker)
711     Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
712     
713     // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()
714     for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
715         if (n->hasTagName(liTag) || (isListElement(n->parentNode()) && n != root))
716             return n;
717         if (n == root || isTableCell(n))
718             return 0;
719     }
720     
721     return 0;
722 }
723
724 static HTMLElement* embeddedSublist(Node* listItem)
725 {
726     // Check the DOM so that we'll find collapsed sublists without renderers.
727     for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {
728         if (isListElement(n))
729             return toHTMLElement(n);
730     }
731     
732     return 0;
733 }
734
735 static Node* appendedSublist(Node* listItem)
736 {
737     // Check the DOM so that we'll find collapsed sublists without renderers.
738     for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {
739         if (isListElement(n))
740             return toHTMLElement(n);
741         if (isListItem(listItem))
742             return 0;
743     }
744     
745     return 0;
746 }
747
748 // FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph
749 Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)
750 {
751     // Check that position is on a line by itself inside a list item
752     Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().deprecatedNode());
753     if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))
754         return 0;
755
756     VisiblePosition firstInListChild(firstPositionInOrBeforeNode(listChildNode));
757     VisiblePosition lastInListChild(lastPositionInOrAfterNode(listChildNode));
758
759     if (firstInListChild != visiblePos || lastInListChild != visiblePos)
760         return 0;
761     
762     if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))
763         return 0;
764         
765     return listChildNode;
766 }
767
768 HTMLElement* outermostEnclosingList(Node* node, Node* rootList)
769 {
770     HTMLElement* list = enclosingList(node);
771     if (!list)
772         return 0;
773
774     while (HTMLElement* nextList = enclosingList(list)) {
775         if (nextList == rootList)
776             break;
777         list = nextList;
778     }
779
780     return list;
781 }
782
783 bool canMergeLists(Element* firstList, Element* secondList)
784 {
785     if (!firstList || !secondList || !firstList->isHTMLElement() || !secondList->isHTMLElement())
786         return false;
787
788     return firstList->hasTagName(secondList->tagQName())// make sure the list types match (ol vs. ul)
789     && firstList->rendererIsEditable() && secondList->rendererIsEditable() // both lists are editable
790     && firstList->rootEditableElement() == secondList->rootEditableElement()// don't cross editing boundaries
791     && isVisiblyAdjacent(positionInParentAfterNode(firstList), positionInParentBeforeNode(secondList));
792     // Make sure there is no visible content between this li and the previous list
793 }
794
795 Node* highestAncestor(Node* node)
796 {
797     ASSERT(node);
798     Node* parent = node;
799     while ((node = node->parentNode()))
800         parent = node;
801     return parent;
802 }
803
804 // FIXME: do not require renderer, so that this can be used within fragments, or rename to isRenderedTable()
805 bool isTableElement(Node* n)
806 {
807     if (!n || !n->isElementNode())
808         return false;
809
810     RenderObject* renderer = n->renderer();
811     return (renderer && (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE));
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 (!renderer->isTableCell())
845         return false;
846
847     // Check that the table cell contains no child renderers except for perhaps a single <br>.
848     RenderObject* childRenderer = 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 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const QualifiedName& name)
890 {
891     return HTMLElementFactory::createHTMLElement(name, document, 0, false);
892 }
893
894 PassRefPtr<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 (position.containerNode() == node)
985             position = positionInParentBeforeNode(node);
986         break;
987     case Position::PositionIsAfterChildren:
988         if (position.containerNode() == node)
989             position = positionInParentAfterNode(node);
990         break;
991     case Position::PositionIsOffsetInAnchor:
992         if (position.containerNode() == node->parentNode() && static_cast<unsigned>(position.offsetInContainerNode()) > node->nodeIndex())
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 (!position.anchorNode()->isTextNode() || !position.anchorNode()->renderer()->style()->preserveNewline())
1051         return false;
1052     
1053     Text* textNode = toText(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  
1093 int indexForVisiblePosition(const VisiblePosition& visiblePosition, RefPtr<ContainerNode>& scope)
1094 {
1095     if (visiblePosition.isNull())
1096         return 0;
1097
1098     Position p(visiblePosition.deepEquivalent());
1099     Document* document = p.anchorNode()->document();
1100     ShadowRoot* shadowRoot = p.anchorNode()->containingShadowRoot();
1101
1102     if (shadowRoot)
1103         scope = shadowRoot;
1104     else
1105         scope = document->documentElement();
1106
1107     RefPtr<Range> range = Range::create(document, firstPositionInNode(scope.get()), p.parentAnchoredEquivalent());
1108
1109     return TextIterator::rangeLength(range.get(), true);
1110 }
1111
1112 VisiblePosition visiblePositionForIndex(int index, ContainerNode* scope)
1113 {
1114     RefPtr<Range> range = TextIterator::rangeFromLocationAndLength(scope, index, 0, true);
1115     // Check for an invalid index. Certain editing operations invalidate indices because 
1116     // of problems with TextIteratorEmitsCharactersBetweenAllVisiblePositions.
1117     if (!range)
1118         return VisiblePosition();
1119     return VisiblePosition(range->startPosition());
1120 }
1121
1122 // Determines whether two positions are visibly next to each other (first then second)
1123 // while ignoring whitespaces and unrendered nodes
1124 bool isVisiblyAdjacent(const Position& first, const Position& second)
1125 {
1126     return VisiblePosition(first) == VisiblePosition(second.upstream());
1127 }
1128
1129 // Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1130 // Call this function to determine whether a node is visibly fit inside selectedRange
1131 bool isNodeVisiblyContainedWithin(Node* node, const Range* selectedRange)
1132 {
1133     ASSERT(node);
1134     ASSERT(selectedRange);
1135     // If the node is inside the range, then it surely is contained within
1136     if (selectedRange->compareNode(node, IGNORE_EXCEPTION) == Range::NODE_INSIDE)
1137         return true;
1138
1139     bool startIsVisuallySame = visiblePositionBeforeNode(node) == selectedRange->startPosition();
1140     if (startIsVisuallySame && comparePositions(positionInParentAfterNode(node), selectedRange->endPosition()) < 0)
1141         return true;
1142
1143     bool endIsVisuallySame = visiblePositionAfterNode(node) == selectedRange->endPosition();
1144     if (endIsVisuallySame && comparePositions(selectedRange->startPosition(), positionInParentBeforeNode(node)) < 0)
1145         return true;
1146
1147     return startIsVisuallySame && endIsVisuallySame;
1148 }
1149
1150 bool isRenderedAsNonInlineTableImageOrHR(const Node* node)
1151 {
1152     if (!node)
1153         return false;
1154     RenderObject* renderer = node->renderer();
1155     return renderer && ((renderer->isTable() && !renderer->isInline()) || (renderer->isImage() && !renderer->isInline()) || renderer->isHR());
1156 }
1157
1158 bool areIdenticalElements(const Node* first, const Node* second)
1159 {
1160     if (!first->isElementNode() || !second->isElementNode())
1161         return false;
1162
1163     const Element* firstElement = toElement(first);
1164     const Element* secondElement = toElement(second);
1165     if (!firstElement->hasTagName(secondElement->tagQName()))
1166         return false;
1167
1168     return firstElement->hasEquivalentAttributes(secondElement);
1169 }
1170
1171 bool isNonTableCellHTMLBlockElement(const Node* node)
1172 {
1173     return node->hasTagName(listingTag)
1174         || node->hasTagName(olTag)
1175         || node->hasTagName(preTag)
1176         || node->hasTagName(tableTag)
1177         || node->hasTagName(ulTag)
1178         || node->hasTagName(xmpTag)
1179         || node->hasTagName(h1Tag)
1180         || node->hasTagName(h2Tag)
1181         || node->hasTagName(h3Tag)
1182         || node->hasTagName(h4Tag)
1183         || node->hasTagName(h5Tag);
1184 }
1185     
1186 Position adjustedSelectionStartForStyleComputation(const VisibleSelection& selection)
1187 {
1188     // This function is used by range style computations to avoid bugs like:
1189     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1190     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up 
1191     // with a spurious "mixed" style.
1192
1193     VisiblePosition visiblePosition = selection.start();
1194     if (visiblePosition.isNull())
1195         return Position();
1196
1197     // if the selection is a caret, just return the position, since the style
1198     // behind us is relevant
1199     if (selection.isCaret())
1200         return visiblePosition.deepEquivalent();
1201
1202     // if the selection starts just before a paragraph break, skip over it
1203     if (isEndOfParagraph(visiblePosition))
1204         return visiblePosition.next().deepEquivalent().downstream();
1205
1206     // otherwise, make sure to be at the start of the first selected node,
1207     // instead of possibly at the end of the last node before the selection
1208     return visiblePosition.deepEquivalent().downstream();
1209 }
1210
1211 } // namespace WebCore