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