WebCore:
[WebKit-https.git] / WebCore / page / FrameTree.cpp
1 // -*- c-basic-offset: 4 -*-
2 /*
3  * Copyright (C) 2006 Apple Computer, Inc.
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB.  If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  */
20
21 #include "config.h"
22 #include "FrameTree.h"
23
24 #include "Frame.h"
25 #include "Page.h"
26 #include "PageGroup.h"
27 #include <stdarg.h>
28 #include <wtf/Platform.h>
29 #include <wtf/StringExtras.h>
30 #include <wtf/Vector.h>
31
32 using std::swap;
33
34 namespace WebCore {
35
36 FrameTree::~FrameTree()
37 {
38     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
39         child->setView(0);
40 }
41
42 void FrameTree::setName(const AtomicString& name) 
43 {
44     if (!parent()) {
45         m_name = name;
46         return;
47     }
48     m_name = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName.
49     m_name = parent()->tree()->uniqueChildName(name);
50 }
51
52 Frame* FrameTree::parent(bool checkForDisconnectedFrame) const 
53
54     if (checkForDisconnectedFrame && m_thisFrame->isDisconnected())
55         return 0;
56     return m_parent;
57 }
58
59 void FrameTree::appendChild(PassRefPtr<Frame> child)
60 {
61     ASSERT(child->page() == m_thisFrame->page());
62     child->tree()->m_parent = m_thisFrame;
63
64     Frame* oldLast = m_lastChild;
65     m_lastChild = child.get();
66
67     if (oldLast) {
68         child->tree()->m_previousSibling = oldLast;
69         oldLast->tree()->m_nextSibling = child;
70     } else
71         m_firstChild = child;
72
73     m_childCount++;
74
75     ASSERT(!m_lastChild->tree()->m_nextSibling);
76 }
77
78 void FrameTree::removeChild(Frame* child)
79 {
80     child->tree()->m_parent = 0;
81     child->setView(0);
82     if (child->ownerElement())
83         child->page()->decrementFrameCount();
84     child->pageDestroyed();
85
86     // Slightly tricky way to prevent deleting the child until we are done with it, w/o
87     // extra refs. These swaps leave the child in a circular list by itself. Clearing its
88     // previous and next will then finally deref it.
89
90     RefPtr<Frame>& newLocationForNext = m_firstChild == child ? m_firstChild : child->tree()->m_previousSibling->tree()->m_nextSibling;
91     Frame*& newLocationForPrevious = m_lastChild == child ? m_lastChild : child->tree()->m_nextSibling->tree()->m_previousSibling;
92     swap(newLocationForNext, child->tree()->m_nextSibling);
93     // For some inexplicable reason, the following line does not compile without the explicit std:: namepsace
94     std::swap(newLocationForPrevious, child->tree()->m_previousSibling);
95
96     child->tree()->m_previousSibling = 0;
97     child->tree()->m_nextSibling = 0;
98
99     m_childCount--;
100 }
101
102 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
103 {
104     if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank")
105         return requestedName;
106
107     // Create a repeatable name for a child about to be added to us. The name must be
108     // unique within the frame tree. The string we generate includes a "path" of names
109     // from the root frame down to us. For this path to be unique, each set of siblings must
110     // contribute a unique name to the path, which can't collide with any HTML-assigned names.
111     // We generate this path component by index in the child list along with an unlikely
112     // frame name that can't be set in HTML because it collides with comment syntax.
113
114     const char framePathPrefix[] = "<!--framePath ";
115     const int framePathPrefixLength = 14;
116     const int framePathSuffixLength = 3;
117
118     // Find the nearest parent that has a frame with a path in it.
119     Vector<Frame*, 16> chain;
120     Frame* frame;
121     for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) {
122         if (frame->tree()->name().startsWith(framePathPrefix))
123             break;
124         chain.append(frame);
125     }
126     String name;
127     name += framePathPrefix;
128     if (frame)
129         name += frame->tree()->name().string().substring(framePathPrefixLength,
130             frame->tree()->name().length() - framePathPrefixLength - framePathSuffixLength);
131     for (int i = chain.size() - 1; i >= 0; --i) {
132         frame = chain[i];
133         name += "/";
134         name += frame->tree()->name();
135     }
136
137     // Suffix buffer has more than enough space for:
138     //     10 characters before the number
139     //     a number (3 digits for the highest this gets in practice, 20 digits for the largest 64-bit integer)
140     //     6 characters after the number
141     //     trailing null byte
142     // But we still use snprintf just to be extra-safe.
143     char suffix[40];
144     snprintf(suffix, sizeof(suffix), "/<!--frame%u-->-->", childCount());
145
146     name += suffix;
147
148     return AtomicString(name);
149 }
150
151 Frame* FrameTree::child(unsigned index) const
152 {
153     Frame* result = firstChild();
154     for (unsigned i = 0; result && i != index; ++i)
155         result = result->tree()->nextSibling();
156     return result;
157 }
158
159 Frame* FrameTree::child(const AtomicString& name) const
160 {
161     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
162         if (child->tree()->name() == name)
163             return child;
164     return 0;
165 }
166
167 Frame* FrameTree::find(const AtomicString& name) const
168 {
169     if (name == "_self" || name == "_current" || name.isEmpty())
170         return m_thisFrame;
171     
172     if (name == "_top")
173         return top();
174     
175     if (name == "_parent")
176         return parent() ? parent() : m_thisFrame;
177
178     // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
179     if (name == "_blank")
180         return 0;
181
182     // Search subtree starting with this frame first.
183     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame))
184         if (frame->tree()->name() == name)
185             return frame;
186
187     // Search the entire tree for this page next.
188     Page* page = m_thisFrame->page();
189
190     // The frame could have been detached from the page, so check it.
191     if (!page)
192         return 0;
193
194     for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
195         if (frame->tree()->name() == name)
196             return frame;
197
198     // Search the entire tree of each of the other pages in this namespace.
199     // FIXME: Is random order OK?
200     const HashSet<Page*>& pages = page->group().pages();
201     HashSet<Page*>::const_iterator end = pages.end();
202     for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
203         Page* otherPage = *it;
204         if (otherPage != page) {
205             for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) {
206                 if (frame->tree()->name() == name)
207                     return frame;
208             }
209         }
210     }
211
212     return 0;
213 }
214
215 bool FrameTree::isDescendantOf(const Frame* ancestor) const
216 {
217     if (!ancestor)
218         return false;
219
220     if (m_thisFrame->page() != ancestor->page())
221         return false;
222
223     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
224         if (frame == ancestor)
225             return true;
226     return false;
227 }
228
229 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
230 {
231     Frame* child = firstChild();
232     if (child) {
233         ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin));
234         return child;
235     }
236
237     if (m_thisFrame == stayWithin)
238         return 0;
239
240     Frame* sibling = nextSibling();
241     if (sibling) {
242         ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin));
243         return sibling;
244     }
245
246     Frame* frame = m_thisFrame;
247     while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) {
248         frame = frame->tree()->parent();
249         if (!frame)
250             return 0;
251         sibling = frame->tree()->nextSibling();
252     }
253
254     if (frame) {
255         ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin));
256         return sibling;
257     }
258
259     return 0;
260 }
261
262 Frame* FrameTree::traverseNextWithWrap(bool wrap) const
263 {
264     if (Frame* result = traverseNext())
265         return result;
266
267     if (wrap)
268         return m_thisFrame->page()->mainFrame();
269
270     return 0;
271 }
272
273 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
274 {
275     // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
276
277     if (Frame* prevSibling = previousSibling())
278         return prevSibling->tree()->deepLastChild();
279     if (Frame* parentFrame = parent())
280         return parentFrame;
281     
282     // no siblings, no parent, self==top
283     if (wrap)
284         return deepLastChild();
285
286     // top view is always the last one in this ordering, so prev is nil without wrap
287     return 0;
288 }
289
290 Frame* FrameTree::deepLastChild() const
291 {
292     Frame* result = m_thisFrame;
293     for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
294         result = last;
295
296     return result;
297 }
298
299 Frame* FrameTree::top(bool checkForDisconnectedFrame) const
300 {
301     Frame* frame = m_thisFrame;
302     for (Frame* parent = m_thisFrame; parent; parent = parent->tree()->parent()) {
303         frame = parent;
304         if (checkForDisconnectedFrame && frame->isDisconnected())
305             return frame;
306     }
307     return frame;
308 }
309
310 } // namespace WebCore