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, 2010, 2011 Apple Inc. All rights reserved.
7 * Copyright (C) 2011 Motorola Mobility. All rights reserved.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Library General Public
11 * License as published by the Free Software Foundation; either
12 * version 2 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * Library General Public License for more details.
18 *
19 * You should have received a copy of the GNU Library General Public License
20 * along with this library; see the file COPYING.LIB.  If not, write to
21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22 * Boston, MA 02110-1301, USA.
23 */
24
25#include "config.h"
26#include "Range.h"
27
28#include "ClientRect.h"
29#include "ClientRectList.h"
30#include "DocumentFragment.h"
31#include "Frame.h"
32#include "FrameView.h"
33#include "HTMLElement.h"
34#include "HTMLNames.h"
35#include "NodeTraversal.h"
36#include "NodeWithIndex.h"
37#include "Page.h"
38#include "ProcessingInstruction.h"
39#include "RangeException.h"
40#include "RenderBoxModelObject.h"
41#include "RenderText.h"
42#include "ScopedEventQueue.h"
43#include "TextIterator.h"
44#include "VisiblePosition.h"
45#include "VisibleUnits.h"
46#include "htmlediting.h"
47#include "markup.h"
48#include <stdio.h>
49#include <wtf/RefCountedLeakCounter.h>
50#include <wtf/text/CString.h>
51#include <wtf/text/StringBuilder.h>
52
53#if PLATFORM(IOS)
54#include "SelectionRect.h"
55#endif
56
57namespace WebCore {
58
59using namespace HTMLNames;
60
61DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, rangeCounter, ("Range"));
62
63inline Range::Range(Document& ownerDocument)
64    : m_ownerDocument(ownerDocument)
65    , m_start(&ownerDocument)
66    , m_end(&ownerDocument)
67{
68#ifndef NDEBUG
69    rangeCounter.increment();
70#endif
71
72    m_ownerDocument->attachRange(this);
73}
74
75PassRefPtr<Range> Range::create(Document& ownerDocument)
76{
77    return adoptRef(new Range(ownerDocument));
78}
79
80inline Range::Range(Document& ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
81    : m_ownerDocument(ownerDocument)
82    , m_start(&ownerDocument)
83    , m_end(&ownerDocument)
84{
85#ifndef NDEBUG
86    rangeCounter.increment();
87#endif
88
89    m_ownerDocument->attachRange(this);
90
91    // Simply setting the containers and offsets directly would not do any of the checking
92    // that setStart and setEnd do, so we call those functions.
93    setStart(startContainer, startOffset);
94    setEnd(endContainer, endOffset);
95}
96
97PassRefPtr<Range> Range::create(Document& ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
98{
99    return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
100}
101
102PassRefPtr<Range> Range::create(Document& ownerDocument, const Position& start, const Position& end)
103{
104    return adoptRef(new Range(ownerDocument, start.containerNode(), start.computeOffsetInContainerNode(), end.containerNode(), end.computeOffsetInContainerNode()));
105}
106
107PassRefPtr<Range> Range::create(ScriptExecutionContext& context)
108{
109    return adoptRef(new Range(toDocument(context)));
110}
111
112#if PLATFORM(IOS)
113PassRefPtr<Range> Range::create(Document& ownerDocument, const VisiblePosition& visibleStart, const VisiblePosition& visibleEnd)
114{
115    Position start = visibleStart.deepEquivalent().parentAnchoredEquivalent();
116    Position end = visibleEnd.deepEquivalent().parentAnchoredEquivalent();
117    return adoptRef(new Range(ownerDocument, start.anchorNode(), start.deprecatedEditingOffset(), end.anchorNode(), end.deprecatedEditingOffset()));
118}
119#endif
120
121Range::~Range()
122{
123    // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044
124    m_ownerDocument->detachRange(this);
125
126#ifndef NDEBUG
127    rangeCounter.decrement();
128#endif
129}
130
131void Range::setDocument(Document& document)
132{
133    ASSERT(&m_ownerDocument.get() != &document);
134    m_ownerDocument->detachRange(this);
135    m_ownerDocument = document;
136    m_start.setToStartOfNode(&document);
137    m_end.setToStartOfNode(&document);
138    m_ownerDocument->attachRange(this);
139}
140
141Node* Range::startContainer(ExceptionCode& ec) const
142{
143    if (!m_start.container()) {
144        ec = INVALID_STATE_ERR;
145        return 0;
146    }
147
148    return m_start.container();
149}
150
151int Range::startOffset(ExceptionCode& ec) const
152{
153    if (!m_start.container()) {
154        ec = INVALID_STATE_ERR;
155        return 0;
156    }
157
158    return m_start.offset();
159}
160
161Node* Range::endContainer(ExceptionCode& ec) const
162{
163    if (!m_start.container()) {
164        ec = INVALID_STATE_ERR;
165        return 0;
166    }
167
168    return m_end.container();
169}
170
171int Range::endOffset(ExceptionCode& ec) const
172{
173    if (!m_start.container()) {
174        ec = INVALID_STATE_ERR;
175        return 0;
176    }
177
178    return m_end.offset();
179}
180
181Node* Range::commonAncestorContainer(ExceptionCode& ec) const
182{
183    if (!m_start.container()) {
184        ec = INVALID_STATE_ERR;
185        return 0;
186    }
187
188    return commonAncestorContainer(m_start.container(), m_end.container());
189}
190
191Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
192{
193    for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
194        for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
195            if (parentA == parentB)
196                return parentA;
197        }
198    }
199    return 0;
200}
201
202bool Range::collapsed(ExceptionCode& ec) const
203{
204    if (!m_start.container()) {
205        ec = INVALID_STATE_ERR;
206        return 0;
207    }
208
209    return m_start == m_end;
210}
211
212static inline bool checkForDifferentRootContainer(const RangeBoundaryPoint& start, const RangeBoundaryPoint& end)
213{
214    Node* endRootContainer = end.container();
215    while (endRootContainer->parentNode())
216        endRootContainer = endRootContainer->parentNode();
217    Node* startRootContainer = start.container();
218    while (startRootContainer->parentNode())
219        startRootContainer = startRootContainer->parentNode();
220
221    return startRootContainer != endRootContainer || (Range::compareBoundaryPoints(start, end, ASSERT_NO_EXCEPTION) > 0);
222}
223
224void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
225{
226    if (!m_start.container()) {
227        ec = INVALID_STATE_ERR;
228        return;
229    }
230
231    if (!refNode) {
232        ec = NOT_FOUND_ERR;
233        return;
234    }
235
236    bool didMoveDocument = false;
237    if (&refNode->document() != &ownerDocument()) {
238        setDocument(refNode->document());
239        didMoveDocument = true;
240    }
241
242    ec = 0;
243    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
244    if (ec)
245        return;
246
247    m_start.set(refNode, offset, childNode);
248
249    if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
250        collapse(true, ec);
251}
252
253void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
254{
255    if (!m_start.container()) {
256        ec = INVALID_STATE_ERR;
257        return;
258    }
259
260    if (!refNode) {
261        ec = NOT_FOUND_ERR;
262        return;
263    }
264
265    bool didMoveDocument = false;
266    if (&refNode->document() != &ownerDocument()) {
267        setDocument(refNode->document());
268        didMoveDocument = true;
269    }
270
271    ec = 0;
272    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
273    if (ec)
274        return;
275
276    m_end.set(refNode, offset, childNode);
277
278    if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
279        collapse(false, ec);
280}
281
282void Range::setStart(const Position& start, ExceptionCode& ec)
283{
284    Position parentAnchored = start.parentAnchoredEquivalent();
285    setStart(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
286}
287
288void Range::setEnd(const Position& end, ExceptionCode& ec)
289{
290    Position parentAnchored = end.parentAnchoredEquivalent();
291    setEnd(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
292}
293
294void Range::collapse(bool toStart, ExceptionCode& ec)
295{
296    if (!m_start.container()) {
297        ec = INVALID_STATE_ERR;
298        return;
299    }
300
301    if (toStart)
302        m_end = m_start;
303    else
304        m_start = m_end;
305}
306
307bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
308{
309    if (!m_start.container()) {
310        ec = INVALID_STATE_ERR;
311        return false;
312    }
313
314    if (!refNode) {
315        ec = HIERARCHY_REQUEST_ERR;
316        return false;
317    }
318
319    if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) {
320        return false;
321    }
322
323    ec = 0;
324    checkNodeWOffset(refNode, offset, ec);
325    if (ec)
326        return false;
327
328    return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) >= 0 && !ec
329        && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) <= 0 && !ec;
330}
331
332short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const
333{
334    // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
335    // This method returns -1, 0 or 1 depending on if the point described by the
336    // refNode node and an offset within the node is before, same as, or after the range respectively.
337
338    if (!m_start.container()) {
339        ec = INVALID_STATE_ERR;
340        return 0;
341    }
342
343    if (!refNode) {
344        ec = HIERARCHY_REQUEST_ERR;
345        return 0;
346    }
347
348    if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) {
349        ec = WRONG_DOCUMENT_ERR;
350        return 0;
351    }
352
353    ec = 0;
354    checkNodeWOffset(refNode, offset, ec);
355    if (ec)
356        return 0;
357
358    // compare to start, and point comes before
359    if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) < 0)
360        return -1;
361
362    if (ec)
363        return 0;
364
365    // compare to end, and point comes after
366    if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) > 0 && !ec)
367        return 1;
368
369    // point is in the middle of this range, or on the boundary points
370    return 0;
371}
372
373Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const
374{
375    // http://developer.mozilla.org/en/docs/DOM:range.compareNode
376    // This method returns 0, 1, 2, or 3 based on if the node is before, after,
377    // before and after(surrounds), or inside the range, respectively
378
379    if (!refNode) {
380        ec = NOT_FOUND_ERR;
381        return NODE_BEFORE;
382    }
383
384    if (!m_start.container() && refNode->inDocument()) {
385        ec = INVALID_STATE_ERR;
386        return NODE_BEFORE;
387    }
388
389    if (m_start.container() && !refNode->inDocument()) {
390        // Firefox doesn't throw an exception for this case; it returns 0.
391        return NODE_BEFORE;
392    }
393
394    if (&refNode->document() != &ownerDocument()) {
395        // Firefox doesn't throw an exception for this case; it returns 0.
396        return NODE_BEFORE;
397    }
398
399    ContainerNode* parentNode = refNode->parentNode();
400    int nodeIndex = refNode->nodeIndex();
401
402    if (!parentNode) {
403        // if the node is the top document we should return NODE_BEFORE_AND_AFTER
404        // but we throw to match firefox behavior
405        ec = NOT_FOUND_ERR;
406        return NODE_BEFORE;
407    }
408
409    if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
410        if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
411            return NODE_BEFORE_AND_AFTER;
412        return NODE_BEFORE; // ends before or in the range
413    } else { // starts at or after the range start
414        if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
415            return NODE_AFTER;
416        return NODE_INSIDE; // ends inside the range
417    }
418}
419
420short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
421{
422    if (!m_start.container()) {
423        ec = INVALID_STATE_ERR;
424        return 0;
425    }
426
427    if (!sourceRange) {
428        ec = NOT_FOUND_ERR;
429        return 0;
430    }
431
432    ec = 0;
433    Node* thisCont = commonAncestorContainer(ec);
434    if (ec)
435        return 0;
436    Node* sourceCont = sourceRange->commonAncestorContainer(ec);
437    if (ec)
438        return 0;
439
440    if (&thisCont->document() != &sourceCont->document()) {
441        ec = WRONG_DOCUMENT_ERR;
442        return 0;
443    }
444
445    Node* thisTop = thisCont;
446    Node* sourceTop = sourceCont;
447    while (thisTop->parentNode())
448        thisTop = thisTop->parentNode();
449    while (sourceTop->parentNode())
450        sourceTop = sourceTop->parentNode();
451    if (thisTop != sourceTop) { // in different DocumentFragments
452        ec = WRONG_DOCUMENT_ERR;
453        return 0;
454    }
455
456    switch (how) {
457        case START_TO_START:
458            return compareBoundaryPoints(m_start, sourceRange->m_start, ec);
459        case START_TO_END:
460            return compareBoundaryPoints(m_end, sourceRange->m_start, ec);
461        case END_TO_END:
462            return compareBoundaryPoints(m_end, sourceRange->m_end, ec);
463        case END_TO_START:
464            return compareBoundaryPoints(m_start, sourceRange->m_end, ec);
465    }
466
467    ec = SYNTAX_ERR;
468    return 0;
469}
470
471short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB, ExceptionCode& ec)
472{
473    ASSERT(containerA);
474    ASSERT(containerB);
475
476    if (!containerA)
477        return -1;
478    if (!containerB)
479        return 1;
480
481    // see DOM2 traversal & range section 2.5
482
483    // case 1: both points have the same container
484    if (containerA == containerB) {
485        if (offsetA == offsetB)
486            return 0;           // A is equal to B
487        if (offsetA < offsetB)
488            return -1;          // A is before B
489        else
490            return 1;           // A is after B
491    }
492
493    // case 2: node C (container B or an ancestor) is a child node of A
494    Node* c = containerB;
495    while (c && c->parentNode() != containerA)
496        c = c->parentNode();
497    if (c) {
498        int offsetC = 0;
499        Node* n = containerA->firstChild();
500        while (n != c && offsetC < offsetA) {
501            offsetC++;
502            n = n->nextSibling();
503        }
504
505        if (offsetA <= offsetC)
506            return -1;              // A is before B
507        else
508            return 1;               // A is after B
509    }
510
511    // case 3: node C (container A or an ancestor) is a child node of B
512    c = containerA;
513    while (c && c->parentNode() != containerB)
514        c = c->parentNode();
515    if (c) {
516        int offsetC = 0;
517        Node* n = containerB->firstChild();
518        while (n != c && offsetC < offsetB) {
519            offsetC++;
520            n = n->nextSibling();
521        }
522
523        if (offsetC < offsetB)
524            return -1;              // A is before B
525        else
526            return 1;               // A is after B
527    }
528
529    // case 4: containers A & B are siblings, or children of siblings
530    // ### we need to do a traversal here instead
531    Node* commonAncestor = commonAncestorContainer(containerA, containerB);
532    if (!commonAncestor) {
533        ec = WRONG_DOCUMENT_ERR;
534        return 0;
535    }
536    Node* childA = containerA;
537    while (childA && childA->parentNode() != commonAncestor)
538        childA = childA->parentNode();
539    if (!childA)
540        childA = commonAncestor;
541    Node* childB = containerB;
542    while (childB && childB->parentNode() != commonAncestor)
543        childB = childB->parentNode();
544    if (!childB)
545        childB = commonAncestor;
546
547    if (childA == childB)
548        return 0; // A is equal to B
549
550    Node* n = commonAncestor->firstChild();
551    while (n) {
552        if (n == childA)
553            return -1; // A is before B
554        if (n == childB)
555            return 1; // A is after B
556        n = n->nextSibling();
557    }
558
559    // Should never reach this point.
560    ASSERT_NOT_REACHED();
561    return 0;
562}
563
564short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB, ExceptionCode& ec)
565{
566    return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset(), ec);
567}
568
569bool Range::boundaryPointsValid() const
570{
571    ExceptionCode ec = 0;
572    return m_start.container() && compareBoundaryPoints(m_start, m_end, ec) <= 0 && !ec;
573}
574
575void Range::deleteContents(ExceptionCode& ec)
576{
577    checkDeleteExtract(ec);
578    if (ec)
579        return;
580
581    processContents(Delete, ec);
582}
583
584bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
585{
586    // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
587    // Returns a bool if the node intersects the range.
588
589    // Throw exception if the range is already detached.
590    if (!m_start.container()) {
591        ec = INVALID_STATE_ERR;
592        return false;
593    }
594    if (!refNode) {
595        ec = NOT_FOUND_ERR;
596        return false;
597    }
598
599    if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) {
600        // Firefox doesn't throw an exception for these cases; it returns false.
601        return false;
602    }
603
604    ContainerNode* parentNode = refNode->parentNode();
605    int nodeIndex = refNode->nodeIndex();
606
607    if (!parentNode) {
608        // if the node is the top document we should return NODE_BEFORE_AND_AFTER
609        // but we throw to match firefox behavior
610        ec = NOT_FOUND_ERR;
611        return false;
612    }
613
614    if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
615        comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
616        return false;
617    } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
618               comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
619        return false;
620    }
621
622    return true; // all other cases
623}
624
625static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
626{
627    if (node == commonRoot)
628        return 0;
629
630    ASSERT(commonRoot->contains(node));
631
632    while (node->parentNode() != commonRoot)
633        node = node->parentNode();
634
635    return node;
636}
637
638static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
639{
640    ASSERT(container);
641    ASSERT(commonRoot);
642
643    if (!commonRoot->contains(container))
644        return 0;
645
646    if (container == commonRoot) {
647        container = container->firstChild();
648        for (unsigned i = 0; container && i < offset; i++)
649            container = container->nextSibling();
650    } else {
651        while (container->parentNode() != commonRoot)
652            container = container->parentNode();
653    }
654
655    return container;
656}
657
658static inline unsigned lengthOfContentsInNode(Node* node)
659{
660    // This switch statement must be consistent with that of Range::processContentsBetweenOffsets.
661    switch (node->nodeType()) {
662    case Node::TEXT_NODE:
663    case Node::CDATA_SECTION_NODE:
664    case Node::COMMENT_NODE:
665        return toCharacterData(node)->length();
666    case Node::PROCESSING_INSTRUCTION_NODE:
667        return toProcessingInstruction(node)->data().length();
668    case Node::ELEMENT_NODE:
669    case Node::ATTRIBUTE_NODE:
670    case Node::ENTITY_REFERENCE_NODE:
671    case Node::ENTITY_NODE:
672    case Node::DOCUMENT_NODE:
673    case Node::DOCUMENT_TYPE_NODE:
674    case Node::DOCUMENT_FRAGMENT_NODE:
675    case Node::NOTATION_NODE:
676    case Node::XPATH_NAMESPACE_NODE:
677        return node->childNodeCount();
678    }
679    ASSERT_NOT_REACHED();
680    return 0;
681}
682
683PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
684{
685    typedef Vector<RefPtr<Node>> NodeVector;
686
687    RefPtr<DocumentFragment> fragment;
688    if (action == Extract || action == Clone)
689        fragment = DocumentFragment::create(ownerDocument());
690
691    ec = 0;
692    if (collapsed(ec))
693        return fragment.release();
694    if (ec)
695        return 0;
696
697    RefPtr<Node> commonRoot = commonAncestorContainer(ec);
698    if (ec)
699        return 0;
700    ASSERT(commonRoot);
701
702    if (m_start.container() == m_end.container()) {
703        processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec);
704        return fragment;
705    }
706
707    // Since mutation events can modify the range during the process, the boundary points need to be saved.
708    RangeBoundaryPoint originalStart(m_start);
709    RangeBoundaryPoint originalEnd(m_end);
710
711    // what is the highest node that partially selects the start / end of the range?
712    RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
713    RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
714
715    // Start and end containers are different.
716    // There are three possibilities here:
717    // 1. Start container == commonRoot (End container must be a descendant)
718    // 2. End container == commonRoot (Start container must be a descendant)
719    // 3. Neither is commonRoot, they are both descendants
720    //
721    // In case 3, we grab everything after the start (up until a direct child
722    // of commonRoot) into leftContents, and everything before the end (up until
723    // a direct child of commonRoot) into rightContents. Then we process all
724    // commonRoot children between leftContents and rightContents
725    //
726    // In case 1 or 2, we skip either processing of leftContents or rightContents,
727    // in which case the last lot of nodes either goes from the first or last
728    // child of commonRoot.
729    //
730    // These are deleted, cloned, or extracted (i.e. both) depending on action.
731
732    // Note that we are verifying that our common root hierarchy is still intact
733    // after any DOM mutation event, at various stages below. See webkit bug 60350.
734
735    RefPtr<Node> leftContents;
736    if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
737        leftContents = processContentsBetweenOffsets(action, 0, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(originalStart.container()), ec);
738        leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
739    }
740
741    RefPtr<Node> rightContents;
742    if (m_end.container() != commonRoot && commonRoot->contains(originalEnd.container())) {
743        rightContents = processContentsBetweenOffsets(action, 0, originalEnd.container(), 0, originalEnd.offset(), ec);
744        rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
745    }
746
747    // delete all children of commonRoot between the start and end container
748    RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
749    if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
750        processStart = processStart->nextSibling();
751    RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
752
753    // Collapse the range, making sure that the result is not within a node that was partially selected.
754    if (action == Extract || action == Delete) {
755        if (partialStart && commonRoot->contains(partialStart.get()))
756            setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
757        else if (partialEnd && commonRoot->contains(partialEnd.get()))
758            setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
759        if (ec)
760            return 0;
761        m_end = m_start;
762    }
763
764    // Now add leftContents, stuff in between, and rightContents to the fragment
765    // (or just delete the stuff in between)
766
767    if ((action == Extract || action == Clone) && leftContents)
768        fragment->appendChild(leftContents, ec);
769
770    if (processStart) {
771        NodeVector nodes;
772        for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
773            nodes.append(n);
774        processNodes(action, nodes, commonRoot, fragment, ec);
775    }
776
777    if ((action == Extract || action == Clone) && rightContents)
778        fragment->appendChild(rightContents, ec);
779
780    return fragment.release();
781}
782
783static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
784{
785    if (data->length() - endOffset)
786        data->deleteData(endOffset, data->length() - endOffset, ec);
787    if (startOffset)
788        data->deleteData(0, startOffset, ec);
789}
790
791PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment, Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
792{
793    ASSERT(container);
794    ASSERT(startOffset <= endOffset);
795
796    // This switch statement must be consistent with that of lengthOfContentsInNode.
797    RefPtr<Node> result;
798    switch (container->nodeType()) {
799    case Node::TEXT_NODE:
800    case Node::CDATA_SECTION_NODE:
801    case Node::COMMENT_NODE:
802        endOffset = std::min(endOffset, static_cast<CharacterData*>(container)->length());
803        startOffset = std::min(startOffset, endOffset);
804        if (action == Extract || action == Clone) {
805            RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
806            deleteCharacterData(c, startOffset, endOffset, ec);
807            if (fragment) {
808                result = fragment;
809                result->appendChild(c.release(), ec);
810            } else
811                result = c.release();
812        }
813        if (action == Extract || action == Delete)
814            toCharacterData(container)->deleteData(startOffset, endOffset - startOffset, ec);
815        break;
816    case Node::PROCESSING_INSTRUCTION_NODE:
817        endOffset = std::min(endOffset, static_cast<ProcessingInstruction*>(container)->data().length());
818        startOffset = std::min(startOffset, endOffset);
819        if (action == Extract || action == Clone) {
820            RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
821            c->setData(c->data().substring(startOffset, endOffset - startOffset), ec);
822            if (fragment) {
823                result = fragment;
824                result->appendChild(c.release(), ec);
825            } else
826                result = c.release();
827        }
828        if (action == Extract || action == Delete) {
829            ProcessingInstruction* pi = toProcessingInstruction(container);
830            String data(pi->data());
831            data.remove(startOffset, endOffset - startOffset);
832            pi->setData(data, ec);
833        }
834        break;
835    case Node::ELEMENT_NODE:
836    case Node::ATTRIBUTE_NODE:
837    case Node::ENTITY_REFERENCE_NODE:
838    case Node::ENTITY_NODE:
839    case Node::DOCUMENT_NODE:
840    case Node::DOCUMENT_TYPE_NODE:
841    case Node::DOCUMENT_FRAGMENT_NODE:
842    case Node::NOTATION_NODE:
843    case Node::XPATH_NAMESPACE_NODE:
844        // FIXME: Should we assert that some nodes never appear here?
845        if (action == Extract || action == Clone) {
846            if (fragment)
847                result = fragment;
848            else
849                result = container->cloneNode(false);
850        }
851
852        Node* n = container->firstChild();
853        Vector<RefPtr<Node>> nodes;
854        for (unsigned i = startOffset; n && i; i--)
855            n = n->nextSibling();
856        for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
857            nodes.append(n);
858
859        processNodes(action, nodes, container, result, ec);
860        break;
861    }
862
863    return result.release();
864}
865
866void Range::processNodes(ActionType action, Vector<RefPtr<Node>>& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
867{
868    for (unsigned i = 0; i < nodes.size(); i++) {
869        switch (action) {
870        case Delete:
871            oldContainer->removeChild(nodes[i].get(), ec);
872            break;
873        case Extract:
874            newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent
875            break;
876        case Clone:
877            newContainer->appendChild(nodes[i]->cloneNode(true), ec);
878            break;
879        }
880    }
881}
882
883PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
884{
885    typedef Vector<RefPtr<Node>> NodeVector;
886
887    RefPtr<Node> clonedContainer = passedClonedContainer;
888    Vector<RefPtr<Node>> ancestors;
889    for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
890        ancestors.append(n);
891
892    RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
893    for (Vector<RefPtr<Node>>::const_iterator it = ancestors.begin(); it != ancestors.end(); ++it) {
894        RefPtr<Node> ancestor = *it;
895        if (action == Extract || action == Clone) {
896            if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
897                clonedAncestor->appendChild(clonedContainer, ec);
898                clonedContainer = clonedAncestor;
899            }
900        }
901
902        // Copy siblings of an ancestor of start/end containers
903        // FIXME: This assertion may fail if DOM is modified during mutation event
904        // FIXME: Share code with Range::processNodes
905        ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
906
907        NodeVector nodes;
908        for (Node* child = firstChildInAncestorToProcess.get(); child;
909            child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
910            nodes.append(child);
911
912        for (NodeVector::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
913            Node* child = it->get();
914            switch (action) {
915            case Delete:
916                ancestor->removeChild(child, ec);
917                break;
918            case Extract: // will remove child from ancestor
919                if (direction == ProcessContentsForward)
920                    clonedContainer->appendChild(child, ec);
921                else
922                    clonedContainer->insertBefore(child, clonedContainer->firstChild(), ec);
923                break;
924            case Clone:
925                if (direction == ProcessContentsForward)
926                    clonedContainer->appendChild(child->cloneNode(true), ec);
927                else
928                    clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec);
929                break;
930            }
931        }
932        firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
933    }
934
935    return clonedContainer.release();
936}
937
938PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
939{
940    checkDeleteExtract(ec);
941    if (ec)
942        return 0;
943
944    return processContents(Extract, ec);
945}
946
947PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
948{
949    if (!m_start.container()) {
950        ec = INVALID_STATE_ERR;
951        return 0;
952    }
953
954    return processContents(Clone, ec);
955}
956
957void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
958{
959    RefPtr<Node> newNode = prpNewNode;
960
961    ec = 0;
962
963    if (!m_start.container()) {
964        ec = INVALID_STATE_ERR;
965        return;
966    }
967
968    if (!newNode) {
969        ec = NOT_FOUND_ERR;
970        return;
971    }
972
973    // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
974    // the Range is read-only.
975    if (containedByReadOnly()) {
976        ec = NO_MODIFICATION_ALLOWED_ERR;
977        return;
978    }
979
980    // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
981    // does not allow children of the type of newNode or if newNode is an ancestor of the container.
982
983    // an extra one here - if a text node is going to split, it must have a parent to insert into
984    bool startIsText = m_start.container()->isTextNode();
985    if (startIsText && !m_start.container()->parentNode()) {
986        ec = HIERARCHY_REQUEST_ERR;
987        return;
988    }
989
990    // In the case where the container is a text node, we check against the container's parent, because
991    // text nodes get split up upon insertion.
992    Node* checkAgainst;
993    if (startIsText)
994        checkAgainst = m_start.container()->parentNode();
995    else
996        checkAgainst = m_start.container();
997
998    Node::NodeType newNodeType = newNode->nodeType();
999    int numNewChildren;
1000    if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE && !newNode->isShadowRoot()) {
1001        // check each child node, not the DocumentFragment itself
1002        numNewChildren = 0;
1003        for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
1004            if (!checkAgainst->childTypeAllowed(c->nodeType())) {
1005                ec = HIERARCHY_REQUEST_ERR;
1006                return;
1007            }
1008            ++numNewChildren;
1009        }
1010    } else {
1011        numNewChildren = 1;
1012        if (!checkAgainst->childTypeAllowed(newNodeType)) {
1013            ec = HIERARCHY_REQUEST_ERR;
1014            return;
1015        }
1016    }
1017
1018    for (Node* n = m_start.container(); n; n = n->parentNode()) {
1019        if (n == newNode) {
1020            ec = HIERARCHY_REQUEST_ERR;
1021            return;
1022        }
1023    }
1024
1025    // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node.
1026    switch (newNodeType) {
1027    case Node::ATTRIBUTE_NODE:
1028    case Node::ENTITY_NODE:
1029    case Node::NOTATION_NODE:
1030    case Node::DOCUMENT_NODE:
1031        ec = RangeException::INVALID_NODE_TYPE_ERR;
1032        return;
1033    default:
1034        if (newNode->isShadowRoot()) {
1035            ec = RangeException::INVALID_NODE_TYPE_ERR;
1036            return;
1037        }
1038        break;
1039    }
1040
1041    EventQueueScope scope;
1042    bool collapsed = m_start == m_end;
1043    RefPtr<Node> container;
1044    if (startIsText) {
1045        container = m_start.container();
1046        RefPtr<Text> newText = toText(container.get())->splitText(m_start.offset(), ec);
1047        if (ec)
1048            return;
1049
1050        container = m_start.container();
1051        container->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
1052        if (ec)
1053            return;
1054
1055        if (collapsed && newText->parentNode() == container && &container->document() == &ownerDocument())
1056            m_end.setToBeforeChild(newText.get());
1057    } else {
1058        container = m_start.container();
1059        RefPtr<Node> firstInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->firstChild() : newNode;
1060        RefPtr<Node> lastInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->lastChild() : newNode;
1061        RefPtr<Node> childAfterInsertedContent = container->childNode(m_start.offset());
1062        container->insertBefore(newNode.release(), childAfterInsertedContent.get(), ec);
1063        if (ec)
1064            return;
1065
1066        if (collapsed && numNewChildren && &container->document() == &ownerDocument()) {
1067            if (firstInsertedChild->parentNode() == container)
1068                m_start.setToBeforeChild(firstInsertedChild.get());
1069            if (lastInsertedChild->parentNode() == container)
1070                m_end.set(container, lastInsertedChild->nodeIndex() + 1, lastInsertedChild.get());
1071        }
1072    }
1073}
1074
1075String Range::toString(ExceptionCode& ec) const
1076{
1077    if (!m_start.container()) {
1078        ec = INVALID_STATE_ERR;
1079        return String();
1080    }
1081
1082    StringBuilder builder;
1083
1084    Node* pastLast = pastLastNode();
1085    for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1086        if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1087            const String& data = static_cast<CharacterData*>(n)->data();
1088            int length = data.length();
1089            int start = (n == m_start.container()) ? std::min(std::max(0, m_start.offset()), length) : 0;
1090            int end = (n == m_end.container()) ? std::min(std::max(start, m_end.offset()), length) : length;
1091            builder.append(data, start, end - start);
1092        }
1093    }
1094
1095    return builder.toString();
1096}
1097
1098String Range::toHTML() const
1099{
1100    return createMarkup(*this);
1101}
1102
1103String Range::text() const
1104{
1105    if (!m_start.container())
1106        return String();
1107
1108    // We need to update layout, since plainText uses line boxes in the render tree.
1109    // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1110    m_start.container()->document().updateLayout();
1111
1112    return plainText(this);
1113}
1114
1115PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec)
1116{
1117    if (!m_start.container()) {
1118        ec = INVALID_STATE_ERR;
1119        return 0;
1120    }
1121
1122    Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1123    if (!element || !element->isHTMLElement()) {
1124        ec = NOT_SUPPORTED_ERR;
1125        return 0;
1126    }
1127
1128    RefPtr<DocumentFragment> fragment = WebCore::createContextualFragment(markup, toHTMLElement(element), AllowScriptingContentAndDoNotMarkAlreadyStarted, ec);
1129    if (!fragment)
1130        return 0;
1131
1132    return fragment.release();
1133}
1134
1135
1136void Range::detach(ExceptionCode& ec)
1137{
1138    // Check first to see if we've already detached:
1139    if (!m_start.container()) {
1140        ec = INVALID_STATE_ERR;
1141        return;
1142    }
1143
1144    m_ownerDocument->detachRange(this);
1145
1146    m_start.clear();
1147    m_end.clear();
1148}
1149
1150Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1151{
1152    switch (n->nodeType()) {
1153        case Node::DOCUMENT_TYPE_NODE:
1154        case Node::ENTITY_NODE:
1155        case Node::NOTATION_NODE:
1156            ec = RangeException::INVALID_NODE_TYPE_ERR;
1157            return 0;
1158        case Node::CDATA_SECTION_NODE:
1159        case Node::COMMENT_NODE:
1160        case Node::TEXT_NODE:
1161            if (static_cast<unsigned>(offset) > toCharacterData(n)->length())
1162                ec = INDEX_SIZE_ERR;
1163            return 0;
1164        case Node::PROCESSING_INSTRUCTION_NODE:
1165            if (static_cast<unsigned>(offset) > toProcessingInstruction(n)->data().length())
1166                ec = INDEX_SIZE_ERR;
1167            return 0;
1168        case Node::ATTRIBUTE_NODE:
1169        case Node::DOCUMENT_FRAGMENT_NODE:
1170        case Node::DOCUMENT_NODE:
1171        case Node::ELEMENT_NODE:
1172        case Node::ENTITY_REFERENCE_NODE:
1173        case Node::XPATH_NAMESPACE_NODE: {
1174            if (!offset)
1175                return 0;
1176            Node* childBefore = n->childNode(offset - 1);
1177            if (!childBefore)
1178                ec = INDEX_SIZE_ERR;
1179            return childBefore;
1180        }
1181    }
1182    ASSERT_NOT_REACHED();
1183    return 0;
1184}
1185
1186void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1187{
1188    // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1189    // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree,
1190    // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node.
1191
1192    switch (n->nodeType()) {
1193        case Node::ATTRIBUTE_NODE:
1194        case Node::DOCUMENT_FRAGMENT_NODE:
1195        case Node::DOCUMENT_NODE:
1196        case Node::ENTITY_NODE:
1197        case Node::NOTATION_NODE:
1198            ec = RangeException::INVALID_NODE_TYPE_ERR;
1199            return;
1200        case Node::CDATA_SECTION_NODE:
1201        case Node::COMMENT_NODE:
1202        case Node::DOCUMENT_TYPE_NODE:
1203        case Node::ELEMENT_NODE:
1204        case Node::ENTITY_REFERENCE_NODE:
1205        case Node::PROCESSING_INSTRUCTION_NODE:
1206        case Node::TEXT_NODE:
1207        case Node::XPATH_NAMESPACE_NODE:
1208            break;
1209    }
1210
1211    Node* root = n;
1212    while (ContainerNode* parent = root->parentNode())
1213        root = parent;
1214
1215    switch (root->nodeType()) {
1216        case Node::ATTRIBUTE_NODE:
1217        case Node::DOCUMENT_NODE:
1218        case Node::DOCUMENT_FRAGMENT_NODE:
1219            break;
1220        case Node::CDATA_SECTION_NODE:
1221        case Node::COMMENT_NODE:
1222        case Node::DOCUMENT_TYPE_NODE:
1223        case Node::ELEMENT_NODE:
1224        case Node::ENTITY_NODE:
1225        case Node::ENTITY_REFERENCE_NODE:
1226        case Node::NOTATION_NODE:
1227        case Node::PROCESSING_INSTRUCTION_NODE:
1228        case Node::TEXT_NODE:
1229        case Node::XPATH_NAMESPACE_NODE:
1230            ec = RangeException::INVALID_NODE_TYPE_ERR;
1231            return;
1232    }
1233}
1234
1235PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1236{
1237    if (!m_start.container()) {
1238        ec = INVALID_STATE_ERR;
1239        return 0;
1240    }
1241
1242    return Range::create(ownerDocument(), m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1243}
1244
1245void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1246{
1247    if (!m_start.container()) {
1248        ec = INVALID_STATE_ERR;
1249        return;
1250    }
1251
1252    if (!refNode) {
1253        ec = NOT_FOUND_ERR;
1254        return;
1255    }
1256
1257    ec = 0;
1258    checkNodeBA(refNode, ec);
1259    if (ec)
1260        return;
1261
1262    setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1263}
1264
1265void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1266{
1267    if (!m_start.container()) {
1268        ec = INVALID_STATE_ERR;
1269        return;
1270    }
1271
1272    if (!refNode) {
1273        ec = NOT_FOUND_ERR;
1274        return;
1275    }
1276
1277    ec = 0;
1278    checkNodeBA(refNode, ec);
1279    if (ec)
1280        return;
1281
1282    setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1283}
1284
1285void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1286{
1287    if (!m_start.container()) {
1288        ec = INVALID_STATE_ERR;
1289        return;
1290    }
1291
1292    if (!refNode) {
1293        ec = NOT_FOUND_ERR;
1294        return;
1295    }
1296
1297    ec = 0;
1298    checkNodeBA(refNode, ec);
1299    if (ec)
1300        return;
1301
1302    setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1303}
1304
1305void Range::selectNode(Node* refNode, ExceptionCode& ec)
1306{
1307    if (!m_start.container()) {
1308        ec = INVALID_STATE_ERR;
1309        return;
1310    }
1311
1312    if (!refNode) {
1313        ec = NOT_FOUND_ERR;
1314        return;
1315    }
1316
1317    // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1318    // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation
1319    // node.
1320    for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1321        switch (anc->nodeType()) {
1322            case Node::ATTRIBUTE_NODE:
1323            case Node::CDATA_SECTION_NODE:
1324            case Node::COMMENT_NODE:
1325            case Node::DOCUMENT_FRAGMENT_NODE:
1326            case Node::DOCUMENT_NODE:
1327            case Node::ELEMENT_NODE:
1328            case Node::ENTITY_REFERENCE_NODE:
1329            case Node::PROCESSING_INSTRUCTION_NODE:
1330            case Node::TEXT_NODE:
1331            case Node::XPATH_NAMESPACE_NODE:
1332                break;
1333            case Node::DOCUMENT_TYPE_NODE:
1334            case Node::ENTITY_NODE:
1335            case Node::NOTATION_NODE:
1336                ec = RangeException::INVALID_NODE_TYPE_ERR;
1337                return;
1338        }
1339    }
1340
1341    switch (refNode->nodeType()) {
1342        case Node::CDATA_SECTION_NODE:
1343        case Node::COMMENT_NODE:
1344        case Node::DOCUMENT_TYPE_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::ATTRIBUTE_NODE:
1352        case Node::DOCUMENT_FRAGMENT_NODE:
1353        case Node::DOCUMENT_NODE:
1354        case Node::ENTITY_NODE:
1355        case Node::NOTATION_NODE:
1356            ec = RangeException::INVALID_NODE_TYPE_ERR;
1357            return;
1358    }
1359
1360    if (&ownerDocument() != &refNode->document())
1361        setDocument(refNode->document());
1362
1363    ec = 0;
1364    setStartBefore(refNode, ec);
1365    if (ec)
1366        return;
1367    setEndAfter(refNode, ec);
1368}
1369
1370void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1371{
1372    if (!m_start.container()) {
1373        ec = INVALID_STATE_ERR;
1374        return;
1375    }
1376
1377    if (!refNode) {
1378        ec = NOT_FOUND_ERR;
1379        return;
1380    }
1381
1382    // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1383    // or DocumentType node.
1384    for (Node* n = refNode; n; n = n->parentNode()) {
1385        switch (n->nodeType()) {
1386            case Node::ATTRIBUTE_NODE:
1387            case Node::CDATA_SECTION_NODE:
1388            case Node::COMMENT_NODE:
1389            case Node::DOCUMENT_FRAGMENT_NODE:
1390            case Node::DOCUMENT_NODE:
1391            case Node::ELEMENT_NODE:
1392            case Node::ENTITY_REFERENCE_NODE:
1393            case Node::PROCESSING_INSTRUCTION_NODE:
1394            case Node::TEXT_NODE:
1395            case Node::XPATH_NAMESPACE_NODE:
1396                break;
1397            case Node::DOCUMENT_TYPE_NODE:
1398            case Node::ENTITY_NODE:
1399            case Node::NOTATION_NODE:
1400                ec = RangeException::INVALID_NODE_TYPE_ERR;
1401                return;
1402        }
1403    }
1404
1405    if (&ownerDocument() != &refNode->document())
1406        setDocument(refNode->document());
1407
1408    m_start.setToStartOfNode(refNode);
1409    m_end.setToEndOfNode(refNode);
1410}
1411
1412void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1413{
1414    RefPtr<Node> newParent = passNewParent;
1415
1416    if (!m_start.container()) {
1417        ec = INVALID_STATE_ERR;
1418        return;
1419    }
1420
1421    if (!newParent) {
1422        ec = NOT_FOUND_ERR;
1423        return;
1424    }
1425
1426    // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1427    // Document, or DocumentFragment node.
1428    switch (newParent->nodeType()) {
1429        case Node::ATTRIBUTE_NODE:
1430        case Node::DOCUMENT_FRAGMENT_NODE:
1431        case Node::DOCUMENT_NODE:
1432        case Node::DOCUMENT_TYPE_NODE:
1433        case Node::ENTITY_NODE:
1434        case Node::NOTATION_NODE:
1435            ec = RangeException::INVALID_NODE_TYPE_ERR;
1436            return;
1437        case Node::CDATA_SECTION_NODE:
1438        case Node::COMMENT_NODE:
1439        case Node::ELEMENT_NODE:
1440        case Node::ENTITY_REFERENCE_NODE:
1441        case Node::PROCESSING_INSTRUCTION_NODE:
1442        case Node::TEXT_NODE:
1443        case Node::XPATH_NAMESPACE_NODE:
1444            break;
1445    }
1446
1447    // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1448    // the Range is read-only.
1449    if (containedByReadOnly()) {
1450        ec = NO_MODIFICATION_ALLOWED_ERR;
1451        return;
1452    }
1453
1454    // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1455    Node* parentOfNewParent = m_start.container();
1456
1457    // If m_start.container() is a character data node, it will be split and it will be its parent that will
1458    // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1459    // although this will fail below for another reason).
1460    if (parentOfNewParent->isCharacterDataNode())
1461        parentOfNewParent = parentOfNewParent->parentNode();
1462    if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1463        ec = HIERARCHY_REQUEST_ERR;
1464        return;
1465    }
1466
1467    if (newParent->contains(m_start.container())) {
1468        ec = HIERARCHY_REQUEST_ERR;
1469        return;
1470    }
1471
1472    // FIXME: Do we need a check if the node would end up with a child node of a type not
1473    // allowed by the type of node?
1474
1475    // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1476    Node* startNonTextContainer = m_start.container();
1477    if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1478        startNonTextContainer = startNonTextContainer->parentNode();
1479    Node* endNonTextContainer = m_end.container();
1480    if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1481        endNonTextContainer = endNonTextContainer->parentNode();
1482    if (startNonTextContainer != endNonTextContainer) {
1483        ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1484        return;
1485    }
1486
1487    ec = 0;
1488    while (Node* n = newParent->firstChild()) {
1489        toContainerNode(newParent.get())->removeChild(n, ec);
1490        if (ec)
1491            return;
1492    }
1493    RefPtr<DocumentFragment> fragment = extractContents(ec);
1494    if (ec)
1495        return;
1496    insertNode(newParent, ec);
1497    if (ec)
1498        return;
1499    newParent->appendChild(fragment.release(), ec);
1500    if (ec)
1501        return;
1502    selectNode(newParent.get(), ec);
1503}
1504
1505void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1506{
1507    if (!m_start.container()) {
1508        ec = INVALID_STATE_ERR;
1509        return;
1510    }
1511
1512    if (!refNode) {
1513        ec = NOT_FOUND_ERR;
1514        return;
1515    }
1516
1517    ec = 0;
1518    checkNodeBA(refNode, ec);
1519    if (ec)
1520        return;
1521
1522    setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1523}
1524
1525void Range::checkDeleteExtract(ExceptionCode& ec)
1526{
1527    if (!m_start.container()) {
1528        ec = INVALID_STATE_ERR;
1529        return;
1530    }
1531
1532    ec = 0;
1533    if (!commonAncestorContainer(ec) || ec)
1534        return;
1535
1536    Node* pastLast = pastLastNode();
1537    for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1538        if (n->isReadOnlyNode()) {
1539            ec = NO_MODIFICATION_ALLOWED_ERR;
1540            return;
1541        }
1542        if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1543            ec = HIERARCHY_REQUEST_ERR;
1544            return;
1545        }
1546    }
1547
1548    if (containedByReadOnly()) {
1549        ec = NO_MODIFICATION_ALLOWED_ERR;
1550        return;
1551    }
1552}
1553
1554bool Range::containedByReadOnly() const
1555{
1556    for (Node* n = m_start.container(); n; n = n->parentNode()) {
1557        if (n->isReadOnlyNode())
1558            return true;
1559    }
1560    for (Node* n = m_end.container(); n; n = n->parentNode()) {
1561        if (n->isReadOnlyNode())
1562            return true;
1563    }
1564    return false;
1565}
1566
1567Node* Range::firstNode() const
1568{
1569    if (!m_start.container())
1570        return 0;
1571    if (m_start.container()->offsetInCharacters())
1572        return m_start.container();
1573    if (Node* child = m_start.container()->childNode(m_start.offset()))
1574        return child;
1575    if (!m_start.offset())
1576        return m_start.container();
1577    return NodeTraversal::nextSkippingChildren(m_start.container());
1578}
1579
1580ShadowRoot* Range::shadowRoot() const
1581{
1582    return startContainer() ? startContainer()->containingShadowRoot() : 0;
1583}
1584
1585Node* Range::pastLastNode() const
1586{
1587    if (!m_start.container() || !m_end.container())
1588        return 0;
1589    if (m_end.container()->offsetInCharacters())
1590        return NodeTraversal::nextSkippingChildren(m_end.container());
1591    if (Node* child = m_end.container()->childNode(m_end.offset()))
1592        return child;
1593    return NodeTraversal::nextSkippingChildren(m_end.container());
1594}
1595
1596IntRect Range::boundingBox() const
1597{
1598    IntRect result;
1599    Vector<IntRect> rects;
1600    textRects(rects);
1601    const size_t n = rects.size();
1602    for (size_t i = 0; i < n; ++i)
1603        result.unite(rects[i]);
1604    return result;
1605}
1606
1607void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1608{
1609    Node* startContainer = m_start.container();
1610    Node* endContainer = m_end.container();
1611
1612    if (!startContainer || !endContainer) {
1613        if (inFixed)
1614            *inFixed = NotFixedPosition;
1615        return;
1616    }
1617
1618    bool allFixed = true;
1619    bool someFixed = false;
1620
1621    Node* stopNode = pastLastNode();
1622    for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1623        RenderObject* r = node->renderer();
1624        if (!r)
1625            continue;
1626        bool isFixed = false;
1627        if (r->isBR())
1628            r->absoluteRects(rects, flooredLayoutPoint(r->localToAbsolute()));
1629        else if (r->isText()) {
1630            int startOffset = node == startContainer ? m_start.offset() : 0;
1631            int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1632            rects.appendVector(toRenderText(r)->absoluteRectsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1633        } else
1634            continue;
1635        allFixed &= isFixed;
1636        someFixed |= isFixed;
1637    }
1638
1639    if (inFixed)
1640        *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1641}
1642
1643void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1644{
1645    Node* startContainer = m_start.container();
1646    Node* endContainer = m_end.container();
1647
1648    if (!startContainer || !endContainer) {
1649        if (inFixed)
1650            *inFixed = NotFixedPosition;
1651        return;
1652    }
1653
1654    bool allFixed = true;
1655    bool someFixed = false;
1656
1657    Node* stopNode = pastLastNode();
1658    for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1659        RenderObject* r = node->renderer();
1660        if (!r)
1661            continue;
1662        bool isFixed = false;
1663        if (r->isBR())
1664            r->absoluteQuads(quads, &isFixed);
1665        else if (r->isText()) {
1666            int startOffset = node == startContainer ? m_start.offset() : 0;
1667            int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1668            quads.appendVector(toRenderText(r)->absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1669        } else
1670            continue;
1671        allFixed &= isFixed;
1672        someFixed |= isFixed;
1673    }
1674
1675    if (inFixed)
1676        *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1677}
1678
1679#if PLATFORM(IOS)
1680static bool intervalsSufficientlyOverlap(int startA, int endA, int startB, int endB)
1681{
1682    if (endA <= startA || endB <= startB)
1683        return false;
1684
1685    const float sufficientOverlap = .75;
1686
1687    int lengthA = endA - startA;
1688    int lengthB = endB - startB;
1689
1690    int maxStart = std::max(startA, startB);
1691    int minEnd = std::min(endA, endB);
1692
1693    if (maxStart > minEnd)
1694        return false;
1695
1696    return minEnd - maxStart >= sufficientOverlap * std::min(lengthA, lengthB);
1697}
1698
1699static inline void adjustLineHeightOfSelectionRects(Vector<SelectionRect>& rects, size_t numberOfRects, int lineNumber, int lineTop, int lineHeight)
1700{
1701    ASSERT(rects.size() >= numberOfRects);
1702    for (size_t i = numberOfRects; i; ) {
1703        --i;
1704        if (rects[i].lineNumber())
1705            break;
1706        rects[i].setLineNumber(lineNumber);
1707        rects[i].setLogicalTop(lineTop);
1708        rects[i].setLogicalHeight(lineHeight);
1709    }
1710}
1711
1712static SelectionRect coalesceSelectionRects(const SelectionRect& original, const SelectionRect& previous)
1713{
1714    SelectionRect result(unionRect(previous.rect(), original.rect()), original.isHorizontal(), original.pageNumber());
1715    result.setDirection(original.containsStart() || original.containsEnd() ? original.direction() : previous.direction());
1716    result.setContainsStart(previous.containsStart() || original.containsStart());
1717    result.setContainsEnd(previous.containsEnd() || original.containsEnd());
1718    result.setIsFirstOnLine(previous.isFirstOnLine() || original.isFirstOnLine());
1719    result.setIsLastOnLine(previous.isLastOnLine() || original.isLastOnLine());
1720    return result;
1721}
1722
1723// This function is similar in spirit to addLineBoxRects, but annotates the returned rectangles
1724// with additional state which helps iOS draw selections in its unique way.
1725void Range::collectSelectionRects(Vector<SelectionRect>& rects)
1726{
1727    if (!m_start.container() || !m_end.container())
1728        return;
1729
1730    Node* startContainer = m_start.container();
1731    Node* endContainer = m_end.container();
1732    int startOffset = m_start.offset();
1733    int endOffset = m_end.offset();
1734
1735    Vector<SelectionRect> newRects;
1736    Node* stopNode = pastLastNode();
1737    bool hasFlippedWritingMode = startContainer->renderer() && startContainer->renderer()->style().isFlippedBlocksWritingMode();
1738    bool containsDifferentWritingModes = false;
1739    for (Node* node = firstNode(); node && node != stopNode; node = NodeTraversal::next(node)) {
1740        RenderObject* renderer = node->renderer();
1741        // Only ask leaf render objects for their line box rects.
1742        if (renderer && !renderer->firstChildSlow() && renderer->style().userSelect() != SELECT_NONE) {
1743            bool isStartNode = renderer->node() == startContainer;
1744            bool isEndNode = renderer->node() == endContainer;
1745            if (hasFlippedWritingMode != renderer->style().isFlippedBlocksWritingMode())
1746                containsDifferentWritingModes = true;
1747            // FIXME: Sending 0 for the startOffset is a weird way of telling the renderer that the selection
1748            // doesn't start inside it, since we'll also send 0 if the selection *does* start in it, at offset 0.
1749            //
1750            // FIXME: Selection endpoints aren't always inside leaves, and we only build SelectionRects for leaves,
1751            // so we can't accurately determine which SelectionRects contain the selection start and end using
1752            // only the offsets of the start and end. We need to pass the whole Range.
1753            int beginSelectionOffset = isStartNode ? startOffset : 0;
1754            int endSelectionOffset = isEndNode ? endOffset : std::numeric_limits<int>::max();
1755            renderer->collectSelectionRects(newRects, beginSelectionOffset, endSelectionOffset);
1756            size_t numberOfNewRects = newRects.size();
1757            for (size_t i = 0; i < numberOfNewRects; ++i) {
1758                SelectionRect& selectionRect = newRects[i];
1759                if (selectionRect.containsStart() && !isStartNode)
1760                    selectionRect.setContainsStart(false);
1761                if (selectionRect.containsEnd() && !isEndNode)
1762                    selectionRect.setContainsEnd(false);
1763                if (selectionRect.logicalWidth() || selectionRect.logicalHeight())
1764                    rects.append(newRects[i]);
1765            }
1766            newRects.shrink(0);
1767        }
1768    }
1769
1770    // The range could span over nodes with different writing modes.
1771    // If this is the case, we use the writing mode of the common ancestor.
1772    if (containsDifferentWritingModes) {
1773        if (Node* ancestor = commonAncestorContainer(startContainer, endContainer))
1774            hasFlippedWritingMode = ancestor->renderer()->style().isFlippedBlocksWritingMode();
1775    }
1776
1777    const size_t numberOfRects = rects.size();
1778
1779    // If the selection ends in a BR, then add the line break bit to the last
1780    // rect we have. This will cause its selection rect to extend to the
1781    // end of the line.
1782    if (stopNode && stopNode->hasTagName(HTMLNames::brTag) && numberOfRects) {
1783        // Only set the line break bit if the end of the range actually
1784        // extends all the way to include the <br>. VisiblePosition helps to
1785        // figure this out.
1786        VisiblePosition endPosition(createLegacyEditingPosition(endContainer, endOffset), VP_DEFAULT_AFFINITY);
1787        VisiblePosition brPosition(createLegacyEditingPosition(stopNode, 0), VP_DEFAULT_AFFINITY);
1788        if (endPosition == brPosition)
1789            rects.last().setIsLineBreak(true);
1790    }
1791
1792    int lineTop = std::numeric_limits<int>::max();
1793    int lineBottom = std::numeric_limits<int>::min();
1794    int lastLineTop = lineTop;
1795    int lastLineBottom = lineBottom;
1796    int lineNumber = 0;
1797
1798    for (size_t i = 0; i < numberOfRects; ++i) {
1799        int currentRectTop = rects[i].logicalTop();
1800        int currentRectBottom = currentRectTop + rects[i].logicalHeight();
1801
1802        // We don't want to count the ruby text as a separate line.
1803        if (intervalsSufficientlyOverlap(currentRectTop, currentRectBottom, lineTop, lineBottom) || (i && rects[i].isRubyText())) {
1804            // Grow the current line bounds.
1805            lineTop = std::min(lineTop, currentRectTop);
1806            lineBottom = std::max(lineBottom, currentRectBottom);
1807            // Avoid overlap with the previous line.
1808            if (!hasFlippedWritingMode)
1809                lineTop = std::max(lastLineBottom, lineTop);
1810            else
1811                lineBottom = std::min(lastLineTop, lineBottom);
1812        } else {
1813            adjustLineHeightOfSelectionRects(rects, i, lineNumber, lineTop, lineBottom - lineTop);
1814            if (!hasFlippedWritingMode) {
1815                lastLineTop = lineTop;
1816                if (currentRectBottom >= lastLineTop) {
1817                    lastLineBottom = lineBottom;
1818                    lineTop = lastLineBottom;
1819                } else {
1820                    lineTop = currentRectTop;
1821                    lastLineBottom = std::numeric_limits<int>::min();
1822                }
1823                lineBottom = currentRectBottom;
1824            } else {
1825                lastLineBottom = lineBottom;
1826                if (currentRectTop <= lastLineBottom && i && rects[i].pageNumber() == rects[i - 1].pageNumber()) {
1827                    lastLineTop = lineTop;
1828                    lineBottom = lastLineTop;
1829                } else {
1830                    lastLineTop = std::numeric_limits<int>::max();
1831                    lineBottom = currentRectBottom;
1832                }
1833                lineTop = currentRectTop;
1834            }
1835            ++lineNumber;
1836        }
1837    }
1838
1839    // Adjust line height.
1840    adjustLineHeightOfSelectionRects(rects, numberOfRects, lineNumber, lineTop, lineBottom - lineTop);
1841
1842    // Sort the rectangles and make sure there are no gaps. The rectangles could be unsorted when
1843    // there is ruby text and we could have gaps on the line when adjacent elements on the line
1844    // have a different orientation.
1845    size_t firstRectWithCurrentLineNumber = 0;
1846    for (size_t currentRect = 1; currentRect < numberOfRects; ++currentRect) {
1847        if (rects[currentRect].lineNumber() != rects[currentRect - 1].lineNumber()) {
1848            firstRectWithCurrentLineNumber = currentRect;
1849            continue;
1850        }
1851        if (rects[currentRect].logicalLeft() >= rects[currentRect - 1].logicalLeft())
1852            continue;
1853
1854        SelectionRect selectionRect = rects[currentRect];
1855        size_t i;
1856        for (i = currentRect; i > firstRectWithCurrentLineNumber && selectionRect.logicalLeft() < rects[i - 1].logicalLeft(); --i)
1857            rects[i] = rects[i - 1];
1858        rects[i] = selectionRect;
1859    }
1860
1861    for (size_t j = 1; j < numberOfRects; ++j) {
1862        if (rects[j].lineNumber() != rects[j - 1].lineNumber())
1863            continue;
1864        SelectionRect& previousRect = rects[j - 1];
1865        bool previousRectMayNotReachRightEdge = (previousRect.direction() == LTR && previousRect.containsEnd()) || (previousRect.direction() == RTL && previousRect.containsStart());
1866        if (previousRectMayNotReachRightEdge)
1867            continue;
1868        int adjustedWidth = rects[j].logicalLeft() - previousRect.logicalLeft();
1869        if (adjustedWidth > previousRect.logicalWidth())
1870            previousRect.setLogicalWidth(adjustedWidth);
1871    }
1872
1873    int maxLineNumber = lineNumber;
1874
1875    // Extend rects out to edges as needed.
1876    for (size_t i = 0; i < numberOfRects; ++i) {
1877        SelectionRect& selectionRect = rects[i];
1878        if (!selectionRect.isLineBreak() && selectionRect.lineNumber() >= maxLineNumber)
1879            continue;
1880        if (selectionRect.direction() == RTL && selectionRect.isFirstOnLine()) {
1881            selectionRect.setLogicalWidth(selectionRect.logicalWidth() + selectionRect.logicalLeft() - selectionRect.minX());
1882            selectionRect.setLogicalLeft(selectionRect.minX());
1883        } else if (selectionRect.direction() == LTR && selectionRect.isLastOnLine())
1884            selectionRect.setLogicalWidth(selectionRect.maxX() - selectionRect.logicalLeft());
1885    }
1886
1887    // Union all the rectangles on interior lines (i.e. not first or last).
1888    // On first and last lines, just avoid having overlaps by merging intersecting rectangles.
1889    Vector<SelectionRect> unionedRects;
1890    IntRect interiorUnionRect;
1891    for (size_t i = 0; i < numberOfRects; ++i) {
1892        SelectionRect& currentRect = rects[i];
1893        if (currentRect.lineNumber() == 1) {
1894            ASSERT(interiorUnionRect.isEmpty());
1895            if (!unionedRects.isEmpty()) {
1896                SelectionRect& previousRect = unionedRects.last();
1897                if (previousRect.rect().intersects(currentRect.rect())) {
1898                    previousRect = coalesceSelectionRects(currentRect, previousRect);
1899                    continue;
1900                }
1901            }
1902            // Couldn't merge with previous rect, so just appending.
1903            unionedRects.append(currentRect);
1904        } else if (currentRect.lineNumber() < maxLineNumber) {
1905            if (interiorUnionRect.isEmpty()) {
1906                // Start collecting interior rects.
1907                interiorUnionRect = currentRect.rect();
1908            } else if (interiorUnionRect.intersects(currentRect.rect())
1909                || interiorUnionRect.maxX() == currentRect.rect().x()
1910                || interiorUnionRect.maxY() == currentRect.rect().y()
1911                || interiorUnionRect.x() == currentRect.rect().maxX()
1912                || interiorUnionRect.y() == currentRect.rect().maxY()) {
1913                // Only union the lines that are attached.
1914                // For iBooks, the interior lines may cross multiple horizontal pages.
1915                interiorUnionRect.unite(currentRect.rect());
1916            } else {
1917                unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1918                interiorUnionRect = currentRect.rect();
1919            }
1920        } else {
1921            // Processing last line.
1922            if (!interiorUnionRect.isEmpty()) {
1923                unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1924                interiorUnionRect = IntRect();
1925            }
1926
1927            ASSERT(!unionedRects.isEmpty());
1928            SelectionRect& previousRect = unionedRects.last();
1929            if (previousRect.logicalTop() == currentRect.logicalTop() && previousRect.rect().intersects(currentRect.rect())) {
1930                // previousRect is also on the last line, and intersects the current one.
1931                previousRect = coalesceSelectionRects(currentRect, previousRect);
1932                continue;
1933            }
1934            // Couldn't merge with previous rect, so just appending.
1935            unionedRects.append(currentRect);
1936        }
1937    }
1938
1939    rects.swap(unionedRects);
1940}
1941#endif
1942
1943#ifndef NDEBUG
1944void Range::formatForDebugger(char* buffer, unsigned length) const
1945{
1946    StringBuilder result;
1947    String s;
1948
1949    if (!m_start.container() || !m_end.container())
1950        result.appendLiteral("<empty>");
1951    else {
1952        const int FormatBufferSize = 1024;
1953        char s[FormatBufferSize];
1954        result.appendLiteral("from offset ");
1955        result.appendNumber(m_start.offset());
1956        result.appendLiteral(" of ");
1957        m_start.container()->formatForDebugger(s, FormatBufferSize);
1958        result.append(s);
1959        result.appendLiteral(" to offset ");
1960        result.appendNumber(m_end.offset());
1961        result.appendLiteral(" of ");
1962        m_end.container()->formatForDebugger(s, FormatBufferSize);
1963        result.append(s);
1964    }
1965
1966    strncpy(buffer, result.toString().utf8().data(), length - 1);
1967}
1968#endif
1969
1970bool Range::contains(const Range& other) const
1971{
1972    if (commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument() != other.commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument())
1973        return false;
1974
1975    short startToStart = compareBoundaryPoints(Range::START_TO_START, &other, ASSERT_NO_EXCEPTION);
1976    if (startToStart > 0)
1977        return false;
1978
1979    short endToEnd = compareBoundaryPoints(Range::END_TO_END, &other, ASSERT_NO_EXCEPTION);
1980    return endToEnd >= 0;
1981}
1982
1983bool areRangesEqual(const Range* a, const Range* b)
1984{
1985    if (a == b)
1986        return true;
1987    if (!a || !b)
1988        return false;
1989    return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1990}
1991
1992bool rangesOverlap(const Range* a, const Range* b)
1993{
1994    if (!a || !b)
1995        return false;
1996
1997    if (a == b)
1998        return true;
1999
2000    if (a->commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument() != b->commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument())
2001        return false;
2002
2003    short startToStart = a->compareBoundaryPoints(Range::START_TO_START, b, ASSERT_NO_EXCEPTION);
2004    short endToEnd = a->compareBoundaryPoints(Range::END_TO_END, b, ASSERT_NO_EXCEPTION);
2005
2006    // First range contains the second range.
2007    if (startToStart <= 0 && endToEnd >= 0)
2008        return true;
2009
2010    // End of first range is inside second range.
2011    if (a->compareBoundaryPoints(Range::START_TO_END, b, ASSERT_NO_EXCEPTION) >= 0 && endToEnd <= 0)
2012        return true;
2013
2014    // Start of first range is inside second range.
2015    if (startToStart >= 0 && a->compareBoundaryPoints(Range::END_TO_START, b, ASSERT_NO_EXCEPTION) <= 0)
2016        return true;
2017
2018    return false;
2019}
2020
2021PassRefPtr<Range> rangeOfContents(Node& node)
2022{
2023    RefPtr<Range> range = Range::create(node.document());
2024    int exception = 0;
2025    range->selectNodeContents(&node, exception);
2026    return range.release();
2027}
2028
2029int Range::maxStartOffset() const
2030{
2031    if (!m_start.container())
2032        return 0;
2033    if (!m_start.container()->offsetInCharacters())
2034        return m_start.container()->childNodeCount();
2035    return m_start.container()->maxCharacterOffset();
2036}
2037
2038int Range::maxEndOffset() const
2039{
2040    if (!m_end.container())
2041        return 0;
2042    if (!m_end.container()->offsetInCharacters())
2043        return m_end.container()->childNodeCount();
2044    return m_end.container()->maxCharacterOffset();
2045}
2046
2047static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container)
2048{
2049    if (!boundary.childBefore())
2050        return;
2051    if (boundary.container() != &container)
2052        return;
2053    boundary.invalidateOffset();
2054}
2055
2056void Range::nodeChildrenChanged(ContainerNode& container)
2057{
2058    ASSERT(&container.document() == &ownerDocument());
2059    boundaryNodeChildrenChanged(m_start, container);
2060    boundaryNodeChildrenChanged(m_end, container);
2061}
2062
2063static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
2064{
2065    for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
2066        if (boundary.childBefore() == nodeToBeRemoved) {
2067            boundary.setToStartOfNode(&container);
2068            return;
2069        }
2070
2071        for (Node* n = boundary.container(); n; n = n->parentNode()) {
2072            if (n == nodeToBeRemoved) {
2073                boundary.setToStartOfNode(&container);
2074                return;
2075            }
2076        }
2077    }
2078}
2079
2080void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
2081{
2082    ASSERT(&container.document() == &ownerDocument());
2083    boundaryNodeChildrenWillBeRemoved(m_start, container);
2084    boundaryNodeChildrenWillBeRemoved(m_end, container);
2085}
2086
2087static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
2088{
2089    if (boundary.childBefore() == nodeToBeRemoved) {
2090        boundary.childBeforeWillBeRemoved();
2091        return;
2092    }
2093
2094    for (Node* n = boundary.container(); n; n = n->parentNode()) {
2095        if (n == nodeToBeRemoved) {
2096            boundary.setToBeforeChild(nodeToBeRemoved);
2097            return;
2098        }
2099    }
2100}
2101
2102void Range::nodeWillBeRemoved(Node* node)
2103{
2104    ASSERT(node);
2105    ASSERT(&node->document() == &ownerDocument());
2106    ASSERT(node != &ownerDocument());
2107    ASSERT(node->parentNode());
2108    boundaryNodeWillBeRemoved(m_start, node);
2109    boundaryNodeWillBeRemoved(m_end, node);
2110}
2111
2112static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
2113{
2114    if (boundary.container() != text)
2115        return;
2116    unsigned boundaryOffset = boundary.offset();
2117    if (offset >= boundaryOffset)
2118        return;
2119    boundary.setOffset(boundaryOffset + length);
2120}
2121
2122void Range::textInserted(Node* text, unsigned offset, unsigned length)
2123{
2124    ASSERT(text);
2125    ASSERT(&text->document() == &ownerDocument());
2126    boundaryTextInserted(m_start, text, offset, length);
2127    boundaryTextInserted(m_end, text, offset, length);
2128}
2129
2130static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
2131{
2132    if (boundary.container() != text)
2133        return;
2134    unsigned boundaryOffset = boundary.offset();
2135    if (offset >= boundaryOffset)
2136        return;
2137    if (offset + length >= boundaryOffset)
2138        boundary.setOffset(offset);
2139    else
2140        boundary.setOffset(boundaryOffset - length);
2141}
2142
2143void Range::textRemoved(Node* text, unsigned offset, unsigned length)
2144{
2145    ASSERT(text);
2146    ASSERT(&text->document() == &ownerDocument());
2147    boundaryTextRemoved(m_start, text, offset, length);
2148    boundaryTextRemoved(m_end, text, offset, length);
2149}
2150
2151static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
2152{
2153    if (boundary.container() == oldNode.node())
2154        boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
2155    else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
2156        boundary.set(oldNode.node()->previousSibling(), offset, 0);
2157}
2158
2159void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
2160{
2161    ASSERT(oldNode.node());
2162    ASSERT(&oldNode.node()->document() == &ownerDocument());
2163    ASSERT(oldNode.node()->parentNode());
2164    ASSERT(oldNode.node()->isTextNode());
2165    ASSERT(oldNode.node()->previousSibling());
2166    ASSERT(oldNode.node()->previousSibling()->isTextNode());
2167    boundaryTextNodesMerged(m_start, oldNode, offset);
2168    boundaryTextNodesMerged(m_end, oldNode, offset);
2169}
2170
2171static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
2172{
2173    if (boundary.container() != oldNode)
2174        return;
2175    unsigned boundaryOffset = boundary.offset();
2176    if (boundaryOffset <= oldNode->length())
2177        return;
2178    boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
2179}
2180
2181void Range::textNodeSplit(Text* oldNode)
2182{
2183    ASSERT(oldNode);
2184    ASSERT(&oldNode->document() == &ownerDocument());
2185    ASSERT(oldNode->parentNode());
2186    ASSERT(oldNode->isTextNode());
2187    ASSERT(oldNode->nextSibling());
2188    ASSERT(oldNode->nextSibling()->isTextNode());
2189    boundaryTextNodesSplit(m_start, oldNode);
2190    boundaryTextNodesSplit(m_end, oldNode);
2191}
2192
2193void Range::expand(const String& unit, ExceptionCode& ec)
2194{
2195    VisiblePosition start(startPosition());
2196    VisiblePosition end(endPosition());
2197    if (unit == "word") {
2198        start = startOfWord(start);
2199        end = endOfWord(end);
2200    } else if (unit == "sentence") {
2201        start = startOfSentence(start);
2202        end = endOfSentence(end);
2203    } else if (unit == "block") {
2204        start = startOfParagraph(start);
2205        end = endOfParagraph(end);
2206    } else if (unit == "document") {
2207        start = startOfDocument(start);
2208        end = endOfDocument(end);
2209    } else
2210        return;
2211    setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
2212    setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
2213}
2214
2215PassRefPtr<ClientRectList> Range::getClientRects() const
2216{
2217    if (!m_start.container())
2218        return ClientRectList::create();
2219
2220    ownerDocument().updateLayoutIgnorePendingStylesheets();
2221
2222    Vector<FloatQuad> quads;
2223    getBorderAndTextQuads(quads);
2224
2225    return ClientRectList::create(quads);
2226}
2227
2228PassRefPtr<ClientRect> Range::getBoundingClientRect() const
2229{
2230    return ClientRect::create(boundingRect());
2231}
2232
2233void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
2234{
2235    Node* startContainer = m_start.container();
2236    Node* endContainer = m_end.container();
2237    Node* stopNode = pastLastNode();
2238
2239    HashSet<Node*> selectedElementsSet;
2240    for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
2241        if (node->isElementNode())
2242            selectedElementsSet.add(node);
2243    }
2244
2245    // Don't include elements that are only partially selected.
2246    Node* lastNode = m_end.childBefore() ? m_end.childBefore() : endContainer;
2247    for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode())
2248        selectedElementsSet.remove(parent);
2249
2250    for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
2251        if (node->isElementNode() && selectedElementsSet.contains(node) && !selectedElementsSet.contains(node->parentNode())) {
2252            if (RenderBoxModelObject* renderBoxModelObject = toElement(node)->renderBoxModelObject()) {
2253                Vector<FloatQuad> elementQuads;
2254                renderBoxModelObject->absoluteQuads(elementQuads);
2255                ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(elementQuads, renderBoxModelObject->style());
2256
2257                quads.appendVector(elementQuads);
2258            }
2259        } else if (node->isTextNode()) {
2260            if (RenderObject* renderer = toText(node)->renderer()) {
2261                const RenderText& renderText = toRenderText(*renderer);
2262                int startOffset = (node == startContainer) ? m_start.offset() : 0;
2263                int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
2264
2265                auto textQuads = renderText.absoluteQuadsForRange(startOffset, endOffset);
2266                ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(textQuads, renderText.style());
2267
2268                quads.appendVector(textQuads);
2269            }
2270        }
2271    }
2272}
2273
2274FloatRect Range::boundingRect() const
2275{
2276    if (!m_start.container())
2277        return FloatRect();
2278
2279    ownerDocument().updateLayoutIgnorePendingStylesheets();
2280
2281    Vector<FloatQuad> quads;
2282    getBorderAndTextQuads(quads);
2283    if (quads.isEmpty())
2284        return FloatRect();
2285
2286    FloatRect result;
2287    for (size_t i = 0; i < quads.size(); ++i)
2288        result.unite(quads[i].boundingBox());
2289
2290    return result;
2291}
2292
2293} // namespace WebCore
2294
2295#ifndef NDEBUG
2296
2297void showTree(const WebCore::Range* range)
2298{
2299    if (range && range->boundaryPointsValid()) {
2300        range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E");
2301        fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
2302    }
2303}
2304
2305#endif
2306