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