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

Delta Between Two Patch Sets: lib/elemHide.js

Issue 29773570: Issue 6652 - Implement fast selector lookups for unknown domains (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore/
Left Patch Set: Reinclude test/elemHide.js Created May 15, 2018, 4:26 p.m.
Right Patch Set: Avoid unnecessary Array.concat Created May 23, 2018, 12:22 a.m.
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « no previous file | test/elemHide.js » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
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
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after
71 */ 71 */
72 let genericExceptions = new Map(); 72 let genericExceptions = new Map();
73 73
74 /** 74 /**
75 * List of selectors that apply on any unknown domain 75 * List of selectors that apply on any unknown domain
76 * @type {?string[]} 76 * @type {?string[]}
77 */ 77 */
78 let conditionalGenericSelectors = null; 78 let conditionalGenericSelectors = null;
79 79
80 /** 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 /**
88 * Adds a filter to the lookup table of filters by domain. 81 * Adds a filter to the lookup table of filters by domain.
89 * @param {Filter} filter 82 * @param {Filter} filter
90 */ 83 */
91 function addToFiltersByDomain(filter) 84 function addToFiltersByDomain(filter)
92 { 85 {
93 let domains = filter.domains || defaultDomains; 86 let domains = filter.domains || defaultDomains;
94 if (filter instanceof ElemHideException) 87 if (filter instanceof ElemHideException)
95 { 88 {
96 for (let domain of domains.keys()) 89 for (let domain of domains.keys())
97 { 90 {
(...skipping 16 matching lines...) Expand all
114 if (!filters) 107 if (!filters)
115 filtersByDomain.set(domain, filters = new Map()); 108 filtersByDomain.set(domain, filters = new Map());
116 filters.set(filter, isIncluded); 109 filters.set(filter, isIncluded);
117 } 110 }
118 } 111 }
119 } 112 }
120 113
121 /** 114 /**
122 * Returns a list of domain-specific filters matching a domain 115 * Returns a list of domain-specific filters matching a domain
123 * @param {string} [domain] 116 * @param {string} [domain]
124 * @returns {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>} 117 * @returns {Array.<?Map.<Filter,boolean>>}
125 */ 118 */
126 function getSpecificFiltersForDomain(domain) 119 function getSpecificFiltersForDomain(domain)
127 { 120 {
128 let filtersList = []; 121 let filtersList = [];
129 122
130 if (domain) 123 if (domain)
131 domain = domain.toUpperCase(); 124 domain = domain.toUpperCase();
132 125
133 while (domain) 126 while (domain)
134 { 127 {
135 let filters = filtersByDomain.get(domain); 128 let filters = filtersByDomain.get(domain);
136 if (typeof filters != "undefined") 129 if (typeof filters != "undefined")
137 filtersList.push({domain, filters}); 130 filtersList.push(filters);
138 131
139 let nextDot = domain.indexOf("."); 132 let nextDot = domain.indexOf(".");
140 domain = nextDot == -1 ? null : domain.substring(nextDot + 1); 133 domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
141 } 134 }
142 135
143 return filtersList; 136 return filtersList;
144 } 137 }
145 138
146 /** 139 /**
147 * Returns a list of selectors that apply on a domain from a given list of 140 * Returns a list of selectors that apply on a domain from a given list of
148 * filters 141 * filters
149 * @param {string} [domain] 142 * @param {string} [domain]
150 * @param {Array.<{domain: string, filters: ?Map.<Filter,boolean>}>} filtersList 143 * @param {Array.<?Map.<Filter,boolean>>} filtersList
151 * @param {Set.<Filter>} excludeSet 144 * @param {Set.<Filter>} excludeSet
152 * @returns {string[]} 145 * @returns {string[]}
153 */ 146 */
154 function matchSelectors(domain, filtersList, excludeSet) 147 function matchSelectors(domain, filtersList, excludeSet)
155 { 148 {
156 let matches = []; 149 let matches = [];
157 150
158 // This code is a performance hot-spot, which is why we've made certain 151 // This code is a performance hot-spot, which is why we've made certain
159 // micro-optimisations. Please be careful before making changes. 152 // micro-optimisations. Please be careful before making changes.
160 for (let i = 0; i < filtersList.length; i++) 153 for (let i = 0; i < filtersList.length; i++)
161 { 154 {
162 let {filters} = filtersList[i]; 155 let filters = filtersList[i];
163 if (filters) 156 if (filters)
164 { 157 {
165 for (let [filter, isIncluded] of filters) 158 for (let [filter, isIncluded] of filters)
166 { 159 {
167 if (!isIncluded) 160 if (!isIncluded)
168 { 161 {
169 excludeSet.add(filter); 162 excludeSet.add(filter);
170 } 163 }
171 else if ((excludeSet.size == 0 || !excludeSet.has(filter)) && 164 else if ((excludeSet.size == 0 || !excludeSet.has(filter)) &&
172 !exports.ElemHide.getException(filter, domain)) 165 !exports.ElemHide.getException(filter, domain))
173 { 166 {
174 matches.push(filter.selector); 167 matches.push(filter.selector);
175 } 168 }
176 } 169 }
177 } 170 }
178 } 171 }
179 172
180 return matches; 173 return matches;
181 } 174 }
182 175
183 /** 176 /**
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 177 * Returns a list of selectors that apply on any unknown domain
233 * @returns {string[]} 178 * @returns {string[]}
234 */ 179 */
235 function getConditionalGenericSelectors() 180 function getConditionalGenericSelectors()
236 { 181 {
237 if (conditionalGenericSelectors) 182 if (conditionalGenericSelectors)
238 return conditionalGenericSelectors; 183 return conditionalGenericSelectors;
239 184
240 conditionalGenericSelectors = []; 185 conditionalGenericSelectors = [];
241 186
(...skipping 27 matching lines...) Expand all
269 * @class 214 * @class
270 */ 215 */
271 exports.ElemHide = { 216 exports.ElemHide = {
272 /** 217 /**
273 * Removes all known filters 218 * Removes all known filters
274 */ 219 */
275 clear() 220 clear()
276 { 221 {
277 for (let collection of [filtersByDomain, filterBySelector, 222 for (let collection of [filtersByDomain, filterBySelector,
278 knownFilters, exceptions, 223 knownFilters, exceptions,
279 genericExceptions, genericFriendlyDomains]) 224 genericExceptions])
280 { 225 {
281 collection.clear(); 226 collection.clear();
282 } 227 }
283 unconditionalSelectors = null; 228 unconditionalSelectors = null;
284 conditionalGenericSelectors = null; 229 conditionalGenericSelectors = null;
285 FilterNotifier.emit("elemhideupdate"); 230 FilterNotifier.emit("elemhideupdate");
286 }, 231 },
287 232
288 /** 233 /**
289 * Add a new element hiding filter 234 * Add a new element hiding filter
290 * @param {ElemHideBase} filter 235 * @param {ElemHideBase} filter
291 */ 236 */
292 add(filter) 237 add(filter)
293 { 238 {
294 if (knownFilters.has(filter)) 239 if (knownFilters.has(filter))
295 return; 240 return;
296 241
297 conditionalGenericSelectors = null; 242 conditionalGenericSelectors = null;
298 genericFriendlyDomains.clear();
299 243
300 if (filter instanceof ElemHideException) 244 if (filter instanceof ElemHideException)
301 { 245 {
302 let {selector, domains} = filter; 246 let {selector, domains} = filter;
303 247
304 let list = exceptions.get(selector); 248 let list = exceptions.get(selector);
305 if (list) 249 if (list)
306 list.push(filter); 250 list.push(filter);
307 else 251 else
308 exceptions.set(selector, [filter]); 252 exceptions.set(selector, [filter]);
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after
349 /** 293 /**
350 * Removes an element hiding filter 294 * Removes an element hiding filter
351 * @param {ElemHideBase} filter 295 * @param {ElemHideBase} filter
352 */ 296 */
353 remove(filter) 297 remove(filter)
354 { 298 {
355 if (!knownFilters.has(filter)) 299 if (!knownFilters.has(filter))
356 return; 300 return;
357 301
358 conditionalGenericSelectors = null; 302 conditionalGenericSelectors = null;
359 genericFriendlyDomains.clear();
360 303
361 // Whitelisting filters 304 // Whitelisting filters
362 if (filter instanceof ElemHideException) 305 if (filter instanceof ElemHideException)
363 { 306 {
364 let list = exceptions.get(filter.selector); 307 let list = exceptions.get(filter.selector);
365 let index = list.indexOf(filter); 308 let index = list.indexOf(filter);
366 if (index >= 0) 309 if (index >= 0)
367 list.splice(index, 1); 310 list.splice(index, 1);
368 311
369 if (filter.isGeneric()) 312 if (filter.isGeneric())
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after
425 368
426 /** 369 /**
427 * Determines from the current filter list which selectors should be applied 370 * Determines from the current filter list which selectors should be applied
428 * on a particular host name. 371 * on a particular host name.
429 * @param {string} domain 372 * @param {string} domain
430 * @param {boolean} [specificOnly] true if generic filters should not apply. 373 * @param {boolean} [specificOnly] true if generic filters should not apply.
431 * @returns {string[]} List of selectors. 374 * @returns {string[]} List of selectors.
432 */ 375 */
433 getSelectorsForDomain(domain, specificOnly = false) 376 getSelectorsForDomain(domain, specificOnly = false)
434 { 377 {
435 let selectors = getConditionalSelectorsForDomain(domain, specificOnly); 378 let specificFilters = getSpecificFiltersForDomain(domain);
436 379
437 if (!specificOnly) 380 // If there are no specific filters (nor any specific exceptions), we can
438 selectors = getUnconditionalSelectors().concat(selectors); 381 // just return the selectors from all the generic filters modulo any
439 382 // generic exceptions.
440 return selectors; 383 if (specificFilters.length == 0)
384 {
385 return specificOnly ? [] :
386 getUnconditionalSelectors()
387 .concat(getConditionalGenericSelectors());
388 }
389
390 let excluded = new Set();
391 let selectors = matchSelectors(domain, specificFilters, excluded);
392
393 if (specificOnly)
394 return selectors;
395
396 return getUnconditionalSelectors()
397 .concat(selectors,
398 matchSelectors(domain, [filtersByDomain.get("")],
399 excluded));
441 } 400 }
442 }; 401 };
LEFTRIGHT
« no previous file | test/elemHide.js » ('j') | Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Toggle Comments ('s')

Powered by Google App Engine
This is Rietveld