//! Reading an MPD (http-delivery §11.2, Appendix I): the XML subset this binding reads,
//! an MPD's periods and the segment timelines of their adaptation sets, and the DASH
//! adjacency check — a `wai.mpd` beside its classical MPD has the same `Period@id`s and
//! `@start`s, and each of its timelines has a classical timeline's timescale and lists
//! only that timeline's segments, each with its `t` and `d`, in order.
//!
//! A timeline is held as it is written, one run per `S` (`@t`, `@d`, and `@r` + 1
//! segments), never expanded: what a reader holds is bounded by the document's size,
//! whatever `@r` says, and timelines are compared run by run. A document holds at most
//! [`MAX_TIMELINES`] timelines, so comparing every WAI timeline with every classical one
//! is bounded too.
//!
//! The XML read is a subset of XML 1.0, stated in Appendix I, so that every conforming
//! reader refuses the same documents: no document type declaration, CDATA section or
//! processing instruction past the declaration; ASCII names; the five predefined
//! entities and character references to XML `Char`s; no attribute twice.

use super::hls::{decimal_ms, PlaylistError};

/// The most `SegmentTimeline`s a document holds (Appendix I); a document past it is
/// refused.
/// cbindgen:ignore
pub const MAX_TIMELINES: usize = 256;

/// The deepest element nesting read (Appendix I).
/// cbindgen:ignore
pub const MAX_DEPTH: usize = 64;

fn malformed(s: impl Into<String>) -> PlaylistError {
    PlaylistError::Malformed(s.into())
}

fn misaligned(s: impl Into<String>) -> PlaylistError {
    PlaylistError::Misaligned(s.into())
}

/// An element read: its name, its attributes in document order, and its child elements
/// (text is not kept).
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Element {
    pub name: String,
    pub attrs: Vec<(String, String)>,
    pub children: Vec<Element>,
}

impl Element {
    /// The name after its last `:`.
    pub fn local(&self) -> &str {
        self.name.rsplit(':').next().unwrap_or(&self.name)
    }

    pub fn attr(&self, name: &str) -> Option<&str> {
        self.attrs.iter().find(|(k, _)| k == name).map(|(_, v)| v.as_str())
    }

    fn children_named<'a>(&'a self, local: &'a str) -> impl Iterator<Item = &'a Element> + 'a {
        self.children.iter().filter(move |c| c.local() == local)
    }
}

/// Whether `c` is an XML `Char`.
pub fn xml_char(c: char) -> bool {
    matches!(c, '\t' | '\n' | '\r' | '\u{20}'..='\u{D7FF}' | '\u{E000}'..='\u{FFFD}' | '\u{10000}'..='\u{10FFFF}')
}

fn name_start(b: u8) -> bool {
    b.is_ascii_alphabetic() || b == b'_' || b == b':'
}

fn name_char(b: u8) -> bool {
    name_start(b) || b.is_ascii_digit() || b == b'-' || b == b'.'
}

struct Reader<'a> {
    s: &'a str,
    at: usize,
}

