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

Side by Side Diff: lib/matcher.js

Issue 29926557: Issue 6994 - Use shortcut matching for location-only filters (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore/
Patch Set: Minor update Created Oct. 25, 2018, 9:22 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/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 48 matching lines...) Expand 10 before | Expand all | Expand 10 after
59 exports.isSlowFilter = isSlowFilter; 59 exports.isSlowFilter = isSlowFilter;
60 60
61 /** 61 /**
62 * Blacklist/whitelist filter matching 62 * Blacklist/whitelist filter matching
63 */ 63 */
64 class Matcher 64 class Matcher
65 { 65 {
66 constructor() 66 constructor()
67 { 67 {
68 /** 68 /**
69 * Lookup table for filters by their associated keyword 69 * Lookup table for simple filters by their associated keyword
70 * @type {Map.<string,(Filter|Set.<Filter>)>} 70 * @type {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>}
71 * @private 71 * @private
72 */ 72 */
73 this._filterByKeyword = new Map(); 73 this._simpleFiltersByKeyword = new Map();
74
75 /**
76 * Lookup table for complex filters by their associated keyword
77 * @type {Map.<string,(RegExpFilter|Set.<RegExpFilter>)>}
78 * @private
79 */
80 this._complexFiltersByKeyword = new Map();
74 } 81 }
75 82
76 /** 83 /**
77 * Removes all known filters 84 * Removes all known filters
78 */ 85 */
79 clear() 86 clear()
80 { 87 {
81 this._filterByKeyword.clear(); 88 this._simpleFiltersByKeyword.clear();
89 this._complexFiltersByKeyword.clear();
82 } 90 }
83 91
84 /** 92 /**
85 * Adds a filter to the matcher 93 * Adds a filter to the matcher
86 * @param {RegExpFilter} filter 94 * @param {RegExpFilter} filter
87 */ 95 */
88 add(filter) 96 add(filter)
89 { 97 {
98 let filtersByKeyword = filter.isLocationOnly() ?
99 this._simpleFiltersByKeyword :
100 this._complexFiltersByKeyword;
90 // Look for a suitable keyword 101 // Look for a suitable keyword
91 let keyword = this.findKeyword(filter); 102 let keyword = this.findKeyword(filter);
92 let set = this._filterByKeyword.get(keyword); 103 let set = filtersByKeyword.get(keyword);
93 if (typeof set == "undefined") 104 if (typeof set == "undefined")
94 { 105 {
95 this._filterByKeyword.set(keyword, filter); 106 filtersByKeyword.set(keyword, filter);
96 } 107 }
97 else if (set.size == 1) 108 else if (set.size == 1)
98 { 109 {
99 if (filter != set) 110 if (filter != set)
100 this._filterByKeyword.set(keyword, new Set([set, filter])); 111 filtersByKeyword.set(keyword, new Set([set, filter]));
101 } 112 }
102 else 113 else
103 { 114 {
104 set.add(filter); 115 set.add(filter);
105 } 116 }
106 } 117 }
107 118
108 /** 119 /**
109 * Removes a filter from the matcher 120 * Removes a filter from the matcher
110 * @param {RegExpFilter} filter 121 * @param {RegExpFilter} filter
111 */ 122 */
112 remove(filter) 123 remove(filter)
113 { 124 {
125 let filtersByKeyword = filter.isLocationOnly() ?
126 this._simpleFiltersByKeyword :
127 this._complexFiltersByKeyword;
114 let keyword = this.findKeyword(filter); 128 let keyword = this.findKeyword(filter);
115 let set = this._filterByKeyword.get(keyword); 129 let set = filtersByKeyword.get(keyword);
116 if (typeof set == "undefined") 130 if (typeof set == "undefined")
117 return; 131 return;
118 132
119 if (set.size == 1) 133 if (set.size == 1)
120 { 134 {
121 if (filter == set) 135 if (filter == set)
122 this._filterByKeyword.delete(keyword); 136 filtersByKeyword.delete(keyword);
123 } 137 }
124 else 138 else
125 { 139 {
126 set.delete(filter); 140 set.delete(filter);
127 141
128 if (set.size == 1) 142 if (set.size == 1)
129 this._filterByKeyword.set(keyword, [...set][0]); 143 filtersByKeyword.set(keyword, [...set][0]);
130 } 144 }
131 } 145 }
132 146
133 /** 147 /**
134 * Chooses a keyword to be associated with the filter 148 * Chooses a keyword to be associated with the filter
135 * @param {Filter} filter 149 * @param {Filter} filter
136 * @returns {string} keyword or an empty string if no keyword could be found 150 * @returns {string} keyword or an empty string if no keyword could be found
137 * @protected 151 * @protected
138 */ 152 */
139 findKeyword(filter) 153 findKeyword(filter)
140 { 154 {
141 let result = ""; 155 let result = "";
142 let {pattern} = filter; 156 let {pattern} = filter;
143 if (pattern == null) 157 if (pattern == null)
144 return result; 158 return result;
145 159
146 let candidates = pattern.toLowerCase().match(allKeywordsRegExp); 160 let candidates = pattern.toLowerCase().match(allKeywordsRegExp);
147 if (!candidates) 161 if (!candidates)
148 return result; 162 return result;
149 163
150 let hash = this._filterByKeyword;
151 let resultCount = 0xFFFFFF; 164 let resultCount = 0xFFFFFF;
152 let resultLength = 0; 165 let resultLength = 0;
153 for (let i = 0, l = candidates.length; i < l; i++) 166 for (let i = 0, l = candidates.length; i < l; i++)
154 { 167 {
155 let candidate = candidates[i].substr(1); 168 let candidate = candidates[i].substr(1);
156 let filters = hash.get(candidate); 169 let simpleFilters = this._simpleFiltersByKeyword.get(candidate);
157 let count = typeof filters != "undefined" ? filters.size : 0; 170 let complexFilters = this._complexFiltersByKeyword.get(candidate);
171 let count = (typeof simpleFilters != "undefined" ?
172 simpleFilters.size : 0) +
173 (typeof complexFilters != "undefined" ?
174 complexFilters.size : 0);
158 if (count < resultCount || 175 if (count < resultCount ||
159 (count == resultCount && candidate.length > resultLength)) 176 (count == resultCount && candidate.length > resultLength))
160 { 177 {
161 result = candidate; 178 result = candidate;
162 resultCount = count; 179 resultCount = count;
163 resultLength = candidate.length; 180 resultLength = candidate.length;
164 } 181 }
165 } 182 }
166 return result; 183 return result;
167 } 184 }
168 185
169 /** 186 /**
170 * Checks whether the entries for a particular keyword match a URL 187 * Checks whether the entries for a particular keyword match a URL
171 * @param {string} keyword 188 * @param {string} keyword
172 * @param {string} location 189 * @param {string} location
173 * @param {number} typeMask 190 * @param {number} typeMask
174 * @param {string} [docDomain] 191 * @param {string} [docDomain]
175 * @param {boolean} [thirdParty] 192 * @param {boolean} [thirdParty]
176 * @param {string} [sitekey] 193 * @param {string} [sitekey]
177 * @param {boolean} [specificOnly] 194 * @param {boolean} [specificOnly]
178 * @returns {?Filter} 195 * @returns {?Filter}
179 * @protected 196 * @protected
180 */ 197 */
181 checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey, 198 checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey,
182 specificOnly) 199 specificOnly)
183 { 200 {
184 let set = this._filterByKeyword.get(keyword); 201 // We need to skip the simple (location-only) filters if the type mask does
185 if (typeof set == "undefined") 202 // not contain any non-default content types like $document, $elemhide,
186 return null; 203 // $csp, and so on.
204 if ((typeMask & RegExpFilter.prototype.contentType) != 0)
205 {
206 let simpleSet = this._simpleFiltersByKeyword.get(keyword);
207 if (simpleSet)
208 {
209 for (let filter of simpleSet)
210 {
211 if (specificOnly && !(filter instanceof WhitelistFilter))
212 continue;
187 213
188 for (let filter of set) 214 if (filter.matchesLocation(location))
215 return filter;
216 }
217 }
218 }
219
220 let complexSet = this._complexFiltersByKeyword.get(keyword);
221 if (complexSet)
189 { 222 {
190 if (specificOnly && filter.isGeneric() && 223 for (let filter of complexSet)
191 !(filter instanceof WhitelistFilter)) 224 {
192 continue; 225 if (specificOnly && filter.isGeneric() &&
226 !(filter instanceof WhitelistFilter))
227 continue;
193 228
194 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey)) 229 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey))
195 return filter; 230 return filter;
231 }
196 } 232 }
233
197 return null; 234 return null;
198 } 235 }
199 236
200 /** 237 /**
201 * Tests whether the URL matches any of the known filters 238 * Tests whether the URL matches any of the known filters
202 * @param {string} location 239 * @param {string} location
203 * URL to be tested 240 * URL to be tested
204 * @param {number} typeMask 241 * @param {number} typeMask
205 * bitmask of content / request types to match 242 * bitmask of content / request types to match
206 * @param {string} [docDomain] 243 * @param {string} [docDomain]
(...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after
396 433
397 exports.CombinedMatcher = CombinedMatcher; 434 exports.CombinedMatcher = CombinedMatcher;
398 435
399 /** 436 /**
400 * Shared {@link CombinedMatcher} instance that should usually be used. 437 * Shared {@link CombinedMatcher} instance that should usually be used.
401 * @type {CombinedMatcher} 438 * @type {CombinedMatcher}
402 */ 439 */
403 let defaultMatcher = new CombinedMatcher(); 440 let defaultMatcher = new CombinedMatcher();
404 441
405 exports.defaultMatcher = defaultMatcher; 442 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