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

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

#[derive(Debug, PartialEq)]
struct Error {
    message: String,
    offset: usize,
}

impl Error {
    fn new(message: impl Into<String>, offset: usize) -> Self {
        Self {
            message: message.into(),
            offset,
        }
    }
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} at byte {}", self.message, self.offset)
    }
}

struct Parser<'a> {
    input: &'a str,
    pos: usize,
}

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

    fn parse(mut self) -> Result<Json, Error> {
        self.skip_whitespace();
        let value = self.parse_value()?;
        self.skip_whitespace();

        if self.pos != self.input.len() {
            return Err(self.error("unexpected trailing input"));
        }

        Ok(value)
    }

    fn parse_value(&mut self) -> Result<Json, Error> {
        self.skip_whitespace();

        match self.peek_byte() {
            Some(b'n') => {
                self.expect_keyword("null")?;
                Ok(Json::Null)
            }
            Some(b't') => {
                self.expect_keyword("true")?;
                Ok(Json::Bool(true))
            }
            Some(b'f') => {
                self.expect_keyword("false")?;
                Ok(Json::Bool(false))
            }
            Some(b'"') => Ok(Json::String(self.parse_string()?)),
            Some(b'[') => self.parse_array(),
            Some(b'{') => self.parse_object(),
            Some(b'-' | b'0'..=b'9') => self.parse_number(),
            Some(_) => Err(self.error("expected a JSON value")),
            None => Err(self.error("unexpected end of input")),
        }
    }

    fn parse_array(&mut self) -> Result<Json, Error> {
        self.consume_byte(b'[')?;
        self.skip_whitespace();

        let mut values = Vec::new();
        if self.take_byte(b']') {
            return Ok(Json::Array(values));
        }

        loop {
            values.push(self.parse_value()?);
            self.skip_whitespace();

            if self.take_byte(b']') {
                break;
            }

            self.consume_byte(b',')?;
            self.skip_whitespace();
        }

        Ok(Json::Array(values))
    }

    fn parse_object(&mut self) -> Result<Json, Error> {
        self.consume_byte(b'{')?;
        self.skip_whitespace();

        let mut entries = Vec::new();
        if self.take_byte(b'}') {
            return Ok(Json::Object(entries));
        }

        loop {
            if self.peek_byte() != Some(b'"') {
                return Err(self.error("expected an object key"));
            }

            let key = self.parse_string()?;
            self.skip_whitespace();
            self.consume_byte(b':')?;
            let value = self.parse_value()?;
            entries.push((key, value));
            self.skip_whitespace();

            if self.take_byte(b'}') {
                break;
            }

            self.consume_byte(b',')?;
            self.skip_whitespace();
        }

        Ok(Json::Object(entries))
    }

    fn parse_string(&mut self) -> Result<String, Error> {
        self.consume_byte(b'"')?;
        let mut output = String::new();

        loop {
            let byte = self
                .peek_byte()
                .ok_or_else(|| self.error("unterminated string"))?;

            match byte {
                b'"' => {
                    self.pos += 1;
                    return Ok(output);
                }
                b'\\' => {
                    self.pos += 1;
                    self.parse_escape(&mut output)?;
                }
                0x00..=0x1f => {
                    return Err(self.error("unescaped control character in string"));
                }
                _ => {
                    let ch = self.input[self.pos..]
                        .chars()
                        .next()
                        .ok_or_else(|| self.error("invalid UTF-8"))?;
                    output.push(ch);
                    self.pos += ch.len_utf8();
                }
            }
        }
    }

    fn parse_escape(&mut self, output: &mut String) -> Result<(), Error> {
        let escaped = self
            .next_byte()
            .ok_or_else(|| self.error("incomplete escape sequence"))?;

        match escaped {
            b'"' => output.push('"'),
            b'\\' => output.push('\\'),
            b'/' => output.push('/'),
            b'b' => output.push('\u{0008}'),
            b'f' => output.push('\u{000c}'),
            b'n' => output.push('\n'),
            b'r' => output.push('\r'),
            b't' => output.push('\t'),
            b'u' => {
                let first = self.parse_hex_quad()?;

                // JSON represents non-BMP characters as UTF-16 surrogate pairs.
                let code_point = if (0xd800..=0xdbff).contains(&first) {
                    if self.next_byte() != Some(b'\\') || self.next_byte() != Some(b'u') {
                        return Err(self.error("expected a low surrogate"));
                    }

                    let second = self.parse_hex_quad()?;
                    if !(0xdc00..=0xdfff).contains(&second) {
                        return Err(self.error("invalid low surrogate"));
                    }

                    0x10000 + (((first - 0xd800) as u32) << 10)
                        + (second - 0xdc00) as u32
                } else if (0xdc00..=0xdfff).contains(&first) {
                    return Err(self.error("unexpected low surrogate"));
                } else {
                    first as u32
                };

                output.push(
                    char::from_u32(code_point)
                        .ok_or_else(|| self.error("invalid Unicode code point"))?,
                );
            }
            _ => return Err(self.error("invalid escape sequence")),
        }

        Ok(())
    }

    fn parse_hex_quad(&mut self) -> Result<u16, Error> {
        let mut value = 0u16;

        for _ in 0..4 {
            let byte = self
                .next_byte()
                .ok_or_else(|| self.error("incomplete Unicode escape"))?;
            let digit = match byte {
                b'0'..=b'9' => byte - b'0',
                b'a'..=b'f' => byte - b'a' + 10,
                b'A'..=b'F' => byte - b'A' + 10,
                _ => return Err(self.error("invalid Unicode escape")),
            };
            value = value * 16 + digit as u16;
        }

        Ok(value)
    }

    fn parse_number(&mut self) -> Result<Json, Error> {
        let start = self.pos;

        self.take_byte(b'-');

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

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

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

        Ok(Json::Number(self.input[start..self.pos].to_owned()))
    }

    fn expect_keyword(&mut self, keyword: &str) -> Result<(), Error> {
        if self.input[self.pos..].starts_with(keyword) {
            self.pos += keyword.len();
            Ok(())
        } else {
            Err(self.error(format!("expected {keyword}")))
        }
    }

    fn consume_byte(&mut self, expected: u8) -> Result<(), Error> {
        if self.take_byte(expected) {
            Ok(())
        } else {
            Err(self.error(format!("expected '{}'", expected as char)))
        }
    }

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

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

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

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

    fn error(&self, message: impl Into<String>) -> Error {
        Error::new(message, self.pos)
    }
}

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

