Line data Source code
1 : /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #include "nsFrameList.h"
7 :
8 : #include "mozilla/ArenaObjectID.h"
9 : #include "nsBidiPresUtils.h"
10 : #include "nsContainerFrame.h"
11 : #include "nsGkAtoms.h"
12 : #include "nsILineIterator.h"
13 : #include "nsIPresShell.h"
14 : #include "nsLayoutUtils.h"
15 : #include "nsPresContext.h"
16 :
17 : using namespace mozilla;
18 :
19 : namespace mozilla {
20 : namespace layout {
21 : namespace detail {
22 : const AlignedFrameListBytes gEmptyFrameListBytes = { 0 };
23 : } // namespace detail
24 : } // namespace layout
25 : } // namespace mozilla
26 :
27 : void*
28 15 : nsFrameList::operator new(size_t sz, nsIPresShell* aPresShell)
29 : {
30 15 : return aPresShell->AllocateByObjectID(eArenaObjectID_nsFrameList, sz);
31 : }
32 :
33 : void
34 1 : nsFrameList::Delete(nsIPresShell* aPresShell)
35 : {
36 1 : NS_PRECONDITION(this != &EmptyList(), "Shouldn't Delete() this list");
37 1 : NS_ASSERTION(IsEmpty(), "Shouldn't Delete() a non-empty list");
38 :
39 1 : aPresShell->FreeByObjectID(eArenaObjectID_nsFrameList, this);
40 1 : }
41 :
42 : void
43 0 : nsFrameList::DestroyFrames()
44 : {
45 0 : while (nsIFrame* frame = RemoveFirstChild()) {
46 0 : frame->Destroy();
47 0 : }
48 0 : mLastChild = nullptr;
49 0 : }
50 :
51 : void
52 89 : nsFrameList::DestroyFramesFrom(nsIFrame* aDestructRoot)
53 : {
54 89 : NS_PRECONDITION(aDestructRoot, "Missing destruct root");
55 :
56 182 : while (nsIFrame* frame = RemoveFirstChild()) {
57 93 : frame->DestroyFrom(aDestructRoot);
58 93 : }
59 89 : mLastChild = nullptr;
60 89 : }
61 :
62 : void
63 336 : nsFrameList::SetFrames(nsIFrame* aFrameList)
64 : {
65 336 : NS_PRECONDITION(!mFirstChild, "Losing frames");
66 :
67 336 : mFirstChild = aFrameList;
68 336 : mLastChild = nsLayoutUtils::GetLastSibling(mFirstChild);
69 336 : }
70 :
71 : void
72 141 : nsFrameList::RemoveFrame(nsIFrame* aFrame)
73 : {
74 141 : NS_PRECONDITION(aFrame, "null ptr");
75 : #ifdef DEBUG_FRAME_LIST
76 : // ContainsFrame is O(N)
77 : NS_PRECONDITION(ContainsFrame(aFrame), "wrong list");
78 : #endif
79 :
80 141 : nsIFrame* nextFrame = aFrame->GetNextSibling();
81 141 : if (aFrame == mFirstChild) {
82 123 : mFirstChild = nextFrame;
83 123 : aFrame->SetNextSibling(nullptr);
84 123 : if (!nextFrame) {
85 69 : mLastChild = nullptr;
86 : }
87 : }
88 : else {
89 18 : nsIFrame* prevSibling = aFrame->GetPrevSibling();
90 18 : NS_ASSERTION(prevSibling && prevSibling->GetNextSibling() == aFrame,
91 : "Broken frame linkage");
92 18 : prevSibling->SetNextSibling(nextFrame);
93 18 : aFrame->SetNextSibling(nullptr);
94 18 : if (!nextFrame) {
95 9 : mLastChild = prevSibling;
96 : }
97 : }
98 141 : }
99 :
100 : nsFrameList
101 0 : nsFrameList::RemoveFramesAfter(nsIFrame* aAfterFrame)
102 : {
103 0 : if (!aAfterFrame) {
104 0 : nsFrameList result;
105 0 : result.InsertFrames(nullptr, nullptr, *this);
106 0 : return result;
107 : }
108 :
109 0 : NS_PRECONDITION(NotEmpty(), "illegal operation on empty list");
110 : #ifdef DEBUG_FRAME_LIST
111 : NS_PRECONDITION(ContainsFrame(aAfterFrame), "wrong list");
112 : #endif
113 :
114 0 : nsIFrame* tail = aAfterFrame->GetNextSibling();
115 : // if (!tail) return EmptyList(); -- worth optimizing this case?
116 0 : nsIFrame* oldLastChild = mLastChild;
117 0 : mLastChild = aAfterFrame;
118 0 : aAfterFrame->SetNextSibling(nullptr);
119 0 : return nsFrameList(tail, tail ? oldLastChild : nullptr);
120 : }
121 :
122 : nsIFrame*
123 188 : nsFrameList::RemoveFirstChild()
124 : {
125 188 : if (mFirstChild) {
126 99 : nsIFrame* firstChild = mFirstChild;
127 99 : RemoveFrame(firstChild);
128 99 : return firstChild;
129 : }
130 89 : return nullptr;
131 : }
132 :
133 : void
134 8 : nsFrameList::DestroyFrame(nsIFrame* aFrame)
135 : {
136 8 : NS_PRECONDITION(aFrame, "null ptr");
137 8 : RemoveFrame(aFrame);
138 8 : aFrame->Destroy();
139 8 : }
140 :
141 : nsFrameList::Slice
142 120 : nsFrameList::InsertFrames(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
143 : nsFrameList& aFrameList)
144 : {
145 120 : NS_PRECONDITION(aFrameList.NotEmpty(), "Unexpected empty list");
146 :
147 120 : if (aParent) {
148 43 : aFrameList.ApplySetParent(aParent);
149 : }
150 :
151 120 : NS_ASSERTION(IsEmpty() ||
152 : FirstChild()->GetParent() == aFrameList.FirstChild()->GetParent(),
153 : "frame to add has different parent");
154 120 : NS_ASSERTION(!aPrevSibling ||
155 : aPrevSibling->GetParent() == aFrameList.FirstChild()->GetParent(),
156 : "prev sibling has different parent");
157 : #ifdef DEBUG_FRAME_LIST
158 : // ContainsFrame is O(N)
159 : NS_ASSERTION(!aPrevSibling || ContainsFrame(aPrevSibling),
160 : "prev sibling is not on this list");
161 : #endif
162 :
163 120 : nsIFrame* firstNewFrame = aFrameList.FirstChild();
164 : nsIFrame* nextSibling;
165 120 : if (aPrevSibling) {
166 23 : nextSibling = aPrevSibling->GetNextSibling();
167 23 : aPrevSibling->SetNextSibling(firstNewFrame);
168 : }
169 : else {
170 97 : nextSibling = mFirstChild;
171 97 : mFirstChild = firstNewFrame;
172 : }
173 :
174 120 : nsIFrame* lastNewFrame = aFrameList.LastChild();
175 120 : lastNewFrame->SetNextSibling(nextSibling);
176 120 : if (!nextSibling) {
177 100 : mLastChild = lastNewFrame;
178 : }
179 :
180 120 : VerifyList();
181 :
182 120 : aFrameList.Clear();
183 120 : return Slice(*this, firstNewFrame, nextSibling);
184 : }
185 :
186 : nsFrameList
187 0 : nsFrameList::ExtractHead(FrameLinkEnumerator& aLink)
188 : {
189 0 : NS_PRECONDITION(&aLink.List() == this, "Unexpected list");
190 0 : NS_PRECONDITION(!aLink.PrevFrame() ||
191 : aLink.PrevFrame()->GetNextSibling() ==
192 : aLink.NextFrame(),
193 : "Unexpected PrevFrame()");
194 0 : NS_PRECONDITION(aLink.PrevFrame() ||
195 : aLink.NextFrame() == FirstChild(),
196 : "Unexpected NextFrame()");
197 0 : NS_PRECONDITION(!aLink.PrevFrame() ||
198 : aLink.NextFrame() != FirstChild(),
199 : "Unexpected NextFrame()");
200 0 : NS_PRECONDITION(aLink.mEnd == nullptr,
201 : "Unexpected mEnd for frame link enumerator");
202 :
203 0 : nsIFrame* prev = aLink.PrevFrame();
204 0 : nsIFrame* newFirstFrame = nullptr;
205 0 : if (prev) {
206 : // Truncate the list after |prev| and hand the first part to our new list.
207 0 : prev->SetNextSibling(nullptr);
208 0 : newFirstFrame = mFirstChild;
209 0 : mFirstChild = aLink.NextFrame();
210 0 : if (!mFirstChild) { // we handed over the whole list
211 0 : mLastChild = nullptr;
212 : }
213 :
214 : // Now make sure aLink doesn't point to a frame we no longer have.
215 0 : aLink.mPrev = nullptr;
216 : }
217 : // else aLink is pointing to before our first frame. Nothing to do.
218 :
219 0 : return nsFrameList(newFirstFrame, prev);
220 : }
221 :
222 : nsFrameList
223 0 : nsFrameList::ExtractTail(FrameLinkEnumerator& aLink)
224 : {
225 0 : NS_PRECONDITION(&aLink.List() == this, "Unexpected list");
226 0 : NS_PRECONDITION(!aLink.PrevFrame() ||
227 : aLink.PrevFrame()->GetNextSibling() ==
228 : aLink.NextFrame(),
229 : "Unexpected PrevFrame()");
230 0 : NS_PRECONDITION(aLink.PrevFrame() ||
231 : aLink.NextFrame() == FirstChild(),
232 : "Unexpected NextFrame()");
233 0 : NS_PRECONDITION(!aLink.PrevFrame() ||
234 : aLink.NextFrame() != FirstChild(),
235 : "Unexpected NextFrame()");
236 0 : NS_PRECONDITION(aLink.mEnd == nullptr,
237 : "Unexpected mEnd for frame link enumerator");
238 :
239 0 : nsIFrame* prev = aLink.PrevFrame();
240 : nsIFrame* newFirstFrame;
241 : nsIFrame* newLastFrame;
242 0 : if (prev) {
243 : // Truncate the list after |prev| and hand the second part to our new list
244 0 : prev->SetNextSibling(nullptr);
245 0 : newFirstFrame = aLink.NextFrame();
246 0 : newLastFrame = newFirstFrame ? mLastChild : nullptr;
247 0 : mLastChild = prev;
248 : } else {
249 : // Hand the whole list over to our new list
250 0 : newFirstFrame = mFirstChild;
251 0 : newLastFrame = mLastChild;
252 0 : Clear();
253 : }
254 :
255 : // Now make sure aLink doesn't point to a frame we no longer have.
256 0 : aLink.mFrame = nullptr;
257 :
258 0 : NS_POSTCONDITION(aLink.AtEnd(), "What's going on here?");
259 :
260 0 : return nsFrameList(newFirstFrame, newLastFrame);
261 : }
262 :
263 : nsIFrame*
264 111 : nsFrameList::FrameAt(int32_t aIndex) const
265 : {
266 111 : NS_PRECONDITION(aIndex >= 0, "invalid arg");
267 111 : if (aIndex < 0) return nullptr;
268 111 : nsIFrame* frame = mFirstChild;
269 111 : while ((aIndex-- > 0) && frame) {
270 0 : frame = frame->GetNextSibling();
271 : }
272 111 : return frame;
273 : }
274 :
275 : int32_t
276 0 : nsFrameList::IndexOf(nsIFrame* aFrame) const
277 : {
278 0 : int32_t count = 0;
279 0 : for (nsIFrame* f = mFirstChild; f; f = f->GetNextSibling()) {
280 0 : if (f == aFrame)
281 0 : return count;
282 0 : ++count;
283 : }
284 0 : return -1;
285 : }
286 :
287 : bool
288 39 : nsFrameList::ContainsFrame(const nsIFrame* aFrame) const
289 : {
290 39 : NS_PRECONDITION(aFrame, "null ptr");
291 :
292 39 : nsIFrame* frame = mFirstChild;
293 177 : while (frame) {
294 108 : if (frame == aFrame) {
295 39 : return true;
296 : }
297 69 : frame = frame->GetNextSibling();
298 : }
299 0 : return false;
300 : }
301 :
302 : int32_t
303 1080 : nsFrameList::GetLength() const
304 : {
305 1080 : int32_t count = 0;
306 1080 : nsIFrame* frame = mFirstChild;
307 2366 : while (frame) {
308 643 : count++;
309 643 : frame = frame->GetNextSibling();
310 : }
311 1080 : return count;
312 : }
313 :
314 : void
315 43 : nsFrameList::ApplySetParent(nsContainerFrame* aParent) const
316 : {
317 43 : NS_ASSERTION(aParent, "null ptr");
318 :
319 105 : for (nsIFrame* f = FirstChild(); f; f = f->GetNextSibling()) {
320 62 : f->SetParent(aParent);
321 : }
322 43 : }
323 :
324 : /* static */ void
325 0 : nsFrameList::UnhookFrameFromSiblings(nsIFrame* aFrame)
326 : {
327 0 : MOZ_ASSERT(aFrame->GetPrevSibling() && aFrame->GetNextSibling());
328 0 : nsIFrame* const nextSibling = aFrame->GetNextSibling();
329 0 : nsIFrame* const prevSibling = aFrame->GetPrevSibling();
330 0 : aFrame->SetNextSibling(nullptr);
331 0 : prevSibling->SetNextSibling(nextSibling);
332 0 : MOZ_ASSERT(!aFrame->GetPrevSibling() && !aFrame->GetNextSibling());
333 0 : }
334 :
335 : #ifdef DEBUG_FRAME_DUMP
336 : void
337 0 : nsFrameList::List(FILE* out) const
338 : {
339 0 : fprintf_stderr(out, "<\n");
340 0 : for (nsIFrame* frame = mFirstChild; frame;
341 : frame = frame->GetNextSibling()) {
342 0 : frame->List(out, " ");
343 : }
344 0 : fprintf_stderr(out, ">\n");
345 0 : }
346 : #endif
347 :
348 : nsIFrame*
349 0 : nsFrameList::GetPrevVisualFor(nsIFrame* aFrame) const
350 : {
351 0 : if (!mFirstChild)
352 0 : return nullptr;
353 :
354 0 : nsIFrame* parent = mFirstChild->GetParent();
355 0 : if (!parent)
356 0 : return aFrame ? aFrame->GetPrevSibling() : LastChild();
357 :
358 0 : nsBidiDirection paraDir = nsBidiPresUtils::ParagraphDirection(mFirstChild);
359 :
360 0 : nsAutoLineIterator iter = parent->GetLineIterator();
361 0 : if (!iter) {
362 : // Parent is not a block Frame
363 0 : if (parent->IsLineFrame()) {
364 : // Line frames are not bidi-splittable, so need to consider bidi reordering
365 0 : if (paraDir == NSBIDI_LTR) {
366 0 : return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
367 : } else { // RTL
368 0 : return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
369 : }
370 : } else {
371 : // Just get the next or prev sibling, depending on block and frame direction.
372 0 : if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild)) {
373 0 : return aFrame ? aFrame->GetPrevSibling() : LastChild();
374 : } else {
375 0 : return aFrame ? aFrame->GetNextSibling() : mFirstChild;
376 : }
377 : }
378 : }
379 :
380 : // Parent is a block frame, so use the LineIterator to find the previous visual
381 : // sibling on this line, or the last one on the previous line.
382 :
383 : int32_t thisLine;
384 0 : if (aFrame) {
385 0 : thisLine = iter->FindLineContaining(aFrame);
386 0 : if (thisLine < 0)
387 0 : return nullptr;
388 : } else {
389 0 : thisLine = iter->GetNumLines();
390 : }
391 :
392 0 : nsIFrame* frame = nullptr;
393 : nsIFrame* firstFrameOnLine;
394 : int32_t numFramesOnLine;
395 0 : nsRect lineBounds;
396 :
397 0 : if (aFrame) {
398 0 : iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds);
399 :
400 0 : if (paraDir == NSBIDI_LTR) {
401 0 : frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
402 : } else { // RTL
403 0 : frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
404 : }
405 : }
406 :
407 0 : if (!frame && thisLine > 0) {
408 : // Get the last frame of the previous line
409 0 : iter->GetLine(thisLine - 1, &firstFrameOnLine, &numFramesOnLine, lineBounds);
410 :
411 0 : if (paraDir == NSBIDI_LTR) {
412 0 : frame = nsBidiPresUtils::GetFrameToLeftOf(nullptr, firstFrameOnLine, numFramesOnLine);
413 : } else { // RTL
414 0 : frame = nsBidiPresUtils::GetFrameToRightOf(nullptr, firstFrameOnLine, numFramesOnLine);
415 : }
416 : }
417 0 : return frame;
418 : }
419 :
420 : nsIFrame*
421 0 : nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const
422 : {
423 0 : if (!mFirstChild)
424 0 : return nullptr;
425 :
426 0 : nsIFrame* parent = mFirstChild->GetParent();
427 0 : if (!parent)
428 0 : return aFrame ? aFrame->GetPrevSibling() : mFirstChild;
429 :
430 0 : nsBidiDirection paraDir = nsBidiPresUtils::ParagraphDirection(mFirstChild);
431 :
432 0 : nsAutoLineIterator iter = parent->GetLineIterator();
433 0 : if (!iter) {
434 : // Parent is not a block Frame
435 0 : if (parent->IsLineFrame()) {
436 : // Line frames are not bidi-splittable, so need to consider bidi reordering
437 0 : if (paraDir == NSBIDI_LTR) {
438 0 : return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
439 : } else { // RTL
440 0 : return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
441 : }
442 : } else {
443 : // Just get the next or prev sibling, depending on block and frame direction.
444 0 : if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild)) {
445 0 : return aFrame ? aFrame->GetNextSibling() : mFirstChild;
446 : } else {
447 0 : return aFrame ? aFrame->GetPrevSibling() : LastChild();
448 : }
449 : }
450 : }
451 :
452 : // Parent is a block frame, so use the LineIterator to find the next visual
453 : // sibling on this line, or the first one on the next line.
454 :
455 : int32_t thisLine;
456 0 : if (aFrame) {
457 0 : thisLine = iter->FindLineContaining(aFrame);
458 0 : if (thisLine < 0)
459 0 : return nullptr;
460 : } else {
461 0 : thisLine = -1;
462 : }
463 :
464 0 : nsIFrame* frame = nullptr;
465 : nsIFrame* firstFrameOnLine;
466 : int32_t numFramesOnLine;
467 0 : nsRect lineBounds;
468 :
469 0 : if (aFrame) {
470 0 : iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds);
471 :
472 0 : if (paraDir == NSBIDI_LTR) {
473 0 : frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
474 : } else { // RTL
475 0 : frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
476 : }
477 : }
478 :
479 0 : int32_t numLines = iter->GetNumLines();
480 0 : if (!frame && thisLine < numLines - 1) {
481 : // Get the first frame of the next line
482 0 : iter->GetLine(thisLine + 1, &firstFrameOnLine, &numFramesOnLine, lineBounds);
483 :
484 0 : if (paraDir == NSBIDI_LTR) {
485 0 : frame = nsBidiPresUtils::GetFrameToRightOf(nullptr, firstFrameOnLine, numFramesOnLine);
486 : } else { // RTL
487 0 : frame = nsBidiPresUtils::GetFrameToLeftOf(nullptr, firstFrameOnLine, numFramesOnLine);
488 : }
489 : }
490 0 : return frame;
491 : }
492 :
493 : #ifdef DEBUG_FRAME_LIST
494 : void
495 : nsFrameList::VerifyList() const
496 : {
497 : NS_ASSERTION((mFirstChild == nullptr) == (mLastChild == nullptr),
498 : "bad list state");
499 :
500 : if (IsEmpty()) {
501 : return;
502 : }
503 :
504 : // Simple algorithm to find a loop in a linked list -- advance pointers
505 : // through it at speeds of 1 and 2, and if they ever get to be equal bail
506 : NS_ASSERTION(!mFirstChild->GetPrevSibling(), "bad prev sibling pointer");
507 : nsIFrame *first = mFirstChild, *second = mFirstChild;
508 : for (;;) {
509 : first = first->GetNextSibling();
510 : second = second->GetNextSibling();
511 : if (!second) {
512 : break;
513 : }
514 : NS_ASSERTION(second->GetPrevSibling()->GetNextSibling() == second,
515 : "bad prev sibling pointer");
516 : second = second->GetNextSibling();
517 : if (first == second) {
518 : // Loop detected! Since second advances faster, they can't both be null;
519 : // we would have broken out of the loop long ago.
520 : NS_ERROR("loop in frame list. This will probably hang soon.");
521 : return;
522 : }
523 : if (!second) {
524 : break;
525 : }
526 : NS_ASSERTION(second->GetPrevSibling()->GetNextSibling() == second,
527 : "bad prev sibling pointer");
528 : }
529 :
530 : NS_ASSERTION(mLastChild == nsLayoutUtils::GetLastSibling(mFirstChild),
531 : "bogus mLastChild");
532 : // XXX we should also assert that all GetParent() are either null or
533 : // the same non-null value, but nsCSSFrameConstructor::nsFrameItems
534 : // prevents that, e.g. table captions.
535 : }
536 : #endif
537 :
538 : namespace mozilla {
539 : namespace layout {
540 :
541 64 : AutoFrameListPtr::~AutoFrameListPtr()
542 : {
543 32 : if (mFrameList) {
544 0 : mFrameList->Delete(mPresContext->PresShell());
545 : }
546 32 : }
547 :
548 : } // namespace layout
549 : } // namespace mozilla
|
