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