url.bend
bend-kit-url@0.4.0.0 · 518 lines · 0 definitions
1# URL parsing, resolution, and percent-encoding (RFC 3986). Source: https://github.com/paymog/bend-kit/tree/main/url
2import Base
3
4# origin-form /path[?k=v] with RFC 3986 percent-encoding.
5
6type Url is Data:
7 Url{path: String, query: Map<&2, String>}
8
9def unreserved(+c: U32) -> Bool:
10 Bool.or(Bool.and(U32.is_le(65, c), U32.is_le(c, 90)), Bool.or(Bool.and(U32.is_le(97, c), U32.is_le(c, 122)), Bool.or(Bool.and(U32.is_le(48, c), U32.is_le(c, 57)), Bool.or(U32.is_eq(c, 45), Bool.or(U32.is_eq(c, 46), Bool.or(U32.is_eq(c, 95), U32.is_eq(c, 126)))))))
11
12def path_ok(+c: U32) -> Bool:
13 Bool.or(unreserved(c), U32.is_eq(c, 47))
14
15def hexn(+n: U32) -> U32:
16 Bool.pick(U32, U32.is_le(n, 9), (48 + n : U32), (55 + n : U32))
17
18def hexhi(+n: U32) -> U32:
19 U32.div(n, 16)
20
21def hexlo(+n: U32) -> U32:
22 U32.mod(n, 16)
23
24def pct.enc.push(+c: U32, acc: String, keep: Bool) -> String:
25 match keep:
26 case True{}:
27 SCon{Chr{c}, acc}
28 case False{}:
29 SCon{Chr{hexn(hexlo(c))}, SCon{Chr{hexn(hexhi(c))}, SCon{Chr{37}, acc}}}
30
31def pct.enc.path(s: String, acc: String) -> String:
32 match s:
33 case SNil{}:
34 String.reverse(acc)
35 case SCon{Chr{+c}, t}:
36 pct.enc.path(t, pct.enc.push(c, acc, path_ok(c)))
37
38def pct.enc.query(s: String, acc: String) -> String:
39 match s:
40 case SNil{}:
41 String.reverse(acc)
42 case SCon{Chr{+c}, t}:
43 pct.enc.query(t, pct.enc.push(c, acc, unreserved(c)))
44
45def pct.encode_path(s: String) -> String:
46 pct.enc.path(s, SNil{})
47
48def pct.encode_q(s: String) -> String:
49 pct.enc.query(s, SNil{})
50
51def unhex.H(c: U32, hex: Bool) -> Maybe<&2, U32>:
52 match hex:
53 case True{}:
54 Some{(c - 55 : U32)}
55 case False{}:
56 None{}
57
58def unhex.h(+c: U32, lo: Bool) -> Maybe<&2, U32>:
59 match lo:
60 case True{}:
61 Some{(c - 87 : U32)}
62 case False{}:
63 unhex.H(c, Bool.and(U32.is_le(65, c), U32.is_le(c, 70)))
64
65def unhex.d(+c: U32, dec: Bool, lo: Bool) -> Maybe<&2, U32>:
66 match dec:
67 case True{}:
68 Some{(c - 48 : U32)}
69 case False{}:
70 unhex.h(c, lo)
71
72def unhex(+c: U32) -> Maybe<&2, U32>:
73 unhex.d(c, Bool.and(U32.is_le(48, c), U32.is_le(c, 57)), Bool.and(U32.is_le(97, c), U32.is_le(c, 102)))
74
75# Lit: plain bytes. Hi: after "%". Lo: after "%" and one hex digit. Bad: never decodes.
76type Pd is Data:
77 PdLit{}
78 PdHi{}
79 PdLo{hi: U32}
80 PdBad{}
81
82def pct.lit(+c: U32, racc: String, pct: Bool) -> Pd & String:
83 match pct:
84 case True{}:
85 (PdHi{}, racc)
86 case False{}:
87 (PdLit{}, SCon{Chr{c}, racc})
88
89def pct.hi(m: Maybe<&2, U32>, racc: String) -> Pd & String:
90 match m:
91 case None{}:
92 (PdBad{}, racc)
93 case Some{x}:
94 (PdLo{x}, racc)
95
96def pct.lo(+x: U32, m: Maybe<&2, U32>, racc: String) -> Pd & String:
97 match m:
98 case None{}:
99 (PdBad{}, racc)
100 case Some{y}:
101 (PdLit{}, SCon{Chr{(x * 16 + y : U32)}, racc})
102
103def pct.byte(h: Char) -> U32:
104 Chr{c} = h
105 c
106
107def pct.end(st: Pd, racc: String) -> Maybe<&2, String>:
108 match st:
109 case PdLit{}:
110 Some{String.reverse(racc)}
111 case PdHi{}:
112 None{}
113 case PdLo{x}:
114 None{}
115 case PdBad{}:
116 None{}
117
118def pct.step(st: Pd, +c: U32, racc: String) -> Pd & String:
119 match st:
120 case PdLit{}:
121 pct.lit(c, racc, U32.is_eq(c, 37))
122 case PdHi{}:
123 pct.hi(unhex(c), racc)
124 case PdLo{+x}:
125 pct.lo(x, unhex(c), racc)
126 case PdBad{}:
127 (PdBad{}, racc)
128
129def pct.end.of(sr: Pd & String) -> Maybe<&2, String>:
130 (st, racc) = sr
131 pct.end(st, racc)
132
133def pct.step.of(sr: Pd & String, +c: U32) -> Pd & String:
134 (st, racc) = sr
135 pct.step(st, c, racc)
136
137def pct.decode.go(s: String, sr: Pd & String) -> Maybe<&2, String>:
138 match s:
139 case SNil{}:
140 pct.end.of(sr)
141 case SCon{h, t}:
142 pct.decode.go(t, pct.step.of(sr, pct.byte(h)))
143
144def pct.decode(s: String) -> Maybe<&2, String>:
145 pct.decode.go(s, (PdLit{}, ""))
146
147# Bool.pick evaluates both arms; a split that recursed inside it would reverse acc at every byte.
148def take.cut(acc: String, rest: String) -> String & String:
149 (String.reverse(String.drop(acc, 1n)), rest)
150
151# hit: the last char pushed onto acc was the stop char.
152def take_to.go(s: String, +stop: U32, acc: String, hit: Bool) -> String & String:
153 match s:
154 case SNil{}:
155 match hit:
156 case True{}:
157 take.cut(acc, SNil{})
158 case False{}:
159 (String.reverse(acc), SNil{})
160 case SCon{Chr{+c}, t}:
161 match hit:
162 case True{}:
163 take.cut(acc, SCon{Chr{c}, t})
164 case False{}:
165 take_to.go(t, stop, SCon{Chr{c}, acc}, U32.is_eq(c, stop))
166
167# (text before the first stop char, text after it)
168def take_to(s: String, stop: U32) -> String & String:
169 take_to.go(s, stop, SNil{}, False{})
170
171def pair(kv: String) -> String & String:
172 take_to(kv, 61)
173
174def qput.decv(m: Map<&2, String>, key: String, v: Maybe<&2, String>) -> Map<&2, String>:
175 match v:
176 case None{}:
177 m
178 case Some{val}:
179 Map.set(&2, String, m, key, val)
180
181def qput.dec(m: Map<&2, String>, k: Maybe<&2, String>, v: Maybe<&2, String>) -> Map<&2, String>:
182 match k:
183 case None{}:
184 m
185 case Some{key}:
186 qput.decv(m, key, v)
187
188def qput.kv(m: Map<&2, String>, kv: String & String) -> Map<&2, String>:
189 (k, v) = kv
190 qput.dec(m, pct.decode(k), pct.decode(v))
191
192def qput(m: Map<&2, String>, kv: String) -> Map<&2, String>:
193 qput.kv(m, pair(kv))
194
195def qfold(xs: List<&2, String>, m: Map<&2, String>) -> Map<&2, String>:
196 match xs:
197 case Nil{}:
198 m
199 case Con{h, t}:
200 qfold(t, qput(m, h))
201
202def parse.q(path: String, rest: String, hasq: Bool) -> Maybe<&2, Url>:
203 match hasq:
204 case False{}:
205 Some{Url{path, Map.new(&2, String)}}
206 case True{}:
207 Some{Url{path, qfold(String.split(rest, '&'), Map.new(&2, String))}}
208
209def parse.path(path: Maybe<&2, String>, +rest: String) -> Maybe<&2, Url>:
210 match path:
211 case None{}:
212 None{}
213 case Some{p}:
214 parse.q(p, rest, Bool.not(String.is_empty(rest)))
215
216def parse.split(pr: String & String) -> Maybe<&2, Url>:
217 (path, +rest) = pr
218 parse.path(pct.decode(path), rest)
219
220def parse.ok(+s: String, ok: Bool) -> Maybe<&2, Url>:
221 match ok:
222 case False{}:
223 None{}
224 case True{}:
225 parse.split(take_to(s, 63))
226
227def parse(+s: String) -> Maybe<&2, Url>:
228 parse.ok(s, String.starts_with(s, "/"))
229
230def enc.pairs.go(xs: List<&2, Sigma<&2, &2, String, _ => String>>, acc: String) -> String:
231 match xs:
232 case Nil{}:
233 acc
234 case (k, v) <> t:
235 enc.pairs.go(t, acc ++ ("&" ++ pct.encode_q(k) ++ "=" ++ pct.encode_q(v)))
236
237def enc.pairs(m: Map<&2, String>) -> String:
238 enc.pairs.go(Map.to_list(&2, String, m), "")
239
240def encode.q(path: String, q: String, empty: Bool) -> String:
241 match empty:
242 case True{}:
243 path
244 case False{}:
245 path ++ "?" ++ String.drop(q, 1n)
246
247def encode.go(path: String, +q: String) -> String:
248 encode.q(path, q, String.is_empty(q))
249
250def encode(u: Url) -> String:
251 Url{path, query} = u
252 encode.go(pct.encode_path(path), enc.pairs(query))
253
254def form.drop(q: String, empty: Bool) -> String:
255 match empty:
256 case True{}:
257 ""
258 case False{}:
259 String.drop(q, 1n)
260
261def form.go(+q: String) -> String:
262 form.drop(q, String.is_empty(q))
263
264# application/x-www-form-urlencoded. Space is %20.
265def form(m: Map<&2, String>) -> String:
266 form.go(enc.pairs(m))
267
268# Absolute http(s) URLs (RFC 3986 §3) for clients.
269# ---------------------------------------------
270
271# target is the RFC 9112 §3.2.1 origin-form: path (never empty) and query, no fragment.
272type Abs is Data:
273 Abs{scheme: String, host: String, port: U32, target: String}
274
275def has(s: String, +c: U32) -> Bool:
276 match s:
277 case SNil{}:
278 False{}
279 case SCon{Chr{d}, t}:
280 Bool.or(U32.is_eq(d, c), has(t, c))
281
282def auth_end(+c: U32) -> Bool:
283 Bool.or(U32.is_eq(c, 47), Bool.or(U32.is_eq(c, 63), U32.is_eq(c, 35)))
284
285def take.back(acc: String, rest: String) -> String & String:
286 match acc:
287 case SNil{}:
288 (SNil{}, rest)
289 case SCon{x, a2}:
290 (String.reverse(a2), SCon{x, rest})
291
292# §3.2: the authority runs to the first "/", "?" or "#".
293def take_auth.go(s: String, acc: String, hit: Bool) -> String & String:
294 match s:
295 case SNil{}:
296 match hit:
297 case True{}:
298 take.back(acc, SNil{})
299 case False{}:
300 (String.reverse(acc), SNil{})
301 case SCon{Chr{+c}, t}:
302 match hit:
303 case True{}:
304 take.back(acc, SCon{Chr{c}, t})
305 case False{}:
306 take_auth.go(t, SCon{Chr{c}, acc}, auth_end(c))
307
308def default_port(+scheme: String) -> Maybe<&2, U32>:
309 Bool.pick(Maybe<&2, U32>, String.eq(scheme, "http"), Some{80}, Bool.pick(Maybe<&2, U32>, String.eq(scheme, "https"), Some{443}, None{}))
310
311def abs.target(+pq: String) -> String:
312 Bool.pick(String, String.starts_with(pq, "/"), pq, "/" ++ pq)
313
314def abs.fst(ab: String & String) -> String:
315 (a, b) = ab
316 a
317
318# §3.5: the fragment is for the client; it never goes on the wire.
319def abs.build(scheme: String, host: String, port: Maybe<&2, U32>, rest: String) -> Maybe<&2, Abs>:
320 match port:
321 case None{}:
322 None{}
323 case Some{p}:
324 Some{Abs{scheme, host, p, abs.target(abs.fst(take_to(rest, 35)))}}
325
326def abs.port.num(n: Maybe<&2, U32>) -> Maybe<&2, U32>:
327 match n:
328 case None{}:
329 None{}
330 case Some{+p}:
331 Bool.pick(Maybe<&2, U32>, U32.is_le(p, 65535), Some{p}, None{})
332
333# §3.2.3: an empty port means the scheme's default.
334def abs.port(+ps: String, dflt: Maybe<&2, U32>) -> Maybe<&2, U32>:
335 Bool.pick(Maybe<&2, U32>, String.is_empty(ps), dflt, abs.port.num(U32.read(ps)))
336
337def abs.hostok(scheme: String, host: String, port: Maybe<&2, U32>, rest: String, ok: Bool) -> Maybe<&2, Abs>:
338 match ok:
339 case False{}:
340 None{}
341 case True{}:
342 abs.build(scheme, host, port, rest)
343
344# §3.2.2: hosts are case-insensitive. IPv6 literals are refused (IPv4-only runtime).
345def abs.hostport(scheme: String, dflt: Maybe<&2, U32>, hp: String & String, rest: String) -> Maybe<&2, Abs>:
346 (+host, ps) = hp
347 abs.hostok(scheme, String.to_lower(host), abs.port(ps, dflt), rest, Bool.not(Bool.or(String.is_empty(host), String.starts_with(host, "["))))
348
349# WHATWG fetch refuses URLs that carry credentials (user:pass@).
350def abs.auth.if(+scheme: String, auth: String, rest: String, creds: Bool) -> Maybe<&2, Abs>:
351 match creds:
352 case True{}:
353 None{}
354 case False{}:
355 abs.hostport(scheme, default_port(scheme), take_to(auth, 58), rest)
356
357def abs.auth(scheme: String, ar: String & String) -> Maybe<&2, Abs>:
358 (+auth, rest) = ar
359 abs.auth.if(scheme, auth, rest, has(auth, 64))
360
361def abs.slashes(scheme: String, +rest: String, ok: Bool) -> Maybe<&2, Abs>:
362 match ok:
363 case False{}:
364 None{}
365 case True{}:
366 abs.auth(String.to_lower(scheme), take_auth.go(String.drop(rest, 2n), SNil{}, False{}))
367
368def abs.scheme(sr: String & String) -> Maybe<&2, Abs>:
369 (scheme, +rest) = sr
370 abs.slashes(scheme, rest, String.starts_with(rest, "//"))
371
372# scheme://host[:port][/path][?query][#fragment]
373def absolute(s: String) -> Maybe<&2, Abs>:
374 abs.scheme(take_to(s, 58))
375
376def abs.port.dflt(m: Maybe<&2, U32>) -> U32:
377 match m:
378 case None{}:
379 0
380 case Some{p}:
381 p
382
383# RFC 9110 §7.2: the Host field; the default port may be left out.
384def host_field(a: Abs) -> String:
385 Abs{+scheme, +host, +port, target} = a
386 Bool.pick(String, U32.is_eq(port, abs.port.dflt(default_port(scheme))), host, host ++ ":" ++ U32.show(port))
387
388# Reference resolution (RFC 3986 §5.2) for Location headers.
389# ----------------------------------------------------------
390
391def dots.pop(stack: List<&2, String>) -> List<&2, String>:
392 match stack:
393 case Nil{}:
394 Nil{}
395 case Con{h, t}:
396 t
397
398def dots.push(seg: String, stack: List<&2, String>, dot: Bool, up: Bool) -> List<&2, String>:
399 match dot:
400 case True{}:
401 stack
402 case False{}:
403 match up:
404 case True{}:
405 dots.pop(stack)
406 case False{}:
407 Con{seg, stack}
408
409def dots.join(xs: List<&2, String>, acc: String) -> String:
410 match xs:
411 case Nil{}:
412 acc
413 case Con{h, t}:
414 dots.join(t, "/" ++ h ++ acc)
415
416# stack is reversed; trail: the last segment was "." or "..", so a "/" ends the path.
417def dots.go(segs: List<&2, String>, stack: List<&2, String>, trail: Bool) -> String:
418 match segs:
419 case Nil{}:
420 +out = dots.join(stack, "")
421 Bool.pick(String, Bool.and(trail, Bool.not(String.is_empty(out))), out ++ "/", Bool.pick(String, String.is_empty(out), "/", out))
422 case Con{+seg, t}:
423 +dot = String.eq(seg, ".")
424 +up = String.eq(seg, "..")
425 dots.go(t, dots.push(seg, stack, dot, up), Bool.or(dot, up))
426
427def dots.abs(xs: List<&2, String>) -> String:
428 match xs:
429 case Nil{}:
430 "/"
431 case Con{lead, t}:
432 dots.go(t, Nil{}, False{})
433
434# §5.2.4 for an absolute path: "." and ".." segments go away.
435def remove_dots(path: String) -> String:
436 dots.abs(String.split(path, '/'))
437
438def dir.go(s: String, +acc: String, last: String) -> String:
439 match s:
440 case SNil{}:
441 String.reverse(last)
442 case SCon{Chr{+c}, t}:
443 +acc2 = {SCon{Chr{c}, acc} : String}
444 dir.go(t, acc2, Bool.pick(String, U32.is_eq(c, 47), acc2, last))
445
446# §5.2.3: the base path up to and including its last "/".
447def dir(path: String) -> String:
448 dir.go(path, SNil{}, SNil{})
449
450def with_q(path: String, q: String, has_q: Bool) -> String:
451 match has_q:
452 case True{}:
453 path ++ "?" ++ q
454 case False{}:
455 path
456
457def res.build(scheme: String, host: String, port: U32, path: String, q: String, has_q: Bool) -> Maybe<&2, Abs>:
458 Some{Abs{scheme, host, port, with_q(path, q, has_q)}}
459
460# A path, its query, and whether a "?" was present at all.
461type PQ is Data:
462 PQ{path: String, q: String, has_q: Bool}
463
464def res.pq(pq: String & String, has_q: Bool) -> PQ:
465 (p, q) = pq
466 PQ{p, q, has_q}
467
468def res.ref(+r: String) -> PQ:
469 res.pq(take_to(r, 63), has(r, 63))
470
471# §5.2.2: an empty path keeps the base path (and its query unless one is given);
472# "/..." replaces the path; anything else merges with the base directory.
473def res.rel.go(+scheme: String, +host: String, +port: U32, +bpath: String, +bq: String, +bhas: Bool, +rp: String, +q: String, +rhas: Bool) -> Maybe<&2, Abs>:
474 Bool.pick(Maybe<&2, Abs>, String.is_empty(rp),
475 Bool.pick(Maybe<&2, Abs>, rhas, res.build(scheme, host, port, bpath, q, True{}), res.build(scheme, host, port, bpath, bq, bhas)),
476 res.build(scheme, host, port, remove_dots(Bool.pick(String, String.starts_with(rp, "/"), rp, dir(bpath) ++ rp)), q, rhas))
477
478def res.rel(scheme: String, host: String, port: U32, bpath: String, bq: String, bhas: Bool, r: PQ) -> Maybe<&2, Abs>:
479 PQ{rp, q, rhas} = r
480 res.rel.go(scheme, host, port, bpath, bq, bhas, rp, q, rhas)
481
482def res.base(+r: String, b: PQ, a: Abs) -> Maybe<&2, Abs>:
483 PQ{bpath, bq, bhas} = b
484 Abs{scheme, host, port, target} = a
485 res.rel(scheme, host, port, bpath, bq, bhas, res.ref(abs.fst(take_to(r, 35))))
486
487def res.local(+r: String, a: Abs) -> Maybe<&2, Abs>:
488 Abs{+scheme, +host, +port, +target} = a
489 res.base(r, res.ref(target), Abs{scheme, host, port, target})
490
491def abs.scheme_of(a: Abs) -> String:
492 Abs{scheme, host, port, target} = a
493 scheme
494
495def res.net(+r: String, a: Abs, net: Bool) -> Maybe<&2, Abs>:
496 match net:
497 case True{}:
498 absolute(abs.scheme_of(a) ++ ":" ++ r)
499 case False{}:
500 res.local(r, a)
501
502def scheme.ok(s: String) -> Bool:
503 match s:
504 case SNil{}:
505 True{}
506 case SCon{Chr{+c}, t}:
507 Bool.and(Bool.or(Bool.or(Bool.and(U32.is_le(97, c), U32.is_le(c, 122)), Bool.and(U32.is_le(65, c), U32.is_le(c, 90))), Bool.or(Bool.and(U32.is_le(48, c), U32.is_le(c, 57)), Bool.or(U32.is_eq(c, 43), Bool.or(U32.is_eq(c, 45), U32.is_eq(c, 46))))), scheme.ok(t))
508
509# §3.1: a ":" before any "/", "?" or "#" with a valid scheme name before it.
510def abs.has_scheme(+pre: String, colon: Bool) -> Bool:
511 Bool.and(colon, Bool.and(Bool.not(String.is_empty(pre)), scheme.ok(pre)))
512# ref against base: absolute http(s) URLs as is, "//host...", "/path", "?q",
513# or a relative path. Other schemes are None (fetch cannot follow them).
514def resolve(a: Abs, +ref: String) -> Maybe<&2, Abs>:
515 +low = String.to_lower(ref)
516 Bool.pick(Maybe<&2, Abs>, Bool.or(String.starts_with(low, "http://"), String.starts_with(low, "https://")), absolute(ref),
517 Bool.pick(Maybe<&2, Abs>, abs.has_scheme(abs.fst(take_to(ref, 58)), has(ref, 58)), None{}, res.net(ref, a, String.starts_with(ref, "//"))))
518