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