use std::io::{self, Read};

#[derive(Debug, PartialEq)]
enum Json {
    Null,
    Bool(bool),
    Number(String),
    String(String),
    Array(Vec<Json>),
    Object(Vec<(String, Json)>),
}

struct Parser<'a> {
    input: &'a [u8],
    pos: usize,
}

impl<'a> Parser<'a> {
    fn new(input: &'a str) -> Self {
        Self {
            input: input.as_bytes(),
            pos: 0,
        }
    }

    fn parse(mut self) -> Result<Json, String> {
        let value = self.value()?;
        self.whitespace();
        if self.pos != self.input.len() {
            return Err(self.error("unexpected trailing input"));
        }
        Ok(value)
    }

    fn value(&mut self) -> Result<Json, String> {
        self.whitespace();
        match self.peek() {
            Some(b'n') => {
                self.literal(b"null")?;
                Ok(Json::Null)
            }
            Some(b't') => {
                self.literal(b"true")?;
                Ok(Json::Bool(true))
            }
            Some(b'f') => {
                self.literal(b"false")?;
                Ok(Json::Bool(false))
            }
            Some(b'"') => Ok(Json::String(self.string()?)),
            Some(b'[') => self.array(),
            Some(b'{') => self.object(),
            Some(b'-' | b'0'..=b'9') => Ok(Json::Number(self.number()?)),
            Some(_) => Err(self.error("expected a JSON value")),
            None => Err(self.error("unexpected end of input")),
        }
    }

    fn array(&mut self) -> Result<Json, String> {
        self.pos += 1;
        let mut items = Vec::new();
        self.whitespace();

        if self.consume(b']') {
            return Ok(Json::Array(items));
        }

        loop {
            items.push(self.value()?);
            self.whitespace();
            if self.consume(b']') {
                break;
            }
            if !self.consume(b',') {
                return Err(self.error("expected ',' or ']'"));
            }
        }
        Ok(Json::Array(items))
    }

    fn object(&mut self) -> Result<Json, String> {
        self.pos += 1;
        let mut fields = Vec::new();
        self.whitespace();

        if self.consume(b'}') {
            return Ok(Json::Object(fields));
        }

        loop {
            self.whitespace();
            if self.peek() != Some(b'"') {
                return Err(self.error("expected an object key"));
            }
            let key = self.string()?;
            self.whitespace();
            if !self.consume(b':') {
                return Err(self.error("expected ':'"));
            }
            fields.push((key, self.value()?));
            self.whitespace();
            if self.consume(b'}') {
                break;
            }
            if !self.consume(b',') {
                return Err(self.error("expected ',' or '}'"));
            }
        }
        Ok(Json::Object(fields))
    }

    fn string(&mut self) -> Result<String, String> {
        self.pos += 1; // Opening quote.
        let mut output = String::new();

        loop {
            let byte = self.next().ok_or_else(|| self.error("unterminated string"))?;
            match byte {
                b'"' => return Ok(output),
                b'\\' => match self.next() {
                    Some(b'"') => output.push('"'),
                    Some(b'\\') => output.push('\\'),
                    Some(b'/') => output.push('/'),
                    Some(b'b') => output.push('\u{0008}'),
                    Some(b'f') => output.push('\u{000c}'),
                    Some(b'n') => output.push('\n'),
                    Some(b'r') => output.push('\r'),
                    Some(b't') => output.push('\t'),
                    Some(b'u') => {
                        let first = self.hex_escape()?;
                        let code = if (0xD800..=0xDBFF).contains(&first) {
                            if self.next() != Some(b'\\') || self.next() != Some(b'u') {
                                return Err(self.error("expected a low surrogate"));
                            }
                            let second = self.hex_escape()?;
                            if !(0xDC00..=0xDFFF).contains(&second) {
                                return Err(self.error("invalid low surrogate"));
                            }
                            0x10000 + ((first - 0xD800) << 10) + (second - 0xDC00)
                        } else if (0xDC00..=0xDFFF).contains(&first) {
                            return Err(self.error("unexpected low surrogate"));
                        } else {
                            first
                        };
                        output.push(
                            char::from_u32(code)
                                .ok_or_else(|| self.error("invalid Unicode escape"))?,
                        );
                    }
                    _ => return Err(self.error("invalid string escape")),
                },
                0x00..=0x1f => return Err(self.error("control character in string")),
                0x20..=0x7f => output.push(byte as char),
                _ => {
                    // Copy one complete UTF-8 character.
                    let start = self.pos - 1;
                    let tail = std::str::from_utf8(&self.input[start..])
                        .map_err(|_| self.error("invalid UTF-8"))?;
                    let ch = tail.chars().next().unwrap();
                    output.push(ch);
                    self.pos = start + ch.len_utf8();
                }
            }
        }
    }

    fn hex_escape(&mut self) -> Result<u32, String> {
        let mut value = 0;
        for _ in 0..4 {
            let digit = self
                .next()
                .and_then(|b| (b as char).to_digit(16))
                .ok_or_else(|| self.error("invalid Unicode escape"))?;
            value = value * 16 + digit;
        }
        Ok(value)
    }

