Issue 3673 - Merge closely matching rules

lib/abp2blocklist.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2017 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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 /** @module abp2blocklist */
 
 "use strict";
 
 let filterClasses = require("filterClasses");
-let tldjs = require("tldjs");
 let punycode = require("punycode");
 
 const selectorLimit = 5000;
 const typeMap = filterClasses.RegExpFilter.typeMap;
-const whitelistableRequestTypes = (typeMap.IMAGE
-                                   | typeMap.STYLESHEET
-                                   | typeMap.SCRIPT
-                                   | typeMap.FONT
-                                   | typeMap.MEDIA
-                                   | typeMap.POPUP
-                                   | typeMap.OBJECT
-                                   | typeMap.OBJECT_SUBREQUEST
-                                   | typeMap.XMLHTTPREQUEST
-                                   | typeMap.PING
-                                   | typeMap.SUBDOCUMENT
-                                   | typeMap.OTHER);
+
+const httpRequestTypes = typeMap.IMAGE |
+                         typeMap.STYLESHEET |
+                         typeMap.SCRIPT |
+                         typeMap.FONT |
+                         typeMap.MEDIA |
+                         typeMap.POPUP |
+                         typeMap.OBJECT |
+                         typeMap.OBJECT_SUBREQUEST |
+                         typeMap.XMLHTTPREQUEST |
+                         typeMap.PING |
+                         typeMap.SUBDOCUMENT |
+                         typeMap.OTHER;
+const rawRequestTypes = typeMap.XMLHTTPREQUEST |
+                        typeMap.WEBSOCKET |
+                        typeMap.WEBRTC |
+                        typeMap.OBJECT_SUBREQUEST |
+                        typeMap.PING |
+                        typeMap.OTHER;
+const whitelistableRequestTypes = httpRequestTypes |
+                                  typeMap.WEBSOCKET |
+                                  typeMap.WEBRTC;
 
 function callLater(func)
 {
   return new Promise(resolve =>
   {
     let call = () => resolve(func());
 
     // If this looks like Node.js, call process.nextTick, otherwise call
     // setTimeout.
     if (typeof process != "undefined")
       process.nextTick(call);
     else
       setTimeout(call, 0);
   });
 }
 
-function async(funcs)
-{
-  if (!Array.isArray(funcs))
-    funcs = Array.from(arguments);
+function async(callees, mapFunction)
+{
+  if (!(Symbol.iterator in callees))
+    callees = [callees];
 
   let lastPause = Date.now();
-
-  return funcs.reduce((promise, next) => promise.then(() =>
-  {
-    // If it has been 100ms or longer since the last call, take a pause. This
-    // keeps the browser from freezing up.
-    let now = Date.now();
-    if (now - lastPause >= 100)
-    {
-      lastPause = now;
-      return callLater(next);
-    }
-
-    return next();
-  }),
-  Promise.resolve());
+  let index = 0;
+
+  let promise = Promise.resolve();
+
+  for (let next of callees)
+  {
+    let currentIndex = index;
+
+    promise = promise.then(() =>
+    {
+      if (mapFunction)
+        next = mapFunction(next, currentIndex);
+
+      // If it has been 100ms or longer since the last call, take a pause. This
+      // keeps the browser from freezing up.
+      let now = Date.now();
+      if (now - lastPause >= 100)
+      {
+        lastPause = now;
+        return callLater(next);
+      }
+
+      return next();
+    });
+
+    index++;
+  }
+
+  return promise;
 }
 
 function parseDomains(domains, included, excluded)
 {
   for (let domain in domains)
   {
     if (domain != "")
     {
       let enabled = domains[domain];
       domain = punycode.toASCII(domain.toLowerCase());
 
       if (!enabled)
         excluded.push(domain);
       else if (!domains[""])
         included.push(domain);
     }
   }
 }
 
 function escapeRegExp(s)
 {
   return s.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
 }
 
 function matchDomain(domain)
 {
+  if (!domain)
+    return "^https?://";
+
   return "^https?://([^/:]*\\.)?" + escapeRegExp(domain).toLowerCase() + "[/:]";
+}
+
+function getURLSchemes(contentType)
+{
+  // If the given content type includes all supported URL schemes, simply
+  // return a single generic URL scheme pattern. This minimizes the size of the
+  // generated rule set. The downside to this is that it will also match
+  // schemes that we do not want to match (e.g. "ftp://"), but this can be
+  // mitigated by adding exceptions for those schemes.
+  if (contentType & typeMap.WEBSOCKET && contentType & typeMap.WEBRTC &&
+      contentType & httpRequestTypes)
+    return ["[^:]+:(//)?"];
+
+  let urlSchemes = [];
+
+  if (contentType & typeMap.WEBSOCKET)
+    urlSchemes.push("wss?://");
+
+  if (contentType & typeMap.WEBRTC)
+    urlSchemes.push("stuns?:", "turns?:");
+
+  if (contentType & httpRequestTypes)
+    urlSchemes.push("https?://");
+
+  return urlSchemes;
+}
+
+function findSubdomainsInList(domain, list)
+{
+  let subdomains = [];
+  let suffixLength = domain.length + 1;
+
+  for (let name of list)
+  {
+    if (name.length > suffixLength && name.slice(-suffixLength) == "." + domain)
+      subdomains.push(name.slice(0, -suffixLength));
+  }
+
+  return subdomains;
+}
+
+function extractFilterDomains(filters)
+{
+  let domains = new Set();
+  for (let filter of filters)
+  {
+    let parsed = parseFilterRegexpSource(filter.regexpSource);
+    if (parsed.justHostname)
+      domains.add(parsed.hostname);
+  }
+  return domains;
 }
 
 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};
