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