router.bend
bend-kit-router@0.2.0.0 · 496 lines · 71 definitions
1
2import Base
3import bend-kit-router@0.2.0.0/target.bend as Target
4
5type Segment is Data:
6 Literal{text: String}
7 Parameter{name: String}
8
9type Entry<-A: Data> is Data:
10 Entry{method: String, pattern: String, action: A, groups: List<&2, U32>}
11
12type Handler<-A: Data> is Data:
13 Handler{method: String, pattern: String, segments: List<&2, Segment>, action: A}
14
15type Path<-A: Data> is Data:
16 Path{segments: List<&2, Segment>, handlers: List<&2, Handler<A>>, groups: List<&2, U32>, allow: String}
17
18type Table<-A: Data> is Data:
19 Table{paths: List<&2, Path<A>>, allow: String}
20
21type Error is Data:
22 InvalidPattern{pattern: String}
23 InvalidMethod{method: String}
24 Duplicate{method: String, pattern: String}
25 GroupConflict{pattern: String}
26 BadTarget{}
27
28type Choice<-A: Data> is Data:
29 Found{action: A, params: Map<&2, String>, groups: List<&2, U32>, method: String, pattern: String}
30 MethodMissing{groups: List<&2, U32>, allow: String}
31 Options{groups: List<&2, U32>, allow: String}
32 NotFound{}
33
34type Resolved<-A: Data> is Data:
35 Resolved{target: Target.Target, choice: Choice<A>}
36
37type Hidden is Data:
38 Hidden{pattern: String, methods: String}
39
40type Description is Data:
41 Description{method: String, pattern: String, groups: List<&2, U32>, hidden: List<&2, Hidden>}
42
43def scalar(+c: U32) -> Bool:
44 Bool.and(U32.is_le(c, 1114111), Bool.not(Target.between(c, 55296, 57343)))
45
46def literal.valid(s: String) -> Bool:
47 match s:
48 case SNil{}:
49 True{}
50 case SCon{Chr{+c}, t}:
51 Bool.and(Bool.and(scalar(c), Bool.and(U32.is_ne(c, 0), U32.is_ne(c, 47))), literal.valid(t))
52
53def name.tail(s: String) -> Bool:
54 match s:
55 case SNil{}:
56 True{}
57 case SCon{Chr{+c}, t}:
58 Bool.and(Bool.or(Target.alpha(c), Bool.or(Target.between(c, 48, 57), U32.is_eq(c, 95))), name.tail(t))
59
60def name.valid(s: String) -> Bool:
61 match s:
62 case SNil{}:
63 False{}
64 case SCon{Chr{+c}, t}:
65 Bool.and(Bool.or(Target.alpha(c), U32.is_eq(c, 95)), name.tail(t))
66
67def member(xs: List<&2, String>, +s: String) -> Bool:
68 match xs:
69 case Nil{}:
70 False{}
71 case h <> t:
72 Bool.or(String.eq(h, s), member(t, s))
73
74def pattern.segment(s: String, names: List<&2, String>) -> Maybe<&2, Segment>:
75 match s:
76 case SCon{Chr{58}, +t}:
77 Bool.pick(Maybe<&2, Segment>, Bool.and(name.valid(t), Bool.not(member(names, t))), Some{Parameter{t}}, None{})
78 case SNil{}:
79 Some{Literal{""}}
80 case SCon{+h, +t}:
81 +lit = {SCon{h, t} : String}
82 Bool.pick(Maybe<&2, Segment>, literal.valid(lit), Some{Literal{lit}}, None{})
83
84def pattern.names(segment: Segment, names: List<&2, String>) -> List<&2, String>:
85 match segment:
86 case Literal{text}:
87 names
88 case Parameter{name}:
89 name <> names
90
91def pattern.parts(xs: List<&2, String>, +names: List<&2, String>, acc: List<&2, Segment>) -> Maybe<&2, List<&2, Segment>>:
92 match xs:
93 case Nil{}:
94 Some{List.reverse(&2, Segment, acc)}
95 case "" <> Nil{}:
96 Some{List.reverse(&2, Segment, Literal{""} <> acc)}
97 case "" <> t:
98 None{}
99 case h <> t:
100 do Maybe<&2, List<&2, Segment>>:
101 seg : Segment <- pattern.segment(h, names)
102 +part : Segment = seg
103 pattern.parts(t, pattern.names(part, names), part <> acc)
104
105def pattern(s: String) -> Maybe<&2, List<&2, Segment>>:
106 match s:
107 case "/":
108 Some{Nil{}}
109 case SCon{Chr{47}, t}:
110 pattern.parts(String.split(t, '/'), Nil{}, Nil{})
111 case _:
112 None{}
113
114def token(+c: U32) -> Bool:
115 Bool.or(Target.alpha(c), Bool.or(Target.between(c, 48, 57), Bool.or(U32.is_eq(c, 33), Bool.or(Target.between(c, 35, 39), Bool.or(Target.between(c, 42, 43), Bool.or(Target.between(c, 45, 46), Bool.or(Target.between(c, 94, 96), Bool.or(U32.is_eq(c, 124), U32.is_eq(c, 126)))))))))
116
117def method.tail(s: String) -> Bool:
118 match s:
119 case SNil{}:
120 True{}
121 case SCon{Chr{c}, t}:
122 Bool.and(token(c), method.tail(t))
123
124def method.valid(s: String) -> Bool:
125 match s:
126 case SNil{}:
127 False{}
128 case SCon{Chr{c}, t}:
129 Bool.and(token(c), method.tail(t))
130
131def continue(ok: Bool, later: Unit -> Bool) -> Bool:
132 match ok:
133 case False{}:
134 False{}
135 case True{}:
136 later(Unit{})
137
138def matches(pat: List<&2, Segment>, got: List<&2, String>) -> Bool:
139 match pat got:
140 case Nil{} Nil{}:
141 True{}
142 case Literal{p} <> pt g <> gt:
143 continue(String.eq(p, g), u => matches(pt, gt))
144 case Parameter{name} <> pt +g <> gt:
145 continue(Bool.not(String.is_empty(g)), u => matches(pt, gt))
146 case _ _:
147 False{}
148
149def capture(pat: List<&2, Segment>, got: List<&2, String>, acc: Map<&2, String>) -> Map<&2, String>:
150 match pat got:
151 case Parameter{name} <> pt g <> gt:
152 capture(pt, gt, Map.set(&2, String, acc, name, g))
153 case Literal{text} <> pt g <> gt:
154 capture(pt, gt, acc)
155 case _ _:
156 acc
157
158def shape(a: List<&2, Segment>, b: List<&2, Segment>) -> Bool:
159 match a b:
160 case Nil{} Nil{}:
161 True{}
162 case Literal{x} <> at Literal{y} <> bt:
163 continue(String.eq(x, y), u => shape(at, bt))
164 case Parameter{x} <> at Parameter{y} <> bt:
165 shape(at, bt)
166 case _ _:
167 False{}
168
169def specific(a: List<&2, Segment>, b: List<&2, Segment>) -> Bool:
170 match a b:
171 case Literal{x} <> at Parameter{y} <> bt:
172 True{}
173 case Parameter{x} <> at Literal{y} <> bt:
174 False{}
175 case Literal{x} <> at Literal{y} <> bt:
176 specific(at, bt)
177 case Parameter{x} <> at Parameter{y} <> bt:
178 specific(at, bt)
179 case _ _:
180 False{}
181
182def groups.eq(a: List<&2, U32>, b: List<&2, U32>) -> Bool:
183 match a b:
184 case Nil{} Nil{}:
185 True{}
186 case x <> at y <> bt:
187 continue(U32.is_eq(x, y), u => groups.eq(at, bt))
188 case _ _:
189 False{}
190
191def handler.has(~A: Data, xs: List<&2, Handler<A>>, +method: String) -> Bool:
192 match xs:
193 case Nil{}:
194 False{}
195 case Handler{want, pattern, segments, action} <> t:
196 Bool.or(String.eq(want, method), handler.has(~A, t, method))
197
198def insert.merge(~A: Data, duplicate: Bool, same_groups: Bool, entry: Handler<A>, segments: List<&2, Segment>, handlers: List<&2, Handler<A>>, groups: List<&2, U32>, rest: List<&2, Path<A>>) -> Result<&2, &2, Error, List<&2, Path<A>>>:
199 match duplicate same_groups:
200 case True{} _:
201 Handler{method, pattern, ss, action} = entry
202 Fail{Duplicate{method, pattern}}
203 case False{} False{}:
204 Handler{method, pattern, ss, action} = entry
205 Fail{GroupConflict{pattern}}
206 case False{} True{}:
207 Done{Path{segments, entry <> handlers, groups, ""} <> rest}
208
209def insert.branch(~A: Data, same: Bool, segments: List<&2, Segment>, +handlers: List<&2, Handler<A>>, +old_groups: List<&2, U32>, allowed: String, tail: List<&2, Path<A>>, entry: Handler<A>, groups: List<&2, U32>, rest: Unit -> Result<&2, &2, Error, List<&2, Path<A>>>) -> Result<&2, &2, Error, List<&2, Path<A>>>:
210 match same:
211 case True{}:
212 Handler{+method, pattern, ss, action} = entry
213 insert.merge(~A, handler.has(~A, handlers, method), groups.eq(old_groups, groups), Handler{method, pattern, ss, action}, segments, handlers, old_groups, tail)
214 case False{}:
215 do Result<&2, &2, Error, List<&2, Path<A>>>:
216 remaining : List<&2, Path<A>> <- rest(Unit{})
217 return Path{segments, handlers, old_groups, allowed} <> remaining
218
219
220def insert(~A: Data, paths: List<&2, Path<A>>, +entry: Handler<A>, +groups: List<&2, U32>) -> Result<&2, &2, Error, List<&2, Path<A>>>:
221 match paths:
222 case Nil{}:
223 Handler{method, pattern, +ss, action} = entry
224 Done{[Path{ss, [Handler{method, pattern, ss, action}], groups, ""}]}
225 case Path{+ss, +handlers, +old_groups, +allow} <> +t:
226 Handler{+method, +pattern, +es, +action} = entry
227 candidate = {Handler{method, pattern, es, action} : Handler<A>}
228 insert.branch(~A, shape(ss, es), ss, handlers, old_groups, allow, t, candidate, groups, u => insert(~A, t, Handler{method, pattern, es, action}, groups))
229
230def method.prepend(get: Bool, method: String, tail: List<&2, String>) -> List<&2, String>:
231 match get:
232 case True{}:
233 method <> "HEAD" <> tail
234 case False{}:
235 method <> tail
236
237def method.names(~A: Data, xs: List<&2, Handler<A>>) -> List<&2, String>:
238 match xs:
239 case Nil{}:
240 ["OPTIONS"]
241 case Handler{+method, pattern, ss, action} <> t:
242 method.prepend(String.eq(method, "GET"), method, method.names(~A, t))
243
244def unique(xs: List<&2, String>, prev: String, +acc: List<&2, String>) -> List<&2, String>:
245 match xs:
246 case Nil{}:
247 List.reverse(&2, String, acc)
248 case +h <> t:
249 unique(t, h, Bool.pick(List<&2, String>, String.eq(h, prev), acc, h <> acc))
250
251def allow(xs: List<&2, String>) -> String:
252 String.join(unique(List.sort(~String, ~String.is_le, xs), "", Nil{}), ", ")
253
254def finish.paths(~A: Data, paths: List<&2, Path<A>>) -> List<&2, Path<A>>:
255 match paths:
256 case Nil{}:
257 Nil{}
258 case Path{segments, +handlers, groups, old_allow} <> t:
259 Path{segments, handlers, groups, allow(method.names(~A, handlers))} <> finish.paths(~A, t)
260
261def all.methods(~A: Data, paths: List<&2, Path<A>>) -> List<&2, String>:
262 match paths:
263 case Nil{}:
264 ["OPTIONS"]
265 case Path{ss, handlers, groups, allowed} <> t:
266 List.append(&2, String, method.names(~A, handlers), all.methods(~A, t))
267
268def prepare.pattern(~A: Data, parsed: Maybe<&2, List<&2, Segment>>, method: String, pattern: String, action: A, groups: List<&2, U32>, paths: List<&2, Path<A>>) -> Result<&2, &2, Error, List<&2, Path<A>>>:
269 match parsed:
270 case None{}:
271 Fail{InvalidPattern{pattern}}
272 case Some{ss}:
273 insert(~A, paths, Handler{method, pattern, ss, action}, groups)
274
275def prepare.entry(~A: Data, valid: Bool, entry: Entry<A>, paths: List<&2, Path<A>>) -> Result<&2, &2, Error, List<&2, Path<A>>>:
276 match valid:
277 case False{}:
278 Entry{method, p, action, groups} = entry
279 Fail{InvalidMethod{method}}
280 case True{}:
281 Entry{method, +p, action, groups} = entry
282 prepare.pattern(~A, pattern(p), method, p, action, groups, paths)
283
284def prepare.go(~A: Data, entries: List<&2, Entry<A>>, paths: List<&2, Path<A>>) -> Result<&2, &2, Error, Table<A>>:
285 match entries:
286 case Nil{}:
287 +prepared = finish.paths(~A, paths)
288 Done{Table{prepared, allow(all.methods(~A, prepared))}}
289 case Entry{+method, p, action, groups} <> t:
290 do Result<&2, &2, Error, Table<A>>:
291 next : List<&2, Path<A>> <- prepare.entry(~A, method.valid(method), Entry{method, p, action, groups}, paths)
292 prepare.go(~A, t, next)
293
294def prepare(~A: Data, entries: List<&2, Entry<A>>) -> Result<&2, &2, Error, Table<A>>:
295 prepare.go(~A, entries, Nil{})
296
297def best.compare(~A: Data, candidate: Path<A>, old: Path<A>) -> Maybe<&2, Path<A>>:
298 Path{+cs, +ch, +cg, +ca} = candidate
299 Path{+ss, +handlers, +groups, +allowed} = old
300 Bool.pick(Maybe<&2, Path<A>>, specific(cs, ss), Some{Path{cs, ch, cg, ca}}, Some{Path{ss, handlers, groups, allowed}})
301
302def best.pick(~A: Data, best: Maybe<&2, Path<A>>, candidate: Path<A>) -> Maybe<&2, Path<A>>:
303 match best:
304 case None{}:
305 Some{candidate}
306 case Some{old}:
307 best.compare(~A, candidate, old)
308
309def best.step(~A: Data, matched: Bool, candidate: Path<A>, best: Maybe<&2, Path<A>>) -> Maybe<&2, Path<A>>:
310 match matched:
311 case False{}:
312 best
313 case True{}:
314 best.pick(~A, best, candidate)
315
316
317def best(~A: Data, paths: List<&2, Path<A>>, +segments: List<&2, String>, acc: Maybe<&2, Path<A>>) -> Maybe<&2, Path<A>>:
318 match paths:
319 case Nil{}:
320 acc
321 case Path{+ss, handlers, groups, allowed} <> t:
322 best(~A, t, segments, best.step(~A, matches(ss, segments), Path{ss, handlers, groups, allowed}, acc))
323
324def handler.next(~A: Data, same: Bool, here: Handler<A>, later: Unit -> Maybe<&2, Handler<A>>) -> Maybe<&2, Handler<A>>:
325 match same:
326 case True{}:
327 Some{here}
328 case False{}:
329 later(Unit{})
330
331def handler(~A: Data, xs: List<&2, Handler<A>>, +method: String) -> Maybe<&2, Handler<A>>:
332 match xs:
333 case Nil{}:
334 None{}
335 case Handler{+want, pattern, ss, action} <> t:
336 handler.next(~A, String.eq(want, method), Handler{want, pattern, ss, action}, u => handler(~A, t, method))
337
338def chosen(~A: Data, hit: Maybe<&2, Handler<A>>, segments: List<&2, String>, +groups: List<&2, U32>, +allowed: String, options: Bool) -> Choice<A>:
339 match hit:
340 case Some{Handler{method, pattern, ss, action}}:
341 Found{action, capture(ss, segments, Map.new(&2, String)), groups, method, pattern}
342 case None{}:
343 Bool.pick(Choice<A>, options, Options{groups, allowed}, MethodMissing{groups, allowed})
344
345def choose.fallback(~A: Data, head: Bool, handlers: List<&2, Handler<A>>, method: String, segments: List<&2, String>, groups: List<&2, U32>, allowed: String) -> Choice<A>:
346 match head:
347 case True{}:
348 chosen(~A, handler(~A, handlers, "GET"), segments, groups, allowed, False{})
349 case False{}:
350 chosen(~A, None{}, segments, groups, allowed, String.eq(method, "OPTIONS"))
351
352def choose.method(~A: Data, direct: Maybe<&2, Handler<A>>, +handlers: List<&2, Handler<A>>, +method: String, segments: List<&2, String>, groups: List<&2, U32>, allowed: String) -> Choice<A>:
353 match direct:
354 case Some{h}:
355 chosen(~A, Some{h}, segments, groups, allowed, False{})
356 case None{}:
357 choose.fallback(~A, String.eq(method, "HEAD"), handlers, method, segments, groups, allowed)
358
359def choose.path(~A: Data, path: Maybe<&2, Path<A>>, +method: String, segments: List<&2, String>) -> Choice<A>:
360 match path:
361 case None{}:
362 NotFound{}
363 case Some{Path{ss, +handlers, groups, allowed}}:
364 choose.method(~A, handler(~A, handlers, method), handlers, method, segments, groups, allowed)
365
366def resolve.star(~A: Data, star: Bool, paths: List<&2, Path<A>>, allowed: String, target: Target.Target, method: String, +segments: List<&2, String>) -> Resolved<A>:
367 match star:
368 case True{}:
369 Resolved{target, Options{Nil{}, allowed}}
370 case False{}:
371 Resolved{target, choose.path(~A, best(~A, paths, segments, None{}), method, segments)}
372
373def resolve.target(~A: Data, parsed: Maybe<&2, Target.Target>, table: Table<A>, method: String) -> Result<&2, &2, Error, Resolved<A>>:
374 match parsed:
375 case None{}:
376 Fail{BadTarget{}}
377 case Some{Target.Target{+segments, +query, +authority, +star}}:
378 Table{paths, allowed} = table
379 Done{resolve.star(~A, star, paths, allowed, Target.Target{segments, query, authority, star}, method, segments)}
380
381def resolve(~A: Data, table: Table<A>, +method: String, target: String) -> Result<&2, &2, Error, Resolved<A>>:
382 resolve.target(~A, Target.parse(target, method), table, method)
383
384def route.match(ok: Bool, ss: List<&2, Segment>, got: List<&2, String>) -> Maybe<&2, Map<&2, String>>:
385 match ok:
386 case False{}:
387 None{}
388 case True{}:
389 Some{capture(ss, got, Map.new(&2, String))}
390
391def route.path(star: Bool, +ss: List<&2, Segment>, +got: List<&2, String>) -> Maybe<&2, Map<&2, String>>:
392 match star:
393 case True{}:
394 None{}
395 case False{}:
396 route.match(matches(ss, got), ss, got)
397
398def route.target(parsed: Maybe<&2, Target.Target>, +ss: List<&2, Segment>) -> Maybe<&2, Map<&2, String>>:
399 match parsed:
400 case None{}:
401 None{}
402 case Some{Target.Target{+got, query, authority, star}}:
403 route.path(star, ss, got)
404
405def route.pattern(parsed: Maybe<&2, List<&2, Segment>>, path: String, method: String) -> Maybe<&2, Map<&2, String>>:
406 match parsed:
407 case None{}:
408 None{}
409 case Some{ss}:
410 route.target(Target.parse(path, method), ss)
411
412def route.method(same: Bool, p: String, path: String, method: String) -> Maybe<&2, Map<&2, String>>:
413 match same:
414 case False{}:
415 None{}
416 case True{}:
417 route.pattern(pattern(p), path, method)
418
419def route(want: String, +method: String, pattern: String, path: String) -> Maybe<&2, Map<&2, String>>:
420 route.method(String.eq(want, method), pattern, path, method)
421
422def overlap(a: List<&2, Segment>, b: List<&2, Segment>) -> Bool:
423 match a b:
424 case Nil{} Nil{}:
425 True{}
426 case Literal{x} <> at Literal{y} <> bt:
427 continue(String.eq(x, y), u => overlap(at, bt))
428 case Literal{x} <> at Parameter{y} <> bt:
429 continue(Bool.not(String.is_empty(x)), u => overlap(at, bt))
430 case Parameter{x} <> at Literal{y} <> bt:
431 continue(Bool.not(String.is_empty(y)), u => overlap(at, bt))
432 case Parameter{x} <> at Parameter{y} <> bt:
433 overlap(at, bt)
434 case _ _:
435 False{}
436
437def unavailable.prepend(keep: Bool, h: String, tail: List<&2, String>) -> List<&2, String>:
438 match keep:
439 case False{}:
440 tail
441 case True{}:
442 h <> tail
443
444def unavailable(xs: List<&2, String>, +present: List<&2, String>) -> List<&2, String>:
445 match xs:
446 case Nil{}:
447 Nil{}
448 case +h <> t:
449 unavailable.prepend(Bool.not(member(present, h)), h, unavailable(t, present))
450
451def hidden.add(empty: Bool, pattern: String, methods: String, tail: List<&2, Hidden>) -> List<&2, Hidden>:
452 match empty:
453 case True{}:
454 tail
455 case False{}:
456 Hidden{pattern, methods} <> tail
457
458def hidden.handlers(~A: Data, handlers: List<&2, Handler<A>>, +present: List<&2, String>, tail: List<&2, Hidden>) -> List<&2, Hidden>:
459 match handlers:
460 case Nil{}:
461 tail
462 case Handler{+method, +pattern, ss, action} <> rest:
463 +missing = allow(unavailable(method.prepend(String.eq(method, "GET"), method, Nil{}), present))
464 hidden.add(String.is_empty(missing), pattern, missing, hidden.handlers(~A, rest, present, tail))
465
466def hidden.path(~A: Data, hides: Bool, handlers: List<&2, Handler<A>>, present: List<&2, String>, tail: List<&2, Hidden>) -> List<&2, Hidden>:
467 match hides:
468 case False{}:
469 tail
470 case True{}:
471 hidden.handlers(~A, handlers, present, tail)
472
473def hidden.scan(~A: Data, paths: List<&2, Path<A>>, +segments: List<&2, Segment>, +methods: List<&2, String>) -> List<&2, Hidden>:
474 match paths:
475 case Nil{}:
476 Nil{}
477 case Path{+ss, handlers, groups, allowed} <> t:
478 hidden.path(~A, Bool.and(specific(segments, ss), overlap(segments, ss)), handlers, methods, hidden.scan(~A, t, segments, methods))
479
480def description.handlers(~A: Data, handlers: List<&2, Handler<A>>, +groups: List<&2, U32>, +hidden: List<&2, Hidden>) -> List<&2, Description>:
481 match handlers:
482 case Nil{}:
483 Nil{}
484 case Handler{method, pattern, ss, action} <> t:
485 Description{method, pattern, groups, hidden} <> description.handlers(~A, t, groups, hidden)
486
487def description.paths(~A: Data, paths: List<&2, Path<A>>, +all: List<&2, Path<A>>) -> List<&2, Description>:
488 match paths:
489 case Nil{}:
490 Nil{}
491 case Path{segments, +handlers, groups, allowed} <> t:
492 List.append(&2, Description, description.handlers(~A, handlers, groups, hidden.scan(~A, all, segments, method.names(~A, handlers))), description.paths(~A, t, all))
493
494def describe(~A: Data, table: Table<A>) -> List<&2, Description>:
495 Table{+paths, allowed} = table
496 description.paths(~A, paths, paths)