//! A URI reference resolved against a base and normalized (RFC 3986 §5.2, §6.2.2), so
//! that two spellings of one URL are one key (http-delivery §11.5): what a playlist lists
//! is bound by the URL it names, not by how a line happens to write it.
//!
//! Resolution is §5.2.2's strict algorithm, with §5.2.3's merge and §5.2.4's removal of
//! dot segments. Normalization is §6.2.2's: the scheme and the host in lower case, the
//! hexadecimal digits of a percent-encoding in upper case, a percent-encoded unreserved
//! character decoded, and dot segments removed again from the result. The fragment is
//! dropped: it names nothing the server holds. A base without a scheme is used as it is,
//! so that relative names still resolve relative to each other.

/// The five components of a reference (RFC 3986 Appendix B), each absent or present
/// (possibly empty).
#[derive(Clone, Debug, Default, PartialEq, Eq)]
struct Parts {
    scheme: Option<String>,
    authority: Option<String>,
    path: String,
    query: Option<String>,
}

/// Split `s` as Appendix B's expression does; the fragment is dropped.
fn split(s: &str) -> Parts {
    let s = s.split_once('#').map_or(s, |(a, _)| a);
    let mut rest = s;
    let mut p = Parts::default();
    if let Some(i) = rest.find([':', '/', '?']) {
        if rest.as_bytes()[i] == b':' && i > 0 {
            p.scheme = Some(rest[..i].to_string());
            rest = &rest[i + 1..];
        }
    }
    if let Some(r) = rest.strip_prefix("//") {
        let end = r.find(['/', '?']).unwrap_or(r.len());
        p.authority = Some(r[..end].to_string());
        rest = &r[end..];
    }
    match rest.split_once('?') {
        Some((path, q)) => {
            p.path = path.to_string();
            p.query = Some(q.to_string());
        }
        None => p.path = rest.to_string(),
    }
    p
}

/// §5.2.4: remove `.` and `..` segments.
fn remove_dot_segments(path: &str) -> String {
    let mut input = path;
    let mut out = String::with_capacity(path.len());
    while !input.is_empty() {
        if let Some(r) = input.strip_prefix("../") {
            input = r;
        } else if let Some(r) = input.strip_prefix("./") {
            input = r;
        } else if input.starts_with("/./") {
            input = &input[2..];
        } else if input == "/." {
            input = "/";
        } else if input.starts_with("/../") || input == "/.." {
            input = if input == "/.." { "/" } else { &input[3..] };
            match out.rfind('/') {
                Some(i) => out.truncate(i),
                None => out.clear(),
            }
        } else if input == "." || input == ".." {
            input = "";
        } else {
            let start = usize::from(input.starts_with('/'));
            let end = input[start..].find('/').map_or(input.len(), |i| i + start);
            out.push_str(&input[..end]);
            input = &input[end..];
        }
    }
    out
}

/// §5.2.3: merge a relative path with the base's.
fn merge(base: &Parts, path: &str) -> String {
    if base.authority.is_some() && base.path.is_empty() {
        format!("/{path}")
    } else {
        match base.path.rfind('/') {
            Some(i) => format!("{}{path}", &base.path[..=i]),
            None => path.to_string(),
        }
    }
}

/// §6.2.2.2: hexadecimal digits of a percent-encoding in upper case, and a
/// percent-encoded unreserved character decoded.
fn normalize_percent(s: &str) -> String {
    let b = s.as_bytes();
    let mut out = String::with_capacity(s.len());
    let mut i = 0;
    while i < b.len() {
        if b[i] == b'%' && i + 2 < b.len() && b[i + 1].is_ascii_hexdigit() && b[i + 2].is_ascii_hexdigit() {
            let v = u8::from_str_radix(&s[i + 1..i + 3], 16).expect("two hexadecimal digits");
            if v.is_ascii_alphanumeric() || b"-._~".contains(&v) {
                out.push(v as char);
            } else {
                out.push('%');
                out.push_str(&s[i + 1..i + 3].to_ascii_uppercase());
            }
            i += 3;
        } else {
            let c = s[i..].chars().next().expect("a character");
            out.push(c);
            i += c.len_utf8();
        }
    }
    out
}

