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/frame/FrameClient.h" 26 #include "core/frame/FrameView.h" 27 #include "core/frame/LocalFrame.h" 28 #include "core/frame/RemoteFrame.h" 29 #include "core/frame/RemoteFrameView.h" 30 #include "core/page/Page.h" 31 #include "wtf/Vector.h" 32 #include "wtf/text/CString.h" 33 #include "wtf/text/StringBuilder.h" 34 35 using std::swap; 36 37 namespace WebCore { 38 39 namespace { 40 41 const unsigned invalidChildCount = ~0; 42 43 } // namespace 44 45 FrameTree::FrameTree(Frame* thisFrame) 46 : m_thisFrame(thisFrame) 47 , m_scopedChildCount(invalidChildCount) 48 { 49 } 50 51 FrameTree::~FrameTree() 52 { 53 // FIXME: Why is this here? Doesn't this parallel what we already do in ~LocalFrame? 54 for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) { 55 if (child->isLocalFrame()) 56 toLocalFrame(child)->setView(nullptr); 57 else if (child->isRemoteFrame()) 58 toRemoteFrame(child)->setView(nullptr); 59 } 60 } 61 62 void FrameTree::setName(const AtomicString& name, const AtomicString& fallbackName) 63 { 64 m_name = name; 65 if (!parent()) { 66 m_uniqueName = name; 67 return; 68 } 69 m_uniqueName = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName. 70 m_uniqueName = parent()->tree().uniqueChildName(name.isEmpty() ? fallbackName : name); 71 } 72 73 Frame* FrameTree::parent() const 74 { 75 if (!m_thisFrame->client()) 76 return 0; 77 return m_thisFrame->client()->parent(); 78 } 79 80 Frame* FrameTree::top() const 81 { 82 // FIXME: top() should never return null, so here are some hacks to deal 83 // with EmptyFrameLoaderClient and cases where the frame is detached 84 // already... 85 if (!m_thisFrame->client()) 86 return m_thisFrame; 87 Frame* candidate = m_thisFrame->client()->top(); 88 return candidate ? candidate : m_thisFrame; 89 } 90 91 Frame* FrameTree::previousSibling() const 92 { 93 if (!m_thisFrame->client()) 94 return 0; 95 return m_thisFrame->client()->previousSibling(); 96 } 97 98 Frame* FrameTree::nextSibling() const 99 { 100 if (!m_thisFrame->client()) 101 return 0; 102 return m_thisFrame->client()->nextSibling(); 103 } 104 105 Frame* FrameTree::firstChild() const 106 { 107 if (!m_thisFrame->client()) 108 return 0; 109 return m_thisFrame->client()->firstChild(); 110 } 111 112 Frame* FrameTree::lastChild() const 113 { 114 if (!m_thisFrame->client()) 115 return 0; 116 return m_thisFrame->client()->lastChild(); 117 } 118 119 bool FrameTree::uniqueNameExists(const AtomicString& name) const 120 { 121 for (Frame* frame = top(); frame; frame = frame->tree().traverseNext()) { 122 if (frame->tree().uniqueName() == name) 123 return true; 124 } 125 return false; 126 } 127 128 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const 129 { 130 if (!requestedName.isEmpty() && !uniqueNameExists(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() - 1); 166 name.appendLiteral("-->-->"); 167 168 return name.toAtomicString(); 169 } 170 171 Frame* FrameTree::scopedChild(unsigned index) const 172 { 173 if (!m_thisFrame->isLocalFrame()) 174 return 0; 175 TreeScope* scope = toLocalFrame(m_thisFrame)->document(); 176 if (!scope) 177 return 0; 178 179 unsigned scopedIndex = 0; 180 for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) { 181 if (result->isLocalFrame() && toLocalFrame(result)->inScope(scope)) { 182 if (scopedIndex == index) 183 return result; 184 scopedIndex++; 185 } 186 } 187 188 return 0; 189 } 190 191 Frame* FrameTree::scopedChild(const AtomicString& name) const 192 { 193 if (!m_thisFrame->isLocalFrame()) 194 return 0; 195 196 TreeScope* scope = toLocalFrame(m_thisFrame)->document(); 197 if (!scope) 198 return 0; 199 200 for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) 201 if (child->tree().name() == name && child->isLocalFrame() && toLocalFrame(child)->inScope(scope)) 202 return child; 203 return 0; 204 } 205 206 inline unsigned FrameTree::scopedChildCount(TreeScope* scope) const 207 { 208 if (!scope) 209 return 0; 210 211 unsigned scopedCount = 0; 212 for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) { 213 if (result->isLocalFrame() && toLocalFrame(result)->inScope(scope)) 214 scopedCount++; 215 } 216 217 return scopedCount; 218 } 219 220 unsigned FrameTree::scopedChildCount() const 221 { 222 if (m_scopedChildCount == invalidChildCount) 223 m_scopedChildCount = scopedChildCount(toLocalFrame(m_thisFrame)->document()); 224 return m_scopedChildCount; 225 } 226 227 void FrameTree::invalidateScopedChildCount() 228 { 229 m_scopedChildCount = invalidChildCount; 230 } 231 232 unsigned FrameTree::childCount() const 233 { 234 unsigned count = 0; 235 for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) 236 ++count; 237 return count; 238 } 239 240 Frame* FrameTree::child(const AtomicString& name) const 241 { 242 for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) 243 if (child->tree().name() == name) 244 return child; 245 return 0; 246 } 247 248 Frame* FrameTree::find(const AtomicString& name) const 249 { 250 if (name == "_self" || name == "_current" || name.isEmpty()) 251 return m_thisFrame; 252 253 if (name == "_top") 254 return top(); 255 256 if (name == "_parent") 257 return parent() ? parent() : m_thisFrame; 258 259 // Since "_blank" should never be any frame's name, the following just amounts to an optimization. 260 if (name == "_blank") 261 return 0; 262 263 // Search subtree starting with this frame first. 264 for (Frame* frame = m_thisFrame; frame; frame = frame->tree().traverseNext(m_thisFrame)) 265 if (frame->tree().name() == name) 266 return frame; 267 268 // Search the entire tree for this page next. 269 Page* page = m_thisFrame->page(); 270 271 // The frame could have been detached from the page, so check it. 272 if (!page) 273 return 0; 274 275 for (Frame* frame = page->mainFrame(); frame; frame = frame->tree().traverseNext()) 276 if (frame->tree().name() == name) 277 return frame; 278 279 // Search the entire tree of each of the other pages in this namespace. 280 // FIXME: Is random order OK? 281 const HashSet<Page*>& pages = Page::ordinaryPages(); 282 HashSet<Page*>::const_iterator end = pages.end(); 283 for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) { 284 Page* otherPage = *it; 285 if (otherPage != page) { 286 for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree().traverseNext()) { 287 if (frame->tree().name() == name) 288 return frame; 289 } 290 } 291 } 292 293 return 0; 294 } 295 296 bool FrameTree::isDescendantOf(const Frame* ancestor) const 297 { 298 if (!ancestor) 299 return false; 300 301 if (m_thisFrame->page() != ancestor->page()) 302 return false; 303 304 for (Frame* frame = m_thisFrame; frame; frame = frame->tree().parent()) 305 if (frame == ancestor) 306 return true; 307 return false; 308 } 309 310 Frame* FrameTree::traverseNext(const Frame* stayWithin) const 311 { 312 Frame* child = firstChild(); 313 if (child) { 314 ASSERT(!stayWithin || child->tree().isDescendantOf(stayWithin)); 315 return child; 316 } 317 318 if (m_thisFrame == stayWithin) 319 return 0; 320 321 Frame* sibling = nextSibling(); 322 if (sibling) { 323 ASSERT(!stayWithin || sibling->tree().isDescendantOf(stayWithin)); 324 return sibling; 325 } 326 327 Frame* frame = m_thisFrame; 328 while (!sibling && (!stayWithin || frame->tree().parent() != stayWithin)) { 329 frame = frame->tree().parent(); 330 if (!frame) 331 return 0; 332 sibling = frame->tree().nextSibling(); 333 } 334 335 if (frame) { 336 ASSERT(!stayWithin || !sibling || sibling->tree().isDescendantOf(stayWithin)); 337 return sibling; 338 } 339 340 return 0; 341 } 342 343 Frame* FrameTree::traverseNextWithWrap(bool wrap) const 344 { 345 if (Frame* result = traverseNext()) 346 return result; 347 348 if (wrap) 349 return m_thisFrame->page()->mainFrame(); 350 351 return 0; 352 } 353 354 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const 355 { 356 // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm 357 358 if (Frame* prevSibling = previousSibling()) 359 return prevSibling->tree().deepLastChild(); 360 if (Frame* parentFrame = parent()) 361 return parentFrame; 362 363 // no siblings, no parent, self==top 364 if (wrap) 365 return deepLastChild(); 366 367 // top view is always the last one in this ordering, so prev is nil without wrap 368 return 0; 369 } 370 371 Frame* FrameTree::deepLastChild() const 372 { 373 Frame* result = m_thisFrame; 374 for (Frame* last = lastChild(); last; last = last->tree().lastChild()) 375 result = last; 376 377 return result; 378 } 379 380 } // namespace WebCore 381 382 #ifndef NDEBUG 383 384 static void printIndent(int indent) 385 { 386 for (int i = 0; i < indent; ++i) 387 printf(" "); 388 } 389 390 static void printFrames(const WebCore::Frame* frame, const WebCore::Frame* targetFrame, int indent) 391 { 392 if (frame == targetFrame) { 393 printf("--> "); 394 printIndent(indent - 1); 395 } else 396 printIndent(indent); 397 398 WebCore::FrameView* view = frame->isLocalFrame() ? toLocalFrame(frame)->view() : 0; 399 printf("Frame %p %dx%d\n", frame, view ? view->width() : 0, view ? view->height() : 0); 400 printIndent(indent); 401 printf(" owner=%p\n", frame->owner()); 402 printIndent(indent); 403 printf(" frameView=%p\n", view); 404 printIndent(indent); 405 printf(" document=%p\n", frame->isLocalFrame() ? toLocalFrame(frame)->document() : 0); 406 printIndent(indent); 407 printf(" uri=%s\n\n", frame->isLocalFrame() ? toLocalFrame(frame)->document()->url().string().utf8().data() : 0); 408 409 for (WebCore::Frame* child = frame->tree().firstChild(); child; child = child->tree().nextSibling()) 410 printFrames(child, targetFrame, indent + 1); 411 } 412 413 void showFrameTree(const WebCore::Frame* frame) 414 { 415 if (!frame) { 416 printf("Null input frame\n"); 417 return; 418 } 419 420 printFrames(frame->tree().top(), frame, 0); 421 } 422 423 #endif 424