Expand bidi-trie code to hold more types of filters

[gorhill]

Related issue:

• Coalesce common plain filters in a bucket into a single trie #528

The current bidi-trie code can hold filters which are plain pattern, i.e. no wildcard characters, and which have no origin option (i.e. domain=), right or left anchor, and neither a csp= option.

Examples of filter that can be moved into a bidi-trie data structure:

&ad_box_
/w/d/capu.php?z=$script,third-party
||liveonlinetv247.com/images/muvixx-150x50-watch-now-in-hd-play-btn.gif

Examples of filters that cannot be moved to a bidi-trie:

-adap.$domain=~l-adap.org
/tsc.php?*&ses=
||ibsrv.net/*forumsponsor$domain=[...]
@@||imgspice.com/jquery.cookie.js|$script
||view.atdmt.com^*/iview/$third-party
||postimg.cc/image/$csp=[...]

Ideally the filters above should be able to be moved to a bidi-trie since they are basically plain patterns, or at least partially moved to a bidi-trie when there is only a single wildcard (i.e. made of two plain patterns).

Also, currently there are two distinct bidi-tries in which plain-pattern filters can be moved to: one for patterns without hostname anchoring and another one for patterns with hostname-anchoring. This is currently required because the hostname-anchored patterns have an extra condition which is outside the bidi-trie knowledge. Ideally there should be only one bidi-trie for both filters.

This issue is to track the work on this.

[gorhill]

Stats comparing before/after for top 25 buckets, from most populous to least populous. For the before: stats, the trie= figure is the sum of the two tries that were used, while there is a single figure for after: since there is now only one trie per bucket. The array= figure is the number of filters which can't be put in a trie and which must be iterated when there is no match against the trie. Some buckets are not present in either before: or after:: this is because the token picking code has been changed -- the "bad tokens" are now programmatically generated.

bits: 0, token: cf
- before: size=940   trie=911+9  array=20
-  after: size=1030  trie=1027   array= 3

bits: 0, token: cee
- before:  size=649  trie=641+0  array=8
-  after:  size=770  trie=769    array=1

bits: 41, token: 1a29ee9
- before:  size=253  trie=0+231  array=22
-  after:  size=253  trie=251    array=2

bits: 0, token: d9d55e4
- before:  size=211  trie=174+10  array=27
-  after:  size=235  trie=232     array=3

bits: 0, token: 1edcf759
- before:  size=163  trie=154+0  array=9
-  after:  size=178  trie=176    array=2

bits: 0, token: cd1
- before:  size=122  trie=118+0  array=4
-  after:  size=142  trie=142    array=0

bits: 41, token: 158dee6
- before:  size=121  trie=0+0  array=121
-  after:  ?

bits: 41, token: 1ee76acf
- before:  ?
-  after:  size=116  trie=116  array=0

bits: 0, token: cd01ce4
- before:  size=104  trie=86+0  array=18
-  after:  size=104  trie=104   array=0

bits: 0, token: 1edcf6
- before:  size=100  trie=88+0  array=12
-  after:  size=106  trie=105   array=1

bits: 0, token: f34
- before:  ?
-  after:  size=96  trie=95  array=1

bits: 8, token: e80c60e
- before:  size=96  trie=0+54  array=42
-  after:  size=96  trie=95    array=1

bits: 0, token: ee9
- before:  size=88  trie=8+9  array=71
-  after:  ?

bits: 0, token: 1ffdee
- before:  size=84  trie=80+0  array=4
-  after:  size=95  trie=94    array=1

bits: 0, token: 16b2
- before:  size=74  trie=65+0  array=9
-  after:  size=83  trie=80    array=3

bits: 40, token: 1bd30cf3
- before:  size=80  trie=0+0  array=80
-  after:  size=80  trie=75   array=5

bits: 0, token: dd881d
- before:  size=76  trie=75+0  array=1
-  after:  size=77  trie=77    array=0

bits: 0, token: 1fab8fbd
- before:  size=73  trie=70+0  array=3
-  after:  size=77  trie=77    array=0

bits: 0, token: 12c
- before:  size=71  trie=66+0  array=5
-  after:  size=76  trie=76    array=0

bits: 0, token: 1edcf71d
- before:  size=68  trie=63+0  array=5
-  after:  size=71  trie=71    array=0

bits: 0, token: 1351
- before:  size=70  trie=62+0  array=8
-  after:  ?

bits: 0, token: 13bb360c
- before:  size=73  trie=64+0  array=9
-  after:  size=69  trie=69    array=0

bits: 0, token: f680e0d
- before:  size=66  trie=0+45  array=21
-  after:  size=66  trie=64    array=2

bits: 0, token: 1a6217
- before:  size=53  trie=46+0  array=7
-  after:  size=53  trie=55    array=1

bits: 0, token: d00564c
- before:  size=52  trie=48+0  array=4
-  after:  size=54  trie=54    array=0

bits: 0, token: d8e4b9c
- before:  size=51  trie=0+30  array=21
-  after:  size=51  trie=50    array=1

bits: 41, token: ee84e
- before:  ?
-  after:  size=49  trie=39     array=10

(all the comments I add here are meant to be used in the commit message, hence why I am verbose).