impl<'a> Reader<'a> {
    fn rest(&self) -> &'a str {
        &self.s[self.at..]
    }

    fn eat(&mut self, lit: &str) -> bool {
        if self.rest().starts_with(lit) {
            self.at += lit.len();
            true
        } else {
            false
        }
    }

    fn space(&mut self) -> bool {
        let n = self.rest().bytes().take_while(|b| matches!(b, b' ' | b'\t' | b'\n')).count();
        self.at += n;
        n > 0
    }

    fn name(&mut self) -> Result<String, PlaylistError> {
        let r = self.rest().as_bytes();
        if r.first().is_none_or(|&b| !name_start(b)) {
            return Err(malformed("a name"));
        }
        let n = r.iter().take_while(|&&b| name_char(b)).count();
        let out = self.rest()[..n].to_string();
        self.at += n;
        Ok(out)
    }

    /// A reference after its `&`, decoded.
    fn reference(&mut self) -> Result<char, PlaylistError> {
        let r = self.rest();
        let end = r.find(';').ok_or_else(|| malformed("an unterminated reference"))?;
        let body = &r[..end];
        let c = match body {
            "amp" => '&',
            "lt" => '<',
            "gt" => '>',
            "quot" => '"',
            "apos" => '\'',
            _ => {
                let n = if let Some(h) = body.strip_prefix("#x") {
                    (!h.is_empty() && h.len() <= 8 && h.bytes().all(|b| b.is_ascii_hexdigit())).then(|| u32::from_str_radix(h, 16).ok()).flatten()
                } else if let Some(d) = body.strip_prefix('#') {
                    (!d.is_empty() && d.len() <= 10 && d.bytes().all(|b| b.is_ascii_digit())).then(|| d.parse::<u32>().ok()).flatten()
                } else {
                    None
                };
                n.and_then(char::from_u32).filter(|&c| xml_char(c)).ok_or_else(|| malformed("a reference to an entity or character outside the subset"))?
            }
        };
        self.at += end + 1;
        Ok(c)
    }

    fn attr_value(&mut self) -> Result<String, PlaylistError> {
        let q = match self.rest().as_bytes().first() {
            Some(b'"') => '"',
            Some(b'\'') => '\'',
            _ => return Err(malformed("an attribute value is quoted")),
        };
        self.at += 1;
        let mut out = String::new();
        loop {
            let c = self.rest().chars().next().ok_or_else(|| malformed("an unterminated attribute value"))?;
            self.at += c.len_utf8();
            match c {
                _ if c == q => return Ok(out),
                '<' => return Err(malformed("< in an attribute value")),
                '&' => out.push(self.reference()?),
                // XML 1.0 §3.3.3: white space in a value is normalised to a space.
                '\t' | '\n' => out.push(' '),
                c => out.push(c),
            }
        }
    }

    /// Comments and white space; `false` at anything else.
    fn misc(&mut self) -> Result<(), PlaylistError> {
        loop {
            if self.space() {
                continue;
            }
            if self.rest().starts_with("<!--") {
                self.comment()?;
                continue;
            }
            return Ok(());
        }
    }

    fn comment(&mut self) -> Result<(), PlaylistError> {
        self.at += 4;
        let end = self.rest().find("--").ok_or_else(|| malformed("an unterminated comment"))?;
        if !self.rest()[end..].starts_with("-->") {
            return Err(malformed("-- inside a comment"));
        }
        self.at += end + 3;
        Ok(())
    }

    /// A start tag after its `<`: the element (children empty) and whether it closed
    /// itself.
    fn start_tag(&mut self) -> Result<(Element, bool), PlaylistError> {
        let name = self.name()?;
        let mut attrs: Vec<(String, String)> = Vec::new();
        // The names read so far, to refuse one twice in constant time per attribute.
        let mut names = std::collections::HashSet::new();
        loop {
            let spaced = self.space();
            if self.eat("/>") {
                return Ok((Element { name, attrs, children: Vec::new() }, true));
            }
            if self.eat(">") {
                return Ok((Element { name, attrs, children: Vec::new() }, false));
            }
            if !spaced {
                return Err(malformed("an attribute is preceded by white space"));
            }
            let k = self.name()?;
            self.space();
            if !self.eat("=") {
                return Err(malformed("an attribute has a value"));
            }
            self.space();
            let v = self.attr_value()?;
            if !names.insert(k.clone()) {
                return Err(malformed(format!("the attribute {k} twice")));
            }
            attrs.push((k, v));
        }
    }
}

