1 /**
2  * This file is part of the DOM implementation for KDE.
3  *
4  * (C) 1999-2003 Lars Knoll (knoll@kde.org)
5  * (C) 2001-2003 Dirk Mueller (mueller@kde.org)
6  * (C) 2000 Gunnstein Lye (gunnstein@netcom.no)
7  * (C) 2000 Frederik Holljen (frederik.holljen@hig.no)
8  * (C) 2001 Peter Kelly (pmk@post.com)
9  * Copyright (C) 2003-2008 Apple Computer, Inc.
10  *
11  * This library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Library General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19  * Library General Public License for more details.
20  *
21  * You should have received a copy of the GNU Library General Public License
22  * along with this library; see the file COPYING.LIB.  If not, write to
23  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
24  * Boston, MA 02110-1301, USA.
25  */
26 
27 #include "dom2_rangeimpl.h"
28 
29 #include <dom/dom_exception.h>
30 #include "dom_docimpl.h"
31 #include "dom_textimpl.h"
32 #include "dom_xmlimpl.h"
33 #include <html/html_elementimpl.h>
34 
35 using namespace DOM;
36 
RangeImpl(DocumentImpl * _ownerDocument)37 RangeImpl::RangeImpl(DocumentImpl *_ownerDocument)
38 {
39     m_ownerDocument = _ownerDocument;
40     m_ownerDocument->ref();
41     m_startContainer = _ownerDocument;
42     m_startContainer->ref();
43     m_endContainer = _ownerDocument;
44     m_endContainer->ref();
45     m_startOffset = 0;
46     m_endOffset = 0;
47     m_detached = false;
48 }
49 
RangeImpl(DocumentImpl * _ownerDocument,NodeImpl * _startContainer,long _startOffset,NodeImpl * _endContainer,long _endOffset)50 RangeImpl::RangeImpl(DocumentImpl *_ownerDocument,
51                      NodeImpl *_startContainer, long _startOffset,
52                      NodeImpl *_endContainer, long _endOffset)
53 {
54     m_ownerDocument = _ownerDocument;
55     m_ownerDocument->ref();
56     m_startContainer = _startContainer;
57     m_startContainer->ref();
58     m_startOffset = _startOffset;
59     m_endContainer = _endContainer;
60     m_endContainer->ref();
61     m_endOffset = _endOffset;
62     m_detached = false;
63 }
64 
~RangeImpl()65 RangeImpl::~RangeImpl()
66 {
67     m_ownerDocument->deref();
68     int exceptioncode = 0;
69     if (!m_detached) {
70         detach(exceptioncode);
71     }
72 }
73 
startContainer(int & exceptioncode) const74 NodeImpl *RangeImpl::startContainer(int &exceptioncode) const
75 {
76     if (m_detached) {
77         exceptioncode = DOMException::INVALID_STATE_ERR;
78         return nullptr;
79     }
80 
81     return m_startContainer;
82 }
83 
startOffset(int & exceptioncode) const84 long RangeImpl::startOffset(int &exceptioncode) const
85 {
86     if (m_detached) {
87         exceptioncode = DOMException::INVALID_STATE_ERR;
88         return 0;
89     }
90 
91     return m_startOffset;
92 }
93 
endContainer(int & exceptioncode) const94 NodeImpl *RangeImpl::endContainer(int &exceptioncode) const
95 {
96     if (m_detached) {
97         exceptioncode = DOMException::INVALID_STATE_ERR;
98         return nullptr;
99     }
100 
101     return m_endContainer;
102 }
103 
endOffset(int & exceptioncode) const104 long RangeImpl::endOffset(int &exceptioncode) const
105 {
106     if (m_detached) {
107         exceptioncode = DOMException::INVALID_STATE_ERR;
108         return 0;
109     }
110 
111     return m_endOffset;
112 }
113 
commonAncestorContainer(int & exceptioncode)114 NodeImpl *RangeImpl::commonAncestorContainer(int &exceptioncode)
115 {
116     if (m_detached) {
117         exceptioncode = DOMException::INVALID_STATE_ERR;
118         return nullptr;
119     }
120 
121     NodeImpl *com = commonAncestorContainer(m_startContainer, m_endContainer);
122     if (!com) { //  should never happen
123         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
124     }
125     return com;
126 }
127 
commonAncestorContainer(NodeImpl * containerA,NodeImpl * containerB)128 NodeImpl *RangeImpl::commonAncestorContainer(NodeImpl *containerA, NodeImpl *containerB)
129 {
130     NodeImpl *parentStart;
131 
132     for (parentStart = containerA; parentStart; parentStart = parentStart->parentNode()) {
133         NodeImpl *parentEnd = containerB;
134         while (parentEnd && (parentStart != parentEnd)) {
135             parentEnd = parentEnd->parentNode();
136         }
137 
138         if (parentStart == parentEnd) {
139             break;
140         }
141     }
142 
143     return parentStart;
144 }
145 
collapsed(int & exceptioncode) const146 bool RangeImpl::collapsed(int &exceptioncode) const
147 {
148     if (m_detached) {
149         exceptioncode = DOMException::INVALID_STATE_ERR;
150         return 0;
151     }
152 
153     return (m_startContainer == m_endContainer && m_startOffset == m_endOffset);
154 }
155 
setStart(NodeImpl * refNode,long offset,int & exceptioncode)156 void RangeImpl::setStart(NodeImpl *refNode, long offset, int &exceptioncode)
157 {
158     if (m_detached) {
159         exceptioncode = DOMException::INVALID_STATE_ERR;
160         return;
161     }
162 
163     if (!refNode) {
164         exceptioncode = DOMException::NOT_FOUND_ERR;
165         return;
166     }
167 
168     if (refNode->document() != m_ownerDocument) {
169         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
170         return;
171     }
172 
173     checkNodeWOffset(refNode, offset, exceptioncode);
174     if (exceptioncode) {
175         return;
176     }
177 
178     setStartContainer(refNode);
179     m_startOffset = offset;
180 
181     // check if different root container
182     NodeImpl *endRootContainer = m_endContainer;
183     while (endRootContainer->parentNode()) {
184         endRootContainer = endRootContainer->parentNode();
185     }
186     NodeImpl *startRootContainer = m_startContainer;
187     while (startRootContainer->parentNode()) {
188         startRootContainer = startRootContainer->parentNode();
189     }
190     if (startRootContainer != endRootContainer) {
191         collapse(true, exceptioncode);
192     }
193     // check if new start after end
194     else if (compareBoundaryPoints(m_startContainer, m_startOffset, m_endContainer, m_endOffset) > 0) {
195         collapse(true, exceptioncode);
196     }
197 }
198 
setEnd(NodeImpl * refNode,long offset,int & exceptioncode)199 void RangeImpl::setEnd(NodeImpl *refNode, long offset, int &exceptioncode)
200 {
201     if (m_detached) {
202         exceptioncode = DOMException::INVALID_STATE_ERR;
203         return;
204     }
205 
206     if (!refNode) {
207         exceptioncode = DOMException::NOT_FOUND_ERR;
208         return;
209     }
210 
211     if (refNode->document() != m_ownerDocument) {
212         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
213         return;
214     }
215 
216     checkNodeWOffset(refNode, offset, exceptioncode);
217     if (exceptioncode) {
218         return;
219     }
220 
221     setEndContainer(refNode);
222     m_endOffset = offset;
223 
224     // check if different root container
225     NodeImpl *endRootContainer = m_endContainer;
226     while (endRootContainer->parentNode()) {
227         endRootContainer = endRootContainer->parentNode();
228     }
229     NodeImpl *startRootContainer = m_startContainer;
230     while (startRootContainer->parentNode()) {
231         startRootContainer = startRootContainer->parentNode();
232     }
233     if (startRootContainer != endRootContainer) {
234         collapse(false, exceptioncode);
235     }
236     // check if new end before start
237     if (compareBoundaryPoints(m_startContainer, m_startOffset, m_endContainer, m_endOffset) > 0) {
238         collapse(false, exceptioncode);
239     }
240 }
241 
collapse(bool toStart,int & exceptioncode)242 void RangeImpl::collapse(bool toStart, int &exceptioncode)
243 {
244     if (m_detached) {
245         exceptioncode = DOMException::INVALID_STATE_ERR;
246         return;
247     }
248 
249     if (toStart) {  // collapse to start
250         setEndContainer(m_startContainer);
251         m_endOffset = m_startOffset;
252     } else {        // collapse to end
253         setStartContainer(m_endContainer);
254         m_startOffset = m_endOffset;
255     }
256 }
257 
compareBoundaryPoints(Range::CompareHow how,RangeImpl * sourceRange,int & exceptioncode)258 short RangeImpl::compareBoundaryPoints(Range::CompareHow how, RangeImpl *sourceRange, int &exceptioncode)
259 {
260     if (m_detached) {
261         exceptioncode = DOMException::INVALID_STATE_ERR;
262         return 0;
263     }
264 
265     if (!sourceRange) {
266         exceptioncode = DOMException::NOT_FOUND_ERR;
267         return 0;
268     }
269 
270     NodeImpl *thisCont = commonAncestorContainer(exceptioncode);
271     NodeImpl *sourceCont = sourceRange->commonAncestorContainer(exceptioncode);
272     if (exceptioncode) {
273         return 0;
274     }
275 
276     if (thisCont->document() != sourceCont->document()) {
277         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
278         return 0;
279     }
280 
281     NodeImpl *thisTop = thisCont;
282     NodeImpl *sourceTop = sourceCont;
283     while (thisTop->parentNode()) {
284         thisTop = thisTop->parentNode();
285     }
286     while (sourceTop->parentNode()) {
287         sourceTop = sourceTop->parentNode();
288     }
289     if (thisTop != sourceTop) { // in different DocumentFragments
290         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
291         return 0;
292     }
293 
294     switch (how) {
295     case Range::START_TO_START:
296         return compareBoundaryPoints(m_startContainer, m_startOffset,
297                                      sourceRange->startContainer(exceptioncode), sourceRange->startOffset(exceptioncode));
298         break;
299     case Range::START_TO_END:
300         return compareBoundaryPoints(m_endContainer, m_endOffset,
301                                      sourceRange->startContainer(exceptioncode), sourceRange->startOffset(exceptioncode));
302         break;
303     case Range::END_TO_END:
304         return compareBoundaryPoints(m_endContainer, m_endOffset,
305                                      sourceRange->endContainer(exceptioncode), sourceRange->endOffset(exceptioncode));
306         break;
307     case Range::END_TO_START:
308         return compareBoundaryPoints(m_startContainer, m_startOffset,
309                                      sourceRange->endContainer(exceptioncode), sourceRange->endOffset(exceptioncode));
310         break;
311     default:
312         exceptioncode = DOMException::SYNTAX_ERR;
313         return 0;
314     }
315 }
316 
compareBoundaryPoints(NodeImpl * containerA,long offsetA,NodeImpl * containerB,long offsetB)317 short RangeImpl::compareBoundaryPoints(NodeImpl *containerA, long offsetA, NodeImpl *containerB, long offsetB)
318 {
319     // see DOM2 traversal & range section 2.5
320 
321     // case 1: both points have the same container
322     if (containerA == containerB) {
323         if (offsetA == offsetB) {
324             return 0;    // A is equal to B
325         }
326         if (offsetA < offsetB) {
327             return -1;    // A is before B
328         } else {
329             return 1;    // A is after B
330         }
331     }
332 
333     // case 2: node C (container B or an ancestor) is a child node of A
334     NodeImpl *c = containerB;
335     while (c && c->parentNode() != containerA) {
336         c = c->parentNode();
337     }
338     if (c) {
339         int offsetC = 0;
340         NodeImpl *n = containerA->firstChild();
341         while (n != c) {
342             offsetC++;
343             n = n->nextSibling();
344         }
345 
346         if (offsetA <= offsetC) {
347             return -1;    // A is before B
348         } else {
349             return 1;    // A is after B
350         }
351     }
352 
353     // case 3: node C (container A or an ancestor) is a child node of B
354     c = containerA;
355     while (c && c->parentNode() != containerB) {
356         c = c->parentNode();
357     }
358     if (c) {
359         int offsetC = 0;
360         NodeImpl *n = containerB->firstChild();
361         while (n != c) {
362             offsetC++;
363             n = n->nextSibling();
364         }
365 
366         if (offsetC < offsetB) {
367             return -1;    // A is before B
368         } else {
369             return 1;    // A is after B
370         }
371     }
372 
373     // case 4: containers A & B are siblings, or children of siblings
374     // ### we need to do a traversal here instead
375     NodeImpl *cmnRoot = commonAncestorContainer(containerA, containerB);
376     if (!cmnRoot) {
377         return -1;    // Whatever...
378     }
379     NodeImpl *childA = containerA;
380     while (childA->parentNode() != cmnRoot) {
381         childA = childA->parentNode();
382     }
383     NodeImpl *childB = containerB;
384     while (childB->parentNode() != cmnRoot) {
385         childB = childB->parentNode();
386     }
387 
388     NodeImpl *n = cmnRoot->firstChild();
389     int i = 0;
390     int childAOffset = -1;
391     int childBOffset = -1;
392     while (childAOffset < 0 || childBOffset < 0) {
393         if (n == childA) {
394             childAOffset = i;
395         }
396         if (n == childB) {
397             childBOffset = i;
398         }
399         n = n->nextSibling();
400         i++;
401     }
402 
403     if (childAOffset == childBOffset) {
404         return 0;    // A is equal to B
405     }
406     if (childAOffset < childBOffset) {
407         return -1;    // A is before B
408     } else {
409         return 1;    // A is after B
410     }
411 }
412 
boundaryPointsValid()413 bool RangeImpl::boundaryPointsValid()
414 {
415     short valid =  compareBoundaryPoints(m_startContainer, m_startOffset,
416                                          m_endContainer, m_endOffset);
417     if (valid == 1) {
418         return false;
419     } else {
420         return true;
421     }
422 
423 }
424 
deleteContents(int & exceptioncode)425 void RangeImpl::deleteContents(int &exceptioncode)
426 {
427     if (m_detached) {
428         exceptioncode = DOMException::INVALID_STATE_ERR;
429         return;
430     }
431 
432     checkDeleteExtract(exceptioncode);
433     if (exceptioncode) {
434         return;
435     }
436 
437     processContents(DELETE_CONTENTS, exceptioncode);
438 }
439 
processContents(ActionType action,int & exceptioncode)440 DocumentFragmentImpl *RangeImpl::processContents(ActionType action, int &exceptioncode)
441 {
442     // ### when mutation events are implemented, we will have to take into account
443     // situations where the tree is being transformed while we delete - ugh!
444 
445     // ### perhaps disable node deletion notification for this range while we do this?
446 
447     // shortcut for special case
448     if (collapsed(exceptioncode) || exceptioncode) {
449         if (action == CLONE_CONTENTS || action == EXTRACT_CONTENTS) {
450             return new DocumentFragmentImpl(m_ownerDocument);
451         }
452         return nullptr;
453     }
454 
455     NodeImpl *cmnRoot = commonAncestorContainer(exceptioncode);
456     if (exceptioncode) {
457         return nullptr;
458     }
459 
460     // what is the highest node that partially selects the start of the range?
461     NodeImpl *partialStart = nullptr;
462     if (m_startContainer != cmnRoot) {
463         partialStart = m_startContainer;
464         while (partialStart->parentNode() != cmnRoot) {
465             partialStart = partialStart->parentNode();
466         }
467     }
468 
469     // what is the highest node that partially selects the end of the range?
470     NodeImpl *partialEnd = nullptr;
471     if (m_endContainer != cmnRoot) {
472         partialEnd = m_endContainer;
473         while (partialEnd->parentNode() != cmnRoot) {
474             partialEnd = partialEnd->parentNode();
475         }
476     }
477 
478     DocumentFragmentImpl *fragment = nullptr;
479     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
480         fragment = new DocumentFragmentImpl(m_ownerDocument);
481     }
482 
483     // Simple case: the start and end containers are the same. We just grab
484     // everything >= start offset and < end offset
485     if (m_startContainer == m_endContainer) {
486         if (m_startContainer->nodeType() == Node::TEXT_NODE ||
487                 m_startContainer->nodeType() == Node::CDATA_SECTION_NODE ||
488                 m_startContainer->nodeType() == Node::COMMENT_NODE) {
489 
490             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
491                 RefPtr<CharacterDataImpl> c = static_pointer_cast<CharacterDataImpl>(m_startContainer->cloneNode(true));
492                 c->deleteData(m_endOffset, static_cast<CharacterDataImpl *>(m_startContainer)->length() - m_endOffset, exceptioncode);
493                 c->deleteData(0, m_startOffset, exceptioncode);
494                 fragment->appendChild(c.get(), exceptioncode);
495             }
496             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
497                 static_cast<CharacterDataImpl *>(m_startContainer)->deleteData(m_startOffset, m_endOffset - m_startOffset, exceptioncode);
498             }
499         } else if (m_startContainer->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {
500             // ### operate just on data ?
501         } else {
502             NodeImpl *n = m_startContainer->firstChild();
503             unsigned long i;
504             for (i = 0; n && i < m_startOffset; i++) { // skip until m_startOffset
505                 n = n->nextSibling();
506             }
507             while (n && i < m_endOffset) { // delete until m_endOffset
508                 NodeImpl *next = n->nextSibling();
509                 if (action == EXTRACT_CONTENTS) {
510                     fragment->appendChild(n, exceptioncode);    // will remove n from its parent
511                 } else if (action == CLONE_CONTENTS) {
512                     fragment->appendChild(n->cloneNode(true).get(), exceptioncode);
513                 } else {
514                     m_startContainer->removeChild(n, exceptioncode);
515                 }
516                 n = next;
517                 i++;
518             }
519         }
520         collapse(true, exceptioncode);
521         return fragment;
522     }
523 
524     // Complex case: Start and end containers are different.
525     // There are three possiblities here:
526     // 1. Start container == cmnRoot (End container must be a descendant)
527     // 2. End container == cmnRoot (Start container must be a descendant)
528     // 3. Neither is cmnRoot, they are both descendants
529     //
530     // In case 3, we grab everything after the start (up until a direct child
531     // of cmnRoot) into leftContents, and everything before the end (up until
532     // a direct child of cmnRoot) into rightContents. Then we process all
533     // cmnRoot children between leftContents and rightContents
534     //
535     // In case 1 or 2, we skip either processing of leftContents or rightContents,
536     // in which case the last lot of nodes either goes from the first or last
537     // child of cmnRoot.
538     //
539     // These are deleted, cloned, or extracted (i.e. both) depending on action.
540 
541     RefPtr<NodeImpl> leftContents = nullptr;
542     if (m_startContainer != cmnRoot) {
543         // process the left-hand side of the range, up until the last ancestor of
544         // m_startContainer before cmnRoot
545         if (m_startContainer->nodeType() == Node::TEXT_NODE ||
546                 m_startContainer->nodeType() == Node::CDATA_SECTION_NODE ||
547                 m_startContainer->nodeType() == Node::COMMENT_NODE) {
548 
549             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
550                 RefPtr<CharacterDataImpl> c = static_pointer_cast<CharacterDataImpl>(m_startContainer->cloneNode(true));
551                 c->deleteData(0, m_startOffset, exceptioncode);
552                 leftContents = c;
553             }
554             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
555                 static_cast<CharacterDataImpl *>(m_startContainer)->deleteData(
556                     m_startOffset, static_cast<CharacterDataImpl *>(m_startContainer)->length() - m_startOffset, exceptioncode);
557         } else if (m_startContainer->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {
558             // ### operate just on data ?
559             // leftContents = ...
560         } else {
561             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
562                 leftContents = m_startContainer->cloneNode(false);
563             }
564             NodeImpl *n = m_startContainer->firstChild();
565             for (unsigned long i = 0; n && i < m_startOffset; i++) { // skip until m_startOffset
566                 n = n->nextSibling();
567             }
568             while (n) { // process until end
569                 NodeImpl *next = n->nextSibling();
570                 if (action == EXTRACT_CONTENTS) {
571                     leftContents->appendChild(n, exceptioncode);    // will remove n from m_startContainer
572                 } else if (action == CLONE_CONTENTS) {
573                     leftContents->appendChild(n->cloneNode(true).get(), exceptioncode);
574                 } else {
575                     m_startContainer->removeChild(n, exceptioncode);
576                 }
577                 n = next;
578             }
579         }
580 
581         NodeImpl *leftParent = m_startContainer->parentNode();
582         NodeImpl *n = m_startContainer->nextSibling();
583         for (; leftParent != cmnRoot; leftParent = leftParent->parentNode()) {
584             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
585                 RefPtr<NodeImpl> leftContentsParent = leftParent->cloneNode(false);
586                 leftContentsParent->appendChild(leftContents.get(), exceptioncode);
587                 leftContents = leftContentsParent;
588             }
589 
590             NodeImpl *next;
591             for (; n; n = next) {
592                 next = n->nextSibling();
593                 if (action == EXTRACT_CONTENTS) {
594                     leftContents->appendChild(n, exceptioncode);    // will remove n from leftParent
595                 } else if (action == CLONE_CONTENTS) {
596                     leftContents->appendChild(n->cloneNode(true).get(), exceptioncode);
597                 } else {
598                     leftParent->removeChild(n, exceptioncode);
599                 }
600             }
601             n = leftParent->nextSibling();
602         }
603     }
604 
605     RefPtr<NodeImpl> rightContents = nullptr;
606     if (m_endContainer != cmnRoot) {
607         // delete the right-hand side of the range, up until the last ancestor of
608         // m_endContainer before cmnRoot
609         if (m_endContainer->nodeType() == Node::TEXT_NODE ||
610                 m_endContainer->nodeType() == Node::CDATA_SECTION_NODE ||
611                 m_endContainer->nodeType() == Node::COMMENT_NODE) {
612 
613             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
614                 RefPtr<CharacterDataImpl> c =
615                     static_pointer_cast<CharacterDataImpl>(m_endContainer->cloneNode(true));
616                 c->deleteData(m_endOffset, static_cast<CharacterDataImpl *>(m_endContainer)->length() - m_endOffset, exceptioncode);
617                 rightContents = c;
618             }
619             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
620                 static_cast<CharacterDataImpl *>(m_endContainer)->deleteData(0, m_endOffset, exceptioncode);
621             }
622         } else if (m_startContainer->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {
623             // ### operate just on data ?
624             // rightContents = ...
625         } else {
626             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
627                 rightContents = m_endContainer->cloneNode(false);
628             }
629             NodeImpl *n = m_endContainer->firstChild();
630             if (n && m_endOffset) {
631                 for (unsigned long i = 0; i + 1 < m_endOffset; i++) { // skip to m_endOffset
632                     NodeImpl *next = n->nextSibling();
633                     if (!next) {
634                         break;
635                     }
636                     n = next;
637                 }
638                 NodeImpl *prev;
639                 for (; n; n = prev) {
640                     prev = n->previousSibling();
641                     if (action == EXTRACT_CONTENTS) {
642                         rightContents->insertBefore(n, rightContents->firstChild(), exceptioncode);    // will remove n from its parent
643                     } else if (action == CLONE_CONTENTS) {
644                         rightContents->insertBefore(n->cloneNode(true).get(), rightContents->firstChild(), exceptioncode);
645                     } else {
646                         m_endContainer->removeChild(n, exceptioncode);
647                     }
648                 }
649             }
650         }
651 
652         NodeImpl *rightParent = m_endContainer->parentNode();
653         NodeImpl *n = m_endContainer->previousSibling();
654         for (; rightParent != cmnRoot; rightParent = rightParent->parentNode()) {
655             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
656                 RefPtr<NodeImpl> rightContentsParent = rightParent->cloneNode(false);
657                 rightContentsParent->appendChild(rightContents.get(), exceptioncode);
658                 rightContents = rightContentsParent;
659             }
660 
661             NodeImpl *prev;
662             for (; n; n = prev) {
663                 prev = n->previousSibling();
664                 if (action == EXTRACT_CONTENTS) {
665                     rightContents->insertBefore(n, rightContents->firstChild(), exceptioncode);    // will remove n from its parent
666                 } else if (action == CLONE_CONTENTS) {
667                     rightContents->insertBefore(n->cloneNode(true).get(), rightContents->firstChild(), exceptioncode);
668                 } else {
669                     rightParent->removeChild(n, exceptioncode);
670                 }
671 
672             }
673             n = rightParent->previousSibling();
674         }
675     }
676 
677     // delete all children of cmnRoot between the start and end container
678 
679     NodeImpl *processStart; // child of cmnRooot
680     if (m_startContainer == cmnRoot) {
681         unsigned long i;
682         processStart = m_startContainer->firstChild();
683         for (i = 0; i < m_startOffset; i++) {
684             processStart = processStart->nextSibling();
685         }
686     } else {
687         processStart = m_startContainer;
688         while (processStart->parentNode() != cmnRoot) {
689             processStart = processStart->parentNode();
690         }
691         processStart = processStart->nextSibling();
692     }
693     NodeImpl *processEnd; // child of cmnRooot
694     if (m_endContainer == cmnRoot) {
695         unsigned long i;
696         processEnd = m_endContainer->firstChild();
697         for (i = 0; i < m_endOffset; i++) {
698             processEnd = processEnd->nextSibling();
699         }
700     } else {
701         processEnd = m_endContainer;
702         while (processEnd->parentNode() != cmnRoot) {
703             processEnd = processEnd->parentNode();
704         }
705     }
706 
707     // Now add leftContents, stuff in between, and rightContents to the fragment
708     // (or just delete the stuff in between)
709 
710     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents) {
711         fragment->appendChild(leftContents.get(), exceptioncode);
712     }
713 
714     NodeImpl *next;
715     NodeImpl *n;
716     if (processStart) {
717         for (n = processStart; n && n != processEnd; n = next) {
718             next = n->nextSibling();
719 
720             if (action == EXTRACT_CONTENTS) {
721                 fragment->appendChild(n, exceptioncode);    // will remove from cmnRoot
722             } else if (action == CLONE_CONTENTS) {
723                 fragment->appendChild(n->cloneNode(true).get(), exceptioncode);
724             } else {
725                 cmnRoot->removeChild(n, exceptioncode);
726             }
727         }
728     }
729 
730     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents) {
731         fragment->appendChild(rightContents.get(), exceptioncode);
732     }
733 
734     // collapse to the proper position - see spec section 2.6
735     if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
736         if (!partialStart && !partialEnd) {
737             collapse(true, exceptioncode);
738         } else if (partialStart) {
739             setStartContainer(partialStart->parentNode());
740             setEndContainer(partialStart->parentNode());
741             m_startOffset = m_endOffset = partialStart->nodeIndex() + 1;
742         } else if (partialEnd) {
743             setStartContainer(partialEnd->parentNode());
744             setEndContainer(partialEnd->parentNode());
745             m_startOffset = m_endOffset = partialEnd->nodeIndex();
746         }
747     }
748     return fragment;
749 }
750 
extractContents(int & exceptioncode)751 DocumentFragmentImpl *RangeImpl::extractContents(int &exceptioncode)
752 {
753     if (m_detached) {
754         exceptioncode = DOMException::INVALID_STATE_ERR;
755         return nullptr;
756     }
757 
758     checkDeleteExtract(exceptioncode);
759     if (exceptioncode) {
760         return nullptr;
761     }
762 
763     return processContents(EXTRACT_CONTENTS, exceptioncode);
764 }
765 
cloneContents(int & exceptioncode)766 DocumentFragmentImpl *RangeImpl::cloneContents(int &exceptioncode)
767 {
768     if (m_detached) {
769         exceptioncode = DOMException::INVALID_STATE_ERR;
770         return nullptr;
771     }
772 
773     return processContents(CLONE_CONTENTS, exceptioncode);
774 }
775 
insertNode(NodeImpl * newNode,int & exceptioncode)776 void RangeImpl::insertNode(NodeImpl *newNode, int &exceptioncode)
777 {
778     if (m_detached) {
779         exceptioncode = DOMException::INVALID_STATE_ERR;
780         return;
781     }
782 
783     if (!newNode) {
784         exceptioncode = DOMException::NOT_FOUND_ERR;
785         return;
786     }
787 
788     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
789     // the Range is read-only.
790     NodeImpl *n = m_startContainer;
791     while (n && !n->isReadOnly()) {
792         n = n->parentNode();
793     }
794     if (n) {
795         exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
796         return;
797     }
798 
799     n = m_endContainer;
800     while (n && !n->isReadOnly()) {
801         n = n->parentNode();
802     }
803     if (n) {
804         exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
805         return;
806     }
807 
808     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
809     // not created from the same document.
810     if (newNode->document() != m_startContainer->document()) {
811         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
812         return;
813     }
814 
815     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
816     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
817 
818     // an extra one here - if a text node is going to split, it must have a parent to insert into
819     if (m_startContainer->nodeType() == Node::TEXT_NODE && !m_startContainer->parentNode()) {
820         exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
821         return;
822     }
823 
824     // In the case where the container is a text node, we check against the container's parent, because
825     // text nodes get split up upon insertion.
826     NodeImpl *checkAgainst;
827     if (m_startContainer->nodeType() == Node::TEXT_NODE) {
828         checkAgainst = m_startContainer->parentNode();
829     } else {
830         checkAgainst = m_startContainer;
831     }
832 
833     if (newNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE) {
834         // check each child node, not the DocumentFragment itself
835         NodeImpl *c;
836         for (c = newNode->firstChild(); c; c = c->nextSibling()) {
837             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
838                 exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
839                 return;
840             }
841         }
842     } else {
843         if (!checkAgainst->childTypeAllowed(newNode->nodeType())) {
844             exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
845             return;
846         }
847     }
848 
849     for (n = m_startContainer; n; n = n->parentNode()) {
850         if (n == newNode) {
851             exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
852             return;
853         }
854     }
855 
856     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, or Document node.
857     if (newNode->nodeType() == Node::ATTRIBUTE_NODE ||
858             newNode->nodeType() == Node::ENTITY_NODE ||
859             newNode->nodeType() == Node::NOTATION_NODE ||
860             newNode->nodeType() == Node::DOCUMENT_NODE) {
861         exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
862         return;
863     }
864 
865     long endOffsetDelta = 0;
866     if (m_startContainer->nodeType() == Node::TEXT_NODE ||
867             m_startContainer->nodeType() == Node::CDATA_SECTION_NODE) {
868         // ### leaks on exceptions
869         TextImpl *newText = static_cast<TextImpl *>(m_startContainer)->splitText(m_startOffset, exceptioncode);
870         if (exceptioncode) {
871             return;
872         }
873 
874         if (m_startContainer == m_endContainer) {
875             endOffsetDelta = -(long)m_startOffset;
876             setEndContainer(newText);
877             // ### what about border cases where start or end are at
878             // ### the margins of the text?
879         }
880 
881         m_startContainer->parentNode()->insertBefore(newNode, newText, exceptioncode);
882         if (exceptioncode) {
883             return;
884         }
885     } else {
886         if (m_startContainer == m_endContainer) {
887             bool isFragment = newNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE;
888             endOffsetDelta = isFragment ? newNode->childNodeCount() : 1;
889         }
890 
891         m_startContainer->insertBefore(newNode, m_startContainer->childNode(m_startOffset), exceptioncode);
892         if (exceptioncode) {
893             return;
894         }
895     }
896     m_endOffset += endOffsetDelta;
897 }
898 
toString(int & exceptioncode)899 DOMString RangeImpl::toString(int &exceptioncode)
900 {
901     if (m_detached) {
902         exceptioncode = DOMException::INVALID_STATE_ERR;
903         return DOMString();
904     }
905 
906     DOMString text = "";
907     NodeImpl *n = m_startContainer;
908 
909     /* This function converts a dom range to the plain text string that the user would see in this
910      * portion of rendered html.
911      *
912      * There are several ways ranges can be used.
913      *
914      * The simplest is the start and endContainer is a text node.  The start and end offset is the
915      * number of characters into the text to remove/truncate.
916      *
917      * The next case is the start and endContainer is, well, a container, such a P tag or DIV tag.
918      * In this case the start and end offset is the number of children into the container to start
919      * from and end at.
920      *
921      * The other cases are different arrangements of the first two.
922      *
923      * pseudo code:
924      *
925      * if start container is not text:
926      *     count through the children to find where we start (m_startOffset children)
927      *
928      * loop from the start position:
929      *     if the current node is text, add the text to our variable 'text', truncating/removing if at the end/start.
930      *
931      *     if the node has children, step to the first child.
932      *     if the node has no children but does have siblings, step to the next sibling
933      *     until we find a sibling, go to next the parent but:
934      *         make sure this sibling isn't past the end of where we are supposed to go. (position > endOffset and the parent is the endContainer)
935      *
936      */
937 
938     if (m_startContainer == m_endContainer && m_startOffset >= m_endOffset) {
939         return text;
940     }
941 
942     if (n->firstChild()) {
943         n = n->firstChild();
944         int current_offset = m_startOffset;
945         while (current_offset-- && n) {
946             n = n->nextSibling();
947         }
948     }
949 
950     while (n) {
951         if (n == m_endContainer && m_endOffset == 0) {
952             break;
953         }
954         if (n->nodeType() == DOM::Node::TEXT_NODE ||
955                 n->nodeType() == DOM::Node::CDATA_SECTION_NODE) {
956 
957             DOMString str = static_cast<TextImpl *>(n)->string();
958             if (n == m_endContainer || n == m_startContainer) {
959                 str = str.copy();    //copy if we are going to modify.
960             }
961 
962             if (n == m_endContainer) {
963                 str.truncate(m_endOffset);
964             }
965             if (n == m_startContainer) {
966                 str.remove(0, m_startOffset);
967             }
968             text += str;
969             if (n == m_endContainer) {
970                 break;
971             }
972         }
973 
974         NodeImpl *next = n->firstChild();
975         if (!next) {
976             next = n->nextSibling();
977         }
978 
979         while (!next && n->parentNode()) {
980             if (n == m_endContainer) {
981                 return text;
982             }
983             n = n->parentNode();
984             if (n == m_endContainer) {
985                 return text;
986             }
987             next = n->nextSibling();
988         }
989 
990         if (n->parentNode() == m_endContainer) {
991             if (!next) {
992                 break;
993             }
994             unsigned long current_offset = 0;
995             NodeImpl *it = n;
996             while ((it = it->previousSibling())) {
997                 ++current_offset;
998             }
999             if (current_offset >= m_endOffset) {
1000                 break;
1001             }
1002         }
1003 
1004         n = next;
1005     }
1006     return text;
1007 }
1008 
toHTML(int & exceptioncode)1009 DOMString RangeImpl::toHTML(int &exceptioncode)
1010 {
1011     bool hasHtmlTag = false;
1012     bool hasBodyTag = false;
1013     //FIXME:  What is this section of code below exactly?  Do I want it here?
1014     if (m_detached) {
1015         exceptioncode = DOMException::INVALID_STATE_ERR;
1016         return DOMString();
1017     }
1018     DOMString text = "";
1019     NodeImpl *n = m_startContainer;
1020     int num_tables = 0;
1021     bool in_li = false; //whether we have an li in the text, without an ol/ul
1022     int depth_difference = 0;
1023     int lowest_depth_difference = 0;
1024 
1025     if (m_startContainer == m_endContainer && m_startOffset >= m_endOffset) {
1026         return text;
1027     }
1028 
1029     while (n) {
1030         /* First, we could have an tag <tagname key=value>otherstuff</tagname> */
1031         if (n->nodeType() == DOM::Node::ELEMENT_NODE) {
1032             int elementId = static_cast<ElementImpl *>(n)->id();
1033             if (elementId == ID_TABLE) {
1034                 num_tables++;
1035             }
1036             if (elementId == ID_BODY) {
1037                 hasBodyTag = true;
1038             }
1039             if (elementId == ID_HTML) {
1040                 hasHtmlTag = true;
1041             }
1042             if (elementId == ID_LI) {
1043                 in_li = true;
1044             }
1045             if (num_tables == 0 && (elementId == ID_TD || elementId == ID_TR || elementId == ID_TH || elementId == ID_TBODY || elementId == ID_TFOOT || elementId == ID_THEAD)) {
1046                 num_tables++;
1047             }
1048             if (!(!n->hasChildNodes() && (elementId == ID_H1 || elementId == ID_H2 || elementId == ID_H3 || elementId == ID_H4 || elementId == ID_H5))) { //Don't add <h1/>  etc.  Just skip these nodes just to make the output html a bit nicer.
1049                 text += static_cast<ElementImpl *>(n)->openTagStartToString(true /*safely expand img urls*/); // adds "<tagname key=value"
1050                 if (n->hasChildNodes()) {
1051                     depth_difference++;
1052                     text += ">";
1053                 } else {
1054                     text += "/>";
1055                 }
1056             }
1057         } else if (n->nodeType() == DOM::Node::TEXT_NODE ||
1058                    n->nodeType() == DOM::Node::CDATA_SECTION_NODE) {
1059             if (n->nodeType() == DOM::Node::CDATA_SECTION_NODE) {
1060                 text += "<![CDATA[ ";
1061             }
1062             long long startOffset = (n == m_startContainer) ? (long long)m_startOffset : -1;
1063             long long endOffset = (n == m_endContainer) ? (long long) m_endOffset : -1;
1064             text += static_cast<TextImpl *>(n)->toString(startOffset, endOffset); //Note this should always work since CDataImpl inherits TextImpl
1065             if (n->nodeType() == DOM::Node::CDATA_SECTION_NODE) {
1066                 text += " ]]>";
1067             }
1068             if (n == m_endContainer) {
1069                 break;
1070             }
1071         }
1072         if (n->parentNode() == m_endContainer && !n->nextSibling()) {
1073             break;
1074         }
1075 
1076         //if (n == m_endContainer) break;
1077         NodeImpl *next = n->firstChild();
1078         if (next) {
1079             if (n == m_startContainer) {
1080                 //This is the start of our selection, so we have to move to where we have started selecting.
1081                 //For example, if 'n' is "hello <img src='hello.png'> how are you? <img src='goodbye.png'>"
1082                 //then this has four children.  If our selection started on the image, then we need to start from there.
1083                 unsigned long current_offset = 0;
1084                 while (current_offset < m_startOffset && next) {
1085                     next = next->nextSibling();
1086                     ++current_offset;
1087                 }
1088             }
1089         } else {
1090             next = n->nextSibling();
1091 
1092             if (n->parentNode() == m_endContainer) {
1093                 unsigned long current_offset = 1;
1094                 NodeImpl *it = n;
1095                 while ((it = it->previousSibling())) {
1096                     ++current_offset;
1097                 }
1098 
1099                 if (current_offset >= m_endOffset) {
1100                     break;
1101                 }
1102             }
1103         }
1104 
1105         while (!next && n->parentNode()) {
1106             n = n->parentNode();
1107             if (n->nodeType() == DOM::Node::ELEMENT_NODE) {
1108                 text += "</";
1109                 text += static_cast<ElementImpl *>(n)->nonCaseFoldedTagName();
1110                 int elementId = static_cast<ElementImpl *>(n)->id();
1111                 if (elementId == ID_TABLE) {
1112                     num_tables--;
1113                 }
1114                 depth_difference--;
1115                 if (lowest_depth_difference > depth_difference) {
1116                     lowest_depth_difference = depth_difference;
1117                 }
1118                 if (num_tables == 0 && (elementId == ID_TD || elementId == ID_TR || elementId == ID_TH || elementId == ID_TBODY || elementId == ID_TFOOT || elementId == ID_THEAD)) {
1119                     num_tables--;
1120                 }
1121                 if (elementId == ID_OL || elementId == ID_UL) {
1122                     in_li = false;
1123                 }
1124                 text += ">";
1125             }
1126             next = n->nextSibling();
1127         }
1128         n = next;
1129     }
1130 
1131     //We have the html in the selection.  But now we need to properly add the opening and closing tags.
1132     //For example say we have:   "Hello <b>Mr. John</b> How are you?"  and we select "John" or even
1133     //"John</b> How"  and copy.  We want to return "<b>John</b>" and "<b>John</b> How" respectively
1134 
1135     //To do this, we need to go up the tree from the start, and prepend those tags.
1136     //Imagine our selection was this:
1137     //
1138     //  hello</b></p><p>there
1139     //
1140     //  The difference in depths between the start and end is -1, and the lowest depth
1141     //  difference from the starting point is -2
1142     //
1143     //  So from the start of the selection, we want to go down to the lowest_depth_difference
1144     //  and prepend those tags.  (<p><b>)
1145     //
1146     //  From the end of the selection, we want to also go down to the lowest_depth_difference.
1147     //  We know the depth of the end of the selection - i.e. depth_difference.
1148     //
1149     //
1150     n = m_startContainer;
1151     int startdepth = 0; //by definition - we are counting from zero.
1152     while ((n = n->parentNode()) && startdepth > lowest_depth_difference) {
1153         if (n->nodeType() == DOM::Node::ELEMENT_NODE) { //This should always be true.. right?
1154             switch (static_cast<ElementImpl *>(n)->id()) {
1155             case ID_TABLE:
1156                 num_tables--;
1157                 break;
1158             case ID_BODY:
1159                 hasBodyTag = true;
1160                 break;
1161             case ID_HTML:
1162                 hasHtmlTag = true;
1163                 break;
1164             case ID_LI:
1165                 in_li = true;
1166                 break;
1167             }
1168             text = static_cast<ElementImpl *>(n)->openTagStartToString(true /*expand img urls*/) + DOMString(">") + text; // prepends "<tagname key=value>"
1169         }
1170         startdepth--;
1171     }
1172     n = m_endContainer;
1173     while (depth_difference > lowest_depth_difference && (n = n->parentNode())) {
1174         if (n->nodeType() == DOM::Node::ELEMENT_NODE) { //This should always be true.. right?
1175             switch (static_cast<ElementImpl *>(n)->id()) {
1176             case ID_TABLE:
1177                 num_tables++;
1178                 break;
1179             case ID_OL:
1180             case ID_UL:
1181                 in_li = false;
1182                 break;
1183             }
1184             text += "</";
1185             text += static_cast<ElementImpl *>(n)->nonCaseFoldedTagName();
1186             text += ">";
1187         }
1188         depth_difference--;
1189     }
1190 
1191     // Now our text string is the same depth on both sides, with nothing lower (in other words all the
1192     // tags in it match up.)  This also means that the end value for n in the first loop is a sibling of the
1193     // end value for n in the second loop.
1194     //
1195     // We now need to go down the tree, and for certain tags, add them in on both ends of the text.
1196     // For example, if have:  "<b>hello</b>"  and we select "ll", then we want to go down the tree and
1197     // add "<b>" and "</b>" to it, to produce "<b>ll</b>".
1198     //
1199     // I just guessed at which tags you'd want to keep (bold, italic etc) and which you wouldn't (tables etc).
1200     // It's just wild guessing.  feel free to change.
1201     //
1202     // Note we can carry on with the value of n
1203     if (n) {
1204         while ((n = n->parentNode())) {
1205             if (n->nodeType() == DOM::Node::ELEMENT_NODE) { //This should always be true.. right?
1206                 int elementId = static_cast<ElementImpl *>(n)->id();
1207                 switch (elementId) {
1208                 case ID_TABLE:
1209                 case ID_TD:
1210                 case ID_TR:
1211                 case ID_TH:
1212                 case ID_TBODY:
1213                 case ID_TFOOT:
1214                 case ID_THEAD:
1215                     if (num_tables > 0) {
1216                         if (elementId == ID_TABLE) {
1217                             num_tables--;
1218                         }
1219                         text = static_cast<ElementImpl *>(n)->openTagStartToString(true /*expand img urls*/) + DOMString(">") + text;
1220                         text += "</";
1221                         text += static_cast<ElementImpl *>(n)->nonCaseFoldedTagName();
1222                         text += ">";
1223 
1224                     }
1225                     break;
1226 
1227                 case ID_LI:
1228                     if (!in_li) {
1229                         break;
1230                     }
1231                     text = static_cast<ElementImpl *>(n)->openTagStartToString(true /*expand img urls*/) + DOMString(">") + text;
1232                     text += "</";
1233                     text += static_cast<ElementImpl *>(n)->nonCaseFoldedTagName();
1234                     text += ">";
1235                     break;
1236 
1237                 case ID_UL:
1238                 case ID_OL:
1239                     if (!in_li) {
1240                         break;
1241                     }
1242                     in_li = false;
1243                 case ID_B:
1244                 case ID_I:
1245                 case ID_U:
1246                 case ID_FONT:
1247                 case ID_S:
1248                 case ID_STRONG:
1249                 case ID_STRIKE:
1250                 case ID_DEL:
1251                 case ID_A:
1252                 case ID_H1:
1253                 case ID_H2:
1254                 case ID_H3:
1255                 case ID_H4:
1256                 case ID_H5:
1257                     //should small, etc be here?   so hard to decide.  this is such a hack :(
1258                     //There's probably tons of others you'd want here.
1259                     text = static_cast<ElementImpl *>(n)->openTagStartToString(true /*expand img urls*/) + DOMString(">") + text;
1260                     text += "</";
1261                     text += static_cast<ElementImpl *>(n)->nonCaseFoldedTagName();
1262                     text += ">";
1263                     break;
1264                 }
1265             }
1266         }
1267     }
1268 
1269     if (!hasBodyTag) {
1270         text = DOMString("<body>") + text + DOMString("</body>");
1271     } else if (!hasHtmlTag) {
1272         text = DOMString("<html xmlns=\"http://www.w3.org/1999/xhtml\">\n"
1273                          "<head>\n"
1274                          "<meta http-equiv=\"Content-Type\" content=\"text/html; charset=UTF-8\" />\n"
1275                          "<meta name=\"Generator\" content=\"KHTML, the KDE Web Page Viewer\" />\n"
1276                          "</head>\n") +
1277                text +
1278                DOMString("</html>");
1279     }
1280     text = DOMString("<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Strict//EN\" \"DTD/xhtml1-strict.dtd\">\n") + text;
1281 
1282     return text;
1283 
1284 }
1285 
createContextualFragment(const DOMString & html,int & exceptioncode)1286 DocumentFragment RangeImpl::createContextualFragment(const DOMString &html, int &exceptioncode)
1287 {
1288     if (m_detached) {
1289         exceptioncode = DOMException::INVALID_STATE_ERR;
1290         return DocumentFragment();
1291     }
1292 
1293     DOM::NodeImpl *start = m_startContainer;
1294 
1295     if (start->isDocumentNode()) {
1296         start = static_cast<DocumentImpl *>(start)->documentElement();
1297     }
1298 
1299     if (!start || !start->isHTMLElement()) {
1300         exceptioncode = DOMException::NOT_SUPPORTED_ERR;
1301         return DocumentFragment();
1302     }
1303 
1304     HTMLElementImpl *e = static_cast<HTMLElementImpl *>(start);
1305     DocumentFragment fragment = e->createContextualFragment(html);
1306     if (fragment.isNull()) {
1307         exceptioncode = DOMException::NOT_SUPPORTED_ERR;
1308         return DocumentFragment();
1309     }
1310 
1311     return fragment;
1312 }
1313 
detach(int & exceptioncode)1314 void RangeImpl::detach(int &exceptioncode)
1315 {
1316     if (m_detached) {
1317         exceptioncode = DOMException::INVALID_STATE_ERR;
1318         return;
1319     }
1320 
1321     if (m_startContainer) {
1322         m_startContainer->deref();
1323     }
1324     m_startContainer = nullptr;
1325     if (m_endContainer) {
1326         m_endContainer->deref();
1327     }
1328     m_endContainer = nullptr;
1329     m_detached = true;
1330 }
1331 
isDetached() const1332 bool RangeImpl::isDetached() const
1333 {
1334     return m_detached;
1335 }
1336 
checkNodeWOffset(NodeImpl * n,int offset,int & exceptioncode) const1337 void RangeImpl::checkNodeWOffset(NodeImpl *n, int offset, int &exceptioncode) const
1338 {
1339     if (offset < 0) {
1340         exceptioncode = DOMException::INDEX_SIZE_ERR;
1341     }
1342 
1343     switch (n->nodeType()) {
1344     case Node::ENTITY_NODE:
1345     case Node::NOTATION_NODE:
1346     case Node::DOCUMENT_TYPE_NODE:
1347         exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
1348         break;
1349     case Node::TEXT_NODE:
1350     case Node::COMMENT_NODE:
1351     case Node::CDATA_SECTION_NODE:
1352         if ((unsigned long)offset > static_cast<CharacterDataImpl *>(n)->length()) {
1353             exceptioncode = DOMException::INDEX_SIZE_ERR;
1354         }
1355         break;
1356     case Node::PROCESSING_INSTRUCTION_NODE:
1357         // ### are we supposed to check with just data or the whole contents?
1358         if ((unsigned long)offset > static_cast<ProcessingInstructionImpl *>(n)->data().length()) {
1359             exceptioncode = DOMException::INDEX_SIZE_ERR;
1360         }
1361         break;
1362     default:
1363         if ((unsigned long)offset > n->childNodeCount()) {
1364             exceptioncode = DOMException::INDEX_SIZE_ERR;
1365         }
1366         break;
1367     }
1368 }
1369 
checkNodeBA(NodeImpl * n,int & exceptioncode) const1370 void RangeImpl::checkNodeBA(NodeImpl *n, int &exceptioncode) const
1371 {
1372     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1373     // Attr, Document or DocumentFragment node or if refNode is a Document,
1374     // DocumentFragment, Attr, Entity, or Notation node.
1375     NodeImpl *root = n;
1376     while (root->parentNode()) {
1377         root = root->parentNode();
1378     }
1379     if (!(root->nodeType() == Node::ATTRIBUTE_NODE ||
1380             root->nodeType() == Node::DOCUMENT_NODE ||
1381             root->nodeType() == Node::DOCUMENT_FRAGMENT_NODE)) {
1382         exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
1383         return;
1384     }
1385 
1386     if (n->nodeType() == Node::DOCUMENT_NODE ||
1387             n->nodeType() == Node::DOCUMENT_FRAGMENT_NODE ||
1388             n->nodeType() == Node::ATTRIBUTE_NODE ||
1389             n->nodeType() == Node::ENTITY_NODE ||
1390             n->nodeType() == Node::NOTATION_NODE) {
1391         exceptioncode = RangeException::INVALID_NODE_TYPE_ERR  + RangeException::_EXCEPTION_OFFSET;
1392     }
1393 
1394 }
1395 
cloneRange(int & exceptioncode)1396 RangeImpl *RangeImpl::cloneRange(int &exceptioncode)
1397 {
1398     if (m_detached) {
1399         exceptioncode = DOMException::INVALID_STATE_ERR;
1400         return nullptr;
1401     }
1402 
1403     return new RangeImpl(m_ownerDocument, m_startContainer, m_startOffset, m_endContainer, m_endOffset);
1404 }
1405 
setStartAfter(NodeImpl * refNode,int & exceptioncode)1406 void RangeImpl::setStartAfter(NodeImpl *refNode, int &exceptioncode)
1407 {
1408     if (m_detached) {
1409         exceptioncode = DOMException::INVALID_STATE_ERR;
1410         return;
1411     }
1412 
1413     if (!refNode) {
1414         exceptioncode = DOMException::NOT_FOUND_ERR;
1415         return;
1416     }
1417 
1418     if (refNode->document() != m_ownerDocument) {
1419         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
1420         return;
1421     }
1422 
1423     checkNodeBA(refNode, exceptioncode);
1424     if (exceptioncode) {
1425         return;
1426     }
1427 
1428     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, exceptioncode);
1429 }
1430 
setEndBefore(NodeImpl * refNode,int & exceptioncode)1431 void RangeImpl::setEndBefore(NodeImpl *refNode, int &exceptioncode)
1432 {
1433     if (m_detached) {
1434         exceptioncode = DOMException::INVALID_STATE_ERR;
1435         return;
1436     }
1437 
1438     if (!refNode) {
1439         exceptioncode = DOMException::NOT_FOUND_ERR;
1440         return;
1441     }
1442 
1443     if (refNode->document() != m_ownerDocument) {
1444         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
1445         return;
1446     }
1447 
1448     checkNodeBA(refNode, exceptioncode);
1449     if (exceptioncode) {
1450         return;
1451     }
1452 
1453     setEnd(refNode->parentNode(), refNode->nodeIndex(), exceptioncode);
1454 }
1455 
setEndAfter(NodeImpl * refNode,int & exceptioncode)1456 void RangeImpl::setEndAfter(NodeImpl *refNode, int &exceptioncode)
1457 {
1458     if (m_detached) {
1459         exceptioncode = DOMException::INVALID_STATE_ERR;
1460         return;
1461     }
1462 
1463     if (!refNode) {
1464         exceptioncode = DOMException::NOT_FOUND_ERR;
1465         return;
1466     }
1467 
1468     if (refNode->document() != m_ownerDocument) {
1469         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
1470         return;
1471     }
1472 
1473     checkNodeBA(refNode, exceptioncode);
1474     if (exceptioncode) {
1475         return;
1476     }
1477 
1478     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, exceptioncode);
1479 
1480 }
1481 
selectNode(NodeImpl * refNode,int & exceptioncode)1482 void RangeImpl::selectNode(NodeImpl *refNode, int &exceptioncode)
1483 {
1484     if (m_detached) {
1485         exceptioncode = DOMException::INVALID_STATE_ERR;
1486         return;
1487     }
1488 
1489     if (!refNode) {
1490         exceptioncode = DOMException::NOT_FOUND_ERR;
1491         return;
1492     }
1493 
1494     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1495     // DocumentType node or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation
1496     // node.
1497     NodeImpl *anc;
1498     for (anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1499         if (anc->nodeType() == Node::ENTITY_NODE ||
1500                 anc->nodeType() == Node::NOTATION_NODE ||
1501                 anc->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1502 
1503             exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
1504             return;
1505         }
1506     }
1507 
1508     if (refNode->nodeType() == Node::DOCUMENT_NODE ||
1509             refNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE ||
1510             refNode->nodeType() == Node::ATTRIBUTE_NODE ||
1511             refNode->nodeType() == Node::ENTITY_NODE ||
1512             refNode->nodeType() == Node::NOTATION_NODE) {
1513 
1514         exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
1515         return;
1516     }
1517 
1518     setStartBefore(refNode, exceptioncode);
1519     if (exceptioncode) {
1520         return;
1521     }
1522     setEndAfter(refNode, exceptioncode);
1523 }
1524 
selectNodeContents(NodeImpl * refNode,int & exceptioncode)1525 void RangeImpl::selectNodeContents(NodeImpl *refNode, int &exceptioncode)
1526 {
1527     if (m_detached) {
1528         exceptioncode = DOMException::INVALID_STATE_ERR;
1529         return;
1530     }
1531 
1532     if (!refNode) {
1533         exceptioncode = DOMException::NOT_FOUND_ERR;
1534         return;
1535     }
1536 
1537     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1538     // or DocumentType node.
1539     NodeImpl *n;
1540     for (n = refNode; n; n = n->parentNode()) {
1541         if (n->nodeType() == Node::ENTITY_NODE ||
1542                 n->nodeType() == Node::NOTATION_NODE ||
1543                 n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1544 
1545             exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
1546             return;
1547         }
1548     }
1549 
1550     setStartContainer(refNode);
1551     m_startOffset = 0;
1552     setEndContainer(refNode);
1553     m_endOffset = maxEndOffset();
1554 }
1555 
surroundContents(NodeImpl * newParent,int & exceptioncode)1556 void RangeImpl::surroundContents(NodeImpl *newParent, int &exceptioncode)
1557 {
1558     if (m_detached) {
1559         exceptioncode = DOMException::INVALID_STATE_ERR;
1560         return;
1561     }
1562 
1563     if (!newParent) {
1564         exceptioncode = DOMException::NOT_FOUND_ERR;
1565         return;
1566     }
1567 
1568     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1569     // Document, or DocumentFragment node.
1570     if (newParent->nodeType() == Node::ATTRIBUTE_NODE ||
1571             newParent->nodeType() == Node::ENTITY_NODE ||
1572             newParent->nodeType() == Node::NOTATION_NODE ||
1573             newParent->nodeType() == Node::DOCUMENT_TYPE_NODE ||
1574             newParent->nodeType() == Node::DOCUMENT_NODE ||
1575             newParent->nodeType() == Node::DOCUMENT_FRAGMENT_NODE) {
1576         exceptioncode = RangeException::INVALID_NODE_TYPE_ERR + RangeException::_EXCEPTION_OFFSET;
1577         return;
1578     }
1579 
1580     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1581     // the Range is read-only.
1582     if (readOnly()) {
1583         exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
1584         return;
1585     }
1586 
1587     NodeImpl *n = m_startContainer;
1588     while (n && !n->isReadOnly()) {
1589         n = n->parentNode();
1590     }
1591     if (n) {
1592         exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
1593         return;
1594     }
1595 
1596     n = m_endContainer;
1597     while (n && !n->isReadOnly()) {
1598         n = n->parentNode();
1599     }
1600     if (n) {
1601         exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
1602         return;
1603     }
1604 
1605     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
1606     // not created from the same document.
1607     if (newParent->document() != m_startContainer->document()) {
1608         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
1609         return;
1610     }
1611 
1612     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
1613     // does not allow children of the type of newParent or if newParent is an ancestor of the container
1614     // or if node would end up with a child node of a type not allowed by the type of node.
1615 
1616     // If m_startContainer is a character data node, it will be split and it will be its parent that will
1617     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1618     // although this will fail below for another reason).
1619 
1620     NodeImpl *parentOfNewParent = m_startContainer;
1621 
1622     if (parentOfNewParent->offsetInCharacters()) {
1623         parentOfNewParent = parentOfNewParent->parentNode();
1624     }
1625 
1626     if (!parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1627         exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
1628         return;
1629     }
1630 
1631     for (n = m_startContainer; n; n = n->parentNode()) {
1632         if (n == newParent) {
1633             exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
1634             return;
1635         }
1636     }
1637 
1638     // ### check if node would end up with a child node of a type not allowed by the type of node
1639 
1640     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-text node.
1641     if (m_startContainer->nodeType() != Node::TEXT_NODE &&
1642             m_startContainer->nodeType() != Node::CDATA_SECTION_NODE) {
1643 
1644         if (m_startOffset > 0 && m_startOffset < maxStartOffset()) {
1645             exceptioncode = RangeException::BAD_BOUNDARYPOINTS_ERR + RangeException::_EXCEPTION_OFFSET;
1646             return;
1647         }
1648     }
1649 
1650     if (m_endContainer->nodeType() != Node::TEXT_NODE &&
1651             m_endContainer->nodeType() != Node::CDATA_SECTION_NODE) {
1652 
1653         if (m_endOffset > 0 && m_endOffset < maxEndOffset()) {
1654             exceptioncode = RangeException::BAD_BOUNDARYPOINTS_ERR + RangeException::_EXCEPTION_OFFSET;
1655             return;
1656         }
1657     }
1658 
1659     while (newParent->firstChild()) {
1660         newParent->removeChild(newParent->firstChild(), exceptioncode);
1661         if (exceptioncode) {
1662             return;
1663         }
1664     }
1665     DocumentFragmentImpl *fragment = extractContents(exceptioncode);
1666     if (exceptioncode) {
1667         return;
1668     }
1669     insertNode(newParent, exceptioncode);
1670     if (exceptioncode) {
1671         return;
1672     }
1673     newParent->appendChild(fragment, exceptioncode);
1674     if (exceptioncode) {
1675         return;
1676     }
1677     selectNode(newParent, exceptioncode);
1678 }
1679 
maxStartOffset() const1680 unsigned long RangeImpl::maxStartOffset() const
1681 {
1682     if (!m_startContainer) {
1683         return 0;
1684     }
1685     if (!m_startContainer->offsetInCharacters()) {
1686         return m_startContainer->childNodeCount();
1687     }
1688     return m_startContainer->maxCharacterOffset();
1689 }
1690 
maxEndOffset() const1691 unsigned long RangeImpl::maxEndOffset() const
1692 {
1693     if (!m_endContainer) {
1694         return 0;
1695     }
1696     if (!m_endContainer->offsetInCharacters()) {
1697         return m_endContainer->childNodeCount();
1698     }
1699     return m_endContainer->maxCharacterOffset();
1700 }
1701 
setStartBefore(NodeImpl * refNode,int & exceptioncode)1702 void RangeImpl::setStartBefore(NodeImpl *refNode, int &exceptioncode)
1703 {
1704     if (m_detached) {
1705         exceptioncode = DOMException::INVALID_STATE_ERR;
1706         return;
1707     }
1708 
1709     if (!refNode) {
1710         exceptioncode = DOMException::NOT_FOUND_ERR;
1711         return;
1712     }
1713 
1714     if (refNode->document() != m_ownerDocument) {
1715         exceptioncode = DOMException::WRONG_DOCUMENT_ERR;
1716         return;
1717     }
1718 
1719     checkNodeBA(refNode, exceptioncode);
1720     if (exceptioncode) {
1721         return;
1722     }
1723 
1724     setStart(refNode->parentNode(), refNode->nodeIndex(), exceptioncode);
1725 }
1726 
setStartContainer(NodeImpl * _startContainer)1727 void RangeImpl::setStartContainer(NodeImpl *_startContainer)
1728 {
1729     if (m_startContainer == _startContainer) {
1730         return;
1731     }
1732 
1733     if (m_startContainer) {
1734         m_startContainer->deref();
1735     }
1736     m_startContainer = _startContainer;
1737     if (m_startContainer) {
1738         m_startContainer->ref();
1739     }
1740 }
1741 
setEndContainer(NodeImpl * _endContainer)1742 void RangeImpl::setEndContainer(NodeImpl *_endContainer)
1743 {
1744     if (m_endContainer == _endContainer) {
1745         return;
1746     }
1747 
1748     if (m_endContainer) {
1749         m_endContainer->deref();
1750     }
1751     m_endContainer = _endContainer;
1752     if (m_endContainer) {
1753         m_endContainer->ref();
1754     }
1755 }
1756 
checkDeleteExtract(int & exceptioncode)1757 void RangeImpl::checkDeleteExtract(int &exceptioncode)
1758 {
1759 
1760     NodeImpl *start;
1761     if (m_startContainer->nodeType() != Node::TEXT_NODE &&
1762             m_startContainer->nodeType() != Node::CDATA_SECTION_NODE &&
1763             m_startContainer->nodeType() != Node::COMMENT_NODE &&
1764             m_startContainer->nodeType() != Node::PROCESSING_INSTRUCTION_NODE) {
1765 
1766         start = m_startContainer->childNode(m_startOffset);
1767         if (!start) {
1768             if (m_startContainer->lastChild()) {
1769                 start = m_startContainer->lastChild()->traverseNextNode();
1770             } else {
1771                 start = m_startContainer->traverseNextNode();
1772             }
1773         }
1774     } else {
1775         start = m_startContainer;
1776     }
1777 
1778     NodeImpl *end;
1779     if (m_endContainer->nodeType() != Node::TEXT_NODE &&
1780             m_endContainer->nodeType() != Node::CDATA_SECTION_NODE &&
1781             m_endContainer->nodeType() != Node::COMMENT_NODE &&
1782             m_endContainer->nodeType() != Node::PROCESSING_INSTRUCTION_NODE) {
1783 
1784         end = m_endContainer->childNode(m_endOffset);
1785         if (!end) {
1786             if (m_endContainer->lastChild()) {
1787                 end = m_endContainer->lastChild()->traverseNextNode();
1788             } else {
1789                 end = m_endContainer->traverseNextNode();
1790             }
1791         }
1792     } else {
1793         end = m_endContainer;
1794     }
1795 
1796     NodeImpl *n;
1797     for (n = start; n && n != end; n = n->traverseNextNode()) {
1798         if (n->isReadOnly()) {
1799             exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
1800             return;
1801         }
1802         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) { // ### is this for only directly under the DF, or anywhere?
1803             exceptioncode = DOMException::HIERARCHY_REQUEST_ERR;
1804             return;
1805         }
1806     }
1807 
1808     if (containedByReadOnly()) {
1809         exceptioncode = DOMException::NO_MODIFICATION_ALLOWED_ERR;
1810         return;
1811     }
1812 }
1813 
containedByReadOnly()1814 bool RangeImpl::containedByReadOnly()
1815 {
1816     NodeImpl *n;
1817     for (n = m_startContainer; n; n = n->parentNode()) {
1818         if (n->isReadOnly()) {
1819             return true;
1820         }
1821     }
1822     for (n = m_endContainer; n; n = n->parentNode()) {
1823         if (n->isReadOnly()) {
1824             return true;
1825         }
1826     }
1827     return false;
1828 }
1829 
1830