commit c043d7c313746e7a546b4d43732a0a82681ef376
parent a420bf02e3ab0195cb21403149b446583fe76264
Author: Denis Palmeiro <dpalmeiro@mozilla.com>
Date: Wed, 3 Dec 2025 14:46:42 +0000
Bug 1997380: Implement bloom filter for element attributes. r=smaug,emilio,firefox-style-system-reviewers
This patch stores a bloom filter in AttrArray to track attribute and class names
in the element tree. This infrastructure will be used to optmimize querySelector.
Differential Revision: https://phabricator.services.mozilla.com/D273066
Diffstat:
8 files changed, 452 insertions(+), 71 deletions(-)
diff --git a/dom/base/AttrArray.cpp b/dom/base/AttrArray.cpp
@@ -35,12 +35,12 @@ AttrArray::Impl::~Impl() {
void AttrArray::SetMappedDeclarationBlock(
already_AddRefed<mozilla::StyleLockedDeclarationBlock> aBlock) {
MOZ_ASSERT(NS_IsMainThread());
- MOZ_ASSERT(mImpl);
+ MOZ_ASSERT(HasImpl());
MOZ_ASSERT(IsPendingMappedAttributeEvaluation());
if (auto* decl = GetMappedDeclarationBlock()) {
Servo_DeclarationBlock_Release(decl);
}
- mImpl->mMappedAttributeBits = reinterpret_cast<uintptr_t>(aBlock.take());
+ GetImpl()->mMappedAttributeBits = reinterpret_cast<uintptr_t>(aBlock.take());
MOZ_ASSERT(!IsPendingMappedAttributeEvaluation());
}
@@ -103,13 +103,13 @@ const nsAttrValue* AttrArray::GetAttr(const nsAString& aName,
const nsAttrValue* AttrArray::AttrAt(uint32_t aPos) const {
NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
- return &mImpl->Attrs()[aPos].mValue;
+ return &GetImpl()->Attrs()[aPos].mValue;
}
template <typename Name>
inline nsresult AttrArray::AddNewAttribute(Name* aName, nsAttrValue& aValue) {
- MOZ_ASSERT(!mImpl || mImpl->mCapacity >= mImpl->mAttrCount);
- if (!mImpl || mImpl->mCapacity == mImpl->mAttrCount) {
+ MOZ_ASSERT(!HasImpl() || GetImpl()->mCapacity >= GetImpl()->mAttrCount);
+ if (!HasImpl() || GetImpl()->mCapacity == GetImpl()->mAttrCount) {
if (!GrowBy(1)) {
return NS_ERROR_OUT_OF_MEMORY;
}
@@ -161,27 +161,29 @@ nsresult AttrArray::SetAndSwapAttr(mozilla::dom::NodeInfo* aName,
nsresult AttrArray::RemoveAttrAt(uint32_t aPos, nsAttrValue& aValue) {
NS_ASSERTION(aPos < AttrCount(), "out-of-bounds");
- mImpl->mBuffer[aPos].mValue.SwapValueWith(aValue);
- mImpl->mBuffer[aPos].~InternalAttr();
+ Impl* impl = GetImpl();
+ impl->mBuffer[aPos].mValue.SwapValueWith(aValue);
+ impl->mBuffer[aPos].~InternalAttr();
// InternalAttr are not trivially copyable *but* we manually called the
// destructor so the memmove should be ok.
- memmove((void*)(mImpl->mBuffer + aPos), mImpl->mBuffer + aPos + 1,
- (mImpl->mAttrCount - aPos - 1) * sizeof(InternalAttr));
+ memmove((void*)(impl->mBuffer + aPos), impl->mBuffer + aPos + 1,
+ (impl->mAttrCount - aPos - 1) * sizeof(InternalAttr));
- --mImpl->mAttrCount;
+ --impl->mAttrCount;
return NS_OK;
}
mozilla::dom::BorrowedAttrInfo AttrArray::AttrInfoAt(uint32_t aPos) const {
NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
- InternalAttr& attr = mImpl->mBuffer[aPos];
- return BorrowedAttrInfo(&attr.mName, &attr.mValue);
+ const Impl* impl = GetImpl();
+ return BorrowedAttrInfo(&impl->mBuffer[aPos].mName,
+ &impl->mBuffer[aPos].mValue);
}
const nsAttrName* AttrArray::AttrNameAt(uint32_t aPos) const {
NS_ASSERTION(aPos < AttrCount(), "out-of-bounds access in AttrArray");
- return &mImpl->mBuffer[aPos].mName;
+ return &GetImpl()->mBuffer[aPos].mName;
}
[[nodiscard]] bool AttrArray::GetSafeAttrNameAt(
@@ -189,7 +191,7 @@ const nsAttrName* AttrArray::AttrNameAt(uint32_t aPos) const {
if (aPos >= AttrCount()) {
return false;
}
- *aResult = &mImpl->mBuffer[aPos].mName;
+ *aResult = &GetImpl()->mBuffer[aPos].mName;
return true;
}
@@ -239,33 +241,36 @@ int32_t AttrArray::IndexOfAttr(const nsAtom* aLocalName,
}
void AttrArray::Compact() {
- if (!mImpl) {
+ if (!HasImpl()) {
return;
}
- if (!mImpl->mAttrCount && !mImpl->mMappedAttributeBits) {
- mImpl.reset();
+ Impl* impl = GetImpl();
+ if (!impl->mAttrCount && !impl->mMappedAttributeBits) {
+ Clear();
return;
}
// Nothing to do.
- if (mImpl->mAttrCount == mImpl->mCapacity) {
+ if (impl->mAttrCount == impl->mCapacity) {
return;
}
+ // Extract the real pointer for realloc
Impl* oldImpl = mImpl.release();
- Impl* impl = static_cast<Impl*>(
+
+ Impl* newImpl = static_cast<Impl*>(
realloc(oldImpl, Impl::AllocationSizeForAttributes(oldImpl->mAttrCount)));
- if (!impl) {
- mImpl.reset(oldImpl);
+ if (!newImpl) {
+ SetImpl(oldImpl);
return;
}
- impl->mCapacity = impl->mAttrCount;
- mImpl.reset(impl);
+ newImpl->mCapacity = newImpl->mAttrCount;
+ SetImpl(newImpl);
}
nsresult AttrArray::EnsureCapacityToClone(const AttrArray& aOther) {
- MOZ_ASSERT(!mImpl,
+ MOZ_ASSERT(!HasImpl(),
"AttrArray::EnsureCapacityToClone requires the array be empty "
"when called");
@@ -276,13 +281,15 @@ nsresult AttrArray::EnsureCapacityToClone(const AttrArray& aOther) {
// No need to use a CheckedUint32 because we are cloning. We know that we
// have already allocated an AttrArray of this size.
- mImpl.reset(
- static_cast<Impl*>(malloc(Impl::AllocationSizeForAttributes(attrCount))));
- NS_ENSURE_TRUE(mImpl, NS_ERROR_OUT_OF_MEMORY);
+ Impl* impl =
+ static_cast<Impl*>(malloc(Impl::AllocationSizeForAttributes(attrCount)));
+ NS_ENSURE_TRUE(impl, NS_ERROR_OUT_OF_MEMORY);
- mImpl->mMappedAttributeBits = 0;
- mImpl->mCapacity = attrCount;
- mImpl->mAttrCount = 0;
+ impl->mMappedAttributeBits = 0;
+ impl->mCapacity = attrCount;
+ impl->mAttrCount = 0;
+ impl->mSubtreeBloomFilter = aOther.GetSubtreeBloomFilter();
+ SetImpl(impl);
return NS_OK;
}
@@ -291,7 +298,7 @@ bool AttrArray::GrowBy(uint32_t aGrowSize) {
const uint32_t kLinearThreshold = 16;
const uint32_t kLinearGrowSize = 4;
- CheckedUint32 capacity = mImpl ? mImpl->mCapacity : 0;
+ CheckedUint32 capacity = HasImpl() ? GetImpl()->mCapacity : 0;
CheckedUint32 minCapacity = capacity;
minCapacity += aGrowSize;
if (!minCapacity.isValid()) {
@@ -317,7 +324,7 @@ bool AttrArray::GrowBy(uint32_t aGrowSize) {
}
bool AttrArray::GrowTo(uint32_t aCapacity) {
- uint32_t oldCapacity = mImpl ? mImpl->mCapacity : 0;
+ uint32_t oldCapacity = HasImpl() ? GetImpl()->mCapacity : 0;
if (aCapacity <= oldCapacity) {
return true;
}
@@ -336,32 +343,46 @@ bool AttrArray::GrowTo(uint32_t aCapacity) {
MOZ_ASSERT(sizeInBytes.value() ==
Impl::AllocationSizeForAttributes(aCapacity));
- const bool needToInitialize = !mImpl;
- Impl* oldImpl = mImpl.release();
+ const bool needToInitialize = !HasImpl();
+ uint64_t oldBloom = 0xFFFFFFFFFFFFFFFFULL;
+ Impl* oldImpl = nullptr;
+
+ if (HasImpl()) {
+ // We have a real Impl pointer, extract it for realloc
+ oldImpl = mImpl.release();
+ } else if (HasTaggedBloom()) {
+ // Preserve bloom filter from the tagged value
+ oldBloom = GetTaggedBloom();
+ }
+
Impl* newImpl = static_cast<Impl*>(realloc(oldImpl, sizeInBytes.value()));
if (!newImpl) {
- mImpl.reset(oldImpl);
+ if (oldImpl) {
+ SetImpl(oldImpl);
+ } else if (HasTaggedBloom()) {
+ SetTaggedBloom(oldBloom);
+ }
return false;
}
- mImpl.reset(newImpl);
-
// Set initial counts if we didn't have a buffer before
if (needToInitialize) {
- mImpl->mMappedAttributeBits = 0;
- mImpl->mAttrCount = 0;
+ newImpl->mMappedAttributeBits = 0;
+ newImpl->mAttrCount = 0;
+ newImpl->mSubtreeBloomFilter = oldBloom;
}
- mImpl->mCapacity = aCapacity;
+ newImpl->mCapacity = aCapacity;
+ SetImpl(newImpl);
return true;
}
size_t AttrArray::SizeOfExcludingThis(
mozilla::MallocSizeOf aMallocSizeOf) const {
- if (!mImpl) {
+ if (!HasImpl()) {
return 0;
}
- size_t n = aMallocSizeOf(mImpl.get());
+ size_t n = aMallocSizeOf(GetImpl());
for (const InternalAttr& attr : Attrs()) {
n += attr.mValue.SizeOfExcludingThis(aMallocSizeOf);
}
diff --git a/dom/base/AttrArray.h b/dom/base/AttrArray.h
@@ -23,18 +23,36 @@
namespace mozilla {
class AttributeStyles;
struct StyleLockedDeclarationBlock;
+
+namespace dom {
+class Element;
+class ElementInternals;
+} // namespace dom
} // namespace mozilla
class AttrArray {
using BorrowedAttrInfo = mozilla::dom::BorrowedAttrInfo;
+ // Declare as friend to grant access to call SetAndSwapAttr.
+ friend class mozilla::dom::Element;
+ friend class mozilla::dom::ElementInternals;
+
public:
- AttrArray() = default;
- ~AttrArray() = default;
+ AttrArray() {
+ // Initialize bloom filter.
+ SetTaggedBloom(0x1ULL);
+ }
+ ~AttrArray() {
+ // If mImpl contains a tagged bloom filter (bit 0 = 1), we must clear it
+ // before the BindgenUniquePtr destructor tries to free it as a pointer.
+ if (HasTaggedBloom()) {
+ mImpl.release();
+ }
+ }
bool HasAttrs() const { return !!AttrCount(); }
- uint32_t AttrCount() const { return mImpl ? mImpl->mAttrCount : 0; }
+ uint32_t AttrCount() const { return HasImpl() ? GetImpl()->mAttrCount : 0; }
const nsAttrValue* GetAttr(const nsAtom* aLocalName) const;
@@ -48,14 +66,6 @@ class AttrArray {
const nsAttrValue* GetAttr(const nsAString& aName,
nsCaseTreatment aCaseSensitive) const;
const nsAttrValue* AttrAt(uint32_t aPos) const;
- // SetAndSwapAttr swaps the current attribute value with aValue.
- // If the attribute was unset, an empty value will be swapped into aValue
- // and aHadValue will be set to false. Otherwise, aHadValue will be set to
- // true.
- nsresult SetAndSwapAttr(nsAtom* aLocalName, nsAttrValue& aValue,
- bool* aHadValue);
- nsresult SetAndSwapAttr(mozilla::dom::NodeInfo* aName, nsAttrValue& aValue,
- bool* aHadValue);
// This stores the argument and clears the pending mapped attribute evaluation
// bit, so after calling this IsPendingMappedAttributeEvaluation() is
@@ -64,11 +74,11 @@ class AttrArray {
already_AddRefed<mozilla::StyleLockedDeclarationBlock>);
bool IsPendingMappedAttributeEvaluation() const {
- return mImpl && mImpl->mMappedAttributeBits & 1;
+ return HasImpl() && GetImpl()->mMappedAttributeBits & 1;
}
mozilla::StyleLockedDeclarationBlock* GetMappedDeclarationBlock() const {
- return mImpl ? mImpl->GetMappedDeclarationBlock() : nullptr;
+ return HasImpl() ? GetImpl()->GetMappedDeclarationBlock() : nullptr;
}
// Remove the attr at position aPos. The value of the attr is placed in
@@ -101,9 +111,9 @@ class AttrArray {
// Mark the element as pending mapped attribute evaluation. This should be
// called when a mapped attribute is changed (regardless of connectedness).
bool MarkAsPendingPresAttributeEvaluation() {
- // It'd be great to be able to assert that mImpl is non-null or we're the
+ // It'd be great to be able to assert that HasImpl() is true or we're the
// <body> or <svg> elements.
- if (MOZ_UNLIKELY(!mImpl) && !GrowBy(1)) {
+ if (MOZ_UNLIKELY(!HasImpl()) && !GrowBy(1)) {
return false;
}
InfallibleMarkAsPendingPresAttributeEvaluation();
@@ -112,8 +122,8 @@ class AttrArray {
// See above.
void InfallibleMarkAsPendingPresAttributeEvaluation() {
- MOZ_ASSERT(mImpl);
- mImpl->mMappedAttributeBits |= 1;
+ MOZ_ASSERT(HasImpl());
+ GetImpl()->mMappedAttributeBits |= 1;
}
// Clear the servo declaration block on the mapped attributes, if any
@@ -188,7 +198,17 @@ class AttrArray {
bool GrowBy(uint32_t aGrowSize);
bool GrowTo(uint32_t aCapacity);
- void Clear() { mImpl.reset(); }
+ void Clear() {
+ // If mImpl contains a tagged bloom filter, release it first to prevent
+ // unique_ptr from trying to delete it as a pointer
+ if (HasTaggedBloom()) {
+ mImpl.release();
+ } else {
+ mImpl.reset();
+ }
+ // Reinitialize to default tagged bloom filter
+ SetTaggedBloom(0x1ULL);
+ }
private:
// Tries to create an attribute, growing the buffer if needed, with the given
@@ -234,18 +254,134 @@ class AttrArray {
// have), and are pending an update to recompute our declaration.
uintptr_t mMappedAttributeBits = 0;
+ // Combined bloom filter (63 bits) for both classes and attributes
+ // Bit 0: Always 1 to match tagged pointer implementation.
+ // Bits 1-63: Combined bloom filter (63 bits)
+ uint64_t mSubtreeBloomFilter;
+
+ public:
+ Impl() : mSubtreeBloomFilter(0xFFFFFFFFFFFFFFFFULL) {}
+
// Allocated in the same buffer as `Impl`.
InternalAttr mBuffer[0];
};
mozilla::Span<InternalAttr> Attrs() {
- return mImpl ? mImpl->Attrs() : mozilla::Span<InternalAttr>();
+ return HasImpl() ? GetImpl()->Attrs() : mozilla::Span<InternalAttr>();
}
mozilla::Span<const InternalAttr> Attrs() const {
- return mImpl ? mImpl->Attrs() : mozilla::Span<const InternalAttr>();
+ return HasImpl() ? GetImpl()->Attrs() : mozilla::Span<const InternalAttr>();
+ }
+
+ bool HasTaggedBloom() const {
+ return (reinterpret_cast<uintptr_t>(mImpl.get()) & 1) != 0;
+ }
+
+ bool HasImpl() const {
+ MOZ_ASSERT(mImpl.get() != nullptr);
+ return !HasTaggedBloom();
+ }
+
+ Impl* GetImpl() {
+ MOZ_ASSERT(HasImpl());
+ return mImpl.get();
}
+ const Impl* GetImpl() const {
+ MOZ_ASSERT(HasImpl());
+ return mImpl.get();
+ }
+
+ uint64_t GetTaggedBloom() const {
+ MOZ_ASSERT(HasTaggedBloom());
+ return reinterpret_cast<uint64_t>(mImpl.get());
+ }
+
+ void SetTaggedBloom(uint64_t aBloom) {
+ // If we already have a tagged bloom, release it first
+ if (HasTaggedBloom()) {
+ mImpl.release();
+ }
+ // Ensure bit 0 is set (tag bit) and upper bit is clear (valid pointer
+ // range)
+ MOZ_ASSERT((aBloom & 1) != 0);
+ mImpl.reset(reinterpret_cast<Impl*>(static_cast<uintptr_t>(aBloom)));
+ }
+
+ void SetImpl(Impl* aImpl) {
+ MOZ_ASSERT(aImpl != nullptr &&
+ (reinterpret_cast<uintptr_t>(aImpl) & 1) == 0);
+ // If we currently have a tagged bloom filter, release it first to prevent
+ // unique_ptr from trying to delete it as a pointer
+ if (HasTaggedBloom()) {
+ mImpl.release();
+ }
+ mImpl.reset(aImpl);
+ }
+
+ public:
+ // Set bloom filter directly from 64-bit value
+ void SetSubtreeBloomFilter(uint64_t aBloom) {
+ if (HasImpl()) {
+ GetImpl()->mSubtreeBloomFilter = aBloom;
+ } else {
+ SetTaggedBloom(aBloom);
+ }
+ }
+
+ // Get bloom filter, used for fast querySelector
+ uint64_t GetSubtreeBloomFilter() const {
+ if (HasImpl()) {
+ return GetImpl()->mSubtreeBloomFilter;
+ } else if (HasTaggedBloom()) {
+ return GetTaggedBloom();
+ }
+ MOZ_ASSERT_UNREACHABLE("Bloom filter should never be nullptr");
+ return 0xFFFFFFFFFFFFFFFFULL;
+ }
+
+ // Update bloom filter with new 64-bit hash
+ void UpdateSubtreeBloomFilter(uint64_t aHash) {
+ if (HasImpl()) {
+ GetImpl()->mSubtreeBloomFilter |= aHash;
+ } else {
+ uint64_t current = GetSubtreeBloomFilter();
+ SetTaggedBloom(current | aHash);
+ }
+ }
+
+ // Check if bloom may contain the given hash
+ bool BloomMayHave(uint64_t aHash) const {
+ uint64_t bloom = GetSubtreeBloomFilter();
+ return (bloom & aHash) == aHash;
+ }
+
+ private:
+ // Internal method that swaps the current attribute value with aValue.
+ // Does NOT update bloom filters - external code should always use
+ // Element::SetAndSwapAttr instead, which calls this and updates bloom
+ // filters. If the attribute was unset, an empty value will be swapped into
+ // aValue and aHadValue will be set to false. Otherwise, aHadValue will be set
+ // to true.
+ nsresult SetAndSwapAttr(nsAtom* aLocalName, nsAttrValue& aValue,
+ bool* aHadValue);
+ nsresult SetAndSwapAttr(mozilla::dom::NodeInfo* aName, nsAttrValue& aValue,
+ bool* aHadValue);
+
+ // mImpl serves dual purposes using pointer tagging:
+ //
+ // 1. When the element has no attributes:
+ // - Stores a "tagged bloom filter" (bit 0 is 1). The remaining
+ // bits are used as a bloomfilter to identify the existence of
+ // attribute & class names in this subtree for querySelector.
+ //
+ // 2. When the element has attributes:
+ // - Points to an Impl struct (bit 0 is 0).
+ // - Contains actual attribute storage and the bloom filter
+ // is now copied as a member of Impl.
+ //
+ // Use HasTaggedBloom() vs HasImpl() to distinguish.
mozilla::BindgenUniquePtr<Impl> mImpl;
};
diff --git a/dom/base/Element.cpp b/dom/base/Element.cpp
@@ -2201,6 +2201,144 @@ bool Element::HasVisibleScrollbars() {
return scrollFrame && !scrollFrame->GetScrollbarVisibility().isEmpty();
}
+// Hash function for 63-bit bloom filter (k=2)
+// Returns 64-bit value with bit 0 set to 1 and 2 bits set in range 1-63
+static uint64_t HashForBloomFilter63(const nsAtom* aAtom) {
+ if (!aAtom) {
+ return 1ULL; // Just the tag bit
+ }
+ uint32_t hash = aAtom->hash();
+ uint64_t filter = 1ULL;
+ // Set 2 bits in the 63-bit range (bits 1-63)
+ filter |= 1ULL << (1 + (hash % 63)); // First hash function
+ filter |= 1ULL << (1 + ((hash >> 6) % 63)); // Second hash function
+ return filter;
+}
+
+// Propagates this element's bloom filter up the tree by OR-ing it with
+// all ancestor element bloom filters, stopping early if no new bits are added.
+void Element::PropagateBloomFilterToParents() {
+ Element* toUpdate = this;
+ Element* parent = GetParentElement();
+
+ while (parent) {
+ uint64_t childBloom = toUpdate->mAttrs.GetSubtreeBloomFilter();
+ uint64_t parentBloom = parent->mAttrs.GetSubtreeBloomFilter();
+ uint64_t newBloom = parentBloom | childBloom;
+
+ if (newBloom == parentBloom) {
+ break;
+ }
+ parent->mAttrs.SetSubtreeBloomFilter(newBloom);
+ toUpdate = parent;
+ parent = toUpdate->GetParentElement();
+ }
+}
+
+// Hashes all class names in a class attribute value for the bloom filter.
+// Handles both single class (eAtom) and multiple classes (eAtomArray).
+static uint64_t HashClassesForBloom(const nsAttrValue* aValue) {
+ uint64_t filter = 1ULL; // Start with tag bit
+ if (!aValue) {
+ return filter;
+ }
+
+ if (aValue->Type() == nsAttrValue::eAtomArray) {
+ const mozilla::AttrAtomArray* array = aValue->GetAtomArrayValue();
+ if (array) {
+ for (const RefPtr<nsAtom>& className : array->mArray) {
+ filter |= HashForBloomFilter63(className);
+ }
+ }
+ } else if (aValue->Type() == nsAttrValue::eAtom) {
+ filter |= HashForBloomFilter63(aValue->GetAtomValue());
+ }
+#ifdef DEBUG
+ else {
+ // Assert that only empty strings make it here.
+ nsAutoString value;
+ aValue->ToString(value);
+ bool isOnlyWhitespace = true;
+ for (uint32_t i = 0; i < value.Length(); i++) {
+ if (!nsContentUtils::IsHTMLWhitespace(value[i])) {
+ isOnlyWhitespace = false;
+ break;
+ }
+ }
+ MOZ_ASSERT(isOnlyWhitespace, "Expecting only empty strings here.");
+ }
+#endif
+
+ return filter;
+}
+
+#ifdef DEBUG
+// Asserts that the bloom filter contains all expected bits from
+// current attributes, classes, and descendant bloom filters.
+void Element::VerifySubtreeBloomFilter() const {
+ uint64_t expectedBloom = 1ULL;
+
+ // Hash all attribute names in kNameSpaceID_None namespace
+ uint32_t attrCount = GetAttrCount();
+ for (uint32_t i = 0; i < attrCount; i++) {
+ const nsAttrName* attrName = GetAttrNameAt(i);
+ MOZ_ASSERT(attrName, "Attribute name should not be null");
+ if (attrName->NamespaceEquals(kNameSpaceID_None)) {
+ nsAtom* localName = attrName->LocalName();
+ expectedBloom |= HashForBloomFilter63(localName);
+
+ if (!localName->IsAsciiLowercase()) {
+ Document* doc = OwnerDoc();
+ if (!IsHTMLElement() && doc->IsHTMLDocument()) {
+ RefPtr<nsAtom> lowercaseAttr(localName);
+ ToLowerCaseASCII(lowercaseAttr);
+ expectedBloom |= HashForBloomFilter63(lowercaseAttr);
+ }
+ }
+ }
+ }
+
+ // Hash class names
+ const nsAttrValue* classAttr = GetClasses();
+ expectedBloom |= HashClassesForBloom(classAttr);
+
+ // Include children's bloom filters
+ for (Element* child = GetFirstElementChild(); child;
+ child = child->GetNextElementSibling()) {
+ expectedBloom |= child->mAttrs.GetSubtreeBloomFilter();
+ }
+
+ uint64_t actualBloom = mAttrs.GetSubtreeBloomFilter();
+ // Bloom filters are append-only: bits can be set but never cleared.
+ // So actualBloom may contain extra bits from removed attributes.
+ // We only check that all expected bits are present.
+ MOZ_ASSERT((actualBloom & expectedBloom) == expectedBloom,
+ "Bloom filter missing required bits");
+}
+#endif
+
+void Element::UpdateSubtreeBloomFilterForClass(const nsAttrValue* aClassValue) {
+ if (!aClassValue) {
+ return;
+ }
+ mAttrs.UpdateSubtreeBloomFilter(HashClassesForBloom(aClassValue));
+}
+
+void Element::UpdateSubtreeBloomFilterForAttribute(nsAtom* aAttribute) {
+ MOZ_ASSERT(aAttribute, "Attribute should not be null");
+ mAttrs.UpdateSubtreeBloomFilter(HashForBloomFilter63(aAttribute));
+
+ // For non-HTML elements in HTML documents, also add the lowercase hash.
+ // This ensures querySelector on HTML ancestors can find these attributes,
+ // since HTML elements use case-insensitive attribute matching.
+ if (!aAttribute->IsAsciiLowercase() && !IsHTMLElement() &&
+ OwnerDoc()->IsHTMLDocument()) {
+ RefPtr<nsAtom> lowercaseAttr(aAttribute);
+ ToLowerCaseASCII(lowercaseAttr);
+ mAttrs.UpdateSubtreeBloomFilter(HashForBloomFilter63(lowercaseAttr));
+ }
+}
+
nsresult Element::BindToTree(BindContext& aContext, nsINode& aParent) {
MOZ_ASSERT(aParent.IsContent() || aParent.IsDocument(),
"Must have content or document parent!");
@@ -2339,6 +2477,13 @@ nsresult Element::BindToTree(BindContext& aContext, nsINode& aParent) {
MOZ_ASSERT(aParent.IsInComposedDoc() == IsInComposedDoc());
MOZ_ASSERT(aParent.IsInShadowTree() == IsInShadowTree());
MOZ_ASSERT(aParent.SubtreeRoot() == SubtreeRoot());
+
+#ifdef DEBUG
+ VerifySubtreeBloomFilter();
+#endif
+
+ // When binding to tree, propagate this element's bloom to parents.
+ PropagateBloomFilterToParents();
return NS_OK;
}
@@ -2890,6 +3035,37 @@ nsresult Element::SetAttr(int32_t aNamespaceID, nsAtom* aName, nsAtom* aPrefix,
});
}
+nsresult Element::SetAndSwapAttr(nsAtom* aLocalName, nsAttrValue& aValue,
+ bool* aHadValue) {
+ MOZ_TRY(mAttrs.SetAndSwapAttr(aLocalName, aValue, aHadValue));
+
+ if (aLocalName == nsGkAtoms::_class) {
+ UpdateSubtreeBloomFilterForClass(GetClasses());
+ }
+ UpdateSubtreeBloomFilterForAttribute(aLocalName);
+ PropagateBloomFilterToParents();
+
+ return NS_OK;
+}
+
+nsresult Element::SetAndSwapAttr(mozilla::dom::NodeInfo* aName,
+ nsAttrValue& aValue, bool* aHadValue) {
+ MOZ_TRY(mAttrs.SetAndSwapAttr(aName, aValue, aHadValue));
+
+ // Only update bloom filter for null-namespace attributes, since the
+ // querySelector bloom filter optimization only applies to those.
+ if (aName->NamespaceEquals(kNameSpaceID_None)) {
+ nsAtom* localName = aName->NameAtom();
+ if (localName == nsGkAtoms::_class) {
+ UpdateSubtreeBloomFilterForClass(GetClasses());
+ }
+ UpdateSubtreeBloomFilterForAttribute(localName);
+ PropagateBloomFilterToParents();
+ }
+
+ return NS_OK;
+}
+
nsresult Element::SetAttr(int32_t aNamespaceID, nsAtom* aName, nsAtom* aPrefix,
nsAtom* aValue, nsIPrincipal* aSubjectPrincipal,
bool aNotify) {
@@ -3015,7 +3191,7 @@ nsresult Element::SetAttrAndNotify(
hadDirAuto = HasDirAuto(); // already takes bdi into account
}
- MOZ_TRY(mAttrs.SetAndSwapAttr(aName, aParsedValue, &oldValueSet));
+ MOZ_TRY(SetAndSwapAttr(aName, aParsedValue, &oldValueSet));
if (IsAttributeMapped(aName) && !IsPendingMappedAttributeEvaluation()) {
mAttrs.InfallibleMarkAsPendingPresAttributeEvaluation();
if (Document* doc = GetComposedDoc()) {
@@ -3026,7 +3202,7 @@ nsresult Element::SetAttrAndNotify(
RefPtr<mozilla::dom::NodeInfo> ni =
mNodeInfo->NodeInfoManager()->GetNodeInfo(aName, aPrefix, aNamespaceID,
ATTRIBUTE_NODE);
- MOZ_TRY(mAttrs.SetAndSwapAttr(ni, aParsedValue, &oldValueSet));
+ MOZ_TRY(SetAndSwapAttr(ni, aParsedValue, &oldValueSet));
}
PostIdMaybeChange(aNamespaceID, aName, &valueForAfterSetAttr);
diff --git a/dom/base/Element.h b/dom/base/Element.h
@@ -1059,6 +1059,32 @@ class Element : public FragmentOrElement {
nsresult UnsetAttr(int32_t aNameSpaceID, nsAtom* aName, bool aNotify);
/**
+ * Swap an attribute value. This is a public wrapper that ensures bloom
+ * filter updates are performed correctly. For kNameSpaceID_None attributes,
+ * this will automatically update the bloom filter and propagate changes to
+ * parent elements.
+ *
+ * @param aLocalName the local name of the attribute
+ * @param aValue the value to swap (will contain old value on return)
+ * @param aHadValue set to true if attribute existed, false otherwise
+ */
+ nsresult SetAndSwapAttr(nsAtom* aLocalName, nsAttrValue& aValue,
+ bool* aHadValue);
+
+ /**
+ * Swap an attribute value. This is a public wrapper that ensures bloom
+ * filter updates are performed correctly. For kNameSpaceID_None attributes,
+ * this will automatically update the bloom filter and propagate changes to
+ * parent elements.
+ *
+ * @param aName the node info of the attribute
+ * @param aValue the value to swap (will contain old value on return)
+ * @param aHadValue set to true if attribute existed, false otherwise
+ */
+ nsresult SetAndSwapAttr(mozilla::dom::NodeInfo* aName, nsAttrValue& aValue,
+ bool* aHadValue);
+
+ /**
* Get the namespace / name / prefix of a given attribute.
*
* @param aIndex the index of the attribute name
@@ -2321,6 +2347,16 @@ class Element : public FragmentOrElement {
MOZ_CAN_RUN_SCRIPT
void FireBeforematchEvent(ErrorResult& aRv);
+ void PropagateBloomFilterToParents();
+ void UpdateSubtreeBloomFilterForClass(const nsAttrValue* aClassValue);
+ void UpdateSubtreeBloomFilterForAttribute(nsAtom* aAttribute);
+ uint64_t GetSubtreeBloomFilter() const {
+ return mAttrs.GetSubtreeBloomFilter();
+ }
+#ifdef DEBUG
+ void VerifySubtreeBloomFilter() const;
+#endif
+
protected:
enum class ReparseAttributes { No, Yes };
/**
diff --git a/dom/base/nsStyledElement.cpp b/dom/base/nsStyledElement.cpp
@@ -154,8 +154,7 @@ nsresult nsStyledElement::ReparseStyleAttribute(bool aForceInDataDoc) {
// Don't bother going through SetInlineStyleDeclaration; we don't
// want to fire off mutation events or document notifications anyway
bool oldValueSet;
- nsresult rv =
- mAttrs.SetAndSwapAttr(nsGkAtoms::style, attrValue, &oldValueSet);
+ nsresult rv = SetAndSwapAttr(nsGkAtoms::style, attrValue, &oldValueSet);
NS_ENSURE_SUCCESS(rv, rv);
}
diff --git a/dom/svg/SVGElement.cpp b/dom/svg/SVGElement.cpp
@@ -283,6 +283,11 @@ void SVGElement::DidAnimateClass() {
}
mClassAnimAttr->ParseAtomArray(src);
+ // Update bloom filter after mutating mClassAnimAttr.
+ UpdateSubtreeBloomFilterForClass(mClassAnimAttr.get());
+ UpdateSubtreeBloomFilterForAttribute(nsGkAtoms::_class);
+ PropagateBloomFilterToParents();
+
// FIXME(emilio): This re-selector-matches, but we do the snapshot stuff right
// above... Is this needed anymore?
if (presShell) {
diff --git a/dom/xul/nsXULElement.cpp b/dom/xul/nsXULElement.cpp
@@ -1047,11 +1047,9 @@ nsresult nsXULElement::MakeHeavyweight(nsXULPrototypeElement* aPrototype) {
bool oldValueSet;
// XXX we might wanna have a SetAndTakeAttr that takes an nsAttrName
if (protoattr->mName.IsAtom()) {
- rv = mAttrs.SetAndSwapAttr(protoattr->mName.Atom(), attrValue,
- &oldValueSet);
+ rv = SetAndSwapAttr(protoattr->mName.Atom(), attrValue, &oldValueSet);
} else {
- rv = mAttrs.SetAndSwapAttr(protoattr->mName.NodeInfo(), attrValue,
- &oldValueSet);
+ rv = SetAndSwapAttr(protoattr->mName.NodeInfo(), attrValue, &oldValueSet);
}
NS_ENSURE_SUCCESS(rv, rv);
}
diff --git a/servo/components/style/gecko/wrapper.rs b/servo/components/style/gecko/wrapper.rs
@@ -660,12 +660,22 @@ impl<'le> GeckoElement<'le> {
self.may_have_animations() && unsafe { Gecko_ElementHasAnimations(self.0) }
}
+ /// Check if mImpl contains a real pointer (not a bloom filter).
+ #[inline(always)]
+ fn has_attr_impl(&self) -> bool {
+ let ptr = self.0.mAttrs.mImpl.mPtr as usize;
+ ptr != 0 && (ptr & 1) == 0
+ }
+
#[inline(always)]
fn attrs(&self) -> &[structs::AttrArray_InternalAttr] {
unsafe {
+ if !self.has_attr_impl() {
+ return &[];
+ }
match self.0.mAttrs.mImpl.mPtr.as_ref() {
Some(attrs) => attrs.mBuffer.as_slice(attrs.mAttrCount as usize),
- None => return &[],
+ None => &[],
}
}
}
