Issue 3673 - Merge closely matching rules

test/abp2blocklist.js

Index: test/abp2blocklist.js
===================================================================
--- a/test/abp2blocklist.js
+++ b/test/abp2blocklist.js
@@ -15,19 +15,20 @@
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 let Filter = require("filterClasses").Filter;
 let ContentBlockerList = require("../lib/abp2blocklist.js").ContentBlockerList;
 
-function testRules(test, filters, expected, transformFunction)
+function testRules(test, filters, expected, transformFunction,
+                   {merge = false, exhaustiveMerge = false} = {})
 {
-  let blockerList = new ContentBlockerList();
+  let blockerList = new ContentBlockerList({merge, exhaustiveMerge});
   for (let filter of filters)
     blockerList.addFilter(Filter.fromText(filter));
 
   let rules = blockerList.generateRules();
   if (transformFunction)
     rules = transformFunction(rules);
 
   test.deepEqual(rules, expected);
@@ -226,10 +227,140 @@
   testUnicode: function(test)
   {
     testRules(test, ["$domain=🐈.cat"], ["xn--zn8h.cat", "www.xn--zn8h.cat"],
               rules => rules[0]["trigger"]["if-domain"]);
     testRules(test, ["🐈$domain=🐈.cat"], []);
     testRules(test, ["###🐈"], []);
 
     test.done();
+  },
+
+  testMerging: function(test)
+  {
+    // Single character substitutions, deletions, and insertions.
+    testRules(test, ["/ads", "/adv"], ["^https?://.*/ad[sv]"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ad", "/ads"], ["^https?://.*/ads?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/ad"], ["^https?://.*/ads?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/adv", "/ad"], ["^https?://.*/ad[sv]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ad", "/ads", "/adv"], ["^https?://.*/ad[sv]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/ad", "/adv"], ["^https?://.*/ad[sv]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/a", "/ad", "/ads", "/adv"],
+              ["^https?://.*/a", "^https?://.*/ad[sv]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ad", "/a", "/ads", "/adv"],
+              ["^https?://.*/a", "^https?://.*/ad[sv]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/adv", "/ad", "/a"],
+              ["^https?://.*/ad[sv]?", "^https?://.*/a"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/adv", "/a", "/ad"],
+              ["^https?://.*/ad[sv]?", "^https?://.*/a"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ad", "/a", "/ads", "/adv", "/adx"],
+              ["^https?://.*/a", "^https?://.*/ad[svx]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/a", "/ad", "/adv", "/adx"],
+              ["^https?://.*/ad[svx]?", "^https?://.*/a"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+
+    // Multiple character deletions and insertions.
+    testRules(test, ["/ad", "/adxsi"],
+              ["^https?://.*/ad(xsi)?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adxsi", "/xsi"],
+              ["^https?://.*/(ad)?xsi"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adxsi", "/ai"],
+              ["^https?://.*/a(dxs)?i"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+
+    // Both single and multiple character edits combined.
+    testRules(test, ["/ad", "/adxsi", "/xsi", "/axsi", "/bxsi"],
+              ["^https?://.*/ad(xsi)?", "^https?://.*/[ab]?xsi"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+
+    testRules(test, ["/ads", "/a", "/ad", "/adv", "/adx", "/adxs"],
+              ["^https?://.*/ad[svx]?", "^https?://.*/a(dxs)?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adxs", "/a", "/ad", "/ads", "/adv", "/adx"],
+              ["^https?://.*/a(dxs)?", "^https?://.*/ad[svx]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adxs", "/a", "/ads", "/ad", "/adv", "/adx"],
+              ["^https?://.*/a(dxs)?", "^https?://.*/ad[svx]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adxs", "/a", "/ads", "/adv", "/ad", "/adx"],
+              ["^https?://.*/a(dxs)?", "^https?://.*/ad[svx]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adsxi", "/adxs", "/a", "/ads", "/adv", "/ad", "/adx"],
+              ["^https?://.*/a(dsxi)?", "^https?://.*/adxs",
+               "^https?://.*/ad[svx]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/adxsi", "/adsxi", "/adxs", "/a", "/ads", "/adv", "/ad",
+                     "/adx"],
+              ["^https?://.*/adxsi?", "^https?://.*/a(dsxi)?",
+               "^https?://.*/ad[svx]?"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+
+    // Given the 6 rules "ads", "bds", "adv", "bdv", "adx", and "bdx", we want
+    // the 2 rules "ad[svx]" and "bd[svx]", not the 3 rules "[ab]ds", "[ab]dv",
+    // and "[ab]dx"
+    testRules(test, ["/ads", "/bds", "/adv", "/bdv", "/adx", "/bdx"],
+              ["^https?://.*/ad[svx]", "^https?://.*/bd[svx]"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads", "/bds", "/adv", "/bdv", "/bdx"],
+              ["^https?://.*/ad[sv]", "^https?://.*/bd[svx]"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+
+    // Make sure there's no merge where there are special characters in the
+    // delta.
+    testRules(test, ["/ads?", "/ads"],
+              ["^https?://.*/ads\\?", "^https?://.*/ads"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads?", "/ads-"],
+              ["^https?://.*/ads\\?", "^https?://.*/ads-"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+    testRules(test, ["/ads?-", "/ads-"],
+              ["^https?://.*/ads\\?-", "^https?://.*/ads-"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true});
+
+    // In exhaustive merge, redundant rules should be discarded.
+    testRules(test, ["/ad", "/ads", "/advertisement"],
+              ["^https?://.*/ad"],
+              rules => rules.map(rule => rule.trigger["url-filter"]),
+              {merge: true, exhaustiveMerge: true});
+
+    test.done();
   }
 };