diff options
Diffstat (limited to 'data/extensions/uBlock0@raymondhill.net/js/static-net-filtering.js')
| -rw-r--r-- | data/extensions/uBlock0@raymondhill.net/js/static-net-filtering.js | 5923 |
1 files changed, 5923 insertions, 0 deletions
diff --git a/data/extensions/uBlock0@raymondhill.net/js/static-net-filtering.js b/data/extensions/uBlock0@raymondhill.net/js/static-net-filtering.js new file mode 100644 index 0000000..6651f08 --- /dev/null +++ b/data/extensions/uBlock0@raymondhill.net/js/static-net-filtering.js @@ -0,0 +1,5923 @@ +/******************************************************************************* + + uBlock Origin - a comprehensive, efficient content blocker + Copyright (C) 2014-present Raymond Hill + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see {http://www.gnu.org/licenses/}. + + Home: https://github.com/gorhill/uBlock +*/ + +import * as sfp from './static-filtering-parser.js'; + +import { domainFromHostname, hostnameFromNetworkURL } from './uri-utils.js'; +import { dropTask, queueTask } from './tasks.js'; +import { isRE2, toHeaderPattern, tokenizableStrFromRegex } from './regex-analyzer.js'; + +import BidiTrieContainer from './biditrie.js'; +import { CompiledListReader } from './static-filtering-io.js'; +import { FilteringContext } from './filtering-context.js'; +import HNTrieContainer from './hntrie.js'; +import { urlSkip } from './urlskip.js'; + +/******************************************************************************/ + +// Access to a key-val store is optional and useful only for optimal +// initialization at module load time. Probably could re-arrange code +// to export an init() function with optimization parameters which would +// need to be called by module clients. For now, I want modularizing with +// minimal amount of changes. + +const keyvalStore = typeof vAPI !== 'undefined' + ? vAPI.localStorage + : { getItem() { return null; }, setItem() {}, removeItem() {} }; + +/******************************************************************************/ + +// 10fedcba9876543210 +// |||||||| | || | +// |||||||| | || | +// |||||||| | || | +// |||||||| | || | +// |||||||| | || +---- bit 0- 1: block=0, allow=1, block important=2 +// |||||||| | |+------ bit 2: unused +// |||||||| | +------- bit 3- 4: party [0-3] +// |||||||| +--------- bit 5- 9: type [0-31] +// |||||||+-------------- bit 10: headers-based filters +// ||||||+--------------- bit 11: redirect filters +// |||||+---------------- bit 12: removeparam filters +// ||||+----------------- bit 13: csp filters +// |||+------------------ bit 14: permissions filters +// ||+------------------- bit 15: uritransform filters +// |+-------------------- bit 16: replace filters +// +--------------------- bit 17: urlskip filters +// TODO: bit 11-17 could be converted into 3-bit value, as these options are not +// meant to be combined. + +const BLOCK_REALM = 0b0000_0000_0000_0000_0000; +const ALLOW_REALM = 0b0000_0000_0000_0000_0001; +const IMPORTANT_REALM = 0b0000_0000_0000_0000_0010; +const BLOCKALLOW_REALM = BLOCK_REALM | ALLOW_REALM | IMPORTANT_REALM; +const BLOCKIMPORTANT_REALM = BLOCK_REALM | IMPORTANT_REALM; +const ANYPARTY_REALM = 0b0000_0000_0000_0000_0000; +const FIRSTPARTY_REALM = 0b0000_0000_0000_0000_1000; +const THIRDPARTY_REALM = 0b0000_0000_0000_0001_0000; +const ALLPARTIES_REALM = FIRSTPARTY_REALM | THIRDPARTY_REALM; +const TYPE_REALM = 0b0000_0000_0011_1110_0000; +const HEADERS_REALM = 0b0000_0000_0100_0000_0000; +const REDIRECT_REALM = 0b0000_0000_1000_0000_0000; +const REMOVEPARAM_REALM = 0b0000_0001_0000_0000_0000; +const CSP_REALM = 0b0000_0010_0000_0000_0000; +const PERMISSIONS_REALM = 0b0000_0100_0000_0000_0000; +const URLTRANSFORM_REALM = 0b0000_1000_0000_0000_0000; +const REPLACE_REALM = 0b0001_0000_0000_0000_0000; +const URLSKIP_REALM = 0b0010_0000_0000_0000_0000; +const MODIFY_REALMS = REDIRECT_REALM | CSP_REALM | + REMOVEPARAM_REALM | PERMISSIONS_REALM | + URLTRANSFORM_REALM | REPLACE_REALM | + URLSKIP_REALM; + +const TYPE_REALM_OFFSET = 5; + +const typeNameToTypeValue = { + 'no_type': 0 << TYPE_REALM_OFFSET, + 'stylesheet': 1 << TYPE_REALM_OFFSET, + 'image': 2 << TYPE_REALM_OFFSET, + 'object': 3 << TYPE_REALM_OFFSET, + 'object_subrequest': 3 << TYPE_REALM_OFFSET, + 'script': 4 << TYPE_REALM_OFFSET, + 'fetch': 5 << TYPE_REALM_OFFSET, + 'xmlhttprequest': 5 << TYPE_REALM_OFFSET, + 'sub_frame': 6 << TYPE_REALM_OFFSET, + 'font': 7 << TYPE_REALM_OFFSET, + 'media': 8 << TYPE_REALM_OFFSET, + 'websocket': 9 << TYPE_REALM_OFFSET, + 'beacon': 10 << TYPE_REALM_OFFSET, + 'ping': 10 << TYPE_REALM_OFFSET, + 'other': 11 << TYPE_REALM_OFFSET, + 'popup': 12 << TYPE_REALM_OFFSET, // start of behavioral filtering + 'popunder': 13 << TYPE_REALM_OFFSET, + 'main_frame': 14 << TYPE_REALM_OFFSET, // start of 1p behavioral filtering + 'generichide': 15 << TYPE_REALM_OFFSET, + 'specifichide': 16 << TYPE_REALM_OFFSET, + 'inline-font': 17 << TYPE_REALM_OFFSET, + 'inline-script': 18 << TYPE_REALM_OFFSET, + 'cname': 19 << TYPE_REALM_OFFSET, + 'webrtc': 20 << TYPE_REALM_OFFSET, + 'unsupported': 21 << TYPE_REALM_OFFSET, +}; + +const otherTypeBitValue = typeNameToTypeValue.other; + +const bitFromType = type => + 1 << ((typeNameToTypeValue[type] >>> TYPE_REALM_OFFSET) - 1); + +// All network request types to bitmap +// bring origin to 0 (from TYPE_REALM_OFFSET -- see typeNameToTypeValue) +// left-shift 1 by the above-calculated value +// subtract 1 to set all type bits +const allNetworkTypesBits = + (1 << (otherTypeBitValue >>> TYPE_REALM_OFFSET)) - 1; + +const allTypesBits = + allNetworkTypesBits | + 1 << (typeNameToTypeValue['popup'] >>> TYPE_REALM_OFFSET) - 1 | + 1 << (typeNameToTypeValue['main_frame'] >>> TYPE_REALM_OFFSET) - 1 | + 1 << (typeNameToTypeValue['inline-font'] >>> TYPE_REALM_OFFSET) - 1 | + 1 << (typeNameToTypeValue['inline-script'] >>> TYPE_REALM_OFFSET) - 1; +const unsupportedTypeBit = + 1 << (typeNameToTypeValue['unsupported'] >>> TYPE_REALM_OFFSET) - 1; + +const typeValueToTypeName = [ + '', + 'stylesheet', + 'image', + 'object', + 'script', + 'xhr', + 'frame', + 'font', + 'media', + 'websocket', + 'ping', + 'other', + 'popup', + 'popunder', + 'document', + 'generichide', + 'specifichide', + 'inline-font', + 'inline-script', + 'cname', + '', + '', + 'webrtc', + 'unsupported', +]; + +const typeValueToDNRTypeName = [ + '', + 'stylesheet', + 'image', + 'object', + 'script', + 'xmlhttprequest', + 'sub_frame', + 'font', + 'media', + 'websocket', + 'ping', + 'other', +]; + +// Do not change order. Compiled filter lists rely on this order being +// consistent across sessions. +const MODIFIER_TYPE_REDIRECT = 1; +const MODIFIER_TYPE_REDIRECTRULE = 2; +const MODIFIER_TYPE_REMOVEPARAM = 3; +const MODIFIER_TYPE_CSP = 4; +const MODIFIER_TYPE_PERMISSIONS = 5; +const MODIFIER_TYPE_URLTRANSFORM = 6; +const MODIFIER_TYPE_REPLACE = 7; +const MODIFIER_TYPE_URLSKIP = 8; + +const modifierBitsFromType = new Map([ + [ MODIFIER_TYPE_REDIRECT, REDIRECT_REALM ], + [ MODIFIER_TYPE_REDIRECTRULE, REDIRECT_REALM ], + [ MODIFIER_TYPE_REMOVEPARAM, REMOVEPARAM_REALM ], + [ MODIFIER_TYPE_CSP, CSP_REALM ], + [ MODIFIER_TYPE_PERMISSIONS, PERMISSIONS_REALM ], + [ MODIFIER_TYPE_URLTRANSFORM, URLTRANSFORM_REALM ], + [ MODIFIER_TYPE_REPLACE, REPLACE_REALM ], + [ MODIFIER_TYPE_URLSKIP, URLSKIP_REALM ], +]); + +const modifierTypeFromName = new Map([ + [ 'redirect', MODIFIER_TYPE_REDIRECT ], + [ 'redirect-rule', MODIFIER_TYPE_REDIRECTRULE ], + [ 'removeparam', MODIFIER_TYPE_REMOVEPARAM ], + [ 'csp', MODIFIER_TYPE_CSP ], + [ 'permissions', MODIFIER_TYPE_PERMISSIONS ], + [ 'uritransform', MODIFIER_TYPE_URLTRANSFORM ], + [ 'replace', MODIFIER_TYPE_REPLACE ], + [ 'urlskip', MODIFIER_TYPE_URLSKIP ], +]); + +const modifierNameFromType = new Map([ + [ MODIFIER_TYPE_REDIRECT, 'redirect' ], + [ MODIFIER_TYPE_REDIRECTRULE, 'redirect-rule' ], + [ MODIFIER_TYPE_REMOVEPARAM, 'removeparam' ], + [ MODIFIER_TYPE_CSP, 'csp' ], + [ MODIFIER_TYPE_PERMISSIONS, 'permissions' ], + [ MODIFIER_TYPE_URLTRANSFORM, 'uritransform' ], + [ MODIFIER_TYPE_REPLACE, 'replace' ], + [ MODIFIER_TYPE_URLSKIP, 'urlskip' ], +]); + +//const typeValueFromCatBits = catBits => (catBits >>> TYPE_REALM_OFFSET) & 0b11111; + +const MAX_TOKEN_LENGTH = 7; + +// Four upper bits of token hash are reserved for built-in predefined +// token hashes, which should never end up being used when tokenizing +// any arbitrary string. +const NO_TOKEN_HASH = 0x5000_0000; +const DOT_TOKEN_HASH = 0x1000_0000; +const ANY_TOKEN_HASH = 0x2000_0000; +const ANY_HTTPS_TOKEN_HASH = 0x3000_0000; +const ANY_HTTP_TOKEN_HASH = 0x4000_0000; +const EMPTY_TOKEN_HASH = 0xF000_0000; +const INVALID_TOKEN_HASH = 0xFFFF_FFFF; + +/******************************************************************************/ + +// See the following as short-lived registers, used during evaluation. They are +// valid until the next evaluation. + +let $requestMethodBit = 0; +let $requestTypeValue = 0; +let $requestURL = ''; +let $requestURLRaw = ''; +let $requestHostname = ''; +let $requestAddress = ''; +let $docHostname = ''; +let $docDomain = ''; +let $tokenBeg = 0; +let $patternMatchLeft = 0; +let $patternMatchRight = 0; +let $isBlockImportant = false; + +const $docEntity = { + entity: '', + last: '', + compute() { + if ( this.last !== $docHostname ) { + this.last = $docHostname; + const pos = $docDomain.indexOf('.'); + this.entity = pos !== -1 + ? `${$docHostname.slice(0, pos - $docDomain.length)}.*` + : ''; + } + return this.entity; + }, +}; + +const $requestEntity = { + entity: '', + last: '', + compute() { + if ( this.last !== $requestHostname ) { + this.last = $requestHostname; + const requestDomain = domainFromHostname($requestHostname); + const pos = requestDomain.indexOf('.'); + this.entity = pos !== -1 + ? `${$requestHostname.slice(0, pos - requestDomain.length)}.*` + : ''; + } + return this.entity; + }, +}; + +const $httpHeaders = { + init(headers) { + this.headers = headers; + this.parsed.clear(); + }, + reset() { + this.headers = []; + this.parsed.clear(); + }, + lookup(name) { + if ( this.parsed.size === 0 ) { + for ( const { name, value } of this.headers ) { + this.parsed.set(name.toLowerCase(), value); + } + } + return this.parsed.get(name); + }, + headers: [], + parsed: new Map(), +}; + +/******************************************************************************/ + +// Local helpers + +const restrSeparator = '(?:[^%.0-9a-z_-]|$)'; + +// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions +const reEscape = /[.*+?^${}()|[\]\\]/g; + +// Convert a plain string (devoid of special characters) into a regex. +const restrFromPlainPattern = s => s.replace(reEscape, '\\$&'); + +const restrFromGenericPattern = function(s, anchor = 0) { + let reStr = s.replace(restrFromGenericPattern.rePlainChars, '\\$&') + .replace(restrFromGenericPattern.reSeparators, restrSeparator) + .replace(restrFromGenericPattern.reDanglingAsterisks, '') + .replace(restrFromGenericPattern.reAsterisks, '\\S*?'); + if ( anchor & 0b100 ) { + reStr = ( + reStr.startsWith('\\.') ? + restrFromGenericPattern.restrHostnameAnchor2 : + restrFromGenericPattern.restrHostnameAnchor1 + ) + reStr; + } else if ( anchor & 0b010 ) { + reStr = '^' + reStr; + } + if ( anchor & 0b001 ) { + reStr += '$'; + } + return reStr; +}; +restrFromGenericPattern.rePlainChars = /[.+?${}()|[\]\\]/g; +restrFromGenericPattern.reSeparators = /\^/g; +restrFromGenericPattern.reDanglingAsterisks = /^\*+|\*+$/g; +restrFromGenericPattern.reAsterisks = /\*+/g; +restrFromGenericPattern.restrHostnameAnchor1 = '^[a-z-]+://(?:[^/?#]+\\.)?'; +restrFromGenericPattern.restrHostnameAnchor2 = '^[a-z-]+://(?:[^/?#]+)?'; + +/******************************************************************************/ + +class LogData { + constructor(categoryBits, tokenHash, iunit) { + this.result = 0; + this.source = 'static'; + this.tokenHash = tokenHash; + if ( iunit === 0 ) { + this.raw = this.regex = ''; + return; + } + this.result = (categoryBits & ALLOW_REALM) === 0 ? 1 : 2; + const pattern = []; + const regex = []; + const options = []; + const denyallow = []; + const fromDomains = []; + const toDomains = []; + const logData = { + pattern, + regex, + denyallow, + fromDomains, + toDomains, + options, + isRegex: false, + }; + filterLogData(iunit, logData); + if ( (categoryBits & THIRDPARTY_REALM) !== 0 ) { + logData.options.unshift('3p'); + } else if ( (categoryBits & FIRSTPARTY_REALM) !== 0 ) { + logData.options.unshift('1p'); + } + const type = categoryBits & TYPE_REALM; + if ( type !== 0 ) { + logData.options.unshift(typeValueToTypeName[type >>> TYPE_REALM_OFFSET]); + } + let raw = logData.pattern.join(''); + if ( + logData.isRegex === false && + raw.charCodeAt(0) === 0x2F /* '/' */ && + raw.charCodeAt(raw.length - 1) === 0x2F /* '/' */ + ) { + raw += '*'; + } + if ( (categoryBits & ALLOW_REALM) !== 0 ) { + raw = '@@' + raw; + } + if ( denyallow.length !== 0 ) { + options.push(`denyallow=${denyallow.join('|')}`); + } + if ( fromDomains.length !== 0 ) { + options.push(`from=${fromDomains.join('|')}`); + } + if ( toDomains.length !== 0 ) { + options.push(`to=${toDomains.join('|')}`); + } + if ( options.length !== 0 ) { + raw += '$' + options.join(','); + } + this.raw = raw; + this.regex = logData.regex.join(''); + if ( logData.reason ) { + this.reason = logData.reason; + } + } + isUntokenized() { + return this.tokenHash === NO_TOKEN_HASH; + } + isPureHostname() { + return this.tokenHash === DOT_TOKEN_HASH; + } + + static requote(s) { + if ( /^\$|^(["'`]).*\1$|,/.test(s) === false ) { return s; } + if ( s.includes("'") === false ) { return `'${s}'`; } + if ( s.includes('"') === false ) { return `"${s}"`; } + if ( s.includes('`') === false ) { return `\`${s}\``; } + return `'${s.replace(/'/g, "\\'")}'`; + } +} + +/******************************************************************************/ + +const charClassMap = new Uint32Array(128); +const CHAR_CLASS_SEPARATOR = 0b00000001; + +{ + const reSeparators = /[^\w%.-]/; + for ( let i = 0; i < 128; i++ ) { + if ( reSeparators.test(String.fromCharCode(i)) ) { + charClassMap[i] |= CHAR_CLASS_SEPARATOR; + } + } +} + +const isSeparatorChar = c => (charClassMap[c] & CHAR_CLASS_SEPARATOR) !== 0; + +/******************************************************************************/ + +const FILTER_DATA_PAGE_SIZE = 65536; + +const roundToFilterDataPageSize = + len => (len + FILTER_DATA_PAGE_SIZE-1) & ~(FILTER_DATA_PAGE_SIZE-1); + +let filterData = new Int32Array(FILTER_DATA_PAGE_SIZE * 5); +let filterDataWritePtr = 2; +const filterDataGrow = len => { + if ( len <= filterData.length ) { return; } + const newLen = roundToFilterDataPageSize(len); + const newBuf = new Int32Array(newLen); + newBuf.set(filterData); + filterData = newBuf; +}; +const filterDataShrink = ( ) => { + const newLen = Math.max( + roundToFilterDataPageSize(filterDataWritePtr), + FILTER_DATA_PAGE_SIZE + ); + if ( newLen >= filterData.length ) { return; } + const newBuf = new Int32Array(newLen); + newBuf.set(filterData.subarray(0, filterDataWritePtr)); + filterData = newBuf; +}; +const filterDataAlloc = (...args) => { + const len = args.length; + const idata = filterDataAllocLen(len); + for ( let i = 0; i < len; i++ ) { + filterData[idata+i] = args[i]; + } + return idata; +}; +const filterDataAllocLen = len => { + const idata = filterDataWritePtr; + filterDataWritePtr += len; + if ( filterDataWritePtr > filterData.length ) { + filterDataGrow(filterDataWritePtr); + } + return idata; +}; +const filterSequenceAdd = (a, b) => { + const iseq = filterDataAllocLen(2); + filterData[iseq+0] = a; + filterData[iseq+1] = b; + return iseq; +}; +const filterDataReset = ( ) => { + filterData.fill(0); + filterDataWritePtr = 2; +}; +const filterDataToSelfie = ( ) => + filterData.subarray(0, filterDataWritePtr); + +const filterDataFromSelfie = selfie => { + if ( selfie instanceof Int32Array === false ) { return false; } + filterData = selfie; + filterDataWritePtr = selfie.length; + return true; +}; + +const filterRefs = [ null ]; +let filterRefsWritePtr = 1; +const filterRefAdd = ref => { + const i = filterRefsWritePtr; + filterRefs[i] = ref; + filterRefsWritePtr += 1; + return i; +}; +const filterRefsReset = ( ) => { + filterRefs.fill(null); + filterRefsWritePtr = 1; +}; +const filterRefsToSelfie = ( ) => + filterRefs.slice(0, filterRefsWritePtr); + +const filterRefsFromSelfie = selfie => { + if ( Array.isArray(selfie) === false ) { return false; } + for ( let i = 0, n = selfie.length; i < n; i++ ) { + filterRefs[i] = selfie[i]; + } + filterRefsWritePtr = selfie.length; + return true; +}; + +/******************************************************************************/ + +const origHNTrieContainer = new HNTrieContainer(); +const destHNTrieContainer = new HNTrieContainer(); + +/******************************************************************************/ + +const bidiTrieMatchExtra = (l, r, ix) => { + for (;;) { + $patternMatchLeft = l; + $patternMatchRight = r; + const iu = filterData[ix+0]; + if ( filterMatch(iu) ) { return iu; } + ix = filterData[ix+1]; + if ( ix === 0 ) { break; } + } + return 0; +}; + +const bidiTrie = new BidiTrieContainer(bidiTrieMatchExtra); + +/******************************************************************************* + + Each filter class will register itself in the map. + + IMPORTANT: any change which modifies the mapping will have to be + reflected with µBlock.systemSettings.compiledMagic. + +*/ + +const filterClasses = []; +const filterArgsToUnit = new Map(); +let filterClassIdGenerator = 0; + +const registerFilterClass = fc => { + const fid = filterClassIdGenerator++; + fc.fid = fid; + fc.fidstr = `${fid}`; + filterClasses[fid] = fc; +}; + +const filterFromCompiled = args => { + const fc = filterClasses[args[0]]; + const keygen = fc.keyFromArgs; + if ( keygen === undefined ) { + return fc.fromCompiled(args); + } + const key = `${fc.fidstr} ${(keygen(args) || '')}`; + let idata = filterArgsToUnit.get(key); + if ( idata !== undefined ) { return idata; } + idata = fc.fromCompiled(args); + filterArgsToUnit.set(key, idata); + return idata; +}; + +const filterGetClass = idata => { + return filterClasses[filterData[idata+0]]; +}; + +const filterMatch = idata => filterClasses[filterData[idata+0]].match(idata); + +const filterHasOriginHit = idata => { + const fc = filterClasses[filterData[idata+0]]; + return fc.hasOriginHit !== undefined && fc.hasOriginHit(idata); +}; + +const filterGetDomainOpt = (idata, out) => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.getDomainOpt === undefined ) { return; } + const fromOpt = fc.getDomainOpt(idata); + if ( out === undefined ) { return fromOpt; } + out.push(fromOpt); +}; + +const filterGetRegexPattern = (idata, out) => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.hasRegexPattern === undefined ) { return; } + const reStr = fc.getRegexPattern(idata); + if ( out === undefined ) { return reStr; } + out.push(reStr); +}; + +const filterIsBidiTrieable = idata => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.isBidiTrieable === undefined ) { return false; } + return fc.isBidiTrieable(idata) === true; +}; + +const filterToBidiTrie = idata => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.toBidiTrie === undefined ) { return; } + return fc.toBidiTrie(idata); +}; + +const filterMatchAndFetchModifiers = (idata, env) => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.matchAndFetchModifiers === undefined ) { return; } + return fc.matchAndFetchModifiers(idata, env); +}; + +const filterGetModifierType = idata => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.getModifierType === undefined ) { return; } + return fc.getModifierType(idata); +}; + +const filterLogData = (idata, details) => { + const fc = filterClasses[filterData[idata+0]]; + if ( fc.logData === undefined ) { return; } + fc.logData(idata, details); +}; + +const filterDumpInfo = (idata) => { + const fc = filterGetClass(idata); + if ( fc.dumpInfo === undefined ) { return; } + return fc.dumpInfo(idata); +}; + +const dnrRuleFromCompiled = (args, rule) => { + const fc = filterClasses[args[0]]; + if ( fc.dnrFromCompiled === undefined ) { return false; } + fc.dnrFromCompiled(args, rule); + return true; +}; + +const dnrAddRuleError = (rule, msg) => { + rule._error = rule._error || []; + rule._error.push(msg); +}; + +const dnrAddRuleWarning = (rule, msg) => { + rule._warning = rule._warning || []; + rule._warning.push(msg); +}; + +/******************************************************************************* + + Filter classes + + Pattern: + FilterPatternAny + FilterPatternPlain + FilterPatternPlain1 + FilterPatternPlainX + FilterPatternGeneric + FilterRegex + FilterPlainTrie + FilterHostnameDict + + Pattern modifiers: + FilterAnchorHnLeft + FilterAnchorHn + FilterAnchorRight + FilterAnchorLeft + FilterTrailingSeparator + + Context, immediate: + FilterOriginHit + FilterOriginMiss + FilterOriginEntityMiss + FilterOriginEntityHit + FilterOriginHitSet + FilterOriginMissSet + FilterJustOrigin + FilterHTTPJustOrigin + FilterHTTPSJustOrigin + + Other options: + FilterDenyAllow + FilterImportant + FilterNotType + FilterStrictParty + FilterModifier + FilterOnHeaders + FilterIPAddress + + Collection: + FilterCollection + FilterCompositeAll + FilterBucket + FilterBucketIf + FilterBucketIfOriginHits + FilterBucketIfRegexHits + FilterDomainHitAny + + A single filter can be made of many parts, in which case FilterCompositeAll + is used to hold all the parts, and where all the parts must be a match in + order for the filter to be a match. + +**/ + +/******************************************************************************/ + +class FilterPatternAny { + static match() { + return true; + } + + static compile() { + return [ FilterPatternAny.fid ]; + } + + static fromCompiled(args) { + return filterDataAlloc(args[0]); + } + + static keyFromArgs() { + } + + static logData(idata, details) { + details.pattern.push('*'); + details.regex.push('^'); + } +} + +registerFilterClass(FilterPatternAny); + +/******************************************************************************/ + +class FilterImportant { + static match() { + return ($isBlockImportant = true); + } + + static compile() { + return [ FilterImportant.fid ]; + } + + static fromCompiled(args) { + return filterDataAlloc(args[0]); + } + + static dnrFromCompiled(args, rule) { + rule.__important = true; + } + + static keyFromArgs() { + } + + static logData(idata, details) { + details.options.unshift('important'); + } +} + +registerFilterClass(FilterImportant); + +/******************************************************************************/ + +class FilterPatternPlain { + static isBidiTrieable(idata) { + return filterData[idata+2] <= 255; + } + + static toBidiTrie(idata) { + return { + i: filterData[idata+1], + n: filterData[idata+2], + itok: filterData[idata+3], + }; + } + + static match(idata) { + const left = $tokenBeg; + const n = filterData[idata+2]; + if ( + bidiTrie.startsWith( + left, + bidiTrie.getHaystackLen(), + filterData[idata+1], + n + ) === 0 + ) { + return false; + } + $patternMatchLeft = left; + $patternMatchRight = left + n; + return true; + } + + static compile(details) { + const { tokenBeg } = details; + if ( tokenBeg === 0 ) { + return [ FilterPatternPlain.fid, details.pattern, 0 ]; + } + if ( tokenBeg === 1 ) { + return [ FilterPatternPlain1.fid, details.pattern, 1 ]; + } + return [ FilterPatternPlainX.fid, details.pattern, tokenBeg ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(4); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = bidiTrie.storeString(args[1]); // i + filterData[idata+2] = args[1].length; // n + filterData[idata+3] = args[2]; // tokenBeg + return idata; + } + + static dnrFromCompiled(args, rule) { + if ( rule.condition === undefined ) { + rule.condition = {}; + } else if ( rule.condition.urlFilter !== undefined ) { + dnrAddRuleError(rule, `urlFilter already defined: ${rule.condition.urlFilter}`); + } + rule.condition.urlFilter = args[1]; + } + + static logData(idata, details) { + const s = bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ); + details.pattern.push(s); + details.regex.push(restrFromPlainPattern(s)); + // https://github.com/gorhill/uBlock/issues/3037 + // Make sure the logger reflects accurately internal match, taking + // into account MAX_TOKEN_LENGTH. + if ( /^[0-9a-z%]{1,6}$/i.exec(s.slice(filterData[idata+3])) !== null ) { + details.regex.push('(?![0-9A-Za-z%])'); + } + } + + static dumpInfo(idata) { + const pattern = bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ); + return `${pattern} ${filterData[idata+3]}`; + } +} + +FilterPatternPlain.isPatternPlain = true; + +registerFilterClass(FilterPatternPlain); + + +class FilterPatternPlain1 extends FilterPatternPlain { + static match(idata) { + const left = $tokenBeg - 1; + const n = filterData[idata+2]; + if ( + bidiTrie.startsWith( + left, + bidiTrie.getHaystackLen(), + filterData[idata+1], + n + ) === 0 + ) { + return false; + } + $patternMatchLeft = left; + $patternMatchRight = left + n; + return true; + } +} + +registerFilterClass(FilterPatternPlain1); + + +class FilterPatternPlainX extends FilterPatternPlain { + static match(idata) { + const left = $tokenBeg - filterData[idata+3]; + const n = filterData[idata+2]; + if ( + bidiTrie.startsWith( + left, + bidiTrie.getHaystackLen(), + filterData[idata+1], + n + ) === 0 + ) { + return false; + } + $patternMatchLeft = left; + $patternMatchRight = left + n; + return true; + } +} + +registerFilterClass(FilterPatternPlainX); + +/******************************************************************************/ + +class FilterPatternGeneric { + static hasRegexPattern() { + return true; + } + + static getRegexPattern(idata) { + return restrFromGenericPattern( + bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ), + filterData[idata+3] + ); + } + + static match(idata) { + const refs = filterRefs[filterData[idata+4]]; + if ( refs.$re === null ) { + refs.$re = new RegExp(this.getRegexPattern(idata)); + } + return refs.$re.test($requestURL); + } + + static compile(details) { + const out = [ + FilterPatternGeneric.fid, + details.pattern, + details.anchor, + ]; + details.anchor = 0; + return out; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(5); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = bidiTrie.storeString(args[1]); // i + filterData[idata+2] = args[1].length; // n + filterData[idata+3] = args[2]; // anchor + filterData[idata+4] = filterRefAdd({ $re: null }); + return idata; + } + + static dnrFromCompiled(args, rule) { + if ( rule.condition === undefined ) { + rule.condition = {}; + } else if ( rule.condition.urlFilter !== undefined ) { + dnrAddRuleError(rule, `urlFilter already defined: ${rule.condition.urlFilter}`); + } + let pattern = args[1]; + if ( args[2] & 0b100 ) { + if ( pattern.startsWith('.') ) { + pattern = `*${pattern}`; + } + pattern = `||${pattern}`; + } else if ( args[2] & 0b010 ) { + pattern = `|${pattern}`; + } + if ( args[2] & 0b001 ) { + pattern += '|'; + } + rule.condition.urlFilter = pattern; + } + + static keyFromArgs(args) { + return `${args[1]}\t${args[2]}`; + } + + static logData(idata, details) { + details.pattern.length = 0; + const anchor = filterData[idata+3]; + if ( (anchor & 0b100) !== 0 ) { + details.pattern.push('||'); + } else if ( (anchor & 0b010) !== 0 ) { + details.pattern.push('|'); + } + const s = bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ); + details.pattern.push(s); + if ( (anchor & 0b001) !== 0 ) { + details.pattern.push('|'); + } + details.regex.length = 0; + details.regex.push(restrFromGenericPattern(s, anchor & ~0b100)); + } + + static dumpInfo(idata) { + return bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ); + } +} + +FilterPatternGeneric.isSlow = true; + +registerFilterClass(FilterPatternGeneric); + +/******************************************************************************/ + +class FilterAnchorHnLeft { + static match(idata) { + const len = $requestHostname.length; + const haystackCodes = bidiTrie.haystack; + let lastBeg = filterData[idata+2]; + let lastEnd = filterData[idata+3]; + if ( + len !== filterData[idata+1] || + lastBeg === -1 || + haystackCodes[lastBeg-3] !== 0x3A /* ':' */ || + haystackCodes[lastBeg-2] !== 0x2F /* '/' */ || + haystackCodes[lastBeg-1] !== 0x2F /* '/' */ + ) { + lastBeg = len !== 0 ? haystackCodes.indexOf(0x3A) : -1; + if ( lastBeg !== -1 ) { + if ( + lastBeg >= bidiTrie.getHaystackLen() || + haystackCodes[lastBeg+1] !== 0x2F || + haystackCodes[lastBeg+2] !== 0x2F + ) { + lastBeg = -1; + } + } + if ( lastBeg !== -1 ) { + lastBeg += 3; + lastEnd = lastBeg + len; + } else { + lastEnd = -1; + } + filterData[idata+1] = len; + filterData[idata+2] = lastBeg; + filterData[idata+3] = lastEnd; + } + const left = $patternMatchLeft; + return left < lastEnd && ( + left === lastBeg || + left > lastBeg && haystackCodes[left-1] === 0x2E /* '.' */ + ); + } + + static compile() { + return [ FilterAnchorHnLeft.fid ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(4); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = 0; // lastLen + filterData[idata+2] = -1; // lastBeg + filterData[idata+3] = -1; // lastEnd + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.condition.urlFilter = `||${rule.condition.urlFilter}`; + } + + static keyFromArgs() { + } + + static logData(idata, details) { + details.pattern.unshift('||'); + } +} + +registerFilterClass(FilterAnchorHnLeft); + +/******************************************************************************/ + +class FilterAnchorHn extends FilterAnchorHnLeft { + static match(idata) { + return super.match(idata) && filterData[idata+3] === $patternMatchRight; + } + + static compile() { + return [ FilterAnchorHn.fid ]; + } + + static dnrFromCompiled(args, rule) { + rule.condition.requestDomains = [ rule.condition.urlFilter ]; + rule.condition.urlFilter = undefined; + } + + static keyFromArgs() { + } + + static logData(idata, details) { + super.logData(idata, details); + details.pattern.push('^'); + details.regex.push('\\.?', restrSeparator); + } +} + +registerFilterClass(FilterAnchorHn); + +/******************************************************************************/ + +class FilterAnchorLeft { + static match() { + return $patternMatchLeft === 0; + } + + static compile() { + return [ FilterAnchorLeft.fid ]; + } + + static fromCompiled(args) { + return filterDataAlloc(args[0]); + } + + static dnrFromCompiled(args, rule) { + rule.condition.urlFilter = `|${rule.condition.urlFilter}`; + } + + static keyFromArgs() { + } + + static logData(idata, details) { + details.pattern.unshift('|'); + details.regex.unshift('^'); + } +} + +registerFilterClass(FilterAnchorLeft); + +/******************************************************************************/ + +class FilterAnchorRight { + static match() { + return $patternMatchRight === $requestURL.length; + } + + static compile() { + return [ FilterAnchorRight.fid ]; + } + + static fromCompiled(args) { + return filterDataAlloc(args[0]); + } + + static dnrFromCompiled(args, rule) { + rule.condition.urlFilter = `${rule.condition.urlFilter}|`; + } + + static keyFromArgs() { + } + + static logData(idata, details) { + details.pattern.push('|'); + details.regex.push('$'); + } +} + +registerFilterClass(FilterAnchorRight); + +/******************************************************************************/ + +class FilterTrailingSeparator { + static match() { + if ( $patternMatchRight === $requestURL.length ) { return true; } + if ( isSeparatorChar(bidiTrie.haystack[$patternMatchRight]) ) { + $patternMatchRight += 1; + return true; + } + return false; + } + + static compile() { + return [ FilterTrailingSeparator.fid ]; + } + + static fromCompiled(args) { + return filterDataAlloc(args[0]); + } + + static dnrFromCompiled(args, rule) { + rule.condition.urlFilter = `${rule.condition.urlFilter}^`; + } + + static keyFromArgs() { + } + + static logData(idata, details) { + details.pattern.push('^'); + details.regex.push(restrSeparator); + } +} + +registerFilterClass(FilterTrailingSeparator); + +/******************************************************************************/ + +class FilterRegex { + static hasRegexPattern() { + return true; + } + + static getRegexPattern(idata) { + return bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ); + } + + static match(idata) { + const refs = filterRefs[filterData[idata+4]]; + if ( refs.$re === null ) { + refs.$re = new RegExp( + this.getRegexPattern(idata), + filterData[idata+3] === 0 ? 'i' : '' + ); + } + if ( refs.$re.test($requestURLRaw) === false ) { return false; } + $patternMatchLeft = $requestURLRaw.search(refs.$re); + return true; + } + + static compile(details) { + return [ + FilterRegex.fid, + details.pattern, + details.optionValues.has('match-case') ? 1 : 0, + ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(5); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = bidiTrie.storeString(args[1]); // i + filterData[idata+2] = args[1].length; // n + filterData[idata+3] = args[2]; // match-case + filterData[idata+4] = filterRefAdd({ $re: null }); + return idata; + } + + static dnrFromCompiled(args, rule) { + if ( rule.condition === undefined ) { + rule.condition = {}; + } + if ( isRE2(args[1]) === false ) { + dnrAddRuleError(rule, `regexFilter is not RE2-compatible: ${args[1]}`); + } + rule.condition.regexFilter = args[1]; + if ( args[2] === 1 ) { + rule.condition.isUrlFilterCaseSensitive = true; + } + } + + static keyFromArgs(args) { + return `${args[1]}\t${args[2]}`; + } + + static logData(idata, details) { + const s = bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ); + details.pattern.push('/', s, '/'); + details.regex.push(s); + details.isRegex = true; + if ( filterData[idata+3] !== 0 ) { + details.options.push('match-case'); + } + } + + static dumpInfo(idata) { + return [ + '/', + bidiTrie.extractString( + filterData[idata+1], + filterData[idata+2] + ), + '/', + filterData[idata+3] !== 0 ? ' (match-case)' : '', + ].join(''); + } +} + +FilterRegex.isSlow = true; + +registerFilterClass(FilterRegex); + +/******************************************************************************/ + +class FilterMethod { + static match(idata) { + if ( $requestMethodBit === 0 ) { return false; } + const methodBits = filterData[idata+1]; + const notMethodBits = filterData[idata+2]; + return (methodBits !== 0 && ($requestMethodBit & methodBits) !== 0) || + (notMethodBits !== 0 && ($requestMethodBit & notMethodBits) === 0); + } + + static compile(details) { + return [ FilterMethod.fid, details.methodBits, details.notMethodBits ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(3); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = args[1]; // methodBits + filterData[idata+2] = args[2]; // notMethodBits + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.condition = rule.condition || {}; + const rc = rule.condition; + let methodBits = args[1]; + let notMethodBits = args[2]; + if ( methodBits !== 0 && rc.requestMethods === undefined ) { + rc.requestMethods = []; + } + if ( notMethodBits !== 0 && rc.excludedRequestMethods === undefined ) { + rc.excludedRequestMethods = []; + } + for ( let i = 1; methodBits !== 0 || notMethodBits !== 0; i++ ) { + const bit = 1 << i; + const methodName = FilteringContext.getMethodName(bit); + if ( (methodBits & bit) !== 0 ) { + methodBits &= ~bit; + rc.requestMethods.push(methodName); + } else if ( (notMethodBits & bit) !== 0 ) { + notMethodBits &= ~bit; + rc.excludedRequestMethods.push(methodName); + } + } + } + + static keyFromArgs(args) { + return `${args[1]} ${args[2]}`; + } + + static logData(idata, details) { + const methods = []; + let methodBits = filterData[idata+1]; + let notMethodBits = filterData[idata+2]; + for ( let i = 0; methodBits !== 0 || notMethodBits !== 0; i++ ) { + const bit = 1 << i; + const methodName = FilteringContext.getMethodName(bit); + if ( (methodBits & bit) !== 0 ) { + methodBits &= ~bit; + methods.push(methodName); + } else if ( (notMethodBits & bit) !== 0 ) { + notMethodBits &= ~bit; + methods.push(`~${methodName}`); + } + } + details.options.push(`method=${methods.join('|')}`); + } + + static dumpInfo(idata) { + return `0b${filterData[idata+1].toString(2)} 0b${filterData[idata+2].toString(2)}`; + } +} + +registerFilterClass(FilterMethod); + +/******************************************************************************/ + +// stylesheet: 1 => bit 0 +// image: 2 => bit 1 +// object: 3 => bit 2 +// script: 4 => bit 3 +// ... + +class FilterNotType { + static match(idata) { + return $requestTypeValue !== 0 && + (filterData[idata+1] & (1 << ($requestTypeValue - 1))) === 0; + } + + static compile(details) { + return [ FilterNotType.fid, details.notTypeBits ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(2); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = args[1]; // notTypeBits + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.condition = rule.condition || {}; + const rc = rule.condition; + if ( rc.excludedResourceTypes === undefined ) { + rc.excludedResourceTypes = [ 'main_frame' ]; + } + let bits = args[1]; + for ( let i = 1; bits !== 0 && i < typeValueToDNRTypeName.length; i++ ) { + const bit = 1 << (i - 1); + if ( (bits & bit) === 0 ) { continue; } + bits &= ~bit; + const type = typeValueToDNRTypeName[i]; + if ( type === undefined ) { continue; } + if ( rc.excludedResourceTypes.includes(type) ) { continue; } + rc.excludedResourceTypes.push(type); + } + } + + static keyFromArgs(args) { + return `${args[1]}`; + } + + static logData(idata, details) { + let bits = filterData[idata+1]; + for ( let i = 1; bits !== 0 && i < typeValueToTypeName.length; i++ ) { + const bit = 1 << (i - 1); + if ( (bits & bit) === 0 ) { continue; } + bits &= ~bit; + details.options.push(`~${typeValueToTypeName[i]}`); + } + } + + static dumpInfo(idata) { + return `0b${filterData[idata+1].toString(2)}`; + } +} + +registerFilterClass(FilterNotType); + +/******************************************************************************/ + +// A helper class to parse `domain=` option. + +class DomainOptIterator { + constructor(domainOpt) { + this.reset(domainOpt); + } + reset(domainOpt) { + this.domainOpt = domainOpt; + this.i = 0; + this.value = undefined; + this.done = false; + return this; + } + next() { + if ( this.i === -1 ) { + this.domainOpt = ''; + this.value = undefined; + this.done = true; + return this; + } + const pos = this.domainOpt.indexOf('|', this.i); + if ( pos !== -1 ) { + this.value = this.domainOpt.slice(this.i, pos); + this.i = pos + 1; + } else { + this.value = this.domainOpt.slice(this.i); + this.i = -1; + } + return this; + } + [Symbol.iterator]() { + return this; + } +} + +// A helper instance to reuse throughout +const domainOptIterator = new DomainOptIterator(''); + +/******************************************************************************/ + +// The optimal class is picked according to the content of the `from=` +// filter option. +const compileDomainOpt = (ctors, iterable, prepend, units) => { + const hostnameHits = []; + const hostnameMisses = []; + const entityHits = []; + const entityMisses = []; + const regexHits = []; + const regexMisses = []; + for ( const s of iterable ) { + const len = s.length; + const beg = len > 1 && s.charCodeAt(0) === 0x7E /* '~' */ ? 1 : 0; + if ( len <= beg ) { continue; } + if ( s.charCodeAt(beg) === 0x2F /* / */ ) { + if ( beg === 0 ) { regexHits.push(s); continue; } + regexMisses.push(s.slice(1)); continue; + } + if ( s.endsWith('.*') === false ) { + if ( beg === 0 ) { hostnameHits.push(s); continue; } + hostnameMisses.push(s.slice(1)); continue; + } + if ( beg === 0 ) { entityHits.push(s); continue; } + entityMisses.push(s.slice(1)); continue; + } + const toTrie = []; + let trieWhich = 0b00; + if ( hostnameHits.length > 1 ) { + toTrie.push(...hostnameHits); + hostnameHits.length = 0; + trieWhich |= 0b01; + } + if ( entityHits.length > 1 ) { + toTrie.push(...entityHits); + entityHits.length = 0; + trieWhich |= 0b10; + } + const compiledHit = []; + if ( toTrie.length !== 0 ) { + compiledHit.push( + ctors[2].compile(toTrie.sort(), trieWhich) + ); + } + for ( const hn of hostnameHits ) { + compiledHit.push(ctors[0].compile(hn)); + } + for ( const hn of entityHits ) { + compiledHit.push(ctors[1].compile(hn)); + } + for ( const hn of regexHits ) { + compiledHit.push(ctors[3].compile(hn)); + } + if ( compiledHit.length > 1 ) { + compiledHit[0] = FilterDomainHitAny.compile(compiledHit.slice()); + compiledHit.length = 1; + } + toTrie.length = trieWhich = 0; + if ( hostnameMisses.length > 1 ) { + toTrie.push(...hostnameMisses); + hostnameMisses.length = 0; + trieWhich |= 0b01; + } + if ( entityMisses.length > 1 ) { + toTrie.push(...entityMisses); + entityMisses.length = 0; + trieWhich |= 0b10; + } + const compiledMiss = []; + if ( toTrie.length !== 0 ) { + compiledMiss.push( + ctors[6].compile(toTrie.sort(), trieWhich) + ); + } + for ( const hn of hostnameMisses ) { + compiledMiss.push(ctors[4].compile(hn)); + } + for ( const hn of entityMisses ) { + compiledMiss.push(ctors[5].compile(hn)); + } + for ( const hn of regexMisses ) { + compiledMiss.push(ctors[7].compile(hn)); + } + if ( prepend ) { + if ( compiledHit.length !== 0 ) { + units.unshift(compiledHit[0]); + } + if ( compiledMiss.length !== 0 ) { + units.unshift(...compiledMiss); + } + } else { + if ( compiledMiss.length !== 0 ) { + units.push(...compiledMiss); + } + if ( compiledHit.length !== 0 ) { + units.push(compiledHit[0]); + } + } +}; + +/******************************************************************************/ + +class FilterDomainHit { + static getDomainOpt(idata) { + return this.hntrieContainer.extractHostname( + filterData[idata+1], + filterData[idata+2] + ); + } + + static match(idata) { + return this.hntrieContainer.matchesHostname( + this.getMatchTarget(), + filterData[idata+1], + filterData[idata+2] + ); + } + + static compile(hostname) { + return [ this.fid, hostname ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(3); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = this.hntrieContainer.storeHostname(args[1]); // i + filterData[idata+2] = args[1].length; // n + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.condition = rule.condition || {}; + const prop = this.dnrConditionName; + if ( rule.condition[prop] === undefined ) { + rule.condition[prop] = []; + } + rule.condition[prop].push(args[1]); + } + + static dumpInfo(idata) { + return this.getDomainOpt(idata); + } +} + +/******************************************************************************/ + +class FilterDomainHitSet { + static getDomainOpt(idata) { + return this.hntrieContainer.extractDomainOpt( + filterData[idata+1], + filterData[idata+2] + ); + } + + static getTrieCount(idata) { + const itrie = filterData[idata+4]; + if ( itrie === 0 ) { return 0; } + return Array.from( + this.hntrieContainer.trieIterator(filterData[idata+4]) + ).length; + } + + static getLastResult(idata) { + return filterData[idata+5]; + } + + static getMatchedHostname(idata) { + const lastResult = filterData[idata+5]; + if ( lastResult === -1 ) { return ''; } + return this.getMatchTarget(lastResult >>> 8).slice(lastResult & 0xFF); + } + + static match(idata) { + const refs = filterRefs[filterData[idata+6]]; + const docHostname = this.getMatchTarget(0b01); + if ( docHostname === refs.$last ) { + return filterData[idata+5] !== -1; + } + refs.$last = docHostname; + const which = filterData[idata+3]; + const itrie = filterData[idata+4] || this.toTrie(idata); + if ( itrie === 0 ) { return false; } + if ( (which & 0b01) !== 0 ) { + const pos = this.hntrieContainer + .setNeedle(docHostname) + .matches(itrie); + if ( pos !== -1 ) { + filterData[idata+5] = 0b01 << 8 | pos; + return true; + } + } + if ( (which & 0b10) !== 0 ) { + const pos = this.hntrieContainer + .setNeedle(this.getMatchTarget(0b10)) + .matches(itrie); + if ( pos !== -1 ) { + filterData[idata+5] = 0b10 << 8 | pos; + return true; + } + } + filterData[idata+5] = -1; + return false; + } + + static add(idata, hn) { + this.hntrieContainer.setNeedle(hn).add(filterData[idata+4]); + filterData[idata+3] |= hn.charCodeAt(hn.length - 1) !== 0x2A /* '*' */ + ? 0b01 + : 0b10; + filterData[idata+5] = -1; + filterRefs[filterData[idata+6]].$last = ''; + } + + static create(fid = -1) { + const idata = filterDataAllocLen(7); + filterData[idata+0] = fid !== -1 ? fid : this.fid; + filterData[idata+1] = 0; + filterData[idata+2] = 0; + filterData[idata+3] = 0; + filterData[idata+4] = this.hntrieContainer.createTrie(); + filterData[idata+5] = -1; // $lastResult + filterData[idata+6] = filterRefAdd({ $last: '' }); + return idata; + } + + static compile(hostnames, which) { + const stringified = Array.isArray(hostnames) + ? hostnames.join('|') + : hostnames; + return [ this.fid, stringified, which ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(7); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = this.hntrieContainer.storeDomainOpt(args[1]); + filterData[idata+2] = args[1].length; + filterData[idata+3] = args[2]; // which + filterData[idata+4] = 0; // itrie + filterData[idata+5] = -1; // $lastResult + filterData[idata+6] = filterRefAdd({ $last: '' }); + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.condition = rule.condition || {}; + const prop = this.dnrConditionName; + if ( rule.condition[prop] === undefined ) { + rule.condition[prop] = []; + } + rule.condition[prop].push(...args[1].split('|')); + } + + static toTrie(idata) { + if ( filterData[idata+2] === 0 ) { return 0; } + const itrie = filterData[idata+4] = + this.hntrieContainer.createTrieFromStoredDomainOpt( + filterData[idata+1], + filterData[idata+2] + ); + return itrie; + } + + static keyFromArgs(args) { + return args[1]; + } + + static dumpInfo(idata) { + return `0b${filterData[idata+3].toString(2)} ${this.getDomainOpt(idata)}`; + } +} + +/******************************************************************************/ + +class FilterDomainRegexHit { + static getDomainOpt(idata) { + const ref = filterRefs[filterData[idata+1]]; + return ref.restr; + } + + static match(idata) { + const ref = filterRefs[filterData[idata+1]]; + if ( ref.$re === null ) { + ref.$re = new RegExp(ref.restr.slice(1,-1)); + } + return ref.$re.test(this.getMatchTarget()); + } + + static compile(restr) { + return [ this.fid, restr ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(2); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = filterRefAdd({ restr: args[1], $re: null }); + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.condition = rule.condition || {}; + const prop = this.dnrConditionName; + if ( rule.condition[prop] === undefined ) { + rule.condition[prop] = []; + } + rule.condition[prop].push(args[1]); + } + + static dumpInfo(idata) { + return this.getDomainOpt(idata); + } +} + +/******************************************************************************/ + +// Implement the following filter option: +// - domain= +// - from= + +class FilterFromDomainHit extends FilterDomainHit { + static hasOriginHit() { + return true; + } + + static getMatchTarget() { + return $docHostname; + } + + static get dnrConditionName() { + return 'initiatorDomains'; + } + + static logData(idata, details) { + details.fromDomains.push(this.getDomainOpt(idata)); + } +} +Object.defineProperty(FilterFromDomainHit, 'hntrieContainer', { + value: origHNTrieContainer +}); + +class FilterFromDomainMiss extends FilterFromDomainHit { + static hasOriginHit() { + return false; + } + + static get dnrConditionName() { + return 'excludedInitiatorDomains'; + } + + static match(idata) { + return super.match(idata) === false; + } + + static logData(idata, details) { + details.fromDomains.push(`~${this.getDomainOpt(idata)}`); + } +} + +class FilterFromEntityHit extends FilterFromDomainHit { + static getMatchTarget() { + return $docEntity.compute(); + } +} + +class FilterFromEntityMiss extends FilterFromDomainMiss { + static getMatchTarget() { + return $docEntity.compute(); + } +} + +class FilterFromDomainHitSet extends FilterDomainHitSet { + static hasOriginHit() { + return true; + } + + static getMatchTarget(which) { + return (which & 0b01) !== 0 + ? $docHostname + : $docEntity.compute(); + } + + static get dnrConditionName() { + return 'initiatorDomains'; + } + + static logData(idata, details) { + details.fromDomains.push(this.getDomainOpt(idata)); + } +} +Object.defineProperty(FilterFromDomainHitSet, 'hntrieContainer', { + value: origHNTrieContainer +}); + +class FilterFromDomainMissSet extends FilterFromDomainHitSet { + static hasOriginHit() { + return false; + } + + static match(idata) { + return super.match(idata) === false; + } + + static get dnrConditionName() { + return 'excludedInitiatorDomains'; + } + + static logData(idata, details) { + details.fromDomains.push('~' + this.getDomainOpt(idata).replace(/\|/g, '|~')); + } +} + +class FilterFromRegexHit extends FilterDomainRegexHit { + static getMatchTarget() { + return $docHostname; + } + + static get dnrConditionName() { + return 'initiatorDomains'; + } + + static logData(idata, details) { + details.fromDomains.push(`${this.getDomainOpt(idata)}`); + } +} + +class FilterFromRegexMiss extends FilterFromRegexHit { + static match(idata) { + return super.match(idata) === false; + } + + static get dnrConditionName() { + return 'excludedInitiatorDomains'; + } + + static logData(idata, details) { + details.fromDomains.push(`~${this.getDomainOpt(idata)}`); + } +} + +registerFilterClass(FilterFromDomainHit); +registerFilterClass(FilterFromDomainMiss); +registerFilterClass(FilterFromEntityHit); +registerFilterClass(FilterFromEntityMiss); +registerFilterClass(FilterFromDomainHitSet); +registerFilterClass(FilterFromDomainMissSet); +registerFilterClass(FilterFromRegexHit); +registerFilterClass(FilterFromRegexMiss); + +const fromOptClasses = [ + FilterFromDomainHit, + FilterFromEntityHit, + FilterFromDomainHitSet, + FilterFromRegexHit, + FilterFromDomainMiss, + FilterFromEntityMiss, + FilterFromDomainMissSet, + FilterFromRegexMiss, +]; + +const compileFromDomainOpt = (...args) => { + return compileDomainOpt(fromOptClasses, ...args); +}; + +/******************************************************************************/ + +// Implement the following filter option: +// - to= + +class FilterToDomainHit extends FilterDomainHit { + static getMatchTarget() { + return $requestHostname; + } + + static get dnrConditionName() { + return 'requestDomains'; + } + + static logData(idata, details) { + details.toDomains.push(this.getDomainOpt(idata)); + } +} +Object.defineProperty(FilterToDomainHit, 'hntrieContainer', { + value: destHNTrieContainer +}); + +class FilterToDomainMiss extends FilterToDomainHit { + static get dnrConditionName() { + return 'excludedRequestDomains'; + } + + static match(idata) { + return super.match(idata) === false; + } + + static logData(idata, details) { + details.toDomains.push(`~${this.getDomainOpt(idata)}`); + } +} + +class FilterToEntityHit extends FilterToDomainHit { + static getMatchTarget() { + return $requestEntity.compute(); + } +} + +class FilterToEntityMiss extends FilterToDomainMiss { + static getMatchTarget() { + return $requestEntity.compute(); + } +} + +class FilterToDomainHitSet extends FilterDomainHitSet { + static getMatchTarget(which) { + return (which & 0b01) !== 0 + ? $requestHostname + : $requestEntity.compute(); + } + + static get dnrConditionName() { + return 'requestDomains'; + } + + static logData(idata, details) { + details.toDomains.push(this.getDomainOpt(idata)); + } +} +Object.defineProperty(FilterToDomainHitSet, 'hntrieContainer', { + value: destHNTrieContainer +}); + +class FilterToDomainMissSet extends FilterToDomainHitSet { + static match(idata) { + return super.match(idata) === false; + } + + static get dnrConditionName() { + return 'excludedRequestDomains'; + } + + static logData(idata, details) { + details.toDomains.push('~' + this.getDomainOpt(idata).replace(/\|/g, '|~')); + } +} + +class FilterToRegexHit extends FilterDomainRegexHit { + static getMatchTarget() { + return $requestHostname; + } + + static get dnrConditionName() { + return 'requestDomains'; + } + + static logData(idata, details) { + details.toDomains.push(`${this.getDomainOpt(idata)}`); + } +} + +class FilterToRegexMiss extends FilterToRegexHit { + static match(idata) { + return super.match(idata) === false; + } + + static get dnrConditionName() { + return 'excludedRequestDomains'; + } + + static logData(idata, details) { + details.toDomains.push(`~${this.getDomainOpt(idata)}`); + } +} + +registerFilterClass(FilterToDomainHit); +registerFilterClass(FilterToDomainMiss); +registerFilterClass(FilterToEntityHit); +registerFilterClass(FilterToEntityMiss); +registerFilterClass(FilterToDomainHitSet); +registerFilterClass(FilterToDomainMissSet); +registerFilterClass(FilterToRegexHit); +registerFilterClass(FilterToRegexMiss); + +const toOptClasses = [ + FilterToDomainHit, + FilterToEntityHit, + FilterToDomainHitSet, + FilterToRegexHit, + FilterToDomainMiss, + FilterToEntityMiss, + FilterToDomainMissSet, + FilterToRegexMiss, +]; + +const compileToDomainOpt = (...args) => { + return compileDomainOpt(toOptClasses, ...args); +}; + +/******************************************************************************/ + +class FilterDenyAllow extends FilterToDomainMissSet { + static compile(details) { + return super.compile(details.optionValues.get('denyallow'), 0b01); + } + + static logData(idata, details) { + details.denyallow.push(this.getDomainOpt(idata)); + } +} + +registerFilterClass(FilterDenyAllow); + +/******************************************************************************/ + +class FilterModifier { + static getModifierType(idata) { + return filterData[idata+2]; + } + + static match() { + return true; + } + + static matchAndFetchModifiers(idata, env) { + if ( this.getModifierType(idata) !== env.type ) { return; } + env.results.push(new FilterModifierResult(idata, env)); + } + + static compile(details) { + return [ + FilterModifier.fid, + details.action, + details.modifyType, + details.modifyValue || '', + ]; + } + + static fromCompiled(args) { + const idata = filterDataAllocLen(4); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = args[1]; // actionBits + filterData[idata+2] = args[2]; // type + filterData[idata+3] = filterRefAdd({ + value: args[3], + $cache: null, + }); + return idata; + } + + static dnrFromCompiled(args, rule) { + rule.__modifierAction = args[1]; + rule.__modifierType = modifierNameFromType.get(args[2]); + rule.__modifierValue = args[3]; + } + + static keyFromArgs(args) { + return `${args[1]}\t${args[2]}\t${args[3]}`; + } + + static logData(idata, details) { + let opt = modifierNameFromType.get(filterData[idata+2]); + const refs = filterRefs[filterData[idata+3]]; + if ( refs.value !== '' ) { + opt += `=${LogData.requote(refs.value)}`; + } + details.options.push(opt); + } + + static dumpInfo(idata) { + const s = modifierNameFromType.get(filterData[idata+2]); + const refs = filterRefs[filterData[idata+3]]; + if ( refs.value === '' ) { return s; } + return `${s}=${refs.value}`; + } +} + +registerFilterClass(FilterModifier); + +// Helper class for storing instances of FilterModifier which were found to +// be a match. + +class FilterModifierResult { + constructor(imodifierunit, env) { + this.imodifierunit = imodifierunit; + this.refs = filterRefs[filterData[imodifierunit+3]]; + this.ireportedunit = env.iunit; + this.th = env.th; + this.bits = (env.bits & ~BLOCKALLOW_REALM) | filterData[imodifierunit+1]; + } + + get result() { + return (this.bits & ALLOW_REALM) === 0 ? 1 : 2; + } + + get value() { + return this.refs.value; + } + + get cache() { + return this.refs.$cache; + } + + set cache(a) { + this.refs.$cache = a; + } + + logData() { + const r = new LogData(this.bits, this.th, this.ireportedunit); + r.result = this.result; + r.modifier = true; + return r; + } +} + +/******************************************************************************/ + +class FilterCollection { + static getCount(idata) { + let n = 0; + this.forEach(idata, ( ) => { n += 1; }); + return n; + } + + static forEach(idata, fn) { + let i = filterData[idata+1]; + if ( i === 0 ) { return; } + do { + const iunit = filterData[i+0]; + const r = fn(iunit); + if ( r !== undefined ) { return r; } + i = filterData[i+1]; + } while ( i !== 0 ); + } + + static unshift(idata, iunit) { + filterData[idata+1] = filterSequenceAdd(iunit, filterData[idata+1]); + } + + static shift(idata) { + filterData[idata+1] = filterData[filterData[idata+1]+1]; + } + + static create(fid = -1) { + return filterDataAlloc( + fid !== -1 ? fid : FilterCollection.fid, + 0 + ); + } + + static compile(fc, fdata) { + return [ fc.fid, fdata ]; + } + + static fromCompiled(args) { + const units = args[1]; + const n = units.length; + let iunit, inext = 0; + let i = n; + while ( i-- ) { + iunit = filterFromCompiled(units[i]); + inext = filterSequenceAdd(iunit, inext); + } + const idata = filterDataAllocLen(2); + filterData[idata+0] = args[0]; // fid + filterData[idata+1] = inext; // i + return idata; + } + + static dnrFromCompiled(args, rule) { + for ( const unit of args[1] ) { + dnrRuleFromCompiled(unit, rule); + } + } + + static logData(idata, details) { + this.forEach(idata, iunit => { + filterLogData(iunit, details); + }); + } + + static dumpInfo(idata) { + return this.getCount(idata); + } +} + +registerFilterClass(FilterCollection); + +/******************************************************************************/ + +class FilterDomainHitAny extends FilterCollection { + static getDomainOpt(idata) { + const domainOpts = []; + this.forEach(idata, iunit => { + if ( filterHasOriginHit(iunit) !== true ) { return; } + filterGetDomainOpt(iunit, domainOpts); + }); + return domainOpts.join('|'); + } + + static hasOriginHit(idata) { + this.forEach(idata, iunit => { + if ( filterHasOriginHit(iunit) ) { return true; } + }); + return false; + } + + static match(idata) { + let i = filterData[idata+1]; + while ( i !== 0 ) { + if ( filterMatch(filterData[i+0]) ) { return true; } + i = filterData[i+1]; + } + return false; + } + + static compile(fdata) { + return super.compile(FilterDomainHitAny, fdata); + } + + static fromCompiled(args) { + return super.fromCompiled(args); + } +} + +registerFilterClass(FilterDomainHitAny); + +/******************************************************************************/ + +class FilterCompositeAll extends FilterCollection { + // FilterPatternPlain is assumed to be first filter in sequence. This can + // be revisited if needed. + static isBidiTrieable(idata) { + return filterIsBidiTrieable(filterData[filterData[idata+1]+0]); + } + + static toBidiTrie(idata) { + const iseq = filterData[idata+1]; + const details = filterToBidiTrie(filterData[iseq+0]); + this.shift(idata); + return details; + } + + static getDomainOpt(idata) { + return this.forEach(idata, iunit => { + if ( filterHasOriginHit(iunit) !== true ) { return; } + return filterGetDomainOpt(iunit); + }); + } + + static hasOriginHit(idata) { + return this.forEach(idata, iunit => { + if ( filterHasOriginHit(iunit) === true ) { return true; } + }) || false; + } + + static hasRegexPattern(idata) { + return this.forEach(idata, iunit => { + const fc = filterGetClass(iunit); + if ( fc.hasRegexPattern === undefined ) { return; } + if ( fc.hasRegexPattern(iunit) === true ) { return true; } + }) || false; + } + + static getRegexPattern(idata) { + return this.forEach(idata, iunit => { + const fc = filterGetClass(iunit); + if ( fc.getRegexPattern === undefined ) { return; } + return fc.getRegexPattern(iunit); + }); + } + + static match(idata) { + let i = filterData[idata+1]; + while ( i !== 0 ) { + if ( filterMatch(filterData[i+0]) !== true ) { + return false; + } + i = filterData[i+1]; + } + return true; + } + + // IMPORTANT: the modifier filter unit is assumed to be ALWAYS the + // first unit in the sequence. This requirement ensures that we do + // not have to traverse the sequence to find the modifier filter + // unit. + static getModifierType(idata) { + const iseq = filterData[idata+1]; + const iunit = filterData[iseq+0]; + return filterGetModifierType(iunit); + } + + static matchAndFetchModifiers(idata, env) { + const iseq = filterData[idata+1]; + const iunit = filterData[iseq+0]; + if ( + filterGetModifierType(iunit) === env.type && + this.match(idata) + ) { + filterMatchAndFetchModifiers(iunit, env); + } + } + + static compile(fdata) { + return super.compile(FilterCompositeAll, fdata); + } + + static fromCompiled(args) { + return super.fromCompiled(args); + } +} + +registerFilterClass(FilterCompositeAll); + +/******************************************************************************/ + +// Dictionary of hostnames + +class FilterHostnameDict { + static getCount(idata) { + const itrie = filterData[idata+1]; + if ( itrie !== 0 ) { + return Array.from(destHNTrieContainer.trieIterator(itrie)).length; + } + return filterRefs[filterData[idata+3]].length; + } + + static match(idata) { + const itrie = filterData[idata+1] || this.optimize(idata); + return ( + filterData[idata+2] = destHNTrieContainer + .setNeedle($requestHostname) + .matches(itrie) + ) !== -1; + } + + static add(idata, hn) { + const itrie = filterData[idata+1]; + if ( itrie === 0 ) { + filterRefs[filterData[idata+3]].push(hn); + } else { + destHNTrieContainer.setNeedle(hn).add(itrie); + } + } + + static optimize(idata) { + const itrie = filterData[idata+1]; + if ( itrie !== 0 ) { return itrie; } + const hostnames = filterRefs[filterData[idata+3]]; + filterData[idata+1] = destHNTrieContainer.createTrieFromIterable(hostnames); + filterRefs[filterData[idata+3]] = null; + return filterData[idata+1]; + } + + static create() { + const idata = filterDataAllocLen(4); + filterData[idata+0] = FilterHostnameDict.fid; // fid + filterData[idata+1] = 0; // itrie + filterData[idata+2] = -1; // lastResult + filterData[idata+3] = filterRefAdd([]); // []: hostnames + return idata; + } + + static logData(idata, details) { + const hostname = $requestHostname.slice(filterData[idata+2]); + details.pattern.push('||', hostname, '^'); + details.regex.push( + restrFromPlainPattern(hostname), + '\\.?', + restrSeparator + ); + } + + static dumpInfo(idata) { + return this.getCount(idata); + } +} + +registerFilterClass(FilterHostnameDict); + +/******************************************************************************/ + +// Dictionary of hostnames for filters which only purpose is to match +// the document origin. + +class FilterJustOrigin extends FilterFromDomainHitSet { + static create(fid = -1) { + return super.create(fid !== -1 ? fid : FilterJustOrigin.fid); + } + + static logPattern(idata, details) { + details.pattern.push('*'); + details.regex.push('^'); + } + + static logData(idata, details) { + this.logPattern(idata, details); + details.fromDomains.push(this.getMatchedHostname(idata)); + } + + static dumpInfo(idata) { + return this.getTrieCount(idata); + } +} + +registerFilterClass(FilterJustOrigin); + +/******************************************************************************/ + +class FilterHTTPSJustOrigin extends FilterJustOrigin { + static match(idata) { + return $requestURL.startsWith('https://') && super.match(idata); + } + + static create() { + return super.create(FilterHTTPSJustOrigin.fid); + } + + static logPattern(idata, details) { + details.pattern.push('|https://'); + details.regex.push('^https://'); + } +} + +registerFilterClass(FilterHTTPSJustOrigin); + +/******************************************************************************/ + +class FilterHTTPJustOrigin extends FilterJustOrigin { + static match(idata) { + return $requestURL.startsWith('http://') && super.match(idata); + } + + static create() { + return super.create(FilterHTTPJustOrigin.fid); + } + + static logPattern(idata, details) { + details.pattern.push('|http://'); + details.regex.push('^http://'); + } +} + +registerFilterClass(FilterHTTPJustOrigin); + +/******************************************************************************/ + +class FilterPlainTrie { + static match(idata) { + if ( bidiTrie.matches(filterData[idata+1], $tokenBeg) !== 0 ) { + filterData[idata+2] = bidiTrie.$iu; + return true; + } + return false; + } + + static create() { + const idata = filterDataAllocLen(3); + filterData[idata+0] = FilterPlainTrie.fid; // fid + filterData[idata+1] = bidiTrie.createTrie(); // itrie + filterData[idata+2] = 0; // matchedUnit + return idata; + } + + static addUnitToTrie(idata, iunit) { + const trieDetails = filterToBidiTrie(iunit); + const itrie = filterData[idata+1]; + const id = bidiTrie.add( + itrie, + trieDetails.i, + trieDetails.n, + trieDetails.itok + ); + // No point storing a pattern with conditions if the bidi-trie already + // contain a pattern with no conditions. + const ix = bidiTrie.getExtra(id); + if ( ix === 1 ) { return; } + // If the newly stored pattern has no condition, short-circuit existing + // ones since they will always be short-circuited by the condition-less + // pattern. + const fc = filterGetClass(iunit); + if ( fc.isPatternPlain ) { + bidiTrie.setExtra(id, 1); + return; + } + // FilterCompositeAll is assumed here, i.e. with conditions. + if ( fc === FilterCompositeAll && fc.getCount(iunit) === 1 ) { + iunit = filterData[filterData[iunit+1]+0]; + } + bidiTrie.setExtra(id, filterSequenceAdd(iunit, ix)); + } + + static logData(idata, details) { + const s = $requestURL.slice(bidiTrie.$l, bidiTrie.$r); + details.pattern.push(s); + details.regex.push(restrFromPlainPattern(s)); + if ( filterData[idata+2] !== -1 ) { + filterLogData(filterData[idata+2], details); + } + } + + static dumpInfo(idata) { + return `${Array.from(bidiTrie.trieIterator(filterData[idata+1])).length}`; + } +} + +registerFilterClass(FilterPlainTrie); + +/******************************************************************************/ + +class FilterBucket extends FilterCollection { + static getCount(idata) { + return filterData[idata+2]; + } + + static forEach(idata, fn) { + return super.forEach(filterData[idata+1], fn); + } + + static match(idata) { + const icollection = filterData[idata+1]; + let iseq = filterData[icollection+1]; + while ( iseq !== 0 ) { + const iunit = filterData[iseq+0]; + if ( filterMatch(iunit) ) { + filterData[idata+3] = iunit; + return true; + } + iseq = filterData[iseq+1]; + } + return false; + } + + static matchAndFetchModifiers(idata, env) { + const icollection = filterData[idata+1]; + let iseq = filterData[icollection+1]; + while ( iseq !== 0 ) { + const iunit = filterData[iseq+0]; + env.iunit = iunit; + filterMatchAndFetchModifiers(iunit, env); + iseq = filterData[iseq+1]; + } + } + + static unshift(idata, iunit) { + super.unshift(filterData[idata+1], iunit); + filterData[idata+2] += 1; + } + + static shift(idata) { + super.shift(filterData[idata+1]); + filterData[idata+2] -= 1; + } + + static create() { + const idata = filterDataAllocLen(4); + filterData[idata+0] = FilterBucket.fid; // fid + filterData[idata+1] = FilterCollection.create(); // icollection + filterData[idata+2] = 0; // n + filterData[idata+3] = 0; // $matchedUnit + return idata; + } + + static logData(idata, details) { + filterLogData(filterData[idata+3], details); + } + + static optimize(idata, optimizeBits = 0b11) { + if ( (optimizeBits & 0b01) !== 0 ) { + if ( filterData[idata+2] >= 3 ) { + const iplaintrie = this.optimizePatternTests(idata); + if ( iplaintrie !== 0 ) { + const icollection = filterData[idata+1]; + const i = filterData[icollection+1]; + if ( i === 0 ) { return iplaintrie; } + this.unshift(idata, iplaintrie); + } + } + } + if ( (optimizeBits & 0b10) !== 0 ) { + if ( filterData[idata+2] >= 5 ) { + const ioptimized = this.optimizeMatch( + idata, + FilterBucketIfOriginHits, + 5 + ); + if ( ioptimized !== 0 ) { + const icollection = filterData[idata+1]; + const i = filterData[icollection+1]; + if ( i === 0 ) { return ioptimized; } + this.unshift(idata, ioptimized); + } + } + if ( filterData[idata+2] >= 5 ) { + const ioptimized = this.optimizeMatch( + idata, + FilterBucketIfRegexHits, + 5 + ); + if ( ioptimized !== 0 ) { + const icollection = filterData[idata+1]; + const i = filterData[icollection+1]; + if ( i === 0 ) { return ioptimized; } + this.unshift(idata, ioptimized); + } + } + } + return 0; + } + + static optimizePatternTests(idata) { + const isrccollection = filterData[idata+1]; + let n = 0; + let iseq = filterData[isrccollection+1]; + do { + if ( filterIsBidiTrieable(filterData[iseq+0]) ) { n += 1; } + iseq = filterData[iseq+1]; + } while ( iseq !== 0 && n < 3 ); + if ( n < 3 ) { return 0; } + const iplaintrie = FilterPlainTrie.create(); + iseq = filterData[isrccollection+1]; + let iprev = 0; + for (;;) { + const iunit = filterData[iseq+0]; + const inext = filterData[iseq+1]; + if ( filterIsBidiTrieable(iunit) ) { + FilterPlainTrie.addUnitToTrie(iplaintrie, iunit); + if ( iprev !== 0 ) { + filterData[iprev+1] = inext; + } else { + filterData[isrccollection+1] = inext; + } + filterData[idata+2] -= 1; + } else { + iprev = iseq; + } + if ( inext === 0 ) { break; } + iseq = inext; + } + return iplaintrie; + } + + static optimizeMatch(idata, fc, min) { + const isrccollection = filterData[idata+1]; + const candidates = []; + this.forEach(idata, iunit => { + if ( fc.canCoalesce(iunit) === false ) { return; } + candidates.push(iunit); + }); + if ( candidates.length < min ) { return 0; } + const idesbucket = FilterBucket.create(); + const idescollection = filterData[idesbucket+1]; + let coalesced; + let isrcseq = filterData[isrccollection+1]; + let iprev = 0; + for (;;) { + const iunit = filterData[isrcseq+0]; + const inext = filterData[isrcseq+1]; + if ( candidates.includes(iunit) ) { + coalesced = fc.coalesce(iunit, coalesced); + // move the sequence slot to new bucket + filterData[isrcseq+1] = filterData[idescollection+1]; + filterData[idescollection+1] = isrcseq; + filterData[idesbucket+2] += 1; + if ( iprev !== 0 ) { + filterData[iprev+1] = inext; + } else { + filterData[isrccollection+1] = inext; + } + filterData[idata+2] -= 1; + } else { + iprev = isrcseq; + } + if ( inext === 0 ) { break; } + isrcseq = inext; + } + return fc.create(coalesced, idesbucket); + } + + static dumpInfo(idata) { + return this.getCount(idata); + } +} + +registerFilterClass(FilterBucket); + +/******************************************************************************/ + +// Filter bucket objects which have a pre-test method before being treated +// as a plain filter bucket -- the pre-test method should be fast as it is +// used to avoid having to iterate through the content of the filter bucket. + +class FilterBucketIf extends FilterBucket { + static getCount(idata) { + return super.getCount(filterData[idata+1]); + } + + static forEach(idata, fn) { + return super.forEach(filterData[idata+1], fn); + } + + static match(idata) { + return this.preTest(idata) && super.match(filterData[idata+1]); + } + + static matchAndFetchModifiers(idata, env) { + if ( this.preTest(idata) ) { + super.matchAndFetchModifiers(filterData[idata+1], env); + } + } + + static create(fid, ibucket, itest) { + const idata = filterDataAllocLen(3); + filterData[idata+0] = fid; + filterData[idata+1] = ibucket; + filterData[idata+2] = itest; + return idata; + } + + static logData(idata, details) { + filterLogData(filterData[idata+1], details); + } +} + +registerFilterClass(FilterBucketIf); + +/******************************************************************************/ + +class FilterBucketIfOriginHits extends FilterBucketIf { + static preTest(idata) { + return filterMatch(filterData[idata+2]); + } + + static canCoalesce(iunit) { + return filterHasOriginHit(iunit); + } + + static coalesce(iunit, coalesced) { + if ( coalesced === undefined ) { + coalesced = new Set(); + } + const domainOpt = filterGetDomainOpt(iunit); + if ( domainOpt.includes('|') ) { + for ( const hn of domainOptIterator.reset(domainOpt) ) { + coalesced.add(hn); + } + } else { + coalesced.add(domainOpt); + } + return coalesced; + } + + static create(coalesced, ibucket) { + const units = []; + compileFromDomainOpt(coalesced, false, units); + const ihittest = filterFromCompiled(units[0]); + const ipretest = super.create( + FilterBucketIfOriginHits.fid, + ibucket, + ihittest + ); + return ipretest; + } +} + +registerFilterClass(FilterBucketIfOriginHits); + +/******************************************************************************/ + +class FilterBucketIfRegexHits extends FilterBucketIf { + static preTest(idata) { + return filterRefs[filterData[idata+2]].test($requestURLRaw); + } + + static canCoalesce(iunit) { + const fc = filterGetClass(iunit); + if ( fc.hasRegexPattern === undefined ) { return false; } + if ( fc.hasRegexPattern(iunit) !== true ) { return false; } + return true; + } + + static coalesce(iunit, coalesced) { + if ( coalesced === undefined ) { + coalesced = new Set(); + } + coalesced.add(filterGetRegexPattern(iunit)); + return coalesced; + } + + static create(coalesced, ibucket) { + const reString = Array.from(coalesced).join('|'); + return super.create( + FilterBucketIfRegexHits.fid, + ibucket, + filterRefAdd(new RegExp(reString, 'i')) + ); + } + + static dumpInfo(idata) { + return filterRefs[filterData[idata+2]].source; + } +} + +registerFilterClass(FilterBucketIfRegexHits); + +/******************************************************************************/ + +class FilterStrictParty { + // TODO: disregard `www.`? + static match(idata) { + return ($requestHostname === $docHostname) === (filterData[idata+1] === 0); + } + + static compile(details) { + return [ + FilterStrictParty.fid, + details.strictParty > 0 ? 0 : 1 + ]; + } + + static fromCompiled(args) { + return filterDataAlloc( + args[0], // fid + args[1] + ); + } + + static dnrFromCompiled(args, rule) { + const partyness = args[1] === 0 ? 1 : 3; + dnrAddRuleError(rule, `strict${partyness}p not supported`); + } + + static keyFromArgs(args) { + return `${args[1]}`; + } + + static logData(idata, details) { + details.options.push( + filterData[idata+1] === 0 ? 'strict1p' : 'strict3p' + ); + } +} + +registerFilterClass(FilterStrictParty); + +/******************************************************************************/ + +class FilterOnHeaders { + static match(idata) { + const refs = filterRefs[filterData[idata+1]]; + if ( refs.$parsed === null ) { + refs.$parsed = sfp.parseHeaderValue(refs.headerOpt); + } + const { bad, name, not, value } = refs.$parsed; + if ( bad ) { return false; } + const headerValue = $httpHeaders.lookup(name); + if ( headerValue === undefined ) { return false; } + if ( value === '' ) { return true; } + let { re } = refs.$parsed; + if ( re === undefined ) { + re = new RegExp(refs.$parsed.reStr, refs.$parsed.reFlags); + refs.$parsed.re = re; + } + return re.test(headerValue) !== not; + } + + static compile(details) { + const parsed = sfp.parseHeaderValue(details.optionValues.get('header')); + let normalized = parsed.name; + if ( parsed.value !== '' ) { + normalized += `:${parsed.value}`; + } + return [ FilterOnHeaders.fid, normalized ]; + } + + static fromCompiled(args) { + return filterDataAlloc( + args[0], // fid + filterRefAdd({ + headerOpt: args[1], + $parsed: null, + }) + ); + } + + static dnrFromCompiled(args, rule) { + rule.condition ||= {}; + const parsed = sfp.parseHeaderValue(args[1]); + if ( parsed.bad !== true ) { + const value = parsed.isRegex + ? toHeaderPattern(parsed.reStr) + : parsed.value; + if ( value !== undefined ) { + const prop = parsed.not + ? 'excludedResponseHeaders' + : 'responseHeaders'; + rule.condition[prop] ||= []; + const details = { + header: parsed.name, + }; + if ( value !== '' ) { + details.values = [ value ]; + } + rule.condition[prop].push(details); + return; + } + } + dnrAddRuleError(rule, `header="${args[1]}" not supported`); + } + + static logData(idata, details) { + const irefs = filterData[idata+1]; + const headerOpt = filterRefs[irefs].headerOpt; + let opt = 'header'; + if ( headerOpt !== '' ) { + opt += `=${LogData.requote(headerOpt)}`; + } + details.options.push(opt); + } +} + +registerFilterClass(FilterOnHeaders); + +/******************************************************************************/ + +class FilterIPAddress { + static TYPE_UNKNOWN = 0; + static TYPE_EQUAL = 1; + static TYPE_STARTSWITH = 2; + static TYPE_LAN = 3; + static TYPE_LOOPBACK = 4; + static TYPE_RE = 5; + static reIPv6IPv4lan = /^::ffff:(7f\w{2}|a\w{2}|a9fe|c0a8):\w+$/; + static reIPv6local = /^f[cd]\w{2}:/; + + static match(idata) { + const ipaddr = $requestAddress; + if ( ipaddr === '' ) { return false; } + const details = filterRefs[filterData[idata+1]]; + switch ( details.$type || this.TYPE_UNKNOWN ) { + case this.TYPE_LAN: + return this.isLAN(ipaddr); + case this.TYPE_LOOPBACK: + return this.isLoopback(ipaddr); + case this.TYPE_EQUAL: + case this.TYPE_STARTSWITH: + case this.TYPE_RE: + return details.$pattern.test(ipaddr); + default: + break; + } + const { pattern } = details; + if ( pattern === 'lan' ) { + details.$type = this.TYPE_LAN; + } else if ( pattern === 'loopback' ) { + details.$type = this.TYPE_LOOPBACK; + } else if ( pattern.startsWith('/') && pattern.endsWith('/') ) { + details.$type = this.TYPE_RE; + details.$pattern = new RegExp(pattern.slice(1, -1), 'm'); + } else if ( pattern.endsWith('*') ) { + details.$type = this.TYPE_STARTSWITH; + details.$pattern = new RegExp(`^${restrFromPlainPattern(pattern.slice(0, -1))}`, 'm'); + } else { + details.$type = this.TYPE_EQUAL; + details.$pattern = new RegExp(`^${restrFromPlainPattern(pattern)}$`, 'm'); + } + return this.match(idata); + } + + // https://github.com/uBlockOrigin/uAssets/blob/master/filters/lan-block.txt + // https://en.wikipedia.org/wiki/Reserved_IP_addresses + // `ipaddr` is assumed well-formed + static isLAN(ipaddr) { + const c0 = ipaddr.charCodeAt(0); + // ipv4 + if ( c0 === 0x30 /* 0 */ ) { + return ipaddr.startsWith('0.'); + } + if ( c0 === 0x31 /* 1 */ ) { + if ( ipaddr.startsWith('10.') ) { return true; } + if ( ipaddr.startsWith('127.') ) { return true; } + if ( ipaddr.startsWith('169.254.') ) { return true; } + if ( ipaddr.startsWith('172.') ) { + const v = parseInt(ipaddr.slice(4), 10); + return v >= 16 && v <= 31; + } + return ipaddr.startsWith('192.168.'); + } + // ipv6 + if ( c0 === 0x3A /* : */ ) { + if ( ipaddr.startsWith('::') === false ) { return false; } + if ( ipaddr === '::' || ipaddr === '::1' ) { return true; } + if ( ipaddr.startsWith('::ffff:') === false ) { return false; } + return this.reIPv6IPv4lan.test(ipaddr); + } + if ( c0 === 0x66 /* f */ ) { + return this.reIPv6local.test(ipaddr); + } + return false; + } + + static isLoopback(ipaddr) { + return ipaddr === '127.0.0.1' || ipaddr === '::1'; + } + + static compile(details) { + return [ FilterIPAddress.fid, details.optionValues.get('ipaddress') ]; + } + + static fromCompiled(args) { + const pattern = args[1]; + const details = { pattern }; + return filterDataAlloc(args[0], filterRefAdd(details)); + } + + static dnrFromCompiled(args, rule) { + dnrAddRuleError(rule, `"ipaddress=${args[1]}" not supported`); + } + + static logData(idata, details) { + const irefs = filterData[idata+1]; + details.options.push(`ipaddress=${LogData.requote(filterRefs[irefs].pattern)}`); + } +} + +registerFilterClass(FilterIPAddress); + +/******************************************************************************/ + +class FilterMessage { + static match() { + return true; + } + + static compile(details) { + return [ + FilterMessage.fid, + encodeURIComponent(details.optionValues.get('reason')), + ]; + } + + static fromCompiled(args) { + const msg = args[1]; + return filterDataAlloc(args[0], bidiTrie.storeString(msg), msg.length); + } + + static keyFromArgs(args) { + return `${args[1]}`; + } + + static logData(idata, details) { + const reason = decodeURIComponent( + bidiTrie.extractString(filterData[idata+1], filterData[idata+2]) + ); + details.reason = reason; + details.options.push(`reason=${reason}`); + } +} + +registerFilterClass(FilterMessage); + +/******************************************************************************/ +/******************************************************************************/ + +// https://github.com/gorhill/uBlock/issues/2630 +// Slice input URL into a list of safe-integer token values, instead of a list +// of substrings. The assumption is that with dealing only with numeric +// values, less underlying memory allocations, and also as a consequence +// less work for the garbage collector down the road. +// Another assumption is that using a numeric-based key value for Map() is +// more efficient than string-based key value (but that is something I would +// have to benchmark). +// Benchmark for string-based tokens vs. safe-integer token values: +// https://gorhill.github.io/obj-vs-set-vs-map/tokenize-to-str-vs-to-int.html + +// http://www.cse.yorku.ca/~oz/hash.html#djb2 +// Use above algorithm to generate token hash. + +const urlTokenizer = new (class { + constructor() { + this._chars = '0123456789%abcdefghijklmnopqrstuvwxyz'; + this._validTokenChars = new Uint8Array(128); + for ( let i = 0, n = this._chars.length; i < n; i++ ) { + this._validTokenChars[this._chars.charCodeAt(i)] = i + 1; + } + + this._urlIn = ''; + this._urlOut = ''; + this._tokenized = false; + this._hasQuery = 0; + // https://www.reddit.com/r/uBlockOrigin/comments/dzw57l/ + // Remember: 1 token needs two slots + this._tokens = new Uint32Array(bidiTrie.haystack.length + 16); + + this.knownTokens = new Uint8Array(65536); + this.resetKnownTokens(); + } + + setURL(url) { + if ( url !== this._urlIn ) { + this._urlIn = url; + this._urlOut = url.toLowerCase(); + this._hasQuery = 0; + this._tokenized = false; + } + return this._urlOut; + } + + resetKnownTokens() { + this.knownTokens.fill(0); + this.addKnownToken(DOT_TOKEN_HASH); + this.addKnownToken(ANY_TOKEN_HASH); + this.addKnownToken(ANY_HTTPS_TOKEN_HASH); + this.addKnownToken(ANY_HTTP_TOKEN_HASH); + this.addKnownToken(NO_TOKEN_HASH); + } + + addKnownToken(th) { + this.knownTokens[th & 0xFFFF] = 1; + } + + // Tokenize on demand. + getTokens() { + if ( this._tokenized ) { return this._tokens; } + let i = this._tokenize(); + this._tokens[i+0] = ANY_TOKEN_HASH; + this._tokens[i+1] = 0; + i += 2; + if ( this._urlOut.startsWith('https://') ) { + this._tokens[i+0] = ANY_HTTPS_TOKEN_HASH; + this._tokens[i+1] = 0; + i += 2; + } else if ( this._urlOut.startsWith('http://') ) { + this._tokens[i+0] = ANY_HTTP_TOKEN_HASH; + this._tokens[i+1] = 0; + i += 2; + } + this._tokens[i+0] = NO_TOKEN_HASH; + this._tokens[i+1] = 0; + this._tokens[i+2] = INVALID_TOKEN_HASH; + this._tokenized = true; + return this._tokens; + } + + hasQuery() { + if ( this._hasQuery === 0 ) { + const i = this._urlOut.indexOf('?'); + this._hasQuery = i !== -1 ? i + 1 : -1; + } + return this._hasQuery > 0; + } + + // http://www.cse.yorku.ca/~oz/hash.html#djb2 + + tokenHashFromString(s) { + const l = s.length; + if ( l === 0 ) { return EMPTY_TOKEN_HASH; } + const vtc = this._validTokenChars; + let th = vtc[s.charCodeAt(0)]; + for ( let i = 1; i !== 7 /* MAX_TOKEN_LENGTH */ && i !== l; i++ ) { + th = (th << 5) + th ^ vtc[s.charCodeAt(i)]; + } + return th & 0xFFFFFFF; + } + + stringFromTokenHash(th) { + if ( th === 0 ) { return ''; } + return th.toString(16); + } + + toSelfie() { + return this.knownTokens; + } + + fromSelfie(selfie) { + this.knownTokens = selfie; + } + + // https://github.com/chrisaljoudi/uBlock/issues/1118 + // We limit to a maximum number of tokens. + + _tokenize() { + const tokens = this._tokens; + const url = this._urlOut; + const l = bidiTrie.setHaystackLen(url.length); + if ( l === 0 ) { return 0; } + let j = 0; + let hasq = -1; + mainLoop: { + const knownTokens = this.knownTokens; + const vtc = this._validTokenChars; + const charCodes = bidiTrie.haystack; + let i = 0, n = 0, ti = 0, th = 0; + for (;;) { + for (;;) { + if ( i === l ) { break mainLoop; } + const cc = url.charCodeAt(i); + charCodes[i] = cc; + i += 1; + th = vtc[cc]; + if ( th !== 0 ) { break; } + if ( cc === 0x3F /* '?' */ ) { hasq = i; } + } + ti = i - 1; n = 1; + for (;;) { + if ( i === l ) { break; } + const cc = url.charCodeAt(i); + charCodes[i] = cc; + i += 1; + const v = vtc[cc]; + if ( v === 0 ) { + if ( cc === 0x3F /* '?' */ ) { hasq = i; } + break; + } + if ( n === 7 /* MAX_TOKEN_LENGTH */ ) { continue; } + th = (th << 5) + th ^ v; + n += 1; + } + if ( knownTokens[th & 0xFFFF] !== 0 ) { + tokens[j+0] = th & 0xFFFFFFF; + tokens[j+1] = ti; + j += 2; + } + } + } + this._hasQuery = hasq; + return j; + } +})(); + +/******************************************************************************/ +/******************************************************************************/ + +class FilterCompiler { + constructor(other = undefined) { + if ( other !== undefined ) { + return Object.assign(this, other); + } + this.reTokens = /[%0-9A-Za-z]+/g; + this.optionValues = new Map(); + this.tokenIdToNormalizedType = new Map([ + [ sfp.NODE_TYPE_NET_OPTION_NAME_CNAME, bitFromType('cname') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_CSS, bitFromType('stylesheet') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_DOC, bitFromType('main_frame') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_FONT, bitFromType('font') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_FRAME, bitFromType('sub_frame') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_GENERICBLOCK, bitFromType('unsupported') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_GHIDE, bitFromType('generichide') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_IMAGE, bitFromType('image') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_INLINEFONT, bitFromType('inline-font') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_INLINESCRIPT, bitFromType('inline-script') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_MEDIA, bitFromType('media') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_OBJECT, bitFromType('object') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_OTHER, bitFromType('other') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_PING, bitFromType('ping') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_POPUNDER, bitFromType('popunder') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_POPUP, bitFromType('popup') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_SCRIPT, bitFromType('script') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_SHIDE, bitFromType('specifichide') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_XHR, bitFromType('xmlhttprequest') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_WEBRTC, bitFromType('unsupported') ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_WEBSOCKET, bitFromType('websocket') ], + ]); + this.modifierIdToNormalizedId = new Map([ + [ sfp.NODE_TYPE_NET_OPTION_NAME_CSP, MODIFIER_TYPE_CSP ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_PERMISSIONS, MODIFIER_TYPE_PERMISSIONS ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECT, MODIFIER_TYPE_REDIRECT ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECTRULE, MODIFIER_TYPE_REDIRECTRULE ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_REMOVEPARAM, MODIFIER_TYPE_REMOVEPARAM ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_URLTRANSFORM, MODIFIER_TYPE_URLTRANSFORM ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_REPLACE, MODIFIER_TYPE_REPLACE ], + [ sfp.NODE_TYPE_NET_OPTION_NAME_URLSKIP, MODIFIER_TYPE_URLSKIP ], + ]); + // These top 100 "bad tokens" are collated using the "miss" histogram + // from tokenHistograms(). The "score" is their occurrence among the + // 200K+ URLs used in the benchmark and executed against default + // filter lists. + this.badTokens = new Map([ + [ 'https',123617 ], + [ 'com',76987 ], + [ 'js',43620 ], + [ 'www',33129 ], + [ 'jpg',32221 ], + [ 'images',31812 ], + [ 'css',19715 ], + [ 'png',19140 ], + [ 'static',15724 ], + [ 'net',15239 ], + [ 'de',13155 ], + [ 'img',11109 ], + [ 'assets',10746 ], + [ 'min',7807 ], + [ 'cdn',7568 ], + [ 'content',6900 ], + [ 'wp',6444 ], + [ 'fonts',6095 ], + [ 'svg',5976 ], + [ 'http',5813 ], + [ 'ssl',5735 ], + [ 'amazon',5440 ], + [ 'ru',5427 ], + [ 'fr',5199 ], + [ 'facebook',5178 ], + [ 'en',5146 ], + [ 'image',5028 ], + [ 'html',4837 ], + [ 'media',4833 ], + [ 'co',4783 ], + [ 'php',3972 ], + [ '2019',3943 ], + [ 'org',3924 ], + [ 'jquery',3531 ], + [ '02',3438 ], + [ 'api',3382 ], + [ 'gif',3350 ], + [ 'eu',3322 ], + [ 'prod',3289 ], + [ 'woff2',3200 ], + [ 'logo',3194 ], + [ 'themes',3107 ], + [ 'icon',3048 ], + [ 'google',3026 ], + [ 'v1',3019 ], + [ 'uploads',2963 ], + [ 'googleapis',2860 ], + [ 'v3',2816 ], + [ 'tv',2762 ], + [ 'icons',2748 ], + [ 'core',2601 ], + [ 'gstatic',2581 ], + [ 'ac',2509 ], + [ 'utag',2466 ], + [ 'id',2459 ], + [ 'ver',2448 ], + [ 'rsrc',2387 ], + [ 'files',2361 ], + [ 'uk',2357 ], + [ 'us',2271 ], + [ 'pl',2262 ], + [ 'common',2205 ], + [ 'public',2076 ], + [ '01',2016 ], + [ 'na',1957 ], + [ 'v2',1954 ], + [ '12',1914 ], + [ 'thumb',1895 ], + [ 'web',1853 ], + [ 'ui',1841 ], + [ 'default',1825 ], + [ 'main',1737 ], + [ 'false',1715 ], + [ '2018',1697 ], + [ 'embed',1639 ], + [ 'player',1634 ], + [ 'dist',1599 ], + [ 'woff',1593 ], + [ 'global',1593 ], + [ 'json',1572 ], + [ '11',1566 ], + [ '600',1559 ], + [ 'app',1556 ], + [ 'styles',1533 ], + [ 'plugins',1526 ], + [ '274',1512 ], + [ 'random',1505 ], + [ 'sites',1505 ], + [ 'imasdk',1501 ], + [ 'bridge3',1501 ], + [ 'news',1496 ], + [ 'width',1494 ], + [ 'thumbs',1485 ], + [ 'ttf',1470 ], + [ 'ajax',1463 ], + [ 'user',1454 ], + [ 'scripts',1446 ], + [ 'twitter',1440 ], + [ 'crop',1431 ], + [ 'new',1412], + ]); + this.reset(); + } + + reset() { + this.action = BLOCK_REALM; + // anchor: bit vector + // 0000 (0x0): no anchoring + // 0001 (0x1): anchored to the end of the URL. + // 0010 (0x2): anchored to the start of the URL. + // 0011 (0x3): anchored to the start and end of the URL. + // 0100 (0x4): anchored to the hostname of the URL. + // 0101 (0x5): anchored to the hostname and end of the URL. + this.anchor = 0; + this.badFilter = false; + this.error = undefined; + this.modifyType = undefined; + this.modifyValue = undefined; + this.pattern = ''; + this.party = ANYPARTY_REALM; + this.optionUnitBits = 0; + this.optionValues.clear(); + this.isPureHostname = false; + this.isGeneric = false; + this.isRegex = false; + this.strictParty = 0; + this.token = '*'; + this.tokenHash = NO_TOKEN_HASH; + this.tokenBeg = 0; + this.typeBits = 0; + this.notTypeBits = 0; + this.methodBits = 0; + this.notMethodBits = 0; + return this; + } + + start(/* writer */) { + } + + finish(/* writer */) { + } + + clone() { + return new FilterCompiler(this); + } + + normalizeRegexSource(s) { + try { + const re = new RegExp(s); + return re.source; + } catch { + } + return ''; + } + + processMethodOption(value) { + for ( const method of value.split('|') ) { + if ( method.charCodeAt(0) === 0x7E /* '~' */ ) { + const bit = FilteringContext.getMethod(method.slice(1)) || 0; + if ( bit === 0 ) { continue; } + this.notMethodBits |= bit; + } else { + const bit = FilteringContext.getMethod(method) || 0; + if ( bit === 0 ) { continue; } + this.methodBits |= bit; + } + } + this.methodBits &= ~this.notMethodBits; + } + + // https://github.com/chrisaljoudi/uBlock/issues/589 + // Be ready to handle multiple negated types + + processTypeOption(id, not) { + if ( id !== -1 ) { + const typeBit = this.tokenIdToNormalizedType.get(id); + if ( not ) { + this.notTypeBits |= typeBit; + } else { + this.typeBits |= typeBit; + } + return; + } + // `all` option + if ( not ) { + this.notTypeBits |= allTypesBits; + } else { + this.typeBits |= allTypesBits; + } + } + + processPartyOption(firstParty, not) { + if ( not ) { + firstParty = !firstParty; + } + this.party |= firstParty ? FIRSTPARTY_REALM : THIRDPARTY_REALM; + } + + processHostnameList(iter, out = []) { + let i = 0; + for ( const { hn, not, bad } of iter ) { + if ( bad ) { return ''; } + out[i] = not ? `~${hn}` : hn; + i += 1; + } + out.length = i; + return i === 1 ? out[0] : out.join('|'); + } + + processModifierOption(modifier, value) { + if ( this.modifyType !== undefined ) { return false; } + const normalized = this.modifierIdToNormalizedId.get(modifier); + if ( normalized === undefined ) { return false; } + this.modifyType = normalized; + this.modifyValue = value || ''; + return true; + } + + processCspOption(value) { + this.modifyType = MODIFIER_TYPE_CSP; + this.modifyValue = value || ''; + this.optionUnitBits |= MODIFY_BIT; + return true; + } + + processOptionWithValue(parser, id) { + switch ( id ) { + case sfp.NODE_TYPE_NET_OPTION_NAME_CSP: + if ( this.processCspOption(parser.getNetOptionValue(id)) === false ) { return false; } + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_DENYALLOW: { + const value = this.processHostnameList( + parser.getNetFilterDenyallowOptionIterator() + ); + if ( value === '' ) { return false; } + this.optionValues.set('denyallow', value); + this.optionUnitBits |= DENYALLOW_BIT; + break; + } + case sfp.NODE_TYPE_NET_OPTION_NAME_FROM: { + const iter = parser.getNetFilterFromOptionIterator(); + const list = []; + const value = this.processHostnameList(iter, list); + if ( value === '' ) { return false; } + this.optionValues.set('from', value); + this.optionValues.set('fromList', list); + this.optionUnitBits |= FROM_BIT; + break; + } + case sfp.NODE_TYPE_NET_OPTION_NAME_HEADER: { + this.optionValues.set('header', parser.getNetOptionValue(id) || ''); + this.optionUnitBits |= HEADER_BIT; + break; + } + case sfp.NODE_TYPE_NET_OPTION_NAME_IPADDRESS: + this.optionValues.set('ipaddress', parser.getNetOptionValue(id) || ''); + this.optionUnitBits |= IPADDRESS_BIT; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_METHOD: + this.processMethodOption(parser.getNetOptionValue(id)); + this.optionUnitBits |= METHOD_BIT; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_PERMISSIONS: + case sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECTRULE: + case sfp.NODE_TYPE_NET_OPTION_NAME_REMOVEPARAM: + case sfp.NODE_TYPE_NET_OPTION_NAME_REPLACE: + case sfp.NODE_TYPE_NET_OPTION_NAME_URLSKIP: + case sfp.NODE_TYPE_NET_OPTION_NAME_URLTRANSFORM: + if ( this.processModifierOption(id, parser.getNetOptionValue(id)) === false ) { + return false; + } + this.optionUnitBits |= MODIFY_BIT; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_REASON: + this.optionValues.set('reason', parser.getNetOptionValue(id)); + this.optionUnitBits |= MESSAGE_BIT; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECT: { + const actualId = this.action === ALLOW_REALM + ? sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECTRULE + : id; + if ( this.processModifierOption(actualId, parser.getNetOptionValue(id)) === false ) { + return false; + } + this.optionUnitBits |= MODIFY_BIT; + break; + } + case sfp.NODE_TYPE_NET_OPTION_NAME_TO: { + const iter = parser.getNetFilterToOptionIterator(); + const list = []; + const value = this.processHostnameList(iter, list); + if ( value === '' ) { return false; } + this.optionValues.set('to', value); + this.optionValues.set('toList', list); + this.optionUnitBits |= TO_BIT; + break; + } + default: + break; + } + return true; + } + + process(parser) { + // important! + this.reset(); + + if ( parser.hasError() ) { + return this.FILTER_INVALID; + } + + if ( parser.isException() ) { + this.action = ALLOW_REALM; + } + + if ( parser.isLeftHnAnchored() ) { + this.anchor |= 0b100; + } else if ( parser.isLeftAnchored() ) { + this.anchor |= 0b010; + } + if ( parser.isRightAnchored() ) { + this.anchor |= 0b001; + } + + this.pattern = parser.getNetPattern(); + if ( parser.isHostnamePattern() ) { + this.isPureHostname = true; + } else if ( parser.isGenericPattern() ) { + this.isGeneric = true; + } else if ( parser.isRegexPattern() ) { + this.isRegex = true; + } + + for ( const type of parser.getNodeTypes() ) { + switch ( type ) { + case sfp.NODE_TYPE_NET_OPTION_NAME_1P: + this.processPartyOption(true, parser.isNegatedOption(type)); + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_STRICT1P: + this.strictParty = this.strictParty === -1 ? 0 : 1; + this.optionUnitBits |= STRICT_PARTY_BIT; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_3P: + this.processPartyOption(false, parser.isNegatedOption(type)); + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_STRICT3P: + this.strictParty = this.strictParty === 1 ? 0 : -1; + this.optionUnitBits |= STRICT_PARTY_BIT; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_ALL: + this.processTypeOption(-1); + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_BADFILTER: + this.badFilter = true; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_CNAME: + case sfp.NODE_TYPE_NET_OPTION_NAME_CSS: + case sfp.NODE_TYPE_NET_OPTION_NAME_DOC: + case sfp.NODE_TYPE_NET_OPTION_NAME_FONT: + case sfp.NODE_TYPE_NET_OPTION_NAME_FRAME: + case sfp.NODE_TYPE_NET_OPTION_NAME_GENERICBLOCK: + case sfp.NODE_TYPE_NET_OPTION_NAME_GHIDE: + case sfp.NODE_TYPE_NET_OPTION_NAME_IMAGE: + case sfp.NODE_TYPE_NET_OPTION_NAME_INLINEFONT: + case sfp.NODE_TYPE_NET_OPTION_NAME_INLINESCRIPT: + case sfp.NODE_TYPE_NET_OPTION_NAME_MEDIA: + case sfp.NODE_TYPE_NET_OPTION_NAME_OBJECT: + case sfp.NODE_TYPE_NET_OPTION_NAME_OTHER: + case sfp.NODE_TYPE_NET_OPTION_NAME_PING: + case sfp.NODE_TYPE_NET_OPTION_NAME_POPUNDER: + case sfp.NODE_TYPE_NET_OPTION_NAME_POPUP: + case sfp.NODE_TYPE_NET_OPTION_NAME_SCRIPT: + case sfp.NODE_TYPE_NET_OPTION_NAME_SHIDE: + case sfp.NODE_TYPE_NET_OPTION_NAME_XHR: + case sfp.NODE_TYPE_NET_OPTION_NAME_WEBRTC: + case sfp.NODE_TYPE_NET_OPTION_NAME_WEBSOCKET: + this.processTypeOption(type, parser.isNegatedOption(type)); + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_CSP: + case sfp.NODE_TYPE_NET_OPTION_NAME_DENYALLOW: + case sfp.NODE_TYPE_NET_OPTION_NAME_FROM: + case sfp.NODE_TYPE_NET_OPTION_NAME_HEADER: + case sfp.NODE_TYPE_NET_OPTION_NAME_IPADDRESS: + case sfp.NODE_TYPE_NET_OPTION_NAME_METHOD: + case sfp.NODE_TYPE_NET_OPTION_NAME_PERMISSIONS: + case sfp.NODE_TYPE_NET_OPTION_NAME_REASON: + case sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECT: + case sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECTRULE: + case sfp.NODE_TYPE_NET_OPTION_NAME_REMOVEPARAM: + case sfp.NODE_TYPE_NET_OPTION_NAME_REPLACE: + case sfp.NODE_TYPE_NET_OPTION_NAME_TO: + case sfp.NODE_TYPE_NET_OPTION_NAME_URLSKIP: + case sfp.NODE_TYPE_NET_OPTION_NAME_URLTRANSFORM: + if ( this.processOptionWithValue(parser, type) === false ) { + return this.FILTER_INVALID; + } + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_EHIDE: { + const not = parser.isNegatedOption(type); + this.processTypeOption(sfp.NODE_TYPE_NET_OPTION_NAME_SHIDE, not); + this.processTypeOption(sfp.NODE_TYPE_NET_OPTION_NAME_GHIDE, not); + break; + } + case sfp.NODE_TYPE_NET_OPTION_NAME_EMPTY: { + const id = this.action === ALLOW_REALM + ? sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECTRULE + : sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECT; + if ( this.processModifierOption(id, 'empty') === false ) { + return this.FILTER_INVALID; + } + this.optionUnitBits |= MODIFY_BIT; + break; + } + case sfp.NODE_TYPE_NET_OPTION_NAME_IMPORTANT: + this.optionUnitBits |= IMPORTANT_BIT; + this.action = BLOCKIMPORTANT_REALM; + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_MATCHCASE: + this.optionValues.set('match-case', true); + break; + case sfp.NODE_TYPE_NET_OPTION_NAME_MP4: { + const id = this.action === ALLOW_REALM + ? sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECTRULE + : sfp.NODE_TYPE_NET_OPTION_NAME_REDIRECT; + if ( this.processModifierOption(id, 'noopmp4-1s') === false ) { + return this.FILTER_INVALID; + } + this.processTypeOption(sfp.NODE_TYPE_NET_OPTION_NAME_MEDIA, false); + this.optionUnitBits |= MODIFY_BIT; + break; + } + default: + break; + } + } + + if ( this.party === ALLPARTIES_REALM ) { + this.party = ANYPARTY_REALM; + } + + // Negated network types? Toggle on all network type bits. + // Negated non-network types can only toggle themselves. + // + // https://github.com/gorhill/uBlock/issues/2385 + // Toggle on all network types if: + // - at least one network type is negated; or + // - no network type is present -- i.e. all network types are + // implicitly toggled on + if ( this.notTypeBits !== 0 ) { + if ( (this.typeBits && allNetworkTypesBits) === allNetworkTypesBits ) { + this.typeBits &= ~this.notTypeBits | allNetworkTypesBits; + } else { + this.typeBits &= ~this.notTypeBits; + } + this.optionUnitBits |= NOT_TYPE_BIT; + } + + // CSP/permissions options implicitly apply only to + // document/subdocument. + if ( + this.modifyType === MODIFIER_TYPE_CSP || + this.modifyType === MODIFIER_TYPE_PERMISSIONS + ) { + if ( this.typeBits === 0 ) { + this.processTypeOption(sfp.NODE_TYPE_NET_OPTION_NAME_DOC, false); + this.processTypeOption(sfp.NODE_TYPE_NET_OPTION_NAME_FRAME, false); + } + } + + // https://github.com/gorhill/uBlock/issues/2283 + // Abort if type is only for unsupported types, otherwise + // toggle off `unsupported` bit. + if ( this.typeBits & unsupportedTypeBit ) { + this.typeBits &= ~unsupportedTypeBit; + if ( this.typeBits === 0 ) { return this.FILTER_UNSUPPORTED; } + } + + // Plain hostname? (from HOSTS file) + if ( this.isPureHostname && parser.hasOptions() === false ) { + this.anchor |= 0b100; + return this.FILTER_OK; + } + + // regex? + if ( this.isRegex ) { + return this.FILTER_OK; + } + + if ( this.pattern.length > 1024 ) { + return this.FILTER_UNSUPPORTED; + } + + return this.FILTER_OK; + } + + // Given a string, find a good token. Tokens which are too generic, + // i.e. very common with a high probability of ending up as a miss, + // are not good. Avoid if possible. This has a significant positive + // impact on performance. + // + // For pattern-less removeparam filters, try to derive a pattern from + // the removeparam value. + + makeToken() { + if ( this.pattern === '*' ) { + if ( this.modifyType !== MODIFIER_TYPE_REMOVEPARAM ) { return; } + return this.extractTokenFromQuerypruneValue(); + } + if ( this.isRegex ) { + return this.extractTokenFromRegex(this.pattern); + } + this.extractTokenFromPattern(this.pattern); + } + + // Note: a one-char token is better than a documented bad token. + extractTokenFromPattern(pattern) { + this.reTokens.lastIndex = 0; + let bestMatch = null; + let bestBadness = 0x7FFFFFFF; + for (;;) { + const match = this.reTokens.exec(pattern); + if ( match === null ) { break; } + const token = match[0]; + const badness = token.length > 1 ? this.badTokens.get(token) || 0 : 1; + if ( badness >= bestBadness ) { continue; } + if ( match.index > 0 ) { + const c = pattern.charCodeAt(match.index - 1); + if ( c === 0x2A /* '*' */ ) { continue; } + } + if ( token.length < MAX_TOKEN_LENGTH ) { + const lastIndex = this.reTokens.lastIndex; + if ( lastIndex < pattern.length ) { + const c = pattern.charCodeAt(lastIndex); + if ( c === 0x2A /* '*' */ ) { continue; } + } + } + bestMatch = match; + if ( badness === 0 ) { break; } + bestBadness = badness; + } + if ( bestMatch !== null ) { + this.token = bestMatch[0]; + this.tokenHash = urlTokenizer.tokenHashFromString(this.token); + this.tokenBeg = bestMatch.index; + } + } + + // https://github.com/gorhill/uBlock/issues/2781 + // For efficiency purpose, try to extract a token from a regex-based + // filter. + // https://github.com/uBlockOrigin/uBlock-issues/issues/1145#issuecomment-657036902 + // Mind `\b` directives: `/\bads\b/` should result in token being `ads`, + // not `bads`. + extractTokenFromRegex(pattern) { + pattern = tokenizableStrFromRegex(pattern); + this.reTokens.lastIndex = 0; + let bestToken; + let bestBadness = 0x7FFFFFFF; + for (;;) { + const matches = this.reTokens.exec(pattern); + if ( matches === null ) { break; } + const { 0: token, index } = matches; + if ( index === 0 || pattern.charAt(index - 1) === '\x01' ) { + continue; + } + const { lastIndex } = this.reTokens; + if ( + token.length < MAX_TOKEN_LENGTH && ( + lastIndex === pattern.length || + pattern.charAt(lastIndex) === '\x01' + ) + ) { + continue; + } + const badness = token.length > 1 + ? this.badTokens.get(token) || 0 + : 1; + if ( badness < bestBadness ) { + bestToken = token; + if ( badness === 0 ) { break; } + bestBadness = badness; + } + } + if ( bestToken !== undefined ) { + this.token = bestToken.toLowerCase(); + this.tokenHash = urlTokenizer.tokenHashFromString(this.token); + } + } + + // https://github.com/uBlockOrigin/uAssets/discussions/14683#discussioncomment-3559284 + // If the removeparam value is a regex, unescape escaped commas + extractTokenFromQuerypruneValue() { + const pattern = this.modifyValue; + if ( pattern === '*' || pattern.charCodeAt(0) === 0x7E /* '~' */ ) { + return; + } + const match = /^\/(.+)\/i?$/.exec(pattern); + if ( match !== null ) { + return this.extractTokenFromRegex( + match[1].replace(/(\{\d*)\\,/, '$1,') + ); + } + if ( pattern.startsWith('|') ) { + return this.extractTokenFromRegex('\\b' + pattern.slice(1)); + } + this.extractTokenFromPattern(pattern.toLowerCase()); + } + + hasNoOptionUnits() { + return this.optionUnitBits === 0; + } + + isJustOrigin() { + if ( this.optionUnitBits !== FROM_BIT ) { return false; } + if ( this.isRegex ) { return false; } + if ( /[/~]/.test(this.optionValues.get('from')) ) { return false; } + if ( this.pattern === '*' ) { return true; } + if ( this.anchor !== 0b010 ) { return false; } + if ( /^(?:http[s*]?:(?:\/\/)?)$/.test(this.pattern) ) { return true; } + return false; + } + + domainIsEntity(s) { + const l = s.length; + return l > 2 && + s.charCodeAt(l-1) === 0x2A /* '*' */ && + s.charCodeAt(l-2) === 0x2E /* '.' */; + } + + compile(parser, writer) { + const r = this.process(parser); + + // Ignore non-static network filters + if ( r === this.FILTER_INVALID ) { return false; } + + // Ignore filters with unsupported options + if ( r === this.FILTER_UNSUPPORTED ) { + const who = writer.properties.get('name') || '?'; + this.error = `Invalid network filter in ${who}: ${parser.raw}`; + return false; + } + + writer.select( + this.badFilter + ? 'NETWORK_FILTERS:BAD' + : 'NETWORK_FILTERS:GOOD' + ); + + // Reminder: + // `redirect=` is a combination of a `redirect-rule` filter and a + // block filter. + if ( this.modifyType === MODIFIER_TYPE_REDIRECT ) { + this.modifyType = MODIFIER_TYPE_REDIRECTRULE; + // Do not generate block rule when compiling to DNR ruleset + if ( parser.options.toDNR !== true ) { + const parsedBlock = this.clone(); + parsedBlock.modifyType = undefined; + parsedBlock.optionUnitBits &= ~MODIFY_BIT; + parsedBlock.compileToFilter(writer); + } + } + + this.compileToFilter(writer); + + return true; + } + + compileToFilter(writer) { + // Pure hostnames, use more efficient dictionary lookup + if ( this.isPureHostname && this.hasNoOptionUnits() ) { + this.tokenHash = DOT_TOKEN_HASH; + this.compileToAtomicFilter(this.pattern, writer); + return; + } + + this.makeToken(); + + // Special pattern/option cases: + // - `*$domain=...` + // - `|http://$domain=...` + // - `|https://$domain=...` + // The semantic of "just-origin" filters is that contrary to normal + // filters, the original filter is split into as many filters as there + // are entries in the `domain=` option. + if ( this.isJustOrigin() ) { + if ( this.pattern === '*' || this.pattern.startsWith('http*') ) { + this.tokenHash = ANY_TOKEN_HASH; + } else if /* 'https:' */ ( this.pattern.startsWith('https') ) { + this.tokenHash = ANY_HTTPS_TOKEN_HASH; + } else /* 'http:' */ { + this.tokenHash = ANY_HTTP_TOKEN_HASH; + } + for ( const hn of this.optionValues.get('fromList') ) { + this.compileToAtomicFilter(hn, writer); + } + return; + } + + const units = []; + + // Pattern + const patternClass = this.compilePattern(units); + + // Anchor: must never appear before pattern unit + if ( (this.anchor & 0b100) !== 0 ) { + if ( this.isPureHostname ) { + units.push(FilterAnchorHn.compile()); + } else { + units.push(FilterAnchorHnLeft.compile()); + } + } else if ( (this.anchor & 0b010) !== 0 ) { + units.push(FilterAnchorLeft.compile()); + } + if ( (this.anchor & 0b001) !== 0 ) { + units.push(FilterAnchorRight.compile()); + } + + // Method(s) + if ( this.methodBits !== 0 || this.notMethodBits !== 0 ) { + units.push(FilterMethod.compile(this)); + } + + // Not types + if ( this.notTypeBits !== 0 ) { + units.push(FilterNotType.compile(this)); + } + + // Strict partiness + if ( this.strictParty !== 0 ) { + units.push(FilterStrictParty.compile(this)); + } + + // Origin + if ( (this.optionUnitBits & FROM_BIT) !== 0 ) { + compileFromDomainOpt( + this.optionValues.get('fromList'), + units.length !== 0 && patternClass.isSlow === true, + units + ); + } + + // Destination + if ( (this.optionUnitBits & TO_BIT) !== 0 ) { + compileToDomainOpt( + this.optionValues.get('toList'), + units.length !== 0 && patternClass.isSlow === true, + units + ); + } + + // Deny-allow + if ( (this.optionUnitBits & DENYALLOW_BIT) !== 0 ) { + units.push(FilterDenyAllow.compile(this)); + } + + // IP address + if ( (this.optionUnitBits & IPADDRESS_BIT) !== 0 ) { + units.push(FilterIPAddress.compile(this)); + } + + // Header + if ( (this.optionUnitBits & HEADER_BIT) !== 0 ) { + units.push(FilterOnHeaders.compile(this)); + this.action |= HEADERS_REALM; + } + + // Message + if ( (this.optionUnitBits & MESSAGE_BIT) !== 0 ) { + units.push(FilterMessage.compile(this)); + } + + // Important + // + // IMPORTANT: must always appear at the end of the sequence, so as to + // ensure $isBlockImportant is set only for matching filters. + if ( (this.optionUnitBits & IMPORTANT_BIT) !== 0 ) { + units.push(FilterImportant.compile()); + } + + // Modifier + // + // IMPORTANT: the modifier unit MUST always appear first in a sequence + if ( this.modifyType !== undefined ) { + units.unshift(FilterModifier.compile(this)); + this.action = (this.action & ~BLOCKALLOW_REALM) | + modifierBitsFromType.get(this.modifyType); + } + + const fdata = units.length === 1 + ? units[0] + : FilterCompositeAll.compile(units); + + this.compileToAtomicFilter(fdata, writer); + + if ( (this.optionUnitBits & IPADDRESS_BIT) !== 0 ) { + if ( (this.action & HEADERS_REALM) !== 0 ) { return; } + this.action |= HEADERS_REALM; + this.compileToAtomicFilter(fdata, writer); + } + } + + compilePattern(units) { + if ( this.isRegex ) { + units.push(FilterRegex.compile(this)); + return FilterRegex; + } + if ( this.pattern === '*' ) { + units.push(FilterPatternAny.compile()); + return FilterPatternAny; + } + if ( this.tokenHash === NO_TOKEN_HASH ) { + units.push(FilterPatternGeneric.compile(this)); + return FilterPatternGeneric; + } + if ( this.pattern.includes('*') === false ) { + const caretPos = this.pattern.indexOf('^'); + if ( caretPos === -1 ) { + units.push(FilterPatternPlain.compile(this)); + return FilterPatternPlain; + } + if ( caretPos === (this.pattern.length - 1) ) { + this.pattern = this.pattern.slice(0, -1); + units.push(FilterPatternPlain.compile(this)); + units.push(FilterTrailingSeparator.compile()); + return FilterPatternPlain; + } + } + units.push(FilterPatternGeneric.compile(this)); + return FilterPatternGeneric; + } + + compileToAtomicFilter(fdata, writer) { + const catBits = this.action | this.party; + let { typeBits } = this; + + // Typeless + if ( typeBits === 0 ) { + writer.push([ catBits, this.tokenHash, fdata ]); + return; + } + // If all network types are set, create a typeless filter. Excluded + // network types are tested at match time, se we act as if they are + // set. + if ( (typeBits & allNetworkTypesBits) === allNetworkTypesBits ) { + writer.push([ catBits, this.tokenHash, fdata ]); + typeBits &= ~allNetworkTypesBits; + if ( typeBits === 0 ) { return; } + } + // One filter per specific types + let bitOffset = 1; + do { + if ( typeBits & 1 ) { + writer.push([ + catBits | (bitOffset << TYPE_REALM_OFFSET), + this.tokenHash, + fdata + ]); + } + bitOffset += 1; + typeBits >>>= 1; + } while ( typeBits !== 0 ); + } +} + +// These are to quickly test whether a filter is composite +const FROM_BIT = 0b00000000001; +const TO_BIT = 0b00000000010; +const DENYALLOW_BIT = 0b00000000100; +const HEADER_BIT = 0b00000001000; +const STRICT_PARTY_BIT = 0b00000010000; +const MODIFY_BIT = 0b00000100000; +const NOT_TYPE_BIT = 0b00001000000; +const IMPORTANT_BIT = 0b00010000000; +const METHOD_BIT = 0b00100000000; +const IPADDRESS_BIT = 0b01000000000; +const MESSAGE_BIT = 0b10000000000 + +FilterCompiler.prototype.FILTER_OK = 0; +FilterCompiler.prototype.FILTER_INVALID = 1; +FilterCompiler.prototype.FILTER_UNSUPPORTED = 2; + +/******************************************************************************/ +/******************************************************************************/ + +const StaticNetFilteringEngine = function() { + this.compilerVersion = '10'; + this.selfieVersion = '10'; + + this.MAX_TOKEN_LENGTH = MAX_TOKEN_LENGTH; + this.optimizeTaskId = undefined; + // As long as CategoryCount is reasonably low, we will use an array to + // store buckets using category bits as index. If ever CategoryCount + // becomes too large, we can just go back to using a Map. + this.bitsToBucket = new Map(); + this.goodFilters = new Set(); + this.badFilters = new Set(); + this.unitsToOptimize = []; + this.reset(); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.prime = function() { + origHNTrieContainer.reset( + keyvalStore.getItem('SNFE.origHNTrieContainer.trieDetails') + ); + destHNTrieContainer.reset( + keyvalStore.getItem('SNFE.destHNTrieContainer.trieDetails') + ); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.reset = function() { + this.processedFilterCount = 0; + this.acceptedCount = 0; + this.discardedCount = 0; + this.goodFilters.clear(); + this.badFilters.clear(); + this.unitsToOptimize.length = 0; + this.bitsToBucket.clear(); + + urlTokenizer.resetKnownTokens(); + + filterDataReset(); + filterRefsReset(); + origHNTrieContainer.reset(); + destHNTrieContainer.reset(); + bidiTrie.reset(); + filterArgsToUnit.clear(); + + // Cancel potentially pending optimization run. + if ( this.optimizeTaskId !== undefined ) { + dropTask(this.optimizeTaskId); + this.optimizeTaskId = undefined; + } + + this.notReady = false; + + // Runtime registers + this.$catBits = 0; + this.$tokenHash = 0; + this.$filterUnit = 0; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.freeze = function() { + const unserialize = CompiledListReader.unserialize; + + for ( const line of this.goodFilters ) { + if ( this.badFilters.has(line) ) { + this.discardedCount += 1; + continue; + } + + const args = unserialize(line); + + const bits = args[0]; + const bucket = this.bitsToBucket.get(bits) || (new Map()); + if ( bucket.size === 0 ) { + this.bitsToBucket.set(bits, bucket); + } + + const tokenHash = args[1]; + const fdata = args[2]; + + let iunit = bucket.get(tokenHash) || 0; + + if ( tokenHash === DOT_TOKEN_HASH ) { + if ( iunit === 0 ) { + iunit = FilterHostnameDict.create(); + bucket.set(DOT_TOKEN_HASH, iunit); + this.unitsToOptimize.push({ bits, tokenHash }); + } + FilterHostnameDict.add(iunit, fdata); + continue; + } + + if ( tokenHash === ANY_TOKEN_HASH ) { + if ( iunit === 0 ) { + iunit = FilterJustOrigin.create(); + bucket.set(ANY_TOKEN_HASH, iunit); + } + FilterJustOrigin.add(iunit, fdata); + continue; + } + + if ( tokenHash === ANY_HTTPS_TOKEN_HASH ) { + if ( iunit === 0 ) { + iunit = FilterHTTPSJustOrigin.create(); + bucket.set(ANY_HTTPS_TOKEN_HASH, iunit); + } + FilterHTTPSJustOrigin.add(iunit, fdata); + continue; + } + + if ( tokenHash === ANY_HTTP_TOKEN_HASH ) { + if ( iunit === 0 ) { + iunit = FilterHTTPJustOrigin.create(); + bucket.set(ANY_HTTP_TOKEN_HASH, iunit); + } + FilterHTTPJustOrigin.add(iunit, fdata); + continue; + } + + urlTokenizer.addKnownToken(tokenHash); + + this.addFilterUnit(bits, tokenHash, filterFromCompiled(fdata)); + + // Add block-important filters to the block realm, so as to avoid + // to unconditionally match against the block-important realm for + // every network request. Block-important filters are quite rare so + // the block-important realm should be checked when and only when + // there is a matched exception filter, which important filters are + // meant to override. + if ( (bits & BLOCKALLOW_REALM) === BLOCKIMPORTANT_REALM ) { + this.addFilterUnit( + bits & ~IMPORTANT_REALM, + tokenHash, + filterFromCompiled(fdata) + ); + } + } + + this.badFilters.clear(); + this.goodFilters.clear(); + filterArgsToUnit.clear(); + + this.notReady = false; + + // Optimizing is not critical for the static network filtering engine to + // work properly, so defer this until later to allow for reduced delay to + // readiness when no valid selfie is available. + if ( this.optimizeTaskId !== undefined ) { return; } + + this.optimizeTaskId = queueTask(( ) => { + this.optimizeTaskId = undefined; + this.optimize(30); + }, 2000); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.dnrFromCompiled = function(op, context, ...args) { + if ( op === 'begin' ) { + Object.assign(context, { + good: new Set(), + bad: new Set(context.bad), + invalid: new Set(), + filterCount: 0, + acceptedFilterCount: 0, + rejectedFilterCount: 0, + }); + return; + } + + if ( op === 'add' ) { + const reader = args[0]; + reader.select('NETWORK_FILTERS:GOOD'); + while ( reader.next() ) { + context.filterCount += 1; + if ( context.good.has(reader.line) === false ) { + context.good.add(reader.line); + } + } + reader.select('NETWORK_FILTERS:BAD'); + while ( reader.next() ) { + context.bad.add(reader.line); + } + return; + } + + if ( op !== 'end' ) { return; } + + const { good, bad } = context; + const unserialize = CompiledListReader.unserialize; + const buckets = new Map(); + + for ( const line of good ) { + if ( bad.has(line) ) { + context.rejectedFilterCount += 1; + continue; + } + context.acceptedFilterCount += 1; + + const args = unserialize(line); + const bits = args[0]; + const tokenHash = args[1]; + const fdata = args[2]; + + if ( buckets.has(bits) === false ) { + buckets.set(bits, new Map()); + } + const bucket = buckets.get(bits); + + switch ( tokenHash ) { + case DOT_TOKEN_HASH: { + if ( bucket.has(DOT_TOKEN_HASH) === false ) { + bucket.set(DOT_TOKEN_HASH, [{ + condition: { + requestDomains: [] + } + }]); + } + const rule = bucket.get(DOT_TOKEN_HASH)[0]; + rule.condition.requestDomains.push(fdata); + break; + } + case ANY_TOKEN_HASH: { + if ( bucket.has(ANY_TOKEN_HASH) === false ) { + bucket.set(ANY_TOKEN_HASH, [{ + condition: { + initiatorDomains: [] + } + }]); + } + const rule = bucket.get(ANY_TOKEN_HASH)[0]; + rule.condition.initiatorDomains.push(fdata); + break; + } + case ANY_HTTPS_TOKEN_HASH: { + if ( bucket.has(ANY_HTTPS_TOKEN_HASH) === false ) { + bucket.set(ANY_HTTPS_TOKEN_HASH, [{ + condition: { + urlFilter: '|https://', + initiatorDomains: [] + } + }]); + } + const rule = bucket.get(ANY_HTTPS_TOKEN_HASH)[0]; + rule.condition.initiatorDomains.push(fdata); + break; + } + case ANY_HTTP_TOKEN_HASH: { + if ( bucket.has(ANY_HTTP_TOKEN_HASH) === false ) { + bucket.set(ANY_HTTP_TOKEN_HASH, [{ + condition: { + urlFilter: '|http://', + initiatorDomains: [] + } + }]); + } + const rule = bucket.get(ANY_HTTP_TOKEN_HASH)[0]; + rule.condition.initiatorDomains.push(fdata); + break; + } + default: { + if ( bucket.has(EMPTY_TOKEN_HASH) === false ) { + bucket.set(EMPTY_TOKEN_HASH, []); + } + const rule = {}; + dnrRuleFromCompiled(fdata, rule); + bucket.get(EMPTY_TOKEN_HASH).push(rule); + break; + } + } + } + + // Priority: + // Removeparam: 1-4 + // Block: 10 (default priority) + // Redirect: 11-19 + // Excepted redirect: 21-29 + // Allow: 30 + // Block important: 40 + // Redirect important: 41-49 + + const realms = new Map([ + [ BLOCK_REALM, { type: 'block', priority: 10 } ], + [ ALLOW_REALM, { type: 'allow', priority: 30 } ], + [ BLOCK_REALM | IMPORTANT_REALM, { type: 'block', priority: 10 } ], + [ REDIRECT_REALM, { type: 'redirect', priority: 11 } ], + [ REMOVEPARAM_REALM, { type: 'removeparam', priority: 0 } ], + [ CSP_REALM, { type: 'csp', priority: 0 } ], + [ PERMISSIONS_REALM, { type: 'permissions', priority: 0 } ], + [ URLTRANSFORM_REALM, { type: 'uritransform', priority: 0 } ], + [ HEADERS_REALM, { type: 'block', priority: 10 } ], + [ HEADERS_REALM | ALLOW_REALM, { type: 'allow', priority: 30 } ], + [ HEADERS_REALM | IMPORTANT_REALM, { type: 'allow', priority: 10 } ], + [ URLSKIP_REALM, { type: 'urlskip', priority: 0 } ], + ]); + const partyness = new Map([ + [ ANYPARTY_REALM, '' ], + [ FIRSTPARTY_REALM, 'firstParty' ], + [ THIRDPARTY_REALM, 'thirdParty' ], + ]); + const types = new Set([ + 'no_type', + 'stylesheet', + 'image', + 'object', + 'script', + 'xmlhttprequest', + 'sub_frame', + 'main_frame', + 'font', + 'media', + 'websocket', + 'ping', + 'other', + ]); + const ruleset = []; + const seen = new Set(); + for ( const [ realmBits, realmDetails ] of realms ) { + for ( const [ partyBits, partyName ] of partyness ) { + for ( const typeName in typeNameToTypeValue ) { + if ( types.has(typeName) === false ) { continue; } + const typeBits = typeNameToTypeValue[typeName]; + const bits = realmBits | partyBits | typeBits; + const bucket = buckets.get(bits); + if ( bucket === undefined ) { continue; } + for ( const rules of bucket.values() ) { + for ( const rule of rules ) { + rule.action = rule.action || {}; + rule.action.type = realmDetails.type; + if ( realmDetails.priority !== 0 ) { + rule.priority = (rule.priority || 0) + realmDetails.priority; + } + if ( partyName !== '' ) { + rule.condition = rule.condition || {}; + rule.condition.domainType = partyName; + } + if ( typeName !== 'no_type' ) { + rule.condition = rule.condition || {}; + rule.condition.resourceTypes = [ typeName ]; + } + const hash = JSON.stringify(rule); + if ( seen.has(hash) ) { continue; } + seen.add(hash); + ruleset.push(rule); + } + } + } + } + } + seen.clear(); + + // Adjust `important` priority + for ( const rule of ruleset ) { + if ( rule.__important !== true ) { continue; } + if ( rule.priority === undefined ) { continue; } + rule.priority += 30; + } + + // Collect generichide filters + const generichideExclusions = []; + const generichideInclusions = []; + { + const bucket = buckets.get(ALLOW_REALM | typeNameToTypeValue['generichide']); + if ( bucket ) { + for ( const rules of bucket.values() ) { + for ( const rule of rules ) { + if ( rule.condition === undefined ) { continue; } + if ( rule.condition.initiatorDomains ) { + generichideExclusions.push(...rule.condition.initiatorDomains); + } else if ( rule.condition.requestDomains ) { + generichideExclusions.push(...rule.condition.requestDomains); + } + if ( rule.condition.excludedInitiatorDomains ) { + generichideInclusions.push(...rule.condition.excludedInitiatorDomains); + } else if ( rule.condition.excludedRequestDomains ) { + generichideInclusions.push(...rule.condition.excludedRequestDomains); + } + } + } + } + } + { + const bucket = buckets.get(BLOCKIMPORTANT_REALM | typeNameToTypeValue['generichide']); + if ( bucket ) { + for ( const rules of bucket.values() ) { + for ( const rule of rules ) { + if ( rule.condition === undefined ) { continue; } + if ( rule.condition.initiatorDomains ) { + generichideInclusions.push(...rule.condition.initiatorDomains); + } else if ( rule.condition.requestDomains ) { + generichideInclusions.push(...rule.condition.requestDomains); + } + } + } + } + } + + // Detect and attempt salvage of rules with entity-based hostnames and/or + // regex-based domains. + const isUnsupportedDomain = hn => hn.endsWith('.*') || hn.startsWith('/'); + for ( const rule of ruleset ) { + if ( rule.condition === undefined ) { continue; } + for ( const prop of [ 'Initiator', 'Request' ] ) { + const hitProp = `${prop.toLowerCase()}Domains`; + if ( Array.isArray(rule.condition[hitProp]) ) { + if ( rule.condition[hitProp].some(hn => isUnsupportedDomain(hn)) ) { + const domains = rule.condition[hitProp].filter( + hn => isUnsupportedDomain(hn) === false + ); + if ( domains.length === 0 ) { + dnrAddRuleError(rule, `Can't salvage rule with unsupported domain= option: ${rule.condition[hitProp].join('|')}`); + } else { + dnrAddRuleWarning(rule, `Salvaged rule by ignoring ${rule.condition[hitProp].length - domains.length} unsupported domain= option: ${rule.condition[hitProp].join('|')}`); + rule.condition[hitProp] = domains; + } + } + } + const missProp = `excluded${prop}Domains`; + if ( Array.isArray(rule.condition[missProp]) ) { + if ( rule.condition[missProp].some(hn => isUnsupportedDomain(hn)) ) { + const domains = rule.condition[missProp].filter( + hn => isUnsupportedDomain(hn) === false + ); + rule.condition[missProp] = + domains.length !== 0 + ? domains + : undefined; + } + } + } + } + + // Patch modifier filters + for ( const rule of ruleset ) { + if ( rule.__modifierType === undefined ) { continue; } + let patchDomainOption = false; + switch ( rule.__modifierType ) { + case 'csp': + rule.action.type = 'modifyHeaders'; + rule.action.responseHeaders = [{ + header: 'content-security-policy', + operation: 'append', + value: rule.__modifierValue, + }]; + if ( rule.__modifierAction === ALLOW_REALM ) { + dnrAddRuleError(rule, `Unsupported csp exception: ${rule.__modifierValue}`); + } + break; + case 'permissions': + rule.action.type = 'modifyHeaders'; + rule.action.responseHeaders = [{ + header: 'permissions-policy', + operation: 'append', + value: rule.__modifierValue.split('|').join(', '), + }]; + if ( rule.__modifierAction === ALLOW_REALM ) { + dnrAddRuleError(rule, `Unsupported permissions exception: ${rule.__modifierValue}`); + } + patchDomainOption = true; + break; + case 'redirect-rule': { + let token = rule.__modifierValue; + if ( token !== '' ) { + const match = /:(\d+)$/.exec(token); + if ( match !== null ) { + rule.priority += Math.min(parseInt(match[1], 10), 8); + token = token.slice(0, match.index); + } + } + const resource = context.extensionPaths.get(token); + if ( rule.__modifierValue !== '' && resource === undefined ) { + dnrAddRuleError(rule, `Unpatchable redirect filter: ${rule.__modifierValue}`); + } + if ( rule.__modifierAction !== ALLOW_REALM ) { + const extensionPath = resource || token; + rule.action.type = 'redirect'; + rule.action.redirect = { extensionPath }; + } else { + rule.action.type = 'block'; + rule.priority += 10; + } + break; + } + case 'removeparam': { + rule.action.type = 'redirect'; + if ( rule.__modifierValue === '|' ) { + rule.__modifierValue = ''; + } + if ( rule.__modifierValue !== '' ) { + rule.action.redirect = { + transform: { + queryTransform: { + removeParams: [ rule.__modifierValue ] + } + } + }; + if ( /^~?\/.+\/$/.test(rule.__modifierValue) ) { + dnrAddRuleError(rule, `Unsupported regex-based removeParam: ${rule.__modifierValue}`); + } + } else { + rule.action.redirect = { + transform: { + query: '' + } + }; + } + if ( rule.condition === undefined ) { + rule.condition = { + }; + } + if ( rule.condition.resourceTypes === undefined ) { + if ( rule.condition.excludedResourceTypes === undefined ) { + rule.condition.resourceTypes = [ + 'main_frame', + 'sub_frame', + 'xmlhttprequest', + ]; + } + } + // https://github.com/uBlockOrigin/uBOL-home/issues/140 + // Mitigate until DNR API flaw is addressed by browser vendors + let priority = rule.priority || 1; + if ( rule.condition.urlFilter !== undefined ) { priority += 1; } + if ( rule.condition.regexFilter !== undefined ) { priority += 1; } + if ( rule.condition.initiatorDomains !== undefined ) { priority += 1; } + if ( rule.condition.requestDomains !== undefined ) { priority += 1; } + if ( priority !== 1 ) { + rule.priority = priority; + } + if ( rule.__modifierAction === ALLOW_REALM ) { + dnrAddRuleError(rule, `Unsupported removeparam exception: ${rule.__modifierValue}`); + } + break; + } + case 'uritransform': { + dnrAddRuleError(rule, `Incompatible with DNR: uritransform=${rule.__modifierValue}`); + break; + } + case 'urlskip': { + let urlFilter = rule.condition?.urlFilter; + if ( urlFilter === undefined ) { break; } + let anchor = 0b000; + if ( urlFilter.startsWith('||') ) { + anchor |= 0b100; + urlFilter = urlFilter.slice(2); + } else if ( urlFilter.startsWith('|') ) { + anchor |= 0b10; + urlFilter = urlFilter.slice(1); + } + if ( urlFilter.endsWith('|') ) { + anchor |= 0b001; + urlFilter = urlFilter.slice(0, -1); + } + rule.condition.urlFilter = undefined; + rule.condition.regexFilter = restrFromGenericPattern(urlFilter, anchor); + break; + } + default: + dnrAddRuleError(rule, `Unsupported modifier ${rule.__modifierType}`); + break; + } + + // Some modifiers only work on document resources + // Related issue: https://github.com/uBlockOrigin/uBOL-home/issues/156 + if ( patchDomainOption ) { + const domains = rule.condition.initiatorDomains; + if ( Array.isArray(domains) && domains.length !== 0 ) { + rule.condition.requestDomains ||= []; + rule.condition.requestDomains.push(...domains); + } + const notDomains = rule.condition.excludedInitiatorDomains; + if ( Array.isArray(notDomains) && notDomains.length !== 0 ) { + rule.condition.excludedRequestDomains ||= []; + rule.condition.excludedRequestDomains.push(...notDomains); + } + } + } + + return { + ruleset, + filterCount: context.filterCount, + acceptedFilterCount: context.acceptedFilterCount, + rejectedFilterCount: context.rejectedFilterCount, + generichideExclusions: Array.from(new Set(generichideExclusions)), + generichideInclusions: Array.from(new Set(generichideInclusions)), + }; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.addFilterUnit = function( + bits, + tokenHash, + inewunit +) { + const bucket = this.bitsToBucket.get(bits) || (new Map()); + if ( bucket.size === 0 ) { + this.bitsToBucket.set(bits, bucket); + } + const istoredunit = bucket.get(tokenHash) || 0; + if ( istoredunit === 0 ) { + bucket.set(tokenHash, inewunit); + return; + } + if ( filterData[istoredunit+0] === FilterBucket.fid ) { + FilterBucket.unshift(istoredunit, inewunit); + return; + } + const ibucketunit = FilterBucket.create(); + FilterBucket.unshift(ibucketunit, istoredunit); + FilterBucket.unshift(ibucketunit, inewunit); + bucket.set(tokenHash, ibucketunit); + this.unitsToOptimize.push({ bits, tokenHash }); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.optimize = function(throttle = 0) { + if ( this.optimizeTaskId !== undefined ) { + dropTask(this.optimizeTaskId); + this.optimizeTaskId = undefined; + } + + const later = throttle => { + this.optimizeTaskId = queueTask(( ) => { + this.optimizeTaskId = undefined; + this.optimize(throttle); + }, 1000); + }; + + const t0 = Date.now(); + while ( this.unitsToOptimize.length !== 0 ) { + const { bits, tokenHash } = this.unitsToOptimize.pop(); + const bucket = this.bitsToBucket.get(bits); + const iunit = bucket.get(tokenHash); + const fc = filterGetClass(iunit); + switch ( fc ) { + case FilterHostnameDict: + FilterHostnameDict.optimize(iunit); + break; + case FilterBucket: { + const optimizeBits = + (tokenHash === NO_TOKEN_HASH) || (bits & MODIFY_REALMS) !== 0 + ? 0b10 + : 0b01; + const inewunit = FilterBucket.optimize(iunit, optimizeBits); + if ( inewunit !== 0 ) { + bucket.set(tokenHash, inewunit); + } + break; + } + default: + break; + } + if ( throttle > 0 && (Date.now() - t0) > 40 ) { + return later(throttle - 1); + } + } + + filterArgsToUnit.clear(); + + // Here we do not optimize origHNTrieContainer because many origin-related + // tries are instantiated on demand. + keyvalStore.setItem( + 'SNFE.destHNTrieContainer.trieDetails', + destHNTrieContainer.optimize() + ); + filterDataShrink(); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.toSelfie = function() { + this.optimize(0); + bidiTrie.optimize(); + keyvalStore.setItem('SNFE.origHNTrieContainer.trieDetails', + origHNTrieContainer.optimize() + ); + return { + version: this.selfieVersion, + processedFilterCount: this.processedFilterCount, + acceptedCount: this.acceptedCount, + discardedCount: this.discardedCount, + bitsToBucket: this.bitsToBucket, + urlTokenizer: urlTokenizer.toSelfie(), + destHNTrieContainer: destHNTrieContainer.toSelfie(), + origHNTrieContainer: origHNTrieContainer.toSelfie(), + bidiTrie: bidiTrie.toSelfie(), + filterData: filterDataToSelfie(), + filterRefs: filterRefsToSelfie(), + }; +}; + +StaticNetFilteringEngine.prototype.serialize = function() { + return this.toSelfie(); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.fromSelfie = function(selfie) { + if ( typeof selfie !== 'object' || selfie === null ) { return; } + + this.reset(); + + this.notReady = true; + + const results = [ + destHNTrieContainer.fromSelfie(selfie.destHNTrieContainer), + origHNTrieContainer.fromSelfie(selfie.origHNTrieContainer), + bidiTrie.fromSelfie(selfie.bidiTrie), + filterDataFromSelfie(selfie.filterData), + filterRefsFromSelfie(selfie.filterRefs), + ]; + if ( results.slice(1).every(v => v === true) === false ) { return false; } + + if ( selfie.version !== this.selfieVersion ) { return false; } + this.processedFilterCount = selfie.processedFilterCount; + this.acceptedCount = selfie.acceptedCount; + this.discardedCount = selfie.discardedCount; + this.bitsToBucket = selfie.bitsToBucket; + urlTokenizer.fromSelfie(selfie.urlTokenizer); + + // If this point is never reached, it means the internal state is + // unreliable, and the caller is then responsible for resetting the + // engine and populate properly, in which case the `notReady` barrier + // will be properly reset. + + this.notReady = false; + + return true; +}; + +StaticNetFilteringEngine.prototype.unserialize = function(selfie) { + return this.fromSelfie(selfie); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.createCompiler = function() { + return new FilterCompiler(); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.fromCompiled = function(reader) { + reader.select('NETWORK_FILTERS:GOOD'); + while ( reader.next() ) { + this.acceptedCount += 1; + if ( this.goodFilters.has(reader.line) ) { + this.discardedCount += 1; + } else { + this.goodFilters.add(reader.line); + } + } + + reader.select('NETWORK_FILTERS:BAD'); + while ( reader.next() ) { + this.badFilters.add(reader.line); + } +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.matchAndFetchModifiers = function( + fctxt, + modifierName +) { + if ( this.notReady ) { return; } + + const typeBits = typeNameToTypeValue[fctxt.type] || otherTypeBitValue; + + $requestURL = urlTokenizer.setURL(fctxt.url); + $requestURLRaw = fctxt.url; + $docHostname = fctxt.getDocHostname(); + $docDomain = fctxt.getDocDomain(); + $requestHostname = fctxt.getHostname(); + $requestMethodBit = fctxt.method || 0; + $requestTypeValue = (typeBits & TYPE_REALM) >>> TYPE_REALM_OFFSET; + $requestAddress = fctxt.getIPAddress(); + + const modifierType = modifierTypeFromName.get(modifierName); + const modifierBits = modifierBitsFromType.get(modifierType); + + const partyBits = fctxt.is3rdPartyToDoc() ? THIRDPARTY_REALM : FIRSTPARTY_REALM; + + const catBits00 = modifierBits; + const catBits01 = modifierBits | typeBits; + const catBits10 = modifierBits | partyBits; + const catBits11 = modifierBits | typeBits | partyBits; + + const bucket00 = this.bitsToBucket.get(catBits00); + const bucket01 = typeBits !== 0 + ? this.bitsToBucket.get(catBits01) + : undefined; + const bucket10 = partyBits !== 0 + ? this.bitsToBucket.get(catBits10) + : undefined; + const bucket11 = typeBits !== 0 && partyBits !== 0 + ? this.bitsToBucket.get(catBits11) + : undefined; + + if ( + bucket00 === undefined && bucket01 === undefined && + bucket10 === undefined && bucket11 === undefined + ) { + return; + } + + const results = []; + const env = { + type: modifierType || 0, + bits: 0, + th: 0, + iunit: 0, + results, + }; + + const tokenHashes = urlTokenizer.getTokens(); + let i = 0; + let th = 0, iunit = 0; + for (;;) { + th = tokenHashes[i]; + if ( th === INVALID_TOKEN_HASH ) { break; } + env.th = th; + $tokenBeg = tokenHashes[i+1]; + if ( + (bucket00 !== undefined) && + (iunit = bucket00.get(th) || 0) !== 0 + ) { + env.bits = catBits00; env.iunit = iunit; + filterMatchAndFetchModifiers(iunit, env); + } + if ( + (bucket01 !== undefined) && + (iunit = bucket01.get(th) || 0) !== 0 + ) { + env.bits = catBits01; env.iunit = iunit; + filterMatchAndFetchModifiers(iunit, env); + } + if ( + (bucket10 !== undefined) && + (iunit = bucket10.get(th) || 0) !== 0 + ) { + env.bits = catBits10; env.iunit = iunit; + filterMatchAndFetchModifiers(iunit, env); + } + if ( + (bucket11 !== undefined) && + (iunit = bucket11.get(th) || 0) !== 0 + ) { + env.bits = catBits11; env.iunit = iunit; + filterMatchAndFetchModifiers(iunit, env); + } + i += 2; + } + + if ( results.length === 0 ) { return; } + + // One single result is expected to be a common occurrence, and in such + // case there is no need to process exception vs. block, block important + // occurrences. + if ( results.length === 1 ) { + const result = results[0]; + if ( (result.bits & ALLOW_REALM) !== 0 ) { return; } + return [ result ]; + } + + const toAddImportant = new Map(); + const toAdd = new Map(); + const toRemove = new Map(); + + for ( const result of results ) { + const actionBits = result.bits & BLOCKALLOW_REALM; + const modifyValue = result.value; + if ( actionBits === BLOCKIMPORTANT_REALM ) { + toAddImportant.set(modifyValue, result); + } else if ( actionBits === BLOCK_REALM ) { + toAdd.set(modifyValue, result); + } else { + toRemove.set(modifyValue, result); + } + } + if ( toAddImportant.size === 0 && toAdd.size === 0 ) { return; } + + // Remove entries overridden by important block filters. + if ( toAddImportant.size !== 0 ) { + for ( const key of toAddImportant.keys() ) { + toAdd.delete(key); + toRemove.delete(key); + } + } + + // Exception filters + // + // Remove excepted block filters and unused exception filters. + // + // Special case, except-all: + // - Except-all applies only if there is at least one normal block filters. + // - Except-all does not apply to important block filters. + if ( toRemove.size !== 0 ) { + if ( toRemove.has('') === false ) { + for ( const key of toRemove.keys() ) { + if ( toAdd.has(key) ) { + toAdd.delete(key); + } else { + toRemove.delete(key); + } + } + } + else if ( toAdd.size !== 0 ) { + toAdd.clear(); + if ( toRemove.size !== 1 ) { + const entry = toRemove.get(''); + toRemove.clear(); + toRemove.set('', entry); + } + } else { + toRemove.clear(); + } + } + + if ( + toAdd.size === 0 && + toAddImportant.size === 0 && + toRemove.size === 0 + ) { + return; + } + + const out = Array.from(toAdd.values()); + if ( toAddImportant.size !== 0 ) { + out.push(...toAddImportant.values()); + } + if ( toRemove.size !== 0 ) { + out.push(...toRemove.values()); + } + return out; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.realmMatchString = function( + realmBits, + typeBits, + partyBits +) { + if ( this.notReady ) { return false; } + + const exactType = typeBits & 0x80000000; + typeBits &= 0x7FFFFFFF; + + const catBits00 = realmBits; + const catBits01 = realmBits | typeBits; + const catBits10 = realmBits | partyBits; + const catBits11 = realmBits | typeBits | partyBits; + + const bucket00 = exactType === 0 + ? this.bitsToBucket.get(catBits00) + : undefined; + const bucket01 = exactType !== 0 || typeBits !== 0 + ? this.bitsToBucket.get(catBits01) + : undefined; + const bucket10 = exactType === 0 && partyBits !== 0 + ? this.bitsToBucket.get(catBits10) + : undefined; + const bucket11 = (exactType !== 0 || typeBits !== 0) && partyBits !== 0 + ? this.bitsToBucket.get(catBits11) + : undefined; + + if ( + bucket00 === undefined && bucket01 === undefined && + bucket10 === undefined && bucket11 === undefined + ) { + return false; + } + + let catBits = 0, iunit = 0; + + // Pure hostname-based filters + let tokenHash = DOT_TOKEN_HASH; + if ( + (bucket00 !== undefined) && + (iunit = bucket00.get(DOT_TOKEN_HASH) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits00; + } else if ( + (bucket01 !== undefined) && + (iunit = bucket01.get(DOT_TOKEN_HASH) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits01; + } else if ( + (bucket10 !== undefined) && + (iunit = bucket10.get(DOT_TOKEN_HASH) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits10; + } else if ( + (bucket11 !== undefined) && + (iunit = bucket11.get(DOT_TOKEN_HASH) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits11; + } + // Pattern-based filters + else { + const tokenHashes = urlTokenizer.getTokens(); + let i = 0; + for (;;) { + tokenHash = tokenHashes[i]; + if ( tokenHash === INVALID_TOKEN_HASH ) { return false; } + $tokenBeg = tokenHashes[i+1]; + if ( + (bucket00 !== undefined) && + (iunit = bucket00.get(tokenHash) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits00; + break; + } + if ( + (bucket01 !== undefined) && + (iunit = bucket01.get(tokenHash) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits01; + break; + } + if ( + (bucket10 !== undefined) && + (iunit = bucket10.get(tokenHash) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits10; + break; + } + if ( + (bucket11 !== undefined) && + (iunit = bucket11.get(tokenHash) || 0) !== 0 && + (filterMatch(iunit) === true) + ) { + catBits = catBits11; + break; + } + i += 2; + } + } + + this.$catBits = catBits; + this.$tokenHash = tokenHash; + this.$filterUnit = iunit; + return true; +}; + +/******************************************************************************/ + +// Specialized handler + +// https://github.com/gorhill/uBlock/issues/1477 +// Special case: blocking-generichide filter ALWAYS exists, it is implicit -- +// thus we always first check for exception filters, then for important block +// filter if and only if there was a hit on an exception filter. +// https://github.com/gorhill/uBlock/issues/2103 +// User may want to override `generichide` exception filters. +// https://www.reddit.com/r/uBlockOrigin/comments/d6vxzj/ +// Add support for `specifichide`. + +StaticNetFilteringEngine.prototype.matchRequestReverse = function(type, url) { + const typeBits = typeNameToTypeValue[type] | 0x80000000; + + // Prime tokenizer: we get a normalized URL in return. + $requestURL = urlTokenizer.setURL(url); + $requestURLRaw = url; + $requestMethodBit = 0; + $requestTypeValue = (typeBits & TYPE_REALM) >>> TYPE_REALM_OFFSET; + $requestAddress = ''; + $isBlockImportant = false; + this.$filterUnit = 0; + + // These registers will be used by various filters + $docHostname = $requestHostname = hostnameFromNetworkURL(url); + $docDomain = domainFromHostname($docHostname); + + // Exception filters + if ( this.realmMatchString(ALLOW_REALM, typeBits, FIRSTPARTY_REALM) ) { + // Important block filters. + if ( this.realmMatchString(BLOCKIMPORTANT_REALM, typeBits, FIRSTPARTY_REALM) ) { + return 1; + } + return 2; + } + return 0; + +}; + +/******************************************************************************/ + +// https://github.com/chrisaljoudi/uBlock/issues/116 +// Some type of requests are exceptional, they need custom handling, +// not the generic handling. +// https://github.com/chrisaljoudi/uBlock/issues/519 +// Use exact type match for anything beyond `other`. Also, be prepared to +// support unknown types. +// https://github.com/uBlockOrigin/uBlock-issues/issues/1501 +// Add support to evaluate allow realm before block realm. + +/** + * Matches a URL string using filtering context. + * @param {FilteringContext} fctxt - The filtering context + * @param {integer} [modifier=0] - A bit vector modifying the behavior of the + * matching algorithm: + * Bit 0: match exact type. + * Bit 1: lookup allow realm regardless of whether there was a match in + * block realm. + * + * @returns {integer} 0=no match, 1=block, 2=allow (exception) + */ +StaticNetFilteringEngine.prototype.matchRequest = function(fctxt, modifiers = 0) { + let typeBits = typeNameToTypeValue[fctxt.type]; + if ( modifiers === 0 ) { + if ( typeBits === undefined ) { + typeBits = otherTypeBitValue; + } else if ( typeBits === 0 || typeBits > otherTypeBitValue ) { + modifiers |= 0b0001; + } + } + if ( (modifiers & 0b0001) !== 0 ) { + if ( typeBits === undefined ) { return 0; } + typeBits |= 0x80000000; + } + + const partyBits = fctxt.is3rdPartyToDoc() ? THIRDPARTY_REALM : FIRSTPARTY_REALM; + + // Prime tokenizer: we get a normalized URL in return. + $requestURL = urlTokenizer.setURL(fctxt.url); + $requestURLRaw = fctxt.url; + this.$filterUnit = 0; + + // These registers will be used by various filters + $docHostname = fctxt.getDocHostname(); + $docDomain = fctxt.getDocDomain(); + $requestHostname = fctxt.getHostname(); + $requestMethodBit = fctxt.method || 0; + $requestTypeValue = (typeBits & TYPE_REALM) >>> TYPE_REALM_OFFSET; + $requestAddress = fctxt.getIPAddress(); + $isBlockImportant = false; + + // Evaluate block realm before allow realm, and allow realm before + // block-important realm, i.e. by order of likelihood of a match. + const r = this.realmMatchString(BLOCK_REALM, typeBits, partyBits); + if ( r || (modifiers & 0b0010) !== 0 ) { + if ( $isBlockImportant ) { return 1; } + if ( this.realmMatchString(ALLOW_REALM, typeBits, partyBits) ) { + if ( this.realmMatchString(BLOCKIMPORTANT_REALM, typeBits, partyBits) ) { + return 1; + } + return 2; + } + if ( r ) { return 1; } + } + return 0; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.matchHeaders = function(fctxt, headers) { + const typeBits = typeNameToTypeValue[fctxt.type] || otherTypeBitValue; + const partyBits = fctxt.is3rdPartyToDoc() ? THIRDPARTY_REALM : FIRSTPARTY_REALM; + + // Prime tokenizer: we get a normalized URL in return. + $requestURL = urlTokenizer.setURL(fctxt.url); + $requestURLRaw = fctxt.url; + this.$filterUnit = 0; + + // These registers will be used by various filters + $docHostname = fctxt.getDocHostname(); + $docDomain = fctxt.getDocDomain(); + $requestHostname = fctxt.getHostname(); + $requestMethodBit = fctxt.method || 0; + $requestTypeValue = (typeBits & TYPE_REALM) >>> TYPE_REALM_OFFSET; + $requestAddress = fctxt.getIPAddress(); + $isBlockImportant = false; + $httpHeaders.init(headers); + + let r = 0; + if ( this.realmMatchString(HEADERS_REALM | BLOCK_REALM, typeBits, partyBits) ) { + r = 1; + } + if ( r !== 0 && $isBlockImportant !== true ) { + if ( this.realmMatchString(HEADERS_REALM | ALLOW_REALM, typeBits, partyBits) ) { + r = 2; + } else if ( this.realmMatchString(ALLOW_REALM, typeBits, partyBits) ) { + r = 2; + } + if ( r === 2 ) { + if ( this.realmMatchString(HEADERS_REALM | BLOCKIMPORTANT_REALM, typeBits, partyBits) ) { + r = 1; + } + } + } + + $httpHeaders.reset(); + + return r; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.redirectRequest = function(redirectEngine, fctxt) { + const directives = this.matchAndFetchModifiers(fctxt, 'redirect-rule'); + // No directive is the most common occurrence. + if ( directives === undefined ) { return; } + const highest = directives.length - 1; + // More than a single directive means more work. + if ( highest !== 0 ) { + directives.sort((a, b) => compareRedirectRequests(redirectEngine, a, b)); + } + // Redirect to highest-ranked directive + const directive = directives[highest]; + if ( (directive.bits & ALLOW_REALM) !== 0 ) { return directives; } + const { token } = parseRedirectRequestValue(directive); + fctxt.redirectURL = redirectEngine.tokenToURL(fctxt, token); + if ( fctxt.redirectURL === undefined ) { return; } + return directives; +}; + +function parseRedirectRequestValue(directive) { + if ( directive.cache === null ) { + directive.cache = sfp.parseRedirectValue(directive.value); + } + return directive.cache; +} + +function compareRedirectRequests(redirectEngine, a, b) { + const { token: atok, priority: aint, bits: abits } = + parseRedirectRequestValue(a); + if ( redirectEngine.hasToken(atok) === false ) { return -1; } + const { token: btok, priority: bint, bits: bbits } = + parseRedirectRequestValue(b); + if ( redirectEngine.hasToken(btok) === false ) { return 1; } + if ( abits !== bbits ) { + if ( (abits & IMPORTANT_REALM) !== 0 ) { return 1; } + if ( (bbits & IMPORTANT_REALM) !== 0 ) { return -1; } + if ( (abits & ALLOW_REALM) !== 0 ) { return -1; } + if ( (bbits & ALLOW_REALM) !== 0 ) { return 1; } + } + return aint - bint; +} + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.transformRequest = function(fctxt, out = []) { + const directives = this.matchAndFetchModifiers(fctxt, 'uritransform'); + if ( directives === undefined ) { return; } + const redirectURL = new URL(fctxt.url); + for ( const directive of directives ) { + if ( (directive.bits & ALLOW_REALM) !== 0 ) { + out.push(directive); + continue; + } + if ( directive.cache === null ) { + directive.cache = sfp.parseReplaceByRegexValue(directive.value); + } + const cache = directive.cache; + if ( cache === undefined ) { continue; } + const before = `${redirectURL.pathname}${redirectURL.search}${redirectURL.hash}`; + if ( cache.re.test(before) !== true ) { continue; } + const after = before.replace(cache.re, cache.replacement); + if ( after === before ) { continue; } + const hashPos = after.indexOf('#'); + redirectURL.hash = hashPos !== -1 ? after.slice(hashPos) : ''; + const afterMinusHash = hashPos !== -1 ? after.slice(0, hashPos) : after; + const searchPos = afterMinusHash.indexOf('?'); + redirectURL.search = searchPos !== -1 ? afterMinusHash.slice(searchPos) : ''; + redirectURL.pathname = searchPos !== -1 ? after.slice(0, searchPos) : after; + out.push(directive); + } + if ( out.length === 0 ) { return; } + if ( redirectURL.href !== fctxt.url ) { + fctxt.redirectURL = redirectURL.href; + } + return out; +}; + +StaticNetFilteringEngine.prototype.urlSkip = function( + fctxt, + blocked, + out = [] +) { + if ( fctxt.redirectURL !== undefined ) { return; } + const directives = this.matchAndFetchModifiers(fctxt, 'urlskip'); + if ( directives === undefined ) { return; } + for ( const directive of directives ) { + if ( (directive.bits & ALLOW_REALM) !== 0 ) { + out.push(directive); + continue; + } + const urlin = fctxt.url; + const value = directive.value; + const steps = value.includes(' ') && value.split(/ +/) || [ value ]; + const urlout = urlSkip(urlin, blocked, steps, directive); + if ( urlout === undefined ) { continue; } + if ( urlout === urlin ) { continue; } + fctxt.redirectURL = urlout; + out.push(directive); + break; + } + if ( out.length === 0 ) { return; } + return out; +}; + +/******************************************************************************/ + +// https://github.com/uBlockOrigin/uBlock-issues/issues/1626 +// Do not redirect when the number of query parameters does not change. + +StaticNetFilteringEngine.prototype.filterQuery = function(fctxt, out = []) { + if ( fctxt.redirectURL !== undefined ) { return; } + const directives = this.matchAndFetchModifiers(fctxt, 'removeparam'); + if ( directives === undefined ) { return; } + const url = fctxt.url; + const qpos = url.indexOf('?'); + if ( qpos === -1 ) { return; } + let hpos = url.indexOf('#', qpos + 1); + if ( hpos === -1 ) { hpos = url.length; } + const params = new Map(); + const query = url.slice(qpos + 1, hpos); + for ( let i = 0; i < query.length; ) { + let pos = query.indexOf('&', i); + if ( pos === -1 ) { pos = query.length; } + const kv = query.slice(i, pos); + i = pos + 1; + pos = kv.indexOf('='); + if ( pos !== -1 ) { + params.set(kv.slice(0, pos), kv.slice(pos + 1)); + } else { + params.set(kv, ''); + } + } + const inParamCount = params.size; + for ( const directive of directives ) { + if ( params.size === 0 ) { break; } + const isException = (directive.bits & ALLOW_REALM) !== 0; + if ( isException && directive.value === '' ) { + out.push(directive); + break; + } + const { all, bad, name, not, re } = parseQueryPruneValue(directive); + if ( bad ) { continue; } + if ( all ) { + if ( isException === false ) { params.clear(); } + out.push(directive); + break; + } + if ( name !== undefined ) { + const value = params.get(name); + if ( not === false ) { + if ( value !== undefined ) { + if ( isException === false ) { params.delete(name); } + out.push(directive); + } + continue; + } + if ( value !== undefined ) { params.delete(name); } + if ( params.size !== 0 ) { + if ( isException === false ) { params.clear(); } + out.push(directive); + } + if ( value !== undefined ) { params.set(name, value); } + continue; + } + if ( re === undefined ) { continue; } + let filtered = false; + for ( const [ key, raw ] of params ) { + let value = raw; + try { value = decodeURIComponent(value); } + catch { } + if ( re.test(`${key}=${value}`) === not ) { continue; } + if ( isException === false ) { params.delete(key); } + filtered = true; + } + if ( filtered ) { + out.push(directive); + } + } + if ( out.length === 0 ) { return; } + if ( params.size !== inParamCount ) { + fctxt.redirectURL = url.slice(0, qpos); + if ( params.size !== 0 ) { + fctxt.redirectURL += '?' + Array.from(params).map(a => + a[1] === '' ? `${a[0]}=` : `${a[0]}=${a[1]}` + ).join('&'); + } + if ( hpos !== url.length ) { + fctxt.redirectURL += url.slice(hpos); + } + } + return out; +}; + +function parseQueryPruneValue(directive) { + if ( directive.cache === null ) { + directive.cache = + sfp.parseQueryPruneValue(directive.value); + } + return directive.cache; +} + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.hasQuery = function(fctxt) { + urlTokenizer.setURL(fctxt.url); + return urlTokenizer.hasQuery(); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.toLogData = function() { + if ( this.$filterUnit !== 0 ) { + return new LogData(this.$catBits, this.$tokenHash, this.$filterUnit); + } +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.isBlockImportant = function() { + return this.$filterUnit !== 0 && $isBlockImportant; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.getFilterCount = function() { + return this.acceptedCount - this.discardedCount; +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.enableWASM = function(wasmModuleFetcher, path) { + return Promise.all([ + bidiTrie.enableWASM(wasmModuleFetcher, path), + origHNTrieContainer.enableWASM(wasmModuleFetcher, path), + destHNTrieContainer.enableWASM(wasmModuleFetcher, path), + ]).then(results => { + return results.every(a => a === true); + }); +}; + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.test = function(details) { + const { url, type, from, redirectEngine } = details; + if ( url === undefined ) { return; } + const fctxt = new FilteringContext(); + fctxt.setURL(url); + fctxt.setType(type || ''); + fctxt.setDocOriginFromURL(from || ''); + const r = this.matchRequest(fctxt); + const out = [ `url: ${url}` ]; + if ( type ) { + out.push(`type: ${type}`); + } + if ( from ) { + out.push(`context: ${from}`); + } + if ( r !== 0 ) { + const logdata = this.toLogData(); + if ( r === 1 ) { + out.push(`blocked: ${logdata.raw}`); + } else if ( r === 2 ) { + out.push(`unblocked: ${logdata.raw}`); + } + } else { + out.push('not blocked'); + } + if ( r !== 1 ) { + const entries = this.transformRequest(fctxt); + if ( entries ) { + for ( const entry of entries ) { + out.push(`modified: ${entry.logData().raw}`); + } + } + if ( fctxt.redirectURL !== undefined && this.hasQuery(fctxt) ) { + const entries = this.filterQuery(fctxt, 'removeparam'); + if ( entries ) { + for ( const entry of entries ) { + out.push(`modified: ${entry.logData().raw}`); + } + } + } + if ( fctxt.type === 'main_frame' || fctxt.type === 'sub_frame' ) { + const csps = this.matchAndFetchModifiers(fctxt, 'csp'); + if ( csps ) { + for ( const csp of csps ) { + out.push(`modified: ${csp.logData().raw}`); + } + } + const pps = this.matchAndFetchModifiers(fctxt, 'permissions'); + if ( pps ) { + for ( const pp of pps ) { + out.push(`modified: ${pp.logData().raw}`); + } + } + } + } else if ( redirectEngine ) { + const redirects = this.redirectRequest(redirectEngine, fctxt); + if ( redirects ) { + for ( const redirect of redirects ) { + out.push(`modified: ${redirect.logData().raw}`); + } + } + } + const urlskips = this.matchAndFetchModifiers(fctxt, 'urlskip'); + if ( urlskips ) { + for ( const urlskip of urlskips ) { + out.push(`modified: ${urlskip.logData().raw}`); + } + } + return out.join('\n'); +} + +/******************************************************************************/ + +StaticNetFilteringEngine.prototype.bucketHistogram = function() { + const results = []; + for ( const [ bits, bucket ] of this.bitsToBucket ) { + for ( const [ th, iunit ] of bucket ) { + const token = urlTokenizer.stringFromTokenHash(th); + const fc = filterGetClass(iunit); + const count = fc.getCount !== undefined ? fc.getCount(iunit) : 1; + results.push({ bits: bits.toString(16), token, count, f: fc.name }); + } + } + results.sort((a, b) => { + return b.count - a.count; + }); + console.info(results); +}; + +/******************************************************************************/ + +// Dump the internal state of the filtering engine to the console. +// Useful to make development decisions and investigate issues. + +StaticNetFilteringEngine.prototype.dump = function() { + const thConstants = new Map([ + [ NO_TOKEN_HASH, 'NO_TOKEN_HASH' ], + [ DOT_TOKEN_HASH, 'DOT_TOKEN_HASH' ], + [ ANY_TOKEN_HASH, 'ANY_TOKEN_HASH' ], + [ ANY_HTTPS_TOKEN_HASH, 'ANY_HTTPS_TOKEN_HASH' ], + [ ANY_HTTP_TOKEN_HASH, 'ANY_HTTP_TOKEN_HASH' ], + [ EMPTY_TOKEN_HASH, 'EMPTY_TOKEN_HASH' ], + ]); + + const out = []; + + const toOutput = (depth, line) => { + out.push(`${' '.repeat(depth*2)}${line}`); + }; + + const dumpUnit = (idata, depth = 0) => { + const fc = filterGetClass(idata); + fcCounts.set(fc.name, (fcCounts.get(fc.name) || 0) + 1); + const info = filterDumpInfo(idata) || ''; + toOutput(depth, info !== '' ? `${fc.name}: ${info}` : fc.name); + switch ( fc ) { + case FilterBucket: + case FilterCompositeAll: + case FilterDomainHitAny: { + fc.forEach(idata, i => { + dumpUnit(i, depth+1); + }); + break; + } + case FilterBucketIfOriginHits: { + dumpUnit(filterData[idata+2], depth+1); + dumpUnit(filterData[idata+1], depth+1); + break; + } + case FilterBucketIfRegexHits: { + dumpUnit(filterData[idata+1], depth+1); + break; + } + case FilterPlainTrie: { + for ( const details of bidiTrie.trieIterator(filterData[idata+1]) ) { + toOutput(depth+1, details.pattern); + let ix = details.iextra; + if ( ix === 1 ) { continue; } + for (;;) { + if ( ix === 0 ) { break; } + dumpUnit(filterData[ix+0], depth+2); + ix = filterData[ix+1]; + } + } + break; + } + default: + break; + } + }; + + const fcCounts = new Map(); + const thCounts = new Set(); + + const realms = new Map([ + [ BLOCK_REALM, 'block' ], + [ BLOCKIMPORTANT_REALM, 'block-important' ], + [ ALLOW_REALM, 'unblock' ], + [ REDIRECT_REALM, 'redirect' ], + [ REMOVEPARAM_REALM, 'removeparam' ], + [ CSP_REALM, 'csp' ], + [ PERMISSIONS_REALM, 'permissions' ], + [ URLTRANSFORM_REALM, 'uritransform' ], + [ REPLACE_REALM, 'replace' ], + [ URLSKIP_REALM, 'urlskip' ], + ]); + const partyness = new Map([ + [ ANYPARTY_REALM, 'any-party' ], + [ FIRSTPARTY_REALM, '1st-party' ], + [ THIRDPARTY_REALM, '3rd-party' ], + ]); + for ( const [ realmBits, realmName ] of realms ) { + toOutput(1, `+ realm: ${realmName}`); + for ( const [ partyBits, partyName ] of partyness ) { + toOutput(2, `+ party: ${partyName}`); + const processedTypeBits = new Set(); + for ( const typeName in typeNameToTypeValue ) { + const typeBits = typeNameToTypeValue[typeName]; + if ( processedTypeBits.has(typeBits) ) { continue; } + processedTypeBits.add(typeBits); + const bits = realmBits | partyBits | typeBits; + const bucket = this.bitsToBucket.get(bits); + if ( bucket === undefined ) { continue; } + const thCount = bucket.size; + toOutput(3, `+ type: ${typeName} (${thCount})`); + for ( const [ th, iunit ] of bucket) { + thCounts.add(th); + const ths = thConstants.has(th) + ? thConstants.get(th) + : `0x${th.toString(16)}`; + toOutput(4, `+ th: ${ths}`); + dumpUnit(iunit, 5); + } + } + } + } + + const knownTokens = + urlTokenizer.knownTokens + .reduce((a, b) => b !== 0 ? a+1 : a, 0); + + out.unshift([ + 'Static Network Filtering Engine internals:', + ` Distinct token hashes: ${thCounts.size.toLocaleString('en')}`, + ` Known-token sieve (Uint8Array): ${knownTokens.toLocaleString('en')} out of 65,536`, + ` Filter data (Int32Array): ${filterDataWritePtr.toLocaleString('en')}`, + ` Filter refs (JS array): ${filterRefsWritePtr.toLocaleString('en')}`, + ' Origin trie container:', + origHNTrieContainer.dumpInfo().split('\n').map(a => ` ${a}`).join('\n'), + ' Request trie container:', + destHNTrieContainer.dumpInfo().split('\n').map(a => ` ${a}`).join('\n'), + ' Pattern trie container:', + bidiTrie.dumpInfo().split('\n').map(a => ` ${a}`).join('\n'), + '+ Filter class stats:', + Array.from(fcCounts) + .sort((a, b) => b[1] - a[1]) + .map(a => ` ${a[0]}: ${a[1].toLocaleString('en')}`) + .join('\n'), + '+ Filter tree:', + ].join('\n')); + return out.join('\n'); +}; + +/******************************************************************************/ + +const staticNetFilteringEngine = new StaticNetFilteringEngine(); + +export default staticNetFilteringEngine; |