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   // InternalAttr are not trivially copyable *but* we manually called the
 169   // destructor so the memmove should be ok.
 170   memmove((void*)(mImpl->mBuffer + aPos), mImpl->mBuffer + aPos + 1,
 171           (mImpl->mAttrCount - aPos - 1) * sizeof(InternalAttr));
 172
 173   --mImpl->mAttrCount;
 174   return NS_OK;
 175 }
 176
 177 mozilla::dom::BorrowedAttrInfo AttrArray::AttrInfoAt(uint32_t aPos) const {
 178   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
 179   InternalAttr& attr = mImpl->mBuffer[aPos];
 180   return BorrowedAttrInfo(&attr.mName, &attr.mValue);
 181 }
 182
 183 const nsAttrName* AttrArray::AttrNameAt(uint32_t aPos) const {
 184   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
 185   return &mImpl->mBuffer[aPos].mName;
 186 }
 187
 188 const nsAttrName* AttrArray::GetSafeAttrNameAt(uint32_t aPos) const {
 189   if (aPos >= AttrCount()) {
 190     return nullptr;
 191   }
 192   return &mImpl->mBuffer[aPos].mName;
 193 }
 194
 195 const nsAttrName* AttrArray::GetExistingAttrNameFromQName(
 196     const nsAString& aName) const {
 197   for (const InternalAttr& attr : Attrs()) {
 198     if (attr.mName.QualifiedNameEquals(aName)) {
 199       return &attr.mName;
 200     }
 201   }
 202   return nullptr;
 203 }
 204
 205 int32_t AttrArray::IndexOfAttr(const nsAtom* aLocalName) const {
 206   int32_t i = 0;
 207   for (const InternalAttr& attr : Attrs()) {
 208     if (attr.mName.Equals(aLocalName)) {
 209       return i;
 210     }
 211     ++i;
 212   }
 213   return -1;
 214 }
 215
 216 int32_t AttrArray::IndexOfAttr(const nsAtom* aLocalName,
 217                                int32_t aNamespaceID) const {
 218   if (aNamespaceID == kNameSpaceID_None) {
 219     // This should be the common case so lets use the optimized loop
 220     return IndexOfAttr(aLocalName);
 221   }
 222   int32_t i = 0;
 223   for (const InternalAttr& attr : Attrs()) {
 224     if (attr.mName.Equals(aLocalName, aNamespaceID)) {
 225       return i;
 226     }
 227     ++i;
 228   }
 229   return -1;
 230 }
 231
 232 void AttrArray::Compact() {
 233   if (!mImpl) {
 234     return;
 235   }
 236
 237   if (!mImpl->mAttrCount && !mImpl->mMappedAttributeBits) {
 238     mImpl.reset();
 239     return;
 240   }
 241
 242   // Nothing to do.
 243   if (mImpl->mAttrCount == mImpl->mCapacity) {
 244     return;
 245   }
 246
 247   Impl* oldImpl = mImpl.release();
 248   Impl* impl = static_cast<Impl*>(
 249       realloc(oldImpl, Impl::AllocationSizeForAttributes(oldImpl->mAttrCount)));
 250   if (!impl) {
 251     mImpl.reset(oldImpl);
 252     return;
 253   }
 254   impl->mCapacity = impl->mAttrCount;
 255   mImpl.reset(impl);
 256 }
 257
 258 nsresult AttrArray::EnsureCapacityToClone(const AttrArray& aOther) {
 259   MOZ_ASSERT(!mImpl,
 260              "AttrArray::EnsureCapacityToClone requires the array be empty "
 261              "when called");
 262
 263   uint32_t attrCount = aOther.AttrCount();
 264   if (!attrCount) {
 265     return NS_OK;
 266   }
 267
 268   // No need to use a CheckedUint32 because we are cloning. We know that we
 269   // have already allocated an AttrArray of this size.
 270   mImpl.reset(
 271       static_cast<Impl*>(malloc(Impl::AllocationSizeForAttributes(attrCount))));
 272   NS_ENSURE_TRUE(mImpl, NS_ERROR_OUT_OF_MEMORY);
 273
 274   mImpl->mMappedAttributeBits = 0;
 275   mImpl->mCapacity = attrCount;
 276   mImpl->mAttrCount = 0;
 277
 278   return NS_OK;
 279 }
 280
 281 bool AttrArray::GrowBy(uint32_t aGrowSize) {
 282   const uint32_t kLinearThreshold = 16;
 283   const uint32_t kLinearGrowSize = 4;
 284
 285   CheckedUint32 capacity = mImpl ? mImpl->mCapacity : 0;
 286   CheckedUint32 minCapacity = capacity;
 287   minCapacity += aGrowSize;
 288   if (!minCapacity.isValid()) {
 289     return false;
 290   }
 291
 292   if (capacity.value() <= kLinearThreshold) {
 293     do {
 294       capacity += kLinearGrowSize;
 295       if (!capacity.isValid()) {
 296         return false;
 297       }
 298     } while (capacity.value() < minCapacity.value());
 299   } else {
 300     uint32_t shift = mozilla::CeilingLog2(minCapacity.value());
 301     if (shift >= 32) {
 302       return false;
 303     }
 304     capacity = 1u << shift;
 305   }
 306
 307   return GrowTo(capacity.value());
 308 }
 309
 310 bool AttrArray::GrowTo(uint32_t aCapacity) {
 311   uint32_t oldCapacity = mImpl ? mImpl->mCapacity : 0;
 312   if (aCapacity <= oldCapacity) {
 313     return true;
 314   }
 315
 316   CheckedUint32 sizeInBytes = aCapacity;
 317   sizeInBytes *= sizeof(InternalAttr);
 318   if (!sizeInBytes.isValid()) {
 319     return false;
 320   }
 321
 322   sizeInBytes += sizeof(Impl);
 323   if (!sizeInBytes.isValid()) {
 324     return false;
 325   }
 326
 327   MOZ_ASSERT(sizeInBytes.value() ==
 328              Impl::AllocationSizeForAttributes(aCapacity));
 329
 330   const bool needToInitialize = !mImpl;
 331   Impl* oldImpl = mImpl.release();
 332   Impl* newImpl = static_cast<Impl*>(realloc(oldImpl, sizeInBytes.value()));
 333   if (!newImpl) {
 334     mImpl.reset(oldImpl);
 335     return false;
 336   }
 337
 338   mImpl.reset(newImpl);
 339
 340   // Set initial counts if we didn't have a buffer before
 341   if (needToInitialize) {
 342     mImpl->mMappedAttributeBits = 0;
 343     mImpl->mAttrCount = 0;
 344   }
 345
 346   mImpl->mCapacity = aCapacity;
 347   return true;
 348 }
 349
 350 size_t AttrArray::SizeOfExcludingThis(
 351     mozilla::MallocSizeOf aMallocSizeOf) const {
 352   if (!mImpl) {
 353     return 0;
 354   }
 355   size_t n = aMallocSizeOf(mImpl.get());
 356   for (const InternalAttr& attr : Attrs()) {
 357     n += attr.mValue.SizeOfExcludingThis(aMallocSizeOf);
 358   }
 359   return n;
 360 }
 361
 362 int32_t AttrArray::FindAttrValueIn(int32_t aNameSpaceID, const nsAtom* aName,
 363                                    AttrValuesArray* aValues,
 364                                    nsCaseTreatment aCaseSensitive) const {
 365   NS_ASSERTION(aName, "Must have attr name");
 366   NS_ASSERTION(aNameSpaceID != kNameSpaceID_Unknown, "Must have namespace");
 367   NS_ASSERTION(aValues, "Null value array");
 368
 369   const nsAttrValue* val = GetAttr(aName, aNameSpaceID);
 370   if (val) {
 371     for (int32_t i = 0; aValues[i]; ++i) {
 372       if (val->Equals(aValues[i], aCaseSensitive)) {
 373         return i;
 374       }
 375     }
 376     return ATTR_VALUE_NO_MATCH;
 377   }
 378   return ATTR_MISSING;
 379 }