Issue 235 - Improved performance of ElemHide.getSelectorsForDomain()

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2015 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 41 matching lines @@
  */
 let exceptions = Object.create(null);
 
 /**
  * Currently applied stylesheet URL
  * @type nsIURI
  */
 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
  */
 let ElemHide = exports.ElemHide =
 {
   /**
    * Indicates whether filters have been added or removed since the last apply() call.
    * @type Boolean
    */
   isDirty: false,
@@ skipping 26 matching lines @@
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
     filterByKey = Object.create(null);
     keyByFilter = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
+    filtersByDomain = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (filter.text in knownExceptions)
         return;
 
       let selector = filter.selector;
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
       knownExceptions[filter.text] = true;
     }
     else
     {
       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);
       } while (key in filterByKey);
 
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
       ElemHide.isDirty = true;
     }
   },
@@ skipping 13 matching lines @@
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
       delete knownExceptions[filter.text];
     }
     else
     {
       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];
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
@@ skipping 188 matching lines @@
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
     return (key in filterByKey ? filterByKey[key] : null);
   },
 
   /**
-   * 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;
   }
 };