src/qs.bend
emerging-ezhttp@0.20.0.0 · 439 lines · 0 definitions
1# ezhttp/src/qs: percent-decoding (RFC 3986 §2.1) and query strings
2# (application/x-www-form-urlencoded, WHATWG URL §5), the way Python's
3# urllib.parse.unquote, unquote_plus, quote_plus, urlencode and
4# parse_qsl(keep_blank_values=True) do them. Decoded bytes are read as UTF-8
5# (RFC 3629 §4), each maximal subpart of an ill-formed sequence replaced by
6# one U+FFFD (Unicode §3.9), as Python's errors="replace" does. Pure.
7# SPEC.md HTTP-QS lists what is guaranteed.
8import Base
9import emerging-ezhttp@0.20.0.0/src/pct.bend as Pct
10import emerging-ezhttp@0.20.0.0/src/http.bend as Http
11
12# a name and a value, as a query field or a cookie: a reusable pair, so a
13# list of them can be looked up more than once
14def Kv() -> Data:
15 Sigma<&2, &2, String, _ => String>
16
17# --- percent-decoding: text to bytes (HTTP-QS-1) ---
18
19# one piece of a string being decoded: a byte of an ASCII run, or a
20# character outside ASCII, which is kept as it is and ends the run
21type Tok is Data:
22 B{byte: U32}
23 W{c: Char}
24
25# where the decoding stands: in plain text, after `%`, or after `%` and one
26# hex digit (kept)
27type Esc is Data:
28 Plain{}
29 Pct{}
30 Pct1{d: Char}
31
32# whether a character is a hex digit (`0`-`9`, `A`-`F`, `a`-`f`)
33def tok.hex(c: Char) -> Bool:
34 U32.is_lt(Http.hex.val(c), 16)
35
36# the byte a plain ASCII character stands for: `+` is a space when `plus`
37def tok.byte(plus: Bool, +c: Char) -> U32:
38 Bool.pick(U32, Bool.and(plus, Char.is_eq(c, '+')), 32, Char.to_u32(c))
39
40# a plain ASCII character: `%` opens an escape, any other is its byte
41def tok.ascii(plus: Bool, +c: Char, k: Esc -> List<&2, Tok>, pct: Bool)
42 -> List<&2, Tok>:
43 match pct:
44 case True{}:
45 k(Pct{})
46 case False{}:
47 B{tok.byte(plus, c)} <> k(Plain{})
48
49# a plain character once it is known whether it is outside ASCII
50def tok.wide(plus: Bool, +c: Char, k: Esc -> List<&2, Tok>, wide: Bool)
51 -> List<&2, Tok>:
52 match wide:
53 case True{}:
54 W{c} <> k(Plain{})
55 case False{}:
56 tok.ascii(plus, c, k, Char.is_eq(c, '%'))
57
58# a character in plain text
59def tok.plain(plus: Bool, +c: Char, k: Esc -> List<&2, Tok>) -> List<&2, Tok>:
60 tok.wide(plus, c, k, U32.is_ge(Char.to_u32(c), 128))
61
62# a character after `%`: a hex digit is kept, anything else leaves the `%`
63# as written
64def tok.pct(plus: Bool, +c: Char, k: Esc -> List<&2, Tok>, hex: Bool)
65 -> List<&2, Tok>:
66 match hex:
67 case True{}:
68 k(Pct1{c})
69 case False{}:
70 B{37} <> tok.plain(plus, c, k)
71
72# a character after `%` and a hex digit: a second hex digit makes the byte
73# they name, anything else leaves `%` and the digit as written
74def tok.pct1(plus: Bool, +d: Char, +c: Char, k: Esc -> List<&2, Tok>,
75 hex: Bool) -> List<&2, Tok>:
76 match hex:
77 case True{}:
78 B{U32.add(U32.mul(Http.hex.val(d), 16), Http.hex.val(c))} <> k(Plain{})
79 case False{}:
80 B{37} <> (B{Char.to_u32(d)} <> tok.plain(plus, c, k))
81
82# one character where the decoding stands
83def tok.step(plus: Bool, st: Esc, +c: Char, k: Esc -> List<&2, Tok>)
84 -> List<&2, Tok>:
85 match st:
86 case Plain{}:
87 tok.plain(plus, c, k)
88 case Pct{}:
89 tok.pct(plus, c, k, tok.hex(c))
90 case Pct1{d}:
91 tok.pct1(plus, d, c, k, tok.hex(c))
92
93# the end of the text: an escape left open is written as it stands
94def tok.end(st: Esc) -> List<&2, Tok>:
95 match st:
96 case Plain{}:
97 []
98 case Pct{}:
99 [B{37}]
100 case Pct1{d}:
101 [B{37}, B{Char.to_u32(d)}]
102
103# a string as bytes and wide characters, character by character
104def toks(s: String, +plus: Bool, st: Esc) -> List<&2, Tok>:
105 match s:
106 case SNil{}:
107 tok.end(st)
108 case SCon{+c, t}:
109 tok.step(plus, st, c, st2 => toks(t, plus, st2))
110
111# --- UTF-8 decoding with replacement (HTTP-QS-2) ---
112
113# where the UTF-8 decoding stands: between characters, or inside a sequence
114# with code point bits `cp` so far, needing a byte in lo..hi and `left` more
115# continuation bytes after it
116type Utf is Data:
117 Idle{}
118 Need{cp: U32, left: Nat, lo: U32, hi: U32}
119
120# what a byte between characters is: ASCII, the lead of a sequence (its bits,
121# then what the sequence needs next), or a byte no sequence starts with
122type Lead is Data:
123 Ascii{}
124 Bad{}
125 Opens{cp: U32, left: Nat, lo: U32, hi: U32}
126
127# F4: the last lead, up to U+10FFFF; F5 to FF lead nothing
128def lead.f4(f4: Bool) -> Lead:
129 match f4:
130 case True{}:
131 Opens{4, 2n, 128, 143}
132 case False{}:
133 Bad{}
134
135# F1 to F3, else F4 and up
136def lead.f1(+b: U32, lt: Bool) -> Lead:
137 match lt:
138 case True{}:
139 Opens{U32.and(b, 7), 2n, 128, 191}
140 case False{}:
141 lead.f4(U32.is_eq(b, 244))
142
143# F0 (no overlong four-byte form), else F1 and up
144def lead.f0(+b: U32, f0: Bool) -> Lead:
145 match f0:
146 case True{}:
147 Opens{0, 2n, 144, 191}
148 case False{}:
149 lead.f1(b, U32.is_lt(b, 244))
150
151# EE and EF, else F0 and up
152def lead.ee(+b: U32, lt: Bool) -> Lead:
153 match lt:
154 case True{}:
155 Opens{U32.and(b, 15), 1n, 128, 191}
156 case False{}:
157 lead.f0(b, U32.is_eq(b, 240))
158
159# ED (no surrogates), else EE and up
160def lead.ed(+b: U32, ed: Bool) -> Lead:
161 match ed:
162 case True{}:
163 Opens{13, 1n, 128, 159}
164 case False{}:
165 lead.ee(b, U32.is_lt(b, 240))
166
167# E1 to EC, else ED and up
168def lead.e1(+b: U32, lt: Bool) -> Lead:
169 match lt:
170 case True{}:
171 Opens{U32.and(b, 15), 1n, 128, 191}
172 case False{}:
173 lead.ed(b, U32.is_eq(b, 237))
174
175# E0 (no overlong three-byte form), else E1 and up
176def lead.e0(+b: U32, e0: Bool) -> Lead:
177 match e0:
178 case True{}:
179 Opens{0, 1n, 160, 191}
180 case False{}:
181 lead.e1(b, U32.is_lt(b, 237))
182
183# C2 to DF, else E0 and up
184def lead.two(+b: U32, lt: Bool) -> Lead:
185 match lt:
186 case True{}:
187 Opens{U32.and(b, 31), 0n, 128, 191}
188 case False{}:
189 lead.e0(b, U32.is_eq(b, 224))
190
191# 80 to C1 (continuation bytes, overlong two-byte leads), else C2 and up
192def lead.low(+b: U32, lt: Bool) -> Lead:
193 match lt:
194 case True{}:
195 Bad{}
196 case False{}:
197 lead.two(b, U32.is_lt(b, 224))
198
199# ASCII, else 80 and up
200def lead.ascii(+b: U32, lt: Bool) -> Lead:
201 match lt:
202 case True{}:
203 Ascii{}
204 case False{}:
205 lead.low(b, U32.is_lt(b, 194))
206
207# what a byte between characters is (RFC 3629 §4, Unicode Table 3-7)
208def lead(+b: U32) -> Lead:
209 lead.ascii(b, U32.is_lt(b, 128))
210
211# U+FFFD REPLACEMENT CHARACTER
212def fffd() -> Char:
213 Chr{65533}
214
215# a continuation byte's six bits after the code point so far
216def utf.add(+cp: U32, +b: U32) -> U32:
217 U32.or(U32.shln(cp, 6n), U32.and(b, 63))
218
219# a byte between characters, as its lead says
220def utf.lead(+b: U32, k: Utf -> String, l: Lead) -> String:
221 match l:
222 case Ascii{}:
223 SCon{Chr{b}, k(Idle{})}
224 case Bad{}:
225 SCon{fffd(), k(Idle{})}
226 case Opens{cp, left, lo, hi}:
227 k(Need{cp, left, lo, hi})
228
229# a piece between characters
230def utf.idle(t: Tok, k: Utf -> String) -> String:
231 match t:
232 case W{c}:
233 SCon{c, k(Idle{})}
234 case B{+b}:
235 utf.lead(b, k, lead(b))
236
237# a continuation byte that fits: the character ends, or more are needed
238def utf.more(+cp: U32, left: Nat, +b: U32, k: Utf -> String) -> String:
239 match left:
240 case 0n:
241 SCon{Chr{utf.add(cp, b)}, k(Idle{})}
242 case 1n+l:
243 k(Need{utf.add(cp, b), l, 128, 191})
244
245# a byte inside a sequence: it continues it when it fits, else the sequence
246# so far is one U+FFFD and the byte is read again between characters
247def utf.byte(+cp: U32, left: Nat, +b: U32, k: Utf -> String, fits: Bool)
248 -> String:
249 match fits:
250 case True{}:
251 utf.more(cp, left, b, k)
252 case False{}:
253 SCon{fffd(), utf.lead(b, k, lead(b))}
254
255# a piece inside a sequence: a wide character ends it unfinished
256def utf.need(+cp: U32, left: Nat, +lo: U32, +hi: U32, t: Tok,
257 k: Utf -> String) -> String:
258 match t:
259 case W{c}:
260 SCon{fffd(), SCon{c, k(Idle{})}}
261 case B{+b}:
262 utf.byte(cp, left, b, k, Bool.and(U32.is_le(lo, b), U32.is_le(b, hi)))
263
264# one piece where the decoding stands
265def utf.step(st: Utf, t: Tok, k: Utf -> String) -> String:
266 match st:
267 case Idle{}:
268 utf.idle(t, k)
269 case Need{cp, left, lo, hi}:
270 utf.need(cp, left, lo, hi, t, k)
271
272# the end of the pieces: a sequence left unfinished is one U+FFFD
273def utf.end(st: Utf) -> String:
274 match st:
275 case Idle{}:
276 ""
277 case Need{cp, left, lo, hi}:
278 SCon{fffd(), ""}
279
280# pieces as text, piece by piece
281def utf.dec(ts: List<&2, Tok>, st: Utf) -> String:
282 match ts:
283 case []:
284 utf.end(st)
285 case t <> rest:
286 utf.step(st, t, st2 => utf.dec(rest, st2))
287
288# --- the decoders (HTTP-QS-1, 3) ---
289
290# percent-decode a string, as urllib.parse.unquote
291def unquote(s: String) -> String:
292 utf.dec(toks(s, False{}, Plain{}), Idle{})
293
294# percent-decode a string with `+` as a space, as urllib.parse.unquote_plus
295def unquote.plus(s: String) -> String:
296 utf.dec(toks(s, True{}, Plain{}), Idle{})
297
298# --- quote_plus and urlencode (HTTP-QS-4, 5) ---
299
300# one character: a space as `+`, any other as quote_component writes it
301def plus.one(+cp: U32, rest: String, space: Bool) -> String:
302 match space:
303 case True{}:
304 SCon{'+', rest}
305 case False{}:
306 Pct.one(False{}, cp, rest)
307
308# percent-encode a string with a space as `+`, as urllib.parse.quote_plus
309def quote.plus(s: String) -> String:
310 match s:
311 case SNil{}:
312 SNil{}
313 case SCon{Chr{+cp}, tail}:
314 plus.one(cp, quote.plus(tail), U32.is_eq(cp, 32))
315
316# one name and value as `name=value`, both quote_plus'd
317def form.pair(name: String, value: String) -> String:
318 quote.plus(name) ++ "=" ++ quote.plus(value)
319
320# the pairs after the first, each after an `&`
321def form.more(ps: List<&2, Kv()>) -> String:
322 match ps:
323 case []:
324 ""
325 case (name, value) <> t:
326 "&" ++ form.pair(name, value) ++ form.more(t)
327
328# pairs as a query string, as urllib.parse.urlencode
329def urlencode(ps: List<&2, Kv()>) -> String:
330 match ps:
331 case []:
332 ""
333 case (name, value) <> t:
334 form.pair(name, value) ++ form.more(t)
335
336# --- parse_query and query_get (HTTP-QS-6, 7) ---
337
338# one character put back in front of what the rest of the cut found
339def cut.push(+c: Char, m: Maybe<&2, Kv()>) -> Maybe<&2, Kv()>:
340 match m:
341 case None{}:
342 None{}
343 case Some{(before, after)}:
344 Some{(SCon{c, before}, after)}
345
346# one character of the cut: the first `=` ends the text before it
347def cut.at(+c: Char, t: String, eq: Bool, rest: Unit -> Maybe<&2, Kv()>)
348 -> Maybe<&2, Kv()>:
349 match eq:
350 case True{}:
351 Some{("", t)}
352 case False{}:
353 cut.push(c, rest(Unit{}))
354
355# a string cut at its first `=`: the text before it and the text after it,
356# none when it holds no `=`
357def cut(s: String) -> Maybe<&2, Kv()>:
358 match s:
359 case SNil{}:
360 None{}
361 case SCon{+c, +t}:
362 cut.at(c, t, Char.is_eq(c, '='), _u => cut(t))
363
364# a field once it is cut: the name before its first `=` and the value after
365# it, or all name and an empty value when it has no `=`
366def field.of(m: Maybe<&2, Kv()>, whole: String) -> Kv():
367 match m:
368 case None{}:
369 (unquote.plus(whole), "")
370 case Some{(name, value)}:
371 (unquote.plus(name), unquote.plus(value))
372
373# one field as its name and value
374def field(+piece: String) -> Kv():
375 field.of(cut(piece), piece)
376
377# one piece in front of the rest's fields, skipped when empty
378def fields.put(+piece: String, rest: List<&2, Kv()>, empty: Bool)
379 -> List<&2, Kv()>:
380 match empty:
381 case True{}:
382 rest
383 case False{}:
384 field(piece) <> rest
385
386# the pieces as fields, in order
387def fields(ps: List<&2, String>) -> List<&2, Kv()>:
388 match ps:
389 case []:
390 []
391 case +p <> t:
392 fields.put(p, fields(t), String.is_empty(p))
393
394# a query string as its name and value pairs, as
395# urllib.parse.parse_qsl(text, keep_blank_values=True)
396def parse(text: String) -> List<&2, Kv()>:
397 fields(String.split(text, '&'))
398
399# the value a later pair gives, else this pair's when it is named
400def get.pick(later: Maybe<&2, String>, value: String, hit: Bool)
401 -> Maybe<&2, String>:
402 match later hit:
403 case Some{x} _:
404 Some{x}
405 case None{} True{}:
406 Some{value}
407 case None{} False{}:
408 None{}
409
410# the value of the last pair with this name, none when no pair has it
411def get(ps: List<&2, Kv()>, +name: String) -> Maybe<&2, String>:
412 match ps:
413 case []:
414 None{}
415 case (key, value) <> t:
416 get.pick(get(t, name), value, String.eq(key, name))
417
418# --- received octets as text (SPEC.md HTTP-BODY-4) ---
419
420# octets, one character each, as the pieces utf.dec reads
421def octets.toks(s: String) -> List<&2, Tok>:
422 match s:
423 case SNil{}:
424 []
425 case SCon{c, t}:
426 B{Char.to_u32(c)} <> octets.toks(t)
427
428# received octets as text: decoded as UTF-8, each ill-formed sequence's
429# maximal subpart one U+FFFD (HTTP-QS-2)
430def octets.text(o: String) -> String:
431 utf.dec(octets.toks(o), Idle{})
432
433# received header fields as text, name and value each decoded
434def octets.headers(hs: List<&2, Http.Header>) -> List<&2, Http.Header>:
435 match hs:
436 case []:
437 []
438 case Http.H{name, value} <> t:
439 Http.H{octets.text(name), octets.text(value)} <> octets.headers(t)