sorted_hlist/
lib.rs

Help
1#![no_std]
2
3//! A minimal, no-std library for type-level heterogeneous lists (HLists) and
4//! their compile-time intersection.
5//!
6//! You can build an HList via the [`mk_hlist!`] macro, mark lists as
7//! [`SortedHList`] when their element types are in non-decreasing order (via
8//! `typenum::Cmp`), and compute the intersection of two sorted lists using
9//! the [`Intersect`] trait (which under the hood uses
10//! [`IntersectUnchecked`]).
11
12use core::marker::PhantomData;
13use typenum::{Cmp, Equal, Greater, Less};
14
15/// The empty type-level list.
16pub struct HNil;
17
18/// A non-empty type-level list, with head of type `H` and tail `T`.
19///
20/// # Type Parameters
21/// - `H`: the type of the first element.
22/// - `T`: the rest of the list (must itself be an `HList`).
23pub struct HCons<H, T>(PhantomData<(H, T)>);
24
25/// Marker trait for all HLists.
26pub trait HList {}
27
28impl HList for HNil {}
29impl<H, T: HList> HList for HCons<H, T> {}
30
31/// Build a type-level `HList` from a comma-separated list of types.
32///
33/// # Examples
34///
35/// ```rust
36/// # use sorted_hlist::mk_hlist;
37/// type L = mk_hlist!(u8, bool, char);
38/// // Equivalent to HCons<u8, HCons<bool, HCons<char, HNil>>>
39/// ```
40#[macro_export]
41macro_rules! mk_hlist {
42    () => { $crate::HNil };
43    ($head:ty) => { $crate::HCons<$head, $crate::HNil> };
44    ($head:ty, $($tail:ty),+) => {
45        $crate::HCons<$head, $crate::mk_hlist!($($tail),+)>
46    };
47}
48
49/// Marker trait for lists whose element types are in non-decreasing order.
50///
51/// A `SortedHList` must satisfy at compile time that each head `H` compares
52/// leq the next element `HT` via `typenum::Cmp<H, HT>`.
53pub trait SortedHList: HList {}
54
55impl SortedHList for HNil {}
56impl<H> SortedHList for HCons<H, HNil> {}
57impl<H, HT, TT> SortedHList for HCons<H, HCons<HT, TT>>
58where
59    // tail is already sorted...
60    HCons<HT, TT>: SortedHList,
61    // and head leq next element
62    H: Cmp<HT>,
63    <H as Cmp<HT>>::Output: LeOrEq,
64{
65}
66
67/// Internal helper trait indicating a type-level "leq" relationship for `Cmp`.
68pub trait LeOrEq {}
69impl LeOrEq for Equal {}
70impl LeOrEq for Less {}
71
72/// Marker trait for non-empty HLists (i.e. `HCons<_, _>`).
73pub trait NonEmptyHList: HList {}
74
75impl<H, T: HList> NonEmptyHList for HCons<H, T> {}
76
77/// Compute the intersection of two arbitrary HLists, with no sortedness
78/// requirements.  Yields an `HList` of the common elements (in the order of
79/// the left list).
80///
81/// This trait does *not* check that its inputs are sorted; it simply runs the
82/// single-pass intersect algorithm on any `HList`.
83pub trait IntersectUnchecked<Other: HList>: HList {
84    /// The resulting list of elements present in both `Self` and `Other`.
85    type Output: HList;
86}
87
88impl<H, T: HList> IntersectUnchecked<HNil> for HCons<H, T> {
89    type Output = HNil;
90}
91
92impl<List: HList> IntersectUnchecked<List> for HNil {
93    type Output = HNil;
94}
95
96/// Internal dispatch by comparing the heads of two lists.  Chooses one of three
97/// branches (Less, Equal, Greater) and recurses accordingly.
98pub trait IntersectByOrder<Rhs: HList, Ord>: HList {
99    /// The resulting intersected list after ordering dispatch.
100    type Output: HList;
101}
102
103impl<HA, TA: HList, HB, TB: HList> IntersectByOrder<HCons<HB, TB>, Less> for HCons<HA, TA>
104where
105    // HA < HB -> drop HA, keep intersecting TA and RHS
106    TA: IntersectUnchecked<HCons<HB, TB>>,
107{
108    type Output = <TA as IntersectUnchecked<HCons<HB, TB>>>::Output;
109}
110
111impl<HA, TA: HList, HB, TB: HList> IntersectByOrder<HCons<HB, TB>, Greater> for HCons<HA, TA>
112where
113    // HA > HB -> drop HB, intersect (HA::TA) and TB
114    HCons<HA, TA>: IntersectUnchecked<TB>,
115{
116    type Output = <HCons<HA, TA> as IntersectUnchecked<TB>>::Output;
117}
118
119impl<HA, TA: HList, HB, TB: HList> IntersectByOrder<HCons<HB, TB>, Equal> for HCons<HA, TA>
120where
121    // HA == HB -> keep HA, then intersect TA and TB
122    TA: IntersectUnchecked<TB>,
123{
124    type Output = HCons<HA, <TA as IntersectUnchecked<TB>>::Output>;
125}
126
127impl<HA, TA: HList, HB, TB: HList, Ordering> IntersectUnchecked<HCons<HB, TB>> for HCons<HA, TA>
128where
129    // Compare the two heads at compile time, then dispatch
130    HA: Cmp<HB, Output = Ordering>,
131    HCons<HA, TA>: IntersectByOrder<HCons<HB, TB>, Ordering>,
132{
133    type Output = <Self as IntersectByOrder<HCons<HB, TB>, Ordering>>::Output;
134}
135
136// TODO: In an ideal world, `Intersect` would itself be constrained on
137// `SortedHList` and guarantee a `SortedHList` output.  However, binding
138// `Self: SortedHList` directly to the trait causes certain two-element
139// intersections (e.g. `(U2, U3)` and `(U2, U3)`) to overflow the compiler's
140// recursion limit while others (e.g. `(U1, U2, U3)` and `(U2, U3, U4)`) work.
141// Until a robust solution is found, we provide a checked impl only for
142// sorted lists via `Intersect` below.
143
144/// **Checked** intersection of two *sorted* HLists.
145///
146/// This trait *assumes* `Self` and `Other` are `SortedHList`s, and yields
147/// an `HList` of their intersection.  It does *not* re-check sortedness
148/// of the result (to avoid deep recursion in the compiler).
149pub trait Intersect<Other: HList>: HList {
150    /// Intersection of two sorted lists.  Must itself be an `HList`.
151    type Output: HList;
152}
153
154impl<LA, LB> Intersect<LB> for LA
155where
156    // Only sorted lists may use this impl
157    LA: SortedHList + IntersectUnchecked<LB>,
158    LB: SortedHList,
159{
160    type Output = <LA as IntersectUnchecked<LB>>::Output;
161}
sorted_hlist/lib.rs

sorted_hlist/
lib.rs
