使用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代替了。