Skip to main content

rypipe_core/
parallel_stream.rs

1//! Parallel streaming executor: multi-core parsing with bounded memory.
2
3use std::collections::BTreeMap;
4use std::path::{Path, PathBuf};
5use std::sync::mpsc::{sync_channel, Receiver, SyncSender};
6use std::sync::Arc;
7use std::thread::{self, JoinHandle};
8
9use arrow::record_batch::RecordBatch;
10
11use std::sync::atomic::{AtomicU64, Ordering};
12
13use crate::bounded::MemoryBudget;
14use crate::consumer::BatchConsumer;
15use crate::decoder::{RecordParser, Splitter};
16use crate::engine::TableBuilder;
17use crate::input::InputBuffer;
18use crate::plan::ExecutionPlan;
19use crate::schema::{DiscoveryOpts, FrozenSchema};
20use crate::Result;
21
22static DISCOVERY_NS: AtomicU64 = AtomicU64::new(0);
23
24/// Return the elapsed time (in nanoseconds) spent in schema discovery.
25pub fn discovery_profile() -> u64 {
26    DISCOVERY_NS.load(Ordering::Relaxed)
27}
28/// Reset the discovery timer to zero.
29pub fn reset_discovery_profile() {
30    DISCOVERY_NS.store(0, Ordering::Relaxed);
31}
32
33/// Options for parallel streaming.
34pub struct ParallelStreamOpts {
35    /// Number of worker threads.
36    pub threads: usize,
37    /// Whether to preserve row order (default: true).
38    pub ordered: bool,
39    /// Maximum reorder buffer size (default: = threads).
40    pub max_reorder: usize,
41    /// Explicit schema.  If `Some`, no discovery pass is needed.
42    /// Workers pre-size all columns from construction.
43    pub schema: Option<FrozenSchema>,
44}
45
46impl Default for ParallelStreamOpts {
47    fn default() -> Self {
48        Self {
49            threads: std::thread::available_parallelism()
50                .map(|n| n.get())
51                .unwrap_or(1),
52            ordered: true,
53            max_reorder: 0, // 0 = use threads value
54            schema: None,
55        }
56    }
57}
58
59/// Discovery sink that collects raw field names in encounter order.
60/// `needs_value=false` keeps the scanner in locate-only mode (no value
61/// extraction), but we still need `resolve()` calls, so `needs_resolve`
62/// stays true. Capture happens in `resolve()` via interior mutability.
63struct DiscoverySink {
64    seen: std::cell::RefCell<rustc_hash::FxHashSet<Box<str>>>,
65    order: std::cell::RefCell<Vec<String>>,
66}
67
68impl DiscoverySink {
69    fn new() -> Self {
70        Self {
71            seen: std::cell::RefCell::new(rustc_hash::FxHashSet::default()),
72            order: std::cell::RefCell::new(Vec::new()),
73        }
74    }
75    fn into_order(self) -> Vec<String> {
76        self.order.into_inner()
77    }
78}
79
80impl crate::decoder::ColumnarSink for DiscoverySink {
81    #[inline]
82    fn begin_row(&mut self) {}
83    #[inline]
84    fn put_field(&mut self, name: &str, _value: crate::value::Value<'_>) {
85        // Full-value fallback (if needs_value were true); keep for completeness.
86        let mut seen = self.seen.borrow_mut();
87        if seen.insert(Box::from(name)) {
88            self.order.borrow_mut().push(name.to_string());
89        }
90    }
91    #[inline]
92    fn end_row(&mut self) {}
93    #[inline]
94    fn wants(&self, _name: &str) -> bool {
95        true
96    }
97    #[inline]
98    fn resolve<'a>(&'a self, name: &'a str) -> Option<&'a str> {
99        // Locate-only path calls `resolve` without `put_field`; capture here.
100        let mut seen = self.seen.borrow_mut();
101        if seen.insert(Box::from(name)) {
102            self.order.borrow_mut().push(name.to_string());
103        }
104        Some(name)
105    }
106    #[inline]
107    fn needs_value(&self) -> bool {
108        false
109    }
110    // needs_resolve defaults to true → scanner calls resolve() for each field.
111    fn finish(&mut self) -> crate::Result<arrow::record_batch::RecordBatch> {
112        Ok(arrow::record_batch::RecordBatch::new_empty(
113            std::sync::Arc::new(arrow::datatypes::Schema::empty()),
114        ))
115    }
116}
117
118fn discover_schema<P: crate::decoder::RecordParser>(
119    bytes: &[u8],
120    parser: &P,
121    plan: &crate::plan::ExecutionPlan,
122    splitter: &dyn crate::decoder::Splitter,
123) -> (FrozenSchema, Vec<String>) {
124    let t0 = std::time::Instant::now();
125    // Explicit schema already handled by caller; this is auto-discovery.
126    let opts = DiscoveryOpts::default();
127
128    let file_size = bytes.len() as u64;
129
130    // Dynamic sizing: scale window count and size by file size
131    let n = crate::schema::dynamic_window_count(file_size);
132    let wbytes = crate::schema::dynamic_window_size(file_size);
133
134    let order: Vec<String> = if file_size < opts.full_scan_threshold || n == 0 {
135        // Small file or dynamic sizing says full scan
136        let mut sink = DiscoverySink::new();
137        let _ = parser.parse_chunk_generic(bytes, &mut sink);
138        sink.into_order()
139    } else {
140        use rayon::prelude::*;
141        // Parallelise windows: n×wbytes independent parses
142        let per_window: Vec<Vec<String>> = (0..n)
143            .into_par_iter()
144            .map(|i| {
145                let start = (file_size * i as u64 / n as u64) as usize;
146                let end = (start + wbytes).min(bytes.len());
147                if start >= end {
148                    return Vec::new();
149                }
150                let mut sink = DiscoverySink::new();
151                let slice = &bytes[start..end];
152                let _ = parser.parse_chunk_generic(slice, &mut sink);
153                sink.into_order()
154            })
155            .collect();
156        // Merge in file order, deduplicating, so global order approximates file order.
157        let mut seen = rustc_hash::FxHashSet::<String>::default();
158        let mut merged = Vec::new();
159        for mut v in per_window {
160            for name in v.drain(..) {
161                if seen.insert(name.clone()) {
162                    merged.push(name);
163                }
164            }
165        }
166        // Always scan the tail to catch late-appearing columns
167        if opts.always_scan_tail {
168            let tail_start = bytes.len().saturating_sub(wbytes);
169            let mut tail_sink = DiscoverySink::new();
170            let _ = parser.parse_chunk_generic(&bytes[tail_start..], &mut tail_sink);
171            for name in tail_sink.into_order() {
172                if seen.insert(name.clone()) {
173                    merged.push(name);
174                }
175            }
176        }
177        if merged.is_empty() && !bytes.is_empty() {
178            let mut sink = DiscoverySink::new();
179            let _ = parser.parse_chunk_generic(bytes, &mut sink);
180            sink.into_order()
181        } else {
182            merged
183        }
184    };
185    let elapsed = t0.elapsed().as_nanos() as u64;
186    DISCOVERY_NS.store(elapsed, Ordering::Relaxed);
187    let _ = splitter; // keep splitter in signature for future alignment
188    let schema = if order.is_empty() {
189        FrozenSchema::from_plan(&[], plan)
190    } else {
191        FrozenSchema::from_discovered(&order, plan)
192    };
193    (schema, order)
194}
195
196/// Public helper for batch workloads: discover the schema once and reuse.
197/// Example:
198/// ```ignore
199/// let schema = discover_schema_for_path(path, &splitter, &parser, &plan);
200/// for f in files { ParallelStreamingBatchIterator::new(..., schema.clone(), ...) }
201/// ```
202pub fn discover_schema_for_bytes<P: crate::decoder::RecordParser>(
203    bytes: &[u8],
204    splitter: &dyn crate::decoder::Splitter,
205    parser: &P,
206    plan: &crate::plan::ExecutionPlan,
207) -> FrozenSchema {
208    if !plan.schema_order.is_empty() {
209        let names: Vec<&str> = plan.schema_order.iter().map(|s| s.as_str()).collect();
210        return FrozenSchema::from_partial_plan(&names, plan);
211    }
212    let opts = DiscoveryOpts::default();
213    let sig = crate::schema::layout_signature(bytes, &opts);
214    {
215        let cache = crate::schema::SCHEMA_CACHE.read().unwrap();
216        if let Some(order) = cache.get(&sig) {
217            crate::schema::SCHEMA_CACHE_HITS.fetch_add(1, Ordering::Relaxed);
218            return FrozenSchema::from_discovered(order, plan);
219        }
220    }
221    crate::schema::SCHEMA_CACHE_MISSES.fetch_add(1, Ordering::Relaxed);
222    let (schema, order) = discover_schema(bytes, parser, plan, splitter);
223    if !order.is_empty() {
224        crate::schema::insert_schema_cache(sig, Arc::new(order));
225    }
226    schema
227}
228
229/// Parallel streaming executor: parses chunks concurrently with bounded memory.
230pub struct ParallelStreamingExecutor {
231    budget: MemoryBudget,
232    max_in_flight: usize,
233}
234
235impl ParallelStreamingExecutor {
236    pub fn new(budget: MemoryBudget, max_in_flight: usize) -> Self {
237        Self {
238            budget,
239            max_in_flight: max_in_flight.max(1),
240        }
241    }
242
243    /// Stream a file in parallel, calling `consumer` per batch in order.
244    #[allow(clippy::too_many_arguments)]
245    pub fn run_stream<P, C>(
246        &self,
247        path: &Path,
248        splitter: &dyn Splitter,
249        parser: P,
250        plan: Arc<ExecutionPlan>,
251        prefault: bool,
252        opts: ParallelStreamOpts,
253        consumer: &mut C,
254    ) -> Result<()>
255    where
256        P: RecordParser + Clone + Send + Sync + 'static,
257        C: BatchConsumer,
258    {
259        let input = InputBuffer::open(path, cfg!(feature = "mmap"), prefault)?;
260        if input.is_empty() {
261            return Ok(());
262        }
263        // Share the InputBuffer across workers via Arc to avoid
264        // the O(file_size × threads) to_vec() clone.
265        let shared = std::sync::Arc::new(input);
266        self.run_bytes_stream_shared(shared, splitter, parser, plan, opts, consumer)
267    }
268
269    /// Stream from a shared InputBuffer (zero-copy on mmap).
270    fn run_bytes_stream_shared<P, C>(
271        &self,
272        input: std::sync::Arc<InputBuffer>,
273        splitter: &dyn Splitter,
274        parser: P,
275        plan: Arc<ExecutionPlan>,
276        opts: ParallelStreamOpts,
277        consumer: &mut C,
278    ) -> Result<()>
279    where
280        P: RecordParser + Clone + Send + Sync + 'static,
281        C: BatchConsumer,
282    {
283        // Safety: the Arc keeps the InputBuffer alive for the duration.
284        // We pass a dummy &[u8] to satisfy the signature; run_bytes_stream_core
285        // ignores it when input is Some and uses input.as_slice() instead.
286        let dummy: &[u8] = &[];
287        self.run_bytes_stream_core(dummy, Some(input), splitter, parser, plan, opts, consumer)
288    }
289
290    /// Stream bytes in parallel.
291    pub fn run_bytes_stream<P, C>(
292        &self,
293        bytes: &[u8],
294        splitter: &dyn Splitter,
295        parser: P,
296        plan: Arc<ExecutionPlan>,
297        opts: ParallelStreamOpts,
298        consumer: &mut C,
299    ) -> Result<()>
300    where
301        P: RecordParser + Clone + Send + Sync + 'static,
302        C: BatchConsumer,
303    {
304        self.run_bytes_stream_core(bytes, None, splitter, parser, plan, opts, consumer)
305    }
306
307    /// Core implementation shared by `run_bytes_stream` and `run_bytes_stream_shared`.
308    #[allow(clippy::too_many_arguments)]
309    fn run_bytes_stream_core<P, C>(
310        &self,
311        bytes: &[u8],
312        input: Option<std::sync::Arc<InputBuffer>>,
313        splitter: &dyn Splitter,
314        parser: P,
315        plan: Arc<ExecutionPlan>,
316        opts: ParallelStreamOpts,
317        consumer: &mut C,
318    ) -> Result<()>
319    where
320        P: RecordParser + Clone + Send + Sync + 'static,
321        C: BatchConsumer,
322    {
323        // Prefer the shared InputBuffer's slice over the passed-in bytes.
324        let actual_bytes = match input {
325            Some(ref inp) => inp.as_slice(),
326            None => bytes,
327        };
328        let n = opts.threads.max(1);
329        let max_reorder = if opts.max_reorder > 0 {
330            opts.max_reorder
331        } else {
332            n
333        };
334        // Frozen schema: gates correct ParquetWriter / StreamWriter usage.
335        // Without it, batch 2 can have different column order (FieldG vs Text20
336        // last) even when the set is identical, breaking `write_batch`.
337        // If opts.schema is None, auto-discover:
338        //  - explicit plan.schema_order → from_partial_plan (allows unknown columns)
339        //  - else sampled discovery (16×2 MiB windows for >128 MiB, else full)
340        let schema: Option<FrozenSchema> = match opts.schema {
341            Some(s) => Some(s),
342            None => {
343                if !plan.schema_order.is_empty() {
344                    let names: Vec<&str> = plan.schema_order.iter().map(|s| s.as_str()).collect();
345                    Some(FrozenSchema::from_partial_plan(&names, &plan))
346                } else {
347                    let opts = DiscoveryOpts::default();
348                    let sig = crate::schema::layout_signature(actual_bytes, &opts);
349                    let cached = crate::schema::SCHEMA_CACHE
350                        .read()
351                        .unwrap()
352                        .get(&sig)
353                        .cloned();
354                    let (schema, order) = if let Some(order) = cached {
355                        crate::schema::SCHEMA_CACHE_HITS.fetch_add(1, Ordering::Relaxed);
356                        (FrozenSchema::from_discovered(&order, &plan), order)
357                    } else {
358                        crate::schema::SCHEMA_CACHE_MISSES.fetch_add(1, Ordering::Relaxed);
359                        let (schema, order) =
360                            discover_schema(actual_bytes, &parser, &plan, splitter);
361                        (schema, Arc::new(order))
362                    };
363                    if !order.is_empty() {
364                        crate::schema::insert_schema_cache(sig, order);
365                    }
366                    Some(schema)
367                }
368            }
369        };
370
371        let bytes_per_row = splitter
372            .estimate_bytes_per_row(&actual_bytes[..actual_bytes.len().min(65536)])
373            .max(1);
374        let chunk_size = (self.budget.bytes() / (n * 2))
375            .max(bytes_per_row * 10)
376            .max(64 * 1024);
377        let num_chunks = (actual_bytes.len() / chunk_size).max(n).min(10000);
378        let split_points = splitter.find_split_points(actual_bytes, num_chunks);
379        let mut ranges = crate::decoder::split_points_to_ranges(&split_points, actual_bytes.len());
380        if ranges.is_empty() {
381            ranges.push(0..bytes.len());
382        }
383
384        let chunks_with_seq: Vec<(usize, std::ops::Range<usize>)> =
385            ranges.into_iter().enumerate().collect();
386
387        let (sender, receiver) = sync_channel(self.max_in_flight);
388        let mut handles: Vec<JoinHandle<Result<()>>> = Vec::with_capacity(n);
389        let chunk_queue = std::sync::Arc::new(std::sync::Mutex::new(chunks_with_seq));
390        let plan_arc = plan;
391        let schema_arc = schema.map(std::sync::Arc::new);
392        let est_row = splitter
393            .estimate_bytes_per_row(&bytes[..bytes.len().min(65536)])
394            .max(512);
395
396        // Pre-clone bytes for the fallback path (when input is None).
397        let bytes_fallback = if input.is_none() {
398            Some(actual_bytes.to_vec())
399        } else {
400            None
401        };
402        for _ in 0..n {
403            let queue = std::sync::Arc::clone(&chunk_queue);
404            let sender_clone: SyncSender<(usize, Result<RecordBatch>)> = sender.clone();
405            let parser_clone = parser.clone();
406            let plan_clone = std::sync::Arc::clone(&plan_arc);
407            let schema_clone = schema_arc.clone();
408            let input_clone = input.clone();
409            let fallback_clone = bytes_fallback.clone();
410            let handle = thread::spawn(move || -> Result<()> {
411                // Use shared InputBuffer when available (zero-copy on mmap);
412                // fall back to pre-cloned bytes for external callers.
413                let bytes_ref: &[u8] = match input_clone {
414                    Some(ref inp) => inp.as_slice(),
415                    None => fallback_clone.as_deref().unwrap_or(&[]),
416                };
417                loop {
418                    let next = {
419                        let mut q = queue.lock().unwrap();
420                        q.pop()
421                    };
422                    let Some((seq, range)) = next else { break };
423                    let chunk_bytes = &bytes_ref[range.start..range.end];
424                    let mut builder = TableBuilder::with_plan(
425                        (chunk_bytes.len() / est_row).max(64),
426                        plan_clone.clone(),
427                    );
428                    // If schema is provided, pre-size columns from it.
429                    if let Some(ref schema) = schema_clone {
430                        if let Err(e) = builder.ensure_schema(schema) {
431                            let _ = sender_clone.send((seq, Err(e)));
432                            break;
433                        }
434                    }
435                    if let Err(e) = parser_clone.validate(chunk_bytes) {
436                        let _ = sender_clone.send((seq, Err(e)));
437                        break;
438                    }
439                    if let Err(e) = parser_clone.parse_chunk_generic(chunk_bytes, &mut builder) {
440                        let _ = sender_clone.send((seq, Err(e)));
441                        break;
442                    }
443                    let res = builder.finish();
444                    if sender_clone.send((seq, res)).is_err() {
445                        break;
446                    }
447                }
448                Ok(())
449            });
450            handles.push(handle);
451        }
452        drop(sender);
453
454        // Coordinator: order by seq and deliver.
455        // If `ordered`, buffer out-of-order batches until the next-in-sequence arrives.
456        // If unordered, deliver immediately.
457        // When the reorder buffer overflows, fall back to unordered delivery.
458        let mut pending: BTreeMap<usize, RecordBatch> = BTreeMap::new();
459        let mut next_seq = 0usize;
460        let mut reorder_bytes: usize = 0;
461        let mut fallback_unordered = false;
462        let mut first_chunk_error: Option<crate::Error> = None;
463        let reorder_limit = max_reorder * self.budget.bytes();
464        for (seq, res) in receiver {
465            match res {
466                Ok(batch) => {
467                    if opts.ordered && !fallback_unordered {
468                        if seq == next_seq {
469                            consumer.consume(batch)?;
470                            next_seq += 1;
471                            while let Some(b) = pending.remove(&next_seq) {
472                                consumer.consume(b)?;
473                                next_seq += 1;
474                            }
475                        } else {
476                            reorder_bytes += batch.get_array_memory_size();
477                            if reorder_bytes > reorder_limit {
478                                // Buffer overflow: drain pending in arrival order
479                                // (closest to correct), then deliver all remaining
480                                // batches unordered.  This avoids a hard error when
481                                // the memory budget is too small for the chunk count.
482                                for (_, b) in std::mem::take(&mut pending) {
483                                    consumer.consume(b)?;
484                                }
485                                consumer.consume(batch)?;
486                                reorder_bytes = 0;
487                                fallback_unordered = true;
488                            } else {
489                                pending.insert(seq, batch);
490                            }
491                        }
492                    } else {
493                        // Unordered (either opted out or fell back): deliver immediately.
494                        consumer.consume(batch)?;
495                    }
496                }
497                Err(e) => {
498                    // Keep the first failure: skipping a failed chunk would
499                    // silently drop its rows (e.g. strict_types violations).
500                    if first_chunk_error.is_none() {
501                        first_chunk_error = Some(e);
502                    }
503                }
504            }
505        }
506        if let Some(e) = first_chunk_error {
507            return Err(e);
508        }
509        // Drain remaining.
510        if opts.ordered && !fallback_unordered {
511            while let Some(b) = pending.remove(&next_seq) {
512                consumer.consume(b)?;
513                next_seq += 1;
514            }
515        }
516        for h in handles {
517            h.join().map_err(|_| {
518                crate::Error::Parser(
519                    "worker panicked during parallel parse. \
520                     This usually indicates a bug in the parser (e.g., returning \
521                     Cow::Borrowed that outlives the input chunk, or an unwrap() \
522                     on None/Err during parsing). Check your RecordParser::parse_chunk \
523                     implementation for incorrect lifetime handling or missing error checks."
524                        .to_string(),
525                )
526            })??;
527        }
528        Ok(())
529    }
530}
531
532/// Iterator wrapper for parallel streaming (pull-based).
533pub struct ParallelStreamingBatchIterator {
534    receiver: Receiver<Result<RecordBatch>>,
535    handle: Option<JoinHandle<Result<()>>>,
536    done: bool,
537}
538
539impl ParallelStreamingBatchIterator {
540    pub fn new<P, S>(
541        path: PathBuf,
542        splitter: S,
543        parser: P,
544        plan: Arc<ExecutionPlan>,
545        budget: MemoryBudget,
546        prefault: bool,
547        opts: ParallelStreamOpts,
548    ) -> Self
549    where
550        P: RecordParser + Clone + Send + Sync + 'static,
551        S: Splitter + Clone + Send + Sync + 'static,
552    {
553        let num_threads = opts.threads;
554        let max_in_flight = 2 * num_threads;
555        let (sender, receiver) = sync_channel(max_in_flight);
556        let handle = thread::spawn(move || {
557            let exec = ParallelStreamingExecutor::new(budget, max_in_flight);
558            let mut consumer = ChannelConsumer {
559                sender: sender.clone(),
560            };
561            let res = exec.run_stream(
562                &path,
563                &splitter,
564                parser,
565                plan,
566                prefault,
567                opts,
568                &mut consumer,
569            );
570            if let Err(e) = res {
571                let _ = sender.send(Err(e));
572            }
573            Ok(())
574        });
575        Self {
576            receiver,
577            handle: Some(handle),
578            done: false,
579        }
580    }
581}
582
583struct ChannelConsumer {
584    sender: SyncSender<Result<RecordBatch>>,
585}
586impl BatchConsumer for ChannelConsumer {
587    fn consume(&mut self, batch: RecordBatch) -> Result<()> {
588        let _ = self.sender.send(Ok(batch));
589        Ok(())
590    }
591}
592
593impl Iterator for ParallelStreamingBatchIterator {
594    type Item = Result<RecordBatch>;
595    fn next(&mut self) -> Option<Self::Item> {
596        if self.done {
597            return None;
598        }
599        // This is a simplified version that just receives in order as sent,
600        // not handling seq ordering for now. For true ordered, need BTreeMap logic as in run_stream.
601        // For first version, we will just receive and yield.
602        match self.receiver.recv() {
603            Ok(Ok(batch)) => Some(Ok(batch)),
604            Ok(Err(e)) => {
605                self.done = true;
606                Some(Err(e))
607            }
608            Err(_) => {
609                self.done = true;
610                if let Some(h) = self.handle.take() {
611                    if let Err(p) = h.join() {
612                        let msg = if let Some(s) = p.downcast_ref::<&str>() {
613                            (*s).to_string()
614                        } else if let Some(s) = p.downcast_ref::<String>() {
615                            s.clone()
616                        } else {
617                            "worker panicked".to_string()
618                        };
619                        return Some(Err(crate::Error::Parser(format!(
620                            "parallel streaming worker panicked: {msg}. \
621                             This usually indicates a bug in the parser (e.g., returning \
622                             Cow::Borrowed that outlives the input chunk, or an unwrap() \
623                             on None/Err during parsing). Check your RecordParser::parse_chunk \
624                             implementation for incorrect lifetime handling or missing error checks."
625                        ))));
626                    }
627                }
628                None
629            }
630        }
631    }
632}
633
634#[cfg(test)]
635mod tests {
636    use std::borrow::Cow;
637
638    use super::*;
639    use crate::decoder::{ColumnarSink, RecordParser, Splitter};
640    use crate::plan::ExecutionPlan;
641    use crate::schema::{clear_schema_cache, schema_cache_stats};
642    use crate::value::Value;
643    use arrow::array::Array;
644
645    /// Minimal parser: newline-separated rows of `key=value\t...` tokens.
646    #[derive(Clone, Debug, Default)]
647    struct NameValueParser;
648
649    impl RecordParser for NameValueParser {
650        fn validate(&self, _bytes: &[u8]) -> Result<()> {
651            Ok(())
652        }
653
654        fn parse_chunk(&self, bytes: &[u8], sink: &mut dyn ColumnarSink) -> Result<()> {
655            let text = std::str::from_utf8(bytes).map_err(|e| crate::Error::Plan(e.to_string()))?;
656            for line in text.lines() {
657                if line.is_empty() {
658                    continue;
659                }
660                sink.begin_row();
661                for token in line.split('\t') {
662                    if let Some((k, v)) = token.split_once('=') {
663                        sink.resolve_and_put(k, Value::Str(Cow::Borrowed(v)));
664                    }
665                }
666                sink.end_row();
667            }
668            Ok(())
669        }
670    }
671
672    /// Trivial splitter: one chunk covering the whole input.
673    struct NullSplitter;
674
675    impl Splitter for NullSplitter {
676        fn next_record_start(&self, _bytes: &[u8], _from: usize) -> Option<usize> {
677            None
678        }
679
680        fn find_split_points(&self, bytes: &[u8], _max_chunks: usize) -> Vec<usize> {
681            vec![0, bytes.len()]
682        }
683
684        fn estimate_bytes_per_row(&self, sample: &[u8]) -> usize {
685            let n = sample.iter().filter(|&&b| b == b'\n').count().max(1);
686            sample.len() / n
687        }
688    }
689
690    fn names(schema: &FrozenSchema) -> Vec<&str> {
691        schema.column_names().iter().map(|s| s.as_ref()).collect()
692    }
693
694    #[test]
695    fn schema_cache_hits_misses_and_plan_changes() {
696        clear_schema_cache();
697        let splitter = NullSplitter;
698        let parser = NameValueParser;
699
700        // First layout: miss.
701        let bytes = b"a=1\tb=2\na=3\tb=4\n";
702        let plan = ExecutionPlan::new();
703        let s1 = discover_schema_for_bytes(bytes, &splitter, &parser, &plan);
704        assert_eq!(names(&s1), vec!["a", "b"]);
705        assert_eq!(schema_cache_stats(), (0, 1));
706
707        // Same layout: hit.
708        let s2 = discover_schema_for_bytes(bytes, &splitter, &parser, &plan);
709        assert_eq!(names(&s2), vec!["a", "b"]);
710        assert_eq!(schema_cache_stats(), (1, 1));
711
712        // Different layout: new miss.
713        let bytes2 = b"c=1\td=2\n";
714        let s3 = discover_schema_for_bytes(bytes2, &splitter, &parser, &plan);
715        assert_eq!(names(&s3), vec!["c", "d"]);
716        assert_eq!(schema_cache_stats(), (1, 2));
717
718        // Same layout as the first parse but with a different plan:
719        // cache hit, but the applied schema differs.
720        let mut renamed = ExecutionPlan::new();
721        renamed.field_map.insert("a".to_string(), "x".to_string());
722        let s4 = discover_schema_for_bytes(bytes, &splitter, &parser, &renamed);
723        assert_eq!(names(&s4), vec!["x", "b"]);
724        assert_eq!(schema_cache_stats(), (2, 2));
725    }
726
727    #[test]
728    fn tail_scan_catches_late_columns() {
729        // Create data where column "late" only appears in the last few rows.
730        // With 16 windows of 2 MiB each, the last window starts at ~94%.
731        // Column "late" appears only in the last ~5% of the data.
732        let mut data = Vec::new();
733        // First 90%: only columns "a" and "b"
734        for i in 0..900 {
735            data.extend_from_slice(format!("a={i}\tb=val{i}\n").as_bytes());
736        }
737        // Last 10%: introduce column "late"
738        for i in 900..1000 {
739            data.extend_from_slice(format!("a={i}\tb=val{i}\tlate=new{i}\n").as_bytes());
740        }
741
742        let splitter = NullSplitter;
743        let parser = NameValueParser;
744        let plan = ExecutionPlan::new();
745        let schema = discover_schema_for_bytes(&data, &splitter, &parser, &plan);
746
747        // Column "late" must be discovered
748        let cols = names(&schema);
749        assert!(cols.contains(&"a"), "column 'a' missing");
750        assert!(cols.contains(&"b"), "column 'b' missing");
751        assert!(
752            cols.contains(&"late"),
753            "column 'late' missing from tail scan"
754        );
755
756        // Verify all values are preserved by parsing the full data
757        let mut builder = crate::engine::TableBuilder::with_plan(1024, Arc::new(plan.clone()));
758        builder.ensure_schema(&schema).unwrap();
759        parser.parse_chunk(&data, &mut builder).unwrap();
760        let batch = builder.finish().unwrap();
761
762        assert_eq!(batch.num_rows(), 1000);
763        assert_eq!(batch.num_columns(), 3);
764
765        // Check that the "late" column has values in the last 100 rows
766        let late_col = batch.column_by_name("late").expect("late column missing");
767        let late_arr = late_col
768            .as_any()
769            .downcast_ref::<arrow::array::StringArray>()
770            .expect("late column not string array");
771        // First 900 rows should be null for "late"
772        for i in 0..900 {
773            assert!(
774                late_arr.is_null(i),
775                "row {i}: expected null for 'late', got {:?}",
776                late_arr.value(i)
777            );
778        }
779        // Last 100 rows should have values
780        for i in 900..1000 {
781            assert!(
782                !late_arr.is_null(i),
783                "row {i}: expected value for 'late', got null"
784            );
785            assert!(
786                late_arr.value(i).starts_with("new"),
787                "row {i}: expected 'new{i}', got {:?}",
788                late_arr.value(i)
789            );
790        }
791    }
792
793    #[test]
794    fn all_columns_discovered_no_data_loss() {
795        // Test that all columns from a file are discovered, even with sparse data
796        let mut data = Vec::new();
797        // Mix of columns across rows
798        let rows: Vec<&[u8]> = vec![
799            b"a=1\tb=2\tc=3\n",
800            b"b=5\td=6\n",
801            b"a=7\tc=8\te=9\n",
802            b"f=10\n",
803            b"a=11\tb=12\tc=13\td=14\te=15\tf=16\n",
804        ];
805        for row in &rows {
806            data.extend_from_slice(row);
807        }
808
809        let splitter = NullSplitter;
810        let parser = NameValueParser;
811        let plan = ExecutionPlan::new();
812        let schema = discover_schema_for_bytes(&data, &splitter, &parser, &plan);
813
814        // All 6 columns must be discovered
815        let cols = names(&schema);
816        assert_eq!(cols.len(), 6, "expected 6 columns, got {:?}", cols);
817        assert!(cols.contains(&"a"));
818        assert!(cols.contains(&"b"));
819        assert!(cols.contains(&"c"));
820        assert!(cols.contains(&"d"));
821        assert!(cols.contains(&"e"));
822        assert!(cols.contains(&"f"));
823
824        // Parse all data and verify values
825        let mut builder = crate::engine::TableBuilder::with_plan(1024, Arc::new(plan.clone()));
826        builder.ensure_schema(&schema).unwrap();
827        parser.parse_chunk(&data, &mut builder).unwrap();
828        let batch = builder.finish().unwrap();
829
830        assert_eq!(batch.num_rows(), 5);
831        assert_eq!(batch.num_columns(), 6);
832
833        // Verify specific values
834        let a_col = batch.column_by_name("a").unwrap();
835        let a_arr = a_col
836            .as_any()
837            .downcast_ref::<arrow::array::StringArray>()
838            .unwrap();
839        assert_eq!(a_arr.value(0), "1");
840        assert_eq!(a_arr.value(2), "7");
841        assert_eq!(a_arr.value(4), "11");
842    }
843
844    #[test]
845    fn dynamic_sizing_discovers_same_columns() {
846        // Verify that dynamic window sizing discovers the same columns
847        // as the fixed 16-window approach
848        let mut data = Vec::new();
849        // Create data with columns spread across the file
850        for i in 0..1000 {
851            if i < 100 {
852                // First 10%: columns a, b
853                data.extend_from_slice(format!("a={i}\tb={i}\n").as_bytes());
854            } else if i < 500 {
855                // Middle 40%: columns a, b, c
856                data.extend_from_slice(format!("a={i}\tb={i}\tc={i}\n").as_bytes());
857            } else if i < 900 {
858                // Next 40%: columns a, b, c, d
859                data.extend_from_slice(format!("a={i}\tb={i}\tc={i}\td={i}\n").as_bytes());
860            } else {
861                // Last 10%: columns a, b, c, d, e (late column)
862                data.extend_from_slice(format!("a={i}\tb={i}\tc={i}\td={i}\te={i}\n").as_bytes());
863            }
864        }
865
866        let splitter = NullSplitter;
867        let parser = NameValueParser;
868        let plan = ExecutionPlan::new();
869        let schema = discover_schema_for_bytes(&data, &splitter, &parser, &plan);
870
871        // All 5 columns must be discovered
872        let cols = names(&schema);
873        assert_eq!(cols.len(), 5, "expected 5 columns, got {:?}", cols);
874        assert!(cols.contains(&"a"));
875        assert!(cols.contains(&"b"));
876        assert!(cols.contains(&"c"));
877        assert!(cols.contains(&"d"));
878        assert!(cols.contains(&"e"));
879
880        // Parse and verify
881        let mut builder = crate::engine::TableBuilder::with_plan(1024, Arc::new(plan.clone()));
882        builder.ensure_schema(&schema).unwrap();
883        parser.parse_chunk(&data, &mut builder).unwrap();
884        let batch = builder.finish().unwrap();
885
886        assert_eq!(batch.num_rows(), 1000);
887        assert_eq!(batch.num_columns(), 5);
888    }
889
890    #[test]
891    fn column_order_consistent_across_file_sizes() {
892        // Verify that column order is consistent regardless of file size
893        // This ensures no data reordering issues
894        let make_data = |n: usize| -> Vec<u8> {
895            let mut data = Vec::new();
896            for i in 0..n {
897                data.extend_from_slice(format!("x={i}\ty={i}\tz={i}\n").as_bytes());
898            }
899            data
900        };
901
902        let splitter = NullSplitter;
903        let parser = NameValueParser;
904        let plan = ExecutionPlan::new();
905
906        // Test with different file sizes
907        let sizes = vec![10, 100, 1000];
908        let mut first_order: Option<Vec<String>> = None;
909
910        for size in sizes {
911            let data = make_data(size);
912            let schema = discover_schema_for_bytes(&data, &splitter, &parser, &plan);
913            let cols: Vec<String> = schema
914                .column_names()
915                .iter()
916                .map(|s| s.to_string())
917                .collect();
918
919            if let Some(ref order) = first_order {
920                assert_eq!(
921                    &cols, order,
922                    "column order changed for size {size}: {cols:?} vs {order:?}"
923                );
924            } else {
925                first_order = Some(cols);
926            }
927        }
928    }
929
930    #[test]
931    fn esoteric_sparse_schema_one_column_per_row() {
932        // Each row has a unique column name - extremely sparse
933        let mut data = Vec::new();
934        for i in 0..100 {
935            data.extend_from_slice(format!("col_{i}={i}\n").as_bytes());
936        }
937
938        let splitter = NullSplitter;
939        let parser = NameValueParser;
940        let plan = ExecutionPlan::new();
941        let schema = discover_schema_for_bytes(&data, &splitter, &parser, &plan);
942
943        // All 100 columns should be discovered
944        let cols = names(&schema);
945        assert_eq!(
946            cols.len(),
947            100,
948            "expected 100 columns, got {:?}",
949            cols.len()
950        );
951    }
952
953    #[test]
954    fn esoteric_empty_rows() {
955        // File with many empty rows interspersed
956        let mut data = Vec::new();
957        for i in 0..50 {
958            data.extend_from_slice(format!("a={i}\n").as_bytes());
959            data.extend_from_slice(b"\n"); // empty row
960            data.extend_from_slice(b"\n"); // another empty row
961            data.extend_from_slice(format!("b={i}\n").as_bytes());
962        }
963
964        let splitter = NullSplitter;
965        let parser = NameValueParser;
966        let plan = ExecutionPlan::new();
967        let schema = discover_schema_for_bytes(&data, &splitter, &parser, &plan);
968
969        let cols = names(&schema);
970        assert!(cols.contains(&"a"), "column 'a' missing");
971        assert!(cols.contains(&"b"), "column 'b' missing");
972    }
973
974    #[test]
975    fn esoteric_single_character_columns() {
976        // Very short column names
977        let data = b"a=1\tb=2\tc=3\nd=4\te=5\n";
978
979        let splitter = NullSplitter;
980        let parser = NameValueParser;
981        let plan = ExecutionPlan::new();
982        let schema = discover_schema_for_bytes(data, &splitter, &parser, &plan);
983
984        let cols = names(&schema);
985        assert_eq!(cols.len(), 5);
986        assert!(cols.contains(&"a"));
987        assert!(cols.contains(&"e"));
988    }
989
990    #[test]
991    fn esoteric_unicode_column_names() {
992        // Unicode characters in column names
993        let data = "名前=Alice\t年齢=30\n名前=Bob\t年齢=25\n".as_bytes();
994
995        let splitter = NullSplitter;
996        let parser = NameValueParser;
997        let plan = ExecutionPlan::new();
998        let schema = discover_schema_for_bytes(data, &splitter, &parser, &plan);
999
1000        let cols = names(&schema);
1001        assert_eq!(cols.len(), 2);
1002        assert!(cols.contains(&"名前"));
1003        assert!(cols.contains(&"年齢"));
1004    }
1005
1006    #[test]
1007    fn esoteric_very_long_column_names() {
1008        // Very long column names (100+ chars)
1009        let long_name = "a".repeat(200);
1010        let data = format!("{long_name}=1\tb=2\n{long_name}=3\tc=4\n");
1011
1012        let splitter = NullSplitter;
1013        let parser = NameValueParser;
1014        let plan = ExecutionPlan::new();
1015        let schema = discover_schema_for_bytes(data.as_bytes(), &splitter, &parser, &plan);
1016
1017        let cols = names(&schema);
1018        assert_eq!(cols.len(), 3);
1019        assert!(cols.contains(&long_name.as_str()));
1020    }
1021
1022    #[test]
1023    fn esoteric_duplicate_columns_in_row() {
1024        // Same column appears multiple times in a row
1025        let data = b"a=1\ta=2\ta=3\tb=4\n";
1026
1027        let splitter = NullSplitter;
1028        let parser = NameValueParser;
1029        let plan = ExecutionPlan::new();
1030        let schema = discover_schema_for_bytes(data, &splitter, &parser, &plan);
1031
1032        let cols = names(&schema);
1033        assert_eq!(cols.len(), 2, "expected 2 unique columns, got {:?}", cols);
1034        assert!(cols.contains(&"a"));
1035        assert!(cols.contains(&"b"));
1036    }
1037}