UrlPatternIndex: Introduce ElementType and ActivationType enums to url_pattern_index schema.

components/url_pattern_index/url_pattern_index.cc

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/url_pattern_index/url_pattern_index.h"
 
 #include <algorithm>
 #include <limits>
+#include <map>
 #include <string>
 
 #include "base/logging.h"
 #include "base/numerics/safe_conversions.h"
+#include "base/stl_util.h"
 #include "base/strings/string_piece.h"
 #include "base/strings/string_util.h"
 #include "components/url_pattern_index/ngram_extractor.h"
 #include "components/url_pattern_index/url_pattern.h"
 #include "url/gurl.h"
 #include "url/origin.h"
 
 namespace url_pattern_index {
 
 namespace {
 
 using FlatStringOffset = flatbuffers::Offset<flatbuffers::String>;
 using FlatDomains = flatbuffers::Vector<FlatStringOffset>;
 using FlatDomainsOffset = flatbuffers::Offset<FlatDomains>;
 
+// Maps proto::ActivationType to flat::ActivationType.
+const std::map<proto::ActivationType, flat::ActivationType> kActivationTypeMap =

[pkalinnikov, 2017/06/28 15:59:43]

For performance reasons (queries should be fast), can you please replace these
maps by one of the following?
 - Just switch-case clauses in the below functions, remove #includes. Iterating
through all proto::ElementTypes is doable by looping an int from OTHER to MAX.
The DCHECK_IS_ON checks would become redundant because ProtoToFlat*Type called
from these loops would do the thing.
 - I bet "base/containers/flat_map.h" should be more compact and fast than
std::map for such a use-case.

Once the proto-specific code is detached and moved back to subresource_filter,
this mapping will no longer be needed in queries, since flat::ElementType can be
used directly. A list of pairs will still be needed to convert from proto wire
format to FlatBuffers.

Alternative idea. Could url_pattern_index be agnostic to the types? It could
assume that they are a bitmask (as currently), without knowing which bits
correspond to which types. In this case there would be no need in conversion.
Subresource filter and DNR could use independent typing systems. E.g., DNR could
use WebRequestResourceType. Additional benefit is the ability to get rid of the
notion of element type and activation type in UrlPatternIndex, and simply speak
about "types".

[karandeepb, 2017/06/29 00:58:18]

I preferred to use a flat map, since I think it leads to cleaner code.
Correct.
I prefer the current form. url_pattern_index is meant to match Url rules, and
hence it isn't incorrect for it to know about resource types. Also, the same
argument can be used for OptionFlag. For url_pattern_index to support a generic
bitmask w/o knowing anything about it, seems weird to me. For e.g., how do we
know how many bits to support etc.

[pkalinnikov, 2017/06/29 09:19:16]

Acknowledged.

+    {
+        {proto::ACTIVATION_TYPE_UNSPECIFIED, flat::ActivationType_NONE},
+        {proto::ACTIVATION_TYPE_DOCUMENT, flat::ActivationType_DOCUMENT},
+        // ELEMHIDE is not supported.
+        {proto::ACTIVATION_TYPE_ELEMHIDE, flat::ActivationType_NONE},
+        // GENERICHIDE is not supported.
+        {proto::ACTIVATION_TYPE_GENERICHIDE, flat::ActivationType_NONE},
+        {proto::ACTIVATION_TYPE_GENERICBLOCK,
+         flat::ActivationType_GENERIC_BLOCK},
+};
+
+// Maps proto::ElementType to flat::ElementType.
+const std::map<proto::ElementType, flat::ElementType> kElementTypeMap = {
+    {proto::ELEMENT_TYPE_UNSPECIFIED, flat::ElementType_NONE},
+    {proto::ELEMENT_TYPE_OTHER, flat::ElementType_OTHER},
+    {proto::ELEMENT_TYPE_SCRIPT, flat::ElementType_SCRIPT},
+    {proto::ELEMENT_TYPE_IMAGE, flat::ElementType_IMAGE},
+    {proto::ELEMENT_TYPE_STYLESHEET, flat::ElementType_STYLESHEET},
+    {proto::ELEMENT_TYPE_OBJECT, flat::ElementType_OBJECT},
+    {proto::ELEMENT_TYPE_XMLHTTPREQUEST, flat::ElementType_XMLHTTPREQUEST},
+    {proto::ELEMENT_TYPE_OBJECT_SUBREQUEST,
+     flat::ElementType_OBJECT_SUBREQUEST},
+    {proto::ELEMENT_TYPE_SUBDOCUMENT, flat::ElementType_SUBDOCUMENT},
+    {proto::ELEMENT_TYPE_PING, flat::ElementType_PING},
+    {proto::ELEMENT_TYPE_MEDIA, flat::ElementType_MEDIA},
+    {proto::ELEMENT_TYPE_FONT, flat::ElementType_FONT},
+    // Filterning popups is not supported.
+    {proto::ELEMENT_TYPE_POPUP, flat::ElementType_NONE},
+    {proto::ELEMENT_TYPE_WEBSOCKET, flat::ElementType_WEBSOCKET},
+};
+
+flat::ActivationType ProtoToFlatActivationType(proto::ActivationType type) {
+  DCHECK(base::ContainsKey(kActivationTypeMap, type));
+  return kActivationTypeMap.at(type);
+}
+
+flat::ElementType ProtoToFlatElementType(proto::ElementType type) {
+  DCHECK(base::ContainsKey(kElementTypeMap, type));
+  return kElementTypeMap.at(type);
+}
+
 base::StringPiece ToStringPiece(const flatbuffers::String* string) {
   DCHECK(string);
   return base::StringPiece(string->c_str(), string->size());
 }
 
 // Performs three-way comparison between two domains. In the total order defined
 // by this predicate, the lengths of domains will be monotonically decreasing.
 int CompareDomains(base::StringPiece lhs_domain, base::StringPiece rhs_domain) {
   if (lhs_domain.size() != rhs_domain.size())
     return lhs_domain.size() > rhs_domain.size() ? -1 : 1;
@@ skipping 97 matching lines @@
       case proto::ANCHOR_TYPE_SUBDOMAIN:
         *result = flat::AnchorType_SUBDOMAIN;
         break;
       default:
         return false;  // Unsupported anchor type.
     }
     return true;
   }
 
   bool InitializeOptions() {
+    static_assert(flat::OptionFlag_ANY <= std::numeric_limits<uint8_t>::max(),
+                  "Option flags can not be stored in uint8_t.");
+
     if (rule_.semantics() == proto::RULE_SEMANTICS_WHITELIST) {
       options_ |= flat::OptionFlag_IS_WHITELIST;
     } else if (rule_.semantics() != proto::RULE_SEMANTICS_BLACKLIST) {
       return false;  // Unsupported semantics.
     }
 
     switch (rule_.source_type()) {
       case proto::SOURCE_TYPE_ANY:
         options_ |= flat::OptionFlag_APPLIES_TO_THIRD_PARTY;
       // Note: fall through here intentionally.
       case proto::SOURCE_TYPE_FIRST_PARTY:
         options_ |= flat::OptionFlag_APPLIES_TO_FIRST_PARTY;
         break;
       case proto::SOURCE_TYPE_THIRD_PARTY:
         options_ |= flat::OptionFlag_APPLIES_TO_THIRD_PARTY;
         break;
 
       default:
         return false;  // Unsupported source type.
     }
 
     if (rule_.match_case())
       options_ |= flat::OptionFlag_IS_MATCH_CASE;
 
     return true;
   }
 
   bool InitializeElementTypes() {
-    static_assert(
-        proto::ELEMENT_TYPE_ALL <= std::numeric_limits<uint16_t>::max(),
-        "Element types can not be stored in uint16_t.");
-    element_types_ = static_cast<uint16_t>(rule_.element_types());
+    static_assert(flat::ElementType_ANY <= std::numeric_limits<uint16_t>::max(),
+                  "Element types can not be stored in uint16_t.");
 
-    // Note: Normally we can not distinguish between the main plugin resource
-    // and any other loads it makes. We treat them both as OBJECT requests.
-    if (element_types_ & proto::ELEMENT_TYPE_OBJECT_SUBREQUEST)
-      element_types_ |= proto::ELEMENT_TYPE_OBJECT;
+// Ensure all proto::ElementType(s) are mapped in |kElementTypeMap|.
+#if DCHECK_IS_ON()
+    uint16_t mask = 0;

[pkalinnikov, 2017/06/28 15:59:43]

nit: Can you make it int? Same below for ActivationType.

[karandeepb, 2017/06/29 00:58:18]

Isn't this better being a more concrete type? |element_types_| also uses
uint16_t.

[pkalinnikov, 2017/06/29 09:19:16]

I agree that *current* proto::ElementType values fit into uint16_t. However, the
type of |pair.first| below, which is an enum, is only <= int (not specified
further by the standard). The static_assert above doesn't check
proto::ElementType boundary, so you can either add another static_cast for that,
or (which is shorter) just use int in this line.

+    for (const auto& pair : kElementTypeMap)
+      mask |= pair.first;
+    DCHECK_EQ(proto::ELEMENT_TYPE_ALL, mask);
+#endif  // DCHECK_IS_ON()
 
-    // Ignore unknown element types.
-    element_types_ &= proto::ELEMENT_TYPE_ALL;
-    // Filtering popups is not supported.
-    element_types_ &= ~proto::ELEMENT_TYPE_POPUP;
+    element_types_ = flat::ElementType_NONE;
+
+    for (const auto& pair : kElementTypeMap)
+      if (rule_.element_types() & pair.first)
+        element_types_ |= pair.second;
+
+    // Normally we can not distinguish between the main plugin resource and any
+    // other loads it makes. We treat them both as OBJECT requests. Hence an
+    // OBJECT request would also match OBJECT_SUBREQUEST rules, but not the
+    // the other way round.
+    if (element_types_ & flat::ElementType_OBJECT_SUBREQUEST)

[pkalinnikov, 2017/06/28 15:59:42]

Should we consider merging the 2 types together? Subresource Filter never uses
OBJECT_SUBREQUEST for queries (see ToElementType in
"web_document_subresource_filter_impl.cc"), i.e., "the other way round" never
happens, thus the 2 types are effectively equivalent.

[karandeepb, 2017/06/29 00:58:18]

Yeah I thought of that as well. We can add DCHECKs to FindMatch to ensure it is
not queried with POPUP and OBJECT_SUBREQUEST types.
However since FindMatch takes in a proto::ElementType currently, I think it is
better to support all types for now. Once, proto code is moved back to
subresource filter and we only support flat:: types, we can remove
OBJECT_SUBREQUEST. Added a TODO to that effect.

[pkalinnikov, 2017/06/29 09:19:16]

Acknowledged.

+      element_types_ |= flat::ElementType_OBJECT;
 
     return true;
   }
 
   bool InitializeActivationTypes() {
     static_assert(
-        proto::ACTIVATION_TYPE_ALL <= std::numeric_limits<uint8_t>::max(),
+        flat::ActivationType_ANY <= std::numeric_limits<uint8_t>::max(),
         "Activation types can not be stored in uint8_t.");
-    activation_types_ = static_cast<uint8_t>(rule_.activation_types());
 
-    // Only the following activation types are supported, ignore the others.
-    activation_types_ &=
-        proto::ACTIVATION_TYPE_DOCUMENT | proto::ACTIVATION_TYPE_GENERICBLOCK;
+// Ensure all proto::ActivationType(s) are mapped in |kActivationTypeMap|.
+#if DCHECK_IS_ON()
+    uint16_t mask = 0;
+    for (const auto& pair : kActivationTypeMap)
+      mask |= pair.first;
+    DCHECK_EQ(proto::ACTIVATION_TYPE_ALL, mask);
+#endif  // DCHECK_IS_ON()
+
+    activation_types_ = flat::ActivationType_NONE;
+
+    for (const auto& pair : kActivationTypeMap)
+      if (rule_.activation_types() & pair.first)
+        activation_types_ |= pair.second;
 
     return true;
   }
 
   bool InitializeUrlPattern() {
     switch (rule_.url_pattern_type()) {
       case proto::URL_PATTERN_TYPE_SUBSTRING:
         url_pattern_type_ = flat::UrlPatternType_SUBSTRING;
         break;
       case proto::URL_PATTERN_TYPE_WILDCARDED:
@@ skipping 213 matching lines @@
   }
   if (longest_matching_included_domain_length && rule.domains_excluded()) {
     return GetLongestMatchingSubdomain(origin, *rule.domains_excluded()) <
            longest_matching_included_domain_length;
   }
   return !!longest_matching_included_domain_length;
 }
 
 // Returns whether the request matches flags of the specified URL |rule|. Takes
 // into account:
-//  - |element_type| of the requested resource, if not *_UNSPECIFIED.
-//  - |activation_type| for a subdocument request, if not *_UNSPECIFIED.
+//  - |element_type| of the requested resource, if not *_NONE.
+//  - |activation_type| for a subdocument request, if not *_NONE.
 //  - Whether the resource |is_third_party| w.r.t. its embedding document.
 bool DoesRuleFlagsMatch(const flat::UrlRule& rule,
-                        proto::ElementType element_type,
-                        proto::ActivationType activation_type,
+                        flat::ElementType element_type,
+                        flat::ActivationType activation_type,
                         bool is_third_party) {
-  DCHECK((element_type == proto::ELEMENT_TYPE_UNSPECIFIED) !=
-         (activation_type == proto::ACTIVATION_TYPE_UNSPECIFIED));
+  DCHECK((element_type == flat::ElementType_NONE) !=
+         (activation_type == flat::ActivationType_NONE));
 
-  if (element_type != proto::ELEMENT_TYPE_UNSPECIFIED &&
+  if (element_type != flat::ElementType_NONE &&
       !(rule.element_types() & element_type)) {
     return false;
   }
-  if (activation_type != proto::ACTIVATION_TYPE_UNSPECIFIED &&
+  if (activation_type != flat::ActivationType_NONE &&
       !(rule.activation_types() & activation_type)) {
     return false;
   }
 
   if (is_third_party &&
       !(rule.options() & flat::OptionFlag_APPLIES_TO_THIRD_PARTY)) {
     return false;
   }
   if (!is_third_party &&
       !(rule.options() & flat::OptionFlag_APPLIES_TO_FIRST_PARTY)) {
     return false;
   }
 
   return true;
 }
 
 const flat::UrlRule* FindMatchAmongCandidates(
     const FlatUrlRuleList* candidates,
     const GURL& url,
     const url::Origin& document_origin,
-    proto::ElementType element_type,
-    proto::ActivationType activation_type,
+    flat::ElementType element_type,
+    flat::ActivationType activation_type,
     bool is_third_party,
     bool disable_generic_rules) {
   if (!candidates)
     return nullptr;
   for (const flat::UrlRule* rule : *candidates) {
     DCHECK_NE(rule, nullptr);
     DCHECK_NE(rule->url_pattern_type(), flat::UrlPatternType_REGEXP);
     if (!DoesRuleFlagsMatch(*rule, element_type, activation_type,
                             is_third_party)) {
       continue;
@@ skipping 10 matching lines @@
   return nullptr;
 }
 
 // Returns whether the network request matches a UrlPattern |index| represented
 // in its FlatBuffers format. |is_third_party| should reflect the relation
 // between |url| and |document_origin|.
 const flat::UrlRule* FindMatchInFlatUrlPatternIndex(
     const flat::UrlPatternIndex& index,
     const GURL& url,
     const url::Origin& document_origin,
-    proto::ElementType element_type,
-    proto::ActivationType activation_type,
+    flat::ElementType element_type,
+    flat::ActivationType activation_type,
     bool is_third_party,
     bool disable_generic_rules) {
   const FlatNGramIndex* hash_table = index.ngram_index();
   const flat::NGramToRules* empty_slot = index.ngram_index_empty_slot();
   DCHECK_NE(hash_table, nullptr);
 
   NGramHashTableProber prober;
 
   auto ngrams = CreateNGramExtractor<kNGramSize, uint64_t>(
       url.spec(), [](char) { return false; });
@@ skipping 33 matching lines @@
 
 UrlPatternIndexMatcher::~UrlPatternIndexMatcher() = default;
 
 const flat::UrlRule* UrlPatternIndexMatcher::FindMatch(
     const GURL& url,
     const url::Origin& first_party_origin,
     proto::ElementType element_type,
     proto::ActivationType activation_type,
     bool is_third_party,
     bool disable_generic_rules) const {
+  return FindMatch(url, first_party_origin,
+                   ProtoToFlatElementType(element_type),
+                   ProtoToFlatActivationType(activation_type), is_third_party,
+                   disable_generic_rules);
+}
+
+const flat::UrlRule* UrlPatternIndexMatcher::FindMatch(
+    const GURL& url,
+    const url::Origin& first_party_origin,
+    flat::ElementType element_type,
+    flat::ActivationType activation_type,
+    bool is_third_party,
+    bool disable_generic_rules) const {
   if (!flat_index_ || !url.is_valid())
     return nullptr;
-  if ((element_type == proto::ELEMENT_TYPE_UNSPECIFIED) ==
-      (activation_type == proto::ACTIVATION_TYPE_UNSPECIFIED)) {
+  if ((element_type == flat::ElementType_NONE) ==
+      (activation_type == flat::ActivationType_NONE)) {
     return nullptr;
   }
 
   return FindMatchInFlatUrlPatternIndex(*flat_index_, url, first_party_origin,
                                         element_type, activation_type,
                                         is_third_party, disable_generic_rules);
 }
 
 }  // namespace url_pattern_index