    fn number(&mut self) -> Result<String, String> {
        let start = self.pos;
        self.consume(b'-');

        match self.next() {
            Some(b'0') => {
                if matches!(self.peek(), Some(b'0'..=b'9')) {
                    return Err(self.error("leading zero in number"));
                }
            }
            Some(b'1'..=b'9') => {
                while matches!(self.peek(), Some(b'0'..=b'9')) {
                    self.pos += 1;
                }
            }
            _ => return Err(self.error("invalid number")),
        }

        if self.consume(b'.') {
            if !matches!(self.peek(), Some(b'0'..=b'9')) {
                return Err(self.error("expected digit after decimal point"));
            }
            while matches!(self.peek(), Some(b'0'..=b'9')) {
                self.pos += 1;
            }
        }

        if matches!(self.peek(), Some(b'e' | b'E')) {
            self.pos += 1;
            if matches!(self.peek(), Some(b'+' | b'-')) {
                self.pos += 1;
            }
            if !matches!(self.peek(), Some(b'0'..=b'9')) {
                return Err(self.error("expected exponent digits"));
            }
            while matches!(self.peek(), Some(b'0'..=b'9')) {
                self.pos += 1;
            }
        }

        Ok(std::str::from_utf8(&self.input[start..self.pos])
            .unwrap()
            .to_owned())
    }

    fn literal(&mut self, literal: &[u8]) -> Result<(), String> {
        if self.input.get(self.pos..self.pos + literal.len()) == Some(literal) {
            self.pos += literal.len();
            Ok(())
        } else {
            Err(self.error("invalid literal"))
        }
    }

    fn whitespace(&mut self) {
        while matches!(self.peek(), Some(b' ' | b'\n' | b'\r' | b'\t')) {
            self.pos += 1;
        }
    }

    fn consume(&mut self, byte: u8) -> bool {
        if self.peek() == Some(byte) {
            self.pos += 1;
            true
        } else {
            false
        }
    }

    fn peek(&self) -> Option<u8> {
        self.input.get(self.pos).copied()
    }

    fn next(&mut self) -> Option<u8> {
        let byte = self.peek()?;
        self.pos += 1;
        Some(byte)
    }

    fn error(&self, message: &str) -> String {
        format!("{message} at byte {}", self.pos)
    }
}

fn pretty(value: &Json) -> String {
    let mut output = String::new();
    write_json(value, 0, &mut output);
    output
}

fn write_json(value: &Json, depth: usize, output: &mut String) {
    match value {
        Json::Null => output.push_str("null"),
        Json::Bool(value) => output.push_str(if *value { "true" } else { "false" }),
        Json::Number(value) => output.push_str(value),
        Json::String(value) => write_string(value, output),
        Json::Array(items) => {
            if items.is_empty() {
                output.push_str("[]");
                return;
            }
            output.push_str("[\n");
            for (index, item) in items.iter().enumerate() {
                indent(depth + 1, output);
                write_json(item, depth + 1, output);
                if index + 1 != items.len() {
                    output.push(',');
                }
                output.push('\n');
            }
            indent(depth, output);
            output.push(']');
        }
        Json::Object(fields) => {
            if fields.is_empty() {
                output.push_str("{}");
                return;
            }
            output.push_str("{\n");
            for (index, (key, value)) in fields.iter().enumerate() {
                indent(depth + 1, output);
                write_string(key, output);
                output.push_str(": ");
                write_json(value, depth + 1, output);
                if index + 1 != fields.len() {
                    output.push(',');
                }
                output.push('\n');
            }
            indent(depth, output);
            output.push('}');
        }
    }
}

fn write_string(value: &str, output: &mut String) {
    output.push('"');
    for ch in value.chars() {
        match ch {
            '"' => output.push_str("\\\""),
            '\\' => output.push_str("\\\\"),
            '\u{0008}' => output.push_str("\\b"),
            '\u{000c}' => output.push_str("\\f"),
            '\n' => output.push_str("\\n"),
            '\r' => output.push_str("\\r"),
            '\t' => output.push_str("\\t"),
            '\u{0000}'..='\u{001f}' => {
                output.push_str(&format!("\\u{:04x}", ch as u32));
            }
            _ => output.push(ch),
        }
    }
    output.push('"');
}

fn indent(depth: usize, output: &mut String) {
    for _ in 0..depth {
        output.push_str("  ");
    }
}

fn main() {
    let mut input = String::new();
    if let Err(error) = io::stdin().read_to_string(&mut input) {
        eprintln!("failed to read input: {error}");
        std::process::exit(1);
    }

    match Parser::new(&input).parse() {
        Ok(value) => println!("{}", pretty(&value)),
        Err(error) => {
            eprintln!("invalid JSON: {error}");
            std::process::exit(1);
        }
    }
}

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

    #[test]
    fn formats_nested_json() {
        let value = Parser::new(r#"{"name":"Ada","values":[1,true,null]}"#)
            .parse()
            .unwrap();

        assert_eq!(
            pretty(&value),
            "{\n  \"name\": \"Ada\",\n  \"values\": [\n    1,\n    true,\n    null\n  ]\n}"
        );
    }

    #[test]
    fn handles_escapes_and_rejects_bad_numbers() {
        let value = Parser::new(r#""line\n\uD83D\uDE80""#).parse().unwrap();
        assert_eq!(pretty(&value), r#""line\n🚀""#);
        assert!(Parser::new("01").parse().is_err());
        assert!(Parser::new("1.").parse().is_err());
    }
}