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