Refactoring how conditions without URL attributes are handled.

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

 // Copyright (c) 2012 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 "chrome/browser/extensions/api/declarative_webrequest/webrequest_rules_registry.h"
 
 #include <limits>
 
 #include "chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.h"
 #include "chrome/browser/extensions/api/web_request/web_request_api_helpers.h"
 #include "chrome/browser/extensions/api/web_request/web_request_permissions.h"
 #include "chrome/browser/extensions/extension_system.h"
 #include "net/url_request/url_request.h"
 
 namespace extensions {
 
 WebRequestRulesRegistry::WebRequestRulesRegistry(Profile* profile,
                                                  Delegate* delegate)
     : RulesRegistryWithCache(delegate) {
   if (profile)
     extension_info_map_ = ExtensionSystem::Get(profile)->info_map();
 }
 
 std::set<WebRequestRule::GlobalRuleId>
 WebRequestRulesRegistry::GetMatches(
     const WebRequestRule::RequestData& request_data) {
   std::set<WebRequestRule::GlobalRuleId> result;
 
-  // Figure out for which rules the URL match conditions were fulfilled.
+  // First check for rules with a satisfied condition set without URL

[Jeffrey Yasskin, 2012/12/18 02:24:32]

Given the next change you're making, and the declarativeContent refactoring I'm
working on, I think I would rearrange this function:

1) Collect a set of rules that _might_ match, given the set of
URLMatcherConditionSet::IDs that MatchURL returns. That would be roughly like:

std::set<const WebRequestRule*> rules_to_check =
rules_with_untriggered_conditions;

typedef std::set<URLMatcherConditionSet::ID> URLMatches;
URLMatches url_matches = url_matcher_.MatchURL(request_data.request->url());
for (URLMatches::const_iterator url_match = url_matches.begin();
     url_match != url_matches.end(); ++url_match) {
  RuleTriggers::const_iterator rule_trigger = rule_triggers_.find(*url_match);
  CHECK(rule_trigger != rule_triggers_.end());
  rules_to_check.insert(rule_trigger->second);
}

// Now rules_to_check is all the rules that might match.


2) Check each of these rules against the
request-data-and-matching-URLMatcherConditionSet::IDs:

for (std::set<const WebRequestRule*>::iterator it = rules_to_check.begin();
     it != rules_to_check.end(); ) {
  if (rule->conditions().IsFulfilled(url_matches, request_data))
    ++it;
  else
    it = rules_to_check.erase(it);
}

return rules_to_check;


Note that IsFulfilled() now takes the full set of matching IDs, and it becomes
responsible for checking whether each condition's ID is in that set. Your
https://codereview.chromium.org/11414230/ will add a second set<ID> argument,
and my https://codereview.chromium.org/11572061/ will move all of these set<ID>s
into the MatchData structs.

Sound reasonable?

[battre, 2012/12/18 17:17:54]

This is a very elegant way of dealing with this. SGTM.

[vabr (Chromium), 2012/12/18 18:26:42]

I implemented Jeffrey's suggestion. My only concern was performance, so I
analysed the runtime of both versions of GetMatches. I can share the analysis
with you if you are interested, but it's not a solid piece of computing :). The
main problem here is that the run time depends a lot on which rules we get, how
much URL attributes per rule, etc. There are families of collections of rules
such that the old approach is asymptotically faster, and other families of
collections such that the new approach is asymptotically faster. Another source
of mess were constants for asymptotic complexities of things like set insertion.
To decrease the imprecision as much as possible (but it is still way beyond
talking seriously) I cancelled time for similar work done in both approaches
(e.g., retrieving a rule from rule triggers for each URL match). After all that
I got two formulas, and when I put some random characteristics of rule sets
(e.g., 1000 rules, 800 of them have each 100 conditions with a single URL
attribute) in those formulas, the results seemed to be very similar, even when I
scaled the characteristics (multiplying the numbers by 100, 1000, etc.).

Based on that shaky evidence, I hope this is not hurting the performance.

