prosody
4314eeeed394
util/rfc3484.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Annotate

util/rfc3484.lua @ 4420:4314eeeed394

util.rfc3484: New util implementing RFC3484 sorting
author Florian Zeitz <florob@babelmonkeys.de>
date Sat, 22 Oct 2011 17:59:33 +0200
child 4423:ded726418b16
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4420
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
1 -- Prosody IM
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
2 -- Copyright (C) 2008-2011 Florian Zeitz
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
3 --
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
4 -- This project is MIT/X11 licensed. Please see the
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
5 -- COPYING file in the source package for more information.
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
6 --
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
7
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
8 local t_sort = table.sort;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
9 local commonPrefixLength = require"util.ip".commonPrefixLength
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
10 local new_ip = require"util.ip".new_ip;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
11
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
12 function source(dest, candidates)
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
13 local function comp(ipA, ipB)
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
14 -- Rule 1: Prefer same address
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
15 if dest == ipA then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
16 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
17 elseif dest == ipB then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
18 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
19 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
20
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
21 -- Rule 2: Prefer appropriate scope
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
22 if ipA.scope < ipB.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
23 if ipA.scope < dest.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
24 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
25 else
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
26 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
27 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
28 elseif ipA.scope > ipB.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
29 if ipB.scope < dest.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
30 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
31 else
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
32 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
33 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
34 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
35
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
36 -- Rule 3: Avoid deprecated addresses
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
37 -- XXX: No way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
38 -- Rule 4: Prefer home addresses
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
39 -- XXX: Mobility Address related, no way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
40 -- Rule 5: Prefer outgoing interface
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
41 -- XXX: Interface to address relation. No way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
42 -- Rule 6: Prefer matching label
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
43 if ipA.label == dest.label and ipB.label ~= dest.label then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
44 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
45 elseif ipB.label == dest.label and ipA.label ~= dest.label then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
46 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
47 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
48
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
49 -- Rule 7: Prefer public addresses (over temporary ones)
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
50 -- XXX: No way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
51 -- Rule 8: Use longest matching prefix
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
52 if commonPrefixLength(ipA, dest) > commonPrefixLength(ipB, dest) then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
53 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
54 else
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
55 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
56 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
57 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
58
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
59 t_sort(candidates, comp);
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
60 return candidates[1];
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
61 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
62
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
63 function destination(candidates, sources)
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
64 local t_sort = table.sort;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
65 local sourceAddrs = {};
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
66 local function comp(ipA, ipB)
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
67 local ipAsource = sourceAddrs[ipA];
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
68 local ipBsource = sourceAddrs[ipB];
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
69 -- Rule 1: Avoid unusable destinations
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
70 -- XXX: No such information
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
71 -- Rule 2: Prefer matching scope
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
72 if ipA.scope == ipAsource.scope and ipB.scope ~= ipBsource.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
73 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
74 elseif ipA.scope ~= ipAsource.scope and ipB.scope == ipBsource.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
75 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
76 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
77
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
78 -- Rule 3: Avoid deprecated addresses
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
79 -- XXX: No way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
80 -- Rule 4: Prefer home addresses
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
81 -- XXX: Mobility Address related, no way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
82 -- Rule 5: Prefer matching label
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
83 if ipAsource.label == ipA.label and ipBsource.label ~= ipB.label then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
84 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
85 elseif ipBsource.label == ipB.label and ipAsource.label ~= ipA.label then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
86 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
87 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
88
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
89 -- Rule 6: Prefer higher precedence
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
90 if ipA.precedence > ipB.precedence then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
91 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
92 elseif ipA.precedence < ipB.precedence then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
93 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
94 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
95
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
96 -- Rule 7: Prefer native transport
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
97 -- XXX: No way to determine this
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
98 -- Rule 8: Prefer smaller scope
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
99 if ipA.scope < ipB.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
100 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
101 elseif ipA.scope > ipB.scope then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
102 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
103 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
104
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
105 -- Rule 9: Use longest matching prefix
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
106 if commonPrefixLength(ipA, ipAsource) > commonPrefixLength(ipB, ipBsource) then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
107 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
108 elseif commonPrefixLength(ipA, ipAsource) < commonPrefixLength(ipB, ipBsource) then
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
109 return false;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
110 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
111
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
112 -- Rule 10: Otherwise, leave order unchanged
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
113 return true;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
114 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
115 for _, ip in ipairs(candidates) do
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
116 sourceAddrs[ip] = source(ip, sources);
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
117 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
118
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
119 t_sort(candidates, comp);
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
120 return candidates;
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
121 end
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
122
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
123 return {source = source,
4314eeeed394 util.rfc3484: New util implementing RFC3484 sorting
Florian Zeitz <florob@babelmonkeys.de>
parents:
diff changeset
124 destination = destination};