/// Read an XML document in the subset of Appendix I: its root element.
pub fn read_xml(text: &str) -> Result<Element, PlaylistError> {
    // XML 1.0 §2.11: CR LF and a lone CR are read as LF.
    let normalised = text.strip_prefix('\u{FEFF}').unwrap_or(text).replace("\r\n", "\n").replace('\r', "\n");
    if let Some(c) = normalised.chars().find(|&c| !xml_char(c)) {
        return Err(malformed(format!("U+{:04X} is not an XML character", c as u32)));
    }
    let mut r = Reader { s: &normalised, at: 0 };
    if r.rest().starts_with("<?xml") && r.rest()[5..].starts_with([' ', '\t', '\n', '?']) {
        let end = r.rest().find("?>").ok_or_else(|| malformed("an unterminated declaration"))?;
        r.at += end + 2;
    }
    r.misc()?;
    if !r.eat("<") {
        return Err(malformed("no root element"));
    }
    let mut stack: Vec<Element> = Vec::new();
    let (root, closed) = r.start_tag()?;
    let mut done: Option<Element> = None;
    if closed {
        done = Some(root);
    } else {
        stack.push(root);
    }
    while done.is_none() {
        let c = r.rest().chars().next().ok_or_else(|| malformed("an element is not closed"))?;
        match c {
            '<' => {
                if r.rest().starts_with("<!--") {
                    r.comment()?;
                } else if r.eat("</") {
                    let name = r.name()?;
                    r.space();
                    if !r.eat(">") {
                        return Err(malformed("an end tag"));
                    }
                    let e = stack.pop().expect("an open element");
                    if e.name != name {
                        return Err(malformed(format!("</{name}> closes <{}>", e.name)));
                    }
                    match stack.last_mut() {
                        Some(parent) => parent.children.push(e),
                        None => done = Some(e),
                    }
                } else if r.rest().starts_with("<!") || r.rest().starts_with("<?") {
                    return Err(malformed("a declaration, CDATA section or processing instruction is outside the subset"));
                } else {
                    r.at += 1;
                    let (e, closed) = r.start_tag()?;
                    if closed {
                        stack.last_mut().expect("an open element").children.push(e);
                    } else {
                        if stack.len() >= MAX_DEPTH {
                            return Err(malformed("elements nested past the subset's depth"));
                        }
                        stack.push(e);
                    }
                }
            }
            '&' => {
                r.at += 1;
                r.reference()?;
            }
            _ => {
                if r.rest().starts_with("]]>") {
                    return Err(malformed("]]> in text"));
                }
                r.at += c.len_utf8();
            }
        }
    }
    r.misc()?;
    if !r.rest().is_empty() {
        return Err(malformed("content after the root element"));
    }
    Ok(done.expect("the root"))
}

/// An `xs:duration` of days, hours, minutes and seconds, in milliseconds (§11.2: the
/// seconds read exactly and rounded to the nearest millisecond, a half up). Years and
/// months have no length in milliseconds and are refused.
pub fn duration_ms(s: &str) -> Option<u64> {
    let rest = s.strip_prefix('P')?;
    let (date, time) = match rest.split_once('T') {
        Some((d, t)) => (d, Some(t)),
        None => (rest, None),
    };
    let mut ms: u64 = 0;
    let mut any = false;
    let int = |v: &str| -> Option<u64> { (!v.is_empty() && v.bytes().all(|b| b.is_ascii_digit())).then(|| v.parse().ok()).flatten() };
    if !date.is_empty() {
        let days = int(date.strip_suffix('D')?)?;
        ms = days.checked_mul(86_400_000)?;
        any = true;
    }
    if let Some(mut t) = time {
        if t.is_empty() {
            return None;
        }
        for (unit, scale) in [('H', 3_600_000u64), ('M', 60_000)] {
            if let Some(i) = t.find(unit) {
                ms = ms.checked_add(int(&t[..i])?.checked_mul(scale)?)?;
                t = &t[i + 1..];
                any = true;
            }
        }
        if !t.is_empty() {
            ms = ms.checked_add(decimal_ms(t.strip_suffix('S')?)?)?;
            any = true;
        }
    }
    any.then_some(ms)
}

/// One `S` of a timeline: `count` segments (`@r` + 1, at least 1) of `d` each, the
/// first at `t`.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Run {
    pub t: u64,
    pub d: u64,
    pub count: u64,
}

/// One segment timeline: its timescale and its runs, as written. Every segment's end is
/// at most 2^64 − 1.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Timeline {
    pub timescale: u64,
    pub runs: Vec<Run>,
}

impl Timeline {
    /// How many segments the timeline lists.
    pub fn segment_count(&self) -> u128 {
        self.runs.iter().map(|r| u128::from(r.count)).sum()
    }

    /// Each segment's `t` and `d`, expanded, when there are at most `max`; `None`
    /// otherwise, so that no expansion passes what the caller can hold.
    pub fn segments(&self, max: usize) -> Option<Vec<(u64, u64)>> {
        if self.segment_count() > max as u128 {
            return None;
        }
        let mut out = Vec::with_capacity(self.segment_count() as usize);
        for r in &self.runs {
            for i in 0..r.count {
                out.push((r.t + i * r.d, r.d));
            }
        }
        Some(out)
    }
}

