1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #include "nsFrameList.h"
9 #include "mozilla/intl/BidiEmbeddingLevel.h"
10 #include "mozilla/ArenaObjectID.h"
11 #include "mozilla/PresShell.h"
12 #include "nsBidiPresUtils.h"
13 #include "nsContainerFrame.h"
14 #include "nsGkAtoms.h"
15 #include "nsILineIterator.h"
16 #include "nsLayoutUtils.h"
17 #include "nsPresContext.h"
19 using namespace mozilla
;
23 const AlignedFrameListBytes gEmptyFrameListBytes
= {0};
25 } // namespace mozilla
27 void* nsFrameList::operator new(size_t sz
, mozilla::PresShell
* aPresShell
) {
28 return aPresShell
->AllocateByObjectID(eArenaObjectID_nsFrameList
, sz
);
31 void nsFrameList::Delete(mozilla::PresShell
* aPresShell
) {
32 MOZ_ASSERT(this != &EmptyList(), "Shouldn't Delete() this list");
33 NS_ASSERTION(IsEmpty(), "Shouldn't Delete() a non-empty list");
35 aPresShell
->FreeByObjectID(eArenaObjectID_nsFrameList
, this);
38 void nsFrameList::DestroyFrames(FrameDestroyContext
& aContext
) {
39 while (nsIFrame
* frame
= RemoveFirstChild()) {
40 frame
->Destroy(aContext
);
45 void nsFrameList::RemoveFrame(nsIFrame
* aFrame
) {
46 MOZ_ASSERT(aFrame
, "null ptr");
47 #ifdef DEBUG_FRAME_LIST
48 // ContainsFrame is O(N)
49 MOZ_ASSERT(ContainsFrame(aFrame
), "wrong list");
52 nsIFrame
* nextFrame
= aFrame
->GetNextSibling();
53 if (aFrame
== mFirstChild
) {
54 mFirstChild
= nextFrame
;
55 aFrame
->SetNextSibling(nullptr);
60 nsIFrame
* prevSibling
= aFrame
->GetPrevSibling();
61 NS_ASSERTION(prevSibling
&& prevSibling
->GetNextSibling() == aFrame
,
62 "Broken frame linkage");
63 prevSibling
->SetNextSibling(nextFrame
);
64 aFrame
->SetNextSibling(nullptr);
66 mLastChild
= prevSibling
;
71 nsFrameList
nsFrameList::TakeFramesAfter(nsIFrame
* aFrame
) {
73 return std::move(*this);
76 MOZ_ASSERT(ContainsFrame(aFrame
), "aFrame is not on this list!");
78 nsIFrame
* newFirstChild
= aFrame
->GetNextSibling();
83 nsIFrame
* newLastChild
= mLastChild
;
85 mLastChild
->SetNextSibling(nullptr);
86 return nsFrameList(newFirstChild
, newLastChild
);
89 nsIFrame
* nsFrameList::RemoveFirstChild() {
91 nsIFrame
* firstChild
= mFirstChild
;
92 RemoveFrame(firstChild
);
98 void nsFrameList::DestroyFrame(FrameDestroyContext
& aContext
,
100 MOZ_ASSERT(aFrame
, "null ptr");
102 aFrame
->Destroy(aContext
);
105 nsFrameList::Slice
nsFrameList::InsertFrames(nsContainerFrame
* aParent
,
106 nsIFrame
* aPrevSibling
,
107 nsFrameList
&& aFrameList
) {
108 MOZ_ASSERT(aFrameList
.NotEmpty(), "Unexpected empty list");
111 aFrameList
.ApplySetParent(aParent
);
114 NS_ASSERTION(IsEmpty() || FirstChild()->GetParent() ==
115 aFrameList
.FirstChild()->GetParent(),
116 "frame to add has different parent");
117 NS_ASSERTION(!aPrevSibling
|| aPrevSibling
->GetParent() ==
118 aFrameList
.FirstChild()->GetParent(),
119 "prev sibling has different parent");
120 #ifdef DEBUG_FRAME_LIST
121 // ContainsFrame is O(N)
122 NS_ASSERTION(!aPrevSibling
|| ContainsFrame(aPrevSibling
),
123 "prev sibling is not on this list");
126 nsIFrame
* firstNewFrame
= aFrameList
.FirstChild();
127 nsIFrame
* nextSibling
;
129 nextSibling
= aPrevSibling
->GetNextSibling();
130 aPrevSibling
->SetNextSibling(firstNewFrame
);
132 nextSibling
= mFirstChild
;
133 mFirstChild
= firstNewFrame
;
136 nsIFrame
* lastNewFrame
= aFrameList
.LastChild();
137 lastNewFrame
->SetNextSibling(nextSibling
);
139 mLastChild
= lastNewFrame
;
145 return Slice(firstNewFrame
, nextSibling
);
148 nsFrameList
nsFrameList::TakeFramesBefore(nsIFrame
* aFrame
) {
150 // We handed over the whole list.
151 return std::move(*this);
154 MOZ_ASSERT(ContainsFrame(aFrame
), "aFrame is not on this list!");
156 if (aFrame
== mFirstChild
) {
157 // aFrame is our first child. Nothing to extract.
158 return nsFrameList();
161 // Extract all previous siblings of aFrame as a new list.
162 nsIFrame
* prev
= aFrame
->GetPrevSibling();
163 nsIFrame
* newFirstChild
= mFirstChild
;
164 nsIFrame
* newLastChild
= prev
;
166 prev
->SetNextSibling(nullptr);
167 mFirstChild
= aFrame
;
169 return nsFrameList(newFirstChild
, newLastChild
);
172 nsIFrame
* nsFrameList::FrameAt(int32_t aIndex
) const {
173 MOZ_ASSERT(aIndex
>= 0, "invalid arg");
174 if (aIndex
< 0) return nullptr;
175 nsIFrame
* frame
= mFirstChild
;
176 while ((aIndex
-- > 0) && frame
) {
177 frame
= frame
->GetNextSibling();
182 int32_t nsFrameList::IndexOf(nsIFrame
* aFrame
) const {
184 for (nsIFrame
* f
= mFirstChild
; f
; f
= f
->GetNextSibling()) {
185 if (f
== aFrame
) return count
;
191 bool nsFrameList::ContainsFrame(const nsIFrame
* aFrame
) const {
192 MOZ_ASSERT(aFrame
, "null ptr");
194 nsIFrame
* frame
= mFirstChild
;
196 if (frame
== aFrame
) {
199 frame
= frame
->GetNextSibling();
204 int32_t nsFrameList::GetLength() const {
206 nsIFrame
* frame
= mFirstChild
;
209 frame
= frame
->GetNextSibling();
214 void nsFrameList::ApplySetParent(nsContainerFrame
* aParent
) const {
215 NS_ASSERTION(aParent
, "null ptr");
217 for (nsIFrame
* f
= FirstChild(); f
; f
= f
->GetNextSibling()) {
218 f
->SetParent(aParent
);
223 void nsFrameList::UnhookFrameFromSiblings(nsIFrame
* aFrame
) {
224 MOZ_ASSERT(aFrame
->GetPrevSibling() && aFrame
->GetNextSibling());
225 nsIFrame
* const nextSibling
= aFrame
->GetNextSibling();
226 nsIFrame
* const prevSibling
= aFrame
->GetPrevSibling();
227 aFrame
->SetNextSibling(nullptr);
228 prevSibling
->SetNextSibling(nextSibling
);
229 MOZ_ASSERT(!aFrame
->GetPrevSibling() && !aFrame
->GetNextSibling());
232 #ifdef DEBUG_FRAME_DUMP
233 void nsFrameList::List(FILE* out
) const {
234 fprintf_stderr(out
, "<\n");
235 for (nsIFrame
* frame
= mFirstChild
; frame
; frame
= frame
->GetNextSibling()) {
236 frame
->List(out
, " ");
238 fprintf_stderr(out
, ">\n");
242 nsIFrame
* nsFrameList::GetPrevVisualFor(nsIFrame
* aFrame
) const {
243 if (!mFirstChild
) return nullptr;
245 nsIFrame
* parent
= mFirstChild
->GetParent();
246 if (!parent
) return aFrame
? aFrame
->GetPrevSibling() : LastChild();
248 mozilla::intl::BidiDirection paraDir
=
249 nsBidiPresUtils::ParagraphDirection(mFirstChild
);
251 AutoAssertNoDomMutations guard
;
252 nsILineIterator
* iter
= parent
->GetLineIterator();
254 // Parent is not a block Frame
255 if (parent
->IsLineFrame()) {
256 // Line frames are not bidi-splittable, so need to consider bidi
258 if (paraDir
== mozilla::intl::BidiDirection::LTR
) {
259 return nsBidiPresUtils::GetFrameToLeftOf(aFrame
, mFirstChild
, -1);
261 return nsBidiPresUtils::GetFrameToRightOf(aFrame
, mFirstChild
, -1);
264 // Just get the next or prev sibling, depending on block and frame
266 if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild
)) {
267 return aFrame
? aFrame
->GetPrevSibling() : LastChild();
269 return aFrame
? aFrame
->GetNextSibling() : mFirstChild
;
274 // Parent is a block frame, so use the LineIterator to find the previous
275 // visual sibling on this line, or the last one on the previous line.
279 thisLine
= iter
->FindLineContaining(aFrame
);
280 if (thisLine
< 0) return nullptr;
282 thisLine
= iter
->GetNumLines();
285 nsIFrame
* frame
= nullptr;
288 auto line
= iter
->GetLine(thisLine
).unwrap();
290 if (paraDir
== mozilla::intl::BidiDirection::LTR
) {
291 frame
= nsBidiPresUtils::GetFrameToLeftOf(aFrame
, line
.mFirstFrameOnLine
,
292 line
.mNumFramesOnLine
);
294 frame
= nsBidiPresUtils::GetFrameToRightOf(aFrame
, line
.mFirstFrameOnLine
,
295 line
.mNumFramesOnLine
);
299 if (!frame
&& thisLine
> 0) {
300 // Get the last frame of the previous line
301 auto line
= iter
->GetLine(thisLine
- 1).unwrap();
303 if (paraDir
== mozilla::intl::BidiDirection::LTR
) {
304 frame
= nsBidiPresUtils::GetFrameToLeftOf(nullptr, line
.mFirstFrameOnLine
,
305 line
.mNumFramesOnLine
);
307 frame
= nsBidiPresUtils::GetFrameToRightOf(
308 nullptr, line
.mFirstFrameOnLine
, line
.mNumFramesOnLine
);
314 nsIFrame
* nsFrameList::GetNextVisualFor(nsIFrame
* aFrame
) const {
315 if (!mFirstChild
) return nullptr;
317 nsIFrame
* parent
= mFirstChild
->GetParent();
318 if (!parent
) return aFrame
? aFrame
->GetPrevSibling() : mFirstChild
;
320 mozilla::intl::BidiDirection paraDir
=
321 nsBidiPresUtils::ParagraphDirection(mFirstChild
);
323 AutoAssertNoDomMutations guard
;
324 nsILineIterator
* iter
= parent
->GetLineIterator();
326 // Parent is not a block Frame
327 if (parent
->IsLineFrame()) {
328 // Line frames are not bidi-splittable, so need to consider bidi
330 if (paraDir
== mozilla::intl::BidiDirection::LTR
) {
331 return nsBidiPresUtils::GetFrameToRightOf(aFrame
, mFirstChild
, -1);
333 return nsBidiPresUtils::GetFrameToLeftOf(aFrame
, mFirstChild
, -1);
336 // Just get the next or prev sibling, depending on block and frame
338 if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild
)) {
339 return aFrame
? aFrame
->GetNextSibling() : mFirstChild
;
341 return aFrame
? aFrame
->GetPrevSibling() : LastChild();
346 // Parent is a block frame, so use the LineIterator to find the next visual
347 // sibling on this line, or the first one on the next line.
351 thisLine
= iter
->FindLineContaining(aFrame
);
352 if (thisLine
< 0) return nullptr;
357 nsIFrame
* frame
= nullptr;
360 auto line
= iter
->GetLine(thisLine
).unwrap();
362 if (paraDir
== mozilla::intl::BidiDirection::LTR
) {
363 frame
= nsBidiPresUtils::GetFrameToRightOf(aFrame
, line
.mFirstFrameOnLine
,
364 line
.mNumFramesOnLine
);
366 frame
= nsBidiPresUtils::GetFrameToLeftOf(aFrame
, line
.mFirstFrameOnLine
,
367 line
.mNumFramesOnLine
);
371 int32_t numLines
= iter
->GetNumLines();
372 if (!frame
&& thisLine
< numLines
- 1) {
373 // Get the first frame of the next line
374 auto line
= iter
->GetLine(thisLine
+ 1).unwrap();
376 if (paraDir
== mozilla::intl::BidiDirection::LTR
) {
377 frame
= nsBidiPresUtils::GetFrameToRightOf(
378 nullptr, line
.mFirstFrameOnLine
, line
.mNumFramesOnLine
);
380 frame
= nsBidiPresUtils::GetFrameToLeftOf(nullptr, line
.mFirstFrameOnLine
,
381 line
.mNumFramesOnLine
);
387 #ifdef DEBUG_FRAME_LIST
388 void nsFrameList::VerifyList() const {
389 NS_ASSERTION((mFirstChild
== nullptr) == (mLastChild
== nullptr),
396 // Simple algorithm to find a loop in a linked list -- advance pointers
397 // through it at speeds of 1 and 2, and if they ever get to be equal bail
398 NS_ASSERTION(!mFirstChild
->GetPrevSibling(), "bad prev sibling pointer");
399 nsIFrame
*first
= mFirstChild
, *second
= mFirstChild
;
401 first
= first
->GetNextSibling();
402 second
= second
->GetNextSibling();
406 NS_ASSERTION(second
->GetPrevSibling()->GetNextSibling() == second
,
407 "bad prev sibling pointer");
408 second
= second
->GetNextSibling();
409 if (first
== second
) {
410 // Loop detected! Since second advances faster, they can't both be null;
411 // we would have broken out of the loop long ago.
412 NS_ERROR("loop in frame list. This will probably hang soon.");
418 NS_ASSERTION(second
->GetPrevSibling()->GetNextSibling() == second
,
419 "bad prev sibling pointer");
422 NS_ASSERTION(mLastChild
== nsLayoutUtils::GetLastSibling(mFirstChild
),
424 // XXX we should also assert that all GetParent() are either null or
425 // the same non-null value, but nsCSSFrameConstructor::nsFrameItems
426 // prevents that, e.g. table captions.
432 #ifdef DEBUG_FRAME_DUMP
433 const char* ChildListName(FrameChildListID aListID
) {
435 case FrameChildListID::Principal
:
437 case FrameChildListID::Popup
:
439 case FrameChildListID::Caption
:
440 return "CaptionList";
441 case FrameChildListID::ColGroup
:
442 return "ColGroupList";
443 case FrameChildListID::Absolute
:
444 return "AbsoluteList";
445 case FrameChildListID::Fixed
:
447 case FrameChildListID::Overflow
:
448 return "OverflowList";
449 case FrameChildListID::OverflowContainers
:
450 return "OverflowContainersList";
451 case FrameChildListID::ExcessOverflowContainers
:
452 return "ExcessOverflowContainersList";
453 case FrameChildListID::OverflowOutOfFlow
:
454 return "OverflowOutOfFlowList";
455 case FrameChildListID::Float
:
457 case FrameChildListID::Bullet
:
459 case FrameChildListID::PushedFloats
:
460 return "PushedFloatsList";
461 case FrameChildListID::Backdrop
:
462 return "BackdropList";
463 case FrameChildListID::NoReflowPrincipal
:
464 return "NoReflowPrincipalList";
467 MOZ_ASSERT_UNREACHABLE("unknown list");
468 return "UNKNOWN_FRAME_CHILD_LIST";
472 AutoFrameListPtr::~AutoFrameListPtr() {
474 mFrameList
->Delete(mPresContext
->PresShell());
478 } // namespace mozilla