/// An iterator that takes an input byte string and splits it into the words using the same syntax as
/// the POSIX shell.
pub struct Shlex<'a> {
    in_iter: core::slice::Iter<'a, u8>,
    /// The number of newlines read so far, plus one.
    pub line_no: usize,
    /// An input string is erroneous if it ends while inside a quotation or right after an
    /// unescaped backslash.  Since Iterator does not have a mechanism to return an error, if that
    /// happens, Shlex just throws out the last token, ends the iteration, and sets 'had_error' to
    /// true; best to check it after you're done iterating.
    pub had_error: bool,
}

impl<'a> Shlex<'a> {
    pub fn new(in_bytes: &'a [u8]) -> Self {
        Shlex {
            in_iter: in_bytes.iter(),
            line_no: 1,
            had_error: false,
        }
    }

    fn parse_word(&mut self, mut ch: u8) -> Option<Vec<u8>> {
        let mut result: Vec<u8> = Vec::new();
        loop {
            match ch as char {
                '"' => if let Err(()) = self.parse_double(&mut result) {
                    self.had_error = true;
                    return None;
                },
                '\'' => if let Err(()) = self.parse_single(&mut result) {
                    self.had_error = true;
                    return None;
                },
                '\\' => if let Some(ch2) = self.next_char() {
                    if ch2 != b'\n' { result.push(ch2); }
                } else {
                    self.had_error = true;
                    return None;
                },
                ' ' | '\t' | '\n' => { break; },
                _ => { result.push(ch); },
            }
            if let Some(ch2) = self.next_char() { ch = ch2; } else { break; }
        }
        Some(result)
    }

    fn parse_double(&mut self, result: &mut Vec<u8>) -> Result<(), ()> {
        loop {
            if let Some(ch2) = self.next_char() {
                match ch2 as char {
                    '\\' => {
                        if let Some(ch3) = self.next_char() {
                            match ch3 as char {
                                // \$ => $
                                '$' | '`' | '"' | '\\' => { result.push(ch3); },
                                // \<newline> => nothing
                                '\n' => {},
                                // \x => =x
                                _ => { result.push(b'\\'); result.push(ch3); }
                            }
                        } else {
                            return Err(());
                        }
                    },
                    '"' => { return Ok(()); },
                    _ => { result.push(ch2); },
                }
            } else {
                return Err(());
            }
        }
    }

    fn parse_single(&mut self, result: &mut Vec<u8>) -> Result<(), ()> {
        loop {
            if let Some(ch2) = self.next_char() {
                match ch2 as char {
                    '\'' => { return Ok(()); },
                    _ => { result.push(ch2); },
                }
            } else {
                return Err(());
            }
        }
    }

    fn next_char(&mut self) -> Option<u8> {
        let res = self.in_iter.next().copied();
        if res == Some(b'\n') { self.line_no += 1; }
        res
    }
}

impl Iterator for Shlex<'_> {
    type Item = Vec<u8>;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(mut ch) = self.next_char() {
            // skip initial whitespace
            loop {
                match ch as char {
                    ' ' | '\t' | '\n' => {},
                    '#' => {
                        while let Some(ch2) = self.next_char() {
                            if ch2 as char == '\n' { break; }
                        }
                    },
                    _ => { break; }
                }
                if let Some(ch2) = self.next_char() { ch = ch2; } else { return None; }
            }
            self.parse_word(ch)
        } else { // no initial character
            None
        }
    }

}

