Vince's CSV Parser
Loading...
Searching...
No Matches
scanner.hpp
1#pragma once
2
3#include "../parser/driver.hpp"
4#include "diagnostics.hpp"
5
6#include <cmath>
7#include <limits>
8
9#if CSV_ENABLE_THREADS
10
11namespace csv {
12 namespace internals {
13 namespace speculative {
14 constexpr size_t CSV_SPECULATIVE_PREFIX_SIZE = 64 * 1024;
15
16 struct PrefixScanResult {
17 ParserDFAState ending_state;
18 size_t records_seen = 0;
19 size_t first_record_end = (std::numeric_limits<size_t>::max)();
20 size_t total_states = 0;
21 size_t unquoted_states = 0;
22 size_t max_record_length = 0;
23 size_t quoted_fields = 0;
24 size_t first_quote_open = (std::numeric_limits<size_t>::max)();
25 size_t first_quote_close = (std::numeric_limits<size_t>::max)();
26 long double log_other_start_valid_probability = 0;
27 };
28
29 struct ChunkSpeculation {
30 size_t sequence_number = 0;
31 size_t offset = 0;
32 size_t length = 0;
33 size_t prefix_length = 0;
34 ParserDFAState assumed_start_state;
35 PrefixScanResult outside_scan;
36 PrefixScanResult inside_scan;
37 bool ambiguous = false;
38 bool used_probability_model = false;
39 bool used_record_size_heuristic = false;
40 long double quoted_start_odds = 0;
41 };
42
43 inline void observe_speculation(
44 SpeculativeParseDiagnostics& diagnostics,
45 const ChunkSpeculation& speculation
46 ) noexcept {
47 diagnostics.chunks++;
48 if (speculation.ambiguous) {
49 diagnostics.ambiguous_chunks++;
50 }
51 if (speculation.used_probability_model) {
52 diagnostics.probability_model_chunks++;
53 }
54 if (speculation.used_record_size_heuristic) {
55 diagnostics.record_size_heuristic_chunks++;
56 }
57 if (speculation.assumed_start_state.quote_escape) {
58 diagnostics.assumed_quoted_chunks++;
59 }
60 else {
61 diagnostics.assumed_unquoted_chunks++;
62 }
63 }
64
65 class SpeculativeScanner {
66 public:
67 explicit SpeculativeScanner(
68 const ParseFlagMap& parse_flags,
69 size_t prefix_bytes = CSV_SPECULATIVE_PREFIX_SIZE
70 ) : parse_flags_(parse_flags), prefix_bytes_(prefix_bytes) {}
71
72 ChunkSpeculation speculate(
73 size_t sequence_number,
74 size_t offset,
76 ) const {
77 const size_t prefix_length = std::min(chunk.size(), this->prefix_bytes_);
78 const csv::string_view prefix(chunk.data(), prefix_length);
79
80 ChunkSpeculation result;
81 result.sequence_number = sequence_number;
82 result.offset = offset;
83 result.length = chunk.size();
84 result.prefix_length = prefix_length;
85 this->scan_prefix(prefix, result.outside_scan, result.inside_scan);
86 result.ambiguous = this->is_ambiguous(result.outside_scan, result.inside_scan);
87 result.assumed_start_state = this->choose_start_state(result);
88 return result;
89 }
90
91 private:
92 CONSTEXPR_17 ParseFlags parse_flag(const char ch) const noexcept {
93 return parse_flags_.data()[ch + CHAR_OFFSET];
94 }
95
96 static constexpr size_t missing_index() noexcept {
97 return (std::numeric_limits<size_t>::max)();
98 }
99
100 struct PrefixCounterState {
101 PrefixScanResult result;
102 size_t record_start = 0;
103 size_t quoted_start = missing_index();
104 bool quoted_field_partial = false;
105 long double separator_weight = 0;
106 };
107
108 void observe_quoted_span(
109 PrefixCounterState& state,
110 size_t field_length
111 ) const noexcept {
112 state.result.quoted_fields++;
113
114 if (field_length == 0) {
115 return;
116 }
117
118 if (state.quoted_field_partial || field_length == 1) {
119 state.separator_weight += 1;
120 }
121 else {
122 state.separator_weight += 2;
123 }
124 }
125
126 void finish_record(PrefixCounterState& state, size_t record_end) const noexcept {
127 state.result.records_seen++;
128 const size_t record_length = record_end - state.record_start;
129 if (record_length > state.result.max_record_length) {
130 state.result.max_record_length = record_length;
131 }
132 state.record_start = record_end;
133 }
134
135 bool is_separator_or_record_end(ParseFlags flag) const noexcept {
136 return flag == ParseFlags::DELIMITER
137 || flag == ParseFlags::CARRIAGE_RETURN
138 || flag == ParseFlags::NEWLINE;
139 }
140
141 bool quote_can_open(csv::string_view prefix, size_t pos) const noexcept {
142 if (pos == 0) {
143 return true;
144 }
145
146 return this->is_separator_or_record_end(this->parse_flag(prefix[pos - 1]));
147 }
148
149 bool quote_can_close(csv::string_view prefix, size_t pos) const noexcept {
150 if (pos + 1 >= prefix.size()) {
151 return true;
152 }
153
154 return this->is_separator_or_record_end(this->parse_flag(prefix[pos + 1]));
155 }
156
157 void start_quoted_span(PrefixCounterState& state, size_t pos, bool partial) const noexcept {
158 state.quoted_start = pos;
159 state.quoted_field_partial = partial;
160 }
161
162 void finish_quoted_span(PrefixCounterState& state, size_t pos) const noexcept {
163 if (state.quoted_start == this->missing_index()) {
164 return;
165 }
166
167 this->observe_quoted_span(state, pos - state.quoted_start);
168 state.quoted_start = this->missing_index();
169 state.quoted_field_partial = false;
170 }
171
172 void finish_partial_quoted_span(PrefixCounterState& state, size_t prefix_size) const noexcept {
173 if (state.quoted_start == this->missing_index()) {
174 return;
175 }
176
177 this->observe_quoted_span(state, prefix_size - state.quoted_start);
178 state.quoted_start = this->missing_index();
179 state.quoted_field_partial = false;
180 }
181
182 void finish_scan(
183 PrefixCounterState& state,
184 csv::string_view prefix,
185 bool ending_state,
186 long double log_separator_probability
187 ) const noexcept {
188 const size_t tail_length = prefix.size() - state.record_start;
189 if (tail_length > state.result.max_record_length) {
190 state.result.max_record_length = tail_length;
191 }
192 state.result.ending_state = ParserDFAState(ending_state);
193 state.result.log_other_start_valid_probability = state.separator_weight == 0
194 ? 0
195 : state.separator_weight * log_separator_probability;
196 }
197
198 // The speculative pass should be much cheaper than parsing. This
199 // is a quote-parity scan: q-o / o-q pattern evidence usually
200 // decides the starting state, and the probability model is left
201 // for the rare ambiguous prefix.
202 void scan_prefix(
203 csv::string_view prefix,
204 PrefixScanResult& outside_scan,
205 PrefixScanResult& inside_scan
206 ) const {
207 using internals::ParseFlags;
208
209 PrefixCounterState outside;
210 PrefixCounterState inside;
211 this->start_quoted_span(inside, 0, true);
212
213 bool odd_quotes = false;
214 size_t separators = 0;
215
216 for (size_t pos = 0; pos < prefix.size();) {
217 const ParseFlags flag = this->parse_flag(prefix[pos]);
218 size_t width = 1;
219 if (flag == ParseFlags::CARRIAGE_RETURN
220 && pos + 1 < prefix.size()
221 && this->parse_flag(prefix[pos + 1]) == ParseFlags::NEWLINE) {
222 width = 2;
223 }
224
225 outside.result.total_states += width;
226 inside.result.total_states += width;
227 if (!odd_quotes) {
228 outside.result.unquoted_states += width;
229 }
230 else {
231 inside.result.unquoted_states += width;
232 }
233
234 if (flag == ParseFlags::DELIMITER || flag == ParseFlags::CARRIAGE_RETURN || flag == ParseFlags::NEWLINE) {
235 separators++;
236 }
237
238 if (flag == ParseFlags::QUOTE) {
239 if (outside.result.first_quote_open == this->missing_index()
240 && this->quote_can_open(prefix, pos)) {
241 outside.result.first_quote_open = pos;
242 }
243 if (inside.result.first_quote_close == this->missing_index()
244 && this->quote_can_close(prefix, pos)) {
245 inside.result.first_quote_close = pos;
246 }
247
248 if (odd_quotes) {
249 this->finish_quoted_span(outside, pos);
250 this->start_quoted_span(inside, pos + 1, false);
251 }
252 else {
253 this->start_quoted_span(outside, pos + 1, false);
254 this->finish_quoted_span(inside, pos);
255 }
256
257 odd_quotes = !odd_quotes;
258 pos++;
259 continue;
260 }
261
262 if (flag == ParseFlags::CARRIAGE_RETURN || flag == ParseFlags::NEWLINE) {
263 const size_t record_end = pos + width;
264 if (!odd_quotes) {
265 this->finish_record(outside, record_end);
266 if (outside.result.first_record_end == this->missing_index()) {
267 outside.result.first_record_end = record_end;
268 }
269 }
270 else {
271 this->finish_record(inside, record_end);
272 if (inside.result.first_record_end == this->missing_index()) {
273 inside.result.first_record_end = record_end;
274 }
275 }
276 }
277
278 pos += width;
279 }
280
281 const long double separator_probability = prefix.empty()
282 ? 0
283 : static_cast<long double>(separators) / static_cast<long double>(prefix.size());
284 const long double log_separator_probability = separator_probability > 0
285 ? std::log(separator_probability)
286 : -std::numeric_limits<long double>::infinity();
287
288 if (odd_quotes) {
289 this->finish_partial_quoted_span(outside, prefix.size());
290 }
291 else {
292 this->finish_partial_quoted_span(inside, prefix.size());
293 }
294
295 this->finish_scan(outside, prefix, odd_quotes, log_separator_probability);
296 this->finish_scan(inside, prefix, !odd_quotes, log_separator_probability);
297 outside_scan = outside.result;
298 inside_scan = inside.result;
299 }
300
301 long double unquoted_ratio(const PrefixScanResult& scan) const noexcept {
302 if (scan.total_states == 0) {
303 return scan.ending_state.quote_escape ? 0 : 1;
304 }
305
306 return static_cast<long double>(scan.unquoted_states)
307 / static_cast<long double>(scan.total_states);
308 }
309
310 long double quoted_odds_from_probability_model(
311 const PrefixScanResult& outside_scan,
312 const PrefixScanResult& inside_scan
313 ) const noexcept {
314 const long double log_k = inside_scan.log_other_start_valid_probability
315 - outside_scan.log_other_start_valid_probability;
316
317 if (log_k > 64) {
318 return std::numeric_limits<long double>::infinity();
319 }
320 if (log_k < -64) {
321 return 0;
322 }
323
324 const long double k = std::exp(log_k);
325 const long double u_u = this->unquoted_ratio(outside_scan);
326 const long double u_q = this->unquoted_ratio(inside_scan);
327 const long double a = u_q;
328 const long double b = u_u - k * (1 - u_q);
329 const long double c = -k * (1 - u_u);
330 const long double epsilon = 1e-18L;
331
332 if (std::fabs(a) < epsilon) {
333 if (std::fabs(b) < epsilon) {
334 return k > 1 ? std::numeric_limits<long double>::infinity() : 0;
335 }
336
337 const long double linear_root = -c / b;
338 return linear_root > 0 ? linear_root : 0;
339 }
340
341 const long double discriminant = b * b - 4 * a * c;
342 if (discriminant < 0) {
343 return 1;
344 }
345
346 const long double root = (-b + std::sqrt(discriminant)) / (2 * a);
347 return root > 0 ? root : 0;
348 }
349
350 int pattern_start_state(
351 const PrefixScanResult& outside_scan,
352 const PrefixScanResult& inside_scan
353 ) const noexcept {
354 const size_t outside_open = outside_scan.first_quote_open;
355 const size_t inside_close = inside_scan.first_quote_close;
356 const size_t missing = (std::numeric_limits<size_t>::max)();
357
358 if (outside_open == missing && inside_close == missing) {
359 return -1;
360 }
361
362 if (outside_open < inside_close) {
363 return 0;
364 }
365
366 if (inside_close < outside_open) {
367 return 1;
368 }
369
370 return -1;
371 }
372
373 ParserDFAState choose_start_state(ChunkSpeculation& speculation) const noexcept {
374 const PrefixScanResult& outside_scan = speculation.outside_scan;
375 const PrefixScanResult& inside_scan = speculation.inside_scan;
376 const int pattern_state = this->pattern_start_state(outside_scan, inside_scan);
377
378 if (pattern_state == 0) {
379 return ParserDFAState(false);
380 }
381
382 if (pattern_state == 1) {
383 return ParserDFAState(true);
384 }
385
386 if (outside_scan.records_seen > 0 && inside_scan.records_seen == 0) {
387 return ParserDFAState(false);
388 }
389
390 if (inside_scan.records_seen > 0 && outside_scan.records_seen == 0) {
391 return ParserDFAState(true);
392 }
393
394 if (speculation.ambiguous) {
395 speculation.quoted_start_odds = this->quoted_odds_from_probability_model(
396 outside_scan,
397 inside_scan
398 );
399
400 if (speculation.quoted_start_odds > 1.000001L) {
401 speculation.used_probability_model = true;
402 return ParserDFAState(true);
403 }
404
405 if (speculation.quoted_start_odds < 0.999999L) {
406 speculation.used_probability_model = true;
407 return ParserDFAState(false);
408 }
409
410 speculation.used_record_size_heuristic = true;
411 return inside_scan.max_record_length < outside_scan.max_record_length
412 ? ParserDFAState(true)
413 : ParserDFAState(false);
414 }
415
416 return ParserDFAState(false);
417 }
418
419 bool is_ambiguous(
420 const PrefixScanResult& outside_scan,
421 const PrefixScanResult& inside_scan
422 ) const noexcept {
423 if (this->pattern_start_state(outside_scan, inside_scan) != -1) {
424 return false;
425 }
426
427 return (outside_scan.records_seen == inside_scan.records_seen)
428 || (outside_scan.records_seen > 0 && inside_scan.records_seen > 0);
429 }
430
431 ParseFlagMap parse_flags_;
432 size_t prefix_bytes_;
433 };
434 }
435 }
436}
437
438#endif
std::array< ParseFlags, 256 > ParseFlagMap
An array which maps ASCII chars to a parsing flag.
Definition common.hpp:495
ParseFlags
An enum used for describing the significance of each character with respect to CSV parsing.
Definition common.hpp:456
The all encompassing namespace.
constexpr unsigned CHAR_OFFSET
Offset to convert char into array index.
Definition common.hpp:505
std::string_view string_view
The string_view class used by this library.
Definition common.hpp:182