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