+    return {matchDomains: included, selector: filter.selector};
 }
 
 /**
  * Parse the given filter "regexpSource" string. Producing a regular expression,
  * extracting the hostname (if any), deciding if the regular expression is safe
  * to be converted + matched as lower case and noting if the source contains
  * anything after the hostname.)
  *
  * @param   {string} text regexpSource property of a filter
+ * @param   {string} urlScheme The URL scheme to use in the regular expression
  * @returns {object} An object containing a regular expression string, a bool
  *                   indicating if the filter can be safely matched as lower
  *                   case, a hostname string (or undefined) and a bool
  *                   indicating if the source only contains a hostname or not:
  *                     {regexp: "...",
  *                      canSafelyMatchAsLowercase: true/false,
  *                      hostname: "...",
  *                      justHostname: true/false}
  */
-function parseFilterRegexpSource(text)
+function parseFilterRegexpSource(text, urlScheme)
 {
   let regexp = [];
-  let lastIndex = text.length - 1;
+
+  // Convert the text into an array of Unicode characters.
+  //
+  // In the case of surrogate pairs (the smiley emoji, for example), one
+  // Unicode code point is represented by two JavaScript characters together.
+  // We want to iterate over Unicode code points rather than JavaScript
+  // characters.
+  let characters = Array.from(text);
+
+  let lastIndex = characters.length - 1;
   let hostname;
   let hostnameStart = null;
   let hostnameFinished = false;
   let justHostname = false;
   let canSafelyMatchAsLowercase = false;
 
-  for (let i = 0; i < text.length; i++)
-  {
-    let c = text[i];
+  if (!urlScheme)
+    urlScheme = getURLSchemes()[0];
+
+  for (let i = 0; i < characters.length; i++)
+  {
+    let c = characters[i];
 
     if (hostnameFinished)
       justHostname = false;
 
     // If we're currently inside the hostname we have to be careful not to
     // escape any characters until after we have converted it to punycode.
     if (hostnameStart != null && !hostnameFinished)
     {
       let endingChar = (c == "*" || c == "^" ||
                         c == "?" || c == "/" || c == "|");
       if (!endingChar && i != lastIndex)
         continue;
 
       hostname = punycode.toASCII(
-        text.substring(hostnameStart, endingChar ? i : i + 1)
+        characters.slice(hostnameStart, endingChar ? i : i + 1).join("")
+                  .toLowerCase()
       );
       hostnameFinished = justHostname = true;
       regexp.push(escapeRegExp(hostname));
       if (!endingChar)
         break;
     }
 
     switch (c)
     {
       case "*":
-        if (regexp.length > 0 && i < lastIndex && text[i + 1] != "*")
+        if (regexp.length > 0 && i < lastIndex && characters[i + 1] != "*")
           regexp.push(".*");
         break;
       case "^":
-        if (i < lastIndex)
-          regexp.push(".");
+        let alphabet = "a-z";
+        // If justHostname is true and we've encountered a "^", it means we're
+        // still in the hostname part of the URL. Since hostnames are always
+        // lower case (Punycode), there's no need to include "A-Z" in the
+        // pattern. Further, subsequent code may lower-case the entire regular
+        // expression (if the URL contains only the hostname part), leaving us
+        // with "a-za-z", which would be redundant.
+        if (!justHostname)
+          alphabet = "A-Z" + alphabet;
+        let digits = "0-9";
+        // Note that the "-" must appear first here in order to retain its
+        // literal meaning within the brackets.
+        let specialCharacters = "-_.%";
+        let separator = "[^" + specialCharacters + alphabet + digits + "]";
+        if (i == 0)
+          regexp.push("^" + urlScheme + "(.*" + separator + ")?");
+        else if (i == lastIndex)
+          regexp.push("(" + separator + ".*)?$");
+        else
+          regexp.push(separator);
         break;
       case "|":
         if (i == 0)
         {
           regexp.push("^");
           break;
         }
         if (i == lastIndex)
         {
           regexp.push("$");
           break;
         }
-        if (i == 1 && text[0] == "|")
+        if (i == 1 && characters[0] == "|")
         {
           hostnameStart = i + 1;
           canSafelyMatchAsLowercase = true;
-          regexp.push("https?://([^/]+\\.)?");
+          regexp.push(urlScheme + "([^/]+\\.)?");
           break;
         }
         regexp.push("\\|");
         break;
       case "/":
         if (!hostnameFinished &&
-            text.charAt(i-2) == ":" && text.charAt(i-1) == "/")
+            characters[i - 2] == ":" && characters[i - 1] == "/")
         {
           hostnameStart = i + 1;
           canSafelyMatchAsLowercase = true;
         }
         regexp.push("/");
         break;
       case ".": case "+": case "$": case "?":
       case "{": case "}": case "(": case ")":
       case "[": case "]": case "\\":
         regexp.push("\\", c);
         break;
       default:
         if (hostnameFinished && (c >= "a" && c <= "z" ||
                                  c >= "A" && c <= "Z"))
           canSafelyMatchAsLowercase = false;
-        regexp.push(c);
+        regexp.push(c == "%" ? c : encodeURI(c));
     }
   }
 
   return {
     regexp: regexp.join(""),
     canSafelyMatchAsLowercase: canSafelyMatchAsLowercase,
     hostname: hostname,
     justHostname: justHostname
   };
 }
 
