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

Side by Side Diff: lib/matcher.js

Issue 29892596: Issue 6992 - Remove keyword-by-filter map (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore/
Patch Set: Created Sept. 27, 2018, 4:23 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 | « lib/filterClasses.js ('k') | test/filterListener.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
(...skipping 15 matching lines...) Expand all
26 26
27 /** 27 /**
28 * Blacklist/whitelist filter matching 28 * Blacklist/whitelist filter matching
29 */ 29 */
30 class Matcher 30 class Matcher
31 { 31 {
32 constructor() 32 constructor()
33 { 33 {
34 /** 34 /**
35 * Lookup table for filters by their associated keyword 35 * Lookup table for filters by their associated keyword
36 * @type {Map.<string,(Filter|Filter[])>} 36 * @type {Map.<string,(Filter|Set.<Filter>)>}
37 */ 37 */
38 this.filterByKeyword = new Map(); 38 this.filterByKeyword = new Map();
39
40 /**
41 * Lookup table for keywords by the filter
42 * @type {Map.<Filter,string>}
43 */
44 this.keywordByFilter = new Map();
45 } 39 }
46 40
47 /** 41 /**
48 * Removes all known filters 42 * Removes all known filters
49 */ 43 */
50 clear() 44 clear()
51 { 45 {
52 this.filterByKeyword.clear(); 46 this.filterByKeyword.clear();
53 this.keywordByFilter.clear();
54 } 47 }
55 48
56 /** 49 /**
57 * Adds a filter to the matcher 50 * Adds a filter to the matcher
58 * @param {RegExpFilter} filter 51 * @param {RegExpFilter} filter
59 */ 52 */
60 add(filter) 53 add(filter)
61 { 54 {
62 if (this.keywordByFilter.has(filter))
63 return;
64
65 // Look for a suitable keyword 55 // Look for a suitable keyword
66 let keyword = this.findKeyword(filter); 56 let keyword = this.findKeyword(filter);
67 let oldEntry = this.filterByKeyword.get(keyword); 57 let set = this.filterByKeyword.get(keyword);
68 if (typeof oldEntry == "undefined") 58 if (typeof set == "undefined")
59 {
69 this.filterByKeyword.set(keyword, filter); 60 this.filterByKeyword.set(keyword, filter);
70 else if (oldEntry.length == 1) 61 }
71 this.filterByKeyword.set(keyword, [oldEntry, filter]); 62 else if (set.size == 1)
63 {
64 if (filter != set)
65 this.filterByKeyword.set(keyword, new Set([set, filter]));
66 }
72 else 67 else
73 oldEntry.push(filter); 68 {
74 this.keywordByFilter.set(filter, keyword); 69 set.add(filter);
70 }
75 } 71 }
76 72
77 /** 73 /**
78 * Removes a filter from the matcher 74 * Removes a filter from the matcher
79 * @param {RegExpFilter} filter 75 * @param {RegExpFilter} filter
80 */ 76 */
81 remove(filter) 77 remove(filter)
82 { 78 {
83 let keyword = this.keywordByFilter.get(filter); 79 let keyword = this.findKeyword(filter);
84 if (typeof keyword == "undefined") 80 let set = this.filterByKeyword.get(keyword);
81 if (typeof set == "undefined")
85 return; 82 return;
86 83
87 let list = this.filterByKeyword.get(keyword); 84 if (set.size == 1)
88 if (list.length <= 1) 85 {
89 this.filterByKeyword.delete(keyword); 86 if (filter == set)
87 this.filterByKeyword.delete(keyword);
88 }
90 else 89 else
91 { 90 {
92 let index = list.indexOf(filter); 91 set.delete(filter);
93 if (index >= 0) 92
94 { 93 if (set.size == 1)
95 list.splice(index, 1); 94 this.filterByKeyword.set(keyword, [...set][0]);
96 if (list.length == 1)
97 this.filterByKeyword.set(keyword, list[0]);
98 }
99 } 95 }
100
101 this.keywordByFilter.delete(filter);
102 } 96 }
103 97
104 /** 98 /**
105 * Chooses a keyword to be associated with the filter 99 * Chooses a keyword to be associated with the filter
106 * @param {Filter} filter 100 * @param {Filter} filter
107 * @returns {string} keyword or an empty string if no keyword could be found 101 * @returns {string} keyword or an empty string if no keyword could be found
108 */ 102 */
109 findKeyword(filter) 103 findKeyword(filter)
110 { 104 {
111 let result = ""; 105 let result = "";
112 let {pattern} = filter; 106 let {pattern} = filter;
113 if (pattern == null) 107 if (pattern == null)
114 return result; 108 return result;
115 109
116 let candidates = pattern.toLowerCase().match( 110 let candidates = pattern.toLowerCase().match(
117 /[^a-z0-9%*][a-z0-9%]{3,}(?=[^a-z0-9%*])/g 111 /[^a-z0-9%*][a-z0-9%]{3,}(?=[^a-z0-9%*])/g
118 ); 112 );
119 if (!candidates) 113 if (!candidates)
120 return result; 114 return result;
121 115
122 let hash = this.filterByKeyword; 116 let hash = this.filterByKeyword;
123 let resultCount = 0xFFFFFF; 117 let resultCount = 0xFFFFFF;
124 let resultLength = 0; 118 let resultLength = 0;
125 for (let i = 0, l = candidates.length; i < l; i++) 119 for (let i = 0, l = candidates.length; i < l; i++)
126 { 120 {
127 let candidate = candidates[i].substr(1); 121 let candidate = candidates[i].substr(1);
128 let filters = hash.get(candidate); 122 let filters = hash.get(candidate);
129 let count = typeof filters != "undefined" ? filters.length : 0; 123 let count = typeof filters != "undefined" ? filters.size : 0;
130 if (count < resultCount || 124 if (count < resultCount ||
131 (count == resultCount && candidate.length > resultLength)) 125 (count == resultCount && candidate.length > resultLength))
132 { 126 {
133 result = candidate; 127 result = candidate;
134 resultCount = count; 128 resultCount = count;
135 resultLength = candidate.length; 129 resultLength = candidate.length;
136 } 130 }
137 } 131 }
138 return result; 132 return result;
139 } 133 }
140 134
141 /** 135 /**
142 * Checks whether a particular filter is being matched against.
143 * @param {RegExpFilter} filter
144 * @returns {boolean}
145 */
146 hasFilter(filter)
147 {
148 return this.keywordByFilter.has(filter);
149 }
150
151 /**
152 * Returns the keyword used for a filter, <code>null</code>
153 * for unknown filters.
154 * @param {RegExpFilter} filter
155 * @returns {?string}
156 */
157 getKeywordForFilter(filter)
158 {
159 let keyword = this.keywordByFilter.get(filter);
160 return typeof keyword != "undefined" ? keyword : null;
161 }
162
163 /**
164 * Checks whether the entries for a particular keyword match a URL 136 * Checks whether the entries for a particular keyword match a URL
165 * @param {string} keyword 137 * @param {string} keyword
166 * @param {string} location 138 * @param {string} location
167 * @param {number} typeMask 139 * @param {number} typeMask
168 * @param {string} [docDomain] 140 * @param {string} [docDomain]
169 * @param {boolean} [thirdParty] 141 * @param {boolean} [thirdParty]
170 * @param {string} [sitekey] 142 * @param {string} [sitekey]
171 * @param {boolean} [specificOnly] 143 * @param {boolean} [specificOnly]
172 * @returns {?Filter} 144 * @returns {?Filter}
173 */ 145 */
174 _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey, 146 _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
175 specificOnly) 147 specificOnly)
176 { 148 {
177 let list = this.filterByKeyword.get(keyword); 149 let set = this.filterByKeyword.get(keyword);
178 if (typeof list == "undefined") 150 if (typeof set == "undefined")
179 return null; 151 return null;
180 for (let i = 0; i < list.length; i++) 152
153 for (let filter of set)
181 { 154 {
182 let filter = list[i];
183
184 if (specificOnly && filter.isGeneric() && 155 if (specificOnly && filter.isGeneric() &&
185 !(filter instanceof WhitelistFilter)) 156 !(filter instanceof WhitelistFilter))
186 continue; 157 continue;
187 158
188 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey)) 159 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
189 return filter; 160 return filter;
190 } 161 }
191 return null; 162 return null;
192 } 163 }
193 164
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after
306 * @returns {string} keyword 277 * @returns {string} keyword
307 */ 278 */
308 findKeyword(filter) 279 findKeyword(filter)
309 { 280 {
310 if (filter instanceof WhitelistFilter) 281 if (filter instanceof WhitelistFilter)
311 return this.whitelist.findKeyword(filter); 282 return this.whitelist.findKeyword(filter);
312 return this.blacklist.findKeyword(filter); 283 return this.blacklist.findKeyword(filter);
313 } 284 }
314 285
315 /** 286 /**
316 * @see Matcher#hasFilter
317 * @param {Filter} filter
318 * @returns {boolean}
319 */
320 hasFilter(filter)
321 {
322 if (filter instanceof WhitelistFilter)
323 return this.whitelist.hasFilter(filter);
324 return this.blacklist.hasFilter(filter);
325 }
326
327 /**
328 * @see Matcher#getKeywordForFilter
329 * @param {Filter} filter
330 * @returns {string} keyword
331 */
332 getKeywordForFilter(filter)
333 {
334 if (filter instanceof WhitelistFilter)
335 return this.whitelist.getKeywordForFilter(filter);
336 return this.blacklist.getKeywordForFilter(filter);
337 }
338
339 /**
340 * Checks whether a particular filter is slow
341 * @param {RegExpFilter} filter
342 * @returns {boolean}
343 */
344 isSlowFilter(filter)
345 {
346 let matcher = (
347 filter instanceof WhitelistFilter ? this.whitelist : this.blacklist
348 );
349 let keyword = matcher.getKeywordForFilter(filter);
350 if (keyword != null)
351 return !keyword;
352 return !matcher.findKeyword(filter);
353 }
354
355 /**
356 * Optimized filter matching testing both whitelist and blacklist matchers 287 * Optimized filter matching testing both whitelist and blacklist matchers
357 * simultaneously. For parameters see 288 * simultaneously. For parameters see
358 {@link Matcher#matchesAny Matcher.matchesAny()}. 289 {@link Matcher#matchesAny Matcher.matchesAny()}.
359 * @see Matcher#matchesAny 290 * @see Matcher#matchesAny
360 * @inheritdoc 291 * @inheritdoc
361 */ 292 */
362 matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey, 293 matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey,
363 specificOnly) 294 specificOnly)
364 { 295 {
365 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); 296 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g);
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after
414 345
415 exports.CombinedMatcher = CombinedMatcher; 346 exports.CombinedMatcher = CombinedMatcher;
416 347
417 /** 348 /**
418 * Shared {@link CombinedMatcher} instance that should usually be used. 349 * Shared {@link CombinedMatcher} instance that should usually be used.
419 * @type {CombinedMatcher} 350 * @type {CombinedMatcher}
420 */ 351 */
421 let defaultMatcher = new CombinedMatcher(); 352 let defaultMatcher = new CombinedMatcher();
422 353
423 exports.defaultMatcher = defaultMatcher; 354 exports.defaultMatcher = defaultMatcher;
OLDNEW
« no previous file with comments | « lib/filterClasses.js ('k') | test/filterListener.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld