strata/
lib.rs

1use crate::Position::*;
2use std::{
3    cmp::{max, min},
4    u32, u64,
5};
6
7#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
8pub enum Position {
9    NegativeInfinity,
10    Valid(u64),
11    PositiveInfinity,
12}
13
14impl From<u64> for Position {
15    fn from(v: u64) -> Position {
16        Valid(v)
17    }
18}
19
20trait Epsilon {
21    fn increment(self) -> Self;
22    fn decrement(self) -> Self;
23}
24
25impl Epsilon for Position {
26    fn increment(self) -> Self {
27        match self {
28            NegativeInfinity | PositiveInfinity => self,
29            Valid(x) if x == u64::MAX => PositiveInfinity,
30            Valid(x) => Valid(x + 1),
31        }
32    }
33
34    fn decrement(self) -> Self {
35        match self {
36            NegativeInfinity | PositiveInfinity => self,
37            Valid(x) if x == u64::MIN => NegativeInfinity,
38            Valid(x) => Valid(x - 1),
39        }
40    }
41}
42
43pub type ValidExtent = (u64, u64);
44
45#[derive(Debug, Copy, Clone, PartialEq)]
46pub struct Extent(pub Position, pub Position);
47const START_EXTENT: Extent = Extent(NegativeInfinity, NegativeInfinity);
48const END_EXTENT: Extent = Extent(PositiveInfinity, PositiveInfinity);
49
50impl Extent {
51    fn unwrap(self) -> ValidExtent {
52        match self {
53            Extent(Valid(a), Valid(b)) => (a, b),
54            _ => panic!("Extent was not valid: {:?}", self),
55        }
56    }
57}
58
59impl PartialEq<ValidExtent> for Extent {
60    fn eq(&self, other: &ValidExtent) -> bool {
61        match *self {
62            Extent(Valid(a), Valid(b)) => (a, b) == *other,
63            _ => false,
64        }
65    }
66}
67
68impl From<ValidExtent> for Extent {
69    fn from(v: ValidExtent) -> Extent {
70        Extent(v.0.into(), v.1.into())
71    }
72}
73
74/// The basic query algebra from the [Clarke *et al.* paper][paper]
75///
76/// # Iterators
77///
78/// Iterators are provided that return the entire result set in the
79/// positive direction (tau, rho) and the negative direction
80/// (tau-prime, rho-prime). Both forward iterators and both backwards
81/// iterators return the same extents, and the forwards and backwards
82/// iterators return the same extents in reverse order from each
83/// other. All 4 iterators are provided for completeness.
84///
85/// # tau-prime and rho-prime
86///
87/// The paper does not give a concrete example of how to construct the
88/// `*_prime` functions, simply stating
89///
90/// > The access functions τ′ and ρ′ are the converses of τ and ρ.
91///
92/// Through trial and error, I've determined that there are 4 concrete
93/// steps to transform between prime and non-prime implementations:
94///
95/// 1. Swap usages of {tau,rho} with {tau-prime,rho-prime}
96/// 2. Swap the sign of epsilon
97/// 3. Swap the usages of p and q
98/// 4. Swap comparison operators
99///
100/// [paper]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.8436&rank=1
101#[allow(unused_variables)]
102pub trait Algebra {
103    /// The first extent starting at or after the position k.
104    fn tau(&self, k: Position) -> Extent;
105
106    /// The last extent ending at or before the position k.
107    ///
108    /// This is akin to running `tau` from the other end of the number
109    /// line. We are interested in the *first* number we arrive at
110    /// (the end of the extent). We take the *first* extent that
111    /// passes the criteria (the last extent in order).
112    fn tau_prime(&self, k: Position) -> Extent;
113
114    /// The first extent ending at or after the position k.
115    fn rho(&self, k: Position) -> Extent;
116
117    /// The last extent starting at or before the position k.
118    ///
119    /// This is akin to running `rho` from the other end of the number
120    /// line. We are interested in the *second* number we arrive at
121    /// (the start of the extent). We take the *first* extent that
122    /// passes the criteria (the last extent in order).
123    fn rho_prime(&self, k: Position) -> Extent;
124
125    /// Find all extents in a forward direction using the tau primitive
126    fn iter_tau(self) -> IterTau<Self>
127    where
128        Self: Sized,
129    {
130        IterTau {
131            list: self,
132            k: NegativeInfinity,
133        }
134    }
135
136    /// Find all extents in a forward direction using the rho primitive
137    fn iter_rho(self) -> IterRho<Self>
138    where
139        Self: Sized,
140    {
141        IterRho {
142            list: self,
143            k: NegativeInfinity,
144        }
145    }
146
147    /// Find all extents in a backward direction using the tau-prime primitive
148    fn iter_tau_prime(self) -> IterTauPrime<Self>
149    where
150        Self: Sized,
151    {
152        IterTauPrime {
153            list: self,
154            k: PositiveInfinity,
155        }
156    }
157
158    /// Find all extents in a backward direction using the rho-prime primitive
159    fn iter_rho_prime(self) -> IterRhoPrime<Self>
160    where
161        Self: Sized,
162    {
163        IterRhoPrime {
164            list: self,
165            k: PositiveInfinity,
166        }
167    }
168}
169
170impl<'a, A: ?Sized> Algebra for Box<A>
171where
172    A: Algebra,
173{
174    fn tau(&self, k: Position) -> Extent {
175        (**self).tau(k)
176    }
177    fn tau_prime(&self, k: Position) -> Extent {
178        (**self).tau_prime(k)
179    }
180    fn rho(&self, k: Position) -> Extent {
181        (**self).rho(k)
182    }
183    fn rho_prime(&self, k: Position) -> Extent {
184        (**self).rho_prime(k)
185    }
186}
187
188impl<'a, A: ?Sized> Algebra for &'a A
189where
190    A: Algebra,
191{
192    fn tau(&self, k: Position) -> Extent {
193        (**self).tau(k)
194    }
195    fn tau_prime(&self, k: Position) -> Extent {
196        (**self).tau_prime(k)
197    }
198    fn rho(&self, k: Position) -> Extent {
199        (**self).rho(k)
200    }
201    fn rho_prime(&self, k: Position) -> Extent {
202        (**self).rho_prime(k)
203    }
204}
205
206/// Iterates over the extent list in the forward direction using the
207/// tau primitive
208#[derive(Debug, Copy, Clone)]
209pub struct IterTau<T> {
210    list: T,
211    k: Position,
212}
213
214impl<T> Iterator for IterTau<T>
215where
216    T: Algebra,
217{
218    type Item = ValidExtent;
219
220    fn next(&mut self) -> Option<Self::Item> {
221        let Extent(p, q) = self.list.tau(self.k);
222        if p == PositiveInfinity {
223            return None;
224        }
225
226        debug_assert!(self.k < p.increment());
227        self.k = p.increment();
228        Some(Extent(p, q).unwrap())
229    }
230}
231
232/// Iterates over the extent list in the forward direction using the
233/// rho primitive
234#[derive(Debug, Copy, Clone)]
235pub struct IterRho<T> {
236    list: T,
237    k: Position,
238}
239
240impl<T> Iterator for IterRho<T>
241where
242    T: Algebra,
243{
244    type Item = ValidExtent;
245
246    fn next(&mut self) -> Option<Self::Item> {
247        let Extent(p, q) = self.list.rho(self.k);
248        if q == PositiveInfinity {
249            return None;
250        }
251
252        debug_assert!(self.k < q.increment());
253        self.k = q.increment();
254        Some(Extent(p, q).unwrap())
255    }
256}
257
258/// Iterates over the extent list in the backward direction using the
259/// tau-prime primitive
260#[derive(Debug, Copy, Clone)]
261pub struct IterTauPrime<T> {
262    list: T,
263    k: Position,
264}
265
266impl<T> Iterator for IterTauPrime<T>
267where
268    T: Algebra,
269{
270    type Item = ValidExtent;
271
272    fn next(&mut self) -> Option<Self::Item> {
273        let Extent(p, q) = self.list.tau_prime(self.k);
274        if q == NegativeInfinity {
275            return None;
276        }
277
278        debug_assert!(self.k > q.decrement());
279        self.k = q.decrement();
280        Some(Extent(p, q).unwrap())
281    }
282}
283
284/// Iterates over the extent list in the backward direction using the
285/// rho-prime primitive
286#[derive(Debug, Copy, Clone)]
287pub struct IterRhoPrime<T> {
288    list: T,
289    k: Position,
290}
291
292impl<T> Iterator for IterRhoPrime<T>
293where
294    T: Algebra,
295{
296    type Item = ValidExtent;
297
298    fn next(&mut self) -> Option<Self::Item> {
299        let Extent(p, q) = self.list.rho_prime(self.k);
300        if p == NegativeInfinity {
301            return None;
302        }
303
304        debug_assert!(self.k > p.decrement());
305        self.k = p.decrement();
306        Some(Extent(p, q).unwrap())
307    }
308}
309
310macro_rules! check_forwards {
311    ($k:expr) => {
312        if $k == PositiveInfinity {
313            return END_EXTENT;
314        }
315    };
316}
317
318macro_rules! check_backwards {
319    ($k:expr) => {
320        if $k == NegativeInfinity {
321            return START_EXTENT;
322        }
323    };
324}
325
326macro_rules! check_and_unwrap_forwards {
327    ($k:expr) => {
328        match $k {
329            NegativeInfinity => u64::MIN,
330            Valid(x) => x,
331            PositiveInfinity => return END_EXTENT,
332        }
333    };
334}
335
336macro_rules! check_and_unwrap_backwards {
337    ($k:expr) => {
338        match $k {
339            NegativeInfinity => return START_EXTENT,
340            Valid(x) => x,
341            PositiveInfinity => u64::MAX,
342        }
343    };
344}
345
346// TODO: Investigate `get_unchecked` as we know the idx is valid.
347impl Algebra for [ValidExtent] {
348    fn tau(&self, k: Position) -> Extent {
349        let k = check_and_unwrap_forwards!(k);
350        match self.binary_search_by(|ex| ex.0.cmp(&k)) {
351            Ok(idx) => self[idx].into(),
352            Err(idx) if idx != self.len() => self[idx].into(),
353            Err(..) => END_EXTENT,
354        }
355    }
356
357    // TODO: test
358    fn tau_prime(&self, k: Position) -> Extent {
359        let k = check_and_unwrap_backwards!(k);
360        match self.binary_search_by(|ex| ex.1.cmp(&k)) {
361            Ok(idx) => self[idx].into(),
362            Err(idx) if idx != 0 => self[idx - 1].into(),
363            Err(..) => START_EXTENT,
364        }
365    }
366
367    fn rho(&self, k: Position) -> Extent {
368        let k = check_and_unwrap_forwards!(k);
369        match self.binary_search_by(|ex| ex.1.cmp(&k)) {
370            Ok(idx) => self[idx].into(),
371            Err(idx) if idx != self.len() => self[idx].into(),
372            Err(..) => END_EXTENT,
373        }
374    }
375
376    // TODO: test
377    fn rho_prime(&self, k: Position) -> Extent {
378        let k = check_and_unwrap_backwards!(k);
379        match self.binary_search_by(|ex| ex.0.cmp(&k)) {
380            Ok(idx) => self[idx].into(),
381            Err(idx) if idx != 0 => self[idx - 1].into(),
382            Err(..) => START_EXTENT,
383        }
384    }
385}
386
387/// Finds no extents
388pub struct Empty;
389
390impl Algebra for Empty {
391    fn tau(&self, _: Position) -> Extent {
392        END_EXTENT
393    }
394    fn tau_prime(&self, _: Position) -> Extent {
395        START_EXTENT
396    }
397    fn rho(&self, _: Position) -> Extent {
398        END_EXTENT
399    }
400    fn rho_prime(&self, _: Position) -> Extent {
401        START_EXTENT
402    }
403}
404
405const DOC_MIN: u32 = u32::MIN;
406const DOC_MAX: u32 = u32::MAX;
407const DOC_OFFSET_MIN: u32 = u32::MIN;
408const DOC_OFFSET_MAX: u32 = u32::MAX;
409
410fn k_to_doc_and_offset(k: u64) -> (u32, u32) {
411    ((k >> 32) as u32, k as u32)
412}
413
414fn doc_and_offset_to_k(doc: u32, offset: u32) -> u64 {
415    (u64::from(doc)) << 32 | u64::from(offset)
416}
417
418#[derive(Debug, Copy, Clone)]
419pub struct Documents {
420    count: u32,
421}
422
423impl Documents {
424    pub fn new(count: u32) -> Documents {
425        Documents { count }
426    }
427
428    fn doc_index_to_extent(self, doc: u32) -> Extent {
429        let start = doc_and_offset_to_k(doc, 0);
430        let end = doc_and_offset_to_k(doc, DOC_OFFSET_MAX);
431        (start, end).into()
432    }
433
434    fn doc_index_to_extent_forwards(self, doc: u32) -> Extent {
435        if doc >= self.count {
436            return END_EXTENT;
437        }
438        self.doc_index_to_extent(doc)
439    }
440
441    // Clamps to the last document
442    fn doc_index_to_extent_backwards(self, doc: u32) -> Extent {
443        if self.count == 0 {
444            return START_EXTENT;
445        }
446        self.doc_index_to_extent(min(doc, self.count - 1))
447    }
448}
449
450impl Algebra for Documents {
451    fn tau(&self, k: Position) -> Extent {
452        let k = check_and_unwrap_forwards!(k);
453
454        match k_to_doc_and_offset(k) {
455            (doc, DOC_OFFSET_MIN) => self.doc_index_to_extent_forwards(doc),
456            (DOC_MAX, _) => END_EXTENT,
457            (doc, _) => self.doc_index_to_extent_forwards(doc + 1),
458        }
459    }
460
461    fn tau_prime(&self, k: Position) -> Extent {
462        let k = check_and_unwrap_backwards!(k);
463
464        match k_to_doc_and_offset(k) {
465            (doc, DOC_OFFSET_MAX) => self.doc_index_to_extent_backwards(doc),
466            (DOC_MIN, _) => START_EXTENT,
467            (doc, _) => self.doc_index_to_extent_backwards(doc - 1),
468        }
469    }
470
471    fn rho(&self, k: Position) -> Extent {
472        let k = check_and_unwrap_forwards!(k);
473
474        match k_to_doc_and_offset(k) {
475            (doc, _) => self.doc_index_to_extent_forwards(doc),
476        }
477    }
478
479    fn rho_prime(&self, k: Position) -> Extent {
480        let k = check_and_unwrap_backwards!(k);
481
482        match k_to_doc_and_offset(k) {
483            (doc, _) => self.doc_index_to_extent_backwards(doc),
484        }
485    }
486}
487
488/// Finds extents from the first list that are contained in extents
489/// from the second list.
490///
491/// Akin to finding needles in haystacks.
492#[derive(Debug, Copy, Clone)]
493pub struct ContainedIn<A, B>
494where
495    A: Algebra,
496    B: Algebra,
497{
498    a: A,
499    b: B,
500}
501
502impl<A, B> ContainedIn<A, B>
503where
504    A: Algebra,
505    B: Algebra,
506{
507    pub fn new(a: A, b: B) -> Self {
508        ContainedIn { a, b }
509    }
510}
511
512impl<A, B> Algebra for ContainedIn<A, B>
513where
514    A: Algebra,
515    B: Algebra,
516{
517    fn tau(&self, k: Position) -> Extent {
518        let mut k = k;
519
520        loop {
521            check_forwards!(k);
522
523            let Extent(p0, q0) = self.a.tau(k);
524            let Extent(p1, _) = self.b.rho(q0);
525
526            if p1 <= p0 {
527                return Extent(p0, q0);
528            } else {
529                // iteration instead of recursion
530                k = p1;
531            }
532        }
533    }
534
535    fn tau_prime(&self, k: Position) -> Extent {
536        let mut k = k;
537
538        loop {
539            check_backwards!(k);
540
541            let Extent(p0, q0) = self.a.tau_prime(k);
542            let Extent(_, q1) = self.b.rho_prime(p0);
543
544            if q1 >= q0 {
545                return Extent(p0, q0);
546            } else {
547                // iteration instead of recursion
548                k = q1;
549            }
550        }
551    }
552
553    fn rho(&self, k: Position) -> Extent {
554        check_forwards!(k);
555
556        let Extent(p, _) = self.a.rho(k);
557        self.tau(p)
558    }
559
560    fn rho_prime(&self, k: Position) -> Extent {
561        check_backwards!(k);
562
563        let Extent(_, q) = self.a.rho_prime(k);
564        self.tau_prime(q)
565    }
566}
567
568/// Finds extents from the first list that contain extents from the
569/// second list.
570///
571/// Akin to finding haystacks with needles in them.
572#[derive(Debug, Copy, Clone)]
573pub struct Containing<A, B>
574where
575    A: Algebra,
576    B: Algebra,
577{
578    a: A,
579    b: B,
580}
581
582impl<A, B> Containing<A, B>
583where
584    A: Algebra,
585    B: Algebra,
586{
587    pub fn new(a: A, b: B) -> Self {
588        Containing { a, b }
589    }
590}
591
592impl<A, B> Algebra for Containing<A, B>
593where
594    A: Algebra,
595    B: Algebra,
596{
597    fn tau(&self, k: Position) -> Extent {
598        check_forwards!(k);
599        let Extent(_, q) = self.a.tau(k);
600        self.rho(q)
601    }
602
603    fn tau_prime(&self, k: Position) -> Extent {
604        check_backwards!(k);
605        let Extent(p, _) = self.a.tau_prime(k);
606        self.rho_prime(p)
607    }
608
609    fn rho(&self, k: Position) -> Extent {
610        let mut k = k;
611
612        loop {
613            check_forwards!(k);
614
615            let Extent(p0, q0) = self.a.rho(k);
616            let Extent(_, q1) = self.b.tau(p0);
617
618            if q1 <= q0 {
619                return Extent(p0, q0);
620            } else {
621                // iteration instead of recursion
622                k = q1;
623            }
624        }
625    }
626
627    fn rho_prime(&self, k: Position) -> Extent {
628        let mut k = k;
629
630        loop {
631            check_backwards!(k);
632
633            let Extent(p0, q0) = self.a.rho_prime(k);
634            let Extent(p1, _) = self.b.tau_prime(q0);
635
636            if p1 >= p0 {
637                return Extent(p0, q0);
638            } else {
639                // iteration instead of recursion
640                k = p1;
641            }
642        }
643    }
644}
645
646#[derive(Debug, Copy, Clone)]
647pub struct NotContainedIn<A, B>
648where
649    A: Algebra,
650    B: Algebra,
651{
652    a: A,
653    b: B,
654}
655
656impl<A, B> NotContainedIn<A, B>
657where
658    A: Algebra,
659    B: Algebra,
660{
661    pub fn new(a: A, b: B) -> Self {
662        NotContainedIn { a, b }
663    }
664}
665
666impl<A, B> Algebra for NotContainedIn<A, B>
667where
668    A: Algebra,
669    B: Algebra,
670{
671    fn tau(&self, k: Position) -> Extent {
672        check_forwards!(k);
673        let Extent(p0, q0) = self.a.tau(k);
674        let Extent(p1, q1) = self.b.rho(q0);
675
676        if p1 > p0 {
677            Extent(p0, q0)
678        } else {
679            // TODO: prevent recursion?
680            self.rho(q1.increment())
681        }
682    }
683
684    fn tau_prime(&self, k: Position) -> Extent {
685        check_backwards!(k);
686        let Extent(p0, q0) = self.a.tau_prime(k);
687        let Extent(p1, q1) = self.b.rho_prime(p0);
688
689        if q1 < q0 {
690            Extent(p0, q0)
691        } else {
692            // TODO: prevent recursion?
693            self.rho_prime(p1.decrement())
694        }
695    }
696
697    fn rho(&self, k: Position) -> Extent {
698        check_forwards!(k);
699
700        let Extent(p, _) = self.a.rho(k);
701        self.tau(p)
702    }
703
704    fn rho_prime(&self, k: Position) -> Extent {
705        check_backwards!(k);
706
707        let Extent(_, q) = self.a.rho_prime(k);
708        self.tau_prime(q)
709    }
710}
711
712#[derive(Debug, Copy, Clone)]
713pub struct NotContaining<A, B>
714where
715    A: Algebra,
716    B: Algebra,
717{
718    a: A,
719    b: B,
720}
721
722impl<A, B> NotContaining<A, B>
723where
724    A: Algebra,
725    B: Algebra,
726{
727    pub fn new(a: A, b: B) -> Self {
728        NotContaining { a, b }
729    }
730}
731
732impl<A, B> Algebra for NotContaining<A, B>
733where
734    A: Algebra,
735    B: Algebra,
736{
737    fn tau(&self, k: Position) -> Extent {
738        check_forwards!(k);
739
740        let Extent(_, q) = self.a.tau(k);
741        self.rho(q)
742    }
743
744    fn tau_prime(&self, k: Position) -> Extent {
745        check_backwards!(k);
746
747        let Extent(p, _) = self.a.tau_prime(k);
748        self.rho_prime(p)
749    }
750
751    fn rho(&self, k: Position) -> Extent {
752        check_forwards!(k);
753
754        let Extent(p0, q0) = self.a.rho(k);
755        let Extent(p1, q1) = self.b.tau(p0);
756
757        if q1 > q0 {
758            Extent(p0, q0)
759        } else {
760            // TODO: prevent recursion?
761            self.tau(p1.increment())
762        }
763    }
764
765    fn rho_prime(&self, k: Position) -> Extent {
766        check_backwards!(k);
767
768        let Extent(p0, q0) = self.a.rho_prime(k);
769        let Extent(p1, q1) = self.b.tau_prime(q0);
770
771        if p1 < p0 {
772            Extent(p0, q0)
773        } else {
774            // TODO: prevent recursion?
775            self.tau_prime(q1.decrement())
776        }
777    }
778}
779
780/// Creates extents that extents from both lists would be a subextent
781/// of.
782#[derive(Debug, Copy, Clone)]
783pub struct BothOf<A, B>
784where
785    A: Algebra,
786    B: Algebra,
787{
788    a: A,
789    b: B,
790}
791
792impl<A, B> BothOf<A, B>
793where
794    A: Algebra,
795    B: Algebra,
796{
797    pub fn new(a: A, b: B) -> Self {
798        BothOf { a, b }
799    }
800}
801
802impl<A, B> Algebra for BothOf<A, B>
803where
804    A: Algebra,
805    B: Algebra,
806{
807    fn tau(&self, k: Position) -> Extent {
808        check_forwards!(k);
809
810        // Find the farthest end of the next extents
811        let Extent(_, q0) = self.a.tau(k);
812        let Extent(_, q1) = self.b.tau(k);
813        let max_q01 = max(q0, q1);
814
815        // This line does not match the paper
816        check_forwards!(max_q01);
817
818        // Find the extents prior to that point
819        let Extent(p2, q2) = self.a.tau_prime(max_q01);
820        let Extent(p3, q3) = self.b.tau_prime(max_q01);
821
822        // Create a new extent that encompasses both preceeding extents
823        Extent(min(p2, p3), max(q2, q3))
824    }
825
826    fn tau_prime(&self, k: Position) -> Extent {
827        check_backwards!(k);
828
829        let Extent(p0, _) = self.a.tau_prime(k);
830        let Extent(p1, _) = self.b.tau_prime(k);
831        let min_p01 = min(p0, p1);
832
833        check_backwards!(min_p01);
834
835        let Extent(p2, q2) = self.a.tau(min_p01);
836        let Extent(p3, q3) = self.b.tau(min_p01);
837
838        Extent(min(p2, p3), max(q2, q3))
839    }
840
841    fn rho(&self, k: Position) -> Extent {
842        check_forwards!(k);
843
844        let Extent(p, _) = self.tau_prime(k.decrement());
845        self.tau(p.increment())
846    }
847
848    fn rho_prime(&self, k: Position) -> Extent {
849        check_backwards!(k);
850
851        let Extent(_, q) = self.tau(k.increment());
852        self.tau_prime(q.decrement())
853    }
854}
855
856/// Finds extents that an extent from either list would be a subextent
857/// of.
858///
859/// # Errors in the paper
860///
861/// Using the implementation in the paper, `OneOf::tau` and
862/// `OneOf::rho` do *not* produce the same list. As an example:
863///
864/// ```text
865///          k
866/// |--*==*--|--|
867/// *==|==|==|==*
868/// 1  2  3  4  5
869/// ```
870///
871/// `tau` would be correct for k=[0,5], but `rho` fails at k=[4,5],
872/// producing (1,5).
873///
874/// To work around this, we work backward using `tau_prime` and then
875/// forward again with `tau`, until we find a valid extent.
876#[derive(Debug, Copy, Clone)]
877pub struct OneOf<A, B>
878where
879    A: Algebra,
880    B: Algebra,
881{
882    a: A,
883    b: B,
884}
885
886impl<A, B> OneOf<A, B>
887where
888    A: Algebra,
889    B: Algebra,
890{
891    pub fn new(a: A, b: B) -> Self {
892        OneOf { a, b }
893    }
894}
895
896impl<A, B> Algebra for OneOf<A, B>
897where
898    A: Algebra,
899    B: Algebra,
900{
901    fn tau(&self, k: Position) -> Extent {
902        check_forwards!(k);
903
904        // Find the extents after the point
905        let Extent(p0, q0) = self.a.tau(k);
906        let Extent(p1, q1) = self.b.tau(k);
907
908        // TODO: use Ordering
909
910        // Take the one that ends first, using the smaller extent in
911        // case of ties
912        if q0 < q1 {
913            Extent(p0, q0)
914        } else if q0 > q1 {
915            Extent(p1, q1)
916        } else {
917            Extent(max(p0, p1), q0)
918        }
919    }
920
921    fn tau_prime(&self, k: Position) -> Extent {
922        check_backwards!(k);
923
924        // Find the extents after the point
925        let Extent(p0, q0) = self.a.tau_prime(k);
926        let Extent(p1, q1) = self.b.tau_prime(k);
927
928        // TODO: use Ordering
929
930        // Take the one that ends first, using the smaller extent in
931        // case of ties
932        if p0 > p1 {
933            Extent(p0, q0)
934        } else if p0 < p1 {
935            Extent(p1, q1)
936        } else {
937            Extent(p0, min(q0, q1))
938        }
939    }
940
941    fn rho(&self, k: Position) -> Extent {
942        check_forwards!(k);
943
944        let Extent(p, q) = self.tau_prime(k);
945        if q.increment() > k {
946            return Extent(p, q);
947        }
948
949        loop {
950            let Extent(p, q) = self.tau(p.increment());
951            if q >= k {
952                return Extent(p, q);
953            }
954        }
955    }
956
957    fn rho_prime(&self, k: Position) -> Extent {
958        check_backwards!(k);
959
960        let Extent(p, q) = self.tau(k);
961        if p.decrement() < k {
962            return Extent(p, q);
963        }
964
965        loop {
966            let Extent(p, q) = self.tau_prime(q.decrement());
967            if p <= k {
968                return Extent(p, q);
969            }
970        }
971    }
972}
973
974/// Creates extents that start at an extent from the first argument
975/// and end at an extent from the second argument.
976///
977/// # tau-prime and rho-prime
978///
979/// In addition to the generic rules for constructing the prime
980/// variants, `FollowedBy` requires that the A and B children be
981/// swapped. This ensures that the ordering constraints are adhered,
982/// otherwise we would find extents from B followed by extents from A.
983///
984#[derive(Debug, Copy, Clone)]
985pub struct FollowedBy<A, B>
986where
987    A: Algebra,
988    B: Algebra,
989{
990    a: A,
991    b: B,
992}
993
994impl<A, B> FollowedBy<A, B>
995where
996    A: Algebra,
997    B: Algebra,
998{
999    pub fn new(a: A, b: B) -> Self {
1000        FollowedBy { a, b }
1001    }
1002}
1003
1004impl<A, B> Algebra for FollowedBy<A, B>
1005where
1006    A: Algebra,
1007    B: Algebra,
1008{
1009    fn tau(&self, k: Position) -> Extent {
1010        check_forwards!(k);
1011
1012        // Find the first extent in A at or after the point
1013        let Extent(_, q0) = self.a.tau(k);
1014
1015        // Find the first extent in B at or after the first extent
1016        let Extent(p1, q1) = self.b.tau(q0.increment());
1017        check_forwards!(q1);
1018
1019        // Find the closest extent in A that is before the extent from B
1020        let Extent(p2, _) = self.a.tau_prime(p1.decrement());
1021        Extent(p2, q1)
1022    }
1023
1024    fn tau_prime(&self, k: Position) -> Extent {
1025        check_backwards!(k);
1026
1027        let Extent(p0, _) = self.b.tau_prime(k);
1028
1029        let Extent(p1, q1) = self.a.tau_prime(p0.decrement());
1030        check_backwards!(p1);
1031
1032        let Extent(_, q2) = self.b.tau(q1.increment());
1033        Extent(p1, q2)
1034    }
1035
1036    fn rho(&self, k: Position) -> Extent {
1037        check_forwards!(k);
1038
1039        let Extent(p, _) = self.tau_prime(k.decrement());
1040        self.tau(p.increment())
1041    }
1042
1043    fn rho_prime(&self, k: Position) -> Extent {
1044        check_backwards!(k);
1045
1046        let Extent(_, q) = self.tau(k.increment());
1047        self.tau_prime(q.decrement())
1048    }
1049}
1050
1051#[cfg(test)]
1052mod test {
1053    use quickcheck::{quickcheck, Arbitrary};
1054    use rand::Rng;
1055    use std::{fmt::Debug, u32};
1056
1057    use super::*;
1058
1059    fn find_invalid_gc_list_pair(extents: &[ValidExtent]) -> Option<(ValidExtent, ValidExtent)> {
1060        extents
1061            .windows(2)
1062            .map(|window| (window[0], window[1]))
1063            .find(|&(a, b)| b.0 <= a.0 || b.1 <= a.1)
1064    }
1065
1066    fn assert_valid_gc_list(extents: &[ValidExtent]) {
1067        if let Some((a, b)) = find_invalid_gc_list_pair(extents) {
1068            panic!("{:?} and {:?} are invalid GC-list members", a, b)
1069        }
1070    }
1071
1072    impl Arbitrary for Position {
1073        fn arbitrary<G>(g: &mut G) -> Self
1074        where
1075            G: quickcheck::Gen,
1076        {
1077            match g.gen_range(0, 10) {
1078                0 => Position::NegativeInfinity,
1079                1 => Position::PositiveInfinity,
1080                _ => Position::Valid(Arbitrary::arbitrary(g)),
1081            }
1082        }
1083    }
1084
1085    #[derive(Debug, Clone, PartialEq)]
1086    struct RandomExtentList(Vec<ValidExtent>);
1087
1088    impl Arbitrary for RandomExtentList {
1089        fn arbitrary<G>(g: &mut G) -> Self
1090        where
1091            G: quickcheck::Gen,
1092        {
1093            let mut extents = vec![];
1094            let mut last_extent = (0, 1);
1095
1096            for _ in 0..g.size() {
1097                let start_offset = u64::arbitrary(g);
1098                let new_start = last_extent.0 + 1 + start_offset;
1099                let min_width = last_extent.1 - last_extent.0;
1100                let max_width = min_width + g.size() as u64;
1101                let width = g.gen_range(min_width, max_width);
1102
1103                let extent = (new_start, new_start + width);
1104                extents.push(extent);
1105                last_extent = extent;
1106            }
1107
1108            assert_valid_gc_list(&extents);
1109            RandomExtentList(extents)
1110        }
1111
1112        fn shrink(&self) -> Box<Iterator<Item = Self>> {
1113            Box::new(RandomExtentListShrinker(self.0.clone()))
1114        }
1115    }
1116
1117    /// A simplistic shrinking strategy that preserves the ordering
1118    /// guarantee of the extent list
1119    struct RandomExtentListShrinker(Vec<ValidExtent>);
1120
1121    impl Iterator for RandomExtentListShrinker {
1122        type Item = RandomExtentList;
1123
1124        fn next(&mut self) -> Option<RandomExtentList> {
1125            match self.0.pop() {
1126                Some(..) => Some(RandomExtentList(self.0.clone())),
1127                None => None,
1128            }
1129        }
1130    }
1131
1132    impl Algebra for RandomExtentList {
1133        fn tau(&self, k: Position) -> Extent {
1134            (&self.0[..]).tau(k)
1135        }
1136        fn tau_prime(&self, k: Position) -> Extent {
1137            (&self.0[..]).tau_prime(k)
1138        }
1139        fn rho(&self, k: Position) -> Extent {
1140            (&self.0[..]).rho(k)
1141        }
1142        fn rho_prime(&self, k: Position) -> Extent {
1143            (&self.0[..]).rho_prime(k)
1144        }
1145    }
1146
1147    fn all_extents<A>(a: A) -> Vec<ValidExtent>
1148    where
1149        A: Algebra,
1150    {
1151        a.iter_tau().collect()
1152    }
1153
1154    fn any_k<A>(operator: A, k: Position) -> bool
1155    where
1156        A: Algebra + Copy,
1157    {
1158        let from_zero = all_extents(operator);
1159
1160        let via_tau = operator.tau(k) == from_zero.tau(k);
1161        let via_rho = operator.rho(k) == from_zero.rho(k);
1162        let via_tau_prime = operator.tau_prime(k) == from_zero.tau_prime(k);
1163        let via_rho_prime = operator.rho_prime(k) == from_zero.rho_prime(k);
1164
1165        via_tau && via_rho && via_tau_prime && via_rho_prime
1166    }
1167
1168    #[test]
1169    fn extent_list_all_tau_matches_all_rho() {
1170        fn prop(extents: RandomExtentList) -> bool {
1171            let a = (&extents).iter_tau();
1172            let b = (&extents).iter_rho();
1173
1174            a.eq(b)
1175        }
1176
1177        quickcheck(prop as fn(_) -> _);
1178    }
1179
1180    #[test]
1181    fn extent_list_tau_finds_extents_that_start_at_same_point() {
1182        let a = &[(1, 1), (2, 2)][..];
1183        assert_eq!(a.tau(1.into()), (1, 1));
1184        assert_eq!(a.tau(2.into()), (2, 2));
1185    }
1186
1187    #[test]
1188    fn extent_list_tau_finds_first_extent_starting_after_point() {
1189        let a = &[(3, 4)][..];
1190        assert_eq!(a.tau(1.into()), (3, 4));
1191    }
1192
1193    #[test]
1194    fn extent_list_tau_returns_end_marker_if_no_match() {
1195        let a = &[(1, 3)][..];
1196        assert_eq!(a.tau(2.into()), END_EXTENT);
1197    }
1198
1199    #[test]
1200    fn extent_list_rho_finds_extents_that_end_at_same_point() {
1201        let a = &[(1, 1), (2, 2)][..];
1202        assert_eq!(a.rho(1.into()), (1, 1));
1203        assert_eq!(a.rho(2.into()), (2, 2));
1204    }
1205
1206    #[test]
1207    fn extent_list_rho_finds_first_extent_ending_after_point() {
1208        let a = &[(3, 4)][..];
1209        assert_eq!(a.rho(1.into()), (3, 4));
1210    }
1211
1212    #[test]
1213    fn extent_list_rho_returns_end_marker_if_no_match() {
1214        let a = &[(1, 3)][..];
1215        assert_eq!(a.rho(4.into()), END_EXTENT);
1216    }
1217
1218    #[test]
1219    fn contained_in_all_tau_matches_all_rho() {
1220        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1221            let c = ContainedIn { a: &a, b: &b };
1222            c.iter_tau().eq(c.iter_rho())
1223        }
1224
1225        quickcheck(prop as fn(_, _) -> _);
1226    }
1227
1228    #[test]
1229    fn contained_in_all_tau_prime_matches_all_rho_prime() {
1230        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1231            let c = ContainedIn { a: &a, b: &b };
1232            c.iter_tau_prime().eq(c.iter_rho_prime())
1233        }
1234
1235        quickcheck(prop as fn(_, _) -> _);
1236    }
1237
1238    #[test]
1239    fn contained_in_any_k() {
1240        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1241            any_k(ContainedIn { a: &a, b: &b }, k)
1242        }
1243
1244        quickcheck(prop as fn(_, _, _) -> _);
1245    }
1246
1247    #[test]
1248    fn contained_in_needle_is_fully_within_haystack() {
1249        let a = &[(2, 3)][..];
1250        let b = &[(1, 4)][..];
1251        let c = ContainedIn { a, b };
1252        assert_eq!(c.tau(1.into()), (2, 3));
1253    }
1254
1255    #[test]
1256    fn contained_in_needle_end_matches_haystack_end() {
1257        let a = &[(2, 4)][..];
1258        let b = &[(1, 4)][..];
1259        let c = ContainedIn { a, b };
1260        assert_eq!(c.tau(1.into()), (2, 4));
1261    }
1262
1263    #[test]
1264    fn contained_in_needle_start_matches_haystack_start() {
1265        let a = &[(1, 3)][..];
1266        let b = &[(1, 4)][..];
1267        let c = ContainedIn { a, b };
1268        assert_eq!(c.tau(1.into()), (1, 3));
1269    }
1270
1271    #[test]
1272    fn contained_in_needle_and_haystack_exactly_match() {
1273        let a = &[(1, 4)][..];
1274        let b = &[(1, 4)][..];
1275        let c = ContainedIn { a, b };
1276        assert_eq!(c.tau(1.into()), (1, 4));
1277    }
1278
1279    #[test]
1280    fn contained_in_needle_starts_too_early() {
1281        let a = &[(1, 3)][..];
1282        let b = &[(2, 4)][..];
1283        let c = ContainedIn { a, b };
1284        assert_eq!(c.tau(1.into()), END_EXTENT);
1285    }
1286
1287    #[test]
1288    fn contained_in_needle_ends_too_late() {
1289        let a = &[(2, 5)][..];
1290        let b = &[(1, 4)][..];
1291        let c = ContainedIn { a, b };
1292        assert_eq!(c.tau(1.into()), END_EXTENT);
1293    }
1294
1295    #[test]
1296    fn containing_all_tau_matches_all_rho() {
1297        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1298            let c = Containing { a: &a, b: &b };
1299            c.iter_tau().eq(c.iter_rho())
1300        }
1301
1302        quickcheck(prop as fn(_, _) -> _);
1303    }
1304
1305    #[test]
1306    fn containing_all_tau_prime_matches_all_rho_prime() {
1307        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1308            let c = Containing { a: &a, b: &b };
1309            c.iter_tau_prime().eq(c.iter_rho_prime())
1310        }
1311
1312        quickcheck(prop as fn(_, _) -> _);
1313    }
1314
1315    #[test]
1316    fn containing_any_k() {
1317        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1318            any_k(Containing { a: &a, b: &b }, k)
1319        }
1320
1321        quickcheck(prop as fn(_, _, _) -> _);
1322    }
1323
1324    #[test]
1325    fn containing_haystack_fully_around_needle() {
1326        let a = &[(1, 4)][..];
1327        let b = &[(2, 3)][..];
1328        let c = Containing { a, b };
1329        assert_eq!(c.tau(1.into()), (1, 4));
1330    }
1331
1332    #[test]
1333    fn containing_haystack_end_matches_needle_end() {
1334        let a = &[(1, 4)][..];
1335        let b = &[(2, 4)][..];
1336        let c = Containing { a, b };
1337        assert_eq!(c.tau(1.into()), (1, 4));
1338    }
1339
1340    #[test]
1341    fn containing_haystack_start_matches_needle_start() {
1342        let a = &[(1, 4)][..];
1343        let b = &[(1, 3)][..];
1344        let c = Containing { a, b };
1345        assert_eq!(c.tau(1.into()), (1, 4));
1346    }
1347
1348    #[test]
1349    fn containing_haystack_and_needle_exactly_match() {
1350        let a = &[(1, 4)][..];
1351        let b = &[(1, 4)][..];
1352        let c = Containing { a, b };
1353        assert_eq!(c.tau(1.into()), (1, 4));
1354    }
1355
1356    #[test]
1357    fn containing_haystack_starts_too_late() {
1358        let a = &[(2, 4)][..];
1359        let b = &[(1, 3)][..];
1360        let c = Containing { a, b };
1361        assert_eq!(c.tau(1.into()), END_EXTENT);
1362    }
1363
1364    #[test]
1365    fn containing_haystack_ends_too_early() {
1366        let a = &[(1, 4)][..];
1367        let b = &[(2, 5)][..];
1368        let c = Containing { a, b };
1369        assert_eq!(c.tau(1.into()), END_EXTENT);
1370    }
1371
1372    #[test]
1373    fn not_contained_in_all_tau_matches_all_rho() {
1374        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1375            let c = NotContainedIn { a: &a, b: &b };
1376            c.iter_tau().eq(c.iter_rho())
1377        }
1378
1379        quickcheck(prop as fn(_, _) -> _);
1380    }
1381
1382    #[test]
1383    fn not_contained_in_all_tau_prime_matches_all_rho_prime() {
1384        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1385            let c = NotContainedIn { a: &a, b: &b };
1386            c.iter_tau_prime().eq(c.iter_rho_prime())
1387        }
1388
1389        quickcheck(prop as fn(_, _) -> _);
1390    }
1391
1392    #[test]
1393    fn not_contained_in_any_k() {
1394        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1395            any_k(NotContainedIn { a: &a, b: &b }, k)
1396        }
1397
1398        quickcheck(prop as fn(_, _, _) -> _);
1399    }
1400
1401    #[test]
1402    fn not_contained_in_needle_is_fully_within_haystack() {
1403        let a = &[(2, 3)][..];
1404        let b = &[(1, 4)][..];
1405        let c = NotContainedIn { a, b };
1406        assert_eq!(c.tau(1.into()), END_EXTENT);
1407    }
1408
1409    #[test]
1410    fn not_contained_in_needle_end_matches_haystack_end() {
1411        let a = &[(2, 4)][..];
1412        let b = &[(1, 4)][..];
1413        let c = NotContainedIn { a, b };
1414        assert_eq!(c.tau(1.into()), END_EXTENT);
1415    }
1416
1417    #[test]
1418    fn not_contained_in_needle_start_matches_haystack_start() {
1419        let a = &[(1, 3)][..];
1420        let b = &[(1, 4)][..];
1421        let c = NotContainedIn { a, b };
1422        assert_eq!(c.tau(1.into()), END_EXTENT);
1423    }
1424
1425    #[test]
1426    fn not_contained_in_needle_and_haystack_exactly_match() {
1427        let a = &[(1, 4)][..];
1428        let b = &[(1, 4)][..];
1429        let c = NotContainedIn { a, b };
1430        assert_eq!(c.tau(1.into()), END_EXTENT);
1431    }
1432
1433    #[test]
1434    fn not_contained_in_needle_starts_too_early() {
1435        let a = &[(1, 3)][..];
1436        let b = &[(2, 4)][..];
1437        let c = NotContainedIn { a, b };
1438        assert_eq!(c.tau(1.into()), (1, 3));
1439    }
1440
1441    #[test]
1442    fn not_contained_in_needle_ends_too_late() {
1443        let a = &[(2, 5)][..];
1444        let b = &[(1, 4)][..];
1445        let c = NotContainedIn { a, b };
1446        assert_eq!(c.tau(1.into()), (2, 5));
1447    }
1448
1449    #[test]
1450    fn not_containing_all_tau_matches_all_rho() {
1451        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1452            let c = NotContaining { a: &a, b: &b };
1453            c.iter_tau().eq(c.iter_rho())
1454        }
1455
1456        quickcheck(prop as fn(_, _) -> _);
1457    }
1458
1459    #[test]
1460    fn not_containing_all_tau_prime_matches_all_rho_prime() {
1461        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1462            let c = NotContaining { a: &a, b: &b };
1463            c.iter_tau_prime().eq(c.iter_rho_prime())
1464        }
1465
1466        quickcheck(prop as fn(_, _) -> _);
1467    }
1468
1469    #[test]
1470    fn not_containing_any_k() {
1471        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1472            any_k(NotContaining { a: &a, b: &b }, k)
1473        }
1474
1475        quickcheck(prop as fn(_, _, _) -> _);
1476    }
1477
1478    #[test]
1479    fn not_containing_haystack_fully_around_needle() {
1480        let a = &[(1, 4)][..];
1481        let b = &[(2, 3)][..];
1482        let c = NotContaining { a, b };
1483        assert_eq!(c.tau(1.into()), END_EXTENT);
1484    }
1485
1486    #[test]
1487    fn not_containing_haystack_end_matches_needle_end() {
1488        let a = &[(1, 4)][..];
1489        let b = &[(2, 4)][..];
1490        let c = NotContaining { a, b };
1491        assert_eq!(c.tau(1.into()), END_EXTENT);
1492    }
1493
1494    #[test]
1495    fn not_containing_haystack_start_matches_needle_start() {
1496        let a = &[(1, 4)][..];
1497        let b = &[(1, 3)][..];
1498        let c = NotContaining { a, b };
1499        assert_eq!(c.tau(1.into()), END_EXTENT);
1500    }
1501
1502    #[test]
1503    fn not_containing_haystack_and_needle_exactly_match() {
1504        let a = &[(1, 4)][..];
1505        let b = &[(1, 4)][..];
1506        let c = NotContaining { a, b };
1507        assert_eq!(c.tau(1.into()), END_EXTENT);
1508    }
1509
1510    #[test]
1511    fn not_containing_haystack_starts_too_late() {
1512        let a = &[(2, 4)][..];
1513        let b = &[(1, 3)][..];
1514        let c = NotContaining { a, b };
1515        assert_eq!(c.tau(1.into()), (2, 4));
1516    }
1517
1518    #[test]
1519    fn not_containing_haystack_ends_too_early() {
1520        let a = &[(1, 4)][..];
1521        let b = &[(2, 5)][..];
1522        let c = NotContaining { a, b };
1523        assert_eq!(c.tau(1.into()), (1, 4));
1524    }
1525
1526    #[test]
1527    fn both_of_all_tau_matches_all_rho() {
1528        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1529            let c = BothOf { a: &a, b: &b };
1530            c.iter_tau().eq(c.iter_rho())
1531        }
1532
1533        quickcheck(prop as fn(_, _) -> _);
1534    }
1535
1536    #[test]
1537    fn both_of_all_tau_prime_matches_all_rho_prime() {
1538        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1539            let c = BothOf { a: &a, b: &b };
1540            c.iter_tau_prime().eq(c.iter_rho_prime())
1541        }
1542
1543        quickcheck(prop as fn(_, _) -> _);
1544    }
1545
1546    #[test]
1547    fn both_of_any_k() {
1548        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1549            any_k(BothOf { a: &a, b: &b }, k)
1550        }
1551
1552        quickcheck(prop as fn(_, _, _) -> _);
1553    }
1554
1555    #[test]
1556    fn both_of_intersects_empty_lists() {
1557        let a = &[][..];
1558        let b = &[][..];
1559        let c = BothOf { a: &a, b: &b };
1560
1561        assert_eq!(all_extents(c), []);
1562    }
1563
1564    #[test]
1565    fn both_of_intersects_empty_list_and_nonempty_list() {
1566        let a = &[][..];
1567        let b = &[(1, 2)][..];
1568
1569        let c = BothOf { a: &a, b: &b };
1570        assert_eq!(all_extents(c), []);
1571
1572        let c = BothOf { a: &b, b: &a };
1573        assert_eq!(all_extents(c), []);
1574    }
1575
1576    #[test]
1577    fn both_of_intersects_nonempty_lists() {
1578        let a = &[(1, 2)][..];
1579        let b = &[(3, 4)][..];
1580
1581        let c = BothOf { a: &a, b: &b };
1582        assert_eq!(all_extents(c), [(1, 4)]);
1583
1584        let c = BothOf { a: &b, b: &a };
1585        assert_eq!(all_extents(c), [(1, 4)]);
1586    }
1587
1588    #[test]
1589    fn both_of_intersects_overlapping_nonnested_lists() {
1590        let a = &[(1, 3)][..];
1591        let b = &[(2, 4)][..];
1592
1593        let c = BothOf { a: &a, b: &b };
1594        assert_eq!(all_extents(c), [(1, 4)]);
1595
1596        let c = BothOf { a: &b, b: &a };
1597        assert_eq!(all_extents(c), [(1, 4)]);
1598    }
1599
1600    #[test]
1601    fn both_of_merges_overlapping_nested_lists() {
1602        let a = &[(1, 4)][..];
1603        let b = &[(2, 3)][..];
1604
1605        let c = BothOf { a: &a, b: &b };
1606        assert_eq!(all_extents(c), [(1, 4)]);
1607
1608        let c = BothOf { a: &b, b: &a };
1609        assert_eq!(all_extents(c), [(1, 4)]);
1610    }
1611
1612    #[test]
1613    fn both_of_merges_overlapping_lists_nested_at_end() {
1614        let a = &[(1, 4)][..];
1615        let b = &[(2, 4)][..];
1616
1617        let c = BothOf { a: &a, b: &b };
1618        assert_eq!(all_extents(c), [(1, 4)]);
1619
1620        let c = BothOf { a: &b, b: &a };
1621        assert_eq!(all_extents(c), [(1, 4)]);
1622    }
1623
1624    #[test]
1625    fn both_of_merges_overlapping_lists_nested_at_start() {
1626        let a = &[(1, 4)][..];
1627        let b = &[(1, 3)][..];
1628
1629        let c = BothOf { a: &a, b: &b };
1630        assert_eq!(all_extents(c), [(1, 4)]);
1631
1632        let c = BothOf { a: &b, b: &a };
1633        assert_eq!(all_extents(c), [(1, 4)]);
1634    }
1635
1636    #[test]
1637    fn both_of_lists_have_extents_starting_after_point() {
1638        let a = &[(1, 2)][..];
1639        let b = &[(3, 4)][..];
1640        let c = BothOf { a, b };
1641        assert_eq!(c.tau(1.into()), (1, 4));
1642    }
1643
1644    #[test]
1645    fn both_of_lists_do_not_have_extents_starting_after_point() {
1646        let a = &[(1, 2)][..];
1647        let b = &[(3, 4)][..];
1648        let c = BothOf { a, b };
1649        assert_eq!(c.tau(5.into()), END_EXTENT);
1650    }
1651
1652    #[test]
1653    fn one_of_all_tau_matches_all_rho() {
1654        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1655            let c = OneOf { a: &a, b: &b };
1656            c.iter_tau().eq(c.iter_rho())
1657        }
1658
1659        quickcheck(prop as fn(_, _) -> _);
1660    }
1661
1662    #[test]
1663    fn one_of_any_k() {
1664        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1665            any_k(OneOf { a: &a, b: &b }, k)
1666        }
1667
1668        quickcheck(prop as fn(_, _, _) -> _);
1669    }
1670
1671    #[test]
1672    fn one_of_merges_empty_lists() {
1673        let a = &[][..];
1674        let b = &[][..];
1675        let c = OneOf { a: &a, b: &b };
1676
1677        assert_eq!(all_extents(c), []);
1678    }
1679
1680    #[test]
1681    fn one_of_merges_empty_list_and_nonempty_list() {
1682        let a = &[][..];
1683        let b = &[(1, 2)][..];
1684
1685        let c = OneOf { a: &a, b: &b };
1686        assert_eq!(all_extents(c), [(1, 2)]);
1687
1688        let c = OneOf { a: &b, b: &a };
1689        assert_eq!(all_extents(c), [(1, 2)]);
1690    }
1691
1692    #[test]
1693    fn one_of_merges_nonempty_lists() {
1694        let a = &[(1, 2)][..];
1695        let b = &[(3, 4)][..];
1696
1697        let c = OneOf { a: &a, b: &b };
1698        assert_eq!(all_extents(c), [(1, 2), (3, 4)]);
1699
1700        let c = OneOf { a: &b, b: &a };
1701        assert_eq!(all_extents(c), [(1, 2), (3, 4)]);
1702    }
1703
1704    #[test]
1705    fn one_of_merges_overlapping_nonnested_lists() {
1706        let a = &[(1, 3)][..];
1707        let b = &[(2, 4)][..];
1708
1709        let c = OneOf { a: &a, b: &b };
1710        assert_eq!(all_extents(c), [(1, 3), (2, 4)]);
1711
1712        let c = OneOf { a: &b, b: &a };
1713        assert_eq!(all_extents(c), [(1, 3), (2, 4)]);
1714    }
1715
1716    #[test]
1717    fn one_of_merges_overlapping_nested_lists() {
1718        let a = &[(1, 4)][..];
1719        let b = &[(2, 3)][..];
1720
1721        let c = OneOf { a: &a, b: &b };
1722        assert_eq!(all_extents(c), [(2, 3)]);
1723
1724        let c = OneOf { a: &b, b: &a };
1725        assert_eq!(all_extents(c), [(2, 3)]);
1726    }
1727
1728    #[test]
1729    fn one_of_merges_overlapping_lists_nested_at_end() {
1730        let a = &[(1, 4)][..];
1731        let b = &[(2, 4)][..];
1732
1733        let c = OneOf { a: &a, b: &b };
1734        assert_eq!(all_extents(c), [(2, 4)]);
1735
1736        let c = OneOf { a: &b, b: &a };
1737        assert_eq!(all_extents(c), [(2, 4)]);
1738    }
1739
1740    #[test]
1741    fn one_of_merges_overlapping_lists_nested_at_start() {
1742        let a = &[(1, 4)][..];
1743        let b = &[(1, 3)][..];
1744
1745        let c = OneOf { a: &a, b: &b };
1746        assert_eq!(all_extents(c), [(1, 3)]);
1747
1748        let c = OneOf { a: &b, b: &a };
1749        assert_eq!(all_extents(c), [(1, 3)]);
1750    }
1751
1752    // The paper has an incorrect implementation of OneOf::rho, so we take
1753    // the time to have some extra test cases exposed by quickcheck.
1754
1755    #[test]
1756    fn one_of_rho_one_empty_list() {
1757        let a = &[][..];
1758        let b = &[(1, 2)][..];
1759        let c = OneOf { a: &a, b: &b };
1760
1761        assert_eq!(c.rho(0.into()), (1, 2));
1762        assert_eq!(c.rho(1.into()), (1, 2));
1763        assert_eq!(c.rho(2.into()), (1, 2));
1764        assert_eq!(c.rho(3.into()), END_EXTENT);
1765    }
1766
1767    #[test]
1768    fn one_of_rho_nested_extents() {
1769        let a = &[(2, 3)][..];
1770        let b = &[(1, 5)][..];
1771        let c = OneOf { a: &a, b: &b };
1772
1773        assert_eq!(c.rho(0.into()), (2, 3));
1774        assert_eq!(c.rho(1.into()), (2, 3));
1775        assert_eq!(c.rho(2.into()), (2, 3));
1776        assert_eq!(c.rho(3.into()), (2, 3));
1777        assert_eq!(c.rho(4.into()), END_EXTENT);
1778    }
1779
1780    #[test]
1781    fn one_of_rho_nested_extents_with_trailing_extent() {
1782        let a = &[(1, 5)][..];
1783        let b = &[(2, 3), (6, 7)][..];
1784        let c = OneOf { a: &a, b: &b };
1785
1786        assert_eq!(c.rho(4.into()), (6, 7));
1787    }
1788
1789    #[test]
1790    fn one_of_rho_overlapping_extents() {
1791        let a = &[(1, 4), (2, 7)][..];
1792        let b = &[(3, 6)][..];
1793        let c = OneOf { a: &a, b: &b };
1794
1795        assert_eq!(c.rho(4.into()), (1, 4));
1796    }
1797
1798    #[test]
1799    fn one_of_rho_overlapping_and_nested_extents() {
1800        let a = &[(11, 78)][..];
1801        let b = &[(9, 60), (11, 136)][..];
1802        let c = OneOf { a: &a, b: &b };
1803
1804        assert_eq!(c.rho(12.into()), (9, 60));
1805    }
1806
1807    #[test]
1808    fn followed_by_all_tau_matches_all_rho() {
1809        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1810            let c = FollowedBy { a: &a, b: &b };
1811            c.iter_tau().eq(c.iter_rho())
1812        }
1813
1814        quickcheck(prop as fn(_, _) -> _);
1815    }
1816
1817    #[test]
1818    fn followed_by_all_tau_prime_matches_all_rho_prime() {
1819        fn prop(a: RandomExtentList, b: RandomExtentList) -> bool {
1820            let c = FollowedBy { a: &a, b: &b };
1821            c.iter_tau_prime().eq(c.iter_rho_prime())
1822        }
1823
1824        quickcheck(prop as fn(_, _) -> _);
1825    }
1826
1827    #[test]
1828    fn followed_by_any_k() {
1829        fn prop(a: RandomExtentList, b: RandomExtentList, k: Position) -> bool {
1830            any_k(FollowedBy { a: &a, b: &b }, k)
1831        }
1832
1833        quickcheck(prop as fn(_, _, _) -> _);
1834    }
1835
1836    #[test]
1837    fn followed_by_empty_lists() {
1838        let a = &[][..];
1839        let b = &[][..];
1840        let c = FollowedBy { a, b };
1841        assert_eq!(all_extents(c), []);
1842    }
1843
1844    #[test]
1845    fn followed_by_one_empty_list() {
1846        let a = &[(1, 2)][..];
1847        let b = &[][..];
1848
1849        let c = FollowedBy { a, b };
1850        assert_eq!(all_extents(c), []);
1851
1852        let c = FollowedBy { a: b, b: a };
1853        assert_eq!(all_extents(c), []);
1854    }
1855
1856    #[test]
1857    fn followed_by_overlapping() {
1858        let a = &[(1, 2)][..];
1859        let b = &[(2, 3)][..];
1860        let c = FollowedBy { a, b };
1861        assert_eq!(all_extents(c), []);
1862    }
1863
1864    #[test]
1865    fn followed_by_in_ascending_order() {
1866        let a = &[(1, 2)][..];
1867        let b = &[(3, 4)][..];
1868        let c = FollowedBy { a, b };
1869        assert_eq!(all_extents(c), [(1, 4)]);
1870    }
1871
1872    #[test]
1873    fn followed_by_in_descending_order() {
1874        let a = &[(3, 4)][..];
1875        let b = &[(1, 2)][..];
1876        let c = FollowedBy { a, b };
1877        assert_eq!(all_extents(c), []);
1878    }
1879
1880    trait QuickcheckAlgebra: Algebra + Debug {
1881        fn clone_quickcheck_algebra(&self) -> Box<QuickcheckAlgebra + Send>;
1882    }
1883
1884    impl<A> QuickcheckAlgebra for A
1885    where
1886        A: Algebra + Debug + Clone + Send + 'static,
1887    {
1888        fn clone_quickcheck_algebra(&self) -> Box<QuickcheckAlgebra + Send> {
1889            Box::new(self.clone())
1890        }
1891    }
1892
1893    #[derive(Debug)]
1894    struct ArbitraryAlgebraTree(Box<QuickcheckAlgebra + Send>);
1895
1896    impl Clone for ArbitraryAlgebraTree {
1897        fn clone(&self) -> ArbitraryAlgebraTree {
1898            ArbitraryAlgebraTree(self.0.clone_quickcheck_algebra())
1899        }
1900    }
1901
1902    impl Algebra for ArbitraryAlgebraTree {
1903        fn tau(&self, k: Position) -> Extent {
1904            self.0.tau(k)
1905        }
1906        fn tau_prime(&self, k: Position) -> Extent {
1907            self.0.tau_prime(k)
1908        }
1909        fn rho(&self, k: Position) -> Extent {
1910            self.0.rho(k)
1911        }
1912        fn rho_prime(&self, k: Position) -> Extent {
1913            self.0.rho_prime(k)
1914        }
1915    }
1916
1917    impl Arbitrary for ArbitraryAlgebraTree {
1918        fn arbitrary<G>(g: &mut G) -> Self
1919        where
1920            G: quickcheck::Gen,
1921        {
1922            // We need to control the `size` parameter without making
1923            // new generators, so we make this little side fucntion.
1924            fn inner<G>(g: &mut G, size: usize) -> ArbitraryAlgebraTree
1925            where
1926                G: quickcheck::Gen,
1927            {
1928                let generate_leaf: bool = g.gen_bool(0.1);
1929
1930                if size == 0 || generate_leaf {
1931                    let extents = RandomExtentList::arbitrary(g);
1932                    ArbitraryAlgebraTree(Box::new(extents))
1933                } else {
1934                    let a = inner(g, size / 2);
1935                    let b = inner(g, size / 2);
1936
1937                    let c: Box<QuickcheckAlgebra + Send> = match g.gen_range(0, 7) {
1938                        0 => Box::new(ContainedIn { a, b }),
1939                        1 => Box::new(Containing { a, b }),
1940                        2 => Box::new(NotContainedIn { a, b }),
1941                        3 => Box::new(NotContaining { a, b }),
1942                        4 => Box::new(BothOf { a, b }),
1943                        5 => Box::new(OneOf { a, b }),
1944                        6 => Box::new(FollowedBy { a, b }),
1945                        _ => unreachable!(),
1946                    };
1947
1948                    ArbitraryAlgebraTree(c)
1949                }
1950            }
1951
1952            let sz = g.size();
1953            inner(g, sz)
1954        }
1955    }
1956
1957    #[test]
1958    fn tree_of_operators_all_tau_matches_all_rho() {
1959        fn prop(a: ArbitraryAlgebraTree) -> bool {
1960            (&a).iter_tau().eq((&a).iter_rho())
1961        }
1962
1963        quickcheck(prop as fn(_) -> _);
1964    }
1965
1966    #[test]
1967    fn tree_of_operators_all_tau_prime_matches_all_rho_prime() {
1968        fn prop(a: ArbitraryAlgebraTree) -> bool {
1969            (&a).iter_tau_prime().eq((&a).iter_rho_prime())
1970        }
1971
1972        quickcheck(prop as fn(_) -> _);
1973    }
1974
1975    #[test]
1976    fn tree_of_operators_any_k() {
1977        fn prop(a: ArbitraryAlgebraTree, k: Position) -> bool {
1978            any_k(&a, k)
1979        }
1980
1981        quickcheck(prop as fn(_, _) -> _);
1982    }
1983
1984    #[test]
1985    fn document_tau_matches_rho() {
1986        fn prop(count: u8) -> bool {
1987            let d = Documents::new(u32::from(count));
1988            d.iter_tau().eq(d.iter_rho())
1989        }
1990
1991        quickcheck(prop as fn(_) -> _);
1992    }
1993
1994    #[test]
1995    fn document_tau_prime_matches_rho_prime() {
1996        fn prop(count: u8) -> bool {
1997            let d = Documents::new(u32::from(count));
1998            d.iter_tau_prime().eq(d.iter_rho_prime())
1999        }
2000
2001        quickcheck(prop as fn(_) -> _);
2002    }
2003
2004    fn doc_k(idx: u32, offset: u32) -> Position {
2005        (u64::from(idx) << 32 | u64::from(offset)).into()
2006    }
2007
2008    fn doc_extent(idx: u32) -> (u64, u64) {
2009        let start = u64::from(idx) << 32;
2010        let end = start + 0xFFFF_FFFF;
2011        (start, end)
2012    }
2013
2014    #[test]
2015    fn document_tau_at_document_start() {
2016        let d = Documents::new(10);
2017        assert_eq!(d.tau(doc_k(1, 0)), doc_extent(1));
2018    }
2019
2020    #[test]
2021    fn document_tau_at_document_end() {
2022        let d = Documents::new(10);
2023        assert_eq!(d.tau(doc_k(1, u32::MAX)), doc_extent(2));
2024    }
2025
2026    #[test]
2027    fn document_tau_between_document_boundaries() {
2028        let d = Documents::new(10);
2029        assert_eq!(d.tau(doc_k(1, 42)), doc_extent(2));
2030    }
2031
2032    #[test]
2033    fn document_tau_at_directional_end() {
2034        let d = Documents::new(10);
2035        assert_eq!(d.tau(doc_k(10, 1)), END_EXTENT)
2036    }
2037
2038    #[test]
2039    fn document_tau_prime_at_document_start() {
2040        let d = Documents::new(10);
2041        assert_eq!(d.tau_prime(doc_k(1, 0)), doc_extent(0));
2042    }
2043
2044    #[test]
2045    fn document_tau_prime_at_document_end() {
2046        let d = Documents::new(10);
2047        assert_eq!(d.tau_prime(doc_k(1, u32::MAX)), doc_extent(1));
2048    }
2049
2050    #[test]
2051    fn document_tau_prime_between_document_boundaries() {
2052        let d = Documents::new(10);
2053        assert_eq!(d.tau_prime(doc_k(1, 42)), doc_extent(0));
2054    }
2055
2056    #[test]
2057    fn document_tau_prime_before_directional_start() {
2058        let d = Documents::new(10);
2059        assert_eq!(d.tau_prime(doc_k(20, 0)), doc_extent(9))
2060    }
2061
2062    #[test]
2063    fn document_tau_prime_at_directional_end() {
2064        let d = Documents::new(10);
2065        assert_eq!(d.tau_prime(doc_k(0, u32::MAX - 1)), START_EXTENT)
2066    }
2067
2068    #[test]
2069    fn document_rho_at_document_start() {
2070        let d = Documents::new(10);
2071        assert_eq!(d.rho(doc_k(1, 0)), doc_extent(1));
2072    }
2073
2074    #[test]
2075    fn document_rho_at_document_end() {
2076        let d = Documents::new(10);
2077        assert_eq!(d.rho(doc_k(1, u32::MAX)), doc_extent(1));
2078    }
2079
2080    #[test]
2081    fn document_rho_between_document_boundaries() {
2082        let d = Documents::new(10);
2083        assert_eq!(d.rho(doc_k(1, 42)), doc_extent(1));
2084    }
2085
2086    #[test]
2087    fn document_rho_at_directional_end() {
2088        let d = Documents::new(10);
2089        assert_eq!(d.rho(doc_k(11, 0)), END_EXTENT)
2090    }
2091
2092    #[test]
2093    fn document_rho_prime_at_document_start() {
2094        let d = Documents::new(10);
2095        assert_eq!(d.rho_prime(doc_k(1, 0)), doc_extent(1));
2096    }
2097
2098    #[test]
2099    fn document_rho_prime_at_document_end() {
2100        let d = Documents::new(10);
2101        assert_eq!(d.rho_prime(doc_k(1, u32::MAX)), doc_extent(1));
2102    }
2103
2104    #[test]
2105    fn document_rho_prime_between_document_boundaries() {
2106        let d = Documents::new(10);
2107        assert_eq!(d.rho_prime(doc_k(1, 42)), doc_extent(1));
2108    }
2109
2110    #[test]
2111    fn document_rho_prime_before_directional_start() {
2112        let d = Documents::new(10);
2113        assert_eq!(d.rho_prime(doc_k(20, 0)), doc_extent(9))
2114    }
2115
2116    #[test]
2117    fn document_rho_prime_at_directional_end() {
2118        let d = Documents::new(10);
2119        assert_eq!(d.rho_prime(doc_k(0, 0)), doc_extent(0))
2120    }
2121}
strata/lib.rs

strata/
lib.rs