-function getResourceTypes(filter)
+function getResourceTypes(contentType)
 {
   let types = [];
 
-  if (filter.contentType & typeMap.IMAGE)
+  if (contentType & typeMap.IMAGE)
     types.push("image");
-  if (filter.contentType & typeMap.STYLESHEET)
+  if (contentType & typeMap.STYLESHEET)
     types.push("style-sheet");
-  if (filter.contentType & typeMap.SCRIPT)
+  if (contentType & typeMap.SCRIPT)
     types.push("script");
-  if (filter.contentType & typeMap.FONT)
+  if (contentType & typeMap.FONT)
     types.push("font");
-  if (filter.contentType & (typeMap.MEDIA | typeMap.OBJECT))
+  if (contentType & (typeMap.MEDIA | typeMap.OBJECT))
     types.push("media");
-  if (filter.contentType & typeMap.POPUP)
+  if (contentType & typeMap.POPUP)
     types.push("popup");
-  if (filter.contentType & (typeMap.XMLHTTPREQUEST |
-                            typeMap.OBJECT_SUBREQUEST |
-                            typeMap.PING |
-                            typeMap.OTHER))
+  if (contentType & rawRequestTypes)
     types.push("raw");
-  if (filter.contentType & typeMap.SUBDOCUMENT)
+  if (contentType & typeMap.SUBDOCUMENT)
     types.push("document");
 
   return types;
 }
 
