iris_guard/
indirect.rs

1//! The two arrays that do not hold their own values.
2//!
3//! A dictionary array holds keys into a dictionary that arrives separately, and a view array holds
4//! views into data buffers that may not be the ones next to it. Both are an index into something
5//! else, and an index into something else is where a checker earns its keep: the failure is not a
6//! short buffer, it is a number that happens to be in range for the wrong thing.
7//!
8//! Neither type can be carried in a batch yet, and [`crate::layout`] refuses both by name. The
9//! checks are written and tested here anyway, because the checks are the part that has to be right
10//! and having them ready is what makes carrying these types later a format question rather than a
11//! safety question.
12
13use arrow_schema::DataType;
14
15use crate::error::{Invariant, Result, Violation};
16
17/// How wide one view is, in bytes.
18///
19/// Fixed by the Arrow specification: a four byte length, then either twelve bytes of inline data or
20/// a four byte prefix, a buffer index and an offset.
21pub const VIEW_WIDTH: usize = 16;
22
23/// The longest value that fits inside a view rather than in a data buffer.
24pub const VIEW_INLINE: u32 = 12;
25
26/// Checks that every key is a slot in the dictionary.
27///
28/// The case worth naming is a key equal to the dictionary's length, which is in range for the
29/// arithmetic and one past the end of the data, and is what an off by one in a decoder produces.
30///
31/// # Errors
32///
33/// Returns a violation of [`Invariant::DictionaryIndex`] for a key that is negative or not less
34/// than `dictionary_len`, of [`Invariant::BufferLength`] if the keys buffer is short, and of
35/// [`Invariant::Unsupported`] if the key type is not an integer.
36pub fn check_dictionary(
37    keys: &[u8],
38    key_type: &DataType,
39    len: u64,
40    dictionary_len: u64,
41    path: &str,
42) -> Result<()> {
43    let (width, signed) = match key_type {
44        DataType::Int8 => (1usize, true),
45        DataType::Int16 => (2, true),
46        DataType::Int32 => (4, true),
47        DataType::Int64 => (8, true),
48        DataType::UInt8 => (1, false),
49        DataType::UInt16 => (2, false),
50        DataType::UInt32 => (4, false),
51        DataType::UInt64 => (8, false),
52        other => {
53            return Err(Violation::at(
54                Invariant::Unsupported,
55                path,
56                format!("{other} is not an integer, so it cannot be a dictionary key"),
57            ));
58        }
59    };
60
61    let slots = usize::try_from(len).map_err(|_| {
62        Violation::at(
63            Invariant::Size,
64            path,
65            format!("{len} keys is more than this host can address"),
66        )
67    })?;
68    let needed = slots.checked_mul(width).ok_or_else(|| {
69        Violation::at(
70            Invariant::Size,
71            path,
72            format!("{len} keys of {width} bytes is more than this host can address"),
73        )
74    })?;
75    if keys.len() < needed {
76        return Err(Violation::at(
77            Invariant::BufferLength,
78            path,
79            format!(
80                "{len} keys need {needed} bytes and there are {}",
81                keys.len()
82            ),
83        ));
84    }
85
86    for slot in 0..slots {
87        let at = slot * width;
88        let raw = &keys[at..at + width];
89        let key = if signed {
90            let value = read_signed(raw);
91            if value < 0 {
92                return Err(Violation::at(
93                    Invariant::DictionaryIndex,
94                    path,
95                    format!("key {slot} is {value}, and a key is a position"),
96                ));
97            }
98            u64::try_from(value).unwrap_or(u64::MAX)
99        } else {
100            read_unsigned(raw)
101        };
102
103        if key >= dictionary_len {
104            return Err(Violation::at(
105                Invariant::DictionaryIndex,
106                path,
107                format!("key {slot} is {key} and the dictionary has {dictionary_len} values"),
108            ));
109        }
110    }
111
112    Ok(())
113}
114
115/// Checks that every view points inside a data buffer that is actually there.
116///
117/// The case worth naming is a buffer index equal to the number of buffers, for the same reason as
118/// the dictionary key: it is the value an off by one produces and it is in range for everything
119/// except the thing it indexes.
120///
121/// # Errors
122///
123/// Returns a violation of [`Invariant::ViewBuffer`] for a view pointing at a buffer that is not
124/// there or past the end of one that is, and of [`Invariant::BufferLength`] if the views buffer is
125/// not a whole number of views or is short.
126pub fn check_views<B: AsRef<[u8]>>(views: &[u8], data: &[B], len: u64, path: &str) -> Result<()> {
127    let slots = usize::try_from(len).map_err(|_| {
128        Violation::at(
129            Invariant::Size,
130            path,
131            format!("{len} views is more than this host can address"),
132        )
133    })?;
134    let needed = slots.checked_mul(VIEW_WIDTH).ok_or_else(|| {
135        Violation::at(
136            Invariant::Size,
137            path,
138            format!("{len} views of {VIEW_WIDTH} bytes is more than this host can address"),
139        )
140    })?;
141    if views.len() < needed {
142        return Err(Violation::at(
143            Invariant::BufferLength,
144            path,
145            format!(
146                "{len} views need {needed} bytes and there are {}",
147                views.len()
148            ),
149        ));
150    }
151
152    for slot in 0..slots {
153        let at = slot * VIEW_WIDTH;
154        let view = &views[at..at + VIEW_WIDTH];
155        let length = read_u32(&view[0..4]);
156
157        // A short value lives in the view itself and points at nothing, so there is nothing here to
158        // be out of range.
159        if length <= VIEW_INLINE {
160            continue;
161        }
162
163        let index = read_u32(&view[8..12]);
164        let offset = read_u32(&view[12..16]);
165
166        let buffer = usize::try_from(index)
167            .ok()
168            .and_then(|index| data.get(index))
169            .ok_or_else(|| {
170                Violation::at(
171                    Invariant::ViewBuffer,
172                    path,
173                    format!(
174                        "view {slot} points at data buffer {index} and there are {}",
175                        data.len()
176                    ),
177                )
178            })?;
179
180        let end = u64::from(offset) + u64::from(length);
181        let have = u64::try_from(buffer.as_ref().len()).unwrap_or(u64::MAX);
182        if end > have {
183            return Err(Violation::at(
184                Invariant::ViewBuffer,
185                path,
186                format!(
187                    "view {slot} reads {length} bytes at {offset} of data buffer {index}, which is \
188                     {have} bytes"
189                ),
190            ));
191        }
192    }
193
194    Ok(())
195}
196
197fn read_signed(raw: &[u8]) -> i64 {
198    let mut wide = [0u8; 8];
199    wide[..raw.len()].copy_from_slice(raw);
200    let value = i64::from_le_bytes(wide);
201    // Sign extend from the width that was actually read.
202    let spare = 64 - u32::try_from(raw.len()).unwrap_or(8) * 8;
203    (value << spare) >> spare
204}
205
206fn read_unsigned(raw: &[u8]) -> u64 {
207    let mut wide = [0u8; 8];
208    wide[..raw.len()].copy_from_slice(raw);
209    u64::from_le_bytes(wide)
210}
211
212fn read_u32(raw: &[u8]) -> u32 {
213    let mut wide = [0u8; 4];
214    wide.copy_from_slice(raw);
215    u32::from_le_bytes(wide)
216}
217
218#[cfg(test)]
219mod tests {
220    use arrow_schema::DataType;
221
222    use super::{check_dictionary, check_views};
223    use crate::error::Invariant;
224
225    fn view(length: u32, index: u32, offset: u32) -> Vec<u8> {
226        let mut out = Vec::with_capacity(16);
227        out.extend_from_slice(&length.to_le_bytes());
228        out.extend_from_slice(&[0u8; 4]);
229        out.extend_from_slice(&index.to_le_bytes());
230        out.extend_from_slice(&offset.to_le_bytes());
231        out
232    }
233
234    #[test]
235    fn keys_inside_the_dictionary_pass() {
236        let keys: Vec<u8> = [0i32, 1, 2].iter().flat_map(|k| k.to_le_bytes()).collect();
237        check_dictionary(&keys, &DataType::Int32, 3, 3, "d").expect("every key is a slot");
238    }
239
240    #[test]
241    fn a_key_equal_to_the_dictionary_length_is_caught() {
242        let keys: Vec<u8> = [0i32, 3].iter().flat_map(|k| k.to_le_bytes()).collect();
243        let err = check_dictionary(&keys, &DataType::Int32, 2, 3, "d")
244            .expect_err("three is one past the last slot");
245        assert_eq!(err.invariant, Invariant::DictionaryIndex);
246        assert!(err.to_string().contains("has 3 values"), "{err}");
247    }
248
249    #[test]
250    fn a_negative_key_is_caught_rather_than_read_as_enormous() {
251        let keys: Vec<u8> = (-1i32).to_le_bytes().to_vec();
252        let err =
253            check_dictionary(&keys, &DataType::Int32, 1, 3, "d").expect_err("a key is a position");
254        assert_eq!(err.invariant, Invariant::DictionaryIndex);
255        assert!(err.to_string().contains("is -1"), "{err}");
256    }
257
258    #[test]
259    fn an_unsigned_key_type_is_read_as_unsigned() {
260        let keys: Vec<u8> = 200u8.to_le_bytes().to_vec();
261        check_dictionary(&keys, &DataType::UInt8, 1, 255, "d").expect("200 is a slot in 255");
262        let err = check_dictionary(&keys, &DataType::UInt8, 1, 200, "d")
263            .expect_err("200 is not a slot in 200");
264        assert_eq!(err.invariant, Invariant::DictionaryIndex);
265    }
266
267    #[test]
268    fn a_key_type_that_is_not_an_integer_is_refused_by_name() {
269        let err = check_dictionary(&[], &DataType::Utf8, 0, 0, "d")
270            .expect_err("a string is not a key type");
271        assert_eq!(err.invariant, Invariant::Unsupported);
272    }
273
274    #[test]
275    fn views_inside_their_buffers_pass() {
276        let data: Vec<Vec<u8>> = vec![b"hello there friend".to_vec()];
277        let views = [view(18, 0, 0), view(4, 0, 3)].concat();
278        check_views(&views, &data, 2, "v").expect("both views are inside the buffer");
279    }
280
281    #[test]
282    fn a_view_buffer_index_equal_to_the_buffer_count_is_caught() {
283        let data: Vec<Vec<u8>> = vec![b"hello there friend".to_vec()];
284        let views = view(18, 1, 0);
285        let err = check_views(&views, &data, 1, "v").expect_err("there is no buffer 1");
286        assert_eq!(err.invariant, Invariant::ViewBuffer);
287        assert!(err.to_string().contains("there are 1"), "{err}");
288    }
289
290    #[test]
291    fn a_view_that_runs_off_the_end_of_its_buffer_is_caught() {
292        let data: Vec<Vec<u8>> = vec![b"hello there friend".to_vec()];
293        let views = view(18, 0, 1);
294        let err = check_views(&views, &data, 1, "v").expect_err("that is one byte too many");
295        assert_eq!(err.invariant, Invariant::ViewBuffer);
296    }
297
298    #[test]
299    fn a_short_value_lives_in_the_view_and_points_at_nothing() {
300        let data: Vec<Vec<u8>> = Vec::new();
301        let views = view(12, 99, 99);
302        check_views(&views, &data, 1, "v").expect("an inline value indexes nothing");
303    }
304
305    #[test]
306    fn a_views_buffer_that_is_short_is_caught() {
307        let data: Vec<Vec<u8>> = Vec::new();
308        let err = check_views(&[0u8; 8], &data, 1, "v").expect_err("a view is sixteen bytes");
309        assert_eq!(err.invariant, Invariant::BufferLength);
310    }
311}
iris_guard/indirect.rs

iris_guard/
indirect.rs
