1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/extensions/api/declarative_webrequest/webrequest_rules_registry.h"
6
7#include <algorithm>
8#include <limits>
9#include <utility>
10
11#include "base/bind.h"
12#include "base/stl_util.h"
13#include "chrome/browser/extensions/api/declarative_webrequest/webrequest_condition.h"
14#include "chrome/browser/extensions/api/declarative_webrequest/webrequest_constants.h"
15#include "chrome/browser/extensions/api/web_request/web_request_api_helpers.h"
16#include "chrome/browser/extensions/api/web_request/web_request_permissions.h"
17#include "chrome/browser/profiles/profile.h"
18#include "extensions/browser/extension_system.h"
19#include "extensions/common/error_utils.h"
20#include "extensions/common/extension.h"
21#include "extensions/common/permissions/permissions_data.h"
22#include "net/url_request/url_request.h"
23
24using url_matcher::URLMatcherConditionSet;
25
26namespace {
27
28const char kActionCannotBeExecuted[] = "The action '*' can never be executed "
29    "because there are is no time in the request life-cycle during which the "
30    "conditions can be checked and the action can possibly be executed.";
31
32const char kAllURLsPermissionNeeded[] =
33    "To execute the action '*', you need to request host permission for all "
34    "hosts.";
35
36}  // namespace
37
38namespace extensions {
39
40WebRequestRulesRegistry::WebRequestRulesRegistry(
41    Profile* profile,
42    RulesCacheDelegate* cache_delegate,
43    const WebViewKey& webview_key)
44    : RulesRegistry(profile,
45                    declarative_webrequest_constants::kOnRequest,
46                    content::BrowserThread::IO,
47                    cache_delegate,
48                    webview_key),
49      profile_id_(profile) {
50  if (profile)
51    extension_info_map_ = ExtensionSystem::Get(profile)->info_map();
52}
53
54std::set<const WebRequestRule*> WebRequestRulesRegistry::GetMatches(
55    const WebRequestData& request_data_without_ids) const {
56  RuleSet result;
57
58  WebRequestDataWithMatchIds request_data(&request_data_without_ids);
59  request_data.url_match_ids = url_matcher_.MatchURL(
60      request_data.data->request->url());
61  request_data.first_party_url_match_ids = url_matcher_.MatchURL(
62      request_data.data->request->first_party_for_cookies());
63
64  // 1st phase -- add all rules with some conditions without UrlFilter
65  // attributes.
66  for (RuleSet::const_iterator it = rules_with_untriggered_conditions_.begin();
67       it != rules_with_untriggered_conditions_.end(); ++it) {
68    if ((*it)->conditions().IsFulfilled(-1, request_data))
69      result.insert(*it);
70  }
71
72  // 2nd phase -- add all rules with some conditions triggered by URL matches.
73  AddTriggeredRules(request_data.url_match_ids, request_data, &result);
74  AddTriggeredRules(request_data.first_party_url_match_ids,
75                    request_data, &result);
76
77  return result;
78}
79
80std::list<LinkedPtrEventResponseDelta> WebRequestRulesRegistry::CreateDeltas(
81    const InfoMap* extension_info_map,
82    const WebRequestData& request_data,
83    bool crosses_incognito) {
84  if (webrequest_rules_.empty())
85    return std::list<LinkedPtrEventResponseDelta>();
86
87  std::set<const WebRequestRule*> matches = GetMatches(request_data);
88
89  // Sort all matching rules by their priority so that they can be processed
90  // in decreasing order.
91  typedef std::pair<WebRequestRule::Priority, WebRequestRule::GlobalRuleId>
92      PriorityRuleIdPair;
93  std::vector<PriorityRuleIdPair> ordered_matches;
94  ordered_matches.reserve(matches.size());
95  for (std::set<const WebRequestRule*>::iterator i = matches.begin();
96       i != matches.end(); ++i) {
97    ordered_matches.push_back(make_pair((*i)->priority(), (*i)->id()));
98  }
99  // Sort from rbegin to rend in order to get descending priority order.
100  std::sort(ordered_matches.rbegin(), ordered_matches.rend());
101
102  // Build a map that maps each extension id to the minimum required priority
103  // for rules of that extension. Initially, this priority is -infinite and
104  // will be increased when the rules are processed and raise the bar via
105  // WebRequestIgnoreRulesActions.
106  typedef std::string ExtensionId;
107  typedef std::map<ExtensionId, WebRequestRule::Priority> MinPriorities;
108  typedef std::map<ExtensionId, std::set<std::string> > IgnoreTags;
109  MinPriorities min_priorities;
110  IgnoreTags ignore_tags;
111  for (std::vector<PriorityRuleIdPair>::iterator i = ordered_matches.begin();
112       i != ordered_matches.end(); ++i) {
113    const WebRequestRule::GlobalRuleId& rule_id = i->second;
114    const ExtensionId& extension_id = rule_id.first;
115    min_priorities[extension_id] = std::numeric_limits<int>::min();
116  }
117
118  // Create deltas until we have passed the minimum priority.
119  std::list<LinkedPtrEventResponseDelta> result;
120  for (std::vector<PriorityRuleIdPair>::iterator i = ordered_matches.begin();
121       i != ordered_matches.end(); ++i) {
122    const WebRequestRule::Priority priority_of_rule = i->first;
123    const WebRequestRule::GlobalRuleId& rule_id = i->second;
124    const ExtensionId& extension_id = rule_id.first;
125    const WebRequestRule* rule =
126        webrequest_rules_[rule_id.first][rule_id.second].get();
127    CHECK(rule);
128
129    // Skip rule if a previous rule of this extension instructed to ignore
130    // all rules with a lower priority than min_priorities[extension_id].
131    int current_min_priority = min_priorities[extension_id];
132    if (priority_of_rule < current_min_priority)
133      continue;
134
135    if (!rule->tags().empty() && !ignore_tags[extension_id].empty()) {
136      bool ignore_rule = false;
137      const WebRequestRule::Tags& tags = rule->tags();
138      for (WebRequestRule::Tags::const_iterator i = tags.begin();
139           !ignore_rule && i != tags.end();
140           ++i) {
141        ignore_rule |= ContainsKey(ignore_tags[extension_id], *i);
142      }
143      if (ignore_rule)
144        continue;
145    }
146
147    std::list<LinkedPtrEventResponseDelta> rule_result;
148    WebRequestAction::ApplyInfo apply_info = {
149      extension_info_map, request_data, crosses_incognito, &rule_result,
150      &ignore_tags[extension_id]
151    };
152    rule->Apply(&apply_info);
153    result.splice(result.begin(), rule_result);
154
155    min_priorities[extension_id] = std::max(current_min_priority,
156                                            rule->GetMinimumPriority());
157  }
158  return result;
159}
160
161std::string WebRequestRulesRegistry::AddRulesImpl(
162    const std::string& extension_id,
163    const std::vector<linked_ptr<RulesRegistry::Rule> >& rules) {
164  typedef std::pair<WebRequestRule::RuleId, linked_ptr<WebRequestRule> >
165      IdRulePair;
166  typedef std::vector<IdRulePair> RulesVector;
167
168  base::Time extension_installation_time =
169      GetExtensionInstallationTime(extension_id);
170
171  std::string error;
172  RulesVector new_webrequest_rules;
173  new_webrequest_rules.reserve(rules.size());
174  const Extension* extension =
175      extension_info_map_->extensions().GetByID(extension_id);
176  RulesMap& registered_rules = webrequest_rules_[extension_id];
177
178  for (std::vector<linked_ptr<RulesRegistry::Rule> >::const_iterator rule =
179       rules.begin(); rule != rules.end(); ++rule) {
180    const WebRequestRule::RuleId& rule_id(*(*rule)->id);
181    DCHECK(registered_rules.find(rule_id) == registered_rules.end());
182
183    scoped_ptr<WebRequestRule> webrequest_rule(WebRequestRule::Create(
184        url_matcher_.condition_factory(),
185        extension, extension_installation_time, *rule,
186        base::Bind(&Checker, base::Unretained(extension)),
187        &error));
188    if (!error.empty()) {
189      // We don't return here, because we want to clear temporary
190      // condition sets in the url_matcher_.
191      break;
192    }
193
194    new_webrequest_rules.push_back(
195        IdRulePair(rule_id, make_linked_ptr(webrequest_rule.release())));
196  }
197
198  if (!error.empty()) {
199    // Clean up temporary condition sets created during rule creation.
200    url_matcher_.ClearUnusedConditionSets();
201    return error;
202  }
203
204  // Wohoo, everything worked fine.
205  registered_rules.insert(new_webrequest_rules.begin(),
206                          new_webrequest_rules.end());
207
208  // Create the triggers.
209  for (RulesVector::const_iterator i = new_webrequest_rules.begin();
210       i != new_webrequest_rules.end(); ++i) {
211    URLMatcherConditionSet::Vector url_condition_sets;
212    const WebRequestConditionSet& conditions = i->second->conditions();
213    conditions.GetURLMatcherConditionSets(&url_condition_sets);
214    for (URLMatcherConditionSet::Vector::iterator j =
215         url_condition_sets.begin(); j != url_condition_sets.end(); ++j) {
216      rule_triggers_[(*j)->id()] = i->second.get();
217    }
218  }
219
220  // Register url patterns in |url_matcher_| and
221  // |rules_with_untriggered_conditions_|.
222  URLMatcherConditionSet::Vector all_new_condition_sets;
223  for (RulesVector::const_iterator i = new_webrequest_rules.begin();
224       i != new_webrequest_rules.end(); ++i) {
225    i->second->conditions().GetURLMatcherConditionSets(&all_new_condition_sets);
226    if (i->second->conditions().HasConditionsWithoutUrls())
227      rules_with_untriggered_conditions_.insert(i->second.get());
228  }
229  url_matcher_.AddConditionSets(all_new_condition_sets);
230
231  ClearCacheOnNavigation();
232
233  if (profile_id_ && !registered_rules.empty()) {
234    content::BrowserThread::PostTask(
235        content::BrowserThread::UI, FROM_HERE,
236        base::Bind(&extension_web_request_api_helpers::NotifyWebRequestAPIUsed,
237                   profile_id_, make_scoped_refptr(extension)));
238  }
239
240  return std::string();
241}
242
243std::string WebRequestRulesRegistry::RemoveRulesImpl(
244    const std::string& extension_id,
245    const std::vector<std::string>& rule_identifiers) {
246  // URLMatcherConditionSet IDs that can be removed from URLMatcher.
247  std::vector<URLMatcherConditionSet::ID> remove_from_url_matcher;
248  RulesMap& registered_rules = webrequest_rules_[extension_id];
249
250  for (std::vector<std::string>::const_iterator i = rule_identifiers.begin();
251       i != rule_identifiers.end(); ++i) {
252    // Skip unknown rules.
253    RulesMap::iterator webrequest_rules_entry = registered_rules.find(*i);
254    if (webrequest_rules_entry == registered_rules.end())
255      continue;
256
257    // Remove all triggers but collect their IDs.
258    CleanUpAfterRule(webrequest_rules_entry->second.get(),
259                     &remove_from_url_matcher);
260
261    // Removes the owning references to (and thus deletes) the rule.
262    registered_rules.erase(webrequest_rules_entry);
263  }
264  if (registered_rules.empty())
265    webrequest_rules_.erase(extension_id);
266
267  // Clear URLMatcher based on condition_set_ids that are not needed any more.
268  url_matcher_.RemoveConditionSets(remove_from_url_matcher);
269
270  ClearCacheOnNavigation();
271
272  return std::string();
273}
274
275std::string WebRequestRulesRegistry::RemoveAllRulesImpl(
276    const std::string& extension_id) {
277  // First we get out all URLMatcherConditionSets and remove the rule references
278  // from |rules_with_untriggered_conditions_|.
279  std::vector<URLMatcherConditionSet::ID> remove_from_url_matcher;
280  for (RulesMap::const_iterator it = webrequest_rules_[extension_id].begin();
281       it != webrequest_rules_[extension_id].end();
282       ++it) {
283    CleanUpAfterRule(it->second.get(), &remove_from_url_matcher);
284  }
285  url_matcher_.RemoveConditionSets(remove_from_url_matcher);
286
287  webrequest_rules_.erase(extension_id);
288  ClearCacheOnNavigation();
289  return std::string();
290}
291
292void WebRequestRulesRegistry::CleanUpAfterRule(
293    const WebRequestRule* rule,
294    std::vector<URLMatcherConditionSet::ID>* remove_from_url_matcher) {
295  URLMatcherConditionSet::Vector condition_sets;
296  rule->conditions().GetURLMatcherConditionSets(&condition_sets);
297  for (URLMatcherConditionSet::Vector::iterator j = condition_sets.begin();
298       j != condition_sets.end();
299       ++j) {
300    remove_from_url_matcher->push_back((*j)->id());
301    rule_triggers_.erase((*j)->id());
302  }
303  rules_with_untriggered_conditions_.erase(rule);
304}
305
306bool WebRequestRulesRegistry::IsEmpty() const {
307  // Easy first.
308  if (!rule_triggers_.empty() && url_matcher_.IsEmpty())
309    return false;
310
311  // Now all the registered rules for each extensions.
312  for (std::map<WebRequestRule::ExtensionId, RulesMap>::const_iterator it =
313           webrequest_rules_.begin();
314       it != webrequest_rules_.end();
315       ++it) {
316    if (!it->second.empty())
317      return false;
318  }
319  return true;
320}
321
322WebRequestRulesRegistry::~WebRequestRulesRegistry() {}
323
324base::Time WebRequestRulesRegistry::GetExtensionInstallationTime(
325    const std::string& extension_id) const {
326  return extension_info_map_->GetInstallTime(extension_id);
327}
328
329void WebRequestRulesRegistry::ClearCacheOnNavigation() {
330  extension_web_request_api_helpers::ClearCacheOnNavigation();
331}
332
333// static
334bool WebRequestRulesRegistry::Checker(const Extension* extension,
335                                      const WebRequestConditionSet* conditions,
336                                      const WebRequestActionSet* actions,
337                                      std::string* error) {
338  return (StageChecker(conditions, actions, error) &&
339          HostPermissionsChecker(extension, actions, error));
340}
341
342// static
343bool WebRequestRulesRegistry::HostPermissionsChecker(
344    const Extension* extension,
345    const WebRequestActionSet* actions,
346    std::string* error) {
347  if (extension->permissions_data()->HasEffectiveAccessToAllHosts())
348    return true;
349
350  // Without the permission for all URLs, actions with the STRATEGY_DEFAULT
351  // should not be registered, they would never be able to execute.
352  for (WebRequestActionSet::Actions::const_iterator action_iter =
353           actions->actions().begin();
354       action_iter != actions->actions().end();
355       ++action_iter) {
356    if ((*action_iter)->host_permissions_strategy() ==
357        WebRequestAction::STRATEGY_DEFAULT) {
358      *error = ErrorUtils::FormatErrorMessage(kAllURLsPermissionNeeded,
359                                              (*action_iter)->GetName());
360      return false;
361    }
362  }
363  return true;
364}
365
366// static
367bool WebRequestRulesRegistry::StageChecker(
368    const WebRequestConditionSet* conditions,
369    const WebRequestActionSet* actions,
370    std::string* error) {
371  // Actions and conditions can be checked and executed in specific stages
372  // of each web request. A rule is inconsistent if there is an action that
373  // can only be triggered in stages in which no condition can be evaluated.
374
375  // In which stages there are conditions to evaluate.
376  int condition_stages = 0;
377  for (WebRequestConditionSet::Conditions::const_iterator condition_iter =
378           conditions->conditions().begin();
379       condition_iter != conditions->conditions().end();
380       ++condition_iter) {
381    condition_stages |= (*condition_iter)->stages();
382  }
383
384  for (WebRequestActionSet::Actions::const_iterator action_iter =
385           actions->actions().begin();
386       action_iter != actions->actions().end();
387       ++action_iter) {
388    // Test the intersection of bit masks, this is intentionally & and not &&.
389    if ((*action_iter)->stages() & condition_stages)
390      continue;
391    // We only get here if no matching condition was found.
392    *error = ErrorUtils::FormatErrorMessage(kActionCannotBeExecuted,
393                                            (*action_iter)->GetName());
394    return false;
395  }
396  return true;
397}
398void WebRequestRulesRegistry::AddTriggeredRules(
399    const URLMatches& url_matches,
400    const WebRequestCondition::MatchData& request_data,
401    RuleSet* result) const {
402  for (URLMatches::const_iterator url_match = url_matches.begin();
403       url_match != url_matches.end(); ++url_match) {
404    RuleTriggers::const_iterator rule_trigger = rule_triggers_.find(*url_match);
405    CHECK(rule_trigger != rule_triggers_.end());
406    if (!ContainsKey(*result, rule_trigger->second) &&
407        rule_trigger->second->conditions().IsFulfilled(*url_match,
408                                                       request_data))
409      result->insert(rule_trigger->second);
410  }
411}
412
413}  // namespace extensions
414