Reviewed by John
[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 using DOM::StayInBlock;
46
47 namespace khtml {
48
49 VisiblePosition::VisiblePosition(NodeImpl *node, long offset, EAffinity affinity)
50 {
51     Position pos = Position(node, offset);
52
53     // A first step toward eliminating the affinity parameter.
54     // For <br> 0, it's important not to move past the <br>.
55     if (node && node->id() == ID_BR && offset == 0)
56         affinity = UPSTREAM;
57
58     switch (affinity) {
59         case UPSTREAM:
60             initUpstream(pos);
61             break;
62         case DOWNSTREAM:
63             initDownstream(pos);
64             break;
65         default:
66             ASSERT_NOT_REACHED();
67             break;
68     }
69 }
70
71 VisiblePosition::VisiblePosition(const Position &pos, EAffinity affinity)
72 {
73     // A first step toward eliminating the affinity parameter.
74     // For <br> 0, it's important not to move past the <br>.
75     if (pos.node() && pos.node()->id() == ID_BR && pos.offset() == 0)
76         affinity = UPSTREAM;
77
78     switch (affinity) {
79         case UPSTREAM:
80             initUpstream(pos);
81             break;
82         case DOWNSTREAM:
83             initDownstream(pos);
84             break;
85         default:
86             ASSERT_NOT_REACHED();
87             break;
88     }
89 }
90
91 void VisiblePosition::initUpstream(const Position &pos)
92 {
93     Position deepPos = deepEquivalent(pos);
94
95     if (isCandidate(deepPos)) {
96         m_deepPosition = deepPos;
97         Position next = nextVisiblePosition(deepPos);
98         if (next.isNotNull()) {
99             Position previous = previousVisiblePosition(next);
100             if (previous.isNotNull())
101                 m_deepPosition = previous;
102         }
103     }
104     else {
105         Position previous = previousVisiblePosition(deepPos);
106         if (previous.isNotNull()) {
107             m_deepPosition = previous;
108         }
109         else {
110             Position next = nextVisiblePosition(deepPos);
111             if (next.isNotNull())
112                 m_deepPosition = next;
113         }
114     }
115 }
116
117 void VisiblePosition::initDownstream(const Position &pos)
118 {
119     Position deepPos = deepEquivalent(pos);
120
121     if (isCandidate(deepPos)) {
122         m_deepPosition = deepPos;
123         Position previous = previousVisiblePosition(deepPos);
124         if (previous.isNotNull()) {
125             Position next = nextVisiblePosition(previous);
126             if (next.isNotNull())
127                 m_deepPosition = next;
128         }
129     }
130     else {
131         Position next = nextVisiblePosition(deepPos);
132         if (next.isNotNull()) {
133             m_deepPosition = next;
134         }
135         else {
136             Position previous = previousVisiblePosition(deepPos);
137             if (previous.isNotNull())
138                 m_deepPosition = previous;
139         }
140     }
141 }
142
143 bool VisiblePosition::isLastInBlock() const
144 {
145     if (isNull())
146         return false;
147         
148     VisiblePosition n = next();
149     return n.isNull() || (n.deepEquivalent().node()->enclosingBlockFlowElement() != m_deepPosition.node()->enclosingBlockFlowElement());
150 }
151
152 VisiblePosition VisiblePosition::next() const
153 {
154     VisiblePosition result;
155     result.m_deepPosition = nextVisiblePosition(m_deepPosition);
156     return result;
157 }
158
159 VisiblePosition VisiblePosition::previous() const
160 {
161     VisiblePosition result;
162     result.m_deepPosition = previousVisiblePosition(m_deepPosition);
163     return result;
164 }
165
166 Position VisiblePosition::previousVisiblePosition(const Position &pos)
167 {
168     if (pos.isNull() || atStart(pos))
169         return Position();
170
171     Position test = deepEquivalent(pos);
172     Position downstreamTest = test.downstream(StayInBlock);
173     bool acceptAnyVisiblePosition = !isCandidate(test);
174
175     Position current = test;
176     while (!atStart(current)) {
177         current = previousPosition(current);
178         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream(StayInBlock)))) {
179             return current;
180         }
181     }
182     
183     return Position();
184 }
185
186 Position VisiblePosition::nextVisiblePosition(const Position &pos)
187 {
188     if (pos.isNull() || atEnd(pos))
189         return Position();
190
191     Position test = deepEquivalent(pos);
192     bool acceptAnyVisiblePosition = !isCandidate(test);
193
194     Position current = test;
195     Position downstreamTest = test.downstream(StayInBlock);
196     while (!atEnd(current)) {
197         current = nextPosition(current);
198         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream(StayInBlock)))) {
199             return current;
200         }
201     }
202     
203     return Position();
204 }
205
206 Position VisiblePosition::previousPosition(const Position &pos)
207 {
208     if (pos.isNull())
209         return pos;
210     
211     Position result;
212
213     if (pos.offset() <= 0) {
214         NodeImpl *prevNode = pos.node()->traversePreviousNode();
215         if (prevNode)
216             result = Position(prevNode, prevNode->maxOffset());
217     }
218     else {
219         result = Position(pos.node(), pos.offset() - 1);
220     }
221     
222     return result;
223 }
224
225 Position VisiblePosition::nextPosition(const Position &pos)
226 {
227     if (pos.isNull())
228         return pos;
229     
230     Position result;
231
232     if (pos.offset() >= pos.node()->maxOffset()) {
233         NodeImpl *nextNode = pos.node()->traverseNextNode();
234         if (nextNode)
235             result = Position(nextNode, 0);
236     }
237     else {
238         result = Position(pos.node(), pos.offset() + 1);
239     }
240     
241     return result;
242 }
243
244 bool VisiblePosition::atStart(const Position &pos)
245 {
246     if (pos.isNull())
247         return true;
248
249     return pos.offset() <= 0 && pos.node()->previousLeafNode() == 0;
250 }
251
252 bool VisiblePosition::atEnd(const Position &pos)
253 {
254     if (pos.isNull())
255         return true;
256
257     return pos.offset() >= pos.node()->maxOffset() && pos.node()->nextLeafNode() == 0;
258 }
259
260 bool VisiblePosition::isCandidate(const Position &pos)
261 {
262     if (pos.isNull())
263         return false;
264         
265     RenderObject *renderer = pos.node()->renderer();
266     if (!renderer)
267         return false;
268     
269     if (renderer->style()->visibility() != VISIBLE)
270         return false;
271
272     if (renderer->isReplaced())
273         // return true for replaced elements
274         return pos.offset() == 0 || pos.offset() == 1;
275
276     if (renderer->isBR()) {
277         if (pos.offset() == 0) {
278             InlineBox* box = static_cast<RenderText*>(renderer)->firstTextBox();
279             if (box) {
280                 // return true for offset 0 into BR element on a line by itself
281                 RootInlineBox* root = box->root();
282                 if (root)
283                     return root->firstLeafChild() == box && root->lastLeafChild() == box;
284             }
285         }   
286         return false;
287     }
288     
289     if (renderer->isText()) {
290         RenderText *textRenderer = static_cast<RenderText *>(renderer);
291         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
292             if (pos.offset() >= box->m_start && pos.offset() <= box->m_start + box->m_len) {
293                 // return true if in a text node
294                 return true;
295             }
296             else if (pos.offset() < box->m_start) {
297                 // The offset we're looking for is before this node
298                 // this means the offset must be in content that is
299                 // not rendered. Return false.
300                 return false;
301             }
302         }
303     }
304     
305     if (renderer->isBlockFlow() && !renderer->firstChild() && (renderer->height() || pos.node()->id() == ID_BODY))
306         // return true for offset 0 into rendered blocks that are empty of rendered kids, but have a height
307         return pos.offset() == 0;
308     
309     return false;
310 }
311
312 Position VisiblePosition::deepEquivalent(const Position &pos)
313 {
314     NodeImpl *node = pos.node();
315     long offset = pos.offset();
316
317     if (!node)
318         return Position();
319     
320     if (isAtomicNode(node))
321         return pos;
322
323     if (offset >= (long)node->childNodeCount()) {
324         do {
325             NodeImpl *child = node->lastChild();
326             if (!child)
327                 break;
328             node = child;
329         } while (!isAtomicNode(node));
330         return Position(node, node->caretMaxOffset());
331     }
332     
333     node = node->childNode(offset);
334     ASSERT(node);
335     while (!isAtomicNode(node)) {
336         NodeImpl *child = node->firstChild();
337         if (!child)
338             break;
339         node = child;
340     }
341     return Position(node, 0);
342 }
343
344 Position VisiblePosition::downstreamDeepEquivalent() const
345 {
346     Position pos = m_deepPosition;
347     
348     if (pos.isNull() || atEnd(pos))
349         return pos;
350
351     Position downstreamTest = pos.downstream(StayInBlock);
352
353     Position current = pos;
354     while (!atEnd(current)) {
355         current = nextPosition(current);
356         if (isCandidate(current)) {
357             if (downstreamTest != current.downstream(StayInBlock))
358                 break;
359             pos = current;
360         }
361     }
362     
363     return pos;
364 }
365
366 Position VisiblePosition::rangeCompliantEquivalent(const Position &pos)
367 {
368     NodeImpl *node = pos.node();
369     if (!node)
370         return Position();
371     
372     // FIXME: This clamps out-of-range values.
373     // Instead we should probably assert, and not use such values.
374
375     long offset = pos.offset();
376     if (!offsetInCharacters(node->nodeType()) && isAtomicNode(node) && offset > 0)
377         return Position(node->parentNode(), node->nodeIndex() + 1);
378
379     return Position(node, kMax(0L, kMin(offset, maxOffset(node))));
380 }
381
382 long VisiblePosition::maxOffset(const NodeImpl *node)
383 {
384     return offsetInCharacters(node->nodeType()) ? (long)static_cast<const CharacterDataImpl *>(node)->length() : (long)node->childNodeCount();
385 }
386
387 bool VisiblePosition::isAtomicNode(const NodeImpl *node)
388 {
389     return node && (!node->hasChildNodes() || (node->id() == ID_OBJECT && node->renderer() && node->renderer()->isReplaced()));
390 }
391
392 void VisiblePosition::debugPosition(const char *msg) const
393 {
394     if (isNull())
395         fprintf(stderr, "Position [%s]: null\n", msg);
396     else
397         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, getTagName(m_deepPosition.node()->id()).string().latin1(), m_deepPosition.node(), m_deepPosition.offset());
398 }
399
400 #ifndef NDEBUG
401 void VisiblePosition::formatForDebugger(char *buffer, unsigned length) const
402 {
403     m_deepPosition.formatForDebugger(buffer, length);
404 }
405 #endif
406
407 Range makeRange(const VisiblePosition &start, const VisiblePosition &end)
408 {
409     Position s = start.position();
410     Position e = end.position();
411     return Range(s.node(), s.offset(), e.node(), e.offset());
412 }
413
414 VisiblePosition startVisiblePosition(const Range &r)
415 {
416     return VisiblePosition(r.startContainer().handle(), r.startOffset());
417 }
418
419 VisiblePosition endVisiblePosition(const Range &r)
420 {
421     return VisiblePosition(r.endContainer().handle(), r.endOffset());
422 }
423
424 bool setStart(Range &r, const VisiblePosition &c)
425 {
426     RangeImpl *ri = r.handle();
427     if (!ri)
428         return false;
429     Position p = c.position();
430     int code = 0;
431     ri->setStart(p.node(), p.offset(), code);
432     return code == 0;
433 }
434
435 bool setEnd(Range &r, const VisiblePosition &c)
436 {
437     RangeImpl *ri = r.handle();
438     if (!ri)
439         return false;
440     Position p = c.position();
441     int code = 0;
442     ri->setEnd(p.node(), p.offset(), code);
443     return code == 0;
444 }
445
446 }  // namespace DOM