Issue 3670 - Make rules case sensitive where possible

lib/contentBlockerList.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2016 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 32 matching lines @@
   }
 }
 
 function escapeRegExp(s)
 {
   return s.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
 }
 
 function matchDomain(domain)
 {
-  return "^https?://([^/:]*\\.)?" + escapeRegExp(domain) + "[/:]";
+  return "^https?://([^/:]*\\.)?" + escapeRegExp(domain).toLowerCase() + "[/:]";
 }
 
 function convertElemHideFilter(filter, elemhideSelectorExceptions)
 {
   let included = [];
   let excluded = [];
   let rules = [];
 
   parseDomains(filter.domains, included, excluded);
 
   if (excluded.length == 0 && !(filter.selector in elemhideSelectorExceptions))
     return {matchDomains: included.map(matchDomain), selector: filter.selector};
 }
 
+// Convert the "regexpSource" part of a filter's text to a regular expression,
+// also deciding if the expression can safely be converted to and matched as
+// lowercase.
 function toRegExp(text)
 {
   let result = [];
   let lastIndex = text.length - 1;
+  let hostnameStarted = false;
+  let hostnameFinished = false;
+  let caseSensitive = false;
 
   for (let i = 0; i < text.length; i++)
   {
     let c = text[i];
 
     switch (c)
     {
       case "*":
         if (result.length > 0 && i < lastIndex && text[i + 1] != "*")
           result.push(".*");
         break;
       case "^":
         if (i < lastIndex)
           result.push(".");
         break;
       case "|":
         if (i == 0)
         {
           result.push("^");
           break;
         }
         if (i == lastIndex)
         {
           result.push("$");
           break;
         }
         if (i == 1 && text[0] == "|")
         {
           result.push("https?://");
+          hostnameStarted = caseSensitive = true;
           break;
         }
-      case ".": case "+": case "?": case "$":
-      case "{": case "}": case "(": case ")":
-      case "[": case "]": case "\\":
+        result.push("\\", c);
+        break;
+      case "/":
+        if (!hostnameStarted && i >= 2 && text[i-2] == ":" && text[i-1] == "/")

[Sebastian Noack, 2016/02/24 21:47:06]

Note that when you use charAt() as in my initial suggestion you shouldn't have
to bother about out of bound reads, making the i>=2 check redundant.

[kzar, 2016/02/24 22:19:45]

Done.

+        {
+          hostnameStarted = caseSensitive = true;
+          result.push("/");
+          break;

[Sebastian Noack, 2016/02/24 21:47:07]

If I get the logic here straight, there is an inconsistency: If we encounter
"://" the last slash wouldn't be escaped as we bail out here. However, for all
other occurences of slashes we would fall through, and eventually escape it,
right? But we shouldn't escape slashes no matter what.

[kzar, 2016/02/24 22:19:46]

No, for all other occurrences of slashes we fall through, but then push the
unescaped version as `c != "?"` is true.

I've done it this way because otherwise hostnameStarted will be set to true and
then immediately hostnameFinished will be set to true as well. (I'm not entirely
sure the change to use a fall through here helped, which is why I uploaded that
change as a separate patch set.)

In fact, after addressing your other feedback this logic makes no sense at all.
I've reworked it.

+        }
+      case "?": case "*": case "^":

[Sebastian Noack, 2016/02/24 21:47:06]

"*" and "^" are already handled and bail out above. So this code is never
reached for these characters.

[kzar, 2016/02/24 22:19:46]

Done.

+        if (hostnameStarted)
+          hostnameFinished = true;
+        if (c != "?")
+        {
+          result.push(c);
+          break;
+        }
+      case ".": case "+": case "$": case "{":
+      case "}": case "(": case ")": case "[":
+      case "]": case "\\":
         result.push("\\", c);
         break;
       default:
+        if (hostnameFinished && (c >= "a" && c <= "z" || c >= "A" && c <= "Z"))

[Sebastian Noack, 2016/02/24 21:47:06]

Note that this check can be simlified with a regexp: /[a-z]/i.test(c). But I can
understand if you don't want to use a regexp in a state machine. I don't have a
strong opinion either, so I leave it up to you. However, if you stick to the
current logic, IMO it would be slightly easier to read like that:

  if (hostnameFinished && (c >= "a" && c <= "z" ||
                           c >= "A" && c <= "Z"))

[kzar, 2016/02/24 22:19:45]

Done.

+          caseSensitive = false;
         result.push(c);
     }
   }
 
-  return result.join("");
+  return {regexp: result.join(""), caseSensitive: caseSensitive};
 }
 
