1package ldap
2
3import (
4 "cmp"
5 "strings"
6 "unicode"
7 "unicode/utf8"
8)
9
10type tri uint8
11
12const (
13 triFalse tri = iota
14 triTrue
15 triUndefined
16)
17
18type entry struct {
19 dn string
20 attrs map[string][]string
21}
22
23type matchKind uint8
24
25const (
26 matchExact matchKind = iota
27 matchASCIIFold
28 matchUnicodeFold
29 matchInteger
30)
31
32type attrRule struct {
33 name string
34 match matchKind
35 substrings bool
36 ordering bool
37}
38
39var attrRules = indexRules([]attrRule{
40 {name: "uid", match: matchASCIIFold, substrings: true},
41 {name: "dc", match: matchASCIIFold},
42 {name: "ou", match: matchASCIIFold},
43 {name: "o", match: matchASCIIFold},
44 {name: "cn", match: matchUnicodeFold, substrings: true},
45 {name: "displayname", match: matchUnicodeFold, substrings: true},
46 {name: "sn", match: matchUnicodeFold},
47 {name: "description", match: matchUnicodeFold},
48 {name: "memberof", match: matchExact},
49 {name: "member", match: matchExact},
50 {name: "memberuid", match: matchExact},
51 {name: "sshpublickey", match: matchExact},
52 {name: "homedirectory", match: matchExact},
53 {name: "objectclass", match: matchASCIIFold},
54 {name: "entryuuid", match: matchASCIIFold},
55 {name: "uidnumber", match: matchInteger, ordering: true},
56 {name: "gidnumber", match: matchInteger, ordering: true},
57})
58
59func indexRules(rules []attrRule) map[string]*attrRule {
60 m := make(map[string]*attrRule, len(rules))
61 for i := range rules {
62 m[rules[i].name] = &rules[i]
63 }
64 return m
65}
66
67func lookupAttribute(desc string) *attrRule {
68 return attrRules[asciiFold(desc)]
69}
70
71func (r *attrRule) normalize(s string) (string, bool) {
72 switch r.match {
73 case matchASCIIFold:
74 return asciiFold(s), true
75 case matchUnicodeFold:
76 return unicodeFold(s)
77 case matchInteger:
78 return s, validInteger(s)
79 }
80 return s, true
81}
82
83func (f FilterExpr) eval(e *entry) tri {
84 if f.root == nil || e == nil {
85 return triUndefined
86 }
87 return f.root.eval(e)
88}
89
90func (n *filterNode) eval(e *entry) tri {
91 switch n.kind {
92 case filterAnd:
93 result := triTrue
94 for _, child := range n.children {
95 switch child.eval(e) {
96 case triFalse:
97 return triFalse
98 case triUndefined:
99 result = triUndefined
100 }
101 }
102 return result
103 case filterOr:
104 result := triFalse
105 for _, child := range n.children {
106 switch child.eval(e) {
107 case triTrue:
108 return triTrue
109 case triUndefined:
110 result = triUndefined
111 }
112 }
113 return result
114 case filterNot:
115 switch n.children[0].eval(e) {
116 case triTrue:
117 return triFalse
118 case triFalse:
119 return triTrue
120 }
121 return triUndefined
122 case filterEquality:
123 return n.equality(e)
124 case filterSubstrings:
125 return n.substringMatch(e)
126 case filterGreaterOrEqual:
127 return n.ordering(e, func(c int) bool { return c >= 0 })
128 case filterLessOrEqual:
129 return n.ordering(e, func(c int) bool { return c <= 0 })
130 case filterPresent:
131 return n.present(e)
132 }
133 return triUndefined
134}
135
136func (n *filterNode) equality(e *entry) tri {
137 if n.rule == nil {
138 return triUndefined
139 }
140 want, ok := n.rule.normalize(string(n.value))
141 if !ok {
142 return triUndefined
143 }
144 for _, v := range e.attrs[n.rule.name] {
145 if got, ok := n.rule.normalize(v); ok && got == want {
146 return triTrue
147 }
148 }
149 return triFalse
150}
151
152func (n *filterNode) substringMatch(e *entry) tri {
153 if n.rule == nil || !n.rule.substrings {
154 return triUndefined
155 }
156 parts := make([]string, len(n.substrings))
157 for i, s := range n.substrings {
158 part, ok := n.rule.normalize(string(s.value))
159 if !ok {
160 return triUndefined
161 }
162 parts[i] = part
163 }
164 for _, v := range e.attrs[n.rule.name] {
165 if got, ok := n.rule.normalize(v); ok && n.matchSubstrings(got, parts) {
166 return triTrue
167 }
168 }
169 return triFalse
170}
171
172func (n *filterNode) matchSubstrings(v string, parts []string) bool {
173 for i, s := range n.substrings {
174 part := parts[i]
175 switch s.kind {
176 case substringInitial:
177 if !strings.HasPrefix(v, part) {
178 return false
179 }
180 v = v[len(part):]
181 case substringAny:
182 j := strings.Index(v, part)
183 if j < 0 {
184 return false
185 }
186 v = v[j+len(part):]
187 default:
188 return strings.HasSuffix(v, part)
189 }
190 }
191 return true
192}
193
194func (n *filterNode) ordering(e *entry, accept func(int) bool) tri {
195 if n.rule == nil || !n.rule.ordering {
196 return triUndefined
197 }
198 want := string(n.value)
199 if !validInteger(want) {
200 return triUndefined
201 }
202 for _, v := range e.attrs[n.rule.name] {
203 if validInteger(v) && accept(compareIntegers(v, want)) {
204 return triTrue
205 }
206 }
207 return triFalse
208}
209
210func (n *filterNode) present(e *entry) tri {
211 if n.rule == nil {
212 return triUndefined
213 }
214 if len(e.attrs[n.rule.name]) > 0 {
215 return triTrue
216 }
217 return triFalse
218}
219
220func asciiFold(s string) string {
221 b := []byte(s)
222 for i, ch := range b {
223 if 'A' <= ch && ch <= 'Z' {
224 b[i] = ch + ('a' - 'A')
225 }
226 }
227 return string(b)
228}
229
230func unicodeFold(s string) (string, bool) {
231 if !utf8.ValidString(s) {
232 return "", false
233 }
234 var b strings.Builder
235 b.Grow(len(s))
236 for _, r := range s {
237 b.WriteRune(foldRune(r))
238 }
239 return b.String(), true
240}
241
242func foldRune(r rune) rune {
243 least := r
244 for f := unicode.SimpleFold(r); f != r; f = unicode.SimpleFold(f) {
245 least = min(least, f)
246 }
247 return least
248}
249
250func validInteger(s string) bool {
251 digits := strings.TrimPrefix(s, "-")
252 if digits == "" {
253 return false
254 }
255 if digits[0] == '0' {
256 return s == "0"
257 }
258 for i := range len(digits) {
259 if !isDigit(digits[i]) {
260 return false
261 }
262 }
263 return true
264}
265
266func compareIntegers(a, b string) int {
267 aNegative, bNegative := a[0] == '-', b[0] == '-'
268 switch {
269 case aNegative && !bNegative:
270 return -1
271 case !aNegative && bNegative:
272 return 1
273 case aNegative:
274 return compareMagnitudes(b[1:], a[1:])
275 }
276 return compareMagnitudes(a, b)
277}
278
279func compareMagnitudes(a, b string) int {
280 if len(a) != len(b) {
281 return cmp.Compare(len(a), len(b))
282 }
283 return strings.Compare(a, b)
284}