fn write_string(output: &mut String, value: &str) {
    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}' => {
                use std::fmt::Write;
                write!(output, "\\u{:04x}", ch as u32).unwrap();
            }
            _ => output.push(ch),
        }
    }

    output.push('"');
}

fn format_json(value: &Json, output: &mut String, depth: usize) {
    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(output, value),
        Json::Array(values) => {
            if values.is_empty() {
                output.push_str("[]");
                return;
            }

            output.push_str("[\n");
            for (index, value) in values.iter().enumerate() {
                write_indent(output, depth + 1);
                format_json(value, output, depth + 1);
                if index + 1 != values.len() {
                    output.push(',');
                }
                output.push('\n');
            }
            write_indent(output, depth);
            output.push(']');
        }
        Json::Object(entries) => {
            if entries.is_empty() {
                output.push_str("{}");
                return;
            }

            output.push_str("{\n");
            for (index, (key, value)) in entries.iter().enumerate() {
                write_indent(output, depth + 1);
                write_string(output, key);
                output.push_str(": ");
                format_json(value, output, depth + 1);
                if index + 1 != entries.len() {
                    output.push(',');
                }
                output.push('\n');
            }
            write_indent(output, depth);
            output.push('}');
        }
    }
}

/// Parses JSON and returns a two-space-indented representation.
fn pretty_print(input: &str) -> Result<String, Error> {
    let value = Parser::new(input).parse()?;
    let mut output = String::new();
    format_json(&value, &mut output, 0);
    Ok(output)
}

fn main() {
    let mut input = String::new();

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

    match pretty_print(&input) {
        Ok(output) => println!("{output}"),
        Err(error) => {
            eprintln!("invalid JSON: {error}");
            std::process::exit(1);
        }
    }
}

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

    #[test]
    fn formats_nested_json() {
        let input = r#"{"name":"Ada","active":true,"scores":[10,20],"extra":null}"#;
        let expected = r#"{
  "name": "Ada",
  "active": true,
  "scores": [
    10,
    20
  ],
  "extra": null
}"#;

        assert_eq!(pretty_print(input).unwrap(), expected);
    }

    #[test]
    fn handles_escapes_and_rejects_invalid_numbers() {
        assert_eq!(
            pretty_print(r#"{"text":"snowman: \u2603\n"}"#).unwrap(),
            "{\n  \"text\": \"snowman: ☃\\n\"\n}"
        );
        assert!(pretty_print(r#"{"number": 01}"#).is_err());
        assert!(pretty_print(r#"1e"#).is_err());
    }
}