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 2 import Base 3 import 0x49814d83de8f70993a43e1002be29ecd/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. 11 type 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. 16 type 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 "". 24 type Span is Data: 25 Span{s: U32, e: U32, esc: Bool} 26 27 # Spans are latest first. 28 type 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. 34 type St is Data: 35 SStart{} 36 SUnq{} 37 SQ{} 38 SQQ{} 39 SCR{} 40 41 # Byte i, or 256 past the end. 42 def pk.if(ok: Bool, a: Array, +i: U32) -> Array & U32: 43 match ok: 44 case True{}: 45 Bytes.peek(a, i) 46 case False{}: 47 (a, 256) 48 49 def pk(a: Array, +len: U32, +i: U32) -> Array & 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. 53 def 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. 62 def rec.go(f: Nat, st: St, r: Array & U32, +len: U32, +i: U32, +s: U32, +esc: Bool, +sp: List<&2, Span>) -> Array & 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 131 def q() -> Bytes.Bytes: 132 Bytes.from_string("\"") 133 134 def qq() -> Bytes.Bytes: 135 Bytes.from_string("\"\"") 136 137 # Pieces between "" pairs, latest first, with one quote between each. 138 def 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 145 def 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. 153 def 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 160 def cut.fin(+m: U32, +esc: Bool, r: Array & Array, acc: List<&1, Bytes.Bytes>) -> Array & 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. 165 def cut.go(sp: List<&2, Span>, r: Array & List<&1, Bytes.Bytes>) -> Array & 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 174 def next.fin(+len: U32, +at: U32, r: Array & List<&1, Bytes.Bytes>) -> Next: 175 (a, fs) = r 176 Row{fs, Cur{Bytes.Bytes{len, a}, at}} 177 178 def next.row(+len: U32, r: Array & 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 186 def next.if(more: Bool, +len: U32, buf: Array, +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. 194 def 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. 198 def 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. 203 def 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. 217 def 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. 224 def needs.go(n: Nat, r: Array & U32, +i: U32) -> Array & 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 "". 244 def 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 251 def 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 258 def enc.pick(+len: U32, r: Array & 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. 267 def 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 271 def 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 278 def 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 285 def 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 290 def 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 299 def 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. 307 def encode(rs: List<&1, List<&1, Bytes.Bytes>>) -> Bytes.Bytes: 308 Bytes.concat(List.reverse(&1, Bytes.Bytes, enc.recs(rs, Nil{})))