| /* |
| * Copyright (C) 2008, 2012 Apple Inc. All rights reserved. |
| * Copyright (C) 2009 Google Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "third_party/blink/renderer/core/css/css_selector_list.h" |
| |
| #include <memory> |
| #include <vector> |
| #include "third_party/blink/renderer/core/css/parser/css_parser_selector.h" |
| #include "third_party/blink/renderer/platform/runtime_enabled_features.h" |
| #include "third_party/blink/renderer/platform/wtf/allocator/partitions.h" |
| #include "third_party/blink/renderer/platform/wtf/text/string_builder.h" |
| |
| namespace { |
| // CSSSelector is one of the top types that consume renderer memory, |
| // so instead of using the |WTF_HEAP_PROFILER_TYPE_NAME| macro in the |
| // allocations below, pass this type name constant to allow profiling |
| // in official builds. |
| const char kCSSSelectorTypeName[] = "blink::CSSSelector"; |
| } |
| |
| namespace blink { |
| |
| CSSSelectorList CSSSelectorList::Copy() const { |
| CSSSelectorList list; |
| |
| unsigned length = this->ComputeLength(); |
| list.selector_array_ = |
| reinterpret_cast<CSSSelector*>(WTF::Partitions::FastMalloc( |
| WTF::Partitions::ComputeAllocationSize(length, sizeof(CSSSelector)), |
| kCSSSelectorTypeName)); |
| for (unsigned i = 0; i < length; ++i) |
| new (&list.selector_array_[i]) CSSSelector(selector_array_[i]); |
| |
| return list; |
| } |
| |
| CSSSelectorList CSSSelectorList::ConcatenateListExpansion( |
| const CSSSelectorList& expanded, |
| const CSSSelectorList& original) { |
| unsigned expanded_length = expanded.ComputeLength(); |
| unsigned original_length = original.ComputeLength(); |
| unsigned total_length = expanded_length + original_length; |
| |
| CSSSelectorList list; |
| list.selector_array_ = reinterpret_cast<CSSSelector*>( |
| WTF::Partitions::FastMalloc(WTF::Partitions::ComputeAllocationSize( |
| total_length, sizeof(CSSSelector)), |
| kCSSSelectorTypeName)); |
| |
| unsigned list_index = 0; |
| for (unsigned i = 0; i < expanded_length; ++i) { |
| new (&list.selector_array_[list_index]) |
| CSSSelector(expanded.selector_array_[i]); |
| ++list_index; |
| } |
| DCHECK(list.selector_array_[list_index - 1].IsLastInOriginalList()); |
| DCHECK(list.selector_array_[list_index - 1].IsLastInSelectorList()); |
| list.selector_array_[list_index - 1].SetLastInSelectorList(false); |
| for (unsigned i = 0; i < original_length; ++i) { |
| new (&list.selector_array_[list_index]) |
| CSSSelector(original.selector_array_[i]); |
| ++list_index; |
| } |
| DCHECK(list.selector_array_[list_index - 1].IsLastInOriginalList()); |
| DCHECK(list.selector_array_[list_index - 1].IsLastInSelectorList()); |
| return list; |
| } |
| |
| std::vector<const CSSSelector*> SelectorBoundaries( |
| const CSSSelectorList& list) { |
| std::vector<const CSSSelector*> result; |
| for (const CSSSelector* s = list.First(); s; s = list.Next(*s)) { |
| result.push_back(s); |
| } |
| result.push_back(list.First() + list.ComputeLength()); |
| return result; |
| } |
| |
| void AddToList(CSSSelector*& destination, |
| const CSSSelector* begin, |
| const CSSSelector* end) { |
| for (const CSSSelector* current = begin; current != end; ++current) { |
| new (destination) CSSSelector(*current); |
| destination->SetLastInSelectorList(false); |
| destination->SetLastInOriginalList(false); |
| destination++; |
| } |
| } |
| |
| void AddToList(CSSSelector*& destination, |
| const CSSSelector* begin, |
| const CSSSelector* end, |
| const CSSSelector* selector_to_expand) { |
| for (const CSSSelector* current = begin; current != end; ++current) { |
| new (destination) CSSSelector(*current); |
| DCHECK_EQ(current + 1 == end, current->IsLastInTagHistory()); |
| if (current->IsLastInTagHistory()) { |
| destination->SetRelation(selector_to_expand->Relation()); |
| if (!selector_to_expand->IsLastInTagHistory()) |
| destination->SetLastInTagHistory(false); |
| } |
| if (selector_to_expand->GetPseudoType() == CSSSelector::kPseudoWhere || |
| selector_to_expand->IgnoreSpecificity()) |
| destination->SetIgnoreSpecificity(true); |
| destination->SetLastInSelectorList(false); |
| destination->SetLastInOriginalList(false); |
| destination++; |
| } |
| } |
| |
| CSSSelectorList CSSSelectorList::ExpandedFirstPseudoClass() const { |
| DCHECK(this->RequiresExpansion()); |
| unsigned original_length = this->ComputeLength(); |
| std::vector<const CSSSelector*> selector_boundaries = |
| SelectorBoundaries(*this); |
| |
| size_t i = 0; |
| CSSSelectorList transformed = this->Copy(); |
| while (!selector_boundaries[i]->HasPseudoIs() && |
| !selector_boundaries[i]->HasPseudoWhere()) |
| ++i; |
| |
| const CSSSelector* selector_to_expand_begin = selector_boundaries[i]; |
| const CSSSelector* selector_to_expand_end = selector_boundaries[i + 1]; |
| unsigned selector_to_expand_length = |
| static_cast<unsigned>(selector_to_expand_end - selector_to_expand_begin); |
| |
| const CSSSelector* simple_selector = selector_to_expand_begin; |
| while (simple_selector->GetPseudoType() != CSSSelector::kPseudoIs && |
| simple_selector->GetPseudoType() != CSSSelector::kPseudoWhere) { |
| simple_selector = simple_selector->TagHistory(); |
| } |
| |
| unsigned inner_selector_length = |
| simple_selector->SelectorList()->ComputeLength(); |
| std::vector<const CSSSelector*> selector_arg_boundaries = |
| SelectorBoundaries(*simple_selector->SelectorList()); |
| |
| wtf_size_t num_args = |
| SafeCast<wtf_size_t>(selector_arg_boundaries.size()) - 1; |
| unsigned other_selectors_length = original_length - selector_to_expand_length; |
| |
| wtf_size_t expanded_selector_list_length = |
| (selector_to_expand_length - 1) * num_args + inner_selector_length + |
| other_selectors_length; |
| |
| // Do not perform expansion if the selector list size is too large to create |
| // RuleData |
| if (expanded_selector_list_length > 8192) |
| return CSSSelectorList(); |
| |
| CSSSelectorList list; |
| list.selector_array_ = |
| reinterpret_cast<CSSSelector*>(WTF::Partitions::FastMalloc( |
| WTF::Partitions::ComputeAllocationSize(expanded_selector_list_length, |
| sizeof(CSSSelector)), |
| kCSSSelectorTypeName)); |
| |
| CSSSelector* destination = list.selector_array_; |
| |
| AddToList(destination, selector_boundaries[0], selector_to_expand_begin); |
| for (wtf_size_t i = 0; i < num_args; ++i) { |
| AddToList(destination, selector_to_expand_begin, simple_selector); |
| AddToList(destination, selector_arg_boundaries[i], |
| selector_arg_boundaries[i + 1], simple_selector); |
| AddToList(destination, simple_selector + 1, selector_to_expand_end); |
| } |
| AddToList(destination, selector_to_expand_end, selector_boundaries.back()); |
| |
| DCHECK(destination == list.selector_array_ + expanded_selector_list_length); |
| |
| list.selector_array_[expanded_selector_list_length - 1].SetLastInOriginalList( |
| true); |
| list.selector_array_[expanded_selector_list_length - 1].SetLastInSelectorList( |
| true); |
| |
| return list; |
| } |
| |
| CSSSelectorList CSSSelectorList::TransformForListExpansion() { |
| DCHECK_GT(this->ComputeLength(), 0u); |
| DCHECK( |
| this->selector_array_[this->ComputeLength() - 1].IsLastInOriginalList()); |
| DCHECK(this->RequiresExpansion()); |
| |
| // Append the expanded form of matches to the original selector list |
| CSSSelectorList transformed = this->Copy(); |
| do { |
| transformed = transformed.ExpandedFirstPseudoClass(); |
| } while (transformed.RequiresExpansion()); |
| |
| if (transformed.ComputeLength() == 0) |
| return CSSSelectorList(); |
| return CSSSelectorList::ConcatenateListExpansion(transformed, *this); |
| } |
| |
| bool CSSSelectorList::HasPseudoIs() const { |
| for (const CSSSelector* s = FirstForCSSOM(); s; s = Next(*s)) { |
| if (s->HasPseudoIs()) |
| return true; |
| } |
| return false; |
| } |
| |
| bool CSSSelectorList::HasPseudoWhere() const { |
| for (const CSSSelector* s = FirstForCSSOM(); s; s = Next(*s)) { |
| if (s->HasPseudoWhere()) |
| return true; |
| } |
| return false; |
| } |
| |
| bool CSSSelectorList::RequiresExpansion() const { |
| for (const CSSSelector* s = FirstForCSSOM(); s; s = Next(*s)) { |
| if (s->HasPseudoIs() || s->HasPseudoWhere()) |
| return true; |
| } |
| return false; |
| } |
| |
| CSSSelectorList CSSSelectorList::AdoptSelectorVector( |
| Vector<std::unique_ptr<CSSParserSelector>>& selector_vector) { |
| size_t flattened_size = 0; |
| for (wtf_size_t i = 0; i < selector_vector.size(); ++i) { |
| for (CSSParserSelector* selector = selector_vector[i].get(); selector; |
| selector = selector->TagHistory()) |
| ++flattened_size; |
| } |
| DCHECK(flattened_size); |
| |
| CSSSelectorList list; |
| list.selector_array_ = reinterpret_cast<CSSSelector*>( |
| WTF::Partitions::FastMalloc(WTF::Partitions::ComputeAllocationSize( |
| flattened_size, sizeof(CSSSelector)), |
| kCSSSelectorTypeName)); |
| wtf_size_t array_index = 0; |
| for (wtf_size_t i = 0; i < selector_vector.size(); ++i) { |
| CSSParserSelector* current = selector_vector[i].get(); |
| while (current) { |
| // Move item from the parser selector vector into selector_array_ without |
| // invoking destructor (Ugh.) |
| CSSSelector* current_selector = current->ReleaseSelector().release(); |
| memcpy(&list.selector_array_[array_index], current_selector, |
| sizeof(CSSSelector)); |
| WTF::Partitions::FastFree(current_selector); |
| |
| current = current->TagHistory(); |
| DCHECK(!list.selector_array_[array_index].IsLastInSelectorList()); |
| if (current) |
| list.selector_array_[array_index].SetLastInTagHistory(false); |
| ++array_index; |
| } |
| DCHECK(list.selector_array_[array_index - 1].IsLastInTagHistory()); |
| } |
| DCHECK_EQ(flattened_size, array_index); |
| list.selector_array_[array_index - 1].SetLastInSelectorList(true); |
| list.selector_array_[array_index - 1].SetLastInOriginalList(true); |
| selector_vector.clear(); |
| |
| return list; |
| } |
| |
| const CSSSelector* CSSSelectorList::FirstForCSSOM() const { |
| const CSSSelector* s = this->First(); |
| if (!s) |
| return nullptr; |
| while (this->Next(*s)) |
| s = this->Next(*s); |
| if (this->NextInFullList(*s)) |
| return this->NextInFullList(*s); |
| return this->First(); |
| } |
| |
| unsigned CSSSelectorList::ComputeLength() const { |
| if (!selector_array_) |
| return 0; |
| CSSSelector* current = selector_array_; |
| while (!current->IsLastInSelectorList()) |
| ++current; |
| return static_cast<unsigned>(current - selector_array_) + 1; |
| } |
| |
| void CSSSelectorList::DeleteSelectors() { |
| DCHECK(selector_array_); |
| |
| bool finished = false; |
| for (CSSSelector* s = selector_array_; !finished; ++s) { |
| finished = s->IsLastInSelectorList(); |
| s->~CSSSelector(); |
| } |
| |
| WTF::Partitions::FastFree(selector_array_); |
| } |
| |
| String CSSSelectorList::SelectorsText() const { |
| StringBuilder result; |
| |
| for (const CSSSelector* s = FirstForCSSOM(); s; s = Next(*s)) { |
| if (s != FirstForCSSOM()) |
| result.Append(", "); |
| result.Append(s->SelectorText()); |
| } |
| |
| return result.ToString(); |
| } |
| |
| } // namespace blink |