1 // -*- c-basic-offset: 4 -*-
3 * Copyright (C) 2006 Apple Computer, Inc.
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.
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.
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.
22 #include "FrameTree.h"
26 #include "PageGroup.h"
28 #include <wtf/Platform.h>
29 #include <wtf/StringExtras.h>
30 #include <wtf/Vector.h>
36 FrameTree::~FrameTree()
38 for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
42 void FrameTree::setName(const AtomicString& name)
48 m_name = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName.
49 m_name = parent()->tree()->uniqueChildName(name);
52 void FrameTree::appendChild(PassRefPtr<Frame> child)
54 ASSERT(child->page() == m_thisFrame->page());
55 child->tree()->m_parent = m_thisFrame;
57 Frame* oldLast = m_lastChild;
58 m_lastChild = child.get();
61 child->tree()->m_previousSibling = oldLast;
62 oldLast->tree()->m_nextSibling = child;
68 ASSERT(!m_lastChild->tree()->m_nextSibling);
71 void FrameTree::removeChild(Frame* child)
73 child->tree()->m_parent = 0;
75 if (child->ownerElement())
76 child->page()->decrementFrameCount();
77 child->pageDestroyed();
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.
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);
89 child->tree()->m_previousSibling = 0;
90 child->tree()->m_nextSibling = 0;
95 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
97 if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank")
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.
107 const char framePathPrefix[] = "<!--framePath ";
108 const int framePathPrefixLength = 14;
109 const int framePathSuffixLength = 3;
111 // Find the nearest parent that has a frame with a path in it.
112 Vector<Frame*, 16> chain;
114 for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) {
115 if (frame->tree()->name().startsWith(framePathPrefix))
120 name += framePathPrefix;
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) {
127 name += frame->tree()->name();
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.
137 snprintf(suffix, sizeof(suffix), "/<!--frame%u-->-->", childCount());
141 return AtomicString(name);
144 Frame* FrameTree::child(unsigned index) const
146 Frame* result = firstChild();
147 for (unsigned i = 0; result && i != index; ++i)
148 result = result->tree()->nextSibling();
152 Frame* FrameTree::child(const AtomicString& name) const
154 for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
155 if (child->tree()->name() == name)
160 Frame* FrameTree::find(const AtomicString& name) const
162 if (name == "_self" || name == "_current" || name.isEmpty())
168 if (name == "_parent")
169 return parent() ? parent() : m_thisFrame;
171 // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
172 if (name == "_blank")
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)
180 // Search the entire tree for this page next.
181 Page* page = m_thisFrame->page();
183 // The frame could have been detached from the page, so check it.
187 for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
188 if (frame->tree()->name() == name)
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)
208 bool FrameTree::isDescendantOf(const Frame* ancestor) const
213 if (m_thisFrame->page() != ancestor->page())
216 for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
217 if (frame == ancestor)
222 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
224 Frame* child = firstChild();
226 ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin));
230 if (m_thisFrame == stayWithin)
233 Frame* sibling = nextSibling();
235 ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin));
239 Frame* frame = m_thisFrame;
240 while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) {
241 frame = frame->tree()->parent();
244 sibling = frame->tree()->nextSibling();
248 ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin));
255 Frame* FrameTree::traverseNextWithWrap(bool wrap) const
257 if (Frame* result = traverseNext())
261 return m_thisFrame->page()->mainFrame();
266 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
268 // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
270 if (Frame* prevSibling = previousSibling())
271 return prevSibling->tree()->deepLastChild();
272 if (Frame* parentFrame = parent())
275 // no siblings, no parent, self==top
277 return deepLastChild();
279 // top view is always the last one in this ordering, so prev is nil without wrap
283 Frame* FrameTree::deepLastChild() const
285 Frame* result = m_thisFrame;
286 for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
292 Frame* FrameTree::top() const
294 if (Page* page = m_thisFrame->page())
295 return page->mainFrame();
297 Frame* frame = m_thisFrame;
298 while (Frame* parent = frame->tree()->parent())
303 } // namespace WebCore