src/num.bend

bend-toon-codec@0.1.0.0 · 288 lines · 47 definitions

1import Base
2import bend-toon-codec@0.1.0.0/src/head.bend as Hd
3
4# Decimal text to TOON canonical decimal text, on strings only (no floats, so
5# any number of digits is exact).
6#
7# canon("1.5000") == Some{"1.5"}, canon("-1E+03") == Some{"-1000"},
8# canon("-0.0") == Some{"0"}, canon("1e-7") == Some{"1e-7"}.
9#
10# The value is 0.DDD * 10^P with D free of leading and trailing zeros. P is a
11# U32 biased by 2^31 (`bias`), so comparisons are unsigned. Decimal form for
12# 1e-6 <= |n| < 1e21 (spec section 2), exponent form (`1e+21`, `1.5e-7`)
13# outside it. An exponent of more than nine digits is refused (None).
14
15type Sp is Data:
16  Sp{a: String, b: String}
17
18# A parsed number: sign, integer digits, fraction digits, exponent as a
19# biased-free signed pair.
20type Num is Data:
21  Num{neg: Bool, ip: String, fp: String, eneg: Bool, ex: String}
22
23type Sp2 is Data:
24  Sp2{d: String, p: U32}
25
26def bias() -> U32:
27  2147483648
28
29def sp.cons(+c: U32, +r: Sp) -> Sp:
30  match r:
31    case Sp{a, b}:
32      Sp{SCon{Chr{c}, a}, b}
33
34def sp.pick(+d: Bool, +c: U32, +whole: String, +r: Sp) -> Sp:
35  match d:
36    case True{}:
37      sp.cons(c, r)
38    case False{}:
39      Sp{SNil{}, whole}
40
41# Leading run of ASCII digits, and the rest.
42def span_digits(+s: String) -> Sp:
43  match s:
44    case SNil{}:
45      Sp{SNil{}, SNil{}}
46    case SCon{Chr{c}, t}:
47      sp.pick(Char.is_digit(Chr{c}), c, s, span_digits(t))
48
49def is_zero_char(+c: Char) -> Bool:
50  Char.is_eq(c, '0')
51
52# True when the string is empty or all zeros.
53def all_zeros(+s: String) -> Bool:
54  match s:
55    case SNil{}:
56      True{}
57    case SCon{c, t}:
58      is_zero_char(c) && all_zeros(t)
59
60def num.opt(+ok: Bool, +n: Num) -> Maybe<&2, Num>:
61  match ok:
62    case True{}:
63      Some{n}
64    case False{}:
65      None{}
66
67# After the exponent digits: nothing may follow.
68def exp.done(+neg: Bool, +ip: String, +fp: String, +eneg: Bool, +r: Sp) -> Maybe<&2, Num>:
69  match r:
70    case Sp{+ds, +rest}:
71      num.opt(String.is_empty(rest) && Bool.not(String.is_empty(ds)), Num{neg, ip, fp, eneg, ds})
72
73def exp.sign(+neg: Bool, +ip: String, +fp: String, +eneg: Bool, +s: String) -> Maybe<&2, Num>:
74  exp.done(neg, ip, fp, eneg, span_digits(s))
75
76def exp.part.pick(+plus: Bool, +minus: Bool, +neg: Bool, +ip: String, +fp: String, +s: String) -> Maybe<&2, Num>:
77  match plus minus:
78    case True{} _:
79      exp.sign(neg, ip, fp, False{}, Hd.drop(s))
80    case False{} True{}:
81      exp.sign(neg, ip, fp, True{}, Hd.drop(s))
82    case False{} False{}:
83      exp.sign(neg, ip, fp, False{}, s)
84
85# After `e`: an optional sign, then digits.
86def exp.part(+neg: Bool, +ip: String, +fp: String, +s: String) -> Maybe<&2, Num>:
87  exp.part.pick(Hd.lead(s, 43), Hd.lead(s, 45), neg, ip, fp, s)
88
89def frac.rest.pick(+empty: Bool, +e: Bool, +neg: Bool, +ip: String, +fp: String, +s: String) -> Maybe<&2, Num>:
90  match empty e:
91    case True{} _:
92      Some{Num{neg, ip, fp, False{}, "0"}}
93    case False{} True{}:
94      exp.part(neg, ip, fp, Hd.drop(s))
95    case False{} False{}:
96      None{}
97
98# After the fraction: end of text or an exponent.
99def frac.rest(+neg: Bool, +ip: String, +fp: String, +s: String) -> Maybe<&2, Num>:
100  frac.rest.pick(String.is_empty(s), Hd.lead(s, 101) || Hd.lead(s, 69), neg, ip, fp, s)
101
102def frac.digits(+neg: Bool, +ip: String, +r: Sp) -> Maybe<&2, Num>:
103  match r:
104    case Sp{ds, rest}:
105      match ds:
106        case SNil{}:
107          None{}
108        case _:
109          frac.rest(neg, ip, ds, rest)
110
111def int.rest.pick(+dot: Bool, +neg: Bool, +ip: String, +s: String) -> Maybe<&2, Num>:
112  match dot:
113    case True{}:
114      frac.digits(neg, ip, span_digits(Hd.drop(s)))
115    case False{}:
116      frac.rest(neg, ip, SNil{}, s)
117
118# After the integer digits: a fraction, an exponent, or the end.
119def int.rest(+neg: Bool, +ip: String, +s: String) -> Maybe<&2, Num>:
120  int.rest.pick(Hd.lead(s, 46), neg, ip, s)
121
122def int.digits(+neg: Bool, +r: Sp) -> Maybe<&2, Num>:
123  match r:
124    case Sp{ds, rest}:
125      match ds:
126        case SNil{}:
127          None{}
128        case _:
129          int.rest(neg, ds, rest)
130
131def split.pick(+minus: Bool, +s: String) -> Maybe<&2, Num>:
132  match minus:
133    case True{}:
134      int.digits(True{}, span_digits(Hd.drop(s)))
135    case False{}:
136      int.digits(False{}, span_digits(s))
137
138# `-?digits(.digits)?([eE][+-]?digits)?`, as parts.
139def split(+s: String) -> Maybe<&2, Num>:
140  split.pick(Hd.lead(s, 45), s)
141
142# ---- value to canonical text -----------------------------------------------------
143
144def zeros(+k: U32) -> String:
145  String.repeat("0", U32.to_nat(k))
146
147def len32(+s: String) -> U32:
148  U32.from_nat(String.length(s))
149
150def lead.pick(+z: Bool, +d: String, +p: U32, +r: Sp2) -> Sp2:
151  match z:
152    case True{}:
153      r
154    case False{}:
155      Sp2{d, p}
156
157# Drop leading zeros of the digit string; each one lowers the point position.
158def strip.lead(+d: String, +p: U32) -> Sp2:
159  match d:
160    case SNil{}:
161      Sp2{d, p}
162    case SCon{c, t}:
163      lead.pick(is_zero_char(c), d, p, strip.lead(t, (p - 1 : U32)))
164
165def drop.pick(+z: Bool, +s: String, +rest: String) -> String:
166  match z:
167    case True{}:
168      rest
169    case False{}:
170      s
171
172def drop_zeros(+s: String) -> String:
173  match s:
174    case SNil{}:
175      SNil{}
176    case SCon{c, t}:
177      drop.pick(is_zero_char(c), s, drop_zeros(t))
178
179def strip.trail(+d: String) -> String:
180  String.reverse(drop_zeros(String.reverse(d)))
181
182def mantissa(+d: String) -> String:
183  match d:
184    case SNil{}:
185      "0"
186    case SCon{c, t}:
187      match t:
188        case SNil{}:
189          SCon{c, SNil{}}
190        case _:
191          SCon{c, SCon{'.', t}}
192
193def exp.sign.text(+pos: Bool, +bp: U32) -> String:
194  match pos:
195    case True{}:
196      "e+" ++ U32.show((bp - bias() - 1 : U32))
197    case False{}:
198      "e-" ++ U32.show((bias() + 1 - bp : U32))
199
200# Exponent form: 1e+21, 1.5e-7. `p` is the point position, biased.
201def fmt.exp(+bp: U32, +d: String) -> String:
202  mantissa(d) ++ exp.sign.text(U32.is_gt(bp, bias()), bp)
203
204# 0.000ddd for a point position of 0 down to -5.
205def fmt.small(+bp: U32, +d: String) -> String:
206  "0." ++ zeros((bias() - bp : U32)) ++ d
207
208def fmt.int.pick(+fits: Bool, +k: U32, +d: String) -> String:
209  match fits:
210    case True{}:
211      d ++ zeros((k - len32(d) : U32))
212    case False{}:
213      String.take(d, U32.to_nat(k)) ++ "." ++ String.drop(d, U32.to_nat(k))
214
215def fmt.int(+bp: U32, +d: String) -> String:
216  fmt.int.pick(U32.is_le(len32(d), (bp - bias() : U32)), (bp - bias() : U32), d)
217
218def fmt.mid(+le0: Bool, +bp: U32, +d: String) -> String:
219  match le0:
220    case True{}:
221      fmt.small(bp, d)
222    case False{}:
223      fmt.int(bp, d)
224
225def fmt.low(+exp: Bool, +bp: U32, +d: String) -> String:
226  match exp:
227    case True{}:
228      fmt.exp(bp, d)
229    case False{}:
230      fmt.mid(U32.is_le(bp, bias()), bp, d)
231
232# Digits (no leading or trailing zeros) and biased point position to text.
233def fmt(+bp: U32, +d: String) -> String:
234  fmt.low(U32.is_gt(bp, (bias() + 21 : U32)) || U32.is_lt(bp, (bias() - 5 : U32)), bp, d)
235
236def sign.text(+neg: Bool) -> String:
237  match neg:
238    case True{}:
239      "-"
240    case False{}:
241      ""
242
243def exp.val.pick(+m: Maybe<&2, U32>) -> U32:
244  match m:
245    case Some{n}:
246      n
247    case None{}:
248      0
249
250def exp.val(+s: String) -> U32:
251  exp.val.pick(U32.read(s))
252
253def read.exp(+eneg: Bool, +ex: String) -> U32:
254  match eneg:
255    case True{}:
256      (bias() - exp.val(ex) : U32)
257    case False{}:
258      (bias() + exp.val(ex) : U32)
259
260def canon.zero(+z: Bool, +neg: Bool, +d: String, +p: U32) -> String:
261  match z:
262    case True{}:
263      "0"
264    case False{}:
265      sign.text(neg) ++ fmt(p, strip.trail(d))
266
267def canon.digits(+neg: Bool, +s: Sp2) -> String:
268  match s:
269    case Sp2{d, p}:
270      canon.zero(String.is_empty(d), neg, d, p)
271
272def canon.parts(+ok: Bool, +neg: Bool, +ip: String, +fp: String, +eneg: Bool, +ex: String) -> Maybe<&2, String>:
273  match ok:
274    case False{}:
275      None{}
276    case True{}:
277      Some{canon.digits(neg, strip.lead(ip ++ fp, (read.exp(eneg, ex) + len32(ip) : U32)))}
278
279def canon.opt(+m: Maybe<&2, Num>) -> Maybe<&2, String>:
280  match m:
281    case None{}:
282      None{}
283    case Some{Num{neg, ip, fp, eneg, ex}}:
284      canon.parts(Nat.is_le(String.length(ex), 9n), neg, ip, fp, eneg, ex)
285
286# Canonical text of a decimal number, None when `s` is not one.
287def canon(+s: String) -> Maybe<&2, String>:
288  canon.opt(split(s))