1fbea6372a71d1e305a710adb7d246dcda746408
[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 void FrameTree::appendChild(PassRefPtr<Frame> child)
53 {
54     ASSERT(child->page() == m_thisFrame->page());
55     child->tree()->m_parent = m_thisFrame;
56
57     Frame* oldLast = m_lastChild;
58     m_lastChild = child.get();
59
60     if (oldLast) {
61         child->tree()->m_previousSibling = oldLast;
62         oldLast->tree()->m_nextSibling = child;
63     } else
64         m_firstChild = child;
65
66     m_childCount++;
67
68     ASSERT(!m_lastChild->tree()->m_nextSibling);
69 }
70
71 void FrameTree::removeChild(Frame* child)
72 {
73     child->tree()->m_parent = 0;
74     child->setView(0);
75     if (child->ownerElement())
76         child->page()->decrementFrameCount();
77     child->pageDestroyed();
78
79     // Slightly tricky way to prevent deleting the child until we are done with it, w/o
80     // extra refs. These swaps leave the child in a circular list by itself. Clearing its
81     // previous and next will then finally deref it.
82
83     RefPtr<Frame>& newLocationForNext = m_firstChild == child ? m_firstChild : child->tree()->m_previousSibling->tree()->m_nextSibling;
84     Frame*& newLocationForPrevious = m_lastChild == child ? m_lastChild : child->tree()->m_nextSibling->tree()->m_previousSibling;
85     swap(newLocationForNext, child->tree()->m_nextSibling);
86     // For some inexplicable reason, the following line does not compile without the explicit std:: namepsace
87     std::swap(newLocationForPrevious, child->tree()->m_previousSibling);
88
89     child->tree()->m_previousSibling = 0;
90     child->tree()->m_nextSibling = 0;
91
92     m_childCount--;
93 }
94
95 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
96 {
97     if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank")
98         return requestedName;
99
100     // Create a repeatable name for a child about to be added to us. The name must be
101     // unique within the frame tree. The string we generate includes a "path" of names
102     // from the root frame down to us. For this path to be unique, each set of siblings must
103     // contribute a unique name to the path, which can't collide with any HTML-assigned names.
104     // We generate this path component by index in the child list along with an unlikely
105     // frame name that can't be set in HTML because it collides with comment syntax.
106
107     const char framePathPrefix[] = "<!--framePath ";
108     const int framePathPrefixLength = 14;
109     const int framePathSuffixLength = 3;
110
111     // Find the nearest parent that has a frame with a path in it.
112     Vector<Frame*, 16> chain;
113     Frame* frame;
114     for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) {
115         if (frame->tree()->name().startsWith(framePathPrefix))
116             break;
117         chain.append(frame);
118     }
119     String name;
120     name += framePathPrefix;
121     if (frame)
122         name += frame->tree()->name().string().substring(framePathPrefixLength,
123             frame->tree()->name().length() - framePathPrefixLength - framePathSuffixLength);
124     for (int i = chain.size() - 1; i >= 0; --i) {
125         frame = chain[i];
126         name += "/";
127         name += frame->tree()->name();
128     }
129
130     // Suffix buffer has more than enough space for:
131     //     10 characters before the number
132     //     a number (3 digits for the highest this gets in practice, 20 digits for the largest 64-bit integer)
133     //     6 characters after the number
134     //     trailing null byte
135     // But we still use snprintf just to be extra-safe.
136     char suffix[40];
137     snprintf(suffix, sizeof(suffix), "/<!--frame%u-->-->", childCount());
138
139     name += suffix;
140
141     return AtomicString(name);
142 }
143
144 Frame* FrameTree::child(unsigned index) const
145 {
146     Frame* result = firstChild();
147     for (unsigned i = 0; result && i != index; ++i)
148         result = result->tree()->nextSibling();
149     return result;
150 }
151
152 Frame* FrameTree::child(const AtomicString& name) const
153 {
154     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
155         if (child->tree()->name() == name)
156             return child;
157     return 0;
158 }
159
160 Frame* FrameTree::find(const AtomicString& name) const
161 {
162     if (name == "_self" || name == "_current" || name.isEmpty())
163         return m_thisFrame;
164     
165     if (name == "_top")
166         return top();
167     
168     if (name == "_parent")
169         return parent() ? parent() : m_thisFrame;
170
171     // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
172     if (name == "_blank")
173         return 0;
174
175     // Search subtree starting with this frame first.
176     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame))
177         if (frame->tree()->name() == name)
178             return frame;
179
180     // Search the entire tree for this page next.
181     Page* page = m_thisFrame->page();
182
183     // The frame could have been detached from the page, so check it.
184     if (!page)
185         return 0;
186
187     for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
188         if (frame->tree()->name() == name)
189             return frame;
190
191     // Search the entire tree of each of the other pages in this namespace.
192     // FIXME: Is random order OK?
193     const HashSet<Page*>& pages = page->group().pages();
194     HashSet<Page*>::const_iterator end = pages.end();
195     for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
196         Page* otherPage = *it;
197         if (otherPage != page) {
198             for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) {
199                 if (frame->tree()->name() == name)
200                     return frame;
201             }
202         }
203     }
204
205     return 0;
206 }
207
208 bool FrameTree::isDescendantOf(const Frame* ancestor) const
209 {
210     if (!ancestor)
211         return false;
212
213     if (m_thisFrame->page() != ancestor->page())
214         return false;
215
216     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
217         if (frame == ancestor)
218             return true;
219     return false;
220 }
221
222 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
223 {
224     Frame* child = firstChild();
225     if (child) {
226         ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin));
227         return child;
228     }
229
230     if (m_thisFrame == stayWithin)
231         return 0;
232
233     Frame* sibling = nextSibling();
234     if (sibling) {
235         ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin));
236         return sibling;
237     }
238
239     Frame* frame = m_thisFrame;
240     while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) {
241         frame = frame->tree()->parent();
242         if (!frame)
243             return 0;
244         sibling = frame->tree()->nextSibling();
245     }
246
247     if (frame) {
248         ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin));
249         return sibling;
250     }
251
252     return 0;
253 }
254
255 Frame* FrameTree::traverseNextWithWrap(bool wrap) const
256 {
257     if (Frame* result = traverseNext())
258         return result;
259
260     if (wrap)
261         return m_thisFrame->page()->mainFrame();
262
263     return 0;
264 }
265
266 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
267 {
268     // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
269
270     if (Frame* prevSibling = previousSibling())
271         return prevSibling->tree()->deepLastChild();
272     if (Frame* parentFrame = parent())
273         return parentFrame;
274     
275     // no siblings, no parent, self==top
276     if (wrap)
277         return deepLastChild();
278
279     // top view is always the last one in this ordering, so prev is nil without wrap
280     return 0;
281 }
282
283 Frame* FrameTree::deepLastChild() const
284 {
285     Frame* result = m_thisFrame;
286     for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
287         result = last;
288
289     return result;
290 }
291
292 Frame* FrameTree::top() const
293 {
294     if (Page* page = m_thisFrame->page())
295         return page->mainFrame();
296
297     Frame* frame = m_thisFrame;
298     while (Frame* parent = frame->tree()->parent())
299         frame = parent;
300     return frame;
301 }
302
303 } // namespace WebCore