tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

nsFrameList.cpp (14749B)

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