-function addDomainPrefix(domains)
-{
-  let result = [];
-
-  for (let domain of domains)
-  {
-    result.push(domain);
-
-    if (tldjs.getDomain(domain) == domain)
-      result.push("www." + domain);
-  }
-
-  return result;
-}
-
-function convertFilterAddRules(rules, filter, action, withResourceTypes)
-{
-  let parsed = parseFilterRegexpSource(filter.regexpSource);
+function makeRuleCopies(trigger, action, urlSchemes)
+{
+  let copies = [];
+
+  // Always make a deep copy of the rule, since rules may have to be
+  // manipulated individually at a later stage.
+  let stringifiedTrigger = JSON.stringify(trigger);
+
+  let filterPattern = trigger["url-filter"].substring(1);
+  let startIndex = 0;
+
+  // If the URL filter already begins with the first URL scheme pattern, skip
+  // it.
+  if (trigger["url-filter"].startsWith("^" + urlSchemes[0]))
+  {
+    filterPattern = filterPattern.substring(urlSchemes[0].length);
+    startIndex = 1;
+  }
+  else
+  {
+    filterPattern = ".*" + filterPattern;
+  }
+
+  for (let i = startIndex; i < urlSchemes.length; i++)
+  {
+    let copyTrigger = Object.assign(JSON.parse(stringifiedTrigger), {
+      "url-filter": "^" + urlSchemes[i] + filterPattern
+    });
+    copies.push({trigger: copyTrigger, action});
+  }
+
+  return copies;
+}
+
+function excludeTopURLFromTrigger(trigger)
+{
+  trigger["unless-top-url"] = [trigger["url-filter"]];
+  if (trigger["url-filter-is-case-sensitive"])
+    trigger["top-url-filter-is-case-sensitive"] = true;
+}
+
+function convertFilterAddRules(rules, filter, action, withResourceTypes,
+                               exceptionDomains, contentType)
+{
+  if (!contentType)
+    contentType = filter.contentType;
+
+  // If WebSocket or WebRTC are given along with other options but not
+  // including all three of WebSocket, WebRTC, and at least one HTTP raw type,
+  // we must generate multiple rules. For example, for the filter
+  // "foo$websocket,image", we must generate one rule with "^wss?://" and "raw"
+  // and another rule with "^https?://" and "image". If we merge the two, we
+  // end up blocking requests of all HTTP raw types (e.g. XMLHttpRequest)
+  // inadvertently.
+  if ((contentType & typeMap.WEBSOCKET && contentType != typeMap.WEBSOCKET &&
+       !(contentType & typeMap.WEBRTC &&
+         contentType & rawRequestTypes & httpRequestTypes)) ||
+      (contentType & typeMap.WEBRTC && contentType != typeMap.WEBRTC &&
+       !(contentType & typeMap.WEBSOCKET &&
+         contentType & rawRequestTypes & httpRequestTypes)))
+  {
+    if (contentType & typeMap.WEBSOCKET)
+    {
+      convertFilterAddRules(rules, filter, action, withResourceTypes,
+                            exceptionDomains, typeMap.WEBSOCKET);
+    }
+
+    if (contentType & typeMap.WEBRTC)
+    {
+      convertFilterAddRules(rules, filter, action, withResourceTypes,
+                            exceptionDomains, typeMap.WEBRTC);
+    }
+
+    contentType &= ~(typeMap.WEBSOCKET | typeMap.WEBRTC);
+
+    if (!contentType)
+      return;
+  }
+
+  let urlSchemes = getURLSchemes(contentType);
+  let parsed = parseFilterRegexpSource(filter.regexpSource, urlSchemes[0]);
 
   // For the special case of $document whitelisting filters with just a domain
   // we can generate an equivalent blocking rule exception using if-domain.
   if (filter instanceof filterClasses.WhitelistFilter &&
-      filter.contentType & typeMap.DOCUMENT &&
+      contentType & typeMap.DOCUMENT &&
       parsed.justHostname)
   {
     rules.push({
       trigger: {
         "url-filter": ".*",
-        "if-domain": addDomainPrefix([parsed.hostname])
+        "if-domain": ["*" + parsed.hostname]
       },
       action: {type: "ignore-previous-rules"}
     });
     // If the filter contains other supported options we'll need to generate
     // further rules for it, but if not we can simply return now.
-    if (!(filter.contentType & whitelistableRequestTypes))
+    if (!(contentType & whitelistableRequestTypes))
       return;
   }
 
   let trigger = {"url-filter": parsed.regexp};
 
-  // Limit rules to HTTP(S) URLs
-  if (!/^(\^|http)/i.test(trigger["url-filter"]))
-    trigger["url-filter"] = "^https?://.*" + trigger["url-filter"];
+  // If the URL filter begins with one of the URL schemes for this content
+  // type, we generate additional rules for all the URL scheme patterns;
+  // otherwise, if the start of the URL filter literally matches the first URL
+  // scheme pattern, we just generate additional rules for the remaining URL
+  // scheme patterns.
+  //
+  // For example, "stun:foo$webrtc" will give us "stun:foo", then we add a "^"
+  // in front of this and generate two additional rules for
+  // "^stuns?:.*stun:foo" and "^turns?:.*stun:foo". On the other hand,
+  // "||foo$webrtc" will give us "^stuns?:([^/]+\\.)?foo", so we just generate
+  // "^turns?:([^/]+\\.)?foo" in addition.
+  //
+  // Note that the filter can be already anchored to the beginning
+  // (e.g. "|stun:foo$webrtc"), in which case we do not generate any additional
+  // rules.
+  let needAltRules = trigger["url-filter"][0] != "^" ||
+                     trigger["url-filter"].startsWith("^" + urlSchemes[0]);
+
+  if (trigger["url-filter"][0] != "^")
+  {
+    if (!urlSchemes.some(scheme => new RegExp("^" + scheme)
+                                   .test(trigger["url-filter"])))
+    {
+      trigger["url-filter"] = urlSchemes[0] + ".*" + trigger["url-filter"];
+    }
+
+    trigger["url-filter"] = "^" + trigger["url-filter"];
+  }
 
   // For rules containing only a hostname we know that we're matching against
   // a lowercase string unless the matchCase option was passed.
   if (parsed.canSafelyMatchAsLowercase && !filter.matchCase)
     trigger["url-filter"] = trigger["url-filter"].toLowerCase();
 
   if (parsed.canSafelyMatchAsLowercase || filter.matchCase)
     trigger["url-filter-is-case-sensitive"] = true;
 
   let included = [];
   let excluded = [];
 
   parseDomains(filter.domains, included, excluded);
 
+  if (exceptionDomains)
+    excluded = excluded.concat(exceptionDomains);
+
   if (withResourceTypes)
   {
-    trigger["resource-type"] = getResourceTypes(filter);
-
-    if (trigger["resource-type"].length == 0)
+    let resourceTypes = getResourceTypes(contentType);
+
+    // Content blocker rules can't differentiate between sub-document requests
+    // (iframes) and top-level document requests. To avoid too many false
+    // positives, we prevent rules with no hostname part from blocking document
+    // requests.
+    //
+    // Once Safari 11 becomes our minimum supported version, we could change
+    // our approach here to use the new "unless-top-url" property instead.
+    if (filter instanceof filterClasses.BlockingFilter && !parsed.hostname)
+      resourceTypes = resourceTypes.filter(type => type != "document");
+
+    if (resourceTypes.length == 0)
       return;
+
+    trigger["resource-type"] = resourceTypes;
   }
 
   if (filter.thirdParty != null)
     trigger["load-type"] = [filter.thirdParty ? "third-party" : "first-party"];
 
+  let addTopLevelException = false;
+
   if (included.length > 0)
-    trigger["if-domain"] = addDomainPrefix(included);
+  {
+    trigger["if-domain"] = [];
+
+    for (let name of included)
+    {
+      // If this is a blocking filter or an element hiding filter, add the
+      // subdomain wildcard only if no subdomains have been excluded.
+      let notSubdomains = null;
+      if ((filter instanceof filterClasses.BlockingFilter ||
+           filter instanceof filterClasses.ElemHideFilter) &&
+          (notSubdomains = findSubdomainsInList(name, excluded)).length > 0)
+      {
+        trigger["if-domain"].push(name);
+
+        // Add the "www" prefix but only if it hasn't been excluded.
+        if (!notSubdomains.includes("www"))
+          trigger["if-domain"].push("www." + name);
+      }
+      else
+      {
+        trigger["if-domain"].push("*" + name);
+      }
+    }
+  }
   else if (excluded.length > 0)
-    trigger["unless-domain"] = addDomainPrefix(excluded);
+  {
+    trigger["unless-domain"] = excluded.map(name => "*" + name);
+  }
+  else if (filter instanceof filterClasses.BlockingFilter &&
+           filter.contentType & typeMap.SUBDOCUMENT && parsed.hostname)
+  {
+    // Rules with a hostname part are still allowed to block document requests,
+    // but we add an exception for top-level documents.
+    //
+    // Note that we can only do this if there's no "unless-domain" property for
+    // now. This also only works in Safari 11 onwards, while older versions
+    // simply ignore this property. Once Safari 11 becomes our minimum
+    // supported version, we can merge "unless-domain" into "unless-top-url".
+    addTopLevelException = true;
+    excludeTopURLFromTrigger(trigger);
+  }
 
   rules.push({trigger: trigger, action: {type: action}});
-}
-
-function hasNonASCI(obj)
-{
-  if (typeof obj == "string")
-  {
-    if (/[^\x00-\x7F]/.test(obj))
-      return true;
-  }
-
-  if (typeof obj == "object")
-  {
-    if (obj instanceof Array)
-      for (let item of obj)
-        if (hasNonASCI(item))
-          return true;
-
-    let names = Object.getOwnPropertyNames(obj);
-    for (let name of names)
-      if (hasNonASCI(obj[name]))
-        return true;
-  }
-
-  return false;
+
+  if (needAltRules)
+  {
+    // Generate additional rules for any alternative URL schemes.
+    for (let altRule of makeRuleCopies(trigger, {type: action}, urlSchemes))
+    {
+      if (addTopLevelException)
+        excludeTopURLFromTrigger(altRule.trigger);
+
+      rules.push(altRule);
+    }
+  }
 }
 
 function convertIDSelectorsToAttributeSelectors(selector)
 {
   // First we figure out where all the IDs are
   let sep = "";
   let start = null;
   let positions = [];
   for (let i = 0; i < selector.length; i++)
   {
@@ skipping 33 matching lines @@
   {
     newSelector.push(selector.substring(i, pos.start));
     newSelector.push('[id=', selector.substring(pos.start + 1, pos.end), ']');
     i = pos.end;
   }
   newSelector.push(selector.substring(i));
 
   return newSelector.join("");
 }
 
+function addCSSRules(rules, selectors, domain, exceptionDomains)
+{
+  let unlessDomain = exceptionDomains.size > 0 ? [] : null;
+
+  exceptionDomains.forEach(name =>
+  {
+    // For domain-specific filters, include the exception domains only if
+    // they're subdomains of the given domain.
+    if (!domain || name.substr(-domain.length - 1) == "." + domain)
+      unlessDomain.push("*" + name);
+  });
+
+  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);
+
+    let rule = {
+      trigger: {"url-filter": matchDomain(domain),
+                "url-filter-is-case-sensitive": true},
+      action: {type: "css-display-none",
+               selector: selector}
+    };
+
+    if (unlessDomain)
+      rule.trigger["unless-domain"] = unlessDomain;
+
+    rules.push(rule);
+  }
+}
+
 /**
  * Check if two strings are a close match
  *
  * This function returns an edit operation, one of "substitute", "delete", and
  * "insert", along with an index in the source string where the edit must occur
  * in order to arrive at the target string. If the strings are not a close
  * match, it returns null.
  *
  * Two strings are considered to be a close match if they are one edit
  * operation apart.
@@ skipping 38 matching lines @@
   // calculation.
   if (diff < 0)
   {
     let tmp = s;
     s = t;
     t = tmp;
   }
 
   let edit = null;
 
-  let i = 0, j = 0;

[kzar, 2017/05/29 09:49:54]

Nit: Please split into separate lets.

Also I wonder if we should leave them as undefined here and assign them in the
initialisation bit of the for loops? (Especially with j it seems kind of
misleading to set it to 0 here.)

[Manish Jethani, 2017/05/31 06:43:06]

Done.
I feel like since the variables are in the outer scope it's actually clearer to
initialize them here.

Also j does need to start at 0 (see next comment).

+  let i = 0;
+  let j = 0;
 
   // Start from the beginning and keep going until we hit a character that
   // doesn't match.
   for (; i < s.length; i++)
   {
     if (s[i] != t[i])
       break;
   }
 
   // Now do exactly the same from the end, but also stop if we reach the
   // position where we terminated the previous loop.
   for (; j < t.length; j++)

[kzar, 2017/05/29 09:49:53]

Since j is working backwards through the characters wouldn't it be clearer to
start it as t.length -1 and decrement it down to 0? I think then you wouldn't
need to do `length - j` so often later on as well?

[Manish Jethani, 2017/05/31 06:43:06]

Then we would need two variables, one for s.length - j and one for t.length - j.
j is basically the offset from the end of both the strings.

   {
     if (t.length - j == i || s[s.length - j - 1] != t[t.length - j - 1])
       break;
   }
 
   if (diff == 0)
   {
     // If the strings are equal in length and the delta isn't exactly one
     // character, it's not a close match.
     if (t.length - j - i != 1)

[kzar, 2017/05/29 09:49:53]

Probably a dumb question but wouldn't this also consider identical strings to
not be a close match?

[Manish Jethani, 2017/05/31 06:43:07]

Yes, identical strings are not a close match by definition, since there's no
edit operation. It's debatable whether this should be the case, but anyway it
doesn't matter since identical URL filters will be filtered out in the previous
step when we eliminate redundant rules.

       return null;
   }
   else if (i != t.length - j)
   {
     // For strings of unequal length, if we haven't found a match for every
     // single character in the shorter string counting from both the beginning
     // and the end, it's not a close match.
     return null;
   }
 
@@ skipping 25 matching lines @@
       edit.endIndex = s.length - j;
   }
 
   return edit;
 }
 
 function eliminateRedundantRulesByURLFilter(rulesInfo, exhaustive)
 {
   const heuristicRange = 1000;
 
+  let ol = rulesInfo.length;
+
   // Throw out obviously redundant rules.
-  return async(rulesInfo.map((ruleInfo, index) => () =>
+  return async(rulesInfo, (ruleInfo, index) => () =>
   {
     // If this rule is already marked as redundant, don't bother comparing it
     // with other rules.
     if (rulesInfo[index].redundant)
       return;
 
     let limit = exhaustive ? rulesInfo.length :
                 Math.min(index + heuristicRange, rulesInfo.length);
 
     for (let i = index, j = i + 1; j < limit; j++)
@@ skipping 12 matching lines @@
         {
           rulesInfo[i].redundant = true;
           break;
         }
       }
       else if (target.substring(0, source.length) == source)
       {
         rulesInfo[j].redundant = true;
       }
     }
-  }))
+  })
   .then(() => rulesInfo.filter(ruleInfo => !ruleInfo.redundant));
 }
 
 function findMatchesForRuleByURLFilter(rulesInfo, index, exhaustive)
 {
   // Closely matching rules are likely to be within a certain range. We only
   // look for matches within this range by default. If we increase this value,
   // it can give us more matches and a smaller resulting rule set, but possibly
   // at a significant performance cost.
   //
@@ skipping 141 matching lines @@
     if (best.length > 0)
     {
       let urlFilter = rule.trigger["url-filter"];
 
       let editIndex = best[0].edit.index;
 
       if (!multiEdit)
       {
         // Merge all the matching rules into this one.
 
-        let characters = [];
+        let characters = [urlFilter[editIndex]];
         let quantifier = "";
 
         for (let match of best)
         {
           if (match.edit.type == "delete")
           {
             quantifier = "?";
           }
           else
           {
             let character = rulesInfo[match.index].rule
                             .trigger["url-filter"][editIndex];
-            characters.push(character);
+
+            // Insert any hyphen at the beginning so it gets interpreted as a
+            // literal hyphen.
+            if (character == "-")
+              characters.unshift(character);
+            else
+              characters.push(character);
           }
 
           // Mark the target rule as merged so other rules don't try to merge
           // it again.
           rulesInfo[match.index].merged = true;
         }
 
         urlFilter = urlFilter.substring(0, editIndex + 1) + quantifier +
                     urlFilter.substring(editIndex + 1);
-        if (characters.length > 0)
+        if (characters.length > 1)
         {
           urlFilter = urlFilter.substring(0, editIndex) + "[" +
-                      urlFilter[editIndex] + characters.join("") + "]" +
+                      characters.join("") + "]" +
                       urlFilter.substring(editIndex + 1);
         }
       }
       else
       {
         let editEndIndex = best[0].edit.endIndex;
 
         // Mark the target rule as merged so other rules don't try to merge it
         // again.
         rulesInfo[best[0].index].merged = true;
 
         urlFilter = urlFilter.substring(0, editIndex) + "(" +
                     urlFilter.substring(editIndex, editEndIndex) + ")?" +
                     urlFilter.substring(editEndIndex);
       }
 
       rule.trigger["url-filter"] = urlFilter;
 
       // Mark this rule as one that has had other rules merged into it.
       ruleInfo.mergedInto = true;
     }
   }
 }
 
 function mergeRulesByURLFilter(rulesInfo, exhaustive)
 {
-  return async(rulesInfo.map((ruleInfo, index) => () =>
+  return async(rulesInfo, (ruleInfo, index) => () =>
     findMatchesForRuleByURLFilter(rulesInfo, index, exhaustive)
-  ))
+  )
   .then(() => mergeCandidateRulesByURLFilter(rulesInfo));
 }
 
 function mergeRulesByArrayProperty(rulesInfo, propertyType, property)
 {
   if (rulesInfo.length <= 1)
     return;
 
-  let oneRuleInfo = rulesInfo.shift();
-  let valueSet = new Set(oneRuleInfo.rule[propertyType][property]);
-
-  for (let ruleInfo of rulesInfo)
-  {
-    if (ruleInfo.rule[propertyType][property])
-    {
-      for (let value of ruleInfo.rule[propertyType][property])
-        valueSet.add(value);
-    }
-
-    ruleInfo.merged = true;
+  let valueSet = new Set(rulesInfo[0].rule[propertyType][property]);
+
+  for (let i = 1; i < rulesInfo.length; i++)
+  {
+    for (let value of rulesInfo[i].rule[propertyType][property] || [])
+      valueSet.add(value);
+
+    rulesInfo[i].merged = true;
   }
 
   if (valueSet.size > 0)
-    oneRuleInfo.rule[propertyType][property] = Array.from(valueSet);
-
-  oneRuleInfo.mergedInto = true;
+    rulesInfo[0].rule[propertyType][property] = Array.from(valueSet);
+
+  rulesInfo[0].mergedInto = true;
 }
 
 function groupRulesByMergeableProperty(rulesInfo, propertyType, property)
 {
   let mergeableRulesInfoByGroup = new Map();
 
   for (let ruleInfo of rulesInfo)
   {
     let copy = {
       trigger: Object.assign({}, ruleInfo.rule.trigger),
@@ skipping 17 matching lines @@
 
 function mergeRules(rules, exhaustive)
 {
   let rulesInfo = rules.map(rule => ({rule}));
 
   let arrayPropertiesToMergeBy = ["resource-type", "if-domain"];
 
   return async(() =>
   {
     let map = groupRulesByMergeableProperty(rulesInfo, "trigger", "url-filter");
-    return async(Array.from(map.values()).map(mergeableRulesInfo => () =>
+    return async(map.values(), mergeableRulesInfo => () =>
       eliminateRedundantRulesByURLFilter(mergeableRulesInfo, exhaustive)
       .then(rulesInfo => mergeRulesByURLFilter(rulesInfo, exhaustive))
-    ))
+    )
     .then(() =>
     {
       // Filter out rules that are redundant or have been merged into other
       // rules.
       rulesInfo = rulesInfo.filter(ruleInfo => !ruleInfo.redundant &&
                                                !ruleInfo.merged);
     });
   })
-  .then(() => async(arrayPropertiesToMergeBy.map(arrayProperty => () =>
+  .then(() => async(arrayPropertiesToMergeBy, arrayProperty => () =>
   {
     let map = groupRulesByMergeableProperty(rulesInfo, "trigger",
                                             arrayProperty);
-    return async(Array.from(map.values()).map(mergeableRulesInfo => () =>
+    return async(map.values(), mergeableRulesInfo => () =>
       mergeRulesByArrayProperty(mergeableRulesInfo, "trigger", arrayProperty)
-    ))
+    )
     .then(() =>
     {
       rulesInfo = rulesInfo.filter(ruleInfo => !ruleInfo.merged);
     });
-  })))
+  }))
   .then(() => rulesInfo.map(ruleInfo => ruleInfo.rule));
 }
 
 let ContentBlockerList =
 /**
  * Create a new Adblock Plus filter to content blocker list converter
  *
  * @param {object} options Options for content blocker list generation
  *
  * @constructor
  */
