cel_runtime/
list_traits.rs

1//! A collection of traits for homegenous lists (cons cells), similar to tuples.
2
3use std::any::TypeId;
4
5/// A trait representing a homogeneous list (cons cell) with a head and tail.
6///
7/// The `List` trait provides a type-safe way to work with lists where each node
8/// contains a value (head) and the remainder of the list (tail). This trait
9/// is implemented for both empty lists and non-empty lists.
10pub trait List {
11    /// The type returned by [`List::empty()`].
12    type Empty: EmptyList;
13    /// Returns a new empty list that can be used to create a list with the same characteristics.
14    fn empty() -> Self::Empty;
15
16    /// The type of head.
17    type Head: 'static;
18    /// Returns a reference to the head.
19    fn head(&self) -> &Self::Head;
20
21    /// The type of the rest of the list.
22    type Tail: List;
23    /// Returns a reference to the rest of the list.
24    fn tail(&self) -> &Self::Tail;
25
26    /// Returns true if the list is empty.
27    fn is_empty(&self) -> bool {
28        self.len() == 0
29    }
30
31    /// The length of the list, computed at compile time.
32    const LENGTH: usize = Self::Tail::LENGTH + 1;
33    /// Returns the length of the list.
34    fn len(&self) -> usize {
35        Self::LENGTH
36    }
37
38    /// The type of the list after pushing a new value.
39    type Push<U: 'static>: List;
40    /// Pushes a new value onto the front of the list, returning a new list.
41    fn push<U: 'static>(self, item: U) -> Self::Push<U>;
42
43    // ---
44
45    /// The style of `List` appended to `Self`
46    type Append<U: List>: List;
47
48    /// Append `U` as the tail of `Self`.
49    ///
50    /// # Example
51    ///
52    /// ```rust
53    /// use cel_runtime::*;
54    ///
55    /// assert_eq!(
56    ///     (1, (2, (3, ()))).append((4, (5, (6, ())))),
57    ///     (1, (2, (3, (4, (5, (6, ()))))))
58    /// );
59    /// ```
60    fn append<U: List>(self, other: U) -> Self::Append<U>;
61
62    /// The resulting list when reversing `Self` onto `U`.
63    type ReverseOnto<U: List>: List;
64    /// Reverse `Self` and append the result to `other`.
65    fn reverse_onto<U: List>(self, other: U) -> Self::ReverseOnto<U>;
66
67    /// Reverse this list, returning a new list with elements in opposite order.
68    fn reverse(self) -> Self::ReverseOnto<Self::Empty>
69    where
70        Self: Sized,
71    {
72        self.reverse_onto(Self::empty())
73    }
74}
75
76/// Convenience alias for reversing a `List` onto its empty counterpart.
77pub type ReverseList<T> = <T as List>::ReverseOnto<<T as List>::Empty>;
78
79// Iterate a list (not recurse) to implement equal against an iterator.
80/// Property generator for iterating over type-level lists.
81pub trait ListTypeProperty {
82    /// The per-element property type produced during iteration.
83    type Output;
84    /// Compute the property for the current list head in `R`.
85    fn property<R: List>() -> Self::Output;
86}
87
88impl ListTypeProperty for TypeId {
89    type Output = Self;
90    fn property<R: List>() -> Self::Output {
91        TypeId::of::<R::Head>()
92    }
93}
94
95/// Iterator over type-level `List` values producing properties via `P`.
96pub struct ListTypeIterator<T: List, P: ListTypeProperty> {
97    pub(crate) advance: fn(&mut Self) -> Option<P::Output>,
98}
99
100/// Advance function provider used by [`ListTypeIterator`].
101pub trait ListTypeIteratorAdvance<P: ListTypeProperty>: List + Sized {
102    /// Advance the iterator, returning the next property value.
103    fn advancer<R: List>(iter: &mut ListTypeIterator<R, P>) -> Option<P::Output>;
104}
105
106impl<T: ListTypeIteratorAdvance<P> + 'static, P: ListTypeProperty> ListTypeIterator<T, P> {
107    /// Construct a new `ListTypeIterator` over `T` producing properties via `P`.
108    #[must_use]
109    pub fn new() -> Self {
110        ListTypeIterator {
111            advance: T::advancer::<T>,
112        }
113    }
114}
115
116impl<T: ListTypeIteratorAdvance<P> + 'static, P: ListTypeProperty> Default
117    for ListTypeIterator<T, P>
118{
119    fn default() -> Self {
120        Self::new()
121    }
122}
123
124impl<T: ListTypeIteratorAdvance<P> + 'static, P: ListTypeProperty> Iterator
125    for ListTypeIterator<T, P>
126{
127    type Item = P::Output;
128    fn next(&mut self) -> Option<Self::Item> {
129        (self.advance)(self)
130    }
131}
132
133/// Iterator that yields the [`TypeId`] of each head in the `List`.
134pub type TypeIdIterator<T> = ListTypeIterator<T, TypeId>;
135
136/// Marker type representing the head of an empty list.
137pub struct Undefined;
138
139/// Trait implemented by empty lists to support list construction.
140pub trait EmptyList {
141    /// The result of pushing the first element onto an empty list.
142    type PushFirst<U: 'static>: List;
143    /// Push the first element onto an empty list.
144    fn push_first<U: 'static>(self, item: U) -> Self::PushFirst<U>;
145
146    /// The canonical empty list type for this family.
147    type RootEmpty: EmptyList;
148    /// Return the canonical empty list.
149    fn root_empty() -> Self::RootEmpty;
150}
151
152/// A blanket implementation for EmptyList.
153impl<T: EmptyList> List for T {
154    type Empty = T::RootEmpty;
155    fn empty() -> Self::Empty {
156        T::root_empty()
157    }
158
159    type Head = Undefined;
160    fn head(&self) -> &Self::Head {
161        unreachable!("EmptyList has no head")
162    }
163
164    type Tail = T; // Satisfy the List trait
165    fn tail(&self) -> &Self::Tail {
166        unreachable!("EmptyList has no tail")
167    }
168
169    type Push<U: 'static> = T::PushFirst<U>;
170    fn push<U>(self, item: U) -> Self::Push<U> {
171        self.push_first(item)
172    }
173
174    const LENGTH: usize = 0;
175
176    type Append<U: List> = U;
177    fn append<U: List>(self, other: U) -> Self::Append<U> {
178        other
179    }
180
181    type ReverseOnto<U: List> = U;
182    fn reverse_onto<U: List>(self, other: U) -> Self::ReverseOnto<U> {
183        other
184    }
185}
186
187/// Indexing for lists using typenum-based indices and ranges.
188pub trait ListIndex<Idx: ?Sized> {
189    /// The output reference type when indexing with `Idx`.
190    type Output;
191    /// Return a reference to the element or sublist selected by `index`.
192    fn index(&self, index: Idx) -> &Self::Output;
193}
194
195/// Type alias for getting element type at index `N`, following [`std::ops::Index`] convention
196/// Element type at index `N` of list `L`.
197pub type Item<L, N> = <L as ListIndex<N>>::Output;
198
199/// Convert to a type-level `List` without consuming `self`.
200pub trait ToList {
201    /// The resulting `List` type using `T` as the empty list type family.
202    type ToList<T: EmptyList>: List;
203    /// Convert to a `List` using `T` as the empty list type family.
204    fn to_list<T: EmptyList>(&self) -> Self::ToList<T>;
205}
206
207/// Convert into a type-level `List`, consuming `self`.
208pub trait IntoList {
209    /// The resulting `List` type using `T` as the empty list type family.
210    type Output<T: EmptyList>: List;
211    /// Convert into a `List` using `T` as the empty list type family.
212    fn into_list<T: EmptyList>(self) -> Self::Output<T>;
213}
214
215impl IntoList for () {
216    type Output<T: EmptyList> = <T as List>::Empty;
217    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
218        T::empty()
219    }
220}
221
222impl<A: 'static> IntoList for (A,) {
223    type Output<T: EmptyList> = <<T as List>::Empty as List>::Push<A>;
224    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
225        ().into_list::<T>().push(self.0)
226    }
227}
228
229impl<A: 'static, B: 'static> IntoList for (A, B) {
230    type Output<T: EmptyList> = <<(B,) as IntoList>::Output<T> as List>::Push<A>;
231    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
232        (self.1,).into_list::<T>().push(self.0)
233    }
234}
235
236impl<A: 'static, B: 'static, C: 'static> IntoList for (A, B, C) {
237    type Output<T: EmptyList> = <<(B, C) as IntoList>::Output<T> as List>::Push<A>;
238    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
239        (self.1, self.2).into_list::<T>().push(self.0)
240    }
241}
242impl<A: 'static, B: 'static, C: 'static, D: 'static> IntoList for (A, B, C, D) {
243    type Output<T: EmptyList> = <<(B, C, D) as IntoList>::Output<T> as List>::Push<A>;
244    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
245        (self.1, self.2, self.3).into_list::<T>().push(self.0)
246    }
247}
248
249impl<A: 'static, B: 'static, C: 'static, D: 'static, E: 'static> IntoList for (A, B, C, D, E) {
250    type Output<T: EmptyList> = <<(B, C, D, E) as IntoList>::Output<T> as List>::Push<A>;
251    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
252        (self.1, self.2, self.3, self.4)
253            .into_list::<T>()
254            .push(self.0)
255    }
256}
257
258impl<A: 'static, B: 'static, C: 'static, D: 'static, E: 'static, F: 'static> IntoList
259    for (A, B, C, D, E, F)
260{
261    type Output<T: EmptyList> = <<(B, C, D, E, F) as IntoList>::Output<T> as List>::Push<A>;
262    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
263        (self.1, self.2, self.3, self.4, self.5)
264            .into_list::<T>()
265            .push(self.0)
266    }
267}
268
269impl<A: 'static, B: 'static, C: 'static, D: 'static, E: 'static, F: 'static, G: 'static> IntoList
270    for (A, B, C, D, E, F, G)
271{
272    type Output<T: EmptyList> = <<(B, C, D, E, F, G) as IntoList>::Output<T> as List>::Push<A>;
273    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
274        (self.1, self.2, self.3, self.4, self.5, self.6)
275            .into_list::<T>()
276            .push(self.0)
277    }
278}
279
280impl<A: 'static, B: 'static, C: 'static, D: 'static, E: 'static, F: 'static, G: 'static, H: 'static>
281    IntoList for (A, B, C, D, E, F, G, H)
282{
283    type Output<T: EmptyList> = <<(B, C, D, E, F, G, H) as IntoList>::Output<T> as List>::Push<A>;
284    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
285        (self.1, self.2, self.3, self.4, self.5, self.6, self.7)
286            .into_list::<T>()
287            .push(self.0)
288    }
289}
290
291impl<
292    A: 'static,
293    B: 'static,
294    C: 'static,
295    D: 'static,
296    E: 'static,
297    F: 'static,
298    G: 'static,
299    H: 'static,
300    I: 'static,
301> IntoList for (A, B, C, D, E, F, G, H, I)
302{
303    type Output<T: EmptyList> =
304        <<(B, C, D, E, F, G, H, I) as IntoList>::Output<T> as List>::Push<A>;
305    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
306        (
307            self.1, self.2, self.3, self.4, self.5, self.6, self.7, self.8,
308        )
309            .into_list::<T>()
310            .push(self.0)
311    }
312}
313
314impl<
315    A: 'static,
316    B: 'static,
317    C: 'static,
318    D: 'static,
319    E: 'static,
320    F: 'static,
321    G: 'static,
322    H: 'static,
323    I: 'static,
324    J: 'static,
325> IntoList for (A, B, C, D, E, F, G, H, I, J)
326{
327    type Output<T: EmptyList> =
328        <<(B, C, D, E, F, G, H, I, J) as IntoList>::Output<T> as List>::Push<A>;
329    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
330        (
331            self.1, self.2, self.3, self.4, self.5, self.6, self.7, self.8, self.9,
332        )
333            .into_list::<T>()
334            .push(self.0)
335    }
336}
337
338impl<
339    A: 'static,
340    B: 'static,
341    C: 'static,
342    D: 'static,
343    E: 'static,
344    F: 'static,
345    G: 'static,
346    H: 'static,
347    I: 'static,
348    J: 'static,
349    K: 'static,
350> IntoList for (A, B, C, D, E, F, G, H, I, J, K)
351{
352    type Output<T: EmptyList> =
353        <<(B, C, D, E, F, G, H, I, J, K) as IntoList>::Output<T> as List>::Push<A>;
354    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
355        (
356            self.1, self.2, self.3, self.4, self.5, self.6, self.7, self.8, self.9, self.10,
357        )
358            .into_list::<T>()
359            .push(self.0)
360    }
361}
362
363impl<
364    A: 'static,
365    B: 'static,
366    C: 'static,
367    D: 'static,
368    E: 'static,
369    F: 'static,
370    G: 'static,
371    H: 'static,
372    I: 'static,
373    J: 'static,
374    K: 'static,
375    L: 'static,
376> IntoList for (A, B, C, D, E, F, G, H, I, J, K, L)
377{
378    type Output<T: EmptyList> =
379        <<(B, C, D, E, F, G, H, I, J, K, L) as IntoList>::Output<T> as List>::Push<A>;
380    fn into_list<T: EmptyList>(self) -> Self::Output<T> {
381        (
382            self.1, self.2, self.3, self.4, self.5, self.6, self.7, self.8, self.9, self.10,
383            self.11,
384        )
385            .into_list::<T>()
386            .push(self.0)
387    }
388}
cel_runtime/list_traits.rs

cel_runtime/
list_traits.rs
