| Left: | ||
| Right: |
| OLD | NEW |
|---|---|
| 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 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 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 filters by their associated keyword |
| 70 * @type {Map.<string,(Filter|Set.<Filter>)>} | 70 * @type {Map.<string,(Filter|Set.<Filter>)>} |
| 71 * @private | |
| 71 */ | 72 */ |
| 72 this.filterByKeyword = new Map(); | 73 this._filterByKeyword = new Map(); |
| 73 } | 74 } |
| 74 | 75 |
| 75 /** | 76 /** |
| 76 * Removes all known filters | 77 * Removes all known filters |
| 77 */ | 78 */ |
| 78 clear() | 79 clear() |
| 79 { | 80 { |
| 80 this.filterByKeyword.clear(); | 81 this._filterByKeyword.clear(); |
| 81 } | 82 } |
| 82 | 83 |
| 83 /** | 84 /** |
| 84 * Adds a filter to the matcher | 85 * Adds a filter to the matcher |
| 85 * @param {RegExpFilter} filter | 86 * @param {RegExpFilter} filter |
| 86 */ | 87 */ |
| 87 add(filter) | 88 add(filter) |
| 88 { | 89 { |
| 89 // Look for a suitable keyword | 90 // Look for a suitable keyword |
| 90 let keyword = this.findKeyword(filter); | 91 let keyword = this.findKeyword(filter); |
| 91 let set = this.filterByKeyword.get(keyword); | 92 let set = this._filterByKeyword.get(keyword); |
| 92 if (typeof set == "undefined") | 93 if (typeof set == "undefined") |
| 93 { | 94 { |
| 94 this.filterByKeyword.set(keyword, filter); | 95 this._filterByKeyword.set(keyword, filter); |
| 95 } | 96 } |
| 96 else if (set.size == 1) | 97 else if (set.size == 1) |
| 97 { | 98 { |
| 98 if (filter != set) | 99 if (filter != set) |
| 99 this.filterByKeyword.set(keyword, new Set([set, filter])); | 100 this._filterByKeyword.set(keyword, new Set([set, filter])); |
| 100 } | 101 } |
| 101 else | 102 else |
| 102 { | 103 { |
| 103 set.add(filter); | 104 set.add(filter); |
| 104 } | 105 } |
| 105 } | 106 } |
| 106 | 107 |
| 107 /** | 108 /** |
| 108 * Removes a filter from the matcher | 109 * Removes a filter from the matcher |
| 109 * @param {RegExpFilter} filter | 110 * @param {RegExpFilter} filter |
| 110 */ | 111 */ |
| 111 remove(filter) | 112 remove(filter) |
| 112 { | 113 { |
| 113 let keyword = this.findKeyword(filter); | 114 let keyword = this.findKeyword(filter); |
| 114 let set = this.filterByKeyword.get(keyword); | 115 let set = this._filterByKeyword.get(keyword); |
| 115 if (typeof set == "undefined") | 116 if (typeof set == "undefined") |
| 116 return; | 117 return; |
| 117 | 118 |
| 118 if (set.size == 1) | 119 if (set.size == 1) |
| 119 { | 120 { |
| 120 if (filter == set) | 121 if (filter == set) |
| 121 this.filterByKeyword.delete(keyword); | 122 this._filterByKeyword.delete(keyword); |
| 122 } | 123 } |
| 123 else | 124 else |
| 124 { | 125 { |
| 125 set.delete(filter); | 126 set.delete(filter); |
| 126 | 127 |
| 127 if (set.size == 1) | 128 if (set.size == 1) |
| 128 this.filterByKeyword.set(keyword, [...set][0]); | 129 this._filterByKeyword.set(keyword, [...set][0]); |
| 129 } | 130 } |
| 130 } | 131 } |
| 131 | 132 |
| 132 /** | 133 /** |
| 133 * Chooses a keyword to be associated with the filter | 134 * Chooses a keyword to be associated with the filter |
| 134 * @param {Filter} filter | 135 * @param {Filter} filter |
| 135 * @returns {string} keyword or an empty string if no keyword could be found | 136 * @returns {string} keyword or an empty string if no keyword could be found |
| 137 * @protected | |
| 136 */ | 138 */ |
| 137 findKeyword(filter) | 139 findKeyword(filter) |
| 138 { | 140 { |
| 139 let result = ""; | 141 let result = ""; |
| 140 let {pattern} = filter; | 142 let {pattern} = filter; |
| 141 if (pattern == null) | 143 if (pattern == null) |
| 142 return result; | 144 return result; |
| 143 | 145 |
| 144 let candidates = pattern.toLowerCase().match(allKeywordsRegExp); | 146 let candidates = pattern.toLowerCase().match(allKeywordsRegExp); |
| 145 if (!candidates) | 147 if (!candidates) |
| 146 return result; | 148 return result; |
| 147 | 149 |
| 148 let hash = this.filterByKeyword; | 150 let hash = this._filterByKeyword; |
| 149 let resultCount = 0xFFFFFF; | 151 let resultCount = 0xFFFFFF; |
| 150 let resultLength = 0; | 152 let resultLength = 0; |
| 151 for (let i = 0, l = candidates.length; i < l; i++) | 153 for (let i = 0, l = candidates.length; i < l; i++) |
| 152 { | 154 { |
| 153 let candidate = candidates[i].substr(1); | 155 let candidate = candidates[i].substr(1); |
| 154 let filters = hash.get(candidate); | 156 let filters = hash.get(candidate); |
| 155 let count = typeof filters != "undefined" ? filters.size : 0; | 157 let count = typeof filters != "undefined" ? filters.size : 0; |
| 156 if (count < resultCount || | 158 if (count < resultCount || |
| 157 (count == resultCount && candidate.length > resultLength)) | 159 (count == resultCount && candidate.length > resultLength)) |
| 158 { | 160 { |
| 159 result = candidate; | 161 result = candidate; |
| 160 resultCount = count; | 162 resultCount = count; |
| 161 resultLength = candidate.length; | 163 resultLength = candidate.length; |
| 162 } | 164 } |
| 163 } | 165 } |
| 164 return result; | 166 return result; |
| 165 } | 167 } |
| 166 | 168 |
| 167 /** | 169 /** |
| 168 * Checks whether the entries for a particular keyword match a URL | 170 * Checks whether the entries for a particular keyword match a URL |
| 169 * @param {string} keyword | 171 * @param {string} keyword |
| 170 * @param {string} location | 172 * @param {string} location |
| 171 * @param {number} typeMask | 173 * @param {number} typeMask |
| 172 * @param {string} [docDomain] | 174 * @param {string} [docDomain] |
| 173 * @param {boolean} [thirdParty] | 175 * @param {boolean} [thirdParty] |
| 174 * @param {string} [sitekey] | 176 * @param {string} [sitekey] |
| 175 * @param {boolean} [specificOnly] | 177 * @param {boolean} [specificOnly] |
| 176 * @returns {?Filter} | 178 * @returns {?Filter} |
| 179 * @protected | |
| 177 */ | 180 */ |
| 178 _checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey, | 181 checkEntryMatch(keyword, location, typeMask, docDomain, thirdParty, sitekey, |
| 179 specificOnly) | 182 specificOnly) |
|
Manish Jethani
2018/10/24 18:43:54
Sorry, I missed this one. We need to fix the align
Jon Sonesen
2018/10/24 18:46:26
oof, good catch
| |
| 180 { | 183 { |
| 181 let set = this.filterByKeyword.get(keyword); | 184 let set = this._filterByKeyword.get(keyword); |
| 182 if (typeof set == "undefined") | 185 if (typeof set == "undefined") |
| 183 return null; | 186 return null; |
| 184 | 187 |
| 185 for (let filter of set) | 188 for (let filter of set) |
| 186 { | 189 { |
| 187 if (specificOnly && filter.isGeneric() && | 190 if (specificOnly && filter.isGeneric() && |
| 188 !(filter instanceof WhitelistFilter)) | 191 !(filter instanceof WhitelistFilter)) |
| 189 continue; | 192 continue; |
| 190 | 193 |
| 191 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey)) | 194 if (filter.matches(location, typeMask, docDomain, thirdParty, sitekey)) |
| (...skipping 20 matching lines...) Expand all Loading... | |
| 212 * matching filter or <code>null</code> | 215 * matching filter or <code>null</code> |
| 213 */ | 216 */ |
| 214 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) | 217 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) |
| 215 { | 218 { |
| 216 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); | 219 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); |
| 217 if (candidates === null) | 220 if (candidates === null) |
| 218 candidates = []; | 221 candidates = []; |
| 219 candidates.push(""); | 222 candidates.push(""); |
| 220 for (let i = 0, l = candidates.length; i < l; i++) | 223 for (let i = 0, l = candidates.length; i < l; i++) |
| 221 { | 224 { |
| 222 let result = this._checkEntryMatch(candidates[i], location, typeMask, | 225 let result = this.checkEntryMatch(candidates[i], location, typeMask, |
| 223 docDomain, thirdParty, sitekey, | 226 docDomain, thirdParty, sitekey, |
| 224 specificOnly); | 227 specificOnly); |
| 225 if (result) | 228 if (result) |
| 226 return result; | 229 return result; |
| 227 } | 230 } |
| 228 | 231 |
| 229 return null; | 232 return null; |
| 230 } | 233 } |
| 231 } | 234 } |
| 232 | 235 |
| 233 exports.Matcher = Matcher; | 236 exports.Matcher = Matcher; |
| 234 | 237 |
| 235 /** | 238 /** |
| 236 * Combines a matcher for blocking and exception rules, automatically sorts | 239 * Combines a matcher for blocking and exception rules, automatically sorts |
| 237 * rules into two {@link Matcher} instances. | 240 * rules into two {@link Matcher} instances. |
| 238 */ | 241 */ |
| 239 class CombinedMatcher | 242 class CombinedMatcher |
| 240 { | 243 { |
| 241 constructor() | 244 constructor() |
| 242 { | 245 { |
| 243 /** | 246 /** |
| 244 * Maximal number of matching cache entries to be kept | 247 * Maximal number of matching cache entries to be kept |
| 245 * @type {number} | 248 * @type {number} |
| 246 */ | 249 */ |
| 247 this.maxCacheEntries = 1000; | 250 this.maxCacheEntries = 1000; |
| 248 | 251 |
| 249 /** | 252 /** |
| 250 * Matcher for blocking rules. | 253 * Matcher for blocking rules. |
| 251 * @type {Matcher} | 254 * @type {Matcher} |
| 255 * @private | |
| 252 */ | 256 */ |
| 253 this.blacklist = new Matcher(); | 257 this._blacklist = new Matcher(); |
| 254 | 258 |
| 255 /** | 259 /** |
| 256 * Matcher for exception rules. | 260 * Matcher for exception rules. |
| 257 * @type {Matcher} | 261 * @type {Matcher} |
| 262 * @private | |
| 258 */ | 263 */ |
| 259 this.whitelist = new Matcher(); | 264 this._whitelist = new Matcher(); |
| 260 | 265 |
| 261 /** | 266 /** |
| 262 * Lookup table of previous {@link Matcher#matchesAny} results | 267 * Lookup table of previous {@link Matcher#matchesAny} results |
| 263 * @type {Map.<string,Filter>} | 268 * @type {Map.<string,Filter>} |
| 269 * @private | |
| 264 */ | 270 */ |
| 265 this.resultCache = new Map(); | 271 this._resultCache = new Map(); |
| 266 } | 272 } |
| 267 | 273 |
| 268 /** | 274 /** |
| 269 * @see Matcher#clear | 275 * @see Matcher#clear |
| 270 */ | 276 */ |
| 271 clear() | 277 clear() |
| 272 { | 278 { |
| 273 this.blacklist.clear(); | 279 this._blacklist.clear(); |
| 274 this.whitelist.clear(); | 280 this._whitelist.clear(); |
| 275 this.resultCache.clear(); | 281 this._resultCache.clear(); |
| 276 } | 282 } |
| 277 | 283 |
| 278 /** | 284 /** |
| 279 * @see Matcher#add | 285 * @see Matcher#add |
| 280 * @param {Filter} filter | 286 * @param {Filter} filter |
| 281 */ | 287 */ |
| 282 add(filter) | 288 add(filter) |
| 283 { | 289 { |
| 284 if (filter instanceof WhitelistFilter) | 290 if (filter instanceof WhitelistFilter) |
| 285 this.whitelist.add(filter); | 291 this._whitelist.add(filter); |
| 286 else | 292 else |
| 287 this.blacklist.add(filter); | 293 this._blacklist.add(filter); |
| 288 | 294 |
| 289 this.resultCache.clear(); | 295 this._resultCache.clear(); |
| 290 } | 296 } |
| 291 | 297 |
| 292 /** | 298 /** |
| 293 * @see Matcher#remove | 299 * @see Matcher#remove |
| 294 * @param {Filter} filter | 300 * @param {Filter} filter |
| 295 */ | 301 */ |
| 296 remove(filter) | 302 remove(filter) |
| 297 { | 303 { |
| 298 if (filter instanceof WhitelistFilter) | 304 if (filter instanceof WhitelistFilter) |
| 299 this.whitelist.remove(filter); | 305 this._whitelist.remove(filter); |
| 300 else | 306 else |
| 301 this.blacklist.remove(filter); | 307 this._blacklist.remove(filter); |
| 302 | 308 |
| 303 this.resultCache.clear(); | 309 this._resultCache.clear(); |
| 304 } | 310 } |
| 305 | 311 |
| 306 /** | 312 /** |
| 307 * @see Matcher#findKeyword | 313 * @see Matcher#findKeyword |
| 308 * @param {Filter} filter | 314 * @param {Filter} filter |
| 309 * @returns {string} keyword | 315 * @returns {string} keyword |
| 316 * @protected | |
| 310 */ | 317 */ |
| 311 findKeyword(filter) | 318 findKeyword(filter) |
| 312 { | 319 { |
| 313 if (filter instanceof WhitelistFilter) | 320 if (filter instanceof WhitelistFilter) |
| 314 return this.whitelist.findKeyword(filter); | 321 return this._whitelist.findKeyword(filter); |
| 315 return this.blacklist.findKeyword(filter); | 322 return this._blacklist.findKeyword(filter); |
| 316 } | 323 } |
| 317 | 324 |
| 318 /** | 325 /** |
| 319 * Optimized filter matching testing both whitelist and blacklist matchers | 326 * Optimized filter matching testing both whitelist and blacklist matchers |
| 320 * simultaneously. For parameters see | 327 * simultaneously. For parameters see |
| 321 {@link Matcher#matchesAny Matcher.matchesAny()}. | 328 {@link Matcher#matchesAny Matcher.matchesAny()}. |
| 322 * @see Matcher#matchesAny | 329 * @see Matcher#matchesAny |
| 323 * @inheritdoc | 330 * @inheritdoc |
| 331 * @private | |
| 324 */ | 332 */ |
| 325 matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey, | 333 _matchesAnyInternal(location, typeMask, docDomain, thirdParty, sitekey, |
| 326 specificOnly) | 334 specificOnly) |
| 327 { | 335 { |
| 328 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); | 336 let candidates = location.toLowerCase().match(/[a-z0-9%]{3,}/g); |
| 329 if (candidates === null) | 337 if (candidates === null) |
| 330 candidates = []; | 338 candidates = []; |
| 331 candidates.push(""); | 339 candidates.push(""); |
| 332 | 340 |
| 333 let whitelistHit = null; | 341 let whitelistHit = null; |
| 334 let blacklistHit = null; | 342 let blacklistHit = null; |
| 335 | 343 |
| 336 // If the type mask includes no types other than whitelist-only types, we | 344 // If the type mask includes no types other than whitelist-only types, we |
| 337 // can skip the blacklist. | 345 // can skip the blacklist. |
| 338 if ((typeMask & ~WHITELIST_ONLY_TYPES) != 0) | 346 if ((typeMask & ~WHITELIST_ONLY_TYPES) != 0) |
| 339 { | 347 { |
| 340 for (let i = 0, l = candidates.length; !blacklistHit && i < l; i++) | 348 for (let i = 0, l = candidates.length; !blacklistHit && i < l; i++) |
| 341 { | 349 { |
| 342 blacklistHit = this.blacklist._checkEntryMatch(candidates[i], location, | 350 blacklistHit = this._blacklist.checkEntryMatch(candidates[i], location, |
| 343 typeMask, docDomain, | 351 typeMask, docDomain, |
| 344 thirdParty, sitekey, | 352 thirdParty, sitekey, |
| 345 specificOnly); | 353 specificOnly); |
| 346 } | 354 } |
| 347 } | 355 } |
| 348 | 356 |
| 349 // If the type mask includes any whitelist-only types, we need to check the | 357 // If the type mask includes any whitelist-only types, we need to check the |
| 350 // whitelist. | 358 // whitelist. |
| 351 if (blacklistHit || (typeMask & WHITELIST_ONLY_TYPES) != 0) | 359 if (blacklistHit || (typeMask & WHITELIST_ONLY_TYPES) != 0) |
| 352 { | 360 { |
| 353 for (let i = 0, l = candidates.length; !whitelistHit && i < l; i++) | 361 for (let i = 0, l = candidates.length; !whitelistHit && i < l; i++) |
| 354 { | 362 { |
| 355 whitelistHit = this.whitelist._checkEntryMatch(candidates[i], location, | 363 whitelistHit = this._whitelist.checkEntryMatch(candidates[i], location, |
| 356 typeMask, docDomain, | 364 typeMask, docDomain, |
| 357 thirdParty, sitekey); | 365 thirdParty, sitekey); |
| 358 } | 366 } |
| 359 } | 367 } |
| 360 | 368 |
| 361 return whitelistHit || blacklistHit; | 369 return whitelistHit || blacklistHit; |
| 362 } | 370 } |
| 363 | 371 |
| 364 /** | 372 /** |
| 365 * @see Matcher#matchesAny | 373 * @see Matcher#matchesAny |
| 366 * @inheritdoc | 374 * @inheritdoc |
| 367 */ | 375 */ |
| 368 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) | 376 matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly) |
| 369 { | 377 { |
| 370 let key = location + " " + typeMask + " " + docDomain + " " + thirdParty + | 378 let key = location + " " + typeMask + " " + docDomain + " " + thirdParty + |
| 371 " " + sitekey + " " + specificOnly; | 379 " " + sitekey + " " + specificOnly; |
| 372 | 380 |
| 373 let result = this.resultCache.get(key); | 381 let result = this._resultCache.get(key); |
| 374 if (typeof result != "undefined") | 382 if (typeof result != "undefined") |
| 375 return result; | 383 return result; |
| 376 | 384 |
| 377 result = this.matchesAnyInternal(location, typeMask, docDomain, | 385 result = this._matchesAnyInternal(location, typeMask, docDomain, |
| 378 thirdParty, sitekey, specificOnly); | 386 thirdParty, sitekey, specificOnly); |
| 379 | 387 |
| 380 if (this.resultCache.size >= this.maxCacheEntries) | 388 if (this._resultCache.size >= this.maxCacheEntries) |
| 381 this.resultCache.clear(); | 389 this._resultCache.clear(); |
| 382 | 390 |
| 383 this.resultCache.set(key, result); | 391 this._resultCache.set(key, result); |
| 384 | 392 |
| 385 return result; | 393 return result; |
| 386 } | 394 } |
| 387 } | 395 } |
| 388 | 396 |
| 389 exports.CombinedMatcher = CombinedMatcher; | 397 exports.CombinedMatcher = CombinedMatcher; |
| 390 | 398 |
| 391 /** | 399 /** |
| 392 * Shared {@link CombinedMatcher} instance that should usually be used. | 400 * Shared {@link CombinedMatcher} instance that should usually be used. |
| 393 * @type {CombinedMatcher} | 401 * @type {CombinedMatcher} |
| 394 */ | 402 */ |
| 395 let defaultMatcher = new CombinedMatcher(); | 403 let defaultMatcher = new CombinedMatcher(); |
| 396 | 404 |
| 397 exports.defaultMatcher = defaultMatcher; | 405 exports.defaultMatcher = defaultMatcher; |
| OLD | NEW |