src/qs.bend

emerging-ezhttp@0.21.0.0 · 439 lines · 56 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.21.0.0/src/pct.bend as Pct
10import emerging-ezhttp@0.21.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)