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: Strip out optimization for "generic-friendly" domains Created May 23, 2018, 12:02 a.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 /**
69 * Adds a filter to the lookup table of filters by domain. 81 * Adds a filter to the lookup table of filters by domain.
70 * @param {Filter} filter 82 * @param {Filter} filter
71 */ 83 */
72 function addToFiltersByDomain(filter) 84 function addToFiltersByDomain(filter)
73 { 85 {
74 let domains = filter.domains || defaultDomains; 86 let domains = filter.domains || defaultDomains;
75 for (let [domain, isIncluded] of domains) 87 if (filter instanceof ElemHideException)
76 { 88 {
77 // There's no need to note that a filter is generically disabled. 89 for (let domain of domains.keys())
78 if (!isIncluded && domain == "") 90 {
79 continue; 91 // Add an entry for each domain, but without any filters. This makes
92 // the domain "known" and helps us avoid certain optimizations that
93 // would otherwise yield incorrect results.
94 if (domain != "" && !filtersByDomain.has(domain))
95 filtersByDomain.set(domain, null);
96 }
97 }
98 else
99 {
100 for (let [domain, isIncluded] of domains)
101 {
102 // There's no need to note that a filter is generically disabled.
103 if (!isIncluded && domain == "")
104 continue;
80 105
106 let filters = filtersByDomain.get(domain);
107 if (!filters)
108 filtersByDomain.set(domain, filters = new Map());
109 filters.set(filter, isIncluded);
110 }
111 }
112 }
113
114 /**
115 * Returns a list of domain-specific filters matching a domain
116 * @param {string} [domain]
117 * @returns {Array.<?Map.<Filter,boolean>>}
118 */
119 function getSpecificFiltersForDomain(domain)
120 {
121 let filtersList = [];
122
123 if (domain)
124 domain = domain.toUpperCase();
125
126 while (domain)
127 {
81 let filters = filtersByDomain.get(domain); 128 let filters = filtersByDomain.get(domain);
82 if (!filters) 129 if (typeof filters != "undefined")
83 filtersByDomain.set(domain, filters = new Map()); 130 filtersList.push(filters);
84 filters.set(filter, isIncluded); 131
132 let nextDot = domain.indexOf(".");
133 domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
85 } 134 }
135
136 return filtersList;
137 }
138
139 /**
140 * Returns a list of selectors that apply on a domain from a given list of
141 * filters
142 * @param {string} [domain]
143 * @param {?Array.<?Map.<Filter,boolean>>} filtersList
144 * @param {Set.<Filter>} excludeSet
145 * @returns {string[]}
146 */
147 function matchSelectors(domain, filtersList, excludeSet)
148 {
149 let matches = [];
150
151 // This code is a performance hot-spot, which is why we've made certain
152 // micro-optimisations. Please be careful before making changes.
153 for (let i = 0; i < filtersList.length; i++)
154 {
155 let filters = filtersList[i];
156 if (filters)
157 {
158 for (let [filter, isIncluded] of filters)
159 {
160 if (!isIncluded)
161 {
162 excludeSet.add(filter);
163 }
164 else if ((excludeSet.size == 0 || !excludeSet.has(filter)) &&
165 !exports.ElemHide.getException(filter, domain))
166 {
167 matches.push(filter.selector);
168 }
169 }
170 }
171 }
172
173 return matches;
174 }
175
176 /**
177 * Returns a list of selectors that apply on any unknown domain
178 * @returns {string[]}
179 */
180 function getConditionalGenericSelectors()
181 {
182 if (conditionalGenericSelectors)
183 return conditionalGenericSelectors;
184
185 conditionalGenericSelectors = [];
186
187 let filters = filtersByDomain.get("");
188 if (!filters)
189 return conditionalGenericSelectors;
190
191 for (let {selector} of filters.keys())
192 {
193 if (genericExceptions.size == 0 || !genericExceptions.has(selector))
194 conditionalGenericSelectors.push(selector);
195 }
196
197 return conditionalGenericSelectors;
86 } 198 }
87 199
88 /** 200 /**
89 * Returns a list of selectors that apply on each website unconditionally. 201 * Returns a list of selectors that apply on each website unconditionally.
90 * @returns {string[]} 202 * @returns {string[]}
91 */ 203 */
92 function getUnconditionalSelectors() 204 function getUnconditionalSelectors()
93 { 205 {
94 if (!unconditionalSelectors) 206 if (!unconditionalSelectors)
95 unconditionalSelectors = [...filterBySelector.keys()]; 207 unconditionalSelectors = [...filterBySelector.keys()];
96 208
97 return unconditionalSelectors; 209 return unconditionalSelectors;
98 } 210 }
99 211
100 /** 212 /**
101 * Container for element hiding filters 213 * Container for element hiding filters
102 * @class 214 * @class
103 */ 215 */
104 exports.ElemHide = { 216 exports.ElemHide = {
105 /** 217 /**
106 * Removes all known filters 218 * Removes all known filters
107 */ 219 */
108 clear() 220 clear()
109 { 221 {
110 for (let collection of [filtersByDomain, filterBySelector, 222 for (let collection of [filtersByDomain, filterBySelector,
111 knownFilters, exceptions]) 223 knownFilters, exceptions,
224 genericExceptions])
112 { 225 {
113 collection.clear(); 226 collection.clear();
114 } 227 }
115 unconditionalSelectors = null; 228 unconditionalSelectors = null;
229 conditionalGenericSelectors = null;
116 FilterNotifier.emit("elemhideupdate"); 230 FilterNotifier.emit("elemhideupdate");
117 }, 231 },
118 232
119 /** 233 /**
120 * Add a new element hiding filter 234 * Add a new element hiding filter
121 * @param {ElemHideBase} filter 235 * @param {ElemHideBase} filter
122 */ 236 */
123 add(filter) 237 add(filter)
124 { 238 {
125 if (knownFilters.has(filter)) 239 if (knownFilters.has(filter))
126 return; 240 return;
127 241
242 conditionalGenericSelectors = null;
243
128 if (filter instanceof ElemHideException) 244 if (filter instanceof ElemHideException)
129 { 245 {
130 let {selector} = filter; 246 let {selector, domains} = filter;
247
131 let list = exceptions.get(selector); 248 let list = exceptions.get(selector);
132 if (list) 249 if (list)
133 list.push(filter); 250 list.push(filter);
134 else 251 else
135 exceptions.set(selector, [filter]); 252 exceptions.set(selector, [filter]);
136 253
254 if (domains)
255 addToFiltersByDomain(filter);
256
257 if (filter.isGeneric())
258 {
259 list = genericExceptions.get(selector);
260 if (list)
261 list.push(filter);
262 else
263 genericExceptions.set(selector, [filter]);
264 }
265
137 // If this is the first exception for a previously unconditionally 266 // If this is the first exception for a previously unconditionally
138 // applied element hiding selector we need to take care to update the 267 // applied element hiding selector we need to take care to update the
139 // lookups. 268 // lookups.
140 let unconditionalFilterForSelector = filterBySelector.get(selector); 269 let unconditionalFilterForSelector = filterBySelector.get(selector);
141 if (unconditionalFilterForSelector) 270 if (unconditionalFilterForSelector)
142 { 271 {
143 addToFiltersByDomain(unconditionalFilterForSelector); 272 addToFiltersByDomain(unconditionalFilterForSelector);
144 filterBySelector.delete(selector); 273 filterBySelector.delete(selector);
145 unconditionalSelectors = null; 274 unconditionalSelectors = null;
146 } 275 }
(...skipping 16 matching lines...) Expand all
163 292
164 /** 293 /**
165 * Removes an element hiding filter 294 * Removes an element hiding filter
166 * @param {ElemHideBase} filter 295 * @param {ElemHideBase} filter
167 */ 296 */
168 remove(filter) 297 remove(filter)
169 { 298 {
170 if (!knownFilters.has(filter)) 299 if (!knownFilters.has(filter))
171 return; 300 return;
172 301
302 conditionalGenericSelectors = null;
303
173 // Whitelisting filters 304 // Whitelisting filters
174 if (filter instanceof ElemHideException) 305 if (filter instanceof ElemHideException)
175 { 306 {
176 let list = exceptions.get(filter.selector); 307 let list = exceptions.get(filter.selector);
177 let index = list.indexOf(filter); 308 let index = list.indexOf(filter);
178 if (index >= 0) 309 if (index >= 0)
179 list.splice(index, 1); 310 list.splice(index, 1);
311
312 if (filter.isGeneric())
313 {
314 list = genericExceptions.get(filter.selector);
315 index = list.indexOf(filter);
316 if (index >= 0)
317 list.splice(index, 1);
318
319 // It's important to delete the entry here so the selector no longer
320 // appears to have any generic exceptions.
321 if (list.length == 0)
322 genericExceptions.delete(filter.selector);
323 }
180 } 324 }
181 // Unconditially applied element hiding filters 325 // Unconditially applied element hiding filters
182 else if (filterBySelector.get(filter.selector) == filter) 326 else if (filterBySelector.get(filter.selector) == filter)
183 { 327 {
184 filterBySelector.delete(filter.selector); 328 filterBySelector.delete(filter.selector);
185 unconditionalSelectors = null; 329 unconditionalSelectors = null;
186 } 330 }
187 // Conditionally applied element hiding filters 331 // Conditionally applied element hiding filters
188 else 332 else
189 { 333 {
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
224 368
225 /** 369 /**
226 * Determines from the current filter list which selectors should be applied 370 * Determines from the current filter list which selectors should be applied
227 * on a particular host name. 371 * on a particular host name.
228 * @param {string} domain 372 * @param {string} domain
229 * @param {boolean} [specificOnly] true if generic filters should not apply. 373 * @param {boolean} [specificOnly] true if generic filters should not apply.
230 * @returns {string[]} List of selectors. 374 * @returns {string[]} List of selectors.
231 */ 375 */
232 getSelectorsForDomain(domain, specificOnly = false) 376 getSelectorsForDomain(domain, specificOnly = false)
233 { 377 {
234 let selectors = []; 378 let specificFilters = getSpecificFiltersForDomain(domain);
379
380 // If there are no specific filters (nor any specific exceptions), we can
381 // just return the selectors from all the generic filters modulo any
382 // generic exceptions.
383 if (specificFilters.length == 0)
384 {
385 return specificOnly ? [] :
386 getUnconditionalSelectors()
387 .concat(getConditionalGenericSelectors());
388 }
235 389
236 let excluded = new Set(); 390 let excluded = new Set();
237 let currentDomain = domain ? domain.toUpperCase() : ""; 391 let selectors = matchSelectors(domain, specificFilters, excluded);
238 392
239 // This code is a performance hot-spot, which is why we've made certain 393 if (specificOnly)
240 // micro-optimisations. Please be careful before making changes. 394 return selectors;
241 while (true)
242 {
243 if (specificOnly && currentDomain == "")
244 break;
245 395
246 let filters = filtersByDomain.get(currentDomain); 396 let genericFilters = [filtersByDomain.get("")];
247 if (filters) 397 selectors = selectors.concat(matchSelectors(domain, genericFilters,
248 { 398 excluded));
249 for (let [filter, isIncluded] of filters) 399 return getUnconditionalSelectors().concat(selectors);
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
270 if (!specificOnly)
271 selectors = getUnconditionalSelectors().concat(selectors);
272
273 return selectors;
274 } 400 }
275 }; 401 };
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