use std::ops::Range;

#[derive(Debug)]
pub struct Challenge {
    pub scheme: Range<usize>,
    pub realm: Option<Range<usize>>,
    pub scope: Option<Range<usize>>,
    pub service: Option<Range<usize>>,
}

#[derive(Default)]
pub struct PartialChallenge {
    pub scheme: Option<Range<usize>>,
    pub realm: Option<Range<usize>>,
    pub scope: Option<Range<usize>>,
    pub service: Option<Range<usize>>,
}

impl Into<Challenge> for PartialChallenge {
    fn into(self) -> Challenge {
        return Challenge {
            scheme: self.scheme.unwrap(),
            realm: self.realm,
            scope: self.scope,
            service: self.service,
        }
    }
}

// RFC 7230
fn parse_token(str: &Vec<char>, start: usize) -> Option<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(pos);
}

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, range: &mut Option<&mut Range<usize>>) -> Option<usize> {
    let mut pos = start;
    if str[pos] != '"' {
        return None;
    }
    pos += 1;

    range.as_mut().map(|x| x.start = pos);
    loop {
        if let Some(npos) = parse_qdtext(str, pos) {
            pos = npos;
        } else if let Some(npos) = parse_quotedpair(str, pos) {
            pos = npos;
        } else {
            break;
        }
    }
    range.as_mut().map(|x| x.end = pos);

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

    return Some(pos);
}

fn parse_sp(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_ows(str: &Vec<char>, start: usize) -> Option<usize> {
    // @COMPL: This is not right
    let mut pos = start;
    loop {
        match parse_sp(str, pos) {
            Some(npos) => pos = npos,
            None => break,
        }
    }

    return Some(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<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(pos);
}

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

    let mut value_range_slot = None;

    if let Some(npos) = parse_exact_string(str, pos, "realm") {
        partial.realm = Some(Range {
            ..Default::default()
        });
        value_range_slot = partial.realm.as_mut();
        pos = npos;
    } else if let Some(npos) = parse_exact_string(str, pos, "scope") {
        partial.scope = Some(Range {
            ..Default::default()
        });
        value_range_slot = partial.scope.as_mut();
        pos = npos;
    } else if let Some(npos) = parse_exact_string(str, pos, "service") {
        partial.service = Some(Range {
            ..Default::default()
        });
        value_range_slot = partial.service.as_mut();
        pos = npos;
    } else if let Some(npos) = parse_token(str, pos) {
        pos = npos;
    } else {
        return None;
    }

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

    value_range_slot.as_mut().map(|x| x.start = pos);
    if let Some(npos) = parse_token(str, pos) {
        value_range_slot.map(|x| x.end = npos);
        pos = npos;
    } else if let Some(npos) = parse_quotedstring(str, pos, &mut value_range_slot) {
        pos = npos;
    } else {
        todo!("{:?}", &str[pos..]);
    }

    return Some(pos);
}

pub fn parse_authenticate_header(header: &str) -> Option<Challenge> {
    let mut partial: PartialChallenge = Default::default();
    let data = header.chars().collect();

    parse_challenge(&data, 0, &mut partial)?;

    return Some(partial.into());
}

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

    {
        let mut scheme_range = Range {
            start: pos,
            ..Default::default()
        };

        pos = parse_token(str, pos).unwrap();

        scheme_range.end = pos;
        partial.scheme = Some(scheme_range);
    }

    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 pos = pos;
    loop {
        match parse_lws(str, pos) {
            Some(npos) => pos = npos,
            None => break,
        }
    }
    let pos = parse_param(str, pos, partial).unwrap();
    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, partial) {
            Some(npos) => {
                pos = npos;
            },
            None => return None,
        }
    }

    if pos < str.len() {
        return None;
    }
    return Some(pos);
}

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

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

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

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

fn parse_dec_octet(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_ipv4address(str: &Vec<char>, start: usize) -> Option<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(pos);
}

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

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

fn parse_scheme(str: &Vec<char>, start: usize) -> Option<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<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(pos);
}

