moqtap_codec/
prior_gaps.rs

1//! The Prior Group ID Gap and Prior Object ID Gap conditions that show across
2//! the Objects of one fetch stream, on drafts 11-23. Each draft's `FetchGaps`
3//! refuses what one Object shows on its own and hands its gaps here.
4//!
5//! A fetch stream carries its Groups in the requested Group Order and, within
6//! a Group, its Objects in Object ID order: draft-11 Section 8.13 and
7//! draft-23 Section 3.2.1, "Within each group, objects are sent in Object ID
8//! order; subgroup ID is not used for ordering." So the Group before this one,
9//! and the Object before this one in its Group, are the only ones a gap below
10//! this Object can cover, and the only ones whose gap can hold this Object.
11
12use crate::error::CodecError;
13
14/// Which Prior gap conditions a draft states without contradicting itself.
15// A build without every draft leaves some variants unused.
16#[allow(dead_code)]
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub(crate) enum GapRules {
19    /// draft-11 Section 10.1, draft-12 Section 10.1 and draft-13 Section 10.1:
20    /// an Object may carry Prior Group ID Gap more than once, there is no Prior
21    /// Object ID Gap, and no condition about a gap covering an earlier Object.
22    Draft11To13,
23    /// draft-14 Section 11.1, draft-14 Section 11.3, draft-15 Section 11.1 and
24    /// draft-15 Section 11.2: one instance of each gap per Object, "An endpoint
25    /// receives an Object with a Prior Group ID Gap covering an Object it
26    /// previously received", its Prior Object ID Gap twin, and "An endpoint
27    /// receives an Object with a Group ID within a previously communicated
28    /// gap" and its twin.
29    Draft14To15,
30    /// Drafts 16-17 state the conditions of drafts 14-15, but
31    /// draft-16 Section 2.1 and draft-17 Section 2.1 say of an Object known to
32    /// exist: "From this state, it can transition to not existing, but not vice
33    /// versa." A gap covering an Object already received is that transition, so
34    /// the two covering conditions are ambiguous and not checked.
35    Draft16To17,
36    /// Drafts 18-22 add, in draft-18 Section 2.1, draft-19 Section 2.1,
37    /// draft-20 Section 2.1, draft-21 Section 2.1.1 and draft-22 Section 2.1.2:
38    /// "an endpoint can receive an Object after it has already recorded that
39    /// the Object does not exist [...] This is not a protocol error and the
40    /// Track is not malformed." So the two within-gap conditions are ambiguous
41    /// too, and neither pair is checked.
42    Draft18To22,
43    /// draft-23 Section 10.8 and draft-23 Section 10.9 state all four, and
44    /// draft-23 Section 2.1.2 drops both sentences above.
45    Draft23On,
46}
47
48impl GapRules {
49    /// A gap covering the Group or Object before it on the stream is refused.
50    fn checks_covering(self) -> bool {
51        matches!(self, Self::Draft14To15 | Self::Draft23On)
52    }
53
54    /// A Group or Object within the gap the one before it communicated is
55    /// refused.
56    fn checks_within(self) -> bool {
57        !matches!(self, Self::Draft18To22)
58    }
59}
60
61/// The Prior gap state of one fetch stream.
62#[derive(Debug, Clone, PartialEq, Eq)]
63pub(crate) struct FetchGapTracker {
64    rules: GapRules,
65    run: Option<GroupRun>,
66    /// The Group before the current one, and the gap it communicated.
67    earlier: Option<(u64, u64)>,
68}
69
70#[derive(Debug, Clone, PartialEq, Eq)]
71struct GroupRun {
72    group_id: u64,
73    /// The values every Object of the Group that carried a gap carried, or
74    /// `None` before the first such Object.
75    common: Option<Vec<u64>>,
76    /// The gap the Group communicated: whichever value is taken as each
77    /// Object's, the gap is at least this. 0 while no Object carried one.
78    communicated: u64,
79    /// The latest Object of the Group, and its Prior Object ID Gap.
80    last_object: Option<(u64, Option<u64>)>,
81}
82
83impl FetchGapTracker {
84    pub(crate) fn new(rules: GapRules) -> Self {
85        Self { rules, run: None, earlier: None }
86    }
87
88    /// Check the next Object, whose gaps its draft's `PriorGaps` has already
89    /// held to its Group ID and Object ID. Records the Object only when it
90    /// passes.
91    pub(crate) fn check(
92        &mut self,
93        group_id: u64,
94        object_id: u64,
95        group_gaps: &[u64],
96        object_gap: Option<u64>,
97    ) -> Result<(), CodecError> {
98        let mut earlier = self.earlier;
99        let mut run = match &self.run {
100            Some(run) if run.group_id == group_id => run.clone(),
101            other => {
102                if let Some(prior) = other {
103                    earlier = Some((prior.group_id, prior.communicated));
104                }
105                GroupRun { group_id, common: None, communicated: 0, last_object: None }
106            }
107        };
108
109        if let Some((prior, gap)) = earlier {
110            if self.rules.checks_within() && group_id < prior && group_id >= prior - gap {
111                return Err(malformed(format!(
112                    "Group {group_id} is within the Prior Group ID Gap {gap} that Group {prior} \
113                     communicated"
114                )));
115            }
116            if self.rules.checks_covering() {
117                if let Some(&gap) =
118                    group_gaps.iter().find(|&&gap| prior < group_id && prior >= group_id - gap)
119                {
120                    return Err(malformed(format!(
121                        "Prior Group ID Gap {gap} of Group {group_id} covers Group {prior}, \
122                         received earlier"
123                    )));
124                }
125            }
126        }
127
128        if !group_gaps.is_empty() {
129            let common: Vec<u64> = match &run.common {
130                Some(common) => common.iter().copied().filter(|v| group_gaps.contains(v)).collect(),
131                None => {
132                    let mut values = group_gaps.to_vec();
133                    values.sort_unstable();
134                    values.dedup();
135                    values
136                }
137            };
138            if common.is_empty() {
139                return Err(malformed(match self.rules {
140                    GapRules::Draft11To13 => format!(
141                        "the Objects in Group {group_id} carry no Prior Group ID Gap value in common"
142                    ),
143                    _ => format!(
144                        "two Objects in Group {group_id} carry different Prior Group ID Gap values"
145                    ),
146                }));
147            }
148            run.common = Some(common);
149            let least = group_gaps.iter().copied().min().unwrap_or(0);
150            run.communicated = run.communicated.max(least);
151        }
152
153        if let Some((prior, prior_gap)) = run.last_object {
154            if let Some(gap) = object_gap.filter(|_| self.rules.checks_covering()) {
155                if gap > 0 && prior < object_id && prior >= object_id - gap {
156                    return Err(malformed(format!(
157                        "Prior Object ID Gap {gap} of Object {object_id} covers Object {prior}"
158                    )));
159                }
160            }
161            if let Some(gap) = prior_gap.filter(|_| self.rules.checks_within()) {
162                if object_id < prior && object_id >= prior - gap {
163                    return Err(malformed(format!(
164                        "Object {object_id} is within the Prior Object ID Gap {gap} that Object \
165                         {prior} communicated"
166                    )));
167                }
168            }
169        }
170        run.last_object = Some((object_id, object_gap));
171
172        self.earlier = earlier;
173        self.run = Some(run);
174        Ok(())
175    }
176}
177
178fn malformed(detail: String) -> CodecError {
179    CodecError::MalformedTrack { detail }
180}
181
182#[cfg(test)]
183mod tests {
184    use super::*;
185
186    fn refused(r: Result<(), CodecError>) -> bool {
187        matches!(r, Err(CodecError::MalformedTrack { .. }))
188    }
189
190    #[test]
191    fn objects_of_one_group_with_different_values_are_refused() {
192        let mut t = FetchGapTracker::new(GapRules::Draft23On);
193        t.check(5, 0, &[2], None).unwrap();
194        t.check(5, 1, &[], None).unwrap();
195        assert!(refused(t.check(5, 2, &[3], None)));
196    }
197
198    #[test]
199    fn groups_are_compared_separately() {
200        let mut t = FetchGapTracker::new(GapRules::Draft23On);
201        t.check(5, 0, &[1], None).unwrap();
202        t.check(7, 0, &[1], None).unwrap();
203    }
204
205    #[test]
206    fn a_failed_check_records_nothing() {
207        let mut t = FetchGapTracker::new(GapRules::Draft23On);
208        t.check(5, 0, &[2], None).unwrap();
209        assert!(refused(t.check(5, 1, &[3], None)));
210        t.check(5, 2, &[2], None).unwrap();
211    }
212
213    #[test]
214    fn a_group_gap_covering_the_group_before_is_refused_from_draft_14() {
215        let mut t = FetchGapTracker::new(GapRules::Draft23On);
216        t.check(8, 0, &[], None).unwrap();
217        assert!(refused(t.check(10, 0, &[2], None)));
218        let mut t = FetchGapTracker::new(GapRules::Draft23On);
219        t.check(7, 0, &[], None).unwrap();
220        t.check(10, 0, &[2], None).unwrap();
221        let mut t = FetchGapTracker::new(GapRules::Draft11To13);
222        t.check(8, 0, &[], None).unwrap();
223        t.check(10, 0, &[2], None).unwrap();
224    }
225
226    #[test]
227    fn a_group_within_the_gap_the_group_before_communicated_is_refused() {
228        for rules in [GapRules::Draft11To13, GapRules::Draft23On] {
229            let mut t = FetchGapTracker::new(rules);
230            t.check(10, 0, &[2], None).unwrap();
231            assert!(refused(t.check(9, 0, &[], None)));
232            let mut t = FetchGapTracker::new(rules);
233            t.check(10, 0, &[2], None).unwrap();
234            t.check(7, 0, &[], None).unwrap();
235        }
236    }
237
238    #[test]
239    fn the_least_of_one_objects_values_is_the_gap_it_communicated() {
240        let mut t = FetchGapTracker::new(GapRules::Draft11To13);
241        t.check(10, 0, &[1, 3], None).unwrap();
242        t.check(8, 0, &[], None).unwrap();
243        let mut t = FetchGapTracker::new(GapRules::Draft11To13);
244        t.check(10, 0, &[1, 3], None).unwrap();
245        assert!(refused(t.check(9, 0, &[], None)));
246    }
247
248    #[test]
249    fn objects_of_one_group_with_a_value_in_common_are_accepted_on_drafts_11_to_13() {
250        let mut t = FetchGapTracker::new(GapRules::Draft11To13);
251        t.check(5, 0, &[2, 3], None).unwrap();
252        t.check(5, 1, &[3, 4], None).unwrap();
253        assert!(refused(t.check(5, 2, &[2], None)));
254    }
255
256    #[test]
257    fn an_object_gap_covering_the_object_before_is_refused() {
258        let mut t = FetchGapTracker::new(GapRules::Draft23On);
259        t.check(3, 8, &[], None).unwrap();
260        assert!(refused(t.check(3, 10, &[], Some(2))));
261        let mut t = FetchGapTracker::new(GapRules::Draft23On);
262        t.check(3, 7, &[], None).unwrap();
263        t.check(3, 10, &[], Some(2)).unwrap();
264        t.check(4, 2, &[], Some(2)).unwrap();
265    }
266
267    #[test]
268    fn an_object_within_the_gap_the_object_before_communicated_is_refused() {
269        let mut t = FetchGapTracker::new(GapRules::Draft23On);
270        t.check(3, 10, &[], Some(2)).unwrap();
271        assert!(refused(t.check(3, 9, &[], None)));
272    }
273
274    #[test]
275    fn drafts_16_to_17_do_not_refuse_a_covering_gap() {
276        let mut t = FetchGapTracker::new(GapRules::Draft16To17);
277        t.check(9, 0, &[], None).unwrap();
278        t.check(10, 0, &[1], None).unwrap();
279        t.check(10, 1, &[1], Some(1)).unwrap();
280        let mut t = FetchGapTracker::new(GapRules::Draft16To17);
281        t.check(10, 0, &[2], None).unwrap();
282        assert!(refused(t.check(9, 0, &[], None)));
283    }
284
285    #[test]
286    fn drafts_18_to_22_refuse_neither_covering_nor_within() {
287        let mut t = FetchGapTracker::new(GapRules::Draft18To22);
288        t.check(9, 0, &[], None).unwrap();
289        t.check(10, 0, &[1], None).unwrap();
290        t.check(10, 3, &[1], Some(2)).unwrap();
291        t.check(10, 2, &[1], None).unwrap();
292        t.check(9, 1, &[1], None).unwrap();
293        assert!(refused(t.check(9, 2, &[2], None)));
294    }
295}
moqtap_codec/prior_gaps.rs

moqtap_codec/
prior_gaps.rs