/// Is this ASCII byte okay to emit unquoted?
const fn unquoted_ok(c: u8) -> bool {
    match c as char {
        // Allowed characters:
        '+' | '-' | '.' | '/' | ':' | '@' | ']' | '_' |
        '0'..='9' | 'A'..='Z' | 'a'..='z'
        => true,

        // Non-allowed characters:
        // From POSIX https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html
        // "The application shall quote the following characters if they are to represent themselves:"
        '|' | '&' | ';' | '<' | '>' | '(' | ')' | '$' | '`' | '\\' | '"' | '\'' | ' ' | '\t' | '\n' |
        // "and the following may need to be quoted under certain circumstances[..]:"
        '*' | '?' | '[' | '#' | '~' | '=' | '%' |
        // Brace expansion.  These ought to be in the POSIX list but aren't yet;
        // see: https://www.austingroupbugs.net/view.php?id=1193
        '{' | '}' |
        // Also quote comma, just to be safe in the extremely odd case that the user of this crate
        // is intentionally placing a quoted string inside a brace expansion, e.g.:
        //     format!("echo foo{{a,b,{}}}" | shlex::quote(some_str))
        ',' |
        // '\r' is allowed in a word by all real shells I tested, but is treated as a word
        // separator by Python `shlex` | and might be translated to '\n' in interactive mode.
        '\r' |
        // '!' and '^' are treated specially in interactive mode; see quoting_warning.
        '!' | '^' |
        // Nul bytes and control characters.
        '\x00' ..= '\x1f' | '\x7f'
        => false,
        '\u{80}' ..= '\u{10ffff}' => {
            // This is unreachable since `unquoted_ok` is only called for 0..128.
            // Non-ASCII bytes are handled separately in `quoting_strategy`.
            // Can't call unreachable!() from `const fn` on old Rust, so...
            unquoted_ok(c)
        },
    }
    // Note: The logic cited above for quoting comma might suggest that `..` should also be quoted,
    // it as a special case of brace expansion).  But it's not necessary.  There are three cases:
    //
    // 1. The user wants comma-based brace expansion, but the untrusted string being `quote`d
    //    contains `..`, so they get something like `{foo,bar,3..5}`.
    //  => That's safe; both Bash and Zsh expand this to `foo bar 3..5` rather than
    //     `foo bar 3 4 5`.  The presence of commas disables sequence expression expansion.
    //
    // 2. The user wants comma-based brace expansion where the contents of the braces are a
    //    variable number of `quote`d strings and nothing else.  There happens to be exactly
    //    one string and it contains `..`, so they get something like `{3..5}`.
    //  => Then this will expand as a sequence expression, which is unintended.  But I don't mind,
    //     because any such code is already buggy.  Suppose the untrusted string *didn't* contain
    //     `,` or `..`, resulting in shell input like `{foo}`.  Then the shell would interpret it
    //     as the literal string `{foo}` rather than brace-expanding it into `foo`.
    //
    // 3. The user wants a sequence expression and wants to supply an untrusted string as one of
    //    the endpoints or the increment.
    //  => Well, that's just silly, since the endpoints can only be numbers or single letters.
}

/// Optimized version of `unquoted_ok`.
fn unquoted_ok_fast(c: u8) -> bool {
    const UNQUOTED_OK_MASK: u128 = {
        // Make a mask of all bytes in 0..<0x80 that pass.
        let mut c = 0u8;
        let mut mask = 0u128;
        while c < 0x80 {
            if unquoted_ok(c) {
                mask |= 1u128 << c;
            }
            c += 1;
        }
        mask
    };
    ((UNQUOTED_OK_MASK >> c) & 1) != 0
}

/// Is this ASCII byte okay to emit in single quotes?
fn single_quoted_ok(c: u8) -> bool {
    match c {
        // No single quotes in single quotes.
        b'\'' => false,
        // To work around a Bash bug, ^ is only allowed right after an opening single quote; see
        // quoting_warning.
        b'^' => false,
        // Backslashes in single quotes are literal according to POSIX, but Fish treats them as an
        // escape character.  Ban them.  Fish doesn't aim to be POSIX-compatible, but we *can*
        // achieve Fish compatibility using double quotes, so we might as well.
        b'\\' => false,
        _ => true
    }
}

/// Is this ASCII byte okay to emit in double quotes?
fn double_quoted_ok(c: u8) -> bool {
    match c {
        // Work around Python `shlex` bug where parsing "\`" and "\$" doesn't strip the
        // backslash, even though POSIX requires it.
        b'`' | b'$' => false,
        // '!' and '^' are treated specially in interactive mode; see quoting_warning.
        b'!' | b'^' => false,
        _ => true
    }
}

