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 "core/page/FrameTree.h" 23 24 #include "core/dom/Document.h" 25 #include "core/page/Frame.h" 26 #include "core/page/FrameView.h" 27 #include "core/page/Page.h" 28 #include "core/page/PageGroup.h" 29 #include "wtf/Vector.h" 30 #include "wtf/text/CString.h" 31 #include "wtf/text/StringBuilder.h" 32 33 using std::swap; 34 35 namespace WebCore { 36 37 FrameTree::~FrameTree() 38 { 39 for (Frame* child = firstChild(); child; child = child->tree()->nextSibling()) 40 child->setView(0); 41 } 42 43 void FrameTree::setName(const AtomicString& name) 44 { 45 m_name = name; 46 if (!parent()) { 47 m_uniqueName = name; 48 return; 49 } 50 m_uniqueName = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName. 51 m_uniqueName = parent()->tree()->uniqueChildName(name); 52 } 53 54 void FrameTree::clearName() 55 { 56 m_name = AtomicString(); 57 m_uniqueName = AtomicString(); 58 } 59 60 Frame* FrameTree::parent() const 61 { 62 return m_parent; 63 } 64 65 bool FrameTree::transferChild(PassRefPtr<Frame> child) 66 { 67 Frame* oldParent = child->tree()->parent(); 68 if (oldParent == m_thisFrame) 69 return false; // |child| is already a child of m_thisFrame. 70 71 if (oldParent) 72 oldParent->tree()->removeChild(child.get()); 73 74 ASSERT(child->page() == m_thisFrame->page()); 75 child->tree()->m_parent = m_thisFrame; 76 77 // We need to ensure that the child still has a unique frame name with respect to its new parent. 78 child->tree()->setName(child->tree()->m_name); 79 80 actuallyAppendChild(child); // Note, on return |child| is null. 81 return true; 82 } 83 84 void FrameTree::appendChild(PassRefPtr<Frame> child) 85 { 86 ASSERT(child->page() == m_thisFrame->page()); 87 child->tree()->m_parent = m_thisFrame; 88 actuallyAppendChild(child); // Note, on return |child| is null. 89 } 90 91 void FrameTree::actuallyAppendChild(PassRefPtr<Frame> child) 92 { 93 ASSERT(child->tree()->m_parent == m_thisFrame); 94 Frame* oldLast = m_lastChild; 95 m_lastChild = child.get(); 96 97 if (oldLast) { 98 child->tree()->m_previousSibling = oldLast; 99 oldLast->tree()->m_nextSibling = child; 100 } else 101 m_firstChild = child; 102 103 m_scopedChildCount = invalidCount; 104 105 ASSERT(!m_lastChild->tree()->m_nextSibling); 106 } 107 108 void FrameTree::removeChild(Frame* child) 109 { 110 child->tree()->m_parent = 0; 111 112 // Slightly tricky way to prevent deleting the child until we are done with it, w/o 113 // extra refs. These swaps leave the child in a circular list by itself. Clearing its 114 // previous and next will then finally deref it. 115 116 RefPtr<Frame>& newLocationForNext = m_firstChild == child ? m_firstChild : child->tree()->m_previousSibling->tree()->m_nextSibling; 117 Frame*& newLocationForPrevious = m_lastChild == child ? m_lastChild : child->tree()->m_nextSibling->tree()->m_previousSibling; 118 swap(newLocationForNext, child->tree()->m_nextSibling); 119 // For some inexplicable reason, the following line does not compile without the explicit std:: namespace 120 std::swap(newLocationForPrevious, child->tree()->m_previousSibling); 121 122 child->tree()->m_previousSibling = 0; 123 child->tree()->m_nextSibling = 0; 124 125 m_scopedChildCount = invalidCount; 126 } 127 128 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const 129 { 130 if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank") 131 return requestedName; 132 133 // Create a repeatable name for a child about to be added to us. The name must be 134 // unique within the frame tree. The string we generate includes a "path" of names 135 // from the root frame down to us. For this path to be unique, each set of siblings must 136 // contribute a unique name to the path, which can't collide with any HTML-assigned names. 137 // We generate this path component by index in the child list along with an unlikely 138 // frame name that can't be set in HTML because it collides with comment syntax. 139 140 const char framePathPrefix[] = "<!--framePath "; 141 const int framePathPrefixLength = 14; 142 const int framePathSuffixLength = 3; 143 144 // Find the nearest parent that has a frame with a path in it. 145 Vector<Frame*, 16> chain; 146 Frame* frame; 147 for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) { 148 if (frame->tree()->uniqueName().startsWith(framePathPrefix)) 149 break; 150 chain.append(frame); 151 } 152 StringBuilder name; 153 name.append(framePathPrefix); 154 if (frame) { 155 name.append(frame->tree()->uniqueName().string().substring(framePathPrefixLength, 156 frame->tree()->uniqueName().length() - framePathPrefixLength - framePathSuffixLength)); 157 } 158 for (int i = chain.size() - 1; i >= 0; --i) { 159 frame = chain[i]; 160 name.append('/'); 161 name.append(frame->tree()->uniqueName()); 162 } 163 164 name.appendLiteral("/<!--frame"); 165 name.appendNumber(childCount()); 166 name.appendLiteral("-->-->"); 167 168 return name.toAtomicString(); 169 } 170 171 inline Frame* FrameTree::scopedChild(unsigned index, TreeScope* scope) const 172 { 173 if (!scope) 174 return 0; 175 176 unsigned scopedIndex = 0; 177 for (Frame* result = firstChild(); result; result = result->tree()->nextSibling()) { 178 if (result->inScope(scope)) { 179 if (scopedIndex == index) 180 return result; 181 scopedIndex++; 182 } 183 } 184 185 return 0; 186 } 187 188 inline Frame* FrameTree::scopedChild(const AtomicString& name, TreeScope* scope) const 189 { 190 if (!scope) 191 return 0; 192 193 for (Frame* child = firstChild(); child; child = child->tree()->nextSibling()) 194 if (child->tree()->uniqueName() == name && child->inScope(scope)) 195 return child; 196 return 0; 197 } 198 199 inline unsigned FrameTree::scopedChildCount(TreeScope* scope) const 200 { 201 if (!scope) 202 return 0; 203 204 unsigned scopedCount = 0; 205 for (Frame* result = firstChild(); result; result = result->tree()->nextSibling()) { 206 if (result->inScope(scope)) 207 scopedCount++; 208 } 209 210 return scopedCount; 211 } 212 213 Frame* FrameTree::scopedChild(unsigned index) const 214 { 215 return scopedChild(index, m_thisFrame->document()); 216 } 217 218 Frame* FrameTree::scopedChild(const AtomicString& name) const 219 { 220 return scopedChild(name, m_thisFrame->document()); 221 } 222 223 unsigned FrameTree::scopedChildCount() const 224 { 225 if (m_scopedChildCount == invalidCount) 226 m_scopedChildCount = scopedChildCount(m_thisFrame->document()); 227 return m_scopedChildCount; 228 } 229 230 unsigned FrameTree::childCount() const 231 { 232 unsigned count = 0; 233 for (Frame* result = firstChild(); result; result = result->tree()->nextSibling()) 234 ++count; 235 return count; 236 } 237 238 Frame* FrameTree::child(unsigned index) const 239 { 240 Frame* result = firstChild(); 241 for (unsigned i = 0; result && i != index; ++i) 242 result = result->tree()->nextSibling(); 243 return result; 244 } 245 246 Frame* FrameTree::child(const AtomicString& name) const 247 { 248 for (Frame* child = firstChild(); child; child = child->tree()->nextSibling()) 249 if (child->tree()->uniqueName() == name) 250 return child; 251 return 0; 252 } 253 254 Frame* FrameTree::find(const AtomicString& name) const 255 { 256 if (name == "_self" || name == "_current" || name.isEmpty()) 257 return m_thisFrame; 258 259 if (name == "_top") 260 return top(); 261 262 if (name == "_parent") 263 return parent() ? parent() : m_thisFrame; 264 265 // Since "_blank" should never be any frame's name, the following just amounts to an optimization. 266 if (name == "_blank") 267 return 0; 268 269 // Search subtree starting with this frame first. 270 for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame)) 271 if (frame->tree()->uniqueName() == name) 272 return frame; 273 274 // Search the entire tree for this page next. 275 Page* page = m_thisFrame->page(); 276 277 // The frame could have been detached from the page, so check it. 278 if (!page) 279 return 0; 280 281 for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext()) 282 if (frame->tree()->uniqueName() == name) 283 return frame; 284 285 // Search the entire tree of each of the other pages in this namespace. 286 // FIXME: Is random order OK? 287 const HashSet<Page*>& pages = page->group().pages(); 288 HashSet<Page*>::const_iterator end = pages.end(); 289 for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) { 290 Page* otherPage = *it; 291 if (otherPage != page) { 292 for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) { 293 if (frame->tree()->uniqueName() == name) 294 return frame; 295 } 296 } 297 } 298 299 return 0; 300 } 301 302 bool FrameTree::isDescendantOf(const Frame* ancestor) const 303 { 304 if (!ancestor) 305 return false; 306 307 if (m_thisFrame->page() != ancestor->page()) 308 return false; 309 310 for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent()) 311 if (frame == ancestor) 312 return true; 313 return false; 314 } 315 316 Frame* FrameTree::traverseNext(const Frame* stayWithin) const 317 { 318 Frame* child = firstChild(); 319 if (child) { 320 ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin)); 321 return child; 322 } 323 324 if (m_thisFrame == stayWithin) 325 return 0; 326 327 Frame* sibling = nextSibling(); 328 if (sibling) { 329 ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin)); 330 return sibling; 331 } 332 333 Frame* frame = m_thisFrame; 334 while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) { 335 frame = frame->tree()->parent(); 336 if (!frame) 337 return 0; 338 sibling = frame->tree()->nextSibling(); 339 } 340 341 if (frame) { 342 ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin)); 343 return sibling; 344 } 345 346 return 0; 347 } 348 349 Frame* FrameTree::traverseNextWithWrap(bool wrap) const 350 { 351 if (Frame* result = traverseNext()) 352 return result; 353 354 if (wrap) 355 return m_thisFrame->page()->mainFrame(); 356 357 return 0; 358 } 359 360 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const 361 { 362 // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm 363 364 if (Frame* prevSibling = previousSibling()) 365 return prevSibling->tree()->deepLastChild(); 366 if (Frame* parentFrame = parent()) 367 return parentFrame; 368 369 // no siblings, no parent, self==top 370 if (wrap) 371 return deepLastChild(); 372 373 // top view is always the last one in this ordering, so prev is nil without wrap 374 return 0; 375 } 376 377 Frame* FrameTree::deepLastChild() const 378 { 379 Frame* result = m_thisFrame; 380 for (Frame* last = lastChild(); last; last = last->tree()->lastChild()) 381 result = last; 382 383 return result; 384 } 385 386 Frame* FrameTree::top() const 387 { 388 Frame* frame = m_thisFrame; 389 for (Frame* parent = m_thisFrame; parent; parent = parent->tree()->parent()) 390 frame = parent; 391 return frame; 392 } 393 394 } // namespace WebCore 395 396 #ifndef NDEBUG 397 398 static void printIndent(int indent) 399 { 400 for (int i = 0; i < indent; ++i) 401 printf(" "); 402 } 403 404 static void printFrames(const WebCore::Frame* frame, const WebCore::Frame* targetFrame, int indent) 405 { 406 if (frame == targetFrame) { 407 printf("--> "); 408 printIndent(indent - 1); 409 } else 410 printIndent(indent); 411 412 WebCore::FrameView* view = frame->view(); 413 printf("Frame %p %dx%d\n", frame, view ? view->width() : 0, view ? view->height() : 0); 414 printIndent(indent); 415 printf(" ownerElement=%p\n", frame->ownerElement()); 416 printIndent(indent); 417 printf(" frameView=%p\n", view); 418 printIndent(indent); 419 printf(" document=%p\n", frame->document()); 420 printIndent(indent); 421 printf(" uri=%s\n\n", frame->document()->documentURI().utf8().data()); 422 423 for (WebCore::Frame* child = frame->tree()->firstChild(); child; child = child->tree()->nextSibling()) 424 printFrames(child, targetFrame, indent + 1); 425 } 426 427 void showFrameTree(const WebCore::Frame* frame) 428 { 429 if (!frame) { 430 printf("Null input frame\n"); 431 return; 432 } 433 434 printFrames(frame->tree()->top(), frame, 0); 435 } 436 437 #endif 438