url.bend

bend-kit-url@0.4.1.0 · 568 lines · 97 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# Bracket-free host in Abs; only the authority and Host field carry brackets.
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
349def abs.ipv6.ch(+c: U32) -> Bool:
350  Bool.or(U32.is_eq(c, 58), Bool.or(U32.is_eq(c, 46),
351    Bool.or(Bool.and(U32.is_le(48, c), U32.is_le(c, 57)),
352      Bool.or(Bool.and(U32.is_le(65, c), U32.is_le(c, 70)),
353        Bool.and(U32.is_le(97, c), U32.is_le(c, 102))))))
354
355def abs.ipv6.chars(s: String) -> Bool:
356  match s:
357    case SNil{}:
358      True{}
359    case SCon{Chr{+c}, t}:
360      Bool.and(abs.ipv6.ch(c), abs.ipv6.chars(t))
361
362def abs.ipv6.port(scheme: String, dflt: Maybe<&2, U32>, +host: String, suffix: String, rest: String) -> Maybe<&2, Abs>:
363  match suffix:
364    case SNil{}:
365      abs.hostok(scheme, String.to_lower(host), dflt, rest, Bool.and(has(host, 58), abs.ipv6.chars(host)))
366    case SCon{Chr{58}, ps}:
367      abs.hostok(scheme, String.to_lower(host), abs.port(ps, dflt), rest, Bool.and(has(host, 58), abs.ipv6.chars(host)))
368    case SCon{Chr{c}, t}:
369      None{}
370
371def abs.ipv6.split(scheme: String, dflt: Maybe<&2, U32>, hp: String & String, rest: String) -> Maybe<&2, Abs>:
372  (host, suffix) = hp
373  abs.ipv6.port(scheme, dflt, host, suffix, rest)
374
375def abs.ipv6.auth(+scheme: String, host: String, rest: String, closed: Bool) -> Maybe<&2, Abs>:
376  match closed:
377    case False{}:
378      None{}
379    case True{}:
380      abs.ipv6.split(scheme, default_port(scheme), take_to(host, 93), rest)
381
382def abs.auth.addr(auth: String, +scheme: String, rest: String) -> Maybe<&2, Abs>:
383  match auth:
384    case SCon{Chr{91}, +host}:
385      abs.ipv6.auth(scheme, host, rest, has(host, 93))
386    case SNil{}:
387      None{}
388    case SCon{Chr{c}, tail}:
389      abs.hostport(scheme, default_port(scheme), take_to(SCon{Chr{c}, tail}, 58), rest)
390
391# WHATWG fetch refuses URLs that carry credentials (user:pass@).
392def abs.auth.if(+scheme: String, auth: String, rest: String, creds: Bool) -> Maybe<&2, Abs>:
393  match creds:
394    case True{}:
395      None{}
396    case False{}:
397      abs.auth.addr(auth, scheme, rest)
398
399def abs.auth(scheme: String, ar: String & String) -> Maybe<&2, Abs>:
400  (+auth, rest) = ar
401  abs.auth.if(scheme, auth, rest, has(auth, 64))
402
403def abs.slashes(scheme: String, +rest: String, ok: Bool) -> Maybe<&2, Abs>:
404  match ok:
405    case False{}:
406      None{}
407    case True{}:
408      abs.auth(String.to_lower(scheme), take_auth.go(String.drop(rest, 2n), SNil{}, False{}))
409
410def abs.scheme(sr: String & String) -> Maybe<&2, Abs>:
411  (scheme, +rest) = sr
412  abs.slashes(scheme, rest, String.starts_with(rest, "//"))
413
414# scheme://host[:port][/path][?query][#fragment]
415def absolute(s: String) -> Maybe<&2, Abs>:
416  abs.scheme(take_to(s, 58))
417
418def abs.port.dflt(m: Maybe<&2, U32>) -> U32:
419  match m:
420    case None{}:
421      0
422    case Some{p}:
423      p
424
425# RFC 9110 §7.2: bracket an IPv6 literal in Host, and omit the default port.
426def host_field.wrap(host: String, ipv6: Bool) -> String:
427  match ipv6:
428    case True{}:
429      "[" ++ host ++ "]"
430    case False{}:
431      host
432
433def host_field(a: Abs) -> String:
434  Abs{+scheme, +host, +port, target} = a
435  +field = host_field.wrap(host, has(host, 58))
436  Bool.pick(String, U32.is_eq(port, abs.port.dflt(default_port(scheme))), field, field ++ ":" ++ U32.show(port))
437
438# Reference resolution (RFC 3986 §5.2) for Location headers.
439# ----------------------------------------------------------
440
441def dots.pop(stack: List<&2, String>) -> List<&2, String>:
442  match stack:
443    case Nil{}:
444      Nil{}
445    case Con{h, t}:
446      t
447
448def dots.push(seg: String, stack: List<&2, String>, dot: Bool, up: Bool) -> List<&2, String>:
449  match dot:
450    case True{}:
451      stack
452    case False{}:
453      match up:
454        case True{}:
455          dots.pop(stack)
456        case False{}:
457          Con{seg, stack}
458
459def dots.join(xs: List<&2, String>, acc: String) -> String:
460  match xs:
461    case Nil{}:
462      acc
463    case Con{h, t}:
464      dots.join(t, "/" ++ h ++ acc)
465
466# stack is reversed; trail: the last segment was "." or "..", so a "/" ends the path.
467def dots.go(segs: List<&2, String>, stack: List<&2, String>, trail: Bool) -> String:
468  match segs:
469    case Nil{}:
470      +out = dots.join(stack, "")
471      Bool.pick(String, Bool.and(trail, Bool.not(String.is_empty(out))), out ++ "/", Bool.pick(String, String.is_empty(out), "/", out))
472    case Con{+seg, t}:
473      +dot = String.eq(seg, ".")
474      +up = String.eq(seg, "..")
475      dots.go(t, dots.push(seg, stack, dot, up), Bool.or(dot, up))
476
477def dots.abs(xs: List<&2, String>) -> String:
478  match xs:
479    case Nil{}:
480      "/"
481    case Con{lead, t}:
482      dots.go(t, Nil{}, False{})
483
484# §5.2.4 for an absolute path: "." and ".." segments go away.
485def remove_dots(path: String) -> String:
486  dots.abs(String.split(path, '/'))
487
488def dir.go(s: String, +acc: String, last: String) -> String:
489  match s:
490    case SNil{}:
491      String.reverse(last)
492    case SCon{Chr{+c}, t}:
493      +acc2 = {SCon{Chr{c}, acc} : String}
494      dir.go(t, acc2, Bool.pick(String, U32.is_eq(c, 47), acc2, last))
495
496# §5.2.3: the base path up to and including its last "/".
497def dir(path: String) -> String:
498  dir.go(path, SNil{}, SNil{})
499
500def with_q(path: String, q: String, has_q: Bool) -> String:
501  match has_q:
502    case True{}:
503      path ++ "?" ++ q
504    case False{}:
505      path
506
507def res.build(scheme: String, host: String, port: U32, path: String, q: String, has_q: Bool) -> Maybe<&2, Abs>:
508  Some{Abs{scheme, host, port, with_q(path, q, has_q)}}
509
510# A path, its query, and whether a "?" was present at all.
511type PQ is Data:
512  PQ{path: String, q: String, has_q: Bool}
513
514def res.pq(pq: String & String, has_q: Bool) -> PQ:
515  (p, q) = pq
516  PQ{p, q, has_q}
517
518def res.ref(+r: String) -> PQ:
519  res.pq(take_to(r, 63), has(r, 63))
520
521# §5.2.2: an empty path keeps the base path (and its query unless one is given);
522# "/..." replaces the path; anything else merges with the base directory.
523def res.rel.go(+scheme: String, +host: String, +port: U32, +bpath: String, +bq: String, +bhas: Bool, +rp: String, +q: String, +rhas: Bool) -> Maybe<&2, Abs>:
524  Bool.pick(Maybe<&2, Abs>, String.is_empty(rp),
525    Bool.pick(Maybe<&2, Abs>, rhas, res.build(scheme, host, port, bpath, q, True{}), res.build(scheme, host, port, bpath, bq, bhas)),
526    res.build(scheme, host, port, remove_dots(Bool.pick(String, String.starts_with(rp, "/"), rp, dir(bpath) ++ rp)), q, rhas))
527
528def res.rel(scheme: String, host: String, port: U32, bpath: String, bq: String, bhas: Bool, r: PQ) -> Maybe<&2, Abs>:
529  PQ{rp, q, rhas} = r
530  res.rel.go(scheme, host, port, bpath, bq, bhas, rp, q, rhas)
531
532def res.base(+r: String, b: PQ, a: Abs) -> Maybe<&2, Abs>:
533  PQ{bpath, bq, bhas} = b
534  Abs{scheme, host, port, target} = a
535  res.rel(scheme, host, port, bpath, bq, bhas, res.ref(abs.fst(take_to(r, 35))))
536
537def res.local(+r: String, a: Abs) -> Maybe<&2, Abs>:
538  Abs{+scheme, +host, +port, +target} = a
539  res.base(r, res.ref(target), Abs{scheme, host, port, target})
540
541def abs.scheme_of(a: Abs) -> String:
542  Abs{scheme, host, port, target} = a
543  scheme
544
545def res.net(+r: String, a: Abs, net: Bool) -> Maybe<&2, Abs>:
546  match net:
547    case True{}:
548      absolute(abs.scheme_of(a) ++ ":" ++ r)
549    case False{}:
550      res.local(r, a)
551
552def scheme.ok(s: String) -> Bool:
553  match s:
554    case SNil{}:
555      True{}
556    case SCon{Chr{+c}, t}:
557      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))
558
559# §3.1: a ":" before any "/", "?" or "#" with a valid scheme name before it.
560def abs.has_scheme(+pre: String, colon: Bool) -> Bool:
561  Bool.and(colon, Bool.and(Bool.not(String.is_empty(pre)), scheme.ok(pre)))
562# ref against base: absolute http(s) URLs as is, "//host...", "/path", "?q",
563# or a relative path. Other schemes are None (fetch cannot follow them).
564def resolve(a: Abs, +ref: String) -> Maybe<&2, Abs>:
565  +low = String.to_lower(ref)
566  Bool.pick(Maybe<&2, Abs>, Bool.or(String.starts_with(low, "http://"), String.starts_with(low, "https://")), absolute(ref),
567    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, "//"))))
568