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