1	# Text scanning, number parsing (the SVG/CSS number grammar, units, hex) and
2	# small helpers over strings, U32 and F32.
3	import Base
4	
5	def choose(-A: Type, yes: Bool, a: A, b: A) -> A:
6	  match yes:
7	    case True{}: a
8	    case False{}: b
9	
10	def max.u32(+a: U32, +b: U32) -> U32:
11	  choose(U32, U32.is_gt(a, b), a, b)
12	
13	def min.u32(+a: U32, +b: U32) -> U32:
14	  choose(U32, U32.is_lt(a, b), a, b)
15	
16	def min(+a: F32, +b: F32) -> F32:
17	  choose(F32, F32.is_lt(a, b), a, b)
18	
19	def max(+a: F32, +b: F32) -> F32:
20	  choose(F32, F32.is_gt(a, b), a, b)
21	
22	def clamp(x: F32, lo: F32, hi: F32) -> F32:
23	  max(lo, min(hi, x))
24	
25	def code(c: Char) -> U32:
26	  Chr{x} = c
27	  x
28	
29	def space(+c: U32) -> Bool:
30	  U32.is_eq(c, 32) || U32.is_eq(c, 9) || U32.is_eq(c, 10) || U32.is_eq(c, 13)
31	
32	def digit(+c: U32) -> Bool:
33	  U32.is_ge(c, 48) && U32.is_le(c, 57)
34	
35	def rev(s: String, acc: String) -> String:
36	  match s:
37	    case SNil{}: acc
38	    case SCon{c, t}: rev(t, SCon{c, acc})
39	
40	# `same` says whether the characters before `a` and `b` matched: deciding
41	# it one step ahead keeps the loop a tail call on the shrinking `a`.
42	def string.equal.go(a: String, b: String, same: Bool) -> Bool:
43	  match a b same:
44	    case SNil{} SNil{} True{}: True{}
45	    case SCon{Chr{x}, xs} SCon{Chr{y}, ys} True{}: string.equal.go(xs, ys, U32.is_eq(x, y))
46	    case _ _ _: False{}
47	
48	def string.equal(a: String, b: String) -> Bool:
49	  string.equal.go(a, b, True{})
50	
51	def branch(-A: Type, yes: Bool, a: Unit -> A, b: Unit -> A) -> A:
52	  match yes:
53	    case True{}: a(Unit{})
54	    case False{}: b(Unit{})
55	
56	def trim(+s: String) -> String:
57	  match s:
58	    case SNil{}: ""
59	    case SCon{Chr{c}, t}:
60	      branch(String, space(c), _ => trim(t), _ => SCon{Chr{c}, t})
61	
62	type Scan is Data:
63	  Scan{head: String, tail: String}
64	
65	# Scanning loops decide each character one step ahead (`hit` says whether
66	# `c`, the character before `t`, ends the scan), so the rest of the text is
67	# only ever held once: a shared tail would make every step pay for the
68	# sharing. The rest comes first, as the argument that shrinks.
69	def until.go(t: String, hit: Bool, +c: U32, +end: U32, acc: String) -> Scan:
70	  match t hit:
71	    case t True{}: Scan{rev(acc, ""), t}
72	    case SNil{} False{}: Scan{rev(SCon{Chr{c}, acc}, ""), ""}
73	    case SCon{Chr{c2}, t2} False{}:
74	      +cc = c2
75	      until.go(t2, U32.is_eq(cc, end), cc, end, SCon{Chr{c}, acc})
76	
77	def until(s: String, +end: U32, acc: String) -> Scan:
78	  match s:
79	    case SNil{}: Scan{rev(acc, ""), ""}
80	    case SCon{Chr{c}, t}:
81	      +cc = c
82	      until.go(t, U32.is_eq(cc, end), cc, end, acc)
83	
84	def prefix(s: String, p: String) -> Bool:
85	  match s p:
86	    case _ SNil{}: True{}
87	    case SNil{} SCon{pc, pt}: False{}
88	    case SCon{sc, st} SCon{pc, pt}:
89	      U32.is_eq(code(sc), code(pc)) && prefix(st, pt)
90	
91	def drop(s: String, p: String) -> String:
92	  match s p:
93	    case s SNil{}: s
94	    case SNil{} SCon{pc, pt}: ""
95	    case SCon{sc, st} SCon{pc, pt}: drop(st, pt)
96	
97	def through(+s: String, +p: String) -> String:
98	  match s:
99	    case SNil{}: ""
100	    case SCon{sc, st}:
101	      branch(String, prefix(s, p), _ => drop(s, p), _ => through(st, p))
102	
103	def until.sequence(+s: String, +end: String, +acc: String) -> Scan:
104	  match s:
105	    case SNil{}: Scan{rev(acc, ""), ""}
106	    case SCon{c, t}: branch(Scan, prefix(s, end), _ => Scan{rev(acc, ""), drop(s, end)}, _ => until.sequence(t, end, SCon{c, acc}))
107	
108	# SVG number grammar, including adjacent signs and scientific notation.
109	def separator(+c: U32) -> Bool:
110	  space(c) || U32.is_eq(c, 44)
111	
112	def separators.go(t: String, skip: Bool, +c: U32) -> String:
113	  match t skip:
114	    case t False{}: SCon{Chr{c}, t}
115	    case SNil{} True{}: ""
116	    case SCon{Chr{c2}, t2} True{}:
117	      +cc = c2
118	      separators.go(t2, separator(cc), cc)
119	
120	def separators(s: String) -> String:
121	  match s:
122	    case SNil{}: ""
123	    case SCon{Chr{c}, t}:
124	      +cc = c
125	      separators.go(t, separator(cc), cc)
126	
127	def number.exponent(+s: String) -> Bool:
128	  match s:
129	    case SNil{}: False{}
130	    case SCon{Chr{c}, t}:
131	      match t:
132	        case SNil{}: digit(c)
133	        case SCon{Chr{d}, rest}: digit(c) || ((U32.is_eq(c, 43) || U32.is_eq(c, 45)) && digit(d))
134	
135	type Number is Data:
136	  Number{value: F32, tail: String, valid: Bool}
137	
138	# A number is read straight into a float: digits accumulate the mantissa
139	# (fraction digits also scale a divisor), an exponent accumulates its own
140	# digits, and a sign is taken where it may appear. Nothing is copied into a
141	# scratch string. Each character is classified one step ahead, so the loop
142	# branches on parameters: class 0 digit, 1 dot, 2 exponent mark, 3 sign,
143	# 4 anything else; stage 0 start, 1 mantissa, 2 fraction, 3 after the
144	# mark, 4 exponent digits. An exponent mark that no digit follows is not
145	# part of the number (as in "1em"), so `mark` keeps what was read from the
146	# mark on (the mark and any signs, reversed) to give back in that case.
147	def number.class(+c: U32) -> U32:
148	  choose(U32, digit(c), 0, choose(U32, U32.is_eq(c, 46), 1,
149	    choose(U32, U32.is_eq(c, 101) || U32.is_eq(c, 69), 2,
150	      choose(U32, U32.is_eq(c, 43) || U32.is_eq(c, 45), 3, 4))))
151	
152	def number.accepts(+k: U32, +stage: U32, +digits: Bool) -> Bool:
153	  choose(Bool, U32.is_eq(k, 0), True{},
154	    choose(Bool, U32.is_eq(k, 1), U32.is_lt(stage, 2),
155	      choose(Bool, U32.is_eq(k, 2), digits && U32.is_lt(stage, 3),
156	        choose(Bool, U32.is_eq(k, 3), U32.is_eq(stage, 0) || U32.is_eq(stage, 3), False{}))))
157	
158	def number.stage(+k: U32, +stage: U32) -> U32:
159	  choose(U32, U32.is_eq(k, 0), choose(U32, U32.is_eq(stage, 0), 1, choose(U32, U32.is_eq(stage, 3), 4, stage)),
160	    choose(U32, U32.is_eq(k, 1), 2, choose(U32, U32.is_eq(k, 2), 3, stage)))
161	
162	def number.mark(keep: Bool, +c: U32, mark: String) -> String:
163	  match keep:
164	    case True{}: SCon{Chr{c}, mark}
165	    case False{}: mark
166	
167	def number.pow10(n: Nat, +acc: F32) -> F32:
168	  match n:
169	    case 0n: acc
170	    case 1n+d: number.pow10(d, (acc * 10.0 : F32))
171	
172	def number.tail(dangling: Bool, mark: String, rest: String) -> String:
173	  match dangling:
174	    case True{}: rev(mark, rest)
175	    case False{}: rest
176	
177	# The value from the parts; `rest` is the string from the stop.
178	def number.finish(rest: String, mark: String, +stage: U32, +sign: F32, +mant: F32, +div: F32, +esign: F32, +ev: U32, +digits: Bool, +edigits: Bool) -> Number:
179	  +dangling = U32.is_ge(stage, 3) && Bool.not(edigits)
180	  +scale = number.pow10(U32.to_nat(choose(U32, dangling, 0, ev)), 1.0)
181	  +v = (sign * mant / choose(F32, F32.is_gt(div, 0.0), div, 1.0) : F32)
182	  Number{choose(F32, F32.is_lt(esign, 0.0), (v / scale : F32), (v * scale : F32)), number.tail(dangling, mark, rest), digits}
183	
184	# `c` is the character before `t`; `ok` says whether it was read, and the
185	# parts are the ones after it. The next character is read when the stage
186	# accepts it, and otherwise the parts are kept and the number stops there.
187	def number.go(t: String, ok: Bool, +c: U32, mark: String, +stage: U32, +sign: F32, +mant: F32, +div: F32, +esign: F32, +ev: U32, +digits: Bool, +edigits: Bool) -> Number:
188	  match t ok:
189	    case t False{}: number.finish(SCon{Chr{c}, t}, mark, stage, sign, mant, div, esign, ev, digits, edigits)
190	    case SNil{} True{}: number.finish("", mark, stage, sign, mant, div, esign, ev, digits, edigits)
191	    case SCon{Chr{c2}, t2} True{}:
192	      +cc = c2
193	      +k = number.class(cc)
194	      +read = number.accepts(k, stage, digits)
195	      +isDigit = read && U32.is_eq(k, 0)
196	      +inExp = U32.is_ge(stage, 3)
197	      +minus = read && U32.is_eq(k, 3) && U32.is_eq(cc, 45)
198	      +stage2 = choose(U32, read, number.stage(k, stage), stage)
199	      number.go(t2, read, cc, number.mark(read && U32.is_eq(stage2, 3), cc, mark), stage2,
200	        choose(F32, minus && U32.is_eq(stage, 0), F32.neg(1.0), sign),
201	        choose(F32, isDigit && Bool.not(inExp), (mant * 10.0 + U32.to_f32((cc - 48 : U32)) : F32), mant),
202	        choose(F32, isDigit && U32.is_eq(stage, 2), (div * 10.0 : F32), choose(F32, read && U32.is_eq(k, 1), 1.0, div)),
203	        choose(F32, minus && U32.is_eq(stage, 3), F32.neg(1.0), esign),
204	        choose(U32, isDigit && inExp, (ev * 10 + cc - 48 : U32), ev),
205	        digits || (isDigit && Bool.not(inExp)), edigits || (isDigit && inExp))
206	
207	# The loop starts as if after a character that was read, with nothing yet.
208	def number(s: String) -> Number:
209	  number.go(separators(s), True{}, 0, "", 0, 1.0, 0.0, 0.0, 1.0, 0, False{}, False{})
210	
211	def number.default(num: Number, fallback: F32) -> F32:
212	  Number{x, t, valid} = num
213	  choose(F32, valid, x, fallback)
214	
215	def scalar(s: String, fallback: F32) -> F32:
216	  number.default(number(s), fallback)
217	
218	def numbers.next(num: Number, next: String -> List<&2, F32>) -> List<&2, F32>:
219	  Number{x, t, valid} = num
220	  choose(Unit -> List<&2, F32>, valid, _ => Con{x, next(t)}, _ => Nil{})(Unit{})
221	
222	# Every number read takes at least one character (a digit), so the text's
223	# length bounds how many there are.
224	def numbers.go(fuel: Nat, s: String) -> List<&2, F32>:
225	  match fuel:
226	    case 0n: Nil{}
227	    case 1n+f: numbers.next(number(s), t => numbers.go(f, t))
228	
229	def numbers(+s: String) -> List<&2, F32>:
230	  numbers.go(String.length(s), s)
231	
232	def nth(xs: List<&2, F32>, i: Nat, fallback: F32) -> F32:
233	  match xs i:
234	    case Nil{} _: fallback
235	    case Con{h, t} 0n: h
236	    case Con{h, t} 1n+p: nth(t, p, fallback)
237	
238	def uints.nth(xs: List<&2, U32>, n: Nat, +fallback: U32) -> U32:
239	  match xs n:
240	    case Nil{} _: fallback
241	    case Con{h, t} 0n: h
242	    case Con{h, t} 1n+d: uints.nth(t, d, fallback)
243	
244	def hex.digit(+c: U32) -> U32:
245	  choose(U32, digit(c), (c - 48 : U32),
246	    choose(U32, U32.is_ge(c, 65) && U32.is_le(c, 70), (c - 55 : U32),
247	      choose(U32, U32.is_ge(c, 97) && U32.is_le(c, 102), (c - 87 : U32), 0)))
248	
249	def hex(s: String, acc: U32) -> U32:
250	  match s:
251	    case SNil{}: acc
252	    case SCon{Chr{c}, t}: hex(t, (acc * 16 + hex.digit(c) : U32))
253	
254	def trim.both(s: String) -> String:
255	  rev(trim(rev(trim(s), "")), "")
256	
257	def unit(num: Number, reference: F32) -> F32:
258	  Number{x, t, ok} = num
259	  +v = x
260	  +u = t
261	  (v * choose(F32, prefix(u, "%"), (reference / 100.0 : F32),
262	    choose(F32, prefix(u, "in"), 96.0,
263	      choose(F32, prefix(u, "cm"), 37.7952755906,
264	        choose(F32, prefix(u, "mm"), 3.77952755906,
265	          choose(F32, prefix(u, "pt"), 1.333333333333,
266	            choose(F32, prefix(u, "pc"), 16.0, 1.0)))))) : F32)
267	
268	def string.contains(+s: String, +part: String) -> Bool:
269	  match s:
270	    case SNil{}: string.equal(part, "")
271	    case SCon{c, rest}: prefix(s, part) || string.contains(rest, part)
272	
273	def scan.head(s: Scan) -> String:
274	  Scan{h, t} = s
275	  h
276	
277	def unquote(+s: String) -> String:
278	  branch(String, prefix(s, "'"), _ => scan.head(until(drop(s, "'"), 39, "")),
279	    _ => branch(String, prefix(s, "\""), _ => scan.head(until(drop(s, "\""), 34, "")), _ => s))
280	
281	def strings.has(xs: List<&2, String>, +s: String) -> Bool:
282	  match xs:
283	    case Nil{}: False{}
284	    case Con{h, t}: branch(Bool, string.equal(h, s), _ => True{}, _ => strings.has(t, s))