-exports.ContentBlockerList = function(options)
+exports.ContentBlockerList = function (options)
 {
   const defaultOptions = {
     merge: "auto"
   };
 
   this.options = Object.assign({}, defaultOptions, options);
 
   this.requestFilters = [];
   this.requestExceptions = [];
   this.elemhideFilters = [];
   this.elemhideExceptions =  [];
+  this.genericblockExceptions = [];
+  this.generichideExceptions = [];
   this.elemhideSelectorExceptions = new Map();
 };
 
 /**
  * Add Adblock Plus filter to be converted
  *
  * @param {Filter} filter Filter to convert
  */
 ContentBlockerList.prototype.addFilter = function(filter)
 {
   if (filter.sitekeys)
     return;
   if (filter instanceof filterClasses.RegExpFilter &&
       filter.regexpSource == null)
     return;
 
   if (filter instanceof filterClasses.BlockingFilter)
     this.requestFilters.push(filter);
 
   if (filter instanceof filterClasses.WhitelistFilter)
   {
     if (filter.contentType & (typeMap.DOCUMENT | whitelistableRequestTypes))
       this.requestExceptions.push(filter);
 
-      if (filter.contentType & typeMap.ELEMHIDE)
-        this.elemhideExceptions.push(filter);
+    if (filter.contentType & typeMap.GENERICBLOCK)
+      this.genericblockExceptions.push(filter);
+
+    if (filter.contentType & typeMap.ELEMHIDE)
+      this.elemhideExceptions.push(filter);
+    else if (filter.contentType & typeMap.GENERICHIDE)
+      this.generichideExceptions.push(filter);
   }
 
   if (filter instanceof filterClasses.ElemHideFilter)
     this.elemhideFilters.push(filter);
 
   if (filter instanceof filterClasses.ElemHideException)
   {
     let domains = this.elemhideSelectorExceptions[filter.selector];
     if (!domains)
       domains = this.elemhideSelectorExceptions[filter.selector] = [];
 
     parseDomains(filter.domains, domains, []);
   }
 };
 
 /**
  * Generate content blocker list for all filters that were added
  */
 ContentBlockerList.prototype.generateRules = function()
 {
   let cssRules = [];
   let cssExceptionRules = [];
   let blockingRules = [];
   let blockingExceptionRules = [];
 
   let ruleGroups = [cssRules, cssExceptionRules,
                     blockingRules, blockingExceptionRules];
 
+  let genericSelectors = [];
   let groupedElemhideFilters = new Map();
+
   for (let filter of this.elemhideFilters)
   {
     let result = convertElemHideFilter(filter, this.elemhideSelectorExceptions);
     if (!result)
       continue;
 
     if (result.matchDomains.length == 0)
-      result.matchDomains = ["^https?://"];
-
-    for (let matchDomain of result.matchDomains)
-    {
-      let group = groupedElemhideFilters.get(matchDomain) || [];
-      group.push(result.selector);
-      groupedElemhideFilters.set(matchDomain, group);
-    }
-  }
+    {
+      genericSelectors.push(result.selector);
+    }
+    else
+    {
+      for (let matchDomain of result.matchDomains)
+      {
+        let group = groupedElemhideFilters.get(matchDomain) || [];
+        group.push(result.selector);
+        groupedElemhideFilters.set(matchDomain, group);
+      }
+    }
+  }
+
+  // Separate out the element hiding exceptions that have only a hostname part
+  // from the rest. This allows us to implement a workaround for issue #5345
+  // (WebKit bug #167423), but as a bonus it also reduces the number of
+  // generated rules. The downside is that the exception will only apply to the
+  // top-level document, not to iframes. We have to live with this until the
+  // WebKit bug is fixed in all supported versions of Safari.
+  // https://bugs.webkit.org/show_bug.cgi?id=167423
+  //
+  // Note that as a result of this workaround we end up with a huge rule set in
+  // terms of the amount of memory used. This can cause Node.js to throw
+  // "JavaScript heap out of memory". To avoid this, call Node.js with
+  // --max_old_space_size=4096
+  let elemhideExceptionDomains = extractFilterDomains(this.elemhideExceptions);
+
+  let genericSelectorExceptionDomains =
+    extractFilterDomains(this.generichideExceptions);
+  elemhideExceptionDomains.forEach(name =>
+  {
+    genericSelectorExceptionDomains.add(name);
+  });
+
+  addCSSRules(cssRules, genericSelectors, null,
+              genericSelectorExceptionDomains);
+
+  // Filter out whitelisted domains.
+  elemhideExceptionDomains.forEach(domain =>
+    groupedElemhideFilters.delete(domain));
 
   groupedElemhideFilters.forEach((selectors, matchDomain) =>
   {
-    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);
-
-      cssRules.push({
-        trigger: {"url-filter": matchDomain,
-                  "url-filter-is-case-sensitive": true},
-        action: {type: "css-display-none",
-                 selector: selector}
-      });
-    }
+    addCSSRules(cssRules, selectors, matchDomain, elemhideExceptionDomains);
   });
 
