broadcast_dash/
template.rs

1//! `SegmentTemplate` identifier scanning and substitution (ISO/IEC 23009-1
2//! 5.3.9.4.4, Table 21).
3//!
4//! The scan is strict: a `$` that does not enclose a known identifier makes
5//! the whole template invalid, which the spec resolves by dropping the
6//! containing Representation (5.3.9.4.4 step 2). Format tags are `%0<width>d`
7//! only. Substitution reads the same scanned parts the validator builds, so a
8//! width is clamped once (to [`MAX_FORMAT_WIDTH`]) and `$$` is read once.
9
10use broadcast_common::impl_spec_display;
11
12const IDENT_RESERVED: &str = "RepresentationID";
13const IDENT_NUMBER: &str = "Number";
14const IDENT_TIME: &str = "Time";
15const IDENT_BANDWIDTH: &str = "Bandwidth";
16const IDENT_SUB_NUMBER: &str = "SubNumber";
17const TAG_ZERO_FLAG: char = '0';
18const TAG_CONVERSION: char = 'd';
19const DELIMITER: char = '$';
20const TAG_START: char = '%';
21
22/// Which identifiers a template contains.
23#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
24#[non_exhaustive]
25pub struct TemplateUse {
26    /// `$RepresentationID$`.
27    pub representation_id: bool,
28    /// `$Number$`.
29    pub number: bool,
30    /// `$Time$`.
31    pub time: bool,
32    /// `$Bandwidth$`.
33    pub bandwidth: bool,
34    /// `$SubNumber$` (segment sequences; unsupported).
35    pub sub_number: bool,
36}
37
38/// Why a template is invalid.
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40#[non_exhaustive]
41pub enum TemplateFault {
42    /// A `$` with no closing `$`.
43    UnterminatedIdentifier,
44    /// `$name$` where `name` is not in Table 21.
45    UnknownIdentifier,
46    /// A format tag on `$RepresentationID$`, which takes none.
47    FormatOnRepresentationId,
48    /// A format tag that is not `%0<width>d`.
49    BadFormatTag,
50    /// A width above the supported maximum.
51    WidthTooLarge,
52    /// `$Number$` and `$Time$` in one template.
53    NumberAndTime,
54    /// A media template with neither `$Number$` nor `$Time$`.
55    MissingNumberOrTime,
56    /// An `@initialization` template containing `$Number$` or `$Time$`.
57    DynamicIdentifierInInitialization,
58}
59
60/// Cap on the `%0Nd` zero-padding width in a `$Number$`, `$Time$` or
61/// `$Bandwidth$` substitution. A `u64` in decimal has at most 20 digits, so a
62/// wider padding is meaningless and a hostile `$Number%9999999999d$` would
63/// allocate or loop unboundedly.
64pub const MAX_FORMAT_WIDTH: usize = 20;
65
66/// Why [`substitute`] could not render a URL.
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
68#[non_exhaustive]
69pub enum TemplateError {
70    /// The template is invalid; the Representation is dropped.
71    Invalid(TemplateFault),
72    /// The template contains `$Number$` but no number was supplied.
73    MissingNumber,
74    /// The template contains `$Time$` but no time was supplied.
75    MissingTime,
76}
77
78impl TemplateError {
79    /// The [`TemplateFault`] behind [`TemplateError::Invalid`]; a missing value
80    /// is reported as [`TemplateFault::MissingNumberOrTime`], which is where
81    /// 5.3.9.4.4 leaves a template the caller cannot render.
82    #[must_use]
83    pub fn fault(self) -> TemplateFault {
84        match self {
85            Self::Invalid(f) => f,
86            Self::MissingNumber | Self::MissingTime => TemplateFault::MissingNumberOrTime,
87        }
88    }
89
90    /// Stable snake_case label.
91    #[must_use]
92    pub fn name(&self) -> &'static str {
93        match self {
94            Self::Invalid(_) => "invalid",
95            Self::MissingNumber => "missing_number",
96            Self::MissingTime => "missing_time",
97        }
98    }
99}
100impl_spec_display!(TemplateError);
101
102impl TemplateFault {
103    /// Stable snake_case label.
104    #[must_use]
105    pub fn name(&self) -> &'static str {
106        match self {
107            Self::UnterminatedIdentifier => "unterminated_identifier",
108            Self::UnknownIdentifier => "unknown_identifier",
109            Self::FormatOnRepresentationId => "format_on_representation_id",
110            Self::BadFormatTag => "bad_format_tag",
111            Self::WidthTooLarge => "width_too_large",
112            Self::NumberAndTime => "number_and_time",
113            Self::MissingNumberOrTime => "missing_number_or_time",
114            Self::DynamicIdentifierInInitialization => "dynamic_identifier_in_initialization",
115        }
116    }
117}
118impl_spec_display!(TemplateFault);
119
120fn check_tag(tag: &str) -> Result<(), TemplateFault> {
121    let inner = tag
122        .strip_suffix(TAG_CONVERSION)
123        .ok_or(TemplateFault::BadFormatTag)?;
124    let digits = inner
125        .strip_prefix(TAG_ZERO_FLAG)
126        .ok_or(TemplateFault::BadFormatTag)?;
127    if !digits.bytes().all(|b| b.is_ascii_digit()) {
128        return Err(TemplateFault::BadFormatTag);
129    }
130    if !digits.is_empty() {
131        let width: usize = digits.parse().map_err(|_| TemplateFault::WidthTooLarge)?;
132        if width > MAX_FORMAT_WIDTH {
133            return Err(TemplateFault::WidthTooLarge);
134        }
135    }
136    Ok(())
137}
138
139/// Scan `template` and report the identifiers it uses.
140///
141/// # Errors
142/// [`TemplateFault`] for anything 5.3.9.4.4 leaves undefined.
143pub fn scan(template: &str) -> Result<TemplateUse, TemplateFault> {
144    let mut used = TemplateUse::default();
145    let mut rest = template;
146    while let Some(at) = rest.find(DELIMITER) {
147        let tail = &rest[at + 1..];
148        if let Some(after) = tail.strip_prefix(DELIMITER) {
149            rest = after;
150            continue;
151        }
152        let end = tail
153            .find(DELIMITER)
154            .ok_or(TemplateFault::UnterminatedIdentifier)?;
155        let ident = &tail[..end];
156        let (name, tag) = match ident.split_once(TAG_START) {
157            Some((n, t)) => (n, Some(format!("{TAG_START}{t}"))),
158            None => (ident, None),
159        };
160        match name {
161            IDENT_RESERVED => {
162                if tag.is_some() {
163                    return Err(TemplateFault::FormatOnRepresentationId);
164                }
165                used.representation_id = true;
166            }
167            IDENT_NUMBER | IDENT_TIME | IDENT_BANDWIDTH | IDENT_SUB_NUMBER => {
168                if let Some(t) = &tag {
169                    check_tag(&t[TAG_START.len_utf8()..])?;
170                }
171                match name {
172                    IDENT_NUMBER => used.number = true,
173                    IDENT_TIME => used.time = true,
174                    IDENT_BANDWIDTH => used.bandwidth = true,
175                    _ => used.sub_number = true,
176                }
177            }
178            _ => return Err(TemplateFault::UnknownIdentifier),
179        }
180        rest = &tail[end + 1..];
181    }
182    Ok(used)
183}
184
185/// Validate a media/index template: exactly one of `$Number$`/`$Time$`.
186///
187/// # Errors
188/// [`TemplateFault`].
189pub fn scan_media(template: &str) -> Result<TemplateUse, TemplateFault> {
190    let used = scan(template)?;
191    if used.number && used.time {
192        return Err(TemplateFault::NumberAndTime);
193    }
194    if !used.number && !used.time {
195        return Err(TemplateFault::MissingNumberOrTime);
196    }
197    Ok(used)
198}
199
200/// Validate an initialization template: neither `$Number$` nor `$Time$`.
201///
202/// # Errors
203/// [`TemplateFault`].
204pub fn scan_initialization(template: &str) -> Result<TemplateUse, TemplateFault> {
205    let used = scan(template)?;
206    if used.number || used.time {
207        return Err(TemplateFault::DynamicIdentifierInInitialization);
208    }
209    Ok(used)
210}
211
212/// Substitute the identifiers of an already scanned template.
213///
214/// # Errors
215/// [`TemplateError::Invalid`] when the template is not a valid 5.3.9.4.4
216/// template, [`TemplateError::MissingNumber`] / [`TemplateError::MissingTime`]
217/// when the template names a value the caller did not supply. A missing value
218/// is never dropped silently: the URL would point at the wrong segment.
219pub fn substitute(
220    template: &str,
221    representation_id: &str,
222    number: Option<u64>,
223    time: Option<u64>,
224    bandwidth: u64,
225) -> Result<String, TemplateError> {
226    let parts = parts(template).map_err(TemplateError::Invalid)?;
227    let mut out = String::with_capacity(template.len());
228    for part in &parts {
229        match part {
230            Part::Literal(text) => out.push_str(text),
231            Part::Escape => out.push(DELIMITER),
232            Part::RepresentationId => out.push_str(representation_id),
233            Part::Number(width) => {
234                let value = number.ok_or(TemplateError::MissingNumber)?;
235                out.push_str(&pad(value, *width));
236            }
237            Part::Time(width) => {
238                let value = time.ok_or(TemplateError::MissingTime)?;
239                out.push_str(&pad(value, *width));
240            }
241            Part::Bandwidth(width) => out.push_str(&pad(bandwidth, *width)),
242        }
243    }
244    Ok(out)
245}
246
247/// `value` in decimal, zero-padded to `width` (never truncated, never wider
248/// than [`MAX_FORMAT_WIDTH`]).
249fn pad(value: u64, width: Option<usize>) -> String {
250    let digits = value.to_string();
251    let width = width.unwrap_or(1).min(MAX_FORMAT_WIDTH);
252    if width <= digits.len() {
253        return digits;
254    }
255    let mut out = String::with_capacity(width);
256    out.extend(core::iter::repeat_n('0', width - digits.len()));
257    out.push_str(&digits);
258    out
259}
260
261/// A template split into literals and Table 21 identifiers, with each
262/// identifier's format width.
263#[derive(Debug, Clone, PartialEq, Eq)]
264enum Part<'a> {
265    Literal(&'a str),
266    Escape,
267    RepresentationId,
268    Number(Option<usize>),
269    Time(Option<usize>),
270    Bandwidth(Option<usize>),
271}
272
273fn number_width(ident: &str) -> Option<usize> {
274    let (_, digits) = ident.split_once(TAG_START)?;
275    let digits = digits.strip_suffix(TAG_CONVERSION).unwrap_or(digits);
276    digits.parse().ok().map(|w: usize| w.min(MAX_FORMAT_WIDTH))
277}
278
279fn parts(template: &str) -> Result<Vec<Part<'_>>, TemplateFault> {
280    scan(template)?;
281    let mut out: Vec<Part<'_>> = Vec::new();
282    let mut rest = template;
283    while let Some(at) = rest.find(DELIMITER) {
284        if at > 0 {
285            out.push(Part::Literal(&rest[..at]));
286        }
287        let tail = &rest[at + 1..];
288        if let Some(after) = tail.strip_prefix(DELIMITER) {
289            out.push(Part::Escape);
290            rest = after;
291            continue;
292        }
293        let end = tail
294            .find(DELIMITER)
295            .ok_or(TemplateFault::UnterminatedIdentifier)?;
296        let ident = &tail[..end];
297        let name = match ident.split_once(TAG_START) {
298            Some((n, _)) => n,
299            None => ident,
300        };
301        out.push(match name {
302            IDENT_RESERVED => Part::RepresentationId,
303            IDENT_NUMBER => Part::Number(number_width(ident)),
304            IDENT_TIME => Part::Time(number_width(ident)),
305            IDENT_BANDWIDTH => Part::Bandwidth(number_width(ident)),
306            _ => return Err(TemplateFault::UnknownIdentifier),
307        });
308        rest = &tail[end + 1..];
309    }
310    if !rest.is_empty() {
311        out.push(Part::Literal(rest));
312    }
313    Ok(out)
314}
315
316/// The identifiers a URL was matched against a template: the exact inverse of
317/// [`substitute`].
318#[derive(Debug, Clone, PartialEq, Eq, Default)]
319#[non_exhaustive]
320pub struct TemplateMatch {
321    /// The matched `$RepresentationID$` value (empty if the template carried
322    /// none).
323    pub representation_id: String,
324    /// The matched `$Number$` value, if present.
325    pub number: Option<u64>,
326    /// The matched `$Time$` value, if present.
327    pub time: Option<u64>,
328    /// The matched `$Bandwidth$` value, if present.
329    pub bandwidth: Option<u64>,
330}
331
332/// Recover the identifiers that [`substitute`] would have rendered as `url`.
333///
334/// `known_representation_ids` supplies the values `$RepresentationID$` may
335/// take; they are tried longest-first and the whole `url` must match. Returns
336/// `None` when the template is invalid (any [`TemplateFault`]), when a
337/// `$SubNumber$` makes the reading undefined, or when the reading is not
338/// unique.
339#[must_use]
340pub fn match_url(
341    template: &str,
342    url: &str,
343    known_representation_ids: &[&str],
344) -> Option<TemplateMatch> {
345    let parts = parts(template).ok()?;
346    let mut ids: Vec<&str> = known_representation_ids.to_vec();
347    ids.sort_by(|a, b| b.len().cmp(&a.len()).then_with(|| a.cmp(b)));
348    ids.dedup();
349    let mut solutions: Vec<TemplateMatch> = Vec::new();
350    let search = Search {
351        parts: &parts,
352        ids: &ids,
353        url,
354    };
355    walk(&search, 0, 0, Reading::default(), &mut solutions);
356    if solutions.len() == 1 {
357        solutions.pop()
358    } else {
359        None
360    }
361}
362
363#[derive(Debug, Clone, Default)]
364struct Reading {
365    matched: TemplateMatch,
366    id: bool,
367    number: bool,
368    time: bool,
369    bandwidth: bool,
370}
371
372#[derive(Clone, Copy)]
373struct Search<'s, 'p> {
374    parts: &'s [Part<'p>],
375    ids: &'s [&'s str],
376    url: &'s str,
377}
378
379fn walk(
380    s: &Search<'_, '_>,
381    pi: usize,
382    pos: usize,
383    current: Reading,
384    solutions: &mut Vec<TemplateMatch>,
385) {
386    let Search {
387        parts, ids, url, ..
388    } = *s;
389    if solutions.len() >= 2 {
390        return;
391    }
392    let Some(part) = parts.get(pi) else {
393        if pos == url.len() {
394            solutions.push(current.matched);
395        }
396        return;
397    };
398    let rest = &url[pos..];
399    match part {
400        Part::Literal(lit) => {
401            if let Some(after) = rest.strip_prefix(*lit) {
402                let at = url.len() - after.len();
403                walk(s, pi + 1, at, current, solutions);
404            }
405        }
406        Part::Escape => {
407            if let Some(after) = rest.strip_prefix(DELIMITER) {
408                let at = url.len() - after.len();
409                walk(s, pi + 1, at, current, solutions);
410            }
411        }
412        Part::RepresentationId => {
413            for id in ids {
414                let Some(after) = rest.strip_prefix(*id) else {
415                    continue;
416                };
417                if current.id && current.matched.representation_id != *id {
418                    continue;
419                }
420                let mut next = current.clone();
421                next.id = true;
422                next.matched.representation_id = (*id).to_owned();
423                walk(s, pi + 1, url.len() - after.len(), next, solutions);
424                if solutions.len() >= 2 {
425                    return;
426                }
427            }
428        }
429        Part::Number(width) => numeric(s, pi, pos, *width, &current, solutions, Field::Number),
430        Part::Time(width) => numeric(s, pi, pos, *width, &current, solutions, Field::Time),
431        Part::Bandwidth(width) => {
432            numeric(s, pi, pos, *width, &current, solutions, Field::Bandwidth)
433        }
434    }
435}
436
437#[derive(Debug, Clone, Copy, PartialEq, Eq)]
438enum Field {
439    Number,
440    Time,
441    Bandwidth,
442}
443
444impl Reading {
445    fn set(&mut self, field: Field, value: u64) -> Option<&mut Self> {
446        let slot = match field {
447            Field::Number => &mut self.matched.number,
448            Field::Time => &mut self.matched.time,
449            Field::Bandwidth => &mut self.matched.bandwidth,
450        };
451        match *slot {
452            Some(seen) if seen != value => return None,
453            _ => *slot = Some(value),
454        }
455        match field {
456            Field::Number => self.number = true,
457            Field::Time => self.time = true,
458            Field::Bandwidth => self.bandwidth = true,
459        }
460        Some(self)
461    }
462}
463
464fn digit_run(rest: &str) -> usize {
465    rest.find(|c: char| !c.is_ascii_digit())
466        .unwrap_or(rest.len())
467}
468
469/// `n` zero-padded to `width` digits (5.3.9.4.4 `%0<width>d`), the width
470/// clamped to `1..=`[`MAX_FORMAT_WIDTH`].
471#[must_use]
472pub fn format_width(n: u64, width: usize) -> String {
473    let width = width.clamp(1, MAX_FORMAT_WIDTH);
474    let digits = n.to_string();
475    if digits.len() >= width {
476        digits
477    } else {
478        let mut out = String::with_capacity(width);
479        for _ in 0..(width - digits.len()) {
480            out.push('0');
481        }
482        out.push_str(&digits);
483        out
484    }
485}
486
487fn numeric(
488    s: &Search<'_, '_>,
489    pi: usize,
490    pos: usize,
491    width: Option<usize>,
492    current: &Reading,
493    solutions: &mut Vec<TemplateMatch>,
494    field: Field,
495) {
496    let rest = &s.url[pos..];
497    let max_len = digit_run(rest);
498    let w = width.map_or(1, |w| w.clamp(1, MAX_FORMAT_WIDTH));
499    let min_len = w.min(max_len).max(1);
500    if max_len == 0 || min_len > max_len {
501        return;
502    }
503    for len in (min_len..=max_len).rev() {
504        let Some(sub) = rest.get(..len) else {
505            continue;
506        };
507        let Ok(value) = sub.parse::<u64>() else {
508            continue;
509        };
510        if format_width(value, w) != sub {
511            continue;
512        }
513        let mut next = current.clone();
514        if next.set(field, value).is_none() {
515            continue;
516        }
517        walk(s, pi + 1, pos + len, next, solutions);
518        if solutions.len() >= 2 {
519            return;
520        }
521    }
522}
523
524#[cfg(test)]
525mod tests {
526    use super::{TemplateError, TemplateFault, substitute};
527
528    #[test]
529    fn time_template_without_a_time_is_an_error() {
530        assert_eq!(
531            substitute("chunk-$Time$.m4s", "r1", None, None, 1),
532            Err(TemplateError::MissingTime)
533        );
534        assert_eq!(
535            substitute("chunk-$Time$.m4s", "r1", Some(3), None, 1),
536            Err(TemplateError::MissingTime)
537        );
538    }
539
540    #[test]
541    fn number_template_without_a_number_is_an_error() {
542        assert_eq!(
543            substitute("chunk-$Number%05d$.m4s", "r1", None, None, 1),
544            Err(TemplateError::MissingNumber)
545        );
546        assert_eq!(
547            substitute("chunk-$Number%05d$.m4s", "r1", None, Some(3), 1),
548            Err(TemplateError::MissingNumber)
549        );
550    }
551
552    #[test]
553    fn invalid_template_is_an_error() {
554        assert_eq!(
555            substitute("chunk-$Number.m4s", "r1", Some(1), None, 1),
556            Err(TemplateError::Invalid(
557                TemplateFault::UnterminatedIdentifier
558            ))
559        );
560    }
561
562    #[test]
563    fn supplied_values_render() {
564        assert_eq!(
565            substitute("chunk-$Number%05d$-$Time$.m4s", "r1", Some(7), Some(11), 1),
566            Ok("chunk-00007-11.m4s".to_owned())
567        );
568        assert_eq!(
569            substitute("$RepresentationID$/init.mp4", "r1", None, None, 1),
570            Ok("r1/init.mp4".to_owned())
571        );
572    }
573}
broadcast_dash/template.rs

broadcast_dash/
template.rs
