WebCore/dom/Range.cpp

   1 /*
   2  * (C) 1999 Lars Knoll (knoll@kde.org)
   3  * (C) 2000 Gunnstein Lye (gunnstein@netcom.no)
   4  * (C) 2000 Frederik Holljen (frederik.holljen@hig.no)
   5  * (C) 2001 Peter Kelly (pmk@post.com)
   6  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public License
  19  * along with this library; see the file COPYING.LIB.  If not, write to
  20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  21  * Boston, MA 02110-1301, USA.
  22  */
  23
  24 #include "config.h"
  25 #include "Range.h"
  26 #include "RangeException.h"
  27
  28 #include "CString.h"
  29 #include "ClientRect.h"
  30 #include "ClientRectList.h"
  31 #include "DocumentFragment.h"
  32 #include "FrameView.h"
  33 #include "HTMLElement.h"
  34 #include "NodeWithIndex.h"
  35 #include "ProcessingInstruction.h"
  36 #include "Text.h"
  37 #include "TextIterator.h"
  38 #include "VisiblePosition.h"
  39 #include "htmlediting.h"
  40 #include "markup.h"
  41 #include "visible_units.h"
  42 #include <stdio.h>
  43 #include <wtf/RefCountedLeakCounter.h>
  44
  45 namespace WebCore {
  46
  47 using namespace std;
  48
  49 #ifndef NDEBUG
  50 static WTF::RefCountedLeakCounter rangeCounter("Range");
  51 #endif
  52
  53 inline Range::Range(PassRefPtr<Document> ownerDocument)
  54     : m_ownerDocument(ownerDocument)
  55     , m_start(m_ownerDocument)
  56     , m_end(m_ownerDocument)
  57 {
  58 #ifndef NDEBUG
  59     rangeCounter.increment();
  60 #endif
  61
  62     m_ownerDocument->attachRange(this);
  63 }
  64
  65 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)
  66 {
  67     return adoptRef(new Range(ownerDocument));
  68 }
  69
  70 inline Range::Range(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
  71     : m_ownerDocument(ownerDocument)
  72     , m_start(m_ownerDocument)
  73     , m_end(m_ownerDocument)
  74 {
  75 #ifndef NDEBUG
  76     rangeCounter.increment();
  77 #endif
  78
  79     m_ownerDocument->attachRange(this);
  80
  81     // Simply setting the containers and offsets directly would not do any of the checking
  82     // that setStart and setEnd do, so we call those functions.
  83     ExceptionCode ec = 0;
  84     setStart(startContainer, startOffset, ec);
  85     ASSERT(!ec);
  86     setEnd(endContainer, endOffset, ec);
  87     ASSERT(!ec);
  88 }
  89
  90 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
  91 {
  92     return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
  93 }
  94
  95 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, const Position& start, const Position& end)
  96 {
  97     // FIXME: we shouldn't be using deprecatedEditingOffset here
  98     return adoptRef(new Range(ownerDocument, start.node(), start.deprecatedEditingOffset(), end.node(), end.deprecatedEditingOffset()));
  99 }
 100
 101 Range::~Range()
 102 {
 103     // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044
 104     m_ownerDocument->detachRange(this);
 105
 106 #ifndef NDEBUG
 107     rangeCounter.decrement();
 108 #endif
 109 }
 110
 111 Node* Range::startContainer(ExceptionCode& ec) const
 112 {
 113     if (!m_start.container()) {
 114         ec = INVALID_STATE_ERR;
 115         return 0;
 116     }
 117
 118     return m_start.container();
 119 }
 120
 121 int Range::startOffset(ExceptionCode& ec) const
 122 {
 123     if (!m_start.container()) {
 124         ec = INVALID_STATE_ERR;
 125         return 0;
 126     }
 127
 128     return m_start.offset();
 129 }
 130
 131 Node* Range::endContainer(ExceptionCode& ec) const
 132 {
 133     if (!m_start.container()) {
 134         ec = INVALID_STATE_ERR;
 135         return 0;
 136     }
 137
 138     return m_end.container();
 139 }
 140
 141 int Range::endOffset(ExceptionCode& ec) const
 142 {
 143     if (!m_start.container()) {
 144         ec = INVALID_STATE_ERR;
 145         return 0;
 146     }
 147
 148     return m_end.offset();
 149 }
 150
 151 Node* Range::commonAncestorContainer(ExceptionCode& ec) const
 152 {
 153     if (!m_start.container()) {
 154         ec = INVALID_STATE_ERR;
 155         return 0;
 156     }
 157
 158     return commonAncestorContainer(m_start.container(), m_end.container());
 159 }
 160
 161 Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
 162 {
 163     for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
 164         for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
 165             if (parentA == parentB)
 166                 return parentA;
 167         }
 168     }
 169     return 0;
 170 }
 171
 172 bool Range::collapsed(ExceptionCode& ec) const
 173 {
 174     if (!m_start.container()) {
 175         ec = INVALID_STATE_ERR;
 176         return 0;
 177     }
 178
 179     return m_start == m_end;
 180 }
 181
 182 void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
 183 {
 184     if (!m_start.container()) {
 185         ec = INVALID_STATE_ERR;
 186         return;
 187     }
 188
 189     if (!refNode) {
 190         ec = NOT_FOUND_ERR;
 191         return;
 192     }
 193
 194     if (refNode->document() != m_ownerDocument) {
 195         ec = WRONG_DOCUMENT_ERR;
 196         return;
 197     }
 198
 199     ec = 0;
 200     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
 201     if (ec)
 202         return;
 203
 204     m_start.set(refNode, offset, childNode);
 205
 206     // check if different root container
 207     Node* endRootContainer = m_end.container();
 208     while (endRootContainer->parentNode())
 209         endRootContainer = endRootContainer->parentNode();
 210     Node* startRootContainer = m_start.container();
 211     while (startRootContainer->parentNode())
 212         startRootContainer = startRootContainer->parentNode();
 213     if (startRootContainer != endRootContainer)
 214         collapse(true, ec);
 215     // check if new start after end
 216     else if (compareBoundaryPoints(m_start, m_end) > 0)
 217         collapse(true, ec);
 218 }
 219
 220 void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
 221 {
 222     if (!m_start.container()) {
 223         ec = INVALID_STATE_ERR;
 224         return;
 225     }
 226
 227     if (!refNode) {
 228         ec = NOT_FOUND_ERR;
 229         return;
 230     }
 231
 232     if (refNode->document() != m_ownerDocument) {
 233         ec = WRONG_DOCUMENT_ERR;
 234         return;
 235     }
 236
 237     ec = 0;
 238     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
 239     if (ec)
 240         return;
 241
 242     m_end.set(refNode, offset, childNode);
 243
 244     // check if different root container
 245     Node* endRootContainer = m_end.container();
 246     while (endRootContainer->parentNode())
 247         endRootContainer = endRootContainer->parentNode();
 248     Node* startRootContainer = m_start.container();
 249     while (startRootContainer->parentNode())
 250         startRootContainer = startRootContainer->parentNode();
 251     if (startRootContainer != endRootContainer)
 252         collapse(false, ec);
 253     // check if new end before start
 254     if (compareBoundaryPoints(m_start, m_end) > 0)
 255         collapse(false, ec);
 256 }
 257
 258 void Range::collapse(bool toStart, ExceptionCode& ec)
 259 {
 260     if (!m_start.container()) {
 261         ec = INVALID_STATE_ERR;
 262         return;
 263     }
 264
 265     if (toStart)
 266         m_end = m_start;
 267     else
 268         m_start = m_end;
 269 }
 270
 271 bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
 272 {
 273     if (!m_start.container()) {
 274         ec = INVALID_STATE_ERR;
 275         return false;
 276     }
 277
 278     if (!refNode) {
 279         ec = HIERARCHY_REQUEST_ERR;
 280         return false;
 281     }
 282
 283     if (!refNode->attached()) {
 284         // Firefox doesn't throw an exception for this case; it returns false.
 285         return false;
 286     }
 287
 288     if (refNode->document() != m_ownerDocument) {
 289         ec = WRONG_DOCUMENT_ERR;
 290         return false;
 291     }
 292
 293     ec = 0;
 294     checkNodeWOffset(refNode, offset, ec);
 295     if (ec)
 296         return false;
 297
 298     return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset()) >= 0
 299         && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset()) <= 0;
 300 }
 301
 302 short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const
 303 {
 304     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
 305     // This method returns -1, 0 or 1 depending on if the point described by the
 306     // refNode node and an offset within the node is before, same as, or after the range respectively.
 307
 308     if (!m_start.container()) {
 309         ec = INVALID_STATE_ERR;
 310         return 0;
 311     }
 312
 313     if (!refNode) {
 314         ec = HIERARCHY_REQUEST_ERR;
 315         return 0;
 316     }
 317
 318     if (!refNode->attached() || refNode->document() != m_ownerDocument) {
 319         ec = WRONG_DOCUMENT_ERR;
 320         return 0;
 321     }
 322
 323     ec = 0;
 324     checkNodeWOffset(refNode, offset, ec);
 325     if (ec)
 326         return 0;
 327
 328     // compare to start, and point comes before
 329     if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset()) < 0)
 330         return -1;
 331
 332     // compare to end, and point comes after
 333     if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset()) > 0)
 334         return 1;
 335
 336     // point is in the middle of this range, or on the boundary points
 337     return 0;
 338 }
 339
 340 Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const
 341 {
 342     // http://developer.mozilla.org/en/docs/DOM:range.compareNode
 343     // This method returns 0, 1, 2, or 3 based on if the node is before, after,
 344     // before and after(surrounds), or inside the range, respectively
 345
 346     if (!refNode) {
 347         ec = NOT_FOUND_ERR;
 348         return NODE_BEFORE;
 349     }
 350
 351     if (!m_start.container() && refNode->attached()) {
 352         ec = INVALID_STATE_ERR;
 353         return NODE_BEFORE;
 354     }
 355
 356     if (m_start.container() && !refNode->attached()) {
 357         // Firefox doesn't throw an exception for this case; it returns 0.
 358         return NODE_BEFORE;
 359     }
 360
 361     if (refNode->document() != m_ownerDocument) {
 362         // Firefox doesn't throw an exception for this case; it returns 0.
 363         return NODE_BEFORE;
 364     }
 365
 366     Node* parentNode = refNode->parentNode();
 367     int nodeIndex = refNode->nodeIndex();
 368
 369     if (!parentNode) {
 370         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 371         // but we throw to match firefox behavior
 372         ec = NOT_FOUND_ERR;
 373         return NODE_BEFORE;
 374     }
 375
 376     if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
 377         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
 378             return NODE_BEFORE_AND_AFTER;
 379         return NODE_BEFORE; // ends before or in the range
 380     } else { // starts at or after the range start
 381         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
 382             return NODE_AFTER;
 383         return NODE_INSIDE; // ends inside the range
 384     }
 385 }
 386
 387 short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
 388 {
 389     if (!m_start.container()) {
 390         ec = INVALID_STATE_ERR;
 391         return 0;
 392     }
 393
 394     if (!sourceRange) {
 395         ec = NOT_FOUND_ERR;
 396         return 0;
 397     }
 398
 399     ec = 0;
 400     Node* thisCont = commonAncestorContainer(ec);
 401     if (ec)
 402         return 0;
 403     Node* sourceCont = sourceRange->commonAncestorContainer(ec);
 404     if (ec)
 405         return 0;
 406
 407     if (thisCont->document() != sourceCont->document()) {
 408         ec = WRONG_DOCUMENT_ERR;
 409         return 0;
 410     }
 411
 412     Node* thisTop = thisCont;
 413     Node* sourceTop = sourceCont;
 414     while (thisTop->parentNode())
 415         thisTop = thisTop->parentNode();
 416     while (sourceTop->parentNode())
 417         sourceTop = sourceTop->parentNode();
 418     if (thisTop != sourceTop) { // in different DocumentFragments
 419         ec = WRONG_DOCUMENT_ERR;
 420         return 0;
 421     }
 422
 423     switch (how) {
 424         case START_TO_START:
 425             return compareBoundaryPoints(m_start, sourceRange->m_start);
 426         case START_TO_END:
 427             return compareBoundaryPoints(m_end, sourceRange->m_start);
 428         case END_TO_END:
 429             return compareBoundaryPoints(m_end, sourceRange->m_end);
 430         case END_TO_START:
 431             return compareBoundaryPoints(m_start, sourceRange->m_end);
 432     }
 433
 434     ec = SYNTAX_ERR;
 435     return 0;
 436 }
 437
 438 short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB)
 439 {
 440     ASSERT(containerA);
 441     ASSERT(containerB);
 442
 443     if (!containerA)
 444         return -1;
 445     if (!containerB)
 446         return 1;
 447
 448     // see DOM2 traversal & range section 2.5
 449
 450     // case 1: both points have the same container
 451     if (containerA == containerB) {
 452         if (offsetA == offsetB)
 453             return 0;           // A is equal to B
 454         if (offsetA < offsetB)
 455             return -1;          // A is before B
 456         else
 457             return 1;           // A is after B
 458     }
 459
 460     // case 2: node C (container B or an ancestor) is a child node of A
 461     Node* c = containerB;
 462     while (c && c->parentNode() != containerA)
 463         c = c->parentNode();
 464     if (c) {
 465         int offsetC = 0;
 466         Node* n = containerA->firstChild();
 467         while (n != c && offsetC < offsetA) {
 468             offsetC++;
 469             n = n->nextSibling();
 470         }
 471
 472         if (offsetA <= offsetC)
 473             return -1;              // A is before B
 474         else
 475             return 1;               // A is after B
 476     }
 477
 478     // case 3: node C (container A or an ancestor) is a child node of B
 479     c = containerA;
 480     while (c && c->parentNode() != containerB)
 481         c = c->parentNode();
 482     if (c) {
 483         int offsetC = 0;
 484         Node* n = containerB->firstChild();
 485         while (n != c && offsetC < offsetB) {
 486             offsetC++;
 487             n = n->nextSibling();
 488         }
 489
 490         if (offsetC < offsetB)
 491             return -1;              // A is before B
 492         else
 493             return 1;               // A is after B
 494     }
 495
 496     // case 4: containers A & B are siblings, or children of siblings
 497     // ### we need to do a traversal here instead
 498     Node* commonAncestor = commonAncestorContainer(containerA, containerB);
 499     if (!commonAncestor)
 500         return 0;
 501     Node* childA = containerA;
 502     while (childA && childA->parentNode() != commonAncestor)
 503         childA = childA->parentNode();
 504     if (!childA)
 505         childA = commonAncestor;
 506     Node* childB = containerB;
 507     while (childB && childB->parentNode() != commonAncestor)
 508         childB = childB->parentNode();
 509     if (!childB)
 510         childB = commonAncestor;
 511
 512     if (childA == childB)
 513         return 0; // A is equal to B
 514
 515     Node* n = commonAncestor->firstChild();
 516     while (n) {
 517         if (n == childA)
 518             return -1; // A is before B
 519         if (n == childB)
 520             return 1; // A is after B
 521         n = n->nextSibling();
 522     }
 523
 524     // Should never reach this point.
 525     ASSERT_NOT_REACHED();
 526     return 0;
 527 }
 528
 529 short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB)
 530 {
 531     return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset());
 532 }
 533
 534 bool Range::boundaryPointsValid() const
 535 {
 536     return m_start.container() && compareBoundaryPoints(m_start, m_end) <= 0;
 537 }
 538
 539 void Range::deleteContents(ExceptionCode& ec)
 540 {
 541     checkDeleteExtract(ec);
 542     if (ec)
 543         return;
 544
 545     processContents(DELETE_CONTENTS, ec);
 546 }
 547
 548 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
 549 {
 550     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
 551     // Returns a bool if the node intersects the range.
 552
 553     if (!refNode) {
 554         ec = NOT_FOUND_ERR;
 555         return false;
 556     }
 557
 558     if ((!m_start.container() && refNode->attached())
 559             || (m_start.container() && !refNode->attached())
 560             || refNode->document() != m_ownerDocument) {
 561         // Firefox doesn't throw an exception for these cases; it returns false.
 562         return false;
 563     }
 564
 565     Node* parentNode = refNode->parentNode();
 566     int nodeIndex = refNode->nodeIndex();
 567
 568     if (!parentNode) {
 569         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 570         // but we throw to match firefox behavior
 571         ec = NOT_FOUND_ERR;
 572         return false;
 573     }
 574
 575     if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
 576         comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
 577         return false;
 578     } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
 579                comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
 580         return false;
 581     }
 582
 583     return true; // all other cases
 584 }
 585
 586 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
 587 {
 588     // FIXME: To work properly with mutation events, we will have to take into account
 589     // situations where the tree is being transformed while we work on it - ugh!
 590
 591     RefPtr<DocumentFragment> fragment;
 592     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 593         fragment = DocumentFragment::create(m_ownerDocument.get());
 594
 595     ec = 0;
 596     if (collapsed(ec))
 597         return fragment.release();
 598     if (ec)
 599         return 0;
 600
 601     Node* commonRoot = commonAncestorContainer(ec);
 602     if (ec)
 603         return 0;
 604     ASSERT(commonRoot);
 605
 606     // what is the highest node that partially selects the start of the range?
 607     Node* partialStart = 0;
 608     if (m_start.container() != commonRoot) {
 609         partialStart = m_start.container();
 610         while (partialStart->parentNode() != commonRoot)
 611             partialStart = partialStart->parentNode();
 612     }
 613
 614     // what is the highest node that partially selects the end of the range?
 615     Node* partialEnd = 0;
 616     if (m_end.container() != commonRoot) {
 617         partialEnd = m_end.container();
 618         while (partialEnd->parentNode() != commonRoot)
 619             partialEnd = partialEnd->parentNode();
 620     }
 621
 622     // Simple case: the start and end containers are the same. We just grab
 623     // everything >= start offset and < end offset
 624     if (m_start.container() == m_end.container()) {
 625         Node::NodeType startNodeType = m_start.container()->nodeType();
 626         if (startNodeType == Node::TEXT_NODE || startNodeType == Node::CDATA_SECTION_NODE || startNodeType == Node::COMMENT_NODE) {
 627             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 628                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_start.container()->cloneNode(true));
 629                 c->deleteData(m_end.offset(), c->length() - m_end.offset(), ec);
 630                 c->deleteData(0, m_start.offset(), ec);
 631                 fragment->appendChild(c.release(), ec);
 632             }
 633             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 634                 static_cast<CharacterData*>(m_start.container())->deleteData(m_start.offset(), m_end.offset() - m_start.offset(), ec);
 635         } else if (startNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
 636             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 637                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_start.container()->cloneNode(true));
 638                 c->setData(c->data().substring(m_start.offset(), m_end.offset() - m_start.offset()), ec);
 639                 fragment->appendChild(c.release(), ec);
 640             }
 641             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 642                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_start.container());
 643                 String data(pi->data());
 644                 data.remove(m_start.offset(), m_end.offset() - m_start.offset());
 645                 pi->setData(data, ec);
 646             }
 647         } else {
 648             Node* n = m_start.container()->firstChild();
 649             int i;
 650             for (i = 0; n && i < m_start.offset(); i++) // skip until start offset
 651                 n = n->nextSibling();
 652             int endOffset = m_end.offset();
 653             while (n && i < endOffset) { // delete until end offset
 654                 Node* next = n->nextSibling();
 655                 if (action == EXTRACT_CONTENTS)
 656                     fragment->appendChild(n, ec); // will remove n from its parent
 657                 else if (action == CLONE_CONTENTS)
 658                     fragment->appendChild(n->cloneNode(true), ec);
 659                 else
 660                     m_start.container()->removeChild(n, ec);
 661                 n = next;
 662                 i++;
 663             }
 664         }
 665         return fragment.release();
 666     }
 667
 668     // Complex case: Start and end containers are different.
 669     // There are three possiblities here:
 670     // 1. Start container == commonRoot (End container must be a descendant)
 671     // 2. End container == commonRoot (Start container must be a descendant)
 672     // 3. Neither is commonRoot, they are both descendants
 673     //
 674     // In case 3, we grab everything after the start (up until a direct child
 675     // of commonRoot) into leftContents, and everything before the end (up until
 676     // a direct child of commonRoot) into rightContents. Then we process all
 677     // commonRoot children between leftContents and rightContents
 678     //
 679     // In case 1 or 2, we skip either processing of leftContents or rightContents,
 680     // in which case the last lot of nodes either goes from the first or last
 681     // child of commonRoot.
 682     //
 683     // These are deleted, cloned, or extracted (i.e. both) depending on action.
 684
 685     RefPtr<Node> leftContents;
 686     if (m_start.container() != commonRoot) {
 687         // process the left-hand side of the range, up until the last ancestor of
 688         // start container before commonRoot
 689         Node::NodeType startNodeType = m_start.container()->nodeType();
 690         if (startNodeType == Node::TEXT_NODE || startNodeType == Node::CDATA_SECTION_NODE || startNodeType == Node::COMMENT_NODE) {
 691             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 692                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_start.container()->cloneNode(true));
 693                 c->deleteData(0, m_start.offset(), ec);
 694                 leftContents = c.release();
 695             }
 696             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 697                 static_cast<CharacterData*>(m_start.container())->deleteData(
 698                     m_start.offset(), static_cast<CharacterData*>(m_start.container())->length() - m_start.offset(), ec);
 699         } else if (startNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
 700             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 701                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_start.container()->cloneNode(true));
 702                 c->setData(c->data().substring(m_start.offset()), ec);
 703                 leftContents = c.release();
 704             }
 705             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 706                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_start.container());
 707                 String data(pi->data());
 708                 pi->setData(data.left(m_start.offset()), ec);
 709             }
 710         } else {
 711             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 712                 leftContents = m_start.container()->cloneNode(false);
 713             Node* n = m_start.container()->firstChild();
 714             for (int i = 0; n && i < m_start.offset(); i++) // skip until start offset
 715                 n = n->nextSibling();
 716             while (n) { // process until end
 717                 Node* next = n->nextSibling();
 718                 if (action == EXTRACT_CONTENTS)
 719                     leftContents->appendChild(n, ec); // will remove n from start container
 720                 else if (action == CLONE_CONTENTS)
 721                     leftContents->appendChild(n->cloneNode(true), ec);
 722                 else
 723                     m_start.container()->removeChild(n, ec);
 724                 n = next;
 725             }
 726         }
 727
 728         Node* leftParent = m_start.container()->parentNode();
 729         Node* n = m_start.container()->nextSibling();
 730         for (; leftParent != commonRoot; leftParent = leftParent->parentNode()) {
 731             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 732                 RefPtr<Node> leftContentsParent = leftParent->cloneNode(false);
 733                 leftContentsParent->appendChild(leftContents, ec);
 734                 leftContents = leftContentsParent;
 735             }
 736
 737             Node* next;
 738             for (; n; n = next) {
 739                 next = n->nextSibling();
 740                 if (action == EXTRACT_CONTENTS)
 741                     leftContents->appendChild(n, ec); // will remove n from leftParent
 742                 else if (action == CLONE_CONTENTS)
 743                     leftContents->appendChild(n->cloneNode(true), ec);
 744                 else
 745                     leftParent->removeChild(n, ec);
 746             }
 747             n = leftParent->nextSibling();
 748         }
 749     }
 750
 751     RefPtr<Node> rightContents;
 752     if (m_end.container() != commonRoot) {
 753         // delete the right-hand side of the range, up until the last ancestor of
 754         // end container before commonRoot
 755         Node::NodeType endNodeType = m_end.container()->nodeType();
 756         if (endNodeType == Node::TEXT_NODE || endNodeType == Node::CDATA_SECTION_NODE || endNodeType == Node::COMMENT_NODE) {
 757             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 758                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_end.container()->cloneNode(true));
 759                 c->deleteData(m_end.offset(), static_cast<CharacterData*>(m_end.container())->length() - m_end.offset(), ec);
 760                 rightContents = c;
 761             }
 762             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 763                 static_cast<CharacterData*>(m_end.container())->deleteData(0, m_end.offset(), ec);
 764         } else if (endNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
 765             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 766                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_end.container()->cloneNode(true));
 767                 c->setData(c->data().left(m_end.offset()), ec);
 768                 rightContents = c.release();
 769             }
 770             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 771                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_end.container());
 772                 pi->setData(pi->data().substring(m_end.offset()), ec);
 773             }
 774         } else {
 775             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 776                 rightContents = m_end.container()->cloneNode(false);
 777             Node* n = m_end.container()->firstChild();
 778             if (n && m_end.offset()) {
 779                 for (int i = 0; i + 1 < m_end.offset(); i++) { // skip to end.offset()
 780                     Node* next = n->nextSibling();
 781                     if (!next)
 782                         break;
 783                     n = next;
 784                 }
 785                 Node* prev;
 786                 for (; n; n = prev) {
 787                     prev = n->previousSibling();
 788                     if (action == EXTRACT_CONTENTS)
 789                         rightContents->insertBefore(n, rightContents->firstChild(), ec); // will remove n from its parent
 790                     else if (action == CLONE_CONTENTS)
 791                         rightContents->insertBefore(n->cloneNode(true), rightContents->firstChild(), ec);
 792                     else
 793                         m_end.container()->removeChild(n, ec);
 794                 }
 795             }
 796         }
 797
 798         Node* rightParent = m_end.container()->parentNode();
 799         Node* n = m_end.container()->previousSibling();
 800         for (; rightParent != commonRoot; rightParent = rightParent->parentNode()) {
 801             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 802                 RefPtr<Node> rightContentsParent = rightParent->cloneNode(false);
 803                 rightContentsParent->appendChild(rightContents, ec);
 804                 rightContents = rightContentsParent;
 805             }
 806             Node* prev;
 807             for (; n; n = prev) {
 808                 prev = n->previousSibling();
 809                 if (action == EXTRACT_CONTENTS)
 810                     rightContents->insertBefore(n, rightContents->firstChild(), ec); // will remove n from its parent
 811                 else if (action == CLONE_CONTENTS)
 812                     rightContents->insertBefore(n->cloneNode(true), rightContents->firstChild(), ec);
 813                 else
 814                     rightParent->removeChild(n, ec);
 815             }
 816             n = rightParent->previousSibling();
 817         }
 818     }
 819
 820     // delete all children of commonRoot between the start and end container
 821
 822     Node* processStart; // child of commonRoot
 823     if (m_start.container() == commonRoot) {
 824         processStart = m_start.container()->firstChild();
 825         for (int i = 0; i < m_start.offset(); i++)
 826             processStart = processStart->nextSibling();
 827     } else {
 828         processStart = m_start.container();
 829         while (processStart->parentNode() != commonRoot)
 830             processStart = processStart->parentNode();
 831         processStart = processStart->nextSibling();
 832     }
 833     Node* processEnd; // child of commonRoot
 834     if (m_end.container() == commonRoot) {
 835         processEnd = m_end.container()->firstChild();
 836         for (int i = 0; i < m_end.offset(); i++)
 837             processEnd = processEnd->nextSibling();
 838     } else {
 839         processEnd = m_end.container();
 840         while (processEnd->parentNode() != commonRoot)
 841             processEnd = processEnd->parentNode();
 842     }
 843
 844     // Collapse the range, making sure that the result is not within a node that was partially selected.
 845     if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 846         if (partialStart)
 847             setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
 848         else if (partialEnd)
 849             setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
 850         if (ec)
 851             return 0;
 852         m_end = m_start;
 853     }
 854
 855     // Now add leftContents, stuff in between, and rightContents to the fragment
 856     // (or just delete the stuff in between)
 857
 858     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)
 859         fragment->appendChild(leftContents, ec);
 860
 861     Node* next;
 862     Node* n;
 863     if (processStart) {
 864         for (n = processStart; n && n != processEnd; n = next) {
 865             next = n->nextSibling();
 866             if (action == EXTRACT_CONTENTS)
 867                 fragment->appendChild(n, ec); // will remove from commonRoot
 868             else if (action == CLONE_CONTENTS)
 869                 fragment->appendChild(n->cloneNode(true), ec);
 870             else
 871                 commonRoot->removeChild(n, ec);
 872         }
 873     }
 874
 875     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)
 876         fragment->appendChild(rightContents, ec);
 877
 878     return fragment.release();
 879 }
 880
 881 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
 882 {
 883     checkDeleteExtract(ec);
 884     if (ec)
 885         return 0;
 886
 887     return processContents(EXTRACT_CONTENTS, ec);
 888 }
 889
 890 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
 891 {
 892     if (!m_start.container()) {
 893         ec = INVALID_STATE_ERR;
 894         return 0;
 895     }
 896
 897     return processContents(CLONE_CONTENTS, ec);
 898 }
 899
 900 void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
 901 {
 902     RefPtr<Node> newNode = prpNewNode;
 903
 904     ec = 0;
 905
 906     if (!m_start.container()) {
 907         ec = INVALID_STATE_ERR;
 908         return;
 909     }
 910
 911     if (!newNode) {
 912         ec = NOT_FOUND_ERR;
 913         return;
 914     }
 915
 916     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
 917     // the Range is read-only.
 918     if (containedByReadOnly()) {
 919         ec = NO_MODIFICATION_ALLOWED_ERR;
 920         return;
 921     }
 922
 923     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
 924     // not created from the same document.
 925     if (newNode->document() != m_start.container()->document()) {
 926         ec = WRONG_DOCUMENT_ERR;
 927         return;
 928     }
 929
 930     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
 931     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
 932
 933     // an extra one here - if a text node is going to split, it must have a parent to insert into
 934     bool startIsText = m_start.container()->isTextNode();
 935     if (startIsText && !m_start.container()->parentNode()) {
 936         ec = HIERARCHY_REQUEST_ERR;
 937         return;
 938     }
 939
 940     // In the case where the container is a text node, we check against the container's parent, because
 941     // text nodes get split up upon insertion.
 942     Node* checkAgainst;
 943     if (startIsText)
 944         checkAgainst = m_start.container()->parentNode();
 945     else
 946         checkAgainst = m_start.container();
 947
 948     Node::NodeType newNodeType = newNode->nodeType();
 949     int numNewChildren;
 950     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) {
 951         // check each child node, not the DocumentFragment itself
 952         numNewChildren = 0;
 953         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
 954             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
 955                 ec = HIERARCHY_REQUEST_ERR;
 956                 return;
 957             }
 958             ++numNewChildren;
 959         }
 960     } else {
 961         numNewChildren = 1;
 962         if (!checkAgainst->childTypeAllowed(newNodeType)) {
 963             ec = HIERARCHY_REQUEST_ERR;
 964             return;
 965         }
 966     }
 967
 968     for (Node* n = m_start.container(); n; n = n->parentNode()) {
 969         if (n == newNode) {
 970             ec = HIERARCHY_REQUEST_ERR;
 971             return;
 972         }
 973     }
 974
 975     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, or Document node.
 976     if (newNodeType == Node::ATTRIBUTE_NODE || newNodeType == Node::ENTITY_NODE
 977             || newNodeType == Node::NOTATION_NODE || newNodeType == Node::DOCUMENT_NODE) {
 978         ec = RangeException::INVALID_NODE_TYPE_ERR;
 979         return;
 980     }
 981
 982     bool collapsed = m_start == m_end;
 983     if (startIsText) {
 984         RefPtr<Text> newText = static_cast<Text*>(m_start.container())->splitText(m_start.offset(), ec);
 985         if (ec)
 986             return;
 987         m_start.container()->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
 988         if (ec)
 989             return;
 990
 991         // This special case doesn't seem to match the DOM specification, but it's currently required
 992         // to pass Acid3. We might later decide to remove this.
 993         if (collapsed)
 994             m_end.setToBeforeChild(newText.get());
 995     } else {
 996         RefPtr<Node> lastChild;
 997         if (collapsed)
 998             lastChild = (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) ? newNode->lastChild() : newNode;
 999
1000         int startOffset = m_start.offset();
1001         m_start.container()->insertBefore(newNode.release(), m_start.container()->childNode(startOffset), ec);
1002         if (ec)
1003             return;
1004
1005         // This special case doesn't seem to match the DOM specification, but it's currently required
1006         // to pass Acid3. We might later decide to remove this.
1007         if (collapsed)
1008             m_end.set(m_start.container(), startOffset + numNewChildren, lastChild.get());
1009     }
1010 }
1011
1012 String Range::toString(ExceptionCode& ec) const
1013 {
1014     if (!m_start.container()) {
1015         ec = INVALID_STATE_ERR;
1016         return String();
1017     }
1018
1019     Vector<UChar> result;
1020
1021     Node* pastLast = pastLastNode();
1022     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1023         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1024             String data = static_cast<CharacterData*>(n)->data();
1025             int length = data.length();
1026             int start = (n == m_start.container()) ? min(max(0, m_start.offset()), length) : 0;
1027             int end = (n == m_end.container()) ? min(max(start, m_end.offset()), length) : length;
1028             result.append(data.characters() + start, end - start);
1029         }
1030     }
1031
1032     return String::adopt(result);
1033 }
1034
1035 String Range::toHTML() const
1036 {
1037     return createMarkup(this);
1038 }
1039
1040 String Range::text() const
1041 {
1042     if (!m_start.container())
1043         return String();
1044
1045     // We need to update layout, since plainText uses line boxes in the render tree.
1046     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1047     m_start.container()->document()->updateLayout();
1048
1049     return plainText(this);
1050 }
1051
1052 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec) const
1053 {
1054     if (!m_start.container()) {
1055         ec = INVALID_STATE_ERR;
1056         return 0;
1057     }
1058
1059     Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1060     if (!element || !element->isHTMLElement()) {
1061         ec = NOT_SUPPORTED_ERR;
1062         return 0;
1063     }
1064
1065     RefPtr<DocumentFragment> fragment = static_cast<HTMLElement*>(element)->createContextualFragment(markup);
1066     if (!fragment) {
1067         ec = NOT_SUPPORTED_ERR;
1068         return 0;
1069     }
1070
1071     return fragment.release();
1072 }
1073
1074
1075 void Range::detach(ExceptionCode& ec)
1076 {
1077     // Check first to see if we've already detached:
1078     if (!m_start.container()) {
1079         ec = INVALID_STATE_ERR;
1080         return;
1081     }
1082
1083     m_ownerDocument->detachRange(this);
1084
1085     m_start.clear();
1086     m_end.clear();
1087 }
1088
1089 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1090 {
1091     switch (n->nodeType()) {
1092         case Node::DOCUMENT_TYPE_NODE:
1093         case Node::ENTITY_NODE:
1094         case Node::NOTATION_NODE:
1095             ec = RangeException::INVALID_NODE_TYPE_ERR;
1096             return 0;
1097         case Node::CDATA_SECTION_NODE:
1098         case Node::COMMENT_NODE:
1099         case Node::TEXT_NODE:
1100             if (static_cast<unsigned>(offset) > static_cast<CharacterData*>(n)->length())
1101                 ec = INDEX_SIZE_ERR;
1102             return 0;
1103         case Node::PROCESSING_INSTRUCTION_NODE:
1104             if (static_cast<unsigned>(offset) > static_cast<ProcessingInstruction*>(n)->data().length())
1105                 ec = INDEX_SIZE_ERR;
1106             return 0;
1107         case Node::ATTRIBUTE_NODE:
1108         case Node::DOCUMENT_FRAGMENT_NODE:
1109         case Node::DOCUMENT_NODE:
1110         case Node::ELEMENT_NODE:
1111         case Node::ENTITY_REFERENCE_NODE:
1112         case Node::XPATH_NAMESPACE_NODE: {
1113             if (!offset)
1114                 return 0;
1115             Node* childBefore = n->childNode(offset - 1);
1116             if (!childBefore)
1117                 ec = INDEX_SIZE_ERR;
1118             return childBefore;
1119         }
1120     }
1121     ASSERT_NOT_REACHED();
1122     return 0;
1123 }
1124
1125 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1126 {
1127     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1128     // Attr, Document or DocumentFragment node or part of a shadow DOM tree
1129     // or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation node.
1130
1131     switch (n->nodeType()) {
1132         case Node::ATTRIBUTE_NODE:
1133         case Node::DOCUMENT_FRAGMENT_NODE:
1134         case Node::DOCUMENT_NODE:
1135         case Node::ENTITY_NODE:
1136         case Node::NOTATION_NODE:
1137             ec = RangeException::INVALID_NODE_TYPE_ERR;
1138             return;
1139         case Node::CDATA_SECTION_NODE:
1140         case Node::COMMENT_NODE:
1141         case Node::DOCUMENT_TYPE_NODE:
1142         case Node::ELEMENT_NODE:
1143         case Node::ENTITY_REFERENCE_NODE:
1144         case Node::PROCESSING_INSTRUCTION_NODE:
1145         case Node::TEXT_NODE:
1146         case Node::XPATH_NAMESPACE_NODE:
1147             break;
1148     }
1149
1150     Node* root = n;
1151     while (Node* parent = root->parentNode())
1152         root = parent;
1153
1154     switch (root->nodeType()) {
1155         case Node::ATTRIBUTE_NODE:
1156         case Node::DOCUMENT_NODE:
1157         case Node::DOCUMENT_FRAGMENT_NODE:
1158             break;
1159         case Node::CDATA_SECTION_NODE:
1160         case Node::COMMENT_NODE:
1161         case Node::DOCUMENT_TYPE_NODE:
1162         case Node::ELEMENT_NODE:
1163         case Node::ENTITY_NODE:
1164         case Node::ENTITY_REFERENCE_NODE:
1165         case Node::NOTATION_NODE:
1166         case Node::PROCESSING_INSTRUCTION_NODE:
1167         case Node::TEXT_NODE:
1168         case Node::XPATH_NAMESPACE_NODE:
1169             if (root->isShadowNode())
1170                 break;
1171             ec = RangeException::INVALID_NODE_TYPE_ERR;
1172             return;
1173     }
1174 }
1175
1176 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1177 {
1178     if (!m_start.container()) {
1179         ec = INVALID_STATE_ERR;
1180         return 0;
1181     }
1182
1183     return Range::create(m_ownerDocument, m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1184 }
1185
1186 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1187 {
1188     if (!m_start.container()) {
1189         ec = INVALID_STATE_ERR;
1190         return;
1191     }
1192
1193     if (!refNode) {
1194         ec = NOT_FOUND_ERR;
1195         return;
1196     }
1197
1198     if (refNode->document() != m_ownerDocument) {
1199         ec = WRONG_DOCUMENT_ERR;
1200         return;
1201     }
1202
1203     ec = 0;
1204     checkNodeBA(refNode, ec);
1205     if (ec)
1206         return;
1207
1208     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1209 }
1210
1211 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1212 {
1213     if (!m_start.container()) {
1214         ec = INVALID_STATE_ERR;
1215         return;
1216     }
1217
1218     if (!refNode) {
1219         ec = NOT_FOUND_ERR;
1220         return;
1221     }
1222
1223     if (refNode->document() != m_ownerDocument) {
1224         ec = WRONG_DOCUMENT_ERR;
1225         return;
1226     }
1227
1228     ec = 0;
1229     checkNodeBA(refNode, ec);
1230     if (ec)
1231         return;
1232
1233     setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1234 }
1235
1236 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1237 {
1238     if (!m_start.container()) {
1239         ec = INVALID_STATE_ERR;
1240         return;
1241     }
1242
1243     if (!refNode) {
1244         ec = NOT_FOUND_ERR;
1245         return;
1246     }
1247
1248     if (refNode->document() != m_ownerDocument) {
1249         ec = WRONG_DOCUMENT_ERR;
1250         return;
1251     }
1252
1253     ec = 0;
1254     checkNodeBA(refNode, ec);
1255     if (ec)
1256         return;
1257
1258     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1259
1260 }
1261
1262 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1263 {
1264     if (!m_start.container()) {
1265         ec = INVALID_STATE_ERR;
1266         return;
1267     }
1268
1269     if (!refNode) {
1270         ec = NOT_FOUND_ERR;
1271         return;
1272     }
1273
1274     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1275     // DocumentType node or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation
1276     // node.
1277     for (Node* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1278         switch (anc->nodeType()) {
1279             case Node::ATTRIBUTE_NODE:
1280             case Node::CDATA_SECTION_NODE:
1281             case Node::COMMENT_NODE:
1282             case Node::DOCUMENT_FRAGMENT_NODE:
1283             case Node::DOCUMENT_NODE:
1284             case Node::ELEMENT_NODE:
1285             case Node::ENTITY_REFERENCE_NODE:
1286             case Node::PROCESSING_INSTRUCTION_NODE:
1287             case Node::TEXT_NODE:
1288             case Node::XPATH_NAMESPACE_NODE:
1289                 break;
1290             case Node::DOCUMENT_TYPE_NODE:
1291             case Node::ENTITY_NODE:
1292             case Node::NOTATION_NODE:
1293                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1294                 return;
1295         }
1296     }
1297
1298     switch (refNode->nodeType()) {
1299         case Node::CDATA_SECTION_NODE:
1300         case Node::COMMENT_NODE:
1301         case Node::DOCUMENT_TYPE_NODE:
1302         case Node::ELEMENT_NODE:
1303         case Node::ENTITY_REFERENCE_NODE:
1304         case Node::PROCESSING_INSTRUCTION_NODE:
1305         case Node::TEXT_NODE:
1306         case Node::XPATH_NAMESPACE_NODE:
1307             break;
1308         case Node::ATTRIBUTE_NODE:
1309         case Node::DOCUMENT_FRAGMENT_NODE:
1310         case Node::DOCUMENT_NODE:
1311         case Node::ENTITY_NODE:
1312         case Node::NOTATION_NODE:
1313             ec = RangeException::INVALID_NODE_TYPE_ERR;
1314             return;
1315     }
1316
1317     ec = 0;
1318     setStartBefore(refNode, ec);
1319     if (ec)
1320         return;
1321     setEndAfter(refNode, ec);
1322 }
1323
1324 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1325 {
1326     if (!m_start.container()) {
1327         ec = INVALID_STATE_ERR;
1328         return;
1329     }
1330
1331     if (!refNode) {
1332         ec = NOT_FOUND_ERR;
1333         return;
1334     }
1335
1336     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1337     // or DocumentType node.
1338     for (Node* n = refNode; n; n = n->parentNode()) {
1339         switch (n->nodeType()) {
1340             case Node::ATTRIBUTE_NODE:
1341             case Node::CDATA_SECTION_NODE:
1342             case Node::COMMENT_NODE:
1343             case Node::DOCUMENT_FRAGMENT_NODE:
1344             case Node::DOCUMENT_NODE:
1345             case Node::ELEMENT_NODE:
1346             case Node::ENTITY_REFERENCE_NODE:
1347             case Node::PROCESSING_INSTRUCTION_NODE:
1348             case Node::TEXT_NODE:
1349             case Node::XPATH_NAMESPACE_NODE:
1350                 break;
1351             case Node::DOCUMENT_TYPE_NODE:
1352             case Node::ENTITY_NODE:
1353             case Node::NOTATION_NODE:
1354                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1355                 return;
1356         }
1357     }
1358
1359     m_start.setToStartOfNode(refNode);
1360     m_end.setToEndOfNode(refNode);
1361 }
1362
1363 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1364 {
1365     RefPtr<Node> newParent = passNewParent;
1366
1367     if (!m_start.container()) {
1368         ec = INVALID_STATE_ERR;
1369         return;
1370     }
1371
1372     if (!newParent) {
1373         ec = NOT_FOUND_ERR;
1374         return;
1375     }
1376
1377     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1378     // Document, or DocumentFragment node.
1379     switch (newParent->nodeType()) {
1380         case Node::ATTRIBUTE_NODE:
1381         case Node::DOCUMENT_FRAGMENT_NODE:
1382         case Node::DOCUMENT_NODE:
1383         case Node::DOCUMENT_TYPE_NODE:
1384         case Node::ENTITY_NODE:
1385         case Node::NOTATION_NODE:
1386             ec = RangeException::INVALID_NODE_TYPE_ERR;
1387             return;
1388         case Node::CDATA_SECTION_NODE:
1389         case Node::COMMENT_NODE:
1390         case Node::ELEMENT_NODE:
1391         case Node::ENTITY_REFERENCE_NODE:
1392         case Node::PROCESSING_INSTRUCTION_NODE:
1393         case Node::TEXT_NODE:
1394         case Node::XPATH_NAMESPACE_NODE:
1395             break;
1396     }
1397
1398     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1399     // the Range is read-only.
1400     if (containedByReadOnly()) {
1401         ec = NO_MODIFICATION_ALLOWED_ERR;
1402         return;
1403     }
1404
1405     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
1406     // not created from the same document.
1407     if (newParent->document() != m_start.container()->document()) {
1408         ec = WRONG_DOCUMENT_ERR;
1409         return;
1410     }
1411
1412     // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1413     Node* parentOfNewParent = m_start.container();
1414
1415     // If m_start.container() is a character data node, it will be split and it will be its parent that will
1416     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1417     // although this will fail below for another reason).
1418     if (parentOfNewParent->isCharacterDataNode())
1419         parentOfNewParent = parentOfNewParent->parentNode();
1420     if (!parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1421         ec = HIERARCHY_REQUEST_ERR;
1422         return;
1423     }
1424
1425     if (m_start.container() == newParent || m_start.container()->isDescendantOf(newParent.get())) {
1426         ec = HIERARCHY_REQUEST_ERR;
1427         return;
1428     }
1429
1430     // FIXME: Do we need a check if the node would end up with a child node of a type not
1431     // allowed by the type of node?
1432
1433     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1434     Node* startNonTextContainer = m_start.container();
1435     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1436         startNonTextContainer = startNonTextContainer->parentNode();
1437     Node* endNonTextContainer = m_end.container();
1438     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1439         endNonTextContainer = endNonTextContainer->parentNode();
1440     if (startNonTextContainer != endNonTextContainer) {
1441         ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1442         return;
1443     }
1444
1445     ec = 0;
1446     while (Node* n = newParent->firstChild()) {
1447         newParent->removeChild(n, ec);
1448         if (ec)
1449             return;
1450     }
1451     RefPtr<DocumentFragment> fragment = extractContents(ec);
1452     if (ec)
1453         return;
1454     insertNode(newParent, ec);
1455     if (ec)
1456         return;
1457     newParent->appendChild(fragment.release(), ec);
1458     if (ec)
1459         return;
1460     selectNode(newParent.get(), ec);
1461 }
1462
1463 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1464 {
1465     if (!m_start.container()) {
1466         ec = INVALID_STATE_ERR;
1467         return;
1468     }
1469
1470     if (!refNode) {
1471         ec = NOT_FOUND_ERR;
1472         return;
1473     }
1474
1475     if (refNode->document() != m_ownerDocument) {
1476         ec = WRONG_DOCUMENT_ERR;
1477         return;
1478     }
1479
1480     ec = 0;
1481     checkNodeBA(refNode, ec);
1482     if (ec)
1483         return;
1484
1485     setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1486 }
1487
1488 void Range::checkDeleteExtract(ExceptionCode& ec)
1489 {
1490     if (!m_start.container()) {
1491         ec = INVALID_STATE_ERR;
1492         return;
1493     }
1494
1495     ec = 0;
1496     if (!commonAncestorContainer(ec) || ec)
1497         return;
1498
1499     Node* pastLast = pastLastNode();
1500     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1501         if (n->isReadOnlyNode()) {
1502             ec = NO_MODIFICATION_ALLOWED_ERR;
1503             return;
1504         }
1505         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1506             ec = HIERARCHY_REQUEST_ERR;
1507             return;
1508         }
1509     }
1510
1511     if (containedByReadOnly()) {
1512         ec = NO_MODIFICATION_ALLOWED_ERR;
1513         return;
1514     }
1515 }
1516
1517 bool Range::containedByReadOnly() const
1518 {
1519     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1520         if (n->isReadOnlyNode())
1521             return true;
1522     }
1523     for (Node* n = m_end.container(); n; n = n->parentNode()) {
1524         if (n->isReadOnlyNode())
1525             return true;
1526     }
1527     return false;
1528 }
1529
1530 Node* Range::firstNode() const
1531 {
1532     if (!m_start.container())
1533         return 0;
1534     if (m_start.container()->offsetInCharacters())
1535         return m_start.container();
1536     if (Node* child = m_start.container()->childNode(m_start.offset()))
1537         return child;
1538     if (!m_start.offset())
1539         return m_start.container();
1540     return m_start.container()->traverseNextSibling();
1541 }
1542
1543 Position Range::editingStartPosition() const
1544 {
1545     // This function is used by range style computations to avoid bugs like:
1546     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1547     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up
1548     // with a spurious "mixed" style.
1549
1550     VisiblePosition visiblePosition(m_start.container(), m_start.offset(), VP_DEFAULT_AFFINITY);
1551     if (visiblePosition.isNull())
1552         return Position();
1553
1554     ExceptionCode ec = 0;
1555     // if the selection is a caret, just return the position, since the style
1556     // behind us is relevant
1557     if (collapsed(ec))
1558         return visiblePosition.deepEquivalent();
1559
1560     // if the selection starts just before a paragraph break, skip over it
1561     if (isEndOfParagraph(visiblePosition))
1562         return visiblePosition.next().deepEquivalent().downstream();
1563
1564     // otherwise, make sure to be at the start of the first selected node,
1565     // instead of possibly at the end of the last node before the selection
1566     return visiblePosition.deepEquivalent().downstream();
1567 }
1568
1569 Node* Range::shadowTreeRootNode() const
1570 {
1571     return startContainer() ? startContainer()->shadowTreeRootNode() : 0;
1572 }
1573
1574 Node* Range::pastLastNode() const
1575 {
1576     if (!m_start.container() || !m_end.container())
1577         return 0;
1578     if (m_end.container()->offsetInCharacters())
1579         return m_end.container()->traverseNextSibling();
1580     if (Node* child = m_end.container()->childNode(m_end.offset()))
1581         return child;
1582     return m_end.container()->traverseNextSibling();
1583 }
1584
1585 IntRect Range::boundingBox()
1586 {
1587     IntRect result;
1588     Vector<IntRect> rects;
1589     textRects(rects);
1590     const size_t n = rects.size();
1591     for (size_t i = 0; i < n; ++i)
1592         result.unite(rects[i]);
1593     return result;
1594 }
1595
1596 void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight)
1597 {
1598     Node* startContainer = m_start.container();
1599     Node* endContainer = m_end.container();
1600
1601     if (!startContainer || !endContainer)
1602         return;
1603
1604     Node* stopNode = pastLastNode();
1605     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1606         RenderObject* r = node->renderer();
1607         if (!r || !r->isText())
1608             continue;
1609         RenderText* renderText = toRenderText(r);
1610         int startOffset = node == startContainer ? m_start.offset() : 0;
1611         int endOffset = node == endContainer ? m_end.offset() : numeric_limits<int>::max();
1612         renderText->absoluteRectsForRange(rects, startOffset, endOffset, useSelectionHeight);
1613     }
1614 }
1615
1616 void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight)
1617 {
1618     Node* startContainer = m_start.container();
1619     Node* endContainer = m_end.container();
1620
1621     if (!startContainer || !endContainer)
1622         return;
1623
1624     Node* stopNode = pastLastNode();
1625     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1626         RenderObject* r = node->renderer();
1627         if (!r || !r->isText())
1628             continue;
1629         RenderText* renderText = toRenderText(r);
1630         int startOffset = node == startContainer ? m_start.offset() : 0;
1631         int endOffset = node == endContainer ? m_end.offset() : numeric_limits<int>::max();
1632         renderText->absoluteQuadsForRange(quads, startOffset, endOffset, useSelectionHeight);
1633     }
1634 }
1635
1636 #ifndef NDEBUG
1637 #define FormatBufferSize 1024
1638 void Range::formatForDebugger(char* buffer, unsigned length) const
1639 {
1640     String result;
1641     String s;
1642
1643     if (!m_start.container() || !m_end.container())
1644         result = "<empty>";
1645     else {
1646         char s[FormatBufferSize];
1647         result += "from offset ";
1648         result += String::number(m_start.offset());
1649         result += " of ";
1650         m_start.container()->formatForDebugger(s, FormatBufferSize);
1651         result += s;
1652         result += " to offset ";
1653         result += String::number(m_end.offset());
1654         result += " of ";
1655         m_end.container()->formatForDebugger(s, FormatBufferSize);
1656         result += s;
1657     }
1658
1659     strncpy(buffer, result.utf8().data(), length - 1);
1660 }
1661 #undef FormatBufferSize
1662 #endif
1663
1664 bool operator==(const Range& a, const Range& b)
1665 {
1666     if (&a == &b)
1667         return true;
1668     // Not strictly legal C++, but in practice this can happen, and this check works
1669     // fine with GCC to detect such cases and return false rather than crashing.
1670     if (!&a || !&b)
1671         return false;
1672     return a.startPosition() == b.startPosition() && a.endPosition() == b.endPosition();
1673 }
1674
1675 PassRefPtr<Range> rangeOfContents(Node* node)
1676 {
1677     ASSERT(node);
1678     RefPtr<Range> range = Range::create(node->document());
1679     int exception = 0;
1680     range->selectNodeContents(node, exception);
1681     return range.release();
1682 }
1683
1684 int Range::maxStartOffset() const
1685 {
1686     if (!m_start.container())
1687         return 0;
1688     if (!m_start.container()->offsetInCharacters())
1689         return m_start.container()->childNodeCount();
1690     return m_start.container()->maxCharacterOffset();
1691 }
1692
1693 int Range::maxEndOffset() const
1694 {
1695     if (!m_end.container())
1696         return 0;
1697     if (!m_end.container()->offsetInCharacters())
1698         return m_end.container()->childNodeCount();
1699     return m_end.container()->maxCharacterOffset();
1700 }
1701
1702 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode* container)
1703 {
1704     if (!boundary.childBefore())
1705         return;
1706     if (boundary.container() != container)
1707         return;
1708     boundary.invalidateOffset();
1709 }
1710
1711 void Range::nodeChildrenChanged(ContainerNode* container)
1712 {
1713     ASSERT(container);
1714     ASSERT(container->document() == m_ownerDocument);
1715     boundaryNodeChildrenChanged(m_start, container);
1716     boundaryNodeChildrenChanged(m_end, container);
1717 }
1718
1719 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
1720 {
1721     if (boundary.childBefore() == nodeToBeRemoved) {
1722         boundary.childBeforeWillBeRemoved();
1723         return;
1724     }
1725
1726     for (Node* n = boundary.container(); n; n = n->parentNode()) {
1727         if (n == nodeToBeRemoved) {
1728             boundary.setToBeforeChild(nodeToBeRemoved);
1729             return;
1730         }
1731     }
1732 }
1733
1734 void Range::nodeWillBeRemoved(Node* node)
1735 {
1736     ASSERT(node);
1737     ASSERT(node->document() == m_ownerDocument);
1738     ASSERT(node != m_ownerDocument);
1739     ASSERT(node->parentNode());
1740     boundaryNodeWillBeRemoved(m_start, node);
1741     boundaryNodeWillBeRemoved(m_end, node);
1742 }
1743
1744 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1745 {
1746     if (boundary.container() != text)
1747         return;
1748     unsigned boundaryOffset = boundary.offset();
1749     if (offset >= boundaryOffset)
1750         return;
1751     boundary.setOffset(boundaryOffset + length);
1752 }
1753
1754 void Range::textInserted(Node* text, unsigned offset, unsigned length)
1755 {
1756     ASSERT(text);
1757     ASSERT(text->document() == m_ownerDocument);
1758     boundaryTextInserted(m_start, text, offset, length);
1759     boundaryTextInserted(m_end, text, offset, length);
1760 }
1761
1762 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1763 {
1764     if (boundary.container() != text)
1765         return;
1766     unsigned boundaryOffset = boundary.offset();
1767     if (offset >= boundaryOffset)
1768         return;
1769     if (offset + length >= boundaryOffset)
1770         boundary.setOffset(offset);
1771     else
1772         boundary.setOffset(boundaryOffset - length);
1773 }
1774
1775 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
1776 {
1777     ASSERT(text);
1778     ASSERT(text->document() == m_ownerDocument);
1779     boundaryTextRemoved(m_start, text, offset, length);
1780     boundaryTextRemoved(m_end, text, offset, length);
1781 }
1782
1783 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
1784 {
1785     if (boundary.container() == oldNode.node())
1786         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
1787     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
1788         boundary.set(oldNode.node()->previousSibling(), offset, 0);
1789 }
1790
1791 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1792 {
1793     ASSERT(oldNode.node());
1794     ASSERT(oldNode.node()->document() == m_ownerDocument);
1795     ASSERT(oldNode.node()->parentNode());
1796     ASSERT(oldNode.node()->isTextNode());
1797     ASSERT(oldNode.node()->previousSibling());
1798     ASSERT(oldNode.node()->previousSibling()->isTextNode());
1799     boundaryTextNodesMerged(m_start, oldNode, offset);
1800     boundaryTextNodesMerged(m_end, oldNode, offset);
1801 }
1802
1803 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
1804 {
1805     if (boundary.container() != oldNode)
1806         return;
1807     unsigned boundaryOffset = boundary.offset();
1808     if (boundaryOffset <= oldNode->length())
1809         return;
1810     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
1811 }
1812
1813 void Range::textNodeSplit(Text* oldNode)
1814 {
1815     ASSERT(oldNode);
1816     ASSERT(oldNode->document() == m_ownerDocument);
1817     ASSERT(oldNode->parentNode());
1818     ASSERT(oldNode->isTextNode());
1819     ASSERT(oldNode->nextSibling());
1820     ASSERT(oldNode->nextSibling()->isTextNode());
1821     boundaryTextNodesSplit(m_start, oldNode);
1822     boundaryTextNodesSplit(m_end, oldNode);
1823 }
1824
1825 void Range::expand(const String& unit, ExceptionCode& ec)
1826 {
1827     VisiblePosition start(startPosition());
1828     VisiblePosition end(endPosition());
1829     if (unit == "word") {
1830         start = startOfWord(start);
1831         end = endOfWord(end);
1832     } else if (unit == "sentence") {
1833         start = startOfSentence(start);
1834         end = endOfSentence(end);
1835     } else if (unit == "block") {
1836         start = startOfParagraph(start);
1837         end = endOfParagraph(end);
1838     } else if (unit == "document") {
1839         start = startOfDocument(start);
1840         end = endOfDocument(end);
1841     } else
1842         return;
1843     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
1844     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
1845 }
1846
1847 PassRefPtr<ClientRectList> Range::getClientRects() const
1848 {
1849     if (!m_start.container())
1850         return 0;
1851
1852     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1853
1854     Vector<FloatQuad> quads;
1855     getBorderAndTextQuads(quads);
1856
1857     return ClientRectList::create(quads);
1858 }
1859
1860 PassRefPtr<ClientRect> Range::getBoundingClientRect() const
1861 {
1862     if (!m_start.container())
1863         return 0;
1864
1865     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1866
1867     Vector<FloatQuad> quads;
1868     getBorderAndTextQuads(quads);
1869
1870     if (quads.isEmpty())
1871         return ClientRect::create();
1872
1873     IntRect result;
1874     for (size_t i = 0; i < quads.size(); ++i)
1875         result.unite(quads[i].enclosingBoundingBox());
1876
1877     return ClientRect::create(result);
1878 }
1879
1880 static void adjustFloatQuadsForScrollAndAbsoluteZoom(Vector<FloatQuad>& quads, Document* document, RenderObject* renderer)
1881 {
1882     FrameView* view = document->view();
1883     if (!view)
1884         return;
1885
1886     IntRect visibleContentRect = view->visibleContentRect();
1887     for (size_t i = 0; i < quads.size(); ++i) {
1888         quads[i].move(-visibleContentRect.x(), -visibleContentRect.y());
1889         adjustFloatQuadForAbsoluteZoom(quads[i], renderer);
1890     }
1891 }
1892
1893 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
1894 {
1895     Node* startContainer = m_start.container();
1896     Node* endContainer = m_end.container();
1897     Node* stopNode = pastLastNode();
1898
1899     HashSet<Node*> nodeSet;
1900     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1901         if (node->isElementNode())
1902             nodeSet.add(node);
1903     }
1904
1905     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1906         if (node->isElementNode()) {
1907             if (!nodeSet.contains(node->parentNode())) {
1908                 if (RenderBoxModelObject* renderBoxModelObject = static_cast<Element*>(node)->renderBoxModelObject()) {
1909                     Vector<FloatQuad> elementQuads;
1910                     renderBoxModelObject->absoluteQuads(elementQuads);
1911                     adjustFloatQuadsForScrollAndAbsoluteZoom(elementQuads, m_ownerDocument.get(), renderBoxModelObject);
1912
1913                     quads.append(elementQuads);
1914                 }
1915             }
1916         } else if (node->isTextNode()) {
1917             if (RenderObject* renderer = static_cast<Text*>(node)->renderer()) {
1918                 RenderText* renderText = toRenderText(renderer);
1919                 int startOffset = (node == startContainer) ? m_start.offset() : 0;
1920                 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
1921
1922                 Vector<FloatQuad> textQuads;
1923                 renderText->absoluteQuadsForRange(textQuads, startOffset, endOffset);
1924                 adjustFloatQuadsForScrollAndAbsoluteZoom(textQuads, m_ownerDocument.get(), renderText);
1925
1926                 quads.append(textQuads);
1927             }
1928         }
1929     }
1930 }
1931
1932 } // namespace WebCore