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