Issue 235 - Speed up ElemHide.getSelectorsForDomain

lib/elemHide.js

Index: lib/elemHide.js
diff --git a/lib/elemHide.js b/lib/elemHide.js
index 4b25c62d0daf0079b7e8f54f962cf3d4bddf9792..ecedd2a6921b20625a3d51a8a4f132035bbe0e57 100644
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -40,6 +40,19 @@ var filterByKey = Object.create(null);
 var keyByFilter = Object.create(null);
 
 /**
+ * Nested lookup table, filter (or false if inactive) by filter text by domain
+ * @type Object
+ */
+var filtersByDomain = Object.create(null);
+
+/**
+ * Indicates whether we are using (and maintaining) the filtersByDomain lookup.
+ * (Will be false for Firefox)
+ * @type Boolean
+ */
+var usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+
+/**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
  */
@@ -70,7 +83,7 @@ var ElemHide = exports.ElemHide =
   isDirty: false,
 
   /**
-   * Inidicates whether the element hiding stylesheet is currently applied.
+   * Indicates whether the element hiding stylesheet is currently applied.
    * @type Boolean
    */
   applied: false,
@@ -99,6 +112,7 @@ var ElemHide = exports.ElemHide =
   {
     filterByKey = Object.create(null);
     keyByFilter = Object.create(null);
+    filtersByDomain = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
@@ -134,6 +148,19 @@ var ElemHide = exports.ElemHide =
 
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
+
+      if (usingFiltersByDomain)
+      {
+        let domainMatches = filter.domains || {"": true};
+        for (let domain in domainMatches)
+        {
+          domain = domain.toUpperCase();
+          if (!(domain in filtersByDomain))

[Sebastian Noack, 2016/05/17 09:47:49]

I think we should cache the lookup here:

  let filters = filtersByDomain[domain];
  if (!filters)
    filters = filtersByDomain[domain] = Object.create(null);
  filters[filter.text] = ...;

[kzar, 2016/05/17 10:05:45]

Done.

+            filtersByDomain[domain] = Object.create(null);
+          filtersByDomain[domain][filter.text] = domainMatches[domain] && filter;
+        }
+      }
+
       ElemHide.isDirty = true;
     }
   },
@@ -368,22 +395,45 @@ var ElemHide = exports.ElemHide =
   },
 
   /**
-   * Returns a list of all selectors active on a particular domain (currently
-   * used only in Chrome, Opera and Safari).
+   * Returns a list of all selectors active on a particular domain, must not be
+   * used in Firefox (when usingFiltersByDomain is false).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
-    let result = [];
-    let keys = Object.getOwnPropertyNames(filterByKey);
-    for (let key of keys)
+    if (!usingFiltersByDomain)
+      throw new Error("getSelectorsForDomain can not be used in Firefox!");
+
+    let selectors = [];
+
+    let seenFilters = Object.create(null);
+    let currentDomain = domain ? domain.toUpperCase() : "";
+    while (true)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      if (specificOnly && currentDomain == "")
+        break;
+
+      let filters = filtersByDomain[currentDomain];
+      if (filters)
+      {
+        for (let filterText in filters)
+        {
+          if (filterText in seenFilters)

[Sebastian Noack, 2016/05/17 09:47:49]

Is this some kind of micro optimization or an attempt to exclude duplicate
selectors? If it's supposed to be the latter, I think it makes more sense to
simply use an object for the resulting selectors and simply returning
Object.keys(selectors) below, as this will also remove duplicate selectors from
different filters. 

[kzar, 2016/05/17 10:05:45]

There's a comment in the old codereview about how this logic should work
https://codereview.adblockplus.org/4529242486341632/diff/29321269/lib/elemHid...

"~foo.example.com,example.com##foo really shouldn't apply on foo.example.com
even if that filter is allowed on example.com."

So let's say the domain given to getSelectorsForDomain is foo.example.com. The
matched filter is false for foo.example.com, meaning that the filter should not
be active. Now without the seenFilters logic we would continue to match the
filter example.com but this time it would be active. So the end result would be
that the filter would be applied to foo.example.com, which would be incorrect.

+            continue;
+          seenFilters[filterText] = true;
+
+          let filter = filters[filterText];
+          if (filter && !this.getException(filter, domain))

[Sebastian Noack, 2016/05/17 09:47:49]

I still have a hard time to understand how/whether filters like
~example.com##div are working. As far as I understand the logic here, you simply
ignore such filters, as the variable "filter" will be false for them here.

[kzar, 2016/05/17 10:05:45]

For ~example.com##div there should be two entries added to filtersByDomain.
filtersByDomain["example.com"]["~example.com##div"][false] and
filtersByDomain[""]["~example.com##div"]. The first has the value of false and
the second has of the filter itself. (Originally it was going to simply be true
but this way we avoid a second lookup to get the filter object.)

+            selectors.push(filter.selector);
+        }
+      }
+
+      if (currentDomain == "")
+        break;
 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+      let nextDot = currentDomain.indexOf(".");
+      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
-    return result;
+
+    return selectors;
   }
 };