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
@@ skipping 44 matching lines @@
 
     // 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.
@@ skipping 38 matching lines @@
     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
@@ skipping 431 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, matchDomain, exceptionDomains)
+function addCSSRules(rules, selectors, domain, exceptionDomains)
 {
   let unlessDomain = exceptionDomains.size > 0 ? [] : null;
 
-  exceptionDomains.forEach(name => unlessDomain.push("*" + name));
+  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,
+      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);
   }
@@ skipping 122 matching lines @@
   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 200 matching lines @@
       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 valueSet = new Set(rulesInfo[0].rule[propertyType][property]);
 
@@ skipping 39 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 => () =>

[kzar, 2017/07/25 12:18:53]

If async always took a sequence as the first argument, then we wouldn't need to
convert map.values() into an Array from an iterator here which I think might
reduce memory usage. We could also remove the related logic from the start of
async. Perhaps we should do that and then simply wrap the first argument in an
Array literal when necessary?

[Manish Jethani, 2017/07/28 09:17:36]

That's a good suggestion.

If the async function takes any iterable, it would also have to map the values
lazily. I've modified it now so that it takes a second argument, a map function,
which it calls on the callee value to get the actual callee. The mapping happens
just before the asynchronous function call.

I've left the logic to convert a non-iterable first argument into an iterable
(array) because it makes the calling code neater. It's not expensive because the
async function itself is not called too many times, it's just called with large
arrays/sets of functions.

+    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
@@ skipping 109 matching lines @@
   // --max_old_space_size=4096
   let elemhideExceptionDomains = extractFilterDomains(this.elemhideExceptions);
 
   let genericSelectorExceptionDomains =
     extractFilterDomains(this.generichideExceptions);
   elemhideExceptionDomains.forEach(name =>
   {
     genericSelectorExceptionDomains.add(name);
   });
 
-  addCSSRules(cssRules, genericSelectors, "^https?://",
+  addCSSRules(cssRules, genericSelectors, null,
               genericSelectorExceptionDomains);
+
+  // Filter out whitelisted domains.
+  elemhideExceptionDomains.forEach(domain =>
+    groupedElemhideFilters.delete(domain));
 
   groupedElemhideFilters.forEach((selectors, matchDomain) =>
   {
     addCSSRules(cssRules, selectors, matchDomain, elemhideExceptionDomains);
   });
 
   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,
                           requestFilterExceptionDomains);
   }
 
   for (let filter of this.requestExceptions)
+  {
     convertFilterAddRules(blockingExceptionRules, filter,

[kzar, 2017/07/25 12:18:53]

Nit: Please use braces for this for loop since it spans multiple lines now.

[Manish Jethani, 2017/07/28 09:17:36]

Done.

                           "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), []);
     };
 
     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();
-  }));
+  });
 };