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