use std::ops::Range;

#[derive(Debug)]
pub struct Challenge {
    pub scheme: Range<usize>,
    pub params: Vec<AuthParam>,
}

// RFC 7230
fn parse_token(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;
    while str.len() > pos {
        match str[pos] {
            // RFC 5234
            'a'..='z' | 'A'..='Z' => pos += 1,
            '0'..='9' => pos += 1,
            // RFC 7230
            '!' | '#' | '$' | '%' | '&' | '\'' | '*' | '+' | '-' | '.' | '^' | '_' | '`' | '|' | '~'
                => pos += 1,
            _ => break,
        }
    }

    // Must have matched 1
    if pos == start {
        return None;
    }

    return Some((start..pos, pos));
}

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

    #[test]
    fn rejects_nontchar() {
        let data = vec!['>'];

        let res = parse_token(&data, 0);
        assert!(res.is_none());
    }

    #[test]
    fn matches_letter() {
        let data = vec!['a'];

        let (range, pos) = parse_token(&data, 0).unwrap();
        assert_eq!(pos, 1);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 1);
    }

    #[test]
    fn matches_multiple_letters() {
        let data = vec!['a', '1', '|'];

        let (range, pos) = parse_token(&data, 0).unwrap();
        assert_eq!(pos, 3);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 3);
    }
}

fn parse_qdtext(str: &Vec<char>, start: usize) -> Option<usize> {
    match str[start] {
        '\x00'..='\x1F' | '"' | '\x7F' => return None,
        _ => return Some(start + 1),
    }
}

fn parse_quotedpair(str: &Vec<char>, start: usize) -> Option<usize> {
    if str[start] != '\\' {
        return None;
    }

    return Some(start + 2);
}