-  for (let filter of this.elemhideExceptions)
-  {
-    convertFilterAddRules(cssExceptionRules, filter,
-                          "ignore-previous-rules", false);
+  let requestFilterExceptionDomains = [];
+  for (let filter of this.genericblockExceptions)
+  {
+    let parsed = parseFilterRegexpSource(filter.regexpSource);
+    if (parsed.hostname)
+      requestFilterExceptionDomains.push(parsed.hostname);
   }
 
   for (let filter of this.requestFilters)
-    convertFilterAddRules(blockingRules, filter, "block", true);
+  {
+    convertFilterAddRules(blockingRules, filter, "block", true,
+                          requestFilterExceptionDomains);
+  }
 
   for (let filter of this.requestExceptions)
   {
     convertFilterAddRules(blockingExceptionRules, filter,
                           "ignore-previous-rules", true);
   }
 
-  return async(ruleGroups.map((group, index) => () =>
+  return async(ruleGroups, (group, index) => () =>
   {
     let next = () =>
     {
       if (index == ruleGroups.length - 1)
         return ruleGroups.reduce((all, rules) => all.concat(rules), []);
     };
 
-    ruleGroups[index] = ruleGroups[index].filter(rule => !hasNonASCI(rule));
-
     if (this.options.merge == "all" ||
         (this.options.merge == "auto" &&
          ruleGroups.reduce((n, group) => n + group.length, 0) > 50000))
     {
       return mergeRules(ruleGroups[index], this.options.merge == "all")
       .then(rules =>
       {
         ruleGroups[index] = rules;
         return next();
       });
     }
 
     return next();
-  }));
+  });
 };