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