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

lib/matcher.js

Index: lib/matcher.js
diff --git a/lib/matcher.js b/lib/matcher.js
index 9381ad77c4268718f5f89415fb78c2ba6f2a6a84..8ea66b760b6d022f2ae67dfe7eac138619101894 100644
--- a/lib/matcher.js
+++ b/lib/matcher.js
@@ -37,13 +37,13 @@ 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.

 
@@ -52,8 +52,8 @@ Matcher.prototype = {
    */
   clear()
   {
-    this.filterByKeyword = Object.create(null);
-    this.keywordByFilter = Object.create(null);
+    this.filterByKeyword = new Map();
+    this.keywordByFilter = new Map();
   },
 
   /**
@@ -62,19 +62,19 @@ Matcher.prototype = {
    */
   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);
   },
 
   /**
@@ -83,13 +83,13 @@ Matcher.prototype = {
    */
   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);
@@ -97,11 +97,11 @@ Matcher.prototype = {
       {
         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);
   },
 
   /**
@@ -137,7 +137,8 @@ Matcher.prototype = {
     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))
       {
@@ -156,19 +157,18 @@ Matcher.prototype = {
    */
   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.

   },
 
   /**
@@ -185,7 +185,9 @@ Matcher.prototype = {
   _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];
@@ -225,15 +227,11 @@ Matcher.prototype = {
     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;
@@ -402,15 +400,12 @@ CombinedMatcher.prototype =
     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,