/// An adaptation set's `@id` and the timelines it carries (its own, and each
/// representation's).
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SetTimelines {
    pub id: Option<String>,
    pub timelines: Vec<Timeline>,
}

/// A period's `@id`, its `@start` in milliseconds, and its adaptation sets.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PeriodTimelines {
    pub id: Option<String>,
    pub start_ms: u64,
    pub sets: Vec<SetTimelines>,
}

fn unsigned(v: &str, what: &str) -> Result<u64, PlaylistError> {
    if v.is_empty() || !v.bytes().all(|b| b.is_ascii_digit()) {
        return Err(malformed(format!("{what} is an unsigned integer")));
    }
    v.parse().map_err(|_| malformed(format!("{what} passes 2^64 - 1")))
}

/// The timeline of a `SegmentTemplate` or `SegmentList`, its timescale the first of its
/// own `@timescale` and those it inherits (`inherited`, nearest first), 1 when none is
/// given; `None` without a `SegmentTimeline`.
fn timeline_of(e: &Element, inherited: &[&Element]) -> Result<Option<Timeline>, PlaylistError> {
    let Some(st) = e.children_named("SegmentTimeline").next() else { return Ok(None) };
    let ts = std::iter::once(e).chain(inherited.iter().copied()).find_map(|x| x.attr("timescale"));
    let timescale = ts.map(|v| unsigned(v, "@timescale")).transpose()?.unwrap_or(1);
    if timescale == 0 {
        return Err(malformed("@timescale is 0"));
    }
    let mut runs = Vec::new();
    let mut next = 0u64;
    for s in st.children_named("S") {
        let d = unsigned(s.attr("d").ok_or_else(|| malformed("an S has no @d"))?, "@d")?;
        if d == 0 {
            return Err(malformed("an S of no duration"));
        }
        let t = s.attr("t").map(|v| unsigned(v, "@t")).transpose()?.unwrap_or(next);
        let r = s.attr("r").map(|v| unsigned(v, "@r")).transpose()?.unwrap_or(0);
        // The run's end, t + d·(r + 1), at most 2^64 − 1: computed, never expanded.
        let end = u128::from(t) + u128::from(d) * (u128::from(r) + 1);
        if end > u128::from(u64::MAX) {
            return Err(malformed("a segment time past 2^64 - 1"));
        }
        runs.push(Run { t, d, count: r + 1 });
        next = end as u64;
    }
    Ok(Some(Timeline { timescale, runs }))
}

const SEGMENT_INFO: [&str; 2] = ["SegmentTemplate", "SegmentList"];

/// An MPD's periods (Appendix I): each `Period`'s `@id` and `@start` (0 for the first
/// when absent; a later one without it is refused), and in each `AdaptationSet` its own
/// `SegmentTemplate` or `SegmentList` timeline and each `Representation`'s, a timescale
/// inherited from the set and the period. Refused (`playlist_malformed`) when it does
/// not read, its root is not `MPD`, it has no period, a timeline is not one, or it holds
/// more than [`MAX_TIMELINES`] timelines.
pub fn read_mpd(text: &str) -> Result<Vec<PeriodTimelines>, PlaylistError> {
    let root = read_xml(text)?;
    if root.local() != "MPD" {
        return Err(malformed("the root element is not MPD"));
    }
    let mut periods = Vec::new();
    let mut held = 0usize;
    let mut count = |timelines: &Vec<Timeline>| -> Result<(), PlaylistError> {
        held += timelines.len();
        if held > MAX_TIMELINES { Err(malformed("more SegmentTimelines than the subset's 256")) } else { Ok(()) }
    };
    for (i, p) in root.children_named("Period").enumerate() {
        let start_ms = match p.attr("start") {
            Some(v) => duration_ms(v).ok_or_else(|| malformed("a Period@start is not a duration of days, hours, minutes and seconds"))?,
            None if i == 0 => 0,
            None => return Err(malformed("a Period after the first has no @start")),
        };
        let p_info: Vec<&Element> = p.children.iter().filter(|c| SEGMENT_INFO.contains(&c.local())).collect();
        let mut sets = Vec::new();
        for a in p.children_named("AdaptationSet") {
            let mut timelines = Vec::new();
            let a_info: Vec<&Element> = a.children.iter().filter(|c| SEGMENT_INFO.contains(&c.local())).collect();
            for e in &a_info {
                let up: Vec<&Element> = p_info.iter().filter(|x| x.local() == e.local()).copied().collect();
                timelines.extend(timeline_of(e, &up)?);
            }
            for rep in a.children_named("Representation") {
                for e in rep.children.iter().filter(|c| SEGMENT_INFO.contains(&c.local())) {
                    let up: Vec<&Element> = a_info.iter().chain(p_info.iter()).filter(|x| x.local() == e.local()).copied().collect();
                    timelines.extend(timeline_of(e, &up)?);
                }
            }
            count(&timelines)?;
            sets.push(SetTimelines { id: a.attr("id").map(String::from), timelines });
        }
        periods.push(PeriodTimelines { id: p.attr("id").map(String::from), start_ms, sets });
    }
    if periods.is_empty() {
        return Err(malformed("an MPD with no Period"));
    }
    Ok(periods)
}

