3#include "../parser/driver.hpp"
4#include "diagnostics.hpp"
13 namespace speculative {
14 constexpr size_t CSV_SPECULATIVE_PREFIX_SIZE = 64 * 1024;
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;
29 struct ChunkSpeculation {
30 size_t sequence_number = 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;
43 inline void observe_speculation(
44 SpeculativeParseDiagnostics& diagnostics,
45 const ChunkSpeculation& speculation
48 if (speculation.ambiguous) {
49 diagnostics.ambiguous_chunks++;
51 if (speculation.used_probability_model) {
52 diagnostics.probability_model_chunks++;
54 if (speculation.used_record_size_heuristic) {
55 diagnostics.record_size_heuristic_chunks++;
57 if (speculation.assumed_start_state.quote_escape) {
58 diagnostics.assumed_quoted_chunks++;
61 diagnostics.assumed_unquoted_chunks++;
65 class SpeculativeScanner {
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) {}
72 ChunkSpeculation speculate(
73 size_t sequence_number,
77 const size_t prefix_length = std::min(chunk.size(), this->prefix_bytes_);
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);
92 CONSTEXPR_17
ParseFlags parse_flag(
const char ch)
const noexcept {
96 static constexpr size_t missing_index() noexcept {
97 return (std::numeric_limits<size_t>::max)();
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;
108 void observe_quoted_span(
109 PrefixCounterState& state,
112 state.result.quoted_fields++;
114 if (field_length == 0) {
118 if (state.quoted_field_partial || field_length == 1) {
119 state.separator_weight += 1;
122 state.separator_weight += 2;
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;
132 state.record_start = record_end;
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;
146 return this->is_separator_or_record_end(this->parse_flag(prefix[pos - 1]));
150 if (pos + 1 >= prefix.size()) {
154 return this->is_separator_or_record_end(this->parse_flag(prefix[pos + 1]));
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;
162 void finish_quoted_span(PrefixCounterState& state,
size_t pos)
const noexcept {
163 if (state.quoted_start == this->missing_index()) {
167 this->observe_quoted_span(state, pos - state.quoted_start);
168 state.quoted_start = this->missing_index();
169 state.quoted_field_partial =
false;
172 void finish_partial_quoted_span(PrefixCounterState& state,
size_t prefix_size)
const noexcept {
173 if (state.quoted_start == this->missing_index()) {
177 this->observe_quoted_span(state, prefix_size - state.quoted_start);
178 state.quoted_start = this->missing_index();
179 state.quoted_field_partial =
false;
183 PrefixCounterState& state,
186 long double log_separator_probability
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;
192 state.result.ending_state = ParserDFAState(ending_state);
193 state.result.log_other_start_valid_probability = state.separator_weight == 0
195 : state.separator_weight * log_separator_probability;
204 PrefixScanResult& outside_scan,
205 PrefixScanResult& inside_scan
207 using internals::ParseFlags;
209 PrefixCounterState outside;
210 PrefixCounterState inside;
211 this->start_quoted_span(inside, 0,
true);
213 bool odd_quotes =
false;
214 size_t separators = 0;
216 for (
size_t pos = 0; pos < prefix.size();) {
217 const ParseFlags flag = this->parse_flag(prefix[pos]);
219 if (flag == ParseFlags::CARRIAGE_RETURN
220 && pos + 1 < prefix.size()
221 && this->parse_flag(prefix[pos + 1]) == ParseFlags::NEWLINE) {
225 outside.result.total_states += width;
226 inside.result.total_states += width;
228 outside.result.unquoted_states += width;
231 inside.result.unquoted_states += width;
234 if (flag == ParseFlags::DELIMITER || flag == ParseFlags::CARRIAGE_RETURN || flag == ParseFlags::NEWLINE) {
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;
243 if (inside.result.first_quote_close == this->missing_index()
244 && this->quote_can_close(prefix, pos)) {
245 inside.result.first_quote_close = pos;
249 this->finish_quoted_span(outside, pos);
250 this->start_quoted_span(inside, pos + 1,
false);
253 this->start_quoted_span(outside, pos + 1,
false);
254 this->finish_quoted_span(inside, pos);
257 odd_quotes = !odd_quotes;
262 if (flag == ParseFlags::CARRIAGE_RETURN || flag == ParseFlags::NEWLINE) {
263 const size_t record_end = pos + width;
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;
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;
281 const long double separator_probability = prefix.empty()
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();
289 this->finish_partial_quoted_span(outside, prefix.size());
292 this->finish_partial_quoted_span(inside, prefix.size());
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;
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;
306 return static_cast<long double>(scan.unquoted_states)
307 /
static_cast<long double>(scan.total_states);
310 long double quoted_odds_from_probability_model(
311 const PrefixScanResult& outside_scan,
312 const PrefixScanResult& inside_scan
314 const long double log_k = inside_scan.log_other_start_valid_probability
315 - outside_scan.log_other_start_valid_probability;
318 return std::numeric_limits<long double>::infinity();
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;
332 if (std::fabs(a) < epsilon) {
333 if (std::fabs(b) < epsilon) {
334 return k > 1 ? std::numeric_limits<long double>::infinity() : 0;
337 const long double linear_root = -c / b;
338 return linear_root > 0 ? linear_root : 0;
341 const long double discriminant = b * b - 4 * a * c;
342 if (discriminant < 0) {
346 const long double root = (-b + std::sqrt(discriminant)) / (2 * a);
347 return root > 0 ? root : 0;
350 int pattern_start_state(
351 const PrefixScanResult& outside_scan,
352 const PrefixScanResult& inside_scan
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)();
358 if (outside_open == missing && inside_close == missing) {
362 if (outside_open < inside_close) {
366 if (inside_close < outside_open) {
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);
378 if (pattern_state == 0) {
379 return ParserDFAState(
false);
382 if (pattern_state == 1) {
383 return ParserDFAState(
true);
386 if (outside_scan.records_seen > 0 && inside_scan.records_seen == 0) {
387 return ParserDFAState(
false);
390 if (inside_scan.records_seen > 0 && outside_scan.records_seen == 0) {
391 return ParserDFAState(
true);
394 if (speculation.ambiguous) {
395 speculation.quoted_start_odds = this->quoted_odds_from_probability_model(
400 if (speculation.quoted_start_odds > 1.000001L) {
401 speculation.used_probability_model =
true;
402 return ParserDFAState(
true);
405 if (speculation.quoted_start_odds < 0.999999L) {
406 speculation.used_probability_model =
true;
407 return ParserDFAState(
false);
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);
416 return ParserDFAState(
false);
420 const PrefixScanResult& outside_scan,
421 const PrefixScanResult& inside_scan
423 if (this->pattern_start_state(outside_scan, inside_scan) != -1) {
427 return (outside_scan.records_seen == inside_scan.records_seen)
428 || (outside_scan.records_seen > 0 && inside_scan.records_seen > 0);
432 size_t prefix_bytes_;
std::array< ParseFlags, 256 > ParseFlagMap
An array which maps ASCII chars to a parsing flag.
ParseFlags
An enum used for describing the significance of each character with respect to CSV parsing.
The all encompassing namespace.
constexpr unsigned CHAR_OFFSET
Offset to convert char into array index.
std::string_view string_view
The string_view class used by this library.