blob: 1192d3b5f063f62c59fa64bf2c533594689544cc [file] [log] [blame]
// Copyright 2015 Google Inc. All Rights Reserved.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "base/basictypes.h"
#include "base/containers/small_map.h"
#include "base/hash_tables.h"
#include "base/memory/scoped_vector.h"
#include "base/memory/weak_ptr.h"
#include "cobalt/base/token.h"
#include "cobalt/cssom/combinator.h"
#include "cobalt/cssom/pseudo_class_type.h"
#include "cobalt/cssom/simple_selector_type.h"
#include "cobalt/cssom/specificity.h"
namespace cobalt {
namespace cssom {
class CompoundSelector;
class ComplexSelector;
class CSSStyleRule;
// A selector tree is a tree structure that organizes compound selectors. It is
// used to accelerate rule matching. More details can be found in the doc:
class SelectorTree {
typedef std::vector<base::WeakPtr<CSSStyleRule> > Rules;
class Node;
// This class can be used to store Nodes. It stores the Nodes in its
// internal buffer whose size can be configured via template parameter.
// After the internal buffer is used up the extra Nodes will be stored inside
// the contained std::vector.
// TODO: Move this off to its own file if this can also be used by
// other code.
template <size_t InternalCacheSize>
class NodeSet {
// Minimum interface for iterator.
class const_iterator {
const_iterator(const NodeSet* set, size_t index)
: set_(set), index_(index) {}
void operator++() { ++index_; }
const Node* operator*() const { return set_->GetNode(index_); }
bool operator!=(const const_iterator& that) const {
return set_ != that.set_ || index_ != that.index_;
const NodeSet* set_;
size_t index_;
NodeSet() : size_(0) {}
void insert(const Node* node, bool check_for_duplicate = false) {
// If |check_for_duplicate| is true, then check if the node is already
// contained. In nearly all cases, this check is unnecessary because it is
// already known that the node is not a duplicate. As a result, the caller
// must explicitly request the check when needed.
if (check_for_duplicate) {
for (size_t i = 0; i < size_; ++i) {
if (GetNode(i) == node) {
if (size_ < InternalCacheSize) {
nodes_[size_] = node;
} else {
template <class ConstIterator>
void insert(ConstIterator begin, ConstIterator end,
bool check_for_duplicate = false) {
while (begin != end) {
insert(*begin, check_for_duplicate);
const_iterator begin() const { return const_iterator(this, 0); }
const_iterator end() const { return const_iterator(this, size_); }
size_t size() const { return size_; }
void clear() {
size_ = 0;
const Node* GetNode(size_t index) const {
if (index < InternalCacheSize) {
return nodes_[index];
return nodes_vector_[index - InternalCacheSize];
size_t size_;
const Node* nodes_[InternalCacheSize];
std::vector<const Node*> nodes_vector_;
struct CompoundNodeLessThan {
bool operator()(const CompoundSelector* lhs,
const CompoundSelector* rhs) const;
// This class holds references to Nodes allocated on the heap that are owned
// by the same parent Node. It deletes all contained Nodes on destruction.
class OwnedNodes
: public base::SmallMap<
std::map<CompoundSelector*, Node*, CompoundNodeLessThan>, 2> {
~OwnedNodes() {
for (iterator iter = begin(); iter != end(); ++iter) {
delete iter->second;
struct PseudoClassNode {
PseudoClassType pseudo_class_type;
CombinatorType combinator_type;
Node* node;
struct SimpleSelectorNode {
SimpleSelectorType simple_selector_type;
CombinatorType combinator_type;
Node* node;
typedef std::vector<SimpleSelectorNode> SimpleSelectorNodes;
typedef std::vector<PseudoClassNode> PseudoClassNodes;
// The vast majority of SelectorTextToNodesMap objects have 4 or fewer
// selectors. However, they occasionally can number in the hundreds. Using
// a SmallMap with an array size of 4, allows both cases to be handled
// quickly.
typedef base::SmallMap<base::hash_map<base::Token, SimpleSelectorNodes>, 4>
class Node {
CompoundSelector* compound_selector() const { return compound_selector_; }
Specificity cumulative_specificity() const {
return cumulative_specificity_;
bool HasCombinator(CombinatorType type) const {
return (combinator_mask_ & (1 << type)) != 0;
Rules& rules() { return rules_; }
const Rules& rules() const { return rules_; }
const PseudoClassNodes& pseudo_class_nodes() const {
return pseudo_class_nodes_;
bool HasAnyPseudoClass() const { return pseudo_class_mask_ != 0; }
bool HasPseudoClass(PseudoClassType pseudo_class_type,
CombinatorType combinator_type) const {
return (pseudo_class_mask_ &
(1u << (pseudo_class_type * kCombinatorCount +
combinator_type))) != 0;
void AppendPseudoClassNode(PseudoClassType pseudo_class_type,
CombinatorType combinator_type, Node* node) {
PseudoClassNode child_node = {pseudo_class_type, combinator_type, node};
pseudo_class_mask_ |=
(1u << (pseudo_class_type * kCombinatorCount + combinator_type));
const SelectorTextToNodesMap* selector_nodes_map() const {
return selector_nodes_map_.get();
bool HasSimpleSelector(SimpleSelectorType simple_selector_type,
CombinatorType combinator_type) const {
return (selector_mask_ & (1u << (simple_selector_type * kCombinatorCount +
combinator_type))) != 0;
void AppendSimpleSelector(base::Token name,
SimpleSelectorType simple_selector_type,
CombinatorType combinator_type, Node* node) {
// Create the SelectorTextToNodesMap if this is the first simple selector
// being appended.
if (!selector_nodes_map_) {
selector_nodes_map_.reset(new SelectorTextToNodesMap());
SimpleSelectorNode child_node = {simple_selector_type, combinator_type,
selector_mask_ |=
(1u << (simple_selector_type * kCombinatorCount + combinator_type));
friend class SelectorTree;
Node(CompoundSelector* compound_selector, Specificity parent_specificity);
// Bit mask used to quickly reject a certain combinator type.
uint8 combinator_mask_;
COMPILE_ASSERT(sizeof(uint8) * 8 >= kCombinatorCount,
// Pointer to one of the equivalent compound selectors.
CompoundSelector* compound_selector_;
// Sum of specificity from root to this node.
Specificity cumulative_specificity_;
// Indexes for the children. This is a scoped_ptr because the majority of
// nodes do not contain any children.
scoped_ptr<SelectorTextToNodesMap> selector_nodes_map_;
// Bit mask used to quickly reject a certain selector type and combinator
// combination.
uint32 selector_mask_;
COMPILE_ASSERT(sizeof(uint32) * 8 >=
kSimpleSelectorTypeCount * kCombinatorCount,
PseudoClassNodes pseudo_class_nodes_;
// Bit mask used to quickly reject a certain pseudo class and combinator
// combination.
uint32 pseudo_class_mask_;
COMPILE_ASSERT(sizeof(uint32) * 8 >=
kPseudoClassTypeCount * kCombinatorCount,
// Rules that end with this node.
Rules rules_;
SelectorTree() : has_sibling_combinators_(false) { root_set_.insert(&root_); }
const Node* root() const { return &root_; }
const NodeSet<1>& root_set() const { return root_set_; }
bool has_sibling_combinators() const { return has_sibling_combinators_; }
void AppendRule(CSSStyleRule* rule);
void RemoveRule(CSSStyleRule* rule);
// Used by unit tests only.
const OwnedNodes& children(const Node* node, CombinatorType combinator);
// Gets or creates node for complex selector, starting from root.
Node* GetOrCreateNodeForComplexSelector(ComplexSelector* selector);
// Gets or creates node for compound selector, starting from given node, using
// given combiantor as edge.
Node* GetOrCreateNodeForCompoundSelector(CompoundSelector* compound_selector,
Node* parent_node,
CombinatorType combinator);
Node root_;
NodeSet<1> root_set_;
// This variable maps from a parent Node and a combinator type to child Nodes
// under the particular parent Node corresponding to the particular combinator
// type. It is only used when modifying the SelectorTree and is not used
// during rule matching. So we store it externally to the Node to minimize
// the size of Node structure.
std::map<std::pair<const Node*, CombinatorType>, OwnedNodes> owned_nodes_map_;
bool has_sibling_combinators_;
} // namespace cssom
} // namespace cobalt