使用Double-array trie优化Proxy auto-config

Proxy auto-config

浏览器的proxy auto-config让我们可以根据URL和host决定使用什么代理。

PAC文件是一个JavaScript脚本,其中最重要的就是函数FindProxyForURL,下面给出一个简单的例子:

1
2
3
4
function FindProxyForURL(url, host)
{
return 'PROXY 0.1.2.3:4; SOCKS5 6.7.8.9:10; DIRECT';
}

这个函数接受两个参数,分别为URL和host,需要返回一个字符串,表示使用什么代理。 DIRECT即为不使用代理,直接链接;PROXY指定HTTP代理,IP地址和端口用冒号隔开; SOCKS5指定SOCKS5代理。

Chrome

Chrome可以带上命令行选项--proxy-pac-url指定PAC文件,比如:

1
google-chrome --proxy-pac-url=file:///home/ray/.config/google-chrome/proxy.pac "$@"

在地址栏输入chrome://net-internals/#proxy,如果PAC成功启用了,Effective settings会这样如下字样:

1
PAC script: file:///home/ray/.config/google-chrome/proxy.pac

PAC文件修改之后,需要点击Re-apply settings加载新的配置。

Firefox

找到

1
Preferences - Advanced - Network - Settings - Automatic proxy configuration URL

填入file:///home/ray/.config/google-chrome/proxy.pac,点击Reload

提高host匹配性能

实际应用的FindProxyForURL应该维护了一份需要代理的host列表,如果其中某个host是URL中host的后缀,那么就选择使用代理。

如果host列表很长,一一匹配性能会很低,需要考虑使用一些算法优化。

对于字符串检索问题,可以考虑使用trie这一数据结构。

Double-array trie

朴素实现的trie对于每个节点,都需要维护大小为|SIGMA|的children指针,其中|SIGMA|为字符集大小(这里就是合法的host字符集),空间复杂度较高。

Trie的一种改良double-array trie能大量节省空间,具体可以参考这篇文章:An Implementation of Double-Array Trie

实现

下面给出用于生成PAC文件的CoffeeScript程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class DATrie
constructor: (@n) ->
@alphabet = [0].concat '-.'.split('').map((c) -> c.charCodeAt(0)), [48..57], [97..122]
@mapping = {}
@mapping[x] = i for x, i in @alphabet

@base = Array(n)
@check = Array(n)
last = 0
for i in [@alphabet.length+2...n]
@check[last] = -i
@base[i] = -last
last = i
@check[last] = -0
@base[0] = -last
@base[1] = 2

chars: (s) ->
c for c in [0...@alphabet.length] when @check[@base[s]+c] == s

freeCell: (s) ->
@check[s] = @check[0]
@base[-@check[0]] = -s
@base[s] = -0
@check[0] = -s

useCell: (s) ->
if s >= @alphabet.length+2
@base[-@check[s]] = @base[s]
@check[-@base[s]] = @check[s]

allocate: (chars) ->
test = (b) =>
for c in chars
return false if @check[b+c] > 0 or @base[b+c] > 0
true

loop
b = -@check[0]
while b != 0
if b+@alphabet.length < @n and test b
return b
b = -@check[b]
nn = Math.ceil @n*1.3
base2 = Array(nn)
check2 = Array(nn)
for i in [0...@n]
base2[i] = @base[i]
check2[i] = @check[i]
@base = base2
@check = check2
for i in [nn-1..@n] by -1
@freeCell i
@n = nn

relocate: (s, b) ->
for c in @chars s
@useCell b+c
@check[b+c] = s
@base[b+c] = @base[@base[s]+c]
for cc in @chars(@base[s]+c)
@check[@base[@base[s]+c]+cc] = b+c
@freeCell @base[s]+c
@base[s] = b

ord: (ch) ->
@mapping[ch.charCodeAt(0)]

insertBranch: (s, c) ->
if @base[s] > 0
if @check[@base[s]+c] == s
return
if @check[@base[s]+c] > 0
@relocate s, @allocate([c].concat @chars s)
else
t = @allocate [c]
# @base may vary
@base[s] = t
@useCell @base[s]+c
@check[@base[s]+c] = s

insert: (str) ->
s = 1
for _, i in str
o = @ord str[i]
@insertBranch s, o
s = @base[s]+o
@insertBranch s, 0

retrieve: (str) ->
s = 1
for c in str
ss = @base[s]+@ord(c)
return false if @check[ss] != s
s = ss
true

String::reverse = ->
this.split('').reverse().join ''

hosts = [
'github.com'
'jquery.com'
]

trie = new DATrie(100)
for host in hosts
trie.insert host.reverse()

FindProxyForURL = (url, host) ->
proxy = 'PROXY 0.1.2.3:4; SOCKS5 6.7.8.9:10; DIRECT'
if trie.retrieve host.reverse()
proxy
else
'DIRECT'

使用coffee -bc datrie-pac.coffee编译得到不含top-level function wrapper的PAC文件。

另外,Chrome的PAC不支持Int32Array,上面代码就用Array代替了。