scan.bend
gralha-text-scan@0.1.0.0 · 290 lines · 0 definitions
1# Text scanning, number parsing (the SVG/CSS number grammar, units, hex) and
2# small helpers over strings, U32 and F32.
3import Base
4
5def choose(-A: Type, yes: Bool, a: A, b: A) -> A:
6 match yes:
7 case True{}: a
8 case False{}: b
9
10def max.u32(+a: U32, +b: U32) -> U32:
11 choose(U32, U32.is_gt(a, b), a, b)
12
13def min.u32(+a: U32, +b: U32) -> U32:
14 choose(U32, U32.is_lt(a, b), a, b)
15
16def min(+a: F32, +b: F32) -> F32:
17 choose(F32, F32.is_lt(a, b), a, b)
18
19def max(+a: F32, +b: F32) -> F32:
20 choose(F32, F32.is_gt(a, b), a, b)
21
22def clamp(x: F32, lo: F32, hi: F32) -> F32:
23 max(lo, min(hi, x))
24
25def code(c: Char) -> U32:
26 Chr{x} = c
27 x
28
29def 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
32def digit(+c: U32) -> Bool:
33 U32.is_ge(c, 48) && U32.is_le(c, 57)
34
35def 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
42def 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
49def string.equal(a: String, b: String) -> Bool:
50 string.equal.go(True{}, a, b)
51
52def 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
57def 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
63type 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
70def 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
80def 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
87def 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
94def 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
100def 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
106def 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
113def 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
123def 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
130def 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
138type 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.
150def 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
155def 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
161def 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.
168def 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).
176type Head is Data:
177 Head{end: Bool, ok: Bool, k: U32, c: U32, mark: String, t: String}
178
179def 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
187def 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
195def 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
220def 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
223def number.default(num: Number, fallback: F32) -> F32:
224 Number{x, t, valid} = num
225 choose(F32, valid, x, fallback)
226
227def scalar(s: String, fallback: F32) -> F32:
228 number.default(number(s), fallback)
229
230def 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
235def numbers(s: String) -> List<&2, F32>:
236 numbers.next(number(s), t => numbers(t))
237
238def 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
244def 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
250def 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
255def 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
260def trim.both(s: String) -> String:
261 rev(trim(rev(trim(s), "")), "")
262
263def 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
274def 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
279def scan.head(s: Scan) -> String:
280 Scan{h, t} = s
281 h
282
283def 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
287def 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))