scan.bend

gralha-text-scan@0.1.0.1 · 284 lines · 50 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# `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`.
42def 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
48def string.equal(a: String, b: String) -> Bool:
49  string.equal.go(a, b, True{})
50
51def 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
56def 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
62type 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.
69def 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
77def 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
84def 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
91def 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
97def 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
103def 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.
109def separator(+c: U32) -> Bool:
110  space(c) || U32.is_eq(c, 44)
111
112def 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
120def 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
127def 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
135type 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.
147def 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
152def 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
158def 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
162def number.mark(keep: Bool, +c: U32, mark: String) -> String:
163  match keep:
164    case True{}: SCon{Chr{c}, mark}
165    case False{}: mark
166
167def 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
172def 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.
178def 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.
187def 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.
208def number(s: String) -> Number:
209  number.go(separators(s), True{}, 0, "", 0, 1.0, 0.0, 0.0, 1.0, 0, False{}, False{})
210
211def number.default(num: Number, fallback: F32) -> F32:
212  Number{x, t, valid} = num
213  choose(F32, valid, x, fallback)
214
215def scalar(s: String, fallback: F32) -> F32:
216  number.default(number(s), fallback)
217
218def 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.
224def 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
229def numbers(+s: String) -> List<&2, F32>:
230  numbers.go(String.length(s), s)
231
232def 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
238def 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
244def 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
249def 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
254def trim.both(s: String) -> String:
255  rev(trim(rev(trim(s), "")), "")
256
257def 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
268def 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
273def scan.head(s: Scan) -> String:
274  Scan{h, t} = s
275  h
276
277def 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
281def 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))