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
347 if (aFrame) {
348 auto line = iter->GetLine(thisLine).unwrap();
349
350 if (paraDir == NSBIDI_LTR) {
351 frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, line.mFirstFrameOnLine,
352 line.mNumFramesOnLine);
353 } else { // RTL
354 frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, line.mFirstFrameOnLine,
355 line.mNumFramesOnLine);
356 }
357 }
358
359 if (!frame && thisLine > 0) {
360 // Get the last frame of the previous line
361 auto line = iter->GetLine(thisLine - 1).unwrap();
362
363 if (paraDir == NSBIDI_LTR) {
364 frame = nsBidiPresUtils::GetFrameToLeftOf(nullptr, line.mFirstFrameOnLine,
365 line.mNumFramesOnLine);
366 } else { // RTL
367 frame = nsBidiPresUtils::GetFrameToRightOf(
368 nullptr, line.mFirstFrameOnLine, line.mNumFramesOnLine);
369 }
370 }
371 return frame;
372 }
373
GetNextVisualFor(nsIFrame * aFrame) const374 nsIFrame* nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const {
375 if (!mFirstChild) return nullptr;
376
377 nsIFrame* parent = mFirstChild->GetParent();
378 if (!parent) return aFrame ? aFrame->GetPrevSibling() : mFirstChild;
379
380 nsBidiDirection paraDir = nsBidiPresUtils::ParagraphDirection(mFirstChild);
381
382 nsAutoLineIterator iter = parent->GetLineIterator();
383 if (!iter) {
384 // Parent is not a block Frame
385 if (parent->IsLineFrame()) {
386 // Line frames are not bidi-splittable, so need to consider bidi
387 // reordering
388 if (paraDir == NSBIDI_LTR) {
389 return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
390 } else { // RTL
391 return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
392 }
393 } else {
394 // Just get the next or prev sibling, depending on block and frame
395 // direction.
396 if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild)) {
397 return aFrame ? aFrame->GetNextSibling() : mFirstChild;
398 } else {
399 return aFrame ? aFrame->GetPrevSibling() : LastChild();
400 }
401 }
402 }
403
404 // Parent is a block frame, so use the LineIterator to find the next visual
405 // sibling on this line, or the first one on the next line.
406
407 int32_t thisLine;
408 if (aFrame) {
409 thisLine = iter->FindLineContaining(aFrame);
410 if (thisLine < 0) return nullptr;
411 } else {
412 thisLine = -1;
413 }
414
415 nsIFrame* frame = nullptr;
416
417 if (aFrame) {
418 auto line = iter->GetLine(thisLine).unwrap();
419
420 if (paraDir == NSBIDI_LTR) {
421 frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, line.mFirstFrameOnLine,
422 line.mNumFramesOnLine);
423 } else { // RTL
424 frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, line.mFirstFrameOnLine,
425 line.mNumFramesOnLine);
426 }
427 }
428
429 int32_t numLines = iter->GetNumLines();
430 if (!frame && thisLine < numLines - 1) {
431 // Get the first frame of the next line
432 auto line = iter->GetLine(thisLine + 1).unwrap();
433
434 if (paraDir == NSBIDI_LTR) {
435 frame = nsBidiPresUtils::GetFrameToRightOf(
436 nullptr, line.mFirstFrameOnLine, line.mNumFramesOnLine);
437 } else { // RTL
438 frame = nsBidiPresUtils::GetFrameToLeftOf(nullptr, line.mFirstFrameOnLine,
439 line.mNumFramesOnLine);
440 }
441 }
442 return frame;
443 }
444
445 #ifdef DEBUG_FRAME_LIST
VerifyList() const446 void nsFrameList::VerifyList() const {
447 NS_ASSERTION((mFirstChild == nullptr) == (mLastChild == nullptr),
448 "bad list state");
449
450 if (IsEmpty()) {
451 return;
452 }
453
454 // Simple algorithm to find a loop in a linked list -- advance pointers
455 // through it at speeds of 1 and 2, and if they ever get to be equal bail
456 NS_ASSERTION(!mFirstChild->GetPrevSibling(), "bad prev sibling pointer");
457 nsIFrame *first = mFirstChild, *second = mFirstChild;
458 for (;;) {
459 first = first->GetNextSibling();
460 second = second->GetNextSibling();
461 if (!second) {
462 break;
463 }
464 NS_ASSERTION(second->GetPrevSibling()->GetNextSibling() == second,
465 "bad prev sibling pointer");
466 second = second->GetNextSibling();
467 if (first == second) {
468 // Loop detected! Since second advances faster, they can't both be null;
469 // we would have broken out of the loop long ago.
470 NS_ERROR("loop in frame list. This will probably hang soon.");
471 return;
472 }
473 if (!second) {
474 break;
475 }
476 NS_ASSERTION(second->GetPrevSibling()->GetNextSibling() == second,
477 "bad prev sibling pointer");
478 }
479
480 NS_ASSERTION(mLastChild == nsLayoutUtils::GetLastSibling(mFirstChild),
481 "bogus mLastChild");
482 // XXX we should also assert that all GetParent() are either null or
483 // the same non-null value, but nsCSSFrameConstructor::nsFrameItems
484 // prevents that, e.g. table captions.
485 }
486 #endif
487
488 namespace mozilla {
489
~AutoFrameListPtr()490 AutoFrameListPtr::~AutoFrameListPtr() {
491 if (mFrameList) {
492 mFrameList->Delete(mPresContext->PresShell());
493 }
494 }
495
496 } // namespace mozilla
497