| LEFT | RIGHT |
| 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-2016 Eyeo GmbH | 3 * Copyright (C) 2006-2016 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 Matcher class implementing matching addresses against | 21 * @fileOverview Matcher class implementing matching addresses against |
| 22 * a list of filters. | 22 * a list of filters. |
| 23 */ | 23 */ |
| 24 | 24 |
| 25 let {Filter, RegExpFilter, WhitelistFilter} = require("filterClasses"); | 25 const {Filter, WhitelistFilter} = require("filterClasses"); |
| 26 | 26 |
| 27 /** | 27 /** |
| 28 * Blacklist/whitelist filter matching | 28 * Blacklist/whitelist filter matching |
| 29 * @constructor | 29 * @constructor |
| 30 */ | 30 */ |
| 31 function Matcher() | 31 function Matcher() |
| 32 { | 32 { |
| 33 this.clear(); | 33 this.clear(); |
| 34 } | 34 } |
| 35 exports.Matcher = Matcher; | 35 exports.Matcher = Matcher; |
| (...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 100 this.filterByKeyword[keyword] = list[0]; | 100 this.filterByKeyword[keyword] = list[0]; |
| 101 } | 101 } |
| 102 } | 102 } |
| 103 | 103 |
| 104 delete this.keywordByFilter[filter.text]; | 104 delete this.keywordByFilter[filter.text]; |
| 105 }, | 105 }, |
| 106 | 106 |
| 107 /** | 107 /** |
| 108 * Chooses a keyword to be associated with the filter | 108 * Chooses a keyword to be associated with the filter |
| 109 * @param {Filter} filter | 109 * @param {Filter} filter |
| 110 * @return {String} keyword | 110 * @return {string} keyword or an empty string if no keyword could be found |
| 111 */ | 111 */ |
| 112 findKeyword(filter) | 112 findKeyword(filter) |
| 113 { | 113 { |
| 114 let result = ""; | 114 let result = ""; |
| 115 let {text} = filter; | 115 let {text} = filter; |
| 116 if (Filter.regexpRegExp.test(text)) | 116 if (Filter.regexpRegExp.test(text)) |
| 117 return result; | 117 return result; |
| 118 | 118 |
| 119 // Remove options | 119 // Remove options |
| 120 let match = Filter.optionsRegExp.exec(text); | 120 let match = Filter.optionsRegExp.exec(text); |
| (...skipping 24 matching lines...) Expand all Loading... |
| 145 resultCount = count; | 145 resultCount = count; |
| 146 resultLength = candidate.length; | 146 resultLength = candidate.length; |
| 147 } | 147 } |
| 148 } | 148 } |
| 149 return result; | 149 return result; |
| 150 }, | 150 }, |
| 151 | 151 |
| 152 /** | 152 /** |
| 153 * Checks whether a particular filter is being matched against. | 153 * Checks whether a particular filter is being matched against. |
| 154 * @param {RegExpFilter} filter | 154 * @param {RegExpFilter} filter |
| 155 * @return {Boolean} | 155 * @return {boolean} |
| 156 */ | 156 */ |
| 157 hasFilter(filter) | 157 hasFilter(filter) |
| 158 { | 158 { |
| 159 return (filter.text in this.keywordByFilter); | 159 return (filter.text in this.keywordByFilter); |
| 160 }, | 160 }, |
| 161 | 161 |
| 162 /** | 162 /** |
| 163 * Returns the keyword used for a filter, null for unknown filters. | 163 * Returns the keyword used for a filter, null for unknown filters. |
| 164 * @param {RegExpFilter} filter | 164 * @param {RegExpFilter} filter |
| 165 * @return {String} | 165 * @return {string} |
| 166 */ | 166 */ |
| 167 getKeywordForFilter(filter) | 167 getKeywordForFilter(filter) |
| 168 { | 168 { |
| 169 if (filter.text in this.keywordByFilter) | 169 if (filter.text in this.keywordByFilter) |
| 170 return this.keywordByFilter[filter.text]; | 170 return this.keywordByFilter[filter.text]; |
| 171 return null; | 171 return null; |
| 172 }, | 172 }, |
| 173 | 173 |
| 174 /** | 174 /** |
| 175 * Checks whether the entries for a particular keyword match a URL | 175 * Checks whether the entries for a particular keyword match a URL |
| 176 * @param {String} keyword | 176 * @param {string} keyword |
| 177 * @param {String} location | 177 * @param {string} location |
| 178 * @param {Number} typeMask | 178 * @param {number} typeMask |
| 179 * @param {String} docDomain | 179 * @param {string} docDomain |
| 180 * @param {Boolean} thirdParty | 180 * @param {boolean} thirdParty |
| 181 * @param {String} sitekey | 181 * @param {string} sitekey |
| 182 * @param {Boolean} specificOnly | 182 * @param {boolean} specificOnly |
| 183 * @return {Filter|null} | 183 * @return {?Filter} |
| 184 */ | 184 */ |
| 185 _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey, | 185 _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey, |
| 186 specificOnly) | 186 specificOnly) |
| 187 { | 187 { |
| 188 let list = this.filterByKeyword[keyword]; | 188 let list = this.filterByKeyword[keyword]; |
| 189 for (let i = 0; i < list.length; i++) | 189 for (let i = 0; i < list.length; i++) |
| 190 { | 190 { |
| 191 let filter = list[i]; | 191 let filter = list[i]; |
| 192 | 192 |
| 193 if (specificOnly && filter.isGeneric() && | 193 if (specificOnly && filter.isGeneric() && |
| 194 !(filter instanceof WhitelistFilter)) | 194 !(filter instanceof WhitelistFilter)) |
| 195 continue; | 195 continue; |
| 196 | 196 |
| 197 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey)) | 197 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey)) |
| 198 return filter; | 198 return filter; |
| 199 } | 199 } |
| 200 return null; | 200 return null; |
| 201 }, | 201 }, |
| 202 | 202 |
| 203 /** | 203 /** |
| 204 * Tests whether the URL matches any of the known filters | 204 * Tests whether the URL matches any of the known filters |
| 205 * @param {String} location URL to be tested | 205 * @param {string} location |
| 206 * @param {number} typeMask bitmask of content / request types to match | 206 * URL to be tested |
| 207 * @param {String} docDomain domain name of the document that loads the URL | 207 * @param {number} typeMask |
| 208 * @param {Boolean} thirdParty should be true if the URL is a third-party | 208 * bitmask of content / request types to match |
| 209 * request | 209 * @param {string} docDomain |
| 210 * @param {String} sitekey public key provided by the document | 210 * domain name of the document that loads the URL |
| 211 * @param {Boolean} specificOnly should be true if generic matches should be | 211 * @param {boolean} thirdParty |
| 212 * ignored | 212 * should be true if the URL is a third-party request |
| 213 * @return {RegExpFilter|null} matching filter or null | 213 * @param {string} sitekey |
| 214 * public key provided by the document |
| 215 * @param {boolean} specificOnly |
| 216 * should be true if generic matches should be ignored |
| 217 * @return {?RegExpFilter} |
| 218 * matching filter or null |
| 214 */ | 219 */ |
| 215 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) | 220 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) |
| 216 { | 221 { |
| 217 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); | 222 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); |
| 218 if (candidates === null) | 223 if (candidates === null) |
| 219 candidates = []; | 224 candidates = []; |
| 220 candidates.push(""); | 225 candidates.push(""); |
| 221 for (let i = 0, l = candidates.length; i < l; i++) | 226 for (let i = 0, l = candidates.length; i < l; i++) |
| 222 { | 227 { |
| 223 let substr = candidates[i]; | 228 let substr = candidates[i]; |
| 224 if (substr in this.filterByKeyword) | 229 if (substr in this.filterByKeyword) |
| 225 { | 230 { |
| 226 let result = this._checkEntryMatch(substr, location, typeMask, | 231 let result = this._checkEntryMatch(substr, location, typeMask, |
| 227 docDomain, thirdParty, sitekey, | 232 docDomain, thirdParty, sitekey, |
| 228 specificOnly); | 233 specificOnly); |
| 229 if (result) | 234 if (result) |
| 230 return result; | 235 return result; |
| 231 } | 236 } |
| 232 } | 237 } |
| 233 | 238 |
| 234 return null; | 239 return null; |
| 235 } | 240 } |
| 236 }; | 241 }; |
| 237 | 242 |
| 238 /** | 243 /** |
| 239 * Combines a matcher for blocking and exception rules, automatically sorts | 244 * Combines a matcher for blocking and exception rules, automatically sorts |
| 240 * rules into two Matcher instances. | 245 * rules into two Matcher instances. |
| 241 * @constructor | 246 * @constructor |
| 247 * @augments Matcher |
| 242 */ | 248 */ |
| 243 function CombinedMatcher() | 249 function CombinedMatcher() |
| 244 { | 250 { |
| 245 this.blacklist = new Matcher(); | 251 this.blacklist = new Matcher(); |
| 246 this.whitelist = new Matcher(); | 252 this.whitelist = new Matcher(); |
| 247 this.resultCache = Object.create(null); | 253 this.resultCache = Object.create(null); |
| 248 } | 254 } |
| 249 exports.CombinedMatcher = CombinedMatcher; | 255 exports.CombinedMatcher = CombinedMatcher; |
| 250 | 256 |
| 251 /** | 257 /** |
| 252 * Maximal number of matching cache entries to be kept | 258 * Maximal number of matching cache entries to be kept |
| 253 * @type {Number} | 259 * @type {number} |
| 254 */ | 260 */ |
| 255 CombinedMatcher.maxCacheEntries = 1000; | 261 CombinedMatcher.maxCacheEntries = 1000; |
| 256 | 262 |
| 257 CombinedMatcher.prototype = | 263 CombinedMatcher.prototype = |
| 258 { | 264 { |
| 259 /** | 265 /** |
| 260 * Matcher for blocking rules. | 266 * Matcher for blocking rules. |
| 261 * @type {Matcher} | 267 * @type {Matcher} |
| 262 */ | 268 */ |
| 263 blacklist: null, | 269 blacklist: null, |
| 264 | 270 |
| 265 /** | 271 /** |
| 266 * Matcher for exception rules. | 272 * Matcher for exception rules. |
| 267 * @type {Matcher} | 273 * @type {Matcher} |
| 268 */ | 274 */ |
| 269 whitelist: null, | 275 whitelist: null, |
| 270 | 276 |
| 271 /** | 277 /** |
| 272 * Lookup table of previous matchesAny results | 278 * Lookup table of previous matchesAny results |
| 273 * @type {Object} | 279 * @type {Object} |
| 274 */ | 280 */ |
| 275 resultCache: null, | 281 resultCache: null, |
| 276 | 282 |
| 277 /** | 283 /** |
| 278 * Number of entries in resultCache | 284 * Number of entries in resultCache |
| 279 * @type {Number} | 285 * @type {number} |
| 280 */ | 286 */ |
| 281 cacheEntries: 0, | 287 cacheEntries: 0, |
| 282 | 288 |
| 283 /** | 289 /** |
| 284 * @see Matcher#clear | 290 * @see Matcher#clear |
| 285 */ | 291 */ |
| 286 clear() | 292 clear() |
| 287 { | 293 { |
| 288 this.blacklist.clear(); | 294 this.blacklist.clear(); |
| 289 this.whitelist.clear(); | 295 this.whitelist.clear(); |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 323 if (this.cacheEntries > 0) | 329 if (this.cacheEntries > 0) |
| 324 { | 330 { |
| 325 this.resultCache = Object.create(null); | 331 this.resultCache = Object.create(null); |
| 326 this.cacheEntries = 0; | 332 this.cacheEntries = 0; |
| 327 } | 333 } |
| 328 }, | 334 }, |
| 329 | 335 |
| 330 /** | 336 /** |
| 331 * @see Matcher#findKeyword | 337 * @see Matcher#findKeyword |
| 332 * @param {Filter} filter | 338 * @param {Filter} filter |
| 333 * @return {String} keyword | 339 * @return {string} keyword |
| 334 */ | 340 */ |
| 335 findKeyword(filter) | 341 findKeyword(filter) |
| 336 { | 342 { |
| 337 if (filter instanceof WhitelistFilter) | 343 if (filter instanceof WhitelistFilter) |
| 338 return this.whitelist.findKeyword(filter); | 344 return this.whitelist.findKeyword(filter); |
| 339 return this.blacklist.findKeyword(filter); | 345 return this.blacklist.findKeyword(filter); |
| 340 }, | 346 }, |
| 341 | 347 |
| 342 /** | 348 /** |
| 343 * @see Matcher#hasFilter | 349 * @see Matcher#hasFilter |
| 344 * @param {Filter} filter | 350 * @param {Filter} filter |
| 345 * @return {Boolean} | 351 * @return {boolean} |
| 346 */ | 352 */ |
| 347 hasFilter(filter) | 353 hasFilter(filter) |
| 348 { | 354 { |
| 349 if (filter instanceof WhitelistFilter) | 355 if (filter instanceof WhitelistFilter) |
| 350 return this.whitelist.hasFilter(filter); | 356 return this.whitelist.hasFilter(filter); |
| 351 return this.blacklist.hasFilter(filter); | 357 return this.blacklist.hasFilter(filter); |
| 352 }, | 358 }, |
| 353 | 359 |
| 354 /** | 360 /** |
| 355 * @see Matcher#getKeywordForFilter | 361 * @see Matcher#getKeywordForFilter |
| 356 * @param {Filter} filter | 362 * @param {Filter} filter |
| 357 * @return {String} keyword | 363 * @return {string} keyword |
| 358 */ | 364 */ |
| 359 getKeywordForFilter(filter) | 365 getKeywordForFilter(filter) |
| 360 { | 366 { |
| 361 if (filter instanceof WhitelistFilter) | 367 if (filter instanceof WhitelistFilter) |
| 362 return this.whitelist.getKeywordForFilter(filter); | 368 return this.whitelist.getKeywordForFilter(filter); |
| 363 return this.blacklist.getKeywordForFilter(filter); | 369 return this.blacklist.getKeywordForFilter(filter); |
| 364 }, | 370 }, |
| 365 | 371 |
| 366 /** | 372 /** |
| 367 * Checks whether a particular filter is slow | 373 * Checks whether a particular filter is slow |
| 368 * @param {RegExpFilter} filter | 374 * @param {RegExpFilter} filter |
| 369 * @return {Boolean} | 375 * @return {boolean} |
| 370 */ | 376 */ |
| 371 isSlowFilter(filter) | 377 isSlowFilter(filter) |
| 372 { | 378 { |
| 373 let matcher = ( | 379 let matcher = ( |
| 374 filter instanceof WhitelistFilter ? this.whitelist : this.blacklist | 380 filter instanceof WhitelistFilter ? this.whitelist : this.blacklist |
| 375 ); | 381 ); |
| 376 if (matcher.hasFilter(filter)) | 382 if (matcher.hasFilter(filter)) |
| 377 return !matcher.getKeywordForFilter(filter); | 383 return !matcher.getKeywordForFilter(filter); |
| 378 return !matcher.findKeyword(filter); | 384 return !matcher.findKeyword(filter); |
| 379 }, | 385 }, |
| 380 | 386 |
| 381 /** | 387 /** |
| 382 * Optimized filter matching testing both whitelist and blacklist matchers | 388 * Optimized filter matching testing both whitelist and blacklist matchers |
| 383 * simultaneously. For parameters see Matcher.matchesAny(). | 389 * simultaneously. For parameters see Matcher.matchesAny(). |
| 384 * @see Matcher#matchesAny | 390 * @see Matcher#matchesAny |
| 385 * @param {String} location URL to be tested | 391 * @inheritdoc |
| 386 * @param {number} typeMask bitmask of content / request types to match | |
| 387 * @param {String} docDomain domain name of the document that loads the URL | |
| 388 * @param {Boolean} thirdParty should be true if the URL is a third-party | |
| 389 * request | |
| 390 * @param {String} sitekey public key provided by the document | |
| 391 * @param {Boolean} specificOnly should be true if generic matches should be | |
| 392 * ignored | |
| 393 * @return {RegExpFilter|null} matching filter or null | |
| 394 */ | 392 */ |
| 395 matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey, | 393 matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey, |
| 396 specificOnly) | 394 specificOnly) |
| 397 { | 395 { |
| 398 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); | 396 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); |
| 399 if (candidates === null) | 397 if (candidates === null) |
| 400 candidates = []; | 398 candidates = []; |
| 401 candidates.push(""); | 399 candidates.push(""); |
| 402 | 400 |
| 403 let blacklistHit = null; | 401 let blacklistHit = null; |
| (...skipping 14 matching lines...) Expand all Loading... |
| 418 substr, location, typeMask, docDomain, thirdParty, sitekey, | 416 substr, location, typeMask, docDomain, thirdParty, sitekey, |
| 419 specificOnly | 417 specificOnly |
| 420 ); | 418 ); |
| 421 } | 419 } |
| 422 } | 420 } |
| 423 return blacklistHit; | 421 return blacklistHit; |
| 424 }, | 422 }, |
| 425 | 423 |
| 426 /** | 424 /** |
| 427 * @see Matcher#matchesAny | 425 * @see Matcher#matchesAny |
| 428 * @param {String} location URL to be tested | 426 * @inheritdoc |
| 429 * @param {number} typeMask bitmask of content / request types to match | |
| 430 * @param {String} docDomain domain name of the document that loads the URL | |
| 431 * @param {Boolean} thirdParty should be true if the URL is a third-party | |
| 432 * request | |
| 433 * @param {String} sitekey public key provided by the document | |
| 434 * @param {Boolean} specificOnly should be true if generic matches should be | |
| 435 * ignored | |
| 436 * @return {RegExpFilter} matching filter or null | |
| 437 */ | 427 */ |
| 438 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) | 428 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) |
| 439 { | 429 { |
| 440 let key = location + " " + typeMask + " " + docDomain + " " + thirdParty + | 430 let key = location + " " + typeMask + " " + docDomain + " " + thirdParty + |
| 441 " " + sitekey + " " + specificOnly; | 431 " " + sitekey + " " + specificOnly; |
| 442 if (key in this.resultCache) | 432 if (key in this.resultCache) |
| 443 return this.resultCache[key]; | 433 return this.resultCache[key]; |
| 444 | 434 |
| 445 let result = this.matchesAnyInternal(location, typeMask, docDomain, | 435 let result = this.matchesAnyInternal(location, typeMask, docDomain, |
| 446 thirdParty, sitekey, specificOnly); | 436 thirdParty, sitekey, specificOnly); |
| 447 | 437 |
| 448 if (this.cacheEntries >= CombinedMatcher.maxCacheEntries) | 438 if (this.cacheEntries >= CombinedMatcher.maxCacheEntries) |
| 449 { | 439 { |
| 450 this.resultCache = Object.create(null); | 440 this.resultCache = Object.create(null); |
| 451 this.cacheEntries = 0; | 441 this.cacheEntries = 0; |
| 452 } | 442 } |
| 453 | 443 |
| 454 this.resultCache[key] = result; | 444 this.resultCache[key] = result; |
| 455 this.cacheEntries++; | 445 this.cacheEntries++; |
| 456 | 446 |
| 457 return result; | 447 return result; |
| 458 } | 448 } |
| 459 }; | 449 }; |
| 460 | 450 |
| 461 /** | 451 /** |
| 462 * Shared CombinedMatcher instance that should usually be used. | 452 * Shared CombinedMatcher instance that should usually be used. |
| 463 * @type {CombinedMatcher} | 453 * @type {CombinedMatcher} |
| 464 */ | 454 */ |
| 465 let defaultMatcher = exports.defaultMatcher = new CombinedMatcher(); | 455 exports.defaultMatcher = new CombinedMatcher(); |
| LEFT | RIGHT |