Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code

Unified Diff: lib/elemHide.js

Issue 29773570: Issue 6652 - Implement fast selector lookups for unknown domains (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore/
Patch Set: Used cached list for generic-friendly domains Created May 11, 2018, 9:51 a.m.
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | test/elemHide.js » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: lib/elemHide.js
===================================================================
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -22,17 +22,17 @@
*/
const {ElemHideException} = require("./filterClasses");
const {FilterNotifier} = require("./filterNotifier");
/**
* Lookup table, active flag, by filter by domain.
* (Only contains filters that aren't unconditionally matched for all domains.)
- * @type {Map.<string,Map.<Filter,boolean>>}
+ * @type {Map.<string,?Map.<Filter,boolean>>}
*/
let filtersByDomain = new Map();
/**
* Lookup table, filter by selector. (Only used for selectors that are
* unconditionally matched for all domains.)
* @type {Map.<string,Filter>}
*/
@@ -56,21 +56,158 @@
/**
* Set containing known element hiding and exception filters
* @type {Set.<ElemHideBase>}
*/
let knownFilters = new Set();
/**
* Lookup table, lists of element hiding exceptions by selector
- * @type {Map.<string,Filter>}
+ * @type {Map.<string,Filter[]>}
*/
let exceptions = new Map();
/**
+ * Lookup table, lists of generic element hiding exceptions by selector
+ * @type {Map.<string,Filter[]>}
+ */
+let genericExceptions = new Map();
+
+/**
+ * List of selectors that apply on any unknown domain
+ * @type {?string[]}
+ */
+let conditionalGenericSelectors = null;
+
+/**
+ * Domains that are known not to be specifically excluded from any generic
+ * filters
+ * @type {Set.<string>}
+ */
+let genericFriendlyDomains = new Set();
+
+/**
+ * Returns a list of domain-specific filters matching a domain
+ * @param {string} [domain]
+ * @returns {Array.<?Map.<Filter,boolean>>}
+ */
+function getSpecificFiltersForDomain(domain)
+{
+ let filtersList = [];
+
+ if (domain)
+ domain = domain.toUpperCase();
+
+ while (domain)
+ {
+ // Note that we also push null values into the list, because
+ // ElemHide.getSelectorsForDomain still needs to know if there are any
+ // entries for the domain.
+ let filters = filtersByDomain.get(domain);
+ if (typeof filters != "undefined")
+ filtersList.push(filters);
+
+ let nextDot = domain.indexOf(".");
+ domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
+ }
+
+ return filtersList;
+}
+
+/**
+ * Returns a list of selectors from a given list of filters that apply on a
+ * domain
+ * @param {string} [domain]
+ * @param {Array.<?Map.<Filter,boolean>>} filtersList
+ * @param {boolean} specificOnly
+ * @returns {string[]}
+ */
+function getConditionalSelectorsForDomain(domain, filtersList, specificOnly)
+{
+ let selectors = [];
+
+ let genericFilters = !specificOnly ? filtersList.pop() : null;
+ let excluded = new Set();
+
+ // This code is a performance hot-spot, which is why we've made certain
+ // micro-optimisations. Please be careful before making changes.
+ for (let i = 0; i < filtersList.length; i++)
+ {
+ if (!filtersList[i])
+ continue;
+
+ for (let [filter, isIncluded] of filtersList[i])
+ {
+ if (!isIncluded)
+ {
+ excluded.add(filter);
+ }
+ else if ((excluded.size == 0 || !excluded.has(filter)) &&
+ !ElemHide.getException(filter, domain))
+ {
+ selectors.push(filter.selector);
+ }
+ }
+ }
+
+ if (!genericFilters)
+ return selectors;
+
+ if (genericFriendlyDomains.has(domain))
+ return selectors.concat(getConditionalGenericSelectors());
+
+ let genericSelectors = [];
+
+ for (let filter of genericFilters.keys())
+ {
+ if ((excluded.size == 0 || !excluded.has(filter)) &&
+ !ElemHide.getException(filter, domain))
+ {
+ genericSelectors.push(filter.selector);
+ }
+ }
+
+ // If the number of conditional generic selectors that apply on this domain
+ // is the same as the total number of conditional generic selectors, the
+ // domain is "generic friendly". In that case, we mark it is as such for
+ // faster lookups.
+ if (conditionalGenericSelectors &&
+ genericSelectors.length == conditionalGenericSelectors.length)
+ {
+ genericFriendlyDomains.add(domain);
Manish Jethani 2018/05/11 10:00:32 Most domains will fall in this category. We might
Manish Jethani 2018/05/11 10:09:09 Done.
+ }
+
+ return selectors.concat(genericSelectors);
+}
+
+/**
+ * Returns a list of selectors that apply on any unknown domain
+ * @returns {string[]}
+ */
+function getConditionalGenericSelectors()
+{
+ if (conditionalGenericSelectors)
+ return conditionalGenericSelectors;
+
+ conditionalGenericSelectors = [];
+
+ let filters = filtersByDomain.get("");
+ if (!filters)
+ return conditionalGenericSelectors;
+
+ for (let {selector} of filters.keys())
+ {
+ if (genericExceptions.size == 0 || !genericExceptions.has(selector))
+ conditionalGenericSelectors.push(selector);
+ }
+
+ return conditionalGenericSelectors;
+}
+
+/**
* Returns a list of selectors that apply on each website unconditionally.
* @returns {string[]}
*/
function getUnconditionalSelectors()
{
if (!unconditionalSelectors)
unconditionalSelectors = [...filterBySelector.keys()];
@@ -83,58 +220,90 @@
*/
let ElemHide = exports.ElemHide = {
/**
* Removes all known filters
*/
clear()
{
for (let collection of [filtersByDomain, filterBySelector,
- knownFilters, exceptions])
+ knownFilters, exceptions,
+ genericExceptions, genericFriendlyDomains])
{
collection.clear();
}
unconditionalSelectors = null;
+ conditionalGenericSelectors = null;
FilterNotifier.emit("elemhideupdate");
},
_addToFiltersByDomain(filter)
{
let domains = filter.domains || defaultDomains;
- for (let [domain, isIncluded] of domains)
+ if (filter instanceof ElemHideException)
{
- // There's no need to note that a filter is generically disabled.
- if (!isIncluded && domain == "")
- continue;
+ for (let domain of domains.keys())
+ {
+ // Add an entry for each domain, but without any filters. This makes
+ // the domain "known" and helps us avoid certain optimizations that
+ // would otherwise yield incorrect results.
+ if (domain != "" && !filtersByDomain.has(domain))
+ filtersByDomain.set(domain, null);
+ }
+ }
+ else
+ {
+ for (let [domain, isIncluded] of domains)
+ {
+ // There's no need to note that a filter is generically disabled.
+ if (!isIncluded && domain == "")
+ continue;
- let filters = filtersByDomain.get(domain);
- if (!filters)
- filtersByDomain.set(domain, filters = new Map());
- filters.set(filter, isIncluded);
+ let filters = filtersByDomain.get(domain);
+ if (!filters)
+ filtersByDomain.set(domain, filters = new Map());
+ filters.set(filter, isIncluded);
+ }
}
},
/**
* Add a new element hiding filter
* @param {ElemHideBase} filter
*/
add(filter)
{
if (knownFilters.has(filter))
return;
+ conditionalGenericSelectors = null;
+ genericFriendlyDomains.clear();
+
if (filter instanceof ElemHideException)
{
- let {selector} = filter;
+ let {selector, domains} = filter;
+
let list = exceptions.get(selector);
if (list)
list.push(filter);
else
exceptions.set(selector, [filter]);
+ if (domains)
+ this._addToFiltersByDomain(filter);
+
+ if (filter.isGeneric())
+ {
+ list = genericExceptions.get(selector);
+ if (list)
+ list.push(filter);
+ else
+ genericExceptions.set(selector, [filter]);
+ }
+
// If this is the first exception for a previously unconditionally
// applied element hiding selector we need to take care to update the
// lookups.
let unconditionalFilterForSelector = filterBySelector.get(selector);
if (unconditionalFilterForSelector)
{
this._addToFiltersByDomain(unconditionalFilterForSelector);
filterBySelector.delete(selector);
@@ -161,23 +330,37 @@
* Removes an element hiding filter
* @param {ElemHideBase} filter
*/
remove(filter)
{
if (!knownFilters.has(filter))
return;
+ conditionalGenericSelectors = null;
+ genericFriendlyDomains.clear();
+
// Whitelisting filters
if (filter instanceof ElemHideException)
{
let list = exceptions.get(filter.selector);
let index = list.indexOf(filter);
if (index >= 0)
list.splice(index, 1);
+
+ if (filter.isGeneric())
+ {
+ list = genericExceptions.get(filter.selector);
+ index = list.indexOf(filter);
+ if (index >= 0)
+ list.splice(index, 1);
+
+ if (list.length == 0)
+ genericExceptions.delete(filter.selector);
+ }
}
// Unconditially applied element hiding filters
else if (filterBySelector.get(filter.selector) == filter)
{
filterBySelector.delete(filter.selector);
unconditionalSelectors = null;
}
// Conditionally applied element hiding filters
@@ -251,49 +434,35 @@
* ElemHide.SPECIFIC_ONLY.
* @returns {string[]}
* List of selectors.
*/
getSelectorsForDomain(domain, criteria = ElemHide.ALL_MATCHING)
{
let selectors = [];
- let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
- let excluded = new Set();
- let currentDomain = domain ? domain.toUpperCase() : "";
-
- // This code is a performance hot-spot, which is why we've made certain
- // micro-optimisations. Please be careful before making changes.
- while (true)
- {
- if (specificOnly && currentDomain == "")
- break;
+ let specificOnly = criteria >= ElemHide.SPECIFIC_ONLY;
+ let filtersList = getSpecificFiltersForDomain(domain);
- let filters = filtersByDomain.get(currentDomain);
- if (filters)
- {
- for (let [filter, isIncluded] of filters)
- {
- if (!isIncluded)
- {
- excluded.add(filter);
- }
- else if ((excluded.size == 0 || !excluded.has(filter)) &&
- !this.getException(filter, domain))
- {
- selectors.push(filter.selector);
- }
- }
- }
+ if (filtersList.length > 0)
+ {
+ if (!specificOnly)
+ filtersList.push(filtersByDomain.get(""));
- if (currentDomain == "")
- break;
-
- let nextDot = currentDomain.indexOf(".");
- currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
+ selectors = getConditionalSelectorsForDomain(domain, filtersList,
+ specificOnly);
+ }
+ else if (!specificOnly)
+ {
+ selectors = getConditionalGenericSelectors();
}
if (criteria < ElemHide.NO_UNCONDITIONAL)
selectors = getUnconditionalSelectors().concat(selectors);
+ // If the above logic leaves us with a reference to our internal cache of
+ // selectors, we make a copy here.
+ if (selectors == conditionalGenericSelectors)
+ selectors = selectors.slice();
+
return selectors;
}
};
« no previous file with comments | « no previous file | test/elemHide.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld