csv.bend

bend-kit-csv@0.3.0.0 · 308 lines · 34 definitions

1# CSV (RFC 4180) over bytes: a record cursor, a whole-document parse, and an encoder. Source: https://github.com/paymog/bend-kit/tree/main/csv
2import Base
3import bend-kit-bytes@0.3.3.0/bytes.bend as Bytes
4
5# Fields are Bytes, taken as they are: no charset, no trimming. A record ends at
6# CRLF, LF, or a lone CR, and the last line end is optional. A quoted field may
7# hold commas, CR, LF, and "" for one quote. An empty line has no fields.
8#   import ./csv/csv.bend as Csv
9
10# The unread bytes and the offset of the next record.
11type Cur is Type:
12  Cur{src: Bytes.Bytes, at: U32}
13
14# One step of the cursor: a record and the cursor after it, the end of input, or
15# the offset of the first byte that breaks RFC 4180.
16type Next is Type:
17  Row{fields: List<&1, Bytes.Bytes>, cur: Cur}
18  End{}
19  Bad{at: U32}
20
21# Reader
22# ------
23# A field's bytes are src[s..e]. esc says the field was quoted and holds "".
24type Span is Data:
25  Span{s: U32, e: U32, esc: Bool}
26
27# Spans are latest first.
28type Scan is Data:
29  SRow{sp: List<&2, Span>, at: U32}
30  SBad{at: U32}
31
32# Start: before a field. Unq: in an unquoted field. Q: in a quoted field.
33# QQ: just past a quote inside a quoted field. CR: just past a record's CR.
34type St is Data:
35  SStart{}
36  SUnq{}
37  SQ{}
38  SQQ{}
39  SCR{}
40
41# Byte i, or 256 past the end.
42def pk.if(ok: Bool, a: Array<U32>, +i: U32) -> Array<U32> & U32:
43  match ok:
44    case True{}:
45      Bytes.peek(a, i)
46    case False{}:
47      (a, 256)
48
49def pk(a: Array<U32>, +len: U32, +i: U32) -> Array<U32> & U32:
50  pk.if(U32.is_lt(i, len), a, i)
51
52# An empty line has no fields; a trailing comma adds an empty field.
53def start.sp(sp: List<&2, Span>, +i: U32) -> List<&2, Span>:
54  match sp:
55    case Nil{}:
56      Nil{}
57    case Con{h, t}:
58      Span{i, i, False{}} <> Con{h, t}
59
60
61# r holds byte i. s is where the open field starts. Every step but the last reads one byte.
62def rec.go(f: Nat, st: St, r: Array<U32> & U32, +len: U32, +i: U32, +s: U32, +esc: Bool, +sp: List<&2, Span>) -> Array<U32> & Scan:
63  match f:
64    case 0n:
65      (a, c) = r
66      (a, SBad{i})
67    case 1n+p:
68      match st:
69        case SStart{}:
70          (a, +c) = r
71          match c:
72            case 34:
73              rec.go(p, SQ{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, sp)
74            case 44:
75              rec.go(p, SStart{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, Span{i, i, False{}} <> sp)
76            case 10:
77              (a, SRow{start.sp(sp, i), (i + 1 : U32)})
78            case 13:
79              rec.go(p, SCR{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, start.sp(sp, i))
80            case 256:
81              (a, SRow{start.sp(sp, i), i})
82            case _:
83              rec.go(p, SUnq{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), i, False{}, sp)
84        case SUnq{}:
85          (a, +c) = r
86          match c:
87            case 44:
88              rec.go(p, SStart{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, Span{s, i, False{}} <> sp)
89            case 10:
90              (a, SRow{Span{s, i, False{}} <> sp, (i + 1 : U32)})
91            case 13:
92              rec.go(p, SCR{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, Span{s, i, False{}} <> sp)
93            case 256:
94              (a, SRow{Span{s, i, False{}} <> sp, i})
95            case 34:
96              (a, SBad{i})
97            case _:
98              rec.go(p, SUnq{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), s, False{}, sp)
99        case SQ{}:
100          (a, +c) = r
101          match c:
102            case 34:
103              rec.go(p, SQQ{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), s, esc, sp)
104            case 256:
105              (a, SBad{i})
106            case _:
107              rec.go(p, SQ{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), s, esc, sp)
108        case SQQ{}:
109          (a, +c) = r
110          match c:
111            case 34:
112              rec.go(p, SQ{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), s, True{}, sp)
113            case 44:
114              rec.go(p, SStart{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, Span{s, (i - 1 : U32), esc} <> sp)
115            case 10:
116              (a, SRow{Span{s, (i - 1 : U32), esc} <> sp, (i + 1 : U32)})
117            case 13:
118              rec.go(p, SCR{}, pk(a, len, (i + 1 : U32)), len, (i + 1 : U32), (i + 1 : U32), False{}, Span{s, (i - 1 : U32), esc} <> sp)
119            case 256:
120              (a, SRow{Span{s, (i - 1 : U32), esc} <> sp, i})
121            case _:
122              (a, SBad{i})
123        case SCR{}:
124          (a, +c) = r
125          match c:
126            case 10:
127              (a, SRow{sp, (i + 1 : U32)})
128            case _:
129              (a, SRow{sp, i})
130
131def q() -> Bytes.Bytes:
132  Bytes.from_string("\"")
133
134def qq() -> Bytes.Bytes:
135  Bytes.from_string("\"\"")
136
137# Pieces between "" pairs, latest first, with one quote between each.
138def unq.go(xs: List<&1, Bytes.Bytes>, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
139  match xs:
140    case Nil{}:
141      acc
142    case Con{h, t}:
143      unq.go(t, h <> q() <> acc)
144
145def unq.of(xs: List<&1, Bytes.Bytes>) -> Bytes.Bytes:
146  match xs:
147    case Nil{}:
148      Bytes.new(0)
149    case Con{h, t}:
150      Bytes.concat(List.reverse(&1, Bytes.Bytes, unq.go(t, [h])))
151
152# A quoted field's inner bytes with each "" as one quote. Quotes inside come in pairs.
153def field.of(esc: Bool, b: Bytes.Bytes) -> Bytes.Bytes:
154  match esc:
155    case True{}:
156      unq.of(Bytes.split(b, "\"\""))
157    case False{}:
158      b
159
160def cut.fin(+m: U32, +esc: Bool, r: Array<U32> & Array<U32>, acc: List<&1, Bytes.Bytes>) -> Array<U32> & List<&1, Bytes.Bytes>:
161  (a, d) = r
162  (a, field.of(esc, Bytes.Bytes{m, d}) <> acc)
163
164# Spans latest first give fields in order.
165def cut.go(sp: List<&2, Span>, r: Array<U32> & List<&1, Bytes.Bytes>) -> Array<U32> & List<&1, Bytes.Bytes>:
166  match sp:
167    case Nil{}:
168      r
169    case Con{Span{+s, +e, +esc}, t}:
170      (a, acc) = r
171      +m = (e - s : U32)
172      cut.go(t, cut.fin(m, esc, Bytes.copy(m, a, Bytes.alloc(m), s, 0), acc))
173
174def next.fin(+len: U32, +at: U32, r: Array<U32> & List<&1, Bytes.Bytes>) -> Next:
175  (a, fs) = r
176  Row{fs, Cur{Bytes.Bytes{len, a}, at}}
177
178def next.row(+len: U32, r: Array<U32> & Scan) -> Next:
179  (a, sc) = r
180  match sc:
181    case SRow{sp, +at}:
182      next.fin(len, at, cut.go(sp, (a, Nil{})))
183    case SBad{+at}:
184      Bad{at}
185
186def next.if(more: Bool, +len: U32, buf: Array<U32>, +at: U32) -> Next:
187  match more:
188    case False{}:
189      End{}
190    case True{}:
191      next.row(len, rec.go(U32.to_nat((len - at + 1 : U32)), SStart{}, pk(buf, len, at), len, at, at, False{}, Nil{}))
192
193# A cursor at the first record.
194def cursor(b: Bytes.Bytes) -> Cur:
195  Cur{b, 0}
196
197# The next record, End at the end of input, or Bad with the offset of the first bad byte.
198def next(c: Cur) -> Next:
199  Cur{Bytes.Bytes{+len, buf}, +at} = c
200  next.if(U32.is_lt(at, len), len, buf, at)
201
202# Each record reads at least one byte, so len + 1 steps are enough.
203def parse.go(f: Nat, nx: Next, acc: List<&1, List<&1, Bytes.Bytes>>) -> Result<&1, &1, U32, List<&1, List<&1, Bytes.Bytes>>>:
204  match f:
205    case 0n:
206      Fail{0}
207    case 1n+p:
208      match nx:
209        case End{}:
210          Done{List.reverse(&1, List<&1, Bytes.Bytes>, acc)}
211        case Bad{+at}:
212          Fail{at}
213        case Row{fs, cur}:
214          parse.go(p, next(cur), fs <> acc)
215
216# Every record, or Fail with the offset of the first bad byte.
217def parse(b: Bytes.Bytes) -> Result<&1, &1, U32, List<&1, List<&1, Bytes.Bytes>>>:
218  Bytes.Bytes{+len, buf} = b
219  parse.go(U32.to_nat((len + 1 : U32)), next(Cur{Bytes.Bytes{len, buf}, 0}), Nil{})
220
221# Writer
222# ------
223# Does a byte from i on need quotes? n counts the bytes left.
224def needs.go(n: Nat, r: Array<U32> & U32, +i: U32) -> Array<U32> & Bool:
225  match n:
226    case 0n:
227      (a, c) = r
228      (a, False{})
229    case 1n+p:
230      (a, +c) = r
231      match c:
232        case 34:
233          (a, True{})
234        case 44:
235          (a, True{})
236        case 10:
237          (a, True{})
238        case 13:
239          (a, True{})
240        case _:
241          needs.go(p, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32))
242
243# The pieces after the first, each after "".
244def enc.rest(xs: List<&1, Bytes.Bytes>, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
245  match xs:
246    case Nil{}:
247      acc
248    case Con{h, t}:
249      enc.rest(t, h <> qq() <> acc)
250
251def enc.parts(xs: List<&1, Bytes.Bytes>, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
252  match xs:
253    case Nil{}:
254      acc
255    case Con{h, t}:
256      q() <> enc.rest(t, h <> q() <> acc)
257
258def enc.pick(+len: U32, r: Array<U32> & Bool, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
259  (a, quote) = r
260  match quote:
261    case False{}:
262      Bytes.Bytes{len, a} <> acc
263    case True{}:
264      enc.parts(Bytes.split(Bytes.Bytes{len, a}, "\""), acc)
265
266# Pieces are latest first. A field is quoted only when it holds a quote, comma, CR, or LF.
267def enc.field(f: Bytes.Bytes, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
268  Bytes.Bytes{+len, buf} = f
269  enc.pick(len, needs.go(U32.to_nat(len), Bytes.peek(buf, 0), 0), acc)
270
271def enc.more(fs: List<&1, Bytes.Bytes>, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
272  match fs:
273    case Nil{}:
274      acc
275    case Con{h, t}:
276      enc.more(t, enc.field(h, Bytes.from_string(",") <> acc))
277
278def enc.only.if(empty: Bool, f: Bytes.Bytes, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
279  match empty:
280    case True{}:
281      Bytes.from_string("\"\"") <> acc
282    case False{}:
283      enc.field(f, acc)
284
285def enc.only(f: Bytes.Bytes, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
286  Bytes.Bytes{+len, buf} = f
287  enc.only.if(U32.is_eq(len, 0), Bytes.Bytes{len, buf}, acc)
288
289
290def enc.fields(fs: List<&1, Bytes.Bytes>, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
291  match fs:
292    case Nil{}:
293      acc
294    case Con{h, Nil{}}:
295      enc.only(h, acc)
296    case Con{h, t}:
297      enc.more(t, enc.field(h, acc))
298
299def enc.recs(rs: List<&1, List<&1, Bytes.Bytes>>, acc: List<&1, Bytes.Bytes>) -> List<&1, Bytes.Bytes>:
300  match rs:
301    case Nil{}:
302      acc
303    case Con{r, t}:
304      enc.recs(t, Bytes.from_string("\r\n") <> enc.fields(r, acc))
305
306# Records as RFC 4180 text: fields joined by commas, each record ended by CRLF.
307def encode(rs: List<&1, List<&1, Bytes.Bytes>>) -> Bytes.Bytes:
308  Bytes.concat(List.reverse(&1, Bytes.Bytes, enc.recs(rs, Nil{})))