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