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