Reviewed by Darin
[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         // This is part of the strategy to wean the code off Positions with BRs and replaced elements
322         // as the nodes and offsets > 0.
323         if (offset > 0 && (node->id() == ID_BR || node->renderer() && node->renderer()->isReplaced())) {
324             NodeImpl *next = node->traverseNextNode();
325             if (next && node->enclosingBlockFlowElement() == next->enclosingBlockFlowElement())
326                 return deepEquivalent(Position(next, 0));
327         }
328         return pos;
329     }
330
331     if (offset >= (long)node->childNodeCount()) {
332         do {
333             NodeImpl *child = node->lastChild();
334             if (!child)
335                 break;
336             node = child;
337         } while (!isAtomicNode(node));
338         return Position(node, node->caretMaxOffset());
339     }
340     
341     node = node->childNode(offset);
342     ASSERT(node);
343     while (!isAtomicNode(node)) {
344         NodeImpl *child = node->firstChild();
345         if (!child)
346             break;
347         node = child;
348     }
349     return Position(node, 0);
350 }
351
352 Position VisiblePosition::upstreamDeepEquivalent() const
353 {
354     Position pos = m_deepPosition;
355     
356     if (pos.isNull() || atStart(pos))
357         return pos;
358
359     Position downstreamTest = pos.downstream(StayInBlock);
360
361     Position current = pos;
362     while (!atStart(current)) {
363         current = previousPosition(current);
364         if (isCandidate(current)) {
365             if (downstreamTest != current.downstream(StayInBlock))
366                 break;
367             pos = current;
368         }
369     }
370     
371     return pos;
372 }
373
374 Position VisiblePosition::rangeCompliantEquivalent(const Position &pos)
375 {
376     NodeImpl *node = pos.node();
377     if (!node)
378         return Position();
379     
380     // FIXME: This clamps out-of-range values.
381     // Instead we should probably assert, and not use such values.
382
383     long offset = pos.offset();
384     if (!offsetInCharacters(node->nodeType()) && isAtomicNode(node) && offset > 0)
385         return Position(node->parentNode(), node->nodeIndex() + 1);
386
387     return Position(node, kMax(0L, kMin(offset, maxOffset(node))));
388 }
389
390 long VisiblePosition::maxOffset(const NodeImpl *node)
391 {
392     return offsetInCharacters(node->nodeType()) ? (long)static_cast<const CharacterDataImpl *>(node)->length() : (long)node->childNodeCount();
393 }
394
395 bool VisiblePosition::isAtomicNode(const NodeImpl *node)
396 {
397     return node && (!node->hasChildNodes() || (node->id() == ID_OBJECT && node->renderer() && node->renderer()->isReplaced()));
398 }
399
400 void VisiblePosition::debugPosition(const char *msg) const
401 {
402     if (isNull())
403         fprintf(stderr, "Position [%s]: null\n", msg);
404     else
405         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, getTagName(m_deepPosition.node()->id()).string().latin1(), m_deepPosition.node(), m_deepPosition.offset());
406 }
407
408 #ifndef NDEBUG
409 void VisiblePosition::formatForDebugger(char *buffer, unsigned length) const
410 {
411     m_deepPosition.formatForDebugger(buffer, length);
412 }
413 #endif
414
415 Range makeRange(const VisiblePosition &start, const VisiblePosition &end)
416 {
417     Position s = start.position();
418     Position e = end.position();
419     return Range(s.node(), s.offset(), e.node(), e.offset());
420 }
421
422 VisiblePosition startVisiblePosition(const Range &r)
423 {
424     return VisiblePosition(r.startContainer().handle(), r.startOffset());
425 }
426
427 VisiblePosition endVisiblePosition(const Range &r)
428 {
429     return VisiblePosition(r.endContainer().handle(), r.endOffset());
430 }
431
432 bool setStart(Range &r, const VisiblePosition &c)
433 {
434     RangeImpl *ri = r.handle();
435     if (!ri)
436         return false;
437     Position p = c.position();
438     int code = 0;
439     ri->setStart(p.node(), p.offset(), code);
440     return code == 0;
441 }
442
443 bool setEnd(Range &r, const VisiblePosition &c)
444 {
445     RangeImpl *ri = r.handle();
446     if (!ri)
447         return false;
448     Position p = c.position();
449     int code = 0;
450     ri->setEnd(p.node(), p.offset(), code);
451     return code == 0;
452 }
453
454 }  // namespace DOM