+  // attributes.
+  for (std::set<const WebRequestRule*>::iterator rule =
+           rules_with_untriggered_conditions_.begin();
+       rule != rules_with_untriggered_conditions_.end(); ++rule) {
+    if (result.find((*rule)->id()) == result.end() &&
+        (*rule)->conditions().IsFulfilledWithoutURLMatcher(request_data))
+      result.insert((*rule)->id());
+  }
+
+  // Now figure out for which rules the URL match conditions were fulfilled.
   typedef std::set<URLMatcherConditionSet::ID> URLMatches;
   URLMatches url_matches = url_matcher_.MatchURL(request_data.request->url());
 
   // Then we need to check for each of these, whether the other
   // WebRequestConditionAttributes are also fulfilled.
   for (URLMatches::iterator url_match = url_matches.begin();
        url_match != url_matches.end(); ++url_match) {
     RuleTriggers::iterator rule_trigger = rule_triggers_.find(*url_match);
     CHECK(rule_trigger != rule_triggers_.end());
 
     WebRequestRule* rule = rule_trigger->second;
-    if (rule->conditions().IsFulfilled(*url_match, request_data))
+    if (result.find(rule->id()) == result.end() &&

[vabr (Chromium), 2012/12/13 12:18:06]

This check spares time, because some rules might both have a condition with and
a condition without a UrlFilter attribute in their condition set. If the latter
is fulfilled, then we no longer have to test the former here.

[battre, 2012/12/18 08:20:44]

Use ContainsKey from base/stl_util.h?

[vabr (Chromium), 2012/12/18 18:26:42]

Code changed. But thanks, base/stl_util.h is a useful place to know about. :)

+        rule->conditions().IsFulfilled(*url_match, request_data))
       result.insert(rule->id());
   }
   return result;
 }
 
 std::list<LinkedPtrEventResponseDelta> WebRequestRulesRegistry::CreateDeltas(
     const ExtensionInfoMap* extension_info_map,
     const WebRequestRule::RequestData& request_data,
     bool crosses_incognito) {
   if (webrequest_rules_.empty())
@@ skipping 98 matching lines @@
        i != new_webrequest_rules.end(); ++i) {
     URLMatcherConditionSet::Vector url_condition_sets;
     const WebRequestConditionSet& conditions = i->second->conditions();
     conditions.GetURLMatcherConditionSets(&url_condition_sets);
     for (URLMatcherConditionSet::Vector::iterator j =
          url_condition_sets.begin(); j != url_condition_sets.end(); ++j) {
       rule_triggers_[(*j)->id()] = i->second.get();
     }
   }
 
-  // Register url patterns in url_matcher_.
+  // Register url patterns in |url_matcher_| and
+  // |rules_with_untriggered_conditions_|.
   URLMatcherConditionSet::Vector all_new_condition_sets;
   for (RulesMap::iterator i = new_webrequest_rules.begin();
        i != new_webrequest_rules.end(); ++i) {
     i->second->conditions().GetURLMatcherConditionSets(&all_new_condition_sets);
+    if (i->second->conditions().has_untriggered_conditions())
+      rules_with_untriggered_conditions_.insert(i->second.get());
   }
   url_matcher_.AddConditionSets(all_new_condition_sets);
 
   ClearCacheOnNavigation();
 
   return "";
 }
 
 std::string WebRequestRulesRegistry::RemoveRulesImpl(
     const std::string& extension_id,
@@ skipping 13 matching lines @@
     // Remove all triggers but collect their IDs.
     URLMatcherConditionSet::Vector condition_sets;
     WebRequestRule* rule = webrequest_rules_entry->second.get();
     rule->conditions().GetURLMatcherConditionSets(&condition_sets);
     for (URLMatcherConditionSet::Vector::iterator j = condition_sets.begin();
          j != condition_sets.end(); ++j) {
       remove_from_url_matcher.push_back((*j)->id());
       rule_triggers_.erase((*j)->id());
     }
 
-    // Remove reference to actual rule.

[Jeffrey Yasskin, 2012/12/18 02:24:32]

This comment should probably have read "Remove owning reference to actual rule,
which deletes the rule."

[vabr (Chromium), 2012/12/18 18:26:42]

Corrected.

+    // Remove references to the rule.
     webrequest_rules_.erase(webrequest_rules_entry);
+    rules_with_untriggered_conditions_.erase(rule);

[Jeffrey Yasskin, 2012/12/18 02:24:32]

This ought to happen before webrequest_rules_.erase() because that actually
deletes the rule. Nothing will break immediately if you remove the pointer from
the set afterwards, but it makes the code more brittle.

[vabr (Chromium), 2012/12/18 18:26:42]

Makes sense, thanks for explaining that to me.
I changed the order and corrected the comment.

   }
 
   // Clear URLMatcher based on condition_set_ids that are not needed any more.
   url_matcher_.RemoveConditionSets(remove_from_url_matcher);
 
   ClearCacheOnNavigation();
 
   return "";
 }
 
@@ skipping 30 matching lines @@
     return base::Time();
 
   return extension_info_map_->GetInstallTime(extension_id);
 }
 
 void WebRequestRulesRegistry::ClearCacheOnNavigation() {
   extension_web_request_api_helpers::ClearCacheOnNavigation();
 }
 
 }  // namespace extensions