Issue 3673 - Merge closely matching rules

test/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/>.
  */
 
 "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();
   for (let filter of filters)
     blockerList.addFilter(Filter.fromText(filter));
 
-  let rules = blockerList.generateRules();
+  let rules = blockerList.generateRules({merge, exhaustiveMerge});
   if (transformFunction)
     rules = transformFunction(rules);
 
   test.deepEqual(rules, expected);
 }
 
 exports.generateRules = {
   testElementHiding: function(test)
   {
     testRules(test, ["##.whatever"], [
@@ skipping 184 matching lines @@
   },
 
   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();
   }
 };