Reviewed by Hyatt
[WebKit-https.git] / WebCore / khtml / editing / visible_position.cpp
1 /*
2  * Copyright (C) 2004 Apple Computer, Inc.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "visible_position.h"
27
28 #include "misc/htmltags.h"
29 #include "rendering/render_text.h"
30 #include "xml/dom2_rangeimpl.h"
31
32 #if APPLE_CHANGES
33 #include "KWQAssertions.h"
34 #include "KWQLogging.h"
35 #else
36 #define ASSERT(assertion) assert(assertion)
37 #define LOG(channel, formatAndArgs...) ((void)0)
38 #endif
39
40 using DOM::CharacterDataImpl;
41 using DOM::offsetInCharacters;
42 using DOM::Position;
43 using DOM::Range;
44 using DOM::RangeImpl;
45
46 namespace khtml {
47
48 VisiblePosition::VisiblePosition(NodeImpl *node, long offset, EAffinity affinity)
49 {
50     Position pos = Position(node, offset);
51
52     // A first step toward eliminating the affinity parameter.
53     // For <br> 0, it's important not to move past the <br>.
54     if (node && node->id() == ID_BR && offset == 0)
55         affinity = UPSTREAM;
56
57     switch (affinity) {
58         case UPSTREAM:
59             initUpstream(pos);
60             break;
61         case DOWNSTREAM:
62             initDownstream(pos);
63             break;
64         default:
65             ASSERT_NOT_REACHED();
66             break;
67     }
68 }
69
70 VisiblePosition::VisiblePosition(const Position &pos, EAffinity affinity)
71 {
72     // A first step toward eliminating the affinity parameter.
73     // For <br> 0, it's important not to move past the <br>.
74     if (pos.node() && pos.node()->id() == ID_BR && pos.offset() == 0)
75         affinity = UPSTREAM;
76
77     switch (affinity) {
78         case UPSTREAM:
79             initUpstream(pos);
80             break;
81         case DOWNSTREAM:
82             initDownstream(pos);
83             break;
84         default:
85             ASSERT_NOT_REACHED();
86             break;
87     }
88 }
89
90 void VisiblePosition::initUpstream(const Position &pos)
91 {
92     Position deepPos = deepEquivalent(pos);
93
94     if (isCandidate(deepPos)) {
95         m_deepPosition = deepPos;
96         Position next = nextVisiblePosition(deepPos);
97         if (next.isNotNull()) {
98             Position previous = previousVisiblePosition(next);
99             if (previous.isNotNull())
100                 m_deepPosition = previous;
101         }
102     }
103     else {
104         Position previous = previousVisiblePosition(deepPos);
105         if (previous.isNotNull()) {
106             m_deepPosition = previous;
107         }
108         else {
109             Position next = nextVisiblePosition(deepPos);
110             if (next.isNotNull())
111                 m_deepPosition = next;
112         }
113     }
114 }
115
116 void VisiblePosition::initDownstream(const Position &pos)
117 {
118     Position deepPos = deepEquivalent(pos);
119
120     if (isCandidate(deepPos)) {
121         m_deepPosition = deepPos;
122         Position previous = previousVisiblePosition(deepPos);
123         if (previous.isNotNull()) {
124             Position next = nextVisiblePosition(previous);
125             if (next.isNotNull())
126                 m_deepPosition = next;
127         }
128     }
129     else {
130         Position next = nextVisiblePosition(deepPos);
131         if (next.isNotNull()) {
132             m_deepPosition = next;
133         }
134         else {
135             Position previous = previousVisiblePosition(deepPos);
136             if (previous.isNotNull())
137                 m_deepPosition = previous;
138         }
139     }
140 }
141
142 bool VisiblePosition::isLastInBlock() const
143 {
144     if (isNull())
145         return false;
146         
147     VisiblePosition n = next();
148     return n.isNull() || (n.deepEquivalent().node()->enclosingBlockFlowElement() != m_deepPosition.node()->enclosingBlockFlowElement());
149 }
150
151 VisiblePosition VisiblePosition::next() const
152 {
153     VisiblePosition result;
154     result.m_deepPosition = nextVisiblePosition(m_deepPosition);
155     return result;
156 }
157
158 VisiblePosition VisiblePosition::previous() const
159 {
160     VisiblePosition result;
161     result.m_deepPosition = previousVisiblePosition(m_deepPosition);
162     return result;
163 }
164
165 Position VisiblePosition::previousVisiblePosition(const Position &pos)
166 {
167     if (pos.isNull() || atStart(pos))
168         return Position();
169
170     Position test = deepEquivalent(pos);
171     bool acceptAnyVisiblePosition = !isCandidate(test) || pos.isFirstRenderedPositionOnLine();
172
173     Position current = test;
174     while (!atStart(current)) {
175         current = previousPosition(current);
176         if (isCandidate(current) && (acceptAnyVisiblePosition || current.rendersInDifferentPosition(test))) {
177             return current;
178         }
179     }
180     
181     return Position();
182 }
183
184 Position VisiblePosition::nextVisiblePosition(const Position &pos)
185 {
186     if (pos.isNull() || atEnd(pos))
187         return Position();
188
189     Position test = deepEquivalent(pos);
190     bool acceptAnyVisiblePosition = !isCandidate(test) || pos.isLastRenderedPositionOnLine();
191
192     Position current = test;
193     while (!atEnd(current)) {
194         current = nextPosition(current);
195         if (isCandidate(current) && (acceptAnyVisiblePosition || current.rendersInDifferentPosition(test))) {
196             return current;
197         }
198     }
199     
200     return Position();
201 }
202
203 Position VisiblePosition::previousPosition(const Position &pos)
204 {
205     if (pos.isNull())
206         return pos;
207     
208     Position result;
209
210     if (pos.offset() <= 0) {
211         NodeImpl *prevNode = pos.node()->traversePreviousNode();
212         if (prevNode)
213             result = Position(prevNode, prevNode->maxOffset());
214     }
215     else {
216         result = Position(pos.node(), pos.offset() - 1);
217     }
218     
219     return result;
220 }
221
222 Position VisiblePosition::nextPosition(const Position &pos)
223 {
224     if (pos.isNull())
225         return pos;
226     
227     Position result;
228
229     if (pos.offset() >= pos.node()->maxOffset()) {
230         NodeImpl *nextNode = pos.node()->traverseNextNode();
231         if (nextNode)
232             result = Position(nextNode, 0);
233     }
234     else {
235         result = Position(pos.node(), pos.offset() + 1);
236     }
237     
238     return result;
239 }
240
241 bool VisiblePosition::atStart(const Position &pos)
242 {
243     if (pos.isNull())
244         return true;
245
246     return pos.offset() <= 0 && pos.node()->previousLeafNode() == 0;
247 }
248
249 bool VisiblePosition::atEnd(const Position &pos)
250 {
251     if (pos.isNull())
252         return true;
253
254     return pos.offset() >= pos.node()->maxOffset() && pos.node()->nextLeafNode() == 0;
255 }
256
257 bool VisiblePosition::isCandidate(const Position &pos)
258 {
259     if (pos.isNull())
260         return false;
261         
262     RenderObject *renderer = pos.node()->renderer();
263     if (!renderer)
264         return false;
265     
266     if (renderer->style()->visibility() != VISIBLE)
267         return false;
268
269     if (renderer->isReplaced())
270         // return true for replaced elements
271         return pos.offset() == 0 || pos.offset() == 1;
272
273     if (renderer->isBR()) {
274         if (pos.offset() == 0) {
275             InlineBox* box = static_cast<RenderText*>(renderer)->firstTextBox();
276             if (box) {
277                 // return true for offset 0 into BR element on a line by itself
278                 RootInlineBox* root = box->root();
279                 if (root)
280                     return root->firstLeafChild() == box && root->lastLeafChild() == box;
281             }
282         }   
283         return false;
284     }
285     
286     if (renderer->isText()) {
287         RenderText *textRenderer = static_cast<RenderText *>(renderer);
288         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
289             if (pos.offset() >= box->m_start && pos.offset() <= box->m_start + box->m_len) {
290                 // return true if in a text node
291                 return true;
292             }
293             else if (pos.offset() < box->m_start) {
294                 // The offset we're looking for is before this node
295                 // this means the offset must be in content that is
296                 // not rendered. Return false.
297                 return false;
298             }
299         }
300     }
301     
302     if (renderer->isBlockFlow() && !renderer->firstChild() && (renderer->height() || pos.node()->id() == ID_BODY))
303         // return true for offset 0 into rendered blocks that are empty of rendered kids, but have a height
304         return pos.offset() == 0;
305     
306     return false;
307 }
308
309 Position VisiblePosition::deepEquivalent(const Position &pos)
310 {
311     NodeImpl *node = pos.node();
312     long offset = pos.offset();
313
314     if (!node)
315         return Position();
316     
317     if (isAtomicNode(node)) {
318         // This is part of the strategy to wean the code off Positions with BRs and replaced elements
319         // as the nodes and offsets > 0.
320         if (offset > 0 && (node->id() == ID_BR || node->renderer() && node->renderer()->isReplaced())) {
321             NodeImpl *next = node->traverseNextNode();
322             if (next && node->enclosingBlockFlowElement() == next->enclosingBlockFlowElement())
323                 return deepEquivalent(Position(next, 0));
324         }
325         return pos;
326     }
327
328     if (offset >= (long)node->childNodeCount()) {
329         do {
330             NodeImpl *child = node->lastChild();
331             if (!child)
332                 break;
333             node = child;
334         } while (!isAtomicNode(node));
335         return Position(node, node->caretMaxOffset());
336     }
337     
338     node = node->childNode(offset);
339     ASSERT(node);
340     while (!isAtomicNode(node)) {
341         NodeImpl *child = node->firstChild();
342         if (!child)
343             break;
344         node = child;
345     }
346     return Position(node, 0);
347 }
348
349 Position VisiblePosition::rangeCompliantEquivalent(const Position &pos)
350 {
351     NodeImpl *node = pos.node();
352     if (!node)
353         return Position();
354     
355     // FIXME: This clamps out-of-range values.
356     // Instead we should probably assert, and not use such values.
357
358     long offset = pos.offset();
359     if (!offsetInCharacters(node->nodeType()) && isAtomicNode(node) && offset > 0)
360         return Position(node->parentNode(), node->nodeIndex() + 1);
361
362     return Position(node, kMax(0L, kMin(offset, maxOffset(node))));
363 }
364
365 long VisiblePosition::maxOffset(const NodeImpl *node)
366 {
367     return offsetInCharacters(node->nodeType()) ? (long)static_cast<const CharacterDataImpl *>(node)->length() : (long)node->childNodeCount();
368 }
369
370 bool VisiblePosition::isAtomicNode(const NodeImpl *node)
371 {
372     return node && (!node->hasChildNodes() || (node->id() == ID_OBJECT && node->renderer() && node->renderer()->isReplaced()));
373 }
374
375 void VisiblePosition::debugPosition(const char *msg) const
376 {
377     if (isNull())
378         fprintf(stderr, "Position [%s]: null\n", msg);
379     else
380         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, getTagName(m_deepPosition.node()->id()).string().latin1(), m_deepPosition.node(), m_deepPosition.offset());
381 }
382
383 #ifndef NDEBUG
384 void VisiblePosition::formatForDebugger(char *buffer, unsigned length) const
385 {
386     m_deepPosition.formatForDebugger(buffer, length);
387 }
388 #endif
389
390 Range makeRange(const VisiblePosition &start, const VisiblePosition &end)
391 {
392     Position s = start.position();
393     Position e = end.position();
394     return Range(s.node(), s.offset(), e.node(), e.offset());
395 }
396
397 VisiblePosition startVisiblePosition(const Range &r)
398 {
399     return VisiblePosition(r.startContainer().handle(), r.startOffset());
400 }
401
402 VisiblePosition endVisiblePosition(const Range &r)
403 {
404     return VisiblePosition(r.endContainer().handle(), r.endOffset());
405 }
406
407 bool setStart(Range &r, const VisiblePosition &c)
408 {
409     RangeImpl *ri = r.handle();
410     if (!ri)
411         return false;
412     Position p = c.position();
413     int code = 0;
414     ri->setStart(p.node(), p.offset(), code);
415     return code == 0;
416 }
417
418 bool setEnd(Range &r, const VisiblePosition &c)
419 {
420     RangeImpl *ri = r.handle();
421     if (!ri)
422         return false;
423     Position p = c.position();
424     int code = 0;
425     ri->setEnd(p.node(), p.offset(), code);
426     return code == 0;
427 }
428
429 }  // namespace DOM