1 /*
2 * Copyright 2018 Google Inc. All rights reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 use core::fmt::{Debug, Formatter, Result};
18 use core::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator};
19 use core::marker::PhantomData;
20 use core::mem::size_of;
21 use core::slice::from_raw_parts;
22 use core::str::from_utf8_unchecked;
23
24 use crate::endian_scalar::read_scalar_at;
25 #[cfg(target_endian = "little")]
26 use crate::endian_scalar::EndianScalar;
27 use crate::follow::Follow;
28 use crate::primitives::*;
29
30 pub struct Vector<'a, T: 'a>(&'a [u8], usize, PhantomData<T>);
31
32 impl<'a, T: 'a> Default for Vector<'a, T> {
default() -> Self33 fn default() -> Self {
34 // Static, length 0 vector.
35 // Note that derived default causes UB due to issues in read_scalar_at /facepalm.
36 Self(
37 &[0; core::mem::size_of::<UOffsetT>()],
38 0,
39 Default::default(),
40 )
41 }
42 }
43
44 impl<'a, T> Debug for Vector<'a, T>
45 where
46 T: 'a + Follow<'a>,
47 <T as Follow<'a>>::Inner: Debug,
48 {
fmt(&self, f: &mut Formatter) -> Result49 fn fmt(&self, f: &mut Formatter) -> Result {
50 f.debug_list().entries(self.iter()).finish()
51 }
52 }
53
54 // We cannot use derive for these two impls, as it would only implement Copy
55 // and Clone for `T: Copy` and `T: Clone` respectively. However `Vector<'a, T>`
56 // can always be copied, no matter that `T` you have.
57 impl<'a, T> Copy for Vector<'a, T> {}
58 impl<'a, T> Clone for Vector<'a, T> {
clone(&self) -> Self59 fn clone(&self) -> Self {
60 *self
61 }
62 }
63
64 impl<'a, T: 'a> Vector<'a, T> {
65 #[inline(always)]
new(buf: &'a [u8], loc: usize) -> Self66 pub fn new(buf: &'a [u8], loc: usize) -> Self {
67 Vector {
68 0: buf,
69 1: loc,
70 2: PhantomData,
71 }
72 }
73
74 #[inline(always)]
len(&self) -> usize75 pub fn len(&self) -> usize {
76 unsafe { read_scalar_at::<UOffsetT>(self.0, self.1) as usize }
77 }
78 #[inline(always)]
is_empty(&self) -> bool79 pub fn is_empty(&self) -> bool {
80 self.len() == 0
81 }
82 }
83
84 impl<'a, T: Follow<'a> + 'a> Vector<'a, T> {
85 #[inline(always)]
get(&self, idx: usize) -> T::Inner86 pub fn get(&self, idx: usize) -> T::Inner {
87 assert!(idx < self.len() as usize);
88 let sz = size_of::<T>();
89 debug_assert!(sz > 0);
90 T::follow(self.0, self.1 as usize + SIZE_UOFFSET + sz * idx)
91 }
92
93 #[inline(always)]
iter(&self) -> VectorIter<'a, T>94 pub fn iter(&self) -> VectorIter<'a, T> {
95 VectorIter::from_vector(*self)
96 }
97 }
98
99 pub trait SafeSliceAccess {}
100 impl<'a, T: SafeSliceAccess + 'a> Vector<'a, T> {
safe_slice(self) -> &'a [T]101 pub fn safe_slice(self) -> &'a [T] {
102 let buf = self.0;
103 let loc = self.1;
104 let sz = size_of::<T>();
105 debug_assert!(sz > 0);
106 let len = unsafe { read_scalar_at::<UOffsetT>(buf, loc) } as usize;
107 let data_buf = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len * sz];
108 let ptr = data_buf.as_ptr() as *const T;
109 let s: &'a [T] = unsafe { from_raw_parts(ptr, len) };
110 s
111 }
112 }
113
114 impl SafeSliceAccess for u8 {}
115 impl SafeSliceAccess for i8 {}
116 impl SafeSliceAccess for bool {}
117
118 // TODO(caspern): Get rid of this. Conditional compliation is unnecessary complexity.
119 // Vectors of primitives just don't work on big endian machines!!!
120 #[cfg(target_endian = "little")]
121 mod le_safe_slice_impls {
122 impl super::SafeSliceAccess for u16 {}
123 impl super::SafeSliceAccess for u32 {}
124 impl super::SafeSliceAccess for u64 {}
125
126 impl super::SafeSliceAccess for i16 {}
127 impl super::SafeSliceAccess for i32 {}
128 impl super::SafeSliceAccess for i64 {}
129
130 impl super::SafeSliceAccess for f32 {}
131 impl super::SafeSliceAccess for f64 {}
132 }
133
134 #[cfg(target_endian = "little")]
135 pub use self::le_safe_slice_impls::*;
136
follow_cast_ref<'a, T: Sized + 'a>(buf: &'a [u8], loc: usize) -> &'a T137 pub fn follow_cast_ref<'a, T: Sized + 'a>(buf: &'a [u8], loc: usize) -> &'a T {
138 let sz = size_of::<T>();
139 let buf = &buf[loc..loc + sz];
140 let ptr = buf.as_ptr() as *const T;
141 unsafe { &*ptr }
142 }
143
144 impl<'a> Follow<'a> for &'a str {
145 type Inner = &'a str;
follow(buf: &'a [u8], loc: usize) -> Self::Inner146 fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
147 let len = unsafe { read_scalar_at::<UOffsetT>(buf, loc) } as usize;
148 let slice = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len];
149 unsafe { from_utf8_unchecked(slice) }
150 }
151 }
152
153 #[cfg(target_endian = "little")]
follow_slice_helper<T>(buf: &[u8], loc: usize) -> &[T]154 fn follow_slice_helper<T>(buf: &[u8], loc: usize) -> &[T] {
155 let sz = size_of::<T>();
156 debug_assert!(sz > 0);
157 let len = unsafe { read_scalar_at::<UOffsetT>(buf, loc) as usize };
158 let data_buf = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len * sz];
159 let ptr = data_buf.as_ptr() as *const T;
160 let s: &[T] = unsafe { from_raw_parts(ptr, len) };
161 s
162 }
163
164 /// Implement direct slice access if the host is little-endian.
165 #[cfg(target_endian = "little")]
166 impl<'a, T: EndianScalar> Follow<'a> for &'a [T] {
167 type Inner = &'a [T];
follow(buf: &'a [u8], loc: usize) -> Self::Inner168 fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
169 follow_slice_helper::<T>(buf, loc)
170 }
171 }
172
173 /// Implement Follow for all possible Vectors that have Follow-able elements.
174 impl<'a, T: Follow<'a> + 'a> Follow<'a> for Vector<'a, T> {
175 type Inner = Vector<'a, T>;
follow(buf: &'a [u8], loc: usize) -> Self::Inner176 fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
177 Vector::new(buf, loc)
178 }
179 }
180
181 /// An iterator over a `Vector`.
182 #[derive(Debug)]
183 pub struct VectorIter<'a, T: 'a> {
184 buf: &'a [u8],
185 loc: usize,
186 remaining: usize,
187 phantom: PhantomData<T>,
188 }
189
190 impl<'a, T: 'a> VectorIter<'a, T> {
191 #[inline]
from_vector(inner: Vector<'a, T>) -> Self192 pub fn from_vector(inner: Vector<'a, T>) -> Self {
193 VectorIter {
194 buf: inner.0,
195 // inner.1 is the location of the data for the vector.
196 // The first SIZE_UOFFSET bytes is the length. We skip
197 // that to get to the actual vector content.
198 loc: inner.1 + SIZE_UOFFSET,
199 remaining: inner.len(),
200 phantom: PhantomData,
201 }
202 }
203
204 #[inline]
from_slice(buf: &'a [u8], items_num: usize) -> Self205 pub fn from_slice(buf: &'a [u8], items_num: usize) -> Self {
206 VectorIter {
207 buf,
208 loc: 0,
209 remaining: items_num,
210 phantom: PhantomData,
211 }
212 }
213 }
214
215 impl<'a, T: Follow<'a> + 'a> Clone for VectorIter<'a, T> {
216 #[inline]
clone(&self) -> Self217 fn clone(&self) -> Self {
218 VectorIter {
219 buf: self.buf,
220 loc: self.loc,
221 remaining: self.remaining,
222 phantom: self.phantom,
223 }
224 }
225 }
226
227 impl<'a, T: Follow<'a> + 'a> Iterator for VectorIter<'a, T> {
228 type Item = T::Inner;
229
230 #[inline]
next(&mut self) -> Option<T::Inner>231 fn next(&mut self) -> Option<T::Inner> {
232 let sz = size_of::<T>();
233 debug_assert!(sz > 0);
234
235 if self.remaining == 0 {
236 None
237 } else {
238 let result = T::follow(self.buf, self.loc);
239 self.loc += sz;
240 self.remaining -= 1;
241 Some(result)
242 }
243 }
244
245 #[inline]
nth(&mut self, n: usize) -> Option<T::Inner>246 fn nth(&mut self, n: usize) -> Option<T::Inner> {
247 let sz = size_of::<T>();
248 debug_assert!(sz > 0);
249
250 self.remaining = self.remaining.saturating_sub(n);
251
252 // Note that this might overflow, but that is okay because
253 // in that case self.remaining will have been set to zero.
254 self.loc = self.loc.wrapping_add(sz * n);
255
256 self.next()
257 }
258
259 #[inline]
size_hint(&self) -> (usize, Option<usize>)260 fn size_hint(&self) -> (usize, Option<usize>) {
261 (self.remaining, Some(self.remaining))
262 }
263 }
264
265 impl<'a, T: Follow<'a> + 'a> DoubleEndedIterator for VectorIter<'a, T> {
266 #[inline]
next_back(&mut self) -> Option<T::Inner>267 fn next_back(&mut self) -> Option<T::Inner> {
268 let sz = size_of::<T>();
269 debug_assert!(sz > 0);
270
271 if self.remaining == 0 {
272 None
273 } else {
274 self.remaining -= 1;
275 Some(T::follow(self.buf, self.loc + sz * self.remaining))
276 }
277 }
278
279 #[inline]
nth_back(&mut self, n: usize) -> Option<T::Inner>280 fn nth_back(&mut self, n: usize) -> Option<T::Inner> {
281 self.remaining = self.remaining.saturating_sub(n);
282 self.next_back()
283 }
284 }
285
286 impl<'a, T: 'a + Follow<'a>> ExactSizeIterator for VectorIter<'a, T> {
287 #[inline]
len(&self) -> usize288 fn len(&self) -> usize {
289 self.remaining
290 }
291 }
292
293 impl<'a, T: 'a + Follow<'a>> FusedIterator for VectorIter<'a, T> {}
294
295 impl<'a, T: Follow<'a> + 'a> IntoIterator for Vector<'a, T> {
296 type Item = T::Inner;
297 type IntoIter = VectorIter<'a, T>;
298 #[inline]
into_iter(self) -> Self::IntoIter299 fn into_iter(self) -> Self::IntoIter {
300 self.iter()
301 }
302 }
303
304 impl<'a, 'b, T: Follow<'a> + 'a> IntoIterator for &'b Vector<'a, T> {
305 type Item = T::Inner;
306 type IntoIter = VectorIter<'a, T>;
into_iter(self) -> Self::IntoIter307 fn into_iter(self) -> Self::IntoIter {
308 self.iter()
309 }
310 }
311
312 #[cfg(feature="serialize")]
313 impl<'a, T> serde::ser::Serialize for Vector<'a, T>
314 where
315 T: 'a + Follow<'a>,
316 <T as Follow<'a>>::Inner: serde::ser::Serialize,
317 {
serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error> where S: serde::ser::Serializer,318 fn serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error>
319 where
320 S: serde::ser::Serializer,
321 {
322 use serde::ser::SerializeSeq;
323 let mut seq = serializer.serialize_seq(Some(self.len()))?;
324 for element in self {
325 seq.serialize_element(&element)?;
326 }
327 seq.end()
328 }
329 }
330