fn parse_quotedstring(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;
    if str[pos] != '"' {
        return None;
    }
    pos += 1;

    loop {
        if let Some(npos) = parse_qdtext(str, pos) {
            pos = npos;
        } else if let Some(npos) = parse_quotedpair(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }

    if str[pos] != '"' {
        return None;
    }
    pos += 1;

    return Some((start+1..pos-1, pos));
}

fn parse_sp(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    if str.len() <= start {
        return None;
    }

    let mut pos = start;
    match str[pos] {
        ' ' => pos += 1,
        _ => return None,
    }

    if pos == start {
        return None;
    }

    return Some((start..pos, pos));
}

fn parse_crlf(str: &Vec<char>, start: usize) -> Option<usize> {
    if str.len() - 2 < start {
        return None;
    }

    if str[start] == '\r' && str[start+1] == '\n' {
        return Some(start + 2);
    }

    return None;
}

fn parse_lws(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    match parse_crlf(str, pos) {
        Some(npos) => pos = npos,
        None => {},
    }

    match parse_sp(str, pos) {
        Some((_, npos)) => pos = npos,
        None => return None,
    }
    loop {
        match parse_sp(str, pos) {
            Some((_, npos)) => pos = npos,
            None => break,
        }
    }

    return Some((start..pos, pos));
}

#[derive(Debug)]
pub struct AuthParam {
    pub key: Range<usize>,
    pub value: Range<usize>,
}

fn parse_param(str: &Vec<char>, start: usize) -> Option<(AuthParam, usize)> {
    let pos = start;
    let (param_range, pos) = parse_token(str, pos)?;

    let mut pos = pos;
    if str[pos] == '=' {
        pos += 1;
    } else {
        todo!();
    }

    let value_range;
    if let Some((range, npos)) = parse_token(str, pos) {
        value_range = range;
        pos = npos;
    } else if let Some((range, npos)) = parse_quotedstring(str, pos) {
        value_range = range;
        pos = npos;
    } else {
        todo!("{:?}", &str[pos..]);
    }

    return Some((AuthParam{key: param_range, value: value_range}, pos));
}

pub fn parse_challenge(str: &Vec<char>, start: usize) -> Option<(Challenge, usize)> {
    let pos = start;
    let (scheme_range, pos) = parse_token(str, pos).unwrap();

    let (_, pos) = parse_sp(str, pos).unwrap();
    let mut pos = pos;
    loop {
        match parse_sp(str, pos) {
            Some((_, npos)) => pos = npos,
            None => break,
        }
    }

    let mut params = vec!();

    let mut pos = pos;
    loop {
        match parse_lws(str, pos) {
            Some((_, npos)) => pos = npos,
            None => break,
        }
    }
    let (param, pos) = parse_param(str, pos).unwrap();
    params.push(param);
    let mut pos = pos;
    loop {
        loop {
            match parse_lws(str, pos) {
                Some((_, npos)) => pos = npos,
                None => break,
            }
        }

        if pos >= str.len() || str[pos] != ',' {
            break;
        }
        pos += 1;

        loop {
            match parse_lws(str, pos) {
                Some((_, npos)) => pos = npos,
                None => break,
            }
        }

        match parse_param(str, pos) {
            Some((param, npos)) => {
                pos = npos;
                params.push(param);
            },
            None => return None,
        }
    }

    if pos < str.len() {
        return None;
    }
    return Some((Challenge {scheme: scheme_range, params}, pos));
}

#[derive(Debug)]
pub enum LinkParam {
    Rel{relation: Range<usize>},
}

impl LinkParam {
    pub fn value(&self) -> &Range<usize> {
        match self {
            LinkParam::Rel{relation} => &relation,
        }
    }
}

#[derive(Debug)]
pub struct LinkValue {
    uri: Range<usize>,
    pub params: Vec<LinkParam>,
}

fn parse_alpha(str: &Vec<char>, pos: usize) -> Option<(Range<usize>, usize)> {
    if pos >= str.len() {
        return None;
    }

    return match str[pos] {
        'a'..='z' | 'A'..='Z' => Some((pos..pos+1, pos+1)),
        _ => None,
    }
}

fn parse_digit(str: &Vec<char>, pos: usize) -> Option<(Range<usize>, usize)> {
    if pos >= str.len() {
        return None;
    }

    return match str[pos] {
        '0'..='9' => Some((pos..pos+1, pos+1)),
        _ => None,
    }
}

fn parse_dec_octet(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let mut len = 0;
    let mut value: u16 = 0;

    while len < 3 {
        if let Some((_, npos)) = parse_digit(str, pos) {
            value = value * 10 + (str[pos] as u16 - '0' as u16);
            pos = npos;
            len += 1;
        } else {
            break;
        }
    }

    if len == 0 {
        return None;
    }

    if len > 1 && str[start] == '0' {
        return None;
    }

    if value > 255 {
        return None;
    }

    return Some((start..pos, pos));
}

fn parse_ipv4address(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_dec_octet(str, pos)?;
    pos = npos;

    if let Some(ch) = str.get(pos) && *ch == '.' {
        pos += 1;
    } else {
        return None;
    }

    let (_, npos) = parse_dec_octet(str, pos)?;
    pos = npos;

    if let Some(ch) = str.get(pos) && *ch == '.' {
        pos += 1;
    } else {
        return None;
    }

    let (_, npos) = parse_dec_octet(str, pos)?;
    pos = npos;

    if let Some(ch) = str.get(pos) && *ch == '.' {
        pos += 1;
    } else {
        return None;
    }

    let (_, npos) = parse_dec_octet(str, pos)?;
    pos = npos;

    return Some((start..pos, pos));
}

fn parse_hexdig(str: &Vec<char>, pos: usize) -> Option<(Range<usize>, usize)> {
    if pos >= str.len() {
        return None;
    }

    return match str[pos] {
        '0'..='9' | 'A'..='F' | 'a'..='f' => Some((pos..pos+1, pos+1)),
        _ => None,
    }
}

fn parse_scheme(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_alpha(str, pos)?;
    pos = npos;

    loop {
        if let Some((_, npos)) = parse_alpha(str, pos) {
            pos = npos;
        } else {
            break;
        }
    };

    return None;
}

fn parse_reg_name(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    loop {
        if let Some((_, npos)) = parse_unreserved(str, pos) {
            pos = npos;
        } else if let Some((_, npos)) = parse_pct_encoded(str, pos) {
            pos = npos;
        } else if let Some((_, npos)) = parse_sub_delims(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_h16(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_hexdig(str, pos)?;
    pos = npos;

    for _ in 0..3 {
        if let Some((_, npos)) = parse_hexdig(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_ls32(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if let Some((_, npos)) = parse_h16(str, pos) {
        if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
            if let Some((_, npos)) = parse_h16(str, npos) {
                return Some((start..npos, npos));
            }
        }
    }

    if let Some((_, npos)) = parse_ipv4address(str, pos) {
        return Some((start..npos, npos));
    }

    return None;
}

fn parse_ipv6address(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    {
        let mut tpos = pos;
        for _ in 0..6 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // We fail the match, Rollback and stop
            tpos = pos;
            break;
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;
        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            for _ in 0..5 {
                if let Some((_, npos)) = parse_h16(str, tpos) {
                    if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                        tpos = npos;
                        continue;
                    }
                }

                // We fail the match, Rollback and stop
                tpos = pos;
                break;
            }
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            for _ in 0..4 {
                if let Some((_, npos)) = parse_h16(str, tpos) {
                    if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                        tpos = npos;
                        continue;
                    }
                }

                // We fail the match, Rollback and stop
                tpos = pos;
                break;
            }
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        for _ in 0..1 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // Match failed
            break;
        }

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            for _ in 0..3 {
                if let Some((_, npos)) = parse_h16(str, tpos) {
                    if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                        tpos = npos;
                        continue;
                    }
                }

                // We fail the match, Rollback and stop
                tpos = pos;
                break;
            }
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        for _ in 0..2 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // Match failed
            break;
        }

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            for _ in 0..2 {
                if let Some((_, npos)) = parse_h16(str, tpos) {
                    if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                        tpos = npos;
                        continue;
                    }
                }

                // We fail the match, Rollback and stop
                tpos = pos;
                break;
            }
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        for _ in 0..3 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // Match failed
            break;
        }

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            for _ in 0..1 {
                if let Some((_, npos)) = parse_h16(str, tpos) {
                    if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                        tpos = npos;
                        continue;
                    }
                }

                // We fail the match, Rollback and stop
                tpos = pos;
                break;
            }
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        for _ in 0..4 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // Match failed
            break;
        }

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_ls32(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        for _ in 0..5 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // Match failed
            break;
        }

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        if tpos != pos {
            // We successfully matched the last part
            if let Some((_, npos)) = parse_h16(str, tpos) {
                pos = npos;
            }
        }
    }

    if pos == start {
        let mut tpos = pos;

        for _ in 0..6 {
            if let Some((_, npos)) = parse_h16(str, tpos) {
                if let Some((_, npos)) = parse_exact_string(str, npos, ":") {
                    tpos = npos;
                    continue;
                }
            }

            // Match failed
            break;
        }

        if let Some((_, npos)) = parse_h16(str, tpos) {
            tpos = npos;
        }

        if let Some((_, npos)) = parse_exact_string(str, tpos, "::") {
            tpos = npos;
        } else {
            tpos = pos;
        }

        pos = tpos;
    }

    if pos == start {
        return None;
    }

    return Some((start..pos, pos));
}

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

    #[test]
    fn parses_full_ipv6address() {
        let data = "2001:0db8:85a3:0000:0000:8a2e:0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 39);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 39);
    }

    #[test]
    fn parses_7part_ipv6address() {
        let data = "::0db8:85a3:0000:0000:8a2e:0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 36);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 36);
    }

    #[test]
    fn parses_6part_ipv6address() {
        let data = "::85a3:0000:0000:8a2e:0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 31);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 31);
    }

    #[test]
    fn parses_5part_ipv6address() {
        let data = "::0000:0000:8a2e:0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 26);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 26);
    }

    #[test]
    fn parses_4part_ipv6address() {
        let data = "::0000:8a2e:0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 21);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 21);
    }

    #[test]
    fn parses_3part_ipv6address() {
        let data = "::8a2e:0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 16);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 16);
    }

    #[test]
    fn parses_2part_ipv6address() {
        let data = "::0370:7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 11);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 11);
    }

    #[test]
    fn parses_1part_ipv6address() {
        let data = "::7334".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 6);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 6);
    }

    #[test]
    fn parses_0part_ipv6address() {
        let data = "::".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 2);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 2);
    }

    #[test]
    fn parses_full_ipv6address_trailing_ipv4() {
        let data = "2001:0db8:85a3:0000:0000:8a2e:127.0.0.1".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 39);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 39);
    }

    #[test]
    fn parses_compressed_ipv6_loopback() {
        let data = "::1".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 3);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 3);
    }

    #[test]
    fn parses_ipv6_with_embedded_ipv4() {
        let data = "::ffff:192.0.2.128".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 18);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 18);
    }

    #[test]
    fn rejects_invalid_ipv6_hex() {
        let data = "2001:db8::g1".chars().collect();

        let res = parse_ipv6address(&data, 0);

        assert!(res.is_none());
    }

    #[test]
    fn rejects_multiple_compressions() {
        let data = "2001::85a3::7334".chars().collect();

        let res = parse_ipv6address(&data, 0);

        assert!(res.is_none());
    }

    #[test]
    fn rejects_too_many_segments() {
        let data = "1:2:3:4:5:6:7:8:9".chars().collect();

        let res = parse_ipv6address(&data, 0);

        assert!(res.is_none());
    }

    #[test]
    fn rejects_missing_segments_without_compression() {
        let data = "2001:db8:85a3:0:0:8a2e:370".chars().collect();

        let res = parse_ipv6address(&data, 0);

        assert!(res.is_none());
    }

    #[test]
    fn parses_trailing_compression() {
        let data = "2001:db8:85a3::".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 15);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 15);
    }

    #[test]
    fn parses_compressed_ipv6_with_ipv4_tail() {
        let data = "2001:db8::192.0.2.33".chars().collect();

        let (range, pos) = parse_ipv6address(&data, 0).unwrap();

        assert_eq!(pos, 21);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 21);
    }

    #[test]
    fn rejects_ipv4_tail_out_of_range() {
        let data = "2001::256.0.0.1".chars().collect();

        let res = parse_ipv6address(&data, 0);

        assert!(res.is_none());
    }
}


