layout/generic/CSSOrderAwareFrameIterator.h
author Daniel Holbert <dholbert@cs.stanford.edu>
Wed, 05 Apr 2017 19:31:47 -0700
changeset 351531 f6cc0dd3e7b8d90d0b1d29d5835a1bc4075211e4
parent 351530 947d5e737c2d05f038f01ddc2f02a01289db7ba8
child 351921 1a649a805099f4381e684920668f873569586c9a
permissions -rw-r--r--
Bug 812687 part 4: Add an optional parameter which can make CSSOrderAwareFrameIterator use the legacy "box-ordinal-group" property. r=mats This patch just adds an optional codepath that isn't taken yet, so it shouldn't affect our behavior. (The next patch in the series will make use of this new codepath.) Note: the large code-comment that this patch adds is taken mostly-verbatim from some nsFlexContainerFrame.cpp code. (The original copy will be removed by the next patch in this series, when we switch to take advantage of this new mechanism.) MozReview-Commit-ID: 9pkJ346rrXg

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/* Iterator class for frame lists that respect CSS "order" during layout */

#ifndef mozilla_CSSOrderAwareFrameIterator_h
#define mozilla_CSSOrderAwareFrameIterator_h

#include <algorithm>
#include "nsFrameList.h"
#include "nsIFrame.h"
#include "mozilla/Maybe.h"
#include "mozilla/Assertions.h"

#if defined(__clang__) && __clang_major__ == 3 && __clang_minor__ <= 8
#define CLANG_CRASH_BUG 1
#endif

namespace mozilla {

template<typename Iterator>
class CSSOrderAwareFrameIteratorT
{
public:
  enum OrderState { eUnknownOrder, eKnownOrdered, eKnownUnordered };
  enum ChildFilter { eSkipPlaceholders, eIncludeAll };
  enum OrderingProperty {
    eUseOrder,          // Default behavior: use "order".
    eUseBoxOrdinalGroup // Legacy behavior: use prefixed "box-ordinal-group".
  };
  CSSOrderAwareFrameIteratorT(nsIFrame* aContainer,
                              nsIFrame::ChildListID aListID,
                              ChildFilter aFilter = eSkipPlaceholders,
                              OrderState aState = eUnknownOrder,
                              OrderingProperty aOrderProp = eUseOrder)
    : mChildren(aContainer->GetChildList(aListID))
    , mArrayIndex(0)
    , mItemIndex(0)
    , mSkipPlaceholders(aFilter == eSkipPlaceholders)
#ifdef DEBUG
    , mContainer(aContainer)
    , mListID(aListID)
#endif
  {
    size_t count = 0;
    bool isOrdered = aState != eKnownUnordered;
    if (aState == eUnknownOrder) {
      auto maxOrder = std::numeric_limits<int32_t>::min();
      for (auto child : mChildren) {
        ++count;

        int32_t order;
        if (aOrderProp == eUseBoxOrdinalGroup) {
          // We'll be using mBoxOrdinal, which has type uint32_t. However, the
          // modern 'order' property (whose functionality we're co-opting) has
          // type int32_t.  So: if we happen to have a uint32_t value that's
          // greater than INT32_MAX, we clamp it rather than letting it
          // overflow. Chances are, this is just an author using BIG_VALUE
          // anyway, so the clamped value should be fine.
          uint32_t clampedBoxOrdinal =
            std::min(child->StyleXUL()->mBoxOrdinal,
                     static_cast<uint32_t>(INT32_MAX));
          order = static_cast<int32_t>(clampedBoxOrdinal);
        } else {
          order = child->StylePosition()->mOrder;
        }

        if (order < maxOrder) {
          isOrdered = false;
          break;
        }
        maxOrder = order;
      }
    }
    if (isOrdered) {
      mIter.emplace(begin(mChildren));
      mIterEnd.emplace(end(mChildren));
    } else {
      count *= 2; // XXX somewhat arbitrary estimate for now...
      mArray.emplace(count);
      for (Iterator i(begin(mChildren)), iEnd(end(mChildren)); i != iEnd; ++i) {
        mArray->AppendElement(*i);
      }
      auto comparator = (aOrderProp == eUseBoxOrdinalGroup)
        ? CSSBoxOrdinalGroupComparator
        : CSSOrderComparator;

      // XXX replace this with nsTArray::StableSort when bug 1147091 is fixed.
      std::stable_sort(mArray->begin(), mArray->end(), comparator);
    }

    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }
  ~CSSOrderAwareFrameIteratorT()
  {
    MOZ_ASSERT(IsForward() == mItemCount.isNothing());
  }

  bool IsForward() const;
  Iterator begin(const nsFrameList& aList);
  Iterator end(const nsFrameList& aList);

  nsIFrame* operator*() const
  {
    MOZ_ASSERT(!AtEnd());
    if (mIter.isSome()) {
      return **mIter;
    }
    return (*mArray)[mArrayIndex];
  }

