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 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 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 53 void FrameTree::clearName() 54 { 55 m_name = AtomicString(); 56 m_uniqueName = AtomicString(); 57 } 58 59 Frame* FrameTree::parent(bool checkForDisconnectedFrame) const 60 { 61 if (checkForDisconnectedFrame && m_thisFrame->isDisconnected()) 62 return 0; 63 return m_parent; 64 } 65 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 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 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 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 129 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 178 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 186 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 194 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 242 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 256 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 289 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 300 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 317 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 326 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
