Refactoring how conditions without URL attributes are handled.

chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.cc

Index: chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.cc
diff --git a/chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.cc b/chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.cc
index 1ece019e6a397c6c4e7e31d0ecc7cc457b17551c..c66036258f97e6a1aeef27875fc51aba45079f07 100644
--- a/chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.cc
+++ b/chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.cc
@@ -6,6 +6,7 @@
 
 #include "base/bind.h"
 #include "base/logging.h"
+#include "base/stl_util.h"
 #include "base/stringprintf.h"
 #include "base/values.h"
 #include "chrome/browser/extensions/api/declarative_webrequest/request_stage.h"
@@ -49,7 +50,6 @@ WebRequestCondition::WebRequestCondition(
     : url_matcher_conditions_(url_matcher_conditions),
       condition_attributes_(condition_attributes),
       applicable_request_stages_(~0) {
-  CHECK(url_matcher_conditions.get());
   for (WebRequestConditionAttributes::const_iterator i =
        condition_attributes_.begin(); i != condition_attributes_.end(); ++i) {
     applicable_request_stages_ &= (*i)->GetStages();
@@ -59,7 +59,13 @@ WebRequestCondition::WebRequestCondition(
 WebRequestCondition::~WebRequestCondition() {}
 
 bool WebRequestCondition::IsFulfilled(
+    const std::set<URLMatcherConditionSet::ID>& url_matches,
     const WebRequestRule::RequestData& request_data) const {
+  // Check a UrlFilter attribute if present.
+  if (url_matcher_conditions_.get() &&
+      !ContainsKey(url_matches, url_matcher_conditions_->id()))
+    return false;
+
   // All condition attributes must be fulfilled for a fulfilled condition.
   if (!(request_data.stage & applicable_request_stages_)) {
     // A condition that cannot be evaluated is considered as violated.
@@ -132,13 +138,6 @@ scoped_ptr<WebRequestCondition> WebRequestCondition::Create(
       return scoped_ptr<WebRequestCondition>(NULL);
   }
 
-  if (!url_matcher_condition_set) {
-    URLMatcherConditionSet::Conditions url_matcher_conditions;
-    url_matcher_conditions.insert(
-        url_matcher_condition_factory->CreateHostPrefixCondition(""));
-    url_matcher_condition_set =
-        new URLMatcherConditionSet(++g_next_id, url_matcher_conditions);
-  }
   scoped_ptr<WebRequestCondition> result(
       new WebRequestCondition(url_matcher_condition_set, attributes));
 
@@ -150,38 +149,53 @@ scoped_ptr<WebRequestCondition> WebRequestCondition::Create(
   return result.Pass();
 }
 
-
 //
 // WebRequestConditionSet
 //
 
-WebRequestConditionSet::WebRequestConditionSet(
-    const WebRequestConditionSet::Conditions& conditions)
-    : conditions_(conditions) {
-  for (Conditions::iterator i = conditions_.begin(); i != conditions_.end();
-       ++i) {
-    URLMatcherConditionSet::ID trigger_id =
-        (*i)->url_matcher_condition_set_id();
-    match_triggers_[trigger_id] = i->get();
-  }
-}
-
 WebRequestConditionSet::~WebRequestConditionSet() {}
 
 bool WebRequestConditionSet::IsFulfilled(
-    URLMatcherConditionSet::ID url_match,
+    const std::set<URLMatcherConditionSet::ID>& url_matches,
     const WebRequestRule::RequestData& request_data) const {
-  MatchTriggers::const_iterator trigger = match_triggers_.find(url_match);
-  DCHECK(trigger != match_triggers_.end());
-  DCHECK_EQ(url_match, trigger->second->url_matcher_condition_set_id());
-  return trigger->second->IsFulfilled(request_data);
+  // Prioritize the conditions triggered by URL matches.
+  if (!match_id_to_condition_.empty()) {
+    // [first_id, last_id] is the range in |url_matches| corresponding to our
+    // conditions.
+    URLMatcherConditionSet::ID first_id = match_id_to_condition_.begin()->first;
+    URLMatcherConditionSet::ID last_id = match_id_to_condition_.rbegin()->first;
+
+    // Only inspect the url_matches in the range corresponding our conditions.
+    for (std::set<URLMatcherConditionSet::ID>::const_iterator it =
+         url_matches.lower_bound(first_id);

[battre, 2013/01/07 17:36:27]

nit: +4 spaces as in line 182.

+         it != url_matches.end() && *it <= last_id; ++it) {
+      URLMatcherIdToCondition::const_iterator triggered =
+          match_id_to_condition_.find(*it);
+      if (triggered != match_id_to_condition_.end() &&
+          triggered->second->IsFulfilled(url_matches, request_data))
+        return true;
+    }
+  }

[battre, 2013/01/07 17:36:27]

I discussed this with Vaclav and I am concerned that this may become extremely
slow in the worst case because |url_matches| can be very large.

Our suggestion was to change the signature to the following:
bool WebRequestConditionSet::IsFulfilled(
    URLMatcherConditionSet::ID url_match_trigger,
    const std::set<URLMatcherConditionSet::ID>& url_matches,
    const WebRequestRule::RequestData& request_data) const;

We would guarantee that this function is called 

- once for each trigger contained in the ConditionSet, and in addition

- once with |url_match_trigger| == -1 in case the ConditionSet has
conditions_without_urls_.

until any ConditionSet is fulfilled.

[Jeffrey Yasskin, 2013/01/07 20:47:41]

We can optimize this scan by putting the matches into a sorted vector and using
a modified binary search to find the next one. That bounds the time at
O(min(|match_id_to_condition| * log(|url_matches|),
log(|match_id_to_condition|)*|url_matches|, |match_id_to_condition| +
|url_matches|)). In the case you're worried about, with lots of url_matches and
few conditions in each rule, that adds up to O(|url_matches|*log(|rules|) +
|conditions|*log(|url_matches|)), while your suggestion is
O(|url_matches|*log(|conditions|)). In practice the current code will be quite
fast since IDs are actually allocated sequentially.

I'd like to see a benchmark (micro or macro, but automated) showing the cases
you're interested in before we spend too much time worrying about optimizations
here.

I imagine your suggestion will work with Vaclav's first_party_url change by
using the passed-in ID to narrow to a condition, and then searching the
first_party_url_match_set using that condition?

I think the templating change will work either way, so if you want to pass in an
ID, I don't object.

+
+  // Now try out all conditions without URL attributes.
+  for (std::vector<const WebRequestCondition*>::const_iterator it =
+           conditions_without_urls_.begin();
+       it != conditions_without_urls_.end(); ++it) {
+    if ((*it)->IsFulfilled(url_matches, request_data))
+      return true;
+  }
+
+  return false;
 }
 
 void WebRequestConditionSet::GetURLMatcherConditionSets(
     URLMatcherConditionSet::Vector* condition_sets) const {
   for (Conditions::const_iterator i = conditions_.begin();
        i != conditions_.end(); ++i) {
-    condition_sets->push_back((*i)->url_matcher_condition_set());
+    scoped_refptr<URLMatcherConditionSet> set =
+        (*i)->url_matcher_condition_set();
+    if (set.get())
+      condition_sets->push_back(set);
   }
 }
 
@@ -190,7 +204,7 @@ scoped_ptr<WebRequestConditionSet> WebRequestConditionSet::Create(
     URLMatcherConditionFactory* url_matcher_condition_factory,
     const AnyVector& conditions,
     std::string* error) {
-  WebRequestConditionSet::Conditions result;
+  Conditions result;
 
   for (AnyVector::const_iterator i = conditions.begin();
        i != conditions.end(); ++i) {
@@ -203,7 +217,33 @@ scoped_ptr<WebRequestConditionSet> WebRequestConditionSet::Create(
     result.push_back(make_linked_ptr(condition.release()));
   }
 
-  return scoped_ptr<WebRequestConditionSet>(new WebRequestConditionSet(result));
+  URLMatcherIdToCondition match_id_to_condition;
+  std::vector<const WebRequestCondition*> conditions_without_urls;
+
+  for (Conditions::const_iterator i = result.begin(); i != result.end(); ++i) {
+    const URLMatcherConditionSet* set = (*i)->url_matcher_condition_set().get();
+    if (set) {
+      URLMatcherConditionSet::ID id = set->id();
+      match_id_to_condition[id] = i->get();
+    } else {
+      conditions_without_urls.push_back(i->get());
+    }
+  }
+
+  return make_scoped_ptr(new WebRequestConditionSet(
+      result, match_id_to_condition, conditions_without_urls));
+}
+
+bool WebRequestConditionSet::HasConditionsWithoutUrls() const {
+  return !conditions_without_urls_.empty();
 }
 
+WebRequestConditionSet::WebRequestConditionSet(
+    const Conditions& conditions,

[vabr (Chromium), 2012/12/20 19:27:42]

These three const references lead to a lot of copying, and the originals are
destroyed just after the constructor returns.

Should I use the swap method instead? That way I would copy the container
objects, but only transfer the ownership of their data.

To me it sounds like a good idea, but I don't remember seeing swap in the code
much -- is there some reason for why this is perhaps discouraged?

+    const URLMatcherIdToCondition& match_id_to_condition,
+    const std::vector<const WebRequestCondition*>& conditions_without_urls)
+    : match_id_to_condition_(match_id_to_condition),
+      conditions_(conditions),
+      conditions_without_urls_(conditions_without_urls) {}
+
 }  // namespace extensions