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 348 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 closeMatch(s, t)
+{
+  // This function returns an edit operation, one of "substitute", "delete",

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

Mind using the JSDoc syntax for the comment explaining this function?

[Manish Jethani, 2017/05/08 23:12:48]

Done.

+  // 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.
+  //
+  // Deletions or insertions of a contiguous range of characters from one
+  // string into the other, at the same index, are treated as a single edit.
+  // For example, "internal" and "international" are considered to be one edit
+  // apart and therefore a close match.
+
+  // A few things to note:
+  //
+  //   1) This function does not care about the format of the input strings.
+  //   For example, the caller may pass in regular expressions, where "[ab]"
+  //   and "[bc]" could be considered to be a close match, since the order
+  //   within the brackets doesn't matter. This function will still return null
+  //   for this set of inputs since they are two edits apart.
+  //
+  //   2) To be friendly to calling code that might be passing in regular
+  //   expressions, this function will simply return null if it encounters a
+  //   special character (e.g. "\", "?", "+", etc.) in the delta. For example,
+  //   given "Hello" and "Hello, how are you?", it will return null.
+  //
+  //   3) If the caller does indeed pass in regular expressions, it must make
+  //   the important assumption that the parts where two such regular
+  //   expressions may differ can always be treated as normal strings. For
+  //   example, "^https?://.*/ads" and "^https?://.*/adv" differ only in the
+  //   last character, therefore the regular expressions can safely be merged
+  //   into "^https?://.*/ad[sv]".
+
+  let diff = s.length - t.length;
+
+  // 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 i = 0, j = 0;
+
+  for (; i < s.length; i++)
+  {
+    if (s[i] != t[i])
+      break;
+  }
+
+  for (; j < t.length; j++)
+  {
+    if (t.length - j == i || s[s.length - j - 1] != t[t.length - j - 1])

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

I find this part hard to grok, could you add a comment?

[Manish Jethani, 2017/05/08 23:12:48]

Done.

+      break;
+  }
+
+  if (diff == 0)
+  {
+    if (t.length - j - i != 1)
+      return null;
+  }
+  else if (i != t.length - j)
+  {
+    return null;
+  }
+
+  for (let k = i; k < s.length - j; k++)
+  {
+    // If there are any special characters in the delta, bail.

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

Nit: IMO this comment doesn't add much.

[Manish Jethani, 2017/05/08 23:12:48]

I'm slightly rephrasing here, but since I've added comments all over the
function now, I'll leave this here.

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

Fair enough. Thanks for those extra comments, they helped me grok the algorithm.

+    if (s[k] == "." || s[k] == "+" || s[k] == "$" || s[k] == "?" ||
+        s[k] == "{" || s[k] == "}" || s[k] == "(" || s[k] == ")" ||
+        s[k] == "[" || s[k] == "]" || s[k] == "\\")
+      return null;
+  }
+
+  if (diff == 0)
+  {
+    edit = {type: "substitute", index: i};
+  }
+  else if (diff > 0)
+  {
+    edit = {type: "delete", index: i};
+
+    if (diff > 1)
+      edit.endIndex = s.length - j;
+  }
+  else
+  {
+    edit = {type: "insert", index: i};
+
+    if (diff < -1)
+      edit.endIndex = s.length - j;
+  }
+
+  return edit;
+}
+
+function eliminateRedundantRulesByURLFilter(rulesInfo)
+{
+  for (let i = 0; i < rulesInfo.length; i++)
+  {
+    // If this rule is already marked as redundant, don't bother comparing it
+    // with other rules.
+    if (rulesInfo[i].redundant)
+      continue;
+
+    for (let j = i + 1; j < rulesInfo.length; j++)
+    {
+      if (rulesInfo[j].redundant)
+        continue;
+
+      let source = rulesInfo[i].rule.trigger["url-filter"];
+      let target = rulesInfo[j].rule.trigger["url-filter"];
+
+      if (source.length >= target.length)
+      {
+        // If one URL filter is a substring of the other starting at the
+        // beginning, the other one is clearly redundant.
+        if (source.substring(0, target.length) == target)
+        {
+          rulesInfo[i].redundant = true;
+          break;
+        }
+      }
+      else if (target.substring(0, source.length) == source)
+      {
+        rulesInfo[j].redundant = true;
+      }
+    }
+  }
+
+  return rulesInfo.filter(ruleInfo => !ruleInfo.redundant);
+}
+
+function mergeRulesByURLFilter(rulesInfo, exhaustive)
+{
+  // 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 = 10;

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

Could you mention about the behaviour (or lack thereof) of heursiticRange when
exhaustive is true in this comment?

[Manish Jethani, 2017/05/08 23:12:48]

Done.

+
+  if (exhaustive)
+    // Throw out obviously redundant rules.

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

Nit: Please surround with braces since it spans multiple lines.

[Manish Jethani, 2017/05/08 23:12:48]

Done.

+    rulesInfo = eliminateRedundantRulesByURLFilter(rulesInfo);
+
+  if (rulesInfo.length <= 1)
+    return;
+
+  for (let i = 0; i < rulesInfo.length; i++)
+  {
+    let limit = exhaustive ? rulesInfo.length :
+                Math.min(i + heuristicRange, rulesInfo.length);
+
+    for (let j = i + 1; j < limit; j++)
+    {
+      let source = rulesInfo[i].rule.trigger["url-filter"];
+      let target = rulesInfo[j].rule.trigger["url-filter"];
+
+      let edit = closeMatch(source, target);
+
+      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.
+          urlFilter = target;
+          ruleInfo = rulesInfo[j];
+          match.index = i;
+          edit.type = "delete";
+        }
+        else
+        {
+          urlFilter = source;
+          ruleInfo = rulesInfo[i];
+          match.index = j;
+        }
+
+        // If the edit has an end index, it represents a multiple character
+        // edit.
+        let multiEdit = !!edit.endIndex;
+
+        if (multiEdit)
+        {
+          // We only care about a single multiple character edit because the
+          // number of characters for such a match doesn't matter, we can
+          // only merge with one other rule.
+          if (!ruleInfo.multiEditMatch)
+            ruleInfo.multiEditMatch = match;
+        }
+        else
+        {
+          // For single character edits, multiple rules can be merged into
+          // one. e.g. "ad", "ads", and "adv" can be merged into "ad[sv]?".
+          if (!ruleInfo.matches)
+            ruleInfo.matches = new Array(urlFilter.length);
+
+          // Matches at a particular index. For example, for a source string
+          // "ads", both target strings "ad" (deletion) and "adv"
+          // (substitution) match at index 2, hence they are grouped together
+          // to possibly be merged later into "ad[sv]?".
+          let matchesForIndex = ruleInfo.matches[edit.index];
+
+          if (matchesForIndex)
+          {
+            matchesForIndex.push(match);
+          }
+          else
+          {
+            matchesForIndex = [match];
+            ruleInfo.matches[edit.index] = matchesForIndex;
+          }
+
+          // Keep track of the best set of matches. We later sort by this to
+          // get best results.
+          if (!ruleInfo.bestMatches ||
+              matchesForIndex.length > ruleInfo.bestMatches.length)
+            ruleInfo.bestMatches = matchesForIndex;
+        }
+      }
+    }
+  }
+
+  // Filter out rules that have no matches at all.
+  let candidateRulesInfo = rulesInfo.filter(ruleInfo =>
+  {
+    return ruleInfo.bestMatches || ruleInfo.multiEditMatch
+  });
+
+  // For best results, we have to sort the candidates by the largest set of
+  // matches.
+  //
+  // For example, we want "ads", "bds", "adv", "bdv", "adx", and "bdx" to
+  // generate "ad[svx]" and "bd[svx]" (2 rules), not "[ab]ds", "[ab]dv", and
+  // "[ab]dx" (3 rules).
+  candidateRulesInfo.sort((ruleInfo1, ruleInfo2) =>
+  {
+    let weight1 = ruleInfo1.bestMatches ? ruleInfo1.bestMatches.length :
+                  ruleInfo1.multiEditMatch ? 1 : 0;
+    let weight2 = ruleInfo2.bestMatches ? ruleInfo2.bestMatches.length :
+                  ruleInfo2.multiEditMatch ? 1 : 0;
+
+    return weight2 - weight1;
+  });
+
+  for (let ruleInfo of candidateRulesInfo)
+  {
+    let rule = ruleInfo.rule;
+
+    // If this rule has already been merged into another rule, we skip it.
+    if (ruleInfo.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 !rulesInfo[match.index].merged &&
+               !rulesInfo[match.index].mergedInto;
+      });
+
+      return matchesForIndex.length > best.length ? matchesForIndex : best;
+    },
+    []);
+
+    let multiEdit = false;
+
+    // If we couldn't find a single rule to merge with, let's see if we have a
+    // multiple character edit. e.g. we could merge "ad" and "adserver" into
+    // "ad(server)?".
+    if (best.length == 0 && ruleInfo.multiEditMatch &&
+        !rulesInfo[ruleInfo.multiEditMatch.index].merged &&
+        !rulesInfo[ruleInfo.multiEditMatch.index].mergedInto)
+    {
+      best = [ruleInfo.multiEditMatch];
+      multiEdit = true;
+    }
+
+    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 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);
+          }
+
+          // 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)
+        {
+          urlFilter = urlFilter.substring(0, editIndex) + "[" +
+                      urlFilter[editIndex] + 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 mergeRulesByArrayProperty(rulesInfo, propertyType, property)
+{
+  if (rulesInfo.length <= 1)
+    return;
+
+  let set = new Set();
+
+  rulesInfo.forEach((ruleInfo, index) =>
+  {
+    if (ruleInfo.rule[propertyType][property])
+    {
+      for (let value of ruleInfo.rule[propertyType][property])
+        set.add(value);
+    }
+
+    if (index > 0)
+      ruleInfo.merged = true;
+  });
+
+  if (set.size > 0)
+    rulesInfo[0].rule[propertyType][property] = Array.from(set);
+
+  rulesInfo[0].mergedInto = true;
+}
+
+function groupRulesByMergeableProperty(rulesInfo, propertyType, property)
+{
+  let mergeableRulesInfoByGroup = new Map();
+
+  rulesInfo.forEach(ruleInfo =>
+  {
+    let copy = {
+      trigger: Object.assign({}, ruleInfo.rule.trigger),
+      action: Object.assign({}, ruleInfo.rule.action)
+    };
+
+    delete copy[propertyType][property];
+
+    let groupKey = JSON.stringify(copy);
+
+    let mergeableRulesInfo = mergeableRulesInfoByGroup.get(groupKey);
+
+    if (mergeableRulesInfo)
+      mergeableRulesInfo.push(ruleInfo);
+    else
+      mergeableRulesInfoByGroup.set(groupKey, [ruleInfo]);
+  });
+
+  return mergeableRulesInfoByGroup;
+}
+
+function mergeRules(rules, options)
+{
+  const defaultOptions = {exhaustive: false};
+
+  options = Object.assign({}, defaultOptions, options);
+
+  let rulesInfo = rules.map(rule => ({rule}));

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

What's the purpose of this line?

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

The purpose of this line is to create one "ruleInfo" object for each rule, where
the ruleInfo object has one property, "rule", pointing to the rule it belongs
to.

Essentially this:

let rulesInfo = new Array(rules.length);
for (let i = 0; i < rules.length; i++)
  rulesInfo[i] = {rule: rule};

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

Argh, sorry that was an especially dumb question. In my defence a cat jumped on
my head at 4am that morning, I couldn't get back to sleep and was kind of dazed
all day!

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

Haha, no worries :)

+
+  groupRulesByMergeableProperty(rulesInfo, "trigger", "url-filter")
+  .forEach(mergeableRulesInfo =>

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

Any reason you used forEach instead of for ... of ... here (and below)? We
prefer the latter unless there's a good reason.

Oh, there is one problem with that though, the JS Hydra transpiler produces code
that evaluates the right hand part of for ... of ... loops for each iteration.
So bear that in mind if you do use those, we often assigned the value to a
variable first to avoid expensive operations from being performed repeatedly!

[Manish Jethani, 2017/05/08 14:04:00]

It was for (let value of map.values()) { ... } at first, but as you said JS
Hydra can't handle non-array iterables. It looks for the length property on the
iterable, trying to convert this into a regular for loop with an index.

i.e. for (let i = 0; i < map.values().length; i++) { let value =
map.values()[i]; ... }

The only other way to do this is:

let mapValues = Array.from(map.values());
for (let value of mapValues) { ... }

If we simply call the forEach method on the map object, that does the job as
well, without creating another intermediate array. I thought this was better
because these intermediate arrays would again take up more memory.

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

Well groupRulesByMergeableProperty creates the array either way, so assuming you
didn't keep a reference to that after the second array is created I don't see
that it would use more memory. That said I don't care too much and IMO this is a
pretty reasonable use of forEach.

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

The intermediate array here would an array of the arrays created inside
groupRulesByMergeableProperty.

Since you brought this up, I noticed that we're using a forEach in that function
itself where we could use for..of. I've changed it now both in
groupRulesByMergeableProperty and mergeRulesByArrayProperty.

+  {
+    if (mergeableRulesInfo.length > 1)
+      mergeRulesByURLFilter(mergeableRulesInfo, options.exhaustive);
+  });
+
+  // Filter out rules that are redundant or have been merged into other rules.
+  rulesInfo = rulesInfo.filter(ruleInfo => !ruleInfo.redundant &&
+                                           !ruleInfo.merged);
+
+  for (let arrayProperty of ["resource-type", "if-domain"])
+  {
+    groupRulesByMergeableProperty(rulesInfo, "trigger", arrayProperty)
+    .forEach(mergeableRulesInfo =>

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

This logic seems pretty much the same as above, I wonder if we could avoid
duplicating it somehow?

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

I suppose we could merge them into one, but then we'd end up with an if...else
or a function lookup inside that loop. They're also sufficiently different that
I thought it made sense to keep them separate. The first one is really
expensive, the second one is relatively very cheap.

I could still merge them if you feel like that would be better. We'll also have
to check performance again. I've found making small changes can hurt performance
in a big way.

For example, this:

obj[flag ? "prop1" : "prop2"] = value;

Is way, way slower than this:

if (flag)
  obj.prop1 = value;
else
  obj.prop2 = value;

For whatever reason.

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

Acknowledged.

+    {
+      if (mergeableRulesInfo.length > 1)
+        mergeRulesByArrayProperty(mergeableRulesInfo, "trigger", arrayProperty);
+    });
+
+    rulesInfo = rulesInfo.filter(ruleInfo => !ruleInfo.merged);

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

Maybe a dumb question, but instead of setting the merged or redundant property
on ruleInfo Objects and then filtering those away couldn't we just delete them
immediately instead?

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

I could try that, but then we'd have to adjust the indexes i and j every time we
delete something from the array. Also deleting individual elements from an array
should be way more expensive than marking them first and then filtering them out
later using the filter method.

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

Acknowledged.

+  }
+
+  return rulesInfo.map(ruleInfo => ruleInfo.rule);
+}
+
 let ContentBlockerList =
 /**
  * Create a new Adblock Plus filter to content blocker list converter
  *
  * @constructor
  */
 exports.ContentBlockerList = function ()
 {
   this.requestFilters = [];
   this.requestExceptions = [];
@@ skipping 38 matching lines @@
 
     parseDomains(filter.domains, domains, []);
   }
 };
 
 /**
  * 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(options)
 {
+  const defaultOptions = {
+    merge: false,
+    exhaustiveMerge: false
+  };
+
+  options = Object.assign({}, defaultOptions, options);
+
   let rules = [];
 
   let groupedElemhideFilters = new Map();
   for (let filter of this.elemhideFilters)
   {
     let result = convertElemHideFilter(filter, this.elemhideSelectorExceptions);
     if (!result)
       continue;
 
     if (result.matchDomains.length == 0)
@@ skipping 26 matching lines @@
     }
   });
 
   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 (options.merge)
+  {
+    let mergeOptions = {

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

Couldn't you just pass options.exhaustiveMerge straight through instead of
putting it inside this Object?

Also wouldn't it make more sense to take the merging options in the constructor
instead of this method? I think the defaultOptions logic above looks especially
out of place here.

[Manish Jethani, 2017/05/08 23:12:48]

Done.

+      exhaustive: options.exhaustiveMerge
+    };
+
+    rules = mergeRules(rules, mergeOptions);
+  }
+
+  return rules;
 };