/// Whether `wai` lists only segments of `classical`, each with its `t` and `d`, in
/// order: for each WAI segment in turn, the first classical segment at or after the one
/// matched before with its `t` has its `d` too. Run by run, never expanded: each step
/// consumes a WAI run or a classical one, so the work is linear in the runs.
fn within(wai: &[Run], classical: &[Run]) -> bool {
    // The classical cursor: a run, and the segments of it already passed.
    let (mut ci, mut co) = (0usize, 0u128);
    for w in wai {
        let (mut t, mut left) = (u128::from(w.t), u128::from(w.count));
        while left > 0 {
            // The first classical segment at or after the cursor whose time is `t`.
            loop {
                let Some(c) = classical.get(ci) else { return false };
                let (ct, cd) = (u128::from(c.t), u128::from(c.d));
                if t >= ct + co * cd && (t - ct) % cd == 0 && (t - ct) / cd < u128::from(c.count) {
                    co = (t - ct) / cd;
                    break;
                }
                (ci, co) = (ci + 1, 0);
            }
            let c = &classical[ci];
            if c.d != w.d {
                return false;
            }
            let take = left.min(u128::from(c.count) - co);
            (left, co, t) = (left - take, co + take, t + take * u128::from(w.d));
            if co == u128::from(c.count) {
                (ci, co) = (ci + 1, 0);
            }
        }
    }
    true
}

/// §11.2 in DASH: `wai` (a `wai.mpd`) is adjacent to `classical` when each of its periods
/// has a classical period with the same `@id` and `@start`, and each timeline of each of
/// its adaptation sets is not empty and has the timescale of a timeline of that classical
/// period whose segments it lists only, each with its `t` and `d`, in order (a segment
/// left out is a gap). Refused `playlist_malformed` when either does not read, and
/// `adjacency_misaligned` otherwise.
pub fn check_dash_adjacent(wai: &str, classical: &str) -> Result<(), PlaylistError> {
    let w = read_mpd(wai)?;
    let k = read_mpd(classical)?;
    for wp in &w {
        let kp = k.iter().find(|p| p.id == wp.id).ok_or_else(|| misaligned(format!("no classical Period with the @id {:?}", wp.id)))?;
        if kp.start_ms != wp.start_ms {
            return Err(misaligned(format!("Period {:?} starts at {} ms, the classical one at {} ms", wp.id, wp.start_ms, kp.start_ms)));
        }
        if wp.sets.is_empty() {
            return Err(misaligned("a WAI Period with no AdaptationSet"));
        }
        for s in &wp.sets {
            if s.timelines.is_empty() {
                return Err(misaligned(format!("AdaptationSet {:?} has no SegmentTimeline", s.id)));
            }
            for tl in &s.timelines {
                let aligned = tl.segment_count() > 0
                    && kp.sets.iter().flat_map(|c| &c.timelines).any(|c| c.timescale == tl.timescale && within(&tl.runs, &c.runs));
                if !aligned {
                    return Err(misaligned(format!("a timeline of AdaptationSet {:?} is not a classical one's", s.id)));
                }
            }
        }
    }
    Ok(())
}
