Issue 3673 - Merge closely matching rules

lib/abp2blocklist.js

Index: lib/abp2blocklist.js
===================================================================
--- a/lib/abp2blocklist.js
+++ b/lib/abp2blocklist.js
@@ -361,16 +361,310 @@
     newSelector.push('[id=', selector.substring(pos.start + 1, pos.end), ']');
     i = pos.end;
   }
   newSelector.push(selector.substring(i));
 
   return newSelector.join("");
 }
 
+function closeMatch(s, t, {multi = false} = {})

[kzar, 2017/05/03 11:17:24]

I've not seen this syntax before `{multi = false} = {}` could you explain?

[Manish Jethani, 2017/05/03 14:41:54]

This:

  function func(param1, param2, {option1 = false} = {})
  {
    ...
  }

Is the equivalent of this:

  function func(param1, param2, options)
  {
    let option1 = false;

    if (options && options.option1 !== undefined) // Note: strict equality
      option1 = options.option1;

    ...
  }

It's part of the ES6 standard.

http://2ality.com/2015/01/es6-destructuring.html#simulating-named-parameters-...

The idea is that a function will take a list of parameters that are strictly
required for it to do its job, and then a bunch of options. The list of options
can keep growing over time. Here they can be added in a backwards compatible way
without much fuss. This is a common pattern in JavaScript.

[kzar, 2017/05/03 15:19:04]

Acknowledged.

