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 Cut = B1;
30    type N = U0;
31    fn niche() -> GenericArray<u8, Self::N> {
32        Default::default()
33    }
34    type Next = Self;
35}
36
37/// [`MaybeNiche`] asserting that `V` is a fake niche.
38pub struct NoNiche<V>(V);
39/// [`MaybeNiche`] asserting that `A` and `B` are fake niches.
40pub struct NoNiche2<A, B>(A, B);
41/// [`MaybeNiche`] asserting that `T` is a true niche.
42pub struct AndNiche<V, T>(V, T);
43/// [`MaybeNiche`] asserting that `T` is a true niche.
44pub struct NicheAnd<T, V>(T, V);
45/// [`MaybeNiche`] asserting that `T` is a true niche.
46pub struct SomeNiche<T>(T);
47
48/// True or fake (placeholder) niche.
49pub trait Niche {
50    /// Whether this is a fake niche (true niches, i.e. those which don't need a tag, don't
51    /// represent a value).
52    type NeedsTag: Bit;
53    /// Whether to stop tail extension of this niche.
54    type Cut: Bit;
55    /// Length in bytes.
56    type N: ArrayLength;
57    /// Get the niche bytes.
58    fn niche() -> GenericArray<u8, Self::N>;
59    /// What we're left with once we occupy [`Self::niche`].
60    type Next;
61}
62
63/// Conditionally implements [`Niche`]. Used to simplify derivations (and make them possible at
64/// all).
65pub trait MaybeNiche {
66    /// Length in bytes.
67    type N: Unsigned;
68    /// Whether to stop tail extension of this niche.
69    type Cut: Bit;
70}
71
72pub trait AsTailOf<U: MaybeNiche>: MaybeNiche {
73    type WithHead: MaybeNiche;
74}
75
76pub trait AsHeadOf<U: MaybeNiche>: MaybeNiche {
77    type WithTail: MaybeNiche;
78}
79
80impl<V: Niche<NeedsTag = B1>> Niche for NoNiche<V> {
81    type NeedsTag = B1;
82    type Cut = V::Cut;
83    type N = V::N;
84    fn niche() -> GenericArray<u8, Self::N> {
85        V::niche()
86    }
87    type Next = Self;
88}
89
90impl<V: Niche<NeedsTag = B1>> MaybeNiche for NoNiche<V> {
91    type N = V::N;
92    type Cut = V::Cut;
93}
94
95impl<U: MaybeNiche<N: Add<V::N, Output: Unsigned>>, V: Niche<NeedsTag = B1>> AsTailOf<U>
96    for NoNiche<V>
97{
98    type WithHead = NoNiche2<U, Self>;
99}
100
101impl<V: Niche<NeedsTag = B1, Cut = Cut>, U: AsTailOf<Self>, Cut: CutNone<Self, U>> AsHeadOf<U>
102    for NoNiche<V>
103{
104    type WithTail = Cut::Cut;
105}
106
107impl<A: Niche<N: Add<B::N, Output: ArrayLength>>, B: Niche> Niche for NoNiche2<A, B> {
108    type NeedsTag = B1;
109    type Cut = B::Cut;
110    type N = Sum<A::N, B::N>;
111    fn niche() -> GenericArray<u8, Self::N> {
112        Concat::concat(A::niche(), B::niche())
113    }
114    type Next = NoNiche<Self>;
115}
116
117impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche> MaybeNiche for NoNiche2<A, B> {
118    type N = Sum<A::N, B::N>;
119    type Cut = B::Cut;
120}
121
122impl<
123    U: MaybeNiche<N: Add<Sum<A::N, B::N>, Output: Unsigned>>,
124    A: MaybeNiche<N: Add<B::N, Output: Unsigned>>,
125    B: MaybeNiche,
126> AsTailOf<U> for NoNiche2<A, B>
127{
128    type WithHead = NoNiche2<U, Self>;
129}
130
131impl<
132    A: MaybeNiche<N: Add<B::N, Output: Unsigned>>,
133    B: MaybeNiche<Cut = Cut>,
134    U: AsTailOf<Self>,
135    Cut: CutNone<Self, U>,
136> AsHeadOf<U> for NoNiche2<A, B>
137{
138    type WithTail = Cut::Cut;
139}
140
141impl<
142    V: Niche<N = N, NeedsTag: NicheAuto>,
143    N: ArrayLength + Add<T::N, Output: ArrayLength>,
144    T: Niche,
145> Niche for AndNiche<V, T>
146{
147    type NeedsTag = T::NeedsTag;
148    type Cut = T::Cut;
149    type N = Sum<N, T::N>;
150    fn niche() -> GenericArray<u8, Self::N> {
151        Concat::concat(V::niche(), T::niche())
152    }
153    type Next = AndNiche<AutoNiche<V>, T::Next>;
154}
155
156impl<V: MaybeNiche<N = N>, N: Unsigned, T: MaybeNiche> MaybeNiche for AndNiche<V, T>
157where
158    N: Add<T::N, Output: Unsigned>,
159{
160    type N = Sum<N, T::N>;
161    type Cut = T::Cut;
162}
163
164impl<
165    U: MaybeNiche<N: Add<Sum<N, T::N>, Output: Unsigned>>,
166    V: MaybeNiche<N = N>,
167    N: Unsigned,
168    T: MaybeNiche,
169> AsTailOf<U> for AndNiche<V, T>
170where
171    N: Add<T::N, Output: Unsigned>,
172{
173    type WithHead = AndNiche<U, Self>;
174}
175
176impl<
177    V: MaybeNiche<N = N>,
178    N: Unsigned,
179    T: MaybeNiche<Cut = Cut>,
180    U: MaybeNiche,
181    Cut: CutSome<Self, U>,
182> AsHeadOf<U> for AndNiche<V, T>
183where
184    N: Add<T::N, Output: Unsigned>,
185    Sum<N, T::N>: Add<U::N, Output: Unsigned>,
186{
187    type WithTail = Cut::Cut;
188}
189
190impl<T: Niche<N: Add<N, Output: ArrayLength>>, V: Niche<N = N, NeedsTag: NicheAuto>, N: ArrayLength>
191    Niche for NicheAnd<T, V>
192{
193    type NeedsTag = T::NeedsTag;
194    type Cut = V::Cut;
195    type N = Sum<T::N, N>;
196    fn niche() -> GenericArray<u8, Self::N> {
197        Concat::concat(T::niche(), V::niche())
198    }
199    type Next = NicheAnd<T::Next, AutoNiche<V>>;
200}
201
202impl<T: MinNiche, V> MinNiche for NicheAnd<T, V> {}
203
204impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned> MaybeNiche
205    for NicheAnd<T, V>
206{
207    type N = Sum<T::N, N>;
208    type Cut = V::Cut;
209}
210
211impl<
212    U: MaybeNiche<N: Add<Sum<T::N, N>, Output: Unsigned>>,
213    T: MaybeNiche<N: Add<N, Output: Unsigned>>,
214    V: MaybeNiche<N = N>,
215    N: Unsigned,
216> AsTailOf<U> for NicheAnd<T, V>
217{
218    type WithHead = AndNiche<U, Self>;
219}
220
221impl<
222    T: MaybeNiche<N: Add<N, Output: Unsigned>>,
223    V: MaybeNiche<N = N, Cut = Cut>,
224    N: Unsigned,
225    U: MaybeNiche,
226    Cut: CutSome<Self, U>,
227> AsHeadOf<U> for NicheAnd<T, V>
228where
229    Sum<T::N, N>: Add<U::N, Output: Unsigned>,
230{
231    type WithTail = Cut::Cut;
232}
233
234impl<T: Niche<NeedsTag = B0>> Niche for SomeNiche<T> {
235    type NeedsTag = T::NeedsTag;
236    type Cut = T::Cut;
237    type N = T::N;
238    fn niche() -> GenericArray<u8, Self::N> {
239        T::niche()
240    }
241    type Next = T::Next;
242}
243
244impl<T: MinNiche> MinNiche for SomeNiche<T> {}
245
246impl<T: Niche<NeedsTag = B0>> MaybeNiche for SomeNiche<T> {
247    type N = T::N;
248    type Cut = T::Cut;
249}
250
251impl<U: MaybeNiche<N: Add<T::N, Output: Unsigned>>, T: Niche<NeedsTag = B0>> AsTailOf<U>
252    for SomeNiche<T>
253{
254    type WithHead = AndNiche<U, Self>;
255}
256
257impl<
258    T: Niche<N: Add<U::N, Output: Unsigned>, NeedsTag = B0, Cut = Cut>,
259    U: MaybeNiche,
260    Cut: CutSome<Self, U>,
261> AsHeadOf<U> for SomeNiche<T>
262{
263    type WithTail = Cut::Cut;
264}
265
266/// Array ([`typenum`]-ish) that *might* be reducible down to a [`Niche`].
267pub trait MnArray {
268    /// Possibly, [`Niche`].
269    type MaybeNiche: MaybeNiche;
270}
271
272impl MnArray for ATerm {
273    type MaybeNiche = NoNiche<ZeroNoNiche<U0>>;
274}
275
276impl<T: MaybeNiche> MnArray for T {
277    type MaybeNiche = T;
278}
279
280impl<T: MnArray<MaybeNiche = U>, U: AsHeadOf<R::MaybeNiche>, R: MnArray> MnArray for TArr<T, R> {
281    type MaybeNiche = U::WithTail;
282}
283
284/// Already occupied/unusable byte representation filled with `0x00` bytes.
285pub struct ZeroNoNiche<N>(N);
286
287impl<N: ArrayLength> Niche for ZeroNoNiche<N> {
288    type NeedsTag = B1;
289    type Cut = B0;
290    type N = N;
291    fn niche() -> GenericArray<u8, Self::N> {
292        GenericArray::default()
293    }
294    type Next = NoNiche<Self>;
295}
296
297/// Niche filled with `0x00` bytes.
298pub struct ZeroNiche<N, Next = NoNiche<ZeroNoNiche<N>>>(N, Next);
299
300impl<N: ArrayLength, Next> Niche for ZeroNiche<N, Next> {
301    type NeedsTag = B0;
302    type Cut = B0;
303    type N = N;
304    fn niche() -> GenericArray<u8, Self::N> {
305        GenericArray::default()
306    }
307    type Next = Next;
308}
309
310impl<N: ArrayLength, Next> MinNiche for ZeroNiche<N, Next> {}
311
312/// Niche filled with `0xFF` bytes.
313pub struct OneNiche<N>(N);
314
315impl<N: ArrayLength> Niche for OneNiche<N> {
316    type NeedsTag = B0;
317    type Cut = B0;
318    type N = N;
319    fn niche() -> GenericArray<u8, Self::N> {
320        GenericArray::default().map(|()| 0xff)
321    }
322    type Next = NoNiche<ZeroNoNiche<N>>;
323}
324
325#[doc(hidden)]
326pub trait NicheOr: MaybeNiche {
327    type NicheOr<U: NicheOr<N = Self::N>>: NicheOr<N = Self::N>;
328    fn index(index: usize) -> usize;
329}
330
331impl<V: Niche<NeedsTag = B1>> NicheOr for NoNiche<V> {
332    type NicheOr<U: NicheOr<N = Self::N>> = U;
333    fn index(index: usize) -> usize {
334        index + 1
335    }
336}
337
338impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche> NicheOr for NoNiche2<A, B> {
339    type NicheOr<U: NicheOr<N = Self::N>> = U;
340    fn index(index: usize) -> usize {
341        index + 1
342    }
343}
344
345impl<V: MaybeNiche<N = N>, N: Unsigned + Add<T::N, Output: Unsigned>, T: MaybeNiche> NicheOr
346    for AndNiche<V, T>
347{
348    type NicheOr<U: NicheOr<N = Self::N>> = Self;
349    fn index(_: usize) -> usize {
350        0
351    }
352}
353
354impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned> NicheOr
355    for NicheAnd<T, V>
356{
357    type NicheOr<U: NicheOr<N = Self::N>> = Self;
358    fn index(_: usize) -> usize {
359        0
360    }
361}
362
363impl<T: Niche<NeedsTag = B0>> NicheOr for SomeNiche<T> {
364    type NicheOr<U: NicheOr<N = Self::N>> = Self;
365    fn index(_: usize) -> usize {
366        0
367    }
368}
369
370pub trait NicheFoldOr {
371    type Or: NicheOr;
372    fn index() -> usize;
373}
374
375impl<T: MnArray<MaybeNiche: NicheOr>> NicheFoldOr for TArr<T, ATerm> {
376    type Or = T::MaybeNiche;
377    fn index() -> usize {
378        0
379    }
380}
381
382impl<T: NicheOr, A: NicheFoldOr<Or: MaybeNiche<N = T::N>>> NicheFoldOr for TArr<T, A> {
383    type Or = T::NicheOr<A::Or>;
384    fn index() -> usize {
385        T::index(A::index())
386    }
387}
388
389#[doc(hidden)]
390pub struct NicheFoldOrArray<T>(T);
391
392impl<T: NicheFoldOr> MnArray for NicheFoldOrArray<T> {
393    type MaybeNiche = T::Or;
394}
395
396pub struct EnumNiche<E, const X: usize>(E);
397
398impl<
399    E: Enum<Kind = K>,
400    K: EnumKind<Tag = T>,
401    T: UsizeTag + ToOutput + Size<Size = N> + MaybeHasNiche<MnArray: MnArray<MaybeNiche = V>>,
402    V: Niche<N = N>,
403    N: ArrayLength,
404    const X: usize,
405> Niche for EnumNiche<E, X>
406{
407    type NeedsTag = V::NeedsTag;
408    type Cut = B0;
409    type N = N;
410    fn niche() -> GenericArray<u8, Self::N> {
411        if V::NeedsTag::BOOL {
412            T::from_usize(X).to_array()
413        } else {
414            V::niche()
415        }
416    }
417    type Next = NoNiche<ZeroNoNiche<N>>;
418}
419
420pub trait NicheAuto: Bit {
421    type Auto<T: Niche<NeedsTag = Self>>: MaybeNiche<N = T::N>;
422}
423
424impl NicheAuto for B0 {
425    type Auto<T: Niche<NeedsTag = Self>> = SomeNiche<T>;
426}
427
428impl NicheAuto for B1 {
429    type Auto<T: Niche<NeedsTag = Self>> = NoNiche<T>;
430}
431
432#[doc(hidden)]
433pub type AutoNiche<T> = <<T as Niche>::NeedsTag as NicheAuto>::Auto<T>;
434
435#[doc(hidden)]
436pub type AutoEnumNiche<E, const X: usize> = AutoNiche<EnumNiche<E, X>>;
437
438#[doc(hidden)]
439pub struct HackNiche<const X: usize>;
440
441impl<const X: usize> Niche for HackNiche<X> {
442    type NeedsTag = B1;
443    type Cut = B0;
444    type N = U0;
445    fn niche() -> GenericArray<u8, Self::N> {
446        GenericArray::default()
447    }
448    type Next = NoNiche<Self>;
449}
450
451/// This niche precedes all non-niche values.
452pub trait MinNiche {}
453
454pub trait CutSome<A, B> {
455    type Cut: MaybeNiche;
456}
457
458impl<A, B> CutSome<A, B> for B0
459where
460    NicheAnd<A, B>: MaybeNiche,
461{
462    type Cut = NicheAnd<A, B>;
463}
464
465impl<A: MaybeNiche, B> CutSome<A, B> for B1 {
466    type Cut = A;
467}
468
469pub trait CutNone<A, B> {
470    type Cut: MaybeNiche;
471}
472
473impl<A: MaybeNiche, B: AsTailOf<A>> CutNone<A, B> for B0 {
474    type Cut = B::WithHead;
475}
476
477impl<A: MaybeNiche, B> CutNone<A, B> for B1 {
478    type Cut = A;
479}
object_rainbow/niche.rs

object_rainbow/
niche.rs