  /**
   * Return the child index of the current item, placeholders not counted.
   * It's forbidden to call this method when the current frame is placeholder.
   */
  size_t ItemIndex() const
  {
    MOZ_ASSERT(!AtEnd());
    MOZ_ASSERT((**this)->GetType() != nsGkAtoms::placeholderFrame,
               "MUST not call this when at a placeholder");
    MOZ_ASSERT(IsForward() || mItemIndex < *mItemCount,
               "Returning an out-of-range mItemIndex...");
    return mItemIndex;
  }

  void SetItemCount(size_t aItemCount)
  {
#ifndef CLANG_CRASH_BUG
    MOZ_ASSERT(mIter.isSome() || aItemCount <= mArray->Length(),
               "item count mismatch");
#endif
    mItemCount.emplace(aItemCount);
    // Note: it's OK if mItemIndex underflows -- ItemIndex()
    // will not be called unless there is at least one item.
    mItemIndex = IsForward() ? 0 : *mItemCount - 1;
  }

  /**
   * Skip over placeholder children.
   */
  void SkipPlaceholders()
  {
    if (mIter.isSome()) {
      for (; *mIter != *mIterEnd; ++*mIter) {
        nsIFrame* child = **mIter;
        if (child->GetType() != nsGkAtoms::placeholderFrame) {
          return;
        }
      }
    } else {
      for (; mArrayIndex < mArray->Length(); ++mArrayIndex) {
        nsIFrame* child = (*mArray)[mArrayIndex];
        if (child->GetType() != nsGkAtoms::placeholderFrame) {
          return;
        }
      }
    }
  }

  bool AtEnd() const
  {
#ifndef CLANG_CRASH_BUG
    // Clang 3.6.2 crashes when compiling this assertion:
    MOZ_ASSERT(mIter.isSome() || mArrayIndex <= mArray->Length());
#endif
    return mIter ? (*mIter == *mIterEnd) : mArrayIndex >= mArray->Length();
  }

  void Next()
  {
#ifdef DEBUG
    MOZ_ASSERT(!AtEnd());
    nsFrameList list = mContainer->GetChildList(mListID);
    MOZ_ASSERT(list.FirstChild() == mChildren.FirstChild() &&
               list.LastChild() == mChildren.LastChild(),
               "the list of child frames must not change while iterating!");
#endif
    if (mSkipPlaceholders ||
        (**this)->GetType() != nsGkAtoms::placeholderFrame) {
      IsForward() ? ++mItemIndex : --mItemIndex;
    }
    if (mIter.isSome()) {
      ++*mIter;
    } else {
      ++mArrayIndex;
    }
    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  void Reset(ChildFilter aFilter = eSkipPlaceholders)
  {
    if (mIter.isSome()) {
      mIter.reset();
      mIter.emplace(begin(mChildren));
      mIterEnd.reset();
      mIterEnd.emplace(end(mChildren));
    } else {
      mArrayIndex = 0;
    }
    mItemIndex = IsForward() ? 0 : *mItemCount - 1;
    mSkipPlaceholders = aFilter == eSkipPlaceholders;
    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  bool IsValid() const { return mIter.isSome() || mArray.isSome(); }

  void Invalidate()
  {
    mIter.reset();
    mArray.reset();
    mozWritePoison(&mChildren, sizeof(mChildren));
  }

  bool ItemsAreAlreadyInOrder() const { return mIter.isSome(); }

  static bool CSSOrderComparator(nsIFrame* const& a, nsIFrame* const& b);
  static bool CSSBoxOrdinalGroupComparator(nsIFrame* const& a, nsIFrame* const& b);
private:
  nsFrameList mChildren;
  // Used if child list is already in ascending 'order'.
  Maybe<Iterator> mIter;
  Maybe<Iterator> mIterEnd;
  // Used if child list is *not* in ascending 'order'.
  // This array is pre-sorted in reverse order for a reverse iterator.
  Maybe<nsTArray<nsIFrame*>> mArray;
  size_t mArrayIndex;
  // The index of the current item (placeholders excluded).
  size_t mItemIndex;
  // The number of items (placeholders excluded).
  // It's only initialized and used in a reverse iterator.
  Maybe<size_t> mItemCount;
  // Skip placeholder children in the iteration?
  bool mSkipPlaceholders;
#ifdef DEBUG
  nsIFrame* mContainer;
  nsIFrame::ChildListID mListID;
#endif
};

typedef CSSOrderAwareFrameIteratorT<nsFrameList::iterator>
  CSSOrderAwareFrameIterator;
typedef CSSOrderAwareFrameIteratorT<nsFrameList::reverse_iterator>
  ReverseCSSOrderAwareFrameIterator;

} // namespace mozilla

#endif // mozilla_CSSOrderAwareFrameIterator_h