Blacklist API change for allowing multiple rule matches

The findMatch function now returns a Match object which aggregates multiple
entries into one, in case (which is expected to be common) that multiple
rules match a given URL.

Since the set of matches is highly dependent on the URL, the Match class
replaces the old RequestData object to be added to URLRequests.

BUG=16932
TEST=Blacklist*
Review URL: http://codereview.chromium.org/149737

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@20886 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 265 insertions, 49 deletions

diff --git a/chrome/browser/net/chrome_url_request_context.cc b/chrome/browser/net/chrome_url_request_context.cc
index 3668328..1b33919 100644
--- a/chrome/browser/net/chrome_url_request_context.cc
+++ b/chrome/browser/net/chrome_url_request_context.cc
@@ -391,13 +391,12 @@ bool ChromeURLRequestContext::interceptCookie(const URLRequest* request,
   const URLRequest::UserData* d =
       request->GetUserData((void*)&Blacklist::kRequestDataKey);
   if (d) {
-    const Blacklist::Entry* entry =
-        static_cast<const Blacklist::RequestData*>(d)->entry();
-    if (entry->attributes() & Blacklist::kDontStoreCookies) {
+    const Blacklist::Match* match = static_cast<const Blacklist::Match*>(d);
+    if (match->attributes() & Blacklist::kDontStoreCookies) {
       cookie->clear();
       return false;
     }
-    if (entry->attributes() & Blacklist::kDontPersistCookies) {
+    if (match->attributes() & Blacklist::kDontPersistCookies) {
       *cookie = Blacklist::StripCookieExpiry(*cookie);
     }
   }
@@ -409,9 +408,8 @@ bool ChromeURLRequestContext::allowSendingCookies(const URLRequest* request)
   const URLRequest::UserData* d =
       request->GetUserData((void*)&Blacklist::kRequestDataKey);
   if (d) {
-    const Blacklist::Entry* entry =
-      static_cast<const Blacklist::RequestData*>(d)->entry();
-    if (entry->attributes() & Blacklist::kDontSendCookies)
+    const Blacklist::Match* match = static_cast<const Blacklist::Match*>(d);
+    if (match->attributes() & Blacklist::kDontSendCookies)
       return false;
   }
   return true;
diff --git a/chrome/browser/privacy_blacklist/blacklist.cc b/chrome/browser/privacy_blacklist/blacklist.cc
index e937ad2..a234bf2 100644
--- a/chrome/browser/privacy_blacklist/blacklist.cc
+++ b/chrome/browser/privacy_blacklist/blacklist.cc
@@ -9,17 +9,15 @@
 
 #include "base/file_path.h"
 #include "base/file_util.h"
+#include "base/string_util.h"
 #include "chrome/browser/privacy_blacklist/blacklist_store.h"
+#include "chrome/common/url_constants.h"
 #include "net/http/http_util.h"
 
 #define STRINGIZE(s) #s
 
 namespace {
 
-bool matches(const std::string& pattern, const std::string& url) {
-  return url.find(pattern) != std::string::npos;
-}
-
 const char* const cookie_headers[2] = { "cookie", "set-cookie" };
 
 }  // namespace
@@ -47,6 +45,49 @@ unsigned int Blacklist::String2Attribute(const std::string& s) {
   return 0;
 }
 
+bool Blacklist::Matches(const std::string& pattern, const std::string& url) {
+  if (pattern.size() > url.size())
+    return false;
+
+  std::string::size_type p = 0;
+  std::string::size_type u = 0;
+
+  while (pattern[p] != '\0' && url[u] != '\0') {
+    if (pattern[p] == '@') {
+      while (pattern[++p] == '@');  // Consecutive @ are redundant.
+
+      if (pattern[p] == '\0')
+        return true;  // Nothing to match after the @.
+
+      // Look for another wildcard to determine pattern-chunk.
+      std::string::size_type tp = pattern.find_first_of("@", p);
+
+      // If it must match until the end, compare the last characters.
+      if (tp == std::string::npos) {
+        std::string::size_type ur = url.size() - u;
+        std::string::size_type pr = pattern.size() - p;
+        return (pr <= ur) &&
+            (url.compare(url.size() - pr, pr, pattern.c_str() + p) == 0);
+      }
+
+      // Else find the pattern chunk which is pattern[p:tp]
+      std::string::size_type tu = url.find(pattern.c_str() + p, u, tp - p);
+      if (tu == std::string::npos)
+        return false;  // Pattern chunk not found.
+
+      // Since tp is strictly greater than p, both u and p always increase.
+      u = tu + tp - p;
+      p = tp;
+      continue;
+    }
+
+    // Match non-wildcard character.
+    if (pattern[p++] != url[u++])
+      return false;
+  }
+  return pattern[p] == '\0';
+}
+
 bool Blacklist::Entry::MatchType(const std::string& type) const {
   return std::find(types_.begin(), types_.end(), type) != types_.end();
 }
@@ -80,6 +121,27 @@ void Blacklist::Entry::SwapTypes(std::vector<std::string>* types) {
   }
 }
 
+bool Blacklist::Match::MatchType(const std::string& type) const {
+  for (std::vector<const Entry*>::const_iterator i = entries_.begin();
+      i != entries_.end(); ++i) {
+    if ((*i)->MatchType(type))
+      return true;
+  }
+  return false;
+}
+
+bool Blacklist::Match::IsBlocked(const GURL& url) const {
+  return (attributes_ & kBlockAll) ||
+    ((attributes_ & kBlockUnsecure) && !url.SchemeIsSecure());
+}
+
+Blacklist::Match::Match() : attributes_(0) {}
+
+void Blacklist::Match::AddEntry(const Entry* entry) {
+  attributes_ |= entry->attributes();
+  entries_.push_back(entry);
+}
+
 Blacklist::Blacklist(const FilePath& file) {
   // No blacklist, nothing to load.
   if (file.value().empty())
@@ -122,12 +184,24 @@ Blacklist::~Blacklist() {
 
 // Returns a pointer to the Blacklist-owned entry which matches the given
 // URL. If no matching Entry is found, returns null.
-const Blacklist::Entry* Blacklist::findMatch(const GURL& url) const {
+Blacklist::Match* Blacklist::findMatch(const GURL& url) const {
+  // Never match something which is not http, https or ftp.
+  // TODO(idanan): Investigate if this would be an inclusion test instead of an
+  // exclusion test and if there are other schemes to test for.
+  if (!url.SchemeIs(chrome::kHttpScheme) &&
+      !url.SchemeIs(chrome::kHttpsScheme) &&
+      !url.SchemeIs(chrome::kFtpScheme))
+    return 0;
+  Match* match = NULL;
   for (std::vector<Entry*>::const_iterator i = blacklist_.begin();
-       i != blacklist_.end(); ++i)
-    if (matches((*i)->pattern(), url.spec()))
-      return *i;
-  return 0;
+       i != blacklist_.end(); ++i) {
+    if (Matches((*i)->pattern(), url.host()+url.path())) {
+      if (!match)
+        match = new Match;
+      match->AddEntry(*i);
+    }
+  }
+  return match;
 }
 
 std::string Blacklist::StripCookies(const std::string& header) {
@@ -135,12 +209,19 @@ std::string Blacklist::StripCookies(const std::string& header) {
 }
 
 std::string Blacklist::StripCookieExpiry(const std::string& cookie) {
-  std::string::size_type start = cookie.find("; expires=");
+  std::string::size_type delim = cookie.find(';');
+  std::string::size_type start = cookie.find("expires=", delim + 1);
   if (start != std::string::npos) {
-    std::string::size_type finish = cookie.find(";", start+1);
-    std::string session_cookie(cookie, 0, start);
-    if (finish != std::string::npos)
-      session_cookie.append(cookie.substr(finish));
+    std::string::size_type i = start;
+    // Make sure only whitespace precedes the expiry until a delimiter.
+    while (cookie[--i] != ';')
+      if (!IsAsciiWhitespace(cookie[i]))
+        return cookie;
+
+    std::string session_cookie(cookie, 0, i);
+    std::string::size_type end = cookie.find(';', start + 1);
+    if (end != std::string::npos)
+      session_cookie.append(cookie.substr(end));
     return session_cookie;
   }
   return cookie;
diff --git a/chrome/browser/privacy_blacklist/blacklist.h b/chrome/browser/privacy_blacklist/blacklist.h
index 9d2b2e6..4c36d08 100644
--- a/chrome/browser/privacy_blacklist/blacklist.h
+++ b/chrome/browser/privacy_blacklist/blacklist.h
@@ -119,17 +119,29 @@ class Blacklist {
     friend class BlacklistIO;
   };
 
-  // When a request matches a Blacklist rule but the rule must be applied
-  // after the request has started, we tag it with this user data to
-  // avoid doing lookups more than once per request. The Entry is owned
-  // be the blacklist, so this indirection makes sure that it does not
-  // get destroyed by the Blacklist.
-  class RequestData : public URLRequest::UserData {
+  // A request may match one or more Blacklist rules. The Match class packages
+  // all the matching entries behind a single interface with access to the
+  // underlying set of entries so that we can display provider information.
+  // Often a match must be applied after a URLRequest has started, so it gets
+  // tagged with the Match object to avoid doing lookups more than once per
+  // request.
+  class Match : public URLRequest::UserData {
    public:
-    explicit RequestData(const Entry* entry) : entry_(entry) {}
-    const Entry* entry() const { return entry_; }
+    // Functions that return combined results from all entries.
+    unsigned int attributes() const { return attributes_; }
+    bool MatchType(const std::string&) const;
+    bool IsBlocked(const GURL&) const;
+
+    // Access to individual entries, mostly for display/logging purposes.
+    const std::vector<const Entry*>& entries() const { return entries_; }
+
    private:
-    const Entry* const entry_;
+    Match();
+    void AddEntry(const Entry* entry);
+    std::vector<const Entry*> entries_;
+    unsigned int attributes_;  // Precomputed ORed attributes of entries.
+
+    friend class Blacklist;  // Only blacklist constructs and sets these.
   };
 
   // Constructs a Blacklist given the filename of the persistent version.
@@ -144,9 +156,10 @@ class Blacklist {
   // Destructor.
   ~Blacklist();
 
-  // Returns a pointer to the Blacklist-owned entry which matches the given
-  // URL. If no matching Entry is found, returns null.
-  const Entry* findMatch(const GURL&) const;
+  // Returns a pointer to a Match structure holding all matching entries.
+  // If no matching Entry is found, returns null. Ownership belongs to the
+  // caller.
+  Match* findMatch(const GURL&) const;
 
   // Helper to remove cookies from a header.
   static std::string StripCookies(const std::string&);
@@ -155,11 +168,17 @@ class Blacklist {
   static std::string StripCookieExpiry(const std::string&);
 
  private:
+  // Matches a pattern to a core URL which is host/path with all the other
+  // optional parts (scheme, user, password, port) stripped away. Used only
+  // internally but made static so that access can be given to tests.
+  static bool Matches(const std::string& pattern, const std::string& url);
+
   std::vector<Entry*> blacklist_;
   std::vector<Provider*> providers_;
 
   FRIEND_TEST(BlacklistTest, Generic);
+  FRIEND_TEST(BlacklistTest, PatternMatch);
   DISALLOW_COPY_AND_ASSIGN(Blacklist);
 };
 
-#endif
+#endif  // CHROME_BROWSER_PRIVACY_BLACKLIST_BLACKLIST_H_
diff --git a/chrome/browser/privacy_blacklist/blacklist_unittest.cc b/chrome/browser/privacy_blacklist/blacklist_unittest.cc
index 4df5f7c..9516c11 100644
--- a/chrome/browser/privacy_blacklist/blacklist_unittest.cc
+++ b/chrome/browser/privacy_blacklist/blacklist_unittest.cc
@@ -60,9 +60,55 @@ TEST(BlacklistTest, Generic) {
   EXPECT_EQ("Sample", blacklist.providers_.front()->name());
   EXPECT_EQ("http://www.google.com", blacklist.providers_.front()->url());
 
-  // Empty blacklist should not match any URL.
+  // No match for chrome, about or empty URLs.
   EXPECT_FALSE(blacklist.findMatch(GURL()));
-  EXPECT_FALSE(blacklist.findMatch(GURL("http://www.google.com")));
+  EXPECT_FALSE(blacklist.findMatch(GURL("chrome://new-tab")));
+  EXPECT_FALSE(blacklist.findMatch(GURL("about:blank")));
+
+  // Expected rule matches.
+  Blacklist::Match* match;
+  match = blacklist.findMatch(GURL("http://www.google.com"));
+  EXPECT_TRUE(match);
+  if (match) {
+    EXPECT_EQ(Blacklist::kBlockByType|Blacklist::kDontPersistCookies,
+              match->attributes());
+    EXPECT_EQ(1U, match->entries().size());
+  }
+
+  match = blacklist.findMatch(GURL("http://www.site.com/bad/url"));
+  EXPECT_TRUE(match);
+  if (match) {
+    EXPECT_EQ(Blacklist::kBlockAll|
+              Blacklist::kBlockByType|Blacklist::kDontPersistCookies,
+              match->attributes());
+    EXPECT_EQ(2U, match->entries().size());
+  }
+
+  match = blacklist.findMatch(GURL("http://www.site.com/anonymous"));
+  EXPECT_TRUE(match);
+  if (match) {
+    EXPECT_EQ(Blacklist::kBlockByType|Blacklist::kDontPersistCookies,
+              match->attributes());
+    EXPECT_EQ(1U, match->entries().size());
+  }
+
+  match = blacklist.findMatch(GURL("http://www.site.com/anonymous/folder"));
+  EXPECT_TRUE(match);
+  if (match) {
+    EXPECT_EQ(Blacklist::kBlockByType|Blacklist::kDontPersistCookies,
+      match->attributes());
+    EXPECT_EQ(1U, match->entries().size());
+  }
+
+  match = blacklist.findMatch(
+      GURL("http://www.site.com/anonymous/folder/subfolder"));
+  EXPECT_TRUE(match);
+  if (match) {
+    EXPECT_EQ(Blacklist::kDontSendUserAgent|Blacklist::kDontSendReferrer|
+              Blacklist::kBlockByType|Blacklist::kDontPersistCookies,
+              match->attributes());
+    EXPECT_EQ(2U, match->entries().size());
+  }
 
   // StripCookieExpiry Tests
   std::string cookie1(
@@ -74,17 +120,25 @@ TEST(BlacklistTest, Generic) {
   std::string cookie3(
     "PREF=ID=14a549990453e42a:TM=1245183232:LM=1245183232:S=Occ7khRVIEE36Ao5;"
     " expires=Thu, 17-Jun-2011 02:13:52 GMT; path=/; domain=.google.com");
+  std::string cookie4("E=MC^2; path=relative;  expires=never;");
+  std::string cookie5("E=MC^2; path=relative;");
 
   // No expiry, should be equal to itself after stripping.
-  EXPECT_TRUE(cookie2 == Blacklist::StripCookieExpiry(cookie2));
+  EXPECT_EQ(cookie2, Blacklist::StripCookieExpiry(cookie2));
+  EXPECT_EQ(cookie5, Blacklist::StripCookieExpiry(cookie5));
 
   // Expiry, should be equal to non-expiry version after stripping.
-  EXPECT_TRUE(cookie2 == Blacklist::StripCookieExpiry(cookie1));
+  EXPECT_EQ(cookie2, Blacklist::StripCookieExpiry(cookie1));
+  EXPECT_EQ(cookie5, Blacklist::StripCookieExpiry(cookie4));
+
+  // Same cookie other than expiry should be same after stripping.
+  EXPECT_EQ(Blacklist::StripCookieExpiry(cookie2),
+            Blacklist::StripCookieExpiry(cookie3));
 
   // Edge cases.
-  EXPECT_TRUE(std::string() == Blacklist::StripCookieExpiry(std::string()));
-  EXPECT_TRUE(Blacklist::StripCookieExpiry(cookie2) ==
-              Blacklist::StripCookieExpiry(cookie3));
+  std::string invalid("#$%^&*()_+");
+  EXPECT_EQ(invalid, Blacklist::StripCookieExpiry(invalid));
+  EXPECT_EQ(std::string(), Blacklist::StripCookieExpiry(std::string()));
 
   // StripCookies Test. Note that "\r\n" line terminators are used
   // because the underlying net util uniformizes those when stripping
@@ -105,3 +159,52 @@ TEST(BlacklistTest, Generic) {
   EXPECT_TRUE(header2 == Blacklist::StripCookies(header2));
   EXPECT_TRUE(header4 == Blacklist::StripCookies(header3));
 }
+
+TEST(BlacklistTest, PatternMatch) {
+  // @ matches all but empty strings.
+  EXPECT_TRUE(Blacklist::Matches("@", "foo.com"));
+  EXPECT_TRUE(Blacklist::Matches("@", "path"));
+  EXPECT_TRUE(Blacklist::Matches("@", "foo.com/path"));
+  EXPECT_TRUE(Blacklist::Matches("@", "x"));
+  EXPECT_FALSE(Blacklist::Matches("@", ""));
+  EXPECT_FALSE(Blacklist::Matches("@", std::string()));
+
+  // Prefix match.
+  EXPECT_TRUE(Blacklist::Matches("prefix@", "prefix.com"));
+  EXPECT_TRUE(Blacklist::Matches("prefix@", "prefix.com/path"));
+  EXPECT_TRUE(Blacklist::Matches("prefix@", "prefix/path"));
+  EXPECT_TRUE(Blacklist::Matches("prefix@", "prefix/prefix"));
+  EXPECT_FALSE(Blacklist::Matches("prefix@", "prefix"));
+  EXPECT_FALSE(Blacklist::Matches("prefix@", "Xprefix"));
+  EXPECT_FALSE(Blacklist::Matches("prefix@", "Y.Xprefix"));
+  EXPECT_FALSE(Blacklist::Matches("prefix@", "Y/Xprefix"));
+
+  // Postfix match.
+  EXPECT_TRUE(Blacklist::Matches("@postfix", "something.postfix"));
+  EXPECT_TRUE(Blacklist::Matches("@postfix", "something/postfix"));
+  EXPECT_TRUE(Blacklist::Matches("@postfix", "foo.com/something/postfix"));
+  EXPECT_FALSE(Blacklist::Matches("@postfix", "postfix"));
+  EXPECT_FALSE(Blacklist::Matches("@postfix", "postfixZ"));
+  EXPECT_FALSE(Blacklist::Matches("@postfix", "postfixZ.Y"));
+
+  // Infix matches.
+  EXPECT_TRUE(Blacklist::Matches("@evil@", "www.evil.com"));
+  EXPECT_TRUE(Blacklist::Matches("@evil@", "www.evil.com/whatever"));
+  EXPECT_TRUE(Blacklist::Matches("@evil@", "www.whatever.com/evilpath"));
+  EXPECT_TRUE(Blacklist::Matches("@evil@", "www.evil.whatever.com"));
+  EXPECT_FALSE(Blacklist::Matches("@evil@", "evil"));
+  EXPECT_FALSE(Blacklist::Matches("@evil@", "evil/"));
+  EXPECT_FALSE(Blacklist::Matches("@evil@", "/evil"));
+
+  // Outfix matches.
+  EXPECT_TRUE(Blacklist::Matches("really@bad", "really/bad"));
+  EXPECT_TRUE(Blacklist::Matches("really@bad", "really.com/bad"));
+  EXPECT_TRUE(Blacklist::Matches("really@bad", "really.com/path/bad"));
+  EXPECT_TRUE(Blacklist::Matches("really@bad", "really.evil.com/path/bad"));
+  EXPECT_FALSE(Blacklist::Matches("really@bad", "really.bad.com"));
+  EXPECT_FALSE(Blacklist::Matches("really@bad", "reallybad"));
+  EXPECT_FALSE(Blacklist::Matches("really@bad", ".reallybad"));
+  EXPECT_FALSE(Blacklist::Matches("really@bad", "reallybad."));
+  EXPECT_FALSE(Blacklist::Matches("really@bad", "really.bad."));
+  EXPECT_FALSE(Blacklist::Matches("really@bad", ".really.bad"));
+}
diff --git a/chrome/browser/renderer_host/resource_dispatcher_host.cc b/chrome/browser/renderer_host/resource_dispatcher_host.cc
index 16d8a62..35a47f0 100644
--- a/chrome/browser/renderer_host/resource_dispatcher_host.cc
+++ b/chrome/browser/renderer_host/resource_dispatcher_host.cc
@@ -358,10 +358,11 @@ void ResourceDispatcherHost::BeginRequest(
   }
 
   // Note that context can still be NULL here when running unit tests.
-  const Blacklist::Entry* entry = context && context->blacklist() ?
+  Blacklist::Match* match = context && context->blacklist() ?
       context->blacklist()->findMatch(request_data.url) : NULL;
-  if (entry && entry->IsBlocked(request_data.url)) {
+  if (match && match->IsBlocked(request_data.url)) {
     // TODO(idanan): Send a ResourceResponse to replace the blocked resource.
+    delete match;
     return;
   }
 
@@ -392,14 +393,13 @@ void ResourceDispatcherHost::BeginRequest(
 
   // Construct the request.
   URLRequest* request = new URLRequest(request_data.url, this);
-  if (entry && entry->attributes()) {
-    request->SetUserData((void*)&Blacklist::kRequestDataKey,
-                         new Blacklist::RequestData(entry));
+  if (match) {
+    request->SetUserData((void*)&Blacklist::kRequestDataKey, match);
   }
   request->set_method(request_data.method);
   request->set_first_party_for_cookies(request_data.first_party_for_cookies);
 
-  if (!entry || !(entry->attributes() & Blacklist::kDontSendReferrer))
+  if (!match || !(match->attributes() & Blacklist::kDontSendReferrer))
     request->set_referrer(request_data.referrer.spec());
 
   request->SetExtraRequestHeaders(request_data.headers);
diff --git a/chrome/browser/renderer_host/resource_message_filter.cc b/chrome/browser/renderer_host/resource_message_filter.cc
index d913aec..bf542cd 100644
--- a/chrome/browser/renderer_host/resource_message_filter.cc
+++ b/chrome/browser/renderer_host/resource_message_filter.cc
@@ -18,6 +18,7 @@
 #include "chrome/browser/net/dns_global.h"
 #include "chrome/browser/plugin_service.h"
 #include "chrome/browser/profile.h"
+#include "chrome/browser/privacy_blacklist/blacklist.h"
 #include "chrome/browser/renderer_host/audio_renderer_host.h"
 #include "chrome/browser/renderer_host/browser_render_process_host.h"
 #include "chrome/browser/renderer_host/file_system_accessor.h"
@@ -424,8 +425,22 @@ void ResourceMessageFilter::OnSetCookie(const GURL& url,
                                         const std::string& cookie) {
   URLRequestContext* context = url.SchemeIs(chrome::kExtensionScheme) ?
       extensions_request_context_.get() : request_context_.get();
-  if (context->cookie_policy()->CanSetCookie(url, first_party_for_cookies))
-    context->cookie_store()->SetCookie(url, cookie);
+  if (context->cookie_policy()->CanSetCookie(url, first_party_for_cookies)) {
+    if (context->blacklist()) {
+      Blacklist::Match* match = context->blacklist()->findMatch(url);
+      if (match) {
+        if (match->attributes() & Blacklist::kDontPersistCookies) {
+          context->cookie_store()->SetCookie(url,
+              Blacklist::StripCookieExpiry(cookie));
+        } else if (!(match->attributes() & Blacklist::kDontStoreCookies)) {
+          context->cookie_store()->SetCookie(url, cookie);
+        }
+        delete match;
+      }
+    } else {
+      context->cookie_store()->SetCookie(url, cookie);
+    }
+  }
 }
 
 void ResourceMessageFilter::OnGetCookies(const GURL& url,