-function getRegExpSource(filter)
+function getRegExpTrigger(filter)
 {
-  let source = toRegExp(filter.regexpSource.replace(
+  let result = toRegExp(filter.regexpSource.replace(
     // Safari expects punycode, filter lists use unicode
     /^(\|\||\|?https?:\/\/)([\w\-.*\u0080-\uFFFF]+)/i,
     function (match, prefix, domain)
     {
       return prefix + punycode.toASCII(domain);
     }
   ));
 
+  let trigger = {"url-filter": result.regexp};
+
   // Limit rules to to HTTP(S) URLs
-  if (!/^(\^|http)/i.test(source))
-    source = "^https?://.*" + source;
+  if (!/^(\^|http)/i.test(trigger["url-filter"]))
+    trigger["url-filter"] = "^https?://.*" + trigger["url-filter"];
 
-  return source;
+  // For rules containing only a hostname we know that we're matching against
+  // a lowercase string and can therefore enable case sensitive matching.
+  if (result.caseSensitive)
+  {
+    trigger["url-filter"] = trigger["url-filter"].toLowerCase();
+    trigger["url-filter-is-case-sensitive"] = true;
+  }
+
+  return trigger;
 }
 
 function getResourceTypes(filter)
 {
   let types = [];
 
   if (filter.contentType & typeMap.IMAGE)
     types.push("image");
   if (filter.contentType & typeMap.STYLESHEET)
     types.push("style-sheet");
@@ skipping 26 matching lines @@
 
     if (tldjs.getDomain(domain) == domain)
       result.push("www." + domain);
   }
 
   return result;
 }
 
 function convertFilter(filter, action, withResourceTypes)
 {
-  let trigger = {"url-filter": getRegExpSource(filter)};
+  let trigger = getRegExpTrigger(filter);
   let included = [];
   let excluded = [];
 
-  parseDomains(filter.domains, included, excluded);
+  if (filter.matchCase)
+    trigger["url-filter-is-case-sensitive"] = true;
+
+ parseDomains(filter.domains, included, excluded);
 
   if (withResourceTypes)
     trigger["resource-type"] = getResourceTypes(filter);
   if (filter.thirdParty != null)
     trigger["load-type"] = [filter.thirdParty ? "third-party" : "first-party"];
 
   if (included.length > 0)
     trigger["if-domain"] = addDomainPrefix(included);
   else if (excluded.length > 0)
     trigger["unless-domain"] = addDomainPrefix(excluded);
@@ skipping 177 matching lines @@
   {
     while (selectors.length)
     {
       let selector = selectors.splice(0, selectorLimit).join(", ");
 
       // As of Safari 9.0 element IDs are matched as lowercase. We work around
       // this by converting to the attribute format [id="elementID"]
       selector = convertIDSelectorsToAttributeSelectors(selector);
 
       addRule({
-        trigger: {"url-filter": matchDomain},
+        trigger: {"url-filter": matchDomain,
+                  "url-filter-is-case-sensitive": true},
         action: {type: "css-display-none",
                  selector: selector}
       });
     }
   });
 
   for (let filter of this.elemhideExceptions)
     addRule(convertFilter(filter, "ignore-previous-rules", false));
   for (let filter of this.requestFilters)
     addRule(convertFilter(filter, "block", true));
   for (let filter of this.requestExceptions)
     addRule(convertFilter(filter, "ignore-previous-rules", true));
 
   return rules;
 };