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.
8	import Base
9	import ./pct.bend as Pct
10	import ./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
14	def 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
21	type 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)
27	type 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`)
33	def 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`
37	def 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
41	def 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
50	def 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
59	def 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
64	def 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
74	def 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
83	def 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
94	def 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
104	def 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
116	type 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
122	type 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
128	def 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
136	def 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
144	def 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
152	def 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
160	def 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
168	def 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
176	def 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
184	def 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
192	def 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
200	def 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)
208	def lead(+b: U32) -> Lead:
209	  lead.ascii(b, U32.is_lt(b, 128))
210	
211	# U+FFFD REPLACEMENT CHARACTER
212	def fffd() -> Char:
213	  Chr{65533}
214	
215	# a continuation byte's six bits after the code point so far
216	def 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
220	def 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
230	def 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
238	def 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
247	def 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
256	def 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
265	def 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
273	def 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
281	def 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
291	def 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
295	def 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
301	def 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
309	def 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
317	def form.pair(name: String, value: String) -> String:
318	  quote.plus(name) ++ "=" ++ quote.plus(value)
319	
320	# the pairs after the first, each after an `&`
321	def 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
329	def 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
339	def 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
347	def 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 `=`
357	def 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 `=`
366	def 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
374	def field(+piece: String) -> Kv():
375	  field.of(cut(piece), piece)
376	
377	# one piece in front of the rest's fields, skipped when empty
378	def 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
387	def 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)
396	def 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
400	def 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
411	def 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
421	def 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)
430	def octets.text(o: String) -> String:
431	  utf.dec(octets.toks(o), Idle{})
432	
433	# received header fields as text, name and value each decoded
434	def 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)