Issue 5735 - Use JS Map instead of Object for matcher properties filterByKeyword and keywordByFilter

lib/matcher.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present 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 19 matching lines @@
  */
 function Matcher()
 {
   this.clear();
 }
 exports.Matcher = Matcher;
 
 Matcher.prototype = {
   /**
    * Lookup table for filters by their associated keyword
-   * @type {Object}
+   * @type {Map.<string,Filter>}
    */
   filterByKeyword: null,
 
   /**
    * Lookup table for keywords by the filter text
-   * @type {Object}
+   * @type {Map.<string,string>}

[sergei, 2017/09/21 13:22:21]

I will check the difference between Map.<string,string> and Map.<Filter,string>
separately.

[Wladimir Palant, 2017/09/25 11:07:46]

I'd prefer to have this change done in the same go.

[sergei, 2017/09/25 13:46:33]

Done.

I have checked it and there is no visible difference in the memory usage.

    */
   keywordByFilter: null,

[sergei, 2017/09/21 13:22:21]

strictly speaking the change of type of keywordByFilter could be separated from
the change of type of filterByKeyword but it seems not very interesting from any
performance point of view, because they are very similar and there is no
comparison between "many Object objects" and "many Map objects". However, if
someone wants it then please let me know and I extract it into another
codereview.

 
   /**
    * Removes all known filters
    */
   clear()
   {
-    this.filterByKeyword = Object.create(null);
-    this.keywordByFilter = Object.create(null);
+    this.filterByKeyword = new Map();
+    this.keywordByFilter = new Map();
   },
 
   /**
    * Adds a filter to the matcher
    * @param {RegExpFilter} filter
    */
   add(filter)
   {
-    if (filter.text in this.keywordByFilter)
+    if (this.keywordByFilter.has(filter.text))
       return;
 
     // Look for a suitable keyword
     let keyword = this.findKeyword(filter);
-    let oldEntry = this.filterByKeyword[keyword];
+    let oldEntry = this.filterByKeyword.get(keyword);
     if (typeof oldEntry == "undefined")
-      this.filterByKeyword[keyword] = filter;
+      this.filterByKeyword.set(keyword, filter);
     else if (oldEntry.length == 1)
-      this.filterByKeyword[keyword] = [oldEntry, filter];
+      this.filterByKeyword.set(keyword, [oldEntry, filter]);
     else
       oldEntry.push(filter);
-    this.keywordByFilter[filter.text] = keyword;
+    this.keywordByFilter.set(filter.text, keyword);
   },
 
   /**
    * Removes a filter from the matcher
    * @param {RegExpFilter} filter
    */
   remove(filter)
   {
-    if (!(filter.text in this.keywordByFilter))
+    let keyword = this.keywordByFilter.get(filter.text);
+    if (typeof keyword == "undefined")
       return;
 
-    let keyword = this.keywordByFilter[filter.text];
-    let list = this.filterByKeyword[keyword];
+    let list = this.filterByKeyword.get(keyword);
     if (list.length <= 1)
-      delete this.filterByKeyword[keyword];
+      this.filterByKeyword.delete(keyword);
     else
     {
       let index = list.indexOf(filter);
       if (index >= 0)
       {
         list.splice(index, 1);
         if (list.length == 1)
-          this.filterByKeyword[keyword] = list[0];
+          this.filterByKeyword.set(keyword, list[0]);
       }
     }
 
-    delete this.keywordByFilter[filter.text];
+    this.keywordByFilter.delete(filter.text);
   },
 
   /**
    * Chooses a keyword to be associated with the filter
    * @param {Filter} filter
    * @return {string} keyword or an empty string if no keyword could be found
    */
   findKeyword(filter)
   {
     let result = "";
@@ skipping 15 matching lines @@
     );
     if (!candidates)
       return result;
 
     let hash = this.filterByKeyword;
     let resultCount = 0xFFFFFF;
     let resultLength = 0;
     for (let i = 0, l = candidates.length; i < l; i++)
     {
       let candidate = candidates[i].substr(1);
-      let count = (candidate in hash ? hash[candidate].length : 0);
+      let filters = hash.get(candidate);
+      let count = typeof filters != "undefined" ? filters.length : 0;
       if (count < resultCount ||
           (count == resultCount && candidate.length > resultLength))
       {
         result = candidate;
         resultCount = count;
         resultLength = candidate.length;
       }
     }
     return result;
   },
 
   /**
    * Checks whether a particular filter is being matched against.
    * @param {RegExpFilter} filter
    * @return {boolean}
    */
   hasFilter(filter)
   {
-    return (filter.text in this.keywordByFilter);
+    return this.keywordByFilter.has(filter.text);
   },
 
   /**
    * Returns the keyword used for a filter, null for unknown filters.
    * @param {RegExpFilter} filter
-   * @return {string}
+   * @return {?string}
    */
   getKeywordForFilter(filter)
   {
-    if (filter.text in this.keywordByFilter)
-      return this.keywordByFilter[filter.text];
-    return null;
+    let keyword = this.keywordByFilter.get(filter.text);
+    return typeof keyword != "undefined" ? keyword : null;

[Wladimir Palant, 2017/09/25 11:07:46]

It seems that this can be simplified:

  return this.keywordByFilter.get(filter.text) || null;

[sergei, 2017/09/25 13:46:33]

It changes the behavior because if the value of `keyword` is the empty string ""
then it returns `null` instead of that empty string. It may be a correct value
(BTW, tests fail but they can be fixed) but I'm not sure about it because it's
not clear what this method is actually for. I would propose to make it in a
separate commit what should simplify the search for a regression if there is
one.

So far, I see that `Matcher.getKeywordForFilter` is used by
`CombinedMatcher.getKeywordForFilter` which seem not used and by
`CombinedMatcher.isSlowFilter` for which it's a correct value. I would propose
to make that change, remove `CombinedMatcher.getKeywordForFilter` and maybe
remove `matcher.hasFilter` in a separate commit.

   },
 
   /**
    * Checks whether the entries for a particular keyword match a URL
    * @param {string} keyword
    * @param {string} location
    * @param {number} typeMask
    * @param {string} docDomain
    * @param {boolean} thirdParty
    * @param {string} sitekey
    * @param {boolean} specificOnly
    * @return {?Filter}
    */
   _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
                    specificOnly)
   {
-    let list = this.filterByKeyword[keyword];
+    let list = this.filterByKeyword.get(keyword);
+    if (typeof list == "undefined")

[sergei, 2017/09/21 13:22:21]

This change is additional to the change of type. Previously a caller didn't call
_checkEntryMatch with an unknown by filterByKeyword keyword, however it's not
only about performance (no double look up) but also about design because it
reduces the number of places of work with filterByKeyword.

+      return null;
     for (let i = 0; i < list.length; i++)
     {
       let filter = list[i];
 
       if (specificOnly && filter.isGeneric() &&
           !(filter instanceof WhitelistFilter))
         continue;
 
       if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
         return filter;
@@ skipping 19 matching lines @@
    *   matching filter or null
    */
   matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly)
   {
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
     candidates.push("");
     for (let i = 0, l = candidates.length; i < l; i++)
     {
-      let substr = candidates[i];
-      if (substr in this.filterByKeyword)
-      {
-        let result = this._checkEntryMatch(substr, location, typeMask,
-                                           docDomain, thirdParty, sitekey,
-                                           specificOnly);
-        if (result)
-          return result;
-      }
+      let result = this._checkEntryMatch(candidates[i], location, typeMask,
+                                         docDomain, thirdParty, sitekey,
+                                         specificOnly);
+      if (result)
+        return result;
     }
 
     return null;
   }
 };
 
 /**
  * Combines a matcher for blocking and exception rules, automatically sorts
  * rules into two Matcher instances.
  * @constructor
@@ skipping 148 matching lines @@
   {
     let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
     if (candidates === null)
       candidates = [];
     candidates.push("");
 
     let blacklistHit = null;
     for (let i = 0, l = candidates.length; i < l; i++)
     {
       let substr = candidates[i];
-      if (substr in this.whitelist.filterByKeyword)
-      {
-        let result = this.whitelist._checkEntryMatch(
-          substr, location, typeMask, docDomain, thirdParty, sitekey
-        );
-        if (result)
-          return result;
-      }
-      if (substr in this.blacklist.filterByKeyword && blacklistHit === null)
+      let result = this.whitelist._checkEntryMatch(
+        substr, location, typeMask, docDomain, thirdParty, sitekey
+      );
+      if (result)
+        return result;
+      if (blacklistHit === null)
       {
         blacklistHit = this.blacklist._checkEntryMatch(
           substr, location, typeMask, docDomain, thirdParty, sitekey,
           specificOnly
         );
       }
     }
     return blacklistHit;
   },
 
@@ skipping 22 matching lines @@
 
     return result;
   }
 };
 
 /**
  * Shared CombinedMatcher instance that should usually be used.
  * @type {CombinedMatcher}
  */
 exports.defaultMatcher = new CombinedMatcher();