Issue 235 - Improved performance of ElemHide.getSelectorsForDomain()

lib/elemHide.js

Index: lib/elemHide.js
===================================================================
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -59,6 +59,18 @@
 let styleURL = null;
 
 /**
+ * Lookup table, blocking filters by domain which they are applied to
+ * @type Object
+ */
+let filtersByDomain = Object.create(null);
+
+/**
+ * Indicates whether stylesheets can be used for element hiding
+ * @type Boolean
+ */
+let canUseStylesheets = ("nsIStyleSheetService" in Ci);
+
+/**
  * Element hiding component
  * @class
  */
@@ -105,6 +117,7 @@
     keyByFilter = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
+    filtersByDomain = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
@@ -131,6 +144,28 @@
       if (filter.text in keyByFilter)
         return;
 
+      if (!canUseStylesheets)
+      {
+        let domains = filter.domains;
+        if (domains === null)
+        {
+          domains = Object.create(null);
+          domains[""] = true;
+        }
+
+        for (let domain in domains)
+        {
+          if (!(domain in filtersByDomain))
+          {
+            filtersByDomain[domain] = Object.create(null);
+            filtersByDomain[domain].$length = 0;
+          }
+
+          filtersByDomain[domain][filter.text] = domains[domain];
+          filtersByDomain[domain].$length++;
+        }
+      }
+
       let key;
       do {
         key = Math.random().toFixed(15).substr(5);
@@ -164,6 +199,26 @@
       if (!(filter.text in keyByFilter))
         return;
 
+      if (!canUseStylesheets)
+      {
+        let domains = filter.domains;
+        if (!domains)
+        {
+          domains = Object.create(null);
+          domains[""] = true;
+        }
+
+        for (let domain in domains)
+        {
+          if (domain in filtersByDomain && filter.text in filtersByDomain[domain])
+          {
+            delete filtersByDomain[domain][filter.text];
+            if (!--filtersByDomain[domain].$length)
+              delete filtersByDomain[domain];
+          }
+        }
+      }
+
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
@@ -372,21 +427,65 @@
   },
 
   /**
-   * 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 (it cannot
+   * be used in Firefox).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
-    let result = [];
-    for (let key in filterByKey)
+    if (canUseStylesheets)
+      throw new Error("Use of getSelectorsForDomain is limited to platforms which cannot inject stylesheets");
+
+    let selectors = [];
+    domain = domain.toUpperCase();
+
+    if (!specificOnly)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      let filterTexts = filtersByDomain[""];
+      if (filterTexts)
+      {
+        for (let filterText in filterTexts)
+        {
+          if (filterTexts[filterText] && filterText != "$length")
+          {
+            let filter = Filter.fromText(filterText);
+            if (!this.getException(filter, domain))
+              selectors[selectors.length] = filter.selector;
+          }
+        }
+      }
+    }

[Wladimir Palant, 2015/06/05 21:58:54]

This block duplicates the logic below unnecessarily. It also happens to produce
wrong results. For example, ~example.com##foo should be active on every domain
but example.com. However, with domain being foo.example.com your code will
currently add it to the selectors in the block above and ignore the exception
completely.

"" should really be handled in the loop below along with other "domains":

while (true)
{
  if (domain in filtersByDomain && (domain != "" || !specificOnly))
  ...

  if (domain == "")
    break;

  let nextDot = domain.indexOf(".");
  domain = domain.substr(nextDot + 1);
}

[Thomas Greiner, 2015/06/23 13:28:40]

Done.

 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+    let ignorableFilters = [];

[Wladimir Palant, 2015/06/05 21:58:54]

Use an object here rather than an array, given that you need to do frequent
lookups?

Also, it's ignoredFilters I think.

[Thomas Greiner, 2015/06/23 13:28:40]

Done.

+    while (true)
+    {
+      if (domain && domain in filtersByDomain)
+      {
+        let filterTexts = filtersByDomain[domain];
+        for (let filterText in filterTexts)
+        {
+          if (ignorableFilters.indexOf(filterText) > -1)

[Wladimir Palant, 2015/06/05 21:58:54]

How about checking for $length immediately?

if (filterText == "$length" || filterText in ignoredFilters)
  continue;

[Thomas Greiner, 2015/06/23 13:28:40]

Done.

+            continue;
+          
+          if (filterTexts[filterText])
+          {
+            if (filterText == "$length")
+              continue;
+
+            let filter = Filter.fromText(filterText);
+            if (!this.getException(filter, domain))

[Wladimir Palant, 2015/06/05 21:58:54]

Calling Filter.fromText() here looks like unnecessary overhead - you don't
really need the full filter. How about storing the selectors in the data rather
than the complete filter text? ElemHide.getException() can be changed to accept
selectors rather than filters, that's what it needs anyway. The only other
caller of ElemHide.getException() is contentPolicy.js and easily changed.

The only problem: multiple filters could use the same selector for the same
domain (consider foo.example.com##foo and bar.example.org,foo.example.com##foo),
meaning that your current approach to remove filters from the data will no
longer work. We need to store the count for each selector rather than for
domains.

[Thomas Greiner, 2015/06/23 13:28:40]

Done. That's an awesome tip, thanks!

Note that the `#foo` selector is currently being returned twice when using the
two filters you mentioned. This no longer occurs with these changes.

+              selectors[selectors.length] = filter.selector;

[Wladimir Palant, 2015/06/05 21:58:54]

selectors.push() please.

Either way, I think this might add the same selector multiple times. Consider
foo.example.com,example.com##foo on foo.example.com.

[Thomas Greiner, 2015/06/23 13:28:40]

Done.
Done. Unfortunately, `Array.indexOf()` is terribly slow to check this so I chose
to use the `ignoredSelectors` object for this.

+          }
+          else
+            ignorableFilters[ignorableFilters.length] = filterText;
+        }
+      }
+
+      let nextDot = domain.indexOf(".");
+      if (nextDot < 0)
+        break;
+      domain = domain.substr(nextDot + 1);
     }
-    return result;
+
+    return selectors;
   }
 };