csveee 0.2.1

A very fast, parallel CSV parser.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
//! Per-vector field-count verification: extract a boundary-class bitmask
//! `P` (0 delimiter, 1 terminator) and compare it against a pre-built
//! rotation table for the running phase.

use super::isa::Isa;

/// Field-count verifier, one per chunk parse. Supports `1 ≤ N < 64`;
/// wider records route to the DFA backend.
pub(super) struct FieldCounter<I> {
    /// The ISA token `pext` goes through.
    isa: I,
    /// Fields per record.
    n: u32,
    /// Expected `P` pattern per starting phase; `& 63` keeps the load unchecked.
    rotations: [u64; 64],
    /// Boundaries of the current record already seen; `0 ≤ phase < n`.
    phase: u32,
}

impl<I: Isa> FieldCounter<I> {
    /// Build a verifier for records with exactly `n` fields.
    pub(super) fn new(isa: I, n: u32) -> Self {
        assert!(
            (1..64).contains(&n),
            "FieldCounter currently supports only 1 ≤ N < 64 (got {n})",
        );
        let mut rotations = [0u64; 64];
        for p in 0..n {
            rotations[p as usize] = expected_pattern(n, p);
        }
        Self {
            isa,
            n,
            rotations,
            phase: 0,
        }
    }

    /// Verify one vector's boundary pattern: PEXT `term` at the positions
    /// `d_struct` selects, then compare the resulting `P` against this
    /// phase's rotation, masked to `popcnt(d_struct)` bits.
    #[inline]
    pub(super) fn verify(&mut self, d_struct: u64, term: u64) -> bool {
        if I::FAST_PEXT {
            self.verify_pext(d_struct, term)
        } else {
            self.verify_by_terminators(d_struct, term)
        }
    }

    /// [`Self::verify`] without PEXT: walk only the terminators, checking
    /// each lands on boundary `n - 1 - phase + k·n`. One iteration per
    /// record rather than per field, for ISAs that emulate PEXT bit by bit.
    #[inline]
    fn verify_by_terminators(&mut self, d_struct: u64, term: u64) -> bool {
        let count = d_struct.count_ones();
        let mut t = term & d_struct;
        // Boundary index the next terminator must sit at.
        let mut expect = self.n - 1 - self.phase;
        // Boundaries past the last terminator, or `phase + count` without one.
        let mut phase = self.phase + count;
        while t != 0 {
            let below = (t & t.wrapping_neg()) - 1;
            let idx = (d_struct & below).count_ones();
            if idx != expect {
                return false;
            }
            expect += self.n;
            phase = count - idx - 1;
            t &= t - 1;
        }
        // A record reaching `n` boundaries needed a terminator at `n - 1`.
        if phase >= self.n {
            return false;
        }
        self.phase = phase;
        true
    }

    #[inline]
    fn verify_pext(&mut self, d_struct: u64, term: u64) -> bool {
        let count = d_struct.count_ones();
        if count == 0 {
            return true;
        }
        let p = self.isa.pext(term, d_struct);
        let expected = self.rotations[(self.phase & 63) as usize];
        let mask = if count == 64 {
            !0u64
        } else {
            (1u64 << count) - 1
        };
        if (p ^ expected) & mask != 0 {
            return false;
        }
        let carry = if p == 0 { self.phase } else { 0 };
        self.phase = count + p.leading_zeros() - 64 + carry;
        true
    }

    /// Fields-per-record this counter validates.
    pub(super) fn n(&self) -> usize {
        self.n as usize
    }

    /// Current running phase, exposed for tests.
    #[cfg(test)]
    pub(super) fn phase(&self) -> u32 {
        self.phase
    }
}

/// Pin down the record the verifier rejected, as `(record_start, found)`,
/// by walking the bytes from `from` — which must start an already
/// accepted record. `found` is a lower bound past the end of `buf`.
pub(super) fn locate_bad_record(
    buf: &[u8],
    from: usize,
    n: usize,
    delim: u8,
    term: u8,
    term_b: Option<u8>,
    quote: Option<u8>,
) -> (usize, usize) {
    let is_term = |c: u8| c == term || term_b == Some(c);
    let mut i = from.min(buf.len());
    let mut start = i;
    // Fields = delimiters + 1, so an empty record already counts as one.
    let mut fields = 1usize;
    let mut in_quotes = false;

    while i < buf.len() {
        let c = buf[i];
        if Some(c) == quote {
            in_quotes = !in_quotes;
        } else if !in_quotes {
            if c == delim {
                fields += 1;
            } else if is_term(c) {
                if fields != n {
                    return (start, fields);
                }
                // Collapse the run so `start` lands on real content.
                i += 1;
                while i < buf.len() && is_term(buf[i]) {
                    i += 1;
                }
                start = i;
                fields = 1;
                continue;
            }
        }
        i += 1;
    }

    // Out of buffer mid-record: only reachable with too *many* fields.
    debug_assert!(
        fields != n,
        "locate_bad_record found no mismatch at or after {from}",
    );
    (start, fields)
}

