src/cobalt/cssom/selector_tree.h - cobalt - Git at Google

 // 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
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #ifndef COBALT_CSSOM_SELECTOR_TREE_H_
 #define COBALT_CSSOM_SELECTOR_TREE_H_

 #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:
 // https://docs.google.com/document/d/1LTbSenGsGR94JTGg6DfZDXYB3MBBCp4C8dRC4rckt_8/
 class SelectorTree {
  public:
   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 {
    public:
     // Minimum interface for iterator.
     class const_iterator {
      public:
       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_;
       }

      private:
       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) {
             return;
           }
         }
       }

       if (size_ < InternalCacheSize) {
         nodes_[size_] = node;
       } else {
         nodes_vector_.push_back(node);
       }
       ++size_;
     }
     template <class ConstIterator>
     void insert(ConstIterator begin, ConstIterator end,
                 bool check_for_duplicate = false) {
       while (begin != end) {
         insert(*begin, check_for_duplicate);
         ++begin;
       }
     }

     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;
       nodes_vector_.clear();
     }
     const Node* GetNode(size_t index) const {
       if (index < InternalCacheSize) {
         return nodes_[index];
       }
       return nodes_vector_[index - InternalCacheSize];
     }

    private:
     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> {
    public:
     ~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>
       SelectorTextToNodesMap;

   class Node {
    public:
     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_nodes_.push_back(child_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,
                                        node};
       (*selector_nodes_map_)[name].push_back(child_node);
       selector_mask_ |=
           (1u << (simple_selector_type * kCombinatorCount + combinator_type));
     }

    private:
     friend class SelectorTree;

     Node();
     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,
                    combinator_mask_does_not_have_enough_bits);

     // 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,
                    selector_mask_does_not_have_enough_bits);
     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,
                    pseudo_class_mask_does_not_have_enough_bits);

     // 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);

  private:
   // 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_;

   DISALLOW_COPY_AND_ASSIGN(SelectorTree);
 };

 }  // namespace cssom
 }  // namespace cobalt

 #endif  // COBALT_CSSOM_SELECTOR_TREE_H_
	// 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
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#ifndef COBALT_CSSOM_SELECTOR_TREE_H_
	#define COBALT_CSSOM_SELECTOR_TREE_H_

	#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:
	// https://docs.google.com/document/d/1LTbSenGsGR94JTGg6DfZDXYB3MBBCp4C8dRC4rckt_8/
	class SelectorTree {
	public:
	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 {
	public:
	// Minimum interface for iterator.
	class const_iterator {
	public:
	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_;
	}

	private:
	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) {
	return;
	}
	}
	}

	if (size_ < InternalCacheSize) {
	nodes_[size_] = node;
	} else {
	nodes_vector_.push_back(node);
	}
	++size_;
	}
	template <class ConstIterator>
	void insert(ConstIterator begin, ConstIterator end,
	bool check_for_duplicate = false) {
	while (begin != end) {
	insert(*begin, check_for_duplicate);
	++begin;
	}
	}

	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;
	nodes_vector_.clear();
	}
	const Node* GetNode(size_t index) const {
	if (index < InternalCacheSize) {
	return nodes_[index];
	}
	return nodes_vector_[index - InternalCacheSize];
	}

	private:
	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> {
	public:
	~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>
	SelectorTextToNodesMap;

	class Node {
	public:
	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_nodes_.push_back(child_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,
	node};
	(*selector_nodes_map_)[name].push_back(child_node);
	selector_mask_ \|=
	(1u << (simple_selector_type * kCombinatorCount + combinator_type));
	}

	private:
	friend class SelectorTree;

	Node();
	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,
	combinator_mask_does_not_have_enough_bits);

	// 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,
	selector_mask_does_not_have_enough_bits);
	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,
	pseudo_class_mask_does_not_have_enough_bits);

	// 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);

	private:
	// 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_;

	DISALLOW_COPY_AND_ASSIGN(SelectorTree);
	};

	} // namespace cssom
	} // namespace cobalt

	#endif // COBALT_CSSOM_SELECTOR_TREE_H_