cel_runtime/
c_stack_list.rs

1//! A [`CStackList`] is a [`List`] with guaranteed memory layout (`repr(C)`). The tail is stored
2//! first, so appending items does not change the memory layout of prior items (though the required
3//! alignment may increase). [`CNil<T>`] represents the empty list where `T` is used to hide the
4//! tail for [`std::ops::RangeTo`] and [`std::ops::RangeToInclusive`] indexing.
5//!
6//! See <https://doc.rust-lang.org/stable/reference/type-layout.html#r-layout.repr.c.struct>
7//!
8//! # Indexing
9//!
10//! Indexing is done using the [`typenum::uint::UInt`] type integral constants.
11//!
12//! Because the [`std::ops::Range`] trait requires a `start` and `end` that are the same type,
13//! it cannot be implemented for `List` types. Instead we use the [`std::ops::RangeFrom`] and
14//! [`std::ops::RangeTo`]
15//! traits. To Access a range of elements, you can use the syntax `list[..end][start..]`.
16//!
17//! # Example
18//!
19//!
20//! ```rust
21//! use cel_runtime::*;
22//! use typenum::*;
23//!
24//! let list = (1, 2.5, 3, 4, "world", "Hello").into_c_stack_list();
25//! assert_eq!(list[..U5::new()][U2::new()..], (3, 4, "world").into_c_stack_list());
26//! ```
27//!
28//! Indexing out of bounds will result in a compile error.
29//!
30//! ```compile_fail,E0277
31//! use cel_runtime::c_stack_list::*;
32//! use typenum::*;
33//!
34//! let list = (1, 2.5, 3, 4, "world", "Hello").into_c_stack_list()[U6::new()];
35//! ```
36use std::mem::offset_of;
37use std::ops::{Index, RangeFrom, RangeTo, RangeToInclusive, Sub};
38use std::{fmt, ptr};
39
40use typenum::{B1, Bit, Sub1, U0, UInt, Unsigned};
41
42use crate::list_traits::{
43    EmptyList, IntoList, List, ListIndex, ListTypeIterator, ListTypeIteratorAdvance,
44    ListTypeProperty,
45};
46
47/// A list using a guaranteed memory layout (`repr(C)`), with tail stored first so appending items
48/// does not change the memory layout of prior items.
49#[repr(C)]
50#[derive(Clone)]
51pub struct CStackList<H, T: CStackListHeadLimit>(pub T, pub H);
52
53/// A trait describing the memory layout of a [`CStackList`].
54/// Describes the memory layout of a [`CStackList`]'s head and tail boundary.
55pub trait CStackListHeadLimit {
56    /// The offset to the _end_ of the head element.
57    const HEAD_LIMIT: usize;
58}
59
60/// Indicates whether the head element is padded to satisfy alignment.
61pub trait CStackListHeadPadded {
62    /// Whether the head element is padded to the next alignment boundary.
63    const HEAD_PADDED: bool;
64}
65
66impl<H: 'static, T: CStackListHeadLimit> CStackListHeadPadded for CStackList<H, T> {
67    const HEAD_PADDED: bool = offset_of!(Self, 1) != T::HEAD_LIMIT;
68}
69
70impl<H: 'static, T: CStackListHeadLimit> CStackListHeadLimit for CStackList<H, T> {
71    const HEAD_LIMIT: usize = offset_of!(Self, 1) + size_of::<H>();
72}
73
74impl<T: CStackListHeadLimit> CStackListHeadLimit for CNil<T> {
75    const HEAD_LIMIT: usize = T::HEAD_LIMIT;
76}
77
78impl CStackListHeadLimit for () {
79    const HEAD_LIMIT: usize = 0;
80}
81
82impl<H: 'static, T: List + CStackListHeadLimit> List for CStackList<H, T> {
83    type Empty = CNil<()>;
84    fn empty() -> Self::Empty {
85        CNil(())
86    }
87
88    type Head = H;
89    fn head(&self) -> &Self::Head {
90        &self.1
91    }
92
93    type Tail = T;
94    fn tail(&self) -> &Self::Tail {
95        &self.0
96    }
97
98    type Push<U: 'static> = CStackList<U, Self>;
99    fn push<U: 'static>(self, item: U) -> Self::Push<U> {
100        CStackList(self, item)
101    }
102
103    type Append<U: List> = <T::Append<U> as List>::Push<H>;
104    fn append<U: List>(self, other: U) -> Self::Append<U> {
105        self.0.append(other).push(self.1)
106    }
107
108    type ReverseOnto<U: List> = T::ReverseOnto<U::Push<H>>;
109    fn reverse_onto<U: List>(self, other: U) -> Self::ReverseOnto<U> {
110        self.0.reverse_onto(other.push(self.1))
111    }
112}
113
114/// Converts tuples and list-like values into a source-ordered [`CStackList`].
115///
116/// The first source field becomes the logical head, even though each `repr(C)`
117/// node physically stores its tail before its head.
118///
119/// # Examples
120///
121/// ```
122/// use cel_runtime::{IntoCStackList, IntoRustTuple};
123///
124/// let list = (String::from("left"), 7_u8).into_c_stack_list();
125/// assert_eq!(list.into_rust_tuple(), (String::from("left"), 7));
126/// ```
127pub trait IntoCStackList {
128    /// The resulting list type.
129    type Output: List;
130    /// Moves fields into a `CStackList`, preserving logical source order.
131    ///
132    /// - Complexity: Native tuple conversions take O(n) field moves for n fields,
133    ///   without heap allocation.
134    ///
135    /// # Examples
136    ///
137    /// ```
138    /// use cel_runtime::{IntoCStackList, List};
139    ///
140    /// assert_eq!((1_u8, 2_u16).into_c_stack_list().len(), 2);
141    /// ```
142    fn into_c_stack_list(self) -> Self::Output;
143}
144
145impl<T: IntoList> IntoCStackList for T {
146    type Output = T::Output<CNil<()>>;
147    fn into_c_stack_list(self) -> Self::Output {
148        self.into_list()
149    }
150}
151
152/// Moves a canonical list into a native Rust tuple in logical source order.
153///
154/// Canonical lists terminate in [`CNil<()>`]. Native tuple bridges support zero
155/// through twelve fields; lists themselves have no arity limit. Nested list
156/// fields remain lists rather than being recursively converted or flattened.
157/// Conversion requires no cloning, equality, or formatting capabilities.
158///
159/// # Examples
160///
161/// ```
162/// use cel_runtime::{IntoCStackList, IntoRustTuple};
163///
164/// let list = (String::from("left"), 7_u8, 2.5_f64).into_c_stack_list();
165/// let value: (String, u8, f64) = list.into_rust_tuple();
166/// assert_eq!(value, (String::from("left"), 7, 2.5));
167/// ```
168pub trait IntoRustTuple {
169    /// The native tuple type with fields in logical source order.
170    type Tuple;
171
172    /// Moves each logical field into the corresponding native tuple field.
173    ///
174    /// - Complexity: O(n) field moves for n fields, without heap allocation.
175    ///
176    /// # Examples
177    ///
178    /// ```
179    /// use cel_runtime::{IntoCStackList, IntoRustTuple};
180    ///
181    /// let value: (String,) = (String::from("owned"),)
182    ///     .into_c_stack_list()
183    ///     .into_rust_tuple();
184    /// assert_eq!(value.0, "owned");
185    /// ```
186    fn into_rust_tuple(self) -> Self::Tuple;
187}
188
189impl IntoRustTuple for CNil<()> {
190    type Tuple = ();
191
192    fn into_rust_tuple(self) -> Self::Tuple {}
193}
194
195/// Implements native tuple bridges by destructuring tail-first canonical nodes.
196macro_rules! impl_rust_tuple {
197    (@type) => { CNil<()> };
198    (@type $head:ident $(, $tail:ident)*) => {
199        CStackList<$head, impl_rust_tuple!(@type $($tail),*)>
200    };
201    (@pattern) => { CNil(()) };
202    (@pattern $head:ident $(, $tail:ident)*) => {
203        CStackList(impl_rust_tuple!(@pattern $($tail),*), $head)
204    };
205    ($($head:ident : $value:ident),+) => {
206        impl<$($head: 'static),+> IntoRustTuple for impl_rust_tuple!(@type $($head),+) {
207            type Tuple = ($($head,)+);
208
209            fn into_rust_tuple(self) -> Self::Tuple {
210                let impl_rust_tuple!(@pattern $($value),+) = self;
211                ($($value,)+)
212            }
213        }
214    };
215}
216
217impl_rust_tuple!(A: a);
218impl_rust_tuple!(A: a, B: b);
219impl_rust_tuple!(A: a, B: b, C: c);
220impl_rust_tuple!(A: a, B: b, C: c, D: d);
221impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e);
222impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f);
223impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f, G: g);
224impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f, G: g, H: h);
225impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f, G: g, H: h, I: i);
226impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f, G: g, H: h, I: i, J: j);
227impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f, G: g, H: h, I: i, J: j, K: k);
228impl_rust_tuple!(A: a, B: b, C: c, D: d, E: e, F: f, G: g, H: h, I: i, J: j, K: k, L: l);
229
230impl<H: 'static, T: List + CStackListHeadLimit> ListIndex<RangeFrom<U0>> for CStackList<H, T> {
231    type Output = CStackList<H, T>;
232    fn index(&self, _index: RangeFrom<U0>) -> &Self::Output {
233        self
234    }
235}
236
237impl<H: 'static, T: List + CStackListHeadLimit, U: Unsigned, B: Bit>
238    ListIndex<RangeFrom<UInt<U, B>>> for CStackList<H, T>
239where
240    T: ListIndex<RangeFrom<Sub1<UInt<U, B>>>>,
241    UInt<U, B>: Sub<B1>,
242{
243    type Output = <T as ListIndex<RangeFrom<Sub1<UInt<U, B>>>>>::Output;
244    fn index(&self, index: RangeFrom<UInt<U, B>>) -> &Self::Output {
245        self.tail().index((index.start - B1)..)
246    }
247}
248
249impl<H: 'static, T: List + CStackListHeadLimit> ListIndex<RangeTo<U0>> for CStackList<H, T> {
250    type Output = CNil<CStackList<H, T>>;
251    fn index(&self, _index: RangeTo<U0>) -> &Self::Output {
252        unsafe { &*ptr::from_ref(self).cast::<Self::Output>() }
253    }
254}
255
256type TailRangeTo<T, U, B> = <T as ListIndex<RangeTo<Sub1<UInt<U, B>>>>>::Output;
257
258impl<H: 'static, T: List + CStackListHeadLimit, U: Unsigned, B: Bit> ListIndex<RangeTo<UInt<U, B>>>
259    for CStackList<H, T>
260where
261    T: ListIndex<RangeTo<Sub1<UInt<U, B>>>>,
262    TailRangeTo<T, U, B>: List,
263    UInt<U, B>: Sub<B1>,
264{
265    type Output = <TailRangeTo<T, U, B> as List>::Push<H>;
266    fn index(&self, _index: RangeTo<UInt<U, B>>) -> &Self::Output {
267        unsafe { &*ptr::from_ref(self).cast::<Self::Output>() }
268    }
269}
270
271impl<H: 'static, T: List + CStackListHeadLimit> ListIndex<RangeToInclusive<U0>>
272    for CStackList<H, T>
273{
274    type Output = CStackList<H, CNil<T>>;
275    fn index(&self, _index: RangeToInclusive<U0>) -> &Self::Output {
276        unsafe { &*ptr::from_ref(self).cast::<Self::Output>() }
277    }
278}
279
280type TailRangeToInclusive<T, U, B> = <T as ListIndex<RangeToInclusive<Sub1<UInt<U, B>>>>>::Output;
281
282impl<H: 'static, T: List + CStackListHeadLimit, U: Unsigned, B: Bit>
283    ListIndex<RangeToInclusive<UInt<U, B>>> for CStackList<H, T>
284where
285    T: ListIndex<RangeToInclusive<Sub1<UInt<U, B>>>>,
286    TailRangeToInclusive<T, U, B>: List,
287    UInt<U, B>: Sub<B1>,
288{
289    type Output = <TailRangeToInclusive<T, U, B> as List>::Push<H>;
290    fn index(&self, _index: RangeToInclusive<UInt<U, B>>) -> &Self::Output {
291        unsafe { &*ptr::from_ref(self).cast::<Self::Output>() }
292    }
293}
294
295impl<H: 'static, T: List + CStackListHeadLimit> ListIndex<U0> for CStackList<H, T> {
296    type Output = H;
297    fn index(&self, _index: U0) -> &Self::Output {
298        self.head()
299    }
300}
301
302impl<H: 'static, T: List + CStackListHeadLimit, U: Unsigned, B: Bit> ListIndex<UInt<U, B>>
303    for CStackList<H, T>
304where
305    T: ListIndex<Sub1<UInt<U, B>>>,
306    UInt<U, B>: Sub<B1>,
307{
308    type Output = <T as ListIndex<Sub1<UInt<U, B>>>>::Output;
309    fn index(&self, index: UInt<U, B>) -> &Self::Output {
310        self.tail().index(index - B1)
311    }
312}
313
314// Implement Index in terms of ListIndex for CStackList
315impl<H: 'static, T: List + CStackListHeadLimit, Idx> Index<Idx> for CStackList<H, T>
316where
317    Self: ListIndex<Idx>,
318    <Self as ListIndex<Idx>>::Output: Sized,
319{
320    type Output = <Self as ListIndex<Idx>>::Output;
321    fn index(&self, index: Idx) -> &Self::Output {
322        ListIndex::index(self, index)
323    }
324}
325
326// Move this to an #[derive(DebugList)] macro
327trait DebugHelper {
328    fn fmt_helper(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
329}
330
331impl<T: CStackListHeadLimit> DebugHelper for CNil<T> {
332    fn fmt_helper(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
333        write!(f, ")")
334    }
335}
336
337impl<H: 'static, T: List + CStackListHeadLimit> DebugHelper for CStackList<H, T>
338where
339    H: fmt::Debug,
340    T: DebugHelper,
341{
342    fn fmt_helper(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
343        write!(f, ", {:?}", self.head())?;
344        self.tail().fmt_helper(f)
345    }
346}
347
348impl<T: CStackListHeadLimit> fmt::Debug for CNil<T> {
349    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
350        write!(f, "()")
351    }
352}
353
354impl<H: 'static, T: List + CStackListHeadLimit> fmt::Debug for CStackList<H, T>
355where
356    H: fmt::Debug,
357    T: DebugHelper,
358{
359    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
360        write!(f, "({:?}", self.head())?;
361        self.tail().fmt_helper(f)
362    }
363}
364
365impl<T: List + CStackListHeadLimit, O: List> std::cmp::PartialEq<O> for CNil<T> {
366    fn eq(&self, other: &O) -> bool {
367        other.is_empty()
368    }
369}
370
371impl<H: 'static, T: List + CStackListHeadLimit, O: List> std::cmp::PartialEq<O> for CStackList<H, T>
372where
373    H: PartialEq<O::Head>,
374    T: PartialEq<O::Tail>,
375{
376    fn eq(&self, other: &O) -> bool {
377        self.head() == other.head() && self.tail() == other.tail()
378    }
379}
380
381/// Empty `repr(C)` list used as the tail sentinel for [`CStackList`].
382#[repr(C)]
383#[derive(Clone)]
384pub struct CNil<T: CStackListHeadLimit>(T);
385
386impl<T: CStackListHeadLimit> EmptyList for CNil<T> {
387    type PushFirst<U: 'static> = CStackList<U, CNil<T>>;
388    fn push_first<U: 'static>(self, item: U) -> Self::PushFirst<U> {
389        CStackList(self, item)
390    }
391
392    type RootEmpty = CNil<()>;
393    fn root_empty() -> Self::RootEmpty {
394        CNil(())
395    }
396}
397
398impl<T: CStackListHeadLimit, P: ListTypeProperty> ListTypeIteratorAdvance<P> for CNil<T> {
399    fn advancer<R: List>(_iter: &mut ListTypeIterator<R, P>) -> Option<P::Output> {
400        None
401    }
402}
403
404impl<P: ListTypeProperty, H: 'static, T: ListTypeIteratorAdvance<P> + CStackListHeadLimit>
405    ListTypeIteratorAdvance<P> for CStackList<H, T>
406{
407    fn advancer<R: List>(iter: &mut ListTypeIterator<R, P>) -> Option<P::Output> {
408        iter.advance = T::advancer::<R>;
409        Some(P::property::<CStackList<H, T>>())
410    }
411}
412
413#[cfg(test)]
414mod tests {
415    use typenum::{U1, U2, U5};
416
417    use crate::list_traits::Item;
418
419    use super::*;
420    #[test]
421    fn into_c_stack_list() {
422        let list = (1, 2.5, 3, 4, "world", "Hello").into_c_stack_list();
423        assert_eq!(
424            list,
425            CStackList(
426                CStackList(
427                    CStackList(
428                        CStackList(CStackList(CStackList(CNil(()), "Hello"), "world"), 4),
429                        3
430                    ),
431                    2.5
432                ),
433                1
434            )
435        );
436        assert_eq!(().into_c_stack_list(), CNil(()));
437    }
438
439    #[test]
440    fn index() {
441        let list = (1, 2.5, "Hello").into_c_stack_list();
442        assert_eq!(list[U0::new()], 1);
443        assert_eq!(list[U1::new()], 2.5);
444        assert_eq!(list[U2::new()], "Hello");
445    }
446
447    #[test]
448    fn slice() {
449        let list = (1, 2.5, 3, 4, "world", "Hello").into_c_stack_list();
450        println!("{:?}", list[..U5::new()][U2::new()..]);
451    }
452
453    #[test]
454    fn index_range_from() {
455        let list = (1, 2.5, "Hello").into_c_stack_list();
456        assert_eq!(list[U1::new()..][U1::new()], "Hello");
457    }
458
459    #[test]
460    fn index_range_to() {
461        let list = (1, 2.5, "Hello").into_c_stack_list();
462        assert_eq!(list[..U2::new()][U1::new()], 2.5);
463    }
464
465    #[test]
466    fn index_type() {
467        use std::any::type_name;
468
469        type List = <(i32, f64, &'static str) as IntoList>::Output<CNil<()>>;
470        type Zero = Item<List, U0>;
471        type One = Item<List, U1>;
472        type Two = Item<List, U2>;
473        assert_eq!(type_name::<Zero>(), "i32");
474        assert_eq!(type_name::<One>(), "f64");
475        assert_eq!(type_name::<Two>(), "&str");
476    }
477
478    #[test]
479    fn cstack_list() {
480        let list = CStackList(CNil(()), 32i32).push("Hello").push(42.5);
481        // Test that we can cast to a C struct and read values
482        #[repr(C)]
483        struct TestStruct(i32, &'static str, f64);
484
485        let test_struct = unsafe {
486            std::mem::transmute::<
487                CStackList<f64, CStackList<&str, CStackList<i32, CNil<()>>>>,
488                TestStruct,
489            >(list)
490        };
491
492        assert_eq!(test_struct.0, 32);
493        assert_eq!(test_struct.1, "Hello");
494        assert_eq!(test_struct.2, 42.5);
495    }
496}
cel_runtime/c_stack_list.rs

cel_runtime/
c_stack_list.rs