/// Expected-`P` pattern for a vector starting at `phase` with `n` fields
/// per record: bit `i` is set iff `(i + phase) mod n == n - 1`, i.e. the
/// `i`-th boundary completes a record.
#[inline]
fn expected_pattern(n: u32, phase: u32) -> u64 {
    let mut out = 0u64;
    let target = (n - 1) as usize;
    let phase = phase as usize;
    let n = n as usize;
    let mut i = 0usize;
    while i < 64 {
        if (i + phase) % n == target {
            out |= 1u64 << i;
        }
        i += 1;
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::parser::simd::isa::CompileTime;

    /// Build a u64 from a list of set-bit positions.
    fn bits(positions: &[u32]) -> u64 {
        let mut m = 0u64;
        for &p in positions {
            assert!(p < 64);
            m |= 1u64 << p;
        }
        m
    }

    // ── expected_pattern ──────────────────────────────────────────

    #[test]
    fn expected_pattern_n1_all_terminators() {
        // N=1: every boundary is a record terminator.
        assert_eq!(expected_pattern(1, 0), !0u64);
    }

    #[test]
    fn expected_pattern_n3_phase0() {
        // N=3: term at boundaries 2, 5, 8, ..., 62.
        let expected: Vec<u32> = (2..64).step_by(3).collect();
        assert_eq!(expected_pattern(3, 0), bits(&expected));
    }

    #[test]
    fn expected_pattern_n3_phase1() {
        // Phase 1: one boundary seen, so terms at 1, 4, 7, ..., 61.
        let expected: Vec<u32> = (1..64).step_by(3).collect();
        assert_eq!(expected_pattern(3, 1), bits(&expected));
    }

    #[test]
    fn expected_pattern_n5_phase1_includes_msb() {
        // Bits where (i+1) mod 5 == 4, i.e. i mod 5 == 3 — bit 63 included.
        let expected: Vec<u32> = (3..64).step_by(5).collect();
        let pat = expected_pattern(5, 1);
        assert_eq!(pat, bits(&expected));
        // Catches the off-by-one a plain u64 rotation would introduce.
        assert_ne!(pat & (1u64 << 63), 0);
    }

    // ── FieldCounter ──────────────────────────────────────────────

    #[test]
    fn verify_n1_all_term_passes() {
        // N=1 means every boundary is a terminator. D=term must hold.
        let mut fc = FieldCounter::new(CompileTime, 1);
        let d = bits(&[2, 5, 8]);
        let term = d;
        assert!(fc.verify(d, term));
    }

    #[test]
    fn verify_n3_clean_record_passes() {
        // `a,b,c\nd,e,f\n`: boundaries {1, 3, 5, 7, 9, 11}, terms {5, 11}.
        let mut fc = FieldCounter::new(CompileTime, 3);
        let d = bits(&[1, 3, 5, 7, 9, 11]);
        let term = bits(&[5, 11]);
        assert!(fc.verify(d, term));
        // 6 boundaries, N=3 → phase wraps to 0.
        assert_eq!(fc.phase(), 0);
    }

    #[test]
    fn verify_n3_partial_record_advances_phase() {
        // One full record + one delim of the next: phase ends at 1.
        let mut fc = FieldCounter::new(CompileTime, 3);
        let d = bits(&[1, 3, 5, 7]);
        let term = bits(&[5]);
        assert!(fc.verify(d, term));
        assert_eq!(fc.phase(), 1);
    }

    #[test]
    fn verify_phase_threads_across_vectors() {
        // V1 = `a,b,` leaves phase 2; V2 = `c\n` brings the awaited term.
        let mut fc = FieldCounter::new(CompileTime, 3);

        // V1: boundaries {1, 3}, no terminator → P = 0b00.
        let d1 = bits(&[1, 3]);
        assert!(fc.verify(d1, 0));
        assert_eq!(fc.phase(), 2);

        // V2: one boundary, a terminator → P = 0b1, as phase 2 expects.
        let d2 = bits(&[1]);
        let term2 = bits(&[1]);
        assert!(fc.verify(d2, term2));
        // The record completes, so the phase wraps to 0.
        assert_eq!(fc.phase(), 0);
    }

    #[test]
    fn verify_missing_terminator_fails() {
        // N=3 expects a terminator at boundary 2, but we give all delims.
        let mut fc = FieldCounter::new(CompileTime, 3);
        let d = bits(&[1, 3, 5]);
        let term = 0;
        assert!(!fc.verify(d, term));
    }

    #[test]
    fn verify_misplaced_terminator_fails() {
        // N=3 expects the term at boundary 2, not boundary 0.
        let mut fc = FieldCounter::new(CompileTime, 3);
        let d = bits(&[1, 3, 5]);
        let term = bits(&[1]);
        assert!(!fc.verify(d, term));
    }

    #[test]
    fn verify_extra_terminator_fails() {
        // Two terminators where only one is expected.
        let mut fc = FieldCounter::new(CompileTime, 3);
        let d = bits(&[1, 3, 5]);
        let term = bits(&[3, 5]);
        assert!(!fc.verify(d, term));
    }

    #[test]
    fn verify_empty_vector_is_a_noop() {
        // No boundaries → no work, phase unchanged.
        let mut fc = FieldCounter::new(CompileTime, 5);
        // Bring phase to a non-zero value first.
        let _ = fc.verify(bits(&[1, 3]), 0);
        let phase_before = fc.phase();
        assert!(fc.verify(0, 0));
        assert_eq!(fc.phase(), phase_before);
    }

    #[test]
    fn terminator_walk_matches_pext() {
        let mut x = 0x9E37_79B9_7F4A_7C15u64;
        let mut rng = move || {
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            x
        };
        for n in [1u32, 2, 3, 5, 16, 63] {
            let mut a = FieldCounter::new(CompileTime, n);
            let mut b = FieldCounter::new(CompileTime, n);
            for _ in 0..200_000 {
                // Sparse boundaries, terminators mostly where they belong.
                let d = rng() & rng() & rng();
                let term = if rng() % 4 == 0 { rng() } else { rng() & rng() };
                let ok = a.verify_pext(d, term);
                assert_eq!(
                    ok,
                    b.verify_by_terminators(d, term),
                    "n {n} d {d:#x} t {term:#x}"
                );
                if ok {
                    assert_eq!(a.phase, b.phase);
                } else {
                    a.phase = 0;
                    b.phase = 0;
                }
            }
        }
    }

    // ── locate_bad_record ─────────────────────────────────────────

    /// `locate_bad_record` with the default dialect: `,` / `\n` / `"`.
    fn locate(buf: &[u8], from: usize, n: usize) -> (usize, usize) {
        locate_bad_record(buf, from, n, b',', b'\n', None, Some(b'"'))
    }

    #[test]
    fn locate_finds_a_short_record() {
        let buf = b"aa,bb,cc\nxx,yy\ndd,ee,ff\n";
        assert_eq!(locate(buf, 0, 3), (9, 2));
    }

    #[test]
    fn locate_finds_a_long_record() {
        // `found` counts the whole record, not just up to the mismatch.
        let buf = b"aa,bb,cc\nww,xx,yy,zz\ndd,ee,ff\n";
        assert_eq!(locate(buf, 0, 3), (9, 4));
    }

    #[test]
    fn locate_skips_quoted_delimiters_and_terminators() {
        // None of the quoted `,`, `\n` or `""` may count as a boundary.
        let buf = b"\"a\nb\",\"c,d\",\"e\"\"f\"\nxx,yy\n";
        let bad = buf.len() - 6;
        assert_eq!(locate(buf, 0, 3), (bad, 2));
    }

    #[test]
    fn locate_collapses_terminator_runs() {
        // Blank lines aren't records: the bad one starts past the run.
        let buf = b"aa,bb,cc\n\n\n\nxx,yy\n";
        assert_eq!(locate(buf, 0, 3), (12, 2));
    }

    #[test]
    fn locate_starts_from_the_given_anchor() {
        // The anchor skips a record that would otherwise look short.
        let buf = b"xx,yy\naa,bb,cc\npp,qq\n";
        assert_eq!(locate(buf, 6, 3), (15, 2));
    }

    #[test]
    fn locate_reports_a_lower_bound_past_the_buffer() {
        // Buffer ends mid-record, so `found` is what has been read.
        let buf = b"aa,bb,cc\nww,xx,yy,zz";
        assert_eq!(locate(buf, 0, 3), (9, 4));
    }

    #[test]
    fn locate_handles_a_final_record_without_a_terminator() {
        let buf = b"aa,bb,cc\nxx,yy";
        assert_eq!(locate(buf, 0, 3), (9, 2));
    }

    #[test]
    fn locate_without_a_quote_char_treats_quotes_as_content() {
        // Quote-free: `"` is content, so the `,` in `"x,1"` separates.
        let buf = b"aa,bb,cc\n\"x,1\",yy,zz\n";
        assert_eq!(
            locate_bad_record(buf, 0, 3, b',', b'\n', None, None),
            (9, 4)
        );
        // With quoting on, `"x,1"` is one field, so this record is short.
        let buf = b"aa,bb,cc\n\"x,1\",yy\n";
        assert_eq!(locate(buf, 0, 3), (9, 2));
    }

    #[test]
    #[should_panic(expected = "1 ≤ N < 64")]
    fn ctor_rejects_n_zero() {
        let _ = FieldCounter::new(CompileTime, 0);
    }

    #[test]
    #[should_panic(expected = "1 ≤ N < 64")]
    fn ctor_rejects_n_64() {
        let _ = FieldCounter::new(CompileTime, 64);
    }
}