+{
+  // This function returns an edit operation (one of "substitute", "delete",
+  // and "insert") along with an index in the source string where the edit
+  // should occur in order to arrive at the target string.
+
+  let diff = s.length - t.length;
+
+  // If the string lenghts differ by more than one character, we cannot arrive

[kzar, 2017/05/03 11:17:24]

Nit: Typo "lenghts".

[Manish Jethani, 2017/05/04 02:49:32]

Done.

+  // at target from source in a single edit operation.
+  if (!multi && (diff < -1 || diff > 1))
+    return null;
+
+  // If target is longer than source, swap them for the purpose of our
+  // calculation.
+  if (diff < 0)
+  {
+    let tmp = s;
+    s = t;
+    t = tmp;
+  }
+
+  let edit = null;
+  let multiEdit = false;
+
+  let j = 0;
+
+  for (let i = 0; i < s.length; i++)
+  {
+    if (s[i] == t[j])
+    {
+      j++;
+
+      if (edit && multiEdit && !edit.closeIndex)
+        edit.closeIndex = i;
+    }
+    else if (edit && (!multi || diff == 0 || edit.closeIndex))
+    {
+      // Since we want one and only one edit operation, we must bail here.
+      return null;
+    }
+    else if ((s[i] == "." || s[i] == "+" || s[i] == "$" || s[i] == "?" ||
+              s[i] == "{" || s[i] == "}" || s[i] == "(" || s[i] == ")" ||
+              s[i] == "[" || s[i] == "]" || s[i] == "\\") ||
+             (t[j] == "." || t[j] == "+" || t[j] == "$" || t[j] == "?" ||
+              t[j] == "{" || t[j] == "}" || t[j] == "(" || t[j] == ")" ||
+              t[j] == "[" || t[j] == "]" || t[j] == "\\"))
+    {
+      // We don't deal with special characters for now.

[kzar, 2017/05/03 11:17:24]

So we skip special characters in the url-filter regexp, but I wonder if that's
enough to avoid messing up regexps. For example

s = "[ab]"
b = "[bc]"

Wouldn't we end up with "[abc]"?

I'm not sure if things like that are a problem in practice though, what do you
think?

[Manish Jethani, 2017/05/03 14:41:54]

The above is not a good example because this is not even supported. The "edit
distance" (Levenshtein distance) between the two is greater than 1. It's going
to treat the above two inputs as "not close matches".

However let's take this one: "[ab]" and "[ac]". It's going to mess up and give
you "[a[bc]]".

I thought of supporting this, but then I decided against it after looking at the
actual values for the URL filters. There is not a single instance of this case.
The code right now makes the assumption that this never occurs in the input.

The ignoring of special characters is more for when the character appears as a
literal in the original filter. For example, "foo.com/?ad" becomes
"^https?://foo\.com/\?ad", and we just don't want to deal with the "?" because
it is escaped (which means we really have to consider the preceding backslash
with it, and that would complicate things).

[kzar, 2017/05/03 15:19:04]

Maybe add a comment explaining that assumption?

[Manish Jethani, 2017/05/04 02:49:32]

Added a comment to explain this.

+      return null;
+    }
+    else
+    {
+      if (diff == 0)

[kzar, 2017/05/03 11:17:24]

Nit: Couldn't this be an `else if` too?

[Manish Jethani, 2017/05/04 02:49:32]

Done.

+      {
+        // If both strings are equal in length, this is a substitution.
+        edit = {type: "substitute", index: i};
+        j++;
+      }
+      else
+      {
+        if (edit)
+          multiEdit = true;
+        else if (diff > 0)

[kzar, 2017/05/03 11:17:24]

Nit: Please use braces since the clause spans multiple lines.

[Manish Jethani, 2017/05/04 02:49:32]

Done.

+          // If the source string is longer, this is a deletion.
+          edit = {type: "delete", index: i};
+        else
+          edit = {type: "insert", index: i};
+      }
+    }
+  }
+
+  if (edit && multiEdit && !edit.closeIndex)
+  {
+    if (j < t.length)
+      return null;
+
+    edit.closeIndex = s.length;
+  }
+
+  return edit;
+}
+
+function ruleWithoutURLFilter(rule)
+{
+  let copy = {

[kzar, 2017/05/03 15:19:04]

How about `return Object.create(rule, {"url-filter": {value: undefined}});`

[Manish Jethani, 2017/05/04 02:49:31]

That would not work for multiple reasons, but most notably because "url-filter"
is a property of rule.trigger, not rule itself.

The other reason is that an object created that way has no own, enumerable
properties, therefore the stringified version is "{}".

+    trigger: Object.assign({}, rule.trigger),
+    action: Object.assign({}, rule.action)
+  };
+
+  delete copy.trigger["url-filter"];
+
+  return copy;
+}
+
+function mergeCloselyMatchingRules(rules, {multi = false} = {})
+{
+  // Closely matching rules are likely to be within a certain range. We only
+  // look for matches within this range. If we increase this value, it can give
+  // us more matches and a smaller resulting rule set, but possibly at a
+  // significant performance cost.
+  const heuristicRange = 100;

[kzar, 2017/05/03 15:19:04]

Since the code either runs in a place where speed really matters, or where it
doesn't matter at all, perhaps we should change this and the multi option?

I was thinking "multi" could be renamed "slow" or something like that. If slow's
true then match multiple character changes and have no heuristicRange limit. We
could perhaps use the option to make other decisions in the future too, if we
think of other ways to process the rules.

[Manish Jethani, 2017/05/04 02:49:32]

In the latest update the generateRules function takes both general options like
fastMerge and more specific options like advancedMerge (experimental or slow
stuff) and exhaustiveMerge (test every rule against every other rule). If fast
is true, it'll skip both these; if set to false, it'll be as experimental and as
slow as it can (but you can still turn off individual settings).

+
+  let rulesInfo = new Array(rules.length);
+
+  rules.forEach((rule, index) =>
+  {
+    rulesInfo[index] = {rule};

[kzar, 2017/05/03 11:17:24]

I'm not sure syntax like this will work for Safari 9 :(

[Manish Jethani, 2017/05/03 14:41:54]

I'll check, but if it doesn't work then I'll have to change this in a few
places.

[kzar, 2017/05/08 08:13:02]

You mentioned testing the code on Safari now, but unless I missed it not the
version. Which version did you test with?

[Manish Jethani, 2017/05/08 14:03:58]

I've been testing with Safari 10.

Anyway, this is not a problem because JS Hydra transpiles {rule} into {rule:
rule}.

[kzar, 2017/05/09 10:05:46]

I think you should test with Safari 9 at least once to make sure it still works.
If you don't have a access to a copy you can us our test machines from
https://app.webmate.io/

[Manish Jethani, 2017/05/09 15:52:46]

"{rule: rule}" ought to work in every single JS engine in existence. It makes
sense to test everything out in Safari 9 though, I'll do that and get back with
the results.

+
+    if (rule.action.type == "ignore-previous-rules")
+    {
+      rulesInfo[index].skip = true;
+    }
+    else
+    {
+      // Save a stringified version of the rule, but without the URL filter. We
+      // use this for comparison later.
+      rulesInfo[index].stringifiedWithoutURLFilter =
+        JSON.stringify(ruleWithoutURLFilter(rule));
+    }
+  });
+
+  for (let i = 0; i < rules.length; i++)
+  {
+    if (rulesInfo[i].skip)
+      continue;
+
+    for (let j = i + 1; j < i + heuristicRange && j < rules.length; j++)
+    {
+      if (rulesInfo[j].skip)
+        continue;
+
+      // Check if the rules are identical except for the URL filter.
+      if (rulesInfo[i].stringifiedWithoutURLFilter ==

[kzar, 2017/05/03 15:19:04]

I wonder if we could create a lookup table stringifiedWithoutURLFilter =>
[ruleInfo] instead?

[Manish Jethani, 2017/05/04 02:49:32]

I'm not sure what the benefit of that would be.

We have two ruleInfo objects, and we want to find out if they're identical
except for the URL filter. Now it's as simple as a string comparison. I actually
tried the lookup table approach (we don't even need to store an array there,
just an empty object), it is significantly slower.

But you give me a good idea: compare hashes instead. I just take the first 32
bits of the SHA-1 hash of the string, and it makes it more than 10% faster.

+          rulesInfo[j].stringifiedWithoutURLFilter)
+      {
+        let source = rules[i].trigger["url-filter"];
+        let target = rules[j].trigger["url-filter"];
+
+        let edit = closeMatch(source, target, {multi});
+
+        if (edit)
+        {
+          let urlFilter, ruleInfo, match = {edit};
+
+          if (edit.type == "insert")
+          {
+            // Convert the insertion into a deletion and stick it on the target
+            // rule instead. We can only group deletions and substitutions;
+            // therefore insertions must be treated as deletions on the target
+            // rule, to be dealt with later.
+            urlFilter = target;
+            ruleInfo = rulesInfo[j];
+            match.index = i;
+            edit.type = "delete";
+          }
+          else
+          {
+            urlFilter = source;
+            ruleInfo = rulesInfo[i];
+            match.index = j;
+          }
+
+          if (edit.closeIndex)
+          {
+            if (!ruleInfo.multiEditMatch)
+              ruleInfo.multiEditMatch = match;
+          }
+          else
+          {
+            if (!ruleInfo.matches)
+              ruleInfo.matches = new Array(urlFilter.length + 1);
+
+            let matchesForIndex = ruleInfo.matches[edit.index];
+
+            if (matchesForIndex)
+            {
+              matchesForIndex.push(match);
+            }
+            else
+            {
+              matchesForIndex = [match];
+              ruleInfo.matches[edit.index] = matchesForIndex;
+            }
+
+            if (!ruleInfo.bestMatches ||
+                matchesForIndex.length > ruleInfo.bestMatches.length)
+              ruleInfo.bestMatches = matchesForIndex;
+          }
+        }
+      }
+    }
+  }
+
+  let candidateRulesInfo = rulesInfo.filter(ruleInfo => ruleInfo.bestMatches ||
+                                                        ruleInfo.multiEditMatch);

[kzar, 2017/05/03 11:17:24]

Nit: Long line.

[Manish Jethani, 2017/05/04 02:49:31]

Done.

+
+  // For best results, we have to sort the candidates by the number of matches.
+  // For example, we want "ads", "bds", "adv", "bdv", and "bdx" to generate
+  // "ad[sv]" and "bd[svx]" (2 rules), not "[ab]ds", "[ab]dv", and "bdx" (3
+  // rules).
+  candidateRulesInfo.sort((ruleInfo1, ruleInfo2) =>
+  {
+    let weight1 = 1;
+    let weight2 = 1;
+
+    if (ruleInfo1.bestMatches)
+      weight1 = ruleInfo1.bestMatches.length;
+
+    if (ruleInfo2.bestMatches)
+      weight2 = ruleInfo2.bestMatches.length;
+
+    return weight2 - weight1;
+  });
+
+  for (let ruleInfo of candidateRulesInfo)
+  {
+    let rule = ruleInfo.rule;
+
+    if (rule._merged)
+      continue;
+
+    // Find the best set of rules to group, which is simply the largest set.
+    let best = (ruleInfo.matches || []).reduce((best, matchesForIndex) =>
+    {
+      matchesForIndex = (matchesForIndex || []).filter(match =>
+      {
+        // Filter out rules that have either already been merged into other
+        // rules or have had other rules merged into them.
+        return !rules[match.index]._merged &&
+               !rulesInfo[match.index].mergedInto;
+      });
+
+      return matchesForIndex.length > best.length ? matchesForIndex : best;
+    },
+    []);
+
+    if (best.length == 0 && ruleInfo.multiEditMatch &&
+        !rules[ruleInfo.multiEditMatch.index]._merged &&
+        !rulesInfo[ruleInfo.multiEditMatch.index].mergedInto)
+      best = [ruleInfo.multiEditMatch];
+
+    if (best.length > 0)
+    {
+      let urlFilter = rule.trigger["url-filter"];
+
+      let editIndex = best[0].edit.index;
+
+      if (best[0] != ruleInfo.multiEditMatch)
+      {
+        // Merge all the matching rules into this one.
+
+        let characters = [];
+        let quantifier = "";
+
+        for (let match of best)
+        {
+          if (match.edit.type == "delete")
+            quantifier = "?";
+          else
+            characters.push(rules[match.index].trigger["url-filter"][editIndex]);
+
+          rules[match.index]._merged = true;
+        }
+
+        urlFilter = urlFilter.substring(0, editIndex + 1) + quantifier +
+                    urlFilter.substring(editIndex + 1);
+        if (characters.length > 0)
+        {
+          urlFilter = urlFilter.substring(0, editIndex) + "[" +
+                      urlFilter[editIndex] + characters.join("") + "]" +
+                      urlFilter.substring(editIndex + 1);
+        }
+      }
+      else
+      {
+        let editCloseIndex = best[0].edit.closeIndex;
+
+        rules[best[0].index]._merged = true;
+
+        urlFilter = urlFilter.substring(0, editIndex) + "(" +
+                    urlFilter.substring(editIndex, editCloseIndex) + ")?" +
+                    urlFilter.substring(editCloseIndex);
+      }
+
+      rule.trigger["url-filter"] = urlFilter;
+
+      ruleInfo.mergedInto = true;
+    }
+  }
+
+  return rules.filter(rule => !rule._merged);
+}
+
 let ContentBlockerList =
 /**
  * Create a new Adblock Plus filter to content blocker list converter
  *
  * @constructor
  */
 exports.ContentBlockerList = function ()
 {
@@ -419,17 +713,18 @@
   }
 };
 
 /**
  * Generate content blocker list for all filters that were added
  *
  * @returns   {Filter}   filter    Filter to convert
  */
-ContentBlockerList.prototype.generateRules = function(filter)
+ContentBlockerList.prototype.generateRules = function(
+  {merge = false, multiMerge = false} = {})
 {
   let rules = [];
 
   let groupedElemhideFilters = new Map();
   for (let filter of this.elemhideFilters)
   {
     let result = convertElemHideFilter(filter, this.elemhideSelectorExceptions);
     if (!result)
@@ -467,10 +762,15 @@
 
   for (let filter of this.elemhideExceptions)
     convertFilterAddRules(rules, filter, "ignore-previous-rules", false);
   for (let filter of this.requestFilters)
     convertFilterAddRules(rules, filter, "block", true);
   for (let filter of this.requestExceptions)
     convertFilterAddRules(rules, filter, "ignore-previous-rules", true);
 
-  return rules.filter(rule => !hasNonASCI(rule));
+  rules = rules.filter(rule => !hasNonASCI(rule));
+
+  if (merge)
+    rules = mergeCloselyMatchingRules(rules, {multi: multiMerge});
+
+  return rules;
 };