fn parse_h16(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_ls32(str: &Vec<char>, start: usize) -> Option<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(npos);
            }
        }
    }

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

    return None;
}

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

    if let Some(npos) = parse_h16(str, start) {
        pos = Some(npos);
    } else {
        pos = Some(start);
    }

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

        break;
    }

    if let Some(npos) = parse_exact_string(str, pos.unwrap(), "::") {
        pos = Some(npos);
    } else {
        pos = None;
    }

    return pos;
}

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

    // 6( h16 ":" ) ls32
    if pos == start { // Just for symmetry, this is always true
        let mut tpos = Some(pos);

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

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

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None;
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // "::" 5( h16 ":" ) ls32
    if pos == start {
        let mut tpos;

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

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

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

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None;
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // [               h16 ] "::" 4( h16 ":" ) ls32
    if pos == start {
        let mut tpos;

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

        if let Some(npos) = parse_exact_string(str, tpos.unwrap(), "::") {
            tpos = Some(npos);
        } else {
            tpos = None;
        }

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

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

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None;
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // [ *1( h16 ":" ) h16 ] "::" 3( h16 ":" ) ls32
    // Implementing this parsing rule sucks. When reading the first repeating block ( h16 ":" ) we
    // have to speculatively read those two tokens, but we can't commit them since we don't know if
    // they're valid until we then read ANOTHER h16 followed by another colon, which can then of
    // course ALSO be part of the repetition if not followed by a second colon. I don't want to
    // write that lookahead/rollback code. Instead we can reformulate that production into:
    // [ h16 *1( ":" h16 ) ] "::" 3( h16 ":" ) ls32
    // This is much easier to implement, since we now just have to try and read a colon followed by
    // an h16, and if we don't find that fall through to the double colon or fail.
    // @COMPL We have to be a little careful, since this may interact differently with whitespace
    // and such, but that's for later.
    if pos == start {
        let mut tpos = parse_first_part_ipv6(str, pos, 1);

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

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

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // [ *2( h16 ":" ) h16 ] "::" 2( h16 ":" ) ls32
    if pos == start {
        let mut tpos = parse_first_part_ipv6(str, pos, 2);

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

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

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // [ *3( h16 ":" ) h16 ] "::"    h16 ":"   ls32
    if pos == start {
        let mut tpos = parse_first_part_ipv6(str, pos, 3);

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

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

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // [ *4( h16 ":" ) h16 ] "::"              ls32
    if pos == start {
        let mut tpos = parse_first_part_ipv6(str, pos, 4);

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_ls32(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    // [ *5( h16 ":" ) h16 ] "::"              h16
    if pos == start {
        let mut tpos = parse_first_part_ipv6(str, pos, 5);

        if let Some(ref mut tpos_val) = tpos {
            if let Some(npos) = parse_h16(str, *tpos_val) {
                *tpos_val = npos;
            } else {
                tpos = None
            }
        }

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    if pos == start {
        let tpos = parse_first_part_ipv6(str, pos, 6);

        if let Some(tpos_val) = tpos {
            pos = tpos_val;
        }
    }

    if pos == start {
        return None;
    }

    return Some(pos);
}

fn parse_ipvfuture(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_ip_literal(str: &Vec<char>, start: usize) -> Option<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(pos);
    }

    return None;
}

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

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

    return Some(pos);
}

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

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

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

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

    return None;
}

fn parse_userinfo(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_authority(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_relative_part_1(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_unreserved(str: &Vec<char>, start: usize) -> Option<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+1),
        _ => None
    }
}

fn parse_pct_encoded(str: &Vec<char>, start: usize) -> Option<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 + 3);
    }

    return None;
}

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

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

}

fn parse_pchar(str: &Vec<char>, start: usize) -> Option<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 + 1),
            _ => {}
        }
    }

    return None;
}

fn parse_segment_nz(str: &Vec<char>, start: usize) -> Option<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(pos);
}

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

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

    return Some(pos);
}

fn parse_path_absolute(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_path_abempty(str: &Vec<char>, start: usize) -> Option<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(pos);
}

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

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

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

    return None;
}

fn parse_query(str: &Vec<char>, start: usize) -> Option<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(pos);
}

fn parse_fragment(str: &Vec<char>, start: usize) -> Option<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(pos);
}

// RFC 3986
fn parse_relative_ref(str: &Vec<char>, start: usize) -> Option<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(pos);
}

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

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

    return Some(pos);
}

fn parse_exact_string(str: &Vec<char>, start: usize, to_match: &str) -> Option<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(pos);
}

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

    let mut is_rel = false;

    if let Some(npos) = parse_exact_string(str, pos, "rel") {
        is_rel = true;
        pos = npos;
    } else if let Some(npos) = parse_token(str, pos) {
        pos = npos;
    } else {
        return None;
    }

    // @CORRECT This part is actually supposed to be optional
    if let Some(npos) = parse_ows(str, pos) {
        pos = npos;
    }

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

    if let Some(npos) = parse_ows(str, pos) {
        pos = npos;
    }

    // @INCOMPLETE This is not exhaustive
    if is_rel && let Some(npos) = parse_exact_string(str, pos, "\"next\"") {
        res.found_next_uri = Some(res.current_uri.clone());
        pos = npos;
    } else if let Some(npos) = parse_token(str, pos) {
        pos = npos;
    } else if let Some(npos) = parse_quotedstring(str, pos, &mut None) {
        pos = npos;
    } else {
        return None;
    }

    return Some(pos);
}

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

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

    res.current_uri.start = pos;
    if let Some(npos) = parse_uri(str, pos) {
        pos = npos;
    } else if let Some(npos) = parse_relative_ref(str, pos) {
        pos = npos;
    } else {
        return None;
    }
    res.current_uri.end = pos;

    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(npos) = parse_ows(str, pos) {
            pos = npos;
        }

        if let Some(npos) = parse_link_param(str, pos, res) {
            pos = npos;
        } else {
            break;
        }
    }

    return Some(pos);
}

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

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

    let npos = parse_link_value(str, pos, res)?;
    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, res) {
            Some(npos) => {
                ipos = npos;
            },
            None => {
                break;
            },
        }

        pos = ipos;
    }


    return Some(pos);
}

#[derive(Default)]
struct PartialNextPage {
    current_uri: Range<usize>,

    found_next_uri: Option<Range<usize>>,
}

impl Into<NextPage> for PartialNextPage {
    fn into(self) -> NextPage {
        return NextPage {
            next_uri: self.found_next_uri,
        }
    }
}

pub struct NextPage {
    pub next_uri: Option<Range<usize>>
}

pub fn extract_next_page(header: &str) -> Option<NextPage> {
    let mut partial = Default::default();

    let data = header.chars().collect();

    parse_link_into(&data, 0, &mut partial)?;

    return Some(partial.into());
}