1use std::hash::BuildHasher;
2use std::sync::atomic::{AtomicU64, Ordering};
3use std::sync::{Arc, Mutex, OnceLock};
4
5use polars_arrow::array::{Array, MutableBinaryViewArray, Utf8ViewArray};
6use polars_buffer::Buffer;
7use polars_error::{PolarsResult, polars_ensure};
8use polars_utils::aliases::{InitHashMaps, PlHashMap, PlRandomState};
9use polars_utils::pl_str::PlSmallStr;
10
11use super::{Column, DataType, IntoColumn, Series};
12use crate::prelude::*;
13use crate::series::IsSorted;
14
15static NEXT_DICTIONARY_ID: AtomicU64 = AtomicU64::new(0);
16
17const MAX_CACHED_HASHERS: usize = 4;
19
20static STRING_DTYPE: DataType = DataType::String;
21
22pub struct SharedDictionary {
27 id: u64,
29 values: Utf8ViewArray,
31 hashes: Mutex<Vec<CachedHashes>>,
33 lookup: OnceLock<CodeLookup>,
35}
36
37struct CachedHashes {
39 fingerprint: u128,
40 random_state: PlRandomState,
41 hashes: Buffer<u64>,
42}
43
44#[derive(Clone)]
46struct CodeLookup {
47 random_state: PlRandomState,
48 codes: hashbrown::HashTable<u32>,
49}
50
51impl std::fmt::Debug for SharedDictionary {
52 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
53 f.debug_struct("SharedDictionary")
54 .field("id", &self.id)
55 .field("len", &self.values.len())
56 .finish()
57 }
58}
59
60fn hasher_fingerprint(random_state: &PlRandomState) -> u128 {
62 let lo = random_state.hash_one(0x243F_6A88_85A3_08D3_u64);
63 let hi = random_state.hash_one(0x1319_8A2E_0370_7344_u64);
64 ((hi as u128) << 64) | lo as u128
65}
66
67impl SharedDictionary {
68 pub fn new(values: Utf8ViewArray) -> Arc<Self> {
70 assert!(
71 values.validity().is_none_or(|v| v.unset_bits() == 0),
72 "dictionary values must not be null"
73 );
74 let values = values.with_validity(None);
75 Arc::new(Self {
76 id: NEXT_DICTIONARY_ID.fetch_add(1, Ordering::Relaxed),
77 values,
78 hashes: Mutex::new(Vec::new()),
79 lookup: OnceLock::new(),
80 })
81 }
82
83 fn lookup(&self) -> &CodeLookup {
84 self.lookup.get_or_init(|| {
85 let random_state = PlRandomState::default();
86 let mut codes = hashbrown::HashTable::with_capacity(self.len());
87 for (c, v) in self.values.values_iter().enumerate() {
88 let h = random_state.hash_one(v);
89 let value = |k: &u32| unsafe { self.values.value_unchecked(*k as usize) };
91 if codes.find(h, |k| value(k) == v).is_none() {
92 codes.insert_unique(h, c as u32, |k| random_state.hash_one(value(k)));
93 }
94 }
95 CodeLookup {
96 random_state,
97 codes,
98 }
99 })
100 }
101
102 pub fn code_of(&self, value: &str) -> Option<u32> {
105 let lookup = self.lookup();
106 lookup
107 .codes
108 .find(lookup.random_state.hash_one(value), |k| {
109 unsafe { self.values.value_unchecked(*k as usize) == value }
111 })
112 .copied()
113 }
114
115 pub fn extended(&self, added: &[&str]) -> Arc<Self> {
119 let old_len = self.len();
120 let mut values = MutableBinaryViewArray::<str>::with_capacity(old_len + added.len());
121 for buffer in self.values.data_buffers().iter() {
122 values.push_buffer(buffer.clone());
123 }
124 unsafe {
126 values.views_mut().extend(self.values.views().iter());
127 values.set_total_bytes_len(self.values.total_bytes_len());
128 }
129 values.extend_values(added.iter().copied());
130 let values: Utf8ViewArray = values.freeze();
131
132 let value = |k: &u32| unsafe { values.value_unchecked(*k as usize) };
134 let lookup = OnceLock::new();
135 if let Some(old) = self.lookup.get() {
136 let mut new = old.clone();
137 for (i, v) in added.iter().enumerate() {
138 let h = new.random_state.hash_one(*v);
139 let random_state = &new.random_state;
140 new.codes
141 .insert_unique(h, (old_len + i) as u32, |k| random_state.hash_one(value(k)));
142 }
143 _ = lookup.set(new);
144 }
145
146 let views = values.views();
147 let buffers = values.data_buffers();
148 let hashes = self
149 .hashes
150 .lock()
151 .unwrap()
152 .iter()
153 .map(|c| {
154 let tail = views[old_len..]
155 .iter()
156 .map(|v| unsafe { v.hash_with_buffers_unchecked(buffers, &c.random_state) });
158 CachedHashes {
159 fingerprint: c.fingerprint,
160 random_state: c.random_state.clone(),
161 hashes: c
162 .hashes
163 .iter()
164 .copied()
165 .chain(tail)
166 .collect::<Vec<_>>()
167 .into(),
168 }
169 })
170 .collect();
171
172 Arc::new(Self {
173 id: NEXT_DICTIONARY_ID.fetch_add(1, Ordering::Relaxed),
174 values,
175 hashes: Mutex::new(hashes),
176 lookup,
177 })
178 }
179
180 pub fn id(&self) -> u64 {
181 self.id
182 }
183
184 pub fn values(&self) -> &Utf8ViewArray {
185 &self.values
186 }
187
188 pub fn len(&self) -> usize {
189 self.values.len()
190 }
191
192 pub fn is_empty(&self) -> bool {
193 self.values.is_empty()
194 }
195
196 pub fn cached_hashes(&self, random_state: &PlRandomState) -> Option<Buffer<u64>> {
198 let fingerprint = hasher_fingerprint(random_state);
199 self.hashes
200 .lock()
201 .unwrap()
202 .iter()
203 .find(|c| c.fingerprint == fingerprint)
204 .map(|c| c.hashes.clone())
205 }
206
207 pub fn hashes(&self, random_state: &PlRandomState) -> Buffer<u64> {
210 if let Some(hashes) = self.cached_hashes(random_state) {
211 return hashes;
212 }
213 let fingerprint = hasher_fingerprint(random_state);
214
215 let values = self.values.to_binview();
216 let buffers = values.data_buffers();
217 let hashes: Buffer<u64> = values
218 .views()
219 .iter()
220 .map(|v| unsafe { v.hash_with_buffers_unchecked(buffers, random_state) })
221 .collect::<Vec<_>>()
222 .into();
223
224 let mut cache = self.hashes.lock().unwrap();
225 if !cache.iter().any(|c| c.fingerprint == fingerprint) {
226 if cache.len() == MAX_CACHED_HASHERS {
227 cache.remove(0);
228 }
229 cache.push(CachedHashes {
230 fingerprint,
231 random_state: random_state.clone(),
232 hashes: hashes.clone(),
233 });
234 }
235 hashes
236 }
237}
238
239#[derive(Debug, Clone)]
244pub struct DictionaryColumn {
245 name: PlSmallStr,
246 dict: Arc<SharedDictionary>,
247 codes: UInt32Chunked,
250 sorted: IsSorted,
252
253 materialized: OnceLock<Series>,
255}
256
257fn codes_in_bounds(codes: &UInt32Chunked, dict_len: usize) -> bool {
260 use polars_compute::min_max::MinMaxKernel;
261 codes
262 .downcast_iter()
263 .filter_map(MinMaxKernel::max_ignore_nan_kernel)
264 .max()
265 .is_none_or(|m| (m as usize) < dict_len)
266}
267
268impl DictionaryColumn {
269 pub unsafe fn new_unchecked(
272 name: PlSmallStr,
273 dict: Arc<SharedDictionary>,
274 codes: UInt32Chunked,
275 ) -> Self {
276 debug_assert!(
277 codes_in_bounds(&codes, dict.len()),
278 "dictionary code out of bounds"
279 );
280 Self {
281 name,
282 dict,
283 codes: codes.with_name(PlSmallStr::EMPTY),
284 sorted: IsSorted::Not,
285 materialized: OnceLock::new(),
286 }
287 }
288
289 pub fn try_new(
290 name: PlSmallStr,
291 dict: Arc<SharedDictionary>,
292 codes: UInt32Chunked,
293 ) -> PolarsResult<Self> {
294 polars_ensure!(
295 codes_in_bounds(&codes, dict.len()),
296 ComputeError: "dictionary code out of bounds"
297 );
298 Ok(unsafe { Self::new_unchecked(name, dict, codes) })
299 }
300
301 pub fn name(&self) -> &PlSmallStr {
302 &self.name
303 }
304
305 pub fn rename(&mut self, name: PlSmallStr) {
306 if let Some(s) = self.materialized.get_mut() {
307 s.rename(name.clone());
308 }
309 self.name = name;
310 }
311
312 pub fn dtype(&self) -> &DataType {
313 &STRING_DTYPE
314 }
315
316 pub fn len(&self) -> usize {
317 self.codes.len()
318 }
319
320 pub fn is_empty(&self) -> bool {
321 self.codes.is_empty()
322 }
323
324 pub fn null_count(&self) -> usize {
325 self.codes.null_count()
326 }
327
328 pub fn has_nulls(&self) -> bool {
329 self.codes.has_nulls()
330 }
331
332 pub fn dict(&self) -> &Arc<SharedDictionary> {
333 &self.dict
334 }
335
336 pub fn codes(&self) -> &UInt32Chunked {
337 &self.codes
338 }
339
340 fn with_codes(&self, codes: UInt32Chunked) -> Self {
342 Self {
343 name: self.name.clone(),
344 dict: self.dict.clone(),
345 codes,
346 sorted: IsSorted::Not,
347 materialized: OnceLock::new(),
348 }
349 }
350
351 fn with_order_kept(&self, codes: UInt32Chunked) -> Self {
353 Self {
354 sorted: self.sorted,
355 ..self.with_codes(codes)
356 }
357 }
358
359 pub fn is_sorted_flag(&self) -> IsSorted {
360 self.sorted
361 }
362
363 pub fn set_sorted_flag(&mut self, sorted: IsSorted) {
364 if let Some(s) = self.materialized.get_mut() {
365 s.set_sorted_flag(sorted);
366 }
367 self.sorted = sorted;
368 }
369
370 pub fn to_series(&self) -> Series {
372 let values = StringChunked::with_chunk(self.name.clone(), self.dict.values.clone());
373 #[cfg(feature = "bigidx")]
374 let idx = self.codes.cast(&IDX_DTYPE).unwrap();
375 #[cfg(feature = "bigidx")]
376 let idx = idx.idx().unwrap();
377 #[cfg(not(feature = "bigidx"))]
378 let idx = &self.codes;
379 let mut s = unsafe { values.take_unchecked(idx) }.into_series();
381 s.set_sorted_flag(self.sorted);
382 s
383 }
384
385 pub fn lazy_as_materialized_series(&self) -> Option<&Series> {
387 self.materialized.get()
388 }
389
390 pub fn as_materialized_series(&self) -> &Series {
394 self.materialized.get_or_init(|| self.to_series())
395 }
396
397 pub fn take_materialized_series(self) -> Series {
399 match self.materialized.into_inner() {
400 Some(s) => s,
401 None => Self {
402 materialized: OnceLock::new(),
403 ..self
404 }
405 .to_series(),
406 }
407 }
408
409 pub fn slice(&self, slice: impl Into<Slice>) -> Self {
410 self.with_order_kept(self.codes.slice(slice))
411 }
412
413 pub fn filter(&self, filter: &BooleanChunked) -> PolarsResult<Self> {
414 Ok(self.with_order_kept(self.codes.filter(filter)?))
415 }
416
417 pub unsafe fn take_unchecked(&self, indices: &IdxCa) -> Self {
420 self.with_codes(unsafe { self.codes.take_unchecked(indices) })
421 }
422
423 pub unsafe fn take_slice_unchecked(&self, indices: &[IdxSize]) -> Self {
426 self.with_codes(unsafe { self.codes.take_unchecked(indices) })
427 }
428
429 pub fn rechunk(&self) -> Self {
430 if self.codes.chunks().len() <= 1 {
431 return self.clone();
432 }
433 self.with_order_kept(self.codes.rechunk().into_owned())
434 }
435
436 pub fn reverse(&self) -> Self {
437 let mut out = self.with_codes(self.codes.reverse());
438 out.sorted = self.sorted.reverse();
439 out
440 }
441
442 pub fn new_empty(name: PlSmallStr) -> Self {
445 let dict = SharedDictionary::new(Utf8ViewArray::new_empty(
446 polars_arrow::datatypes::ArrowDataType::Utf8View,
447 ));
448 let codes = UInt32Chunked::from_vec(PlSmallStr::EMPTY, Vec::new());
449 unsafe { Self::new_unchecked(name, dict, codes) }
451 }
452
453 pub fn try_append(&mut self, other: &DictionaryColumn) -> bool {
464 if other.is_empty() {
465 return true;
466 }
467 if self.dict.id != other.dict.id {
468 if self.is_empty() {
469 self.dict = other.dict.clone();
471 self.codes = other.codes.clone().with_name(self.codes.name().clone());
472 self.sorted = IsSorted::Not;
473 self.materialized = OnceLock::new();
474 return true;
475 }
476 let max_len = (self.len() + other.len()).min(u32::MAX as usize);
477 if self.dict.len() > max_len {
478 return false;
479 }
480 let used = if other.len() < other.dict.len() {
483 other.used_codes(other.len())
484 } else {
485 None
486 };
487 let mut added = Vec::new();
488 let mut added_code_of = PlHashMap::<&str, u32>::new();
489 let mut remap = Vec::with_capacity(match &used {
490 Some((used, _)) => used.len(),
491 None => other.dict.len(),
492 });
493 let values = &other.dict.values;
494 let to_resolve: Box<dyn Iterator<Item = &str> + '_> = match &used {
495 Some((used, _)) => Box::new(
497 used.iter()
498 .map(|c| unsafe { values.value_unchecked(*c as usize) }),
499 ),
500 None => Box::new(values.values_iter()),
501 };
502 for v in to_resolve {
503 let c = match self.dict.code_of(v) {
504 Some(c) => c,
505 None => {
506 let next = (self.dict.len() + added.len()) as u32;
507 *added_code_of.entry(v).or_insert_with(|| {
508 added.push(v);
509 next
510 })
511 },
512 };
513 remap.push(c);
514 if self.dict.len() + added.len() > max_len {
515 return false;
516 }
517 }
518 if !added.is_empty() && self.dict.len() > other.len() {
519 return false;
520 }
521 let other_codes = match used {
522 Some((_, row_slots)) => {
523 let codes = other.codes.rechunk();
524 let arr = codes.downcast_as_array();
525 let new_codes: Vec<u32> = row_slots
527 .iter()
528 .map(|s| remap.get(*s as usize).copied().unwrap_or(0))
529 .collect();
530 let arr = PrimitiveArray::<u32>::new(
531 ArrowDataType::UInt32,
532 new_codes.into(),
533 arr.validity().cloned(),
534 );
535 UInt32Chunked::with_chunk(PlSmallStr::EMPTY, arr)
536 },
537 None => other
539 .codes
540 .apply_values(|c| remap.get(c as usize).copied().unwrap_or(0)),
541 };
542 if !added.is_empty() {
543 self.dict = self.dict.extended(&added);
544 }
545 self.codes.append(&other_codes).unwrap();
546 } else {
547 self.codes.append(&other.codes).unwrap();
548 }
549 self.sorted = IsSorted::Not;
550 self.materialized = OnceLock::new();
551 true
552 }
553
554 pub fn estimated_size(&self) -> usize {
560 let dict_size = polars_arrow::compute::aggregate::estimated_bytes_size(&self.dict.values);
561 let dict_part = if self.len() >= self.dict.len() {
562 dict_size
563 } else {
564 (dict_size as u128 * self.len() as u128 / self.dict.len() as u128) as usize
565 };
566 self.codes
567 .chunks()
568 .iter()
569 .map(|c| polars_arrow::compute::aggregate::estimated_bytes_size(c.as_ref()))
570 .sum::<usize>()
571 + dict_part
572 + self.materialized.get().map_or(0, |s| s.estimated_size())
573 }
574
575 pub fn used_codes(&self, max_used: usize) -> Option<(Vec<IdxSize>, Vec<u32>)> {
581 const MAX_DENSE_ENTRIES_PER_ROW: usize = 4;
583
584 let codes = self.codes.rechunk();
585 let codes = codes.downcast_as_array();
586 let validity = codes.validity().filter(|v| v.unset_bits() > 0);
587
588 fn assign(
590 codes: &[u32],
591 validity: Option<&polars_arrow::bitmap::Bitmap>,
592 max_used: usize,
593 mut slot_of: impl FnMut(u32, u32) -> u32,
594 ) -> Option<(Vec<IdxSize>, Vec<u32>)> {
595 let mut used: Vec<IdxSize> = Vec::new();
596 let mut row_slots = Vec::with_capacity(codes.len());
597 for (i, c) in codes.iter().enumerate() {
598 if validity.is_some_and(|v| !unsafe { v.get_bit_unchecked(i) }) {
599 row_slots.push(0);
600 continue;
601 }
602 let next = used.len() as u32;
603 let s = slot_of(*c, next);
604 if s == next {
605 if used.len() >= max_used {
606 return None;
607 }
608 used.push(*c as IdxSize);
609 }
610 row_slots.push(s);
611 }
612 Some((used, row_slots))
613 }
614
615 if self.dict.len() <= MAX_DENSE_ENTRIES_PER_ROW.saturating_mul(self.len()) {
616 let mut slot = vec![u32::MAX; self.dict.len()];
617 assign(codes.values(), validity, max_used, |c, next| {
618 let s = unsafe { slot.get_unchecked_mut(c as usize) };
620 if *s == u32::MAX {
621 *s = next;
622 }
623 *s
624 })
625 } else {
626 let mut slot = polars_utils::aliases::PlHashMap::<u32, u32>::default();
627 assign(codes.values(), validity, max_used, |c, next| {
628 *slot.entry(c).or_insert(next)
629 })
630 }
631 }
632
633 pub fn apply_elementwise(
643 &self,
644 f: impl FnOnce(&Series) -> PolarsResult<Series>,
645 ) -> PolarsResult<Column> {
646 let max_evaluated = self.len() / 2;
647 let Some((used, mut row_slots)) = self.used_codes(max_evaluated) else {
648 return f(self.as_materialized_series()).map(Column::from);
649 };
650 let null_slot = used.len() as u32;
651
652 let codes = self.codes.rechunk();
653 let validity = codes
654 .downcast_as_array()
655 .validity()
656 .filter(|v| v.unset_bits() > 0);
657 if let Some(v) = validity {
658 for (s, is_valid) in row_slots.iter_mut().zip(v.iter()) {
659 if !is_valid {
660 *s = null_slot;
661 }
662 }
663 }
664
665 let values = StringChunked::with_chunk(self.name.clone(), self.dict.values.clone());
666 let mut input = unsafe { values.take_unchecked(&IdxCa::from_vec(PlSmallStr::EMPTY, used)) };
667 if validity.is_some() {
668 input.append(&StringChunked::full_null(PlSmallStr::EMPTY, 1))?;
669 }
670 let input = input.into_series();
671 let out = f(&input)?;
672 polars_ensure!(
673 out.len() == input.len(),
674 ComputeError: "elementwise function changed the length of a dictionary column"
675 );
676
677 if out.dtype() == &DataType::String {
678 let name = out_name(&input, &out, &self.name);
680 let out = out.str().unwrap().rechunk();
681 let out = out.downcast_as_array();
682 let out_validity = out.validity().filter(|v| v.unset_bits() > 0);
683 let row_validity = out_validity.map(|ov| {
684 row_slots
685 .iter()
686 .map(|s| unsafe { ov.get_bit_unchecked(*s as usize) })
687 .collect::<polars_arrow::bitmap::Bitmap>()
688 });
689 let dict = SharedDictionary::new(out.clone().with_validity(None));
690 let codes =
691 UInt32Chunked::from_vec_validity(PlSmallStr::EMPTY, row_slots, row_validity);
692 return Ok(unsafe { DictionaryColumn::new_unchecked(name, dict, codes) }.into_column());
694 }
695
696 #[cfg(feature = "bigidx")]
697 let idx = IdxCa::from_vec(
698 PlSmallStr::EMPTY,
699 row_slots.into_iter().map(|s| s as IdxSize).collect(),
700 );
701 #[cfg(not(feature = "bigidx"))]
702 let idx = IdxCa::from_vec(PlSmallStr::EMPTY, row_slots);
703 Ok(unsafe { out.take_unchecked(&idx) }.into_column())
705 }
706
707 pub fn check_invariants(&self) {
709 let expected = self.to_series();
710 if let Some(m) = self.materialized.get() {
711 assert!(m.equals_missing(&expected));
712 }
713 assert_eq!(expected.len(), self.len());
714 }
715}
716
717fn out_name(input: &Series, out: &Series, name: &PlSmallStr) -> PlSmallStr {
719 if out.name() == input.name() {
720 name.clone()
721 } else {
722 out.name().clone()
723 }
724}
725
726impl IntoColumn for DictionaryColumn {
727 #[inline(always)]
728 fn into_column(self) -> Column {
729 Column::Dictionary(self)
730 }
731}
732
733impl From<DictionaryColumn> for Column {
734 #[inline]
735 fn from(value: DictionaryColumn) -> Self {
736 value.into_column()
737 }
738}
739
740pub fn dictionary_codes_enabled() -> bool {
743 static ENABLED: OnceLock<bool> = OnceLock::new();
744 *ENABLED.get_or_init(|| std::env::var("POLARS_DICT_CODES").as_deref() != Ok("0"))
745}
746
747#[cfg(test)]
748mod test {
749 use super::*;
750 use crate::chunked_array::cast::CastOptions;
751 use crate::chunked_array::flags::StatisticsFlags;
752 use crate::frame::ChunkCursor;
753
754 fn dict_column(dict: &[&str], codes: &[Option<u32>]) -> DictionaryColumn {
755 let values = Utf8ViewArray::from_slice_values(dict);
756 let codes = UInt32Chunked::from_iter_options(PlSmallStr::EMPTY, codes.iter().copied());
757 DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap()
758 }
759
760 fn values(c: &DictionaryColumn) -> Vec<Option<String>> {
761 c.to_series()
762 .str()
763 .unwrap()
764 .iter()
765 .map(|v| v.map(str::to_owned))
766 .collect()
767 }
768
769 #[test]
770 fn try_append_merges_by_value() {
771 let mut a = dict_column(&["x", "y"], &[Some(0), Some(1), None, Some(0)]);
772 let id = a.dict().id();
773 let b = dict_column(&["y", "x"], &[Some(0), None, Some(1), Some(1)]);
775 assert!(a.try_append(&b));
776 assert_eq!(a.dict().id(), id);
777 assert_eq!(a.dict().len(), 2);
778 let c = dict_column(&["z", "x"], &[Some(0), Some(1), Some(0), Some(0)]);
780 assert!(a.try_append(&c));
781 assert_eq!(a.dict().len(), 3);
782 a.check_invariants();
783 let s = |v: &str| Some(v.to_owned());
784 assert_eq!(
785 values(&a),
786 [
787 s("x"),
788 s("y"),
789 None,
790 s("x"),
791 s("y"),
792 None,
793 s("x"),
794 s("x"),
795 s("z"),
796 s("x"),
797 s("z"),
798 s("z"),
799 ]
800 );
801 }
802
803 #[test]
804 fn try_append_remaps_only_used_codes() {
805 let mut a = dict_column(
808 &["x", "y", "w"],
809 &[Some(0), Some(1), Some(2), Some(0), Some(1)],
810 );
811 let b = dict_column(
812 &[
813 "unused-1", "z", "x", "unused-2", "unused-3", "y", "unused-4",
814 ],
815 &[Some(1), None, Some(2), Some(5), Some(2)],
816 );
817 assert!(a.try_append(&b));
818 assert_eq!(a.dict().len(), 4);
820 assert_eq!(a.dict().code_of("unused-1"), None);
821 a.check_invariants();
822 let s = |v: &str| Some(v.to_owned());
823 assert_eq!(values(&a)[5..], [s("z"), None, s("x"), s("y"), s("x")]);
824 let mut a = dict_column(&["x", "y", "w"], &[Some(0), Some(1), Some(2)]);
826 let b = dict_column(&["p", "q", "r", "s"], &[None, None]);
827 assert!(a.try_append(&b));
828 assert_eq!(a.dict().len(), 3);
829 assert_eq!(values(&a)[3..], [None, None]);
830 a.check_invariants();
831 }
832
833 #[test]
834 fn try_append_to_empty_adopts_the_other_dictionary() {
835 let mut a = dict_column(&["old-1", "old-2"], &[Some(0)]).slice((0usize, 0usize));
836 let b = dict_column(&["x", "y", "z"], &[Some(2), None, Some(0)]);
837 assert!(a.is_empty());
838 assert!(a.try_append(&b));
839 assert_eq!(a.dict().id(), b.dict().id());
840 a.check_invariants();
841 let s = |v: &str| Some(v.to_owned());
842 assert_eq!(values(&a), [s("z"), None, s("x")]);
843 assert_eq!(a.name(), "s");
844 }
845
846 #[test]
847 fn try_append_extends_lookup_and_hashes() {
848 let rs = PlRandomState::default();
849 let mut a = dict_column(&["x", "y"], &[Some(0), Some(1)]);
850 a.dict().hashes(&rs);
851 assert_eq!(a.dict().code_of("y"), Some(1));
852 let b = dict_column(
853 &["z", "a-value-longer-than-a-view", "x"],
854 &[Some(0), Some(1), Some(2)],
855 );
856 assert!(a.try_append(&b));
857 let dict = a.dict();
858 assert_eq!(dict.len(), 4);
859 assert!(dict.lookup.get().is_some());
861 assert_eq!(dict.code_of("a-value-longer-than-a-view"), Some(3));
862 assert_eq!(dict.code_of("x"), Some(0));
863 assert_eq!(dict.code_of("absent"), None);
864 let cached = dict.cached_hashes(&rs).unwrap();
865 let fresh = SharedDictionary::new(dict.values().clone()).hashes(&rs);
866 assert_eq!(cached.as_slice(), fresh.as_slice());
867 a.check_invariants();
868 }
869
870 #[test]
871 fn compare_length_one_with_longer_constant_broadcasts() {
872 let lhs = Column::from(dict_column(&["a", "b"], &[Some(0)]));
873 let rhs = Column::new_scalar(
874 "c".into(),
875 Scalar::new(DataType::String, AnyValue::StringOwned("a".into())),
876 5,
877 );
878 let out = lhs.equal(&rhs).unwrap();
879 assert_eq!(out.len(), 5);
880 assert!(out.all());
881 let out = rhs.not_equal(&lhs).unwrap();
882 assert_eq!(out.len(), 5);
883 assert!(!out.any());
884 }
885
886 #[cfg(feature = "serde")]
887 #[test]
888 fn serializes_as_series() {
889 let col = Column::from(dict_column(&["a", "b"], &[Some(1), None, Some(0)]));
890 let series = Column::from(col.as_materialized_series().clone());
891 let json = serde_json::to_string(&col).unwrap();
892 assert_eq!(json, serde_json::to_string(&series).unwrap());
893 let back: Column = serde_json::from_str(&json).unwrap();
894 assert!(
895 back.as_materialized_series()
896 .equals_missing(&series.take_materialized_series())
897 );
898 }
899
900 #[test]
901 fn try_append_declines_a_large_dictionary() {
902 let mut a = dict_column(&["a", "b"], &[Some(0), Some(1)]);
903 let b = dict_column(&["c", "d", "e"], &[Some(0)]);
904 assert!(!a.try_append(&b));
905 assert_eq!(a.len(), 2);
906 assert_eq!(a.dict().len(), 2);
907 }
908
909 #[test]
910 fn try_append_bounds_dictionary_extension() {
911 let a = dict_column(&["a", "b", "c"], &[Some(0), Some(1), Some(2)]);
912 let b = dict_column(&["d"], &[Some(0), None, Some(0)]);
913 let mut at_limit = a.clone();
914 assert!(at_limit.try_append(&b));
915 assert_eq!(at_limit.dict().len(), 4);
916 let expected = values(&at_limit);
917
918 let mut above_limit = a.clone();
919 above_limit.set_sorted_flag(IsSorted::Ascending);
920 above_limit.as_materialized_series();
921 let smaller_b = b.slice(Slice::head(2));
922 assert!(!above_limit.try_append(&smaller_b));
923 assert_eq!(above_limit.dict().id(), a.dict().id());
924 assert_eq!(values(&above_limit), values(&a));
925 assert_eq!(above_limit.is_sorted_flag(), IsSorted::Ascending);
926 assert!(above_limit.lazy_as_materialized_series().is_some());
927
928 let mut col = Column::from(above_limit);
929 col.append(&Column::from(smaller_b)).unwrap();
930 assert!(col.as_dictionary_column().is_none());
931 assert_eq!(
932 col.str().unwrap().iter().collect::<Vec<_>>(),
933 expected[..5]
934 .iter()
935 .map(Option::as_deref)
936 .collect::<Vec<_>>(),
937 );
938 }
939
940 #[test]
941 fn try_append_reuses_dictionary_above_extension_bound() {
942 let mut a = dict_column(&["a", "b", "c"], &[Some(0), Some(1), Some(2)]);
943 let same_dict = a.slice((1usize, 1));
944 let overlapping = dict_column(&["c"], &[Some(0)]);
945 let id = a.dict().id();
946 assert!(a.try_append(&same_dict));
947 assert!(a.try_append(&overlapping));
948 assert_eq!(a.dict().id(), id);
949 assert_eq!(
950 a.as_materialized_series()
951 .str()
952 .unwrap()
953 .iter()
954 .collect::<Vec<_>>(),
955 [Some("a"), Some("b"), Some("c"), Some("b"), Some("c")],
956 );
957 }
958
959 #[test]
960 fn try_new_ignores_sorted_flag() {
961 let values = Utf8ViewArray::from_slice_values(["a"]);
962 let mut codes = UInt32Chunked::from_slice(PlSmallStr::EMPTY, &[5, 0]);
963 codes.set_sorted_flag(IsSorted::Ascending);
964 let dict = SharedDictionary::new(values);
965 assert!(DictionaryColumn::try_new("s".into(), dict, codes).is_err());
966 }
967
968 #[test]
969 fn clear_keeps_a_dictionary_column_without_its_dictionary() {
970 let col = Column::from(dict_column(&["x", "y"], &[Some(0), Some(1)]));
971 let mut empty = col.clear();
972 let d = empty.as_dictionary_column().unwrap();
973 assert_eq!(d.dict().len(), 0);
974 assert_eq!(empty.dtype(), &DataType::String);
975 assert_eq!(empty.len(), 0);
976 empty.append(&col).unwrap();
978 let d = empty.as_dictionary_column().unwrap();
979 assert_eq!(d.dict().len(), 2);
980 assert_eq!(empty.str().unwrap().get(1), Some("y"));
981 }
982
983 #[test]
984 fn try_append_empty_other_is_a_no_op() {
985 let mut a = dict_column(&["x", "y", "z"], &[Some(0)]);
986 let id = a.dict().id();
987 let b = dict_column(&["q"], &[]);
988 assert!(a.try_append(&b));
989 assert_eq!(a.dict().id(), id);
990 assert_eq!(a.len(), 1);
991 }
992
993 #[test]
994 fn apply_elementwise_on_a_filtered_big_dictionary_stays_coded() {
995 let dict: Vec<String> = (0..2000).map(|i| format!("value-{i}")).collect();
996 let dict: Vec<&str> = dict.iter().map(String::as_str).collect();
997 let codes: Vec<Option<u32>> = (0..200).map(|i| Some((i % 5) * 7)).collect();
998 let col = dict_column(&dict, &codes);
999 let out = col.apply_elementwise(|s| Ok(s.clone())).unwrap();
1000 let d = out.as_dictionary_column().expect("stays coded");
1002 assert_eq!(d.dict().len(), 5);
1003 assert_eq!(out.str().unwrap().get(8), Some("value-21"));
1004 }
1005
1006 #[test]
1007 fn strict_cast_counts_rows() {
1008 let codes: Vec<Option<u32>> = (0..100).map(|i| Some(u32::from(i >= 90))).collect();
1009 let col = Column::from(dict_column(&["bad", "1"], &codes));
1010 let err = col.strict_cast(&DataType::Int64).unwrap_err().to_string();
1011 assert!(err.contains("90 out of 100"), "{err}");
1012 let err = col
1013 .cast_with_options(&DataType::Int64, CastOptions::Strict)
1014 .unwrap_err()
1015 .to_string();
1016 assert!(err.contains("90 out of 100"), "{err}");
1017 let ok = Column::from(dict_column(&["2", "1"], &codes));
1018 assert_eq!(
1019 ok.strict_cast(&DataType::Int64)
1020 .unwrap()
1021 .i64()
1022 .unwrap()
1023 .get(95),
1024 Some(1)
1025 );
1026 }
1027
1028 #[test]
1029 #[cfg(feature = "dtype-struct")]
1030 fn strict_cast_to_nested_checks_the_fields() {
1031 let col = Column::from(dict_column(&["bad", "1"], &[Some(0), Some(1), Some(1)]));
1032 let dtype = DataType::Struct(vec![Field::new("n".into(), DataType::Int64)]);
1033 assert!(col.as_materialized_series().strict_cast(&dtype).is_err());
1035 assert!(col.strict_cast(&dtype).is_err());
1036 assert!(col.cast_with_options(&dtype, CastOptions::Strict).is_err());
1037 }
1038
1039 #[test]
1040 fn split_chunks_of_a_dictionary_only_frame() {
1041 let values = Utf8ViewArray::from_slice_values(["x", "y"]);
1042 let mut codes = UInt32Chunked::from_slice(PlSmallStr::EMPTY, &[0, 1, 0]);
1043 codes
1044 .append(&UInt32Chunked::from_slice(PlSmallStr::EMPTY, &[1, 1]))
1045 .unwrap();
1046 assert_eq!(codes.chunks().len(), 2);
1047 let col =
1048 DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap();
1049 let mut df = DataFrame::new_infer_height(vec![Column::from(col)]).unwrap();
1050 assert_eq!(df.first_col_n_chunks(), 2);
1051 let parts: Vec<DataFrame> = df.split_chunks().collect();
1052 assert_eq!(parts.len(), 2);
1053 assert_eq!(parts[0].height(), 3);
1054 assert_eq!(parts[1].height(), 2);
1055 for p in &parts {
1056 assert_eq!(p.columns()[0].len(), p.height());
1057 }
1058 let last = parts[1].columns()[0]
1059 .as_materialized_series()
1060 .str()
1061 .unwrap()
1062 .clone();
1063 assert_eq!(last.get(0), Some("y"));
1064 }
1065
1066 #[test]
1067 fn chunk_iterators_and_split_follow_dictionary_code_chunks() {
1068 let values = Utf8ViewArray::from_slice_values(["x", "y"]);
1069 let mut codes = UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![0; 1000]);
1070 codes
1071 .append(&UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![1; 1000]))
1072 .unwrap();
1073 let col =
1074 DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap();
1075 let df = DataFrame::new_infer_height(vec![Column::from(col)]).unwrap();
1076 assert_eq!(df.iter_chunks(CompatLevel::newest(), false).count(), 2);
1077 assert_eq!(df.iter_chunks_physical().count(), 2);
1078 let parts = crate::utils::split(&df, 2);
1079 assert_eq!(parts.len(), 2);
1080 assert!(parts.iter().all(|p| p.height() == 1000));
1081 let parts = crate::utils::split_and_flatten(&df, 2);
1082 assert_eq!(parts.len(), 2);
1083 }
1084
1085 #[test]
1086 fn chunk_cursor_of_an_unaligned_frame_follows_the_series_chunks() {
1087 let values = Utf8ViewArray::from_slice_values(["x", "y"]);
1088 let mut codes = UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![0; 1000]);
1089 codes
1090 .append(&UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![1; 1000]))
1091 .unwrap();
1092 let d =
1093 DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap();
1094 let ints = Column::new("i".into(), (0..2000i64).collect::<Vec<_>>());
1095 let df = DataFrame::new_infer_height(vec![Column::from(d), ints]).unwrap();
1096 assert_eq!(df.first_col_n_chunks(), 1);
1099 assert_eq!(df.first_col_chunk_lengths().collect::<Vec<_>>(), [2000]);
1100 let mut cursor = ChunkCursor::new(&df);
1101 assert_eq!(cursor.next(), Some((0, 2000)));
1102 assert_eq!(cursor.next(), None);
1103 }
1104
1105 #[test]
1106 fn sorted_flag() {
1107 let mut a = dict_column(&["b", "a"], &[Some(1), Some(1), Some(0)]);
1108 assert_eq!(a.is_sorted_flag(), IsSorted::Not);
1109 a.set_sorted_flag(IsSorted::Ascending);
1110 assert_eq!(a.slice((1usize, 2)).is_sorted_flag(), IsSorted::Ascending);
1111 assert_eq!(a.rechunk().is_sorted_flag(), IsSorted::Ascending);
1112 assert_eq!(a.reverse().is_sorted_flag(), IsSorted::Descending);
1113 assert_eq!(
1114 a.as_materialized_series().is_sorted_flag(),
1115 IsSorted::Ascending
1116 );
1117 let idx = IdxCa::from_vec(PlSmallStr::EMPTY, vec![2, 0]);
1118 assert_eq!(
1119 unsafe { a.take_unchecked(&idx) }.is_sorted_flag(),
1120 IsSorted::Not
1121 );
1122 let b = a.clone();
1123 assert!(a.try_append(&b));
1124 assert_eq!(a.is_sorted_flag(), IsSorted::Not);
1125
1126 let mut col = Column::from(dict_column(&["a"], &[Some(0)]));
1127 col.set_sorted_flag(IsSorted::Descending);
1128 assert_eq!(col.is_sorted_flag(), IsSorted::Descending);
1129 assert!(col.get_flags().contains(StatisticsFlags::IS_SORTED_DSC));
1130 }
1131}