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 filter selectors by domain which they are applied to

[Wladimir Palant, 2015/06/23 13:57:09]

Nit: the word "blocking" makes no sense here.

[Thomas Greiner, 2015/07/02 09:32:49]

Done.

+ * @type Object
+ */
+let selectorsByDomain = 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);
+    selectorsByDomain = 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 selectorsByDomain))
+          {
+            selectorsByDomain[domain] = Object.create(null);
+            selectorsByDomain[domain].$length = 0;
+          }
+
+          let selectors = selectorsByDomain[domain];
+          if (!(filter.selector in selectors))
+          {
+            selectors[filter.selector] = {
+              isActive: false,
+              count: 0
+            };
+          }
+          selectors[filter.selector].isActive |= domains[domain];

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

I made this change here because I noticed that this would be set to `false` for
domain "" if the following filters were added in that order:

###foo
example.com###foo

[Wladimir Palant, 2015/06/23 13:57:09]

Unfortunately, the result still isn't correct. Consider the following:

###foo
~example.com###foo

For selector "#foo" we get isActive: true on "" and isActive: false on
"example.com". As a result, it won't apply on "example.com" even though it
should.

I think that I gave you a bad advise here. One would somehow need to combine the
domain lists for all filters having the same selector, and I am having doubts
that this is possible in a manageable way.

[Thomas Greiner, 2015/06/23 15:11:41]

I see your point and please correct me if I'm wrong but wouldn't it make more
sense to prioritize the specific filter over the generic one in this case?
Because what I don't understand is why a generic filter should hide an element
if another filter explicitly declares that that element shouldn't be hidden on
that domain.

So to illustrate what I mean…
Currently: ###foo + ~example.com###foo == ###foo
Suggested: ###foo + ~example.com###foo == ###foo + example.com#@##foo

Admittingly, this behavior would be inconsistent with request blocking filters
but element hiding filters can only activate or deactivate specific selectors
anyway so I wouldn't see this as an issue.

[Wladimir Palant, 2015/06/29 09:09:09]

The problem is: you would create a behavior here that is highly confusing for
filter list authors. If you add a filter like ###foo you expect it to work. Now
suddenly it depends on other filters with the same selector, probably in other
filter lists. And if you implement a minimal change to the selector this
behavior will suddenly change.

Never mind inconsistency to blocking rules (foo + foo$domain=~example.com).

Granted, it's already the same with exception rules - we've implemented fairly
complicated interactions there. However, exception rules are explicit overrides,
and are typically found in only one filter list: Acceptable Ads.

[Thomas Greiner, 2015/06/29 13:03:44]

Generally, I might be able to solve this by splitting up "isActive" into
"isActiveGeneric" and "isActiveSpecific" to prioritize generic filters over
specific ones.

Still, I think it's worth discussing so feel free to move this discussion
elsewhere (e.g. our public forum).

On 2015/06/29 09:09:09, Wladimir Palant wrote:
That's correct, `~example.com###foo` is not an exception rule but it's still an
explicit intent to not apply a selector on example.com.
The underlying issue is that because `~example.com` is not treated as an
exception rule, we are being forced to work around that inconsistency now.
So I'd suggest that if we want to remove that inconsistency without confusing
filter list authors we should clarify that in the blockable items list.

Note that I couldn't find any conflicts in EasyList+EasyListGermany that would
result from this change in handling `~example.com`. Asking Arthur about that, he
said that they usually avoid writing `example.com,~www.example.com###foo`.
Instead they write `example.com###foo` and `www.example.com#@##foo` as separate
filters.
Therefore another option would be to get rid of the ability to have inverted
domains for element hiding filters. However, I'm not suggesting this for now to
avoid breaking backwards-compatibility.

In any case, filters of the form `~example.com###foo` are already and will
continue to be confusing.

[Thomas Greiner, 2015/07/02 09:32:49]

Done. See comment below for further details.

+          selectors[filter.selector].count++;
+
+          selectors.$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 selectorsByDomain
+            && filter.selector in selectorsByDomain[domain]
+            && !--selectorsByDomain[domain][filter.selector].$length)
+          {
+            delete selectorsByDomain[domain][filter.selector];
+            if (!--selectorsByDomain[domain].$length)
+              delete selectorsByDomain[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.
    */
-  getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
+  getException: function(/**String*/ selector, /**String*/ docDomain) /**ElemHideException*/
   {
-    if (!(filter.selector in exceptions))
+    if (!(selector in exceptions))
       return null;
 
-    let list = exceptions[filter.selector];
+    let list = exceptions[selector];
     for (let i = list.length - 1; i >= 0; i--)
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
 
     return null;
   },
 
   /**
    * Will be set to true if apply() is running (reentrance protection).
    * @type Boolean
@@ skipping 81 matching lines @@
           }
         }
 
         FilterNotifier.triggerListeners("elemhideupdate");
       }
     }.bind(this));
 
     this._applying = true;
   },
 
   _generateCSSContent: function*()

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

This was added when rebasing

   {
     // Grouping selectors by domains
     let domains = Object.create(null);
     let hasFilters = false;
     for (let key in filterByKey)
     {
       let filter = filterByKey[key];
       let domain = filter.selectorDomain || "";
 
       let list;
@@ skipping 69 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)
+  getSelectorsForDomain: function(/**String*/ docDomain, /**Boolean*/ specificOnly)
   {
-    let result = [];
-    let keys = Object.getOwnPropertyNames(filterByKey);
-    for (let key of keys)
+    if (canUseStylesheets)
+      throw new Error("Use of getSelectorsForDomain is limited to platforms which cannot inject stylesheets");
+
+    let selectors = [];
+    let domain = docDomain.toUpperCase();
+
+    let ignoredSelectors = Object.create(null);
+    while (true)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      if (domain in selectorsByDomain && (domain != "" || !specificOnly))
+      {
+        let domainSelectors = selectorsByDomain[domain];
+        let filterSelectors = Object.getOwnPropertyNames(domainSelectors);
+        for (let filterSelector of filterSelectors)
+        {
+          if (filterSelector == "$length" || filterSelector in ignoredSelectors)
+            continue;
 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+          if (domainSelectors[filterSelector].isActive)
+          {
+            if (!this.getException(filterSelector, docDomain))
+            {
+              selectors.push(filterSelector);
+              ignoredSelectors[filterSelector] = null;
+            }
+          }
+          else
+            ignoredSelectors[filterSelector] = null;

[Thomas Greiner, 2015/07/02 09:32:49]

Basically, all I did was remove the else-case here. All the other changes are
simplifications.

Due to that change, however, both "selectors" and "ignoredFilters" would've
ended up containing the exact same values which is why I decided to change
"selectors" from an array to a plain object. Actually, I'd prefer using `Set`
for that because it has the best performance but that would've required changing
the return type of "getSelectorsForDomain".

+        }
+      }
+
+      if (domain == "")
+        break;
+
+      let nextDot = domain.indexOf(".");
+      domain = (nextDot < 0) ? "" : domain.substr(nextDot + 1);
     }
-    return result;
+
+    return selectors;
   }
 };