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

Side by Side Diff: lib/elemHide.js

Issue 29743730: Issue 6559 - Use maps and sets where appropriate (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore/
Patch Set: Revert logic in getUnconditionalFilterKeys Created April 6, 2018, 1:32 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 | « lib/downloader.js ('k') | lib/elemHideEmulation.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, filters by their associated key 28 * Lookup table, filters by their associated key
29 * @type {Object} 29 * @type {Filter[]}
30 */ 30 */
31 let filterByKey = []; 31 let filterByKey = [];
32 32
33 /** 33 /**
34 * Lookup table, keys of the filters by filter 34 * Lookup table, keys of the filters by filter
35 * @type {Map.<Filter,string>} 35 * @type {Map.<Filter,number>}
36 */ 36 */
37 let keyByFilter = new Map(); 37 let keyByFilter = new Map();
38 38
39 /** 39 /**
40 * Nested lookup table, filter (or false if inactive) by filter key by domain. 40 * Nested lookup table, filter (or false if inactive) by filter key by domain.
41 * (Only contains filters that aren't unconditionally matched for all domains.) 41 * (Only contains filters that aren't unconditionally matched for all domains.)
42 * @type {Map.<string,Map.<string,(Filter|boolean)>>} 42 * @type {Map.<string,Map.<number,(Filter|boolean)>>}
43 */ 43 */
44 let filtersByDomain = new Map(); 44 let filtersByDomain = new Map();
45 45
46 /** 46 /**
47 * Lookup table, filter key by selector. (Only used for selectors that are 47 * Lookup table, filter key by selector. (Only used for selectors that are
48 * unconditionally matched for all domains.) 48 * unconditionally matched for all domains.)
49 * @type {Map.<string,number>}
49 */ 50 */
50 let filterKeyBySelector = Object.create(null); 51 let filterKeyBySelector = new Map();
51 52
52 /** 53 /**
53 * This array caches the keys of filterKeyBySelector table (selectors which 54 * This array caches the keys of filterKeyBySelector table (selectors which
54 * unconditionally apply on all domains). It will be null if the cache needs to 55 * unconditionally apply on all domains). It will be null if the cache needs to
55 * be rebuilt. 56 * be rebuilt.
56 */ 57 */
57 let unconditionalSelectors = null; 58 let unconditionalSelectors = null;
58 59
59 /** 60 /**
60 * This array caches the values of filterKeyBySelector table (filterIds for 61 * This array caches the values of filterKeyBySelector table (filterIds for
61 * selectors which unconditionally apply on all domains). It will be null if the 62 * selectors which unconditionally apply on all domains). It will be null if the
62 * cache needs to be rebuilt. 63 * cache needs to be rebuilt.
63 */ 64 */
64 let unconditionalFilterKeys = null; 65 let unconditionalFilterKeys = null;
65 66
66 /** 67 /**
67 * Object to be used instead when a filter has a blank domains property. 68 * Object to be used instead when a filter has a blank domains property.
68 */ 69 */
69 let defaultDomains = new Map([["", true]]); 70 let defaultDomains = new Map([["", true]]);
70 71
71 /** 72 /**
72 * Lookup table, keys are known element hiding exceptions 73 * Set containing known element hiding exceptions
73 * @type {Object} 74 * @type {Set.<string>}
74 */ 75 */
75 let knownExceptions = Object.create(null); 76 let knownExceptions = new Set();
76 77
77 /** 78 /**
78 * Lookup table, lists of element hiding exceptions by selector 79 * Lookup table, lists of element hiding exceptions by selector
79 * @type {Object} 80 * @type {Map.<string,Filter>}
80 */ 81 */
81 let exceptions = Object.create(null); 82 let exceptions = new Map();
82 83
83 /** 84 /**
84 * Container for element hiding filters 85 * Container for element hiding filters
85 * @class 86 * @class
86 */ 87 */
87 let ElemHide = exports.ElemHide = { 88 let ElemHide = exports.ElemHide = {
88 /** 89 /**
89 * Removes all known filters 90 * Removes all known filters
90 */ 91 */
91 clear() 92 clear()
92 { 93 {
94 for (let collection of [keyByFilter, filtersByDomain, filterKeyBySelector,
95 knownExceptions, exceptions])
96 {
97 collection.clear();
98 }
93 filterByKey = []; 99 filterByKey = [];
94 keyByFilter = new Map();
95 filtersByDomain = new Map();
96 filterKeyBySelector = Object.create(null);
97 unconditionalSelectors = unconditionalFilterKeys = null; 100 unconditionalSelectors = unconditionalFilterKeys = null;
98 knownExceptions = Object.create(null);
99 exceptions = Object.create(null);
100 FilterNotifier.emit("elemhideupdate"); 101 FilterNotifier.emit("elemhideupdate");
101 }, 102 },
102 103
103 _addToFiltersByDomain(key, filter) 104 _addToFiltersByDomain(key, filter)
104 { 105 {
105 let domains = filter.domains || defaultDomains; 106 let domains = filter.domains || defaultDomains;
106 for (let [domain, isIncluded] of domains) 107 for (let [domain, isIncluded] of domains)
107 { 108 {
108 let filters = filtersByDomain.get(domain); 109 let filters = filtersByDomain.get(domain);
109 if (!filters) 110 if (!filters)
110 filtersByDomain.set(domain, filters = new Map()); 111 filtersByDomain.set(domain, filters = new Map());
111 filters.set(key, isIncluded ? filter : false); 112 filters.set(key, isIncluded ? filter : false);
112 } 113 }
113 }, 114 },
114 115
115 /** 116 /**
116 * Add a new element hiding filter 117 * Add a new element hiding filter
117 * @param {ElemHideFilter} filter 118 * @param {ElemHideFilter} filter
118 */ 119 */
119 add(filter) 120 add(filter)
120 { 121 {
121 if (filter instanceof ElemHideException) 122 if (filter instanceof ElemHideException)
122 { 123 {
123 if (filter.text in knownExceptions) 124 if (knownExceptions.has(filter.text))
124 return; 125 return;
125 126
126 let {selector} = filter; 127 let {selector} = filter;
127 if (!(selector in exceptions)) 128 let list = exceptions.get(selector);
128 exceptions[selector] = []; 129 if (list)
129 exceptions[selector].push(filter); 130 list.push(filter);
131 else
132 exceptions.set(selector, [filter]);
130 133
131 // If this is the first exception for a previously unconditionally 134 // If this is the first exception for a previously unconditionally
132 // applied element hiding selector we need to take care to update the 135 // applied element hiding selector we need to take care to update the
133 // lookups. 136 // lookups.
134 let filterKey = filterKeyBySelector[selector]; 137 let filterKey = filterKeyBySelector.get(selector);
135 if (typeof filterKey != "undefined") 138 if (typeof filterKey != "undefined")
136 { 139 {
137 this._addToFiltersByDomain(filterKey, filterByKey[filterKey]); 140 this._addToFiltersByDomain(filterKey, filterByKey[filterKey]);
138 delete filterKeyBySelector[selector]; 141 filterKeyBySelector.delete(selector);
139 unconditionalSelectors = unconditionalFilterKeys = null; 142 unconditionalSelectors = unconditionalFilterKeys = null;
140 } 143 }
141 144
142 knownExceptions[filter.text] = true; 145 knownExceptions.add(filter.text);
143 } 146 }
144 else 147 else
145 { 148 {
146 if (keyByFilter.has(filter)) 149 if (keyByFilter.has(filter))
147 return; 150 return;
148 151
149 let key = filterByKey.push(filter) - 1; 152 let key = filterByKey.push(filter) - 1;
150 keyByFilter.set(filter, key); 153 keyByFilter.set(filter, key);
151 154
152 if (!(filter.domains || filter.selector in exceptions)) 155 if (!(filter.domains || exceptions.has(filter.selector)))
153 { 156 {
154 // The new filter's selector is unconditionally applied to all domains 157 // The new filter's selector is unconditionally applied to all domains
155 filterKeyBySelector[filter.selector] = key; 158 filterKeyBySelector.set(filter.selector, key);
156 unconditionalSelectors = unconditionalFilterKeys = null; 159 unconditionalSelectors = unconditionalFilterKeys = null;
157 } 160 }
158 else 161 else
159 { 162 {
160 // The new filter's selector only applies to some domains 163 // The new filter's selector only applies to some domains
161 this._addToFiltersByDomain(key, filter); 164 this._addToFiltersByDomain(key, filter);
162 } 165 }
163 } 166 }
164 167
165 FilterNotifier.emit("elemhideupdate"); 168 FilterNotifier.emit("elemhideupdate");
166 }, 169 },
167 170
168 _removeFilterKey(key, filter) 171 _removeFilterKey(key, filter)
169 { 172 {
170 if (filterKeyBySelector[filter.selector] == key) 173 if (filterKeyBySelector.get(filter.selector) == key)
171 { 174 {
172 delete filterKeyBySelector[filter.selector]; 175 filterKeyBySelector.delete(filter.selector);
173 unconditionalSelectors = unconditionalFilterKeys = null; 176 unconditionalSelectors = unconditionalFilterKeys = null;
174 return; 177 return;
175 } 178 }
176 179
177 // We haven't found this filter in unconditional filters, look in 180 // We haven't found this filter in unconditional filters, look in
178 // filtersByDomain. 181 // filtersByDomain.
179 let domains = filter.domains || defaultDomains; 182 let domains = filter.domains || defaultDomains;
180 for (let domain of domains.keys()) 183 for (let domain of domains.keys())
181 { 184 {
182 let filters = filtersByDomain.get(domain); 185 let filters = filtersByDomain.get(domain);
183 if (filters) 186 if (filters)
184 filters.delete(key); 187 filters.delete(key);
185 } 188 }
186 }, 189 },
187 190
188 /** 191 /**
189 * Removes an element hiding filter 192 * Removes an element hiding filter
190 * @param {ElemHideFilter} filter 193 * @param {ElemHideFilter} filter
191 */ 194 */
192 remove(filter) 195 remove(filter)
193 { 196 {
194 if (filter instanceof ElemHideException) 197 if (filter instanceof ElemHideException)
195 { 198 {
196 if (!(filter.text in knownExceptions)) 199 if (!knownExceptions.has(filter.text))
197 return; 200 return;
198 201
199 let list = exceptions[filter.selector]; 202 let list = exceptions.get(filter.selector);
200 let index = list.indexOf(filter); 203 let index = list.indexOf(filter);
201 if (index >= 0) 204 if (index >= 0)
202 list.splice(index, 1); 205 list.splice(index, 1);
203 delete knownExceptions[filter.text]; 206 knownExceptions.delete(filter.text);
204 } 207 }
205 else 208 else
206 { 209 {
207 let key = keyByFilter.get(filter); 210 let key = keyByFilter.get(filter);
208 if (typeof key == "undefined") 211 if (typeof key == "undefined")
209 return; 212 return;
210 213
211 delete filterByKey[key]; 214 delete filterByKey[key];
212 keyByFilter.delete(filter); 215 keyByFilter.delete(filter);
213 this._removeFilterKey(key, filter); 216 this._removeFilterKey(key, filter);
214 } 217 }
215 218
216 FilterNotifier.emit("elemhideupdate"); 219 FilterNotifier.emit("elemhideupdate");
217 }, 220 },
218 221
219 /** 222 /**
220 * Checks whether an exception rule is registered for a filter on a particular 223 * Checks whether an exception rule is registered for a filter on a particular
221 * domain. 224 * domain.
222 * @param {Filter} filter 225 * @param {Filter} filter
223 * @param {string} docDomain 226 * @param {string} docDomain
224 * @return {ElemHideException} 227 * @return {ElemHideException}
225 */ 228 */
226 getException(filter, docDomain) 229 getException(filter, docDomain)
227 { 230 {
228 if (!(filter.selector in exceptions)) 231 let list = exceptions.get(filter.selector);
232 if (!list)
229 return null; 233 return null;
230 234
231 let list = exceptions[filter.selector];
232 for (let i = list.length - 1; i >= 0; i--) 235 for (let i = list.length - 1; i >= 0; i--)
233 { 236 {
234 if (list[i].isActiveOnDomain(docDomain)) 237 if (list[i].isActiveOnDomain(docDomain))
235 return list[i]; 238 return list[i];
236 } 239 }
237 240
238 return null; 241 return null;
239 }, 242 },
240 243
241 /** 244 /**
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
274 return domains; 277 return domains;
275 }, 278 },
276 279
277 /** 280 /**
278 * Returns a list of selectors that apply on each website unconditionally. 281 * Returns a list of selectors that apply on each website unconditionally.
279 * @returns {string[]} 282 * @returns {string[]}
280 */ 283 */
281 getUnconditionalSelectors() 284 getUnconditionalSelectors()
282 { 285 {
283 if (!unconditionalSelectors) 286 if (!unconditionalSelectors)
284 unconditionalSelectors = Object.keys(filterKeyBySelector); 287 unconditionalSelectors = [...filterKeyBySelector.keys()];
285 return unconditionalSelectors.slice(); 288 return unconditionalSelectors.slice();
286 }, 289 },
287 290
288 /** 291 /**
289 * Returns a list of filter keys for selectors which apply to all websites 292 * Returns a list of filter keys for selectors which apply to all websites
290 * without exception. 293 * without exception.
291 * @returns {number[]} 294 * @returns {number[]}
292 */ 295 */
293 getUnconditionalFilterKeys() 296 getUnconditionalFilterKeys()
294 { 297 {
295 if (!unconditionalFilterKeys) 298 if (!unconditionalFilterKeys)
296 { 299 {
297 let selectors = this.getUnconditionalSelectors(); 300 let selectors = this.getUnconditionalSelectors();
298 unconditionalFilterKeys = []; 301 unconditionalFilterKeys = [];
299 for (let selector of selectors) 302 for (let selector of selectors)
300 unconditionalFilterKeys.push(filterKeyBySelector[selector]); 303 unconditionalFilterKeys.push(filterKeyBySelector.get(selector));
301 } 304 }
302 return unconditionalFilterKeys.slice(); 305 return unconditionalFilterKeys.slice();
303 }, 306 },
304 307
305 308
306 /** 309 /**
307 * Constant used by getSelectorsForDomain to return all selectors applying to 310 * Constant used by getSelectorsForDomain to return all selectors applying to
308 * a particular hostname. 311 * a particular hostname.
309 */ 312 */
310 ALL_MATCHING: 0, 313 ALL_MATCHING: 0,
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
344 if (typeof criteria == "undefined") 347 if (typeof criteria == "undefined")
345 criteria = ElemHide.ALL_MATCHING; 348 criteria = ElemHide.ALL_MATCHING;
346 if (criteria < ElemHide.NO_UNCONDITIONAL) 349 if (criteria < ElemHide.NO_UNCONDITIONAL)
347 { 350 {
348 selectors = this.getUnconditionalSelectors(); 351 selectors = this.getUnconditionalSelectors();
349 if (provideFilterKeys) 352 if (provideFilterKeys)
350 filterKeys = this.getUnconditionalFilterKeys(); 353 filterKeys = this.getUnconditionalFilterKeys();
351 } 354 }
352 355
353 let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY); 356 let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
354 let seenFilters = Object.create(null); 357 let seenFilters = new Set();
355 let currentDomain = domain ? domain.toUpperCase() : ""; 358 let currentDomain = domain ? domain.toUpperCase() : "";
356 while (true) 359 while (true)
357 { 360 {
358 if (specificOnly && currentDomain == "") 361 if (specificOnly && currentDomain == "")
359 break; 362 break;
360 363
361 let filters = filtersByDomain.get(currentDomain); 364 let filters = filtersByDomain.get(currentDomain);
362 if (filters) 365 if (filters)
363 { 366 {
364 for (let [filterKey, filter] of filters) 367 for (let [filterKey, filter] of filters)
365 { 368 {
366 if (filterKey in seenFilters) 369 if (seenFilters.has(filterKey))
367 continue; 370 continue;
368 seenFilters[filterKey] = true; 371 seenFilters.add(filterKey);
369 372
370 if (filter && !this.getException(filter, domain)) 373 if (filter && !this.getException(filter, domain))
371 { 374 {
372 selectors.push(filter.selector); 375 selectors.push(filter.selector);
373 // It is faster to always push the key, even if not required. 376 // It is faster to always push the key, even if not required.
374 filterKeys.push(filterKey); 377 filterKeys.push(filterKey);
375 } 378 }
376 } 379 }
377 } 380 }
378 381
379 if (currentDomain == "") 382 if (currentDomain == "")
380 break; 383 break;
381 384
382 let nextDot = currentDomain.indexOf("."); 385 let nextDot = currentDomain.indexOf(".");
383 currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1); 386 currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
384 } 387 }
385 388
386 if (provideFilterKeys) 389 if (provideFilterKeys)
387 return [selectors, filterKeys]; 390 return [selectors, filterKeys];
388 return selectors; 391 return selectors;
389 } 392 }
390 }; 393 };
OLDNEW
« no previous file with comments | « lib/downloader.js ('k') | lib/elemHideEmulation.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld