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

Side by Side 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: Reinclude test/elemHide.js Created May 15, 2018, 4:26 p.m.
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | test/elemHide.js » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * This file is part of Adblock Plus <https://adblockplus.org/>, 2 * This file is part of Adblock Plus <https://adblockplus.org/>,
3 * Copyright (C) 2006-present eyeo GmbH 3 * Copyright (C) 2006-present eyeo GmbH
4 * 4 *
5 * Adblock Plus is free software: you can redistribute it and/or modify 5 * Adblock Plus is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 3 as 6 * it under the terms of the GNU General Public License version 3 as
7 * published by the Free Software Foundation. 7 * published by the Free Software Foundation.
8 * 8 *
9 * Adblock Plus is distributed in the hope that it will be useful, 9 * Adblock Plus is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details. 12 * GNU General Public License for more details.
13 * 13 *
14 * You should have received a copy of the GNU General Public License 14 * You should have received a copy of the GNU General Public License
15 * along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>. 15 * along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>.
16 */ 16 */
17 17
18 "use strict"; 18 "use strict";
19 19
20 /** 20 /**
21 * @fileOverview Element hiding implementation. 21 * @fileOverview Element hiding implementation.
22 */ 22 */
23 23
24 const {ElemHideException} = require("./filterClasses"); 24 const {ElemHideException} = require("./filterClasses");
25 const {FilterNotifier} = require("./filterNotifier"); 25 const {FilterNotifier} = require("./filterNotifier");
26 26
27 /** 27 /**
28 * Lookup table, active flag, by filter by domain. 28 * Lookup table, active flag, by filter by domain.
29 * (Only contains filters that aren't unconditionally matched for all domains.) 29 * (Only contains filters that aren't unconditionally matched for all domains.)
30 * @type {Map.<string,Map.<Filter,boolean>>} 30 * @type {Map.<string,?Map.<Filter,boolean>>}
31 */ 31 */
32 let filtersByDomain = new Map(); 32 let filtersByDomain = new Map();
33 33
34 /** 34 /**
35 * Lookup table, filter by selector. (Only used for selectors that are 35 * Lookup table, filter by selector. (Only used for selectors that are
36 * unconditionally matched for all domains.) 36 * unconditionally matched for all domains.)
37 * @type {Map.<string,Filter>} 37 * @type {Map.<string,Filter>}
38 */ 38 */
39 let filterBySelector = new Map(); 39 let filterBySelector = new Map();
40 40
(...skipping 18 matching lines...) Expand all
59 */ 59 */
60 let knownFilters = new Set(); 60 let knownFilters = new Set();
61 61
62 /** 62 /**
63 * Lookup table, lists of element hiding exceptions by selector 63 * Lookup table, lists of element hiding exceptions by selector
64 * @type {Map.<string,Filter[]>} 64 * @type {Map.<string,Filter[]>}
65 */ 65 */
66 let exceptions = new Map(); 66 let exceptions = new Map();
67 67
68 /** 68 /**
69 * Lookup table, lists of generic element hiding exceptions by selector
70 * @type {Map.<string,Filter[]>}
71 */
72 let genericExceptions = new Map();
73
74 /**
75 * List of selectors that apply on any unknown domain
76 * @type {?string[]}
77 */
78 let conditionalGenericSelectors = null;
79
80 /**
81 * Domains that are known not to be specifically excluded from any generic
82 * filters
83 * @type {Set.<string>}
84 */
85 let genericFriendlyDomains = new Set();
86
87 /**
69 * Adds a filter to the lookup table of filters by domain. 88 * Adds a filter to the lookup table of filters by domain.
70 * @param {Filter} filter 89 * @param {Filter} filter
71 */ 90 */
72 function addToFiltersByDomain(filter) 91 function addToFiltersByDomain(filter)
73 { 92 {
74 let domains = filter.domains || defaultDomains; 93 let domains = filter.domains || defaultDomains;
75 for (let [domain, isIncluded] of domains) 94 if (filter instanceof ElemHideException)
76 { 95 {
77 // There's no need to note that a filter is generically disabled. 96 for (let domain of domains.keys())
78 if (!isIncluded && domain == "") 97 {
79 continue; 98 // Add an entry for each domain, but without any filters. This makes
80 99 // the domain "known" and helps us avoid certain optimizations that
100 // would otherwise yield incorrect results.
101 if (domain != "" && !filtersByDomain.has(domain))
102 filtersByDomain.set(domain, null);
103 }
104 }
105 else
106 {
107 for (let [domain, isIncluded] of domains)
108 {
109 // There's no need to note that a filter is generically disabled.
110 if (!isIncluded && domain == "")
111 continue;
112
113 let filters = filtersByDomain.get(domain);
114 if (!filters)
115 filtersByDomain.set(domain, filters = new Map());
116 filters.set(filter, isIncluded);
117 }
118 }
119 }
120
121 /**
122 * Returns a list of domain-specific filters matching a domain
123 * @param {string} [domain]
124 * @returns {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>}
125 */
126 function getSpecificFiltersForDomain(domain)
127 {
128 let filtersList = [];
129
130 if (domain)
131 domain = domain.toUpperCase();
132
133 while (domain)
134 {
81 let filters = filtersByDomain.get(domain); 135 let filters = filtersByDomain.get(domain);
82 if (!filters) 136 if (typeof filters != "undefined")
83 filtersByDomain.set(domain, filters = new Map()); 137 filtersList.push({domain, filters});
84 filters.set(filter, isIncluded); 138
85 } 139 let nextDot = domain.indexOf(".");
140 domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
141 }
142
143 return filtersList;
144 }
145
146 /**
147 * Returns a list of selectors that apply on a domain from a given list of
148 * filters
149 * @param {string} [domain]
150 * @param {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>} filtersList
151 * @param {Set.<Filter>} excludeSet
152 * @returns {string[]}
153 */
154 function matchSelectors(domain, filtersList, excludeSet)
155 {
156 let matches = [];
157
158 // This code is a performance hot-spot, which is why we've made certain
159 // micro-optimisations. Please be careful before making changes.
160 for (let i = 0; i < filtersList.length; i++)
161 {
162 let {filters} = filtersList[i];
163 if (filters)
164 {
165 for (let [filter, isIncluded] of filters)
166 {
167 if (!isIncluded)
168 {
169 excludeSet.add(filter);
170 }
171 else if ((excludeSet.size == 0 || !excludeSet.has(filter)) &&
172 !exports.ElemHide.getException(filter, domain))
173 {
174 matches.push(filter.selector);
175 }
176 }
177 }
178 }
179
180 return matches;
181 }
182
183 /**
184 * Returns a list of selectors that apply on a domain
185 * @param {string} [domain]
186 * @param {boolean} specificOnly
187 * @returns {string[]}
188 */
189 function getConditionalSelectorsForDomain(domain, specificOnly)
190 {
191 let specificFilters = getSpecificFiltersForDomain(domain);
192
193 // If there are no specific filters (nor any specific exceptions), we can
194 // just return the selectors from all the generic filters modulo any generic
195 // exceptions.
196 if (specificFilters.length == 0)
197 return specificOnly ? [] : getConditionalGenericSelectors();
198
199 let excludeSet = new Set();
200 let specificSelectors = matchSelectors(domain, specificFilters, excludeSet);
201
202 if (specificOnly)
203 return specificSelectors;
204
205 // We use the longest subdomain of this domain found in our data structures
206 // as the key to check if the domain is "generic friendly." For example,
207 // given foo.example.com, there may be an entry for example.com in our data
208 // structures (e.g. "example.com###foo"), so we use that subdomain as the
209 // key. This way we make only one entry and it works for all subdomains of
210 // example.com, except those that have specific entries
211 // (e.g. "~bar.example.com##.no-bar").
212 let domainKey = specificFilters[0].domain;
213
214 if (genericFriendlyDomains.has(domainKey))
215 return specificSelectors.concat(getConditionalGenericSelectors());
216
217 let genericFilters = [{filters: filtersByDomain.get("")}];
218 let genericSelectors = matchSelectors(domain, genericFilters, excludeSet);
219
220 // If the number of conditional generic selectors that apply on this domain
221 // is the same as the total number of conditional generic selectors, the
222 // domain is "generic friendly" (i.e. all generic filters apply, except those
223 // with generic exceptions). In that case, we mark it is as such for faster
224 // lookups.
225 if (genericSelectors.length == (conditionalGenericSelectors || {}).length)
226 genericFriendlyDomains.add(domainKey);
227
228 return specificSelectors.concat(genericSelectors);
229 }
230
231 /**
232 * Returns a list of selectors that apply on any unknown domain
233 * @returns {string[]}
234 */
235 function getConditionalGenericSelectors()
236 {
237 if (conditionalGenericSelectors)
238 return conditionalGenericSelectors;
239
240 conditionalGenericSelectors = [];
241
242 let filters = filtersByDomain.get("");
243 if (!filters)
244 return conditionalGenericSelectors;
245
246 for (let {selector} of filters.keys())
247 {
248 if (genericExceptions.size == 0 || !genericExceptions.has(selector))
249 conditionalGenericSelectors.push(selector);
250 }
251
252 return conditionalGenericSelectors;
86 } 253 }
87 254
88 /** 255 /**
89 * Returns a list of selectors that apply on each website unconditionally. 256 * Returns a list of selectors that apply on each website unconditionally.
90 * @returns {string[]} 257 * @returns {string[]}
91 */ 258 */
92 function getUnconditionalSelectors() 259 function getUnconditionalSelectors()
93 { 260 {
94 if (!unconditionalSelectors) 261 if (!unconditionalSelectors)
95 unconditionalSelectors = [...filterBySelector.keys()]; 262 unconditionalSelectors = [...filterBySelector.keys()];
96 263
97 return unconditionalSelectors; 264 return unconditionalSelectors;
98 } 265 }
99 266
100 /** 267 /**
101 * Container for element hiding filters 268 * Container for element hiding filters
102 * @class 269 * @class
103 */ 270 */
104 exports.ElemHide = { 271 exports.ElemHide = {
105 /** 272 /**
106 * Removes all known filters 273 * Removes all known filters
107 */ 274 */
108 clear() 275 clear()
109 { 276 {
110 for (let collection of [filtersByDomain, filterBySelector, 277 for (let collection of [filtersByDomain, filterBySelector,
111 knownFilters, exceptions]) 278 knownFilters, exceptions,
279 genericExceptions, genericFriendlyDomains])
112 { 280 {
113 collection.clear(); 281 collection.clear();
114 } 282 }
115 unconditionalSelectors = null; 283 unconditionalSelectors = null;
284 conditionalGenericSelectors = null;
116 FilterNotifier.emit("elemhideupdate"); 285 FilterNotifier.emit("elemhideupdate");
117 }, 286 },
118 287
119 /** 288 /**
120 * Add a new element hiding filter 289 * Add a new element hiding filter
121 * @param {ElemHideBase} filter 290 * @param {ElemHideBase} filter
122 */ 291 */
123 add(filter) 292 add(filter)
124 { 293 {
125 if (knownFilters.has(filter)) 294 if (knownFilters.has(filter))
126 return; 295 return;
127 296
297 conditionalGenericSelectors = null;
298 genericFriendlyDomains.clear();
299
128 if (filter instanceof ElemHideException) 300 if (filter instanceof ElemHideException)
129 { 301 {
130 let {selector} = filter; 302 let {selector, domains} = filter;
303
131 let list = exceptions.get(selector); 304 let list = exceptions.get(selector);
132 if (list) 305 if (list)
133 list.push(filter); 306 list.push(filter);
134 else 307 else
135 exceptions.set(selector, [filter]); 308 exceptions.set(selector, [filter]);
136 309
310 if (domains)
311 addToFiltersByDomain(filter);
312
313 if (filter.isGeneric())
314 {
315 list = genericExceptions.get(selector);
316 if (list)
317 list.push(filter);
318 else
319 genericExceptions.set(selector, [filter]);
320 }
321
137 // If this is the first exception for a previously unconditionally 322 // If this is the first exception for a previously unconditionally
138 // applied element hiding selector we need to take care to update the 323 // applied element hiding selector we need to take care to update the
139 // lookups. 324 // lookups.
140 let unconditionalFilterForSelector = filterBySelector.get(selector); 325 let unconditionalFilterForSelector = filterBySelector.get(selector);
141 if (unconditionalFilterForSelector) 326 if (unconditionalFilterForSelector)
142 { 327 {
143 addToFiltersByDomain(unconditionalFilterForSelector); 328 addToFiltersByDomain(unconditionalFilterForSelector);
144 filterBySelector.delete(selector); 329 filterBySelector.delete(selector);
145 unconditionalSelectors = null; 330 unconditionalSelectors = null;
146 } 331 }
(...skipping 16 matching lines...) Expand all
163 348
164 /** 349 /**
165 * Removes an element hiding filter 350 * Removes an element hiding filter
166 * @param {ElemHideBase} filter 351 * @param {ElemHideBase} filter
167 */ 352 */
168 remove(filter) 353 remove(filter)
169 { 354 {
170 if (!knownFilters.has(filter)) 355 if (!knownFilters.has(filter))
171 return; 356 return;
172 357
358 conditionalGenericSelectors = null;
359 genericFriendlyDomains.clear();
360
173 // Whitelisting filters 361 // Whitelisting filters
174 if (filter instanceof ElemHideException) 362 if (filter instanceof ElemHideException)
175 { 363 {
176 let list = exceptions.get(filter.selector); 364 let list = exceptions.get(filter.selector);
177 let index = list.indexOf(filter); 365 let index = list.indexOf(filter);
178 if (index >= 0) 366 if (index >= 0)
179 list.splice(index, 1); 367 list.splice(index, 1);
368
369 if (filter.isGeneric())
370 {
371 list = genericExceptions.get(filter.selector);
372 index = list.indexOf(filter);
373 if (index >= 0)
374 list.splice(index, 1);
375
376 // It's important to delete the entry here so the selector no longer
377 // appears to have any generic exceptions.
378 if (list.length == 0)
379 genericExceptions.delete(filter.selector);
380 }
180 } 381 }
181 // Unconditially applied element hiding filters 382 // Unconditially applied element hiding filters
182 else if (filterBySelector.get(filter.selector) == filter) 383 else if (filterBySelector.get(filter.selector) == filter)
183 { 384 {
184 filterBySelector.delete(filter.selector); 385 filterBySelector.delete(filter.selector);
185 unconditionalSelectors = null; 386 unconditionalSelectors = null;
186 } 387 }
187 // Conditionally applied element hiding filters 388 // Conditionally applied element hiding filters
188 else 389 else
189 { 390 {
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
224 425
225 /** 426 /**
226 * Determines from the current filter list which selectors should be applied 427 * Determines from the current filter list which selectors should be applied
227 * on a particular host name. 428 * on a particular host name.
228 * @param {string} domain 429 * @param {string} domain
229 * @param {boolean} [specificOnly] true if generic filters should not apply. 430 * @param {boolean} [specificOnly] true if generic filters should not apply.
230 * @returns {string[]} List of selectors. 431 * @returns {string[]} List of selectors.
231 */ 432 */
232 getSelectorsForDomain(domain, specificOnly = false) 433 getSelectorsForDomain(domain, specificOnly = false)
233 { 434 {
234 let selectors = []; 435 let selectors = getConditionalSelectorsForDomain(domain, specificOnly);
235
236 let excluded = new Set();
237 let currentDomain = domain ? domain.toUpperCase() : "";
238
239 // This code is a performance hot-spot, which is why we've made certain
240 // micro-optimisations. Please be careful before making changes.
241 while (true)
242 {
243 if (specificOnly && currentDomain == "")
244 break;
245
246 let filters = filtersByDomain.get(currentDomain);
247 if (filters)
248 {
249 for (let [filter, isIncluded] of filters)
250 {
251 if (!isIncluded)
252 {
253 excluded.add(filter);
254 }
255 else if ((excluded.size == 0 || !excluded.has(filter)) &&
256 !this.getException(filter, domain))
257 {
258 selectors.push(filter.selector);
259 }
260 }
261 }
262
263 if (currentDomain == "")
264 break;
265
266 let nextDot = currentDomain.indexOf(".");
267 currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
268 }
269 436
270 if (!specificOnly) 437 if (!specificOnly)
271 selectors = getUnconditionalSelectors().concat(selectors); 438 selectors = getUnconditionalSelectors().concat(selectors);
272 439
273 return selectors; 440 return selectors;
274 } 441 }
275 }; 442 };
OLDNEW
« 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