dom/base/AttrArray.cpp

   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 /*
   8  * Storage of the children and attributes of a DOM node; storage for
   9  * the two is unified to minimize footprint.
  10  */
  11
  12 #include "AttrArray.h"
  13
  14 #include "mozilla/AttributeStyles.h"
  15 #include "mozilla/CheckedInt.h"
  16 #include "mozilla/MathAlgorithms.h"
  17 #include "mozilla/MemoryReporting.h"
  18 #include "mozilla/ServoBindings.h"
  19
  20 #include "nsString.h"
  21 #include "nsUnicharUtils.h"
  22 #include "nsContentUtils.h"  // nsAutoScriptBlocker
  23
  24 using mozilla::CheckedUint32;
  25
  26 AttrArray::Impl::~Impl() {
  27   for (InternalAttr& attr : Attrs()) {
  28     attr.~InternalAttr();
  29   }
  30   if (auto* decl = GetMappedDeclarationBlock()) {
  31     Servo_DeclarationBlock_Release(decl);
  32     mMappedAttributeBits = 0;
  33   }
  34 }
  35
  36 void AttrArray::SetMappedDeclarationBlock(
  37     already_AddRefed<mozilla::StyleLockedDeclarationBlock> aBlock) {
  38   MOZ_ASSERT(NS_IsMainThread());
  39   MOZ_ASSERT(mImpl);
  40   MOZ_ASSERT(IsPendingMappedAttributeEvaluation());
  41   if (auto* decl = GetMappedDeclarationBlock()) {
  42     Servo_DeclarationBlock_Release(decl);
  43   }
  44   mImpl->mMappedAttributeBits = reinterpret_cast<uintptr_t>(aBlock.take());
  45   MOZ_ASSERT(!IsPendingMappedAttributeEvaluation());
  46 }
  47
  48 const nsAttrValue* AttrArray::GetAttr(const nsAtom* aLocalName) const {
  49   NS_ASSERTION(aLocalName, "Must have attr name");
  50   for (const InternalAttr& attr : Attrs()) {
  51     if (attr.mName.Equals(aLocalName)) {
  52       return &attr.mValue;
  53     }
  54   }
  55   return nullptr;
  56 }
  57
  58 const nsAttrValue* AttrArray::GetAttr(const nsAtom* aLocalName,
  59                                       int32_t aNamespaceID) const {
  60   NS_ASSERTION(aLocalName, "Must have attr name");
  61   NS_ASSERTION(aNamespaceID != kNameSpaceID_Unknown, "Must have namespace");
  62   if (aNamespaceID == kNameSpaceID_None) {
  63     // This should be the common case so lets use the optimized loop
  64     return GetAttr(aLocalName);
  65   }
  66   for (const InternalAttr& attr : Attrs()) {
  67     if (attr.mName.Equals(aLocalName, aNamespaceID)) {
  68       return &attr.mValue;
  69     }
  70   }
  71   return nullptr;
  72 }
  73
  74 const nsAttrValue* AttrArray::GetAttr(const nsAString& aLocalName) const {
  75   for (const InternalAttr& attr : Attrs()) {
  76     if (attr.mName.Equals(aLocalName)) {
  77       return &attr.mValue;
  78     }
  79   }
  80   return nullptr;
  81 }
  82
  83 const nsAttrValue* AttrArray::GetAttr(const nsAString& aName,
  84                                       nsCaseTreatment aCaseSensitive) const {
  85   // Check whether someone is being silly and passing non-lowercase
  86   // attr names.
  87   if (aCaseSensitive == eIgnoreCase &&
  88       nsContentUtils::StringContainsASCIIUpper(aName)) {
  89     // Try again with a lowercased name, but make sure we can't reenter this
  90     // block by passing eCaseSensitive for aCaseSensitive.
  91     nsAutoString lowercase;
  92     nsContentUtils::ASCIIToLower(aName, lowercase);
  93     return GetAttr(lowercase, eCaseMatters);
  94   }
  95
  96   for (const InternalAttr& attr : Attrs()) {
  97     if (attr.mName.QualifiedNameEquals(aName)) {
  98       return &attr.mValue;
  99     }
 100   }
 101
 102   return nullptr;
 103 }
 104
 105 const nsAttrValue* AttrArray::AttrAt(uint32_t aPos) const {
 106   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
 107   return &mImpl->Attrs()[aPos].mValue;
 108 }
 109
 110 template <typename Name>
 111 inline nsresult AttrArray::AddNewAttribute(Name* aName, nsAttrValue& aValue) {
 112   MOZ_ASSERT(!mImpl || mImpl->mCapacity >= mImpl->mAttrCount);
 113   if (!mImpl || mImpl->mCapacity == mImpl->mAttrCount) {
 114     if (!GrowBy(1)) {
 115       return NS_ERROR_OUT_OF_MEMORY;
 116     }
 117   }
 118
 119   InternalAttr& attr = mImpl->mBuffer[mImpl->mAttrCount++];
 120   new (&attr.mName) nsAttrName(aName);
 121   new (&attr.mValue) nsAttrValue();
 122   attr.mValue.SwapValueWith(aValue);
 123   return NS_OK;
 124 }
 125
 126 nsresult AttrArray::SetAndSwapAttr(nsAtom* aLocalName, nsAttrValue& aValue,
 127                                    bool* aHadValue) {
 128   *aHadValue = false;
 129
 130   for (InternalAttr& attr : Attrs()) {
 131     if (attr.mName.Equals(aLocalName)) {
 132       attr.mValue.SwapValueWith(aValue);
 133       *aHadValue = true;
 134       return NS_OK;
 135     }
 136   }
 137
 138   return AddNewAttribute(aLocalName, aValue);
 139 }
 140
 141 nsresult AttrArray::SetAndSwapAttr(mozilla::dom::NodeInfo* aName,
 142                                    nsAttrValue& aValue, bool* aHadValue) {
 143   int32_t namespaceID = aName->NamespaceID();
 144   nsAtom* localName = aName->NameAtom();
 145   if (namespaceID == kNameSpaceID_None) {
 146     return SetAndSwapAttr(localName, aValue, aHadValue);
 147   }
 148
 149   *aHadValue = false;
 150   for (InternalAttr& attr : Attrs()) {
 151     if (attr.mName.Equals(localName, namespaceID)) {
 152       attr.mName.SetTo(aName);
 153       attr.mValue.SwapValueWith(aValue);
 154       *aHadValue = true;
 155       return NS_OK;
 156     }
 157   }
 158
 159   return AddNewAttribute(aName, aValue);
 160 }
 161
 162 nsresult AttrArray::RemoveAttrAt(uint32_t aPos, nsAttrValue& aValue) {
 163   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds");
 164
 165   mImpl->mBuffer[aPos].mValue.SwapValueWith(aValue);
 166   mImpl->mBuffer[aPos].~InternalAttr();
 167
 168   memmove(mImpl->mBuffer + aPos, mImpl->mBuffer + aPos + 1,
 169           (mImpl->mAttrCount - aPos - 1) * sizeof(InternalAttr));
 170
 171   --mImpl->mAttrCount;
 172   return NS_OK;
 173 }
 174
 175 mozilla::dom::BorrowedAttrInfo AttrArray::AttrInfoAt(uint32_t aPos) const {
 176   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
 177   InternalAttr& attr = mImpl->mBuffer[aPos];
 178   return BorrowedAttrInfo(&attr.mName, &attr.mValue);
 179 }
 180
 181 const nsAttrName* AttrArray::AttrNameAt(uint32_t aPos) const {
 182   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
 183   return &mImpl->mBuffer[aPos].mName;
 184 }
 185
 186 const nsAttrName* AttrArray::GetSafeAttrNameAt(uint32_t aPos) const {
 187   if (aPos >= AttrCount()) {
 188     return nullptr;
 189   }
 190   return &mImpl->mBuffer[aPos].mName;
 191 }
 192
 193 const nsAttrName* AttrArray::GetExistingAttrNameFromQName(
 194     const nsAString& aName) const {
 195   for (const InternalAttr& attr : Attrs()) {
 196     if (attr.mName.QualifiedNameEquals(aName)) {
 197       return &attr.mName;
 198     }
 199   }
 200   return nullptr;
 201 }
 202
 203 int32_t AttrArray::IndexOfAttr(const nsAtom* aLocalName) const {
 204   int32_t i = 0;
 205   for (const InternalAttr& attr : Attrs()) {
 206     if (attr.mName.Equals(aLocalName)) {
 207       return i;
 208     }
 209     ++i;
 210   }
 211   return -1;
 212 }
 213
 214 int32_t AttrArray::IndexOfAttr(const nsAtom* aLocalName,
 215                                int32_t aNamespaceID) const {
 216   if (aNamespaceID == kNameSpaceID_None) {
 217     // This should be the common case so lets use the optimized loop
 218     return IndexOfAttr(aLocalName);
 219   }
 220   int32_t i = 0;
 221   for (const InternalAttr& attr : Attrs()) {
 222     if (attr.mName.Equals(aLocalName, aNamespaceID)) {
 223       return i;
 224     }
 225     ++i;
 226   }
 227   return -1;
 228 }
 229
 230 void AttrArray::Compact() {
 231   if (!mImpl) {
 232     return;
 233   }
 234
 235   if (!mImpl->mAttrCount && !mImpl->mMappedAttributeBits) {
 236     mImpl.reset();
 237     return;
 238   }
 239
 240   // Nothing to do.
 241   if (mImpl->mAttrCount == mImpl->mCapacity) {
 242     return;
 243   }
 244
 245   Impl* oldImpl = mImpl.release();
 246   Impl* impl = static_cast<Impl*>(
 247       realloc(oldImpl, Impl::AllocationSizeForAttributes(oldImpl->mAttrCount)));
 248   if (!impl) {
 249     mImpl.reset(oldImpl);
 250     return;
 251   }
 252   impl->mCapacity = impl->mAttrCount;
 253   mImpl.reset(impl);
 254 }
 255
 256 nsresult AttrArray::EnsureCapacityToClone(const AttrArray& aOther) {
 257   MOZ_ASSERT(!mImpl,
 258              "AttrArray::EnsureCapacityToClone requires the array be empty "
 259              "when called");
 260
 261   uint32_t attrCount = aOther.AttrCount();
 262   if (!attrCount) {
 263     return NS_OK;
 264   }
 265
 266   // No need to use a CheckedUint32 because we are cloning. We know that we
 267   // have already allocated an AttrArray of this size.
 268   mImpl.reset(
 269       static_cast<Impl*>(malloc(Impl::AllocationSizeForAttributes(attrCount))));
 270   NS_ENSURE_TRUE(mImpl, NS_ERROR_OUT_OF_MEMORY);
 271
 272   mImpl->mMappedAttributeBits = 0;
 273   mImpl->mCapacity = attrCount;
 274   mImpl->mAttrCount = 0;
 275
 276   return NS_OK;
 277 }
 278
 279 bool AttrArray::GrowBy(uint32_t aGrowSize) {
 280   const uint32_t kLinearThreshold = 16;
 281   const uint32_t kLinearGrowSize = 4;
 282
 283   CheckedUint32 capacity = mImpl ? mImpl->mCapacity : 0;
 284   CheckedUint32 minCapacity = capacity;
 285   minCapacity += aGrowSize;
 286   if (!minCapacity.isValid()) {
 287     return false;
 288   }
 289
 290   if (capacity.value() <= kLinearThreshold) {
 291     do {
 292       capacity += kLinearGrowSize;
 293       if (!capacity.isValid()) {
 294         return false;
 295       }
 296     } while (capacity.value() < minCapacity.value());
 297   } else {
 298     uint32_t shift = mozilla::CeilingLog2(minCapacity.value());
 299     if (shift >= 32) {
 300       return false;
 301     }
 302     capacity = 1u << shift;
 303   }
 304
 305   return GrowTo(capacity.value());
 306 }
 307
 308 bool AttrArray::GrowTo(uint32_t aCapacity) {
 309   uint32_t oldCapacity = mImpl ? mImpl->mCapacity : 0;
 310   if (aCapacity <= oldCapacity) {
 311     return true;
 312   }
 313
 314   CheckedUint32 sizeInBytes = aCapacity;
 315   sizeInBytes *= sizeof(InternalAttr);
 316   if (!sizeInBytes.isValid()) {
 317     return false;
 318   }
 319
 320   sizeInBytes += sizeof(Impl);
 321   if (!sizeInBytes.isValid()) {
 322     return false;
 323   }
 324
 325   MOZ_ASSERT(sizeInBytes.value() ==
 326              Impl::AllocationSizeForAttributes(aCapacity));
 327
 328   const bool needToInitialize = !mImpl;
 329   Impl* oldImpl = mImpl.release();
 330   Impl* newImpl = static_cast<Impl*>(realloc(oldImpl, sizeInBytes.value()));
 331   if (!newImpl) {
 332     mImpl.reset(oldImpl);
 333     return false;
 334   }
 335
 336   mImpl.reset(newImpl);
 337
 338   // Set initial counts if we didn't have a buffer before
 339   if (needToInitialize) {
 340     mImpl->mMappedAttributeBits = 0;
 341     mImpl->mAttrCount = 0;
 342   }
 343
 344   mImpl->mCapacity = aCapacity;
 345   return true;
 346 }
 347
 348 size_t AttrArray::SizeOfExcludingThis(
 349     mozilla::MallocSizeOf aMallocSizeOf) const {
 350   if (!mImpl) {
 351     return 0;
 352   }
 353   size_t n = aMallocSizeOf(mImpl.get());
 354   for (const InternalAttr& attr : Attrs()) {
 355     n += attr.mValue.SizeOfExcludingThis(aMallocSizeOf);
 356   }
 357   return n;
 358 }
 359
 360 int32_t AttrArray::FindAttrValueIn(int32_t aNameSpaceID, const nsAtom* aName,
 361                                    AttrValuesArray* aValues,
 362                                    nsCaseTreatment aCaseSensitive) const {
 363   NS_ASSERTION(aName, "Must have attr name");
 364   NS_ASSERTION(aNameSpaceID != kNameSpaceID_Unknown, "Must have namespace");
 365   NS_ASSERTION(aValues, "Null value array");
 366
 367   const nsAttrValue* val = GetAttr(aName, aNameSpaceID);
 368   if (val) {
 369     for (int32_t i = 0; aValues[i]; ++i) {
 370       if (val->Equals(aValues[i], aCaseSensitive)) {
 371         return i;
 372       }
 373     }
 374     return ATTR_VALUE_NO_MATCH;
 375   }
 376   return ATTR_MISSING;
 377 }