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.

+ * Lookup table, filter selectors by domain which they are applied to
  * @type Object
  */
 let selectorsByDomain = Object.create(null);
 
 /**
  * Indicates whether stylesheets can be used for element hiding
  * @type Boolean
  */
 let canUseStylesheets = ("nsIStyleSheetService" in Ci);
 
@@ skipping 89 matching lines @@
           }
 
           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);
@@ skipping 159 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 77 matching lines @@
 
   /**
    * Returns a list of all selectors active on a particular domain (it cannot
    * be used in Firefox).
    */
   getSelectorsForDomain: function(/**String*/ docDomain, /**Boolean*/ specificOnly)
   {
     if (canUseStylesheets)
       throw new Error("Use of getSelectorsForDomain is limited to platforms which cannot inject stylesheets");
 
-    let selectors = [];
+    let selectors = Object.create(null);
     let domain = docDomain.toUpperCase();
-
-    let ignoredSelectors = Object.create(null);
     while (true)
     {
       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)
+          if (filterSelector == "$length"
+            || filterSelector in selectors
+            || !domainSelectors[filterSelector].isActive
+            || this.getException(filterSelector, docDomain))
             continue;

[Wladimir Palant, 2015/07/30 11:26:53]

Even with the inconsistent logic changes you are implementing, this is still
wrong. !domainSelectors[filterSelector].isActive shouldn't mean "oh well, maybe
some other domain is allowed" - it's really "oops, should not apply, stop now."
Meaning that ~foo.example.com,example.com##foo really shouldn't apply on
foo.example.com even if that filter is allowed on example.com. Same goes for
exceptions, if we have foo.example.com#@#foo then example.com##foo should *not*
apply on foo.example.com.

I recommend adding unit tests for all the scenarios I mention in the review
comments. I feel like you are consistently forgetting to test the edge cases.

 
-          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".

+          selectors[filterSelector] = null;
         }
       }
 
       if (domain == "")
         break;
 
       let nextDot = domain.indexOf(".");
       domain = (nextDot < 0) ? "" : domain.substr(nextDot + 1);
     }
 
-    return selectors;
+    return Object.getOwnPropertyNames(selectors);
   }
 };