tor-browser

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

AttrArray.cpp (11580B)

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