fn parse_ipvfuture(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_exact_string(str, pos, "v")?;
    pos = npos;

    let (_, npos) = parse_hexdig(str, pos)?;
    pos = npos;

    loop {
        if let Some((_, npos)) = parse_hexdig(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }

    let (_, npos) = parse_exact_string(str, pos, ".")?;
    pos = npos;

    if let Some((_, npos)) = parse_unreserved(str, pos) {
        pos = npos;
    } else if let Some((_, npos)) = parse_sub_delims(str, pos) {
        pos = npos;
    } else if let Some((_, npos)) = parse_exact_string(str, pos, ":") {
        pos = npos;
    } else {
        return None;
    }

    loop {
        if let Some((_, npos)) = parse_unreserved(str, pos) {
            pos = npos;
        } else if let Some((_, npos)) = parse_sub_delims(str, pos) {
            pos = npos;
        } else if let Some((_, npos)) = parse_exact_string(str, pos, ":") {
            pos = npos;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

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

    #[test]
    fn parses_ipvfuture_with_colons_and_subdelims() {
        let data = "vF.fe80::1-._~+!".chars().collect();

        let (range, pos) = parse_ipvfuture(&data, 0).unwrap();

        assert_eq!(pos, 16);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 16);
    }

    #[test]
    fn rejects_ipvfuture_missing_dot() {
        let data = "v1fe80::1".chars().collect();

        let res = parse_ipvfuture(&data, 0);

        assert!(res.is_none());
    }

    #[test]
    fn rejects_ipvfuture_with_percent_encoded() {
        let data = "v1.fe80::1%25".chars().collect();

        let (range, pos) = parse_ipvfuture(&data, 0).unwrap();

        assert_eq!(pos, 10);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 10);
    }
}


fn parse_ip_literal(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if let Some(ch) = str.get(pos) && *ch == '[' {
        pos += 1;
    } else {
        return None;
    }

    if let Some((_, npos)) = parse_ipv6address(str, pos) {
        pos = npos;
    } else if let Some((_, npos)) = parse_ipvfuture(str, pos) {
        pos = npos;
    } else {
        return None;
    }

    if let Some(ch) = str.get(pos) && *ch == ']' {
        pos += 1;
        return Some((start..pos, pos));
    }

    return None;
}

fn parse_port(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    while let Some(ch) = str.get(pos) {
        match ch {
            '0'..='9' => pos += 1,
            _ => break,
        }
    }

    return Some((start..pos, pos));
}

fn parse_host(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if let Some((_, npos)) = parse_ip_literal(str, pos) {
        pos = npos;
        return Some((start..pos, pos));
    }

    if let Some((_, npos)) = parse_ipv4address(str, pos) {
        pos = npos;
        return Some((start..pos, pos));
    }

    if let Some((_, npos)) = parse_reg_name(str, pos) {
        pos = npos;
        return Some((start..pos, pos));
    }

    return None;
}

fn parse_userinfo(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    loop {
        if let Some((_, npos)) = parse_unreserved(str, pos) {
            pos = npos;
        } else if let Some((_, npos)) = parse_pct_encoded(str, pos) {
            pos = npos;
        } else if let Some((_, npos)) = parse_sub_delims(str, pos) {
            pos = npos;
        } else if let Some(ch) = str.get(pos) && *ch == ':' {
            pos += 1;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_authority(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if let Some((_, npos)) = parse_userinfo(str, pos) {
        if let Some(ch) = str.get(npos) && *ch == '@' {
            pos = npos;
        }
    }
    // If the character after the userinfo isn't a @ we roll back that parse and try it as a host.

    if let Some((_, npos)) = parse_host(str, pos) {
        pos = npos;
    } else {
        return None;
    }

    if let Some(ch) = str.get(pos) && *ch == ':' {
        if let Some((_, npos)) = parse_port(str, pos+1) {
            pos = npos;
        } else {
            return None;
        }
    }

    return Some((start..pos, pos));
}

fn parse_relative_part_1(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if str[pos] != '/' || str[pos+1] != '/' {
        return None;
    }
    pos += 2;

    let (_, npos) = parse_authority(str, pos)?;
    pos = npos;

    let (_, npos) = parse_path_abempty(str, pos)?;
    pos = npos;

    return Some((start..pos, pos));
}

fn parse_unreserved(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    if let Some(x) = parse_alpha(str, start) {
        return Some(x);
    }

    if let Some(x) = parse_digit(str, start) {
        return Some(x);
    }

    if start >= str.len() {
        return None;
    }
    match str[start] {
        '-' | '.' | '_' | '~' => Some((start..start+1, start+1)),
        _ => None
    }
}

fn parse_pct_encoded(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    if start + 2 >= str.len() {
        return None;
    }

    if str[start] != '%' {
        return None;
    }

    let is_hexdig = |ch: char| matches!(ch, '0'..='9' | 'A'..='F' | 'a'..='f');

    if is_hexdig(str[start + 1]) && is_hexdig(str[start + 2]) {
        return Some((start..start + 3, start + 3));
    }

    return None;
}

fn parse_sub_delims(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    if start >= str.len() {
        return None;
    }

    match str[start] {
        '!' | '$' | '&' | '\'' | '(' | ')' | '*' | '+' | ',' | ';' | '=' => Some((start..start+1, start+1)),
        _ => None
    }

}

fn parse_pchar(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    if let Some(x) = parse_unreserved(str, start) {
        return Some(x);
    }

    if let Some(x) = parse_pct_encoded(str, start) {
        return Some(x);
    }

    if let Some(x) = parse_sub_delims(str, start) {
        return Some(x);
    }

    if let Some(ch) = str.get(start) {
        match ch {
            ':' | '@' => return Some((start..start + 1, start + 1)),
            _ => {}
        }
    }

    return None;
}

fn parse_segment_nz(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_pchar(str, pos)?;
    pos = npos;

    loop {
        if let Some((_, npos)) = parse_pchar(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_segment(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    loop {
        if let Some((_, npos)) = parse_pchar(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_path_absolute(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if str[pos] != '/' {
        return None;
    }
    pos += 1;

    if let Some((_, npos)) = parse_segment_nz(str, pos) {
        pos = npos;

        loop {
            if str[pos] != '/' {
                break;
            }

            if let Some((_, npos)) = parse_segment(str, pos+1) {
                pos = npos;
            } else {
                break;
            }
        }
    }

    return Some((start..pos, pos));
}

fn parse_path_abempty(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    loop {
        if let Some(ch) = str.get(pos) && *ch == '/' {
            if let Some((_, npos)) = parse_segment(str, pos+1) {
                pos = npos;
            } else {
                break;
            }
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_relative_part(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if let Some((_, npos)) = parse_relative_part_1(str, pos) {
        pos = npos;
        return Some((start..pos, pos));
    }

    if let Some((_, npos)) = parse_path_absolute(str, pos) {
        pos = npos;
        return Some((start..pos, pos));
    }

    return None;
}

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

    #[test]
    fn absolute_path() {
        let data = "/foo?".chars().collect();

        let (range, pos) = parse_relative_part(&data, 0).unwrap();
        assert_eq!(pos, 4);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 4);
    }
}

fn parse_query(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if start >= str.len() {
        return None;
    }

    loop {
        if let Some((_, npos)) = parse_pchar(str, pos) {
            pos = npos;
        } else if let Some(ch) = str.get(pos) && *ch == '/' {
            pos += 1;
        } else if let Some(ch) = str.get(pos) && *ch == '?' {
            pos += 1;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_fragment(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if start >= str.len() {
        return None;
    }

    loop {
        if let Some((_, npos)) = parse_pchar(str, pos) {
            pos = npos;
        } else if let Some(ch) = str.get(pos) && (*ch == '/' || *ch == '?') {
            pos += 1;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

// RFC 3986
fn parse_relative_ref(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_relative_part(str, pos)?;
    pos = npos;

    if let Some(ch) = str.get(pos) && *ch == '?' && let Some((_, npos)) = parse_query(str, pos+1) {
        pos = npos;
    }

    if let Some(ch) = str.get(pos) && *ch == '#' && let Some((_, npos)) = parse_fragment(str, pos+1) {
        pos = npos;
    }

    return Some((start..pos, pos));
}

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

    #[test]
    fn reject_not_starting_slash() {
        let data = vec!['?'];

        let res = parse_relative_ref(&data, 0);
        assert!(res.is_none());
    }

    #[test]
    fn simple() {
        let data = vec!['/', '/', 'h', 'e', 'l', 'l', 'o', '/'];

        let (range, pos) = parse_relative_ref(&data, 0).unwrap();
        assert_eq!(pos, 8);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 8);
    }

    #[test]
    fn with_query_parameter() {
        let data = "/foo?bar=baz".chars().collect();

        let (range, pos) = parse_relative_ref(&data, 0).unwrap();
        assert_eq!(pos, 12);
        assert_eq!(range.start, 0);
        assert_eq!(range.end, 12);
    }

    #[test]
    fn with_fragment() {
        let data = "/foo#frag".chars().collect();

        let (range, pos) = parse_relative_ref(&data, 0).unwrap();
        assert_eq!(pos, data.len());
        assert_eq!(range.start, 0);
        assert_eq!(range.end, data.len());
    }

    #[test]
    fn with_percent_encoded_fragment() {
        let data = "/foo#fr%20ag".chars().collect();

        let (range, pos) = parse_relative_ref(&data, 0).unwrap();
        assert_eq!(pos, data.len());
        assert_eq!(range.start, 0);
        assert_eq!(range.end, data.len());
    }
}

fn parse_uri(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let(_, npos) = parse_scheme(str, pos)?;
    pos = npos;

    return Some((start..pos, pos));
}

fn parse_exact_string(str: &Vec<char>, start: usize, to_match: &str) -> Option<(Range<usize>, usize)> {
    let mut pos = start;
    let end = pos + to_match.len();

    if end > str.len() {
        return None;
    }

    if !to_match.chars().eq(str[start..start+to_match.len()].iter().map(|x| *x)) {
        return None;
    }
    pos += to_match.len();

    return Some((start..pos, pos));
}

fn parse_loalpha(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    match str.get(start) {
        Some('a'..='z') => Some((start..start+1, start+1)),
        _ => None,
    }
}

fn parse_relation_type(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    let (_, npos) = parse_loalpha(str, pos)?;
    pos = npos;

    loop {
        if let Some((_, npos)) = parse_loalpha(str, pos) {
            pos = npos;
            continue;
        } else if let Some((_, npos)) = parse_digit(str, pos) {
            pos = npos;
            continue;
        } else if let Some((_, npos)) = parse_exact_string(str, pos, ".") {
            pos = npos;
            continue;
        } else if let Some((_, npos)) = parse_exact_string(str, pos, "-") {
            pos = npos;
            continue;
        } else {
            break;
        }
    }

    return Some((start..pos, pos));
}

fn parse_relation_types(str: &Vec<char>, start: usize) -> Option<(Range<usize>, usize)> {
    let mut pos = start;

    if let Some((_, npos)) = parse_relation_type(str, pos) {
        pos = npos;

        return Some((start..pos, pos));
    } else if let Some((_, npos)) = parse_exact_string(str, pos, "\"") {
        pos = npos;

        if let Some((_, npos)) = parse_relation_type(str, pos) {
            pos = npos;

            loop {
                if let Some((_, npos)) = parse_sp(str, pos) {

                    loop {
                        if let Some((_, npos)) = parse_sp(str, pos) {
                            pos = npos;
                        } else {
                            break;
                        }
                    }

                    pos = npos;
                    if let Some((_, npos)) = parse_relation_type(str, pos) {
                        pos = npos;
                        continue;
                    }
                }
                break;
            }

            if let Some((_, npos)) = parse_exact_string(str, pos, "\"") {
                pos = npos;
                return Some((start+1..pos-1, pos));
            }
        }
    }

    return None;
}

fn parse_link_param(str: &Vec<char>, start: usize) -> Option<(LinkParam, usize)> {
    let mut pos = start;

    // Non-standard but seen in the wild
    if let Some((_, npos)) = parse_sp(str, pos) {
        pos = npos;
    }

    if let Some((_, npos)) = parse_exact_string(str, pos, "rel=") {
        if let Some((relation, npos)) = parse_relation_types(str, npos) {
            pos = npos;
            return Some((LinkParam::Rel{relation}, pos));
        }
    }

    return None;
}

fn parse_link_value(str: &Vec<char>, start: usize) -> Option<(LinkValue, usize)> {
    let mut pos = start;

    if let Some((_, npos)) = parse_exact_string(str, pos, "<") {
        pos = npos;
    } else {
        return None;
    }

    let uri_range;
    let mut params = vec!();

    if let Some((range, npos)) = parse_uri(str, pos) {
        uri_range = range;
        pos = npos;
    } else if let Some((range, npos)) = parse_relative_ref(str, pos) {
        uri_range = range;
        pos = npos;
    } else {
        return None;
    }

    if let Some((_, npos)) = parse_exact_string(str, pos, ">") {
        pos = npos;
    } else {
        return None;
    }

    loop {
        if let Some((_, npos)) = parse_exact_string(str, pos, ";") {
            pos = npos;
        } else {
            break;
        }

        if let Some((param, npos)) = parse_link_param(str, pos) {
            pos = npos;
            params.push(param);
        } else {
            break;
        }
    }

    return Some((LinkValue{ uri: uri_range, params: params }, pos));
}

pub fn parse_link(str: &Vec<char>, start: usize) -> Option<(Vec<LinkValue>, usize)> {
    let mut pos = start;

    let mut values = vec!();

    loop {
        match parse_lws(str, pos) {
            Some((_, npos)) => pos = npos,
            None => break,
        }
    }

    let (param, npos) = parse_link_value(str, pos)?;
    values.push(param);
    pos = npos;

    loop {
        let mut ipos = pos;
        loop {
            match parse_lws(str, ipos) {
                Some((_, npos)) => ipos = npos,
                None => break,
            }
        }

        if ipos >= str.len() || str[ipos] != ',' {
            break;
        }
        ipos += 1;

        loop {
            match parse_lws(str, ipos) {
                Some((_, npos)) => ipos = npos,
                None => break,
            }
        }

        match parse_link_value(str, ipos) {
            Some((param, npos)) => {
                ipos = npos;
                values.push(param);
            },
            None => {
                break;
            },
        }

        pos = ipos;
    }


    return Some((values, pos));
}

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

    #[test]
    fn parses_relative_authority_only() {
        let data: Vec<char> = "<//example.com>".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 15);
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].uri, 1..14);
        assert_eq!(links[0].params.len(), 0);
    }

    #[test]
    fn parses_relative_absolute_path() {
        let data: Vec<char> = "</path/to/resource>".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 19);
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].uri, 1..18);
    }

    #[test]
    fn parses_relative_with_query() {
        let data: Vec<char> = "</foo?bar=baz>".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 14);
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].uri, 1..13);
    }

    #[test]
    fn parses_rel_param_unquoted() {
        let data: Vec<char> = "<//example.com>; rel=preconnect".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 31);

        match &links[0].params[0] {
            LinkParam::Rel { relation } => {
                assert_eq!(relation.clone(), 21..31);
            }
            _ => assert!(false),
        }
    }

    #[test]
    fn parses_multiple_links_with_lws() {
        let data: Vec<char> = "<//a>; rel=preconnect, <//b>".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 28);
        assert_eq!(links.len(), 2);

        match &links[0].params[0] {
            LinkParam::Rel { relation } => {
                assert_eq!(relation.clone(), 11..21);
            }
        }

        assert_eq!(links[1].params.len(), 0);
        assert_eq!(links[0].uri, 1..4);
        assert_eq!(links[1].uri, 24..27);
    }

    #[test]
    fn parses_lws_between_link_values() {
        let data: Vec<char> = "<//a>,\r\n <//b>".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 14);
        assert_eq!(links.len(), 2);
        assert_eq!(links[0].uri, 1..4);
        assert_eq!(links[1].uri, 10..13);
    }

    #[test]
    // Is this correct?
    fn rejects_absolute_uri() {
        let data: Vec<char> = "<http://example.com>".chars().collect();

        let res = parse_link(&data, 0);
        assert!(res.is_none());
    }

    #[test]
    fn rejects_missing_closing_delimiter() {
        let data: Vec<char> = "<//example.com".chars().collect();

        let res = parse_link(&data, 0);
        assert!(res.is_none());
    }

    #[test]
    fn parses_quoted_rel_multiple_values() {
        let data: Vec<char> = "<//example.com>; rel=\"preconnect dns-prefetch\"".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, data.len());
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].params.len(), 1);

        match &links[0].params[0] {
            LinkParam::Rel { relation } => {
                assert_eq!(relation.clone(), 22..45);
            }
        }
    }

    #[test]
    #[ignore = "absolute URI targets are not parsed yet"]
    fn parses_absolute_uri_with_rel() {
        let data: Vec<char> = "<http://example.com>; rel=preconnect".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 35);
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].uri, 1..19);
        match &links[0].params[0] {
            LinkParam::Rel { relation } => assert_eq!(relation.clone(), 22..32),
        }
    }

    #[test]
    #[ignore = "additional parameters beyond rel= are not parsed"]
    fn parses_title_parameter() {
        let data: Vec<char> = "<//example.com>; rel=preconnect; title=\"Example\"".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 57);
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].params.len(), 2);
    }

    #[test]
    #[ignore = "extended title* parameter not supported"]
    fn parses_title_star_parameter() {
        let data: Vec<char> = "<//example.com>; rel=preconnect; title*=UTF-8''Ex%C3%A4mple".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 65);
        assert_eq!(links.len(), 1);
    }

    #[test]
    #[ignore = "anchor parameter not parsed"]
    fn parses_anchor_parameter() {
        let data: Vec<char> = "<//example.com>; rel=preconnect; anchor=\"/base\"".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 56);
        assert_eq!(links.len(), 1);
    }

    #[test]
    #[ignore = "hreflang parameter not parsed"]
    fn parses_hreflang_parameter() {
        let data: Vec<char> = "<//example.com>; rel=preconnect; hreflang=en".chars().collect();

        let (links, pos) = parse_link(&data, 0).unwrap();

        assert_eq!(pos, 53);
        assert_eq!(links.len(), 1);
    }

    #[test]
    fn rejects_percent_encoded_path() {
        let data: Vec<char> = "</pa%20th>".chars().collect();

        let res = parse_link(&data, 0);
        assert!(res.is_some());
    }
}