/// `reference` resolved against `base` (§5.2.2) and normalized (§6.2.2), without its
/// fragment.
pub fn resolve(base: &str, reference: &str) -> String {
    let (b, r) = (split(base), split(reference));
    let t = if r.scheme.is_some() {
        Parts { scheme: r.scheme, authority: r.authority, path: remove_dot_segments(&r.path), query: r.query }
    } else if r.authority.is_some() {
        Parts { scheme: b.scheme, authority: r.authority, path: remove_dot_segments(&r.path), query: r.query }
    } else if r.path.is_empty() {
        Parts { scheme: b.scheme, authority: b.authority, path: b.path, query: r.query.or(b.query) }
    } else if r.path.starts_with('/') {
        Parts { scheme: b.scheme, authority: b.authority, path: remove_dot_segments(&r.path), query: r.query }
    } else {
        let merged = merge(&b, &r.path);
        Parts { scheme: b.scheme, authority: b.authority, path: remove_dot_segments(&merged), query: r.query }
    };
    let mut out = String::new();
    if let Some(s) = &t.scheme {
        out.push_str(&s.to_ascii_lowercase());
        out.push(':');
    }
    if let Some(a) = &t.authority {
        out.push_str("//");
        // The host (after any userinfo) in lower case.
        let a = normalize_percent(a);
        match a.rfind('@') {
            Some(i) => {
                out.push_str(&a[..=i]);
                out.push_str(&a[i + 1..].to_ascii_lowercase());
            }
            None => out.push_str(&a.to_ascii_lowercase()),
        }
    }
    out.push_str(&remove_dot_segments(&normalize_percent(&t.path)));
    if let Some(q) = &t.query {
        out.push('?');
        out.push_str(&normalize_percent(q));
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    /// RFC 3986 §5.4.1 and §5.4.2, every example, against its base.
    #[test]
    fn the_rfc_examples() {
        let base = "http://a/b/c/d;p?q";
        for (r, want) in [
            ("g:h", "g:h"), ("g", "http://a/b/c/g"), ("./g", "http://a/b/c/g"), ("g/", "http://a/b/c/g/"), ("/g", "http://a/g"),
            ("//g", "http://g"), ("?y", "http://a/b/c/d;p?y"), ("g?y", "http://a/b/c/g?y"), ("#s", "http://a/b/c/d;p?q"),
            ("g#s", "http://a/b/c/g"), ("g?y#s", "http://a/b/c/g?y"), (";x", "http://a/b/c/;x"), ("g;x", "http://a/b/c/g;x"),
            ("g;x?y#s", "http://a/b/c/g;x?y"), ("", "http://a/b/c/d;p?q"), (".", "http://a/b/c/"), ("./", "http://a/b/c/"),
            ("..", "http://a/b/"), ("../", "http://a/b/"), ("../g", "http://a/b/g"), ("../..", "http://a/"), ("../../", "http://a/"),
            ("../../g", "http://a/g"),
            ("../../../g", "http://a/g"), ("../../../../g", "http://a/g"), ("/./g", "http://a/g"), ("/../g", "http://a/g"),
            ("g.", "http://a/b/c/g."), (".g", "http://a/b/c/.g"), ("g..", "http://a/b/c/g.."), ("..g", "http://a/b/c/..g"),
            ("./../g", "http://a/b/g"), ("./g/.", "http://a/b/c/g/"), ("g/./h", "http://a/b/c/g/h"), ("g/../h", "http://a/b/c/h"),
            ("g;x=1/./y", "http://a/b/c/g;x=1/y"), ("g;x=1/../y", "http://a/b/c/y"), ("g?y/./x", "http://a/b/c/g?y/./x"),
            ("g?y/../x", "http://a/b/c/g?y/../x"), ("g#s/./x", "http://a/b/c/g"), ("g#s/../x", "http://a/b/c/g"), ("http:g", "http:g"),
        ] {
            assert_eq!(resolve(base, r), want, "{r:?}");
        }
    }

    /// Two spellings of one URL are one key; another URL is another.
    #[test]
    fn spellings_of_one_url() {
        let base = "https://Origin.Example/live/wai-720.m3u8";
        let key = resolve(base, "720/1201.0.wai#cid=00");
        assert_eq!(key, "https://origin.example/live/720/1201.0.wai");
        for same in ["./720/1201.0.wai", "../live/720/1201.0.wai", "/live/720/1201.0.wai", "720/./1201.0.wai", "720/x/../1201.0.wai",
                     "%37%32%30/1201.0.wai", "HTTPS://ORIGIN.EXAMPLE/live/720/1201.0.wai", "//origin.example/live/720/1201.0.wai",
                     "720/1201%2E0.wai", "720/%2E/1201.0.wai"] {
            assert_eq!(resolve(base, same), key, "{same:?}");
        }
        for other in ["720/1201.1.wai", "720/1201.0.wai?x", "720/1201%2e0.WAI", "../720/1201.0.wai", "720%2F1201.0.wai"] {
            assert_ne!(resolve(base, other), key, "{other:?}");
        }
        assert_eq!(resolve(base, "a%2fb%7e"), "https://origin.example/live/a%2Fb~");
        // A base with no scheme: names resolve relative to each other.
        assert_eq!(resolve("live/wai-720.m3u8", "./720/a.wai"), resolve("live/wai-720.m3u8", "720/a.wai"));
        assert_eq!(resolve("", "./720/a.wai"), "720/a.wai");
    }
}
