Add m-esr52 at 52.6.0

1 files changed, 907 insertions, 0 deletions

diff --git a/dom/base/nsAttrAndChildArray.cpp b/dom/base/nsAttrAndChildArray.cpp
new file mode 100644
index 000000000..b285ee003
--- /dev/null
+++ b/dom/base/nsAttrAndChildArray.cpp
@@ -0,0 +1,907 @@
+/* -*- 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/. */
+
+/*
+ * Storage of the children and attributes of a DOM node; storage for
+ * the two is unified to minimize footprint.
+ */
+
+#include "nsAttrAndChildArray.h"
+
+#include "mozilla/CheckedInt.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/MemoryReporting.h"
+
+#include "nsMappedAttributeElement.h"
+#include "nsString.h"
+#include "nsHTMLStyleSheet.h"
+#include "nsRuleWalker.h"
+#include "nsMappedAttributes.h"
+#include "nsUnicharUtils.h"
+#include "nsContentUtils.h" // nsAutoScriptBlocker
+
+using mozilla::CheckedUint32;
+
+/*
+CACHE_POINTER_SHIFT indicates how many steps to downshift the |this| pointer.
+It should be small enough to not cause collisions between adjecent arrays, and
+large enough to make sure that all indexes are used. The size below is based
+on the size of the smallest possible element (currently 24[*] bytes) which is
+the smallest distance between two nsAttrAndChildArray. 24/(2^_5_) is 0.75.
+This means that two adjacent nsAttrAndChildArrays will overlap one in 4 times.
+However not all elements will have enough children to get cached. And any
+allocator that doesn't return addresses aligned to 64 bytes will ensure that
+any index will get used.
+
+[*] sizeof(Element) + 4 bytes for nsIDOMElement vtable pointer.
+*/
+
+#define CACHE_POINTER_SHIFT 5
+#define CACHE_NUM_SLOTS 128
+#define CACHE_CHILD_LIMIT 10
+
+#define CACHE_GET_INDEX(_array) \
+  ((NS_PTR_TO_INT32(_array) >> CACHE_POINTER_SHIFT) & \
+   (CACHE_NUM_SLOTS - 1))
+
+struct IndexCacheSlot
+{
+  const nsAttrAndChildArray* array;
+  int32_t index;
+};
+
+// This is inited to all zeroes since it's static. Though even if it wasn't
+// the worst thing that'd happen is a small inefficency if you'd get a false
+// positive cachehit.
+static IndexCacheSlot indexCache[CACHE_NUM_SLOTS];
+
+static
+inline
+void
+AddIndexToCache(const nsAttrAndChildArray* aArray, int32_t aIndex)
+{
+  uint32_t ix = CACHE_GET_INDEX(aArray);
+  indexCache[ix].array = aArray;
+  indexCache[ix].index = aIndex;
+}
+
+static
+inline
+int32_t
+GetIndexFromCache(const nsAttrAndChildArray* aArray)
+{
+  uint32_t ix = CACHE_GET_INDEX(aArray);
+  return indexCache[ix].array == aArray ? indexCache[ix].index : -1;
+}
+
+
+/**
+ * Due to a compiler bug in VisualAge C++ for AIX, we need to return the
+ * address of the first index into mBuffer here, instead of simply returning
+ * mBuffer itself.
+ *
+ * See Bug 231104 for more information.
+ */
+#define ATTRS(_impl) \
+  reinterpret_cast<InternalAttr*>(&((_impl)->mBuffer[0]))
+
+
+#define NS_IMPL_EXTRA_SIZE \
+  ((sizeof(Impl) - sizeof(mImpl->mBuffer)) / sizeof(void*))
+
+nsAttrAndChildArray::nsAttrAndChildArray()
+  : mImpl(nullptr)
+{
+}
+
+nsAttrAndChildArray::~nsAttrAndChildArray()
+{
+  if (!mImpl) {
+    return;
+  }
+
+  Clear();
+
+  free(mImpl);
+}
+
+nsIContent*
+nsAttrAndChildArray::GetSafeChildAt(uint32_t aPos) const
+{
+  if (aPos < ChildCount()) {
+    return ChildAt(aPos);
+  }
+
+  return nullptr;
+}
+
+nsIContent * const *
+nsAttrAndChildArray::GetChildArray(uint32_t* aChildCount) const
+{
+  *aChildCount = ChildCount();
+
+  if (!*aChildCount) {
+    return nullptr;
+  }
+
+  return reinterpret_cast<nsIContent**>(mImpl->mBuffer + AttrSlotsSize());
+}
+
+nsresult
+nsAttrAndChildArray::InsertChildAt(nsIContent* aChild, uint32_t aPos)
+{
+  NS_ASSERTION(aChild, "nullchild");
+  NS_ASSERTION(aPos <= ChildCount(), "out-of-bounds");
+
+  uint32_t offset = AttrSlotsSize();
+  uint32_t childCount = ChildCount();
+
+  NS_ENSURE_TRUE(childCount < ATTRCHILD_ARRAY_MAX_CHILD_COUNT,
+                 NS_ERROR_FAILURE);
+
+  // First try to fit new child in existing childlist
+  if (mImpl && offset + childCount < mImpl->mBufferSize) {
+    void** pos = mImpl->mBuffer + offset + aPos;
+    if (childCount != aPos) {
+      memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
+    }
+    SetChildAtPos(pos, aChild, aPos, childCount);
+
+    SetChildCount(childCount + 1);
+
+    return NS_OK;
+  }
+
+  // Try to fit new child in existing buffer by compressing attrslots
+  if (offset && !mImpl->mBuffer[offset - ATTRSIZE]) {
+    // Compress away all empty slots while we're at it. This might not be the
+    // optimal thing to do.
+    uint32_t attrCount = NonMappedAttrCount();
+    void** newStart = mImpl->mBuffer + attrCount * ATTRSIZE;
+    void** oldStart = mImpl->mBuffer + offset;
+    memmove(newStart, oldStart, aPos * sizeof(nsIContent*));
+    memmove(&newStart[aPos + 1], &oldStart[aPos],
+            (childCount - aPos) * sizeof(nsIContent*));
+    SetChildAtPos(newStart + aPos, aChild, aPos, childCount);
+
+    SetAttrSlotAndChildCount(attrCount, childCount + 1);
+
+    return NS_OK;
+  }
+
+  // We can't fit in current buffer, Realloc time!
+  if (!GrowBy(1)) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  void** pos = mImpl->mBuffer + offset + aPos;
+  if (childCount != aPos) {
+    memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
+  }
+  SetChildAtPos(pos, aChild, aPos, childCount);
+
+  SetChildCount(childCount + 1);
+
+  return NS_OK;
+}
+
+void
+nsAttrAndChildArray::RemoveChildAt(uint32_t aPos)
+{
+  // Just store the return value of TakeChildAt in an nsCOMPtr to
+  // trigger a release.
+  nsCOMPtr<nsIContent> child = TakeChildAt(aPos);
+}
+
+already_AddRefed<nsIContent>
+nsAttrAndChildArray::TakeChildAt(uint32_t aPos)
+{
+  NS_ASSERTION(aPos < ChildCount(), "out-of-bounds");
+
+  uint32_t childCount = ChildCount();
+  void** pos = mImpl->mBuffer + AttrSlotsSize() + aPos;
+  nsIContent* child = static_cast<nsIContent*>(*pos);
+  if (child->mPreviousSibling) {
+    child->mPreviousSibling->mNextSibling = child->mNextSibling;
+  }
+  if (child->mNextSibling) {
+    child->mNextSibling->mPreviousSibling = child->mPreviousSibling;
+  }
+  child->mPreviousSibling = child->mNextSibling = nullptr;
+
+  memmove(pos, pos + 1, (childCount - aPos - 1) * sizeof(nsIContent*));
+  SetChildCount(childCount - 1);
+
+  return dont_AddRef(child);
+}
+
+int32_t
+nsAttrAndChildArray::IndexOfChild(const nsINode* aPossibleChild) const
+{
+  if (!mImpl) {
+    return -1;
+  }
+  void** children = mImpl->mBuffer + AttrSlotsSize();
+  // Use signed here since we compare count to cursor which has to be signed
+  int32_t i, count = ChildCount();
+
+  if (count >= CACHE_CHILD_LIMIT) {
+    int32_t cursor = GetIndexFromCache(this);
+    // Need to compare to count here since we may have removed children since
+    // the index was added to the cache.
+    // We're also relying on that GetIndexFromCache returns -1 if no cached
+    // index was found.
+    if (cursor >= count) {
+      cursor = -1;
+    }
+
+    // Seek outward from the last found index. |inc| will change sign every
+    // run through the loop. |sign| just exists to make sure the absolute
+    // value of |inc| increases each time through.
+    int32_t inc = 1, sign = 1;
+    while (cursor >= 0 && cursor < count) {
+      if (children[cursor] == aPossibleChild) {
+        AddIndexToCache(this, cursor);
+
+        return cursor;
+      }
+
+      cursor += inc;
+      inc = -inc - sign;
+      sign = -sign;
+    }
+
+    // We ran into one 'edge'. Add inc to cursor once more to get back to
+    // the 'side' where we still need to search, then step in the |sign|
+    // direction.
+    cursor += inc;
+
+    if (sign > 0) {
+      for (; cursor < count; ++cursor) {
+        if (children[cursor] == aPossibleChild) {
+          AddIndexToCache(this, cursor);
+
+          return static_cast<int32_t>(cursor);
+        }
+      }
+    }
+    else {
+      for (; cursor >= 0; --cursor) {
+        if (children[cursor] == aPossibleChild) {
+          AddIndexToCache(this, cursor);
+
+          return static_cast<int32_t>(cursor);
+        }
+      }
+    }
+
+    // The child wasn't even in the remaining children
+    return -1;
+  }
+
+  for (i = 0; i < count; ++i) {
+    if (children[i] == aPossibleChild) {
+      return static_cast<int32_t>(i);
+    }
+  }
+
+  return -1;
+}
+
+uint32_t
+nsAttrAndChildArray::AttrCount() const
+{
+  return NonMappedAttrCount() + MappedAttrCount();
+}
+
+const nsAttrValue*
+nsAttrAndChildArray::GetAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const
+{
+  uint32_t i, slotCount = AttrSlotCount();
+  if (aNamespaceID == kNameSpaceID_None) {
+    // This should be the common case so lets make an optimized loop
+    for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+      if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
+        return &ATTRS(mImpl)[i].mValue;
+      }
+    }
+
+    if (mImpl && mImpl->mMappedAttrs) {
+      return mImpl->mMappedAttrs->GetAttr(aLocalName);
+    }
+  }
+  else {
+    for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+      if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
+        return &ATTRS(mImpl)[i].mValue;
+      }
+    }
+  }
+
+  return nullptr;
+}
+
+const nsAttrValue*
+nsAttrAndChildArray::GetAttr(const nsAString& aLocalName) const
+{
+  uint32_t i, slotCount = AttrSlotCount();
+  for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+    if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
+      return &ATTRS(mImpl)[i].mValue;
+    }
+  }
+
+  if (mImpl && mImpl->mMappedAttrs) {
+    return mImpl->mMappedAttrs->GetAttr(aLocalName);
+  }
+
+  return nullptr;
+}
+
+const nsAttrValue*
+nsAttrAndChildArray::GetAttr(const nsAString& aName,
+                             nsCaseTreatment aCaseSensitive) const
+{
+  // Check whether someone is being silly and passing non-lowercase
+  // attr names.
+  if (aCaseSensitive == eIgnoreCase &&
+      nsContentUtils::StringContainsASCIIUpper(aName)) {
+    // Try again with a lowercased name, but make sure we can't reenter this
+    // block by passing eCaseSensitive for aCaseSensitive.
+    nsAutoString lowercase;
+    nsContentUtils::ASCIIToLower(aName, lowercase);
+    return GetAttr(lowercase, eCaseMatters);
+  }
+
+  uint32_t i, slotCount = AttrSlotCount();
+  for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+    if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
+      return &ATTRS(mImpl)[i].mValue;
+    }
+  }
+
+  if (mImpl && mImpl->mMappedAttrs) {
+    const nsAttrValue* val =
+      mImpl->mMappedAttrs->GetAttr(aName);
+    if (val) {
+      return val;
+    }
+  }
+
+  return nullptr;
+}
+
+const nsAttrValue*
+nsAttrAndChildArray::AttrAt(uint32_t aPos) const
+{
+  NS_ASSERTION(aPos < AttrCount(),
+               "out-of-bounds access in nsAttrAndChildArray");
+
+  uint32_t nonmapped = NonMappedAttrCount();
+  if (aPos < nonmapped) {
+    return &ATTRS(mImpl)[aPos].mValue;
+  }
+
+  return mImpl->mMappedAttrs->AttrAt(aPos - nonmapped);
+}
+
+nsresult
+nsAttrAndChildArray::SetAndSwapAttr(nsIAtom* aLocalName, nsAttrValue& aValue)
+{
+  uint32_t i, slotCount = AttrSlotCount();
+  for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+    if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
+      ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
+      return NS_OK;
+    }
+  }
+
+  NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
+                 NS_ERROR_FAILURE);
+
+  if (i == slotCount && !AddAttrSlot()) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  new (&ATTRS(mImpl)[i].mName) nsAttrName(aLocalName);
+  new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
+  ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
+
+  return NS_OK;
+}
+
+nsresult
+nsAttrAndChildArray::SetAndSwapAttr(mozilla::dom::NodeInfo* aName, nsAttrValue& aValue)
+{
+  int32_t namespaceID = aName->NamespaceID();
+  nsIAtom* localName = aName->NameAtom();
+  if (namespaceID == kNameSpaceID_None) {
+    return SetAndSwapAttr(localName, aValue);
+  }
+
+  uint32_t i, slotCount = AttrSlotCount();
+  for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+    if (ATTRS(mImpl)[i].mName.Equals(localName, namespaceID)) {
+      ATTRS(mImpl)[i].mName.SetTo(aName);
+      ATTRS(mImpl)[i].mValue.Reset();
+      ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
+
+      return NS_OK;
+    }
+  }
+
+  NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
+                 NS_ERROR_FAILURE);
+
+  if (i == slotCount && !AddAttrSlot()) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  new (&ATTRS(mImpl)[i].mName) nsAttrName(aName);
+  new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
+  ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
+
+  return NS_OK;
+}
+
+
+nsresult
+nsAttrAndChildArray::RemoveAttrAt(uint32_t aPos, nsAttrValue& aValue)
+{
+  NS_ASSERTION(aPos < AttrCount(), "out-of-bounds");
+
+  uint32_t nonmapped = NonMappedAttrCount();
+  if (aPos < nonmapped) {
+    ATTRS(mImpl)[aPos].mValue.SwapValueWith(aValue);
+    ATTRS(mImpl)[aPos].~InternalAttr();
+
+    uint32_t slotCount = AttrSlotCount();
+    memmove(&ATTRS(mImpl)[aPos],
+            &ATTRS(mImpl)[aPos + 1],
+            (slotCount - aPos - 1) * sizeof(InternalAttr));
+    memset(&ATTRS(mImpl)[slotCount - 1], 0, sizeof(InternalAttr));
+
+    return NS_OK;
+  }
+
+  if (MappedAttrCount() == 1) {
+    // We're removing the last mapped attribute.  Can't swap in this
+    // case; have to copy.
+    aValue.SetTo(*mImpl->mMappedAttrs->AttrAt(0));
+    NS_RELEASE(mImpl->mMappedAttrs);
+
+    return NS_OK;
+  }
+
+  RefPtr<nsMappedAttributes> mapped =
+    GetModifiableMapped(nullptr, nullptr, false);
+
+  mapped->RemoveAttrAt(aPos - nonmapped, aValue);
+
+  return MakeMappedUnique(mapped);
+}
+
+mozilla::dom::BorrowedAttrInfo
+nsAttrAndChildArray::AttrInfoAt(uint32_t aPos) const
+{
+  NS_ASSERTION(aPos < AttrCount(),
+               "out-of-bounds access in nsAttrAndChildArray");
+
+  uint32_t nonmapped = NonMappedAttrCount();
+  if (aPos < nonmapped) {
+    return BorrowedAttrInfo(&ATTRS(mImpl)[aPos].mName, &ATTRS(mImpl)[aPos].mValue);
+  }
+
+  return BorrowedAttrInfo(mImpl->mMappedAttrs->NameAt(aPos - nonmapped),
+                    mImpl->mMappedAttrs->AttrAt(aPos - nonmapped));
+}
+
+const nsAttrName*
+nsAttrAndChildArray::AttrNameAt(uint32_t aPos) const
+{
+  NS_ASSERTION(aPos < AttrCount(),
+               "out-of-bounds access in nsAttrAndChildArray");
+
+  uint32_t nonmapped = NonMappedAttrCount();
+  if (aPos < nonmapped) {
+    return &ATTRS(mImpl)[aPos].mName;
+  }
+
+  return mImpl->mMappedAttrs->NameAt(aPos - nonmapped);
+}
+
+const nsAttrName*
+nsAttrAndChildArray::GetSafeAttrNameAt(uint32_t aPos) const
+{
+  uint32_t nonmapped = NonMappedAttrCount();
+  if (aPos < nonmapped) {
+    void** pos = mImpl->mBuffer + aPos * ATTRSIZE;
+    if (!*pos) {
+      return nullptr;
+    }
+
+    return &reinterpret_cast<InternalAttr*>(pos)->mName;
+  }
+
+  if (aPos >= AttrCount()) {
+    return nullptr;
+  }
+
+  return mImpl->mMappedAttrs->NameAt(aPos - nonmapped);
+}
+
+const nsAttrName*
+nsAttrAndChildArray::GetExistingAttrNameFromQName(const nsAString& aName) const
+{
+  uint32_t i, slotCount = AttrSlotCount();
+  for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+    if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
+      return &ATTRS(mImpl)[i].mName;
+    }
+  }
+
+  if (mImpl && mImpl->mMappedAttrs) {
+    return mImpl->mMappedAttrs->GetExistingAttrNameFromQName(aName);
+  }
+
+  return nullptr;
+}
+
+int32_t
+nsAttrAndChildArray::IndexOfAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const
+{
+  int32_t idx;
+  if (mImpl && mImpl->mMappedAttrs && aNamespaceID == kNameSpaceID_None) {
+    idx = mImpl->mMappedAttrs->IndexOfAttr(aLocalName);
+    if (idx >= 0) {
+      return NonMappedAttrCount() + idx;
+    }
+  }
+
+  uint32_t i;
+  uint32_t slotCount = AttrSlotCount();
+  if (aNamespaceID == kNameSpaceID_None) {
+    // This should be the common case so lets make an optimized loop
+    for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+      if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
+        return i;
+      }
+    }
+  }
+  else {
+    for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+      if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
+        return i;
+      }
+    }
+  }
+
+  return -1;
+}
+
+nsresult
+nsAttrAndChildArray::SetAndTakeMappedAttr(nsIAtom* aLocalName,
+                                          nsAttrValue& aValue,
+                                          nsMappedAttributeElement* aContent,
+                                          nsHTMLStyleSheet* aSheet)
+{
+  bool willAdd = true;
+  if (mImpl && mImpl->mMappedAttrs) {
+    willAdd = !mImpl->mMappedAttrs->GetAttr(aLocalName);
+  }
+
+  RefPtr<nsMappedAttributes> mapped =
+    GetModifiableMapped(aContent, aSheet, willAdd);
+
+  mapped->SetAndTakeAttr(aLocalName, aValue);
+
+  return MakeMappedUnique(mapped);
+}
+
+nsresult
+nsAttrAndChildArray::DoSetMappedAttrStyleSheet(nsHTMLStyleSheet* aSheet)
+{
+  NS_PRECONDITION(mImpl && mImpl->mMappedAttrs,
+                  "Should have mapped attrs here!");
+  if (aSheet == mImpl->mMappedAttrs->GetStyleSheet()) {
+    return NS_OK;
+  }
+
+  RefPtr<nsMappedAttributes> mapped =
+    GetModifiableMapped(nullptr, nullptr, false);
+
+  mapped->SetStyleSheet(aSheet);
+
+  return MakeMappedUnique(mapped);
+}
+
+void
+nsAttrAndChildArray::WalkMappedAttributeStyleRules(nsRuleWalker* aRuleWalker)
+{
+  if (mImpl && mImpl->mMappedAttrs) {
+    aRuleWalker->Forward(mImpl->mMappedAttrs);
+  }
+}
+
+void
+nsAttrAndChildArray::Compact()
+{
+  if (!mImpl) {
+    return;
+  }
+
+  // First compress away empty attrslots
+  uint32_t slotCount = AttrSlotCount();
+  uint32_t attrCount = NonMappedAttrCount();
+  uint32_t childCount = ChildCount();
+
+  if (attrCount < slotCount) {
+    memmove(mImpl->mBuffer + attrCount * ATTRSIZE,
+            mImpl->mBuffer + slotCount * ATTRSIZE,
+            childCount * sizeof(nsIContent*));
+    SetAttrSlotCount(attrCount);
+  }
+
+  // Then resize or free buffer
+  uint32_t newSize = attrCount * ATTRSIZE + childCount;
+  if (!newSize && !mImpl->mMappedAttrs) {
+    free(mImpl);
+    mImpl = nullptr;
+  }
+  else if (newSize < mImpl->mBufferSize) {
+    mImpl = static_cast<Impl*>(realloc(mImpl, (newSize + NS_IMPL_EXTRA_SIZE) * sizeof(nsIContent*)));
+    NS_ASSERTION(mImpl, "failed to reallocate to smaller buffer");
+
+    mImpl->mBufferSize = newSize;
+  }
+}
+
+void
+nsAttrAndChildArray::Clear()
+{
+  if (!mImpl) {
+    return;
+  }
+
+  if (mImpl->mMappedAttrs) {
+    NS_RELEASE(mImpl->mMappedAttrs);
+  }
+
+  uint32_t i, slotCount = AttrSlotCount();
+  for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+    ATTRS(mImpl)[i].~InternalAttr();
+  }
+
+  nsAutoScriptBlocker scriptBlocker;
+  uint32_t end = slotCount * ATTRSIZE + ChildCount();
+  for (i = slotCount * ATTRSIZE; i < end; ++i) {
+    nsIContent* child = static_cast<nsIContent*>(mImpl->mBuffer[i]);
+    // making this false so tree teardown doesn't end up being
+    // O(N*D) (number of nodes times average depth of tree).
+    child->UnbindFromTree(false); // XXX is it better to let the owner do this?
+    // Make sure to unlink our kids from each other, since someone
+    // else could stil be holding references to some of them.
+
+    // XXXbz We probably can't push this assignment down into the |aNullParent|
+    // case of UnbindFromTree because we still need the assignment in
+    // RemoveChildAt.  In particular, ContentRemoved fires between
+    // RemoveChildAt and UnbindFromTree, and in ContentRemoved the sibling
+    // chain needs to be correct.  Though maybe we could set the prev and next
+    // to point to each other but keep the kid being removed pointing to them
+    // through ContentRemoved so consumers can find where it used to be in the
+    // list?
+    child->mPreviousSibling = child->mNextSibling = nullptr;
+    NS_RELEASE(child);
+  }
+
+  SetAttrSlotAndChildCount(0, 0);
+}
+
+uint32_t
+nsAttrAndChildArray::NonMappedAttrCount() const
+{
+  if (!mImpl) {
+    return 0;
+  }
+
+  uint32_t count = AttrSlotCount();
+  while (count > 0 && !mImpl->mBuffer[(count - 1) * ATTRSIZE]) {
+    --count;
+  }
+
+  return count;
+}
+
+uint32_t
+nsAttrAndChildArray::MappedAttrCount() const
+{
+  return mImpl && mImpl->mMappedAttrs ? (uint32_t)mImpl->mMappedAttrs->Count() : 0;
+}
+
+nsMappedAttributes*
+nsAttrAndChildArray::GetModifiableMapped(nsMappedAttributeElement* aContent,
+                                         nsHTMLStyleSheet* aSheet,
+                                         bool aWillAddAttr)
+{
+  if (mImpl && mImpl->mMappedAttrs) {
+    return mImpl->mMappedAttrs->Clone(aWillAddAttr);
+  }
+
+  MOZ_ASSERT(aContent, "Trying to create modifiable without content");
+
+  nsMapRuleToAttributesFunc mapRuleFunc =
+    aContent->GetAttributeMappingFunction();
+  return new nsMappedAttributes(aSheet, mapRuleFunc);
+}
+
+nsresult
+nsAttrAndChildArray::MakeMappedUnique(nsMappedAttributes* aAttributes)
+{
+  NS_ASSERTION(aAttributes, "missing attributes");
+
+  if (!mImpl && !GrowBy(1)) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  if (!aAttributes->GetStyleSheet()) {
+    // This doesn't currently happen, but it could if we do loading right
+
+    RefPtr<nsMappedAttributes> mapped(aAttributes);
+    mapped.swap(mImpl->mMappedAttrs);
+
+    return NS_OK;
+  }
+
+  RefPtr<nsMappedAttributes> mapped =
+    aAttributes->GetStyleSheet()->UniqueMappedAttributes(aAttributes);
+  NS_ENSURE_TRUE(mapped, NS_ERROR_OUT_OF_MEMORY);
+
+  if (mapped != aAttributes) {
+    // Reset the stylesheet of aAttributes so that it doesn't spend time
+    // trying to remove itself from the hash. There is no risk that aAttributes
+    // is in the hash since it will always have come from GetModifiableMapped,
+    // which never returns maps that are in the hash (such hashes are by
+    // nature not modifiable).
+    aAttributes->DropStyleSheetReference();
+  }
+  mapped.swap(mImpl->mMappedAttrs);
+
+  return NS_OK;
+}
+
+
+bool
+nsAttrAndChildArray::GrowBy(uint32_t aGrowSize)
+{
+  CheckedUint32 size = 0;
+  if (mImpl) {
+    size += mImpl->mBufferSize;
+    size += NS_IMPL_EXTRA_SIZE;
+    if (!size.isValid()) {
+      return false;
+    }
+  }
+
+  CheckedUint32 minSize = size.value();
+  minSize += aGrowSize;
+  if (!minSize.isValid()) {
+    return false;
+  }
+
+  if (minSize.value() <= ATTRCHILD_ARRAY_LINEAR_THRESHOLD) {
+    do {
+      size += ATTRCHILD_ARRAY_GROWSIZE;
+      if (!size.isValid()) {
+        return false;
+      }
+    } while (size.value() < minSize.value());
+  }
+  else {
+    uint32_t shift = mozilla::CeilingLog2(minSize.value());
+    if (shift >= 32) {
+      return false;
+    }
+
+    size = 1u << shift;
+  }
+
+  bool needToInitialize = !mImpl;
+  CheckedUint32 neededSize = size;
+  neededSize *= sizeof(void*);
+  if (!neededSize.isValid()) {
+    return false;
+  }
+
+  Impl* newImpl = static_cast<Impl*>(realloc(mImpl, neededSize.value()));
+  NS_ENSURE_TRUE(newImpl, false);
+
+  mImpl = newImpl;
+
+  // Set initial counts if we didn't have a buffer before
+  if (needToInitialize) {
+    mImpl->mMappedAttrs = nullptr;
+    SetAttrSlotAndChildCount(0, 0);
+  }
+
+  mImpl->mBufferSize = size.value() - NS_IMPL_EXTRA_SIZE;
+
+  return true;
+}
+
+bool
+nsAttrAndChildArray::AddAttrSlot()
+{
+  uint32_t slotCount = AttrSlotCount();
+  uint32_t childCount = ChildCount();
+
+  CheckedUint32 size = slotCount;
+  size += 1;
+  size *= ATTRSIZE;
+  size += childCount;
+  if (!size.isValid()) {
+    return false;
+  }
+
+  // Grow buffer if needed
+  if (!(mImpl && mImpl->mBufferSize >= size.value()) &&
+      !GrowBy(ATTRSIZE)) {
+    return false;
+  }
+
+  void** offset = mImpl->mBuffer + slotCount * ATTRSIZE;
+
+  if (childCount > 0) {
+    memmove(&ATTRS(mImpl)[slotCount + 1], &ATTRS(mImpl)[slotCount],
+            childCount * sizeof(nsIContent*));
+  }
+
+  SetAttrSlotCount(slotCount + 1);
+  offset[0] = nullptr;
+  offset[1] = nullptr;
+
+  return true;
+}
+
+inline void
+nsAttrAndChildArray::SetChildAtPos(void** aPos, nsIContent* aChild,
+                                   uint32_t aIndex, uint32_t aChildCount)
+{
+  NS_PRECONDITION(!aChild->GetNextSibling(), "aChild with next sibling?");
+  NS_PRECONDITION(!aChild->GetPreviousSibling(), "aChild with prev sibling?");
+
+  *aPos = aChild;
+  NS_ADDREF(aChild);
+  if (aIndex != 0) {
+    nsIContent* previous = static_cast<nsIContent*>(*(aPos - 1));
+    aChild->mPreviousSibling = previous;
+    previous->mNextSibling = aChild;
+  }
+  if (aIndex != aChildCount) {
+    nsIContent* next = static_cast<nsIContent*>(*(aPos + 1));
+    aChild->mNextSibling = next;
+    next->mPreviousSibling = aChild;
+  }
+}
+
+size_t
+nsAttrAndChildArray::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
+{
+  size_t n = 0;
+  if (mImpl) {
+    // Don't add the size taken by *mMappedAttrs because it's shared.
+
+    n += aMallocSizeOf(mImpl);
+
+    uint32_t slotCount = AttrSlotCount();
+    for (uint32_t i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
+      nsAttrValue* value = &ATTRS(mImpl)[i].mValue;
+      n += value->SizeOfExcludingThis(aMallocSizeOf);
+    }
+  }
+
+  return n;
+}
+