/// Given an input, return a quoting strategy that can cover some prefix of the string, along with
/// the size of that prefix.
///
/// Precondition: input size is nonzero.  (Empty strings are handled by the caller.)
/// Postcondition: returned size is nonzero.
#[cfg_attr(manual_codegen_check, inline(never))]
fn quoting_strategy(in_bytes: &[u8]) -> (usize, QuotingStrategy) {
    const UNQUOTED_OK: u8 = 1;
    const SINGLE_QUOTED_OK: u8 = 2;
    const DOUBLE_QUOTED_OK: u8 = 4;

    let mut prev_ok = SINGLE_QUOTED_OK | DOUBLE_QUOTED_OK | UNQUOTED_OK;
    let mut i = 0;

    if in_bytes[0] == b'^' {
        // To work around a Bash bug, ^ is only allowed right after an opening single quote; see
        // quoting_warning.
        prev_ok = SINGLE_QUOTED_OK;
        i = 1;
    }

    while i < in_bytes.len() {
        let c = in_bytes[i];
        let mut cur_ok = prev_ok;

        if c >= 0x80 {
            // Normally, non-ASCII characters shouldn't require quoting, but see quoting_warning.md
            // about \xa0.  For now, just treat all non-ASCII characters as requiring quotes.  This
            // also ensures things are safe in the off-chance that you're in a legacy 8-bit locale that
            // has additional characters satisfying `isblank`.
            cur_ok &= !UNQUOTED_OK;
        } else {
            if !unquoted_ok_fast(c) {
                cur_ok &= !UNQUOTED_OK;
            }
            if !single_quoted_ok(c){
                cur_ok &= !SINGLE_QUOTED_OK;
            }
            if !double_quoted_ok(c) {
                cur_ok &= !DOUBLE_QUOTED_OK;
            }
        }

        if cur_ok == 0 {
            // There are no quoting strategies that would work for both the previous characters and
            // this one.  So we have to end the chunk before this character.  The caller will call
            // `quoting_strategy` again to handle the rest of the string.
            break;
        }

        prev_ok = cur_ok;
        i += 1;
    }

    // Pick the best allowed strategy.
    let strategy = if prev_ok & UNQUOTED_OK != 0 {
        QuotingStrategy::Unquoted
    } else if prev_ok & SINGLE_QUOTED_OK != 0 {
        QuotingStrategy::SingleQuoted
    } else if prev_ok & DOUBLE_QUOTED_OK != 0 {
        QuotingStrategy::DoubleQuoted
    } else {
        unreachable!()
    };
    debug_assert!(i > 0);
    (i, strategy)
}

fn append_quoted_chunk(out: &mut Vec<u8>, cur_chunk: &[u8], strategy: QuotingStrategy) {
    match strategy {
        QuotingStrategy::Unquoted => {
            out.extend_from_slice(cur_chunk);
        },
        QuotingStrategy::SingleQuoted => {
            out.reserve(cur_chunk.len() + 2);
            out.push(b'\'');
            out.extend_from_slice(cur_chunk);
            out.push(b'\'');
        },
        QuotingStrategy::DoubleQuoted => {
            out.reserve(cur_chunk.len() + 2);
            out.push(b'"');
            for &c in cur_chunk.iter() {
                if let b'$' | b'`' | b'"' | b'\\' = c {
                    // Add a preceding backslash.
                    // Note: We shouldn't actually get here for $ and ` because they don't pass
                    // `double_quoted_ok`.
                    out.push(b'\\');
                }
                // Add the character itself.
                out.push(c);
            }
            out.push(b'"');
        },
    }
}

impl Iterator for Shlex<'_> {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        self.0.next().map(|byte_word| {
            // Safety: given valid UTF-8, bytes::Shlex will always return valid UTF-8.
            unsafe { String::from_utf8_unchecked(byte_word) }
        })
    }
}

    /// # Safety
    ///
    /// The parameter must have been constructed from valid UTF-8.
    pub unsafe fn from_bytes(bytes: bytes::Shlex<'a>) -> Self {
        Self(bytes)
    }

    /// # Safety
    ///
    /// If the returned reference is reassigned, the new [`bytes::Shlex`] must have been constructed from valid UTF-8.
    pub unsafe fn as_bytes_mut(&mut self) -> &mut bytes::Shlex<'a> {
        &mut self.0
    }
}