Skip to main content

polars_core/chunked_array/ops/
chunkops.rs

1use std::borrow::Cow;
2use std::cell::Cell;
3
4use polars_arrow::bitmap::{Bitmap, BitmapBuilder};
5use polars_arrow::compute::concatenate::concatenate_unchecked;
6use polars_error::constants::LENGTH_LIMIT_MSG;
7use polars_utils::slice_enum::Slice;
8
9use super::*;
10use crate::chunked_array::flags::StatisticsFlags;
11#[cfg(feature = "object")]
12use crate::chunked_array::object::builder::ObjectChunkedBuilder;
13
14pub(crate) fn split_at(
15    chunks: &[ArrayRef],
16    offset: i64,
17    own_length: usize,
18) -> (Vec<ArrayRef>, Vec<ArrayRef>) {
19    let mut new_chunks_left = Vec::with_capacity(1);
20    let mut new_chunks_right = Vec::with_capacity(1);
21    let raw_offset = Slice::resolve_offset(offset, own_length);
22
23    let mut remaining_offset = raw_offset;
24    let mut iter = chunks.iter().filter(|c| !c.is_empty());
25
26    for chunk in &mut iter {
27        let chunk_len = chunk.len();
28        if remaining_offset > 0 && remaining_offset >= chunk_len {
29            remaining_offset -= chunk_len;
30            new_chunks_left.push(chunk.clone());
31            continue;
32        }
33
34        let (l, r) = chunk.split_at_boxed(remaining_offset);
35        new_chunks_left.push(l);
36        new_chunks_right.push(r);
37        break;
38    }
39
40    for chunk in iter {
41        new_chunks_right.push(chunk.clone())
42    }
43    if new_chunks_left.is_empty() {
44        new_chunks_left.push(chunks[0].sliced(0, 0));
45    }
46    if new_chunks_right.is_empty() {
47        new_chunks_right.push(chunks[0].sliced(0, 0));
48    }
49    (new_chunks_left, new_chunks_right)
50}
51
52pub(crate) fn slice(
53    chunks: &[ArrayRef],
54    slice: Slice,
55    own_length: usize,
56) -> (Vec<ArrayRef>, usize) {
57    let mut new_chunks = Vec::with_capacity(1);
58    let range = slice.resolve(own_length);
59    let mut remaining_length = range.len();
60    let mut remaining_offset = range.start;
61    let mut new_len = 0;
62
63    for chunk in chunks {
64        let chunk_len = chunk.len();
65        if remaining_offset > 0 && remaining_offset >= chunk_len {
66            remaining_offset -= chunk_len;
67            continue;
68        }
69        let take_len = if remaining_length + remaining_offset > chunk_len {
70            chunk_len - remaining_offset
71        } else {
72            remaining_length
73        };
74        new_len += take_len;
75
76        debug_assert!(remaining_offset + take_len <= chunk.len());
77        unsafe {
78            // SAFETY:
79            // this function ensures the slices are in bounds
80            new_chunks.push(chunk.sliced_unchecked(remaining_offset, take_len));
81        }
82        remaining_length -= take_len;
83        remaining_offset = 0;
84        if remaining_length == 0 {
85            break;
86        }
87    }
88    if new_chunks.is_empty() {
89        new_chunks.push(chunks[0].sliced(0, 0));
90    }
91    (new_chunks, new_len)
92}
93
94// When we deal with arrays and lists we can easily exceed the limit if
95// we take the underlying values array as a Series. This call stack
96// is hard to follow, so for this one case we make an exception
97// and use a thread local.
98thread_local!(pub static CHECK_LENGTH: Cell<bool> = const { Cell::new(true) });
99
100/// Meant for internal use. In very rare conditions this can be turned off.
101/// # Safety
102/// The caller must ensure the Series that exceeds the length gets deconstructed
103/// into array values or list values before and never is used.
104pub unsafe fn _set_check_length(check: bool) {
105    CHECK_LENGTH.set(check)
106}
107
108impl<T: PolarsDataType> ChunkedArray<T> {
109    /// Get the length of the ChunkedArray
110    #[inline]
111    pub fn len(&self) -> usize {
112        self.length
113    }
114
115    /// Return the number of null values in the ChunkedArray.
116    #[inline]
117    pub fn null_count(&self) -> usize {
118        self.null_count
119    }
120
121    /// Set the null count directly.
122    ///
123    /// This can be useful after mutably adjusting the validity of the
124    /// underlying arrays.
125    ///
126    /// # Safety
127    /// The new null count must match the total null count of the underlying
128    /// arrays.
129    pub unsafe fn set_null_count(&mut self, null_count: usize) {
130        self.null_count = null_count;
131    }
132
133    /// Check if ChunkedArray is empty.
134    #[inline]
135    pub fn is_empty(&self) -> bool {
136        self.len() == 0
137    }
138
139    /// Compute the length
140    pub(crate) fn compute_len(&mut self) {
141        fn inner(chunks: &[ArrayRef]) -> usize {
142            match chunks.len() {
143                // fast path
144                1 => chunks[0].len(),
145                _ => chunks.iter().fold(0, |acc, arr| acc + arr.len()),
146            }
147        }
148        let len = inner(&self.chunks);
149        // Length limit is `IdxSize::MAX - 1`. We use `IdxSize::MAX` to indicate `NULL` in indexing.
150        if len >= (IdxSize::MAX as usize) && CHECK_LENGTH.get() {
151            panic!("{}", LENGTH_LIMIT_MSG);
152        }
153        self.length = len;
154        self.null_count = self
155            .chunks
156            .iter()
157            .map(|arr| arr.null_count())
158            .sum::<usize>();
159    }
160
161    /// Rechunks this ChunkedArray, returning a new Cow::Owned ChunkedArray if it was
162    /// rechunked or simply a Cow::Borrowed of itself if it was already a single chunk.
163    pub fn rechunk(&self) -> Cow<'_, Self> {
164        match self.dtype() {
165            #[cfg(feature = "object")]
166            DataType::Object(_) => {
167                panic!("implementation error")
168            },
169            _ => {
170                if self.chunks.len() == 1 {
171                    Cow::Borrowed(self)
172                } else {
173                    let chunks = vec![concatenate_unchecked(&self.chunks).unwrap()];
174
175                    let mut ca = unsafe { self.copy_with_chunks(chunks) };
176                    use StatisticsFlags as F;
177                    ca.retain_flags_from(self, F::IS_SORTED_ANY | F::CAN_FAST_EXPLODE_LIST);
178                    Cow::Owned(ca)
179                }
180            },
181        }
182    }
183
184    /// Rechunks this ChunkedArray in-place.
185    pub fn rechunk_mut(&mut self) {
186        if self.chunks.len() > 1 {
187            let rechunked = concatenate_unchecked(&self.chunks).unwrap();
188            if self.chunks.capacity() <= 8 {
189                // Reuse chunk allocation if not excessive.
190                self.chunks.clear();
191                self.chunks.push(rechunked);
192            } else {
193                self.chunks = vec![rechunked];
194            }
195        }
196    }
197
198    pub fn rechunk_validity(&self) -> Option<Bitmap> {
199        if self.chunks.len() == 1 {
200            return self.chunks[0].validity().cloned();
201        }
202
203        if !self.has_nulls() || self.is_empty() {
204            return None;
205        }
206
207        let mut bm = BitmapBuilder::with_capacity(self.len());
208        for arr in self.downcast_iter() {
209            if let Some(v) = arr.validity() {
210                bm.extend_from_bitmap(v);
211            } else {
212                bm.extend_constant(arr.len(), true);
213            }
214        }
215        bm.into_opt_validity()
216    }
217
218    pub fn with_validities(&mut self, validities: &[Option<Bitmap>]) {
219        assert_eq!(validities.len(), self.chunks.len());
220
221        // SAFETY:
222        // We don't change the data type of the chunks, nor the length.
223        for (arr, validity) in unsafe { self.chunks_mut().iter_mut() }.zip(validities.iter()) {
224            *arr = arr.with_validity(validity.clone())
225        }
226        self.compute_len();
227    }
228
229    /// Split the array. The chunks are reallocated the underlying data slices are zero copy.
230    ///
231    /// When offset is negative it will be counted from the end of the array.
232    /// This method will never error,
233    /// and will slice the best match when offset, or length is out of bounds
234    pub fn split_at(&self, offset: i64) -> (Self, Self) {
235        // A normal slice, slice the buffers and thus keep the whole memory allocated.
236        let (l, r) = split_at(&self.chunks, offset, self.len());
237        let mut out_l = unsafe { self.copy_with_chunks(l) };
238        let mut out_r = unsafe { self.copy_with_chunks(r) };
239
240        use StatisticsFlags as F;
241        out_l.retain_flags_from(self, F::IS_SORTED_ANY | F::CAN_FAST_EXPLODE_LIST);
242        out_r.retain_flags_from(self, F::IS_SORTED_ANY | F::CAN_FAST_EXPLODE_LIST);
243
244        (out_l, out_r)
245    }
246
247    /// Get a zero copy view of the elements `slice` selects. The chunks are reallocated, the
248    /// buffers are not.
249    pub fn slice(&self, slice: impl Into<Slice>) -> Self {
250        let slice = slice.into();
251
252        // The len: 0 special cases ensure we release memory.
253        // A normal slice, slice the buffers and thus keep the whole memory allocated.
254        let exec = || {
255            let (chunks, len) = self::slice(&self.chunks, slice, self.len());
256            let mut out = unsafe { self.copy_with_chunks(chunks) };
257
258            use StatisticsFlags as F;
259            out.retain_flags_from(self, F::IS_SORTED_ANY | F::CAN_FAST_EXPLODE_LIST);
260            out.length = len;
261
262            out
263        };
264
265        match slice.resolve(self.len()).len() {
266            0 => match self.dtype() {
267                #[cfg(feature = "object")]
268                DataType::Object(_) => exec(),
269                _ => self.clear(),
270            },
271            _ => exec(),
272        }
273    }
274
275    /// Take a view of top n elements
276    #[must_use]
277    pub fn limit(&self, num_elements: usize) -> Self
278    where
279        Self: Sized,
280    {
281        self.slice(Slice::head(num_elements))
282    }
283
284    /// Get the head of the [`ChunkedArray`]
285    #[must_use]
286    pub fn head(&self, length: Option<usize>) -> Self
287    where
288        Self: Sized,
289    {
290        self.slice(Slice::head(length.unwrap_or(10)))
291    }
292
293    /// Get the tail of the [`ChunkedArray`]
294    #[must_use]
295    pub fn tail(&self, length: Option<usize>) -> Self
296    where
297        Self: Sized,
298    {
299        self.slice(Slice::tail(length.unwrap_or(10)))
300    }
301
302    /// Remove empty chunks.
303    pub fn prune_empty_chunks(&mut self) {
304        let mut count = 0u32;
305        unsafe {
306            self.chunks_mut().retain(|arr| {
307                count += 1;
308                // Always keep at least one chunk
309                if count == 1 {
310                    true
311                } else {
312                    // Remove the empty chunks
313                    !arr.is_empty()
314                }
315            })
316        }
317    }
318}
319
320#[cfg(feature = "object")]
321impl<T: PolarsObject> ObjectChunked<T> {
322    pub(crate) fn rechunk_object(&self) -> Self {
323        if self.chunks.len() == 1 {
324            self.clone()
325        } else {
326            use crate::chunked_array::object::registry::run_with_gil;
327
328            run_with_gil(|| {
329                let mut builder = ObjectChunkedBuilder::new(self.name().clone(), self.len());
330                let chunks = self.downcast_iter();
331
332                // todo! use iterators once implemented
333                // no_null path
334                if !self.has_nulls() {
335                    for arr in chunks {
336                        for idx in 0..arr.len() {
337                            builder.append_value(arr.value(idx).clone())
338                        }
339                    }
340                } else {
341                    for arr in chunks {
342                        for idx in 0..arr.len() {
343                            if arr.is_valid(idx) {
344                                builder.append_value(arr.value(idx).clone())
345                            } else {
346                                builder.append_null()
347                            }
348                        }
349                    }
350                }
351                builder.finish()
352            })
353        }
354    }
355}
356
357#[cfg(test)]
358mod test {
359    #[cfg(feature = "dtype-categorical")]
360    use crate::prelude::*;
361
362    #[test]
363    #[cfg(feature = "dtype-categorical")]
364    fn test_categorical_map_after_rechunk() {
365        let s = Series::new(PlSmallStr::EMPTY, &["foo", "bar", "spam"]);
366        let mut a = s
367            .cast(&DataType::from_categories(Categories::global()))
368            .unwrap();
369
370        a.append(&a.slice(Slice::head(2))).unwrap();
371        let a = a.rechunk();
372        assert!(a.cat32().unwrap().get_mapping().num_cats_upper_bound() > 0);
373    }
374}