object_rainbow/
niche.rs

1use std::ops::Add;
2
3use generic_array::{ArrayLength, GenericArray, functional::FunctionalSequence, sequence::Concat};
4use typenum::{ATerm, B0, B1, Bit, Sum, TArr, U0, Unsigned};
5
6use crate::{
7    Enum, Size, SizeExt, ToOutput,
8    enumkind::{EnumKind, UsizeTag},
9};
10
11/// This *might* contain a valid [`Niche`].
12///
13/// If `Self: Size`, a niche must have the same size.
14///
15/// A niche must satisfy these requirements if it *doesn't need a tag*:
16/// - No valid values are a prefix of it, if `Self` is inline. Otherwise we might misinterpret a
17///   concatenation.
18/// - It's not a prefix of any values. Otherwise we wouldn't be able to parse some valid values.
19pub trait MaybeHasNiche {
20    /// Should implement [`MnArray`]. Not constraint explicitly, because that breaks things.
21    type MnArray;
22}
23
24/// Special [`Niche`] to force use of a tag without any padding.
25pub struct NicheForUnsized;
26
27impl Niche for NicheForUnsized {
28    type NeedsTag = B1;
29    type N = U0;
30    fn niche() -> GenericArray<u8, Self::N> {
31        Default::default()
32    }
33    type Next = Self;
34}
35
36/// [`MaybeNiche`] asserting that `V` is a fake niche.
37pub struct NoNiche<V>(V);
38/// [`MaybeNiche`] asserting that `A` and `B` are fake niches.
39pub struct NoNiche2<A, B>(A, B);
40/// [`MaybeNiche`] asserting that `T` is a true niche.
41pub struct AndNiche<V, T>(V, T);
42/// [`MaybeNiche`] asserting that `T` is a true niche.
43pub struct NicheAnd<T, V>(T, V);
44/// [`MaybeNiche`] asserting that `T` is a true niche.
45pub struct SomeNiche<T>(T);
46
47/// True or fake (placeholder) niche.
48pub trait Niche {
49    /// Whether this is a fake niche (true niches, i.e. those which don't need a tag, don't
50    /// represent a value).
51    type NeedsTag: Bit;
52    /// Length in bytes.
53    type N: ArrayLength;
54    /// Get the niche bytes.
55    fn niche() -> GenericArray<u8, Self::N>;
56    /// What we're left with once we occupy [`Self::niche`].
57    type Next;
58}
59
60/// Conditionally implements [`Niche`]. Used to simplify derivations (and make them possible at
61/// all).
62pub trait MaybeNiche {
63    /// Length in bytes.
64    type N: Unsigned;
65}
66
67pub trait AsTailOf<U: MaybeNiche>: MaybeNiche {
68    type WithHead: MaybeNiche;
69}
70
71pub trait AsHeadOf<U: MaybeNiche>: MaybeNiche {
72    type WithTail: MaybeNiche;
73}
74
75impl<V: Niche<NeedsTag = B1>> Niche for NoNiche<V> {
76    type NeedsTag = B1;
77    type N = V::N;
78    fn niche() -> GenericArray<u8, Self::N> {
79        V::niche()
80    }
81    type Next = Self;
82}
83
84impl<V: Niche<NeedsTag = B1>> MaybeNiche for NoNiche<V> {
85    type N = V::N;
86}
87
88impl<U: MaybeNiche<N: Add<V::N, Output: Unsigned>>, V: Niche<NeedsTag = B1>> AsTailOf<U>
89    for NoNiche<V>
90{
91    type WithHead = NoNiche2<U, Self>;
92}
93
94impl<V: Niche<NeedsTag = B1>, U: AsTailOf<Self>> AsHeadOf<U> for NoNiche<V> {
95    type WithTail = U::WithHead;
96}
97
98impl<A: Niche<N: Add<B::N, Output: ArrayLength>>, B: Niche> Niche for NoNiche2<A, B> {
99    type NeedsTag = B1;
100    type N = Sum<A::N, B::N>;
101    fn niche() -> GenericArray<u8, Self::N> {
102        Concat::concat(A::niche(), B::niche())
103    }
104    type Next = NoNiche<Self>;
105}
106
107impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche> MaybeNiche for NoNiche2<A, B> {
108    type N = Sum<A::N, B::N>;
109}
110
111impl<
112    U: MaybeNiche<N: Add<Sum<A::N, B::N>, Output: Unsigned>>,
113    A: MaybeNiche<N: Add<B::N, Output: Unsigned>>,
114    B: MaybeNiche,
115> AsTailOf<U> for NoNiche2<A, B>
116{
117    type WithHead = NoNiche2<U, Self>;
118}
119
120impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche, U: AsTailOf<Self>> AsHeadOf<U>
121    for NoNiche2<A, B>
122{
123    type WithTail = U::WithHead;
124}
125
126impl<
127    V: Niche<N = N, NeedsTag: NicheAuto>,
128    N: ArrayLength + Add<T::N, Output: ArrayLength>,
129    T: Niche,
130> Niche for AndNiche<V, T>
131{
132    type NeedsTag = T::NeedsTag;
133    type N = Sum<N, T::N>;
134    fn niche() -> GenericArray<u8, Self::N> {
135        Concat::concat(V::niche(), T::niche())
136    }
137    type Next = AndNiche<AutoNiche<V>, T::Next>;
138}
139
140impl<V: MaybeNiche<N = N>, N: Unsigned, T: MaybeNiche> MaybeNiche for AndNiche<V, T>
141where
142    N: Add<T::N, Output: Unsigned>,
143{
144    type N = Sum<N, T::N>;
145}
146
147impl<
148    U: MaybeNiche<N: Add<Sum<N, T::N>, Output: Unsigned>>,
149    V: MaybeNiche<N = N>,
150    N: Unsigned,
151    T: MaybeNiche,
152> AsTailOf<U> for AndNiche<V, T>
153where
154    N: Add<T::N, Output: Unsigned>,
155{
156    type WithHead = AndNiche<U, Self>;
157}
158
159impl<V: MaybeNiche<N = N>, N: Unsigned, T: MaybeNiche, U: MaybeNiche> AsHeadOf<U> for AndNiche<V, T>
160where
161    N: Add<T::N, Output: Unsigned>,
162    Sum<N, T::N>: Add<U::N, Output: Unsigned>,
163{
164    type WithTail = NicheAnd<Self, U>;
165}
166
167impl<T: Niche<N: Add<N, Output: ArrayLength>>, V: Niche<N = N, NeedsTag: NicheAuto>, N: ArrayLength>
168    Niche for NicheAnd<T, V>
169{
170    type NeedsTag = T::NeedsTag;
171    type N = Sum<T::N, N>;
172    fn niche() -> GenericArray<u8, Self::N> {
173        Concat::concat(T::niche(), V::niche())
174    }
175    type Next = NicheAnd<T::Next, AutoNiche<V>>;
176}
177
178impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned> MaybeNiche
179    for NicheAnd<T, V>
180{
181    type N = Sum<T::N, N>;
182}
183
184impl<
185    U: MaybeNiche<N: Add<Sum<T::N, N>, Output: Unsigned>>,
186    T: MaybeNiche<N: Add<N, Output: Unsigned>>,
187    V: MaybeNiche<N = N>,
188    N: Unsigned,
189> AsTailOf<U> for NicheAnd<T, V>
190{
191    type WithHead = AndNiche<U, Self>;
192}
193
194impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned, U: MaybeNiche>
195    AsHeadOf<U> for NicheAnd<T, V>
196where
197    Sum<T::N, N>: Add<U::N, Output: Unsigned>,
198{
199    type WithTail = NicheAnd<Self, U>;
200}
201
202impl<T: Niche<NeedsTag = B0>> Niche for SomeNiche<T> {
203    type NeedsTag = T::NeedsTag;
204    type N = T::N;
205    fn niche() -> GenericArray<u8, Self::N> {
206        T::niche()
207    }
208    type Next = T::Next;
209}
210
211impl<T: Niche<NeedsTag = B0>> MaybeNiche for SomeNiche<T> {
212    type N = T::N;
213}
214
215impl<U: MaybeNiche<N: Add<T::N, Output: Unsigned>>, T: Niche<NeedsTag = B0>> AsTailOf<U>
216    for SomeNiche<T>
217{
218    type WithHead = AndNiche<U, Self>;
219}
220
221impl<T: Niche<N: Add<U::N, Output: Unsigned>, NeedsTag = B0>, U: MaybeNiche> AsHeadOf<U>
222    for SomeNiche<T>
223{
224    type WithTail = NicheAnd<Self, U>;
225}
226
227/// Array ([`typenum`]-ish) that *might* be reducible down to a [`Niche`].
228pub trait MnArray {
229    /// Possibly, [`Niche`].
230    type MaybeNiche: MaybeNiche;
231}
232
233impl MnArray for ATerm {
234    type MaybeNiche = NoNiche<ZeroNoNiche<U0>>;
235}
236
237impl<T: MaybeNiche> MnArray for T {
238    type MaybeNiche = T;
239}
240
241impl<T: AsHeadOf<R::MaybeNiche>, R: MnArray> MnArray for TArr<T, R> {
242    type MaybeNiche = T::WithTail;
243}
244
245/// Already occupied/unusable byte representation filled with `0x00` bytes.
246pub struct ZeroNoNiche<N>(N);
247
248impl<N: ArrayLength> Niche for ZeroNoNiche<N> {
249    type NeedsTag = B1;
250    type N = N;
251    fn niche() -> GenericArray<u8, Self::N> {
252        GenericArray::default()
253    }
254    type Next = NoNiche<Self>;
255}
256
257/// Niche filled with `0x00` bytes.
258pub struct ZeroNiche<N, Next = NoNiche<ZeroNoNiche<N>>>(N, Next);
259
260impl<N: ArrayLength, Next> Niche for ZeroNiche<N, Next> {
261    type NeedsTag = B0;
262    type N = N;
263    fn niche() -> GenericArray<u8, Self::N> {
264        GenericArray::default()
265    }
266    type Next = Next;
267}
268
269/// Niche filled with `0xFF` bytes.
270pub struct OneNiche<N>(N);
271
272impl<N: ArrayLength> Niche for OneNiche<N> {
273    type NeedsTag = B0;
274    type N = N;
275    fn niche() -> GenericArray<u8, Self::N> {
276        GenericArray::default().map(|()| 0xff)
277    }
278    type Next = NoNiche<ZeroNoNiche<N>>;
279}
280
281#[doc(hidden)]
282pub trait NicheOr: MaybeNiche {
283    type NicheOr<U: NicheOr<N = Self::N>>: NicheOr<N = Self::N>;
284    fn index(index: usize) -> usize;
285}
286
287impl<V: Niche<NeedsTag = B1>> NicheOr for NoNiche<V> {
288    type NicheOr<U: NicheOr<N = Self::N>> = U;
289    fn index(index: usize) -> usize {
290        index + 1
291    }
292}
293
294impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche> NicheOr for NoNiche2<A, B> {
295    type NicheOr<U: NicheOr<N = Self::N>> = U;
296    fn index(index: usize) -> usize {
297        index + 1
298    }
299}
300
301impl<V: MaybeNiche<N = N>, N: Unsigned + Add<T::N, Output: Unsigned>, T: MaybeNiche> NicheOr
302    for AndNiche<V, T>
303{
304    type NicheOr<U: NicheOr<N = Self::N>> = Self;
305    fn index(_: usize) -> usize {
306        0
307    }
308}
309
310impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned> NicheOr
311    for NicheAnd<T, V>
312{
313    type NicheOr<U: NicheOr<N = Self::N>> = Self;
314    fn index(_: usize) -> usize {
315        0
316    }
317}
318
319impl<T: Niche<NeedsTag = B0>> NicheOr for SomeNiche<T> {
320    type NicheOr<U: NicheOr<N = Self::N>> = Self;
321    fn index(_: usize) -> usize {
322        0
323    }
324}
325
326pub trait NicheFoldOr {
327    type Or: NicheOr;
328    fn index() -> usize;
329}
330
331impl<T: MnArray<MaybeNiche: NicheOr>> NicheFoldOr for TArr<T, ATerm> {
332    type Or = T::MaybeNiche;
333    fn index() -> usize {
334        0
335    }
336}
337
338impl<T: NicheOr, A: NicheFoldOr<Or: MaybeNiche<N = T::N>>> NicheFoldOr for TArr<T, A> {
339    type Or = T::NicheOr<A::Or>;
340    fn index() -> usize {
341        T::index(A::index())
342    }
343}
344
345#[doc(hidden)]
346pub struct NicheFoldOrArray<T>(T);
347
348impl<T: NicheFoldOr> MnArray for NicheFoldOrArray<T> {
349    type MaybeNiche = T::Or;
350}
351
352pub struct EnumNiche<E, const X: usize>(E);
353
354impl<
355    E: Enum<Kind = K>,
356    K: EnumKind<Tag = T>,
357    T: UsizeTag + ToOutput + Size<Size = N> + MaybeHasNiche<MnArray: MnArray<MaybeNiche = V>>,
358    V: Niche<N = N>,
359    N: ArrayLength,
360    const X: usize,
361> Niche for EnumNiche<E, X>
362{
363    type NeedsTag = V::NeedsTag;
364    type N = N;
365    fn niche() -> GenericArray<u8, Self::N> {
366        if V::NeedsTag::BOOL {
367            T::from_usize(X).to_array()
368        } else {
369            V::niche()
370        }
371    }
372    type Next = NoNiche<ZeroNoNiche<N>>;
373}
374
375pub trait NicheAuto: Bit {
376    type Auto<T: Niche<NeedsTag = Self>>: MaybeNiche<N = T::N>;
377}
378
379impl NicheAuto for B0 {
380    type Auto<T: Niche<NeedsTag = Self>> = SomeNiche<T>;
381}
382
383impl NicheAuto for B1 {
384    type Auto<T: Niche<NeedsTag = Self>> = NoNiche<T>;
385}
386
387#[doc(hidden)]
388pub type AutoNiche<T> = <<T as Niche>::NeedsTag as NicheAuto>::Auto<T>;
389
390#[doc(hidden)]
391pub type AutoEnumNiche<E, const X: usize> = AutoNiche<EnumNiche<E, X>>;
392
393#[doc(hidden)]
394pub struct HackNiche<const X: usize>;
395
396impl<const X: usize> Niche for HackNiche<X> {
397    type NeedsTag = B1;
398    type N = U0;
399    fn niche() -> GenericArray<u8, Self::N> {
400        GenericArray::default()
401    }
402    type Next = NoNiche<Self>;
403}
object_rainbow/niche.rs

object_rainbow/
niche.rs
